El Farol Bar problem

※此筆記可能會有一些錯誤, 歡迎大家指正:)※
前一陣子看了一本科普書, 書名是大科學[1], 對書裡面某一個章節的內容蠻有興趣的 (在另一本書隱藏的邏輯[2]中也有提及相同的內容), 因為看著看著就覺得應該可以試寫一個程式來跑跑看. 於是最近就用個幾天時間, 找了文獻及參考資料等之後, 就著手來做做看囉!! 結果還蠻順利的寫完了程式及做了一些簡單的實驗!! :D

I. Introduction
又到星期五啦~!! 想必大家一定都想在今天晚上要不要跟朋友去看一場電影?!還是要去吃頓大餐?! 又或者是去那裡喝一杯呢?! :D 有時候會覺得要決定去那個地方似乎是一件很困難的事!! 誰知道選擇去看一場電影, 到時候會不會人很多, 排隊買票要排很久, 卻有點後悔當初應該去吃頓大餐或喝一杯的!! :s 關於人們如何做決定這件事, 有沒有什麼方法可以幫助我們了解, 人們到底是如何做決定, 而且可不可做出預測? 至少, 可以讓我們想去看電影, 吃大餐或者是喝一杯時, 希望目的地的人數不要太多, 這樣子的一個小願望, 總是是被大家期待的!! :)

在 1994 年亞瑟(Brian Arthur)提出了一個艾法洛(El Farol)酒吧模型[3][4], 用一個簡單的模型來模擬人們如何做出決定. 至於為什麼會提出這個模型呢?! 科科…,原因跟大家一樣囉!! 那個時候亞瑟在新墨西哥州的聖塔菲研究院工作, 在同一條街上, 有一間名叫艾法洛的酒吧, 在每個星期二晚上都會有現場的音樂表演, 因此, 可以喝一杯並且同時欣賞現場表演, 應該是很高興的一件事!!

但是, 問題來了!! 這是一間小酒吧, 酒吧內的座位有限(假設為L). 若當亞瑟去的時候, 酒吧內的人數小於L, 那想必亞瑟當天晚上一定會過的相當愉快 (酒吧的座位未滿, 即酒吧不擁擠, 加上又有現場音樂表演, 而且應該還能夠喝上好幾杯!!). 反之, 若當亞瑟去的時候, 酒吧內的人數大於L, 亞瑟當天晚上會覺很失望, 因為酒吧太擠了!!!

在亞瑟提出酒吧模型之後, 後續就有其他的研究人員以這個模型為基礎, 加以修改並且應用在其他的問題上. 我們也可以稍為想一下, 如果就一開始提到的, 我們想去看電影, 吃大餐或喝一杯, 在這樣的情況下就包含了三種做決定的對象, 而且我們只能選擇其中的一個. 以酒吧模型來做模擬的話就會有三個酒吧, 分別代表不同決定 (看電影, 吃大餐及喝一杯). 當然, 這個情況一定會比單一酒吧的問題更來的複雜了 (若大家有興趣就再自行研究吧!!).

II. Agent-based simulation
在看過一些文獻及參考資料[5][6][7][8] 之後, 稍為整理一下前人在利用agent-based model (以代理人為基礎的模型) 做電腦模擬的時候, 使用了那些相關的設定. 在agent-based model 中, 用一個agent (代理人) 來表示一個人, 並且這個代理人會依照我們給它的設定做一些事情, 因此我們就可以用代理人來模擬一個人. 例如: 用一個代理人來模擬一隻羊, 我們設定牠在一個星期7 天中,每天都會做不同的事, 像是星期一小羊穿新衣, 星期二小羊肚子餓, 星期三小羊去爬山…等等 (猴子表示: 應該是我吧!!).

小羊版的酒吧模型之相關參數設定:
(1)程式的部份
S: 執行模擬(simulation)的次數:

(2)酒吧的部份
L: 酒吧座位的上限.
K: 僅關心過去K 個星期.
B[K]: 過去K 個星期, 去酒吧的人是否超過上限的歷史資訊 (0:沒有超過, 所以應該去酒吧; 1:超過, 所以不應該去酒吧).
例如: L=60, 表示酒吧只有60 個座位. K=3, 只關心過去3 個星期. B[]的大小為3,所以有B[0], B[1]及B[2]. 若過去3 個星期的模式(pattern)為101, 則表示B[0]=1為上上上星期不應該去酒吧, B[1]=0 為上上星期應該去酒吧, B[2]=1 為上星期不應該去酒吧.

