サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
掃除・片付け
tsubosaka.hatenadiary.org
情報検索において検索手法の結果を評価する方法の手法の一つに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 (絶品餃子!!肉汁がやばい究極のギョーザのレ
タイトルの論文はCommunication of the ACM, 2012のレビュー記事 ドラフトバージョンは下のリンクから読める。 http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf 割と面白かったのでいくつか内容を紹介 概要 機械学習システムはデータから自動でタスク(スパムフィルタ、レコメンドなど)をどうやって実行するかを見出すことができます。 しかしながら機械学習システムを成功させるには教科書を読んだだけではなかなか見つけづらいお約束事とかがあって、思うようには行かないことが多い。 本文献では機械学習の研究者および実務に携わる人間が知っておくべきである事柄を12個に要約しています。 一般化が重要 機械学習のゴールは訓練データにはないデータに対しても一般化して推定ができるという点になります。単に訓練データのみ分類できればよ
転置インデックスから上位k件の文章を取ってくる手法について、知ってる範囲でまとめてみました。 転置インデックスとTop k-query View more presentations from tsubosaka この辺の話は教科書だと Information Retrieval: Implementing and Evaluating Search Engines (MIT Press) 作者: Stefan Buettcher,Charles L. A. Clarke,Gordon V. Cormack出版社/メーカー: The MIT Press発売日: 2010/07/23メディア: ハードカバー購入: 2人 クリック: 78回この商品を含むブログ (8件) を見る のChapter 5とかに疑似コードなども含め載っているので、参考になるかと思います。
以前書いたけどいつもjavaのXMLライブラリの使い方とか忘れるので備忘録用に上げておく import java.io.File; import javax.xml.parsers.SAXParser; import javax.xml.parsers.SAXParserFactory; import org.apache.lucene.analysis.Analyzer; import org.apache.lucene.analysis.standard.StandardAnalyzer; import org.apache.lucene.index.IndexWriter; import org.apache.lucene.index.IndexWriterConfig; import org.apache.lucene.store.Directory; import org.apa
今日はmixiでLuceneソースコードリーディングに参加して、Scorerの部分を読んでました。 Scorerについて Scorerは与えられたクエリに対して文章をidの昇順で返すような抽象クラスです。 検索で使われるメインの部分は以下のようになっており、collectorに対してnextDoc()によって求まる適合した文章を渡すというのを繰り返しています。 protected boolean score(Collector collector, int max, int firstDocID) throws IOException { collector.setScorer(this); int doc = firstDocID; while (doc < max) { collector.collect(doc); doc = nextDoc(); } return doc != N
最近勉強会で発表する予定のものと仕事関係の論文しか読んでなかったのでこのブログにはあんまり書けなかったんだけど、久々に書いてみる。 紹介する論文はSIGIR 2011のLSIを語彙数が大きい時にも効率的に並列化できるようにしたという論文[1]。 論文概要 PLSIやLDAみたいなトピックモデルは情報検索においても性能向上で重要であるが、語彙数が多い時スケールしないという問題点がある(文章数に関しては効率的な実装が知られている。例えば[2])。このためよく行われるのが語彙数を1万とかに制限する方法ですが、情報検索への応用を考えるとこのアプローチは問題がある(文章分類やクラスタリングへの応用であればこれで問題ない)。 このため著者らはRLSIという方法を提案した。これにより160万文章、語彙数700万のデータセットに対して16台のマシンでトピック数500のとき1時間半で処理できた(おそらく1イ
id:nokunoさんの主催したICML2011読み会で発表してきました 自分はSparse Additive Generative Model for Textという論文について発表しました 発表資料: Icml2011 reading-sage View more presentations from tsubosaka 他の発表についていくつかメモ Infinite SVM: a Dirichlet Process Mixture of Large-margin Kernel Machines データをある程度セグメントに分けて、それぞれで識別モデルを構成したほうが性能が上がるよねという話という理解 これは実務的にもユーザモデルの作成のときに性別で分けて独立にモデルを作成したほうが性能が高いことがあったり、決定木的な方法が割とうまくいくことからも納得できる GoDec: Random
id:nokunoさんの主催する自然言語処理勉強会で、Infer.NETを使ってLDAを実装してみたというタイトルで発表してきました。 Infer.NETはMicrosoftが公開しているグラフィカルモデル上でベイズ推定を行うためのフレームワークです。このようなものを使うことにより、具体的な推論アルゴリズムの導出を人が行うことなく、生成モデルを記述するだけで事後分布の推論が可能になり、簡単に確率モデルを問題に合わせて定義するということが行えるようになるといいなと思って、今回紹介しました。 Infer.NETを使ってLDAを実装してみた View more presentations from tsubosaka 参考文献 Infer.NETを使う上で参考になるかと思われる書籍をあげておきます。 パターン認識と機械学習 上 - ベイズ理論による統計的予測 作者: C. M.ビショップ,元田浩
kinabaさんのブログの 「無限ビット列を作ったときに最初に "001" が並ぶインデックスの期待値は 8。では、"000" なら?」という問題に対して、マルチンゲールを使った解説をしてみます。 いま無限に生成されるビット列に対して次に何がでるかを賭けるギャンブルを考えます。配当はフェアな賭けで賭け金の2倍返しとします。ここで000が出現したら賭けは終了するとします。 このとき毎時刻ギャンブラーが1$持ってきてつぎのように賭けます。 1. はじめに0が出ることに賭けて、勝ったら次へ、そうでなければ終了 2. 再び0が出ることに前の儲け2$を全額賭ける、勝ったら次へ、そうでなければ終了 3. 再び0が出ることに前の儲け4$を全額賭ける、勝ったら000が出てるので賭け自体が終了、そうでなければ終了この話はたとえば010がでる期待値を考えるときは2.のところで0にではなく1に賭けることになりま
岡野原氏の作成したwavelet木を使った高速配列処理ライブラリwat-arrayを利用して、2次元探索のプログラムを書いてみた。 なお、自分はwavelet木のアルゴリズムについては全く分かってないですが、wat-arrayでは配列に対して、操作を行うインターフェイスがしっかり与えられているのでそれを見ながら作りました。 問題定義 2次元座標の集合P={(x,y)}が与えられる。Queryとして(xs,xe,ys,ye)が与えられたときにPの中でxs <= x < x, ys <= y < yeを満たす点の数を答えるというものを考える。 なお、Pの内容は途中で変化したりすることはないものとする(変更が加わった場合は一から作り直す)。 インターフェースとしては次のようになる、2次元座標の表現にはpairを用いることにする。 namespace wat2DSearch{ typedef st
id:nokunoさん主催のNIPS読む会で発表してきました。 僕が発表した論文はThe Multidimensional Wisdom of Crowdsというものです。この論文を選んだのはOral Sessionの論文の中でタイトルがちょっと面白そうだったのでという理由です。 機械学習では大量のラベル付けしたデータが必要になることが多いのですが、データ自体は例えば画像ならGoogle画像検索やflickrなどから大量に取ってくることができるのですが、それにラベル付けをするとなるとどうしても人手が必要であることが多く困ってしまうことがあります。 こういったときのためにAmazon Mechanical Turkという画像にラベルをつけるとか簡単なアノテーションを安く大量に行ってもらうサービスがあるのですが、このサービスを普通に使うとアノテータの質が良くなかったりしてラベルの質が良くないと
次回のCVIM勉強会でmean-shiftについて話すことになってしまったので、理解のためにmean-shiftアルゴリズムを実装してみた。 カーネルは一番簡単なフラットカーネルを利用し、また画像もグレイスケール画像のみを扱うためピクセルの値は[0,256]の一次元データとみなす。 またナイーブな実装だと512*512ぐらいの画像でもすごい時間がかかるので二分探索とFenwickTree(動的に更新する必要はないので別に使う必要なかった、累積和を保存した配列に変更)を使ってグレイスケール画像かつフラットカーネルであることを利用して高速化した関数meanShiftLoopFastを用意した。 元画像は下のようになっている。 bandWidth=10のときは下のようになり、肌の部分が同じ値に収束していることがわかる。 bandWidth=20のときは以下のようになり、やや平滑化されすぎているこ
id:nokunoさんが主宰する第2回自然言語処理勉強会@東京で"Latent Dirichlet Allocation入門"というタイトルで発表してきました。 内容としては機械学習ライブラリMalletに実装されているLDAのマルチスレッド実装クラスのParallelTopicModelで使われているトピックモデルの技術を紹介するという話でした。 Latent Dirichlet Allocation入門View more presentations from tsubosaka. 本当は文章検索への応用とかの話もしたかったのですが準備に時間が足りず断念
PRML 14.5.1の混合正規回帰モデルのEMアルゴリズムによるパラメータ推定を実装してみた。 混合正規回帰モデルは下図のようなデータ点に対して 一本の直線でフィッティングする代わりに 複数の直線でフィッティングするというモデルである。 これは混合正規分布の推定と同じくEMアルゴリズムで推定できる。詳しくはPRMLの14.5.1を参照。 package chapter14; import java.util.Random; public class Main { static double generate(double x){ if(Math.abs(x) >= 0.5){ return - 0.5 * x - 1; }else{ return 0.5 * x + 1; } } public static void main(String[] args) throws Exceptio
タイトルは釣りです。id:mamorukさんの書いたHadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記を読んで、そもそも1G程度のデータの単語頻度を数えるのに858分もかかるんだっけと思い、id:nokunoさんの資料を読んでみると単語頻度を求める際に a b a aみたいなデータを a 3 b 1に変形するのにsortしたファイルをuniq -cで処理するということをやっていた。これはあまり効率のよい方法ではなくて行数をNとしたときにO(N log N)の計算時間となる(文字列比較はO(1)でやれることにする)。 これに対して、単語の頻度をハッシュ表で保存すると理想的な条件の元ではO(N)の計算時間で頻度を求めることが出来、より高速に計算することが可能となることが期待される。 また、単語数をWとしたとき、C++のmapのような二分探索木を使ってもO(N
岡野原さんのtweetで紹介されていたPower Iteration Clusteringという文章分類の手法に関する論文[1,2]を読んでみた。 背景 n個のデータX={x_1,...,x_n}が与えられたときに各データ間の類似度s(x_i,x_j)を成分に持つ類似度行列Aを考える。 また次数行列としてAのi行目の値を合計したd_{ii} = \sum_j A_{ij}を対角成分にもつ対角行列をDとする。 このときW:=D^{-1} Aをnormalized affinity matrixと定義する。簡単のためWはフルランクであるとする。 この行列はすべての要素が1となる固有ベクトルをもち、この時固有値は1となる。実はこれが最大固有値である(行列Aの行和が1となること+Gershgorin circle theorem(en)より導かれる)。また、行列Wの固有値を1=λ_1>=...>=
PRML勉強会で11.4のスライスサンプリングについて発表してきました。 発表スライドは以下となります。 Prml11 4View more presentations from tsubosaka. また、参考として以前のPRMLハッカソンで作成したスライスサンプリングを用いたLDAのコードをgithubにアップロードしました。http://github.com/tsubosaka/LDASlice/tree/master/src/lda/
この文章について 最近言語モデル方面にも少し興味があるので自分の知識を整理する意味で書いてみた。NLPは専門ではないので、おかしなことを書いてある可能性がありますがその場合はご指摘ください。 本文章ではn-gramモデル、単語の出現確率がn-1個前の単語のみに依存するモデルを考える。 問題 who is * という文が与えられたときに*にくる文字の確率を求めることを考える。この場合だと*には例えばheが当てはまるかもしれないが, isが入ることはまずなさそうに思える。このことは文法的にも説明ができると思うが、文法のルールを作るのは大変だし、文法的に正しい単語の中でどれが出やすいかということはできない。 一方で機械学習を使った言語モデルの文脈では文法的知識を余り持たず、与えられたコーパスから自動的に出やすい単語/表現を学習する方針をとる。 最尤推定 一番簡単なモデルとしては最尤推定を使うもの
PRML Hackathonに行ってきました。 今回のHackathonでは昨日書いたスライスサンプリングという手法をLDAの推論に使ってみて通常のGibbs samplerと比較してみました。 結果としてはサンプリング速度が2-3倍程度高速になり、手法の有効性を確かめることができました。また、perplexityの値は Gibbs samplerよりも少し悪い結果となりました。(誤解を招く表現でした、詳しくは下に追記しました) Prml HackathonView more presentations from tsubosaka. 追記: perplexityの値が悪くなったというと変分ベイズのように近似が入って性能が悪くなる印象を与えますがそうではないです。 slice samplerはgibbs samplerと同様に十分な回数反復すれば正しい確率分布からのサンプルを取ることができ
持橋さんのlwlmに関する記事を読んで、スライスサンプリング[1,2]というのが有用そうということで調べてみたのでメモ。 スライスサンプリング概要 今確率分布f(x)が の形で与えられており、このf(x)からxをサンプリングすることを考える。ここでl(x)は非負の関数、\pi(x)は確率密度関数とする。 サンプリングを以下の手順で行なう 初期値x_0を適当に決定する u_t = Uniform(0 , l(x_t))で一様分布からサンプリング X_t = { x | u_t < l(x)}とする x_{t+1}をX_tに含まれるxから\pi(x)に従ってサンプリングする 2へ戻る ここでu_tの値は捨てて、{x_t}だけ取り出すとf(x)に従うxをサンプリングできる。 何が嬉しいのか スライスサンプリングの話は以前から聞いたことがあったのですが、連続の場合だと4の部分が簡単にできそうではな
プログラム上からPDFの文章を取り出したいと思うことがあったので、方法を調べてみた。 PDFBoxというツールを使うと結構いい感じに抽出できた。 以下に簡単なサンプルプログラムを示す。 import java.io.*; import org.apache.pdfbox.pdfparser.PDFParser; import org.apache.pdfbox.pdmodel.PDDocument; import org.apache.pdfbox.util.PDFTextStripper; public class ExtractPDF { private static String extractText(String filePath) throws FileNotFoundException, IOException { FileInputStream pdfStream = ne
PRML勉強会の発表資料公開しました。 自分の担当は10.1の変分推論のところでした。次回は10.2以降からでPRMLで計算が一番多いところなので予習を頑張らないとなといった感じです。 Prml 10 1View more presentations from tsubosaka.
持橋さんの書かれたgoogle-sparsehashと自作のsplay-treeとの速度比較をした結果の記事を読んで、さすがに速度に200倍近くの差がでるのはおかしいだろうということで原因を探ってみた。 結論としてはGoogle Sparsehashを使うときに__gnu_cxx::hashを使わない方がよいということが分かった。 時間の測定に用いられているコードは概ね以下のコードと同じである。 #include <iostream> #include <google/sparse_hash_map> #include <cstdio> #include <cstring> #include <ext/hash_map> using namespace std; using google::sparse_hash_map; typedef __gnu_cxx::hash<const cha
bayonやCLUTOが爆速な理由 - download_takeshi’s diaryを読んで、すぐには成り立つかどうか分からなかったので証明してみた。 上の記事で述べられていることはクラスタ中のベクトルとその中心ベクトルのコサイン類似度の和と、クラスタ中のベクトルを全て足したベクトルのノルムが一致するというである。 ただしここでクラスタ中の要素ベクトルはすべて大きさ1の規格化されたベクトルであるとする。 証明 今クラスタ内に含まれるベクトルを とする。 このとき全ベクトルを足しこんだ複合ベクトルを とする。またこのクラスタのセントロイドは となる。このときセントロイドと各ベクトルとのコサイン類似度は [tex: s_i = \frac{}{||C|| ||x_i||} = \frac{}{||{C}||}] となる。ここでと正規化されていることを用いた。この類似度の合計は [tex:
3/6の第11回PRML読書会と2/9の第10回PRML読書会の資料を今さらですが、SlideShareにアップしたのでリンク貼っておきます。 Prml Reading Group 10 8.3View more presentations from tsubosaka. Prml Reading Group 11 LDPCView more presentations from tsubosaka.
MG勉強会の後にid:sleepy_yoshiさんに教えてもらったWSDM 2009における講演"Challenges in Building Large-Scale Information Retrieval Systems"で述べられている符号化方式のGroup Varint Encodingを実装してみた。 資料 講演スライド スライドの日本語による解説記事 整数の符号化方式 転置インデックスなどで文章番号のリストを前の値との差分で表すなどの方法を用いると出現する、ほとんどの値は小さな値となるためこれを4バイト使って表現するのは記憶容量の無駄である。 このためVarint Encoding、ガンマ符号、デルタ符号、Rice Coding、Simple 9、pForDeltaなど様々な符号化方式が提案されている。このうちVarint Encodingは実装が手軽なことからよく用いられて
bayonを使って画像からbag-of-keypointsを求める - のんびり読書日記の記事を読んで、クラスタリングを行う際の入力データを作るために文献[1]にある方法が利用できると思って実験してみた。 局所特徴量を持ったデータの取扱い 画像データの分類などを行う際にSIFTのような画像中の特徴点(keypoint)を抽出するということがよく行われる。 例えばSIFTを用いる場合は各keypointは128次元のベクトルとなり、画像ごとにいくつかのkeypointが抽出される。ここで抽出されるkeypointの数は画像ごとに異なる。このため、画像間の類似性を比較するのは困難である。 これに対するアプローチとしては一つは画像中の特徴点同士の全対比較を行う、もしくはマッチングをとるという方法が挙げられるがこれは計算量が非常に大きい。 別の方法としてヒストグラムを利用するという方法がある。これ
pthread_cancelを使ったプログラムを書いててはまりそうになったのでメモ。 下のコードのように子スレッドでpthread_cond_wait(3)を用いてなんらかの条件が成立するまで待機している関数があるとする。このスレッドをキャンセルしてみる。 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t cond = PTHREAD_COND_INITIALIZER; void * func(void * arg){ int last_type; pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED , &last_type); pthread_mutex_lock(&mutex); // cancelation point pthread_cond_wait(&con
新年明けましておめでとうございます。今年初の論文紹介。 大規模なデータセットに対する条件付き最大エントロピーモデルの学習を並列で行う話[1]。 論文概要 条件付き最大エントロピーモデルの学習を並列でおこなうというタスクに関して、標準的な3通りの方法について比較を行った。 そのうちmixture weight methodに関しては収束レートの理論的解析を行っている また100万件から10億件までのデータセットに対して実験を行った。 条件付き最大エントロピーモデル 条件付き最大エントロピーモデルの詳細に関しては文献[2]などを参考にされたい。 訓練データS={(x_1,y_1) , \dots , (x_m ,y_m)}が与えられたとする。ここでxは入力データ、yはクラスラベルだと思ってもらえればよい。素性ベクトルをとして、としたとき、解かなければならない問題は を最小化するwを求めることで
次のページ
このページを最初にブックマークしてみませんか?
『tsubosakaの日記』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く