Final

Question 1

Quiz: PCA vs ICA

Answer 1

• Mutually Orthogonal
  
  • PCA
• Mutually Independent
  
  • ICA
  • uncorrelated ends up being independent for certain distributions (so PCA could find independent features, but not as a fact)
• Maximal Variance
  
  • PCA
  • NO on ICA
    
    • independent variables would be combined for maximal variance (central limit theorem)
• Maximal Mutual Information
  
  • ICA
    
    • Maximize joint mutual info between original and transformed features
• Ordered Features
  
  • PCA
    
    • eigenvalues ordered by variance
  • Not for ICA
    
    • kurtosis can be used to order but generally order is not considered
• Bag of Features
  
  • ICA

Question 2

Definition of Utility (U)

Answer 2

U(s) = R(s) + gamma * max_a sum_s’ [T(S,a,s’) U(s’)]

Long term value of being in a state

Question 3

What to do when we are facing Tit For Tat?

Answer 3

• Always defect
  
  • best for low gamma
• always cooperate
  
  • best for high gamma

Question 4

Way to implement feature selection for wrapping

Answer 4

• Hill Climbing
• Randomized Optimization
• Forward/Backward Selection

Question 5

How do ICA and PCA differ?

Answer 5

• ICA
  
  • solves blind source separation problem
  • directional
  • images
    
    • finds noses, mouth, hair
    • local “parts of”
  • natural scenes
    
    • finds edges
    • independent components of the world are edges
  • documents
    
    • gives topics
  • can understand fundamental features of data
  • about probability, information theory
  • more expensive, doesn’t always produce answer
• PCA
  
  • not directional
  • images
    
    • finds direction of maximal variance (brightness)
    • finds the average face next
    • global
  • natural scenes
    
    • brightness
    • average scene
  • about linear algebra

Question 6

What is KL Divergence

Answer 6

Measures the difference between any two distributions (distance measures)

Question 7

Impossibility Theorem

Answer 7

• No clustering scheme can achieve all three of:
  
  • richness
  • scale invariance
  • consistency
• Mutually contradictory properties
• Can re-define the properties and get *nearly* all 3

Question 8

Relevance

Answer 8

Feature xi

• Xi is strongly relevant if removing it degrades BOC (Bayes Optimal Classifier, best on avg, weighted avg of hypotheses)
• Xi is weakly relevant if
  
  • not strongly relevant
  • there exists subset of features that adding Xi improves BOC
• Otherwise Xi is irrelevant

Measures effect on BOC

Relevance ~ Information

Question 9

Minimax

Answer 9

• 2 agents A, B
  
  • A considers worst case counter while maximizing own value
  • B considers worst case counter while minimizing A value
• Finding the maximum minimum or minimum maximum

Question 10

prisoners dilemma

Answer 10

The prisoner’s dilemma is a standard example of a game analyzed in game theory that shows why two completely rational individuals might not cooperate, even if it appears that it is in their best interests to do so

Question 11

Issues with SLC

Answer 11

• Using the distances (closest) only can result in weird cluster shapes (stringy clusters because they are in the same cluster if they are close anywhere)

Question 12

Repeated Games and the Folk Theorem

Answer 12

• In repeated games, the possibility of retaliation opens the door for cooperation
• Folk Theorem Definition (math):
  
  • Results known, at least to experts in the field, and considered to have established status, but not published in complete form
  • Everybody knows, no one gets credit, in the cloud of understanding
• Folk Theorem Definition (game theory):
  
  • Describes the set of payoffs that can result from Nash strategies in repeated games
  • Any feasible payoff profile that strictly dominates the minmax/security profile can be realized as a Nash equilibrium payoff profile, with sufficiently large discount factor.

Question 13

KMeans as Optimization - Definition

Answer 13

• Configurations
  
  • Center, P
• Scores
  
  • Err(P, center) = sum_x ( euclidean distance(Center_P(x) - x) )
• Neighborhood
  
  • P, center = set of pairs
    
    • (P’, center) U (P, center’ )
      
      • change one or the other
