Note20

Perceptron

Linear Classifiers

我们在上次的Note19中提及到了Naive Bayes中的提取feature的思想,我们在这里尝试把一个数据点的所有特征提取出来，提取成为一个向量的形式

f(x) = [f1(x), f2(x), ..., fn(x)]

与之对应的，每个feature还有一个权重

w = [w1, w2, ..., wn]

线性分类器的基本思想是利用特征的线性组合来进行分类，我们把这个值叫做激活值激活函数之前的值即activation。具体公式如下

$$\begin{array}{rl}{\text{activation}}_w(x)& =h_w(x)=\sum _i{w}_i{f}_i(x)={\mathbf{w}}^{\top }\mathbf{f}(x)=\mathbf{w}\cdot \mathbf{f}(x)\end{array}$$

我们来着重看一下$h_w(x)$这个值： 如果我们只有两个lable，可以回忆一下之前提及到的垃圾邮件的例子，这就是只有两个标签—只有ham和spam。

• 这时候$h_w(x)$如果为正，我们就把数据点标记为正类。
• 如果$h_w(x)$值为负，我们就把数据点标记为负类

Decision Boundary

我们用数学的角度来看一下$h_w(x)$的值：

$$\begin{array}{rl}{h}_{\mathbf{w}}(\mathbf{x})& =\mathbf{w}\cdot \mathbf{f}(\mathbf{x})=\Vert \mathbf{w}\Vert \Vert \mathbf{f}(\mathbf{x})\Vert \cos (\theta )\end{array}$$

看最后一串，决定$h_w(x)$值正负的是cosθ，因为两个向量的模是正的。也就是说

$$\begin{array}{rl}\text{classify}(\mathbf{x})& =\{\begin{array}{ll}+& \text{if }\theta <\frac{\pi }{2}\\ -& \text{if }\theta >\frac{\pi }{2}\end{array}\end{array}$$

我们已知了向量w，那我们是不是可以画一条与向量w垂直的虚线，任何位于这条线上的特征向量其$h_w(x)$的值都为0，即满足式子${\mathbf{w}}^T\mathbf{f}(\mathbf{x})=0$,我们把这条线叫做决策边界即Decision Boundary 我们可以根据决策边界来判断$h_w(x)$的值

---

Binary Perceptron

二分类感知机是一个简单的线性分类器，它的目的是为了找到一个权重向量w让训练集中的样本都可以正确分类。

Perceptron Algorithm

1. Initialize weights: w = 0
2. For each training example (x, y*):
   a. Compute prediction:
      y = classify(x)
   b. If y == y*, do nothing
   c. If y != y*, update weights:
      w ← w + y* f(x)
3. Repeat until all samples are classified correctly in one pass

其中：

• y*是真实的lable
• y是模型预测的lable
• f(x)是样本特征向量

算法正确性验证

核心的更新规则就是$w\leftarrow w+y^{\ast }f(x)$ 1.我们假设$y^{\ast }=1$，$y=-1$。即原本为正类的数据点被分错分到负类里去了 2.我们可以推断的是：当前的$h_w(x)$是偏小的，我们期望是让$h_w(x)$变大 3.更新后的权重为

$$\begin{array}{rl}{w}^{\prime }& =w+f(x)\end{array}$$

4.更新后的激活值为

$$\begin{array}{rl}{h}_{w^{\prime }}(x)& =(w+f(x){)}^{T}f(x)=w^{T}f(x)+f(x{)}^{T}f(x)=h_w(x)+f(x{)}^{T}f(x)\end{array}$$

5.因为

$$\begin{array}{r}f(x{)}^{T}f(x)\ge 0\end{array}$$

即激活值会变大，这也就表明了这种更新法则是符合我们的预期—让$h_w(x)$变大

Bias

如果我们的决策边界模型只有$w^{T}f(x)$,那么我们的决策边界就必须经过原点，这非常限制模型的能力，因为很多不同lable的数据点虽然能被一条直线分开，但那条直线不一定经过原点。我们就参考着一次函数的样式加入了bias term,让它变成

$$\begin{array}{rl}{w}^{T}f(x)+b& =0\end{array}$$

实现方法通常是给每个特征向量额外加一个恒等于1的feature，然后通过控制权重w来控制大小，这样模型仍然可以写成点积的形式:

$$\begin{array}{rl}{h}_w(x)& =w^{T}f(x)\end{array}$$

---

Multiclass Perceptron

多个类别的和binary非常类似，如果有K个lable，那么就有K个权重。与二分类感知机对应的是，二分类感知机只有一个权重，因为可以用正负来区别两个lable. 对于输入样本，计算它的每个lable的score:

$$\begin{array}{rl}{\text{score}}_k& =w_k^{T}f(x)\end{array}$$

选择分数最高的lable:

$$\begin{array}{rl}\hat{y}& =\arg \underset{k}{\max }{w}_k^{T}f(x)\end{array}$$

多分类感知机更新规则

同样的：

• y*是真实的并且正确的lable
• y是被错误预测的lable
• f(x)是样本特征向量

那么就可以得到：

$$\begin{array}{rl}{w}_{y^{\ast }}& \leftarrow w_{y^{\ast }}+f(x)\\ w_y& \leftarrow w_y-f(x)\end{array}$$

给正确类别的权重加上这个样本，给错误类别减去这个样本

---

Linear Regression

和前面不同的是:

• Regression预测的是连续的数值，比如房价温度销量等等
• Classification预测的是类别 和前面相同的是：
• 模型相同，即权重和特征向量的格式相同 特征向量是

$$\begin{array}{rl}x& =[1,x_1,x_2,\dots ,x_n]\end{array}$$

对应的权重也是和之前的格式，注意特征向量的第一项1是bias term，那么我们可以得到$h_w(x)$为：

$$\begin{array}{rl}{h}_w(x)& =w_0+w_1{x}_1+w_2{x}_2+\cdots +w_n{x}_n={\mathbf{w}}^T\mathbf{x}\end{array}$$

L2 Loss

训练线性回归时，我们希望预测值接近真实值 对于第 j 个样本：

$$\begin{array}{rl}{\text{error}}_j& =y_j-h_w(x_j)\end{array}$$

L2 Loss是误差平方:

$$\begin{array}{r}(y_j-h_w(x_j){)}^2\end{array}$$

整个训练集上的loss：

$$\begin{array}{rl}Loss(h_w)& =\frac{1}{2}\sum _{j=1}^N(y_j-h_w(x_j){)}^2\end{array}$$

前面加上1/2是为了求导时抵消平方项前面的2，让整体公式更加整洁

Matrix Form矩阵形式

将所有的训练样本堆起来:

$$\begin{array}{rl}\mathbf{y}& =\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_N\end{array}\right]\end{array}$$

