2016年7月19日火曜日

libcoro で並行処理プログラムを書く

libcoro という C のライブラリがある。Perl Mongers にはおなじみ (だった) 協調スレッド実装である Coro.pm のバックエンドとして使われているライブラリで、作者は Coro と同じく Marc Lehmann 氏。

coro というのは Coroutine (コルーチン) の略で、要するに処理の進行を明示的に中断して別の実行コンテキストに切り替えたり、そこからさらに再開できる機構のことである。言語やプラットフォームによって Fiber と呼ばれるものとほぼ同義。

(ネイティヴ) スレッドとの違いはとどのつまり並行処理と並列処理の違いで、スレッドは同時に複数の実行コンテキストが進行し得るがコルーチンはある時点では複数の実行コンテキストのうち高々一つだけが実行され得る。 スレッドに対するコルーチンの利点は主に理解のし易さにある。スレッドの実行中断と再開は予測不可能なタイミングで起こるため、メモリその他の共有資源へのアクセスが常に競合し得る。一方コルーチンは自発的に実行を中断するまでプロセスの資源を独占しているため、コンテキスト・スイッチをまたがない限り共有資源の排他制御や同期などを考えなくて良い。

同時に一つのコルーチンしか実行されないということは、プロセッサのコア数に対して処理がスケールアウトしないことを意味する。ただしシングルスレッドのプログラムでも IO などの間はプロセッサが遊んでいるため、非同期 IO とコルーチンを組み合わせるなどして待ち時間に別の処理を行わせることで効率を高められることが多い。 また1コアでの性能に関しては、コンテキスト・スイッチの回数が減り、またスイッチング自体もユーザモードで完結するため、スレッドよりも高速である場合が多い。このため「軽量スレッド」とも呼ばれることがある。

libcoro の特徴

C で利用できるコルーチン実装は複数あって、Wikipedia にある Coroutine の記事 を見ても片手では足りない数が挙げられている。

libcoro がその中でどう特徴付けられるかというとポータビリティが挙げられる。

実装のバックエンドは Windows の Fiber や POSIX の ucontext の他、setjmp/longjmppthread 果てはアセンブラによる実装が選択でき、API は共通である。 少なくとも setjmp/longjmp は C90 の標準ライブラリ関数なので現代の OS であれば利用できるはずだ。

ライブラリはヘッダファイルと実装を収めたソースコードファイル1つずつからなる。 CVS レポジトリには Makefile すら含まれていない。ビルドするにはバックエンドを選択するプリプロセッサマクロを定義するだけで良い:

# CORO_SJLJ は setjmp/longjmp を使った実装
bash-3.2$ clang -DCORO_SJLJ -c -o coro.o coro.c
bash-3.2$ ar crs libcoro.a coro.o

あとは使用するプログラムとリンクするだけ:

# マクロはライブラリのコンパイル時と同じものを与える必要がある
bash-3.2$ clang++ --std=c++11 -DCORO_SJLJ -I. coro_usage.cc -L. -lcoro -static

API

シンプルなライブラリにはシンプルな API しかない。できるのは「一つのコルーチンから別のコルーチンを指定してコンテキスト・スイッチする」ことだけである。

コルーチンを一つ生成して実行するには以下の手順を踏む。ドキュメントはヘッダファイル内のコメントのみだが素晴らしく詳細である。

1. スタックを初期化する

まずコルーチンが使用する専用のスタックを確保する。スタック領域を確保して coro_stack 構造体を初期化する関数 coro_stack_alloc を使用する。 スタックは第二引数に指定した個数のポインタが保持できる大きさになる。要するに指定した数に8倍したバイト数が確保される。通常は考えるのが面倒なので0を指定するとよしなに確保してくれる。 戻り値は確保の成否を返す。

struct coro_stack stack;
if (!coro_stack_alloc(&stack, 0)) {
  perror("coro_stack_alloc");
}

2. コルーチンを作成する

