COL333/COL671 - Artificial Intelligence - Autumn 2023
Tuesday, Thursday, Friday 11-11:50 pm in LH 111


Instructor: Mausam
(mausam at cse dot iitd dot ac dot in)
Office hours: by appointment, SIT 402
TAs: (office hours by appointment)

Course Contents

Introduction; philosophy of intelligent agents; uninformed search; heuristic search; local search; constraint satisfaction; logic and satisfiability; adversarial search; decision theory; Markov decision processes; Bayesian networks representation, inference and learning; reinforcement learning; basics of supervised, semi-supervised and unsupervised learning; intro to deep learning; intro to NLP; current research trends.

Schedule

Start End Topics & Lecture Notes Required Readings Additional Resources
Jul 25 Jul 25 [Slides] Administrivia
[Video] What to Expect from Course


Jul 27 Aug 4 [Slides] Introduction
[Video] What to Expect from AI
[Video] History of AI from 40s - 90s
[Video] History of AI in the 90s
[Video] History of AI in NASA & DARPA (2000s)
[Video] The Present State of AI
[Video] Definition of AI (Dictionary Meaning)
[Video] Definition of AI (Thinking vs. Acting and Humanly vs. Rationally)
[Video] Definition of AI (Rational Agent View of AI)
[Video] Examples Tasks, Phases of AI & Course Plan
AIMA Chapter 1
Beyond Turing Test
Applications of AI
Benefits/Risks of AI
Introduction to AI: Past, Present & Future
Aug 8 Aug 12 [Slides] Uninformed search
[Video] Uninformed Search: Notion of a State
[Video] Uninformed Search: Search Problem and Examples
[Video] Uninformed Search: Basic Search Strategies
[Video] Uninformed Search: Iterative Deepening DFS
[Video] Uninformed Search: Bidirectional Search
AIMA Chapter 3.1-3.4
Beam Search
Intuition of Search Algorithms
Search Algorithms Performance
Uniform Cost Search vs. Djikstra's
Aug 17 Aug 19 [Slides] Informed search
[Video] Informed Search: Best First Search
[Video] Informed Search: Greedy Best First Search and A* Search
[Video] Informed Search: Analysis of A* Algorithm
[Video] Informed Search: Proof of optimality of A*
[Video] Informed Search: Iterative Deepening A* and Depth First Branch & Bound
[Video] Informed Search: Admissible Heuristics and Domain Relaxation
[Video] Informed Search: Pattern Database Heuristics
AIMA Chapter 3.5-3.7
IDA*
Depth First Branch and Bound
A*/IDA* Example
Aug 22 Aug 25 [Slides] Local search
[Video] Local Search: Satisfaction vs. Optimization
[Video] Local Search: The Example of N-Queens
[Video] Local Search: Hill Climbing
[Video] Local Search: Drawbacks of Hill Climbing
[Video] Local Search: Hill Climbing with Random Walk & Random Restart
[Video] Local Search: Simulated Anealing
[Video] Local Search: Local Beam Search and Genetic Algorithms
AIMA Chapter 4.1
Stochastic Beam Search
Evolving Monalisa through Genetic Algorithms
Evolving TSP with Genetic Algorithms
Mixability for Genetic Algorithms (pages 66-68)
Aug 22 Sep 5 Programming Assignment 1
Resources
Aug 29Sep 1 [Slides] Adversarial search
[Video] Adversarial Search: Minimax Algorithm for two player games
[Video] Adversarial Search: An Example of Minimax Search
[Video] Adversarial Search: Alpha Beta Pruning
[Video] Adversarial Search: Analysis of Alpha Beta Pruning
[Video] Adversarial Search: Cutting Off Search
[Video] Adversarial Search: Horizon Effect, Game Databases & Other Ideas
[Video] Adversarial Search: Summary and Other Games
AIMA Chapter 5
How Intelligent is Deep Blue?
Minimax Applet
Sep 5 Sep 11 [Slides] Constraint Satisfaction
[Video] Constraint Satisfaction: Representation of the atomic state
[Video] Constraint Satisfaction: Map coloring and other examples of CSP
[Video] Constraint Satisfaction: Backtracking Search
[Video] Constraint Satisfaction: Variable and Value Ordering in Backtracking Search
[Video] Constraint Satisfaction: Inference for detecting failures early
[Video] Constraint Satisfaction: Exploiting problem structure
AIMA Chapter 6 (skip 6.3.3)
Conversion to Binary CSP
NumberJack
Constraint Programming
Sep 5 Sep 23 Programming Assignment 2
Resources
Sep 19Sep 27 [Slides] Logic and Satisfiability
[Slides] Backdoors in Satisfiability
[Video] Logic in AI: Different Knowledge Representation Systems
[Video] Logic in AI: Syntax
[Video] Logic in AI: Semantics
[Video] Logic in AI: Forward Chaining
[Video] Logic in AI: Resolution
[Video] Logic in AI: Reduction to Satisfiability Problems
[Video] Logic in AI: SAT Solvers - DPLL Algorithm
[Video] Logic in AI: Sat Solvers - WalkSAT Algorithm
AIMA Chapter 7
Advanced SAT Solvers (Sections 2.3, 2.4)
Backdoors
Sep 26 Oct 10 Programming Assignment 3
Resources
Sep 27 Sep 29 [Slides] Intro to Probability
[Slides] Bayesian Networks Representation
[Video] Uncertainty in AI: Motivation
[Video] Uncertainty in AI: Basics of Probability
[Video] Uncertainty in AI: Conditional Independence & Bayes Rule
[Video] Bayesian Networks: Syntax
[Video] Bayesian Networks: Factoriziation
[Video] Bayesian Networks: Conditional Independences and d-Separation
AIMA Chapter 12
AIMA Chapter 13.1-13.2
History of Bayes Theorem
Influence Flow in Bayes Nets
Oct 10 Oct 13 [Slides] Approximate Inference in Bayesian Networks
[Slides] Learning in Bayesian Networks
[Video] Bayesian Networks: Inference using Variable Elimination
[Video] Bayesian Networks: Reducing 3-SAT to Bayes Net
[Video] Bayesian Networks: Rejection Sampling
[Video] Bayesian Networks: Likelihood Weighting
[Video] Bayesian Networks: MCMC with Gibbs Sampling
[Video] Bayesian Networks: Maximum Likelihood Learning
[Video] Bayesian Networks: Maximum a-Posteriori Learning
[Video] Bayesian Networks: Bayesian Learning
[Video] Bayesian Networks: Structure Learning and Expectation Maximization
AIMA Chapter 13.3-13.4
AIMA Chapter 20
Log Probabilities
Oct 14 Oct 14 [Slides] Agent Architectures
[Video] Agents and Environments
AIMA Chapter 2

