Answering Relationship Queries on the Web

這篇paper來自於WWW 2007，作者為三位IBM T.J Research Center的成員。在這篇paper中，作者想要探討，對於不同的entity(人、事、物)，如何透過網路搜尋引擎來找尋其中的關連性。現今的網路搜尋引擎對於keyword matching以及document ranking很擅長，但是如何去處理relationship queries，也就是找尋不同的keyword之間的關連性(ex:我們想要知道A與B兩人之間有無一些共同的特性)，卻沒有一套辦法，因此作者提出了這個新的議題，主要內容如下。

這篇論文希望從兩個不同的entity之間，透過網路搜尋引擎，擷取出一些相關的特性。因此作者
1.對兩個entity當作keyword，分別去擷取出一些有關於該entity的網頁(得到兩個網頁的集合)，
2.對兩個entity的網頁集合做前處理的動作。
3.從兩個entity所找出的兩個網頁集合中，各自取出一個網頁，做網頁比對(web page matching)，以找出它們之間的相似度(關聯性)，因此假如每個entity各擷取出五篇網頁的話，我們會有5*5=25個網頁比對的結果，網頁比對的目的，就在於希望從兩個網頁集合中，去找尋他們之間(A集合的網頁與B集合的網頁)是否有存在一些類似的關係(common term)，作者以Okapi formula為基礎，加以修正去計算common term的權重(權重高的common term稱為connecting term，表示連結敘述了兩個entity之間的某特定關係)以及每個web page pair的相似度(分數)，並且回傳前10高分(相似度)的web page pair，將connecting term與keyword做highlighting以方便使用者得知entities之間的關係描述。

實驗部份，作者展示了7個範例，分別來自於5種不同的scenario(人、地方、公司...之間)，像是用兩個人名當作entities，去找尋他們之間有無共通的關係(一起在哪裡工作過、專業領域...)。另外還證明了方法中用到的parameters，對於結果不會有獨斷的影響；以及論文中所提出的幾個方法，對於實驗結果各自的影響力，做一個比較性的小實驗。

WWW 2007: Answering Relationship Queiries on the Web

Compare&Contrast: Using the Web to Discover Comparable Cases for News Stories

這篇來自於WWW 2007的paper，主要的目的是，為了提供使用者一個能做範例比較與比對的機會，user給定一個news article後，paper裡面所建構的系統會至web search engine去找尋相關的news stories，這也是paper標題選擇的原因。

這篇paper所提出的系統，名稱即為Compare&Contrast，它所做的事情是，給定一篇news article作為input後，一開始我們對這篇article建構一個story model: 對此document做sentence splitting與named entity recognition。paper做named entity tagging的原因是，它想要找出article內主要談論的named entity，可能是人名、地名、組織名等等，此main entity表示了該篇news article所談論的最主要的entity，像是一篇"某國家要求獨立"的此篇新聞中，這個"某國家"就代表了這篇新聞的main entity。除了萃取出main entity之外，我們還想要找出generic situation keyword，這些situation keyword敘述了這篇news article的事件描述以及事件發生的背景原因，因此我們需要擷取出situation keyword，所以paper另外做了non-named entity recognition。

有了main entity與generic situation keyword，我們可以建構一個query到web search engine來尋找相關的news stories，在此paper中，對"相關"的news stories的定義為，有出現類似的generic situation keyword，但是不包含main entity。因此我們會找出有相似事件背景的story，但不會找到與original story相同公司(人物、組織、國家..)的article。

經由上述main entity與generic situation keyword兩者combine起來的query，去web search engine搜尋後，我們會找到一些可能相關的文章。對這些文章，paper使用自己定義的score計算與更改過的TF-IDF算法，去找尋comparable entity，也就是代表這篇"可能相關"文章的main entity，這也是我們主要想找尋的output。