(3)代理人的部份
N: 有多少人(代理人)會去酒吧.
P[i]: 代理人i 的決策機率, 例如: P[1]=0.9, 表示代理人1 有90%機率會做出跟上一次相同的決定.
A[i][K]: 過去K 個星期, 代理人i 所做的決定(0: 不去酒吧; 1:去酒吧).
Win[i]: 代理人i 贏的次數.
Lose[i]: 代理人i 輸的次數.
D: 代理人輸的次數超過贏的次數D 次, 則更換決策機率P[i].
H[i][j]: 代理人i 的策略, 其中有j 個歷史模式. 例如: 當K=3 時, 則j=2^3=8 個歷史模式, 即000~111 共8 個.

代理人決定輸贏的方法:
(1)代理人決定不去酒吧, 且酒吧人數未到上限, 則輸.
(2)代理人決定不去酒吧, 且酒吧人數超過上限, 則贏.
(3)代理人決定去酒吧, 且酒吧人數未到上限, 則贏.
(4)代理人決定去酒吧, 且酒吧人數超過上限, 則輸.

小羊版的模擬演算法:
1. 讀取參數設定
2. 初始化程式變數
3. 執行模擬S 次
3.1 每個代理人根據自己的歷史模式做出決策, 或更改舊有決策.
3.2 統計去酒吧的人數及給出是否該去酒吧的資訊.
3.3 判斷每個代理人的輸贏.
3.4 判斷每個代理人是否更換決策機率; 若要更換, 則隨機選取新的機率, 但不可跟舊的機率相同.
3.5 重設相關變數
4. 輸出結果

(以下為小羊之不負責任解說)

在小羊版的酒吧模型做了一些簡化, 像是每一個代理人只有一種策略, 及一種決定方式, 就是”僅根據上次遇到的歷史模式來做決定”. 例如: 這次遇到了模式(K=3) 001, 則代理人會根據從自己的策略中找到歷史模式 001 -> 1 (去酒吧) 這個模式, 再根據自己的決策機率P[i]來做決定並且加以修改.

但是, 在文獻中每一個代理人應會有多個方法來預測這次去酒吧人數, 像是方法1: 跟上星期的人數相同, 方法2: 過去K 個星期的平均人數, 方法3: 跟上上上(K=3)週的人數一樣, 方法4: 在過去6 個(2K)星期中最大的人數等, 藉此來判斷這週是否要去酒吧. 再者, 每一個方法都有一個分數, 來得知該種方法預測能力的好壞, 並且會有加減分數的判斷方式, 每一次只選分數最好的方法來預測.

最後, 在文獻中每一個代理人的策略在K=3 時, 會有000~111 共8 個歷史模式,其中以000 為例, 會對應到一個決定, 即000 -> 0 or 1. 因此, 8 個歷史模式還會有2^8=256 種策略組合. 在初始化時, 每一個代理人會從256 種策略中取S 種策略作為自己的策略, 每一種策略還會有一個分數及加減分數的判斷方式, 每一次只選分數最好的策略來使用.

(以上為小羊之不負責任解說)

III. Experiment
基於好奇心會殺死一隻羊的原因, 小羊實在是很想親自做出跟科普書[1]中提到的結果, 即:

“群眾最終會朝向兩極化 (就是群眾跟反群眾, 又或者去跟不去).”

最後在決定輸贏關鍵會落在少數人 (猶豫不決的人) 的身上. 有趣的是, 這些猶豫不決的人在輸的次數上, 會比處在兩個極端的人來的多!! (科科…, 真可憐 :p)在文獻中有研究人員將酒吧模型修改成更為簡化的模型, 稱為”少數者賽局(minority game)” (即少數者贏).

實驗1 (L=60, N=100, K=3, D=20, S=1000):
在實驗1 中, 想初步的了解科普書中所說的現象, 去酒吧的人數會在一個數值(L=60)上上下下的變化(如圖1 所示). 再者, 就是會出現最重要的兩極化 (群眾跟反群眾) 現象 (如圖2 所示). 在初始化時, 代理人的決策機率會是均勻分佈(uniform distribution), 即在第0 次模擬時. 隨著時間變化, 在第1000 次模擬時,似乎是有出現兩極化的現象, 即曲線的兩端往上升.




實驗2 (L=600, N=1000, K=5, D=20, S=100000):
在做完實驗1 之後, 總覺得圖2 的曲線不是很漂亮, 就在想是不是應做一些調整.在實驗2 中, 小羊把酒吧的座位改成600, 總共有1000 個代理人, 並且做了10萬次的模擬, 還有一些分析.

首先, 在圖3 中, 酒吧人數的平均都維持在600 人, 原因在於酒吧的座位是600個. :p 在圖4 中, 酒吧人數的標準差有逐漸下降, 我們也許可以想成是群眾越朝向兩極化, 猶豫不決的人就越來越少, 所以在圖5 中, 酒吧人數上下變化的幅度會變小.




