2008年12月29日

DEByE─Data Extraction By Example

以下是我對這篇論文的摘要:

網路的蓬勃發展,使得越來越多使用者透過網路找尋有興趣的資訊,但如何擷取出特定的資訊是一件即為複雜的任務。因此本篇論文呈現如何從眾多的網頁資源當中去擷取資料的方法,使用者透過GUI介面提供自己想要擷取的例子(Example),而不需要了解整個網頁架構為何,利用這些例子從新的網頁中去擷取資訊並產生pattern,另外DEByE也提出從下至上的程序來做資料的擷取,結果顯示出可利用較少的例子得到較好的擷取資訊效果。

投影片:
DEByE─Data Extraction By Example
View SlideShare presentation or Upload your own. (tags: data &)

FivaTech:Page-Level Web Data Extraction from Template Pages

這一次閱讀的論文是以前Lab中博班學長與老師所發表的,目前Lab中的研究還有使用到以本篇論文技術為基礎的系統,但是仍然有些問題需要解決。如果這個系統能夠維護好並擴展改進的話,對未來網頁資料擷取的許多應用相信將很有幫助。

最早Web IE採用的是supervised的方式,必須依靠人工標註才能產生擷取資料的規則。後來Dynamic Web的研究往Template-based的推論方向發展,產生了一些unsupervised方式的論文。FivaTech就是其中之一,它可以透過多個擁有相同Template的頁面來推論出其結構,也因此把這樣的方法歸類為Page-Level。

FivaTech以多個網頁作輸入,最後產生共同的Template、Schema及個別的擷取資料。Template及Schema是以樹狀表示,與網頁的DOM Tree形成較一致的表現,其核心過程主要分成兩個較大的部份:Tree Merging以及Schema Detection。Tree Merging部份又可細分出四個小部份:Peer Node Recognition、Multiple String Alignment、Tandem Repeat Mining及Optional Merging,經過這四個步驟後會形成所謂的Pattern Tree,接著利用它來作下一階段的Schema Detection。

Peer Node Recognition主要是用來決定輸入的Tree中第1層(假設root為第0層)Node間的相似程度,相似程度大於某個門檻值以上則給定相同的代表符號(比如用英文字母a、b、c...等),相同代表符號的node則屬於peer node。peer node辯識的準確性可以說是最為關鑑,在同一個DOM Tree中,peer node代表了資料樣式的重覆,可能是data rich區域;在不同DOM Tree中,peer node的意義可以用來推斷Page間共同的Template。不過在論文中並沒有提到門檻值應該設多少,而這個門檻值怎樣設可以產生最好的結果?是否可以適用在所有情況?是我感到比較疑問的地方。因為peer node的判斷直接就影響了後面的所有步驟,只要稍有不同,產生的結果可能就差很多。

決定出peer node後,下一步就是Peer Matrix Alignment。這個階段的工作就是把不同Tree的第1層node依序並排,然後取出每一行(同一個DOM Tree)中兩個相同符號的node(peer node)間距離最大的值,裡面最大的定義為span。接著對於span值大於0的符號node,盡量將其每一行的距離調整成span的值(最大可能長度的Template);剩下部份則盡量把相同的符號在每一列間對齊,其中空出的位置可以看成是missing data。要補充說明的部份是,對齊除了可以是相同符號(空出的部份不算),也可以是不同的文字node。

在對齊步驟過後,可以得到一個Node List用來代表不同Page間的共同樣式(Template)。接下來就可以對此List作Pattern Mining的運算,將重覆的pattern壓縮起來。最後再根據不同的node在所有DOM Tree中的occurrence vector概念,由vector不一致(值不全為1)的node決定出哪些node是optional(不一定會有的資料),這個過程稱為Optional Node Merging。

以上四個步驟從root往下一層層的作下去,最後將會形成一棵fixed/variant Pattern Tree。由此再將tree中的每個node分類並決定其order,則可以得出最終的Schema格式。至於Template的產生部份,先以規則決定出參考點(用來當作template間的分界),然後定出各個小範圍的子Template,再遞迴產生出Schema中相對應的一組Template表示法。這部份規則就不再說明,有興趣的話請參考投影片。

最後是本次報告論文的投影片:

2008年12月24日

Conference Call For Paper

ICML 2009 Homepage and Paper Submission Website

Important Dates