• A lot like Hill Climbing

Question 14

Desirable Clustering Properties

Answer 14

• Richness
  
  • For any assignment of objects to clusters, there is some distance matrix such that partition returns that clustering
  • all inputs (distance) are valid and any clustering can be valid
  • Not limited in clusters that can be expressed
• Scale-invariance
  
  • change of units does not change clustering
    
    • inches instead of feet
• Consistency
  
  • shrinking intra-cluster distances and expanding inter-cluster distances does not change clustering
  • make similar more similar and less similar even less similar, it should not change the groupings

Question 15

Entropy

Answer 15

Tells us if a feature provides any information

Min # of yes/no questions needed to convey information

Question 16

Discounted Rewards

Answer 16

• Sum from t = 0 to inf : gamma^<em>t</em> R(S_t)
• Geometric series
• Rmax / (1 - gamma)
  
  • gamma = 0
    
    • Rmax
  • gamma = 1
    
    • prior case (no discount)
• infinite distance in finite time
  
  • add infinite numbers -> get finite number

Question 17

Markov Decision Process Framework

Answer 17

• States
  
  • S
  • coordinates, descriptors, represent where we are
• Model
  
  • T(s,a,s’) ~ Pr(s’ | s, a)
• Action
  
  • A(s), A
• Reward
  
  • R(s), R(S,a), R(s,a,s’)
• Policy
  
  • pi(s) -> a
  • optimal policy, pi*

Question 18

Sequences of Rewards: Assumptions

Answer 18

• Infinite Horizons
  
  • you can live forever
  • if finite
    
    • may take risks if horizon is short
    • policy can change even if state is unchanged
    • lose stationarity in model
• Utility of Sequences
  
  • 2 sequences with same start, have same preference with start state missing
  • stationary preferences
    
    • if I prefer one set of sequences today, I will tomorrow

Question 19

If X and y are independent, what are their joint and conditional entropy?

Answer 19

Joint Entropy:

H(X, y) = H(X) + H(y)

Conditional Entropy:

H(y | X ) = H(y)

Question 20

What is the utility of a sequence of states?

Answer 20

• Sum of the reward over the states
• Utility of infinite sequences equal infinity
  
  • two sequences, one with larger rewards randomly, both are infinite, neither are better
  • it doesn’t matter what you do if always positive rewards

Question 21

Implausible Threats

Answer 21

• Idea that a grim trigger threat is implausible.
  
  • Why would opposing agent threaten when the result is less reward for themselves too?
• Potential issue with Grim Trigger
  *

Question 22

How can achievable averages payoffs be found in Repeated Games and the Folk Theorem

Answer 22

• Plot strategy pairs onto a 2 player plot
• Form a convex hull between strategy pairs
  
  • “feasible region”
• Points within the convex hull are valid average payoffs for join strategies

Question 23

3 fundamental theorems of nash equilibria

Answer 23

• In the n-player pure strategy game, if elemination of strictly dominated strategies eliminates all but one combination, that combination is the unique N.E.
  
  • ex: prisoners dilemma
• any N.E will survive elimination of strictly dominated strategies
• if n is finite and all states are finite, there exists a (mixed) N.E.

Question 24

tf-idf

Answer 24

• term frequency - inverse document frequency
  
  • nearest-neighbor in textual data

Question 25

What is the Q Function?

Answer 25

Q(s, a) = R(s) + gamma sum_s’ [T(s,a,s’) max_a’ Q(s’,a’)]

Value for arriving in a state s, leaving via a, then proceeding optimally thereafter.

Question 26

MDP: Reward

Answer 26

• Reward
  
  • R(s), R(S,a), R(s,a,s’)
    
    • mathematically equivalent
  • encompasses domain knowledge

Question 27

Principal Components Analysis (PCA)

Answer 27

• Eigenproblem
• Find direction of maximal variance
• Finds orthogonal directions
  
  • PC2 is orthogonal to PC1
