実家に帰省中，電車の中で読んでた論文の紹介。 概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。 しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出…

東京駅で新幹線を待っている間暇なので、今年の出来事に関して振り返ってみる。 イベント 卒業 2009年3月をもって、修士課程を卒業する。修士論文のテーマは"ネットワークのコミュニティ構造を抽出するベイズ推論アルゴリズムの研究"であった。 正直、内容に…

とりあえず以下のコードをollのoll.cppに突っ込むことによってAROWを使うようにできる。(あとoll.hppやoll_train.cppの学習手法が並んでいるところにAROW用の値を付け加える)バイアスの部分とかはちゃんとなってるかあまり自信ないです。CW(Confidence-weigh…

前回の記事でAROWを実装して、パラメータの影響に関して簡単な実験をしてみた。まず、パラメータr=0.1,10.0,50.0とした場合の誤り率の収束は下図のようになった。(データは前回と同様にnews20.binaryを用いた)これを見るとr=0.1のときはすぐに収束しているの…

昨日のPFIセミナーで紹介されていたAROW (Adaptive Regularization Of Weight Vector)を実装してみた。AROWはCrammerらによりNIPS 2009で提案された手法で、彼らが以前提案したConfidence weightedよりもノイズに強く、またCWとほぼ同等の性能を持っている。…

On Smoothing and Inference for Topic Models (UAI 2009) pdfで述べられているLDAの推論方法であるCVB0を実装してみた。 これはTehらのCVBで述べられている期待値の2次の項までの近似の部分をさらに近似して0次の項だけで近似したものとなっている。二次近…

最近読んだトピックモデル関係の論文のざっとしたメモ。内容については間違って理解しているところも多々あると思います。(追記 12/24) 最後のほうに論文を読む基礎となる文献を追加しました。 Efficient Methods for Topic Model Inference on Streaming Do…

昔書いたことがあったけど、どこかにいってしまったのでもう一度書いてみた。推論方法にはギブスサンプリングと変分ベイズの2つがあるけど、導出も実装もより楽なcollapsed gibbs sampling(Griffiths and Steyvers, PNAS, 2004)の方を採用。Token.java packa…

NIPS 2009で発表された論文"Polynomial Semantic Indexing" [1]を読んだ。これは低ランク近似を用いた教師ありの情報検索に関する手法である。 情報検索について 与えられたクエリに関して適当な重みづけをおこなって順位づけして、適切な文章を返却するとい…

NIPS 2009のonline papersがすでにダウンロードできるように*1なってたのでタイトルを眺めていたらGPUでLDAを並列化するという論文があって読んだので少し紹介してみる。まず、彼らの論文[1]ではLDAの推論アルゴリズムのうち、Collapsed Gibbs sampling(CGS)…

ネットワークプログラム周りで、aio_read(3)*1を使う必要が出てきたので、軽く調べてみた。 今回やりたかったのは非同期にIOを発行したあとに別処理を行って、その後取得された結果を使うというものだったのでJavaのFurtureっぽいインターフェイスの実装を行…

MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこ…

ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m =…

毎月恒例のPRML読書会で発表してきました。 今回の発表は6.4.5,6.4.6でガウス過程による分類を行う際の定式化とそこで出てくる積分をラプラス近似で近似を行う方法についてでした。 ラプラス近似で計算を行う部分についてはこの読書会で出てくるのが3度目と…

マルチスレッドでのechoサーバのメモserver.cc #include <iostream> #include <sstream> #include <pthread.h> #include "ServerSocket.h" #include "Queue.h" using namespace std; string readLine(int sock){ char c; stringstream buffer; while(1){ int ret = read(sock, &c , 1); if(</pthread.h></sstream></iostream>…

最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介し…

今日のInterpolative codingの話が面白かったのと復号の部分のコードが必ずしも自明ではないかと思ったのでメモ。Interpolative codingは長さと出てくる値の最小値、最大値が分かっている狭義単調増加な自然数のリストを圧縮する方法である。 ここで最大値と…

オープンソースのSVMソフトウェアの基本デフォルトの設定で比較などをしてみた。利用データはLIBSVM Data: Classification, Regression, and Multi-labelのa9aとnews20.binaryを利用した。 データセットの詳細は以下のようになっている データセット名 訓練…

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…

圧縮のプログラムを書くときにはbit単位でエンコーディングをする必要があるため、bit単位でエンコードをするBitEncoderというものを書いてみた。 動作としては1byte変数にbitをバッファリングしていっぱいになったらファイルに書き出すという感じです。 #in…

Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,60…

Grand Prizeが達成されたNetflix Prizeですが、データの公開が停止されたりすると困るので登録してデータを確保した。Netflixのデータフォーマットは展開先のフォルダの下にtraining_setというフォルダができ、その中にmv_0000001.txt ...という形式で17770…

二つの箱があって、一方にはもう片方の箱の倍の金額が入っている。 あなたは一つの箱を開けて中に入っている金額を確認した後にどちらの箱を選ぶのかを決めることができる。 あなたが一つの箱を開けた時に1万円入っていたとした時に果たして箱を変更した方が…

前回に引き続き会津大のWarm Up Contestに参加結果は前と同じ3問。ただJavaが使えたのでスコアは前よりはよかった。 A : Sleeping Cats 猫がいっぱい出てくる問題ってどっかで見た設定だなと思いながら読んでた。 やるだけ。 7/0 B: Monster Factory 最初に…

PRML読書会の予習を兼ねて3.1のガウス基底関数を用いて線形回帰を行うプログラムをRで書いた。疑問としては(3.4)式の の部分で\mu_jとsはどうやって決定するのかがよくわからなかった。とりあえずs=1,\mu_j = j / Mとした。追記：本当はbase(x[i],j)ではなく…

去年は出題側でしたが、今年は解く側で参加。結果は6問で(24)位(1問去年の問題案から使い回しがあるので順位は参考ということで) A やるだけ。Accept B 典型的なDP。ただ点ではなくエッジが通れないので２問目にしてはややめんどう。Accept C 一人の方の手を…

測定結果 http://kakaku.com/bb/speed.asp 測定日時 ：2009/06/06 14:50:45 回線種類 ：光(マンション) 回線名称 ：NTT フレッツ光/Bフレッツ プロバイダ：So-net（ソネット） 下り速度 ：79.5M(79,517,816bps) 上り速度 ：30.4M(30,443,061bps)

今住んでいるところでNTTの光回線が利用可能になって、申込みも済ませて来週には工事なんだけど情報の共有がなされていないのか今日だけで3社も勧誘に来た。 マンションタイプで申し込んでるんだから、代理店を1社にしぼるとか情報の共有を行うとかやっとい…

1Q84 BOOK 1作者: 村上春樹出版社/メーカー: 新潮社発売日: 2009/05/29メディア: 単行本購入: 45人 クリック: 1,408回この商品を含むブログ (1247件) を見る1Q84 BOOK 2作者: 村上春樹出版社/メーカー: 新潮社発売日: 2009/05/29メディア: 単行本購入: 40人 …