論文が簡単に採録されるのも複雑な気分 - ny23の日記
震災の一ヶ月後に投稿した論文が某国内論文誌（英文）の特集号に採録された．六月上旬に第一回判定結果が来ると聞いていたが何の連絡もなく，いつ連絡が来るのかと内心心配していたが，今日ひと月遅れで結果の通知が来て，ごく軽微な修正のみ（タイポと表の体裁の改善）の照会なし採録だった．最終原稿の提出は10月と聞いていたが，来週には締切りとのこと．ずいぶん早いなぁ． 論文が採録されたこと自体はもちろん喜ばしいことなのだけど，少し物足りない感じがするのは，第一査読者，第二査読者，メタ査読者共，査読のコメントが 2-3 文（3行程度）しかなかったこと（軽微な修正に関する指摘を除く）．二流国際会議やワークショップの査読ならともかく，論文誌の査読コメントって，こんなにもシンプルで良いのだろうか．投稿したのは自分も査読したことがある国内論文誌だが，自分は（この論文誌に限らず）論文誌の査読では最低でも30行以上はコメ
文節区切り判定器の実装を公開 - ny23の日記
一年ほど前に構文解析器を公開したが，（文節区切りされたデータを入力する仕様で）単体では使えない状態のままずっと放置していた．ところが最近になって，幾つかの共著論文で公開した構文解析器を引用する機会があり，このままではマズイと思ったので，現時点で使っている文節区切り - ny23の日記で書いた200行弱のシンプルな文節区切りの実装を同梱してみた．文節区切りの入出力がパイプ経由の文字列渡しなのは明らかに無駄なのだけど，気にしないことにしよう． MeCab と組み合わせる場合，解析速度は新聞記事だと入出力（UTF-8）込みで12,000文／秒，ブログ記事なら21,000文／秒程度（3.2 Ghz CPU; MeCab だけだと，新聞記事で22,000文／秒程度（入出力込み）なので，そんなに悪くない速度ではないかと）*1．係り受けのところだけで評価すると（デフォルトのパラメタで）解析精度は91.8
トライ（ダブル配列，簡潔データ構造）と 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 を公開されたので，例によってベ
密／疎ベクトルのトレードオフを調べてみた - ny23の日記
k-means を実装していて，疎ベクトルと密ベクトルのトレードオフ（距離計算の速度差）が気になったので軽く実験してみた．具体的に知りたかったのは，どれぐらい疎なら疎ベクトルを使った方が距離計算が速くなるか，という問に対する答え．空間使用率の改善については sparse vector における index と value の型のサイズ比でほぼ自明に分かるが，速度に関してはコンパイラの最適化の加減もあるので良く分からない．以下がテストコード（ややずぼらな実装）． [追記] 折角なので，Eigen 3.0-beta2 とも比べてみた． #include <sys/time.h> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <tr1/random> #include <eig
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の日記
大規模データから 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の日記
以前トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記で比較に使った自作のレコード付き動的ダブル配列 (dda) の実装も公開．以下の論文のアルゴリズムを実装したもの． 矢田晋, 田村雅浩, 森田和宏, 泓田正雄, 青江順一．ダブル配列による動的辞書の構成と評価, 情報処理学会第71回全国大会, 1-263-1-264頁, 2009年3月. レコード付き動的ダブル配列 - ny23の日記から始まり，レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記 と二週間かかって書いた僅か360行の c++ ヘッダファイル．動的ダブル配列は上の分類器の学習手法で素性の重みの管理に使っているので，学習手法の実装に同梱した．std::tr1::unordered_map ベースのトライに
オープンソースとアルゴリズムの特許 - ny23の日記
GPL で公開していた構文解析ライブラリで実装していたアルゴリズム（の一つ）について，特許が出ているという指摘を受けたので，GPL で公開するのは不適切だと判断して，当該アルゴリズムの実装を取り除いた．このアルゴリズムは，同じくオープンソースな解析器 (LGPL/BSD) でも実装され公開されていたので，すっかり ok だと油断していた．確かに企業研究者の提案手法なので，特許が取られている可能性は頭の隅にはあったのだけど，それにつけても非常に残念だ．今回のアルゴリズムは，かんたん特許検索で提案者名を入れてもそれこそ「かんたんに」出てくるので，自分自身の過失だろう．が，それで済ませていいのだろうか．[最後にオチあり] 以前，Bayesian Setsの特許について - のんびり読書日記 を読んだ時も思ったけど，アルゴリズム（あるいはソフトウェア）の特許というのは，オープンソース開発者にとって
トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
