タグ

ブックマーク / tsubosaka.hatenadiary.org (22)

  • Regularized Latent Semantic Indexing - tsubosakaの日記

    最近勉強会で発表する予定のものと仕事関係の論文しか読んでなかったのでこのブログにはあんまり書けなかったんだけど、久々に書いてみる。 紹介する論文はSIGIR 2011のLSIを語彙数が大きい時にも効率的に並列化できるようにしたという論文[1]。 論文概要 PLSIやLDAみたいなトピックモデルは情報検索においても性能向上で重要であるが、語彙数が多い時スケールしないという問題点がある(文章数に関しては効率的な実装が知られている。例えば[2])。このためよく行われるのが語彙数を1万とかに制限する方法ですが、情報検索への応用を考えるとこのアプローチは問題がある(文章分類やクラスタリングへの応用であればこれで問題ない)。 このため著者らはRLSIという方法を提案した。これにより160万文章、語彙数700万のデータセットに対して16台のマシンでトピック数500のとき1時間半で処理できた(おそらく1イ

    Regularized Latent Semantic Indexing - tsubosakaの日記

  • 初ビット列がでるまでの期待時間 - tsubosakaの日記

    kinabaさんのブログの 「無限ビット列を作ったときに最初に "001" が並ぶインデックスの期待値は 8。では、"000" なら？」という問題に対して、マルチンゲールを使った解説をしてみます。 いま無限に生成されるビット列に対して次に何がでるかを賭けるギャンブルを考えます。配当はフェアな賭けで賭け金の2倍返しとします。ここで000が出現したら賭けは終了するとします。 このとき毎時刻ギャンブラーが1$持ってきてつぎのように賭けます。 1. はじめに0が出ることに賭けて、勝ったら次へ、そうでなければ終了 2. 再び0が出ることに前の儲け2$を全額賭ける、勝ったら次へ、そうでなければ終了 3. 再び0が出ることに前の儲け4$を全額賭ける、勝ったら000が出てるので賭け自体が終了、そうでなければ終了この話はたとえば010がでる期待値を考えるときは2.のところで0にではなく1に賭けることになりま

    初ビット列がでるまでの期待時間 - tsubosakaの日記

  • [機械学習] LDAのコードを書いてみた - tsubosakaの日記

    昔書いたことがあったけど、どこかにいってしまったのでもう一度書いてみた。推論方法にはギブスサンプリングと変分ベイズの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

    [機械学習] LDAのコードを書いてみた - tsubosakaの日記

  • [機械学習] NIPS読む会で発表してきました - tsubosakaの日記

    id:nokunoさん主催のNIPS読む会で発表してきました。 僕が発表した論文はThe Multidimensional Wisdom of Crowdsというものです。この論文を選んだのはOral Sessionの論文の中でタイトルがちょっと面白そうだったのでという理由です。 機械学習では大量のラベル付けしたデータが必要になることが多いのですが、データ自体は例えば画像ならGoogle画像検索やflickrなどから大量に取ってくることができるのですが、それにラベル付けをするとなるとどうしても人手が必要であることが多く困ってしまうことがあります。 こういったときのためにAmazon Mechanical Turkという画像にラベルをつけるとか簡単なアノテーションを安く大量に行ってもらうサービスがあるのですが、このサービスを普通に使うとアノテータの質が良くなかったりしてラベルの質が良くないと

    [機械学習] NIPS読む会で発表してきました - tsubosakaの日記

  • Power Iteration Clustering - tsubosakaの日記

    岡野原さんの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>=...>=

    Power Iteration Clustering - tsubosakaの日記

  • [NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記

    この文章について 最近言語モデル方面にも少し興味があるので自分の知識を整理する意味で書いてみた。NLPは専門ではないので、おかしなことを書いてある可能性がありますがその場合はご指摘ください。 本文章ではn-gramモデル、単語の出現確率がn-1個前の単語のみに依存するモデルを考える。 問題 who is * という文が与えられたときに*にくる文字の確率を求めることを考える。この場合だと*には例えばheが当てはまるかもしれないが, isが入ることはまずなさそうに思える。このことは文法的にも説明ができると思うが、文法のルールを作るのは大変だし、文法的に正しい単語の中でどれが出やすいかということはできない。 一方で機械学習を使った言語モデルの文脈では文法的知識を余り持たず、与えられたコーパスから自動的に出やすい単語/表現を学習する方針をとる。 最尤推定 一番簡単なモデルとしては最尤推定を使うもの

    [NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記

  • [プログラミング] Google Sparsehashを使うときの注意点 - 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

    [プログラミング] Google Sparsehashを使うときの注意点 - tsubosakaの日記

  • PRML勉強会 - tsubosakaの日記

    PRML勉強会の発表資料公開しました。 自分の担当は10.1の変分推論のところでした。次回は10.2以降からでPRMLで計算が一番多いところなので予習を頑張らないとなといった感じです。 Prml 10 1View more presentations from tsubosaka.

    PRML勉強会 - tsubosakaの日記

  • [機械学習] スライスサンプリング - tsubosakaの日記

    持橋さんの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の部分が簡単にできそうではな

    [機械学習] スライスサンプリング - tsubosakaの日記

  • [機械学習] PRML Hackathon #2 - tsubosakaの日記

    PRML Hackathonに行ってきました。 今回のHackathonでは昨日書いたスライスサンプリングという手法をLDAの推論に使ってみて通常のGibbs samplerと比較してみました。 結果としてはサンプリング速度が2-3倍程度高速になり、手法の有効性を確かめることができました。また、perplexityの値は Gibbs samplerよりも少し悪い結果となりました。(誤解を招く表現でした、詳しくは下に追記しました) Prml HackathonView more presentations from tsubosaka. 追記: perplexityの値が悪くなったというと変分ベイズのように近似が入って性能が悪くなる印象を与えますがそうではないです。 slice samplerはgibbs samplerと同様に十分な回数反復すれば正しい確率分布からのサンプルを取ることができ

    [機械学習] PRML Hackathon #2 - tsubosakaの日記

  • [機械学習] PRML勉強会発表会資料 - tsubosakaの日記

    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.

    [機械学習] PRML勉強会発表会資料 - tsubosakaの日記

  • [IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - 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は実装が手軽なことからよく用いられて

    [IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記

  • Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models - tsubosakaの日記

    新年明けましておめでとうございます。今年初の論文紹介。 大規模なデータセットに対する条件付き最大エントロピーモデルの学習を並列で行う話[1]。 論文概要 条件付き最大エントロピーモデルの学習を並列でおこなうというタスクに関して、標準的な3通りの方法について比較を行った。 そのうちmixture weight methodに関しては収束レートの理論的解析を行っている また100万件から10億件までのデータセットに対して実験を行った。 条件付き最大エントロピーモデル 条件付き最大エントロピーモデルの詳細に関しては文献[2]などを参考にされたい。 訓練データS={(x_1,y_1) , \dots , (x_m ,y_m)}が与えられたとする。ここでxは入力データ、yはクラスラベルだと思ってもらえればよい。素性ベクトルをとして、としたとき、解かなければならない問題は を最小化するwを求めることで

    Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models - tsubosakaの日記

  • Streaming k-means approximation - tsubosakaの日記

    実家に帰省中，電車の中で読んでた論文の紹介。 概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。 しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。 ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっている ストリームアルゴリズムについて 本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。 k-meansとは k-meansとはデータ点 X = {x_1 , ... x_

    Streaming k-means approximation - tsubosakaの日記

  • Polynomial Semantic Indexing - tsubosakaの日記

    NIPS 2009で発表された論文"Polynomial Semantic Indexing" [1]を読んだ。これは低ランク近似を用いた教師ありの情報検索に関する手法である。 情報検索について 与えられたクエリに関して適当な重みづけをおこなって順位づけして、適切な文章を返却するという問題は古くから研究されている。 オーソドックスな方法としては文章をbag-of-wordsで表して各単語の重みをtf-idfで正規化し、クエリに関しても同様な処理を行いコサイン類似度などの距離尺度を使って最も近い何件かを返すというものがある。この方法の欠点としてはクエリの単語を含まない文章はヒットしないという問題がある。これは各単語が独立であるという仮定を行っているためであり、明らかに誤っている仮定である。 もう一つの方法としては文章-単語行列が低次元の特徴量によって近似する方法である。代表的な方法としてLS

    Polynomial Semantic Indexing - tsubosakaの日記

  • [論文] Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units - tsubosakaの日記

    NIPS 2009のonline papersがすでにダウンロードできるように*1なってたのでタイトルを眺めていたらGPUでLDAを並列化するという論文があって読んだので少し紹介してみる。 まず、彼らの論文[1]ではLDAの推論アルゴリズムのうち、Collapsed Gibbs sampling(CGS)とCollapsed Variational Bayes(CVB)の2つに関して並列化を試みているがCollapsed Gibbs samplingの方に関してのみ紹介する。また、彼らの論文ではGPGPUの統合開発環境としてCUDAを用いている。 LDAについて LDAは論文[2]で提案された、文章生成モデルでトピック分析などに広く用いられている。 モデルの推論アルゴリズムとしては変分ベイズ[1]、ギブスサンプリング[4]、EP、collapsed 変分ベイズ[5]などが知られている。 こ

    [論文] Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units - tsubosakaの日記

  • [プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記

    ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))

    [プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記

  • 次元が高い場合に関してのsimhashの計算 - tsubosakaの日記

    最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。 ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。 解説 simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビット

    次元が高い場合に関してのsimhashの計算 - tsubosakaの日記

  • Interpolative coding - tsubosakaの日記

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

    Interpolative coding - tsubosakaの日記

  • SVMソフトウェアの比較 - tsubosakaの日記

    オープンソースのSVMソフトウェアの基本デフォルトの設定で比較などをしてみた。 利用データはLIBSVM Data: Classification, Regression, and Multi-labelのa9aとnews20.binaryを利用した。 データセットの詳細は以下のようになっている データセット名 訓練データ数 テストデータ数 データの次元 a9a 32561 16281 123 news20.binary 15000 4996 1355199 なお、news20.binaryでの訓練データとテストデータの作成については id:n_shuyoさんの記事を参考にした。 比較に用いたソフトウェアは以下の5つ LIBSVM リンク SVM-Light リンク TinySVM リンク SVM-perf リンク LIBLINEAR リンク 測定結果は以下のようになった。パラメータの設定

    SVMソフトウェアの比較 - tsubosakaの日記
  • 1 2 次のページ

お知らせ

もっと読む

公式Twitter

  • @HatenaBookmark

    リリース、障害情報などのサービスのお知らせ

  • @hatebu

    最新の人気エントリーの配信

はてなブックマーク

公式Twitter

はてなのサービス

  • App Storeからダウンロード
  • Google Playで手に入れよう
Copyright © 2005-2025 Hatena. All Rights Reserved.