學習的自我要求

學生時代我一直在想一個問題，究竟是問題導向的學習方式較佳，還是技術導向較佳？舉例來說，我想寫個留言版，我發現要完成最基本的需求，我得學 HTML、PHP 和 MySQL，於是我針對我要做的功能學相關的語法，最後完成留言版。可能資料庫設計沒用到正規化，網站外觀沒用到 CSS，一些動態功能用 PHP 實現而非 JavaScript。相較於從頭學寫網站所需的各項技術，這個作法比較務實，我用較少的時間完成目標。極端地看，用問題導向的解法時，我可能找到相關的程式碼，用它們拼貼出結果，但不確定各塊在做什麼。技術導向的解法，可能要先花一段時間弄清楚寫網站需要的技術，再各別學個基本能力，接著開始實作。當然，世界上不是只有 0 和 1，我們常混著用問題導向和技術導向的方式解問題。這裡我說用問題導向的意思，是指偏向用問題導向。

不只做產品，做研究時也是類似的情況。問題導向就是從問題開始往下挖，看前人做那些方法，將自己不熟的部份補起來，有了必要的知識後，就能回頭解決問題。而技術導向的做法，我可能會加強基礎學科知識，視類別而定可能是機率和線代，或是計算機組織和編譯器，接著才開始思考如何解問題（或重新定義問題）。

以前我沒什麼時間觀念，通常是技術導向的作法，覺得有趣就看我能從多底層開始往上學。比方說使用 Java Collections Framework 時，我會弄清楚我要用的資料結構怎麼運作的的，時間複雜度是多少。實際上大部份的使用情境不需要這些知識，稍微讀一下文件的注意事項即可。要用 machine learning 的工具，就找適合的 machine learning 課程講義來讀，弄清楚要用到的 model 怎麼運作。直到現在，我無法確認這些對於使用工具究竟幫了多少忙，當初花的時間對應到目前的幫助，真的划算嗎？

最近我試著用問題導向的方式解問題，初期進展確實比較快，不過後來遇到一些狀況，才發覺技術導向的好處。有些情況，我們根本不明白問題出在那裡，有太多可能。舉例來說，前幾天我和同事發覺不同使用者登入同一頁面，操作速度卻差了一大截。有許多可能原因：網路連線 、網頁框架、資料庫等。做了一些初步測試，我懷疑是 MySQL 根據歷史記錄做錯 query optimization。於是用 EXPLAIN  看相同的 SQL 配合不同使用者 ID，結果發現 MySQL 執行 query 的方式有細微差異，造成取出某些使用者的資料時，用較慢方式執行 SQL。於是讓 MySQL 重分析表內的資料後，問題就解決了。若不是之前稍微看過 MySQL 執行 query 的相關知識，不會這麼快就直指問題核心。也許就會用別的方式繞開這問題，一輩子都不知道怎麼解它。待發生類似問題時，又用別的方式繞開它，長遠來看浪費開發時間又增加維護成本。

另一個反面的例子是，我一直沒用 lock 的習慣，教科書告訴我們 deadlock 很可怕，所以我會想辦法避開用 lock。結果最近有個小專案因為沒用 lock，真的發生 race condition 造成有一點點資料不正確。實作前我明白會有這樣的狀況，但這個問題對我們的目的沒什麼影響，衡量開發時間後我決定寫下註解強調會有 race condition，而選擇不處理它。對照最近的體悟，我明白這樣下去我不可能學會用 lock，這不是個好現象，所以又找時間回頭看 MySQL 怎麼 lock table，結果比想像中來得簡單，之前多慮了。

有很多類似這種的逃避例子，像多人一起寫程式容易有問題，於是大家傾向將功能切乾淨，每人寫沒有交集的功能，最後再來整合。但是，對照近年來的軟體開發的趨勢，愈早整合愈容易解決問題。一個人開發容易有盲點，互相協助可以降低初期錯誤，以利後期整合。問題是，要能順利地多人共同開發，得做對不少事才行。像是版本管理系統、coding style、天天合併程式等。每一項都需要時間練習。若一個人開發時有好好練習，和別人合作時會減少許多問題，比較容易推動密集的團隊合作。

在面試別人時，我發覺一個問題：有些人學到的技能剛好只能應付他負責的專案。問題在於，若平時我們都處理簡單的專案，要怎麼轉去負責困難的專案？兩者之間有個斷層。像這類的例子不勝杖舉。比方說要從資料庫表 A 取出部份資料塞入表 B，最「簡單」的作法是寫個程式用 SQL 取出資料，用程式做些處理再用 SQL 一筆筆寫入表 B。另一個作法是直接用一個較複雜的 SQL 直接搞定。當資料量大時，後者執行速度會快上不少。並且，學會後者的寫法後，之後只要花一點時間就能處理類似的情況，不用再寫一個小程式。其它像寫程式的習慣、用程式工具的習慣，都是一樣的。多數情況我們可以用最「不費力」的作法滿足需求，但長遠來看卻是毫無長進。實際上有更有效率的作法，這裡的效率包含開發時間和軟體品質。

對照大學的程式來看，這一年來我以為自己程式已寫得頗有品質了，雖然知道一些小問題，但覺得並不迫切，也不知怎麼查相關的解法，就放著它們。最近翻了一下 Effective Java 第二版和 Growing Object-Oriented Software Guided by Tests，才發覺還有太多的東西要學，自己和資深的軟體工程師差了一大截，照我目前的學習方式，和他們的差距只會拉大不會縮短。若只專注完成眼前的工作，我永遠無法補足和更難工作之間的差距，這才驚覺問題導向的盲點。

