# CS188 Notes Part 2 # Lecture 13: 10/15/19 ## Uncertainty * Observed variables: Agent knows things about the state (sensor readings) * Unobserved variables: Agent reasons about other aspects (where an object is) * Random variables * Note that $+r$ means True, $-r$ means False * Probability distributions * Marginal distributions: sub-tables that eliminiate variables * "Summing out" is marginalization over a variable * Conditional probabilities * $P(a|b) = \frac{P(a,b)}{P(b)}$ * Select joint probabilities matching the evidence * Then normalize the section ## Probabilistic Inference * Compute a desired probability from other known probabilities (ex. conditional from joint) * Probabilities change with new (given) evidence * Inference by enumeration * Evidence variables: $E_1, \ldots E_k$ * Query variables: $Q$ * Hidden variables: $H_1, \ldots H_r$ * We want $P(Q | e_1, \ldots e_k)$ * Steps * 1) Select entries consistent with evidence * 2) Sum out H to get joint of Query and evidence * 3) Normalize ($\frac{1}{P(Q)}$) * Time: $O(d^n)$ * Space: $O(d^n)$ * Sometimes have conditional dist but want joint * Product rule: $P(y)P(x|y) = P(x,y)$ * Chain rule: $P(x_1, x_2, \ldots x_n) = \Pi_i P(x_i | x_1 \ldots x_{i-1})$ * Bayes' Rule: $P(x,y) = P(x|y)P(y) = P(y|x)P(x)$ * $P(y) = \sum\limits_{x'} P(y|x')P(x')$ # Lecture 14: 10/22/19 ## Bayes' Nets * Models are always simplifications of the world * Use probabilistic models to reason about unknown variables * Absolute/unconditional independence * If $X \perp\!\!\!\perp Y, P(x,y) = P(x)P(y)$ * Conditional independence * $\forall x,y,z:P(x, y | z) = P(x | z) P(y | z)$ * Equivalently, $P(x|z, y) = P(x| z)$ * Joint distribution tables are too large to explicitly represent * Hard to learn anything empirically more than a few variables at a time * Bayes' Net: technique for describing complex joint distribution (model) using conditional probabilities * Graphical model, how variables locally interact ### Graphical Model Notation * Bayes net = DAG + conditional probability table (CPT) * $P(X | a_1, \ldots a_n)$ * Nodes: 1 per variable (with domains) * Can be assigned (observed) or unassigned (unobserved) * Arcs: interactions/direct influence between variables * Encode conditional independence * Absolute independence = no interactions between variables * Implicitly encode joint distributions * Product of local conditional distributions * $P(x_1, x_2, \ldots x_N) = \Pi^{n}_{i=1}P(x_i|parents(X_i))$ * Not every BN can represent every joint distribution # Lecture 15: 10/24/18 ## Inference by Enumeration in BN * Evidence variables: Evidence you have observed * Query variables: Probability you want * Hidden variables: Not observed * $P(B | +j, +m) \propto_B P(B, +j, +m)$ * $= \sum\limits_{e,a}P(B, e, a, +j, +m)$ * $= \sum\limits_{e,a} P(B)P(e)P(a|B,e)P(+j|a)P(+m|a)$ * Computing the joint distribution is time and memory intensive * Track factors called factors * Procedure: Join all factors, eliminate hidden variables, normalize * 1) Join: $\forall r,t: P(r,t) = P(r)P(t|r)$ * 2) Eliminate/marginalize. Take hidden variables out * Projection operation ## Variable Elimination * NP-hard but tends to be much faster * Cannot solve 3-SAT * Inference by enumeration: $\sum\limits_t \sum\limits_r P(L|t)P(r)P(t|r)$ * Variable elimination $\sum\limits_t P(L|t) \sum\limits_r P(r)P(t|r)$ * Interleave joins and elimination * Eliminate all hidden variables * Normalize at the end * Moving summations as right as possible * Elimination order matters * Doesn't always exist an ordering with small factors # Lecture 16: 10/29/19 * Independence in a BN * Yes: Prove using algebra * No: Give a counterexample * Typically look for independence relations from the graph structure (the numbers could just work out that way) ## Independence Properties * Study independence properties for triples * For 1: Never independent of self * For 2: Just look if there is an edge * For 3+: Can be reduced to triples of these canonical chains * 1) Causal Chains * $P(x,y,z) = P(x)P(y|x)P(z|y)$ * Not guaranteed $X \perp\!\!\!\perp Z$ * Guaranteed $X \perp\!\!\!\perp Z | Y$ * 2) Common Cause * $P(x,y,z) = P(y)P(x|y)P(z|y)$ * Not guaranteed $X \perp\!\!\!\perp Z$ * Guaranteed $X \perp\!\!\!\perp Z | Y$ * 3) Common Effect * $P(x,y,z) = P(x)P(y)P(z|x,y)$ * Guaranteed $X \perp\!\!\!\perp Z$ * NOT guaranteed $X \perp\!\!\!\perp Z | Y$ * Observing an effect activates influence between causes ## D-Separation * Reachability is not enough (fails for common effects) * $X \perp\!\!\!\perp Y | Z$ if X and Y are d-separated by Z * Consider all undirected paths from X to Y * No active paths = independent * Active path if each triple is active * Causal chain: A->B->C where B is unobserved * Common cause: A <- B -> C where B is unobserved * Common effect: A -> B <- C where B or one of its descendents is OBSERVED * A single inactive segment can block a path * If 1 or more path is active, independence not guaranteed * If all paths are inactive, independence guaranteed ## Topology Limits Distributions * Fully conditioning can encode any distribution # Lecture 17: 10/31/19 ## Sampling * Repeated simulations * Draw N samples from a sampling distribution S * Compute an approximate posterior probability which converges to true probability P * 1) Get sample u from uniform distribution $[0, 1)$ * 2) Divide the interval into subintervals equal to size of probability ## Prior Sampling * 1) Run through nodes in topological order * Sample $x_i$ from $P(X_i | Parents(X_i))$ * 2) Return ($x_1, x_2, \ldots x_n$) * Sampling procedure is consistent * If we do procedure long enough, it converges * Monte Carlo Estimation: Estimate expected value of f(X) ## Rejection Sampling * Only consider samples that match evidence * Input: evidence instantiation * 1) Run through nodes in topological order * Sample $x_i$ from $P(X_i | Parents(X_i))$ * 2) If $x_i$ not consistent with evidence, reject it * 3) Return ($x_1, x_2, \ldots x_n$) * Sampling procedure is consistent * Problem: If evidence is unlikely, reject lots of samples ## Likelihood Weighting * Fix evidence variables, sample the rest * Problem: Sample distribution is not consistent * Solution: Weight by probability of evidence given parents * Algorithm * 1) Instantiate weights to be 1 * 2) Run through nodes in topological order * If $x_i$ is an evidence variable, * $X_i =$ observation of $x_i$ for $X_i$ * Set $w = w * P(X_i | Parents(X_i))$ * Else: $x_i$ from $P(X_i | Parents(X_i))$ * 3) Return ($x_1, x_2, \ldots x_n$), w * Problem: Evidence influences choice of downstream variables, but not upstream variables ## Gibbs Sampling * 1) Fix evidence variables * 2) Start with random instantiation. * 3) Resample X from P(X | rest of variables) * Sample 1 variable at a time conditioned on the rest * Idea: No hidden variables # Lecture 18: 11/5/19 ## Decision Networks * Maximize Expected Utility (MEU) * Bayes net with nodes for utility * Calculate expected utility for each action * Chances nodes, action nodes, utility nodes * Procedure * 1) Instantiate all evidencce * 2) Select action nodes along the way * 3) Calculate posterior for all parents * 4) Calculate expected utility for each action * 5) Choose maximizing action * Value of information = expected gain in MEU with new info * When you get evidence, your MEU might be less * But now you can make the correct decision knowing that life sucks ## Value of Perfect Information * MEU(F=bad) + MEU(F=good) - MEU(none) * $VPI(E' | e) = \left(\sum\limits_{e'}P(e'|e)MEU(e,e') \right) - MEU(e)$ * $MEU(e) = \max\limits_a \sum\limits_sP(s|e)U(s,a)$ * Properties * VPI is always nonnegative * VPI is nonadditive * $VPI(E_j, E_k | e) \neq VPI(E_j|e) + VPI(E_k|e)$ * VPI is order independent * $VPI(E_j, E_k | e) = VPI(E_j|e) + VPI(E_k|e, e_J)$ in any order # Lecture 19: 11/7/19 ## POMDPs * Observation function $O(s,o) = P(o|s)$ * POMDPs are MDPs over belief states b * One way to solve: Use truncated expectimax for approximate values of actions * VPI based agent ## Hidden Markov Models * Reasoning about a sequence of observations over time * Value of X at a given time is called the state * Parameters: transition probabilities/dynamics show how state evolves over time * Stationary assumption: transition probabilities the same at all times * Initial distribution $P(X_1)$ * Transitions: $P(X_t | X_{t-1})$ * Emissions: $P(E_t, X_t)$ * Markov hidden process: Future depends on past via the present * Current observation is independent of everything else given current state ## Mini-Forward Algorithm * Find $P(X)$ on some day t * $P(x_t) = \sum\limits_{x_{t-1}} P(x_t | x_{t-1})P(x_{t-1})$ * Can converge as $t \to \infty$ * Stationary distribution: $P_\infty = P_{\infty + 1}$ # Lecture 20: 11/12/19 * Localization: Only 1 sensor reading could be wrong. Compute probability distribution of where robot can be * $B(X_T) = P(X_T|e_1\colon t)$ ## Inference (Passage of time) * Current belief $B(X_T) = P(X_T|e_{1\colon t})$ * After 1 time step: $P(X_{t+1}|e_{1 \colon t})$ * Prediction of new time step from old evidence * $B'(X_{t+1}) = \sum_{x_t} P(X'|x_t)B(x_t)$ * No $e_{t+1}$ ## Observation * We have current belief $B'(X_{t+1}) = \sum_{x_t} P(X'|x_t)B(x_t)$ * New evidence comes in: $P(X_{t+1}|e_{1\colon t+1}) \propto P(X_{t+1}, e_{t}|e_{1\colon t+1})$ * $= P(e_{t+1}|e_{1\colon t}, X_{t+1})P(X_{t+1}|e_{1\colon t})$ * Or compactly, $P(X_{t+1}|e_{1\colon t+1}) \propto P(e_{t+1}|X_{t+1})B'(X_{t+1})$ * Must renormalize ### Forward Algorithm * $P(x_t|e_{1\colon t}) = P(e_t | x_T) \sum\limits_{x_{t-1}} P(x_t|x_{t-1})P(x_{t-1}, e_{1\colon t-1})$ ## Particle Filtering * Just use sampling instead of dealing with exact beliefs * Good if $|X|$ is too big to store in memory (if X is continuous) * Track samples of X, not all values * Time per step is linear in the number of samples * Generall N particles << $|X|$ * $x' = sample(P(X'|x))$ * Captures passage of time * Observation: * Compute a weight for each particle of how likely is based on evidence * $B(X) \propto P(e|X)B'(X)$ * Resample: * Resample particles to go back to all weight 1 particles * Resample N times from weighted sample distribution (equivalent to renormalizing) ## Dynamic Bayes Nets (DBNs) * Track multiple variables over time using multiple evidence * Idea: Repeat a fixed Bayes net structure at each time # Lecture 21: 11/14/19 ## Classification * Spam vs ham prediction of new future emails * Features: * Text Patterns, words * Other features unrelated to email content: Sender in contacts * Ex. Digit recognition * Get a large collection of example images, labeled * Want to learn to predict labels of new, future digit images * Features: pixels, num components, aspect ratio, numloops ## Model based classification * Naive bayes: Assume all features are independent of label * Inference: Get joining probability distribution * Count the probability that each pixel is on for that label * Bag of words model: Features = Wi is word at position i * Insensitive to word order or reordering * Weight each word along the way to give a total score for spam vs ham ## Training vs Test * Training set, Held out set, test data * Use test data to get a sense of accuracy in the real world * Features: attribute-value pairs to characterize each x * Never peek at the test set * Evaluation: * Accuracy: fraction of instances predicted correctly * Don't want false positives * Friend classified as a gorilla * Overfitting: * When you try to maximize accuracy on training data * Odds ratio of infinity blows up ## Parameter Estimation * Estimating the distribution of a RV * Elicitation: ask a human * Empirically: use training data (learning) ### Maximum Likelihood Estimation * Data: Observed set D of heads and tails * Hypothesis space: binomial distributions * Learning: Finding $\theta$ is an optimization problem * MLE: $\hat{\theta} = arg\max_{\theta} \ln \theta^{\alpha_H} (1 - \theta)^{\alpha_T}$ * $= \frac{\alpha_H}{\alpha_H + \alpha_T}$ * Another option is to consider the most likely parameter value given the data ## Laplace Smoothing * Pretend that you saw every outcome once more than you actually did * Avoids the division by 0 problem * Extended laplace estimate: pretend we saw everything $k$ times * Tuning on held out data * Learn parameters from training data * Tune hyperparamaters on different data * For each value of hyperparameters, train and test on held out data * Choose the best value, do a final test on test data # Lecture 22: 11/19/19 * Reinforcement Learning vs Supervised Learning * RL finds policy - mapping from states to actions ## Perceptron * Inputs are feature vectors * Each feature has a weight, sum is the activation * Activation(x) = $w \cdot f(x)$ * Positive outputs +1, negative output -1 * Weight updates * Start with weights = 0 * For each training instance: * Classify current weights * If correct, don't do anything. If wrong, adjust the weight vector ($w = w + y^* \cdot f$) * Add/subtract the feature vector ## Multi-Class Perceptron * For multiclass, there is a weight vector for each class * Score of class y: $w_y \cdot f(x)$ * Prediction highest score wins: $y = arg \max\limits_y w_y \cdot f(x)$ * Algorithm: * Start with weights all 0 * Pick up training examples 1 by 1 * Predict with current weights * If wrong, $w_y = w_y - f(x)$, $w_y^* = w_y^* + f(x)$ ## Properties * Separability: true if some parameters get the training set perfectly correct * Convergence: if the training is separable, perceptron will eventually converge (binary case) * Mistake bound: $\frac{k}{\delta^2}$ ## Problems * If data is not separable, weights might thrash * Averaged perceptron can help * Mediocre generalization sometimes barely finds the solution * Overtraining/overfitting * Non-separable case: use probabilistic decision * Very positive score, probability close to 1 * Sigmoid function: $\phi(z) = \frac{1}{1+e^{-z}}$ ## MLE * $\max\limits_w ll(w) = \max\limits_w \sum\limits_i \log P(y^{(i)} | x^{(i)}, w)$ # Lecture 23: 11/21/19 ## Gradient Ascent * Perform update in uphill direction for each coordinate * For $g(w_1, w_2)$ * $w_1 \leftarrow w_1 + \alpha \frac{\partial g}{\partial w_1}(w_1,w_2)$ * $w \leftarrow w + \alpha \nabla_w g(w)$ * $g(w) = \sum\limits_i \log P(y^{(i)} | x^{(i)}, w)$ * Keep doing this until update changes $w$ by around $0.1 - 1\%$ * Can't make $\alpha$ too big * Mini-batch gradient ascent: compute gradients for points in parallel * Stop when log likelihood of hold-out data begins to decrease ## Neural Networks * 2 layer neural network can approximate any continuous function * Last year = still logistic regression * More layers before this last layer * Feasure are learned rather than hand-designed # Lecture 24: 12/3/19 ## Deep Neural Networks * Softmax: $P(y_1| x; w) = \frac{e^{z_1}}{e^{z_1} + e^{z_2} + e^{z_3}}$ * Deep neural network: $\max\limits_w ll(w) = \max\limits_w \sum\limits_i \log P(y^{(i)}| x^{(i)}; w)$ * w is just a much larger vector * Run gradient ascent, stop when log likelihood of hold out data starts to decrease * Covariate shift: correlations present in train data not in test data ## Inverse RL * Usually we try to find an optimal policy * Inverse planning: We see optimal behavior and try to recover the reward function that demonstrates the reward behavior * Reward engineering is hard, try demonstrating behavior and extract reward function * Aka inverse planning, inverse optimal control * More causal model of learning ## IRL Formulation * Given $\xi_D$, find $R(s,a) = \theta^T \phi(s,a)$ such that $R(\xi_D) \geq \max\limits_\xi R(\xi)$ * But 0/constant reward ends up being a solution * Maximum Margin Planning * $R(\xi_D) \geq \max\limits_\xi R[\xi + l(\xi, \xi_D)]$ * Search for a reward function giving a bonus to trajectories farther from the demonstration * Makes it a little more difficult to pick the demonstration * $\max\limits_\theta[\theta^T \phi(\xi_D) - \max\limits_\xi [\theta^T \phi(\xi) + l(\xi, \xi_D)]]$ * $\xi_\theta^*$ is arg max * Taking gradient is hard because there's a max nested * Take a subgradient: Pick different directions * $\nabla_\theta = \phi(\xi_D) - \phi(\xi^*_\theta)$ * What if the demonstrator is not optimal? * Bayesian view: $P(\xi_D | \theta)$, run inference on $\theta$ * Use softmax: $P(\xi_D | \theta) \propto e^{\beta \theta^T \phi(\xi_D)}$ * Bayesian belief update using demonstration as evidence * Maximum Entropy RL just looks at maximum likelihood estimate