情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

条件付きエントロピー最小化に基づく教師付き次元削減手法

Supervised Dimensionality Reduction by Conditional Entropy
Minimization
日野英逸∗
Hideitsu Hino

村田昇†
Noboru Murata

Abstract: データが有する本質的な情報を失うことなくデータの次元を削減することは情報処理における重要な課題である. 学習データにクラスラベルが付随している教師付き次元削減手法としては, Fisher Discriminant Analysis(FDA) が広く用いられている. しかし, FDA
による次元削減で得られる判別曲面は非常に限定された理想的状況においてのみ最適であり,実際上も適切な判別曲面が得られないことが多い. 本報告では, 情報論的な観点から教師付
き次元削減問題を捉え, 条件付きエントロピー最小化に基づく次元削減の枠組みを提案する.
推定した条件付きエントロピーの最小化を勾配法により実行し, 可視化及び判別問題への適用結果を記す. さらに, カーネル法を用いた非線型教師付き次元削減への拡張も試みる.

Keywords: dimensionality reduction, conditional entropy, classiﬁcation, visualization

1

まえがき
情報処理の重要な目的の一つとしてデータの縮約, あ

るいはコンパクトな表現がある. 特に, 情報処理の対象として画像, 音声, テキスト, 遺伝子発現データなど, 極めて高次元なデータを扱う場合, 本質的な情報を保持したまま次元を低減することは必須である. 次元削減により, 後に続く判別やクラスタリングといった処理が高速に実現でき, また, データを低次元で表現することで可視化も可能となる.
教師無しの線型次元削減手法としては, 主成分分析[1](Principal Component Analysis:PCA) が代表的である. 一方, 代表的な教師付き線型次元削減手法として,
Fisher の判別分析 [2](Fisher Discriminant Analysis:FDA)がある. FDA は, 特徴データとそのクラスラベルが観測された状況で, クラス内のデータの分散を小さく保ちつつ, クラス間の分散が大きくなるような方向への特徴
データの射影を求める手法である.
各クラスのデータが共分散構造の等しい正規分布に従っている時は, FDA は最適なクラス分離を与える方向を発見することができる. しかし, 多くの問題では正規性の仮定は成り立たず, 判別性の高い射影を得ることが∗ 早稲田大学, 169-8555, 東京都新宿区大久保 3-4-1 tel. 03-5286-

3383, e-mail hideitsu.hino@toki.waseda.jp,
Waseda University, 3-4-1 Ohkubo, Shinjuku, Tokyo 169-8555,
Japan† e-mail noboru.murata@eb.waseda.ac.jp

できないことがある. FDA の自然な拡張として, 同一のクラスに属するデータ同士の類似度を考慮した, Local

Fisher Discriminant Analysis(LFDA) が提案されている [3]. これはデータの局所性をデータ間の類似度行列という形で導入するものであり, 判別の前処理として用いた場合に FDA を大きく上回る判別精度が得られると報告されている.
本報告では, 情報論的観点から次元削減問題にアプロー
チする. 上述の代表的な次元削減手法をエントロピーの観点から理解し, 続いて次元削減のための目的関数として条件付きエントロピーが自然であることを論じる. 提案する手法は, データの分布を仮定せず, ノンパラメト
リックにデータの密度推定を行った上でクラス条件付き
エントロピーを最小化するような変換を探索するものであり, FDA における最適性の仮定から大きく外れたデー
タに対してもよい結果が期待できる.
以下, 本報告の構成を記す. 第 2 節において, 線型次元
削減問題を定式化し, その情報論的な解釈を与える. 第 3
節では, 条件付きエントロピーが情報論的に自然な次元削減の基準となることを示す. エントロピーの推定と最適化に用いるカーネル密度推定にも言及する. 条件付き
エントロピー最小化による次元削減を提案し, 人工デー
タを用いた実験により, FDA がうまく働かない状況においても提案手法が最適な射影方向を発見できる例を示
す. 第 4 節では, 条件付きエントロピーを変形すること

により, 提案手法が教師付き次元削減 (より一般には特な変換を求める. ただし,

徴抽出) 手法として機能する原理を考察する. 第 5 節ではベンチマークデータセットを用いて, 多クラスデータ

Σw=に対する可視化の例と, 提案手法によって得られた低次元特徴空間における判別実験の結果を示す. 第 6 節では,
提案手法の非線型次元削減への拡張を検討する.

2n
データ {xi }N
i=1 , xi ∈ R が与えられたときに, これを m 次元ベクトル f (xi ) = zi ∈ Rm , (m < n) に変換
する次元削減問題を考える. 線型の次元削減の場合には,変換 f は行列 A によってzi = A x i ,

x∈Dy

Σb

1
Ny (µy − µ)(µy − µ)T ,N y=1