走過天平的兩端後，我現在的體悟是，得雙向夾擊來解決問題。一方面用問題導向解問題以符合時程，確保時間有花在刀口上。另一方面再抽時間用技術導向的方式強化自己的實力。如此一來，在完成當下的專案的同時，也有一點一滴地補足技術斷層，取得挑戰更難專案的機會。題外話，英文也是很重要的「技術」，這一年來我半強迫地讓自己盡量搜英文文件，思考關鍵字比以前敏銳不少，閱讀速度也變快，獲得答案的速度比以前快、品質也較佳。

我學 Machine Learning 的方法

有人問我這個問題，想說就寫在這吧。目前還學不到家，只有斷斷續續讀個一陣子，有錯還請大家指正。

讀 Data mining 的書

一開始我讀 data mining 之類的課本、講義，發現內容講得滿概念的。但若只是想拿 ML 來用，那看這類文件會比較容易上手。比方 Introduction to Data Mining 寫得挺不錯的，可謂深入淺出！官網附的投影片挺棒的，可以先「快速」 (相對於看書來說……) 看一遍，再挑有興趣的部份閱讀課本。若有耐性慢慢讀完課本，會較有系統性地認識相關內容。由於碩論做 clustering 的緣故，我有好好地讀書本 clustering 部份。不過 clustering 論文種類多到爆炸，看完這本的內容也只是苦痛的開始而已……。

讀國外大學的授課講義

若想進一步了解 model 的原理，那就需要讀 ML 課程用的課本和講義。這類文件滿多的，其中我強力推薦 Andrew Ng 教的 Stanford CS229 Machine Learning。大部份教材在講解 model 最關鍵的數學時，只會從天空掉下來一句「套用 gradient ascending 求最大值」、「運用 EM 求最佳值」之類的話，接著結果就神奇地飛出來。這份講義卻從最基礎的數學開始講，包含需要用到的微分、線性代數、機率等，讓讀者有能力自己從頭推導數學算式，算是 ML 文件裡最親切的教材。當然，讀者也要有興趣慢慢地啃才行。我大概啃了一半多一點內容，收獲良多。可惜久一沒用也只記得概念了。有機會想再從頭自己推導一次。我覺得 Andrew Ng 數學寫得相當漂亮，這是我第一次察覺寫數學式和寫程式一樣，也有美醜、易懂難懂之分。附帶一提，當初會看這份教材是看 Mr. Saturday 推薦才讀的，感謝 Mr. Saturday 推薦。

後來我陸續看了一些不同國外大學的 ML 課程講義，發覺大家的切入點差很多，各有不同考量。像 MIT OCR 6.867 Machine Learning 有教 HMM，Stanford CS229 沒教。A Fundamentalist Organization of Machine Learning 提到由 Learning theory 的方式切入 ML，而不要走馬看花講一堆 model (作者稱為 “zoo approach”，挺傳神的譬喻)。我只有從 Andrew Ng 的講義裡讀了一點 learning theory，懂些基本觀念 (bias 和 variance)，感覺挺有用的。若對 learning to theory 有興趣，印象中該文作者有推薦 15-859(B) Machine Learning Theory，Spring 2009。我看了一晚講義，內容是從簡單的假設環境中推導出明確的性質，還挺有趣的。但看到後來就看不懂了，也不明白能做什麼，就沒繼續看了。

讀 Wikipedia

此外，我發覺 Wikipedia 是學東西的好地方。有代表性的方法早已有系統地記錄下來，又提供詳細的參考資料可以一路讀下去。比方說想學 Linear classifier ，比起查書，查 Wikipedia 更有效率。我常拿 Wikipedia 內容和其它文件交叉對照，弄明白看不懂的部份。讀這些東西需要的是耐心以及不傷眼的 Wikipedia CSS 樣版。

讀經典課本

後來又看到 Mr. Saturday 提到 Elements of Statistical Learning: data mining，inference，and prediction. 2nd Edition.，而且官網還有附完整電子書，就載來看看。不得不說這本書數學超硬，但內容超級紮實，相當值得一讀。我挑有興趣且讀得下去的部份加減看，學到 bagging、random forest 等東西，讓我擴展眼界，明白許多原理。除數學太硬之外，這本書另一問題是實驗資料太小了，令人懷疑實驗結果是否適用於真實世界的情況。只好先暫時相信大師，之後再從實驗中確認。

有興趣的話可以在 Amazon 查一下其它書，或以這本書為底看相關書籍。ML 有不少經典書籍，也有針對影像處理或文字處理的。

其它

O’Reilly 出的 Programming Collective Intelligence - O’Reilly Media 也是不錯的書，適合初學者閱讀。配合使用情境，作者簡單地解釋 model 的概念並用 Python 說明如何實作。最令人讚賞的是，作者還有比較各個模型的優缺點。雖然分析的內容不見得正確，對初學者來說挺受用的。

總結

讀這些理論時，我發覺有許多文件提供不同的講解方式，可以多比較一番，找自己看得懂的。不用刻意從某個地方學會某種 model。文中提的是我學習的歷程，每個人的需求不同，數學底也不同，我的經驗不見得適用於其他人。寫在這裡供大家做個參考，有錯還請告知，感謝。

Naive Bayes Classifier 的原理（單刀直入版）

這篇內容和上篇《Naive Bayes Classifier 的原理》一樣，只是改採簡明厄要的寫法。話說我以前都寫這種風格的說。

問題描述

