決斷的演算:預測、分析與好決定的11堂邏輯課

閱讀時間約 27 分鐘

決斷的演算:預測、分析與好決定的11堂邏輯課

Algorithms to Live By: The Computer Science of Human Decisions

Brian Christian, Tom Griffiths  2022 行路出版社

分類:論說--理論 

★★★☆☆

 

一句話:

探討人類演算法的設計概念,把電腦科學解決問題的方法套用到人類日常生活的挑戰上。

 

重要字句:

電腦科學家也一直在探究人類日常遭遇的困境(時間、空間和能力的有限),例如處理器該如何分配它的「注意力」;減少做白工的時間;什麼時候應該決定轉而處理不同工作;如何運用有限的記憶體資源;應該繼續蒐集資料還是依據現有資料採取行動。電腦的工作方式,也就是演算法,可以帶給我們許多啟發。

 

並不是要讓電腦教我們如何思考,而是透過電腦科學的眼光看問題,把求生和認知當成「解決環境造成的基本運算問題的方法」,來試著了解人類心智和理性的特質。此外也可以根據演算法的觀點做出設計讓人類的生活更好。

 

現代電腦解決問題已不再單純只是靠著暴力運算(假設有無窮的運算能力和時間來解決問題),而是使用機率和近似法,權衡時間與誤差後選擇最適合的演算法。電腦處理困難問題不再是耗費大量時間和算力運算各種可能再做出理性選擇,而是在短時間內得出最合理的答案。

 

演算法設計必須藉助多個學科,例如數學、電腦科學、工程學、統計學等等。討論人類心智所使用的演算法也需要跨學科領域。

 

電腦科學可以幫助我們找到解決人類問題的演算方法,雖然不一定產生最好的結果,另外也可以幫助我們判斷問題是否是可以使用經驗法則或隨機性計畫的難解問題。

 

摘要:

近年來行為經濟學主張,人類既不理性又容易犯錯,是因為大腦演化而來的缺陷導致。但電腦科學衍生的日常問題解決方案,對人類心智提出完全不同的看法,是我們面對的問題和環境太過複雜困難(不確定性、時間限制、資訊不足、變動快速),而非人類大腦不可靠,某些情況根本不存在高效率又絕對正確的演算法。

 

最佳停止點 optimal stopping

最佳停止問題:

秘書問題(在有每位應徵者的相對排名情況下,如果決定不錄取某人之後就沒機會用他,決定錄取那個人一定會接受);要和多少人交往才知道誰適合你;找房子;找停車位。

 

策略:

找出太早決定或找的太久之間的平衡。困境在於遇見「目前最佳」應徵者的機率會隨著面試更多人而降低。

 

最佳解決方案:

37%法則。數學證明在前37%的應徵者一律不錄取,經過這段「思考期」研究和蒐集資料後,只要看到比所有思考階段更好的人選就馬上錄取,如此找到最佳人選的機率是37%,不論應徵者有多少人。因此雖然大多數狀況下無法找到最佳人選,但隨著應徵人數增加成功機率會逐漸降低,因此最佳停止仍是最佳策略。

如果可能被拒絕,就提早採取行動(被拒絕的機率為q,則在應徵者比率到達q的1/(1-q)次方時就開始行動,這個比率一定小於0.37=1/e),且被拒絕以後只要出現最佳人選就錄取;如果可以回頭邀約,就把按兵不動的時間拉長。

 

其他變化:

傳統的秘書問題因為沒有客觀標準,只有應徵者的相對比較,因此需要有思考階段冒著錯過最佳應徵者的風險來建立期望和標準,數學上稱為「無資訊賽局」。但平常找房子或找伴侶的狀況是類似「完全資訊」,有客觀的甄選標準,則改使用臨界值法則,不需要先考慮再行動,只要應徵者的等級超過特定值立刻錄取,剩餘應徵者越少,就慢慢降低標準,此時找到最優秀應徵者的機率是58%,所以釣金龜婿的成功率通常會比追尋真愛高一點。

 

