Robust Unsupervised Feature Selection on Networked Data -- 閱讀筆記

02-02

轉載請註明出處：

每周一篇機器學習論文筆記zhuanlan.zhihu.com

論文來源：SDM 2016

論文下載：Robust Unsupervised Feature Selection on Networked Data

論文作者： Junking Li、 Xia Hu、Liang Wu、 Huan Liu

Abstract

背景：

高維數據的學習任務需要進行降維處理，特徵選擇是一個比較有效的降維方法；
大多數傳統的特徵選擇演算法是基於數據實例滿足獨立同分布（i.i.d.），但是網路數據不滿足這個假設；
在很多現實環境中很難獲取標籤信息，需要進行無監督特徵選擇。

方法： 利用網路數據中的連接信息去選擇有效特徵。

貢獻：這篇文章針對網路數據提出了具有魯棒性的無監督特徵選擇框架NetFS，將潛在表達學習嵌入到特徵選擇中去。因此，內容信息能夠幫助減輕學習潛在表達中雜訊環節的負面影響，而良好的內容表達又可以有助於提取更有意義的特徵。最後，在真實數據集上的實驗結果驗證了所提出的功能框架的有效性。

Introduction

網路數據特徵：

網路數據對網路中實例之間的配對關係進行編碼，如生物信息學中的基因相互作用，網頁之間的超鏈接，研究論文中的引用等。
網路化的實體往往伴隨著高維度的特徵，如在Facebook和Twitter上，每天都會產生數百萬個帖子。

現有的無監督特徵選擇演算法不能直接應用在網路數據中：

在網路中，數據實例不滿足獨立同分布(i.i.d.)；且他們往往與一些內容信息相關聯。
內容信息和連接信息包含大量雜訊。

根據網路數據的獨特性質，作者提出了一個健壯的無監督特徵選擇框架NetFS。首先，引入潛在表示（latent representation）的概念來揭示網路結構中編碼的隱藏屬性，去捕捉網路實例之間固有的相互作用；其次，將潛在表示學習嵌入到特徵選擇階段，去減少特徵選擇中雜訊環節的負面影響。具體而言，內容信息有助於減輕嘈雜環節對學習潛在表現的負面影響，學習到的潛在表徵不僅可以表徵網路結構，還可以作為標籤信息來指導特徵選擇階段。

本文的主要貢獻如下：

提出將網路結構中的潛在表徵學習嵌入特徵選擇階段的原理方法;
提出一個強大的無監督特徵選擇框架NetFS用於網路數據;
提供交替演算法來優化提出的NetFS框架；
在真實數據集中評估NetFS框架的有效性。

Robust Unsupervised Feature Selection for Networked Data - NetFS

相關定義：

$u = {u_1,u_2,...,u_n}$ ：網路中存在連接關係的 $n$ 個實例；
鄰接矩陣 $Ain R^{ntimes n}$ ：表達 $U$ 的網路結構，對於無向圖 $A=A^{}$ ，對於有向圖 $A=max(A,A^{})$ ;
$F={ f_1, f_2,...,f_d }$ ：實例的特徵集；
$Xin R^{ntimes d}$ ： $n$ 個實例的內容信息矩陣；

根據定義，網路數據的無監督特徵選擇問題可以總結如下：

給定：特徵集 $F$ 、內容信息矩陣 $X$ 和網路信息鄰接矩陣 $A$ ；
選擇：利用給定信息，選擇最具相關性的子集 $Ssubseteq F$ 。

提出的框架如下圖所示：

由圖可知，首先從網路數據中提取出內容信息和連接信息；然後交替進行以下兩步：

第一步，用潛在表達學習的概念來模擬連接信息。
第二步，將潛在表達學習嵌入到特徵選擇中。

第一步：Modeling Link Information with Latent Representation

在網路中，實例由於各種因素而相互連接，例如：

在社交網路中，這些因素可以是電影迷，體育愛好者，同事，家庭成員等;
在共同作者網路中，這些因素可以是類似的研究興趣，相同的從屬關係等。

這些因素可以描述隱藏在網路中一組不同的歸屬因素，通常被稱為潛在表達。不同實例的潛在表達形成連接信息，具有相似潛表達的實例比潛在表達不同的實例更有可能相互連接。

在這裡，利用對稱非負矩陣分解模型（SymNMF）對連接信息中的潛在表達進行建模。SymNMF的原理與網路聚類一致，每個網路實例由潛在屬性組成。在數學上，它將鄰接矩陣 $A$ 分解成非負矩陣 $U$ 和其在低維空間中的轉置 $U$ 的乘積：

