顯示具有 information extraction 標籤的文章。 顯示所有文章
顯示具有 information extraction 標籤的文章。 顯示所有文章

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年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年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年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年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

2007年8月9日

Homepage live: automatic block tracing for web personalization

這篇論文觀察到personal homepage的趨勢,包括Microsoft和Google都有做personal homepage,並在homepage中讓人放置許多功能區塊。因此論文提出一個系統Homapge Live,可以讓使用者在這個網頁上建立個人首頁,並且加入小區塊。Homepage live的小區塊特色是可以讓使用者作網頁中的block tracing,也就是網頁區塊的monitering。這篇論文重點在於系統在目標網頁版本更新後,如何正確地抓取使用者所想看到的區塊。

首先將原網頁P_old和新網頁P_new表示成DOM Tree然後執行以下步驟:
  1. 找出Fix Nodes:Fix Node代表在P_old及P_new中內容重複的node。
  2. 產生Reduced Tree:刪除掉P_old及P_new中的Fix Nodes。
  3. Mapping:此時P_old和P_new都已經成為reduced tree,將P_old和P_new作tree mapping,找出P_new中對應到的目標區塊。
Tree Mapping作者用Minimum Edit Distance Mapping來作,找出P_new中對應到P_old中使用者選取的區塊。

實驗的部分作者測試系統的accuracy和effectiveness,和Direct Path Finding(DPF)、Tag String Matching(TSM)、Tree Edit Distance(TED)三個方法比較。在accuracy部分證明系統可以超過DPF和TSM,並和TED達到一樣的效果; 在effectiveness部分證明系統時間複雜度遠低於TED,並且證明了系統的scalability。

出處:Proceedings of the 16th international conference on World Wide Web (WWW2007)


2007年7月2日

Supporting end-users in the creation of dependable web clips

當使用者利用 Microsoft FrontPage 等Web Authoring Tools建立自己的網頁時,常希望加入可以對網路資訊作monitoring的小區塊,例如擷取天氣預報、新聞…等等,將個人資料作information integration。有些網站有自行提供API或Mashup等工具讓使用者做資料擷取,但許多網站沒有相關工具。

Web Clip: 作者定義為end-user在自行製作網頁時,
能夠即時擷取網頁資訊並顯示在網頁上的小區塊。一個Web Clip會針對某目標網站中的資料作monitoring,多個web clips可以整合到單一個人網頁。這篇論文提出Web Clipper,一個圖形化介面的Web Clip製作流程,讓使用者在 Microsoft Frontpage 中透過簡單操作就可以快速產生Web Clip並加入個人網頁中,並強調使用者不需要自行撰寫任何程式就可以完成工作。

Web Clipper主要分為四個部分:
1) Clipping
讓使用者選擇目標網頁中的區塊,記錄該區塊的HTML-Path。
2) Training 一個semi-supervised方法,為了提高區塊擷取的正確率,作者定義了數個Extraction Patterns,提供介面讓使用者選取哪些是Valid Patterns。
3) Deployment
記錄先前兩步驟的資訊並自動產生Web Clip的Ajax Script程式碼,同時在對2)中選取的Valid Patterns產生對應Filters,Filters用於評估Clip效果。
4) Filtering & Assessment 當發佈的Web Clip每次擷取資訊時,根據3)中建立的filters和2)中的patterns來計算confindence score,用來決定利用那個Filter擷取資料及檢驗Clip的Robustness。

實驗部分作者針對Web Clip的擷取效果,以及目標網站隨時間改變內容後系統正確擷取資訊的程度作評估,同時設計實驗來評估不同類型網頁區塊變化對資料擷取的影響(如block insertion, movement, deletion...等)。


出處:Proceedings of the 16th international conference on World Wide Web (WWW2007)



2007年6月4日

Interactive Wrapper Generation with Minimal User Effort

這篇論文出自WWW 2006,目標是提出一個半自動化的wrapper generation方法。

不同於其他semi-automatic和unsupervised wrapper,這篇論文並沒有很困難的方法,主要是提供一個使用者介面利用minimal user effort來完成wrapper工作。內容可以區分為兩個部分:
  • Interactive User Interface:只需少量的training pages,讓使用者highlight頁面中的tuples,然後系統根據使用者highlight的部分做處理,將文件轉為DOM parse tree。
  • Wrapper Generation System:系統定義了自己的Extraciton Language predicates,來作為產生extraction patterns的工具。
  1. 首先透過training tuple產生dom_path和最低層的共同節點LCA(lowest common ancestor),LCA object記錄了兩項資訊:
    1. training page中tuple的lca nodes。
    2. 萃取出這些lca nodes的patterns。
  2. 利用LCA objects產生patterns, 然後萃取出tuple attributes。
  3. 利用patterns去找出tuple region,產生初始的wrapper。
  4. 利用predicates產生tuple validation rules,並產生新的wrapper。
  5. 利用category utility function對wrapper做ranking。
    C: cluster, A: attribute, v: value
    同一群的兩個物件我們希望有較多相同的屬性,因此P(A=v|C)期望越大越好。
    不同群的兩的物件我們希望有較少相同的屬性,因此P(C|A=v)期望越小越好。
    因此CU值越大越好。
  6. 由使用者做確認。
  7. 將產生的wrapper使用一些verification set測試。
論文中提到雖然他們的方法和其他方法比較,可能需要較多的人力介入,且training examples較多,但是相信可以減少所需要的time和effort。實驗部分和WIEN, STALKER, WL^2等wrapper比較,都可以發現所需的training tuples較少,並且做了14個網站的wrapper實驗,在total user effort的部分表現也都不錯。




Proceedings of the 15th international conference on World Wide Web