raw-image


賣房子的目標不是選出最高的出價,而是在過程中賺到最多的錢,如果沒有金錢壓力或預期出價人數有限,那我們應該根據等待下次出價的成本設定最低接受值,只要出價低於它一律拒絕,停止價格沒有理由隨著尋找過程而退讓。也不應該考慮先前的機會,因為如果當初它沒有超過你的臨界值,現在當然也不會。


raw-image


停車問題也是最佳停止問題,對停車策略的影響主要來自於占用率(已有車的車位和所有車位的比例)。如果占用率和一般大都市一樣99%,那應該在距離目的地將近70個車位(假設停車格等距離直線排列,大概超過400公尺)時,一看到車位就停進去,如果使用率85%,只要等到距離目的地半條街,約5個車位左右再開始找空位。

 

我們問了加州大學都市規劃特聘教授Donald Shoup,全世界最頂尖的停車專家,他的研究是否對他自己通勤上班有幫助。的確有。他說:「我騎自行車。」

 

啟發:

實際上古典秘書問題並沒有考量耐心、厭倦、應徵和尋找的時間成本等等,所以一般的人都會在處理秘書問題時提早停止。秘書問題的基本假設是嚴格的序列性和無法回頭的單向過程,因此時間的流逝可以讓所有決策都變成最佳停止,儘管失敗率居高不下,我們不得不依據尚未得知的可能性做出決定,選擇一旦錯過就過去了。

 

當時鐘不斷跳動,決策(廣義來說是思考)過程中最重要的面向其實只有一個,就是何時應該拿定主意。

 

開發與善用 explore/exploit

問題:

要嘗試新事物還是堅持自己原本喜歡的東西,這類問題電腦科學家稱為「開法與善用權衡」,開發是蒐集資料,善用是運用現有資訊取得已知的良好結果。例如選擇餐廳、選擇想聽的音樂、開發新藥或製作現有商品。

 

解決方案:

多臂土匪問題,形容賭場中很多吃角子老虎機,每部機器的報酬率都不同(但金額相同),計算出測試每一部機器(開發)與選定最可能贏錢的那台(善用)的方式。其中每個決策並非孤立的,期望值也不是唯一的結果,思考的是未來對相同選項做出的所有決定。

 

採用何種策略取決於時間,探索和發現新喜好的價值會越來越小,因為我們體會它的機會越來越少,而善用的價值則會越來越大。如同完全資訊秘書問題,可以嘗試用逆向推理的方式找出答案,但我們很難知道有多少機會和多少選項。數學家John Gittins根據及時收益、等待時間和長期價值的折現,計算出吉廷斯指數,

 

raw-image


舉例來說,假設下次下注的報酬價值為此次的90%時,你應該選擇2注1中(0.6346)的機器,而非期望值較高的15注9中(0.6300)。由表可以看出贏錢繼續玩確實是正確的策略,也可以看出輸錢換一台策略什麼時候會更糟,例如一開始贏9次後輸1次的指數是0.8695,還是高於其他的值,因此應該至少再下注一次再考慮換不換。如果未來的權重和現在相差無幾時(如折現率99%),開發的價值變得更高,從來沒測試過的機器的指數高達0.8699,因此考慮未來而非專注現在將促使我們趨向創新。但如果改換選擇需要付出代價,吉廷斯指數就非最佳策略了。

 

如果把「遺憾」(沒有嘗試過的選擇比實際選擇更好)考量進去,數學家證明了如果選擇最佳策略,遺憾會增加的比較慢,以及最小可能遺憾是隨下注次數呈對數增加的遺憾,代表最初10次下注犯錯的次數,和接下來90次下注相同。信賴上界(upper confidence bound)演算法是最常見的一種使遺憾次數最少的演算法,遇到多臂土匪問題時,選擇信賴區間頂端最高的選項,也就是不考慮目前哪部機器表現最好,只選出日後可能表現最棒的機器。採用這類演算法的建議,表示樂觀是防止遺憾的最佳方法。

 

