| Week | Topics/Notes | Reading
| 1 | Overview: History and Implications of AI, Intelligent Agents
| Chs. 1-2, 26-27 |
|
| |
- Make sure to look at the assigned readings, as there will be questions on the history and implications of AI research on the midterm and final exams.
- Key concept: an agent function may be represented as a table of all possible percept histories (inputs) and associated actions (outputs), vs. agent programs which implement agent functions compactly.
|
| 2 | Uninformed vs.
Informed Search, Lisp Review (Adam Risi) | Chs. 3-4
|
| |
|
| 3 | Constraint Satisfaction, Game Search | Chs. 5-6
| |
- Both backtracking-search (for constraint-satisfaction) and minimax searches are variants of depth-first search (which is space-efficient).
- For backtracking search, we can modify a simple depth-first search to order variables and values in different ways (e.g. using minimum remaining values and least-constraining value heuristics). Backtracking ('undoing') of assignments occurs when a chosen value is found to be inconsistent (i.e. when all possible assignments at and/or below a node violate the problem constraints).
- Minimax exhausts the search space for finite games, in order to choose the next move; alpha-beta search (a modified minimax) allows terminating sub-optimal paths (move sequences) early.
(move sequences)
|
| 4 | Propositional Logic, Predicate Logic and PROLOG | Chs. 7-8
| | |
- Propositional logic: only has variables (representing independent statements or propositions), negation, and connectives (e.g. implication, disjunction (or), conjunction (and)), biconditional ('if and only if' (iff) 'A iff B' is the same as 'A -> B and B -> A').
- Predicate logic: we add an underlying domain of objects; variables are now place-holders for objects, and predicates (logical assertions, somewhat similar to boolean functions) define properties of objects. Quantifiers are added in order to indicate whether predicates apply to some (existential quant.) or all (universal quant.) objects that can be substituted for variables.
- PROLOG: introduction is available on the (see Resources web page). Examples from slides/class: Appending to lists, Colonel West example.
- Another example PROLOG program: a Semantic Network corresponding to the one shown in the course text, page 351. Try loading the program (using ['SemanticNet.prolog']), and then querying PROLOG about different properties of objects. Try isa(john,X)., to find out what types of thing john is (use ';' after each response is returned to have prolog perform another search), or isa(john,persons). to see if John is a person. Final suggestion: try isa(john,dog). Remember that in PROLOG, all statements must end with a period.
|
| 5-6 | Inference Using Predicate Logic, and Classical Planning | Chs. 9,11
|
| |
- Propositionalization: converting a first-order knowledge base into a propositional knowledge base using universal and existential instantiation.
- Unification: the process of making two FOL statements identical through defining (logically consistent) variable substitutions.
- For inference in first order logic, we can extend the forward and backward-chaining methods for propositional logic to include necessary unification steps, using the generlized Modus Ponens inference rule. We can also produce resolution proofs (which are proofs by contradiction) using a resolution rule for CNF clauses in first-order logic.
- For planning, we focus on the STRIPS planning language, and partial-order planning, where our plans represent mutliple action orderings rather than a single solution path as we've seen from `standard' searches.
|
| 7 | Inductive Learning and Probability | Chs. 18, 13
|
| |
- Inductive learning is a form of supervised learning, where an algorithm constructs a hypothesis for the function that generates the training set used by the algorithm (samples are labeled with correct reponses/outputs).
- Decision tree induction constructs a function hypothesis, representing the function as a tree. The tree can be equivalently represented by a table enumerating all possible inputs and the associated output (e.g., classification); normally, the tree representation is much more compact.
- Regression: leaning a function with continuous outputs. Classification: learning a function with a finite, discrete set of outputs.
| 8 | Bayesian Networks | Ch. 14
| |
- This week we reviewed the midterm examination. Be aware that similar questions might be asked on the final exam.
- We completed our review of unconditional (absolute) and conditional probability, as well as the absolute and conditional independence of variables (i.e. variables that do not influence one another at all (absolute ind.) or that do not influence one another if values for other variables are known(conditional independence). We also talked about Bayes' Rule, which can be used to compute the probability of causes given effects (P(Cause | Effect)), but using the probability of effects given causes (P(Effect | Cause)), as these are normally easier to observe.
- Using the problem of deciding where to move in Wumpus World, we looked at how agents can make decisions by selecting the most likely desirable outcome, e.g. by moving to a board location on the fringe of visited locations with the lowest probability of containing a pit.
- We looked at how a Bayesian Network, which represents the conditional independence of variables, may be used to compute the probability of atomic events using many fewer probabilities than using enumeration with a complete joint probability distribution (linear vs. exponential in the number of variables in a probability model).
|
| 9 | Inference Using Bayesian Networks, and Neural Networks | Ch. 14
| |
- We looked at inference in Bayesian networks, both for absolute (e.g. P(B)) and conditional (e.g. P(B | a)) queries, using exact inference (producing probabilities consistent with those defined in the network), and approximate inference (produced by estimating probabilities from samples generated from the network).
- We also had a (brief!) introduction to the use of neural networks for learning functions (e.g. for classification), specifically perceptrons and multi-layer perceptrons trained via backpropagation of error. Function input and output variables are represented by
nodes in the input and output layers; functions are represented by
the node connection structure (topology) and weights of connections
in the network. There is a tradeoff between the expressivity of the
network (roughly coinciding with the number of layers and nodes in the
network topology), and the amount of data and time needed to train
the network.
| | |
