マルコフ連鎖の脱乱択化：決定性近似アルゴリズム設計に対する新しい汎用手法の開発

马尔可夫链的解序：开发一种新的通用方法来设计确定性逼近算法

基本信息

批准号：
15J03840
负责人：
白髪丈晴
金额：
$ 1.22万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2015
资助国家：
日本
起止时间：
2015-04-24 至 2017-03-31
项目状态：
已结题

项目摘要

本年度はマルコフ連鎖の脱乱択化研究のなかで, 全訪問時間研究において顕著な成果をあげることに成功した.これまで行ってきた研究は, 各時刻ごとのトークン配置の誤差解析であり, 即ちマルコフ連鎖(確率過程)とそれに類似する決定性過程の``空間平均''の誤差解析であった. 本年度はこの空間平均にあたるトークン分布の誤差解析を, ``時間平均''の誤差解析へ拡張することに成功した. 具体的には, 確率過程, 決定性過程のトークンがある頂点を訪問した回数(訪問頻度)の誤差の上界の導出に成功した. 既存研究でも時間平均にあたる訪問頻度の誤差解析は行われていたが, グラフ上の1トークン単純ランダムウォークに対応するものにとどまっており, 一般の可逆な遷移確率かつ複数トークンまで拡張に成功した本研究の意義は大きい.特に, 訪問頻度の解析手法を用いることで, 一般の遷移確率を持つマルコフ連鎖に類似する決定性過程の, 全訪問時間の上界を得ることに成功した. これは一般の遷移確率に対する初の全訪問時間の上界であり, 本年度にこの成果をまとめ, 国際会議に採択され発表済みである. 更に, 本成果は既存の複数トークン単純ランダムウォークに対応する決定性過程のものを改善している.全訪問時間解析を更に洗練させることにも成功しつつあり, 特定の構造上ではあるが, 遷移確率を工夫することによるランダムウォークの高速化アルゴリズムに習い, それを模倣する決定性過程の全訪問時間が通常の単純なものよりも高速化出来ることを示しており, 29年度, 国際会議に投稿予定である.このように, 本年度の研究でこれまで行ってきた空間平均の解析と時間平均の解析が研ぎ澄まされ, MCMC法の脱乱択化へ大きな進歩が見られた.

今年，我们在马尔可夫链去随机化的研究中，在总访问次数的研究中，成功取得了显着的成果。到目前为止我们所做的研究都是对每个时间的代币放置进行误差分析，即这是一个误差马尔可夫链（随机过程）和类似确定性过程的“空间平均”分析。今年，我们将与空间平均相对应的令牌分布的误差分析扩展到“时间”的误差分析平均。”具体来说，随机过程，我们成功地推导了确定性过程中令牌某个顶点的访问次数（访问频率）误差的上限。现有研究也分析了访问频率的误差，即时间平均值，但是可以在确定性过程中导出令牌的某个顶点的访问次数（访问频率）的误差上限，这项研究的意义在于它仅限于与随机相对应的方法。 walk，但成功地将其扩展到一般可逆转移概率和多个标记。特别是，通过使用访问频率分析方法，可以实现具有类似于马尔可夫链的确定性过程的方法，我们成功地获得了总访问时间的上限，这是第一个一般转移概率的总访问时间的上限，这个结果在今年进行了总结，并已在国际会议上被采纳和提出。结果改进了与现有多令牌简单随机游走相对应的确定性过程，我们还成功地进一步细化了总访问时间分析，尽管它是基于特定结构，但我们可以提高随机学习的转移概率。通过设计步行加速算法，我们已经证明，模仿这个过程的确定性过程的总访问时间可以比普通的简单过程更快，我们计划在 2019 年将其提交给一个国际会议。通过这种方式，我们证明了模拟该过程的确定性过程的总访问时间可以比普通简单过程更快。空间平均分析和时间平均分析得到了细化，并且在去随机化MCMC方法方面取得了很大进展。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Total Variation Discrepancy of Deterministic Random Walks for Ergodic Markov Chains

遍历马尔可夫链的确定性随机游走的总变差差异

DOI：
发表时间：
2016
期刊：
影响因子：
0
作者：
Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;Masafumi Yamashita
通讯作者：
Masafumi Yamashita

L∞-Discrepancy Analysis of Polynomial-time Deterministic Samplers Emulating Rapidly Mixing Chains

模拟快速混合链的多项式时间确定性采样器的 L∞-差异分析

DOI：
发表时间：
2014
期刊：
影响因子：
0
作者：
Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;and Masafumi Yamashita
通讯作者：
and Masafumi Yamashita

King's College London(英国)

伦敦国王学院（英国）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

一般の遷移確率を持つマルコフ連鎖の脱乱択化

具有一般转移概率的马尔可夫链的解序

DOI：
发表时间：
2016
期刊：
影响因子：
0
作者：
Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;Masafumi Yamashita;白髪丈晴;白髪丈晴;谷田川友里;Takeharu Shiraga;井田貴子;Yuri Yatagawa;白髪丈晴
通讯作者：
白髪丈晴

ランダムウォークの脱乱択化, 分散投票モデル

随机游走的非随机化、分布式投票模型