Oct 17 Oct 30 Programming Assignment 4

Oct 17 Oct 20 [Slides] Decision Theory
[Slides] Markov Decision Processes
[Video] Decision Theory: Steps in Decision Theory
[Video] Decision Theory: Non Deterministic Uncertainty
[Video] Decision Theory: Probabilistic Uncertainty & Value of perfect information
[Video] Decision Theory: Expected Utility vs Expected Value
[Video] Markov Decision Processes: Definition
[Video] Markov Decision Processes: An Example of a Policy
[Video] Markov Decision Processes: Policy Evaluation using System of Linear Equations
[Video] Markov Decision Processes: Iterative Policy Evaluation
[Video] Markov Decision Processes: Value Iteration
[Video] Markov Decision Processes: Policy Iteration and Applications & Extensions of MDPs
AIMA Chapter 16.1-16.3, 16.6, 17.1-17.2.2

Oct 27 Nov 17 Programming Assignment 5

Oct 26Oct 31 [Slides] Reinforcement Learning
[Video] Reinforcement Learning: Background
[Video] Reinforcement Learning: Model-based Learning for policy evaluation (Passive Learning)
[Video] Reinforcement Learning: Model-free Learning for policy evaluation (Passive Learning)
[Video] Reinforcement Learning: TD Learning
[Video] Reinforcement Learning: TD Learning and Computational Neuroscience
[Video] Reinforcement Learning: Q Learning
[Video] Reinforcement Learning: Exploration vs Exploitation Tradeoff
[Video] Reinforcement Learning: Generalization in RL
AIMA Chapter 22.1-22.4.2
TD Learning for Backgammon
Nov 2Nov 3 [Slides] Hidden Markov Models
AIMA Chapter 14.1-14.3

Nov 7Nov 10 [Slides] Introduction to Deep Learning and CNNs
[Slides] Deep Reinforcement Learning
[Video] Deep Learning: Perceptrons and Activation functions
[Video] Deep Learning: Example of Handwritten digit recognition
[Video] Deep Learning: Neural Layer as matrix operations
[Video] Deep Learning: Differentiable loss function
[Video] Deep Learning: Backpropagation through a computational graph
[Video] Deep Learning: Thin Deep Vs Fat Shallow Networks
[Video] Deep Learning: Convolutional Neural Networks
[Video] Deep Learning: Deep Reinforcement Learning
AIMA Chapter 21.1-21.3, 21.4.1

Nov 14Nov 14 [Slides] ChatGPT and Other Language Models


Nov 17Nov 17 [Slides] Ethics of AI
[Slides] WrapUp
[Video] Ethics of AI: Humans vs Robots
[Video] Ethics of AI: Robustness and Transparency of AI systems
[Video] Ethics of AI: Data Bias and Fairness of AI systems
[Video] Ethics of AI: Accountability, privacy and Human-AI interaction
[Video] Wrapup



Textbooks

Stuart Russell & Peter Norvig, Artificial Intelligence: A Modern Approach,
Prentice-Hall, Fourth Edition (2021) (required).

Ina GoodFellow, Yoshua Bengio & Aaron Courville, Deep Learning,
MIT Press (2016).

Grading

Assignments: 40%; Midterm: 18%; Final: 27%; Quizzes: 15%; Class participation, online discussions: extra credit.

There will be five programming assignments due approximately every two weeks.

Course Administration and Policies

Cheating Vs. Collaborating Guidelines

As adapted from Dan Weld's guidelines.

Collaboration is a very good thing. On the other hand, cheating is considered a very serious offense. Please don't do it! Concern about cheating creates an unpleasant environment for everyone. If you cheat, you get a zero in the assignment, and additionally you risk losing your position as a student in the department and the institute. The department's policy on cheating is to report any cases to the disciplinary committee. What follows afterwards is not fun.

So how do you draw the line between collaboration and cheating? Here's a reasonable set of ground rules. Failure to understand and follow these rules will constitute cheating, and will be dealt with as per institute guidelines.