Matrix Factorizationで遊ぶ - Negative/Positive Thinking
はじめに 次元削減せずにはいられない。 0の扱いがいまいちピンとこなかったので、ちょっと調べて試してみた。 Matrix Factorizationとは Netflix Prizeという推薦システム・協調フィルタリングのコンテストで良い結果を残した手法 行列Mを、2つの行列P,Qの掛け算で近似するもの 行列Mが与えられたとき、行列Pと行列Qをそれぞれ見つける ユーザー数m、アイテム数nとして、Mはm*n行列。Pはm*k行列。Qはn*k行列。 行列Mには欠損データが含まれている 行列PとQを求めるために次式を最小化する min Σ_{(u,i)∈κ} (M[u][i] - Q_vec[i]*P_vec[u])^2 + λ(|Q_vec[i]|^2 + |P_vec[u]|^2) κは、既知のM[u][i]が存在する(u,i)のペアの集合 SGDで解を探す場合は以下の反復式になる e_ui :
トピックモデルメモ - Negative/Positive Thinking
はじめに トピックモデルについてメモ。 トピックモデルとは 文書は、何らかの話題について書かれていたりする 「ある文書内に一緒にでてくる単語は、意味的な関連性が強い」など考えられる トピックモデルは、文書から「何らかの話題(＝トピック)」を発見するための統計的なモデルのこと トピックモデルのいろいろ Unigram Mixtures ナイーブベイズでクラス数kと各パラメータをEMで繰り返し推定していく http://www.kamalnigam.com/papers/emcat-mlj99.pdf Probabilistic Latent Semantic Indexing(PLSI) 検索技術であった潜在意味解析(LSI,1990年)を確率的に解析、開発された生成モデル(1999年) 各単語ごとに別なトピックから生成されたと仮定する http://cs.brown.edu/~th/pap
Locality Sensitive Hashによる類似ベクトル検索を試す - Negative/Positive Thinking
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと 高次元データの次元圧縮を行える (P1,P2,r,cr)-sensitiveなHash族とは、 2つの特徴ベクトルp,qについて(P1>P2) ||p-q||P1 ||p-q||>crならPr[h(p)=h(q)] を満たすハッシュ関数h:R^d->U コサイン類似度に対するLSH 2つのk次元ベクトルu,vについて コサイン類似度: u*v / sqrt(|u|*|v|) d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を h_i(u) = 1 (r*u >=0) h_i(u)
超大規模テキストにおけるN-gram統計 - Negative/Positive Thinking
はじめに 超大規模なテキストデータでのN-gram統計を取る場合、そもそもデータがメモリにのらなくてSuffixArrayを使ったカウントも無理だったりする。近似値でよい場合、効率的な方法があると知ったのでちょっとメモ＆試してみた。 与えられるデータ 大量のデータがストリーム形式で与えられるとする 高速にどんどん与えられる 例えば、データパケット監視やtwitterなど カウントしたいデータの種類が膨大 種類をメモリに保持するのが無理 ストリームデータにおける頻度カウント法 正確なカウントは難しいが、近似的に頻度カウントを行うことができる Sticky Sampling Algorithmは解釈が間違っているかもしれない Sticky Sampling Algorithm カウントする要素をサンプリングで選ぶ方法 保持するのは以下の2つのペアの集合 e : 要素(例えばN-gram) f
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
サンプリング法メモ - Negative/Positive Thinking
はじめに ある分布に従った乱数を生成したいことがよくあったりする(一様分布に従う一様乱数や正規分布に従う正規乱数など)。 ベイズ統計学なんかだと、自然共役事前分布が使えないような複雑な分布の場合にMCMCで分布のサンプリングをして計算したりするので、結構使う場面は多い(はず)。 ちょっと調べてみたので、メモ。(基本、PRML第11章のはなし) 一様分布からの(疑似)乱数生成 一様乱数の生成の仕方について。少し。 線形合同法 X_{n+1} = (A*X_{n}+B) mod Mという形式で乱数Xを次々に生成していく方法 C言語のライブラリで実装されているrand関数 多次元にすると均等に分布しなかったり、下位ビットがランダムじゃなかったり、といろいろ問題がある xorshift http://ja.wikipedia.org/wiki/Xorshift xor演算とビットシフトだけで生成し
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