Σy は Dy に属するデータの平均と共分散行列, µ は全てのデータの平均を表す. 以上の準備の下, FDA は,log |AT Σw A|/|AT Σb A| を最小化する変換 A を求めることと理解される. ただし, | · | で行列の行列式を表す
ものとする. ここで, log の中身の分母, 分子を定数倍

A∈R

n×m

.

(1)

してもこの目的関数の値は変わらないことから, 通常は|AT Σb A| を一定に固定した上での最小化問題

で記述できる. ここでは, 次元削減手法をエントロピー

min log |AT Σw A| subject to |AT Σb A| = const.

の観点から考察する. 本稿で用いるエントロピーとは,(Shannon) 微分エントロピーを意味し, 確率変数 X に対して,∫H(X) = −=C∑であり, Dy はクラス y に属するデータの集合, µy と次元削減手法の情報論的理解

T

C
C
∑
Ny
1 ∑ ∑
(x − µy )(x − µy )T =
Σy ,
N y=1
N
y=1

p(x) log p(x)dx

A

(4)
を解く.
データが各クラスで同一の共分散行列 Σy = Σc , y =(2)

1, . . . , C を持つ正規分布に従う場合には, FDA によってBayes 最適な判別曲面が得られることが知られている.

で定義される. ただし p は X の密度関数である.
教師無し次元削減手法として広く用いられている PCA

この理想的な状況では Σw = Σc であり, 従っては, データを低次元に射影したときに分散ができるだけ大きくなるような射影軸を求める手法である. これは,H(AT X|Y ) =log(2π)m/2 e +データが正規分布に従うという条件下で, もとのデータの情報量 − log p(x) を平均としてできるだけ保つよう

log |AT Σy A|

1
log |AT Σc A|
2
1= log(2π)m/2 e + log |AT Σw A|
2

正規分布 N (x; µ, σ 2 ) の平均情報量, すなわちエントロ

から FDA における log |AT Σw A| の最小化はクラス条件

∫ ∞

1
−
p(x) log p(x)dx = log(2πeσ 2 )
2
−∞

2N
y=1

= log(2π)m/2 e +な低次元構造を抽出することに相当する. 実際, 1 次元
ピーは

C
∑
Ny

(3)

付きエントロピーの最小化と等価である.
以上より, 教師無しの代表的な次元削減手法であるとなり, 分散 σ 2 が大きいことはエントロピーが大きい

PCA は, データ分布の正規性の仮定の下でエントロピー

ことと等価である. PCA ではラベル情報が利用できなを最大にするように変換をすることで特徴を抽出しよういので, 判別のための射影軸の決定ではなく, 情報量をとするものであり, 教師付きの代表的な次元削減手法で保存することでデータの特徴を最もよく捉えると考えらある FDA は, データが各クラスで同一の共分散行列をれる射影軸を定めている.

持つ正規分布に従うという仮定の下で, 条件付きエント

一方, 教師データが与えられている状況では, データ

ロピーを最小にすることで特徴を抽出するものであるこ

x が属するクラスラベルを用いた判別的な次元縮約として, FDA がよく利用される. FDA は, データ {xi }N
i=1とそのクラスラベル {yi }N
,
y
∈
{1,
2,
.
.
.
,
C}
が与え
i
i=1

とがわかる. 本節における考察を踏まえて, 次節では条件付きエントロピー最小化を基準とした教師付き次元削減方法を提案する.

られたときに, 最もクラス判別が容易になる小数個の射影軸を求める手法である. データ x ∈ Rn を式 (1) の3

提案する枠組みように変換するとして, 変換後のデータのクラス間分散

データのクラスラベルが与えられている教師付き学習AT Σb A とクラス内分散 AT Σw A の比が最大になるようの枠組みにおいて, データの低次元空間での表現としては, 類似したデータ同士がコンパクトにまとまっていることが望ましい. データを x から z に変換してコンパ

ピーをクトな表現を得ることを考えると, 相互情報量

I(X; Z) = H(Z) − H(Z|X)

H(X) ≈ H̃(X) = −E[log p̂(X; D, h)](5)が小さいほど圧縮性の高い良い変換であるといえる [4].

のように近似し, さらに p̂(x; D, h) を p̂(xj ; D\{xj }, h)で置き換えて, LOO 法によって期待値の計算を学習の際, クラスラベル y などの情報が利用できる教師
付き学習の枠組みでは, 教師データ y で条件付けた場合

I(X; Z|Y ) = H(Z|Y ) − H(Z|X, Y )1 ∑log p̂(xj ; D\{xj }, h) (10)N j=1
NH̃(X) ≈ Ĥ(X) = −にデータがコンパクトに表現できればよく, このときは,変換の良さの尺度として条件付き相互情報量(9)のように近似する. 以下ではエントロピーを上式で推定(6)することとして, 推定値であることを表す ˆ· は省略する.
多次元確率変数の密度推定及び結合エントロピーのを考えるのが自然である. さらに, データの変換 f : x 7→

