ACM Comm 2015 07 Unifying Logic and Probability (Notes)

From University
Jump to: navigation, search
"Exascale Computing and Big Data" CACM July 2015

Unifying Logic and Probability
by Stuart Russell, p.88-97

Unifying Logic and Probability

"Open-universe probability models show merit in unifying efforts."
the real world is uncertain and has things in it.
MutantOS is uncertain and has things in it.

People

  1. Judea Pearl[1]
  2. Haim Gaifman[2]
  3. Jan Łukasiewicz[3]
  4. Fahiem Bacchus[4]
  5. Joseph Y. Halpern[5]
  6. Nils John Nilsson[6]
  7. Mark A. Paskin[7]
  8. John S. Breese Construction of belief and decision networks. Computational Intelligence. 8 (1992) 624–647[8]

Ideas

  1. Pioneering A.I. focused on describing the real world.
    1. The real world has objects.
    2. Adopted first-order logic to describe those objects.
    3. This produced concise, and hence learnable models. A model is useless if no one, or only a few, can understand it.
  2. Modern A.I. addresses another real world property, pervasive uncertainty.
    1. Applies to a system's state and dynamics and is described by probability theory.
  3. Bayesian Networks have limited expressive power because the variable set is limited with each taking a value from a fixed range.
    1. This produces a propositional formalism, like Boolean circuits.
    2. The rules for chess, and other domains, are beyond its power to describe.
  4. Pioneering and Modern A.I. both realized the world is uncertain and it has things in it.
  5. Unifying logic and probability can describe an uncertain world with things in it.
  6. "Real objects seldom wear unique identifiers or preannounce their existence like the cast of a play."
    1. Imagine simulating a corn field and demanding a unique identifier for each kernel.
    2. Objects are given a unique identifier only when they come into "view". Other objects are "invisible" until they come into view.
  7. How are objects detected by the process and for the context at hand?
    1. Once an object is detected, is it significant to the current process?
  8. "The difference between knowing all the objects in advance and inferring their existence from observation corresponds to the distinction between closed-universe languages such as SQL and logic programs and open-universe languages such as full first-order logic."
  9. Closed-Universe software language. SQL
    1. Figure 2 shows a closed universe with three variables but exactly 16 possible outcomes.
    2. Unique Names Assumption - Every object has a distinct and unique name.
    3. Domain Closure Assumption - There are no objects other than those named by terms.
  10. Open-Universe software language. Full first order-logic.
    1. Figure 1 shows an open universe with two variables but infinite possible world outcomes.
    2. This makes defining probability models more challenging.
  11. Bayesian Language (BLOG)[9]
  12. Truth Value[10]
    1. In a Closed Universe determining the truth-value for a statement requires testing that statement in each logical world. Tedious but easy.
    2. But in an Open Universe? When logical worlds appear and disappear randomly, testing the truth value for a statement is limited to the worlds known at that instant.
  13. Logic enjoys broad agreement on syntactic forms for expressing nontrivial assertions, i.e., objects. Probability does not. So statisticians combine English and \(\LaTeX\) to communicate.
  14. A Bayes net does more than distributes probabilities over worlds. It is also a machine for generating worlds.
  15. Because any particular probability model \(\mu\) assigns a probability to every possible world, such a constraint will be either true or false in \(\mu\); thus, \(\mu\), a distribution over possible propositional worlds, acts as a single possible world, with respect to which the truth of any probability assertion can be evaluated.
  16. Probabilistic Databases[11]
  17. Adding irrelevant objects to a probability model can change the model's behavior to an arbitrary extent.
  18. A well-formed Bayes Net necessarily defines a unique probability - a complete theory in probability logics - over the variables it contains. In short, it allows for unobserved objects.
  19. Limitations for a propositional language. Creating variables and connecting them is done manually.
    1. Figure 3 shows pseudocode to build an alarm network for \(R\) geological fault regions, each with \(H(r)\) houses.
  20. An open-universe probability model (OUPM) defines a probability distribution over possible worlds that vary in the objects they contain and in the mapping from symbols to objects. Thus, OUPMs can handle data from sources that violate the closed-universe assumption.

References

  1. Inference Engine[12]
  2. Declarative System[13][14]
  3. Bayesian Networks[15]
  4. Logic[16]
  5. Probability[17]
  6. Possible World[18] A model or structure in Probability Theory.
  7. First-Order Logic[19]
    1. Term. From First-Order logic. A constant symbol, a logical variable, or a \(k\)-ary function applied to \(k\) terms as arguments.
  8. Gaifman's Propositional Probability Logic[20]
  9. First Order Logic, with probability worlds.
  10. Łukasiewicz logic[21]
  11. Horn Clause[22]
  12. Fahiem Bacchus Representing and Reasoning with Probabilistic Knowledge. MIT Press, 1990.[23]
  13. Joseph Y. Halpern An Analysis of First-Order Logics of Probability[24]
  14. Markov Logic Networks[25]
  15. Probabilistic Logic[26]
  16. Mark A. Paskin[27]
  17. BUGS[28]
  18. Microsoft infer.net[29]
  19. BLOG[30]

Figures

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10


Internal Links

Parent Article: Reading Notes

Retrieved from "https://www.minormiraclesoftware.com/university_wiki/index.php?title=ACM_Comm_2015_07_Unifying_Logic_and_Probability_(Notes)&oldid=4553"