EMアルゴリズムによる混合分布のパラメーター推定の解析計算＆実装例 from 「Rによるモンテカルロ法入門」 - My Life as a Mock Quant
問題設定 R言語の書籍「Rによるモンテカルロ法入門」 のEMアルゴリズムに関連した「練習問題5.14」をpthonの練習がてらEMアルゴリズム構築までの数式もメモりながら解いてみたというお話。問題設定としては という混合分布(分布から確率、分布から確率でサンプリング)から個サンプリングした状況を考えて、このパラメーターをEMアルゴリズムで推定するというもの。機械学習の分野でいう所の「教師なし２クラス分類」に該当する（たぶん）。 グラフを使ってもうちょっとちゃんと説明しておくと、実際に観察された青い棒グラフで示されているデータは赤色のグラフで示されているからのサンプルなのか、それとも緑色のグラフで示されているからのサンプルなのかを識別するための閾値的な量になっているというパラメーターを推定してましょうと、そして、既存のデータはのどちらの分布から来た可能性が高いのかを判断しましょうとそういう問
画像処理におけるアルゴリズム
ここでは各画像処理におけるアルゴリズムを簡単に解説する。 2値化 明るさ調整 色成分の抽出 色反転 コントラスト調整 切り出し ガンマ補正 グレイスケール化 増色 画像枠付加 鏡像反転 ノイズ除去 輪郭抽出 輪郭追跡 拡大縮小 任意角回転 セピア調化 ぼかし 2値化 指定画像を白と黒の2階調の画像に変換する処理であり、本研究で作成した2値化処理は単一手動閾値方式、P-タイル法、また、誤差分散法およびその拡張型である Floyd&Steinberg 型誤差分散、Jarvice,Judice&Ninke 型誤差分散の5つである。 次にそれぞれのアルゴリズムについて解説する。 単一手動閾値方式 指定された色深度を基準として、その値より入力画素の色深度値が明るければ白、暗ければ黒色として2値化する。下の式を用いている。 このとき、出力画像は初期状態で黒色となるので、入力画像の画素値が閾値以
Lanczos拡縮アルゴリズムの実装 - GIOの日記
原理 画像の拡大縮小アルゴリズムはいくつか存在します ・ニアレストネイバー ・バイリニア ・バイキュービック ・Lanczos-2 ・Lanczos-3 この中で理論上最も美しいとされているのはLanczos-3であり、漢はだまってこの方法を選ぶべきなのですが、いくつかの実装では正確な計算がされておらず、もったいない事になっています。 なので今回はできるだけ正確な高品質な画像を目指して実装してみました。 rubyで。 原理的なものはコチラが詳しいです。こんなブログを見るよりお勧め http://gwaihir.hp.infoseek.co.jp/wiki.shtml?Lanczos%E9%96%A2%E6%95%B0%E3%81%AB%E3%82%88%E3%82%8B%E7%94%BB%E5%83%8F%E3%81%AE%E6%8B%A1%E5%A4%A7%E7%B8%AE%E5%B0%
WWW2012で発表された3つの Twitter 関連論文のまとめと考察 | ぱろすけのメモ帳
気づいたら7月が終わってたんですがこれが相対論的効果ですかね。 4月が8本、5月が17本、6月が7本でした。そして今月は、驚きの3本！ 東京大学制作展なるイベントで1週間ほど吹き飛んで、そのあとレポートで1週間吹き飛んで、論文の書き直しやって、体調崩して1週間吹き飛んで、まあこんなもんですよね。 反省しています。 さらには、今月は「知能情報論に関する一流学会・一流雑誌の論文を3本以上読め」ってレポートに関連して読んだものしかないんですね。だったらレポート自体をブログに乗っければいいんですよね。 なので以下は実際に提出したレポート（を一部改変したもの）です。恥ずかしいですね。 知能情報論に関連する，一流雑誌もしくは会議の英語論文を三本以上読んで， その論文の概要 それらの論文を貫く考え方 をA4 で4ページ以内にまとめよ。 対象とする論文の選出 今回は、自分自身の知識領域を広げるため、自分の
Googleがスパムを特定する新アルゴリズム ｜SEO Japan by アイオイクスSEO Japan｜アイオイクスのSEO・CV改善・Webサイト集客情報ブログ
今年に入ってからアルゴリズム更新が激しいGoogleですが、最近スパムを特定するための新たな特許を取得したらしい、ということで詳細をSEO by the Seaから。 — SEO Japan グーグルのウェブマスターガイドラインは、ウェブマスターに警告を与える対象として、欺くことを意図して検索結果のランキングを上げようとする複数の取り組みを挙げている。このガイドラインは冒頭で次のように警告を発している: ガイドラインの提案項目を導入しないサイトでも、「品質に関するガイドライン」には目を通されますようお願い致します。このガイドラインでは、Google のインデックスから完全に削除されるか、アルゴリズムまたは手動によるスパム対策が実施される可能性のある不正行為について説明しています。スパム対策が実施されたサイトは、Google.co.jp や Google のパートナー サイトの検索結果に表示
DSIRNLP#03でウェーブレット木について発表しません！ - EchizenBlog-Zwei
9/30(日)に開催予定のDSIRNLP#03でウェーブレット木について発表しません。 なんで発表しないかというとウェーブレット行列というウェーブレット木の上位互換であるまじぱないデータ構造について話すからです。 ウェーブレット木がわからないとウェーブレット行列もわからないんじゃないの？と思われるかもしれませんが、その逆でウェーブレット木では必要以上に難しく考えていたことを「それ、もっと単純に出来るよ」っていうふうに見方を変えたのがウェーブレット行列です。 ウェーブレット木を知らない人はむしろウェーブレット行列から入ったほうが近道です。 なのでDSIRNLP#03ではウェーブレット木については発表しません。発表予定だった資料は以下のURLで公開していますので興味ある方は参考にどうぞ。 よくわかるウェーブレット木
ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix" - EchizenBlog-Zwei
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。 これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
PRML復々習レーン#3に参加して発表しました - シリコンの谷のゾンビ
PRML復々習レーン#3に参加して発表しました．会場係と会場を提供してくださった@showyouさんとDeNAさんに感謝申し上げます．毎度ながら素晴らしい会場，そして素晴らしい景色． 今回から新しい試みで前回の復習内容をまとめてみることにしてみた．いちsubsectionを1枚程度にまとめて，「よーするに」というポイントをまとめてみたもの．資料をまとめて喋ってみてはじめて気が付くことがあったので次回もぜひやってみたい． 発表資料は以下のとおり 前回までのあらすじ PRML復々習レーン#3 前回までのあらすじ View more presentations from sleepy_yoshi 3.1.3-3.1.5 (代打) PRML復々習レーン#3 3.1.3-3.1.5 View more presentations from sleepy_yoshi 日程の都合で今回参加できない方の代
JavaScriptによるパーセプトロン/Passive-Aggressive体験デモ - シリコンの谷のゾンビ
前回k-NNデモを作った後に「これパーセプトロンも同じようにデモ作れるんじゃね?」と思ったので実装してみた．今度はクリックでデータ点を追加できるようにしたり，サンプル選択方法を可変にしたり，PAの更新の様子を可視化すると面白いかもと思って後からPAも追加してみた． パーセプトロンは誤分類するサンプルを正しく分類するように超平面を更新する線形識別器で，Passive-Aggressive (PA) は損失を発生させるサンプルに対して損失が0になり，重みベクトルの変化量が最小になるように超平面を更新するアルゴリズム． オンライン学習についてざっくりした俯瞰は以下の資料などをご参照． TokyoNLP#5で「パーセプトロンで楽しい仲間がぽぽぽぽ〜ん」を発表しました というわけでk-NNと同じように公開． Perceptron/PA Demo ver.1.0 使い方 Update onceボタンで
The Anatomy of Large-Scale Social Search Engine: ソーシャル検索エンジンAardvark論文の輪講用資料 - シリコンの谷のゾンビ
巷 (もしかしたら非常に一部?) を騒がせているWWW2010に採択されたソーシャル検索エンジンAardvark論文 "The Anatomy of Large-Scale Social Search Engine" を読んで，ここ3日間ほど夜なべをして作成した輪講用資料を公開します．普段読まない類の論文だったので色々大変でしたが，非常に勉強になりました． ちょうど論文を読んだ頃にGoogleによる買収が正式発表になったので非常にタイムリーなネタとなりました． The Anatomy of Large-Scale Social Search EngineView more presentations from sleepy_yoshi. 論文や資料を見ればわかるとおり，個々の技術はオーソドックスな技術の組み合わせになっています．それを組み合わせてひとつのサービスという形で提供し，更に実際の
高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
svartalfheim.jp - 配列を少ない仕事量でシャッフルするFisher-Yates法
Fisher-Yates法は配列をシャッフルする際に用いる一般的なアルゴリズムのようです。 Wikipedia：Fisher-Yates法（英語） Javascriptで書くと（Wikipediaより抜粋） var n = a.length; for(var i = n - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var tmp = a[i]; a[i] = a[j]; a[j] = tmp; } ActionScript（jp.ferv.blogさんより） var i:int = array.length; var j:int,tmp:Object; while(i){ var j = Math.floor(Math.random()*i); var tmp = array[--i]; array[i]
なぜBTreeがIndexに使われているのか - maru source
この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル 1 2 3 4 5 CREATE TABLE user ( id INT UNSIGNED NOT NULL AUTO_INCREMENT, name VARCHAR(255) NOT NULL, PRIMARY KEY (id) )ENGINE=InnoDB; idカラムにIndex(PRIMARY KEY)を張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラム
[JavaScript] Nクイーン問題（ノンプリエンプティブマルチタスク風）
有名な Nクイーン問題を解く JavaScript です。 アルゴリズムは、単純なバックトラックのみです。 ブラウザの動作をロックせずに、 処理状況をアニメーション表示させている点がミソです。 ノンプリエンプティブマルチタスク風に定期的に処理をブラウザ側に返すようにクラスを組むことで、 複数の処理を並列動作させる習作です。 盤の大きさ（デフォルトは8マス＝8クイーン問題）を入力して、[開始] ボタンを押して下さい。 盤の大きさ： マス 0 個の解を検出しました。 [開始] ボタンを押して下さい。 アルゴリズム 深さ優先で、単純なバックトラックのみを使用しています。 また、再帰呼び出しもせずに、ぐるぐるループしています。 とりあえずなので、解の回転／反転すら使っていません。 試してませんが、JavaScript でビットマックを作ってマッチングさせると遅くなりそうですね。 上下反転くらいなら
文字列データ圧縮ことはじめ | SlideShare
2012/6/21のPFI全体セミナー, 「文字列データ圧縮ことはじめ」の内容です。データ圧縮の話とそれに纏わる歴史と最近の話を紹介しています。
平方根を使わずに高速で２点間の距離を近似する - きしだのHatena
２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え
綱引きに蛇口当てゲーム？！ 楽しく学ぶベイズフィルターの仕組み
付き合いたくないスパムと付き合うために 受信者の意向を無視して、一方的に送りつけられる迷惑メール（スパム）は、いまやメールボックスを雑音でいっぱいにしてしまい、大事なメールを見過ごしかねないほどの量に膨れ上がり、大きな問題となっています。 残念ながら、このようなスパムを発生源から断つような根本的な対策はいまだになく、私たちは、せめてメールサーバで受け取った大量のメール群からスパムと大事なメールを仕分けしてくれる仕組みに頼らざるを得ません。 スパムを判定する方法は、次の2つに大別することができます。 本稿では前者の方法に着目します。メールを受け取った人にとっては、メールの中身を読めば、そのメールがスパムかそうでないかを判定するのは容易なことです。スパムの定義は、メールを読む人によって変わる可能性があります。例えば、まったくゴルフをしない人にゴルフの勧誘メールが来た場合はスパムといえるでしょう
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Technical documentation
転置インデックスとTop k-query
プログラミングコンテストでの乱択アルゴリズム
