2008年1月27日 星期日

用automata的path做為memory

最近想整理一下過去修課時散落的心得,就這樣隨時間過去而忘記挺可惜的。

在讀 DFA/NFA 時就有這種感覺,利用 state 的連結方式或某種 path 的展開,可以表示特定記憶狀態,比方若 language 的 size 為有限個,可以把每個 string 以一個 state sequence 表示,於是這些 state sequences 的聯集會成為 state tree,藉此記下整個 language。

這概念運用到 PDA 更有效果,如果想記住 stack 最上層有限個元素,可以在PDA裡加入由2^k個state表示的 tree,記下 stack 裡 top k 元素,像下圖所示:

由 state s 連出的上面那條 path 表示 stack 最上面的元素是 0,下面則表示 1。即使被 pop 掉了,由此延伸,就能同時「多看」幾個 stack 內的元素,比方比較 stack 最上面 3 個和 最下面 3 個是否一樣。由於 PDA 的 state 數是有限個,所以這個做法無法記下無限長的 input string,並且,在建立 state 時就要設計好要記憶多長的內容,比方我們假設最多記 k 個 input,萬一輸入多了一個,這個做法就失效了。所以,在記憶的功能上,這個做法同樣地比不上 Turing Machine,這是先天架構的限制。

以實例來看,FA 和 PDA 都可以判斷部份 ww 類型的字串,只要事先建好長度為 1 ~ k 的 ”state path”,配合 Non-deterministic 的做法 [1],即可判斷。但我們無法處理任意長度的 w,當 |w| > k時,就無法處理了。

由此想法發展, 我想到 Neural network (NN) 用 node、link、link weight 表示memory,類似的概念在 NN 裡已被提過:linking structure 表示 memory,training 就是將資料記到 linking structure 裡,所以 training 的同時也會破壞 memory。

這個想法很有趣,也能類推到人腦運作,不過不管從正反面來看都有用也有問題。可以說新 input 會造成舊的 knowledge (memory) 被破壞,但也不知道是那個 knowledge 被破壞,也可能是重組成新的 knowledge,隱含可以推論出包含舊有功能和新功能的 knowledge。唯一可以確定的是,link structure 的大小決定了記憶容量。在 FA 和 NN 之間,應該還有更深入的關聯性可以思考,或許可以有系統地分析 NN,從而改進 NN 的不足。

ps

做法:

  1. 假設 |w| = i,讀入 i 個 input,並將其「記在」state 裡,舉例來說,s1001表示先前讀到的順序為 1、0、0、1。
  2. 往後讀 i 個 input,若讀入的順序和先前「記住」的順序相同,且讀完 i 個 input 後剛好到字串結尾,Accept。

配合 Non-deterministic 的特性,從起點開始會有 k 條叉路,只要有一條猜對|w|,就能正確判斷。

2008年1月25日 星期五

減少操作實驗浪費的時間

分享一下之前做實驗時發展出的小技巧,我這裡指的是跑程式的實驗。花點時間研究一些工具,可以剩下不少重覆執行的動作。

首先,畫圖方面 gnuplot 是最好的選擇,用法很簡單,google一下學個基本,之後要用什麼特殊指令,去 Demos and Screenshots 裡找符合的圖,將範例code抓下來試一試,改一改就會用了。看到常用的指令或參數,就到 DocumentsIndex 裡找詳細說明(比方查 xrange 的用法),減少試誤的時間。

gnuplot 最大的好處在於批次處理,初期費些工夫寫出滿意格式的 gnuplot code,接著就可以把所有圖表套用一樣的格式,想變更格式時,比方加格線或放大字型,只要改一份 code,所有圖表可以一同更新,這是 Excel 難以做到的,也許 VBScript可以,但學習代價應該會比 gnuplot 高。若會寫 shell script或scripting language如Perl、Python、Ruby、PHP,可以配合script和寫好的gnuplot code,執行一個程式讀入不同的資料檔,即可重畫所有圖表,這點 Excel 更不方便達成。配合 script 還可以自動轉成 LaTeX 用的圖檔格式。若不滿意 gnuplot 預設 EPS 的風格,像我較喜歡預設 PNG 的話,可以配合圖檔轉檔軟體,可以輕易地批次處理,像 Linux、FreeBSD上可以用 convert。做實驗時常要重畫圖表,很少能一次搞定,初期投資些時間在 gnuplot 和批次處理程式上,絕對會回本的。