• Properties
  
  • Global algorithm
  • Best reconstruction
    
    • no information lost (with all PCs kept)
    • Minimize L2 (squared) error moving from n to m dimensions
  • Each dimension has eigenvalue
    
    • non-negative
    • monotonically non-increase from PC1 to PC2 to PCn
    • Can through away higher eigenvalues (least variance)
    • eigenvalue of 0 is ignorable (0 entropy, meaningless)
  • well studied (fast algorithms)
• Filter method
  
  • Can be difficult with classification if feature associated with label has low variance (the feature may be inadvertently thrown out)

Question 28

Random Components Analysis

Answer 28

• Generate random directions and then projects data out into those directions
• works well
  
  • At what?
    
    • Before classification
      
      • Maintains signal in lower dimension
      • Picks up some correlations
• projects in higher dimensional space than other algorithms like PCA
• Advantage over PCA/ICA
  
  • fast

Question 29

If 2 coins are independent, what is the entropy and mutual information between them?

Answer 29

I(A,B) = H(A) - H(A|B) = 1 - 1 = 0 (no mutual info between them)

H(A , B) = H(A) + H(B) = 1 + 1 = 2

H(A) = H(B) = -0.5 log_2(0.5) - 0.5 log_2(0.5) = 1 (Maximum entropy)

Question 30

mixed strategy vs pure strategy

Answer 30

• mixed strategy
  
  • some distribution over strategies
• pure strategy
  
  • mixed strategy with all probability mass on a single strategy
  • probability 1 of chosen strategy

Question 31

Properties of EM

Answer 31

• Monotonically non-decreasing likelihood
• does not converge (in practice does)
  
  • in strange examples
• will not diverge
• can get stuck
  
  • random restart
• works with any distribution (if E, M solvable)
  
  • expectation is expensive (generally)

Question 32

Forward & Backward Feature Selection

Answer 32

• Forward
  
  • Pass all features to learner
    
    • Start with no features
    • Repeat until error doesnt reduce
      
      • Add feature to get best score
• Backward
  
  • Pass all features to learner
    
    • Start with all features
    • Repeat until error doesn’t reduce
      
      • Remove feature to get best score
• Like hill-climbing

Question 33

MDP: Model

Answer 33

• Model
  
  • T(s,a,s’) ~ Pr(s’ | s, a)
    
    • probability of transition into s’ given that you were in state s and took action a
  • rules of the game
  • physics of the world

Question 34

Feature Selection: Why?

Answer 34

• Knowledge Discovery
  
  • interpretability & insight
    
    • which features matter
    • allow lower dimensions for understanding
• Curse of dimensionality
  
  • need exponentially more data for more features

Question 35

Value Iteration

Answer 35

• Repeat until convergence
  
  • Start w/arbitrary utilities
  • Update utilities based on neighbors
    
    • U_prime(s)_t+1 = R(s) + gamma * maxa sum_s’ [T(s,a,s’) U_prime_t(s’)]
      
      • ​update utility of s by looking at utilities of all other states
      • the R(s) is truth
• Why do we converge?
  
  • Add truth to wrong.. more truth to wrong… more truth to wrong… converge to true as wrong is miniscule
• Works because we propagate value across the states
  
  • Order matters, not absolute values
  • We don’t care about the actual value, just need utility good enough

Question 36

Curse of Dimensionality

Answer 36

Amount of data needed is 2^N number of features

Adding more features means exponentially more data is needed

Question 37

Linear Discrimant Analysis (LDA)

Answer 37

• finds a projection that discriminates based on the label
• like supervised learning
• Not filter method like others, cares about label explicitly
  *

Question 38

Importance different between MDPs and supervised learning

Answer 38

• delayed rewards
  
  • take many actions prior to reward
  • ex: chess
    
    • temporal credit assignment
• minor changes matter
  
  • reward changes affect policy

Question 39

Iterated Prisoner’s Dilemma with Uncertain Ending

Answer 39

• With probability gamma, game continues
  
  • else, game over
