Liner Classifier
给定 \(n\) 组 \((x_i,y_i)\)，其中 \(x_i\in \mathbb R^d,y_i\in \{-1,1\}\)，判定是否存在 \((w,b),w\in \mathbb R^d,b\in \mathbb R\) 满足 \(\mathrm{sgn}(w^tx_i)=y_i,\forall i\)。
解：等价于如下最优化问题的解非负：
\[\begin{aligned} \text{max} & \quad & t\\ \text{s.t.} & \quad & y_i(w^tx_i+b)\ge t\\ &\quad & \| w \|_2=1 \end{aligned} \]也等价于如下最优化问题有解：
\[\begin{aligned} \text{min} & \quad & \frac 12\|w\|_2^2\\ \text{s.t.} & \quad & y_i(w^tx_i+b)\ge 1\\ \end{aligned} \]拉格朗日函数为：
\[L(w,b;\lambda)=\frac 12\|w\|_2^2+\sum_{i=1}^n\lambda_i(1-y_i(w^tx_i+b)) \]于是
\[\frac{\partial L(w,b;\lambda)}{\partial w}{\huge |}_{w^*,b^*}=0\Rightarrow w^*=\sum_{i=1}^n \lambda_iy_ix_i\\ \frac{\partial L(w,b;\lambda)}{\partial b}{\huge |}_{w^*,b^*}=0\Rightarrow \sum_{i=1}^n \lambda_iy_i=0 \]这意味着 \(w^*\) 是 \(y_ix_i\) 的线性组合。
\(L\) 可以写成：
\[\begin{aligned} L(\varphi(\lambda),\lambda)&=\frac 12\|\sum_{i=1}^n\lambda_iy_ix_i\|^2+\sum_{i=1}^n\lambda_i(1-y_i((\sum_{j=1}^n\lambda_jy_jx_j^\top)x_i+b))\\ &=\frac 12 \sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_jx_i^\top x_j+\sum_{i=1}^n\lambda_i-b\sum_{i=1}^n\lambda_iy_i-\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_jx_i^\top x_j\\ &=\sum_{i=1}^n\lambda_i-\frac 12 \sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_jx_i^\top x_j \end{aligned} \]因此，对偶问题为：
\[\begin{aligned} \text{max} & \quad & \sum_{i=1}^n\lambda_i-\frac 12 \sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_jx_i^\top x_j\\ \text{s.t.} & \quad & \lambda_i\ge 0\\ & \quad & \sum_{i=1}^n\lambda_iy_i=0 \end{aligned} \] 标签：iy,frac,sum,学习,quad,机器,aligned,lambda From： https://www.cnblogs.com/xay5421/p/18619654