|Inferences: when we move from premises to conclusions we carry out inferences. _____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. |
|Norvig I 471
Reasoning/inference/artificial intelligence/AI research/Norvig/Russell: The three main formalisms for dealing with nonmonotonic inference—circumscription (McCarthy, 1980)(1), default logic (Reiter, 1980(2)), and modal nonmonotonic logic (McDermott and Doyle, 1980)(3) - were all introduced in one special issue of the AI Journal. Delgrande and Schaub (2003)(4) discuss the merits of the variants, given 25 years of hindsight.
Answer set programming can be seen as an extension of negation as failure or as a refinement of circumscription;
Norvig I 472
the underlying theory of stable model semantics was introduced by Gelfond and Lifschitz (1988)(5), and the leading answer set programming systems are DLV (Eiter et al., 1998)(6) and SMODELS (Niemel¨a et al., 2000)(7). The disk drive example comes from the SMODELS user manual (Syrjanen, 2000)(8). Lifschitz (2001)(9) discusses the use of answer set programming for planning. Brewka et al. (1997)(10) give a good overview of the various approaches to nonmonotonic logic. Clark (1978)(11) covers the negation-as-failure approach to logic programming and Clark completion. Van Emden and Kowalski (1976)(12) show that every Prolog program without negation has a unique minimal model. Recent years have seen renewed interest in applications of nonmonotonic logics to large-scale knowledge representation systems.
The BENINQ systems for handling insurance-benefit inquiries was perhaps the first commercially successful application of a nonmonotonic inheritance system (Morgenstern, 1998)(13). Lifschitz (2001)(9) discusses the application of answer set programming to planning.
Norvig I 473
Spatial reasoning: The earliest serious attempt to capture commonsense reasoning about space appears in the work of Ernest Davis (1986(14), 1990(15)). The region connection calculus of Cohn et al. (1997)(16) supports a form of qualitative spatial reasoning and has led to new kinds of geographical information systems; see also (Davis, 2006)(17). As with qualitative physics, an agent can go a long way, so to speak, without resorting to a full metric representation.
Psychological reasoning: Psychological reasoning involves the development of a working psychology for artificial agents to use in reasoning about themselves and other agents. This is often based on so-called folk psychology, the theory that humans in general are believed to use in reasoning about themselves and other humans. ((s) Cf. >Folk psychology/Philosophical theories).
When AI researchers provide their artificial agents with psychological theories for reasoning about other agents, the theories are frequently based on the researchers’ description of the logical agents’ own design. Psychological reasoning is currently most useful within the context of natural language understanding, where divining the speaker’s intentions is of paramount importance. Minker (2001)(18) collects papers by leading researchers in knowledge representation, summarizing 40 years of work in the field. The proceedings of the international conferences on Principles of Knowledge Representation and Reasoning provide the most up-to-date sources for work in this area.
1. McCarthy, J. (1980). Circumscription: A form of non-monotonic reasoning. AIJ, 13(1–2), 27–39.
2. Reiter, R. (1980). A logic for default reasoning. AIJ, 13(1–2), 81–132.
3. McDermott, D. and Doyle, J. (1980). Nonmonotonic logic: i. AIJ, 13(1–2), 41–72.
4. Delgrande, J. and Schaub, T. (2003). On the relation between Reiter’s default logic and its (major) variants. In Seventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, pp. 452–463.
5. Gelfond, M. and Lifschitz, V. (1988). Compiling circumscriptive theories into logic programs. In Non-
Monotonic Reasoning: 2nd International Workshop Proceedings, pp. 74–99.
6. Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. (1998). The KR system dlv: Progress report, comparisons and benchmarks. In KR-98, pp. 406–417.
7. Niemela, I., Simons, P., and Syrjanen, T. (2000). Smodels: A system for answer set programming.
In Proc. 8th International Workshop on Non-Monotonic Reasoning.
8. Syrjanen, T. (2000). Lparse 1.0 user’s manual.saturn.tcs.hut.fi/Software/smodels.
9. Lifschitz, V. (2001). Answer set programming and plan generation. AIJ, 138(1–2), 39–54.
10. Brewka, G., Dix, J., and Konolige, K. (1997). Nononotonic Reasoning: An Overview. CSLI Publications.
11. Clark, K. L. (1978). Negation as failure. In Gallaire, H. and Minker, J. (Eds.), Logic and Data Bases, pp. 293–322. Plenum.
12. Van Emden, M. H. and Kowalski, R. (1976). The semantics of predicate logic as a programming language. JACM, 23(4), 733–742.
13. Morgenstern, L. (1998). Inheritance comes of age: Applying nonmonotonic techniques to problems in industry. AIJ, 103, 237–271
14. Davis, E. (1986). Representing and Acquiring Geographic Knowledge. Pitman and Morgan Kaufmann.
15. Davis, E. (1990). Representations of Commonsense Knowledge. Morgan Kaufmann
16. Cohn, A. G., Bennett, B., Gooday, J. M., and Gotts, N. (1997). RCC: A calculus for region based qualitative spatial reasoning. GeoInformatica, 1, 275–316.
17. Davis, E. (2006). The expressivity of quantifying over regions. J. Logic and Computation, 16, 891–
18. Minker, J. (2001). Logic-Based Artificial Intelligence. Kluwer
- - -
Norvig I 570
Inference/temporal models/AI research/Norvig/Russell: (…) the basic inference tasks that must be solved:
a) Filtering: This is the task of computing the belief state—the posterior distribution over the most recent state - given all evidence to date. Filtering is also called state estimation. >Belief states/Norvig.
b) Prediction: This is the task of computing the posterior distribution over the future state, given all evidence to date. That is, we wish to compute P(Xt+k | e1:t) for some k > 0.
Norvig I 571
c) Smoothing: This is the task of computing the posterior distribution over a past state, given all evidence up to the present. That is, we wish to compute P(Xk | e1:t) for some k such that 0 ≤ k < t.
d) Most likely explanation: Given a sequence of observations, we might wish to find the sequence of states that is most likely to have generated those observations. That is, we wish to compute argmaxx1:t P(x1:t | e1:t).
In addition to these inference tasks (…):
Learning: The transition and sensor models, if not yet known, can be learned from observations. Just as with static >Bayesian networks, dynamic Bayes net learning can be done as a by-product of inference. Inference provides an estimate of what transitions actually occurred and of what states generated the sensor readings, and these estimates can be used to update the models. >Change/AI research, >Uncertainty/AI research.
Norvig I 605
Ad a) The particle filtering algorithm (…) has a particularly interesting history. The first sampling algorithms for particle filtering (also called sequential Monte Carlo methods) were developed in the control theory community by Handschin and Mayne (1969)(1), and the resampling idea that is the core of particle filtering appeared in a Russian control journal (Zaritskii et al., 1975)(2). It was later reinvented in statistics as sequential importance sampling resampling, or SIR (Rubin, 1988(3); Liu and Chen, 1998(4)), in control theory as particle filtering (Gordon et al., 1993(5); Gordon, 1994(6)), in AI as survival of the fittest (Kanazawa et al., 1995)(7), and in computer vision as condensation (Isard and Blake, 1996)(8). The paper by Kanazawa et al. (1995)(7) includes an improvement called evidence reversal whereby the state at time t+1 is sampled conditional on both the state at time t and the evidence at time t+1. This allows the evidence to influence sample generation directly and was proved by Doucet (1997)(9) and Liu and Chen (1998)(4) to reduce the approximation error.
Particle filtering has been applied in many areas, including tracking complex motion patterns in video (Isard and Blake, 1996)(8), predicting the stock market (de Freitas et al., 2000)(10), and diagnosing faults on planetary rovers (Verma et al., 2004)(11). A variant called the Rao-Blackwellized particle filter or RBPF (Doucet et al., 2000(12); Murphy and Russell, 2001)(13) applies particle filtering to a subset of state variables and, for each particle, performs exact inference on the remaining variables conditioned on the value sequence in the particle. In some cases RBPF works well with thousands of state variables. >Utility/AI research, >Utility theory/Norvig, >Rationality/AI research, >Certainty ffect/Kahneman/Tversky, >Ambiguity/Kahneman/Tversky.
1. Handschin, J. E. and Mayne, D. Q. (1969). Monte Carlo techniques to estimate the conditional expectation in multi-stage nonlinear filtering. Int. J. Control, 9(5), 547–559.
2. Zaritskii, V. S., Svetnik, V. B., and Shimelevich, L. I. (1975). Monte-Carlo technique in problems of
optimal information processing. Automation and Remote Control, 36, 2015–22.
3. Rubin, D. (1988). Using the SIR algorithm to simulate posterior distributions. In Bernardo, J. M.,
de Groot,M. H., Lindley, D. V., and Smith, A. F. M. (Eds.), Bayesian Statistics 3, pp. 395–402. Oxford
4. Liu, J. S. and Chen, R. (1998). Sequential Monte Carlo methods for dynamic systems. JASA, 93,
5. Gordon, N., Salmond, D. J., and Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian
Bayesian state estimation. IEE Proceedings F (Radar and Signal Processing), 140(2), 107–113.
6. Gordon, N. (1994). Bayesian methods for tracking. Ph.D. thesis, Imperial College.
7. Kanazawa, K., Koller, D., and Russell, S. J. (1995). Stochastic simulation algorithms for dynamic probabilistic networks. In UAI-95, pp. 346–351.
8. Isard, M. and Blake, A. (1996). Contour tracking by stochastic propagation of conditional density. In
ECCV, pp. 343–356.
9. Doucet, A. (1997). Monte Carlo methods for Bayesian estimation of hidden Markov models: Application to radiation signals. Ph.D. thesis, Université de Paris-Sud.
10. de Freitas, J. F. G., Niranjan, M., and Gee, A. H. (2000). Sequential Monte Carlo methods to train neural network models. Neural Computation, 12(4), 933–953.
11. Verma, V., Gordon, G., Simmons, R., and Thrun, S. (2004). Particle filters for rover fault diagnosis.
IEEE Robotics and Automation Magazine, June.
12. Doucet, A., de Freitas, N., Murphy, K., and Russell, S. J. (2000). Rao-blackwellised particle filtering for dynamic bayesian networks. In UAI-00.
13. Murphy, K. and Russell, S. J. (2001). Rao-blackwellised particle filtering for dynamic Bayesian networks. In Doucet, A., de Freitas, N., and Gordon, N. J. (Eds.), Sequential Monte Carlo Methods in Practice. Springer-Verlag._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010