# LectureBlog

Home Assignments Lecture Blog Resources Project Discussion Group

*Note: Right-click on any image to open it in hi-res.*

**Final Exam Review Session: Wed Dec 15**

- CACM feature article on Bayesian networks
- CACM article on latent Dirichlet allocation
- final review video (part 1 of 2)
- final review video (part 2 of 2)
- handwritten notes from review session

**Meeting 41: Fri Dec 10**

- This was the final project expo! Here is a link to the Projects.

**Meeting 40: Wed Dec 8**

- Marvin Minsky guest lecture. Here is a recording of the conversation. Content starts at about the 18 minute mark.

**Meeting 39: Mon Dec 6**

- more on HMMs from earlier handout
- sometimes-fair-casino HMM

**Meeting 38: Fri Dec 3**

- Discuss SoM Ch 20
- Went over Template Project
- Brainstormed questions for MM (see newsgroup)

**Meeting 37: Wed Dec 1**

- Debriefed project plans

**Meeting 36: Mon Nov 29**

- Discuss SoM Ch 19
- intro HMMs
- Minsky will join for Skype chat on Wed Dec 8

**Meeting 35: Wed Nov 24**

- Discuss SoM Ch 18

**Meeting 34: Mon Nov 22**

- final project proposals returned with feedback
- FP Deliverable One Guidelines
- Discuss SoM Ch 17
- Work through AIMA Ch 14 problems 14.1, 14.6, and 14.14

**Meeting 33: Fri Nov 19**

- Discuss literacy and the brain article
- Derive P(Alarm|Earthquake) using Bayes Net theory since we don't have JPD

**Meeting 32: Wed Nov 17**

- Discuss SoM Ch 16
- Intro to Bayes nets

**Meeting 31: Mon Nov 15**

- Discuss SoM Ch 15
- Independence (& 3-pg handout)
- Bayes Nets Attach:91420_543_bayes_nets.pdf

**Meeting 30: Fri Nov 12**

- Discuss SoM Ch 14
- Handed out FinalProjectProposalDocumentSpecs
- rest of semester overview:

November 2010 Su Mo Tu We Th Fr Sa 7 8 9 10 11(12)13 we are here 14 15 16 17 18 19 20 21 22 23 24 xx xx 27 Thanksgiving 28 29 30 1 2 3 4 December 2010 5 6 7 8 9 xx 11 last day of class->FPs due 12 13 14 15 16 xx 18 12/17 8am: final & proj papers due

**Summary:**There is one month left (minus Thanksgiving) + 1 week before final

**Plan:**work on FPs in parallel with last problem set

**FP Schedule:**

- Fri 11/19: FP proposal due (real one)
- Wed 11/24: 1st deliverable
- Fri 12/03: 2nd deliverable
- Fri 12/10: project presentations (working code + 1-pg writeup)
- Fri 12/17: project papers due

**PS4 schedule TBA**

**Meeting 29: Mon Nov 8**

- fpp2 back
- Attach:91420_543_bayes_nets.pdf

**Meeting 28: Fri Nov 5**

**Meeting 27: Wed Nov 3**

- discussed bridge question again (q6 from ps)
- feature functions & linear combinations
- look at feature code in Pac-Man
- upside down flying helicopters (ponies)

**Meeting 26: Mon Nov 1**

- discussed SoM 13
- final project proposal 1 handed back & example proposal & discussion
- final project proposal 2 assigned
- discuss PS3 question 6 -- where is the goal; what is the optimal policy; how do you learn it
- problem with strict Q-learning of states

**Meeting 25: Fri Oct 29**

- reinforcement learning notes handed out
- discussed SoM 12.7-12.12

**Meeting 24: Wed Oct 27**

- Quiz 1 and solutions returned
- look at http://www.sensorsportal.com/HTML/DIGEST/New_Digest.htm for example of AI & sensors
- model-based learning
- model-free learning
- temporal-difference learning
- active learning
- Q-learning

**Meeting 23: Mon Oct 25**

- discuss mouse science NPR story
- go over final project pitch 1 assignment
- policy iteration
- reinforcement learning
- Attach:91420_543_rl.pdf

**Meeting 22: Fri Oct 22**

- quiz

**Meeting 21: Wed Oct 20**

