機械学習における重大な"仮定"と、アルゴリズムの評価

Mahout

Mahoutシリーズを最初から読む場合はこちらApache Mahoutで機械学習してみるべ - 都元ダイスケ IT-PRESS。

さて、前回までで、実際にMahoutのレコメンデーションエンジンを動かしてみつつ、その計算原理を軽く追いかけました。今回は、機械学習全般における大事な前提について。

仮定がいっぱい

通常プログラムを書く場合は、事実や仕様に基づいて、正確にプログラミングすることを求められます。可能性の大小や、大ざっぱな計算などに依存したプログラミングはあまり書く機会がありません。例えばあるソフトで扱う業務で、土日祝日料金と平日料金というものがあったとします。これを「1週間のうち、だいたい5日が平日で2日が休日だよね、祝日とかたまにしかないから、考慮すると大変だし、いいよね、べつに」ってことにはなりません。多分。

しかし、機械学習は違います。気づいていないだけで、実はかなり大きな仮定と近似で成り立っています。地盤ゆるゆるです。

  • 類似度にピアソン相関係数という指標を採用してよい（人と人の間の類似度はピアソン相関係数ではかることができる、という仮定です。ピアソンで良いなんて、誰がいいました？ 他にもスピアマンとか色々理論はありますよ？）
  • 加重平均というアルゴリズム（ある人の好みは、他の人のそのアイテムに対する評価の（類似度を重さとした）加重平均で求めることができる、という仮定。加重平均って、相加平均*1がベースになったものですよね。平均にも色々あるんですけど。なぜ相乗平均や調和平均でなく、相加平均なんですか？）
  • 類似度ベスト2に絞るというやり方（結果は、Aさんにもっとも類似度が大きい人2人の加重平均でよい、という仮定。2人に限定しちゃっていいんですか？）
  • 類似度が大きい同士の好みは似ている（というのも、そもそも仮定なんです）


と、まぁ色々出て来ます。最後なんて、レコメンドの根底を揺るがす大事件ですよ。そもそも「事実」というのは、入力に使ったCSVのデータだけなのです。

ちなみに、これらの疑問に論理的に答えることはできません。きっちりとした事実に基づいて正しいロジックを用いて全てを計算しなければならないとしたら、機械学習なんて成り立たないんです。

というわけで、このような分野では「厳密にしすぎて結果が出ないくらいなら、仮定に基づいてでも何らかの意味のありそうな結果を出す」ことに重点を置きます。まずはやってみることが大事、ということで、上記の仮定に基づいて結果を出したわけです。

では、やってみたのは良いけれど、今後永遠にこの仮定に基づいたアルゴリズムだけでよいのか？ 他を試してみる必要はないのか？ と言われると、確かに試してみる必要性は感じます。実際に、運用で高い精度を出していくためには、継続的にアルゴリズムの見直しが必須になります。

だけど、試してみた結果、どっちが良いのかなんて、どうやって判定するんでしょうか？

レコメンデーションアルゴリズムの評価

理屈は簡単です。入力に使ったCSVデータのうち、いくつかのエントリを除去した上でデータモデルを作ります。その上で、評価を取り除いたアイテムについて、評価対象のアルゴリズムによって、予測評点を算出するのです。

除去した「リアル評点」と、算出した「予測評点」の差が小さければ小さいほど、良いアルゴリズムと言えます。例えば3つのエントリを除去して、3つのリアルと予測の差が出て来ます。これの平均値を評価結果とします。

org.apache.mahout.common.RandomUtils.useTestSeed(); // (A)
DataModel model = new FileDataModel(new File("src/main/resources/intro.csv"));
RecommenderEvaluator evaluator = new AverageAbsoluteDifferenceRecommenderEvaluator(); // (B)
RecommenderBuilder builder = new RecommenderBuilder() {
    
     @Override
     public Recommender buildRecommender(DataModel model) throws TasteException {
          UserSimilarity similarity = new PearsonCorrelationSimilarity(model);
          UserNeighborhood neighborhood = new NearestNUserNeighborhood(2, similarity, model);
          return new GenericUserBasedRecommender(model, neighborhood, similarity);
     }
};
double score = evaluator.evaluate(builder, null, model, 0.7, 1.0); // (C)
System.out.println("score=" + score);

