乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development吉田です。相変わらず乱択アルゴリズム紹介ということで、今日はBloom Filterの話をしたいと思います。今までと違うのはBloom Filterはある問題を解くアルゴリズムではなくデータ構造であるということです。データ構造に乱数を導入するとどういうことが出来るようになるか見てみましょう。
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
『MPJoin を使った類似データ抽出 ―アルゴリズムシリーズ 1―』
Hattori です。以前書いた記事の冒頭 で、”今度はシリーズで何かエントリを書きたい ! ”と軽いノリで一文を表記しておいたら、ホントにやることになりました。 弊社のエンジニア組織の特徴のひとつに、手を上げる・声を上げると、『じゃ、やってよ。』というノリで返ってくるという事が挙げられるのですが、今回もその例に漏れなったわけですね・・・。シクシク・・・。 というわけで、何を書こうかなぁって話しなんですが・・・。私の場合アルゴリズム系の話しかできそうにないので、毎回ポツポツとマイナーで極一部の人にしかウケないテーマを紹介して行こうと思います。 で、初回の今回は SimilarityJoin 関連のアルゴリズムで "MPJoin" というやつを紹介したいと思います。 ■ Similarity Join とは何ぞや？ まず最初に SimilarityJoin [1] の定義なんですが、ざっくり
機械学習/MacでSVM-Lightを使う - とうごろうぃき
インストール † 展開するときにディレクトリーを作ってくれないので注意しましょう． mkdir svm_light mv svm_light.tar.gz gunzip -c svm_light.tar.gz | tar xvf - make all gunzipの-cオプションは圧縮ファイルをそのままにして伸張した結果を標準出力に書き出すもので，tarの引数-は標準入力から入力されたファイルを展開するものです． これだとコンパイルだけで，パスを通さないと使えません． パスが通っているところにコンパイルされたファイルを移動させると，いつでもターミナルから実行できるようになります． sudo mv svm_learn svm_classify /usr/local/bin make clean 最後のmake cleanは不要になったファイルを消すためのオマケです． コンパイルでできたファイ
Web本文抽出 using crf
10. ExtractContentのアルゴリズム概略 • html をブロックに分割 • ブロックごとにスコアを計算 – 句読点が多い – 非リンクテキストが長い – 本文っぽくないフレーズが含まれている • 連続するブロックを「大ブロック」にまとめる – スコアの高いものをつなげていく – スコアが低いとつながる確率は減衰していく • スコアが最大となる「大ブロック」が本文 • 「ヒューリスティック」と言えば聞こえがいいが – 思いつきのアイデア＋感覚による調整 11. ExtractContentのコード(抜粋) module ExtractContent # Default option parameters. @default = { :threshold => 100, :min_length => 80, :decay_factor => 0.73, :continuous_
機械学習 × MapReduce - ny23の日記
個人的な興味というより，雑用絡みで眺めた論文の紹介．機械学習アルゴリズムを並列分散化するという話が最近流行っているようだ．全然網羅的ではないけど，誰かの役に立つかも知れないので，幾つかメモしておく．まず古典的にはこれ， Map-reduce for machine learning on multicore (NIPS 2006) 古典的な機械学習アルゴリズム（バッチ学習）の多くは，Statistical Query Model で記述できて，それらは summation form で記述できる (から，MapReduce で並列化できる)．実装は Mahout．ただ最近は，バッチアルゴリズムで解ける問題には多くの場合対応するオンラインアルゴリズムが提案されていて，バッチアルゴリズムを並列化することのメリットはあまり無い．オンラインアルゴリズムだとパラメタが連続的に更新されるので，MapR
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック：最強最速アルゴリズマー養成講座（1/3 ページ） 競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。 教育的な観点から見るTopCoder 今回からTopCoderに関する実践的アルゴリズムを解説していく予定でしたが、序盤のうちに触れておきたいことがありましたので、今回の枕は“教育的視点から見るTopCoder”というテーマで少し書こうかと思います。 まず、最初に宣言しておきたいことは、この連載は初心者向きである、ということです。「どう考えても上級者向けだろう」という意見はたくさんの方から寄せられていますが、筆者は、まだプログラミングレ
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
Confidence Weighted Linear Classificationを読んだ - 射撃しつつ前転 改
ICML2008で発表されたDredzeらのConfidence Weighted Linear Classificationを読んだ。これは線形分類器を学習する新しいオンライン学習型アルゴリズムの提案である。すぐに使える実装としてはOLLというオープンソースのライブラリがあり、実際に良い実験結果が出ているようだ。 Confidence Weightedのアイデアは、よく出てくる素性に関しては一回の更新における数値の変更量を減らしてやり、あまり出てこない素性に関しては、一回の更新でぐっと値を変更してやろう、というものである。 こういった新しい更新方法を考案した動機を明らかにするために、Perceptronを使って、単語を素性として評判分類の学習を行うような問題を考えてみる。肯定的な評価のサンプルとして"I liked this author."というものがあったとすると、このサンプルの分類
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
Google Prediction API - Google Code
How do I start? Learn more about Google Prediction API. Request access. Try out the sample code. What is the Google Prediction API? The Prediction API enables access to Google's machine learning algorithms to analyze your historic data and predict likely future outcomes. Upload your data to Google Storage for Developers, then use the Prediction API to make real-time decisions in your applications.
くさもち研究室生活ブログだったもの LSHまとめ(1)
LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ． 近似最近傍探索とは，簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること． つまり，半径(1+ε)の点のうち，どれか1つでも探索できればおｋ． 言葉の意味そのままに最近傍探索(Nearest Neighbor)の条件を少し緩くした探索といえる． （実は，特徴ベクトルの次元がd=2の場合なら，ボロノイ図を使えば近似最近傍探索ができる） LSHはハッシュ関数を用いた確率的探索で近似最近傍探索を解く． そう，実はハッシュ関数を用いるということ以上に確率的探索ということに大きな意味がある．（これが自分にとってはかなりやっかいな問題） LSHでは，クエリqと近傍(半径(1+ε)以内)にある点ではハッシュ値が一致する確率が高く， クエリqと遠い位置にある点ではハッシュ値が一致する確率が低
lsh
2. ( 最 ) 近傍点探索 ( Nearest Neighbor Search) とは いわゆる、特徴空間内での類似データ探索 二種類の問題が考えられる 定義 ℜ d 空間上の点集合 P が与えられた場合 最近傍点探索 クエリ点 q に対し、 p∈P で、 ||p-q|| を最小とする点 p を求める問題 r- 近傍点探索 クエリ点 q に対し、 p∈P で、 ||p-q||<r となる点 p を ( 存在するのならば ) 列挙する問題 3. 近傍点探索問題 近傍点探索アルゴリズムは、以下のようなタスクにおいて利用される インスタンスベース学習(k-近傍法) クラスタリング データセグメンテーション データベース検索 最短経路木探索(Minimum Spanning Tree) データ圧縮 類似データ検索 4. 近傍点探索アルゴリズム 最も単純なものは、クエリ点 q と、 p∈P の点全
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>=...>=
LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出 - mixi engineer blog
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの
Better Bayesian Filtering ベイジアンフィルタの改善
ベイジアンフィルタの改善 --- Better Bayesian Filtering Paul Graham, January 2003 これは、Paul Graham： Better Bayesian Filtering を、原著者の許可を得て翻訳・公開するものです。 <版権表示> 本和訳テキストの複製、変更、再配布は、この版権表示を残す限り、自由に行って結構です。 (「この版権表示」には上の文も含まれます。すなわち、再配布を禁止してはいけません)。 Copyright 2002 by Paul Graham 原文: http://www.paulgraham.com/better.html 日本語訳：Shiro Kawai (shiro ＠ acm.org) <版権表示終り> Paul Graham氏のエッセイをまとめた『ハッカーと画家』の 邦訳版が出版されました。 出版社の案内ページ
本物と見違えるような画像補間を実現するパスフレームワーク手法 - A Successful Failure
SIGGRAPH2009で発表された"Moving Gradients: A Path-Based Method for Plausible Image Interpolation"という論文*1では、2枚の連続する入力画像を与えると、その間のフレームを極めて自然に補間生成する新たな手法を提案している。 図1 図1は両端の入力画像A, Bから間の3フレームを生成した例を示している。生成する補間フレーム数は任意で何枚でも生成可能であり、極めて自然な補間が実現できている。この例の驚くべきところは、制約条件を有する複雑で柔らかな局所変形を含む自然な補間画像が、全自動で生成されている点である。モーフィング処理では対応点を一点一点指定する必要があるが、ここで必要なのは2つの画像を選択するだけだ。 生成される補間画像の品質は素晴らしく、またアイデアもシンプルで興味深いので、原論文を参照して本手法の概要
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブックマークのシステムについて
ローカルサーチ vs 遺伝的アルゴリズム - アルゴリズムマニア2.0