Vol.27 No.4 (2012/07) 確率密度比に基づく機械学習 (Machine Learning based on Density Ratio) – 人工知能学会 (The Japanese Society for Artificial Intelligence)

私のブックマーク

確率密度比に基づく機械学習

(Machine Learning based on Density Ratio)

東京工業大学　大学院情報理工学研究科　計算工学専攻山田　誠 (Makoto Yamada)
URL: http://sugiyama-www.cs.titech.ac.jp/~yamada

1.はじめに

パターン認識、ドメイン適応、外れ値検出、変化点検出、次元削減、因果推論等の様々な機械学習の問題が確率密度比(確率密度関数の比)の問題として定式化できることから、近年、確率密度比に基づいた機械学習の研究が機械学習およびデータマイニングの分野において大変注目されている。本ブックマークでは確率密度比の研究開発のための有用なリソースを紹介する。

2.解説記事等

密度比に基づく機械学習の新たなアプローチ　統計数理, vol.58, no.2, pp.141-155, 2010. [1]: 杉山先生による確率密度比の解説記事。
確率密度比を用いた新しい機械学習アルゴリズム (YouTube), Google Tech Talk. [2]: 杉山先生による確率密度比の紹介+確率密度比の応用(話者識別、教科学習)に関する講演。
Density Ratio Estimation in Machine Learning, Cambridge University Press, Cambridge, UK, 2012. [3]: 確率密度比推定研究のバイブル。2011年までの研究成果はほぼすべてこの本から知ることができる。
Machine Learning in Non-Stationary Environments: Introduction to covariate shift adaptation, Cambridge, MA, USA: MIT Press, 2012. [4]: 共変量シフト適応の専門書。

3.確率密度比推定手法

確率密度比推定とは、確率密度推定を介さずに、直接確率密度比を推定する手法である。ここでは代表的な確率密度比およびその推定手法を紹介する。

p(x)/q(x)の推定 (応用: 共変量シフト、外れ値検出、変化点検出等)

(カーネル) ロジスティック回帰:

p(x)をクラス1(y = 1)の確率密度関数、q(x)をクラス2(y = 2)の確率密度関数とし、ロジスティック回帰を用いて事後確率p(y = 1 | x) = p(x)/(p(x) + q(x))およびp(y = 2 | x) = q(x)/(p(x) + q(x))を推定。最後に、p(x)/q(x) = p(y = 1 | x)/p(y = 2 | x)として確率密度比を推定。

Qin, Inferences for case-control and semiparametric two-sample density ratio models, Biometrika, 85(3):619-639, 1998. [5]
Bickel+, Discriminative
learning for differing training and test distributions, ICML, pp. 81-88, 2007. [6]

Kernel Mean Matching (KMM):

確率密度比のモデルをb(x)とした時に、p(x)とb(x)q(x)のモーメントが一致するようにモデルを学習。

Huang+, Correcting Sample Selection Bias by Unlabeled Data, NIPS, pp.601-608, 2006. [7]

Kullback-Leibler Importance Estimation Procedure (KLIEP) (Matlab code [8]):

確率密度比を線形モデルで直接推定する手法。真の確率密度比と線形モデルとのカルバックライブラー距離が最小になるように、モデルパラメータを学習。

Sugiyama+, Direct importance estimation with model selection and its application to covariate shift adaptation, NIPS, pp.1433-1440, 2008. [9]
Nguyen+, Estimating Divergence Functionals and the
Likelihood Ratio by Convex Risk Minimization, IEEE Transactions on information theory, vol. 56, no. 11, pp. 5847-5861, 2010. [10]

Unconstrained Least-Squares Importance Fitting (uLSIF) (Matlab code [11]):

確率密度比を線形モデルで直接推定する手法。真の確率密度比と線形モデルの二乗距離が最小になるように、モデルパラメータを学習。線型方程式を解くことによりモデルパラメータを推定できるため大変高速。

Kanamori+, A least-squares approach to direct importance estimation, Journal of Machine Learning Research, vol.10 (Jul.), pp.1391-1445, 2009. [12]
Kanamori+, Statistical analysis of kernel-based least-squares density-ratio estimation, Machine Learning, vol.86, no.3, pp.335-367, 2012. [13]

