Unifying Logic and Probability for Learning

Unifying logic and probability is an active and ongoing research topic of great interest to many. There are many proposals of probabilistic logics in the literature, each with a different motivation, either computational or philosophical, and a different system of syntax and semantics. This state of affairs is confusing and not satisfactory, especially in view of the fact that the foundational mathematical problem of integrating logic and probability was long ago solved by Haim Gaifman in this paper:

H. Gaifman, Concerning measures in first order calculi. Israel Journal of Mathematics, 2(1):1-18, 1964.

I believe we will get clarity and make further progress in the study of computationally tractable probabilistic logics if every researcher in the field makes a deliberate attempt to discuss the connections between their systems and Gaifman’s theory, in particular in what way their proposed systems approximate Gaifman’s theory.

To help with this effort, we have recast Gaifman’s theory in a modern framework in this short paper: Unifying Probability and Logic for Learning. Here is the abstract of the paper.

Uncertain knowledge can be modeled by using graded probabilities rather than binary truth-values, but so far a completely satisfactory integration of logic and probability has been lacking. In particular the inability of confirming universal hypotheses has plagued most if not all systems so far. We address this problem head on. The main technical problem to be discussed is the following: Given a set of sentences, each having some probability of being true, what probability should be ascribed to other (query) sentences? A natural wish-list, among others, is that the probability distribution

  1. is consistent with the knowledge base,
  2. allows for a consistent inference procedure and in particular
  3. reduces to deductive logic in the limit of probabilities being 0 and 1,
  4. allows (Bayesian) inductive reasoning and
  5. learning in the limit and in particular
  6. allows confirmation of universally quantified hypotheses/sentences.

We show that probabilities satisfying (1)-(6) exist, and present necessary and sufficient conditions (Gaifman and Cournot). The theory is a step towards a globally consistent and empirically satisfactory unification of probability and logic.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s