アルゴリズムの理解まではほど遠いですが機械学習に挑戦します、shinyaです。
まさか大人になって微分やら線形代数やらが必要になるとは思いませんでした。
ちなみにcourseraで勉強中。無料ですし、おすすめです。

本当はフロントエンドの記事を書くつもりが、最近こっちの方が面白くそっちはまた今度。

てことで、MNISTの手書き文字の仕分け(クラスタリング)をEMアルゴリズムを使ってしてみます。
分類で言うと教師なし学習で、newsとかのカテゴリ自動分類とかにつかえたりするアルゴリズムです。

ただ写経してもあれなんで、普段使ってるjavascriptでpythonを解きほぐしながら試していきたいと思います。
numeric.jsとか使えばもっと簡単にできそうですが、せっかくなので使わず頑張ります。
※ライブラリはlodash.jsだけ使用しております。

準備

手書き文字をいっぱい書いてる場合でもないので、とりあえずもらってくる。

THE MNIST DATABASE
http://yann.lecun.com/exdb/mnist/

とりあえず私の誕生日(3月11日)にちなんで 031 を合計2000枚(多すぎると時間かかるので)抜き出す。

こんな感じの画像達。

で、画像のpixelデータを0,1のベクトルデータにする。
縦横が28*28なので784次元ベクトルになります。
今回はグレースケールが前提なので、127より大きかったら1それ以外は0に設定

var img = _.map([0, 0, 0, 0, 38, 222, 225, 0, ....., 0, 0], (v) => {
  return v > 127 ? 1 : 0
});

仕分ける

一旦ランダムの0-1までが入った784次元ベクトルを仕分ける数だけ準備、今回は031なので3つ生成。
それぞれの特徴を掴んでいくベクトルになります。

var params_ = {},
vector = [];

_.each(_.range(3), (i) => {
  var v = [],
  params_ = {},
  j = 0,
  l = 28 * 28;
  for(;j<l;i++) {
    v[j] = parseInt(Math.random() * 100000, 10) / 100000;
  }
  vector[i] = v;
});

// vecotorの中身の総和が1になるように調整
// 要はピクセルごとに色があるかの確率がはいっている。
vector = _.map(vector, (v, i) => {
  var sum = _.sum(v);
  return _.map(v, (n) => {
    return n / sum;
  })
});

params_.vector = vector;

// 今回だと031の三種なので各々1/3で分類されると一旦設定
params_.mix = 1/3;

画像化すると下の用な感じ。

このベクトルをベースにお勉強していく。

E

EM法のEの方、期待値(expectation)
勉強していくベクトルとぶつけて、ピクセルごとの確率などを計算していく。

function phaseE(){
  var result_ = [];
  // dataの中身はベクトル
  _.each(実データ, (data, i) => {
    var tmp = [];
    _.each('仕分け数', (j) => {
      var mix = params_.mix[j],
      // params_.vector[j]は前述した準備したベクトル
      // こいつと比較してどれに属するか計算
      ratio = bernoulli_(data, params_.vector[j]),
      a = mix * ratio,
      s = 0;
      if(a === 0) {
        tmp[tmp.length] = 0;
      }else {
        _.each(_.range(3), (k) => {
          var mix = params_.mix[j];
          // 各クラスタに属する確率の総和
          s += mix * bernoulli_(data, params_.vector[k]);
        });
        // 各クラスタに属する確率を算出
        tmp[tmp.length] = a/s;
      }
    });
    result_[result_.length] = tmp;
  });

  // ベルヌーイ分布
  function bernoulli_(a, b) {
    var r = 1.0;
    _.each(a, (data, i) => {
      var param = b[i];
      // 1次元ごとに比較
      if(data == 1) {
        r *= param;
      }else {
        r *= (1.0 - param);
      }
    });
    return r;
  }
}

ベルヌーイ分布(Bernoulli distribution)

M

最大化 (英: maximization, M)ステップ
Eで計算した結果を勉強していくベクトルに反映させる。

function phaseM(){
  _.each('仕分け数', (k) => {
    // Eステップででたベクトルの総和
    var nk = _.sum(result_[k]); 
    // 学習した内容を反映
    // 次のEステップで使用
    param_.mix[k] = nk/CNT;
    // 比較元のベクトルのアップデート
    _.each(train_data, (data, idx) => {
      var r = result_[idx][k];
      _.each(data.vector, (d, i)=> {
        var n = d * r;
        param_.mu[k][i] += n;
      });
    });
    // vecotorの中身の総和が1になるように調整
    param_.mu[k] = _.map(param_.mu[k], (mu)=>{
      return mu / nk;
    });
  });
}

EMの実行結果

上記を反復(今回は10回)で実行した結果が以下。最初に用意したベクトルが徐々に仕分けしたい特徴をつかんでくる。
途中からほぼ変化がない。おそらく過学習なのであろう。

なんとなく、0と3と1の特徴を掴んだベクトルになったように思える、少なくとも僕には。
784次元とかだと意味不明なので2次元で表すと下のグラフの用な感じで変化していっている、多分。

結果

実際に上記で作成されたベクトルで仕分けされた結果が以下。

ぱっとみなんとなく成功している感じの結果になったが、うまく仕分けできているやつから、できてない奴まで色々いる。
ほっそい3とかが1になったり、まるっこい3が0と同分類で仕分けされたりしちゃう。実用するにはキツイ印象。

ついでに、全然ダメパターンで下みたいになったりもする。

非常に残念な結果である。
もっと言うと本当は409(4009)でやったんだが4,9の区別がつかなすぎて散々になる。。。

感想

最初のベクトルの取り方を工夫すると、もうちょっと落ち着いた感じになるはず。
おそらくこんな考え方[k-means++法]

ただ今回は数式ばっか見てとてもつかれたので、とりあえずこれでゴール。。。
今回の検証だと識別率がそんなに高くないですが、数式を眺めるだけでは意味不明だったのが、なんとなくノリがつかめた気がします。
次はいつになるかわからないが、がっつりライブラリ使ってDeep Learningに挑戦したいと思います。