具有不确定性的约束满足

Question

我试图解决一个问题，在这个问题中，约束的满意度不能总是得到验证。我可以找到很多关于灵活约束满意度的论文，但这不是我想要的。下面是一个例子：

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是否是构建问题的正确方法？

Answer 1

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

如果您对这些模型的简洁、一阶表示感兴趣，则应该研究统计关系学习或一阶概率模型(同义词)。在这里，模型以“解除”的形式表达。例如，可能采用以下形式的概率约束，使用在某些对象域上的变量：

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

在提升概率推理领域，对这些不依赖于生成地面模型的模型进行推理。

Answer 2

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

Answer 3

如果您对概率推理的统一方面感兴趣，那么您需要查看统计关系模型，正如特殊触摸所指出的那样。其中最突出的是马尔可夫逻辑网络(网络)。原来的报纸甚至有一个“朋友和烟民”的例子非常接近你的。

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

另一种更近的概率关系模型是概率编程(目前正在对这一主题进行DARPA授权)。您可能想检查语言教堂，博客(贝叶斯逻辑)和菲加罗，但同样，这些是最近的研究主题，不太容易使用。