[閱讀筆記] The Math of Life and Death - ㊅ 永不停歇的改善：從演化到電子商務，展現演算法的無限潛力 (Relentless Optimization: From Evolution to E-commerce, Life is an Algorithm)

 

1. 演算法其實是一連串的指示，用來明確完成某一項任務，從整理手邊蒐集的唱片到做出一到菜等。然而，史上最早的演算法，本質上是很單純的數學。

古早時代的演算法 🤔💭📊🧮📝

古埃及時代有一套簡單的演算法，用來將兩個數字相乘； 巴比倫也有一套演算法來計算平方根； 西元前三世紀，古希臘數學家 Eratosthenes 發明質數篩選法 (sieve)，可以找出一定範圍內的質數； 阿基米德發明窮舉法 (method of exhaustion) 來計算圓周率。

2. 現在電腦執行的演算法日益複雜，當我們想要有效率的處理日常事務時，演算法變成不可或缺的一環。以往的解答已經無法滿足我們的需求

	Before	Now
搜尋引擎	找到資料	找出最相關的資料 ℹ️
氣象預報	告訴你明天天氣	告訴你明天下午五點會下雨 ☔
GPS	算出一條路線	提供能最快抵達的路線 🚗

3. P/NP 問題的核心：針對問題的答案做驗證，通常比找出問題的答案還容易。這個數學未解之謎真正要問的是：如果某個解答能用電腦快速驗證，是否也能用電腦快速求解？

P 問題 (Practical Problem)

如果有一組問題，能在多項式時間 (polynomial time) 內快速求解，就是 P 問題 🧩 假設我打造一套會拼拼圖的演算法，求解時間取決於片數、片數的平方 / 立方 / 更高的次方。舉例來說，如果這套系統取決於片數的平方，解開兩片拼圖需要 22 = 4 秒、10 片拼圖要 102 = 100 秒、100 片拼圖要 1002 = 10,000 秒，雖然看起來很久，但仍舊是幾個小時內可以解決的事。

NP 問題 (Not Practical Problem)

另一種問題，可以快速驗證，但不一定能快速求解，就是 NP 問題，NP 指的是非多項式時間 (nondeterministic polynomial time) 。NP 問題會因問題規模的增加，很快得變得不可行。 一旦能快速求解，當然就可快速驗證答案，所以 P 問題是 NP 問題的子集合。 假設這套會拼拼圖的演算法，需要的是非多項式時間 (NP)，解開兩片拼圖一樣需要 22 = 4 秒、10 片拼圖要 210 = 1,024 秒、100 片拼圖要 2100  秒，這已經超過從宇宙爆炸迄今的時間。

P 與 NP 問題間的關係

4. Bubble Sort、Insertion Sort、Merge Sort 《Algorithms to Live By》

Bubble Sort

