近傍成分分析 (NCA) 特徴選択

近傍成分分析 (NCA) は、特徴量を選択するためのノンパラメトリックな手法であり、回帰および分類アルゴリズムの予測精度を最大化することを目的とします。Statistics and Machine Learning Toolbox™ の関数 fscnca および fsrnca は、正則化がある NCA 特徴選択を実行することにより、目的関数を最小化するための特徴量の重みを学習します。目的関数では、leave-one-out 分類または回帰の平均損失を学習データに対して評価します。

分類の場合の NCA 特徴選択

学習セットに n 個の観測値が含まれているマルチクラス分類問題について考えます。

$$\begin{array}{l}S=\left\{\left(x_i,y_i\right),i=1,2,\dots ,n\right\}\hfill \end{array},$$

ここで、$$x_i\in {ℝ}^p$$ は特徴ベクトル、$$y_i\in \{1,2,\dots ,c\}$$ はクラス ラベル、c はクラスの数です。目的は、特徴ベクトルを受け入れて $$f:{ℝ}^p\to \{1,2,\dots ,c\}$$$$f\left(x\right)$$ の真のラベル $$y$$ に対する予測 $$x$$ を行う分類器の学習です。

次のようなランダム化された分類器があるとします。

• $$x$$ の ‘基準点’ として点 $$\text{Ref}\left(x\right)$$ を $$S$$ から無作為に選択する。

• 基準点 $$\text{Ref}\left(x\right)$$ のラベルを使用して $$x$$ にラベルを付ける。

この方法は、次の点 $$x$$ の最近傍になるように基準点が選択される 1-NN 分類器の方法に似ています。NCA では基準点は無作為に選択され、$$S$$ のすべての点は何らかの確率で基準点として選択され得ます。点 $$P\left(\text{Ref}\left(x\right)=x_j|S\right)$$ が $$x_j$$ の基準点として $$S$$ から選択される確率 $$x$$ は、次のような距離関数 $$x_j$$ で測定した場合に $$x$$ が $$d_w$$ に近いほど大きくなります。

$$d_w(x_i,x_j)={\displaystyle \sum _{r=1}^p{w}_r^2}\left|x_{ir}-x_{jr}\right|,$$

$$w_r$$ は特徴量の重みです。次のように仮定します。

$$\begin{array}{l}P\left(\text{Ref}\left(x\right)=x_j|S\right)\propto k\left(d_w\left(x,x_j\right)\right)\hfill \end{array},$$

ここで、$$k$$ は $$d_w\left(x,x_j\right)$$ が小さい場合に大きい値になると仮定される何らかのカーネル関数または類似度関数です。[1]で提案されているように、次のようになっているとします。

$$k\left(z\right)=\exp \left(-\frac{z}{\sigma }\right),$$

$$x$$ の基準点は $$S$$ から選択されるので、すべての j について $$P\left(\text{Ref}\left(x\right)=x_j|S\right)$$ を合計すると必ず 1 になります。したがって、次のように記述できます。

$$\begin{array}{l}P\left(\text{Ref}\left(x\right)=x_j|S\right)=\frac{k\left(d_w\left(x,x_j\right)\right)}{{\displaystyle \sum _{j=1}^{n}k}\left(d_w\left(x,x_j\right)\right)}\hfill \end{array}.$$

次に、このランダム化された分類器の leave-one-out 適用について考えます。つまり、学習セット $$S$$ から点 $$\left(x_i,y_i\right)$$ を除外した $$S^{-i}$$ のデータを使用して $$x_i$$ のラベルを予測します。点 $$x_j$$ が $$x_i$$ の基準点として選択される確率は次のようになります。

$$p_{ij}=P\left(\text{Ref}\left(x_i\right)=x_j|S^{-i}\right)=\frac{k\left(d_w\left(x_i,x_j\right)\right)}{{\displaystyle \sum _{j=1,j\ne i}^{n}k}\left(d_w\left(x_i,x_j\right)\right)}.$$

正しい分類の平均 leave-one-out 確率は、ランダム化された分類器が $$p_i$$ を使用して観測値 i を正しく分類する確率 $$S^{-i}$$ です。

