最適輸送理論の解説論文とか書籍へのリンクのまとめ

はじめに

メモとして。WGANの勉強にもなるかなと。

おわりに

最適輸送理論、とても難しい。数学者はすごい。

密度比推定まわりの書籍・解説記事・論文・ソフトウェアの各種情報まとめ

はじめに

密度比推定の文献については、すでに山田氏による素晴らしいまとめ記事がある。同記事「はじめに」より、確率密度比推定の有用性を引用すれば、

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

というわけである。しかしながら、同記事は2012年に書かれたもので、本記事の執筆時点の2018年ではリンク切れなど、一部の情報が古くなっている。そのため、これら情報を更新したいということ。また、2012年以降、いくつか研究の進展が見られたので個人的に気になった論文を備忘録としてまとめておきたいということ。以上が本記事の動機である。

以下、山田氏のまとめ記事からも情報を引っ張りつつまとめる。編集方針として、各文献のリンクの情報はできるだけ「本家」のものを採用した(つまり公式ページ)。また会議論文よりは雑誌論文を優先した。
専門家から見れば、あの論文が足りない、などの不満はあろうが、ご容赦願いたい。

書籍

  • Sugiyama et al., Density Ratio Estimation in Machine Learning Amazon
    • 確率密度比の直接推定について。2011年ごろまでの研究がまとまっている。
  • 井手 et al., 異常検知と変化検知 Amazon
    • 密度比推定に基づく異常検知や変化点検出のトピックが扱われている。

解説論文・解説記事

密度比推定

  • Sugiyama et al, "A Density-ratio Framework for Statistical Data Processing," vol. 1, pp. 183-208, 2009. Link
  • 杉山, "密度比に基づく機械学習の新たなアプローチ," 統計数理, vo. 58, no. 2, pp. 141–155, 2010. PDF
  • Sugiyama et al, "Density Ratio Estimation: A Comprehensive Review," 2010. Link
  • 統計的機械学習の新展開:確率密度比に基づくアプローチ PDF
  • 杉山, "密度比推定によるビッグデータ解析," 電子情報通信学会誌, vol. 97, no. 5, pp. 353–358, 2014. PDF
  • S. Mohamed, "Machine Learning Trick of the Day (7): Density Ratio Trick", 2018. Link

ダイバージェンス

  • Sugiyama et al, "Density-ratio matching under the Bregman divergence: a unified framework of density-ratio estimation," Annals of the Institute of Statistical Mathematics, vol. 64, no. 5, pp. 1009–1044, 2012. Link
  • Sugiyama, "Machine Learning with Squared-Loss Mutual Information," Entropy, vol. 15, no. 1, pp. 80-112, 2013. Link
  • Sugiyama et al., "Direct Divergence Approximation between Probability Distributions and Its Applications in Machine Learning," Journal of Computing Science and Engineering, vol. 7, no. 2, pp. 99-111, 2013. PDF
  • 杉山, "確率分布間の距離推定 : 機械学習分野における最新動向," 日本応用数理学会論文誌, vol. 23, no. 3, pp. 439-452, 2013. Link

論文

密度比推定法

