2007年12月31日 星期一

搜尋與推薦

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

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

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

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

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

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

2007年12月30日 星期日

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

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

2007年12月25日 星期二

先破後立

前幾天konya問我,這一個月半來想法轉變的原因,說實在的,這還挺難回答的。

我一直很喜歡這段話:

看山是山,看水是水;
看山不是山,看水不是水;
看山還是山,看水還是水。

我走過的路,常常如此,在記下過去的想法後,這個軌跡更是明顯。我愈來愈明白,為什麼成功人士都說些像屁話般的大道理,像是「態度決定高度」、「你的心胸有多大,舞台就有多大」,可惜我無法清楚地描述出這個轉變,硬要說明,也只是用更長的篇幅說屁話。但和我聊天的人,我可以依他們所處的位置,給相對應的回答。如果對方看到的還是山,我必須說明其實那不是山;而當對方明白那不是山時,我卻要更直接地點出,其實那是山。

舉個例子,《通往成功的方法》裡提到,當不知如何是好時,選困難的路。當對方接受這個想法,並落實時,必須改告訴對方,如果你努力錯了方向,再怎麼跑也到不了終點。用商管的角度思考會更直覺,我們要為客戶創造價值,產品做得再好、價格再便宜,客戶不想用,還是白費力氣。比方說現在大家普遍使用19″ LCD電腦螢幕,若製程有所突破,38″ LCD電腦螢幕的價格和19″的差不多,38″的會大賣嗎?其實不見得,考量到使用電腦的習慣和一般住家的大小,38″ LCD適合當電視,卻不適合當電腦螢幕。那麼38″ LCD沒有價值嗎?也不見得,要看針對什麼樣的客戶(市場區隔),年輕人只用一台電腦沒有家用DVD播放器或電視,平時工作用NB,多一個38″ LCD,可以做為娛樂用。

重點是,要先確立客戶需求,再行研發;先確立自己的目標,再開始努力。那麼,為何一開始要說選困難的路?因為那總比不努力來得好。我也很喜歡這句話:

沒有前提,沒有答案。

在「看山」的議題上,有類似的意境在。要破還是要立,端看我們處在什麼位置。

附帶一提,當我們回頭看山是山時,內心的想法已有所不同,這個想法轉變,將帶動其它方面的提昇,比方眼界更廣,立足點更高,連帶反映在日後的行動上。我愈來愈常聽到人生歷程的前輩和我說最重要的還是「人」,或是最重要的能力是「態度」,不管在什麼情境,在什麼考量下又聽到這老掉牙的詞時,我漸漸明白他們的意思。

在不斷地自我提昇後,我們無法簡單地和他人解釋這一串成功背後的原因,因為在每一階段,內在和外在都在轉變,沒有一個方法能含蓋這個過程。當我們在 A 情況時,我們該這麼想,進入 B 情況後,應該改成這麼想,...。面對一個素昧平生的人,想分享這一系列的想法,太費時也無助益,於是只能用最後的體悟來回答對方,而形成另一個屁話。

2007年12月20日 星期四

無入而不自得

晚上和 ltw 閒聊了一陣子,剛才靜坐時忽然想到「無入而不自得」這句,查了一下原文,深有同感。偶而讀讀古文,可以感受到中國文化的博大精深。真的,真理早已被前人記錄下來,只是我們還沒參透。

原文出自中庸

君子素其位而行,不願乎其外。素富貴,行乎富貴;素貧賤,行乎貧賤;素夷狄,行乎夷狄;素患難,行乎患難:君子無入而不自得焉。

2007年12月19日 星期三

自信和積極

剛才看到李開復寫的文章:《給中國學生的信:做個積極主動的你》,有些啟示。

先談「自信」,高中時我寫下這樣的疑問:

