ML: test-driven-development, not studied yet, less relevant

Question 1

ML: What is a generative model?

Answer 1

It models P(Y|X) using P(X|Y)P(Y)
(derived from Bayes rule)

Question 2

ML: What is a discriminative model?

Answer 2

Models P(Y|X) directly, as P(Y|X)

Question 3

ML: What is a Bayes classifier?

Answer 3

Question 4

ML: At a high level, how would a Bayes Classifier be constructed in a case where errors are asymmetric, meaning some errors are worse than others?

Answer 4

We would weight each possible error with its own amount of loss L_i,j, pertaining to what you said the answer is and what the answer should’ve been.

Question 5

ML: What is a simplistic view of logistic regression when Y is binary?

Answer 5

We are just doing a linear regression on our X’s, then squishing the outcome into [0,1]

Question 6

ML: In binary logistic regression, what is the formula for P(Y=1|X=x)?

Answer 6

For x of any dimension, it is as follows:

Question 7

ML: What decision boundary does binary logistic regression yield?

Answer 7

It yields the linear separator:

Question 8

ML: For binary logistic regression, how do we learn the coefficients of the model B₀, B₁, B₂… in order to make predictions?

Answer 8

We estimate them using simple maximum likelihood, found iteratively with something like gradient descent.. So we find the coefficients B₀, B₁, B₂… that have the highest likelihood of producing the observed training data with the observed labels.

Question 9

ML: How to we extend binary logistic regression to multinomial logistic regression? So our X’s are still n-dimensional vectors, but now our Y’s are scalars in [1,K]?

Answer 9

Question 10

ML: How do you specify a hyperplane classifier for D-dimensional x, and Y either 0 or 1?

Answer 10

Question 11

ML: How does prediction work for a KNN classifier or regressor?

Answer 11

For each new point, you find the K points in the training set closest to it (by some measure such as euclidean distance); then for classification you’d return the most common label among the nearest neighbors, and for regression you’d return the average label of the nearest neighbors.

Question 12

ML: How do ensemble classifiers generally work?

Answer 12

Several models are learned, and they vote on what the prediction is.

Question 13

ML: What is boosting? How does it generally work?

Answer 13

In boosting, you fit several (typically very basic) classifiers iteratively, with each new classifier trying to do well on the training points that the previous classifiers did poorly on.

Question 14

ML: How does boosting improve the performance of the classifiers its using? In otherwords, how does bias and/or variance impacted before and after the use of boosting?

Answer 14

Because it uses very simple predictors (for example, stumps of decision trees), each one individually has very high bias. But, by fitting a lot of them and correcting for previous mistakes, bias is decreased.

Question 15

ML: What is the (somewhat high-level) algorithm for Adaboost?

Answer 15

We start with each training example X_i having equal weights w_i. Then, repeat:

1. Fit a new classifier that minimizes weighted training error, based on the weights w_i. (Points on which earlier classifiers have performed poorly have higher weights, and errors on those points cost more)
2. Based on the weighted error of that classifier, find a weight alpha_j for the classifier for when it votes later on. The lower its weighted error, the higher its alpha_j, and thus the higher its voting power.
3. Update each of the point weights w_i based on this round’s results.

Question 16

ML: How (at a high level) does gradient boosting work?

Answer 16

At each step, we find the current gradient of the loss function. We then find our next classifier to “approximate this gradient vector”.

So we in some way optimally take into account the gradient of the loss function at each step as we choose our classifiers.

Question 17

What is the xgboost library at a very high level?

Answer 17

The xgboost library is an ML library for training models that are ensembles of decision trees using gradient boosting (a version of boosting, which you’re familiar with). The implementation in the library contains many optimizations, making it very fast and effective, hence it’s popularity throughout the ML world.

Creating models with xgboost is simple: its interface is very similar to sklearn for example.

It was made by CMU professor Tianqi Chen!

Question 18

ML: How does bagging work, at a fairly high level? How do we train a bagging ensemble given a training set of n X_i’s?

Answer 18

Resample several samples from your training data; say m bootstrapped samples of size n, with replacement.

Train a (typically complex) model on each of the m bootstrapped samples. Have these models vote on the prediction.

Question 19

ML: How do bias and variance work with bagging? So what is the level bias and variance from one of the individual classifiers in the ensemble, and then what happens to bias and variance when we have several classifiers vote?

Answer 19

The classifiers in bagging are complex; if they’re trees, they’re deep trees. As a result, the individual classifiers have low bias, but high variance.

However, when we use several classifiers and have them vote, we can drive down this variance because we’re averaging votes from classifiers trained on different bootstrapped samples. (As n goes infinity, these samples become independent.)

Question 20

