2015年11月3日火曜日

Algorithm::LibLinear Tutorial

About this article

This article is meant to be an introduction guide of Algorithm::LibLinear, a Perl binding to the famous LIBLINEAR machine learning toolkit.

I've once written an article titled "Algorithm::LibLinear の紹介" ("Introduction to Algorithm::LibLinear,") in Japanese. Today, although some part of the article is outdated, Blogger's access analytics reported me that the article is still popular, and fairly large number of visitors are from English-speaking country. Thus I guessed I should prepare an updated tutorial in English.

Notice that what I try to describe here is library usage, not a machine learning methodology. If you are new to machine learning, I recommend to read a practical guide by Chih-Wei Hsu, et al and try LIBSVM/LIBLINEAR using CLI commands at first.

As you might see my English skill is not so great. Please don't hesitate to point/correct unclear part of this article and help me to fix it.

Installation

Algorithm::LibLinear is an XS library. So a compiler is needed for compiling C/C++ dependencies.

Nov 2, 2015 at present, the latest version of Algorithm::LibLinear is v0.16 (based on LIBLINEAR 2.1) and available on CPAN. You can install the library using cpan or cpanm command (since dependencies to be compiled are bundled in the distribution, no additional instruction should be required ):

cpanm Algorithm::LibLinear

Class overview

You should consider only 4 main classes:

  • Algorithm::LibLinear - Trainer class. Holds training setting and generates trained model.
  • Algorithm::LibLinear::DataSet - Dataset.
  • Algorithm::LibLinear::FeatureScaling - Utility class for scaling feature range.
  • Algorithm::LibLinear::Model - Trained classifier (classification) / Estimated function (regression.)

Note that all the classes are immutable. Once created there's no method to modify it.

Executing training

On training, first you prepare a training dataset as Algorithm::LibLinear::DataSet and regulate it using Algorithm::LibLinear::FeatureScaling object:

use Algorithm::LibLinaer;  # This also loads Algorithm::LibLinear::{DataSet,Model} for convinence.
use Algorithm::LibLinear::FeatureScaling;  # FeatureScaling class is sometimes unused. So load it manually when you use.

# |A::LL::DataSet#load| loads LIBSVM format data from string/file.
my $data_set = Algorithm::LibLinear::DataSet->load(string => <<EOS);
+1 1:0.708333 2:1 3:1 4:-0.320755 5:-0.105023 6:-1 7:1 8:-0.419847 9:-1 10:-0.225806 12:1 13:-1 
-1 1:0.583333 2:-1 3:0.333333 4:-0.603774 5:1 6:-1 7:1 8:0.358779 9:-1 10:-0.483871 12:-1 13:1 
+1 1:0.166667 2:1 3:-0.333333 4:-0.433962 5:-0.383562 6:-1 7:-1 8:0.0687023 9:-1 10:-0.903226 11:-1 12:-1 13:1 
-1 1:0.458333 2:1 3:1 4:-0.358491 5:-0.374429 6:-1 7:-1 8:-0.480916 9:1 10:-0.935484 12:-0.333333 13:1 
...
EOS

# Scale all the data for ensuring each value is within {-1, +1}.
my $scaler = Algorithm::LibLinear::FeatureScaling->new(
   data_set => $data_set,
   lower_bound => -1,
   upper_bound => +1,
);
# Save scaling parameter for scaling test data later.
$scaler->save(filename => '/path/to/scaling_parameter_file');

# Since A::LL::DataSet is immutable, |scale| method creates a new scaled instance.
$data_set = $scaler->scale(data_set => $data_set);

Historical note: As of v0.08, Algorithm::LibLinear::ScalingParameter was provided instead of Algorithm::LibLinear::FeatureScaling class. It was removed from v0.09+ due to its complex interface.

Then you set up an Algorithm::LibLinear instance with training parameter:

my $learner = Algorithm::LibLinear->new(
    # |solver| determines learning algorithm and type of trained object ("SVC" is for SVM classification).
    solver => 'L2R_L2LOSS_SVC_DUAL',
    # Training parameters are problem-dependent.
    cost => 1,
    epsilon => 0.01,
);

At last, you give the dataset to the trainer then take a trained Algorithm::LibLinear::Model object:

# This process may take several minutes (depends on dataset size.)
my $model = $learner->train(data_set => $data_set);

# Save the model for later use.
$model->save(filename => '/path/to/model_file');

After that, trainer and dataset are no longer required. So you can undef them for increasing free memory.

Using trained model

Now you have a trained classifier model. You can predict a class label which a given feature to belong:

my %unknown_feature = (
    1 => 0.875,
    2 => -1,
    3 => -0.333333,
    4 => -0.509434,
    5 => -0.347032,
    6 => -1,
    7 => 1,
    8 => -0.236641,
    9 => 1,
    10 => -0.935484,
    11 => -1,
    12 => -0.333333,
    13 => -1,
);
my $scaled_feature = $scaler->scale(feature => \%unknown_feature);
my $class_label = $model->predict(feature => $scaled_feature);