A/B testing:亞馬遜或谷歌為某個網頁製作好幾個版本,接著隨機指派給使用者,一段時間後在統計上有明確效果的版本就會獲得採用或進入下一輪當對照組。企業想發掘能賺錢的事物,同時要讓這個事物發揮到極致,就是開發和善用的實例。在演算法的多臂土匪問題中,我們是大獎而不是賭徒。但也許這不是最佳方法,因為在測試進行時,有一半的使用者會被迫使用較差的選項。

 

我這一代最傑出的頭腦都在研究如何讓大眾點閱網路廣告。-- 前臉書資料科學家Jeff Hammerbacher

 

醫學臨床試驗也存在著「搜尋更多資訊」和「根據自己深信的資訊行事」之間的矛盾,獲取新知往往價值極高,可以帶來很大的助益,但通常仍然必須承擔傷害某些患者的風險。標準的臨床試驗重在釐清哪種治療方式較好,而非在試驗中提供每位患者最好的治療,運作方式有如A/B testing。如果把臨床試驗當成多臂土匪問題,使用某種治療方法的機率隨著療法的成功率而提高,也許就能盡量在實驗期間為患者提供更好的治療

 

生活中做的決定大多數都會提供資訊,讓我們日後做其他決定時參考,大多數人面對多臂土匪問題傾向於過度開發。過度開發的行為源自於假設世界不斷變化。先開發再善用方法的缺點是開發階段的報酬通常不理想,就如人類幼兒的依賴期特別長,讓我們能好好開發各種可能性,將報酬問題交由父母處理。「長久以來大人通常認為兒童在各方面認知不足,因為在我們看來,兒童的善用能力非常差。」加州大學心理學教授Alison Gopnik表示。如果說兒童的目標是開發,那麼他們確實是不擅長做長期計畫與專注。

 

啟發:

我們討論決策時通常只注意單一決策的立即報酬,因此善用看似理性的策略。但人生中一輩子要做許多決定,尤其是人生初期的決定,強調開發(捨已知最佳事物而選擇新事物、捨考慮而選擇隨機),才是真正合理的選擇。開發試用樂趣來交換知識,多數情況下善用比較可以提高生活品質,但驚喜的報酬往往高達好多倍。而社會網路關係隨著年齡而縮小,可能也是理性的選擇,提升社會和情緒的獲益和減少風險,專注在與親密家人朋友的關係。開發與善用的困境決策重點在於知道自己還剩下多少時間,而非年輕或年長的區別。

 

排序 Sorting

問題:

排序的主要目的是以好用的方式呈現物件,因此排序對人類的資訊經驗和電腦資訊十分重要。排序的問題在於東西規模越多越難處理。

 

策略:

電腦科學重視的是平均完成時間和最差完排時間。大O符號是用來探討演算法時間複雜度的指標,它不是以精確的分秒描述,而是最差情況下的運算次數,所以在估算時會忽略常數或是低次方的係數。

 

例如邀請n個賓客打掃房子需要花的時間,稱為常數時間O(1),大O符號不理會打掃需要多少時間,只說明打掃時間不受賓客人數的影響。烤肉在桌上傳一圈需要的時間則是線性時間O(n),也就是時間和賓客人數呈線性相關。如果賓客都要互相擁抱的時間稱為平方時間O(n2),同樣我們只在乎n和時間的關係,因此每人擁抱兩次的時間,或是擁抱加上傳遞食物或打掃房子的時間,全都是平方時間。

 

