僕のIT革命

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 / longjmp に pthread 果てはアセンブラによる実...

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

この記事について 先日の稿で 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 とみなせる。 Bag や Mix を使えば重みに応じて確率的に要素をサンプリングするような処理も可能なため、各種のアルゴリズムやビジネスロジックの記述にも便利だろう。 Set 、 Bag そして Mix はすべて不変クラスである。対応する可変クラスとして SetHash 、 BagHash そ...

これまでブログではデスマス調を用いていたけれども、推敲が要って面倒に思ったのでときどきはデアル調で書くことにする。 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 の {並列, 平行, 非同期} 処理機能の紹介で大変に面白か...

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(p...

要旨 Algorithm::SVM は極めて有用だけど API がなんか変なので注意が必要。 詳説 CPAN に Algorithm::SVM 1 というモジュールがあります。これ Support Vector Machine (SVM) 2 を提供する LIBSVM 3 という有名なライブラリの 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) より...

要旨 Algorithm::LossyCount というモジュールを書きました。これを使うとそこそこメモリ効率良く大規模なデータの計数ができます。アクセスランキング集計とかに使えるんじゃないでしょうか。 Github MetaCPAN 動機 例えばブログホスティングサービスで 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 が当てはまるこ...

要旨 CaboCha やなんかの出力形式であるところの京大テキストコーパス形式のパーサモジュールを Perl で書いたので紹介します。 Github Tarball on Github Ppages これを使うと例えば 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...

2014-01-01: CPAN にアップロードしたので追記。 要旨 Search::Fulltext という大変シンプルな全文検索モジュールがリリースされていたので、N-gram トークナイザを提供する Search::Fulltext::Tokenizer::Ngram を書きました。 Github MetaCPAN これを使うと日本語として怪しい表現でもとりあえずヒットするような全文検索ができます。 動機 大変シンプルなモジュールだったのでシンプルに使ってみようと思ったら現在のところ日本語のトークナイザは Search::Fulltext::Tokenizer::MeCab のみでした。Text::MeCab のインストールが億劫なのと、ワンダー日本語が跋扈している Web 文書なんかの検索だと N-gram の方が都合が良いこともあるので作ってみました。 念の為: N-gram って何 テキストを N 文字毎に区切ったもの。e.g., "色彩を持たない多崎つくると、彼の巡礼の年" から 2-gram を作ると "色彩", "彩を", "を持", ... "の年" といった具合になる。 要は文書中に出現する N 文字の組合せを網羅するので、N-gram を使ってインデックスを作ると N 文字以上のクエリにヒットする文書は一切取り零さなくなる。 短所は形態素の区切りを知らないので "京都" というクエリで "東京都" という語を含んだ文書までヒットする、N 文字以下のクエリは一切ヒットしない、N が小さいとインデックスが大きくなるなど。 使い方 インストール cpanm などを使ってインストールできます: cpanm Search::Fulltext::Tokenizer::Ngram Dist::Zilla (dzil) が必要です。面倒なら CPAN に上がるのを待つか `lib/` 以下をコピーで動きます。 git clone git@github.com:sekia/Search-Fulltext-Tokenizer-Ngram.git cd...

Notice: This article is outdated. Please refer an updated English tutorial . 要旨 かなり前になりますが、Algorithm::LibLinear という Perl モジュールを書きました。 CPAN Github これを使うと線形分類器などが高速に学習できます。テキストや画像の分類が応用として期待されます。 LIBLINEAR について LIBLINEAR は LIBSVM と同じ台湾国立大学の Chih-Jen Lin 教授のチームが公開しているオープンソースの機械学習パッケージです。 関数のロジスティック回帰、サポートベクター回帰及び線形 SVM による多クラス分類を行うことができます。LIBSVM と違ってカーネル関数を使うことはできませんが、はるかに高速に動作します。 Algorithm::LibLinear について LIBLINEAR には C++ で書かれたライブラリと、その機能を使って機械学習と分類・関数回帰を行うコマンドラインユーティリティが含まれています。 Algorithm::LibLinear はライブラリの機能を Perl からオブジェクト指向的に利用できるようにした上で、コマンドラインユーティリティの一部機能をライブラリ化して Perl で再実装したものです。 使い方 分類問題を解くときは、 訓練データセットの読み込み・スケーリング 学習器パラメータの設定 分類器の訓練 実データの分類 という手順で行います。 訓練データセットの読み込み 正解ラベルのついたデータを大量に用意して学習させます。 LIBSVM 形式のデータを読み込むか： my $data_set = Algorithm::LibLinear::DataSet->load(string => <<'EOD'); 1 1:0.1 2:0.1 4:0.1 -1 1:0.1 2:-0.1 3:0.1 ... EOD HashRef として表現されたデータを使います： my $data_set = Algorithm::LibLinear::DataSet->new(data_set => [ +{ feature => +{ 1...