2008年8月27日

8/26 Regular Meeting: Learning On the Border:Active Learning in Imbalanced Classification data

本篇論文著重於某些機器學習演算法,對於資料不平衡(imbalance data)處理效能的問題。

在現實世界中一些需要分類的工作,比方說文字分類、詐欺偵測、醫療判斷等等,若以機器學習的方式處理,該怎樣達到最好的分類效果呢?標準的機器學習演算法對於平衡資料的處理可以達到極佳的預測效果,但是對於不平衡資料的預測效果卻是沒辦法達到要求。

本篇論文解釋何謂資料不平衡,以實驗驗證Active Learning對於class imbalance可以達到不錯的效果,其次提出另一種有效率的方法--以更小的sample pool訓練資料,可以減少計算的時間、減少記憶體的消耗。

2008年8月18日

8/20 Regular Meeting: Just-In-Time Contextual Advertising

Just-In-Time Contextual Advertising, CIKM’2007論文和自身的研究有著高度的相關性, 目的同樣都是去解內容廣告配適問題 (Contextual Advertising).

此論文考量到目前的網頁可分為靜態網頁 (static)和動態網頁 (dynamic), 在內容廣告配適技術上可針對靜態網頁做事前的內容分析(offline content analysis), 然而在面臨動態網頁時, 則需透過即時內容分析(online content analysis)方法. 因此該篇論文主要是探討如何在及時的情況下, 快速地針對網頁(動態和靜態)進行廣告配適.

為達到real-time 的廣告配適, 勢必要考量到網頁內容的大小, 如果分析該網頁全部的內容, 則會犧牲了網路傳輸和分析時間; 反之如果僅考量網頁的部分內容, 則可能會因為語意的缺乏, 而造成廣告的不適當配適. 作者引用了文件摘要技術 (text summarization technique)來克服此兩難的問題. [文件摘要 (text summarization) 議題, 研究已有多年的歷史了, 在不失真的情況之下, 希望擷取文章中足夠的重要語句來表達原始文章之涵義], 除了文件摘要技術之外, 作者也透過文件分類系統 (text classification system), 將語意相似的網頁和廣告進行分類, 來加強網頁-廣告間的相關性. 網頁-廣告之間的相似度的比對, 則選用了cosine similarity.

在實驗方面, 兩個資料集分別包含105個一般性網頁以及856個不存在於搜尋引擎索引範圍內的網頁, 作者針對不同的文件摘要片段 (例如: 網頁的title, meta information, URL….), 以precision , mean average precision和bpref-10為度量單位進行評估, 實驗結果數據顯示, 由少量的文件摘要資訊即可達到和使用全文(full-text)資訊的準確率效果.

論文連結: Just-in-Time Contextual Advertising
自製投影片:

2008年8月15日

08/12 Regular Meeting: Pattern Mining to Unknown Word Extraction

本次報告為我的論文: Pattern Mining to Unknown Word Extraction。

摘要如下:
中文的文件資訊處理,由於沒有如歐美語系中有區隔符號(ex:空白)斷開每個辭彙,會遇到兩個大問題: 歧義性 與 未知詞問題。

本篇的論文主要為解決中文的未知詞問題。未知詞又稱為OOV words(Out-Of-Vocabulary),顧名思義,就是字典無法辨識的辭彙。由字典輔助的初步斷詞,會將這些不存在於字典裡的辭彙,錯誤的斷開成多個部份,如人名-王小明會被斷成 王 小 明 三個字。未知詞的任務,就是針對錯誤切割的多個字元部份,重新結合成一個正確的辭彙。

本篇論文的架構,主要分成兩個階段:

1. 第一階段為未知詞偵測部份。文章裡並非所有的字元都是未知詞的候選字元,必須先經過判斷,哪些是屬於未知詞的可能字元。因此我們一開始會找尋可能的未知詞字元,並著重於單音節(詞長為1)字元(96%的未知詞經初步斷詞被切開後,會包含至少一個的單音節字元)。我們使用Prowl這個continuity pattern mining工具有效率的找出單音節字元屬於已知詞(未知詞)的特徵規則(pattern rule),透過特徵規則,對於落單的中文字,去判斷他是可單獨存在的已知詞,或是未知詞的一部份。