上記のコードで、先日ご紹介したアルゴリズムの評価ができます。評価の結果 1.0 が得られたので、このアルゴリズムは平均で1.0の誤差があるよ、という意味になります。

コードのポイントを解説していきます。まず(A)ですが、評価には乱数を使います。というのも「いくつかのエントリを除去」する必要があるため、どのエントリを削除するのかを乱数で決めるのです。これによって評価の結果は実行する毎に異なると予測できます。今回はテストであるため、毎回同じ結果を出すために、乱数種を固定値で初期化するために、この(A)を実行しています。本番の評価では(A)は使いませんので注意。

次に(B)で RecommenderEvaluator として AverageAbsoluteDifferenceRecommenderEvaluator のインスタンスを作ります。そして RecommenderBuilder という、DataModelからRecommenderを作るロジックを作ります。これが「評価対象のアルゴリズム」ですね。evaluatorには「Recommender」を与えるのではなく、RecommenderBuilderを与える必要があります。

そして(C)で評価をかけます。第二引数は DataModelBuilder を与えることができます*2が今回はnullで。第四引数の0.7は、30%を「除去」します、という指定、第五引数の1.0は、全体の100%を評価に使います*3、という指定です。

さて、以上のようにして、アルゴリズムを評価できるようになりました。自分の持っているデータによって、最適なアルゴリズムは異なると思います。従って、随時レコメンデーションロジックを評価しつつ、ベターな*4ロジックを採用していくことが重要です。

無限回廊

さて。

この「評価」も大きな仮定に基づいていたことに気づきましたか？ 以下、完全主義の人は半狂乱にならないように注意して読みましょう。

  • レコメンダの性能は、除去データのリアルと予測の「差の平均」で決まる （えっ、二乗和の平方根*5じゃだめ？）
  • データの除去率は30%でよい（なんで30%なんだよ）
  • （今回はやらなかったが）時間短縮のためにデータを間引いてもよい （へー、良いんだ）
  • 除去するデータは乱数で決めてよい （乱数っておいｗ）


　　「評価ロジックの評価ロジックが必要だ！」
　　「評価ロジックの評価ロジックの評価ロジックが必要だ！」

とならないようにしましょう。ほどほどで諦めが肝心です。機械学習に携わる人は、以下の事に早々に気づく必要があります。

　　「機械学習というのは、そもそも多くの仮定に基づいているものである！」
　　「完璧な機械学習というのは、すなわち100%の未来予測と等価なので、そもそも実現できない！」

*1:普通の人がイメージする平均のこと

*2:DataModelを独自実装した際に、データモデルの在り方を含めて評価したい場合に使うんだと思います。

*3:データ量が大量になると、評価にも時間が掛かる。評価時間を短縮するため、一部のデータを抽出した上で評価に使うことがある。

*4:完全なロジックは存在しなため、ベストという表現は使いませんでした。

*5:RMSRecommenderEvaluatorってのがありますｗ

レコメンデーションの簡単な原理を視覚的に把握してから実際に計算してみる

Mahout

Mahoutシリーズを最初から読む場合はこちらApache Mahoutで機械学習してみるべ - 都元ダイスケ IT-PRESS。

昨日分析したデータは、1番の人にお勧めなアイテムは104で、4.25点をつけるだろう、という予想でした。なぜこのような計算結果になったのか、なんとなく感覚をつかんでみよう。

入力に使ったCSVデータを、簡単にグラフ化してみたのがこれだ。

レコメンド対象となる1番の人は、青のグラフだ。この青のグラフのパターンに一番似ているのはどれだろう？ 101〜103をぱっと見た感じ、紫(5)の人と似た傾斜だと感じると思う。また、赤(4)の人も分かりづらいけど結構似ている。102の評価は抜けているものの、101*1と103の評価は近い。

逆に、緑(2)の人とは正反対の好みを持っているようだ。グラフが逆行している。黄色(3)の人は…、あんまり関連性はなさそうだな。

というようなことを考えると、104〜107のアイテムに「何点つけそうか？」が計算できる。紫と赤の人の傾向と似てるわけだから、青の人だって同じように104に高得点をつけそうだ。また、緑の人とは逆の好みを持っているのだから、緑の人が104を酷評しているので、やはり青の人にとっては高得点に思えるであろう。というわけだ。

