Nonnegative Sparse Linear Discriminant Analysis

物理的な意味解釈が可能な特徴量ベクトルを次元圧縮したいときには，非負な変換を使って次元圧縮を使うのが良い．非負な変換を使わないと，物理的意味解釈ができなくなってしまう．それから，次元圧縮後のデータの意味づけがしやすくなるという点で，スパースな変換だとなお良い．

NonnegativeでSparseな次元圧縮法の一つに，Nonnegative Sparse PCA*1(NSPCA)がある．

NSPCAの前に，普通のPCAを復習する． $d$ 次元の特徴量を $n$ 個並べた行列を $X \in R^{d\times n}$ ， $k$ 次元への圧縮を実現する求めるべき変換行列を $U \in R^{d\times k}$ とすると，PCAでは
$\max_U{||U^T X||^2_F}$ 　（ $U^TU = I$ ， $||\cdot||^2_F$ はフロベニウスノルム）
を解くことになる．これは解析解がもとまって，結論は $X$ の分散共分散行列を固有値分解し，固有値の大きいものから対応する固有ベクトルを並べたもの，が求めるべき $U$ である．

NSPCAは，上で書いた最大化問題に，非負の制約条件と，スパースにするための正則化項を加え，さらに $U^TU = I$ をrelaxしたもので，
$\max_U{||U^T X||^2_F} - \alpha ||I-U^TU||^2_F - \beta||U||_{L_0}$ 　（ただし $U \ge 0$ ， $||\cdot||_{L_0}$ はL0ノルム， $\alpha,\beta$ は超パラメータ）
を解く問題になる．ここで，一つ目の項はPCAと同じ項，二つ目の項が $U^TU = I$ をrelaxしたもの，三つ目の項がスパース正則化項である．この問題はPCAと違って，大域最適解を求めるのがNP-hardなので，なんらかのアルゴリズムを使って局所最適解を探索しなければいけない．

＊1の論文で提案されている探索アルゴリズムは，以下の通りである．上の式は， $U$ の要素 $u_{rs}$ に関する4次方程式 $f_{rs}$ の和に分解できて，
$\max_U \sum_{r,s}f_{rs}(u_{rs})$
という形に変形できる． $f_{rs}(u_{rs})$ は $U$ の各要素の4次方程式なので， $u_{rs}$ 以外の $U$ の要素がfixされていれば， $u_{rs}(\ge 0)$ に関して最大化することができる（微分して0になってかつ正となる $u_{rs}$ と， $u_{rs} = 0$ のうち，一番 $f_{rs}(u_{rs})$ が大きくなるものを選べばよい）．そこで，最初に適当な $U$ の初期値を決め，この最適化を $r,s$ を変えながら収束するまで繰り返せば，局所最適解がみつけられる．

さて，NSPCAはこれでよいのだが，同じような感じでノンネガティブでスパースなLDAはできないのだろうか？と思って，Google先生に聞いてみたのだが，以外に論文がみつからない（だれか知ってたら教えてください，，，）．

一番単純には，NSPCAのアルゴリズムの最大化の式をLDA用に変更して
$\max_U{\frac{\det{(U^T S_b U)}}{\det{(U^T S_w U)}}} - \alpha ||I-U^TU||^2_F - \beta||U||_{L_0}$ 　（ただし $U \ge 0$ ）
とするのが考えられる．途中の数値計算はNSPCAよりだいぶハードになるが，できないわけではない？？
やる気と根気が続けば，実装してうまくいくか確かめてみようかな．．．

*1: Ron Zass and Amnon Shashua, ``Nonnegative Sparse PCA,'' http://www.cs.huji.ac.il/~shashua/papers/spca-nips06.pdf