2. 第二階段為未知詞萃取部份,我們針對第一階段所偵測的未知詞可能位置,運用上下文資訊、POS資訊與統計資訊等,學習並判斷是否該要結合(是否形成一個該結合的未知詞詞彙)。我們使用Sequential Supervised Learning中的indirect方法,將原本的文件資料,用Sliding Window格式轉換為可分類(未知詞與否)的資料。另外,我們亦使用machine-learning的多個分類演算法進行訓練與測試。

最近新增的是未知詞萃取的實驗部分,除了先前使用的SVM、HMM之外,我們也嘗試了Ensemble method的演算法(Bagging、AdaBoost)進行擷取的測試並加以比較。另外,reference提到,imbalance class problem使用sampling解決問題時,若是能夠挑選較難分類的資料點組成training data,會比random sampling的效果更好,我們亦根據了其所提出的sampling方法進行實驗。


以上為報告前的摘要,接下來為老師對我報告的投影片所提供的意見:
1. 本論文所專注的是"中文文件處理"轄下的未知詞問題,不宜說成"中文資訊處理",因為中文資訊處理涵蓋範圍很廣,我們處理的文件只是其中之一。

2. 同一張投影片表達兩大階段的重點時,應該以對稱的方式呈現。例如"偵測"方面一開始提到使用pattern mining方法,為偵測時使用的主要方法;對應的"擷取"一開始就不應該馬上切入細部(所應用的資訊),應以擷取的主要方法- Sequential Supervised Learning中的indirect方法與Machine Learning方法列於開頭。(參考P.8為錯誤的呈現方法,應把P.9的第一段提到P.8的第二段開頭,原第二段開頭改成副段落)

3. Related Works中,General methods是否一定要以Rule-Based 與 Statistical Model-Based 來區分。可以考慮使用Sequential Supervised Learning中的direct方法取代Statistical Model-Based來解釋。

4. 未知詞的整體系統架構缺乏。目前僅有個別的兩階段系統架構,需要進一步整合為整體的系統架構,讓讀者更清楚整個處理的流程。

5. P.17的Continuity Pattern舉例錯誤。原例子{打球}比較像是String Match的問題,所謂Pattern應該是以{打*球}呈現較正確。

6. P.20偵測規則的說明不夠仔細,規則中每一個元素(字元、POS、已知未知、大括號、頻率與機率)都要清楚說明,用更簡潔的格式呈現。

7. P.22介紹字元的型態屬性時,用一句話舉例,再用字元與型態屬性互相對照介紹會更好。 P.23的BIES刪除,往後的分類依據用一般的要結合(Y)或不結合(N)表示就好。 Phase 2在訓練與測試時使用到的資訊,以Machine Learning的資料格式呈現介紹(feature dimension)。

8. 未知詞偵測的實驗,training使用8/10語料庫,testing時為何不使用剩下全部的2/10。
未知詞擷取的實驗,training來自於Phase1 testing的資料,只有1/10語料庫,為何不使用更多的語料
庫資料。
實驗想要呈現的觀點、實驗的設定要先想好,再做實驗,以免浪費時間。


2008年8月4日

Tag-based Social Interest Discovery

對於社群網站中常見的元素─標籤,我總覺得應該可以有更多利用的方法。我也曾經思考過標籤可以有哪些用途,甚至也想過可能可以代表使用者的興趣取向。可是不知道怎樣去分析,也不知道資料該如何取得。剛好WWW 2008有這一篇題為"Tag-based Social Interest Discovery"的paper,所以我就研讀了一下,學習別人的思考方式。這篇paper是由Yahoo公司的研究員所發表的,由於剛好收購del.icio.us網站,所以不難想像完全採用該網站的資料作分析與研究。底下是摘要部份:

在Web 2.0的概念下,許多社群網站開始發展且越來越受到歡迎。其中主要區分成兩類,一類是以人為核心,如Facebook、MySpace等等;一類是以物件為核心,如YouTube、Flickr與del.icio.us等等。對於社群網站來說,發現使用者群體中的共同喜好是很有用的。一來可以有助於加強使用者間的關係(有共通興趣),二來可以刺激使用者貢獻與分享更多內容。然而目前已經提出的相關解決方法中,都是基於利用使用者在網站上的互動關係來分析,這對於像del.icio.us這類網站來說是不合適的。因此本篇paper提出一個利用使用者自定標籤(tag)的新方法來找出像這類網站中的社群興趣(Social Interest),它的好處是不需要透過使用者間的互動關係來作分析。