$$\begin{array}{l}{p}_i={\displaystyle \sum _{j=1,j\ne i}^{n}P\left(\text{Ref}\left(x_i\right)=x_j|S^{-i}\right)I\left(y_i=y_j\right)}\hfill \end{array}={\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}}{y}_{ij},$$

ここで

$$y_{ij}=I\left(y_i=y_j\right)=\{\begin{array}{cc}1& \text{if}{y}_i=y_{j,}\\ 0& \text{otherwise}\text{.}\end{array}$$

ランダム化された分類器を使用した正しい分類の平均 leave-one-out 確率は、次のように記述できます。

$$F\left(w\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{p}_i}.$$

$$F\left(w\right)$$ の右辺は重みベクトル $$w$$ に依存します。近傍成分分析の目標は、$$F\left(w\right)$$ に関して $$w$$ を最大化することです。[1]で紹介されているように、fscnca は正則化された目標関数を使用します。

$$\begin{array}{ll}F\left(w\right)\hfill & =\frac{1}{n}{\displaystyle \sum _{i=1}^n{p}_i-\lambda {\displaystyle \sum _{r=1}^p{w}_r^2}}\hfill \\ \hfill & =\frac{1}{n}{\displaystyle \sum _{i=1}^n\underset{F_i\left(w\right)}{\underbrace{\left[{\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}{y}_{ij}-\lambda {\displaystyle \sum _{r=1}^p{w}_r^2}}\right]}}}\hfill \\ \hfill & =\frac{1}{n}{\displaystyle \sum _{i=1}^n{F}_i\left(w\right)}\hfill \end{array},$$

ここで、$$\lambda$$ は正則化パラメーターです。正則化項により、$$w$$ の重みの多くは 0 になります。

$$p_{ij}$$ のカーネル パラメーター $$\sigma$$ として 1 を選択すると、重みベクトル $$w$$ を求める問題は、与えられた $$\lambda$$ に対する次のような最小化問題として表すことができます。

$$\widehat{w}=\underset{w}{\text{argmin}}f\left(w\right)=\underset{w}{\text{argmin}}\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(w\right)},$$

ここで、f(w) = -F(w) および f_i(w) = -F_i(w) です。

ここで

$$\frac{1}{n}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}}}=1,$$

また、目的関数に定数を加算しても最小値の引数は変化しないことに注意してください。したがって、定数 1 を加算して目的関数を書き直すことができます。

$$\begin{array}{c}\widehat{w}=\underset{w}{\text{argmin}}\left\{1+f(w)\right\}\\ =\underset{w}{\text{argmin}}\left\{\frac{1}{n}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}}}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}{y}_{ij}}+\lambda {\displaystyle \sum _{r=1}^p{w}_r^2}}\right\}\\ =\underset{w}{\text{argmin}}\left\{\frac{1}{n}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}\left(1-y_{ij}\right)}+\lambda {\displaystyle \sum _{r=1}^p{w}_r^2}}\right\}\\ =\underset{w}{\text{argmin}}\left\{\frac{1}{n}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}l(y_i,y_j)}+\lambda {\displaystyle \sum _{r=1}^p{w}_r^2}}\right\},\end{array}$$

ここで、損失関数は次のように定義されます。

$$l\left(y_i,y_j\right)=\{\begin{array}{cc}1& \text{if}{y}_i\ne y_{j,}\\ 0& \text{otherwise}\text{.}\end{array}$$

最小値の引数は、分類誤差を最小化する重みベクトルです。fscnca の呼び出しで名前と値のペアの引数 LossFunction を使用することでカスタムな損失関数が指定できます。

回帰の場合の NCA 特徴選択

関数 fsrnca は、回帰用に修正された NCA 特徴選択を実行します。n 個の観測値が与えられています。

$$\begin{array}{l}S=\left\{\left(x_i,y_i\right),i=1,2,\dots ,n\right\}\hfill \end{array},$$

分類問題との違いは、応答値 $$y_i\in ℝ$$ が連続的であるということだけです。この場合、目標は与えられた学習セット $$S$$ に対する応答 $$y$$ の予測です。

次のようなランダム化された回帰モデルがあるとします。

• $$x$$ の ‘基準点‘ として点 ($$\text{Ref}\left(x\right)$$) を $$S$$ から無作為に選択する。

• $$x$$ における応答値を基準点 $$\text{Ref}\left(x\right)$$ の応答値と等しい値に設定する。

この場合も、点 $$x_j$$ が $$x$$ の基準点として $$S$$ から選択される確率 $$P\left(\text{Ref}\left(x\right)=x_j|S\right)$$ は次のようになります。

$$\begin{array}{l}P\left(\text{Ref}\left(x\right)=x_j|S\right)=\frac{k\left(d_w\left(x,x_j\right)\right)}{{\displaystyle \sum _{j=1}^{n}k}\left(d_w\left(x,x_j\right)\right)}\hfill \end{array}.$$

次に、このランダム化された回帰モデルの leave-one-out 適用について考えます。つまり、学習セット $$S$$ から点 $$\left(x_i,y_i\right)$$ を除外した $$S^{-i}$$ のデータを使用して $$x_i$$ の応答を予測します。点 $$x_j$$ が $$x_i$$ の基準点として選択される確率は次のようになります。

$$p_{ij}=P\left(\text{Ref}\left(x_i\right)=x_j|S^{-i}\right)=\frac{k\left(d_w\left(x_i,x_j\right)\right)}{{\displaystyle \sum _{j=1,j\ne i}^{n}k}\left(d_w\left(x_i,x_j\right)\right)}.$$

$$x_i$$ の、ランダム化された回帰モデルが予測する応答値を $${\widehat{y}}_i$$、実際の応答を $$y_i$$ とします。また、$${\widehat{y}}_i$$ と $$y_i$$ の相違を測定する損失関数を $$l:{ℝ}^2\to ℝ$$ とします。すると、$$l\left(y_i,{\widehat{y}}_i\right)$$ の平均値は次のようになります。

$$l_i=E\left(l\left(y_i,{\widehat{y}}_i\right)|S^{-i}\right)={\displaystyle \sum _{j=1,j\ne i}^n{p}_{ij}l\left(y_i,y_j\right).}$$

正則化項を加算すると、最小化のための目的関数は次のようになります。

$$f\left(w\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{l}_i+\lambda {\displaystyle \sum _{r=1}^p{w}_r^2}}.$$

回帰の場合の NCA 用の既定の損失関数 $$l\left(y_i,y_j\right)$$ は平均絶対偏差ですが、fsrnca を呼び出すときに名前と値のペアの引数 LossFunction を使用すると、カスタム関数を含め、他の損失関数を指定できます。

標準化の影響

正則化項により、無関係な予測子の重みがゼロになります。分類用または回帰用の NCA の目的関数では、すべての重みについて正則化パラメーターは $$\lambda$$ の 1 つだけです。これは、重みの大きさが互いに比較可能であることを必要とします。$$x_i$$ の特徴ベクトル $$S$$ のスケールが異なる場合、別スケールの重みとなり、無意味になる可能性があります。この状況を回避するには、NCA の適用前に、ゼロ平均と単位標準偏差をもつように予測子を標準化します。予測子は、fscnca または fsrnca の呼び出し時に名前と値のペアの引数 'Standardize',true を使用して標準化できます。

正則化パラメーターの値の選択

正則化パラメーターの値は通常、独立の検定セットにおけるランダム化された NCA 分類器または回帰モデルの精度の計算によって選択する必要があります。単一の検定セットではなく交差検証を使用する場合は、交差検証分割全体で平均損失が最小になる $$\lambda$$ の値を選択します。例については、分類に NCA を使用して特徴量を判別するための正則化パラメーターの調整と回帰用の NCA の正則化パラメーターの調整を参照してください。

参照

[1] Yang, W., K. Wang, W. Zuo. "Neighborhood Component Feature Selection for High-Dimensional Data." Journal of Computers. Vol. 7, Number 1, January, 2012.

参考

fscnca | fsrnca | FeatureSelectionNCAClassification | FeatureSelectionNCARegression

関連するトピック

• 回帰に NCA を使用するロバスト特徴選択
• 分類に NCA を使用して特徴量を判別するための正則化パラメーターの調整
• 特徴選択の紹介