Vol.27 No.4 (2012/07) 確率密度比に基づく機械学習
(Machine Learning based on Density Ratio)


私のブックマーク

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

(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)

入力空間の中から出力と独立な部分空間を探す次元削減手法。独立性を測るのにLSMIが有用。

Suzuki+, Sufficient Dimension Reduction via Squared-loss Mutual Information Estimation, AISTATS 2010, pp.804-811. [30]
Yamada+, Computationally Efficient Sufficient Dimension Reduction via Squared-Loss Mutual Information, ACML 2011, pp.247-262. [31]

その他

確率密度比推定は二標本検定、異ドメイン間オブジェクト適合、因果推論等の問題にも有用。

Yamada+, Dependence minimizing regression with model selection for non-linear causal inference under non-Gaussian noise, AAAI 2010, pp.643-648. [32]
Yamada+, Cross-Domain Object Matching with Model Selection, AISTATS 2011, pp.807-815. [33]
Sugiyama+, Least-squares two-sample test, Neural Networks, vol.24, no.7, pp.735-751, 2011 [34]

5.ソフトウェア

確率密度比推定手法のソフトウェア (Matlab)は杉山先生のホームページから入手することができる。

6.国際会議

確率密度比推定の論文は主に機械学習系の国際会議やジャーナルから入手することができる。

主な研究者

国内外の確率密度比に関連する研究をしている主な研究者を紹介する。

確率密度比全般
共変量シフト
  • 下平 英寿 教授 (大阪大学)

  • Mehryar Mohri, Professor (New York University) [42]

  • Shai Ben-David, Professor (University of Waterloo) [43]

  • John Blitzer, Research Scientist (Google) [44]

おわりに

本稿では、確率密度比に関係する解説記事やソフトウェアを紹介した。このブックマークが、確率密度比に関心のある方々の参考になれば幸いである。

謝辞

本稿を執筆するにあたり、相談に乗っていただきました東京工業大学の杉山将准教授およびDisney Research Pittsburghの白鳥貴亮博士に感謝いたします。

[1] http://sugiyama-www.cs.titech.ac.jp\/\~sugi\/2010\/DensityRatioReview-jp.pdf
[2] http://www.youtube.com/watch?v=RLMgw8AVRyY
[3] http://www.cambridge.org/aus/catalogue/catalogue.asp?isbn=9780521190176
[4] http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=12795
[5] http://biomet.oxfordjournals.org/content/85/3/619.full.pdf+html
[6] http://domino.mpi-inf.mpg.de/intranet/rg2/rg2publ.nsf/6a06bf33407d587ec12565dd006fb8de/95affc61f8132a45c1257348002bc112/$FILE/bickel_icml_2007.pdf
[7] http://books.nips.cc/papers/files/nips19/NIPS2006_0915.pdf
[8] http://sugiyama-www.cs.titech.ac.jp/~sugi/software/KLIEP/index.html
[9] http://books.nips.cc/papers/files/nips20/NIPS2007_0232.pdf
[10] http://www.stat.lsa.umich.edu/~xuanlong/Papers/Nguyen-Wainwright-Jordan-10.pdf
[11] http://sugiyama-www.cs.titech.ac.jp/~sugi/software/uLSIF/index.html
[12] http://jmlr.csail.mit.edu/papers/volume10/kanamori09a/kanamori09a.pdf
[13] http://sugiyama-www.cs.titech.ac.jp/~sugi/2012/KuLSIF-statistical.pdf
[14] http://sugiyama-www.cs.titech.ac.jp/~yamada/RuLSIF.html
[15] http://books.nips.cc/papers/files/nips24/NIPS2011_0418.pdf
[16] http://sugiyama-www.cs.titech.ac.jp/~sugi/software/MLMI/index.html
[17] http://sugiyama-www.cs.titech.ac.jp/~sugi/2009/ISIT2009.pdf
[18] http://sugiyama-www.cs.titech.ac.jp/~sugi/software/LSMI/index.html
[19] http://www.biomedcentral.com/content/pdf/1471-2105-10-S1-S52.pdf
[20] http://sugiyama-www.cs.titech.ac.jp/~sugi/software/LSCDE/index.html
[21] http://jmlr.csail.mit.edu/proceedings/papers/v9/sugiyama10a/sugiyama10a.pdf
[22] http://sugiyama-www.cs.titech.ac.jp/~sugi/software/LSPC/
[23] http://sugiyama-www.cs.titech.ac.jp/~sugi/2010/LSPC.pdf
[24] http://www.sciencedirect.com/science/article/pii/S0378375800001154

[25] http://jmlr.csail.mit.edu/papers/volume8/sugiyama07a/sugiyama07a.pdf
[26] http://sugiyama-www.cs.titech.ac.jp/~sugi/2011/LSOD.pdf
[27] http://jmlr.csail.mit.edu/proceedings/papers/v5/smola09a/smola09a.pdf
[28] http://sugiyama-www.cs.titech.ac.jp/~sugi/2011/CDKLIEP.pdf
[29] http://arxiv.org/abs/1203.0453
[30] http://sugiyama-www.cs.titech.ac.jp/~sugi/2010/AISTATS2010b.pdf
[31] http://jmlr.csail.mit.edu/proceedings/papers/v20/yamada11/yamada11.pdf
[32] http://sugiyama-www.cs.titech.ac.jp/~sugi/2010/AAAI2010.pdf
[33] http://jmlr.csail.mit.edu/proceedings/papers/v15/yamada11a/yamada11a.pdf
[34] http://sugiyama-www.cs.titech.ac.jp/~sugi/2011/LSTT.pdf
[35] http://nips.cc/
[36] http://www.aistats.org/
[37] http://jmlr.csail.mit.edu/
[38] http://www.springer.com/computer/ai/journal/10994
[39] http://sugiyama-www.cs.titech.ac.jp/~sugi/
[40] http://www.math.cm.is.nagoya-u.ac.jp/~kanamori/
[41] http://www.simplex.t.u-tokyo.ac.jp/~s-taiji/
[42] http://cs.nyu.edu/~mohri/
[43] http://www.cs.uwaterloo.ca/~shai/
[44] http://john.blitzer.com/