实际上就是线性分类的感知机算法PLA和针对非线性的适用算法POCKET
y（标签）={-1（bad）,1（good）}
h ( x ) = s i g n ( ( ∑ i = 1 d w i x i ) − t h r e s h o l d ( 阈 值 ) ) = s i g n ( w T x ) h(x)=sign((\sum^d_{i=1}w_ix_i)-threshold(阈值))=sign(w^Tx) h(x)=sign((∑i=1d​wi​xi​)−threshold(阈值))=sign(wTx)
w T 是 超 平 面 的 法 向 量 ， 为 { w 1 , w 2 , . . . , w n , d } 其 中 d 为 偏 执 量 ， w 的 维 度 与 x 样 本 的 维 度 一 致 。 同 理 ， 样 本 x = { x 1 , x 2 , . . . , x n , 1 } w^T是超平面的法向量，为\{w_1,w_2,...,w_n,d\}其中d为偏执量，w的维度与x样本的维度一致。同理，样本x=\{x_1,x_2,...,x_n,1\} wT是超平面的法向量，为{w1​,w2​,...,wn​,d}其中d为偏执量，w的维度与x样本的维度一致。同理，样本x={x1​,x2​,...,xn​,1}。会多一个维度
PLA的主要任务：找到一个w，使样本点可以正确二分类，即要求：
已知理想直线 W f W_f Wf​，求证 w t + 1 w_{t+1} wt+1​比 w t w_t wt​更接近 w f w_f wf​
w t + 1 = w t + y n ( t ) x n ( t ) ， ( x n ( t ) , y n ( t ) ) 是 一 个 错 分 点 更 接 近 代 表 着 向 量 的 内 积 增 大 即 求 证 w f T w t + 1 ≥ w f T w t 代 入 有 w f T w t + 1 = w f T ( w f + y n ( t ) x n ( t ) ) = w f T w t + y n ( t ) w f T x n ( t ) 因 为 w f 是 理 想 直 线 ， ， 在 线 性 可 分 的 时 候 全 部 分 类 正 确 即 y n ( t ) 与 w f T x n ( t ) 同 符 号 即 y n ( t ) w f T x n ( t ) ≥ 0 故 w f T w t + 1 ≥ w f T w t + min ⁡ n y n ( t ) w f T x n ( t ) — — 1 式 其 中 虽 然 已 知 内 积 增 大 ， 但 可 能 是 夹 角 减 小 （ 即 我 们 想 要 的 靠 近 ） 或 者 是 模 增 加 现 在 考 虑 模 长 的 改 变 ， 即 ∣ ∣ w t + 1 ∣ ∣ 与 ∣ ∣ w t ∣ ∣ 的 关 系 ∣ ∣ w t + 1 ∣ ∣ 2 = ∣ ∣ w t + y n ( t ) x n ( t ) ∣ ∣ 2 = ∣ ∣ w t ∣ ∣ 2 + 2 y n ( t ) w t T x n ( t ) + ∣ ∣ y n ( t ) x n ( t ) ∣ ∣ 2 因 为 对 w t 而 言 ， ( x n ( t ) , y n ( t ) ) 是 错 分 点 故 2 y n ( t ) w t T x n ( t ) ≥ 0 可 有 ∣ ∣ w t + 1 ∣ ∣ 2 ≤ ∣ ∣ w t ∣ ∣ 2 + ∣ ∣ y n ( t ) x n ( t ) ∣ ∣ 2 对 第 二 项 取 极 值 可 有 ∣ ∣ w t + 1 ∣ ∣ 2 ≤ ∣ ∣ w t ∣ ∣ 2 + max ⁡ n ∣ ∣ y n ( t ) x n ( t ) ∣ ∣ 2 — — 2 式 max ⁡ n ∣ ∣ y n ( t ) x n ( t ) ∣ ∣ 2 表 示 变 化 上 界 现 在 可 以 考 虑 夹 角 θ 的 cos ⁡ 值 cos ⁡ θ = w f T w t ∣ ∣ w f ∣ ∣ ∣ ∣ w t ∣ ∣ 所 以 需 要 考 虑 cos ⁡ θ 的 上 界 或 下 界 对 1 式 求 错 位 ： 初 始 化 w 0 = 0 w f T w 1 ≥ w f T w 0 + min ⁡ n y n w f T x n w f T w 2 ≥ w f T w 1 + min ⁡ n y n w f T x n . . . w f T w t ≥ w f T w t − 1 + min ⁡ n y n w f T x n 错 位 后 是 ： w f T w t ≥ w f T w 0 + t min ⁡ n y n w f T x n 即 w f T w t ≥ t min ⁡ n y n w f T x n 同 理 ， 对 2 式 求 错 位 ： 初 始 化 w 0 = 0 ∣ ∣ w 1 ∣ ∣ 2 ≤ ∣ ∣ w 0 ∣ ∣ 2 + max ⁡ n ∣ ∣ y n x n ∣ ∣ 2 ∣ ∣ w 2 ∣ ∣ 2 ≤ ∣ ∣ w 1 ∣ ∣ 2 + max ⁡ n ∣ ∣ y n x n ∣ ∣ 2 . . . ∣ ∣ w t ∣ ∣ 2 ≤ ∣ ∣ w t − 1 ∣ ∣ 2 + max ⁡ n ∣ ∣ y n x n ∣ ∣ 2 错 位 后 是 ： ∣ ∣ w t ∣ ∣ 2 ≤ ∣ ∣ w 0 ∣ ∣ 2 + t max ⁡ n ∣ ∣ y n x n ∣ ∣ 2 即 ∣ ∣ w t ∣ ∣ 2 ≤ t max ⁡ n ∣ ∣ y n x n ∣ ∣ 2 故 可 有 cos ⁡ θ ： cos ⁡ θ = w f T w t ∣ ∣ w f ∣ ∣ ∣ ∣ w t ∣ ∣ ≥ t min ⁡ n y n w f T x n ∣ ∣ w f ∣ ∣ max ⁡ n ∣ ∣ y n x n ∣ ∣ 2 因 为 y n ∈ { − 1 , 1 } 故 可 转 化 为 cos ⁡ θ ≥ t min ⁡ n y n w f T x n ∣ ∣ w f ∣ ∣ max ⁡ n ∣ ∣ x n ∣ ∣ 其 中 ， max ⁡ n ∣ ∣ x n ∣ ∣ 表 示 距 离 圆 点 最 远 的 点 的 距 离 R 而 min ⁡ n y n w f T x n ∣ ∣ w f ∣ ∣ 表 示 离 理 想 直 线 最 近 的 点 ( x n , y n ) 到 直 线 的 距 离 ρ 故 cos ⁡ θ ≥ t ρ R 很 明 显 ， 随 着 迭 代 次 数 t 的 增 加 ， cos ⁡ θ 的 下 界 逐 渐 增 加 ， 表 示 cos ⁡ θ 越 来 越 大 但 是 ， 由 于 cos ⁡ θ 本 身 具 有 上 界 1 ， 这 个 时 候 表 示 w t 与 w f 完 全 重 合 w_{t+1}=w_t+y_n(t)x_n(t)，(x_n(t),y_n(t))是一个错分点\\ 更接近代表着向量的内积增大\\ 即求证w_f^Tw_{t+1}\ge w_f^Tw_t\\ 代入有w_f^Tw_{t+1}=w_f^T(w_f+y_n(t)x_n(t))\\ =w_f^Tw_t+y_n(t)w_f^Tx_n(t)\\ 因为w_f是理想直线，，在线性可分的时候全部分类正确\\ 即y_n(t)与w_f^Tx_n(t)同符号\\ 即y_n(t)w_f^Tx_n(t)\ge 0\\ 故w_f^Tw_{t+1}\ge w_f^Tw_t+\min_ny_n(t)w_f^Tx_n(t)——1式\\ 其中虽然已知内积增大，但可能是夹角减小（即我们想要的靠近）或者是模增加\\ 现在考虑模长的改变，即||w_{t+1}||与||w_t||的关系\\ ||w_{t+1}||^2=||w_t+y_n(t)x_n(t)||^2\\ =||w_t||^2+2y_n(t)w_t^Tx_n(t)+||y_n(t)x_n(t)||^2\\ 因为对w_t而言，(x_n(t),y_n(t))是错分点\\ 故2y_n(t)w_t^Tx_n(t)\ge 0\\ 可有\\ ||w_{t+1}||^2\le ||w_t||^2+||y_n(t)x_n(t)||^2\\ 对第二项取极值可有\\ ||w_{t+1}||^2\le ||w_t||^2+\max_n ||y_n(t)x_n(t)||^2——2式\\ \max_n ||y_n(t)x_n(t)||^2表示变化上界\\ 现在可以考虑夹角\theta的\cos值\\ \cos\theta=\frac{w_f^Tw_t}{||w_f||||w_t||}\\ 所以需要考虑\cos\theta的上界或下界\\ 对1式求错位：初始化w_0=0\\ w_f^Tw_1\ge w_f^Tw_0+\min_ny_nw_f^Tx_n\\ w_f^Tw_2\ge w_f^Tw_1+\min_ny_nw_f^Tx_n\\ ...\\ w_f^Tw_t\ge w_f^Tw_{t-1}+\min_ny_nw_f^Tx_n\\ 错位后是：\\ w_f^Tw_t\ge w_f^Tw_0+t\min_ny_nw_f^Tx_n\\ 即 w_f^Tw_t\ge t\min_ny_nw_f^Tx_n\\ 同理，对2式求错位：初始化w_0=0\\ ||w_1||^2\le||w_0||^2+\max_n||y_nx_n||^2\\ ||w_2||^2\le||w_1||^2+\max_n||y_nx_n||^2\\ ...\\ ||w_t||^2\le||w_{t-1}||^2+\max_n||y_nx_n||^2\\ 错位后是：\\ ||w_t||^2\le||w_0||^2+t\max_n||y_nx_n||^2\\ 即||w_t||^2\le t\max_n||y_nx_n||^2\\ 故可有\cos\theta：\\ \cos\theta=\frac{w_f^Tw_t}{||w_f||||w_t||}\\ \ge \frac{\sqrt t\min_ny_nw_f^Tx_n}{||w_f||\sqrt{\max_n||y_nx_n||^2}}\\ 因为y_n\in\{-1,1\}\\ 故可转化为 \cos\theta\ge \frac{\sqrt t\min_ny_nw_f^Tx_n}{||w_f||\max_n||x_n||}\\ 其中，\max_n||x_n||表示距离圆点最远的点的距离R\\ 而 \frac{\min_ny_nw_f^Tx_n}{||w_f||}表示离理想直线最近的点(x_n,y_n)到直线的距离\rho\\ 故\cos \theta\ge \sqrt{t}\frac{\rho}{R}\\ 很明显，随着迭代次数t的增加，\cos\theta的下界逐渐增加，表示\cos\theta越来越大\\ 但是，由于\cos\theta本身具有上界1，这个时候表示w_t与w_f完全重合 wt+1​=wt​+yn​(t)xn​(t)，(xn​(t),yn​(t))是一个错分点更接近代表着向量的内积增大即求证wfT​wt+1​≥wfT​wt​代入有wfT​wt+1​=wfT​(wf​+yn​(t)xn​(t))=wfT​wt​+yn​(t)wfT​xn​(t)因为wf​是理想直线，，在线性可分的时候全部分类正确即yn​(t)与wfT​xn​(t)同符号即yn​(t)wfT​xn​(t)≥0故wfT​wt+1​≥wfT​wt​+nmin​yn​(t)wfT​xn​(t)——1式其中虽然已知内积增大，但可能是夹角减小（即我们想要的靠近）或者是模增加现在考虑模长的改变，即∣∣wt+1​∣∣与∣∣wt​∣∣的关系∣∣wt+1​∣∣2=∣∣wt​+yn​(t)xn​(t)∣∣2=∣∣wt​∣∣2+2yn​(t)wtT​xn​(t)+∣∣yn​(t)xn​(t)∣∣2因为对wt​而言，(xn​(t),yn​(t))是错分点故2yn​(t)wtT​xn​(t)≥0可有∣∣wt+1​∣∣2≤∣∣wt​∣∣2+∣∣yn​(t)xn​(t)∣∣2对第二项取极值可有∣∣wt+1​∣∣2≤∣∣wt​∣∣2+nmax​∣∣yn​(t)xn​(t)∣∣2——2式nmax​∣∣yn​(t)xn​(t)∣∣2表示变化上界现在可以考虑夹角θ的cos值cosθ=∣∣wf​∣∣∣∣wt​∣∣wfT​wt​​所以需要考虑cosθ的上界或下界对1式求错位：初始化w0​=0wfT​w1​≥wfT​w0​+nmin​yn​wfT​xn​wfT​w2​≥wfT​w1​+nmin​yn​wfT​xn​...wfT​wt​≥wfT​wt−1​+nmin​yn​wfT​xn​错位后是：wfT​wt​≥wfT​w0​+tnmin​yn​wfT​xn​即wfT​wt​≥tnmin​yn​wfT​xn​同理，对2式求错位：初始化w0​=0∣∣w1​∣∣2≤∣∣w0​∣∣2+nmax​∣∣yn​xn​∣∣2∣∣w2​∣∣2≤∣∣w1​∣∣2+nmax​∣∣yn​xn​∣∣2...∣∣wt​∣∣2≤∣∣wt−1​∣∣2+nmax​∣∣yn​xn​∣∣2错位后是：∣∣wt​∣∣2≤∣∣w0​∣∣2+tnmax​∣∣yn​xn​∣∣2即∣∣wt​∣∣2≤tnmax​∣∣yn​xn​∣∣2故可有cosθ：cosθ=∣∣wf​∣∣∣∣wt​∣∣wfT​wt​​≥∣∣wf​∣∣maxn​∣∣yn​xn​∣∣2 ​t ​minn​yn​wfT​xn​​因为yn​∈{−1,1}故可转化为cosθ≥∣∣wf​∣∣maxn​∣∣xn​∣∣t ​minn​yn​wfT​xn​​其中，nmax​∣∣xn​∣∣表示距离圆点最远的点的距离R而∣∣wf​∣∣minn​yn​wfT​xn​​表示离理想直线最近的点(xn​,yn​)到直线的距离ρ故cosθ≥t ​Rρ​很明显，随着迭代次数t的增加，cosθ的下界逐渐增加，表示cosθ越来越大但是，由于cosθ本身具有上界1，这个时候表示wt​与wf​完全重合
根据这个就可以得到PLA算法的迭代上界，即我们的Radios-Margin Bound定理
t ρ R ≤ 1 即 t ≤ ( R ρ ) 2 \sqrt t\frac{\rho}{R}\le1\\ 即t\le(\frac{R}{\rho})^2 t ​Rρ​≤1即t≤(ρR​)2
代码就不展示了，CSDN里有很多大佬。
至于POCKET算法，则是面对非线性分类的时候，当且仅当 w t + 1 w_{t+1} wt+1​分类的错误项比 w t w_t wt​分类的错误项少的时候，才会用 w t + 1 w_{t+1} wt+1​来代替 w t w_t wt​，然后人为设定一个最大迭代阈值即可。