オンライン凸最適化と線形識別モデル学習の最前線 - Preferred Networks Research & Development
内容は線形識別モデルの学習について（Perceptron, PA, CW, AROW, NHELDとNLP2010のtutorial + 最新のアップデート. 更新式が整理されています）、オンライン凸最適化のregret解析、sublinearなSVMの学習の話です。最近公開したjubatusの中の学習アルゴリズムの解説でもあります。 コスト関数が凸である場合のOnline Gradient Descentのregret解析の証明は美しかったので、普通はこういうのはプレゼンではやらないとおもうのですが紹介しました。 Sublinearの学習の話は今後いろいろ発展しそうです。各学習例に動的に重みをつけて優先的に学習する方法は直感的にはできそうだと昔考えてたのですが、こういう形できれいに定式化できるのだと感心しました。 IBISはそこそこ参加していますが、毎年新しい分野の問題が登場してきて面白
多クラス 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
オンライン学習による線形識別器 - kisa12012の日記
オンライン学習による線形識別器(Online Linear Classifiers ~PerceptronからCWまで~)というタイトルで研究室内の勉強会発表を行いました． 勉強会で使用したスライドを以下に公開します． (スライドが表示されない場合は，一度リロードを行うと表示されるようになる場合があります．） スライド OnlineClassifiers View more presentations from Hidekazu Oiwa. 内容概説 本スライドの構成は以下の通りです． 線形識別器とオンライン学習の定義，特性の説明 Perceptron MIRA / Passive-Aggressive Confidence-Weighted Algorithms 各アルゴリズムについて，アルゴリズム概要・理論保証・その後の発展に焦点を当てて解説しています． 内容のちょっとした補足 上のス
キャッシュありオンライン学習の実装を公開 - ny23の日記
多項式カーネルで別データから再学習する際のバグを直すついでに更新しておいた．オンディスク版の random_shuffleも同梱．実験結果は徐々に更新．オンメモリ版とオンディスク版の速度差は，訓練データのシャッフル時間程度の差になった（ディスクキャッシュが効いてしまっているからだと思うけど）． [追記]バッチ学習を除いて実験結果を更新した．懸案のliblinear-poly2-1.7 は，liblinear-poly2-1.6 を変更したときのソースを元に diff でパッチを作ったらそのまま適用できたので楽だった．あと，make 時に出た型不一致の warning を6箇所ほど直してコンパイルしたら無事動いた． しかし，メモリと実行時間を同時に測れるのはやっぱりすごく便利だ． [追記]バッチ学習も実験結果を更新した．
オンライン学習でキャッシュを実装してみた - 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
Exploiting Feature Covariance in High-Dimensional Online Learning - ny23の日記
二値素性でのオンライン学習の実験まとめ - ny23の日記 で CW は素性数が多いと共分散行列のサイズが問題になるという話をしたが，その改良をしたよ（共分散行列を rank の低い行列で近似）という論文．Online Passive-Aggressive Algorithms on a Budget - ny23の日記 と同じ，AISTATS という学会に出たようだ．数カ月前にダウンロードしていたのだけど，放置していた．話としてはあるだろうなとは思っていたが，近似パラメタが一つ増えるのはちょっとやな感じ．そもそもオンライン学習の時点で近似なのだけど，さらに近似を重ねるパラメータが増えるのは感覚的に気持ち悪い．
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 を再コンパイルしたら動い
突然来た - ny23の日記
論文の締め切りまで2週間を切って，学習器をさらに高速化する画期的なアイデアを思いついた．実装は10-20行ぐらいで済みそうな予感．どうしようかと思いつつ，現在の内容を書いた 2p 日本語の原稿を30分で英訳．英訳後のページ数は 3.5p しかない．あと 4.5p 書くか short paper として葬り去るか悩むところ．時間も無いし，困った． 共著の論文をチェックしてる場合じゃないかも． [追記 2/8] 適当に実装してみたら，ちゃんと速くなった．無駄がだいぶあるので，今日頑張ってチューニングしよう．論文はグダグダ足して，5p弱だけど，実験+1p, 新しいアイデア+1p で7pぐらいの内容にはなってきた． [追記 2/9] 昨日は最優先の用事があって結局何もしなかったが，今日少しチューニングして，前のアイデアより効果がありそうな雰囲気になってきた．もっと劇的に効くと思っていたのだけれど．
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
Kernelized Passive Aggressive の微々たる高速化 - ny23の日記
インフルエンザの間に考えていたアイデアを実装したところ，多項式カーネルの学習・二値分類が約10-20%高速化された．うわショボ。せめて2倍ぐらいになってくれればいいのに．ダメ論文に封印だなこりゃ．で，とっととオープンソースで公開しよう． [12/19; 追記] アイデアを splitSVM でも有効にするために，実装を変えたら splitSVM 自体が 10-40% ほど高速になってしまった．低頻度の素性をインクリメンタルに一つずつ処理するようにして，内積を取るのをやめただけ．高頻度の素性の部分の内積を何度も計算するため遅くなりそうだが，それ以上に低頻度の素性の部分の内積を unordered_map で保存するコストが大きかったらしい（インクリメンタルに低頻度の素性を処理する場合は，PKI の転置インデクスをそのまま使いまわせる）．というわけで，展開する素性を極端に小さくしたときの速度劣
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 をファイルに出力す
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の日記
去年実装したものがあったので、多項式カーネルの学習を高速化してみた。__gnu_cxx::hash_map の char* のハッシュ関数はかなりダメな感じだったので、最初 ELF hash にして、さらに FNV hash に置き換えて最終的に約5倍、発火する素性番号がバラけていたのを密にするようにして約2-3倍と約10倍学習が速くなった。手持ちのタスクで実験したら、普通に多項式カーネル (PKI) で学習するより20倍ほど高速だったので取りあえず満足。速さが売りのオンライン学習もカーネル化すると学習がサポートベクタ倍（重複を合併するようにしても最大学習データサイズ倍）遅くなってしまう（下手すると数万倍）がこれで少しは使い易くなったか。しかも、SVM/ME より高い精度が出るようになってしまった（線形カーネルではもともと SVM/ME よりかなり良かったが多項式カーネルでも精度が出るよう
二値素性でのオンライン学習の実験まとめ - ny23の日記
複数のオンライン学習のライブラリについて，線形学習と多項式カーネルの学習の詳細な実験結果（構文解析タスクと関係抽出タスク）を学習器の公開ページに追加した．今までの実験のまとめ的な内容になっている．オンライン学習は，訓練例を shuffling をするように統一して実験したら，ライブラリ間の速度差が少し縮まった．分類時間にはモデルの読み込み時間も入っているが，多項式カーネルではモデルの読み込みに時間がかかる分（と言っても100msec.とかだけど），特にテスト例数が少ない関係抽出タスクの実験セットで（線形学習に比べて）やや不利となっている． 幾つか分かったこと PA-I は averaging すると，繰り返し数を固定した場合の C の最適値が変わって，より少ないサポートベクタ数で同程度以上の分類精度が出せる．SVM よりサポートベクタ数が多くなりがちな PA-I にとっては良い特性だと思わ
人工知能基本問題研究会(SIG-FPAI)での岡野原さんの発表のときに取ったメモ - yasuhisa's blog
hillbig.cocolog-nifty.com ということで僕が取ったメモも出してみようと思う。内容としては大体3つで オンライン学習 L1正則化 索引を用いた効率化, 全ての部分文字列を利用した文書分類 という感じだったんだけど、最後の索引の付近はid:syou6162の勉強不足によりよく分からなかった。が、最初の二つはなんとか付いていけたので、出してみます。主に自分用のメモですが。 オンライン学習自然言語処理のデータは3つの特徴がある。 高次元 疎 冗長 で、あとはデータがばかでかいので、いわゆるバッチ処理だとメモリに乗り切らなかったりとかということがある。それでオンライン学習というのが今よく使われているようだ。オンライン学習の方法には下のような方法がある。簡単なものから難しいものへ。 perceptron 自然言語処理と相性がよい 色んなもののベースになる 線形分離できるときには
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
