|Norvig I 566
Change/probability/time/inference/AI research/Norvig/Russell: Agents in partially observable environments must be able to keep track of the current state, to the extent that their sensors allow. (…) an agent maintains a belief state that represents which states of the world are currently possible. >Belief states/Norvig.
From the belief state and a transition model, the agent can predict how the world might evolve in the next time step. From the percepts observed and a sensor model, the agent can update the belief state.
[There are two ways of representing belief states] (…)
a) by explicitly enumerated sets of states,
b) by logical formulas. Those approaches defined belief states in terms of which world states were possible, but could say nothing about which states were likely or unlikely.
Problem: a changing world is modeled using a variable for each aspect of the world state at each point in time. The transition and sensor models may be uncertain: the transition model describes the probability distribution of the variables at time t, given the state of the world at past times, while the sensor model describes the probability of each percept at time t, given the current state of the world.
Solution: three specific kinds of models: hidden Markov models, Kalman filters, and dynamic Bayesian networks (which include hidden Markov models and Kalman filters as special cases).
Norvig I 567
To assess the current state from the history of evidence and to predict the outcomes of treatment actions, we must model these changes.
We view the world as a series of snapshots, or time slices, each of which contains a set of random variables, some observable and some not. ((s) Cf. >Four dimensionalism/Philosophical theories).
Norvig I 568
(…) the next step is to specify how the world evolves (the transition model) and how the evidence variables get their values (the sensor model).
Norvig I 570
Order: increasing the order can always be reformulated as an increase in the set of state variables, keeping the order fixed. Notice that adding state variables might improve the system’s predictive power but also increases the prediction requirements (…).
Norvig I 603
Problem: data association: When trying to keep track of many objects, uncertainty arises as to which observations belong to which objects—the data association problem. The number of association hypotheses is typically intractably large, but MCMC and particle filtering algorithms for data association work well in practice.
Norvig I 602
MCMC: An MCMC algorithm explores the space of assignment histories.
Norvig I 603
Change: The changing state of the world is handled by using a set of random variables to represent the state at each point in time.
Representations: can be designed to satisfy the Markov property, so that the future is independent of the past given the present. Combined with the assumption that the process is stationary—that is, the dynamics do not change over time—this greatly simplifies the representation.
Probability: A temporal probability model can be thought of as containing a transition model describing the state evolution and a sensor model describing the observation process. >Inference/AI research.
Historical development: Many of the basic ideas for estimating the state of dynamical systems came from the mathematician C. F. Gauss (1809)(1), who formulated a deterministic least-squares algorithm for the problem of estimating orbits from astronomical observations. A. A. Markov (1913)(2) developed what was later called the Markov assumption in his analysis of stochastic processes;
Norvig I 604
(…). The general theory of Markov chains and their mixing times is covered by Levin et al. (2008)(3). Significant classified work on filtering was done during World War II by Wiener (1942)(4) for continuous-time processes and by Kolmogorov (1941)(5) for discrete-time processes. Although this work led to important technological developments over the next 20 years, its use of a frequency-domain representation made many calculations quite cumbersome. Direct state-space modeling of the stochastic process turned out to be simpler, as shown by Peter Swerling (1959)(6) and Rudolf Kalman (1960)(7).
The hidden Markov model and associated algorithms for inference and learning, including the forward–backward algorithm, were developed by Baum and Petrie (1966)(8). The Viterbi algorithm first appeared in (Viterbi, 1967)(9). Similar ideas also appeared independently in the Kalman filtering community (Rauch et al., 1965)(10). The forward–backward algorithm was one of the main precursors of the general formulation of the EM algorithm (Dempster et al., 1977)(11) (…).
Dynamic Bayesian networks (DBNs) can be viewed as a sparse encoding of a Markov process and were first used in AI by Dean and Kanazawa (1989b)(12), Nicholson and Brady (1992)(13), and Kjaerulff (1992)(14). The last work extends the HUGIN Bayes net system to accommodate dynamic Bayesian networks. The book by Dean and Wellman (1991)(15) helped popularize DBNs and the probabilistic approach to planning and control within AI. Murphy (2002)(16) provides a thorough analysis of DBNs. Dynamic Bayesian networks have become popular for modeling a variety of complex motion processes in computer vision (Huang et al., 1994(17); Intille and Bobick, 1999)(18).
Like HMMs, they have found applications in speech recognition (Zweig and Russell, 1998(19)); Richardson et al., 2000(20); Stephenson et al., 2000(21); Nefian et al., 2002(22); Livescu et al., 2003(23)),
Norvig I 605
genomics (Murphy and Mian, 1999(24); Perrin et al., 2003(25); Husmeier, 2003(26)) and robot localization (Theocharous et al., 2004)(27). The link between HMMs and DBNs, and between the forward–backward algorithm and Bayesian network propagation, was made explicitly by Smyth et al. (1997)(28). A further unification with Kalman filters (and other statistical models) appears in Roweis and Ghahramani (1999)(29). Procedures exist for learning the parameters (Binder et al., 1997a(30); Ghahramani, 1998)(31) and structures (Friedman et al., 1998)(32) of DBNs.
Norvig I 606
Data association: Data association for multi target tracking was first described in a probabilistic setting by Sittler (1964)(33). The first practical algorithm for large-scale problems was the “multiple hypothesis tracker” or MHT algorithm (Reid, 1979)(34). Many important papers are collected by Bar-Shalom and Fortmann (1988)(35) and Bar-Shalom (1992)(36). The development of an MCMC algorithm for data association is due to Pasula et al. (1999)(37), who applied it to traffic surveillance problems. Oh et al. (2009)(38) provide a formal analysis and extensive experimental comparisons to other methods. Schulz et al. (2003)(39) describe a data association method based on particle filtering. Ingemar Cox analyzed the complexity of data association (Cox, 1993(40); Cox and Hingorani, 1994(41)) and brought the topic to the attention of the vision community. He also noted the applicability of the polynomial-time Hungarian algorithm to the problem of finding most-likely assignments, which had long been considered an intractable problem in the tracking community. The algorithm itself was published by Kuhn (1955)(42), based on translations of papers published in 1931 by two Hungarian mathematicians, Dénes König and Jenö Egerváry. The basic theorem had been derived previously, however, in an unpublished Latin manuscript by the famous Prussian mathematician Carl Gustav Jacobi (1804–1851).
1. Gauss, C. F. (1829). Beiträge zur Theorie der algebraischen Gleichungen. Collected in Werke,
Vol. 3, pages 71–102. K. Gesellschaft Wissenschaft, Göttingen, Germany, 1876.
2. Markov, A. A. (1913). An example of statistical investigation in the text of “Eugene Onegin” illustrating coupling of “tests” in chains. Proc. Academy of Sciences of St. Petersburg, 7.
3. Levin, D. A., Peres, Y., and Wilmer, E. L. (2008). Markov Chains and Mixing Times. American Mathematical Society.
4. Wiener, N. (1942). The extrapolation, interpolation, and smoothing of stationary time series. Osrd 370, Report to the Services 19, Research Project DIC-6037, MIT.
5. Kolmogorov, A. N. (1941). Interpolation und Extrapolation von stationären zufälligen Folgen. Bulletin of the Academy of Sciences of the USSR, Ser. Math. 5, 3–14.
6. Swerling, P. (1959). First order error propagation in a stagewise smoothing procedure for satellite observations. J. Astronautical Sciences, 6, 46–52.
7. Kalman, R. (1960). A new approach to linear filtering and prediction problems. J. Basic Engineering, 82, 35–46.
8. Baum, L. E. and Petrie, T. (1966). Statistical inference for probabilistic functions of finite state Markov chains. Annals of Mathematical Statistics, 41.
9. Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, 13(2), 260–269.
10. Rauch, H. E., Tung, F., and Striebel, C. T. (1965). Maximum likelihood estimates of linear dynamic systems. AIAA Journal, 3(8), 1445–1450.
11. Dempster, A. P., Laird, N., and Rubin, D. (1977). Maximum likelihood from incomplete data via the
EM algorithm. J. Royal Statistical Society, 39 (Series B), 1–38.
12. Dean, T. and Kanazawa, K. (1989b). A model for reasoning about persistence and causation. Computational Intelligence, 5(3), 142–150.
13. Nicholson, A. and Brady, J. M. (1992). The data association problem when monitoring robot vehicles using dynamic belief networks. In ECAI-92, pp. 689–693.
14. Kjaerulff, U. (1992). A computational scheme for reasoning in dynamic probabilistic networks. In
UAI-92, pp. 121–129.
15. Dean, T. and Wellman, M. P. (1991). Planning and Control. Morgan Kaufmann.
16. Murphy, K. (2002). Dynamic Bayesian Networks: Representation, Inference and Learning. Ph.D. thesis, UC Berkeley
17. Huang, T., Koller, D., Malik, J., Ogasawara, G., Rao, B., Russell, S. J., and Weber, J. (1994). Automatic symbolic traffic scene analysis using belief networks. In AAAI-94, pp. 966–972
18. Intille, S. and Bobick, A. (1999). A framework for recognizing multi-agent action from visual evidence. In AAAI-99, pp. 518-525.
19. Zweig, G. and Russell, S. J. (1998). Speech recognition with dynamic Bayesian networks. In AAAI-98, pp. 173–180.
20. Richardson, M., Bilmes, J., and Diorio, C. (2000). Hidden-articulator Markov models: Performance improvements and robustness to noise. In ICASSP-00.
21. Stephenson, T., Bourlard, H., Bengio, S., and Morris, A. (2000). Automatic speech recognition using
dynamic bayesian networks with both acoustic and articulatory features. In ICSLP-00, pp. 951-954.
22. Nefian, A., Liang, L., Pi, X., Liu, X., and Murphy, K. (2002). Dynamic bayesian networks for audiovisual speech recognition. EURASIP, Journal of Applied Signal Processing, 11, 1–15.
23. Livescu, K., Glass, J., and Bilmes, J. (2003). Hidden feature modeling for speech recognition using dynamic Bayesian networks. In EUROSPEECH-2003, pp. 2529-2532
24. Murphy, K. and Mian, I. S. (1999). Modelling gene expression data using Bayesian networks.
25. Perrin, B. E., Ralaivola, L., and Mazurie, A. (2003).
Gene networks inference using dynamic Bayesian networks. Bioinformatics, 19, II 138-II 148.
26. Husmeier, D. (2003). Sensitivity and specificity of inferring genetic regulatory interactions from microarray experiments with dynamic bayesian networks. Bioinformatics, 19(17), 2271-2282.
27. Theocharous, G., Murphy, K., and Kaelbling, L. P. (2004). Representing hierarchical POMDPs as
DBNs for multi-scale robot localization. In ICRA-04.
28. Smyth, P., Heckerman, D., and Jordan, M. I. (1997). Probabilistic independence networks for hidden Markov probability models. Neural Computation, 9(2), 227-269.
29. Roweis, S. T. and Ghahramani, Z. (1999). A unifying review of Linear GaussianModels. Neural Computation, 11(2), 305-345.
30. Binder, J., Koller, D., Russell, S. J., and Kanazawa, K. (1997a). Adaptive probabilistic networks with hidden variables. Machine Learning, 29, 213-244.
31. Ghahramani, Z. (1998). Learning dynamic bayesian networks. In Adaptive Processing of Sequences
and Data Structures, pp. 168–197.
32. Friedman, N., Murphy, K., and Russell, S. J. (1998). Learning the structure of dynamic probabilistic
networks. In UAI-98.
33. Sittler, R. W. (1964). An optimal data association problem in surveillance theory. IEEE Transactions on Military Electronics, 8(2), 125-139.
34. Reid, D. B. (1979). An algorithm for tracking multiple targets. IEEE Trans. Automatic Control, 24(6), 843–854.
35. Bar-Shalom, Y. and Fortmann, T. E. (1988). Tracking and Data Association. Academic Press.
36. Bar-Shalom, Y. (Ed.). (1992). Multi target multi sensor tracking: Advanced applications. Artech House.
37. Pasula, H., Russell, S. J., Ostland, M., and Ritov, Y. (1999). Tracking many objects with many sensors. In IJCAI-99.
38. Oh, S., Russell, S. J., and Sastry, S. (2009). Markov chain Monte Carlo data association for multi-target tracking. IEEE Transactions on Automatic Control, 54(3), 481-497.
39. Schulz, D., Burgard, W., Fox, D., and Cremers, A. B. (2003). People tracking with mobile robots
using sample-based joint probabilistic data association filters. Int. J. Robotics Research, 22(2), 99-116
40. Cox, I. (1993). A review of statistical data association techniques for motion correspondence. IJCV, 10, 53–66.
41 Cox, I. and Hingorani, S. L. (1994). An efficient implementation and evaluation of Reid’s multiple hypothesis tracking algorithm for visual tracking. In ICPR-94, Vol. 1, pp. 437-442.
42. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics
Quarterly, 2, 83-97._____________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