p(x)/q(x)の推定
  • ロジスティック回帰
    • Qin, "Inferences for Case-Control and Semiparametric Two-Sample Density Ratio Models," Biometrika vol. 85, no. 3, pp. 619-630, 1998. Link
    • Bickel et al, "Discriminative learning for differing training and test distributions," Proceedings of the 24th international conference on Machine learning (ICML 2007), pp. 81-87, 2007. PDF
  • Kernel Mean Matching (KMM): 確率密度比のモデルをb(x)とした時に、p(x)とb(x)q(x)のモーメントが一致するようにモデルを学習。
    • Huang et al., "Correcting Sample Selection Bias by Unlabeled Data," Advances in Neural Information Processing Systems 19 (NIPS 2006), pp. 601-608, 2006. Link
  • Kullback-Leibler Importance Estimation Procedure (KLIEP): 確率密度比を線形モデルで直接推定する手法。真の確率密度比と線形モデルとのカルバックライブラー距離が最小になるように、モデルパラメータを学習。
    • Sugiyama et al., "Direct Importance Estimation with Model Selection and Its Application to Covariate Shift Adaptation," Advances in Neural Information Processing Systems 20 (NIPS 2007), pp. 1433-1440, 2007. Link
    • Nguyen et al., "Estimating Divergence Functionals and the Likelihood Ratio by Convex Risk Minimization," IEEE Transactions on Information Theory, vol. 56, no. 11, 2010. Link
  • Unconstrained Least-Squares Importance Fitting (uLSIF): 確率密度比を線形モデルで直接推定する手法。真の確率密度比と線形モデルの二乗距離が最小になるように、モデルパラメータを学習。線型方程式を解くことによりモデルパラメータを推定できるため大変高速。
    • Kanamori et al., "A Least-squares Approach to Direct Importance Estimation," The Journal of Machine Learning Research, vol. 10, 2009. Link
  • Relative uLSIF (RuLSIF): 相対密度比 {p(x)/(a p(x) + (1-a)q(x)), 0 <= a < 1}を推定する手法。a = 0の時はuLSIFと同じになる。
    • Yamada et al., "Relative Density-Ratio Estimation for Robust Distribution Comparison," Neural Computation, vol. 25, no. 5, pp. 1324–1370, 2013. Link
p(x,y)/(p(x)p(y))の推定
  • Maximum Likelihood Mutual Information (MLMI): KLIEPの相互情報量版。相互情報量の推定に有用。
    • Suzuki et al., "Mutual information approximation via maximum likelihood estimation of density ratio," 2009 IEEE International Symposium on Information Theory, pp. 463-467, 2009. Link
  • Least-Squares Mutual Information (LSMI): uLSIFの相互情報量版。二乗損失相互情報量を高速に推定可能。
    • Suzuki et al., "Mutual information estimation reveals global associations between stimuli and biological processes," BMC Bioinformatics, vol. 10, no. 1, 2009. Link
p(x,y)/p(y)の推定
  • Least-Squares Conditional Density Estimation (LSCDE): yが連続値の場合の条件付き確率を直接推定する手法。
    • Sugiyama et al., "Least-Squares Conditional Density Estimation," IEICE Transactions on Information and Systems, vol. E93-D, no. 3, pp. 583-594, 2010. Link
  • Least-Squares Probabilistic Classifier (LSPC): yが離散値の場合(識別問題)の条件付き確率を直接推定する手法。
    • Sugiyama et al., "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. Link

応用

共変量シフト適応

  • Sugiyama et al., "Covariate Shift Adaptation by Importance Weighted Cross Validation," The Journal of Machine Learning Research, vol.8, pp. 985-1005, 2007. Link
  • Shimodaira, "Improving predictive inference under covariate shift by weighting the log-likelihood function," Journal of Statistical Planning and Inference, vol. 90, no. 2, pp. 227-244, 2010. Link

外れ値検出

  • Smola et al., "Relative Novelty Detection," Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS) 2009, pp. 536-543, 2009. Link
  • Hido et al., "Statistical outlier detection using direct density ratio estimation," Knowledge and Information Systems, vol. 26, no. 2, pp. 309-336, 2011. Link
  • Nam et al., "Direct Density Ratio Estimation with Convolutional Neural Networks with Application in Outlier Detection," IEICE Transactions on Information and Systems, vol. E98-D, no. 5, pp. 1073-1079, 2015. Link
  • Plessis et al., "Online Direct Density-Ratio Estimation Applied to Inlier-Based Outlier Detection," Neural Computation, vol. 27, no.9, pp. 1899-1914, 2015. PDF

変化点検出

  • Kawahara et al., "Sequential change-point detection based on direct density-ratio estimation," Statistical Analysis and Data Mining, vol. 5, no. 2, 2011. Link
  • Song et al., "Change-point detection in time-series data by relative density-ratio estimation," Neural Networks, vol. 43, pp. 72-83, 2013. Link
  • Yamada et al, "Change-point detection with feature selection in high-dimensional time-series data," Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2013), pp. 1827-1833, 2013. PDF

マルコフネットワークの構造変化検知

  • Song et al., "Direct Learning of Sparse Changes in Markov Networks by Density Ratio Estimation," Neural Computation, vol. 26, no. 6, pp.1169-1197, 2014. Link

十分次元削減

  • Yamada et al., "Computationally Efficient Sufficient Dimension Reduction via Squared-Loss Mutual Information," Proceedings of the Second Asian Conference on Machine Learning (ACML2011), pp. 247-262, 2011. Link
  • Suzuki et al., "Sufficient Dimension Reduction via Squared-Loss Mutual Information Estimation," Neural Computation, vol. 25, no. 3, pp. 725-758, 2013. Link

次元削減

  • Sugiyama et al., "Direct density-ratio estimation with dimensionality reduction via least-squares hetero-distributional subspace search," Neural Networks, vol. 24, no. 2, pp. 183-198, 2011. Link

独立成分分析

  • Suzuki et al., "Least-Squares Independent Component Analysis," Neural Computation, vol. 23, no. 1, pp. 284-301, 2011. Link

クラスタリング

  • Sainui et al., "Direct Approximation of Quadratic Mutual Information and Its Application to Dependence-Maximization Clustering," IEICE Transactions on Information and Systems, vol. E96-D, no. 10, pp. 2282-2285, 2013. Link

二標本検定

  • Sugiyama et al, "Least-squares two-sample test," Neural Networks, vol. 24, no. 7, pp. 735-751, 2011. Link

Generative adversarial network

  • Uehara et al., "Generative Adversarial Nets from a Density Ratio Estimation Perspective," arXiv preprint arXiv:1610.02920, 2016. Link
  • Mohamed et al., "Learning in Implicit Generative Models," arXiv preprint arXiv:1610.03483, 2016. Link

音声区間検出

  • 太刀岡 et al., "音声と騒音の密度比推定を用いた音声区間検出法,'' 電気学会論文誌C, vol. 133, no. 8, pp. 1549-1555, 2013. Link

話者認識

  • Yamada, "Kernel Methods and Frequency Domain Independent Component Analysis for Robust Speaker Identification," Doctor Thesis, Department of Statistical Science, The Graduate University for Advanced Studies, Hayama, Japan, 2010. Link
  • Yamada et al., "Semi-supervised speaker identification under covariate shift," Signal Processing, vol.90, no.8, pp.2353-2361, 2010. Link

二乗損失相互情報量

  • Yamada et al., "Cross-Domain Matching with Squared-Loss Mutual Information," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 9, pp. 1764-1776, 2015. Link
  • Sakai et al., "Estimation of Squared-Loss Mutual Information from Positive and Unlabeled Data," arXiv preprint, arXiv:1710.05359, 2017. Link

その他(必ずしも密度比推定ではないが)

  • Song et al., "Trimmed Density Ratio Estimation," arXiv preprint, arXiv:1703.03216, 2017. Link
密度微分推定
  • Sasaki et al., "Direct Density Derivative Estimation," Neural Computation, vol. 28, no. 6, pp. 1101-1140, 2016. Link
  • 佐々木 et al., "確率密度微分の直接推定と機械学習への応用", 数理解析研究所講究録, vol. 1999, pp. 154-173, 2016. Link
密度差推定
  • Sugiyama et al., "Density-Difference Estimation," Neural Computation, vol. 25, no. 10, pp. 2734-2775, 2013. Link
スライド

ソフトウェア

おわりに

確率密度比推定は勉強していて楽しい。

novelty detectionのサーベイ論文

A review of novelty detection
A review of novelty detection - ScienceDirect
http://www.robots.ox.ac.uk/~davidc/pubs/NDreview2014.pdf

MinimalRNNをTensorFlowで実装した(だけ)

もはや「実装した」と呼べるかどうか。既存のコードを少しいじっただけなので。

論文を要約すると以下の通りである。

各種ベンチマークによる検証は各自で(手抜き)。

Simple Recurrent Unit をTensorFlowで実装した

論文の主旨はRNN学習(例えばLSTM)の高速化であるが、上記実装は論文の式の通りにTensorFlowで組んだだけなので、実行速度は遅い。Chainerを用いた高速化実装はmusyoku氏の以下のブログ記事を参考にすると良い。
musyoku.github.io

Chaos Free NetworkをTensorflowで実装した

