動機
普通競爭學習把最符合目前觀測的原型拉近輸入。若預先分配太少原型,不同群必須共用代表;若太多,多個原型可能擠在同一群。即使算法只稱自己為無監督學習,預先決定原型數,也已是一項模型選擇。
對手懲罰競爭學習,簡稱 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 並核對兩個距離恆等式。)
先用舊位置決定角色。
解答 · 答案
一勝出,三是對手。新位置為 ,及 。平方距離分別是舊值一乘 ,以及舊值九乘 。若對手也用正學習符號,就變成另一條規則。
快速檢查
(某原型距固定輸入二,連續三步只當對手,反學習率 。求其距離,並說明結論的條件性。)
位移每次乘相同倍數。
解答 · 答案
距離為 。計算假設輸入固定、學習率固定,而且此原型三次皆為對手、沒有勝出。實際頻率與幾何每次都改變,所以必須檢查這種角色序列,不能單從遞推式推斷它一定發生。
快速檢查
(觀測為負一與一,原中心零。計算加入中心一的收益,並決定正懲罰在甚麼範圍接受出生。)
只有一個觀測得到更小最近距離。
解答 · 答案
原先兩殘差平方皆一。加中心一後,負一仍離零最近、平方距離一;正一殘差降零,因此 。嚴格政策在 接受, 拒絕,等於一時並列而不接受。進一步重擬合可以改善兩中心結果,再次顯示固定中心測試是充分測試,不是完整搜索。
快速檢查
(區分已分配數、有效數與真正刪除,並舉例說明刪去低累積勝出原型的風險。)
考慮罕見真實群或正在改變的分佈。
解答 · 答案
已分配數計所有儲存原型;有效數計通過已指定活動規則的原型,儲存不變時也可改變;真正刪除則移除參數,改變未來競爭。罕見但真實的子群可能一直很少勝出,新出現子群也沒有長期歷史。單按累積次數刪除,可能抹去有用表示。因此應報門檻與窗口,並以合適驗證檢查預測或聚類行為。