U-過程集中不等式及其在學(xué)習(xí)理論中的應(yīng)用.pdf

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

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

3、的集中不等式，
　　·關(guān)于相關(guān)隨機(jī)變量的集中不等式。
　　前兩個(gè)是關(guān)于U一過程的，其實(shí)當(dāng)我們把這種弱相關(guān)整體看成一個(gè)泛函時(shí)，這樣仍然可以當(dāng)做獨(dú)立同分布的情形來證明，只是在證明過程中使用退耦不等式來分解這種非獨(dú)立的結(jié)構(gòu)。在證明第一個(gè)不等式時(shí)，我們分成了兩步，先是證明非負(fù)核的U一過程的集中不等式，然后證明有界的核。我們使用非退化的不等式的研究了逐對(duì)損失的學(xué)習(xí)問題。第二個(gè)不等式的證明更復(fù)雜一些，我們證明的結(jié)果和經(jīng)驗(yàn)過程有相同的結(jié)構(gòu)

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

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