氣泡排序法是從第一筆資料開始,找出順序錯誤的兩者對調,再重複巡視數列直到排序完成。雖然簡單但時間複雜度為O(n2)。插入排序則是逐一將原始資料和以排序好的序列做比較,就像把書全部搬下書架,再一本本依照順序排回去,時間複雜度一樣為O(n2)。合併排序則是將陣列拆分排序後再合併至大陣列做排序,他的複雜性介於線性和平方時間之間,是線性對數時間O(n log n)。

 

raw-image


桶排序屬於分配性的排序,先分配固定區間的桶子,再將資料分配到相對應桶子裡,則把n個項目分到m個桶子可在O(nm)時間內完成,如果桶子的數目和項目數目比起來很小,就會是O(n)線性時間。之後每個桶再個別排序後依序收集好排列完成的資料,如此就能大幅減少排序所需的時間。

 

氣泡排序或許效率極低,但比較穩固而不容易受到干擾,就像循環賽(或排位賽)雖然比賽場數需要多很多,但單淘汰制的排序比較脆弱(NCAA的64強淘汰,若是強隊獲勝的機率是七成,那麼最強隊獲得冠軍的機率只有0.7的6次方)。

 

啟發:

電腦科學家思考的是到底需不需要排序,排序是為了節省日後搜尋資料的心力,因此必須權衡排序和搜尋,如何避免排序之後不會搜尋的資料或是需要搜尋沒有排序過的資料,問題就成了:要如何評估這些資料未來的用途?例如谷歌靠的就是排序網頁的能力,節省我們搜尋的時間;而家中的書架就不一定要排序,因為排序很慢,但可能只節省了幾秒鐘。

 

動物間也有互相鬥爭的排序問題,敵對行為會隨著群體擴大而大幅增加,呈現對數甚至平方增加,但如果用一個數值或基數做為評定水準的比較(例如馬拉松比賽),就能以常數時間演算法決定名次。

 

快取 Caching

問題:

整理衣櫃(該留下哪些和接著要怎麼收),電腦的記憶體管理。

 

策略:

電腦的中央處理器速度增加,但記憶體的效能並沒有以相同的速率提升,因此存取記憶體的成本也呈指數成長,快取記憶體是容量較小但速度較快的記憶體,可以做為處理資料後再存回去的便利區域,還可以存放稍後可能需要的片段資料,如同你從圖書館借回必要的書籍回來寫論文,就不需要一直回去圖書館。

 

快取演算法又稱替換策略或剔除策略,快取管理的目標是盡量減少在快取中找不到需要的資料。以隨機剔除、先進先出(覆寫在快取裡存放最久的資料)、最近最少使用法(LRU剔除未使用時間最長的資料)來比較,LRU最能預測未來使用的資料。時序局部性temporal locality是指如果程式曾經呼叫某項資訊一次,不久後就可能再度呼叫,人類解決問題的方式也有點類似電腦的時序局部性。

 

再以圖書館為例,剛還的書籍也是圖書館現在最可能再被借出的書,因此把歸還區的書重新排序或放回架上,某種意義而言反而是把它弄亂。最近歸還的書最可能馬上借出,這就是快取提高效率的意義。電腦的硬體線路布局對速度十分重要,如果存放網頁內容快取的硬體位置越接近使用者,就能越快存取網頁,目前網路的資料流量大多由內容分配網路(CDN)管理,規模最大(全球流量的1/4)的CDN由Akamai負責,他在世界各地都有電腦,因此使用者不需要跨過層層大陸到原始伺服器去取用。亞馬遜預測包裹寄送的專利也是利用快取的概念,把某地受歡迎的商品運送到該區的臨時倉庫。


啟發:

生活中的用品也可以如此整理,LRU就比先進先出來的好,雖然比較新但很久沒穿的衣服就先處理掉。通常在哪裡使用該物品,就放到那附近的「快取」裡。也可以具備多個層級的快取,例如收納箱、櫥櫃、倉庫。整理櫥櫃內的物品或文件也可以使用LRU,將每次找來用的東西放回最前端,而非馬上分門別類收好,刻意的不排序也許會比花時間全面排序更有效率。

 

