與最佳固定專家比較
在線預測中,學習器須在看到當前損失前行動。專家會犯錯,因此一次表現不佳便永久淘汰可能過於嚴苛。指數權重逐步降低高損失專家的影響,並把學習器總損失與事後選出的最佳單一專家比較。
固定 個專家及 輪。第 輪專家 的損失為 。以下保證把整個損失序列視為獨立於學習器隨機抽樣而預先固定。在全資訊設定下,行動之後學習器觀察每個專家的損失,而非只觀察抽中專家的損失。損失不必互相獨立,也不必來自統計分布。
定義 5.3.1
(指數權重)
初始化 ,選擇學習率 。每輪開始時計算
定義 5.3.2
(相對最佳固定專家的期望遺憾)
學習器在看見本輪損失前按 抽取一個專家,待損失揭示後更新所有權重。對固定損失序列, 是過往損失的確定性函數,所以本輪期望損失為 。相對最佳固定專家的期望遺憾為
遺憾可以為負;以下不等式是上界。
常見錯誤
(與每輪最佳專家比較)
基準 每輪選不同的專家,它永不大於 ,卻可以小得多。取兩輪損失 和 ,前者等於 ,而每個固定專家都損失 。下面的定理針對的是後一個基準,即全程只用一個專家。
勢能計算
定理 5.3.3
(指數權重的遺憾界)
設損失 預先固定,且 。則對每個固定專家 ,
特別地,若預先知道 並取 ,相對最佳固定專家的期望遺憾至多為 ;固定 時,平均遺憾隨 增大而趨向零。
證明
(以弦界為基礎的勢能論證)
對 , 的凸性使其圖像不高於連接兩個端點值的弦:
因此利用 時 ,得到
由於 且 ,對數有定義。另一方面,任意固定專家 的最終權重是 ,故 至少為該權重。把這個下界與求和後的上界及 結合,得到
對 ,,因此對 有 。由於 ,代入並移項先得 。再用 ,得到對每個固定專家 均成立的上界
證明透視
各項假設在哪裏使用
證明用到三個要素,各用一次。 的凸性加上取值範圍 給出弦界,把混合量 化為只依賴期望損失 的式子;損失超出 時弦不等式不成立。全資訊用在更新每一個權重時,使 依賴全部損失。關鍵一步是勢能 :它的增量裂項相消為 ,上界來自學習器的損失,下界來自單個專家的權重,其餘各項都被捨去。由於 是任意的,這個界對所有固定專家同時成立,最佳專家事後才選出。最後一步把 換成 , 這一項就來自這裏。
這個弦界論證提供有效上界,並不聲稱常數最優。這是加性的期望損失比較:若所有專家表現都差,它不表示絕對損失小;它也不是單次隨機執行的高概率保證。
反例模式
大於一的損失
人們容易以為,對任何有界損失都可以沿用同樣的常數。取 、、,損失向量為 。上界給出 。但 ,所以 ,而最佳專家的損失為 ,遺憾是 。弦不等式在 時不成立,因為 。補救方法是重新縮放:若損失落在 ,對 應用定理,遺憾上界便乘以 。
例子
例題 5.3.4
(三個專家的兩輪)
取 。第一輪損失向量為 ,第二輪為 。初始權重都是一,所以第一輪期望損失為 。第一輪後權重為 ,下一輪分布為 。第二輪期望損失為 ,總期望損失為 。三個固定專家的損失為 ,最佳者損失零,因此期望遺憾為 。第二輪更新後權重是 。
例題 5.3.5
(調整學習率)
取 、。則 ,而 、。上界的兩項相等,這正是這個取法使 最小的原因。保證為 :一百輪內,期望總損失比最佳專家至多多出約 ,即平均每輪約 。
例題 5.3.6
(完全相同的專家)
設 ,且每輪 。兩個權重每輪都乘以 ,因此對所有 都有 、,相對任一專家的遺憾為 。上界 在此遠非緊的,因為它是對所有損失序列的最壞情況。
常見錯誤
(期望損失不等於單次執行的損失)
單次實際執行可能不同於 ,因為學習器會抽取專家。上述計算對這些抽樣取平均,專家損失序列則保持固定。例如,若學習器兩輪都抽中第二個專家(概率為 ),實際損失是 ,而不是 。
保證的界限
全資訊假設很重要:若只揭示抽中專家的損失,便不能按原式更新。多臂賭博機式回饋需要不同的估計量與分析。同樣,所選 使用了時域 ;未知時域的方法需要自己的調度或重啟分析。與分布無關的序列上界,本身並不表示在不斷改變的環境下未來預測風險如何。
練習
快速檢查
(取 、,某輪損失為 。給出初始分布、期望損失及更新後權重。)
由 開始。
解答 · 答案
初始分布為 ,期望損失為 。權重變為 。
快速檢查
(為何勢能證明能與每個固定專家比較,即使最佳專家要到所有輪次後才確定?)
論證中的專家 是任意的。
解答 · 答案
對每個專家 , 的下界都成立,所以遺憾上界對所有固定專家同時成立。算法無須知道誰最佳;對 取最小值只發生在分析中。
快速檢查
(為何上述更新需要完整回饋?若只觀察抽中專家的損失,哪些權重無法更新?)
留意因子 。
解答 · 答案
更新要對每個 把 乘以 。若只觀察到抽中專家的損失,其他專家的因子便未知,它們的權重無法更新。
練習 5.3.7
(證明對 及 ,。)
基礎證明
解答(3)
- 1
把 寫成兩個端點的凸組合
,權重 與 都在 內。
- 2
應用凸性
由於 是凸函數,。
依據: 函數 的二階導數 。
- 3
化簡右邊
∎,正是所要的上界。