搜尋器

2009/02/10

一。

生活跟Google有很大關係。

我把所有電郵都forward至gmail,同時習慣把文件forward給自己,當流動硬碟用,兼具backup功能;大部份我的文都是在google doc寫的;我進行實驗的數據也是在google doc內;每天努力地爬的新聞也都在google reader內;已經沒有用bookmark,打兩隻字然後google方便得多。

我時常想,如果有天,沒有了google,我真的會唔知點死。

二。

Google在世紀初的第一次互聯網泡沫裏,擊敗了yahoo成為最強搜尋器,因為兩位創辨人提出了前所未見的概念。

二。零。

在Google出現以前,搜尋器跟閣下notepad裏的search基本上沒有分別。

搜尋器只會配對在網頁裏和query的字眼,然而這個方法很不準確,很容易被人manipulate。Google搜尋方法(跟據Brin和Page在九八年發表的論文)的基本原則,是認為如果一個的網頁連結了另一網頁,某種意義上是投了那個網頁一票。而Google的搜尋器,是透過分析網頁上的超連結,來區分不同網頁的重要性。簡單來說,愈多人連結的就愈好愈重要。

二。一。

基本上,這是個「自由行」。

可以想像成,一個人,由某個隨意的網頁開始,在網頁上隨意地按一個連結,然後遊到新一頁,然後又亂按一個連結,一直無止境地亂走下去。途中紀錄每個網頁被訪的次數。被重覆到訪的次數愈多,代表這個網頁被愈多人連上,即指這個網頁愈為重要。

「自由行」,亦即是人所共知的PageRank。

二。二。

又或者,整個互聯網是一個Directed Graph。vertex代表一個網頁,一支edge由vertex i指向vertex j意即網頁i上有連結指向網頁j。這是一個在graph上面的random walk。

二。三。

又或者,可看成一個Markov chain,我們求的是stationary distribution。重要的網頁,自然有較高的frequency。

二。四。

咦咦咦咦咦。等陣先。

如果有條茂利,起個網站,淨係得兩頁,自己link自己,跟住响出面求其地方,放條link連去自己果兩頁度,那個random walk咪會失效?!意思係,如果「自由行」行到金至尊,入到去睇完個金廁所,先發覺原來係冇出路既,咁就永遠被困住响個金廁所裏面喇。佢地永遠留响個金廁所度,但咁又唔等於個金廁所德高望重喎。

當然史上最偉大公司的兩位創辨人沒有那麼笨,至少他們考進stanford讀phd(而兩年前我報stanford的master也給reject了)。

他們也知道有世上有這些茂利的存在,於是他們在「自由行」的時候,加了一個「自由跳」的機制,每到新的一頁,在亂按之前,會先擲骰,擲中一點就求其飛去互聯網的求其一頁。(當然擲中一點只是個比喻,傳說中,Google使用的機會率是0.15)。

二。五。

當然,呢個咁簡單既模型是Page跟Brin兩位先生十一年前用來出paper的。响academia生活過既人都知,從來,最好既野,通常都唔會用黎出論文咁浪費既,真係咁正既話,點解唔自己做左佢然後搵真銀?

今日,pagerank只不過係一個好基本的模型。裏面真正既運作就真係木宰羊。

二。六。

咦咦咦咦咦。又再等多陣先。

翻查史料,第一個提出並應用網頁連結作分析的,是個叫做Jon Kleinberg的人。一九九七年,他是康柰爾大學的研究生(好似係),他發了史上第一篇文,關於如何透過超連結來找出重要的網頁。

這個意念今日沒有人會覺得新鮮,因為Google已經進行最龐大的user studies。不過,在一九九七年,當他第一次發表有關論文時,竟然給人reject,後來幾經辛苦到九九年才給發表。跟據citeseer,Jon Kleinberg果篇文俾人引過一千六百八十九次,而PageRank只係比人引過一千零四十三次。事實證明,象牙塔同現實係少少距離。

今日,Jon已貴為康柰爾大學電腦系的教授。不知道Jon會否夜半夢迴,想「頂,如果當日我做多少少,今日就可以有私人飛機⋯⋯」

(未寫完,再續,容許我緩慢的寫⋯⋯)

廣告

7 回應 to “搜尋器”

  1. 悟樂 Says:


    如果一日…. Google 話唔做…

    真係唔知會點算…….

  2. michelle Says:

    哈,做個行寫D嘢你唔同喎 🙂

  3. kklo Says:

    關於二。零。
    在 Google 之前,搜尋器與 notepad search 還是有分別,搜尋器應該是用向量空間模型的

    而且 Pagerank 著墨的是 “rank" 的部分,將重要的網頁排前。至於search 方面,不肯定 Google 有沒有公開過

  4. 周游 Says:

    我也是自甘墮google網的,一切都放在這銀行戶口了,只能希望它一直強下去。
    你有無用chrome?我day 1 便裝了,但仍覺得不及firefox。

  5. circle Says:

    最近在看paper, 不記得那一份(所以我不是做academic research的好材料..XD)說 PageRank 其實是一個利用連結將某d野撒開去o既 algorithm, 的確只要加少少變化, 就可以有好多新用途了~ 例如有人整o左個叫 TrustRank 的東東去detect web spam~

  6. Gilbert Says:

    我都係,依加寫緊個time counter 計下我自GE己上網習慣,GOOGLE 應該會係第一名:P
    一篇幾值得我地反思幾文章
    http://www.codinghorror.com/blog/archives/001224.html

  7. wiwiana Says:

    我都係極度依賴google﹐除左個爛鬼picasa之外﹐從gmail到google map﹐冇左邊樣都唔得。如果有日google獅子開大口要收年費﹐睇怕就算一千幾百都要豪俾佢…


發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

%d 位部落客按了讚: