U-過程集中不等式及其在學習理論中的應用.pdf

1、偏序學習和排序學習在機器學習、信息檢索領域受到廣泛的關注，在統(tǒng)計學習理論的框架下，我們基于U一過程的理論，對偏序學習和排序學習進行推廣性的分析。
　　本文面向兩個緊密相連的研究領域：一是U一過程的最大值集中不等式，二是學習算法的推廣性能的界。
　　集中不等式描述一個隨機變量是否集中在某個數值(如數學期望)附近。在統(tǒng)計學習理論中，一個主要的數學工具就是集中不等式，經驗過程的集中不等式廣泛的應用在學習算法的收斂速率的研究中。而一

2、些學習問題又可以歸結到U一統(tǒng)計的表達形式。這樣促使我們研究U一過程最大值的集中不等式。U一過程與經驗過程緊既有區(qū)別又有聯系，這種緊密的聯系使我們自然地想到用來證明經驗過程的熵方法也能夠用來證明U一過程。區(qū)別是U一過程具有弱的相關結構，所以我們使用退耦的技巧來分解這種復雜的結構。
　　在本文中我們的主要貢獻和創(chuàng)新點如下：
　　首先，我們給出了三種類型的集中不等式：
　　·關于非退化核的集中不等式，
　　·關于退化核

3、的集中不等式，
　　·關于相關隨機變量的集中不等式。
　　前兩個是關于U一過程的，其實當我們把這種弱相關整體看成一個泛函時，這樣仍然可以當做獨立同分布的情形來證明，只是在證明過程中使用退耦不等式來分解這種非獨立的結構。在證明第一個不等式時，我們分成了兩步，先是證明非負核的U一過程的集中不等式，然后證明有界的核。我們使用非退化的不等式的研究了逐對損失的學習問題。第二個不等式的證明更復雜一些，我們證明的結果和經驗過程有相同的結構

4、。第三個是非獨立的隨機變量的泛函，可以看作是圖上的數據，每一個隨機變量是圖的頂點，我們借助于分數覆蓋的理論，把非獨立的隨機變量，分解成一些塊的和，而每一塊是獨立同分布的隨機變量之和，結合已有的結果和染色數的概念，我們就得到了非獨立的集中不等式。此外，我們還推廣了自有界函數的結構，定義了推廣的自有界函數，并且給出了一個集中不等式。
　　第二個是學習算法的推廣性能的界。集中不等式和統(tǒng)計學習緊密的相連，二階的U一過程是適用于逐對的損失的

5、學習問題。在本文中我們主要集中于偏序學習和排序學習，采用兩種分割假設空間的方法，一是基于相對風險的分割，二是基于方差的分割。
　　采用我們新證明的不等式，應用到逐點損失學習，不同于已有的文獻。在已有的結果中，作者采用了先把U一過程進行分解，然后分別用經驗過程理論和退化的U一過程來界定。而我們的方法是統(tǒng)一的進行處理，然后再分解然后分別用Rademacher。復雜度和Rademacher’chaos復雜度來界定。這樣做的好處是，對于基