PRML復々習レーン#13に参加して発表してきました

PRML復々習レーン#13に参加して発表してきました．会場を提供してくださった @7shi さん，会場手配にご尽力いただいた @Prunus1350 さんに改めて御礼申し上げます．発表者，参加者のみなさまもありがとうございます．

前回のあらすじをuploadしました．

PRML復々習レーン#13 前回までのあらすじ from sleepy_yoshi

今日はついにノーテーション地獄である因子グラフ->積和アルゴリズム->max-sumアルゴリズムのセクション．本レーンで読んだときには???の嵐で何も覚えていなかったが，さすがに3度目の正直，ついに (今までに比べて) 深く理解できたという気がした．図や式に対してどんな説明が欠けているのか，今までよく理解できなかった理由がよくわかった気がした．(え，それを本レーンで説明したんじゃないかって?)

ざっくりいうと今日は

• 無向グラフをさらに一般化した因子グラフの導入
• 因子グラフにおけるメッセージパッシング手法である積和 (sum-product) アルゴリズムの説明
• max-sum アルゴリズムの説明

の3つがポイント．

sum-product アルゴリズムは，説明不足な記号があって苦労したものの，なんとか理解することができたと思う．変数ノード->因子ノード，因子ノード->変数ノードのメッセージを分けて書いているけれど，結局再帰的に表現するのでどちらかのメッセージだけで表現することも可能．というか，どちらもμで書いているから目をしばしばさせないと区別できないから記号を変えればよいじゃない，と思ったり．

以前まで有向グラフ <=> 無向グラフ <=> 因子グラフは等価な変換が可能と思い込んでいたけれど，そうではないことも認識できた．PRMLに書いてあるとおり無向グラフではクリークあたり，ひとつのポテンシャル関数しか用意できないが，因子グラフでは複数の因子関数を用意してもよい意味で柔軟である．また，因子グラフでは表現できないノードの親子関係を有向グラフは表現可能である．

あとは図8.44と図8.45，図8.44では有向グラフを因子グラフに「変換」している．ここでは，p(x3|x1,x2)が存在するため，f(x_1, x_2, x_3)の因子が必須 (図8.45のように3つの因子に分解できない) という解釈をした．グラフを変えた時点で失われる情報もあるのから，そこも落としてもよいのかもしれないけれど，図8.45ではそもそも親子関係が不明な無向グラフをスタート地点にしているので，極大クリークにポテンシャル関数を用意しようが，2ノードのクリークにポテンシャル関数を用意しようがどちらでもよい (グラフがそれを規定できないので) ふたつの記述方法を例示している．読み違いかもしれないけれど，きっとそういうことだろう．

最後の最後だけ少し担当．発表資料は以下のとおり．

PRML復々習レーン#13 8.4.6-8.4.8 from sleepy_yoshi

ジャンクションツリーアルゴリズムについて誤りがあったので訂正．そもそも無向グラフ->三角分割->ジャンクションツリーと変換されたジャンクションツリーそのものは因子グラフとは異なるクラスのグラフである，ということを理解できていなかった．詳細は追っていないけれど，クリークをノード，クリーク間で共有された変数(集合)をリンクとしたグラフの模様．グラフは奥が深い…．

有向グラフィカルモデルにおける信念伝播を宿題にさせてもらったのだけれど，PRMLでは信念伝播 (BP) を積和アルゴリズムとは区別しているがWikipediaでは等しいものとして記述されているなど，よくわからない．

まぁなんにせよ一週目はたんなるお経にしか聞こえなかったand見えなかったノーテーション地獄をなんとなくクリアした気分になれたので大変気分がよい．
次回は混合モデルとEM．具体的な例も出てくるのでとても楽しみ．

補足

@K5_semさんに資料を参考にしたといわれて「なんのこっちゃ」と思っていたらPRML本レーンで発表していたことに気づく．全く記憶になかった…．というわけで過去のブログ記事と発表資料へのリンクはこちら

• PRML読書会10回: 第8章グラフィカルモデル (前半)
• 第11回PRML読書会: 第8章グラフィカルモデル (後半)

菜穂子

（2013-08-14読了）

谷川岳への行き帰りに青空文庫で読んだ．風立ちぬの原案の一部なのかな?

堀辰雄の本は初めて読んだけれど，読みづらい．最初は菜穂子の母親の一人称で始まるのだけれど，母親自身を三人称で呼称したり，人の入れ替わりにどうもついていくのがつらかった．

映画の菜穂子とはかなり違う，それでいて通じるところもある．なお，ストーリーとして収拾がつかず，よくわからないまま終わる．村上春樹小説的な終わり方と捉えることもできるか．

風立ちぬも読んでみよう．

ラムダ式を使ってもう少しかっこよくstd::transformを使ってみる

先日の記事ではstd::transformの使い方を学んだ．しかし，既に用意された関数以外を利用する場合にはその都度関数を定義するのはダサい．どうやらC++ではラムダ式が使えるようになっていたらしいので使ってみたのだけれど，けっこうハマったのでメモ．

先日と同じようなコードをラムダ式を使って書いてみる．

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <numeric>

#include <cmath>