Features are represented as HashRefs which having integer (> 0) keys, as same as training dataset. Note that feature scaling with same parameter as training is important.

Before you go

Git repository is on GitHub. Please report any issues / send patches to there, not to CPAN RT (I rarely watch it).

For more detail on API, refer perldoc Algorithm::LibLinear. And LIBLINEAR's README file which describes equivalent C API might be help.

2015年11月1日日曜日

Perl 6 Language Documentation を読む - Sets, Bags and Mixes

この記事について

先日の稿で Perl 6 の解説を書こうと思っているなどと書いて言質を振り出してしまったので果たさねばならない。 Perl 6 の言語自体を解説するアップデートされた日本語資料は大変乏しいので、とりあえず Perl 6 Documentation を読んで紹介するだけでもいくらか価値があるだろうと思う。

率直に言って僕の英語の読解力は甚だ貧しいので、近頃話題になった「腐った翻訳」になるのを避けるためにドキュメントを読んでから試行した結果に基いて解説を書くことにする。 翻訳ではないので文章自体は元の文書とは対応しないが、とにかく Rakudo Perl 6 上での挙動としては正しい解説になるはずである。

読む順番は決めていないが、簡単そうな文書の中で面白そうなものから進めていきたい。

本文の前書き

近頃の言語は集合型が必要なことになっている。厳密にいえば数学的な集合というより、順序付けられておらず要素が重複しないコンテナがプログラムの構成部品として便利だということである。

Ruby も Python も Swift も、C++ の STL にだって (それが本当に集合と呼べるかは別にして) [Ss]et がある。

Sets, Bags, and Mixes は Perl 5 には標準で備わっていなかった集合の操作をサポートする Perl 6 のクラスとロール群について解説している。

Set は単純な集合、Bag は重複可能な集合 (つまり multi set) で、Mix は要素に重みを持たせた集合を表す。 これらは一種の連想配列で、つまり要素に対して Set はそれが自身の要素かという真偽値、Bag はその要素をいくつ持っているかという整数値、そして Mixはその要素に割り当てられた重みを実数値で対応させる。真偽値を 0/1 と対応させれば Set の一般化が Bag だし、さらにその一般化が Mix とみなせる。

BagMix を使えば重みに応じて確率的に要素をサンプリングするような処理も可能なため、各種のアルゴリズムやビジネスロジックの記述にも便利だろう。

SetBag そして Mix はすべて不変クラスである。対応する可変クラスとして SetHashBagHash そして MixHash というクラスが存在する。

型システム上は不変クラスも可変クラスもそれぞれ SettyBaggy そして Mixy (mixi ではない) というロールを適用しているため同じインタフェースを持つ。MixyBaggy を適用しているため MixBag の真のスーパーセットである。Setty だけ孤立しているのは多分 Bool が数値型でないため実装の都合だろう。

可変クラスの不変クラスとのふるまい上の違いは、連想配列としてアクセスしたときに要素に再代入可能か (i.e., $set_hash<foo> = False) と、要素を破壊的に非復元抽出するメソッドである grabgrabpairs が例外を投げないことの2点。後者はそもそも個別のクラスでなくロールにメソッドがあるのが変だと思う。

初期化

リストから型変換メソッドを使って生成するのが最も簡単である:

> <foo bar bar baz>.Set
set(foo, baz, bar)
> <foo bar bar baz>.Bag
bag(foo, baz, bar(2))
> <foo bar bar baz>.Mix
mix(foo, baz, bar(2))

Set は要素の個数を覚えないが BagMixbar が2回与えられたことが判別できる。

そういうわけで、Bag-of-Words は文字通りである:

> my $str = "Humpty Dumpty sat on a wall\nHumpty Dumpty had a great fall\n"
Humpty Dumpty sat on a wall
Humpty Dumpty had a great fall

> $str.words.Bag
bag(a(2), great, Humpty(2), had, wall, fall, Dumpty(2), sat, on)

ただしこの方法だと Mix は整数値の重みしか取れないので Bag と変わりない。実数の重みを与えるにはペアのリストに対して .Mix メソッドを呼ぶ:

> (foo => 1.0, bar => 3.14, baz => 2.72).Mix
mix(foo, baz(2.72), bar(3.14))

ペアのリストを SetBag に変換することもできるが、その場合ペアの値はそれぞれ BoolInt に型変換されて解釈される:

> (foo => True, bar => False, baz => True).Set
set(foo, baz)
> (foo => 2, bar => 1, baz => 0).Set
set(foo, bar)
> (foo => 0, bar => 2.72, baz => 3.14).Set
set(baz, bar)
> (foo => True, bar => False, baz => True).Bag
bag(foo, baz)
> (foo => 2, bar => 1, baz => 0).Bag
bag(foo(2), bar)
> (foo => 0, bar => 2.72, baz => 3.14).Bag
bag(baz(3), bar(2))

不変クラスの場合 &set&bag そして &mix というサブルーチンも提供されている:

> set <foo bar bar baz>
set(foo, baz, bar)
> bag <foo bar bar baz>
bag(foo, baz, bar(2))
> mix <foo bar bar baz>
mix(foo, baz, bar(2))

