11

马尔可夫链是一种(几乎是标准的)生成随机乱码的方法,在未经训练的人看来很聪明。您将如何从人类书面文本中识别马尔可夫生成的文本。

如果您指向的资源是 Python 友好的,那就太棒了。

4

6 回答 6

8

一种简单的方法是让一大群人为您阅读输入文本,看看文本是否有意义。我只是半开玩笑,这是一个棘手的问题。

我认为这是一个难题,因为马尔可夫链生成的文本在词频和词序之间的简单关系方面将具有许多与真实人类文本相同的属性。

真实文本与马尔可夫链生成的文本之间的区别在于更高级别的语法规则和语义含义,它们很难以编程方式进行编码。另一个问题是马尔可夫链足够擅长生成文本,它们有时会提出语法和语义正确的语句。

例如,这是来自 kantmachine 的一句格言

今天,他会确信人的意志是自由的;明天,考虑到自然的不可分割的链条,他会将自由视为一种幻觉,并宣布自然是万能的。

虽然这个字符串是由计算机程序编写的,但很难说人类永远不会这么说。

我认为,除非您可以向我们提供有关计算机和人工生成文本的更具体细节,从而暴露出更明显的差异,否则使用计算机编程将很难解决这个问题。

于 2009-07-26T20:11:29.917 回答
6

您可以使用“蛮力”方法,将生成的语言与在比生成它的马尔可夫模型更高阶的 n-gram 上收集的数据进行比较。

即,如果语言是使用二阶马尔可夫模型生成的,最多 3-gram 将具有正确的频率,但 4-gram 可能不会。

您可以从 Google 的公共n-gram 数据集中获得高达 5-gram 的频率。虽然它很大 - 24G压缩- 你需要通过LDC的 DVD 邮寄来获得它。

编辑:添加了一些实现细节

n-gram 已经被计算过了,所以你只需要以一种快速搜索的方式存储计数(或频率)。一个正确索引的数据库,或者一个 Lucene 索引应该可以工作。

给定一段文本,扫描它并查找数据库中每个 5-gram 的频率,并查看它与以相同 4 个单词开头的其他 5-gram 相比的排名。

实际上,更大的障碍可能是数据集的许可条款。可能会禁止将其用于商业应用程序。

于 2009-07-27T09:20:32.940 回答
5

我建议对 Evan 的回答进行概括:制作自己的马尔可夫模型,并使用您提供的大部分(非常大的)样本对其进行训练,并将其余样本保留为“测试数据”。现在,看看您训练过的模型在测试数据上的表现如何,例如使用卡方检验会建议“拟合太好”的情况(表明测试数据确实是由该模型生成的)以及拟合度非常差的模型(表明模型结构存在错误——在这种情况下,结构错误的过度训练模型的表现非常糟糕)。

当然还有很多问题需要校准,比如模型的结构——你是在怀疑一个基于 Ntuples 的简单模型等等,还是一个更复杂的带有语法状态等的模型。幸运的是,您可以通过使用大量已知自然文本的语料库以及您自己使用各种结构的模型生成的语料库来很好地校准事物。

另一种方法是使用nltk来解析你给出的句子——即使在自然文本中也会出现少量的错误解析(因为人类是不完美的,解析器也是如此——它可能不知道那个词X 可以用作动词,并且只能将其分类为名词等),但大多数马尔可夫模型(除非它们对您的解析器碰巧使用的语法结构进行建模,并且您可以使用多个解析器来尝试抵消这一点!-) 会导致比阅读障碍的人更多的错误解析。再次,在自然文本和合成文本上进行校准,你就会明白我的意思了!-)

于 2009-07-27T02:46:20.073 回答
2

如果你有几个大的马尔可夫生成的文本,你可以通过比较每个样本之间的词频来确定它们是这样的。由于马尔可夫链依赖于恒定的单词概率,因此任何给定单词的比例在样本之间应该大致相等。

于 2009-07-26T19:52:33.667 回答
2

众包。使用 Mechanical Turk 并让一些人对此进行投票。甚至还有一些库可以帮助您实现这一目标。例如:

以下是 O'Reilly Radar 的一篇关于使用 Mechanical Turk 完成工作的技巧的博客文章:

于 2009-07-27T01:18:56.777 回答
0

如果您编写一个程序,该程序从任何符号序列生成马尔可夫转移概率,然后计算马尔可夫矩阵的熵率。(参见http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains)这基本上是对仅使用马尔可夫链预测文本的难易程度的估计(更高的熵意味着更难预测)。因此,我认为马尔可夫矩阵的熵越低,文本样本就越有可能由马尔可夫矩阵控制。如果您对如何编写此代码有疑问,我碰巧有一个 Python 程序,它可以在我的计算机上执行此操作,所以我可以帮助您

于 2013-07-22T17:50:49.993 回答