給定由屬性 A1, A2, A3 和類別 C1, C2 組成的 training data（例如 (A1, A2, C1) 或 (A1, A3, C2)）。求 A1, A2, A3 三者任意組合的情況下，應該分類到 C1 還是 C2。

Naive Bayes Classifier 定義

以 (A1, A2) 為例說明：

P(C1 | A1, A2) = P(A1, A2 | C1) * P(C1) / P(A1, A2)

比較 P(C1 | A1, A2) 和 P(C2 | A1, A2) ，若前者較高，就將 (A1, A2) 分類到 C1，反之分到 C2。

注意 P(C1 | A1, A2) 和 P(C2 | A1, A2) 分母一樣，可以忽略不算。

Naive Bayes Classifier 原理說明

相較於直接數 training data 裡各種組合和對應到類別的數量，Naive Bayes Classifier 的優勢是在 training data 不足時，仍能處理各種屬性組合。也就是說，即使 training data 內沒有出現過 (A1, A2, C1) 和 (A1, A2, C2)，Naive Bayes Classifier 仍可估計出 P(C1 | A1, A2) 和 P(C2 | A1, A2) 何者機率較高。

原因是 Naive Bayes Classifier 假設所有屬性對其類別具有 conditional independence ，所以 P(C1 | A1, A2) 可拆成如下的算法：

P(A1, A2 | C1) = P(A1 | C1) * P(A2 | C1)

同理可算出 P(A1, A2 | C2) ，所以能比較 P(C1 | A1, A2) 和 P(C2 | A1, A2) 的值。注意真實情況下 conditional independence 不見得會成立。

Naive Bayes Classifier 的原理

以前讀 Bayesian probability 時一直有個疑問，為什麼要這樣繞彎來計算？這疑問在讀 Naive Bayes Classifier 時更大了。

假設輸入為屬性 A1、A2、A3 和類別 C1, C2，為什麼不從 training data 裡直接計算出 P(C1 | A1, A2, A3) ？如下所示：

P(C1 | A1, A2, A3) = P(A1, A2, A3, C1) / P(A1, A2, A3) — (1)
P(A1, A2, A3, C1) = N(A1, A2, A3, C1) / N(U)
P(A1, A2, A3) = N(A1, A2, A3) / N(U)

其中 N(.) 表示計算出現次數，U 是宇集。或是更直接一點，直接算數量：

P(C1 | A1, A2, A3) = N(A1, A2, A3, C1) / N(A1, A2, A3) — (2)

可是 Naive Bayes Classifier 卻採用下面這種繞彎的方式子計算：

P(C1 | A1, A2, A3) = P(A1, A2, A3 | C1) * P(C1) / P(A1, A2, A3) — (3)

顯然 (2) 看來直接易懂，為什麼 Naive Bayes Classifier 要用 (3) 的算法呢？畢竟等式右邊各項，也是用 N(.) / N(U) 組出來的。

今天想了許久，終於想通了！關鍵在於 training data 不見得能完整涵蓋所有可能。比方從來沒出現過 (A1, A2, C1) 或 (A1, A2, C2) ，在這種情況下，無法從 training data 裡直接用計數的方式求出 P(C1 | A1, A2) 和 P(C2 | A1, A2) 。於是疑問轉成：「為何 Naive Bayes Classifier 可以計算沒出現過的組合？」

先從定義來看：

P(C1 | A1, A2) = P(A1, A2 | C1) * P(C1) / P(A1, A2)

由於 P(C1 | A1, A2) 和 P(C2 | A1, A2) 的分母一樣，分母可以忽略不算（事實上也算不出來），所以問題簡化為計算上式分子的值。P(C1) 或 P(C2) 可從 training data 裡算估出，但在沒有 P(A1, A2) 的情況下，難道 P(A1, A2 | C1) 可以估的出來？

答案是：「在 conditional independence 的假設下可以！」

假設 A1, A2 在 C1 發生的情況下為 conditional independence，則可得到如下的結果：

P(A1, A2 | C1) = P(A1 | C1) * P(A2 | C1)

原本要求 A1, A2 在 C1 條件下同時出現的機率，成功地轉換為計算各別在 C1 條件下的機率！於是在 A1, …, Ak 對 Ci 都具有 conditional independence 的假設下，只要 training data 內可估出全部的 P(Aj | Ci)，就能計算各種 Aj 組合的條件機率！

結論

