[機械学習] CVB0を実装してみた - tsubosakaの日記
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 =
![[機械学習] CVB0を実装してみた - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/1076ded556cb2333ae5e387eee863e409f9bbd05/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124031153%2F1557332457)
[機械学習] トピックモデル関係の論文メモ - tsubosakaの日記
最近読んだトピックモデル関係の論文のざっとしたメモ。内容については間違って理解しているところも多々あると思います。 (追記 12/24) 最後のほうに論文を読む基礎となる文献を追加しました。 Efficient Methods for Topic Model Inference on Streaming Document Collections (KDD 2009) 論文の話は2つあって一つ目がSparseLDAというCollapsed Gibbs samplerの省メモリかつ高速な方法の提案と2つ目はオンラインで文章が入力されるような場合において訓練データと新規データをどう使うかという戦略について述べて実験している。 Collapsed Gibbs samplerを高速化しようという論文はPorteous et al.(KDD 2008)でも述べられているけどそれよりも2倍ぐらい高速(通
![[機械学習] トピックモデル関係の論文メモ - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/a7d7bebddebe117cac45f7a60d8849efcd2d85c8/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124031236%2F1557332459)
Polynomial Semantic Indexing - tsubosakaの日記
NIPS 2009で発表された論文"Polynomial Semantic Indexing" [1]を読んだ。これは低ランク近似を用いた教師ありの情報検索に関する手法である。 情報検索について 与えられたクエリに関して適当な重みづけをおこなって順位づけして、適切な文章を返却するという問題は古くから研究されている。 オーソドックスな方法としては文章をbag-of-wordsで表して各単語の重みをtf-idfで正規化し、クエリに関しても同様な処理を行いコサイン類似度などの距離尺度を使って最も近い何件かを返すというものがある。この方法の欠点としてはクエリの単語を含まない文章はヒットしないという問題がある。これは各単語が独立であるという仮定を行っているためであり、明らかに誤っている仮定である。 もう一つの方法としては文章-単語行列が低次元の特徴量によって近似する方法である。代表的な方法としてLS
[プログラミング] ビット並列アルゴリズムを使った編集距離 - 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の日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/466673dcf501fbd428f9b1a630d943c8246acf97/height=288;version=1;width=512/https%3A%2F%2Fcdn.image.st-hatena.com%2Fimage%2Fscale%2Fbf0812ca52ab03f4abef108e09e49c6a9ef9fb9e%2Fbackend%3Dimagemagick%3Bheight%3D1200%3Bversion%3D1%3Bwidth%3D1200%2Fhttps%253A%252F%252Fcdn-ak.f.st-hatena.com%252Fimages%252Ffotolife%252Ft%252Ftsubosaka%252F20091103%252F20091103000001.jpg)
次元が高い場合に関してのsimhashの計算 - tsubosakaの日記
最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。 ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。 解説 simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビット
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
自然言語処理研究会 - tsubosakaの日記