Multiplicative LSTM (Workshop Track in ICLR 2017)をTensorFlowで実装した

はじめに

表題の通り、ICLR 2017のWorkshop Trackで発表されたMultiplicative LSTMを実装した。

論文

実装

github.com

ICLR2017のレビューコメント

ここより引用する:

Comment: The paper presents a new way of doing multiplicative / tensored recurrent weights in RNNs. The multiplicative weights are input dependent. Results are presented on language modeling (PTB and Hutter). We found the paper to be clearly written, and the idea well motivated. However, as pointed out by the reviewers, the results were not state of the art. We feel that is that this is because the authors did not make a strong attempt at regularizing the training. Better results on a larger set of tasks would have probably made this paper easier to accept.

Pros:
- interesting idea, and reasonable results
Cons:
- only shown on language modeling tasks
- results were not very strong, when compared to other methods (which typically used strong regularization and training like batch normalization etc).
- reviewers did not find the experiments convincing enough, and felt that a fair comparison would be to compare with dynamic weights on the competing RNNs.

  • 他手法と比較したときに、有効性を示すには実験結果がまだちょっと弱い
  • 評価タスクが言語モデルだけで行われており、手法の比較もまだ足りない

先行研究 : Multiplicative RNN (mRNN) *1

1時刻前の隠れ状態に掛けられる重み行列$W_{hh}$を(テンソル的に)分解し、当該時刻の入力に依存するように拡張したもの。character-levelの言語モデリングに有効性が示されている。また、生成モデルとして用いて文章を生成した実験結果から、mRNNが高次の言語的構造、文法的構造を捉えていることが示された。

拡張前

\begin{eqnarray}
\hat{h}_{t} &=& W_{hh} h_{t-1} + W_{hx}x_{t}
\end{eqnarray}

拡張後

\begin{eqnarray}
m_{t} &=& (W_{mx} x_{t}) \odot (W_{mh} h_{t-1})\\
\hat{h}_{t} &=& W_{hm} m_{t} + W_{hx}x_{t}
\end{eqnarray}

なぜ Multiplicative なのか?

積の形にすることで、コンテキストと文字の共起関係(conjunction)を表現している。同時確率的な。

LSTM

論文の中で著者らは以下のLSTM形式を用いた。通常用いられるものとは若干異なる点に注意。$h_{t}$の計算も、活性化関数に通す前にゲートの処理をしているが、何故これで良いのか定性的な説明は(論文中に)あまりないように思う。


\begin{eqnarray}
\hat{h}_{t} &=& W_{hm} m_{t} + W_{hx} x_{t} \\
i_{t} &=& \sigma (W_{ix} x_{t} + W_{ih} h_{t-1}) \\
o_{t} &=& \sigma (W_{ox} x_{t} + W_{oh} h_{t-1})\\
f_{t} &=& \sigma (W_{fx} x_{t} + W_{fh} h_{t-1}) \\
c_{t} &=& f_{t} \odot c_{t-1} + i_{t} \odot \hat{h}_{t} \\
h_{t} &=& \tanh(c_{t} \odot o_{t})
\end{eqnarray}

提案手法

先行研究として提案されたmultiplicative RNNの仕組みを上記のLSTMに導入したモデル。


\begin{eqnarray}
m_{t} &=& (W_{mx} x_{t}) \odot (W_{mh} h_{t-1}) \\
\hat{h}_{t} &=& W_{hm} m_{t} + W_{hx}x_{t} \\
i_{t} &=& \sigma (W_{ix} x_{t} + W_{im} m_{t}) \\
o_{t} &=& \sigma (W_{ox} x_{t} + W_{om} m_{t})\\
f_{t} &=& \sigma (W_{fx} x_{t} + W_{fm} m_{t})
\end{eqnarray}

$W_{mx}$と$W_{mh}$の分、パラメータ数は増える。先のレビューの通り、性能が劇的に向上するというわけではないので、タスクを選ぶネットワーク構造なのかもしれない。

参考文献

  1. I. Sutskever, J. Martens, and G. E. Hinton. Generating text with recurrent neural networks. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pp. 1017–1024, 2011.

*1:参考文献 1