さて、もう少し数学的にしてみよう。もう少しだけ。

ある二人のグラフのパターンがどの程度似ているのか？ というのを数値化できる。この数値化の式は少々複雑なので説明しないけど。これを相関係数と言うのだが、「全く関連性がない状態」を0、「完全に一致」を1とします。さらに、「逆の関連を持つ」つまり緑の人は相関係数がマイナスとなる。最小値は-1で、完全に逆相関。この値を-1〜1の実数として扱う。

昨日のデータの相関係数は以下の通り。目分量で考察した結果と一致しているのが分かると思います。

1 vs 1 = 1.0
1 vs 2 = -0.7642652566278799
1 vs 3 = NaN
1 vs 4 = 0.9999999999999998
1 vs 5 = 0.944911182523068

この情報を表すのが UserSimilarity ですね。ちなみに、自分自身と比較したら完全一致ですから1.0です。そして3は共通した評価が101しかないので、相関係数を計算できなかった感じです。

次に、これらを相関係数（の絶対値）順に並べ、「特に似ている人」を二人*2選び出します。まぁ、4と5の人ですね。この「似ている人たち」を表すのが UserNeighborhood です。

で、4と5の人を参考にして1の人に対してレコメンドするので、ここでレコメンド候補アイテムが絞り込めます。4または5が評価していて、かつ、1が評価していないアイテムを選び出します。その結果 104, 105, 106 となります。

104のアイテムについては、以下のように評点と相関係数、及びその積をまとめました。

user pref 相関係数 pref×相関
4 4.5 0.99 4.50
5 4.0 0.94 3.78
計 - 1.94 8.28

これをこのように割ると 8.28 ÷ 1.94 ≒ 4.26 です。104の予測評点は約4.26となりました。この計算はいわゆる加重平均です。重み=相関係数ですね。

他のアイテムについても同様の計算をした結果、一番予測評点が高かった104をお薦めした、というわけです。

これが、レコメンドの簡単な原理です。

*1:青グラフの■の裏に、赤の■が隠れている。表の方で確認すれば分かる。

*2:NearestNUserNeighborhoodのコンストラクタ第一引数に指定した値

Apache Mahoutで機械学習してみるべ

Mahout 分散技術

Mahoutシリーズ目次（随時更新）

非分散レコメンデーション
  1. Apache Mahoutで機械学習してみるべ - 都元ダイスケ IT-PRESS （これ）
  2. レコメンデーションの簡単な原理を視覚的に把握してから実際に計算してみる - 都元ダイスケ IT-PRESS
  3. 機械学習における重大な"仮定"と、アルゴリズムの評価 - 都元ダイスケ IT-PRESS
分散レコメンデーション
  1. Mahoutで分散レコメンド(1) - 都元ダイスケ IT-PRESS
  2. Mahoutで分散レコメンド(2) - 都元ダイスケ IT-PRESS
  3. Mahoutで分散レコメンド(3) - 都元ダイスケ IT-PRESS
クラスタリング
  1. 今度はMahoutでクラスタリング - 都元ダイスケ IT-PRESS
  2. 今度はMahoutでクラスタリング(ソース編) - 都元ダイスケ IT-PRESS

では、本文いきます。

Apache Mahoutっていう機械学習ライブラリがあります。詳しくはApache Mahout の紹介辺りを参考にしてください。

まぁ、要するにクラスタリング*1とか、レコメンデーション*2なんかをするクラスライブラリです。

例えばAmazonの「おすすめ」は、大勢のユーザの購買履歴に基づいて、各ユーザが興味を持ちそうな製品を算出しています。また、Facebookの「もしかして、この人と知り合いではありませんか？」というのも、機械学習によるものです。
さらに、Google Newsには次々とニュース記事が入ってきますが、「あるニュースとその続報」など、関連の深いニュースをひとまとめのスレッドにして表示したりしています。この「ニュースの分類」も手動ではなく、本文中に現れる単語の頻度などを分析した結果、自動でまとめています。また、同じ技術を使って、「このメールはスパムか否か」ということも計算で判定できるのです。これはgmail等で利用されています。

そんな中、レコメンデーションエンジンなんかは、様々な言語で色々な実装があり、OSSとして公開されているものも多くあります。そんな中でMahoutが一押しであるのは、スケーラビリティの確保に重点が置かれていることです。