人為什麼會有自信心呢? 是出於本能嗎?
還是別人給他的? 是因為有了別人的表示,
所以才會有自信心? 還是因為天生如此?
為什麼有些人會覺得自己一無是處, 很失敗,
沒優點? 是真得嗎? 還是因為他缺乏自信心?
又有自信心是來自於有能力嗎? 一個平凡過日子的人
也可以擁有自信心啊

我覺得自信心或許也可以由”看到別人沒有自信”
而導至自己產生了微妙的自信, 看到別人的失敗,
覺得自己成功. 也或許是因為自己有份優於別人的能力.
是種比較後得到的感覺

當時正在轉型的階段,經過後來六年多的嘗試,我漸漸建立出自信,有些誤打誤撞。記得李開復寫過一些文章,提及自信是需要培養的,藉由自己的經驗,我印證了這點,並了解往後自己仍有培養不同方向自信的可能性。這裡必須補充的是,當時的體悟不夠完善,真正的自信應該來自於本身,從比較而來的自信,終究會由比較而失去。唯有達到超越自己,才能自強不息啊!對此觀點有興趣的人不妨看看電影《霍元甲》。

不只自信如此,認識會長、skylight這類人,給我最大的啟發在於積極的程度。常會發現「原來也可以這麼做哦?」,接著反問自己:「我為什麼不這麼做?」,而在和家人或朋友聊天時,在他們身上看到我過去的疑惑,從而明白我的確有在前進。對於那些未能踏出的朋友,也只能簡單地分享觀念,待他們自己踏出來。

這裡引用李開復該篇文章裡的一些反面例子,深有同感:

他們總是抱怨:「我沒時間。」——這表明:又是外力控制了我,讓我沒有選擇的機會。
他們還喜歡說:「我不得不如此。」——這其實意味著:迫於環境或他人的壓力,我只好選擇服從。
他們在自我表白的時候說:「我就是這樣的人。」——這其實是在宣稱:我已經無法改進或提高自己了。

對於沒時間的觀點,李開復給了一段說明:

遇到困難時,不要找藉口,應該多想一想,有沒有別的解決方案?能不能將問題分解開來,一步一步地加以解決?或者,是否需要先提高自己在某方面的能力,然後再回頭來處理這個難題?不要因為逃避而說自己沒有選擇或沒有時間——沒有人缺少時間,只不過,每個人分配時間的方式有所不同而已。

漸漸地,我發現自己在挑合作伙伴時,不像以前那樣極力看重個人能力,而轉為看重態度,或著更明確的說,是積極的程度。

然而,在沒有明確目標時,人很難有熱血地衝衝衝,像我自己,時常覺得我憧憬的生活,是悠閒自在,到不用成就一番大事業,只是偶而又不甘於平凡,想做點什麼。李開復是這麼回答的:

美國人很喜歡嘗試不同的工作,他們一生中平均要換四次工作。在長期計劃經濟的思想影響 下,更多的中國人不願意換工作,而更傾向于終生做一件事。其實,換工作崗位的意義在於,你一開始作的決定並不一定是你的終生決定,你仍然有機會去嘗試更多 的東西,只有這樣才能真正找到自己的興趣所在,才能最大限度地發揮自己的潛力。

所以,不要因為暫時不瞭解自己的長處而猶疑不決。大家要珍惜每一次嘗試,因為機遇往往不可複製。要隨時作好準備,以免機遇到來時錯失良機,同時也應學會從每一個失去的機遇中吸取教訓。此外,只有敢於挑戰自我,你才能充分地開發自身的潛力。

這和Paul Graham的格言一樣,有兩條路可選時,走難的那條。當選擇差不多時,有時這意外地受用。

ps

李開復果然是大道理天王啊!之前略讀「最做好的自己」時,就覺得那是本佳言錄大全,偶而讀很有感受,但讀太多時會感到很空虛。學而不思則罔,思而不學則殆。

2007年12月16日 星期日

高中生活

得先感謝shakalaca,豬頭站沒倒,偶而能回去看看高中的文章。

