Date: Thu 31 Mar 1988 23:23-PST From: AIList Moderator Kenneth Laws Reply-To: AIList@KL.SRI.COM Us-Mail: SRI Int., 333 Ravenswood Ave., Menlo Park, CA 94025 Phone: (415) 859-6467 Subject: AIList V6 #63 - Future of AI, Evidential Reasoning To: AIList@KL.SRI.COM Status: RO AIList Digest Friday, 1 Apr 1988 Volume 6 : Issue 63 Today's Topics: Administrivia - Slight Delay Review - The Ecology of Computation, Opinion - The Future of AI, Theory - On the D/S Theory of Evidence ---------------------------------------------------------------------- Date: Thu 31 Mar 88 22:50:53-PST From: Ken Laws Reply-to: AIList-Request@SRI.COM Subject: Administrivia - Slight Delay There will be a delay of about a week before the next AIList issue is posted. -- Ken ------------------------------ Date: Tue, 29 Mar 88 11:51:02 PST From: Ken Kahn Subject: The Ecology of Computation A new book entitled "The Ecology of Computation" editted by B.A. Huberman has just been published by North-Holland. The collection includes papers by Huberman, Hewitt, Lenat, Brown, Miller, Drexler, Hogg, Rosenschein, Genesereth, Malone, Fikes, Grant, Howard, Rashid, Liskov, Scheifler, Kahn, and Stefik. Its the first collection of papers about open systems (very large scale distributed systems) and several of the papers make important connections to AI. ------------------------------ Date: 29 Mar 88 09:55:31 GMT From: otter!cwp@hplabs.hp.com (Chris Preist) Subject: Re: The future of AI [was Re: Time Magazine -- Computers of the Future] Whatever the future of AI is, it's almost certainly COMPANY CONFIDENTIAL! :-) Chris Disclaimer: In this case, the opinion expressed probably IS the opinion of my employer! ------------------------------ Date: 29 Mar 88 17:02:39 GMT From: ssc-vax!bcsaic!rwojcik@beaver.cs.washington.edu (Rick Wojcik) Subject: Re: The future of AI [was Re: Time Magazine -- Computers of the Future] In article <962@daisy.UUCP> klee@daisy.UUCP (Ken Lee) writes: > >Is AI just too expensive and too complicated for practical use? I >spent 3 years in the field and I'm beginning to think the answer is >mostly yes. In my opinion, all working AI programs are either toys or >could have been developed much more cheaply using conventional >techniques. > Your posting was clearly intended to provoke, but I'll try to keep the flames low :-). Please try to remember that AI is a vast subject area. It is expensive because it requires a great deal of expertise in language, psychology, philosophy, etc.--not just programming skills. It is also a very high risk area, as anyone can see. But the payoff can be tremendous. Moreover, your opinion that conventional techniques can replace AI is ludicrous. Consider the area of natural language. What conventional techniques that you know of can extract information from natural language text or translate a passage from English to French? Maybe you believe that we should stop all research on robotics. If not, would you like to explain how conventional programming can be used get robots to see objects in the real world? But maybe we should give up on the whole idea. We can replace robots with humans. Would you like to volunteer for the bomb squad :-)? In the development stage, AI is expensive, but in the long term it is cost effective. Your pessimism about the field seems to be based on the failure of expert systems to live up to the hype. The future of AI is going to be full of unrealistic hype and disappointing failures. But the demand for AI is so great that we have no choice but to push on. -- Rick Wojcik csnet: rwojcik@boeing.com uucp: {uw-june uw-beaver!ssc-vax}!bcsaic!rwojcik address: P.O. Box 24346, MS 7L-64, Seattle, WA 98124-0346 phone: 206-865-3844 ------------------------------ Date: 29 Mar 88 14:24:11 GMT From: otter!cdfk@hplabs.hp.com (Caroline Knight) Subject: Re: The future of AI [was Re: Time Magazine -- Computers of the Future] Whatever the far future uses of AI are we can try to make the current uses as humane and as ethical as possible. I actually believe that AI in its current form should complement humans not make them redundant. It should increase the skill of the person doing the job by doing those things which are boring or impractical for humans but possible for computers. This is the responsibility mostly of people doing applications but can also form the focus of research. When sharing a job with a computer which tasks are best automated and which best given to the human - not just which is it possible to automate! Then the research can move on to how to automate those that it is desirable to have autmoated instead of simply trying to show how clever we all are in mimicking "intelligence". Perhaps computers will free people up so that they can go back to doing some of the tasks that we currently have machines do - has anyone thought of it that way? And if we are going to do people out of jobs then we'd better start understanding that a person is still valuable even if they do not do "regular work". How can AI actually improve life for those that are made jobless by it? Can we improve on previous revolutions by NOT treading rough shod over the people that are displaced? Either that or prepare to give up our world to the machines - perhaps thats why we are not looking after it very carefully! Caroline Knight What I say is said on my own behalf - it is not a statement of company policy. ------------------------------ Date: Wed, 30 Mar 88 20:51:06 EST From: Bob Hummel Subject: On the D/S Theory of Evidence Reading the renewed discussion on the meaning of various calculi of uncertainty reasoning prompts me to inject a note on the Dempster/Shafer formalism. I will summarize a few observations here, but direct interested readers to a joint paper with Michael Landy, which appeared this month in IEEE Pattern Analysis and Machine Intelligence [1]. These observations were inspired, oddly enough, by reading Dempster's original paper, in which he introduces the now-famous combination formula [2]. It seems logical that the original source should contain the motiva- tion and interpretation of the formula. But what is odd is that the interpretation migrated over the years, and that the clear, logical founda- tions became obscure. There have been numerous attempts to reconstruct an explanation of the true meaning of the belief values and the normalization terms and the combination method in the Dempster/Shafer work. Some of these attempts succeed reasonably well. Along these lines, I think the best work is represented by Kyberg's treatment in terms of extrema over collections of opinions [3], and Ruspini's work connecting Dempster/Shafer formalism to Bayesian analysis [4]. Shafer also constructs what he calls a "canonical example" which is supposed to be used as a scale to invoke degrees of belief into general situations, based on "coded messages." The idea, described for example in [5], is isomorphic to the observations made here and in [1] based on the foundations laid by Dempster [2]. The problem is that none of these interpretations lead to generalizations and explain the precise intent of the original formulation. Before giving the succinct interpretation, which, it turns out, is a statistical formulation, I should comment briefly on the compatibility of the various interpretations. When lecturing on the topic, I have often encountered the attitude that the statistical viewpoint is simply one interpretation, limited in scope, and not very helpful. The feeling is that we should be willing to view the constructs in some sort of general way, so as to be able to map the formalism onto more general applications. Here, I believe, is one source of the stridency: that if I would only per- mit myself to view certain values as subjective degrees of belief in anal- ogy with some mystical frame of reference, then I will see why certain arguments make perfectly logical sense. Accordingly, our treatment of the statistical viewpoint is introduced in the framework of algebraic struc- tures, and our results are based on proving an isomorphism between an easily interpreted algebraic structure and the structure induced by the Dempster rule of combination acting on states of belief. So when I use the terms "experts" and "opinions" and related terms below, an alternate interpretation might easily use different concepts. However, any interpre- tation that truly captures the Dempster/Shafer calculus must necessarily be isomorphic, under some mapping identifying corresponding concepts, to the interpretation given here. Here is the formulation. Consider a frame of discernment, here denoted S. Instead of giving a probability distribution over S, we con- sider a collection of experts, say E, where each expert e in E gives an opinion. The opinions are boolean, which is to say that expert e declares which labels in S are possible, and which are ruled out. For the combination formula, suppose we have two collections of experts, E1 and E2. Each expert in E1 and each expert in E2 expresses an opinion, in a boolean fashion, over the labels in S. (An important point is that the frame of discernment S is the same for all collections of experts). We now wish to combine the two collections of experts. We con- sider the cross product E1 X E2, which is the set of all committees of two, with a pair of experts comprised of one expert from E1 and one expert from E2. For any such committee, say (e1,e2), we define the committee's boolean opinion to be the logical intersection of the two composing opinions. Thus the committee says that a label is possible only if both committee members say that the label is possible. We regard the collection of all such com- mittees and their opinions to be a new collection of experts E, with their boolean opinions. We have defined an algebraic structure. Call it the the "Boolean opinions of Experts." The elements of this space consist of pairs (E,f), where E is a collection of experts, and f is their opinions, formed as a map from E to a vector of boolean statements about the labels in S. Now define an equivalence relation. We will say that two such elements are equivalent if the statistics over the collections of experts, among those experts giving at least one possibility, are the same. By the statistics, we mean the following. Let E' be the subset of experts in E for whom at least one label is possible. For any given subset A of S, let m(A) be the percentage of experts in E' that designate precisely A as the subset of possible labels. Note that m of the empty set is 0, by the definition of E', and that m forms a probability distribution over the power set of S. It turns out that m is a mass function, used to define a belief state on S. Further, when sets of experts combine, the statistics, represented by the corresponding m functions, combine in exactly the Dempster rule of combination. (This is no accident. This is the way Dempster defined it.) Accordingly, the set of equivalence classes in the space of "Boolean opinions of Experts" is isomorphic to the Dempster/Shafer formalism, represented as a space of belief states formed by mass distributions m. Some people express disappointment in the Dempster/Shafer theory, when it is viewed this way. For example, it should be noted that no where does the theory make use of probabilities of the labels. The theory makes no distinction between an expert's opinion that a label is likely or that it is remotely possible. This is despite the fact that the belief values seem to give weighted results. Instead, the belief in a particular subset A, it can be shown, corresponds to the fraction of experts in E' who state that every label outside of A is impossible. The weighted values come about by maintaining multiple boolean opinions, instead of one single weighted opin- ion. In the PAMI paper, Mike Landy and I suggest an extension [1], where we track the statistics of probabilistic opinions. In this formulation, we track the mean and covariance of the log's of probabilistic opinions. Details are in Section 5 of the paper. In a follow-on paper [6], presented at the 1987 IJCAI, Larry Manevitz and I extend the formulation to weaken the necessary notion of independence of information. It is always true that some independence assumption is necessary. Larry and I defined a one-parameter measure of a degree of dependence, and show how the formulas tracking means and covariances are transformed. We also consider a case where we combine bodies of experts by union, as opposed to cross product. To those who study these extensions, it will become clear that the formulas bear some resemblance to treatments of uncertainty based on Kalman filtering. For specific applications involving the observation of data and the estimation of parameters, the Kalman theory is certainly to be recom- mended if it can be applied. Robert Hummel Courant Institute New York University References 1. Hummel, Robert A. and Michael S. Landy, "A statistical viewpoint on the theory of evidence," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 235-247 (1988). 2. Dempster, A. P., "Upper and lower probabilities induced by a mul- tivalued mapping," Annals of Mathematical Statistics Vol. 38 pp. 325- 339 (1967). 3. Kyburg, Jr., Henry E., "Bayesian and non-bayesian evidential updat- ing," University of Rochester Dept. of Computer Science Tech. Rep. 139 (July, 1985). 4. Ruspini, E., Proceedings of the International Joint Conference on Artificial Intelligence, (August, 1987). Also SRI Technical Note 408. 5. Shafer, Glenn, "Belief functions and parametric models," Journal of the Royal Statistical Society B Vol. 44 pp. 322-352 (1982). (Includes commentaries). 6. Hummel, Robert and Larry Manevitz, "Combining bodies of dependent information," Tenth International Joint Conference on Artificial Intelligence, (August, 1987). ------------------------------ End of AIList Digest ********************