Lisp 初體驗:Grammar Induction

Sep 19 2010

python

我們這個地球上的人實在太多了,加上上天賦與我們的大腦又過於活躍,以致於時時可以聽聞到,又有什麼人做出了驚人之舉。

幾個禮拜前,無意間得知一個網頁:Random CG Paper Generator。每 reload 這個頁面一次,就會亂數產生一篇圖學論文的標題出來(以假亂真似地)。也許,苦於找不到研究方向的研究生,可以來這個頁面 reload, re-roll your brain,看看有沒有什麼意外的研究靈感可以借用的。

Anyway,借用一個這樣的 random stuff generator 來找點子,實在太冒險也太不明智了,況且,我還處於 non-qualified Ph.D. student,沒啥理由理會這個網站的。除非…

我想知道它是怎麼產生這些以假亂真的論文標題。

在與 Edward 來來回回,反反覆覆的 email 往來後,終於,他了解我的目的了。Ed 建議我用 Lisp 來試著解解看這個問題。一方面 Ed 最近一直在寫 Lisp program,而 Lisp 又是號稱 functional programming languages 裏頭的元老之一,很擅長處理這類 AI 相關,或是 NLP(Natural Language Processing)相關的問題;另一方面,我剛好也在鑽研 FP,想多一些小而美的例子好讓自己的手變得髒一些(黑手),從中了解一下 FP 的特色。於是就開工了。

透過 MacPorts 安裝好 SBCL (Steel Bank Common Lisp)Emacs 後,自 Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp 這本書的網站上,下載了書中提到的一些程式碼。試圖用裏頭的一些函式與方法來解決,或是某種程度上“逼近“我想要處理的這個問題。非常遺憾的,PAIP 的程式碼,似乎是給老舊的 Common Lisp 用的,而 SBCL 與他沒有很合,會一直出現一堆 warnings,得一直按 continue/ignore 之類的@@

ok, 首先,我一點都不懂 AI, NLP. 就算有修過一堂 AI 課,也是以非常低分,只比及格還來得高一點的方式過關。(沒辦法,大二在什麼都不懂的情況下,就跟著同學起鬨去修了許永貞教授的課。我還記得那是堂限定大三以上才可以修的課,但我們一群人居然表現出無比的勇氣與真誠,感動了教授,於是我在懞懂中修完了 AI,至今還是覺得很後悔,應該大四再去修,收獲比較完整的)加上我也沒看過 PAIP 這本書,一開始想以最快最省事的方式,把玩一下先。

  • 下載 PAIP 程式碼,解開至某個資料夾。
  • 執行 Emacs interactive shell(或是採用 Emacs + SLIME),根據原網頁上寫的,先載入 auxfns 這個檔

            (load "auxfns.lisp")
    
  • 有很高的機會,你會看到如下的一些畫面,持續按 0 (continue) 就對了。(原因是新的 Lisp interpreter 已經內建了 symbol 與 debug 這兩個函式了)PAIP in SBCL on Emacs/SLIME

  • 麻煩的事來了。接著是按照網頁上的建議,想執行

            (requires "examples")
    

就會遇上另外一些有看沒有懂的 msg:Error msg by \(requires "examples"\)

  • 這是 auxfns.lisp 裏的 load-paip-file 這個函式的問題。它原來的程式碼如下:

            (defun load-paip-file (file)
    

    “Load the binary file if it exists and is newer, else load the source.” (let* ((src (paip-pathname file :lisp)) (src-date (file-write-date src)) (bin (paip-pathname file :binary)) (bin-date (file-write-date bin))) (load (if (and (probe-file bin) src-date bin-date (>= bin-date src-date)) bin src))))

裏頭的 file-write-date 這個函式會因為找不到 .binary 這檔而發出類似 exception,中斷了程式的執行之類的。(我亂猜測)作法是直接拿掉 .binary 檔的測試。如下:

            (defun load-paip-file (file)
  (load (paip-pathname file :lisp)))
  • 最後,我們重新來一次,順利執行過了 (requires “examples”),接著輸入

            (do-examples :all)
    

過程中反覆按了不下十次的 0 (continue),最後好像可以了?(其實還是不行,不過我已經想放棄了…)假設已經可以了好了 = =

這過程讓人很氣餒,一來還搞不清楚,那個 do-examples :all 是在幹麻的(喔喔,我這邊的寫法不算正確,正式來說,應該寫成 (do-examples :all),你也曉得的,Lisp 最有名的,就是那些括號了,如果拿掉那些括號,程式碼說不定可以減少 14 ~ 13!!!!),連個鬼影都還沒瞧見就得狂按一堆 continue,但最後居然還是宣告失敗;二來,我們一個 Lisp 的語法都還不懂的情況下,更無法去 trace code,況且 trace code 也不是現在的首要目的。當下最重要的,是確定你的 Lisp 環境運作正常,然後有個例子可以執行~