January 26, 2009 Full paper submissions due (no separate abstract date)
Febrary 27, 2009 First round reviews available
March 10, 2009 Author response due
April 6, 2009 Acceptance notification
April 20, 2009 Final camera-ready version due
June 14, 2009 ICML tutorials
June 15-17, 2009 ICML conference
June 18, 2009 Joint ICML/UAI/COLT workshop day; MSRL

* Note that a new Review Process for 2009! Check Area chairs

2008年12月23日

CompoWeb: A Component-Oriented Web Architecture

這篇出自於www '08,是由亞洲微軟研究中心合發的一篇論文,在這邊他們提出舊有web application的開發方式缺點,並提出把component-based software development應用到web application development上面。

他們提出了兩個新的concept,一個就是Gadget,另一個為Interface,前者就是如同一個COM元件一樣,主要是要呈現某些功能或是邏輯;後者是允許Gadget可以輸出一些PME model,而Interface就是來管理這些資訊,讓其他Gadget可以去使用這些PME。

此研究如果可以開發出完整的開發平台,那必定是會造福很多開發者在管理Web application的程式碼更為容易,而且讓Web application更穩定以及提高安全性。

2008.12.23 CompoWeb
View SlideShare presentation or Upload your own.

2008年11月17日

Learning Social Networks from Web Documents Using Support Vector Classifiers

Learning Social Networks from Web Documents Using Support Vector Classifiers出自於IEEE Web Intelligence 2006, 本篇論文主要係透過機器學習的方式自動地去建立social network, 本研究首先假設已經存有不完整關聯 (incomplete relationship), 再透過SVM建立出完整的social network, 其中屬性的建立則是藉由網路文章 (web documents)來產生文件向量. 不難發現作者將判斷social network relationships的問題轉化成傳統的文件分類問題 (text classification problem), 所採用的判斷方法 (亦可視為分類方法) 則是SVM.
此外由於relationships在social network中呈現出不均衡的資料型態 (imbalance data), 此類型資料對於機器學習具有很大的挑戰 (亦即容易傾向將資料判斷成某一特定類別), 作者也採用一般常見的 up-sampling 及 down-sampling 方法來舒緩此議題. 實驗部份採用真實資料集 FOAF (Friend Of A Friend), 評估機制則以Precision, Recall 及 F-measure為主.
以下為投影片:

2008年11月5日

10/21 Data Selection for Support Vector Machine Classifiers

摘要:
本論文介紹MSVM(Minimal Support Vector Machine)分類器,其概念為"基於SVM的架構下,減少其support vectors"。此分類器應用於Fraud detection等含有數以萬計的data points,亦可以增進其他需要大量support vector才能決定的分類器之效能。 
 
內文首先介紹SVM的作用及原理,其後介紹MSVM。此技術使用fast linear programming並加入了error term來減少所使用的vectors。最後提出了SLA(Successive Linearization Algorithm)的演算法來實作MSVM,最後是實驗比較。

將MSVM和FSV以及1-norm SVM對於七個資料集運算的結果做比較,明顯的發現MSVM所使用的support vectors遠低於另外兩個分類器所需要的個數。此外,對於一些資料集來說,MSVM的效能高於另外兩個分類器 。


2008年11月2日

11/11 電腦鑑識程序之研究 A Survey of the Procedure for Computer Forensics

文港主要報告在碩士班的研究,和老師以及同學報告,與否能在資料庫研究上延續,還請老師以及同學多多指教。

摘要
隨著資訊科技的興起與電腦時代的來臨,利用電腦以及網路犯罪的問題,讓執法單位面臨了更大的挑戰與困難,如何利用在電腦上的鑑識工具來取得有效的數位證據,是當前迫切所需要的課題,一般鑑識單位針對無法開機鑑識的電腦主機,大多使用Linux Live CD整合鑑識工具研究,但以目前電腦作業系統來看,以XP作業系統佔有率最高,本文研究提出電腦鑑識程序,利用XP Live CD整合電腦鑑識工具,建置實驗環境,針對電腦犯罪情事,採集相關證據,探討解決方法。通常單一鑑識工具所提出的證據不足,但以測試多套鑑識工具使用,過程中產生的相關癥結,最後彙整鑑識報告,相信能讓調查鑑識人員於數位證據擷取上趨於完善,在法庭呈現上的證據多一分效力。
關鍵字:電腦鑑識、數位證據、Live CD。


電腦鑑識程序之研究
View SlideShare presentation or Upload your own.

