《Boosting理論與算法的研究》是依託北京大學，由王立威擔任負責人的面上項目。
基本介紹
- 中文名：Boosting理論與算法的研究
- 項目負責人：王立威
- 項目類別：面上項目
- 依託單位：北京大學
項目摘要,結題摘要,
項目摘要
Boosting是模式識別、機器學習領域最重要的研究成果之一。雖然在算法方面取得了突出的效果，但關於boosting的兩個核心問題- - 1、Boosting為何具備優異的性能；2、Boosting為何會具有較強的抗過擬合能力- - 至今沒有令人滿意的理論解釋。本項目將研究並建立完整的理論體系以回答上述兩個核心問題，進而在理論指導下設計更高性能的全新boosting算法。計畫建立boosting分類器基於Emargin的泛化錯誤率上界、匹配下界、以及大樣本相合性。設計以最佳化Emargin為目標的boosting算法。此外，還預計將新算法套用到人臉檢測與識別系統。本項目預期在國際權威學術期刊、會議上發表論文8-10篇，並培養3-5名研究生。
結題摘要
Boosting是機器學習領域性能最好的算法之一，已經被廣泛用於多個套用領域。Boosting中最具代表性的算法是adaboost。該算法利用一個給定的基本分類算法，通過對訓練數據集相繼賦予不同的權重分布，學習出一系列基本分類器，而後將這些基本分類器組合起來作為最終的分類器。關於adaboost有兩個核心問題：1、為什麼adaboost會有如此優異的性能？ 2、實驗中觀察到adaboost在很多情況下不發生過擬和,這似乎與Occam剃刀原則完全相悖，理論上如何解釋？ 本項目針對上述兩個boosting基本問題進行了較為系統的理論研究。在Schapire, Breiman等人工作的基礎上，提出了Equilibrium margin理論。項目核心成果在於，我們證明了一個組合分類器的margin上界。該上界中的核心量是我們定義的一個新的概念，稱作Equilibrium-margin，簡稱Emargin。我們證明了Emargin理論一致優於Breiman的最小margin理論和Schapire的margin distribution理論。這一結果對margin理論的爭論給出了解釋。此外，我們根據Emargin理論，設計了新的boosting算法，取得了較好的效果。 在上述工作基礎上，我們對一般線性分類器的margin理論進行了深入的分析。由Vapnik等人給出的經典margin理論一直認為學習結果的泛化能力只與分類器的margin有關，與數據所在空間維數無關。我們證明了一個新的margin上界，該上界不僅與margin有關，而且與空間維數有關。我們同時證明，新的維數相關margin上界一致優於經典的維數無關上界。新結論說明泛化能力隨著空間維數增加變差，並非與維數無關。 此外我們還研究了主動學習理論、排序學習和基於學習的算法博弈論。並將以上理論和算法成果套用於計算機視覺領域的具體問題中，取得了較好的效果。 本項目在包括JMLR, NIPS, COLT, IJCAI等機器學習領域權威學術刊物、會議上發表高水平論文10篇。項目負責人在CCML2013做大會特邀報告。本項目還培養6名研究生。
