不太記得第一次遇到「熵」是什麼時候了。
無比確定國高中有遇到過，但毫無印象為什麼。據說大一修普物也會遇到，但身為一個大學幾乎從來不上課、普物下被當的人，當然連「熵」有教這件事也毫不知情。
最有印象的是，大四修ＣＡＤ的時候，要最佳化電路的時候有用到一個演算法，裡面有「熵」。嗯，但是那次的作業記得只要照著講義把演算法弄成code就好，我管他「熵」是什麼鬼。
前陣子被推坑（心不甘情不願地）去讀「數學之美」。這書名真的不好。一開始覺得這本書大概都是數學，後來發現他是在講資訊處理…都是非常ＣＳ的東西：NLP、搜尋、ranking之類的 — 而且幾乎沒放需要知道的數學 — 是一本告訴你「不知道數學難怪你不懂這個為什麼是這樣拉哈哈哈」、擅長嘲諷的書。「數學之美」大都是在簡介一些東西怎麼做…還有那些技巧跟數學的關係。如上所述，因為數學細節的部分都被極為簡略地一筆帶過，所以本來就懂一點點這些領域的人可能會覺得讀起來有一點點搔不到癢處。不過，書裡反覆提到的「資訊論」倒是成功地吸引了我的注意…也就只是吸引了注意而已。：）
接著看了一本談複雜系統的書「直視全貌」。
這本在goodreads上3.7分的書，其實比我以前看過的三四本也談複雜系統的書在架構上好了非常多…因為架構很好，所以可以忽略細節過少的小缺點…雖然看完還是覺得餓，但至少是精緻的一餐的感覺（是說這本每一章都讓我想到ＣＳ，之後也打算來為了這本書寫個幾篇…）。「直視全貌」的兩個章節也引發了我對「雜訊」跟「隨機」的好奇，尤其是蒙地卡羅演算法的部分…一樣是因為他什麼細節都不寫的關係。：）
然後發現我的書架上不就剛好有一本買了兩次但始終沒看的書嗎！
所以這本「資訊：一段歷史，一個理論，一股洪流」，就讓我踏入了享樂（？）的查資料地獄。(❍ᴥ❍ʋ)
上面是動機…所以要接章節介紹。：）（你自以為在寫論文嗎！！）
接下來會先解釋隨機的定義，哪些學者做過哪些事，主要是看了「資訊」一書的第十二章所整理出來的（因為書本人寫的非常讓我混亂…只好自己寫一次）。接著講熵的演進，從熱力學、資訊論、然後講一點點量子資訊論。最後講隨機的用途，這部分主要會結合在「直視全貌」和「決斷的演算」看到的東西來寫，但大概不會寫得很細。
最後會講一下小小的心得跟這裡沒cover到，但其實想細細寫下來的相關東西…沒錯，就是future work。：）
隨機的定義
首先，什麼是隨機呢？
隨便找一個人來定義隨機，可能大都會用隨機的反面來定義隨機：秩序。有因果關係的、有模式的、看起來整齊的、不亂七八糟的…就不是隨機吧？且不論心理學上發現，人們有多擅長從混亂中找出模式 — 就算並沒有這種模式（大概可以放個三四本書來講）; 這種隨機，可以是嚴謹的科學定義嗎？這種「主觀」的隨機，難道不會因人或因時而異嗎？對混沌理論打下基礎的學者龐加萊說得好，「如果說看不出模式就說是隨機的話…以前天文學家也以為天體運動是隨機啊。」（其實我也不確定他精確是不是這樣說的。）
表面的隨機可能是雜訊，也可能有深層複雜的動力因素。無知是主觀的，是觀察者的屬性。隨機假如真的存在，照理應該是事物的本質。
出自「資訊：一段歷史、一個理論、一股洪流」
那麼，假設要為隨機找到…本質、找到一個科學定義，它應該是什麼呢？
首先先放一張export出來（又）醜醜的圖。ＱＱ
這大概…可以說是「資訊」一書裡，列出各種去定義的嘗試。我把他們畫在一起感覺比較好懂…還貼心地編了號！
首先看1。顯然，直接從觀察（observations）去觀察一個東西 (stuff，各個學者都有志一同把它先當作一個數字，放在數學這個形式系統裡來簡化問題)，就會遇到上面說的「主觀」或「無知」的問題 — 這是在科學上是行不通的。
從觀察「科學地」獲得模式的方法 — 可以說是統計（statistics）了吧！那麼，可以從統計推論一個東西是不是隨機的嗎？
許多人在2這條線做了嘗試，但很悲傷地，很快就出現了反例 — 統計上是normalized的數字，但其實是有「模式」的：譬如Champernowne number、譬如π。這個數字印出來（3.1415926…)，根本在統計上看不出什麼特別的模式 — 但顯然這傢伙是π、是「有意義」的、認識它的人看到這串數字自動就知道這串數字是個「模式」 — 於是這顯然也不是隨機的。
不過，就有人說啦，你要知道這串數字不是隨機，前提是你有這「知識」，知道π長什麼樣吧？這，就是3這條線了 — 想要從一堆數據、一堆觀察，透過一些數學方法…找到產生數字的方式。
「如果找得到產生這個東西的方式，那，他就不是隨機了吧？」
嗯，這就是索羅門諾夫（Ray Solomonoff）想要做的事。
索羅門諾夫問了個問題：「給定一系列觀察，人要如何做出最佳預測知道接下來要發生什麼？」 — 看起來很ML/AI吧？沒錯，他就是AI的先驅之一。他嘗試想要從一堆對某個東西的「觀察」中找出「模式」，以推斷這個東西是不是隨機的。找到之後，這模式當然就可以拿來用了 — 譬如說以這模式預測未來。
這聽起來很合理（嗎？）可是，有（好幾個）奇怪的人問了，真的所有的數字，都可以被產生出來嗎？這是個奇妙的問題。因為如果有數字連產生都不能被產生出來…你用產生方法來定義數字是不是隨機有用嗎？橫豎有些數字根本就不能被產生啊？
這裏要注意的是，隨機數字是可以被產生出來的。只是比起有「模式」的非隨機數字，他產生出來的方式可能是…直接把整個數字印出來。譬如說，假設12345是隨機好了（雖然這邊他顯然不是），我產生這個隨機數字的方式就是直接印「12345」，他沒有其他的「模式」，他就是他本人，混亂本身就是混亂自己。
所以這邊的假設是，東西（stuff），或數字，可能不是 （（隨機）＋（非隨機）），可能是（（可以被產生）＋（不能被產生））=（（（隨機）＋（非隨機））＋（不能被產生））。那，不能被產生的那些人怎麼辦！你要怎麼定義他們？
這就是可計算性問題。
雖然我這裡的寫法很像是因為想定義隨機才去問可計算性問題，但以時間軸來看其實並不是如此…而真的是已經有好幾個奇怪的人（希爾伯斯 Hilbert, 哥德爾 Gödel, 圖靈Turing），本來就在想這問題…只是剛好有兩個叫查丁（Gregory Chaitin）跟柯爾莫哥洛夫（Andrey Kolmogorov）的人，分別在地球的兩端，把可計算性問題跟隨機放在一起問了。這就是圖上的4跟5。
查丁（Gregory Chaitin）跟柯爾莫哥洛夫（Andrey Kolmogorov）有個東西叫做 柯爾莫哥洛夫-查丁複雜度（Kolmogorov-Chaitin complexity, 亦作隨機複雜度、描述複雜性，或演算法熵）。
查丁跟柯爾莫哥洛夫兩個人雖然都是在討論generation跟number的關係，但圖上有兩條線 — 因為他們是從不同的角度在看這一件事。
柯爾莫哥洛夫問，假設產生的方式一樣（用同一台圖靈機），那我有辦法度量兩個數誰比誰更複雜嗎？ — 我的度量方式，就是找出誰用比較短的機器語言（程式）把數產生出來。
查丁問，假設拿到一個數字，我怎麼知道它可不可以被產生或以被更短的方式產生出來（除了直接把它全部印出來）。
「用演算法來定義隨機，讓資訊也能用演算法來定義：演算法的大小代表一個字串含有多少資訊。」
顯然，查丁的說法比較受到資訊論影響，但柯爾莫哥洛夫與殊途同歸。
從上面這串可以發現，其實有三個人從這張圖的不同角度問了不同的問題：
- 索羅門諾夫：「想要從一堆觀察，找出數字被產生的可能模式。」（3）
- 柯爾莫戈洛夫：「假如產生數字的方法都一樣，怎麼說一個數字比另一個更隨機？」(4)
- 查丁：「透過機器語言跟資訊論，想探討數學的完備性。」(5)
雖然是用不同的角度探討隨機的定義、也問了不太一樣的問題，但他們其實得到了一樣的解答手法：找數字可以被表達的最短程式。
隨機是什麼？綜上所述，不管用什麼手法來看，隨機如果是一種物理性質的話，那其實隨機可以說是「混亂」。可以從混亂找出模式的話，找出模式比較多的數字，跟找出模式比較少的數字 — 我們就可以說，模式比較多的數字，就是比較有秩序的吧？那有辦法去「丈量」所謂的混亂程度嗎？
可以啊，就是熱力學的熵。
熵，熱力學
熱力學在蒸汽機出現後開始興盛。將熱跟能量轉成功，解決了工業革命所需要的動力來源問題。
而身為熱力學開山始祖，克勞修斯製造了熵這個字，並以此訂了兩條熱力學的定律：
第一定律：「宇宙的能量恆定不變。」
第二定律：「宇宙的熵值永遠增加。」
熵：他發現一種量，和能量有關但不是能量，需要給個名字。
第一定律大概不意外，只要你把宇宙看成一個封閉系統。但第二定律是想要講什麼呢？其實，是需要表達「宇宙不斷耗損」的意思。克勞修斯（好像是用數學…）證明了，整個宇宙都在不斷地做功…不斷地消耗能量。
以水來舉例，就像是不斷地…把水倒進去大海裡讓他冷熱混合，之後你就拿不回同一杯水了。（比較熱力學的說法是：熵值增加了，而且你沒辦法逆轉這個過程。）
但為什麼拿不回來？為什麼擺著冷熱混合會發生，但卻不能逆轉(irreversible)？人家牛頓運動定律，時間這變數不管帶正的或負的值都可以 — 也就是可以逆轉啊。為什麼熱力學的現象不行？
這時候想要先講一點點統計力學。
統計力學是什麼呢？wiki上給的解釋是：
統計力學是理論物理的一個分支。統計力學會使用機率理論來探討一個機械系統的「平均行為」…就算這個機械系統的確切狀態是不確定(不穩定或變動)的。
Statistical mechanics is a branch of theoretical physics that uses probability theory to study the average behaviour of a mechanical system whose exact state is uncertain.
其實這描述在某種抽象層次上跟「資訊」這東西很像，關於這點等下討論。
回到冷熱混合。
我們可以看到根據上面統計力學的定義，其實是用數學來探討一個具有一堆小粒子的系統。
牛頓運動定律是在描述粒子的行為。在熱力學的系統裡，裡面每一個粒子，在「微觀態」的運動都是可逆的 — 只是在「巨觀態」的系統層次上，統計上「幾乎不可能發生」。
「計算一個系統所有可能的狀態就會發現，無序的狀態遠遠多於有序的狀態。在很多狀態下分子都是混在一起的，只有極少數的狀態分子會整齊分類。」
所以冷熱混合不能逆轉…就只是因為他機率小到不行而已 — 不是不可能發生 — 但機率小到這種程度你大概跨多少平行宇宙都看不到它發生了。
這其實也解釋了時間。時間的流逝：
「過程只朝一個方向前進的理由都是因為機率，所有不可逆的過程都必須如此解釋。時間本身有賴於機率。」
費曼：「不可逆是由生命中普遍存在的意外引起的，就這麼簡單。」
硬要把這兩句話放進來…覺得這兩句話實在太酷了。
總之，熵就是「無法做功的程度」，而同時他也是：
（熵成為）一種物理上的機率：某一種巨觀態有多少種可能的微觀態，他的熵值就是微觀態數量的對數值。
而，第二定律其實就是：「宇宙的發展傾向是從可能性較小的巨觀態（有序的那種），移往可能性較大的巨觀態（無序的巨觀態）。」
這個「熵」，根本就夏農對資訊的量的定義！
回到統計力學的部分，其實，我們也能看到資訊跟熱力學系統的相似之處。
以「不可逆是由生命中普遍存在的意外引起的」這樣的一句話來討論，難道不是整句話是一個系統，而每個字是一串或許互動或許不互動、冷熱（資訊多寡）不同的粒子嗎？用統計力學的角度去思考資訊，就能夠得到資訊論的理論基礎了。
但其實夏農狀似並不是這樣想的，一開始。
他一開始只是純就他的模型去建構了資訊的數學理論，那時候，他還不知道理論物理的部分可以跟他的模型連結在一起。
熵，資訊論
在夏農實際提出資訊論之前（1984年），有個叫希勞德（Szilard）的物理學家在進行一個思考實驗：永動機。
要做功，就要付出代價。但根據熱力學第二定律，「宇宙的熵值永遠增加」 — 這難道不是一個可以被（隨著宇宙）永恆使用…而且不用付出代價的力嗎？
前面提到，冷熱混合的不可逆其實是來自於統計上的極低機率。而馬克士威為了闡述這個思考方式，用了個有趣也非常有名的教學道具：「馬克士威的惡魔」。
這張圖可以看到，冷熱混合的過程被逆轉了，而逆轉的發生是「馬克士威的惡魔」所操縱的閘門。這「惡魔」每檢查要經過Ａ與Ｂ中間閘門的粒子，都謹慎地選擇讓熱的可以到一邊、冷的到另一邊：馬克士威是想表示在粒子跟系統的行為上，其實分成冷熱兩邊還是有可能發生的。
而希勞德在思考的是 — 假設真的有這個惡魔 — 這惡魔需不需要耗能呢？
前人假裝惡魔的知識（要把哪個分子往哪裡擺才能達成某個巨觀態）是本來就有或唾手可得的，但這惡魔要有這些「知識」（知道哪邊熱哪邊冷、誰算冷誰算熱、哪邊多熱哪邊多冷…etc.）去操控閘門是不是會需要一些「代價」？（思考實驗裡的惡魔不是生物…因為顯然生物需要耗能。）
接著，希勞德在數學推導中發現，「惡魔只要精確掌握每個粒子測量和記憶，轉換就能精確計算。計算得出，每一單位資訊的增加會增加一定量的熵，精確值為
，也就是說，惡魔每做一次選擇其實就欠下一位元的資訊。當週期完成必須清除記憶時，就要償還了。」（書上說希勞德沒有直接講，可是有用數學這樣表達。其實不太確定為什麼寫「週期完成要清除記憶」…我自己的腦補是說大概像cache一樣必須要清掉才能記新的資訊吧。）
這叫希勞德引擎（Szilard engine）。
所以，其實沒有永動機（這個矛盾的存在），因為要做到這種朝向某個機率結果（的巨觀態）前進的話，勢必會需要花上一些「代價」，所以所謂的「永動」的「永」並不存在。
「想減少理想氣體的熵，以換取有用的功，需要付出資訊為代價。」
「特定訊息會減少所有可能訊息整體（用動力系統的術語來說是相空間）的熵。」
「宇宙回覆和諧，重新和第二定律歸於一致。」
而這歸於一致的原因在於證明了：資訊就是熵。
如前所述，夏農其實本來根本就不管資訊論的物理理論基礎…不過他的思考切入方式讓他剛好跟物理學這邊重合了。這思考實驗是1922年提出的，而湊巧補足了夏農1948年的資訊論，「熵就是資訊」的理論基礎。
其實，我們也可以從公式看到熵跟資訊的關係：
- 物理學家：熵是某個物理系統的狀態的不確定程度（當下這個狀態相對於其他所有可能的狀態），是
- 資訊學家：熵是一個訊息的不確定程度 （一個訊息相對於其他所有可能由通訊員發出的訊息），是
他們的算式剛好一樣，不是因為剛好，其實是因為他們問的兩個問題是同一個問題。
故知，熵即資訊。
熵，量子資訊論
在量子資訊論的部分，「資訊」有描述了愛因斯坦跟惠勒的「黑洞」、「弦論」、「霍金輻射」。接著談到班奈特的「邏輯深度」。
剛好看「學數學弄懂這三十九個數字就對了」這本書的時候，裡面也有簡單明瞭描述了「弦論」。
新的兩本講宇宙跟量子物理的書今天也會拿到…打算把這些跟之前看過的幾本整理在一起放另外一篇。ＱＱ
熵，哲學與生命
在「資訊」一書中，熵的討論最後是進到了比較哲學（？）的討論。
在熱力學第二定律裡提到，「宇宙的熵值永遠增加」，也就是說，宇宙逐漸從有序走到無序…但其實，世界上有種東西不是這樣啊：「生命」。
生命，或者生物，看起來是如此的有結構…那這跟熱力學第二定律有什麼關聯呢？
有辦法的話，這部分的討論也跟量子資訊論放在同一篇好了。
隨機的用途 （待補）
幹嘛要要探討隨機？還要用數學或物理來定義隨機？定義東西亂到什麼程度…怎麼會有用？
出乎意料的，還滿有用的。
- 當實驗的input用：據說以前還有人出版亂數表的本子給科學家用呢…
- 當找最佳解的快速手段
- trigger unknowns: 比起上面找global最佳解的手段，比較偏演化、創意、社會發展的部分。
下面討論一下利用隨機找全局最佳解這回事。
- 登山法 hill climbing, gardient descent,
- 加入一些雜訊 https://en.wikipedia.org/wiki/Jitter，stochastic,
- 模擬退火法 simulated-annealing (量子物理),
- 蒙地卡羅法
恩，心得是，小時候不懂事不好好讀書，以前唾手可得的，現在都要看好多wiki跟買書來看。不過，話又說回來，這本書涵蓋的領域這麼廣，回到學校的話，大概會變成很分散的好幾堂課，就沒辦法這麼統整的變成一個以資訊為主軸的脈絡了…然後如果不知道有這個脈絡的話，其實我根本也不會想去讀這些有的沒的東西。
這這裡有關的future work有幾個。下一篇打算寫形式物理、哥德爾不完備定理、可計算性、判定問題、圖靈機之類的，接著寫最近讀的量子物理、測不準定理、量子資訊論的部分 — 不確定要不要把遺傳物質還有哲學性的「生命」的討論寫在同一篇。
然後，可能中間要看看有沒有打算寫語言學跟演化心理學的部分（針對「資訊」一書所提到的小小片段）。
接著要把「資訊」一書的整本書的知識架構抽出來，畫張圖來紀錄。