Python Packages for Graph Cuts on Images
A graph for a small image of 512x512 pixels has 261144 nodes and 523264 edges in the 4-connected pixels case. Graphs in this scale require a fast construction interface. I reviewed a few python packages mainly from this perspective. The comparison is by no means exhaustive and fair! Based on Kolmogorov min-cut / max-flow C++ library original Kolmogorov’s code: http://vision.csd.uwo.ca/code/#Max-fl
"Efficient Graph-Based Image Segmentation"の手法と実装 - IrohaLog
記事概要 1. Felzenszwalbらの提案したEfficient Graph-Based Image Segmentation *1の手法と実装を解説 2. 手法：画像中の各画素を1つのノードとした木から、輝度が類似なノードをまとめていきセグメンテーションを行う 3. 実装：Union-Findを用いることでo(nlogn)となる Felzenszwalbらの提案したEfficient Graph-Based Image Segmentation を解説してみる。 画像のセグメンテーション*2は1枚の画像を同じような特徴(明るさ、色、テクスチャなど)を持つ複数の領域に分割する処理で、基本的な画像処理技術の1つである。画像合成処理、物体認識、ジェスチャ認識などの前処理として幅広く利用されている。 中でも、2004年にFelzenszwalbらが提案したEfficient Graph-B
近似ベイズ計算によるベイズ推定 - 捨てられたブログ
近似ベイズ計算 (approximate Bayesian computation, ABC) と呼ばれるベイズ的手法があります。近似ベイズ計算の「近似」たるゆえんは，複雑な尤度の計算を行わないために，近似計算を行うという点にあります。 そもそも，ベイズの定理は，事後分布 は事前分布 と尤度 の間に の関係が成り立つことを主張しています。尤度が一般に計算困難であることを考えると，事後分布を求めることはほとんどできなくなってしまいます。 ABC では， からデータ をシミュレーションし，データ間の距離 が 以下であれば許容することにしています。つまり， の代わりに からサンプリングを行えれば良いという考えです。なお，データ間の距離そのものを考えることは難しい場合は，統計量 を用いて とする場合もあります。 一般に ABC で用いられているフレームワークは次の 3 つです。 棄却サンプリング
2048のAIを書かなかった話。あるいは遺伝的プログラミングの話 - isEOL(@Angelworm_)
序 KMCでは2048のAIを作って戦わせるコンテストである「第一回2048AIコンテスト 結果報告 - KMC活動ブログ」が開催たそうですね。これを見て2048AIを私も作ってみたくなりました。 ところで、ボードゲーム上でAIとはおおよそ「勝率が最も高まる手を現在の状況を元に出力する」ものだと思います。チェスなどのゲームに置いて有名な「ミニマックス法」などは相手が最も自分に取って都合が悪い選択をして、自分が最高の選択をし続けた場合一番最初に選ぶべき最高の手を出力するアルゴリズムです。 このような次におこる状況を予測して手を決定するアルゴリズムは、探索アルゴリズムなんて呼ばれたりしています。 探索アルゴリズムを利用する上で大事なのは、読みの深さと評価関数の良さです。読みの深さとは、言葉の通りゲームの状況を何手先まで読む事が出来るかを表し、深ければ深いほどより大局的な戦い方が出来るようになる
EM アルゴリズム | パターン認識と機械学習
Andrew 先生の説明がとてもわかりやすかったのでメモです。カルバック・ライブラー情報量（KL divergence）を用いる事なく、イェンゼンの不等式のみで自然に展開していました。 凸関数 – convex function f’’(x) > 0、また x がベクトルの場合はヘシアン H >= 0 の時、f(x) は凸関数。f’’(x) > 0 とは x が大きくなるにつれ接線の傾き f’(x) も大きくなるということ。全ての x で、下図の (1) -> (2) -> (3) のような変化が成り立つ f(x) のこと。 イエンセンの不等式 – Jensen’s inequality f(x) が凸関数の時、E[f(x)] >= f(E[x]) が成り立つ。これがイェンゼンの不等式。 図を見れば直感的にわかるのだが、今仮に xは a,b の２点しか取れないとすると、f(E[x])より、
Sign in - Google Accounts
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
Atsushi TATSUMA Web Page » Python と OpenCV で手軽に近似最近傍探索をする
はじめに 近似最近傍探索は、その名のとおり、k-近傍探索の高速な近似手法です。 大量にあるデータから、検索クエリのk-近傍となるデータを、高速に探してくる技術です。 近似最近傍探索の有名ライブラリに、FLANN（Fast Library for Approximate Nearest Neighbors）があります。 FLANN 自体、独立したライブラリとして存在しているのですが、OpenCV にも組み込まれています。 しかも、OpenCV の Python インターフェースからも叩けます。 各ライブラリのバージョン Python から FLANN へデータを渡すには Numpy の行列オブジェクトを用います。 今回は、以下の環境で、実行を確認しました。Python、Numpy、OpenCV は独自にビルドしたものです。 Debian GNU/Linux 6.0.5 Python
PythonでPLSAを実装してみる
probabilistic latent semantic analysis (PLSA)は、 ・文書dがP(d)で選ばれる ・潜在変数zがP(z|d)で選ばれる ・語wがP(w|z)で生成される というプロセスを経て、結果として(d,w)のペアが観測されるという文書と語の生成モデル。 式で表すと (1) となる。P(d,w)の尤もらしい確率分布を見つけたい。対数尤度関数は (2) となる。n(d,w)は語wが文書dに出現する回数。この式は訓練データn(d,w)（;どの語がどの文書に何回出現したか）が尤もらしい確率分布P(d,w)に従うとき最大になる。ベイズの定理を用いると (3) となることを利用して、この尤度関数を最大化するためにEMアルゴリズムを用いて実装してみる。（過学習を回避するために文献ではTempered EM (TEM)を用いている。）尤度関数が収束するまで以下のE-ste
RでWAICを強引に計算させてみた - motivicのチラ裏
"R Advent Calendar 2013" 13日目の記事です。 どうも、13日の金曜日に記事を書くことになった幸運の持ち主のmotivicです。 先日WAICについてJapan.RでLTをしたので、まずはこちらをご覧ください。 RでWAIC from motivic ということで、WAICスゴイ！早速Rで強引に計算してみましょう。 渡辺先生のmatlabのコードはこちらから辿れます。 http://watanabe-www.math.dis.titech.ac.jp/users/swatanab/dicwaic.html 以下のRのコードはこれの昔のバージョンのものを翻訳したものです。ここでは混合分布のdelicate caseのWAICを計算しています。 研究室の高スペックなコンピュータでも計算するのに37分かかったので、普通のパソコンだと計算に数時間かかるかもしれません。 #T
ハミング距離の計算はホントに速いのか？
これは@sakanazensen君が主催する『Computer Vision Advent Calendar 2013』の12/8の記事です。今年はあまり活発でないようなので、小ネタですが参戦しました。 はじめに 昨今のコンピュータビジョン・パターン認識分野で特徴ベクトルのバイナリベースの記述法が流行っています。その利点の一つとして、特徴ベクトル間の距離としてコンピュータにとって計算が容易な「ハミング距離」が使える、というものがあります。これはXOR演算と PopCount演算（いくつのビットが1かをカウントする演算）で構成されており、特に近年のCPUにはまず搭載されているベクトル計算命令セットの一つ「SSE4.2」の専用命令「POPCNT」が高速演算の根拠としてよく引き合いに出されます。二つともかなりプリミティブな命令ですから確かに高速に計算できそうな感じはします。しかしながら、例えばL
PageRankアルゴリズムを使った人事評価実験 | 株式会社サイバーエージェント
2-2-1.一般的な360度評価による評価方法 問題点 一般的に評価プロセスが公開されていないため、最終評価までのプロセスが不透明である 全員が全員を評価するのは多数の社員がいる場合は不可能である ランダム抽出によるお互いの評価を行うと、まったく違う専門分野を評価したり、まったく関わりあいのない人を評価することになり精度が下がる 2-2-2.専門分野での評価者による評価方法 問題点 *評価者になる人材の不足 高い専門スキル、会社とのビジョンマッチ、メンバーからのその専門分野での高い信頼の全てを備えている人材が専門分野毎に必要。 さらに、評価の納得性を保つためにはメンバーからの信頼がある人材ではないと評価できない。 *評価者によって評価ポイントの違いがある 同じ分野の技術者でも、スキルの価値をどこに置いているかというスタンスの違いから評価ポイントにゆらぎが発生する。 さらに評価者自体
HyperLogLogで遊ぶ - Negative/Positive Thinking
はじめに 「さぁ、お前の罪の異なり数を数えろ！」と言われたときに使えそうな「HyperLogLog」という異なり数をカウントする方法を教えてもらったので、遊んでみた。 いつもながら論文ちゃんと読んでないので、条件やコード間違ってるかも。。。 HyperLogLogとは cardinalityと呼ばれる、要素の異なり数を決定する問題 かなり省メモリで精度のよい異なり数を推定できる方法 要素をそのまま保存せず、ハッシュ値に変換したものをうまくレジスタに保存しておく ので、レジスタサイズ程度しかメモリを使わない 並列化もできて、最近のbigdataとかで注目されている また、googleが並列計算用に改善したHyperLogLogを提案してるみたい http://blog.aggregateknowledge.com/2013/01/24/hyperloglog-googles-take-on-
ICML2013読み会を開催しました - Preferred Networks Research & Development
夏ですね。暑いですね。比戸です。 先月開かれた機械学習のトップ会議ICML2013の論文読み会を開催しました。本会議に参加したPFIメンバーがいたので、せっかくだからと外部公開にしたところ、想像以上の盛り上がりとなりました。 1週間前というかなり無理なスケジュールで募集をかけたにも関わらず、読む人枠は瞬時に埋まり、聞く人の数も予想を大きく超え合計40名と弊社オフィスでは収まらなくなったため、東大の中川先生にお願いして場所をお貸し頂きました。ありがとうございました。 平日夜18時から22時という時間にもかかわらず濃密なガチ発表が続き、とても有意義な情報共有・質疑が出来たのではないかと思います。ここ1-2年このような論文読み会の機会が減っていると感じていたので、今後も継続的に開催出来ればと思います。 発表者の皆さんもかなり資料をSlideshareに上げてくださったのでせっかくなのでここにまと
全点対間最短路(all-pairs shortest-path) - kanetaiの二次記憶装置
リポジトリ 計算結果（最短距離とバックポインタ） 最短経路はbuildPath()で復元。 /** Results of All-Pairs Shortest Path (APSP) Algorithm */ public static class APSPResult{ private int[][] dist; // dist[d]:= shortest path to d private int[][] prev; // back pointers private boolean hasNegativeCycle; public APSPResult(int[][] dist, int[][] prev, boolean hasNegativeCycle){ set(dist, prev, hasNegativeCycle); } final private void set(int
Real World Recommdnder - 現実世界の推薦システムにおける、精度と速度以外の話 -
自己紹介 d:id:gnarl twitter:todesking いちおう情報系 興味 プログラミング言語処理系 ソフトウェア・アーキテクチャ(オブジェクト指向設計とか) 機械学習(ニワカ) 推薦エンジンを作ってるチームに所属してます 最近の仕事: javaでニュース記事の特徴語を解析して云々 ruby+sinatraでなんかつくる仕事 アジェンダ(1) 推薦システムとはなにか 推薦システムの種類 コンテンツベース、行動ベース ユーザ-アイテム、アイテム-アイテム モデルベース、メモリベース この辺の話は皆さんのほうが専門家ですね…… 省略します アジェンダ(2) 推薦システムの精度をはかる MAE/RMSE Precision, Recall 推薦システムの抱える問題点 スパースネスの問題 コールドスタートの問題 この辺の話を長々とすると会場の研究者にしらけた顔をされる…… 省略します
SIGMOD'13 に論文採択 - iwiwiの日記
論文が国際学会 SIGMOD'13 (ACM SIGMOD International Conference on Management of Data) に採択されました．SIGMOD はデータベース分野のトップ会議です．日本からの論文は知る限り 5 年ぶりだと思います．修士の間の研究で，この厳しい戦いを勝ち抜き論文採択に至ることができ，本当に嬉しいです． 論文は "Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで，研究室同期の岩田と NII の吉田さんとの共同研究です． 内容について 扱っている問題は前回の EDBT 論文と同じく，大規模ネットワーク上の最短路クエリです．グラフに対し，ある程度の前計算データを蓄えておく事により，2 点間の最短
Sign in - Google Accounts
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
p-Stable LSHをC++11でさっくり実装 - nyanp::blog
高次元の特徴量を持ったベクトルの集合に対して，与えられたクエリベクトルに似ているものを探し出すという問題を，近傍探索とかいう．旧来のkd-treeあたりを使った探索ではなく，近似的に近いベクトルを探す近似近傍探索が流行っている（らしい）．近似近傍探索のひとつ，LSHの説明を読んでたら「これ案外簡単に実装できるんじゃね？」と思い至ったので，C++11で書いてみた． LSHについては以下の説明がとても分かりやすい． 060108 Locality-Sensitive Hashingの実装が一段落 - 飛行船通信 - Seesaa Wiki（ウィキ） 他には以下を実装の参考にした． lsh p-stable 最近のバイナリハッシングをいくつかJavaで実装してみた - るびゅ備忘録 Locality Sensitive Hashing - (setf yaruki nil) - nlpyutor
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://www.smapip.is.tohoku.ac.jp/~smapip/2003/tutorial/textbook/koji-hukushima.pdf