final exam review Flashcards
How is entropy used in clustering?
entropy (IG) ranks attributes by how much they contribute information. 0 = no info, 1 = max info
Describe SLC algo
- each obj starts as own cluster
- merge 2 closest clusters
- repeat n-k times
what is an important consideration for SLC?
how you define distance what is “close” for clusters/data points. This can be considered your domain knowledge
Describe K-means algo
- pick k centers at random.
- for each center
a. claim the closest points
b. recompute the centroid (dimensional mean) - repeat until convergence
define a consistent tie-breaking metric.
what rand opt also is K-means similar to?
hill climbing - take steps to move to a better configuration
What is a pitfall of K-means? How can you avoid it?
can get stuck in local optima. avoid by doing random restarts, or defining your space to be points of the convex hull.
K-means time complexity
each iteration O(Kn)
total number of iterations = O(K^n)
K-means properties
monotonically non-increasing in error.
squared error metric for the distance from centers/means
EM algo overview
soft clustering technique that assigns based on probability distributions.
- select k gaussians distributions
- find prob that each point (x_i) would be in each gaussian distribtuion
- take avg of all x_is in each distribution (cluster)
- recompute cluster based on wgt’d avg of the x_i’s
- repeat until the x’s don’t move that much
EM Properties
- does not diverge
- doesn’t fully converge, but practically does
- can get stuck in local optima, need restarts
- monotonically non-decreasing likelihood.
- If E, M solvable, works with any distribution.
Can EM or K-means ever act in the same way?
if probabilities were argmax to 0 or 1, EM would function same as k-means
What are some properties of clustering?
richness
scale invariance
consistency
what is cluster richness
all possible partitions are possible. for any cluster that you want, there is some distribution where P_distribution can produce that cluster
scale invariance
mult. list by a positive scalar does not change clustering (ie changing units)
cluster consistentcy
making similar things more similar and different things more different will not change the groupings.
what is the impossibility thm
you can never have all 3 three of consistency, richness, and scale invariance for a cluster algorithm
what is game theory?
the mathematics of conflict. games can have single or multiple agents.
what is a strategy
mapping of all possible states to an action s.
each player has their own strategy
can only map to states attainable by a player
what is the difference between a pure and a mixed strategy?
pure represent straight moves by a player, while mixed strategies are based on a probability distribution over the players’ strategies.
In a pure strategy a player chooses an action for sure, whereas in a mixed strategy, they choose a probability distribution over the set of actions available to them.
what is minimax
for a game btw A and B, A considers the best case counter, while B considers the worst case counter.
this is all about pov.
A picks the strategy that maxes it’s value while knowing your opponent is trying to minimize your value.
also known as covering your ass.
what is the fundamental results for a 2 player, zero sum, deterministic game of perfect info?
- minimax = maximin
- there always exists a pure strategy for each player.
- this is saying the value found in the matrix that describes the game is when A, B both try to maximize their strategies acting rationally.
what is the effect of hidden information?
- mini poker
- minimax does not equal maximin b/c one player’s strategy depends on what the opponent is going to do.
what is a Nash Equilbrium
for n players with strategies S1,..,Sn.
These n players with strategies are in a Nash eq. iff for all states the player chooses the strategy that maximizes their utility.
This is saying that a no player in the game has a reason to change its strategy.
a unique NE exists if the elimination of strictly dominated strategies eliminates all but one combo.
any NE will survive the elimination of strictly dominated states
T/F : for a finite # of players and finite # of strategies, there exists a NE
True
T/F: in a repeated game, the last state is only one that matters
True, because eventually the NE will dominate. Even though we’ve built up trust eventually we will defect because it is in our best interest.
n repeated game -> n repeated NE
what is the expected number of rounds for an IPD?
1/1-gamma
describe tit for tat
- cooperate on the 1st round
- each round thereafter, copy the opponents previous move.
T/F: when facing TFT, you should always cooperate for low gamma
False. You should always defect for low gamma because there will be a small number of games being played.
For high gamma, you should always cooperate when facing TFT.
What is a finite state strategy?
a strategy based on deterministic states where the choices of one players impacts their own payoff and the future decisions of the opponents.
what is the folk theorem?
in repeated games, the possibility of retaliation opens the door for cooperation.
Any feasible payoff profile that strictly dominates the minimax/security level profile can be realized as a NE payoff profile, with sufficiently large gamma.
This is proved because if the strategy strictly dominates the minimax profile, it can be used as a threat. the player is best off doing what it is told.
what is the minimax profile for an IPD?
it is the pair of payoffs, one for each player, that represent the payoffs that can be attainted by a player defending itself from a malicious opponent.
- this can be solved as a zero-sum game.
- this can be considered the feasible region of a 2 player game.
what is the security level profile?
these are payoffs in an acceptable region that are better than what each player can guarantee themselves in an adversarial situation.
what is subgame perfect?
- each player takes the best response independent of the history in the game.
what makes a game not subgame perfect?
- game is not SGP if there exists some history of actions given to players and there is a point where one of the players is not taking a best response
- player makes a threat, but when it comes time to act on the threat, it is doing something that is worse for itself than what it would do otherwise.
Describe Grim Trigger
- cooperate, but if ever defect, always defect thereafter.
- strategy that can be used to prove folk theorem
- implausible threat -> always taking vengeance and forgoing rewards is irrational and unreasonable
T/F: Grim Trigger vs. TFT is subgame perfect
False. this game is not subgame perfect because grim trigger will defect in one situation where it should cooperate.
what is an example of a sub perfect game?
Pavlov v. Pavlov
average reward for this game is mutual cooperation
what is the difference between a plausible and implausible threat?
implausible threat - taking vengeance and forgoing rewards without a way to improve it for yourself.
plausible threat - defect knowing that you will be ok/get a positive state afterwards.