What is a computer primarily used for? To entertain with music To process data, perform calculations, and execute instructions To store mechanical parts To decorate an office space

To process data, perform calculations, and execute instructions

What best describes an algorithm? A type of electronic device A step-by-step procedure for solving a problem A random sequence of events A form of data storage

A step-by-step procedure for solving a problem

What was a 'floppy' used for in computing? A display technology A type of removable data storage medium A computer's operating system A programming language

A type of removable data storage medium

What does data refer to in a computing context? A type of computer programming Digital information stored on a floppy Quantitative or qualitative values collected for analysis A visual display unit

Quantitative or qualitative values collected for analysis

What is AI defined as? Simulation of human intelligence in machines Building physical robots Data encryption techniques Software development protocols

Simulation of human intelligence in machines

Define an 'agent' in the context of AI. A software bug fixer Anything that perceives and acts upon its environment Hardware component in computers Data storage system

Anything that perceives and acts upon its environment

What does PEAS stand for in AI? Performance, Efficiency, Actions, Solutions Planning, Execution, Analysis, Storage Performance measure, Environment, Actuators, Sensors Programming, Encryption, Algorithms, Systems

Performance measure, Environment, Actuators, Sensors

What is the formula for the norm of a vector \( v \)? \[ ||v|| = \sqrt{\sum v_i} \] \[ ||v|| = v^T \cdot v \] \[ ||v|| = \sqrt{v^T \cdot v} \] \[ ||v|| = \sum v_i^2 \]

\[ ||v|| = \sqrt{v^T \cdot v} \]

How is the distance between two vectors \( u \) and \( v \) calculated? \[ \text{dist}(u,v) = u \cdot v \] \[ \text{dist}(u,v) = ||u+v|| \] \[ \text{dist}(u,v) = ||u-v|| \] \[ \text{dist}(u,v) = \sqrt{u^T v} \]

\[ \text{dist}(u,v) = ||u-v|| \]

Which learning algorithm uses unlabeled data to extract patterns, often used for clustering? Semi-supervised learning algorithms Supervised learning algorithms Unsupervised learning algorithms Reinforcement learning algorithms

Unsupervised learning algorithms

What is the primary goal of a clustering algorithm? Maximize both intra-cluster and inter-cluster distances Minimize intra-cluster distances and maximize inter-cluster distances Maximize intra-cluster distances and minimize inter-cluster distances Minimize both intra-cluster and inter-cluster distances

Minimize intra-cluster distances and maximize inter-cluster distances

What measures the 'goodness' of a clustering when the ground truth is known or unknown? Jaccard index and Silhouette coefficient Rand index and Jaccard index Silhouette coefficient and Dunn index Rand index and Silhouette coefficient

Rand index and Silhouette coefficient

b,c Select the correct statements about the Fiedler vector. A: The Fiedler vector is the eigenvector of the Laplacian matrix that is associated with the smallest eigenvalue B: The Fiedler vector always satisfies the balance constraint (as written as an equation) C: The Fiedler vector is a solution to the unrelaxed, NP-hard optimization problem D: The sweep cut is a spectral graph partitioning technique that tries n − 1 different cuts (in an n-vertex graph) and picks one of them. Given X ∈ R n×d and y ∈ R n , consider solving the normal equations X >Xw = X >y for w ∈ R d . Let the SVD of X be X = UDV>. Let X + denote the Moore-Penrose pseudoinverse of a matrix X. Which of the following statements are certain to be true, for any values of X and y? A: w = (X >X) −1X >y is a solution of the normal equations. B: w = X + y is a solution of the normal equations. C: w = VD+U >y is a solution of the normal equations. D: Every solution w to the normal equations is a solution to Xw = y. Which of the following are typical benefits that might motivate you to preprocess data with principal components analysis (PCA) before training a classifier? A: PCA tends to reduce the bias of your classification algorithm. B: PCA can be used to avoid overfitting. C: PCA tends to reduce the variance of your classification algorithm. D: PCA can be used to avoid underfitting. For binary classification, which of the following statements are true of AdaBoost with decision trees? It usually has lower bias than a single decision tree It is popular because it usually works well even before any hyperparameter tuning To use the weight wi of a sample point Xi when training a decision tree G, we scale the loss function L(G(Xi), yi) by wi It can train multiple decision trees in parallel

