Unsupervised Personalized Feature Selection--閱讀筆記

01-29

轉載請註明出處：All Minable團隊的搬磚日常

論文來源：AAAI 2018

論文鏈接：Unsupervised Personalized Feature Selection

論文原作者：Jundong Li, LiangWu, Harsh Dani, Huan Liu.

（侵刪）

Abstract

背景：

高維數據的學習任務需要進行降維處理，特徵選擇是一個比較有效的降維方法；
在很多現實環境中很難獲取標籤信息，需要進行無監督特徵選擇。

動機： 現存的絕大多數特徵選擇演算法都假設所有實例（instance）都具有一些共享特性子集（如，某一類）中的共性（commonality），然而，在許多實例顯示高度個性化的領域中，這種假設並不一定是正確的。例如，在社交媒體中，用戶發票圈的行為具有高度個性化（personality），我們需要捕捉用戶的異質性，以進行個性化的預測建模。

方法：這篇文章提出了一種新的無監督個性化特徵選擇框架UPFS，去獲取所有實例的共享特徵（shared features）和每個實例的個性化特徵（instance-specific features）；將問題轉化為一個原則性的優化框架，並提供了一個有效的演算法來解決這個問題。最後，在真實數據集上的實驗結果驗證了所提出的功能框架的有效性。

Introduction

目前提出的大多數基於稀疏學習的特徵選擇方法，絕大部分為所有實例構建了一個單一的全局模型（即特徵權重）。儘管在分類、聚類等方面取得了成功，但這種全局模型不可避免地忽略了每個實例的個性。在很多情況下，實例可能是非常特殊的。例如，不同興趣、個性的用戶在社交媒體的發帖行為明顯不同，他們經常使用的詞語和句子是多樣化的，具有不同的社交焦點。

雖然個性化特徵很重要，但不同的事例或多或少具有一些共性。例如，在醫學預測建模中，可能患者的健康狀況是不同的，但他們仍可能會有一些特定疾病的共同癥狀。因此，通過在所有實例中找出一些共享特徵來利用常見模式進行學習也至關重要。

受上述觀察的啟發，作者提出了一個為每個實例獲取子集共享特徵和個性化特徵的無監督個性化特徵選擇演算法。下圖1顯示了提出的無監督個性化特徵選擇的實例：

本文主要解決兩個問題：

如何對所有實例的共同模式進行模型化，並對每個特定實例的個性化模式進行特徵選擇。
當標籤信息不可用時如何找到共享特徵和個性化特徵。

為了回答這兩個問題，提出了一個無監督的個性化特徵選擇框架UPFS。這項工作的主要貢獻總結如下：

正式定義了無監督個性化特徵選擇的問題。
我們提出一個原則性的方法，通過發現共同特徵和為每個實例定製的判別特徵來捕捉共同模式和個性化模式。
我們提出了一個有效的交替演算法來解決UPFS框架的優化問題。
我們驗證UPFS框架在不同類型的實際數據集上的有效性。

Unsupervised Personalized Feature Selection Framework - UPFS

相關定義：

$X$ ：為無標籤數據集，其中每個實例 $X_i in mathbb R^d$ 在一個 $d$ 的特徵空間。
$n$ 個不同的實例來自 $c$ 個不同的類，這裡假設每個實例只屬於一個類。
$F in {0,1}^{n*c}$ ：為one-hot 類矩陣，其中當 $X_i$ 屬於類 $j$ 時， $F_{i,j} = 1$ ，否則 $F_{i,j} = 0$ 。

獲取共享特徵的目標函數，即求全局特徵權重：

這是一個帶有稀疏正則化項的最小二乘分類模型，其中 $W in mathbb R ^{d*c}$ 是一個全局特徵權重， $alpha$ 去控制全局特徵權重 $W$ 的稀疏度，在 $W$ 中添加一個範式懲罰項是為了在不同類中實現聯合特徵的稀疏性。

獲取共享特徵和個性化特徵的目標函數，即求全局特徵權重和局部特徵權重：

其中 $U^i in mathbb R ^{d*c}$ 是實例 $X_i$ 局部特徵權重。

為了找到每個實例判別特徵的一個子集，實現局部特徵權重 $U^i$ 的特徵稀疏性。將每個局部特徵權重 $U^i$ 看作一個組。當我們試圖找到針對每個實例定製的個性化特徵時，我們鼓勵組內競爭，但是不鼓勵組間競爭。通過這種方式去找每個實例的個性化特徵。數學上，在每個 $U^i$ 上添加 $l_{2,1}$ 範式進行聯合特徵稀疏化，如下：

公式（3）能夠執行無監督的個性化特徵選擇，以獲得所有實例的多個共享特徵以及特定於單個實例的個性化特徵。但存在以下不足：

計算耗費很大
很容易過擬合且泛化能力較差（只利用一個實例 $X_i$ 來訓練局部特徵權重 $U^i$ ）

為了緩解這些不足，強迫實例向鄰居借力去學習局部特徵權重。首先構建輸入實例的最近鄰親和度圖來實現局部幾何結構。最近鄰親和度圖 $S∈mathbb R^{n×n}$ 的創建過程如下：

其中 $mathcal N_p(X_i)$ 是實例 $X_i$ 的 $k$ 近鄰鄰居集合， $sigma$ 是個預定義參數。

在此基礎上，強迫連接的實例通過網路lasso懲罰（network lasso penalty）來相互借鑒學習局部特徵權重：

式（5）表明如果 $X_i$ 和 $X_j$ 具有高度相似性，那麼 $U^i$ 和 $U^j$ 就相似。因此，它可以極大地減少個性化特徵選擇的模型參數的數量，也可以減輕過度擬合問題。

此外，根據光譜理論（spectral theory），偽類標籤的合理選擇應該保留數據的局部幾何結構，使得其他原始特徵空間中也應該具有相同的類別標籤。由於數據局部幾何結構已經通過方程（4）中定義的親和度圖來建模。我們使偽類標籤 $F$ 在親和度圖 $S$ 上平滑，得到下面的項：

其中， $D$ 是對角矩陣且 $D_{ii} = sum_{j=1}^nS_{ij}$ ； $L$ 為歸一化的拉普拉斯矩陣且 $L=D^{-1/2}(D-S)D^{-1/2}$ 。

綜上，最後的目標函數如下：

其中， $U = [U^1;...;U^n]$ 是所有局部特徵權重的連接； $beta$ 正則化參數，控制在學習局部特徵權重時藉助鄰居的強度； $gamma$ 正則化參數，控制偽標籤保存數據局部幾何結構的程度。由於離散約束，使得它成為整數規劃問題（integer programming problem），因此難以求解上述目標函數。因此放寬了約束條件：

放寬後可重寫如下：

這裡引入參數 $theta$ 來保證正交條件滿足。

求解上述目標函數獲得模型參數 $W$ , $U$ 和 $F$ 之後，可以執行偽類標籤預測。對於每個實例 $X_i$ ，分類器是全局特徵權重 $W$ 和局部特徵權重 $U^i$ 的聯合。特別地，對於每個實例 $X_i$ ，我們將第 $j$ 個特徵的特徵分數定義為 $parallel K_{j *} parallel_2^2$ ，其中 $K = W + U^i$ 。在計算所有特徵分數之後，對它們進行降序排序，並返回排名前 $m$ 位的特徵，其中 $m$ 是我們想要選擇的特徵的數量。