Mathematical Sciences for Artificial Intelligence

STEFANO LEONARDI
LORENZO MARCONI

General objectives

To provide the student with the fundamental formal notions of two basic aspects of the preparation of an artificial intelligence scientist, mathematical logic and probabilistic methods in computer science. The two sections of the course are dedicated to these two aspects. The first part of the course aims to introduce mathematical logic as a powerful tool for modeling and formally reasoning on different aspects of artificial intelligence, in particular data management, knowledge representation, querying and data review. and knowledge. The second part of the course aims to illustrate some fundamental aspects of the
probabilistic methods in computer science such as the design and analysis of probabilistic algorithms, sampling and probabilistic allocation methods, stochastic processes and some of their applications to data analysis and machine learning.


Specific goals

Knowledge and understanding
For to the first part of the course, the student learns the fundamental notions of mathematical logic, the principles according to which the validity of arguments is judged, the relationships between arguments are analyzed and inferential relationships are evaluated, such as deduction, induction and abduction, among them. Compared to the second part of the course, the student learns the basic notions of the design of probabilistic algorithms and their analysis and acquires the basics to apply these notions to the design of fundamental algorithms in Artificial Intelligence, including search and sorting algorithms, algorithms on networks and graphs, classification algorithms, clustering and machine learning.

Apply knowledge and understanding
The student gains a deep understanding of the role of logic in various aspects of artificial intelligence and basic knowledge to formalize a problem in logic, analyze logical theories and reason on related inferences, build logical theories for modeling knowledge bases of medium complexity, specify logic queries of databases and knowledge base and translate the specification of simple computations into logic programs.
The student acquires a deep understanding of the role of probability in the design of algorithms and in data analysis and acquires basic knowledge to carry out analysis of probabilistic algorithms, define probabilistic algorithms for problems of medium complexity, apply fundamental methods such as Monte Carlo method, Markov chains, dynamic programming and Bayesian models in different contexts, such as sequences, graphs, networks, machine learning, classification and clustering.

Critical and judgmental skills
The student is able to evaluate the validity of statements and arguments, the coherence of a set of axioms in a knowledge base, the adequacy of the formulation of a computation that extracts data from a data and knowledge base, the correctness of a logic program with respect to the specification of certain properties. The student is able to analyze probabilistic algorithms, to evaluate the effectiveness of probabilistic and dynamic optimization methods for algorithmic and Artificial Intelligence problems and to judge the quality of the application of machine learning, classification and clustering algorithms.

Communication skills
The practical activities and exercises of the course allow the student to acquire crucial tools to communicate and share the critical evaluation of logical tools and languages and their role in artificial intelligence and algorithmic methods and their role in different important contexts of Artificial Intelligence.

Learning ability
In addition to the classic learning skills provided by the theoretical study of the basic topics covered in the course, the methods used for the course, in particular the programming activities, stimulate the student to autonomously study some topics, to work in groups and to develop concrete applications of the concepts and techniques learned during the course.

General objectives



To provide the student with the fundamental formal notions of two basic aspects of the preparation of an artificial intelligence scientist, mathematical logic and probabilistic methods in computer science. The two sections of the course are dedicated to these two aspects. The first part of the course aims to introduce mathematical logic as a powerful tool for modeling and formally reasoning on different aspects of artificial intelligence, in particular data management, knowledge representation, querying and data review. and knowledge. The second part of the course aims to illustrate some fundamental aspects of the

probabilistic methods in computer science such as the design and analysis of probabilistic algorithms, sampling and probabilistic allocation methods, stochastic processes and some of their applications to data analysis and machine learning.





Specific goals



Knowledge and understanding

For to the first part of the course, the student learns the fundamental notions of mathematical logic, the principles according to which the validity of arguments is judged, the relationships between arguments are analyzed and inferential relationships are evaluated, such as deduction, induction and abduction, among them. Compared to the second part of the course, the student learns the basic notions of the design of probabilistic algorithms and their analysis and acquires the basics to apply these notions to the design of fundamental algorithms in Artificial Intelligence, including search and sorting algorithms, algorithms on networks and graphs, classification algorithms, clustering and machine learning.



Apply knowledge and understanding

The student gains a deep understanding of the role of logic in various aspects of artificial intelligence and basic knowledge to formalize a problem in logic, analyze logical theories and reason on related inferences, build logical theories for modeling knowledge bases of medium complexity, specify logic queries of databases and knowledge base and translate the specification of simple computations into logic programs.

The student acquires a deep understanding of the role of probability in the design of algorithms and in data analysis and acquires basic knowledge to carry out analysis of probabilistic algorithms, define probabilistic algorithms for problems of medium complexity, apply fundamental methods such as Monte Carlo method, Markov chains, dynamic programming and Bayesian models in different contexts, such as sequences, graphs, networks, machine learning, classification and clustering.



Critical and judgmental skills

