Locality Sensitive Binary Codes for Shift Invaliant KernelsとSpectral Hashingの比較 - Yasuo Tabeiの日記
Locality Sensitive Hashing(LSH)とは、ベクトルとして表現されたデーターの集合を入力として、それらの２点間の距離を保存したまま、ハミング距離に基づく文字列の集合に射影する技術です。コサイン距離[1]、ユーグリッド距離[2]に基づくものや、機械学習法を応用した、semantic hashing[3], spectral hashing[4], kernelized LSH[5], その他[6][7][8]、現在までに多くの手法が提案されています。この背景には、Googleが、昔に提案されたLSHが、ニュース記事の推薦システムで使えることを示した[9]のきっかけに、現在、推薦システム、画像検索、文章のクラスタリング[10]など、色々なシステムや研究の場面で利用されています。 理論的な収束の保証があるという意味で、オリジナルのコサイン距離ベース[1]の手法が良いのです
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>=...>=
Streaming k-means approximation - tsubosakaの日記
実家に帰省中，電車の中で読んでた論文の紹介。 概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。 しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。 ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっている ストリームアルゴリズムについて 本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。 k-meansとは k-meansとはデータ点 X = {x_1 , ... x_
きまぐれ日記: MIRAとstructured outputs
MIRAというアルゴリズムが統計的係り受けの学習でいい成績を叩き出しているようです． 係り受けに特化したアルゴリズムではなく，structured output ならほぼ何でもできる非常に汎用性の高いアルゴリズムのようです．詳細はこちら 面白そうなので，ちょっと深追いしてみました．特徴をまとめると - オンライン学習 - k-best解が得られるような decoder さえあれば動く - single-best でももちろん可能 - single best の場合は Collins voted perceptron に酷似 - single best の場合の inference は SMO と共通点があり，実際 max-margin parsing の特殊系になっている などなど，面白い点がたくさんあります． もともとは Ben Tasker の Max margin parsing の
オンラインEMアルゴリズム - DO++
EMアルゴリズム（Expectation Maximizationアルゴリズム、期待値最大化法、以下EMと呼ぶ）は、データに観測できない隠れ変数（潜在変数）がある場合のパラメータ推定を行う時に有用な手法である。 EMは何それという人のために簡単な説明を下の方に書いたので読んでみてください。 EMのきちんとした説明なら持橋さんによる解説「自然言語処理のための変分ベイズ法」や「計算統計 I―確率計算の新しい手法 統計科学のフロンティア 11」が丁寧でわかりやすい。 EMは教師無学習では中心的な手法であり、何か観測できない変数を含めた確率モデルを作ってその確率モデルの尤度を最大化するという枠組みで、観測できなかった変数はなんだったのかを推定する場合に用いられる。 例えば自然言語処理に限っていえば文書や単語クラスタリングから、文法推定、形態素解析、機械翻訳における単語アライメントなどで使われる。
Vowpal Wabbit (Fast Learning)
This is a project started at Yahoo! Research and continuing at Microsoft Research to design a fast, scalable, useful learning algorithm. VW is the essence of speed in machine learning, able to learn from terafeature datasets with ease. Via parallel learning, it can exceed the throughput of any single machine network interface when doing linear learning, a first amongst learning algorithms. We prim
SODA2010 ALENEX2010＠テキサス - DO++
先日までTexas Austinで開催されていたALENEX2010とSODA2010に参加してきました。 一緒に行った吉田さんの感想もありますのでそれも参照してください まず一応自分のALENEXでの発表資料は以下にありますので参照ください "Conjunctive Filter: Conjunctive Filter: Breaking the Entropy Barrier"論文、発表スライド(pptx pdf) 他に聞いた中で印象的だったものを下に書いてみます。ただ、大部分の発表は私の基礎知識が足りなくてついていけませんでした。残念 昨年末の研究開発セミナーでも紹介しましたが、簡潔木とよばれる限界まで圧縮した上で（ノード数がnの時2n+o(n) bit）様々な木上での操作（親を辿る、子を辿る、共通祖先を探すなど）のあらゆる操作を統一された操作の組み合わせで実現するというものの理論的
non-Negative Matrix Factorization (NMF) - naoyaのはてなダイアリー
以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し、低階数近似を行います。これにより、似たような次元をまとめたりといった効果が得られるのでした。自分の考察では HITS も同様のことを行っているという認識でした。 さて、集合知プログラミングを読んでいたら、第10章で "non-Negative Matrix Factorization" (非負値行列因子分解, 以下NMF) という手法が出てきました。NMF も SVD や主成分分析に同じく行列を分解
SciPyを用いて潜在的意味解析(LSA) - 未来は僕以外の手の中
自然言語処理の技法の１つに、潜在的意味解析(LSA)というものがある。 単語文書行列Ａがあった場合、特異値分解(SVD)により Ａ=ＵΣＶ に分解し、特異値を大きいほうからk個使って Ａk=ＵkΣkＶk のように階数の低減を行うことで、階数kのＡへの近似を最小誤差で得ることができる。 つまり特異値分解の計算さえできてしまえばLSAもすぐできるわけだが、 pythonの数値解析モジュールScipyにかかれば特異値分解もあっという間である。 まずは特異値分解まで↓ from numpy import * from scipy import linalg A = matrix([ [5, 8, 9, -4, 2, 4], [2, -4, 9, 4, 3, 3], [-3, 4, 8, 0, 5, 6], [-2, 5, 4, 7, 0, 2] ]) u, sigma, v = linalg.sv
「確率密度比」を用いた機械学習の新たなアプローチ - yasuhisa's blog
東工大の杉山先生の講演がすごく面白かったのでメモ。 やりたいこと、特徴p(x)とp'(x)という分布を推定しようという問題があったとする。このとき、二つの分布のパラメータを推定しないといけないので普通は大変。そこで、w(x) = p'(x) / p(x)を推定するという風に少し変形してやる。p(x)とp'(x)が分かればw(x)は求めることができるが、w(x)があってもp(x)とp'(x)は分からない。ということでw(x)のほうが簡単な問題になっている。 こういう風に「何か問題を解くときに、その過程で元の問題より難しい問題を解かないようにしないと!」というような考え方をVapnikの原理といったりするそうです。 この確率密度比の枠組みを利用すると非定常環境適応、ドメイン適応、マルチタスク学習、外れ値検出、時系列の変化点検知、特徴選択、次元削減、独立成分分析、条件付き確率推定などなどの問題を
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
自然言語処理における類似度学習(機械学習における距離学習)について - 武蔵野日記
Twitter でグラフ理論に関する話題が上がっていたので、最近調べている距離学習(distance metric learning)について少しまとめてみる。カーネルとか距離(類似度)とかを学習するという話(カーネルというのは2点間の近さを測る関数だと思ってもらえれば)。 この分野では Liu Yang によるA comprehensive survey on distance metric learning (2005) が包括的なサーベイ論文として有名なようだが、それのアップデート(かつ簡略)版として同じ著者によるAn overview of distance metric learning (2007) が出ているので、それをさらに簡略化してお届けする(元論文自体本文は3ページしかないし、引用文献のあとに表が2ページあって、それぞれ相違点と共通点がまとまっているので、これを見ると非
きまぐれ日記: 情報抽出アルゴリズム Espresso 最終章
Espresso を飲みながらさらに Espresso を考えていました。 r_instance = A^n * r_instance_0 となるのは間違いないと思います。A は P * P^{T}、さらに P = 1/|I||P| * pmi(i, p)/ maxpmi です。 A は、インスタンスどうしの類似度を表現した正方対称行列です。A_{i,j} はインスタンス i, j の類似度です。 類似度は、パターン個数次元からなるベクトルの内積で、各次元は pmi となります。 この形だと、r_instanc は r_instance_0 できまるので、初期値に依存してるように思えますが、A^n がいったい どういう意味を持つのかずっと考えていました。 A_{i,j} が 0, 1 の場合、A は無向グラフの接続行列となります。i,j がつながっている場合は A_{i,j} = 1となり
SVM-Light: Support Vector Machine
SVMlight Support Vector Machine Author: Thorsten Joachims <thorsten@joachims.org> Cornell University Department of Computer Science Developed at: University of Dortmund, Informatik, AI-Unit Collaborative Research Center on 'Complexity Reduction in Multivariate Data' (SFB475) Version: 6.02 Date: 14.08.2008 Overview SVMlight is an implementation of Support Vector Machines (SVMs) in C. The main featu
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.neurosci.aist.go.jp/~akaho/thesis/thesis-www/node16.html
http://www.cs.princeton.edu/~wdong/wiki/index.php?n=Main.Research
(Matlab) Codes and Datasets for Subspace Learning (Dimensionality Reduction)
not found
業績