サブルーチンにペアのリストを渡すときは名前付き引数と解釈されないように記法に注意が必要である:

> mix(foo => 1.0, bar => 3.14, baz => 2.72)
Unexpected named parameter 'foo' passed
> mix: foo => 1.0, bar => 3.14, baz => 2.72
mix(foo, baz(2.72), bar(3.14))

要素の等値性

要素同士の等値性は === の意味で判定される。 つまり StrNum のような値型はその内容で、Array などの参照型は同じオブジェクトへの参照か否かで同値か判定される:

> set <foo bar bar baz 1 2 3 3 4>
set(4, foo, 1, baz, 3, bar, 2)
> (set ['foo'], ['foo'], { bar => 1 }, { bar => 1 })
set(bar => 1, bar => 1, foo, foo)
# REPL の出力 (.gist) だと構造が分かりにくいのでソースコードダンプ
> (set ['foo'], ['foo'], { bar => 1 }, { bar => 1 }).perl
set(["foo"],["foo"],{:bar(1)},{:bar(1)})

メソッド

先述のとおりどのクラスもよく似たインタフェースを持っている。 連想配列として使うためのメソッドと、集合からランダムに要素をサンプリングするメソッドが提供されている:

> my $b = bag <foo bar bar baz>
bag(foo, baz, bar(2))

> $b.kv
foo 1 baz 1 bar 2

# 存在しない要素の値は 0 になる (Set の場合は False)
> $b<foo>
1
> $b<bar>
2
> $b<quux>
0

# pick は非復元抽出
> $b.pick
bar
> $b.pick
baz
# 最大で要素数まで取れる
> $b.pick(*)
baz bar foo bar
> $b.pick(*)
bar foo baz bar

# roll は復元抽出
> $b.roll
bar
> $b.roll
foo
> $b.roll(10)
baz bar bar bar foo bar bar bar bar foo
> $b.roll(10)
baz baz foo bar bar bar bar baz bar foo
# 要素数を * にすると遅延無限リストが返ってくる
> $b.roll(*)

組み込み演算子

集合関連の操作は演算子として提供されている。ちょっと信じられないことに Perl 6 は組み込み演算子が ASCII 外の文字である場合がままあるが集合演算はその極致で、全部の演算が集合演算記号にマップされている。 幸い大部分には ASCII の同義語が定義されているので、あまり頻用する場合以外はそちらを使う方が良いと思う。基本的にスカラ同士の似た操作の演算子を () で囲ったものが集合演算子である(e.g., &infix:<(|)> が集合の和、&infix:<(<)> が部分集合のテスト、など。)

Perl 6 で高度な集合演算を記述する場合は LaTeX チートシートと SKK を用意しよう。

以下の演算子は集合の要素や部分集合の述語である:

  • &infix:<<∈>> (&infix:<<(elem)>>)
  • &infix:<<∉>>
  • &infix:<<∋>> (&infix:<<(cont)>>)
  • &infix:<<∌>>
  • &infix:<<⊂>> (&infix:<<(<)>>)
  • &infix:<<⊄>>
  • &infix:<<⊆>> (&infix:<<(<=)>>)
  • &infix:<<⊈>>
  • &infix:<<⊃>> (&infix:<<(>)>>)
  • &infix:<<⊅>>
  • &infix:<<⊇>> (&infix:<<(>=)>>)
  • &infix:<<⊉>>

以下の2つは Baggy 版で、要素の有無に加えて対応する重みも比較される:

  • &infix:<<≼>> (&infix:<<(<+)>>)
  • &infix:<<≽>> (&infix:<<(>+)>>)

以下の演算子はそれぞれ集合の和、積、差そして対称差である。なお対称差とは集合 A と B が与えられたときの (A \ B) ∪ (B  A) のこと:

  • &infix:<<∪>> (&infix:<<(|)>>)
  • &infix:<<∩>> (&infix:<<(&)>>)
  • &infix:<<\>> (&infix:<<(-)>>)
  • &infix:<<⊖>> (&infix:<<(^)>>)

以下の2つ (判読困難だがそれぞれ U+228D と U+228E) は Baggy 版で、重みの積と和をそれぞれ取る:

  • &infix:<<⊍>> (&infix:<<(.)>>)
  • &infix:<<⊎>> (&infix:<<(+)>>)

まとめ

Perl 6 の集合関連のクラスとロールについて説明した。

Perl 5 では集合計算や数の集計、重みに応じた要素の乱択などあらゆる操作にハッシュが広く用いられていた。ハッシュは単純な非順序付け連想配列であり必ずしも理想的な実装ではなかった。 用途に応じて Set::Object などの CPAN モジュールも利用されたが、新しい演算子を定義できないとか tie が低速であるといった Perl 5 の言語及び実装上の制約により、組み込み型であるハッシュほど利便性が高くなかった。

Perl 6 は用途に応じて選択できる複数のコンテナを提供し、操作は新しい演算子の導入によって簡潔に記述できる (やりすぎの感があるが。)

閑話