資料庫延續
View SlideShare presentation or Upload your own.

2008年10月27日

10/28 Regular Meeting: Monority Report in Fraud Detection Classification of Skewed Data

摘要:
本篇論文提出一個新的詐欺偵測方法,根據現存的詐欺偵測系統以及minority report,處理與skewed data有關的資料探勘問題。

本篇論文提出的方法使用Backpropagation (BP),Naive Bayesian (NB),及C4.5演算法,配合over-sampling的方式。獨特的方在於使用一個meta-classifier (stacking),選擇這些比較performance好的base classifiers,再將這些base classifiers的預測合併 (bagging),用以改善cost savings (stacking-bagging)。

實驗的結果證明stacking-bagging的performance比起傳統的algorithms要來的好。

接著,本篇論文比較新的詐欺偵測方法與C4.5使用undersampling、oversampling、SMOTE。結果顯示當給予一個固定的決策門檻及cost matrix,partitioning和多個演算法的方式會比以整個training data set方式有比較高的cost savings。

以下是論文連結
論文連結


2008年10月12日

10/14 Regular Meeting: Pattern Mining to Chinese Unknown Word Extraction

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

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

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

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

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

2. 第二階段為未知詞擷取部份,我們針對第一階段所偵測出的未知詞可能字元,運用上下文資訊、POS資訊與統計資訊等,學習並判斷是否該要結合(是否形成一個該結合的未知詞詞彙)。我們使用機器學習(Machine Learning)中的間接式序列學習方法(Sequential Learning),將原本的序列文件資料,轉換為可分類(未知詞與否)的資料格式,再搭配SVM分類演算法進行擷取的訓練與測試。我們設計了三種長度的模型,可用來擷取這三種長度的未知詞。

此外,在擷取的實驗中,本文亦針對資料不均衡問題以及數種模型中的選擇問題提出解決的方法。對資料不均衡問題,本文使用under-sampling產生模型用資料,再使用Ensemble Method的投票方式聚集多個模型的學習能力,以提升擷取的表現。由於我們設計三種長度的模型提供擷取,在甚麼樣的情況下該選擇哪一種模型作為最終的結合方式,我們亦提供了幾種判斷的方式。

報告後大家給我的意見,已經更改於投影片中,只不過有些投影片是用動畫方式呈現,SlideShare好像秀不出來,另外上傳至SlideShare後,有部分地方變得怪怪的,因此我會再寄投影片檔給大家,謝謝。

2008年10月5日

10/07 Regular Meeting: A fuzzy symbolic Inference System for Postal Address Component Extraction and labeling

論文連結:請點此

論文摘要:

此篇論文主要是提出一個系統可以將地址的各項元素標示上不同的標籤,例如:地區名稱和街道號碼等資訊。對於有規律架構的地址格式和非標準架構的地址格式,後者在研究上顯得較不容易,因此本論文主要在解決unstructured address的問題。

首先,利用符號表示法來表示地址,建立知識庫作為標籤的依據,系統主要從輸入地址的各項元素和知識庫之間找出相似度,再利用提出的方法論來確定地址各項元素的標籤為何,所以fuzzy symbolic inference system即是對於一些較為模糊意義的地址元素加以判斷、擷取並標上標籤。

論文介紹:

a fuzzy symbolic system是這篇論文提出的系統,主要在解決unstrctured address的問題。一般我們所建的地址格式通常較為精確,可標示在Google Map上,但文中提到,類似India所使用的地址描述方式,沒有較為切確的位置,所以無法在Google Map上標示出來(有試過,但無法標出地點),因此主要想要解決的問題為此。

其中定義address和Knowledge base兩種基本格式,利用Assertion Object、Hoard Object和Synthetic Object來做表示。postal address使用Assertion Object和Hoard Object;Knowledge Base則是使用Assertion Object、Hoard Object和Synthetic Object。每個Assertion Object內都有其event,event包含了feature variable和其feature value。

而系統提出兩個方法,將我們所輸入的input component和knowledge base中的component label求算出相似度,稱為symbolic similarity measure。將求算出來的相似度依大小排序好後,再利用我們另外計算的alpha值(臨界值)去找出比alpha高的相似度,將這些比alpha高的相似度看作alpha-cut set,如果set中只有一個component label,那即為我們要找的label,並將confidence設為100,若set中的值有兩個或以上,則confidence則在50左右,可套用confidence的公式去計算出來。

