牛客网算法八股刷题系列(三) 最小均方误差算法,h-k算法,感知机算法-爱代码爱编程
牛客网算法八股刷题系列——最小均方误差算法,H-K算法,感知机算法
题目描述
基于二次准则函数的 H-K \text{H-K} H-K算法较之于感知机算法的优点是 ( ) ? \text(\quad)? ()?
A \mathcal A \quad A 计算量小
B \mathcal B \quad B 可以判别问题是否线性可分
C \mathcal C\quad C 其解完全适用于非线性可分的情况
正确答案: B \mathcal B B
题目解析
关于感知机算法
在感知机算法中,我们介绍了其对于线性分类的策略:错误驱动
关于神经元内的阈值,这里合并在权重中。
L
(
W
)
=
∑
(
x
(
i
)
,
y
(
i
)
)
∈
D
−
y
(
i
)
(
W
T
x
(
i
)
)
\mathcal L(\mathcal W) = \sum_{(x^{(i)},y^{(i)}) \in \mathcal D} -y^{(i)} \left(\mathcal W^T x^{(i)}\right)
L(W)=(x(i),y(i))∈D∑−y(i)(WTx(i))
关于二分类任务,它的判别思想很朴素,就是指示函数:
I
=
{
1
if
y
(
i
)
(
W
T
x
(
i
)
)
<
0
0
otherwise
\mathcal I = \begin{cases} 1 \quad \text{if }y^{(i)}\left(\mathcal W^Tx^{(i)}\right) < 0 \\ 0 \quad \text{otherwise} \end{cases}
I={1if y(i)(WTx(i))<00otherwise
可以看出, L ( W ) \mathcal L(\mathcal W) L(W)明显是存在下界的,这个下界结果是 0 0 0:当 L ( W ) = 0 \mathcal L(\mathcal W) = 0 L(W)=0时,所有的样本均划分正确。
但从损失函数 L ( W ) \mathcal L(\mathcal W) L(W)中,我们同样可以发现一些问题:
- 基于 L ( W ) \mathcal L(\mathcal W) L(W)产生的模型不唯一:只要满足 L ( W ) = 0 \mathcal L(\mathcal W) = 0 L(W)=0的直线模型,都可以作为样本空间的划分边界;
- 无法判别是否线性可分:如果出现了线性不可分的问题,例如:
这是一个‘仅存在少量错误’的线性不可分情况。
关于这种情况,我们的损失函数 L ( W ) \mathcal L(\mathcal W) L(W)永远无法达到终极的 0 0 0状态。而是一个小的正数值。我们从上帝视角看,我们知道该正数值就是基于线性不可分条件下的最优分类结果,但 L ( W ) \mathcal L(\mathcal W) L(W)只会认为样本学习错误。因而它的梯度优化永远不会结束。
回归感知机算法的第一个问题,其原因是:指示函数的这种判别方式并没有指向某个具体的解,而是一个解区域;而解区域中的任意一个解均对应一个划分正确的划分边界:
最小化均方误差算法( Least Mean Square Error,LMSE \text{Least Mean Square Error,LMSE} Least Mean Square Error,LMSE)
给定样本集合
D
=
{
(
x
(
i
)
,
y
(
i
)
)
}
i
=
1
N
\mathcal D = \{(x^{(i)},y^{(i)})\}_{i=1}^N
D={(x(i),y(i))}i=1N,关于样本特征集合
X
\mathcal X
X可表示为如下形式:
X
=
(
x
1
(
1
)
,
x
2
(
1
)
,
⋯
,
x
p
(
1
)
x
1
(
2
)
,
x
2
(
2
)
,
⋯
,
x
p
(
2
)
⋮
⋮
⋱
⋮
x
1
(
N
)
,
x
2
(
N
)
,
⋯
,
x
p
(
N
)
)
N
×
p
\mathcal X = \begin{pmatrix} x_1^{(1)},& x_2^{(1)},& \cdots,& x_{p}^{(1)} \\ x_1^{(2)},& x_2^{(2)},&\cdots,& x_p^{(2)} \\ \vdots &\vdots &\ddots & \vdots \\ x_1^{(N)},&x_2^{(N)},& \cdots,& x_p^{(N)} \end{pmatrix}_{N \times p}
X=
x1(1),x1(2),⋮x1(N),x2(1),x2(2),⋮x2(N),⋯,⋯,⋱⋯,xp(1)xp(2)⋮xp(N)
N×p
如果我们不仅希望样本能够被正确分类,并且还希望从解区域中找到最优解。一个动机是:从解区域中找到一个确定解。
基于上述动机,我们尝试给模型/决策边界 W T x ( i ) \mathcal W^Tx^{(i)} WTx(i)一个实际的物理意义:
W T x ( i ) \mathcal W^Tx^{(i)} WTx(i)表示样本点 x ( i ) x^{(i)} x(i)到决策边界 W T x \mathcal W^Tx WTx的距离,该距离记作 b ( i ) b^{(i)} b(i),并根据 b ( i ) b^{(i)} b(i)的实际意义,它是一个正值:
W T x ( i ) = b ( i ) > 0 \mathcal W^Tx^{(i)} = b^{(i)} > 0 WTx(i)=b(i)>0
那么
N
N
N个样本点自然能够得到
N
N
N个方程:
{
∑
j
=
1
p
w
j
⋅
x
j
(
1
)
=
b
(
1
)
∑
j
=
1
p
w
j
⋅
x
j
(
2
)
=
b
(
2
)
⋮
∑
j
=
1
p
w
j
⋅
x
j
(
N
)
=
b
(
N
)
\begin{cases} \sum_{j=1}^p w_j \cdot x_j^{(1)} = b^{(1)} \\ \sum_{j=1}^p w_j \cdot x_j^{(2)} = b^{(2)} \\ \vdots \\ \sum_{j=1}^p w_j \cdot x_j^{(N)} = b^{(N)} \end{cases}
⎩
⎨
⎧∑j=1pwj⋅xj(1)=b(1)∑j=1pwj⋅xj(2)=b(2)⋮∑j=1pwj⋅xj(N)=b(N)
我们在降维——维数灾难中介绍过,通常情况下样本数量
N
N
N远远大于样本维度
p
p
p。这使得上面的方程组成为了一个超定方程组。
除非数据集内的样本之间存在线性相关的情况,从而将行秩下降至 p p p,否则该超定方程组不存在精确解。至此,我们需要一个近似解。
关于这个近似解的策略如何描述?将
b
^
=
(
b
^
(
1
)
,
b
^
(
2
)
,
⋯
,
b
^
(
N
)
)
N
×
1
T
\hat b = (\hat b^{(1)},\hat b^{(2)},\cdots,\hat b^{(N)})_{N \times 1}^T
b^=(b^(1),b^(2),⋯,b^(N))N×1T表示所有样本到最终分类决策边界距离的期望值组成的向量;我们在学习过程中得到的模型输出表示为:
该‘模型表示’指的就是模型学习过程中计算得到的距离结果。
X
N
×
p
W
p
×
1
=
b
=
(
b
(
1
)
,
b
(
2
)
,
⋯
,
b
(
N
)
)
N
×
1
T
\mathcal X_{N \times p} \mathcal W_{p \times 1} = b = (b^{(1)},b^{(2)},\cdots,b^{(N)})_{N \times 1}^T
XN×pWp×1=b=(b(1),b(2),⋯,b(N))N×1T
模型输出
b
b
b和期望结果
b
^
\hat b
b^之间的误差向量
E
\mathcal E
E表示为:
E
=
b
−
b
^
=
X
W
−
b
^
\begin{aligned} \mathcal E & = b - \hat b \\ & = \mathcal X \mathcal W - \hat b \end{aligned}
E=b−b^=XW−b^
由于向量
X
W
\mathcal X\mathcal W
XW和向量
b
^
\hat b
b^内各元素之间的大小关系是不确定的,因而采用均方误差作为损失函数进行描述:
{
J
(
W
)
=
1
N
∣
∣
X
W
−
b
^
∣
∣
2
=
1
N
(
X
W
−
b
^
)
T
(
X
W
−
b
^
)
arg
min
W
J
(
W
)
\begin{cases} \begin{aligned} \mathcal J(\mathcal W) & = \frac{1}{N}||\mathcal X \mathcal W - \hat b||^2 \\ & = \frac{1}{N}(\mathcal X \mathcal W - \hat b)^T (\mathcal X \mathcal W - \hat b) \end{aligned} \\ \mathop{\arg\min}\limits_{\mathcal W} \mathcal J(\mathcal W) \end{cases}
⎩
⎨
⎧J(W)=N1∣∣XW−b^∣∣2=N1(XW−b^)T(XW−b^)WargminJ(W)
求解
J
(
W
)
\mathcal J(\mathcal W)
J(W)关于
W
(
t
)
\mathcal W^{(t)}
W(t)的梯度,使用梯度下降法(
Gradient Descent
\text{Gradient Descent}
Gradient Descent)对
W
\mathcal W
W进行迭代求解:
W
(
t
+
1
)
⇐
W
(
t
)
−
η
(
t
+
1
)
⋅
∇
W
(
t
)
J
(
W
(
t
)
)
\mathcal W^{(t+1)} \Leftarrow \mathcal W^{(t)} - \eta^{(t+1)} \cdot \nabla_{\mathcal W^{(t)}} \mathcal J(\mathcal W^{(t)})
W(t+1)⇐W(t)−η(t+1)⋅∇W(t)J(W(t))
关于梯度
∇
W
(
t
)
J
(
W
(
t
)
)
\nabla_{\mathcal W^{(t)}}\mathcal J(\mathcal W^{(t)})
∇W(t)J(W(t))可表示为:
链式求导法则。
∇
W
(
t
)
J
(
W
)
=
∂
J
(
W
(
t
)
)
∂
W
(
t
)
=
∂
J
(
W
(
t
)
)
∂
(
X
W
(
t
)
−
b
^
)
⋅
∂
(
X
W
(
t
)
−
b
^
)
∂
W
(
t
)
=
2
N
(
X
W
−
b
^
)
N
×
1
⋅
X
p
×
N
T
=
2
N
⋅
X
T
(
X
W
−
b
^
)
\begin{aligned} \nabla_{\mathcal W^{(t)}}\mathcal J(\mathcal W) & = \frac{\partial \mathcal J(\mathcal W^{(t)})}{\partial \mathcal W^{(t)}} \\ & = \frac{\partial \mathcal J(\mathcal W^{(t)})}{\partial (\mathcal X \mathcal W^{(t)} - \hat b)} \cdot \frac{\partial (\mathcal X \mathcal W^{(t)} - \hat b)}{\partial \mathcal W^{(t)}} \\ & = \frac{2}{N}(\mathcal X \mathcal W - \hat b)_{N \times 1} \cdot \mathcal X^T_{p \times N} \\ & = \frac{2}{N} \cdot \mathcal X^T (\mathcal X \mathcal W - \hat b) \end{aligned}
∇W(t)J(W)=∂W(t)∂J(W(t))=∂(XW(t)−b^)∂J(W(t))⋅∂W(t)∂(XW(t)−b^)=N2(XW−b^)N×1⋅Xp×NT=N2⋅XT(XW−b^)
最终关于权重向量递推公式表示为:
常数
2
N
\frac{2}{N}
N2可以合并至学习率
η
\eta
η中.
W
(
t
+
1
)
⇐
W
(
t
)
−
η
(
t
+
1
)
⋅
X
T
(
X
W
−
b
^
)
\mathcal W^{(t+1)} \Leftarrow \mathcal W^{(t)} - \eta^{(t+1)} \cdot \mathcal X^T(\mathcal X \mathcal W - \hat b)
W(t+1)⇐W(t)−η(t+1)⋅XT(XW−b^)
H-K \text{H-K} H-K算法
关于最小化均方误差算法,忽略了一个问题:期望结果 b ^ \hat b b^我们并没有给它制定规则。如果出现 b ^ \hat b b^给定有误的情况下,必然会出现错分样本的情况。
H-K
\text{H-K}
H-K算法的思路是:在使用均方误差优化权重
W
\mathcal W
W的同时,也优化
b
^
\hat b
b^。此时,损失函数
J
\mathcal J
J是变量
W
,
b
^
\mathcal W,\hat b
W,b^的函数。关于
b
^
\hat b
b^的递推公式重新表示为:
b
^
(
t
+
1
)
⇐
b
^
(
t
)
−
η
(
t
+
1
)
⋅
∇
b
^
(
t
)
J
(
W
(
t
)
,
b
^
(
t
)
)
\hat b^{(t+1)} \Leftarrow \hat b^{(t)} -\eta^{(t+1)} \cdot \nabla_{\hat b^{(t)}} \mathcal J(\mathcal W^{(t)},\hat b^{(t)})
b^(t+1)⇐b^(t)−η(t+1)⋅∇b^(t)J(W(t),b^(t))
其中梯度
∇
b
^
(
t
)
J
(
W
(
t
)
,
b
^
(
t
)
)
\nabla_{\hat b^{(t)}} \mathcal J(\mathcal W^{(t)},\hat b^{(t)})
∇b^(t)J(W(t),b^(t))表示为:
依然是链式求导法则。
∇
b
^
(
t
)
J
(
W
(
t
)
,
b
^
(
t
)
)
=
∂
J
(
W
(
t
)
)
∂
(
X
W
(
t
)
−
b
^
(
t
)
)
⋅
∂
(
X
W
(
t
)
−
b
^
(
t
)
)
∂
b
^
(
t
)
=
2
N
(
X
W
(
t
)
−
b
^
(
t
)
)
⋅
(
−
1
)
=
−
2
N
(
X
W
(
t
)
−
b
^
(
t
)
)
\begin{aligned} \nabla_{\hat b^{(t)}} \mathcal J(\mathcal W^{(t)},\hat b^{(t)}) & = \frac{\partial \mathcal J(\mathcal W^{(t)})}{\partial (\mathcal X \mathcal W^{(t)} - \hat b^{(t)})} \cdot \frac{\partial (\mathcal X \mathcal W^{(t)} - \hat b^{(t)})}{\partial \hat b^{(t)}} \\ & = \frac{2}{N}(\mathcal X \mathcal W^{(t)} - \hat b^{(t)}) \cdot (-1) \\ & = - \frac{2}{N}(\mathcal X \mathcal W^{(t)} - \hat b^{(t)}) \end{aligned}
∇b^(t)J(W(t),b^(t))=∂(XW(t)−b^(t))∂J(W(t))⋅∂b^(t)∂(XW(t)−b^(t))=N2(XW(t)−b^(t))⋅(−1)=−N2(XW(t)−b^(t))
最终,
b
^
\hat b
b^的递推公式可表示为:
2
N
\frac{2}{N}
N2依然合并到学习率
η
\eta
η中。
b
^
(
t
+
1
)
⇐
b
^
(
t
)
+
η
(
t
+
1
)
⋅
(
X
W
(
t
)
−
b
^
(
t
)
)
=
b
^
(
t
)
+
η
(
t
+
1
)
⋅
E
(
t
)
\begin{aligned} \hat b^{(t+1)} & \Leftarrow \hat b^{(t)} + \eta^{(t+1)} \cdot (\mathcal X \mathcal W^{(t)} - \hat b^{(t)}) \\ & = \hat b^{(t)} +\eta^{(t+1)} \cdot \mathcal E^{(t)} \end{aligned}
b^(t+1)⇐b^(t)+η(t+1)⋅(XW(t)−b^(t))=b^(t)+η(t+1)⋅E(t)
可以看出,
b
^
\hat b
b^迭代过程中的更新量与误差向量
E
\mathcal E
E相关。由于
X
W
\mathcal X\mathcal W
XW和
b
^
\hat b
b^之间的大小关系不确定,因而
E
\mathcal E
E的正负也不确定。为了保证迭代过程中
b
^
\hat b
b^恒正,将
b
^
\hat b
b^的迭代过程修改为如下形式:
b
^
(
t
+
1
)
⇐
b
^
(
t
)
+
η
(
t
+
1
)
⋅
(
E
(
t
)
+
∣
E
(
t
)
∣
)
\hat b^{(t+1)} \Leftarrow \hat b^{(t)} + \eta^{(t+1)} \cdot \left(\mathcal E^{(t)} + \left|\mathcal E^{(t)}\right|\right)
b^(t+1)⇐b^(t)+η(t+1)⋅(E(t)+
E(t)
)
观察,这种迭代过程可能出现的情况:
- 如果误差向量为正:意味着
∣
E
(
t
)
∣
=
E
(
t
)
\left|\mathcal E^{(t)}\right| = \mathcal E^{(t)}
E(t)
=E(t)。那么原式可写作:
多余的系数
2 2 2可以和上步骤中化简得
2 N \frac{2}{N} N2合并一下,当
N N N足够大时,这个数值变化极小;
b ^ ( t + 1 ) ⇐ b ^ ( t ) + 2 ⋅ η ( t + 1 ) ⋅ E ( t ) = b ^ ( t ) + η ( t + 1 ) ⋅ E ( t ) \begin{aligned} \hat b^{(t+1)} & \Leftarrow \hat b^{(t)} + 2 \cdot \eta^{(t+1)} \cdot \mathcal E^{(t)} \\ & = \hat b^{(t)} + \eta^{(t+1)} \cdot \mathcal E^{(t)} \end{aligned} b^(t+1)⇐b^(t)+2⋅η(t+1)⋅E(t)=b^(t)+η(t+1)⋅E(t) - 如果误差向量为零或者为负:
∣
E
(
t
)
∣
=
−
E
(
t
)
\left|\mathcal E^{(t)}\right| = - \mathcal E^{(t)}
E(t)
=−E(t)。那么原式可写作:
b ^ ( t + 1 ) ⇐ b ^ ( t ) + η ( t + 1 ) ⋅ 0 = b ^ ( t ) \begin{aligned} \hat b^{(t+1)} & \Leftarrow \hat b^{(t)} + \eta^{(t+1)} \cdot 0 \\ & = \hat b^{(t)} \end{aligned} b^(t+1)⇐b^(t)+η(t+1)⋅0=b^(t)
这意味着 b ^ \hat b b^的数值只会单调递增,不会减小。
观察
W
(
t
)
\mathcal W^{(t)}
W(t)和
b
^
(
t
)
\hat b^{(t)}
b^(t)之间的关联关系。根据最小化均方误差的描述,
W
(
t
)
\mathcal W^{(t)}
W(t)的最优解即给定当前期望结果
b
^
(
t
)
\hat b^{(t)}
b^(t)条件下,通过损失函数
J
(
W
(
t
)
,
b
^
(
t
)
)
\mathcal J(\mathcal W^{(t)},\hat b^{(t)})
J(W(t),b^(t))取得的极值结果。因而有:
∇
W
(
t
)
J
(
W
(
t
)
,
b
^
(
t
)
)
≜
0
⇒
X
T
(
X
W
(
t
)
−
b
^
(
t
)
)
=
0
⇒
W
(
t
)
=
(
X
T
X
)
−
1
X
T
⋅
b
^
(
t
)
\begin{aligned} \nabla_{\mathcal W^{(t)}} \mathcal J(\mathcal W^{(t)},\hat b^{(t)}) \triangleq 0 & \Rightarrow \mathcal X^T (\mathcal X \mathcal W^{(t)} - \hat b^{(t)}) = 0 \\ & \Rightarrow \mathcal W^{(t)} = (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \cdot \hat b^{(t)} \end{aligned}
∇W(t)J(W(t),b^(t))≜0⇒XT(XW(t)−b^(t))=0⇒W(t)=(XTX)−1XT⋅b^(t)
至此,将
b
^
(
t
+
1
)
\hat b^{(t+1)}
b^(t+1)的迭代过程代入到上式中:
W
(
t
+
1
)
=
(
X
T
X
)
−
1
X
T
⋅
b
^
(
t
+
1
)
=
(
X
T
X
)
−
1
X
T
[
b
(
t
)
+
η
(
t
+
1
)
⋅
(
E
(
t
)
+
∣
E
(
t
)
∣
)
]
=
(
X
T
X
)
−
1
X
T
⋅
b
^
(
t
)
⏟
W
(
t
)
+
η
(
t
+
1
)
⋅
(
X
T
X
)
−
1
X
T
⋅
(
E
(
t
)
+
∣
E
(
t
)
∣
)
=
W
(
t
)
+
η
(
t
+
1
)
⋅
(
X
T
X
)
−
1
X
T
⋅
(
X
W
(
t
)
−
b
^
(
t
)
)
⏟
E
(
t
)
+
(
X
T
X
)
−
1
X
T
∣
E
(
t
)
∣
=
W
(
t
)
+
η
(
t
+
1
)
⋅
[
(
X
T
X
)
−
1
X
T
⋅
X
⏟
单位矩阵
I
W
(
t
)
−
(
X
T
X
)
−
1
X
T
⋅
b
^
(
t
)
⏟
=
0
+
(
X
T
X
)
−
1
X
T
∣
E
(
t
)
∣
]
=
W
(
t
)
+
η
(
t
+
1
)
(
X
T
X
)
−
1
X
T
∣
E
(
t
)
∣
\begin{aligned} \mathcal W^{(t+1)} & = (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \cdot \hat b^{(t+1)} \\ & = (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \left[b^{(t)} + \eta^{(t+1)} \cdot \left(\mathcal E^{(t)} + \left|\mathcal E^{(t)}\right|\right)\right] \\ & = \underbrace{(\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \cdot \hat b^{(t)}}_{\mathcal W^{(t)}} + \eta^{(t+1)} \cdot (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \cdot \left(\mathcal E^{(t)} + \left|\mathcal E^{(t)}\right|\right) \\ & = \mathcal W^{(t)} + \eta^{(t+1)} \cdot (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \cdot \underbrace{(\mathcal X \mathcal W^{(t)} - \hat b^{(t)})}_{\mathcal E^{(t)}} + (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \left|\mathcal E^{(t)}\right| \\ & = \mathcal W^{(t)} + \eta^{(t+1)} \cdot \left[\underbrace{\underbrace{(\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \cdot \mathcal X}_{单位矩阵\mathcal I} \mathcal W^{(t)} - (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \cdot \hat b^{(t)}}_{=0} + (\mathcal X^{T}\mathcal X)^{-1}\mathcal X^T \left|\mathcal E^{(t)}\right|\right] \\ & = \mathcal W^{(t)} + \eta^{(t+1)} (\mathcal X^T\mathcal X)^{-1} \mathcal X^T \left|\mathcal E^{(t)}\right| \end{aligned}
W(t+1)=(XTX)−1XT⋅b^(t+1)=(XTX)−1XT[b(t)+η(t+1)⋅(E(t)+
E(t)
)]=W(t)
(XTX)−1XT⋅b^(t)+η(t+1)⋅(XTX)−1XT⋅(E(t)+
E(t)
)=W(t)+η(t+1)⋅(XTX)−1XT⋅E(t)
(XW(t)−b^(t))+(XTX)−1XT
E(t)
=W(t)+η(t+1)⋅
=0
单位矩阵I
(XTX)−1XT⋅XW(t)−(XTX)−1XT⋅b^(t)+(XTX)−1XT
E(t)
=W(t)+η(t+1)(XTX)−1XT
E(t)
至此,关于
b
^
,
W
\hat b,\mathcal W
b^,W的迭代过程已经求解。关于
H-K
\text{H-K}
H-K算法的完整流程表示如下:
初始化:
初始化期望距离向量
b
^
(
0
)
⇒
N
×
1
\hat b^{(0)} \Rightarrow N \times 1
b^(0)⇒N×1,并通过
b
^
(
0
)
\hat b^{(0)}
b^(0)求解初始权重
W
(
0
)
=
(
X
T
X
)
−
1
X
T
b
(
0
)
\mathcal W^{(0)} = (\mathcal X^{T}\mathcal X)^{-1} \mathcal X^Tb^{(0)}
W(0)=(XTX)−1XTb(0);
循环过程
t
=
1
,
2
,
⋯
t=1,2,\cdots
t=1,2,⋯
- 计算误差向量: E ( t ) = X W ( t ) − b ^ ( t ) \mathcal E^{(t)} = \mathcal X\mathcal W^{(t)} - \hat b^{(t)} E(t)=XW(t)−b^(t);
- 对权重 W ( t + 1 ) \mathcal W^{(t+1)} W(t+1)进行更新: W ( t + 1 ) = W ( t ) + η ( t + 1 ) ⋅ ( X T X ) − 1 X T ∣ E ( t ) ∣ \mathcal W^{(t+1)} = \mathcal W^{(t)} + \eta^{(t+1)} \cdot \left(\mathcal X^T\mathcal X\right)^{-1} \mathcal X^T \left|\mathcal E^{(t)}\right| W(t+1)=W(t)+η(t+1)⋅(XTX)−1XT E(t) ;
- 对期望距离向量进行更新: b ^ ( t + 1 ) = b ^ ( t ) + η ( t + 1 ) ⋅ ( E ( t ) + ∣ E ( t ) ∣ ) \hat b^{(t+1)} = \hat b^{(t)} + \eta^{(t+1)} \cdot \left(\mathcal E^{(t)} + \left|\mathcal E^{(t)}\right|\right) b^(t+1)=b^(t)+η(t+1)⋅(E(t)+ E(t) );
- 重复执行循环体,直到如下情况出现:
E ( t ) \mathcal E^{(t)} E(t)自身是一个
N × 1 N \times 1 N×1的向量。
- E ( t ) > 0 \mathcal E^{(t)} > 0 E(t)>0:各分量继续迭代,观察后续结果。期望: E ( t ) = 0 \mathcal E^{(t)} = 0 E(t)=0
- E ( t ) = 0 \mathcal E^{(t)} = 0 E(t)=0:即 E ( t ) \mathcal E^{(t)} E(t)中的所有分量均为 0 0 0,此时各样本关于距离的预测结果 b ( t ) = b ^ ( t ) b^{(t)} = \hat b^{(t)} b(t)=b^(t)。算法结束,线性可分。
- E ( t ) < 0 \mathcal E^{(t)} < 0 E(t)<0:线性不可分。
解释一下为什么 E ( t ) < 0 \mathcal E^{(t)}<0 E(t)<0线性不可分。这里并不是指 E ( t ) \mathcal E^{(t)} E(t)均小于0才被确定为线性不可分,由于超定方程组能够有解的条件是极苛刻的。如果在拟合足够长时间后,依然存在 E ( t ) \mathcal E^{(t)} E(t)部分分量 < 0 <0 <0,那意味着假设将该分量强行扶正为0,会存在更多的样本被错误划分。
回归本题:
A
\mathcal A \quad
A
H-K
\text{H-K}
H-K算法的计算量是巨大的。因为每次关于权重
W
\mathcal W
W的迭代都需要计算
(
X
T
X
)
N
×
N
(\mathcal X^T\mathcal X)_{N \times N}
(XTX)N×N。
并且关于 ( X T X ) − 1 (\mathcal X^T\mathcal X)^{-1} (XTX)−1的计算并不是很稳定。在线性回归介绍中见到过这种格式。 X T X \mathcal X^T\mathcal X XTX我们能够保证它是一个实对称矩阵,但不能保证它是一个正定矩阵。因而矩阵 X T X \mathcal X^T\mathcal X XTX的逆是否存在,是值得商榷的问题。
B \mathcal B \quad B H-K \text{H-K} H-K算法判断是否线性可分的条件是误差 E ( t ) < 0 \mathcal E^{(t)} < 0 E(t)<0;但感知机算法无法判断是否存在非线性可分,最终会无限迭代下去,无法使损失函数为 0 0 0;
C \mathcal C \quad C H-K \text{H-K} H-K算法依然是线性分类模型,虽然在迭代过程中,尽可能使线性不可分的代价降至最小,但它无法将线性不可分的情况正确分类。