hvirtanen@abo.fi (Harry Virtanen) (09/10/90)
I have recently been developing the theoretical foundations for a Fuzzy Prolog system, called LukLog, a connection between Lukasiewicz logic and logic programming. I know of two other Fuzzy Prolog systems, PROLOG/P (developed in sweden) and PROLOG-ELF (developed in Japan). These two systems are built around the "fuzzy" connectors a' = 1-a (negation, NOT) a^b = min(a,b) (intersection, AND) avb = max(a,b) (union, OR) a<-b = max(1-b,a) (implication) where a, b are truth values (uncertainty factors) in the unit interval. Given the following Fuzzy Prolog program (A<-B1^B2^B3)<-0.9. % 0.9 denotes the uncertainty of the implication (B1<-)<-0.9. (B2<-)<-0.7. (B3<-)<-0.8. and the goal <-A gives the truthvalue of A as 0.7. LukLog is however built on the following functions/connectors a' = 1-a a^b = max(a+b-1,0) avb = max(a,b) a<-b = min(1-b+a,1) Given the above program and the same goal, gives the truth value of A as 0.3. I'm planning to present a paper (if accepted) on this subject at the IFSA 91' Brussels congress. Any comments, or information on other existing Fuzzy Prolog systems are welcome (personal mail or in this newsgroup). Harry Virtanen Abo Akademi University Department of Computer Science DataCity Turku, Finland ------------------------------------ The Future Ain't what it Used to Be Arthur C. Clarke ------------------------------------
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (09/11/90)
In article <6921.26ebb2bb@abo.fi>, hvirtanen@abo.fi (Harry Virtanen) writes: > I have recently been developing the theoretical foundations for a Fuzzy > Prolog system, called LukLog, a connection between Lukasiewicz logic and > logic programming. > LukLog is however built on the following functions/connectors > a' = 1-a > a^b = max(a+b-1,0) > avb = max(a,b) > a<-b = min(1-b+a,1) Would you care to say something about the relationship between "fuzzy" and whichever of Lukasiewicz's logics you have in mind? For a system without negation, Udi Shapiro had a paper in a conference years ago on logic programming with certainty factors. Basically, if you have head <-[f]- goal1 & ... & goaln meaning certainty(head) >= f(certainty(goal1), ..., certainty(goaln)) where f is monotone (details spelled out in the paper), the usual T^w(P) fixed point approach carries over just fine. The really exciting thing about this is that *numeric* certainties are (a) too limited and (b) too detailed: (b) people can never figure out what the numbers are to be (whereas with a coarse classification -- say four certainty levels, as used in some medical programs -- they can often manage) but (a) when strange things go happen there isn't enough information in the numbers to figure out _why_. Shapiro's approach applies to *any* complete lattice used as a certainty space. (There isn't the least reason for fuzzy logic to be confined to numbers. There was an MSc thesis done at Auckland University Mathematics Department about 11 years ago that generalised fuzzy stuff to other lattices.) After reading Shapiro's paper I started to write a paper on the generalisation to other lattices, but someone from MIRU convinced me that it was too trivial to be worth writing up. (There were some interesting details about cutoffs when you haven't got numbers, but alas, I've forgotten how I was going to solve the problem.) Handling negation with certainty factors in something resembling Prolog is going to be at least as hard as handling "simple" negation; I find it incredible that doing something like non G has certainty 1-X if G has certainty X would work. Surely you must be doing something much cleverer than that? -- Heuer's Law: Any feature is a bug unless it can be turned off.
mgv@usceast.UUCP (Marco Valtorta) (09/11/90)
In article <3728@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <6921.26ebb2bb@abo.fi>, hvirtanen@abo.fi (Harry Virtanen) writes: >> I have recently been developing the theoretical foundations for a Fuzzy > >For a system without negation, Udi Shapiro had a paper in a conference >years ago on logic programming with certainty factors. Basically, if I think that the paper you have in mind is "Logic Programs With Uncertainties: A Tool for Implementing Rule-Based Systems." _Proceedings of IJCAI-83," 529-532. (The paper is interesting, but the approach to debugging sketched in its section 4 seems hopelessly naive to me. There is no way an expert can be expected to provide or recognize whether a proposition has the correct numerical certainty, as required by the algorithm sketched there.) Marco Valtorta usenet: ...!ncrcae!usceast!mgv Department of Computer Science internet: mgv@cs.scarolina.edu University of South Carolina tel.: (1)(803)777-4641 Columbia, SC 29208 tlx: 805038 USC U.S.A. fax: (1)(803)777-3065 usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv
ken@aiai.ed.ac.uk (Ken Johnson) (09/12/90)
In article <6921.26ebb2bb@abo.fi> hvirtanen@abo.fi (Harry Virtanen) writes: >I'm planning to present a paper (if accepted) on this subject at the IFSA 91' >Brussels congress. Any comments, or information on other existing Fuzzy Prolog >systems are welcome Look at Fril, distributed by Fril Systems Limited, which is some sort of offshoot of the University of Bristol (UK). Fril is a Lisp-look prolog in which relations and facts have probability ranges, e.g. `the probability of this lies between 0.4 and 0.7'. -- Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 213 `I have read your article, Mr Johnson, and I am no wiser now than when I started'. -- `Possibly not, sir, but far better informed.'
hvirtanen@abo.fi (Harry Virtanen) (09/12/90)
In article <3728@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > In article <6921.26ebb2bb@abo.fi>, hvirtanen@abo.fi (Harry Virtanen) writes: >> I have recently been developing the theoretical foundations for a Fuzzy >> Prolog system, called LukLog, a connection between Lukasiewicz logic and >> logic programming. > >> LukLog is however built on the following functions/connectors >> a' = 1-a >> a^b = max(a+b-1,0) >> avb = max(a,b) >> a<-b = min(1-b+a,1) > > Would you care to say something about the relationship between "fuzzy" and > whichever of Lukasiewicz's logics you have in mind? The fact is, that I have allready written my thesis (master thesis I think it's called in english) that is simply called Fuzzy Prolog. The idea to the thesis comes from a preprint by Ulrich Hohle (1989): MONOIDAL CLOSED CATEGORIES, WEAK TOPOI, AND GENERALIZED LOGICS. He writes: "This paper is motivated by the problem of finding the categorial foundation of fuzzy set theory. Refering to Zadeh's pioneering paper on "fuzzy sets" (Information and Control 8 (1965) 338-358) it is evident that from a logical point of view fuzzy set theory is based on Lukasiewicz logic...........we are interested in a category C such that the logicla connectives of the [0,1]-valued Lukasiewicz logic appear as truth arrows in C..........." Motivation for max(a+b-1,0) for AND, a'=1-a for NOT and min(1-b+a,1) for a<-b are found in this paper. Another interesting paper is FUZZY INFERENCE IN A FORMAL THEORY OF SEMANTIC EQUIVALENCE by Daniel G. Schwartz (Fuzzy Sets and Systems 1989 volume ??). The paper studies several fuzzy implication operators including the Lukasiewicz operator min(1,1-a+b) (for a->b). > > For a system without negation, Udi Shapiro had a paper in a conference > years ago on logic programming with certainty factors. Basically, if > you have > head <-[f]- goal1 & ... & goaln > meaning > certainty(head) >= f(certainty(goal1), ..., certainty(goaln)) > where f is monotone (details spelled out in the paper), the usual > T^w(P) fixed point approach carries over just fine. The Shapiro paper: LOGIC PROGRAMS WITH UNCERTAINTIES: A TOOL FOR IMPLEMENTING RULE-BASED SYSTEMS (proc. 8th IJCAI 1983), is included in my references to my thesis. In my thesis I have also compared Mycin and Prolog/P (the swedish system, P, I think stands for Possibility) with my LukLog Approach. One of the conclusions is that both max(a+b-1,0) and min(a,b) have their pros and cons, but to my oppinion the max is preferable because it takes into consideration all the truth values in a clause. The min(a,b) operator cannot "see" changes of higher values when there is a constant min-value present in the body of the clause. The problem with max(a+b-1,0) is that it goes very fast towards zero. > > The really exciting thing about this is that *numeric* certainties > are (a) too limited and (b) too detailed: (b) people can never figure > out what the numbers are to be (whereas with a coarse classification > -- say four certainty levels, as used in some medical programs -- > they can often manage) but (a) when strange things go happen there isn't > enough information in the numbers to figure out _why_. Shapiro's approach > applies to *any* complete lattice used as a certainty space. (There isn't > the least reason for fuzzy logic to be confined to numbers. There was an > MSc thesis done at Auckland University Mathematics Department about 11 > years ago that generalised fuzzy stuff to other lattices.) It is very true that many people has a hard time understanding what these numbers (call them what you like: propabilites, possibilities, uncertainties, certainties or truth values) really are, and would prefere words like "true", "unlikely","likely","very likely" etc. > > After reading Shapiro's paper I started to write a paper on the > generalisation to other lattices, but someone from MIRU convinced > me that it was too trivial to be worth writing up. (There were some > interesting details about cutoffs when you haven't got numbers, but > alas, I've forgotten how I was going to solve the problem.) A question that is unanswered by my thesis, by the Shapiro paper and also by Istvan P. Orci (the man behind Prolog/P) is whether the resolution in Fuzzy Prolog is Sound and Complete. As Shapiro writes: "A less trivial exercise is to associate a transformation Tp with the program P, and to prove that the least fixpoint of Tp is M(P)" M(P)=The minimal model (or interpretation). > > Handling negation with certainty factors in something resembling Prolog > is going to be at least as hard as handling "simple" negation; I find it > incredible that doing something like > non G has certainty 1-X if G has certainty X > would work. Very true. To handle negation in this way is not the best. But everybody is using it !. There is of course the exception of (Dempster) Shafer's evidence theory, but then again, I don't think its ever been implemented. > >Surely you must be doing something much cleverer than that? I guess I'm not that clever after all, but I bet I would beat You in chess, which in turn would implicate that Your not that clever either !?? P.S. Talking about category theory, I just found a interesting article in LOGIC PROGRAMMING, proc. 6th int. conf., MIT press: PROJECTIONS INSTEAD OF VARIABLES, A CATEGORY THEORETIC INTERPRETATION OF LOGIC PROGRAMMING by Andrea Aperti and Simone Martini, 337-352. P.P.S. My "boss" Dr.Patrik Eklund has come up with an interesting idea: "...linking neural nets and LukLog we first interrelate the specification of uncertainty factors in implications with adaptation of synaptic weights................... .......... As a consequence, we can transform any net to a corresponding Lukasiewicz logic program". It's All Fuzzy To Me ! Harry Virtanen Abo Akademi University Department of Computer Science DataCity SF-20520 Turku Finland
mgv@usceast.UUCP (Marco Valtorta) (09/13/90)
In article <6925.26ee40ee@abo.fi> hvirtanen@abo.fi (Harry Virtanen) writes: >P.P.S. >My "boss" Dr.Patrik Eklund has come up with an interesting idea: "...linking >neural nets and LukLog we first interrelate the specification of uncertainty >factors in implications with adaptation of synaptic weights................... >.......... As a consequence, we can transform any net to a corresponding >Lukasiewicz logic program". That is indeed an interesting idea, but (partly, at least) not a new one. I think that several people had it independently. For example, I heard it while giving a talk on my work on the complexity of knowledge base refinement in 1988, when Terry Huntsberger told me that I had just shown him why back-propagation is slow. (I am now his colleague at USC, so his comments were helpful in more ways than one. :-) The person who has published the most about this is Li-Min Fu. You could start with his paper at IEA/AIE-90 [Fu, 1990] and work your way back. Also check my papers in IWML-89 and ICML-90 [Valtorta, 1989; 1990]. I guess I am biased when I say that it is an interesting idea! :-) > > > It's All Fuzzy To Me ! > >Harry Virtanen >Abo Akademi University >Department of Computer Science >DataCity >SF-20520 Turku >Finland REFERENCES Fu, Li-Min. "Recognition of Semantic Incorrect Rules: A Neural-network Approach." _Proceedings of the Third International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE-90)_, pp. 1013-1018. Valtorta, Marco. "Some Results on the Complexity of Knowledge Base Refinement." _Proceedings of the Sixth International Workshop on Machine Learning (IWML-89)_, pp. 326-331. Valtorta, Marco. "More Results on the Complexity of Knowledge Base Refinement: Belief Networks." _Proceedings of the Seventh International Conference on Machine Learning (ICML-90)_, pp. 419-426. Marco Valtorta usenet: ...!ncrcae!usceast!mgv Department of Computer Science internet: mgv@cs.scarolina.edu University of South Carolina tel.: (1)(803)777-4641 Columbia, SC 29208 tlx: 805038 USC U.S.A. fax: (1)(803)777-3065 usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv P.S. I would like to obtain a copy of your thesis. How can I do that? (Please answer by e-mail.)
jwmills@iuvax.cs.indiana.edu (Jonathan Mills) (09/15/90)
In article <6921.26ebb2bb@abo.fi> hvirtanen@abo.fi (Harry Virtanen) writes: >I'm planning to present a paper (if accepted) on this subject at the IFSA 91' >Brussels congress. Any comments, or information on other existing Fuzzy Prolog >systems are welcome (personal mail or in this newsgroup). It would be interesting to consider the architectures that might support your language. If evaluation of Lukasiewicz sentences plays a significant part in the execution of LukLog programs, you might find that the analog VLSI Lukasiewicz logic arrays implemented at Indiana University could be used in a hybrid machine. I have been more interested in defining applications of these arrays to connectionist networks, fuzzy controllers and expert systems. Languages for hybrid systems integrating connectionism & logic programming may also be possible, using sentence schema in Lukasiewicz logic as targets for network descriptions. To answer Richard's question, the VLSI LLAs are continuous-valued theoretically, but can be resolved to L(64) in the current test set-up (6 bits of precision). Lukasiewicz logic connects a number of computational paradigms, and offers a means to approach analog computation logically. McNaughton noted the relationship between Lukasiewicz logic and polynomial curves approximated by linear segments ("A theorem about infinite-valued sentential logic," Journal of Symbolic Logic, Vol 16, pp. 1-13, 1951). Robin Giles has published a series of papers from 1976 to 1985 discussing the relationships between Lukasiewicz logic, fuzzy logic, and a game-theoretic approach to truth. His most recent paper, "A resolution logic for fuzzy reasoning" appeared in the 1985 Proceedings of the IEEE 17th International Symposium on Multiple-Valued Logic. Lukasiewicz logic arrays are described in a paper of that title by Mills, Daffinger and Beavers in the Proceedings of the 20th IEEE Symposium on Multiple-valued Logic. A discussion of the use of both the algebraic and logical operational semantics of LLAs appeared as "An Analog VLSI Array Processor for Classical and Connectionist AI," in the Proceedings of the 1990 Conference on Application-specific Array Processors. Fuzzy Prologs are certainly interesting, but Lukasiewicz logic offers a novel approach to extending Kowalski's paradigm, "algorithm = logic + control" to other areas of AI, as well as developing languages and/or compilation techniques for analog and hybrid processors.