Final Flashcards
Quiz: PCA vs ICA
- 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
- ICA
- Ordered Features
- PCA
- eigenvalues ordered by variance
- Not for ICA
- kurtosis can be used to order but generally order is not considered
- PCA
- Bag of Features
- ICA
Definition of Utility (U)
U(s) = R(s) + gamma * maxa sums’ [T(S,a,s’) U(s’)]
Long term value of being in a state
What to do when we are facing Tit For Tat?
- Always defect
- best for low gamma
- always cooperate
- best for high gamma
Way to implement feature selection for wrapping
- Hill Climbing
- Randomized Optimization
- Forward/Backward Selection
How do ICA and PCA differ?
- 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
What is KL Divergence
Measures the difference between any two distributions (distance measures)
Impossibility Theorem
- 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
Relevance
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
Minimax
- 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
prisoners dilemma
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
Issues with SLC
- 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)
Repeated Games and the Folk Theorem
- 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.
KMeans as Optimization - Definition
- 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
- (P’, center) U (P, center’ )
- P, center = set of pairs
- A lot like Hill Climbing
Desirable Clustering Properties
- 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
- change of units does not change clustering
- 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
Entropy
Tells us if a feature provides any information
Min # of yes/no questions needed to convey information
Discounted Rewards
- Sum from t = 0 to inf : gamma<em>t</em> R(St)
- Geometric series
- Rmax / (1 - gamma)
- gamma = 0
- Rmax
- gamma = 1
- prior case (no discount)
- gamma = 0
- infinite distance in finite time
- add infinite numbers -> get finite number
Markov Decision Process Framework
- 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*
Sequences of Rewards: Assumptions
- 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
If X and y are independent, what are their joint and conditional entropy?
Joint Entropy:
H(X, y) = H(X) + H(y)
Conditional Entropy:
H(y | X ) = H(y)
What is the utility of a sequence of states?
- 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
Implausible Threats
- 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
*
How can achievable averages payoffs be found in Repeated Games and the Folk Theorem
- 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
3 fundamental theorems of nash equilibria
- 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.
tf-idf
- term frequency - inverse document frequency
- nearest-neighbor in textual data
What is the Q Function?
Q(s, a) = R(s) + gamma sums’ [T(s,a,s’) maxa’ Q(s’,a’)]
Value for arriving in a state s, leaving via a, then proceeding optimally thereafter.
MDP: Reward
- Reward
- R(s), R(S,a), R(s,a,s’)
- mathematically equivalent
- encompasses domain knowledge
- R(s), R(S,a), R(s,a,s’)
Principal Components Analysis (PCA)
- 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)
Random Components Analysis
- 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
- Before classification
- At what?
- projects in higher dimensional space than other algorithms like PCA
- Advantage over PCA/ICA
- fast
If 2 coins are independent, what is the entropy and mutual information between them?
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)
mixed strategy vs pure strategy
- mixed strategy
- some distribution over strategies
- pure strategy
- mixed strategy with all probability mass on a single strategy
- probability 1 of chosen strategy
Properties of EM
- 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)
Forward & Backward Feature Selection
- Forward
- Pass all features to learner
- Start with no features
- Repeat until error doesnt reduce
- Add feature to get best score
- Pass all features to learner
- Backward
- Pass all features to learner
- Start with all features
- Repeat until error doesn’t reduce
- Remove feature to get best score
- Pass all features to learner
- Like hill-climbing
MDP: Model
- 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
- T(s,a,s’) ~ Pr(s’ | s, a)
Feature Selection: Why?
- Knowledge Discovery
- interpretability & insight
- which features matter
- allow lower dimensions for understanding
- interpretability & insight
- Curse of dimensionality
- need exponentially more data for more features
Value Iteration
- Repeat until convergence
- Start w/arbitrary utilities
- Update utilities based on neighbors
-
U_prime(s)t+1 = R(s) + gamma * maxa sums’ [T(s,a,s’) U_primet(s’)]
- update utility of s by looking at utilities of all other states
- the R(s) is truth
-
U_prime(s)t+1 = R(s) + gamma * maxa sums’ [T(s,a,s’) U_primet(s’)]
- 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
Curse of Dimensionality
Amount of data needed is 2N number of features
Adding more features means exponentially more data is needed
Linear Discrimant Analysis (LDA)
- finds a projection that discriminates based on the label
- like supervised learning
- Not filter method like others, cares about label explicitly
*
Importance different between MDPs and supervised learning
- delayed rewards
- take many actions prior to reward
- ex: chess
- temporal credit assignment
- minor changes matter
- reward changes affect policy
Iterated Prisoner’s Dilemma with Uncertain Ending
- With probability gamma, game continues
- else, game over
- Expected # of rounds
- Finite with gamma < 1
- 1 / (1 - gamma)
- reminiscent of discount factor
Tit-For-Tat
- 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
- always defect
What is the best response to each strategy (gamma > 1/6)
- 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
MDP: States
- States
- S
- coordinates, descriptors, represent where we are
Policy Iteration
- Algorithm
- Start with initial policy (arbitrary)
- Evalute policy
- calculate Ut for policy (utility)
- Improve Policy
- pit+1 = argmaxa sum T(s,a,s’) Ut(s’)
- Ut(s) = R(s) + gamma sums’ T(s, pit(s), s’) Ut(s’)
- n linear (unlike VI) equations in n unknowns
- Fewer iterations than Value Iterations
- guaranteed to converge
mechanism design
- set up incentives to get particular behavior
- economics/government
- ex: tax breaks for mortgage
Bellman Equation
- True utility of a state
- reward for the state plus discounted rewards
-
R(s) + gamma * maxa sums T(s,a,s’) U(s’)
- non-linear
Policies
- pi*
- maximizes expected reward
- argmax_pi E [sumt to inf: gammat R(St) | pi]
- maximizes expected reward
- 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 [sumt to inf: gammat R(St) | pi , so = s]
- accounts for all delayed rewards
Define a Basic Clustering Problem
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
Why use Feature Transformation? (Example)
- 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
Possible filtering criteria for feature selection
- 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
Feature Transformation
- 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
Q-Learning Convergence
- Converges if:
- s,a is visited infinitely often
- learning rate sum = inf, sum2 < inf
- next states have to be drawn from transition probabilities
- rewards have to be drawn from reward function
Cascade Learning
- 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
Definition of Policy of a state
pi(s) = argmaxa sum<span>s’</span> [T(s,a,s’) U(s’)]
security profile
- mixed strategy, similar to minmax profile
Usefulness
Measures effect on a particular predictor
Usefulness ~ Error | Model/Learner
Properties of Q for general-sum games
- 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
*
- Nash Equilibrium is a joint behavior
Three Approaches to RL
- 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
Von Neumann’s Theorem
- 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
What is important about subgame perfect?
- You will fall into mutual cooperation no matter what
- Can return to a cooperative state even after punishment
- becomes a plausible threat
Time Complexity of Feature Selection
- Given n features -> m features
- where m <= n
-
Exponential
- there’s an exponential number of subsets 2n
- NP-Hard
Independent Components Analysis (ICA)
- 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
What are the general approaches to feature selection
- 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
Grim Trigger
- 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
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%)
= 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
A soft clustering algorithm
- Assumption: Data generated by
- Repeat n times
- One of K Gaussians, uniformly
- Sample Xi from Gaussian
- Repeat n times
- 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!
- What if there are k mus?
MDP: Actions
- Action
- A(s), A
- things that you can do in a particular state
- gridworld: up, down, left, right
- generalized as a function of state
Clustering Properties Quiz
- 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
Formula for Entropy
(using log base 2)
POMDPs
- partially observable markov decision processes
- more realistic
- separation between actual world and the decision makers idea of the state
central limit theorem
Law of large numbers - the data turns normal, gaussian
Linear combinations of statistically independent variables
inverse reinforcement learning
start from observations of behavior, try to guess what reward function resulted in the behaviors
Soft Clustering
Data points can belonhg to more than one cluster
probabilistic
Is Pavlov v. Pavlov Nash?
- Yes
- Start out cooperating (both agents), continue to cooperate, no reason to not cooperate
Supervised Learning
Use labeled training data to generalize labels to new instances
“Feature Approximation”
Estimating Q from transitions (without R or T)
Q-Learning update rule
- Qest(s,a) (alpha) r + gamma * maxa’ Q_est(s’.a’)
- utility of the state
- Qest
- utility of the next state
- maxa’ Qest(s’,a’)
- alphat: learning rate
- utility of the state
2-player, zero-sum, non-deterministic game of hidden information
- minmax != maxmin
- von neuman fails
- A strategy depends on B and B depends on A
- with hidden information you wont know
- mixed strategy
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?
Fair = 10 (need all bits)
Unfair = 0 (need no bits, already know result)
What is true of a sequence that is more predictable?
more predictable = less information
Nash Equilibrium
- n players with strategies (s1, s2, …, sn)
- 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 = argmaxsi utility(s1 … s2 … sn)
Direct Learning, Indirect Use RL
model-based approaches
access to underlying T and R
Minmax Profile
- 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
Properties of Q for Zero-sum stochastic games
- 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
n-Step Prisoners dilemma
prisoners will always defect (nash equilibrium) in the last attempt (expecting other player to diverge from the previous attempts to maximize their own payout)
Markovian Property
- 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
What measure can be used to assess dependence between two variables?
Mutual Information ( I )
I (X, y) = H(y) - H(X | y)
Measures the reduction of randomness of a variable given knowledge of another variable
How can the four symbols with given frequencies be sent with bits, most efficiently?
A - 50%
B - 12.5%
C - 12.5%
D - 25%
A - 0
B - 1 1 0
C - 1 1 1
D - 1 0
Information Theory
Mathematical Framework to allow us to compare probability density functions.
Allows us to determine what input variables provide more information for a response variable
Reinforcement Learner “API”
- Planner
- Input: Model (T,R)
- Output: Policy (pi)
- Learner
- Input: Transitions
- Output: Policy
- Modeler
- Input: Transitions
- Outout: model
- Simulator
- Input: model
- Output: transitions
Properties of Wrapping Algorithm for Feature Selection
- Pros
- Take into account model bias and learning
- Cons
- Soooo slow
Game Theory
- Mathematics of conflict
- conflicts of interest
- Single Agents -> multiple agents
- Economics ( & politics)
- Increasingly a part of AI/ML
- Runtime of SLC
- given n points (objects)
- k clusters
O(n3)
- Repeat k times (n/2)
- Look at all distances to find closest O(n2) pair that have different labels
Differences between supervised, unsupervised, and reinforcement learning
- 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
- given x’s and z’s and learn some f to generate y’s
MDP: Policy
- 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
In what ways is information between two variables determined?
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
)
Unsupervised Learning
Make sense out of unlabeled data
“data description”
Single Linkage Clustering (SLC)
* 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
- repeat n-k times to make k clusters
Pavlov
- Cooperate if agree, defect if disagree
K-Means Clustering
- Algorithm:
- Repeat until convergence
- Pick K Centers (random)
- Centers claim closest points
- Recompute the centers by averaging clustered points
- Repeat until convergence
- Note: Center is not always a point
cross-entropy
- randomized optimization algorithm
- similar to MIMIC
Direct Use, Indirect Learning RL
Policy search based algorithms
Algorithms that use filtering for feature selection
- Decision trees are a filtering algorithm
- Use information gain
- features that provide most information given class labels
- Use information gain
Is Pavlov v. Pavlov Subgame perfect?
- Yes
- Synchronize to mutually cooperative state no matter the historical sequence
- Average reward is mutual cooperation
- C, C
- C, D
- D, C
- D, D
Computational Folk Theorem
- 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
Mutual Information
to determine if input vectors are similar
Different versions of Q
- 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
- all awesome “optimism in the face of uncertainty”
- How to decay learning rate?
- how to choose actions?
- always choose ao - 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
- How to initialize Q_est?
What are the Utility and Policy of a state given Q?
U(s) = maxa Q(s,a)
pi(s) = argmaxa Q(s,a)
Ideas for solving general-sum stochastic games
- 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
Properties of Filtering algorithms for feature selection
- Pros
- Faster than wrapping
- Cons
- Ignores the learning problem
- Look at features in isolation
2 player, non zero-sum, non-deterministic game of hidden information
- prisoners dilemma
- choose option that is not best for the group
- over fear of other agent making bad choice
- choose option that is not best for the group
- see image
- (-6, -6) option is chosen, both agents will never cooperate
Expectation Maximization
- 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
- Expectation
- 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
Subgame perfect equilibrium
- 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, …
- If TFT decides to defect first, Grim defects
Epsilon-Greedy Exploration
- 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
What is true of K-Means in euclidean space?
- 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 (kn iterations)
- Need some way of breaking ties
- If a point is equally far from both partitions
- Consistently break ties
- Only look at configuration once
- Need some way of breaking ties
- Can get stuck (ties)
