[閱讀筆記] Algorithms to Live By - 開發與善用 (Explore / Exploit)

 開發與善用 (Explore / Exploit) - 嘗試新歡？還是固守舊愛？

1. 最佳停止問題的權威教科書一開頭就寫道：「最佳停止理論探討選擇適當時機採取特定行動的問題。」我們很難想出比這個更精確的言詞來描述人的境況。例如，我們決定買賣股票的時機、決定打開一瓶留給特殊場合的紅酒的適當時機、打擾某人的適當時機、以及接吻的適當時機。

2. 直覺上我們視為理性的決策方式，是毫無遺漏地列出各種選項，小心翼翼地加以權衡，最後選出一個最好的；然而，實際上，當時間不斷流逝，決策 (廣義的說是思考) 過程最重要的面相其實只有一個，就是何時該拿定主意。

3. 我們在日常生活中，常遇到抉擇。原本只是想放鬆一下，但是想到要做抉擇，就又沒那麼輕鬆了。生活就是在創新和傳統、最新和最棒、冒險和堅持舊愛之間取得平衡。這正如找房子時，應按兵不動或採取行動的兩難局面一樣，真正的問題是：平衡點到底在哪？

	選擇一	選擇二
去哪吃晚餐？	去最喜歡的義大利餐廳？	去剛開幕的泰國餐館？
找誰一起吃飯？	找最好的朋友去？	找想進一步認識的普通朋友？
點餐	點老樣子？	點新菜色？

4. 開發與善用的權衡 (explore / exploit tradeoff)：了解開發與善用後，不只有助於更正確決定上哪吃飯或聽什麼音樂，還能幫助我們了解應該如何隨時間而改變目標，並且知道合理的行動多半未必會選擇最好的目標。在權衡新事物和舊愛時，最重要的是我們打算在上面花多少時間？

	開發 (explore)	善用 (exploit)
電腦領域的定義	蒐集資料	運用現有資訊取得已知的良好結果
特質	探索與發現新喜好的價值會隨時間而逐漸降低，因為我們體會它的機會越來越少。例如，你在阿姆斯特丹最後一晚到一家迷人的咖啡廳喝咖啡，日後再也沒機會光顧。	善用的價值會隨時間而逐漸提高，例如，今天你最喜歡的咖啡廳，跟你上個月的體驗差不多讚。
賭場的應用	如果你有時間善用到開發結果，就選擇開發 (ex. 哪台吃角子老虎比較好賺)	如果你打算離開賭場，就選擇善用 (選擇已知勝率最高的吃角子老虎機)
其他生活的例子	樂評家聽新作品，寫評論	家人在假日聚在一起吃飯；聽喜愛歌手的演唱會

5. 製藥業的兩難

開發 (explore)	善用 (exploit)
探索不確定的未來，希望永續經營，若有重大醫學突破，可以持續幫助未來的人類。	確保現在能賺進利潤的現有產品有很好的表現。 不論怎麼想，「現在」總是比未來重要，利潤更是如此，經濟學家把「現在比未來有價值」稱為「折現」。 舉例來說，你對於明天晚餐的關心程度遠高於一年後的晚餐，確切的差異取決於你的「貼現函數」。

6. Gittins Index 說明

提出者

英國數學家 John Gittings 於 1970 年提出此指數，破解數十年來無法解達的數學謎題。

白話說明