推定も, 上述のようにカーネル密度推定を介して行うこz が確定的な場合を考えているので H(Z|X, Y ) は 0 になり, H(Z|Y ) が小さいことが, 教師付きの枠組みにおとができる. しかし, 十分な精度で多次元の密度推定を行うことは困難であるため, ここでは, 多次元のデータ

ントロピー H(Z|Y ) を変換 f : x 7→ z に関して最小化す

z ∈ Rm の結合エントロピーの推定をするのではなく, 変換された特徴量ベクトルの各次元での周辺エントロピー

ることで次元削減のための変換を学習するというのが提の和で与えられる上界を求め, それを最小化する [4]. つ

案する枠組みである. ただし, H(Z|Y ) は全てのデータ

まり, 変換行列 A の第 l 列のベクトル al によって射影x を一点に写像する f によって最小化される. また, 変される第 l 次元特徴量に関する周辺エントロピー∫T
Hl (al X) = Hl (Zl ) = − p(zl ) log p(zl )dzl

けるコンパクトなデータ表現の基準となる. 条件付きエ換関数 f の自由度が高い場合には与えられた学習データに過度に適合する可能性もある. こうした問題を避けるために, 実際上は何らかの制約条件が必要となる. ここの和が, 結合エントロピーの上界

では一般に, 制約の強さを表すパラメタ ε と, 変換関数

f 及び学習データ D に依存して定まる制約関数 Ψ(f, D)

H(Z) =

を用いて, 制約項を εΨ(f, D) で表現する. 従って,min H(Z|Y ) + εΨ(f, D)

f :x7→z(7)の具体的な形状は対象とする問題に応じて適切に定める必要がある.
まずは, 線型変換 A ∈ R

について式 (7) の最小化問題を考える. エントロピーの最小化のために, Gaussian(11)を与えるので, 各次元の周辺エントロピー Hl (aTl X) を al
に関して最小化することで, 目的関数である結合エントロ
ピーを近似的に最小化する. また, このエントロピーをク∑m
ラス別に計算したものを H(Z|Y = y) = l=1 Hl (Zl |Y =y) として, これをクラス事前確率 (各クラスのデータ数と全データ数の比で推定) で重みを付けて加えたものがH(Z|Y ) の上界

カーネル密度推定に基づくエントロピーの推定を行う. エH(Z|Y ) =ントロピー推定の方法は数多くあるが, ここでは, Leave-

N
(
)
1 ∑
1
√
exp −||x − xi ||2 /2h22
N i=1 2πh(8)1で推定する . その上で, 一次元のエントロピーの近似を以下のように行う. 推定した密度を用いてエントロ
1 写像 f に関する最適化を繰り返すことで, 変換後のデータの密度推定に適したバンド幅は変わっていくため, バンド幅の推定方法は高速に行えることが必要である. カーネルのバンド幅 h は, “Silverman’s
Rule of Thumb” と呼ばれるヒューリスティックな方法を用いて推定した [6].

C∑

p(y)H(Z|Y = y)y=1

One-Out(LOO) に基づく方法を採用した [5]. まず, デー
タ D = {xi }N
i=1 が与えられたとき, x の密度をp̂(x; D, h) =Hl (Zl ) ≥ H(Z)l=1なる最適化問題を考えることになる. 制約関数 Ψ(f, D)

n×m

m
∑

=

C
∑
y=1

p(y)

m
∑

Hl (Zl |Y = y)

(12)

l=1

である. 以下では, 多次元のエントロピーを実際に最小化する際には各次元に関する周辺エントロピーの和を最小化するものとする.

3.1

勾配法による最適化

条件付きエントロピーの近似を, A に関する勾配法で最小化する. 周辺エントロピーの和を最適化するので,変換行列 A の第 l 列を al として, 変換特徴量 aTl x =AT A = EDE T で表すと, 上記の step.1 によってzl , l = 1, 2 . . . , m についての周辺エントロピーの勾配を求めてから, A の各列毎に更新を行った.

min H(AT X|Y ) + εΨ(A, D)
A

=

(13)

あり, AT A の変換後の固有値を {h(di )}m
i=1 とすると

Nyy に属するデータ集合を Dy = {xj }j=1
, y = 1, . . . , Ch(di ) = 41 (9di − 6d2i + d3i ) となる. 従って, h(di ) − di =として, 条件付きエントロピーは=di2
4 {(di − 3) − 4} ≥ 0 より h(di ) ≥ di が成立するので,
T

C
∑

