1. 簡介在線預測可以被看做一個在玩家（演算法）和環境之間的重複遊戲。假設 T 為遊戲的總輪數。那麼在每一輪 t(t=1,cdots,T) 上，在玩家和環境之間的這個遊戲可以直觀的表示為：環境：從問題庫中取一個問題玩家：根據環境提出的問題給出回答環境：根據玩家的回答產生一個損失 loss in mathcal{R} 。（對於玩家而言當然希望回答正確，損失越小越好）。然後環境把損失反饋給玩家。

    玩家：學習和記錄反饋。

    在這個重複遊戲中，玩家不斷根據環境的反饋進行學習。這樣在環境給出新問題時，根據歷史上學到的知識進行決策。下面看一個例子。1.1在線二分類遊戲在線二分類有很多應用，比如垃圾郵件分類。在這個應用中，玩家得到的問題是環境給出的郵件的一些特徵（feature）信息。然後玩家要回答（垃圾郵件or No）。根據上面的流程環境：給玩家一個郵件相關信息的特徵向量 x_t in mathcal{R}^n 玩家：根據環境提出的問題給出一個回答 ar{y_t} in {+1, -1} 環境：根據玩家的回答產生一個損失 ell_t = mathbf{1}_{ar{y}_t eq y_t} 。 y_t 為問題的答案。玩家：學習和記錄反饋。 那麼在 T 輪後，累計的損失為 sum_{t=1}^T ell_t 。現在考慮玩家使用假設類 mathcal{H} 中假設（比如二元分類器） h_t: mathcal{R}^n o {+1, -1} 。這個假設是一個將特徵向量 x_t in mathcal{R}^n 映射到二元集合 {+1, -1} 上的一個函數。

1.2 採用Hinge損失的在線二元線性分類器

考慮使用二元線性分類器 h_w: mathcal{R}^n o {+1, -1}

h_w(x)=sign(w cdot x)= left{ egin{array}{ll} +1, , if ;; w cdot x > 0 \ -1, , if ;; w cdot x <0 end{array} ight.

這個假設的唯一參數就是向量 w in mathcal{R}^n 。從幾何意義上來看，所有同 w 相垂直的向量構成了一個超平面 {x: w cdot x = 0} ,如下圖所示

圖1：超平面和半空間

數據x可能落入任意一個半空間 {x: w cdot x < 0} 和 {x: w cdot x >0} 之中。 |w cdot x| 可以被看作信心程度。

假設類 mathcal{H} 設為 mathcal{H}={h_w(x): w in mathcal{R}^n, |w|_2 leq 1} ，這是一個二元線性分類器構成的類。 mathbf{1}_{ar{y}_t eq y_t} 被稱作指示器損失或者0-1損失。常用的損失函數還有Hinge損失

l(w;(x_t, y_t))=max{0, 1-y_twcdot x_t}

Hinge函數在兩種情況下產生損失

(1) 分錯了 y_t w cdot x_t < 0

(2) 分對了但是信心不夠 0 leq y_twcdot x_t < 1

這個遊戲現在可以泛化唯一個在線凸優化問題(Online Convex Optimization， OCO)

2.在線凸優化

For t=1, cdots, T

(1)玩家選擇模型參數 w_t in mathcal{W} , 其中 mathcal{W} 是 mathcal{R}^n 上的凸集（凸組合下閉合的仿射空間的子集）

(2)環境選擇一個凸的損失函數 f_t: mathcal{W} o mathcal{R}

(3)玩家根據第t輪的問題做出回答產生損失 ell_t=f_t(w_t)=f_t(w_t;(x_t,y_t))

(4)玩家根據損失對模型進行反饋

假設: 玩家的模型w_1,cdots, w_T 只能去學習環境，但是環境可以惡意的定義 f_1, cdots, f_t （比如獲得玩家的決策演算法等）。那麼累計損失可以無限大。那麼如何評價分類或預測效果？

一個好的方案就是採用一個事先固定的最優假設的累計損失 :

mathop{min}limits_{w in mathcal{W}} sum_{t=1}^T f_t(w).

那麼為了選擇一個最優的固定假設，我們需要收集所有的 f_1, cdots, f_t ，然後運行一個離線的演算法。

那麼可以定義在真實累計損失和對於提前知道的固定假設的最小損失之間的差值定義為後悔之值(regret):

R(T)=sum_{t=1}^Tf_t(w_t) - mathop{min}limits_{w in mathcal{W}}sum_{t=1}^Tf_t(w).

(1)如果損失是線性增長的 R(T)=Omega(T) ,那麼玩家就沒有在學習。

(2)如果損失是次線性的 R(T)=o(T) ,那麼玩家在學習並且預測精度在提高。每一輪的損失隨著T的增大而趨近於0

frac{1}{T}(minlimits_{w in mathcal{W}} sum_{t=1}^T f_t(w)) o 0, T o infty.

(3) R(T)=O(sqrt{T})

reference:

CSE599s: Online Learning?

courses.cs.washington.edu


推薦閱讀：

相关文章