IR and DM algorithms codes

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

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

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

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，再用自己方法算出來的值重排。

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

MSRA推出Benchmark Datasets for Learning to Rank（LETOR）

剛才收到老師轉寄給lab的信，Microsoft Research Asia推出LETOR。研究ranking的最大問題在於沒有共通測量標準，於是某學者參考了99個model後提出了第100個model，但沒有人知道這100個model差在那，適用在什麼樣的資料。

MSRA推出的LETOR想建立一個通用標準，幫助評量各種model。在machine learning裡，讀入一堆traninig data改善model內部結構稱為learning，machine learning的做法多為自訂一個model，透過learning建出model後，就能拿來應用，比方ranking web pages（PageRank不是machine learning）。

官網也提到MSRA會在SIGIR’2007用LETOR辦個workshop，看起來很有意思，也有助於MSRA建立LETOR的地位。目前來看，MS Research的東西看起來都挺有趣的，只要在十年內能弄出強大的新功能，MS又能站穩它們的地位吧。

另外那篇公告是放在users/tyliu/目錄下，看了一下tyliu的介紹，真是強的亂七八糟，SIGIR’2007上三篇！中文介紹上寫他是清華大學電工系畢業，先做multimedia再轉information retrieval，完全是不同等級的人。看來若想做學術研究，當教授不如進MS/Yahoo/Google Research吧。

額外想到的事，ranking的特徵是order，clustering的關鍵是定義相似度，可以看成比order弱的屬性。若ranking的標準成立了，是否能帶出clustering的標準呢？比方以ranking相近表示相似度，再看怎麼把ranking的benchmark轉過去。

什麼樣才叫保持連繫呢？

由無名BBS不再有保障（純個人推測），聯想到失聯。

國中以前網路不發達，失聯是很容易的事，只要搞丟小學國中電話簿就行了，對資工系學生來說，紙本電話簿本來就很容易搞丟，總覺得東西沒存在電腦裡，就會搞丟。網路發達後和朋友聯繫容易，幾個朋友去了瑞典，也沒什麼感覺，畢竟我和別人的相處以談話為主，影響不大。

我不會隨便換email，email使用頻率又高，找我是很容易的事，反過來說，找其他朋友不見得如此，要有什麼媒介的存在，才稱得上保持連繫呢？如何才能避免失聯？忽然覺得這和讀書寫筆記一樣，總擔心著學過的東西不容易找出來，思考要如何組織知識，以便隨時能快速存取，這之中最重要的是記得keyword，可藉由做index和分類達成。

query expansion是藉keyword生keyword的研究，人與人之間的連絡也能透過朋友間互找，只不過沒電腦資料這麼方便，接著聯想到人力資源類的網站，不過一般朋友不會用這種東西保持連繫的，扯遠了。

或許保持連繫和學習一樣，自然隨意就好，時機對，碰巧就會搭上，不用在意。