Perceptron -收敛证明

Question

我研究了感知器算法，并试图证明自己的收敛性。然而，我错了，我找不到错误。

假设：

1. 我们假设存在一些$\gamma > 0$，使得$$y_{t}(\theta ^{*})^{T}x_{t} \geq \gamma $$对于所有$t = 1，\l ldots，n$。附加数字$\gamma > 0$用于确保每个示例按照有限的裕度正确分类。
2. 我们将假设所有(训练)图像都有有界欧几里德范数，即$$\left \bar{x_{t} \right \leq$对于所有$t$和一些有限的$R$。

根据假设，学习规则是：

$$\theta ^{(k)}=θ^{(k-1)} +mu y_{t}bar{x_{t}$$

现在，$$(\theta ^{t}}^{T}{(K)}= (\theta ^{*})^{T}\theta ^{(k-1)} }+ \mu y_{t}bar{x_{t} \geq (\theta{t*}){T}}{T}}{T}{(k-1)}+ \mu \γ$$，通过诱导诱导$$(\theta {x*})^{T}{(K)}{(K)}{(K)}geq^{T}{(K)}{(K)}

同时，$$\left \ \theta ^{(k)} } \theta \θ^{(K)}{2}\θ^{(k-1)} }+ \mu y_{t}{t}{x_{t}}\{2}=\\x_{{t}+左\theta ^{(k-1)}}\x_{(k-1)}+2 mu y_{t}((k-1)^{{T}})\bar{x_{t}+\左\mu条形{x_{t}}\\{2} \leq \左\θ^a ^{(k-1)} \右\{2} \mu\bar{x_{t}} \右\{2}\leq\左\{2}\leq \theta ^{(k-1)}右\{2}}{2}+{2}R^2}$$

所以，通过归纳

$$\left \θ^{(k)} \右\{2} \leq }{2}{2}R^{2}$$

我们现在可以将第1部分和第2部分结合起来，将$\theta^∗$和$\theta(K)$之间的余弦结合起来：

$$\cos(θ^{*}，\theta ^{(k)}) =\frac{\theta ^{{(K)}}{{(K)}}{\左\theta ^{*} \右\theta ^{(k)} \ \geq \\geq\\sqrt{k*}{2}{2}{2}{2}左}\\θ^2}右}$$

由于余弦是以1为界的，我们得到：

$$k \leq \frac{R^{2}\左\theta ^{*} \右{2}{2}{γ^2}}$$

问题是，正确的结果应该是：

$$k \leq \frac{mu^2}{2}\左\θ^{*} {2}}{2}{2}{γ^2}$$

Answer 1

您介绍的是感知器的收敛性的典型证明，确实独立于$\mu$。因此，结论是正确的。

通常，$\theta^*x$表示一个将两个类完全分开的超平面。

公式$k \le框架{mu^2R^2\theta^*\γ^2}$没有意义，因为它意味着如果您将$\mu$设置为小，则$k$在仲裁上接近$0$。也就是说，在学习速度小的情况下，它会立即收敛。您可能需要仔细查看感知器算法的终止条件。