2013-06-19

Play! 2.0 / 2.1 ぐらいで play コマンドを実行したときに Permission denied な例外が発生する問題への対処

イラッとしたのでメモ。

概要

Linux など UNIX 系 OS に Play framework 本体をインストールし、${PLAY_HOME}/play コマンドで play clean compile stage などをした場合に、

java.io.FileNotFoundException: /path/to/play/framework/sbt/boot/sbt.boot.lock (Permission denied)
        at java.io.FileOutputStream.open(Native Method)

とか

java.io.FileNotFoundException: /path/to/play/repository/.sbt.ivy.lock (許可がありません)
        at java.io.FileOutputStream.open(Native Method)

などの Java の IOException が発生してしまうことがある件への暫定対処です。

原因

そもそも何でこの例外が発生するのかというと、Play framework 本体をインストールした際のユーザ (所有者) であったりパーミッションの設定が厳しかったりすることが原因となり、上記した類のロックファイルの作成や書き込みができないことによります。

※ play コマンドを実行したときに、${PLAY_HOME} ディレクトリ以下に書き込みをする Play framework もどうかと思いますがね…

(暫定) 対処法

本当はもうちょっとスマートな方法があるんじゃないか… と思ったのですが何かと面倒そうなので、

chmod -R go+wx ${PLAY_HOME}/framework/sbt/boot
chmod -R go+wx ${PLAY_HOME}/repository

こんな感じで解決するのがいいでしょう。

2013.8.21 追記

よくよく Play! 2.x の公式ドキュメント http://www.playframework.com/documentation/2.1.3/Installing を読んでみると、

Download the latest Play binary package (take the latest official version) and extract the archive to a location where you have both read and write access. (Running play writes some files to directories within the archive, so don’t install to /opt, /usr/local or anywhere else you’d need special permission to write to.)
と書かれていました。つまり「(ファイル／ディレクトリ書き込みなどをするから) /opt, /usr/local にはインストールするなボケ！」ということですね。

by @komiya_atsushi23:371 comment

2013-06-03

Jubatus Casual Talks #1 でトークしてきました #jubatuscasual

主催者の方に発表内容をかっちりと決めずになんとなく「発表したいです！」と参加表明してみたものの、いざ開催日が近づくと「やばいな発表できるネタができない…」という状態に陥ってちょっとお腹痛くなる思いをしましたが、何とか発表し切れてホッと一息ついたのでエントリ起こしておきます。

Jubatus って何？

PFI & NTT によって共同開発されている、「機械学習の各種タスクをオンライン (かつ分散) で処理できるようにする」ことを目的としたプロダクトです。「機械学習」と一口に言ってもいろいろありますが、例えば「クラス分類」とか「回帰」とか「レコメンド」とかが Jubatus ではできるようですね。

詳しくは 公式 をご覧ください。

お話したこと

「Java で楽して Jubatus したい！」というタイトルで、Java から Jubatus を利用する際にお世話になる Jubatus Java Client に関してお話をしました。

他の方々の発表は軒並み「Jubatus を使って◯◯しました」というとっても実践的な内容、というか ガチュアルな内容も盛りだくさんで、Jubatus を使わないネタで発表をする身としては肩身が狭いことこの上ありませんでしたが、まあ多少盛り上がった (?) ようでしたのでよしとしましょう…

発表内容は以下のスライドをご覧いただくとして、ざっくり要約すると

  • Java から Jubatus を使ってみようかなー
  • Jubatus Java Client を使う必要があるらしいけど… こ、これを使うのははちょっと辛いな…
  • よし、楽に使えるラッパーライブラリを作ろう → Jubaba (ゆばーば) 爆誕！

こんな感じです。

 

Jubaba (ゆばーば)

そういうわけで、Java から Jubatus をカジュアルに利用するためのラッパーライブラリ、 Jubaba プロトタイプ版を作り始めました！