最後,我們修正了一下我們的目的:

參考 PAIP 的 syntax1.lisp,使用裏頭一個號稱 PSG-based natural language parser。然後自行先隨便兜一個 grammar 出來,然後用這個 grammar 來 parse 一個 randomly generated paper title。這過程的目的在於,小小把玩一下 NLP 裏頭的 parsing by grammar.

為此,拿出事先就已經準備好的一個文字檔來,裏頭的每一行是一筆 random paper title,這個檔是事先用 Python 寫了幾行程式,自動“觀看“那個網址 10,000 次,再把每次得到的 paper title 存起來的結果。途中我一度擔心,是不是會把這個網站給搞掛了,連續 10,000 次的 query,中間一點喘息的時間都沒有,應該是 ok 的吧? 很顯然它活得好好的,網站沒有掛點 :D

開始亂試 grammar 幾分鐘後,我突然意識到一件事。參考 syntax1.lisp 的 grammar 的寫法,算是非常正規的一種作法,就是說,把一個句子拆開來看,然後一個句子可能是由名詞子句 + 動詞子句構成的,然後名詞子句又可以是單單一個名詞,或是一個名詞片語,然後動詞又可以是……就這樣一路下去。然後我也意識到,一般的 paper title,其實不過是一個名詞子句,並非完整的句子。為此,我只要專注在刻出一個名詞子句的樣子,然後最後把會用到的(或者說,會出現的)單字給放上去就行了。

要做到前者這點不難,難的是怎麼挑出會用到的單字,CG 界裏頭常常出現在 title 的單字可能就那些,不過要得到一個清單也是得花些時間的,偏偏對於一位 programmer 來說,最貴的就是時間了,尤其在你只是在寫個 prototype,連真的的目的的一點邊都還沾不上的時間,豈可以花費太多時間在你壓根兒都還不清楚的細節上頭?! 於是我把腦筋動到那 10,000 個 paper titles 上頭。裏頭不是有很多個單字嗎? 直接從中抓出“到底有多少單字有用到“,不就得了?![How many words appearing on a CG paper title?](http://farm5.static.flickr.com/4105/5003476445_d454d1c700.jpg)

最後,我約略胡亂弄出了個 grammar 來:

(defparameter *grammar4*
  '((NP -> (D N))
    (NP -> (N))
    (NP -> (D A+ N))
    (NP -> (A+ N))
    (NP -> (NP PP))
    (PP -> (P NP))
    (N -> (N N))
    (A+ -> (A))
    (A+ -> (A A+))
    (A -> abstract) (A -> adaptive) (A -> anisotropic) (A -> arbitrary) (A -> ambient)
    (A -> bidirectional)
    (A -> distributed) (A -> dynamic)
    (A -> exponential)
    (A -> gaussian)
    (A -> hardware-accelerated) (A -> hierarchical) 
    (A -> intelligent) (A -> interactive) (A -> inverse)
    (A -> linear) (A -> logarithmic)
    (A -> multi-resolution)
    (A -> non-linear) (A -> normal) (A -> normal-mapped)
    (A -> occlusion-mapped) (A -> omnidirectional) (A -> output-sensitive)
    (A -> parameterized) (A -> persistent) (A -> piecewise) (A -> polygonal) (A -> practical) (A -> pre-computed) (A -> precise) (A -> probabalistic) (A -> procedural)
    (A -> real-time) (A -> reflective) (A -> relief)
    (A -> shadow-mapped) (A -> soft) (A -> spherical)
    (A -> texture-mapped)
    (A -> variable) (A -> view-dependent) (A -> volumetric)
    (D -> the) (D -> a) (D -> an)
    (N -> approximation) (N -> attenuation)
    (N -> caustics) (N -> clustering) (N -> compression) (N -> culling)
    (N -> displacement)
    (N -> estimation)
    (N -> fields)
    (N -> geometry)
    (N -> interpolation)
    (N -> light)
    (N -> mapping) (N -> map) (N -> mipmap) (N -> modeling)
    (N -> occlusion) (N -> opacity) 
    (N -> preprocessing)
    (N -> re-meshing) (N -> rendering)
    (N -> sampling) (N -> shadow) (N -> spline) (N -> subsurface scattering) (N -> surface)
    (N -> texture) (N -> texturing)
    (P -> with) (P -> for) (P -> at) (P -> on) (P -> by) (P -> of) (P -> in) (P -> using)
   ))

檔案:

最後,我終究是沒有完成 Grammar Induction,只能說是小小玩了一下而已~

comments powered by Disqus