代码之家 › 专栏 › 技术社区 › Sampson

用马尔可夫逻辑避免确定性

variations markov-chains deterministic

2

Sampson · 技术社区 · 16 年前

我今天刚开始阅读更多关于马尔可夫链生成器的内容,并且对构建一个生成器的整个过程非常感兴趣。据我所知,未来的状态取决于过去到现在的统计状态。

例子:

你好,世界。你好,多莉。你好,世界。

“世界”跟在“你好”后面大约66%的时间。

如果总是这样的话,那么你如何避免每次都输出相同的结果呢?统计事件不会随静态字符串的变化而变化,所以我可以假设不会生成所有变量,除非以某种方式修改源数据?

考虑到统计值,我如何从静态源获取变化,同时又允许一些灵活性?使用上面的例子,当“dolly”只跟在“hello”后面33%的时候,我如何允许生成器跟在“hello”和“dolly”后面?

我想我要问的是,下一次选择的概率是如何建立在当前选择后面的单词的统计存在性之上的?这样,“多莉”显示的时间占33%,而“世界”显示的时间占66%——或者我在这里完全迷路了?

2 回复 | 直到 16 年前

1

3

Omnifarious 16 年前

您可以使用随机数生成器来选择您要走的路径。您必须保存每个状态(实际上是n个前一项的历史记录)和该状态的概率。然后你选择一个随机数,并根据它来决定你下一个过渡到什么状态。

在您的示例中,有一个n为1的马尔可夫链,您将有一个类似这样的链结构:

<start> -> Hello : 1.0

Hello -> World. : 0.66666
Hello -> Dolly. : 0.33333

Dolly. -> Hello : 1.0

World. -> <end> : 0.5
World. -> Hello : 0.5

如果您当前的状态是hello,那么您下一个可能的状态是world。还有新子…生成一个介于0和1之间的随机数并选择World。如果小于0.666666,则选择多莉。

对于n=2马尔可夫链,您可以通过该输入获得几乎确定性的行为:

<start> <start> -> <start> Hello : 1.0

<start> Hello -> Hello World. : 1.0

Hello World. -> World. Hello : 0.5
Hello World. -> World. <end> : 0.5

World. Hello -> Hello Dolly. : 1.0

Hello Dolly. -> Dolly. Hello : 1.0

Dolly. Hello -> Hello World. : 1.0

2

0

Jonathan Graehl 16 年前

两个评论:

1)要从随机过程中生成样本,无论某个选择是否很有可能(>50%),而其他选择的可能性较小,只需要一个加权的“硬币翻转”:在[0,1]上均匀生成一个随机实数,并以相同的固定顺序考虑各种可能性,保持目前的概率总和。一旦金额超过随机选择的数字,选择该选项。如果你的选择有非标准化的(不是1的总和)概率,你首先需要计算概率的总和,然后将它们全部除以s,或者在[0,s]上选择你的随机数。

2)为了防止从少量样本训练数据(与参数数量相比)估算模型时过度拟合,请在模型参数上使用贝叶斯先验。对于一个非常酷的例子,模型参数的数量(历史大小)没有预先固定为任何有限的数字,请参见 Infinite HMM .如果您不使用贝叶斯方法,那么您将需要为您所拥有的训练数据量适当地选择历史长度,和/或实现一些特殊的平滑(例如订单2和订单1模型之间的线性插值)。