ECE 461/661: Introduction to Machine Learning for Engineers Homework #4

a.  [2 points]

b.  [2 points]

c.  [2 points]

0 < ξi  ≤ 1

ξi  > 1

ξi = 0

1.2    Properties of Kernels [12 points]

We have seen in lecture that we can use kernel functions to learn nonlinear SVM models.  Recall from the lecture that a function K(x, z) : Rd  × Rd  → R is considered a valid kernel function if (i) it is symmetric (that is, K(x, z) = K(z, x)), and (ii) it is positive-definite (that is, K(x, x) > 0 if x  0).

Given that K0 (x, z) : Rd  × Rd  → R and K1 (x, z) : Rd  × Rd  → R are valid kernels, prove the following kernels are also valid.

a.  [2 points]

b.  [2 points]

c.  [2 points]

d.  [3 points]

e.  [3 points]

Product Rule: Ka(x, z) = K0 (x, z)K1 (x, z)

Scaling Rule: Kb(x, z) = f(x)K0 (x, z)f(z) for any function f : Rd → R.

Sum Rule: Kc(x, z) = αK0 (x, z) + βK1 (x, z) where α,β ≥ 0

Kd(x, z) = exp(K0 (x, z)) (You can use the above 3 rules.)

Using the above rules, suppose that K0 (x, z) = 1 and K1 (x, z) = xTz.  Prove that the

following kernel is valid:

Ke(x, z) =    1 +  T  !2

2    k −Nearest Neighbors [24 points]

2.1    Curse of Dimensionality [16 points]

When the number of features d is large, the performance of k-nearest neighbors, which makes predictions using only observations that are near the test observation, tends to degrade. This phenomenon is known as the curse  of dimensionality, and it ties into the fact that non-parametric approaches often perform poorly when d is large.

a.  [4 points]  Suppose that we have a set of training observations, each corresponding to a one-dimensional (d = 1) feature, X.  We assume that X is uniformly (evenly) distributed on [0, 1].  Associated with each training observation is a response value.

Suppose that we wish to predict a test observation x’s response using only training observations that are within 10% of the range of x closest to that test observation. In other words, if x ∈ [0.05, 0.95] then we will use training observations in the range [x − 0.05,x + 0.05], as shown in Figure 1 when x = 0.6. When x ∈ [0, 0.05) we use the range [0, 0.1], and when x ∈ (0.95, 1] we use training observations in the range [0.9, 1]. Figure 1 shows this range for x = 0.02.

On average (assuming x is uniformly distributed on [0, 1]), what fraction of the available observations will we use to make the prediction?

Range of observation, d = 1

b.  [4 points]   Now suppose that we have a set of observations, each corresponding to two features, X1 and X2  (i.e., d = 2). We assume that (X1,X2) are uniformly distributed on [0, 1] × [0, 1]. We wish to predict the response of a test observation (x1,x2) using only training observations that are within 10% of the range of x1  and within 10% of the range of x2  closest to that test observation. For instance, in order to predict the response for a test observation with x1  = 0.6 and x2  = 0.04, we will use training observations (X1,X2) such that X1  ∈ [0.55, 0.65] and X2  ∈ [0, 0.1].  On average, assuming x1  and x2 are each uniformly distributed on [0, 1], what fraction of the available observations will we use to make the prediction?

c.  [4 points]   Now suppose that we have a set of training observations on d = 100 features.  Again the observations are uniformly distributed on each feature, and again each feature ranges in value from

0 to 1.  We wish to predict a test observation’s response using observations within the 10% of each feature’s range that is closest to that test observation. What fraction of the available observations will we use to make the prediction?

d.  [2 points]   Using your answers to parts a–c, argue that a drawback of k-nearest neighbors when d is large is that there are very few training observations “near” any given test observation.

e.  [2  points]    Now suppose that we wish to make a prediction for a test observation by creating a d-dimensional hypercube centered around the test observation that contains, on average, 10% of the training observations. For d = 1, 2, and 100, what is the length of each side of the hypercube? How does your answer change as d increases, and what does this imply for the accuracy of k-nearest neighbors when d is large?

