マルコフ連鎖でTwitter BOTを作る
既にやり尽くされた感のあるネタだが，個人的には得られた点が多かったのでまとめておく。
やりたいこととしては，「twittbotでBOTを作るだけじゃツマラナイし面倒だから，自動でBOTが学習して呟いてくれたらいいよね！」って感じ。皆に愛されているしゅうまい君などもマルコフ連鎖で文章を生成しているらしいヨ。圧縮新聞は言わずもがな。
環境
アカウントの準備
BOTを運用するアカウントを作成する。このとき，アカウントで利用するメールアドレスの認証を済ませておかないと，後でTwitter Developersのサイトにログインできなくてハマる。
アカウントを作成したら，Twitter DevelopersのサイトにSign inして，新しくアプリケーションを作成する。アプリケーションの名称・説明・ウェブサイトなどは適当に埋めればOK（後から変更できる）。OAuthのAccess LevelはRead and Writeとしておき，アプリの管理画面からAccess Tokenを生成する。
Access Tokenの生成が終わったら，Consumer Key，Consumer Secret，Access Token，Access Token Secretの値をメモる。この値は後でスクリプトに埋め込んでOAuthアクセスするために利用する。
ライブラリの導入
BOTスクリプトを動かすためにigo-rubyという形態素解析のライブラリとおなじみのTwitter Ruby GemというTwitter APIのWrapperライブラリを使う。
igo-rubyはgemのインストールの他に，前もって辞書ファイルを準備する必要がある。igo-rubyの移植元であるIgoのサイトで辞書ファイルの作成方法が説明されているので，その通りに進める。作成した辞書ファイル郡（が入っているディレクトリ）は次項で説明するスクリプトと同じディレクトリに配置するといいだろう。なお，この段階でJavaコンパイラが必要になるので注意されたい*1。
Twitter Ruby GemはBasic認証の頃からするとだいぶAPIが変わっているが，現バージョンではOAuthも簡単に利用できるようになっている。いずれにせよライブラリの開発者に感謝。
BOTスクリプト
スクリプトは2つのファイルに分かれている。エントリポイントで利用するクラス郡を記述したtwitterbot.rbを下記に示す。
このスクリプトにはマルコフ連鎖のアルゴリズムやfavstarをスクレイピングする処理などが含まれる。
続いて，エントリポイントであるentry.rbを示す。
アカウント準備の項でメモしたConsumer Key，Consumer Secret，OAuth Token，OAuth Token SecretをRuby Twitter Gemのパラメータとして設定する。また，TwitterBot::CrawlerのコンストラクタにBOTのscreen_nameと取得元のscreen_nameを与える必要がある。
簡単なコマンドラインオプションに対応しているので，「--no-reply」でリプライなし，「--no-tweet」で通常のツイートなしなど，動作を多少カスタマイズできる*2。
マルコフ連鎖
メインの文章生成アルゴリズムは3次のマルコフ連鎖である。3次なので，基本的には先行する2つの『語』を引数として取り，その後に続く1語を推定する。マルコフ連鎖アルゴリズムを実装するには文章を語に分解（わかち書き）する必要があるから，この部分で形態素解析が必要になる。ここでは，前述のとおり形態素解析ライブラリとしてigo-rubyを利用した。
igo-rubyによって分解された語は，連続する3語ごとに『テーブル』に登録される（この段階を『学習』と呼ぶ）。
たとえば，「私 は 田中 です 。」*3という文章であれば，「私 は 田中」「は 田中 です」「田中 です 。」などがテーブルの要素になる。ただし実際には，その後の生成処理のために文章の最初と最後に「__BEGIN__」「__END__」というダミー語を付加している。
ここまでの準備が終わったら，テーブルに格納された語順を元に文章を生成する（この段階を『生成』と呼ぶ）。
まず，ダミー語である「__BEGIN__」が先頭にあるテーブルの要素を検索する。続いて，見付かった要素群からひとつランダムに選ぶ。ここで，選ばれた要素の2個目の語を文章の起点とする。例えば，テーブルから「__BEGIN__ 私 は」という要素が選ばれたのであれば，「私」が文章の起点となる。これはちょうど，2次のマルコフ連鎖に相当する処理である。
以降は，テーブルをフルに活用して3次のマルコフ連鎖を行う。
まず，ここまでで得られた「__BEGIN__」ともうひとつの語（先ほどの例であれば「私」）が先頭部に含まれるテーブルの要素を検索する。続いて，見付かった要素郡からひとつランダムに選ぶ。ここで，選ばれた要素の3個目の語を次の語とする。例えば，テーブルから「__BEGIN__ 私 は」という要素が選ばれたのであれば，「は」が次の語となる。
以降は要素の検索に使う2つの語を順々に入れ替え，語を生成していく。採用した語が「__END__」であれば，そこで文章を終端する。
プログラムの動作
長々と説明したが，上記のスクリプトでは，80%の確率でマルコフ連鎖がBOTのツイート生成に使われる。残りの10%ではfavstarのrecent favorited tweetsから，残りの10%ではfavstarのbest tweetsから文章を選んでツイートする。マルコフ連鎖アルゴリズムにおける『学習』の段階では，元アカウントのツイート（最近の200件）をクロールし，取得したツイートの語順を『テーブル』に記憶する仕組みである。
また，ここで紹介したスクリプトはmentionへのリプライにも対応している。
リプライ時は，APIから最近のmentionを取得し，これらのmentionのうち，BOTが最近言及していない相手に対するものを抽出する。こうして抽出したmentionに対して，ツイート時と同様にマルコフ連鎖で文章を生成してリプライする。
なお，リプライ時の文章生成に利用するテーブルと，通常ツイート時の文章生成に利用するテーブルは，このスクリプトでは独立したものとして扱われており，リプライ時に通常ツイート時の語順を参考にするようなことはない。
その他，付け加える点としては，元アカウントのツイートからはURIやRT/QTなどの外部へのリンクに相当する文字列が削除されていることや，文章生成時には140文字以内に収まるものを生成結果として採用していることなどが挙げられる。
以上
理解するとごく単純な仕組みだが，実行してみるとそれっぽい文章が生成されるあたりにおもしろみがある。ときどき思いもよらぬ文章ができて，実装した自分でも(￣ー￣)ﾆﾔﾘとしてしまうこと請け合い。夏休みの自由研究には持って来いかもしれないね。
更新（2012-03-12T08:06:00+09:00）
favstarをスクレイピングして得たツイートに改行が含まれる場合に改行タグがそのまま出力されてしまう不具合を修正。また、自身にリプライを飛ばしてしまって延々とひとり語りしてしまう不具合を修正。
更新（2012-12-12T02:23:00+09:00）
favstarが出力するHTMLの仕様変更に追従した。
