CSCI 540
Machine Learning, Spring 2020
Final Project
SVM Optimization Algorithms

Due 5/8/2020@8:00 pm via Blackboard
Presentation: 5/4/2019@6:00pm
Goal The goal of this project is for you to gain experience with the optimization portion/internals of a Support Vector Classification problem.
Background Review all material on Support Vector Machines to refresh your memory. Review slides for Lectures #14 and #15 on Support Vector Machines and Kernels respectively. Also available is the companion web-site for the book available at California Institute of Technology (CalTech): http://work.caltech.edu/lectures.html. Another excellent source is MIT Open Courseware’s module on SVMs: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-16-learning-support-vector-machines
Assignment For this assignment, you will derive the SVM problem employing kernels and soft margins (slack variables) and implement an experiment that employs SVMs in a classification problem. You will be formulating the SVM problem yourself, setting up the optimization problem, then running an optimization method to return a result employed in your solution. The optimization methods you will employ is quadratic programming. Remember, these are solution methods that solve the “Dual Formulation” in order to find values for = (!, … , ") associated with in-sample points ⃗!, … , ⃗" . You will compare your results to Weka’s version of SVM that employs the Sequential Minimal Optimization (SMO) algorithm. 1. Review material on SVM formulation with kernels and soft margins 2. Derive an expression for the primal and dual formulation
3. Write code that computes the appropriate coefficient matrix for running MATLAB’s Quadratic programming solver. 4. Install and run the Weka Data Mining toolkit (https://www.cs.waikato.ac.nz/ml/weka/ ). This will require Java. 5. For a data set use the similar-digit data set and different-digit data set from the MNIST data. To construct a similar-digit data set, you will select MNIST image information for two digits that are similar, for example the “1” digit and the “7” digit. To construct a different-digit data set, you will select MNIST image information for two digits that are different, for example the “9” digit and the “7” digit. This can be constructed from the MNIST gray level image data-set for 16x16 digit images. The training/test sets can be found on the textbook’s companion site:
• Companion site: http://www.amlbook.com
• Data Info: http://amlbook.com/data/zip/zip.info
• Training Set: http://amlbook.com/data/zip/zip.train
• Test Set: http://amlbook.com/data/zip/zip.test For the training/test sets, the first column is the digit description (0-9) and the next 256 columns are the pixel intensities. You will construct the aforementioned similar-digit and different-digit data sets by selecting the appropriate rows from the training set and test set. You will use MATLAB’s dlmread(.) or import into Excel and save as a CSV file for processing in MATLAB. 6. Solve the SVM problem using a kernel of your choosing (polynomial, radial basis, etc.) solving the dual formulation problem using quadratic programming Note: MATLAB has toolboxes providing functions for quadratic programming. MATLAB’s quadratic programming solver is invoked by API call quadprog(.). 7. Compare the performance of your Quadratic Programming version of SVM with Weka’s SMO version of SVM. 8. Report your results and discuss differences. This will require you to investigate what SMO and quadratic programming are doing at a high level. 9. Prepare slides consisting of
• Derivation of SVM with soft margins
• Results of SMO version of SVM with selected kernel
• Results of your own MATLAB quadprog version of SVM with selected kernel
• Discussion of the differences and your observations

Submitting your assignment 1. Bring your power point to the final exam period on Monday May 4th. 2. Submit your derivation of primal/dual problem, MATLAB code, and PowerPoint slides on Blackboard as a single ZIP archive by Friday May 3rd , 2019 at 8:00pm.