CSE 150 is an upper-division course devoted to the basic concepts and algorithms of modern artificial intelligence (AI) research. 150 is part of a two quarter sequence with CSE 151, but each course may be taken independently. 150 will mainly cover search and reasoning methods, while 151 will focus on learning methods. Both courses will cover theory and applications.
Some specific AI topics that will be covered in CSE 150 are:
Lectures will be on Mondays and Wednesdays from 5pm to 6:20pm in
room Cog Sci 005 (not PCYNH 106).
Section meetings are on Wednesdays (3pm to 3:50, HSS 1330) and Fridays
(noon to 12:50, Cog Sci 004). You must attend at least one of
these sections every week. You are welcome to attend both.
The instructor is Charles
Elkan, Professor. Office hours will be on Mondays
from 2pm to 3pm, and Wednesdays 11:30am to 12:30pm, in AP&M room
4856. If you are
unable to attend office hours, feel free to send email to arrange an appointment.
We have an excellent teaching assistant (TA), Doug Turnbull.
He will lead the sections and have office hours on Tuesdays (11am to
noon) and Thursdays (2pm to 3pm) in EBU1, room 6307C.
Juniors, seniors, and graduate students in CSE, mathematics, and
cognitive science are
welcome. The only prerequisite for 150 is CSE 100
(upper-division data structures) or an equivalent course.
For registration, the section id is 507382. Note: If you are not allowed to register because the course is listed "majors only," do not worry. We are lifting this restriction. If necessary, come to the first leacture and the instructor will sign an add card.
| date |
topics |
| September 27 |
Planning as search,
priority-queue search. |
| September 29 |
Breadth- and depth-first search,
space and time usage, iterative deepening. |
| October 4 | Greedy heuristic search, f = g + h function, A* algorithm,
proof of A* optimality. |
| October 6 |
Proof of A* optimality,
completeness, and efficiency. Effective branching factor,
duplicate elimination. |
| October 11 |
Offline vs online, global vs
local search. Constraint satisfaction problems: DFS,
forward-checking. |
| October 13 |
Forward checking CSP
algorithm. Heuristics for variable and value ordering.
Intro to DPLL algorithm. |
| October 18 |
DPLL algorithm: unit
propagation, heuristic for variable selection. Hard random 3SAT
instances. |
| October 20 |
Randomized local search: GSAT
algorithm, simulated annealing. |
| October 25 |
Walksat, metaphorical algorithms
in general. Reasoning with probabilities: events, independence,
conditional probabilities. |
| October 27 |
Product rule and Bayes'
rule. Application in diagnosis, probabilities vs. counts.
Framework for classifier learning |
| November 1 |
Random variables. Bayesian
learning, the naive Bayes assumption of conditional independence. |
| November 3 |
Review of Bayesian
learning. Step by step naive Bayes algorithm, computational
complexity, computing with logarithms. |
| November 8 |
Using pseudocounts to avoid zero
probabilities. Generalization, overfitting, concept drift.
Measuring accuracy, cross-validation. |
| November 10 |
In-class midterm. Sample exam |
| November 15 |
First-order logic (FOL):
predicates, arguments, connectives, quantifiers, variables, the [[ ]]
meaning function, constant-symbols, function-symbols |
| November 17 |
Contrast between functions and
predicates in FOL, equality predicate, ontology, guidelines for
axiomatizing knowledge |
| November 22 |
The situation calculus: actions,
states, fluents, the holds
predicate. Syntactic, semantic, and type errors in FOL. |
| November 24 |
Proof by contradiction in
Otter. The Yale shooting domain, the frame problem and its holds/causes/cancels solution. |
| November 29 |
Reasoning forwards and bacwards
about actions, solving planning tasks. Completeness and
semi-decidability of FOL theorem-proving. |
| December 1 |
How Otter works: the modus ponens inference rule, an
example proof, resolution, clausal normal form, unification |
| ... |
|
| December 6 |
(Monday) Final exam 7pm
to 10pm. |
| date |
topics |
| Sept
29/Oct 1 |
Search algorithm framework using
a priority queue. |
| October
7/9 |
A* algorithm, code design for
Assignment 1. |
| October
13/15 |
Boolean satisfiability problem,
CSP framework, forward checking algorithm. |
| October
20/22 |
The DPLL algorithm in detail. |
| October 27/29 |
Comments on Assignment 1,
Walksat and DPLL questions. |
| November 3/5 |
Review and advice for the
midterm. |
| November
10/12 |
Review of naive Bayesian
learning, advice for the spam filtering assignment |
| November
17/19 |
Assignment 2 feedback, FOL
introduction, getting started with the Otter theorem-prover |
| November 24 |
Using Otter to encode a
narrative with the situation calculus (old section notes by Kristin
Branson) |
| December
1/2 |
Review of FOL and general review
for the final. Midterm sample
solution. |
Quite a few of the topics discussed in class will not be in either
book, or will be explained differently. Coming to lectures and taking
notes carefully is important. As the quarter progresses,
it is your responsibility to locate relevant chapters of the books and
to study them. Use the indexes of the books!
An excellent second reference is Mathematical
Methods in Artificial Intelligence by Edward A. Bender, IEEE
Press, 1995, ISBN 0818672005.
The course will have an open-book final examination on Monday
December 6, from 7pm to 10pm. There will be one
midterm exam, also open-book, on Wednesday November 10 in class.
Examinations will be based
mainly on the online lecture notes, but may ask
questions that involve knowledge from the assignments, or in Russell
and Norvig.
There will be four assignments. The examinations will count
for 50% of your overall grade and the assignments for 50%. Complete academic honesty is always
required.
The first three assignments are due in class, i.e. at 5pm. The
penalty for late submission is 20% of the maximum score per day or part
of day late. One day late means after 5pm and before midnight on
the due date, two days late means the next day, and so on. The
assignments will be due on Wednesday October 13, Monday November 1,
Wednesday November 17, and Friday December 3.
For all programming assignments, code quality is very
important. This includes useful commenting, clarity and
concision,
modularity and organization, and appropriate error checking. See How To Write Unmaintainable Code
for what not to do. Coding assignments will use Java, C++, and/or
C.
Grading will not be based on arbitrary numerical standards, nor will there be a fixed "curve." There is no a priori correspondence between letter grades and numerical scores on the assignments or on the exam. You can evaluate your performance in the class by comparing your scores with the means and standard deviations, which will be announced. However there is also no fixed correspondence between letter grades and standard deviations above or below the mean. If all students do well in the absolute, then all students will get a good grade.
You should not
drop
CSE 150 just because you are unhappy with the score that you receive on
an assignment or the midterm. Instead, you should make an
appointment to discuss with the instructor how you can do better on
following assignments.
The first assignment is due on Wednesday October 13. Here are detailed submission instructions. See these (old) section notes and web board summary for advice about the assignment. Grading uses this score sheet
The second assignment is due on
Monday November 1.
The third assignment is due on
Wednesday November 17. For details, see this grading
guide and these section
notes. Here is the file containing 1200
test messages (link removed).
Most recently updated on December 2, 2004 by Charles Elkan, elkan@cs.ucsd.edu.