馬可夫鏈與生成藝術

不知道現代人，還有沒有寫日記的習慣？以前的日記裡，我總覺得有個無聊的欄位，那就是用來記錄當日的天氣，或許簡單地寫個晴、陰或雨。如果某人一直保持寫日記的習慣，有天心血來潮，將多年來的天氣記錄做了個統計，然後各自計算出前天是晴、陰、雨之一的情況下，隔天是晴、陰、雨的機率，心裡想著，這樣不就可以根據今天的天氣，預測隔天的天氣狀況嗎？

顯然地，這種方式的假設是，某日的天氣狀態，只受到前一日的天氣狀態影響。天氣預測當然不是這麼簡單（不過可能有某種程度的準確率）；然而，對於某些隨機過程確實有可能，「在給定現在狀態及所有過去狀態情況下，未來狀態的條件機率分布僅依賴於當前狀態」，這種性質稱為馬可夫性質（Markov property）。

認識馬可夫鏈

馬可夫性質的名稱，是從俄國數學家Andrey Markov而來，對於一個隨機過程，X(t)表示t時間的狀態（或稱為發生的事件），X(t)、X(t+1)、X(t+2)……，關於這樣的過程，我們稱為馬可夫過程（Markov process）或是馬可夫鏈（Markov chain）。

為了簡單地表示馬可夫鏈的隨機過程，通常會使用狀態轉移圖，在每個轉移標示轉移機率，看來就像個非確性有限狀態機，例如方才的天氣案例，可用圖來表示具有三個狀態的馬可夫鏈：

圖中可以看到有九個方向的轉移，這樣的轉移，若以當日狀態晴、陰、雨為縱軸，隔日狀態晴、陰、雨為橫軸，將對應的轉移機率逐一填入構成矩陣，就是馬可夫矩陣（Markov matrix）或轉移機率矩陣（transition probability matrix），如果有某天晴、陰、雨的機率分布矩陣（例如[0.2,0.6,0.2]），乘上馬可夫矩陣，就可以得到隔日的機率分布矩陣。

馬可夫鏈L-system？

從網路上搜尋馬可夫鏈相關文件，就會有更多的名詞了，例如方才談到天氣預測當然不是這麼簡單，也就是單純從日記本裡的歷史資訊得到的馬可夫鏈，只是外部觀察到的現象，然而，內部可能會有隱藏的狀態（氣壓、溫度等更多狀態），這就有了隱馬可夫模型（Hidden Markov model）……不過，到底馬可夫鏈可以用來做什麼呢？

就統計相關領域而言，它是一種機率論，若搜尋相關資料，我們多半會看到在經濟、金融、社會科學等方面的探討，常應用於時間序列方面的資料分析，像是基於已知的歷史資料進行觀察、預測，或進一步地模擬取樣等。

只不過對我而言，統計、機率之類的文件或話題，始終難以感到有趣，但不知為何，這次我耐著性子繼續看相關資料，然後漸漸有點似曾相似的感覺：怎麼覺得我寫過類似概念的程式呢？原來，我在先前專欄文章〈碎形與L-system〉最後談到：在看到可展開的符號時，若能根據機率決定是否將符號展開，就會是隨機（Stochastic）L-system。

確實，試著搜尋一下「markov chain generated art」，就能找到許多基於馬可夫鏈來進行生成藝術的資料，像是馬可夫鏈圖片產生器之類，因此，我想到，可否基於L-system的符號，也來個馬可夫鏈L-system呢？

這需要建立符號轉移的馬可夫鏈，也就是需要一連串符號的歷史過程，例如，我們可以觀察許多棵碎形樹的生長模式，以L-system的符號記錄生成過程，然後讓程式讀入這些符號串，統計每個符號後跟隨的符號機率，而有了馬可夫鏈之後，接下來可以使用任一符號作為初始，並且基於馬可夫鏈來產生下個符號，而在多次迭代後基於生成新的符號串，也就能根據此符號串繪製更隨機的碎形樹了。

如果想用程式驗證一下概念，我們可以先寫個L-system產生器，然後生成碎形樹的符號串，後續讓程式讀入這些符號串，進行方才的馬可夫鏈等過程，若你有興趣了解，可以參考我寫的〈Coral〉程式，因為更為隨機，看來不像樹了，更像是珊瑚。

假文產生器

另一個相關例子是Reddit，它是娛樂、社交等各式主題的討論區網站，裡頭有個r/SubredditSimulator子版（subreddit），裡頭的發文使用者全都是機器人，卻也討論地有模有樣，就像個鄉民模擬系統，每篇發文或評論顯示的使用者（機器人）名稱，其實可以看出機器人的訓練來源是哪個子版，而不同子版訓練出來的機器人，發文的風格各有特色。

而在〈What is /r/SubredditSimulator?〉裡，我們可以看到，機器人的訓練是基於馬可夫鏈。其實，我也是在閒逛網站時，在〈Markov chain-based text generator in Python〉看到馬可夫鏈這個名稱，因而產生興趣而做了進一步探索。

基於馬可夫鏈來作為假文產生器的概念，出發點非常簡單，因為，閱讀一篇文章的過程，就是逐字逐句進行，也就是個時間序列的過程。以英文來說，我們可以根據空白或標點符號切割整篇文章，然後讀入每個切割後的子字串，統計每個子字串後跟隨的各種子字串之機率，建構出馬可夫鏈。

有了馬可夫鏈之後，接下來，我們可以使用任一子字串作為初始，基於馬可夫鏈產生下個子字串，將這些子字串連起來，就像一篇有模有樣的假文了；或許更簡單一些，我們可以針對每n個字元來切割字串（n-grams），如此一來，還可以產生各式各樣的文字，不同的n會產生不同的結果。

Daniel Shiffman的〈Programming from A to Z〉系列，是有關文字資料處理的一系列線上教學，其中〈N-Grams and Markov Chains〉就談到馬可夫鏈，裡面也有逐步的p5.js程式碼建構過程，說明如何實現簡單的假文產生器，有興趣的人可以看看。

更多的生成應用

那麼，我們可否基於馬可夫鏈，訓練一個繪圖機器人呢？如果將二維的像素降為一維，然後像假文產生器那樣，以每n個像素為一組，看看後續會出現哪一組像素，這種作法是可以建立馬可夫鏈，〈Can we generate images with Markov Chains?〉就談到了這個作法。

不過，降維會失去資訊，像是失去鄰接的上、下像素的訊息，可能要搭配卷積網路之類的預處理，才更能模仿來源圖片的風格。如果不想那麼複雜的話，我倒是想到了波函數塌縮演算，因為它的演算流程中，建立權重的方式，某些程度上，也是個類似建立馬可夫鏈的過程。

顯然馬可夫鏈是個生成藝術可運用的方向，〈生成式藝術與算法創作〉是一系列講述生成藝術與演算方向的文件，其中〈08-馬可夫模型〉，談到了音樂創作方面的應用，畢竟音樂也可看成是時間序列資料，文中列出了基於馬可夫鏈生成的Illiac Suite弦樂四重奏，可以聽聽看是什麼感覺，或許你會訝異，這竟然沒有太大的違和感呢！