Final Exam

Question 1

EM always converges? (T/F)

Answer 1

False. In practice it usually does, but since the configuration space is infinite the only guarantee we have is that it will not DIVERGE.

Question 2

What is a WEAKLY RELEVANT feature

Answer 2

1. Not strongly relevant
2. Exists a subset of features S such that adding x_i to S improves the Bayes Optimal Classifier (BOC)

Question 3

Why is feature selection difficult?

Answer 3

Because from a theoretical perspective, we would have to score all the possible subsets. Given N features where we desire to downsize to M features, this requires 2^n runs. This means the feature selection problem is EXPONENTIAL, and is known to be NP-HARD.

Question 4

What is “Usefulness” (in the context of feature selection) roughly equivalent to?

Answer 4

Error GIVEN the model/learner (for example, consider a neural net; some feature x_i might be useful in the sense that performing an operating like y=w.T*x enables the model to achieve better predictions, i.e. lower error predictions, on average, but might still not be “relevant” to a Bayesian Optimal Classifier)

Question 5

PCA will never find independent components? (T/F)

Answer 5

False. Because of the mutual orthogonality and maximal variance constraints, there ARE cases where it will find independent components by virtue of trying to find components that are uncorrelated. However, uncorrelated != statistical independence necessarily.

Question 6

Where does domain knowledge get encoded in Filtering style feature selection algorithms?

Answer 6

In the criterion used for the search algorithm, e.g. information gain, variance, entropy, “usefulness”, non-redundancy, etc.

Question 7

What is the clustering impossibility theorem?

Answer 7

It’s the reality that we can have a clustering algorithm that all have (because they’re mutually exclusive, you can at best get 2/3 of them):

1. Richness
2. Scale Invariance
3. Consistency

This was proved by John Kleinberg

Question 8

What are the components of an MDP?

Answer 8

SART; i.e. states, actions, rewards, transitions. (Dr. Isbell notes that some people include the discount factor gamma, which he disagrees with since he thinks it’s part of the definition of the problem.)

Question 9

Policy iteration eliminates the “max” term in the Bellman equation? (True/False)

Answer 9

True. Since in policy iteration we’re already following the policy, we no longer have to compute over all the actions, so that get’s rid of the nonlinear function.

The reason this is useful is because once we get rid of the nonlinear operation, we can use things like matrix inversion, etc. to solve the n equations and n unknowns in the Bellman equation in linear time. This is MORE COMPUTATIONALLY EXPENSIVE (roughly n^3 for inversions, also is a function of dimensionality) than something like say value iteration, but in theory it should converge to the optimal policy in FEWER ITERATIONS.

Another thing that follows from this is that when performing policy iteration, the jumps in utility will be bigger than in value iteration because we’re iterating policy space instead of value space.

Question 10

What is one case where PCA would return the same components as ICA?

Answer 10

If the data are Gaussian. This is because the distribution that maximizes variance IS the normal distribution (remember that PCA is trying to find the basis vectors that maximize variance!)

Question 11

The configuration space for both K-Means and EM is finite? (T/F)

Answer 11

False. K-Means is finite because the cluster assignments are HARD. There are only so many ways we can assign n points to K clusters (K^n in fact), hence finite.

EM on the other hand works in probability space, so there’s an infinite number of possible configurations.

The key takeaway from this is that while K-MEANS IS GUARANTEED TO CONVERGE, THE ONLY THING GUARANTEED BY EM IS THAT IT WONT DIVERGE!

Question 12

What is the intercluster distance of two objects that are in the same cluster?

Answer 12

Really a trick question. Answer is zero

Question 13

What is the time complexity of SLC?

Answer 13

O(n^3)

Question 14

What is the time complexity each iteration of K-Means?

Answer 14

O(kn), or O(knd) if we’re considering multiple dimensions d

Question 15

Describe filtering style feature selection?

Answer 15

Use some criterion for filtering, e.g. information gain, variance, entropy, “usefulness”, non-redundancy, etc.

