ＩＢＩＳ２００８

２００８年１０月２９日～３１日

密度比推定の手法と応用
杉山将（東工大）

重点サンプリング
確率密度に関する期待値を，別の確率密度を用いて計算する統計手法
から標本を取るのが難しいとき，代わりに簡単な分布から標本を取る．

密度比2本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
z パターン認識，非定常環境下での適応学習，ドメイン適応，マルチタスク学習，異常値検出，時系列の変化点検知，特徴選択，次元削減，独立成分分析，条件付き確率推定，二標本検定など

2. 密度比推定の手法
3. 実験

3

例：非定常環境下での適応学習

4

共変量シフト：訓練時とテスト時で入力分布が変化するが，入出力関数は不変
z ロボット制御則の獲得

Shimodaira (JSPI2000)

z アンケートデータの学習
z 脳波，音声，言語データの学習

入力分布

訓練データ関数テストデータ
学習したい関数共変量シフト下での学習

5

Shimodaira (JSPI2000), Sugiyama & Müller (Stat&Deci2007),
Sugiyama, Krauledat & Müller (JMLR2007)

通常の最小二乗法は 密度比重み付きの最小一致性がない
二乗法は一致性がある

訓練誤差（尤度）に基づく学習法全てに適応可能！

ドメイン適応とマルチタスク学習

6ドメイン適応：あるドメインでの学習結果を別のドメインでの学習に活用する
Storkey & Sugiyama (NIPS2006)
Tsuboi, Kashima, Hido, Bickel & Sugiyama (SDM2008)
一般会話

医療文章

マルチタスク学習：複数の似た問題を同時に解くことにより，それぞれを解くよりも良い解を得る
Bickel, Bogojeska, Lengauer & Scheffer (ICML2008)
薬ＡによるHIV治療効果

薬BによるHIV治療効果

薬CによるHIV治療効果同様な密度比重み付けによりうまく対応できる．

例：異常値検出7

異常値検出：標本に含まれる異常値を見つける
z 生産ラインの不良品検出
z ネットワークシステムへの不正侵入検出
z 文書集合からの新規トピック発見

確率密度の低い標本を異常値とみなす
0.40.3

異常値

0.20.10−5058

例：異常値検出（続き）

Hido, Tsuboi, Kashima & Sugiyama (ICDM2008)

異常値は密度比が小さい
0.40.30.2
0.1
01−5050.50.40.30

異常値

0.20.10−505−505

9

時系列の変化点検知
Kawahara & Sugiyama (IBIS2008)

時系列の傾向が変化する点を検知する
時間
密度比を逐次的に計算：

時間

10

例：特徴選択特徴選択：入出力関係
出力 を最もよく説明する入力変数

で，を選ぶ

z 遺伝子選択，脳の活動部位の特定，創薬など

1050−5−10−505相互情報量に基づく独立性判定

11Suzuki, Sugiyama, Sese & Kanamori (FSDM2008)

相互情報量：相互情報量がゼロと は独立

相互情報量は密度比を用いて計算できる．
特徴選択，独立成分分析などに適用可12

例：条件付き確率推定

回帰分析：条件付き期待値の推定法
条件付き分布が複雑なときは，回帰分析では情報不足
6z 非対称性

5z 不等分散性

Duration time [minutes]

z 多峰性

432
1
040

50

60708090

Weighting time [minutes]

条件付き確率そのものを推定したい！

100

例：条件付き確率推定（続き）

13

Sugiyama, Takeuchi, Suzuki, Kanamori & Hachiya (準備中)条件付き確率は，密度比を用いて計算できる．

本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
z Kullback-Leibler Importance EstimationProcedure (KLIEP)z Least-Squares Importance Fitting (LSIF)z Unconstrained LSIF (uLSIF)

3. 実験

14

密度比の推定密度比が分かれば，色々な事ができる．
実用上は，密度比を標本から推定する必要がある．

ナイーブな方法：それぞれの密度を推定し，比を取る

15

Vapnikの原理
ある問題を解くとき，その問題よりも難しい問題を途中段階で解いてはならないが分かるが分かる

密度を求めるよりも，密度比を求めるほうが易しい！
密度推定を経由せず，密度比を推定することにする．

16

本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
z Kullback-Leibler Importance Estimation

Procedure (KLIEP)z Least-Squares Importance Fitting (LSIF)z Unconstrained LSIF (uLSIF)

