Ai Final

Front 1

Frequentist view of probability

Back 1

Probabilities come from relative frequencies

Front 2

Subjectivist view of probability

Back 2

Probabilities are degrees of belief

Front 3

Expectation equation

Back 3

Front 4

Independence of A and B

(and & or)

Back 4

P(A and B) = P(A)P(B)

P(A or B) = P(A) + P(B) - P(A)P(B)

Front 5

Mutual exclusion of A and B

(and & or)

Back 5

P(A or B) = P(A) + P(B)

P(A and B) = 0

Front 6

Conditional probability

P(a|b)

Back 6

Front 7

Bayes Rule

Back 7

Front 8

JPD

Back 8

Joint probability distribution

Front 9

Joint distributions

Back 9

P(X1, …, Xn)

From this you can infer P(X1), P(X1|Xs) etc.

Front 10

What are joint distributions useful for?

Back 10

Classification

- P(X1 | X2 … Xn)

Co-occurence

- P(Xa, Xb)

Rare event detection

- P(X1, …, Xn)

Front 11

Conditional independence of A and B

Back 11

P(A|B, C) = P(A|C)

P(A, B|C) = P(A|C) P(B|C)

Front 12

Bayes Nets

Given ____, each RV independent of ____

Back 12

Given parents, each RV independent of non-descendants

Front 13

CPT

Back 13

Conditional probability table

(use in Bayes Nets)

Front 14

JPD decomposes to...

P(x1, ..., xn)

Back 14

Front 15

What does the CPT show? (equation)

Back 15

Front 16

Naive Bayes

Back 16

Want to find

P(S|W1 … Wn)

Front 17

Sampling the conditional (2 approaches)

Back 17

Rejection sampling

- Sample, throw away when mismatch occurs (B != b)

Importance sampling

- Bias the sampling process to get more “hits”

- Use a reweighing trick to unbias probabilities

Front 18

PDF

Back 18

probability density function

Front 19

How to use a PDF (equation)

Back 19

Front 20

Markov assumption

Back 20

State at t depends only on state at t-1

(Future independent of past given present)

We can write

P(St|St-1, St-2, ..., S0) as

P(St|St!1)

Front 21

Markov model

Back 21

A model operating under the Markov assumption

Front 22

Markov chain

Back 22

Sequence of events generated by Markov model

Front 23

Assumptions for state machine (Markov model)

Back 23

- Markov assumption

- Transition probabilities don’t change with time

- Event space doesn’t change with time

- Time moves in discrete increments

Front 24

HMM

Back 24

Hidden Markov Model

Front 25

Uses for HMM

Back 25

Monitoring/Filtering

- P(St | E0 … Et)

- Estimate patient disease state

- Where is the robot?

Prediction

- P(St | E0 … Ek), k < t

- Where will the robot be in 3 steps?

Smoothing

- P(St | E0 … Ek), k > t

- Where was the robot at t=3?

Most likely state sequence

- What was the robot's path?

Front 26

Viterbi Algorithm

Back 26

P(S0) = P(S0 | O0)

P(S1) = P(S0) P(S1 | S0) P(S1 | 01)

= P(S0 | O0) P(S1 | S0) P(S1 | 01)

...and recurse

Front 27

PDDL

Back 27

Planning Domain Description Language

Front 28

Components of PDDL

Back 28

Domain - describes a class of tasks

- Predicates

- Operators

Task - an instance of domain

- Objects

- Start and goal states

Front 29

PDDL

Predicate

Back 29

Given object(s), returns T/F

Front 30

PDDL

Operator

Back 30

Operator has:

- Name

- Parameters

- Preconditions

- Effects

*Note: Markov assumption

Front 31

PDDL

State

Back 31

Describe the world at a moment in time

Conjunction of positive literal predicates

Those not mentioned assumed to be false (closed world assumption)

Front 32

PDDL

Goal

Back 32

Partial state expression

Conjunction of literal predicates

Those not mentioned are don’t-cares

Front 33

When executing an action in PDDL...

Back 33

- Check preconditions

- Delete negative effects

- Add positive effects

Front 34

Planning approaches

Back 34

Forward search

- Need a heuristic or it's hopeless

FFPlan

- Relaxation - make the problem easier

Regression planning

- Start at goal, regress backward, reversing operators

Front 35

MDP

Back 35

Markov Decision Process

Front 36

Components of MDP

Back 36

S set of states

A set of actions

γ discount factor

R reward function

- R(s, a, s′)

T transition function

- T(s′|s, a)

Front 37

Absorbing state

Back 37

Execution stops

Front 38

