Chapter2 线性分类与感知机
2.1 线性回归
-
线性回归定义：利用数理统计中回归分析，来确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。
-
线性回归要素：
- 训练集（或训练数据），一般记为 x x x；
- 输出数据，一般记为 y y y；
- 模型（或假设），一般记为 y = h ( x ) y=h(x) y=h(x)，如果是直线则 y = k x + b y=kx+b y=kx+b；
- 训练数据的条目数，一条训练数据是由一对输入数据和输出数据组成的，输入数据的维度（即特征个数）为 n n n。
-
学习过程：
-
线性回归问题：
-
假设和 n n n 个因素有关，令
θ = [ θ 1 , θ 2 , ⋯ , θ n ] T , x = [ x 1 , x 2 , ⋯ , x n ] T \pmb{\theta} = \left[ \theta_1,\theta_2,\cdots,\theta_n \right]^\text{T},\ \ \pmb{x} = \left[ x_1,x_2,\cdots,x_n \right]^\text{T} θ=[θ1,θ2,⋯,θn]T, x=[x1,x2,⋯,xn]T
则有：
y = h θ ( x ) = θ T x y=h_{\pmb{\theta}}(\pmb{x})=\pmb{\theta}^\text{T}\pmb{x} y=hθ(x)=θTx -
假设给定样本： ( x ( i ) , y ( i ) ) (\pmb{x}^{(i)},y^{(i)}) (x(i),y(i))，构造代价（误差、损失）函数（目标代价函数为二次型形式）：
J ( θ ) = 1 2 ∑ i = 1 m ( y ( i ) − h θ ( x ( i ) ) ) J(\pmb{\theta})=\frac{1}{2} \sum_{i=1}^m \left( y^{(i)}-h_{\pmb{\theta}}(\pmb{x}^{(i)}) \right) J(θ)=21i=1∑m(y(i)−hθ(x(i)))
目标：找到超平面参数 θ \pmb{\theta} θ，使 J ( θ ) J(\pmb{\theta}) J(θ) 最小，即求解 min θ J ( θ ) \underset{\pmb{\theta}}{\min}J(\pmb{\theta}) θminJ(θ) -
求解，令 ∂ J ( θ ) ∂ θ = 0 \frac{\partial J(\pmb{\theta})}{\partial \pmb{\theta}} = 0 ∂θ∂J(θ)=0，即可得到
θ = ( X T X ) − 1 X T y \pmb{\theta} = \left( \pmb{X}^{\text{T}} \pmb{X} \right)^{-1} \pmb{X}^{\text{T}}\pmb{y} θ=(XTX)−1XTy
其中：
$$
\pmb{X} =
\begin{bmatrix}
(\pmb{x}{(1)}){\text{T}} \
(\pmb{x}{(2)}){\text{T}} \
\vdots \
(\pmb{x}{(N)}){\text{T}} \
\end{bmatrix}\pmb{y} =
\begin{bmatrix}
(\pmb{y}^{(1)}) \
(\pmb{y}^{(2)}) \
\vdots \
(\pmb{y}^{(N)}) \
\end{bmatrix}
$$
-
2.2 线性二分类问题
2.2.1 线性分类
-
定义：线性分类器则透过特征的线性组合来做出分类决定，以达到此种目的。简言之，样本通过直线(或超平面)可分。
输入：特征向量；
输出：哪一类，二分类问题对应 0 或 1，属于某类的概率对应 0~1 之间的数。
-
线性分类与线性回归差别：
- 输出意义不同：属于某类的概率 vs 回归具体值
- 参数意义不同：最佳分类直线 vs 最佳拟合直线
- 维度不同：二维分类 vs 一维回归
-
思路：构造这条二分类的“分界直线”
-
一边是负值，一边是正值。越属于这类，值越大（正）；反之越小（负）。
-
最终要求概率结果在 0~1 之间，需要对值做一个变换。
-
Sigmoid 函数：
y = 1 1 + e − z y=\frac{1}{1+e^{-z}} y=1+e−z1
其中， z = θ 1 x 1 + θ 2 x 2 + θ 0 z=\theta_1x_1+\theta_2x_2+\theta_0 z=θ1x1+θ2x2+θ0。
性质： y ′ = y ( 1 − y ) y'=y(1-y) y′=y(1−y)。
-
Softmax 回归：
-
给定样本 ( x ( i ) , y ( i ) ) \left( x^{(i)},y^{(i)} \right) (x(i),y(i))，注意 y ( i ) y^{(i)} y(i) 只能取 0 , 1 0,1 0,1；
-
构造代价（误差）函数：
J ( θ ) = 1 2 ∑ i = 1 N ( y ( i ) − h θ ( x ( i ) ) ) 2 J(\pmb{\theta})=\frac{1}{2}\sum_{i=1}^{N}\left( y^{(i)} - h_{\pmb{\theta}}(\pmb{x}^{(i)}) \right)^2 J(θ)=21i=1∑N(y(i)−hθ(x(i)))2
注意，这里
h θ ( x ( i ) ) = 1 1 + e − θ T x ( i ) h_{\pmb{\theta}}(\pmb{x}^{(i)}) = \frac{1}{1+e^{-\pmb{\theta}^{\text{T}}\pmb{x}^{(i)}}} hθ(x(i))=1+e−θTx(i)1
上述和回归方程一致，只是加了 S 函数，因此称为 softmax 回归。 -
目标：找到超平面参数 θ \pmb{\theta} θ，使 J ( θ ) J(\pmb{\theta}) J(θ) 最小，即求解 min θ J ( θ ) \underset{\pmb{\theta}}{\min}J(\pmb{\theta}) θminJ(θ)
-
-
2.2.2 梯度下降法
-
J J J 非线性，无法求出 d J ( θ ) d θ = 0 \frac{\text{d}J(\pmb{\theta})}{\text{d}\pmb{\theta}}=0 dθdJ(θ)=0 的解析解。
-
采用迭代的方式，让 J ( θ ) → 0 J(\pmb{\theta}) \rightarrow 0 J(θ)→0 ，即构造一个序列，使
θ 1 , θ 2 , … , θ k → θ ∗ \pmb{\theta}_1,\pmb{\theta}_2,\ldots,\pmb{\theta}_k \rightarrow \pmb{\theta}^* θ1,θ2,…,θk→θ∗
最简单的方式：
θ k + 1 = θ k + Δ θ k \pmb{\theta}_{k+1} = \pmb{\theta}_k + \Delta \pmb{\theta}_k θk+1=θk+Δθk
确定 Δ θ k \Delta \pmb{\theta}_k Δθk，即确定了如何构建序列。 -
令：
Δ θ k = − α d J d θ = − α ∇ θ J \Delta \pmb{\theta}_k = -\alpha \frac{\text{d} J}{\text{d} \pmb{\theta}} = -\alpha \nabla_{\pmb{\theta}}J Δθk=−αdθdJ=−α∇θJ
由于 J ( θ k + 1 ) = J ( θ k ) + [ d J d θ ] T Δ θ k J(\pmb{\theta}_{k+1}) = J(\pmb{\theta}_k)+\left[ \frac{\text{d}J}{\text{d}\pmb{\theta}} \right]^{\text{T}}\Delta \pmb{\theta}_k J(θk+1)=J(θk)+[dθdJ]TΔθk，则必有 J ( θ k + 1 ) ≤ J ( θ k ) J(\pmb{\theta}_{k+1}) \leq J(\pmb{\theta}_k) J(θk+1)≤J(θk)。证明：
∵ J ( θ ) = 1 2 ∑ i = 1 N ( y ( i ) − h θ ( x ( i ) ) ) 2 ∴ ∂ J ∂ θ = ∑ i = 1 N ( y ( i ) − h θ ( x ( i ) ) ( − ∂ h θ ( x ( i ) ) ∂ θ ) ∵ h θ ( x ( i ) ) = 1 1 + e − z ( x ( i ) ) and z ( x ( i ) ) = θ T x ( i ) ∴ ∂ h θ ( x ( i ) ) ∂ θ = ∂ h θ ( x ( i ) ) ∂ z ( i ) ∂ z ( i ) ∂ θ = h θ ( 1 − h θ ) x ( i ) \begin{array}{l} \because J(\pmb{\theta})=\frac{1}{2}\sum_{i=1}^{N}\left( y^{(i)} - h_{\pmb{\theta}}(\pmb{x}^{(i)}) \right)^2 \\ \therefore \frac{\partial J}{\partial \pmb{\theta}} = \sum_{i=1}^N\left(y^{(i)}-h_{\pmb{\theta}}(x^{(i)}\right)\left( -\frac{\partial h_{\pmb{\theta}}(x^{(i)})}{\partial \pmb{\theta}} \right) \\ \because h_{\pmb{\theta}}(x^{(i)})=\frac{1}{1+e^{-z(x^{(i)})}} \text{ and } z(x^{(i)})=\pmb{\theta}^{\text{T}}\pmb{x}^{(i)} \\ \therefore \frac{\partial h_{\pmb{\theta}}(x^{(i)})}{\partial \pmb{\theta}} = \frac{\partial h_{\pmb{\theta}}(x^{(i)})}{\partial z^{(i)}} \frac{\partial z^{(i)}}{\partial \pmb{\theta}} = h_{\pmb{\theta}}(1-h_{\pmb{\theta}})\pmb{x}^{(i)} \end{array} ∵J(θ)=21∑i=1N(y(i)−hθ(x(i)))2∴∂θ∂J=∑i=1N(y(i)−hθ(x(i))(−∂θ∂hθ(x(i)))∵hθ(x(i))=1+e−z(x(i))1 and z(x(i))=θTx(i)∴∂θ∂hθ(x(i))=∂z(i)∂hθ(x(i))∂θ∂z(i)=hθ(1−hθ)x(i)
2.3 对数回归于多分类回归
2.3.1 指数回归
-
从概率角度，二分类问题可使用条件概率描述：
P ( y ( i ) = 1 ∣ x ( i ) ) = h θ ( x ( i ) ) = 1 1 + e − θ T x ( i ) P ( y ( i ) = 0 ∣ x ( i ) ) = 1 − P ( y ( i ) = 1 ∣ x ( i ) ) = 1 − h θ ( x ( i ) ) P(y^{(i)}=1 | \pmb{x}^{(i)}) = h_{\pmb{\theta}}(\pmb{x}^{(i)}) = \frac{1}{1+e^{-\pmb{\theta}^{\text{T}}\pmb{x}^{(i)}}} \\ P(y^{(i)}=0 | \pmb{x}^{(i)}) = 1 - P(y^{(i)}=1 | \pmb{x}^{(i)}) = 1-h_{\pmb{\theta}}(\pmb{x}^{(i)}) P(y(i)=1∣x(i))=hθ(x(i))=1+e−θTx(i)1P(y(i)=0∣x(i))=1−P(y(i)=1∣x(i))=1−hθ(x(i))
或统一记为：
P ( y ∣ x , θ ) = ( h θ ) y ( 1 − h θ ( x ) ) 1 − y P(y|\pmb{x},\pmb{\theta}) = (h_{\pmb{\theta}})^y(1-h_{\pmb{\theta}}(\pmb{x}))^{1-y} P(y∣x,θ)=(hθ)y(1−hθ(x))1−y因为是二分类问题，可假设输出为 { 0 , 1 } \{0,1\} {0,1}。
-
重新修改指标函数：
J ( θ ) = − ∑ i ( y ( i ) log ( h θ ( x ( i ) ) ) + ( 1 − y ( i ) ) log ( 1 − h θ ( x ( i ) ) ) ) J(\pmb{\theta}) = - \sum_i \left( y^{(i)}\log\left(h_{\pmb{\theta}}(x^{(i)})\right) +(1-y^{(i)})\log\left( 1-h_{\pmb{\theta}}(x^{(i)}) \right)\right) J(θ)=−i∑(y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i))))
对其最小化，有：
∇ θ J ( θ ) = ∑ i x i ( h θ ( x ( i ) ) − y ( i ) ) \nabla_{\pmb{\theta}}J(\pmb{\theta}) = \sum_i \pmb{x}^{i} \left( h_{\pmb{\theta}}(x^{(i)})-y^{(i)} \right) ∇θJ(θ)=i∑xi(hθ(x(i))−y(i)) -
假设各样本相互独立，即服从 Bernouli 分布。取似然函数：
L ( θ ) = ∏ i = 1 m p ( y ( i ) ∣ x ( i ) , θ ) L(\pmb{\theta}) = \prod_{i=1}^{m}p(y^{(i)}|\pmb{x}^{(i)},\pmb{\theta}) L(θ)=i=1∏mp(y(i)∣x(i),θ)
对上式最大化等价于 min θ { − l ( θ ) } \underset{\pmb{\theta}}{\min} \left\{ -l(\pmb{\theta}) \right\} θmin{−l(θ)} ， l ( θ ) = log L ( θ ) l(\pmb{\theta}) = \log L(\pmb{\theta}) l(θ)=logL(θ)。
2.3.2 多分类回归
-
对于有 k k k 个标记的分类问题，分类函数如下：
h θ ( x ( i ) ) = [ p ( y ( i ) ) = 1 ∣ x ( i ) , θ p ( y ( i ) ) = 2 ∣ x ( i ) , θ ⋮ p ( y ( i ) ) = k ∣ x ( i ) , θ ] = 1 ∑ c = 1 k e x c T x ( i ) [ e θ 1 T x ( i ) e θ 2 T x ( i ) ⋮ e θ k T x ( i ) ] h_{\pmb{\theta}}(x^{(i)})= \begin{bmatrix} p(y^{(i)}) = 1 | \pmb{x}^{(i)},\pmb{\theta} \\ p(y^{(i)}) = 2 | \pmb{x}^{(i)},\pmb{\theta} \\ \vdots \\ p(y^{(i)}) = k | \pmb{x}^{(i)},\pmb{\theta} \end{bmatrix}= \frac{1}{\sum_{c=1}^k e^{\pmb{x}_c^{\text{T}}\pmb{x}^{(i)}}} \begin{bmatrix} e^{\pmb{\theta}_1^{\text{T}}\pmb{x}^{(i)}} \\ e^{\pmb{\theta}_2^{\text{T}}\pmb{x}^{(i)}} \\ \vdots \\ e^{\pmb{\theta}_k^{\text{T}}\pmb{x}^{(i)}} \end{bmatrix} hθ(x(i))= p(y(i))=1∣x(i),θp(y(i))=2∣x(i),θ⋮p(y(i))=k∣x(i),θ =∑c=1kexcTx(i)1 eθ1Tx(i)eθ2Tx(i)⋮eθkTx(i)
多分类有多个分割超平面：
θ = [ θ 1 T θ 2 T ⋮ θ k T ] \pmb{\theta} = \begin{bmatrix} \pmb{\theta}_1^{\text{T}} \\ \pmb{\theta}_2^{\text{T}} \\ \vdots \\ \pmb{\theta}_k^{\text{T}} \end{bmatrix} θ= θ1Tθ2T⋮θkT -
Softmax 方式：
-
取代价函数：
J ( θ ) = − [ ∑ i = 1 m ∑ i = 1 k l { y ( i ) = k } log exp ( θ ( k ) T x ( i ) ) ∑ j = 1 K exp ( θ ( j ) T x ( i ) ) ] J(\pmb{\theta}) = - \left[ \sum_{i=1}^m\sum_{i=1}^k l\{ y^{(i)}=k \} \log\frac{\text{exp}(\pmb{\theta}^{(k)\text{T}}\pmb{x}^{(i)})}{\sum_{j=1}^K\text{exp}(\pmb{\theta}^{(j)\text{T}}\pmb{x}^{(i)})} \right] J(θ)=−[i=1∑mi=1∑kl{y(i)=k}log∑j=1Kexp(θ(j)Tx(i))exp(θ(k)Tx(i))] -
对应梯度：
∇ θ J ( θ ) = − ∑ i = 1 m [ x ( i ) ( l { y ( i ) = k } − P ( y ( i ) = k ∣ x ( i ) ; θ ) ) ] \nabla_{\pmb{\theta}}J(\pmb{\theta})= -\sum_{i=1}^m \left[ \pmb{x}^{(i)} \left( l\{y^{(i)}=k\} -P(y^{(i)}=k|\pmb{x}^{(i)};\pmb{\theta}) \right) \right] ∇θJ(θ)=−i=1∑m[x(i)(l{y(i)=k}−P(y(i)=k∣x(i);θ))] -
代价函数可简写为：
l ( y , y ^ ) = − ∑ j = 1 K y j log y ^ j l(\pmb{y},\hat{\pmb{y}}) = -\sum_{j=1}^Ky_j\log\hat y_j l(y,y^)=−j=1∑Kyjlogy^j
称为交叉熵损失。
-
-
Softmax演示：
2.4 神经元模型
2.4.1 神经元模型
- 生物神经元：
- Spiking 模型
- Integrate&fire 模型
- 人工神经元模型：
- M-P 模型
- 单神经元模型
2.4.2 作用函数
-
非对称 Sigmoid 函数（Log Sigmoid）
f ( x ) = 1 1 + e − x or f ( x ) = 1 1 + e − β x , β > 0 f(x) = \frac{1}{1+e^{-x}} \text{ or } f(x)=\frac{1}{1+e^{-\beta x}},\beta > 0 f(x)=1+e−x1 or f(x)=1+e−βx1,β>0 -
对称型 Sigmoid 函数（Tangent Sigmoid）
f ( x ) = 1 − e − x 1 + e − x or 1 − e − β x 1 + e − β x , β > 0 f(x)=\frac{1-e^{-x}}{1+e^{-x}} \text{or} \frac{1-e^{-\beta x}}{1+e^{-\beta x}},\beta > 0 f(x)=1+e−x1−e−xor1+e−βx1−e−βx,β>0 -
对称型阶跃函数 - 阈值逻辑单元
f ( x ) = { + 1 , x ≥ 0 − 1 , x < 0 f(x)=\begin{cases} +1,x \geq 0 \\ -1,x < 0 \end{cases} f(x)={+1,x≥0−1,x<0
2.4.3 Hebb规则
-
Hebb学习规则是一个无监督学习规则，这种学习的结果是使网络能够提取训练集的统计特性，从而把输入信息按照它们的相似性程度划分为若干类。这一点与人类观察和认识世界的过程非常吻合，人类观察和认识世界在相当程度上就是在根据事物的统计特征进行分类。Hebb学习规则只根据神经元连接间的激活水平改变权值，因此这种方法又称为相关学习或并联学习。
-
连续权值的调整量与输入、输出的乘积成正比：
Δ w = α ⋅ x ⋅ y \Delta w = \alpha \cdot x \cdot y Δw=α⋅x⋅y
2.5 感知机模型
2.5.1 感知机原理
- 感知机（Perceptron）解决线性分类问题。
-
点到直线的距离的定义：
-
直线方程 a x + b y + c = 0 ax+by+c=0 ax+by+c=0，点 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)到直线的距离为：
d = a x 0 + b y 0 + c a 2 + b 2 d=\frac{ax_0+by_0+c}{\sqrt{a^2+b^2}} d=a2+b2 ax0+by0+c -
高维情况，分类面为超平面，有：
d = w T x ∣ ∣ w ∣ ∣ d=\frac{\mathbf{w} ^\text{T} \mathbf{x}}{||\mathbf{w}||} d=∣∣w∣∣wTx
其中， w 0 = b w_0=b w0=b。
-
2.5.2 感知机模型
-
感知机从输入到输出的模型如下：
y = f ( x ) = sign ( w T x ) y=f(x)=\text{sign}(\pmb{w}^{\text{T}}\pmb{x}) y=f(x)=sign(wTx)
其中， sign \text{sign} sign 为符号函数。 -
对于样本 ( x ( i ) , y ( i ) ) (x^{(i)},y^{(i)}) (x(i),y(i))，注意到，如果样本正确分类，则有：
{ y ( i ) ( w T x ( i ) ) ∥ w ∥ > 0 , 正确分类样本 y ( i ) ( w T x ( i ) ) ∥ w ∥ < 0 , 错误分类样本 \begin{cases} \frac{y^{(i)}(\pmb{w}^{\text{T}}\pmb{x}^{(i)})}{\begin{Vmatrix} \pmb{w}\end{Vmatrix}} > 0,正确分类样本 \\ \frac{y^{(i)}(\pmb{w}^{\text{T}}\pmb{x}^{(i)})}{\begin{Vmatrix} \pmb{w}\end{Vmatrix}} < 0,错误分类样本 \end{cases} ⎩ ⎨ ⎧∥w∥y(i)(wTx(i))>0,正确分类样本∥w∥y(i)(wTx(i))<0,错误分类样本
因此可定义损失函数如下：
L ( w ) = − 1 ∥ w ∥ ∑ y ( i ) ( w T x ( i ) ) L(\pmb{w}) = -\frac{1}{\begin{Vmatrix} \pmb{w} \end{Vmatrix}} \sum y^{(i)}(\pmb{w}^{\text{T}}\pmb{x}^{(i)}) L(w)=− w 1∑y(i)(wTx(i))
需要找到超平面参数 w ∗ \pmb{w}^* w∗，满足：
L ( w ∗ ) = min w ∑ y ( i ) ( w T x ( i ) ) L(\pmb{w}^*)=\underset{\pmb{w}}{\min} \sum y^{(i)}(\pmb{w}^{\text{T}}\pmb{x}^{(i)}) L(w∗)=wmin∑y(i)(wTx(i)) -
过程：输入 - 训练数据集 { x ( i ) , y ( i ) } \{\pmb{x}^{(i)},y^{(i)}\} {x(i),y(i)} （监督学习），输出 - w \pmb{w} w
-
赋初值 w 0 \pmb{w}_0 w0，数据序号 i = 1 i=1 i=1，迭代次数 k = 0 k=0 k=0
-
选择数据点 ( x ( i ) , y ( i ) ) (\pmb{x}^{(i)},y^{(i)}) (x(i),y(i))
-
判断该数据点是否为当前模型的误分类点，即判断若 y ( i ) ( w T x ( i ) ) y^{(i)}(\pmb{w}^{\text{T}}\pmb{x}^{(i)}) y(i)(wTx(i))，则更新权值：
w k + 1 = w k + η y ( i ) x ( i ) \pmb{w}_{k+1} = \pmb{w}_k + \eta y^{(i)} \pmb{x}^{(i)} wk+1=wk+ηy(i)x(i)
（与 Hebb 规则相同）
- 转到
2，直到训练集种没有误分类点
-
2.5.3 训练过程
……
2.5.4 感知机与神经元模型类比
-
具有相同的形式