设计矩阵：

$$\begin{array}{rl}\mathbf{X}& =\left[\begin{array}{cccc}1& x_1^1& \cdots & x_n^1\\ 1& x_1^2& \cdots & x_n^2\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_1^N& \cdots & x_n^N\end{array}\right]\end{array}$$

权重为:

$$\begin{array}{rl}\mathbf{w}& =\left[\begin{array}{c}{w}_0\\ w_1\\ ⋮\\ w_n\end{array}\right]\end{array}$$

那么loss可以写成：

$$\begin{array}{rl}\mathrm{Loss}(h_w)& =\frac{1}{2}{\Vert \mathbf{y}-\mathbf{Xw}\Vert }_2^2\end{array}$$

线性回归最重要的一个特点是它有闭式解( closed-form solution ) 我们对loss求梯度:

$$\begin{array}{rl}{\nabla }_w\frac{1}{2}\Vert y-Xw{\Vert }_2^2& =-X^{T}y+X^{T}Xw\end{array}$$

令梯度为0:

$$\begin{array}{rl}{X}^{T}Xw& =X^{T}y\end{array}$$

如果$X^{T}X$可逆的话，那么就可以得到:

$$\begin{array}{rl}\hat{\mathbf{w}}& =(X^{\top }X{)}^{-1}{X}^{\top }\mathbf{y}\end{array}$$

---

Logistic Regression

Logistic Regression用logistic function把线性模型输出转成概率，需要注意的是

Logistic Regression 名字里有 regression，但它主要用于 classification

Logistic Function / Sigmoid Function

Logistic Function:

$$\begin{array}{rl}g(z)& =\frac{1}{1+e^{-z}}\end{array}$$

其中

$$\begin{array}{rl}z& ={\mathbf{w}}^T\mathbf{x}\end{array}$$ $$\begin{array}{rl}{h}_{\mathbf{w}}(\mathbf{x})& =\frac{1}{1+e^{-{\mathbf{w}}^T\mathbf{x}}}.\end{array}$$

它的输出一定在0到1之间，因此可以解释为: 当$h_w(x)>0.5$时预测为正类，下面的式子为样本属于正类的概率

$$\begin{array}{rl}P(y=+1\mid \mathbf{f}(x);\mathbf{w})& =\frac{1}{1+e^{-{\mathbf{w}}^{\top }\mathbf{f}(x)}}\end{array}$$

和当$h_w(x)<0.5$时预测为负类，下面的式子属于样本属于负类的概率

$$\begin{array}{rl}P\left(y=-1\mid f(\mathbf{x});\mathbf{w}\right)& =1-\frac{1}{1+e^{-{\mathbf{w}}^{\top }f(\mathbf{x})}}\end{array}$$

Logistic Regression的损失函数和梯度

首先有一个数学小性质

$$\begin{array}{rl}{g}^{\prime }(z)& =g(z)(1-g(z))\end{array}$$

然后我们看L2 Loss的函数：

$$\begin{array}{rl}Loss(w)& =\frac{1}{2}(y-h_w(x){)}^2\end{array}$$

然后对第i个权重求偏导

$$\begin{array}{rl}\frac{\partial }{\partial w_i}\frac{1}{2}(y-h_w(x){)}^2& =(y-h_w(x))\frac{\partial }{\partial w_i}(y-h_w(x))=-(y-h_w(x))h_w(x)(1-h_w(x))x_i\end{array}$$

