マトロイドの凸構造 - けんちょんの競プロ精進記録
この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何故でしょうか？実は、マトロイドは単に「Greedyの一例」として出て来るばかりでなく、「現在効率的なアルゴリズムが知られている問題の殆どはマトロイドが何かしら関わっている」と言える程にイイ構造を持っています。以前、以下のようなツイートをしました。 dpやってていつも思うのが、なんか凸凹してるなーと。凸凹し過ぎてdpじゃなきゃ解けないよな、みたいな感じ。マトロイドは凹んでるところがない凸なイメージ。だから、局所最適狙う貪欲法だけで最適解に辿り着ける。焼き鈍しなんて必要ない。 本記事では、この
DPの話 - aizuzia
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
かなり甘い感じなディリクレ過程のお話。 - photogenic blue note
photogenic blue note "We cannot all do great things, but we can do small things with great love." 空間Xがあるとしよう。この空間上に定義された関数を考える。この関数がどんなものかについては、漠然と、Xの一部分Aについて、Aの範囲で積分を計算できる、ぐらいに思っておく。もちろん、Xの一部分と言えるものは、いろいろありえる。なお、いま言った「積分」がどんな積分かは、ここでは厳密には考えないことにする。 しかも、この関数を、X全体で積分すると、1になるとしよう。そういう関数だけを考える。 X上に定義された関数で、X全体で積分すると1になるものは、無数にある。これら無数にあるものの上に、確率分布を定義することができる。本当にできるのかどうかは、ここでは気にしないことにする。とにかく、できる。 ディリク
ディリクレ過程(Dirichlet Process)を調査中 - EchizenBlog-Zwei
そろそろ階層ディリクレ過程(Hierarchical Dirichlet Processes)を理解したい気分だったので調査中。とりあえずディリクレ過程について現時点での理解をメモしておく。間違ってる可能性もあるので悪しからず。 やりたい事。データの系列x={x1, x2, ..., xn}について、P(x)を求めたい。もしくはP(x)からxをサンプリングしたい。このP(x)がディリクレ過程。 事前分布としてG0という分布を考える。この分布は何でも良く、とりあえず正規分布とかを思い描くと良い。加えてαというスケーリングパラメータを用意する。 このG0とαをパラメータとした分布DP(G; α, G0)を考える。これは具体的にはDir(αG0(x1), αG0(x2), ...)というディリクレ分布となっている。従ってDPは足して1になるパラメータセットθ={θ1, θ2, ..., θn}に
動的計画法を学ぶリソース・練習問題まとめ - フリーフォーム フリークアウト
移転しました http://please-sleep.cou929.nu/20100708.html
動的計画法は再帰で表せ
動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています． メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります． 今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x
Dirichlet Processes: A Gentle Tutorial
Dirichlet Processes A gentle tutorial Khalid El-Arini SELECT Lab Meeting October 14, 2008 Motivation 2 We are given a data set, and are told that it was generated from a mixture of Gaussian distributions. Unfortunately, no one has any idea how many Gaussians produced the data. Motivation 3 We are given a data set, and are told that it was generated from a mixture of Gaussian distributions.
mots quotidiens.
Cでプログラムを書いていて, テキスト形式でセーブされたパラメータファイルから ベクトル/行列に読み込むという処理は非常によくあると思うのだが (MATLABの load に相当), うっかり前に書いたコードを忘れて車輪を再発明する ところだった。; 誰が書いても同じようなコードになると思うのだけれども, 次元を事前に指定せず, 読むのと同時に決めるコードは一瞬では書けないと思うので, せっかくなので 下に公開しておきます。(ファイルに書く方は簡単なので省略。) loader.c loader.h dmatrix.c dmatrix.h これを使うには, 以下のようにします。 #include "loader.h" double *vector, **matrix; int dim, rows, cols; if ((vector = load_vector(file, &dim)) ==
スライド 1
ノンパラメトリックベイズモデル 上田 修功 NTT コミュニケーション科学基礎研究所 2009年 3月13日 パターン認識応用の視点で解説 CVIM/PRMU研究会 ノンパラメトリックベイズの基礎に関連する キーワード ディリクレ過程(DP: Dirichlet Process) 棒折り過程 (SBP: Stick Breaking Process) ディリクレ混合過程(DPM) 中華レストラン過程(CRP: Chinese Restaurant Process) 階層ディリクレ混合過程(HDPM) FAQ Q1: 新しい分野？ No! 創始者Ferguson(1973)，近年，機械学習で流行 Q4: ディリクレ過程はディリクレ分布と関係する？ Yes! それこそが本質 Q２: “ノンパラメトリック”の意味は？ 直観的には”massive parametric”が妥当 Q３: 通常のベイ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
変分ベイズでディリクレ過程混合モデル（Blei論文を解く）
Scientific Programmes | Isaac Newton Institute for Mathematical Sciences
https://people.eecs.berkeley.edu/~jordan/papers/hierarchical-dp.pdf
https://people.eecs.berkeley.edu/~jordan/nips-tutorial05.ps
http://www.gatsby.ucl.ac.uk/~ywteh/research/npbayes/dp.pdf
thesis_1spc.dvi
NIPS*03 One-day Workshop on Nonparametric Bayesian methods and Infinite models
http://www.phontron.com/dirichlettopic/dirichlet-topic.pdf
抽出公式の数学的諸相1 半田 賢司 （佐賀大学 理工学部） handa@ms.saga-u.ac.jp 集団遺伝学のモデルにおいて、ある種の平衡状態にある集団からランダムに抽出した個 体を、それらの型によ�
An Introduction to Bayesian Nonparametric Modelling
Nonparametric Bayes for Non-Bayesians