Which of the following are typical benefits that might motivate you to preprocess data with principal components analysis (PCA) before training a classifier? A: PCA tends to reduce the bias of your classification algorithm. B: PCA can be used to avoid overfitting. C: PCA tends to reduce the variance of your classification algorithm. D: PCA can be used to avoid underfitting.

b,c Suppose your training set for two-class classification in one dimension (d = 1; xi ∈ R) contains three sample points: point x1 = 3 with label y1 = 1, point x2 = 1 with label y2 = 1, and point x3 = −1 with label y3 = −1. What are the values of w and b given by a hard-margin SVM? A: w = 1, b = 1 B: w = 0, b = 1 C: w = 1, b = 0 D: w = ∞, b = 0 Select the true statements about principal components analysis (PCA). A: PCA is a clustering algorithm. B: PCA produces features (principal coordinates) that are linear combinations of the input features. C: The principal components are chosen to maximize the variance in the projected data. D: The principal coordinates are the eigenvalues of the sample covariance matrix. Select the correct statements about the Fiedler vector. A: The Fiedler vector is the eigenvector of the Laplacian matrix that is associated with the smallest eigenvalue B: The Fiedler vector always satisfies the balance constraint (as written as an equation) C: The Fiedler vector is a solution to the unrelaxed, NP-hard optimization problem D: The sweep cut is a spectral graph partitioning technique that tries n − 1 different cuts (in an n-vertex graph) and picks one of them. Let classifier A be a random forest. Let classifier B be an ensemble of decision trees with bagging—identical to classifier A except that we do not limit the splits in each treenode to a subset of the features; at every treenode, the very best split among all d features is chosen. Which statements are true? A: After training, all the trees in classifier B must be identical B: Classifier B will tend to have higher bias than Classifier A C: Classifier B will tend to have higher variance than Classifier A D: Classifier B will tend to have higher training accuracy than Classifier A

Select the true statements about principal components analysis (PCA). A: PCA is a clustering algorithm. B: PCA produces features (principal coordinates) that are linear combinations of the input features. C: The principal components are chosen to maximize the variance in the projected data. D: The principal coordinates are the eigenvalues of the sample covariance matrix.

In each plot below, the data is projected onto two (unit-length) principal component vectors. We say that a plot is "valid" if the x-coordinate (written as "PC1") would be the first chosen principal coordinate and the y-coordinate (written as "PC2") would be the second chosen principal coordinate. Which plots are valid? Which of the following methods will cluster the data in panel (a) of the figure below into the two clusters (red circle and blue horizontal line) shown in panel (b)? Every dot in the circle and the line is a data point. In all the options that involve hierarchical clustering, the algorithm is run until we obtain two clusters. A: Hierarchical agglomerative clustering with Euclidean distance and complete linkage B: Hierarchical agglomerative clustering with Euclidean distance and single linkage C: Hierarchical agglomerative clustering with Euclidean distance and centroid linkage D: k-means clustering with k = 2 Write the SVD of an n × d design matrix X (with n ≥ d) as X = UDVT . Which of the following are true? The components of D are all nonnegative If X is a real, symmetric matrix, the SVD is always the same as the eigendecomposition The columns of V all have unit length and are orthogonal to each other The columns of D are orthogonal to each other We are using an ensemble of decision trees for a classification problem, with bagging. We notice that the decision trees look too similar. We would like to build a more diverse set of learners. What are possible ways to accomplish that? A: Increase the size of each random subsample B: Decrease the size of each random subsample C: Apply normalization to the design matrix first D: Sample without replacement

In each plot below, the data is projected onto two (unit-length) principal component vectors. We say that a plot is "valid" if the x-coordinate (written as "PC1") would be the first chosen principal coordinate and the y-coordinate (written as "PC2") would be the second chosen principal coordinate. Which plots are valid?