ところで SetBag および Mix は組み込み型だが Perl 6 で実装されている。これは組み込み型のインタフェースをユーザ定義型でも同様に実装できることを示唆している。 Perl 6 においては配列やハッシュもコンテナクラスの1つに過ぎず、そのインタフェースは単なるメソッドや演算子である。 組み込みデータ型が明確に区別され、同様のインタフェースで操作するには tie という追加操作を必要とした Perl 5 とはこの点でも大きく異なる。

2015年10月29日木曜日

YAPC::Asia 2015 の感想文

これまでブログではデスマス調を用いていたけれども、推敲が要って面倒に思ったのでときどきはデアル調で書くことにする。

YAPC::Asia Tokyo 2015 が終わった。

既に終了から二ヶ月が経っているが「ブログに書くまでが YAPC」とのことで、これには期限が指定されていないので結局書かなかった昨年の分もまとめて終わらせても良かろうとて本稿を書いている。 目を開けねばいつまでも不思議の国にあるような感じで、ブログを書かねばいつまでもお祭りナノダとブンガク的怠惰的主張を述べようかとも思ったけれど、アラサー男がアリスなど引用しても薄ら寒いばかりなので止めにする。

落とし物

私的には今回最大の事件は前夜祭のちの二次会みたいなものに向かう途中の電車でマネークリップを落としたことだった。結局翌日 JR に4度ほど問合せたところ何故か渋谷駅に現金も手つかずで届けられていてことなきを得た (オモテナシはあながちでまかせとも言えないことが分かった) が、クレジットカードを再発行したために (僕はカードを一枚しか持っていないので) 一週間ほどオンラインの決済ができなかったり大変に生活に支障があった。

これまでの YAPC とのかかわり (フリーライダとして)

東京に越してきてからは毎年 YAPC::Asia に参加していた。特に熱心だったわけではなく、勤務先がスポンサーなのでチケットがただで手に入るし平日は業務扱いで参加できたからである。 2012年だったか岡山の院生だったときに旅費の補助があるというので一度 Lightning Talk (LT) をしたことがあるが、そのときを別にすれば見る方ばかりの参加だった。 ちなみにそのときの LT (動画が YouTube に上がっているが見たくないのでリンクもしない。スライドは以前のブログ記事のどこかにある) は要するに研究室の愚痴で、いかにも Perl 4 然としたコードを矯正するといった趣旨だった。

今年のトークについて

Rakudo 及び MoarVM 開発者の Jonathan Worthington 氏の "Parallelism, Concurrency, and Asynchrony in Perl 6" は Perl 6 の {並列, 平行, 非同期} 処理機能の紹介で大変に面白かった。二日目は昼過ぎから会場に向かったので現地で聴けたわけではなく、YouTube に動画が公開されてから観たのだけれども。

今年は Perl 6 のリリースが予定されておりある程度は界隈の関心を買うと思われるので、キャッチアップして簡単な解説を書くつもりでいる。先月に会社のブログの当番が回ってきたので丁度良いと思い Perl 6 の導入みたいな記事を一つ書いた。Twitter などで好意的な反応がそこそこあったが、時間をかけた割に尻切れトンボだし解説が抽象的すぎてためにならないあたり不満が残る。今の時点だと公式ドキュメントの翻訳や解説でもそれなりに価値があると思われるので、下手に構成せずに安直に進めたい。

なお以前翻訳した記事のシリーズである Perl 5 to 6 は現在もそのまま通用するので Perl 5 プログラマ向けのチュートリアルとして有益だと思う。

現地で観たトークの中では京大マイコンクラブ (KMC) の Hideaki Nagamine 氏の「PietでLISP処理系を書くのは難しい」が面白かった。 タイトルがほぼ出オチだが、画像ファイルをソースコードとする特異な難解プログラミング言語 Piet を用いて Lisp インタプリタを作ろうとしたという話。Piet インタプリタはスタック一本のプッシュダウンオートマトンのようなものなので、それに与える命令列からソース画像を逆コンパイルする手法で文字通りエンコードしていたのが大変にハッカーらしくて面白かった。結局環境がうまくキャプチャできずに字句的スコープがうまく動作しなかったという結末だったが、そもそも Piet 自体がチューリング完全ではない気がする。

僕が KMC という名前をはじめて知ったのは高専生だった頃に某氏が持ってきた「熊カレー」というゲームがきっかけだったので、大変微妙なサークルなのだと思っていたのだが、どっこい競技プログラミングガチ勢の名産地でもあったりするし、要は賢い人の頭をアイドル状態にしておくと変なものができるのだろう。

Piet 処理系についての閑話

ところで Piet の処理系として一番有名なのは多分 Perl で実装された Piet::Interpreter だが、Piet のサイトでも言及されているように白ブロック中での移動処理にバグがある。さらに悪いことにこのバグを前提として描かれた (書かれた、ではない) コードも数多くある。したがって処理系を実装しようとするときはまず正しい処理系で動くソースコードを見極めなければならない。

