タグ

2011年1月21日のブックマーク (32件)

  • 吉永直樹 / Naoki Yoshinaga, Ph.D --- University of Tokyo

    Ee-503, 4-6-1 Komaba, Meguro-Ku, Tokyo, 153-8505, Japan +81-3-5452-6239 ynaga (at) iis [guess from URL] For prospective students (updated on Apr. 21st, 2021): at first, refer to Admission guide and Laboratory leaflet. We accept a wide range of students who want to take the master's or Ph.D. program in our lab. For those who want to enter PhD program, send a presentation slide in English on a paper

  • 密/疎ベクトルのトレードオフを調べてみた - 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

    密/疎ベクトルのトレードオフを調べてみた - ny23の日記
  • 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の日記 で実装を公開しました.自分の専門分野だと,クラスタリングする対象

    k-means をさらに速くする - ny23の日記
  • 効率的な実装を自動的に見つけることは可能か - ny23の日記

    最近は新しいアルゴリズムが提案されると,素早く実装する人が沢山いる.また,色々な実装を比較して情報を公開している人もたくさんいる.いずれにせよ,そこに多分の労力が割かれていることは間違いない.利用者側の立場からすると,「取り敢えず公開されていたから」という理由で,非効率的な実装を運悪く選択し,ボトルネックになっていると気がつかないで使い続けたりするのはなるべく避けたい.実装する側からすると,高級言語が隠蔽するライブラリの落とし穴にどういうものがあるのかは,把握しておきたい. さて,なるべく労力を使わず,(非)効率的な実装を自動的に判別することは可能だろうか.例えばプログラム言語を限定して (C++ とか),ある特定の問題を解く実装の中から,(例えば機械学習などを用いて)時間/空間効率の良い(悪い)実装を見つけることはできるだろうか.あるいは逆に,時間/空間効率の良い(悪い)実装を示唆する素

    効率的な実装を自動的に見つけることは可能か - ny23の日記
  • 人手で頑張らない注釈付きデータの作成は可能か - ny23の日記

    忘れないうちにメモ.中国の学会で感心した発表の一つに以下のような研究があった. Discriminant Ranking for Efficient Treebanking ポスター発表を聴講しただけなので,誤解しているところもあるかも知れないが,話としては単純で,曖昧性解消の注釈付けをする際に,作業者自身の履歴から曖昧性解消モデルを学習して注釈付け候補をリランキングして作業者に提示する,というもの.実際の作業を通して効果を計測しているのも良く,約1.5倍注釈付けが高速化される上,inter-rator agreement も上がったとのこと. この研究自体も面白いのだけど,人を分類器とみなして,機械学習の文脈で対応する手法を考えるとさらに興味深い.アプローチとしては, Revision Learning and its Application to Part-of-Speech Tagg

    人手で頑張らない注釈付きデータの作成は可能か - ny23の日記
  • ux... - ny23の日記

    ux-trie(簡潔データ構造のトライで,tail を実装してさらに tail 自体もトライ化して圧縮する)のバグが直ったようなので,トライのサイズや検索性能を調べているのだけど,長い tail を持つようなデータだと,トライのサイズが tx 比で 1/2 近くまで小さくなる一方,検索は(辞書順だと)tx 比で倍程度遅くなるようだ(tail を圧縮しないと tx よりトライのサイズが大きくなる).これぐらい極端だと,かえって潔い感じかもしれない.トライ(ダブル配列,簡潔データ構造)と STL コンテナ - ny23の日記に ux を加えて再実験したものは以下の通り. ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Sea

    ux... - ny23の日記
  • キャッシュありオンライン学習の実装を公開 - ny23の日記

    多項式カーネルで別データから再学習する際のバグを直すついでに更新しておいた.オンディスク版の random_shuffleも同梱.実験結果は徐々に更新.オンメモリ版とオンディスク版の速度差は,訓練データのシャッフル時間程度の差になった(ディスクキャッシュが効いてしまっているからだと思うけど). [追記]バッチ学習を除いて実験結果を更新した.懸案のliblinear-poly2-1.7 は,liblinear-poly2-1.6 を変更したときのソースを元に diff でパッチを作ったらそのまま適用できたので楽だった.あと,make 時に出た型不一致の warning を6箇所ほど直してコンパイルしたら無事動いた. しかし,メモリと実行時間を同時に測れるのはやっぱりすごく便利だ. [追記]バッチ学習も実験結果を更新した.

    キャッシュありオンライン学習の実装を公開 - ny23の日記
  • オンライン学習でキャッシュを実装してみた - ny23の日記

    手持ちのオンライン学習器で訓練データをメモリに載せず処理するモードがオンメモリで処理するモードに比べて5倍ぐらい遅いのが気になったので,Vowpal Wabbit みたく訓練データをキャッシュしてみることにした.まず準備として,Simple-9 と Variable byte code (vByte),さらに binary でそのまま保存する場合 (Raw) に,訓練データの符号化(入出力込み)/復号化 (入力のみ込み) の性能を比較してみた.普段使っている訓練データをx100倍したもの (約3000万訓練例, 819,841,000 integers) を入力.Disk Cache の扱いがいい加減だったので,再実験した.さらに,Group Varint Encoding の結果も追加した. 素性番号を適当につけた場合 (5952MiB) | Simple-9 | vByte |Grou

    オンライン学習でキャッシュを実装してみた - ny23の日記
  • Exploiting Feature Covariance in High-Dimensional Online Learning - ny23の日記

    二値素性でのオンライン学習の実験まとめ - ny23の日記 で CW は素性数が多いと共分散行列のサイズが問題になるという話をしたが,その改良をしたよ(共分散行列を rank の低い行列で近似)という論文.Online Passive-Aggressive Algorithms on a Budget - ny23の日記 と同じ,AISTATS という学会に出たようだ.数カ月前にダウンロードしていたのだけど,放置していた.話としてはあるだろうなとは思っていたが,近似パラメタが一つ増えるのはちょっとやな感じ.そもそもオンライン学習の時点で近似なのだけど,さらに近似を重ねるパラメータが増えるのは感覚的に気持ち悪い.

    Exploiting Feature Covariance in High-Dimensional Online Learning - ny23の日記
  • Mersenne Twister でランダムに行をシャッフル - ny23の日記

    テキストファイルでランダムに行をシャッフルしたい場合,sort -R やその改良 (以下,sort -n) は標準入力を読めたり,メモリ周りを気にしなくて良かったりと使い勝手は非常に良いのだけど,Vapnik の原理が頭にあると sort が O(n log n) なのが少し気になるので,O(n) な Fisher-Yates shuffle (Durstenfeld's version) ベースの std::random_shuffle と std::tr1::mt19937 (または random ())を使って行をシャッフルしてみた. Mersenne Twister でランダムに行をシャッフル (2) - ny23の日記 に sort -R|-n の代替になりうる実用版あり. 注意: MAX_MEM_SIZE=0 にすると,Random Write を行数回行うことになるので SS

    Mersenne Twister でランダムに行をシャッフル - ny23の日記
  • Vowpal Wabbit (Fast Learning)

    This is a project started at Yahoo! Research and continuing at Microsoft Research to design a fast, scalable, useful learning algorithm. VW is the essence of speed in machine learning, able to learn from terafeature datasets with ease. Via parallel learning, it can exceed the throughput of any single machine network interface when doing linear learning, a first amongst learning algorithms. We prim

  • Vowpal Wabbit 入れてみた - ny23の日記

    Vowpal Wabbit を試してみようと思ったが,MacPorts で入れた gcc 4.5 (gcc-mp-4.5) からだと io.h から string.h を,example.h から pthread.h を,さらに loss_function.h から stdlib.h を追加で include する必要があった.さらに,boost の program_options が必要なので,MacPorts 経由で boost をインストールして,Makefile を編集し,漸くコンパイルに成功した.なのに,実行すると malloc: *** error for object 0xa03066d8 ... が連打.なんなの.valgrind で調べたら boost が Apple gcc-4.0 でコンパイルされているせいっぽい.Apple gcc で vw を再コンパイルしたら動い

    Vowpal Wabbit 入れてみた - ny23の日記
  • レコード付き動的ダブル配列の実装も公開 - ny23の日記

    以前トライ(ダブル配列,簡潔データ構造)と STL コンテナ - ny23の日記で比較に使った自作のレコード付き動的ダブル配列 (dda) の実装も公開.以下の論文のアルゴリズムを実装したもの. 矢田晋, 田村雅浩, 森田和宏, 泓田正雄, 青江順一.ダブル配列による動的辞書の構成と評価, 情報処理学会第71回全国大会, 1-263-1-264頁, 2009年3月. レコード付き動的ダブル配列 - ny23の日記から始まり,レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記 と二週間かかって書いた僅か360行の c++ ヘッダファイル.動的ダブル配列は上の分類器の学習手法で素性の重みの管理に使っているので,学習手法の実装に同梱した.std::tr1::unordered_map ベースのトライに

    レコード付き動的ダブル配列の実装も公開 - ny23の日記
  • オープンソースとアルゴリズムの特許 - ny23の日記

    GPL で公開していた構文解析ライブラリで実装していたアルゴリズム(の一つ)について,特許が出ているという指摘を受けたので,GPL で公開するのは不適切だと判断して,当該アルゴリズムの実装を取り除いた.このアルゴリズムは,同じくオープンソースな解析器 (LGPL/BSD) でも実装され公開されていたので,すっかり ok だと油断していた.確かに企業研究者の提案手法なので,特許が取られている可能性は頭の隅にはあったのだけど,それにつけても非常に残念だ.今回のアルゴリズムは,かんたん特許検索で提案者名を入れてもそれこそ「かんたんに」出てくるので,自分自身の過失だろう.が,それで済ませていいのだろうか.[最後にオチあり] 以前,Bayesian Setsの特許について - のんびり読書日記 を読んだ時も思ったけど,アルゴリズム(あるいはソフトウェア)の特許というのは,オープンソース開発者にとって

    オープンソースとアルゴリズムの特許 - ny23の日記
  • Mac OS X と Linux で rand () の実装が違うのか - ny23の日記

    時間計測用のサーバ (Mac OS X 10.5) は 32GB しかメモリがないので,20GB ほどメモリを消費する L1-LLM (SGD) のハイパーパラメタの調整には 256GB のサーバ (Red Hat Enterprise Linux 5.4) を使っていたが,ライブラリまで含めて同じバージョンの gcc (4.5.0) でコンパイルした学習器が二つのサーバで微妙に異なるモデルを学習するのに気がついた.少し調べると,どうも(学習を安定させるため)訓練例を random_shuffle しているところが良くないらしい.gcc 4.5.0 の実装 (include/c++/4.5.0/bits/stl_algo.h) では,どちらも rand () を呼んで乱数を生成しているのだが,実験の再現性を確保するため srand () は敢えて呼んでないので,rand () の実装が同じ

    Mac OS X と Linux で rand () の実装が違うのか - ny23の日記
  • n-best を数式で表現する方法 - ny23の日記

    集合 の各要素に対して,スコア関数 が定義されているとき,その集合中のスコアの上位 n 要素から構成される部分集合 を数式で書きたくなった(ただし,スコア関数は単射とし, は一意に定まるとする).n-best がタイトルに入った論文などを色々見てみたが,ほとんど言葉で定義されていて,数式で書いているものは少ない.すぐ思いつくのは, 外延的記法っぽいの(帰納的定義): として, 内包的記法っぽいの(n-部分集合+条件): 裏技: \argmax 的に部分集合を返す \nbest (\argmaxN) を定義する どれも微妙だ.mimetex の表示品質ぐらい気に入らないが,強いて言えば一つ目が一番ましか.まどろっこしい書き方だが,一番スコアが高いものから一つずつ選ぶというのを補助関数無しで表現するとこうなる.二つ目は短いけど,どんな集合を意味しているか分かりにくいのが玉に瑕.三つ目は最終手段

    n-best を数式で表現する方法 - ny23の日記
  • iPhone で読む (Machine Learning 系) Tutorial スライドの個人的なまとめ - ny23の日記

    iPhone で論文の pdf を読むのは,iPhone 4 の解像度でも画面のサイズ的に厳しそうなのだけど,スライドなら iPhone 3GS 程度の解像度でもストレスなく読めるので,機械学習系の Tutorial スライドをまとめてみた.NIPS/ICML などはビデオもあるのでそっちを見るのもありかも.内容的に被ってるのも差を見るために列挙.応用分野の研究者なので,かなり偏っています(ごく一部関係ないのも混ざってる). Metric Learning (by B. Kuils; ICML 2010) Domain Adaptation (by J. Blitzer and H. Daume III; ICML 2010) Sparse Modeling: Theory, Algorithms and Applications (by I. Rish & G. Grabarnik; I

    iPhone で読む (Machine Learning 系) Tutorial スライドの個人的なまとめ - ny23の日記
  • MapReduce と四身の拳 - ny23の日記

    最近大規模データを処理するのに MapReduce とかがよく使われるのだけど,クラウドなど分散環境を使う人は基礎的なアルゴリズムを書く訓練もした方がいい.そもそも並列・分散系の環境は,最高速のアルゴリズムでも時間がかかる処理を,さらに速くするために使うべきものであって,基礎的なアルゴリズムの高速な実装ができない人が,実装をサボるために使うべきものではない.基礎的なアルゴリズムの差は MapReduce を使っても残る.特にデータが巨大になり,かかる時間が伸びれば延びるほど,基礎的なアルゴリズムの速度差が致命的になる(10分かかる処理が20分かかっても気にならないかもしれないが,1週間かかる処理が2週間もかかったら致命的; 1000台あるマシンを2000台に増やす方法を考える前に,ベースのプログラムの処理速度を2倍にすべし). こんな例を出すと,年がバレるが,日曜プログラマが1000台のマ

    MapReduce と四身の拳 - ny23の日記
  • 浅い文解析器と深い文解析器 - ny23の日記

    某資料で速度比較があって,どちらも一番速いものが20文/秒とあったけど,これは単に深い文解析器が速いと言うより,比べている浅い文解析器が遅過ぎるのではないかと思う.係り受け解析ぐらいなら,速いものなら10000文/秒ぐらいは出るでしょう(日語で transition-based なアルゴリズムで良ければ,三年前の計算機環境で,学部生の演習レベルの実装でも(多分係り受け解析のところだけだけど)7500文/秒とか出てた).深い文解析にも昔関与していた身からすると,ずいぶん速くなったなとは思うけど,後二桁ぐらいは速くならないと,Web スケールのテキスト処理には使えない(何でもクラウドを使えばいいと言うのはどうかと思う).前段の処理(品詞タグ付け)より処理速度が三桁も遅ければ,どう見ても明らかなボトルネックでしょう.逆に基礎的な解析アルゴリズムの高速化を研究する人は,前段の処理の2倍ぐらいまで

    浅い文解析器と深い文解析器 - ny23の日記
  • やっと出たのか - ny23の日記

    1月に試した liblinear-poly2 の論文 Training and Testing Low-degree Polynomial Data Mappings via Linear SVM が JMLR でも公開されてた.少し内容が変わってる?気のせいか. liblinear-poly2 は組み合わせ素性の重みが配列で実装されている関係で,素性数が多いデータで実験するとえらいことになる.論文ではハッシュを使う方法を提案してるけど,良いハッシュ関数を使うほど完全なランダムアクセスになるので,「ちゃんと実装した」動的ダブル配列を使った方が良い(頻度降順で素性番号をバイトコーディングしてループで組み合わせ素性を列挙すると,ほとんどキャッシュに載った配列アクセスと同じになるため).また全展開してしまうと,ハッシュを使っても,3次(以上)で動かすのは大変.この問題を解決した論文(今年の某全国

    やっと出たのか - ny23の日記
  • トライ(ダブル配列,簡潔データ構造)と 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] =================

    トライ(ダブル配列,簡潔データ構造)と STL コンテナ - ny23の日記
  • 突然来た - ny23の日記

    論文の締め切りまで2週間を切って,学習器をさらに高速化する画期的なアイデアを思いついた.実装は10-20行ぐらいで済みそうな予感.どうしようかと思いつつ,現在の内容を書いた 2p 日語の原稿を30分で英訳.英訳後のページ数は 3.5p しかない.あと 4.5p 書くか short paper として葬り去るか悩むところ.時間も無いし,困った. 共著の論文をチェックしてる場合じゃないかも. [追記 2/8] 適当に実装してみたら,ちゃんと速くなった.無駄がだいぶあるので,今日頑張ってチューニングしよう.論文はグダグダ足して,5p弱だけど,実験+1p, 新しいアイデア+1p で7pぐらいの内容にはなってきた. [追記 2/9] 昨日は最優先の用事があって結局何もしなかったが,今日少しチューニングして,前のアイデアより効果がありそうな雰囲気になってきた.もっと劇的に効くと思っていたのだけれど.

    突然来た - ny23の日記
  • liblinear-poly2 - ny23の日記

    liblinear の低次多項式カーネル版拡張という明日原稿を出す論文と関連する研究の実装があったので試してみた.論文を読む時間が無いので,手持ちのデータで試そうとしたが segmentation fault.もしやと思って中を見たら,二次の全組み合わせ素性の重み (= n*(n-1)/2) を保存する配列を作っていた (素性の種類数が少ないときしか対応出来ない実装) ので,コンパイルオプションに -m64 をつけて,素性番号を密にして,さらに配列の添字周りを int -> int64_t にすると動いた. | Train | Mem | Acc. | Test --------------------------------------------------- liblinear-poly2 | 347.3s | 16GB | 93.0% | 289.2s pa poly2 | 27.

    liblinear-poly2 - ny23の日記
  • AROW は CW より幾分マシか - ny23の日記

    今話題?の AROW (Adaptive Regularization Of Weight Vectors) の oll 向けの実装を見かけたので,Confidence-Weighted (CW) が Passive-Aggressive (PA)/LIBLINEAR に比べて全然ダメ (PA/LIBLINEAR: 91%, CW: 88%; Perceptron: 89%) だった例のタスク(学習/テストデータは公開中のコードに同梱してある)で,試してみた.パラメタを調整したが (c=100, 50, 10, 5, 1, 0.5, 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, I=1, 5, 10, 20, 50, 100),PA/LIBLINEAR -0.5% 程度の精度 (90.4%) しか出なかった.繰り返し回数を10回以下とかで固定すれば,AROW

    AROW は CW より幾分マシか - ny23の日記
  • Kernelized Passive Aggressive の微々たる高速化 - ny23の日記

    インフルエンザの間に考えていたアイデアを実装したところ,多項式カーネルの学習・二値分類が約10-20%高速化された.うわショボ。せめて2倍ぐらいになってくれればいいのに.ダメ論文に封印だなこりゃ.で,とっととオープンソースで公開しよう. [12/19; 追記] アイデアを splitSVM でも有効にするために,実装を変えたら splitSVM 自体が 10-40% ほど高速になってしまった.低頻度の素性をインクリメンタルに一つずつ処理するようにして,内積を取るのをやめただけ.高頻度の素性の部分の内積を何度も計算するため遅くなりそうだが,それ以上に低頻度の素性の部分の内積を unordered_map で保存するコストが大きかったらしい(インクリメンタルに低頻度の素性を処理する場合は,PKI の転置インデクスをそのまま使いまわせる).というわけで,展開する素性を極端に小さくしたときの速度劣

    Kernelized Passive Aggressive の微々たる高速化 - ny23の日記
  • C++ スタイル - ny23の日記

    プログラムを公開するので,c++ のスタイルについても少し考えてみる.C++ Coding Standard は英語で長く読む気が起きないので,Google C++ Style の日語訳を眺める.気になったのは以下 (注: 括弧内は自分のコメント). 前方宣言で十分なときには、#include を使ってはいけない. インクルードの順序は Cライブラリ、C++ライブラリ、その他のライブラリの.h、プロジェクトの.h (c, c++ はごっちゃになってる直さねば) struct はデータを運ぶ受動的なオブジェクトのみ,その他は class (大体そういう感じにしてる). 簡潔な関数を書く (40行程度が望ましいそうだ.Emacs のデフォルトで1画面に収まる程度を目安にしている.読み易さより,全体の行数の短さを重視するので,二度以上呼ばれる手続きだけ関数にしてる.しかし200行とかある関数は

    C++ スタイル - ny23の日記
  • LIBLINEAR と oll - ny23の日記

    最近よく使われているのを見かける LIBLINEAR と oll (PA-I) を比べてみた.いつものタスク,学習サンプル数: 296,776,平均発火素性数: 27.6, 学習データサイズ: 62,412,806 bytes, 二値素性のみ.テストサンプル数: 60,766, 平均発火素性数: 27.6, テストデータサイズ: 12,789,886 bytes. LIBLINEAR は全てのパラメタ推定法 (s=0-6),oll は繰り返し回数 (I) 20回と50回で試してみた.LIBLINEAR / oll とも c = 1.0, 0.5, ..., 0.005, 0.001 辺りを試して,一番分類精度の高かった c を利用.その他のパラメタはデフォルト (データは事前にランダムシャッフルし,テストでは LIBLINEAR に合わせて label か margin をファイルに出力す

    LIBLINEAR と oll - ny23の日記
  • レコード付き動的ダブル配列 - ny23の日記

    ブロック管理の詳細を、ダブル配列の世界的権威の某氏に昨日伺ったので実装し直し。400行近くなってしまった。デバッグ中。体調微妙なので深刻なバグを作り込んでないか心配。 [追記] ブロックの連結リストが壊れるバグを修正してデバッグ完了。ランダム順追加でも50秒程度(辞書順だと20秒)とかなり高速にバイナリのダブル配列を構築できるようになった。動的ダブル配列の実装もこれで一段落か。370行。後二三日最適化したら、予定していた用途に使ってみよう・・・ [追記] 遷移節点集合や,ブロック内未使用要素リストをソートしないようにして高速化。343行。float の値を格納できるようにして,予定した用途に使ってみたら、ハッシュベースのトライを使う場合に比べて,実行速度は約2倍となった。これだけ速ければまあ満足だ。苦労したかいがあったというところ。ダブル配列万歳。 [追記] ところで,値をダブル配列に保存

    レコード付き動的ダブル配列 - ny23の日記
  • Passive Aggressive と多項式カーネル - ny23の日記

    Passive Aggressive で陽に多項式カーネルを展開した場合 (explicit) の速度劣化について調べてみた。訓練データ約30万例、平均発火素性数27ほどのタスクで20回ほど学習のループを回すと、 d | C | PKI | explicit | speed-up | |SV| (PKI) ---------------------------------------------------------------- 0 | 0.005 | NA | 1.09s | | 1 | 0.005 | 11684.02s | 7.75s | x 1444.8 | 107354 (107390) 2 | 0.0001 | 10067.15s | 91.35s | x 110.2 | 94490 (94480) 3 | 0.000005 | 9106.61s | 1247.02s |

    Passive Aggressive と多項式カーネル - ny23の日記
  • Passive Aggressive - ny23の日記

    去年実装したものがあったので、多項式カーネルの学習を高速化してみた。__gnu_cxx::hash_map の char* のハッシュ関数はかなりダメな感じだったので、最初 ELF hash にして、さらに FNV hash に置き換えて最終的に約5倍、発火する素性番号がバラけていたのを密にするようにして約2-3倍と約10倍学習が速くなった。手持ちのタスクで実験したら、普通に多項式カーネル (PKI) で学習するより20倍ほど高速だったので取りあえず満足。速さが売りのオンライン学習もカーネル化すると学習がサポートベクタ倍(重複を合併するようにしても最大学習データサイズ倍)遅くなってしまう(下手すると数万倍)がこれで少しは使い易くなったか。しかも、SVM/ME より高い精度が出るようになってしまった(線形カーネルではもともと SVM/ME よりかなり良かったが多項式カーネルでも精度が出るよう

    Passive Aggressive - ny23の日記
  • 二値素性でのオンライン学習の実験まとめ - ny23の日記

    複数のオンライン学習のライブラリについて,線形学習と多項式カーネルの学習の詳細な実験結果(構文解析タスクと関係抽出タスク)を学習器の公開ページに追加した.今までの実験のまとめ的な内容になっている.オンライン学習は,訓練例を shuffling をするように統一して実験したら,ライブラリ間の速度差が少し縮まった.分類時間にはモデルの読み込み時間も入っているが,多項式カーネルではモデルの読み込みに時間がかかる分(と言っても100msec.とかだけど),特にテスト例数が少ない関係抽出タスクの実験セットで(線形学習に比べて)やや不利となっている. 幾つか分かったこと PA-I は averaging すると,繰り返し数を固定した場合の C の最適値が変わって,より少ないサポートベクタ数で同程度以上の分類精度が出せる.SVM よりサポートベクタ数が多くなりがちな PA-I にとっては良い特性だと思わ

    二値素性でのオンライン学習の実験まとめ - ny23の日記
  • LaTeX for writing papers in English

    Windows環境においてLaTeXで(英語の)論文を書く際の備忘録です。論文を書くという目的に集中してトピックを集めたページはあまり無かったのでまとめてみることにしました。環境整備・締め切り間際で役立つのテクニックなど。 Contents(予定) 最新の LaTeX 環境を揃える 論文に EPS の絵を貼る PDF 形式の論文を作る 論文に PS フォントを使う 論文のワード数を数える 論文のスペルチェックをする 論文を書く際に必要になる LaTeX Tips 締め切り間際に論文をページ数内に詰め込むトリック LaTeXで論文を書く際に揃えておくと良いツール 計算言語学で使うLaTeXスタイルファイル (おまけ)論文の投稿の際のメールのテンプレート (おまけ)論文の英語表現をチェックする LaTeX オンライン HOWTO Windows で最新の LaTeX 環境を揃える まずは La