遺忘可能問題也不在於儲存容量不夠,大腦的記憶曲線和我們周遭事物消失的頻率模式一樣,這是大腦適應世界的方式,為最有可能用到的記憶騰出空間。老化對認知的影響是因為儲存量增加而增加了搜索的時間,如果記憶的基本挑戰是整理而非儲存,那麼我們或許應該調整我們對年齡影響心智能力的想法。

 

raw-image


排程 Scheduling

問題:

在單一機器排程中,如果我們要完成所有指定工作,那麼以任何次序執行工作,花費的時間都會相同。因此第一個課題是如何訂出明確的測量標準和目標,因為這將會直接影響各種排程方法的表現

 

策略:

如果是有期限的工作,標準就是延遲的程度,因此減少最大延遲的策略就是一開始先處理期限最早的工作(Earliest Due Date),不需要知道工作所需的時間。Moore Hodgson algorithm則是剔除超過時程中耗時最多的項目,主要考量是延遲專案的數目而非嚴重程度。

 

如果把每樣工作都代表一名在等待的客戶,那麼減少「完成總時間」的方式稱為最短處理時間Shortest Processing Time,永遠處理能最快完成的工作,減少所有客戶的等待時間。如同「搞定Getting Things Done」書中建議的,一項工作完成的時間少於兩分鐘,一想到就去做,可以盡快減少待處理工作的數目,讓心情舒服一點。如果能辨別每樣工作的重要性,就把該工作的權重除已完成時間,從每單位時間重要性最高的工作開始。「除非重要性有兩倍之多,否則不要把耗時兩倍的工作放在前面。」

 

執行各種瑣碎工作而拖延重要工作的人,是在採取盡快減少心中待辦事項數目的行動,只是評估成果的標準跟他們想的不同。

 

當某件工作必須等另一件完成才能進行,稱之為優先權限制,了解日常生活中這種影響大事的小事十分重要。如果有幾項工作有優先權限制,或是有些工作要到特定時間才能開始,排程問題就成了沒有演算法可以找出最佳解的「難解問題」。在我們已經了解的排程問題中,有84%確定是難解問題。

 

如果能夠占先(preemption),也就是工作可以中途停止改做另一項,如果新工作比當前進行中的工作更早到期或能更快完成,就立刻改做新工作,這樣的話古典策略(最早到期日和最短處理時間)依然是最佳策略。就算在不確定何時有新工作的狀況下,最短處理時間的加權版本仍然是最佳策略的選項之一。然而,電腦和人切換工作都要付出延遲或可能錯誤的成本,認知資源有限,當記住必須做的每項工作占據了全部的注意力,或是設定工作優先權花了太多時間,會造成效能急遽下降,最好的方法是學著說不。

 

排程必須在工作的反應能力(回應速度)和處理能力(完成的工作量)達成取捨,番茄工作法(設定每項作業的最小執行時間)就是防止為了確保反應能力而犧牲處理能力。我們應該盡可能延長單一工作的時間,不要經常執行上下文切換來處理個別中斷的資訊,但不要使反應能力低於可接受的最低限度。

 

貝氏法則 Baye's Rule

問題:

生活中常常需要以單一資料點進行預測,例如已知公車等了多久,下一班什麼時候會來;由已知中獎與未中獎彩卷的張數推測整體中獎率。

 

策略:

拉普拉斯定律解決了由觀察結果逆向推測可能原因的問題,提供了現實世界面對小數據的經驗法則。拉普拉斯運用微積分證明重複一個實驗n次,獲得w次成功和n-w次失敗,則期望值為(w + 1)/(n + 2)

 