int
main (int argc, char *argv[])
{

  std::vector<double> vec;
  vec.push_back( 1.0 );
  vec.push_back( 1.5 );
  vec.push_back( 2.0 );
  vec.push_back( 2.5 );

  std::transform(vec.begin(),
                 vec.end(),
                 vec.begin(),
                 std::ptr_fun<double, double>( std::exp ) );

  double sum = std::accumulate(vec.begin(), vec.end(), 0.0);

  //
  std::transform( vec.begin(), vec.end(),
                  vec.begin(),
                  ( [&sum] (double x) -> double { return (x / sum); } ) ); // sum変数を参照キャプチャ

  // 別の方法．こんな書き方もできる
  /*
  std::transform(vec.begin(), vec.end(),
                 vec.begin(),
                 std::bind2nd(
                              std::ptr_fun<double, double, double>( [] (double x, double s) -> double { return (x / s); } ),
                              sum ));
  */
                                         

  for (int i = 0; i < (int)vec.size(); i++) {
    std::cout << vec[ i ] << std::endl;
  }

  return 0;
}

ラムダ式は (<引数>) -> <返り値> {} で書くことができる．ただし，スコープ外部の変数を参照することができないため，最初のの中に参照したい変数を記述する．無印で記述すれば値渡し (すなわち，内部で変更しても外部の変数には影響がない)，&を付与すれば参照渡しになる．

コンパイルする際には g++ std=c++0x とstdオプションをつける必要がある．これにけっこうハマった．

なお読み出し元のコンテナとは別のコンテナに値を確保する場合には少しだけ注意が必要．格納先のコンテナにも要素数の大きさのサイズが必要になるため，あらかじめ確保しておく必要がある．

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <numeric>

#include <cmath>