這篇論文所使用的knowledge base,內容資料數量並未提到,不過根據他們測試500筆地址出來的labelling結果,高達94%,即便是只侷限在一個國家的範圍裡,其資料量應該是蠻大的。

其實閱讀完這篇論文,對目前研究領域幫助沒有很大,但仍值得做為參考。

投影片:
2008/10/07 Regular meeting
View SlideShare presentation or Upload your own.

2008年10月2日

080930 Rugular Meeting:Relations, Cards, and Search Templates:User-Guided Web Data Integration and Layout

這次報告的論文出自於UIST 2007,是由微軟、adobe及華盛頓大學所合作的一篇論文。

對現在人們來說,WWW是一個很大的資訊來源,使用者可以透過網路作旅遊計畫、購物、學習新事物或者是看電視等等,但是資訊內容極多,使用者有時候要找到適當的資訊會變的越來越難,所以他們的研究是提出一個互動式介面來幫助使用者更方便更容易的去收集、管理、組織及分享他們的資料。

對於此研究,他們提出了三個技術,分別是:
1. an interaction technique:允許使用者去規劃網站之間的關係並且使用這些關係自動地從多個網站收集內容。
2. an interface:此介面是為了合併來自數個網站的內容並且以視覺化來呈現它們,此介面稱為card.
3.a novel search paradigm:利用 search template 來從網路收集內容。
以上三種技術是會建立在summaries framework[1]上面。

最後他們也請了學生來實際操作,大部分都覺得是一個不錯的系統,不過也同時針對relation、card及search template作了一些反映。

[1]M. Dontcheva, S.M. Drucker, G.Wade, D. Salesin, and M. F. Cohen. Summarizing personalWeb browsing sessions. In Proc. of UIST, pp. 115–124, 2006.

此為這次的報告投影片

20080930
View SlideShare presentation or Upload your own.

2008年9月30日

09/19 Regular Meeting:Timely Ontologies for Business Relations

這一次報告的paper標題是"TOB:Timely Ontologies for Business Model",出自WebDB 2008。主要是關於商業領域的資訊擷取應用,但是裡面所提到的方式其實也可以用在其它領域上。我覺得這種應用蠻有趣的,而且內容並不難懂,又可以了解其它種類的資訊擷取技術。底下是這篇paper的摘要部份:

本體論(Ontology)一語出自哲學領域,主要探討存在的本質。近年來電腦科學家也將其應用在知識表達上,作為描述實體的概念以及實體間關係的模型。本篇作者主要提出一套法方來建立商業關係的本體論模型─TOB,此模型特色是包含了時間的因果關係。這種模型在商業智慧的應用上是很有用的,舉例來說,我們可以問像這一類的問題:微軟公司現在的執行長是誰?Google收購Youtube之後的獲利表現如何?

TOB是基於YAGO模型[1]之上,加入了時間範圍的表達。在商業實體關係的擷取中,主要針對以下幾種:公司與公司之間(比如收購關係)、公司與產品之間以及公司與客戶或買主之間。示範建立模型的資料來源主要有三個部份:Wikipedia Infoboxes、Reuter's news feeds以及Google News pages;分別演示了三種不同的資訊擷取方式:基於結構化資料的pattern matching技術、自然語言文件為主的處理以及由不包含時間元素的句子中推論出時間關係的方法。以下對這三種方式作個別說明:

pattern matching部份─
先前工作(Yago[1]與DBpedia[2])中已經有這種方式的處理,作者使用了29種屬性如公司創立時間、核心人員等來作比對。
自然語言文件方面─
使用基於Link-Grammar的Leila方法(只支援二元關係擷取)再加以擴充為E-Leila來擷取文字間實體及實體間的關係(包含時間的三元關係)。
時間關係推論方式─
又分為ontology-level與page-level。前者是利用模型內已有的實體時間關係來作結合;後者是利用網頁的發佈日期,將原本相對的時間描述(比如上星期)轉換為絕對時間表達(比如某年某月)。

最後 實驗結果顯示在Wikipedia Infoboxes、Reuter's news feeds以及Google news pages的關係擷取上均有不錯的precision。

[1] Fabian M.Suchanek, Gjergji Kasneci and Gerhard Weikum "YAGO:A Core of Semantic Knowledge Unifying WordNet and Wikipedia" WWW 2007, ACM Press,pp.697-706.
[2] Soren Auer,Christian Bizer,Georgi Kobilarov,Jens Lehmann,Richard Cyganiak,Zachary G. Ives:DBpedia:A Nucleus for a Web of Open Data.ISWC/ASWC 2007