• Expected # of rounds
  
  • Finite with gamma < 1
  • 1 / (1 - gamma)
    
    • reminiscent of discount factor

Question 40

Tit-For-Tat

Answer 40

• iterated prisoner’s dilemma strategy
  
  • cooperate on first round
  • copy opponents previous move thereafter
• strategies
  
  • always defect
    
    • cooperate, defect, defect, defect, …
  • always cooperate
    
    • cooperate forever
  • defect, cooperate, defect, cooperate, …
    
    • cooperate, defect, cooperate, defect, …
  • TFT (against another TFT agent)
    
    • cooperate forever

Question 41

What is the best response to each strategy (gamma > 1/6)

Answer 41

• Mutual Best Response
  
  • Pair of strategies where eaach best respone to other. Nash Equilibria
  • In the below chart, D - D and TFT - TFT are Nash Equilibria
    
    • TFT - TFT Cooperative Nash

Question 42

MDP: States

Answer 42

• States
  
  • S
  • coordinates, descriptors, represent where we are

Question 43

Policy Iteration

Answer 43

• Algorithm
  
  • Start with initial policy (arbitrary)
  • Evalute policy
    
    • calculate U_t for policy (utility)
  • Improve Policy
    
    • pi_t+1 = argmax_a sum T(s,a,s’) U_t(s’)
    • U_t(s) = R(s) + gamma sum_s’ T(s, pi_t(s), s’) U_t(s’)
      
      • n linear (unlike VI) equations in n unknowns
• Fewer iterations than Value Iterations
• guaranteed to converge

Question 44

mechanism design

Answer 44

• set up incentives to get particular behavior
• economics/government
  
  • ex: tax breaks for mortgage

Question 45

Bellman Equation

Answer 45

• True utility of a state
  
  • reward for the state plus discounted rewards
  • R(s) + gamma * max_a sum_s T(s,a,s’) U(s’)
    
    • ​non-linear

Question 46

Policies

Answer 46

• pi*
  
  • maximizes expected reward
    
    • argmax_pi E [sum_{t to inf}: gamma^t R(S_t) | pi]
• Utility of a state
  
  • not equal to the reward of state (immediate feedback)
  • long term feedback
  • expected reward for given state and all future states
  • E [sum_{t to inf}: gamma^t R(S_t) | pi , s_o = s]
  • accounts for all delayed rewards

Question 47

Define a Basic Clustering Problem

Answer 47

Take a set of objects and put into groups.

Given: Set of objects, X; inter-object distances ( d(X,y) = D(y, x) )

Output: Partition Pd(X) = Pd(y) if x & y are in same cluster

Question 48

Why use Feature Transformation? (Example)

Answer 48

• Information Retrieval (ad-hoc) “google problem”
  
  • Need: retrieve subset of documents based off of relevance
  • Features
    
    • words
  • Problem with words as features?
    
    • insufficient indicators
    • lot of words
    • polysemy - words mean multiple things
      
      • apple (fruit or company)
      • false positive
    • synonymy - many words mean same thing
      
      • car vs. automobile
      • false negatives

Question 49

Possible filtering criteria for feature selection

Answer 49

• Information Gain
  
  • depends on labels
• Gini index
• variance
• entropy
  
  • doesn’t depend on labels
• NN and prune with low weights
  
  • “useful”
• non-redundant/independent
  
  • get rid of x2 if x2 = x1 + x3

Question 50

Feature Transformation

Answer 50

• The problem of pre-processing a set of features to create a new (smaller? more compact?) feature set, while retaining as much (relevant? useful?) information as possible
• usually less features (almost always)
• Linear combination of original features
• Feature selection is a subset
• Features into a new feature space

Question 51

Q-Learning Convergence

Answer 51

• Converges if:
  
  • s,a is visited infinitely often
  • learning rate sum = inf, sum² < inf
  • next states have to be drawn from transition probabilities
  • rewards have to be drawn from reward function

Question 52

Cascade Learning

Answer 52