Note:  A hypercube is a generalization of a cube to an arbitrary number of dimensions. When d = 1, a hypercube is simply a line segment, when d = 2 it is a square, and when d = 100 it is a 100-dimensional cube.

2.2    An Alternative of k-NN Algorithms [8 points]

Computing the distances between all data points and the new input x in the k-NN algorithm can be inefficient if we have too many features.  For binary-valued data (where yi  ∈ {−1, 1}), we can eliminate the need to compute these distances by deriving a simpler decision rule.  To do so, we first precompute the centers of mass µ1  and µ0  for label 1 and label − 1 respectively:

1

=

yi=1

1

yi = − 1

Here n1  and n − 1  indicate the number of the training points labelled 1 and -1 respectively.

We can define a new classifier f(x) that classifies a data point x by comparing the ℓ2  distances between x and the centers of mass for each class. In other words, f(x) should return the label 1 if x is closer to µ1 than it is to µ − 1, and it should return the label -1 if x is closer to µ − 1  than it is to µ1. This classifier can be written in the form f(x) = sgn(α < γ,x > +β) where:

f(x) = 

Here sgn(a) is the sign function, which takes value 1/-1 when a is positive/negative.

Find expressions for α , β and γ that depend on µ0  and µ1. Note that, since these values do not depend on x, they do not need to be re-computed whenever we classify a new data point x.

[Hint:]  Use the property that for vectors a, b ∈ Rn, we have:  ||a − b|| = ||a|| + ||b|| − 2 < a, b >.

Note:  In fact, this new classifier could be represented as f(x) = sgn(P αi  < xi , x > +β), which is close to a weighted (n1 +n− 1) −nearest neighbors classifier with the weight based on the distance to the new data point and the number data points of each class. However, our derived new classifier drastically reduces the computations required compared to k-nearest neighbors.

3    Decision Tree [24 points]

3.1    KL-Divergence and Information Gain [10 points]

We have introduced  “information gain” and  “mutual information” during the class as a way to evaluate the informativeness of each feature in our training dataset.  In this part, we are going to prove that the

information gain is always non-negative.  First, we introduce the Kullback-Leibler  (KL) Divergence between two discrete probability distributions p and q.  Each can take values 1, 2,...,n, with associated probabilities {p1 , ··· ,pn} and {q1 , ··· ,qn} respectively. The KL Divergence is defined as:

D(p∥q) = X(n)pi log pi

Intuitively, the KL Divergence measures the ”similarity” of two distributions, which is sometimes called the ”relative entropy”.  In answering the below problems, you may assume that the KL Divergence is always nonnegative (i.e., D(p∥q) ≥ 0 for any probability distributions p and q) and that D(p∥q) = 0 if and only if p = q.

a.  [3 points]   Does D(p∥q) = D(q∥p) for arbitrary distributions p and q? Please explain your answer.

b.  [3 points]  Use the properties of KL Divergence to prove that the information gain of random variables X and Y is always non-negative (i.e. I(X; Y) ≥ 0).

c.  [4 points]   Show that I(X;Y) = H(X) − H(X|Y). Combining with the results with part (b), we can show an important property of entropy, that is conditioning reduces entropy (i.e. H(X|Y) ≤ H(X)).

3.2    An Example Decision Tree [14 points]

In this section, we are going to construct decision trees to predict whether a student will pass the course or not. The following is the data of the course ”Introduction to Machine Learning for Kids” at Cranberry-Melon Elementary School:

a.  [6 points]  Explain the meaning of information gain and calculate the three information gains between Pass/Fail and the three features using log to the base 2.

b.  [8 points]   Construct the decision trees using your answer above.  Draw the tree and label each leaf node clearly.

4    Boosting [16 points]

We learned about boosting in lecture, and the topic is covered in Murphy 16.4. On page 555 Murphy claims that “it was proved that one could boost the performance (on the training set) of any weak learner arbitrarily high, provided the weak learner could always perform slightly better than chance.” We will now verify this statement in the AdaBoost framework.

4.1  [2 points]   Given a set of N observations (xj,yj) where yj  is the label yj  ∈ {−1, 1}, let ht(x) be the weak classifier at step t and let βt  be its weight. First we note that the final classifier after T steps is defined as:

H(x) = sgn (βtht(x)) = sgn{f(x)},

