SIC ITUR AD ASTRA

初始3個菌點經過80單位時間後形成的菌落 利用電腦模擬真實世界的情況，不僅僅是電腦科學家，還包含了物理學家、生物學家、化學家和多種領域專家有志一同的想法。自然界千變萬化，圖騰多樣，但或許它們都可以從幾個簡單的規則當中得到答案， 這便是所謂的湧現現象 (emergence phenomenon)。 我們來看個簡單的例子，黴菌菌落的增值過程。 一、菌落的消長 用一個\(N\times N\)的區域代表一整片的培養區域如圖1，這個區域裡有比例\(q\)的部份是培養基質可以生長出黴菌 (淺綠)，剩下的區域則不能長出黴菌 (白色)，假設長出和不能長出的區域是隨機分佈的，那麼我隨意在這片區域灑上幾個菌點 (墨綠色)，是問它們發展成菌落的過程為何？ 圖1. 培養區域，淺綠是含有生長基質的區域，白色不能生長，墨綠色表示初始的5個隨機菌點 　這個問題和Prof. Downey在他的著作Think Complexity的第七章在描述滲透的情況基本上一模一樣，除了關鍵的黴菌生長需要引入額外的判定條件外，所以我會依照Prof. Downey的方式來做，最後在引入這個判定生長的條件。欲執行這個雜記的notebook，我需要下載Prof. Downey所寫的一個 python 腳本 Cell2D.py ，可以從雜記的notebook裡直接點連結。這個腳本主要是需要其中的 Cell2DViewer 類來將黴菌菌落的消長輸出成動畫，如果只需要用 imshow 看特定時刻的結果，引入 Cell2D.py 不是必須的，但如果想執行本篇雜記的notebook第一個擴散的例子，則需要有其中的 Cell2D 類。 1.1 預備知識 如果說以圖1其中一個淺綠的基質為中心 (Eq. (1)的\(?\)處)，那麼它週邊\(3\times 3\)的區域內4個東南西北 (不含對角線方向：東南、東北……等等) 的方向可能含有黴菌或不含有黴菌，如下 \[ \begin{array}{ccc} \times & {\rm 黴} & \times\\ {\rm 無} & ? & {\rm 無}\\ \times & {\rm 無} & \times \end{array}\tag{1} \] 所以我們想知道如果它周圍有一個以上的菌點，

