はてなブックマーク

とりあえず以下のコードをollのoll.cppに突っ込むことによってAROWを使うようにできる。(あとoll.hppやoll_train.cppの学習手法が並んでいるところにAROW用の値を付け加える) バイアスの部分とかはちゃんとなってるかあまり自信ないです。 CW(Confidence-weighted)のコードと非常によく似たコードになっている。 // // Adaptive Regularization Of Weight Vector // void oll::updateAROW(const fv_t& fv, const int y, const float alpha) { for (size_t i = 0; i < fv.size(); i++){ if (cov.size() <= fv[i].first) { w.resize(fv[i].first+1); con

前回の記事でAROWを実装して、パラメータの影響に関して簡単な実験をしてみた。 まず、パラメータr=0.1,10.0,50.0とした場合の誤り率の収束は下図のようになった。(データは前回と同様にnews20.binaryを用いた) これを見るとr=0.1のときはすぐに収束しているのに対して、r=50のときはなかなか収束しないということが分かる。 一方で元データのラベルを10%反転させたものを訓練データとして用いた場合は以下のような図が得られる。このときr=0.1と10は明らかに過学習となっているのに対し、r=50のときは反復ごとに誤り率が減少していることが分かる。 そもそもパラメータrは式(1)で表される、以前の確率分布からのずれと正しく分類できるかどうかのトレードオフパラメータであった。これが小さい場合は確率分布から大きくずれてもいいから分類を正しくすることを要求し、大きい場合は大きなず

昨日のPFIセミナーで紹介されていたAROW (Adaptive Regularization Of Weight Vector)を実装してみた。 AROWはCrammerらによりNIPS 2009で提案された手法で、彼らが以前提案したConfidence weightedよりもノイズに強く、またCWとほぼ同等の性能を持っている。 今回実装したのは共分散行列を対角に近似した場合の式に基づいている。これは共分散行列をフルに持とうとすると素性の数の2乗程度のメモリが必要で、コストが大きすぎるためである。 追記 Featureクラスの定義を書くのを忘れてたので追加 public class Feature { int index; double weight; Feature(int i , double w){ index = i; weight = w; } } import java.ut

