MMDays – 網路, 資訊, 觀察, 生活



« | »

字字珠璣: TF 和 IDF

Posted By Mr. Thursday

在今日我們可以從網路上吸收大量資訊,有時候一堆文章看不完。如果我們想要吸收資訊,時間卻又不夠的時候,使用電腦幫我們過濾資訊,或是用電腦幫我們做個總整理,是個方法。如果今天手中有一篇文章,我們想要用電腦幫我們找出這篇文章最重要的關鍵字,要怎麼做呢?在資訊檢索 (IR: Information Retrieval)領域裡面,有個基礎的方法,入門必學的方法,就是使用 TF IDF (TF: Term Frequency, IDF: Inverse Document Frequency)。使用這兩個估計值,可以讓電腦具有計算重要關鍵字的能力,進而節省我們的時間。

接下來讓我們看看,TF IDF 個是甚麼東西呢?TF 全名是Term Frequency,也就是某個關鍵字出現的次數,譬如說某篇文章裡面,「電腦」這個詞出現很多次,或是「使用者需求」這個詞出現很多次,那麼這些詞句的出現頻率,就會很高。一篇文章中出現很多次的詞句,必定有其重要性。譬如說一篇論述「人工智慧」的文章,「人工智慧」這個詞句再文章中出現的頻率也一定很高。然而為甚麼除了 TF  (Term Frequency) 以外,還要有 IDF (Inverse Document Frequency) 呢?

讓我們先想想,如果單使用某個字詞出現的頻率,來判斷一篇文章最重要的關鍵字,會有甚麼困難。首先,我們會遇到一些常用字詞,出現的頻率也很高,會和重要字詞出現的頻率一樣高,讓電腦因此無法分辨出,哪些是常用字詞,那些是重要字詞。如果就英文來說,有個規則是語言學家 (linguist) 歸納出來的規則,叫做 Zipf’s Law

引述中文維基百科的一段介紹如下:

從根本上講, 齊夫定律 可以表述為, 在自然語言語素庫 里, 一個單詞出現的頻率與它在頻率表裡的排名成 反比. 所以, 頻率最高的單詞出現的頻率大約是出現頻率第二位的單詞的 2 倍,而出現頻率第二位的單詞則是出現頻率第四位的單詞的2倍。這個定律被作為任何與 power law probability distributions 有關的事物的參考。 這個 “定律” 是 Harvard linguist George Kingsley Zipf (IPA [zɪf])發表的.

比如, 在 Brown 語庫中, “the” 是最常見的單詞,它在這個語庫中出現了大約 7 %(10 萬單詞中出現 69971 次)。正如齊夫定律中所描述的一樣,出現次數為第二位的單詞 “of” 占了整個語庫中的 3.5% (36411次), 之後的是”and” (28852次). 僅僅 135 但此項就占了 Brown 語庫的一半。

所以我們現在知道問題在哪邊了。如果只用詞句出現的頻率來判斷某一篇文章裡面最重要的關鍵字,我們可能會找到常用字,而不是最重要的字,像是英文裡面的 “the”、”a”、”it”,都是常常出現的字,但是通常一篇文章裡面最重要的字不是這些字,即使那些重要的字出現的頻率也很高。

這個時候我們要怎麼辦呢?IDF 在這個時候就幫上忙了。在了解 IDF 之前,我們先了解 DF 是甚麼。DF 就是Document Frequency,也就是說,如果今天我們手中有固定 N 篇文章,某個關鍵字的 Document Frquency (DF),就是說這個關鍵字在 N 篇文章裡面出現了幾次。Inverse Document Frequency (IDF) 則是把 DF 取倒數,如此一來,一個數字乘以 IDF,就等於是除以 DF 的意思。