再者, 也許是個有趣的地方, 在大約30000 次, 57500 次, 70000 次, 85000 次的附近有一種相同的模式, 當酒吧人數變化的幅度逐漸變小時, 突然間又劇烈的變化後再逐漸變小. 也許是跟代理人變更決策機率的設定方式有關, 先前有提到代理人更換新的機率時是隨機選取的.




在圖 6 中, 相較於圖2 可以發現, 曲線的變化相當明顯. 決策機率從第0 次的模擬的均勻分佈, 在第10000 次模擬時呈現兩極化的現象, 在第20000 次及100000次時則更加極端.



在圖 7 中, 以圓餅圖的方式來觀察兩極化的現像, 在圖中決策機率為0 及1 的部份 (群眾及反群眾), 會隨著時間越來越大, 其他位於中間的部份則越來越小.




--
參考文獻及資料
[1] 詹森 (N. Johnson), 大科學: 解析群眾行為、金融風暴、流行病毒、戰爭衝突背後的共通脈絡 (林俊宏譯), 天下文化.
[2] 布侃南 (M. Buchanan), 隱藏的邏輯：掌握群眾行為的不敗公式 (葉偉文譯), 天下文化.
[3] W. B. Arthur, "Inductive Reasoning and Bounded Rationality", The American Economic Review, Vol. 84, No. 2, pp. 406-411, 1994.
[4] W. B. Arthur, "Complexity and the Economy", Science, Vol. 284, pp. 107-109, 1999.
[5] S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 2nd, Prentice Hall International, 2002.
[6] Lecture - El Farol Bar Problem and the Minority Game,
http://www.ece.rutgers.edu/~marsic/books/SE/projects/MinorityGame/
[7] M. Nekovee, The El Farol Bar Problem on Complex Networks,
http://www.richardclegg.org/mon/meeting5/Nekovee.ppt
[8] Wikipedia - El Farol Bar problem,
http://en.wikipedia.org/wiki/El_Farol_Bar_problem

Self-organizing map

※此筆記可能會有一些錯誤, 歡迎大家指正:)※
這學期似乎會被學長找去代課, 聽說是要上機器學習(machine learning, ML). 什麼!! 聽到的瞬間身體不自主的抖了兩下(還好沒有漏了幾滴東西…), 剛好最近看到一篇文獻是探討類神經網路(neural network)中的Self-organizing map(SOM)與複雜網路(complex network)之間的關係(究竟SOM跟網路拓樸會擦出什麼火花呢?! 有興趣可以參閱[1]), 為了能夠稍為進入代課的狀況, 就來複習一下SOM並且寫寫筆記[4] :).

I. Introduction
SOM的全名是Self-organizing map又或著是Self-organizing feature map(SOFM), 中文翻譯成"自我組織(特徵映射)圖"網路, 不管名稱為何所說的都是同一個東西. 此方法是由T. Kohonen在1980年代所提出, 因此SOM又被稱為Kohonen network[3][4][5].

(以下為小羊之不負責任解說)

SOM的概念來源為人類大腦網路或生物網路在處理資訊時, 處理相同資訊的神經元會聚集在一起的特性, 簡單來說就是會有一個個區域的樣子. 例如: 給一隻羊看草原的照片並且同時給牠照fMRI, 我們會發現其腦部有一些特定的區域會對草原有反應. 圖1與圖2為fMRI及SOM, 互相對照之下, 可以觀察看看兩者有何相似之處.


(以上為小羊之不負責任解說)

II. Self-organizing map
SOM有一個很重要的優點為, 將N維(N-dimension)的資料映射(mapping)到2維(2-dimension)的空間上(如圖3所示)並且維持資料中的拓撲(topology)特性.將資料映射到2 維空間時則可以使用視覺化(visualization)的方式呈現, 以方便後續的觀察及分析.



舉個例子, 假設我們想要了解全世界各地所有不同品種的羊之間的關係為何, 若總共有5個品種(a.亞洲, b.非洲, c.歐洲, d.美洲及e.大洋洲), 每一個品種都有5個屬性(5維). 對每一個品種收集100 隻羊的資料, 因此資料總數為500 筆. 接下來我們利用SOM 將5維的資料映射到2維的空間上, 以視覺化的方式來呈現這5個品種的羊之間的拓樸關係.

SOM 演算法(參考至[2]及[5]):
1. 初始化(initialization)
2. 輸入資料集(dataset)
3. 從資料集挑選一個pattern 並尋找距離最近的神經元為winner
4. 更新winner 神經元的權重及其鄰近神經元
5. 重複步驟3~4, 且迴圈步數 step=2 至結束