4

where

T

f(x) = Xβtht(x).

t=1

Show that:

N                                               N

ϵTraining = N X 1{H(xj)yj}  ≤ N X exp( −f(xj)yj),

j=1                                        j=1

where 1{H(xj)yj}  is 1 if H(xj)  yj  and 0 otherwise.

4.2  [4 points]   The weight for each data point j at step t + 1 can be defined recursively by:

wt+1) =                                    ,

where Zt  is a normalizing constant ensuring the weights sum to 1:

N

Zt = X wt) exp( −βtyjht(xj)).

j=1

Show that:

N                                               T

N Xexp( −f(xj)yj) = Y Zt

j=1                                        t=1

4.3 By combining your results to parts a and b, you have shown that the training error ϵTraining is bounded above by Q Zt. At step t the values Z1,Z2,...,Zt − 1  are already fixed. Therefore, at step t we can choose βt  to minimize Zt. Let

ϵt = X wt)1{ht(xj)yj}

j=1

be the weighted training error for weak classifier ht(x). Then we can re-write the formula for Zt  as: Zt = (1 − ϵt)exp( −βt) + ϵt exp(βt).

a.  [3 points]   First, find the value of βt  that minimizes Zt. Then show that Z = 2pϵt(1 − ϵt)

b.  [2 points]   Assume we choose βt  to have this optimal value, and thus that Zt  = Z.  We can express the training error ϵt =  − γt, so that γt  > 0 implies that the weak classifier ht(x) performs better than random (i.e., the weighted training error ϵt  < ) and γt  < 0 implies that it performs worse than random. Then show that:

Zt  ≤ exp( −2γ)

You may take as given the fact that ln(1 − x) ≤ −x for 0 ≤ x < 1.

Putting together this result with your results from parts a and b, you have shown that:

T                                  T

ϵtraining  ≤ Y Zt  ≤ exp( −2 Xγ)

t=1                              t=1

c.  [3 points]   Now, if the weak classifier does slightly better than random guessing, i.e., γt  ≥ γ > 0 (recall for γt   = 0, the error ϵt   = 0.5, which is the error you would get by random guessing,

assuming each class has roughly the same size), then show that:

ϵtraining  ≤ exp( −2Tγ2)

From the above expression, we can infer that by increasing T (the number of weak classifiers) we can make the training error arbitrarily small.

d.  [2 points]   Finally, consider the case when γt  ≤ −γ, ∀ t and γ > 0.  Note that in this case the error for each weak classifier ϵt  > 0.5, i.e. the weak classifiers do worse than random guessing. Is it still possible to make ϵtraining  arbitrarily small? Provide a justification for your answer.

5    SVM: Implementation [18 points]

In this problem, you will experiment with SVMs on a real-world dataset. You will implement a linear SVM (i.e., an SVM using the original features). You should implement it from scratch without using any libraries like scikit-learn, although you can use existing packages to solve quadratic programs. If you are not sure if the API you want to use is allowed, please ask the TAs or post a question on Piazza. Please submit your source code as part of the homework PDF that you submit.

Dataset: We have provided the Splice Dataset from UCI’s machine learning data repository.1  The provided binary classification dataset has 60 input features, and the training and test sets contain 1,000 and 2,175 samples, respectively. The files containing features are called train data.txt and test data.txt, and the files containing labels are called train label.txt and test label.txt.

5.1    Data preprocessing [4 points]

Let x , ··· ,xN)  be the values of feature k for all sample points. Preprocess the training and test data by a. Computing the mean xk  =  P xi) of each feature and subtracting it from all values of this feature.

b. Dividing each feature by its standard deviation, defined as

for feature k. Here, xk  is the sample mean of this feature.

This type of preprocessing is useful for SVMs, as SVMs attempt to maximize the distance between the separating hyperplane and the support vectors.  If one feature (i.e., one dimension in this space) has very large values, it will dominate the other features when calculating this distance. Rescaling the features (e.g. to [0, 1]), will ensure that they all have the same influence on the distance metric.

Note that the mean and standard deviation should be estimated from the  training  data and then applied to both datasets.  Explain why this is the case.  Also, report the mean and the standard deviation of the 3rd and 10th features on the training data.