$Uin R^{ntimes c}$ ：所有 $n$ 個實例的潛在表達；
$c$ ：潛在因素的數目。

第二步：Embedding Latent Representation Learning into Feature Selection

背景：

由於網路數據中存在雜訊連接，直接從連接信息中獲取的潛在表達可能會影響內容空間的特徵選擇。
根據網路研究中的同質效應，內容信息會影響和依賴於網路結構中的潛在表達。

因此，將潛在表達學習嵌入到內容空間的特徵選擇階段。內容信息可以幫助學習更好的魯棒潛在表達，更好的潛在表達可以填補標籤信息和豐富連接信息。

潛在的因素與網路實例的一些特徵（或屬性）相關，因此以 $U$ 為約束，通過多元線性回歸模型對內容信息進行建模：

$Win R^{dtimes c}$ ：變換參數矩陣，每一行向量 $W(i,:)$ 衡量第 $i$ 個特徵的重要性；
在 $W$ 上添加了一個 $l_{2,1}$ 範數正則項：為了控制所有潛在因素之間的聯合稀疏性。

綜合以上第一步和第二步，框架的最後目標函數如下：

$beta$ ：平衡內容空間中的潛在表達建模和特徵選擇。

目標函數使得當變換參數矩陣 $W$ 固定時，潛在表達學習階段不僅與鄰接矩陣 $A$ 有聯繫，而且還與內容矩陣 $X$ 有關。這樣，學習到的潛在表達不僅可以捕獲它們固有的相關性，還對雜訊連接更加魯棒。當潛在表達矩陣 $U$ 被固定時，利用標籤信息以監督的方式進行特徵選擇。

Optimization Solution

固定 $U$ ，更新 $W$ ：

$Din R^{dtimes d}$ ：是個對角矩陣，對角元素為 $D(i,i)=frac{1}{2||W(i,:)||_2+epsilon }$ （3.6）。

將式（3.7）代入原目標函數，得到：

上式是一個標準的邊界約束優化問題，這裡使用投影梯度法來優化它。目標函數可以重新表述為：

固定 $W$ ，更新 $U$ ：

$U_t$ ： $U$ 的第 $t$ 次迭代；
$P[U_t-s_t bigtriangledown jmath (U_t)]$ ：投影點映射到有界區域的盒投影運算元。

最後NetFS框架的演算法如下：

Experiments

數據集：

BlogCatalog：是一個社交博客目錄，用戶可以在不同的預定義類別下發布他們的博客。用戶博客的標籤信息構成了特徵信息，ground truth是用戶博客的主要類別。
Flickr：是一個圖片分享網站，用戶可以為他們上傳的照片提供標籤，提供特徵信息。此外，用戶與其他人交互形成鏈接信息。照片按照一些預定義的類別進行上傳，ground truth是預定於類別。
Epinions：是一個產品評論網站，用戶可以在其中分享有關產品的評論。用戶自己也可以建立信任網路來尋求他人的建議。特徵由詞袋模型形成，ground truth是用戶的主要評論類別。

實驗評估參數：

Clustering Accuracy (ACC)
Normalized Mutual Information (NMI)

對比特徵選擇演算法：

聚類演算法：K-means；
實驗結果：20次K-means求平均。

實驗結果：

實驗總結：

NetFS幾乎都優於傳統的無監督特徵選擇演算法，一個主要的原因是傳統演算法只能處理i.i.d.數據，而NetFS利用內容信息和網路結構獲得良好的性能。
NetFS只使用總特徵的1/7--1/8便能達到很好的聚類效果。

參數分析：

$beta$ 固定為0.1， $alpha$ 在1-1000中穩定；
$alpha$ 固定為10， $beta$ 不敏感。

個人總結：

特徵選擇演算法就是要選擇出最能表達原始數據的特徵子集，這就需要研究原始數據的特性，對於不同的數據有不同的隱藏信息，根據隱藏信息設計目標函數。本文作者就根據網路數據的內容信息和連接信息去尋求數據特徵的潛在表達，最後採用交叉迭代法來求解。交叉迭代法一來可以讓目標函數收斂，二來使交叉的兩個步驟相互幫助促進選擇結果。

最近一直在看這個作者的系列論文，看完最新的又回過頭來補之前的，發現任何idea都需要積累沉澱，自己還需要多多學習！