b,c Select the correct statements about the k-nearest neighbor classifier. A: For exact nearest neighbor search in a very high-dimensional feature space, generally it is faster to use exhaustive search than to use a k-d tree. B: When using a k-d tree, approximate nearest neighbor search is sometimes substantially faster than exact nearest neighbor search. C: When using exhaustive search, approximate nearest neighbor search is sometimes substantially faster than exact nearest neighbor search. D: Order-k Voronoi diagrams are widely used in practice for k-nearest neighbor search (with k > 1) in a two-dimensional feature space. Which of the following are typical benefits of ensemble learning in its basic form (that is, not AdaBoost and not with randomized decision boundaries), with all weak learners having the same learning algorithm and an equal vote? A: Ensemble learning tends to reduce the bias of your classification algorithm. B: Ensemble learning tends to reduce the variance of your classification algorithm. C: Ensemble learning can be used to avoid overfitting. D: Ensemble learning can be used to avoid underfitting. Lasso (with a fictitious dimension), random forests, and principal component analysis (PCA) all . . . A: can be used for dimensionality reduction or feature subset selection B: compute linear transformations of the input features C: are supervised learning techniques D: are translation invariant: changing the origin of the coordinate system (i.e., translating all the training and test data together) does not change the predictions or the principal component directions Which of the following statement(s) about kernels are true? A: The dimension of the lifted feature vectors Φ(·), whose inner products the kernel function computes, can be infinite. B: For any desired lifting Φ(x), we can design a kernel function k(x,z) that will evaluate Φ(x) >Φ(z) more quickly than explicitly computing Φ(x) and Φ(z). C: The kernel trick, when it is applicable, speeds up a learning algorithm if the number of sample points is substantially less than the dimension of the (lifted) feature space. D: If the raw feature vectors x, y are of dimension 2, then k(x, y) = x 2 1 y 2 1 + x 2 2 y 2 2 is a valid kernel.

Which of the following are typical benefits of ensemble learning in its basic form (that is, not AdaBoost and not with randomized decision boundaries), with all weak learners having the same learning algorithm and an equal vote? A: Ensemble learning tends to reduce the bias of your classification algorithm. B: Ensemble learning tends to reduce the variance of your classification algorithm. C: Ensemble learning can be used to avoid overfitting. D: Ensemble learning can be used to avoid underfitting.

