Neural Network 期末報告

曾義澄 D9915006

 

 

Outline

 

1.      Problem Understanding

2.      Feature Extraction

3.      Observation and Proposed Solution

4.      Experiments

5.      Conclusion

 

 

 

 


Problem Understanding

 

KDD Cup 2011的題目是有關於Yahoo! Music的,包括了2tracks

l  Track 1
給定一組項目資料 (項目資料可以是trackalbumartistgenre),預測使用者們會給這組資料的各個項目評定幾分。

l  Track 2
從一組歌曲資料中找出使用者們喜愛的歌曲。

資料集的項目數量非常的龐大,有超過100萬個使用者來進行評分。而有超過3億個使用者評分記錄,這些評分記錄有些是針對track、有些是對album、有些是對artist、有些是對genre來進行評分。而trackalbumartistgenre互相有階層關係,例如:某track是屬於某一album之中的,某album又是屬於某一artist或某一genre等。為了避免洩漏較隱密的資訊,每個usertrackalbumartistgenre都是以一個無實質意義的ID來代表。附帶一提,由於在此規劃中只針對Track 1來進行規劃,因此只說明關於Track 1的事項。

此外,在KDD Cup 2011的介紹網頁 [1] 中,還有提到一些頗值得提的事項:

l  跟其他的資料集相比,Yahoo! Music的資料相當的豐富,有超過3億個使用者評分記錄,又有超過60萬個項目可當作評分標的 (意即:trackalbumartistgenre),其他的資料集通常只有使用者的數量很大而項目卻不多,此為特點之一。

l  每個項目之間都有階層關係,意即trackalbumartistgenre互相有階層關係,以下面簡圖略做說明。可以看到的是每一個track都屬於某一album,而每一個album都屬於某一個或多個artist,且每一個album又可屬於一個或多個genre。而使用者且可對trackalbumartistgenre進行評分。

NN1.png

而訓練資料集分為3個檔案,分別為Train dataValidation dataTest data。每個檔案的資料都遵照著以下格式:

<UsedId>|<#UserRatings>\n

<#UserRatings>\n後會接一組或數組<ItemId>\t<Date>\t<Time>\n,會有多少組全看<#UserRatings>是多少。上述之格式用以表示此使用者做了幾個評分,在何時間點分別對何項目評分、評了多少分。例如,用以下格式來表示使用者編號1評了2個評分,在某時間點過了4天的05:06:073號項目評分且在某時間點過了9天的10:11:128號項目評分。

1|2\n3\t4\t05:06:07\n8\t9\t10:11:12\n

使用者評的分數是介於0100的整數。所有的使用者ID及各項目的ID都是連續的且唯一的整數,且都是從0開始起算。

而有關於trackalbumartistgenre的資料則分別存於trackDataalbumDataartistDatagenreData (所有的Missing value都標記成None)。格式分別為:

l  trackData
<TrackId>|<AlbumId>|<ArtistId>|<Optional GenreId_1>
<Optional GenreId_k>\n

l  albumData
<AlbumId>|<ArtistId>|<Optional GenreId_1>
<Optional GenreId_k>\n

l  artistData
<ArtistId>\n

l  genreData
<GenreId>\n

Train dataValidation dataTest data這三個檔案中,每個被評分的item都有至少20個使用者評分記錄。在Train data中,每個使用者至少都有10個以上的評分記錄 (不管項目為何)。在Validation data中,每個使用者就只有4個評分記錄。而在Test data中,每個使用者至少都有6個以上的評分記錄。下表整理了Track 1的資料集中的各項統計數值。

#Users

#Items

#Ratings

#TrainRatings

#ValidRatings

#TestRatings

1,000,990

624,961

262,810,175

252,800,275

4,003,960

6,005,940

評估預測正確程度的方式為Root Mean Squared Error (RMSE)。值得一提的是,Test data將會被分割為2個評分記錄數量相等的部分,分別計算這2個部分的RMSE,將其中一個的RMSE結果公佈在Leaderboard上,讓每個競賽者都能得知。而另一個RMSE的結果將會用來決定誰是最後的冠軍,也就是說在Leaderboard上是冠軍的不一定是最後的冠軍,而在Leaderboard上不是冠軍的也不一定不是最後的冠軍。


 

