Online learning — introduction (2)

Online learning，機器學習 2 分

本篇接續《Online learning — introduction》，我們給出一個 online learning 十分常見的架構，以及從它衍伸出來的 regret 的定義做更充分的討論。

Expert Advice

在 introduction 中有提到，面對 online learning 的問題，我們在乎的通常是 regret ，也就是跟「後見之明」比起來希望不要太差。但在 online learning 中，我們早已脫離了「有一個最好的 h\in \mathcal{H}  」這種後見之明了，也就是說，並不一定真的有一個什麼 hypothesis 可以適用於所有資料，頂多只能說「有一個決定策略的人」。這兩者個差別是上面的 h\in \mathcal{H} 是跟時間無關的函數，而「決定策略的人」可以隨時間改變自己做決定的心意。因此在 online learning 中，更常討論另一種設定：專家意見﹝Prediction with Expert Advice﹞，以下正式來介紹。

專家意見 Expert advice

雖然在 online learning 一開始，玩家對問題一竅不通，但幸運的是現在玩家身邊有 K 個專家願意為他做預測，不過究竟哪個專家才是最厲害的也不知道。無論如何，現在的目標是玩家看能不能有一個策略，使得他最終的獲利﹝reward﹞跟最厲害的專家相去不遠。前句的『最終』，在 online learning ，大家約定成俗就是經過 T 時間後的總獲利狀況。這裡先介紹最普遍的『專家意見』，當然裡面的每個要素都可以有很多種自然的變形，但這之後遇到了再提。準確來說：

玩家身邊有 K 個專家：[K]:=\{1,2,\cdots,K\}，（他們在每個時間 t\in [T] 都會給出意見  \mathbf{x}_t\in \mathcal{X}\subset \mathbb{R}^K，其中 x_t[i] 表示第 i 個專家的意見。）玩家每一回合都選擇相信一個專家 I_t\in \{1,2,\cdots K\}，而環境也（根據專家在當回合的意見）選擇了這回合的 loss vector \ell_t\in [0,1]^K，\ell_t[i] 代表第 i 個專家在第 t 回合收到的失誤（loss），其中因為玩家選擇第 I_t 個專家，因此 \ell_t[I_t] 也是玩家這回合的失誤。玩家的目標是最小化 regret

\mbox{regret}:=\sum\limits_{t=1}^T \ell_t[I_t]-\min_i\ell_t[i] -- (1)

玩家在做選擇的時候，只知道從 1\sim t-1 步環境給專家們的回饋，以及專家們從 1\sim t 步的意見。

這裡有一些東西需要補充。上面有講到獲利（reward），還有失誤（loss），在文獻中兩種都會出現，但這其實很容易處理，跟失誤相反，獲利是越高越好，因此 regret 就會訂成

\mbox{regret}:=\sum\limits_{t=1}^T\max_i\ell_t[i]- \ell_t[I_t]

這樣寫也是因為 regret 約定成俗就是一個非負實數，不過用兩種方式得出來的 regret 是一樣的。通常通常，在大部分的情境看到的都是 loss，除了 stochastic setting，當初在發展這方面的研究時，用的就是獲利，因此現在很多時候還沿用此習慣。

第二，上面有兩個打（）的部分，在很多變形的設定，這些並不一定會被特別寫出來。第一個（）是因為有時候是不一定有這個東西，有時候是有沒有都無所謂。無所謂是因為玩家在做決定時，就只知道 1\sim t-1 的真正狀況，而第 t 步專家的意見，因為環境還沒公佈答案，也不知道這個意見的可信度多少，因此最終玩家還是只能從前 t-1 的結果判斷這回合到底應該聽哪個專家的。第二個（）牽涉到這個環境到底會不會『針對』這些專家。如果文章說環境是 oblivious 的，那就是假設環境不會針對專家做調整，也就是 loss \ell(t,k), \mbox{where } t\in [T], k\in [K] 只跟『時間』和『專家』有關，而跟『專家的意見 x 』無關。你可以把它想成是， loss 是遊戲開始前就決定好的，只是還沒公佈而已，當玩家玩了以後才會公布。但如果文章說環境是 non-oblivious 的，那就意味著第 t 回合的 loss \ell(t,k,x) 會根據專家的預測決定，這其實就是 online learning 的最壞狀況（worst-case）了。不過在 online learning 領域，學者給出的 regret upper bound 其實都已經包含這種狀況，也就是說當你在設計演算法，然後進行 regret 分析的時候，也必須把最糟的狀況考慮進去。