Ny
H(AT X|Y = y)
N
y=1

= −

C
∑
1

N

y=1

∑

1
(3A − AAT A)T (3A − AAT A)
4(
)
6
1
9
E
D − D2 + D3 E T
444となる. A の各列は正規化してあるので di ∈ [0, 1] でである. ただし, 全データ集合を D = {xi }N
i=1 , 各クラス

H(AT X|Y )

7→

AT A

解くべき最適化問題は

A A の固有値は 1 に収束する.

人工データを用いた実験結果

3.2

log p̂(A xj ; Dy \{xj }, h)T

xj ∈Dy

図 3.2 に, 2 種類の 2 クラスデータを用いて, FDA 及び提案手法を用いて求めた判別軸を示す. 2 クラス判別で計算される. H(AT X) の A の第 l 列 al に関する条件問題なので, FDA により射影軸が 1 つ得られる. 提案手付き周辺エントロピーの導関数は法では, 変換 A = a を 2 次元ベクトルとして学習することで, FDA と同様に射影軸が 1 つ得られる. 点線が∂H(aTl X|Y )
=
∂al

∑

xj ∈Dyられた a で射影される軸である. 各クラスが単峰性の分

vji

«
„
||aT x −aT x ||2− l j2h2l i,xi ∈Dy \{xj } e3xi ∈Dy \{xj } e

LDA
minH

vji = (xj − xi ) al · (xj − xi ) ∈ Rn

1
2nd axis

−1
−2

−3

化が行える.

3.1.1

−3

−2

−1

ために後述の準直交化を繰り返すことで式 (13) の最適0であり, 制約条件なしの勾配法と, 近似的な制約充足の2nd axis

1

2

LDA
minH

2

T

−3

準直交化

0

1
h2 N y=1∑«„||aT x −aT x ||2− l j2h2l i

∑

3

C
∑

FDA による判別軸で, 実線が H(aT X|Y ) の最小化で得

−2

−1

0

1

2

3

−3

−2

−1

1st axis

周辺エントロピーで結合エントロピーの上界を最小化(a) Unimodal data.

0

1

2

3

1st axis(b) Multimodal data.

する場合, 各周辺エントロピーを個別に最小化しても, 単
一の方向ベクトルしか得られない. そこで準直交化 [7] を

図 1: Discriminative axes found by FDA and proposed

各ステップで行い, 勾配法の各ステップにおいて, 射影しmethod.

た各次元でのデータ aT1 x, . . . , aTm x を無相関化する. つ布に従うような単純な場合 (a) には, FDA と提案手法はまり, データ {xi }N
i=1 は白色化してあるとして, 周辺エンほぼ同一の射影軸を与える. 一方, 同クラスで modality

トロピーの最小化の途中で得られている行列 A ∈ Rn×m

が二つある場合 (b) では, 提案手法が優れた結果を与え

を, ||AT A − Im ||F を近似的に満たすように修正する. こていることがわかる.

こで Im は m × m の単位行列であり, || · ||F は行列のフロベニウスノルムである. すなわち, 式 (13) における制約関数を Ψ(A, D) = Ψ(A) = ||AT A − Im ||F と定めたことになる. この準直交化は, 次の 2 つの操作を適当な回数繰り返すことで行われる:

1.

A ← 32 A − 12 AAT A.

2. A の各列のノルムを 1 に正規化.

4

提案手法の正当性の検討
H(Z|Y ) を書き換える事で, なぜ条件付きエントロピーの最小化アプローチがうまくいくのかを再考する. まず, 確率変数 X のネゲントロピー [8] に注目する. ネ
ゲントロピー及び条件付きネゲントロピーは, それぞれJ(Z) = HG (Z)−H(Z), J(Z|Y ) = HG (Z|Y )−H(Z|Y )で定義される. ただし, HG (Z) は, p(z) と同じ共分散構

実際, 対称行列 AT A の対角化を, 直交行列 E ∈ Rm×m

造を持つ正規分布のエントロピーである. このネゲント

A の固有値 {di }mi=1 を並べた対角行列 D を用いてロピーを用いると, z = AT x とクラスラベル y の相互とAT情報量が次のように変形できる:I(Z; Y )項の最適化はクラス判別に大きく寄与することが理解できる.

= H(Z) − H(Z|Y )= {HG (AT X) − HG (AT X|Y )}−{J(AT X) − J(AT X|Y )}1|AT ΣA|=log ∏CTp(y)2y=1 |A Σy A|

5

実験

5.1

多クラスデータの可視化

まず, 提案手法の可視化への適用例を示す. ここで,条件付きエントロピーを直接最小化するのではなく, 式−{J(AT X) − J(AT X|Y )}.