分析所需的資料來自del.icio.us資料庫中的一部份(公開的書籤),總共有140萬個URL被20萬個使用者儲存到430萬個書籤上。這些URL對應的網頁利用英文中廣泛使用的stopword list來對文字內容與標籤作過濾,接著將過濾出來的關鍵字與標籤利用Porter stemming algorithm作正規化。結果顯示,平均來說一個URL的註解標籤數量遠小於對應網頁內容的關鍵字數量(大約是100個量)。所以如果能夠以標籤來取代關鍵字作為社群興趣發現的元素,將可以讓工作得到非常大的簡化。

首先,作者們利用實例展示URL中top-10 tf、tfidf 關鍵字和註解標籤的比較,說明標籤比關鍵字更能表達出內容的高階概念。其次,觀察top-10、top-20及top-40的tf、tfidf關鍵字被標籤字彙函蓋的程度,顯示標籤對最重要關鍵字集的函蓋程度是很高的。第三,分析標籤的發散性,其中標籤隨著URL數量的增加不會無限制的成長,而是會趨向穩定的數量。最後,檢視標籤與關鍵字的匹配率,大部份URL中較常被使用的標籤被關鍵字匹配的程度是不錯的。經由以上分析,使用標籤來找出社群興趣是可行的。

此外,作者們還根據分析結果實作了一個稱為ISID(Internet Social Interest Discovery)的系統,可以用來發現共同的使用者興趣以及依據興趣主題對使用者或URL作分群的功能。其原理是對URL中註解標籤運用關連規則(association rule)的方式找出熱門興趣主題,在此將每個張貼書籤(由user、url和tags組合而成)看成傳統上的交易資料,而user+url的組合可以當成唯一key,tags則代表item。

最後,將此系統產生的結果對資料作評估顯示:
1.相同主題群組內的URL間資料的相似度遠高於不同主題群組的URL
2.ISID系統找出的興趣主題函蓋極大多數使用者最常使用的標籤集
3.經人類編輯審查,群組中URL與該主題的相關性是夠高的

因此採用以標籤來代表興趣的方法在效果上是不錯的,同時也不需要使用者間必需有網站上的互動關係或是真實世界中額外的關係資訊。

底下是投影片部份:

Building Data Integration Queries by Demonstration

本篇論文的標題為Building Data Integration Queries by Demonstration,出自IUI 2007。

隨著網路越來越進步,許多資訊都可以從網路中取得。但使用者的資訊需求,常常是分佈於不同的網頁中。舉例來說,某個餐廳在餐廳評價網站中得到不錯的評價,但於衛生評定網站的評定是不衛生的,那麼對於想去此餐廳吃飯的人,可能就要去這些網站搜集、整理相關資訊以決定是否去此餐廳享用餐點。

使用者想要從不同的網頁資料源取得資訊,大致有兩種方法。第一種是使用者自己至各個網站取得資料並整理,但這必需花費使用者許多時間。第二種是找尋資訊整合服務網站,利用網站的功能做資訊整合,不過這些網站所提供的資料來源都來自於固定某些網站,而使用者所需的資料,不一定是資訊整合網站有提供的。

於是作者提出了一個名為Karma的系統,目標是方便使用者做不同網頁資料的整合,建立自己所需的mashup。為了達到此目摽,必需解決data retrival(如何從網站中擷取資料)、data cleaning and schema matching(如何修正missspellings以及格式不一致…等等)、data integration(如何結合不同資料源的資料)、filtering and visualization(型式不同的widget(map、table…等等)有其適合的filtering paradigms,如何找出適合此widget的filtering paradigm)四個主要問題。而這篇論文內容著重在data integration部分,Karma提供可能的值供使用者選擇,並利用constraints以及partial plans來減少可能的值,使用者不需了解query語法或資料的來源,即可完成data integration。

論文連結:Proceedings of the 12th international conference on Intelligent user interfaces Pages: 170 - 179 Year of Publication: 2007

以下為我的投影片: