ぱらぱらめくる『Density Ratio Estimation In Machine Learning』

Density Ratio Estimation in Machine Learning

• ２つの分布推定をするより、分布の比を知るだけなら、分布の比の分布推定(を１個)する方がうまく行く(Vapnik's principle)から、機械学習でそれをやろう、という話
• 目次
  • Part I Density-Ratio Approach to Machine Learning
  • Part II Methods of Density-Ratio Estimation
  • Part III Applications of Density Rations in Machine Learning
  • Part IV Theoretical Analysis of Density-Ratio Estimation
  • Part V Conclusions
• 細目次
  • Part I Density-Ratio Approach to Machine Learning
    • 1 Introduction
  • Part II Methods of Density-Ratio Estimation
    • 2 Density Estimation
    • 3 Moment Matching
    • 4 Probabilistic Classification
    • 5 Density Fitting
    • 6 Density-Ratio Fitting
    • 7 Unified Framework
    • 8 Direct Density-Ratio Estimation with Dimensionality Reduction
  • Part III Applications of Density Rations in Machine Learning
    • 9 Importance Sampling
    • 10 Distribution Comparison
    • 11 Mutual Information Estimation
    • 12 Conditional Probability Estimation
  • Part IV Theoretical Analysis of Density-Ratio Estimation
    • 13 Parametric Convergence Analysis
    • 14 Non-Parametric Convergence Analysis
    • 15 Parametric Two-Sample Test
    • 16 Non-Parametric Numerical Stability Analysis
  • Part V Conclusions
    • 17 Conclusions and Future Directions
• 1 Introduction
  • 機械学習の分類
    • Supervised
    • Unsupervised
    • Reinfocement
  • 機械学習に関連する考え方・アプローチ
    • Model selection,Active learning,Dimensionality reduction
    • Visualization,Clustering,Outlier detection,Independent component analysis
    • Decision-making
  • Density-Ratioを扱うのはどうしてか
    • 分布が推定できれば大概のことはできる
    • 問題は分布の推定は難しい、ということ
  • Density-Ratioアプローチの適用対象例(今回、特にわかりたいものには*を付与)
    • *Non-stationarity adaptation
      • 教育用データとそれを用いて推定する標本とが同一分布でなくてもなんとかする
    • Multi-task learning
      • 複数のタスクを一緒にとくことで精度を上げる
    • Outlier detection
    • Two-sample test
      • ふたつの分布の異同を見る
    • Change-point detection in time series
    • *Conditional density estimation
      • 事前確率分布・事後確率分布
    • Probabilistic classification
    • *Mutual information推定
      • 独立性検定
      • 変数選択
      • クラスタリング
      • マッチング
      • Dimensionality reduction
      • Independent component analysis
      • Causality learning
  • Density-Ratio Learningのアルゴリズム(たった５行です、と著者の(１人の)杉山先生が口演で話されていました)
    • Density estimation とは(第２章)
      • を分子・分母の分布を推定せずに直接推定すること
    • Moment matchingを使う方法。２分布が同一である、というのは、すべてのMomentが matchするということ。のモーメントがマッチするということを使ってを推定する。ただし、そんなにうまく行かないので、universal reproducing kernel Hilbert spaceを使う(第３章)
    • Probabilistic classifierを援用する。が成り立つから、のときに、分子分布から来たか、分母分子から来たかの確率がわかるなら、それがDensity ratio推定値。ロジスティック回帰やLeast-squares probabilistic classifier(LSPC)が使える(第４章)。ロジスティック回帰は仮定するモデルが正しいときにはsemi-parametric estimatorsの中では最適なことが知られているが、LSPCの方が計算効率はよい。…この回帰がいまいちなので、Density-Ratioが推定したいのだが、大丈夫だろうか。
    • Density fitting法では、のKullback-Leibler divergenceを最小化するようにDensity ratioを推定する。Moment matchingがという等式からのずれを最小化するのと比べれば、「最適化対象の式」が違う(だけ)。KL importance estimation procedure。手法としては、線形手法、カーネル手法、ログリニア手法、Gaussian mixture手法、PCA-mixture手法などが提唱されている
    • Density-ratio fittingは「直接には観察されていない」ratioを表す関数を推定する方法(第６章)
• で、一番の押しはLSPCらしい
  • その押しの理由は、線形計算で速いから
  • 速い部分は行列・逆行列演算。そこが速いので、その手前で2種類のパラメタの最適化をしなくてはならないが、なんとかなる、と、そういう作りらしい
  • 肝の部分のMATLABソース(こちら)のR対応のためのメモ

n <- 500
x <- rnorm(n)
y <- rnorm(n) + 1

x2 <- x^2
y2 <- y^2
xx <- matrix(rep(x2,n),ncol=n)
xx <- xx + t(xx)
xx <- xx - 2 * x %*% t(x)


yx <- matrix(rep(y2,n),ncol=n)
yx <- yx + t(matrix(rep(x2,n),ncol=n))
yx <- yx - 2 * y %*% t(x)

r <- exp(-yx)
tmp.mean <- apply(exp(-xx),1,mean)
tmp.solve <- solve(t(r) %*% r + diag(rep(1,n)),tmp.mean)

s <- r %*% tmp.solve

s <- s/sum(s)

plot(y,s)

dx <- dnorm(y)
dy <- dnorm(y,1)

plot(y,dx/(dx+dy),ylim=c(0,1))
points(y,s,col=2)

nx <- 10
ny <- 13

s <- 1

x <- rnorm(nx)
y <- rnorm(ny)+0.5

G <- matrix(0,nx,nx)
for(i in 1:nx){
	for(j in 1:nx){
		G[i,j] <- 1/ny * sum(exp(-sum((y-x[i])^2+(y-x[j])^2)/2*s^2))
	}
}


h <- rep(0,nx)
for(i in 1:nx){
	h[i] <- 1/nx * sum(-(x-x[i])^2/2*s^2)
}

lambda <- 1

solve(G + diag(rep(lambda,nx))) %*% h