On Smoothing and Inference for Topic Models (UAI 2009) pdfで述べられているLDAの推論方法であるCVB0を実装してみた。 これはTehらのCVBで述べられている期待値の2次の項までの近似の部分をさらに近似して0次の項だけで近似したものとなっている。二次近似に比べexpの計算がいらない分、高速に実行することができる。 手元で実験したところ前回の記事で実装したCGS(Collapsed Gibbs samplerより2倍程度高速であった。 Token.java 前回のものに文章重みの項が付け加わっている public class Token { public int docId; public int wordId; public double weight; public Token(int d , int w ){ docId =

昔書いたことがあったけど、どこかにいってしまったのでもう一度書いてみた。推論方法にはギブスサンプリングと変分ベイズの2つがあるけど、導出も実装もより楽なcollapsed gibbs sampling(Griffiths and Steyvers, PNAS, 2004)の方を採用。 Token.java package lda; public class Token { public int docId; public int wordId; public Token(int d , int w){ docId = d; wordId = w; } } LDA.java package lda; import java.util.*; public class LDA { int D; // number of document int K; // number of topic int

ネットワークプログラム周りで、aio_read(3)*1を使う必要が出てきたので、軽く調べてみた。 今回やりたかったのは非同期にIOを発行したあとに別処理を行って、その後取得された結果を使うというものだったのでJavaのFurtureっぽいインターフェイスの実装を行ってみた。 Descriptorクラスのread_async(buf , count)を呼ぶとFurtureDescriptor * が返ってくるので、それに対して別処理を行うなどしたあとget()を呼ぶとread(2)の結果に相当する値が返ってくる。 実装は以下 #include <iostream> #include <cstdlib> #include <unistd.h> #include <aio.h> #include <errno.h> using namespace std; class FurtureDescr

MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。 情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこれを実現するためのコードはもっとも単純に行うと以下のようになる //長さlenの配列arrayの中でトップr個の値をresultに挿入する void sort_method(int * array , int len, int r , vector<int> & result){ sort(array , array + len); copy(array + len - r , array + len , back_inserter(result)); } しかし、Nが大きいとき、MGの例だとN=100万のときにsortの処理にはおおよそ100

毎月恒例のPRML読書会で発表してきました。 今回の発表は6.4.5,6.4.6でガウス過程による分類を行う際の定式化とそこで出てくる積分をラプラス近似で近似を行う方法についてでした。 ラプラス近似で計算を行う部分についてはこの読書会で出てくるのが3度目ということもあって、割と素直に式の意味を追うことができた。 発表資料は下に載せておきます。 PRML 6.4-6.5View more documents from tsubosaka. あと、今回の読書会で読んだ部分では逆行列が出てきたが、今回出てきた範囲においては実際の逆行列を計算する必要はなく逆行列とベクトルの積を計算するだけでよい。すなわち行列A,ベクトルvに対しての計算ができればよい。 こういう場合の常とう手段として線型方程式 をxに関して解くことによっての値を求める。 ちなみにこの計算はmatlabではA\vでRではsolve(

今日のInterpolative codingの話が面白かったのと復号の部分のコードが必ずしも自明ではないかと思ったのでメモ。 Interpolative codingは長さと出てくる値の最小値、最大値が分かっている狭義単調増加な自然数のリストを圧縮する方法である。 ここで最大値とはリストの最大値ではなく、たとえば転置リストであれば最大の文書IDなど圧縮を行う際に出てきうる値の最大値である。 Interpolative codingの基本的な考え方としてはたとえば1から20までの数が表れるとわかっておりかつリストの長さが20であるということが分かっていれば、なにもデータがなくてもリストが[1..20]であるとわかるということに基づいている。 ここでは例で説明する。長さ7のリスト<7;3,8,9,11,12,13,17>を圧縮することを考える。またここで出てくる数の最大値は20であることが分

3回目から参加しているhttp://sites.google.com/site/ikomadokushokai/prml/prml06|title=PRML読書会で5.3誤差逆伝播と5.4ヘッセ行列に関して発表してきました。 発表資料を公開しておきます。 PRML 5.3-5.4View more documents from tsubosaka.

前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては 上位bit 符号の個数 符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。 例えば ( 3 , 5 , 0 , 0 ,

圧縮のプログラムを書くときにはbit単位でエンコーディングをする必要があるため、bit単位でエンコードをするBitEncoderというものを書いてみた。 動作としては1byte変数にbitをバッファリングしていっぱいになったらファイルに書き出すという感じです。 #include <cstdio> #include <iostream> struct BitEncoder{ FILE *fp; unsigned char bval , bindex; bool buffered; BitEncoder(const char * fileName){ fp = fopen(fileName , "wb"); buffered = false; bindex = 7; bval = 0; } ~BitEncoder(){ if(buffered){ flush(); } fclose(fp);

二つの箱があって、一方にはもう片方の箱の倍の金額が入っている。 あなたは一つの箱を開けて中に入っている金額を確認した後にどちらの箱を選ぶのかを決めることができる。 あなたが一つの箱を開けた時に1万円入っていたとした時に果たして箱を変更した方が良いか否か？ 額が少ない方を選んだとすると、多い方(もう片方の箱)には2万円入っていて、逆の場合は5000円入っているので2つの状態が半々だとすると箱を移動したときの期待値は 20000 * 0.5 + 5000 * 0.5 = 12500(円) でもう片方の箱を選んだほうが得になりそう。しかしはじめに1万円の箱を開かずに、もう片方の箱を選んでいて2万円を観測したときには箱移動時の期待値は 40000 * 0.5 + 20000 * 0.5 = 30000(円) でやはり箱を移動した方が期待値的にはいい。 以上の議論から最初に選んだ箱がどちらであっても

http://mallet.cs.umass.edu/より class Digamma { public static final double EULER_MASCHERONI = -0.5772156649015328606065121; public static final double DIGAMMA_COEF_1 = 1.0 / 12; public static final double DIGAMMA_COEF_2 = 1.0 / 120; public static final double DIGAMMA_COEF_3 = 1.0 / 252; public static final double DIGAMMA_COEF_4 = 1.0 / 240; public static final double DIGAMMA_COEF_5 = 1.0 / 132; publ

Google Code Jamのベータテストに参加してみました。 今回のルールは大体次のようなものでした。(昨日書いたことの整理もかねて) 制限時間は2時間 各問題にはスコアがあって、順位はスコアの合計で決定される、同着の場合は回答時間の合計の短い方が勝つ。 間違いの提出一つに対して4分のペナルティがつく。 回答の提出はダウンロードした入力に対して、ローカルでプログラムを走らせて得た出力を提出する。 この辺はICPCの国内予選とほぼ同じで違う点は プログラミング言語は何を使ってもかまわない、複数使ってもよい(その場合は使ったプログラムをzipで固めて送る)、さらにExcelやシェルで結果を出してもよい。 入力にはsmall Inputとlarge Inputの二種類がある。small Inputに対する回答は何度でも(正解がでるまで)提出してよい、large Inputに対する回答はコンテ

情報検索において検索手法の結果を評価する方法の手法の一つにInterleavingという方法がある。最近その辺についてちょっと読んでいたのでまとめておく。 検索エンジンにおいては何らかのRanking Function(http://en.wikipedia.org/wiki/Ranking_function)を用いて、与えられたクエリに対する検索結果を並び替える。 例えば"餃子 レシピ"というクエリでGoogleで今検索したところ 1. http://cookpad.com/recipe/316319 (☆ほっぺが落ちちゃう　餃子☆) 2. http://cookpad.com/category/836 (餃子・シュウマイ レシピ 306品) 3. http://matome.naver.jp/odai/2133424266153597701 (絶品餃子！！肉汁がやばい究極のギョーザのレ