Description
Problem 1
Given the a dataset with covariates Xt
i =< xi,1, . . . , xi,p >, and corresponding responses yi (i = 1, . . . , N), consider the standardization transformation:
x˜i,j =
xi,j
q
− x¯.,j
σˆ
2
.,j
.
x¯.,j and ˆσ
2
.,j represent the sample mean and variance across feature j, respectively.
Part a
Is CART invariant to using ˜x instead of x? In other words, are the answers equivalent?
Explain why or why not.
Yes, CART is invariant to using ˜x instead of x. When the covariates are standardized, the splitting threshold t1, t2, t3, … will be rescaled (standardized) automatically
by the algorithm of CART in order to minimize the in-group sum of squares, according to what dimension that ti belongs to. As a result, the classification label for
each standardized data point is the same as the classification label for the data point
before the standardization. In other words, the classification results are equivalent
before and after the standardization of the covariates when using CART.
Part b
Is LASSO regression invariant to using ˜x instead of x? In other words, are the answers
equivalent? Explain why or why not.
No, LASSO regression is not invariant to using ˜x instead of x. If we set D to be
the transformation matrix with which we have
X˜ = XD.
1
Plug the above expression into the formula for LASSO regression, we have
min
β
||Y − XDβ||2 + λ||β||1 = min
α=Dβ
||Y − Xα||2 + λ||D
−1α||1
This means, the LASSO after standardization is equivalent to the LASSO of the
original covariate with a modified constraint ||D−1α||1 < s. The shape of this new
constraint in the parameter space will be different from the original one (for the
covariates without standardization), which will result in a different set of parameter
estimations. Thus, the LASSO won’t give the equivalent answer before and after the
standardization of the covariates.
Problem 2
Prove that the LASSO formulation
min
β
||Y − Xβ||2 subject to X
k
|βk| < s, (1)
where || · ||2 represents the Euclidean norm, is equivalent to the formulation:
min
β
||Y − Xβc
||2 + λ
X
p
i=1
|β
c
i
|. (2)
Show the correspondence between the β
c
k
’s and the original βk’s. Hint: think about
Lagrange multipliers.
Proof: Using the Lagrange multiplier, the constraint formulation of the LASSO
can be expressed as follows. First, we add the term with Lagrange multiplier to the
original sum of square of errors:
L = ||Y − Xβ||2 + η(||β||1 − s)
where L is the quantity we want to minimize. Then we obtain the LASSO estimator
by
min
β
L = min
β
[||Y − Xβ||2 + η(||β||1 − s)]
Since s is a constant, the above minimization process can be simplified as
min
β
L = min
β
[||Y − Xβ||2 + η||β||1] = min
β
[||Y − Xβ||2 + η
X
p
i=1
|βi
|] (3)
for finding the LASSO estimators. Compare Eq.(3) with Eq.(2), it is not hard the
constraint formulation of LASSO (Eq.(3) is derived from the constraint formulation
shown in (1)) is equivalent to the Lagrange formulation of LASSO (shown in (2)
directly). Thus, the β
c
k
’s and the original βk’s should be the same.
2
Part 3
Load the spam dataset.
Part a
Build a Classification Tree with at least 100 terminal nodes. Using 10-fold cross
validation, report the overall classification error rate.
Here I set the number of terminal nodes to be 110, the overall classification error
rate is 0.03478. See below for the cross validation plot, and the decision tree. See
Appendix for code.
Figure 1: Cross validation plot for finding a classification tree with size larger than
100.
Figure 2: A classification tree with size of 110.
3
Part b
Now determine a simpler tree (i.e. by pruning the tree). Again, using a 10-fold cross
validation scheme, report the overall classification error rate.
Here I pruned the tree and let the final number of terminal nodes to be 20. The
overall classification error rate is 0.07826 (, which is larger than the one in Part a due
to simplification of the tree). See below for the cross validation plot, and the decision
tree. See Appendix for code.
Figure 3: Cross validation plot for finding a classification tree with size smaller than
100.
Figure 4: A classification tree with size of 20.
4
Part c
Attempt to find an optimal tree under a 10-fold cross validation scheme. That is,
try to find a tree that minimizes the cross validation error. While this is nearly an
impossible task, see how close you can come. Describe your method and your overall
error rate.
In the plot of cross validation, I found the deviance (cross validation error) stops
dropping when the size of the tree reaches 13. Then I pruned the tree with size=13.
The pruned tree has overall error rate as 0.08261, slightly larger than that of Part b.
See below the cross validation plot and the decision tree. See Appendix for code.
Figure 5: Cross validation plot for finding an optimized classification tree.
Figure 6: The optimized classification tree with size of 13.
5
Part 4
Using the spam dataset, perform a logistic regression, and report the 10-fold cross
validation error.
See Appendix for the implementation and detailed result for the logistic regression.
The logistic regression shows that the significant predictor variables include V2, V5,
V6, V7, V8, V9, V16, V17, V19, V21, V23, V24, V25, V26, V27, V28, V33, V35,
V36, V39, V42, V44, V45, V46, V48, V49, V52, V53, V54, V56, V67.
The 10-fold cross validation error is found to be 0.05848635.
Part 5
Repeat the previous exercise using LASSO logistic regression, using the parameter λ
that minimizes the deviance measure.
Figure 7: The cross validation plot with log(λ).
The parameter λ that minimizes the deviance measure is found to be 0.0004034505.
See Appendix for the implementation of LASSO logistic regression with cross validation.
6