まだまだインタフェースも試行錯誤を重ねていて流動的だったり、多値分類 (Classifier) しかサポートできていないので完成には程遠い状態ですが、ちょっとずつ開発を進めていく予定です。ご要望、ご意見等ありましたらご連絡いただけると幸いです。あ、pull request くれてもよかですよ！！

その他・感想

発表機会をくださいました @unnonouno さんこと海野さん、Jubatus 関係者の方々、そして拙い発表を忍耐強く聞いてくださった会場参加者の方々、ありがとうございました！

  • Jubatus 開発チームの、Java に対する如何ともし難い黒いオーラが滲み出ているところを深くえぐってしまった (※後述) 感がありますねこの発表は… ははは。ごめんなさい…
    • 懇親会のときの、海野先生のコード生成裏話 LT は涙なしには聞けなかったです、はい。
  • Java で機械学習している人、前からわかっていたことですが少ないですねー。Java エンジニアとしては、もっと盛り上げていきたいなあ。
    • 今回の開催でも、他の参加者はみんな Python だったり Ruby を使ってるし、それらとの対比で Java での煩わしさを引き合いに出されるし… 特徴抽出を試行錯誤するなら LL な言語でやるのが定石ですね。
  • 異常検知、熱いですね！ このみなさんの注目度は意外だったー。

そんなわけで、また機会がありましたらお邪魔させてください＆ネタがありましたら発表させてください！ (今度はガチュアルな話をしたい…)

※補足

えぐってはいけないものをえぐってしまってごめんなさいごめんなさいごめんなさい…
by @komiya_atsushi9:03No comments

2013-05-20

Java 7 時代の String#split() 事情

Java 7 になって String#split() の実装が変更されたことに今更ながら気付いたので、Pattern#split() や Java 6 との性能の比較をしてみたメモです。

Java 6 以前の文字列分割処理

古くから Java を触っているエンジニアであればみな当然知っていることだと思いますが、 TSV ファイルを Java のプログラムで読み込んで処理をするときなど、特定のデリミタで区切られた文字列を個々の要素に分割するときは String#split() を利用せず、事前にデリミタに対する java.util.regex.Pattern オブジェクトを生成しておき、そのオブジェクトを使い回す形で Pattern#split() を利用した方が処理効率 (処理時間) がよくなります。

これは、 String#split() の実装が実質的に Pattern.compile(delimiter).split(str) と等価であることによります。つまり String#split() メソッドは、そのメソッドの呼び出し毎に Pattern オブジェクトを生成するため、オブジェクト生成のオーバーヘッド (と GC 発生頻度の増加) によって処理性能が悪化する、ということです。

Java 7 での String#split() 実装

一方で、Java 7 ではこの String#split() に手が加えられ、Java 6 以前と少し事情が異なっています。