b,d Recall that in certain cases, Newton's method can converge to the global optimum of an objective function in just one step. For which of the following objective functions and methods will Newton's method always converge in just one step? (Assume λ > 0 where regularization is used.) A: Dualized, kernelized logistic regression where the cost function is the mean of the logistic losses B: Ridge regression with an ℓ2-regularized mean squared error C: A neural network with ReLU activation functions on the hidden units and an ℓ2-regularized mean squared error D: Dualized, kernelized ridge regression with an ℓ2-regularized mean squared error Select the correct statements about principal component analysis (PCA). A: PCA is a method of dimensionality reduction B: If we select only one direction (a one-dimensional subspace) to represent the data, the sample variance of the projected points is zero if and only if the original sample points are all identical C: The orthogonal projection of a point x onto a unit direction vector w is (x >w)w D: If we select only one direction (a one-dimensional subspace) to represent the data, PCA chooses the eigenvector of the sample covariance matrix that corresponds to the least eigenvalue Recall that k-means clustering (Lloyd's algorithm) takes n sample points X1, X2, . . . , Xn and seeks to find a vector y of cluster assignments that minimizes X k i=1 X yj=i Xj − µi 2 , where yj ∈ {1, 2, . . . , k} and the cluster center µi = 1 ni X yj=i Xj is the average of the sample points assigned to cluster i. Select the true statements. A: k-means is guaranteed to find clusters that minimize its cost function, as the steps updating the cluster assignments yj can be solved optimally, and so can the steps updating the cluster means µis. B: In the algorithm's output, any two clusters are separated by a linear decision boundary. C: It is not possible to kernelize the k-means algorithm, because the means µi are not accounted for in the kernel matrix. D: Statisticians justify k-means optimization by assuming a Gaussian prior on the means and applying maximum likelihood estimation. Which of the following are true about two-class Gaussian discriminant analysis? Assume you have estimated the parameters ˆµC, Σˆ C, ˆπC for class C and ˆµD, Σˆ D, ˆπD for class D.

Recall that in certain cases, Newton's method can converge to the global optimum of an objective function in just one step. For which of the following objective functions and methods will Newton's method always converge in just one step? (Assume λ > 0 where regularization is used.) A: Dualized, kernelized logistic regression where the cost function is the mean of the logistic losses B: Ridge regression with an ℓ2-regularized mean squared error C: A neural network with ReLU activation functions on the hidden units and an ℓ2-regularized mean squared error D: Dualized, kernelized ridge regression with an ℓ2-regularized mean squared error

a,b Select the true statements about the running time of k-means clustering of n sample points with d features each. A: The step that updates the cluster means µi , given fixed cluster assignments yj , can be implemented to run in at most O(nd) time. B: Increasing k always increases the running time. C: The step that updates the cluster assignments yj , given fixed cluster means µi , can be implemented to run in at most O(nkd) time. D: The k-means algorithm runs in at most O(nkd) time. Let classifier A be a random forest. Let classifier B be an ensemble of decision trees with bagging—identical to classifier A except that we do not limit the splits in each treenode to a subset of the features; at every treenode, the very best split among all d features is chosen. Which statements are true? A: After training, all the trees in classifier B must be identical B: Classifier B will tend to have higher bias than Classifier A C: Classifier B will tend to have higher variance than Classifier A D: Classifier B will tend to have higher training accuracy than Classifier A Suppose we are doing ordinary least-squares linear regression with a fictitious dimension. Which of the following changes can never make the cost function's value on the training data smaller? A: Discard the fictitious dimension (i.e., don't append a 1 to every sample point). B: Append quadratic features to each sample point. C: Project the sample points onto a lower-dimensional subspace with PCA (without changing the labels) and perform regression on the projected points. D: Center the design matrix (so each feature has mean zero). We are fitting a linear function to data in which some features are known to be much noisier than others. We account for this by applying an asymmetric penalty in ridge regression: in the normal equations, we replace the identity matrix with a different diagonal matrix. Each entry on the diagonal is a hyperparameter. Although there are many hyperparameters, suppose that we magically find the best hyperparameter values for our validation set. How is the result likely to differ from the result of standard ridge regression? A: Lower validation error. B: It is equivalent to placing an anisotropic Gaussian prior probability on the regression weights, then finding the weights that maximize the likelihood. C: The number of weights equal to zero tends to be greater. D: The difference is usually small, as the hyperparameters will tend to have almost the same value.

We are fitting a linear function to data in which some features are known to be much noisier than others. We account for this by applying an asymmetric penalty in ridge regression: in the normal equations, we replace the identity matrix with a different diagonal matrix. Each entry on the diagonal is a hyperparameter. Although there are many hyperparameters, suppose that we magically find the best hyperparameter values for our validation set. How is the result likely to differ from the result of standard ridge regression? A: Lower validation error. B: It is equivalent to placing an anisotropic Gaussian prior probability on the regression weights, then finding the weights that maximize the likelihood. C: The number of weights equal to zero tends to be greater. D: The difference is usually small, as the hyperparameters will tend to have almost the same value.

