CS7641 FINAL EXAM | VERIFIED STUDY GUIDE
Four optimization approaches - Answers - 1) Generate and test
2) Calculus
3) Newton's Method
4) Randomized Optimization
Hill Climbing Algorithm - Answers - Guess x∈X
Repeat the following:
Let n*=argmax_n∈N(x) f(n)
If f(n)>f(x): x=n
Else: stop
Disadvantage:
- Get stuck in local optima
Randomized Restart Hill Climbing - Answers - Same as Hill Climbing but once local
optimum reached, restart again with a different starting x
Advantage:
- Won't get stuck in local optimum
- Not much more expensive than HC (constant factor)
Disadvantage:
- May not do better than enumeration (depends on size of attraction basin around
global optimum)
Entropy - Answers - -∑p(s)log₂p(s)
Number of bits per symbol (probability of symbol X # of bits to describe that symbol)
Joint Entropy - Answers - H(x,y)=-∑p(x,y)log₂p(x,y)
Randomness contained in two variables together
Conditional Entropy - Answers - H(y|x)=-∑p(x,y)log₂p(y|x)
Randomness of one variable given the other variable
Entropy if x and y are independent - Answers - H(Y|X)=H(Y) Y doesn't get any info from
x
H(X,Y)=H(X)+H(Y) Joint entropy is sum
Mutual Information - Answers - I(x,y)=H(y)-H(y|x)=I(y,x)
, Measure of reduction of randomness of variable given some knowledge of another
variable.
Specific case of KL Divergence
Kullback-Leibler Divergence - Answers - Always non-negative
Zero when P is equal to Q
Measures distance between any two distributions
Supervised Learning - Answers - Use labeled training data to generalize labels to new
instances (function approximation)
Unsupervised Learning - Answers - Make sense out of unlabeled data (data description)
Single Linkage Clustering (SLC) Algorithm - Answers - - Consider each object a cluster
(n objects)
- Define intercluster distance as distance between closest two points in the two clusters
- Merge 2 closest clusters
- Repeat n-k times to make k clusters
Notes:
- Running time O(n²)x(~n)
k-Means Clustering Algorithm - Answers - - Pick k centers at random
- Each center claims closest points
- Recompute the centers by averaging the clustered points
- Repeat until convergence
Notes:
- Can get stuck
Expectation Maximization - Answers - Expectation - soft clustering:
E[Zᵢⱼ]=(P(x=xᵢ|µ=µⱼ)/(∑ᵏP(x=xᵢ|µ=µⱼ)
"Likelihood data element i comes from cluster j"
Maximization - calculating meas of clusters:
µⱼ=(∑E[Zᵢⱼ]xᵢ)/(∑E[Zᵢⱼ])
P(x=xᵢ|µ=µⱼ)=exp[-½σ²(xᵢ-µⱼ)²]
Properties:
- Monotonically non-decreasing likelihood
- Does not converge
- Will not diverge
- Can get stuck -> overcame with randomization
- Works with any distribution
Four optimization approaches - Answers - 1) Generate and test
2) Calculus
3) Newton's Method
4) Randomized Optimization
Hill Climbing Algorithm - Answers - Guess x∈X
Repeat the following:
Let n*=argmax_n∈N(x) f(n)
If f(n)>f(x): x=n
Else: stop
Disadvantage:
- Get stuck in local optima
Randomized Restart Hill Climbing - Answers - Same as Hill Climbing but once local
optimum reached, restart again with a different starting x
Advantage:
- Won't get stuck in local optimum
- Not much more expensive than HC (constant factor)
Disadvantage:
- May not do better than enumeration (depends on size of attraction basin around
global optimum)
Entropy - Answers - -∑p(s)log₂p(s)
Number of bits per symbol (probability of symbol X # of bits to describe that symbol)
Joint Entropy - Answers - H(x,y)=-∑p(x,y)log₂p(x,y)
Randomness contained in two variables together
Conditional Entropy - Answers - H(y|x)=-∑p(x,y)log₂p(y|x)
Randomness of one variable given the other variable
Entropy if x and y are independent - Answers - H(Y|X)=H(Y) Y doesn't get any info from
x
H(X,Y)=H(X)+H(Y) Joint entropy is sum
Mutual Information - Answers - I(x,y)=H(y)-H(y|x)=I(y,x)
, Measure of reduction of randomness of variable given some knowledge of another
variable.
Specific case of KL Divergence
Kullback-Leibler Divergence - Answers - Always non-negative
Zero when P is equal to Q
Measures distance between any two distributions
Supervised Learning - Answers - Use labeled training data to generalize labels to new
instances (function approximation)
Unsupervised Learning - Answers - Make sense out of unlabeled data (data description)
Single Linkage Clustering (SLC) Algorithm - Answers - - Consider each object a cluster
(n objects)
- Define intercluster distance as distance between closest two points in the two clusters
- Merge 2 closest clusters
- Repeat n-k times to make k clusters
Notes:
- Running time O(n²)x(~n)
k-Means Clustering Algorithm - Answers - - Pick k centers at random
- Each center claims closest points
- Recompute the centers by averaging the clustered points
- Repeat until convergence
Notes:
- Can get stuck
Expectation Maximization - Answers - Expectation - soft clustering:
E[Zᵢⱼ]=(P(x=xᵢ|µ=µⱼ)/(∑ᵏP(x=xᵢ|µ=µⱼ)
"Likelihood data element i comes from cluster j"
Maximization - calculating meas of clusters:
µⱼ=(∑E[Zᵢⱼ]xᵢ)/(∑E[Zᵢⱼ])
P(x=xᵢ|µ=µⱼ)=exp[-½σ²(xᵢ-µⱼ)²]
Properties:
- Monotonically non-decreasing likelihood
- Does not converge
- Will not diverge
- Can get stuck -> overcame with randomization
- Works with any distribution