當我們找到這些可能相關的文章與文章的main entity(以系統層面看，即為comparable entity)後，我們做了兩項實驗:
1. 經由觀察，作者發現並不是所有的news article都適合於找尋comparable case，因為有些文章所談論的too general，或是too specific，都不利於找尋comparable case。然而，有些新聞文章，在敘述完新聞內容後，後半段會附上跟此篇新聞內容的類似案件，因此我們可以利用這些新聞文章當作test case，並以其中所附的類似案件當作answer key，以此來判斷我們所找的comparable case是否與這些answer key相符。
2. 除了把找出來的comparable case與answer key相比，作者還想要知道user對這些output的真正看法是什麼。因此paper random找出了6個test case，並邀請5個人來衡量，針對這6個test case，所找出來的comparable case是否為正確的"相關"新聞文章。
WWW 2007 Compare&Contrast:Using the Web to Discover Comparable Cases for News Stories.

05/16 Ranking Objects by Exploiting Relationships:Computing Top-K over Aggregation

這篇paper是來自於SIGMOD 2006，主要是探討給定一些keyword query時，我們想要去某些document尋找相關的target object to match query，不過若是要進行完整的搜尋，事實上是很浪費時間且不切實際的，其實我們只需要找出最好的前k項就足夠了。因此，這篇paper就是以上述為目標，來進行如何計算object score與如何提升效能節省時間的early termination之研究。
在paper中主要分成下列幾點:
1.界定document與object，以及他們之間的關係。舉例來說，在expert finder的應用上，我們想要搜尋的document是paper，而我們想要找尋的target object，也就是user所要的答案，是paper的author。而我們會用一個table來記錄document與object之間的包含關係，也就是我們在某個document內發現哪些target object，這些紀錄有助於之後的分數計算。
2.接下來是System Overview。在這篇paper中，我們對於每個document搜尋符合keyword的方法，都是FTS(Full Text Search)。對於每個single keyword w，我們會得到一對應的ranked list，裡面包含了符合這keyword的document，並按照分數高低來排列。
3.作者提出了兩種scoring function，一個是row marginal class，另一個是column marginal class。Row marginal class是先對each document做所有的keyword分數之combine，再對combine後的分數作aggregation。而Column marginal class是先對each keyword做aggregation，再對所有的document分數做combination。在此篇paper中，我們用的是column marginal class。
4.接下來是此篇paper的重點，他們提出了一個early termination的觀念，也就是說當我們確定找出了最好的k個target object，而且之後所搜尋的object都不會比這k個更好的話，我們就可以停止搜尋並回傳結果了。其中又分為generate-prune approach and generate-only approach。generate-prune approach用的是先產生一size大於k的candidate set，再做pruning得到final k。而generate-only則是會不斷產生直到符合某stopping criterion為止。
最後實驗證明，使用early termination的generate-prune(GP)與generate-only(GO)的執行時間皆比原本的SQL好上幾倍，而GP比GO來得更好。因此，加入early termination的觀念能成功的縮短執行時間，而且回傳top K的結果，對使用者來說也算是足夠，畢竟使用者也不見得需要那麼多卻不一定相關的答案。
SIGMOD 2006 : Ranking Objects by Exploiting Relationships

<04/14> 建好了C4.5 decision tree

雖然說build a decision tree的規則很簡單，但是真正在算information gain、entropy等等的時候還是會有些一時無法理解。好不容易把全部搞懂，代入正確的數字，最後比較gain ratio的地方也正確了，建出來的tree跟第五章投影片的順序也一致，接下來就是要搞C4.5 rule的部份了，希望趕快把這個作業寫完囉。

<03/28>這兩三個禮拜

實作了K-means、Sammon's、Fuzzy-C-means演算法，以及SVM未知詞合併的計畫。程式一個接一個寫的過程中，不知不覺熟悉的速度就會愈來愈快，也就愈來愈上手。在寫程式的過程中，因為會碰到問題，因此查API變成了例行公式，漸漸的，有些觀念也應用的比較熟練了，像是 garbage collection，以前總是覺得不需要，但是隨著程式所牽扯的資料量愈來愈大，做gc反而變成了很重要的一回事。
在SVM未知詞合併的計畫裡，目前是用training data訓練SVM，而在training data裡標示為要合併的未知詞組合，像是(婦、唱、夫、隨)這四個"詞"被判定為要合併，但不會將它加進原有辭典中，因為只是讓SVM學會，碰到這種例子的時候，SVM要判定為合併，目的是讓SVM學習；不過現在老師說要將testing data判定為要合併的未知詞組合，要把它加進舊有的辭典裡去。
我有一個疑問，是否要將training data判定要合併的這些未知詞組合也要加到辭典裡，還是只是為了讓SVM學習，不加進去，讓SVM以後再次遇到時，自行判斷合併與否。
這個疑問的兩種解答會造成辭典裡的index不同，畢竟婦唱夫隨這四個字是分開的時候，在辭典裡分屬四個不同的位置，所以餵給SVM的資料也要存四個不同的index；若是在training的過程中將這四個字合併並加入辭典，則這個新詞(四字合起來)只會有一個index，SVM對待它的方式也會大有不同(只會看成一個attribute)。