若想再進一步自動化的話,可以將實驗結果存到資料庫裡,不要存到普通檔案裡。花點時間研究如何用 scripting language 或自己慣用的程式語言操作DBMS(如MySQL),看要在實驗結束時程式直接將結果寫入資料庫,或是先寫入暫存檔再另用別的語言 (例如直接用 MySQL script)將結果寫入資料庫。於是,透過 DBMS 網頁介面的軟體(如phpMyAdmin),可以輕易地觀察實驗結果,像是依時間排序資料、依數據大小排序,或要算平均、標準差等,都輕而易舉;要輸出成 gnuplot 或其它程式的輸入格式,也是非常容易。

最後,跑實驗的程式最好寫成從命令列讀參數,或讀一個設定檔設定參數,減少重新編譯的動作,也方便批次實驗不同參數。

總結一下,我自己的做法是:

  1. 實驗用的程式從命令列讀參數。
  2. 其中一個參數決定要將實驗結果直接輸出(STDOUT) 或寫入 MySQL。有時候做些小更動想看看實驗有什麼差別,不想塞太多資料進資料庫弄亂原有資料,可以下參數讓程式不要寫入資料庫。
  3. 用 shell script 寫好測試用的批次檔,會輸入不同參數給實驗用的程式,產生所有要的結果。
  4. 裝 phpMyAdmin,方便分析實驗情形,以及輸出 gnuplot 要求的輸入格式(用TAB分隔)。
  5. 寫好 gnuplot 的 code,我不知道怎麼在 gnuplot 裡使用變數,讓它能配合shell script對畫圖作細部調整(如更改輸出檔檔名),所以我改用笨一點的做法,將gnuplot code存成字串,用Ruby配合不同變數產生有點不同的 gnuplot code 到文字檔裡,再執行 gnuplot 讀入新產生的 code 以符合細部調整。
  6. 寫個簡單網頁顯示 gnuplot 輸出的 PNG 檔,方便用圖形觀察各組數據的差異。再寫個 script 利用 convert 把所有 PNG 檔轉成 EPS,確保論文裡的圖檔和我想要的樣子一致,但會犠牲向量圖檔任意放大的優點。

上述的方式我試過幾次,幫我省下不少時間,第一次試用時間投資就有回本,更不用說第二次之後的收益了。舉例來說,我其中一個實驗要求是記錄演算法各段落執行的時間,想配合各種不同資料量,判斷演算法的子項目平均時間差多少。但用 profiler 會拖慢執行速度,我只想記錄幾個主要步驟而已。這時輸入到 MySQL 變得相當順手,執行一次批次檔,上床睡覺,隔天早上下個 SQL 做平均,就可以看出差異。找出關鍵的部份後,再下 SQL 選出關鍵資料的細項,看看資料分佈的情況,有助於了解情況。想想看,若不用自動化實驗和資料庫來呈現數據,前述動作有多麼冗長無味,你會想重覆幾次這樣的事?更不用說集中精神分析結果和思考改進方式了。

漫步在冬夜

我很喜歡冬天的氣息,朝晨刺骨的寒氣、午後陽光的溫暖、深夜輕風的寧靜,各有不同韻味。我也喜歡在一般的小街小巷裡散步,隨意而行,一邊欣賞普通街道的日凡景色,一邊沉浸在自己的思考世界裡。

不知道為什麼,冬天總讓我有懷念的感覺,時常憶起冬天的事,特別是夜裡的事。想起小時候縮在被窩裡看書、想起大學和室友們衝到樓下全家買宵夜。或許,這些微不足道的日常反映出我嚮往的生活,和我追求的挑戰人生達到平衡,形成最適合我的生活方式。於是我選在晚餐幾小時後徒步到小街上的7-11,為的不是宵夜,而是走路的這段時間。