當你計劃出去吃一頓飯的時候，明天那頓應該比今天這頓要貶值一點 —— 因為你明天可能會離開這裡，吃不上那頓飯。具體貶值多少，取決於你預期還能停留多長時間。基於這一點，他提出了一個非常複雜的解決方案，最後結果是給每個選項計算了一個指數，現在被稱為「Gittins Index」。 (Ref.: https://reurl.cc/1gZmkX)

Gittins Index 表格說明 (表 2-1)

表 2-1 假定每次比前一次貶值 10% 的計算結果 從表格發現有趣的現象 ① 任選一列，由左往右的指數逐漸增加，這隱含著如果選到一直贏錢的吃角子老虎機，繼續在同一台下注是正確選擇。 ② 輸錢就換一台的策略很糟，例如贏 9 次、輸 1 次的指數還有 .8695，仍高於表格中的其他值，應在同一台下注而非換一台。 ③ 左上角 0 注 0 贏，也就是一台完全陌生的機器，期望值為 0.5，Gittins Index 卻高達 0.7029

Gittins Index 表格說明 (表 2-2)

表 2-2 假定每次比前一次貶值 99% 的計算結果 假設未來的權重與現在相差無幾，相對於接受確定事物，選擇偶然發現之事物的價值會更高。在下表中，左上角 0 注 0 贏，也就是從來沒測試過的機器，勝率高達 86.99%。

理論限制

如果改變選擇要付出代價，Gittins 策略就非最佳策略。 另外那座山可能比較高，但不一定要前往，更不用說要花力氣爬山。

反思

如果我們有機會善用開發的結果，我們就有絕佳又精確的理由偏好未知事物。即使覺得未知事物沒有改變、甚至更糟，但它提供更好的機會。 開發本身是有價值的，因為嘗試新事物可提高發現最佳選擇的機會，因此考慮未來而非專注現在，將促使我們趨向創新。

生活智慧應用

① 年輕時代要大膽探索，因為你還有時間：年輕時可不斷探索未知，積累經驗教訓，才能迅速理解這個世界，後期才能做出更好的選擇。 ② 隨著年齡增長，要慢慢學會利用已有的經驗，專注於收獲：一般人的規律是，人的年齡越大，社交的圈子越窄。這其實是老人的理性選擇。他們已經完成了探索！知道自己最適合做的事情是什麼，和哪些人在一起最舒服，哪個餐館最符合自身口味，已沒有冒險探索的必要，只要享受人生就行了。 ③ 慢慢變老的過程中，我們的生活其實是越來越好：老人不探索，並不是不敢探索，而是因為他們不用探索 — 他們已經完成探索。當你看到一位老人，每天跟同一個人，去同一個餐館，坐在同一個座位，點同樣的飯菜，你可能以為他的生活很無聊 —— 殊不知這才是最浪漫的事，他是在享受自己用一輩子的時間所探索出來的成果！

7. 當 Gittins Index 對你來說太複雜，你還有一個選擇：特別注意「遺憾」。遺憾常源自於我們沒做到的事，以及沒嘗試過的事。管理理論學家 Chester Barnard 曾說：「放手嘗試的話，就算不成功你至少還有收穫 (to try and fail is at least to learn)；但沒嘗試就沒有結果，這樣的損失難以估計。」

8. A/B Test (Ref.: https://reurl.cc/1gZGLV)

定義

AB 測試 (A/B test) 是許多網站、尤其是具備電子商務功能的網站拿來快速測試改版、微調效果並協助設計與商業決策的方法之一。簡單來說就是將欲測試的變因或假說分別做成A版與B版 (甚至C、D等版)，利用一些工具，將造訪網站的人流隨機均分至兩個版本，最後選擇目標達成表現較好的版本。

統計學角度

從上面的定義，我們可以知道 A/B 測試其實包含了三個核心概念：「隨機化的實驗」、「一個變因，兩種選擇」、「兩種樣本的假設檢定」。以統計學中實驗設計的角度來看，進行A/B 測試實際上是在執行一個「隨機對照試驗」 (Randomized Controlled Trial，RCT)：在所有的使用者中隨機抽出兩組，一組投放 A 版本，另一組投放 B 版本，其中 A 版本與 B 版本只有一個地方不一樣，接著蒐集使用者的資料，並進行分析比較出哪一個版本較佳，這便是整個A/B 測試的過程。在進行 A/B 測試時的步驟如下：

9. 大致來說，大多數人傾向過度開發，也就是對新事物的偏好遠大於原本最喜愛的事物。所以，我們常太早決定用誰擔任新秘書，但又常常太晚決定不再嘗試新航空公司；沒有祕書需要付出代價，太早決定只選某家航空公司也是。

10. 要在變化不定的世界生活，本身也要有變化不定的特質。只要事物持續改變，你就不能完全停止開發，例如，你先前感到失望而幾年沒去過的餐廳，或許已經換人經營，可能可以再訪一次。

11. 開發與善用的矛盾、時間的重要性、Gittins Index 表格中 0-0 選項的高勝率、盡量減少遺憾等，不僅讓我們以新方式理解自身面臨的特定問題，也能了解人類生活的所有層面。

12. 人類有個奇怪的特質，就是我們需要花費多年才學會自立；反觀動物，北美馴鹿與羚羊打從一出生就要開始逃離掠食者。

玩吃角子老虎機	育兒
最佳策略通常是一開始先開發，再依據開發 (explore) 結果善加利用 (exploit) 勝率較高的機台。這種方式的缺點是，開發階段的報酬通常不理想。	童年時期讓我們有機會開發各種可能性，不用擔心報酬，將報酬問題交給父母、祖父母來處理。 兒童的善用能力 (exploit) 很差，不會穿鞋子、不懂長期計畫、很難專注，各方面都不在行；但是對新玩具很感興趣，很擅長按下隨機按紐 (explore)，從 A 跳到 B。 如果說兒童時期的目的是開發，他們確實應該做上述的事情。嬰兒很會把每個東西都放到嘴裡嘗嘗，就跟大人在賭場裡每部吃角子老虎都拉拉看一樣。

13. 更廣泛地說，我們對理性的直覺通常源自善用而非開發。我們討論決策時通常只注意單一決策的立即報酬結果，如果我們把每個決定都當成最後一次，採取善用決策確實合理。但是我們一輩子要做出許多決定，其中許多決定、尤其是在人生初期來說，強調開發 (例如，捨棄已知事物而選擇新事物、捨安全而選擇刺激、捨考慮而選擇隨機)，才是最合理的選擇。

14. 老人的社會關係減少，是他們自己選擇的。他們選擇削減次要關係，轉而專注於少數親近的朋友和家庭成員。這個過程是刻意的選擇，人類接近生命終結時，往往希望更專注於更具意義的關係。但是，老人與年輕人都是依據自己的時間做出最適宜的選擇。刻意把社會網絡限縮到只留下最具意義的關係，是享受剩餘人生較少時的合理反映。但並非老人永遠都是選擇善用，年輕人永遠都選擇開發：

選項	年輕人	老人
選擇飯友	【開發】 傾向選擇新朋友	【善用】 傾向選擇家人或老友
選擇是否搬到國外	【善用】 傾向選擇家人留在家鄉	【善用】 傾向選擇家人留在家鄉
選擇是否選擇新的醫療技術，讓自己延年益壽	【開發】是	【開發】是

15. 如果把未來的人生視為好好運用幾十年來累積的知識的機會，最大的收穫應是這句話：開發者用樂趣換取知識，人生應該越過越好。

[閱讀筆記] Algorithms to Live By - 最佳停止點 (Optimal Stopping)

 最佳停止點 (Optimal Stopping) - 什麼時候該見好就收？

1. 在最佳停止問題 (Optimal Stopping) 中，真正讓人困擾的不是該選擇哪個，而是可以考慮的選項有多少。面臨這類問題的不只有情侶與想租房子的人，還有駕駛人、想買屋的人、竊賊、開車度假找旅館的人等。

2. 37% 法則 (37% Rule) 源自於著名的最佳停止問題 - 秘書問題 (secretary problem)：

秘書問題

假設你想跟幾個應徵者面試，並盡量提高從中找到最佳人選的機率。 以隨機順序與應徵者面談，每次一位，可以在任何時候決定錄取人選，且那個人一定會接受職位，並結束徵人過程。但是若你決定不錄取某人，之後就沒有機會錄用他。 【決策的兩難】 ① 太早做決定，其實有更好的人選。 ② 找得太久，想找更好的人，但是不存在這樣的人選。 最佳策略顯然是找出兩者間的平衡，不要太快做決定，但也不要太倉促決定、太不挑。

思而後行的策略 (秘書問題的最佳解決方案)

設定一段「思考」時間階段，也就是研究各種選擇和蒐集資料，在這段時間不論遇到多優秀的人，都不錄取；過了設定的時間階段後，就要準備好隨時出手，只要看到比思考階段的應徵者更好的人選，毫不猶豫馬上錄取。

為什麼是 37%？

數學家歐拉（Euler）提出了一個 37% 法則作為解答，他先將所有的受試者人數設定 為n，然後就開始面試，把面試過的每一個人的適合程度做排序，再面試到 K 個人之前，無論受試者多優秀都不錄取，等到面試到 K+1 之後如果看到比之前優秀的受試者，則毫不猶豫的錄取。歐拉推導出了一個公式，說明Ｋ值的最佳解就是37%。(Ref.: https://reurl.cc/xgORzE) (Ref.: https://reurl.cc/MZbeqn) 意即，一旦過了這個底線，就大膽地開始選擇，這就是最好的選擇模式。

37% Rule 日常生活例子(Ref.: https://reurl.cc/xgORzE)

假設你是一名人力主管，要找一個會計，你們這家公司家大業大，共有十萬人來應徵，那歐拉告訴你，你的策略就是先面試 100,000.37=37,000 人，這些人全部打槍不錄取，到 37,001 人之後如果有比前面更優秀的人就直接錄取。 假設女孩的追求者有 10 個人，那依據 37% 法則，女孩會對前 4 個追求者全部發好人卡，等到第 5 位之後，如果有條件更好的男生出現則直接接受。 我們在找車位的時候也是一樣，總是想要停的離目的地近一點，但是又怕錯過了這個車位之後就沒有了，37% 法則告訴你，假設目前的車位離你的目的地有十分鐘的距離，那當你開到距離目的地 6.3 分鐘以後只要有空車位，你應該馬上停車。

37% Rule 意涵

最算採取此最佳策略，失敗機率高達 63% (1-.37=.63)。絕大多數的狀況你無法找到最佳人選，但最佳停止就是最佳策略，不管有多少人選都適用。 37%法則不一定能讓你的人生找到完美伴侶或是保證找到車位，但是卻是數學家用模型告訴你如何面對一個既期待又怕錯過的未來。

3. 當你要衡量的對象能提供完整資訊，呈現某應徵者總排名的客觀標準，就會使適用的解方從「思而後行法則」變成「臨界值法則」(完全資訊賽局)，找到最佳人選的機率會從 37% 大幅提升。

4. 沒有選擇的時候，只能降低標準；可選擇比較多的時候，就提高標準。

例子	說明
🏡 賣房	在賣房的你，因為存款有限，一定時間內沒賣掉有缺錢問題的話，就該在界線接近時降低標準，所以買房的人通常會找「急售」的物件，議價空間較大。
🚗 找車位	找停車位時，當有一堆空位，你就可以選擇離電梯最近的車位；當沒什麼停車位時，看到位置就要毫不猶豫馬上搶。

[閱讀筆記] Algorithms to Live By - 前言：為什麼我們能跟電腦學決策？

 前言：為什麼我們能跟電腦學決策？

1. 說到演算法，許多人聯想到的是大數據、大政府與大企業神祕難解的算計。這類算計在現代世界基礎建設中的比重越來越大，但稱不上是實用智慧或人生指南。演算法其實是解決問題的一連串步驟，而且範圍比電腦廣、歷史也更悠久。早在機器使用演算法前，人類就已經在使用它們了。

2. 用到演算法的領域不只數學。參考食譜做麵包、依照圖樣打毛衣、，或是用一定方式用鹿角末端敲擊燧石，在燧石形成尖銳的邊緣 (這是製作精細石器的重要步驟)，都是依據演算法在做事。早從石器時代開始，人類科技就蘊藏演算法。

3. 我要看幾間房子才要決定買哪間？我要在停車場繞幾圈才要決定停哪個位置？賣房、賣車要忍耐多久才能等到更好的價格？要相親幾次才要決定哪一位才是我的終身伴侶？當我們在做選擇時，總是在「錯過好機會」與「說不定還有更好機會」兩者間徘徊、猶豫不決。你取得的資訊越多，越能掌握真正的好機會，但在這之前錯過好機會的機率也越高。例如你要看過一陣子才知道什麼房子才是好房子，但是當你建立此標準後，你也可能已經錯過好房子。

4. 數學家提出 37% 法則 (最佳停止問題，optimal stopping) 來協助我們解決上述問題，這不只是尋找與放棄之間的平衡點，也是經過驗證後的最佳解決方案。37% 法則就是將願意花掉的總時間乘以 37%，就是最佳決定的時刻。舉個簡單例子，如果你想要在一個月之內租到房子，那個房子是最佳房子的最佳機率，那就是 11 天 (30.37=11.1)，也就是花了 11 天之後，你就要出手了。只要找到比你先前看過的房子更令人心動的房子，就立刻動手，不要猶豫，這就是最佳決定的時間點，因為你花再多時間也不可能找到更好的了。

5. 37%法則也可用於決定人生伴侶這件事，假設從 18 歲開始，我們就汲汲營營於尋找另一半，至 45 歲左右為止。那依據最簡單的加減法與乘法 ((45-18+1)37%=10.36)，決定終身伴侶的時間點約落在 28 至 29 歲之間 (18+10.36=28.36)。如果那時你已經有合適的伴侶，那就可以考慮結婚，因為以後也找不到更好的。(https://reurl.cc/WEkr57)

6. Carl Sagan 曾說：科學不只是知識，更是一種思考方式。即使混沌的難以進行嚴謹數值分析或有現成答案的狀況，運用直覺和簡化問題後加以思考得到的概念，也能讓我們了解關鍵問題和獲得進展。

7. 直接了當的計算 (如 8542765=6,534,630) 對於電腦而言輕而易舉，但是跟人類交談、修復損壞的檔案或下贏一盤圍棋等，這類沒有明確規則、缺少必要資料，或是必須考慮多如繁星的可能才能找到正確解答的問題，才是電腦科學最大的挑戰。研究人員為了解決極端困難的問題而開發的演算法，已經使電腦不再仰賴繁重的計算，相反地，執行實際工作必須接受機率，為了省時而不那麼講究精確，還要懂得運用近似法。

8. 本書將探討的演算法，可以針對每天面臨的挑戰，尋找更好的解決方案，把電腦科學解決問題的方法討用到你我的日常生活中

演算法	日常生活應用
最佳停止問題 (Optimal Stopping)	何時該大膽跳過，何時又該留意機會
開發與利用取捨 (Explore / Exploit)	如何在嘗試新事物和享受原本喜愛的事物間找到平衡點
排序理論 (Sorting)	教我們如何以及是否應該整理辦公室
快取理論 (Caching)	教我們如何把物品收進櫥櫃
排程理論 (Scheduling)	教我們如何安排工作

9. 真實世界並非數學家描述的那麼條理分明與嚴謹，真實的規則其實違反我們內心的合理性，包含：

真實世界的規則

① 不一定要考慮所有選擇

② 不一定非得追求看起來最好的結果，偶爾可以製造混亂

③ 看到紅綠燈就停一下

④ 相信直覺，不要思考太久

⑤ 放鬆，拋個硬幣

⑥ 寬恕，記住這個教訓就好

⑦ 誠實對待自己

10. 本書將帶你深入了解各類日常生活問題，以全新方式觀察人們遭遇的各種困境背後的美麗結構，認識人類和電腦的解決方式融合程度極高，還將獲得更深刻的東西：我們會有描述周遭世界的新詞彙，並且擁有重新認識自己的機會。

11. 21 世紀的 AI 專家主張「有界限的最佳化」，意即權衡時間與誤差後，選擇最適合的演算法，是開發實用智慧代理的關鍵。曾參與撰寫 AI 書籍、暢銷教科書 Artificial Intelligence : A Modern Approach 的加州大學柏克萊分校電腦科學家 Stuart Russell，以及微軟研究中心管理主任 Eric Horvitz 都曾提到這點。