ML: What are the high-level differences between boosting and bagging, and how they achieve the goal of making several classifiers work effectively together?

Answer 20

Boosting fits several models that are not complex, and thus have high bias. But by fitting several and correcting errors from previous iterations, bias is reduced.

Bagging fits several complex models, so bias is lower but variance is high. But by averaging many predictions on slightly different datasets, we can lower variance.

Question 21

ML: What is an improvement we can make to bagging (specifically classification bagging) when we are calculating our predicted class?

Answer 21

Rather than just picking the class with the most votes from each of the classifiers, average the probabilities of each class from each of the classifiers, then predict the class with the highest probability.

(If we get to the end of a branch in one of the classifiers, the “probability” of class j predicted by that classifier is the proportion of training examples that had class j).

This improvement makes performance more consistent, decreasing variance a bit.

Question 22

ML: How do Random Forests work?

Answer 22

Random Forests work basically just by using bagging with deep decision trees: bootstrapping several resampled training sets, training a deep tree on each of them, and having them vote for a classification or regressed value.

The key change from traditional bagging is this: if there are p features of a training example X, at each split in a decision tree, only m < p features are considered for that split. (Typically m = sqrt(p))

Question 23

ML: Why is the Random Forest alteration to bagging often advantageous?

Answer 23

By only considering m < p features at each split of a decision tree, the trees become more independent, which helps the random forest algorithm decrease the variance in the overall prediction (which is the general goal of bagging).

Question 24

ML: What method is typically used to evaluate random forests instead of cross-validated error? Why is this other approach typically better for random forests?

Answer 24

You use out-of-bag error. Because each classifier is trained on a bootstrapped training set, each point in the original training set was not used in training some of the classifiers (about 36.8%). So, get a prediction on this point from these classifiers, and find the error on all the points from that method.

This is preferable to cross-validation because you don’t need to retrain the model for each of the folds; training takes a long time for random forests, so we want to avoid it. But with enough trees, out-of-bag error tends to be very similar to CV error.

Question 25

ML: For random forests, what are the 2 most common ways to calculate variable importance metrics?

Answer 25

