CSC 421 Intro to Artificial Intelligence: Spring 2005

Text:
S. Russell and P. Norvig, Artificial Intelligence, a Modern Approach, 2nd Edition, Prentice Hall, 2003

Languages:
We will use Java and Prolog for the programming part of assignments.
Java for AI in other universities: MIT, Stanford, and McGill.

Midterm: Monday, Feb. 28, in class.
Solutions.

Final Exam: Apr. 15,
Solutions.

Assignments:
There would be five assignments, which will have both paper and programming questions.  The assignments would be team work wherein you are required to team up with another classmate.

Source Code:
Here is the book source code. Also, you can download a jar file and put it in the classpath. The UML diagrams (after reverse engineering) are: diagram1, diagram2, diagram3 (save diagram3 and then zoom it).

The code for the Water Jugs problem is here. Also, check some instructions on how to implement a search problem.

WebBoard: Link

E-Submission: Link

Marks so far: Link

Assignment 1 Solutions (missionaries-cannibals and water-jugs)

Assignment 2
Examples: Australia CSP coloring (also download again aima.jar above). General framework for games. Tic-tac-toe.
Solutions (non-programming ones), Zebra, Nim

Assignment 3
Theo Theorem Prover (Linux)
Theo Theorem Prover (SunOS)
Theo Theorem Prover (Windows/DOS)
Solutions(tar file)

Assignment 4 Solutions

Assignment 5

Lectures and Handouts:

Problem-solving.

• Overview of AI. History of AI. Application of AI. Topics to be covered in the course. Slides(ppt)
• Solving Problems by Searching. Formulating problems. Searching for Solutions. Measuring problem-solving performance. Uninformed Search Strategies. Iterative deepening depth-first search. Comparing uninformed search strategies. Avoiding Repeated States. Slides(ppt).
• Informed Search and Exploration. Informed (Heuristic) Search Strategies. Greedy best-first search. A* search. Heuristic Functions. Inventing admissible heuristic functions. Local Search Algorithms and Optimization Problems. Hill-climbing search. Slides(ppt).
• Constraint Satisfaction Problems. Backtracking Search for CSPs. Variable and value ordering. Propagating information through constraints. Forward checking. Constraint propagation. Local Search for Constraint Satisfaction Problems Slides(ppt).
• Games. Optimal Decisions in Games. Optimal strategies. The minimax algorithm. Alpha-Beta Pruning. Imperfect, Real-Time Decisions. Evaluation functions. Cutting off search. Slides(ppt).

Knowledge and Reasoning.

• An informal introduction to logic. Human Logic. Proofs. Unsound Patterns. Soundness. Deduction. Formalization. Resolution Principle. Application to Databases. Slides(ppt).
• Propositional Logic. Syntax. Semantics. Interpretations. Evaluation. Reverse Evaluation. Validity, Satisfiability, Unsatisfiability. Entailment. Semantic Reasoning Methods. Proofs. Resolution Principle. Slides(ppt).
• Conceptualization. First-Order Logic. Syntax. Semantics: Models. Entailment. Herbrand's Models and Method. Slides(ppt).
• Converting to Clausal Form: Skolemization, Inseado. Substitutions and Unification. Computing the Most General Unifier. Relational Resolution. Examples. Slides(ppt).
• Examples, Strategies for resolution. Theo Theorem Prover. Slides(ppt).
• Horn Clauses. Ordered resolution. Directed Resolution: Forward and Backward Resolution. Prolog. Slides(ppt).

Uncertain Knowledge and Reasoning.

• Handling Uncertainty. Belief and Probability. Atomic events. Joint probability. Conditional probability. Inference by enumeration. Independence. Bayes' Rule. Combining evidence. Conditional independence. Slides(ppt).
• Bayesian networks. Compactness of Conditional Probability Tables (CPT’s). Semantics. Constructing Bayesian networks. Noisy-OR. Exact Inference in Bayesian Networks. Slides(ppt).

Machine Learning.

• Induction. Kinds of learning. Memory, averaging, and generalization. Variety of Learning Methods. Data Mining. Complexity of hypothesis. Learning DNF. Slides(ppt).
• Inferring rudimentary rules (1R). Dealing with numeric attributes. The problem of overfitting. Statistical modeling. Naive Bayes classifier. The “zero-frequency problem”. Missing values. Slides(ppt).
• Decision Trees. Entropy. Information gain. Highly-branching attributes. Slides(ppt).
• Rules. Covering. Separate-and-Conquer (vs. Divide-and-Conquer). PRISM algorithm. Slides(ppt).
• Mining Association Rules. Frequent Item sets. Generating item sets efficiently. Slides(ppt).
• Credibility: Evaluating what’s been learned. Training and testing. Cross-validation. Slides(ppt).
• Nearest Neighbor. Scaling. Voronoi partition of the space. KD-Trees. K-Nearest Neighbors. Slides(ppt).
• More on Decision Trees. Numerical attributes. Slides(ppt).
• Regression: Locally weighted averaging. Kernel functions for weighting. Regression Trees. Slides(ppt).
• Linear Separators. Hyperplane Geometry. Margin. Perceptron algorithm. Slides(ppt).
• Neural Networks: Single Perceptron Unit. Beyond Linear Separability. Multi-Layer Perceptron Learning. Soft Threshold. Sigmoid Unit. Gradient Descent. Delta Rule. Backpropagation Algorithm. Training Neural Nets. Slides(ppt).

Review.

• Review Slides(ppt).

Notes: All assignments are due in class. There will be a grade penalty for late assignments. All programs must have adequate internal documentation.