從資料之海撈出冠軍杯(2/2)

從資料之海撈出冠軍杯(2/2)
撰文／林軒田｜轉載自《科學人》2012年11月第129期

在緊張刺激的資料探勘比賽中，且看資訊專家如何運用適當的策略與演算法，逐步提升預測模型的準確度。

(續前文)

擬定策略

2011年的資料探勘杯其實和〈會思考的電腦〉文中所提到的Netflix百萬獎金大賽十分相似。和該比賽比起來，2011年的資料探勘杯具有「資料量更大」（2.6億筆，相對於Netflix的1億筆）及「額外資訊更多」兩項特點。其中所謂的「額外資訊」，是指主辦單位提供了歌曲的作者、專輯、類型等相關資訊，希望預測系統能善加利用。大量的資料及額外資訊，讓參賽者很難設計有效率的系統來充份運用所有的資料和資訊，就像教材太多，學生很難有效率地讀完一樣。這些特點，讓2011年的資料探勘杯比起Netflix百萬大賽更為複雜而困難。

在Netflix百萬大賽裡一個重要的系統設計方向，就像阿布–莫斯塔法的文章中所提到的奇異值分解法（singular value decomposition）一樣，是希望能有效率地計算出使用者及歌曲的特性。舉例來說，如果系統知道，李四喜歡充滿童趣的歌曲，而「快樂天堂」是首充滿童趣的歌曲，那麼系統可能可以推論：李四會喜歡「快樂天堂」這首歌。這裡的是否充滿童趣，就是歌曲的一項特性。「快樂天堂」在這項特性上可能分數很高，而「陸軍軍歌」可能分數不高。每個使用者喜不喜歡童趣，則是該使用者的特性，李四可能這項特性值很高，王五可能這項特性值不高。把許多不同的特性從大量資料以及額外資訊中萃取出來後，想預測李四對「快樂天堂」的喜好時，只要把這些特性的符合度加總起來就可以了。

Netflix百萬大賽中，領先群的團隊開發出許多方法，可以自動從資料中萃取出這些特性，而在2011年資料探勘杯裡，台灣大學的團隊總共使用了五大類的方法來分析資料並做出預測，分別是芳鄰法、矩陣因式分解（matrix factorization，包括奇異值分解法）、限制型波茲曼機（restricted Boltzmann machine，這是一種基於類神經網絡的特性萃取法）、機率式潛在語意分析（probabilistic latent semantic analysis，一種基於機率模型的特性萃取法）、監督式迴歸分析（supervised regression，可以看成是傳統統計學中線性迴歸法的延伸）。

在這五大類方法中，表現最好的單一方法是矩陣因式分解，它所預測出來的分數和實際分數的均方根誤差是22.9022，也就是說，如果這個方法預測你對某首歌的喜好度是70分的話，你實際的喜好度大概會落在47~93分之間。這樣的誤差看似很大，在這個比賽中，卻已經是很不容易的成績。最後台灣大學拿到第一名的解法，均方根誤差是21.0147。從22.9022進步到21.0147的背後，是數個月的努力以及許多先進的機器學習技巧。

台大團隊由林智仁教授、林守德教授和我、三位助教及19位學生組成。25名師生對於這種「協同篩選」的問題，在一開始其實都是新手；相反地，許多參加過Netflix百萬大賽的隊伍，經驗都豐富得多。比賽雖然3月15日才開始，台大的團隊從前一年的11月就開始招兵買馬，並在11月30日正式成軍，利用上學期的學期末及寒假的時間，大量閱讀相關文獻以進入狀況。並由三位指導老師在下學期開設「機器學習的理論與實務」的課程，做為參加這項比賽的平台。

堅持到底，絕不放棄

比賽在3月15日開始，當時台大團隊首先努力實作並嘗試Netflix百萬大賽中已經使用的各式方法，勉強向前追趕。在第一次團隊上傳的時候，結果連前20名都排不上。而當時一路領先的隊伍叫做Commendo，其實就是Netflix百萬大賽冠軍隊伍的部份成員。但我們並不氣餒，我們把團隊分為六個小組，小組之間透過課程內互相討論與良性競爭，分頭去研究不同的方法。每週三小時的課程討論中，六個小組會報告當週的成果，供老師、助教及同學討論，團隊每週也會訂定下週的完成事項及目標。下課後，同學們要花上數十小時去研究新的方法並調整、撰寫程式，並且及早把程式放到電腦上去分析資料。因為這個比賽的資料量實在太大，往往程式一開始執行，要花三、四天才跑得出結果，同學們必須非常小心，隨時注意程式執行的狀況。如果運氣不好程式有錯或者電腦跳電，很可能跑了幾天的結果都白費了。

靠著分組的策略及所有成員的努力，讓台大團隊在廣度上取得了優勢。在比賽的中期，台大團隊靠著廣泛嘗試這五大類方法並加以改善，穩定維持在前五名，卻似乎難以超越Commendo一枝獨秀的氣勢。

這樣的情況在比賽的最後兩週開始改變，當時台大團隊已經嘗試過上百種不同的預測系統模型。最後的衝刺時刻，團隊成員把重點放在讓這些眾多系統模型截長補短。團隊的成員開發了一個方法，能夠知道各個不同的系統在什麼狀況下比較準確，例如甲系統可能對抒情類歌曲預測得比較準，乙系統可能對高使用量的使用者預測得比較準。最後團隊成員嘗試把這些不同系統組合在一起，測試資料中看到有抒情類歌曲，就使用甲系統；碰到高使用量的使用者，就使用乙系統。這種組合式的系統模型是台大團隊的強項，比起單一系統來看，組合式系統把精確度提升了7%，這個差距在比賽中是非常顯著的。

除了組合式的系統外，團隊還使用了平均式的系統模型（也是在Netflix比賽中普遍使用的方法）。這種模型的優點，是好像民主投票一樣，找出眾多系統的共識，來做穩健的預測。平均式的系統把精確度再提升了1.5%，就靠著這1.5%的差距，台大團隊在比賽的最後幾個小時一舉超越了Commendo這個先前的世界冠軍隊伍，拿下了2011年資料探勘杯（第一項子比賽）的世界冠軍。

這一屆比賽中，台大團隊同時拿下了第二項子比賽的冠軍（Commendo則屈居季軍），主辦單位在大會頒獎典禮上還特別盛讚台大團隊優異表現，包括連續四年獲獎及難得的雙料冠軍紀錄。在現今無所不在的資料之海裡，台大團隊撈出的不但是世界冠軍的榮譽，更重要的是比賽過程中所獲得的寶貴實務經驗，希望能培養同學繼續成為領航資料探勘的船長，持續開發資料探勘及機器學習的新技術，來解決未來更新、更大量、更複雜的資料探勘問題。(完)

(本文由教育部補助「AI報報─AI科普推廣計畫」取得網路轉載授權)