2017年2月15日水曜日

仕事で使わない Perl コーディングテクニック

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it? -- Brian Kernighan

(まずもって、デバッグがプログラミングの倍も難しいことは衆知である。だからもしあなたが能う限りの知力でコードを書いたとしたら、どうやってデバッグするのか?)

言語のマイナ機能とか関数のデフォルトの挙動なんかを駆使してプログラムを書くと未来の自分や同僚が困るので、普段はいくらか制限して書くと思う。 僕は Perl 5 だとライブラリはともかくアプリケーションのコードは「続・初めてのPerl (Intermediate Perl)」程度の知識を前提して書いていた。

要するに意図的に低俗なコードを書いているわけで面白くない。 だいたい頭の内にあるボンヤリとした「Perl 的な書き方」が実際に動くのがこの言語の良いところで、昔2ちゃんねるで見かけた「キモいが矛盾していない、それが Perl」というコメントはけだし慧眼だったと思う。

そんなわけでマイナであったり環境の都合で自制していた言語機能をいくつか紹介したい。

メソッドの事前解決

Perl 5 のメソッド呼出しは遅い。まずもってメソッドの解決が遅い。繰り返し同じメソッドを呼ぶときはメソッドを一度だけ解決してそれを直接呼び出したい。要するに Objective-C で selector を取得してそれを実行するようなことをやりたい。

名前のせいで述語と勘違いしがちだが UNIVERSAL::can はまさにこのメソッド解決を行う。例えば my $do_foo = $obj->can('do_foo'); とすれば $obj が属するパッケージないしその親クラスに存在する do_foo メソッドへのリファレンスが得られる。存在しない場合は undef である。

そうとなれば後は簡単で、メソッドは第一引数にインスタンスないしクラス名を受けるただのサブルーチンなので、$do_foo->($obj, ...) と呼び出せば動くことは動く。 しかしこれは不恰好である。抽象が破れているではないか。何故メソッド呼び出しだったものを関数呼び出しに書き換えなければならないのか。

実はメソッド呼び出しの矢印演算子の右辺には CodeRef が置ける。この場合メソッド解決は省略され、単に左辺を第一引数として右辺の CodeRef が呼ばれる。つまり解決済みの $do_foo メソッドを呼び出すには $obj->$do_foo(...) とすれば良い。

この事実は perlop と perlobj に載っているが、そもそもメソッド名は裸のワードであるから都合の良いときはほぼいつでもシンボリック・リファレンスで与えられることを我々は知っている。そうなればハード・リファレンスに拡張されることも自然に類推できる。

Perl 5.24 にて実験を行った。簡単なカウンタを作り、百万回 incr メソッドを呼んで数値をインクリメントする。"regular" は毎回メソッド解決を行い、"resolved" は can で解決済みのメソッドを使う:

#!/usr/bin/env perl

use strict;
use warnings;
use Benchmark qw/cmpthese/;

package Counter {
  sub new {
    my ($class, $initial) = @_;
    bless \$initial => $class;
  }

  sub count {
    my ($self) = @_;
    $$self;
  }

  sub incr {
    my ($self) = @_;
    ++$$self;
  }
}

cmpthese(
  -5,
  +{
    regular => sub {
      my $counter = Counter->new(0);
      $counter->incr for 1 .. 1_000_000;
    },
    resolved => sub {
      my $counter = Counter->new(0);
      my $incr = $counter->can('incr');
      $counter->$incr for 1 .. 1_000_000;
    },
  },
);

結果は以下の通りで、解決済みのメソッドを使う方が20ポイントほど高速であった:

bash-3.2$ perl ~/toybox/sel.pl
           Rate  regular resolved
regular  3.73/s       --     -18%
resolved 4.56/s      22%       --

ブロックの last / redo

ブロックは新しい字句的スコープを導入する。これはガードオブジェクトと組み合わせて確実にリソースを開放したいときなどに便利だが、それだけに留まらない。

ブロックは「一回こっきり実行されるループ」と見なして良い。つまりループ制御コマンドの last/redo はループでないただのブロックでも使用できる (next も使えるが last と同じになるので意味はない)。

これは途中で失敗したときにやり直す処理を書くのに便利である:

my @resources = (...);
my @locks;
my $retries = 0;
my $lock_succeed = 0;
TRY_LOCKS:
{
    last if $retries >= 3;
    for my $resource (@resources) {
        my $lock = try_lock($resource);
        unless ($lock) {
            ++$retry;
            @locks = ();
            redo TRY_LOCKS;
        }
        push $locks, $lock;
    }
    $lock_succeed = 1;
}

if ($lock_succeed) { ... }

Key-Value ハッシュスライス

これは Perl 5.8 フリーな環境では仕事で使っている人もいるかも知れない。