Relative uLSIF (RuLSIF) (Matlab code [14]):

相対密度比 {p(x)/(a p(x) + (1-a)q(x)), 0 <= a < 1}を推定する手法。a = 0の時はuLSIFと同じになる。

Yamada+, Relative density-ratio estimation for robust distribution comparison, NIPS, pp.594-602, 2011. [15]

p(x,y)/(p(x)p(y))の推定 (応用: 特徴選択、次元削減、因果推論等)

Maximum Likelihood Mutual Information (MLMI) (Matlab code [16]):

KLIEPの相互情報量版。相互情報量の推定に有用。

Suzuki+, Mutual information approximation via maximum likelihood estimation of density ratio, ISIT, pp.463-467, 2009. [17]

Least-Squares Mutual Information (LSMI) (Matlab code [18]):

uLSIFの相互情報量版。二乗損失相互情報量を高速に推定可能。

Suzuki+, Mutual information estimation reveals global associations between stimuli and biological processes, BMC Bioinformatics, vol.10, no.1, pp.S52, 2009. [19]

p(x,y)/p(y)の推定 (応用: パターン認識、条件付確率推定)

Least-Squares Conditional Density Estimation (LSCDE) (Matlab code [20]):

yが連続値の場合の条件付き確率を直接推定する手法。

Sugiyama+, Conditional density estimation via least-squares density ratio estimation, AISTATS, pp.781-788, 2010. [21]

Least-Squares Probabilistic Classifier (LSPC) (Matlab code [22]):

yが離散値の場合(識別問題)の条件付き確率を直接推定する手法。

Sugiyama, Superfast-Trainable Multi-Class Probabilistic Classifier
by Least-Squares Posterior Fitting, IEICE Transactions on Information and Systems, vol.E93-D, no.10, pp.2690-2701, 2010. [23]

4.確率密度比応用

ここでは代表的な確率密度比推定手法の応用を紹介する。

共変量シフト適応

共変量シフトとは、訓練時の入力分布(確率密度関数 p(x))とテスト時の入力分布(確率密度関数 q(x))が異なるが条件付き確率p(y|x)は訓練時とテスト時で変化しないとする仮定。共変量シフト適応とは、各訓練サンプルxを重要度重みq(x)/p(x)で重み付けすることにより、共変量シフト下でのモデルのバイアスを減らす方法。確率密度比推定は重要度重みの推定に使用される。

Shimodaira, Improving predictive inference under covariate shift by weighting the log-likelihood function, Journal of Statistical Planning and Inference, 90, pp.227-244, 2000. [24]
Sugiyama+, Covariate shift adaptation by importance weighted cross validation,
Journal of Machine Learning Research, vol.8 (May), pp.985-1005, 2007. [25]

外れ値検出

サンプルxが外れ値の場合には確率密度比p(x)/q(x)が小さくなることを利用して外れ値を検出 (p(x):外れ値を含まないデータの確率密度関数、q(x): 外れ値を含んだデータの確率密度関数)。

Hido+, Statistical outlier detection using direct density ratio estimation, Knowledge and Information Systems, vol.26, no.2, pp.309-336, 2011. [26]
Smola+, Relative Novelty Detection, AISTATS 2009, pp.536-543. [27]

変化点検出

確率密度比推定を用いて推定したカルバックライブラー情報量等(KL(p_t(x)||q_t(x)))の指標を用いて変化点を検出 (p_t(x): 時間tの直前のデータの確率密度関数、q_t(x): 時間tの直後のデータの確率密度関数)。変化点でない場合にはp_t(x)とq_t(x)が同じとなり、KL(p_t(x)||q_t(x)) = 0となる。一方で変化点の場合には、KL(p_t(x)||q_t(x)) > 0となる。

Kawahara+, Change-point detection based on direct density-ratio estimation, Statistical Analysis and Data Mining, Vol.5, No.2, pp.114-127. [28]
Song+, Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation, arXiv:1203.0453v1. [29]

十分次元削減 (Sufficient Dimension Reduction)