(14) の最小化によっても理論的には同じ効果があるは
ただし, Σ, Σy はそれぞれ全データの共分散行列, クラスずである. その実証のために, ここでは式 (14) の各項のy に属するデータの共分散行列であり, p(y) はクラス事
前確率である. 従って, 最小化の目的である H(Z|Y ) は,勾配を計算し, 勾配法による最適化によって実データのH(Z|Y ) = H(A X) + {J(A X) − J(A X|Y )}|AT ΣA|1− log ∏CTp(y)2
y=1 |A Σy A|

比べて計算量は大きくなるので, 式 (14) の最適化は本節= HG (AT X) − J(AT X|Y )|AT ΣA|1− log ∏CTp(y)2
y=1 |A Σy A|

しか判別軸を得ることができないため, 3 クラス以上の

T

T

T

次元削減を行う. 当然, 直接 H(Z|Y ) を最小化するのとの実験のみにとどめる. また, FDA による可視化も行う
が, C をクラス数としたとき, FDA では C − 1 次元まで
データセットを用いる. データは UCI レポジトリから,(14)

Iris と Soybeans データを利用した. それぞれ, 4 次元 3
クラス, 22 次元 3 クラスのデータである.

の 3 項に分ける事ができる.

4.1

全データが正規分布に従うとした時の全データのエントロピー

変形した条件付きエントロピーである式 (14) の第一
項 HG (AT X) は, データ全体が正規分布に従うとした場
合のエントロピーである. これは全データの共分散行列の行列式で完全に決まる項であり, この項を小さくする(a) Iris:FDA(b) Iris:Proposal(c) Soybean:FDA(d) Soybean:Proposal

ことは, データ全体をコンパクトに表現することにつながる. ただし, データのスケール変換によりいくらでも小さくなる項であり, 判別性には関係しない. 従って, 変換の正規化 (直交化など) を行うという状況では, 本質的にはこの項は影響しない.

4.2

条件付きネゲントロピー

第二項に現れる (条件付き) ネゲントロピーは, 主に

図 2: Visualization result of multidimensional data.

独立性分分析の分野において正規分布からの離れ具合の指標として用いられている [8]. 式 (14) の最適化によりJ(AT X|Y ) が大きくなることで, クラスラベルで条件付けたときにネゲントロピーが大きくなるようにデータが分布することになる. つまり条件付けすることでデータの構造がより顕著に現れる (特徴的な構造が現れる) よ
うにデータを変換していることに相当する.

4.3

クラス内分散が一定でない判別分析規準

どちらのデータに対しても, クラスがよく分離される
ような 2 次元への射影が得られていることがわかる.

5.2

One-nearest-neighbor 法による判別

データの分離性を測る指標はいくつもあるが, ここでは単純に, one-nearest-neighbor 法 [10] で判別した場合の誤判別率を用いる. 実験には, IDA データセット2 を用いた. 表 1 に, 利用したデータセットの名称, 特徴量式 (14) の第三項は, 各クラスの分散構造及び事前分
布が異なる状況での線型判別分析 (Heteroscedastic dis-

criminant analysis;[9]) の目的関数そのものであり, この

2 以前は
http://ida.ﬁrst.fraunhofer.de/projects/bench/benchmarks.htm
から入手可能であったが, 現在は公開されていない

表 2: Misclassiﬁcation rate of linear methods.
Data namebananabreast-cancer
diabetes
ﬂare-solar
germanheart
image
ringnorm
splicethyroidtitanic
twonorm
waveformmin H(Z|Y )13.64(0.765)[2]33.90(4.704)[5]31.98(4.703)[7]36.50(1.936)[4]34.91(3.024)[7]27.68(3.909)[7]5.72(1.712)[7]20.25(1.303)[7]31.36(6.958)[2]
4.674(2.535)[5]22.510(1.107)[1]
3.359(0.4241)[13]
24.76(3.167)[7]LFDA
13.7(0.8)
34.7(4.3)
32.0(2.5)
39.2(5.0)
29.9(2.8)
21.9(3.7)
3.2(0.8)
21.1(1.3)
16.9(0.9)
4.6(2.6)
33.1(11.9)
3.5(0.4)
12.5(1.0)

次元, 学習データとテストデータの数と, 学習/テスト

FDA
38.34(3.966)
34.91(5.076)
31.32(2.813)
36.42(1.875)
32.03(2.577)
22.93(4.105)
22.12(0.860)
31.72(1.016)
20.35(0.783)
17.92(4.888)
22.53(1.066)
3.54(0.496)
18.61(1.162)

PCA
13.99(0.849)[2]40.71(7.085)[3]38.44(5.019)[4]48.64(6.920)[5]41.83(4.452)[2]
46.27(23.894)[4]37.33(9.546)[2]
28.04(5.075)[10]43.90(4.894)[2]9.05(4.366)[2]26.41(8.392)[1]7.55(18.770)[3]31.69(18.714)[9]Euclidean
13.64(0.761)
32.73(4.824)
30.12(2.051)
36.47(1.880)
29.46(2.469)
23.16(3.735)
3.381(0.540)
35.03(1.362)
28.77(1.524)
4.36(2.210)
22.50(1.057)
6.68(0.718)
15.83(0.654)

しているケースも見られる.

データの組のセット数を示す. PCA 及び提案手法によData namebananabreast-cancer
diabetes
ﬂare-solar
germanheart
image
ringnorm
splicethyroidtitanic
twonorm
waveform

dim
2
9
8
9
20
13
18
20
60
5
3
20
21

train(test) data size
400(4900)
200(77)468(300)
666(400)700(300)
170(100)
1300(1010)
400(7000)
1000(2175)
140(75)150(2051)
400(7000)
1000(1000)

非線型変換への拡張

6

表 1: IDA data speciﬁcations.
set 数
100
100
100
100
100
100
20
100
20
100
100
100
100

非線型変換によって特徴抽出を行い, 次元を削減する
方法を検討する. FDA のカーネル法を用いた非線型化(Kernel Fisher Discriminant Analysis:KFDA) が提案されており [11], 線型分離不可能な複雑なデータに対して有効であることが知られている. 本節では, 提案手法の非線型化を, カーネル法の枠組みで試みる.

6.1

Kernel Fisher Discriminant Analysis

1 次元線型射影関数を, f (x) = aT x で定義する. 多次元への射影は, 射影ベクトル a を列に並べた行列を用いることで実現するものとして, 以下では簡単のためにる変換後のデータの次元は, 各データセットから 5 セッ

1 次元への射影のみを扱う. データ x を何らかの写像 Φト分の学習データを取り出し, それらを用いた 5 foldによって特徴量空間に写像した空間においてデータの判

cross validation によって定めた. 表 2 に, one-nearestneighbor 法による誤判別の平均及び標準偏差 (全て%表記) を示す. 提案手法及び PCA において選択された最適別を行うことを考えると, これは f (x) = aT Φ(x) とな
る. ここで, 一般にカーネル法では適当な正則条件の下で∑N
a = i=1 αi Φ(xi ) と書けることと, 特徴量空間におけな次元 D は表中で [D] のように記した. また, LFDA にる内積を表すカーネル関数 〈Φ(xi ), Φ(xj )〉 = k(xi , xj )よる同一のデータに対する判別結果は [3] より引用した.

を用いると,

提案手法による判別精度は, 多くのデータに対して PCA,

FDA を上回っている. LFDA と比較すると, titanic デー
タのように有意に優れた結果が得られる場合がある一方で, waveform, splice データのように精度が大幅に落ちる場合もあるが, その他の多くのデータに対して同程度の判別力を有していることがわかる. また, 表の最右行(Euclidean) に示した次元削減をしていない特徴量を用いた one-nearest-neighbor 法による判別結果と比較しても, 多くの場合ほとんど判別精度が落ちず, 精度が向上

f (x) =N∑αi k(x, xi )

(15)

i=1