perldelta をちゃんと毎回読んでいる人には衆知だが Perl 5.20 からの新機能。Perl 5.10 の // defined-or 演算子や Perl 5.14 の /r 非破壊的置換修飾子以来のキラー機能だと思う。 要するにハッシュの一部だけを抜き出して偶数サイズのリストにする機能で、構文は大方の想像通り:

my %source = (foo => 1, bar => 2, baz => 3);
# equivalent: map { $_ => $source{$_} } qw/foo bar/;
my %projected = %source{qw/foo bar/};  # (foo => 1, bar => 2)

ちなみに existsdelete 演算子などと同様に配列にも一般化されている:

my @source = 'a' .. 'z';
# equivalent: map { $_ => $source[$_] } [3, 4, 5]
my %projected = %source[3, 4, 5];  # (3 => 'd', 4 => 'e', 5 => 'f')

少々異和感を覚えるが、代入の両辺で sigil が揃う点で一貫しているし慣れの問題だろう。

左辺値の返却

関数やメソッドは左辺値を返せる。左辺値であるからにはつまり代入できる。

C++ でも lvalue 参照を使うと同じことができて、std::mapoperator[] なんかが典型である。

組み込み関数で左辺値を返す典型は substr / vec / splice である。 perldoc -f substr を見るとプロトタイプは次のようになっている:

substr EXPR,OFFSET,LENGTH,REPLACEMENT substr EXPR,OFFSET,LENGTH substr EXPR,OFFSET

この内4引数版に代入するのはナンセンスなのでエラーになるが、2引数版と3引数版は第一引数 (EXPR) が左辺値であれば代入ができる:

my $str = 'bar';
substr($str, 2, 1) = 'z';  # $str eq 'baz'

つまり右辺の値は4引数版の第四引数に相当する。substr は第一引数への一種のビューを提供しているとも見なせるが、実際にはそれ以上のことを行う。代入される文字列の長さが substr で得られた文字列と異なる場合は元の文字列が伸縮する。例えば空文字列を代入することで部分文字列を削除できる。

ちなみ代入式全体の値は元の (置換された) 文字列である。上記の例であれば 'r' が返る。

同様にvec はビット列に対してビット列を代入することができるし、splice は配列に対してリストを代入できる。

また少し意外なものとしては keys も左辺値を返す。これは C++ の STL コンテナにある reserve メンバ関数に似ていて、事前にハッシュの記憶スロットを確保しておくのに使える:

my %code_map;
keys(%code_map) = 26;
$code_map{+chr} = $_ for 65 .. 90;

蛇足として keys 自体は Perl 5.12 から配列に対しても使えるが、この場合左辺値としては使えない。 配列の事前確保は特殊変数 $#array への代入で行えるが、こちらは伸びた領域が実際に undef で埋まってしまうので元の要素数に戻す一手間が要る:

my @char_map;
$#char_map = 26 - 1;  # Initialized with (undef) x 26
@char_map = ();  # もう一回空にするが、確保されたスロットはそのまま
push @char_map, chr for 65 .. 90;

さてユーザ定義する場合だが、lvalue 属性がついたサブルーチンの最後に評価される式が左辺値であれば良い。メソッドの例を示す:

package Foo;

sub new {
    my ($class) = @_;
    bless +{ foo => '' } => $class;
}

sub foo :lvalue {
    my ($self) = @_;
    $self->{foo};
}

package main;

use 5.024;

my $obj = Foo->new;
$obj->foo = 'bar';
say $obj->foo;  # 'bar'

属性 (attributes) を忘れている人も多いと思うが、要するに Java でいうアノテーションである。Catalyst なんかで見たことがあるだろう。

うっかり値を return してしまうと左辺値にならないことに注意が必要である。(return $x) = 42; はナンセンスだ。

ところでアクセサがオブジェクトの状態を左辺値として返すのはカプセル化の観点からはあまりよろしくない。代入される値を検査できないのでオブジェクトの状態が保障できないからである。 これを避けるには代入操作にフックして検査をすれば良い。C++ なら返す型の代入演算子 (operator=) をオーバーライドするが、Perl ではスカラの代入演算をオーバーライドする。つまり tie するのである:

package Bar;

use strict;
use warnings;

sub new {
    my ($class) = @_;
    bless +{ bar => 0 } => $class;
}

sub bar :lvalue {
    my ($self) = @_;
    tie my $v, 'Bar::NumberField' => $self->{bar};
    $v;
}

package Bar::NumberField;

use strict;
use warnings;
use Carp ();
use Scalar::Util qw/looks_like_number/;

# $_[1] は tie に渡された引数 (e.g., $self->{bar}) のエイリアスなので、
# リファレンスを保存しておくことで後で書き換えられるようにする。
sub TIESCALAR { bless \$_[1] => $_[0] }

