(cache) Unsupervised Feature Selection with Adaptive Structure Learning(KDD 2015)を読んだ

読んだ論文は
Unsupervised Feature Selection with Adaptive Structure Learning
今回もKDD　2015というか当分はKDD2015の論文の消化を行う．
Tableを見て，興味のありそうな論文をかたっぱしから読んで，とりあえずまとめてみることにする．
ちなみにタイトルを日本語検索してヒットしなかったものをチョイスしている．（前回のはTwitterで感想を述べている先生がいたんですが．．．カウントせずということにしています）

モチベーション

Feature SelectionとStructure Characterizationを同時に行う手法を考えたい．
何故なら
特徴選択は本質的な構造を保持するように行うべきものである．(Structure Characterization → Feature Selection)
しかし，同時に
本質的な構造は高次元やノイズが多い状態では分からない (Feature Selection → Structure Characterization)
というジレンマ(Chicken and Egg Problem，鶏が先か卵が先か)を解決したい．

コントリビューション

既にLLCFSという手法が両方を同時に行う手法として提案されているようだが，

異なる目的を最適化しているためよろしくない．（どのようなものなのかは，論文を読んでいないので定かではない）
提案法は両方を組み込んだ一つの最適化問題にしている．

他の手法がよくまとめられている．（網羅されているかは定かではないが．．．）

問題設定

Unsupervised Learningを行うための特徴選択．ゴールはd次元の特徴からクラスタリングの精度を向上させるk個の特徴(kはd以下の任意の数)を選ぶこと
扱う行列は $X \in \mathbb{R}^{d \times n}$ ，d次元n個のインスタンスがある(各列ベクトルが各インスタンスに対応)

提案手法

Global StructureとLocal StructureそしてFeature Selectionを同時に最適化する．

Global Structure

Global StructureはPCAやMaximum Variance(MaxVer)といったもので学習されるもので，
この論文ではインスタンスを他のインスタンスで表現するような形で学習されるSpare Representationを用いる．(顔画像の学習に用いられている)
具体的には
$\begin{equation} \min_{S} \sum_{i=1}(\|x_{i} -Xs_{i}\|^{2}+\alpha\|s_{i}\|_{1}) \ \ \ \ \ \ \text{s.t.} \ \ \ \ S_{ii}=0 \end{equation}$
(対角要素に値が入ると，自分自身を自分自身で表現するような話になるので0という制約を与えている)

Local Structure

Local StructureはLocal manifold structureをさしており，グラフラプラシアンを用いて学習されるもので(LLEとかLPPとかいろんなところで使われてる)
グラフラプラシアンを用いる場合にはFeature Selectionによって選択された特徴を用いてk-nn(discrete)グラフを作成する必要がある．しかしdiscrete neighborhoodは収束の保証がない．
そのためこの論文ではprobabilistic neighborhood $P \in \mathbb{R}^{n\times n}$ をもちいる．
よって最適化問題は
$\begin{equation} \min_{P}(\|x_{i}-x_{j}\|^{2}_{2}P_{ij}+\mu P_{ij}^{2}), \ \ \ \ \ \ \ \text{s.t.} \ \ \ \ P1_{n}=1_{n},P \geq 0 \end{equation}$
（制約は確率となるような制約）

Feature Selection

Global StructureとLocal Structureの両方に，d次元をc次元に線形変換する行列 $W \in \mathbb{R}^{d \times c}$ を考える．( $\{0,1\}$ ではないことに留意)
ここで列ベクトル毎のスパース制約を与える． $l_{2,1}$ ノルムを $\|X\|_{2,1}=\sum_{i=1}^{d}\sqrt{\sum_{j=1}^{n}X_{ij}^{2}}$ このように定義する．
これを用いてGlobal StructureとLocal Structureを再定義する.

Global Structureは
$\begin{equation} \min_{S,W} \sum_{i=1}(\|W^{T}x_{i} -W^{T}Xs_{i}\|^{2}+\alpha\|s_{i}\|_{1}＋\gamma\|W\|_{2,1}) \ \ \ \ \ \ \text{s.t.} \ \ \ \ S_{ii}=0, W^{T}XX^{T}W^{T}=I \end{equation}$
同様にLocal Structureは
$\begin{equation} \min_{P,W}(\|W^{T}x_{i}-W^{T}x_{j}\|^{2}_{2}P_{ij}+\mu P_{ij}^{2})+\gamma\|W\|_{2,1}, \ \ \ \ \ \ \ \text{s.t.} \ \ \ \ P1_{n}=1_{n},P \geq 0, W^{T}XX^{T}W^{T}=I \end{equation}$

上の2式を足し合わせることで同時に最適化する．
最適化には交互最適化を用いる．

は一般化固有値問題に帰着できる．
はLasso．
は論文上で反復なしで高速解くことができるアルゴリズムが紹介されている．（略）

収束するまで頑張りましょうということです．
こうすることで，Global/Local Structureを考慮した特徴選択する行列が得られる．（同時にGlobal/Local Structure S,P は特徴選択を考慮したものになっている)
最終的には得られたの行ベクトルのノルムでソート $\|w^{T}_{i}\|_{2},i=1,\dots,d$ でソートした上から順に好きなK個の特徴を選ぶ(擬似コードでは $\|w_{i}\|_{2}$ になっているが，typoだと思っている．読んだ人に教えて欲しい．)

実はの求め方は工夫がある．
というのも交互最適化で固有値問題を解くことは絶望的なので
この最適化を2段階に分けて行う．仮に
$\begin{equation} XLX^{T}w=\lambda XX^{T}w \end{equation}$
という一般化固有値問題を解きたいとする．その際に， $XW^{T}=Y$ となる行列があるとすると，
上の固有値及び固有ベクトルと以下の式の固有値固有ベクトルは等価になる．(Theorem 1.)
$\begin{equation} Ly=\lambda y \end{equation}$

よって下の式を解いてから，
$\begin{equation} \min_{W}\| Y-X^{T}W\|^{2}+\gamma\|W\|_{2,1} \end{equation}$
を求めることで，を得る．

実験

設定

複数の特徴選択手法と比較
LapScore,MCFS,LLCFS,UDFS,NDFS,SPFS,RUFS
データセットはMEFA,USPS49,UMIST,JAFFE,AR,COIL,LUNG,TOX
提案手法のコードは公開されている模様．どうやらmatlab形式
csliangdu/FSASL · GitHub

特徴選択後のクラスタリングアルゴリズムにはk-meansを用いる．

結果

全ての特徴を用いた場合よりは必ずいい結果
他手法と比べても，全てのデータセットで最良の結果．（Accuracyで他手法の最良と比べておおよそ2%程度いい結果，t検定を行って有意差があることを確認)
また， P,S,W を全て用いる場合が一番良い結果になることも確認．

所感

反復内でを求める方法にある程度の工夫があるものの計算量は大きそう．
実験で用いられているデータセットのサイズも一番大きいもので，COIL( $1024 \times 1440$ )なので，小さなデータセットのような気がする．（大規模データには使えなさそう）
実験に計算時間の話が載っていないのが非常に怖い．

次元縮約はある程度勉強しているつもりだが，特徴選択はあまり触れていなかったので，いい勉強になった，比較手法についてもまとめたい．

北の大地から

北大でひっそりと研究

Unsupervised Feature Selection with Adaptive Structure Learning(KDD 2015)を読んだ