ML midterm

Question 1

Consider a set of classifiers that includes all linear classifiers that use different choices of strict subsets of the components of the input vectors x∈Rd. Claim: the VC-dimension of this combined set cannot be more than d+1.

Answer 1

True

Question 2

It is impossible to overfit to the test set if one only uses it for evaluation.

Answer 2

False

Question 3

If the target function is deterministic, overfitting cannot occur.

Answer 3

False

Question 4

For a given linear regression problem with weight decay, there is a λ>0
regularization coefficient so that the optimal weight vectors of the regularized problem is the same as for the unregularized problem

Answer 4

True

Question 5

If the VC dimension of a model is infinite, then VC theory still guarantees generalization, but the bound is looser.

Answer 5

False

Question 6

If a data set of size k cannot be shattered by a hypothesis set H, then k is H’s break point.

Answer 6

True

Question 7

The cross-entropy error for a logistic regression model has an upper bound when all the samples are classified correctly.

Answer 7

True

Question 8

Consider the following hypotheses: h1(x)=w1x1 and h2(x)=1−w1x1, where x1 is the first component of the input vector x. Then for any dataset, the absolute difference between Eout and Ein can be proven to be the same for the two hypotheses.

Answer 8

False

Question 9

Underfitting occurs when the in sample error gets larger than the out of sample error.

Answer 9

False

Question 10

Hard Support Vector Machines work by trying to find a separating hyperplane that correctly classifies all elements in the training dataset while maximizing the distance of the nearest points to this separator.

Answer 10

True

Question 11

Stochastic Gradient Descent is made stochastic with respect to normal Gradient Descent by adding a randomized extra noise term to the estimation of the gradient.

Answer 11

False

Question 12

If the target function is not a linear function, then the training dataset cannot linearly separable.

Answer 12

False

Question 13

Polynomial regression is not a linear problem, so Stochastic Gradient Descent cannot be used.

Answer 13

False

Question 14

The Hoeffding Inequality implies that the increase of the generalization error is bounded from below by a logarithmic function of the growth of the size of the training set.

Answer 14

False

Question 15

The test set can be used to estimate the out of sample error.

Answer 15

True

Question 16

The following model is linear (with respect to the parameters w):

h(x)=w1sin(x1)+ew2x2

Answer 16

False

Question 17

There exists a dataset of size dVC+1 for which Ein>0.

Answer 17

True

Question 18

If the training set is linearly separable, then the pocket algorithm returns a worse model (in approximating the target function) than PLA.

Answer 18

False

Question 19

The Ein obtained by normal linear regression is not larger than the Ein obtained by linear regression with weight decay.

Answer 19

True

Question 20

The gradient of the error with respect to the weights can be estimated on one sample and this estimation is unbiased.

Answer 20

True

Question 21

The following model is linear (with respect to the parameters):

h(x)=w1sin(x1)+w2ex2−w3x1x2

Answer 21

True

Question 22

By using the cross-entropy error measure, logistic regression is guaranteed not to get stuck in a local minimum of the error function.

Answer 22

True

Question 23

Ein=0 for all datasets of size at most dVC.

Answer 23

True

Question 24

It is possible for a growth function to have more than one break point.

Answer 24

False

Question 25

In Gradient Descent, too small step size can lead to slow learning.

Answer 25

True

Question 26

The training set can be used to estimate the in sample error

Answer 26

True

Question 27

The squared error measure can be decomposed into bias and variance term

Answer 27

True

Question 28

In gradient desxent the step size should be as small as possible, to avoid instability

Answer 28

False

Question 29

The PLA is guaranteed to terminate in a finite number of steps

Answer 29

False

Question 30

In each step of Gradient descent, the gradient of the error is added to the weigths

Answer 30

False

Question 31

The variance of model measures the expected squared difference between the output of the model and the target value.

Answer 31

False

Question 32

When considering a missclassified sample, the PLA algorithm will moe the separator in the direction of classifying that sample correctly

Answer 32

True

Question 33

The Hoeffding Inequality implies that the generalisation error decreases as the model complexity is increased

Answer 33

False

Question 34

If we decrease the regularization coefficiont, the generalization error decreases when using weight decay

Answer 34

False

Question 35

Nonlinear transformation of the inputs cannot increase the VC dimension.

Answer 35

False

Question 36

There exists no closed analytical formula to determine the weigths of a linear regression problem that minimise the sample error

Answer 36

False

Question 37

The gardient descent algo is used to find local minimum in a logistic regression problem.

Answer 37

True

Question 38

The Hoeffding inequality implies that the generalisation error grows as the size of the dataset grows

Answer 38

False

Question 39

The best stopping criterion for an iterative classification algorithm is to stop only when Ein stops decreasing.

Answer 39

False

Question 40

lt is impossible for any learning algorithm to generalise to unseen examples, ie. the output for those will be random.

Answer 40

False

Question 41

Stochastic Gradient Descent differs from normal Gradient Descent in that it adds an extra noise term after the estimation gradient.

Answer 41

False

Question 42

Regularization is commonly used to speed up the optimization process.

Answer 42

False

Question 43

Regularization can improve generalisation.

Answer 43

True

Question 44

Using a model with the same complexity as the target function does not prevent overfitting.

Answer 44

True

Question 45

When considering a misclassified sample, the PLA algorithm will move the separator in a way to ensure that after this update the sample will be classified correctly.

Answer 45

False

Question 46

Increasing the amount of testing data reduces overfitting.

Answer 46

False

Question 47

After hyperparameter optimization, the validation error is an unbiased estimate for Eout.

Answer 47

False

Question 48

For hypothesis space H with VC dimension dVC:dVC>=N implies that there exists a dataset of size N that H sthatters

Answer 48

True

Question 49

Increasing the amount of training data reduces overfitting.

Answer 49

True

Question 50

A growth function with a breakpoint k can be bounded by a polynomial of degree k -1.

Answer 50

True

Question 51

Overfitting happens when the in sample error is larger (“goes over”) than the out of sample error.

Answer 51

False

Question 52

The validation set can be used to optimize hyperparameters.

Answer 52

True

Question 53

Polynomial regression is not a linear problem, so Stochastic Gradient Descent cannot be used.

Answer 53

False

Question 54

The perceptron model is a linear separator.

Answer 54

True

Question 55

Since the (logistic) sigmoid function is not linear, the logistic regression model
is also nonlinear

Answer 55

False

Question 56

Overfitting occurs when the out of sample error gets larger than the in sample
error.

Answer 56

False

Question 57

The cross-entropy error for a logistic regression model does not have an upper
bound

Answer 57

True

Question 58

The Rademacher bound can be used to bound the 0-1 loss of a classification
model.

Answer 58

True

Question 59

The obtained by normal linear regression is not larger than the Ein
obtained by linear regression with weight decay.

Answer 59

True

Question 60

In Gradient Descent, as a general rule of thumb, the step size should be
chosen to be small enough to keep the magnitude of the gradient under
to avoid instability.

Answer 60

False

Question 61

When considering a misclassified sample, the
PLA algorithm will move the separator in the
direction of classifying that sample correctly,
however, the sample might still be classified
incorrectly after the weight update.

Answer 61

True

Question 62

The vector (the normal of the separating hyperplane) in an SVM is in the span of the input samples x_i.

Answer 62

True

Question 63

A not linearly separable dataset can become linearly separable if further features are added.

Answer 63

True

Question 64

In each step of Gradient Descent, the gradient of the error is subtracted from the weights.

Answer 64

True

Question 65

If the training set is not linearly separable, then the perceptron learning algorithm always goes into an infinite loop.

Answer 65

True