Feature Extraction

 

本次競賽的最大困難點,如同台灣大學團隊在KDD Cup 2010做的主要工作,應該是Feature Extraction。有句名言「Garbage In Garbage Out」,只要輸入的資料品質不佳,那麼,就算分類器(Classifier)擁有頂尖的分類效果也是罔然。因此,只要特徵擷取的工作做得好,所使用的分類器就相對地不是那麼至關重要。較為簡單且直覺的作法應該是把各item全部攤開來看,並把Train data轉換成sparse matrix,套用到Track 1上,就會變成以下所示:

圖片15.png

若該user有評過某item的分數時,則會在該item對應的位置填上該user給的分數。而datetime分別利用不同的表格記錄下來,如以下所示:

圖片16.png

圖片17.png

舉例來說,現有User0User1User2User3分別對Item0Item1Item2Item3的評分資料:

圖片21.png

User0Item0Item2Item4分別評了7050100分,其餘的依此類推。如前所述,如果採用full matrix存下的話將會佔用記憶體約

#user * #item * 4 bytes * 3 / 10243 = 6991.5 GB

很明顯地,以目前的環境根本無法達到,較為合理的作法是將其存成sparse matrix,如此一來使用的記憶體空間會將降成約

#rating * 4 bytes * 3 / 10243 = 2.937 GB

在計算過程中,應該會有許多需重複利用的資訊,因此將準備額外的記憶體空間來存下所有計算過的資訊,以加速之後的計算。

另一方面,對於各item之間的階層關係的處理方式,在此是利用Adjacency Matrix來表示各item之間的關係。由資料集我們可知某一track必定屬於某一album;某一album必定屬於某一artist;某一track可屬於某些genre;某一album可屬於某些genre,且某一album包含的某些trackgenre與該albumgenre並不一定相同;某一artist可屬於某些genre。因此採用2個不同的Adjacency Matrix來記錄各item之階層關係,如下所示:

圖片19.png

圖片18.png

舉例來說,現有Track0Track1Track2Track3分別對其他Item0Item1Item2Item3Item4Item5的階層關係:

圖片20.png

Track0分別屬於Item0Item1Item4,而Track1則是屬於Item0Item3Item4Item5


 

Observation and Proposed Solution

 

進一步觀察Track 1的資料集,可從資料內容發現其影響因素大概有以下幾項 (可能還有)

Label Instance

Unlabel Instance

No Rating's Item

Rating Time

Relation Between Items

The Number of the Models

以下將分別說明各項因素的考量。

 

l  Label Instance

假設有User0User1User2User3分別對Item0Item1Item2Item3的評分資料,且欲預測User0對於Item1所給予的評分:

圖片22.png

Test data中的User想要PredictItemTrain data中有沒有被其他User評過分數。如果有的話,則該User的評分行為將會被納入考量,如果沒有的話,我們將進行其他處理。則對於此資料,Item1就相當於是此次PredictLabel,其餘Items則是作為Train dataFeatures,並以此來進行訓練與學習,以圖示說明如下:

圖片24.png

基於此觀點,我們可用來預測的方法大致有以下幾種:

n  直接平均所有評過此ItemUser之分數。但這依然是屬於較為單純的作法,因為它是假設各Item間彼此獨立且各User間彼此獨立,我們可想像此作法大概不會有很好的預測效果。

n  套用k Nearest Neighbor [2]的概念,計算User0Train data其他的User的相似程度,挑選山與之最近的k個鄰居並進行這k個鄰居分數的投票(Prediction來說便是平均),但此法有個參數k需要進行Tuning,但k的大小又與資料集的分佈很有關係,因此k的值對於預測的效果可能會有很大的影響。

n  k Nearest Neighbor進階一點的概念為Weighted k Nearest Neighbor [2]。其目的是想要讓Distance越小(Similarity越大)的資料對於預測的影響力越高,Distance越大(Similarity越小)則影響力越低。

