Machine Learning Homework #3 Solution

i=1
 
1.  (15  points) Let  D  = {(xi , yi )}n


be a dataset for a 2-class classification  problem,  where

1, +1}


.  We consider  developing boosting  algorithms  for the problem.   At iteration t

of boosting,  the  distribution over the  dataset is denoted  by wt , and  we assume  access to a weak learning  algorithm  which generates  a classifier Gt whose error rate   t = Px∼wt [Gt (x) = y] ≤ ( 1 −  γ ), for all t, where 0 < γ ≤ 1.

2        2



t=1
 
(a)  (10 points)  Let  g(x)  = sign   PT


 

αt Gt (x)   .   For  Adaboost,   show that the  training

error-rate satisfies the following inequality:

 

1   N                                                            γ2



N
 
   X ✶(g(xi ) = yi ) ≤ exp

i=1


− 2 T     ,

where  ✶(·)  denotes  the  indicator  function,  which  is 1 if the  argument  is true,  and  0 otherwise.

(b)  (5 points)  Assuming that we can always get a weak classifier Gt whose error-rate satisfies

 t ≤ ( 1  − γ ) for 0 < γ  ≤ 1, will the  training  error-rate  1  PN


✶(g(xi ) = yi ) always

2        2                                                                                                              N


i=1

become zero as T is increased, i.e., we keep adding more weak classifiers? Clearly explain

your answer.

 



}i=1
 
