離散化Dirichlet分布に従うパーフェクトサンプリング(セッション4)
スポンサーリンク
概要
- 論文の詳細を見る
本稿では離散化Dirichlet分布に厳密に従うサンプリングの手法を提案する。提案するアルゴリズムはマルコフ連鎖を用いたサンプリング法で、単調CFTP(Coupling From The Past)アルゴリズムに基づくLas Vegas型の乱択アルゴリズム(randomized algorithm)である。我々は離散化Dirichlet分布を唯一の極限分布に持つ新しいマルコフ連鎖を提案する。このマルコフ連鎖の各推移では離散化ベータ分布に従う確率変数を生成し、アルゴリズムは平均O(n^3 lnΔ)回の推移で終了して、Dirichlet分布に厳密に従う確率変数を返す。ただし、nは変数の次元(パラメータの個数)であり、1/Δは離散化のグリッド幅の大きさである。従って、計算時間はパラメータの数値の大きさに依存しない。
- 2004-05-19
著者
関連論文
- 古典的オーヴァーハングパズルをLPで解く(ORメモランダム)
- 木における消防士問題に対する近似アルゴリズムの改良 (コンピュテーション)
- パズル・ゲームに見る悪魔の証明
- スポーツスケジューリング
- 木における消防士問題に対する近似アルゴリズムの改良
- 統計的機械翻訳におけるフレーズ対応最適化を利用したN-best翻訳候補のリランキング
- オークションの設計理論と数理計画(数理計画の理論と実装)
- 必要不可欠財オークションによる複数財の資源配分(統合オペレーション(2))
- Sealed Bid Multi-object Auctions with Necessary Bundles and its Application to Spectrum Auctions
- Finding a Common Weight Vector of DEA Based on Bargaining Game(DEA(1))
- グラフクラスと部分グラフ同型性
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- フルートの運指のモデル化とその最適化に関する研究
- 1-C-8 ハブ空港配置問題の近似解法(離散最適化(1))
- Integer programming for a phrase alignment problem on statistical machine translation (21世紀の数理計画--最適化モデルとアルゴリズム--RIMS研究集会報告集)
- 解けないパズルをLPで解く : ペグソリティアとパゴダ関数と線形計画(ORメモランダム)
- Dependent Rounding Technique(従属丸め技法) : 最小カット問題の整数性(新・ORの図解,学会創立50周年記念号)
- 新入生のための数学ブートキャンプ(後編)
- 新入生のための数学ブートキャンプ(前編)
- A-1-3 自律移動ロボットの最適タスク計算(A-1.回路とシステム,一般セッション)
- フルートの運指最適化と逆最適化を用いたパラメータチューニング
- マルコフ連鎖の完璧シミュレーション(超ロバスト計算原理とモデリング・シミュレーション)
- クラス編成問題--素敵な出会いを演出します
- 多変量離散分布とマルコフ連鎖モンテカルロ法(学生セッション)
- データ結合問題で現れる多次元割当問題の近似解法
- ここまで解ける整数計画(堅く柔らかく…数理計画アプローチ再訪)
- 1-C-12 Approximation Algorithm for Multidimensional Assignment Problem Arising from Data Association Problem
- 1-C-9 フルートの運指のモデル化とその最適化に関する研究(離散最適化(2))
- 1-A-3 対戦日程計画におけるCarry-Over Effect最小化問題(離散最適化(1))
- DS-1-4 スポーツのスケジューリングにおける会場割当問題(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- スーパーコンピューティング・コンテスト2005
- 1-D-13 Sampling from Logarithmic Separable Concave Distribution on Simplex
- 離散化Dirichlet分布に従うパーフェクトサンプリング(セッション4, 日本計算機統計学会第18回大会報告)
- 電力取り引きにおける約定量決定問題の高速解法
- リーグ戦の最適会場割当問題に対するSDP緩和を用いた手法(グラフ・ネットワーク(1))
- スポーツスケジューリング : 未解決問題を中心に
- 電力取り引きにおける約定量決定問題の高速解法(組合せ最適化(5))
- Multicoloring Unit Disk Graphs on Triangular Lattice Points
- 離散化Dirichlet分布に従うパーフェクトサンプリング(セッション4)
- 対角線付き格子グラフに対するマルチカラーリングの線形時間近似解法
- 離散化Dirichlet分布に従うPerfect Sampler(マルコフモデル)
- The Break Minimization Problem
- Weighted Lattice Graph with Diagonals に対するマルチカラーリングの線形時間近似解法(グラフ・ネットワーク)
- 平衡状態を探す:マルコフ連鎖/CFTP (特集 最適を探す)
- A-2 2行分割表の多項式時間Perfect Sampling(コンペティション(1))(2003年度統計関連学会連合大会記録(日本統計学会第71回大会))
- MCMC法による2×n分割表個数数え上げ(セッション5)(日本計算機統計学会第16回大会報告)
- A Cutting Plane Approach to Hub Network Design Problems
- 2行分割表の多項式時間 Perfect Sampling
- Dirichlet分布に従う多項式時間近似サンプリング法(マルコフ連鎖)
- 選択組立におけるマッチング算法(組合せ最適化(2))
- 0-1分数計画問題に対するDinkelbachの解法の解析(組合せ最適化(4))
- 分散型の目的関数をもつ割当問題の一解法(数理計画)
- A-2 Path coupling法を用いた多元分割表生成のためのマルコフ連鎖設計
- Path coupling 法を用いた : 多元分割表生成のためのマルコフ連鎖設計
- Approximation algorithm for generating B^m × J contingency tables
- 重み付き多数決ゲームでの投票力指数計算のNP完全性(ゲーム・理論)
- 重みつきマトロイドのK番目に重い基を求める
- 偽金貨を探そう(高校生のためのOR)
- 全張木を重さの軽い順に列挙する(組合せ最適化(5))
- 非巡回的有向グラフ上のs-tパスの列挙(組合せ最適化(5))
- Farkasの補題と双対定理の初等的証明(数理計画)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 有限グラフ上のランダムウォークの脱乱択化
- Cheating Strategies for the Gale-Shapley Algorithm with Complete Preference Lists
- 最長片道きっぷの厳密解を求める(組合せ最適化)
- 月次配油計画とその解法(スケジューリング(4))
- 2部グラフの辺彩色の列挙(グラフ・ネットワーク)
- コーダルグラフのサンドイッチ列挙
- Deegan-Packel指数の特性(ゲーム理論(2))
- 和音に対するピアノ運指決定法 (最適化手法の深化と広がり)
- m×n分割表の近似数え上げスキームの提案(マルコフ連鎖)
- 2×n分割表のPerfect Sampling(マルコフ連鎖)
- m×n分割表の近似数え上げスキームの提案
- MCMC法による2×n分割表個数数え上げ(一般講演)
- 2-K-7 スライディングブロックパズルを用いた画像再構築(ワークショップ「娯楽のOR-エンターテイメントの数理」)
- 多施設巡回路決定問題について(グラフ・ネットワーク)
- 数理ゲームの必勝法とイカサマの技(パズルとゲームの計算理論)
- 特集にあたって(ランキングとレイティング)
- 不動点定理によるドロネー性の確認
- 1-B-5 Lower Bounds for Bruss' Odds Problem with Multiple Stoppings
- NP-completeness of Arithmetical Restorations (Preprint)
- ANPを用いたサッカーチームの項目別強さ推定(グラフと確率・統計モデル)
- 2-C-3 不動点定理によるドロネー性の確認(離散最適化(2))
- 無理数の遷移確率を許すランダムウォークの脱乱択化 (理論計算機科学の新展開)
- 森および連結全域部分グラフの乱択近似数え上げ (理論計算機科学の新展開)