3. 実験

17

Kullback-Leibler Importance
Estimation Procedure (KLIEP)

18

Sugiyama, Nakajima, Kashima, von Bünau & Kawanabe (NIPS2007)線形密度比モデル：（例：ガウスカーネル）

からのKLダイバージェンスを最小にするようにパラメータを学習KLIEP：解法

19

KL情報量の分解：定数は確率密度：
拘束条件

KLIEP：解法（続き）
期待値を標本平均で近似すれば，

これは凸最適化問題なので，
z 勾配上昇z 拘束充足を繰り返せば大域的最適解に収束
最適解はスパース！

20

KLIEP：収束性

21

Sugiyama, Suzuki, Nakajima, Kashima, von Bünau & Kawanabe (AISM2008)
Nguyen, Wainwright & Jordan (NIPS2007)

パラメトリックの場合:
z 標本から学習したパラメータは，最適な値にのオーダーで収束（少ない方の標本数）

ノンパラメトリックの場合：
z 標本から学習した関数は，真の関数により少し遅いオーダーで収束（関数集合のブラケッティングナンバーに依存）KLIEP：実行例

22

KLIEP：モデル選択

23

 ガウシアンの幅はどうやって決めればよいか？
 交差確認法：
z テスト標本を分割
グループ1

グループ2…

密度比を推定グループk-1

グループk

尤度を確認

z 全ての組み合わせに対して繰り返し，平均を出力

 これにより，KLの不偏推定量が得られる

KLIEP：尤度交差確認法の例
交差確認法
による推定値
真のKL（定数項は除く）

非常に精度が良い！

24

計算機実験の設定

25

 実験設定：ｄ次元データ，分散１の正規分布で平均はz 訓練： （０，０，０，．．．，０）z テスト： （１，０，０，．．．，０）

カーネル密度推定(KDE)：
z 訓練密度とテスト密度をそれぞれ推定z ガウシアンカーネルの幅は尤度交差確認法で決定

KLIEP：z ガウシアンカーネルの幅は交差確認法で決定Normalized MSE次元が増えたときの精度比較
KDE
KLIEP

次元
KDE：次元が増えると誤差は単調に増加
KLIEP：高次元でも比較的うまくいく

26

KLIEP：特徴27

比較的高次元でも精度がよい（Vapnikの原理）
スパースな大域的最適解が求まる
交差確認法によりモデル選択ができる分母と分子のドメインが異なってもいてもよい（相互情報量や条件付き確率の推定で重要）
ＫＬロスは，相互情報量（ＫＬダイバージェンス）推定と相性がよい対数線形密度比モデルを用いれば，分子のデータが大量の場合でも効率よく計算できる
Tsuboi, Kashima, Hido, Bickel & Sugiyama (SDM2008)本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
z Kullback-Leibler Importance Estimation

Procedure (KLIEP)z Least-Squares Importance Fitting (LSIF)z Unconstrained LSIF (uLSIF)3. 実験28

29

Least-Squares Importance Fitting(LSIF)
Kanamori, Hido & Sugiyama (NIPS2008)

線形密度比モデル：（例：ガウスカーネル）

二乗損失：

30

LSIF：解法
二乗損失の分解：定数

拘束条件：

LSIF：解法（続き）
期待値を標本平均で近似し，正則化項を加えれば

これは凸二次計画問題なので，標準的な二次計画ソルバーで大域的最適解が求まる
最適解はスパース！

31

LSIF：正則化パス追跡

解は正則化パラメータ全ての32に関して区分線形に対する解が効率よく計算できる！

LSIF：実行例

33

正則化パラメータとカーネル
幅は交差確認法で決定

正則化パス

LSIF：特徴
二乗ロスは条件付き確率推定には都合が良い（裾はあまり気にしない）
正則化パスが計算できるため計算効率が良いしかし，正則化パス計算は数値的にやや不安定

34本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
z Kullback-Leibler Importance Estimation

Procedure (KLIEP)z Least-Squares Importance Fitting (LSIF)z Unconstrained LSIF (uLSIF)

3. 実験

35

Unconstrained LSIF (uLSIF)

36

Kanamori, Hido & Sugiyama (NIPS2008)

LSIFを少し改変：
z 非負拘束を無視する
z 正則化項を２次にする

uLSIF：解法
解は解析的に計算できる！