機械学習というのは、当然、計算に基づいて結果を出すわけですが、その基礎となるデータが多ければ多いほど、確からしい結果を出してくれます。が、しかし、データが多ければ多いほど、指数的に計算量が増加する傾向があります。近年、このような大量データ処理のニーズは高まっています。その辺りの考察はHadoopとかに入門してみる 〜 分散技術が出てきた背景 - 都元ダイスケ IT-PRESSを参照。

じゃあHadoopの上で動く機械学習ライブラリを実装すりゃいいじゃん、ていうのがMahoutです。

えぇい、そろそろコード見せろ、って思ってますね？ とりあえずレコメンデーションでいきましょう。ひとまずHadoopとかは出て来ません。簡単な感じでいきます。

データを用意する

まず、「基礎となるデータ」を用意します。誰が何をどのくらい好きか、のデータですね。

1,101,5.0
1,102,3.0
1,103,2.5

2,101,2.0
2,102,2.5
2,103,5.0
2,104,2.0

3,101,2.5
3,104,4.0
3,105,4.5
3,107,5.0

4,101,5.0
4,103,3.0
4,104,4.5
4,106,4.0

5,101,4.0
5,102,3.0
5,103,2.0
5,104,4.0
5,105,3.5
5,106,4.0

こんなんですね。CSVフォーマットで、user,item,preference という順に並んでます。userとitemはlong型のID、preferenceはfloat型です。ここでは1.0〜5.0の範囲で適当に。5人のユーザと7つのアイテムに登場してもらいました。1番の人は101番のアイテムに5.0点つけました。…(中略)…5番の人は106のアイテムに4.0点をつけました。ってデータですね。

この状況で、1番の人に「新たなアイテム*3」を1つだけお薦めするとしたらどれ？ というのがレコメンドです。レコメンデーションエンジンは101〜107のアイテムしか知らないので、104〜107の4択ですが。データ量が多くなれば、もっと幅広く、予想のつかない結果が出て面白いです。

Javaプロジェクトを用意する

Mahoutを使うために、Mavenのdependencyにコレを入れておきましょう。

<dependency>
  <groupId>org.apache.mahout</groupId>
  <artifactId>mahout-core</artifactId>
  <version>0.4</version>
</dependency>

さっき用意したcsvは、src/main/resources/intro.csv あたりに保存しておきましょう。

コードを書く

DataModel model = new FileDataModel(new File("src/main/resources/intro.csv"));
UserSimilarity similarity = new PearsonCorrelationSimilarity(model);

// 第一引数の意味は明日解説
UserNeighborhood neighborhood = new NearestNUserNeighborhood(2, similarity, model);

Recommender recommender = new GenericUserBasedRecommender(model, neighborhood, similarity);

// 1番の人に対するレコメンドが1つ欲しい、という意味で(1, 1)です。
List<RecommendedItem> recommendations = recommender.recommend(1, 1);
for (RecommendedItem recommendation : recommendations) {
     System.out.println(recommendation);
}

こんだけです！ ホントにこんだけです。すげーー。出力結果はこれ。

RecommendedItem[item:104, value:4.257081]

1番の人にお勧めなのは、104のアイテムで、恐らくこの人にこのアイテムを評価させたら4.25点くらいをつけるでしょう。ということです。

*1:データの集合をクラスタと呼ぶグループに分ける。似たようなデータが同じクラスタに属するようになる。

*2:多くのユーザの好みに基づいて、特定ユーザーが興味を持つと思われる情報をお薦めとして提示する。

*3:101〜103は既に知ってるアイテムなのでレコメンドする意味はない。

Javaのcloneは悪者か？

Java

Effective Java 第2版 (The Java Series)

Effective Java 第2版 (The Java Series)

Java: The Good Partsが（賛否両論の）話題を呼んでいるが、それ以前にEffective Javaは皆さん、読んだだろうか？ この本の項目11に、「cloneを注意してオーバーライドする」というセクションがある。そのほかにも、Javaのcloneメソッドは各所で嫌われているようだ。

そのような論調において、clone代替案としては、コピーコンストラクタと、staticなファクトリメソッドがしばしば挙げられる*1。