哥白尼原理是指多數情況下,我們可以預期自己目睹任何現象的那一刻,都是其持續期間的中間點,所以要預測這個現象還會持續多久,最可能的答案是等於它已經存在的時間,這是用在無提示性事前機率(沒有事前機率,完全不知道要預測的時間長度)時。但貝式法則告訴我們,要以有限的證據進行預測時,最重要的條件是擁有正確的事前分布,如果是冪次律分布或無尺度分布是用乘法法則,把目前為止觀察到的機率乘以某個常數(在哥白尼原理中這個常數是2)。但若事前分布是常態分布,則是用平均法則,以自然平均值當作指引。厄蘭分布則是描述已持續時間對結束的可能性不產生影響的事物,則用加法法則,事物持續時間的預測值會逐漸加長,而加長量是固定的。


冪次律分布代表事物已持續的時間越長,可能持續的時間就越長,因此等待某個冪次律事件(例如歷史悠久的公司倒閉)的時間越長,這事就越令人驚訝;常態分布的事件則我們等待越久,對它的期待越大,若晚於平均值時則不會驚訝;厄蘭分布的事件也稱無記憶分布,無論何時發生,都不影響它令人驚訝的程度,無論已經持續多久結束的可能性都相等。


raw-image


啟發:

我們從周遭生活中不知不覺吸收許多資料,形成了我們對事物事前分布的了解,因此我們對未來的預測其實透露出我們的經驗和過去。著名的棉花糖測驗也許抵擋誘惑的能力來自於期望實驗者回來的時間,而不只是意志力。另外媒體的特殊事件或特別的經驗和故事則會扭曲我們腦中的事前分布,影響我們的預測。

 

過度擬合 overfitting

問題:

做決定時應該要花多少心力以及考慮多少因素。要怎麼分辨學生真的了解主題還是很會考試;要如何分辨哪些員工是真正的人才而非只是照公司的重要績效指標過度擬合來工作。

 

策略:

每個決定其實都是一種預測,都必須考慮我們知道什麼(經驗)和不知道什麼(未來)。在統計科學中,納入更多因素能使模型更貼近現有資料,但不一定能做出更好的預測,模型會變得太複雜或因為納入不同的資料而出現大幅差異,或是會因為資料失準或雜訊造成誤差,這就稱為過度擬合。

 

交叉驗證是用來評估模型在看不見的資料的狀況中是否符合,可以用保留幾個現有的資料點來建立模型,再用剩餘的資料點做測試,或是使用其他評估方法的資料來測試,例如在學校辦隨機的「非標準化測試」。

 

拉索Lasso演算法讓只有對結果有明顯影響的因素才保留權重,如果建立比較複雜的模型那在解釋資料方面必須表現好上許多,才能證明它確實有必要這麼複雜。如同生物體的神經網路必須權衡效能和維持本身所需的成本,來決定神經活動的複雜度。許多器官的構造和功能並未演化到最佳功能和配置也是一種避免過度擬合的行為,以免對環境改變過度敏感。

 

啟發:

因為真實生活非常複雜,單純的試探法其實反而是理性的選擇。管理投資組合,必須正確估計各種資訊的統計特性,只要稍有誤差就可能差別很大。提出現代投資組合理論的諾貝爾獎經濟學家Harry Markowitz把他的退休金平均股債各半,而非用自己開創的效率前緣曲線做資產配置。過分追求流行趨勢也是一種對最新資料過度擬合的表現。

 

當找出最重要的因素,或是只有不確定的有限資料,那就要提前停止思考。不確定性越大,越應該盡可能簡單,避免過度擬合,浪費時間和精神也讓解決方案變得更差

 

鬆弛 Relaxation

問題:

約束最佳化問題是指如何遵循給訂的規則和記分方式,找出一組變數的最佳配置方法,例如業務員出差問題:如何規劃以最短路線經過所有城鎮但又不經過同一城鎮兩次的路徑。如果使用暴力解法列出所有可能,會花費驚人的階乘時間O(n!)。

 

策略:

