CMU的研究人員Yichong Xu等提出了一種半監(jiān)督算法排序回歸

非參數(shù)回歸（nonparametric regression）是一種在實(shí)踐中很有吸引力的方法，因?yàn)樗浅ｌ`活，對(duì)未知回歸函數(shù)的先驗(yàn)結(jié)構(gòu)假定限制相對(duì)寬松。然而，相應(yīng)的代價(jià)是它需要大量標(biāo)注數(shù)據(jù)，且隨著維度的增加而指數(shù)級(jí)增長——所謂維度的詛咒（curse of dimensionality）。標(biāo)注數(shù)據(jù)極為耗時(shí)耗力，而在很多場(chǎng)景下，序信息（ordinal information）的獲取則相對(duì)而言成本較低。有鑒于此，CMU的研究人員Yichong Xu等提出了一種半監(jiān)督算法排序回歸（Ranking-Regression），結(jié)合少量標(biāo)注樣本，加上大量未標(biāo)注樣本的序信息，逃脫維度的詛咒。

非參數(shù)方法

在監(jiān)督學(xué)習(xí)問題中，我們有一些標(biāo)注過的數(shù)據(jù)（觀測(cè)），然后尋找一個(gè)能夠較好地?cái)M合這些數(shù)據(jù)的函數(shù)。

給定一些數(shù)據(jù)點(diǎn)，尋找擬合這些數(shù)據(jù)點(diǎn)的函數(shù)，我們首先想到的就是線性回歸：

其中：

y為因變量（即目標(biāo)變量）；

w為模型的參數(shù)；

X為觀測(cè)及其特征矩陣；

?為對(duì)應(yīng)于隨機(jī)、不可預(yù)測(cè)的模型錯(cuò)誤的變量。

我們可以看到，線性回歸的過程，其實(shí)就是找出能夠最好地?cái)M合觀測(cè)的參數(shù)w，因此，線性回歸屬于參數(shù)方法。

然而，線性回歸假定線性模型可以很好地?cái)M合數(shù)據(jù)，這一假定未必成立。很多數(shù)據(jù)之間的關(guān)系是非線性的，而且很難用線性關(guān)系逼近。在這種情況下，我們需要用其他模型才能較好地?cái)M合數(shù)據(jù)，比如，多項(xiàng)式回歸。

綠線為線性回歸，紅線為多項(xiàng)式回歸；圖片來源：ardianumam.wordpress.com

無論是線性回歸，還是多項(xiàng)式回歸，預(yù)先都對(duì)模型的結(jié)構(gòu)有比較強(qiáng)的假定，例如數(shù)據(jù)可以通過線性函數(shù)或多項(xiàng)式函數(shù)來擬合，而這些假定不一定成立。因此，許多場(chǎng)景下，我們需要使用非參數(shù)回歸，也就是說，我們不僅需要找到回歸函數(shù)的參數(shù)，還需要找到回歸函數(shù)的結(jié)構(gòu)。

圖片來源：Brmccune；許可： CC BY-SA 3.0

例如，通常用于分類的K近鄰算法，其實(shí)還可以用于回歸。用于回歸的K近鄰算法，其基本流程和一般的用于分類的K近鄰算法差不多，唯一的區(qū)別是，分類時(shí)，目標(biāo)變量的分類為它的最近鄰中最常見的分類（眾數(shù)），而回歸時(shí)，目標(biāo)變量的值為它的最近鄰的均值（或中位數(shù)）。用于回歸的K近鄰算法，就是一種非參數(shù)回歸方法。

當(dāng)然，非參數(shù)方法的靈活性不是沒有代價(jià)的。由于不僅回歸函數(shù)的參數(shù)未知，回歸函數(shù)的結(jié)構(gòu)也未知，相比參數(shù)方法，我們需要更多的標(biāo)注數(shù)據(jù)來訓(xùn)練，以得到較好的結(jié)果。而隨著維度的增加，我們需要的標(biāo)注數(shù)據(jù)的數(shù)量呈指數(shù)級(jí)增長。這也正是我們前面提到的維度的詛咒。前面我們舉了K近鄰作為非線性回歸的例子，而K近鄰正因受維度詛咒限制而出名。

有鑒于此，許多研究致力于通過給非參數(shù)回歸增加結(jié)構(gòu)上的限制來緩解這一問題，例如，稀疏性或流形的限制（很多時(shí)候，高維數(shù)據(jù)空間是稀疏的，有時(shí)高維數(shù)據(jù)甚至基本上處于一個(gè)低維流形之上）。這是一件很有意思的事情。在實(shí)踐中，之所以選用非參數(shù)回歸，正是看重其靈活性，對(duì)擬合函數(shù)的結(jié)構(gòu)沒有很強(qiáng)的假定。然而，當(dāng)非參數(shù)回歸遇到維度詛咒的時(shí)候，我們又退回一步，通過加強(qiáng)結(jié)構(gòu)上的假定來緩解維度詛咒問題。

而CMU的研究人員Yichong Xu、Hariank Muthakana、Sivaraman Balakrishnan、Aarti Singh、 Artur Dubrawski則采用了另外的做法，使用具有序信息的較大數(shù)據(jù)集補(bǔ)充帶標(biāo)注的較小數(shù)據(jù)集，緩解非參數(shù)回歸在高維度下的問題。這一做法在實(shí)踐中意義很大，因?yàn)橄鄬?duì)標(biāo)簽而言，序信息的收集成本要低很多。例如，在臨床上，精確地評(píng)估單個(gè)患者的健康狀況可能比較困難，但是比較兩個(gè)患者誰更健康，則比較容易，也比較精確。

排序回歸算法

研究人員提出的排序回歸（Ranking-Regression）算法（以下簡(jiǎn)稱R2），其基本直覺是根據(jù)序信息推斷未標(biāo)注數(shù)據(jù)點(diǎn)的值。具體而言，根據(jù)序信息排序數(shù)據(jù)點(diǎn)，之后應(yīng)用保序回歸（isotonic regression），然后根據(jù)已標(biāo)注數(shù)據(jù)點(diǎn)和序信息推斷未標(biāo)注數(shù)據(jù)點(diǎn)的值。經(jīng)過以上過程之后，就可以用最近鄰算法估計(jì)新數(shù)據(jù)點(diǎn)的值了。

算法示意圖

上為R2算法示意圖。當(dāng)然，如果你更習(xí)慣看偽代碼的話：

R2的上下界

顯然，用序信息代替標(biāo)簽，有以次充好之嫌。因此，研究人員研究了R2算法的誤差上下界。

正如之前提到的，非參數(shù)回歸對(duì)結(jié)構(gòu)的假定比較寬松，但也并不是毫無限制的。研究人員采用了經(jīng)典的非參數(shù)回歸限制：

未標(biāo)簽數(shù)據(jù)集{X1, ..., Xn}中，Xi∈ X ? [0,1]d，且Xi均勻獨(dú)立抽取自分布Px。而Px滿足其密度p(x)對(duì)x ∈ [0,1]d而言是有界的，即 0 < pmin?<= p(x) <= pmax。

回歸函數(shù)f同樣也是有界的（[-M, M]），并且是赫爾德連續(xù)的，在0 < s <= 1時(shí)，

在滿足以上條件的條件下，研究人員證明了R2得出的回歸函數(shù)的均方誤差上界為：

其中，C1、C2為大于0的常數(shù)。

而回歸函數(shù)的均方誤差下界為：

其中，C為大于0的常數(shù)。

由誤差上下界可知，基于序信息的排序回歸效果不錯(cuò)，從對(duì)數(shù)因子上來說是最優(yōu)的。

另外，從R2誤差的上界來看，只有序信息（n）依賴于維度d（不等式右側(cè)第二項(xiàng)），而標(biāo)注信息并不依賴維度d（不等式右側(cè)第一項(xiàng)），也就是說，R2逃脫了維度的詛咒。

限于篇幅，這里就不介紹了證明過程了。上下界的證明思路，分別見論文的3.1小節(jié)和3.2小節(jié)；詳細(xì)證明過程，分別見論文的附錄B、C。

含噪聲的序信息

雖然之前說過序信息相對(duì)容易取得，也比較容易保持精確，但實(shí)際數(shù)據(jù)難免會(huì)有噪聲——錯(cuò)誤的序信息。之前的結(jié)論都是在序信息不含噪聲的前提下得出的，那么，當(dāng)序信息有噪聲的時(shí)候，情況又是怎么樣的呢？

研究人員進(jìn)一步推導(dǎo)了序信息包含噪聲的情況。當(dāng)然，噪聲是控制在一定范圍之內(nèi)的。假定根據(jù)含噪序信息所得到的排序與真實(shí)排序之間的Kendall-Tau距離不超過vn2（n代表只有序信息的未標(biāo)注數(shù)據(jù)），則R2的均方誤差的上界為：

下界為：

由此可知，R2的魯棒性相當(dāng)好。當(dāng)有足夠的序信息時(shí)，即使序信息包含一些噪聲，標(biāo)注數(shù)據(jù)仍然不依賴于維度，也就是說，R2仍能逃脫維度的詛咒。

同樣，我們這里不給出具體的證明過程。請(qǐng)參考論文4.1、4.2小節(jié)了解證明思路，論文附錄D、F了解詳細(xì)證明過程。

另外，研究人員還進(jìn)一步證明了（證明過程見附錄E），存在逼近函數(shù)f滿足

這就意味著，當(dāng)噪聲過大（v過大）時(shí)，通過使用交叉驗(yàn)證過程（R2和忽略序信息的簡(jiǎn)單非參數(shù)回歸器），我們可以選擇較好的回歸方法，從而取得較優(yōu)的表現(xiàn)。事實(shí)上，當(dāng)我們有足夠標(biāo)簽時(shí)，即使序信息非常噪雜，以上比率仍能收斂至0.

含噪聲的成對(duì)比較

有的時(shí)候，序信息是以成對(duì)比較（pairwise comparison）（數(shù)據(jù)點(diǎn)兩兩之間的大?。┑男问饺〉玫?。當(dāng)不含噪聲的時(shí)候，成對(duì)比較和之前提到的標(biāo)準(zhǔn)排序形式是等價(jià)的。但有噪聲的情況卻有所不同。研究人員證明了，在序信息為含噪聲的成對(duì)比較時(shí)，逼近函數(shù)的均方誤差的上界為：

其中，C1和C2為大于0的常數(shù)。

由上式可知，當(dāng)維度d >= 4s時(shí)，誤差取決于n-2s/d，并且，在這一設(shè)定下，基于含噪聲的成對(duì)比較的排序回歸，同樣從對(duì)數(shù)因子上來說是最優(yōu)的。

試驗(yàn)

為了驗(yàn)證理論結(jié)果以及測(cè)試R2的實(shí)際表現(xiàn)，研究人員進(jìn)行了一些試驗(yàn)：

在模擬數(shù)據(jù)上進(jìn)行試驗(yàn)，這樣可以充分控制噪聲

在UCI數(shù)據(jù)集上進(jìn)行試驗(yàn)，通過標(biāo)簽?zāi)M排序

試驗(yàn)R2在實(shí)際應(yīng)用中的表現(xiàn)

在所有試驗(yàn)中，研究人員對(duì)比了R2和K近鄰算法的表現(xiàn)。之所以選擇K近鄰，是因?yàn)镵近鄰在理論上接近最優(yōu)，并在實(shí)踐中應(yīng)用廣泛。理論上說，有m個(gè)標(biāo)注樣本時(shí)，k的最優(yōu)值為m2/(d+2)。然而，對(duì)研究人員考慮的所有m、d值而言，m2/(d+2)非常小（< 5）。因此，研究人員的試驗(yàn)中選用的是一組常量k值（不隨m改變）。每個(gè)試驗(yàn)重復(fù)了20次，并對(duì)均方誤差取平均值。

模擬數(shù)據(jù)

研究人員采用如下方法生成了數(shù)據(jù)：令d = 8，均勻取樣X自[0, 1]d。目標(biāo)函數(shù)為：

其中，xd為x的第d維，且

其中，p隨機(jī)均勻取樣自[0, 10]。研究人員調(diào)整了f(x)，使其均值為0，方差為單位方差。通過y = f(x) + ε，ε ~ N(0, 0.52)生成標(biāo)簽。

研究人員為訓(xùn)練集和測(cè)試集各生成了1000個(gè)樣本。

研究人員測(cè)試了R2的兩個(gè)變體，1-NN和5-NN，在算法的最后一步分別使用1、5個(gè)最近鄰。5-NN并不影響之前理論分析部分的上下界，然而，從經(jīng)驗(yàn)出發(fā)，研究人員發(fā)現(xiàn)5-NN提升了表現(xiàn)。

左：序信息無噪聲；右：序信息有噪聲

從上圖可以看到，無論序信息是否有噪聲，R2的表現(xiàn)都很好。

為了研究序信息噪聲的影響，研究人員在固定標(biāo)注/排序樣本數(shù)100/1000的情況下，改變了序信息噪聲的等級(jí)。對(duì)噪聲水平σ，序信息通過y' = f(x) + ε'生成，其中ε' ~ N(0, σ2)。

可以看到，隨著噪聲水平的升高，均方誤差也相應(yīng)升高了。

UCI數(shù)據(jù)集

研究人員在兩個(gè)UCI回歸數(shù)據(jù)集上進(jìn)行了試驗(yàn)。這兩個(gè)數(shù)據(jù)集分別為Boston-Housing（波士頓房價(jià)）和diabetes（糖尿?。Ｐ蛐畔⑹峭ㄟ^數(shù)據(jù)集標(biāo)簽生成的。

可以看到，相比不使用序信息的基線，R2在兩個(gè)數(shù)據(jù)集上的表現(xiàn)都更好。

根據(jù)肖像預(yù)測(cè)年齡

為了進(jìn)一步在實(shí)踐中驗(yàn)證R2算法，研究人員考慮了根據(jù)肖像估計(jì)人員年齡的任務(wù)。

研究人員使用了APPA-REAL數(shù)據(jù)集，該數(shù)據(jù)集包含7591張圖像，每張圖像都有相應(yīng)的生物學(xué)年齡和表觀年齡。生物學(xué)年齡為實(shí)際年齡，表觀年齡基于眾包收集。根據(jù)多人的估計(jì)的平均值得到表觀年齡（平均有38個(gè)不同的估計(jì)者）。APPA-REAL同時(shí)提供了表觀年齡估計(jì)的標(biāo)準(zhǔn)差。數(shù)據(jù)集分為三部分，4113張訓(xùn)練圖像、1500張驗(yàn)證圖像、1978張測(cè)試圖像，研究人員的試驗(yàn)只使用了訓(xùn)練和驗(yàn)證樣本。

研究人員使用FaceNet的最后一層從每張圖像中提取了128個(gè)維度的特征，并縮放每項(xiàng)特征使每個(gè)樣本X ∈ [0, 1]d。研究人員使用了5-NN和10-NN。除了像之前的試驗(yàn)一樣，使用不包含序信息的5-NN、10-NN作為基線外，還比較了核支持向量回歸（SVR）的表現(xiàn)。SVR的參數(shù)配置為scikit-learn的標(biāo)準(zhǔn)配置，懲罰參數(shù)C = 1，RBF核，tolerance值為0.1.

研究人員試驗(yàn)了兩個(gè)任務(wù)：

第一個(gè)任務(wù)的目標(biāo)是預(yù)測(cè)生物學(xué)年齡。標(biāo)簽為生物學(xué)年齡，而序信息基于表觀年齡生成。這是為了模擬現(xiàn)實(shí)場(chǎng)景，有一小部分樣本的真實(shí)年齡信息，但希望通過眾包的方式收集更多樣本的年齡信息。而在眾包時(shí)，讓人對(duì)樣本的長幼進(jìn)行排序，要比直接估計(jì)年齡要容易一點(diǎn)，也精確一點(diǎn)。

第二個(gè)任務(wù)的目標(biāo)是預(yù)測(cè)表觀年齡。在這一任務(wù)中，標(biāo)簽和排序根據(jù)APPA-REAL提供的標(biāo)準(zhǔn)差生成。具體而言，標(biāo)簽取樣自一個(gè)高斯分布，其均值等于表觀年齡，標(biāo)準(zhǔn)差為數(shù)據(jù)集提供的標(biāo)準(zhǔn)差。排序的生成分兩步，首先根據(jù)同樣的分布生成標(biāo)簽，然后根據(jù)標(biāo)簽排序。這是為了模擬現(xiàn)實(shí)場(chǎng)景中，讓人同時(shí)估計(jì)樣本的年齡，并對(duì)樣本的長幼進(jìn)行排序。注意，在真實(shí)應(yīng)用中，相比試驗(yàn)，排序的噪聲會(huì)低一點(diǎn)。

結(jié)果如上圖所示。我們可以看到，10-NN版本的R2的表現(xiàn)最好。而當(dāng)樣本數(shù)少于500時(shí)，R2的10-NN版本和5-NN版本均優(yōu)于其他算法。

結(jié)語

論文可通過預(yù)印本文庫獲?。篴rXiv:1806.03286

另外，本文作者將在ICML 2018上做口頭報(bào)告（Wed Jul 11th 11:00 -- 11:20 AM @ A6）。