うん、確かにJavaのcloneメソッドはイケてない。俺もそう思う。まぁ、イケてない理由はみんなと同じだから上記の各文献を当たってください。まぁ要するに「きちんと実装するのが難しく、それをコンパイラに強制させられない」のです。

では、cloneメソッドは要らないのか？ と言われれば、俺はNOだ。要る。要件として「コピー元と同じ実装クラスのインスタンスを生成しなければならない」というケースでcloneを使わざるを得ない場合がある。

  • コピーコンストラクタは、コピー元の実装クラスを知らなければ使えない。
  • staticなファクトリメソッドも、オーバーライドが出来ないため、やはりコピー元の実装クラスを知る必要がある。


まぁ、言いたいことはだいたい伝わったとは思うのだが、具体例で説明してみたい。…で、これを説明するにあたって、良く知られたクラスを例に出したかった。が、そんな例が見つからなかった…。不当に嫌われすぎていて、そんな実装例が見つからないのだ*2。

というわけで、現実の話を少し曲げて説明に使ってみる。

JavaにはListというインターフェイスがあって、その実装としてArrayListやLinkedListがある。まず前提として確認したいのは、Listは Cloneable インターフェイスを実装しておらず、ArrayListとLinkedListはこれを実装しているということ。これは何故だろう、と考えると、ArrayListやLinkedListは、順序付き集合をオンメモリで扱う実装だからだ。メモリ上の集合ならばcloneしても構わない。しかし、Listはというと、実装がオンメモリであるとは限らない。add/removeなどを実行する度に、律儀にファイルやDB、もしくはリモートのサーバに内容を書き出すような実装クラスを作っても、Listインターフェイス契約的には何ら問題にならない。List型にcloneを認めてしまうと、このような実装を妨げてしまうからであろう。

ここで、現実の話を少し曲げる。Listとその実装型の間に、仮に OnMemoryList というインターフェイスを挟んであるものだと仮定する。さらにもう一つ、ArrayList#clone()も戻り値型はObject型ではなくArrayList型、そしてLinkedList#clone()の戻り値型は同様にLinkedList型である、とします。共変戻り値ですね。

ではここで問題。

/**
 * {@code in}に与えたリストが持つ要素のうち、{@code p}を満たす要素のみで
 * 構成される新しいリストを返す。
 * 
 * <p>戻り値のリストの実装型は{@code in}の実装型と同じである。
 * また、{@code in}は破壊してはならない。
 * 戻り値のリストの要素順は、{@code in}の要素間の相互の位置関係を維持する。
 * </p>
 * 
 * @param<E> 要素の型
 * @param in 入力のリスト
 * @param p 条件を表す述語
 * @return 新しい {@link OnMemoryList}
 * @throws IllegalArgumentException 引数に{@code null}を与えた場合
 */
public <E>OnMemoryList<E> filter(OnMemoryList<E> in, Predicate<? super E> p) {
  // ...
}

ArrayList<String> idList = new ArrayList<String>();
// LinkedList<String> idList = new LinkedList<String>();
// どちらでもテストは成功すること。

idList.add("dai.0304");
idList.add("daisuke_m");
idList.add("dai19780304");
idList.add("daisuke-m");
idList.add("dai0304");
idList.add("daisuke");

OnMemoryList<String> filtered = filter(idList, new Predicate<String>() {
  public boolean apply(String input) {
    return input.matches(".*[0-9].*"); // contains digits
  }
});

// idListの非破壊を確認
assertThat(idList.toString(), is("[dai.0304, daisuke_m, dai19780304, daisuke-m, dai0304, daisuke]"));

// 正常にフィルタリングされていることを確認
assertThat(filtered.toString(), is("[dai.0304, dai19780304, dai0304]"));

// 実装クラスが同じであることを確認
assertThat(filtered.getClass().equals(idList.getClass()), is(true));

このメソッド、どうやって実装しますか？ よくある関数型っぽいことをするためのメソッドですね。ミソは「戻り値のリストの実装型は{@code in}の実装型と同じである」ってところで、これが恐らく、cloneを使わないと実装できないところだと思います。

Validate.notNull(in);
Validate.notNull(p);
OnMemoryList<E> result = in.clone();
Iterator<E> itr = result.iterator();
while (itr.hasNext()) {
  if (p.apply(itr.next()) == false) {
    itr.remove();
  }
}
return result;