透過今天這樣寒冷的夜,我聯想起兩年多前,踏上中國大陸土地的第一次。出發前一天的下午衝去台北報名碩士推甄,傍晚趕回新竹參加期中考,隔天一早出發前往北京。對照這樣緊湊的生活,在北京無憂無慮地漫步,如夢幻一般。我想起一個人在北大校園內散步的事,想起大家一起在北大校園內散步的事。一個人散步的孤寂感是種享受,配合寒冷的北方氣息、人生地不熟卻熱鬧非凡的場景,感觸倍增。相對來說,一群人散步時帶來的安穩感,亦是筆墨無法描述,讓人想永遠停留在那短暫的時光內。即使是平淡的旅程,一個人、一群人在北大的夜裡走著,反而成為最深的回憶,很想再一次在那樣的夜裡隨意散步。

對照回憶起北京行的日記,上次投稿WWW 2008前,感到的是做研究的孤寂感,當時想趁結束研究後休息一陣子,沉澱思緒再來思考未來方向。轉眼間,將近三個月過去,和很多朋友聊過,靜下心來思考了許久,未來一樣地未知。然而,相較於去年十月底的落寞焦慮,如今卻是莫名的自在,憶起一樣的事,卻振盪出不同的思緒。不急不徐,願我能保留如此心境,迎接往後的日子。

2008年1月22日 星期二

能者多勞?

以前曾寫過類似的心得,當時看了「別給優秀人才過多的工作」這句話,深有同感,過去一年剛好有不少管理的經驗,配合自己和別人的情況來看,卻發現這個觀念難以實現。

可能任何地方都有一樣的問題,緊急重要的事不得不交給信任的人,而且這類事永遠不會少,於是有能力的人手邊工作只會愈做愈多,主管在必須達成上級要求的前提下,很難做到工作量平衡,大家都忙著為眼前的情況解套,自顧不暇,那來的時間培育人才?

唯一的解套方式就是讓組內有一群優秀人才,自然不會發生能者多勞的慘狀。於是,人才多的組織愈來愈強;人才少的組織,人才沒時間充實自己,失去前瞻競爭力,漸漸被操到不是人才。像是「多做多學」、「態度決定高度」之類的話,在這種場合只是不得已的精神慰藉罷了。

2008年1月20日 星期日

comparison decision tree和延伸想法

Algo裡提到由 sort 的 comparison decision tree 可得知,任一 decision tree 都存在worst case,其下界為Omega(N*lgN)。

證明的想法很簡單,一個sorting algorithm對 n 個elements來說,會形成一個decision tree,inner nodes是比較的過程,一個由 root 往 leaf 的過程,就是一個排序演算法經歷的步驟。於是,任一 decision tree 對 n 個不同的數來說,至少會有 n! 個 leaves (因為有 n! 種排法)。依tree的性質,有 n! 個 leaves的話,高度至少為 lg(n!),而對於任意的input來說,這個 decision tree 的高度即為比較次數的 worst case。所以 worst case比較次數的下界是:

Omega(lg(n!)) = Omega(n*lg(n))

記得我第一次看到這證明時,對 decision tree 的想法相當感動,沒想到重讀 Algo 再看到這想法時,還是一樣感動,而且發現我並沒有懂得很透徹。做過習題 8-1 後,我才覺得自己似乎又多了解一些 decision tree 的想法。

若反向思考的話,decision tree 自然也存在最矮的 leaves,也就是當每次比較剛好都能利用到上回的結果時,只要比 n-1 次即可,例如:

第一次拿到最小和次小的數、第二次拿次小和第三小的數比、...

那麼,有沒有可能對於任意輸入,找到最佳的比較方式呢?也就是說,這顆 decision tree 並不是固定的形式,而會依輸入的過程改變比法。比方在讀入數字後,以O(n)的時間猜測數字可能的分佈方式,來調整 decision tree 的樣子(即 sorting algorithm 的流程)。在這個想法之下,是否有較高的機率走入較短的 sorting path,而加快排序速度呢?

