ギレンも登場！BM25なPerlモジュール書いたよ - download_takeshi’s diary
久しぶりに何か書きます。 情報検索のアルゴリズムで「BM25」というものがあります。 何年か前に某研究所に遊びに行ったときに「TF/IDFより精度のいいやつ」みたいな感じでかなりアバウトに教えてもらいました。 その時は「名前だけでも覚えて帰ろう」と思っていたのですが、帰りに安い居酒屋で大酒をのみ、電車のなかで騒いでしまうほど酔っ払ってすっかりその名前を忘れてしまってました。（なにやってんだか・・・） で、最近Web+DB pressをパラパラ見ていたらBM25の名前を発見！ああ、これだこれだ、思い出したよ！ というわけで、重い腰を上げてモジュール化してみました。 githubに上げてあります。 Lingua::JA::OkapiBM25 http://github.com/miki/Lingua-JA-OkapiBM25 そのうちCPANからも落とせるようになります。 正式名称は「Okap
トーナメントと多値分類 - DO++
今やってる研究で、トーナメント問題を調べる機会がありました。 トーナメントは私も知らなかったのですが、勝者や順位を決める方式のことを指し、いわゆる二人ずつ戦って生き残っていく方式はノックアウトトーナメントといわれるそうです(wikipedia)。 ＃10000人戦う時にノックアウトトーナメントでは何回試合が行われるかというのはよくある質問ですね。 で、このトーナメント方式というのは調べてみると非常に様々なものがあります 例えばスイス式トーナメントは、最初はランダムな組み合わせで対戦、次は勝者同士と敗者同士、その次は全勝・１勝１敗・２戦全敗のそれぞれが・・というふうに同じ成績の人同士で戦う方式です。レーティングを計算して、レーティングが近いもの同士を戦わせるような拡張もあります。近いのは将棋でやってるようなものですね。 利点は全ての人が同じ試合数で戦い、また厳密な順位が決めやすいことがありま
2008-07-01 - きしだのはてな - バックプロパゲーションでニューラルネットの学習
ニューラルネットというのは、入力があって、複数の階層を経て出力を得るようなグラフ構造のことです。通常は、入力層・中間層・出力層のように層構造になっているようなものを差します。中でも、中間層が1層の、３層構造になっているものが多くとりあげられます。バックプロパゲーションは、誤差逆伝播法とも言って、ニューラルネットワークのパラメータを学習するための手法です。 ニューラルネットについてのサイトや本では、中間層を多層に対応した一般的な表現で説明されることが多いのですが、なかなか式を読み解くのが難しかったりするので、今回は3層で入力が2パラメータ、出力は1つ、中間層のニューロンは2つという、単純なものを取り上げます。 では、3層ニューラルネットワークでの判定時のデータの流れを見てみます。 3層ということになっていますが、実際の処理は2層になっています。実装するときには2層だと考えたほうがわかりやすい
Consistent Binary Tree Layout(1) - agwの日記
名著アルゴリズム Cの特筆すべき点の一つとして、可視の美しさが挙げられます。特に二分木の可視は美しく、計算されつくされた様にいつも唸らされます。 以下は、アルゴリズム C 第2巻の14章、初等的な検索法の章に掲載されている二分木の可視です。この木は95個の接点から成り立っています。なかなかよく平衡した木で、極端に込み合っていたりもしていませんが、それを差し置いても大変美しく可視されていると言えるでしょう。 また以下は、同じ章に掲載されている二分検索木の可視です。キー群ASEARCHIを用いて構築した二分検索木にキー群NGEXAMPLEを挿入する過程を可視しています。新たなキーが挿入されるにつれ接点の数が増加しているにも関わらず、それぞれの段階における可視は一貫しており、美しいのです。 さて、木の配置を注意深く見てみましょう。以下は、kd-tree Visualization(1) - ag
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
BlockSorting
BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、本当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ（データ）が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も
Succinct なトライの実験に用いたソースコード - やた＠はてな日記
いつものように，Google Code にアップロードしました．プロジェクトの名前は sumire-tries になっています．名前を sumire にした理由は，なんとなくです…． ドキュメントは準備中ですが，基本的な使い方は後述します． Google Code Archive - Long-term storage for Google Code Project Hosting. 右のメニューにある Featured downloads からアーカイブをダウンロードして，よくある手順を踏めば動作確認できます． ./configure make make check ヘッダのみで構成されているため，make install でインストールしなくても，ヘッダを格納しているディレクトリ（include/）をコピーすれば使えます． トライを構築する手順は，以下のようになっています． 基礎となる
min_heapを用いた上位r個の要素の抽出 - tsubosakaの日記
MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。 情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこれを実現するためのコードはもっとも単純に行うと以下のようになる //長さlenの配列arrayの中でトップr個の値をresultに挿入する void sort_method(int * array , int len, int r , vector<int> & result){ sort(array , array + len); copy(array + len - r , array + len , back_inserter(result)); } しかし、Nが大きいとき、MGの例だとN=100万のときにsortの処理にはおおよそ100
[プログラミング] ビット並列アルゴリズムを使った編集距離 - 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/7ca3ca3d9a967967d3c1900062079765c7d58c98/height=288;version=1;width=512/https%3A%2F%2Fcdn.image.st-hatena.com%2Fimage%2Fscale%2F3b21b9940827376b8faf757c1dcc041507e62d8d%2Fbackend%3Dimagemagick%3Bversion%3D1%3Bwidth%3D1300%2Fhttps%253A%252F%252Fcdn-ak.f.st-hatena.com%252Fimages%252Ffotolife%252Ft%252Ftsubosaka%252F20091103%252F20091103000001.jpg)
系列ラベリングアルゴリズムの比較 - 松本研研究日誌
今日の DMLA 勉強会は松本先生で Nam Nguyen and Yunsong GuoComparisons of Sequence Labeling Algorithms and ExtensionsICML-2007の紹介。SVM^struct/SVM^multiclass/CRF/HMM/Averaged perceptron/SEARN/M^3Nといったいろいろなアルゴリズムで品詞タグづけ問題を解くという話。提案手法はensemble learningで複数の手法の重み付けによる分類器を作ると、単体で一番成績がよかったSVM^structよりさらによくなりますよ、とのこと。なんか CRF が予想外に悪かった(松本先生も首を傾げていた)のだが、なんなんだろうか。 SEARN (Search-based Structured Prediction)というのは元論文は Search
2009-10-29 - やた＠はてな日記 Succinct なトライの実験
実験の概要 Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみました．今回のテストで実装したトライは，以下のとおりです． BasicTrie 各ノードに「一つ目の子ノードの ID」，「兄弟ノードが存在するか」，「ラベル」を持たせたトライ 兄弟ノードが隣接するように配置 探索時，子ノードを線形探索して移動先を決定 TernaryTrie BasicTrie の各ノードに「子ノードの数」を加えたトライ 探索時，子ノードを二分探索して移動先を決定 DaTrie ダブル配列によるトライ 探索時，ラベルにより移動先を一意に決定 SuccinctTrie 「一つ目の子ノードを左の子」，「兄弟ノードを右の子」とする二分木に
GHMM: General Hidden Markov Model library
The General Hidden Markov Model library (GHMM) is a freely available C library implementing efficient data structures and algorithms for basic and extended HMMs with discrete and continous emissions. It comes with Python wrappers which provide a much nicer interface and added functionality. The GHMM is licensed under the LGPL. Defining a HMM with two states which output either heads or tails (thin
3日で作る高速特定物体認識システム (2) SIFT特徴量の抽出 - 人工知能に関する断創録
3日で作る高速特定物体認識システム (1) 物体認識とは（2009/10/18）の続きです。 今回は、画像からSIFT (Scale-Invariant Feature Transform) という局所特徴量を抽出するところを作ってみようと思います。 SIFT特徴量の抽出 まずは、局所特徴量の代表ともいえるSIFTを試してみます。OpenCVにはSIFTを抽出する関数がなかったのでRob Hess氏がC言語で実装したライブラリを試してみます。内部でOpenCVを使っているので事前にOpenCVのインストールが必要です。実装はOpenCV 1.1でされているみたいですが、2.0でもちょっと手直しすると動きました。Rob Hess氏のホームページからSIFT Feature Detectorのzip版を落とします。 （注）Hess氏のサイトが更新されたようで現在はGitHub上のOpenSIF
Suffix Arrays の構築がいつまでたっても終わらない問題
Suffix Arrays の構築がいつまでたっても終わらない問題 2009-10-20-4 [Algorithm] よくあるトラブルなのでまとめておく。 suffix を文字列比較でソートするという単純な方法で Suffix Arrays を作るSUFARYでのトラブルについて。 - SUFARY 臨時復旧ページ http://ta2o.net/tools/sufary/ ちなみに Suffix Array の作成ロジック（もっとも簡単なやつ）はこんな感じ(C言語です)： #include <fcntl.h> #include <malloc.h> #include <stdio.h> #include <sys/mman.h> #include <sys/stat.h> #include <sys/types.h> /* usage: sufsort1 text > text.suf
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
ボロノイ図いろいろ - kaisehのブログ
Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。 マンハッタン距離にもとづくボロノイ図 ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。 加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram) 母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。 加法的重み付きべき乗ボロノイ図 (Additivel
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Consistent Binary Tree Layout(2) - agwの日記
Consistent Binary Tree Layout(3) - agwの日記
加藤 和彦 Kazuhiko KATO, Dr. Prof.
Amazon.co.jp: Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて―: Amy N.Langville (著), Carl D.Meyer (著), 岩野和生 (翻訳), 黒川利明 (翻訳), 黒川洋 (翻訳): 本