以前 YAP (センスの欠片もないがそのまま Yet Another Piet Interpreter の意である) という名前で Perl で自前実装してみたことがあり、この時はそのバグを再現するモードを追加したりしてコードが無用に複雑になった。ちなみに Perl プログラマが一度はかかる「Moooose はしか」に罹っていた時期に書いたので実にオブジェクト指向で実にモジュラな重量級の実装だった。 YAPC::Asia のトークを見てもう一度実装してみようと思い、それで今度は OCaml で書いた。自分で言うと馬鹿みたいだが簡潔で良い。OCaml を使ってまとまった量のコードを書いたのは始めてだが、代数的データ構造に対する強力な静的型検査がコーディング中の不安感を払拭してくれた。ここに至ってようやく僕は静的型システムの優位を認識できた。

閑話休題

最後の YAPC::Asia は「外野」として参加しても十分に実のあるカンファレンスだったことはとても良かった。うすら寒い内輪ネタもないことはないが参加者が多いので無視できた。

YAPC::Asia は Web 界隈の話題、特に運用ノウハウであるとかサービスのアーキテクチャの話題が充実していて、Perl が全く関係ないトークが過半といった印象の、最早 P の起源が摩滅しきっている点が特徴だと認識しているが、その勘定を別にしても Perl 5 から人の心が離れていると感じた。Perl 6 への注目も今年出るというだけが理由ではないだろう。

Paul Graham が云うように「良い言語には人気がなければだめだ」。今のところ Perl 5 は比較的巨大なユーザベースを持っているけれども、早ければ2010年代の終わりには発展が止まった言語になるだろうと思う。 本来の用途であったシステム管理などにはこれからも (Python といくらか競合しつつ) 利用されるだろうけれど、それは既に必要なものが揃っているからであって新しい用途に開いているからではない。

これから Perl 6 がどれだけのユーザを繋ぎ止められるかは分からない。そこが影横たわるモルドールの国でない保証もないが、いずれにせよ Perl Monger には是非もない。

いろいろと取り留めもなく述べたけれどこれでおしまい。

2014年6月9日月曜日

Algorithm::LibLinear アップデート

LIBLINEAR の Perl バインディングである Algorithm::LibLinear ですが、以前の記事で紹介した時点ではバージョン 0.04 だったのが現在では 0.10 になっており、非互換な変更もあったので当該記事のサンプルコードも最早動かなくなっています。 案外と今でもアクセスがある記事なので、現在までの変更を補足します。

LIBLINEAR 1.94 ベースになった

Algorithm::LibLinear 0.08 より LIBLINEAR 1.94 をバンドルしています。

配布サイトには内部処理のどうでもいい変更点しか載っていませんがメモリリークの修正が入っています。機能的には同一です。

API の非互換な変更

Algorithm::LibLinear::ScalingParameter クラスはバージョン 0.07 で非推奨になり、0.09 で廃止されました。同時に Algorithm::LibLinear::DataSet の scale() メソッドも削除されました。 今後は新しい Algorithm::LibLiner::FeatureScaling を使ってください。

ScalingParameter は設計ミスで、テストデータをスケーリングする場合に極めて周りくどい記述が必要でした:

use Algorithm::LibLinear::DataSet;
use Algorithm::LibLinear::ScalingParameter;

my $scaling_parameter = Algorithm::LibLienar::ScalingParameter->new(...);
my $feature = +{ attr1 => 0.2, attr2 => 1, ...};
# データ1個の DataSet を作って scale し配列として取り出した最初の要素の feature...
my $scaled_feature = Algorithm::LibLinear::DataSet->new(
    data_set => [ +{ feature => \%feature, label => 42 } ],
)->scale(parameter => $scaling_parameter)->as_arrayref->[0]{feature};

FeatureScaling はより分かり易いインタフェースを提供します:

use Algorithm::LibLinear::DataSet;
use Algorithm::LibLinear::FeatureScaling;

my $scaler = Algorithm::LibLinear::FeatureScaling->new(...);
my $feature = +{ attr1 => 0.2, attr2 => 1, ...};
# scale() に渡すだけ
my $scaled_feature = $scaler->scale(feature => $feature);

# DataSet やラベル付きデータも同様
my $scaled_dataset = $scaler->scale(
    data_set => Algorithm::LibLinear::DataSet->new(...),
);
my $scaled_labeled_data = $scaler->scale(
    labeled_data => +{ feature => $feature, label => 42 },
);

ScalingParameter が利用できる最終バージョンは 0.08 です。この点を除くと 0.08 と 0.10 は機能的に同一です。つまり事実上 0.08 は 0.10 のスーパーセットですが、新規のコードで ScalingParameter を利用する意味はありません。

今後の予定など

Algorithm::LibLinear は既に安定版です。今後非互換な変更は入りません。

今後の更新は LIBLINEAR の更新に併せたメンテナンスとドキュメントの修正のみのつもりです。あとビルドシステムが Module::Install なのが老頭児っぽいので気が向いたら変更するかも知れません。

