追記: sort を使うときは，LC_ALL=C を忘れずに - ny23の日記
> wc --lines unigram_raw.txt 290768333 unigram_raw.txtそもそも，たかだか3億要素，1.7Gのデータのソートに，最近のマシンで sort | uniq -c が858分もかかるのは変ですよね． > export LC_ALL=C > time sort -S 2G unigram_raw.txt | uniq -c > tmp.sort.uniq sort -S 2G unigram_raw.txt 389.93s user 16.32s system 99% cpu 6:49.61 total uniq -c > tmp.sort.uniq 15.40s user 1.56s system 4% cpu 6:49.62 totalIntel Xeon E5462 (3.2Ghz) が Dual Core AMD Opteron 1210
非線形分類器のミニバッチ分散オンライン学習器を実装してみた - ny23の日記
ソフトウェアをいろいろ更新した - ny23の日記 で紹介した， Minibatch and Parallelization for Online Large Margin Structured Learning, NAACL 2013 がようやく学会で発表されたようなので，非線形学習版の実装を置いておく．RBF カーネルを用いたオンライン学習器をミニバッチ＋並列化したもの．実装したのはもう二ヶ月ぐらい前（論文の pdf を著者が公開した直後）なのだけど，流石に学会発表前に実装を出すのは気が引けたので公開を先延ばしにしていた． // mpa1.cc ; GNU GPL version 2 copyright@id:ny23 #include <err.h> #include <cstdio> #include <cstdlib> #include <cstring> #include <c
人手で頑張らない注釈付きデータの作成は可能か - ny23の日記
忘れないうちにメモ．中国の学会で感心した発表の一つに以下のような研究があった． Discriminant Ranking for Efficient Treebanking ポスター発表を聴講しただけなので，誤解しているところもあるかも知れないが，話としては単純で，曖昧性解消の注釈付けをする際に，作業者自身の履歴から曖昧性解消モデルを学習して注釈付け候補をリランキングして作業者に提示する，というもの．実際の作業を通して効果を計測しているのも良く，約1.5倍注釈付けが高速化される上，inter-rator agreement も上がったとのこと． この研究自体も面白いのだけど，人を分類器とみなして，機械学習の文脈で対応する手法を考えるとさらに興味深い．アプローチとしては， Revision Learning and its Application to Part-of-Speech Tagg
SIMD で線形分類器を省メモリ・高速化 - ny23の日記
公開している構文解析器と線形分類器のコードを更新した．（論文にするほどではないが）幾つか面白い結果が得られたのでメモ（どちらかというと構文解析器の更新が主だけれど，良いタイトルが思いつかなかったので線形分類器の更新内容をタイトルにした）． 構文解析器の実装は C++ に慣れる前に書き始めたもので，効率重視で継ぎ接ぎの変更を繰り返して，色々と見苦しいことになっている．幸い，全体で 2000行足らずと身動きが取れないほどのサイズでもないので，効率を落とさないよう注意しつつ，リファクタリング（というかコードの短縮化）を繰り返してきた．今回の更新では，if-else だらけで読み難い素性抽出のコードを書き直して条件分岐の数を大幅に削減した．変更については長くなるので末尾． コードも整理されたので，気分転換に素性選択を一日ほどしてみた．標準的なデータセットにおける一回の学習・テストが MacBook
ソフトウェアの更新も一人旅になってきた - ny23の日記
最近研究のことを全然書いていないけれど，先月末にオープンソースで公開している線形分類器（分類専用のライブラリと学習器）と構文解析器の実装をこっそり更新しておいた．分類器は MacPorts に登録して頂いているのだけど，まだ対応していないかなと思って，分類専用のライブラリを（公開時点の版よりさらに速くするアイデアを思いついたので実装して）差し替えようとしたら，分類器も学習器も公開した翌日に Portfile が更新されていて驚いた． 今回の更新では分類専用のライブラリがアルゴリズム的な工夫で最大2倍程度速くなった*1．その恩恵で構文解析器も速くなった．一番最初に公開した頃は競合する構文解析器と違いが出るように（速度）差をさらに広げようと頑張っていたのだけど，今となっては解析速度だけでなく解析精度も一人旅になりつつある．解析速度については既存実装の十倍以上速く，解析精度も（最高精度のモデルに
インタフェースの表裏を意識する: GNU getopt & autotools - ny23の日記
公開しているコードについて問い合わせを受ける機会が増えてきたので，もう少しソフトウェアとして導入・利用し易くしようとインタフェース周りを作り直した．自作の（コマンドライン）オプション解析と手書きの環境依存 Makefile が利便性を損ねているのは明らかだったので，標準的なオプション解析ライブラリとビルドツールに対応することにした．オプション解析を書き換えたのはだいぶ前（自作の学習器が MacPorts から導入可能になっていた - ny23の日記）のことだけど関連するのでまとめてメモしておく． C++ で使えるオプション解析ライブラリは古典的な GNU getopt を初めとして getoptpp, google-gflags, boost::program_options, cmdline など色々あるが，最近のもので定番と呼べるほどのものはないようだ． How to Parse Co
はてなダイアリーからはてなブックマークボタンを削除した - ny23の日記
[追記]: はてな側での対応により，記事の大半が現在の実態を反映していませんが，騒動の記録という意味で残しておくことにします． はてなブックマークボタンが設置されたページを閲覧すると，http://b.st-hatena.com/js/bookmark_button.js によりマイクロアドのトラッキング cookie が仕込まれ，ユーザのブラウザ閲覧履歴が追跡されるようになることが話題になっている（本ブログからは削除済み）． はてなブックマークボタンを表示する - はてなブックマークヘルプ（行動情報の取得について） ブログパーツやソーシャルボタンの類でアクセスログが残るのは当然だけどトラッキングされるのは当たり前にはなっていない - 最速転職研究会 はてなブックマークボタンのトラッキング問題で高木浩光先生が決別ツイートをするに至った経緯まとめ - NAVER まとめ 確かに， http:
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
可視化系の国際会議に共著論文が通った - ny23の日記
第二著者としてかなりコミットしていたビジュアル（可視化）系の共著論文が，採択率 1/3 ぐらいの国際会議に採録された．11月の湯治中に最初の採否の通知が来たのだけど，国際会議にも関わらず条件付き採録という結果だった．結果が来るのは知っていたものの（まさか国際会議で条件付き採録とは予想できず）湯治中だったので迷惑をかけてしまったが，第一著者を中心にせっせと直して（自分も途中から参加して）先月末に再投稿した．それから一週間，改めて採否の結果が来て，ようやく採録となった．今回の研究はそもそもネタを持ち込んだのが自分なので，無事通ってくれてほっとした．採録されたのは可視化系の国際会議なので，自分の専門分野の研究者にはほとんど知られることは無いかも知れない．折角なので，少しこの研究のことなどを書いてみる． 今回の研究は，大規模データ（個人的な感覚では中規模ぐらい）を，文ではなく構文解析した結果の可視
機械学習／テキスト処理 × Lua (LuaJIT) - ny23の日記
Python で書いた Passive Aggressive-I が C++ 実装に比べて50倍遅かったので，（スクリプト言語でも）もう少しぐらい速くならないかと思って，スクリプト言語で最速の処理系 (LuaJIT) を持つ Lua で Passive Aggressive-I を実装してみることにした． Lua はアプリケーションへの組み込みを意図し，高速な動作，ポータビリティ，拡張の容易さなどを重視して設計されたコンパクトな汎用スクリプト言語．今月の TIOBE Programming Community Index では Ruby の一つ下の12位にランキングされている*1．これは，iPhone アプリの開発者による利用が増えているというのが大きい*2と思うが，プログラム言語の設計者たちへのインタビューを纏めた Masterminds of Programming（邦訳: 言語設計者
Boogie Board LCD Writing Tablet (メモ環境構築のためのプチまとめ) - ny23の日記
手書きの文字＋スケッチでメモをとる場合には，どういう手段・媒体を使うのが良いだろうか．自分の場合，研究のアイデアやアルゴリズムのデータ構造などを（フリーハンドで）描きながら考えるのには，昔ながらの紙媒体 Moleskine Pocket Squared Notebook Classic*1 パイロット フリクションポイント04（ブルーブラック）*2 BOOK DARTS を愛用している．0.4mm のフリクションポイントは，巷に出回っている 0.7mm のフリクションボールと違って Moleskine に細かい字を書くのに十分な細さがあり，（残しておきたい）試行錯誤の過程をメモするにはこれでほとんど不満は感じていない．ただ，普段の生活では紙媒体で残すほどでもない走り書きをしたくなることも多く，そういうときは *scratch* として裏紙を使っていて無駄が多いと感じていた． そこで最近，某
トライ（ダブル配列，簡潔データ構造）と STL コンテナの比較（最新版） - ny23の日記
[2011/11/30 更新; std::(unordered_)map でメモリ使用量を見積もる - ny23の日記に従い，STL コンテナのメモリ使用量を計測] [2011/02/21 更新: marisa-trie 0.1.3; 発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮） - やた＠はてな日記 にてこの記事の実験結果を引用されているので，以後原則更新しないこととする．なお，marisa-trie は 検索時間が短くなりました - やた＠はてな日記 にあるように，marisa-0.2.0-beta3 以降ではさらに検索が速くなっています．] [2011/02/18 更新: marisa-trie の仕様変更に伴い，追記の記述を整合性が取れるよう変更; 最新版では未確認] id:s-yata さんが marisa-trie を公開されたので，例によってベ
k-means をさらに速くする - ny23の日記
昨日，今日と電車に乗っている時間が長かったので，暇つぶしに論文を読んでいた． Making k-means even faster (SDM 2010) この論文では，Elkan の三角不等式を用いた k-means の高速化手法 Using the triangle inequality to accelerate k-means (ICML 2003) のアイデアを元に，空間計算量を悪化せず k-means を高速化する手法を提案している．手法自体の新規性はそれほどない感じだけど，空間使用率を大幅に改善しつつ，かつ実際に幾つかのデータで Elkan の手法以上の高速化が得られたことに意義があるのかな． [追記; 2013/02/20] 別解出力をサポートした高速 k-means の C++ 実装を公開 - ny23の日記 で実装を公開しました．自分の専門分野だと，クラスタリングする対象
効率的な実装を自動的に見つけることは可能か - ny23の日記
最近は新しいアルゴリズムが提案されると，素早く実装する人が沢山いる．また，色々な実装を比較して情報を公開している人もたくさんいる．いずれにせよ，そこに多分の労力が割かれていることは間違いない．利用者側の立場からすると，「取り敢えず公開されていたから」という理由で，非効率的な実装を運悪く選択し，ボトルネックになっていると気がつかないで使い続けたりするのはなるべく避けたい．実装する側からすると，高級言語が隠蔽するライブラリの落とし穴にどういうものがあるのかは，把握しておきたい． さて，なるべく労力を使わず，（非）効率的な実装を自動的に判別することは可能だろうか．例えばプログラム言語を限定して (C++ とか)，ある特定の問題を解く実装の中から，（例えば機械学習などを用いて）時間／空間効率の良い（悪い）実装を見つけることはできるだろうか．あるいは逆に，時間／空間効率の良い（悪い）実装を示唆する素
大規模データで単語の数を数える - ny23の日記
大規模データから one-pass で item（n-gram など）の頻度を数える手法に関するメモ．ここ数年，毎年のように超大規模な n-gram の統計情報を空間／時間効率良く利用するための手法が提案されている．最近だと， Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval (EMNLP 2010) とか．この論文では，最小完全ハッシュ関数や power-law を考慮した頻度表現の圧縮など，細かい技術を丁寧に組み上げており，これぐらい工夫が細かくなってくるとlog-frequency Bloom filter (ACL 2007) ぐらいからから始まった n-gram 頻度情報の圧縮の研究もそろそろ収束したかという印象（ちょうど論文を読む直前に，この論文の7節の
機械学習 × MapReduce - ny23の日記
個人的な興味というより，雑用絡みで眺めた論文の紹介．機械学習アルゴリズムを並列分散化するという話が最近流行っているようだ．全然網羅的ではないけど，誰かの役に立つかも知れないので，幾つかメモしておく．まず古典的にはこれ， Map-reduce for machine learning on multicore (NIPS 2006) 古典的な機械学習アルゴリズム（バッチ学習）の多くは，Statistical Query Model で記述できて，それらは summation form で記述できる (から，MapReduce で並列化できる)．実装は Mahout．ただ最近は，バッチアルゴリズムで解ける問題には多くの場合対応するオンラインアルゴリズムが提案されていて，バッチアルゴリズムを並列化することのメリットはあまり無い．オンラインアルゴリズムだとパラメタが連続的に更新されるので，MapR
キャッシュありオンライン学習の実装を公開 - ny23の日記
多項式カーネルで別データから再学習する際のバグを直すついでに更新しておいた．オンディスク版の random_shuffleも同梱．実験結果は徐々に更新．オンメモリ版とオンディスク版の速度差は，訓練データのシャッフル時間程度の差になった（ディスクキャッシュが効いてしまっているからだと思うけど）． [追記]バッチ学習を除いて実験結果を更新した．懸案のliblinear-poly2-1.7 は，liblinear-poly2-1.6 を変更したときのソースを元に diff でパッチを作ったらそのまま適用できたので楽だった．あと，make 時に出た型不一致の warning を6箇所ほど直してコンパイルしたら無事動いた． しかし，メモリと実行時間を同時に測れるのはやっぱりすごく便利だ． [追記]バッチ学習も実験結果を更新した．
MapReduce と四身の拳 - ny23の日記
最近大規模データを処理するのに MapReduce とかがよく使われるのだけど，クラウドなど分散環境を使う人は基礎的なアルゴリズムを書く訓練もした方がいい．そもそも並列・分散系の環境は，最高速のアルゴリズムでも時間がかかる処理を，さらに速くするために使うべきものであって，基礎的なアルゴリズムの高速な実装ができない人が，実装をサボるために使うべきものではない．基礎的なアルゴリズムの差は MapReduce を使っても残る．特にデータが巨大になり，かかる時間が伸びれば延びるほど，基礎的なアルゴリズムの速度差が致命的になる（10分かかる処理が20分かかっても気にならないかもしれないが，1週間かかる処理が2週間もかかったら致命的; 1000台あるマシンを2000台に増やす方法を考える前に，ベースのプログラムの処理速度を2倍にすべし）． こんな例を出すと，年がバレるが，日曜プログラマが1000台のマ
動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記
Wikipediaによるテキストマイニング入門など，Wikipedia 中の単語頻度を測るのが流行っているようだ．例えば，Hadoop を使ったり（Hadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記），ハッシュを使ったり（Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記）とか．情報系の人間なら普通はハッシュで十分と思うところ，折角なので動的ダブル配列を使って測ってみた．動的ダブル配列から保存された文字列を効率的に取り出すには，ノードリンクを実装して traverse () を再帰的に呼び出せば良い．今回は MSD radix sort 用に sibling のリンクを昇順にしたバージョン（僅かに追加速度が低
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
