weak learnerとstrong leaner

　日本語だと、弱学習器と強識別器？

よく聞くけど厳密な定義を知らなかったので調べてみた。
そのあと、おもしろそうな問題を思いついたので解いてみた。

定義

とりあえず、weak leanerとstrong leanerの定義が分からなかったので調べてみました。

• weak leaner := a classifier which is only slightly correlated with the true classification
• strong learner := a classifier that is arbitrarily well-correlated with the true classification

思いついた問題

ある人は、60%の確率で必ず正しい判断をする。
迷ったときは、この人に判断を任せれば60%の確率で正しい道へ導いてくれる。
もし、同じような特性を持った人が３人いたとする。3人に相談して、意見の多かった案を採用すると正しい判断がえられる確率はいくらになるか？
　3人ではなく、11人いたらどうか？1001人いたら？

上の問題に対する答えがpositiveなものだったら、60%程度のパフォーマンスを発揮できる識別器をたくさんつくれば、非常に高パフォーマンスの識別器がえられるってことが感覚的に納得できる。（厳密に理解するためには、この論文を読むとよさそう。）

問題に対する解答

3人だったら、組み合わせの確率使えば紙とペンで解ける。答えは、64.8%。ややよくなったかなという感じ。
10人、1000人のときは自分で計算するのは大変なので、コンピュータにやってもらった。

import java.util.Scanner;


public class Main {
 private double p;    // each classifier's performance
 private int n;       // number of classifiers
 
 public Main(double p, int n) {
  this.p = p;
  this.n = n;
 }
 
 // calculate the ensemble classifier's performance
 public double calc() {
  double [][] dp = new double[n+1][n+1];
  dp[0][0] = 1.0;
  
  for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
    dp[i+1][j+1] += dp[i][j] * p;
    dp[i+1][j] += dp[i][j] * (1-p);
   }
  }
  
  double ret = 0;
  for (int i = n / 2 + 1; i <= n; i++)
   ret += dp[n][i];
  
  return ret;
 }
 
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  System.out.println("p = :");
  double p = sc.nextDouble();
  System.out.println("n = :");
  int n = sc.nextInt();
  
  double ret = new Main(p, n).calc();
  System.out.println(ret);
  
 }
}

11人だと、75.3%。1001人だと、99.9%。

今度、Random Forestの勉強しようかと思ってて、これだけ見ると、Decision Treeを1000本くらい作ればかなりの高パフォーマンスがえらるように感じるんだけど、実際やってみるといろいろ難しいことがあるんだろうな。。