1

我正在尝试解决无法始终验证约束满足的问题。我可以找到很多关于灵活约束满足的论文，但这并不是我想要的。这是一个例子：

P(Jim likes Cheese) = 0.8
P(Joe likes Cheese) = 0.5
P(Sam likes Cheese) = 0.2
P(Jim and Sam are friends) = 0.9
P(Jim and Joe are friends) = 0.5
P(Joe and Sam are friends) = 0.7

查理正在谈论两个喜欢奶酪的朋友。他最有可能在谈论谁？

我目前将此视为约束满足问题：

[likes cheese]   [likes cheese]
 |                           |
 | /-------[alldiff]-------\ |
 |/                         \|
[X]--------[friends]--------[Y]

  ?            ?             ?
  |            |             |
(Sam)        (Joe)         (Jim)

是否有处理此类 CSP 的现有方法？

CSP 甚至是解决问题的正确方法吗？

4

3 回答 3

1

这看起来更像是统计关系学习而不是约束满足。尤其参见概率逻辑网络。

于 2013-06-11T20:12:32.437 回答
1

对于命题模型（其中每个变量都有一个不同的名称），您应该查看概率图形模型（特别是马尔可夫网络）。它们与 SAT 和 CSP 密切相关，因为它们基本上是一种概括，但仍属于同一复杂性类别#P。

如果您对这些模型的简洁的一阶表示感兴趣，您应该研究统计关系学习或一阶概率模型（同义词）。在这里，模型以“提升”的形式表示。例如，可能是以下形式的概率约束，使用范围在某个对象域上的变量：

on(?x,?y) => largerThan(?y,?x)

不依赖于生成地面模型的这些模型的推理是在提升概率推理领域完成的。

于 2013-06-12T09:38:48.407 回答
1

如果您对概率推理的统一方面感兴趣，那么正如 Special Touch 所指出的，您需要查看统计关系模型。该领域最突出的是 Markov Logic Networks ( http://en.wikipedia.org/wiki/Markov_logic_network )。原始论文甚至有一个与您非常接近的“朋友和吸烟者”示例。

解决 MLN 和其他概率关系模型的一种方法是提升概率推理，它明确涉及统一等问题。这是教程的链接：https ://www.biostat.wisc.edu/~natarasr/tutorials/lifted.htm 。然而，这是一个相对较新的研究方向，不太可能在实践中轻松应用。

另一个更近的概率关系模型是概率编程（现在有一个 DARPA 资助的主题）。您可能想检查一下语言 Church、BLOG（贝叶斯逻辑）和 Figaro，但同样，这些都是最近的研究主题，不太容易使用。

于 2015-03-12T18:40:39.210 回答