2.  (30 points) Consider a two class classification problem setting with training  data {(xi , yi )  n where yi ∈ {0, 1} and xi ∈ Rd . Consider a linear activation model ai = a(xi , w) = wT xi , and activation functions  of the form

 

fsigmoid (ai )   =


1

,                                                (1)

1 + exp(−ai )

frelu (ai )   =  max(0, ai ) .                                                     (2)

 

(a)  (15 points)  The  square  loss on the  entire  dataset in terms  of the  activation function

fsigmoid  applied  to all the activations a = [a1   . . .  an ] is given by

 



sq              (a) =
 
n

 

 

 

Is L(sigmoid)


L(sigmoid)


X

 

i=1


(yi − fsigmoid (ai ))2   .

sq                a convex function  of the  activation vector  a?   Clearly  explain/prove your

answer with necessary (mathematical) details,  including the definition of convexity  you are using.

(b)  (15 points)  The square loss on the entire dataset in terms of the activation function frelu

applied  to all the activations a = [a1   . . .  an ] is given by

 

n



sq       (a) =
 
L(relu)


X

 

i=1


(yi − frelu (ai ))2   .

 



Is L(relu)
 
sq        a convex function of the activation vector a?  Clearly explain/prove your answer with  necessary  (mathematical) details,   including  the  definition  of convexity  you  are using.

 

3.  (15  points) Recall that gradient boosting can work with any loss function L(y, F (x)),  where the additive  model Fm (x) = Fm−1(x) + ρm h(x; am ).  Consider  a 2-class classification setting, where the loss for gradient boosting  is the logistic loss, i.e.,

 

n

L(y, F (x))  = X −yi F (xi ) + log(1 + exp(yi F (xi ))

i=1

 

(i)  (10 points)  Assuming  the current function  to be Fm−1(x), what  is the gradient gm (xi ) computed  at  F (x)  = Fm−1(x) at  point  xi ?  What  is the  optimization problem  which needs to be solved to obtain  h(x, am )?

(ii)  (5 points)  What  is the optimization problem which needs to be solved to obtain  the step size ρm  for the additive  model Fm (x) = Fm−1(x) + ρm h(x; am )?  Does the problem have a closed form solution?  Clearly explain your answer.

 

Programming assignments: The  next  problem  involves programming.  We will be using the Boston housing dataset. The dataset has 506 points,  13 features,  and 1 target  (response) variable.  You can find more information about the dataset here: https://archive.ics.uci.edu/ml/datasets/Housing

While the original dataset is for a regression problem, we will create two classification datasets for the  homework.    Note  that you  only  need  to  work  with  the  target t to  create  these classification dataset, the data X  should not be changed.

 

a.  Boston50: Let  τ50  be the  median  (50th  percentile)  over all t (response)  values.   Create a  2-class classification  problem  such  that y  = 1 if t ≥ τ50   and  y  = 0 if t < τ50 .   By construction, note that the class priors will be p(y = 1) ≈ 1 , p(y = 0) ≈ 1 .

2                              2

b.  Boston75: Let  τ75  be the  75th  percentile  over all t (response)  values.   Create  a 2-class classification  problem  such that y = 1 if t ≥ τ75  and  y = 0 if t < τ75 .  By construction, note that the class priors will be p(y = 1) ≈ 1 , p(y = 0) ≈ 3 .

4                              4

 

*The original Boston dataset is  provided on  Moodle course page in  csv  format. The last column shows target values, which is continuous (house price). All  other columns are data values. Each row is a input point. Same as HW1, your functions (main) will  take the original Boston dataset as  input and output results for  both Boston50 and Boston75 in  one  run.

 

4.  (40  points) Train  and evaluate  the following classifiers using 10-fold cross-validation:

 

(a)  (20 points)  Adaboost  using  2-layer  decision trees  with  binary  splits  using  Information

Gain with the following number  of base classifiers: B = [5, 10, 15, . . . , 50].

(b)  (20 points)  Random  forest  of 100 2-layer  decision trees  with  binary  splits  using  Infor- mation  Gain  with  the  size of the  random  feature  set  M  = [1, 2, . . . , 13].  Note  that for M = 13, we get a bagged trees.

You will have  to  submit  (i)  summary of  methods and results, and  (ii)  code for each algorithm:

 

(i)  Summary of  methods and results: Briefly describe  the algorithms  in (a)  and  (b)

along with necessary equations,  e.g., for splitting  on a feature. For (a),

•  Provide  a table  of the training  and test  set error rates  for each fold and number  of base classifiers.  This will be a 20 × 10 table.  Row 2i − 1 and 2i should correspond to the  ith  fold train  and  test  error  respectively  and  columns  pertains  to different number  of base classifiers, i.e., B = [5, 10, 15, . . . , 50].

•  Also provide  the  training  and  test  set average  error  rates  and  standard deviation across all folds for each number  of base classifiers. This can be two rows under  the above table,  providing  mean and standard deviation  of each column.

•  Finally,  include a plot of the training  and test set average error rates as the number of base classifiers increase.

For (b),

•  Provide  a table of the training  and test  set error rates  for each fold and value of M .

Similar to the above specification,  the table  will be 20 × 13.

•  Also provide  the  training  and  test  set average  error  rates  and  standard deviation across all folds for each value of M . This will add two other rows to the above table.

•  Finally,  include a plot  of the  training and  test  set average  error  rates  as the  value of M  increases.

The graphs  must  have a title,  labeled axis, and  labeled curves.  Finally,  briefly discuss the results  of each method.

*Guidelines on  feature split: In the Boston dataset, there  are in total  13 features, and only the fourth  feature  (column)  has binary  values whereas all others have continu- ous values (non-categorical). During feature  selection, we will use binary split for each feature  with  continuous  values.   To  find the  best  split,  enumerate the  [10, 20, ..., 90]th percentiles  for each  continuous  feature  for data  points  belonging  to  the  current tree- node.   The  percentiles  will be treated as possible  split  points  for each  feature.    The best-split maximizes the information  gain for this feature.  For example,  if your feature set has 13 features to choose from, then for each feature with continuous  values, evaluate all possible split-values  (as given by the  9 percentiles),  and  choose the  best  split  point for each feature  with its information  gain recorded (within feature). Next, choose the best feature  from your feature  set that overall maximizes the information  gain (across features).  Note  that the  split-values  based  on percentiles  cannot  be predetermined. They need to be computed  on-the-fly using the data  points you have at the current tree node.

(ii)  Code: For part  (a), you will have to submit  code for myABoost(filename,B, k) (main file).   This  main  file has  input:  a  filename  (including  extension  and  absolute  path) containing  the  dataset, and  a vector  B  for the number  of base  classifiers,  e.g.,  B  = [5, 10, 15, . . . , 50], and  k as the  number  of folds in k-fold cross validation  and  output: print to the terminal  (stdout) the training  and test  set error  rates  and number  of base classifiers for each fold of the  k-fold cross-validation, along with  the  average  error  rate

and standard deviation  for training  and test sets.  The function  must  take the inputs  in this order and display the output via the terminal.

For part  (b), you will have to submit  code for myRForest(filename,M, k) (main  file). This main file has input:  a filename (including extension and absolute  path) containing the  dataset, a vector  M  of the  size of the  random  feature  set,  e.g., M  = [1, 2, . . . , 13], and k as the number of folds in k-fold cross validation and output:  print to the terminal (stdout) the  training  and  test  set  error  rates  and  feature  set  size for each fold of the k-fold cross-validation, along  with  the  average  error  rate  and  standard deviation  for training  and test  sets.  The function  must  take  the inputs  in this order and display the output via the terminal.

Although  in your report  you should  provide  the  results  for specific value of vectors  B and M and number  k, your code should be general and accept any input  arguments and produce  the required  results  without  errors.

For each part,  you can submit  additional files/functions (as needed)  which will be used by the main file. Put  comments  in your code so that one can follow the key parts  and steps in your code.

 

Additional instructions: Code can only be written  in Python or Matlab;  no other  programming languages  will be  accepted.    One  should  be  able  to  execute  all  programs  from  matlab/python command  prompt  or  the  code can  be  a  jupyter  notebook.    Your  code must  run  on a  CSE  lab machine  (e.g.,  csel-kh1260-01.cselabs.umn.edu).   Please  specify instructions on how to  run  your program  in the  README  file. Information on the  size of the  datasets, including  number  of data points  and  dimensionality of features,  as well as number  of classes can be readily  extracted from the dataset text  file.

Each function must take the inputs  in the order specified in the problem and display the textual output via the  terminal.  The  input  data  file for your  function  must  be exactly  the  same as the original downloaded  file, which will be used as input  for grading.

For each part,  you can submit  additional files/functions (as needed)  which will be used by the main  file.  In your  code,  you cannot  use machine  learning  libraries  such  as those  available  from scikit-learn  for learning the models or for cross-validation. However, you may use libraries for basic matrix  computations. Put  comments  in your code so that one can follow the  key parts  and steps in your code.

 

 

Extra Credit problem:

 

EC1  (20  points) The problem considers the convolution  operation  in a convolutional  neural  net- work as a matrix  operation.  Let the  input  X  ∈ Rn×m  be a n × m real valued  matrix.   Let K  ∈ R3×3  be a kernel applied  to the  input  X  without  any zero-padding  or other  extension, so that the output Z = (X ∗ K ) ∈ Rn−2×m−2 is a (n − 2) × (m − 2) matrix.

 

(a)  (10 points)  Using pseudo-code,  clearly  describe  the  convolution  operation  which takes any input  matrix  X  and kernel matrix  K  as input,  and outputs matrix  Z .

(b)  (10 points)  Let vec(X ) ∈ Rnm be a vectorized  version of matrix  X  constructed colum- nwise, i.e., vec(X )[1 : n] = X [1 : n, 1], vec(X )[n + 1 : 2n] = X [1 : n, 2], and  so on.  Let A ∈  R(n−2)(m−2)×(nm)  matrix  such  that vec(Z ) = Avec(X ).   Specify the  matrix  A in

terms  of the kernel matrix  K , i.e., which entries  of A will correspond  to which entries  of

K , and which entries  are 0.

 

 

Instructions

 

Follow the rules strictly. If we  cannot run your code, you  will  not get any credit.

Things to submit

 

1.  hw3.pdf:  A document which contains  the solutions  to Problems  1, 2, 3, and 4, including the summary  of methods  and results.

 

2.  myABoost and myRForest: Code for Problem  4.

 

3.  README.txt:  README  file that contains  your  name,  student ID, email,  instructions on how to compile (if necessary)  and run your code, any assumptions you are making,  and any other  necessary details.

 

4.  Any other  files, except the data,  which are necessary for your program.