因为logistic regression没有简单的closed-form solution, 所以通常用gradient descent来估计权重

---

Multi-Class Logistic Regression

和之前Perceptron的思路一样，都是从binary变成多类别的，对于多分类逻辑回归我们希望模型输出一个概率分布:

P(y=1|x), P(y=2|x), ..., P(y=K|x)
其中需要满足:
每个概率都 ≥ 0
所有概率加起来 = 1

我们用的模型是Softmax Function，Softmax是logistic function的多分类拓展: 对于类别i我们有:

$$\begin{array}{rl}P(y=i\mid \mathbf{f}(\mathbf{x});\mathbf{w})& =\frac{e^{{\mathbf{w}}_i^{\top }\mathbf{f}(\mathbf{x})}}{{\sum }_{k=1}^K{e}^{{\mathbf{w}}_k^{\top }\mathbf{f}(\mathbf{x})}}.\end{array}$$

其中:

• 每个类别都有自己的权重向量 w_i；
• 每个类别都会得到一个 score；
• 对 score 做指数变换；
• 再除以所有类别指数分数之和；
• 得到每个类别的概率

Likelihood

我们在这里用Likelihood方法来表示参数w以使观测到的数据有最大的可能性,我们的训练目标就是最大化这个likelihood：

$$\begin{array}{rl}\ell ({\mathbf{w}}_1,\dots ,{\mathbf{w}}_K)& =\prod _{i=1}^{n}P(y_i\mid f(x_i);\mathbf{w})\end{array}$$

注意一下区分:

Softmax 负责算每个类别的概率；
Likelihood 负责把每个样本“真实类别的概率”拿出来乘在一起

然后我们为了写出多分类的likelihood，定义下面:

$$\begin{array}{rl}{t}_{i,k}& =\{\begin{array}{ll}1,& y_i=k\\ 0,& y_i\ne k\end{array}\end{array}$$

即:

• 如果第 i 个样本真实类别是 k，那么 t_{i,k}=1；
• 否则 t_{i,k}=0 这里举个例子更容易理解，对于某个样本x_i，Softmax会输出：

P(猫 | x_i)
P(狗 | x_i)
P(鸟 | x_i)

但是真实标签只有一个，比如真实标签是狗，我们只想保留:

P(狗 | x_i)

我们就用$t_{i,k}$来表示：

如果第 i 个样本真实类别是 k，那么 t_{i,k} = 1
否则 t_{i,k} = 0

所以就可以得到如果真实类别是狗，也就是第二类那么:

t_i = [0, 1, 0]

所以说：

$$\begin{array}{r}P(\mathrm{猫}\mid x_i{)}^0\times P(\mathrm{狗}\mid x_i{)}^1\times P(\mathrm{鸟}\mid x_i{)}^0=P(\mathrm{狗}\mid x_i)\end{array}$$

然后我们的likelihood公式就可以写成:

$$\begin{array}{rl}\ell ({\mathbf{w}}_1,\dots ,{\mathbf{w}}_K)& =\prod _{i=1}^n\prod _{k=1}^K{\left(\frac{e^{{\mathbf{w}}_k^T\mathbf{f}({\mathbf{x}}_i)}}{{\sum }_{\ell =1}^K{e}^{{\mathbf{w}}_{\ell }^T\mathbf{f}({\mathbf{x}}_i)}}\right)}^{t_{i,k}}\end{array}$$

对应的log- likelihood就是:

$$\begin{array}{rl}log\ell ({\mathbf{w}}_1,\dots ,{\mathbf{w}}_K)& =\sum _{i=1}^n\sum _{k=1}^K{t}_{i,k}\log \left(\frac{e^{{\mathbf{w}}_k^T\mathbf{f}({\mathbf{x}}_i)}}{{\sum }_{\ell =1}^K{e}^{{\mathbf{w}}_{\ell }^T\mathbf{f}({\mathbf{x}}_i)}}\right)\end{array}$$

Softmax的梯度

$$\begin{array}{rl}{\nabla }_{{\mathbf{w}}_j}\log \ell (\mathbf{w})& =\sum _{i=1}^n{\nabla }_{{\mathbf{w}}_j}\sum _{k=1}^K{t}_{i,k}\log \left(\frac{e^{{\mathbf{w}}_k^{\top }\mathbf{f}({\mathbf{x}}_i)}}{{\sum }_{\ell =1}^K{e}^{{\mathbf{w}}_{\ell }^{\top }\mathbf{f}({\mathbf{x}}_i)}}\right)=\sum _{i=1}^n\left(t_{i,j}-\frac{e^{{\mathbf{w}}_j^{\top }\mathbf{f}({\mathbf{x}}_i)}}{{\sum }_{\ell =1}^K{e}^{{\mathbf{w}}_{\ell }^{\top }\mathbf{f}({\mathbf{x}}_i)}}\right)\mathbf{f}({\mathbf{x}}_i)\end{array}$$