接下來我們定義 SOM 演算法中的必要元件(公式):
1.距離函數(distance function),
2.學習規則(learning rule),
3.核心函數(kernel function),
4.鄰近函數(neighborhood function),
5.學習率函數(learning-rate function),
6.函數及
7. 鄰近範圍的形狀(shape of neighborhood).

首先, 定義距離函數, 學習規則及核心函數.
1.距離函數(歐幾里德距離):


其中是目前的pattern i, 是2維Map上的神經元 j. 距離函數是用來找出距離目前patter最近的神經元並成為winner神經元, 隨後根據鄰近函數更新winner神經元的鄰近其他神經元.

2.學習規則:


其中為神經元 j 在時間 t 時的權重, 為神經元 j 在時間 t 時的核心函數, 為目前所選的 pattern, 為時間 t 時的鄰近範圍之大小.

3.核心函數:


包含了學習率函數及函數, 核心函數會隨著時間 t 變化, 參考常態分佈(Normal distribution)的在不同參數下的曲線變化之後[8], 則我們可以感覺一下是如何更新winner神經元的鄰近其他神經元之權重.

再者, 定義學習率函數, 函數及鄰近函數, 這三個函數通常都定義成單調的(monotonic)遞減的函數. 第一種定義的方式為參考相關文獻[3], 第二種定義的方式則是簡單的方式, 可以從下圖看出其中差異.



4.學習率函數:




其中 為學習率的初始值, 為總迴圈數.

5. 函數:




其中為的初始值, 為總迴圈數.

6.鄰近函數:




其中為鄰近函數的初始值, 為總迴圈數.

最後, 對於鄰近範圍的形狀可以定義成正方形(square)或六角形.

7.鄰近範圍的形狀:



III. Experiment
接下來我們來做點小實驗來體驗一下SOM :D. 首先, 從UCI Machine Learning Repository下載Iris資料集(http://archive.ics.uci.edu/ml/datasets/Iris, 簡單的介紹此資料集, 總共有150筆資料, 每一筆資料有4個屬性(包含sepal length, sepal width, petal length, petal width及class)及3種類別(Iris setosa, Iris versicolour及Iris virginica). 例如: 第35筆資料為4.9,3.1,1.5,0.2,"Iris-setosa".

當想要了解Iris資料集在2維平面上的樣子為何, 我們將屬性兩兩一組並且利用Excel畫出散佈來觀察. 例如: 圖6的x軸為sepal length為及y軸為sepal width.



但是, 當資料集的屬性變多時, 想要畫出所有的散佈圖是相當累人的工作. 此時, SOM就派上用場了, 我們僅需觀察SOM將多維資料映射到2維空間之後的結果就可以了(如圖7), 所以使用SOM是相當的方便.


--
參考文獻及資料
[1] F. Jiang, H. Berry, and M. Schoenauer, "The impact of network topology on self-organizing maps," Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, pp.247–254, 2009.
[2] K. A. Smith and A. Ng, "Web page clustering using a self-organizing map of user navigation patterns," Decision Support Systems, Vol. 35, pp. 245– 256, 2003.
[3] T. Kohonen, “The Self-organizing map,” Proceedings of the IEEE, Vol. 78, No. 9, pp.1464-1480, Sep. 1990.
[4] Lecture - Neural Network I: Fundamental Theory and Applications, The University of Aizu.
[5] Wikipedia - Self-organizing map,
http://en.wikipedia.org/wiki/Self-organizing_map
[6] Human brain,
http://en.wikipedia.org/wiki/Human_brain
[7] ai-junkie - Kohonen's Self Organizing Feature Map,
http://www.ai-junkie.com/ann/som/som1.html
[8] Wikipedia - Normal distribution, http://en.wikipedia.org/wiki/Gaussian_distribution

Nicholas Christakis: The hidden influence of social networks

Nicholas Christakis: How social networks predict epidemics

CNN - Small world experiment

--
參考資料:
Social Networking in Plain English

CNN - Flu spread model

這是一個CNN報導有關流感的電腦模擬模型; 首先, 提到如果沒有任何的防疫措施情形下, 大約會流行3個月左右, 至少會有半數的人會感染. 再來, 施行預防性投藥(克流感)措施之後, 會使得疫情延後發生, 但並非使其不發生. 接著, 施行疫苗政策之後疫情也還是會緩慢的發生, 如同前一個措施. 緊接著, 對空中交通做管制的話, 似乎對疫情的發生沒有什麼太大的作用. 最後一個我想應該是減少一些社交活動, 避免人與人之間的接觸.

--
參考資料:
另一則報導:
Computer model of how virus will spread

註:H1N1 flu = Swine flu

第六感驚人的潛力PranavMistry(中文）

--
原文影片:
Pranav Mistry: The thrilling potential of SixthSense technology