sub FETCH { ${$_[0]} }

sub STORE {
    my ($self, $value) = @_;
    unless (looks_like_number $value) {
        Carp::croak("Seems like not a number: $value");
    }
    $$self = $value;
}

package main;

use strict;
use warnings;
use feature qw/say/;

my $bar = Bar->new;
$bar->bar = 42;
say $bar->bar;  # 42
$bar->bar = 'blah blah blah';  # Error.

この例だとやりたいことに比べて労力が馬鹿げているが、ともかく tie された変数を返すことで substr のような組み込み関数と同じ挙動をユーザ定義できるということに意義がある。 実際的には Sentinel のようなライブラリを使うことでシンプルに書ける。なんなら Moose も併用して値の検査を型制約に任せても良い。

¯

2017年2月10日金曜日

MacPorts の GHC が macOS Sierra でビルドできない件の回避策 (i.e. MacPorts のパッチの当て方)

多分じきに修正されて腐る内容だが、MacPorts の port にパッチする方法としてまとめておく。

会社を辞めたので久方ぶりにブログを書こうと思い、pandoc をインストールしようとしたところ GHC のビルドがコケた。 ログをみると GetTime.c というファイルのコンパイルに失敗している。MacPorts の Trac を検索してみると果たして既知の問題だった。「Haskell 処理系とそれに依存する全パッケージがインストールできない」問題が四ヶ月前に報告されていまだに直っていないという大らかさ。

幸いチケット内にパッチが提案されていたのでこれを適用してことなきを得た。

まずローカルに GHC の port をコピーし、MacPorts の ports tree として登録する:

$ sudo -i
Password:
# mkdir -p /usr/local/ports/lang/ && cd /usr/local/ports/lang/
# cp -r $(port dir ghc) ./
# cd ghc && port lint

# cp /opt/local/etc/macports/sources.conf{,.orig}
# vi /opt/local/etc/macports/sources.conf  # 作成したディレクトリをデフォルトの ports tree の前に追記する
# diff -u /opt/local/etc/macports/sources.conf{.orig,}
--- /opt/local/etc/macports/sources.conf.orig   2017-02-10 14:10:00.000000000 +0900
+++ /opt/local/etc/macports/sources.conf        2017-02-10 14:11:04.000000000 +0900
@@ -29,4 +29,5 @@
 # sites, etc.), the primary MacPorts source must always be tagged
 # "[default]", even if switched from the default "rsync://" URL.

+file:///usr/local/ports
 rsync://rsync.macports.org/release/tarballs/ports.tar [default]

# cd /usr/local/ports && portindex

これで ghc をインストールする際は /usr/local/ports 以下にあるソースが使われるようになった。port dir ghc コマンドを実行すると /usr/local/ports/lang/ghc と表示されるはずである。

続いてパッチを配置して Portfile を書き換える:

# curl -Lo $(port dir ghc)/files/patch-Fix-GetTime.c-on-Darwin-with-clock_gettime.diff https://trac.macports.org/raw-attachment/ticket/52582/patch-Fix-GetTime.c-on-Darwin-with-clock_gettime.diff
# cp $(port file ghc){,.orig}
# port edit ghc  # Portfile を編集する専用コマンド。要するに vi /usr/local/ports/lang/ghc/Portfile
# diff -u $(port file ghc){.orig,}
--- /usr/local/ports/lang/ghc/Portfile.orig     2017-02-10 14:24:42.000000000 +0900
+++ /usr/local/ports/lang/ghc/Portfile  2017-02-10 14:40:40.000000000 +0900
@@ -56,7 +56,8 @@

 patchfiles      patch-configure-workaround-bsdsed-incompatibility.diff \
                 patch-configure-disable-docs.diff \
-                patch-unix_lib_osx_sandbox_compatibility.diff
+                patch-unix_lib_osx_sandbox_compatibility.diff \
+                patch-Fix-GetTime.c-on-Darwin-with-clock_gettime.diff

 livecheck.type  none
 test.run        yes

これで改変は終わり。一般的にパッチで済む変更は port dir 以下の files ディレクトリにパッチを置いて Portfile を書き換えるだけで良い。

あとはビルドできるか試して実際にインストールするだけ。異様に時間がかかるのは GHC が巨大だからであってパッチが悪いわけではない:

# port clean ghc
# port build ghc  # この間に昼食に行って仮眠してその後コーヒーを入れるなどする
--->  Computing dependencies for ghc
--->  Fetching distfiles for ghc
--->  Verifying checksums for ghc
--->  Extracting ghc
--->  Applying patches to ghc
--->  Configuring ghc
--->  Building ghc
...
# port install ghc

この記事は Markdown で書いているので、これが公開されているということは筆者が pandoc をインストールできたということである。

参考

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 に含まれる機能)

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