無視した非負拘束は，事後補正する：
LSIFとuLSIFの解の差：z 正則化パラメータz ガウス幅が大きいとき，差が小さいが大きいとき，差が小さい

37

uLSIF：一つ抜き交差確認法

38

一つ抜き交差確認法：
標本1

標本2…

密度比を推定

標本n-1

標本n

誤差を確認

通常はｎ回繰り返して計算する必要があるが，uLSIFでは解析的に一発で計算できる（Sherman-Woodbury-Morrison公式を使う）
モデル選択を含めた計算時間が飛躍的に短縮される！

密度比推定法のまとめ

39

分子と分母の モデル
手法 密度推定
計算速度
ドメイン選択KDEあり
違っても良い あり
超速い
KMM
なし
同じなし やや遅い
LogRegなし
同じあり やや遅い
KLIEP
なし
違っても良い あり やや遅い
LSIF
速い
なし
違っても良い あり
uLSIFなし
違っても良い あり とても速い Kernel mean matching (KMM)
Huang, Smola, Gretton, Borgwardt & Schölkopf (NIPS2006)

 Logistic regression method (LogReg)
Qin (Biometrica1998), Cheng & Chu (Bernoulli2004)
Bickel, Brückner & Scheffer (ICML2007)本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
3. 実験z 共変量シフト適応
z 外れ値検出z 特徴選択z 条件付き確率推定

40

41

共変量シフト適応：
ブレイン・コンピュータインターフェース
Sugiyama, Krauledat & Müller (JMLR2007)

脳波(EEG)でコンピューターを操作する
入力は脳波，出力は左右の方向
分類規則をデータから学習する

訓練風景
画面に現れる指示に従って，左手／右手を動かすイメージをする．

動画：ドイツFraunhofer研究所提供

42

テスト風景43

左右の手を動かすイメージをすることにより，脳波でパッドを操作する

動画：ドイツFraunhofer研究所提供

実験結果（識別誤差）

44

被験者 試行 従来法 提案法KL

10.0 %0.762

訓練時とテスト時で精神状態が異なるため，
8.8 % 8.8 % 1.11
4.3 % 4.3 % 0.69
脳波の分布が変化．
40.0 % 40.0 % 0.97
39.3 % 38.7 % 1.05 KL：訓練・テスト入力分布25.5 % 25.5 % 0.43のＫＬ情報量の推定値
36.9 % 34.4 % 2.63
21.3 % 19.3 % 2.88 識別性能が向上

322.5 % 17.5 %1.25z 密度比重み付き線形判別分析

121.3 % 21.3 %9.23z 密度比重み付き交差確認法

22.4 %

2.4 %

5.58

36.4 %

6.4 %

1.83

1

21.3 % 21.3 %

0.79

2

15.3 % 14.0 %2.011123122
3
13459.3 %共変量シフト適応：話者識別45

 音声から話者を特定する． Yamada & Sugiyama (DMSS2008)
 音声データの分布は一定でない
z マイクや部屋の特性
z 話者の心理状況

 識別性能が向上
z 密度比重み付きロジスティック回帰z 密度比重み付き交差確認法

３ヵ月後
６ヵ月後９ヵ月後

従来法(1.5s)
13.9 %
18.0 %
8.3 %提案法(1.5s)
13.2 %
16.1 %
8.0 %

従来法(4.5s)
7.7 %
7.3 %
0.3 %

提案法
(4.5s)
7.4 %
6.3 %
0.1 %

共変量シフト適応：
強化学習によるロボット制御

46

Hachiya, Akiyama, Sugiyama & Peters (AAAI2008)

振り子ロボットz 状態
z 行動：振り子の角度，角速度：左に加速，右に加速ゴール：車を左右に動かして振り子を振り上げ，垂直な状態を維持する制御則を獲得

強化学習
強化学習：得られる報酬が最大になるように制御方策を学習報酬： 振り子の角度（振り子が上にあるほど報酬が大きい）47

強化学習における共変量シフト

48

価値関数
：状態 で行動 を取り，その後 に従って行動して得られる報酬和
方策反復法：現在の制御方策の価値関数を推定

方策を更新すると，制御方策を更新の分布が変わる！

49

実験結果
−6ν=0
ν=1
ν=^ν IWCV得られた報酬和
Sum of discounted rewards

−7

提案法