コルーチン自身は coro_context 型で表現される。これを初期化する関数は coro_create である。

第一引数に初期化したいコルーチンへのポインタを指定する。残りの引数はコルーチンとして実行すべき関数、コルーチンに渡す引数へのポインタ、確保したポインタのサイズ、そして確保したスタック領域へのポインタである。 最後の二つは前もって確保した coro_stacksptrssze メンバがそれぞれ対応する。malloc やなんかで勝手に確保したメモリ領域を渡すと落ちるので注意。

coro_context context;
coro_create(
    &context,
    [](void *) { ... },
    nullptr,
    stack.sptr,
    stack.ssze);

C++ ユーザに残念なお知らせ: 関数として lambda は使えるが変数はキャプチャできない。何故かというに、coro_create の第二引数の型 coro_funcvoid (*)(void *) の typedef に過ぎないので lambda から coro_func への型変換 operator void(*)(void *) が必要だからである (ところでこれが合法なメンバ関数名なのはひどすぎると思う)。

coro_func が受け取る void * には coro_create の第三引数が渡される。外部の環境 (というより呼出し元のコール・スタック) をコルーチン内から参照したければここに必要なものを詰めてお土産に持たせることになる。このあたりは C なので仕方がない。

3. コルーチンを実行する

コルーチンの実行を開始するにはちょっと工夫が要る。libcoro にはコンテキスト・スイッチする関数しかないので、スイッチ元となるコルーチンが要るからである。

それで実行開始と終了のために特別な「空の」コルーチンを生成する必要がある。これは coro_context を null ポインタと0で初期化することで得られる:

coro_context empty;
coro_create(&empty, nullptr, nullptr, nullptr, 0);

これで準備ができたので、空のコルーチンから目的のコルーチンへコンテキスト・スイッチする。その際に使うのは coro_transfer である:

coro_transfer(&empty, &context);

以降再び coro_transfer が呼ばれるまで context が表すコルーチンが独占的に実行される。 コルーチンの実行を終了するときは空のコルーチンへ再度コンテキスト・スイッチすれば良い。

4. リソースを開放する

処理が終わったらメモリの片付けをする。コルーチンは coro_destroy で破棄し、対応するスタックは coro_stack_free で開放する:

coro_destroy(context);
coro_stack_free(stack);

coro_destroy(empty);  // 空のコルーチンに対応するスタックはないので coro_stack_free は不要

注意点

コルーチンへの引数が void * なのでどうやっても型チェックは効かない。また渡したオブジェクトの寿命をコルーチンの実行終了まで保たせるのはプログラマの責任である。

外部の環境をコルーチン内から参照できないので、コンテキスト・スイッチしたいときに coro_transfer に渡す自分自身をどうやって指定するかが問題になる。手っ取り早いのは static coro_context contexts[MAX_COROS] でも作ってまとめておく方法である。真面目にやるなら汎用のスレッドローカルストレージに類する機構を作ってそこに入れておくのが良いと思う。 あるいはコルーチンへの引数としてコルーチン自身へのポインタを渡しても良い。この場合スイッチ先のコルーチンか、あるいはそれを決めるディスパッチャのようなものを一緒に渡す必要がある。

サンプル

お決まりの producer/consumer のサンプル・プログラムを書いた。

libcoro の上に直接並行処理プログラムを書くのはさすがに辛いものがあるので、ちょっと高水準なライブラリを書いてそれを使うことにした。C で書くには人生が短すぎるので C++ で書いた。

単純なラウンドロビン・ディスパッチャを実装してコンテキスト・スイッチする先を考えなくても良いようにした。真面目に並行処理するなら優先度つきキューやらコルーチンの実行状態表やら導入してもっとマシなスケジューリングが要るが考えたくない。 コルーチン間の通信には Coro ライクな Channel 機構を作ってそれを利用した。

自前ライブラリの実装が150行。ユーザーコードである main が30行。標準外ライブラリへの依存はない:


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. ↩