Hard-SVM
对于数据集$S = (x_1, y_1), \cdots , (x_m, y_m)$其中$x_i \in R^d$, $y_i \in {\pm 1}$. 假定该数据集可以被一个超平面(halfspace)区分，我们可得： $$ \forall i \in [m], y_i(<w, x_i> + b) > 0. $$ 我们想要的超平面是能最大化间隔，所以： $$ \arg\max_{(w,b):||w||=1} \min_{i \in [m]} |<w, x_i> + b| \ \ s.t. \ \ \forall i, y_i(<w, x_i> + b) > 0. $$ 等价于： $$ \arg\max_{(w,b):||w||= 1} \min_{i \in [m]} y_i (<w, x_i> + b). $$
等价于： $$ (w_0, b_0) = \arg\min_{(w,b)} ||w||^2. \ \ s.t. \ \ \forall i, y_i(<w, x_i> + b) \geq 1. $$
Soft-SVM
假定数据不能被一个超平面正确区分 $$ \min_{w,b, \xi} (\lambda ||w||^2 + \frac{1}{m}\sum_{i=1}^m \xi_i) \ \ s.t. \ \ \forall i, y_i(<w, x_i> + b) \geq 1 - \xi_i \ and \ \xi_i \geq 0. $$
SVM-SGD
目标函数为： $$ obj(w) = \frac{1}{2} \lambda w^2 + \frac{1}{n} \sum_{i=1}^n L(x_i, w). $$ 利用SGD进行w的更新 $$ w = (1 - \lambda \eta_t)w - \eta_t \frac{dL}{dw(x, w)} $$ 其中$\eta_t$为学习率$\lambda$的衰退系数 $$ \eta_t = \eta_0 (1 + a\eta_0 t)^{-c} $$ 其中$\eta_0,a$为常数.此处$\eta_t$取值为 $$ \eta_t = \frac{\eta_0}{1 + \lambda \eta_0 t}. $$ 我们假定： $$ w = \frac{W}{\epsilon} $$ 所以可得SGD进行w的更新为： $$ \epsilon = \frac{\epsilon}{1 - \lambda \eta_t} $$ $$ W = W - \eta_t \epsilon \frac{dL}{dw(x, w)}. $$
采用ASGD(averaged SGD)的方法$\bar{w} = \frac{1}{t}\sum_{i=1}^t w_t$进行更新， $$ w = (1 - \lambda\eta_t)w - \eta_t \frac{dL}{dw(x, w)} $$ $$ a = a + \mu_t(w - a). $$ 此处衰退系数定义为: $$ \eta_t = \frac{\eta_0}{(1 + \lambda \eta_0 t)^{0.75}} $$ 并且在一定的时间我们就进行average操作，使用$\mu_t$来实现： $$ \mu_t = \frac{1}{\max(1, t - t_0)}. $$ 我们定义： $$ w = \frac{W}{\epsilon} $$ $$ a = \frac{A + \alpha W}{\beta} $$ 所以可得ASGD进行w的更新为： $$ \epsilon = \frac{\epsilon}{1 - \eta_t * \lambda} $$ $$ W = W - \eta_t \alpha \epsilon \frac{dL}{dw(x, w)} $$ $$ \beta = \frac{\beta}{1 - \mu_t} $$ $$ \alpha = \alpha + \frac{\mu_t \beta}{\epsilon}. $$