- quiz review
- see repository of Berkeley quizzes here: http://inst.eecs.berkeley.edu/~cs188/sp09/exams/
- don't worry about stuff we didn't do (e.g., CSPs) or stuff that will be tested later (e.g., MDPs)
- everything else is fair game -- these are good questions

**Meeting 20: Mon Oct 18**

- SoM 11.1 - 11.4 discussed
- alternation between q-values being computed and state values being updated in Bellman value iteration algorithm
- discussed how varying noise, discount, and reward parameters can lead to different paths, per question 3
- looked at the code for PS3a

**Meeting 19: Fri Oct 15**

- assignments update: PS3a assigned; Quiz 1 Oct 22
- SoM 10.5-10.9 discussed
- Bellman equations and value iteration
- policy iteration

**Meeting 18: Wed Oct 13**

- http://www-inst.eecs.berkeley.edu/~cs188/pacman/projects/reinforcement/reinforcement.html
- Recap MDPs (slide 15)
- High-low game
- Q-values vs. state values
- demo of value iteration
- solving with value iteration
- policy iteration
- Attach:91420_543_MDPs.pdf

**Meeting 17: Tue Oct 12**

- Bytes and Brains discussion
- What is a Markov process? Each chance is independent of previous events
- Additive vs. discounted methods for calculating utility (γ as discount factor)
- Policy: pre-determined series of choices for actions given state
- Expected utility: sum over states given policy choices, probabilities, and discounting
- Attach:91420_543_MDPs.pdf

**Meeting 16: Fri Oct 8**

- PS1c returned
- NYT “NELL” article
- Attach:91420_543_meu_utilities.pdf
- more about Expectimax
- utility functions and maximum expected utility
- cash example
- Gridworld and Markov Decision Processes

**Meeting 15: Wed Oct 6**

- demo won't eat one-dot problem
- SoM 10.1 - 10.4
- alpha-beta
- expectimax & demo

**Meeting 14: Mon Oct 4**

- Fred's SoM example (walk through the woods)
- SoM 9.x
- talked through what's required to deal with multiple ghosts in minimax
- tried to figure out why Pac-Mac doesn't food when it can (turns out that this only occurs when there's exactly one nearby dot; he doesn't care if he eats it now or later)

**Meeting 13: Fri Oct 1**

- went over
`reflexAgent`

code - “When Pac-Man believes that his death is unavoidable, he will try to end the game as soon as possible because of the constant penalty for living.”

**Meeting 12: Wed Sep 29**

- Adversarial search! Multi-Agent project
`⚠ (:html:) <a href="http://inst.eecs.berkeley.edu/~cs188/fa09/slides/FA09%20cs188%20lecture%206%20%2d%2d%20adversarial%20search%20(2PP).pdf">Berkeley minimax slides</a> (:htmlend:)`

... starting at Slide 19 / Page 10 of PDF- Attach:adversarial.txt
- tic-tac-toe game tree
- min-max example
- alpha-beta example
`⚠ (:html:) <a href="http://inst.eecs.berkeley.edu/~cs188/fa09/slides/FA09%20cs188%20lecture%207%20--%20expectimax%20search%20(2PP).pdf">Berkeley alpha-beta pruning slides</a> (:htmlend:)`

**Meeting 11: Mon Sep 27**

- PS1c due Wed; grad student papers due Fri
- relaxed problems Attach:relaxed.txt slides 31+ showing 8-puzzle & heuristics
- comparing performance of IDS, heuristic h1 (# of misplaced tiles), & heuristic h2 (sum of Manhattan distances over all tiles)
- another intuitive way of understanding
*admissible*: never leads you astray by telling you things are worse than they are. This would cause you to prune a subbranch that would otherwise be explored, if the heuristic weren't telling you things were bad this way. - Berkeley food search problem

**Meeting 10: Fri Sep 24**

- handed out solution code for
`aStarSearch`

,`Node`

, and`graphSearch`

(do not redistribute) - handed out
`starterCornersHeuristic.py`

- tried large constant heuristic on CornersHeuristic -> same as using zero as the heuristic
- tried using a random number as the heuristic -> expanded fewer nodes, but found worse solutions
- used distance to nearest corner as heuristic (idea we had previously, as implemented in
`starterCornersHeuristic`

) and it was better than UCS: found optimal solution with fewer nodes expanded - had long conversation about what is the impact of the heuristic value going down as a food dot gets eaten (does it get eaten as the search expands? yes.) in the context of talking about a
*consistent*vs. a merely*admissible*heuristic - yes, the “distance to nearest corner” heuristic is lame (and we knew that) because it is not consistent, but (a) it's an admissible heuristic and (b) it does improve things over UCS
- what are better heuristics? something that's also consistent, involving TSP search over remaining dots? Distance to nearest + distance from that dot to another (if there are more than one left)?

**Meeting 9: Wed Sep 22**

- PS1a graded & handed back
- how did PS1b go?
`CornersProblem`

solution handed out in hard-copy form – please do*not*redistribute electronically in any fashion- recap:
- complete == will always find solution if there is one (DFS is not if search space is infinite)
- optimal == will always find best solution if there are more than one
- heuristic: if admissible, never overestimates, then, can provably avoid expanding nodes that are demonstrably bad while expanding nodes that may still be better, thereby guiding complete & optimal search to be more (optimally) efficient

- read through
`CornersProblem`

code, and figured out the evil line of code that simultaneously determines if a given action will take us to a corner, and then rebuilds the visited-array:

`newVisited = tuple([v or (nextx,nexty) == corner for v, corner in zip(visited, self.corners)])`

- then realized that the state representation for the CornerSearch problem is a two-element array
`[pos, visited]`

, where`pos`

is an x,y coordinate and`visited`

is a 4-element list of true/false values, indicating whether the corresponding corner has been visited.

**Meeting 8: Mon Sep 20**

- Attach:lec8-notes.txt
- started the
`CornersProblem`

with heuristics problem - proposed distance to nearest corner as a heuristic
- discovered properties of heuristics: (a) must be fcn of state, so they tell you where to go, (b) must be easily calculable

**Meeting 7: Fri Sep 17**

- has search infected your thinking? e.g., CS prereq flow chart and 91.420 pre-reqs
- 2nd Edition Chapter 4 slides on greedy best-first search and A*
- difference between (greedy) best-first search and A*
- Project 1B
- Attach:lec7-notes.txt

**Meeting 6: Wed Sep 15**

- Informed (heuristic) search: A* search
- solving the IGVC Nav Challenge with A*

**Meeting 5: Mon Sep 13**

**Meeting 4: Fri Sep 10**

- recap again def'n of search problem
- walk thru a breadth-first and depth-first search
- python intro
- Attach:util.py.pdf Attach:search.py.pdf
- running the
`tinyMazeSearch`

-- it just outputs a fixed list of directions - delving to
`depthFirstSearch`

**Meeting 3: Wed Sep 8**

- discussed SoM Chap 2
- recap definition of search problem
- discussed Assignment 1: Snakes & Ladders, Tantrix, and Rush Hour
- presented GENERAL-SEARCH algorithm (page 20 of 1st edition chapter 3 slides)
- presented Node data structure for solving search
- discussed “fringe” (2nd edition) aka “frontier” (3rd edition): collection of unexpanded nodes
- talked through TREE-SEARCH algorithm (page 30 of 2nd edition chapter 3 slides)
- Attach:lec3-notes.txt

**Meeting 2: Fri Sep 3**

- sign up for Google Group at the class home page
- tweet using
`@fgmart`

- Attach:lec2-notes.txt
- adjacent fields to AI
- Computational Sustainability AI
- properties that make it search: observable environment, discrete states, deterministic actions
- definition of search problem: an initial state, a set of actions (as a fcn of state), transition model (aka, successor fcn of state and action), goal test, and path cost.
- analyzed Arad-Bucharest map, with and without path costs noted
- straight-line distances will be useful in heuristic search (which we will do later) – now, we're doing
*uninformed search.*

**Meeting 1: Wed Sep 1**

- how to get textbooks (buy them used w/link on course home page)
- course policies and syllabus
- approach for working with Minsky SOM text (daily readings and daily "tweet"-style writeups)
- what is AI? see discussion on whiteboard
- Russell and Norvig's agent model of AI (Chap 2 stuff)
- Berkeley AI class's quick history of AI