First Semester
Fri: 11:00 a.m. - 1:00 p.m., Aula 5
Fri: 2:00 p.m. - 4:00 p.m., Aula 5
Introduction [pdf]
Alan Turing (Wikipedia)
Computer chess (Wikipedia)
Shannon, C., "Programming a Computer for Playing Chess", Philosophical Magazine, 41 (314), 1950 [pdf]
BBC2 Horizon, "Out of Control", 2012 [video, on Dailymotion]
D. Silver, et al., "Mastering the game of Go with deep neural networks and tree search", Nature, 529, 2016 [link]
"AlphaGo - The Movie | Full Documentary", YouTube, 2020 [video]
Symbolic reasoning [pdf]
Language, schemas and reasoning
Syllogism (ancient logic) (Wikipedia)
Propositional logic [pdf]
Boolean algebras, formal propositional language and its semantics, satisfiability, entailment
Rules of inference, justified by entailment (Wikipedia)
Entailment and algorithms [pdf]
Turing machine, decision problems, computational complexity, entailment as a satisfiability problem (refutation)
Automated Symbolic Calculus [pdf]
Semantic tableaux, propositional resolution, soundess and completeness, computational complexity
Tree Proof Generator [link]: online solver through semantic tableaux
First-order logic [pdf]
First-order semantic structures, formal language, variables and quantifiers, satisfaction,
entailment
Semi-decidability of First-Order logic [pdf]
Prenex normal form, skolemization, Herbrand's theorem
First-Order resolution [pdf]
Clausal form, unification, resolution method for first-order logic
SLD resolution [pdf]
Horn clauses, SLD resolution, logic programming
Depth-first search (Wikipedia)
Breadth-first search (Wikipedia)
Two Prolog examples that can be executed SWI-Prolog online [link]:
* Re-definition of Prolog append/3 using the function cons/2 [pl]
A note [pdf] describing the trace of an example of SLD resolution with append/3
* Regression to infinity and fairness [pl]
EXTRA: Minimal Models [pdf]
Horn clauses, Herbrand model, implicit database
Plausible reasoning [pdf]
Negation as failure, closed world assumption, deductive, inductive and abductive reasoning
Probabilitistic reasoning: representation and inference [pdf]
Foundations of probability, probability space, random variables, Bayes' theorem, probabilistic inference
Countable set (Wikipedia)
Sigma algebra
(Wikipedia - see simple set-based examples)
Probability space (Wikipedia)
Random variable (Wikipedia)
"The Banach-Tarski Paradox" (semi-serious but also very informative), YouTube, 2015 [video]
Graphical models [pdf]
Graphical models and factorization, d-separation, inference, computational methods
GeNIe Modeler (free academic license) available on BayesFusion LLC [download]
Examples for GeNIe Modeler:
Alarm.xdsl [model]
Alarm_dataset.csv [data file]
Supervised learning [pdf]
Learning proababilities from observations: maximum likelihood estimator, maximum a posteriori probability,
conjugate prior distribution
Binomial distribution (Wikipedia)
Beta distribution (Wikipedia)
Conjugate prior (Wikipedia)
Beta distribution interactive plot [link]
Numerical supervised learning [pdf]
Learning with models that cannot be optimized analytically, logistic regression, gradient descent,
stochastic gradient descent, mini-batch gradient descent
Logistic regression (Wikipedia)
Unsupervised learning [pdf]
Learning from incomplete observations: k-means, hidden random variables, EM algorithm, observability model
k-means (a.k.a. LBG) algorithm - online demo [link]
Voronoi tesselation with Lloyd relaxation - online demo [link]
Expectation Maximization in Python (Colab Notebook) [link]
Andrew Ng, "The EM algorithm", CS229 Lecture notes, Stanford [pdf]
EM algorithm for missing data, examples for GeNIe Modeler:
Alarm.xdsl [model]
Alarm_missing_values_dataset.csv [data file]
Reinforcement learning [pdf]
Multi-armed bandits and methods, Thompson sampling, Markov Decision Processes, state value function, optimal policy,
iterative learning algorithms, action value function, Q-learning
Shannon Entropy (Wikipedia)
Kullback-Leibler divergence (Wikipedia)
GridWorld: Dynamic Programming Demo [link]
ConvnetJS: Deep Q Learning Demo [link]
Sutton, R.S., Barto, A.G., Reinforcement Learning: An Introduction, 2nd Edition (draft)
[link]
(at this time, an early draft is freely available at the above link)
Marco Piastra
Contact: marco.piastra@unipv.it
Mordechai Ben-Ari, Mathematical Logic for Computer Science (3rd Edition). Springer, 2012
Kevin P. Murphy, Probabilistic Machine Learning: Advanced Topics, MIT Press, 2023. [Pre-print]