Linear Discriminants 线性判别式

线性判别式公式
$$f(\mathbf{x};\mathbf{w})=w_1{x}^{(1)}+w_2{x}^{(2)}+\cdots +w_d{x}^{(d)}+b=0$$

两种表示方法


$w^{\prime }$是更加数学化的公式

我们所要做的，就是求$w$和$b$，获得线性判别式。

Loss Function 损失函数

misclassification 误分类

误分类是一种错误
如果一个训练样本的标签为𝑦 = +1，那么它的判别函数得分$f(x)$应该 > 0
如果一个训练样本的标签为𝑦 = −1，那么它的判别函数得分$f(x)$应该 < 0
因此，当出现 $yf(x)<0$，说明分类错误。

0-1 Loss/Error function 0-1损失函数

$$l(f(x),y)=\{\begin{array}{ll}0,& yf(x)>0\\ 1,& yf(x)\le 0\end{array}$$

The whole error整体误差：用于判断全部examples
$$\sum _{i=1}^{N}l(f(x_i),y_i)$$

0-1损失函数有两个问题：

• 显而易见，这是一个阶跃函数，在0点具有不连续性，没有很好的定义可以求导；
• 它不是凸的，这意味着当我们试图用梯度下降算法来最小化整体损失，它是无法给出这个特定损失函数的最优解

所以我们建议做的或者最初的创造者，或者现在所谓的感知器所做的是，他们想出了这个零一损失函数的凸近似值——the hinge loss 铰链损失函数

Hinge Loss Function 铰链损失函数

Hinge Loss Function is a convex over-approximation of the 0-1 loss. 铰链损失函数是 0-1 损失函数的凸过度近似。

$$l(f(x),y)=\{\begin{array}{ll}0,& yf(x)>1\\ 1-yf(x),& yf(x)\le 1\end{array}=\{\begin{array}{ll}0,& 1-yf(x)<0\\ 1-yf(x),& 1-yf(x)\ge 0\end{array}$$

OR
$$l(f(x),y)=\max (0,1-yf(x))$$

简单的理解

$$\mathbf{l}(\mathbf{z})=\{\begin{array}{ll}0,& z>1\\ 1-z,& z\le 1\end{array}$$
我们所做的就是构建0-1损失函数的凸近似函数，它是凸的，我们也可以对它进行微分（求导）。

Optimization 优化

min⁡wL(X,Y;w)=∑i=1Nmax⁡{0,1−yif(xi;w)}\min_{\mathbf{w}} \; L(\mathbf{X}, \mathbf{Y}; \mathbf{w}) = \sum_{i=1}^{N} \max\{0,\, 1 - y_i f(x_i; \mathbf{w})\} wmin​L(X,Y;w)=i=1∑N​max{0,1−yi​f(xi​;w)}

在这个具体实例中，将4个节点代入模型公式 $f(\mathbf{x};\mathbf{w})=w_1{x}^{(1)}+w_2{x}^{(2)}+b=0$。我们已知道他们的标签 $y_i$，由此得到每个节点的损失函数值 max⁡{0,1−yif(xi;w)}\max\{0,\, 1 - y_i f(x_i;\mathbf{w})\}max{0,1−yi​f(xi​;w)}。整个数据集，总体损失是 ∑i=14max⁡{0,1−yif(xi;w)}\sum_{i=1}^{4} \max\{0,\, 1 - y_i f(x_i; \mathbf{w})\}∑i=14​max{0,1−yi​f(xi​;w)}。
由此，我们采用梯度下降算法来求最小损失函数，这就是我们面对的优化问题。

所有的机器学习都可以表示为优化问题，一旦我们有了机器学习问题的表示方式（模型），我们表示了特征features，我们表示了判别式disccriminant，并且量化定义了什么是误差。我们开始使用0-1损失函数，但因为它不可微，使用这个数据会导致复杂的后续处理过程。因此我们简化了它，或者说以此为目的构建了一个复杂的铰链损失过度近似。然后下一步，我们将以优化问题的形式进行问题训练。这是整个机器学习和数据挖掘的一致主题。

现在我们将使用梯度下降算法进行优化。使用这个算法所求的便是这个模型，参数为向量$w$。

这里是有点难以理解的，这个图的损失函数，分界点在$x=1$，不是0点。虽然实际上 $yf(x)=[0,1]$是正确分类了，本应该没有损失值的，但这是近似损失函数，不是完全符合实际的，所以我们会计算它的损失值。所以当 $yf(x)<1$ 时候，我们会假定视为这是分类错误了。

算法

已知： 训练样本：{(xi,yi)∣i=1…N},yi∈{−1,+1}\{(x_i, y_i) \mid i = 1 \dots N\}, \quad y_i \in \{-1, +1\}{(xi​,yi​)∣i=1…N},yi​∈{−1,+1}
随机初始化 $w^{(0)}$
循环直到收敛（Until Convergence）

• 对于 $i=1\dots N$：
  • 选择样本 $x_i$，其标签为 $y_i$
  • 计算
    $$f(x_i)={\mathbf{w}}^{(k)T}\mathbf{x}+b$$
  • 如果 $y_{i}f(x_i)<1$，则使用梯度下降更新权重向量：
    $${\mathbf{w}}^{(k)}={\mathbf{w}}^{(k-1)}-\alpha \nabla l({\mathbf{w}}^{(k)})={\mathbf{w}}^{(k-1)}-\alpha (-y_i{x}_i)={\mathbf{w}}^{(k-1)}+\alpha y_i{x}_i$$

如果循环收敛一直是0，说明这是被完全分类正确的模型。
这个算法是在20世纪60年代开发1960s，是最早的神经网络之一，被称为perceptron 感知器。