• Using a logarthmic reduction in an unbalanced dataset to remove the majority class by half in each iterations, ultimately ending up with a small balanced dataset
  
  • As dataset size is reduced by half in each step, computational power can be double and end up the same (half the data, 2x computation is original to previous step)
• In unbalanced dataset it is often important to get accurately classify the minority class

Question 53

Definition of Policy of a state

Answer 53

pi(s) = argmax_a sum_{<span>s’</span>} [T(s,a,s’) U(s’)]

Question 54

security profile

Answer 54

• mixed strategy, similar to minmax profile

Question 55

Usefulness

Answer 55

Measures effect on a particular predictor

Usefulness ~ Error | Model/Learner

Question 56

Properties of Q for general-sum games

Answer 56

• Nash - Q
• No longer using minimax games (not zero sum)
• Nash Equilibrium operator instead of minimax
• value iteration doesn’t work
• Nash - Q doesn’t converge
• No unique solutions
• Policies cannot be computed independently
  
  • Nash Equilibrium is a joint behavior
    *

Question 57

Three Approaches to RL

Answer 57

• Pi
  
  • policy
  • maps states to actions
  • direct use, indirect learning
  • policy search algorithms
• U
  
  • utility
  • maps states to value
  • • value function based algorithms
• T,R
  
  • Can use to solve Bellman Equations
  • maps states, actions to new states and rewards
  • direct learning, indirect use
  • model-based learners

Question 58

Von Neumann’s Theorem

Answer 58

• In a 2-player, zero-sum (non)deterministic game of perfect information
  
  • minimax = maximin
  • there always exists an optimal pure strategy for each player
• Can determine optimal joint policy with matrix (without original tree)
• Assumption
  
  • rational agent trying to maximize reward
  • other agents are doing the same rational thing

Question 59

What is important about subgame perfect?

Answer 59

• You will fall into mutual cooperation no matter what
• Can return to a cooperative state even after punishment
  
  • becomes a plausible threat

Question 60

Time Complexity of Feature Selection

Answer 60

• Given n features -> m features
  
  • where m <= n
• Exponential
  
  • ​there’s an exponential number of subsets 2ⁿ
• NP-Hard

Question 61

Independent Components Analysis (ICA)

Answer 61

• About finding independence (not correlation to maximize variance like PCA)
• Transform features to be statistically independent from each other (mutual information is 0)
• Maximize the mutual information between all of the original features and the original feature space
• Underlying Assumption
  
  • mutually independent random variables combined linearly
  • observables are linear combinations of hidden variables
  • ex: cocktail party problem
    
    • microphones (observables) hear different linear combinations of voices (hidden variables) at party

Question 62

What are the general approaches to feature selection

Answer 62

• Filtering
  
  • input -> set of features
  • selection algorithm
    
    • contains how well you’re doing
  • output -> fewer features
  • input to learning algorithm
  • Search Algorithm doesnt use learner
• Wrapping
  
  • input -> set of features
  • algorithm - selection & learning
    
    • assess features and get fewer
  • Search Algorithm wrapped with learner

Question 63

Grim Trigger

Answer 63

• Mutual Benefit, as long as you cooperate
• Stop cooperating (cross the line)
  
  • Deal out vengence forever
• Create a nash equilibrium situation, no incentive to “cross the line” which decreases the reward

Question 64

What is the expected message size?

A - 0 (50%)

B - 1 1 0 (12.5%)

C - 1 1 1 (12.5%)

D - 1 0 (25%)

Answer 64

= 1bit * 0.5 + 2bits * 0.25 + 3bits * 0.123 * 2 letters

= 0.5 + 0.5 + 0.75

= 1.75

This is an example of variable length encoding

The computed value is called entropy

Question 65

A soft clustering algorithm

Answer 65

• Assumption: Data generated by
  
  • Repeat n times
    
    • One of K Gaussians, uniformly
    • Sample Xi from Gaussian
