最近看STRCF算法，这是一个克服遮挡和大幅形变的实时视觉追踪算法。这篇论文的主要贡献如下：

1. 通过将空间和时间正则化纳入 DCF 框架，提出了 STRCF 模型。基于在线 PA 的 STRCF 不仅可以合理地逼近多幅训练图像上的 SRDCF 形式，而且在较大的外观变化情况下比 SRDCF 具有更强的鲁棒性。
2. 为高效求解 STRCF，开发了一种 ADMM 算法，其中每个子问题都有封闭形式的解。并且本文提出的算法可以在非常少的迭代中经验地收敛。
3. 本文提出的 STRCF 具有人工设计的特征，可以实时运行，相比 SRDCF 在准确率上有了显著的提升。此外，STRCF 与最先进的追踪器 [9，15] 相比，性能良好。

论文中反复提到STRCF算法是在线被动攻击学习(PA）算法的扩展，于是我找来了PA算法的论文，一篇2006年发表的古老的论文。

问题

符号	表示
xt$x_t$	n维向量，第t次循环中的输入实例
yt$y_t$	xt$x_t$对于的类标，取值为+1,-1
(xt,yt)$(x_t,y_t)$	实例-类标对，也叫一个示例
w	n维权重向量
|w⋅x|$|w\cdot x|$	预测置信度
yt(wt⋅xt)$y_t(w_t\cdot x_t)$	第t次循环中（有符号的）边际利润

当边际利润margin是正数时，sign(wt⋅xt)=yt$sign(w_t\cdot x_t)=y_t$，这时算法预测正确。然而，我们不满足于一个正边际利润值，我们还希望算法能有很高的预测置信度。于是，算法的目标是尽可能经常实现一个最少是1的边际利润，在每次循环中当边际利润小于1时就会有一个瞬间损失。这就是所谓的hinge损失函数：

解释：当边际利润>1时，损失值=0，否则等于1和边际利润之间的差值。注意到，选择1作为边际阈值其实是相当随意的。所以后面在解决回归问题时，作者又将hinge损失函数推广到一般化，将这个边际阈值作为一个用户输入的参数。
记lt=l(wt;(xt,yt))$l_t=l(w_t;(x_t,y_t))$，本文给出的算法将被证明在给定的示例序列中获得一个小的累积平方损失，即作者能证明在∑Tt=1l2t$\sum _{t=1}^T{l}_t^2$上不同的界限，其中T是序列的长度。注意到当有一个预测错误出现时，l2t≥1$l_t^2\ge 1$，因此累积平方损失的界限也限制在示例序列中错误预测的数量。

二分类算法

本节作者给出了二分类问题在线学习算法的三种变体。这三种变体的w1$w_1$都初始化为全0向量，区别在于更新规则不同。

PA算法的更新规则

在第t次循环中设置新的权重向量wt+1$w_{t+1}$是下一次循环中约束优化问题的解，即：

每当lt=0$l_t=0$时，则wt+1=wt$w_{t+1}=w_t$，这时候算法是被动性的(passive)。相反的，当lt>0$l_t>0$时，尽管有步长要求，算法还是会攻击性(aggressively)的迫使wt+1$w_{t+1}$满足约束条件l(wt+1;(xt,yt))=0$l(w_{t+1};(x_t,y_t))=0$。于是作者将这个算法命名为被动攻击（Passive-Aggressively，简称：PA）。
一方面，我们要求wt+1$w_{t+1}$可以对当前示例准确分类，并且取得充分高的边际利润；另一方面，wt+1$w_{t+1}$要尽可能接近wt$w_t$，从而能保留之前的循环中学习到的信息。
公式(2)有一个简单的闭式解形式：

当lt=0,wt+1=wt$l_t=0,w_{t+1}=w_t$就是公式(2)的最优解；当lt>0$l_t>0$时，公式(2)中优化问题的拉格朗日函数为：

其中，τ≥0$\tau \ge 0$是拉格朗日乘子。对(4)式关于w求偏导，并且令偏导为0，

于是有，

将(5)式代入(4)中，由于(xt⋅xt)=0$x_t\cdot x_t)=0$，则有，

对L(τ)$\mathcal{L}(\tau )$关于τ$\tau$求偏导，并且令偏导为0，

可得，

ps:(7)式同时也满足lt=0$l_t=0$的情况。

PA-I、PA-II算法的更新规则

在现实生活中，考虑到数据常带有噪声的情况，PA算法的更新策略可能会导致不好的结果。一个类标错误的实例可能就会在一个错误的方向上大幅度改变了权值向量w。为了解决这个问题，作者提出PA算法的两种变体。

这里C是一个大于0的参数，用来控制目标函数中的松弛项。注意到当C取值很大时，算法在更新策略上更有攻击性，所以作者把C称作攻击力因子。
相应的，如果ζ$\zeta$换做平方的形式，则目标函数可以写为，

这个时候ζ$\zeta$就无需满足非负数的条件，因为ζ2${\zeta }^2$是永远满足非负数的。式(8)(9)均有闭式解：

算法的伪代码