現在 LIBLINEAR ディストリビューションで提供されている機能で Algorithm::LibLinear から利用できないものは次の2つです:

  • SVR 時の cross_validation() の戻り値が平均二乗誤差のみで二乗相関係数を返さない
  • データの Y 軸方向へのスケーリング機能。換言すると svm-scale コマンドの -y オプションによる設定、及び当該オプションを設定して出力されたスケーリング情報ファイルの -r オプションによる読み込み (正確には LIBLINEAR じゃなくて LIBSVM に含まれる機能)

これらについては筆者が必要性を感じていないので対応予定はありません。いずれも互換性を保って追加できる機能なのでパッチは歓迎します。

2014年3月23日日曜日

Algorithm::SVM の注意点

要旨

Algorithm::SVM は極めて有用だけど API がなんか変なので注意が必要。

詳説

CPAN に Algorithm::SVM1 というモジュールがあります。これ Support Vector Machine (SVM)2 を提供する LIBSVM3 という有名なライブラリの Perl バインディングなのですが、なんか API に癖があるので注意点を解説します。

まず使い方を簡単に紹介します:

use strict;
use warnings;
use Algorithm::SVM;

my @data_set;
while (<DATA>) {
  chomp;
  my ($label, $vector) = split /:\s+/, $_, 2;
  my @vector = split /,\s+/, $vector;
  my $data = Algorithm::SVM::DataSet->new(
    DataSet => \@vector,
    Label => $label,
  );
  push @data_set, $data;
}

# 本当はパラメータ調整が要るけど省略。全部デフォルトなのでガウスカーネル利用の C-SVC になる。
my $svm = Algorithm::SVM->new;
# 分類器を訓練する。
$svm->train(@data_set);

# ラベル1に分類されるべき未知のデータ。
my $test_data = Algorithm::SVM::DataSet->new(
  DataSet => [ 4.6, 3.2, 1.4, 0.2 ],
  # ラベルは未知なので仮に 0 とする。単に無視されるので -1 でも 65536 でも 42 でも良い。
  Label => 0,
);
# 未知データを分類。1 が返るはず。
my $label = $svm->predict($test_data);
print "$label\n";

# Iris Data Set (http://archive.ics.uci.edu/ml/datasets/Iris) より一部抜粋の上形式を変更。
# <label>: <vector elm1>, <vector elm2>, ...
__DATA__
1: 5.1, 3.5, 1.4, 0.2
1: 4.9, 3.0, 1.4, 0.2
2: 7.0, 3.2, 4.7, 1.4
2: 6.4, 3.2, 4.5, 1.5
3: 6.3, 3.3, 6.0, 2.5
3: 5.8, 2.7, 5.1, 1.9
...

DataSet がデータセットじゃない

SVM で訓練・分類されるべき (正解ラベル付き) ベクトルを表現するために Algorithm::SVM::DataSet というクラスが用意されていますが、このクラスが表現するのは1個のベクトルです。つまりデータセットじゃなくてデータです。Algorithm::SVM->train メソッドで訓練するときにはデータセットとして Algorithm::SVM::DataSet の配列を渡す必要があります。

分類時にもラベルが必要

未知データを分類する Algorithm::SVM->predict メソッドのパラメータは Algorithm::SVM::DataSet オブジェクトです。Algorithm::SVM::DataSet->new は名前付きパラメータとしてベクトル (DataSet) と正解ラベル (Label) を取りますが、正解ラベルは必須パラメータです。 つまりラベルが未知のデータに対してもラベルを与えてやらなければなりません。割と意味不明ですが、predict ではラベルは単に無視されるのでダミーのラベルを与えてやれば良いです。

疎ベクトルの与え方

Algorithm::SVM::DataSet->newDataSet パラメータは ArrayRef を取ります。ところで問題によってはほとんどの成分が 0 である (i.e., 疎である) ようなベクトルを扱う場合があり、このような問題のデータを配列で表現するとメモリの無駄です。 例えば1万次元ベクトルの 1123 番目と 5813 番目の要素だけが 1 のようなベクトルを表現する場合、[ (0) x 1122, 1, (0) x 4689, 1, (0) x 4187 ] という具合になってほとんど 0 です。もし HashRef で表現できるなら +{ 1123 => 1, 5813 => 1 } といった感じになってより簡潔かつ省メモリです。

実際 LIBSVM の内部ではベクトルは連想リストとして表現されていて、ArrayRef でしか受けつけないのはバインディングのコンストラクタの都合です。疎ベクトルのつもりで 0 だらけの ArrayRef をコンストラクタに渡すと、値 0 の無駄なデータで連想リストが伸びて、メモリ使用量だけでなく計算量も増大します。

これを避けるためには成分をコンストラクタから与えず、Algorithm::SVM::DataSet->attribute を使用します。このメソッドはベクトルの成分と値を併せて指定することで非零成分だけを連想リストに追加できます:

sub sparse_data {
  my ($sparse_vector) = @_;
  my $data = Algorithm::SVM::DataSet->new(Label => 0);
  # 番号が若い成分を追加すると挿入ソートが走るので若い順に追加していく方が速い。
  for my $index (sort { $a <=> $b } keys %$sparse_vector) {
    $data->attribute($index => $sparse_vector->{$index});
  }
  return $data;
}
my $sparse_data = sparse_data(+{ 1123 => 1, 5813 => 1 });

