Differences

This shows you the differences between two versions of the page.

--- assignments:assignment3 [2015/10/02 10:04]
asa
+++ assignments:assignment3 [2016/09/15 14:45]
asa
@@ Line 1: / Line 1: @@
-========= Assignment 3: Support Vector Machines ============
+~~NOTOC~~
-Due:  October 20th at 6pm
+====== Assignment 3 ======
-===== Part 1:  SVM with no bias term =====
+**Due:** 10/2 at 11pm.
-Formulate a soft-margin SVM without the bias term, i.e. one where the discriminant function is equal to $\mathbf{w}^{T} \mathbf{x}$.
+===== Preliminaries =====
-Derive the saddle point conditions, KKT conditions and the dual.
-Compare it to the standard SVM formulation.
-As we discussed in class, SMO-type algorithms for the dual optimize the smallest number of variables at a time, which is two variables.
-Is this still the case for the formulation you have derived?
-Hint:  consider the difference in the constraints.
-===== Part 2:  Soft-margin SVM for separable data =====
+In this assignment you will explore ridge regression applied to the task of predicting wine quality.
+You will use the [[http://archive.ics.uci.edu/ml/datasets/Wine+Quality | wine quality]] dataset from the UCI machine learning repository, and compare accuracy obtained using ridge regression to the results from a [[http://www.sciencedirect.com/science/article/pii/S0167923609001377# | recent publication]] (if you have trouble accessing that version of the paper, here's a link to a [[http://www3.dsi.uminho.pt/pcortez/wine5.pdf| preprint]].
+The wine data is composed of two datasets - one for white wines, and one for reds.  In this assignment perform all your analyses on just the red wine data.
-Consider training a soft-margin SVM
+The features for the wine dataset are not standardized, so make sure you do this, especially since we are going to consider the magnitude of the weight vector (recall that standardization entails subtracting the mean and then dividing by the standard deviation for each feature; you can use the [[http://docs.scipy.org/doc/numpy/reference/routines.statistics.html | Numpy statistics module]] to perform the required calculations).
-with the soft margin constant $C$ set to some positive constant. Suppose the training data is linearly separable.
+==== Part 1 ====
-Since increasing the $\xi_i$ can only increase the objective of the primal problem (which
-we are trying to minimize), at the optimal solution to the primal problem, all the
-training examples will have $\xi_i$ equal
-to zero. True or false?  Explain!
-Given a linearly separable dataset, is it necessarily better to use a
-a hard margin SVM over a soft-margin SVM?  Explain!
-===== Part 3:  Using SVMs =====
+Implement ridge regression keeping the same API you used in implementing the classifiers in assignment 2, and functions for computing the following measures of error:
-The data for this question comes from a database called SCOP (structural
+  * The Root Mean Square Error (RMSE).
-classification of proteins), which classifies proteins into classes
+  * The Maximum Absolute Deviation (MAD).
-according to their structure (download it from {{assignments:scop_motif.data|here}}).
-The data is a two-class classification
-problem
-of distinguishing a particular class of proteins from a selection of
-examples sampled from the rest of the SCOP database
-using features derived from their sequence (note that a protein is an arbitrary length sequence over the alphabet of the 20 amino acids).
-I chose to represent the proteins in
-terms of their motif composition.  A sequence motif is a
-pattern of amino acids that is conserved in evolution.
-Motifs are usually associated with regions of the protein that are
-important for its function, and are therefore useful in differentiating between classes of proteins.
-A given protein will typically contain only a handful of motifs, and
-so the data is very sparse.
-Therefore, only the non-zero elements of the data are represented.
-Each line in the file describes a single example and has the format:
-<code>
-d1scta_,a.1.1.2 31417:1.0 32645:1.0 39208:1.0 42164:1.0 ....
-</code>
-The first column is the ID of the protein, the second is the class it belongs to (the values for the class variable are ''a.1.1.2'', which is the given class of proteins, and ''rest'' which is the negative class representing the rest of the database), and the rest of the elements are pairs of the form ''feature_id:value'' - an id of a feature and the value associated with it.
-This is an extension of the format used by LibSVM, that scikit-learn can read.
-See a discussion [[http://scikit-learn.org/stable/datasets/#datasets-in-svmlight-libsvm-format | here]].
-We note that the data is very high dimensional since
+For a hypothesis $h$, they are defined as follows:
-the number of conserved patterns in the space of all proteins is
-large.
-The data was constructed as part of the following analysis of detecting distant relationships between proteins:
-  * A. Ben-Hur and D. Brutlag. [[http://bioinformatics.oxfordjournals.org/content/19/suppl_1/i26.abstract | Remote homology detection: a motif based approach]]. In: Proceedings, eleventh international conference on intelligent systems for molecular biology. Bioinformatics 19(Suppl. 1): i26-i33, 2003.
+$$RMSE(h) = \sqrt{\frac{1}{N}\sum_{i=1}^N (y_i - h(\mathbf{x}_i))^2}$$
-In this part of the assignment we will explore the dependence of classifier accuracy on
+and
-the kernel, kernel parameters, kernel normalization, and the SVM soft-margin parameter.
-In your implementation you can use the scikit-learn [[http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html | svm]] class.
-In this question we will consider both the Gaussian and polynomial kernels:
+$$MAD(h) = \frac{1}{N}\sum_{i=1}^N |y_i - h(\mathbf{x}_i)|.$$
-$$
-K_{gauss}(\mathbf{x}, \mathbf{x'}) = \exp(-\gamma || \mathbf{x} - \mathbf{x}' ||^2)
-$$
-$$
-K_{poly}(\mathbf{x}, \mathbf{x'}) = (\mathbf{x}^T \mathbf{x}' + 1) ^{p}
-$$
-Plot the accuracy of the SVM, measured using the area under the ROC curve
+With the code you just implemented, your next task is to explore the dependence of error on the value of the regularization parameter, $\lambda$.
-as a function of both the soft-margin parameter of the SVM, and the free parameter
+In what follows set aside 30% of the data as a test-set, and compute the in-sample error, and the test-set error as a function of the parameter $\lambda$ on the red wine data.  Choose the values of $\lambda$ on a logarithmic scale with values 0.01, 0.1, 1, 10, 100, 1000 and plot the RMSE only.
-of the kernel function.
+Repeat the same experiment where instead of using all the training data, choose 20 random training examples.
-Accuracy should be measured in five-fold cross-validation.
-Show a couple of representative cross sections of this plot for a given value
-of the soft margin parameter, and for a given value of the kernel parameter.
-Comment on the results.  When exploring the values of a continuous
-classifier/kernel parameter it is
-useful to use values that are distributed on an exponential grid,
-i.e. something like 0.01, 0.1, 1, 10, 100 (note that the degree of the
-polynomial kernel is not such a parameter).
-Next, we will compare the accuracy of an SVM with a Gaussian kernel on the raw data with accuracy obtained when the data is normalized to be unit vectors (the values of the features of each example are divided by its norm).
+Now answer the following:
-This is different than standardization which operates at the level of individual features.  Normalizing to unit vectors is more appropriate for this dataset as it is sparse, i.e. most of the features are zero.
-Perform your comparison by comparing the accuracy measured by the area under the ROC curve in five-fold cross validation.
-The optimal values of kernel parameters should be measured by cross-validation, where the optimal SVM/kernel parameters are chosen using grid search on the training set of each fold.
-Use the scikit-learn [[http://scikit-learn.org/stable/tutorial/statistical_inference/model_selection.html
- | grid-search]] class for model selection.
+  * What is the optimal value of $\lambda$?
+  * What observations can you make on the basis of these plots?  (The concepts of overfitting/underfitting should be addressed in your answer).
+  * Finally, compare the results that you are getting with the published results in the paper linked above.  In particular, is the performance you have obtained is comparable to that observed in the paper?
-Finally, visualize the kernel matrix associated with the dataset.
+==== Part 2 ====
-Explain the structure that you are seeing in the plot (it is more
-interesting when the data is normalized).
+Regression Error Characteristic (REC) curves are an interesting way of visualizing regression error as described
+in the following [[http://machinelearning.wustl.edu/mlpapers/paper_files/icml2003_BiB03.pdf|paper]].
+Write a function that plots the REC curve of a regression method, and plot the REC curve of the best regressor you found in Part 1 of the assignment.
+What can you learn from this curve that you cannot learn from an error measure such as RMSE or MAD?
+==== Part 3 ====
+As we discussed in class, the magnitude of the weight vector can be interpreted as a measure of feature importance.
+Train a ridge regression classifier on a subset of the dataset that you reserved for training.
+We will explore the relationship between the magnitude of weight vector components and their relevance to the classification task in several ways.
+Each feature is associated with a component of the weight vector.  It can also be associated with the correlation of that feature with the vector of labels.
+Create a scatter plot of the weight vector component against the [[https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient | Pearson correlation coefficient]] of a feature against the labels (again, you can use the [[http://docs.scipy.org/doc/numpy/reference/routines.statistics.html | Numpy statistics module]] to compute it).
+What can you conclude from this plot?
+The paper ranks features according to their importance using a different approach.  Compare your results with what they obtain.
+Next, perform the following experiment:
+Incrementally remove the feature with the lowest absolute value of the weight vector and retrain the ridge regression classifier.
+Plot RMSE as a function of the number of features that remain on the test set which you have set aside.
 ===== Submission =====
@@ Line 99: / Line 66: @@
 ===== Grading =====
-A few general guidelines for this and future assignments in the course:
+Here is what the grade sheet will look like for this assignment.  A few general guidelines for this and future assignments in the course:
   * Always provide a description of the method you used to produce a given result in sufficient detail such that the reader can reproduce your results on the basis of the description (UNLESS the method has been provided in class or is there in the book).  Your code needs to be provided in sufficient detail so we can make sure that your implementation is correct.  The saying that "the devil is in the details" holds true for machine learning, and is sometimes the makes the difference between correct and incorrect results.  If your code is more than a few lines, you can include it as an appendix to your report, or submit it as a separate file.  Make sure your code is readable!
@@ Line 109: / Line 76: @@
 Grading sheet for assignment 2
-Part 1:  45 points.
+Part 1:  50 points.
-(10 points):  Primal SVM formulation is correct
+(20 points):  Plots of MAD and RMSE as a function of lambda are generated correctly.
-(10 points):  Lagrangian found correctly
+(20 points):  REC curves are generated correctly
-(10 points):  Derivation of saddle point equations
+( 5 points):  discussion of REC curves
-(10 points):  Derivation of the dual
+( 5 points):  Discussion of the MAD and RMSE plots and comparison of results to the published ones.
-( 5 points):  Discussion of the implication of the form of the dual for SMO-like algorithms
-Part 2:  15 points.
+Part 2:  40 points.
+(30 points):  Weight vector analysis
-Part 3:  40 points.
+(10 points):  Comparison to the published results
-(20 points):  Accuracy as a function of parameters and discussion of the results
-(15 points):  Comparison of normalized and non-normalized kernels and correct model selection
-( 5 points):  Visualization of the kernel matrix and observations made about it
 Report structure, grammar and spelling:  10 points
@@ Line 128: / Line 91: @@
               Grammar, spelling, and punctuation.
 </code>

CS545 fall 2016

User Tools

Site Tools

Differences

Page Tools