Informatica A Journal of Computing and Informatics The Slovene Society INFORMATIKA Ljublana Informatica A Journal of Computing and Informatics Subscription Information Informatica (YU ISSN 0350 - 5596) ìs published four times a year in Winter, Spring, Summer and Autumn (4 issues). The subscription price for 1990 (Volume 14) is US$ 30 for companies and US$ 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, Ljubljana. Informacija za naročnike Informatica (YU ISSN 0350-5596) izide Štirikrat na leto, in sicer v začetku januarja, aprila, julija in oktobra. Letna naročnina v letu 1991 (letnik 15) se oblikuje z upoštevanjem tečaja domače valute in znaSa 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-5184L " 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 2 Maj 1991 YU ISSN 0350-5596 Informatica Časopis za računalništvo in informatiko VSEBINA Meaning, Understanding Self-reference Routing Algorithms for Packet Switched Networks Parallel Implementation of VLSI Circuit Simulation The Principle of Multiple Knowledge Informiranje stvari Algoritem Ohlajanje (Simulated Annealing) Zvezne Bayesove Nevronske mreže Algoritem za pretvorbo telesa predstavljenega z ovojnico v predstavitev z osmiškim drevesom Računalniški podprogrami za računanje lastnih vrednosti in lastnih vektorjev Novice in zanimivosti o elektronskih slovarjih Knjižne recenzije (A.P. Železnikar: On the Way to Information 1; Na poti k informaciji 1) (z nekaterimi odgovori avtorja) Z), Bojadžiev 1 Iskra Djonova Popova 6 S. Ramar 14 L M. Pamaik I Sile M. Špegel M. Gams 23 A.P. Železnikar 29 J. Zerovnik 40 I. Kononenko 49 Natalija Trstenjak 54 B. Zalik N. Guid Vesna Čančer 65 A.P. Železnikar 71 B. Souček 78 V. Motaln A.P. Železnikar MEANING, UNDERSTANDING, SELF-REFERENCE Keywords: Meaning, Chinese room argument, self-reference Damjan Bojadžiev Institute Jožef Stefan, Ljubljana Arguments against the possibility of machine understanding as symbol manipulation tend to downplay the internal structure of the computational system. The case for genuine mechanical understanding can be made more appealing by considering the levels of (self)-representati on and the self-referential mechanisms operating between them. Pcmcfi, razumevanje, samo-referenca: Argumenti proti možnosti mehaničnega razumevanja kot manipulacije simbolov obiCajno podcenjujejo noTranjo strukturo programskega sistema. Možnost resniSnega mehaničnega razumevanja se zdi bolj smiselna, £e upoštevamo nivoje (samo)reprezentacije in samo-referenčne mehanizme, ki delujejo med njimi. 1. Introduction Mainstream tradition in philosophy and more or less educated common sense maintains that there is (and will-always be) a huge gap between the cognition, and in particular the linguistic abilities, of men and machines (computers as their most advanced representatives). It is said that, by manipulating symbols, computers might at most succeed in producing an illusion of understanding: appearing to understand what is being said/typed to them and what they themselves say or print, but without actually doing so. Although the current state of the art of artificial intelligence and natural language understanding does not make this a burning issue, many different positions have already been taken on it, presumably because the possibility of machine understanding challenges our current linguistic and cognitive supremacy, and because of the extent to which it affects our self-image as cognitive beings, our understanding of ourselves. The prospect of mechanical understanding apparently tends to have a negative effect on our conception of ourselves, though it is not obvious that it should do so. The indignant position that we are not "mere machines" would only go along with what is sometimes called weak AI, the position that AI programs might only provide superficial I/O simulations and need not be regarded as actual models of human cognitive performance. The present paper is an overview of some typical arguments, notably yet another debunking of Searle's "Chinese room" argument (section 2) and a compilation of some programatic answers, centering on the notion of self-reference (section 3). The main thesis elaborated there is that the connection between meaning, understanding and self-reference goes through the subject of that understanding, which is construed as an effect of self-referential mechanisms in a metalevel architecture. If the objections against computational understanding are summarized by saying, as Searle does, that computers have syntax but not semantics, and that syntax alone is not sufficient for semantics [19:34], the answer can be surmarized, following Casti [4:334-5], by saying that syntax and self-reference may add up to semantics. 2. Real Understanding The standard objection against computational understanding by means of symbol manipulation in a formal representational system says: computers themselves don't mean anything by their tokens (any more than books do) - they only mean what we say they do [7:32-3]; symbols must mean something to the system performing the operations [6]. The second quotation comes from the philosopher F. Dretske, who helps us keep a cool head in such discussions by reminding us that computers are tools, and that we should not get carried away in attributing conceptual or cognitive capacities to them. According to Dretske, the meaning of internal signs consists in their correlation with external conditions, and affects (through learning) the way the system manages the signs. (His negative conclusions about computational cognition seem to rest on the premise that robots can't learn) A much debated argument about machine understanding is the thought experiment suggested a decade ago by the philosopher J. Searle, known as,the Chinese Room argument [19], Searle imagines that Vie could pass a (Turing) test for understanding eg. Chinese in the following way, although he does not actually know the language: Isolated in a room, Searle would carry out instructions (in English) for manipulating incoming strings of Chinese symbol s using given strings of Chinese data, and producing answer strings such as would be given by a speaker of Chinese. It is important in this setup that the instructions only say how to manipulate formally characterized Chinese symbols, and thus do not interpret them (in English). Searle then claims that, just as he would not have understood a word of the Chinese, although he would appear to do so from the point of view of the external questioner, a computer executing the same instructions would also not understand anything^: In the Chinese case, the computer is roe, and in cases where the computer is not me, the computer has nothing more than I have in the case where I understand nothing [Minds, Brains and Programs]. It seems obvious that Searle would indeed not come to understand Chinese in this way, although even that might be allowed as an abstract possibility^. More importantly, a computer taking Searle's place would indeed also not understand anything, but only on Searle's peculiar usage of the word 'computer". Searle seems to think of a computer as an "empty" processor, without programs and data: he almost seems to identify with the CPU; more accurately, he identifies with the interpreter (in the computational sense of the word) of the formal instructions for manipulating Chinese symbols. No one has ever claimed understanding (of Chinese or anything else) for a computer in this sense; it is the progratimed computer (plus data) that might be said to understand - this is what Searle calls the systems reply to his argument'. Torrance aptly summarizes it by relating it to an everyday situation: it is not the washing machine's motor which washes clothes, but the washing machine [22:15]. The part I find interesting about the Chinese room thought experiment^ is Searle's attempt to identify with an understanding computer. According to strong A!, which he is trying to refute, computational understanding models human understanding, so that some identification should be possible; Searle only makes a type error in the particular identification he imagines. The identification does not go through because we do not.recognize a (formal) description of what it is for symbols to be meaningful to us in the work of the fast, dumb homunculus whose place Searle thinks he could take. The systems reply to the "experiment" suggests another identification, with the whole Chinese room (or, in a parallel processing version with some Chinese hotel). A variant on this would be identification with (the perspective of) the simulated speaker [10:378]. These possibilities correspond to the two senses in which we speak of symbols being meaningful to us: meaningful to our whole cognitive system or meaningful to some particular point within the system: consciousness, self, mind's eye or I, whatever; such labels only presume what they appear to explain. A short argument for the connection between understanding and "selfhood" can be found in Haugeland [8:240]: ego involvement may be integral to understanding, and ego involvement requires a self-concept. A more technical one can be built around the notions of levels of representation in a symbolic system and the relationships between such levels. An early, idealized attempt to discern some analogue of subjectivity within a formal system was made by Hofstadter, in his 'Godei. Escher. Bach' [9]. He proposed an arithmetical, Pythagorean version of the interplay between levels as engendering the self: it is formed when it can reflect itself [9:709]. The (meta)arith[netical basis of the slogan were the effects of sentential self-reference for particular predicates: the "strange loop" connecting the (un)-provability of a senténce and the sentence's assertion of its own (un)provability. In hard(er) computer science, ideas about the' effects of incorporating the meta-level in a formal representational systeni were further developed under the label meta-level architectures^. 3. Self-Referential Systems If the symbols of a system are to be meaningful to the system itself, it must first be able to consider them and the way it manipulates them. Thus, Perlis C15] has suggested that a system would use symbols meaningfully if it could consider its own symbolic forms and distinguish between its symbols and what they symbolize. Both conditions require second-order representation (naming or otherwise representing the symbols themselves) and could thus be met in a system with quotation^. The suggestion may appear singularly inappropriate, since the alleged problem with computational understanding was that a computer has no access to what its symbols symbolize , in which he is the agent, he will simply internalize (memorize) the other components: The individual then incorporates the entire system. There isn't anything at all to the system that he does not encompass ... All the same, he understands nothing of the Chinese, and a fortiori neither does the system, because there isn't anything in the system that isn't in him [Minds, Brains, Programs]. Searle rightly says that he feels somewhat embarassod to give this 'quite simple' reply: paraphrasing to bring out its curiously childish nature, Searle seems to be saying: "OK, if understanding is not in me but in (my relationship to) these other things outside me, then I'll just put them inside me". Searle scorns to be confusing physical with functional containment: he would still be only the agent in this internalized (sub)system, through which he would now be speaking in tongues. The argument The whole doesn't understand So, the parts don't. only seems to bug the question: that is exactly a situation in which the whole doesn't understand while parts do. A. Searle's "experiment" does dramatize some issues concerning the formalization of meaning and understanding: where or how is meaning present in a formal system (program), and who or what is that meaning present to. Common sense answers invoke the programmer: it is his knowledge of meaning that goes into setting up a formal system, and the meaning captured in it is present to him (as attributed meaning). Other attempts rely on some kind of (w)holism: the meaningfulIness of individual symbols is an effect of the whole system, deriving from the relationships of individual symbols with indefinitely many other symbols and with the procedures which manipulate them. Symbols would then be meaningful to the system if it considered not only their immediate, explicit, locally computable ... properties, but also their relationships with indefinitely many other symbols; cf. Hofstadter- in [9:582]. 5. A survey of three early attempts at computational introspection (Smith's introspective LISP, Weyhrauch's introspective first order logic, FOL, and Doyle's model of introspective action and deliberation) can be found in [2]. More recent efforts are collected in the proceedings of the 1986 workshop on meta-level architectures and reflection, sponsored by the COST-13 project Advanced Issues in Knowledge Representation [13]. 6. Perlis uses a more general idea of quotatation, according to which not only internal tokens, but any internal (mental) object or process can be "quoted" (or reflected, as he also says, meaning something similar to what Hofstadter calls jumping out). 7. The ideas of language levels (use and mention (quotation)) and disquotation (truth) are basic to Davidson's semantics for natural language [5]; I hadn't seen Perlis's point in my estimate of the usefulness of Davidson's semantics for computational understanding of language [3]. 8. The basic, low-level view of the world, at which we have no representation of ourselves, could be compared to the perspective of the "man with no head" in [10:23-33]. The higher level consists of additional representational structure, which is basic to what Smith has to say about the self-referential mechanisms of the self. In the arithmetical ease, considered by Hofstadter, there is no additional representational structure on the higher level, and it is the Godei code which provides "additional", meta-arithmetical interpretations. 9. The importance of introspective mechanisms in evolutionary biological engineering was pointed out by Lycan: Parallel processing, time-sharing and hierarchical control, all vital to the fabulous efficiency of such complex sensor-cognition-motor systems as we human beings are, individually and together require a formidable capacity for internal monitoring ... As a matter of engineering, if we did not have the devices of introspection, there would be no we to argue about,' or to do the arguing [Consciousness:72-3]. References 1. Barwise, J., Perry, J., Situations and Attitudes. HIT Press 1983 2. Batali, J., Computational Introspection, MIT A! Memo 701, 1983 3. Bojadžiev, D., Davidson's Semantics and Computa- tional Understanding of Language, Grazer Phi Iosophi sehe Studien, Vol.36, 1989 4. Casti, J.L., Paradigms Lost: Images of Man in the Mirror of Science. U.Morrow & Co. 1989 5. Davidson, D., Inquiries into Truth and Interpre- tation, Oxford Univ. Press 1984 6. Dretske, F., Machines and the Mental, Am. Phil. Assoc. Presidential Address, 1985 7. Haugeland, J., Mind Design. Bradford Books 1981 8. —-........., Artificial l.ntel I igence: The very Idea. Bradford Books 1985 9. Hofstadter, D.R., Godei, Escher, Bach: An Eternal Golden Braid. Basic Books 1979 11. Jackendoff, R., Semantics and Cognition, ^'IT Press 1983 12. Lycan, W.G., Consciousness, Bradford, MIT 1987 13. Maes, P., Nardi, D. (eds.), Meta-Level Architec- tures and Reflection. Elsevier 1988 14. Perils, D., Languages with Self-Reference I: Foundations, Artificial Intelligence 25, 30122, 1985 15. ......, How Can a Program Mean?, in Procce-d- ings of the 10.^" IJCAI, Vol.1, Milano 1987 16. Perry, J., Self-knowledge and Self-r^epresenta- tion, in Proceedings of the 9. IJCAI. Vol.2, Los Angeles 1985 17. Searle, J., Minds, Brains and Programs, Behavioral & Brain Sc. 3, 1980; rep-i-tod eg. in [7] 18. .........., Minds, Brains and Science, The 1984 Reith Lectures, British Broadcasting Corporation 1984 19. .........., Is the Brain's Mind a Computer Pro- gram?, Sc. Am. Vol.262 No.1, Jan. 1990 20. Smith, B.C., Varieties of Self-reference, in J.Y.Hal pern (ed.). Theoretical Aspects of Reasoning about Knowledge. Proceedings of the 1986 Conf., Morgan Kaufmann 1986 21. Steels, L., Meaning in Knowledge Representation, in [13] 22. Torrance, S. (ed.), The Mind and the Machine - Philosophical Aspects of Artificial Intelligence. Ellis Horwood 1984 10. ..............., Dennett, D.C., The Mind's I - Fantasies and Reflections on Self and Soul (1981), Penguin 1982 ROUTING ALGORITHMS FOR PACKET SWITCHED NETWORKS Keywords: Routing Algorithms, Packet Switched Networks Iskra Djonova Popova Research Center for New Technologies Macedonian Academy of Sciences and Arts Skopje V Abstract: In this paper a short survey of the routing pi-oblem in packet-switched networksisprovided. A number of shortest path type procedures for several networks are presented (ARPANET, TYMNET and TRANSPAC). An optimal routing ap' proach for the networks with stationary input traffic s tati s tics is itroduced as a more sofisticated alternative. The interaction between the flow control sheme and the routing algorithm in the network is shown as a chalenge for development of a class ofalgorithms that jointly addresses the problem of routing and flow control. 1. INTRODUCTION Packet switching, [1], have been inspired by the idea of sharing communication channel capacityacross a number of users by implementing the same time slicing philosophy that had earlierproved so sucessfull in sharing the execution power of a single processor across many users processes. Every user node thatisconected to a packet switched common carrier makes a contract with the carrier (i.e., follows standard protocols) to hand him bit streams already segmented (packetized), with each packet supplemented with a header saying among other things, to which user node he whishes the packet delivered. The consequent design is then a net-workwhich handles small pieces of information (packets) at the highest possible transmission rates. Packet switchingdoes allow the carrier to offertotheusermoreoftheaccess path function, freedom in buffering and delayed delivery, [2]. Such a network can be reconfigured at tremendous speed, i.e. reconfigured in the sence of providing connections between different dis-patchingpriorities oruseing different routs. The routing of packets from a source node to a destination node is an important issue in the design ofpacket switched networks. The routing problemconsistsofhowto allocate the available resources in the network in order to accomplish the transsmision of the information offered in the nodes while performing the best possible service. The objective is to optimize the mcfin packetdelayatall levels ofthe network load, The effect of good routing is to increase throughput for the same value of avarage delay per packet under havy load conditions while decreasing average delay per packet under lighter load conditions. 2, CLASSIFICATION Th e r e a r e a n u m b e r o f wa y s to cl a s s i fy r o u t i n g algorithms. One of the possible classifications relates to wether they change routs in responce to the traffic input patterns. In static routing algorithms, the path used by the sessions of each origin-destination pair is fixed regardless of traffic conditions. This type of algorithm cannot achieve a high throughput under a broad variety of traffic input patterns. The idea behind the adaptivei\)uling algorithms is to change the rou ts in response to network congestion and guide the traffic between origins and destinations around the pointof overload. The static versus adaptive classification is particulary vague, since all networks provide some type of a da p ti v i ty to accora od a te to p o 1 o gi ca 1 eh a n ge s ( 1 i n k a n d/o r n o d e coming up or going down, new topologies being established). . Another way of classification is to devide them into centralized and distibuted. In centralized algorithms routing strategies are prepared cen trai ly a t a ce n tra Hzed n e two rk r o u ti n g ce n te r (NRC), while in distributed tehnicques the strategyisprepared throughout the network. The centralized method suffers from high communication overhead, and must deal with the problem of handling link and node failures. An even more serious problem is how to handle the failure of the NRC itself. It appears that distributed routing avoids some of these problems. In this case each node makes its own routing decision based on the information recieved from its neighboring nodes. One potential problem hereisthatinconsistentroutingpaths can cause looping of packets and possibly deadlocks. A different classification could be made according to the kind of information used when implementing the routing algorithm. It is either local, i.e., only the locally available information at the nodes is used,or global, when the comprehensive knoledge about network performance is used. While routing pocedures can be setup within the network more or less independently of the protocols seen by the users (i.e., the devices external to the network), the choice of an appropriate routing procedure is influenced, to someextent,by the transportprotocols operating atthenetwork/user interface, [3]. It is convenient to classify these as either virtual circuit-oriented or message (datagram) oriented. In the former case, a virtual circuit is set up for each new session, The virtual circuit appears to the external devices as if it were a dedicated line; under normal operation, individual data packets arrive at the destination in the proper sequence. However, within the network, packets from many different virtual circuitü are generally sharing the same communication lines. In the message-oriented case, communication is on a message-by-message basis. Each message or packet (often called a datagram) may travell along different routs. Therefore it must contain its own destination address. Figure 1 illustrates virtal circuit versus datagram network. " nil 1 pucVfl ìrf'-^ a Figure la Rout.irio In ciatagrarn nfstwork. Two pockois of tho same usor pair cjjri traval along diffwisnt loutot.. Figure 1 b. Floutiit^ In a virtual circuit ii^work. All pocketB of each virtual circuit uoc th» aame path. 3, FUNCTIONS OF ROUTING PROCEDURES In an idealized situation where all parameters ofthe network are as,sumed to be known and not changing, it is possible to determine a static routing strategy which minimizes average network delay. The routing problem posed in this form is equivalent to the multicommodity How problem, [4]. Changingsituationsin r6alnctAvork.s,such a,s a line failure orchangein the traffic di.stribution, necessate some degree of adaptivity. .'\ny adaptive routing procedure must perform a number of functions listed below. 1. Measurement ofthe network parameters pe r t i n e n t to th e ro u tin g s tra teg\'. 2. Reporting the local state to neighbors or t o 1 h e p o i n t o r p o i n t s a t V/ h i c h r o u t i n g CO m p u ( a -tion take place. 3. Finding optimum niuts bused on the information recieved. Constructing the routing tables to detemine which output line to use to route a packet towards ii:s destination. . Typical information thatis measured and used in routingcomputationconsists of states ofconi-munication lines, estimated traffic, link delays, avaJiable resources (line capacity, jjodal buffers) etc. There is a huge number of possible combinations in using this information and making tlie routing decisions. The variety is partly due to historical reasons and partly to the diversity of needs in different networks. The problem of routinghas been investigated using different approaches. Some are based on heuristics (e.g shortestpath algorithms) while others formulate the routing problem as one of optimal control and than attempt to solve it using standard optimization tehnicque. In section 4 several routing procedures implemented in various packet-switched networks will be described, and in section 5an optimal routingapproach of the routing problem will be given. 4. SEVERAL ROUTING PROCEDURES USED IN PRACTICE A. ARPANET was created in Ì969 as an experiment in computer resource sharing. It is a distributed datagram network with at least two paths between any pair of nodes. The original routing algorithm was an ambitious, distributed, adaptive procedure thatunfortunatelyhad some fundamental flaws that were corected in 1979 when the algorithm was replaced by a new version, [5]. Both ARPANET algorithms are based on the notion of a shortest path between two nodes. Here each communication node Is assigned a positive number called its lenght. The path between two nodes has a lenght equal to the sum of the lenghts of its links. Each packet is routed along a minimum lenght (or shortest) path bet ween the origin and the destination node of the packet. The idea here is that, if the lenght of each link is representative of the delay on the link, than a shortest path contains relatively few and uncongested links, and is therefore desirable for routing. The route calculation is performed in distributed manner, with each node basing its calculation on local information together with calculations made at every other node. Each update is transmitted toall nodes by the simple, but a reliable method, the so called flooding technique. Anode broadcasts an update message to all nodesbysendingthe message to all its neighbors except to the one from which it was recieved, in turn they send the message to their neighbors, etc. ARPANET algorithms are prone to oscillation. The phenomenon is explained by the idea that selecting routes through one area of the network iricrcasc.s the lenghts of the corcspoiid-ing links. As a result, at the next routing update the algorithm tends to select routes through different areas. This makes the first area desirable atthesubsequentroutingupdatewithan oscillation resulting. The feedback effect between link lenghts and routing updates was a primary flaw oftheoriginal ARPANET algorithm that caused dificulties over several years and evenlually led to its replacemant. The latest algorit hm is also prone to oscillations, but not nearly as much. In particular this algoritham solved the following problems in the original one: 1) The delay measurment pn>cedure wns changed. An instantenious measurement of the queue lenght ill the old algorithm was replaced by the measurment of the actual delay of each packet crossing the link. Each link lenglit is updated periodically every 10 seconds, instead of evet-^^ rZSms., and is taken to be the avnrage packet delay on the link during the prcccding 10 second period. The avarage dclfiy has been proved to be the best informa tion policy for the minimum delay algoritlim, [6]. 2) The algorithm for finding the shortes path spanning tree was replaced by the so called shortest path first algorithm which is 1>ased on oneatributed toDijkstra,[7]. The important addition to the basic algorithm is that changes in n e tAvo r k t o p o 1 o gy o r ch a r a c t e r i s t i c s r e q u i r c o n 1 y an incremental calculation rather then a complete recalculation of all short paths. 3) The inten'al between two succesive exhange of the shortest distances among neigbor-ing nodes was changed from 625ms. to 10s. To reduce the amount of communication overhead involved in this information exhange, the 10s. avarage linkdelay measurements are not always transmited. Only when the change in link delay since the last transmission exeeds a certain ti^hold,does a new transmission take place. The treshold is reduced as time increases since the previous transmission. I^ou ti ng a Igori th m, as i t p resen tly exis ts i n the ARPANET, is a greedy one. Switches attempt to grab the best resources (the fastest routes) without regard to their utilization or tlie effects on neighboring-switching. Ause of a congestion-based metric instead of delay could alleviates these problems, [8]. A replacement of the exist;ing algorithm is beingplanned with a new one which uses multi- pie paths for the same origin destination pair. Furthermore,trafficisdevided in several service classes each routed independently of the others. Thepathscorresponding to an origin-destination pair, and service class are updated over fairly longtime intervals. Because of the use of multiple paths, this type of algorithm is capable of higherthroughputthen the existingone. B. TYMNET is a computer communication network developed in 1970 by Tymsharc, Inc. of Cupertino,California. Al most all nodes are connected to at least two other nodes giving the network an alternate path capability. Routing is set up centrally on a virtual circuit basis by a supervisory program running on one of the four network routing centers. The routing algorithm is based on the shortest path metod, and is adaptive like the ARPANET algorithm.?. Unlike these algorithm s this one does not have poten tial of oscillation, primarely due to the use of virtual circuits rather then datagrams. A routing decision in TYMNET is needed only at the time a virtual circuit is set up. The Network routng center (also called the supervisor) ass ignes a virtual circuit to each sessiom by calculating the minimum cost path connecting the origin and the desti nation nodes of the virtual circuit Integer-valued costs are asigned to each link. The cost assignments depend on the line speed, the line utilization as well as other factors, [9]. In the absence of overloading the algorithm tends to select the shortest path with highesttransmissionspeed. As more users come on the network, the lower speed link begin to be used as well. In lightly loaded situations, users tend to have relatively shorter time delays through the network. The minimum hop paths, favored in the lightly loded ease, also tend to be more reliable than ones witli more links. Once the path has been selected, the virtual circuitis assigned an 8-bitlogical record number on each link it traverses. This allows up to 256 users or channels to share any one link. In addition, one number or channel is reserved for a node to communicate with supervisor and one channel is resei-ved for communica tions with the neighboringnodes. The NRCnotifies each of the nodesalong the path and the necessary information is entered in each node's routing tables. These tables are structured as shown on Figure 2, (Eight possible logical record numbers only havebeenassumed for simplicity.) In the original version of TYMNET (TYMNET I), the operating NRC maintainse an image of the routing tables ofall nodes and explicitly reads and writes the tables in the nodes, In the latter version (TYMNET 11), the nodes maintain their own tables. bipi.it horn lini- 1 ChjIpijI to tj'ifsi ——-> P.H1 5 \ — O Z 0 1 C -H — £ C - lirik 1 8 Input port S onto cliannal 3 on link 1. At noda 8 Incoming charm«! 3 ia mapped into outgoing channel 6 on link 2. At nod« 11, incoming channel » i» mopped into output port 7. The TYMNET algorithm is well thought out and has performed well over the years. A potential concern is its vulnerability' to failure of the networkrouting centre which is handled by using backup central nodes. C. TRANSPAC is the French public packet-switched network. It is a virtual circuit oriented sy,stem which u,ses partially decentralized routing algorithm, using a minimum cost, i. e, shortest path criterion. Link costs arc defined in terms of link resource utilization. The concept used is similarto"delta routingalgorithm" suggested by Rudin, [10]. Each node consists of a control unit ( CU ) to w h i eh a re a ta eh e d a n u ni b e r o f s w i teh i n g units (SU). Each incident link is controled by an SU, which executes all dat^i link procedures, Routingis handled by the CU, using information from the NRC (Network Manegeman t Center in TRANSPAC terminology). liie evaluation of link costs will be described first, and then the routingalgorithm will be presented. Concidera full duplexlinkconected to nodes m and n. Let Cm(k), Cn(k) be tlie cost assigned to link A:as percived by nodes;« and n,respectively, and let Cik)^Max[Cm(k},Cnik}] be the "com-bined^estimateoflinkcost. Thequantitics Ci{k), i = m, n a re th e b a s i c d a ta o n wh i ch r o u ti n g co m -putation is based. They are defined as a function of the les'el of utilization of two types of resources: line capacity and link buffers. The cost Ci{k} is set to infinity if cither the link is carrj'ng its maximum permissablenumberofvirtual circuits or it has exeeded a preset threshold of buffer occupancy. Otherwise Ci(k) is defined as a picewise constant increasingfunction of avarage link flow, quantized to a small number of levels and including a "hysteiTesis" effect. A typical function is shown on Figure 3, with the arrows indicatingthewaylinkcostchangesasa function ofchangingutilization. The nodes send updated values of their Ci(k)'s to the NRC whenever a change occurs. Hink cost CT' link utilization Figure 3. A typical link cost relation (TRANSPAC) The major part of the routing computation takes place at the NRC, but some local information is used at each node. LetC(y) (computed by the NRC) be the total cost associated with the minimum cost path between nodes i and j. Every node s determins the route to node t by choosing the value of i which minimizes C(i,/)+Max[C(i),G('{7], i=all nodes conected to j;. In this way the node ä- chooses the intermediate node that would have been choosen by the NRC, unless the value oiCs(i) has changed recently. Ties are resolved by giving priority to the shortest hop path. Becouse of the way in which link costs are defined, the routing procedure becomes a minimum hop method upon which is superimposed a bias derived from the level of link resource utilization. Althow the TRANSPAC routing algorithm has many of the features of a typical centralized routing procedure, its operation is not puerly centralized by allowing the final routing decision to be made locally, based on a combination of centrally and locally determined information. 5. OPTIMAL ROUTING APROACH The algorithms described in Section 4 are generally re ffered as grredyalgorithms, Switches attempt to use the best resources (the minimum delaypath)withoutregard tootherdelays in t!ic network. On the other side the optimal routing approach .solves the routingproblem by minimizing the overall delay of all the messages in the network. The difference between "useroptimiza tion" in the former approach and "system optimization" in the latter is evident. When the statistics of the traffic entering the network do not change over time (quasistatic enviroment) it is convinient to u.se flow models to describe the behaviour of the network. Traffic congestion can be quantified in terms of the statistics of the arrival processes of the network queue.s. These statistics determine the distributions of queue lenght and packet delay at each 1 i n k. U n fo r t u n a te I y, t h ere i s u s u a II y n o t a oc u ra Le analytical expression for the means or variance.^ of the queue lenghts in a data netv/ork. Someimperfcct alternative is to measure congestion at a link in terms of the avarage traffic carried by the link. More precisely, we assume that the statistics of the arrival process at each link (i,k) changconlyduetoroutingupdates, and tl 1 a t we m e a s 11 re c o n gc s ti o n o n (7, A:) v i a t h e t r a ff i c arrival ratefik. We call/it the flow of link (i,k), andv.'eexprcss itin data units/sec, where ihe data units arc the same units used for the macsure-mentofthe transsmitioncapacity of the link, Cik- The optimal routingproblem reduces (.o min-imizing(or maximizing) some objective function D(fik} with respect to the variables/i/c, subject to certain constraints such as flow conservation, nonnegativity of flows etc. Gallager, [11], has defined a recursive algorithm for datagram networks to solve the distributed routing problem in a quasistatic enviroment. We first define some notation in order to explain the main features of the algorithm: The ordered pair (i,k) denotes die directed link from node i to node k. ri(j) = expected traffic entering the net\vork at node i and destined to node / in packets/sec ti(j)-= tot'dl expected traffic at node i destined for node; in packets/Kcc fik= expected traffic over link (i,k) in pack ets/sec, i. e, flow of link (i,k} ^ik(j} = fraction of traffic//(/') tJiai: is routed over link (i,k); also referred as the routing var-rible for link (i,k). The flow model in the network is u es cri bed bv t h e fo I o w i n g e q u a t i o n s : u(j} = n(j) +Y.tl(j)'f'li(J) ally I fik =lti{j) M) • J The algorithm minimizes Dt =YDik{fik) . i,k Dik(fik) is the avarage number of packets in queue or under transmission at link (i,k). By Little's lawDr is proportional to the mean delay of packets in the network, so that minimizingD r is equivalent to minimizing the mean packet delay, It is shown in [11] that> in order to minimize Dt, each node i must incremantally decrease those routing variables for which the marginal delay is large, and increase tliosc for which it is small. The marginal delay is defined as: D'iJc(fik} + àDT/drkO') The algorithm obtained is distributed in nature and is intended for quasi-static applications where the input statistics are slowly changing with time and where occasionally links or nodes fail or are added to the network. Under these conditions, the loop freedom of the algorithm is maintained since this is a mathematical property that is independent of the marginal link delays and node flows, which are the only inputs to the algorithm. ^ Galagher's algorithm needs asa basic quantity the incremental delay JDife/i/ifc. One way to find itisbyusingKleinrock's formula Đik(fiJc) = fikl(Cik-fik) . This expression involves the assumptions of Poison arrivals at nodes, exponentially distributed packet lenghts, and the "independence assumption" of service time atsucessive nodes (i, e. when a packet arrives at a node, a new lenght is assigned to it from some common exponential distribution). Such assumptions do not hold in practice. It is therefore preferable to estimate the derivative of the delay directly by using data available in the network. A few techniques have been proposed for on line estimation of performance gradients of .systems modeled as queuing networks.One of them is the "customer rejection" algoritlim proposed by Segali, [12]. In this approach, the delay sen-sitivit}' is estimated along an observed sample patii by assuming tliat packets airiving at a link arcr>;:jected with probability The effective link flow/ is thus reduced on the avarage by 8f = Mtfr . A/is the number of obsei-ved arrivals in the intej-vair. Leton'^betheamountofsystem time dia t the m-th packetwouldsavc if then-tJi packet were to be removed. Then, ovcrB busy periods, containing each [Ni i=l, ,.., B] packets, the quantity öD/Öf will be B Ni Ni B l~Jn-l m—n /v. 1 AnotJier procedure for estimating on-line marginal packet delays trough links is a tehnio-que known as perturbation analyses, [J3J. This method is based on the assumption that a sample path of the system is obseived. Hence, for the-observed link i the queuing and transmission delay nk of the Ar-th packet could be recorded. Than the mean is obtained as K Rik= (l.fKj'Z^-ik. Thecorrespondingsensitivity is compiitcd na K 8Rik= (IIK) IS/VA. k----1 Since by Little's law Dik - fikRik, than Dik = ÒDiklÒfyc = Rik + fikiÒRikJàfik) . However, in the prturbation analyses technique the gradientestimates are obtained in ierrns of the mean interarrival time 'Cjk^lIfik^ instead in terms of the link flow/it. Then the estimate of Dik'^ Rik-(liklèXik}ÒR,k. 12 There also exists a class of algorithms for solving the optimal routing problem which could be viewed as constrained version of common, unconstained optimization methods, such as steepest descend and Newton's method, described in nonlinear programming texts, [14]. Itis evident that the optimal routingapproach is a more sofisticated alternative to the shortest path routing in the quasi-static network enviro-ment Asthe statistics of the input arrival proces-seschangemore rapidly, the aproprietness of the optimal routing algorithms diminishes. In such cases it is difficult to recomend routing methods thataresimultaniouslyeffitientand practical. 6. ROUTING ALGORITHMS AND THE FLOW CONTROL There are two main performance measures that are substantually affected by the routing algorithm: throughput(quantity of service), and average packet delay (quality of service). Routing interacts with flow control in determining these performance measures by means of a feedback mechanism shown in Figure 4. When the offered load is relatively low, it will be fully accepted into the network, i. e, Troughput = Offered load . When the offered load is excessive, a portion will be rejected by the flow control algorithm and Throughput = Offered load - Lx>st load . D IR", aiul q(v(0,u(0) = [9i(v(0,u(<)),...,7„(v(/),u(/))F, where rji is sum of currents charging the capacitors connected to node i. The two common relaxation methods used aie the Gauss-Seidel (GS) and the Gauss-Jacobi (G,l) method. Relaxation methods can be used for the solution of equations (4) in different ways. Fig.2 illustrates the levels at which relaxation methods can be applied. Linear relaxation method is applied at the linear equation level and consists of replacing the GE method for solving equation (3) by GJ or GS. Nonlinear relaxation methods are applied at the nonlinear equation level and augment the NR method applied to equation (2). They replace the linear equation solution based on sparse-matrix techniques. Relaxation methods when applied directly to the system of nonlinear algebraic equations describing the circuit are termed Waveform Relaxation (WR) [NSV84]. As a result of this, the system is decomposed into decoupled subsystems of algebraic-differential equations corresponding to decoupled dynamical subcircuits. Each decoupled subcircuit is then analyzed for the entire simulation time interval using the standard simulation techniques. Such a decomposition permits latency to be exploited. Decomposition into subcircuits permits a trade-off between the amount of time spent Direct-Method Linear Equation Solution (GE or LU decomposition Solution Subvector for a subcircuit Relaxation Iteration Nonlinear Differential Equations Numerical Numerical Integration Integration Relaxation Iteration N-R N- -R Linearization Linearization Relaxation 1 Iteration Direct-method Linear Equation Solution (GE or LU decomposition) Solution Vector Figure 2: Relaxation Applied at Different Levels of Analisis. on any single processor at an iteration and the time spent commùnicating the results of the analysis. This is a key requirement for deriving maximum efficiency from a parallel processing environment. The WR algorithm using GS iteration is given in Fig.3. Superscript k is the iteration count, subscript i is the component index of a vector, e is a small positive number, N is the maximum node number and n is the number of circuit variables. Modifications in the WR algorithm help in improving the speed of convergence. Instead of solving each differential equation for one unknown (point relaxation), the system of differential equations can be partitioned into subsystems having more than one equation (block relaxation). Each decomposed circuit is then solved using standard simulation techniques. Each subcircuit can be an. alyzed independently [NSV84] from t = Otot = T, using its own time step sequence, controlled by the integration method. As opposed to this, in a standard circuit simulator entire circuit is analyzed over the total simulation time using only one common time step sequence. The number of time step for each subcircuit is thus less in WR decomposition which is a definite computational advantage. Latency of the circuit can be exploited by incorporating bypass techniques. Without losing accuracy the analysis of subcircuits is bypassed for some time intervals knowing the information obtained from the previous time point or previous iteration. The bypass techniques have been described in [NSV84] in detail. WR methods have guaranteed convergence and have proven to be effective decomposition methods for the analysis of large scale MOS circuits. However, they do suffer from a few drawbacks. The k ^ 0; guess waveform v°(i) Vi G [0,r] such that v°(0) = V; repeat k k+1] for each i solve j=i i=.-+i for vf{t), t 6 [0,T] with initial condition v-'(O) = T-^-until, max max I vj'fi) - vj^'^ft) |< s l continue to increase with the progress in technology and existing computer architectures are- reaching their performance limits due to> constraints on, the fundamental speed of light.. This has prompted development of an experimental' relaxation-based circuit simulator on a massively parallel processor (MPP) -the Connection Machine'reported by Webber el al. in [WSV87]. The Connection Machine is an MPP with upto 65,536 processors and uses SIMD architecture.. The simulator in [WSV87] uses GJ iteration at the nonlinear equation level with point relaxation and a single step)of N-R method.. Though point relaxation causes^ slow conivergence, it has been found toi work well' for large: class of circuits. Block relaxation is not found' to. be suitable on the Connection Machine. This is; because the data is less uniform' in block method's.. The m'atrices to be solved may be of different sizes which make it difficult to exploit the parallelism on the Connection Machine. For an EPROM circuit, the point relaxation on the Connection Machine has been experimentally found by Webber et al. [WSV87] to be 30 times faster than the direct method on a Micro Vax. The results show that the execution is nearly independent of the size of the problem for circuits without tight coupling. Connection Machine is good for very large problems though it is extremely slow for small problems. The largest circuit that can be run on the Connection Machine is about 10,000 nodes. 5 Conclusion In this paper we have surveyed the two well known methods for circuit simulation - direct and relaxation. The parallel implementation of these meth- ods has been considered. The architectures used for the simulation problem as reported in the literature and the observations from our experiments have been presented. It follows from the discussion that considerably higher performance can be achieved by using a speciaUpurpose multiprocessor in which the interconnection of the processors and the design of processors are turned td .the circuit simulation task. This is particularly true for the relaxation-based algorithms. Present research work includes finding good partitioning schemes for dividing the circuit into tightly coupled subcircuits, investigation of optimal techniques för finding the simulation time steps and mapping the algorithms tó the best possible hardware. References [CA79] D. A. Calahan and W. G. Ames. Vector Processors: Models and Application. IEEE Trans. Circuits Syst., CAS-26(9), September 1979. [CGK75] B. R. Chawla, H. K. Gummel, and P. Kozak. MOTIS - An MOS Timing Simulator. IEEE Trans'. Circuits Syst., CAS-22(12):901-909, December 1975. [DN84] J. T. Deutsch and A. R. Newton. A Multiprocessor Implementation of Relaxation-Based Electrical Circuit Simulation. In Proc. Slih Design Automation Conf., pages 350-357, 1984. [IIHL82] M. H. Heydemann, G. D. Hachtel, and M. Lightner. Implementation Issues in Multiple Delay Switch Level Simulation. In Proc. Int'l Conf. on Circ. and.Comp., pages 46-52, September 1982. [JNP86] G. K. Jacob, A. R. Newton, andD. O. Ped-erson. Direct Method Circuit Simulation using Multiprocessors. In IEEE Proc. ISCAS, 1986. [LRSV82] E. Lelarasmee, A. E. Ruehli, and A. L. Sangiovanni-Vincentelli. The Waveform Relaxation Method for the Time-Domain Analysis of Large Scale Integrated Circuits. IEEE Trans. Computer-Aided Design, CAD-1(3):131-145, August 1982. [Mat86] S. Mattison. CONSINE - A Simulation Program on Ilypercube. Technical report, Lund University, 1986. [MITM87] M. Mikami, J. Ishibashi, N. Tahara, and G. Matsuoka. Vectorization of SPICE Circuit Simulator: on FACOM VP Series Su- percomputer. In Proc. 2nd Int'l Conf. on SuperComputing, pages 29-34, 1987. [Nag75] . L. W. Nagel. SPICE2: A Computer Program to Simulate Semiconductor Circuits. Technical Report Memo.No.ERL-M 520, UCB, Berkeley, May 1975. [NP78] A. R. Newton and D. 0. Pederson. Analysis Time, Accuracy and Memory Requirement Tradeoffs in SPICE2. In IEEE Proc. ISCAS, pages 6-9, 1978. [NSV84] A.R. Newton and- A.L. Sangiovanni-Vincentelli. Relaxation-Based Electrical Simulation. IEEE Trans. Computer-Aided Design, CAD-3(4):308-331, October 1984. [Ram88] S. Raman. HIRECS: llyiiercubc Implementation of Relaxation-Biiscd Circuit Simulation. Master's thesis, Dept. of Comi^uLer Science and Automation, Indian Institute of Science, Bangalore, India, July 1988. [Sal87] R. A. Saleh et al. Parallel Waveform Newton Algoritlims for Circuit Simulation. In Proc. /CCf, .pages 660-663, 1987. [ST75] S. A. Szygenda and E. W. Thompson. Digital Logic Simulation in a Ti me-Based, Table-Driven Environment: Part 1 Design Verification. IEEE Computer, 7(3):24-36, March 1975. [Vla87] A. Vladimirescu et. al. A Vector Hardware Accelerator with Circuit Simulation Emphasis. In Proc. 24th Design Automation Conf, pages 90-94, 1987. [Whi85] J. White et al. Accelerating Relaxation Algorithms for Circuit Simulation using Waveform Newton, Iterative Step Size Refinement, and Parallel Techniques, [n Proc. IC-CAD, pages 5-7, 1985. • [WJM+73] W. T. Weeks, A. J. Jimenez, G. W. Ma-honey, D. Mehta, H. Qassemzadeh, and T. R. Scott. Algorithm for ASTAP - A Network. Analysis Program. IEEE Trans. Circuit TAcor?/, CT-20(ll):624-628, November 1973. [WSV87] D. M. Webber and A. L. Sangiovanni-Vincentelli. Circuit Siniulation on the Connection Machine. In Proc. 24th Design Automation Conf, pages 108-113, 1987. [WW86] J. White and N. Weiner. Parallelizing Circuit Simulation - A Combined Algorithmic and Specialized Hardware yVpproach. In Proc. ICCD, pages 438-441, 1986. THE PRINCIPLE OF MULTIPLE KNOWLEDGE Keywords: knowledge representation, learning, classification Matjaž Gams and Viljem Križman Jožef Stefan Institute Jamova 39, Ljubljana ABSTRACT The principle of multiple knowledge is presented and it's implications are analyzed in real-life classification tasks. Empirical measurements, simulated computer models and analogy with humans strongly indicate that better classification accuracy is obtained when constructing and using multiple knowledge bases instead of one knowledge base alone. POVZETEK V članku je predstavljen princip mnogoterega znanja in njegov pomen v realnih klasifikacijskih domenah. Empirične meritve, simulirani računalniški modeh in primerjava z ljudmi kažejo, da je v splošnem klasifikacijska točnost več baz znanja boljša kot najboljše baze izmed njih. 1 Introduction Real-life domains are characterized by nonexistence of exact computational model and consequently, traditional computing approach is often inadequate. Expert systems enabled a significant step ahead yet different studies, e.g. (Keyes 89), report that they are successful only when the application is relatively small, simple, well understood and when experts agree with each other. When coping with more difficult problems, existing ES methodology lacks mechanisms for dealing with • nonexistence of a single compact body of encod-able knowledge, • nonexistence of isolated static body of knowledge, independent of time, related events and environments, • nonexistence of perfect exact single algorithm for applying the knowledge. It is surprising that AI literature hardly mentions problems with multiple contradictory and redundant knowledge with the purpose to increase performance by exploiting these properties. Recent keyword search of 'In this paper we don't distinguish between multiple methods, multiple systems, multiple knowledge or multiple knowledge bases. 50.000 abstracts from AI literature over 10 years (Clark 90) indicates that only a few refer to this problem. Indeed, computer methods regularly tend to use only one single body of knowledge in the form of one computer procedure. People usually take quite different approach in real life. They tend to form expert groups, verify results independently and cross-check information in order to find the best solution. Practical experiences show that such approach in general produces better results than when relying on one man or one source of knowledge alone. In other words - people inherently and successfully use multiple knowledge in most of difficult tasks without paying much attention to that phenomenon. 2 Related work Many well known AI systems like DENDRAL, MYCIN, PROSPECTOR and DIPMETER already enable the use of multiple knowledge to a certain degree.' Multiple knowledge is also present in qualitative modeling (Murthy 88), e.g., when combining qualitative and quantitative models, and in the second generation expert systems. Probably the most relevant work regarding multiple knowledge was reported in empirical learning or learning from examples. Different authors argue that a proper use of multiple knowledge enables better possibilities to analyze the domain and better classification accuracy. Catlett & Jack (87) reported of important increase in clćissification accuracy in several domains when one knowledge base in the form of a decision tree was constructed for each class instead of classifying all classes with one tree. Similarly, Buntine (89) reported of important increase when 10 different decision trees were designed each time with different attribute at the root. Another interesting approach was taken by Schlimmer (87) enabling multiple view on the same domain by using different algorithms each with differently preprocessed input data. Brazdil & Torgo (90) used different' data and different algorithms and achieved very significant improvements. Slightly different approach was taken in GINESYS (Gams 78; Gfuns, Drobnič min Po > 0. oeS (1) Opomba: če za trenutek pozabimo na (daljši ali krajši) računski čas, lahko rečemo, daje H slučajna spremenljivka z zalogo vrednosti S. Lep posebni primer dobimo, če je množica S končna in če H generira vse elemente množice S z enako verjetnostjo. Na množici S je definirana stroškovna funkcija c : S —* C. Za množico vrednosti C lahko vzamemo na primer množico naravnih IN ali realnih števil IR. Naloga je poiskati minimum stroškovne funkcije c na množici objektov S. Povzemimo: Definicija 1 Splošni problem kombinatorične optimizacije je družina primerkov. Primerek (splošnega) problema kombinatorične optimizacije je par (S,c), kjer je S množica (množica dopustnih rešitev), c pa je preslikava 5 —► C (stroškovna funkcija). Treba je poiskati tak O min fc da velja Cmin - c(Or - min c(o) oeS (2) Problem iskanja maksimuma definiramo analogno, je pa trivialno ekvivalenten problemu minimuma na isti množici S s stroškovno funkcijo č = —c. V [KLPP86] pravkar definirane pojme imenujejo nekoliko drugače. Primerku problema rečejo naloga, stroškovna funkcija pa je namenska ali ciljna funkcija. V tem delu se bomo omejili na probleme s končno množico S. Čeprav končna, pa je množica S pogosto zelo obsežna (recimo velikosti, ki je eksponentna funkcija velikosti problema). V primeru trgovskega potnika je kar n! permutacij mest, če je vsak par mest povezan. Zaradi obsežnosti pregledovanje vse množice S običajno ne pride v poštev. Pri NP-polnih problemih je pregled množice S algoritem eksponentnega reda. Doslej še nikomur ni uspelo odkriti algoritma, ki bi bil bistveno hitrejši (ki bi imel časovno zahtevnost manj kot eksponentnega reda). Ker verjetno velja hipoteza P^NP, je za to tudi kaj malo upanja; Pri obravnavi splošnega problema kombinatorične optimizacije (S, c) bomo privzeli, da obstaja vsaj en verjetnostni algoritem H (Ti : 0 S) in vsaj en verjetnostni algoritem M {M : S —► S). Verjetnostni algoritem V:/! B v našem primeru realizira neko preslikavo. Rezultat je element ciljne množice B, porazdelitev verjetnosti, da bo izračunan konkretni element pa je v splošnem odvisna od podatka, elementa množice A. Množico N(i) = {y\P{M{x) = j/) > 0} imenujemo soseščina točke i € S.. Z algoritmom A/" na naravni način vpeljemo razdaljo na množico S, ki inducira neko topologijo. Pogosto je za dani problem mogoče na več načinov smiselno definirati pojem soseščine. V takih primerih nam različne izbire v splošnem dajo različne topologije na množici S, s tem pa tudi različno obnaSanje splošnih algoritmov, ki jih bomo definirali v nadaljevanju. Nas bo tu poleg topologije seveda zanimala tudi učinkovitost (hitrost) algoritma A/". Običajno lahko pričakujemo, da bomo imeli ali hiter algoritem A/" in "grdo" topologijo (z mnogimi lokalnimi ekstremi) ali pa obratno, "lepo" topologijo, vendar počasni algoritem A/". Za primerjavo različnih splošnih algoritmov 42 je pomembno tudi razmerje med časovnima zahtevnoslima algoritmov M in 71. Brž ko privzamemo, da imamo dan algoritem A/" in z njim topologijo, lahko definiramo lokalni minimum na S: 01 je lokalni minimum, če velja c(oi) < c(o) Vo € N(o) — {"<} Analogno lahko definiramo lokalni maksimum. Za reševanje splošnega problema kombinatorične optimizacije je znan enostavni algoritem, ki ga bomo imenovali algoritem lokalna optimizacija (angl. randomised local search TICS [Maff86], neighborhood search, iterative improvement [LaAr87, Laar88], multistart algorithm [GidaSS]). Algoritem TICS: (lokalna optimizacija) repeat generiraj slučajno začetno stanje repeat poišči soseda if je boljši then premakni se until ni boljšega soseda until preveč korakov Enostaven premislek nas pripelje do ugotovitve, da notranja repeat until zanka konča v lokalnih minimumih. V nobenem primeru v notranji zanki algoritem ne more iz lokalnega minimuma. To, da se 'ustavi' v lokalnih ekstremih, je tudi glavna zamera, ki jo temu algoritmu namenjajo kritiki [Laar88]. Argument je tembolj tehten, kolikor je učinkovitejši od algoritma TI. O časovni zahtevnosti tako splošnega algoritma se ne da povedati veliko. Prav mogoče je, da je celo samo eno iskanje lokalnega optimuma potreben nepolinomski računski čas. Zadostuje, da so okolice dovolj 'bogate'. O tem nas prepriča trivialni primer: vedno je mogoče definirati soseščino tako, da so vse dopustne rešitve dosegljive ena iz druge. Za A/^ vzamemo kar TI iz definicije problema kombinatorične optimizacije. V tem primeru potrebujemo za pregled ene same okolice 0(|S|) časa! (Za tolažbo pa bomo optimalno rešitev zanesljivo dobili.) Zanimivo je, da celo za znano '2-opt' soseščino pri problemu trgovskega potnika časovna zahtevnost ene lokalne optimizacije ni znana [L1TT89]. Menda je Kern [Kern86] nedavno za nekatere probleme trgovskega potnika pokazal, da je '2-opt' v povprečju polinomske časovne zahtevnosti. Pregled različnih posplošitev algoritma TICS najdemo v [MafF86], kjer med drugim tudi algoritem Ohlajanje (5^) definirajo kot posplošitev algoritma TLCS. 3. Primer problema kombinatorične optimizacije Mnogi diskretni optimizacijski problemi se dajo zapisati v obliki problema kombinatorične optimizacije, bogato zalogo problemov najdemo na primer v [KLPP86, Koza86], verjetno najpopolnejšo zbirko (preko 300) pa v [GaJo79]. V reviji Journal of Algorithms v posebni rubriki že leta zbirajo nove in nove probleme z znano ali pa še neznano časovno zahtevnostjo. Morda najbolj popularen problem kombinatorične optimizacije (oziroma operacijskih raziskav) je problem trgovskega potnika (angl. traveling salesman problem, TSP). Slika 1: Korak lokalne optimizacije tipa 2-opt TSP spada v širši razred transportnih problemov, ki so deležni precejšnje pozornosti v strokovni literaturi. Za ilustracijo povejmo, da pregledni članek iz leta 1983 [BGAB83] navaja kar 699 referenc v zvezi s transportnimi problemi! Ob mnogih primerih praktične uporabe je verjetno eden od razlogov popularnosti problema trgovskega potnika dejstvo, da ga je zelo enostavno opisati. Imamo neusmerjen graf z utežmi na povezavah (omrežje). Hamiltonov obhod ali Hamiltonov cikel je pot, katere začetna in končna točka sovpadata in ki obišče vsako točko grafa natanko enkrat. Problem je poiskati Hamiltonov obhod z minimalno dolžino, če za dolžino poti vzamemo vsoto uteži na povezavah poti. V duhu definicije 1 so dopustne rešitve vsi Ilamiltonovi obhodi na grafu. Vsak Hamiltonov obhod lahko zapišemo tudi kot ciklično permutacijo. če je graf poln, potem tudi vsaka ciklična permutacija definira Hamiltonov obhod, v splošnem pa to ni res. Stroškovna funkcija je (3) kjer je x permutacija € S„, {1,..., n} so oznake točk, d(i,j) pa je utež na povezavi (i, j). Pogosto je uporabljana lokalna optimizacija tipa r-opt. Sosednje stanje k danemu stanju dobimo tako, da vzamemo r povezav in jih zamenjamo z novimi. Primer za 2-opt je na sliki 1. Ker z rastočim r časovna zahtevnost lokalne optimizacije r-opt narašča, so najpogosteje uporabljane 2-opt in 3-opt, ali pa optimizacija, ki se sproti odloča za r. Kot najboljšo pa v [LLRS85] priporočajo Or-opt. Problem trgovskega potnika je NP-poln. Tu samo omenimo, da so tudi mnogi zanimivi posebni primeri še vedno NP-polni problemi, na primer: simetrični TSP, Evk-lidski TSP, TSP na polnem omrežju, TSP za katerega velja trikotniška neenakost. Še več, že odločitveni problem, ali ima dani graf Hamiltonov cikel, je NP-poln problem. Pogosto rešujemo problem na polnem omrežju, saj s tem ne izgubimo splošne uporabnosti algoritma. Vedno namreč lahko povezave, ki jih nočemo uporabljati, obtežimo z zelo veliko utežjo (na primer večjo kot vsota vseh dovoljenih uteži). Ce je potem dobljena optimalna rešitev prevelika, vemo, da je bila uporabljena kakšna prepovedana povezava. V primeru, ko rešujemo problem na splošnem grafu, bi bilo naravno vzeti za dopustne rešitve Hamiltonove obhode grafa. V tem primeru bi bil že algoritem TI časovno zelo zahteven, saj bi moral reševati NP-poln problem. To je pomemben razlog za odločitev, da rešujemo problem na polnem omrežju. 4. Algoritem SA Eden od razlogov za popularnost algoritma SA je analogija z modelom procesa ohlajanja snovi iz statistične mehanike. Tu analogije ne bomo opisovali, omenimo le referenco [KÌGV83]. S staJišča kombinatorične optimizacije je algoritem ohlajanje (5^) zelo enostaven. Za razliko od lokalne optimizacije so možni tudi premiki v smeri poslabšanja stroškovne funkcije. Verjetnost takega koraka je odvisna od parametra T, ki mu po analogiji s fizikalnim modelom rečemo temperatura. Algoritem Ohlajanje (5^): generiraj slučajno začetno stanje nastavi začetno temperaturo T repeat znižaj temperaturo T slučajno izberi soseda if sosed je boljši then premakni se else (* sosed je slabši*) premakni se z verjetnostjo p = p{T) until preveč korakov Označimo s p verjetnost dogodka, da je v algoritmu sprejet korak, ki poslabša vrednost stroškovne funkcije. Ta verjetnost je odvisna od trenutnega stanja (trenutne dopustne rešitve) in od trenutne vrednosti parametra T. Predpostavili bomo, da je p padajoča funkcija parametra T. Pri danem primerku problema in dani temperaturi T bomo zahtevali, da naj bo p omejena s konstanto p < P < \ . Funkcijska odvisnost je običajno oblike p = exp -AC/T AC < O AC > O (4) kjer smo z AC označili razliko stroškovnih funkcij starega in novega stanja. Taka definicija je predlagana v [MRRT53] in [KÌGV83], in je običajno uporabljena. Edina avtorju znana izjema je definicija Boltzmanovega stroja [AaKo87, AaKpBS] kjer uporabljajo (5) Definicija algoritma 5.4 je res enostavna, vendar pri implementaciji hitro naletimo na netrivialne probleme. Na primer, kako je treba zmanjševati temperaturo, da bomo dosegli dobre rezultate. Vemo, da prehitro zniževanje temperature ne zagotavlja več 'konvergence' algoritma [MÌRS86]. Ali znamo zniževanje temperature dobro določiti vsaj za kakšen poseben problem? V [LaAr87, Laar88] in v [LaDe88] predlagajo polinomske strategije ohlajanja, ki se dobro odrežejo na nekaterih preiskušenih primerih. (Pri tem se seveda morajo zadovoljiti z dobrimi namesto optimalnih rešitev.) Tu se s tem problemom ne bomo podrobneje ukvarjali. Zniževanje temperature definiramo lahko tako, da povemo, kako je T odvisna od števila korakov. Poseben primer (in ekvivalenten !) je, da povemo, koliko korakov naredimo pri neki temperaturi. Odvisnost temperature od časa v tem primeru podamo z zaporedjem parov (temperatura, število korakov), na primer C^^i > "»i), (T2, mi),... ,{Tk,mk),... kar pomeni: naredi mi korakov pri temperaturi Ti,... naredi ruk korakov pri temperaturi Tjc,...itd. Kot že omenjeno. mora temperatura padati počasi, če želimo, da algoritem z verjetnostjo 1 najde optimalno rešitev (v končnem, toda ne omejenem številu korakov) [MÌRS86]. V nadaljevanju bomo predpostavili, da temperatura T konvergira proti O z naraščajočim številom korakov. lim T{n) = O (6) 5. Računski rezultati z algoritmom SA (pregled literature) V tem razdelku bomo s kratkimi opombami pospremili poročila o testiranju algoritma 5.4 na različiiili ])roblcmih. Pregled še zdaleč ni popoln, zajema pa (verjetno) večino 'klasičnih' člankov in nekaj poročil, ki jih je avtor bolj ali manj slučajno dobil v roke. V že večkrat omenjenem članku Kirckpatrick s sodelavci [KÌGV83] preizkusi algoritem SA na problemu trgovskega potnika (TSP) in na dveh problemih, ki se pojavita pri načrtovanju integriranih vezij (Celi Placement, Wiring). Članek je populariziral algoritem. Uspešna uporaba tu in še v celi vrsti poročil pomeni, da so bile dosežene dobre ali celo dotlej najboljše znane rešitve za kakšen primerek kakšnega problema. O času, potrebnem za računanje ne poročajo ali pa priznavajo, daje algoritem zelo potraten. Nasploh običajno (z izjemami, ki jih navajamo v pregledu) velja splošna ugotovitev (ki jo v [AnMS87] (stran 8) povzamejo po [JAMS85] in [GoSk86]), da je 5.4 tipično slabši od algoritmov, ki so posebej prilagojeni konkretnemu problemu. Bonomi in Lutton [BoLu84] z algoritmom računata 'skoraj optimalne' rešitve za TSP v O(n^) časa. Eksperimentalno ugotovita, da se algoritem SA obnese bolje od lokalne optimizacije. Na žalost uporabita staro verzijo 2-opt algoritma. Ista avtorja v [LuBo86] algoritem uporabita na problemu minimalno uteženo Evklidsko prirejanje (angl. minimum weighted perfect Euclidean matching). Opazita, da je potrebni čas (za osnovno verzijo algoritma 'ogromen' (stran 195, zadnji odstavek). Se eno poročilo omenjenih avtorjev [BoLu86] se ukvarja z aplikacijo algoritma na kvadratni problem prirejanja (angl. Quadratic sum assignement problems). Algoritem 5.4 je predlagan kot linearni aproksimacijski algoritem. O poizkusih na kvadratnem problemu prirejanja (Quadratic assignement problem) poročata Burkhardt in Rendi [BuRe84]. Iz rezultatov je videti, da SA ni bil bistveno boljši od QAPH4B algoritma (ki je v resnici lokalna optimizacija), posebej če upoštevamo porabljeni čas. Uporabljena je tudi različica z več ponovitvami. Grover [GrovST] poroča o uporabnem programu, ki prinaša lepe prihranke (precej odstotkov) na problemu razporejanja čipov (angl. Standard Celi Placement), uporabljanem v načrtovanju integriranih vezij (VLSI design). Začne vedno z dobro začetno rešitvijo. Poročili [DoSS87, DoSk88] ugotavljata, da je algoritem 5.4 na problemu razbitja grafa (graph partitioning) zelo potraten, so pa dobili dobre rešitve v primerjavi z nekaterimi drugimi algoritmi. V [AnMS87] (stran 8) sta omenjeni dve eksperimentalni študiji. V [JAMS85] ugotavljajo, da je z SA sicer mogoče dobiti dobre rešitve, vendar je bil algoritem na problemih razcep števil (number partitioning), barvanje grafa (graph colouring) in trgovski potnik (TSP) praviloma slabši od tradicionalnih algoritmov za te probleme. V primeru ■problema razbitja grafa so bili dobljeni rezultati ugodni za algoritem 5.4. V drugem poročilu [GoSk86] ugotavljajo, da za problem trgovskega potnika in "p-mediane" obstajajo • algoritmi, ki so boljši od SA. V članku [LALW89] Laarhoven, Aarts, Lint in Wille poročajo o doslej najboljših rešitvah za problem trdnjav (angl. Footbal-pool problem) na 6, 7 in 8 parih. Prej je najboljšo znano rešitev za n = 6 našel Wille [WÌ1187], prav tako z algoritmom Za konec omenimo še nekaj poročil, v katerih primerjajo algoritem 5.4 z lokalno optimizacijo. V [LaAr87] povzemajo primer [LuMe86], za katerega je dokazano, da je 5.4 boljši od TICS (pričakovano število korakov 5.4 je manjše od pričakovanega števila korakov algoritma TLCS). Ta rezultat ne nasprotuje našemu izreku 2, saj je primer narejen za verzijo 5.4 s konstantno temperaturo, torej ne ustreza pogojem izreka (oziroma naži definiciji algoritma 5.4). Rahin [RaSh89] poroča o primerjavi lokalne optimizacije in 5.4 na problemu razbitja grafa. Za majhne n se je lokalna optimizacija izkazala za boljšo: rezultat je bil boljši in čas krajši. Uporabljen je bil stari Lin-Kerninghamov algoritem za lokalno optimizacijo. Lam in Delosme [LaDeSS] poročata o testiranju algoritma SA z originanim načinom ohlajanja. V nekaterih primerih se je algoritem izkazal za boljšega od Lin-Kerninghamove in od Karpove hevristike za problem trgovskega potnika. Na problemu razbitja grafa je bil pri nekaterih načinih generiranja slučajnih primerkov problema algoritem boljši, pri drugih pa slabši od hevristike Fiduccia in Mattheysesa. Kategorično v prid 5.4 interpretirajo rezultate v [JAMS85], kjer pa je to storjeno izrazito 'nepošteno'. 100 poskusov z algoritmom 5.4 je primerjano s 100 poskusi lokalno, optimizacije (TICS), to pa pomeni, da je bil čas porabljen za SA kar približno 300-krat daljši! (6 minut za SA proti 1 sekundi za HCS). Po drugi strani v zborniku [AnMS87](sttan 95) omenjajo referenco [RiTi85] kjer so eksperimentalno ugotovili, da je pri globalni optimizaciji na kompaktni množici S C IR* pri pogoju, da leži optimalna točka v notranjosti S med znanimi najboljša naslednja metoda: 1.generiraj nekaj slučajno izbranih točk (z enakomerno porazdelitvijo); 2.naredi lokalno iskanje na vsaki od njih 3.zapomni si dotedaj najboljšo rešitev (Torej analogno algoritmu TICS za diskretni primer!) Pred zaključkom pregleda povzemimo komentar iz [LaAr87]. Večina poskusov z algoritmom SA je bila narejena z enostavnim ohlajanjem. Rezultati bi bili verjetno boljši, če bi uporabili bolj "zvite" načine ohlajanja, kot jih (na primer) predlagajo v [LaAr87, Laat88]. Po drugi strani je res, da tudi algoritmi, s katerimi SA primerjajo niso vedno najboljši od znanih. Pri tovrstnih poskusih je na žalost vedno tako, daje zelo težko doseči popolnoma pošteno primerjavo. Verjetno bo za dokončno splošno priznano sodbo potrebno še precej primerjalnih študij. Poskusimo navezati nekatere rezultate poskusov na teoretični rezultat iz naslednjega razdelka: Upanje, da je mogoče rezultat izreka 2 podkrepiti še s kakšnim praktičnim rezultatom, sta naslednji poročili. Dueck in Scheuer [DuSc88] sta testirala algoritem TA (treeshold accepting), ki je nekoliko popravljena lokalna optimizacija. Namesto verjetnostnega kriterija ta algoritem sprejema poleg korakov navzdol tudi korake, ki 'ne gredo preveč navzgor'. Algoritem torej 'preskoči' majhne 'hribčke' in 'dolinicc', ki so za običajno lokalno optimizacijo usodni. Doseženi rezultati na primerku problema trgovskega potnika s 442-mesti so najboljši doslej (boljši kot tisti, dobljeni z algoritmom 5.4). Poročajo tudi o sorazmerno kratkem času računanja. K temu dodajmo še primerjavo [LeBi89] med algoritmom SA in 'quenching' algoritmom (zelo hitro ohlajanje), ki se je prav tako izkazalo za boljše od počasnega ohlajanja (pri ustreznem številu ponovitev za hitrejši algoritem, seveda). Ce poskusimo iz tega potegniti nekakšen nasvet, bi lahko rekli takole: Običajno se ne izplača predolgo časa porabiti z 'zelo premetenim' algoritmom. Bolje je večkrat začeti prav od začetka, če 'dovolj dolgo' nimamo zaželjenega uspeha. Obravnava vprašanja, kaj v konkretnih primerih pomeni 'dovolj dolgo' presega okvire tega dela. Tukaj omenimo le referenci [BoRV87] in [Laar88], ki obravnavata ustavitvena pravila za nekatere verjetnostne hevristike. 6. Konvergenca algoritma SA Konvergenco algoritma 5.4 obravnavajo v člankih [GeGe84, Gida85] in [HaSa89], v [GeMi87] pa so omenjeni tudi izreki Hajeka in Tsitsiklisa. Model izvajanja algoritma je (časovno) nehomogena Markovska veriga, kajti prehodne verjetnosti se s časom spreminjajo. V tem razdelku bomo povzeli po enem od omenjenih virov izrek o konvergenci algoritma 5.4. Izrek 1 [MÌRS86] Ce parameter T pada dovolj počasi, potem iz kakršnegakoli začetnega stanja algoritem SA z verjetnostjo 1 konča v enem od globalnih optimumov, če mu dovolimo narediti neskončno mnogo korakov. Ali, ekvivalentno: Ce parameter T pada dovolj počasi, potem iz kakršnegakoli začetnega stanja algoritem 5.4 z verjetnostjo poljubno blizu 1 konča v enem od globalnih optimumov, če mu dovolimo narediti dovolj korakov. 7. Primerjava algoritmov SA in ncs v tem razdelku navajamo izrek, ki pravi, da je algoritem SA asimptotsko slabši od algoritma TICS. Se več, iz dokaza bo sledilo, da je celo enostavno ponavljanje neodvisnih generiranj dopustnih rešitev asimptotsko uspešnejši algoritem kakor algoritem 5.4 [2ero88]. Uporabljali bomo naslednje oznake: • JV je število stanj (moč množice dopustnih rešitev) • K\ označuje število stanj, iz katerih vse poti, ki gredo samo navzdol, končajo v enem od globalnih optimumov. • K označuje število stanj, iz katerih obstaja pot, ki gre samo navzdol in konča v enem od globalnih optimumov. Očitno K > Ki >0. Da se izognemo trivialnim primerom privzemimo še N > K. »Rje dolžina najdaljše poti, ki gre samo navzdol. • ui je razmerje med časom, potrebnim za generiranje začetne dopustne rešitve (algoritem TI) in med časom, potrebnim za generiranje novega stanja, če kakšno stanje že poznamo (algoritem Af). • d je maksimalna stopnja stanja (maksimalno število sosedov) oziroma d = max|N(i)| isS • 1 —p, je verjetnost, da algoritem ne bo sprejel slabšega stanja v algoritmu SA pri temperaturi Ti. Lahko bi tudi rekli: verjetnost, da algoritem ne bo šel 'gor'. (Vrednost pi je odvisna tudi od trenutnega stanja.) • = min{l — pi}, kjer minimum izračunamo po vseh možnih stanjih danega primerka problema. Temperatura je tu fiksirana (T,). qi je torej spodnja meja za verjetnost dogodka, da pri temperaturi Ti pri danem primerku problema algoritem SA ne bo sprejel koraka 'gor', v smeri poslabšanja stroškovne funkcije. V dokazu Izreka 2 bomo predpostavili g, —♦ 1 ko gre I —► oo. Ce vzamemo 4 za definicijo p in predpostavimo T —> O sledi —► 1, torej je za algoritem predpostavka izreka izpolnjena. • n je število korakov, ki jih je algoritem že opravil. V dokazu privzamemo, da algoritem TI generira vse dopustne rešitve z enako verjetnostjo. (Privzetek deloma poenostavi dokaz, vendar ni bistven za resničnost izrekov.) Dokaz je (presenetljivo) enostaven. Poiščemo spodnjo mejo za verjetnost, da algoritem lokalna optimizacija najde globalno optimalno rešitev v n korakih in zgornjo mejo za verjetnost, da algoritem najde globalno optimalno rešitev v n korakih. Potem primerjamo obe oceni in sledi rezultat (za dokaz glej [2ero88, 2ero90]). Formalno definiramo P-R.cs{n) := PT{aigoritem HCS je uspel v n korakih) (7) in PsA{n) := Pr(algoritem SA je uspel v n korakih) (8) ocenimo Lema 1 Lema 2 PsA(n) < 1 - gfgZ'r ■ ■ ■ irc' (l - I) (10) kjer je n — thi O < m; < m, , in izpeljemo Izrek 2 Obstaja konstanta no, tako da velja Vn > no PsA{n) < Pncsin) (11) 8. Skoraj optimalne rešitve Pri reševanju NP-težkih problemov se moramo običajno odpovedati zahtevi po optimalni rešitvi. Izkaže se, da je mogoče enako primerjavo med algoritmoma SA in TICS narediti tudi v primeru ko smo zadovoljni tudi s skoraj-optimalnimi rešitvami optimizacijskega problema, ki jih definiramo takole: Bodi Cmin strošek optimalne rešitve in bodi Cmax strošek ene od najslabših rešitev, (torej Cmin < c < Cmax za vsako dopustno rešitev) Izberimo si e > 0. Rešitev s stroškom C < Cmin + c{cmax — Cmin) imenujemo s-skoraj optimalna rešitev. Po definiciji c govori o kvaliteti rešitve na nekako normirani stroškovni funkciji. Na primer za e = 0.10 skoraj optimalne rešitve niso za več kot 10% slabše od optimalne rešitve. Pri e = O dobimo optimalne rešitve, pri e = 1 pa kar vse dopustne rešitve. Tukaj velja opozoriti, da so mnenja, katere rešitve je smiselno proglasiti za skoraj optimalne, deljena. Namesto o skoraj optimalnih rešitvah bomo tu raje govorili o množici zaželjenih rešitev, ki je lahko množica skoraj optimalnih rešitev za neki c, lahko pa za množico zaželjenih rešitev vzamemo tudi kakšno drugo podmnožico množice S. Ce povzamemo oznake iz dokaza izreka 2, ponovno pa definiramo Ki, K in pojem 'uspeh algoritma SA', potem lahko dokažemo podoben izrek za verjetnost zadetka nove množice zaželjenih rešitev. V tem razdelku naj: • Ki označuje število stanj, iz katerih vse poti, ki gredo samo navzdol, končajo v eni od zaželjenih rešitev. • K označuje število stanj, iz katerih obstaja pot, ki gre samo navzdol in konča v eni od zaželjenih rešitev. Očitno K > Ki. Tokrat bomo rekli, da je algoritem uspel (najti zaželjeno rešitev) brž ko je dosegel stanje, iz katerega obstaja vsaj ena pot, ki gre samo navzdol in konča v stanju, ki ustreza zaželjeni rešitvi. Z natanko istim premislekom kot v dokazu izreka 2 bi pokazali, da velja Trditev 1 Obstaja konstanta no, tako da velja 'in > no PsA{n) < P-Ticsin) (12) kjer je PaÌ^) verjetnost, da je algoritem A našel zaželjeno res'itev v n korakih. Trditev lahko zapišemo še nekoliko drugače: Posledica 1 Bodi Ps^(no) < p in no > j^ Ki \ TO^I k - min Označimo nncs = min{ti; P7Z£s(n) > p) in nsA min{n; P5^(n) > p}. Potem je nsA > nncs Torej je pri dani zahtevani kvaliteti rešitve in pri dani (dovolj veliki) minimalni zahtevani verjetnosti uspeha število potrebnih korakov manjše, če se odločimo za algoritem HCS namesto za algoritem 9. Vzporedne implementacije algoritma v tem razdelku predstavimo izrek, analogen izreku 2, ki velja za vse (nam) poznane paralelizacije algoritma V literaturi sta znana dva modela paralelizacije algoritma SA. Prvi [BoLu84, FgKOBS] temelji na delitvi podatkov, 46 kar v primeru problema trgovskega potnika pomeni, da cikel, ki predstavlja začetno rešitev, razbijemo na več poti in jih razdelimo procesorjem. Vsak od procesorjev nekaj časa optimizira svoj del poti (lahko si mislimo, da sta začetna in končna točka fiksirani), potem pa si procesorji izmenjajo podatke. S tem je doseženo, da lahko algoritem (s pozitivno verjetnostjo) doseže katerokoli dopustno rešitev. Drugi model vsem procesorjem dodeli nerazdeljeni problem, procesorji na njem vsak zase izvajajo običajni algoritem SA, po določenem času pa se 'sinhronizirajo'. Sinhronizacija tu pomeni, da na osnovi dotlej najboljših rešitev izberejo nove začetne rešitve. Preizkušeni so bili različni kriteriji sinhronizacije, na primer izbira najboljše rešitve, izbira n najboljših rešitev, slučajna izbira, na primer glede na Boltzmanovo porazdelitev, itd. [LaAr87, DoSS87, ABHL86]. V nadaljevanju bomo definirali model, ki zajema vse zgoraj naštete različice kot posebne primere. Za ta splošni model se da pokazati analogni izrek Izreku 2. Ker je mogoče algoritem lokalna optimizacija TICS naravno implementirati na več procesorjih z optimalnim pospeškom (saj nimamo nobenih izgub zaradi komunikacije oziroma sinhronizacije), ni presenetljivo, daje tudi na več procesorjih SA asimptotsko slabši od lokalne optimizacije. (Pospešek pri paralelnem izvajanju je definiran s takoimenovanim Gustafsonovim zakonom [GustSS], ki je na glavo postavljena oblika Amdahlovega zakona [Amda67]. Gustafeonov zakon mnogo očitneje pokaže moč vzporednega izvajanja algoritmov, zato je bil seveda lepo sprejet v krogih, ki se s tem ukvarjajo. Na kratko in neformalno povedano zakona povesta naslednje; če imamo na voljo n procesorjev optimalni pospešek pomeni, da bomo porabili n-krat manj časa kot prej. Ah, še lepše, na n procesorjih ob optimalnem pospešku lahko v istem času rešimo n-krat večje probleme.) V splošnem modelu predpostavljamo, da p procesorjev (neodvisno) izvaja splošni algoritem, imenovali ga bomo VSA, s sinhronizacijsko razporeditvijo (angl. sinchroniza-tion schedule). Namesto 'temperature' (ki je v splošnem lahko različna od procesa do procesa) tu uporabimo števec korakov algoritma in verjetnost, da bo algoritem sprejel korak 'gor', je zdaj funkcija števila kcuakov p = p(i). Zaporedje 0,t)i,ti2.....Vk,... zdaj beremo; naredi ui korakov do prve sinhronizacije, potem naredi dj do druge sinhronizacije, itd. Oziroma, sinhroniziraj se prvič pri tij-tem koraku, drugič pri uj-tem koraku, itd. Algoritem zapišemo podobno kot prej: Algoritem VSA: generiraj slučajno začetno stanje J := 0; repeat repeat i:=i+l; slučajno izberi soseda if sosed je boljši then premakni se else (* sosed je slabši *) premakni se z verjetnostjo p = p(i) until sinhronizacija izberi novo začetno stanje in/ali izmenjaj podatke until preveč korakov Oba prej omenjena pristopa k paralelizaciji 5,4 sta posebna primera splošnega algoritma PSA. Verjetnost koraka 'gor' zdaj ni odvisna od parametra T, ampak od i. Ponovno bomo uporabili iste oznake kot v dokazu izteka 2. Nekoliko drugače bomo definirali samo verjetnost qi = min{ verjetnost, da VSA ne gre 'gor' v fazi i na nobenem od procesorjev] (13) kjer minimum izračunamo po vseh možnih stanjih danega primerka problema. Izraz "faza «'" tu nadomešča frazo "med sinhronizacijama i — 1 in j". V dokazu Izreka 3 bomo ponovno predpostavili g; —» 1 ko gre t —» oo. To bo gotovo res, če se bo sistem 'ohlajal', ali, z drugimi besedami, če bo maksimalna temperatura (po vseh procesorjih) kakorkoli šla proti 0. Verjetnost, da p neodvisnih izvajanj algoritma lokalna optimizacija najde globalni optimum v n vzporednih korakih je očitno omejena z istim tipom spodnje meje kot če imamo samo eno izvajanje. Pvncsin) = l-il-Pncsin))" > 1-(1-(1-Q))'' = l-Q" ----(14) kjer je N ) (15) Analogno kot prej bomo rekli, daje algoritem VSA uspel, brž ko je vsaj eden od procesorjev našel stanje, iz katerega pelje vsaj ena pot, ki gre samo navzdol, in konča v enem od globalnih optimumov. Podobno kot prej dobimo Lema 3 Za n = ^ Vk + Vi, kjer je O < Vi < v,-, velja k=i PvsA(n) < (l - (16) In Izrek 3 Obstaja konstanta no, tako da velja Vn > no ==> PvsA{n) < PvTics{n) (17) Podrobnosti opuščamo. (Vsebina razdelka in dokaz izreka je rezultat krajšega obiska v laboratoriju za paralelne algoritme na Ecole Normale Superiuere de Lyon in je objavljena v [BFZ89a, BrFZ89, 2ero90].) Opomba: V posebnem primeru, ko vzporedno poganjamo p neodvisnih procesov, lahko zgornjo mejo za algoritem VSA nekoliko izboljšamo. V tem primeru imamo namreč p neodvisnih poskusov, od katerih je vsak en običajni (zaporedni) tek algoritma SA. Razliko pojasnimo preprosto: V rezultatu leme, enačba (16), 'manjkajoča' potenca p na faktorju (1 — je posledica naše implicitne predpostavke, da smo vzporedni tek algoritma začeli z enim začetnim stanjem (in ne s p-timi). Lahko bi se prepričali, da izrek 3 tudi v tem primeru velja. 10. Zaključek Namen sestavka je bil predstavitev algoritma SA, ki je bil v zadnjih letih deležen precej pozornosti v strokovni javnosti. Pregled teoretičnih in praktičnih rezultatov kaže, daje vrednost algoritma v splošnem še nejasna. Asimptotski rezultat, ki ga predstavimo, implicira, da v vseh primerih algoritem ne more biti najboljši. Verjetno je relativna uspešnost algoritma (glede na tekmece) bistveno odvisna od lastnosti prostora stanj, ki je pri različnih problemih kombinatorične optimizacije lahko bistveno različen. Omenimo tukaj sveži članek [Sasa91], ki dokazuje povezavo med 'gostoto' prostora stanj in mejo za uspešnost Metropolisovega algoritma. Potrebno bo še precej eksperimetalnih študij, preden bo jasno, v katerih primerih se Ohlajanje res izplača. Zahvala: Članek temelji na delu disertacije, ki je nastala pod mentorstvom prof. Tomaža Pisanskega. Zahvaljujem se mu za pomoč in vzpodbudo. Zadnja verzija članka je nastala med avtorjevim obiskom prof. Wilfrieda Imricha na Montanuniversität v Leobnu. Literatura [AaKo87] E.H.L.Aarts, J.H.M.Korst, Boltzmann Machines and Their Applications' PARLE Parallel Architectures and Languages Europe, Lecture Notes in Comp. Sci. 258, Springer, Berlin 1987, 34-50 [AaKo88] E.H.L.Aarts, J.H.M.Korst, Computations in massively parallel networks based on the Boltzmann machine: A rewiew, Parallel Computing, 9 (1988/89) pp. 129-145 [ABHL86] E.H.L.Aarts, F.M.J.Bont, E.H.A.Habers, P.J.M. Laarhoven: Parallel Implementations of the Statistical Cooling Algorithm, INTEGRATION, the VLSI Journal 4 (1986) pp. 209-238 [Amda67] G.M. Amdahl: Validity of the single-processor approach to achieving large scale computing capabilities. AFIPS Conference Proceedings, Atlantic City, N.J., Apr.18-20 30 AFIPS Press, Restn, Va. 1967 pp. 483-485 [AnMS87] G. Andreatta, F. Mason, P. Serafini (eds.), Advanced School on Stochasiics in Combinatorial Optimization, World Scientific, Singapore 1987 [BGAB83] L. Bodin, B.Golden, A.Assad, M.Ball, Routing and Scheduling of Vechicles and Crews, the State of the Art Compu t & Ops. Res. 10 (1983) pp. 63-211 [BoLu84] E.Bonomi, J.L.Lutton, The A^-city traveling salesman problem: Statistical Mechanics and the Metropolis algorithm, SIAM rewiév 26 1984 [BoLu86] E.Bonomi, J.L.Lutton, The asymptotic behaviour of quadratic sum assignement problems: A statistical mechanics approach, European journal of Operational Research 26 1986 pp. 295-300 [BoRV87] G.E.Boender, A.H.G. Rinooy Kan, C. Vercelis: Stochastic Optimization Methods, v Advanced School on Stochasiics in Combinatorial Optimization, G. Andreatta, F. Mason, P. Serafini (eds.):. World Scientific, Singapore 1987 [BrFZ89] [BFZ89a] [B u Re 84] [Cern84] [DoSS87] [DoSk88] [DuSc88] [FeK085] [Frie79] [GaJo79] [GeGe84] [GeMi87] [Gida85] [GoSk86] [Gust88] [Grov87] B.Braschi, A.G.Ferreira, J. Zerovnik: On the Behaviour of Simulated Annealing, Research Report no.89-10, 1989, LIP-IMAG, Lyon, France B.Braschi, A.G. Ferreira, J.Zerovnik: On the Asymptotic Behaviour of Parallel Simulated Annealing, v Parallel Computing 89 (eds: D.J.Evans, G.R. Joubert, F.J.Peters) North-Holland, Amsterdam 1990, 263-268 R.E.Burkard, F.Rendi, A thermodinamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research 17 1984 pp. 169-174 V. Cerny, A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm, Journal of Optimizaiion Theory and Applications 45 1984 pp. 41-51 J.G.Donnett, M.Starkey, D.B.Skilicorn, Effective Algorithms for Partitioning Distributed Programs, (preprint) Queen's University, Kingston, Canada 1987 J.G.Donnett, D.B.Skilicorn, Code Partitioning by Simulated Annealing, v: Parallel Processing and Applications,- E.Chiricozzi and A.D'Amico feda.;, North-Holland, 1988 G.Dueck and T.Scheuer, Threshold Accepting, A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing, (preprint) Heildelberg Scientific Center TR 88.10.011 1989 + E. Feiten, S.Karlin and S.W.Otto: The traveling salesman problem on a hypercubic, MIMD computer Proceedings of the 1985 International Conference on Parallel Processing Avgust 20-23, 1985 R. Friedvals. Fast Probabilistic Algorithms, Lecture Notes in Computer Science 74, SpringerVerlag, Berlin, 1979, pp.57-69 M.R. Garey, D.S. Johnson , Computers and Intractability, W.H. Freeman and Co., San Francisco (1979) * S.Geman, D.Geman, Stochastic Relaxation, Gibbs Distributions and the Bayesian Restoration of Images, IEEE Trans PAMI 6 (1984) S.B. Gelfand, S.K. Mitter, Simulated Annealing V Advanced School on Stochasiics in Combinatorial Optimization, (eds:) G. Andreatta, F. Mason, P. Serafini, World Scientific, Singapore 1987 / * B.Gidas, Nonstationary Markov Chains and Convergence of the Annealing Algorithm, J.Stat. Phys. 39 (1985) pp. 73-131 B.Golden and C.Skiscim: Using Simulated Annealing to Solve Routing and Location Problems, Naval Res. Log. Quarterly 33 1986 pp. 261-279 J.L. Gustafson: Reevaluating Amdahl's Law, Communications of the ACM 31 1988 pp. 532-533 L.K.Grover, GRIM: A Fast Simulated Annealing Program for Standard Cell Placement IEEE 1987 Custom Integrated Circuits Conference pp. 622-624 1987 [HaSa89] H. Haario, E. Salesman, On the Definition and Convergence of the Simulated Annealing Process in General State Space, Reports of the Dept. of Math., University of Helsinki, 1989 [H0UI86] V.E.Hopcroft, J.D.Ullman: Uvod v teorijo avtomatov, jezikov in izračunov, (prevod B.Vilfan), Fakulteta za elektrotehniko, Ljubljana 1986 [JAMS85] D.S.Johnson, C.R.Aragon, L.A.McGeoch and C.Schevon: Optimization by simulated Annealing: An Experimental Evaluation preprint, 1985 [John90] M.E.Johnson, Simulated Annealing & Applications, American Science Press, New York [KÌGV83] S.Kirckpatrick, C.D.Gellat, Jr., M.P.Vecchi, Optimization by Simulated Annealing Science 1983 220 pp. 671-680 [KhSV81] * A.Khačaturjan, S.Semenovskaja and B.Vain-stein: The Thermodynamical Approach to the Structure Analysis of Chrystals Acta Cryst A37 1981 pp. 742-754 [Kern86] W.Kern: A Probabilistic Analysis of the Switching Algorithm for the Euclidean TSP, Universität zu Köln, Report No 86.28. [KLPP86] S. Klavžar, M.Lokar, M. Petkovšek, T. Pisanski, Diskretna optimizacija DMFA SRS, Ljubljana, 1986 [Knut81] D.E.Knuth: Algorithms in modem mathematics and computer science, Lecture Notes in Comp. Sci. 122, Springer-Verlag, Berlin 1981 [Koza86] J.Kozak, Podatkovne strukture in algoritmi, DMFA SRS, Ljubljana, 1986 [LALW89] Laarhoven, P.J.M., Aarts, E.H.L., Lint, J.H. and Wille, L.T.: New Upper Bounds for the Footbal Pool Problem for 6,7 and 8 Matches Journd of Combinatorial Theory, Series A, 52 pp. 304312 (1989) [LaAr87] P.J.M. Laarhoven, and E.H.L. Aarts, Simulated Annealing, Theory and Applications, D.Reidel Publishing Company, Dordrecht (1987) [Laar88] P.J.M. Laarhoven: Theoretical and computational aspects of simulated annealing, Centrum voor Wiskunde en Informatica, Amsterdam 1989 [LaDe88] J. Lam, J-M. Delosme, An Efficient Simulated Annealing Schedule: Derivation, Report 8816 in An Efficient Simulated Annealing Schedule: Implementation and Evaluation, Report 8817, Yale University, 1988 [LLRS85] &.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, D.B. Schmoys (eds.). The Traveling Salesman Problem, John Wiley sons (1985) [LeBi89] C. Lee and L. Bic Comparing Quenching and Slow Simulated Annealing on the Mapping Problem Proceedings of the third annual parallel processing symposium, California State University, Fullerton 1989 [L1TT89] D.C.Llewellyn, C.Tovey and M.Trick: Local optimization on graphs. Discrete Applied Math. 23 1989 pp. 157-178 [LuMe86] M.Lundy, A.Mees, Convergence of an annealing algorithm, Mathematical programming 34 1986 pp. 111-124 [LuBo86] J.L.Lutton, E.Bonomi, Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem, R.A.LR.O. Oper. Res. 20 1986 pp. 177-197 [MaffSe] F.Maffioli, Randomised algorithms in combinatorial optimisation: a survey, Discreto Applied Mathematics 14 1986 pp. 157-170 [MRRT53] N.Metropolis, A.Rosenbluth, M.Rosenbluth, A.Teller, E.Teller, Equation of State Calculations by Fast Computing Machines, J.Cham. Phys. 21 1953 pp. 1087-1091 [MÌRS86] D.Mitra, F.Romeo, A. Sangiovanni-Vincentelli, Convergence and Finite Time Behavior of Simulated Annealing, Adv. Appi. Prob. 18 1986 pp. 747-771 [Pinc70] * M.Pincus: A Monte Carlo Method for the Approximate Solutions of Certain Types of Constrained Optimization Problems Opcr. Res 18 1970 pp. 1225-1228 [Rabi76] M.O.Rabin: Probabilistic Algorithms, v Algorithms and Complexity (ur. Traub), 21-39, Academic Press 1976 [RaSh89] M.A.Rahin, J.Shield, Parallel Partitioning of Concurrent VLSI Simulation Graphs, (preprint) Dept of Electronic and Electrical Engineering, Loughborough University of Technology, 1989 [RÌTÌ85] ♦ A.H.G. Rinooy Kan, G.T. Timmer, Stochastic Global Optimization Methods, parts I & II, Econometric Institute, Erasmus University, Rotterdam, 1985 [SaHa88] G.H.Sasaki, B.Hajek, The time Complexity of Maximum Matching by Simulated Annealing, Jour. ACM 35 1988 pp. 387-403 [Sasa91] G.Sasaki The effect of the density of states on the Metropolis algorithm Information Processing Letters 37 (1991) pp. 159-163 [2ero88] J. Zerovnik, Comparison of Asymptotic Behaviour of two Randomised Heuristic Approaches, Preprint Series Dept. Math, University E.K. Ljubljana 26, pp. 186-192 (1988) (poslano V objavo) [2ero90] J. Zerovnik, Verjetnost v kombinatorični optimizaciji, Univerza v Ljubljani, FNT, (oddana) doktorska disertacija, 1990 [Wels83] D.J.A.Welsh: Randomised algorithms. Discrete Applied Math. 5 (1983), 133-145 [WÌ1187] L.T. Wille: The Footbal Pool Problem for 6 Matches: A new Upper Bound Obtained by Simulated Annealing, Journal of Combinatorial Theory, Series A, 45 pp. 171-177 (1987) Z zvezdico * smo označili posredne reference. ZVEZNE BAYESOVE NEVRONSKE MREŽE INFORMATICA 2/91 Keywords: machine learning, artificial neural networks, artificial Intelligence, naive Bayes, Hopfield's model Igor Kononenko Univerza v Ljubljani Fakulteta za elektrotehniko in računalništvo Tržaška 25, Ljubljana POVZETEK V prispevku je opisajia posplošitev Bayesovih nevronskih mrež na zvezna stanja nevronov, analogno Hopfieldovi posplošitvi. Podane so posplošene prehodne funkcije in dokazana stabilnost izvajanja zvezne Bayesove nevronske mreže, ki temelji na verjetnosti in zvezne Bayesove nevronske mreže, ki temelji na razmerju verjetnosti. Opisane so prednosti zveznih Bayesovih nevronskih mrež pred diskretnimi. CONTINUOUS BAYESIAN NEURAL NETWORKS In the paper the Bayesian neural network model is generalized to continuous states of neurons, analogously to Hopfield's generalization. The generalized transition functions are given together with the proof of convergence of execution for the continuous Bayesian neural network beised on probability and for the continuous Bayesian neural network based on probability ratio. The advaifeges of continuous Bayesian neural network models are discussed. 1 Uvod V (Kononenko 1990) so opisane diskretne Bayesove nevronske mreže, ki temeljijo na verjetnosti (BNM-p), in diskretne Bayesove nevronske noreže, ki temeljijo na razmerju verjetnosti (BNM-odds). Celotna kombinacijska funkcija za izračun novega stanja Sj in s tem izhoda nevrona v BNM-p je definirana z: S; = i5y(P{5y = l|5i,...,5jv)) (1) kjer je verjetnost, da je j-ti nevron aktiven, pri danih indeksih aktivnih nevronov in 1, če X>P(Sj- = l) Dj(X) = 5y, če X = P(Sj- = 1) (3) [o, če X< P(5y = 1) pragovna odločitvena funkcija. Pri tem so Si, i = 1..N trenutna stanja vseh nevronov v mreži in P(5y = 1) apriorna verjetnost aktivnega stanja j-tega nevrona. Če je izračunana verjetnost večja od apriorne verjetnosti, potem je novo stanje enako 1, če je enaka apriorni verjetnosti, potem se stanje nevrona ne spremeni, in če je izračunana verjetnost manjša od apriorne verjetnosti, potem je novo stanje nevrona enako 0. Celotna kombinacijska funkcija za izračun novega stanja iSj in s tem izhoda nevrona v BNM-odds je definirana z: 5-; = Dqi{odds{Sj = ll-S-i,.... 5;,)) (4) kjer je odds[Sj\Su--.,SN) = razmerje verjetnosti, da je j-ti nevron aktiven, pri danih indeksih aktivnih nevronov in ■ 1, le X> odds{Sj = 1) Dqi{X) = 1 5;-, le X= oddslSj = 1) [o, le X< odds{Sj = 1) (6) pragovna odločitvena funkcija. Pri tem so Si, i = l-.iV trenutna stanja vseh nevronov v mreži in odds{Sj) apriorna verjetnost stanja 1 j-tega nevrona deljena z apriorno verjetnostjo nasprotnega stanja. Če je izračunano razmerje verjetnosti večje od apriornega razmerja, potem je novo stanje enako 1, če je enako apriornemu razmerju, potem se stanje nevrona ne spremeni, in če je izračunano razmerje verjetnosti manjše od apriornega, potem je novo stanje nevrona enako 0. Ker stanja BNM-p in BNM-odds lahko zavzemajo samo diskretni vrednosti O in 1, jim pravimo diskretni. V (Kononenko 1990) je dokazana stabilnost asinhronega izvajanja za obe vrsti mrež iz poljubnega začetnega stajija, z uporabo funkcij podobnosti odvisnih samo od stanja mreže. Le te z asinhronim izvajanjem monotono padajo. Ker je možnih stanj diskretne nevronske mreže končno mnogo, nam to garantira prihod v fiksno točko v končnem številu iteracij. Oglejmo si še enkrat funkciji podobnosti za BNM-p in BNM-odds. Naslednja funkcija definira podobnost med aktivacijskimi nivoji nevronov in njihovimi trenutnimi stanji v BNM-p: - TT = " .iii ^ ^ Podobnost je večja, če je aktivacijski nivo (izračunana verjetnost, da je nevron aktiven) večji od apriorne verjetnosti, daje nevron aktiven in obratno. Za BNM-odds je funkcija podobnosti enaka, le da produkt teče preko vseh nevronov (ni pogoja 5,- = 1). V tem prispevku je podana generalizacija večsmernih BNM na zvezna stanja nevronov analogno Hopfieldovemu (1984) zveznemu modelu nevronske mreže. Namesto diskretnih stanj O in 1 je stanje nevrona v zvezni BNM predstavljeno z realno vrednostjo na intervalu [0,1]. Stanje nevrona bo proporcionalno verjetnosti, da je nevron trenutno aktiven. V naslednjem razdelku je na kratko opisan Hopfieldov zvezni model nevronske mreže. V nadaljnjih dveh razdelkih sta opisana zvezna modela večsmerne BNM-p in BNM-odds. V zadnjem razdelku prikazane prednosti in slabosti zveznih modelov. 2 Hopfieldov zvezni model nevronske mreže Hopfield (1984) za zvezni model uporablja isto topologijo kot pri diskretni nevronski mreži, t.j. vsak nevron je povezan z vsakim. Kombinacijska funkcija diskretnega modela je podana z enačbo (Hopfield 1982): E + = + (8) V Hopfieldovem modelu so Tji elementi spominske matrike, dobljene kot vsota zunanjih produktov učnih vzorcev, ki so popravljeni tako, da so vrednosti komponent O spremenjene v -1. Ij predstavlja konstanten vhod v j-ti nevron. Model BNM brez povratnih povezav (t ^ j) ustreza spominski matriki z ničelno diagonalo {Tu = O za vse i = 1...N). Si ima lahko vrednosti O in 1 kot v originalnem Hopfieldovem modelu, čeprav učno pravilo Hopfieldovega modela uporablja vrednosti -1 in 1. Sim{Si,...,Si^) = Kombinacìjska funkcija zveznega Hopfield-ovega modela je analogna. Dinamika zveznega modela je opisana z naslednjima enačbama (Hopfield 1984): + = (S) i.ij^i Sj = (10) kjer je Si stanje oziroma izhod »-tega nevrona, uy vhod (aktivacijski nivo) j-tega nevrona in IjfRj, C j konstante, g j je izhodna funkcija, ki definira relacijo med vhodom in izhodom, in je odvedljiva in sigmoidna z asimptotama O in 1. Iz enačbe (9) sledi, daje hitrost spremembe uy proporcionalna razliki med trenutnim in novim Uj, izračunanim po enaičbi (8). V originalni Hopfieldovi (1984) enačbi je izpuščen pogoj t ^ j, ker za Hopfieldovo pravilo učenja velja, da so vsi Ta = 0. Stabilnost zveznega modela pokaže Hopfield tako, da definira "energijsko" funkcijo stanja sistema: ^ i i = (11) ki s časom monotono pada, ker velja: dt (12) m dE 3 Zvezna Bayesova nevronska mreža, ki temelji na verjetnosti Informacijski prispevek t-tega nevrona za aktivnost j-tega nevrona je v diskretni BNM-p dobimo z logaritmiranjem enačbe (2) in je podan z Bolj splošna definicija informacijskega prispevka je podana z kjer Si predstavlja trenutno stanje t-tega nevrona. Si lahko zavzema poljubno vrednost na intervalu [0,1] in ustreza verjetnosti, daje t-ti nevron aktiven. Posplošen logaritem enačbe (2) vsebuje vsoto po vseh nevronih in ne samo po aktivnih nevronih: -log2P{Sj\Su...,SN) = (13) Z antilogaritmiranjem dobimo kombinacijsko funkcijo zvezne BNM-p, ki je posplošena enačba (2): P{S,-\Su. fPjSi Si)) P{Sj) Si (14) Posplošitev pogojne verjetnosti P(5y|5< = 1), pri negotovi evidenci, da je 5,- = 1, je podana z Si X P{S,\Si = 1) (Diara 1987). Ta posplošitev vodi do drugačne definicije enačbe (14), kjer lahko več nevronov predstavlja isti atribut. Enačba (14) je smiselna posplošitev, če se vplivi različnih nevronov, čeprav mogoče predstavljajo isti atribut, obravnavajo neodvisno. Če v enačbi (13) namesto —l^i,..., 5jv) pišemo Aj, namesto -log2P{Sj) pišemo I j in namesto pišemo Tji, dobimo enačbo (8), t.j. kombinacijsko funkcijo Hopfieldovega modela. Zato lahko za opis dinamike zvezne BNM-p uporabimo enačbi (9) in (10). Dokaz stabilnosti je ekvivalenten Hopfieldovemu dokazu (glej razdelek 2). Posplošena funkcija podobnosti (7) na zvezna stanja je torej: Sim{Si,...,Sif) -9( P{S:) (15) Če enačbo (16) logaritmiraino in namesto —pišemo Aj, namesto —log2odds{S,-) pižemo 7y in namesto pižemo Tfi^, dobimo: 4 Zvezna Bayesova nevronska mreža, ki temelji na razmerju verjetnosti Težo evidence stanja Si t-tega nevrona za aktivnost j-tega nevrona v diskretni BNM-odds dobimo z logaritmiranjem enačbe (5) in je podana z Bolj splošna definicija teže evidence je podana z „ , odds(Sj = 115,• = 1) (1 - Si) X log2 oddsjSj = 1[5.= 0) odds{Sj = 1) kjer Si predstavlja trenutno stanje t-tega nevrona. 5,- lahko zavzema poljubno vrednost na intervalu [0,1] in ustreza verjetnosti, da je t-ti nevron v stanju 1 (oziroma 1 minus verjetnosti, da je nevron v stanju 0). Posplošena kombinacijska funkcija (5) za zvezne BNM-odds je sledeča: odds[Sj Si,..., Sif) = =odds{Si = 1) n (odds{Sj = 1[5.- = 1) odds{S,- = 1) X (oddsjSj = l\Si = 0)\ V odds{Sj = 1) ; (16) Ustrezna posploSena funkcija podobnosti je pri zvezni BNM-odds različna od funkcije podobnosti zvezne BNM-P: =n } ( PjS: = 0) ^ s,=l) 1-s/ (17) (18) Če zgoraj definirani aktivacijski nivo nevrona Aj- uporabimo v enačbi (9) dobimo enačbo za opis dinamike zvezne BNM-odds. Ker nova enačba ni enaka enačbi za zvezno BNM-P, dokaz stabilnosti ni tako očiten. Iz dokaza stabilnosti Hopfieldovega modela podanega v razdelku 2 je razvidno, da je za stabilnost pri enačbi (11) zadosten pogoj: dEi dt (19) Če v enačbi (1| uporabimo za Ei naslednji izraz: i ^ i i?i3 il-Sj)SiTf^ + {l-Si){l-Si)Tfn (20) potem je pogoj (19) izpolnjen, ker velja: dEi dt __ ^ (dEi dSj\ ■ m^-iv dt Ai (21) S tem je stabilnost zveznega modela BNM-odds dokazana. 5 Zaključki Bayesove nevronske mreže so lahko diskretne ali zvezne ter lahko temeljijo na verjetnosti ali na razmerju verjetnosti. Razlika med Hopfiel-dovim modelom in BNM je v učnem pravilu. Za učenje BNM zadošča osnovno Hebbovo pravilo (Hebb 1Ì949), za katerega je precej nevrofiziološke evidence, da se po tem pravilu učijo biološki nevroni. Uteži na sinap-sah ustrezajo apriornim verjetnostim, da sta povezzoia nevrona aktivna. Hopfieldov model uporablja posplošeno Hebbovo pravilo. Uteži na sinapsah ustrezajo rEizliki med verjetnostjo, da sta povezana nevrona v istem stanju, in verjetnostjo, da sta povezéina nevrona v različnem stanju. Zato uteži Hopfieldovega modela vsebujejo manj informacije kot uteži pri BNM. Kompleksnost učenja in izvajanja je pri obeh modelih enaka, po klasifikacijski pravilnosti pa BNM daleč presega Hopfieldov model (Kononenko 1990). Za opis stanja modela Hopfield uporablja energijsko funkcijo, ki je analogna funkciji podobnosti za opis stanja BNM. Logaritem funkcije podobnosti lahko interpretiramo kot entropijo ali informacijsko vsebino sistema. Iz tega sledi, da je fiksna točka stanje sistema z lokalno minimalno entropijo. Prednost zveznih BNM je v večji fleksibilnosti predstavitve znanja. Vhodni podatki so lahko "mehki" in nezanesljivi. Dani primer ima lahko več vrednosti za isti atribut, ki jim je možno določiti zaupanje. Tudi odgovor zvezne BNM je zato lahko bolj fleksibilen. BNM-P ima prednost pred BNM-odds, ker se lahko entropija direktno posploši na več kot dva disjunktna dogodka. BNM-P je zato bolj prožna in računsko manj zahtevna. BNM-odds je primerna samo za binarne atribute in razrede in je manj primerna za predstavitev manjkajočih podatkov. V diskretni BNM-odds je lahko manjkajoči podatek predstavljen z apriornim razmerjem verjetnosti (odds) samo med učenjem, medtem ko je v zvezni BNM-odds lahko predtavljen z apriornim razmerjem verjetnosti, tako med učenjem kot med izvajanjem. Interpretacija izvajanja BNM-P je bolj naravna (prispevek informacije v bitih) kot interpretacija BNM- odds (teža evidence). Po drugi strani pa BNM-odds potrebuje bistveno manj nevronov za predstavitev istega problemskega prostora kot BNM-P. Z nadaljnjimi raziskavami bo potrebno eksperimentalno testiranje zveznih BNM. Potrebno bo preveriti prednosti zveznih BNM na realnih problemih. Poleg bolj fleksibilne predstavitve znanja omogočajo zvezne BNM, z asinhronim izvajanjem, ki služi kot globalnainf ormaci ja, bolj zanesljivo delovanje. Namreč zaradi asinhronosti bodo nevroni, katerih spremembe stanj so bolj zanesljive, prej spremenili svoje stanje, kar bo vplivalo na spremembe stanj ostalih nevronov, preden le-ti uspejo spremeniti svoje stanje. Spremembe niso diskretne (torej niso drastične) ampak majhne z majhnimi vplivi in ne prehudimi posledicami. Reference Hebb, D.O. (1949) The Organization of Behavior. New York: Wiley. Hopfield J.J. (1982) Neural networks and physical systems with emergent collective computational abilities. Proc. of the National Academy of Sciences 79:2554-2558. Hopfield J.J. (1984) Neurons with graded response have collective computational properties like those of two-state neurons. Proc. of the .National Academy of Sciences 81:4586-4590. Ihara J. (1987) Extension of conditional probability and measures of belief and disbelief in a hypothesis based on uncertain evidence. IEEE Trans, on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, no.4, pp. 561-568. Kononenko, I. (1990) Bayesove umetne nevronske mreže. Informatica, letnik 14, št. 3, str.72-86. ALGORITEM ZA PRETVORBO TELESA INFORMATICA 2/91 PREDSTAVLJENEGA Z OVOJNICO V PREDSTAVITEV Z OSMIŠKIM DREVESOM Keywords: geometric modeling, boundary Natalija Trstenjak, representation, octree representation, computer Borut Žalik, Nikola Quid graphics Tehniška fakulteta Maribor Smetanova 17, 62000 Maribor Slovenija, Jugoslavija Predstavitev teles z ovojnico Je široko uporabljena v računalniški grafiki In predstavlja tudi primarno predstavitev v Eksperimentalnem modellrnlku teles, ki smo ga razvili. Vendar pa Je izvajanje Boolovlh operatorjev, ki so standardno orodje vsakega modellrnlka, zelo težavno nad telesi predstavljenimi z ovojnico. Zato smo kot sekundarno predstavitev v modellrnlku uvedli predstavitev z osralškimi drevesi, ki Je za izvajanje Boolovlh operatorjev prav idealna. V tem ćlanku obravnavamo pretvorbo predstavitve z ovojnico poljubnega telesa v predstavitev z osmlékim drevesom. Podrobno smo predstavili iskanje sećlžč med oktantom^ in poljubnim telesom, ki Je najbolj kritičen del pretvorbe. An Algorithm for Boundary to Octree Conversion The boundary representation is widely used In computer graphics and It represents a primary representation in our Experimental geometric modeler. An Implementation of the regularized Boolean operators which are the standard tools in the solid modelers is very complicated in the case of boundary representation. For this reason the octree representation is Included as a secundary representation and It is almost Ideal for the Implementation of Boolean operators. In this papei , we consider the problem of converting the boundary representation of a polyhedron to its octree representation. The critical work In the subdlvison process is to determine how an octant Intersects the polyhedron and this problem is described in details. 1 Uvod geometry", CSG) In z osmlSklral drevesi ("octree representation") ([REQU821, [REQU83J, [MORT851). Vsaka Osnovni problem geometrijskega modeliranja je v izmed predstavitev Ima svoje slabosti in prednosti, opisovanju tridimenzionalnega zveznega telesa v Zato večina komercialnih raodelirnikov temelji na digitalnem računalniku tako, da Je predstavitev takolmenovani hibridni predstavitvi, ki Jo dobimo s nedvoumna [HII.L82). Znanih je več nedvoumnih kombinacijo vsaj dveh različnih predstavitev, Idealno predstavitev, najpogostejše pa so predstavitev z arhitekturo bi tvorile vse tri prej omenjene ovojnico ("boundary representation", B-rep), predstavitve [MILL89). 2a hibridno predstavitev so predstavitev s temeljlml gradniki ("constructive solid izjemno pomembni učinkoviti pretvorbenl algoritmi iz one predstavitve v drugo. V prispevku bomo podali pretvorbenl algoritem Iz predstavitve z ovojnico v predstavitev z osmlšklm drevesom. Predstavitev z ovojnico hrani podatke o povržju telesa In Je sestavljeno iz ogllšč, robov In ploskev. Podatkovna struktura mora hraniti tako sosednostne relacije kot geometrijske podatke, kar zahteva pazljivo načrtovanje podatkovne strukture. Ker Je vsaka ploskev predstavljena eksplicitno, omogoča dodajanje specifičnih Informacij vsaki ploskvi telesa (npr. barva, kvaliteta materiala), prav tako pa v principu nI težav pri vgradnji poljubno oblikovanih ploskev 1CHIY871. Pri vlzuallzacljl predstavljenega telesa večjih težav nI, saj lahko žični model prikažemo zelo hitro, mnogo klasičnih algoritmov računalniške grafike za odstranjevanje zakritih robov, senčenje In uporabljanje pa temelji na tej predstavitvi (PRAT831. Telesa lahko modeliramo z nizko - nlvojsklml operatorji, npr. Eulerjevlml operatorji, z uporabo višje - nlvojsklh lokalnih operatorjev In z Boolovlml operatorji (tMANT821, [WILS85I, tCHIY851, (MANT881). Prav Implementacija Boolovlh operatorjev, ki so standardno orodje vsakega geometrijskega modellrnlka, pa Je v predstavitvi z ovojnico zelo težavno [MANT83]. Predstavitev z osmlšklm drevesom temelji na principu rekurzlvne delitve prostora. Rezultat rekurzlvnega delitvenega procesa Je predstavljen z drevesom osme stopnje, katerega vozlišča so aH listi ali sinovi. Korensko vozllSče v Izhodnem drevesu predstavja vhodni prostor. Končna vozllšča-llstl predstavljajo oktante, ki vsebujejo enotske kocke Iste barve In so označena s črna ali bela, odvisno od tega ali se nahajajo znotraj ali zunaj telesa. Vmesna vozlišča Imenujemo notranja vozlišča in so označena s siva. Ta predstavljajo oktante v prostoru osmlškega drevesa, ki ležijo delno znotraj delno zunaj telesa In Jih v rekurzlvnem postopku delimo na podoktante. Vsak oktant ima predpisano osmläko kodo, ki določa njegov položaj glede na oktanta očeta. Osmlške kode oktantov so prikazane na sliki la, primer telesa In njegove predstavitve pa kažeta sliki Ib In Ic. Predstavitev z osmlšklml drevesi Je prav Idealna za izvajanje Boolovlh operacij. Vsa Izračunavanja pri Boolovlh operacijah temeljijo na celoštevlIski aritmetiki (vse potrebne zaokrožitve smo namreč odpravili že v fazi tvorbe osmlškega drevesa), zato so algoritmi Izredno robustni. Glavna slabost Je v tem, ker meja telesa ni eksplicitno znana, zato nI možno hitro prikazati npr. žičnega modela objekta; direktno Jih lahko vlzualIzlramo samo s tehnikami sledenja žarku ("ray tracing"). Prav tako predstavitev zahteva mnogo pomnilnika, s tem pa Je omejena tudi resolucija objekta ICLIF87]. Za predstavitev z osmlšklml drevesi razvijajo zaradi njenih dobrih lastnosti tudi specialno namensko aparaturno opremo [KAUF881. /6 / / /2 /V 7 2 ■z / / C 0 1 1 / / X a) Osmlške kode oktantov (oktant 4 je skrit) b) Primer telesa c) Njegova predstavitev z osmlšklm drevesom Slika 1 Osmlške kode oktantov ter predstavitev telesa z osmlšklm drevesom Naš Eksperimentalni geometrijski modelIrnlk (EGM) ima primarno predstavitev z ovojnico, sekundarno pa z osmišklmi drevesi. Predstavitev z ovojnico podpira 14 vgrajenih Eulerjevlh operatorjev, domena teles pa vključuje telesa z ravnimi ploskvami [ŽALI89al. Višje nlvojskl operatorji omogočajo tvorbo teles s translaclJsklm pomikanjem In z operatorji, ki upoštevajo značilnosti teles (ŽALI90). Vgrajeni so tudi Boolovl operatorji, ki pa so uspešni le nad konveksni telesi z lici, ki ne vsebujejo prstanov lŽAl.I89b). Zaradi tega smo se odločili, da bomo izdelali algoritem za pretvorbo predstavitve z ovojnico v predstavitev z osmlšklml drevesi. 2 Tehnike za tvorbo osmlškega drevesa iz predstavitve z ovojnico Poznamo različne tehnike za tvorbo osmlškega drevesa, ki se razlikujejo med seboj po obliki vhodnih podatkov. Vhodni podatki so različne predstavitve 3D teles, kot so na primer 3D polja, zaporedne sekcije, slike obrisa objekta, globinske slike in modeli objektov. Med modele objektov spada tudi predstavitev z 56 ovojnico. Poznamo dve tehniki za tvorbo osmläkega drevesa telesa, predstavljenega z ovojnico: tehnika označevanja komponent in tehnika deli-ln-vladaj. Tehnika označevanja komponent temelji na principu polnjenja notranjosti zaprte meje, zato ne potrebuje testiranja presečlSč. Algoritem Je sestavljen Iz dveh delov. V prvem delu pretvorimo mejo objekta v delno 3D binarno drevo. Crnl Usti drevesa predstavljajo celice, ki sekajo mejo objekta. V drugem delu delno binarno drevo prečno obiščemo In tiste nedoločene bele liste, ki odgovarjajo notranjosti ali zunanjosti telesa, klasificiramo v črna ali bela vozlišča, skladno s tehniko označevanja. Algoritem generira binarno verzijo osmiškega drevesa, ki jo lahko enostavno pretvorimo v osmlško drevo. Druga tehnika za pretvorbo poljubnega telesa, predstavljenega z ovojnico v predstavitev z osmiéklm drevesom, je tehnika dell_in_vladaj, ki Jo bomo v tem članku podrobno predstavili. Ta tehnika velja za grob pristop In pričenja z enojnim črnim vozliščem - korenom drevesa kot začetno aproksimacijo poljubnega telesa in nato nadaljuje z rekurzlvno delitvijo prostora osmlškega drevesa. Algoritem Je predstavljen na sliki 2. Deli_in_vladaJ ( vozlišče ) (• M ; meja - obris telesa Begin Case PRESEČIŠČE ( vozlišče,M ) of BELA : opusti vozlišče In vkorenlnjeno poddrevo ČRNA : vozlišče.barva = CRNA SIVA : begin vozlišče.barva = SIVA for 1 = O to 7 Dell_in_vladaj ( vozi išče.sini 11 ) end end End Slika 2 Algoritem tehnike del1-ln-vladaJ Kritičen del v procesu delitve je določiti, kako oktant seka poljubno telo. To lahko opravimo v dveh korakih: v prvem koraku pregledamo aH oktant seka katero koli ploskev poljubnega telesa. Ce seka, potem je oktant delno zunaj, delno znotraj telesa, pripadajoče vozlišče v osttilškem drevesu označimo s Giva In oktant delimo na podoktante. Drugače je oktant aH zunaj aH znotraj telesa. V drugem koraku, katerega bistvo je vsebnostnl test, določimo, katera od trditev je pravilna. Ce za katero koli ogllSče oktanta ugotovimo, da Je obdano s površino poljubnega telesa, se oktant nahaja znotraj telesa, vozlišče osmlškega drevesa označimo s črna, drugače pa se nahaja zunaj telesa in vozlišče osmlškega drevesa označimo z bela (H0ME881. 3 Ugotavljanje presečišča med oktantom In poljubnim telesom Testiranje presečišča med oktantom In poljubnim telesom Je v splošnem počasen proces. Da bi povečali hitrost testiranja presečišč, uvedemo Izločevalnl postopek, ki sestoji iz petih korakov oziroma testov: - testa minimax, - testiranja ravnin ploskev telesa, - testiranja ogllSč ploskev telesa, - testiranja presečnega mnogokotnlka, - testiranja lukenj ploskve telesa. Namen tega postopka Je v prvih dveh korakih zmanjšati število ploskev telesa, ki bodo prišle v naslednji korak. Izločamo ploskve, ki zagotovo ležijo zunaj oktanta in ga zato ne morejo sekati. Ce je število vseh Izločenih ploskev enako številu vseh ploskev telesa, v naslednji korak ne vstopimo, saj lahko v takem primeru določimo barvo vozlišča oziroma presečišča z vsebnostnlm testom. V tretjem koraku želimo ugotoviti, aH oktant seka katero od ploskev telesa, ki Jih nismo izločili In s tem določiti barvo vozlišča. Vsak nadaljnl korak obravnava presečišče bolj podrobno In v zadnjem, petem koraku, barvo vozlišča osmlškega drevesa, ki predstavlja pripadajoč oktant v prostoru osmlškega drevesa, zagotovo določimo. V podpoglavjih, ki sledijo, je podrobno obdelan vsak korak in zaključki, ki sledijo Iz rezultatov testiranja v omenjenem koraku. 3.1 Test minimax S testom minimax izločimo tiste ploskve telesa, ki zagotovo ne sekajo oktanta. Test Je razširjen na 3D prostor, z njim pa ugotavljamo prekrivanje omejitvenih škatel ("bounding box") ploskev telesa In oktanta (omejitvena škatla ploskve Je pravokotna škatla, katere robovi so vzporedni z osmi prostora osmlškega drevesa In omejuje ploskev). To Je prva groba selekcija ploskev, ki ne sekajo oktanta, saj zaradi narave testa minimax ne moremo trditi, da smo Izločili vse takšne ploskve iz nadaljnega postopka [GUID881. Kljub temu pa s tem testom Izločimo veliko število ploskev, še posebej pri večji globini osmlškega drevesa, ko je lahko oktant napram telesu zelo majhen. Ce s testom minimax Izločimo vse ploskve telesa, kar pomeni, da vse ploskve ležijo zunaj oktanta, se lahko oktant nahaja strogo znotraj telesa aH strogo zunaj telesa. Primer Je podan na sliki 3, kjer Je oktant narisan z močnejšo in telo s tanjšo črto. Da bi določili, katera od trditev Je pravilna, uporabimo vsebnostnl test ogllSč oktanta v telesu. V ' A i Vi / . / ■)jfM -tr^V ----J / a) Oktant strogo znotraj b) Oktant strogo zunaj telesa telesa Slika 3 S testom minimax smo izločili vse ploskve telesa a) Oktant zunaj telesa b) Oktant znotraj telesa Slika 5 Ploskve telesa 2, 3. 5 smo Izločili s testom minimax,ravnine ploskev 1, 4, 5 sovpadajo z ravninami oktanta Ce s testom minimax nismo izločili vseh ploskev telesa, oziroma ne moremo trditi, da ležijo vse zunaj oktanta, ne moremo določiti barve vozlišča osmiäkega drevesa. Ploskve, ki Jih nismo Izločili, testiramo v drugem koraku, ki vključuje test ravnin ploskev. Če vsota do sedaj Izločenih ploskev ni enaka Številu vseh ploskev telesa. Je barva presečišča odvisna od lege ploskev, ki Jih še nismo izločili. Te ploskve testiramo v naslednjem koraku, ki vključuje test ogllšč ploskev. 3.2 Test ravnin ploskev telesa 3.3 Test oglišč ploskev telesa S tem testom izločimo ploskve telesa, ki se oktanta dotikajo. Za vsako ploskev telesa izračunamo enačbo ravnine, v kateri leži. In Jo primerjamo z enačbami ravnin, v katerih ležijo ploskve oktanta. Ce ravnina ploskve telesa sovpada s katero od ravnin ploskev oktanta, leži ploskev telesa na eni od ploskev oktanta ali pa se oktanta dotika v enem od njegovih robov. Primer je podan na sliki 4, kjer so ploskve telesa označene s vodoravno šrafuro. V tem primeru se ploskev in oktant zagotovo ne sekata In ploskev Izločimo Iz nadaljnega postopka. Slika 4 Ploskve telesa, katerih ravnine sovpadajo z ravninami ploskev oktanta Ce Je vsota ploskev, ki smo Jih Izločili v prvem koraku, In ploskev, katere smo Izločili v drugem koraku, enaka številu vseh ploskev telesa, se lahko oktant nahaja le zunaj ali znotraj telesa (slika 5). Uporabimo vsebnostnl test, da ugotovimo, katera od navedenih trditev je pravilna In lahko skladno s tehniko označevanja določimo barvo vozlišča osmlškega drevesa. V tem koraku ne Izločamo ploskev, ampak želimo ugotoviti, ali katera od ploskev zagotovo seka oktant. Ploskve telesa, ki Jih testiramo v tem koraku, lahko: - ležijo znotraj oktanta, - sekajo oktant, - ležijo zunaj oktanta. a) OP=NP ; MP=0,ZP=0 b) OP=MP ; NP=0.ZP=0 c) OP=MP+NP : MP*0, NP»0, ZP=0 Slika 6 Ploskev leži znotraj oktanta Ploskev zagotovo seka oktant, če leži v celoti znotraj oktanta. ali pa seka oktant, ne glede na to ali Je konveksna ali konkavna in ali ima luknje ali ne. Ta dva položaja ploskve lahko enostavno doloClmo na podlagi lege njenih ogllS£. Naj Je OP število vseh ogllSč ploskve telesa. Število ogllSfi ploskve zunaj oktanta označimo z ZP, Število ogllžč znotraj oktanta z NP In število ogllSč ploskve na meji oktanta z MP. Ce se vsa ogllSča ploskve telesa nahajajo znotraj ali na meji oktanta, oziroma če velja 3.4 Test presečnega mnogokotnlka Za ploskve telesa, ki Jih testiramo v tem koraku velja, da Imajo vsaj eno ogllžče zunaj oktanta In nobenega oglièta znotraj oktanta oziroma velja OP = MP + ZP ; NP = O, ZP « O (3) Ploskve telesa lahko ležijo zunaj oktanta ali sekajo oktant (slika 8), na rezultat testa pa lahko vpliva tudi konkavnost ploskve. OP = NP + MP ; ZP = O (1) lahko sklepamo, da se ploskev telesa nahaja, znotraj oktanta (slika 6). Ploskev ne more ležati na eni Izmed ploskev oktanta, kljub temu, da lahko vsa ogllšča ploskve telesa ležijo na meji oktanta, saj bi ploskev Izločili že v drugem koraku, s testom ravnin ploskev telesa (slika 4). Ce se vsaj eno ogllžče ploskve telesa nahaja zunaj oktanta In vsaj eno ogllSče znotraj oktanta, oziroma če velja OP = NP + MP + ZP ; ZP » O , NP * O (2) ploskev telesa seka oktant, ne glede na to ali je konveksna ali konkavna In ali ima luknje ali ne (slika 7). a) OP=NP+ZP MP=0,NP*0,ZP«0 b) OP=NP+HP+ZP NPie0,MP*0,ZP='0 Slika 7 Ploskev seka oktant Ko ugotovimo, da se vsaj ena od ploskev telesa nahaja znotraj oktanta ali seka oktant. Je barva vozlišča osralškega drevesa siva ne glede na položaj ostalih ploskev telesa glede na oktant. Ce za nobeno od ploskev telesa, ki smo Jih testirali v tem koraku ne velja enačba 1 ali enačba 2. ne moremo trditi, da katera od ploskev seka oktant, ali da so vse ploskve zunaj oktanta, zato nadaljujemo s četrtim korakom, ki vključuje test presečnega mnogokotnlka. a) 0P=ZP;MP=0,NP=0 b) OP=MP+ZP NP=0,ZP»0,MP*0 Slika 8 Ploskve telesa ležijo zunaj oktanta ali sekajo oktant Cilj tega testa Je isti kot v tretjem koraku, le da je postopek ugotavljanja presečišč bolj natančen, saj moramo upoštevati, da Ima ploskev lahko luknje In nI nujno konveksna. Ta test sestoji Iz štirih korakov -testov, ki se nanašajo na posamezno ploskev. Da bi ugotovili položaj ploskve telesa, si pomagamo s presečnim mnogokotnlkon, ki ga določajo točke, v katerih ravnina ploskve telesa seka oktant. Ravnina ploskve telésa seka ravnine šestih ploskev oktanta v šestih premicah. Točke, v katerih se teh šest premic seka, določajo ogllšča presečnega mnogokotnlka, ki leži v ravnini ploskve telesa. Ploskev telesa seka oktant le takrat, ko seka presečni mnogokotnlk. V prvem koraku testiramo število ogllSč presečnega mnogokotnlka, ki Je odvisno od položaja ravnine ploskve telesa glede na oktant. Na podlagi rezultatov tega testa, Izločimo ploskve, ki ležijo zunaj oktanta. Naj je OPM število vseh ogllšč presečnega mnokotnlka. Ko Je število ogllšč presečnega mnogokotnlka manjše ali enako dva, oziroma če velja OPM 3 2 ; OPM » O (4) se ravnina ploskve telesa dotika oktanta. Ko je število ogllšč presečnega mnogokotnlka enako nič, oziroma če velja 0PM (5) leži ravnina ploskve telesa zunaj oktanta. Na podlagi tega sklepamo, da ploskev ne seka oktanta, temveč zagotovo leži zunaj oktanta (slika 9). OOPM b) OPM c) OPM = O Slika 9 Ploskev telesa leži zunaj oktanta Ko Je število oglläC presečnega mnogokotnlka većje od dva, oziroma velja. OPM > 2 (6) ravnina ploskve seka oktant in preidemo na drugI korak (slika 10). a) OPM b) OPM = 3 Slika 10 Ploskev telesa seka oktant V drugem koraku moramo določiti položaj presečnega mnogokotnlka glede na ploskev telesa. Da bi poenostavili vsebnostnl test, s katerim določamo položaj oglišč presečnega mnogokotnlka, zavrtimo ravnino, v kateri ležita ploskev In presečni mnogokotnik tako, da Je vzporedna s koordinatno ravnino XY. To opravimo tako, da zavrtimo normalni vektor ploskve telesa v koordinatno os 2 (slika 11). Slika 11 Rotacija normale ploskve telesa v koordinatno os 2 Sedaj opravimo vsebnostnl test, da ugotovimo položaj presečnega mnogokotnlka glede na ploskev telesa. Presečni mnogokotnik Je na vseh nadaljnlh slikah označen z navpično Šrafuro, ploskev telesa pa z vodoravno šrafuro. Naj bo 2PH število oglišč presečnega mnogokotnlka zunaj ploskve, MPM naj bo število oglišč na meji ploskve in NPH število oglišč znotraj ploskve telesa. Presečni mnogokotnik lahko leži: - strogo znotraj ploskve telesa, - seka ploskev telesa, - znotraj ploskve telesa, - zunaj ploskve telesa. Ce so vsa ogllšča presečnega mnogokotnlka znotraj ploskve, oziroma če velja OPM = NPM ; MPM = O, 2PM = O (7) potem Je presečni mnogokotnik strogo znotraj ploskve telesa (slika 12), vendar barve vozlišča ne moremo določiti, saj Je ta odvisna od medsebojne lege presečnega mnogokotnlka in lukenj v ploskvi. Če ploskev nima lukenj, potem ploskev seka oktant Csllka I2a) In Je barva vozlišča osmlškega drevesa siva. V primeru, ko Ima ploskev luknje (slika 12b), uporabimo test lukenj ploskve telesa in določimo položaj ploskve glede na oktant. V primeru, ko enačba 7 nI izpolnjena, preidemo na tretji korak. V tem koraku želimo ugotoviti, aH presečni mnogokotnik seka ploskev telesa. a) Ploskev nima luknje b) Ploskev z luknjo Slika 12 Presečni mnogokotnik strogo znotraj ploskve telesa Ce vsaj en rob presečnega mnogokotnlka seka kateri koli rob ploskve telesa, presečni mnogokotnik seka ploskev (slika 13), ne glede na to ali Je ploskev konkavna ali konveksna In ali ima luknje ali ne. 60 a) OPM = ZPM k; c) OPM = ZPM + NPH + MPM J b) OPM = ZPM + NPM d) OPM = ZPM + MPM Slika 13 Presečni mnogokotnlk seka ploskev telesa Ploskev telesa seka oktant, barva vozlišča osraläkega drevesa Je siva In prekinemo s testiranjem presečlSč. Ce noben rob presečnega mnogokotnlka ne seka katerega koli roba ploskve telesa, preidemo na četrti korak. V četrtem koraku ugotavljamo položaj presečnega mnogokotnlka glede na ploskev telesa na osnovi lege njegovih ogliSč. Če so vsa ogllšča presečnega mnogokotnlka na meji ploskve telesa, oziroma če velja a) OPM = MPM b) OPM = ZPM ♦ MPM C) OPM = ZPM Slika 15 Presečni mnogokotnlk zunaj ploskve telesa Ce Je vsaj eno ogllSče presečnega mnogokotnlka znotraj ploskve, oziroma če velja OPM = NPM + MPM : ZPM = O, NPH * O (9) leži presečni mnogokotnlk znotraj ploskve In ploskev seka oktant (slika 14b,c). Barva presečišča, oziroma vozlišča osmlSkega drevesa Je siva In prekinemo s testiranjem presečišč. Ce Je vsaj eno oglišče presečnega mnogokotnlka zunaj ploskve telesa.■ozi roma če velja OPM = MPM i NPM = O, ZPM = O (8) OPM = ZPM + MPM ; ZPM » O, NPM (10) Je rezultat testa odvisen od lege središčne točke presečnega mnogokotnlka (slika Ila. 15a). i i a) OPM = MPM b) OPM = MPM + NPM c) OPM = MPM ■>■ NPM Slika 14 Presečni mnogokotnlk znotraj ploskve telesa Ce središčna točka presečnega mnogokotnlka leži znotraj ploskve telesa, leži tudi presečni mnogokotnlk znotraj ploskve in ploskev seka oktant (slika 14a). Barva presečišča Je siva in prekinemo s testiranjem presečišč. Ce leži središčna točka presečnega mnogokotnlka zunaj ploskve, leži tudi presečni mnogokotnlk zunaj ploskve telesa in ploskev ne seka oktanta (slika ISa). leži presečni mnogokotnlk zunaj ploskve (slika 15b,c) In ploskev ne seka oktanta. Rezultat testa presečnega mnogokotnlka nam vrne barvo presečišča oziroma vozlišča osmlSkega drevesa, če vsaj ena ploskev telesa seka oktant. V primeru, ko nismo dobili barve presečišča, so vse ploskve, ki smo Jih testirali v tem koraku, zunaj oktanta (slika 16) in oktant lahko leži znotraj telesa, ali zunaj telesa. a) Oktant Je zunaj telesa b) Oktant Je znotraj telesa Slika 16 Medsebojna lega telesa In oktanta Uporabimo vsebnostnl test ogllšč oktanta v telesu, da bi ugotovili, katera od trditev Je pravilna. Nato skladno s tehniko označevanja predpišemo vozlišču osmlškega drevesa črno ali belo barvo. 3.5 Test lukenj ploskve telesa Presečni «nogokotnlk Je strogo znotraj ploskve, ko velja enačba 7. Samo v tem primeru lahko luknja ploskve prekriva presečni mnogokotnlk tsllka 12b) In ploskev ne seka oktanta. Luknja v ploskvi se ne more dotikati roba ploskve niti sekati ploskve, zato v primerih, ko enačba 7 ne velja, presečni mnogokotnlk ne more biti v celoti prekrit z luknjo (slike 13, 14, 15). Ploskev ima lahko več lukenj (slika 17), zato test ponavljamo za vsako luknjo v ploskvi, dokler ne določimo barve presečišča. Slika 17 Ploskev telesa z luknjami In lega presečnega mnogokotnika Ugotoviti moramo ali luknja v celoti prekriva presečni mnogokotnlk. saj v vseh ostalih primerih ploskev vsaj delno prekriva presečni mnogokotnlk, kar pomeni, da ploskev seka oktant. Presečni mnogokotnlk lahko: - seka luknjo, - leži znotraj luknje, - prekriva luknjo, - leži strogo zunaj luknje. Slika 18 Presečni mnogokotnlk seka luknjo ploskve oziroma, ali leži presečni mnogokotnlk v celoti znotraj luknje ploskve. V tem primeru ploskev ne seka oktanta, ne glede na ostale luknje ploskve in lahko zaključimo s testiranjem. Ce omejitveni pravokotnik presečnega mnogokotnika omejuje omejitveni pravokotnik luknje ploskve, ugotavljamo vsebnost luknje ploskve v presečnem mnogokotniku, drugače pa ugotavljamo vsebnost presečnega mnogokotnika znotraj luknje ploskve. Ta vsebnostni lest Je enak v obeh primerih, zato ga lahko posplošimo na ugotavljanje vsebnosti mnogokotnika Ml v mnogokotniku M2. Naj bo OHI število ogllšč mnogokotnika Ml In 0M2 število ogllšč mnogokotnika M2. Število ogllšč mnogokotnika Ml zunaj mnogokotnika M2 označimo z ZMl, število ogllšč Ml znotraj M2 označimo z NMl, število ogllšč. ki ležijo v ogliščlh H2 označimo z VMl in število ogllšč. ki ležijo na robovih M2 označimo z RNl. Če vsa ogllšča Ml ležijo v ogliščlh M2, oziroma če velja OMl = VMl ; RMl = O, ZMl = O, NMl In OMl = 0M2 (11) (12) Določanje medsebojne lege luknje ploskve in presečnega mnogokotnika poteka v treh korakih. V prvem koraku uporabimo test minimax, s katerim določimo prekrivanje omejitvenih pravokotnlkov presečnega mnogokotnika in luknje ploskve. Ce se omejitvena pravokotnlka ne prekrivata, nadaljujemo z naslednjo luknjo ploskve. Ce za vse luknje ploskve velja, da se njihovi omejitveni pravokotnlkl ne prekrivajo z omejitvenim pravokotnlkom presečnega mnogokotnika, potem presečni mnogokotnlk seka, oziroma leži na ploskvi telesa in ta seka oktant. Ce se omejitvena pravokotnlka luknje ploskve in presečnega mnogokotnika prekrivata, preidemo na naslednji korak. V drugem koraku preverjamo, ali kateri od robov presečnega mnogokotnika seka kateri koli rob luknje ploskve. Ce Je test pritrdilen, leži presečni mnogokotnlk delno na ploskvi telesa in ploskev seka oktant ne glede na to, ali Ima ploskev še kakšno luknjo in kje na ploskvi se ta luknja nahaja (slika 18). Zato lahko v tem primeru zaključimo s testom lukenj ploskve. Ce Je test sekanja robov negativen, nadaljujemo s tretjim korakom. V tretjem koraku želimo ugotoviti, ali luknja ploskve popolnoma prekriva presečni mnogokotnlk sta mnogokotnika enaka In se popolnoma prekrivata. V tem primeru leži presečni mnogokotnlk v celoti znotraj luknje ploskve, ne glede na to kateri mnogokotnlk označuje presečni mnogokotnlk in kateri luknjo ploskve (slika 19). Ploskev telesa ne seka oktanta in prekinemo s testiranjem. Slika 19 Mnogokotnika se popolnoma prekrivata Ce vsa ogllšča mnogokotnika Ml ležijo v ogliščlh M2 In na robovih M2, oziroma če velja OMl = VMl + RMl -, ZMl = O, NMl (13) Je mnogokotnlk Ml lahko zunaj aH znotraj mnogokotnika M2. Uporabimo vsebnostni test središčne točke mnogokotnika Ml v mnogokotniku M2, da ugotovimo, katera trditev Je pravilna. a) Presečni mnogokotnik znotraj luknje b) PreseCni mnogokotnik zunaj luknje Slika 20 Ml presečni mnogokotnik, M2 luknja ploskve V primeru, ko Ml označuje presečni nnogokotnlk In M2 luknjo ploskve (slika 20), Imamo naslednjo reällev: Ce presečni mnogokotnik leži znotraj luknje (slika 20a). ploskev ne seka oktanta. Ce leži presečni mnogokotnik zunaj luknje ploskve, ploskev seka oktant (slika 20b). Slika 21 Ml luknja ploskve, M2 presečni mnogokotnik V primeru, ko Ml označuje luknjo ploskve In M2 presečni mnogokotnik. Je reSltev naslednja: luknja ploskve lahko leži le znotraj presečnega mnogokotnlka, ker Je oblika presečnega mnogbkotnlka omejena. Zato presečni mnogokotnik leži delno na ploskvi telesa in ta seka oktant (slika 21). Ce vsaj eno ogllSče mnogokotnlka Ml leži znotraj mnogokotnlka M2, oziroma če velja OMl = NMl + RHl + VMl ; NMl * O, ZMl (14) leži mnogokotnik Ml znotraj mnogokotnlka M2. Ce leži presečni mnogokotnik (Ml ) znotraj luknje ploskve (M2), luknja ploskve prekriva presečni mnogokotnik in ploskev ne seka oktanta (slika 22). Ce leži luknja ploskve (Ml) znotraj presečnega mnogokotnlka (M2), leži presečni mnogokotnik delno na ploskvi telesa In ploskev seka oktant (slika 23). a) RMl * O, VMl » O ■b) RMl = O, VMl = O Slika 22 Presečni mnogokotnik (Ml) znotraj luknje ploskve (M2) Ce vsaj eno ogliSče mnogokotnlka Ml leži zunaj mnogokotnlka M2, oziroma če velja a) RMl » O, VMl « O b) RMl = O, VMl Slika 23 Luknja ploskve (Ml) znotraj presečnega mnogokotnlka (M2) In RMl « O all VMl * O (16) leži mnogokotnik Ml zunaj mnogokotnlka M2 In mnogokotnlka se dotikata. V tem primeru, ne glede na to, kateri mnogokotnik določa luknjo ploskve In kateri presečni mnogokotnik, ugotovimo, da presečni mnogokotnik leži zunaj luknje ploskve, vendar ga nobena druga luknja ploskve ne more popolnoma prekrivati. Ploskev seka oktant in prekinemo s testiranjem lukenj (slika 24). a) Presečni mnogokotnik (Ml) b) Luknja ploskve (Ml) luknja ploskve (M2) presečni mnogokotnik (M2) Slika 24 Mnogokotnik Ml zunaj mnogokotnlka M2 Če vsa ogllSča mnogokotnlka Ml ležijo zunaj mnogokotnlka M2 oziroma, če velja OMl = 2M1 ; VMl = O, RMl = O, NMl = O (17) leži mnogokotnik Ml strogo zunaj mnogokotnlka M2 (slika 25). Ne glede na to, kateri mnogokotnik označuje presečni mnogokotnik In kateri luknjo ploskve, leži presečni mnogokotnik strogo zunaj luknje ploskve, kar pomeni, da lahko ostale luknje ploskve vplivajo na rešitev. Ce ploskev nima več lukenj oziroma, če smo obdelali vse luknje ploskve, ploskev seka oktant, drugače pa ponovimo test lukenj za naslednjo luknjo ploskve. a) Presečni mnogokotnik Ml luknja ploskve M2 b) Luknja ploskve HI presečni mnogokotnik M2 OMl = ZMl + RMl + VMl ; ZMl » O, NMl = O ' (15) Slika 25 Mnogokotnik Ml strogo zunaj mnogokotnlka M2 4 Zaključek 5 Literatura Testiranje presečišč med elementi telesa In osmläkega drevesa Je časovno In prostorsko zelo zahtevno. Ta zahtevnost Je odvisna predvsem od oblike telesa oziroma od števila vozlišč v osmlškem drevesu In od morebitne konkavnosti In luknjavostl telesa. Naše nadaljnje raziskovalno delo bo temeljilo na Izboljšanju, oziroma optimiranju algoritma, kot tudi na realizaciji algoritma za pretvorbo Iz predstavitve z osmlSklm drevesom v predstavitev z ovojnico. Program Je napisan v pascalu in vključen v Eksperimentalni geometrijski modellrnik teles (EGM) :ŽALI89bl. Razvili smo ga na računalniku VAX-8800, za vlzualizacljo pa smo uporabili grafični terminal TEK 4207. Rezultati programa so predstavljeni na slikah 26 in 27, kjer smo telesa prikazali z žičnim modelom. Za prikaz telesa in osmiškega drevesa z odstranjenimi zakritimi robovi smo uporabili razširjen Robertsov algoritem za odstranjevanje zakritih robov in ploskev ((Š0B0881, (Š0B089I). [CHIY85) Chiyokura, H., F. Klmura, "A Method of Representing the Solid Design Process", IEEE CG&A, Vol. 5. No. 4, 1985, pp. 32 - 41. ICHIY87) Chiyokura, H. , "An Extended Rounding Operation for Modeling Solids with Free-Form Surfaces", IEEE CG&A, Vol. 7, No. 12, 1987, pp. 27 - 36. (CLIF87] Clifford, A. S. and H. Samet, "Optimal Quadtree Construction Algorithms", Computer Vision, Graphics, and Image Processing, Vol. 37, No. 3, March 1987, pp. 402 - 419. (GUID881 Guld, N., ."Računalniška grafika" Tehniška fakulteta Maribor. Maribor 1988. [HILL821 Hillyard. R., "The Build Group of Solid Modelers". IEEE CG&A. Vol. 2. Ho. 2, 1982, pp. 43 - 52. [H0HE88] Homer. H. C. and T. S. Huang. "A Survey of Construction and Manipulation of Octree". Computer Vision. Graphics, and Image Processing, Vol.43. No.3, September 1988, pp. 409 - 431. Slika 27 Primer konkavnega telesa (KAUF88) Kaufman, A. and R. Bakalash, "Memory and Processing Architecture for 3D Voxel - Based Imagery", IEEE CG&A, Vol. 8. No. 6. 1988, pp. 10 - 23. 1MÄNT821 Mäntylä, M. and R. Sulonen, "GWB: A Solid Modeler with Euler Operators", IEEE CG&A Vol. 2, No. 7, 1982, pp. 17 - 31. [MÄNT83] Mäntylä. M.. "SET operations of GWB". Graphics Forum, No. 2-3, 1983, pp. 122 -134. (MÄNT881 Mäntylä, M.. "An Introduction to Solid Modeling", Computer Science Press, Rockvllle, MD (1988). Slika 26 Primer telesa z luknjo (MILLB91 Miller, R. J., "Architectural Issues in Solid Modelers", IEEE CG&A, Vol. 9, No. 5, 1989. pp. 72 - 87. [M0RT85] Mortenson, M. E. . "Geometric Modeling", John Wiley & Sons. New York, 1985. (PRAT831 Pratt. M. J.. "Interactive geometric modelling for CAD/CAU", Eurographics "83 Tuturlals, Zagreb, 1983. IREQU82] Requlcha, A. A. C., "Solid Modeling: A Historical Summary and Contemporary Assessment". IEEE CG&A, Vol. 2. No. 2. 1982, pp. 9 - 24. (REQU831 Requlcha, A. A. G, and H. B. Völcker, "Solid Modeling; Current Status and Research Directions", IEEE CG&A, Vol. 3, No. 5, 1983, pp. 25 - 37. (S0B0881 Sobot, P.. B. 2allk, N. Guld, "Extended Robert's hidden line / hidden surface algorithm for computer graphics", X. international Symposium Computer at the University, Cavtat 1988, pp. 7.5/1-4. IS0B0891 Sobot, P., B. Žallk, N. Guld, "Analiza in uporaba razširjenega Robertsovega algoritma, kl reSuJe problem zakritih robov pri mnogokotniških pravilnih telesih", XIII. Simpozljura o informaclonlm tehnologijama, Sarajevo 1989, pp. 227/1-10. IWEIL851 Weller, K., "Edge-Based Data Structures for Solid Modeling in Curved-Surface Envlronmenst", IEEE CG&A, Vol. 5, No. 1, 1985, pp. 21 - 40. (WILS8S) Wilson, P. R., "Euler Formulas and Geometric . Modeling", IEEE CG&A, Vol. 5, No. 8, August 1985, pp. 24 - 36. [ŽALI89a) 2allk, B., N. Guld, and P. Sobot, "Experimental geometric modeler based on boundary representation", XI. International Symposium Computer at the University, Cavtat 1989, pp. 7.6/1-6. IŽALI89.bl 2alik, B.. "Geometrijski modelirnik z EulerJevlmi operatorji". Magistrsko delo, Tehnižka fakulteta, VTO ERI, Maribor, 1990. IŽAL190] Žallk, B., N. Guld. "Vgradnja EulerJevih operatorjev in njihova uporaba pri tvorbi teles s translaciJskira pomikanjem", Informatica, Ljubljana. Vol. 14. No. 2. 1990. pp. 32 - 38. Knjiga Antona P. Železnikarja On the Way to Information (Na poti k informaciji) (recenziji na strani 79 in 80) odpira izvirne poglede in možnosti razvoja • teorije informacije, umetne inteligence in nove poglede na področje informacije. Profesor Branko Souček in doc. dr. Valter Motaln podajata svoja stališča in ocene o knigi. Knjigo lahko naročite pri Slovenskem društvu Informatika, po telefonu (061) 214 455ali na naslov Tržaška c. 2, Ljubljana. s plačilom din 270. RAČUNALNIŠKI PODPROGRAMI ZA RAČUNANJE LASTNIH VREDNOSTI IN LASTNIH VEKTORJEV Key.words: principal components analysis, eigenvalues, eigenvectors, diagonalization method, subroutine Vesna Čančer Ekonomsko-poslovna fakulteta v Mariboru Razlagova 14, 62000 Maribor v članku obravnavamo računalniške podprograme za računanje lastnih vrednosti In lastnih vektorjev simetrične korelacijske matrike, ki Jih potrebujemo pri analizi slavnih komponent. V nJem Je uporabljena modifikacija JacoblJevega postopka. Imenovana "Pope In Tompkins", kl Je primerna za računalniško programiranje. Čeprav se uporabljajo hitrejše metode s tridlagonallzlrano korelacljsko matriko, so JacoblJeva metoda Se pojavlja v sodobnih podprogramskih paketih, saj omogoča natančne izračune lastnih vrednosti In nJim pripadajočih lastnih vektorjev. Delovanje podprograma smo ponazorili s primerom In Izpisali konCnl rezultat. ABSTRACT The following paper deals with the for tran computer subroutines for computing eigenvalues and eigenvectors of a real symmetric matrix, which are necessary for the principal components analysis. Because of Its convenience for computer programming, diagonalization method originated by Jacobi and modified by the Iterative "Pope and Tompkins" technique is used. In spite of some quicker methods, based on the threedlagonallzatlon matrix, Jacobi "s method still appears in the modern subroutine packages because It provides precise definitions of eigenvalues and associated eigenvectors. A numeric example illustrating the application of the described procedure and given computer subroutine Is presented. 1. UVOD Analiza glavnih komponent Je statisticn.) tehnika, s katero n statističnih znakov , ..., X linearno in ortogonalno nadomestimo z n enakim številom nekoreliranlh glavnih komponent y , y..... y [3], [81. Transformacija temelji 12 n na Iskanju lastnih vrednosti in lastnih vektorjev kovarlanCne matrike ali, kot v našem primeru, korelacijske matrike A, ki Je kovarlanCna matrika standardiziranih spremenljivk , ..., l^J , [4], [6]. Vzemimo n-razsezni vektoi- z elementi r . r , l 2 . . . , r in poskušajmo resiti matrično enačbo l n =1 2n X Ct.l> kjer Je A matrika korelacijskih koeficientov In K poljubno Število [8]. To enačbo Je mogoCe zapisati v obliki sistema n linearnih enacb, ki Jih uredimo tako, da vse Člene z ne7.n.3nkaml r^, r^, ..., r^ prenesemo na levo stran. Dobimo homogen sistem enacb; desne strani vseh enacb so namreC enake nlc [8], [iO]- Tak trivialno sistem Ima pri poljubni vrednosti \ rešitev O. Netrivlalna rešitev . ekslstlra kvečjemu tedaj, kadar 66 determinanta koeficientov A >• O [10], Ce za X vzamemo tako vrednost, da enacbe tvorijo odvisen sistem, dobimo neskončno mnogo reSltev. Sistem homogenih enačb Je torej determinanta sistema enaka nlc: odvisen, ce 1 2 = o a.2> To Je karakteristična enačba korelacljske matrike, ki Jo lahko zapišemo v obliki algebrajske enačbe n-te stopnje [8], ReSitve karakteristične enacbe <1.25 K^, ..., imenujemo lastne vrednosti korelacljske matrike. Predpostavimo, da so lastne vrednosti realne in različne. Uredimo Jih po velikosti: X \ > ... > X . 2 r, C1.3> Vsaki lastni vrednosti X , 1 » 1, 2, ..., n, v pripada lastni vektor r^, ki je rešitev matrične enačbe: A r " X r.. v v v. Lastnosti lastnih vrednosti in lastnih vektorjev korelacljske matrike so podrobneje opisane npr. v [3]. [4], [8] in [10]. S podprogramom EIGEN [5] se računajo lastne vrednosti In lastni vektorji simetrične korelacljske matrike, katere elementi so v podprogramu urejeni v vektor, označen s formalno spremenljivko A. V tej spremenljivki se izračunajo tudi lastne vrednosti. Tvori se matrika Lastnih vektorjev, katere elementi so v podprogramu urejeni v vektorju R. 2. OSNOVE UPORABLJENE METODE Uporabljena je za računalniško programiranje primerna modifikacija JacobiJeve metode za določanje lastnih vrednosti, t. j. algoritem Pope in Tompkins [4], ki ga Je za računalnike priredil von Neumann. Bistvo Jacobijevega postopka za ugotavljanje lastnih vrednosti je, da se z zaporedjem ortogonalnih transformaci J korelacijska matrika pretvori v diagonalno matriko lastnih vrednosti: a R' A R tli = R' A R 2 2 12 A = R'A R = A, g 9 9-1 g kjer Je A simetrična korelacijska matrika, R transformacijska matrika ortogonalnih transformacij in A diagonalna matrika lastnih vrednosti. Z vsako ortogonalno transformacijo lahko en nediagonalni element reduciramo na nlc. Proces se prične z redukcijo največjega nediagonalnega elementa, nato se reducira drugi največji nediagonalni element itd., dokler niso vsi nediagonalni elementi reducirani na nlc. V vsakem zaporedju moramo poznati elementarno transformacijsko matriko, s katero bomo izbrani element v matriki reducirali na nlc [10], [11]: cos © -sin G O sin S O cos 0 O O 1 <2.1 > Kot S, za katerega moramo matriko A, da bo element a^^ z Izrazom; zarotlrati korelacijsko postal nlc, Je podan tang 2 0" -2 a, / Ortogonalna transformacije je z geometričnega vidika podorobneje razložena v [3], [4], [10] in [11]; v članku navajamo le kljucne enacbe, ki so uporabljene v podprogramu EIGEN [3]. Kot 0 Je določen s predmultipllkaci jo in postmultlpllkaci jo matrike A s transformacijsko matriko R in pogojem, da mora biti rezultat taksne multiplikacije nlc: sin © cos © + a, Ccos®© - sin^©> «O. Ll mm Lm <2.3) Upoštevajmo vrednosti za sin 2 © In cos 2 ©: > sin 2 © + a, cos 2 © - O, <2.4> 1/2 - lm iz cesar sledi: -2 a. > " sin 2 e/cos 2 © ■ tang 2 ©. <2.S> Nato Iz izraza za tangens dobimo vrednosti sin © in cos ©, t.j. elemente transformacijske matrike R. Bistvena razlika med izvirno Jacobijevo metodo in algoritmom Pope in Tompkins je v tem, da se z nJim na nlc ne reducira le en element, pac pa se z določitvijo minimalne meje tolerance zaporedno eliminirajo vsi nediagonalni elementi, ki so vecjl od te meje. Nato se določi nova minimalna meja tolerance, ki Je nižja od prejšnje meje. Proces se nadaljuje vse do konCne meje tolerance napake za l.-istne vrednosti. Algoritem tvori osem korakov; V 1. koraku poiSCemo vsote kvadratov vseh nediagonalnlh elementov korelacljske matrike in kvadratni koren te vsote, t. J. zaCetno normo £2 a iSk ki ji Je v podprogramu spremenljivka ANORM. V 2. koraku določimo koncno napake za lastne vrednosti: prirejena C2.Ó) formalna mejo tolerance 10 C2.7> r.^^ = B C2.17> kjer Je N rang korelacljske matrike. V podprogramu Je tej meji prirejena formalna spremenljivka ANRMX. V 3. koraku tvorimo enotsko transformacijsko matriko R. V 4. koraku določimo začetno minimalno mejo tolerance, tako da bodo vsi nediagonalni elementi, vecjl od te meje, rotirani na nie. V podprogramu Ji Je prirejena formalna spremenljivka THR. V 5. koraku Iscemo nedlagonalne elemente, ki so po absolutni vrednosti veCji od minimalne meje tolerance. Iskanje lahko omejimo na desno od glavne diagonale, ker Je korelacljska matrika simetrična glede na glavno diagonalo. Vsak tak element Je zreduciran na nie. Iskanje in reduciranje nadaljujemo, dokler vsi elementi, ki niso na diagonali, niso manJsl ali enaki dani meji. Tedaj definiramo novo minimalno mejo tolerance in nadaljujemo opisani postopek, dokler ne dosežemo konCne meje tolerance. V 6. koraku določimo elemente zaporedne transformacijske matrike A po vsaki Iteraci Ji; v tej matriki se izračunajo tudi lastne vrednosti korelacljsko matrike. V 7. koraku z ortogonalno transformacijo zajamemo tudi enotsko transformacijsko matriko R; v tej matriki se izračunajo tudi lastni vektorji korelacljske matrike. V 8. koraku ugotavljamo lastne vektorje korelacljske matrike; lastne vrednosti in nJim pripadajoče lastne vektorje uredimo po velikosti lastnih vrednosti. V zbirki podprogramov IBM Corporation [3] so S., 6. In 7. korak opisanega algoritma zaradi lažjega razumevanja podprograma EIGEN strnjeni v enačbe, ki Jih bomo uporabili pri razlagi delovanja obravnavanega podprograma: M = 1/2 Ca - a > l l mm (O = sign <(j) t2.8> C2.10> sin © (x> <2. 11 > -/C2C1 + Vci - cos © = /ci - sin"©? C2. 12> B " a. 1. cos 0 - a. v m sin © C2. 13> C = a i 1 sin © + a, ■ L m cos 9 <2 . 14> B » r 1 cos © - r t m sin © C2. . 1S> r i m = r © + r. L T cos © n C2. . 16i cos^e + a sin^S - 2a. sin Q cos © C2.18> a " a, , sin^© + a cos^© + 2a. sin © cos mm im mm I I a, " sin © cos (5>, + lm II mm * a , Ccos^© - sln^©> l tn C2.19> <2.20> 3. OPIS DELOVANJA PODPROGRAMA EIGEN S PRIMEROM V glavnem programu [2] kličemo podprogi-aim EIGEN z ukazom CALL, s katerim se dejeu^ki parametri Iz glavnega programa priredijo formalnim parametrom v podprogramu: f ormalni earantel rv podprog. pomen A vhodna simetrična korelacljska matri- ka, urejena kot vektor, ki se med računanjem v podprogramu unici; Izhodni vektor lastnih vrednosti, ki so elementi matrike lastnih vrednosti R izhodna matrika lastnih vektorjev, urejena kot vektor N rang matrik A in R, enak redu teh ma- trik zaradi neodvisnosti statističnih znakov MV vhodna spremenljivka za EIGEN, ki Ji priredimo vrednost z ukazom DATA v glavnem programu in Je lahko O za računanje laistnih vrednosti in vektorjev ali _1 za računanje zgolj lastnih vrednosti V glavnem programu smo spremenljivki MV priredili vrednost O. V EIGEN-u niso potrebni drugI podprogrami ali funkcijski podprogrami. Za ponazoritev delovanja podprograma bomo navedli. vmesne in Izpisali končne rezultate. Za lazje razumevanje uporabljenega algoritma izplsimo podprogram EIGEN [S]. SUBROUTINE EIGEN(A,R,N,MV) DIMENSION A<1),R(1> C TVORJENJE ENOTSKE MATftiKE 5 RANGE=1.0E-6 IF(MV-l) 10,25,10 10 IQ=-N DO 20 J=1,N IQ=IQ+N DO 20 1=1,N IJ=IQ+I R(IJ)=0.0 IF(I-J) 20,15,20 15 B(IJ)=1.0 20 CONTINUE C RAČUNANJE ZAČETNE IN KONCNE NORME ( ANORM IN C ANRMX; 25 ANORM=0.0 DO 35 I-1,N DO 35 J=I,N IF(I-J) 30,35,30 30 IA=I+(J*J-J)/2 ANORM=ANORM+A(IA)*A(IA) 35 CONTINUE IF(ANORM) 165,165,40 40 AN0RM=1.414*SQRT 135,140,135 135 M=M+1 GO TO 60 C TEST, DA JE L PREDZADNJI STOLPEC 140 IF(L-(N-1)) 145,150,145 145 L=L+1 GO TO 55 150 IF(IND-l) 160,155,160 155 IND=0 GO TO 50 C PRIMERJANJE INPUTA S KONČNO NORMO 160 IF(THR-ANRHX) 165,165,45 C SORTIRANJE LASTNIH VREDNOSTI IN LASTNIH VEKTOF 165 IQ=-N DO 185 1=1,N I9=IQ+N LL=I+(I*I-I)/2 JQ=N*(I-2) DO 185 J=I,N JQ=JQ+N MM=J+(J»J-J)/2 IF(A(LL)-A(MM)) 170,185,185 170 X=A(LL) A(LL)=A(MM) A 1.000 0.887 -0.125 0.887 1.000 0.307 -0.123 0.307 1.000 C3.1> se v podprogramu CIOEN priredi kot vektor v formalni spremenljivki A z naslednjim zaporedjem elementov: 1., 0.887, 1., -0.125, 0.307, 1., torej Je njihovo Število N«, katere elementi so urejeni v vektor RCIJ>. Izvede se 3. korak algoritma Pope In Tompkins. Z ukazi 23 do 40 se tvori zaCetna norma ANORM <.2.6>. Izvede se 1. korak algoritma Pope In Tompkins. V nasem primeru Je zaCetna norma 1.3389340. V ukazu 40+1 se tvori konCna meja tolerance napake za lastne vrednosti oz. konCna norma ANRMX C2.7>. Izvaja se torej 2. korak obravnavanega algoritma. V naSem primeru Je končna norma U.ÜÜU0004. Z ukazi 43-2 do 33 poteka Inlclallzacija Indikatorjev IND in določanje začetne minimalne meje tolerance, kar sodi v 4. korak v algoritmu Pope In Tompkins. V nasem primeru se Je Izračunalo 14 minimalnih mej tolerance THR; prva Je bila 0.4463114, zadnja pa 0.0000003. Z ukazi od 60 do 78+2 se računajo sinusi In koslnusl, nato pa se do 130-1 zamenjujejo L in M stolpci. V vsaki Iteracljl se , namreč selekcionirajo nedlagonalni element-l. To sodi v S., 6. In 7. korak obravnavanega algoritma. Iz ukaza 62 je razvidno: Ce Je nedlagonalni element korelacljske matrike po absolutni vrednosti manJsl od prej določene minimalne meje tolerance THR, ni reduciran na niC; Ce so nedlagonalni elementi po absolutni vrednosti enaki ali vecji od prej določene minimalne meje tolerance, pa se začne reduciranje tega elementa na niC. V našem primeru Je v prvi iteraci Ji AC2>, ki Je 0.887, vecjl od THR, ki Je 0.446, zato sledi reduciranje AC2> na nie. V ukazu 68-1 se izračuna X po C2.9>. X predstavlja del izraza <2.4>. V ukazu 68 se po <2.105, v katerem nastopa <2.8>, izračuna Y, ki je potreben pri računanju vrednosti elementov transformacijske matrike R in A: sin © In cos ©. V ukazu 75 se po <2.11) Izračuna element transformacijske matrike R sin © In se zapomni v formadni spremenljivki SINX. V naslednjem ukazu se izračuna sin®© In se zapomni v formalni spremenljivki SINX2. V ukazu 78 se po <2.12> Izračuna cos © In se zapomni v COSX. V naslednjih dveh ukazih se izračunata Se cos^© in sinOcosS in se zapomnita v spremenljivkah COSX2 in SINCS. V 6. koraku se določijo elementi zaporednih transformacijskih matrik po vsaki iteraci Ji. V ukazu 110 se izračuna X po <2.13>. V naslednjem ukazu se izračuna A po <2.14>. Nato se A priredi X. Ce se računajo le lastne vrednosti, se 7. korak algoritma preskoci, sicer pa se na ukazu 120 prične 7. korak v algoritmu Pope in Tompkins, v katerem Jo z ortogonalno transformacljo zajeta tudi transformacijska matrika R, ki • Je v podprogramu urejena v vektor. V ukazu 120+2 se po <2.13) izračuna X. V naslednjem ukazu se po <2.16> izračuna R in nato po <2.17) Se R. G. Goos ft J. Hartmanls, Sprlnger- -Verlag 1983. 2. CANCER, Vesna: Analiza statističnega vzorca po glavnih komponentah. CDiplomsko delo) EPF, Marlbor 1990. 3. DUNTEMAN, H. George: Principal Components Ana- lysis. Sage Publications, Newbury Park 1989. 4. FULGOSI, Ante: Faktorska anaUza. Školska knji- ga, Zagreb 1984. 5. IBM Corporation: Scientific Subroutine Package GH20-0252~4. IBM 1968. tì. JAMNIK, Rajko: Uvod v matematično statistiko. DMFA Slovenije, Ljubljana 1976. 7. KAVKLER, Ivan: Teoretične osnove In primeri uporabe faktorske analize. CMaglstrsko delo> SveuclllSte u Zagrebu, Zagreb 197S. 8. MESKO, Ivan: Izbrana poglavja iz kvantitativne analize. VEKS, Maribor 1978. 9. Statistički godišnjak Jugoslavije 1990. Savezni zavod za statistiku, Beograd 1990. 10. VIDAV, Ivan: VlSja matematika I. DZS, Ljublja- na 1973. 11. VIDAV, Ivan: VlSja matematika II. DZS, Ljubljana 1975. Novice in zanimivosti o elektronskih slovarjih Longman Dictionaries Najuglednejša založniška hiša angleških slovarjev Longman Dictionaries (Burnt Mill, Harlow, Essex CM20 2JE, UK), kije izdala svoj prvi angleški slovar leta 1755, razpolaga z največjim korpusom angleških besed (30 milijonov). Leta 1974 je začela razvijati računalniški sistem za izdajanje angleških slovarjev v angleščini (materinem jeziku), in sicer za poučevanje (English Language Teaching, kratko ELT) in splošno uporabo. Longmanovi leksikografi razpolagajo z vrsto orodij, kot so avtomatična križna referenca, definiranje slovarskega preizkušanja, validacija zadevnega področja in izboljšana kontrola dolžine slovarja z možnostjo spremembe načrta v zelo pozni fazi produkcijskega procesa. Načelo Longmanove definicije slovarjev za ELT je omejenost slovarja na 2000 besed, ki naj bi jih obvladali študenti (dijaki) z dovolj dobrim znanjem angleškega jezika. Avtomatsko preizkušanje vseh definicij, ki odstopajo od definicij slovarja z 2000 besedami, je tako eden glavnih pripomočkov Longmanovih leksikografov. Leta 1979 je Longman začel distribuirati trakove za svoje ELT slovarje, hkrati pa je postal Longmanov slovar sodobnega angleškega jezika (Longman Dictionary of Contemporary English, kratko LDOCE) dosegljiv tudi za lingvistične raziskave na univerzah, inštitutih in v komercialnih podjetjih, in sicer zlasti na področju gramatičnih kodov in njihovih povezav v različne gramatične sisteme, npr. v GPSG (Cambridge Computer Laboratory). Longman je danes vodilni dobavitelj slovarjev (in tezavrov) na področju raziskav. S posebnimi kodi v posameznih poljih se omejuje subjekmo polje, regija, čas ali register (avtorja Kate in Fodor). Te kode uporabljajo leksikografi pri sistematičnemu določanju individualnih pomenov. Obstaja dogovor za fino semantično analizo z zadostno natančnostjo in prečiščenostjo pomenov aidi za tuje učence angleškega jezika. Prvi veliki angleški slovar Samuela Johnsona je izšel leta 1755. Johnsonov leksikografski princip je pri Longmanu v veljavi še danes. Leksikografe informirata dve računalniški podatkovni bazi, ko se odločajo za uvrščanje posameznih besed v posamezne slovarje, za obliko definicij in oblikovanje primerov (npr. upoštevanje neologiz-mov). Tako se jezik razvija na leksikalni ravni. T.i. Longman Lancaster English Language Corpus vsebuje 30 milijonov britanskih, ameriških, avstralskih in drugih variant angleščine in predstavlja bazo angleškega jezika v 20. stoletju. Glavna principa Longmanovega korpusa sta zadevno polje in besedilne značilnosti: čas (kateri del 20. stoletja), raven (literarna/tehnična, srednja/laična ali popularna), medij (knjige, periodika ali kratkotrajni neobjavljeni materiali) in regija (ZDA, Britanija, Avstralija itd.). 40% korpusa je namenjega fikciji (imaginativ-nemu), ostalo pa je kategorizirano kot informativno. V korpusu se zrcali vplivnost tekstov, inovativnost avtorjev, pomembnost itd. z upoštevanjem selekcijskih kriterijev. V tem smislu je korpus deljen na dva enaka dela s po 15 milijoni besed. Prva polovica upošteva pred izbrana besedila (selektivna polovica), druga polovica pa tekste, identificirane naključno iz seznamov objavljenih materialov (mikrokozmična polovica). Za majhno članarinoje celoten korpus razpoložljiv v ASCII obliki za akademsko skupnost. Z različnimi zahtevami je mogoče iz celotnega korpusa oblikovati delne korpuse, npr. po razdobjih, v določeni regiji, za področje imaginativnega itd. Korpus je razdeljen na dokumente z naslovi in besedili. V naslovnem delu se nahajajo bibliografski podatki, kot so avtor, datum, klasifikacijska informacija (regija, vsebina, čas, raven, medij in spol). Besedilni del je izpisan z ASCII znaki (1127) in z razširjenimi ASCII znaki (naglasi, denarni simboli in nelatinični znaki). Longmanov semantični kodirni sistem ima tri dele: izbira omejitev (omejitev na subjekte glagolov in pridevnikov in na prve ali druge objekte glagolov), semantične značilnosti (stopnja, funkcija, način, intencija itd.) in sociolingvistične značilnosti (register, intencija, uporabniška skupina, itd.). Leksikograf analizira vsako definicijo s posebnim menijem (računalniška podpora) in izbere značilnosti z uporabo posebnega okenskega menija. LDOCE definicijski slovar deluje v Prologu in Lispu in je primeren za posebne raziskave. Leksikografe zanima zlasti vedenje besed, gramatični vzorci, kolokacije (kontekst) in idiomi skozi avtentično evidenco govorice. Longman razvija mdi govorjeno komponento kot del korpusa (konkordance v ortografiji, neprosodična notacija). Longman Pronunciation Dictionary (J. Wells) s 75000 besedami britanske in ameriške izgovaijave je izšel v letu 1990. Longmanov korpus in dostopi v bazo so na razpolago raziskovalnim organizacijam, ki morajo imeti status popolne nekomercialnosti (ne smejo ustvarjati dohodka z nobeno komercialno dejavnostjo). Večina univerzitetnih ustanov ne izpolnjuje tega pogoja, saj svoje zmogljivosti plasirajo tudi komercialno, tj. izven okvira neprofitnega državnega financiranja. Anton p. Železnikar Projekt japonsko-nemškega slovarja Japonski in nemški učitelji na področju nemškega jezika, japonskega jezika, lingvistike in informacijske tehnologije so razvili koncept novega japonsko-nemškega slovarja, ki naj bi poenotil različne funkcije dvojezikovnega slovarja v obliki podatkovne baze in omogočil dostop k razumljivejši in raznovrstnejši vsebini. Ta slovar upošteva splošno sprejete, vendar večkrat negirane razlike dvojezikovnih slovarjev glede na izvirni jezik (izvirnega uporabnika). Te razlike semujno pokažejo v primerih, ko japonsko-nemški slovar uporabljajo Nemci pri študiju japonščine ali Japonci pri študiju nemščine. Zato morajo izhodni formati pri vhodnih podatkih dovolj izčrpno upoštevati tako japonsko kot nemško leksiko. Le tako lahko slovar preseže študijske in didaktične kakovosti navadnih dvojezikovnih slovarjev v obliki unificirane, relativno pomensko zgoščene in leksikalno kontrastne deskripcije za oba jezika, vendar v eni smeri (iz japonščine v nemščino). Slovar vsebuje podrobno fonetično, gramatično, semantično in fakmalno informacijo za vsako glavno besedo (headword), ki je bila še zlasti dopolnjena za japonskega uporabnika slovarja. Elektronsko procesiranje podatkov omogoča zapis velike količine podatkov na omejenem prostoru in tako so bili lahko vključeni v slovar tudi sistematično številni primeri besedil. Skozi to orientacijo je postal slovar tadi dragocen instrument za raziskave gramatike, semantike in stila za nemške in japonske uporabnike. Druga specifična lasmost slovarjaje integracija leksikografsko distinktnih komponent, kot so npr. splošni, tehnični in kulturni Vokabular v okviru enega obsežnega slovarja. V okviru splošnega japonskega vokabularja je narejena distnikcija med avtohtonim in sino-japonskim vokabularjem (yamatokotoba in kango), ki morata biti obravnavana leksikalno ločeno. Z upoštevanjem vseh teh komponent je bila ekspertno določena dvojezikovna baza podatkov, ki omogoča javni dostop prek primernih medijev (MT, FD, CDROM itd.). Projekt podpirajo Japan Society for the Promotion of Science, the Instimte of Cultural and Linguistic Studies of Keio University, the Scientific and Technical Faculty of Keio University, the National Research Institute for the Japanese Language, The Japan Information Center of Science and Technology (JICST), Toshiba, DEC Japan, NEC korporacije, Toyota Foundation in Kaj ima Foundation. Projekt vodi dr. Kennosuke Ezawa na univerzi v Tübingenu (Nemčija) v okviru Lingvističnega oddelka za nemški seminar. Na projektu sodelujejo še univerze in inštituti v različnih krajih, kot so Tübingen, Bonn, Hamburg, Niiza, Tsukuba, Dokkyo, Kyoto, Tokyo in Yokohama. Vse to kaže, kako kompleksno so danes koncipirani za nas »enostavni« projekti. Anton P". Železnikar Konzorcij za leksikalne raziskave Računalniška lingvistika je dosegla točko, kjer so zmogljivosti sistemov za procesiranje naravnih jezikov omejene s t.i. leksikalnim zadržkom. Ti sistemi lahko obdelajo veliko več besedila in producirajo pomembne aplikativne rezultate z ugotovitvijo, da so njihovi leksikoni premajhni. Association for Computational Linguistics v ZDA je predlagala ustanovitev konzorcija (Consortium for Lexical Research, kratko CRL), ki ga bo financirala DARPA. Sedež tega konzorcija j e v Computing Research Laboratory (Rio Grande Research Corridor, New Mexico State University). Konzorcij je organizacija za razdeljevanje podatkov in orodij pri raziskavah slovarjev in leksikonov naravnih jezikov in za komunikacijo raziskovalnih rezultatov. CLR ne sme kreirati t.i. komercialnih produktov in služi le predkonkurenčnim raziskavam, katerih cilj je konstrukcija računalniških leksikonov. CRL sprejema prispevke neglede na izvor, teoretično usmeritev in jih distribuira. Računalniška oprema CRL obsega primerne stroje za napredno obdelavo podatkov, kot so: Connection Machine, Intel Hypercube, Sequent Symmetry, IBM-ACE in še vrsto navadnih strojev. Omogočen bo mdi dostop do strojev z velikimi pomnilniki. Anton P. Železuikar Genelex: Eureka za lingvistično inženirstvo Računalniška lingvistika že vrsto let ni več samo akademska aktivnost, postaja čedalje bolj mdi industrijska. Na sestanku evropskih ministrov junija 1990 v Rimuje bil tako odobren mdi projekt Genelex v okviru Eureke kot največji projekt leta. Projekt bo živel štiri leta s proračunom 250 milijonov frankov in se bo izvajal v Franciji, Italiji in Španiji. Sodelujejo pa: v Franciji Buli, Gsi-Erli, Hachette, IBM, LADL, Sema-Group; v Italiji Lexicon, Research consortium of Pisa, Servedi (Utet and Paravia); v Španiji Sal vat, Tecsidel, University of Barcelona. Jezik postaja glavni informacijski vektor in mnoge aplikacije potrebujejo kompleksno informacijsko procesiranje v pisni obliki. Vrsta projektov je bila realiziranih v okviru ERLI (Eureka for Linguistic Engineering). Avtomatično indeksiranje je program za analizo dokumentov, ki pridmžuje celomi dokumentni bazi primerne koncepte za uporabo v raziskovalni fazi. S tem orodjem je mogoče tudi avtomatično analizirati vprašanja v naravnem jeziku in prek konceptov, s katerimi je bil dokument indeksiran, poiskati odgovore (informacijski retrieval). Telematični vmesniki so bili razviti v Franciji in zahtevajo naravni dialog (brez uporabe računalniških jezikov) med javnimi uporabniki in različnimi storitvami v okviru francoske mreže Minitel. Avtomatično prevajanje ali računalniško podprto prevajanje (Computer Assisted Translation, kratko CAT) je program za analizo stavkov v danem jeziku, ki zgradi bolj ali naj abstraktno predstavitev stavkov in generira namenske stavke iz te predstavitve. Možno je mdi vpraševanje v relacijskih podatkovnih bazah v naravnem jeziku, avtomatično generiranje korespondence itd. Ta možnost je tako sestavni faktor kompleksa računalniki in jezik v moderni družbi. V primerjavi z ekspertnimi sistemi je ostalo področje procesiranja naravnih jezikov na margini naprednih medijev. Enostavneje je bilo namreč razumevati generična komercialna orodja (ekspertai generatorji) in se tako izogibati realnim problemom (oblikovanje pravil), ki se začenjajo pri uporabnikih. Področje naravnih jezikov je še vedno v svoji jecljavi fazi in se najraje ukvarja z aplikacijskim razvojem za posamezne kliente in potrebe ter se. ne spušča v tvegano investiranje svojih razvojnih produktov (izjema so seveda Japonci!). Trg ekspertaih sistemov seje oblikoval .vnaprej, trg naravnih jezikov pa oblikujejo zahteve. V Gsi-Erli je 90% naročenega razvoja namenjenega naročniškim aplikacijam in ne produkmemu razvoju. Izkušnje na področju aplikacij z naravnim jezikom pa so povzročile nastanek generičnih razvojnih orodij s splošnim pomenom, ki jih lahko razvrstimo v tri skupine. Avtomati so analizatorji, ki omogočajo računalniško konstrukcijo predstavitve stavčnih pomenov. Ti generatorji lahko zgradijo stavek iz semantične predstavitve. Analizatorji uporabljajo dve vrsti podatkovnih baz, in sicer gramatično in slovarsko. Gramatika pomaga analizatorju pri manipulaciji s sintakso stavka in deluje v obliki pravil. Za vsako aplikacijo obsega določen korpus, ki je reprezentativni vzorec za množico stavkov, ki se procesirajo. Gramatika opisuje lingvistične fenomene, ki so zastopani v korpusu: vprašalni, relacijski, koordinacijski fenomeni itd. Navadno se v tej zvezi razvijajo zelo različne gramatike. 5/ovf2r dovoljuje analizatorju, da razpolaga z vso povezano informacijo za neko besedo: morfološko informacijo (del govorice, pravila sestavljanja z drugimi besedami), semantično informacijo (opisi pomenov besede) in večkrat še s pragmatično aplikativno informacijo. Cilj projekta Genelex (Generic Lexicon) je konstrukcija generičnega slovarja za različne evropske jezike (zaenkrat francoskega, italijanskega in španskega), tako da ne bo potrebno konstruirati novega slovarja za vsako novo aplikacijo. S teni načinom naj bi bila zagotovljena tudi operacijska kakovost slovarja in nizka cena pri več kot 40000 besedah. Ta sistem bo omogočal tudi poljubne modifikacije, izdelavo posebnih slovarjev, skratka razvojno fleksibilnost in ekspertizo. Cilj projekta ni le generični slovar, temveč mdi strategija, ki bo zagotavljala, da bo slovar ostal generičen. Osnova tega slovarja bo velika podatkovna baza. Projekt Genelex sestavljajo tri naloge. 1. Definira se podatkovni model za predstavitev strukture besede z možnostjo naložitve te predstavitve v podatkovno bazo. Informacijska množica (morfološka, sintaksna in semantična), ki se lahko poveže z besedo, predstavlja Uidi relacijo odvisnosti. Ta model bo postal standard za lek-sikalno predstavitev. 2. Možna je konverzija iz drugih modelov slovarjev v model Genelex in na razpolago so še druge funkcije: pomoč leksikografu pri mešanju (zlivanju) slovarjev, analiza besedil pri vstavljanju v model (morfologija, sintaksa), leksikografska delovna postaja (administracija leksikalne podatkovne baze) in generatorski programi (generiranje podlek-sikonov). 3. Učinkovito konstruiranje generičnega slovarja. Ànton P. Železnikar Oblikovanje leksikalnih modelov pri IBM IBM gleda na možnosti računalniške leksikografije/leksikologije predvsem s stališča predstavitve in shranjevanja leksikalnih podatkov. Tako se problemsko osredotoča na postopke ekstrakcije leksikografskih podatkov v okviru procesiranja strojno berljivih besedil v naravnem jeziku. To je seveda le prvi in pri IBM vselej poslovno zakriti vtis. Prav verjetno pa se IBM s tem ne odpoveduje implementaciji on-line slovarjev za človekovo rabo in implementaciji kom-pilacijskega programskega sistema za vključevanje podatkov v prihodnje človekove slovarje, ki jih bo tržil. Pri vsem tem je izrecno poudarjeno pridobivanje (akvizicija) leksikalne informacije in oblikovanje (struktura in organizacija) podatkovnih modelov za generične naloge, kot so identifikacija, odkrivanje, ekstrakcija in reprezentacija leksikalnih lastnosti besed na osnovi raziskovanja velikih slovarjev, ki so na razpolago v elektronski obliki. Takšen slovar bi lahko bil npr. Longmanov elektronski slovar (ali bolje baza), s 30 milijoni angleških besed. Vse več projektov s področja računalniške leksikografije in leksikologije uporablja v začetni fazi strojno berljive oblike objavljenih slovarjev. Posamezni cilji pri tem bistveno variirajo: vključujejo npr. lingvistično analizo slovarskih definicij, statistično osnovano iskanje regularnih vzorcev v slovarskih virih ali polavtomatično izpeljavo leksikonov iz obstoječih slovarjev. Skupna značilnost vseh takih projektov je potreba po določenih okvirih, v katerih se iščejo preslikave iz izvirnih oblik v leksikalne podatkovne baze. Opazne so predvsem tri oblike opisanih okvirov, in sicer prenos (transdukcija), predstavitev (reprezentacija) in vpraševanje. Zunaj specifičnosti katerega koli pristopa je uporaba strojno berljivega slovarja za ekstrakcijo fragmentov leksikalnih enot. Dostop do leksikalne vsebine on-line slovarja je vselej zagotovljen z uporabo vpraševalnega mehanizma; izrazna moč vpraševalnega jezika določa meje in podrobnosti leksikalnih lastnosti, ki bodo izločljive iz leksikal- nega vira. Podrobnosti so seveda odvisne tudi od predstavitvene sheme, ki jo npr. uporablja konkretni model on-line slovarja. Narava slovarske predstavitve bistveno omejuje vrsto opazovanja, ki zadeva implicitno kodirano informacijo slovaija in lingvistične posplošitve, ki se zrcalijo v slovarju. Neodvisno od predstavitve pa je potrebna računalniška podpora za prenos surovega tračnega formata v množico slovarskih zapisov in polj. Nekatere zahteve pa so ortogonalne: mehanizem za analizo slovarskega vira je lahko neodvisen od načina predstavitve slovarskih podatkov. IBM razvija npr. splošno orodje za analizo slovarskih enot; v pripravi je tudi predlog za splošno in aplikacijsko neodvisno predstavitveno shemo za on-line slovarje. Kljub temu pa še ni soglasja, kakšen naj bi bil splošen računalniški model slovarja, še posebej z vidika, kakšne vrste procesiranja naj bi model podpiral. Pridobivanje (akvizicija) leksikalnih podatkov zadeva tako njihovo analizo, dostop in metodologijo. V okviru tega je posebno vprašanje namenjeno formatom leksikalnih podatkov v okviru konvencionalne tehnologije podatkovnih baz in načrtovanju slovarskih podatkovnih baz. Možna je identifikacija štirih razredov slovarskih modelov. Te je mogoče razdeliti na relacijske in hierarhične formate, s poddelitivijo na fizične, logične in leksikalno koncipirane hierarhije, ki se pojavljajo kot organizirni principi predstavitve on-line slovarja. Skladno s priznanim principom tehnologije podatkovnih baz preslikava relacijski model slovarja neko slovarsko enoto na množico tabel. Tu ne obstaja kanonična splošna preslikava med leksikalnimi atributi in lastnostmi, ki so tipične za slovar in entitetami in relacijami, ki jih modelira relacijska podatkovna baza. Kljub temu pa postopen način načrtovanja podatkovne sheme omogoča vzdrževanje vidne slovarske informacije v podatkovni enoti. Primer take podatkovne sheme je npr. on-line model za Longman Dictionary of Contemporary English. Za ekstrakcijo leksikalnih relacij, kot so is_a, pàrt_of, group_of, degree itd., sta Nakamura in Nagao predvidéla posebna polja V enotah tega slovarja. Longmanov izvirni trak vsebuje določene označevalce, ki jih v knjižni obliki slovarja ne najdemo. Anton p. Železnikar Kitajski elektronski slovar Kitajci (Dept. of Computer Science, Tsinghua University) razvijajo elektronski slovar z bogato sintaksno in semantično informacijo za potrebe kitajskega determinističnega analizatorja, ki so ga razvili na univerzi Cingua. Format tega slovarja je prilagojen analizatorju in upošteva strukturne dvoumnosti kitajščine. Znanost o analizi kitajščine je v zaostanku. Kitajščina je predvsem analitični jezik, ki mu manjkajo formalni označevalci, kar otežuje analizo kitajskega jezika. Kitajci še ne razpolagajo z dovolj robustnim analizatorjem in zaradi tega zaostajajo tudi s projekti strojnega prevajanja kitajščine v uije.jezike. Analizatorje programiran v jeziku Common Lisp in se izvaja na delovni postaji Sun4/280. Analizator lahko analizira posamezne stavke kitajskega jezika v času, ki je manjši od stotinke sekunde. em analizatorja je postalo očitno, daje potrebno razviti tudi elektronski slovar z bogatim lek-sikalnim znanjem. Gre torej za slovar, ki je strukturno prilagojen potrebam determinističnega analizatorja. Vsak vstop kitajskega elektronskega slovarja ima tole strukturo: sintaksno-kategorialna, semantična, primerna (selektivna restrikcija različnih primerov), klasifikacijska, distinktivna (pravila razločevanja), ponovljiva (kategorialna dvoumnost) in shematska informacija. Že ta informacijska struktura odraža posebnosti kitajskega jezika, tj. kitajskih »besed«. Kaj bistveno več pa na tem mestu brez znanja kitajščine tudi ni mogoče povedati. Anton p. železnikar Slovenski slovnični in besedni pregliedovalnik Slovnični pregledovalnik slovenskih besedil (BesAna) je program za besedno in skladenjsko analizo, odkrivanje napak v besedilih in slovnični pregledovalnik. Program ima bazo s 15000 koreni, tj. okoli 250000 besed. Besede v bazi so zapisane s korenom in vzorcem za njihovo izpel-jevanje; tak pristop nudi majhno porabo pomnilnika in hitro iskanje besed. V bazo je mogoče dodajati nove besede. Posebej so zbrane besede, ki se najpogosteje napačno uporabljajo. Je pa še vrsta drugih opozorilnih funkcij: npr. velike črke sredi besede, lastna imena z veliko začemico, pisanje krajšav, manjkajoče vejice, kontrola pravilnosti rimskih številk, raba predlogov s, z, iz, k, h, v in na, preverjanje sklanjatve ob predlogih, ujemanje pridevnika in samostalnika, pomožnega glagola in deležnika na -1, označevanje napak v besedilu, ki se kasneje popravijo z urejevalnikom itd. Posamezne dele besedila (npr. v tujem jeziku) je mogoče izključiti iz analize, opravlja se statistika uporabljenih besednih vrst in pregledujejo se besedila vseh znanih besedilnih urejevalnikov (od ASCII formata do WordStara). Čeprav je Bes Ana čisti komercialni proizvod poslovnega konglomerata Graf, se v okviru te dejavnosti oblikuje tudi združen nacionalni in predvsem mednarodni projekt, tako da bo oblikovanje slovenskega elektronskega slovarja omogočeno z uporabo mednarodnih slovarskih standardov. Ti standardi se bodo vzdrževali s posebnim programskim orodjem za sistematično zajemanje slovarskih entitet (besed, slovničnih pravil, besednih kontekstov, besednih pomenskih konceptov, prevajalnih relacij glede na tuje jezike itd.). Pogajanja s rnjimi raziskovalnimi in komercialnimi ustanovami po svetu so v teku. Proizvajalec in distributor programa BesAna (Besedna Analiza) je Graf Inženiring, Letališka 33, Ljubljana (061/448 241). Cena je v območju 500 DM. Drugi proizvod je Mspell (Miha Mazzini), ki je program za odkrivanje tipkarskih, slovničnih in stilističnih napak v besedilih. Vsebuje 200000 izvedenih slovenskih besed, preverja uporabo velike začetnice po ločilih, odkriva in popravlja uporabo predlogov s, z, k, h in v, odstranjuje odvečne presledke pred ločili in dodaja manjkajoče za ločili, predlaga vejice, opozarja na zaporedno začenjanje stavkov z eno in isto besedo, preveija rimske številke, vodi evidenco o pojavnosti besed. opozarja na velike črke sredi besede itn. Okvirna cena je 300 DM. Anton P. Železnikar Japonska pobuda za sodelovanje pri razvoju in prodaji elektronskih slovarjev Razvoj elektronskih slovarjev zahteva harmonično sodelovanje različnih skupin, njihovo vodenje in koordinacijo. Japan Electronic Dictionary Research Instimte (kratko EDR) razvija v sodelovanju z drugimi skupinami in instituti elektronski slovar. Področji računalniških znanosti (procesiranje naravnega jezika) in lingvistike z leksikologijo sodelujeta tesno pri razvoju slovarja. V EDR projektu imajo računalniške znanosti pomembnejšo vlogo. Tudi obsežen elektronski slovar ni kaj dmgega kot kompleksen sistem in prav računalniško osebje ima potrebno izkustvo pri načrtovanju, razvoju, čiščenju, vzdrževanju in obvladovanju velikih sistemov. Glavni viri pri razvoju elektronskih slovarjev so seveda obstoječi slovarji v knjižni obliki, vendar se ti slovarji bistveno razlikujejo od elektronskih. Prav zaradi tega se elektronski slovarji načrmjejo in oblikujejo drugače že od samega začetka. EDR ima svoje slovarske podatke, ki so zelo grobi in so zbrani iz različnih slovarjev japonskih založnikov. Za zbiranje tega materiala zunaj EDR je bila potrebna kar precejšnja količina tehnologije in opreme. Pri tem je bilo potrebno upoštevati tudi avtorske pravice in pravno urediti ta vprašanja. Pomembno je omeniti, da elektronski slovarji pomagajo človeku uporabljati slovarje. Tu gre za velike volumne zbranih besedilnih podatkov in za metodologijo njihove uporabe. Tako se razvija novo področje interakcije med človekom in strojem na prodročju oblikovanja in uporabe slovarjev. Elektronski slovar je naprava za dejansko in učinkovito uporabo. Zaradi tega je primarni cilj projekta uporaba, kije pred samo kreacijo slovarja. Slovarji naj bi odražali poglede in zamisli uporabnikov na eni strani in izkustvo načrtovalcev, ki so se že doslej ukvarjali s procesiranjem naravnihjezikov in procesiranjem znanja, na dmgi strani. Pri EDR gre za distribuiran laboratorijski sistem z osmimi raziskovalnimi laboratoriji, ki so razporejeni v posameznih investicijskih podjetjih. Vsak laboratorij je tesno povezan s skupinami svojega podjetja, ko razvija svoj del velikega aplikativnega sistema za procesiranje naravnega jezika, vključno s strojnim prevajanjem. Pri projektu pomagajo mdi zunanje institucije, ki bodo predvidoma postale največji uporabniki elektronskih slovarjev. Trenutno sodeluje EDR z Electronic Laboratory (ETL), Institute for New Generation Computer Technology (ICOT), Center of the International Cooperation for Computerization (CICC) in s petimi univerzami na Japonskem (univerza v Kyom je glavna med njimi). Kakšno pa je mednarodno sodelovanje na projektu? Dokončni cilj projekta je razvoj in priprava elektronskih slovarjev, ki bodo lahko uporabljeni v številnih jezikih in v vseh svetovnih okoljih. Ta cilj se dosega s stalnimi in zadostnimi napori. Prevladuje prepričanje, da lahko elektronski slovar za posamezen jezik pripravijo samo skupine ljudi, ki jim je ta jezik materin jezik. Pri izdelavi dvojezikovnih slovarjev sodelujejo strokovnjaki s področja obeh jezikov. Pri EDR projektu (v sedanji fazi) stabili izbrani japonščina in angleščina kot namenska jezika s podarkom na japonščini. Angleščina je bila pridružena kot namenski jezik zaradi svoje pomembnosti, saj prevzema vlogo skupnega mednarodnega jezika. Z vključitvijo angleščine bo mogoče todi preveriti univerzalnost specifikacij v EDR slovarjih. Zaradi nujnosti sodelovanja z raziskovalnimi skupinami v različnih jezikih je EDR zaupal nekatere svoje naloge univerzi v Manchestru (University of Manchester Instimte of Science and Technology). To sodelovanje se bo razširilo še na druge anglosaksonske univerze. Japonci so že zdavnaj ugotovoli, da je angleščina skupen mednarodni jezik. Vendar narašča mdi zanimanje za druge jezike, ki naj bi jih tudi bolj upoštevali. V poštev prihajata zlasti francoščina in nemščina. Vendar je predvideno tudi tesno sodelovanje z nekaterimi azijskimi narodi, zlasti s skupinami v Kitajski, Tajski, Maleziji in Indoneziji skozi projekte v okviru CICC. Te skupine že razvijajo svoje lastne elektronske slovarje z uporabo istih specifikacij kot v EDR. Odprte so tudi vse možnosti za daige narode (tudi za slovenščino), če bi se sami lahko odločili za tovrsten raziskovalni podvig. Iz tega bi prav gotovo lahko nastali odlični elektronski slovarji za Slovence, slovenska raziskovalna sfera pa bi dobila relevantno nalogo ne le v okviru slovenske samobitnosti temveč predvsem v povečevanju možnosti za kakršnokoli preživetje slovenskega jezika. Pri sodelovanju s tujimi skupinami poudarja EDR pomembnost dogovorjenih procedur, ki so koristne za obe strani. To sodelovanje naj bi se uravnavalo v naslednjih korakih: Korak 1. Izmenjava informacye o tehnologijah. Specifikacije EDR in druga informacija v procesu raziskav in razvoja je praktično na razpolago z vsemi podrobnostmi. EDR že prireja posebne delovne sestanke za udeležence z vsega sveta. Obstaja slovarska povezava za interesente, ki bi želeli bolj podrobno informacijo o vsebini elektronskega slovarja. Slovarsko povezavo sestavljajo množice glavnih konceptov in glavnih besed, ki kažejo trenutno stanje elektronskega slovarja. Ta povezava se spreminja z napredovanjem projekta in deluje od začetka tega leta. Pristojbina za povezavo obsega le distribucijske stroške. Korak 2. Tehnične obveznosti. Nadaljnje dogovarjanje je potrebno s skupinami, ki nameravajo razvijati elektronske slovarje po specifikacijah, ki so enake ali podobne oniin iz EDR. EDR je pripravil podrobnosti in programsko opremo (objektni kod) za različne sisteme, na katerih bi se izvajal razvoj elektronskega slovarja. Korak 3. Medsebojna izmenjava elektronskih slovarjev. Ta korak naj bi bil končna stopnja sodelovanja. Možno naj bi bilo izmenjevanje elektronskih slovarjev, če obstaja soglasje obeh partnerjev. Z izmenjavo slovarjev naj bi počasi in zanesljivo nastal svet različnih elektronskih slovarjev. V tej fazi je najpomembnejši princip, da se vsak jezik obravnava enako, na enaki osnovi. Načelno se vsi rezultati EDR projekta prodajajo za primemo ceno. Pod enakimi pogoji bo tekla tudi prodaja elektronskih slovarjev neglede na izvor, lokacijo uporabnika (enaki pogoji za domače in tuje uporabnike). Pričakovane cene bodo nižje od drugih elektronskih slovarjev na trgu. Posebni popusti bodo veljali za akademske, univerzitetne in javne raziskovalne institucije. Natančen datum začetoe prodaje je tale: Japanese Word Dictionary (april 1991); drugi slovarji bodo sledili kolikor mogoče kmalu. Opisane principe zastopa EDR. Pri sodelovanju z drugimi skupinami bo EDR postopal kar se da prožno in prilagodljivo. Pri tem naj bi se nikoli ne ustavilo izboljševanje in razširjanje slovarjev. Prav izboljšave in razširitve slovarjev bodo zahtevale svetovno koordinirano vzdrževanje. EDRje že pristopil k vzpostavljanju ustrezne organizacije, ki bo širila in vzdrževala trajno sodelovanje med deželami tega sveta. Anton p. Želemikar Knjižne recenzije Recenzija knjige: Anton P. Železnikar, On the Way to Information, Part 1, Ljubljana Nastanak ove knjige najbolje će razumjeti čitaoci, koji poznaju autora, Antona Železnikara. Železnikar je u svojoj karijeri prošao kroz sve sektore digitalne elektronike, kompjutora i informatike. Već kao mladi inženjer projektirao je digitalnu memoriju za spremanje podataka iz nuklearnih strojeva. Tada su Instimti Jožef Stefan, Rudjer Bošković i Boris Kidrič bili u samom svjetskom vrhu u digitalnoj tehnici. Tako na primjer, instituti u mnogim zapadno evropskim zemljama u to vrijeme nisu još razvili digitalnu memoriju, kakvu je Železnikar razvio u Jožef Štefanu. Od digitalne logike Železnikar je krenuo u svijet programiranja, programskih jezika, dizajna i upotrebe kompjutora, matematičkih i teoretskih radova, pa sve do ove knjige. Probao je život sveučilišnog profesora, istraživača i dizajnera i voditelja razvojne grupe u industriji. Njegovo veliko i široko iskustvo omogućilo mu je da stvori filozofski stav prema kompjutorima i informacijama i da ga uobliči u ovoj knjizi. Kompjuteri služe da skupljaju, preradjuju, filtriraju, modificiraju, transformiraju, i t.d., informacije. Svrha: dati korisniku pravu i traženu informaciju. 0 obradi informacija postoje razradjene teorije i posaipci na nižem i na višem nivoju, od interesa za kompjuterske profesionalce. Železnikar želi svoju knjigu postaviti iznad ovih teorija i iznad kompjuterske profesije i približiti ju filozofiji, pogledu na svijet. Gotovo sve filozofske studije pisane su od ljudi koji ne poznaju niti približno, a kamoli detaljno, svijet kompjutera i informatike i utjecaj na život i rad ljudi. Železnikar predvidja da će filozofi, sociolozi, žurnalisti, kompjuteraši, materijalisti i idealisti oponirati proširenju i predefiniranju pojava informacije. Ova knjiga upravo to čini: proširuje i predefinira pojam informacije. Železnikar nije želeo upasti u postojeće kolotečine, želeo je ići smjerom koji nije uobičajen. Univerzalna informacijska teorija i filozofija koju opisuje ova knjiga predstavljaju originalne poglede Železnikara, a ne kompilaciju do sada poznatog i prihvaćenog. To se dobro vidi u dijelu knjige koji obradjuje temu: Bog kao informacija. Železnikar vjeruje da univerzalno poimanje informacija može pozitivno utjecati na budući razvoj informacijskih teorija u raznim znanostima, na konstrukciju intelegentih strojeva i programa i nà bolje razumjevanje života i živih biča, mozga, uma i vjere. Knjiga je pisana na engleskom jeziku i na nekim mjestima se osjeća da to nije materinji jezik autora. Knjiga je originalna i traži prilično truda i odredjenu naklonost prema filozofiji da bi se čitala. Vjerovatno će izazvati kontradiktorne sudove. Po svoj prilici Železnikar to upravo i želi: stvoriti nove valove u Moru Informacija. Zagreb, 12.11.1990 Prof. Branko Souček Prirodoslovno-mateniatički fakultet Sveučilišta u Zagrebu On the Way to Information (Na poti k informaciji) Knjiga »Na poti k informaciji« predstavlja sintezo več znanj s področja filozofije, tehnike, jezikoslovja in tudi — če pomislimo na njeno nadaljevanje (tovrstoi članki so bili že objavljeni v časopisu Informatica) — logike in matematike. Avtor se loteva problematike na sebi svojstven način, ki mu vsaj v naši deželi ni para. Z zelo široko in poglobljeno definicijo pojma informacije (njemu sorodnih pojmov) skuša zajeti glavne paradigme filozofije in mdi tehniških in naravoslovnih ved. Seveda se mu to pokaže skozi analizo pojma subjekta in objekta. Pri tem se znajde pred svojevrstno dilemo: ali opisovati subjekt kot vzročno-posledičen splet, ali drugače rečeno, kot zaporedje možganskih stanj ali pa kot tok predstav ali odnosov med idejami; skratka, namesto stanja možganov imamo stanja duha. S svojim konceptom informacije, ki je tudi nekaj, kar samo sebe izpeljuje, se avtor hoče rešiti te dileme pri opisu subjekta. Na ta način lahko združi opise naravoslovnih ved, kot so fiziologija (možgani) in sploh biologija (v stilu kakega Mamrane) in psihologije, s fenomenološkimi opisi zavesti kot toka doživljajev. Če gleda na organizem zgolj kot na nosilca informacijskih procesov in jih razlaga s pomočjo znanstvenega aparata biologije (fiziologije), potem mu ta razlaga lahko predstavlja podlago za razlago organizma kot subjekta, ki sam sebe izgrajuje (autopoiesis), kar pa lahko razumemo tudi čisto v filozofskem smislu subjekta, ki skozi svoj razvoj (zgodovino) konstimira samega sebe predvsem tako, da ima sam določeno predstavo ali razmerje samega sebe (informacija informacije). Če se bo avtorju posrečilo še na dovolj enostaven, razumljiv in zanimiv način formalizirati (kar je delno že storil v prej omenjenih člankih v Informatici) sklop pojmov, ki vsi izhajajo iz pojma informacije, kar bo vsebina nadaljevanja te knjige, potem bo imel bralec pred sabo močan izziv za razmišljanje o odnosu mišljenja in sveta in za tehniško zapopadenje tega odnosa, v Ljubljani, 29.1.1991 Doc. dr. Valter Motaln Fakulteta za strojništvo Univerze v Ljubljani Vprašanja, ki jih je postavil dr. V. Motaln avtorju na tiskovni konferenci v Mladinski knjigi (Titova 3, Ljubljana), dne 29.1.1991: 1. Kako lahko vpliva po vaše razdelava teorije infonnacije na razvoj metodologije znanosti? Odgovor: Razširjena teorija informacije lahko bistveno prispeva k razvoju metodologij znanosti na več načinov. Prvi vidik je sprememba jezika (znanstvene govorice neke discipline), v katerem t.i. znanstvene formule (fiksni logični izrazi, principi znanosti, njene formalizirane teorije) preidejo v t.i. formalne scenarije, tj. v razvojno odprte formule in teorije, ki so podvržene nastajalnim, konstruktivnim možnostim znanstvene discipline. Ta vidik se veže na vpeljavo informacijske logike, ki določeni znanstveni disciplini omogoča vpeljavo njenih specifičnih pravil za razvoj znanostnih, raziskovalnih in konstrukcijskih formul. Ta logika prinaša v mišljenje znanosti metodološki obrat, ki poudarja nastajanje znanstvene discipline same in odvisnost od informacijskega nastajanja v drugih znanostih, znanstvenih komunah in okoljih. Hkrati pa informacijski pristop, kot je zasnovan v knjigi, prinaša v zavest raziskovalca fenomenološki vidik, ki ima lahko bistveni vpliv na nastajanje nove metodologije. 2. Kaj lahko pove teorija informacije o naravi jezika? Ali ga razume predvsem kot skupek pravil za rojevanje (generiranje) novih izrazov (izrazov nasploh) ali tudi kot skupek pravil, ki rojeva tudi samega sebe? Kakšen je odnos jezika in bitja, ki ta jezik uporablja? Ali je jezik v resnici »hiša biti«, kot slikovito pravi Heidegger? Odgovor: Jezik je le ena izmed specifičnih jezikovnih informacijskih pojavnosti-, seveda če ga ne motrimo zgolj s stališča tradicionalnega jezikoslovja. Teorija informacije se lahko marsičesa nauči prav pri nastajanju (govorjenju, pisanju, mišljenju) jezika, tj. njegovih stavkov in stvačnih kompleksov. Naravni jezik je najprej sam sebi jezik, sam sebi opisni jezik oziroma metajezik ali jezik jezika. Naravni jezik, njegovi označevalci in njim pripadajoči (nastajajoči) pomeni, razumevanje jezika kot spontano informacijsko gibanje po prepletenih semiotičnih mrežah in oblikovanje pomena nastajajo tedaj v prostranstvu jezika samega, razvijajočega, nastajajočega jezika. Jezik kot informacija rojeva sam sebe v jezikovnih diskurzih, spontano upoštevajoč določfcna pravila in njihovo nastajanje v domeni jezikovnega informiranja. Razširjena teorija informacije seveda ne gleda na jezik kot skupek pravil, npr. v stilu N, Chomskega ali podobnih formalnih, značilno reduciranih, avtomatnih (generacijskih) teorij jezika. Tovrstoe končne množice pravil za rojevanje neskončnih množic izrazov (npr. sin-taksno pravilnih) so s stališča teoretske estetike seveda privlačne, vendar ne razrešujejo problemov pomena, vsebine, prevajanja. razumevanja, specifične uporabe in drugih bistvenih vidikov jezika. Odnos jezika in bitja je odnos jezikovne informacije (lasme in druge) do metafizike kot totalne (vseobsegajoče) informacije bitja. Seveda je v metafiziki tudi jezikovna informacija že ponotran-jena, stvar metafizike same, čeprav bistveno oblikovana iz jezikovnega informacijskega okolja. Materin naravni jezik je npr. sooblikovalec metafizike kot informacije (prepričanja, vere, znanja, govornega in motoričnega obnašanja, nazora itd.), prav za prav del metafizike same, njenega domovanja; mj naravni jezik je spočetka le neke vrste metafizični problem bitja, prenašalec informacijske vsebine, nastale npr. v mišljenskem prostoru materinega jezika. Sčasoma pa se seveda lahko oblikujejo pristoi (profesionalni, tehnični ali metafizični) odnosi tudi med tujimi ali celo umetelnimi jeziki in bitjem. Jezik kot informacija postane tako najprej »hiša bitjevske informacije«. Kot »hiša oziroma dom biti« je jezik seveda »hiša informacije«. Zakaj prav hiša, to je prijazno okrovje in ne nekaj manj? Ker z jezikom, zlasti naravnim (materinim) jezikom bistveno, intenzivno in kar se da domače komuniciramo (informiramo) s samimi seboj in seveda z drugimi bitji. Ta jezik ne le tovori informacijo, temveč postane hkrati tudi njen konstiment, ne le kot možnost, temveč kot »sema« in »pragma«, kot pomen in govorna praksa in v tem okviru informacijska (govorna) moč, ki se lahko povzpne do poljubno zahtevnih višin, seveda le tistih, ki j ih posameznik (kot avtopoezno bitje) še lahko smiselno in im-aginativno doumeva (oblikuje, razumeva, zapopada, umešča v svoje umevanje stvari). Heidegger je namenil razumevanju kot eksistencialni konstituciji tu-biti doslej nedosegljivi filozofski spev (glej npr. v »Sein und Zeit«, paragrafa »31. Das Da-sein als Verstehen« in »32. Verstehen und Auslegung«), seveda le v okviru svojega projekta razumevanja biti. V »hiši informacije« z jezikom, bitjo, mbitjo, bitjem, bistvom, razumevanjem, stvarjo oziroma s katerim koli (mejnim) filozofskim pojmom postane vse to lahko le posebna oblika oziroma proces informacije — zgolj informacija — formirane in organizirane fenomenološke strukture. 3. Ali odpira knjiga nove razsežnosti za razumevanje umetne inteligence ? Odgovor: Prvotni" (primordialni) impulz moje odločitve za »potovanje« po poti k informaciji je nastal iz osebne teorijske in inženirske (konstruk-torske, tehnološke — v smislu nove tehnologije — in simbohio-teoretske) atitude. Terry Winograd (Stanford University), eden pionirjev prostranstva umetne inteligence, je leta 1986, skupaj s Fernan-dom Floresom, razprl do takrat nezaslišano dilemo o razumevanju (načrtovanju, rabi) računalnikov in spoznanja, na katero je ostro reagirala konsolidirana komuna umetnih inteligenčnikov (polemika v časopisu Artificial Intelligence) (hereza, odpadništvo, zgubljenost). Reakcija je bila podobna oni pred dobrimi dvajsetimi leti, ki jo je doživljal H.L. Dreyfuss (What Computers Can't Do) na MIT. Moje osnovno vprašanje takrat je bilo, kaj je informacija v živem in umetnem, katere so možne povezave, modeli, projekti, scenariji, novi formalni okviri in predvsem razumevanje. Umetna inteligenca — z umetnim razumevanjem — je prostor človekovih inteligentnih orodij (pripomočkov, naprav, opreme), ki se preko razumevanja informacijske fenomenologije v živem približuje živi kompleksnosti, poziciji in atitudi informacije tudi v strojih, seveda, v kolikor ji uspeva spoznava in tehnološka realizacija naravnih informacijskih scenarijev. Posledica tega stališča je, da sta »stroj« (arhitektura stroja) in »program« (programski sistem stroja) informacijska, tj. informacijsko spremenljiva oziroma nastajalna. S tem se preseže tradicionalna algorit-mika, kije prevladujoči princip zlasti na področju programiranja računalnikov. Tudi informacija v stroju — tako kot v živem — »nastaja« z informiranjem, protiinformiranjem in umeščanjem informacije, ki so osnovni trije informacijski principi. Scenariji (arhitekture, programi) so informacijsko nastajajoči, odvisni od trenutne informacijske pozicije in atitude naprave v določenem informacijskem okolju. Umetna inteligenca (inteligentni programi, ekspertni sistemi) seveda lahko uporablja nastalo, tudi tradicionalno (matematično, programsko) al- goritmiko, vendar razpolaga ob tem še z vgrajenimi informacijskimi mehanizmi, ki omogočajo obdelavo izredno velikih količin mrežno prepletene informacije, katere »obdelava« s programi in stroji temelji na izkustvenih scenarijih in ne več le na togih (fiksno formuliranih) teorijsko-modelnih programskih upodobitvah informacijske stvarnosti. Osnovna intenca teorije informacije je, da se tudi v človekove stroje »vgradijo« nekateri (spoznani) principi informacije v živem. Ob tem pa se teorija informacije nikakor ne odpoveduje spoznavanju nastajanja informacije zlasti v človekovih kortek-sih, v okviai katerih človek spoznava, razumeva, transcendira svojo mentalno, intelektualno in vedenjsko informacijo. V okviru tega pogleda na stvar umetne inteligence odpira knjiga tudi nove razsežnosti za razumevanje umetne inteligence kot človekove in hkrati strojne informacijske pojavnosti. 4. Ali je sploh možna formalizacija informacije, ki sama sebe izgrajuje? Odgovor: Formalizacija nekega področja je vselej predmet posebnega, lahko rečemo umetnega jezika (pomenskega prostora in razumevanja) discipline. Živi objekti so (iz perspektive subjektivnega opazovalca) samoreproduktivni, tj. av-topoezni oziroma sami sebe izgrajujoči. Npr. rekurzivne funkcije izgrajujejo svoje vrednosti iz predhodno zgrajenih vrednosti, od neke dane začetne vrednosti dalje. Tu so formalni začetki informacije, ki npr. od določenega mesta dalje izgrajuje svoje vrednosti izključno iz svoje prejšnje informacije s fiksnim pravilom, tj. z rekurzivno matematično formulo. Vendar je od tu dalje potreben skok v naslednjem premisleku: ali lahko ta funkcija izgrajuje tudi svojo formalno podobo, predpis, definicijo formule kot same sebe? Odgovor na to vprašanje je pritrdilen, saj je mogoče napisati program (v strojnem jeziku), ki sam sebe in druge programe modificira (npr. programski vimsi), torej jim nas taj alno spreminja strukturo funkcije. Človek seveda ima izkustvo, kako je mogoče samega sebe izgrajevati, zlasti na informacijskem področju (učenje, asociativno sklepanje, modusi zavestnega mišljenja, spontano gibanje po prepletenih nevronskih mrežah) ali kako oblikovati stroje, ki bodo imeli samoizgrajevalno funkcijo. Formalno se informacijska entiteta izgrajuje tako, da preprosto ima t.i. »operator nastajanja«, magični simbol informacijskega nastajanja, ki gaje mogoče modelirati celo z vrsto psevdodeterminističnih postopkov (npr. generiranje naključnih števil, znakov, simbolov, označevalcev informacijskih entitet, za katerimi se skrivajo informacijske procedure, tj. operacije itd.). Formalna teorija uvede preprosto operator informiranja, ki združuje v sebi aktaal-nost in potencialnost informacijskega učinkovanja (nastajanja, spreminjanja, preminjanja). 5. Kako bi s pomočjo teorije o informaciji razložili koncept zavednega-nezavednega? Ali je mogoče na njeni podlagi razviti razlago ustvarjalnosti (ustvarjalnost kot produkt nezavednega, kot produkt primarnih impulzov, ki izhajajo iz same iivalske narave človeka in, na drugi strani, ustvarjalnost kot produkt zavestnega ega, ki izhaja iz intemalizacije dnčtbenih odnosov) ? Odgovor: Zavedno je lahko tisto, kar informacijsko vstopa v razumevanje kot informacijsko entiteto. Nezavedno lahko ostaja zunaj razumevanja. Razumevanje je skupaj s svojimi pomeni, kijih producira, v razumevajoči cirkular-ni informacijski povezavi. To seveda ni ničesar drugega kot znani atributi filozofsko poj movane zavesti in samozavesti (samoreferenca, refleksija, transcendenca itd.). Ustvaijalnostna področju informacijskega je v grobem informacijsko nastajanje (spajanje, pomensko prepletanje, konstruiranje novih pomenov kot informacije, naraščanje ali minevanje razumevanja kot aktivne entitete). Razločitev na nezavedno in zavedno je kot rečeno lahko bistvena le s posebnega informacijskega vidika, kije razumevanje samo. Informacijski model sploh ne izključuje določenih fizioloških in psiholoških konceptov, npr. primarnih impulzov (instinktov), ega, ida, drugega, družbenega okolja, intemalizacije itd. Nasprotoo, prav iz teh konceptov lahko sestavlja informacijske entitete, jih ozaveda ali pa jih sploh ne opazi, jih pušča v nezavednem. Vprašanje, ki se postavlja, je prav gotovo izziv avtorju, da poskuša podrobneje odgovoriti, kaj je lahko koncept zavestnega in nezavednega v okviru razširjene teorije informacije. 6. Kako je sploh motno opisati zavestni tok, kje je po vašem točka razprtja (nem. die Erschlossen-heit, angl. disclosure, hrv. dokučenost), ko je mogoče govoriti o pogledu v notranjost duha (mind) (npr. topološki primer krogle, v katero je bila napravljena luknjica, tako da je razprtje notranjosti krogle mogoče) ? Odgovor: Vprašanje vprašuje po začetku zavesti, po točki, v kateri se informacija razpre (začne razumevati) kot zavest oziroma samozavest. Ali bistveno razumljeno, kdaj informacija pogleda ali že gleda sama vase, kdaj se ta pogled pojavi in kako se ta obrat in nezavednega v zavedno pokaže navznoter (samozavest) in navzven (zavest)? Izkustvo duha nam tu že marsikaj pove. Točka razprtja je kot že tolikanj doslej odvisna predvsem od opredelitve. Kot zavestna bitja se te zavesti opredelitve naenkrat zavemo in od ai naprej govorimo lahko o zavestoem razprtju. Razprtje torej ni ničesar drugega kot nova oblika razumevanja v okviru razumevanja kot nastajajoči informaciji (razumevajoča diferenciacija). Kriterije zavedanja je že danes mogoče specifično tako formulirati, da bi bili uporabni tudi za eksperimente v umetni inteligenci (npr. zdravorazumski modeli sklepanja). Avtor se zaveda, da so dani odgovori spontani, filozofsko in teorijsko zahtevni in daje za njihove izčrpnejše utemeljitve potreben dodaten napor in izvirni premislek. Oglas Prosimo imetnike starejših letnikov časopisa Informatica, da odstopijo ali prodajo posamezne letnike časopisa, in sicer: letnik I (1977), II (1978), III (1979) in VIII (1984). Informacije dobite pri tehničnem uredniku dr. R. Murnu, tel. (061) 214 399. Informatica Editor-in-Chief ANTON P. ŽELEZNIKAR 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 ALAGIĆ Faculty of Electrical Engineering University of Sarajevo Lukavica - Toplieka bb 71000 Sarajevo DAMJAN BOJADŽIEV . Jožef Stefan Inštitute Jamova c. 39 61000 Ljubljana JOŽO DUJMOVIC Faculty of Electrical Engineering University of Belgrade. Bulevar revolucije 73 11000 Beograd JANEZ GRAD Faculty of Economics University of Ljubljana Kardeljeva ploSč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 TOMAZ pisanski Department of Mathematics and Mechanics University of Ljubljana Jadranska c. 19 61000 Ljubljana , . oliver popov' Faculty of Natural Sciences and Mathematics C. M. University of Skopje Arhimedova 5 . 91000 Skopje sa^o prešern Footscray Institute of Technology Ballarat Road, Footscray P.O. Box 64, Footscray Victoria, Australia 3011 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 tomaž banovec Zavod SR Slovenije za statistiko Vožarski pot 12 61000 Ljubljana andrej jerman-blazič Iskra Telematika Tržaška C. 2 61000 Ljubljana bojan klemenčič Turk Telekomunikasyon E.A.S. Cevizlibag Duragy, Yilanly Ayazma Yolu .14 Topkapi Istanbul, Turkey stane saksida Institute of Sociology University of Ljubljana Cankaijeva ul. 1 61000 Ljubljana jernej 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, Yugoslavia. / A Journal of Computing and Informatics CONTENTS Meaning, Understanding Self-reference Routing Algorithms for Packet Switched Networks Parallel Implementation of VLSI Circuit Simulation The Principle of Multiple Knowledge Informing of Things (in Slovene) Algorithm Simulated Annealing (in Slovene) Continuous Bayesian Neural Networks (in Slovene) An Algorithm for Boundary to Octree Conversion (in Slovene) Subprograms for Eigenvalue and Eigenvector Calculation (in Slovene) News on Electronic Dictionaries (in Slovene) Book Reviews (A.P. Železnikar: On the Way to Information 1; with some answers of the author) (in Croatian and in Slovene) D. Bojadžiev 1 Iskra Djonova Popova 6 S. Raman 14 LM. Patnaik J. Sile M. Špegel M. Gams 23 A.P. Železnikar 29 J. Zerovnik 40 /. Kononenko 49 Natalija Trstenjak 54 B. Zalik N. Guid Vesna Čančer 65 A.P. Železnikar 71 B. Souček 78 V. Motaln A.P. Železnikar