發現我高中時真是一整個熱血啊,當時大概是最接近我理想的學習環境,難怪剛上大學對於大學環境的落差難以接受,畢竟幻想破碎了。

在高中這麼忙碌的時間裡,還能寫一堆無聊自娛的東西,像是GTK版的雙人對戰五子棋、Linux console版的網路對戰貪食蛇、bash版的電腦鍵盤電子琴、bash版的Hanoi、自以為的平行處理排序,還有高一和邱、孝銘、ggod一起在社辦coding的事,真是一生難以忘懷的事,常寫到八點被校方強制斷電,接著聽到大家大喊「幹!又停電了!」,那種感覺真得很棒。後來高三用OpenGL寫的天蠶變,以及最後未完成的大計畫:HSNU Game(簡稱為H-Game,一群人合寫到萬行呢),印象到是比較薄弱,大概是申請上學校後時間較鬆,成就感較低。

一路走來似乎有堅持理想,也不可否認看法變得愈來愈實際,嗯,現在的我覺得,純理想是難以實現的,也許高中的我會認為我在狡辯,然而現在的我,確實認為兼顧現實考量的理想,才有實現的機會,而不會淪為夢想。

ps

「自以為的平行處理排序」值得解釋一下,當時我和孝銘一起做科展,在Red Hat 6.x下,把一台電腦輸入的資料,用TCP傳到自己和另一台電腦上排序,再傳回來合併。當時胡亂看了一些平行處理的書,一開始不太順利,後來速度真的有變快!只不過科展結束後才發現,原來是網路傳輸時掉資料,排的資料變少才變快的...。

2007年12月15日 星期六

讀iWoz初感:耐心

最近和一些朋友聊天時,加上自己做研究的體悟,耐性真的很重要,比快速的反應力還重要。從網路上大師的文章讀到,從學長那聽到,自己體會到,還有發現學弟又遇到一樣的問題。看到Woz提到「一次跨一步」的重要,再次從不同背景的人身上獲得印證。

p75,培養一次跨一步的耐性:

多虧了這些科學計畫,我得到了在工作上終生受益的核心能力:耐心。我是說真的。大家往往低估了耐心的重要。我是,說從小學三年級到初中二年級,我所進行的科展計畫讓我逐漸學到多事情,學會如何把電子元件組合起來,而不是只懂得翻書。多時候我想,天啊,我真是太幸運了,看來我似乎從一開始就幸運走對方向,從小就學會一次跨一小步的做事方法。我學會不要太擔心結果,而是專注在做事的過程上,並且要盡可能把事情做到最完美。

今天在工程界做事的人並非每個人都有同樣的領悟。我在蘋果電腦和其他公司工作的時候,看到很多怪才想一步登天,卻不肯先一步步完成中間的步驟,出來的結果當然不對,絕不可能行得通,那只是一種認知層次上的發展結果,如此而已。如果沒有經過實做,你無法單單在認知的層次教會別人下兩步該怎麼走。

話說回來,也如同Woz在書裡提到的,不要隨便相信任何事,科學家的精神就是要自己動手實驗。不少大道理大家都聽過,實際走一遭後才會確實了解,而不是單單知道而已。令人為難的是,當自己走到一個程度後,難以和別人分享自己的經驗,以減少別人的冤枉路。我們只能剛巧碰到差自己一步的人,向他們請教,或協助他們,讓自己跨向他們的所在,或讓他們跨向自己的所在。所以我喜歡像這樣一路記下自己的心得,減少自己忘記成長歷程的遺憾。

讀iWoz初感:父母的教育

Blog的好處就是,即使你不是偉人,仍可以寫篇落落長的回顧感謝文。

「 如何選擇科系與工作」文中提到找工作的三個指標:

「我喜歡做什麼?」、「我擅長做什麼?」、「我覺得做什麼最有意義?」
這三個問題,其實是卡內基訓練的黑幼龍先生提出的。他說:
「要判斷一個人是否成功,
就看是否常常做他最喜歡、最擅長,和最重要的事,
如果他都能做到,就表示他符合自己的興趣、能力和價值觀。」