相較於直接在 training data 內算次數猜類別，Naive Bayes Classifier 的特色是用極少的機率函數 [*1] 表示出所有屬性組合的機率。但是前提是 conditional independence 的假設要成立。若 Ai 和 Aj 有關聯性 ( Ai and Aj are correlate ），會算出錯誤的數據，這時可能得用 Bayesian network。

更新 (2009-02-21)

經祖佑 [*2] 說明，在這補充幾點：

• 我誤用 missing value 一詞，文中已改正為「training data 不完備」。
• 修改結論，將 Naive Bayes Classifier 的特色寫得更明確。

備註

1. 若有 k 個屬性和 c 個類別，只要從 training data 裡估出 k * c 個機率函數，就能估計出所有組合（(2^k - 1) * c）的機率。
2. 祖佑回覆的原文如下（從 BBS 複製過來的，排版有點亂）：
   

   一點個人感想

   NBC假設conditional independence的優勢是
   把很大的機率表拆成許多小的機率表相乘，所以減少了機率參數
   因此減少了training data的需求量，或反過來說讓同一筆training data資料意義變大
   而文中所提的”missing value”只是這個優勢下的一個特例而已
   事實上就算完全沒有”missing value”的情況，NBC還是可能有他的優勢存在

   因為自己說要舉例，所以只好舉例
   假設要判斷一部動畫camel喜不喜歡
   觀察的attribute是有沒有蘿莉跟有沒有身材好的女角
   同樣一筆training data [(有蘿莉，沒身材好的女角) => camel喜歡]
   在沒有假設conditional independence的情況下
   就只代表(有，無)這樣的組合camel可能會喜歡
   但是在假設conditional independence的情況下
   代表的是”有蘿莉=>camel可能會喜歡”以及”沒身材好的女角=>camel可能會喜歡”
   所以說同一筆資料的information變大

   但是很明顯的這樣假設的危險就在於也許camel只是不喜歡蘿莉身材好XD
   所以(無蘿莉，無身材好的女角)可能在NBC會被誤判成camel喜歡
   這就是有denpendency的情況下，錯誤假設造成的謬誤
   順帶一提的是我覺得missing value這個詞很怪XD
   因為有另一類問題是在處理某input attribute不存在的情況
   例如training data出現(有蘿莉，”不知道”) => camel喜歡這樣的情況

   前文所說的missing value與其說是missing value
   不如說是training data不足

Reverse linked-list

剛才看了《The Guerrilla Guide to Interviewing (version 3.0)》，立即想重寫 Joel 提到的兩題面試關鍵題：“reversing a linked list” 和 “detect loops in a tree structure.”。後者很簡單，前者要更動指標內容，記得初學 C 時讓我奮鬥了很久，想來看看自己現況如何。

完成的程式如下（全文見這裡，記得用 gcc -std=c99 編譯）：

Node* reverse(Node *node) { if (!node || !node->next) return node; Node* head = reverse(node->next); node->next->next = node; node->next = 0; return head; }

若是以前的話，大概不能這麼自然地寫出簡潔的 code，看來學過 scheme 果然有差，變得較能從高階觀點堆砌程式，也就是將 function 看成基本單位，如此一來，遞迴是自然而然的事。得找個時間練練 functional language，這計畫不能放棄。

碩士研究生涯回顧 (4)

最近週末都在打 YsO，不小心就拖稿了。

上回提到碩一上的結束，我終於確定研究方向為 social bookmark。碩一下修指導老師開的 Data Mining 和必修課 Formal Language。由於我兩門課都有些背景知識，沒花太多時間在課業上。學期初滿認真地做研究，也在 delicious 的 tag 裡找到一些有趣的訊息，像是人們提到 usb 時，容易聯想到 portable [*1]，我猜這是因為隨身碟是最熱門的 USB 產品而帶來的印象。後來斷斷續續想了些相關點子，可惜沒足夠的時間做進一步的研究。

結果後來被會長拐去參加比賽，加上專題生的比賽，同一時間報了五六個比賽吧。原本想亂槍打鳥，看那些發展較好就做下去，結果都有過初賽，搞得寫完初賽報告就不想比了（一口氣寫太多報告把參加整個比賽的力氣用完了）。最後大多爛掉了，幸好還有一兩個有好成績，像是去西安參加微軟思源競賽，是滿有趣的經驗。這算是我參加過的比賽裡，自認為做得最有成就感的，開發速度快，demo 效果不壞，報告也滿成功的。我們做的產品 BNW （Brand New World）用來比較公司品牌或產品。輸入公司或產品名稱後，BNW 會彙集網路上的直述句，再計算出分數。

上圖是其中一個 demo 例子，比較四家公司的品牌。資料只是 web 上的一小部份取樣，不見得能反映實際情況，但不管怎麼說，我們是去向主辦單位 Microsoft 報告，這個結果還挺尷尬的，最後決定在簡報時快速帶過這張，免得被人誤認為是去拆台的。另外，當時看了相關研究「Opinion Mining」，主要是看 Bing Liu 的論文和書，滿有意思的。比賽結束後老師問我是否有意延伸這方面的研究，不過我覺得資料難以取得（比賽時有 MSRA 支援），而且我比較想做 social bookmark 的研究，就結束掉這個小插曲，而碩一下也這麼結束了。之後是碩士兩年裡最發光發熱的暑假衝刺時期，後來完成的兩篇論文，都是在這暑假內完成一半以上的內容。

ps

*1 我用 association rule，發現”usb” -> “portable” with confidence 80%，”portable” -> “usb” with 60%。

理論與現實

這篇只是描述剛遇到的小例子，不是要探討什麼大道理。

這段話說得太有道理了，先引用一下：

In theory, there is no difference between theory and practice. But, in practice, there is.

By Jan L. A. van de Snepscheut　

剛才很快樂地實作別人的方法來補我的碩論實驗，結果遇到一個作者沒考慮到的情況，於是程式就噴了。理論上這是不會發生的，但實務上因為浮點數的誤差，造成這個 bug。看來得用強硬的方式解掉。

舉個類似的例子說明我的情況，用 Quadtree 存地理性資料時，當一個 region 內的資料數量超過上限時（比方每個 region 不要超過五個點），會把該 region 切成四個 sub-region，理論上可以無限地切下去直到所有 region 的數量都小於給定值。

事實上，當一部份點很散（造成起始 region 空間很大），而大部份點極為密集時，切到後來會因為 region 空間過小，浮點數不精確，而使得某些點「不屬於」任何 sub-region。比方說 region 左上角的 x 變成 296.999999999988，寬度則切為 1.82751591637498e-11，結果四個 sub-region 拼不回原來的 region。

幸好我有加 assertion 檢查是不是所有點都在切開的 sub-region 內（如同廢話般的檢查），不然寫到後面 debug 時就慘了。隨手養成的好習慣，總會在無形之中救了自己。

IR and DM algorithms codes

http://www.igvita.com/。好站一推，不止有code教學，連觀念的講解都超清楚的。比方說這兩篇：

• SVD Recommendation System in Ruby
• Decision Tree Learning in Ruby

看來以後用Ruby寫code會愈來愈方便啊！不過愈是了解Ruby運作的方式，愈是不敢對它的效率抱以期望。

勇闖資訊新未來：打造資訊科技的幕後英雄

書藉基本資料： 勇闖資訊新未來：打造資訊科技的幕後英雄 (Out of their minds : the lives and discoveries of 15 great computer scientists)

前幾個月對於是否要讀博班、是否要從事研究工作感到困惑，就找了這本書來看，看看大師們怎麼說。中譯名稱不太好，這本書收錄了15位Computer Science 界大師的傳記，並穿插和大師們的訪談。從軟體到硬體；從計算機結構、演算法到人工智慧，包含諸多CS子領域。最後的後記分析大師們成功原因的異同。這本書的中譯相當不順，如果可以的話，或許讀原文較好。

總結來說，大師們相似部份很少，令我驚呀的是，包含發明BNF的John Backus在內，有幾位大師是年輕時不知做什麼好，先去當個幾年兵回來，才找到人生方向。遺憾的是，究竟是什麼讓他們找到目標，書裡沒有進一步的說明，似乎男人當個兵回來就能發現方向。仔細地分析，演算法、學術型的大師，大多是學生時代就表現過人，可能不是在CS領域發光發熱，總之就是優於一般水平的學生。至於對研究的看法，看法差異很大，Dijkstra說找最難的做；提出planar graph快速解法、network maximum flow的Robert E. Tarjan說要挑對問題，從實際應用面下手；然而對分散性系統有深入研究的Leslie Lamport（提出bakery algorithm）說要找有興趣的問題，他甚至這麼說：

我也很懷疑別人會因為某項問題非常重要，覺得此項研究非常有趣。好的研究來自於你認為某項研究是有趣的，然後想要好好和它玩一玩。

其它像讀到Fred Brooks的故事滿高興的，我很喜歡他寫的《人月神話》，這本大概是我做筆記最認真的一本書。還有Douglas Lenat提的Automated Mathematician和Cyc也很有趣。沒有絕對的正確，我們有許多認知相互衝突，現實世界不如數學，能用一個完美式子推衍含蓋，人工智慧的研究也該接受現實的亂象，才有可能實現。人類在判斷時會依自己的認知，潛意識地在不同的前提做出正確的判斷，比方書中提的例子，「德古拉是誰？我們會回答「吸血鬼」；世上有吸血鬼嗎？我們會回答「沒有」。即使上述兩個問句和答案，邏輯上令機器感到困惑，卻不會造成我們任何困擾，因為問答時的背景不同。

若對研究感到一些疑問，讀這本書只會得到更分歧的答案。不過就像讀個案研究一般，讀到一個程度後，會對於整個時代背景有些感覺，而明白一件事，我所處的時代和他們不同，他們的故事無法給我明確的指引，我得自己走一遍，才知道自己的路在那。之前問一些教授他們當時要出國讀博士，才發現他們的環境和現在不同，所以老教授們的回答差不多：他們是不得不出國。現在學校的選擇變多，工作的可能性也變雜，使自己過於煩惱要怎麼選。經過這些談話，以及讀過這本書後，我體驗到時代背景差異的重要性，事前準備已夠了，我得多花點時間在自己的嘗試上。

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

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

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

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

social network推薦機制

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

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

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

搜尋與推薦

原本想下的標題為「資訊傳播的推與拉」，轉念一想，這麼遜的標題大概沒人想看。

依《隨意搜尋》的分類，資訊傳播的方式可分為「推」 (push) 和「拉」 (pull) 兩種。舉例來說，傳統入口網站如Yahoo的做法，是透過人工編排網站，將資訊「推」給使用者；相反的，Google的搜尋引擎則是讓使用者自己「拉」資訊。廣為人知的關鍵字廣告，則是成功將「推」、「拉」兩者整合成功的獲利方式。相較於傳統橫幅式廣告，關鍵字廣告的成功如今已不需多做說明，有興趣了解背景歷史的話，可以參閱《搜尋未來》，書內有提到當初Overture的創辦人Bill Gross怎麼提出這個構想，以及被Google拿去使用後的發展。

前陣子有幸參與一場很辦的討論，聽到搜尋的可能性，如今Google發展成熟的關鍵字搜尋，其實不過是搜尋發展的冰山一角吧，搜尋的方式仍有很多可能性，現今諸多 Vertical Search 網站是很好的例子，以 location based service (LBS) 為例，我們可以問：「離我最近的加油站在那？離我最近的餐廳有那幾家？半徑五公里內有那些電影院？」從而產生大量的新應用和獲利模式，不在此多提。值得注意的是，搜尋的輸入方式不止有關鍵字；輸出方式也不止有網頁。

除了搜尋種類的變化外，依人、時、地來看，任何搜尋都可以變得更精緻。以關鍵字為例，若你是珠寶商，搜「Ruby」時，你預期看到珠寶相關的事；若你是程式設計師，你預期看到程式設計相關的事。搜新聞時，當我們鍵入「颱風警報」，預期看到的是最近的消息，再者，預期看到的是自己所處地域的消息。搜尋的延伸變化多端，絕不如我們現今看到的如此單調。

然而搜尋有個極限：使用者必須提供資訊。有時候使用者不知道他要什麼，或著是他沒想到。創造未知的服務，正是開拓新市場的契機。舉例來說，統計過各個消費者的購物記錄後，可以推測出他們可能在什麼時候需要補貨，也可以依貨品的互補性提供優惠，比方小明常買泡麵，告知小明最近熱水壺在特價，或是買十箱泡麵送熱水壺，可以促銷。推廣一層來看，除了個人的過去記錄外，可以分析他的社交圈，比方小明常和大毛、二毛一起看電影，最近大毛、二毛看了部新電影，小明還沒看，可以推薦小明去看。再廣義點來看，小明並不需要真的認識大毛和二毛，只要他們的興趣相似就夠了。於是 social network 帶來了新的發展，從最近火熱的 FaceBook 相關新聞可窺知一二。當然，個人使用記錄和 social network 也可以用在搜尋，強化個人化搜尋功能。

這看起來像是「推」與「拉」模式的變化，當「推」的方式變得更靈活、不如傳統入口網站笨重時，應該會出現別於關鍵字廣告外的全贏模式。全贏是指平台經營者 (例如Google)、服務提供者和消費者都滿意，都能從中獲利。

search驗證的方法

兩個月前寫的心得，當時沒餘力將心得整理得更完備，隨手寫了草稿，丟了也可惜，先放上Blog備忘吧。

警告：本篇的心得並不嚴僅，只是抽樣讀了幾篇近二年SIGIR論文，簡單歸納的結果，不見得正確。

我從SIGIR’06、’07裡用ranking當keyword找paper title，隨意挑幾篇有興趣的paper看，只看abstract和實驗裡keyword附近的說明，簡單地整理一下驗證的方法。

驗證 ranking order 的差異性都是用 Kendall’s coefficient of concordance，這個方法對 n 個 item 比較 C(n，2) 對的差異，若比較的兩個 item 在這兩個 ranking 的 order 一致就 +1，不一致 -1，其中一邊相等則為 0，總合除以 C(n，2) 即為結果，1.0 表示完全一致，-1.0 表示完全相反。

驗證 ranking 的正確性時，常用的測量基準是: NDCG，MAP (Mean Average Precision)，和 k-precision (取不同的 top k 結果看 precision)，個人覺得 NDCG 很怪，無法像 MAP 或 k-repcision 從數字值理解出大致狀況，只能從高低之分得知那個好，但大概接近半數論文採用這個做法，而且作者都說這是well-known，很有用的基準。它的概念不差，強調名次之間重要性的差異，就性質的判斷來說不錯，但無法判斷重要性的差異有多大。例如，我們可以用NDCG了解 A ranking 比 B ranking 好，但無法從數據得知好多少。而且這個整體差異也許是某局部計算帶來的，很難分析數字計算出的成因。

在使用這些基準前得先決定兩件事：

1. query words。
2. groud truth，也就是那些文件和query相關。

這兩者通常會一起討論，比方使用TREC的資料，裡面已有整理好的documents和queries，以及標示為相關與否；或是從 search engine log裡找 click 的情況 (大公司的玩法)，將資料多的網頁取出，先透過某種搜尋方式 (e.g. by Lucene) 取出 top k，再由人工驗證相關與否。不管怎麼說，人工驗證耗時可靠性又有限，但很難避開這問題。

以上的準備結束後，再來要說明自己的方法真的有效，於是要找個替死鬼來打，說自己的方法比它好，早期的論文可能會用 tf*idf，一個針對 query 取出網頁和排序的算式，而近兩年我看到的SIGIR paper，幾乎都用 BM25 (Best Match 25)，BM25是由 tf*idf 變化出的複雜算式，似乎是某年 workshop 的冠軍，所以大家都用它當替死鬼吧。於是把自己算出的網頁權重 (e.g PageRank) 和 BM25 的結果合起來，畫個圖表說在 NDCG，MAP，k-precision 下，合起來都比單純的 BM25 好，就算達到目的了。

合的方法也有很多種，像用 RankSVM，RankNet (learning to rank的做法)，這些做法似乎是把 BM25 算的值當一個 feature (或稱 attribute)，也就是 learn 出合起來的 weight；或是用 BM25 取出 top k，再用自己方法算出來的值重排。

大致上是這樣吧，但看的時候跳來跳去沒有細看，不敢保證正確性，我只是大概了解情況而已。

近一個半月來的Clustering心得

最近做了一個和clustering有關的研究，基於不要被自己吐糟的考量下，花了一些時間讀clustering相關的東西，發現這領域真是又深又廣，永遠有做不完的題目，呃．．．有沒有意義是另一回事。趁剛結束一個階段的研究，記錄一下心得，不然腦容量有限，一個月後大概就忘了。

clustering的定義是，給定 n 筆資料，每筆資料有 d 個屬性，將資料分成 k 群。特別的是，事先沒有群的定義，只能從屬性判斷兩筆資料是否相似，將相似的資料放到同一群。比方資料是地理位置，那台北市和台北縣就挺像的，應該歸到同一群裡。注意，何謂「相似」是無法明確定義的，這是 clustering 裡一個很大問題，也提高驗證方法正確性的難度。於是，依據分群的特性，就分成許多不同題目，像是centered-based clustering，同一群資料的屬性的變異數 (variance) 要小；或是density-based clustering，同一群資料和「週圍」資料之間的密度要相近。也有將資料以 graph 表示而成的 graph-based clustering。一開始我沒把這些分類弄清楚，以為可以有某種程度的互通使用，但實測後才意識到，其實方法之間差異很大，依要解的題目特性，套錯方法效果會極差，比方資料可以輕易地轉成graph，但這不表示套用graph-based clustering會有用，至少像 graph 難以用 edge weight 表示 centroid (or mean)，所以不適合用來解 centered-based clustering。

除了五花八門的分群目標外，cluster 的數量也是個問題。是要給定 k ，找出 k 個 cluster？還是給定一個範圍？或是根本沒有數量限制？於是各群內部的相似度和分群的數量合起來，就變很複雜的問題，畢竟群的數量愈多，各群的變異數會愈小。很難同時考量兩者給個合理的評估分式，所以大部份的研究先限定 cluster 的數量，再討論如何降低變異數或其它評估值。silhouette coefficient是個有趣的公式，它的概念頗合理的，又能同時考量兩者，但我套用它到centered-based clustering，實測的結果 [1]，計算量頗大，效果也不好。原因不明，我後來沒有仔細測試和探討背後成因。

若再加上一些細項要求，題目可以組合出更多變化，像是利用每個 cluster 內最少要有幾筆資料，可以得到一些良好的數學特性，而有不錯的成果。當然，當這個數量限制難以找到合理值時，這些方法也無用武之地。細項限制帶來的變化在 clustering with constraint 中有更系統化的研究，用這當 keyword 應該會找到一大票研究，有限制不見得是加深題目難度，有時反而變更簡單，可以協助分群；甚至也可以將重心放在如何從既有資料裡生出 constraint。

從分群的反向來看，驗證分群結果也是一大難題，但似乎沒有論文在專門討論這個（吃力不討好？），我也沒仔細去找就是了。對於未知答案的研究來說，有時只要改變評估方式，大壞的結果也可能變成大好。前面提到分群的概念變化多端，加深了評估方法之間優伏的難度。Introduction to Data Mining
的 ch 8.5 有頗詳細的介紹，值得一看。

以上的心得是以該書的 ch8, ch9 和一些零星論文得來，書裡那兩章的內容我也沒全看完，若要看完那兩章並確實理解，一兩個月跑不掉吧，但若有心在這個領域研究的話，個人覺得是必須做，而且很值得做的事。最後補一些雜項，參與 clustering 研究的人，就我個人的主觀分類，可以分成 Data Mining 背景、 Machine Learning 背景和 Statistics 背景的人。依不同背景來看，方法的切入點差異很大。 Data Mining 背景是指像傳統 Computer Science 背景的做法，或是指「比較不數學」的做法。另一方面，是否一定要能處理大量資料，才稱得上有意義的方法，就見仁見智了。

ps.

1. 我的做法是用hierarchy clustering，一開始每筆資料自成一個 cluster，看合併那兩個 cluster 可以達到最佳的silhouette coefficient，就選那兩個合併。全部併完後，會有 n 種可能分法（全部一群、兩群、．．．、 n 群），選silhouette coefficient值最高的 k 個cluster當結果。

快速找中位數演算法和KNN

之前找到kd-tree這個data strucutre，想說可以用它來找KNN (k nearest neighbors)，而且建立kd-tree的速度很快，空間成本又和資料量成線性關係，實在是很讚的資料結構。

實作kd-tree的關鍵在於要能快速找到中位數，而在quick sort的Theta(N*log(N))的證明裡，有經典的找中位數演算法：用Theta(N)的時間找出中位數。不過這個演算法的常數項很大，是理論上很有意思的方法（ 由它證明了quick sort的order可以寫為 Theta(N*log(N)) )，但實務上不會拿來用。