1. Find all of the splits which use that variable in all of the decision trees, and then find how much on average those splits improve the predictions, using some measure of prediction performance like Gini index. 2. Randomly permute each variable one at a time, and see how much model performance decreases for each. (I'm guessing this means to calculate out-of-bag error, and for each point, before getting the prediction, choose the value of the variable in question randomly.)

Question 26

ML: What is clustering, and how does it differ from classification?

Answer 26

Clustering is an unsupervised learning technique, so our training data are not labeled, and we try to divide the data into groups that are in some way "similar". So basically, we try to label each point such that similar points have the same label. Classification is similar because each point has a label, but classification is supervised: we are given a labeling scheme and want to learn how to predict it as best as possible. With clustering, we aren't given a labeling scheme, and want to find a sensible one.

Question 27

ML: What does k-means clustering approximately minimize? And how does its approximation of this minimization work on a theory level?

Answer 27

Question 28

ML: How do you run the k-means clustering algorithm?

Answer 28

After choosing your number of classes k, randomly initialize the locations of your k cluster centers. Then, repeat: 1. Assign all training points to the cluster center that is closest by euclidean distance 2. Set cluster center as the average of all points in the cluster

Question 29

ML: What are some drawbacks to k-means clustering?

Answer 29

1. It's nondeterministic due to the random initializations, and is not guarenteed to reach the global optimum. 2. Cluster center isn't interpretable, as it's an average of a bunch of points

Question 30

ML: What is an advantage to k-means clustering?

Answer 30

It will always converge, as each step will decrease the in-cluster variance (until it's at a local minimum)

Question 31

ML: How does the k-medoids algorithm work? Specifically, what alterations are made to the k-means algorithm?

Answer 31

Here the cluster centers are actual points in the dataset, rather than an average of a bunch of points. So we initialize k points randomly to be the initial cluster centers, then repeat: 1. Assign all training points to the cluster center (a real point) that is closest to it 2. For each cluster, choose the point in the cluster which minimizes mean squared distance from other points as the new cluster center. (In other words, minimize in-cluster variation.)

Question 32

ML: What does it mean to "fold the intercept in" for a hyperplane classifier?

Answer 32

Rather than writing the hyperplane as w^Tx + b = 0, you write it as w^Tx = 0, and implicitly assume that the first (zeroth) entry in w is your intercept b, and the first (zeroth) entry in your x vector is a 1.

Question 33

ML: What is a simple way to draw a hyperplane classifier w^Tx = 0, as well as the direction of the arrow pointing towards y=1?

Answer 33

Just draw the hyperplane by normally drawing a line, by converting into y = mx + b form. To figure out which side has which label and draw that arrow, do some easy-to-calculate sample point back in the original form of w^Tx = 0, and see whether w^Tx is above or below 0.

Question 34

ML: What is the goal of dimensionality reduction?

Answer 34

We want to take our D-dimensional dataset, and represent it using fewer dimensions (or fewer features). And we want to preserve as much of the structure and information in the data as we can: we want similar points in our original dataset to also be similar in the dimension-reduced dataset, and want dissimilar points to also remain dissimilar (by whatever measure of similarity makes sense in context).

Question 35

ML: What does PCA give you?

Answer 35

With D-dimensional data, PCA finds up to D new linear dimensions, or vectors, or "number lines" as I think of them, which are linear combinations of the original dimensions (e_1, e₂,...). Each of these dimensions is called a Principal Component, and the first is the vector v₁ maximizing the variance of Xv₁, the projections of the points in design matrix X onto the number line of v₁. The remaining principal components maximize the variance of the projection Xv_i while also making v_i orthogonal to all previous principal components. (All D principal components thus form a basis for R^D, as they're all orthogonal.) Using these principal components, you can choose k \< D of them to represent your data in the k dimensional subspace preserving as much of the variance in the data as possible (I bet it's actually an approximation of that, cuz it feels like it's a greedy algorithm, but that's the idea).

Question 36

ML: In PCA, what is proportion of variance explained?

Answer 36

For some subset of the D principal components, say k of them, the proportion of variance explained is how much of the variance from the original dataset is preserved by this k-dimensional representation. (Or what is explained by each individual principal component; both definitions work.) Specifically, it is (I assume) the variance in the k-dimensional representation divided by the variance in the original data. We are often interested in proportion of variance explained *as a function of k*, so we can see when we have a k high enough to explain a reasonable proportion of the variance, such as maybe 90%.

Question 37

ML: In PCA, what is a scree plot?

Answer 37

It plots proportion of variance explained vs number of principal components used, as a means of visualizing how much information will be preserved by each additional principal component. This is the general idea, but there are many versions. Some plot number of PCs used vs eigenvalue associatied with its eigenvector, because these are related (as described in another flashcard). Another type, shown below, has the proportion of variance at each individual PC.

Question 38

ML: What is the formula or equation satisfied by matrix M and its eigenvector v and associated eigenvalue ÿ (lambda)?

Answer 38

Mv = ÿv | (Mv = lambda\*v)

Question 39

ML: In PCA, once you have your top k principal components v_i, how do you get your k-dimensional representation of data matrix X?

Answer 39

X_new = XV_k, where the columns of V_k are the k principal components v_i. In other words, you find all k PC scores, Xv_i, which is just the projection of each point x onto the number line of direction v_i, and then you combine all of those projections into your new representation X_new.

Question 40

ML: There are three common high-level ways to compute PCA. What are they? In other words, what 3 matrices can you do what three things to to get relevant information for PCA?

Answer 40

Given data matrix X, you can: 1. Find the eigendecomposition VDV^T of its covariance matrix (Sigma-hat) 2. Find the singular value decomposition of X = UD\*V^T. 3. Take the inner product matrix XX^T and find XX^T = U(D\*)²U^T, where U and D\* the same as in option 2.

Question 41

ML: How do you Kernel PCA for some dataset, and what does Kernel PCA allow you to do?

Answer 41

Kernel PCA allows you to find *nonlinear embeddings* using PCA, which typically only finds optimal linear embeddings. You'll recall that you can do normal PCA by taking the inner product matrix as XX^T​ = U(D\*)²U^T, where XX^T is the inner product matrix with (XX^T)_i,j = x_i^Tx_j. Well instead, use the kernel trick and make a different similarity matrix, a kernel matrix K, where the entries K_i,j = k(x_i,x_j) for some nonlinear kernel. Then do the same decomposition into K = U(D\*)²U^T for some other matrices U and D, and find the PC scores in the new nonlinear space as UD just as you would when using XX^T. This way, you can find the PCA dimension reduction of X, but after transforming the points of X into any new subspace you want, likely a non-linear one, using kernels.

Question 42

ML: How do you train a model using cross-validation? How does it differ from normal validation?

Answer 42

With normal validation, once you've set aside your test data, you split your remaining data into train and validation data. You train all your models on the train data, then validate them with the validation data. You pick a model and test it on the test data. With cross-validation (say with k folds, such as 5 or 10), after you set aside test data, you instead divide it into k groups, or k "folds". For every model you try, you train it on k-1 of the folds and find its validation error on the remaining fold, and you do this *for each of the k folds*. Finally, you get your validation error by averaging all k of your error measures on each of the folds. (So you train your model k times rather than once when you are validating.) This "wastes" less data, but takes more time and compute

Question 43

ML: When cross-validating, is more or less folds better? What is the "ideal" number of folds? What is the intuition behind this?

Answer 43

Generally more folds is better, and you want as many folds as possible. The "ideal" cross validation is leave-one-out cross validation or LOOCV, where each datapoint is its own fold, with the intuition being that the more data you use to train for each fold, the better you simulate how the model will perform on actual held-out data. But of course, more folds means more time, and thus LOOCV is often not realistic. 5-fold and 10-fold CV are common and tend to do the trick.

Question 44

What is an SVM at a high level? Hard and soft-margin SVM?

Answer 44

Support vector machines (SVMs) are an algorithm for finding the optimal linear/hyperplane classifier for a dataset. In hard-margin, no points can be misclassified, and the classifier tries to maximize the "margin", which is the distance between the hyperplane and the closest point(s). In soft-margin, points are allowed to cross the hyperplane. Each point is assigned a "slack variable", describing how far it's within the margin (a concept still kept from hard-margin) or within the decision boundary (i.e. misclassified).

Question 45

ML: How does multi-class SVM work, i.e. where there's more than two classes?

Answer 45

Similar to multiclass logistic regression, we just fit k binary-classification SVMs: one for each of the k labels, predicting whether it's that specific label vs *any of the others* (we treat all other labels as a single label for each binary classifier). We then predict via:

Question 46

ML: What is the idea of the kernel trick? What two valuable advantages does the kernel trick give us?

Answer 46

Question 47

ML: How does using the kernel trick for SVM work? Where do we sub in the kernel?

Answer 47

Question 48

ML: What does a norm accomplish at a very high level?

Answer 48

It maps a vector to a non-negative scalar in a way that measures its "length"

Question 49

ML: What is the *l_p* norm (as in *l₀, l₁,* etc) for integer values from 0 all the way to infinity?

Answer 49

Question 50

ML: What is the *l₂* norm? What does it find, and how do we calculate it for a vector?

Answer 50

The *l₂* norm, or the euclidean norm, is simply the distance formula: it's the length of the vector in euclidean space. If x = [1,5,2], ||x||₂ = sqrt(1² + 5² + 2²).

Question 51

ML: What is the *l₁* norm? How do we calculate it?

Answer 51

For ||x||₁, you just sum the absolute values of the entries in x. ||x||₁ = |x₁| + |x₂| + |x₃|

Question 52

ML: In the context of machine learning, what is the key difference between the *l₁* and *l₂* norms, and in the outcomes they produce? How does this concept impact the regularization techniques we're familiar with?

Answer 52

Suppose we are trying to find a vector x that minimizes a norm, either the *l₁* or *l₂* norm. So in both cases, we're trying to find a vector x whose entries are near zero. The *l₂* norm doesn't care much whether an entry in x is exactly zero, or very nearly zero; as such, when we try to minimize the *l₂* norm, we get a bunch of values that are very nearly zero. Conversely, the *l₁* norm *does* care a lot whether an entry in x is exactly zero, or very nearly zero; as such, when we try to minimize the *l₁* norm, we get a bunch of values that are exactly zero, whereas with the *l₂* norm they weren't quite zeroed out. This pops up in regularization: when we do ridge regression, we're minimizing the parameter vector over the *l₂* norm, and so we get a bunch of values that are almost zero, but none that are really zeroed out. When we do lasso regression, we use the *l₁* norm and thus get a bunch of parameters that are exactly 0. There are tradeoffs here: lasso regression yields more interpretable results, but ridge regression is better at capturing very small relationships that lasso tends to just zero out.

Question 53

402/401: What is the correct way of interpreting a coefficient B_i in a linear regression? What is an incorrect way of interpreting it? Why is the latter correct while the former is incorrect?

Answer 53

**Correct:** B_i is the expected difference in the outcome variable Y between two points whose difference in X_i is 1, assuming the values of all other predictors are held equal. **Incorrect:** B_i is the expected difference in Y caused by increasing X_i by 1. The incorrect one is wrong because *it assumes some sort of causal relationship*. Our linear model by itself says nothing about what will happen if we *change* the value of X_i, it just says that on average, points with higher X_i have higher (or lower, depending on sign of Bi) values of Y based proportionally on B_i, which is what the correct interpretation is saying.

Question 54

ML: At an extremely high level, how does graph clustering work?

Answer 54

Form a graph from your training points, connecting points that are similar. Then, make graph cuts which separate dissimilar points to form your clusters.

Question 55

ML: What is a key advantage of graph clustering?

Answer 55

It is very good at capturing *non-blob-like clusters*, or clusters with atypical shapes. This can be very useful