我不知道我熱愛什麼,於是,我拿起iWoz,先看看熱愛當工程師的人是怎麼看的。Woz在書的前幾頁提到,他今日的成長,來自於父親從小帶他的方式,讓他接觸到工程師的樂趣,激起改變世界、改善生活方式的想法。我想到自己的成長背景,忽然明白為什麼成功人士都會感謝小時候的環境,即使有時看起來關聯性不高。以前我看到費曼感謝父親給他的教育,我感到納悶,這樣的教育也許不多,但不是誰都能拿諾貝爾獎,為何他將父親的教育當做首功?現在我似乎懂了一些。

我對小學以前的記憶很模糊,國二以後的記憶卻很鮮明。國二那年,爸媽為了鼓勵我讀書,說考個班上第一名,就送我一台Sega Saturn!為了能在家練KOF系列,去電動場才不會被電,那次考試有比較努力一些,因綠巧合剛好塞中第一名,而我父母也確實實現他們的承諾(結果這個承諾造成我日後近視的主因,一個暑假從1.0/1.0掉到0.6/0.3,還自以為遊戲字太小)。在那之後成績漸漸穩了下來,父母的管理也愈來愈鬆,忘了從什麼時候開始,我甚至能說我要去電動場玩,會晚點回來。或是當父母外出,剛好可以載我回家時,我可以在漫畫店慢慢地邊看漫畫邊等。

當然,高中社團的轉機,造就我讀大學時的優勢,則是另一個故事了。不管怎麼說,沒有高中時對我的完全信任,讓我能每天在社團待到晚上八點回家,九點十點到家後再開始讀書,也不會有高中練功的機會。於是,持續的良好表現,和持續的管理鬆綁,持續的向父母聊我最近做了什麼、去那裡玩,到後來父母唯一在乎的事,只剩我的健康狀態,其它事情,都隨我發展。也許是這樣的成長背景,造就我現在的樣子吧。

2007年12月12日 星期三

群眾機制評價的問題

相較於專家機制的評價,群眾機制的評價普遍存在強者強,弱者弱的問題。以YouTube來說,很多人看過不見得是好影片,後進的讀者看到很多人看,跟著點那些「熱門」影片,發現很無趣後也來不及了。雖然有評分機制,多人看的影片似乎是4或4.5星,參考價值不大。像熱門排行榜更是極端,除非有做適當的分隔,像依上傳時間區隔,否則新產生的內容難以追過舊有的熱門內容。

有些網站會用文章是否被捲到底,來判斷是否真的有被閱讀(也許再加上一點時間判斷),而非點了就算一次。依人類閱讀的習性來判斷影片或網頁是否有被完整觀看,甚至是自動判斷觀後旳評價,應該有發展的價值。影片用時間判斷,文章可用時間和被捲動的情況。配合真的有給評價的數據,這可視為classification的問題:

  • 基本屬性:觀看時間長度內容被看過的比例
  • 外部屬性:使用者的個人資訊、過去的行為如看過的影片(網頁)、好友清單
  • 分類的目標:給予的評價(例如:0~5顆星)

研究進行的流程大致上是:

  1. 分析問題的嚴重性,即影片熱門指數的誤報比率(定性分析,這問題是否真的存在,誤差到一定的值視為有)或各影片誤報程度的平均值(定量分析,將誤差量化,了解問題的嚴重性)
  2. 在給定基本屬性的情況下建classification model的結果,能改善多大程度?可用cross validation做驗證手段
  3. 考慮外部屬性,先討論如何整理外部屬性成可用的資料,再看引入後對問題的影響程度
  4. 應用到實驗平台,觀察使用者的反應,分成使用者回報感想和自動判讀指標(參考第一步的分析),綜合判斷改進的程度

若能拿真實資料玩玩,應該很有意思。忘了是誰說的,真正的研究,應該是來自於日常生活的體驗。