Important thing to consider is that THE LEARNER IS NOT INCLUDED.

Question 16

How does K-Means clustering algo work

Answer 16

1. Pick K “centers” (at random)
2. Each center “claims” its closest points
3. Recompute the centers by averaging the clustered points
4. Repeat until convergence

Question 17

Which part of the EM algorithm is usually the most computationally expensive?

Answer 17

The E (expectation) step. This is because we’re doing some sort of inference stuff there, e.g. Bayes nets, etc, whereas the M (maximization) step typically just involves counting things.

The lectures mention this isn’t ALWAYS true, but in general it’s a good heuristic.

Question 18

What are some of the advantages and disadvantages of the Filtering style of feature selection algorithms?

Answer 18

1. Speed:
   Pro:
   Doesn’t involve learner, so FS is fast
   Con:
   Isolated features - maybe a feature on its own doesn’t seem important, but when combined with another one it is. Since filtering doesn’t include the learner, no way of knowing this.
   More generally, the major con is that it ignores the actually learning problem.

Question 19

What is the intuition behind K-Means?

Answer 19

It’s an interative process of randomly partitioning a dataset, and then finding the centroids of each of those partitions, then going back to step one and repartitioning based on the new centroid locations.

This is important because it’s what allows us to think about K-Means in terms of OPTIMIZATION (specifically hill climbing).

Question 20

How is PCA in some sense a method for determining correlation?

Answer 20

Because it is maximizing variance in the data.

Question 21

Would ICA be better at finding global or local features?

Answer 21

Local. The lecture videos bring up an interesting point how in natural scenes ICA actually recovers EDGES.

Question 22

What are the two broad categories of Feature Selection algorithms?

Answer 22

Filtering and Wrapping

Question 23

What are some other types of hierarchical agglomerative cluster models besides SLC?

Answer 23

max, average, median

Question 24

What is the main advantage of Random Component Analysis?

Answer 24

It’s very fast.

Question 25

Using entropy as a criterion for feature selection is difficult because you need to know the labels of the data? (T/F)

Answer 25

False. This is one of the big advantages of criterion like entropy over things like information gain, which does require labels.

Question 26

What are some filtering criteria you could use for feature selection?

Answer 26

1. Information gain 2. Variance, entropy 3. "Useful" features (e.g. maybe train a neural net and prune away features where the weights are zero) 4. Independent/non-redundant

Question 27

What learning algorithm could you use as a Filtering style feature selector? Describe how it could be used.

Answer 27