• Find hypothesis h = that maximizes the probability of the data (maximum likelihood)
• The maximum likelihood of the gaussian mu is the mean of the data (for one distribution)
  
  • What if there are k mus?
    
    • Hidden variables!

Question 66

MDP: Actions

Answer 66

• Action
  
  • A(s), A
  • things that you can do in a particular state
    
    • gridworld: up, down, left, right
  • generalized as a function of state

Question 67

Clustering Properties Quiz

Answer 67

• A
  
  • Not rich (cant have any combination of clusters)
  • SI - ordered
  • Consistent
• B
  
  • Rich (any clusters)
  • Not SI - depends on unit
  • Consistent
• C
  
  • Rich (any clusters)
  • SI (scaling is undone by theta and max)
  • Not consistent

Question 68

Formula for Entropy

Answer 68

(using log base 2)

Question 69

POMDPs

Answer 69

• partially observable markov decision processes
  
  • more realistic
  • separation between actual world and the decision makers idea of the state

Question 70

central limit theorem

Answer 70

Law of large numbers - the data turns normal, gaussian

Linear combinations of statistically independent variables

Question 71

inverse reinforcement learning

Answer 71

start from observations of behavior, try to guess what reward function resulted in the behaviors

Question 72

Soft Clustering

Answer 72

Data points can belonhg to more than one cluster

probabilistic

Question 73

Is Pavlov v. Pavlov Nash?

Answer 73

• Yes
• Start out cooperating (both agents), continue to cooperate, no reason to not cooperate

Question 74

Supervised Learning

Answer 74

Use labeled training data to generalize labels to new instances

“Feature Approximation”

Question 75

Estimating Q from transitions (without R or T)

Q-Learning update rule

Answer 75

• Q_est(s,a) (alpha) r + gamma * max_a’ Q_est(s’.a’)
  
  • utility of the state
    
    • Q_est
  • utility of the next state
    
    • max_a’ Q_est(s’,a’)
  • alpha_t: learning rate

Question 76

2-player, zero-sum, non-deterministic game of hidden information

Answer 76

• minmax != maxmin
• von neuman fails
• A strategy depends on B and B depends on A
  
  • with hidden information you wont know
• mixed strategy

Question 77

With a fair coin (Heads/Tails) and an unfair coin (Heads both sides) what is the size of each message in bits if the coins are flipped 10 times and the results are transmitted?

Answer 77

Fair = 10 (need all bits)

Unfair = 0 (need no bits, already know result)

Question 78

What is true of a sequence that is more predictable?

Answer 78

more predictable = less information

Question 79

Nash Equilibrium

Answer 79

• n players with strategies (s₁, s₂, …, s_n)
• particular strategies are in a nash equilibrium iff
  
  • for all strategies chosen, if you randomly choose a player to switch their strategy they would have no reason to (in equilibrium)
  • for all strategies chosen = argmax_si utility(s₁ … s₂ … s_n)

Question 80

Direct Learning, Indirect Use RL

Answer 80

model-based approaches

access to underlying T and R

Question 81

Minmax Profile

Answer 81

• Pair of payoffs, one for each player, that represent the payoffs that can be achieved by a player defending itself from a malicious adversary
  
  • zero sum game
  • trying to lower the agents score
• pure

Question 82

Properties of Q for Zero-sum stochastic games

Answer 82

• Uses minimax operator
• Value iteration works
• minimax-Q Converges
• Unique solution to Q*
• Policies can be computed independently
  
  • 2 players can run minimax Q on their own
• Update efficiently
  
  • polynomial time
  • linear programming for minimax
• Q functions are sufficient to specify policy

Question 83

n-Step Prisoners dilemma

Answer 83

prisoners will always defect (nash equilibrium) in the last attempt (expecting other player to diverge from the previous attempts to maximize their own payout)

Question 84

Markovian Property

Answer 84

• Only the present matters
• Transition function in an MDP only depends on current state s
  
  • s’ only needs s
• Current state can be markovian if it remembers where you’ve been
• Things are stationary
  
  • rules do not change
  • transition model doesn’t change

