疎行列同士のcos類似度計算では、0以外の要素集合に変換すると超速いことに気付いた(Ruby) - Qiita
# vectorsには上記の変換を行った疎行列が約40000格納される vectors = Marshal.load(File.read(input)) # クエリの行列 input = vectors[id] # 類似度が上位5個を保存 max_score = Array.new(5, {score: 0, index: 0}) vectors.each_with_index do |vector, index| double = vector[0] & input[0] score = 0 double.each do |s| score += vector[1][vector[0].index(s)] * input[1][input[0].index(s)] end score = score.fdiv(Math.sqrt(input[1].reduce(0){|vec, s| v
最大マージン kNN と SVM の関係: kNN も最近はがんばっています - 武蔵野日記
先日書いた機械学習における距離学習の続き。 kNN (k-nearest neighbour: k 近傍法)は Wikipedia のエントリにも書いてある通り、教師あり学習の一つで、あるインスタンスのラベルを周辺 k 個のラベルから推定する手法。memory-based learning と呼ばれることもある。単純に多数決を取る場合もあれば(同点を解決する必要があるが)、近いインスタンスの重みを大きくする場合もあるのだが、いずれにせよかなり実装は単純なので、他の機械学習との比較(ベースライン)として使われることも多い。 簡単なアルゴリズムではあるが、1-NN の場合このアルゴリズムの誤り率はベイズ誤り率(達成可能な最小誤り率)の2倍以下となることが示されたり、理論的にもそれなりにクリアになってきているのではないかと思う。また、多クラス分類がちょっと一手間な SVM (pairwise に
高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開
Yahoo! JAPAN研究所の岩崎です。 私は主に特定物体認識の研究開発を行っていますが、その一方で特定物体認識において必須技術である高次元ベクトルデータの近傍検索の研究開発も行っています。近傍検索の一種であるk最近傍検索とは、クエリとしてベクトルデータが与えられた時に、クエリと空間内に点在するベクトルデータとの距離に基づき近い順にk個のデータを検索する、ことです。kが5の場合の最近傍検索の例を図1に示します。図中の数字は距離の順位で、青い点が検索結果となるデータです。 空間内のすべてのデータとの距離を計算すると時間がかかるので、高速化のためにインデックスを利用します。インデックスを用いることにより数次元といった低次元のベクトルデータ空間では高速な検索が比較的容易に実現できます。しかし、インデックスを用いても100次元を超えるような高次元ベクトルデータの場合には高速に検索することが困難と
3日で作る高速特定物体認識システム (7) 最近傍探索の高速化 - 人工知能に関する断創録
3日で作る高速特定物体認識システム (6) 線形探索を用いた特定物体認識（2009/11/22）のつづきです。今回がこのシリーズの最終回です。 前回の線形探索は遅すぎるので最近傍探索を高速化します。これで表題の高速特定物体認識システムができあがります。高速化にはいくつかの方法がありますが、物体モデルデータベースをなんらかのデータ構造にあらかじめ格納しておくというのがポイントです。今回は、資料でも述べられているkd-treeとLocality Sensitive Hashing (LSH)という手法を試してみます。kd-treeは木構造、LSHはハッシュでデータを構造化（インデキシング）します。kd-treeは、厳密な最近傍を求めますが、LSHは近似最近傍検索と呼ばれ、厳密な最近傍は求められない代わりに計算を大幅に高速化できます。 資料では、ANN (Approximate Nearest
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
