Markov chains, named after Andrey Markov, are mathematical systems that hop from one "state" (a situation or set of values) to another. For example, if you made a Markov chain model of a baby's behavior, you might include "playing," "eating", "sleeping," and "crying" as states, which together with other behaviors could form a 'state space': a list of all possible states. In addition, on top of the
勤務先の社内勉強会で、機械学習を用いた文書推薦*1に関する基本的なことがらについて説明しました。その資料を公開します。 プログラマのための文書推薦入門 from y-uti 数学やコンピュータサイエンスを専門的に学んでいないエンジニアでも理解しやすいように、できるだけ数式を使わずに説明したつもりです。厳密性にはこだわっていないので、専門家からはあちこちツッコミを受ける内容かもしれません。 プログラマ向けということで、実際にコンピュータ上で動作を確認できるように、Wikipedia のデータを対象にして類似文書検索を行うスクリプトを作成しました。GitHub に置いてあります。 y-uti/document-recommendation · GitHub *1:推薦というより情報検索、類似文書検索という方が適切だったかもしれません。
どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから
EMアルゴリズムはいろんなところで使われます。 基本的には未知パラメータの推定方法の一種です。 とりあえず箇条書でまとめます。 提案論文：Maximun likelihood from incomplete data via the EM algorithm. Dempster AP, Laird NM and Rubin DB. JRSS B. 39,1-38. 1977. 提案者のRubinは欠測分野、因果推論の権威で次の教科書も書いています。 Statistical Analysis with Missing Data (Wiley Series in Probability and Statistics) 作者: Roderick J. A. Little,Donald B. Rubin出版社/メーカー: Wiley-Interscience発売日: 2002/09/09メディア:
講義資料を全世界に向けて無償で公開し、最高水準の理工系教育を全世界の共有財産とすべく提供するプラットフォームです
(株)永和システムマネジメント 平鍋健児 作成日：初版 1999, 3/16 第2版 2002, 11/6 第3版 2004, 9/14 第4版 2008, 5/1 情報処理技術社試験の中で良く出て来る「待ち行列」理論を，直感的に覚えやすく解説してみました． 何度もトライしたけど待ち行列が理解できない人向けです． 正確な定義や論理展開は重視せず，いかに効率的にこの理論を覚えることができるかに焦点を絞ってみました．
Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう？と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き
2010年は、パターン認識と機械学習（PRML）を読破して、機械学習の基礎理論とさまざまなアルゴリズムを身につけるという目標（2010/1/1）をたてています。もうすでに2010年も半分以上過ぎてしまいましたが、ここらでまとめたページを作っておこうと思います。ただ漫然と読んでると理解できてるかいまいち不安なので、Python（2006/12/10）というプログラミング言語で例を実装しながら読み進めています。Pythonの数値計算ライブラリScipy、Numpyとグラフ描画ライブラリのmatplotlibを主に使ってコーディングしています。実用的なコードでないかもしれませんが、ご参考まで。 PRMLのPython実装 PRML読書中（2010/3/26） 多項式曲線フィッティング（2010/3/27） 最尤推定、MAP推定、ベイズ推定（2010/4/4） 分類における最小二乗（2010/4/
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
移転しました http://please-sleep.cou929.nu/20100708.html
蟻コロニー最適化の概念図 蟻コロニー最適化（ありコロニーさいてきか、Ant Colony Optimization、ACO）とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー（＝群れ）から食物までの経路を見つける際の挙動からヒントを得たものである。 実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。 しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発す
相当、出遅れた感はあるが、以下の試験問題をやってみた。（Rubyで） さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************という入力に対し、 **************************
JAVAでデータマイング！ 『情報工学の難しいそうなアルゴリズムをJAVAで実装して、ひたすらその結果を公開する』ブログになる予定。 PR Calendar <<March>> S M T W T F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Theme NaiveBayes ( 2 ) スムージング ( 0 ) はじめに ( 1 ) 計算テクニック ( 0 ) 外れ値除去 ( 0 ) LSH ( 4 ) 協調フィルタリング ( 0 ) ブースティング ( 0 ) Kmeans ( 0 ) 階層的クラスタリング ( 2 ) EMアルゴリズム ( 0 ) BM ( 0 ) SVD ( 0 ) PLSI ( 0 ) LDA ( 0 ) パーセプトロン ( 0 ) A
たとえば、複数の信号源があって、そこから毎回確率的にどれかの信号源が選ばれて発生されるデータを観測することを考えます。 ただし観測されたデータは、どの信号源から発生されたかはわからないとします。 また、データにはノイズがのっているなど、各々の信号源も確率的な挙動を示すことにしましょう。 このとき、観測できるデータだけから、確率モデルでモデル化した信号源（と信号源の混ざり具合）のパラメータ同定を行う手法として、以下で説明するEMアルゴリズムを利用することが出来ます。 観測データを \(X\) 、観測できないデータは特に隠れ変数と言い、\(Y\) とします。 どちらも確率変数です。 \(Y\) は上の例で言えば信号源のインデックス（どの信号源が選ばれたか）になります。 観測データと隠れ変数を合わせた \(Z=(X,Y)\) を完全データと言い、システムの全ての確率変数となります。 また便宜
混合正規分布について 混合正規分布のEMアルゴリズムによるパラメータ推定 EMアルゴリズムの単調増加性について この前はEMアルゴリズムがどんな感じのメカニズムで、どんな性質を持っているか簡単に書いた。 初めてのEMアルゴリズム - yasuhisa's blog というわけで、ちょちょいとRで書いてみることにした。お題はありがちな混合正規分布。 混合正規分布について確率変数がにがで、それぞれ0.3、0.7で生成されているというような分布が真の分布だとしよう。図で書くとこんな感じの密度関数である。 図を書くためのRのスクリプト。 mixture_gaussian <- function(x) { pi_0 <- 0.3 ifelse(runif(1) < pi_0, rnorm(1, -5, 1), rnorm(1, 5, 4)) } N <- 1000 x <- sapply(1:N,
組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP） コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各
Quicksilverの検索性能が、感性をくすぐってきた。 「apple」→「AppleScript Editor」 「ase」→「AppleScript Editor」 「prol」→「Property List Editor」 「im」と入力して、「Image Capture」を起動したいが、「iMove」がトップヒットになってしまう...。 そんな状況でも、候補リストから2回連続で「Image Capture」を選択すれば、3回目以降は「Image Capture」がトップヒットになる。 直近のユーザーの好みを学習してくれるのだ。 もちろん、「ima」まで入力すれば「Image Capture」がトップヒットになる。 「ase」「prol」のような、単純な前方一致でも、部分一致でもない検索には恐れ入る。しかも、シンプルだけど学習もしてくれる。使うほどに手に馴染んでくる仕組みは、この辺
< ---- < | > Naive Bayesの罠 > ================================================ Naive Bayes(NB,ナイーブベイズ)の実装についてメモ。 NBというのはベイズ則に基づく単純な分類器で lnP(Ci|D) = Σj{lnP(wj|Ci)} + lnP(Ci)で文書DがクラスCiに属する確率が得られるよ、というもの。(以下、Σiで添字iのすべての場合についての足し合わせを表す) これを実装する場合、まず手元にデータ集合を用意する。データ集合はクラスラベル(Ci)の付けられた単語(wj)、つまり(Ci,wj)のペアの集まり。例えば (甘い,りんご) (甘い,りんご) (甘い,りんご) (甘い,ハチミツ) (甘い,ハチミツ) (甘い,バナナ) (甘い,砂糖) (甘い,カレー) (辛い,カレー) (辛い,カレー)
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
