I arrived at Syracuse University as a graduate student in 1989 –
straight from the heat of the desert in India, to the cold, windy
climate in Syracuse. Fortunately, the warmth of the students, staff and
Professors at Syracuse made up for the lack of a good climate. At
the time, Syracuse was populated by four big giants in logic
programming. Alan Robinson, who had invented the resolution principle
in 1965 led the “group”, but this itself was a somewhat
amorphous entity. Ken Bowen headed an effort in metalevel logic
programming with a crew of talented implementers like Hamid Bacha,
Ilyas Cicekli, as well as with some outstanding theorists like Aida
Batarekh. Howard Blair, a former Bowen student, had just returned
to Syracuse as an Assistant Professor. Klaus Berkling, a recent
arrival from Germany, was designing logic machines. And Ernie Sibert
was developing higher order logic languages with a postdoc, Kevin
Greene. Those were heady days for logic programming – and
Syracuse had the cream of the crop in North America. I took my
introductory logic programming class with Tim Clement – an
outstanding and enthusiastic teacher.
Shortly after this, I took a seminar course with Howard Blair. Howard
had been assigned the task of reviewing a controversial paper submitted
to the Journal of Logic Programming. The paper effectively said the
main results of some leaders of logic programming were wrong. Nowadays,
we might be tempted to look askance at such papers, but Howard took his
job seriously. So seriously that he invited the whole class to look at
the paper. We literally read the paper, line by line, in the
class, and critiqued each and every line of the paper. Every single
claim was read, understood, and if not immediately obvious, was
assigned to a student to verify or invalidate. The student was
subjected to a thorough grilling at the end of which Howard decided
whether to believe the sentence or not. Not surprisingly, the
paper took the whole semester to read and review. Though I did not
learn much from the paper itself (whose main result was incorrect), I
learned a far more valuable lesson, namely that when writing a paper,
one must be careful about each and every single written word.
I continued studying logic programming and in 1986, came across a paper called "Quantitative Logic Programming” by Maarten van Emden in the Journal of Logic Programming [VE86]. This paper extended the pioneering paper of van Emden and Kowalski [VEK] and Apt and van Emden [AVE82]
that laid the foundation of LP. I was so intrigued by the paper that it
became the subject of my Master’s paper supervised by Lockwood
Morris. I developed an immediate affinity for logic, for
uncertainty, and for semantics – a love that I have continued to
hold ever since.
Logic programming with uncertainty has gone through several phases in
the last 25 years – I divide these phases into the following six
parts.
The First Phase
The first “serious” paper on quantitative logic programming was one by Ehud Shapiro in IJCAI 1983 [SH83].
Shapiro defined certainty factors to be numbers in the left open and
right closed interval (0,1]. A certainty function was a mapping
from multisets of certainty factors to certainty factors. Shapiro
studied logic programs where a certainty function was associated with
each rule. Intuitively, the certainty function took the multiset
of certainty values of atoms in the body of a rule and combined them
together to assign a certainty value to the head. Based on this
syntax, Shapiro [SH83]
provided a model theoretic semantics for such logic programs and then
provided a meta-interpreter or such programs. He also identified some
methods for debugging of such programs.
The Second Phase
Multiple competing efforts in 1986 all decided that rather than
associating certainty functions with rules, it was much simpler to just
associate a certainty factor with each rule. Ishizuka and
Kanai’s Prolog-ELF system [IK86], Baldwin’s evidential support logic programming and FRIL systems [BA86,BA87], and Van Emden’s quantitative rule sets [VE86]
all adopted this special case of Shapiro’s syntax. Van
Emden’s noteworthy paper built on the foundation laid by Shapiro
to provide a fixpoint theory and a proof theory for Shapiro’s
work – the proof theory was sound and complete (under certain
restrictions).
The Third Phase
In 1987, I introduced a very weird notion of a quantitative logic
program at what was then called the IEEE Symposium on Logic Programming
[SU87] The space of truth values was [0,1] U { * }
where * denoted inconsistency. * was the top value, while 0.5 was the
bottom value (denoting “ignorance”) in this complete
lattice of truth values. For numbers x,y in [0.5,1],
x was considered below y in the lattice ordering if it was less than or
equal to y in the usual ordering on the reals. For numbers in the
[0,0.5], x was
considered below y in the lattice ordering if it was greater than or
equal to y in the usual ordering on the reals. This corresponded
precisely to a “knowledge order” and
supported a paraconsistent semantics (one where inconsistency did not
allow everything to be derived). It was also the first paper that
explicitly allowed a form of negation to appear in the head. Moreover,
unlike previous efforts, each atom in a rule was annotated with a truth
value. This was the first “annotated logic”. Later in 1987 and 1988, Howard Blair and I proposed annotated logics [BS87,BS88]
where the truth values could be drawn from any lattice whatsoever, and
we showed that various previous methods to handle uncertainty could be
captured within our framework.
Several other important developments took place just after this. Kifer
and I extended the Blair-Subrahmanian annotated logics to a
“generalized annotated program (or GAP)” – a paradigm
that allowed annotations (truth values) to include complex term like
structures and greatly extended the expressive power of the language to
support temporal reasoning, temporal and uncertain reasoning, and so on
[KS89,KS92]. GAPs would prove to be one of the most lasting ideas in uncertain logic programming Kifer and Lozinskii [KL92]
started working on a generalization of the annotated logic idea called
an annotated predicate calculus. These ideas were
beautifully developed further by Kifer and Krishnaprasad who went on to
develop an annotated logic based theory of inheritance networks [KK93].
Larry Henschen and his graduate student, James Lu (now a Professor at
Emory University) started working on automated theorem proving in
annotated logics [LH92]. Shortly thereafter, Neil Murray and Erik Rosenthal wrote a series of papers advancing theorem proving in these fields [MR94].
Concurrently, Melvin Fitting started working on bilattice based logic programs [FI88].
Bilattices required that the set of truth values be a complete lattice
under both a “knowledge” order and a “truth”
order, and moreover required that these orderings mesh together
nicely. This is another important idea that has withstood the
test of time.
The Fourth Major Phase
Despite approximately a decade of work on managing uncertainty, not a
single approach had even pretended to handle probabilities. In the
early 90s, my student Raymond Ng (now a Full Professor at the Univ. of
British Columbia in Vancouver) and I decided to tackle the problem of
probabilistic logic programming head on. Inspired by a paper by
Fagin, Halpern and Megiddo [FHM90] which in turn was based on prior work by Hailperin [HA84],
we set up an interval based probabilistic LP language which used an
annotated logic style syntax, but provided a probabilistic
semantics (with the “ignorance” assumption that we knew
nothing about the dependencies between the events denoted by
atoms). Ng and I developed a model theoretic and fixpoint
semantics for such programs, as well as a sound and complete query
processing procedure [NS91,NS92]. Later, we extended the semantics to allow certain type of complex formulas to be annotated in rule heads and bodies [NS93]. Linear programming was used in the declarative semantics.
Around this time, Lakshmanan at Concordia University got interested in
probabilistic logic programming and wrote a series of excellent papers
with Fereidoon Sadri on this topic [LS94,LS94a].
They proposed the concept of a trilattice by adding an extra precision
ordering to the bilattices used by Fitting. They developed a
declarative semantics, complexity results, and query processing
procedures for such programs.
The Fifth Major Phase, Thread A
Somewhere around
this time, probabilistic logic programming became ready to enter the
more traditional database world. I joined forces with Lakshmanan,
Nicola Leone in Calabria, and Robert Ross, to develop the concept of
probabilistic database [LLRS97].
We extended the relational algebra to include probabilistic data and
built the first probabilistic DBMS (called ProbView) that did not
assume everything was independent. ProbView proposed the notion of
conjunction and disjunction strategies that allowed a user to bring his
knowledge of the dependencies between events into a query that he
articulated. ProbView, as the name indicates, also supported
views and view maintenance. Robert wrote the ProbView code on top of
DBASE, a database system that few of us remember today. Later, when I
co-wrote a book [ZA98]
with Rick Snodgrass, Rick asked me how ProbView scaled to the case of
temporal uncertainty. My students Alex Dekhtyar, Rob Ross and I
investigated this question and later proposed the concept of a
temporal-probabilistic database [DRS01]. The TP-database system was part of a highly innovative application [MR03]
that garnered praise from a top Admiral in the US Navy. Subsequently,
Thomas Eiter, James Lu, Thomas Luksiewicz and I showed how to extend
the concept of ProbView to probabilistic data management in an object
oriented setting [ELLS01].
Rosalba Giugno, Thomas Lukasiewicz and I worked on extending
temporal-probabilistic databases to the object oriented case as well [BGLS03]. Robert Ross, John Grant and I also took the first steps towards aggregate computation in probabilistic databases [RGS05].
The Fifth Major Phase, Thread B
Concurrently with thread A above, exciting developments were also
occurring in the logic programming arena. Lakshmanan and
Shiri were interested in optimizing queries to probabilistic LPs [LS01].
They focused only on implication based semantics as opposed to the
annotation based semantics (as the latter was more expressive than the
former), and produced the first query optimizer for probabilistic
LPs. Concurrently, Dekhtyar and I [DS97,DDS99,DS00]
were trying to get rid of the “ignorance” assumption in
probabilistic logic programs and proposed the concept of a hybrid
probabilistic program that allowed ProbView’s conjunction and
disjunction strategies to be explicitly encoded into logic programs.
Thus, logic programmers could explicitly express conditions that
captured their knowledge about the dependencies between events encoded
in the logic program. Lukasiewicz did important work on developing
alternative conditional probability based semantics for probabilistic
LP and for coming up with reasonable approximation algorithms [LUK01]. Damasio and his colleagues [DPS01,DP02] showed how HPPs could be embedded into a framework called residuated logic programs.
The Sixth Phase
Probabilistic logic programming has branched out into two major new
directions. The first focuses on the problem of agents that need
to reason in the presence of uncertainty and that have to access or
effectively leverage legacy data and/or specialized software
modules. Based on the notion of a heterogeneous agent program due
to Eiter et. Al. [ESP99,SU00], Dix et. al. proposed the concept of a probabilistic agent program [DNS00].
In such programs, the agent’s behavior is fixed, but there is
uncertainty in the state that the agent is in. Subsequently, Dix
et. al. [DKS06] extended this work to the case of agents that reason with both time and uncertainty.
More recently, I, along with my students, have proposed the concept of a Stochastic Opponent Modelling Agent (SOMA) [SSNS06,SU07,KH07]
as a paradigm for modeling what a third party might do. SOMA was
used to model the behavior of various tribes in the
Pakistan-Afghanistan borderlands and to try and understand the behavior
of two terrorist groups – Hezbollah and the Fatah Revolutionary
Council (Abu Nidal Organization). SOMA uses an extension of
probabilistic logic programs to write rules that specify the
probability that a given group will take a given action in a given
situation. Based on this, the SOMA system at UMD can compute the
k most probable sets of actions that a given group might do in a given
situation. The development of heuristics within SOMA [KH07]
allows us to find very good (though sub-optimal) solutions to this
problem even when the group may take upto 1027 possible sets of actions
in a given situation ! SOMA has perhaps been the most visible
application of techniques for uncertainty management and logic
programming to date, even garnering references to its findings in
Science magazine [BH07].
The Future
This points the way to the future, and also highlights a major problem
– not just with uncertainty in LP, but with LP in general.
There is an over-abundance of theorems, and a great paucity of
algorithms and systems that actually work, even if only under some
limitations. Heuristics have an important role to play, but are
looked down upon in the LP community. So are applications.
Unfortunately, the complexity of managing uncertainty in LP is so high
that for many realistic applications, heuristics are a must. The study
of how such heuristics can be developed and built and how these can be
effectively deployed in real world applications. is critical for the
future success of LP.
References
[AVE82]
K.R. Apt and M.H. van Emden. (1982) Contributions to the theory of logic programming, JACM, 29, 3, pages 841-862.
[BA86]
J. F. Baldwin. (1986) Support logic programming, International Journal of Intelligent Systems, 1, pp. 73-104.
[BA87]
J.F. Baldwin. (1987) Evidential support logic programming, Fuzzy Sets and Systems, 24, 1, pages 1-26.
[BH07]
Y. Bhattacharjee. (2007) Cross Cultural Research: Pentagon asks Academics for help in Understanding its Enemies, Science, Vol. 316, pages 534-535. April 27, 2007.
[BGLS03]
V. Biazzo, R. Giugno, T. Lukasiewicz and V. S. Subrahmanian. Temporal Probabilistic Object Bases. IEEE Transactions on Knowledge and Data Engineering, 15, 4, pages 921-939.
[BS87]
H. Blair, V. S. Subrahmanian: Paraconsistent Logic Programming. Proc. FSTTCS 1987, Springer LNCS Vol. 405, pages 56-67.
[BS88]
H. Blair, V. S. Subrahmanian, Paraconsistent Foundations for Logic Programming, . J. of Non-Classical Logic, 5, 2, pages 45-73.
[BS89]
H. Blair, V. S. Subrahmanian. (1989) Paraconsistent Logic Programming. Theoretical Computer Science, 68, 2, pages 135-154.
[DPS01]
C. Damasio, L.M. Pereira and T. Swift. (2001) Coherent, well founded annotated logic programs, Proc. 5th Intl. Conference on Logic Programming and Nonmonotonic Reasoning, Springer LNCS Vol. 1730.
[DP02]
C. Damasio and L. M. Pereira. (2000) Hybrid logic programs as residuated logic programs, Proc. JELIA 2000, Springer LNCS Vol. 1919.
[DS97]
A. Dekhtyar and V. S. Subrahmanian. (1997) Hybrid Probabilistic Programs. Proc. International Conference on Logic Programming, pages 391-405.
[DDS99]
M. I. Dekhtyar, A. Dekhtyar and V. S. Subrahmanian. (1999) Hybrid Probabilistic Programs: Algorithms and Complexity, Intl. Conf. on Uncertainty in Artificial Intelligence, pages 160-169.
[DS00] A. Dekhtyar and V. S. Subrahmanian. (2000) Hybrid Probabilistic Programs. Journal of Logic Programming 43, 3, pages 187-250.
[DNS00]
J. Dix, M. Nanni and V. S. Subrahmanian. (2000) Probabilistic agent programs. ACM Trans. Comput. Log. 1, 2, pages 208-246.
[DKS06]
J. Dix, S. Kraus and V. S. Subrahmanian. (2006) Heterogeneous temporal probabilistic agents. ACM Trans. Comput. Log. 7, 1, pages 151-198.
[DRS01]
A. Dekhtyar, R. Ross and V. S. Subrahmanian. (1991) Probabilistic temporal databases, I: algebra. ACM Transactions on Database Systems, 26, 1, pages 41-95.
[ELLS01]
T. Eiter, J. J. Lu, T. Lukasiewicz and V. S. Subrahmanian. Probabilistic object bases. ACM Transactions on Database Systems, 26, 3, pages 264-312.
[ESP99]
T. Eiter, V. S. Subrahmanian and G. Pick. (1999) Heterogeneous Active
Agents, I: Semantics. Artificial Intelligence, 108, 1-2, pages
179-255.
[FHM90]
R. Fagin, J.Y. Halperin and N. Megiddo. (1990) A logic for reasoning about probabilities, Information and Computation, 87, 11, pages 78-128.
[FI88]
M. Fitting. (1988) Logic programming on a topological bilattice, Fundamenta Informaticae, 11, pages 209-219.
[HA84]
T. Hailperin. (1984) Probability logic. Notre Dame J. of Logic, 25, 3, pages 198-212.
[IK86]
M. Ishizuka and N. Kanai. (1986) Prolog-ELG Incorporating Fuzzy Logic, New Generation Computing, 3, 4, pages 479-486.
[KH07]
S. Khuller, V. Martinez, D. Nau, G. Simari, A. Sliva, and V.S.
Subrahmanian. Finding Most Probable Worlds of Probabilistic Logic
Programs, submitted.
[KL92]
M. Kifer and E. Lozinski. A Logic for Reasoning with Inconsistency. J. Autom. Reasoning 9(2): 179-215 (1992)
[KK93]
M. Kifer and T. Krishnaprasad. (1993) A Theory of Nonmonotonic Inheritance based on Annotated Logic, Artificial Intelligence, 1993, 60, 1, pages 23-50.
[KS89]
M. Kifer and V. S. Subrahmanian. (1989) On the Expressive Power of Annotated Logic Programs, Proc. North American Conference on Logic Programming, pages 1069-1089.
[KS92]
M. Kifer and V. S. Subrahmanian. (1992) Theory of Generalized Annotated Logic Programming and its Applications. Journal of Logic Programming, 12, 3&4, pages 335-367.
[LLRS97]
L.V. S. Lakshmanan, N. Leone, R. Ross and V. S. Subrahmanian. ProbView: A Flexible Probabilistic Database System. ACM Transactions on Database Systems, 22, 3, pages 419-469.
[LS94]
L.V.S. Lakshmanan and F. Sadri. (1994) Probabilistic deductive databases, Proc. Intl. Symposium on Logic Programming, pages 254-268.
[LS94a]
L.V.S. Lakshmanan and F. Sadri. (1994) Modeling uncertainty in deductive databases, Proc. 5th Intl. Conf. on Databases and Expert Systems Applications, Springer Lecture Notes in Computer Science Vol. 856, pages 724-733.
[LS01]
L.V.S. Lakshmanan and N. Shiri. (2001) A parametric approach to deductive databases with uncertainty, IEEE Transactions on Knowledge and Data Engineering, 13, 4, pages 554-570.
[LH92]
J. J. Lu and L.. Henschen. (1992) The Completeness of GP-Resolution for Annotated Logics, Inf. Process. Letters, 44, 3, pages 135-140.
[LUK01]
T. Lukasiewicz. (2001) Probabilistic logic programming with conditional constraints, ACM Transactions on Computational Logic, 2, 3, pages 289-339.
[MR03]
R. Mittu and R. Ross. (2003) Building upon the coalitions agent
experiment (coax)-integration of multimedia information in gccs-m, Proceedings 9th International Workshop on Multimedia, Ischia, Italy, 2003.
[MR94]
N. V. Murray and E. Rosenthal. (1994) Adapting Classical Inference Techniques to Multiple-Valued Logics Using Signed Formulas, Fundam. Informaticae, 21, 3, pages 237-253 (1994).
[NS91]
R.T. Ng and V. S. Subrahmanian. (1991) A Semantical Framework for
Supporting Subjective and Conditional Probabilities in Deductive
Databases, Proc. Intl. Conf. on Logic Programming, 565-580.
[NS92]
R. T. Ng and V. S. Subrahmanian. (1992) Probabilistic Logic Programming, Information and Computation, Vol. 101, 2, pages 150-201.
[NS93]
R. T. Ng and V. S. Subrahmanian. (1993) A Semantical Framework for
Supporting Subjective and Conditional Probabilities in Deductive
Databases. Journal of Automated Reasoning, Vol. 10, 2, pages 191-235.
[RGS05]
R. Ross, V.S. Subrahmanian and J. Grant. (2005) Aggregate operators in probabilistic databases. J. ACM, 52, 1, pages 54-101.
[SH83]
E. Shapiro. (1983) Logic Programs With Uncertainties: A Tool for Implementing Rule-Based Systems. IJCAI, pages 529-532.
[SSNS06]
Gerardo Simari, Amy Sliva, Dana S. Nau, V. S. Subrahmanian. (2006) A stochastic language for modelling opponent agents, Proc. AAMAS 2006, pages 244-246.
[SU87]
V. S. Subrahmanian. (1987) On the Semantics of Quantitative Logic Programs, Proc. IEEE Symp. On Logic Programming, pages 173-182.
[SU00]
V.S. Subrahmanian, P. Bonatti, J. Dix, T. Eiter, S. Kraus, F. Ozcan and R. Ross. Heterogeneous Agent Systems, MIT Press, 2000.
[SU07]
V.S. Subrahmanian, M. Albanese, V. Martinez, D.Nau, D. Reforgiato, G.
SImari, A. Sliva and J. Wilkenfeld. CARA: A Cultural Adversarial
Reasoning Architecture, IEEE Intelligent Systems, Vol. 22, Number 2, pages 12—16, March/April 2007.
[VEK76]
M.H. van Emden and R. A. Kowalski. (1976) The semantics of predicate logic as a programming language, JACM, 23, 4, pages 733-742.
[VE86]
M.H. van Emden, (1986) Quantitative deduction and its fixpoint theory, Journal of Logic Programming, 3, 2, pages 37-53.
[ZA98]
C. Zaniolo, S. Ceri, C. Faloutsos, R. T. Snodgrass, V. S. Subrahmanian, and R. Zicari: Advanced Database Systems. Morgan Kaufmann 1997.