下面是本次報告的投影影片:

2008年9月17日

080902 Inferring High-Level Behavior from Low-Level Sensors

低價GPS (Global Positioning System)技術的進展,引領了使用者定位的大量商業應用。

本篇是Learning and Inferring Transportation Routines之參考文獻。由於該篇的paremeter learning部份,講得不多,故找本篇來研讀。

本篇的主題是,探討如何根據原始的GPS資料,來預測使用者的日常移動行為。本篇的想法較為原始,並未考慮goal與nolvety之情形。

作者使用的particle filter,是Bayesian filter的一種變形。particle filter以近似的方式來加速計算效率。作者並推導了EM演算法的步驟。

實驗的部份,資料來源為一位使用者的90天GPS資料。GPS訊號發送之時間間隔為2-10秒。實驗顯示,與之間的模型相比,預測的準確度有顯著提昇。


Donald J. Patterson, Lin Liao, Dieter Fox, and Henry Kautz
Department of Computer Science & Engineering
University of Washington
UBICOMP 2003
The Fifth International Conference on Ubiquitous Computing (UBICOMP), 2003
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.5074


0902 regular meeting
View SlideShare presentation or Upload your own.

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

以下為我的投影片:

2008年6月19日

Google 2008 Developer Day

之前得知Google 2008 Developer Day在6/14舉行後,就線上報名參加了。雖然有把這個消息告知一些同學跟學長,最後發現卻只有我一個人報名。大概6/14這個時間非常接近期末考,大家都很忙。本來是想帶數位相機去照一些照片,無奈出發前發現電池竟然出問題,結果只好作罷。

整個會議的時間從早上8:30報到開始到下午四點結束,大會地點在台北國際會議中心。由於開幕致詞時間在9:30,所以報到完後還有很多時間。在等待開始的期間,不經意看到旁邊一位老兄用apple的ibook上網在玩twitter,我猜他可能在抱怨怎麼還不開始。另外,現場休息區的佈置真的很Google的感覺,除了有一台wii跟xbox 360可以消磨時間外,還準備了一大堆的飲料跟零食。地上的椅子也都不太正常,有的是大汽球,有的是沙包,我看到有人坐在汽球上時還不小心跌倒。

這一次大會主要分三個廳,主題都不太相同。上午的部份,我選擇參加Google Maps API的主題,下午一小時的實作報告部份我去聽了關於Open Social的成果展示,剩下時間選擇的兩個主題分別是Android簡介跟小工具(Gadget)。開幕致詞跟主題介紹都是由台灣Google研究院院長簡立峰先生演說,還順便談到了Google對未來網路的看法與願景。主要有四大部份:Google Gears、Google Apps Engine、Android與Open Social,可以強烈感覺到Google想要提出一些標準開放平台讓全世界都可以去利用,希望可以更加快速幫助網路上資料的產生與分享。其中,我覺得Apps Engine最有優勢,因為利用到Google強大的主機服務,網站管理的許多問題將可以省下不少力氣。而Android也是備受關注,參加聽講的人也最多,我想手機應用將很快成為主流。

Google Maps API部份主要是介紹如何使用API,以及有哪些功能。比較特別的應用是,地圖的重疊功能。比如有個展示是把高雄現代地圖與古地圖重疊在一起作比較,可以看出古今變化的樣貌。另外一個是Google Earth的介紹,這一部份讓人感到很驚豔。例如可以選擇台灣隨便一個地點看其地形,也可以模擬從台北101的角度俯瞰整個台北市的景觀。目前網站應用最多的大概就是屬於這一類,像台灣的地圖日記就是,還拿到美國demo秀的特別獎。可以說Google的開放式API造就了許多網站成功的機會,而這些開發者的反饋又增加了Google這一類服務的內容,相輔相成。因此當網路上各式各樣的資料越多,搜尋就越顯重要,而Google的競爭優勢也就越強大。

Android部份是由美國Google總部的軟體工程師所演說,大意是Android平台是架在Linux Kernel之上,類似Java Virtual Machine的功能。除此之外也提供像Windows API一樣的程式開發SDK,讓使用者可以更方便地開發手機上的網路應用程式。讓我感到比較印像深刻的部份是Q & A,演講者的電腦功力非常深厚。在面對各式各樣的問題時,不是只由軟體開發的角度去回答,而解決問題的方式也不只一種。聽完之後,我更加覺得各方面綜合能力對一個軟體開發人員在開發設計上是不可或缺的。