int
main (int argc, char *argv[])
{

  std::vector<double> vec;
  vec.push_back( 1.0 );
  vec.push_back( 1.5 );
  vec.push_back( 2.0 );
  vec.push_back( 2.5 );


  std::vector<dobule> vec2;
  
  // エラー: vec2のサイズが不足
  std::transform(vec.begin(),
                 vec.end(),
                 vec2.begin(),
                 std::ptr_fun<double, double>( std::exp ) );

  std::vector<double> vec3( vec.size() );

  // OK
  std::transform(vec.begin(),
                 vec.end(),
                 vec3.begin(),
                 std::ptr_fun<double, double>( std::exp ) );

std::vectorのようなSTLコンテナの各要素に指定した関数を適用した結果を得る

std::vectorのようなSTLコンテナの各要素に対して関数を適用した結果を簡単に書きたい．
Perlでいうところのこんなイメージ．

my @list     = (1.0, 1.5, 2.0, 2.5);
my @exp_list = map { exp($_) } @list;

C++ではどう書くのだろう? STLで対応する関数が用意されているだろうなぁと思って手書きしていたので，今回ちゃんと調べてみたので自分用メモ．

結論からいえば，std::transform (algorithmヘッダ) を利用すればよい．ただし，最後の引数が関数オブジェクトである必要があるので，そのままではstd::expのような関数ポインタを利用できない．そこでstd::ptr_fun (functionalヘッダ) という関数アダプタ (と呼ばれるもの) を利用する．C++使いには常識なのだろうけれど，今日初めて知った．

ptr_funは関数ポインタを関数オブジェクトに変換してくれる．class1は引数の型，class2は返り値の型を表す．

言葉で書くよりもコードを載せる方がわかりやすいのでメモ．

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <cmath>


int
main (int argc, char *argv[])
{

  std::vector<double> vec;
  vec.push_back( 1.0 );
  vec.push_back( 1.5 );
  vec.push_back( 2.0 );
  vec.push_back( 2.5 );

  std::transform(vec.begin(),
                 vec.end(),
                 vec.begin(),
                 std::ptr_fun<double, double>( std::exp ) );

  for (int i = 0; i < (int)vec.size(); i++) {
    std::cout << vec[ i ] << std::endl;
  }

  return 0;
}

なるほど，これで少しは書きやすくなった．

PRML復々習レーン#12に参加して発表してきました

PRML復々習レーン#12に参加して発表してきました．会場を提供してくださったニフティさん，会場係の @who_you_me さん，幹事の @Prunus1350 さん，発表者，参加者のみなさまありがとうございます．改めて感謝申しあげます．

今日発表した前回のあらすじ資料をアップしました．

PRML復々習レーン#12 前回までのあらすじ from sleepy_yoshi

以下のような質問をいただく．

• 超事前分布をどこまで取るか?
• RVMの貢献ってベイズ線形回帰にデータ毎にARD適用したこと? -> YES
• グラフィカルモデルは誰か提唱したか

元々ベイジアンネットワーク，信念ネットワーク (Belief network) とは別にマルコフ確率場のような手法が出てきて，いつのまにかグラフィカルモデルという言葉が出来て，その分類としてふたつが語られるようになったということ．

久々参加の @shuyo さんの「グラフィカルモデルは矢印のリンクの (2013-07-22修正) あるところに意味があるのではない．矢印のリンクの(2013-07-22修正) ないところに意味がある」というフォローでかなり理解が進む．

ナイーブベイズのところで，矢印反転したらどうなるのか? というところでひと議論．矢印を反転すると，tail-to-tailになってしまうので，クラスが観測されると全ての単語に依存関係が発生してしまう．というわけで矢印の方向はクラスから単語という方向が正しい．

実は1つの依存だけ考えてあげるAverage One-Dependence Estimator (AODE) というものがある．元論文は以下のつぶやきの通り．

"Not So Naive Bayes" というタイトルが大変面白い．そういえばふと思い出したけれど，M1の夏休みだったかを使って研究室でナイーブベイズ輪講というものをやっていたことをふと思い出す．しかし，内容を全く思い出せない．ちょっと資料を漁ってみよう．

条件付き独立については昔本レーンで発表担当した記憶だけあるけれど，すっかり忘れていた．

• 観測すると親と親 (子) が条件付き独立になる
  • head-to-head
  • head-to-tail
• 観測すると親と親が独立にならない (観測されなければ親同士は独立)
  • tail-to-tail

これを元にしたd分離について次回の復習資料でフォローするのが宿題．

イジングモデルのところでは，学習に用いるアルゴリズムの違いは組み合わせ最適化をどれだけ正確に解くのか，ということと理解した．ICM (Greedyな方法)，Gibbs sampling，Max-prodcut，そして厳密解を求めるグラフカットアルゴリズムで，@naoya_t さんおすすめはグラフカットアルゴリズム．

というようなことを感じながら聞いていた．次回は8/24の予定．各自夏休みの課題をやってくるようにと言ってしまったので何をやろうかネタを考えておこう．

勉強会後はひさびさのご飯．エクセルの行列入れ替えの相談をしたり(笑)，勉強に関する話をしたり．@shakezo_ さんとMLaPP読みたいけれど，だれか興味を持つ人はいるのだろうか，という話をしたり．なおMLaPPは以下の1000ページ超の武器．

Machine Learning: A Probabilistic Perspective (Adaptive Computation and Machine Learning series)

右手にPRML (原書)，左手にMLaPPを装備すればそこらへんのモンスターは撲殺できるのではないだろうか*1．

さて今回からグラフィカルモデル本番に入り，次回はいよいよノーテーション地獄．今度はちゃんと理解できるだろうか．

*1:FF3ネタ．分からない人はFF3 学者で検索してみてください

非復元抽出の高速かつ実装が簡単な方法を考える

※ @tomerun さんに書いてもらったコードとその検証結果を記事の最後に追記しました．(2013-07-21 2:00)

ふとしたきっかけで非復元抽出 (random sampling without replacement) を実装するときに気になったのでどんな実装がよいのか考えてみた．なお非復元抽出はビンゴのように，N個の要素の中からk個の異なる要素をランダムに選択するという意味である．

復元抽出については @unnonouno さんのブログなどに書いてあり，非復元抽出についてもリンクが張ってあったのだけれど，リンク先のブログ記事が読めない状態になっていていたのが残念．

• unnonouno: 高速な復元抽出の直感的な説明

はじめに

std::vector

「超」入門 失敗の本質 日本軍と現代日本に共通する23の組織的ジレンマ

（2013-07-19読了）

会社の先輩と組織論などの話になったときに「『失敗の本質』読んだ？読んでないならオススメ．最近その解説本出たみたいだけど読んでないや」と言われて，まず解説本から読むというゆとりっぷりを発揮して読む．

「失敗の本質」は第二次世界大戦において日本が失敗した6つの作戦を題材に，なぜ失敗したのかということを考察した本であり，組織や経営を考えていく上でバイブル的な本らしい．

そもそも「失敗の本質」を読んでいないので，これがよい解説本なのかわからないけれど，割とよくあるハウツー本のような印象を受けた．ざっと以下のようなことが印象に残っている．

• 目的に合わせた新たな指標を設けることの重要さ
• 現在の指標の根底を失わせるためのイノベーションが必要
• ダブル・ループ学習

最後のダブル・ループ学習は"「想定した目標や問題自体が間違っているのではないか」という疑問・検討を含めた学習法 (p.121)"だそうだ．たぶん日本の会社ではPDCA()という言葉が連呼されていると思うけれど，たいていの場合には本書でいうところのシングルループ学習，すなわち「想定した目標や価値観を固定した」営みになっているのではないだろうか．著者によれば日本人は一度決めた指標に対して最適化をするのは得意だが，その指標を適切なタイミングで変えるのがなかなか苦手らしい．自分も割とそのタイプだと思う．

さて，引用の引用の引用になってしまうが，以下の箇所は心に刺さった．

左記は『失敗の本質』３章で引用されている、日本軍の組織がいかに平和時に安定していたか、という指摘です。

日本軍人（陸海軍）は、
・思索せず
・読書せず
・上級者となるに従って反駁する人もなく
・批判をうける機会もなく
・式場の御神体となり
・権威の偶像となって
・温室の裡に保護された
（「太平洋海戦史』高木惣吉／岩波新書より）

まるで、現代日本のどこかの組織内情を暴露しているような印象を抱かないでしょうか。
(p.200)