约束满足不确定性 [英] Constraint Satisfaction with Uncertainty

问题描述

我试图解决一个问题，即约束的满意度不能总是得到验证。我可以找到很多关于灵活的约束满足的论文，但是这并不完全是我想要的。这里有一个例子：

I'm trying to solve a problem in which the satisfaction of constraints cannot always be verified. I can find lots of papers on flexible constraint satisfaction, but that's not quite what I want. Here's an example:

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

查理谈论约两奶酪喜欢的朋友。谁是他最有可能说什么？

Charlie is talking about two cheese-liking friends. Who is he most likely talking about?

我目前看这是一个约束满足问题：

I'm currently viewing this as a constraint satisfaction problem:

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

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

是否有存在的方式来处理这种类型的CSP的？

Are there existing ways for dealing with this type of CSP?

是一个CSP，即使正确的方式来框定问题？

Is a CSP even the right way to frame the problem?

推荐答案

有关命题模型（其中每个变量都有一个独特的名字），你应该看看的概率图模型的（特别是马尔可夫网络的）。他们是非常密切相关的SAT和CSP，因为它们基本上都是一般化，但仍属于同一类的复杂＃P 。

For a propositional model (where each variable has a distinct name), you should have a look at probabilistic graphical models (in particular Markov networks). They are very closely related to SAT and CSP, since they are basically a generalization, but still fall into the same complexity class #P.

如果您有兴趣简洁，一阶重这些模型的presentation，你应该考虑的的统计关系学习或一阶概率模型的（同义词） 。在这里，模型是pssed处于抬起的形式的前$ P $。例如。以下形式的可能概率的限制，使用一些变量对象域范围过：

If you are interested in concise, first order representation of these models, you should look into statistical relational learning or first order probabilistic models (synonyms). Here, the model is expressed in a "lifted" form. E.g. possibly probabilistic constraints of the following form, using variables ranging over some object domain:

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

有这些模特不依赖于产生地面模型推论的领域做的解除概率推理的。

这篇关于约束满足不确定性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！