感到比較失望的部份是小工具主題,只是簡單照著投影片作解說,教大家怎樣建立一個Gadget,沒有看到什麼更進一步的消息或是未來發展。不過Gadget不是只能放在iGoogle上面,而是可以放在任何網站或是Blog上都可以。這部份讓我覺得其實Gadget也可以結合廣告的配置,而不一定要很死版的依賴Google Adword或是Google Adsense。廣義來說,幾乎可以內嵌的都可以看作是一種Gadget,YouTube也可以看成是一種視訊撥放的Gadget放在網站或網頁中。目前除了個人化入口網站之外,大量的Blog中也會放置Gadget。可以說,以往Web 1.0時代那種統一介面被Web 2.0時代的個人化定制介面所取代的關鑑就在於此。

總體來說,這一次參加的感覺是對Google目前各方面的服務多了一些認識。也體會到,其實在網頁應用的開發上最困難的部份可能是去了解眾多API的使用。也許,Google正在作的就是把眾多API的數量盡量精簡,到最後所有開發者都可以在同一個標準下去作開發,那分享與產生的速度相信就可能會更快了。

2008年5月19日

Automatic Identification of Pro and Con Reason in Online Reviews

Automatic Identification of Pro and Con Reason in Online Reviews 這篇論文主要出自於COLING' 06, 其目的是將線上評價中的語句辨識出是否有含主觀意見, 進而將含主觀意見的句子分成pros 和 cons 兩個類別.

因此, 給定一句使用者評論中的句子, 系統架構主要可以分為兩個階對進行, 分別為subjectivity identification and polarity classification phases:
--subjectivity identification 將關於具有主觀意見的句子辨識出來.
--polarity classification 將主觀意見的句子進行分類.
subjectivity identification和polarity classification均採用supervised machine learning algorithm (Maximum Entropy), 類別主要分為三種 (Neither, Pro and Con), neither類別可視為客觀的類別(即一般的事實描述), 其內容不屬於pros and cons. 而分類時所使用的特徵屬性可分為三大類別:
1. Lexical (uni-gram, bi-gram and tri-gram)
2. Position (該sentence是否出現在review中的首兩句或末兩句)
3. Opinion-bearing words (是先選定好的情緒字集)

此外, 為了簡化標準答案的標註, 本論文提出了一套自動標註系統, 主要係透過目前某些評論網站含有特定的欄位來描述pro和con. 作者假設, 使用者在撰寫評論的時亦會使用相同的字詞(包含在pro's和con's feild) 來描述他對於該產品的優缺點, 藉由此特性, 來建立所需的標準答案.

實驗部份: 透過epinions.com(含有pro and con field)來建立訓練資料, 並且將建立好的model除了應用在此網站之外, 同樣也在Compliant.com上進行實驗, 最後實驗結果顯示, 平均precision 可達66%, recall 可達到76%.

利用目前些評論網站均含有描述pro和con的欄位. 假設user撰寫的pro's and con's所使用的字詞, 也會出現在撰寫整體評論中來描述他對於該產品的優缺點, 我們即可以pro's and con's的資料做為參考答案, 藉由此來建立所需的training data.

附上此論文投影片:

2008年5月7日

Image Classification for Mobile Web Browsing

這次報告的paper題目是"Image Classification for Mobile Web Browsing",出處是"Proceedings of the 15th international conference on World Wide Web"。不難想像的是,作者是日本人,畢竟在日本,使用手機已經成為非常高頻率的一種活動。底下是摘要部份:

對於只有小畫面的行動裝置使用者來說,瀏覽專為桌上型PC的大畫面所設計的網頁是不方便的。然而,隨著網路技術的提升與行動裝置的普及,這方面的需求也越來越多。目前已經有一些研究與商業產品正嘗試解決這方面的問題,其中,能夠正確地分辨網頁中image的種類是很有用的。舉例來說,去除網頁中某些image來簡化網頁內容以達到更符合小畫面瀏覽的程度。

在這篇paper中,作者們將web imgaes分成11個種類。接著,從40個網站中收集到的3901個images以手動方式分類。其中,選取了能夠有效分類的37個image features。這些image features的擷取方式總共有4種:
1.use HTML source file analysis
2.query web servers
3.exploit the layout information of DOM trees when rendering the pages
4.use image processing

根據這37個image features,作者們使用C4.5演算法來建立Decision Tree Classification。

實驗部份,總共執行40次,每一次選擇其中一個網站的images當作test set而其餘39個網站的images當作training set。結果顯示,採用作者們的分類方式可以達到83.1%的正確率。最後,作者們還實作了一個automatic web page scrolling system作為展示利用image classification方法的一種應用。

最後是這次報告的投影片:

2008年3月2日

OpenXUP─an Alternative Approach to Developing Highly Interactive Web Applications

本篇paper出處是:"Proceedings of the 6th international conference on Web engineering",底下是摘要內容:

製作更豐富與高互動性的Web Application需求益發增加,目前改善傳統的HTML方式的介面表示方法主要有兩種:一種是利用下載程式到browser中執行的方式如Java Applet或ActiveX;一種是近來很流行的AJAX。但是這兩種方式都有其缺點,前者當UI與程式功能比較複雜時,需要下載的程式碼也變得較多,並且由於程式功能在Client端執行,因此存在有安全性的風險;後者的UI則受限於Browser的JavaScript Engine與DHTML的表現能力。因此作者們提出了另一種可選擇的方式─OpenXUP,一種基於XUP(Extensible User Interface Protocol)的Web User Interface Development Framework。

XUP 是一種基於SOAP的Protocol用來處理在web上的使用者介面事件溝通與更新的通知,而且支援非同步的訊息傳送。OpenXUP的組成有兩部份: thin client and server toolkit which offers a set of event-driven APIs。think Client(XUPClient)只有兩個任務:一個是顯示UI與捕捉UI Events;另一個是負責與server間的通訊(傳送與接收Events)。Server(XUPServer)部份負責處理從Client傳送過來的UI更新要求,裡面包含了Application Manager、Event Dispatcher與XUP applications。Application Manager用來選擇對應的XUP application作處理,Event Dispatcher則把Events分派給對應的Event Handler程式處理(在XUP application之中),而XUP application則是Server中程式邏輯的主要部份,利用一組Event-driven APIs來完成其功能。

OpenXUP 的特色在於程式功能的執行都在Server端完成,透過XUP將UI的更新結果傳到Client,然後由Client顯示更新後的UI畫面。由於程式功能都在Server端執行,因此Cleint端的環境是安全的,並且在除錯與維護上也較容易。另一方面由於Client端完全利用本地端電腦的GUI toolkit能力(目前以.NET實作)再加上XUP支援非同步的訊息傳送,使得在Client端的介面呈現上展現出了快速的UI反應與豐富高互動的 UI可用性。

最後是投影片內容:

2008年1月3日

Data Integration Support for Mashups. & A Framework for Rapid Integration of Presentation Components.

Data Integration Support for Mashups

這篇論文提出一個整合架構,讓使用者將現有的Services資料,透過作者提出的語法整合後轉為新的Service。作者以Online Citation Service為例,建構一個mashup,讓使用者輸入作者姓名,系統從DBLP得到和作者相關的論文,並且以這些論文資料去query Google Scholar,擷取論文的citation count。

作者定義了Query、Fuse、Aggregate、Union等函式,幫助Mashup開發者透過這些函式組合出新元件。而在Query Google Scholar時,作者也設計3個heuristic方式以增加最後結果的正確性。

A Framework for Rapid Integration of Presentation Components

這篇論文提出了一個application level integration架構,讓使用者能夠將現有的網路Services轉化成components,並將components組合成新的Service。

在架構上分成了Component Model、Runtime Middleware和Composition Model三塊。
  • Componenet Model中讓Mashup開發者設定Component的屬性、指令和執行事件。
  • Composition Model可以設定components間事件的呼叫方式,還有資料的傳遞及mapping,並且設定Services Layout Information。
  • Runtime Middleware是一個可擴充的架構,目的在克服相異Services間不同的執行環境可能會造成的整合困難。作者實作了.NET, ActiveX, AJAX等adapter協助component間的溝通。
兩篇論文皆提出了網路服務整合的架構,然而在實驗部分都較為欠缺,對於系統的適應力和實用性其實較缺乏說服力。