n  又或者,我們可利用Support Vector Machine來進行TrainingPrediction,其概念可說是更廣泛的Weighted k Nearest Neighbor,所有的Training Instances都具有一定的影響力,Model的第iComponent決定了第iInstance對於預測的影響力(以處以Dual Form為例)。其中台灣大學林智仁教授所開發出來的LIBSVM [3]LIBLINEAR [4],這兩個軟體皆為免費軟體 (但有使用的情形,必須在參考列表中引用該論文),且非常容易使用,對於初學者的使用門檻應是不高。值得注意的是,LIBLINEAR只能做線性的分類與預測,不能做非線性的工作。林教授主要的理由是:因為在大多數的情況下,線性的分類器的效能就已經夠好了,沒有太大的必要花費數倍以上的時間去提升少量分類與預測的效能。

 

n  基於類似Weighted k Nearest Neighbor的概念,我們可以將其Similarity的結果進行由大到小(或是Distance由小到大)Sorting並給予各筆資料不同的權重,然後進行Linear Regression [5]Nonlinear Regression [5],將其計算結果取出Bias值,以此來做為我們預測的分數 (因為自己跟自己的distance0,代入Regression Model時就是Bias的值)。如下圖所示,y截距便是我們對於該item預測的分數。順帶一提,因為我們給後面資料的權重是越來越小的,因此該linear regression對於後面資料的fitting可能會不太佳,但這正是我們想要的:distance越大的資料我們雖然較為不看重,但我們也不是全然丟棄它們帶有的資訊。

`.png

n  套用Online Learning Algorithms,例如:Stochastic Gradient Descent (SGD)Passive and Aggressive Algorithm (PA)Passive and Aggressive Algorithm with Class Means Information (PAm)等。KDD Cup 2011所提供的sample code就是利用SGD的概念去建立Model的。使用Online Learning 相關演算法,傳統上,機器學習和資料探勘的演算法大多都以Batch Learning為主,但近十年來,為了處理Large-scale資料集的問題,有不同的學習演算法被開發出來,例如Incremental LearningOnline Learning演算法,而Incremental Learning類型的演算法已有相當的發展,它主要強調的是逐步地增加資料量並把現有的Model快速地更新至最佳Model,例如:現已有10000筆資料的最佳Model,如今新進100筆資料,Batch Learning的作法是利用Re-train來得到10100筆資料的最佳Model,但Incremental Learning類型的演算法卻可以直接從10000筆資料的最佳Model直接更新至10100筆資料的最佳Model,計算量與Re-train相比是少非常多的。但 Online Learning不同於Incremental LearningOnline Learning主要強調的是,它一次只參考一筆或少量資料來進行Model的更新。可想而知,Online Learning的計算量是相當地少,且能夠在很短的時間就得知可接受的解。但此種類型的演算法大部分都有隨機性 (Randomness) 的成分存在,並不能保證計算出的結果是效能最好的Model,也不能保證每次計算出來的解都會是一樣的。因此,此種類型的演算法大多是以Stochastic Method來證明其收斂性。儘管Online Learning演算法可能無法保證獲得最佳的Model,但我們可以將其Model當作是Batch Learning演算法的初始解 (Initial Solution),如此一來便可大大地減少Batch Learning的計算量。

l  Unlabel Instance

值得一提的是,半監督式學習(Semi-Supervised Learning) 也許可應用在此資料集上,由上面的敘述可知,若是沒有Label的資料,目前作法是用「各Item間的關聯」來處理。Label意味著該Instance對該Item的預測是否有幫助。但是沒有LabelInstance通常也是能夠幫助預測的。

圖片26.png

以此資料集為例,User0評了Item0 70分、Item2 50分、Item4 100分,User1評了Item0 70分、Item1 60分、Item2 50分、Item3 80分、Item4 100分,但User3評了Item0 70分、Item2 50分、Item3 80分、Item4 100分。現在要預測User0對於Item 1的分數,則User3的資訊其實是非常有用的,例如,藉由User1User3我們大致可知道User0對於Item3的分數大概也會是80分左右,如此一來便加強了User0對於Item1分數預測為60分的信心。關於這點,也許可以參考相關技術及演算法,例如:SVMlight2T1S等演算法。下圖為Label InstanceUnlabel Instance的概念表示圖:

其中,黃色三角形表示Unlabel Instance在空間的分佈,通常Unlabel Instance所提供的資訊為Spatial Information

l  No Rating's Item

圖片25.png

Train data中,User只對某些Item評了分,但還有很多Item沒有評分因而無資料記錄。對於此種情形,我們有以下幾種處理方法:

n  0代替,雖然這樣處理在意義上不一定是正確的,因為評了0分與沒有評分的意義是不一樣的。但因為它是最簡單的處理方式,其效果立即見分曉,因此先採用此方法來進行測試。

n  忽略,這也是最簡單、立即見效的方法之一,但這樣也許會遺失許多針對這個User的個人資訊,因為每個User評分的項目可能跟使用者的興趣有關,也就是說跟使用行為有關,沒評分的資料我們也應該做為一種資訊。

n  套用在Data Mining [2] 課程中學的Missing Value處理技術,例如:直接將有對該Item評分的User之分數平均,或取其出現頻率最高的分數,或是Weighted Average該分數。

對於該User沒有評分之Item的處理方法,我認為這是個很值得探討的方向,如何盡量補齊資料,但又不能破壞掉資料的整體分佈。

l  Rating Time

上述作法中,全然沒有考慮到時間的因素,但我認為「時間」的因素可能包含以下幾種可能:

n  The date of rating,可能與歌曲的流行趨勢有關。

n  The time of rating,可能與User早、中、晚的情緒有關。

n  Rating order,這又包含了「同類Item評分的順序」及「不同類Item評分的順序」,我猜想這可能與User的行為習慣有關。

對於Rating Time的分割及權重分配,便有以下幾種作法:

n  直接將DateTime分別進行平均切割,並平均其計算出來的分數。我們有理由相信在一段時間內,User的評分行為應該是類似的。

n  若不想把在一段時間內的行為進行權重相同的平均,則會採用Sliding Window的方式來進行加權分均。

n  值得注意一點的是,在Test data中每個要PredictItem也有時間資訊,因此如何找到時間對於預測分數的影響,這可能也是關鍵之一。針對各項Item的評分,我想要藉由Train data來進行各時間的權重預測,也就是說:在Train data中找到能使預測效果最好的權重,且它是會隨時間而改變。較為直覺的方法是套用Sequential Learning Algorithms,例如: Hidden Markov Model (HMM)Maximum Entropy Markov Model (MEMM)Conditional Random Field (CRF)等演算法。

l  Relation Between Items

由於之前提到各item之間是有階層關係的,其關係如下圖所示:

NN1.png

看到此圖,我直覺是想到用Graphical Model [6]來描述各item間階層關係。但由於此圖太過精確與複雜,計算上可能會因為變數過多,各變數的因果關係複雜而導致計算的時間複雜度與空間複雜度過高,且計算出來的結果也不一定會有較好的預測效果 (generalization ability可能不佳),實務上並不會這麼做。因此將此圖簡化如下:

`.png