このように、cloneにも重要な役割があるのであって、cloneはイケてないから一律使わない、と思考停止するのはあんまりよくないんじゃないかなー、と思っています。Effective Javaは、本当にcloneが必要なケースかを問いかけ、必要ならばうまくやれ、と言っているんだ。決して「cloneはイケてないから使うな」とは言っておらず「イケてないから、注意深く実装しようね」と指摘しているに過ぎないのだ。

cloneをうまく使っているコードってあまり見ないなぁ、不当に迫害され過ぎてんじゃないかなぁ、と思ったので、こんなん書いてみました。

まぁ、4ヶ月ほど前まで、自分が思考停止してたんですけどネ。

*1:もしくは、シリアライズ＋デシリアライズの組み合わせ、なんてのを提案する場合もある。

*2:分かってる、コレは俺の願望だｗ

ScalaでBrainf*ckのインタプリタを書いてみたよ

Scala

Scalaで書いた作品その3です。まぁ、今までハロワと妙なEclipse Pluginしか書いてないので、全くScalaらしからぬコードだと思うけど。

とりあえずコードを貼ると、モヒモヒした人達がScalaっぽくしてくれるんじゃないかなぁ…。

とりあえずブログ上のテキストだとモヒりにくいと思ったから、githubに上げた…ら、案の定モヒられています。

続きを読む

ScalaでEclipse Pluginを書いてみたよ

Scala EclipsePluginDev

う ご く ｗ ｗ ｗ http://bit.ly/gy1lJ8

都元ダイスケ🍅 on Twitter: "う ご く ｗ ｗ ｗ http://bit.ly/gy1lJ8"

えーと。id:kompiroさんとネタかぶりですがｗ 一足先にScalaを試したのでご報告。

普通に動きました。特に難しいことしてません。id:kompiroさんの手順の変法です、で済まそうとしたらちょっと違ったので手順を箇条書きしときます。

*1:何がどこに入ってるか知らないので、とりあえず全部。恐らくscala-compiler.jarとかは要らないんだけど、まぁとりあえず全部だ全部。

続きを読む

Java: The Good Parts

Java

Java: The Good Parts

Java: The Good Parts

来る2/23、オライリーよりJava: The Good Partsという訳本が発売されます。この本は、監訳のid:t_yanoさんからお話を頂き、査読に参加させて頂いた関係で、献本を頂きました。どうもありがとうございました。

オライリーからは「The Good Parts」シリーズの書籍が何冊か、既に出版済みです。例えばJavaScript: The Good Partsは、（ざっと眺めただけですが）jsにおけるコーディング指針を紹介しているような印象でした。こう書くと良いよ、こう書くと分かりづらくてよくないよ、という感じ。PHP: The Good Partsは目次しか見ていませんが、やはり同じ印象です。

しかし、Java: The Good Parts は毛色が違います。（他のシリーズとは違って）この本は、まさにJavaのGood Parts（良いところ）について書いてあるのです。

良いところ、というと非常に抽象的ですが、世界を「Java以前」と「Java以降」に分けた時、そこで起こったイノベーションを項目毎にまとめて解説したものです。（…と言ってしまうと、言い過ぎかもしれませんが。Javaだけによって起こったイノベーションではないものも、あると思います。）

目次はこんな感じ。


要するに「○○って、いいよね。Java以前には○○はメジャーじゃなかった。だから××な点で大変だったよね。でも、Javaには○○があるんだ。○○って、やっぱりいいよね！」（○○には↑の各項目を代入してください）っていう話です。


「Java以前はどうだったのか」、「なぜこのGood Partsを導入したのか」、「Java以後、どうなったのか」という視点で各項目を説明しています。監訳のid:t_yanoさんも言う通り、普段からJavaをゴリゴリ使いこなしているような人にとっては、言ってしまうと「当たり前」のことがひたすら書かれています。が、私も「うんうん、そうだよね」と同意しながら、時には「いやー、まぁ、意図はそうなんだろうけど、現実問題ねぇ…」と批判的に、楽しく読み進めることができました。

この本は「Java以外の言語をバリバリ使っているが、これからJavaをきっちり使えるようになりたい人」や、「Javaを使ってはいるが、今ひとつ使いこなせている気がしない人」に是非お勧めしたい本です。