Earth Mover's Distance (EMD) - 人工知能に関する断創録
Earth Mover's Distance (EMD) について調べたことを整理しておきます。EMDは、ユークリッド距離のような距離尺度の一つで、二つの分布の間の距離を測ることができます。言語処理ではあまり聞いたことなかったのですが、画像処理や音声処理では比較的有名な距離尺度のようです。 EMDが使える問題設定は下図のようになります。 EMDは特徴量と重みの集合（シグネチャと呼ぶ）で与えられる分布Pと分布Qの間の距離です。ここで、特徴量間では距離 が定義されているのが前提です。特徴量がベクトルのときはユークリッド距離、特徴量が確率分布のときはカルバック・ライブラー距離（情報量）などです。EMDは、特徴量の集合が2つ与えられたときに、1個1個の特徴量間の距離をもとに、特徴量集合間の距離を求められるんですね。これはすごい。 重みは具体的な応用によって使い方が変わりますが、その特徴量の重要度を
BWT と PPM - naoyaのはてなダイアリー
Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。 先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。 サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると本質的に同じことをやっていると言える、というところです。 BWT のあら
ほぼワンパスなラベリング処理 - wosugi blog
画像処理の基礎的な処理の一つにラベリング処理というのがあります。これは連結する画素・領域をくっつけていって、最終的に同じ性質を持つ領域ごとに番号（ラベル）をふるというものです。このラベリングには数多くのやり方があり、突き詰めていけばワンパス（画像を一回だけラスタスキャンする）で処理できることが知られています。しかしネット上には意外とワンパスのコードが少なく、ラスタスキャンではなく一部幅優先探索するものや、あるいはワンパスっぽいけどポインタ駆使しすぎ＆コード量が多いものが多々あり*1、処理速度や読みやすさの点でもっと改善できるんじゃないかなぁ〜と感じました。 今回はできるだけ簡単な記述で、ほぼワンパスのラベリングのコードを書きましたので公開します。詳細は後回しして、とりあえずコードです。 //labeling.hpp #pragma once #include <vector> #inclu
中心性：始まりから最近まで - Preferred Networks Research & Development
PFI に入社して二ヶ月ちょっとの伊藤です。 ソーシャルネットワークサービスが一般的になるにつれ中心性という概念が注目されてきました。情報科学を専攻されている場合、Google PageRank や HITS アルゴリズムで算出されるグラフの節点に付与される重要度と言うと分かりやすいとのではないか思います。呼び方こそ違いますが、この中心性と重要度は同一の概念、つまりグラフの節点に重み（点数）をつける尺度として知られています。以下、PageRank とHITS が提案された論文です。 Brin, S. and Page, L. The anatomy of a large-scale hypertextual (web) search engine. Computer Network and ISDN Systems.1998. Kleinberg, J. M. Authoritative
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
lsh
最近傍探索と直積量子化(Nearest neighbor search and Product Quantization)
私のブックマーク ： 簡潔データ構造
田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろいろなリソースを紹介します。 解説記
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei
前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置今回は簡潔ビットベクトルを利用して転置インデックスを効率的に実装してみる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 転置インデックスとは検索エンジンに用いられるインデックスで apple 1, 3 orange 1, 2, 4, 6のように各単
最近傍探索2011 - Preferred Networks Research & Development
こんにちは、二台目のmbaを買うのをためらっている岡野原です。 アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。 アイテムが低次元（例えば2, 3次元）の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元（数百万次元）中の点であったり、アイテム間の距離のみが定義されている場合（カーネル関数など）です。アイテム数は数万から数億ぐらいを想定しています。 最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、 「アイテム集合X = x1,
行列（画像）分解アルゴリズムGoDec (Zhou+, ICML2011)の実装を公開しました - Educational NLP blog
つい2週間ほど前，機械学習のトップカンファレンスICMLが開催されました．その中のGoDecという行列分解アルゴリズムを実装したので公開します．このアルゴリズムは，簡単にいえば「外れ値抜き特異値分解」で，昨日のICML読み会で発表しました．論文はこれです． GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case. Tianyi Zhou, Dacheng Tao. ICML2011. 厳密な版（Nai:ve GoDec）は遅いですが実装は非常に簡単です．遅い版でも，数百x数百ピクセルの小さな画像であれば，十分実用的な速度で動くので，実装して試してみた次第です．GoDecの論文では，この厳密な版（Nai:ve GoDec）が線形収束することを証明した上で，さらに，実用的に早くなるように（証明はないようですが
スペクトラルクラスタリングの基本的な解説、および高速化手法のざっくりとした説明 - The beautiful mind
久しぶりにブログを更新してみる。 以前スペクトラルクラスタリングについて記事を書いたが、そのときはだいぶ勉強不足で、少し見当違いのことを書いていた気がする。 スペクトラルクラスタリングは、本質的にはラプラシアン固有マップ法と同じことをしている。ラプラシアン固有マップ法は次元削減の手法で、もともとの高次元空間におけるデータ間の類似度が、低次元に写像した後にも反映されるように設計されている。それが結果的に類似度行列から定義されるグラフ・ラプラシアンの固有値問題に帰着されるのだ。具体的には、グラフ・ラプラシアンLの固有値を大きいほう（定式化によっては小さいほう）からk番目までをλ1, λ2, …,λk, それに対応する固有ベクトルをv1, v2, …, vk とすると、その固有ベクトルを列として並べた行列 V = (v1 v2 … vk)の各行が、各データ点の低次元空間における座標とする。このと
TF-IDF - 0001
TF-IDF (TFIDF) 情報検索でよく使われる TF-IDF (TFIDF, term frequency - inverse document frequency) に関するメモ。 IDF (inverse document frequency) The IDF page - ... In 1972, Karen Spärck Jones published in the Journal of Documentation the paper which defined the term weighting scheme now known as inverse document frequency (IDF). This was reprinted in 2004 ... Karen Spärck Jones IDF の原典 情報検索と言語処理 を見ると、IDF (inverse
ANN - Approximate Nearest Neighbor Library
ANN is a library written in C++, which supports data structures and algorithms for both exact and approximate nearest neighbor searching in arbitrarily high dimensions. In the nearest neighbor problem a set of data points in d-dimensional space is given. These points are preprocessed into a data structure, so that given any query point q, the nearest or generally k nearest points of P to q can be
Eigen
Get it The latest stable release is Eigen 3.4.0. Get it here: tar.bz2, tar.gz, zip. Changelog. The latest 3.3 release is Eigen 3.3.9. Get it here: tar.bz2, tar.gz, zip. Changelog. The latest 3.2 release is Eigen 3.2.10. Get it here: tar.bz2, tar.gz, zip. Changelog. The unstable source code from the master is there: tar.bz2, tar.gz, zip. To check out the Eigen repository using Git, do: git clone ht
パターン認識と機械学習（PRML）まとめ - 人工知能に関する断創録
2010年は、パターン認識と機械学習（PRML）を読破して、機械学習の基礎理論とさまざまなアルゴリズムを身につけるという目標（2010/1/1）をたてています。もうすでに2010年も半分以上過ぎてしまいましたが、ここらでまとめたページを作っておこうと思います。ただ漫然と読んでると理解できてるかいまいち不安なので、Python（2006/12/10）というプログラミング言語で例を実装しながら読み進めています。Pythonの数値計算ライブラリScipy、Numpyとグラフ描画ライブラリのmatplotlibを主に使ってコーディングしています。実用的なコードでないかもしれませんが、ご参考まで。 PRMLのPython実装 PRML読書中（2010/3/26） 多項式曲線フィッティング（2010/3/27） 最尤推定、MAP推定、ベイズ推定（2010/4/4） 分類における最小二乗（2010/4/
スペクトラルクラスタリングは次元圧縮しながらKmeansする手法 - 武蔵野日記
機械学習系のエントリを続けて書いてみる。クラスタリングについて知らない人は以下のエントリ読んでもちんぷんかんぷんだと思うので、クラスタリングという概念については知っているものとする。 それで、今日はスペクトラルクラスタリングの話。自然言語処理以外でも利用されているが、これはグラフのスペクトルに基づくクラスタリングの手法で、半教師あり学習への拡張がやりやすいのが利点。なにをするかというとクラスタリングをグラフの分割問題(疎であるエッジをカット)に帰着して解く手法で、どういうふうに分割するかによって Normalized cut (Ncut) とか Min-max cut (Mcut) とかいろいろある。 完全にグラフが分割できる場合はこれでめでたしめでたしなのだが、実世界のグラフはそんな簡単に切れないことが往々にしてある。それで近似してこのグラフ分割問題を解くのだが、Normalized c
多次元尺度法で遊んでみる（オレ流 R入門） - ダウンロードたけし（寅年）の日記
多次元データをクラスタリングする際に、それらのデータを2次元データに落とし込んで可視化させたいことがあります。そんな時に便利なのが「多次元尺度法」という手法です。 個々のデータ間の距離／類似度が分かっている場合に、それらのデータの座標を求めて、データ構造を復元するようなものです。 詳しい説明は割愛します。知りたい人はwikipediaと金先生の連載を読んで下さい。 体で覚えるタイプなので、とにかく何かデータを処理してみます。 「山手線」の地図を再現 さっそく試してみます。 山手線の各駅同士の直線距離を測っておいて、そのデータから実際の位置関係を復元できるか実験してみます。 山手線全駅の距離を測るのはめんどいので、適当に抜粋してしらべました。 以下のような表になりました。単位はメートルです。 さてさて、この距離表からどのようなデータ構造が再現されるでしょうか？ このデータを統計解析ソフトRで
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://yogi.bz/~suzu/wp3/?p=266
Vladimir Kolmogorov's homepage
市川ソフトラボラトリー、「SILKYPIXオートホワイトバランス」が“21世紀発明奨励賞”を受賞 