1.? ? 原文：Active Feature Acquisition with Supervised Matrix Completion

作者來自南航序宦、理研和東大

關(guān)鍵詞：主動學(xué)習(xí)敬惦，特征獲取族操，矩陣完備化

1.1? 引言

在數(shù)據(jù)挖掘和機器學(xué)習(xí)任務(wù)中面睛，一組數(shù)據(jù)對象通常表示為特征矩陣痰滋，其中每行是一個對象酪惭，每列是特征的一個維度沪饺。如果特征值嚴(yán)重缺失，在該數(shù)據(jù)集上訓(xùn)練的分類模型的性能將顯著退化商佛。矩陣完備化將是用于恢復(fù)特征矩陣的缺失條目的有用工具喉钢，已被廣泛研究。類標(biāo)簽強烈依賴于特征表示良姆，會減小全部可能矩陣的選擇范圍肠虽，而且不同的特征可能對恢復(fù)缺失值以及改進(jìn)分類模型具有不同的貢獻(xiàn)。傳統(tǒng)的主動學(xué)習(xí)算法選擇信息量最大的未標(biāo)記實例來查詢其標(biāo)簽玛追，并且可以顯著降低注釋成本税课。這篇文章綜合了主動特征查詢和監(jiān)督矩陣完備化，以最小化數(shù)據(jù)獲得成本痊剖。理論分析給出了矩陣完備算法重構(gòu)誤差的上界伯复，同時在不同的數(shù)據(jù)集上進(jìn)行實驗以驗證所提出的方法的有效性。

1.2? 相關(guān)工作

主動學(xué)習(xí)已經(jīng)被廣泛研究以降低標(biāo)注成本邢笙，比如統(tǒng)計方法啸如，SVM，委員會選擇法等氮惯。與旨在降低標(biāo)簽成本的傳統(tǒng)主動學(xué)習(xí)不同叮雳，還有另一個研究分支采用相似性方法來降低特征獲取成本想暗，比如提出一個標(biāo)準(zhǔn)來估計每單位成本的準(zhǔn)確性的預(yù)期改進(jìn)，然后迭代地獲得最具成本效益的特征值帘不，還有一種類似的方法说莫，其中學(xué)習(xí)任務(wù)是聚類而不是分類，因此相應(yīng)的標(biāo)準(zhǔn)估計了每單位成本的聚類質(zhì)量的預(yù)期改進(jìn)寞焙。這些方法的一個共同限制是它們不考慮可以從觀察到的條目中準(zhǔn)確地恢復(fù)一些缺失特征的情況储狭，因此可能浪費不必要的特征獲取成本〉方迹恢復(fù)缺失特征所使用的懲罰訓(xùn)練需要監(jiān)督學(xué)習(xí)辽狈，而矩陣完備是用于恢復(fù)部分觀察到的矩陣的缺失條目的經(jīng)典方法。在某些情況下呛牲，觀察到的條目不足以恢復(fù)其他條目刮萌，因此需要進(jìn)一步工作以獲取一些缺失條目的更多實實際值。雖然上述所有研究都沒有在理論上的完備性娘扩，但還是有著重于基于結(jié)果的自適應(yīng)查詢矩陣着茸。

1.3? 提出的方法

考慮特征缺失問題，其中僅部分觀察到X琐旁。本文用Ω表示觀察到的X條目的索引集涮阔。 在本節(jié)的其余部分，本文將首先提出一種監(jiān)督矩陣完成方法灰殴，然后提出一種主動特征獲取方法敬特。

1.3.1? ? ?監(jiān)督矩陣完備

我們關(guān)注監(jiān)督分類設(shè)置下的矩陣完成問題，其中任務(wù)是學(xué)習(xí)用于預(yù)測實例的類標(biāo)簽的函數(shù)f验懊。目標(biāo)函數(shù)一方面擅羞，通過低秩假設(shè)從X的部分觀察中準(zhǔn)確地恢復(fù)地面實況特征矩陣尸变，另一方面义图，用恢復(fù)的矩陣DX訓(xùn)練的分類模型f預(yù)期具有小的經(jīng)驗誤差。

對問題優(yōu)化如下：

得到等價問題：

1.3.2? ? ?主動特征獲取

如何積極地查詢地面實況值作為最具信息性的特征召烂，此處目標(biāo)問題是證明模型主要基于最小數(shù)量的查詢碱工。基于方差的選擇奏夫，如果模型對實例的預(yù)測不太確定怕篷，則該實例被認(rèn)為對于改進(jìn)模型更具信息性，并且更有可能被選擇用于標(biāo)簽查詢酗昼。需要提出的是廊谓，沒有必要根據(jù)所有迭代計算方差。一般來說麻削，獲得最近迭代中的條目變化更為重要蒸痹。最后春弥，獲取特征值的代價因不同的特征而異。同時叠荠，在每次迭代中匿沛，選擇一小部分缺失的特征矩陣條目來獲取它們的標(biāo)注值。進(jìn)一步說榛鼎，這里采用最近提出的帕累托優(yōu)化算法（POSS）來解決這個問題逃呼。 POSS是一種進(jìn)化風(fēng)格算法，它維護(hù)解決方案存檔者娱，并通過用更好的解決方案替換某些解決方案來迭代更新存檔抡笼。

1.3.3? ? ?理論分析

對于Xw和y之間的損失最小化問題，這里通過強制Xw和y相等來討論更嚴(yán)格的情況：對于SVD為M=UΣV?的秩-r矩陣M∈Rn×m肺然，我們使用以下值作為相干性蔫缸，相干性越低，條目的值的平均分布越均勻际起。假設(shè)aX∥2tr≤βrnd拾碌，f（X）= y并且Ω是在具有概率|Ω| /（nd）的二項式模型之后隨機獨立選擇的。 設(shè)DX *為優(yōu)化問題的解街望，μ=maxDX∈Gμ（DX）校翔，其中G?Rn×d為G =（XD∈Rn×d |∥DX∥2ndDX*? - X∥2tr ≤βrnd，f（DX）=y√F≤2*灾前。防症，C0μ2βsr（n + d）|Ω|）s對于某些r≤min{n，d}和β≥0哎甲。然后至少有概率 1 -C /（n + d）蔫敲，我們有

1.4? 實驗

在6個數(shù)據(jù)集上進(jìn)行實驗，即鮑魚炭玫，信件奈嘿，圖像，國際象棋吞加，HillValley和HTRU2裙犹。在實驗中，檢查矩陣完備和主動特征獲得后的分類的性能衔憨。主動特征獲取方法AFASMC也與以下方法進(jìn)行了比較叶圃，對于AFASMC，參數(shù)λ1和λ2在所有數(shù)據(jù)集上默認(rèn)固定為1践图。

對于不同的特征獲得代價掺冠，可以觀察到，考慮獲得代價的兩種策略都可以獲得比原始AFASMC更好的性能码党。

同時德崭，捕獲最近迭代中條目的變動更為重要悍及，即方差計算應(yīng)該更多地強調(diào)最近的迭代。