Telecom ParisTech
Dep. Informatique & Réseaux

J-L. Dessalles Home page

February 2019


                with Pierre-Alexandre Murena     

Logic and Knowledge Representation
                                other AI courses


Overview

This course is an introduction to symbolic techniques in Artificial Intelligence (AI). It relies on one technique, Prolog. The Prolog programming language is used here not only for its power in dealing with logic and knowledge representation, but also because it is the best instantiation of notions like unification and backtracking. The course is also an opportunity to discover important concepts involved in artificial reasoning, in symbolic machine learning, in knowledge representation, and in natural language processing.

Why Prolog ?

The Prolog programming language is unique in several respects. It differs radically from imperative languages (python, C++, Java) and from functional languages (caml, Lisp). Prolog is a declarative language. The programmer ideally provides knowledge to the machine and nothing more. And the machine does the job! Prolog is an ideal opportunity to discover and master fundamental notions of computer science such as: Prolog was imagined to deal with symbolic AI problems: knowledge processing, natural langage processing, reasoning. Its functioning principles are commonly used in ontologies, in unification grammars and in constraint planning systems.

Prolog is also an excellent opportunity to train oneself in a way of thinking that goes beyond the domain of computer science. It consists in addressing a problem in terms of constraints rather than in terms of procedure, leaving to others (to the machine in the case of Prolog) the burden of finding out a solution that will comply with the constraints.

Symbolic Artificial Intelligence

In a famous paper, Alan Turing proposed a behaviouristic definition of artificial intelligence. A machine should be declared intelligent if it can fool human judges in a written conversation so that they believe that they are talking with another human being. Consider the following discussion:

H.    Hi, who are you ?
M.    My name? Martine. And you ?
H.    What is the square root of 17684?
M.    Don’t know. I’ve always been crap at maths.
H.    What does the scent of violet remind you?
M.    To the smell of the bed sheets in my grandmother’s cupboard
H.    Suppose I’m facing you. Now I’m turning to look to the right. On which side are you now?
M.    I’d be on your left.

Would you be able to write a program that plays M’s part? The program needs to understand natural language. It also needs to build up a scene to represent what is meant. And it has to understand the relevance of what is said. All things that are not so easy to do.

Recent improvements in statistical machine learning (data mining, deep learning) let some famous people to predict such a surge of machine intellectual capabilities that they could lead to the end of humankind (see Stephen Hawking’s or Bill Gates’ warnings). These concerns probably motivated other important figures to sign a call for better use of AI techniques.

We should not underestimate the danger of giving robots too much decision power. For instance, in high-frequency trading, virtually all decisions are made by computer programs; financial crashes may be the result, as was the case in 2010. However, current techniques are strongly limited, as they rely mainly on statistics. They can only reproduce or extrapolate from known behaviour. It is highy unlikely that the mere extension of statistical techniques may constitute a threat to humankind. Let’s consider a few examples.

Consider for instance the way a statistical machine may learn how to add to numbers. You’ll be never sure that the machine will get it right.
See my question to Jérôme Pésenti (from IBM Watson) during his talk at Telecom and his kind answer.

Let’s take another example. Try to ask this question:

How many phalanges are there in a Human body ?


Make a real try to answer the question, and write down your answer.
Then you may ask your favourite search engine. It certainly knows the correct answer!

Phalanges
State very briefly how you think your reasoning differs from the procedure used in the search engine.


    


Yet another example. Anyone who is able to count will find an obvious way of continuing the following series:

1,2,2,3,3,3,4,4,4,4

Would you be able to write a program that can solve such riddles? Mmm..., think twice before considering the task trivial. Your program would need to implement a principle of simplicity (or minimum description length): the ‘best’ solution, here probably 5,5,5,5,5, should keep the description of the series as short as possible. This issue will be studied as a topic in this course.

Some Web sites such as this one are specialized in performing induction on numerical series. Verify that the ‘correct’ solution is proposed.

IncreasingSeries
Indicate an alternative solution proposed by the site. Explain why you think that solution is not so good. Can you contrast the way you solved the problem with the method used on the Web site?


    

Importantly, solutions to such induction problems are found using computations that may have no statistical basis whatsoever (one-shot learning). However, these computations are sensitive to structure. In the previous example, anyone can perceive repetitions and incrementations (and the repetition of incrementation). This structural analysis is absent from statistical method (though deep learning can sometimes be used to extract frequent features from large sets of examples when available).

This course will deal with symbolic aspects of AI. This means that we will use structures, structural matching and structure-sensitive procedures. This will allow us to deal with problems (such as aspects of Natural Language Processing and problem solving) that are intractable using brute statistics. It will allow us to produce systematic behaviour and to deal with exceptions and anomalies. And we will see how background knowledge can dramatically improve machine learning, making one-shot learning possible.

Topics

The topics addressed in this course result from a compromise between the importance of notions and the coherence of the course (but have a look at other AI courses). They all belong to the symbolic approach to Artificial Intelligence.

Symbolic models are characterized by the use of structures. They rely on discrete time (e.g. a loop index in a sequential algorithm). Procedures are sensitive to structure. The simplest one consists in matching structures.

Sub-symbolic (or dynamical) models, by contrast, are much closer to physics. They involve metrics, parallel processes and rely ideally on continuous time (though they are generally simulated on discrete sequential machines). Most current sub-symbolic technics are based on statistical computations.

AI topics
Mention two topics in Artificial Intelligence that belong to the symbolic approach
and two other topics that are rather sub-symbolic.
You may have a look at the topics mentioned on the AFIA Web Site,
on the UC-Berkeley AI page, or
on the ICAI’16 web site, or
in the AI100-group 2016 report (read p. 6 on).


    

            

Back to the main page