日本OR学会アルゴリズム研究部会 (SAOR)

投稿日:2004/04/20投稿者:岩田 覚
*******************************************************************
*            日本オペレーションズ・リサーチ学会                   *
*                アルゴリズム研究部会 (SAOR)                      *
*                   第8回研究会のお知らせ                        *
*******************************************************************

SAOR第8回研究会を以下の通り開催します.是非御参加下さい.
会場案内に関しては, 当研究部会ホームページ
http://www.me.sophia.ac.jp/~y-miyamo/saor/
を御覧下さい.


====================================================================
          > 

2004年4月24日(土) 14:00-18:00

東京大学工学部6号館3階セミナー室 A&D


14:00-15:50 三好 直人 氏 (東京工業大学) 
「m-バランス列について」

16:10-18:00 青木 敏 氏  (東京大学)
「マルコフ連鎖・モンテカルロ法による分割表解析」

================================================================== 
「m-バランス列について」
三好 直人 氏 (東京工業大学)

N(≧2)種類の文字を並べて (片側または両側に) 無限に長い列 (word) を作る
ことを考える. 各文字に列の中で現れる頻度 (密度) が与えられているとき, 
それを満足し, かつ各文字がバランス良く並んでいる列を作りたい. ここでバ
ランスが良いとは, 各文字ができるだけ均等に並んでいることを指す. こうし
た問題に対して, バランス列 (balanced words) という概念があり,様々なス
ケジューリング問題への応用も考えられているが, 与えられた密度の組に対し
て常にバランス列が存在するとは限らないことが難点である. 本発表で紹介す
る m-バランス列 (m-balanced words) は, バランス列の定義を一般化したも
ので, 任意の密度の組に対して定義することができ, またバランスの良さの尺
度を与えるものである. この m-バランス列について, その性質と簡単な応用
例を説明し, またバランスの良い列を構成するアルゴリズムについて述べる.

================================================================== 
「マルコフ連鎖・モンテカルロ法による分割表解析」
青木 敏 氏  (東京大学)

分割表解析においてわれわれが遭遇する統計的推測の問題の多くは,集約的に
は,適当な統計量の仮説のもとでの条件付期待値の推定問題として定式化する
ことができる.マルコフ連鎖・モンテカルロ法は,その数値的評価のためのア
ルゴリズムのひとつである.特にそれは,単純なモンテカルロ積分が実行でき
ない(直接的なサンプリングが不可能)というようなケースを想定しており,
Importance Sampling 法とはその目的を共有するものである.

分割表解析におけるマルコフ連鎖・モンテカルロ法は,
Diaconis and Sturmfels (1998) によって提案され,注目を集めた.
この方法は,マルコフ連鎖・モンテカルロ法を実現するために必要な,状態空
間上の既約なマルコフ連鎖を構成するための基底(マルコフ基底)を,代数ア
ルゴリズムを用いて算出するものである.理論上は彼らの方法により,任意の
離散の条件付分布からのサンプリングが可能になった,という点で興味深い.
しかし一方で,代数アルゴリズムを用いた基底の算出方法には問題点も多く,
中でも,計算時間の問題と,得られる基底が極小でないという問題は重大であ
る.計算時間の問題は,代数アルゴリズムの理論的な計算量が,変数の数の二
重指数オーダーであることに起因しており,比較的小さなサイズの問題に対し
ても,実際の計算はすぐに破綻してしまう.また,基底が極小でないという問
題は,代数アルゴリズムが変数間に項順序を与えて計算するものであるため,
変数間の対称性が崩れる,ということに起因している.

本報告ではこれらの問題点を踏まえ,極小なマルコフ基底の導出法とその性質
に関して,代数アルゴリズムを用いずに得られる結果を紹介する.特に,本報
告では,理論的に重要な性質として,極小マルコフ基底の一意性と不変性に注
目する.本報告では,実際のさまざまな問題に対して,極小マルコフ基底を導
出し,その一意性,不変性に関して考察する.


================================================================== 
日本オペレーションズ・リサーチ学会
アルゴリズム研究部会 (SAOR)
主査: 岩田 覚     (東京大学)
幹事: 武田 朗子 (東京工業大学)
      宮本 裕一郎 (上智大学)
===================================================================