One example would be a decision tree. You could use the feature importances to select a subset of the most important features, and then pass that onto another learner. The advantage of doing this is different learning algorithms suffer from different types of inductive biases, so there may be some advantage to doing feature selection using one algorithm but a different algo for that actual learning (e.g maybe you need a learner that's more robust to noise data, one that has faster inference times, one that fits within some memory/cpu requirements, etc.).

Question 28

Given a set of points, what is the maximum likelihood estimate for the mean of a Gaussian centered around that dataset?

Answer 28

It's just the mean of the data, for same reasons we described in K-Means, proved using calculus that mean is best way of minimizing error in least squares sense.

Question 29

Unlike K-Means, EM can never get stuck in local optima? (T/F)

Answer 29

False, and for the same reason as K-Means. We're still relying on random initialization of clusters, so if we get a bad initial assignment, it is still possible for EM to get stuck.

Question 30

The reward we get for being in some state is the same thing as the utility for that state? (True/False)

Answer 30

False. Reward is all about IMMEDIATE gratification. But the utility considers "how good is it to be in that state", which is a function of the (discounted) sum of the future rewards that I will get (in expectation) for starting in that state and following some policy pi. So utility is about LONG TERM REWARD.

Question 31

What is the Bayes Optimal Classifier

Answer 31

It's the idea of "what is the best I could do" on a given learning problem. It's not any particular algorithm, it's given ALL algorithms, what is the best I could achieve.

Question 32

Policy iteration is guaranteed to converge to the optimal policy? (True/False)

Answer 32

True. (Dr. Isbell mentions that the argument for why this is the case is similar to the argument for why K-Means works.)

Question 33

Which random optimization algorithm is like K-Means? Why is that?

Answer 33

Hill climbing. This is because of the iterative process that maximizes the score (i.e. minimizes the error) as the centroids of the partitions are moved around.

Question 34

Describe wrapping style feature selection?

Answer 34

Iterative process of searching for features (typically using some sort of randomized optimization algorithm) and then passing that feature subset to the learner to score it, and then repeating the process.

Question 35

What are some ways of performing a "wrapping" style feature selection algorithm?

Answer 35

1 . Hill Climbing 2. Randomized Optimization 3. Forward selection

Question 36

What is one way of dealing with the problem of getting stuck in local optima with K-Means or EM?

Answer 36

Random restarts (just like hill climbing)

Question 37

How difficult is the feature selection problem?

Answer 37

Given N features, it is 2^N

Question 38

What are some of the important properties of the EM algorithm?

Answer 38

1. It is monotonically non-decreasing in terms of likelihood 2. Does not converge (although usually does in practice) 3. Will not diverge 4. Can also get stuck (just like K-Means) 5. Works with any probability distribution (if E, M are solvable)

Question 39

How does Single Linkage Clustering work?

Answer 39

1. Consider each object (i.e. data point) as its own cluster (i.e. n objects) 2. Define intercluster as distance between the CLOSEST two points in the two clusters. (So starting out the intercluster distance is just the interobject distance) 3. Merge two closest clusters 4. Repeat n-k times to make k clusters.

Question 40

How many iterations are possible in K-Means?

Answer 40

Finite (exponential) iterations: O(K^n)

Question 41

Describe the Soft Clustering algorithm?

Answer 41

\*\*Assume data was generated by normal distribution for this example\*\* 1. Select one of K gaussians (with a fixed known variance) uniformly 2. Sample x\_i from that Gaussian 3. Repeat n times Task: Find a hypothesis h= that maximizes the probability of the data (in terms of maximum likelihood)

Question 42

What is one of the main differences between PCA and ICA?

Answer 42

PCA ~= Correlation ICA ~= Independence

Question 43

Why is the prior not included in the Expectation Maximization algorithm?

Answer 43

Because EM uses the maximum likelihood estimate, i.e. we assume a uniform prior, so it can just be dropped from the calculation in the EM update.

Question 44

What are 3 reasons that feature selection is important?

Answer 44

1. Knowledge discovery 2. Interpretability and insight 3. Curse of dimensionality (amount of data we need grows exponentially as we increase the features)

Question 45

What is the idea of "consistency" that Dr. Littman talks about in regards to clustering?

Answer 45

It's the idea that if we make a bunch of points within a cluster more similar, or more the points in two clusters more dissimilar, we shouldn't get different groupings.

Question 46

What is the Bellman Equation?

Answer 46

Question 47

If a PCA component has an eigenvalue of 0, what should we do with that component? Why?

Answer 47

Throw it away because it contains no useful information.

Question 48

Single link clustering terminates fast?

Answer 48

True (mentioned in summary at end of lectures).

Question 49

In terms of feature SELECTION, what is one feature TRANSFORMATION algorithm that is similar to filtering? Why?

Answer 49

PCA. It's similar because once we align the new set of basis vectors that are aligned in the direction of maximal variance, we can throw away (i.e. filter) the components that don't contribute to the variance.

Question 50

If you have a strongly relevant feature, and you make a copy of it, then both features will be strongly relevant? (T/F)

Answer 50

False. By making a copy of it, you've made the feature redundant, so now the features are only weakly relevant.

Question 51

What are some properties of PCA?

Answer 51

1. Maximizes variance 2. Orthogonal 3. Global algorithm (i.e. each of the PCs are orthogonal to one another) 3. Best reconstruction (minimizes L2 error moving from N to M dimensions) 4. Well studied, so lots of fast algorithms exist for it.

Question 52

How does Forward Feature Selection work?

Answer 52

(start with a feature, get a score. Whichever is best keep. Then add another feature along with it, repeat, score, Keep going until you achieve some criterion, e.g. minimum sore, etc.

Question 53

K-Means does not struggle with getting stuck in local optima? (T/F)

Answer 53

False. It's definitely possible to get stuck if the initial random cluster assignment is bad.

Question 54

Give an example of a PCA component that would have an eigenvalue of zero. What should we do with that component?

Answer 54

A PCA component with an eigenvalue of zero is irrelevant; it contains no useful information. You could think of points lying exactly on the line y=1. There would be zero entropy of the points, hence they would not be relevant (although they could possibly useful to something like a NN classifier in terms of prediction error). Therefore, If the eigenvalue is zero, we should just get rid of the component.

Question 55

A feature x\_i that is neither strongly relevant nor weakly relevant it is \_\_\_\_\_\_\_\_.

Answer 55

Irrelevant

Question 56

At a high level, what is PCA doing?

Answer 56

It's lining up a new set of orthogonal basis vectors that are aligned with the direction of the maximal variance of the data. Another way of looking at it is that it is trying to find all the orthogonal gaussians in a dataset (because a Gaussian distribution is the distribution that maximizes variance!)

Question 57

The error in K-Means can go up?

Answer 57

False. It is monotonically non-increasing in error. Things can only be reassigned to a new cluster if the error goes DOWN. This is because the average is the best way of describing the cluster in a least squares sense. Note that this does require that ties are broken consistently, but as long as that is true, ERROR ALWAYS DECREASES FOR K-MEANS

Question 58

What are some of the advantages and disadvantages of the Wrapping style of feature selection algorithms?

Answer 58

Major Pro: Takes into account the MODEL BIAS Major Pro: Actually considers the LEARNING PROBLEM Major Con: VERY Slow

Question 59

What's one way of connecting RL to some of the earlier lectures in the course?

Answer 59

The idea of rewards taking the place of teachers. Basically the reward acts as the "teaching signal" in place of an explicit teacher telling you what is good or bad. You can also think of the rewards as taking the place of domain knowledge.

Question 60

How many configuration spaces are possible in K-Means?

Answer 60

K^n

Question 61

Single linkage clustering is a non-deterministic algorithm? (T/F). Justify your reason.

Answer 61

False. The distance between objects doesn't change, so it's deterministic.

Question 62

What are three properties that are desirable for clustering algorithms?

Answer 62

1. Richness: Ability to assign any inputs to any clustering 2. Scale Invariance: scaling distances by a positive value does not change the clustering 3. Consistency: shrinking INTRA-cluster distances and expanding INTER-cluster distances does not change the clustering.

Question 63

What is the computational complexity of choosing the best M features from a set of N features?

Answer 63

O(2^N). It is known to be an NP-HARD problem.

Question 64

What is "Relevance" (in the context of feature selection) roughly equivalent to?

Answer 64

Information. This is because it's all about the Bayes Optimal Classifier. Relevant things are THINGS THAT GIVE US INFORMATION.

Question 65

The number of configurations in K-Means is infinite? (T/F)

Answer 65

False.

Question 66

Reward and utility are equivalent? (T/F)

Answer 66

False. Reward is all about immediate gratification, whereas utility is all about long-term (i.e. delayed rewards).

Question 67

What is the Filtering style of algorithm for feature selection?

Answer 67

With filtering the scoring of the subset of features occurs INSIDE the feature selection algorithm, and then then once the best subset is found it is passed on to the learner.

Question 68

What is a STRONGLY RELEVANT feature?

Answer 68

x\_i is strongly relevant if removing it degrades Bayes Optimal Classifier (BOC), i.e. if without that feature you couldn't achieve a Bayes Optimal Classifier

Question 69

What is the difference between Relevance vs. Usefullness

Answer 69

1. RELEVANCE measures effect on BAYES OPTIMAL CLASSIFIER 2. USEFULNESS mesures effect on a PARTICULAR predictor

Question 70

What is one way of thinking about what unsupervised learning is?

Answer 70

Compact description

Question 71

The "center" used in K-Means is always one of the datapoints?

Answer 71

False. The centroid need not actually be in the set of data points. It's just describing the central tendency of the cluster. (i.e. the "Means" part of K-Means")

Question 72

What are the two different fundamental epistemological assumptions that PCA and ICA make?

Answer 72

1. PCA: The the world is made up of a bunch of Gaussians, so finding the most important ones is just a matter of finding the ones that are uncorrelated with one another. 2. ICA: The world consists of sources that are highly NON-Gaussian, but when added together as part of a linear combination they became Gaussian in the limit via the Central Limit Theorem.

Question 73

What is one of the key assumptions of the sources of ICA?

Answer 73

That they are INDEPENDENT of one another (remember the microphone example)

Question 74

What analogy does Dr. Littman use that is a good summary of Forward/Backward Feature Selection algorithms?

Answer 74

Imagine a dodgeball team: 1. Using FFS, you'd start with the best player, and then continue adding best players until you reach some criterion. 2. Using BFS, you'd start by eliminating the worse player, and then continue eliminating until you've reached some criterion of minimum number of features.

Question 75

Would PCA be better at finding global or local features?

Answer 75

Global, because of it's Gaussian/maximal variance nature.

Question 76

What are examples of metric and non-metric statistics?

Answer 76

Median is non-metric statistic, Mean IS metric. The reason this is important is that metric statistics like the mean, the values of the data itself matter a lot.

Question 77

What algorithm is Expectation Maximization similar to?

Answer 77

K-Means, because it's an iterative process of assigning X to having been generated by some set of latent variables Z, and then moving the means based on those latent assignments, and then beginning the process all over. CLUSTERING --\> MAXIMIZATION then repeat until convergence

Question 78

What is mutual information?

Answer 78

That amount of information some variable X contains about another variable Y.

Question 79

The Expectation Maximization algorithm is close to, but can never quite be the same as K-Means? (T/F)

Answer 79

False. It ends up being the same thing if the cluster assignments use the argmax. (Have to watch the EM lecture videos to see the math for this)

Question 80

When doing feature selection, even if a feature doesn't seem to be useful for learning, we might as well leave it in there. It isn't harming anything, right? (T/F)

Answer 80

False. Ceterus paribus, leaving a feature in does at least two things that hurt performance: 1. Time 2. Sample efficiency. This is because of the curse of dimensionality, which says that we need exponentially more data as we increase the number of features.

Question 81

What is the Wrapping style of algorithm for feature selection?

Answer 81

With wrapping the feature selection and learner are embedded into the same algorithm, and iteratively passed back and forth: the feature selection algo outputting a subset of features, the learner then takes that as input, scores it, and passes the score back to the feature selection algo and the process starts all over again.

Question 82

In Q-Learning, what would happen if you set the learning rate to 0? To 0.5? To 1.0?

Answer 82

At 0, no learning would happen. At 1.0, you would basically just be discarding the old value and moving straight to the new estimate. 0.5 would then essentially just be the average between your new and old estimates.

Question 83

What requirement is made on the learning rate in Q-Learning?

Answer 83

Sum of LR must be infinite, some of squares of LR must be finite.

Question 84

Q-Learning does not converge to the optimal Q function? (T/F)

Answer 84

False. It does, but ONLY assuming all s, a pairs are visited infinitely often.

Question 85

What is a "Folk Theorem"?

Answer 85

Describes the set of payoffs that can result from Nash Strategies in REPEATED games

Question 86

In repeated games, the possibility of retaliation opens the door for \_\_\_\_\_?

Answer 86

Cooperation

Question 87

What is subgame perfect?

Answer 87

Always best response independent of history.