a,c Select the correct statements about AdaBoost. A: When we go from iteration t to iteration t + 1, the weight of sample point Xi is increased if the majority of the t learners misclassify Xi . B: Unlike with decision trees, two data points that are identical (Xi = Xj) but have different labels (yi , yj) can be classified correctly by Adaboost. C: AdaBoost can benefit from a learner that has only 5% training accuracy. D: If you train enough learners and every learner achieves at least 51% validation accuracy, Adaboost can always achieve 100% validation accuracy; Select the true statements about convolutional neural networks. A: Pooling layers (of edges) reduce the number of hidden units in the subsequent layer (of units). B: For a convolutional layer, increasing the number of filters decreases the the number of hidden units in the subsequent layer. C: Each unit in a convolutional layer is connected to all units in the previous layer. D: For a convolutional layer, increasing the filter height and width decreases the the number of hidden units in the subsequent layer. (Assume no padding.) Which of the following are true about PCA? covariance matrix symmetric. A: Appending a 1 to the end of every sample point doesn't change the results of performing PCA (except that the useful PC vectors have an extra 0 at the end, and there's one extra useless component with eigenvalue zero). B: If you use PCA to project d-dimensional points down to j principal coordinates, and then you run PCA again to project those j-dimensional coordinates down to k principal coordinates, with d > j > k, you always get the same result as if you had just used PCA to project the d-dimensional points directly down to k principle coordinates. C: If you perform an arbitrary rigid rotation of the sample points as a group in feature space before performing PCA, the PC directions do not change. D: Same intro as C, the largest eigenvalue of the sample covariance matrix does not change. We are given n training points having d features each. Select the true statements about applying a k-nearest neighbor algorithm to a test point. A: It is possible to implement the algorithm to use the ℓ1 metric as your distance function. B: The k-d tree k-nearest neighbor algorithm is fast because it computes the distance between the test point and a training point for only k training points. C: There is a k-nearest neighbor algorithm that classifies a test point in at most O(nd + n log k) time, even if k is much larger than d. D: The k-nearest neighbor algorithm can be used for classification, but not regression.

We are given n training points having d features each. Select the true statements about applying a k-nearest neighbor algorithm to a test point. A: It is possible to implement the algorithm to use the ℓ1 metric as your distance function. B: The k-d tree k-nearest neighbor algorithm is fast because it computes the distance between the test point and a training point for only k training points. C: There is a k-nearest neighbor algorithm that classifies a test point in at most O(nd + n log k) time, even if k is much larger than d. D: The k-nearest neighbor algorithm can be used for classification, but not regression.

b,c,d Let X be a matrix with singular value decomposition X = UΣV >. Which of the following are true for all X? A: rank(X) = rank(Σ). B: If all the singular values are unique, then the SVD is unique. C: The first column of V is an eigenvector of X >X. D: The singular values and the eigenvalues of X >X are the same. Select the true statements about the singular value decomposition (SVD) and the eigendecomposition. ⃝ A: The SVD applies only to square matrices. B: The eigendecomposition applies only to square matrices. C: The right singular vectors of a matrix X ∈ R n×d are eigenvectors of X ⊤X. D: Consider a non-square matrix X ∈ R n×d and the vector w ∈ R d \ {0} that maximizes the Rayleigh quotient (w ⊤X ⊤Xw)/(w ⊤w). The singular values of X are no greater than the (positive) square root of the maximum Rayleigh quotient. Which of the following are benefits of using convolutional neural networks—as opposed to fully connected ones— for image recognition tasks? A: The ability to express a wider variety of more complicated functions of the input features B: Fewer model architecture hyperparameters for the designer to select C: Enables the network to more easily learn and recognize features regardless of their position in the image D: Typically requires less data to train well Consider an n × d design matrix X with labels y ∈ R n . What is true of fitting this data with dual ridge regression with the polynomial kernel k(Xi , Xj) = (X T i Xj + 1)p = Φ(Xi) >Φ(Xj) and regularization parameter λ > 0? If the polynomial degree is high enough, the polynomial will fit the data exactly The algorithm computes Φ(Xi) and Φ(Xj) in O(d p ) time The algorithm solves an n × n linear system When n is very large, this dual algorithm is more likely to overfit than the primal algorithm with degree-p polynomial features

Select the true statements about the singular value decomposition (SVD) and the eigendecomposition. ⃝ A: The SVD applies only to square matrices. B: The eigendecomposition applies only to square matrices. C: The right singular vectors of a matrix X ∈ R n×d are eigenvectors of X ⊤X. D: Consider a non-square matrix X ∈ R n×d and the vector w ∈ R d \ {0} that maximizes the Rayleigh quotient (w ⊤X ⊤Xw)/(w ⊤w). The singular values of X are no greater than the (positive) square root of the maximum Rayleigh quotient.