找了一下快速計算中位數的方法，找到一篇有趣的報告：“Fast Median Search: an ANSI C implementation”。這篇報告裡提供幾種找中位數的方法以及時間比較和實務考量的分析，並附有 C source code。這篇報告用的方法都是從沒排序的陣列裡找第 k 小的數字，而找中位數只是這個問題的特殊化罷了。關鍵在於從不同的角度思考中位數的定義：

The median of a list of N values has the property that in the list there are as many greater as smaller values than this element.

很漂亮的出發點，值得學習。

我從中選了差不多最快、且馬上能讀懂的Wirth，將它改成Ruby版，畢竟我其它相關的code都用Ruby寫的（按此觀看Ruby版的Wirth）。Wirth的精神和quick sort一樣，若已學過quick sort的話，看一下code就能明白Wirth的做法。

改完Ruby版的Wirth演算法後，準備要寫kd-tree時，才想到既然我要找KNN，其實找到第 k 近的鄰居後，就可以用它當pivot快速找出前 k-1 個鄰居（掃陣列一遍而已），可以不用實作kd-tree，執行效果應該還可以接受。事實上Wirth的演算法有個副作用(side effect)，它會更動原來陣列內元素的順序，但妙的是，這個副作用在KNN裡反而省下一次線性搜尋的時間，因為找完第 k 近的鄰居後，前 k 個元素就是 KNN 了 (讀一下code立即可以明白）。

有時候意外地把不同時期學的片段記憶整理一下，串成一個完整的觀念，感覺頗爽的。最棒的是，破碎學到的東西，可以更有系統地重新吸收。

ps.

• 當然，網路上可以找到不少kd-tree的實作code，像Weka裡就有Java版的kd-tree，只是功能太雜，code太長了，以我的小規模用途來說，看懂它的code還不如自己寫快一點。
• 真的建出kd-tree的話，應該會更快，因為kd-tree建一次可以找所有元素的KNN，每個元素找的時間是O(N)，但大部份元素應該不會真的要看N個元素。而Wirth的演算法在找各個元素的KNN時，相當於每個元素重算一次，每個都是Omega(N)。有時間的話真想來比較看看kd-tree能比Wirth快多少。

Hidden Markov Model

最近被迫得讀 Hidden Markov Model (HMM) 相關的內容，我入門的方法是參考下面這三篇：

• HMM不負責講座
• Hidden Markov model
• Viterbi algorithm

最近學新東西，愈來愈習慣先看完WikiPedia的介紹再開始，WikiPedia上的介紹通常比書裡寫得還要清楚，真方便。

個人認為最好理解HMM的例子是語音辨識，摘錄Viterbi algorithm裡的一段例子：

For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the “hidden cause” of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

每個文字代表一個state，state和state之間有條件機率，稱為state transition，即文字的連續關連性，比方「駱」下個字出現「駝」的機率很高，出現「馬」的機率很低，丟個文章集統計一下就可以得知state transition。主要的差別是這裡假設每個state只會被上個state影響，所以不會直接統計「王八」下個字出現的機率，得先算出「王」到「八」才行。這點和 N-gram 的做法不同，以文字為例子的話，可以將state transition看成是 2-gram 而已。

單純文字之間的關聯已有很多發展空間，比方套用 Markov chain ，算出給定第一個字的情況，第五個字最有可能出現什麼字？或是無論開頭為何，第三個字最有可能出現什麼字？而在語音辨識的例子裡，除了 state (=文字）外，還有 symbol 。

每個 state 會產生一個 symbol ，打個比方，可以想成在數位電路裡的 Finite State Machine 中的 Moore Machine ，跟著一連串的 state 轉換，每個 state 都有伴隨輸出的資訊，但在 HMM 裡，每個 state 不會只輸出一種 symbol ，而是各個 symbol 有對應的輸出機率，所以不只 state 和 state 之間有條件機率， state 和 symbol 之間也有條件機率。在語音辨識的例子裡， symbol 是聲音訊號。畫圖太麻煩了，麻煩各位發揮想像力， HMM 的架構可看成兩層，上層是一個 graph ， vertex 表示 state， edge 表示 state 間的條件機率；下層是數排 vertices 每個上層的 vertex 對應到下層一排 vertices ，之間有個有向邊由上層指向下層， edge一樣是條件機率，表示在這個 state 下，會產生的 symbol 機率為何。

那麼 HMM 要解決的問題為何呢？直接從語音辨識來看比較容易理解，我們可以取得一連串的聲音訊號，經過處理後斷成一個個文字的聲音，但我們不知道每個聲音對應到的文字為何？考慮這個例子（喔，注音文的正當使用）：

ㄌㄨㄛˋ ㄊㄨㄛˊ ㄏㄨㄟˋ ㄈㄟ

這個例子對應的文字可能是「落鴕會妃」，也可能是「駱駝會飛」，那一個組合較合理，得看文字間的接連出現的機率夠不夠高。在 Markov chain 的例子裡，我們是直接由 state 找出 state sequence，而HMM的例子裡，我們不知道 state 為何，所以稱為 Hidden State ，我們必須由 observation ( symbol sequence ) 來推測原來最有可能的 state sequence。

注意上述的說明都是假設 model 是正確的， model = initial state probability + state transition probability + symbol probability (emission probability)。在 Machine Learning 裡有些方法說明如何找出最有可能的 model ，有空再來看看吧。

Range Search的演算法

原本找到kd-tree覺得夠威了，沒想到還有很多有趣的相關研究。像是”Data Structures for Range Searching”鞭闢入理地分析了6種方法，針對hyperrectangle range query (或稱orthogonal range search)的time complexity、建data structure的time complexity和所需的space complexity，簡潔易懂。結論是一般來說kd-tree最適用，cell（切成格狀）在特殊條件下最適用。

摘錄自1.8 Comparison of Methods：

Both the cell and k-d tree structures are appropriate in situations where the query restricts several of the attributes. If the approximate size and shape of the queries are roughly constant and known in advance, then cells defined by a fixed grid with size and shape similar to those of the expected queries is most advantageous. For queries with sizes and shapes that differ considerably from the design,

…

For most applications of range searching that are not characterized in the preceding paragraphs, k-d trees are likely to be the method of choice.

但這篇沒提到R-tree，也許那時R-tree還沒發明，得再評估一下R-tree的可能性。

關於演算法的早期研究就是這麼美麗、完備，但現在也沒什麼發展空間，只能拿來用就是了，cite ”Data Structures for Range Searching”的兩篇range query延伸研究分別是“On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures”和”Improving the performance of multidimensional search using fingers”，前者看來像理論分析，後者則是實作分析。

原本感到奇怪，為什麼這些研究都是用orthogonal range search，而不是圓形(球形)的range query，後來才想通，圓形的range query可以先用正方形的range query取出資料，再用圓形的條件去掉多餘的資料即可，效率分析差異不大。

1/5 rule self-adaptive under (u+k)-ES (2)

( 寫於2005/12/20 )

想了一種新方法, 測試結果還不錯

將sigma encode到chromosome裡, i.e., chromosome含有Gk, Gs, sigma

select a parent p,
if p.Gk == G
do adaptation (=> revise p.sigma)
p.Gk = p.Gs = 0
fi
p.Gk++

offspring = mutation(p)

if offpsring.fitness BetterThan p.fitness
p.Gs++
fi

如果parent在replacement時被幹掉了也沒差,
一直都留下來的話自然會做到adaptation
( 即parent夠優秀, 才有必要對它調適sigma )

看起來很直接的想法,
但在想出來之前, 一點也不直接, 得跳出幾個迷思才行