若能想出借用 Evolutionary Computation 或其它做法在 comparison based 下找出新解法,應該很有趣,先暫記一下這極可能失敗的想法。

或是放鬆使用的限制,在得知資料分佈下,預測比較的方式,比方預測要拿那兩個數來比,就有較高的機率找到較好的比較方式,比方一開始就找到最小和次小的數,那麼,接下來就假定不用拿最小的數來比,於是問題就變成排 n-1 個數,用數學來描述的話,就是做到:

T(n) = T(n-1) + c

上面這式子成立的話,time complexity只有 O(n) 而已。當然,加號後面要猜中才會是常數,也許有可能配合機率分析,了解比成功的機會,我想這是不錯的練習 Randomized Algorihm 的機會,有空來想看看。

ps.

  1. 雖然非 comparison based 在給定數值範圍的情況下可打破 worst case的下界,但卻多了 value range 的假設,純comparison based的使用範圍更廣,畢竟只要滿足能比較兩數大小的條件而已。
  2. 剛讀大學時,我對 halting problem 或這類證極限的定理有些反感,因為它們證明了「對所有情況來說,不可能有萬能解」,那麼,若對「所有情況減一」呢?很多時候我們不需要考慮所有情況。而以前思考較不清析,讀到這類問題時會被搞混,而弄錯焦點。現在看來,自己似乎有那麼一點成長,可喜可賀。
  3. 習題 8.1 告訴我們,透過 comparison decision tree 的分析,符合O(n)的輸入非常少,甚至不到 n!/(2^n) 種。

重讀Dijkstra’s Algorithm有感

首先是確認了Dijkstra的發音,依Wikipedia的定義,要唸[ˈdɛɪkstra]。

以前我一直有兩個疑問:

  1. O(E*logV)不是比O(V^2)大嗎?為啥變成O(E*logV)後較好?
  2. 當heap內的元素會被更動值時,做起來不是很麻煩嗎?time complexity的影響為何沒有被認真討論?連帶使我懷疑那堆怪異的數字,O(V*logV + E*logV) 之類的。

愚笨的我在重讀Algo時終於想通上面兩件事了,

  1. sparse graph的定義:|E| = o(|V|^2),注意,是small-o,也就是說當 n 趨近於無限大時,|E|/(|V|^2) = 0,於是,E*logV還是比V^2小。若對此感到疑惑的話,不妨想想當|E| = |V|^k,其中 k 可以是比 2 小的任意正實數,也就是說,|V|^(1.9)的情況下,E*logV仍比V^2小。

    小時候自以為有讀懂small-o,第三遍讀到這個符號時,才真的體會到它的含義。如同我以前把worst case和Big-O弄混一樣,Big-O只是方便表示上界的符號,不等同於worst case。所以,average case的Big-O、best case的Big-O都很合理,沒有認合奇怪的地方。

  2. 我被heap的insert/delete動作限制住想法,自以為只有insert/delete時才適合做heapify,但當我們更新heap內任一元素時,可以從這被更新的元素開始做heapify,所以heap內的元素可以任意被更新,僅需 O(logV) 的代價。事先用個 array/hash table 就可以記好 heap 內的元素,當要更新特定元素時 (e.g. 某個vertex),O(1)的時間即能完成值的更新。

    沒想到到今天我才真的弄懂Dijkstra, MST的運作細節,以前碰到 priority queue 的更新維護細節時,都下意識地含糊帶過。也許下次再重讀Algo時,又會發現我還沒真的弄懂吧?

另外最近讀《勇闖資訊新未來:打造資訊科技的幕後英雄》時有讀到Dijkestra的介紹,順便記一下他給年輕科學家的建議:

1.別和你的同事競爭。
2.嘗試你能作的最困難議題。
3.選擇對科學發展有益切題的研究方向,不要與科學界妥協。

現階段來說,第三點可能是我最需要的,要能保有自己的價值觀而不與大環境妥協,相當困難。然而,我想一個可貴且稀少的學者,應該具有這樣的氣魄。若我的觀念錯了,也只不過是少一個一般學者,對大環境來說沒什麼損失。不管前述看法是否正確,目前我還太嫩了,仍需要經驗來確認或修正自己的想法。

