《生活中的算法 (Algorithms to live by)》第二章: 探索/利用
生活中總會碰到，需要決定是探索 (Explore)還是利用 (Exploit) 的場景。所謂探索即不固守現(xiàn)有信息，對未知事物進行探索，獲得關(guān)于它們的新信息；而利用則是對自己已了解的事物進行充分利用，獲得最大好處。
這樣的場景很多，比如說我喜歡看書，所以喜歡收集好書。長期下來，就堆積了很多書看不完。同時，因為惦記這些看不完的書，導(dǎo)致對一些經(jīng)典書沒有進行精讀。這算是探索過度吧，結(jié)果就是沒把時間放在重要的東西上去，因此真正的收獲反而少了。
另一方面，自進入自然語言處理(NLP)領(lǐng)域以來，起初還天天探索新知識技術(shù)。但之后因為需要集中精力做課題，就慢慢把精力放在很窄的范圍了，每天就研究那些。但同時，很多值得研究的新技術(shù)不斷出現(xiàn)，比如說生成對抗性網(wǎng)絡(luò) (GAN) 還有強化學(xué)習(xí) (RL) 在NLP領(lǐng)域的成功應(yīng)用。而自己對這些卻不是很了解。在研究遇到困難，看到其他人在這些方向取得成果時，有時也會想當(dāng)初要是研究那邊課題就好了，有點后悔 (Regret).
如此可見，探索/利用問題在日常生活中是很常見的。而這一章便是講如何利用探索/發(fā)現(xiàn)算法，來對此類問題作出決定。
基本問題
首先，這類問題最基本的原型是“多老虎機問題 (Multi-armed bandit problem)”。假設(shè)進入一個賭場，這里有很多臺老虎機，設(shè)置了不同的勝率，但你并不知道。自然而然你為了最大化自己的收益，就需要到處探索找出勝率最高的機器，然后利用它來獲得最大收益。
這個問題里處于哪個時間段 (interval)對你決定的影響非常大，比如說剛進入賭場時，自然是會優(yōu)先進行探索。而當(dāng)快要離開時，想在剩下的時間帶走更多的錢，那就會優(yōu)先利用，只玩勝率高的機器。
最初的策略：贏了繼續(xù)，輸了就換
第一個有名的策略是 Herbert Robbin 提出來的：贏了繼續(xù)，輸了就換。他考慮的是只有兩臺機器的情況，也就是說先隨便找臺機器玩，如果贏了就繼續(xù)在這臺上玩，輸了換機器，贏了繼續(xù)，輸了就換...
雖然看上去很簡單，但Robbin證明了這個策略要比單純隨機玩更好些。然而也因為過于簡單，存在一個大問題。這個問題便是”輸了就換“并不合理，想想如果你在一臺機器上連續(xù)玩了十把都贏了，而只是突然輸了一把，你會去換嗎？作為一個理性人都不會的，而會繼續(xù)玩，直到覺得這臺機器的勝率其實小于某個預(yù)期。
第二個策略：Gittins 指數(shù)
在數(shù)學(xué)中總會出現(xiàn)一通百通的例子，對于一個問題的解決就是對一系列問題的解決。比如第二個策略的Gittins指數(shù)，實際上是Gittins在制藥公司設(shè)計實驗時提出來的。
制藥公司做實驗和多老虎機問題相似的地方在于，對于一個藥，他們需要探索每個成分對病情的效果，使得在最少的試驗次數(shù)下獲得足夠多的值得信任的數(shù)據(jù)，找出效果最好的成分。這里每個成分就相當(dāng)于一臺老虎機。
Gittins與其他研究者不同的是，他假設(shè)最大化的不是在一段時間內(nèi)的收益，而是無限時間下單次收益會隨著時間變長而打折扣的總收益。這個假設(shè)也很合理，比如說你就會更關(guān)心今晚吃什么，而不是明天吃什么。
Gittins對此提出了一個策略，就是利用Gittins指數(shù)（也叫動態(tài)分配指數(shù)）來輔助決策。具體指數(shù)如下表，下表為下次收益為前一次90%的情況。
使用時，先給每臺機器分配一個Gittins指數(shù)，然后挑出指數(shù)最大的機器玩，玩的時候根據(jù)表格更新指數(shù)，然后繼續(xù)挑最大的，更新...
Gittins指數(shù)的一個顯著特點是，給沒有探索的機器也分配了高于期望值0.5的分數(shù)，也就是說鼓勵探索。同時，Gittins指數(shù)的表格讓解決方法非常簡單直觀。
但Gittins指數(shù)方法也有很多缺點，首先是它的假設(shè)，第二沒有考慮換機器時產(chǎn)生的成本，最后也是最重要的，在日常生活中很難使用，很難一下子就計算出一張表格，即使帶上表格也會因為條件改變表格也得變。
樂觀的上置信界限算法
如果因為Gittins指數(shù)太復(fù)雜，或者你面對的問題并不滿足其假設(shè)，那么你就可以試著把注意力放在后悔(Regret)上面，最小化你的后悔，而不是最大化收益。
人最容易后悔的情況是什么，就是之前自己沒有鼓起勇氣去選擇做某事，之后發(fā)現(xiàn)別人做這件事成功了。比如說，不敢搭訕一位女生，結(jié)果發(fā)現(xiàn)別人搭訕成功了，還交往起來了，心中肯定就會特別后悔。這里之所以出現(xiàn)這種情況，是因為你在擔(dān)心最壞情況（被拒絕，男友出現(xiàn)被打），也就是下置信界限。而由Robbins還有Lai提出的上置信界限算法則認為我們考慮最好的情況會更好。
首先什么是置信界限(Confidence Bound)，即變動的可能性。比如說，有一臺從沒探索過的老虎機，那么它就具有無限的可能性，可能勝率為0，也可能為100%。此時，置信界限就非常大，而隨著探索次數(shù)增加，對老虎機的勝率慢慢心里有了底，此時置信界限就會慢慢收斂變小。再如小說里什么“莫欺少年窮”，就表示年輕人置信界限大，未來可能分分鐘打你臉。
在現(xiàn)實生活中表示置信界限時，可以用如折線圖中的誤差條 (Error bar)來表示。
上置信界限算法策略，就是在所有選擇中挑選上置信界限最大的一個選項。如果轉(zhuǎn)化成現(xiàn)實策略，那就是始終相信一件事可能的最好結(jié)果，也就是面對不確定時，始終樂觀往最好想，然后挑選最好中的最好。
和Gittins指數(shù)方法相似，上置信界限算法也給沒有探索的選項比期望值高的分數(shù)，這樣會鼓勵對未知選項進行更多的探索。而與Gittins指數(shù)不同的是，上置信界限更加容易計算一些。
至于從這里學(xué)到了什么，那就是，下次男生看到美女時就想著，最好的情況她可能成為你的女朋友哦，然后勇敢搭訕。
更多的例子：A/B測試，臨床試驗
類似多老虎機問題的問題，現(xiàn)實中有很多，其中有些非常很重要，有時是一個國家的命運或一個人的生命。
比如說奧巴馬選舉時，為了進行有效募捐，他的“新媒體分析”團利用A/B測試（類似贏了繼續(xù)策略）對各個選項對進行了對比和探索，之后選擇最好的組合。結(jié)果成功募捐到了5700萬的額外捐款。
還有醫(yī)學(xué)臨床實驗，對比兩個療法的效果，也和多老虎機問題類似。如果能夠利用好的算法來處理此類問題，那么就可以避免無謂的死亡。這里舉了ECMO（葉克膜）療法的例子，因為不合理的實驗結(jié)果導(dǎo)致了過多孩子的犧牲。
多變的世界
現(xiàn)實生活往往很多問題要比多老虎機問題更加復(fù)雜，因為世界是多變的。就好像這些老虎機隨著時間，勝率也在變化，之前探索的結(jié)論現(xiàn)在可能以及沒用了。樓下理發(fā)店的Kevin老師，進修完之后，說不定已經(jīng)成了一流理發(fā)師。
多變的世界給了我們一個啟示，要多進行探索，即使是之前探索過認為是不好的選項，說不定已經(jīng)變成好選項。
但是，對于這個多變問題，現(xiàn)在還沒有進行有效解決的算法，而且未來可能也不會有了。
那么既然這樣，之前說的算法就都沒用了咯，也不是?，F(xiàn)實中很多東西很大程度上還是符合上面的那些假設(shè)，不然也不會得到實際應(yīng)用。
其實上面這些算法最重要的并不是告訴我們怎么解決問題，而是提供了一個看待人生的新視角：探索與利用的取舍，時間段的重要性，未知的重要性，最小化后悔...
通過這個新的視角我們才能更合理地做出可能影響一生的決定。
怎么過一個沒有遺憾的人生
回到主題，怎么過一個沒有遺憾的人生？
通過閱讀本章我認為：在年輕時，以一種樂觀積極的態(tài)度來對未知選項進行探索，通過長時間的探索發(fā)現(xiàn)好的選項，當(dāng)?shù)搅艘欢挲g則開始主要注重于利用已知的好選項。當(dāng)然，因為多變世界的原因，還是要對已有的這些選項進行一定的重新探索。