Lazy Associative Classification

這篇paper主要是介紹了一個新的associative classification的作法。一般來說，associative classifier會比decision tree classifier的準確率要來得高。因為decision tree classifier 是用greedy(local) search的方法，選出目前擁有最高information gain的attribute，加進tree裡面形成新的split node，對於此node的子樹來說，皆為該attribute與其他所剩下的attribute中，挑選擁有最高information gain的attribute來繼續splitting，直到所有的instance屬於同一個class或是此node已低於某特定的minimum support threshold等等。decision tree classifier的特點是快速且容易明瞭，缺點為local search的情況下容易忽略了important rules。association rule classifier可以解決此問題，透過global search的方式，可以產生large number of rules。但是該優點正也是缺點所在，產生了大規模的rule set，許多的rule在分類的過程中甚至幾乎沒有用到，整體效率不彰。
因此本篇作者提出了lazy associative classification的觀念，相比於一般的 (eager) associative classification，lazy associative classifier並不是對於所有的 training data皆產生了rule set，而是demand-driven basis，也就是只針對testing instance所擁有的feature去產生association rules，如此可以保證所產生的association rules一定至少跟testing data有若干關係，不至於發生在測試的過程中，只用到少數association rules的情形。
對於lazy associative classification，為了一開始就記錄test instance所包含的feature set，會用到比一般associative classification更多的workload，此問題在paper中也提到了可以用caching的方式解決。另一個問題是只針對test instance產生的association rule，代表的就是要犧牲部分的generalization和影響classification若干的accuracy。
最後實驗證實，lazy association classification可以降低10%的error rate，相比於一般的association classification；而若是跟decision tree classification相比，更可以減少近20%的error rate。



Proceedings of the Sixth International Conference on Data Mining 2006 (IEEE)

研究計畫(SVM using in Chinese Unknown Word)

之前學期尚未結束時，計畫停頓了一下子。並不是完全停頓，但是進度很慢。直到寒假開始，才又開始趕工。
因為training data太過龐大，因此我一直是以subset來做測試，測試辭典的index、屬性，測試Phase2_training的資料是否有正確處理到，包括計算其sliding window所組成的未知詞之frequency，以及該sliding window未知詞之prefix、suffix結合的機率，還有該sliding window的條件機率( P(1/2.3.4) or P(4/1.2.3) ，0是prefix，5是suffix。<=此例子是sliding window4)。
這幾天我開始用全部的Phase2_training data來跑，才發現了嚴重的問題。程式碼的效率不彰，使得整個程式的物件宣告不是太集中，一下子吃掉了太多記憶體；就是太分散，以致於不知道什麼已經宣告過了... 這是自己經驗的問題，看來我還有得學了。所以最近把程式碼不斷的修過，加上讓java擁有更多的memory來跑，跑出來應該不是什麼問題了。
在testing的部份，我用學長的程式將testing的數十個document組合成一起。結果當掉了...我再問問看學長好了。等到組合好，就可以拿去讓LIBSVM predict了。
而LIBSVM的使用，基本的train、predict功能都不是問題，重點是它有些參數可以調，讓precision可以更高一點，這些參數要怎麼設定現在還是不太確定。看過有人寫的tutorial，他說最好的方法就是 "try!!!"... 是啦，good answer~
另外就是論文的部份，因為實在是沒什麼經驗，所以我想應該要先把想要寫什麼，給弄清楚。之後還要多看看別人的paper，看看別人是如何表達意見的，格式、用字等等，才可以。