Regret

regret 看似很單純，但其實也有值得著墨的地方。現在採用失誤（loss）的形式，並把 (1) 寫成

\mbox{regret}:=\min_i\sum\limits_{t=1}^T (\ell_t[I_t]-\ell_t[i]) -- (2)

(1) 跟 (2) 是一樣的，只是寫成 (2) 比較方便接下來的討論。通常玩家的策略會有隨機的因素在裡頭，而有時環境也有一些隨機性，因此我們不太會直接說 regret 是多少，而是會去問 expected regret bound 或是 high probability bound。現在說的 expected regret 其實是比較廣義的，就是要考慮所有 random bit 加權的情況，但它其實還可以再細分成兩種，分別對應到 adversarial setting 和 stochastic setting 常用的 regret。

在 adversarial setting 下常用 expected regret ，它定義成

\mathbb{E}\left[Reg_T\right]:=\mathbb{E}\left[\min_i\sum\limits_{t=1}^T (\ell_t[I_t]-\ell_t[i])\right]=\mathbb{E}\left[\sum\limits_{t=1}^T\left(\ell_t[I_t]-\ell_t[i^*_T]\right)\right]

其中 i^*_T 就是那個在 T 回合中 total loss 是最小的專家；另外期望值是對玩家和環境所有的 randomness 取的。在 stochastic setting 下，每個專家的 loss 是出自於某個未知的 distribution ，distribution i 的 mean 寫成 \mu_i，而\mu^*:=\min_i\mu_i。在這裡大家常考慮 pseudo regret ，定義成

\overline{Reg_T}:=\min_i\mathbb{E}\left[\sum\limits_{t=1}^T\left(\ell_t[I_t]-\ell_t[i]\right)\right]=\mathbb{E}\left[\sum\limits_{t=1}^T\left(\ell_t[I_t]-\ell_t[i^*]\right)\right]

其中 i^* 是對應到 mean 是 $\mu^*$ 的那個專家。這裡的 i^* 跟 i^*_T 可能是不一樣的。以結論來說，\overline{Reg_T}\leq \mathbb{E}\left[Reg_T\right]，pseudo regret 比較弱，但很多時候在 stochastic setting 大家只會做 pseudo regret。這兩種定義差在哪裡呢？expected regret 的定義中，玩家的比較對象是已經固定了一組 random bit 後，『真正在這 T 步之內 total loss 最小的專家』。或是可以看成，在期望值的 [ ] 裡面，其實那些 randomness 都已經確定了，而在外面取期望值只是看在不同組 random bit 下，把 regret 做加權平均。但是 pseudo regret 的定義中，玩家的比較對象，是『mean 最小』的專家。但是 mean 最小的玩家，在這 T 步內並不一定是 total loss 最小的專家。因此知道 \overline{Reg_T}\leq \mathbb{E}\left[Reg_T\right]。

大家常常又會把 pseudo regret 繼續改寫成

=\sum\limits_{t=1}^T\mathbb{E}\left[\mu_{I_t}-\mu^*\right]=\sum\limits_{t=1}^T\sum\limits_i\left[\mu_i-\mu^*\right]\mathbb{P}\left[I_t=i\right]=\sum\limits_{i}\left[\mu_i-\mu^*\right]\mathbb{E}\left[N_T(i)\right]

其中 N_T(i) 表示在 T 時間內，專家 i 總共被選擇幾次。這樣寫有什麼好處，可以看到 \left[\mu_i-\mu^*\right] 其實是個 constant，雖然玩家不知道，但是每個專家的 mean 早就固定了。所以剩下的任務就是去 upper bound 每個專家平均而言會被選擇幾次。

如果希望 pseudo regret 很低，那意味著那些『不好的』專家不能被選擇太多次，而要盡量選擇那個最好的專家，因為他的 mean 正是 \mu^*。很多很多時候，作者在寫證明的時候，不會把 pseudo regret 的推演寫的太詳細，而是直接說明他如何處理每個專家平均而言會被選擇幾次，就結束證明了。

Reference

  1. Bubeck 跟 Cesa-Bianchi 寫的 “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems"，在 Introduction 中寫的蠻清楚的。
  2. Shai Shalev-Shwartz 的 “Online Learning and Online Convex Optimization" .
  3. V.Vovk 的 “A game of prediction with expert advice".

 

發表者：turtleang

已發表

發表留言