如此,便可大為簡化其計算量及空間使用量,至於實際上是否可以使用,目前尚無驗證,畢竟Graphical Model是第一直覺想到的方法。

較為簡單的作法是單純的將各Item的階層關係進行分數的加權平均。例如:若某User給了某Album很高的分數,則對於屬於該Album裡的某Track應該也會很高 (吧?),或者是若某User給了某Track很高的分數,則對於該Track屬於的Album應該也會很高 (吧?)。這種順序關係其實是不一定具有交換性的。如上所述,也許可利用Associative Rule [2,7]的相關演算法來找出較為明顯的Rules以幫助預測,例如:有10%User給某Album評了高分之後也對某Track評了高分…等之類的規則。如此一來,便能Model對於某Item之分數的預測。

l  The Number of the Models

若採用上述作法,則將會有另一問題需探討,那便是「要Train多少個Model?」極端的三個情形:第一,針對每個User建立不同的Model (#UsersModel)。第二,針對每個Item建立不同的Model (#ItemsModel)。第三,只建立一個Model。第三種情形的例子便是KDD Cup 2011所提供的Sample Code,它用的ModelAvg_Total + Bias(User) + Bias(Item) = Predict_Score

建立#Users#ItemsModel在實務上可能較不會採用 (雖然可以暴力法完成實作),較為折衷的辦法為建立數個不同的User Clustering,並給予這些User Clustering不同的權重來進行TrainingPrediction。以下圖表示其概念:

Clustering包含的Instances越多,則該Clustering的重要性越大,如此一來便能解決建立的Model數量過多的問題。

比較值得一提的是,為了提升分類或預測的準確性,Ensemble Learning會是個很不錯的選擇。它主要的想法是結合相同類型的分類器 (或不同類型的分類器) 來進行該資料的分類或預測,好處就如同龍華科技大學的王榮英副教授所說的,大多數的分類器對不同的資料類型都有其判斷特別準確的部分。因此,可用多種不同的學習演算法來進行學習,最後在進行各分類器的投票 (Vote) 或分類預測結果的加權平均。Ensemble learning較為常見的演算法有:Bagging [8]Boosting [9,10]Adaboost [11]等。


 

Experiments

在此,實作的方法為只利用Label Instance來進行Regression的模型建立,Regression模型的建立是採用LIBSVM,且尚未將Items間的關係考慮進來。由於訓練時間上的考量,因此只用了Validation set的資料來當做Training set (若採用全部Training set的資料來進行訓練與學習,不知道要花上幾天幾夜…),初步的成果如下圖所示:

若全部猜80分的話,則RMSE34.9548。因此33.0116的結果不算好,其主要原因大概有以下幾項:

l  其一,因為只用了評分資料過少的Validation set來進行Training。想要用少量的資料來達到較好的結果,一般來說是比較困難的…

l  其二,對於User未評分的Item是用0來代表,其缺點就如同上述內容,意義上是不太正確的。

l  其三,並未考慮每個Item間的階層關係,而是假設各Item間彼此獨立。

l  其四,並未考處每個ItemRating時間與順序。其影響如上述內容,可能此因素也是具有一定影響力的。


 

Conclusion

思考KDD Cup 2011題目的這段時間,我覺得實務上的技術真的挺重要的,實務的技術決定了方法的可行性,好的處理方法和不好的處理方法,所花費的時間將是天差地遠,例如檔案的讀寫、計算的順序…等。對於KDD Cup 2011的資料集,我認為是個滿有挑戰性的研究,但受限於實作能力,不能在較短的時間測試各種不同的方法,且近期的事務較多,不能專心地進行此競賽的研究,這是較為可惜之處。但我覺得這事如果幹得好,應該可套用多種不同的方法來進行效能的評估,例如:Online/Batch LearningClusteringSimilarityFrequent PatternGraphical ModelDimension Reduction另外一件重要的收獲是如何藉由「題目」來得知此次競賽最主要的目的是什麼,如同老師在課堂上跟我們提到的「思考人們要的是什麼」,這往往也提供了我們解決問題的方向。我想這件事情便是我這段時間最主要的收獲。

 

Reference

[1]  KDD Cup 2011 webpage http://kddcup.yahoo.com/

[2]  J. Han and M. Kamber. Data Mining: Concepts and Techniuqes. Morgan Kaufmann Publishers, San Francisco, CA, 2001.

[3]  Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm

[4]  R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification Journal of Machine Learning Research 9(2008), 1871-1874.

[5]  ALPAYDIN, E. 2004. Introduction to Machine Learning. MIT Press, Cambridge, MA.

[6]  D. Edwards. Introduction to graphical modelling. Springer, 2000. 2nd edition.

[7]  R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Inkeri Verkamo. Fast discovery of association rules. In U. Fayyad and et al, editors, Advances in Knowledge Discovery and Data Mining, pages 307328. AAAIPress, Menlo Park, CA, 1996.

[8]  Leo Breiman. Bagging predictors. Technical Report 421, Department of Statistics, Universityof California at Berkeley, 1994.

[9]  Harris Drucker, Corinna Cortes, L. D. Jackel, Yann LeCun, and Vladimir Vapnik. Boostingand other ensemble methods. Neural Computation, 6(6):12891301, 1994.

[10]             Harris Drucker, Robert Schapire, and Patrice Simard. Boosting performance in neural networks. International Journal of Pattern Recognition and Artificial Intelligence, 7(4):705719, 1993.

[11]             M. Collins, R.E. Schapire, and Y. Singer. Logistic Regression, AdaBoost and Bregman distances. Machine Learning, 48(1-3):253285, 2002. Special Issue on New Methods for Model Selection and Model Combination.