2.3　探索與利用問題
探索（exploration）與利用（exploitation）的應(yīng)用很廣，從資金分配到研究自動駕駛汽車項目都在使用，但它最初也是源于賭博問題。該問題的經(jīng)典形式是一個多臂賭博機（老虎機）問題，即假設(shè)有一個或多個手臂的賭博機，按次序以未知概率來拉動每個手臂，以此來表示獨立同分布的回報。在這種簡化模型中不斷獨立地重復(fù)。假設(shè)多個手臂間的回報是獨立的。其目標(biāo)是最大化回報（比如贏錢的金額），同時還要最小化學(xué)習(xí)成本（即在小于最優(yōu)獲勝率的情況下拉動手臂的次數(shù)）。假設(shè)已經(jīng)給定了一個手臂選擇策略，顯然需要在尋找一個能得到最優(yōu)回報的手臂與利用已知最好手臂之間做出權(quán)衡。

其中Si是N次試驗中選擇的第i個臂。多臂賭博機問題在20世紀(jì)30年代被廣泛研究，而在本世紀(jì)初，隨著金融和互聯(lián)網(wǎng)廣告技術(shù)領(lǐng)域的出現(xiàn)，它再次受到關(guān)注。通常由于問題的隨機性，使pseudo-regret的期望界好于N的平方根。pseudo-regret可以控制到以log N為界（Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems by Sebastien Bubeck and Nicolo Cesa-Bianchi，http://arxiv.org/pdf/1204.5721.pdf）。
在實踐中最常用的策略是策略，這種策略選擇最優(yōu)的手臂的概率是（1―），而選擇另一個手臂概率為。這種方法可能會在那些根本不帶來回報的手臂上花費大量的資源。UCB策略優(yōu)化了策略，通過預(yù)估最大回報的手臂，然后再加上回報估計的某些標(biāo)準(zhǔn)偏差。這個方法需要在每一輪中再次計算最佳手臂，并且需要近似估計均值和標(biāo)準(zhǔn)偏差。另外，UCB必須在每輪中重新計算估計值，這可能會帶來擴展性問題。
最后來介紹Thompson采樣策略。它使用一個固定的隨機采樣，該采樣服從-伯努利后驗估計，并且賦給下一個能給出最小期望后悔（regret）的手臂。這種數(shù)據(jù)可以避免參數(shù)重新計算。盡管需要假設(shè)具體的數(shù)，但下圖仍對這些模型的性能進行了有效比較：

圖2-4　當(dāng)K＝5時，單臂老虎機和不同策略的情形下，對采用不同研究-利用策略的模擬結(jié)果
圖2-4顯示了不同策略的仿真結(jié)果（http://engineering.richrelevance.com/recommenda-tions-thompson-sampling）。隨機策略僅僅是隨機地分配手臂，對應(yīng)于純粹的探索（explora-tion）模式。樸素策略是隨機達到特定的閾值，再轉(zhuǎn)成利用（exploitation）模式。Upper Confidence Bound（UCB）模式使用95%的置信區(qū)間，而UCB1是UCB的修改版，它考慮了分布的對數(shù)正態(tài)性。最后是Thompson策略，它通過實際的后驗分布給出一個隨機抽樣來優(yōu)化后悔值。
探索和利用模型對初始條件和異常值非常敏感，特別是在低響應(yīng)的情形下。這已經(jīng)在基本卡死的臂上進行過了大量的試驗。
另一種增強的策略是基于額外的信息（如位置）來估計更好的先驗，或者根據(jù)這些額外的信息限制手臂集，以便探索K。但這些會涉及更專業(yè)的領(lǐng)域（如個性化或在線廣告）。

總結(jié)

以上是生活随笔為你收集整理的《Scala机器学习》一一2.3　探索与利用问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。