public String[] split(String regex, int limit) {
    /* fastpath if the regex is a
     (1)one-char String and this character is not one of the
        RegEx's meta characters ".$|()[{^?*+\\", or
     (2)two-char String and the first char is the backslash and
        the second is not the ascii digit or ascii letter.
     */

上記は Oracle 社の JDK 1.7 src.zip に含まれる String.java より拝借してきた String#split() のメソッド冒頭のコメントです。

この英語をざっくり翻訳すると『指定された正規表現が次の 2 つのどちらか

  • 1 文字で構成されていて、正規表現におけるメタ文字 ".$|()[{^?*+\\" のいずれでもない
  • 2 文字で構成されていて 1 文字目がバックスラッシュ、2 文字目が 英数字以外 である

に合致する場合に、より手短に済む処理をする』となります。

これはつまり「実質的に特定 1 文字の正規表現として取り扱える場合は、(Pattern#split()) より高速な文字列分割処理できる」ことを意味しています。事実、上記コメント以降の String#split() 実装を見てもらえるとわかりますが、 Pattern オブジェクトを生成することなく、 String#indexOf() を用いた単純な文字探索ベースでの文字列分割を実現しています。

ところで Java エンジニアとしては、この Java 7 での変更により、どの程度性能に影響が現れるのかが気になるところです。そういうわけで、

  • Java 6 での String#split() と Pattern#split()
  • Java 7 での String#split() と Pattern#split()

それぞれの処理性能を比較してみることにしました。

文字列分割処理の性能比較

性能比較は こちらのデモプログラム を用いて実施しました。

結果は こちらの Google ドキュメント にまとめました。

結果を見ると明らかですが、Java 7 で特定の 1 文字を現す正規表現 (" ") を指定した場合は String#split() の方が Pattern#split() よりも 2 倍以上速くなっています。一方で、複数種類の文字に一致する正規表現 ("\s") を指定した場合は、Java 6 と同じ傾向になっていることがわかります。

Google ドキュメントには正規表現を複雑にしたときの性能比較と、ガベージコレクションの発生回数も参考までに掲載しておきました。この結果より、

  • Java 6 → Java 7 では、 Pattern クラスの各種処理性能が若干劣化している？
  • 正規表現を複雑にすると String#split() 側の性能が劣化する (＝ Pattern.compile() の処理のオーバーヘッドが効いてくる)
  • 選択の正規表現は (Pattern.compile() もそうだけど) マッチング処理がとにかく重い

ということが窺えますね。

まとめ

今回のまとめは以下のとおり。

  • Java 7 以降なら、TSV ファイルの 1 行を分割するなど、特定の 1 文字で構成されたデリミタを指定するときは迷わず String#split() しよう
  • Java 6、もしくは複数文字や複雑な正規表現で分割したい場合は、 Pattern オブジェクトを事前に定数的に生成しておき、使いまわして Pattern#split() しよう
by @komiya_atsushi11:49No comments

2013-03-29

Java の BlockingQueue 実装の性能を比較してみた

巷では「ArrayBlockingQueue よりも LinkedBlockingQueue の方がスループット性能がいいよ」なんてまことしやかに言われているけど、どうにも気になったので検証してみたら、実は ArrayBlockingQueue の方が性能いいんじゃない？ という結論に至った話です。

Producer-Consumer デザインパターンと BlockingQueue

Java で Producer-Consumer デザインパターン を実現するときによくお世話になる BlockingQueue インタフェース。このインタフェースには ArrayBlockingQueue クラス と LinkedBlockingQueue クラス の二つの実装が標準 API として提供されています。

高い処理性能を要求されるプログラムを Java で書こうとしたときに、CPU のすべてのコアをフル稼動させることを狙って Producer-Consumer パターンによって処理フローをパイプライン的に構成することがあります。そのときにいつも気になっていたのが、「ArrayBlockingQueue と LinkedBlockingQueue、果たしてどちらを利用した方がスループットが高くなるのだろうか？」ということ。

この疑問に対して、海外でも 議論 されていたり、検証 されていたりされているようで、それらの 結論 としては概ね「LinkedBlockingQueue の方が ArrayBlockingQueue よりも高スループットだよ」というものになっています。

しかし、ArrayBlockingQueue と LinkedBlockingQueue の双方の実装やデータ構造の特性を考えると「LinkedBlockingQueue の方が高スループット」という結論がにわかに信じ難かったので、実際に検証をしてみることにしました。

双方のデータ構造と実装の特性

検証を始める前にまず、それぞれのデータ構造および実装の特性を確認してみることにします。参考にした実装は Oracle の JDK 1.7 (update 17) です。

ArrayBlockingQueue クラス

  • 配列をベースとしたキュー実装で、配列をリングバッファとして扱います。
    • エンキュー (add() / offer() / put()) 操作、デキュー (remove() / poll() / take()) 操作をする配列上のインデックスを、それぞれ別々に保持しています (putIndex フィールドと takeIndex フィールド)。
  • キューの大きさは固定長で、その大きさを超える要素数を保持することはできません。
  • エンキュー操作において、余計なオブジェクトが生成されることはありません。
  • エンキュー／デキュー操作では、一つのロックオブジェクト (lock フィールドの ReentrantLock オブジェクト) を共用して排他制御をします。
    • エンキューとデキュー操作のメソッド呼び出しが重なると、一方の処理にてロック解除待ちが生じてしまいます。

LinkedBlockingQueue クラス

  • 片方向の連結リストをベースとしたキュー実装です。
    • 要素の数に応じて、リストが伸長・縮退します。
  • 連結リストの先頭 (head フィールド) より要素をデキューし、末尾 (last フィールド) に要素をエンキューします。
  • 保持できる要素数は最大で Integer.MAX_VALUE になります。
    • コンストラクタで capacity を指定することで、保持する要素数を制限することもできます。
  • 要素のエンキュー操作ごとに、連結リストの Node オブジェクトの生成操作が発生します。
    • 1 つの要素につき 16 バイトほどのヒープを余計に消費します。
  • エンキュー／デキュー操作の排他制御はそれぞれ別々のロックオブジェクト (putLock フィールド、takeLock フィールド) を利用します。
    • エンキューとデキュー操作のメソッド呼び出しが重なったとしても、ロック解除待ちは発生せず並列に処理することができます。

これら上記の双方の特性を比較すると、

  • ArrayBlockingQueue は処理が単純な分、エンキュー／デキュー操作の処理コストが小さく、一方で LinkedBlockingQueue はオブジェクト生成が必要となるために特にエンキュー操作の処理コストが高い。
  • ArrayBlockingQueue は、エンキュー／デキュー操作においてロックオブジェクトを共有するために Producer / Consumer の並列性が低くなるが、LinkedBlockingQueue は別々のロックオブジェクトが用意されているため、Producer / Consumer の並列性が高まる。

と言うことができそうです。 LinkedBlockingQueue の方がスループットが高い、というのは後者の並列性が根拠になっていると思われますね。

性能検証する

続いて、実際に両者の BlockingQueue 実装を利用したプログラムを作成し、各種性能を測定してみました。

測定方法

検証用プログラム を用いて、エンキュー操作、デキュー操作を独立して 1,600 万回ほど行ったときの処理時間、およびエンキュー／デキュー操作を複数の別スレッド (Producer / Consumer) で同時並列に 1,600 万回実施したときのスループットを ArrayBlockingQueue, LinkedBlockingQueue それぞれの実装ごとに測定してみました。

また測定を進めていく上で、Java VM の 32 bit と 64 bit の違いや、Java コンパイラ (JDK / Eclipse)、ハードウェア・OS (Windows / Mac) の違いが性能に影響を与えることが明らかになったため、これらの構成の組み合わせも合わせて検証してみることにしました。

検証環境

  • ハードウェア・OS
    • Windows PC
      • Windows 7 (64 bit)
      • Core i5-3450 (3.10GHz)
      • 8GB Memory
    • Mac
      • Mac OS X 10.8.2
      • 1.7GHz Core i5-3317U
      • 4GB Memory
  • Java
    • Java VM (オプション : Xms1200m)
      • Java 7 Update 17 (32 bit & 64 bit)
    • Java コンパイラ
      • JDK 1.7 Update 17
      • Eclipse Compiler for Java 3.8.2

測定項目

  • エンキュー／デキュー操作を行う各種メソッドの呼び出しにかかる時間 [ミリ秒]
    • エンキュー
      • add()
      • offer()
      • put()
    • デキュー
      • remove()
      • poll()
      • take()
  • スループット [メッセージ/秒]
    • Producer x 1 スレッド, Consumer x 1 スレッド
    • Producer x 1 スレッド, Consumer x 2 スレッド
    • Producer x 2 スレッド, Consumer x 1 スレッド
    • Producer x 2 スレッド, Consumer x 2 スレッド

測定結果と考察

上記の内容で測定した結果を Google ドキュメントで公開 しています。数値に対するカラースケールは行（横一列）のグループに対して設定されており、緑色が良い性能であることを、黄色がほどほどの性能を、赤色が性能が悪いことを示します。

Java VM (64 bit / 32 bit) の違い

さてこの結果を見てすぐに分かることは、ArrayBlockingQueue と LinkedBlockingQueue のどちらについても、32 bit Java VM よりも 64 bit の方が性能がよい、ということになりますね。メソッド単体の呼び出し性能もスループットも、どちらも下は 1.5x から上は 4x ぐらいまでの性能が 64 bit VM では出ています。

メソッドの呼び出し性能に着目すると、32 bit VM ではメソッド間で性能差が大きく開きバラつきがあり、ArrayBlockingQueue も LinkedBlockingQueue もそれぞれの性能特徴がよく分かる結果となっています。一方で 64 bit VM では、メソッド間の性能差は 32 bit ほどの開きは見られず、安定した性能が出せていることがうかがえます。

スループットについては、64 bit VM を使うことで ArrayBlockingQueue の性能が 32 bit VM のときより大幅に性能向上することが見て取れます。LinkedBlockingQueue も 64 bit VM による性能劣化はなく、ArrayBlockingQueue ほどではないものの多少の性能向上がうかがえます。

Java VM の違いにおいて ArrayBlockingQueue と LinkedBlockingQueue の結果を比較すると、

  • 32 bit VM では LinkedBlockingQueue の方が性能がよい。
  • 64 bit VM では ArrayBlockingQueue の方が性能がよい。

と言えるでしょう。

Java コンパイラ (JDK / Eclipse) の違い

コンパイラの違いについては、今回の測定結果では優劣が明確になるほどの性能差は出ませんでした。

ハードウェア・OS の違い

Mac の場合、ArrayBlockingQueue と比べて LinkedBlockingQueue の性能が全体的に悪いことがわかります。メソッドの呼び出しについては、特にエンキュー操作の性能が極端に悪いですね。

スループットも、エンキュー操作メソッドの性能に引きづられてか、LinkedBlockingQueue の性能は芳しくありません。エンキュー操作が競合しやすい Producer x 2 の構成での落ち込みが大きいですね。

Mac では、 ArrayBlockingQueue 択一 と言ってしまっていいと思います。

まとめ

ArrayBlockingQueue を使うべきか、それとも LinkedBlockingQueue を使うべきかの判断は Java VM 次第、すなわち

  • (Mac を含む) 64 bit の Java VM を利用するなら ArrayBlockingQueue がよい。
  • 32 bit の Java VM なら LinkedBlockingQueue がよい。

と言ってしまっていいでしょう。ただ今後のことを考えれば 64 bit VM の利用が多くなっていくと考えられるため、開発時点では 32 bit の VM 利用を想定していても、ArrayBlockingQueue を採用しておくのが無難じゃないかと思います。はい。

だいじなこと

今回は Windows と Mac とで性能検証をしてきたのですが、実際に Java アプリが利用される環境は Linux など Unix 系の OS が多いかと思います。今回の検証でなんとなく傾向はつかめた (64 bit なら ArrayBlockingQueue) のですが、これがそのまま Linux でも通じるかどうかはまた別の話、つまりは要検証、ということです。

by @komiya_atsushi2:22168 comments

2013-02-07

楽して Markdown ファイルをリアルタイムプレビューできる仕組みを作ったった

ざっくり要約すると、お好きなテキストエディタとブラウザさえあれば OK な、ちょっと便利な Markdown リアルタイムレンダリング＆プレビューツールを 車輪 の 再発明 の再発明したよ、ということです。

Markdown のリアルタイムプレビューの現状

動機は言わずもがなですが改めて書くと、github で公開するプロダクトの README など、Markdown のフォーマットでドキュメントを書く機会がここ最近増えてきています。ですが、Markdown の書式に慣れないうちは、HTML レンダリング結果をブラウザで確認しながら編集したいもので、実際にプレビューを確認しながら書くのとそうでないのとでは生産性に結構な差が生じることは、経験者の多くの方々に頷いてもらえるかと思います。

このような欲求があれば当然、それを解決するツールが生み出されるのが世の常なわけでして、すでに Markdown のリアルタイムレンダリングツールの類はいくつか世に出ています。

Showdown は、外部サービスを利用せず JS で実装された Markdown レンダリングエンジンを利用してプレビューを実現するツールで、ブラウザだけで完結するのが強み（でもあり弱みでもある）となっています。一方で Jxck 先生の markup とたむたむ先生の rdoc-view は、いずれもローカル環境に AP サーバを立てて、そのサーバ経由でローカルのファイルシステム上にある Markdown ファイルのプレビューを提供します。この方式の強みはなんといっても、「好きなエディタを使って Markdown の編集ができる」ということに尽きます。

markup にしても rdoc-view にしても、利用するために必要となる実行コマンドは２つだけですが、その前に Node.js の環境やら Ruby の環境やらを整えなくてはいけないという、私みたいなものぐさ人間にはそれなりの高さのハードルがあります。

Markdown Previewer

そんなわけで、「自分の好きなエディタ」を利用できて、かつ「面倒なインストール作業も要らない」Markdown リアルタイムプレビューのサービス (?) を作りました。

Markdown Previewer

利用方法は「これでもか！」というぐらいに簡単（なはず）で、上記サイトを表示して、"Drop your markdown file here" と大きな文字で表示されている領域にローカルにある Markdown ファイルをドラッグ＆ドロップするだけです。後はお好きなエディタでそのファイルを編集するだけ。編集内容を保存すると、その内容がすぐにプレビューに反映されます。

お手軽リアルタイムプレビューを実現している仕組み

エンジニアの方であれば上記の説明から仕組みが簡単に想像できちゃうかと思いますが、JS の File API を利用することで、ローカルの Markdown ファイルの読み込み＆更新検知を実現し、また先の Showdown を利用して Markdown のレンダリングプレビューを実現しています。オリジナルなコードは高々数十行です。

詳しくは markdown-previewer の github リポジトリをご覧ください。

制限事項と今後の展開

今回は自分だけが使えればいいや、ということでブラウザ/OS は Google Chrome 24 (Mac OS X / Windows) のみをターゲットとしています。(2013.2.8 追記) Firefox (Mac/Ubuntu/Windows), Safari (Mac), Chrome (Ubuntu) に追加対応しました。 ですが、できるならば Firefox や Safari などでも使えるように対応していく予定でいます (IE は知らん)。

また、Markdown だけではなくて RDoc などの他の記法にも対応していく予定でいます。

by @komiya_atsushi10:46No comments

2012-12-14

AROW を Ruby で実装してみた

Machine Learning Advent Calendar 2012 の 14 日目の記事になります。気まぐれでこのカレンダー登録してみたものの、この日に至るまでの数々の記事のガチな高レベルさに登録してしまったことをかなり後悔している @komiya_atsushi です。

この記事では、オンライン学習アルゴリズムの AROW を Ruby で実装した (& gem として公開した) という、どこにでもよくある話を書いています。主に機械学習に馴染みのない or 取り組み始めたばかりの（自分を含めた）エンジニア向けの記事となっています。

AROW とオンライン学習

まずはじめに、この記事で取り上げている　AROW とその前提となる知識について軽く説明していきます。

AROW (Adaptive Regularization of Weight Vectors) というのは、「オンライン学習」ができる「教師あり」の「クラス分類（二値分類）」アルゴリズムです。ではこの AROW を使って何ができるのか？ というと、例えば「海賊船からかっぱらってきた金貨のようなものを、事前に明らかになっている数十枚のコインの真贋の情報をもとに、その体積と重さから真贋を見分ける」ことができるようになります。

AROW は 2009 年に提案されたアルゴリズムであるものの、後からよりよい手法が幾つか提案されているので state of the art な手法ではないですが、言い換えれば安定して使える「枯れた技術」として使うには十分ではないでしょうか。

オンライン学習

「オンライン学習」については、今回の Advent Calendar でも記事を書かれている kisa12012 さんの オンライン学習による線形識別器 などがありますので、詳しく知りたい方はこちらをご参照いただくのがいいかと思います。ここではざっくりな概要の説明に留めるとして、クラス分類での説明を簡単（雑？）にすると「次々と与えられるデータの『特徴』とそのデータに対するクラスを示す『ラベル』（Yes / No みたいなもの）をもとに、それらをラベルに従って分類してくれるモデルを作る・更新する（＝学習する）」となるでしょう。

オンライン学習の特徴としては、以下に示すものがあります。

  • 大量のデータをもとにモデルを作る必要があっても、全データを同時にすべて取り扱う必要がない（主記憶装置にやさしい）。
  • モデルの更新に利用したデータを不要となれば破棄することもできる（二次記憶装置にやさしい）。
  • １回１回のモデルの更新にかかる計算量が小さい（演算装置にやさしい）。

教師あり学習

次に「教師あり学習」について。教師あり学習というのは「正解の状態が明らかになっているデータ（訓練データ）をもとにモデルを作成する」学習になります。具体例でいうと今回取り上げている「クラス分類」がそれにあたります。対する用語として「教師なし学習」がありますが、こちらは「クラスタリング」などが例に挙げられます。

クラス分類

最後は「クラス分類」について。これは「データの『特徴』とそのデータに対するクラスを示す『ラベル』（Yes / No みたいなもの）をもとに、それらをラベルに従って分類してくれるモデルを作る・更新する。またラベルが未知のデータを予測して分類してくれる」お仕事と表現できるかと思います。

AROW の論文を読んでみる

続いて、AROW のアルゴリズムを実装する観点で、AROW の 論文 を読んでいきましょう。…とは言え、私自身、数式がそれなりにふんだんに使われた論文をすらすらと読めるほど数学リテラシーが高いわけではないので、重要な部分だけをピックアップして軽く説明します。

AROW を実装するに当たって一番重要なのは、p.4 のページ上にある Fig.1 です。（下図参照）

ここにある式を頑張って実装すればいいわけです。Σ が summation としてではなく共分散行列を表す変数として使われていることと、ベクトル x が列ベクトルであることに注意をすれば比較的容易に数式を読み解けると思います。

実際にこのコア部分を Ruby で実装すると、高々 50 行弱のコードになります。とってもシンプルですね！ 1

なお既存の他言語での実装を見てみると、Σ の更新式が、論文中の (9) 式ではなく、(8) 式をもとにした実装がほとんどになっているようです。tsubosaka 先生の Java 実装 や C++ 実装の AROWPP などなど。なぜみんな (8) 式を利用しているのか理由が分からなかったのと、(9) 式の方がより効率よく計算できて精度も向上するようなので、今回は (9) 式での実装をしました。 2

gem 'arow'

今回は上記実装をもとに gem 化したものを RubyGems.org で公開 しています。ソースコードは github.com/komiya-atsushi/arow にて公開しています。突貫工事的に gem 化したので、テストケースはないしマニュアルはないし README からして適当と粗が目立ちますが、カジュアルに使えるクラス分類器を自分自身が欲していたので、（お仕事が落ち着いたら）もうちょっと使いやすくできるようにメンテナンスをしていく予定です。

利用例がないのもアレなので、先に挙げた Code IQ の問題に対する適用例を示します… としたかったのですが、12/14 現在、まだ挑戦者受付中とのことらしいので念の為にしばらくはコード公開を控えておきます。また後日で。 3

2012.12.21 追記：公開しました。

おわりに・感想

久々に数式たっぷりな論文を読んで、改めて己の数学力の低さを悔やみました。数学力を鍛え直したい…

この Machine Learning Advent Calendar の企画を開催してくださいました @naoya_t さん、ありがとうございました！

1 : 今回の実装では、μ (@means) と Σ (@covariances) は時間・空間計算量を減らすために行列の対角要素をとったもので表現しています。既存の各種実装をみても、いずれもこの対角要素を利用する方式をとっているようです。
2 : 理由を御存知の方がいらしたら是非、教えていただけると幸いです。
3 : Advent Calendar に登録した当初は 12/14 時点で受付終了している予定でしたが、終了が延長されてしまったため、このタイミングでは公開できず、と。ぐぬぬ…
by @komiya_atsushi10:13No comments
登録: コメント (Atom)