以下是兩篇論文的資料及報告投影片:

  1. Andres Thor, David Aumueller, Erhard Rahm. “Data Integration Support for Mashups.” IIWeb 2007
  2. Jin Yu, Boualem Benatallah, Regis Saint-Paul, Fabio Casati, Florian Daniel, Maristella Matera. “A Framework for Rapid Integration of Presentation Components.” WWW 2007

Mining Social Networks for Targeted Advertising

本篇paper的題目是"Mining Social Networks for Targeted Advertising",出處是:"Proceedings of the 39th Annual Hawaii International Conference on System Sciences (HICSS'06)"。以下是本篇paper的摘要內容:

在商業中,針對部份客戶作目標性的廣告推薦是很有用的。傳統上都是靠手動方式分析先前的歷史交易資料或是客戶的相關特徵,但是近年來隨著技術的進展,這部份已經開始利用自動化的工具來處理了。目前推薦系統產生目標廣告的技術主要有兩大類,一類是content-based,另一類則是social-based。前者主要是比對個人特徵與產品內容分類的匹配性,缺點是沒有利用到有影響力的其它人。後者則是利用客戶對產品的評等關係之間的關連來作推薦,但是對於沒有被評等過的新產品或是尚未有評等產品的新客戶來說,這種方法並沒有用處。

為了修正上面所提方法的缺失,因此本篇paper提出一種基於social network概念的data mining framework for targeted advertising system。這種方法的原理是利用social network中的概念─如果兩個不認識的人間有另一個共同彼此認識的人,那麼他們之間的連結程度比任意兩個不認識的人之間還要強的許多。以此為基礎,找出客戶關係網路中的cohesive subgroups。接著將產品作分類,然後計算每個產品類別在對應的subgroup中交易的次數作為整個subgroup對該產品類別的愛好程度。透過這種方式,找出在某個固定的客戶數量下最有可能購買某項產品的客戶群 。對於新客戶來說,廣告推薦是根據新客戶屬於哪一個subgroup而定;對於新產品而言,則是根據新產品屬於哪一個分類。

最後作者們以彰化師範大學的教職員email logs與library-circulation data作為資料針對以下四種方法來實驗:

1. Group-based, 本篇paper所提出的方法
2. Single-based,將每個人視為一個subgroup
3. Neighbor-based,將有直接關係的人視為一個subgroup
4. Random,隨機選擇

結果顯示本篇paper所提出的group-based方法的performance是最佳的,並且在數量100-300之間具有明顯的統計顯著性。

最後是這次報告的投影片內容:

A Framework for Rapid Integration of Presentation Components

本篇paper的題目是 A Framework for Rapid Integration of Presentation Components,出處是Proceedings of the 16th international conference on World Wide Web WWW 2007,底下是我所寫的摘要部份:

UI(User Inteface)的開發在軟體開發過程中是最費時的部份之一。尤其是在合成應用程式的軟體開發中,UI的可重複利用機制的需求變得越來越明顯。基於此,本篇paper的作者們提出了一個Presentation Integration Framework。透過這個Framework,可以讓開發人員利用現成的Web Application組合出一個新的混合程式,只需要提供適當的介面定義文件(以XPIL寫成)而不需撰寫Application間通訊的底層程式碼。開發人員使用XPIL定義Web Application中要參與互動的操作與觸發此互動的事件,然後再提供用XPIL寫的Composition文件檔來定義Application間溝通的設定,像是一個Application的某個操作要觸發哪些對應的Application的操作函式等。最後這些介面定義經由Runtime Middleware來作處理,把高階的語言介面轉換成底層的程式碼運作達到自動化互動的機制。這個Framework包含以下部份:

* Component Model
以抽象的方式描述Presentation Component的定義,包含了Events、Operations、Properties and Presentation Modes。
* Composition Model
a event-based model,其包含了Event Subscriptions、Data Mappings、Additional Integration Logic and Layout Information。
* Language Presentation
作者們提出的一個declarative composition language,稱為Extensible Presentation Integration Language(XPIL)。
用來描述Component Model和Composition Model。
* Runtime Middleware
用來整合presentation component,包含了Event Automation與Component Adapters and Wrappers兩部份。

最後作者們認為:由於這樣一個framework是基於抽象的與鬆散耦和(loose-coupling)的概念,因此適用於web application與desktop application。而且經由這個framework的幫助將使得軟體開發者可以更快速並且簡單地開發合成應用程式中關於UI互動方面的外觀整合部份。

最後是這次報告的投影片內容: