「画像の認識・理解シンポジウム (MIRU2011)」 2011 年 7 月

拡張ペアワイズ表現を用いた一般化多変量解析
木村

昭悟†

杉山

将††

亀岡

弘和†,††† 坂野鋭†† 日本電信電話 (株) コミュニケーション科学基礎研究所 〒 619-0237 京都府相楽郡精華町光台 2-4†† 東京工業大学 大学院情報理工学研究科 〒 152-8552 東京都目黒区大岡山 2-12-1††† 東京大学 大学院情報理工学系研究科 〒 113-8656 東京都文京区本郷 7-3-1
E-mail: †akisato@ieee.org, ††sugi@cs.titech.ac.jp
あらまし 主成分分析 (PCA)・Fisher 線形判別分析 (FDA)・線形回帰分析 (MLR)・正準相関分析 (CCA) など，多変量解析に基づく次元削減手法，及びカーネルトリックを用いたそれらの非線形拡張が，（一般化）固有値問題を解くことで実現されることは広く知られている．本論文では，まず，上記の多変量解析を統一的な視点で捉えるための枠組として，拡張ペアワイズ表現と呼ぶ共分散行列やグラム行列に関する新しい表現形式を導入した多変量解析の一般化について議論する．この枠組は，上記一連の多変量解析だけではなく，L2 ノルム正則化・graph Laplacian・局所
線形判別分析 (LFDA) など解に望ましい性質を加える各種方法や，教師情報が不足している状況下での半教師付き次元削減をも，その特殊例として含む汎用的かつコンパクトな表現形式となっている．本論文では，この枠組の中で具体的な解析手法を設計する指針についても提示する．この指針では，上記の標準的な多変量解析手法やその各種拡張を設計のテンプレートとして利用し，それを適切に組み合わせるだけで解析手法を設計できることを示している．さらに，この設計指針に基づいて具体的に生成した新しい多変量解析手法を提案すると共に，その有効性を一般物体認識を題材として示す．
キーワード

多変量解析，次元削減，ペアワイズ表現，一般化固有値問題，正則化，半教師付き学習

1. は じ め に画像・映像だけでなく，購買履歴・経済データ・地球観測データなどのデータが大量にオンラインで容易に入析 (LFDA) [15] に代表される外れ値や多峰性分布に対する頑健性向上や，半教師付き判別分析 [16] や半教師付き
正準相関分析 [13], [17] などに代表される半教師付き次元削減などの拡張も各種なされている．

手できるようになる一方で，その大量さゆえにデータに現在のデータマイニングにおけるもう 1 つの特徴は，どのような傾向や性質があるのかを読み取ることが困難

目的やデータの性質が複雑で多様化している点にある．

になっている．これら大量のデータの中に隠れている構

このような場合，どこにどのような構造が隠れているか造や情報を抽出するために，多変量解析が強力な道具のが不明確であるため，そもそもどの手法を用いるべきか

1 つとして活用されている．
標準的な多変量解析手法として，主成分分析 (PCA) [1]・
Fisher 判別分析 (FDA) [2]・線形回帰分析 (MLR)・正準
相関分析 (CCA) [1] などが知られている [3], [4]．上記の多変量解析手法は，多次元ベクトルで与えられるサンプルの共分散行列もしくはそれを組み合わせた拡大行列の（一般化）固有値問題として定式化される．
また，非ベクトルサンプル・非線形解析に対応するた
めに，従来の多変量解析にカーネル法を導入したカーネ
ル多変量解析についても，数多くの研究がなされている [4]〜[9]．カーネル多変量解析では，共分散行列に代えて所定のカーネルによって決まるグラム行列が用いられ，その（一般化）固有値問題によって解析が実現される．カーネル法の導入によって必要以上に大きくなった
表現能力を抑える正則化についても各種提案されており，代表的な手法として，Ridge 回帰 [10] ・Tikhonov 正則
化 [11], [12]・graph Laplacian [13] などが知られている．
さらに，局所性保存射影 (LPP) [14] や局所線形判別分がはっきりしない点が問題となる．故に，マイニングの実施者がそれぞれの目的に応じてテーラーメイド的かつ簡易に様々な解析手法を設計できる状況が望ましい．
上記の議論に基づき，本論文では，まず，拡張ペアワ
イズ表現と呼ぶ，共分散行列やグラム行列に関する新しい表現形式を導入することにより，既存の多変量解析手法やその拡張を統一的な視点で捉え直す枠組を提供する．
この枠組を，本論文では以降，簡単のため，一般化多変量解析と呼ぶこととする．本論文の後半では，一般化多変量解析の枠組の中で所望の解析手法を具体的に設計す
る指針について議論する．この指針が示すところは，上記の標準的な多変量解析手法やその各種拡張を設計のテンプレートとして利用し，それを適切に組み合わせるだ
けでも解析手法を設計できるという点にある．この設計指針に基づいて具体的に新しい多変量解析手法を比較的容易に生成することができる．その具体例をいくつか提案すると共に，その有効性を一般物体認識を題材として示す．

3. 一般化多変量解析

2. ベクトルデータに対する多変量解析
多変量解析の対象として，2 種類（注 1）のサンプル集合 Xと Y を考える．各サンプルはそれぞれ dx 次元及び dy次元の多次元列ベクトルで構成されており，その数はそれぞれ Nx 個及び Ny 個である．同じ下付添字を持つサンプルが共起するサンプル対を表すとすると，各サンプル集合は，以下のように，共起サンプル集合 (X C , Y C )と非共起サンプル集合 X I , Y I に分類される．

X = XC ∪ XI ,3. 1 拡張ペアワイズ表現
式 (2) で解析の対象となる行列として共分散行列がしばしば用いられる．（注 2）

S xy = N −1

∑N

−1
⊤
X ⊤Y .
n=1 xn y n = N

また，局所性保存射影 (LPP) [14] や局所線形判別分析(LFDA) [15] では，サンプル間の類似性を考慮した共分
散行列の拡張として下記の 2 次統計量が用いられる．

Y = Y C ∪ Y I,

X C = {x1 , . . . , xN } = {xC,1 , . . . , xC,N },S Q,xy =Y C = {y 1 , . . . , y N } = {y C,1 , . . . , y C,N },

N
N
∑
∑

Qn1 ,n2 (xn1 − xn2 )(y n1 − y n2 )⊤ .

n1 =1 n2 =1

X I = {xN +1 , . . . , xNx } = {xI,1 , . . . , xI,Nx −N },Y I = {y Nx +1 , . . . , y Nx +Ny −N } = {y I,1 , . . . , y I,Ny −N }.

ただし，行列 Q は任意の N × N 非負値対称行列とする．
∑N
ここで，N × N 対角行列 D を Dn,n = n2 =1 Qn,n2 ，行

本論文では，サンプル平均を 0 ベクトルであると仮定す

列 Q によって決まる N × N 行列 LQ を LQ = D − Qる．この仮定により一般性が失われることはない．以下，と置くと，2 次統計量 S Q,xy は行列 LQ を用いて以下の特に注釈がない場合を除き Nx = Ny = N とする．

ように表現できる．

これまでに知られている多変量解析の多くは，下記に示す関数を最大化する基底ベクトル w(opt)を求める問題
この表現を，2 次統計量 S Q,xx のペアワイズ表現 [16] ととして定式化される．

w(opt) = arg max w⊤ Cw(w⊤ Cw)−1 ,w∈Rd呼ぶ．行列 LQ は一般に Laplacian 行列と呼ばれ，半正(1)

ここで，行列 C 及び C は何らかの統計的性質を表現する行列である．例えば，主成分分析 (PCA) では C が Xの共分散行列かつ C が単位行列，線形判別分析 (FDA)
では C がクラスタ間共分散行列かつ C がクラスタ内共分散行列となる．式 (1) に示す最大化は，行列 C に対応する性質を強調し，行列 C に対応する性質を抑制する操作として直感的には理解される．この最大化において，
基底ベクトル w にはスケール任意性が残っているため，
この任意性を取り除いた以下の形式が利用される．

w

(opt)

w∈Rd

R2 (w) = w⊤ Cw.

ンプル数 N と同数の頂点数を持つグラフの辺の重みを保持する場合，行列 LQ は特に graph Laplacian と呼ばれる．
本論文では，このペアワイズ表現に行列 Q と独立な項を追加した以下の表現を新たに導入する．

Ŝ Q,xy = XLQ,1 Y ⊤ + L2 .

(3)

ただし，LQ,1 は行列 Q によって決まる N × N 半正定値対称行列，L2 は行列 Q とは独立に決まる dx × dy 非負値行列である．式 (3) に示す表現を以降，拡張ペアワ

3. 2 一般化多変量解析の設計指針

この制約付最大化問題を Lagrange 未定乗数法を用いて解くことで，以下の一般化固有値問題を得る．

Cw = λCw,

定値行列になることが知られている．また，行列 Q がサイズ表現と呼ぶ．

= arg max R1 (w) s.t. R2 (w) = 1,

R1 (w) = w⊤ Cw,

S Q,xy = XLQ Y ⊤ .

(2)

この一般化固有値問題を解いた結果として得られた固有ベクトルの集合から，固有値の大きい順に r 本選択した
固有ベクトル wk (k = 1, 2, . . . , r) が，当初の多変量解析
において求めるべき基底ベクトルとなる．

