漫步在冬夜

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

不知道為什麼，冬天總讓我有懷念的感覺，時常憶起冬天的事，特別是夜裡的事。想起小時候縮在被窩裡看書、想起大學和室友們衝到樓下全家買宵夜。或許，這些微不足道的日常反映出我嚮往的生活，和我追求的挑戰人生達到平衡，形成最適合我的生活方式。於是我選在晚餐幾小時後徒步到小街上的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 是首當其衝的問題，這要長時間的研究、試驗、修正，才會有好成果。考量到日後的發展，比較「高深」的方法應該會在日後再漸漸導入吧。

一個投機者的告白

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

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

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

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