CLAS 150C1 FINAL EXAM ACTUAL
SCRIPT WITH 100 PERCENT CORRECT
ANSWERS
◉ Markov Decision Process (MDP)
Answer:
◉ Variable Length Encoding
Answer: Code which maps source symbols to a variable number of
bits (smaller bits for more frequent symbols)
◉ kMeans properties
Answer: - Each iteration polynomial
- Finite (exponential) iterations
- Error usually decreases monotonically
- Can get stuck
◉ EM Properties
Answer: - Monotonically non-decreasing likelihood
- Does not converge (but does practically) b/c of infinite
configurations of probabilities
- Will not diverge
- Can get stuck
, - Will work with any distribution
◉ Richness
Answer: For any assignment of objects to clusters, there is some
distance matrix D such that your clustering scheme P_D returns
the clustering
◉ Scale invariance
Answer: Scaling distances by a positive value doesn't change the
clustering.
◉ Consistency
Answer: Shrinking intracluster distances and expanding
intercluster distances does not change the clustering
◉ Best Reconstruction
Answer: Minimize L₂ error (squared error) moving from N-->m
dimensions
◉ Policy
Answer: Function from state to action.
◉ Bellman Equation
Answer: U(s) = R(s) + γ maxₐ ∑ₛ' T(s,a,s')U(s)
SCRIPT WITH 100 PERCENT CORRECT
ANSWERS
◉ Markov Decision Process (MDP)
Answer:
◉ Variable Length Encoding
Answer: Code which maps source symbols to a variable number of
bits (smaller bits for more frequent symbols)
◉ kMeans properties
Answer: - Each iteration polynomial
- Finite (exponential) iterations
- Error usually decreases monotonically
- Can get stuck
◉ EM Properties
Answer: - Monotonically non-decreasing likelihood
- Does not converge (but does practically) b/c of infinite
configurations of probabilities
- Will not diverge
- Can get stuck
, - Will work with any distribution
◉ Richness
Answer: For any assignment of objects to clusters, there is some
distance matrix D such that your clustering scheme P_D returns
the clustering
◉ Scale invariance
Answer: Scaling distances by a positive value doesn't change the
clustering.
◉ Consistency
Answer: Shrinking intracluster distances and expanding
intercluster distances does not change the clustering
◉ Best Reconstruction
Answer: Minimize L₂ error (squared error) moving from N-->m
dimensions
◉ Policy
Answer: Function from state to action.
◉ Bellman Equation
Answer: U(s) = R(s) + γ maxₐ ∑ₛ' T(s,a,s')U(s)
