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

顯然地,這種方式的假設是,某日的天氣狀態,只受到前一日的天氣狀態影響。天氣預測當然不是這麼簡單(不過可能有某種程度的準確率);然而,對於某些隨機過程確實有可能,「在給定現在狀態及所有過去狀態情況下,未來狀態的條件機率分布僅依賴於當前狀態」,這種性質稱為馬可夫性質(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弦樂四重奏,可以聽聽看是什麼感覺,或許你會訝異,這竟然沒有太大的違和感呢!

專欄作者

熱門新聞

Advertisement