如果無法在多項式時間,也就是O(n的任何次方)內解決的問題,就是「難解問題」,不論電腦運算能力多強大都無法解決。電腦科學家的方法是限制鬆弛法,先去除問題的某些限制,著手解決問題,再慢慢加回限制。

 

例如離散最佳化問題(業務員出差、找出能覆蓋地區中所有房屋的消防車停放地點、用最少最有效的方式散布訊息或施打疫苗),可以先把解答變成容許非整數的連續問題,再收斂成整數。拉氏鬆弛法則是把不可能變成高昂的代價,教我們怎麼改變規則(或是先違反規則再接受後果)。

 

啟發:

先求得理想化版本的問題,再思考現實世界的版本,從另一個方向提供解答的界限。

 

隨機性 Randomness

問題:

核子物理反應問題。接龍遊戲的獲勝機率。

 

策略:

在沒有其他方法能得出答案時,抽樣至少能優於分析,我們可以透過確保樣本為隨機和取得更多樣本來減少誤差。蒙地卡羅法是以樣本模擬取代完整機率計算的方法,當整體統計數字(平均值)或是特例的故事無法都讓我們理解過於龐大複雜的事物,抽樣研究隨機樣本可能是最有效的方法。

 

電腦科學解決問題除了權衡時間和空間,還有第三個維度:誤差機率。現代加密技術是用把只有收發雙方知道秘密質數相乘,因為把乘積分解的步驟非常困難,所以尋找和確認質數的演算法就很重要。米勒拉賓質數判定法是利用隨機演算法找出質數的方法,它無法百分之百確定,但偽陽性的比例不到10的24次方分之一。搜尋引擎的布隆過濾器則也是利用方程式來判定網頁的URL,如果可以容許1%到2%的錯誤率,將可省下大量的時間和空間。

 

隨機性也能用來解決離散最佳化問題,例如業務員出差問題,我們可以先選定每一條最短路徑,再略為更改城市的順序,選出最佳的組合(取得局部最大值),這種演算法稱為登山法。這時可以隨機做幾個小改動,看能不能接近整體最大值。IBM的科學家Kirkpatrick發明模擬退火演算法來設計晶片布局,是將尋求組合最佳化的問題類比於物理結晶過程尋求最低能量的方式,先隨機形成高溫,接著慢慢降溫,如果新狀態更優就直接修改答案,否則以一定的概率接受新狀態,從而得到一個非單峰函數的整體最大值。


raw-image


啟發:

如同演化,隨機變異和選擇性保留的過程,跳出框架,可以讓我們離開局部最佳狀態,有機會繼續追尋整體的最佳狀態。由模擬退火演算法我們也得知,採用壞點子的可能性應該與壞點子的糟糕程度成反比,另外應該越早運用隨機性,接著越來越少使用隨機性。

 

網路 Networking

問題:

人類互通聲息的基礎是協定protocol,也就是程序和預期的共通慣例,例如握手、打招呼、禮儀和社會規範,機器間也是用通訊協定來相互理解。目前網際網路最主要的通信協定是傳輸控制協定TCP。

 

策略:

人類的語音通話是連續通話,使用「回路交換」,也就是系統在傳送者和接收者間開啟一條通道,提供雙向的固定頻寬,但不適用於機器溝通。封包交換packet switching則是把訊息切割成極小的封包,再把封包合併成共有的資訊流,類似郵局寄明信片的概念,每封信是分別寄送,郵局不需要知道你和某人持續溝通了多久,可以有效率地使用頻寬,且適應力比穩定專用連線和回路交換好,網路的可靠程度隨著規模而指數提高,而非下降。

 

要怎麼知道訊息有沒有送達,在網路上以應答封包ACK確認,雙方電腦會互相傳送給對方特定的序號來確認。而當通訊中斷或延遲時,我們會使用指數退避,把嘗試重新傳送前的可能延後時間加倍,當電腦試圖連線一個當機的網站也會使用指數退讓法,避免當機的伺服器重新上線時因為要求太多而停擺,帳戶也可以運用指數延長鎖定時間避免被駭客暴力攻擊,也不會讓忘記密碼的帳號使用者永遠被拒於門外。

 