The student is able to evaluate the validity of statements and arguments, the coherence of a set of axioms in a knowledge base, the adequacy of the formulation of a computation that extracts data from a data and knowledge base, the correctness of a logic program with respect to the specification of certain properties. The student is able to analyze probabilistic algorithms, to evaluate the effectiveness of probabilistic and dynamic optimization methods for algorithmic and Artificial Intelligence problems and to judge the quality of the application of machine learning, classification and clustering algorithms.



Communication skills

The practical activities and exercises of the course allow the student to acquire crucial tools to communicate and share the critical evaluation of logical tools and languages and their role in artificial intelligence and algorithmic methods and their role in different important contexts of Artificial Intelligence.



Learning ability

In addition to the classic learning skills provided by the theoretical study of the basic topics covered in the course, the methods used for the course, in particular the programming activities, stimulate the student to autonomously study some topics, to work in groups and to develop concrete applications of the concepts and techniques learned during the course.

A basic class on algorithms, a basic class on programming, a basic class on probability

I Sezione (Logica in Informatica)
1. La logica proposizionale. Sintassi e semantica della logica proposizionale. Potere espressivo della logica proposizionale. “Satisfiability”: problema, complessità e algoritmi di decisione. L’inferenza nella logica proposizionale. Problemi e algoritmi di decisione relativi all’inferenza.
2. La logica dei predicati del primo ordine. Sintassi e semantica della logica dei predicati del primo ordine. Potere espressivo della logica dei predicati. L’inferenza nella logica dei predicati: deduzione, induzione e abduzione. Sistemi formali per la deduzione. Problemi di decisione nella logica dei predicati. Cenno alle logiche modali e temporali.
3. Applicazione della logica nell’informatica. La logica nello sviluppo e nell’analisi dei programmi. Logica e automi. La logica nella gestione dei dati. Logica e linguaggi di interrogazione nelle basi di dati. Il linguaggio Datalog. La logica nella rappresentazione della conoscenza.

II Sezione (Metodi Probabilistici)

Sezione 2: Metodi Probabilistici in Informatica

Docente: Prof. Stefano Leonardi - leonardi@diag.uniroma1.it

Tutor: Dr. Federico Fusco - fuscof@diag.uniorma1.it

Martedì ore 09:00 - 11:00 (regolare)

Mercoledì ore 09:00 - 11:00 (a settimane alterne)

La seconda parte del corso di Metodi Quantitativi per l'Informatica intende illustrare alcune aspetti fondamentali dei metodi probabilistici in Informatica e alcune loro applicazioni a problemi numerici e combinatorici, all’apprendimento automatico, e all’analisi dei dati e delle reti ad ampia scala. Il corso si articola in tre sezioni:


1. Algoritmi e probabilità Riferimento [1], Capp. 1, 2 (tutti)

Probabilità, Eventi, e Variabili Aleatorie

Le distribuzioni binomiale e geometrica

Analisi di algoritmi probabilistici:

Algoritmi con e senza memoria

The coupon collector problem

Selezione del k elemento minimo

Quicksort randomizzato

L'algoritmo di min-cut



2. Metodi di campionamento e allocazione probabilistica. Riferimento [1], Cap 3 tutto, Cap. 4.1-4.2 10.1-10.2 5.1-5.2

Momenti e Deviazione

Le funzioni generatrici ed i Chernoff-Hoeffding bounds

Il metodo Monte Carlo

Metodi di campionamento imparziali

Balls in Bins

Counting triangles


3. Processi stocastici ed applicazioni Riferimento [1] Cap. 7.1-7.4

Le catene di Markov e le proprietà di convergenza

Random walks e l'algoritmo di Pagerank

Random walks for 2-SAT

Random Walks in undirected graphs

II Section:

Riferimenti:

[1] Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitznmacher, E. Upfal, Cambridge University Press,

[2] Algorithms, S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Mc. Graw Hill.

Theory lectures and Exercises

In person

Examination methods
I Section.
The student can choose to take the exam for the "Logic and Computer Science" section in two ways:
In the first case the student or the group of two students (no more) chooses to deal with a topic proposed by themselves (possibly also in synergy with a project related to the section of the course on probabilistic methods) or selected among those proposed by the teacher, and communicate the choice to the teacher.

In the second case, the exam consists of a traditional exam (written and possibly oral) concerning the exam programme. Also in this case the student must send a message to the teacher, who will indicate the date of the exam.

II Section.
There are two possibilities for passing the exam:

1) The first and most advised one is to submit the two Homeworks before deadline. The homeworks will be discussed during the exam.

2) The second one is to answer 4 questions oduring in the written exam.

The student that either fails or does not submit the only first/second homework will answer only two/three questions in the written exam.

II Section

i) Solving the problem of determining the expected number of computational steps necessary to solve a computer problem.
ii) Determine the number of samples needed to estimate a quantity with a given precision in the Monte Carlo method.
iii) Determine the steady state of a Markov chain