动机
普通竞争学习把最符合目前观测的原型拉近输入。若预先分配太少原型,不同群必须共用代表;若太多,多个原型可能挤在同一群。即使算法只称自己为无监督学习,预先决定原型数,也已是一项模型选择。
对手惩罚竞争学习,简称 RPCL,改变适应规则:胜者向输入学习,对手则被推开。其机制希望减少重复表示,让多余原型离开已有代表的数据区域。要理解这个想法,必须先写清竞争分数。原始频率敏感版本的对手,并不一定是欧氏(Euclid)距离第二近的原型。
本节先精确分析一步的几何,再区分较强的统计声明。之后另建一个以惩罚目标明确决定增删的程序。比较两者,可看清“边学边选”有不同意思:有效原型数改变、存储参数真的删除,以及一致估计未知母体结构,是三种不同要求。
定义
定义 7.1.1
(频率敏感竞争与原始 RPCL 一步)
取 个原型 及正的胜出计数 ,设 。输入 的分数为 。先以固定并列规则选最小分数的 ,再在 中选最小的 。若 ,更新
其他原型不动,再把胜者计数加一。两个指派及位移都使用更新前状态。
频率加权指派与相反方向的更新,已核对 Xu、Krzyzak 及 Oja 1993 年原论文第 III.A 节公式 (3a)–(3b)。原文使用累积胜出频率。此处把初始计数设为正,并以索引处理并列,是避免最初比值无定义的明确实现惯例,并非对原实验额外作声明。
常胜原型有较大乘数,必须更接近输入才能再次胜出。这不是后验概率,也不是混合权重估计;位移本身仍是欧氏方向。把分数直接换成未加权距离,是相关的对手惩罚变体,却不能不加说明便代入原规则。
定义 7.1.2
(已分配数与有效模型大小)
已分配数是实际存储的原型数 。有效数只有在指定活动准则后才有意义,例如固定评估窗口内,胜出比例达某阈值的原型数。远离样本的原型可仍被存储,却很少影响预测;真正删除是另一项操作,会影响以后的适应。
没有通用活动阈值。罕见但真实的群可有很少胜出次数;远处原型也可能因频率乘数低而偶尔胜出。累积一生的计数,对分布转变可能反应缓慢。改用窗口或指数遗忘会改变算法,必须另行说明。报告有效数时,应同时检查近期指派、目前几何与阈值,不能只给一个整数。
定理/命题
定理 7.1.3
(局部吸引与排斥的精确式)
一次 RPCL 中,若胜者与对手由旧状态选定,则
若同一固定输入下,某原型连续只当对手、从不胜出,且 固定,其位移在 步后乘 。这是条件式轨迹结论,不表示真实竞争会一直保持相同角色。
定理 7.1.4
(惩罚失真的结构接受条件)
对非空原型集合 ,定义
加入候选 的失真收益为
加入它严格降低 ,当且仅当 。固定其他中心,删除 的失真增加记为 ,则严格改善当且仅当 。之后作 Lloyd 最近指派及非空群均值更新,都不会增加 。
这是另外明确定义的惩罚程序,不是归于 RPCL 的公式。假设包括固定样本、平方欧氏失真及指定复杂度惩罚。若改高斯(Gauss)似然、流式数据分布或其他距离,就应重算每项结构变动。
证明思路或证明
证明
(一次对手更新的几何)
把新原型从 减去,得到 、。平方即得两个距离式。固定输入与角色时重复第二递推,得 。输入或对手身份一变,这条递推便不再适用。
冻结两个索引时,更新也可看成对局部带符号式 作单位步长梯度下降。但对手部分是负二次式,没有下界,而且每个输入之间索引与频率都改变。因此这个观察不提供实际学习过程的有界全局目标,也不是收敛证明。
证明透视
局部公式没有证明什么
胜者接近目前样本、对手远离目前样本,都由精确代数得到。对手最后变成冗余原型、被推向另一有用群,或扰乱某个边界,取决于后来输入与竞争。两个范数恒等式不能推出正确母体群数;要谈统计恢复,必须另设数据生成模型及相应定理。
证明
(增删接受测试为何降低指定目标)
记 。加入 后残差为 ,所以总失真恰降 ;惩罚增 ,目标差便是 。重复中心的收益零,不会在正惩罚下被接受。
删除时,逐点比较旧最近距离与剩余中心的最近距离,其非负增加总和为 。惩罚减 ,故目标差 。旧指派唯一时,只有属于被删中心的观测有贡献;直接比较所有最小值亦能处理并列。此定义不容许删掉最后一个中心。
固定指派时,质心恒等式保证每群均值最小化平方距离;固定中心时,最近指派逐点最小化残差。这些 Lloyd 步不增失真。群数保持不变;若明确移除空群,惩罚亦下降。因此一项严格改善的结构变动,经这些重新拟合后仍严格改善。
一个具体程序可从已拟合的非空分割开始:以样本位置作出生候选,并测试现有中心的删除;只接受上述严格改善,重新以确定并列规则拟合,清除空群,再重复至所有被测候选都不通过。它不需要已知母体群数,但输出仍依赖初始化、候选集合及 。
在确定的同值选择及群非空的假设下,每次 Lloyd 重新拟合本身也会终止。样本指派只有有限多种;若均值更新改变某个中心,该非空群的平方误差严格降低。若一轮目标值相同,每个中心因而保持不变,确定的重新指派便重复同一指派并停止。故既不会有非平凡循环,也不会在有限多个完成状态间无限严格下降。
若每次完成拟合后,非空群中心都换成其均值,固定样本只有有限多种分割,也就只有有限多个完成状态的目标值。严格下降排除循环,故接受的结构变动有限步终止。结论只是在已测操作下的局部停止。固定中心的删除测试不通过,不能排除删除后大幅重新拟合才有改善;更广的合并或分裂候选可找到它漏掉的解。
例题详解
例题 7.1.5
(胜者、对手与不动原型)
一维原型 有相同正计数,输入为一。分数顺序与平方距离 相同,故零胜出、三是对手。取 、,新原型为 。胜者距离由一变 ,对手由二变 。若旧计数 ,新频率为 ;它们只影响下一次竞争,不会倒过来改本步角色。
例题 7.1.6
(频率竞争可以提高普通最近失真)
取 、、,频率为 。分数为 与 ,较远的原型一胜出。用 、,新中心为 与 。普通最近中心平方误差由一增至 。胜者改善了自身距离,却排斥了原先最近的原型,所以不能移植 k-means 的下降定理。
例题 7.1.7
(由明确惩罚支持一次出生)
数据为 ,一个均值中心五的失真为 。 时分数 109。提出中心十,只有九及十一改善,收益分别 与 ,故 。出生后分数 ;重新指派与更新均值,得中心零及十,失真四,分数十四。若删掉十而固定零,失真增加 ,所以拒绝。算术支持此惩罚与操作下的结构,没有宣称二是普遍真实群数。
常见错误
反例模式
拒绝固定中心删除不是全局证书
沿用四点与中心零、十,改取 。两中心分数 。固定另一中心的删除会增失真 200,大于节省 150,所以简单测试拒绝。但重新拟合的单中心五分数为 ,其实更好。测试对固定中心完全精确,也是重新拟合后改善的充分条件,却不是所有有利合并的必要条件。较强搜索可以直接评分完整重拟合候选。
常见错误
(自动化仍有需要说明的选择)
RPCL 有学习率与初始原型分配,增删程序有复杂度价格与候选集合,有效数则有活动阈值及窗口。它们可自动化部分工作,却不能省去任务定义与避免测试泄漏的调参程序。远离其他数据的离群值,可能在平方误差上支持新中心,却只是噪声,不是新母体群。
思想史
原始问题是过多的表示单位
Xu、Krzyzak 与 Oja 的 1993 年论文研究单位分配不合适的竞争学习,并在胜者学习之外加入较小的对手反学习步。原文区分备用单位与代表数据的单位,因此适合分开检查分配数与活动数;这不等于任意样本下的一般一致性定理。
总结
原始频率敏感 RPCL 以加权距离同时排胜者及对手,再吸引前者、排斥后者。局部公式解释机制,也说明普通失真下降不可假定。另一个惩罚式增删程序使结构接受可逐项核对,但其单调有限搜索只保证所指定操作与选择下的局部结果。
练习
快速检查
(输入零、原型一及三、频率相同,胜者率 、对手率 ,做一步 RPCL 并核对两个距离恒等式。)
先用旧位置决定角色。
解答 · 答案
一胜出,三是对手。新位置为 ,及 。平方距离分别是旧值一乘 ,以及旧值九乘 。若对手也用正学习符号,就变成另一条规则。
快速检查
(某原型距固定输入二,连续三步只当对手,反学习率 。求其距离,并说明结论的条件性。)
位移每次乘相同倍数。
解答 · 答案
距离为 。计算假设输入固定、学习率固定,而且此原型三次皆为对手、没有胜出。实际频率与几何每次都改变,所以必须检查这种角色序列,不能单从递推式推断它一定发生。
快速检查
(观测为负一与一,原中心零。计算加入中心一的收益,并决定正惩罚在什么范围接受出生。)
只有一个观测得到更小最近距离。
解答 · 答案
原先两残差平方皆一。加中心一后,负一仍离零最近、平方距离一;正一残差降零,因此 。严格策略在 接受, 拒绝,等于一时并列而不接受。进一步重拟合可以改善两中心结果,再次显示固定中心测试是充分测试,不是完整搜索。
快速检查
(区分已分配数、有效数与真正删除,并举例说明删去低累积胜出原型的风险。)
考虑罕见真实群或正在改变的分布。
解答 · 答案
已分配数计所有存储原型;有效数计通过已指定活动规则的原型,存储不变时也可改变;真正删除则移除参数,改变未来竞争。罕见但真实的子群可能一直很少胜出,新出现子群也没有长期历史。单按累积次数删除,可能抹去有用表示。因此应报阈值与窗口,并以合适验证检查预测或聚类行为。