宣伝

カーネル関数を使わない線形 SVM を利用したい場合、LIBLINEAR ベースの拙作 Algorithm::LibLinear4 の方が高速です。API もこっちの方が明解です (当社比)


  1. https://metacpan.org/pod/Algorithm::SVM ↩

  2. http://ja.wikipedia.org/wiki/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3%82%AF%E3%82%BF%E3%83%BC%E3%83%9E%E3%82%B7%E3%83%B3 ↩

  3. http://www.csie.ntu.edu.tw/~cjlin/libsvm/ ↩

  4. https://metacpan.org/pod/Algorithm::LibLinear ↩

2014年3月10日月曜日

大規模なデータをそれなりに効率良く計数できる Algorithm::LossyCount を書いた

要旨

Algorithm::LossyCount というモジュールを書きました。これを使うとそこそこメモリ効率良く大規模なデータの計数ができます。アクセスランキング集計とかに使えるんじゃないでしょうか。

動機

例えばブログホスティングサービスで HTTP サーバのアクセスログを集計して人気のあるブログ記事ランキングを出したいとします。
Perl でデータの出現頻度を計数するのはハッシュを使うのが鉄板なので、適当に書くとだいたいこんな感じのコードになると思います:
#!/usr/bin/env perl

use v5.18;

my %access_counts;
while (<>) {
    chomp;
    my $access_log = parse_access_log($_);
    next if is_article_request($access_log);
    ++$access_counts{$access_log->{requested_article}};
}

my @popular_articles = (
  sort { $b->[1] <=> $a->[1] }
  map { [ $_ => $access_counts{$_} ] } keys %access_counts
)[0 .. 49];

say "Rank\tURL\tFreq.";
for my $i (0 .. $#popular_articles) {
  say join "\t", $i + 1, @{ $popular_articles[$i] };
}

sub is_article_request { ... }

sub parse_access_log { ... }
シンプルですね。
しかしブログの記事数はサービス全体で数千万から数億のオーダになります。一定期間に全記事にアクセスがあるわけではないにしろ、逐次計数していくとハッシュのキーが数千万件になってメモリが貧弱なマシンだと残念なことになります。
ところで Web ページのアクセス傾向に関しては Zipf の法則1が当てはまることが知られています。要するにアクセス数でソートしたグラフはロングテールで、超人気記事がごく少数あり、急激に坂を下ってほとんどアクセスのない記事がズラーッと並ぶグラフになります。 つまり計数ハッシュの中には低頻度で同順位のデータが大量に存在していることになります。集計したところで下位の順位なんか誰も見ないので無駄です。
こういうロングテールな大規模なデータが対象で、低頻度データの計数結果が多少不正確でも構わないような場合にメモリ効率良く計数するための近似アルゴリズムが Lossy-Counting2 です。 このアルゴリズムは入力が一定数追加される毎に低頻度データの計数結果を捨てていきます。高頻度データの計数結果はパラメータによりますが確率的にまず捨てられないので上位の結果は信頼でき、下位の低頻度データはナンヤカヤ・ウヤムヤにされます。

使い方

上記の例でハッシュを使っている箇所を Algorithm::LossyCount に置き換えるだけ。
#!/usr/bin/env perl

use v5.18;
use Algorithm::LossyCount;

my $counter = Algorithm::LossyCount->new(max_error_ratio => 0.005);
while (<>) {
    chomp;
    my $access_log = parse_access_log($_);
    next if is_article_request($access_log);
    $counter->add_sample($access_log->{requested_article});
}

my $access_counts = $counter->frequencies;
my @popular_articles = (
  sort { $b->[1] <=> $a->[1] }
  map { [ $_ => $access_counts{$_} ] } keys %$access_counts
)[0 .. 49];

say "Rank\tURL\tFreq.";
for my $i (0 .. $#popular_articles) {
  say join "\t", $i + 1, @{ $popular_articles[$i] };
}
add_sample メソッドにデータを渡すと対応するカウンタに1加算したことになります。frequencies メソッドで計数の結果がハッシュリファレンスとして返ります。 詳細は例によって perldoc 参照。

感想

状態を持ったオブジェクトは面倒くさかったです (小並感)。
Algorithm::LossyCount 0.02 で依存関係に Smart::Args が入っていますが消し忘れです。他に変更が無ければ来週にでも 0.03 をリリースします。

  1. ジップの法則 - Wikipedia ↩
  2. Manku, Gurmeet Singh, and Rajeev Motwani. "Approximate frequency counts over data streams." Proceedings of the 28th international conference on Very Large Data Bases. VLDB Endowment, 2002. ↩

2014年2月16日日曜日

京大テキストコーパスのパーサを書いた

要旨

CaboCha やなんかの出力形式であるところの京大テキストコーパス形式のパーサモジュールを Perl で書いたので紹介します。

