追加・削除をサポートしたレコード付きダブル配列の実装を公開 - ny23の日記
線形分類器のライブラリに同梱して公開した動的ダブル配列に削除機能と登録キー／値のダンプ機能を追加実装して，別パッケージとして公開した．標準的な静的ダブル配列のライブラリのインターフェスに加えて，追加，削除，登録キーのダンプを実装してある．自分では使わない共通接頭辞検索が派手にバグっていたのでついでに修正． 主な特徴は， 高速な追加: 整列したキーの追加は std::unordered_map*1の2倍速．ランダム順だと同程度． 高速な検索: ノードの探索に局所性があれば std::unordered_map の4倍速．なければ同程度． 高速な削除: 検索と同程度の時間で登録キーを削除可． 省メモリ: レコード込みで登録キーの3-4倍程度の消費メモリ．静的に構築したトライには負けるが std::unordered_map と同程度． 短いコード: ヘッダファイル一つで構成，500行程度． 4
C++11 で線形分類器の分散オンライン学習器を実装してみた - ny23の日記
自作の（非）線形分類器のオンライン学習器に， Distributed Training Strategies for the Structured Perceptron (NAACL 2010) で提案されている分散オンライン学習法 (Iterative Parameter Mixing) を実装してみた． 機械学習 × MapReduce - ny23の日記 で調べたのがもう2年以上前のことだから今更感はんぱない．と言っても，自作の分類器に実装したのは線形学習の分散化で，多項式カーネルを使った非線形学習の分散化はパラメタを効率的に分配するのが難しく，まだ実装できていない．というか，線形学習の分散化も平均化を行う場合はパラメタの管理が面倒で，効率的な実装になかなか辿りつけなかった． マルチコア CPU 向けの分散オンライン学習は C++11 で新たに導入された thread と lambd
インタフェースの表裏を意識する: GNU getopt & autotools - ny23の日記
公開しているコードについて問い合わせを受ける機会が増えてきたので，もう少しソフトウェアとして導入・利用し易くしようとインタフェース周りを作り直した．自作の（コマンドライン）オプション解析と手書きの環境依存 Makefile が利便性を損ねているのは明らかだったので，標準的なオプション解析ライブラリとビルドツールに対応することにした．オプション解析を書き換えたのはだいぶ前（自作の学習器が MacPorts から導入可能になっていた - ny23の日記）のことだけど関連するのでまとめてメモしておく． C++ で使えるオプション解析ライブラリは古典的な GNU getopt を初めとして getoptpp, google-gflags, boost::program_options, cmdline など色々あるが，最近のもので定番と呼べるほどのものはないようだ． How to Parse Co
別解出力をサポートした高速 k-means の C++ 実装を公開 - ny23の日記
二年ほど前，k-means をさらに速くする - ny23の日記 で書いた三角不等式を利用した高速 k-means の C++ 実装を公開した．以下の三つの論文を組み合わせた実装になっている．二年前の実装と比べると別解が出力できるようになったのが大きな違い． G. Hamerly. Making k-means even faster. (SDM 2010) D. Arthur and S. Vassilvitskii. k-means++: the advantages of careful seeding. (SODA 2007) [New] Y. Cui et al. Non-redundant multi-view clustering via orthogonalization. (ICDM, 2007) 前者二つを実装したのが二年前，別解出力をサポートしたのも一年以上前になる．
SIMD で線形分類器を省メモリ・高速化 - ny23の日記
公開している構文解析器と線形分類器のコードを更新した．（論文にするほどではないが）幾つか面白い結果が得られたのでメモ（どちらかというと構文解析器の更新が主だけれど，良いタイトルが思いつかなかったので線形分類器の更新内容をタイトルにした）． 構文解析器の実装は C++ に慣れる前に書き始めたもので，効率重視で継ぎ接ぎの変更を繰り返して，色々と見苦しいことになっている．幸い，全体で 2000行足らずと身動きが取れないほどのサイズでもないので，効率を落とさないよう注意しつつ，リファクタリング（というかコードの短縮化）を繰り返してきた．今回の更新では，if-else だらけで読み難い素性抽出のコードを書き直して条件分岐の数を大幅に削減した．変更については長くなるので末尾． コードも整理されたので，気分転換に素性選択を一日ほどしてみた．標準的なデータセットにおける一回の学習・テストが MacBook
整数列圧縮アルゴリズムの最前線 - ny23の日記
ちょうど二年ぐらい前，機械学習で疎ベクトルの圧縮に情報検索でよく使われる整数列の圧縮技術を使うことを検討したことがあった（オンライン学習でキャッシュを実装してみた - ny23の日記）．そのときは，オンラインで圧縮し Disk に保存，圧縮したベクトルは陽にメモリに置かず読む（OS に任せる）という実装で，（Disk IO のオーバーヘッドが大きく）圧縮さえすれば何を使っても大差なしという身も蓋もない結論になった（結局2行で書ける最も単純な Variable byte code を採用）． それ以降は整数列圧縮アルゴリズムに関する知識も NewPFD ぐらいで止まっていたのだけど，つい先日，現時点で最速の圧縮アルゴリズムの提案＋ここ数年の主な整数列圧縮アルゴリズム（Simple-8b (J. Software Pract. Exper. 2010), VSEncoding (CIKM 20
移植性の高い Python スクリプトを書く - ny23の日記
以前 Lua の処理系 LuaJIT が速くて羨ましいという話を書いたが，最近は Python でも JIT コンパイラ PyPy の性能向上が著しいようだ．どれぐらい速いかというと，以前実験した PA-I（機械学習）で LuaJIT での実行速度を上回るぐらい*1．Python はもともとスクリプト言語の中では実行速度が速い方だったが，PyPy の急速な性能向上によって Perl や Ruby といった競合言語に対して（実行速度の点で）差を広げつつあるようだ． そういうわけで，最近スクリプトを Python で書く機会が増えている．Python でコードを書く上でやっかいなのは（まともな）ワンライナーが書けないこと*2と，（処理系のバラつきに起因する）移植性の問題である．前者はどうにもならないので，perl / ruby / sed + awk などで回避することになるが，後者は公開する
RE: sort を使うときは，LC_ALL=C を忘れずに - ny23の日記
Twitter ID も livedoor ID もないので直接コメントできないが，sort (GNU coreutils) の名誉のために，ここにメモしておく． 404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な まず第一印象として，この程度のサイズのファイルのソートで sort (GNU coreutils) がいまどきこんなに遅いはずはない．LC_ALL=C で追試すると，やはり bucketsort との差は無くなった．上の記事（に対するツイート）は Twitter 上でもそれなりにリツイートされているように見えるのだけど，この実行時間に違和感を感じる人が全くいないのはどういうことなのだろうか．sort を実際に使う人がほとんど見ていないのか，それとも計算量が違うから速くて当然という思い込みか．
Python で構文木を端末に描画してみる - ny23の日記
巷にある構文解析器には，解析結果を木構造で端末に表示する機能がある．あった方が良いだろうなと思いつつ，自分で実装するのはいかにも面倒そうだと感じて，今まで後回しにしていた．いい加減そろそろ無いと困ると感じるようになってきたので，先日の通勤電車の中で暇つぶしに書いたら，思いの外あっけなく実装できたので，メモ代わりに残しておく．最初 Ruby でワンライナーで書けないかなと思ったが，流石に難しかったので，練習も兼ねて Python で実装してみた． #!/usr/bin/env python # -*- coding: utf-8 -*- # Usage: lattice_to_tree.py < in.KNP # translate parser output into human-readable dependency tree structure import sys # customi
std::(unordered_)map でメモリ使用量を見積もる - ny23の日記
以前，トライと STL コンテナの比較をした際，std::map, std::tr1::unordered_map についてはメモリ使用量をちゃんと測っていなかったが，都合により，コンテナ本体のメモリ使用量を見積もる必要が出てきたので gcc 4.7 の実装を眺めてみた． 結論から言うと，gcc では std::map <_Key, _Tp> のメモリ使用量は， template<typename _Val> struct _Rb_tree_node { _Rb_tree_color; // ノードの色 (enum; int) _Base_ptr; // 親ノードへのポインタ _Base_ptr; // 左ノードへのポインタ _Base_ptr; // 右ノードへのポインタ _Val; // value_type (std::pair <const _Key, _Tp>) }; -> si
たまには std::valarray のことも思い出してあげよう - ny23の日記
多クラス分類器をカーネル化してみたら，訓練速度が劇的に低下してガックリしたので，手持ちの二値分類器に多クラス分類器を追加実装してみた（というより，もともとそのつもりで多クラス分類器を実装していた，という方が正しいかも）．その際，コードの肥大化を抑えるため，可能な限り二値分類器（素性の重みは double）とコードを共有しようと，素性の重みに演算子がオーバーロードされている std::valarray (std::valarray ) を使ったら，多値分類器用のコードをほとんど書かなくて済んで非常に楽だった．std::valarray 便利過ぎる．今までその存在自体は知ってはいたものの， std::vector で充分という場面がほとんどで使うことがなかったが，今回の用途には完璧に嵌った． と，std::valarray の便利さに感心する一方で，あっちこっちで std::valarray
多クラス Passive Aggressive アルゴリズムの平均化 - ny23の日記
先日実装した多クラス Passive Aggressive アルゴリズムに平均化を実装してみた．コードは C++0x で多クラス分類器を実装してみた - ny23の日記 を参照．実装したと言っても大したものではなく，本質的には追加したのは4行（USE_AVERAGING で囲われたところ）．平均化すると，収束を待つ必要がなくなるので，繰り返し回数を 20->5 に変更して実験． # MacBook Air (Mid 2011); Intel Core i7 1.7 Ghz CPU, 4 GB Memory > g++ -DUSE_AVERAGING -std=c++0x -Wall -O2 spa.cc -o spaa # covtype > run spaa PA1 covtype.train covtype.test 0.1 5 read: 0.827s train: .....0.9
情報系の国際会議の採択率 - ny23の日記
ちょっとした理由*1で某国際会議のポスターセッションの採択率を調べた過程で，副産物として情報系の国際会議の採択率を各分野の研究者がまとめたサイトがいくつか見つかったので，メモしておく． Artificial Intelligence: Conference Acceptance Ratio Statistics – Adaptive Toolbox Linguistics: ACL Member Portal | The Association for Computational Linguistics Member Portal Software Engineering: Software Engineering Conferences (Statistics) Networking: Networking Conferences Statistics (http://ppadala.n
二進対数の高速計算を用いた単語クラスタリングの高速化 - ny23の日記
先日実装した単語クラスタリングでは，相互情報量を計算する際の対数計算がボトルネックとなっている．``Premature optimization is the root of all evil'' とは良く言ったものだが，これ以上コードを更新するつもりもなかったので，高価な演算（対数計算）を単純な演算に置き換える定番の最適化を行ってみた． 今回の高速化の対象は， float pmi (float p_ij, float p_i, float p_j) { return p_ij == 0 ? 0 : p_ij * log2 (p_ij / (p_i * p_j)); } という関数．この手の計算を高速化するには，可能な引数に対する結果を事前に計算した lookup table を用意するのが常套手段*1．lookup table を用いた対数計算の高速化手法は，以下の論文で提案されている．
情報系の国際会議・ジャーナルのランキング - ny23の日記
論文が簡単に採録されるのも複雑な気分 - ny23の日記を受けて，自分の専門の周辺分野（情報系）でどのようなジャーナルが権威があるのか（よく引用されるのか・知名度があるのか）知っておこうと思った．少し調べてみたら，Impact factor (IF, Garfield '72)，Conference PageRank などに基づく情報系の国際会議・ジャーナルのランキングを行っているサイトが見つかった*1． AMiner このランキングの上位から，普段主に投稿したり読んだり査読したりする国際会議・ジャーナルをさらってみると， 8 SIGMOD: ACM SIGMOD International Conference on Management of Data 16 VLDB: International Conference on Very Large Data Bases 19* VLDB
車輪の再発明は避けるべき，を実感 - ny23の日記
ここ最近，Percy Liang の Brown クラスタリングの実装を使って単語クラスタリングしていたのだけど，感覚的に実行速度が遅いと感じたので，これぐらい簡単なアルゴリズムなら再実装しても良いかと思って，以下の原著を見ながら C++ で実装してみた． Class-based n-gram models of natural language (Computational Linguistics, 1992) 単純なだけに300行ぐらいで実装できたが，相互情報量の損失の計算をサボるところが少し面倒で，既存実装と結果が一致するまでに丸一日かかった*1． 自分の実装と既存実装の処理速度を比べたところ 5-10 倍ぐらい速くなっており（大規模データを扱う場合には実行速度が 2 倍違うだけでも致命的なので）再実装して良かったと一瞬ぬか喜びしたのだけど，同じ C++ で同じアルゴリズムを実装して
SWIG でスクリプト言語用バインディングを書いた - ny23の日記
先週末から SWIG を使って分類器と学習器の Perl/Python/Ruby/Lua バインディングを書いていた．3年ぐらい前に書いた分類器の Ruby バインディングは，Ruby の C インタフェースが変わってそのままでは動かなかったので，結局一から書き直すことに．Python -> Ruby -> Perl -> Lua と書いてきて一番大変だったのは Perl．学部の時少し使っただけで，もはや文法をほとんど覚えていなかったので，何よりテスト用のスクリプトを書くのが大変だった． SWIG で書いた std::vector 用の入力インタフェースは以下．スクリプト言語側の配列を C++ の std::vector に詰め直して関数に渡すだけ．色々拾ったり編集したりしたものだけど，言語横断的に見れたほうが便が良いのでメモしておく．swig-2.0.3 + Perl 5.8.9/5.1
メタコマンド実行スクリプトを Python で書いてみた - ny23の日記
半指導している学生が Python のライブラリを使って実験しているので，最低限の知識はあった方が良いかと思って，今週半ばぐらいから Python でプログラムを書いたりしている．以下は，Ruby で書いたスクリプトの中で，最も使用頻度の高いメタコマンド実行スクリプトの Python 翻訳． #!/usr/bin/env python # cont: execte meta-commands with disjunctive arguments import sys, re, os if len (sys.argv) < 3: sys.exit ("Usage: run [n][c|p] command") # handle options opt = sys.argv[1] nruns, flag = (int (opt[:-1]), opt[-1] == 'p') \ if re.ma
粗末な（素性とモデルを用いた）単語分割に辞書情報を入れてみた - ny23の日記
文節区切り - ny23の日記や粗末な（素性とモデルで）単語分割 - ny23の日記の実験で，これらのタスクでは文脈の情報がほとんど要らないということは（ラベルバイグラムを考慮した）CRF との精度差が無いという事実を通じて確認していたけど，日本語の品詞タグ付けでもそうらしい． 日本語: Pointwise Prediction for Robust, Adaptable Japanese Morphological Analysis (ACL-HLT: 2011, short) 英語（参考）: Structure Compilation: Trading Structure for Features (ICML 2007; 前も引用した記憶が) この論文の単語区切りの素性は，去年の実験の素性に辞書情報を追加したものに近い*1ので，前のモデルの方にも辞書情報を入れて（mecab-juman
注釈付きデータ駆動の研究が辿り着くところ - ny23の日記
2月20日から東京で開かれる某国際会議で Christopher Manning が Part-of-Speech Tagging From 97% to 100%: Is It Time for Some Linguistics?*1 と題した基調講演を行うそうだ．自分はこの会議には参加しないので，講演を聴講することはできないのだけど，著者のホームページで講演内容に関する原稿が公開されていたので読んでみた．一言でまとめると，この原稿で Manning は，業界的には半ば「終わった」とみなされている品詞タグ付けタスクにおいて，現状の解析器の誤りの半数程度が注釈付けに起因することを指摘し，それを踏まえて「注釈を修正すること」の是非を議論している．かつて品詞タグ付けタスクに取り組んだことがある人や，自分で新しくタスクを定義してデータの注釈付けに取り組んでいる人は，是非読んで欲しい*2．それ以外
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