Question 85

What measure can be used to assess dependence between two variables?

Answer 85

Mutual Information ( I )

I (X, y) = H(y) - H(X | y)

Measures the reduction of randomness of a variable given knowledge of another variable

Question 86

How can the four symbols with given frequencies be sent with bits, most efficiently?

A - 50%

B - 12.5%

C - 12.5%

D - 25%

Answer 86

A - 0

B - 1 1 0

C - 1 1 1

D - 1 0

Question 87

Information Theory

Answer 87

Mathematical Framework to allow us to compare probability density functions.

Allows us to determine what input variables provide more information for a response variable

Question 88

Reinforcement Learner “API”

Answer 88

• Planner
  
  • Input: Model (T,R)
  • Output: Policy (pi)
• Learner
  
  • Input: Transitions
  • Output: Policy
• Modeler
  
  • Input: Transitions
  • Outout: model
• Simulator
  
  • Input: model
  • Output: transitions

Question 89

Properties of Wrapping Algorithm for Feature Selection

Answer 89

• Pros
  
  • Take into account model bias and learning
• Cons
  
  • Soooo slow

Question 90

Game Theory

Answer 90

• Mathematics of conflict
  
  • conflicts of interest
• Single Agents -> multiple agents
• Economics ( & politics)
• Increasingly a part of AI/ML

Question 91

• Runtime of SLC
  
  • given n points (objects)
  • k clusters

Answer 91

O(n³)

• Repeat k times (n/2)
  
  • Look at all distances to find closest O(n²) pair that have different labels

Question 92

Differences between supervised, unsupervised, and reinforcement learning

Answer 92

• Supervised learning
  
  • function approximation
  • given y,x pairs find function f
• unsupervised learning
  
  • given x’s and goal is to find f
  • get description based on features
  • clustering, description
• reinforcement learning
  
  • given x’s and z’s and learn some f to generate y’s
    
    • z - rewards
  • mechanism for decision making

Question 93

MDP: Policy

Answer 93

• Policy
  
  • pi(s) -> a
  • pi*
    
    • optimal policy
    • maximizes long term expected reward
• Function that takes in a state and returns the action you should take

Question 94

In what ways is information between two variables determined?

Answer 94

Joint Entropy (Randomness contained in 2 variables together)

