用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|，就能正確判斷。

減少操作實驗浪費的時間

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

首先，畫圖方面 gnuplot 是最好的選擇，用法很簡單，google一下學個基本，之後要用什麼特殊指令，去 Demos and Screenshots 裡找符合的圖，將範例code抓下來試一試，改一改就會用了。看到常用的指令或參數，就到 Documents 的 Index 裡找詳細說明（比方查 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前，感到的是做研究的孤寂感，當時想趁結束研究後休息一陣子，沉澱思緒再來思考未來方向。轉眼間，將近三個月過去，和很多朋友聊過，靜下心來思考了許久，未來一樣地未知。然而，相較於去年十月底的落寞焦慮，如今卻是莫名的自在，憶起一樣的事，卻振盪出不同的思緒。不急不徐，願我能保留如此心境，迎接往後的日子。

能者多勞？

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

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

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

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的介紹，順便記一下他給年輕科學家的建議：

１．別和你的同事競爭。
２．嘗試你能作的最困難議題。
３．選擇對科學發展有益切題的研究方向，不要與科學界妥協。

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

近日練琴情況

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

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

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

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

social network推薦機制

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

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

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

一個投機者的告白

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

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

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

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