MATH-UA 253/MA-UY 3204 - Fall 2022 - Homework #9

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH-UA 253/MA-UY 3204 - Fall 2022 - Homework #9 - BONUS

NOTE: This homework is for bonus credit equal to one homework.  The homework is worth 25% of the grade, so this homework is worth 3.125% in bonus points beyond the original 25%.

Problem  1.    Read about support vector machines (SVMs) online. Wikipedia is a decent resource. There are many other references. See the scikit-learn documentation, for instance:

https://scikit-learn.org/stable/modules/svm.html

The dual formulation of SVM is a quadratic program with linear inequality constraints.  Write up a short explanation of SVM, along with a derivation of SVM from “first principles”. Key things to include: derive the primal formulation of SVM with hinge loss, derive the dual formulation, and then explain the formulation of the dual problem using the kernel trick.  (You will have to do some research and reading to understand what all this means!) Please keep your explanation fairly short—try not to write more than one page.

Problem 2.    Read Section 16.6 of Nocedal and Wright (“Interior-Point Methods”). This section explains how to use interior-point methods to solve quadratic programs with linear inequality constraints. Program an interior-point method for solving the dual formulation of the SVM with kernel trick. E.g., see Algorithm 16.4. It is HIGHLY RECOMMENDED that you read the chapter in its entirety before attempting to program Algorithm 16.4.

Problem 3.    Find an appropriate dataset for classification online. Here is one possible source: https://archive.ics.uci.edu/ml/datasets.php

Use this dataset to test your implementation of SVM out.   For comparison, you can compare with an implementation of SVM available in the Python ecosystem (scikit-learn has several).