−8−9

従来法２−10−11−12従来法１−13−14−15102030

40

50

60

70

Total number of episodes

方策反復数

識別性能が向上
z 密度比重み付き最小二乗法
z 密度比重み付き交差確認法

8090

ドメイン適応：日本語単語分割

50

Tsuboi, Kashima, Hido, Bickel & Sugiyama (submitted)

適応元データ：会話辞典の例文
z （例）こんな／失敗／は／ご／愛敬／だ／よ／ ．

適応先データ：医療マニュアルz （例）細胞膜には受容体があり、これによって細胞を識別することができます．
手法Ｆ値

従来法92.30

提案法94.46

適応先ラベル有94.43

単語分割性能が向上z 密度比重み付き条件付き確率場(CRF)
z 密度比重み付き交差確認法

本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
3. 実験
z 共変量シフト適応
z 外れ値検出z 特徴選択z 条件付き確率推定51

異常値検出：USPS手書き数字

52

Hido, Tsuboi, Kashima & Sugiyama (ICDM2008)

５００００４８４５４

人間でも読みにくい数字がUSPSのテストデータには含まれている！

53

異常値検出：ハードディスク故障検出
Hido, Tsuboi, Kashima & Sugiyama (ICDM2008)

Self-Monitoring And Reporting Technology(SMART)：ハートディスクの故障検知
手法

One-class
提案法
SVM

AUC

0.881

0.843

LOF
近傍数5
近傍数30
0.847
0.924

z LOFは近傍数をうまく決めれば性能が良いが，モデル選択法がないz 提案法はモデル選択ができる！
One-class SVM:
LOF: Local outlier factor

Schölkopf, Platt, Shawe-Taylor,
Smola & Williamson (NeCo2001)
Breunig, Kriegel, Ng & Sander (SIGMOD2000)

変化点検知：呼吸データ

54

Kawahara & Sugiyama (IBIS2008)

もとの時系列密度比

密度比によって変化点が検知できている本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
3. 実験
z 共変量シフト適応
z 外れ値検出z 特徴選択z 条件付き確率推定

55

56

特徴選択：イースト菌細胞の分類

Suzuki, Sugiyama, Kanamori & Sese (BMC BIoinfomatics 2009)

KDE: Kernel density estimation
KNN: k-nearest neighbor
EDGE: Edgeworth expansion
PCC: Peason correlation
KNN: k-nearest neighbor mehtod
HSIC: Hilbert-Schmidt independence criterion

提案法

本発表の構成
1. 密度比は，重点サンプリングだけでなく，様々な統計的データ解析に役立つ！
2. 密度比推定の手法
3. 実験
z 共変量シフト適応
z 外れ値検出z 特徴選択z 条件付き確率推定57

条件付き確率推定：
ロボットの状態遷移推定

58

Sugiyama, Takeuchi, Suzuki, Kanamori & Hachiya (in preparation)状態遷移確率：状態 で行動 をとったときの行き先 の確率分布
Khereraロボット
z状態：左右の赤外線センサの値
z行動：左右のタイヤの回転速度

条件付き確率推定：
ロボットの状態遷移推定
相対対数尤度（大きいほうが良い）
データ
Khepera1
Khepera2
振り子1
振り子2
平均

提案法
1.07
1.02
1.92
1.92
1.48

KDE: Kernel density estimation
MDN: Mixture density network

KDE
0.80
0.78
1.64
1.62
1.21

MDN00000

Bishop (TechRep1994)

59

まとめ60密度比推定：統計的データ処理の新しい枠組みz パターン認識，非定常環境下での適応学習，ドメイン適応，マルチタスク学習，異常値検出，時系列の変化
点検知，特徴選択，次元削減，独立成分分析，条件付き確率推定，二標本検定など

密度比を直接推定する手法
z KLIEP, LSIF, uLSIF
z 必要最小限の問題を解いている（Vapnikの原理）

様々な応用例
z ブレイン・コンピュータインターフェース，ロボット制御，音声認識，自然言語，故障検知，バイオデータ解析

関連書籍
Quiñonero-Candela, Sugiyama,
Schwaighofer & Lawrence (Eds.),
Dataset Shift in Machine Learning,
MIT Press, 2008.
八谷大岳，杉山将強くなるロボティック・
ゲームプレイヤー の作り方，
毎日コミュニケーションズ, 2008

61