是一種簡單的排序演算法。它重複走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。 是最簡單瞭解和實作的排序算法之一，但它對於包含大量的元素的數列排序是很沒有效率的。 平均時間複雜度O(n2) 最壞時間複雜度O(n2) 最佳時間複雜度O(n) (Ref.: https://reurl.cc/Dv3nRE)

Insertion Sort

此排序法優點是比氣泡排序法更直覺，評價較好，缺點是其實沒有快多少。採取此方式時，每個位置還是都要插一次，每次插入平均時間需經過一半的位置，才能找到正確的位置。儘管插入排序法速度快了一點，花費時間仍是平方時間，沒有比氣泡排序快多少。 平均時間複雜度O(n2) 最壞時間複雜度O(n2) 最佳時間複雜度O(n) (Ref.: https://reurl.cc/qmNdzy)

Merge Sort

上述兩個看似合理且直覺的排序方法，搜尋時間都是平方時間 (quadratic time, O(n2))，排序對象一多就難以負荷。合併排序 (merge sort) 就是用來解決上述難題，它的複雜性介於線性時間和平方時間之間，更精確地說是線性對數時間 (linearithmic time, O(n log n))。屬於 Divide and Conquer 演算法，把問題先拆解 (divide) 成子問題，並在逐一處理子問題後，將子問題的結果合併(conquer)，如此便解決了原先的問題。 (Ref.: https://reurl.cc/bzEEnl)

5. 排序與運動賽事的類比 《Algorithms to Live By》

排序方法	運動賽事
Bubble sort	羽球、壁球等常用的排位賽 (ladder)，是依照排名順序列出的選手名單，每名選手可以挑戰前一名選手，如果獲勝，排名就對調。這就是運動界的 bubble sort，執行時間是平方時間。
Merge sort	NCAA 的單淘汰制 (tournament bracket)，每一輪比賽都淘汰一半隊伍，從 64 強、32 強、16 強、8 強、4 強以及決賽。這就是運動界的 merge sort，一開始為排序的隊伍兩兩比賽，接著不斷對併再對併。

6. 旅行推銷員問題 (Travelling salesman problem, TSP)，是組合最佳化中的一個NP 困難問題，在作業研究和理論電腦科學中非常重要。問題內容為「給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。」旅行推銷員問題有個「決策版本」，它只問有沒有比某長度更短的路徑，就是 NP-Complete 問題的經典範例。理論上，如果能提出一套可行的演算法，解出某個 NP-Complte 問題，就能轉換這套演算法來解決其他 NP 問題，這樣就能證明 P = NP。

P = NP 造成的災難

💻 🛒 🔐 線上交易安全性將會是災難，因為我們正是靠著難以解決的 NP 問題，來建置現行的網路加密技術。

P = NP 造成的好處

🏭 工廠可以排出最有效率的製程 🚚 快遞公司可以排出最有效率的送貨路線 🧬 找到更有效率的基因定序方法 🌀  找出更有效率的預測自然災害方法

7. P 與 NP 的對抗，其實是在確認人類的創意是否能自動化。若 P = NP，那麼任何可證明的數學定理，電腦都能在一定的程式序列內找出證明。這代表過去人類許多偉大的智力成就 (ex. 牛頓的運動定律、達爾文的自然選擇演化論、愛因斯坦的廣義相對論、懷爾斯的費馬最後定理證明)，只需一台機器即可複製並取代，許多數學家將因此失業。

8. 我們有時候不一定想要完美但緩慢的方案，反而寧願接受普通但快速的方案。例如，💼 在上班前，我不太需要研究怎麼擺才能讓公事包裡的物品占據最小空間，只要能讓所有東西塞進去即可。啟發式演算法 (heuristic algorithm，又稱經驗法則)，就是讓我們在面對許多不同問題時，得到與最佳解相去不遠的解決方案。

9. 貪婪演算法 (greedy algorithm) ，是一種短視的演算法，靠著找出當下問題的解決方法，希望最後找出整體問題的最佳解。貪婪演算法，一定能找出某種解決方案，卻無法保證最後得到的是最佳解，有時候甚至稱不上普通解。但確實有些問題，能夠用此法得到最佳解。

10. 汽車衛星導航採用 Dijkstra's algorithm (戴克斯特拉演算法)，是一種 greedy 演算法，每次都去找當前最小的那一條路，能在多項式時間 (polynomial time) 內快速找出「最短路徑」的答案。

運用 Dijkstra's algorithm 尋找 A 到 E 的最短路徑 (https://reurl.cc/735bE5)

建立表格

Visited: 有沒有走過這個點，預設為 False Cost: 從起點到這個點所需路程，預設為無限大 Path: 這個點的上一個相連點，預設 -1 (或是任何可代表非圖上點的值)

A → C → E 【Cost = 12】

A → B → D → E 【最短路徑，Cost = 8】

A → B → E 【Cost = 9】

11. 群體智慧 (Swarm Intelligence) 是自然科學研究的領域，他研究的對象主要是自然群體生物在現實環境中，各種群體行為的相關議題，例如：路徑規劃、任務分配和築巢…等。很多時候甚至可以觀察到，即使是弱小的生物個體，當群聚一起時，卻可以展現出極其複雜的集體行為。常被研究的自然群體生物有：細菌菌落、魚群、螞蟻群、蜜蜂群、蝗蟲、鳥群、靈長類部落，當然其中也包含了人類。研究這些群體是非常有趣的，例如：螞蟻群在工作時，儘管沒有領袖發號司令，卻可以在移動過程中漸漸地找出最佳移動路徑。演算法設計人員從動物間的互動得到靈感，可以派出大量彼此連結緊密的人工智慧體 (artificial agent)，讓它們去探索某個環境；這些人工智慧體能夠如動物群體般的迅速溝通互動，在搜尋環境的過程中，互相掌握其他個體的發現。它的控制是分布式的，不存在中心控制。(https://reurl.cc/73ORrN)

12. 在我們眼中，有許多物種適應良好，堪稱典範。但有可能演化還沒找到最佳方案，只是我們想像力不足，才會誤會這已是「完美」的方案；幸好有隨機的組合與突變，能讓我們擺脫局部最大值，進一步找到更好的解決方案。

13. 隨機性演算法未必能提出最佳解，但它不用像確定性演算法那麼辛苦，只要有計畫地丟幾個硬幣，就能在短短時間內提出相當接近最佳解的答案。隨機性演算法用於特定問題的效果，甚至超越最好的確定性演算法。問題的最佳解決方法有時候是交給機率決定，而不是自己試圖推出答案。運用隨機法，想辦法從局部最大值，變成整體最大值。《Algorithms to Live By》

14. 無論是抖動、隨機重新開始、或是接受解決方案偶而變糟，隨機性用於避免局部最大值的效果都很好。機率不只是處理困難最佳化問題的可行方法，在許多狀況下還是必要方法。從模擬退火法可以得知，你應盡早使用隨機性，並快速離開隨機的狀態，隨時間而降低隨機性，停留在接近結冰的時間最久。壓住火氣，不要急躁。《Algorithms to Live By》

15. 在最佳停止問題 (Optimal Stopping) 中，真正讓人困擾的不是該選擇哪個，而是可以考慮的選項有多少。面臨這類問題的不只有情侶與想租房子的人，還有駕駛人、想買屋的人、竊賊、開車度假找旅館的人等。37% Rule 源自於著名的最佳停止問題 - 秘書問題 (secretary problem)：《Algorithms to Live By》

秘書問題

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

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

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

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

👨‍💼 假設你是一名人力主管，要找一個會計，你們這家公司家大業大，共有十萬人來應徵，那歐拉告訴你，你的策略就是先面試 10,000 x 0.37 = 37,000 人，這些人全部打槍不錄取，到 37,001 人之後如果有比前面更優秀的人就直接錄取。 👧 假設女孩的追求者有 10 個人，依據 37% 法則，女孩會對前 4 個追求者全部發好人卡，等到第 5 位之後，若有條件更好的男生出現則直接接受。 🅿️ 我們在找車位的時候也是一樣，總是想要停的離目的地近一點，但是又怕錯過了這個車位之後就沒有了，37% 法則告訴你，假設目前的車位離你的目的地有十分鐘的距離，那當你開到距離目的地 6.3 分鐘以後只要有空車位，你應該馬上停車。 🍽️ 假設你與另一半在逛街、找餐廳，你大約有十間餐廳可以選且不想留下優柔寡斷的印象，最好的策略前三間餐廳只是觀察、不進去，從第四間開始，只要比前三間都好，就近去用餐。 當賣場有 11 個收銀櫃臺，你可以先觀察 4 個收銀櫃檯的排隊長度，接下來只要看到更短的隊伍，就去排那一排。

37% Rule 意涵

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

16. 世上有很多人都會跟我們處得不錯，能讓我們有幸福的一生。最佳停止時機的策略，並不會提供所有人生問題的答案。我們雖然可以用演算法來簡化、加速單調乏味的任務，但風險也伴隨而來。因為演算法包含輸入、規則和輸出，也就代表有三個可能錯誤的地方。就算使用者確信所用的規則完全符合需求，只要輸入有誤或輸出不符合規範，就可能導致災難。

17. ​💠​🤖​ 現在的股市交易，已有越來越多是程式交易 (algo trading)，因為面對市場的種種變化，電腦察覺並做出回應的速度遠快於真人。根據估計，Wall Street 的交易已大約有 70% 都是由這種所謂的黑盒子機器來處理。

18. 📉 2010/5/6 美股遭到閃電崩盤 (flash crash)，電腦股票系統被不明原因觸發，連編寫程式的人也不了解電腦做的交易。道瓊工業指數在 5 分鐘內下跌近 600 點，電腦間在 15 秒內互相交易 27,000 份期貨合約，最終因期貨市場內建的保護機制，將所有交易中止 5 秒鐘，電腦的瘋狂交易就令人讓人難以置信的恢復正常。電腦的演算法是人撰寫的，電腦沒有常識，只會盲目地買進與賣出，因為這就是它的演算法要求它們做的事情。《Standard Deviations: Flawed Assumptions, Tortured Data, and Other Ways to Lie with Statistics》

📉 2010/5/6 flash crash (https://reurl.cc/DZap3e)

19. Navinder Sarao 在自家臥室就成功操控了股市，正說明用演算法發動惡意攻擊是多麼容易的事。我們太常把演算法視為一系列公正、不帶偏見、不受情緒影響的指令，而忘了所有演算法背後都隱藏著一開始研發的目的。

20. 即使演算法事前定義，在執行時也公正不阿，但即使設計者確實抱持公正的初衷，也不代表當初設計的目的完全不帶偏見。規則是人訂的，無論有心或無意，程式設計師都可能把自己的偏見帶進演算法本身，寫成程式後，令人一時看不出那就是先入為主的偏見。

21. 華盛頓郵報引述的內部文件揭露，臉書的排名演算法自 2017 年開始，將「怒」等表情符號回應的價值視為比「讚」高出 5 倍。背後理論很簡單，激起很多情緒符號的貼文往往會確保用戶提高參與，而確保用戶參與率對臉書有極大好處。報導更指出，演算法推廣的力量則破壞了內容審查員及操守團隊對抗有毒及有害內容的努力。臉書前產品經理兼「揭弊者」Frances Haugen 告訴英國議會，「憤怒與仇恨是臉書上最簡單的增長方式」。(https://reurl.cc/mvabnA)

22. 隨著演算法日益複雜，輸出結果也越來越難以預測，所以需要加強控制與人為監督。然而這些控制與人為監督，絕不只是科技龍頭企業的責任。身為這些科技龍頭企業的 end user，也須負起部分責任，判斷自己得到的 output 真實無偽，例如：❶ 📰 對於自己讀到的新聞，是否要相信此消息來源？❷ 🛰️ 對於汽車導航的建議路線，是否要照著走？