b In which of the following cases should you prefer k-nearest neighbors over k-means clustering? For all the four options, you have access to images X1, X2, . . . , Xn ∈ R d . A: You do not have access to labels. You want to find out if any of the images are very different from the rest, i.e., are outliers. B: You have y1, y2, . . . , yn telling us whether image i is a cat or a dog. You want to find out whether the distribution of cats is unimodal or bimodal. You already know that the distribution of cats either has either one or two modes, but that's all you know. C: You have access y1, y2, . . . , yn telling us whether image i is a cat or a dog. You want to find out whether a new image z is a cat or a dog. D: You have y1, y2, . . . , yn telling us whether image i is a cat or a dog. Given a new img z, you want to approximate the posterior probability of z being a cat and the posterior probability of z being a Select the true statements about awards given for research related to this course. A: A Nobel Prize in Physiology was awarded for characterizing action potentials in squid axons. B: A Nobel Prize in Physiology was awarded for discoveries about how neurons in the visual cortex process images. C: A Turing Award was awarded for work on deep neural networks. D: A Godel Prize was awarded for the paper on ¨ AdaBoost. Select the true statements about AdaBoost for two-class classification. A: We can train all T weak learners simultaneously in parallel. B: After a weak learner is trained, the weights associated with the training points it misclassifies are increased. C: The coefficient βT assigned to weak learner GT is 0 if the weighted error rate errT of GT is 1. D: AdaBoost makes no progress if it trains a weak learner only to discover that its weighted error rate is substantially greater than 0.5. Which of the following statements about AdaBoost is true? A: AdaBoost is a natural good fit with the 1-nearest neighbor classifier. B: AdaBoost can give you a rough estimate of the posterior probability that a test point is in the predicted class. C: AdaBoost trains multiple weak learners that classify test points by equal majority vote. D: AdaBoost with an ensemble of soft-margin linear SVM classifiers allows the metalearner to learn nonlinear decision boundaries.

Select the true statements about AdaBoost for two-class classification. A: We can train all T weak learners simultaneously in parallel. B: After a weak learner is trained, the weights associated with the training points it misclassifies are increased. C: The coefficient βT assigned to weak learner GT is 0 if the weighted error rate errT of GT is 1. D: AdaBoost makes no progress if it trains a weak learner only to discover that its weighted error rate is substantially greater than 0.5.

Select the correct statements about AdaBoost. A: When we go from iteration t to iteration t + 1, the weight of sample point Xi is increased if the majority of the t learners misclassify Xi . B: Unlike with decision trees, two data points that are identical (Xi = Xj) but have different labels (yi , yj) can be classified correctly by Adaboost. C: AdaBoost can benefit from a learner that has only 5% training accuracy. D: If you train enough learners and every learner achieves at least 51% validation accuracy, Adaboost can always achieve 100% validation accuracy; Which of the following are valid kernel functions? A kernel function k(x,z) is valid when there exists some function Φ : R d → S where S is a space (possibly finite, possibly infinite) that has inner products such that we can write k(x,z) = Φ(x) ⊤Φ(z). Suppose you have a fixed dataset and want to train a decision tree for two-class classification. If you increase the maximum depth of the decision tree, which of the following are possible effects? A: The test accuracy goes up. B: The training accuracy goes down. C: The number of pure leaves is reduced. D: The time to classify a test point increases. Which of the following are true of decision trees? Assume splits are binary and are done so as to maximize the information gain. If there are at least two classes at a given node, there exists a split such that information gain is strictly positive As you go down any path from the root to a leaf, the information gain at each level is non-increasing The deeper the decision tree is, the more likely it is to overfit Random forests are less likely to overfit than decision trees

Which of the following are valid kernel functions? A kernel function k(x,z) is valid when there exists some function Φ : R d → S where S is a space (possibly finite, possibly infinite) that has inner products such that we can write k(x,z) = Φ(x) ⊤Φ(z).