有了 TF IDF 以後,我們就可以計算 TF 乘上 IDF對每一個關鍵字都算出一個分數。這個分數的高低,就代表了這個關鍵字在某篇文章中的重要程度。為甚麼我們說這樣子可以找出重要的字,而不是常出現的字呢?因為 TF 會把某篇文章中,出現最多次的排在第一位,其次的排在第二位,以此類推。然而乘上 IDF 以後,也就是除以 DF,那些常常出現的字,像是英文中的 “the”、”a”、”it”,因為每一篇文章都會出現,所以 DF 就大。DF 大,取倒數之後的 IDF 就小,IDF 小,乘上 TF 以後,雖然”the”、”a”、”it”在某篇文章中出現的頻率很高,但是因為 IDF 小,TF * IDF 一相乘,重要性就變低了,我們 (電腦程式) 就不會把這些常出現的字,誤認為是重要的字了!

真正重要的字會得到甚麼樣子的分數呢?如果這篇文章剛好在講 AI,”AI” 出現很多次,因此 “AI” 在這篇文章裡面的 TF 很高。然而我們電腦資料庫裡面的 N 篇文章,並不是每一篇都在講  AI,也因此”AI”可能只有在 N 篇文章裡面的某 3 篇文章出現,因此 DF 只有 3,IDF 變成 0.33,假設我們 N = 100 有 100 篇文章在資料庫裡面,其他常出現字像是 “the” 每一篇都出現,DF 就是 100,IDF 就是 0.01。所以 “AI” 的 IDF 會比 “the” 的 IDF 高,假設這篇文章中 “AI” 和 “the” 兩個字出現的次數剛好一樣,乘上 IDF 以後,”AI” 這個字的分數就比 “the” 這個字的分數來的高,電腦也就會判斷 “AI” 是這篇文章重要的關鍵字,而 “the” 這個字並不是這篇文章的重要關鍵字。

所以經由 TF * IDF,我們可以計算某個關鍵字,在某篇文章裡面的重要性。從這一個方向,我們可以計算一篇文章中重點的字有哪些,幫我們做一篇文章的總整理。從相反的方向,我們可以給定關鍵字,然後再每一篇文章裡面為這個關鍵字計算一次 TF * IDF,然後比較哪一篇文章,這個關鍵字是最具重要性的,用這個方法找出和一個關鍵字最相關的文章。不管是從文章找出重點字詞,或是由關鍵字找相關文章TF * IDF 都是個基本且不錯的方法。會寫程式又還沒嚐試過這個方法的讀者,或許可以親自試試看,不過可能要先自己準備文章資料庫 (corpus),或是從網際網路上面用網頁擷取器 (crawler) 存幾篇有興趣的網頁,然後把 HTML 標籤清理乾淨,剩下純文字,就可以用這個方法來小試身手囉!

我們也可以比較一下人類和電腦的不同。電腦做數學數字的計算,或是執行固定的步驟 ,非常擅長,速度也很快。人類可以了解一個字的意思,讀完一篇文章以後,了解了意思,之後要找這篇文章最重要的關鍵字,是從「意義」開始,回憶出或做出結論,這篇文章重要的關鍵字是甚麼。

然而如果要電腦也遵照這個方向,先了解字的意義,再了解文章的意義,然後在做出結論,這篇文章的重要關鍵字,反而困難,因為要了解字的意義,電腦需要先有一個語意網路 (Semantic Network),或是知識的分類關係樹 (Ontology),把字句依照語意分門別類,有如生物裡面的「界門綱目科屬種」一般的關係分類,才有辦法了解一個字和其他字的關係。之後要了解一篇文章,又必須要了解一個句子,牽涉到自然語言處理 (NLP: Natural language Processing) 的問題,像是從句子裡面找出主詞、動詞、和受詞,以及補語,分辨出子句和主句,代名詞的指稱,以及前後文判斷產生不同的剖析 (parsing)。了解完一句,才能了解整篇文章。