これを使うと例えば CaboCha の出力した係り受け関係を Perl のオブジェクトグラフとして取得できます。

使用例

単なる文節区切りの例。

#!/usr/bin/env perl

use v5.18;
use utf8;
use IPC::Open3;
use Parse::KyotoUniversityTextCorpus;
use Parse::KyotoUniversityTextCorpus::MorphemeParser::MeCab;
use Symbol qw//;

my ($in, $out, $err);
my $pid;

BEGIN {
  ($in, $out, $err) = (Symbol::gensym, Symbol::gensym, Symbol::gensym);
  $pid = open3($in, $out, $err, cabocha => '-f1');
}

END {
  close $out;
  close $err;
  waitpid $pid => 0 if defined $pid;
}

binmode STDOUT, ':encoding(utf8)';
binmode $in, ':encoding(utf8)';
binmode $out, ':encoding(utf8)';

my $parser = Parse::KyotoUniversityTextCorpus->new(
  morpheme_parser =>
    Parse::KyotoUniversityTextCorpus::MorphemeParser::MeCab->new,
);

say $in '星から出るのに、その子は渡り鳥を使ったんだと思う。';
say $in '出る日の朝、自分の星の片付けをした。';
close $in;
my $sentence_trees = $parser->parse(fh => $out);
for my $sentence_tree (@$sentence_trees) {
  for my $chunk (@{ $sentence_tree->as_arrayref }) {
    printf(
      "\%d: \%s -> \%d\n",
      $chunk->id,
      $chunk->surface,
      $chunk->is_root ? '-1' : $chunk->dependency->id,
    );
  }
  print "\n";
}

実行すると:

0: 星から -> 1
1: 出るのに、 -> 5
2: その -> 3
3: 子は -> 5
4: 渡り鳥を -> 5
5: 使ったんだと -> 6
6: 思う。 -> -1

0: 出る -> 1
1: 日の -> 2 
2: 朝、 -> 6 
3: 自分の -> 4
4: 星の -> 5
5: 片付けを -> 6
6: した。 -> -1

立志

日本語係り受け解析器 CaboCha1 は大変便利ですごく便利ですが (便利なので2回言いました) 公式の Perl バインディングは SWIG 製で API 的にあんまり良い感じじゃないし CPAN にも上がっていないのが悲しい点です。MeCab に対する Text::MeCab のような素敵なバインディングも今のところありません。

簡単に使って幸せになるには cabocha コマンドをパイプで繋いで出力をパースするのが手っ取り早いです。CaboCha の出力形式には人間用のツリー形式の他に京都大学テキストコーパス (以下 KC)2/XML/CoNLL の各形式があります。 この中でパースし易いのは XML 形式ですが、これは CaboCha の独自形式 (だと思う) なので対応してもあまり面白くありません。KC 形式と CoNLL 形式は他のツールでも使われています。例えば日本語の構文解析器として CaboCha の他に KNP3 や J.DepP4 が知られていて、これらも KC 形式で出力ができるので必要になったら CaboCha から切り替えて使えます。多分これを処理する車輪は知の高速道路の路肩に一杯転がっているはずなんですが、見つからなくて辛いので自分で書くことにしました。

導入

Tarball を cpanm で突っこむのが早いです:

cpanm http://sekia.github.io/Parse-KyotoUniversityTextCorpus-0.01.tar.gz

リポジトリから最新版を入れる場合は Dist::Zilla (dzil) でビルドする必要があります:

git clone git@github.com/sekia/Parse-KyotoUniversityTextCorpus.git
cd Parse-KyotoUniversityTextCorpus
dzil install

そのうち CPAN に上げるので気の長い人はそれまで待っててください。

使い方

だいたい perldoc 参照ですが Parse::KyotoUniversityTextCorpusnew して parse したら係り受け関係の木構造の根 (即ち最後の文節) に相当する Parse::KyotoUniversityTextCorpus::Chunk を含んだ配列リファレンスが返ってくるので、ここからトラバースするのが基本的な使い方です。 上のコード例のように as_arrayref を呼ぶと文節が順番に並んだ配列リファレンスが返ってくるので単に文節を分割したいだけの時なんかは便利です。

MorphemeParser について

KC の文節中の形態素の出力形式は形態素解析器 JUMAN のものですが、CaboCha は内部で MeCab を使っているので当然 MeCab の形式になります。また MeCab は出力形式や辞書が設定で変更できるので、KC 形式でも形態素の出力形式は様々あることになります。 なので Parse::KyotoUniversityTextCorpus では形態素のパースはせず、一行一形態素とみなして MorphemeParser というオブジェクトに丸投げするようになっています。 ディストリビューションに含まれている MorphemeParser は Parse::KyotoUniversityTextCorpus::MorphemeParser::MeCab で、これは IPA 辞書を使った MeCab が出力するデフォルトの出力をパースできます。JUMAN とか ChaSen とか Unidic を使った MeCab とかの形式がパースしたい人は頑張って自分で書いてください。

TODO

  • Chunk にもっとメソッドを生やす
  • JUMAN の MorphemeParser も追加する
  • CPAN にアップロード