生命遊戲 (Game of Life, GoL)，取自維基百科 元胞自動機 (cellular automaton，複數automata，縮寫CA) 由John von Neumann在上個世紀50年代所提出，希望能用來模擬生物自我複製的情況，然後到了70年代由John Conway設計了生命遊戲 (Game of Life, GoL) 並刊上了科學美國人後才逐漸吸引其他研究者的目光。而在80年代由天才科學家，也是知名數學套件Mathematica®的開發者Stephen Wolfram利用統計力學的方式做了一系列的研究後，我們才對這類型的計算理論與結果有了系統性的理解。 一、元胞自動機的演化規則 CA通常由包含了\(N\)個元素的一維陣列所組成，每個元素不是\(1\)便是\(0\)。用比較圖像化的形式，將每個元素都想像成一個細胞，每個細胞不是黑\(1\)就是白\(0\)的兩種狀態，而整個陣列便代表在時間\(t\)時由\(N\)個細胞所構成的假想生物體的狀態，當然這個假想生物體就是由一系列\({\tt 101000100}\cdots\)來描述。 　現在這個生物體的狀態由時間\(t\)演化到\(t+1\)，那麼在\(t+1\)時這個生物體的每個細胞是處在\(1\)或\(0\)則由上一步的它自己與它左右兩個鄰居的狀態來決定，如下： \[ \begin{array}{cccccc} t & \cdots & {\tt 1} & {\tt 0} & {\tt 1} & \cdots\\ & & \searrow & \downarrow & \swarrow\\ t+1 & & & ? \end{array} \] 可以看見在\(t\)時三個相鄰的細胞狀態分別是\({\tt 101}\)，則處在\(0\)的那個細胞它在\(t+1\)時則由它自己原來的狀態\(0\)，以及鄰近那兩個處在\(1\)的細胞來決定。 　所以說任三個相鄰細胞的狀態，可以決定中間那個細胞在下一個時刻時的狀態，由於每個細胞可以處在\(0\)和\(1\)兩種情況，三個細胞變有\(2^3=8\)種可能的組合： \[ \begin{array}{ccccccccc} t &

位於美國新墨西哥州的甚大天線陣列 (Very Large Array, VLA) 資訊 (information) 的傳遞在人類文明演進的歷史中扮演著極重要的角色，不僅僅是知識、技能，更是讓文化以及思想的瑰寶得以傳承，縱然生命會消逝，但前人所建立起的經驗卻能夠代代相傳給往後的人們。這些知識、技能和思想都可以歸納成資訊的一種，而在資訊遞交給後代的過程就稱做傳輸 (transmission)。傳輸不見得是保真的，亦即後代的人們所讀到前人的著作可能有多種版本，例如莎士比亞 (W. Shakespear) 的著作全集就有多種版本在流通，又或是1631年的邪惡聖經 (Wicked Bible) 事件，印刷廠將十誡中的 Thou shalt not commit adultery (不可姦淫) 誤植成 Thou shalt commit adultery (應當姦淫)。這些都是資訊在傳遞的過程當中發生失真，大部分的失真皆無大礙，並不影響資料原來意義的解讀，但少部分的失真卻是重大的，可能導致文意生變，甚至完全與當時書寫者的核心概念大相徑庭。所以既然失誤不可避免，有沒有什麼方法能讓我們盡可能的重建出原始資料的樣貌呢？ 一、訊號的傳遞 讓我們來看看資料是怎麼傳輸的，以通電話為例 (圖1)，當你朋友撥手機給你時，他的聲音會被手機錄下並編碼，接著通過基地台、電信機房，再到離你最近的基地台將訊號廣播出去，你的手機收到訊號後將之解碼重新轉成類比音訊，再透過喇叭將你朋友的聲音播放給你聽，同時地，若換你說話，則這個過程將逆向發生！ 圖1. 聲音訊號如何透過手機傳到朋友的手機或話筒上，補充一下當代手機的編解碼的方式是利用類似貝氏機率的方式去重建可能的原始訊號，不是這篇專題內提到的\(R_r\)編碼 　但注意訊號在傳遞的過程可能失真，就像你聽到手機播放你朋友的聲音時，總會覺得不像是親耳聆聽他的聲音一樣清晰，像隔著一層簾幕一樣，或甚至音調也有一些變化，有時背景還會傳來微若的雜訊滋滋聲。這便是圖1中間紫色虛線框裡描述的，當訊號透過層層基地台、電信機房時，原始的訊號發生了失真，可能被干擾了，或位元流失、誤植⋯等等，如果你的手機收到這樣破損的訊號，它甚至可能沒辦法重新解讀成類比音訊撥放給你聽。這時候，在一開始你朋友的手機做了一件事，那就是不僅僅是將你朋友的聲音送出去

哈伯深空圖像 (NASA/ESA/S. Beckwith(STScI) and The HUDF Team) 根據宇宙學原理 (cosmological principle)，一般相信宇宙在大尺度底下 (>Mpc) 是均勻 (homogeneous) 且各向同性 (isotropic) 的，亦即宇宙不存在中心，就像在球的表面上行走一樣，我們不會找到哪個地方在球面上有特別突出的重要性一樣，另外在宇宙各處的物質密度也應該是均等的。這樣均勻、公正且不偏頗的特性，同樣的也在統計取樣中，特別是沒有任何先驗資訊底下扮演了重要的角色。這裡我們回顧上個專題I&A2中生成任意維度單位球面上點的例子，我們以為生成的點是均勻地散布在球面上，但實際上這是一個錯覺，為什麼我們生成\((x,y)\)的座標明明就是均勻的分佈，但最後會導致不均勻，或不對稱性的發生呢？ 一、均勻性 讓我們回想一下上一個專題談到的均勻性，我們用二維單位圓上的點的例子來舉例比較容易想像。見下圖1，為了產生在單位圓上的點，我們可以隨機生成\((x,y)\)分別在\((-1,1)\)之間的點並正歸化它們，以形成單位圓上的點，而向量\((x,y)\)則用於決定在極座標上的角度\(\phi\)。可是從圖1會很明顯的發現紫色的點它們都是對應到相同的\(\phi\)角，而綠色的則是角度為\(\pi/2\)，但由於\(\phi\)的位置的點可以超出單位圓，所以產生在\(\phi\)這個角度的單位圓上的點，實際上是比角\(\pi/2\)上的綠點來得多。亦即I&A2的算法2其實生成的並不是均勻分布的點，比如說在\(\phi=(\frac{\pi}{4},\frac{3\pi}{4},\frac{5\pi}{4},\frac{7\pi}{4})\)處的點 (二維的例子剛好在這裡的點是最多的) 會多於\(\phi=(0,\frac{\pi}{2},\pi,\frac{3\pi}{2})\)的點 (這裡的點是最少的)。 圖1. 藉由平均分佈生成單位原上的點，以及各個角度\(\phi\)所對應點出現的機率 　我們可以重新run一次I&A2的算法2，取\({\tt dim}=2\)，然後利用 \[ \phi = \tan^{-1}\left(\frac{x}{y}\right

馬可夫過程 (Markov process) 生成三維球面上的點，此時點的位置不是均勻分佈，而是猶如醉漢走路 (drunkard's walk) 的情況。馬可夫過程在針對自然界運作或是社會結構演變的模擬中扮演著核心的角色！ 一、二維圓盤的case 這次的專題非常簡單，我們先從二維的情況開始，二維球面上的點即為是分散在圓周上的點。我們知道如何產生散布在\((x,y)\)上的點 (圖1)，但如何將之收縮到單位圓的圓周上呢？ 圖1.  均勻散布在邊長為1的正方形內的藍點以及單位圓 (紅) 的範圍 　在圖1我們產生了1000個點，以及對應單位圓圈起來的面積。這次我們並不是要估計\(\pi\)，而是要找出哪些點分佈在紅色的圓周上，亦即產生出散布在單位圓上的點。你可能想說可以用以下的方式來實現 (以二維的case為例)： 產生\(N\)的點的座標分別在\((-1,1)\)之間 \(x={\tt rand}(-1,1)\) \(y={\tt rand}(-1,1)\) \({\tt if}~(x^2+y^2=1):~{\tt return}~(x,y)\) \({\tt else:~return}~0\) 上述的算法在第2步就是去篩出隨機生成的\(N\)個點中，哪些是符合半徑等於\(1\)的狀況 (即這些點在紅色的圓上)，如果不等於\(1\)則將之刪去。我不做計算，但我可以打包票，上面的算法接受率 (acceptance rate) 是超級低，生成數以萬計的點可能都不見得有一個是符合半徑等於\(1\)的條件。 　但換個角度來看生成的點，點座標\((x,y)\)其實也代表著向量，既然單位圓有半徑為\(1\)，我們只要將每個點的向量都做歸一化的動作，我們就可以得到單位向量\((x^\prime,y^\prime)\) (即向量距原點的長度為\(1\))，所以可以保證歸一化後的單位向量一定會在圖1的紅色圓上，而未歸一化前的點座標則用來決定在極座標上的角度\(\phi\)，即 \[ \phi=\tan^{-1}\left(\frac{y}{x}\right). \] 示意圖如圖2。這樣不僅保證所有的點都在單位圓上，又由於點是隨機生成的，在圓周上的位置\(\phi\)也是在\(0\)和\(2\pi\)之間均勻分佈。 圖2. 歸

Mathematica®生成400根針的隨機投放示意圖 布豐投針問題 (Buffon's needle problem) 是這樣敘述的： 有一房間的地板由數片平行並列的木板所構成，板與板之間溝紋的距離皆相同，如上圖棕色隔線的間距。試問隨機扔一針，該針觸及溝紋的機率為何？ 這項問題主要由18世紀的布豐伯爵所提出的，並由義大利數學家Mario Lazzarini在1901年實地進行拋針實驗，共拋出了3,408根針(🥴)並計算出\(\pi\)的近似值約為\(355/113\)，參見 維基百科 。在我們繼續追本溯源這個歷史問題以前，讓我們先看看當代最常見估計圓周率的方法。 一、灑點估計法 這個方法概念非常的簡單，我們將產生\(N\)個座標\((x,y)\)隨機散佈在\(0\)和\(1\)之間的點，所這些點將被包在以原點為中心，邊長為2的正方形的第一象限中 (first quarter)。接著我們計算出每個點距原點的長度\(d=\sqrt{x^2+y^2}\)，若\(d<1\)則紀錄，反之則丟棄，最後我們紀錄了\(n\)個點，這些點都被包在以原點為中心，半徑為\(1\)的\(1/4\)圓內，見圖1。 圖1. 在第一象限中藍色正方形的面積為\(1\)而紅色區域的面積為圓的\(1/4\) 　現在我們相信這些處於單位圓內點的數量和全部點的數量的比值應等於那\(1/4\)圓面積和正方形面積之比，即 \[ \frac{n}{N}=\frac{A_圓}{A_方}.\tag{1} \] 而\(A_正 = 1^2\)和\(A_圓=\pi 1^2/4\)，所以我們便得到了 \[ \pi = 4\frac{n}{N},\tag{2} \] 正是\(\pi\)的估計。我們預測若\(N\)愈大，則其估計值愈接近真正的圓周率。另外\(\pi\)可以解析表示成 \[ \pi = \int_{-1}^{1}\frac{dx}{\sqrt{1-x^2}}. \tag{3} \] 上式是由現代分析學之父卡爾·魏爾斯特拉斯 (Karl T. W. Weierstraß, 1815-1897) 在1841年所定義的。 　我們接著可以透過 rand 來實現這個簡單的蒙地卡羅模擬，腳本如下： import numpy as np import matp

藝術化的元胞自動機 (cellular automaton)，取自 Softology's blog 在今年初我在自己的這個部落格開了一個關於機率與統計 (P&S) 的系列，是包含了我自己學習古典機率的心得，後來再加上由於計算機效能長足進步後日漸興起的貝氏推論 (Bayesian inference) 的應用。在研習的過程當中，我感到許多的內容與統計力學和計算機理論是緊密相連的 (必然如此，這些學問都是嘗試去理解大自然的方法，也許從不同的立足點出發，但最終它們想攻剋的都是同一做山頭)，所以不僅僅重新讀了以前懵懵懂懂的統計力學，還對資訊理論以及這些算法做了不少功課，我看見所有的學問都是一脈相承、自有而擁有的，包含最近這幾年不斷引起大眾耳目的人工智慧，以及在推論領域中已穩紮穩打許久的資料科學。 　所以雖然P&S我還沒認為應該結束這個系列，但我想再開一個資訊與算法 ( I nformation & A lgorithm, IA ) 的專題。不像PS系列，在這裡我應該會著重在我研讀這類資料的時候遇到的問題如何解決，以及已經解決的問題，我能夠用簡單的程式腳本來實現，所以這個系列每篇都如同一個小專題一樣，而不是我循序漸進的學習過程。 　這類的問題像是圓周率\(\pi\)的估計，除了耳熟能詳的用computer隨機產生一堆點然後計算有多少落在半徑為1的圓內來估計外，我們也要提及幾乎被遺忘的18世紀法國布豐伯爵 (Georges-Louis Leclerc, Comte de Buffon, 1707-1788)，他發明了布豐投針 (Buffon's needles) 估計\(\pi\)的蒙地卡羅方法 (Monte-Carlo method)。不像是傳統邏輯符號的推論，蒙地卡羅模擬 (Monte-Carlo simulation) 在於能用大自然處理事情的方式來估計未知的參數，或是推論可能發生的情況，而當代硬體計算效能之強大，即使在一台簡便的筆記型電腦上也足以處理這些運算，甚至得出精細的結果，所以電腦是實現蒙地卡羅模擬非常好的工具。除此之外，這個系列也包含了我遇到一些有趣的演算法，除了實踐它們外，我希望能逆向找出這類模擬背後的數理邏輯。 　至於原本的P&S系列，我最想談的還是Bayesian analysis，

當我們說處在海平面為0的時候，亦即以海的平面為基準當作高度為0 (基平面)，例如玉山高度3,925公尺便是高於海面3,925公尺。不過當我們望向一望無際的海面，所有的水分子都處在這個為0的基平面上嗎？原則上這些水分子會以這個基平面為準做上下的震盪，而若我們把所有的水分子在某一瞬間偏離這個平面的高度 (含低於基平面的高度，取負值) 總和的平均，我們會得到非常接近0的值。所以所謂的海平面是一個平均的概念，而真實的水分子會因為熱運動不斷上下偏離這個平均，但其總和仍為0，而這個偏離的行為我們便稱作 漲落 (fluctuation)。 　我們回到杯水的例子，給定宏觀的狀態\(N\)、\(V\)和\(T\)後雖然水分子的平均能量是\(\bar{E}=3k_B T/2\)，但每個水分子真正的能量\(E\)卻是是落在\(0\)到\(\infty\)之間，所以其能量的分佈可用正則分佈來描述。而在眾多的水分子當中，即便都是能量\(E\)也可能有不同的內在狀態 (intrinsic properties)，像是自旋等等，對於這種多個分子共享相同能量確有不同內在狀態的情況我們稱做 簡併 (degenerate)。考慮了簡併後的正則分佈可以改寫成 \[ p(E)=\frac{g(E)e^{-\beta E}}{\mathcal{Z}},\tag{7.1} \] 其中\(\mathcal{Z}=\int g(E) e^{-\beta E}dE\)為配分函數而\(g(E)\)表示在能量為\(E\)時有多少水分子處於簡併的狀態，它是能量\(E\)的函數，也叫做 態密度 (density of state)。這裡用積分表示由於分子數量眾多，所以能量間隔可以考慮成連續譜的狀態。 　原則上\(e^{\beta E}\)是個隨能量遞減的單調函數，而態密度\(g(E)\)則隨能量遞增，一個遞增一個遞減相乘在一起會產生一個極值，而極值的位置則由 \[ \left. \frac{\partial \{g(E)e^{-\beta E}\}}{\partial E}\right|_{E=E^*}=0 \to \left. \frac{\partial \ln g(E)}{\partial E}\right|_{E=E^*}=\beta \] 決定。另外當\(E\)給定後，這個系統的熵正比於簡併態

高爾頓板，或稱做quincunx，是由Galton爵士 (1822-1911) 所發明用來驗證中央極限定理 (CLT) 的裝置。它也是第一位討論均值回歸 (regression to the mean) 現象的科學家，但同時亦是優生學 (eugenics) 這樣錯誤觀念的推廣者 在 上篇雜記 的結尾我們提到了對於一個趨於穩態的系統擁有最大的熵，而這也是統計力學的直接應用，用物理的角度來講便是當系統平衡時 Gibbs 自由能不再變化 (\(\Delta G =0\))，而在此時會對應到系統的熵有全域極大值 (global maximum)。故大自然很多現象都已經處於穩態的狀況下，我們對這個現象的母體做抽樣，所得到的觀測樣本應也有最大熵，則描述這些觀測樣本最好的分佈便是符合該條件下擁有最大熵的機率分佈。而指數族的分佈符合最大熵的特點，我們在這個小專題內便嘗試證明高斯與二項式分佈在連續和離散的隨機變量下的條件擁有最大熵的性質。 一、機率熵 在 上篇雜記 裡裡我們探討了夏儂熵，或者稱作資訊量\(I\)的意含，所以一個系統內 (我們這裡就不再用系綜這種彆扭的歷史名詞了) 每個成員出現的機率是\(p_i\)，則對該系統的熵可以用夏儂熵公式來表示 \[ I(p) = -\sum_i p_i \ln p_i. \tag{7.1} \] 所以對某一組 連續 機率分佈函數\(p(x)\)，其中\(x\)是隨機變量，則將(7.1)的求和符號改成積分後有 \[ I(p) = -\int p(x)\ln p(x) dx, \tag{7.2} \] 稱為機率分佈\(p(x)\)的 機率熵 ，而積分的上下限則看隨機變量的範圍，例如高斯分佈就是\(\pm \infty\)。如果今天我們有兩組機率分佈\(p(x)\)和\(q(x)\)，我們便可以定義它們之間的 相對熵 ，或稱作 KL散度 (Kullback-Leibler divergence)，定義為 \[ D_{KL}(q,p)\equiv\int q(x)\ln \left(\frac{q(x)}{p(x)}\right) dx = I(q,p)-I(q)\geq 0, \tag{7.3} \] 是 正定的 (positively defined)，其中 \[ I(q,p)=-\int q(x)\ln p(x) d

在前面的幾篇文章裡面我討論到一些機率的問題時提到了Shannon entropy來決定least informative prior的技巧，在這篇雜記裡我想要對Shannon entropy做一些探討。Shannon entropy源自於C. E. Shannon在資訊理論上的工作，特別是引入了統計力學對一個物理系統微觀狀態上的觀點。所以在這裡，我想從統計力學的角度推導出Shannon entropy或者稱作資訊量\(I\)的關係式\[I = -\sum_i p_i \ln p_i\]並且探討一些關於資訊理論的簡單問題。 一、系統的狀態 統計力學主要在是從微觀的角度來推論出巨觀的所有現象學上的熱力學特性，這些巨觀的特性諸如壓力\(P\)、內能\(U\)、熵\(S\)和定容或定壓比熱\(C_P\)、\(C_V\)...等等。我們這裡並不去討論如何推導這些特性，我們只要知道為了得出這些特性，我們必須了解系統現在到底處在什麼樣的狀態上。 　舉例來說，桌上裝滿水的杯子，杯子體積是\(V\)且有\(N\)個水分子 (已知水的質量便可以除上水分子的莫爾質量乘上Avogadro常數得到總水分子數\(N\))，假設它已經和室溫\(T\)達成熱平衡，那麼我從中取出任意個水分子，試問該水分子的動能為何？下方我們皆以能量\(E\)來代稱動能。學過普通物理學也許會認為每個水分子的能量是\[\bar{E}=\frac{3}{2}k_B T \tag{7.1}\]其中\(k_B\)為Boltzmann constant。答案是的沒錯，但注意到我們取的是\(\bar{E}\)即平均能量，表示若我測量了無數個水分子的能量，那麼平均來講每個水分子會帶有\(\bar{E}\)，不過對任意個水分子而言，他所帶的能量是在0到\(\infty\)中隨機賦值，這表示所有測量的結果\(E\)是一組統計上的隨機變量 (random variable)。所以這個問題便回到了在一給定的杯水的巨觀狀態\(N\)、\(V\)和\(T\)後，任意取出一個水分子的能量\(E\)的值最有可能為何？而這可以由\(E\)的機率分佈函數來決定。熟悉統計力學的人便可以馬上領會到，這個杯水對應到的是 正則系綜 1 (canonical ensemble)，而每個水分子則是構成該系綜的成員 (members) 之一