從資料之海撈出冠軍杯(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科普推廣計畫」取得網路轉載授權)

(Visited 11 times, 1 visits today)

分享至
views