回路交換在壅塞時線路會被占滿,但網路系統中沒有任何機制可以告知發送者壅塞的狀況,TCP控制壅塞的方式稱為加法遞增乘法遞減(AIMD)的演算法,如果封包遺失時,傳輸率會降到一半,避免網路過載。AIMD是遇到得在不確定和不斷變動的環境下分配有限資源的方法。

 

啟發:

人類的語言溝通類似TCP,不是單純將書面文字當成語言,聆聽者的反應和回饋也會影響說話的人,就像ACK之於TCP一樣。

 

賽局理論 Game Theory

問題:

賽局理論的起源來自於,兩方競爭,一方獲益就是另一方的損失,數學家試圖找出均衡,也就是可供雙方遵循,並且讓雙方知道對方的行動後,也不想改變本身行動的策略。例如剪刀石頭布均衡的意思就是完全隨機出一種。

數學家John Nash證明了雙人賽局一定有均衡狀態,但沒有說明要怎麼達到這個狀態,尤其複雜程度接近真實世界的賽局中,找到均衡屬於難解問題。

 

策略:

均衡狀態不一定是讓參與者獲得最佳結果的策略,例如囚徒困境的均衡策略事都背叛,但結局是雙方都會坐牢。對一群依據自身利益採取理性行動的參與者而言,均衡或許不是最好的結果,因此演算法創造出「自主行為代價」這種度量,衡量合作(協調解決方案)和競爭(試圖取得對自己最好的結果)之間的差距。

 

有些賽局的自主行為代價不像囚徒困境那麼糟,例如網路流量控制或交通流量,大家都只想讓自己最快到達,結果自主行為代價只有4/3,也就是各行其是指比毫無阻礙地順利行進慢33%,因此網際網路就算有中央機關負責管理各別封包路徑,狀況也好不到哪裡去。

 

拍賣或是投資泡沫中的資訊瀑布是一指一群行為理性的參與者,仍然可能受到錯誤資訊左右,因為我們只能得到公開訊息(例如別人的出價),但卻錯誤解讀他們的想法,加上在乎自身判斷是否符合共識而非符合事實。

 

啟發:

量化自主行為代價可以讓我們了解這個系統需不需要細心管理和協調,例如囚徒困境或公有地悲劇從內部力量會達到惡性均衡,必須透過外部改變賽局的機制來改變均衡,而不只是單純改變賽局報酬。例如在囚徒困境增加一位教父,如果背叛就會被殺,如果合作拿到的錢需要拿一部份給老大。要鼓勵員工放假,與其給予度假獎金不如強制訂定最低休假日數,因為休假賽局中每個人都想比同事少休一點,因此均衡是完全不休假。

 

機制設計不只要考慮賽局的結果,還考慮到參與者因為遞迴思考對方想法所付出的運算心力,好的機制可以採取不需要因其他人的戰術而預期、預測或改變行動的策略。例如維克里拍賣Vickrey auction是讓所有參予者秘密寫下標金,而得標者要付的是第二高的標金,在此最佳策略是誠實,依據標的物在心中的真實價值下標。

 

臆測他人的想法是最大的運算挑戰,清楚的表達自身偏好可以分擔認知負荷,幫助群體達成決議。

 

短評:

第一次看的時候十分驚豔,畢竟是很少接觸的領域,但再看一遍又好像覺得還好,用人類發明的演算法來解釋人類的認知能力好像有些弔詭XD但把它當作認識演算法的入門書籍倒是不錯,作者的解釋淺顯易懂。

raw-image


26會員
89內容數
看完如何閱讀一本書之後,決定開始將每本書整理起來,成立這個部落格強迫自己練習維持寫作的習慣
留言0
查看全部
發表第一個留言支持創作者!