CSCI 4150: Introduction to Artificial Intelligence, Fall 2005 |

- [M 8/29] First half: Introduction (what is AI? state of the art; future),
Overview of course. Second half: Scheme part I.
- [R 9/1] First half: Agents and environments. Second half: Scheme
part II.
- [R 9/8] First half: structuring problems for search, blind
searches (BFS, DFS, DLS, UCS). Second half: Scheme parts III and V
(list recursion, recursion patterns, functional vs. procedural
programming),
- [M 9/12] First half: Quiz 1, more blind searches (bidirectional
search, UCS), BFS in Scheme, avoiding repeated states states. Second
half: heuristic search.
- [R 9/15] First half: Wrap-up of blind search and repeated state
strategies, review of best-first searches (uniform cost, greedy, A*),
properties of greedy search, A* algorithms (queue and open/closed
list), admissibility of heuristics, optimality of A* (informal and
formal proof), and Exercise 1. Second half: Scheme part IV
(procedures as arguments, map, apply, lambda forms, implicit begins,
printing).
- [M 9/19] First half: review of A* optimality proof (revised
slides), properties of A*, consistency, optimal efficiency, dominance
of heuristics. Returned Quiz 1 and Exercise 1 and went over Q1
solutions. Second half: creating heuristics via subproblems and
relaxed problems.
- [R 9/22] Review and wrap-up of creating heuristics: pattern
databases and learning heuristics. Local search: a different type of
problem. Hill climbing and variations, local beam search, simulated
annealing, genetic algorithms.
- [M 9/26] Quiz 2, Constraint satisfaction problems: heuristic
repair with the min-conflicts heuristic, "dumb" approach to
constructive search, backtracking, forward checking, heuristics for
selecting variables (MRV and degree heuristics) and values
(least-constraining value heuristic), constraint propagation, handling
higher-order constraints, decomposing CSPs by structure (tree/linear
constraint graphs, cutset conditioning, and tree decomposition).
- [R 9/29] Game playing search: two-player, perfect information,
zero-sum games, minimax search, perfect versus imperfect decisions,
alpha-beta pruning.
- [M 10/3] Game playing: review of alpha-beta minimax, went over
practice exercise 1, correctness of alpha-beta pruning, reduction in
branching factor from alpha-beta pruning, finding all optimal moves,
issues with game search. Returned Quiz 2 and went over solutions.
Second half: creating evaluation functions, expectimax, real
game-playing programs.
- [R 10/6] Search wrapup: beam search (not local beam search);
searching with partial information: sensorless problems (search in
belief state space), contingency planning, exploration problems; A* as
branch and bound with underestimates and dynamic programming;
memory-limited A*: IDA* (iterative deepening A*), RBFS (recursive
best-first search), SMA* (simplified memory-bounded A*).
- [T 10/11] Quiz 3, Introduction to logic and knowledge
representation, ontological and epistemological commitments,
propositional logic, truth tables, inference, interpretations, models,
satisfiability, entailment. Scheme Interlude 0.
- [R 10/13] Review of logic preliminaries leading up to soundness
and completeness. Inference in propositional logic: inference
process, Horn normal form, forward chaining, backward chaining,
conjunctive normal form (CNF), implicative normal form (INF),
resolution inference rule, refutation completeness, proofs by
contradiction, set of support strategy, unit preference. Scheme
Interlude 1.
- [M 10/17] Brief review of inference in propositional logic,
Exercise 2, Satisfiability algorithms (DPLL and WalkSAT). Returned
Quiz 3 and went over solutions, finished Scheme Interlude 1.
- [R 10/20] Propositional logic agents, example agent for the
wumpus world; First order logic (FOL): objects, predicates,
quantifiers, moving negations inside quantifiers, transforming FOL
sentences into CNF, Skolemization, unification.
- [M 10/24] Additional topics in FOL inference: dealing with
equality, axiomizing equality, demodulation, paramodulation.
- [R 10/27] Logic wrap-up: answer extraction, comparison
between inference in proposational logic and FOL (e.g.,
semidecidability of modus ponens on first order definite clases
because of infinitely nested functions). Scheme interlude 2: writing
regular expressions in Scheme, a non-regular-expression-based feature
detector.
- [M 10/31] Brief learning introduction: supervised, unsupervised,
and reinforcement learning; hypothesis space and Ockham's razor.
Learning decision trees: basic algorithm for learning a small decision
tree, information gain heuristic, noise and overfitting, rule
post-pruning, gain ratio, chi-squared pruning. Returned Quiz 4 and
went over solutions.
- [R 11/3] Decision trees: brief review from last time,
finished chi-squared pruning and gain ratio, handling missing
attributes (two approaches), handling continuous valued attributes;
Ensemble learning (boosting, ADA-boost); PAC learning; learning
decision lists.
- [M 11/7] Quiz 5. Introduction to probability: discrete random
events, independence, random variables, axioms of probability, joint
probability distributions, conditional probabilities, Bayes' rule,
marginalization (aka "summing out"), conditioning (aka "theorem of
total probability"), normalization.
- [R 11/10] Review of probability and Bayes brute force and optimal
classifiers from last time, Bayesian updating, conditional
independence, Bayes naive classifier, text classification example,
m-estimates for estimating probabilities.
- [M 11/14] Utilities: preferences, lotteries, properties for
rational preferences, (existence of) utility functions, money and
utility. Sequential decision problems (Markov decision problems):
models, policies, utilities, additive utility functions (and
stationarity), Bellman equation, value iteration (and relation to
numerical relaxation). Returned Quiz 5 and went over solutions.
- [R 11/17] Sequential decision problems: policy iteration,
convergence of policy loss before utility values, use of value
iteration in policy iteration (to solve for utilities). Reinforcement
learning: active versus passive RL. Passive RL: direct utility
estimation, adaptive dynamic programming, temporal differencing, use
of value iteration in adaptive dynamic programming (to correct utility
values). Active RL: exploration versus exploitation, optimistic
utility values, exploration function, adapting a passive RL method for
active RL.
- [M 11/21] Quiz 6. Review of passive and active RL from last
time, Q learning, generalization in RL (using a parameterized utility
function instead of storing a value for each state).
- [M 11/28] Exercise 5; Artificial Neural networks: perceptrons,
the perceptron learning rule, linearly separable functions,
sigmoid units, learning for sigmoid units, gradient descent,
stochastic gradient descent. Returned Quiz 6 and went over solutions.
- [R 12/1] Backpropagation for multi-layer feed-forward networks of
sigmoid units, representational power of these networks, convergence
of the backpropagation algorithm, determining the number of hidden
units necessary by cross-validation or "optimal brain damage".
Support vector machines: idea of functions being linearly separable in
high dimensional spaces, learning the "optimal" linear classifier,
(positive definite) kernel functions computing dot products in high
dimensional spaces without computing the feature vectors.
- [M 12/5] Quiz 7. Review of backpropagation and support vector
machines. Instance-based learning: k-nearest neighbor, different
distance metrics (Euclidean, Mahalanobis, Hamming), combining
neighbors to form an estimate/classification (voting, averaging,
weighed versions), cross-validation to determine k, properties
(generally effective, robust to noise, "interference" by irrelevant
attributes), kernel estimators (called "kernel models" in our text).
- [R 12/8] Concept learning: learning by selecting hypotheses from the hypothesis space, generalization and specialization of hypotheses, current-best-hypothesis search, version space search (candidate elimination algorithm).