因此,TF * IDF 對於電腦來說,計算速度快,工程也不浩大,不用大型計算機就可以計算。這邊也可以順便提到 strong AI 和 weak AI 的關係。如果就工程的角度,TF * IDF 是個好方法,it works! 節省我們的時間,或是解決大問題中的一個小環節。然而 strong AI 在這邊會提出「中文房間」(Chinese Room) 的論證,也就是說,電腦能夠找出重要關鍵字,是否就代表電腦真的「知道」(understand) 關鍵字的意義呢?

中文房間 (Chinese Room) 簡單地說,就是一個人關在房間裡面,只留兩個窗口,一個地方會送紙條出來,另一個地方會送紙條出去。房間裡面有一本手冊,裡面寫滿對照表,記載者看到甚麼英文字,就應該輸出甚麼中文字,以及一些指令的對照,譬如說窗口送一個指令說 COMBINE,就把兩個中文字寫在一起才送出去。接著我們在外面就開始送英文句子進去這個房間,另一個窗口就會有這句話的中文翻譯跑出來。然而這個論證想要坦討的就是,雖然這個房間看起來像是會把英文翻譯成中文,但是在房間裡面的那個操作人員並不懂中文,他指是按照指令,還有手冊裡面的對照表,機械式地動作,可是外面看起來像是這個房間會英翻中,因此這個房間應該懂得中文才對。

在這邊我的看法是,也許就近程來看,我們只要有可以解決問題的解答就可以,不管電腦是否真的 (understand) 字的意義。然而長期來說,如果我們真的需要具有人類的智力的電腦出現,能夠真的懂而不是行為上看起來懂,那麼就要仔細探討中文房間這種論證。也許生物的方法,像是計算神經科學的方法,是一個方向。

我們可能又會問,神經元只有動作電位和靜止兩個狀態,怎麼能了解意義?但是只有一個神經元,或許沒辦法了解意義,全部大腦的神經元交互作用意義可能就因此被了解了!其中的奧妙,就是計算神經科學嚐試要解答的問題之一。有興趣的讀者也可以一起從人腦開始,解決 strong AI 的問題。或是有數學的高手,也許某一個數學理論,可以很漂亮地解決意義了解的問題也說不定,像是 manifolds,具有一個集合使用不同面向來觀看的特性,同時具有 Global 和 Local 的性質,是個不錯的候選選項。從這個方向去解決 strong AI 也是另一個可能性。總之,繼續努力研究就是了!

相關連結

Posted by on October 19, 2007.

Tags: , , , ,

Categories: Mr. Thursday, 專欄, 電腦科學

« | »




Recent Posts


Pages



About MMDays - 網路, 資訊, 觀察, 生活

聯絡我們: 我們,是一群大學時代同窗的好友,在我們的時代,部落格只是一個尚未流行的概念。畢業數年後,我們也各自踏上了截然不同的旅程,在網路走入了 Web 2.0 的同時,有的人深入了資訊界,有的人到了矽谷,有的人到了紐約,也有的人在世界各地不斷奔走,我們的腳步,踏遍了半個地球。今天,透過網路和部落格,我們再度相聚,在廣大的網路世界,開闢這樣一個小小的天地,以 Mr./Ms. Days (MMDays) 為名,希望每天都能夠跟大家分享我們的所見所聞。 謝謝您的造訪,希望您喜歡我們的文章,更期待能夠看到您對於文章的迴響與指教。 Mr. Monday 主要文章內容 : 生活勵志, 網路科技新奇事物 Mr. Tuesday 主要文章內容 : 電影評析 Mr. Wednesday 主要文章內容 : 網路搜尋引擎, 社交網路 Mr. Thursday 主要文章內容 : 生物資訊科技, 機器學習 Mr. Friday 主要文章內容 : 網路生活, P2P技術相關 Mr. Saturday 主要文章內容 : 網路企業, 人工智慧相關 Mr. Sunday 主要文章內容 : 資訊新知分析 Mr. Holiday 主要文章內容:軟體工程,行動通訊技術 Mr. March […]more →
Switch to desktop version