と書き直せる. FDA のカーネル法による非線型化である KFDA は, クラス間分散行列 Σb 及びクラス内分散行
列 Σw をカーネル関数を用いて書き直すことで容易に導出できる. 与えられたカーネル関数に関するデータのグ
ラム行列を K = [k(xi , xj )]ij ∈ RN ×N とする. また, グ
ラム行列から計算されるクラス毎の平均と全データの平αT0 k̄y との二乗誤差を正則化項として用いる. これは,∑C)T
式 (7) において Ψ(f, D) = y=1 (αT k̄y − αT0 k̄y )2 とし
∑ (
N
∈R ,
k(xi , x1 ), · · · , k(xi , xN )たことに相当する. つまり最小化の目的関数は均に対応するベクトルを

k̄y
k̄

=

1
Ny

=

)T
1 ∑ (
∈ RN
k(xi , x1 ), · · · , k(xi , xN )N

xi ∈DyH(f (X)|Y ) + εxi ∈Dとすると, クラス間分散行列 Vb 及びクラス内分散行列
を Vw はそれぞれ

1 ∑Ny (k̄y − k̄)(k̄y − k̄)T ,
N y=1
C

Vb

=

=

上式を最小化する α を求める. 最小化は, 線型の場合と同様に勾配法を採用した. 目的関数 (16) の α に関する導関数は, 条件付きエントロピーの導関数∂H(f (X)|Y )
∂α

i∈Dy

=

となる. ただし ki はグラム行列 K の第 i 列からなるベクル関数を用いた場合, その表現能力の高さから, 過学習を起こす可能性が非常に高い. そこで, 何らかの方法で

C
∑
∑

1
h2 N y=1

xj ∈Dy∑|αT (kj −ki )|2

−
2h2
vji
xi ∈Dy \{xj } e,
T (k −k )|2
|α
j
i
∑
−
2h2
e
xi ∈Dy \{xj }vji = (kj − ki )T α · (kj − ki ) ∈ RN

トルを表す. 以上より, KFDA は log |αT Vw α|/|αT Vb α|
上での最小化問題として定式化される. ただし, カーネ(16)であり, KFDA によって得られた解 α を初期値として,1 ∑∑(ki − k̄y )(ki − k̄y )T
N y=1の最小化問題になり, FDA と同様に αT Vb α を固定した(αT k̄ y − α0 k̄y )2

y=1

C

Vw

C
∑

と, 正則化項の導関数()∂Ψ(f, D)
= 2 (k̄y )T k̄y · α − αT0 k̄y · k̄y∂αから計算できる.

正則化することが重要である. ここではクラス内分散行

One-nearest-neighbor による判別

列を, 正則化項を加えた Vw + ζK で置き換える. ここで

6.3

ζ は適当な正則化パラメタである. 以上より, KFDA は次の最小化問題として定式化される:

KFDA による判別結果と, KFDA によって得られた結合係数 α0 を H(f (X)|Y ) のエントロピー最小化に基

min log |αT (Vw +ζK)α| subject to

づき修正したものによる判別結果を表 3 に記す. KFDA

α

6.2

|αT Vb α| = const.

条件付きエントロピー最小基準による非線型次元削減に用いるカーネル関数は Gaussian カーネル()
k(xj , xi ) = exp −λ||xj − xi ||2(17)であり, カーネルパラメタ λ は線型の場合の変換後の次条件付きエントロピー最小化に基づく次元削減手法

元数と同様に, 各データセットから取り出した 5 つの学の非線型化を, KFDA と組み合わせることで実現する.

習データセットを用いた 5 fold cross validation によっ

KFDA によって定まるカーネル関数値の結合係数 α =て定めた. KFDA と提案手法によるその修正による判(α1 , . . . , αN )T を初期値として, 特徴空間に分布するデー
別結果を表 3 に示す. ただし, 非線型化により表 2 にお∑N
タを判別軸に射影した値 f (x) = aT Φ(x) = i=1 αi k(x, xi ) ける線型次元削減手法による最高精度を上回ったデータのクラス条件付きエントロピーを α に関して最適化する.
ここで, 最適化の目的関数であるクラス条件付きエンセットのみを示している.

える. KFDA によって得られた α = α0 を条件付きエン

KFDA によって求めた α0 から開始して条件付きエントロピー基準 (16) を最小化することで得た解は, 条件付
きエントロピーの観点からはより良いものになっている

トロピー最小化基準で修正するということは, 直観的にはが, 表 3 の ringnorm データに見られるように, 判別の観

KFDA の最適基準を多少外れてでも, 各クラスでデータの分散が小さくなるように α を調整するということと理解できる. このとき, KFDA で定まる射影軸上での各クラ点からは KFDA を改悪する可能性がある. 実用上は, こスの平均値を保ちつつ, クラス毎の分散が小さくなることて選択した. この cross validation を行う際に, KFDA

が, 判別の観点からは望ましい. そこで, KFDA によって単体と, 条件付きエントロピー最小化による修正を施し定まる射影軸上の各クラスのデータの平均を αT0 k̄y , y =た結果を用いた判別精度を計算し, バリデーションセッ

1, . . . , C として, グラム行列を用いて表現した射影軸上∑∑Nのクラス中心 N1y xi ∈Dy j=1 αj k(xi , xj ) = αT k̄y とトに対して判別精度の低下が見られる際には提案手法のトロピーに, 以下のような考えから導かれる正則化項を加うした改悪は以下のようにして避けられる. 上述のように, KFDA のカーネルパラメタは cross validation によっ適用を控えれば良い.

合わせ最適化を行う multiple kernel learning (MKL) を,
表 3: Misclassiﬁcation rate by KFDA and modiﬁed

KFDA.
Data namebreast-cancer
diabetes
ﬂare-solar
germanheart
ringnorm
waveform

7

条件付きエントロピー最小化基準によって行うことができる. これは, 今までは主に SVM のマージン最適化に

KFDA
33.753(4.9489)
29.474(2.2658)
35.608(1.9819)
28.277(2.2762)
21.116(3.7185)
2.056(0.4546)
11.673(0.7438)

modiﬁed KFDA
33.917(5.1108)
29.474(2.2658)
36.334(1.8159)
28.046(2.4585)
21.084(3.7831)
9.739(5.3771)
11.61(0.7425)

おわりに情報論的観点から, クラス条件付きエントロピー最小化に基づく教師付き次元削減手法を提案した. 提案手法
は通常の FDA では正しく判別曲面を得られないような状況でも正しく機能しうることを実験的に示した. また,提案する条件付きエントロピー最小化基準による次元削減によってクラス判別に有効な特徴的な低次元空間が得られる仕組みを理論的に考察した. 大規模なベンチマー
クデータを用いた実験により, 提案する手法によって,

FDA や PCA といった既存の次元削減手法より優れた判別を可能とする特徴量が得られることを示した. 近年,
局所性を考慮した次元削減手法が盛んに研究されており,
特にデータ間の類似度関数を陽に用いるものとしては,

LFDA の他に Locality Preserving Projection[12](LPP)
やその非線型化である Laplacian Eigenmap[13](LE) がよく知られている. LFDA は FDA におけるクラス間,
クラス内分散比の最大化基準を, 局所性を考慮して定式化したものである. LPP 及び LE は, 低次元空間に射影したデータ間の距離を, データの類似度で重みつけて最小化する手法であり, データから構成されるグラフのラプラシアンを用いて, 一般化固有値問題として定式化される. 一方, 提案手法は目的関数が変換後のデータのク
ラス条件付きエントロピーであり, その定義には陽に局所性が含まれていない. しかし, カーネル密度関数に基づくデータの密度推定を介してデータ分布の局所構造が自然に反映され, それにより類似度関数を陽に用いた

LFDA と同程度の判別力を有する方法になっていると考えられる.
さらに, 非線型次元削減 (特徴抽出) への拡張として,カーネル法に基づく一つの方法を提案した. ここで提案した方法では, 表 2 に示したようにほとんどのデータに関して提案手法による有意な精度向上は見られず, また,
精度が劣化するケースもあった. 一方, 紙面の制約上, 本
報告には載せられなかったが, カーネル関数は正定値性を保つような多くの変換について再びカーネル関数となる [14] という性質を用いて, 複数のカーネル関数の組み基づいて行われてきた MKL (e.g., [15]) に対する新しいアプローチであり, 実データを用いた実験により, 既存の MKL 手法と同程度の判別結果が得られている.

参考文献[1] K.Fukunaga. Introduction to statistical pattern recognition (2nd ed.). Academic Press Professional, Inc.,San Diego, CA, USA, 1990.
[2] R.A.Fisher. The use of multiple measurements in taxonomic problems. Annals Eugen., 7:179–188, 1936.
[3] M.Sugiyama. Dimensionality reduction of multimodal
labeled data by local ﬁsher discriminant analysis. J.
Mach. Learn. Res., 8:1027–1061, 2007.
[4] T.M.Cover and J.A.Thomas. Elements of information
theory. John Wiley and Sons, Inc., 1991.
[5] J. Beirlant, E. J. Dudewicz, L. Györﬁ, and E. C.
Meulen.
Nonparametric entropy estimation: An
overview. International Journal of the Mathematical
Statistics Sciences, 6:17–39, 1997.
[6] M. P. Wand and M. C. Jones. Kernel Smoothing.
Chapman & Hall/CRC, December 1994.
[7] A. Hyvärinen. Fast and robust ﬁxed point algorithms
for independent component analysis. IEEE Transactions on Neural Networks, 10(3):626–634, 1999.
[8] A.Hyvärinen, J.Karhunen, and E.Oja. Independent
Component Analysis. J. Wiley, New York, 2001.
[9] N. Kumar and A.G. Andreou.
Heteroscedastic
discriminant analysis and reduced rank HMMs for
improved speech recognition.
Speech Commun.,
26(4):283–297, 1998.
[10] T. Cover and P. Hart. Nearest neighbor pattern classiﬁcation. Information Theory, IEEE Transactions on,
13(1):21–27, 1967.
[11] S. Mika, G. Rätsch, J. Weston, B. Schölkopf, and K. R.
Müllers. Fisher discriminant analysis with kernels. In
Neural Networks for Signal Processing IX, 1999. Proceedings of the 1999 IEEE Signal Processing Society
Workshop, pages 41–48, 1999.
[12] X. He and P. Niyogi. Locality preserving projections.
In In Advances in Neural Information Processing Systems 16. MIT Press, 2003.
[13] M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput., 15(6):1373–1396, 2003.
[14] J. Shawe-Taylor and N. Cristianini. Kernel Methods
for Pattern Analysis. Cambridge University Press,
New York, NY, USA, 2004.
[15] G. R. G. Lanckriet, N. Cristianini, P. Bartlett,
L. E. Ghaoui, and M. I. Jordan. Learning the kernel matrix with semideﬁnite programming. J. Mach.
Learn. Res., 5:27–72, 2004.