ここで，拡張ペアワイズ表現を用いた，以下の一般化
固有値問題で定式化される解析を考える．
)
(
)
(
wx
wx
= λC Q
,
CQ
wy
wy
)
(
Ŝ Q,xx Ŝ Q,xy,
CQ =Ŝ Q,yx Ŝ Q,yy()
Ŝ Q,xx Ŝ Q,xy
CQ =.
Ŝ Q,yx Ŝ Q,yy

(4)

(5)

(6)

本論文では，式 (4) で定式化される多変量解析を一般化（注 1）：3 種類以上のサンプル集合に対しても以降の議論は同様に成り立つが，簡単のため本論文では 2 種類の場合に限定して説明する．

（注 2）：紙面の制約から，以降では S xy 及びその拡張についてのみ言及する．S xx や S yy についても同様に定義できる．

{

多変量解析と呼ぶ．
式 (5)(6) に示される行列をどのように設計するかに∥xn1 − xn2 ∥2An1 ,n2 = exp −σn1 σn2れる．基本的には，通常の多変量解析と同様に，一般化
し，行列 C Q に対応する性質を抑制するという構造は変わらない．しかし，この構造のみでは，目的やデータの性質に応じた解析手法を設計する指針とはならない．

,

σn = ∥xn − x(k)n ∥,よって，式 (4) に示す一般化多変量解析の性質が決定さ
多変量解析においても，行列 C Q に対応する性質を強調}(k)

ただし，xn は xn の第 k 近傍のサンプルとする．
上記の内容により，LFDA は式 (5) と式 (6) に示される行列をそれぞれ(LF DA)

CQ

(lb)

= SQ

(LF DA)and C Q

(lw)

= SQ

以降では，一般化多変量解析を具体的にどのように設計すれば良いかについて詳説する．まず，一般化多変量
解析を構成するテンプレートの役割を担う標準的な多変量解析手法のうち，特に解説が必要と考えられるいくつかの例について述べる．その後，標準的な多変量解析を組み合わせて構成される，一般化多変量解析に含まれる既知の特殊例について，組み合わせ方のテンプレートとして紹介する．さらに，これらの考察から導かれるいく
つかの新しい多変量解析手法について述べる（注 3）．

と設定した一般化多変量解析の特殊例となる．

4. 2 正準相関分析 (CCA)
正準相関分析 (CCA) [1] は，複数のサンプル集合に共通して含まれる情報を抽出して統合する次元削減手法の 1 つである．具体的には，2 つのサンプル集合 (X, Y )を線形変換 (wx , wy ) でそれぞれ変換した際に，変換後の変量の正規化相互相関が最大となるような線形変換(wx , wy ) を求める．すなわち，CCA が最大化すべき目
的関数 ρ(wx , wy |X, Y ) は以下のようになる．

4. 一般化多変量解析の既知例

ρ(CCA) (wx , wy |X, Y )4. 1 局所 Fisher 判別分析 (LFDA)
局所 Fisher 判別分析 (LFDA) [15] は，一般的な FDA=の拡張の 1 つとして知られる教師付き次元削減手法であ(X ⊤ wx )⊤ (Y ⊤ wy )w⊤x S xy w y
√
.
=
⊤
⊤
∥X wx ∥ · ∥Y wy ∥w⊤ S xx wx w⊤ S yy wyxyり，外れ値や分布の多峰性などによる判別性能の低下を緩和することができる．LFDA のポイントは，教師なし次（注 4）

元削減手法の 1 つである局所性保存射影 (LPP) [14]を源流とする，サンプル間類似度行列 Q を考慮したクラス
(lb)
(lw)
間分散 S Q ・クラス内分散 S Q の計算にある．

(lb)
SQ =

N
N
∑
∑

目的関数の最大化に線形変換 (wx , wy ) のスケールが影⊤
響しないことから，正規化 w⊤
x S xx w x = w y S yy w y = 1

を制約条件とした Lagrange 未定乗数法を用いることにより，以下の式を得る．

S xy wy − λS xx wx = 0,⊤Q(lb)n1 ,n2 (xn1 − xn2 )(xn1 − xn2 ) ,S yx wx − λS yy wy = 0.

n1 =1 n2 =1
(lw)
SQ =

N
N
∑
∑

⊤
Q(lw)
n1 ,n2 (xn1 − xn2 )(xn1 − xn2 ) .

n1 =1 n2 =1

Y = {y1 , . . . , yN } の各要素が X の各要素の所属クラスを示すインデックスであるとき，LFDA における行列 Qの各要素は以下の式によって計算される．
{
An1 ,n2 (1/N − 1/Nc ) if yn1 = yn2 = c,(lb)
Qn1 ,n2 =1/N
if yn1 =| yn2 ,{
An1 ,n2 /Nc if yn1 = yn2 = c,Q(lw)n1 ,n2 =1/N
if yn1 =| yn2 ,
ただし，Nc はクラス c に属するサンプルの総数である．
正方行列 A = {An1 ,n2 }N
n1 ,n2 =1 は任意に設計することができるが，LPP 及び LFDA では局所スケーリング法 [19]による設計が用いられている．

（注 3）：以降の節では，C Q や C Q の表記の際に類似度行列 Q や Qが明示的に意識されない場合には，その表記を省略する．
（注 4）：LPP も一般化多変量解析で記述できるが，詳説は割愛する．

上記の内容により，CCA は，式 (5)(6) に示される行列を以下のように設定した一般化多変量解析の特殊例と
なる．
(
C

(CCA)

=

0
S yx

S xy
0

)

(
, C (CCA) =

S xx
0

0
S yy

)

4. 3 線形回帰分析 (MLR)
線形回帰分析 (MLR) は，サンプル y とその線形近似である W x との二乗誤差を最小にする線形変換 W を求める問題として定式化される．一般的には，MLR は最小自乗法を用いて解を導出するが，本節では一般化固有値問題での定式化を試みる．まず，ランク 1 の変換行列

W を考え，それが 2 つの基底ベクトル wx と wy の直積の形に分解できるとする．このとき，最小化すべき二乗
誤差 ϵ2 (wx , wy |X, Y ) は以下のように計算される．
ϵ2 (wx , wy |X, Y )∑N
2= N −1 n=1 ∥y n − αwy w⊤
x xn ∥⊤2 ⊤= S 2yy − 2αw⊤y S xy w x + α w x S xx w x .

.

(

これを α について最小化すると，以下の式が得られる．

C

⊤
⊤
−1
α = (w⊤.
y S xy w x )(w x S xx w x )(T ik)=(

よって二乗誤差 ϵ (wx , wy |X, Y ) は2C

ϵ2 (wx , wy |X, Y )(T ik)

=

0
S yx

S xy
0

)

S xx + δ̂x I dx
0,0
S yy + δ̂y I dy).

本節における考察から，式 (3) で示した拡張ペアワイ

⊤
2
⊤
−1
= S 2yy − (w⊤.
y S xy w x ) (w x S xx w x )ズ表現における行列 L2 は，基底ベクトルに対する正則

二乗誤差 ϵ2 (wx , wy |X, Y ) が非負であること，上式右辺

化項としての役割を果たすことがわかる．

第 1 項が基底ベクトル (wx , wy ) とは独立に決まること

4. 5 半教師付き局所 Fisher 判別分析 (SELF)

から，二乗誤差最小化は以下の目的関数の最大化に置換できる．
(M LR)

ρ(wx , wy |X, Y ) = √w⊤
x S xy w y⊤w⊤x S xx w x w y w y

ゆる半教師付き次元削減の問題に対して， 教師なし次.

上式を CCA の目的関数と比較することで，MLR が CCAの特殊例となること，及び解析対象の行列が以下で与えられることがわかる．
(
C(M LR)

=

0
S yx

S xy
0

)

(
, C (M LR) =S xx
0

半教師付き局所 Fisher 判別分析 (SELF) [16] は，いわ

0
I dy

)
.

4. 4 Tikhonov 正則化
多変量解析における一般的な正則化の方法の 1 つとして，基底ベクトルの二乗和を正則化項とする Tikhonov
正則化 [11], [20] が知られている．Tikhonov 正則化を適用した MLR は，特に Ridge 回帰と呼ばれる [10]．このRidge 回帰を例として，Tikhnonov 正則化とその一般多変量解析との関係について詳説する．
Ridge 回帰で最小化すべき計量は，回帰分析で最小化
すべき二乗誤差に基底ベクトルの二乗和を正則化項として加えた以下の量である．（注 5）

元削減法としての PCA と教師付き次元削減法としての
LFDA を融合させた手法である．SELF は，一般化多変量解析の設計指針において重要となる以下の 2 点を包含する典型的な例となっている．
（ 1 ） 複数の標準的なテンプレートを組み合わせる．
（ 2 ） 組み合わせる各テンプレート内で計量計算に用いるサンプル集合を変える．
本節では，サンプル集合 Y がクラス番号を保持する属性
データ，及び Nx > Ny = N（すなわち X I =| ∅, Y I = ∅）という状況を考える．
少数の教師付きサンプル集合 (X C , Y C ) のみを用いた
LFDA では，過適応が生じる可能性がある．SELF では，教師なしサンプル集合 X I も含めた PCA を組み合わせることで，この過適応を回避する．具体的には，教師付
きサンプル集合のみから計算される LFDA のクラス内・
(lw)
(lb)
クラス間分散行列 (S Q,C , S Q,C ) と，教師なしサンプル
集合をも用いた PCA の共分散行列 S xx とを混合した以下の行列による一般化多変量解析が，SELF となる．
(SELF )= βS Q,C + (1 − β)S xx ,(SELF )= βS Q,C + (1 − β)I dx .

CQ
CQ

(lb)

(lw)

ϵ2 (wx , wy |X, Y )∑N2
2= N −1 n=1 ∥y n − αwy w⊤
x xn ∥ + δ∥w x ∥ただし，β は 0 <=β<= 1 を満たすフリーパラメータであ⊤2 ⊤= S 2yy − 2αw⊤y S xy w x + α w x (S xx + δ̂I dx )w x .

る．β = 1 の場合に教師付きサンプル集合 (X C , Y C ) のただし，δ̂ = δ/α2 である．このことから，Ridge 回帰も一般化多変量解析の特殊例となり，
)
(
0
S xy
(Ridge)
,
C
=
S yx
0
)
(
S xx + δ̂I dx
0(Ridge)
C
.
=
0
I dy
となることがわかる．Ridge 回帰と同様の手順を踏むことで，CCA における Tikhonov 正則化 [12] も一般化多変量解析の特殊例となることが示される．

（注 5）：定数 δ を Lagrange 未定乗数と見なすと，この最小化問題は，
基底ベクトルの自乗和をある定数以下とする制約付問題と等価となる．

みを用いた LFDA と一致し，β = 0 の場合にサンプル集
合 X のみを用いた PCA と一致する．一般に，SELF は，

LFDA と PCA の双方の性質を受け継いでおり，教師付
きサンプル集合の局所的な構造と，サンプル空間における大域的な分布構造とを，パラメータ β で制御する．

4. 6 半教師付き正準相関分析 (SemiCCA)
前 節 で 紹 介 し た SELF の 考 え 方 を CCA に 適 用 した手法が，半教師付き正準相関分析 (SemiCCA) である [17], [21]．具体的には，2 つのサンプル集合 (X, Y )がいずれもベクトルデータ，かつ Nx > N , Ny > N（X I =| ∅, Y I =| ∅）という状況を考え，共起サンプル集
合 (X C , Y C ) のみを用いた CCA と，非共起サンプル集
合 (X I , Y I ) をも取り込む PCA とを，拡大行列の内分混合によって組み合わせる．

C((sCCA)

(

= β

S Cyx

C (sCCA)
(
= β

0

S Cxy
0

)

(
+ (1 − β)

S xx
0

0
S yy

)

C

=

,

K 2xx
0

0
K 2yy

)
.

上記の一般化固有値問題から射影軸 (wx , wy ) そのもの
S Cxx
0

0
S Cyy

)

(
+ (1 − β)

I dx
0

0
I dy

を求めることはできないが，これら射影軸への射影は),

SELF と 同 様 ，β = 1 の 場 合 に 共 起 サ ン プ ル 集 合(X C , Y C ) のみを用いた CCA と一致し，β = 0 の場
合に X と Y を独立に PCA を行う問題に帰着される．
こ れ ま で の 議 論 を 踏 ま え る と ，C (sCCA) 第 2 項 はTikhonov 正則化項と見なすことができる．すなわち，SemiCCA で得られる基底は，ノルムがある定数以下に(sCCA)
なる制約の下で最適化される．一方，C
第 2 項は，
X と Y の独立性に関する制約を緩め，共起サンプル集
合 (X C , Y C ) のみからでは得られない相関関係を，非共起サンプル集合も含めた全サンプル集合 (X, Y ) の同時分布から獲得する効果が期待される．

5. カーネル一般化多変量解析
一般化多変量解析の枠組に含まれるいずれの解析手法
も，カーネルトリックを用いて非ベクトルデータ・非線形解析へ拡張できる．以降では，例としてカーネル正準
相関分析 (kernel CCA) [4], [8], [9] 及びその拡張について概説する．詳細は各文献に譲る．

5. 1 カーネル正準相関分析 (Kernel CCA)
Kernel CCA では，各サンプル (xn , y n ) にそれぞれ（非線形）変換 (ϕx , ϕy ) を施した後のベクトル (ϕx (xn ),ϕy (y n )) に対して CCA を行い，基底ベクトル (wx , wy )を求める．Kernel CCA で最大化すべき目的関数は，変換 (ϕx (xn ), ϕy (y n )) に対応するグラム行列 K x , K y を用いて以下のように記述される．
α⊤ K xx K yy βρ(kCCA) (wx , wy |X, Y , ϕx , ϕy ) = √.
α⊤ K 2xx αβ ⊤ K 2yy β
K xx = {Kx (xn1 , xn2 )}Nn1 ,n2 =1 ,Kx (xn1 , xn2 ) = ϕx (xn1 )⊤ ϕx (xn2 ),Ky (xn1 , xn2 ) = ϕy (y n1 )⊤ ϕy (y n2 ),N∑
n=1

αn ϕx (xn ),

wy =

N
∑

カーネル関数を用いて以下のように求められる．

w⊤x ϕx (x) =N∑

αn Kx (xn , x),n=1w⊤
y ϕy (y) =N∑

βn Ky (y n , y),n=1

5. 2 Kernel CCA における正則化
Kernel CCA は，用いるグラム行列のランクが高々min(mx , my ) となるため，過学習が非常に起こりやすく，
通常は何らかの正則化と共に用いられる．最も一般的な正則化の 1 つが，先に紹介した Tikhonov 正則化である [12]．Tikhonov 正則化により，解析に用いられる各行列は以下のように置き換わる．
)(
0
K xx K yy(kT ik),C=
K yy K xx
0)(0
K 2xx + δx K xx
(kT ik).
C=0
K 2yy + δy K yy
もう 1 つの代表的な正則化手法として，graph Laplacian を用いる方法が知られている [13]．Graph Laplacian
正則化を用いることにより，非線形変換前の原空間での平滑化をもたらす効果がある．サンプル間類似度行列
Qx , Qy によって決まる Laplacian 行列を LQx , LQy とすると，graph Laplacian 正則化を用いることにより，解析に用いられる各行列は以下のように置き換わる．
()
0
K xx K yy
(Lap)
C
=
,
K yy K xx
0()
K 2xx + γx K̂ xx
0
(Lap)
C
=
,
0
K 2yy + γy K̂ yy

K̂ xx = K xx LQx K xx ,K yy = {Ky (y n1 , y n2 )}Nn1 ,n2 =1 ,wx =(kCCA)

βn ϕy (y n ),n=1

K̂ yy = K yy LQy K yy ,5. 3 Kernel SELF
一般多変量解析のカーネル拡張を知る上で重要となるのが，SELF のカーネル拡張である kernel SELF [16] である．先に示した通常の SELF と同様，複数の標準的なテンプレートを組み合わせる方法，及び組み合わせる各

通常の CCA と同様にして，上記の目的関数最大化は，

テンプレート内で計量計算に用いるサンプル集合を変え以下の一般化固有値問題を解くことによって行われる．
(
)
(
)
α
α
(kCCA)(kCCA)
C
= λC
β
β
(
)
0
K xx K yy(kCCA)C=,
K yy K xx
0

る方法を，kernel SELF を見ることで知ることができる．

Kernel SELF を導出するポイントは，ペアワイズ表
現にある．まず，教師付きサンプル集合のみから計算さ(lb)れるクラス間共分散行列 S Q,C とクラス内共分散行列(lw)

S Q,C ，及び全サンプルから計算される共分散行列 S xx
を，それぞれペアワイズ表現に変換する．

S Q,C = X C LQ,C X ⊤
C,
(lb)

(lb)

S Q,C = X C LQ,C X ⊤
C,
(lw)

(lw)

S xx = XLxx X ⊤ ,6. 1 局所正準相関分析 (LCCA)
FDA を LFDA に拡張する方法と同様に，CCA にサン

(lb)

(lw)

ここで得られた各 Laplacian 行列 LQ,C , LQ,C 及び Lxxを用いることにより，解析に用いる各行列を以下のように記述できる．
(lb)
C = K x {βLQ,C + (1 − β)Lxx }K x ,(lw)

C = βK x LQ,C K x + (1 − β)K x ,このことから，線形一般多変量解析における共分散行列

プル間類似度行列 Q を導入することで，外れ値や分布
多峰性の影響を一定程度緩和した基底の導出が可能となる．本稿では，この方法を局所正準相関分析 (LCCA) と呼ぶ．EM アルゴリズムによる混合ガウス分布パラメー
タの推定と CCA とを組み合わせる方法を用いても類似の効果を期待できるが，あらかじめ混合数を設定する必要がない点，一般化固有値問題を一度解くだけで最適解が算出できる点において，LCCA がより優れている．

の内分混合は，カーネル一般多変量解析では（拡張）ペ

具体的には，サンプル間類似度行列 Qxx , Qyy , Qxy を

アワイズ表現に変換した後の内分混合として扱うことが考慮した 2 次統計量 S Qxx ,xx , S Qyy ,yy , S Qxy ,xy を各共できることがわかる．

分散行列に代えて用いた CCA が，LCCA となる．
()
0
S Qxy ,xy
(LCCA)CQ=
S Qyx ,yx0()
S Qxx ,xx
0
(LCCA)CQ=,
0
S Qyy ,yy()
Qxx QxyQ =,Qyx Qyy

5. 4 半教師付き Kernel CCA
SELF を SemiCCA に拡張する方法と同様にして，kernel SELF を拡張することで半教師付き正準相関分析(kernel SemiCCA) を導出できる．詳細は省略する．
半教師付き正準相関分析の別の実現方法として．
Blashcko らによる方法 [13] が知られている．この方法では，半教師付き次元削減を実現するために用いる計量計
算の方法が SELF や SemiCCA と異なる．具体的には，
一般化多変量解析における各行列を以下のように置くことで実現される．
()
0
K XXC K YC Y
(Bla)
C
=
,
K Y Y C K XC X
0)(
K XXC K XC X
0
(Bla)
,
C
=
0
K Y YC K YC YNx
K XXC = {Kx (xn1 , xC,n2 )}N
n1 =1 n2 =1 ,Nx
K XC X = {Kx (xC,n1 , xn2 )}N
n1 =1 n2 =1 .

この方法はすなわち，拡張グラム行列 K XXC の転置積

K XXC K XC X を利用することで，よりサイズの大きなグラム行列の積 K 2XX に相当する情報を抽出している．

6. 一般化多変量解析の構成例
前節までの議論にて，(1) 一般化多変量解析を設計す
る上でのテンプレートとしての既出の多変量解析手法，(2) そのテンプレートの組み合わせ方の例としての共分散行列の内分混合，及び (3) 2 次統計量計算の母集合の切替を提示した．一般化多変量解析の枠組そのものは非常に広範であり，これらの組み合わせに留まるものではない．しかし，前節まで紹介したテンプレートとその組み合わせ方を利用するだけでも，いくつかの有用かつ新しい多変量解析手法を生成することができる．本節では，その例について紹介する．

6. 2 正準相関判別分析 (CCDA)
音響信号と画像信号とによって構成される映像信号にメタ情報が付与されている場合などのように，それぞれ性質の異なる共起サンプル集合 (X, Y ) の各サンプル対にラベルが付与されている状況を考える．
このとき，各サンプル対 (xn , y n ) (n = 1, 2, . . . , N ) を⊤ ⊤連結したベクトル (x⊤n , y n ) を新しいサンプルと考えて

FDA を適用し，判別軸を求める方法が考えられる．しかし，この方法では，CCA で発見可能な 2 種類のベクトル集合の相関関係を PCA で計算できないことと同様に，適切な相関関係を計算できないという問題がある．
この対処法として，共起サンプル集合 (X, Y ) について
CCA を用いた次元削減を行った後に FDA を用いる方法が考えられる．しかし，2 種類のベクトル集合の相関関係がクラスごとに異なる場合には，その関係性を見出す
ことが困難である．
そこで，SELF や SemiCCA で活用した共分散行列の内分混合を利用することで CCA と FDA を融合し，クラスごとに異なる相関関係を持つ可能性のある 2 種類のベクトル集合に対する識別的次元削減を可能にする．
一般化多変量解析の枠組における具体的な定式化は以下の通りとなる．β = 1 の場合に CCA と一致し，β = 0の場合に各サンプル対を連結したベクトルを新しいサンプルと考えた FDA と一致する．
(

C(CCDA)= β(C(CCDA)

= β

0
S yx

S xy
0

S xx
0

0
S yy

)

(

+ (1 − β))(+ (1 − β)

(lb)

S xx
(lb)
S yx
(lw)

S xx
(lw)
S yx

(lb)

S xy
(lb)
S yy
(lw)

S xy
(lw)
S yy

)
,
)
.

図 1 VOC2008 データセットに含まれる画像の例

6. 3 半教師付き学習への拡張

図2

一般物体認識タスクにおける精度評価の結果

上記の 2 つの手法は，SELF や SemiCCA の手順を参考にすることで，半教師付き次元削減に拡張することが間内でのカーネル密度推定により導出された潜在変数のできる．LCCA の半教師拡張の手順は SemiCCA のそれ

確率密度関数に基づいてラベル割り当てを行う．本実験とほぼ同様であり，LCCA と局所性保存射影 (LPP) [14]では，上記 2 手順のうち第 1 の手順である潜在変数空間を組み合わせる．また，CCA+LDA の半教師拡張につの構築について，その手法を変更して評価検証を行う．

いては，教師付き次元削減である FDA に対応する 2 次

画像特徴量は SURF [24] を特徴点抽出・局所特徴量抽出

統計量を教師付きサンプル集合のみから，教師なし次元に用いた Bag-of-Features (256 次元)，ラベル特徴量はラ削減である CCA に対応する 2 次統計量を全サンプル集

ベルの有無を 2 値で表現するラベル数 (=20) と同数次元合から計算することで実現できる．

のベクトルを利用した．潜在変数空間の次元は 8 次元と

7. 検 証 実 験
7. 1 実 験 条 件
提案法の有効性を検証するために，PASCAL VisualObject Challenge (VOC) 2008 及び 2009 [22] データセッ
トを利用して，主に物体認識に関する実験を行い，その精度を評価した．
PASCAL VOC データセットは，20 個のクラスのいずれかに属する「物体」（人物，動物，車両，家具）が含まれる画像からなる，一般物体認識を主目的としたベンチマークである．1 枚の画像の中に複数の物体が含まれることもあり，それら複数物体のクラスが同じ場合も異なる場合もある．VOC2008 データセットに含まれる
学習用画像の例を図 1 に示す．学習用画像には，物体の位置を示す方形領域とそのクラスがメタ情報が付与されている．しかし，一般の画像認識検索が利用される状況
において，上記のようなメタ情報が完全に与えられることは想定しにくい．そこで，本実験においては，全ての処理において物体の存在位置を示す方形領域は用いず，画像に付与されたクラスラベルのみを利用した．また，
VOC2008 学習用データセットに含まれるラベル付画像
5096 枚のうち，本実験では，ランダムに選択した 4000
枚をラベル付き学習用画像 G(L) ，1000 枚を評価用画像
G(E) として利用した．
物体認識アルゴリズムは，中山ら [23] が提案した，
CCA とカーネル密度推定を組み合わせた方法を用いた．
この方法は，(1) 画像特徴量集合とラベル特徴量集合とを共起サンプル集合として用いた CCA を用いることに
より低次元潜在変数空間を構築し，(2) その潜在変数空した．

7. 2 実 験 結 果
一般物体認識における評価尺度として，以下で定義される正答率 (P R)，再現率 (RE)，及び F 値 (F ) を用いる．

∑Ne
P R = ∑NeRE =n=1 tpn,n=1 (tpn + f pn )∑Ne
n=1 tpn,∑Ne
n=1 (tpn + f nn )

(

F =2

1
1
+
P R RE

(7)
(8)

)−1

,

(9)

ここで，Ne は評価用画像の数 (= 500)，tpn ，f pn ，f nn
はそれぞれ n 番目の評価用画像に対する認識結果についての正解数，誤検出数，見落し数を表現する．
図 2 に実験結果を示す．青太線，緑太線が，それぞれ，
潜在変数空間構築に CCA，LCCA を用いた場合の結果である本結果が示すように，サンプル間類似度行列を考慮した LCCA で，それを考慮しない CCA を上回る結果を示している．

8. お わ り に
本論文では，拡張ペアワイズ表現と呼ぶ共分散行列やグラム行列に関する新しい表現形式を導入することにより，標準的な多変量解析手法やその正則化・半教師付き
拡張を統一的な視点で捉え直す枠組を提供すると共に，
これら標準的な多変量解析手法やその正則化・半教師付
き拡張をテンプレートとして組み合わせるという，新しい多変量解析手法の設計指針を提示した．また，この設計指針に基づいて，いくつかの有用で新しい多変量解析
を具体的に提案した．さらに，一般物体認識ベンチマー[17]クを用いた実験によって本手法の有効性を示した．
一般化多変量解析の枠組そのものは非常に広範であり，これらの組み合わせに留まるものではない．カーネル多変量解析におけるカーネルの設計と同様に，拡張ペアワ
イズ表現に含まれる 2 つの行列を問題や対象に合わせて設計する，より汎用的な設計指針については，今後の研究課題として最も重要なものの 1 つである．

[18]
[19]
[20]
[21]

謝辞
本研究に対し真摯にご議論いただき有益な御助言を頂いたNTT コミュニケーション科学基礎研究所 大石康智 氏及び前田英作 主席研究員に深謝する．また，本共同研究に御支援を頂いた NTT コミュニケーション科学基礎研究所 上田修功 所長，大和淳司 主幹研究員，柏野邦夫 主幹研究員，並びに澤田宏 主幹研究員に感謝する．
文

献[1] H. Hotelling, “Analysis of a complex of statisticalvariables into principal components,” Journal of Educational Psychology, Vol. 24, 1933.
[2] R. Fisher, “The use of multiple measurements in taxonomic problems,” Annals Eugen., Vol. 7, pp. 179–188,
1936.
[3] T. Anderson, An Introduction to Multivariate Statistical Analysis, Wiley-Interscience, 2003.
[4] 赤穂, カーネル多変量解析, 岩波書店, 2008.
[5] 福水, カーネル法入門, 朝倉書店, 2010.
[6] B. Schölkopf, A. Smola, and K. Müller, “Nonlinear
component analysis as a kernel eigenvalue problem,”
Neural Computation, Vol. 10, no. 5, pp. 1299–1319,
1998.
[7] G. Baudat and F. Anouar, “Generalized discriminant
analysis using a kernel approach,” Neural Computation, Vol. 12, no. 10, pp. 2385–2404, 2000.
[8] S. Akaho, “A kernel method for canonical correlation
analysis,” in In Proc. IMPS2001.
[9] P. Lai and C. Fyfe, “Kernel and nonlinear canonicalcorrelation analysis,” in Proc. ICANN, Vol. 4, pp.
4614, 2000.
[10] A. Hoerl, “Application of ridge analysis to regression
problem,” Chemical Engineering Progress, vol. 58, pp.
54 – 59, 1962.
[11] A. Tikhonov, “On the stability of inverse problems,”
Dokl. Akad. Nauk SSSR, vol. 39, no. 5, pp. 195–198,
1943.
[12] D. Hardoon, S. Szedmak, and J. Shawe-Taylor,“Canonical correlation analysis: An overview with application to learning methods,” Neural Computation,
vol. 16, no. 12, pp. 2639–2664, 2004.
[13] M. Blaschko, C. Lampert, and A. Gretton, “Semisupervised laplacian regularization of kernel canonicalcorrelation analysis,” in Proc. ECML PKDD 2008,
pp. 133–145.
[14] X. He and P. Niyogi, “Locality preserving projections,” in Proc. NIPS, 2003.
[15] M. Sugiyama, “Dimensionality reduction of multimodal labeled data by local Fisher discriminant analysis,” JMLR, Vol. 8, pp. 1027–1061, May 2007.
[16] M. Sugiyama, T. Idé, S. Nakajima, and J. Sese,

[22]

[23]

[24]

“Semi-supervised local Fisher discriminant analysis
for dimensionality reduction,” Machine Learning, vol.
78, no. 1–2, pp. 35–61, 2010.
A. Kimura, H. Kameoka, M. Sugiyama, T. Nakano,
E. Maeda, H. Sakano, and K. Ishiguro, “SemiCCA:
Eﬃcient semi-supervisedllearning of canonical correlations,” in Proc. ICPR2010, pp. 2933–2936.
K. Fukunaga, Introduction to statistical pattern recognition, Academic Press, Inc., 1990.
L. Zelnik-manor and P. Perona, “Self-tuning spectralclustering,” in Proc. NIPS2004, pp. 1601–1608.
C. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.
木村, 中野, 亀岡, 杉山, 前田, 坂野, “SSCDE: 画像認識
検索のための半教師付正準密度推定法,” in 画像の認識・理解シンポジウム予稿集, July 2010, OS8–1.
M. Everingham, L. Van Gool, C. K. I. Williams,
J. Winn, and A. Zisserman, “The PASCAL VisualObject Classes Challenge 2009 (VOC2009) Results,”
http://www.pascal-network.org/challenges/VOC/
voc2009/workshop/index.html.
中山, 原田, 國吉, “大規模 web 画像のための画像アノテーション・リトリーバル手法,” in 画像の認識・理解
シンポジウム予稿集, July 2009, pp. 55–62.
H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool,“Speeded-up robust features (SURF),” CVIU, Vol.
110, no. 3, pp. 346–359, 2008.