超高速テキスト処理のためのアルゴリズムとデータ構造 (PDF)
超高速テキスト処理のための ゕルゴリズムとデータ構造 東京大学情報理工学系研究科* 岡野原 大輔 hillbig@is.s.u-tokyo.ac.jp NLP2010 チュートリゕル 2010 3/8@東京大学本郷キャンパス * 2010年4月から所属が （株）プリフゔードンフラストラクチャーになります。 内容 • 背景 – 自然言語処理と機械学習 • オンラン学習 – 教師有/無, 正則化 • 疎ベクトル々文字列データ構造 – 特徴情報の格納、全部分文字列情報 • 乱択化ゕルゴリズム – Hash Kernel, Randomized SVD 背景 大規模自然言語処理と機械学習 背景 • 利用可能な言語資源の急激な拡大 – ブログ, 掲示板, 商品情報, レビュー – Wikipedia, Google N-gram Corpus ～1010 語 – c.f. Penn TreeB
bayonやCLUTOが爆速な理由 - download_takeshi’s diary
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。 うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。 きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。 このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほど
次元が高い場合に関してのsimhashの計算 - tsubosakaの日記
最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。 ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。 解説 simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビット
Locality Sensitive Hashing に挑んでみた - download_takeshi’s diary
久々のエントリです。 Locality Sensitive Hashing を perl で使うためのモジュールを書いてみました。Algorithm::LSHと名付けました。 先ほどDeveloper ReleaseとしてCPANにあげましたが、反映されるまで時間かかるので、興味ある方はcodereposからみてください。 Algorithm::LSH CPAN: http://search.cpan.org/~miki/Algorithm-LSH/ coderepos: http://coderepos.org/share/browser/lang/perl/Algorithm-LSH 超アルファバージョンな状態ですが、そのうちgithubにもupする予定。 そうそう、そう言えば WEB+DB PRESS Vol.49 にレコメンドエンジンの特集があって、その中に偶然にもLocality
Affine-SIFT (ASIFT)
SIFT and ASIFT --- online demo : try if your images match! Jean-Michel Morel Guoshen Yu morel[AT]cmla.ens-cachan.fr yu[AT]cmap.polytechnique.fr News: The ASIFT source code and online demo are now published in the journal IPOL! 2011.02.24 News: frequently asked questions on ASIFT. --- 2009.11.22 Summary: A fully affine invariant image comparison method, Affine-SIFT (ASIFT) is introduce
k-means++を試し中 - のんびり読書日記
http://d.hatena.ne.jp/kaiseh/20090113/1231864089 上の記事を見て、k-means++が面白そうだったので、ちょっとだけ試してみた。 k-meansは初期値に大きく依存するところが嫌い。初期値への依存度を軽減するために、初期値を変えて何回か試行してその中で一番良い結果のものを使用する、なんてことをしないといけない。そのため処理時間も馬鹿にならなくなってしまうので、ちょっとこれじゃあなあ…ということで使ってなかった。 でも今回のk-means++は初期値をうまく求めることで、精度と速度の向上が得られるらしい。これはうれしい！ 論文著者のページにサンプルコードがあったので試してみようと思ったんだけど、MFCを使っているみたいで僕の環境ではコンパイルできず…。 http://www.stanford.edu/~darthur/kMeansppTest
DO++: AND検索の最尤推定
検索技術においてAND検索、つまり二つの単語を指定して、それが両方出現している文書数の推定を高速に行うのは難しい問題です。 問題を正しく書くと単語w_xが出ている文書番号(x1,x2,x3,..,xn)とw_yが出ている文書番号(y1,y2,y3,...,ym)が与えられたら | {(i,j)|x_i = y_j} | の数を求める問題です。 これは前もって全通り求めて保存しておくにも単語種類数の二乗のオーダー分必要なのでできません。 これは機械学習でも特徴関数が0/1の値しかとらないとき、二つの要素の特徴ベクトルの内積を求める問題と同じで、またデータベースでもJOINの順番を決めるときにでてくる問題です。 普通は全体の文書からサンプルをとって、その中で数えてみて、それを元のサイズにスケールさせることをします。例えば全体文書1億件の中から文書1000件だけとってきて、その中でw_xとw_y
DO++ : 部分文字列の話
ここしばらく、部分文字列の統計量を利用した機械学習やデータマイニングをやっている。そこの話からちょっと抜粋。 長さnの文字列T[1,...,n]が与えられた時、T中に出現する部分文字列T[i...j] (1≦i≦j≦n）の数はn個の中からiとjの2箇所を選ぶのでO(n^2)個ある。例えば、n=10^6(1MB)だったら、部分文字列の数は約10^12個(1T)と非常に大きい。 しかし、これらの部分文字列の出現位置は同じである場合が多い。例えばT="abracadabra"であれば、"abra"と"abr"の出現場所は1番目と8番目であり、全く同じである。 では出現位置（部分文字列の左端を出現位置とする）が全く同じであるような部分文字列をまとめてグループにした場合、グループの数はいくつになるのだろうか。 これは接尾辞木（wikipedia 授業の資料）を知っているなら簡単に説明できる。 Tに対
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
オンラインEMアルゴリズム - DO++
EMアルゴリズム（Expectation Maximizationアルゴリズム、期待値最大化法、以下EMと呼ぶ）は、データに観測できない隠れ変数（潜在変数）がある場合のパラメータ推定を行う時に有用な手法である。 EMは何それという人のために簡単な説明を下の方に書いたので読んでみてください。 EMのきちんとした説明なら持橋さんによる解説「自然言語処理のための変分ベイズ法」や「計算統計 I―確率計算の新しい手法 統計科学のフロンティア 11」が丁寧でわかりやすい。 EMは教師無学習では中心的な手法であり、何か観測できない変数を含めた確率モデルを作ってその確率モデルの尤度を最大化するという枠組みで、観測できなかった変数はなんだったのかを推定する場合に用いられる。 例えば自然言語処理に限っていえば文書や単語クラスタリングから、文法推定、形態素解析、機械翻訳における単語アライメントなどで使われる。
「確率モデルによるwebデータ解析法」8章メモ - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
昔書いたやつを発掘してきた。また読み返す必要があるなー。 8章は商用アプリケーションの話、レコメンダシステムと顧客行動解析。 ここで扱うレコメンダシステムは、ユーザの行動履歴に基づきユーザに対してアイテムを推薦するようなもの。 興味深い問題として、欠損をすべて0と考えた場合、ユーザiがチェックしなかった項目jに関する行列V中の欠損地の扱いがある。これら欠損データは、必ずしも完全にランダムに欠損しているわけではなく、ユーザが好まない項目に対して「どちらかといえば選ばない」という負のバイアスが 影響していると思われる(Breese,J.S.,Heckerman,D. and Kadie,C. 1988 Empirical analysis of predictive algorithms for collaborative filtering.)。リコメンダシステムに関する多くの研究において、
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
Perlでアニメ顔を検出＆解析するImager::AnimeFace - デー
というのを作ったので自己紹介します。 2月頃から、コンピュータでアニメ顔を検出&解析する方法をいろいろ試しつつ作っていて、その成果のひとつとして、無理やり出力したライブラリです。 はじめに はじめにざっとライブラリの紹介を書いて、あとのほうでは詳細な処理の話を僕の考えを超交えつつグダグだと書きたいと思います。 Imager::AnimeFaceでできること Imager::AnimeFaceは、画像に含まれるアニメキャラクター的な人物の顔の位置を検出し、さらに目や口など顔を構成する部品位置や大きさの推定、肌や髪の色の抽出を簡単に行うことができるライブラリです。 これらが可能になると、 画像から自動でいい感じのサムネイルを作成できる 動画から自動でいい感じのサムネイルを作成できる 自動的にぐぬぬ画像が作れる 自動的に全員の顔を○○にできる 顔ベースのローカル画像検索 など、最新鋭のソリューシ
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
アルゴリズムイントロダクション15章 動的計画法
日本情報オリンピック (JOI) の主催する、 JOI 2021 夏季セミナーでの講義資料です。 拙著『問題解決力を鍛える！アルゴリズムとデータ構造』 の 5.6 節に相当する内容を掘り下げた講義です。 「区間分割の仕方を最適化する動的計画法」を題材として、さまざまな問題に対して汎用的な見方をする数理工学の考え方を紹介しました。
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
衝突判定編
論文 頻出パターン発見アルゴリズム入門 － アイテム集合からグラフまで －
はてなブログ | 無料ブログを作成しよう
