Informatica A Journal of Computing and Informatics The Slovene Society INFORMATIKA Ljcbyana ST Informatica A Journal of Computing and Informatics Subscription Information f . ■ Informatica (YÜ ISSN 0350 - 5596) is published four times a year m Winter, Spring, Summer and Autumn (4 issues). The subscription price for 1991 (Volume 15) is US$ 30 for companies and IJS$ 15 for individuals. . . , Claims for missing issues will be honoured free of charge within six months after the publication date of the issue. . , ^ Printed by Tiskarna Tipa, Gosposvetska 13, Ljùbljana. Informacija za naročnike Informatica (YU ISSN 0350 - 5596) izide, štirikrat na leto, in sicer v začetku februarja, majä, avgusta in novembra. Letna naročnina v letu 1991 (letnik 15) se oblikuje z upoštevanjem tečaja domače valute in znaša okvirno za podjetja DEM 30, za zasebnike:DEM" 15, za študente DEM 8, za posamezno številko pa DM 10. . ; Številka žiro računa: 50101-678 - 51841. Zahteva za izgubljeno številko časopisa se upošteva v roku šestih mesecev od izida in je brezplačna. Tisk: Tiskarna Tipa, Gosposvetska 13, Ljubljana. Na podlagi mnenja Republiškega komiteja za informiranje št. 23 - 85, z dne 29. 1. 1986, je časopis Informatica oproščen temeljnega davka od prometa proizvodov. . . Pri financiranju časopisa Informatica sodeluje Republiški komite za raziskovalno dejavnost in tehnologijo, Tržaška 42, 61000 Ljubljana Informatica A Journal of Computing and Informatics EDITOR - IN - CHIEF Anton P. Železnikar Volaričeva ulica 8, 61111 Ljubljana ASSOCIATE EDITOR Rudolf Murn Jožef Stefan Institute, Ljubljana The Slovene Society INFORMATIKA Ljubljana Letnik 15 Številka 4 November 1991 YU ISSN 0350-5596 Informatica časopis za računalništvo in informatiko VSEBINA Modes for Reasoning about Cosciousness Design, Implementation and Testing of a Primal-dual Interior Point Method for Solving Linear Programs Pattern Recognition Using Kohonen Maps and Multi-layer Perceptrons Formal Informational Principles Planiranje s Prologom Dinamično dodeljevanje procesov na polju transputerjev Ocenjevano učenje v nevronskih mrežah Digitalizacija in vektorizacija črtnih risb veHkih dimenzij O.B. Popov J. Barle J. Grad Tjaša Meško A.P. Zeleznikar M. Likar N. Guid P. Zaveršek P. Kolbezen A. Dobnikar Jelena Ficzko Mira Trebar A. Dedič R. Mum D. Peček 1 5 12 19 36 43 53 60 Uporaba predznanja v induktivnem učenju Možnosti za vodenje sistemov s pomočjo metod umetne inteligence Povezava osebnega računalnika z robotskim krmilnikom ASEA-IRB Novice: 64 let dvoma o nastajanju UI Nada Lavrač Tanja Urbančič Michele Leonardi A. Klofutar L Gorkič A.P. Zeleznikar Avtorsko stvarno k?7fiio časopisa Informatica, letnik 15 (1991) 69 79 84 89 93 MODES FOR REASONING ABOUT CONSCIOUSNESS Keywords: intension, consciousness, knowledge representation, reasoning modes Oliver B. Popov Institute of Informatics College of Math and Natural Sciences University of Skopje Abstract: The ability to reason for an agent in the system S^ for the logic of consciousness LC is quite limited. To increase the power and the flexibility of the system, one needs additional modes which represent metatheorems of the original formalization. These modes are induced through plastic constraints or conditions that maintain the determination of the system. As expected, all the modes considered are qviestioned on the basis of their intuitive admissibility. 1. Introduction The development of formal systems for reasoning in artificial intelligence is necessarily influenced and measured by anthropomorphic characteristics and attributes. Intuitive admissibility is one of those. This characteristic with respect to the various types of reasoning was thoroughly researched by Hintikka in epistemic and doxastic context [Hin62]. Here, some of the well-known types or modes of reasoning are examined in the system S^, for the logic of consciousness LC [Pol91, Po391]. The ability to reason for an agent in the environment of the system Sj, , other then the standard axioms of (PC) and the mie of inference (RE) is quite limited. It is a compromise between the flexibility and the generality of the intensional approach and the rigid power of the modal logic systems such as S4 and S5 [CheSO], In a sense, it is consistent with the heuristic paradigm in artificial intelligence. Certain restrictions that are imposed on the class of conceptual structures n(M), with respect to which the system Sj, is determined, increase the number of logical devices (axioms and theorems)[HaI86]. For the basic definitions and concepts refer to [Po391]. The restrictions are accomplished by defining plastic constraints on the sets of consciousness {G(a,k)}. The constraints are termed plastic for the following reason: as long as a constraint holds for a particular instance of the system, that system is determined. The class of conceptual structures for which the system is determined considering given plastic constraint is denoted by ß(Mp). The axioms of the restricted system are actually the metatheorems of the generalized system S^,. 2. Modes for Reasoning The modes for reasoning in the primal state of knowledge, consciousness, are formalized and di.scussed on the basis of their intuitive admissibility. Mode 1 : (consciousness about the impossible) The plastic constraint imposed on an arbitrary set of consciousness is: Pi: A e e(a,k) where A denotes the empty set. For an agent to be conscious of the impossible means that it is conscious of a wff g such that g — > f & ~ f. Let the intension of f to be INT(t) and define the intension of ~ f to be INT(~ f) = K - INT(f). Denote the intension of ~ f with CINT(f), whence C1NT(0 is the complement of INT(t) with respect to the set of all complexes K. The Formula g is inconsistent since the formula (f & - t) is canonically unsatistlable and INT(t) n ClNT(t) = A. Situations could be encountered, in the reasoning t;paces encompassed by a KB (knowledge base), which may be declared to be inaccessible to any kind of activity until certain conditions are met. These situations, described by formulas of type g, may eventually lead to either a destruction of the reasoning mechanism or to violation of the entire KB. Prima facie, there is a utility in the requirement to have a reasoning agent conscious of the impossible. While this mode of rea.soning might prove useful in an epistemic context, it is inadmissible in a doxastic context. One cannot believe both propositions "There is a life on Mars" and "There is not life on Mars" in the same complex k. Another distinction is to be made between formulas ( aCON(0 and gCONC ~ 0) and jjCON(f & ~ f) which represent entirely different reasoning environments. The later one requires a time resonant interval for the formulas f and ~ f, while the former refers to two disjunctive time intervals. Finally, the behavior of the canonically unsatisfiable formula in the system PC is the argument against the inclusion of a state when someone is conscious about the impossible. Anything is derivable from a contradiction, therefore if an agent is conscious of the impossible it is conscious of everything possible. This certainly defies our intuition and it makes strong case against considering it in the system Sj,. Mode 2: (distribution of consciousness) The process of reasoning from universal toward particular facts is accomplished by the metatheorem (MT2) : aCON(f & g) -->aCON(f) & aCON(g) which is true if the plastic constraint holds: if INT(0 n INT(g) £ e(a,k) then INT(0 « e(a,k) and INT(g) c 0(a,k). Mode 3: (collection of consciousness) The mode that deals with the collection of consciousne.ss is the converse of the previous one. In this case the proce.ss of reasoning goes from particular toward universal facts. (MT3) : aCON(f) & aCON(g) -->aCON(f & g) is true if INT(0 « e(a,k) and INT(g) c 0(a,k) then INT(f) A INT(g) £ 0(a,k). A substitution of the "if ... then" condition in either one of the plastic constraints with the "iff" condition yields a single mode for reasoning. Mode 4:(the omniconsciousness of truth) If a reasoning agent is to recognize canonically true things, denoted by T, then the constraint to be met is K c 0(a,k) which as a result gives (MT4) : a CON(T ) A canonically true formula is true in every complex. Hence, the intension of T must be the set of all possible complex, i. e., INT(T) = K. Mode 5:( conscious about consciousness) This is a case which involves iteration of epistemic operators. It is a metatheorem of positive introspection and has the form: (MT5) : a CON(f ) - > ^ CON(CON(f )) The metatheorem is valid when the following plastic constraint is satisfied: if INT(0 e 0(a,k) then there exists a set of complexes K' such that K' = {i I INT(0 e 0(a,i)} and K' e 0(a,k). The arguments raised against the acceptance of the axiom of positive introspection in an epistemic environment are due to the (p.sychological) phenomena of repression and subconsciousness. It is generally considered that these phenomena are too much of speculative nature to be accepted as arguments in the context of artefact reasoning. However, there might be some technical difficulties with the realiz;ition of either positive or negative introspection. Let 5 denote the number of epistemic operators on the left side of the expression (MT5). The ò stands for a degree of reasoning about consciousness or knowledge. U can be observed that a degree of reasoning 6 always induces a higher degree (<5 + 1). An unlimited degree of reasoning onsequently requires infinite sets of consciousness. Mode 6: ( conscious about unconsciousness) This mode asserts that to be unconscious implies to be conscious about something one is not uncon.scious off. The mode for negative introspection is a sort of linguistic caveat. The peculiar linguistic expression is formalized in the following manner. (MT6): a~CON(0 -> aCON(t)(~CON(t)) is valid with the plastic constraint: if INT(t) / 0(a,k) then there exist a set of complexes K' such that K' = {i 1 INT(0/ e(a,i)} and K' c 0(a,k). It is intriguing to examine another propositional attitude, awareness, that has been introduced in a recent work on epistèmology in the context of artificial intelligence and computer science. Consider the language of the logic of consciousne.ss Assume that r(L(,) is augmented with a monadic operator 'AWE' so that ifa wff f s r(L(,) then aAWE(t) c r(Lj,). The operator of awareness 'AWE' might be viewed as a dual of the operator of consciousness 'CON' so that V( aAWE(t), k) = 1 iff CINT(f) / 0(a,k) , where V is the function of confirmation as defined in [Pol91,Po291]. Given a complex k, a rea.soning agent 'a' and a wff f, by the definition of the consciousne.ss, for 'a' to be conscious of f means that the INT(t) t 0(a,k). The epistemic operator "CON' is a sort of an existential quantifier over the .set of possible concepts and hence complexes for 'a'. Various concepts may exist within a given KB. Nevertheless, they do exist for 'a' if and only if the concepts are elements of the agents 'a' set of consciousness for some complex k c K. When the notion of awareness is concerned , an agent is aware of a formula f if the complement of the intension of f is not an element of its set of awareness. The previous argument does not guarantee that the intension of f is indeed in the agent's set of awareness. What is posited is illustrated in the next example. Let 'a' be conscious that the concept , i. e., the proposition "grass is green" is true in the complex k. In the case of awareness, 'a' is aware that "grass is green" in a complex k if and only if 'a' is not conscious that "grass is not green". The problem with the inclinations such as negative introspection and even awareness is beyond intuitive admissibility. First the theoretical basis for both notions is somehow superfluous and troublesome. The reason being is that with modalities there is no 'clear cut negations' as there is in standard logical systems. The distinction between the two inclinations, consciousness and awareness, may be accepted as a distinction between definitive and possible information [Hal85]. The operator of awareness enables the alternative formulation of the negative introspection as aAWE(f) -->aCON(AWE(f)). The formulation is consistent with the idea of duality in modal and intensional theories. Absence of consciousness does not entail total ignorance about a certain concept. There is a possibility, no matter how small, that a concept is accessible. 3. Conclusion Being quite limited in its potential to offer variety of types of reasoning, the rudimentary system for reasoning about consciousness S^ is enlarged with different modes whose intuitive admissibility is discussed. These modes of reasoning are induced through the imposition of plastic constraints. The selection of particular constraint depends on the nature of KB and the type of reasoning required for the manipulation. All of the standard axioms that are presented [Hin62] are formalized in the intensional context of the logic of consciousness LC. References [CheSO] Chellas, B.F. Modal Lol'Ic. Cambridge University Press, 1980. [Hal86| Halpern, J. "Reasoning about Knowledge: An Overview" in Reasoning about Knowlediie ed. by Halpern, J. , (1986), Morgan Kaufmann, pp. 1-17. [Hin621 Hintikka, J. Knowledge and Belief. Cornell University Pre.ss, 1962. [Hin86] Hintikka, J. "The Paradigm of Epistemic Logic" in Reasonins; about Knowled'je. ed. by Halpern, J. , (1986), Morgan Kaufmann, pp. 63-81. [Kap64] Kaplan, S.C. "Foundations of Intensional Logic", Doctoral Dissertation, UCLA, 1964. [Kri63] Kripke, S. " Semantical Analysis of Modal Logic II: Non-normal Propositional Calculi" in The Theory of Models, ed. Henkin, L. and Tarski, A. , North-Holland, 1965, pp. 206-220. lMon74] Montague, R. Formal Philosophy Yale University Press, 1974. [Po 190] Popov,B. O. "The System of Knowledge", Informatica. Vol. 14, No. 4, October 1990, pp. 87-90. [Po291] Popov, B. O. "An' Intensional Approach towards Omniscience", International Symposium on Information Technology Proceed., Sarajevo, March 1991, pp. 235/1235/5. [Po391] Popov, B. O. "Consciousness as a Prerequisite for Knowledge". Informatica,Vol. 15, No. 3, August 1991, pp. 1-8. DESIGN, IMPLEMENTATION AND TESTING OF A PRIMAL-DUAL INTERIOR POINT METHOD FOR SOLVING LINEAR PROGRAMS Keywords: linear programing, primal-dual interior point algorithm, sparse Cholesky factorization Janez Barle and Janez Grad Univerza v Ljubljani Ekonomska fakulteta Kardeljeva ploščad 17 61109 Ljubljana ABSTRACT: This paper describes our implementation of a primal-dual interior point algorithm for linear programming. The topics discussed include economic data structures, efficient methods for some sparse matrix operations, sparse Cholesky factorization, methods for handling dense columns and comparisons with simplex based methods. Extensive numerical results demonstrate the efficiency of the resulting algorithm as well as some problems which remain to be solved. The role of interior point based solvers in the process of solving large-scale mathematical programming models is also discussed. SNOVANJE, IMPLEMENTACIJA IN TESTIRANJE PRIMARNO-DUALNE METODE NOTRANJE TOČKE ZA REŠEVANJE LINEARNIH PROGRAMOV: V sestavku je opisana naša implementacija primalno-dualne metode notranje točke za reševanje linearnih programov. Obravnavane so ekonomične podatkovne strukture, učinkoviti načini za izvajanje nekaterih operacij z razpršenimi matrikami, razpršeni razcep po Choleskem, metode za delo z gostimi stolpci ter primerjave z metodo simpleksov. Izčrpni rezultati numeričnega testiranja kažejo tako učinkovitost razvitih algoritmov, kot tudi nekatere probleme, ki jih je treba še razrešiti. Opisana je tudi vloga reševanja z metodami notranje točke v splošnem kontekstu modeliranja in reševanja velikih problemov matematičnega programiranja. Introduction The J.iiiear prograjjuiiing (LP) problem may be stated in the f'tji'ih; minimize (maximize} c'^x subject to:Ax=b, Ji.;l; struct.uroH tliat can be effectively exploited. Kfforts to develop software systems for solving super size LP problems with Kaniiarkar's fUgoritlmi proved to be \'ery fruitful. One of the outstanding steps in this direction is AT&T's KORBX system. The system consists of botli hardwai-o, which uses parallel processing, and software which ex^Jloits the resources of this hai-dware (Carolai! et al., 1990). However, there is also a necni for exploring ability of interior point methods for solving LP on a more widely available serial computers. In the paper we present our woi'l( in this dii-ection, which was perfor-metl on MS-DOS personal computers and VAXAflS minicomputers. Algorithms Nowadays a plethora of research palmers is published where different interior point, metiiods are i.>roposed. We have employed the variant of a primal-dual interior point method which is supposed to be among ttie most efficient (Lustig et al. 1989). In order to mal^e cleai-differences between such kind of methods and simplex based algorithms, we first give a brief explanation of the revised simplex algoritlun. The stops of this algorithm are roughly described within tht: following box where B denotes tile basis matrix and cb the cost vectoi-of the basic variables. It is therefore assumed tliat there is a set of m basic variables, which is usually clianged after each iteration in such a way that one nonbasi<; variable enters the basis and one basic variable leaves the basis. The informal description which follows is related to the second phase of the primal i-evised simplex algorithm, where the Ixisic feasible solution is already known. -Rev i sesi-s impi ex-me thod- Rl: Produce a pricing vector: u = cd''B-' (BTRAN). R2: Select the entering variable Xb (column u = Pan) according to a given pricing strategy. If no entering variable ia found, terminate (solution is optimal). R3: Update the entering column : v = B"'u (FTRAN). R4: Determine the leaving variable. If none is found, tenninate (problem is unbounded). R5: Update the basis matrix representation; refuctorize if necessary. Go to Rl. It must be noted however that there is not yet general agreement about what are the best algoritlims in detail, Eiiid how they should be implemented in the most efficient way. In general, number crunching operations are concentrated within the steps Rl and R3 where two systems of linear equations have to be solved (these üjserations are often refered to as BTRAN and FTRAN). It is very important that after basis change updating of basis matrix is possible without performing full factorization, which has to be done only periodically. Other steps, particularly R2 and R4, deal mainly with logic decision and "book-keeping" problems. It is also obvious that a rather sophisticated data structures must be employed in order to exploit sparsity (Duff et al., 1989). Interior fxjint methods differ considerably from the simplex method. Primal-dual interior point method, which we have decided to implement, requires LP problem being foniiulated in the following form: miniiiiize c'''x subject to: Ax = b, x + s = u, x > 0, s > 0 with the asso':;iated dual maximize b^y - u^w subject to; A'^y - w+ z = c, w>0, z>0 (2) (3) Fortunately, formulation (2) can be derived in a straightfoi-ward way from formulation (1). An outline of the algorithm is sketched within the following box, where X, S, W and Z are diagonal matrices with diagonal elements equal to the components of corresponding vectors x, s, w and z. ® is the user supplied constant which is usually computed by using the following f onnula : 4> = $(n) = n2 n < 5000 n/n n > 5000 and M = xiKn) »max ( [c|(i., Nbjo} where t is a scalar multiplier which is used to allow variations of the initial |j. Furthei-more, do = A^'y« + z" - c, where y« and z° are initial y and z, and e = (1,1,...,!). od, Op are some appropriate step lengths in tlie primal and dual ajÄUDes i'esiX!Ctively. These step lengths must be chosen in a way which ensui-es nonnegativity of variables x, s, z and w, foi- example ; U|, = ao^min (minj (xj/-6xj , 6xj<0}, minj (sj/6xj , 6xj>0}} ud = uo *min {mirij (zj/-6zj , fiZj <0}, minj (wj/-öwj , 6wj<0)} wliere 0W + X->Z)-' K3: Corajxite positive definite matrix AOA''. K4: Perform Cholesky factorization of the ABA" K5: Compute o(n) = ij(S-i - X-' )e - (W - Z)e K6: Compute 6y = -(AeA^)-i(A6(o(n) + zodc) + (Ax - b)) 5x = e(Ai'6y + o(p) - Zbdo ) 6s = -6x 6z = -uX-'e + Ze - X-' Z6x 6w = -pS-'e + We - S" ' Wüx K7: Update y»«« = yoi j - Oäöy Xnew = Xoi d - ap 6x Sue u = Sol d - ap6s Zoe w = Zo I d - ad 6z Wo, w = Wo I đ - Qd 6w K8: If relative duality gap satisfies relation: c''x + u^w - b^y 1 + jui'w - bTy| < £ where 6 is user supplied constant, terminate (solution is optimal). Otherwise go to K1. It was also assumed that the initial interior solution is supplied by the user. For example, it is possible to choose X« - z" = min{e,u/2) and yo = 0 (Choi et al., 1990). In general, interior point methtjds are not very sensible to the choice of the initial solution. The above description is based on two papers (Lustig et al. 1989, Choi et al. 1990) where algorittaiic asix.-cts of tlie modularized fortran code OBI (Optiiiiizot ion with Barriers I) were described. Our intention was to ■Jevelop our own code based on mentioned pajKirs and stanjai-d methods for computing sparse Cliolesky factorization (George, Liu, 1981). However, some of tlie implementation details are different, for example: a) In our implementation colvaiin Axo -. b and row do aru computed at esich iteration, rather than only for the initial solution, xa and ya are defined as ratio« between current and initial a> norms of Axo - b find do. Furthermore, Xa and ya retain some small value even in the case if their computed vsalue is zero, Such approach enable us to save some stoi-oge space-and also, according to our experience, to improve accuT'acy of the computed solution. b) Sometimes it is impossible for relative duality gap to reach prescribed 6 on step K8. In such cases we tei-minate algorithm when relative difference between two subsequent objective values become smaller tlian tlie prescribed constant, which is usualily set to be 0.1*e, On the whole, published description of the algoritlun is good enough to enable everyone to create, jiossibly after some experimental investigation, workable implcniontation of a primal dual interior point method. Evidently the? algorithm consists mostly of floating point comixitat ions ajid consequently fortran is £in obvious choice of implementation language. Some features of the inlorior point metlioda that make them so much different from thi-simplex method are obvious: 1) 'Thei-e is no partitioning into tosic and nonlsjsic variables. Tliis means that, in pi'inciple, all variables and constraints are handled i.n equal way during the solution process. 2) Each iteration requires computationally expensive factorisation of positive definite matrix or solution of the least squares problem. 3) Solution vector x is always an interior point of the solution polytope. Feature 1) has a far-reaching consequences. It can be a means for. avoiding potential combinatorial problems arising in the movement from one basis to another which is typical for simplex method. On the other hand such approach may degrade computational speed and stability, Tlie niaiii computational problem of tjie interior point methods is inversion of matrix AQA'' or solution of the coi-responding linear least squares problem. This is usually done by computing spai-se Cholesky factorization of A0A''. In order to understand methods for doing this, one must be acquainted with the methods for storing sparse matrices. In the next section the methods for storing sparse matrices which were applied in our implementation of primal-dual interior point methods are briefly described. Data structures and implementation issues Ex-ploitation of sparsity is based on the fact that only nonzero elements of sparse matrix (or vector) must be stored, together with information about their position within matrix (vector). In the case of LP input data (A, b, c, u) wittiin the framework of interior point methods, we have employed the following data structures: 1) Righthand-side vector b is stored eis a dense vector. 2) Constraint iijatrix A is stored using three one dimensional vectors (XA,IA,CP) where XA = vector of nonzero values Aj j which are sorted by columns and (secondary) by row indices within a particular column, both in increased order. lA - vector of row indices of nonzero elements, which are sorted in a same manner as XA. CP = vector of column pointers which consists of locations where the representation of columns begins in XA and lA. For example, elements of column i are all in locations from CP{I) to CP(I+1)-1. 3) Nonzero elements of c are stored (formally) as n+1. coluimi of A. liierefore they are stored between locations CP(N+1) and CP(N+2)-l in XA (values) and lA (indices). 4) Noninfinite elements of u are stored (formally) as n+2. column of A. Therefore they are stored between locations CP(N+2) and CP(N+3)-l in XA (values) and lA (indices). Obviously, it is also necessary to store the matrix A9A'' and its triangular factor L, in the case if Cholesky factorization is used within the solution process. These matrices can be stored using the same storage locations. Tlie ajnount of this storage is determined by fill-in which generally can not be avoided during the Cholesky factorization of ASAt. It is therefore advisable to try to minimize fill-in by appropriate reordering of rows and coli-rains of ASA^ . Ordering algorithms are essentially graph teclmiques for obtaining appropriate numbering of t)ie graph nodes. In our CEise nonzero structure of ASA'' represents an undirected graph G(X,E) with m nodes. The adjacency list of node xgX is a list containing all nodes adjacent to x, which is represented by indices of nondiagonal nonzero elements of corresponding column of ASAf . Tlie implementation of described structure is done by storing the adjacency lists sequentially in integer array ADJNCY along with an index vector XADJ of length iM+1 containing pointers to the beginning of the lists in ADJNCy. Ttie extra entry XADJ(M+1) points to the next available location in ADJNCY (George, Liu, 1981). These arrays aie input data for ordering algorithms which can be generally divided in two groups: a) reoi-derings which try to minimize number of nonzero elements (and therefore fill-in) in triangular factor L. Although it is known to be NP-cowsplete problem (Duff et al. 1989) several reasonable good heuristics exist. One of tliem is the minimum degree algorithm. The name of this algoriOini is derived from its graph theoretic interpretation: in the graph associated with a symmetric si^arse matrix, tliis strategy corresponds to choosing that node foi-the next elimination which has the least edges connected to it. b) i-eorderings which try to permute AOA^f and triangular factor L into some particular desirable form. This can be for example so-called envelope or profile form. The most known algorithm of this type is the Reverse Cuthill-McKee algorithm. The objective of such kind of algorithms is to reorder the rows and columns of the matrix so that the nonzeroes in the obtained matrix are clustered near the main diagonal since this property is retained in the corresponding Cholesky factor L. Such a cluster is called the profile or envelope and is defined to contain also all zero elements between the diagonal and the last nonzero element in the row or column. Tlie problem of minimizing the envelope size of a matrix is proven to be NP-complete (Billionet, Breteau, 1989) and consequently the Reverse Cuthill-McKee algorithm is only one among heuristic procedures for doing this. We have implemented both the minimum degree and the Reverse Cuthill-McKee algorithm within our LP package. In order to give some insight into these methods, we shall show how they perform on the smallest exajiiple from the NETLIB library (Gay, 1985), which is known under the name AFIRO. This is the problem with constraint matrix having 27 rows and 51 columns which contain all together 102 nonzero elements. Its corresponding ASA'' matrix has the structure as in the following picture, where only the upper triangular part is reproduced: 111111111122222222 123456789012345678901234567 1 D X X X X X 2 D X X X 3 D X 4 D X 5 D X X X X X X X 6 D X X X X X X 7 D X X 8 D X X 9 D X X 10 D X X 11 D X X X X X X 12 D X X X 13 D X 14 D X 15 D X X X X X X X 16 D X X X X X X 17 D X • X 18 D X X 19 D X X 20 D X X 21 D 22 D 23 D 24 D 25 D 26 D 27 D Figure 1. AFIRO - structure of the upper part of ASAT Nondieigonal eind diagonal nonzero elements are presented using symbols X and D respectively. It is obvious that, at least in this case, matrix ABA'' is not as sparse as matrix A itself. Moreover, number of its nonzeroes may substantially increeise during the subsequent Cholesky factorization. The following picture displays how this sitution is controlled by applying the minimum degree algorithm. The produced ordering (permutation of rows and columns) is: (4,14,26,27,13,22,12,3,24,2,1,11,10,17, 18,19,20,23,16,15,9,8,25,21,6,7,5) 122121 2 111112211 22 446732234211078903659851675 4 14 26 27 13 22 12 3 24 2 1 11 10 17 18 19 20 23 16 15 9 8 25 21 6 7 5 D X X X D X X X D XXX D X X X D X X X D X X D X D X X X X X X X X X X X X X X X X X X X X D X X X X D X X X X D X X X X D X X X X D X X X X D X X X X D X X X X D X X X D X X D X D Figure 2. AFIRO - structure of the Cholesky factor The above structure is determined not by actual iiuiiierical factorization but by simulation of it, or so called symbolic factorization. The advantage of this appioach is that the data structures are set up once for all, as the structure of the matrix does not change from one iteration to another. Obviously, at each iteration it is necessary to perfonn numerical factorization since A0A1' is changing along with diagonal matrix 6. The data sti-uctures returned by the symbolic factorization can be presented in a sparse storage scheme known as the ooiiipreased storage scheme of Sherman, cited in (George, Liu, 1981). The scheme has a storage array LNZ which will contain all nonzero entries in the nondisigonal part of Cholesky factor L column-wise (or, which are the same numbei-s, in thie L^ row-wise), an INTEGER vector NZSUB which will hold the row subscripts of the nonzeroes, and an index vector XLNZ whose entries are pointers to the beginning of nonzeroes in each column in LNZ. The diagonal elements are stored separately in vector DIAG. In addition, an index vector XNZSUB is also used to hold pointers to the start of row subscripts in NZSUB for each column. This is the consequence of the key idea of the Sherman's compressed scheme: some of indices from NZSUB can be used for presenting nonzero patterns of two or even more columns. For example, it is applicable when columns 17,18,19,20 from the Figure 2 are considered. Described data structure is filled et each iteration after computation of ASAf is performed. The subsequent Cliolesky factorization is performed using the same data structure. An interesting question is what is the best way to compute ASAf. At first sight row-oriented data structure for matrix A seems to be more practical and efficient when computation of A8A'' is considered. However, theoretical arguments (Duff et al. 1989) and practical testing convinced us that column-wise storage of A is much more efficient. Tiie point is in avoiding operations with zero components of A. Perhaps this c£in be best explained with our fortran code for computating ASAf, which follows. C At this moment LNZ and working vector Z must be C initialised to zero values. DO 500 IC0L=1,N ISTART = CP(IOOL) ISTOP = CP(I00L+1) - 1 DO 100 I=ISTART, ISTOP J = IA(I) Z(J) r XA(I)*THETA(IC!OL) DIAG(J) - DIAG(J) + Z(J)*XA(I) 100 CONTINUE DO 200 I=ISTART, ISTOP-1 IROW = IA(I) ZO : Z(IROW) L = XLNZ(IROW) KSUB : XNZSUB(IROW) JBEGIN =1+1 DO 150 J=JBEGIN,ISTOP 125 (CONTINUE IF (NZSUB{KSUB) .EQ. IA(J)) 'ITIEN LNZ(L) = LNZ(L) + ZO*XA(J) ELSE L = L + 1 KSUB = KSUB + 1 GOTO 125 ENDIF CONTINUE CONTINUE DO 300 I=ISTART,ISTOP Z(IA(I)) = 0.0 CONTINUE 500 CONTINUE CtiHttttt*tttt*%tttttt*tii********ttttt%t*%%%**iit**ttt*ti-t 150 200 300 Another ordering algorithm which we have implemented is the Reverse Guthill-McKee algorithm. Its perfoniiance on our test problem is presented on the following picture. 2 1 2 2 2 1 1 1 1 75536098709 1 2 1 2 112 1 2 765144231431226 27 15 25 23 6 20 19 18 17 10 9 8 7 16 5 21 14 4 22 13 11 24 3 1 12 2 26 D X D X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X D X X X X X X X X D X X X X X X X D X X X X X X D X X X X X D X X X X D X X X D X X D X X X X X X X D X X D X X D X X X D X X D X X D X X D X D X X X X X X X X X D X X D X D Figure 3. AFIBO - Envelope after ROM algorithm The storage scheme for envelope methods has a main storage array ENV which will contain all entries (zeroes as well as nonzerc-es) between tlie first nonzero entry in row of L (or column of L^) and the diagonal, an index vector XENV whose entries are pointers to the beginning of nonzeroes in each row of L, and a vector DIAG where diagonal entries are stored. Our- practical experience with the Reverse Cutliill-McKec algorithm was quite disappointing. Its corresponding storage sclieme is usually not as economical as those produced by the minimum degree algorithm. The results concerning speed of the numerical factorization were even less competitive. However, it would be interesting to try otiier profile methods. Some of them produce more economical storage scheme than the Reverse Cuthill-McKee algoritm (Billionet, Breteau, 1989). There are also some other efficient ordering algorithms, for example the nested dissection ordering algorithm (George, Liu, 1981). Their quantitative and qualitative comparisons may be an interesting topics for further research. Handling of dense columns The problem is what to do if one or more coltrains of A ure dense vectors. In such cases computation of AGA^ leads to a very dense matrix eind therefore should be avoided, if it is possible. This situation can be overcome by first dividing columns of A into dense and sparse subinatrices : A = [Aa;A iteration log MPS data IJvalues data problem file messages reports Figure 5. LPINT system architecture Conclusions Generally we can say that the interior point methods arc-getting more and more reliable and sophisticated aa well. Moreover, interior point methods had greatly influenced algoritlimic and experimental work in the field of linear programming. However, it is not likely that interior point methods can completely replace tlie simplex method in future. In our opinion rfjasons foi-this are mainly in simplex method ability to produce optimal basic solution. The knowledge of basic status of variables is very important, especially when postoptiraal einalysis or solution of mixed integer programs are considered. Ch the other hand, when one wish to solve big LP problem for the first time, it is advisable to start with some interior point based package. It is a fast, reliable and robust way to obtain the first information about LP model. A primal-dual interior point method can be implemented in a rather easy and straightforward way. This fact, as well as method's efficiency Eind mathematical elegance, can be a big step toward deeper understanding of interior point methods in general. References 1. Adler, I., Kannarkar, N., Resende. M. and Veiga, G. (1989>, "An Implementation of Karmarkar's Algorithm for Linear Programming", Mathematical Progranming, Vol. 44, pp. 297-335. 2. Alvarado, F.L. (1990), "Manipulation and visualization of sparse matrices", ORSA Journal on Computing, Vol. 2, pp. 187-207. 3. Andersen, J., Levkovitz, R., Mitra, G. and Tamiz, M. (1990), "Adopting Interior Point Algorithm for the Solution of LPs on Serial, Coarse Grain Psirallel Computers". Presented at the International Symposium on Interior Point Methods for Linear Programming: Theory and Practice, January 18-19, 1990, Europe Hotel, Scheveningen, Netherlands. 4. Billionnet, A. and Breteau, J.F. (1990), "A Comparison of Three Algorithms for Reducing the Profile of a Sparse Matrix", Recherche Opérationnelle, Vol. 23, pp. 289-302. 5. Carolan, W. , Hill, J., Kennington, J., Niemi, S. and Witchntan S. ( 1990 ), "An Empirical Evaluation of the KORBX Algorithms for Military Airlift Applications", Operations Research, Vol. 38, pp. 240-248. 6. Choi, C., Monma, C.L. and Shanno, D.F. (1990), "Further Development of a Primal-Dual Interior Point Method", ORSA Journal on Computing, Vol. 2, pp. 304311. 7. Duff, I.S., Erisman, A.M. and Reid, J.K. (1989), Direct Methods for Sparse Matrices, Clarendon Press, Oxford. 8. Gay, D.M. (1985), "Electronic Mail Distribution of Linear Programming Test Problems", Mathematical Programming Society COAL Newsletter, Vol. 13, pp. 10-12. 9. George, J.A. and Liu, J.W. (1981), Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs. 10. Gondzio, J. (1991), "A Method for Handling Dense Columns of Linear Programs in the Interior Point Algorithm", Presented at the International Symposium "Applied Mathematical Programming and Modelling", London. 11. Karmarkar, N.K. (1984), "A New Polinomial-Time Algorithm for Linear Progi'amming", Combinatorica, Vol. 4, pp. 373-395. 12. Lustig, I.J., Marsten, R.E. and Shanno, D.F. (1989), "Computational Experience wi^ a Primal-Dual Interior Point Method For Linear Programming", Teclinical Report SC® 89-17, School of Industrial Engineering and Operations Research, Georgia Institut of Technology, Atlanta. PATTERN RECOGNITION USING KOHONEN MAPS AND MULTI-LAYER PERCEPTRONS Keywords: multi-layer perceptrons, initialization, a Kohonen map, clustering Tjaša Meško Factuly of Electrical Engeneering and Computer Science University of Ljubljana Multi-layer perceptrons (MLPs) are now widely used for pattern recognition tasks such as specch recognition, liandwritteu character recognition, face recognition, etc. They were proven to generalize well to unseen data. Another kind of neural networks, namely, self-organizing feature maps have also been applied occasionally in pattern classification, but they were not that successful. In this study it is investigated how self-organizing feature nia[)s could be useful in combination with MLPs as a tool for initializing the weights of a MLP. The purpose of the rcscarch was to reduce the amount of supervised training which is required to train MLPs. PREPOZNAVANJE VZORCEV S KOHONENOVO MAPO iN Z VEČNIVOJSKIMI PERCEPTRONI. Večnivojski perceptroni se v zadnjem času pogosto uporabljajo pri prepoznavanju vzorcev (na primer govora), prepoznavanju pisav, prepoznavanju obrazov in podobno. Druga vrsta nevronskih mreŽ, Kohonenove mape, so bile tudi občasno uporabljene pri reševanju podobnih nalog, vendar rezultati so bili slabši. V tem članku je obravnavana možnost inicializacije uteži skritega nivoja trinivtgskega perceptrona. Namen te raziskave je skrajšati čas učenja perceptrona. 1 Kohonen Self-Organizing Feature Maps The self-organizing map belongs to the category of neural networks that use unsupervised training. This means that each time a new input is presented to the map, the desired output is unspecified. This type of neural networks is used to perform data compression, such as vector quantization and as it will be explained later, to reduce the amount of supervised training. A vector quantizer is a mapping, q, that assigns to each input vector x — (xi, • • • > a^iv), a codebook 'A young researcher, employed in PAREX, d.o.o. vector Ci = (cu, Ci2, • • •, Qjv) Ci = qix) drawn from a finite set of codebook vectors Q - {Č1,Č2, . ..,čm} where M is the number of codebook vectors. The quantizer q is completely described by the set of codebook vectors and it divides the input vector space into clusters Ci = {x:qix)=či] (1) of input vectors which are mapped onto the i"* codebook vector. The distortion caused by reproducing an input vector x by a codebook vector c; is given by / Figure 1: Locations of map vectors in a square lattice. Vector fäij can also be addressed as where v — ii-l)J + j. d[x,Ci), where d is assumed to be a Euclidean distance which is defined by equation 2. d{x, Ci) = N Y^iXn -Cin? (2) n = l Kohonen's algorithm creates a vector quantizer by adjusting vectors which are typicaly arranged in a two-dimensional grid (usually a square or a hexagonal lattice). In this study square maps will be used (see figure 1) and the map vectors will be represented by their map coordinates {i,j). The vector at position {i,j) in the map will be addressed in two ways, • m.j, {i,j) = (l,l),...,{I,J) • Cy, V = 1,2,... ,I X J where Wiij equals and I, J are the map sizes. The vector quantizer function g(x) corresponding with a Kohonen map selects the codebook vector č„ which is closest to x: d(x,c„) = mmd(x,čj;), fc = 1,2,..., I X J In order to create the best codebook vectors, an iterative training is performed. During each iteration, a neighbourhood is defined around each vector of the map, as shown in figure 2. The neighbourhood NE(t) slowly decreases with time. At the beginning, the map vector components are initialized to small random values. Then, the following iterative procedure is applied whenever a new input vector is presented (< is the iteration number). 1. Compute the Euclidean distances d{x{t),čf;{t)), to all nodes Cv(<) according to the equation 2. 2. Select the node producing the minimum distance as the winning node č„. Figure 2: Topological neighbourhood at different times as the feature map is formed. NEv{t) is the set of nodes considered to be in the neighbourhood of a node č„ at time t. The neighbourhood is decreased in size as time increases. In this example, 0 < < <2- 3. Compute an updating factor a{t) and define a topological neighbourhood NEt,{t). 4. Update the map vectors belonging to the topological neighbourhood of the winning node. For the adaptation of a map vector Ck the following formula is used, ct„(< -(-!) = Ci„(t) -f a{t){x„{t) - Ckn{t)) where n = 1, 2,..., A''. The input vectors are taken from an input database, and are presented in a random order. The process is terminated as soon as the average distortion introduced by the vector quantization does not drop any more. Parameter a(t) is initialized to a value between zero and one, and is decreasing with time. In this study an exponential rule for adapting a and for determining the topological neighbourhood [Brauer and Knagenhjelm, 1989] was used. In order to use the Kohonen map for pattern classification, each map vector has to receive a label. The easiest way to achieve this is by applying the maximum a posteriory criterium: the labeled observations of a training set are presented to the map, and each node is labeled according to the number of observations of the different classes that were assigned to that node. Once the map is labeled, it can act as a pattern classifier. The percentage of wrongly classified examples (the error rate) can be made as small as desired by introducing a large enough number of vectors. However, as it will be explained later, the training of a large map can be very time consuming and it is likely that such a map will not generalize properly to the unseen examples. 14 6x6 9x9 12 X 12 15 X 15 train 74,55% 79,26% 81,02% 82,72% testi 73,35% 77,59% 79,45% 80,79% test2 75,47% 78,97% 79,85% 81,35% Table 1: RecognUion rates on a BPC task, using different Kokonen maps. 2 Radial Basis Function Network A traditional back-propagation network [Rumelhart et al., 1986] consists of nodes whose outputs are nonlinear, differentiable squashing functions (typically sigmoid functions) / of the weighted sum of activations emerging from nodes on the previous layer. The output of node i is computed as follows, Oi = fiYl ^'jyj + "''o) 1.1 Results Using the Kohonen Map The Kohonen map was tested as a pattern classifier on a Broad Phonetic Classification (BPC) task of Dutch spoken utterances. Here are the following five classes of the BPC task: vowel, sonorant, fricative, burst and closure. We have used a hand-labeled multi-speaker database of continuously spoken Dutch numerical strings, uttered by 30 different speakers (15 male and 15 female). The database consists of 300 different utterances (10 from each speaker). For training, 192 utterances from 24 speakers (8 from each speaker) are used and 108 utterances are used for testing. The test set is divided into 2 sets: testi, a multi-speaker test set (the remaining 48 utterances from the training speakers), and test2, a speaker independent test set (60 utterances from 6 new speakers). The speech signals were bandlimited to 4 kHz and sampled at a rate of 10 kHz. A 20-dimensional feature vector was extracted every 10 ms by means of an auditory model [Martens and Van Immersed, 1990]. To take into account the dynamic nature of speech, several successive frames were presented simultaneously at the input of the map. In particular, we have used a feature vector consisting of three input frames: the first two frames were contextual frames located 40 and 20 ms ahead of the third frame which was the one to be classified. Therefore, each input vector consisted of 60 elements. The map vectors were labeled according to the maximum a posteriori criterium. The recognition rates for the different data sets are very similar, indicating an excellent generalization to unseen data. However, the featuremap cannot compete with a Multi-Layer Perceptron (MLP) trained by means of the back-propagation algorithm [Rumelhart et al., 1986]. Such a MLP obtains a recognition rate of 87, 20% on the second test set [Depuydt et al., 1990]. The question was whether it would be possible to use the clusters obtained by the map to initialize the weights of a feed-forward net, and consequently to improve the supervised training time of that network. where Wij represents a connection weight, tu,o a bias variable, and yj an output from a previous layer. The argument of / defines the following hyperplane in the input space: Y^Wijyj -{-Wio = 0 The hyperplanes defined by the different nodes constitute a set of class boundaries. Searching for other ways of using the back-propagation algorithm, and thereby defining other kinds of class boundaries the idea of using radial basis function networks was introduced [Lowe, 1989]. The RBF network contains a hidden layer of m RBF units represented by the centres Cj. The output layer consists of traditional summation units. Thus, the value of an output unit i is, j=i with / representing the sigmoid function, and a RBF centered around a vector Cj. Using the standard neural network terminology, the above formula for calculating the output of the output-layer node in response to the p"* input pattern, o,p can be stated as, m °ip = fiJ2 - Č;||) + Wio) j=i In this study, a network consisting of a hidden layer of Gaussian nodes is considered, therefore, functions are assumed to be, N n = l i" where the parameters ajn represent the standard deviations of function ^j. The above network could be trained using the back-propagation algorithm with gradients: dyj _ yjjxk -Cjk) dcjk Qy, ^ yjixk-cji)"^ da J k where "5j(||zp — čj||) is addressed as yj. It was suggested that a network with RBF nodes could be trained by means of a layer-by-layer type of training (Gaussian nodes can be trained separately). In this case a computationally efficient way of determining the optimal weights to the output layer can be proposed [Renalds and Rohwer, 1989]. If yjp is the output of RBF j given training input Xp, then the output of output node i will be, o.p = /(13 ^ijVjp + ^io) For optimal weights it holds that E = O.bJ^ioip - Oipf >p is minimal, where Oip is the desired value of the output node i. It can be shown [Renalds and Rower, 1989] that the optimal weights can be obtained as follows, k P (3) where M is the correlation matrix of the RBF outputs Mji^^yjpVip p It is advised to use the pseudo-inverse of M to avoid possible singularities. 3 Initialization of Gaussian Nodes With the error back-propagation algorithm, there is always a chance that the training gets trapped into a local minimum. The search of the optimal network configuration can also be very time consuming. Especially the determination of an optimal number of hidden units is a long process since the training has to be repeated for different amounts of hidden units. If there are too many hidden units, the generalization capabilities of the network might be reduced. If the number of hidden units is too low, the subspaces created by thè network nodes cannot adequately model the class boundaries. Therefore, a dimensionality analysis of neural networks with one hidden layer of Gaussian liidden units and an output layer of conventional summation units was suggested [Weymaere and Martens, 1991]. The weights of the Gaussian nodes are initialized to values which are obtained by a modified k-means clustering algorithm [Wilpon and Rabiner, 1985] and the optimization procedure is performed in order to select the most effective set of Gaussian no'des. By performing a modified k-means clustering it is possible to obtain a fair description of the input data items by a limited number of clusters, each one being represented by a centre and a standard deviation vector. This parametric representation of the clusters can be used to initialize the hidden layer. The clustering can either be performed globally or per class. In the latter case [Weymaere and Martens, 1991], clusters are created for each class separately. During the k-means clustering the ceiitr' and standard deviation components are obtained ior each class separately and for each number of clusters (1,..., predefined maximum). The cluster members tend to converge to that part of the input space that is covered by the examples of that class. Then the optimization procedure is carried out to select the optimal number of clusters for each class. The selected clusters are used to initialize the hidden layer in an almost optimal way. We wondered whether it would also be possible to initialize the Gaussian nodes from the clusters obtained by a Kohonen map. A problem could be that the map was trained using all examples of the BPC task, and consequently that the map vector distribution was dominated by the dominating class (the vowels). In order to perform a clustering per class, we would have to construct five different maps (one for each class). Another problem is that by retaining only a few clusters from the map, only parts of the input space will remain well modelled. This is different in case of k-means clustering where the smaller cluster configurations (less centres) are determined to provide the best coarse representation of the data distribution over the entire input space. Due to the two problems stated above, there was doubt about the sensibility of using the Kohonen map cluster centres for the initialization of the Gaussian nodes. A property attributed to the Kohonen map is that it is not cis much affected by noise and training inconsistencies as the k-means clustering is. Furthermore, the amount of nodes representing the different classes seems to be proportional to the number of examples of these classes in the training database. The map vectors tend to have the same distributions as the training database samples which is not the case for the clusters obtained by the k-means clustering algorithm. The k-means clustering procedure (or the Kohonen map training) starts by selecting a small subset of the full training database (e.g. 50 times the number of clusters that are to be created). Clusters can be created globally or per class. In the former case an evaluation set is constructed which reflects the same a priori class probabilities as the full training database. In the latter case subsets of the different class sets are created. These sets (in case of global clustering there is 16 only one) are used to determine the centres and standard' deviations of the candidate Gaussian units to be derived from the clusters. The computation of the standard deviations assigned to the map vectors is performed as follows: 1. Compute exact cluster centres. In fact, the Koho-nen map vectors divide the input space into clusters (see equation 1), but a map vector is not necessarily the centre of gravity of the cluster members. 2. Compute the standard deviations of the projections of the cluster members on the main éixes. 3. Multiply all computed standard deviations by the same factor, which is determined in such a way that about 80% of the cluster members were located inside Gaussian output ellipsoid corresponding to a 0.5 output. Once the cluster centres and the standard deviations are known, the optimization procedure [Weymaere and Martens, 1991] can be carried out. The optimization process is performed in Up parallel paths. The parameter rip is fixed in the beginning of the optimization procedure. 3.1 Results on the BPC Task In order to evaluate the results obtained by initiahzing the network's hidden layer starting from a Kohonen map, the recognition rates of the obtained networks were compared to those of the corresponding networks which were initialized starting from the k-means clustering algorithm. Two comparisons were made: global clustering and clustering per class. (The results of the latter clustering method, using k-means clustering are reported in [Weymaere and Martens, 1991]). All the experiments were performed with Up fixed to 3. • The global k-means clustering and the 6x6 Kohonen map training were performed on a database consisting of 1800 samples. The 1800 samples reflected the same class probabilities as the full training database. The recognition rates of the initialized networks (as a function of the number of hidden nodes) are depicted on figure 3. The Kohonen map training took 77 minutes of CPUtime while k-means clustering took 75 minutes. • In case of a clustering per class, 9 clusters per class (a 3 X 3 map in case of Kohonen clustering) were computed. In both cases a set of 500 examples of the same class was used for creating the clusters of that class. The recognition rates of the initialized networks, as a function of the number of hidden units, are shown in figure 4. The training of the Kohonen maps now took about 9 minutes, while A JiÉoiìdl Kohon.?" N'i) 12 18 24 30 Ntmco' of nodes Figure 3: Comparison of the recognition rates of networks using 36 global clusters (created by k-means al-gorithm/Kohonen map) to initialize Gaussian nodes. K-means per Class Ù Koncrwf^ Ma u De» Class > Ä 10 15 20 25 30 Ni^rtoer of un ts Figure 4: Comparison of the recognition rates using 9 clusters per class for k-means clustering and for Kohonen map in order to initialize the Gaussian nodes. the k-means clustering took no more than 2:20 minutes of CPU-time. The Kohonen maps of sizes 12 x 12, 9 x 9 and 7x7 (which were already trained see subsection 1.1) were used to create clusters for the initiahzation of the Gaussian nodes. The parameter rip was fixed to three and the maximum number of nodes was 60. In table 2 the recognition rates obtained by using three Kohonen maps for 30 and 60 hidden units are presented. The general conclusions are: 1. Using k-means clustering or Kohonen map clustering, it is possible to initialize MLPs with a Gaussian hidden layer to a near optimum point in 144 clusters 81 clusters 49 clusters 30 nodes 83,8% 84,1% 83,0% 60 nodes 85,4% 84,4% - Table 2: Recognition rates on a BPC task for different numbers of clusters which initialize Gaussian nodes. the weight space. The performance of the initialized network can be as large as 85,4% which is not far from the optimum performance of 89,20%, obtained with traditional 3-layer MLP trained with EBP. 2. The results obtained by clustering per class are substantially better than those obtained by global clustering (higher recognition rates and considerably less CPU-time). 3. The initial network performances obtained with k-means clustering and Kohonen map training are essentially the same, be it that k-means clustering is computationally more efficient. This superior computational efficiency is mainly devoted to the fact that all inter-sample distances required for k-means clustering can be computed (and stored) in advance. However, this advantage is lost as soon as the cluster datasets become larger. 4 Further training of the net Once the Gaussian nodes are initialized, further training of the net can be carried out using the gradient descent method. The problem is that it is difficult to select proper learning rates and proper smoothing factors (for the adaptation of the output nodes' weights and for the adaptation of the Gaussian nodes' weights). If the choice of these parameters is inadequate, training can easily lead to a sub-optimum. Very few tests were run until now and the obtained results could still be improved. The network with Gaussian units whose weights were obtained by our optimization procedure was tested on the three databases (training database, test seti, test set2). The weights to the output units were obtained according to equation 3. The optimization procedure used bpc^o as the training set. Networks with 20 and 30 Gaussian nodes obtained from a Kohonen map of 9 X 9 were used in this test. The network whose hidden layer consisted of 20 Gaussian nodes was trained for 8 cycles with a batch size of 1500 (this means that weights are adapted after 1500 input examples are presented). The network whose hidden layer consisted of 30 Gaussian nodes was trained for 13 cycles with the same batch size and for 20 additional cycles with a batch size of 3600 and a smaller learning rate. The results are presented in tables 3 and 4. 5 Conclusion Experiments were carried out to investigate the capabilities of self-organizing feature maps (Kohonen maps) in a speech pattern recognition task. The conclusions of these experiments is that a labeled Kohonen before training after training train 82,48% 88,70% testi 80,58% , 86,71% test2 82,17% 86,94% Table 3: Recognition rates on a BPC task, using the network with 30 Gaussian nodes. before training after training train 81,58% 87,27% testi 80,21% 85,28% test2 81,80% 85,50% Table 4: Recognition rates on a BPC task, using the network with 20 Gaussian nodes. map cannot compete with a feed-forward MLP trained on the same amount of labeled training examples. Afterwards, it was investigated how Kohonen maps could be used to initiahze the weights of a 3-layer MLP with a hidden layer of Gaussian units. It was found that initialization to a near optimum point in the weight space is feasible, especially if one starts from a set of small Kohonen maps each derived from examples of a particular output class. It was verified that Kohonen map clustering is a sensible alternative to k-means clustering, a technique which was introduced by Weymaere and Martens (1991) for the initialization of Gaussian networks. The EBP-training of the initialized Gaussian networks lead to essentially the same recognition rates as were obtained with standard MLPs [Depuydt et al., 1990]. However, the initialization algorithm yields three major advantages: 1. The danger of getting trapped into a local minimum is reduced. 2. The required dimension (size) of the network can be determined without the need for EBP-training. 3. The training of the initialized network takes much less CPU-time than the traditional EBP-training of randomly initialized MLPs. 6 Acknowledgement This study was made in Electronics Laboratory, University of Ghent in a periode from 1.2.1991 until 1.7.1991. I would like to thank my mentor Prof. Dr. Ir. Pipan from the University of Ljubljana, Faculty of Electrical Engineering and Computer Science for financial support. I am grateful to Prof. Dr. Ir. Van-wormhoudt for letting me work in his laboratory and enabling me to use all its facilities. Special thanks are due to Dr. Ir. J.P. Martens for putting me on the right track, for correcting this report and for giving many useful advices. Thanks are also due to Ir. N. Wey-maere for advising me on the literature, allowing me to use his programs and explaining me matters that I was not yet familiar with. References [1] Brauer,p. and Knagenhjelm.P. (1989). "Infrastructure in Kolionen Maps", Proc. IEEE ICASSP, Glasgow, May 1989, Vol. 1, pp. 647-650. [2] Depuydt,L., Martens,J.P., Van Immerseel, L. and Weymaere, N. (1990). "Improved Broad Phonetic Classification and Segmentation with a Neural Network and a New Auditory Model", ICSLP, Vol. 2, pp. 1041-1044. [3] Kohonen,T. (1989). "Self-Organisation and Associative Memory", Heiderberg, Springer Verlag, 3'"'' Edition. [4] Kohonen,T. (1990). "The Self-organizing Map", Proc. IEEE, vol. 78, no. 9, Sept. 1990, pp. 1464-1480. [5] Lowe,D. (1989). "Adaptive Radial Basis Function Nonlinearities and the Problem of Generćilization", lEE Conference on Artificial Neural Networks, 16-18 October. [6] Martens,J.P. and Van Immerseel,!. (1990). "An Auditory Model Based on the Analysis of Envelope Patterns", ICASSP90, 402-406. [7] Powell,M.J.D. (1985): "Radial Basis Functions for Multy-variable interpolation: a review", IMA Conference on algorithms for the approjdmation of functions and data, RMCS, Shrivenham. [8] Renalds.S. and Rohwer,R. (1989). "Phoneme Classification Experiments Using Radial Basis Functions", IJCNN Washington. [9] Rumelhart,D., Hinton,G. and Williams,R. (1986). "Parallel distributed processing: exploration in the microstructure of cognition", Vol. 1, MIT Press. [10] Weymaere,N. and Martens,J.P. (1991). "A Fast and Robust Algorithm for Feed-forward Neural Networks" , To appear in Neural Networks. [11] WUpon,J. and Rabiner, L. (1985). "A Modified K-means Clustering Algorithm for Use in Isolated Word Recognition", IEEE Transactions on Acustics, Speech and Signal Processing, Vol. 33, pp. 587-594. FORMAL INFORMATIONAL INFORMATICA 4/91 PRINCIPLES Keywords: circularity, decomposition, composition, construction of formulas, intelligent information, metaphysics, parallelization, particularization, principles of Anton P. Železnikar forinula construction, sequentiality, Volaričeva ulica 8 spontaneity, universalization 61111 Ljubljana This essay shows the formalization possibilities of principles by which informational formulas, that is, informational entities occurring in the happening, eventful circumstances, are constructed in a spontaneous and circular way. In this sense, the formation (forming) of informational formulas becomes phenomenal by itself, not only by the spontaneous and circular use of the discussed principles, but also through the principles-own phenomenality. Formal informational system is an informationally arising system and, in this respect, it differs substantially from the concepts of the so-called well-defined, symbol-static, mathematically axiomatized systems. It could be said that an informational systems is spontaneously and circularly adapting to the situation and attitude (intention) of itself and its environment by the impact of itself and environmental information. In this essay the following principles and their formalization are discussed and illuminated in a critically formative and subsequent way: spontaneity, decomposition (analysis), composition (synthesis), circularity, particularization, universalization, sequentiality (serialness), parallelization, structuring, organization, algorithmic information, straightforward information, informing, counter-informing, embedding, excluding, metaphysics, and intelligent information of formulas and formal systems. These principles are used within the informing of formulas and formal systems themselves, that is, as principles of their informational arising. Formalni infoniiacijski principi. Ta spis prikazuje formalizacijske možnosti principov, s katerimi se konstruirajo spontano in cirkularno informacijske entitete, tako kot se pojavljajo kot dogodja oziroma dogodkovne okoliščine. V tej smeri postane formacija (oblikovalnost) informacijskih formul tudi sama fenotnenalnane le s spontano in cirkularno uporabo obravnavanih principov, temveč tudi zaradi principom lastne fenomenalnosti. Formalni informacijski sistem je informacijsko nastajajoč sistem in v tej svoji značilnosti se bistveno razlikuje od t.i. dobro definiranih, simbolno statičnih, matematično ak-siomatiziranih sistemov. Lahko rečemo, da se informacijski sistem spontano in cirkularno prilagaja situaciji in atitudi (intenci) samega sebe in svojega okolja z vplivom samega sebe in okoliške informacije. V tem spisu se v kritično formativni in zaporedni obliki obravnavajo tile principi in njihova formalizacija: spontanost, dekompozicija (analiza), kompozicija (sinteza), cirkularnost, partikularizacija, univerzaliz.acija, posledičnost (zaporednost), paralelizacija, strukturiranje, organizacija, algoritmična informacija, premočrtna informacija, informiranje, protiinformanje, vmeščanje, izključevanje, metafizika in inteligentna informacija formul in formalnih sistemov. Ti principi se uporabljajo v okviru informiranja formul in formalnih sistemov samih, to je kot principi njihovega informacijskega nastajanja. INTRODUCTION In the essay Principles of Information [POI], several general rules concerning informational phenomenality (phenomenology) are treated, for instance, the spontaneity, circularity, informing, counter-informing, embedding, sequentiality (serialness), parallelism, structuring, organizing, and intelligence of information. In the present approach, our attempt will be to deliver as strict as possible formalization of the discussed principles for the informational formula development within a concise, self-sufficient theory. Already within the algebraic informational theory [IIA], the basic informational principles came to the surface: the arising of formulas was accompanied, for instance, by the so-called operator particularization and universalization; further, some (unconscious) principles of spontaneous and circular decomposition of operands and composition of formulas were applied. However, these principles were not treated in a systematic, conscious, and straightforward manner. The aim of this essay is to present formal principles for the development of an informational theory. The principles of this sort can also constitute the so-called axiomatic basis of a theory for the informational formula development. The basic approach at the formula development will be a spontaneous and circular procedure, which starts by an initial informational marker, that is, a single operand symbol or by a set of markers. The formula development will be a subject of the so-called decomposition and composition principles which embrace some other principles, for instance, those belonging to particularization and universalization, serialization and parallelization, circularity and straight-forwardness, spontaneity and algorithmic approach, embedding and excluding of information, metaphysics and intelligence, etc. Hitherto, no attempt for a systematic and meaning treatise of this sort of spontaneous and circular decomposition and composition of informational formulas within a theory was made. Thus, we are standing in the front of the task to develop adequate principles in a formal, that is, axiomatic, theoretic, and symbolically appropriating way, preparing and designing the way fo a senseful theoretical and technological approach. As always in those siaia-tions, we are confronted with the problem, how to begin this systematic way, how to preserve the reasonableness, adequateness, and openness of formula development, that is, of their spontaneous and circular arising. THE PRINCIPLE OF SPONTANEITY Spontaneity of information is the first principle in the set of basic informational principles. Spontaneity of a formula development concerns the formula decomposition as well as the formula composition. A formula is nothing else than a model, scenario, depiction, or description of a real, mental, or artificial process, phenomenon, situation, or attitude, expressed in the form of informational operands, operators, parentheses, and punctation marks, for instance. It means that in the process of decomposition of a formula as an arising entity its inner components can be identified (brought to the surface or clarity) in a spontaneous way. In the process of composition of a formula as an arising entity its outer counterparts, that is, it concerning entities can be introduced or identified in a spontaneous way. The basic question witliin the phenomenon of informational arising is, who or what is the actor of decomposing and composing spontaneity. Formally, the spontaneous actor of the development of formulas can be, for instance, a theory itself, a natural or artificial system, or a living actor demonstrating the faculty of spontaneous developmental action in such or another way. For instance, to a beginning, marking entity, the spontaneity can chose other marking entities which appear within or outside of the beginning entity and connect them operationally into a more complex formal system. In this system, the beginning entity can become a part or component of the decomposed and/or composed system. We argue that spontaneity of this sort is a regular (legal, permissive) principle of decomposition and composition of informational formulas. Let a be an initial marker, that is, a yet undeveloped formula, i.e., operand marker. The spontaneous development of the simple formula a. can take the following spontaneous informational form: (1) a; a 1= cc; Ti, ... , E;; ß, T.....s\=a In this system of formulas, a. as the first formula represents the initial position. The second formula, a ^ a, shows the beginning of the so-called metaphysical decomposition [IT2] of entity a. The third formula, o; ^ 7], ... , shows the beginning of a composition in which cc impacts entities T), ... , C in an informational way. In the last formula of system (1), ß, y, ... , s j= a, entity a is informationally impacted by entities ß, y, ... , s. The point of system (1) is that formulas in the second, third, and fourth line came into existence in a spontaneous way. This spontaneity can be ascribed to a theory or generative system marked by Z. Thus, formula system (1) can be clarified in the form (2) a; S N (« h a); T, ... where the acting entity Z, by which formulas in the second, third, an fourth line of system (1) are introduced in a spontaneous way, is explicated. The following principles will show how spontaneity can come to its action, how it comes to the surface in cases of applications of other informational principles. THE PRINCIPLE OF DECOMPOSITION The decomposition concerns always an un-revealed (non-disclosed) entity cc which is, simultaneously, the most simple, basic formula a, representing a potentially complex, compound, or composed entity. In formula a, entity a acts (behaves, informs) as a unit which indicates yet unidentified or at some other place identified (determined, revealed, composed) entity (for instance, an expression of meaning, contents, understanding). In this way, a single a as expression is a sign, indicator (in German, das Anzeichen, in French, indice) which can be circularly decomposed, as it will be shown. The basic presumption is that oc, in the process of its decomposition, is merely an initial formula of the form a\=a, that is, (3) a=^(a[=a) where is the operator of informational implication and 1=: is the most general operator of informing (of a). We call a a the metaphysics of a, indicating the a-inner informational process; thus, this sort of decomposition is a metaphysical one and must remain in the framework of a |= a. If ß is a part of a, that is, ß C a, then a [= a can be decomposed into (4) (ahß)|=a where the circularity (cyclicity) of a, that is, a (= a, is preserved. The metaphysical cycle a a can be decomposed (de-constructed, revealed, analyzed, differentiated) to an arbitrary extent, depth, intention and also in the form of distinct cycles, for instance, (5) (ahß)>«; ((a ^ ß) Y) N a; (a ß, y) a etc., ad infinirnm. The basic rule of decomposition is the following: entity a 1= a can be decomposed serially (sequentially) and in a parallel way preserving the basic form a [= a in any recursively decomposed form (a ^ ß) [= ... a. This kind of decomposition can occur also in a parallel form, can have parallel pathways (formulas in parallel) of the form «[=... a. If formula (a ß) )= cc was one of the general decomposition principles, the other decomposi- tion principle is (6) whicli preserves the cyclic nature in regard to a. This duality leads to the presumption (7) (ß C a) (((a ß) ^ a; (a (ß h a))) Further, one can have (8) ((rCß); (ßCa))=> ■ ((((a ^ ß) ^ y) ^ a); (a 1= ((ß (= y) «))) etc., in a recursive and mixed recursive way. Decomposition of a }= a in one or another way means the spreading of formula a a in its serial and parallel components and the mutual connection of components and the topic entity a. Through decomposition, formula a a can blow up in an analytical and synthetical way, within itself as a serial and parallel circular system of formulas of different kinds. To these components, also outer components, not belonging to a, can be considered, for they can influence a, that is, its structure and organization. For instance, if ß does not belong to (is not a part oi) a, that is, ß(Za, entity ß can influence the metaphysics of a in the form (9) Formula (9) is the typical position, where entity ß is observed by metaphysics a ^ a, that is by a. We see how informational phenomena can impact the arising of the initial formula a j= a. By decomposition (spreading, de-construction, delivering, distribution, dissemination), new informational entities can be introduced into the context of the metaphysical formation a |= a. The process of metaphysical decomposition is spontaneous and remains in the realm of entity a. The complexity of decomposition (spreading) of a oc depends solely on the degree and depth of distinguishing and differentiation of new components within a and their connectedness. As mentioned before, decomposition can be the subject of a theory Z, of an outward observer w, or of a technical tool x (which possess an adequate technical understanding). In this way, S [= (a )= a) or co )= (a [= a) or T (a cc) are sense fui formulas which explicate the action of decomposition of a 1= a by Z, CO, or T, respectively. We recognize how a [= a as a theoretic, observational, or technological object is in no way only a tautological affair; it is the essential starting point at its acmal and always potentially possible development. THE PRINCIPLE OF COMPOSITION The composition of formulas concerns different informational operands (entities) and their interweavement, that is, their operational connectedness. A composition of operand and operator components in the form of a system of formulas constitutes a new entity. While decomposition (spreading) is in fact merely a more detailed identification (clarification) of an already existing system, composition is the emerging of a new system, defined as informational composition of already composed entities. In fact, the composition and decomposition of formulas can act in a mutually senseful, spontaneous and circular way. For instance, the metaphysical form a oc of entity a is an open self-informing (impacting, observing) system which can be decomposed (particularized) in an arbitrary (intentional, com-prehensional, unpredictable, phenomenal) detail. If ot informs openly, that is, a. [=:, and if ß is informed openly, that is, ß, then ß can become the observer of a. In this situation, one can set a = ß. Now, formula a |= ß can be decomposed in greater detail considering the components of a, ß and a 1= ß, and connecting them within the system a \= ß. We recognize, how decomposition and composition of components become interweaved procedures, proceeding from a hiddenly composed entity into greater detail by decomposition and composing a system in which detailed parts of a problem are coming to the formal surface. If a and ß are separated entities, that is, a (ß^a); (a, ß) ^ (a ^ ß; ß ^ a) etc. The principles of decomposition and composition of formulas can be grasped also in a pure grammatical sense, for instance, in the form of a system including the following rules: (0°) Symbol a (e.g., a, ß.....co) marks an operand; symbol \= marks the most general type of operator; symbols '(' and ')' are parentheses. (1°) a, a t=, a, and a |= a are formulas. (2°) Each formula can be used as an operand (recursiveness of formulas). By rules (0°), (1°), and (2°) any formula can be decomposed and/or composed, starting by the symbol a. Let us have the following developmental steps, for example: (11) a; «N; «Nß; («Nß); («Nß) (N; (a^ß) (^T; ((a[:3ß) (1= T); ^((a[=:ß) ([= T); T|=((a^ß) (h T) etc. A parallel case could be the following: (12) a; ß; «NNß; «NßirNß; (a[zzß);(TNß); (o!Nß)N(TNß);5N(TNß) etc. The parallel has the meaning of introduction of parallel (newly appearing) formulas within a formula system. THE PRINCIPLE OF CIRCULARITY Circular schemes (scenarios, models, phenomena, processes, situations, attimdes) in the form of formulas can appear in various ways. By definition, an informational entity a itself is a circular phenomenon. The basic form of this circular phenomenality we call the metaphysics of a and denote it symbolically by a )= a. In a formula, the circularity of an entity a is expressed by the repeatedly appearing operand a in this formula. Formula cc ^ a, which marks the a's metaphysics, can be decomposed only by the extension of operator |= in such a way that at the beginning and at the end of the decomposed (extended) formula there is operand a, for instance, (a [= ß) )= a or a 1= (ß 1= a). In the first case, process a |= ß informs a; in the second case, entity a. informs process ß \= a; in both cases entity a is involved circularly, but differently. A different form of circularity is the parallel one. Parallel circular schemes are, for instance, (13) al=ß;ßha; (14) a[=ß;ß^T;TNa etc. Formula (13) shows the parallel circularity of the first degree, formula (14) of the second degree, etc. The so-called metaphysical circularity is the serial one, and is, accordingly to the extent of decomposition, of a higher degree (of greatest possible detail). Circularity of an operand a means its recursive appearance in formulas in a serial or parallel way. The serial and parallel type of circularity occurs at the design of formulas in a nauiral (spontaneous) way. For instance, the metaphysical circularity of a, that is, a [= a, can be expressed (expanded, broadened) by its informing counter-informing (S, and embedding ® of information a, counter-information y, and embedding information s, respectively. Various kinds of schemes representing this metaphysical phenomenality of a. can be appropriated. The most common (universal) one could be, for instance. However, several other metaphysical schemes can emerge during the process of decomposition, the serial as well as parallel ones. Anotlier, not necessarily metaphysical type of circularity of a. concerns the so-called understanding ai, which can appear as an intelligent component of informing ^ within a. Usually, understanding 21 produces (informs) a meaning (i^ of the understood situation inside of a and outside of a by a. Thus, a basic scheme of the understanding formula is (16) where ^ can concern a as well as an outside entity ß or both of them. Of course, parallel metaphysical as well as understanding schemes of formulas can be constructed accordingly to the needs, concepts, and scenarios of the imagined reality. The process of the circular deconiposition and composition of formulas is always a recursive one for some existing and arising operands and, in any case, parallel (new, additional) formulas for describing circular and non-circular (straightforward) phenomena can be introduced. Particularization is always a top-down construction of k formula (system), that is, from the beginning-general to the particular. Particularization can also add formulas, operands, and operators to existing systems of formulas with the aim to concretize, analyze, explain, and complete the expression of concepts, scenarios, positions, attitudes, etc. In such procedure of formula development, other principles of informational development can be used (spontaneity, circularity, sequentiality, parallelism, etc.). The most simple act of particularization is the replacement of a general operator by the particularized one which, in an adequate manner, explicates the namre of informational impact between the concerned operands. In general, (17) (ahß) («Npanß) is a scheme of operator particularization. For instance, a theory, several concerned entities by themselves, or an outer observer can be imagined to be the actors of a particularization process. THE PRINCIPLE OF UNIVERSALIZATION THE PRINCIPLE OF PARTICULARIZATION Particularization of formulas is a procedure which proceeds from a general concept into more concrete detail of given phenomena in a decomposing way. Thus, in general, universal formulas are extended into corresponding particular forms. Particularization can be performed simply on the operator level when a general operator in a formula is replaced by an adequate particularized operator. Particularization concerns decomposition as well as composition of formulas (Üieir sequentiality and parallelization) into more accurate detail in the sense of a descent to a sufficiently adequate con-creteness. The terminal situation of a particularization is achieved through a stepwise procedure, descending in the imagined detail of a problem. While particularization concerns a top-down strategy of formula fitting concerning the problem, universalization is a bottom-up search from already concretized situations to the generalized ones. Universalization does not mean a simple replacement of a concrete formula by the general one; it is an introduction of new formulas which express general relations between operands and can be, afterwards, particularized again. Universalization introduces universal processes of informing into the context of a formula development. It performs as a bottom-up construction of formula system being on the way from the concrete to more general. Particular cases can always signalize universal possibilities of their phenomenality. On the operator level, the universalizing principle can be the implication («Nß) In this situation, the particular case a ß is in no way neglected; it does not vanish necessarily from the observed system of formulas. But, the introduced general formula a [= ß can now be decomposed in a new, different way in the form of a parallel phenomenon. Universalization can be understood as a spontaneous principle in the domain of a theory an observer co, or a technical tool T. In the universalization formulas, the general operator of implication can be particularized, for instance, (19) Npa, ß) ^ (^Npanß) ("Npartß) >2 («Nß); ^ (« N ß) yielding general schemes of the so-called operator universalization. THE PRINCIPLE OF SEQUENTIALITY (SERIALIZATION) Sequentiality concerns a serial development (composition, decomposition, circularity, par-ticularization, universalization, etc.) of formulas under consideration. Circular sequentiality leads to the recursiveness of the occurring of operands. For instance, metaphysics, memory, self-con-stmctive informational systems, preservation of a situation (a thing, body) or attitude (mind, consciousness), etc. can be recognized as sequential and, simultaneously, circular phenomena. The sequentiality of a phenomenon can be expressed also in a parallel circular way. Thus sequentiality in regard to the form of a formula or a formula system is twofold: serial (expansion of a formula by insertion of operands and operators) and parallel (expansion of a formula systems by formulas which within the left sides of operators \= have operands already occurring in the existing formulas). The development of a serial sequentiality in the formula a ß can be shown in a stepwise manner by the following example: (20) a^ß; (aNß)NT; (ah(ßh5))hT; (s [.z (a h (ß ò))) h T etc. A twofold circular expansion of the last formula in system (20) would be the case (21) ((s^((a^(ßh5))he))NT)Na where the sequential circular expansion concerns a as well as s which recursively appear in formula (21). While entity s seems to form a proper sub-. cycle of formula (21), entity a is a cycle which improperly enters into the s-cycle, performing an interweavement of cc-cycle and s-cycle. Sequentiality can concern the sequential depth strucmre of a formula, descending not only into a greater detail of a formula through serial analysis and structuring, but also interweaving sequential structures among themselves in any imagined way. At such structuring of a formula also some parallel cases of formulas can emerge, being the consequence of the depth analysis of an original formula. New, additional formulas can expose the faculty of the so-called parallel sequentiality which, in the most primitive case, can have the following form: (22) etc. Parallel sequentiality can become circular, if to formula system (22), formula (23) 5 a or any similar formula concerning the occurring operands in (22) is added. The principle of sequentiality belongs to the most primitive approaches of the serial formula development, which considers the understanding of a formula and positions and attitudes of its operands. In short, this procedure of development can be called also the formula serialization. THE PRINCIPLE OF PARALLELIZATION system can be the following: Parallelization means introduction of parallel formulas by decomposition and composition of a formula; at this occasion parallel formulas emerge as a consequence of the depth analysis, synthesis, and splitting of a formula situation. The emerged formulas broaden a formula system and connect the arisen operand entities in a parallel or some other way. Through parallelization, a formula system becomes not only more complex, but also additionally interweaved, where interweavement concerns the arisen and the existing operand entities. The principle of parallelization embraces the parallel composition and decomposition in a spontaneous, circular, particular, universal, and other ways. Parallelization means the growing in number and extent of informational components (operands and operators) and their interweavement through splitting the operand situations and attitudes. Parallel decomposition of a process, phenomenon, scenario, etc. is a splitting of the imagined (understood, comprehended, appearing) process, phenomenon, scenario entirety into parallel, interconnected entities. As an example, the following developmental steps within a parallel decomposition can occur: (24) a; (ß, T C a) (a ^ ß. T); a a; (a ß, y); (5, s(Zo!); (6, s[=a); ßNSirNs etc. The first formula a is the initial situation. By the second formula, entities ß and y within entity a are observed. This fact implies that components ß and y are informed by a. The third formula opens the possibility of metaphysical decomposition of a by a 1= a and explicates formula (a ß- T) which was implied by the second formula. The fourth formula observes that entities 5 and s are not the constituents of a, however, they impact a as the outer components. The fifth formula introduces the informing of 5 by ß and s by y, etc. A sequential (serial) consequence of the last parallel (25) ((5,sh«)Nß>T)N5.s etc. If, consequently, entities 5 and s become parts (constitoents) of a's metaphysics a [= cc, system (25) closes into (26) (((5, £ h a) N ß. T) 5, £) [= a although in system (24), initially, 5, s (Z a was assumed. Parallelization of formal systems can offer new interweavement of entities which can be in contradiction with the initial situation. A parallel decomposition brings to the surface new informational attitudes which may neglect or annul the initial conditions or force the observer to resolve the emerged contradictory situations, i.e., to change the observational conditions. Parallelization, as an introduction of parallelism of formul? belongs to the most intelligible natural and arti t. cial phenomena. THE PRINCIPLE OF STRUCTURING Strucmring a system of formulas means to apply the principles of decomposition and composition, particularization and universalization, sequentiality and parallelization in a spontaneous and circular way. Structuring of a formula system can use, mix, and connect the discussed principles and those which follow. It can be said that the structuring as an active entity structures the already strucmred system to some extent, gains the arising of structure. Structuring is an informational component in the realm of information, where the principles of information [POI] are closed under information, that is, underiie the logic of informational arising. Structuring means to restructure and tc staic-ture anew a structured informational system. Structuring acts like an informational component with characteristic informing, that is processing of structuring information which leads to a new struc-mre. Structuring is a composed and complex use of singular principles of information. Structuring can get its concrete sense as a particular, that is, informationally determined form or process of shaping, arising, emerging of an informational system in a structural way. For instance, structuring S as a structuring activity and potentiality belongs to the structure entity a which informs 6 how to structure a primitive or system entity a in question. Thus, primordially, (27) (a^6)[=a;a|=a where a observes a, that is, its structure a^ and where a^ serves as the reference for strucuiring a. Thus, one can imagine, (28) (a^a)[=a^; S (= a or, in a cychc form, (29) ((((a ^ a) h a^) ^ 6) a) ^ a The last scheme represents two perplexed cycles concerning the entity to be structured, that is, a, as well as the structuring entity a. This scenario performs as long as the structure entity a is not satisfied with the structure a. In this function, (X entity a can use a reference or dynamic understanding of cr^ for the decision making how to structure a and since when to stop the structuring of a. A concrete process of structuring can be particularized to any necessary extent (detail), thus, specifying the process of structuring of the entity in question. THE PRINCIPLE OF ORGANIZATION A strict distinction between structure and organization remains vague. In some way, however, It is possible to differentiate the phenomena of structuring and, as a consequence of a structure, the arising of organizational relations, for instance, the interweavement of structural informational entities, by which the nature of connectedness, impact, dependence, con-ditionality, etc. comes into existence. Organization means a supplement in the understanding of structure of a formula system. Informationally, structuring causes the so-called organizational relations which are nothing else than the additional, to the structure occurring informational processes. Thus, the arising organization seems to be a consequence of the structure introduced by an informational entity. What could the organization of a formula system, which is a structure of operands, operators and formulas, mean at all? How could the clear difference between the structure and organization of a formula system be observed? The structure of a formula system could be grasped as a visible arrangement, disposition, and appearance of operands, operators, and their formulas. Of course, the structure of a formula hides also the meaning of structuring and the comprehension of occurring formula components. The structure of a formula is a consequence of structuring (grammatical, syntactic) rules, which govern the composition of formula constituents (operands and operators). The organization of a formula concerns its depth structure which is not only grammatical. Organization is related to the interweavement of meaning and understanding of occurring operands and operators, their parallel and circular connectedness and to the impact of occurring organizational forms with processes of decomposition and composition, that is, with the arising of informational formulas. In a semiotic way, organization is an arrangement of operands and operators in a semantic and pragmatic manner, is also a semantic and pragmatic (spontaneous) disposition of operands and operators in a formula. The observing organizational view can cause the arising of new formulas within a formula system. For instance, explaining a system of formulas through the addition of formulas represents an organizational decomposition of the system. Organizing seems to be a particular view of structuring and vice versa. Both, structuring and organizing, are compositional as well as decomposing principles which can enrich, broaden, advance, and complete a system of formulas under investigation. The first look at a formula system can be merely structural; afterwards, through study, analysis, and development of the system, the first look becomes more and more organizational. If strucmre is a sort of system identification, organization is the understanding of the strucmral meaning. This is the well-known cycle, which comes into existence between the strucmral meaning and organizational understanding. This cycle gains the development of strucmre and organization of a formula system in a structuring and organizing way. Let us imagine the following strucmre (a) and organization (o) development system Ö for a formula system 9: (30) (Q 9))) [= 0 Formula (30) describes a circular development system (0) with two significant development sub-processes, which are structuring (6 |= cp) and organizing (Ö 9) of the formula system cp. However, the development of a formula system tp can be expressed also in a traditional parallel form, for instance, as (31) a(cp) ^ 6; 6 1= cp; (a((p), (p ^ 0(9)) ^ D; D ^ (6, where 0(9) and 0(9) are the intentional structure and organization of formula system 9 and, S and Q the stmcturing and organizing mode of the development system Ö, respectively. This development system seems to be 9-circular and the improvement (learning, adaptation) of Ö is governed by structuring S and organizing D, however, still remaining within the cycle of development of 9. THE PRINCIPLE OF ALGORITHMIC INFORMATION Algorithmic information is a well-determined, self-sufficient entity which can be repeatedly applied (understood, used) as a clear, data-stable, definitive recipe (procedure, process) for solving a certain type of problem. Particular algorithmic information is, for instance: mathematical algorithms for various purposes (solving of equations, calculating values, deducing and proving of theorems, developing theories, searching for axioms and principles, etc.); computer programs expressed in different programming languages (well-structured application programs, expert systems, artificially intelligent tools, etc.); and theories of sciences, in general, which have to deliver reliable and repeatable results and predictions. The principle of algorithmic, that is, v/ell-defined, disciplinarily structured, or scientifically doctrinaire information pervades the entire realm of mathematics, computer science, and sciences in general. Furthermore, a certain piece of algorithmic information guaranties that the process it describes can be effectively transferred to a technical tool (automatic equipment, robot, computer, etc.). The contents and strucmre of an algorithmic information can be always applied, understood, or learned by a materially realized technical tool or a mental system. Algorithmic information belongs to the so-called realm of data. In contrast to information, data informs in an identical (repeatedly, definitively regular) way and depends only on data, that is, on well-defined arguments. Algorithmic information is not informational yet in the sense of informational arising. Algorithmic information performs as a functional or procedural determined data strucmre for handling data. But, data 5 as a function or argument [IT2] is nothing else than (32) which initial metaphysical form is 5 = 5. Algorithmic information performs as a tool for solving a kind of problem irrespective of the values of arguments which inform (impact) algorithmic in- formation (procedure, program) in differently occurring situations. THE PRINCIPLE OF STRAIGHTFORWARD INFORMATION The main characteristics of a straightforward information is that it is not expUcitly circular. For instance, formula a ^ ß is straightforward while a j= a is not. Irrespective of the extent of decomposition, a metaphysical information as a whole cannot be straightforward. Implicitly, the circularity of straightforward information occurs. For instance, within a ß, informational entity a as well as ß are circular. Also, the parallel circularity of the system a ß; ß j= a does not violate the principle of straightforwardness. Thus, consequently structured parallel systems can keep the principle of straightforwardness. This principle excludes any explicitly circular scheme (formula, scenario). To achieve the state of straightforwardness of a formula system, circular formulas can be decomposed in an adequately parallel way. However, üiis could mean to reduce a natural scenario into an artificial model. In most cases, both principles of circularity and straightforwardness will be used at üie decomposition and composition of formulas together with other principles. The straightforwardness means the hiding, concealment, and placing out of sight the circularity of operands. This happens in a natural way at speaking, writing, and thinking in any language. It may happen that clearly parallel cases of an implicitly circular structure are interrupted. The best examples of this sort are the so-called concepts of words in a dictionary. A word is rarely defined (conceptualized) by itself. However, in a semantic net of words, circularity (tautology in a transitive sense) always exists. Thus, the principle of the so-called straightforward information is, in fact, the vagueness (hiding) of the circular nature of informational entities in question. The sciences are inclined to the straighforward-ness because it enables the abstraction by simplification and reduction, or a satisfactory ex- planation of otherwise circularly (recursively) perplexed phenomena. The principle of straightforward information concerns a unidirectional, shortened, and decisively unambiguous way to the solution of a problem. THE PRINCIPLE OF INFORMING Informing of things is the most basic principle in üie realm of information. It says that an informational entity a informs and is informed and Üius implies üie system (33) «NN« This system determines entity a in its actual and potential entirety [IT2], irrespective of its material, mental or, in general, phenomenal nature. Informing of entity a, that is, ^^ or simply can be observed explicitly; it is implicitly present in operator (=, that is, in formula a as well as formula a. Thus, entity a can be decomposed in regard to its informing The following straightforward implication seems to be reasonable: (34) It says that informing ^ is a constituent of a, however, a and ^ inform each other and are informed by each other. Another form of informing ^ within a can be conceptualized circularly, for instance, as (35) This circular scheme presumes that informing is a subordinated (subjected) component of a and, certainly, that ^ informs cc circularly. Thus, the following implication in regard to the initial situation described by (35) seems to be reasonable: (36) ((a h S) N «) ^ (S C a; a C ((SN a) NS)); ((SNa)NS)C((aNS)N«) Here, the cycle of informing (C^ a) (= is subordinated to the main (origin) cycle ((a \= 1= a). Both, entity a and its informing are parts of each other within the eventfuhiess (happening of informing) of a. That a and are parts of each other means that they mutually and perplexedly exchange the roles of subject and object: if in one of the events of a, a impacts then in another event, ^ impacts a, or they may impact each other even simultaneously, that is, in the way of a proper (simultaneous) interaction. It is to say that informing of a is not or camiot be exhausted in a decomposing way. Entity cc and its informing can hide various forms of entities and to them belonging informing. The most general components are, for instance, counter-informing of counter-information and embedding of information by the so-called embedding information. These cases will be treated separately in the next two sections and together with informing as the whole, in the framework of metaphysics of an informational entity. THE PRINCIPLE OF COUNTER-INFORMING The principle of counter-informing is an attempt to grasp the arising or coming of information into existence through an explicit (revealed, disclosed) happening of an informational event. Within informing ^ of entity a, counter-informing (£ is the recognizable entity within % which is directly concerned with the arising of information, called counter-information y. Counter-informing S is nothing else than informing of counter-information y, of course, within the entity a and its informing respectively. While it has just arisen or it is still arising, counter-information y as a distinctive entity within a which is not informationally connected (embedded in respect) to entity a yet. It performs as an isolated entity within a as long as it is not embedded (informationally connected) by virtue of the so-called embedding information e. The similar holds for counter-informing (£ within informing So far, counter-informing S is an isolated part of informing of entity a. We see that to be a part of something, but to be not connected to something, means simply to be not embedded in something. This is the characteristics of an informationally isolated part of something. It means that an entity can produce a subentity within itself which does not impact the entity itself yet. The arisen, isolated part of an entity has to be connected to or embedded into the entity to contribute to the arising of the entity as an integrated, whole thing of its parts. We have to introduce a particular operator for the so-called not connected informing, for instance, (Z^pjj. Thus, at the arising of counter-informing S within informing ^ and at the arising of counter-information y within entity a, we have the following situation: (37) a 1= y; y C a; y a; (SN«)NS The isolated counter-informing S performs in regard to as a strange (unconscious), to ^ yet unobserved entity, which produces the unobserved counter-information y. It means that in the first step of counter-informational arising there is no observing in the form (38) or, explicitly, (39) SMSÌTN« Operator ^ explicates the non-informing or non-observing situation. The observing in the sense of formula (38) occurs after the so-called embedding of counter-informing (£ into informing ^ and counter-information y into entity a in question. After the process of embedding, both counter-informing ^ and counter-information y lose the status to be counter-informational entities. They become regular informing and regular information, respectively. Counter-information must be understood as the possible increase of an informational entity when the process of embedding of counter-informational components into the original informational entity is taking place. Counter-information y is that informational entity which arises out and within of the informational entity a by virme of its open informing that is, as a parallel open system (40) a ^ ((a ^ ^ (a [z. [zz a) N (S N «)) The adequate circular, parallel, and open system would be, for instance, (41) az^(((at=S)t=a)N;N((«NS)Na); The counter-informing as the phenomenon of informational arising can take place within system (40) or (41). as the origin question concerning the embedding of information? The concept of embedding proceeds from formula (= a in the sense (42) a, ß, T, ...Na This formula illustrates a (partial) process by which entities a, ß, y. ••• are in the process of embedding, where entity a observes them and can be impacted by their informing. The potentiality of embedding can be expressed, for instance, by formula (43) a, ß, T, or by implication (44) (a,ß, T, (^ (a, ß, T. ••• N«)) Embedding of information means the modus of information for itself (in contrary to information for others). THE PRINCIPLE OF EMBEDDING THE PRINCIPLE OF EXCLUDING The embedding of information can be understood as the act of reception, observation and/or, finally, the perception of information by an entity. The process of embedding is an accumulative and integrative process in informational sense regarding the entity in question. It is the basic principle of appropriation of information by information. By embedding, the outside or inside unconnected information comes into consideration by the entity which embeds. The embedding itself proceeds from the basic informational assumption a (^ a). The question is: which information comes from others and the entity itself as that which has to be embedded? In other words, what are the other things and the thing itself for the thing itself? Or, how to the geiieral question What is a thing for other things? the antisymmetric (inverse) question What are things for the thing in question ? can be considered How can informational entity ß be or how can it stay excluded in regard to an entity a? Entity ß is excluded in regard to a if it does not inform a in any way. Thus the exclusion principle could be symbolized by (45) ß M a ■ Operator is a symbol for a certain non-informing. However, how does ß not inform ol? could be another question. In fact, an explicit form of non-informing between entities can be understood already as a particular case of informing between entities. Immediately we speak out a case of non-informing, we have to do with a particular form of informing. The proper case of the exclusion of information could be the vanishing, disappearing, forgetting and, certainly, non-observing of certain information. THE PRINCIPLE OF METAPHYSICS In regard to the entity as entity, the metaphysical as a thing has die meaning of to be entirely concerned with the entity itself, that is, with die thing within the thing itself, however, still in an open, environmentally impacted manner. For instance, an observing thing as observer always produces its metaphysical information, üiat is, it observes the observed thing by its metaphysics or metaphysical components. To understand the principle of metaphysics |a, one has to observe several metaphysical phenomena. If a is one of the metaphysical components within entity ß, we use the symbolic notation a. C^ ß. Then die following can be observed: knowledge C^ belief; belief C^ truth; truth C^ logic; logic C^ language; language C^ mind; mind central_nervous_system etc. We see how metaphysical components are (hierarchically) nested (already partly embedded) in each other. For instance, belief roots partly in knowledge (is informed by it); truth is a consequence of belief and knowledge. The conscious of truth impacts the arising of logic. Language is the eventfulness for knowledge as well as belief and truth. Mind is the home of language, where language (for instance, speech acts, writing) creates mind. The central nervous system arises under the impact of the mentioned metaphysical components. All of these components are circular and spontaneous, structured and organized, autonomous and interactive. However, not only mental phenomena (knowledge, belief, truüi, logic, language, mind, central nervous system, etc.) are understood to be metaphysical. Regardless of its nature, every Üiing has its metaphysics, that is, the inner phenomenality (processing, form) of thing [IT2]. From the point of view of language, the human logic is always metaphysical. The mind as the entire mental phenomenality is metaphysical too from the point of view of the central nervous system'. For instance, the consciousness of man can never surpass the mind in a non-metaphysical way. Thus, for man, there is not possible to think outside of a his/her metaphysical (mind-concerning, neuronal, autopoietic) background. Metaphysics is the beginning and the end of each informational (philosophic, rational, irrational, scientific, etc.) phenomenality. It can develop, arise, reach any metaphysical point, concern, achievement, development as an open, environmentally impacted system, but cannot surpass its instant potentiality and acmality in the framework of its instantaneous openness and (informational) arising. Metaphysics is one of die four specific modes of informing of things. It is senseful to list these modes to keep the insight into die problem of informing and die context of informing in which metaphysics can be distinguished among other phenomena concerning the informing of things in general. In the case of entity a, we clearly distinguish: (46) a |=; [= cc as entity a itself; 0£ 1= as entity a. for others; t= a as entity a for itself; and a 1= a as entity a in itself. As we see, the essential attributes of these distinctions are: itself, for others, for itself, and in itself All four modes of informing are open: (47) ((a^;[=a)h;t=(ah;t=a)); ((at=)h;[=(at=)); Hoc a) (zr (a a)) Now, these modes of informing of endty a can be applied to metaphysics a [= a as an informing entity. Thus, it is possible to distinguish the following: (48) ((oc [= a) 1= ; ^ (a [= a)) as metaphysics itself; (a [= a) t= as metaphysics for others; ^ (a ^ a) as metaphysics for itself; and ((a a) ^ (a 1= a)) as metaphysics in itself These formulas can have sense in the framework of the metaphysical decomposition. Proceeding from a a as a metaphysical situation of a means first of all that a informs a and that formula oc o; is not only an ontological expression in the sense a is oc, but also oc is not a. Why the second, negative statement is senseful? Because a [= oc means that a. changes itself through its informing and that a comparison of a state of a by its subsequent state never gives a statement of the type oc is equal oc, that is a = o;. This comment explains the reasonableness of introducing the metaphysical, in fact, ontological formula a cc. The metaphysical is always concerned with the auto-cyclicity in an open way. The so-called metaphysical components, that is, components of a metaphysical entity a, have the metaphysical structure in itself. For instance, (49) (ßC^c<)^((ß|=ß)C(a^ß)) or also (50) (ßC^a) ((a[=(ßt=ß))t=a) If y is an outer component which impacts a, then, in general, it can also impact the components of a. In this case, formula (50) becomes (51) (rNa;ßC^a)^((T,af=(ßNß))N«) In the last formula, entity y, which impacts oc, is a distinguished outer component, which is not impacted by a. It means that a, together with its component ß, as the metaphysical observer of y, does not impact y so far. In every case of observation, a thing oc can observe its environment and/or the thing itself only in a metaphysical way, that is, through (the decomposition of) oc [= cc. THE PRINCIPLE OF INTELLIGENT INFORMATION Intelligent information, marked by i, belongs to metaphysical information. It appears as as a part of a thing's metaphysics, that is, as the so-called intelligence of things (beings, minds, programs) which can understand things and can be understood by intelligent things. Thus, things appear to an intelligent information as to be intelligible, that is, apprehensible by the observing thing. Intelligent information performs in an observing and self-observing way. Concerning its arising, emerging, coming into existence, and unforeseeableness, it is thrown into counter-informational situations where it tries to solve some environmentally and by itself impacted problems, searching for an intelligent meaning and understanding of a solution. As any proper information, intelligent information is an unforeseeable phenomenon in the sense to delivering solutions, which can be recognized as intelligent by itself and other intelligent observers. At this point, intelligent information encounters the domain of the so-called communal intelligence, that is, by a certain community governed intelligent information. Intelligent information possesses its own intelligent counter-informing which is the component for unforeseeable production of new information. When observed, intelligent information can be carefully decomposed (analyzed, specifically composed, particularized, etc.), proceeding from its initial metaphysical situation t, ^ (,. Within the phenomenon of intelligent information several other components can be observed which contribute to its further identification (decomposition, de-construction). What does intelligent information produce, how does it arise? Intelligent information arises in connection with the occurring, appearing unpredictable situations when it is thrown into the happening and eventfulness of its environment and itself Besides classical metaphysical components which are intelligent informing , intelligent counter-informing S, and intelligent embedding It , producing (informing) intelligent information I, intelligent counter-information y and intel- L ligent embedding information s^^, respectively, several other forms of intelligent information can be considered. Let us try to show a classification of intelligent information on the global level, where understanding and the informed meaning are coming into the foreground. Intelligent information I as metaphysical information is decomposed through its initial situation !,[=(,. Intelligent information has to include a sort of understanding U (roughly, intelligence) which substantially impacts the arising of i. Intelligent information is always an understanding information, that is, (52) UC l; (i ^U)^ L The next question is, how does understanding U impact intelligent information l? What does U produce? Understanding U as the producer of intelligent information t produces the so-called intelligent meaning for intelligent information i Ij in a metaphysical way. That means Certainly, when arisen, meaning ^ performs as metaphysical information (i |= (i impacting understanding U, yielding (57) Thus, in a further way expanded form of for-(56) could be, for instance, (58) ((i h (((U N N N ((^i, N N M,)) In this sense, intelligent information approaches to the attitude to be more and more cycled, where informational cycles can overlap in a parallel way too. Scenarios corresponding to concrete cases can be constructed by means of the demonstrated informational language. CONCLUSION (53) Commonly, meaning (a^ belongs to the category of informational (e.g. linguistic) concepts which as products of an understanding do not belong to understanding information, that is, C i-. However, in a general scenario of understanding U within intelligent information i, there is (54) In a different simation, formula (55) or even formula (56) (a^((Ut=n^)t=ll))^t. can be appropriate. The last formula shows the direct nesting of cycle (U (a^^) |= U within cycle I, [= I. Several other combinations of cycles concerning intelligent entities (,, U, and are possible. Information as a phenomenon appears as nothing else than the connection (interaction, influence) between things performing as informational entities. Formalization of the connection (impact, phenomenality) from one thing to another thing is an informational phenomenon by itself and performs as regular information. Formulas and systems of formulas are informational entities of the observer who observes things and their interaction (impacts). In this sense, formulas and systems of formulas are understood to be the interface between the reality of things and observers (things) of things. Informational entity is a symbolism which appears between the observed and observing thing set (understood) by the observing thing. It becomes evident that an intelligent informational phenomenon, as a consequence of performing, behavior and being of an intelligent thing, can be satisfactorily symbolized only by an intelligent informational formula. What is an intelligent formula and how does it behave? In short, intelligent formula performs as intelligent information. It means that it must be metaphysical in informational way, that it must be observing and self-observ- ing, arising, emerging and coming into existence, in short, adaptable to the circumstances and to its throwness into unforeseeable situations and attitudes. In contrast to a mathematical formula or a computer program, informational formula is a changeable and emerging structure so far. Only in particular cases, it can take the role of a static, data, niathematical, or program structure to serve as a mechanical tool for an unchangeable and dedicated purpose. In contrast to a mathematical notion, informational formula has its own intention, skill, and rationality accordingly to which it can develop, emerge, arise autonomously through impacts coming from the world, itself, and the thing to which it mediates (communicates, informs). The eventfulness of a formula or a formula system images the events belonging to things which a formula or a formula system depicts. In tills function, formula is the symbolic coping of situation existing between the thing in question and its world. In parallel to the thing in the world, the formula is thrown in the world of observation and its own behavior (functionality, adequateness against a situation), impacting the observing thing, its metaphysics. Thus, a situation, its symbolical expression, and observing constitute a system of entities impacting them not only consequently but rather in an interactive manner. Symbolization of phenomena is in the position to become information for others, for observers of things and for observers of observers. Within occurring positions and attitudes of events higher informational forms and processes emerge, for instance, the phenomena of intention, consciousness, self-consciousness, unconsciousness, and other intelligently structured entities. The construction of formulas through the use of the discussed principles opens the way to spontaneous and circular possibilities for the emerging of formulas. Principles themselves are—as we could see—openly arising informational entities which, in a concrete case, are involved into situations of decomposition, composition, par-ticularization, universalization, informing, counter-informing, embedding, etc. One of the aims of this essay is to reveal the importance of informational understanding of for- mulas, to give them the emerging faculty, by which things themselves and their interactions can be symbolized in a more natural, adaptable way. An informational formula is nothing else than an interface between the worid and the thing in the worid. It is an emerging symbolic depiction of being-in-the-worid. It comes closer to the reality of a thing through its emerging structure than any statically structured symbolism (mathematical, programming language) could ever come. The principles of this essay have to be understood also as a changeable, emerging information for informational development of formulas which have the ability to depict real situations and real attimdes of things in question. REFERENCES [POI] Železnikar, A.P., Principles of Information, Cybemetica31 (1988), 99-122. [IIA] Železnikar, A.P., An Introduction to Informational Algebra, Informatica 14 (1990) 1, 7-28. [IT2] Železnikar, A.P., Informing of Things II (in Slovene), Informatica 15 (1991) 3, 29-43. A COMMENT This essay is a private author's work and no part of it may be used, reproduced or translated in any manner whatsoever without written permission except in the case of brief quotations embodied in critical articles and reviews. PLANIRANJE S PROLOGOM INFORMATICA 4/91 Keywords: planning, search, heuristics Matjaž Likar in Nilalizme [GEOR90] (predikatni račun, situacijski račun, n>odalna logika), ki se izkažejo uporabni tudi na področju planiranja. Najbolj poznane sisteme za planiranje skupaj s približnimi časi njihovili nastankov prikazuje tabela 1 [TATE90]. Bistvene lastnosti, ki jih srečamo i)ri ich sistemih, so; 1. sposobnost izpeljevanja novih zaključkov iz že poznanih dejstev o problemu ter relacij in omejitev, ki veljajo za določeno domeno, 2. nelinearnost, s katero se izognemo iskanju vseh možnih vrstnih redov akcij znotraj plana. hicrarhičnosl, ki proces planirajija razdeli na več nivojev, glede iia slopnjo razgradnje problema, sposobnost obravnavanja spremenljivk, vključevanje dodatnih omejitev, s katerimi omejimo iskanje, sposobnost ponovnega iskanja planov zaradi zunanjih sprememb, ki so nastale neodvisno od subjekta, ki izvršuje plan, 7. neodvisnost od domene. Tabela 1 Kronologija nastankov poznanih sistemov planiranja obdobje ime sistema 1960-1965 GPS, QA3 1965-1970 REF-ARF, STRIPS 1970-1975 ABSTRIPS, HACKER, PLANEX, MACROPS, i WARPLAN, HEARSAY, INTERPLAN 1975-1980 NOAH, NONLIN, MOLGEN, NONLIN+, NASL, 1980-1985 OPM, DEVISER, SIPE, PLANX 10, TWEAK 19S5-1990 OPLAN, PRS, SCRAPS, CHEF, PLEX, GTD, FORBIN, PRIAR, PRODIGY/EBL V tabeli 2 je podano, katere izmed zgoraj naštetih lastnosti so vključene v nekatere poznane sisteme za planiranje [WILK88]. Tabela 2 Lastnosti sistemov za planiranje sistem lastnosti 1 2 3 4 5 6 7 STRIPS + HACKER + ABSRIPST + + NOAH + + + + NONLIN + + + + DEVISER + + + + + MOLGEN + + + + SIPE + + + + + + + sistem za planiranje NOAH (1975) je že sposoben poiskati nelinearne in hierarhične plane, pri čemer uspešno obravnava tudi spremenljivke. Njegov naslednik NONLIN (1977) obvlada vračanje ("backtracking") [CHAP87,WILK88]. Začetki osemdesetih let prinesejo mnogi nove sisteme za planiranje; MOLGEN (1981) [STEF81a,STEF81b], DEVISER (1982) [CHAP87], SIPE (1983) [WILK88] in TWEAK (1984) [CHAPS7]. Bistvo teh sistemov je, da upoštevajo dodatne omejitve ali zahteve ("constraints") nad spremenljivkami, s katerimi operiramo v procesu planiranja, omogočajo planiranje za doseg konjunktivnih ciljcv ("conjunctive goals") in ponovno planiranje ("replanning") ob neuspešnem izvrševanju plana. V tem članku želimo opisati realizacijo sistemov za planiranje in na podlagi eksperimentalno dobljenih podatkov ugotoviti, kakšna je časovna zahtevnost ter kateri faktorji vplivajo na učinkovitost planiranja. Poleg tega obravnavamo tudi lastne izkušnje in rešitve, ki so specifične za planiranje v prologu. 2 ZAHTEVNOST PLANIRANJA Kompleksnost prostora stanj, ki ustreza problemu planiranja, je večinoma eksponentna funkcija velikosti problema [KORF87]. To potrjuje tudi kratka analiza velikosti prostora stanj za klasični problem planiranja v svetu blokov ("blocks world"). Število stanj, tj. različnih razporeditev n blokov v k skladov (k e [1,2..... n]) je enako vrednosti nepredznačenega Lahovega števila L' (pri danem n in k) [AIGN79]; n, k , , _ n!fn-I nj. ~ FT k-1 (1) Celotno število različnih stanj za n blokov, tj. s(n), je enako vsoti vseh nepredznačenih Lahovih števil pri danem n (enačba 2, tabela 3): s(n) = K,. (2) Zgornja meja števila različnih stanj za svet blokov pa je: s(n) = O (3/2)'"-" n! (3) Prvi sistemi za planiranje ,so predvsem eksperimentalne narave in iniajo za cilj formalizacijo človekovih sposobnosti razmišljanja o prihodnjih akcijah. V sistemih STRIPS in NOAH je ideja planiranja realizirana kot iskanje potrebnih akcij in njihovo razvrščanje znotraj plana. Pri sistemu STRIPS, ki so ga razvijali ob koncu šestdesetih in v začetku sedemdesetih let, poteka to iskanje samo na enem nivoju, kar se pri kompleksnejših problemih izkaže kot premalo učinkovit pristop [WILK88]. Ta slabost je odpravljena v sistemu ABSTRIPS [SACE74], kjer poteka proces planiranja na večih nivojih hierarhije abstraktnih prostorov ("hieararchy of abstraction spaces"). Prvi klasični iz česar vidimo, da gre za eksponentno rast prostora stanj. S povečevanjem števila blokov pa ne narašča le število različnih Stanj, temveč tudi število vseh različnih akcij a(n). Če za premikanje blokov uporabljamo akcije: unsiack, stack in move [GENE87], potem je: a(n) = n ^ k (k+1) ^ , (4) Povprečno Slevilo akcij, ki jih lahko izvedemo v nekem slanju, oz. faktor vejitve b(n) ("branching factor"), dobimo kol kvocient števila vseli možnih akcij a(n) in Števila vseh možnih slanj s^n; (tabela 3). Tabela 3 Komplelcsnost prostora slanj za svet blokov izpeljevanja novih dejstev iz predhodno poznanih dejstev. Sistema PLAN_H in PLAN_C vsebujeta dodatne kontrolne mehanizme za povečevanje učinkovitosti (lastnost 5). n s(n) a(n) b(n) 1 1 0 0.000 2 3 4 1.333 3 13 30 2.308 4 73 240 3.288 5 501 2 140 4.271 6 4,051 lO' 2.130 10" 5.258 7 3,763 lO"* 2.351 lO' 6.246 8 3,944 10' 2.854 10® 7.237 9 4,597 10® 3.782 lO' 8.228 10 5.894 10' 5.434 10® 9.220 20 3.277 10^° 6.283 10^' 19.172 30 1.980 lO" 5.771 10" 29.147 50 3.772 lO" 1.853 10'° 49.119 100 2.422 10'^' 2.400 10'" 99.089 Pri večjem številu blokov se faktor vejitve približa vrednosti n, zato velja: b(n) = 0(n) (5) Zahtevnost problema planiranja in s tem tudi čas planiranja pa ni odvisen samo od števila blokov, oz. faktorja vejitve, marveč tudi od dolžine iskanega plana d, ki je lahko od O do 2(n-l). Funkcijski izraz, ki povezuje faktor vejitve in dolžino plana s časom planiranja, je odvisen od strategije planiranja. 3 RE.ALIZACIJA SISTEMOV ZA PLANIRANJE Študijo sistemov za planiranje smo izvedli v treh korakih. Najprej smo poiskali ustrezen model sistema, ga zatem implementirali na računalniku in preizkusili pri reševanju različno zahtevnih problemov. 3.1 Model sistema Model sistema za planiranje (slika 1) smo zgradili na osnovi sheme iz (GENE87]. V sistem PLAN_S smo vgradili lastnosti I, 4 in 7 (glej labelo 2), kar pomeni, da gre za linearni sislem planiranja neodvisnega od domene z možnostjo obravnavanja spremenljivk. Sislem je v omejenem obsegu tudi sposoben Slika 1 Zgradba sistema za planiranje Oznake, ki nastopajo na sliki 1, pomenijo: a - označevalnik začetnega stanja ("initial state designator"), p - označevalnik cilja ("goal designator") ali ciljna relacija ("goal relation"), r - množica označevalnikov akcij ("action designators") (enostavne akcije in zaporedja akcij), Q- podatkovna baza s stavki o začetnem stanju, cilju in uporabnih akcijah, Y - plan (zaporedje akcij), s katerim ob izvršitvi v začetnem stanju dosežemo ciljno slunje. Začetno stanje predstavlja posnetek opazovanega sveta v trenutku, preden začnemo izvajati akcije iz plana (slika 2). C a 1 b 1 Slika 2 Primer začetnega stanja Začetno stanje opiSemo s seznamom dejstev, ki veljajo v tem stanju: inilial([clear(c),on(c,a),tablc(a),clcar(b),table(b)l). Cilj ("goal") je lahko katerokoli dosegljivo željeno stanje opazovanega sveta [GENE87] (slika 3). To je tisto stanje, ki ga v realnena svetu vzpostavimo tedaj, ko opravimo vse v planu zahtevane akcije. Definiciji cilja lahko ustreza več slanj. Slika 3 Primer ciljnega stanja Cilj, da je npr. v svetu treh blokov blok o na bloku b in hkrati hlok 1) na bloku c, zapišemo kol; goal([clcar(a),on(a,b),on(b,c),lablc(c)]). Za opisovanje akcij smo uporabili zapis, v kalerem je podan seznam pogojev ("preconditions") za izvedbo akcije, seznam pozilivnih učinkov ("positive effecls"), oz. dejstev, ki postanejo resnična po izvrSitvi akcije, in seznam negativnih učinkov ("negative effects"), oz. dejstev, ki po izvršitvi akcije ne veljejo več. action action_name(urgumenll ,urgwnent2,...) : preconditions ==> positive effects # negative effects. S tem formatom so implicitno rešeni problemi ozadja ("IVanie problems"), prav tako pa je v njem zajela tudi strategija poravnave stanj ("stale alignmenl") [GENE87,\V1NS84]. Tako smo se izognili spremenljivkam za označevanje stanj, ki so npr. potrebne pri planiranju z uporabo resolucije. Definicije akcij niso del sistema za planiranje, ampak predstavljajo njegove vhodne podatke (f na sliki i). Podati jili moramo za vsako domeno posebej. Akcijo razlaganja (unstuck) iz blokovnega sveta smo v naših sistemih definirali kol; action u(X,Y) : [on(X,Y),dcar(X)] ==> llable{X),dear(Y)] # [on(X,Y)]. plan(Sl,S2,_,_,[]) :- match(Sl,S2). plan(Sl,S2,History,OIdDepth,[Action|Plan]) OldDcpth > O, do_f'orw(Action,Sl,NewSl), not(known(NewSl,IIistDry)), NewDeplh is OldDcpth - 1, plan(NcwSl,S2,[Sl|Mistory],NcwDepth,Plan). do_for\v(Action,OldState,NcwState) :-action Action : Pre ==> Add # Del, match(Prc,OldStatc), del_aII(Dcl,OldState,Tcmp), add_all{ Add,Temp,NcwState). Slika 4 Planiranje z iskanjem v globino v smeri naprej Zatem tvorimo novo stanje NcwState, tako da iz starega stanja zbrišemo negativne učinke Del in mu dodamo pozitivne učinke Add akcije Action. Sistem PLAN M Sistem za planiranje iz vhodnih podatkov: označevalnika začelnega stanja a, ciljne relacije p, množice označevalnikov akcij r in podatkovne baza Q poišče plan y, ki predstavlja reSilcv problema planiranja tedaj in le tedaj, če zadovoljuje pogoja [GENE87]: Iskanje plana na slepo (s poskušanjem) in vračanje ("backtracking") v situacijah, kjer ugotovimo, da nadaljnje planiranje ni več mogoče, se je pri kompleksnejših primerili izkazalo kot premalo učinkovito. Sistem PLAN_H (slika 5) predstavlja nadgradnjo predhodnega sistema. 7 mora biti element množice označevalnikov akcij F: YS r. Podatkovna baze O. mora logično implicirali, da izvršitev (Do) plana Y v začetnem stanju a ustvari stanje, ki ustreza relaciji p: n 1= p(Do(Y,a)). plan(_,Sl,S2,[]) :- niatch(Sl,S2). plan(forward,Sl,S2,[Action|Plan]) do_forw(Action,Sl,NewSl,S2), dircctlon(NewSl,S2,Dlrection), plan(Dircction,NewSl,S2,Plan). 3.2 Implementacija sistemov Sistem PLAN_S Sistem PLAN_S smo realizirali na principu algoritma iskanja v globino v smeri naprej od začetnega stanja proti ciljnemu stanju (slika 4) [BRAT86,STER86]. Jedro tega sistema je rekurzivna procedura plan(+Initial,+Goal,+History,+Dcpth,-Plan) (s predpono + so označeni vhodni argumenti, z - pa izhodni argument). Pred klicem procedure moramo poznati začetno stanje, ciljno stanje in omejitev iskanja v globino. Argument History vsebuje seznam že poznanih stanj v delno zgrajenem planu in je pri prvem klicu prazen ([]). Iskanje v globino omejuje argument Depth. Robni pogoj rekurzije je izpolnjen tedaj, ko se začetno in ciljno stanje ujemata (match). Kot rezultat dobimo Plan - seznam akcij. Znotraj procedure plan kličemo proceduro za spremembo stanja tl0j!ir>Y, Z (loJnrw(^Aclion,+OI(l§tfite,-Ncw§tiU6) preverimo, ali se pogoji Pre za izvedbo akcije Action ujemajo s starim stanjem OldStatc. plan(backward,Sl,S2,[Aclion|l'lan]) do_back(Action,S2,NcwS2,Sl), dircction(Sl,NcwS2,Direction) plan(Direction,Sl,NcwS2,P), coiicalenatc(P,[Action],Plan). do_for\v(Action,OldState,NcwState,Goal) ;-choosc(Action,OldStatc,NcwState,Goal). do_back(Inversc,OldGoal,NcwGoal,Initial) :-choosc( Action,üldGoal,NcwCoal,Initial), in versc(Action,Inverse). choosc(Action,Sl,NewSl,S2) :- findalI(Act,(action Act : Pre ==> Add # Del, matcli(Pre,Sl),lcgal(Act,SI,S2)),Actions), findJ)csKAcH0ns,Aftion,§l,NevvSl,S2), Slika 5 Dvosmerno hevristično planiranje , 40 S pomočjo procedure dircction(+Sl,+S2,-direction) smo realizirali dinamično izbiranje smeri planiranja. Na vsakem koraku iskanja plana ocenimo, ali terja manj naporov iskanje v smeri naprej ali v smeri nazaj. Če je faklor vejitve v irenumem začetnem stanju manjši kakor faktor vejitve v trenutnem ciljnem stanju, potem naredimo en korak v smeri naprej (do_forw) (slika 6), v nasprotnem primeru pa v smeri nazaj (do_back). rO H3 CH Ch Q- o-J trenutno začetno stanje trenutno ciljno stanje Slika 6 Primer izbire smeri planiranja naprej Sistemu PLAN_H smo dodali omejitev, s katero izmed vseh akcij, ki so izvedljive v nekem stanju, izberemo le dovoljene (legal) akcije. Akcija je v sistemu PLAN_H dovoljena v nekem stanju samo tedaj, ko njena izvršitev ne onemogoči nadaljnjega planiranja brez vračanja. Zaradi omejitve legal so učinki akcij odvisni od okoliščin ("context-dependent effects"), v katerih akcijo izvršujemo. Proceduri legal in direction je potrebno sestaviti za vsako domeno posebej. Pravimo, da gre za kontrolne strategije iskanja za specifične domene ("domain-specific search control strategies") [WILK88]. Iskanje plana v sistemu PLAN_H poteka po strategiji vzpenjanje ("hill-climbing"). Izmed vseh dovoljenih akcij v naslednjem koraku s hevrislično ocenjevalno funkcijo izberemo najboljšo akcijo (nnd_best na sliki 5). Od hevristične oceni tvene funkcije zalitevamo, da nikoli ne preceni ("overestimates") dejanskih stroSkov preostalega (Se nedograjenega) plana. Izpolnitev le zahteve zagotavlja, da sistem PLAN_H vedno najde optimalno rešitev. Sistem PLAN_C Pri hevrističnem planiranju v sistemu PLAN_H je iskanje vseh potencialno možnih in glede na okoliščine dovoljenih akcij prostorsko in časovno zahteven proces, kajti učinkovita (hitra) izračunljivost hevristične ocenjevalne funkcije je slabo združljiva z njenim učinkovitim delovanjem. Sistem PLAN_C vsebuje samo omejitev legal in se pri izbiri naslednje akcije zadovolji s prvo najdeno dovoljeno akcijo (slika 7). S tem smo bistveno zmanjšali čas planiranja, odrekli pa smo se temu, da na vsakem koraku poiSčemo najboljšo akcijo. Plani, ki jih najde sistem PLAN_C, zato niso optimalni. choosc(Action,Sl,NewSl,S2) :- action Action : Pre ==> Add # Del, niatch(Pre,Sl), legal(Action,Sl,S2), del_all(Del,SI,Temp,add_aIl(Add,Temp,NcwSl). V tabeli 4 je podan pregled omenjenih realiziranih sistemov s kratkim opisom strategije planiranja. Tabela 4 Kratek opis realiziranih sistemov opis sistema planiranje z iskanjem v globino naprej dvosmerno hevristično planlr. z omejitvami dvosmerno planiranje z omejitvami 3.3 Eksperimenti Vse eksperimente smo izvedli na računalniku PC s procesorjem 80386/80387 (25 MHz) in s pomnilnikom RAM velikosti 4 MB. Od sistemov smo zahtevali, da najdejo pravilen plan, poleg tega pa smo njihovo kvaliteto ocenjevali Se po naslednjih treh kriterijih: - Čas planiranja, - Število obravnavanih stanj in - dolžina najdenega plana. Te podatke nam izpišejo sistemi v trenutku, ko je planiranje zaključeno. Za vse tri sisteme PLAN_S, PLAN_H in PLAN_C smo pripravili enak vzorec z 20 primeri iz sveta blokov, ki se razlikujejo po številu blokov (n e [1, 2..... 5J) in dolžini plana d. V vzorcu so bili enakomerno zastopani primeri, ki so lažje rešljivi s planiranjem v smeri naprej, kot tudi primeri, ki so lažje rešljivi v smeri nazaj. Pazili smo tudi na to, da se v rešitvah - planih približno enako pogosto pojavljajo akcije unstack, stack in move. Pri sistemu PLAN_S smo za vsak problem planiranja najprej izbrali omejitev globine, ki je enaka dolžini optimalnega plana, zatem pa še omejitev 2(n-l), s katero lahko reSimo najbolj neugoden primer za n blokov. Sistema PLAN_H in PLAN_C smo dodatno preizkusili Se na primerih z večjim številom blokov (n € (10, 20, 30, 50, 100|), ker smo želeli ugotoviti, kje so meje njunih zmogljivosti. 4 REZULTATI V vzorcu 20-ih problemov planiranja je bilo več različnih problemov, vendar z enakim Številom blokov (2, 3, 4 ali 5). Zanje smo izračunali srednjo vrednost dobljenih rezultatov in jih podali v tabelah 5, 6 in 7. Na dno tabel smo uvrstili tudi rezultate problemov planiranja za 10, 20, 30, 50 in 100 blokov. V primeru, da kakšen izmed sistemov ni našel neke rešitve zaradi prevelikih pomnilniških zahtev ali zaradi izjemno dolgega časa planiranja, smo lo v labelah označili s simbolom "•". Slika 7 Izbira prve dovoljene akcije Tabela 5 Primerjava äasa olanirania fiirtem PLAN_S PLAN_S PLAN_H PLAN_C d = : opt . d = 2(n-l) n Irain:sec] Imin:secl [min:sec] [min:secl 1 00: 00. 00 00: 00. 00 00: 00, 00 00 00.00 2 00: 00. 05 00: 00. 05 00: 00, 08 00 00.05 3 00: 00. 49 00: 00. 65 00: 00, 30 00 00. 10 4 00: 04. 94 00: 26, 92 00: 00 ,77 00 00. 16 5 02: 57. 12 06: 04, 69 00: 01 ,70 00 00. 26 10 - - 00: 14 .06 00 00.88 20 - - 03: 02 .74 00 04.77 30 - - 14: 18 ,27 00 13. 95 50 - - - 01 04.38 100 - - - - Slike 8, 9 in 10 prikazujejo izmerjene rezullale (pravokolniki) in piedposlavljeiie časovne zalilevnosli (lomljenke), pri čemer je merilo na abscisi logarilemsko. Upoštevali smo vse rezullale cksijcrimenlov in ne več njihovih srednjih vrednosli. Pri sistemu PLAN_S predstavlja diagram odvisnost časa planiranja od vrednosti b'' (slika 8). Odvisnosti časa planiranja od vrednosti bd za sistema PLAN_H in PLAN_C smo prikazali na slikah 9 in 10. 1500 Čas ])laniranja [sck] / / n fii —(f / Oii D Slika 8 Čas planiranja za sistem PLAN_S čas planiranja [sek] D / / n n n 0 ,0 ,00 1000 Slika y Čas planiranja za sistem PLAN_H čas planiranja [sek] I) / / (D 0 Đ —5" ÌI bd Koliko stanj so obravnavali (razvili ali obiskali) med planiranj'-m posamezni sistemi, prikazuje tabela 6. Tabela 6 PrirP' rjava Števila obravnavanih stanj £yste:n PLAN_S PLAN_S PLAN_H PLAN_C d - opt. . d = 2(n-l) n št. stanj ét. stanj št. stanj št. stanj 1 1 1 1 1 2 3.0 3.0 2.5 2.5 3 15.8 20.5 3. 5 3.5 4 99.0 524. 5 4.8 4.7 5 2181.3 4520.3 7. 1 6. 1 10 - - 16 10 20 - - , 53 19 30 - - 112 28 50 - - - 46 100 - Pri sistemih za reSevanje problemov planiranja je ena izmed važnih kvalitet, da sistem najde najkrajši plan. Dolžine najdenih planov za vse sistem smo podali v tabeli 7. Tabela 7 Primerjava dolžine najdenega plana sistem PLAN. .S PLAN_ S PLAN_ .H PLAN_ C d = opt. d = 2(n-l) n dol. plana dol, plana dol. plana dol. plana 1 0 0 0 0 2 1, ,5 1, 5 1. 5 1 . 5 3 2, ,5 3, 0 2, 5 2. 5 4 3, ,5 5, 3 3, 5 3. 7 5 4 ,5 8 ,0 4 ,5 5 1 10 - - 7 9 20 - - 14 18 30 - - 21 27 50 - - - 45 100 - 5 DISKUSIJA V tem članku je podana primerjava delovanje treh različnih sistemov (strategij) za planiranje. Analiza učinkovitosti je opravljena na testnih primerih iz blokovnega sveta. Rezultati eksperimentov se skladajo s teoretičnimi izhodišči, poleg tega pa nudijo tudi povsem praktične napotke, ki so uporabni pri snovanju sistemov za planiranje v prologu, - Časovna zahtevnost planiranja z iskanjem v globino v sistemu PLAN_S se zelo dobro ujema (korelaeijski faktor r = 0.999) s itioreiičMo mipovedanim redimi 0(b'') (sliku 8). Slika 10 Čas planiranja za sistem PLAN_C V nekaterih primeriti je problem planiranja s sistemom PLAN_S lažje in hiireje reSljiv z večjo omejitvijo globine kot pa z manjšo. Ta anomalija se pojavi tedaj, ko že od vsega začetka razvijamo plan po pravi poti in ko do vračanja sploh ne pride. Učinkovitost sistema PLAN_S lahko povečamo z vgraditvijo dvosmernega iskanja, kot je to realizirano pri sistemih PLAN_H in PLAN_C. Rezultati eksperimentov s sistemoma PLAN_H in PLAN_C nakazujejo (r = 0.972 za PLAN_H in r = 0.973 za PLAN_C), da je časovna zahtevnost reda 0(bd) (sliki 9 in 10), s čimer nam je omogočeno reäevanje večjih problemov, kot s sistemom PLAN_S (tabela 5). Pri hevrističnem 'planiranju igra poleg sprejemljivosti [PEAR84] hevrislične ocenitvene funkcije pomembno vlogo njena učinkovita izračunljivost. Za reSevanje povprečnega problema planiranja s petimi bloki (tabeli 5 in 6) porabi sistem PLAN_H za obdelavo enega stanja (!) skoraj Šestkrat več časa kot sistem PLAN_C in trikrat več časa kot sistem PLAN_S. Hevristično planiranje s sprejemljivo hevristično ocenitveno funkcijo in v povezavi z omejitvijo legal v sistemu PLAN_H nam da optimalen (najkrajši) plan. LITERATURA [AIGN79] Aigner, M., Combinatorial Theory. New York: Springer-Verlag, 1979. [ALLE90] Allen, J., Hendler, J., and Tale, A. (eds.). Readings in Planning- San Mateo, California: Morgan Kaufman, 1990. [BARR83] Barr, A. and Feigenbaum, E. A., The Handbook of Artificial Intelligence, Vol. III. Los Altos, California; William Kaufmann, 1983. [BRAT86] Bralko, I., Prolog Progranvning for Artificial Intelligence. Wokingham, England: Addison-Wesley, 1986. [CHAP87] Chapman, D., "Planning for Conjunctive Goals", Artificial Intelligence, 32(3); 333- 337, 1987. [GENE87] Geneserelh, M. R. and Nilsson, N. J., Logical Foundations of Artificial Intelligence. Los Altos, California: Morgan Kaufman, 1987. [GEOR90] Georgeff, M. P., "Planning", in Allen, J., Hendler, J., and Tate, A. (eds.). Readings in Planning. San Mateo, California: Morgan Kaufman, 1990, pp. 5-25. [KORF87] , Korf, R. E., "Planning as Search: A Quantitative Approach", Artificial Intelligence, 33(1): 65-88, 1987. [NILS90] Nilsson, N. J., "Foreword", in Allen, J., Hendler, J., and Tate, A. (eds.). Readings in Planning. San Mateo, California: Morgan Kaufman, 1990, pp. xi-xii. - Obstaja lesna odvisnost časa planiranja od Števila obravnavanih stanj. Statistična analiza to nakazuje s korelacijskimi faktorji r > 0.9 za vse tri sisteme. Na področju planiranja v umetni inteligenci že obstajajo boljSe strategije od teh, ki so opisane v tem članku. Omenimo samo nekatere izmed najperspektivnejših: - razgradnja problemov v podcilje ("subgoals"): ReSitev celotnega problema dobimo s kompozicijo delnih reSitev, - makro operatorji ('macro operators'): V problemih skuSamo odkriti karakteristične vzorce - strukture, pri katerih smemo uporabiti določene makro operatorje. - hierarhično planiranje ("hierarchical planning"): Probleme rešujemo na večih nivojih s pomočjo abstrakcije. Za nadaljevanje razvoja', sistemov planiranja neodvisnega od domene menimo, da bo potrebno uporabiti kombinacijo večih strategij. Smatramo, da bi bila ena izmed perspektivnih možnosti hierarhični pristop k reševanju problemov, kjer bi nà vsakem nivoju lahko uporabljali vnaprej definirane enostavne ali makro operatorje, sama izbira operatorjev pa bi lahko potekala z uporabo učinkovitih hevrističnih ocenitvenih funkcij. Sistemi bi morali bili zgrajeni tako, da bi 'razumeli' primemo formalizirano znanje iz različnih področij, hkrati pa bi morali znali to znanje tudi učinkovito uporabljati. [PEAR84] Pearl, J., Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading, Massachusetts: Addison-Wesley, 1984. [RAND83] The Random House Dictionary of the English language. New York: Random House, 1983. [SACE74] Sacerdoti, D. E., "Planning in a Hierarchy of Abstraction Spaces", Artificial Intelligence, 5(2): J15-135, 1974. [STEFSIa] Stefik, M., "Planning with Constraints (MOLGEN: Part 1)", Artificial Intelligence. 16(2): 111-140, .1981. [STEFSlb] Stefik, M., "Planning and Meta-Planning (MOLGEN: Part 2)", Artificial Intellicence. 16(2): 141-170, 1981. [STER86] Steriing, L. and Shapiro, E., The Art of Prolog: Advanced Programming Techniques. Cambridge, Massachusetts: MIT Press, 1986. [TATE90] Tate, A., "A Review of Al Planning techniques", in Allen, J., Hendler, J., and Tale, A. (eds.). Readings in Planning. San Mateo, California: Morgan Kaufman, 1990, pp. 26-49. [VERB87] Verbinc, F., Slovar tujk. Ljubljana: Cankarjeva založba, 1987. [WILK88] Wilkinson, D. E., Practical Planning: Extending the Classical Al Planning Paradigm. San Mateo, California: Morgan Kaufman, 1988. [WINS84] Winston, P. H., Artificial Intelligence. Reading, Massachusetts: Addison-Wesley, 1984. DINAMIČNO DODELJEVANJE PROCESOV NA POLJU TRANSPUTERJEV Keywords: parallel processor system, token Peter Zaveršek, VELCOM, Velenje data flow, transputer, topology, simulation, Peter Kolbezen, Institut Jožef Stefan, dynamic scheduling Ljubljana V članku je obravnavatci problematika dodeljevanja procesov na večprocesorskem vezju, ki ga sestavljajo večkratno povezane zanke. Lokacija procesiranja posameznega procesa ni vnaprej določena. Obravnavani so trije načini dodeljevanja procesov: pri enonivojskem načinu prenosa podatkov po eni zanki ter pri enonivojskem in dvonivojskem načinu prenosa podatkov po dveh zankah hkrati. Za vse tri primere dinamičnega dodeljevanja je izdelan simulator dodeljevanja procesov. S pomočjo simulatorja sta analizirani izkoriščenost polja in hitrost izvajanja algoritma v odvisnosti od parametrov, kot so velikost in konfiguracija procesorskega polja, topologija programskega grafa in časova karakteristika procesov. Na osnovi opravljene analize je predlagan najboljši način dodeljevanja procesov in za različne topologije programskega grafa takšen izbor parametrov, ki vodi k čim večji učinkovitosti večprocesorskega sistema. PROCESS ALLOCATION IN THE MULTITRANSPUTER NETWORK. The paper deals with a problem of process allocation in a multitransputer network which consists of multiple-connected unidirectional rings. Executing location of every certain process is not explicitly stated, i.e. process allocation is dynamic. Three different possible algorithms for process allocation are presented. The algorithms are as follows: a) one-level communication and sending data in one direction, and b) one-level communication and sending data in two directions simultaneously, c)two-level communication and sending data in two directions simultaneously. Efficiency of different network configurations, program graph topologies and ratio of process execution time to process transfer time were verified by a simulation. Finally the results of simulation are presented and the most efficient process allocation algorithm of the three proposed is selected. 1. UVOD Zahtevam po vedno večji moči procesiranja je mogoče zadostiti le s paralelnim računanjem na dovolj veliki množici procesorjev. Takšno množico, ki ima paralelno strukturo, lahko predstavlja polje procesorjev. Posameznih procesorjev polja ni mogoče izkoristiti tako dobro, kot pri enem samem procesorju. Procesorji, ki delujejo paralelno, praviloma niso zasedeni ves čas izvajanja algoritma. Izkoriščenost (zasedenost) po procesorjih je neenakomerno porazdeljena. Idealnim razmeram se je mogoče le bolj ali manj približati. Pri tem igra pomembno vlogo več dejavnikov. Pomembnejši med njimi so: Paralelizacija algoritma. Postopek naj bi odkril ves inherentni paralelizem v danem algoritmu, ki se bo izvajal na paralelnem sistemu. Z ustrezno analizo algoritma ugotovimo, kateri procesi se lahko izvajajo paralelno in kateri sekvenčno, čas izvajanja posameznih procesov in število podatkov, ki so za izvajanje potrebni. Granulacija algoritma. Algoritem, ki določa neko opravilo in ga izvajamo na našem sistemu, razstavimo na več podopravil. Na koliko podopravil razbijemo opravilo glede na velikost celotnega opravila, kar določa razdrobljenost (granulacijo) algoritma, je odvisno od števila in od zmogljivosti razpoložljivih procesorjev. Podopravilo (subtask ali grain) se avtonomno izvaja na enem od procesorjev polja. Granulacija vpliva na razmerje med časom, ki je potreben za prenos podatkov med dvema procesorjema in časom izvajanja procesa. To razmerje imenujemo količnik prenosnega časa. Izbira najustreznejše granulacije pri danem večprocesorskem sistemu je odvisna od topologije in velikosti procesorskega sistema in ima velik vpliv na učinkovitost izvajanja algoritma. Zato moramo pri pripravi algoritma za izvajanje na paralelnem sistemu granulaciji posvetiti še posebno pozornost. Dodeljevanje procesov. Procese moramo razporediti po polju procesorjev tako, da je polje čimbolj izkoriščeno. Pri tem je pomembno, da je število komunikacij med procesi čimmanjše in čas dodeljevanja čimkrajši. Porazdelitev bremena. Procesorji v polju morajo biti enakomerno obremenjeni. Neenakomerna obremenjenost zmanjša učinkovitost polja in poveča ceno, ki je posledica povečanega skupnega časa procesiranja. V delu je obravnavana problematika, ki je prisotna predvsem v zadnjih dveh dejavnikih, m se opira na simulacijo predlaganega večprocesorskega sistema. Sistem je sestavljen iz polja transputerjev in je podrobneje opisan v delu /6/. Zanj so značilni: Krožna konfiguracija: Konfiguracijo sistema sestavlja večje število med seboj prepletenih prstanov (linkov), ki povezujejo vse transputerje polja. Oblika poti ni pomembna. Pot mora biti le krožno zaključena neglede na to, kje v sistemu ima izhodiščno točko. Primer takšnega sistema je hiperkocka. Hierarhično dodeljevanje procesorjev: Polje procesorjev izvaja podopravila. V podopravilu se operacije (imenovane procesi) izvajajo, kolikor je mogoče konkurenčno. Procesi so v značilnem odnosu, toda neodvisni med seboj (tako kot DO zanke v fortranu). Podopravila je mogoče predstaviti v obliki hierarhičnih acikličnih grafov pretoka podatkov (HADFG). Vozlišče takšnega podgrafa je proces, ki se izvaja na enem od transputerjev polja. Znotraj vsakega procesa so možne zanke. Kontrolo nad podopravih, ki so določeni z eno ali več HADFG, ima poseben procesor na vhodu v procesorsko polje. Dinamično dodeljevanje procesorjev: Razvrščanje procesov je avtomatizirano in dinamično. Dosledno sledi pravilu, ki ga določa položaj procesa ali veje v strukturi HADFG. Komunikacija s pomočjo žetonov: Komunikacijski mehanizmi so osnovani na uporabi žetonov, ki krožno potujejo znotraj posameznih prstanov. Komunikacije so enosmerne. Fizični prstan sestavljata dva komunikacijska prstana. Eden od njiju je uporabljen za prenos krmilnih žetonov, drugi pa za prenos podatkov, programskih blokov in rezultatov. Pri dinamičnem razporejanju se preslikajo posamezni procesi na procesorje med samim izvajanjem algoritma. Izkoriščenost procesorjev, ki mora biti v vsakem trenutku čimboljša, se dinamično spreminja in je odvisna od vsakokratnega trenutnega stanja sistema. Uporaba dinamičnega načina razporejanja je posebej primerna v naslednjih primerih: • čas izvajanja procesov ni vnaprej določen, • v fazi analize algoritma ne poznamo konfiguracije sistema, na katerem se bo algoritem izvajal, • želimo trdoživ (fault tolerant) sistem. 2.1. DINAMIČNO RAZPOREJANJE PROCESOV Sistemi z dinamičnim dodeljevanjem procesov ugotavljajo trenutno stanje sistema na več načinov /7/: • Bolj obremenjen procesor išče manj obremenjenega. Ta način je uspešnejši za malo in srednje obremenjene procesorje. • Manj obremenjen procesor išče bolj obremenjenega. Rešitev je bolj primerna za zelo obremenjene procesorje. Naš sistem uporablja oba zgoraj omenjena načina. Obremenjeni procesor išče nezaseden procesor, da bi mu predal enega izmed čakajočih procesov. Ko ga najde, mu preko sporočila preda podatke o procesu, kije prvi na vrsti na čakajoči lestvici procesov. Postopek se ponavlja, dokler procesor ne ugotovi, da ni več nezasedenega procesorja. Takrat se postavi v stanje čakanja. Procesor, ki zaključi svoj proces in se tako sprosti, pošje procesorjem v zanki sporočilo, da ni več zaseden. Tedaj mu pošlje procesor, ki ima Se čakajoče procese, zahteve oz. podatke o naslednjem procesu, ki ga bo izvajal in cikel se tako ponovi /6/. 2. DODELJEVANJE PROCESOV Poznanih je več načinov dodeljevanja procesov. Bistveno se med seboj razlikujejo predvsem načini statičnega in dinamičnega razporejanja procesov. Pri statičnem razporejanju preslikamo posamezne procese na določene procesorje že pred začetkom izvajanja. Preslikava je osnovana na analizi sočasnosti in čimboljši izkoriščenosti procesorjev. Praviloma je pri statičnem razporejanju mogoče doseči večjo izkoriščenost sistema. 2.2. TEHNIKA ZASEGANJA VIROV IN ZASEDENOST SISTEMA Poznanih je več tehnik zaseganja sistemskih virov. Zlasti sistemi hierarhične zgradbe imajo lahko poseben nadzorni procesor, ki hrani informacijo o stanju vseh ostahh (delovnih) procesorjev. Nadzor nad zasedenostjo procesorjev je osredotočen na enem samem mestu. Slabost takega načina so dodatne komunikacije, ki so potrebne zaradi nenehnega testiranja stanj sistema. Ker so podatki o sistemu shranjeni v skupni tabeli, do katere imajo dostop vsi procesorji, obstaja možnost sočasnega dostopa in lahko pride do konfliktne situacije. V primeru, da ima vsak procesor svojo kopijo tabele, ki vsebuje stanja vseh procesorjev sistema, je nadzor nad zasedenostjo procesorjev enako porazdeljen na vse procesorje. Pri tem je potrebno vse kopije sproti osveževati. Možnost konfliktnih situacij je v tem primeru lahko ob primerni organiziranosti sistema manjša, z večanjem šte\dla procesorjev v sistemu pa se hitro veča tudi število komunikacij. y obravnavanem sistemu je izdelana posebna tehnika zaseganja sistemskih virov, pri kateri je nadzor nad zasedenostjo procesorjev porazdeljen le nekaterim procesorjem, t.im. korenskim procesorjem v sistemu. Ti imajo evidenco o zasedenosti tistih procesorjev, ki so korenskemu procesorju dosegljivi. dodatnih vmesnikov. Komunikacija preko zanke lahko v obeh smereh poteka istočasno, avtomatično in skoraj brez obremenjevanja transputerja. Uporabniku je zunanja komunikacija povsem identična komunikaciji med notranjimi procesi. Prenos podatkov med transputerji je paketni in poteka preko komunikacijske zanke s hitrostjo, kije po tovarniških podatkih 5,10 ali 20 Mb/s. Tej vrednosti se lahko približamo, če imamo prenos v eri zanki in le v eni smeri, in če transputer ne opravlja nobenih drugih opravil. Realno dosežena hitrost prenosa je v veliki meri odvisna tudi od vrste uporabljenega transputerja. Prenosni paket sestavlja 11 bitov: 2.3. PRENAŠANJE SPOROČIL Način prenašanja sporočil ima pomembno vlogo v večprocesorskem sistemu. Sporočilo je sestavljeno iz niza elementarnih podatkovnih paketov FCD (imenovanih "flits" - Flow Control Digits). FCD je najmanjša enota sporočila, ki jo lahko kanal ali vrsta sprejme ali zavrne. Večja hitrost prenosa preko večih posrednikov (procesorjev v sistemu) je dosežena tako, da vsak posrednik prične predajati sporočilo naslednjemu procesorju, še predno ga sprejme v celoti. Predaja prvega FCD se začne takoj, ko procesor preveri, da sporočilo ni namenjeno njemu. Posamezne FCD sporočila pa lahko začasno tudi zadrži, če je pot naprej zasedena. Takšno prenašanje sporočila, ki leze po sistemu kot črv, je v tuji literaturi poznano pod imenom "cut-through" /8/. Pri prenosu sporočila ne sme nastopiti smrtni objem (deadlock) ali živi objem (livelock). Smrtnemu in živemu objemu se v našem transputerskem sistemu izognemo že na dokaj enostaven način. Smrtni objem preprečimo z dovolj velikimi vmesniki za prenos sporočil pri prenosnih procesorjih/2,8/, živi objem pa z enosmernimi zankami. Ibit startni bit Ibit zastavica "podatki" 8 bitov podatek Ibit stop bit Transputer, ki sporočilo sprejema, mora potrditi vsako besedo sporočila posebej. Potrditveno sporočilo je dolgo 2 bita: Ibit startni bit Ibit stop bit Transputer T414 /4/ prenaša sporočilo tako, da najprej sprejme celo besedo sporočila (11 bitov) in nato odda potrdilo o sprejemu (2 bita). Teoretična hitrost prenosa je: ™ uni TQMbs ("I T414 = -1 lòciklov -1 3. MEDTRANSPUTERSKE KOMUNIKACIJE Transputer uvrščamo v družino RISC procesorjev /5/. Na tržišču je že več transputerjev, ki se med seboj razlikujejo predvsem po svoji zmogljivosti (hitrosti), protokolu komuniciranja, podpori za aritmetične operacije in pd., lahko pa tudi po namembnosti, ki jo določi že proizvajalec. Za nas je pomembna značilnost, da transputer že na strojnem nivoju podpira paralelno izvajanje procesov (v določeni meri kvazi-paralelno). Komunikaciji so namenjene štiri vgrajene dvosmerne zanke (linki). Te zanke omogočajo, da lako transputerje medsebojno povezujemo brez Transputer T800 ima izboljšan protokol prenosa. Ne čaka na sprejem cele besede sporočila, temveč potrdi sprejem sporočila že pred zaključkom prenosa. Oddana beseda in potrditev sprejema se med seboj prekrivata. Zato je za prenos sporočila potrebno manjše število ciklov. Dolžina sporočila je le 11 bitov: ™ uni IQMbs ^^ T800 = -1 llciklov -1 Dvosmerni prenos preko ene zanke zahteva dodatne potrditvene bite za nasprotno smer, kar pomeni za T800 13 bitov in prenos s hitrostjo CT = l,54MBs'^ To je teoretična hitrost prenosa za vsako zanko (link) v vsaki smeri. Teoretična skupna možna hitrost prenosa preko štirih dvosmernih zank je 12MBs'\ v eni smeri pa je potem okoli l,5MBs'^. Realna slika je seveda drugačna. Čeprav delujejo komunikacijske zanke ločeno in so ločene tudi od ostalih procesov, ki se izvajajo na transputerju, prihaja do medsebojnih vpUvov. Realne vrednosti so zato dosti manjše od teoretičnih. Prenosi preko zank (sprejem, oddaja, vmesno shranjevanje sporočil) zahtevajo dostop do transputer-jevega pomnilnika. Prenosi do pomnilnika potekajo v obliki DMA prenosov m so načehio med seboj neodvisni, vendar zasedejo določen del pasovne širine transputerjevega podatkovnega in naslovnega vodila. Pasovna širina podatkovnega vodila znaša za notranji pomnilnik 80MBs"^, za zunanji pomnilnik pa 26.6MBs"^ Primerjava s teoretično najvišjo možno hitrostjo prenosa nam pokaže, da to pomeni 15% pasovne širine vodila notranjega pomnilnika oz. skoraj 50% pasovne širine vodila zunanjega pomnilnika. Posledice so dvojne. Konfliktne situacije po eni strani zmanjšujejo hitrost prenosov po zankah, po drugi strani pa ovirajo izvajanje samega procesa na transputerju, ki prav tako potrebuje dostop do pomnilnika. Realno so prenosi po zankah redkejši in je zato pogostost konfliktnih situacij manjša. Procesi, ki izvajajo servisne rutine za prenose, in preklopi med delovnimi procesi (konteksti) nimajo zanemarljivega vpliva na učinkovitost procesiranja. Servisnih procesov je lahko več hkrati in običajno tečejo v prioritetnem načinu (PRI PAR, PRI ALT). Pogostost takšnih procesov lahko občutno podaljša čas izvajanja delovnega procesa in s tem delovno zmogljivost procesorja. Servisne rutine za prenos podatkov morajo biti čimbolj učinkovite. Temu pripomore predvsem hitrost izvajanja teh rutm. Tudi promet podatkov naj bo redkejši, daje obremenjenost notranjih vodil manjša. Analiza prenosa podatkov med transputerji in raziskava vpliva prenosa podatkov na učinkovitost sistema, sta opisana v delu /1/. Raziskava je bila omejena na transputer T414 pri taktu 15MHz in pri različnih konfiguracijah transputerskih povezav (prstan, drevesna struktura, hiperkocka). Za vsako konfiguracijo je bila napisana posebna servisna komunikacijska rutina. Testiranje je bilo opravljeno pri različnih dolžinah sporočil v razponu od enega do 1024bytov. Rezultati kažejo realen vpliv naštetih faktorjev na zmanjšanje delovne moči transputerja. Enosmerni prenos preko ene same zanke zmanjša moč procesiranja za 5 do 10%. Zanimivo je, da se minimalna moč ne pojavlja na gornji ali spodnji meji dolžine sporočila, temveč pri 64 bytih. Možna razlaga tega pojava je, da prihaja do časovno izredno neugodnega preklapljanja kontekstov. Istočasni prenos sporočil po različnih zankah in tudi takih, ki dopuščajo dvosmerne prenose, dajejo približno enake rezultate. To velja le za prenose daljših podatkovnih blokov (okoli IkB). Zmanjšanje delovne moči pri takšnih prenosih je okoli 12%. Krajša sporočila zahtevajo pogostejše preklope na servisni proces in delovna moč transputerja občutno pade - tudi za 85% in več. Zato kratka sporočila niso zaželena. 4. SIMULACIJA PROCESIRANJA Predpostavljmo, da so podalgoritmi, ki se izvajajo na našem transputerskem polju večprocesorskega sistema, predstavljivi v obliki hierarhičnih acikličnih grafov pr^ka podatkov (HADFG). To so drevesni grafi, katerih veje so razvrščene v več nivojev. Vsaka veja se končuje z novim razvejiščem ah s procesom. Nivoji z množicami paralelnih procesov in nivoji z množicami zaporednih procesov se med seboj izmenično prepletajo. Iz dela /6/ je razvidno, da taka predstavitev omogoča avtomatizirano dinamično porazdeljevanje procesov algoritma na polje procesorjev. Dodeljevanje procesov smo opazovali na simulatorju, ki smo ga posebej zgradili v ta namen z nalogo, da čimbolj verno simulira izvajanje algoritma na našem procesorskem polju. Simulator upošteva zmanjšano delovno moč procesorja, ki je posledica prenosov. Predpostavljamo, da prenos v eni sami smeri zmanjša delovno moč transputerja na 90%, prenos v dveh smereh pa na 85%. Ta ocena je slabša od podane v literaturi /1/. Simulacija dodeljevanja in izvajanja procesov naj bi dala odgovore na nekatera odprta vprašanja, ki so bila zastavljena že v delu /6/. Predvsem sta nas zanimala: • najustreznejša granulacija algoritma (količnik prenosnega časa), in • najustreznejša topologija (prstan, kvadrat, pravokotnik). 4.1. KONFLIKTNE SITUACIJE V realnem večprocesorskem sistemu nastopajo konfliktne situacije, ki so pogojene z zgodovino izvajanja opravila. Simulator, ki bi simuliral delovanje transputerskega polja do vseh potankosti, bi imel veliko časovno in programsko kompleksnost. Ker smo želeli kompleksnost simulacije zmanjšati, smo jo poenostavili s hevrističnim razreševanjem konfliktov. Če se pri simulaciji pojavi konfliktna situacija, izberemo enega izmed udeležencev in mu damo prednost pred ostalimi. Posledica tako poenostavljenega razreševanja konfliktov je, da nam lahko dajejo ponavljajoče se simulacije istega HADFG na istem sistemu različne rezultate. Zato smo predpostavili, da predstavlja pravilen rezultat povprečje rezultatov večjega števila simulacij. 4.2. NAČINI RAZPOREJANJA PROCESOV Uporabili smo več različnih načinov razporejanja procesov. Vsi trije načini so osnovani na enakem osnovnem principu, ki je podrobneje opisan v delu /6/, in se opira na hierarhično drevesno strukturo grafa. Razporejanje procesov se lahko izvaja v največ dveh nivojih. Procesorji v obeh zankah, ki pripadata začetnemu korenskemu procesorju tvorijo t.i. prvi procesorski nivo. Če je iskanje prostih procesorjev na tem nivoju neuspešno, nadaljujemo iskanje prostih procesorjev na drugem nivoju, na katerem pregledamo še preostali del ravninskega polja. Pregledovanje poteka tako, da pošlje korenski procesor procesorjem prvega nivoja v eni izmed dveh možnih zank (t.im. horizontalni ali vertikalni) zahtevo, da v zankah, ki so pravokotne na prvi nivo najdejo prost procesor. Oglejmo si posamezne načine razporejanja procesov: a) Enonivojski način razporejanja s prenosom podatkov po eni zanki.Ta način je najpreprostejši. Osnovno idejo razporejanja najlažje predočimo s pomočjo paralelnega razvejišča grafa. Ko se spustimo po grafu do paralelnega razvejišča, zasedemo največ toliko prostih procesorjev, kolikor je vej v razvejišču. Dostopni procesorji se nahajajo neposredno v eni izmed dveh zank prvega procesorskega nivoja. Če pri zaseganju procesorjev zmanjka prostih procesorjev v prvi zanki, jih zasežemo še v drugi. Pri tem se lahko primeri, daje število procesov večje kot število dostopnih procesorjev. V takšnem primeru postavimo čakajoče procese v čakalne vrste. Ko se kateri izmed dostopnih procesorjev sprosti, mu dodelimo naslednji čakajoči proces. Opisana metoda ima vsaj dve slabosti: • Dodeljevanje procesov poteka v vsakem trenutku le v eni zanki (horizontalni ali vertikalni), čeprav lahko transputer hkrati predaja sporočila v več smereh. • Kopridemovnovo razvej išče, v fazi "priprave" takoj zasežemo vse razpoložljive procesorje. Zaseženi procesorji nadalje čakajo na sprejem podatkov o procesu, ki ga morajo izvajati. V stanju čakanja so blokirani in neuporabni, kar zmanjšuje izkoriščenost procesorskega polja. b) Enonivojski način razporejanja s prenosom podatkov po dveh zankah hkrati. Posebnost tega načina je, da pri razporejanju ne rezerviramo vnaprej vseh dostopnih procesorjev. Izberemo le en prost procesor v vodoravni in le en prost procesor v navpični zanki. Prenos procesov lahko poteka hkrati v obeh smereh. Takoj, ko se eno od sporočil prenese, poiščemo naslednji prost procesor v isti smeri, tj. v smeri že prenešenega sporočila. Tako se lahko tudi faza "priprave" v eni smeri in faza prenosa sporočila v drugi smeri izvajata hkrati. To se dogaja v primerih, ko sta dolžini sporočil različni. V primerjavi z zgornjim načinom razporejanja so lastnosti tega načina naslednje: O prost procesor zaseden procesor Slika 1. Neizkoriščenost polja pri enonivojskem dodeljevanju • Sistem je hitrejši zaradi istočasnega prenašanja sporočil v obeh smereh. • Blokiranost procesorjev v polju je manjša. • Delovna moč korenskega procesorja je zaradi povečanega obsega strežbe manjša. Skupna slabost obeh gornjih načinov razporejanja je, da lahko paralelne procese dodeljujeta le v vodoravni in navpični zanki glede na korenski procesor, tj. le na prvem procesorskem nivoju. Večjega števila procesov, kot je prostih procesorjev v teh dveh zankah, korenski procesor ne more oddati. Zato obstaja možnost, da ostanejo nekateri procesorji polja neizkoriščeni. Slika 1 kaže neučinkovitost enonivojskega razporejanja na izkoriščenost sistema. Na polju štirih transputerjev se lahko izvajajo štirje procesi hkrati, v našem primeru pa le trije. Četrti proces čaka na procesor toliko časa, dokler se ne sprosti eden od treh že zasedenih procesorjev, medtem ko četrti procesor ostane ves čas neizkciJfen. c) Dvonivojski način ra/porejanja pri prenosu podatkov po dveh zankah hkrati. Ta način omogoča, da so lahko hkrati izkoriščeni vsi procesoiji polja. 2sl razliko od gornjih dveh metod iščemo tu nezasedene procesoje po celotnem procesorskem polju in ne le Pl O ® P3 P2 2 A P4 O A O začetni procesor posrednik ' končni procesor Slika 2. Izkoriščenost polja pri dvonivojskem dodeljevanju po zankah, ki potekata skozi začetni korenski procesor. Na prvem nivoju iskanja prostih procesorjev je način delovanja enak, kot pri prvih dveh načinih. Če je iskanje na tem nivoju neuspešno, ga nadaljujemo na drugem nivoju in tako pregledamo celotno ravninsko polje procesorjev. Iskanje prostih procesorjev na drugem nivoju poteka takole: Začetni (korenski) procesor najpreje ugotovi zanko v katero ne oddaja nobenega procesa. Procesorji v izbrani zanki so procesorji prvega nivoja. Tem procesorjem pošlje žeton z zahtevo, da mu najdejo prost procesor na drugem nivoju. Procesorji, ki so v zanki, iščejo prost procesor drug za drugim. Procesor, kije našel prost procesor, postane posrednik pri prenosu podatkov in sporočil. Slika 2 kaže pri uporabi tretjega načina razdeljevanja procesov na danem primeru popolno izkoriščenost procesorskega polja. Ta način se je izkazal kot najboljši. 4.3. SIMULACIJA IZVAJANJA HADFG Najpreje smo generirali množico Gn 20 naključnih grafov HADFG. Vseh 20 grafov smo obravnavali kot sortirane in nesortirane grafe. Vsak graf iz množice Gn smo tudi sortirali in tako dobili množico sortiranih grafov Gs. Skupaj smo simulirali izvajanje 2 x 20 grafov iz mnžice G, ^G = Gn U Gs ) . Pomen sortiranja grafov in definicijo sortiranega grafa najdemo v delu/6/. Izvajanje vsakega grafa smo simulirali na različnih konfiguracijah procesorskega polja s številom procesorjev od 1 do 16. Izbirali smo konfiguracije iz nabora konfiguracij K =a x b , kjer sta a,b '1,2,3,4 ' V prvi fazi raziskave smo opazovali čas izvajanja grafa v odvisnosti od izbranih konfiguracij. Na osnovi dobljenih rezultatov smo se pri nadaljnih raziskavah omejili na tiste konfiguracije polja, pri katerih so se pokazah boljši rezultati. V drugi fazi raziskave smo opazovali čas izvajanja grafa HADFG v odvisnosti od količnika prenosnega časa. Količnik smo spreminjali po stopnjah 1,2,5,10, 20,50,100,200,500,1000. Pri tej raziskavi smo izbrali graf iz tiste podmnožice G* grafov množice G, za katero velja: 1., da je G* »1 G*, in 2., da so grafi iz množice G*v prvi fazi raziskave dali podobne rezultate. Tretjo fazo raziskave smo posvetili izbiri najprimernejšega načina razporejanja procesov pri dopustnem količniku prenosnega časa v odvisnosti od dveh kriterijev: • časa izvajanja HADFG •• učinkovitosti procesorskega polja 4J.1. DOPUSTNI KOLIČNIK PRENOSNEGA ČASA Pri dani konfiguraciji polja je čas izvajanja grafa HADFG poleg algoritmičnih lastnosti grafa HADFG tudi funkcija razmerja Tjzv/Tp. Normirani čas izvajanja grafa HADFG je razmerje med tem časom pri izbranem razmerju Tizv/Tp in med minimalnim časom izvajanja. Dopustni količnik prenosnega časa je tisto razmerje Tiiv/Tp, pri katerem je normirani čas izvajanja grafa enak dvakratni vrednosti minimalnega časa izvajanja. 432. ČAS IZVAJANJA HADFG Čas izvajanja grafa HADFG smo vzeli kot merilo za primerjavo med različnimi načini razporejanja. Ker je ta čas odvisen od algoritmičnih lastnosti grafa HADFG in od konfiguracije procesorskega polja, smo definirali vsoto 5k ^Gj ^ , ki je vsota časov iz- vajanj HADFG iz izbrane množice algoritmov pri določeni konfiguraciji procesorskega polja. Velja: Čas zasedenosti procesorskega polja Tzas je podan 7 enačbo Tzds =2]7'izvi +2l7'bloki kjer je: k ... element iz množice konfiguracij {2x2, 3x3, 4x4} G]... element iz množice Gs ,Gn T, ... čas izvajanja / -tega grafa HADFG iz množice Gj . V našem primeru je i element iz množice . i;2,...,20 }. Primerjava vsot 5k ^Gj ^ pri različnih načinih razporejanja nam daje oceno uspešnosti posameznih načinov. 433. UČINKOVITOST PROCESORSKEGA POLJA Učinkovitost procesorskega polja E je razmerje med ceno izvajanja grafa HADFG na enem procesorju in ceno izvajanja na večprocesorskem sistemu. Idealna vrednost je 1, kar pomeni, da je paralelni sistem maksimalno izkoriščen. E =- /I - T' kjer je: n ... število procesorjev v sistemu T ... povprečen čas zasedenosti procesorjev 7s... čas sekvenčnega izvajanja grafa HADFG. Čas sekvenčnega izvajanja grafa HADFG je tisti čas, ki jc potreben, da se graf izvede na enem samem procesorju. Torej je: Ts , i kjer je Tpj čas izvajanja /-tega procesa grafa HADFG. 43.4. ZASEDENOST PROCESORSKEGA POLJA Procesor je zaseden v dveh primerih: ® kadar izvaja proces, ki je določen z vozliščem grafa © kadar pričakuje podatke ali rezultate (je blokiran) .""laj bo 7izvj čas izvajanja procesov na /-tem procesorju In 7"bioki čas blokiranosti /-tega procesorja polja. Zasedenost procesorskega polja Z je razmerje med časom povprečne zasedenosti procesorjev v polju in časom izvajanja grafa HADFG na tem istem polju. Z = T-graf ' kjer je: Tgraf ••• čas izvajanja grafa HADFG na procesorskem polju, in Tzas... čas povprečne zasedenosti procesorjev v polju n—I—I-r 20 100 500 10 M 200 1000 Razmerje Ti^v/Tp Slika 3. Nonnirani čas izvajanja za različne K Povprečna zasedenost procesorjev v polju je: Tn r.as - ^^ kjer je Tzas čas zasedenosti procesorskega polja in n število procesorjev. 5. REZULTATI SIMULACIJE simulacija je pokazala, da je najbolj primerna kvadratna oblika procesorskega polja. Takšna oblika omogoča v povprečju krajše razdalje med procesorji in manjšo obremenitev prenosnih poti. Zato smo se pri nadaljnih raziskavah omejili na kvadratna procesorska polja velikosti 2x2,3x3 in 4x4. 10 12 Stev/o procesorjem 8 10 12 StevJo prD«SOr>?m a) sortirani grafi a) sortirani grafi Stevlo processorjev StevJo procaso ;ev b) nesortirani grafi Slika 4. Prime/java po normiranem času izvajanja b) nesortirani grafi Slika 5. Primerjava po času izvajanja Iz slike 3 je razvidno, da se dopustni količnik prenosnega časa spreminja z velikostjo procesorskega polja. Manjše procesorsko polje zahteva nižji, večje polje pa višji dopustni količnik časa prenosa. Dopustni količnik za polje 4x4 za sortiran graf je 6 in za nesor-tiran graf je 12. Pri nadaljnih simulacijah smo se omejili na količnik 10. Slika 4 prikazuje normirano vsoto, ki je podana z razmerjem med Tk fCj ^ pri izbranem načinu razporejanja in Tk (G\ j pri dvonivojskem načinu razporejanja, v odvisnosti od konfiguracije procesorskega polja. Dvonivojski način razporejanja daje v pogledu časa izvajanja najboljše rezultate za konfiguraciji 2x2 in 3x3. Majhno število procesorjev na prvem nivoju razporejanja preprečuje pri enonivojskem načinu širjenje procesov po celotnem polju, medtem ko lahko dvonivojski način razporejanja uporabi vse nezasedene procesorje. Zanimivo je, da na polju 2x2 kaže najslabše rezultate enonivojski način razporejanja z dvostranskim prenosom. Predvidevamo, da so takšni rezultati posledica dodatnega zmanjšanja moči procesiranja zaradi istočasnih dvostranskih prenosov. Dvonivojsko razporejanje pri konfiguraciji 4x4 in nesortiranih grafih daje presenetljivo slab rezultat, kar je posledica dvonivojskega razdeljevanja večjih poddreves. 14 Slevio prooeeo-jev a) sortirani grafi Zasedenost polja kaže slika 7. Največja zasedenost se pojavlja pri dvonivojskem in najmanjša pri enonivojskem načinu razporejanja s prenosom podatkov po dveh zankah hkrati. a) sortirani grafi 10 Noch o) Noch tj) Noch c) Stevfo procescrjev b) nesortirani grafi Slika 6. Primerjava po učinkovitosti polja Sortirani grafi imajo paralehie veje razporejene tako, da se veje, ki zahtevajo daljše prenosne čase, izvajajo na bližjih procesorjih, kar občutno zmanjša prenosne čase. Primerjava med vsotami Tk za sortirane in nesortirane grafe na sliki 5 kaže, da se sortirani grafi izvajajo neprimerno hitreje od nesortiranih. Učinkovitost polja kaže slika 6. Enonivojski način razporejanja s prenosom podatkov po dveh zankah je najbolj učinkovit, dvonivojski način pa najmanj. Izjemoma je pri dvonivojskem načinu razporejanja, nesortiranih grafih, in konfiguraciji 2x2 učinkovitost polja večja. b) nesortirani graf Slika 7. Primerjava po zasedenosti polja 6. ZAKLJUČEK članek predstavlja poskus verifikacije hierarhičnega večprocesorskega sistema, ki je opisan v delu /6/. Verifikacija se opira na simulacijo sistema. Izdelana je analiza delovanja transputerskega polja v odvisnosti od načina razporejanja, velikosti polja in količnika prenosnega časa. Potrjeno je dejstvo, da imajo razdalje med procesorji pomembno vlogo pri prenašanju sporočil. Analiza sistema je pokazala, da je mogoče doseči s krajšimi zankami in večjim številom možnih komunikacijskih poti boljše rezultate. Zato je kvadratna oblika procesorskega polja praviloma boljša od pravokotne oblike. Količnik prenosnega časa naj bo za uspešno izvajanje čim večji, medtem ko je velikost dopustnega količnika ocenjena na 10. Ta količnik pogojuje stopnjo granulacije algoritma, ki se izvaja na transputerskem sistemu. Pri količniku, ki je večji od dopustnega, postane učinkovitost sistema bistveno večja. Obravnavani sistem omogoča več načinov dinamičnega dodeljevanaja procesov. Raziskave učinkovitosti treh predlaganih načinov so dale naslednje rezultate: • Enonivojski način razporejanja procesov s prenosom podatkov po eni zanki je najmanj učinkovit; je najpočasnejši in slabo izkorišča procesorsko polje. • Enonivojski način razporejanja procesov s prenosom podatkov po dveh zankah hkrati ima največjo učinkovitost in najbolje izkorišča dano procesorsko polje, vendar ni tudi najhitrejši. Priporočljiv je v primerih, ko izvajamo na enem procesorskem polju več opravil hkrati in v polje vstopamo sočasno skozi več procesorjev. Izkoristek procesorskega časa je tu najboljši. • Najhitrejše je izvajanje opravil pri dvonivojskem načinu razporejanja procesov s prenosom podatkov po dveh zankah. Cena, ki jo zahteva večja hitrost, se kaže v manjši učinkovitosti procesorskega polja. 7. LITERATURA /1/ L.C.Waring, A general purpose communications shell for a network of transputers, North-Holland, Microprocessing and Microprogramming Vol.29 (1990), 107-119 /2/ A.Ciampolini, A.Corradi, L.Leonardi, Parallel object system support on transputer-based architectures, North-Holland, Microprocessing and Microprogramming Vol.27 (1989), 339-346 /3/ C.Jesshope, Parallel processing, the transputer and the future, Butterworth & Co. (Publishers) Ltd., Microprocessors and Microsystems, Vol.13 No.l, 1989,33-37 /4/ INMOS Spectrum, "Product information, The Transputer Family", March 1988. /5/ C.Jesshope, Transputers and switches as objects in OCCAM, North-Holland, Parallel Computing 8 (1988), 19-30 /6/ P.Kolbezen, P.Zaveršek, Hierarhični večprocesorski sistem. Informatica, A Journal of Computing and Informatics, Vol.15, Nr.l, Feb. 1991, 65-76 /7/ C.Barmon, M.N.Faruqui, G.P.Battacharjee, Dynamic load balancing algorithm in a distributed system, North-Holland, Microprocessing and Microprogramming, Vol.29 (1990), 273-285 /8/ U.De Carlini, U.Villano, The routing problem in transputer-based parallel systems, ButterworthHeinemann Ltd., Microprocessors and Microsystems, Vol.15 No.l, 1991,21-33 OCENJEVANO UČENJE V NEVRONSKIH MREŽAH Andrej Dobnikar, Jelena Ficzko, Keywords: reinforcement learning, Mira Trebar stochastic reinforcennent learning, neural Fakulteta za elektrotehniko in networks računalništvo POVZETEK Ena izmed kategorij učenja v umetnih nevronskih mrežah je ocenjevano (reinforcement, graded) učenje. To vrsto učenja srečamo tudi v bioloških sistemih. V članku je predstavljen stohastični algoritem z ocenjevanim učenjem. Obnašanje algoritma je podano primerjalno za eno samo stohastično enoto, za stohastično enoto v povezavi z back-propagation enoto ter za samo back-propagation enoto, kjer pa je uporabljeno nadzorovano učenje. Čeprav je nadzorovano učenje bistveno hitrejše od ocenjevanega, pa je ta vrsta učenja uporabna tudi v primerih, ko želeni izhodi za vsak vhod niso poznani. ABSTRACT One category of learning methods in artificial neural networks is reinforcement or graded learning. This kind of learning can be met in biological systems also. This paper presents the performance of the stochastic reinforcement learning algorithm. The performance of the algorithm with one stochastic unit and with stochastic unit and back-propagation unit is compared with the performance of the back-propagation unit that is trained using supervised learning. Although supervised learning is much faster than reinforcement learning, the latter can be used even though the desired outputs for every input are not known. I. UVOD Paraleleno strukturo, sestavljeno iz procesnih elementov (ti so med seboj povezani z usmerjenimi povezavami - sinapsami), ki je sposobna specifičnega porazdeljenega procesiranja informacij, imenujemo nevronska mreža. Osnovni gradniki nevronske mreže, procesni elementi, izvajajo procesiranje na osnovi svoje prenosne funkcije, trenutnih vrednosti na svojih vhodih in vrednosti v svojem lokalnem pomnilniku /1/. Pri tem igra pomembno vlogo pravilo učenja, to je pravilo, po katerem se spreminjajo vrednosti v internih pomnilnikih procesnih elementov. Nevronske mreže, ki uporabljajo eno ali več pravil učenja, morajo nujno skozi fazo učenja, ki lahko poteka v obliki : - nadzorovanega učenja (supervised learning) - samoorganizacije (self - organization) - ocenjevanega učenja (graded, reinforcement learning). Pri nadzorovanem učenju mreža potrebuje "učitelja", ki ima nalogo posredovati pravilni izhod za vsak mreži podani vhod. Mreži tako predstavimo pare (xi, yi), i= l,...,n, pri čemer je xi vhod, yi pa pravilni oz. želeni odgovor na xi. Za samoorganizacijo je značilno, da mreža razen vhodov ne potrebuje nobene dodatne informacije, saj ji le-ti zadostujejo, da se na osnovi notranjega pravila sama ustrezno oblikuje. V primerjavi z nadzorovanim gre pri oce-njevanem učenju za drugačno vrsto signala, ki ga mreža dobi v fazi učenja. Namesto vektorja, ki za dani vhod predstavlja želeni izhod, imamo pri ocenjevanem učenju skalarno oceno obnašanja mreže glede na neko mero. Upoštevajoč signal ocene, skuša mreža izboljšati obnašanje v smeri generiranja pravilnih izhodov. Pri ocenjevanem učenju gre tako za dvoje, za iskanje pravilnih izhodov na podane vhode in za pomnjenje pravilnih izhodov. Ker daje skalami signal ocene pri ocenjevanem učenju manj informacije kot želeni izhod pri nadzorovanem učenju, je ocenjevano učenje običajno počasnejše od nadzorovanega, njegove prednosti pa se pokažejo v primerih, ko želeni izhodi niso vnaprej poznani, oziroma ko je kot odgovor na dani vhod možnih več alternativ (npr. pri kontroli sistemov z določeno stopnjo avtonomnosti). II. UČENJE V BIOLOŠKIH SISTEMIH Nevronsko računalništvo, katerega predmet zanimanja so v prvi vrsti nevronske mreže, se je razvijalo tudi pod vplivom nevrologije (znanstvene discipline, ki skuša razložiti delovanje možganov in miselnih procesov), vendar pa v zadnjem času postaja ta vpliv vzajemen. Nove arhitekture nevronskih mrež in novi koncepti ter teorije o delovanju nevronskih mrež pomagajo tudi nevrologiji na njeni poti do odkritja delovanja možganov in procesov v njih. Ocenjevano učenje kot eden izmed treh možnih načinov učenja v umetnih nevronskih mrežah ima svojo "živo" vzporednico. Psihologi so v klasični teoriji učenja postavili vrsto definicij pojma "reinforcement", pri čemer pa so si te definicije v jedru enotne, da gre za operacijo okrepitve, ojačanja , utrjevanja, oziroma za sam dogodek, ki tako ojačanje oz. okrepitev povzroči. Pri tem je to, kar se ojača, običajno naučen odgovor ali pa vez med tem odgovorom in dražljajem /3/. Okrepitev je lahko pozitivna ali pa negativna. Pozitivno okrepitev predstavlja dogodek, dražljaj ali vedenje, ki, kadar je pogojen-o z odgovorom, povzroči povečanje verjetnosti za pojav tega odgovora v bodoče. Nasprotno pa negativno okrepitev predstavlja dogodek, dražljaj ali vedenje, ki, kadar je njegova ukinitev pogojena z odgovorom, poveča verjetnost tega odgovora v bodoče. Glede na to, kakšna je odvisnost okrepitve od nekega vidika odgovora ( ta je lahko prostorski, časovni ali sekvenčni), so psihologi klasificirali okrepitve v tri razrede. V prvem razredu t.i. "enostavnih" okrepitev gre za samo eno vrsto pogojenosti med odgovorom in pojavom okrepitve. V drugi razred spadajo "sestavljene" okrepitve, ki so sekvenčna ali paralelna kombinacija dveh ali več "enostavnih" okrepitev. Okrepitve, ki jih ne moremo uvrstiti v nobenega od prejšnjih razredov, spadajo v razred t.i. "posebnih" okrepitev. Ocenjevano učenje (reinforcement, graded learning) morda ni najboljše poimenovanje za to vrsto učenja, vsaj v takšnem smislu ne, kot to razumejo psihologi. Glede na to, da ime dobro označi to vrsto učenja v umetnih nevronskih mrežah (ocena, kritika, ki okrepi obnašanje mreže v pravi smeri), je to poimenovanje opravičeno. III. STOHASTIČNI ALGORITEM Z OCENJEVANIM UČENJEM Ideja za ta algoritem, ki ga je v osnovi razvil V. Gullapalli /4/, izvira iz teorije učečih avtomatov. Stohastični učeči avtomat je abstraktni stroj, ki akcije izbira naključno po podani verjetnostni porazdelitvi, pri tem pa iz okolja dobiva povratno informacijo, ki predstavlja ovrednotenje akcij. Upoštevajoč povratno informacijo, avtomat ažurira verjetnostno porazdelitev za akcije tako, da poveča verjetnost za pozitivno ovrednotenje akcij v bodoče. Učeči avtomat deluje v povratni povezavi z okoljem, ki v času t pripelje na vhod avtomata vektor x(t). Odgovor avtomata y(t) je naključno izbran glede na verjetnostno porazdelitev na intervalu YcR. Signal ocene r(t)£ R= 0,1 , ki ga generira okolje, predstavlja oceno odgovora y(t) v kontekstu vhoda x(t). Cilj učečega avtomata je naučiti se odgovarjati na vsak vhodni vektor X s takšnim odgovorom y, da bo ocena, ki jo bo za ta odgovor prejel od okolja, maksimalna. Opisani stohastični avtomat se implementira kot stohastična enota (slika 1), ki nastopa kot komponenta v mreži. r(t: JL azur. utezi -1- y(t) izhodna funkcija a(t) gen. nak1j. števil Pl (t) JÄ ^ > izračun param. - t) slika 1 Vhod v enoto v času t je x(t) = (xi(t), x2(t),...,xn(t)), ki se uporabi za izračun parametrov pi(t), p2(t),..., pm(t) verjetnostne porazdelitve, po kateri se naključno generira aktivnost enote. Parametre porazdelitvene funkcije lahko dobimo od zunaj ali pa so določeni kot utežena vsota vhodov, z različnim naborom uteži za vsak parameter. Aktivnost enote je tako naključna spremenljivka porazdelitve, določene s parametri pi(t),...,pm(t). Izhod iz enote y(t) je funkcija aktivnosti y(t) = f(a(t)), pri čemer je funkcija f (pragovna funkcija, logistična funkcija) izbrana glede na vrsto izhoda, ki ga želimo. Za implementacijo dcločenega stohastičnega algoritma učenja je potrebno tako določiti : 1. porazdehtev, ki se uporabi za generiranje naključnih vrednosti aktivacije 2. funkcije, ki se uporabijo za izračun parametrov porazdelitve 3. izhodno funkcijo f 4. pravila za ažuriranje uteži V članku je predstavljen algoritem stohastičnega ocenjevanega učenja za učenje funkcij z realnimi izhodi. Za generiranje aktivnosti enote se uporabi normalna porazdehtev ^ (//, ct) . Izhod iz enote, ki je realna vrednost, je zvezna, monotona funkcija a' ^0, f vala .ktivnosti. Signal ocene je iz inter. Trenutni vhodi v enoto določajo srednjo vrednost in standardno deviacijo porazdelitve, na podlagi katere se naključno generi»-« aktivnost enote. Učenje poteka v smislu ažuriranja parametrov normalne porazdelitve (standardne deviacije in srednje vrednosti) v smeri povečanja verjetnosti za generiranje optimalnega izhoda za vsak vhod. Pri tem je srednja vrednost n ocena za optimalno aktivnost, standardna deviacija a pa določa obseg iskanja okrog trenutne srednje vrednosti aktivnosti enote. Ker naj bo srednja vrednost porazdelitve fi ocena za optimalni izhod, izračunamo n kot uteženo vsoto vhodov : 56 Al Aw(t) = (r(t) - r(t)) a(t) i=l Za dani vhod naj bo st.deviacija a odvisna od tega, kako blizu je trenutni pričakovani izhod optimalnemu izhodu za ta vhod. Mera za to pa je signal ocene iz okolja. Za dani vhod je tako st.deviacija a odvisna od pričakovanega signala ocene, ki ga prav tako dobimo kot uteženo vsoto vhodov : n r(t) = S^iWxi(t)+Vprag(t) i=l Pričakovani signal ocene uporabimo za izračun st.deviacije : f^(t) = s(r(t)), kjer je funkcija s monotono padajoča nenegativna funkcija pričakovanega signala ocene. Na osnovi a(t) in /^(t) se izračuna aktivnost a(t) kot naključna spremenljivka normalne porazdelitve: Izhodna funkcija f preslika aktivnost enote a(t) v izhod enote y(t) : Pravila za ažuriranje uteži, ki določajo st.deviacijo : vi(t+l)=vi(t)+^Av(t)xi(t) Vprag(t+l)=Vprag(t)+;3Av(t) Av(t) = r(t) - r(t) Pri tem sta a in parametra učenja. Osnovni cikel učenja poteka po naslednjih korakih : 1. okolje poda enoti vhodni vektor xi(t), i = l,...,n 2. enota uporabi vhodni vektor za izračun srednje vrednosti fi(t) (uporabijo se uteži wi(t) in wprag) 3. enota izračuna pričakovani signal kritike r(t), ki ga uporabi za izračun a(t) (pri tem se uporabijo uteži vi(t) in vprag) 4. enota izračuna aktivnost a(t)^^(//(t),a(t)) in izhod y(t) = f(a(t)) 5. okolje ovrednoti izhod in odpošlje signal ocene r(t) 6. r(t) omogoči ažuriranje uteži IV. OBNAŠANJE ALGORITMA y(t) = f(a(t)), pri čemer je f(x) = 1 + e -X Pravila za ažuriranje uteži, ki določajo srednjo vrednost: wi(t+l) = wi(t) + a Aw(t) xi(t) Wprag(t+1) = Wprag(t) + a Aw(t) Delovanje algoritma je preizkušeno na več opravilih, ki so definirana kot množica parov "dražljaj - odgovor" iz f O, ll x ( 0,1). Za vsa opravila se je uporabila najprej samo ena stohastična enota (slika 2), nato stohastična enota v povezavi z back-propagation enoto (slika 3) in primerjalno še ena sama back-propagation enota (učenje te enote je potekalo v obliki nadzorovanega učenja s parametrom učenja 0.1). Hitrost konvergence za vse tri.primere je razvidna iz grafov (slike 4,5 in 6). Xj(t) V' slika 2 slika 3 Delovanja algoritma v pri^ierih ene stohasf "e enote Ob začeiku učenja so vse uteži enote postavljene na O, vrednosti parametrov učenja pa so a = 0.5 in /3 = 0.7. Na vhod enote pripeljemo v vsaki fazi učenja vse vhodne vektorje v naključnem vrstnem redu, pri tem pa se osnovni cikel učenja ponovi za vsak vhodni vektor. Ob koncu točke 4 osnovnega cikla učenja se izračuna napaka kot razlika med dejanskim in želenim izhodom, ki se uporabi za določitev signala ocene. Sledi ažuriranje uteži. Učenje poteka tako dolgo, dokler povprečna napaka ne pade pod določeno mejo, oziroma po preteku določenega števila ciklov učenja. 0.25 C3 M a, C ca C 0.3 in (0.8, 0.3) - > 0.7 Slika 4 CTS d ex rt C rt C 0.3, (0.1, 0.3) - > 0.6 in (0.6, 0.2) - > 0.9. Slika 5 Signal ocene iz okolja je določen kot : r(t) = 1 - napaka pri tem je napaka <= 1. Delovanja algoritma v primerih stohastične in back-propagation enote Hibridna mreža, sestavljena iz stohastične izhodne enot in enote v skritem nivoju, ki je tipa back-propagation, izkazuje boljše obnašanje kot ena sama stohastična enota. V taki mreži se kot aproksimacija napake na izhodu uporabi vrednost Aw(t). Poleg tega se osnovnemu ciklu učenja doda še korak, kjer se izraz Aw(t) iz izhodne enote propagira nazaj kot napaka na skrito enoto in s tem omogoča ažuriranje uteži back-propagation enote. Ob začetku učenja so uteži za back-propagation- enoto postavljene naključno, za stohastično enoto pa so O, parameter učenja za stohastično enoto ß = 0.7, parameter a pa je postavljen različno za povezave na vhode a = 0.5 in za povezave na skrito enoto a = 0.1. Parameter učenja za back-propagation enoto je 0.1. V vsaki fazi učenja se na mrežo pripeljejo vsi vhodni vektorji, za vsakega se ponovi osnovni cikel učenja. Signal ocene je določen enako kot v primeru ene stohastične enote. V. ZAKUUČEK Rezultati so pokazali, da stohastična enota, povezana z back-propagation enoto izkazuje boljše obnašanje kot ena sama stohastična enota. Ta razlika je sicer v nekaterih primerih (slika 6) majhna. Kl Oh rt C rt Cl >(j 0.1, (0.1, 0.9)-> 0.1, (0.9, 0.1)-> 0.1 in (0.9, 0.9)-> 0.9. Slika 6 Konvergenca učenja v primeru ene same stohastične enote in stohastične enote, povezane z back-propagation enoto, je bistveno počasnejša od konvergence učenja pri back-propagation enoti. Faktor, ki vpliva na obnašanje vseh sistemov, ki se učijo z ocenjevanim učenjem, je kvaliteta signala ocene iz okolja. Zato lahko včasih izboljšamo obnašanje mreže, če v signal ocene vgradimo več informacije, ki je specifična za neko opravilo. Literatura: /1/ Robert Hecht-Nielsen, Neurocomputing, Addison-Wesley, 1990 /2/ Hinton, Connectionist Learning Procedures, Artificial Intelligence 40,1989 /3/ Dictionary of psychology, /4/ V.Gullapalli, A Stochastic Reinforcement Learning Algorithm for Learning Real-Valued Functions, Neural Networks, Vol.3,1990 /5/ R.A Leaver, P. Mars, Stochastic Computing and reinforcement neural networks. Conference on Artificial Neural Networks, London, 1989 DIGITALIZACIJA IN VEKTORIZACIJA ČRTNIH RISB VELIKIH DIMENZIJ Keywords: image analysis and processing, pattern recognition, vectorization, GIS A. Dedić R. Murn D. Peček INSTITUT JOŽEF STEFAN LJUBLJANA Odsek za računalništvo in informatiko Programska orodja in aplikacije, ki tečejo na sodobnih računalniških sistemih omogočajo zajem, uporabo in upravljanje prostorsko porazdeljenih podatkov. Zaradi velike količine podatkov, mora biti vnos hiter in učinkovit. Avtomatski vnos grafičnih podatkov nam omogočajo postopki za natančno digitalizacijo in vektorizacijo grafičnih predlog, ki so narisane na papirju in njemu sorodnih medijih.V delu so proučeni postopki za digitalizacijo in vektorizacijo črtnih risb velikih dimenzij. Na osnovi ovrednotenja teh postopkov in zahtev uporabnikov so izdelani osnovni pogoji za kakovostno in hitro digitalizacijo grafičnih predlog in transformacijo rasterske slike v vektorski zapis. To so: natančnost postopka, uporabnost rezultata in hitrost. Izdelan je lasten postopek za digitalizacijo in vektorizacjio, ki optimalno izpolnjuje navedene pogoje. ÜIGITALIZATION AND VECTORIZATION OF LARGE SCALE DRAWINGS AND MAPS Modern programing tools and applications running on up-to-date computer systems enable efficient managing of spatial distributed data. Due to enormous amount of image data, graphic data input must be extremely fast and reliable. In the paper raster to vector conversion techniques are discussed. There are Iwo basic requests: usefulness of the result, and the speed of data acquisition. Dedicated raster to vector converter is shown. Uvod človeški rod je že od pradavnine iz različnih razlogov zbiral podatke o svojem okolju. Težišče tega zbiranja so bili v glavnem geografski in topografski podatki. V 19. stoletju so bila prvič izvedena triangulacijska dela kot osnova novih kartografskih projektov. Prav tako se začne razvijati sistem zemljiškega katastra. V našem stoletju je stekel razvoj še mnogo hitreje. Nasprotno od hitrega razvoja tehnik pridobivanja podatkov o prostoru je tehnika hranjenja teh podatkov napredovala le počasi. Od kamnitih plošč, papirusa je prišel papir, ki se je obdržal do današnjih dni. V zadnjih dveh dekadah se za shranjevanje in obdelavo podatkov nezadržno širi uporaba računalniške tehnologije. Razvili so računalniški sistemi, ki zagotavljajo učinkovito zbiranje, vodenje, povezovanje in vrednotenje geometrijskih podatkov o okolju. Take sisteme imenujemo Geografski Informacijski Sistemi (GIS). Zajemanje podatkov je časovno in finančno najzahtevnejša komponenta GIS-ä. Po nekaterih podatkih je delež vnosa podatkov 80 odstotkov celotne investicije. Poleg vseh ostalih zahtev zajemanja, kot sta hitrost in enostavnost, je bistveni pogoj pri zajemanju ohranjanje izvorne natančnosti podatkov. Sodobna tehnologija omogoča relativno enostavno in hitro zajemanje analognih grafičnih predlog (kart, map) z pomočjo posebnih linijskih kamer, in pretvorbo v digitalno obliko. Rezultat se shrani v računalnik v rasterski obliki. Članek obravnava pretvorbo rasterskih slik v vektorsko obliko. Definicija problema Digitalno sliko, lahko v rasterskem zapisu enostavno in hitro prikažemo na računalniškem zaslonu. Vendar ta oblika zapisa ne nosi informacije o vsebini grafične predloge. Vektorski zapis (vektorska slika) grafičnih podatkov je primerna za računalniško obdelavo in nosi strnjen opis vseh informacij o grafični predlogi, ki jo ponazarja. Zato je potrebno razviti ustrezen računalniški postopek za transformacijo rasterskih podatkov v vektorske. Transformacija mora izpolnjevali nekatere zahteve. Najvažnejše je, da se ohrani izvorna natančnosti podatkov, saj je njihova vsebina informacija o metriki prostora, kije zakonsko predpisana. Računalniški postopek mora omogočati enostaven, hiter in natančen vnos podatkov iz grafičnih predlog v računalniško podprt geografski informacijski sistem [1,2,3], Celotni postopek je razdeljen na dva zaporedna, smisleno in programsko ločena dela: a) digitalizacija črtnih risb velikih dimenzij, b) vektorizacija dobljenih podatkov. Prvi del vsebuje opis problematike digitalizacije grafičnih predlog velikih dimenzij. V drugem delu so detaljno analizirane zahteve za transformacije podatkov iz rasterskega v vektorski zapis. Digitalizacija črtnih risb Pod pojmom "digitalizacija" razumemo proces zajemanja črtnih risb z ustrezno kamero (linijsko - enodimenzijsko ali ploskovno - dvodimenzijsko) in transformacijo analognih zajeia vrstica analogni Signal I i t I I 1 I I » 1 t I i I I I iii, ^ vzorčevalni signal digitalni signal digitalni podatki Slika 1. Analogni signal in digitalni podatki signalov (podatkov) v digitalno obliko. Taki transformirani digitalni podatki so primerni za obdelavo in za hranjenje v digitalnem računalniku. Transformacija zveznih analognih signalov v analogne vzorce se izvaja z elektronskim vezjem v kameri. Analogne signale vzorčimo v predpisani frekvenci in določamo digitalno vrednost vzorcev v odvisnosti od amplitude (Slika 1). Število digitalnih razredovje ponavadi iN-ta potenca števila 2. Značilne vrednosti za N so 1, 4, 6, 8, ... . Najvišji amplitudi odgovarja najvišji digitalni razred in najnižji amplitudi, najnižji razred. Vse vmesne amplitude se zaobkrožijo navzdol na ustrezni razred. Za črtne risbe večjih dimenzij (standardni formati^12, Al, AO in večji) je značilno, da z današnjo tehnologijo ni možna enostavna in cenovno dostopna digitalizacija z dvodimenzijsko kamero zaradi premajhne ločljivosti ustreznih senzorjev. Za te namene se je uveljavila uporaba ustrezno prirejenih linijskih kamer. Na tržišču je uveljavljen izraz "SKENER"; imenovali ga bomo "linijski digitalizator". Z linijskim digitalizatorjem lahko digitaliziramo grafične predloge, ki so omejene z fizično širino linijskega senzorja (ponavadi več kot en meter) in teoretično neomejene dolžine. Dolžina je omejena z velikostjo pomnilnika v računalniku v katerega se zapisujejo podatki iz digitalizatorja. Važen podatek za linijski digitalizator je ločljivost zajemanja. Standardne ločljivosti so 100, 200, 300 in 400 točk na inčo (dots per inch - DPI). Novejši digitalizatorji dosežejo do 600 DPI. Za potrebe aplikacij katerih cilj je zapis segmentov iz grafične predloge v matematični obliki (vektorizacija), je najbolj ugodno, če je slika zapisana v dveh nivojih: belo za ozadje slike in črno za črte na sliki. Črtne risbe, ki so najbolj zanimive in so vplivale na razvoj magistrske naloge so: • katasterske mape standardnih meril, • geografske mape različnih meril, • geodetske, gozdarske, elektrovodne, komunalne, in dnige mape, • inženirski načrti vseh vrst in • dntge grafične predloge, ki so izrisane z črtami kakršne koli oblike. Črtne risbe so največkrat risane v eni barvi na kontrastni podlagi. Obstajajo tudi take, ki so risane v več barvah, vendar na različnih slojih - prozornih folijah, kar obravnavamo kot več različnih, enobarvnih predlog. Za starejše tipe grafičnih predlog, ki so risane v več barvah na eni sami podlagi lahko uporabimo barvne filtre pri digitalizaciji (barvna separacija), tako da dobimo več različnih enobarvnih predlog. To je značilno za veljavne katasterske načrte iz obdobja Marije Terezije. Takšni načrti še zmeraj pokrivajo približno 80 procentov površine Republike Slovenije. Osnovni problem pred vsebinsko obdelavo digitalizirane slike je pravilen izbor algoritmov (izbor uveljavljenih in/ali izdelava novih). Kompleksno sliko je namreč potrebno razbiti na eno ali več homogenih površin, ki opisujejo posamezne logične nivoje. Ta problem imenujemo segmenlizacije ali razčlenjevanje slike. Popularna metoda segmentizacije slike je "rezanje" slike na enem sivinskem nivoju (image thresholding). Ta, metoda je računsko bolj enostavna in hitrejša kot drugé niietode za segmentizacijo (odkrivanje robov na sivinski sliki z različnimi operatorji ali razne tehnike, ki slonijo na odkrivanju homogenih področij na sliki). Metoda rezanja slike je v bistvu metoda iskanja optimalne PRAGOVNE vrednosti. Tako na enostaven način dobimo uporabno dvonivojsko sliko. V splošnem primeru je ta metoda dosti bolj zahtevna, če so črte na sliki, ki jih je treba segmentizirati v različnih sivinah (npr. N sivin) in je zato potrebno poiskati več ustreznih pragovnih vrednosti (N - TLd. segmentizacijp kakovostnih črtnih risb je zadostna in potrebna predstavitev z dvemi nivoji, črno - belo. V teh primerih kaže tudi histogram sivinskih vrednosti izrazito dvopasovno obliko: pas, ki odgovarja točkam na črtah in pas, ki odgovarja točkam ozadja (Slika 2). Na tak način lahko sliko / segmentiziramo na dva dela tako, da upoštevamo razmerje sivinskih vrednosti G(x,y) proti eni sivini T. Vrednost 7-ja leži med maksimumom sivin črt in maksimumom sivin ozadja. Ta enostavni kriterij za vse točke slike / se da predstaviti kot: • če je G(x,y) >= T potem je točka iz skupine črt ali skupine 1, • sicer je točka iz skupine točk ozadja ali skupine 2. Vrednost T imenujemo pragovna vrednost (threshold), postopek pretvorbe slike iz večsivinskega zapisa v dvonivojski pa binarizacija. 5000 80 Sivine 'n' (0-63) Slika 2. Histogram kontrastne črtne risbe kaže izrazito dvopasovnost Digitalizacija in binarizacija pripravi sliko za nadaljno obdelavo, v našem primeru vektorizacijo. Kakovost digitalizacije in binarizacije vpliva na rezultat vektorizacije črtne risbe (ne glede na uporabljeno metodo vektorizacije) [4,5]. Linijski digitalizator omogoča nastavitev pragovne vrednosti za binarizacijo grafične predloge. Kakovost tako dobljenih binarnih slik je zadovoljiva samo za del novejših črtnih risb, ki so risane na posebnih predlogah s stabilnimi, kvalitetnimi peresi. Dobljeni rezultati za ostale črtne risbe so slabši. Razlog je pragovna vrednost, ki je nastavljena globalno, enotno za celo grafično predlogo, ne glede na spreminjanje odtenkov sivine narisanih črt po celi sliki in spreminjanje odtenkov barve papirja kot ozadja [6]. Na slabšanje rezultatov vplivajo: • slaba kvaliteta papirja, ki s staranjem spreminja barvo, • če je papir izrabljen, izdrsan (izdrgnjen), umazan na kakršen koli način, lepljen z neustreznimi lepili (selotejp trakovi), • če je risan z slabimi peresi z nestabilnim črnilom, ki s časom spreminja barvo, ali s preveč vodenim črnilom. Te slabosti se kažejo na digitalni, globalno binarizirani sliki kot: • črte so neenakomerno debele, na enem mestu pretanke, drugje predebele, • prekinjene črte ali jih sploh ni, • na mestih, kjer je gostota črt zelo velika (naselja, križišča), so črte odebeljene, ponekod zlite v črne ploskve. Vse metode iskanja pragovne vrednosti za digitalno, večsivinsko sliko lahko v splošnem razdelimo na dve skupini: • metode iskanja globalne pragovne vrednosti (global threshold selection) in • metode iskanja spremenljive (lokalne, dinamične, spremenljive) pragovne vrednosti (variable threshold selection ). S prvimi določimo za celo sliko enotno pragovno vrednost. Ostale metode določajo pravila, po katerih se pragovna vrednost spreminja po sliki od točke do točke. Lastna metoda (variabilno načelo [7]) Pragovna vrednost Tn se za vsako točko n računa kot: P2 P3 P4 Pl Po Ps Pb P7 Pe Slika 3. Oznake indeksov sosednjih točk Tn = [ Cn an +, /1 = 1,2,3,...,/^ N je število vseh točk na sliki / , ^n je srednja vrednost tekoče točke in njenih osmih sosedov (Slika 3). (i =0,1,...,8) On je standardno odstopanje devetih točk od srednje vrednosti On ^ (,.0,1,...,8) Koefieijentu Cn smo dali ime "pragovni koeficijent" in je odvisen od histograma cele slike H(n): ^n - ^ Koeficijentu Cn smo dali ime "pragovni koeficijent" in je odvisen od histograma cele slike H(n): H(n)\e število točk, ki imajo sivinsko vrednost n na celi sliki /. Vrednost k je konstanta. Dodali smo jo za izboljšanje rezultatov inje odvisna od kvalitete načrta. Konstanta/c se določa z izkušnjo in ima vrednost med 1 za boljše predloge in 0.65 za slabše. Vektorizacija črtnih risb Črtna risba, ki je digitalizirana in binarizirana, je pripravljena za glavni del obdelave, vektorizacijo. Pod pojmom "vektorizacija" razumemo transformacijo zapisa črte iz rasterskega v vektorski zapis in jo imenujemo tudi "rastervektor" transformacija. Rasterski zapis črt je digitalizirana in binarizirana slika teh črt (Slika 4). Omejimo se samo na pravokotno rastersko mrežo, ki je zgrajena iz kvadratnih raslerskih celic (obstoja tudi heksagonalna, itd). (40,55) (48,61) Slika 4. ' Digitalizirana črta v dveh ločljivostih 1 in 2: (a) Narisana črta na papirju, (b) rasterska slika črte v različnih ločljivostih, (c) vektorski zapis črte . V našem primeru vektorski zapis definiramo kot matematičen opis črte z dvema končnima točkama, koordinatami v dvodimenzijskem, x - y prostoru. Z inverzno preslikavo "vektor - raster" se pogosto srečujemo v računalniškem okolju, koje potrebno črte, ki so zapisani v vektorski obliki, izrisati na neko rastersko podlago (računalniški monitorji, matrični tiskalniki itn). Matematične črte nimajo debeline, pri rasterski predstavitvi pa jim jo moramo prirediti - najmanj eno slikovno celico. Idealno rastersko sliko neke črtne risbe dobimo, če so znani vsi vektorji na tej risbi in jih izrišemo na rasterski podlagi z omenjenimi algoritmi. Preslikava nazaj, iz idealne rasterske slike v vektorsko, je enolična samo, če je znan algoritem po katerem je potekala preslikava v prvi smeri. Razlog je v tem, da lahko skozi rastersko črto, debelo eno ali več celic, povlečemo neskončno mnogo vektorjev. Digitalizirana in binarizirana slika črtne risbe je rasterska slika, ki ni idealna. Položaj vektorjev na risbi seveda ni znan, saj je bistvo vektorizacije prav odkrivanje le-teh. Torej, ta preslikava ni enolična. Iz ene rasterske slike lahko dobimo neskončno mnogo različnih, medseboj podobnih vektorskih slik. Da bi to število zmanjšali, oziroma preslikavo čim bolj poenotili, lahko postavimo različne zahteve, kijih morajo izpolnjevati dobljene vektorske slike. Večina črtnih risb, ki jih obdelujemo, vsebuje metriko o prostoru, ki ga predstavljajo. Iformacije o tem prostoru (ali večina le-teh) so v narisanih črtah na papirju. To pomeni, da bo vsaka, še tako majhna napaka pri transformaciji pomenila popačenje v novi vektorski predstavitvi prostora. Primer tega je katasterski načrt, na katerem so narisane zemljiščne parcele. Davek na zemljo je odvisen od površine parcele. Površina večjih parcel se vidno spreminja pri še tako majhnem premiku dolgih mej - črt. Velja da originalna črtna risba ne vsebuje idealne metrike o prostoru temveč samo približek. Zato je splošna zahteva pri vektorizaciji, da se dobljena vektorska slika čim bolj ujema z rastersko. Kakovost vektorizacije je odvisna od uporabljene metode. Preučili smo in testiral vse dostopne metode iz literature [8-11 ] in kot rezultat tega in zahtev uporabnikov postavili lastne zahteve za pogoje vektorizacije. Na osnovi teh zahtev in upoštevajoč delne rešitve iz omenjene literature, smo izdelal lastno metodo za vektorizacijo. V nadaljevanju najprej sledi pregled nekaterih bolj zanimivih in pogostejše uporabljenih metod vektorizacije. Pregled postopkov Velika večina postopkov vektorizacije črtnih risb uporablja kot prvi korak (ali predobdelavo) različne metode za tanjšanje črt na rasterski sliki na debelino ene rasterske celice (Tabela 1). Razlog za tako široko uporabo te predob-delave je v tem, da so postopki za nadaljno obdelavo teh črt, debelih samo eno celico, že razviti in obdelani znotraj postopkov, ki so namenjeni za druge različne potrebe. Večinoma so to različne metode iskanja in izločevanja črt in črtnih oblik kot so: • operatorji za iskanje robov objektov na sliki, • kontumi filtri, • sledenje roba objekta na sliki (border tracking), • algoritmi za odkrivanje linijskih segmentov na sliki itn. Zato bi lahko v splošnem vse postopke za vektorizacijo razvrstili v dve skupini: • skupina A: tiste, ki kot prvi korak pri obdelavi uporabljajo različne metode za tanjšanje rasterskih črt • skupina B : tiste, ki slonijo na vektorizaciji rasterskih črt originalne širine. POSIOPKI VEKTORIZACIJE OPKl kupine a , kohak stwjäevanje .ALGORirw ZA I SIArtJSEVAfJJE n t- MERJENJE OOWUENOSIt . HOUCH-OV TRAIßfORW 2. «O«« J ISKANJE vu<10flxv j . NAJDALJŠI UNIJSXI SECuoni t_ ekaki linusxi segmenti 1. KDRAK: OOKRr/ANjE SKRAJSAN»! \tKrORJEV 2. KORAK: GRADNJA KRlZlSC - I.Oa y KORAK: GRADNJA KRI^lSC - 2.Da . 4. KORAK: DSLIKOVANJE KRlZlSC Tabela 1. Razvrstitev postopkov za vektorizacijo Merila za vrednotenje postopkov za vektorizacijo Da bi lahko ovrednotili postopke vektorizacije, moramo najprej določiti merila. Na prvem mestu so to zahteve ljudi iz stroke, ki bodo uporabljali programske rešitve za vektorizacije. Za vrednotenje smo izbrali tri osnovna merila: 1. natančnost metode, 2. uporabnost dobljenega rezultata, 3. časovna zahtevnost postopka. Po prvem merilu vrednotimo natančnost dobljenih rezultatov (ujemanje vektorskih črt z rastersko sliko). Minimalna zahtevana natančnost je, da vektor leži znotraj točk črte na rasterski sliki. Drugo merilo so zahteve in želje uporabnikov. Naše izkušnje so pokazale, da zaenkrat ni mogoče implementirati univerzalnega algoritma, katerega rezultat bi bil sprejemljiv za različne vrste uporabnikov. To pomeni, daje potrebno vektorizacijske algoritme prilagoditi vsakemu uporabniku posebej. To se največkrat da doseči z nastavljanjem različnih parametrov vektorizacijskega procesa. Pomembno je tudi tretje merilo. Zaradi izredno velikega števila risb, ki jih je treba obdelati, morajo biti postopki prilagojeni. Posebej še, če naj ti algoritmu tečejo na cenenih računalnikih tipa IBM PC. Izpolnjevanje vseh treh pogojev je potreben in zadosten pogoj za kakovostno vektorizacijo. Lastni postopek za vektorizacijo Osnovno vodilo in smernice pri izdelavi lastnega sistema za vektorizacijo so bili trije osnovni pogoji. Prva ugotovitev je bila, daje potrebno celotni postopek razbiti v več enostavnejših korakov. Iskanje postopkov s katerimi bi v enem prehodu dobili uporaben končen rezultat ne daje zahtevanih rezultatov. 1. KORAK: Odkrivanje skrajšanih vektorjev Osnovni problem vektorizacije je ogromna količina podatkov, ki jih je treba obdelati. Na primer: za črtno risbo dimenzije 800 x 700 mm (katasterski načrt), ki je digitalizirana,z ločljivostjo 600 DPI dobimo 320 milijonov črno belih točk ali 40 Mby (Mega zlogov) podatkov. Z zapisom podatkov v kodah tekočih dolžin dosežemo faktor kompresije približno 5, to je 8 Mby. To je še vedno veliko, vendar bistveno lažje za obdelavo. Postopek vektorizacije mora zaradi ogromne količine podatkov teči na komprimirani sliki. Zapis v obliki kod tekočih dolžin je zelo ugoden, ker je komprimiran in ima obliko iz katere se hitro ugotovi potek rasterskih črt. Zato je tak zapis rasterske slike osnova za lasten postopek vektorizacije. Obdelava rasterske slike mora teči zaporedno, od enega konca k drugemu. To je v skladu z zapisom slike. Kakršna koli obdelava v naključni smeri (recimo: sledenje rasterski črti po sliki) je časovno zelo zahtevna. Zato smo za prvi korak izbrali obdelavo slike v eni smeri: od zgoraj navzdol (vrstico za vrstico). S tako obdelavo občutno zmanjšamo število posegov računalnika do zunanjih enot na katerih je slika zapisana (trdi disk). Za zapis rasterske slike v kodah tekočih dolžin je karakteristično, da so za vsako vrstico zapisane dolžine nizov izmenično črnih ali belih točk. Tem podatkom rečemo črna ali bela polja. Ko pri obdelavi slike naletimo na prvo vrstico, ki ni prazna, ■•plšc iio v posebna polja podatkov, vsako črno polje posebej, V teh poljih vodimo evidenco o začetih črtah {SliKa S.A). Za vsako naslednjo vrstico navzdol (tekoča vrstica) testiramo vsako začeto črto posebej, če se nadaljuje z enim izmed črnih polj v tej vrstici. Če se črta nadaljuje, potem testiramo naslednje pogoje po vrsti (če je eden izmed pogojev izpolnjen, ne testiramo naprej): a) če je črno polje s katerim se črta nadaljuje tudi nadaljevanje za eno ali več sosednjih začetih črtah (Slika 5.D), h) če v tekoči vrstici obstoja še eno ali več črnih polj, ki so nadaljevanje testirane začete vrstice (Slika 5.C), Če so lesti a) in b) negativni potem: c) povlečemo ravno črto od sredine prvega črnega polja testirane črte do sredine zadnjega črnega polja (za katero je črta podaljšana). Testiramo, če eno izmed črnih polj vmes odstopa od narisane črte za več, kot je predpisano odstopanje /-o. Obstajata dve možnosti: ci) če je narisana črta znotraj vseh prejšnjih črnih polj, potem v polje podatkovo tekoči črti dopišemo zadnje črno polje (Slika 5.E) , C2) če celotna črta ni znotraj vseh črnih polj, potem začelo črto končamo s črnim poljem v prejšnji vrstici in začnemo novo s črnim poljem v tekoči vrstici (Slika 5.F). Če je pogoj a) pozitiven (to je slučaj, če se testirana črta deli v eno ali več novih črt), potem se tekoča črta konča (kol črta od njenega začetka do črnega polja prejšnje vrstice) in se začne evidenca o eni ali več črtah z začetkom v tekoči vr'^tlci. Za uspešno vektorizacijo črtnih risb, ki vsebujejo metriko o prostoru je ključnega pomena natančno identificirati vektorje naris mih črt, oziroma koordinate dveh končnih točk vsake posamezne črte (vsaka črta je enolično definirana s svojima končnima točkama). Če je črta samostojna (prosta na obeh koncih), potem končne točke ni ležko določiti. Problem je, da so večinoma ti dve točki v vozliščih treh ali večih črt (črte se združujejo ali razdružujejo v vozliščih). Zelo težko je natančno določiti koordinato posameznega vozlišča oziroma eno končno točko vseh črt, ki so združene v vozlišču. Na osnovi tega smo prišli do večkoračne rešitve: v prvem koraku vse črte skrajšamo za del, ki leži v vozlišču, (črte vektoriziramo samo do vozlišča). S postopki v naslednjih korakih še oblikujemo vsa vozlišča. , Tekoča vrstica i Slika 5. Prvi korak vektorizacije V primeru b) (slučaj, da se ena ali več prej začetih črt združuje v eno novo) se v prejšnji vrstici konča ena ali več začetih črl in se začne evidenca o novi črli z začetkom v tekoči vrslici. Če sc ena izmed črt ne nadaljuje v tekoči vrstici (niso iz])olnjeni [logoji za nadaljevanje), se le-ta konča v prejšnji vrstici (Slika 5.B). Polja podatkov v katerih smo vodili evidenco o končanih črtah sproti sproščamo. Koordinate vseh končanih črt (vektorje) shranimo na posebno datoteko. Pri shranjevanju se lahko rešimo nepotrebnih kratkih vektorjev, ki večinoma predstavljajo vektorizirane napise in simbole na grafičnih predlogah. Če je vektor krajši od najkrajše vnaprej določene dolžine r\, potem ga ne shranimo (Slika 5.H). V vsakem križišču po prvem koraku, ostanejo luknje (Slika S). V prvem koraku križišč ne gradimo. To je v bistvu osnovna ideja, na kateri je bil zasnovan celoten postopek: S testiranjem navedenih pogojev v prvem koraku: a), b), in cj hitro in enostavno odkrivamo vozlišča. Postopek v prvem koraku je učinkovit, ima pa pomanjkljivost. Preciznost odkrivanja skrajšanih vektorjev je odvisna od kota pod katerim je narisana črta. Za kote od 45 do /J5 stopinj (navpične črte) je natančnost zelo velika. Za kote od -45 do 45 stopinj (horizontalne črte) natančnost ni zadovoljiva (Slika 5.G). Za rešitev tega problema smo našli enostavno in učinkovito rešitev. Rasterska slika, ki je zapisana s kodami tekočih dolžin, se prepiše v popolnoma enako novo sliko; samo je zapis kod za novo sliko drugačen. Pravila za zapis kod ostanejo ista, vendar se kode ne pišejo več po vrsticah, temveč po stolpcih, z leve proti desni. Slika vsebuje kode, ki so zarotirane za 90 stopinj. Za novo, rotirano sliko isti postopek ponovimo. Vektorje vertikalnih črt originalne slike bomo dobili, če upoštevamo samo črte, ki so pod kotom od 45 do 135 stopinj (prvi del prveg koraka - obdelava nerotirane slike) (Slika 6). Vektorje horizontalnih črt dobimo če upoštevamo samo črte, ki so pod kotom od 45 do 135 stopinj, pri obdelavi rotirane sliki- (to so vektorji črt, ki so na originalni sliki pod kotom od- 5 dostopinj) C^/Z/cw ó^. Celotna vektorizirana slika [/je unija teh dveh podslik 1^(45,135) in ^(^5,45). Prvi korak lahko ponazorimo z dvema preslikavama iz rasterskega R v vektorski prostor V\ R -^ 1^(45,135) R "-► ^'(-45, 45) y = [^(45, 135) U ^'(-45,45) mo^.nost podvojitve vektorjev zato, ker jc lahko npr. črta, ki je pod kotom 45 stopinjah vcktorizirana na ncroUrani in tudi na rotirani sliki. Zato v drugem koraku vse '"ktorje , ki so približno pod koloma 45 in 135 stopinj na lerotirani sliki, testiramo če so enaki (s predpisanim odstopanjem) na rotirani sliki. V slučaju obstoja takih parov odstranimo po eno črto iz para. S tem je predobdelava vektorjev v drugem koraku končana. V glavnem delu drugega koraka testiramo vsak vektor, če obstaja v njegovi vnaprej določeni bližini, n konec drugih vektorjev. To je večinoma slučaj na mestih preskočenih vozlišč, združevanja dveh ali treh črt in redkeje štirih ali več. V primeru pozitivnega testa, podaljšamo odkrite vektorje do presečišča. Če je podaljšek krajši od naslednje pragovne vrednosti n, vpišemo nov vektor na mesto starega. Na ta način zgradimo večino vozlišč. Na Sliki 7. so prikazane različne možnosti podaljševanja vektorjev v vozlišča. 1) Slika 7. Pogoji podaljšanja vektorjev v drugem koraku Slika 6. a)kopija dela črtne risbe b)binarizirana slika c)rezultat po prvem prehodu 2. KORAK: Izgraditev vozlišč, prvi del Za drugi korak je značilno da obdelava poteka samo na vektorski sliki, dobljeni v prvem koraku. Obdelava vektorske slike je bistveno hitrejša od obdelave rasterske slike. Po prvem koraku ostane še zmeraj problem za črte, ki so približno pod kotom 45 oz. 135 stopinj. Za te kote obstaja Slika 8. Rezultat po drugem prehodu 3. KORAK: Gradnja vozlišč, drugi del Po drugem koraku lahko ostane manjši del vozlišč nezaključen. Ta primer je največkrat zaradi relativno majhne pragovne vrednosti n . V drugem koraku ri ne smemo povečali, ker bi lahko prišlo do nepravile interpretacije rasterske slike. prikazano n'd Sliki 11. Po četrtem koraku je postopek vek-lorizacije končan. Slika 9. Pogoji za podaljšanje vektorjev v tretjem koraku O 2) Slika II. Oblikovanje vozlišč v četrtem koraku \ VV"' \ \ Slika 12. Rezultat po četrtem koraku Slika 10. Rezultat po tretjem koraku Zato v tretjem prehodu kombinirano testiramo vektorsko in rastersko sliko, vendar samo lokalno. Določimo novo pragovno vrednost r4, ki je ponavadi dvakrat večja od n. Testiramo preostale nepodaljšane vektorje pod istimi pogoji kol v drugem prehodu (samo z r^ namesto n). Če najdemo v področju m še eno ali več nepodaljšanih vektorjev, potem začasno podaljšamo vse te vektorje do presečišča. Na rasterski sliki testiramo, če so novi vektorji podaljšani preko rasterskih črt (Slika 9). Če je test pozitiven, lahko vpišemo nove podaljšane vektorje na mesto starih. 4. KORAK: Oblikovanje vozlišč Vozlišča, ki združujejo tri ali več črt in so bila zgrajena v drugem in tretjem prehodu, največkrat nimajo popolnoma pravilne oblike. Možne oblike nepravilnosti so povečano prikazane na Sliki 11. Te nepravilnosti so zelo majhne, registrirajo pa jih informacijski sistemi, ki uporabljajo vektorski zapis kot vhodne podatke. Zato v četrtem prehodu preverimo vsa vozlišča in jih ustrezno oblikujemo, kot je to Zaključek Geografski Informacijski Sistemi (GIS) so računalniška orodja, ki zagotavljajo učinkovito vodenje, povezovanje in vrednotenje geometrijskih podatkov o okolju. Osnovni problem za izgradnjo G/S-ov je vnos podatkov v računalnik. Večina podatkov o okolju je še vedno na papirju. Obstajajo različni ročni postopki vnosa teh podatkov v računalnik. V nalogi so preučeni postopki za digitalizacijo in vek-torizacijo črtnih risb velikih dimenzij, katerih struktura opisuje metriko prostora. Ti postopki so avtomatizirani. Vnos podatkov je tako lažji in hitrejši. Postopek vektorizacije črtnih risb je v veliki meri odvisen od vrste in vsebine črtne risbe, ki jo obdelujemo. V različnih okoljih so postavljeni različni standardi. V članku je predstavljena lastna metoda digitalizacije in vektorizacije, ki je zasnovana na zahtevah uporabnikov slovenskega prostora. Postopek digitalizacije je priprava rasterske slike za nadaljno obdelavo s postopkom vektorizacije. Vek-torizacija se izvaja v štirih zaporednih korakih. Izpolnjuje tri osnovne pogoje za uspešnost: natančnost rezultatov, sprejemljivost dobljenih rezultatov in hitrost postopka. Na posebej izdelani testni sliki je bil preverjen naš postopek za prenos grafične informacije iz predloge v vektorski zapis. Testiranje je pokazalo, da naša metoda izpolnjuje vse tri pogoje za uspešno vektorizacijo. OPOMBA: Podani postopki predstavljajo avtorsko delo in jih ni dovoljeneo reproducirati. Prav tako avtorji ne odgovarjajo za škodo, ki bi lahko nastala ob poiskusu implementacije k teh. Literatura [ 1 j A. Dedič, R. M urn, D. Peček, Postopki za obdelavo slik, YUROB'89, 1989, pp. 4.63-4.67. [2] A. Dedič, R. Murn, D. Peček, Optični zajem in digitalizacija grafičnih predlog večjih dimenzij, yraOß'^ö, 1990, pp. 3.38-3.42 [3] A. Dedič, R. Murn, D. Peček, Digitalization of Large Area Drawings and Maps, Melecon'91, IEEE Mediterranean Conf, 1991, pp. 1260-1263. [4] M.T.Musavi at al., A vision Based Method to Automate Map Processing, Pattern Rocognilion, 1988, pp. 319-326. [5] M. Ejiri at al.. Automatic recognition of design and maps, Proc. 7lh Int Conf. Pattern Recognition, pp. 1296-1305 [6] N. Otsu at al, A threshold selection method from gray-level histograms. IEEE Trans. Systems Man Cybernet. 9, 1979, 62-66. [7] Y. Nakagawa, Some experiments on variable thresholding, Pattern recognition 11,1979,191-204 [8] R. Esplid at al., A Raster-to-Vector-Conversation System Producing High Quality Geometric Entities, The 6th Scandin. Conf. on Pattern Ree., 1989,19-22 [9] S. Suzuki, Graph-Based Vcctorization Method for Line Patterns, hu. Conf. on Pattern Recognition, 1988, pp. 616621. [10] S. Suzuki at al.. Automatic line drawing Recognition of Large-scale Maps, Optical Eng. 7,1987, pp. 642-649 [11] K. Ramachandran, Coding Method for Vector Representation of Engineering Drawings, Proceedings of the IEEE 68,1980, pp. 813-816. UPORABA PREDZNANJA INFORMATICA 4/91 V INDUKTIVNEM UČENJU Keywords: machine learning, inductive Nada Lavrač learning, background knowledge, inductive Istitut Jožef Stefan logic programmnig Večina uveljavljenih metod za avtomatsko zajemanje znanja temelji na avtomatskem učenju iz primerov in uporablja atributni jezik za predstavitev primerov in naučenih konceptov. Atributni jezik je zelo omejen, saj ne omogoča opisovanja kompleksnih strukturiranih objektov ter relacij med objekti. V zadnjem času gre vse več pozornosti sistemom za avtomatsko učenje, ki uporabljajo izraznejše jezike prvega reda za predstavitev naučenih konceptov. Ti jeziki omogočajo uporabo relacij, ki izražajo predznanje o učnih primerih in domeni sami. Induktivno avtomatsko učenje relacij imenujemo tudi induktivno logično programiranje. V članku opišemo različne načine uporabe predznanja v atributnem učenju in v učenju relacij. Opišemo tudi uporabo predznanja v sistemu induktivnega logičnega programiranja LINUS. Na kratko predstavimo dve aplikaciji tega sistema. THE USE OF BACKGROUND KNOWLEDGE IN INDUCTIVE CONCEPT LEARNING Inductive concept learning is most frequently used for automatic knowledge acquisition. Most of the successful Inductive learning methods use a propositional attribute-value language for the representation of training examples and concepts. This language is limited and does not allow for representing complex structured objects and relations among objects. The goal of a new research area named Inductive Logic Programming (ILP) is to develop systems which can learn relational descriptions of concepts in a firstorder language of logic programs. A first-order language allows for describing relations which express experts' background knowledge about training examples and the domain as a whole. The paper describes the ways of using background knowledge in inductive concept learning, both in learning attribute and relational descriptions. Furthermore, the ways of using background knowledge in the system LINUS is described. LINUS is an integrated inductive learning environment which can be used for learning attribute descriptions using background knowledge, as well as for inductive logic programming. Two applications of LINUS are briefly described: learning rules for early diagnosis of rheumatic diseases and learning illegal chess endgame positions. 1. Uvod izvrševanju nalog na ozkem problemskem po- dročju dosegajo raven vrhunskih strokovnjakov - ekspertov. 'Inteligenca' ekspertnega sistema V svojem razvoju je umetna inteligenca prišla do temelji na bazi znanja, specifični za konkretno stopnje, ko so njene metode, tehnike in orodja problemsko področje. Proces izgradnje baze postale splošno uporabne v raznovrstnih računal- znanja je najtežavnejša faza v razvoju ekspert-niških aplikacijah. Med njimi so najbolj znani, nega sistema in je znana pod imenom 'Feigen-najuspešnejši in zato tudi komercialno najbolj baurnovo ozko grlo'. Dolgotrajnost in težavnost zanimivi ekspertni sistemi (Jackson 1990), ki v konstrukcije baz znanja sta bila povod za številne raziskave, katerih cilj je olajšati in pospešiti proces zajemanja znanja za ekspertne sisteme. Večina uveljavljenih metod za avtomatsko zajemanje znanja temelji na avtomatskem učenju iz primerov. V tem pristopu iz danih primerov ekspertnih odločitev z induktivnim sklepanjem izpeljemo splošna pravila. Tudi sam ekspert včasih najlaže posreduje svoje znanje s pomočjo dobro izbranih primerov. Večina praktično uporabnih sistemov za av-tomatsico učenje, kot na primer ASISTENT (Cestnik, Kononenko in Bratko 1987), uporablja iitributni jezik za predstavitev primerov in naučenih konceptov (opisov razredov). Pri teli sistemih so primeri predstavljeni z 7i-tericami vrednosti atributov ter ustreznim razredom, medtem ko so naučeni koncepti opisani z odločitvenimi drevesi ali z if-then pravili. Vse informacije o domeni so vsebovane v učnih primerih. Atributni jezik je zelo omejen, saj ne omogoča opisovanja kompleksnih strukturiranih objektov ter relacij med objekti. Zato obstaja vrsta nalog, ki jih z atributnim učenjem iz primerov ni mogoče rešiti. S j)roblemom omejenosti opisnega jezika se lahko spopademo na več načinov: • Metode za konstruktivno učenje omogočajo, da sistem avtomatsko konstruira nove, sestavljene izraze. V interakciji s sistemom ekspert izbere in poimenuje tiste od predlaganih avtomatsko konstruiranih izrazov, ki bi jih bilo smiselno uporabiti v učenju opisov konceptov. • Nove izraze lahko na osnovi svojega zjianja o problemski domeni predlaga ekspert. Ekspert lahko torej poda svoje predznanje (angl. background knowledge) kot funkcije vrednosti obstoječih atributov lahko pa poda tudi smiselne relacije med objekti problemskega prostora. • Moč atributnega jezika lahko povečamo tako, da izberemo izraznejši logični jezik prvega reda za predstavitev naučenih konceptov. V zadnjem času gre vse več pozornosti sistemom za avtomatsko učenje, ki uporabljajo izraznejše jezike prvega reda za predstavitev naučenih konceptov. Ti jeziki omogočajo uporabo relacij, ki izražajo predznanje o učnih primerih in domeni sami. Medtem ko je v atributnih jezikih naloga učenje opisa razredov iz učnih primerov, je v relacijskih jezikih naloga učenje logičnih definicij relacij iz primerov ter predznanja. V relacijskem učenju šo učni primeri opredeljena dejstva oz. n-terice vrednosti argumentov relacije, katere definicije se hočemo naučiti. Po analogiji z razredom je vsak učni primer označen z če pripada, oz. z 9, če ne pripada dani relaciji. Predznanje je tudi izraženo v obliki relacij, ki so podane s pripadajočimi n-tericami, ali pa z logičnimi definicijami (programi) v programskem jeziku prolog. Ker so naučene definicije relacij tudi izražene kot logični programi, induktivno avtomatsko učenje relacij imenujemo tudi induktivno logično programiranje (Muggleton 1991). V članku opiit'iiiu ra/licne načine ui)orabe predznanja v atributnem učenju in v učenju relacij. V drugem razdelku deliniramo problem induktivnega učenja konceptov. S primeri predstavimo naloge atributnega učenja, atributnega učenja z upoštevanjem predznanja ter učenja relacij v induktivnem logičnem programiranju. V tretjem razdelku obravnavamo uporabo predznanja v sistemu induktivnega logičnega programiranja LINUS. Na kratko opišemo algoritem in dve ap-lika.ciji sistema LINUS: učenje medicinskih diagnostičnih pravil v revmatologiji ter učeiije relacij v šahovski končnici. 2. Induktivno učenje konceptov Koncept C lahko definiramo kot podnuiožico prostora objektov. Induktivno učenje konceptov pomeni metodo učenja iz primerov, ki omogoča razpoznavanje objektov v C. Učni primer za učenje koncepta C je par: {Objekt, Razred) kjer je Objekt izbrani opis objekta, Razred pa ® a.li 0, kar označuje, da Objekt pripada ali ne pripada konceptu C. Učni primer je pozitiven, če Objekt i)ripada konceptu C {Razred — (B) in je negativen primer ali protiprimer, če ne pripada C {Razred = 0). Namesto da bi dani objekt klasificirali v enega od dveh razredov ® and O, ga lahko klasificiramo v enega od več medsebojno izključujočih se razredov Cc, c — 1,..., A'. Problem induktivnega učenja konceptov lahko formalno definiramo takole (de Raedt 1991): Al A2 .. Razred primeri Vu "13 • ■ .. Ci primer2 "21 "22 "23 • .. C2 primer^ ... ... Al A2 A3 A4 A5 Tabela 1: Množica primerov, zapisana v oblilti tabele. da balon da kvadrat kvadrat da zastava da osrnerokotnik osmerokotnik da meč da krog osmerokoinik da meč ne kvadrat osmerokoinik ne meč ne osmerokotnik krog ne zastava ne krog osmerokotnik Razred P P N N N N Podani so: • jezik za opis primerov Le • množica pozitivnih primerov P • množica negativnih primerov N • jezik za opis konceptov Lc • relacija pokritosti med Lc in Le « kriterij kvalitete definiran na nizih iz Lc Poišči: • opis koncepta C iz Lc, ki zadošča kriteriju kvalitete Kriterij kvalitete lahko zahteva, da je zgrajeni opis koncepta konsistenten in popoln glede na dano množico primerov. Opis koncepta je konsistenten, če ne pokriva nobenega negativnega primera. Opis je popoln, če pokriva vse pozitivne primere. Zahtevo po konsistenstnosti in popolnosti moramo omiliti, ko se učimo iz šumnih in nepopolnih podatkov. Tako lahko preprečimo, da bi sistem zgradil preveč specifične opise konceptov. Glede na izbor jezika za opis konceptov in primerov ločujemo dve glavni področji v induktivnem učenju: atributno učenje in učenje relacij. Tabela 2: Primeri prijaznih (P) in neprijaznih {N) robotov. if -yi) A (Aj = Vj) A... then Razred — Cc ki je konsistentno in popolno glede na dano množico primerov. Naučena if-then pravila opisujejo posamezne razrede. Sistemi pa se lahko naučijo tudi opisa vseh razredov v obliki odločitvenega drevesa, katerega listi označujejo posamezne razrede. Za ilustracijo učenja odločitvenih dreves izberimo primer iz sveta prijaznih in neprijaznih robotov (Wnek, Sarma, Wahab in Michalski 1990, Sutlič 1991). Opis robota je podan z naslednjimi atributi in njihovimi vrednostmi: AJ - se smeji: A 2 - drži: AS - ima kravato: A4 - oblika glave: yl5 - oblika telesa: da, ne balon, zastava, meč da, ne krog, kvadrat, osmerokotnik krog, kvadrat, osmerokotnik 2.1 Induktivno učenje opisov konceptov atributnih V atributnem učenju so primeri predstavljeni z 7i-tericami vrednosti atributov ter z ustreznim razredom. Objekt lahko pripada enemu od N medsebojno izključujočih se razredov Cc-Množico primerov {Objekt, Razred) lahko predstavimo s tabelo 1. Naloga atributnega učenja je poiskati klasifikacijsko pravilo (hipotezo, opis koncepta) kot funkcijo vrednosti atributov, ki ga lahko uporabimo za napovedovanje razreda neznanega objekta. Naučeni opis koncepta ima lahko obliko if-then pravila: V tabeli 2 je podanih šest učnih primerov. Za vsako 5-terico vrednosti atributov je podan razred, ki določa, ali je robot prijazen ali ne. Naloga učenja je poiskati pravilo, ki opredeli, ali je robot prijazen ali ne. Za učenje odločitvenih dreves lahko uporabimo sistem ASISTENT (Cestnik, Kononenko in Bratko 1987). Naučeno odločitveno drevo je prikazano na sliki 1. Opišimo Quinlanov algoritem ID3 (Quinlan 1986), ki je osnova algoritma ASISTENT. Naj bo S množica učnih primerov, Ci,...Cjv ps-odločitveni razredi. • če vsi primeri iz S spadajo v isti razred Cc • potem označi list drevesa s Cc • sicer Slika 1: Odločitveno drevo, zgrajeno s sistemom ASISTENT iz šestih primerov robotov. • izberi 'najinformativnejši' atribut A z vrednostmi vi,.. .,v„ • razdeli učno množico Sv ..., 5« glede na vrednosti vi,... ,Vn • rekurzivno zgradi poddrevesa Ti,... ,Tn za S\,..., Sn • zgradi odločitveno drevo T, kot je prikazano na sliki 2. Slika 2: Odločitveno drevo, ki ga zgradi ID3. Preiskovalna hevristika algoritma je določena z in-formativnostjo atributa, ki se izračuna na osnovi entropije učne množice E{S), ki izraža količino informacije, potrebne za klasifikacijo enega objekta: N C=1 kjer je pc apriorna verjetnost razreda Cc (izračunana z relativno frekvenco razreda Cc v 5). Entropija učne množice po razbitju po vrednostih .. ,Vn atributa A je: V=1 C=1 ^^ kjer je py apriorna verjetnost, da ima A vrednost ■i^v! Pvc P^ je apriorna verjetnost, da ima primer, ki spada v razred Cc, vrednost Vy atributa A. Informativnost atributa 1(A) je mera, ki mini-mizira število testov, potrebnih za klasifikacijo novega objekta: I{A) - E{S) - E(S/A). Najinformativnejši atribut je tisti, pri katerem doseže informativnost maksimum max I{A), kar je ekvivalentno minimizaciji entropije min E(S/A). V sistemu ASISTENT je bil algoritem ID3 izboljšan na več načinov. Omogoča obravnavo manjkajočih podatkov, obravnavo numeričnih (zveznih) vrednosti atributov, obravnavo NULL listov, v katere ne spada noben učni primer, obravnavo SEARCH listov, v katere spadajo primeri iz več različnih razredov, binarizacijo atributov, ter obravnavo netočnih podatkov, tako da vpelje rezanje dreves; rezanje omogoča izgradnjo manjših drevesa, ki so lažje razumljiva in imajo večjo klasifikacijsko točnost. Drugi primeri sistemov, ki se učijo opisov konceptov v obliki odločitvenih dreves so npr. C4 (Quinlan et al. 1986) in CART (Breiman et al. 1984). Primeri sistemov, ki se učijo if-then pravil pa so AQ15 (Michalski et al. 1986), njegov predhodnik NEWGEM (Mozetič 1985), CN2 (Clark in Niblett 1989) ter GINESYS (Gams 1989). 2.2 Uporaba predznanja v atributnem učenju Kot smo omenili v uvodu, lahko sistem v naučenih pravilih upošteva nove izraze, ki mu jih na osnovi svojega znanja o problemski domeni predlaga ekspert. Pri odločanju in pri razlagi odločitev eksperti namreč uporabljajo svoje znanje o problemu. To znanje je mogoče izraziti kot funkcije vrednosti atributov (s katerimi so opisani učni primeri) ali pa z relacijami med atributi ali objekti problemskega področja. To ekspertovo znanje, imenovano predznanje (angl. background knowledge), lahko sistem koristno uporabi pri učenju kompleksnejših relacij. Predznanje lahko sistem uporabi kot pomožno znanje v atributnem učenju. V učenju relacij pa postane relacijsko predznanje bistvenega pomena za učenje. V atributnem učenju sistem upošteva predznanje tako, da za vsak nov (sestavljen) izraz, podan v predznanju, vpelje nov atribut. Če poda ekspert svoje znanje v funkcijski obliki, se za posamezni .4/ A 5 A 6 Razred da balon da kvadrat kvadrat da I' da zastava da oamtvokotnik osmerokolnik da P da meč da krog osinerokotnik ne N da meč ne kvadrat osinerokotnik ne N n c meč lic osmerokotnik krog ne /V ii ć :asiava ne krog osinerokotnik ne A' Tabela 3: Primeri prijaznih (P) in neprijaznili (iV) rubolov. V stolpcu /16 so podane vrediiosli !i()V(>ga atributa oblika glave = oblika tclc.va. prijazen ^ Slika 3: Odločitveno drevo, zgrajeno s sistemom ASlS'l'l'^MT iz št^stili i)riinerov robotov z upora,bo predznanja. urni primer vrednost iiove'ga atributa izračuna kot 1'unkcija. vrednosti osnovnih a.tributov. Če Jia je prerimera ustrezajo relaciji, sicer ima vrednost Julije. V primeru iz sveta robotov vpeljimo en sestavljen izraz, s katerim testiramo relacijo enakosti: obltkit glave = oblika telesa. S tem smo vpeljali nov atribut /16 z naborom vrednosti ila {iruc/resnično) in ne {false/ni resnično). Nliiožico učnih primerov, dopolnjeno z vr(;dnos-tmi novega atributa /16, prikažemo v tabeli 3. V gra,dnji odločitvenega drevesa iz jirimerov ])o-danih tabeli 3 se novi atribut /16 izkaže kot najbolj inlormativen, zato se pojavi v koieiiu drevesa zgrajenega s sistemom ASISTENT. Ker vrednosti atributa /16 v celoti ločita med prijaznimi in neprijazidmi roboti, je to tudi edini atribut v zgrajenem drevesu. Drevo je podano na sliki 3. Iz primera je razvidno, da je lahko atribut, ki je zgrajen na osnovi predznanja, bolj informativen kot so osnovni atributi. Z u])orabo piedzna.nja nceptov, ki imajo lahko večjo klasifikacijsko točnost. 2.3 Induktivno logično programiranje V učenju relacij učni primeri izražajo relacije med elementi problemskega prostora (objekti), podano pa je tudi dodatno problemsko znanje (predznanje) o učnih primerih in domeni sami. Medtem ko je v atributnih jezikih naloga učenje opisov konceptov (razredov) iz učnih primerov, je v relacijskih jezikih naloga učenje logičnih definicij relacij iz primerov in predznanja. Nalogo učenja relacij v jeziku prvega reda lahko fornmlii'amo takole: Podani so: • jc^zik za opis primerov L^ • množica pozitivnih in negativnih primerov (dejstev ® in 9) neznane relacije p • jezik za opis konceptov Lc, ki določa sintaktične omejitve za definicijo i)redikata. p • jezik za opis predznanja Lß • predznanje - množica definicij iiomožnih predikatov in funkcij r/;, ki jih lahko uporabimo v definiciji predikata p • relacija pokritosti med Lc in glede na L^ • kriterij kvalitete definiran na" definicijah predikatov iz Lc Poišči: • definicijo ciljnega predikata p kot množico stavkov iz Lc, ki zado.šča kriteriju kvalitete Množica pozitivnih (®) in negativnih (9) primerov je podana z opredeljenimi dejstvi (angl. ground facts), kar ])omeni, da so podane vrednosti argumentov relacije, t.j., da v argumentih i-elacije ne nastopajo spremenljivke. Predznanje je [jodano z funkcijami in relacijami, ki vsebujejo informacijo o argumentih ciljne relacije p. Naloga učenja je poiskati definicijo relacije p v odvisnosti od relacij iz predznanja, ki bo ustrezala kriteriju kvalitete, npr. ki bo popolna in konsistentna glede na dana dejstva. Definicija je [jopolna, če razlaga (])okriva) vsa pozitivna dejstva, konsistentna pa, če ne pokriva nobenih negativnih dejstev. Naučena definicija predikata p sestoji iz množice stavkov oblike piXi,X2,...,.\'k) <-7.1,. .., kjei' je telo sta\'ka konjunkcija. litera.lov = Ilustrirajmo zgornjo definicijo na preprostem problemu učenja družinskih relacij (Džeroski 1991). Naj bo ciljna relacija daughter in naj bo predznanje sestavljeno iz relacij female in parent. Za relacijo daughter so podani štirje učni primeri: dva pozitivna in dva negativna. daughter{maja,ana). ® daughter{eva,tom). ® daughter (tom, ana). 0 daughter {èva, ana). 0 Podano je naslednje predznanje: parent(ana, maja), parent {ana, tom). parent{tom, èva). parent{tom, ivo). female{ana). female{maja). feinale{eva). Iz učnih primerov in predznanja se je mogoče naučiti definicije predikata daughter: daughter{X,Y) female{X),parent{Y,X). Naučene definicije relacij so podane s programskimi stavki v sintaksi programskega jezika prolog. Definicijo lahko v kompleksnejših primerih sestavlja več programskih stavkov (angl. program clauses). Množico stavkov z istim predikatom v glavi stavka imenujemo definicija predikata (angl. predicate definition). Definicija predikata tvori prologovo proceduro oziroma prologov logični program. Sistemi, ki se učijo logičnih programov, spadajo med sisteme induktivnega logičnega programiranja (ILP). Induktivno logično programiranje je mlado raziskovalno področje. V svetu so bile prve raziskave s tega področja opravljene leta 1981, ko je bil razvit sistem MIS (Model Inference System, Shapiro 1981), ki se zna učiti logičnih programov, temu pa so sledili sistemi MARVIN (Sammut in Banerji 1986), CIGOL (Muggleton in Buntine 1988), GOLEM (Muggleton in Feng 1990) in FOIL (Quinlan 1990). Področje je dobilo svoje ime šele leta 1990, prva delavnica (First International Workshop on Inductive Logic Programming) pa je bila marca 1991. Področje ILP je razvito tudi v Sloveniji. Razvita sta bila ILP sistema LINUS (Lavrač 1990) in niFOIL (Džeroski 1991), ki sta bila uporabljena v več domenah, znanih iz literature o avtomatskem učenju (Lavrač, Džeroski in Grobelnik 1991), za učenje medicinskih diagnostičnih pravil na področju revmatologije (Lavrač, Džeroski, Pirnat in Krizman 1991), za učenje načrtovanja mrež končnih elementov (Džeroski in Dolšak 1991) ter za učenje iz šumnih podatkov (Lavrač in Džeroski 1991, Džeroski in Lavrač 1991a). Teoretično primerjavo sistemov LINUS in FOIL smo podali z grafi specializacije (Džeroski in Lavrač 1991b). ILP pristop je bil uporabljen tudi za učenje kvalitativnih modelov (Bratko, Muggleton in Varšek 1991). 3. Uporaba predznanja v integriranem okolju za avtomatsko učenje LINUS Sistem induktivnega logičnega programiranja LINUS (Lavrač 1990, Lavrač, Džeroski in Grobelnik 1991) temelji na ideji, da je možno transformirati problem učenja relacij v problem atributnega učenja z uporabo predznanja. Na ta način lahko uporabimo obstoječe atributne učne algoritme, npr. sistem ASISTENT, ki so že dosegli veliko stopnjo uporabnosti in znajo obravnavati nepopolne in šumne podatke. Sistem LINUS omogoča uporabo dodatnega problemskega znanja v učenju opisov konceptov (opisov posameznih razredov objektov) ali učenju logičnih definicij relacij med objekti problemskega prostora. V sistemu LINUS opišemo učne primere in naučena pravila v jeziku deduktivnih hierarhičnih baz podatkov (DHBP), t.j. v logičnem jeziku prega reda, ki je izraznejši od atributnih jezikov 0-tega reda, ki jih uporablja večina uveljavljenih sistemov za induktivno učenje. Izbor tega preprostega jezika prvega reda omogoča sistemu LINUS, da z uporabo atributnih učnih algoritmov učinkovito zgradi logične opise relacij. Stavki DHBP so omejena oblika programskih stavkov; prepovedani so rekurzivni stavki, spremenljivkam pa so pridružene ustrezne končne zaloge vrednosti (tipi). Dodatna omejitev LINUSu onemogoča uvajanje novih spremenljivk v telo stavka. Predznanje je pri LINUSu izraženo v formalizmu deduktivnih baz podatkov (DBP), ki dovoljuje rekurzivne definicije predikatov. Sistem LINUS vključuje tri atributne učne algoritme ASISTENT, NEWGEM in CN2. ASISTENT je predstavnik TDIDT (Top-Down Indue- tion of Decision Trees) družine učnih algoritmov (Quinlan 1986). NEWGEM je član družine AQ algoritmov (npr. Michalski et al. 1986). CN2 združuje najboljše lastnosti ID3 in AQ algoritmov s tem, da dovoli uporabo statističnih metod, podobnih rezanju drevesa, in da generira if-then pravila. 3.1 Opis algoritma LINUS Program, ki omogoča vključitev sistema LINUS v okolje logičnega programiranja imenujemo DHBP vmesnik. Program je implementiran v prologu. Vmesnik pretvori pozitivna dejstva in negativna dejstva (negativna dejstva so podana ali pa jih generira DHBP vmesnik) iz DHBP oblike v obliko 7i-teric vrednosti atributov, atributni učni algoritem se nauči opisa koncepta v atributnem jeziku, DHBP vmesnik pa pretvori te opise v obliko DHBP stavkov. Najpomembnejši del DHBP vmesnika je generiranje novih atributov za učenje. Z upoštevanjem zaloge vrednosti tipov argumentov ciljne relacije namreč preveri, katere so možne aplikacije pomožnih predikatov in funkcij iz predznanja ter le-te upošteva kot dodatne atribute, ki jih bo uporabil v učenju. Vsak učni primer dopolni z vrednostmi teh dodatnih atributov, to je z vrednostmi da (true) ali ne (false) za pomožne predikate, oziroma z vrednostmi izhodnih argumentov za pomožne funkcije. DHBP vmesnik torej implementira osnovno idejo uporabe predznanja v atributnem učenju, ki smo jo razložili v razdelku 2.2. Učenje z LINUSom poteka v naslednjih korakih: • pripravi množico pozitivnih in negativnih dejstev, • pretvori dejstva iz DHBP oblike v n-terice vrednosti atributov, • nauči se opisa koncepta z uporabo atributnega učnega algoritma, • pretvori naučena pravila iz oblike if-then pravil v obliko DHBP stavkov. Algoritem opišemo s preprostim primerom. Denimo, daje relacija r(a,ò,c) podana z naslednjimi tremi dejstvi, označenimi z r(al,01,61). r(al,ò2,ò2). r(a2,òl,ò2). Podana je t,udi informacija o imenih in tipih spre- menljivk. Prvi argument relacije r ima ime a, njegov tip je tip.a, drugi in tretji argument b in C pa sta oba istega tipa tipjo. Vsakemu tipu je pridružena informacija o zalogi vrednosti spremenljivk: {al,a2} za tip.a in {bl,b2} za tip^b. Dodatno znanje o problemu je podano v obUki definicij pomožnih predikatov in funkcij. Uporabimo npr. binarni pomožni predikat p, definiran z naslednjimi dejstvi: p{al,bl). p(al,62). p(ö2,02). V splošnem so lahko pomožni predikati in funkcije definirani z množico rekurzivnih tipiziranih programskih stavkov (v formalizmu DBP). Argumenta predikata p sta tipa iip_a in tip.b. LINUS uporablja tudi vgrajeni pomožni predikat en«. (-/2). Množica negativnih dejstev je lahko vnaprej podana, lahko pa jo sistem generira iz pozitivnih dejstev. V načinu, ki temelji na predpostavki zaprtega sveta (cwa), LINUS generira vse možne kombinacije vrednosti argumentov ciljne relacije. Vsa generirana dejstva, razen podanih pozitivnih dejstev, LINUS uporabi kot negativna dejstva in jih označi z 0: r(al,6l,62). r(al,62,61). r(a2,61,61). r(a2,62,6l). r(a2,02,62). V drugem koraku algoritem preveri vse možne aplikacije pomožnih predikatov in funkcij glede na tipe spremenljivk. V našem primeru so to p{a,b) in p(a,c), enakost pa lahko uporabi nad argumentoma istega tipa, torej b=c. Iz treh pozitivnih primerov relacije r LINUS generira naslednje šesterice oblike: (a, 6, C, (6 = c), p(a,6), p(a,c) ) (al, 61, 61, true, true, true ) (al, 62, 62, true, true, true ) (a2, 61, 62, false, false, true ) Na enak način LINUS generira šesterice tudi negativnih dejstev. iz V tretjem koraku generirane n-terice pozitivnih in negativnih primerov uporabi za učenje s sistemi ASISTENT, NEWGEM ali CN2. Generirani opis koncepta v obliki odločitvenega drevesa, VLl pravila ali if-then pravil, se prepiše v prolo-govo obliko if-then pravil. V četrtem koraku algoritem pretvori if-then pravila iz prologove oblike v obliko DHBP stavkov. V našem preprostem primeru dobimo naslednji opis: r{A,B,C) r{A,B,C) A = al,B = C. C = 62, not piA,B). V generiranih pravilih nastopata poleg literalov A=:al in C=b2, ki jih je mogoče dobiti tudi z atributnim učenjem, tudi literala B=C in not p(A,B), ki sta dobljena z uporabo relacijskega predznanja. Z izborom atributov in predznanja, ki naj se uporabi za učenje, lahko torej sistem LINUS uporabimo na tri načine: • kot atributni učni algoritem, če sistemu povemo, kateri od argumentov ciljne relacije naj upošteva kot odločitveni razred ter če v celoti izključimo predznanje, • kot algoritem za atributno učenje, ki zna uporabljati predznanje, če sistemu povemo, kateri od argumentov ciljne relacije naj upošteva kot odločitveni razred ter če upoštevamo nove atribute, dobljene z uporabo predznanja, t kot algoritem za relacijsko učenje, če obravnavamo samo pozitivne in negativne primere relacije © in 9 ter se učimo samo na osnovi predznanja. 3.2 Uporaba predznanja v atributnem učenju opisov posameznih razredov v revmatologiji LINUS predstavlja razširitev atributnih algoritmov z možnostjo uporabe predznanja in ga lahko uporabimo za atributno učenje. Takemu načinu učenja pravimo učenje razredov (class learning mode, Lavrač, Džeroski in Grobelnik 1991). Sistem smo v tem načinu uporabili za učenje diagnostičnih pravil v revmatologiji. Eksperimenti so podrobno opisani v (Lavrač, Džeroski, Pirnat in Križman 1991). Na voljo smo imeli podatke o 462 pacientih Univerzitetnega kliničnega centra v Ljubljani. Pacienti so bili razvrščeni v 200 diagnoz, ki so bile grupirane v 8 razredov diagnoz: Al degenerativne bolezni hrbtenice (158 primerov), A2 degenerativne bolezni sklepov (128), BI vnetne bolezni hrbtenice (16), 5234 druge vnetne bolezni (29), C zunajsklepni revmatizem (21), D metabolni revmatizem (24), E neznačilne revmatske težave (32) ter F nerevmatske bolezni (54). V eksperimentu smo upoštevali le anamnestične podatke, opisane z vrednostmi naslednjih 16 atributov: spol, starost, družinska anamneza, sedanje težave, sedanja bolezen, bolečine v sklepih, število bolečih sklepov, število oteklih sklepov, bolečine v hrbtenici, ostale bolečine, jutranja okorelost, koža, sluznice, oči, druge težave in terapija. LINUS smo uporabili za učenje opisov posameznih razredov diagnoz. 70 % podatkov smo uporabili za učenje, 30 % pa za testiranje klasifikacijske točnosti naučenih pravil. Eksperiment smo ponovili desetkrat, z naključno porazdelitvijo v učne in testne primere. V učenju smo upoštevali predznanje o značilnih skupinah simptomov. Identificirali smo 6 značilnih skupin simptomov, npr. karakteristične kombinacije simptomov prve skupine so naslednje: Bolečine v sklepih Jutranja okorelost bp artrotična artritična < 1 ura < 1 ura > 1 ura Karakteristične kombinacije v šesti skupini simptomov pa so podane v spodnji tabeli: Število oteklih sklepov Število bolečih sklepov 0 0 1 < št. sklepov < 10 0 1 < št. sklepov < 30 0 < št. sklepov < 30 Kot primer navedimo diagnostično pravilo za metabolni revmatizem: Razred = metabolni^revmatizem skupina6( St-otekl^klepov, St.bol.sklepov, 'J= 30, Starost =< 40, Spol - moški. Razred = metabolnLrevmatizem <— BoLv-hrbtenici = bp, BoLv-sklepih — artriticne, Spol - moški. Razred = metabolni-revmatizem <— Bol.vJirbtenici = bp, Starost =< 40, Sedanje.tezave > 11, Spol = rrùìski, skupina5( BoLv.skltpih, BoLv.hrbtenici, Si.boLsklepov, Vrednost), member( Vrednost, [ 'artriticne&bp&l—omočjo znanja o sistemu, ki ga želimo voditi. O tem govori naslednji razdelek. 4 Kvalitativni modeli in vodenje sistemov Novejši ekspertni sistemi uporabljajo tudi globoko znaiije, ki je kompaktnejše ter odraža strukturo in glol)lje principe problemskega področja. V zvezi s tem se postavljata vprašanji, kako globoko znanje predstaviti in kako ga uporabiti za reševanje problemov. Globoko znanje lahko predstavimo s kvaliiutiv-niuii modeli. Ti opisujejo delovanje sistemov in naprav na enostaven simboličen način, ki je l)]izu človekovemu načinu mišljenja. Natančne nu-mcričue vi-ednosti niso potrebne: vse vrednosti spremenljivke, ki dajo kvalitativno isto vedenje sistema, združimo v eno samo kvalitativno vrednost. Spremenljivke so vezane z relacijami in ne / (Miačbami kot pri klasičnih modelih. Relacije imajo hihko obliko omejitvenih enačb, neenačb ali logičnih izjav. Podrobnejši pregled področja najdemo v knjigi (Weld & de Kleer 1990). Končni cilj predstavitve znanja je seveda njegova uporaba. Za razliko od matematičnih modelov, [)ri katerih rešujemo enačbe in računamo vrednosti funkcij v danih točkah, postanejo kvalitativni modeli operativni s kvalitativnim sklepanjem. Spremenljivkam določamo kvalitativne vrednosti tako, da je zadoščeno relacijam v modelu. Kvalitativni modeli določajo relacije med vhodi v sistem, kvalitativnimi stanji sistema in izhodi. Najpogostejši in "najnaravnejši" način sklepanja začne z znanim začetnim stanjem in vhodi v sistem, nato pa v skladu z modelom razvija nadaljnje vedenje sistema. V tem primeru govorimo o kvalitativni simulaciji [n^tv. Kuipers 1986). Z njo je možno neposredno reševati probleme, kot so na primer napovedovaiije vedenja sistema, verifikacija načrtov, izpeljava vseh možnih stanj sistema in prehodov med njimi (envisioning). Reševati želimo tudi drugačne probleme,' ki so v nekem smislu obratni prejšnjim: izhajamo iz podanega vedenja sistema in ugotavljamo, kako lahko do njega pride. Kadar gre :,a diagnostiko, izhajamo iz manifestiranega nezaželenega vedenja in iščemo stanja, ki so ga povzrcčila. Pri problemu vodenja sistema je podano zaželeno vedenje, poiskati pa je treba zaporedje vhodov (akcij), ki pri danem začetneur stanju tako vedenje zagotovijo. Za neposredno reševanje takih problemov z modelom je potrebno vzvratno sklepanje. PRAVILA ZA VODENJE induktivno učenje TABELA STANJE-AKCIJA strategija za izbor akcije OPIS VEDENJA (GRAF PREHODOV STANJ) izčrpna kvalitativna simulacija KVALITATIVNI MODEL Slika 2: Avtomatska sinteza pravil za vodenje, pristop z izčrpno kvalitativno simulacijo Učinkovitost sklepanja pri tovrstnih problemih lahko povečamo na različne načine. Eden od njih je modeliranje na različnih nivojih podrobnosti in upoštevanje hierarhij pri sklepanju (Mozetič in sod. 1990): rezultati na manj podrobnem nivoju usmerjajo sklepanje na bolj podrobnem. Druga možnost je uporaba izčrpne simulacije za generiranje enostavnih površinskih pravil, s katerimi je možno hitro reševati probleme na nivoju natančnosti modela. Postopek je ponazorjen na sliki 2 in smo ga že uporabili za avtomatsko sintezo pravil za vodenje inverznega nihala (Urbančič 1991). Če je problemsko področje preobsežno za izčrpno simulacijo in iz ogromne množice možnih primerov velika večina dejansko nikoli ne nastopi, je smiselno uporabiti kombinacijo površinskega in globokega znaiija. Za pogoste situacije vgradimo plitvo operativno znanje, v izjemnih situacijah pa izpeljemo rešitev neposredno iz modela in tako dobljeno pravilo naknadno vključimo v plitvo bazo znanja. Seveda se moramo pred uporabo te metode prepričati, da kritičnost in hitrost procesov to dopuščata. Medtem ko so se kvalitativni modeli na nekaterih tehničnih področjih kmalu izkazali kot primerno orodje za reševanje problemov, npr. pri diagnostiki (Davis 1984; Genesereth 1984), so možnosti njihove uporabe na področju vodenja sistemov še relativno neraziskane (Franklin 1990). Nekateri rezultati pa vendarle tudi tukaj kažejo na obe-tavnost kvalitativnega pristopa: • kvalitativne modele je možno uporabljati za načrtovanje vodenja (npr. Leitch & Francis 1986; Bratko 1991; Urbančič 1991), • v posebnih primerih (linearni modeli) je možno na podlagi kvalitativnega modela izvesti analizo perturbacij in določiti, kako s perturbacijo vhodnih parametrov dosežemo željeno vedenje sistema (de Mori & Prager 1989), • kvalitativni modeli lahko pripomorejo k inteligentnemu monitoringu, zaenkrat predvsem v kontekstu diagnostike (Forbus 1987; Dvorak & Kuipers 1989), • rezultate kvalitativne simulacije lahko uporabimo za analizo stabilnosti vodenih sistemov (Fouche & Kuipers 1991). Obetavne so tudi študije primerov (npr. Bratko in sod. 1989; Bratko in sod. 1991; Varšek 1991), ki kažejo, da lahko avtomatsko učenje učinkovito uporabimo pri avtomatizirani gradnji kvalitativnih modelov iz opazovanega vedenja sistema. Vendarle pa še ni bila dosežena stopnja širše praktične uporabnosti. Eden izmed razlogov je gotovo težek problem prevajanja kvantitativnih opažanj v kvalitativni jezik ter kvalitativnih zaključkov v kvantitativne vrednosti kontrolnih akcij. Razen tega je treba poskrbeti za delovanje v realnem času, za upoštevanje različnih tipov znanja (npr. vzročno znanje o sistemu, nujne akcije za zagotavljanje varnosti, verjetnost za posamezne okvare v sistemu in na senzorjih) ter za obvladovanje kompleksnosti. Niso namreč redki sistemi z nekaj tisoč komponentami. 5 Zaključek Poudariti želimo, da pri razvoju alternativnih metod za vodenje sistemov ne gre za tekmovanje s klasičnimi, kvantitativno orientiranimi pristopi, pač pa za smiselno dopolnjevanje: • Če je možno sistem v sprejemljivem času res ustrezno predstaviti z matematičnim modelom in so izpolnjene predpostavke za klasične postopke načrtovanja vodenja, bo tako dobljeno vodenje seveda zmeraj natančnejše od kakršnegakoli kvalitativnega pristopa. Veliko prednost predstavljajo tudi teoretično podprte metode za obravnavanje pomembnih vprašanj, kot npr. določanje območja kontrolabilnosti, stabilnosti ipd., ki jih je v takih primerih možno uporabiti. Kvalitativne pristope je v tem kontekstu smiselno uporabiti le kot dopolnilo zaradi zagotavljanja razlage oziroma transparentnosti vodenja ter zaradi nuđenja pomoči operaterju pri nadzorovanju procesa. • Če ustreznega matematičnega modela v sprejemljivem času ne moremo razviti ali pa le-ta (od samega začetka ali pa čez čas, ko se razmere spremenijo) ne odraža dovolj verno realnosti, je treba iskati kompromis med natančrrostjo rešitve in hitrostjo oziroma ceno, ki je za to potrebna. Problem bi lahko formulirali kot iskanje konceptualno jasnih, čeprav manj natančnih rešitev, ki bi se obnesle v praksi ne le zaradi razumljivosti, pač pa nenazadnje tudi zaradi nižje cene. Literatura Barto, A.G., Sutton, R.S., Anderson, C.W. (1983) Neuronlike Adaptive Elements That Can Solve Difficult Learning Control Problems. IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-13, No.5, 834-846. Bratko; I. (1989) Machine Learning. V knjigi K.J. Gilhooly (ur.) Human and Machine Problem Solving, Plenum Press, New York. Bratko, L, Mozetič, L, Lavrač, N. (1989) KAR-DIO: A study in deep and qualitative knowledge for expert systems. Cambridge, MA: MIT Press. Bratko, I. (1991) Qualitative Modelling: Learning and Control. Sixth Czechoslovak Conference on Artificial Intelligence, Prague, June 1991. Bralko, L, Muggleton, S., Varšek, A. (1991) Learning qualitative models of dynamic sys-• ouis. Inductive Logic Programming Workshop 91, Viaiia de Castello, Portugal, March 1991. A short ve*rsion also in Proc. Machine Learning 91, Morgan Kaufmann. Coniiel, M.E., Utgoff, P.E. (1987) Learning to Control a Dynamic Physical System. In Proceedings of the 6th National Conference on Artificial Intelligence, Morgan Kaufmann, 456-459. Davis, R. (1984) Diagnostic Reasoning Based on Structure and Behavior. Special Volume on Qualitative Reasoning about Physical Systems, Artificial Intelligence, 24(1-3), 347-410. Dvorak, D.L. (1987) Expert Systems for Monitoring and Control. Technical Report AI 87-55, Artificial InteUigence Laboratory, The University of Texas at Austin. Dvorak, D., Kuipers, B. (1989) Model-Based Monitoring of Dynamic Systems. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, August 20-25, Detroit, MI, 1238-1243. Forbus, K.D. (1987) Interpreting Observations of Physical Systems. IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-17, No.3, 350-359. Fouciie, P., Kuipers, B. (1991) Introducing Energy into Qualitative Simulation. First European Workshop on Qualitative Reasoning about Physical Systems, Genova, January 1991. Franklin, J.A. (1990) What is Qualitative Reasoning, and Can We Use it for Control? Proceedings of the 29th IEEE Conference on Decision and Control, Dec. 1990, Honolulu, HI. Genesereth, M.R. (1984) The Use of Design Descriptions in Automated Diagnosis. Special Volume on Qualitative Reasoning about Physical Systems, Artificial Intelligence, 24(1-3), 411-436. Kuipers, B. (1986) Qualitative Simulation. Artificial Intelligence 29, 289-338. Leich, R., Francis, J.C, (1986) Towards Intelligent Control Systems. In Mamdani, A., Efstathiou, J. (eds.) Expert Systems and Optimisation in Process Control. Gower Technical Press, Aldershot, England, 62-73. Litt, J. (1991) An Expert System to Perform On- Line Controller Tuning. IEEE Control Systems Magazine, Vol.11, No.3, 18-23. Michie, D., Chambers, R.A. (1968) BOXES: An experiment in adaptive control. In Dale, E., Michie, D. (eds.) Machine Intelligence 2, Edinburgh University Press, 137-152. de Mori, R., Prager, R. (1989) Perturbation Analysis with Qualitative Models. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, August 20-25, Detroit, MI, 1180-1186. Mozetič, L, Bratko, L, Urbančič, T. (1991) Varying level of abstraction in qualitative modelling. V knjigi J.E.Hayes, D.Michie, E.Tyugu (eds.) Machine Intelligence 12, Oxford University Press, 259-280. Pang, G. (1989) Knowledge engineering in the computer-aided design of control systems. Expert Systems, Vol.6, No.4, 250-262. Sammut, C., Michie, D. (1991) Controlling a "Black Box" Simulation of a Space Craft. Al Magazine, Vol.12, No.l, 56-63. Selfridge, O.G., Sutton, R.S., Barto, A.G. (1985) Training and Tracking in Robotics. In Proc-.-'d-ings of the 9th International Conference on Artificial Intelligence. Morgan Kaufmann, 670-672. Urbančič, T. (1990) Avtomatsko učenje vodenja dinamičnih sistemov. Informatica, letnik 14, št. 4, 39-48. Urbančič, T. (1991) Automatic model-based synthesis of control rules for inverted pendulum. First European Workshop on Qualitative Reasoning about Physical Systems, Genova, January 1991. Varšek, A. (1991) Qualitative model evolution. International Joint Conference on Artificial Intelligence, Sydney, September 1991. Weld, D.S., de Kleer, J. (eds.) (1990) Readings in Qualitative Reasoning about Physical Systems. Morgan Kaufmann, San Mateo, CA. POVEZAVA OSEBNEGA RAČUNALNIKA Z ROBOTSKIM KRMILNIKOM ASEA-IRB Keywords: computer link, robot controller, personal computer, application protocol Michele Leonardi, Aleš Klofutar, Ivo Gorkič Institut Jožef Stefan Prispevek opisuje povezavo robotskega krmilnika ASEA IRB6/L z osebnim računalnikom. Komunikacija temelji na protokolu asinhronske serijske komunikacije (ADLPIO) in aplikacijskem protokolu (ARAP). Prvi del opisuje električno povezavo robotskega krmilnika in osebnega računalnika ter oba protokola. Večji poudarek je na aplikacijskem protokolu, saj ta omogoča dodatke oziroma popravke in dodelave programa brez prevelikih težav. Na podlagi aplikacijskega protokola je nastala knjižnica ukazov. Drugi del vsebuje-spisek ukazov in njihovo uporabo ter opisuje delovanje programa Proto, kije nastal hkrati s knjižnico ukazov. COMPUTER LINK FOR ASEA ROBOT CONTROLLER The paper presents the computer link for ASEA IRB robot controler. Communication is based on as-inchronous communication protocol (ADLPIO) and application protocol (ARAP). Electrical link between the controller and the personal computer together with both protocols are presented in the first part of the paper. The application protocol is more emphasized due to its better possibilities of improvement. A library of instructions was developed on the basis of the application protocol. The list of instructions and the description of program Proto, which was developed together with the library are described in the second part of the paper. 1. Uvod 2. Komunikacijski protokol Vse večja robotizacija proizvodnih procesov pogojuje potrebo po usklajenem delovanju robotov in njihovem prilagajanju okolici. Robotski krmilniki poskrbijo, da robot opravi vnaprej zadane naloge, katerih obsežnost je omejena z zmogljivostmi robotskega krmilnika. Zmogljivosti robotskega krmilnika lahko bistveno povečamo s povezavo z zmogljivejšim osebnim računalnikom. V članku smo opisali povezavo robotskega krmilnika ASEA IRB6/L z računalnikom PC AT. Povezava omogoča izvajanje večine ukazov, ki jih lahko izvedemo neposredno z robotskega krmilnika tudi z osebnega računalnika. Povezava med robotskim krmilnikom in osebnim računalnikom je omogočena s protokoloma, ki jih je predpisala ASEA: ADLP 10 (ASEA Data Link Protocol) [2] in ARAP (ABB Robot Application Protocol) [1]. 2.1 Električna povezava Na strani robotskega krmilnika smo uporabili poseben komunikacijski vmesnik DSCA114 in pri njem ustrezno nastavili vhodno/izhodni naslov vmesnika in prekinitveni nivo. Na strani osebnega računalnika pa smo uporabili že vgrajeni vhodno/izhodni vmesnik z ustrezno nastavitvijo. Slika 1: Povezava robotskega krmilnika z osebnim računalnikom 2.2 ADLPIO 1. Vzpostavitev komunikacije ADLP-10 je postopek za asinhronsko komunikacijo med dvema postajama v hierarhičnem sistemu. Postopek temelji na protokolih ECMA-16 in ECMA-24. Prenos podatkov je asinhronski, serijski in pol-dvosmeren. Lahko je iniciiran z obeh strani. Vsak znak (podatkovni, kontrolni) je sestavljen iz 8 bitov + parnostni bit stop bit. Preverjanje pravilnosti komunikacije se vrši z vertikalno in horizontalno kontrolo parnosti. Za komunikacijo prek serijskega vhodno/izhodnega vmesnika smo razvili podprogram, ki omogoča odpiranje in zapiranje komunikacijskega kanala ter oddajo in sprejem posameznih znakov. Pri odpiranju komunikacijskega kanala je potrebno specificirati številko komunikacijskega kanala (COMI, COM2), hitrost prenosa (npr. 9600 b/s), število bitov na znak, število stop bitov in parnost (npr. liha parnost). Podprogram poleg tega omogoča hkraten sprejem in oddajo znakov ter detektira napake med sprejemom. Izmenjavo informacij med postajama razdelimo v tri faze 2. Prenos informacij 3. Zaključek komunikacije Prenos informacij poteka med drugo fazo. Za spremembo smeri komunikacije moramo izmenjavo zaključiti in ponovno vzpostaviti komunikacijo. Postajo, ki vzpostavi komunikacijo imenujemo master, podrejeno pa slave. Master je zadolžen za prehajanje med fazami in vzdrževanje komunikacije. 2.3 ARAP Komunikacija med postajama poteka prek sporočil, ki so definirana z aplikacijskim protokolom (ARAP). Sporočilo predstavlja informacije, ki so med seboj logično povezane in sestavljajo enoto. Sestavljeno je iz enega ali več telegramov. 2.3.1 Telegrami Informacijo, ki se izmenjuje med robotskim krmilnikom in osebnim računalnikom, razdelimo v manjše enote, ki jim pravimo telegrami. Vsak telegram je sestavljen iz glave in podatkovnega polja. Glava je vedno enake velikosti (8 bytov) in vsebuje informacijo, ki temelji na aplikacijskem protokolu (velikost telegrama, funkcijsko kodo, tip telegrama, indikator dolžine telegrama, status odgovora, naslov pošiljatelja in naslov prejemnika telegrama). Funkcijska koda določa namen sporočila. V dokumentaciji je predvidenih 44 različnih funkcijskih kod. Imamo dva tipa podatkovnih polj (koda napake, podatkovno polje). Velikost in vsebina podatkovnega polja se spreminjata v odvisnosti od tipa sporočila in je v določenih primerih tudi izpuščena. Obstajajo trije različni tipi telegramov: robota npr. itd. izklop v sili, sistemske napake 3. Knjižnica ukazov Na osnovi aplikacijskega protokola smo v programskem jeziku Turbo Pascal razvili knjižnico ukazov, ki omogočajo vodenje in programiranje ■robotskega krmilnika z osebnega računalnika. Osnovo predstavljajo ukazi, ki so z določenimi funkcijskimi kodami direktno dosegljivi iz aplikacijskega protokola. Vsi ukazi so oblike Exec_... in kot prvi parameter vedno vrnejo kodo napake (ErrResult), ki jo javi robotski krmilnik. Če je vrednost ErrResult = O, pomeni, da je prišlo do prekinitve komunikacije, če pa ErrResult = -1, pa da je robotski krmilnik ukaz izvršil. Ostale vrednosti kode napake pa najdemo v dokumentaciji. Ukaze delimo na osem skupin. Ukaz lahko pošljeta tako robotski krmilnik kot osebni računalnik in pomeni, da pošiljatelj zahteva, da sprejemnik izvrši neko nalogo. Ukaz se lahko sestoji le iz glave ali pa iz glave in podatkovnega polja. Podatkovno polje je lahko daljše od maksimalne dolžine telegrama, zato se za ukaz lahko uporabi več povezanih telegramov. Ukaz vedno pričakuje odgovor (pozitiven oz. negativen). Odgovor je poslan le kot potrdilo ukaza in ga lahko pošljeta tako robotski krmilnik kot osebni računalnik. Tako kot ukaz se tudi odgovor lahko sestoji le iz glave ali pa iz glave in podatkovnega polja. Če je podatkovno polje daljše od maksimalne dolžine telegrama, se za odgovor lahko uporabi več med seboj povezanih telegramov. Lahko ga uporabimo tako za pozitivno kot tudi negativno po-drditev ukaza. V primeru negativne potrditve se podatkovno polje nadomesti s 16 bitno kodo napake. Če za neko funkcijsko kodo podatkovno polje ne obstaja, se telegramu doda 16 bitna koda napake v primeru negativnega odgovora. Spontano sporočilo lahko pošlje le robotski krmilnik računalniku in ni pogojeno z ukazom. Robotski krmilnik pošilja spontana sporočila kot posledico različnih dogodkov v delovanju Statusni ukazi omogočajo branje pozicije in orientacije robota ter branje stanja motorjev robota. Ukazi povezani z robotskimi programi omogočajo prenos programov z računalnika na robotski krmilnik, brisanje programov iz spomina krmilnika, zagon in ustavitev programov iz krmilnika. Ukazi povezani s premikanjem robota Za premik robota moramo poslati tri ukaze 1. Začetna točka 2. Ukaz za absolutni ali relativni premik 3. Končna točka Ukaz omogoča nastavitev hitrosti robota in absolutno oziroma relativno premikanje robota. Ukazi povezani s koordinatami orodja omogočajo vpis , brisanje in branje koordinat orodja ter aktiviranje določenih koordinat. Ukazi povezani z registri omogočajo vpisovanje in branje iz • registrov • lokacijskih registrov • digitalnih izhodov • digitalnih vhodov • frame registrov Ukazi povezani s konfiguracijo omogočajo branje in vpisovanje konfiguracije na robotski krmilnik. Ukazi povezani z Vision sistemom omogočajo branje podatkov, ki so povezani z robotskim vidom s krmilnika in lociranje modelov, ki so v vidnem polju kamere, seveda jih lahko uporabljamo le, če je krmilnik opremljen z Vision sistemom. Ukazi povezani s prijemalko robota omogočajo zapiranje in odpiranje prijemalke robota. 4. Program Proto Na podlagi knjižnice ukazov smo razvili program Proto, in z njim preverili delovanje knjižnice ukazov. Poleg osnovnih ukazov, ki smo jih predstavili v prejšnjem poglavju, vsebuje program še nekaj kombinacij le teh, zraven pa še omogoča sprejem ukazov s strani robotskega krmilnika in sprejem spontanih sporočil (Spontaneous messages) s strani robotskega krmilnika. 4.1 Podatki o stanju robota Program periodično zahteva od robotskega krmilnika podatke o stanju, v katerem se robot nahaja. Zgornja vrstica je rezervirana za sporočila uporabniku. Tu se izpisujejo naslednje stvari • Stanje pripravljenosti • Vsebina spontanih sporočil [1, str.78] • V primeru nepravilno sprejetega ukaza s strani robotskega krmilnika, sporočilo, ki ga definira koda napake [1, str.81] • Potrditev uspešno izvedenega ukaza. V drugi vrstici se izpisuje stanje motorjev robota (Stand by. Operate, Execute, Emergency stop) ter program in vrstica programa, v kateri smo. V tretji vrstici imamo stanje enote za programiranje (connected, disconnected). V četrti pa pozicija (v mm) in orientacija (v stopinjah) robota. Spodnji dve tretjini ekrana sta rezervirani za ukaze uporabnika. 4.2 Ukazi Ukazi so razdeljeni na pet sklopov 1. Ukazi povezani s programiranjem robotskega krmilnika (Robot program conunands) Uporabljajo ukaze povezane z robotskimi programi iz knjižnice ukazov poleg tega pa še izpis programov na ekran in tiskalnik. 2. Branje podatkov z robotskega krmilnika (Data reading from SC) Omogočajo branje podatkov iz posameznih registrov robotskega krmilnika, branje konfiguracije in koordinat orodja. 3. Vpisovanje podatkov na robotski krmilnik (Data writing from SC) Omogočajo vpis podatkov iz posameznih registrov robotskega krmilnika, vpis konfiguracije in koordinat orodja. 4. Ukazi povezani z robotskim vidom (Vision system data) Uporabljajo ukaze povezane z robotskim vidom iz knjižnice ukazov. 5. Neposredni ukazi (Direct commands) Omogočajo aktiviranje določenih koordinat orodja in določenega koordinatnega sistema odpiranje in zapiranje prijemalke, sinhronizacijo, vžig in izklop motorjev robota ter premikanje robota. Premikanje robota je mogoče • absolutno ali relativno: podamo koordinate pozicije (v mm) in orientacije (v stopinjah) robota. • zvezno: s pritiskom na določeno tipko se robot premakne v smeri, ki jo določa tipka. 5. Zaključek Programski paket omogoča povezavo robotskega krmilnika ASEA z osebnim računalnikom. Trenutno stanje robota in njegove okolice lahko izčrpnejše in hkrati bolj pregledno prikažemo na message: ABB computer link at your service Op.mode STAND BY Program 0/10 Programming unit CONNECTED X 471.5 y 0.0 z 500.3 roll 41.3 pitch |-77.1 Robot program commćinds Data vriting from SC Data reading from SC Vision system data Direct commćinds Slika 2: Program Proto zaslonu osebnega računalnika kot na dvovrstičnem prikazovalniku robotove prenosne ukazne plošče. S tem je mogoče statistično spremljanje in iskanje optimalnih časov delovnih faz. Pomembna je tudi možnost pisanja programov za robotski krmilnik na osebnem računalniku. S tem prenesemo programiranje iz proizvodnih dvoran v človeku prijaznejše okolje in omogočimo simulacijo delovanja robota na osebnem računalniku. Omogočena nam je tudi uporaba vseh programskih orodij namenjenih za izdelavo programov, kar nam v veliki meri olajša pisanje le teh. Ob vseh drugih prednostih je zelo pomembna tudi možnost implementacije nove programske opreme. Robotski krmilnik ASEA namreč predstavlja zaprt sistem in implementacija nove programske opreme je mogoča le prek povezave z osebnim računalnikom. Programski paket je zgrajen modularno in omogoča lahko vključevanje knjižnice ukazov v programe napisane v programskem jeziku Turbo Pascal. Omogočena je kontrola napak, saj rutine kot enega izhodov vračajo kodo napake. Program Proto, ki smo ga razvili za preizkus delovanja knjižnice ukazov poleg osnovnih funkcij omogoča še izpis robotskih programov na ekran in tiskalnik. Programski paket bi lahko uporabili tudi za uskladitev delovanja več robotov. Protokol to omogoča, seveda pa so potrebne tudi ustrezne dodelave programskega paketa in pa algoritmi, ki bi koordinirali sodelovanje več robotov. Literatura [1] ABB Robot Application Protocol (ARAP) for Computer Link ABB, Sept. 1988 [2] ASEA Asynchronous Communication for Computer Link-ADLP 10, Jan. 1984 [3] ABB Industrial Robot System 1RB6/2, July 1983 [4] Ivo Gorkič: Program za povezavo industrijskega robota z osebnim računalnikom, Diplomska naloga. Fakulteta za elektrotehniko in računalništvo, Ljubljana, Junij 1991 Novice in zanimivosti 64 let dvoma o nastajanju umetne inteligence (Kritika umetne inteligence Huberta L. Dreyfusa) Anton P. Železnikar V zgodovini kritike umetne inteligence bo H. L. Dreyfusu lahko da pripadalo podobno mesto, kot ga ima Sokrat v zgodovini zapadne filozofije. Kot pravi sam [MOM, str. 202], »za Nietzsche]a Sokrat ni bil junak naše kulture, temveč njen prvi izp rij enee [degeneriranec], ker je zgubil zmotnost aristokracije, da zaupa intuiciji. Možje poštenja ne razgaljajo svojega razuma na ta način, " je pripomnil Nietzsche.« Dreyfusova vloga v ev-foričnem in nekritičnem pohodu umetne inteligence v šestdesetih in sedemdesetih letih tega stoletja je bila v prikazovanju naivnosti zaupanja v neko tehnološko (računalniško) intuicijo (ideologijo), ki je napovedovala skorajšnje doseganje in preseganje človekove inteligence (uma) s pomočjo matematično-teorijskega simbolizma in strojev, ki ta logični aparat oziroma logično strojništvo tehnološko podpirajo. Čeprav je bil ameriški filozof H.L. Dreyfus, sicer učenec Dagfina Foellesdala, znanega interpreta fenomenološke koncepcije Edmunda Hus-seria, prvi radikalni kritik zamisli in ideologije umetne inteligence, kije začela nastajati v začetku šestdesetih let na M.I.T., pa seje kritika tega, kar seje v petdesetih poimenovaloumetaa inteligenca, pojavila že prej. Dejansko se kritika mišljenja inteligence (razumevanja) kot človekovega pojava mišljenja pojavlja tako ali drugače in v vsej domišljeni zapletenosti in eksplicitoo v delu Martina Heideggra, Sein und Zeit, ki izide v letu 1927. Dvom o tem, o čemer so še lahko upali učenci Husseria, dobi s Heideggrovim delom spoznavno ozadje, ki ga zlagoma, kasneje pa čedalje bolj intenzivno prevzamejo tudi mlajše generacije iz komune ameriške umetne inteligence in t.i. račun- alniških znanosti po svetu. Kritike umetne inteligence seveda ni mogoče ločiti od kulturnih paradigem modernizma in postmodernizma. Gre za določeno kontinuiteto razvoja znanosti, ki je še pretežno zasidrana v moderni, njena kritika pa se že razteza v t.i. postmodernost. Zgleden opis pojava postmoder-nosti, ki ni le muha enodnevnica, temveč postaja temeljno metafizično vprašanje človeka sedanjosti, je Slovencem podaril A. Debeljak v Postmoderni sfingi [PS]; ob tem se odpira (postmodernistično) vprašanje, ali je to delo le po naključju izšlo v Avstriji. Umetna inteligenca (UI) je kot znastvena in tehnološka disciplina danes še vedno utemeljena v matematičnih in računalniških programskih sistemih, kot posebni (»inteligenčni«) del algoritmike, ki obvladuje včeraj in še danes metodologijo in konceptualizem računalniške znanosti. Pri tem je computer science ustrezni termin za raziskovalno in pedagoško dejavnost na ameriških univerzah in institutih. Opravičilo algoritmike, ki je sinonim za dobro (definitivno) opredeljenost matematičnih izrazov, programov in podatkov, je utemeljeno s posebnim podatkovnim orodjem, ki se imenuje računalnik, tj. stroj za procesiranje programskih kodov, ki so lahko aktivni in pasivni simboli, tj. procedure in pripadajoči podatki. Kritika UI pa se napaja v filozofiji, ki je hkrati kritika kartezijanskega horizonta, značilnega za ustroj znanosti v modernizmu. Profesor H.L. Dreyfus je 10. junija 1991 predaval na Univerzi v Gradcu (Avstrija) [Potrč, HUI] o Heideggrovi kritiki umetne inteligence. Heidegger kritizira več stvari hkrati: Husserlovo razumevanje intencionalnosti, kibernetiko in primeijavo človeškega bitja z računalnikom. Simbolni sistemi naravoslovnih znanosti se praviloma utemeljujejo z reprezentacijskimi (predstavitvenimi) procesi (posebnimi jeziki samimi ali govoricami samimi), kjer se pojavlja problem, kako pojasnjevati razmerja simbolov in stvari v svem; ta problem se danes pojavlja mdi v okviru simbolnih sistemov, ki opisujejo modele uma (duha). Gre za tri stališča, ki so vredna pozornosti: (1) Temeljno razmerje bitja s svetom je inten-cionalnost [pripomba avtorja: npr. neke vrste biološka in trenutna mentalna vztrajnost oziroma vztrajanje], ki ni predstavitvena (reprezen-tacijska), je brez predstavitvene vsebine. (2) To, kar oblikuje enoto, so bistva v svem in naše spretnosti (veščine) v rokovanju z bistvi. To je izhodišče praktičnega holizma, ki je v nasprotju s teorijskim holizmom. (3) Simboli imajo pomen le v okviru vsakdanjih pomenskih dejavnosti. Očitoo je, daje stališče (3) izpeljano iz stališč (1) in (2). Heidegger pravi, da imajo simboli pomen (zgolj) zaradi naših dejavnosti, ki so povezane z veščinami. Naspromje predikativnim pomenom oziroma simbolom v Husserlovem pomenu, kjer smo v razmerju (referiranju) s svetom zaradi predikativnih pomenov, Heidegger nasprotuje tako vzročnim relacijam (npr, if-then-izem v matematiki, in zlasti v računalniških, umetno-in-teligenčnih in programskih strukmrah), kot tudi razlikovanju internalizma in eksternalizma. Heideggrova kritika je tedaj usmerjena na predstavitveno, reprezentacijsko intencionalnost, intencionalnost sama pa je po Dreyfusu izredno pomembna v Heideggrovem načinu mišljenja. Preobrat, ki ga Heidegger predlaga po tradiciji, dolgi dva tisoč let, je v prednosti prvobitne inten-cionalnosti, katere bistvo je v dejavnosti, ki temelji na veščinah. Husserlovska intencionalnost je izjemna; pojavlja se le tedaj, ko določena dejavnost ni uspešna, ko določene veščine še ne obvladujemo (npr. v fazi učenja ali v nepredvidenih okoliščinah). Heigegger očita Husserlu, da predpostavlja nekakšna bistva duha, kritizira tiho uvajanje razlike med subjektom in objektom, med predmetom in svetom, fenomenološko redukcijo, Husserlov intemalizem. Intencionalnost je tako v vedenju (obnašanju), kijebiti-usmeije-na. Temeljna intencionalnost je v vedenju in ne v zavesti, je brez metafizične podlage. Uporaba kladiva za zabijanje je pri Heideggm znani primer fenomena. Pri uspešni uporabi kladiva izgine kladivo-orodje v svoji priročnosti. Pomemben je tedaj namen naše dejavnosti in ne predmet sam. Subjekt, ki zabija s kladivom, je brez prepričanja. Ima veščino, da to opravlja, je vpleten v dogodje zabijanja. Tubit je zaskrbljena vključenost v svet, ko je potrebno vedeti kako, a ne vedeti kaj, kjer ni pomembno propozicionalno znanje. Ni razlikovanja med svetom in menoj. To razlikovanje se pojavi šele pri motnjah, ko rokovanje ne poteka brez težav. V čem je tedaj Heideggrova kritika UI? V Descartesovem kognitivizmu. Nasproti Descar-tesovim predstavam oziroma reprezentacijam postavlja Heidegger stvari v uporabi, s katerimi rokujemo. Pri kognitivizmu je fizikalni simbolni sistem realiziran v duševnosti, pri UI pa v računalniku. Kritika se začne z medsebojnim napotovanjem (spoznavanjem) orodja. Kladivo se napotoje na žebelj, žebelj na les, les na gradnjo hiše in hiša na mizarje (if-then-istični predikativni niz). V UI se za veščine in načine rokovanja dodajajo le funkcijski predikati. Tako se osmišljajo izolirana, nepomembna bistva v povezavi z drugimi izoliranimi, nepomembnimi bistvi. Pomembne so le funkcije delov in napotovanje na dele. Descartesov svet je svet atomamih lastnosti. Šele ko se pojavi problem v funkciji kladiva, stopi kladivo kot predmet v ospredje. Heidegger in njegov mterpret Dreyfus poudarjata [HUI], da rokujejo ljudje v UI z osiromašenimi elementi. UI in logika uvajata izolirane predikate in skozi nje razumevata svet v terminih napovedi (aluzij) in v izrazoslovju predikatoega računa. Ker se pri Descartesu interpretacija, pojasnjevanje sveta začenja z notranjim svetom, lahko rečemo, da UI umanjka pomembnost: nastane vprašanje, kako to pomembnost vzpostaviti. Ko se v računalnik vnaša več in več dejstev (bistev), sistem ne postaja in-teligenmejši, temveč se čedalje bolj oddaljuje od pomembnosti. Tudi pravila veščin, ki se vnašajo, so pravila tipa znanj e-kaj in ne znanj e-kako. Inteligenca veščin pa v UI ne obstaja, saj se same veščine upirajo matematični formalizaciji in programiranju. Optimizem, kot je bil napovedan na začetku UI, ni uspel. Zanimivo je, da je Dreyfusu medtem uspelo izdati knjigo Being-in-the-world pri založbi M.I.T. Press [BIW]. Zakaj zanimivo? Winograd in Flores [UCC] navajata kot referenco [WIB] že leta 1986. Ali je Dreyfusova najnovejša knjiga čakala na objavo pri M. I.T. Press kar nekaj let (pet let ali več), da se je morda zgladil spor med Dreyfusom in M.I.T. iz šestdesetih let, ko je Dreyfus v svoji ekspertizi o perspektivah UI (ocena je bila napisana za RAND) primerjal UI z alkemijo [AAl]. V tej oceni je Dreyfus med drugim zapisal tole [MOM, str. 8-9]: »Zgodnji uspehi pri programiranju digitalnih računalnikov, ki kažejo na enostavne oblike inteligentnega vedenja, se povezujejo s prepričanjem, daje razlika glede na inteligentno aktivnost le v stopnji in kompleksnosti; verjame se, da je procesiranje s kognitivno zmožnostjo mogoče formulirati s programom in simulirati na digitalnem računalniku. Poskusi simuliranja kognitivnih procesov pa so naleteli na večje težave, kot se je pričakovalo. Raziskava teh težav odkriva, da se pri poskusu analize inteligentnega vedenja v jeziku digitalne ga računalnika sistematično zanemarjajo tri osnovne človeške oblike procesiranja (meje zavesti, ločevanje bistvo/naključje in toleranca dvoumnosti). Bistveni razvoj v umetni inteligenci bo moral počakati na računalnike popolnoma dmgačne vrste, od katerih so edini obstoječi [možni] prototip slabo razumljeni človekovi možgani. « Zaradi te svoje ocene je imel Dreyfus na M.I.T. velike težave. Najprej je bila preprečena distribucija kritičnega poročila. Študentje in profesorji, ki so delali na robotskem projektu, se niso smeli družiti z Dreyfusom niti pri kosilu. Profesor J. Weizenbaum, ki je tudi dvomil o verodostojnosti značilnih izjav, seje z Dreyfusom skrivoma sestajal doma. Dreyfusa so bolje razumeli v Novosibirsku, na Japonskem in v Bell Telephone. S svojo kritiko UI se je Dreyfus mimogrede dotaknil tudi filozofije biti v okviru postmodernega tematskega sklopa, ki pomeni vobče detronizacijo racionalnosti, konec kar-tezijanskega subjekta in prevlado informacije (znanja) nad teoretsko-abstraktnim kompleksom racionalizma. Zaustavljanje Drey fuso ve kritike s strani njegovih kolegov na univerzi pa kaže na (trenutno?) pomanjkanje profesionalnega etičnega koda, kije še značilnost iztekajočega modernizma ne le na M.I.T., temveč tudi drugod po svetu. V okviru Dreyfusovega predavanja v Gradcu zasledimo v Potrčevem spisu [HUI], ki bržkone spet ni bil slučajno objavljen izven Slovenije, še neko izjavo, ki kaže morda na trdovratno značilnost slovenske kulturne (filozofske) tradicije. Čeprav sega poznavanje Heideggrovega dela v Sloveniji še v predvojno obdobje pa pozornost slovenskih heideggeijevcev za filozofijo vobče upada in to pomanjkanje interesa za Heideggra tudi ni včerajšnje, čeprav interes za Heideggra v svetu narašča. Ali gre morda za kakovosten (novi ideološki) premik iz domene filozofije v domeno kulture, ki bi lahko bil značilnost nekega koncepta nastopajoče slovenske Kulmrgesellschaft? Naslednje vprašanje, ki se ponuja samo po sebi, je, zakaj Dreyfusova nova knjiga Being-in-the-world obravnava prav kompleks biti-v-svetu. Kot kritik UI preučuje Dreyfus seveda tudi inteligenco, ki je reagiranje v vedenju bitja, ki se odziva na trenutne okoliščine v svetu, na tiste, ki bitje vznemirjajo ali bi ga lahko vznemirile. V svojem bistvu je tedaj razprava o biti-v-svetu tudi razprava o tem, kar vulgarno (neprofesionalno) imenujemo inteligenca. Inteligenca je le obči termin v vrsti njenih pojavnosti, kot so npr. v filozofskem jeziku Heideggra analiza tubiti, bit-v-svetu, svetovnostsveta, so-bitin samo-bit, v-bit in še skrb kot bit tubiti. To pa je prvi odsek (Erster Abschnitt) Heideggrovega Dela Sein und Zeit. V okviru petega poglavja z naslovom V-bit kot taka se obravanavata Tu-bitkot razumevanje (par. 31) in Razumevanje in razlaga (nem. die Auslegung, angl. interpretation) (par. 32). Ker je že osnovno Heideggrovo delo Sein und Zeit zgodnji program postmodernizma, lahko le upamo, da bo Dreyfusova Being-in-the-world morda postala tudi temelj pri študiju možnosti prihodnjih inteligentnih artefaktov — ne le po svetu, temveč tudi v krogih domače UI. In tako prihajamo naposled do vprašanja, ki zadeva slovensko usmeritev UI in njeno perspektivo v postmoderni epohi. Osnovno usmerjenost slovenske Ulje mogoče izluščiti iz njenih del (objav, uporabnih artefaktov, mednarodne povezanosti in odmevnosti). Alije ali ni osnovna usmeritev domače UI predvsem sholas- tična? Pridevnik sholastičen seveda ne aludira na pomen srednjeveškega sholasticizma; poudarja pa šolsko, šolniško in vzgojno naravnanost {angl. scholastic attainments); nanašajoč se na dovolj pedantoo prenašanje in posnemanje (modernističnega) znanja, ki je bistveno in značilno za t.i. sekundarno izobraževanje {angl. scholastic meet). Na tem mesm ostaja odprto vprašanje lastoih raziskovalnih pretenzij in povezav s centri, ki oblikujejo postmodernistično paradigmo UI in seveda tudi lastoih izvirnih dosežkov. O tem pa bo lahko povedanega kaj več in bolj konkretno na drugem mestu. Slovenska UI se bržkone ne približuje kritičnosti pogleda Dreyfusa, saj bi bilo zanj potrebno vzpostaviti ne le zahtevnejše, temveč mdi drugačno razumevanje UI. V okviru postmodernosti nastajajo tudi nova izhodišča pri snovanju t.i. inteligentnih informacijskih sistemov. Zanimivo je, da se pridevnik inteligenten čedalje bolj poredko uporablja. Na površje prihaja zavest, da z obstoječimi računalniki ni mogoče simulirati inteligence, lahko pa se uporabi v posameznih primerih vsa razpoložljiva informacija. Gre v bistvu za ad hoc pristop pri razvoju (načrtovanju, programiranju) zahtevnih informacijskih sistemov, kot je npr. japonski projekt elektronskega slovaija, ki vsebuje med drugim operacijo prevajanja stavkov iz enega jezika v drugi jezik. Ta projekt vzpostavlja ne le posebne informacijske standarde, temveč skupaj z njimi, mdi razvojna orodja za doseganje zahtevnih standardov. Šmdij in izpopolnjevanje teh ad hoc informacijskih sistemov bo lahko opravljen šele po njihovi uspešni uporabi na trgih svetovnih jezikov. UI je v prejšnjih desetletjih nastajala (in ponekod še nastaja) predvsem kot Velika zgodba in manj kot znanstveno konsenzualna disciplina. Določen konsenz je dobivala predvsem v lastoi komuni in deloma v komunah s podobno problematiko (npr. v cognitive science). Toda Velike zgodbe so se zgodovinsko razvrednotile ravno na podlagi spekulativnega prepričanja, da je mogoče določen diskurz opravičiti le, če ga legitimiziramo kot nosilca potencialov (npr. inteligence, razuma, osvoboditve človeštva) [PS, str. 80].Znanosti, kot najvišje oblike racionalnosti, so začele same spodkopavati pozicijo razuma. Npr. naravoslovne znanosti so se same odrekle prentenziji na absolutoo resnico, poudarjajoč, da velja resnica le znotraj njihove posebne paradigme (bermenevtike, logosa, metodologije). Takšen razvoj znanosti je tako že nakazal strukmro nastajajoče postmoderne znanosti (kulture). Tudi redefinirani koncept informacije in informacijskega sistema kot majhna zgodba informiranja stvari oblikuje svojo postmoderno paradigmo [IP], ki naj bi razvijala med drugim nove oblike razumevanja informacijskih strojev (orodij, programov) kot artefaktov t.i. postračun alniškega tipa. Ta diskurz, ki se uveljavlja v postmodernem razmerju ob zatonu modernih legitimizacijskih mehanizmov, ima značaj majhne zgodbe, začasnega dogovora, lokahio obliko konsenza in kakor je lahko resnica na eni strani, ni več resnica na drugi [PS, str. 83]. Slovstvo [PS] Debeljak, A., Postmoderna sfinga, Založba Wieser, Celovec-Salzburg (1989). [AAI] Dreyfus, H.L., Alchemy and Artificial Intelligence, The RAND Corporation Paper P-3244, December 1965. [WCD] Dreyfus, H.L., What Computers Can't Do: A Critique of Artificial Reason, Harper & Row, New York (1972). [MOM] Dreyfus, H.L. and S.E. Dreyfus, Mind over Machine, The Free Press, A Division of Macmillan, Inc., New York (1986). [BIW] Dreyfus, H.L., Being-in-the-world: A Commentary on Division I of Heidegger's Being and Time, M.I.T. Press, Cambridge (in press since 1985, appeared finally, in 1991). [HUI] Potrč, M., Heideggerova kritika umjetne inteligencije, Folozofska istraživanja 11 (1991) (40), sv. 1, 91-97. [UCC] Winograd, T. and F. Flores, Understanding Computers and Cognition: A New Foundation for Design, Ablex PC, Norwood, New Jersey (1986). [IP] Železnikar, A,P., Information and Postmodernism, Cybemetica 34 (1991) 67-73. Avtorsko stvarno kazalo časopisa Informatica, letnik 15 (1991) Authors Subject Index of the Journal Informatica, Volume 15 (1991) Članki — Articles Bsi^, M., Izvedba in uporaba posebne funkcionalno zasnovane računalniške tipkovnice za mrežo osebnih računalnikov, Informatica 15 (1991), No. 1, t/'Barle, J. and J. Grad, Design, Implementation and Testing of a Primal-dual Interior Point Method for Solving Linear Programs, Informatica 15 (1991), No. 4, 5-11. u^ojadžiev, D., Meaning, Understanding, Self-reference, Informatica 15 (1991), No. 2, 1-5. i/ßo§njak, S. and L. ŠerešT Case Tools — Software Development and Maintenance Aid: A Survey, Informatica 15 (1991), No. 1, 43- 47. / ^'Bruha, I., Neural Sets: Survey ans Application to Waveform Processing, Informatica 15 (1991), No. 1, 27-42. ^ančer, Vesna, Računalniški podprogrami za računanje lastnih vrednosti in lastoih vektoijev, Informatica 15 (1991), No. 2, 65- 70. '-"Dedič, A., R. Mum, D. P^ček, Digitalizacija in vektorizacija črtnih risb velikih dimenzij, Informatica 15 (1991), No. 4, 60- 68. '/Djonova Popova, Iskra, Routing Algorithms for Packet Switched Networks, Informatica 15 (1991), No. 2,6-13. y y' ^'Dobnikar, A., Jelena Ficzko, Mira Trebar, Ocenjevano učenje v nevronskih mrežah, Informatica 15 (1991), No. 4, 53-59. ^ Dujmović, J.J., Primena višedimenzionalnih nizova u programima za merenje računarskih performansi, Informatica 15 (19^1), No. 3, 10-14. Gams, M. and V. Križman, The Principle of Multiple Knowledge, Informatica 15 (1991), No. 2, 23-28. Karalič, A. and V. Pirnat, Significance Level Based Classification with Multiple Trees, Informatica 15 (1991), No. 1, 54-58. ^ 'Kobold, Viktorija and M. Špegel, Monitoring of Real-time Systems, Informatica 15 (1991), No. 1, 1-10. {^Kolbezen, P., P. Zaveršek, Hierarhični večprocesorski sistem. Informatica 15 (1991), No. 1, 65-76. ^--'Kononenko, L, Zvezne Bayesove nevronske mreže, Informatica 15 (1991), No. 2, 49-53. ^'Lakner, Barbara, Določanje položaja teles v prostoru iz ene same 2-D slike, Informatica 15 (1991), No. 1, 77-82. ^^Lavrač, Nada, Uporaba predznanja v induktivnem učenju, Informatica 15 (1991), No. 4, 69-78. '"■^onardi. Michele, A. Klofutar, I. Gorkič, Povezava osebnega računalnika z robotskim krmilnikom ASEA-IRB, Informatica 15 (1991), No. 4, 84-88. Likar, M., N. Guid, Planiranje s Prologom, Informatica 15 (1991), No^ 36-42. 2^,-Memik, M. and V. Žumer, Implementation of Denotational Semantics, Informatica 15 (1991), No. 1,48-53. t—'"^Meško, Tjaša, Pattern Recognition Using Kohonen Maps and Multi- layer Perceptrons, Informatica 15 (1991), No. 4, 12-18. «-•^rdalj, S. and V'^Jovanovic, Structured Object-oriented System Decomposition, Informatica 15 (1991), No. 1, 22-26. Popov, O.B., Consciousness as a Perequisite for Knowledge, Informatica 15 (1991), No. 3, 1-8. •"/Popov, O.B., Modes for Reasoning about Consciousness, Informatica 15 (1991), No. 4,1-4. i/'Pučko, Marjeta, Analiza zmogljivosti mehanizma za kontrolo pretoka v mrežah za prenos podatkov, Informatica 15 (1991), No. 3, 63-68. Radovan, M., ER jezik: prijedlog proširenja. Informatica 15 (19912^No. 3, 44-53. ^ ^ajkovič, V., E. Delidžakbva-Drenik, B. Urh, Primerjalna analiza treh orodij za izgradnjo in uporabo baze znanja ekspertnega sistema, Infor- matica 15 (1991), No. 3, 22-28. ^Raman, S., L.M. Patnaik, J. Šile, and M. Špegel, Parallel Implementation of VLSI Circuit Simulation, Informatica 15 (1991), No. 2, 14-22. Robič, B., Polona Blaznik, O vzporednem množenju matrik, Informatica 15 (1991), No. 1, 59-64. Trstenjak, Natalija, B. Žalik, N. Guid, Algoritem za pretvorbo telesa predstavljenega z ovojnico v predstavitev z osmiškim drevesom. Informatica 15 (1991), No. 2, 54-64. ^ Urbančič, Tanja, Možnosti za vodenje sistemov s pomočjo metod umetne inteligence, Infor-maüca 15 (1991), No. 4, 79-83. Zupan, J., »Slonček«, program za geslenje slovenskega teksta. Informatica 15 (1991), No. 3, 15-21. J Zaveršek, P., P. Kolbezen, Dinamično dodeljevanje procesov na polju transputeijev. Informatica 15 (1991), No. 4, 43-52^ ^ UZalik, B., N. Guid, A. Tibaut, A. Vesel, Algoritem za določitev povezovalnih funkcij krivulj B-zlepkov in NURB krivulj v polinomskem času. Informatica 15 (1991), No. 3, 54-62. Železnikar, A.P., Informational Models of Dictionaries I, Informatica 15 (1991), No. 1,1121. Železnikar, A.P., Informiranje stvari, Informatica 15 (1991), No. 2, 29-39. Železnikar, A.P., Informiranje stvari II, Informatica 15 (1991), No. 3, 29-43. Železnikar, A.P., Formal Informational Principles, Informatica 15 (1991), No. 4, 19-35. Žerovnik, J., Algoritem ohlajanje, Informatica 15 (1991), No. 2, 40-48. Knjižne recenzije — Book Reviews Knjižne novice. Informatica 15 (1991), No. 1, 88-90. Dujmović, J.J., O knjizi i njenom autoru: Anton P. Železnikar, »On the Way to Information«, Slovensko društvo Informatika, 1990. Informatica 15 (1991), No. 3, 69-70. Motaln, V., On ther Way to Information (Na poti k informaciji), Informatica 15 (1991), No. 2, 79. Motaln, v., A.P. Železnikar, Vprašanja (kijih je postavil dr. V. Motaln avtorju na tiskovni konferenci v Mladinski knigi, 29.1.1991. Informatica 15 (1991), No. 2, 79-82. Souček, B., Recenzija knjige: Anton P. Železnikar, On the Way to Information, Part 1, Ljubljana. Informatica 15 (1991), No. 2, 78- 79. Novice in zanimivosti - News Železnikar, A.P., Longman Dictionaries, Informatica 15 (1991), No. 2, 71-72. Železnikar, A.P., Projekt j aponsko-nemškega slovarja, Informatica 15 (1991), No. 2, 72. Železnikar, A.P., Konzorcij za leksikalne raziskave, Informatica 15 (1991), No. 2, 73. Železnikar, A.P., Genelex: Eureka za lingvistično inženirstvo. Informatica 15 (1991), No. 2, 73-74. Železnikar, A.P., Oblikovanje leksikalnih modelov pri IBM, Informatica 15 (1991), No. 2, 74-75. Železnikar, A.P., Kitajski elektronski slovar. Informatica 15 (1991), No. 2, 75. Železnikar, A.P., Slovenski slovnični in besedni pregledovalnik, Informatica 15 (1991), No. 2, 75-76. Železnikar, A.P., Japonska pobuda za sodelovanje pri razvoju in prodaji elektronskih slovarjev, Informatica 15 (1991), No. 2, 76- 78. Železnikar, A.P., Dvajsetletnica kongresa IFIP'71, Informatica 15 (1991), No. 3, 70. Železnikar, A.P., 64 let dvoma o nastajanju umetne inteligence. Informatica 15 (1991), No. 4, 89-92. Informatica Editor-in-Chief anton p. 2ELEZNIKAR Volaričeva 8 61111 Ljubljana Yugoslavia PHONE: ( + 38 61) 21 43 99 to the Associate Editor; The Slovene Society Informatika: PHONE: ( + 38 61) 21 44 55 TELEX: 31265 yu icc FAX: ( + 38 61) 21 40 87 Associate Editor RUDOLF MURN Jožef Stefan Institute Jamova c. 39 61000 Ljubljana Editorial Board Publishing Council SUAD ALAGIC Faculty of Electrical Engineering University of Sarajevo Lukavica - Toplička bb 71000 Sarajevo -- - DAMJAN ÉOJADZIEV Jožef Stefan Institute--.': " ^ Jamova c. 39 61000 Ljubljana JOZO DUJMOVIC Faculty of Electrical"^Engineering University of Belgrade Bulevar revolucije 73 11000 Beograd JANEZ GRAD Faculty of Economics University of Ljubljana Kardeljeva ploščad 17 61000 Ljubljana BOGOMIR HORVAT Faculty of Engineering University of Maribor Smetanova ul. 17 62000 Maribor UUBO PIPAN Faculty of Electrical Engineering and Computing University of Ljubljana Tržaška c. 25 61000 Ljubljana TOMAŽ PISANSKI Department of Mathematics and Mechanics University of Ljubljana Jadranska c. 19 ^ 61000 Ljubljana '' - - - . "V fx ', ■ ■ - ^ ÒLIVÉR POPOV Faculty of Natural Sciences and Mathematics C. M. University of Skopje Arhimedova 5 91000 Skopje , ^ . J " SAŠO PREŠERN 3 ' PAREX, Institut for Computer Engineering and Consulting Kardeljeva 8 61000 Ljubljana VIUEM RUPNIK Faculty of Economics University of Ljubljana Kardeljeva ploščad 17 61000 Ljubljana BRANKO SOUČEK Faculty of Natural Sciences and Mathematics University of Zagreb Marulicev trg 19 41000 Zagreb f • TOMAZ banovec Zavod SR Slovenije za statistiko Vožarski pot 12 61000 Ljubljana ANDREJ JERMAN-BLAZIC ■ fskra'^-Telematika Tržaška c. 2 61000 Ljubljana BOJAN KLEMENČIČ Turk Telekomunikasyon E.A.S. Cevizlibäg Duragy, Yilanly Ayazma Yolu 14 Topkapi Istanbul, Turkey stane saksida Institute of Sociology University of Ljubljana Cankarjeva ul. 1 61000 Ljubljana JERNH VIRANT Faculty of Electrical Engineering and Computing University of Ljubljana Tržaška c. 25 61000 Ljubljana Informatica is published four times a year in Winter, Spring, Summer and Autumn by the Slovene Society Informatika, Tržaška cesta 2, 61000 Ljubljana, Yuf^oslavia. A Journal of Computing and Informatics C O N T EN T S Modes for*^Reasoning about Cosciousness Design, Implementation and Testing of a Primal-dual Interior Point Method for Solving Linear Programs Pattern Recognition Using Kohonen Maps and Multi-layer Perceptrons Formal Informational Principles Planning with.Prolog (in Slovene) Process Allocation in the Multitransputer Network (in Slovene) Reinforcement Learning in Neural Networks (in Slovene) Digitaiization and Vectorization of Large Scale Drawings and Maps (in Slovene) The Use of Background Knowledge in Inductive Concept Learning (in Slovene) Towards Controlling Dynamic Systems Using AI Methods (in Slovene) Computer Link for ASEA' Robot Controller (in Slovene) O.B. Popov J. Barle J. Grad Tjaša Meško 12 A.P, Zeleznikar 19 M. Likar 36 N. Guìd P. Zaveršek 43 P. Kolbezen A. Dobnikar 53 Jelena Ficzko Mira Trebar A. Dedič 60 R. Mum D. Peček Nada Lavrač 69 Tarija Urbančič 79 Michele Leonardi 84 A. Klofutar /. Gorkič NEWS: 64 Years of Doubt of AI (in Slovene) A.P. Zeleznikar 89 Authors Subject Index of the Journal Informatica, Volume 15 (1991) 93