SHUNMIAN

1 支持向量机
2 作业
3 总结
4 参考资料

1 支持向量机

1.1 支持向量机介绍

机器学习的分类算法有以下主要三种。

Logistic Regression (逻辑回归)；
Netural Network (神经网络)：用于减少Logistic Regression带来多项式Feature个数的复杂度的问题。例如2次项复杂度是$O(\frac {n^2} 2)$，3次项的复杂度是$O({n^3})$；
Support Vector Machine (支持向量机)：相比于Logistic Regression和Netural Network，Support Vector Machine有时候可以提供更清晰和强大的方式来学习复杂的非线性函数。

SVM：are supervised learning models with associated learning algorithms that analyze data used for classification and regression analysis.

SVM

1.1.1 SVM成本函数

对于Logistic Regression，它的成本函数是：

$\\ J(\theta) = \frac 1 m \sum_{i=1}^m [-y^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))] +\frac \lambda {2m} \sum_{j=1}^n\theta_j^2 \\$

我们用另一种cost function：

Logistic Regression_Cost Function

$\begin{align} \\ J(\theta) &= \frac 1 m \sum_{i=1}^m [-y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})] +\frac \lambda {2m} \sum_{j=1}^n\theta_j^2 \\ &= \frac C m \sum_{i=1}^m [-y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})] +\frac 1 {2} \sum_{j=1}^n\theta_j^2 \text {, where $C = \frac 1 {\lambda}$} \end{align}$

1.1.2 SVM Margin

SVM直观理解：增大Margin。SVM别名是Large Margin Classifier。

Large Margin Classifier

1.1.3 SVM 成本函数最小值和Margin关系

为获得$J_{\theta}$最小值。

$\begin{align} \\ _{min}J(\theta) &= _{min}(\frac C m \sum_{i=1}^m [-y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]) +_{min}(\frac 1 {2} \sum_{j=1}^n\theta_j^2) \text {, where $C = \frac 1 {\lambda}$} \\ &=\begin{cases} 0, &\text{if $\theta^Tx^{(i)} ≥ 1$ so $y = 1$} \\ 0,&\text{if $\theta^Tx^{(i)} ≤ -1$ so $y = 0$} \\ \end{cases} + _{min}(\frac 1 {2} ||\theta||^2) \\ &\text {where $\theta^Tx^{(i)}$ is the inner product of $\theta$ and $x^{(i)}$, } \\ &\text {$\theta$ is the vector perpendicular to the decision boundary } \end{align}$

SVM costfunction vs. margin