H(X,y) = - sum [ P(X,y) log P(X, y)

Conditional Entropy (Entropy of y given X, Randomness of y given X)

H(y | X) = - sum [ P(X,y) log P (y | X
)

Question 95

Unsupervised Learning

Answer 95

Make sense out of unlabeled data

“data description”

Question 96

Single Linkage Clustering (SLC)

Answer 96

* Hierarchical Aglomerative Clustering Algorithm (HAC)

• Algorithm:
  
  • repeat n-k times to make k clusters
    
    • consider each object a cluster (n objects)
    • define intercluster distance as distance between the cloests two points in the two clusters
    • merge two closest clusters

Question 97

Pavlov

Answer 97

• Cooperate if agree, defect if disagree

Question 98

K-Means Clustering

Answer 98

• Algorithm:
  
  • Repeat until convergence
    
    • Pick K Centers (random)
    • Centers claim closest points
    • Recompute the centers by averaging clustered points
• Note: Center is not always a point

Question 99

cross-entropy

Answer 99

• randomized optimization algorithm
• similar to MIMIC

Question 100

Direct Use, Indirect Learning RL

Answer 100

Policy search based algorithms

Question 101

Algorithms that use filtering for feature selection

Answer 101

• Decision trees are a filtering algorithm
  
  • Use information gain
    
    • features that provide most information given class labels

Question 102

Is Pavlov v. Pavlov Subgame perfect?

Answer 102

• Yes
• Synchronize to mutually cooperative state no matter the historical sequence
• Average reward is mutual cooperation
  
  • C, C
  • C, D
  • D, C
  • D, D

Question 103

Computational Folk Theorem

Answer 103

• Game: 2 player, bimatrix game, average reward repeated
• Can build a pavlov-like machine for any game and construct subgame perfect Nash equilibrium for any game in polynomial time
  
  • Pavlov if possible
  • Zero-sum like (solve an LP)
  • at most one player improves

Question 104

Mutual Information

Answer 104

to determine if input vectors are similar

Question 105

Different versions of Q

Answer 105

• Q-Learning is a family of algorithms that differ:
  
  • How to initialize Q_est?
    
    • all awesome “optimism in the face of uncertainty”
      
      • Q will explore less visited “still awesome” states
  • How to decay learning rate?
  • how to choose actions?
    
    • always choose a_o - wont learn
    • always choose randomly - wont use it
    • use Q_est to choose actions - wont learn (if local min)
      
      • greedy
    • use Q_est with random restarts
      
      • slow
    • use Q_est with “simulated annealing” like approach
      
      • random actions sometimes
      • random action with p = epsilon, q_est action with 1 - epsilon

Question 106

What are the Utility and Policy of a state given Q?

Answer 106

U(s) = max_a Q(s,a)

pi(s) = argmax_a Q(s,a)

Question 107

Ideas for solving general-sum stochastic games

Answer 107

• repeated stochastic games (folk theorem)
• cheaptalk -> correlated equilibria
  
  • nothing said is binding
  • players can coordinate
  • can compute a correlated equilibrium (more efficient to compute than nash)
• Cognitive hierarchy -> best responses
  
  • instead of solving for equilibrium, assume other players have limited computational resources then take best response of what you believe other players will do
  • more easily computed, assuming other player is fixed
• side payments (coco values)
  
  • give side reward to encourage actions

Question 108

Properties of Filtering algorithms for feature selection

Answer 108

• Pros
  
  • Faster than wrapping
• Cons
  
  • Ignores the learning problem
  • Look at features in isolation

Question 109

2 player, non zero-sum, non-deterministic game of hidden information

Answer 109

• prisoners dilemma
  
  • choose option that is not best for the group
    
    • over fear of other agent making bad choice
• see image
  
  • (-6, -6) option is chosen, both agents will never cooperate

Question 110

Expectation Maximization

Answer 110

• 2 phases
  
  • Expectation
    
    • Likelihood that data i comes from cluster j
    • E[Zij] = P(X = xi | mu = mu_j) / normalization
  • Maximization
    
    • Compute the means from the cluster
    • mu_j = sum_i E[Zij] * Xi / normalization
• K-means if cluster assignments use argmax
• Note: With EM probabilities, even points clearly in one cluster have a non-zero probability of the other cluster

Question 111

Subgame perfect equilibrium

Answer 111

• Always best response independent of history
  
  • if we had history of the response of each agents and one of the responses was not the best, not subgame perfect equilibrium
• Example: Grim Trigger vs. Tit-For-Tat is not Subgame perfect
  
  • If TFT decides to defect first, Grim defects
    
    • If Grim cooperated anyway, grim would do better
    • Grim makes a threat and follows through with the threat, resulting in worse outcome than if it hadn’t followed through
      
      • Grim: C | D , D, D, D, …
      • TFT: D | C, D, D, D, …

Question 112

Epsilon-Greedy Exploration

Answer 112

• If GLIE “Greedy limit + infinite exploration” (decayed epsilon)
  
  • Q_est converges to Q
  • pi_est converges to pi*
• Exploration - Exploitation dilemma
  
  • Exploration - learn
  • exploitation - use what you know
  • trade-off

Question 113

What is true of K-Means in euclidean space?

Answer 113

• Error can only go down
  
  • Move point into new partition iff the error goes down
  • Average minimizes the squared error, moving the center would never increase error
  • Monotonically non-increasing in error
• Each iteration is polynomial ( k*n per iteration )
• Converges in finite time (kⁿ iterations)
  
  • Need some way of breaking ties
    
    • If a point is equally far from both partitions
    • Consistently break ties
  • Only look at configuration once
• Can get stuck (ties)