2008年1月15日 星期二

近日練琴情況

今天彈得很過癮,一首接一首,照慣例先彈《夏影》,上回彈的感覺還在,狀況不錯,因此又多彈一遍。接著彈了《Memory of Mother》(from Snow Sugar),《Tifa’s Theme》,《FFX Opening》。

彈完可以背譜的這四首後,仍不滿足,拿出西村的譜,彈《i.no.ri》,雖然有點小不順,感覺還OK。再拿《約束》出來練,愈來愈順了,彈《鳥之詩》前兩頁,嗯…不太順。

後來胡亂彈了一陣,又回頭彈夏影,彈到中間一個合弦時 (降A Maj7),忽然有點靈感,作出了8小節創作曲,靈感就斷了,無法編下去,唉呀呀。回家的路上一直哼著主弦律,看看能否有所突破,最後又哼回夏影,發現我的創作和夏影比起來遜太多了,沒完成的遺憾小了不少。

再度重聽夏影的演奏,Re-feel的演奏者真的彈太棒了,雖然我終於彈出了自己的《夏影》,仍和原奏者等級差了一大截。我有彈出曲子中的動感,卻彈不出動感中的寧靜。

2008年1月6日 星期日

social network推薦機制

最近在做 social network 的研究,進度相當緩慢,心力被分散到一堆雜事上,這就是沒壓力的下場啊。

這篇文章與該blog裡和facebook相關的文章都很有意思,了解現今最紅的 social network site 如何獲利。看了幾篇介紹後,發現都是相當簡單的推銷機制,我原本也和Mr. Saturday想的一樣,以為facebook會分析使用者的資料,再做出推薦,這也是我現在著手的研究。也許這些學術方法太耗計算資源 ,又無法明確地證明其有效程度,所以 facebook 採最簡單的做法吧?相較於Google極力避開人的因素浮上台面,facebook大辣辣地挑明人的存在,雖然直觀上能讓使用者相信推薦系統,卻更難過隱私權一關。

去除隱私權的問題從研究的角度來看,只使用既有的 social network 發揮的效力有限,只能找到使用者週遭的人,無法找到「沒有直接關聯,但特徵相當相似」的人,大幅減弱龐大資源背後的金礦。但要找出隱藏的金礦,方法不只要算得準,更要算得快,scalability 是首當其衝的問題,這要長時間的研究、試驗、修正,才會有好成果。考量到日後的發展,比較「高深」的方法應該會在日後再漸漸導入吧。

2008年1月1日 星期二

一個投機者的告白

書籍基本資料: 一個投機者的告白

有時覺得每看過一本書就寫篇心得,似乎有點浪費時間。轉念一想,若那是本值得一看的好書,就算寫個一小段,留個影子供自己日後回頭探索,總比什麼都沒留下得好。趁還有點記憶時,來寫數個月前讀的好書。

看這本書,就相當於是聽一位投資界的大師從他年輕時的事蹟一路臭屁到底,讀起來很順沒有負擔。像我這樣不懂投資理財的人,從中學到一些觀念,像是賺錢的方法很多,甚至用公債也有可能賺大錢。作者提到他從時事新聞判斷沙皇時代的俄國公債勢必會被蘇聯償還,從而購入大量價格如廢紙的公債券,等了幾年,蘇聯為了發展國家,和外國交涉借款時,承諾償還這筆費用,結果債券金額大漲,成為作者得意的大交易之一。

投資獲利的祕訣除了不斷的思考和觀察外,耐心相當重要。如同作者幽默的說法,買股票的獲利方式,就是選個好股票,買幾瓶安眠藥睡個十多年。所以投資的錢不能有壓力,不要讓自己處於借錢投資的局面,那會使得自己沉不住氣。作者也提到你得先賠點錢獲得經驗才能學會投資(作者稱這為「投機」),這種事是別人教不會的,要自己做過才懂。還有要敢逆向操作、相信自己,才有可能在投資市場大豐收,一些準則有些人生哲學的味道。