Applied-Logic, Programming Languages and Systems (ALPS) Lab
Postdoc Researchers: Dr. Zhuo Chen, Dr. Serdar Erbatur, Dr. Elmer Salazar
Sarat Varanasi, Kinjal Basu, Fang Li, Huaduo Wang, Farhad Shakerin (recent graduate)
Collaborators: Dr. Joaquin Arias & Dr. Manuel Carro (IMDEA/UPM, Spain)
The ALPS Lab is engaged in research in Computational Logic, AI (automated reasoning, machine learning) and advanced programming languages.
Much of the work revolves around exploring application of advanced logic programming techniques and answer set programming
to these areas.
Current project in AI are in areas of automating common sense reasoning, natural language text question-answering, automated conversational agents, inductive logic programming, and explainable AI.
In programming languages,
current focus is on co-induction and its applications, semantics of negation, and automated program synthesis.
An (incomplete) list of current projects is below.
Natural Language Question Answering based on Text Understanding: This project, called CASPR, is focused on modeling
knowledge using answer set programming (ASP) using our query-driven
s(CASP) implementation of it that supports
commonsense reasoning. Knowledge contained in an English passage
text is translated into an ASP knowledge-base. Relevant common sense knowledge
from resources such as WordNet and VerbNet is translated into ASP as well. Finally, a
question asked against the passage text is translated into an ASP query and executed
against the knowledge-base assembled in the first two steps. Using our query-driven
s(CASP) system, justification for the question's answer can also be computed. This line
of work has the potential to solve the common sense reasoning problem of AI, a major
road block in building truly intelligent systems.
The system uses our novel,
goal-directed implementation of answer set programming called s(CASP). The techniques
developed are also being used to answer natural language questions about objects in a picture
as well as bringing commonsense reasoning to automated driving of autonomous cars.
We are also applying it for building chatbots that operate by "truly understanding" what a human is saying.
- Kinjal Basu, Sarat Varanasi, Farhad Shakerin, Gopal Gupta.
SQuARE: Semantics-based Question Answering and Reasoning
Engine. In Proc. of International Conference on Logic Programming 2020
(Technical Comm.), EPTCS vol. 325. pp. 73-86. click to read
- Dhruva Pendharkar, Gopal Gupta. An
ASP-based Approach to Answering Questions for Natural Language Text.
In Proc. 21st Symp on Practical Aspects of
Declarative Languages, 2019. Springer LNCS 11372. pp 46-63. click to read
Explainable AI/Inductive Learning of Default Theories: This line of research
extends work done in the field of inductive logic programming (where one learns a
logic program from examples and background knowledge) to learning normal logic programs, i.e., learning logic
programs that contain negation as failure. Normal logic programs have been shown
to model human-style common sense reasoning quite well. The inductive learning
algorithms my group has developed learns a default relation as well as exceptions to
it. The learning algorithm can also handle features that range over real numbers. The
algorithms recursively learn exceptions to exceptions and so on thereby producing a
learned theory that has high accuracy. The project is a step towards what is
dubbed Explainable AI and will prove to be a very important contribution to the area
of Machine Learning. Implementations have been developed (Software release coming soon).
The technique has been extended to explain models learned from statistical
machine learning methods. You can download the tool from here.
Details are in the following papers:
- Farhad Shakerin, Gopal Gupta. Induction of Non-Monotonic Logic Programs to
Explain Boosted Tree Models Using LIME. In Proc. AAAI 2019.
(click to read),
- Farhad Shakerin, Elmer Salazar, Gopal Gupta. Inductive Learning of Default
Theories. Theory and Practice of Logic Programming Journal 17(5-6): 1010-
1026, 2017 (Proc. 33rd ICLP).
(click to read)
Query-driven (Predicate) Answer Set Programming: This problem pertains to
executing answer set programs in a goal-directed, top-down manner. This problem
was widely considered unsolvable and most implementations are based on using a SAT
solver, and thus can only handle propositional programs. The idea of coinductive
logic programming pioneered in the ALPS lab is what facilitated the first solution to this
problem. It culminated in the Galliwasp system. Galliwasp was
then generalized to the s(ASP) system that can execute predicate answer set programs
directly, where predicates can contain arbitrary terms (most other systems available
thus far can only handle propositional answer set programs). Both Galliwasp and
s(ASP) are publicly available. s(ASP) has been used to develop a number of innovative
applications. A student hackathon was recently organized around it.
Galliwasp Resources: Papers and software for Galliwasp, a propositional goal-directed ASP system, are available.
- Kyle Marple, Ajay Bansal, Richard Min and Gopal Gupta. Goal-Directed Execution
of Answer Set Programs. Proc. Principles and Practice of Declarative
Programming (PPDP), ACM Press, 2012. pp 35-44.
- Kyle Marple and Gopal Gupta. Galliwasp: A Goal-Directed Answer Set Solver.
Selected Papers from LOPSTR'12. Springer LNCS 7844. pp. 122-136. 2013.
Software: GALLIWASP: A goal-directed system for answer set programming (includes source code and documentation.)
Coinductive Logic Programming: The idea is to give operational semantics to
compute answers that are in the greatest fixpoint semantics. Coinductive LP has farreaching
applications. Standard logic programming (or standard computation) is based
on induction (least fixpoint semantics). Infiite structures such as perpetual programs,
omega-automata, etc., cannot be modeled elegantly by induction. Rather, they
need coinduction for modeling. The paper that introduced coinductive LP received the
ICLP 2016 test-of-time award for being the most influential paper of ICLP 2006. Coinductive
logic programming has been incorporated in many Prolog implementations, most notably in
L. Simon, A. Mallya, A. Bansal, G. Gupta. Coinductive Logic Programming. In
Proc. Int'l Conference on Logic Programming. 2006. Springer Verlag LNCS 4079.
G. Gupta, N. Saeedloei, R. Min, B. DeVries, K. Marple, F. Kluzniak. Infinite
Computation, Co-induction, and Computational Logic. In Proc. 4th Interna-
tional Conference on Algebra and Co-algebra in Computer Science. Springer Verlag,
Neda Saeedloei, Gopal Gupta. Coinductive Constraint Logic Programming. FLOPS
2012. Springer LNCS 7294. pp. 243-259
- Software: Metainterpreter supporting
DRA-style tabling and coinduction with applications to LTL model checking
Modeling Real-time Systems with CLP(R): It is hard to model real-time systems
faithfully (as time is continuous). Most systems model time by discretizing it.
Discretizing time only produces an approximation. This work showed how time in
real-time systems can be faithfully modeled using constraint logic programming over
reals (CLP(R)). We began by showing how timed automata can be faithfully modeled;
this was then generalized to timed grammars, timed push down automata, timed
pi-calculus, timed linear temporal logic, timed planning, etc.
G. Gupta, E. Pontelli. A Constraint-based Approach to Specification and Verification
of Real-time Systems. In Proc. IEEE Real-time System Symposium, San
Francisco, pp. 230-239. Dec. '97.
N. Saeedloei, G. Gupta. Timed Definite Clause Grammars. Proc. 26th International
Conference on Logic Programming. 2010. pp. 212-221
N. Saeedloei, G. Gupta. Timed pi-calculus. Proc. 8th International Symposium
on Trusted Global Computing. Buenos Aires. 2013. Springer Verlag, LNCS 7844.