Markov property for MDPs (extended)

Back 38

s_t+1 depends only on s_t and a_t

r_t depends only on s_t and a_t

Front 39

Goal of MDP is to find a ____ that maximizes ____

Back 39

Goal of MDP is to find a policy that maximizes return (expected sum of rewards/min sum of costs)

Front 40

Policy (equation)

Back 40

Front 41

Return (equation & def)

Back 41

Max expected sum of rewards

Front 42

Policy vs. Plan

Back 42

Policy: an action for every state

Plan: a sequence of actions

Front 43

Optimal policy (equation)

Back 43

Front 44

VF

Back 44

Value function

Front 45

Value function

Back 45

Front 46

Bellman's equation

Back 46

Front 47

PPDDL

Back 47

probabilisticproblem domain definition language

Now operators have probabilistic outcomes

Front 48

Machine learning

Back 48

Using experience to improve performance on some task

Front 49

Types of learning

Back 49

Supervised learning

Labeled data

Unsupervised learning

No feedback, just data

Reinforcement learning

Sequential data, weak labels

Front 50

Supervised learning

Back 50

Given training data:

X = {x1, …, xn} inputs

Y = {y1, …, yn} labels

Produce decision function

f : X -> Y

That minimizes error:

Σ err(f(xi), yi)

Front 51

Classification vs. Regression

Back 51

Set of labels Y

Y is discrete = Classification

- Minimize number of errors

Y is real-valued = Regression

- Minimize sum squared error

Front 52

Hypothesis space

Back 52

Class of functions F, from which to find f that minimizes error

Front 53

Why test/train split?

Back 53

Do not measure error on the data you train on! May not generalize.

Fit f using training set

Measure error on test set

Front 54

Decision trees

Back 54

- If all the labels are the same, we have a leaf node

- Pick an attribute and split data on it

- Recurse on each half

Front 55

Information gain

Back 55

Front 56

Perceptron equation

Back 56

𝑓(𝒙) = 𝑠𝑖𝑔𝑛(𝒘 ∙ 𝒙 + 𝑐)

𝑓(𝒙) : function of the perceptron

𝑠𝑖𝑔𝑛(𝑧) : returns true if 𝑧 ≥ 0, false otherwise

𝒙 : vector of inputs

𝒘 : vector of perceptron’s weights

𝑐 : bias

Front 57

Perceptrons - how they work

Back 57

For x = [x(1), … , x(n)]: [inputs]

- Create an n-d line

- Slope for each x(i) [weights]

- Constant offset [bias]

Front 58

Perceptron Algorithm

Back 58

Set w and c to 0

for each xi:

---predict zi = sign(w.xi + c)

---if zi != yi:

-------w = w + a(yi - zi)xi

a = learning rate

Converges if linearly separate.

Front 59

Probabilistic classifier

Back 59

Logistic regression

??????

Front 60

K nearest neighbors

Back 60

Distance metric D(xi, xj)

For a new data point x_new:

- Find k nearest points in X (measured via D)

- Set y_new = the label that the majority of those neighbors have

Front 61

Unsupervised learning

Back 61

Given inputs:

X = {x1, …, xn}

Try to understand thestructure of the data.

Front 62

Clustering

Back 62

Split data into discrete clusters (types)

Given:

Data points X = {x1, …, xn}

Find:

- Number of clusters k

- Assignment function f(x) = {1, …, k}

* can answer "which cluster", but not "does this belong"

Front 63

k-means

Back 63

- Pick k

- Place k points (“means”) in the data

- Assign new point to ith cluster if nearest to ith “mean”

Front 64

k-means algorithm (decide where to put the means)

Back 64

- Place k “means” at random

- Assign each point in the data to closest “mean”

- Move “mean” to mean of assigned data

Front 65

GMM

Back 65

Gaussian mixture model

Front 66

PCA

Back 66

Principle Components Analysis

Project data into a new space

- Dimensions are linearly uncorrelated

- Measure of importance for each dimension

Front 67

Reinforcement learning

Back 67

Learning how to interact with anenvironment to maximize reward.

Learning counterpart of planning

Front 68

Goal of reinforcement learning

Back 68

Find policy π that maximizes expected return (sum ofdiscounted future rewards)

Front 69

Reinforcement in relation to MDP

Back 69

S set of states

A set of actions

γ discount factor

R reward function

- R(s, a, s′)

T transition function

- T(s′|s, a)

*** don't know R and/or T ***

Front 70

optimal policy (π)

Back 70

Maximizes thereturn from every state

Front 71

Value function

Back 71

Value of state s under policy π

- Estimate reward

- Improve policy