• Senders / Actuators : Environment sends -> agent decides -> actuator interacts with the environment.
• Terminology:
  • Fully / Partially observable -> full(no memory required) / partial (stores previous data from perception-action cycle) Sensors can see entire state of the env. (Full)
  • Deterministic / stochastic 1 - outcome is determined by your actions 2 - dice throw / randomness stochastic
  • Discrete / Continuous finite / infinte space of actions/senses
  • Benign / Adversarial Might be random etc. but not out to get you / games - out to get you (adversial is a lot tougher)

• Initial State : actions {s} : Result (s,a) -> s' : Goal Test(s) -> T|F : Path Cost (s->s'->s'') -> n [cost of path] : Step cost (s,a,s') -> n
• Frontier -> the farthest we have explored ; Unexplored region; Explored region.
• Tree Search
  • We stop when the solution is explored, not when it is added to the frontier
  • Breadth-first search
  • Uniform Cost Search
  • Depth First Search - efficient on frontier space, not complete, not optimal
  • A* search = path + heuristic : finds the lowest cost if h never over-estimats the actual cost; A* is optimistic
• auto-generating heuristics by relaxing the problem constraints
• Works when:
  • Domain must be fully observables
  • known - we have to know the set of available actions
  • discrete - finite number of actions
  • deterministic - we have to know the results of our actions
  • static (only our actions can change the world)
• Implementations
  • State, action, cost, parent (node)
  • Linked list representing a path
  • Frontier -> PriorityQueue(add/remove) + MembershipTest(Set)
  • Explored -> Add + membership test

Total Probability

P(B) = ∑_j P(B|A_j) . P(A_j)

Joint Probability

P(X.Y) = P(X|Y). P(Y) = P(Y|X).P(X)

Negation

P(~X|Y) = 1 - P(X|Y) ; Note P(X|~Y) is not valid.

. + Conditional Probability :: P(A | B) = P(A ∩ B) / P(B)

Bayes Theroem

Links conditional prob. to it's inverse.

\begin{equation} \begin{align*} &P(A | B) = \frac{P(B | A).P(A)}{P(B)} \\ &P'(A|B) = P(B|A).P(A) ; P'(~A|B) = P(B|~A).P(~A) \\ &\eta = [P'(A|B) + P'(~A|B)] ^{-1} \\ &P(A|B) = \eta P'(A|B) ; P(A|B) = \eta P'(~A|B) \\ \end{align*} \end{equation}

Solving using the normalized equation

• Given: P(C) = 0.01; P( + | C) = 0.9;P( + | ~C) = 0.2
• Find P( C | ++) =

Conditionally independant

P(T₂ | CT₁) = P(T₂ | C) This does not imply that T₁ and T₂ are independant if we don't know C!

\begin{equation} \begin{align*} P(+_1 \big| +_2) &= P(+_2 \big| +_1,C)P(C \big| +_1) + P(+_2 \big| +_1, \neg C).P(\neg C \big| +_1) \\ &=P(+_2 \big| C). P(C \big| +_1) + P(+_2 \big| \neg C).P( \neg C \big| +_1) \end{align*} \end{equation}

Absolute and Conditional

\begin{equation} A \perp B \implies A \perp B \big| C ? False \end{equation} \begin{equation} A \perp B \big| C \implies A \perp B ? False \end{equation}

Confounding Cause

Two hidden (Sunny, Raise) -> one observable(Happy) P(R|S) = P(R) { Raise and sunny are independant!}

Explain Away: P(R|HS) = Now, being happy (effect) can be explained by it being sunny), hence the probabilty of P(R|HS) < P(R | H)!

Bayes Network

Reduces the number of probabilities requried to describe the network. Each node needs only the incoming arcs. Each node requires 2^k probabilities where k = number of incoming arcs.

D-Separation

If we know a node, anything downstream of the node, is renderd independant of anything upstream of the node.

• Evidence - input; Query - output
• P(Q₁ , Q₂ … | E₁ = e₁, … )
• Most likely explanation: argmax_q P(Q₁ = q₁ , Q₂ =q₂ … | E₁ = e₁, … )
• Not restricted in one direction: Mix-match query/evidence variable
• Inference on Bayes Net (e,a = hidden)
  • Enumeration P(+b| +j, +m) = P(+b,+j,+m)/ P(+j,+m); \Sum_e \Sum_a P(+b,+j,+m)
  • Maximize independance of variables
  • Most efficient went network flows from causes to effects
  • Variable Elimination (NP hard in general; but faster then enumeration)
    • Break into smaller networks
    • Joining Factors - chose two factors and combine them together

• Learn models from data
• What? parameters, structure, hidden concepts
• What From? supervised, unsupervised, reinforcement learning
• What For? prediction, diagnostics, summarization
• How? passive active online offline
• Output? Classification regression
• Details? generative, descriminative
• Supervised Learning
  • Occam's razon : Everything else eing equal - chose the least complex method
  • Maximum Likelihood: