Ограничение Удовлетворение неопределенностью

Я пытаюсь решить проблему, в которой не всегда можно проверить выполнение ограничений. Я могу найти множество статей о гибком удовлетворении ограничений, но это не совсем то, что мне нужно. Вот пример:

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 правильным способом сформулировать проблему?


artificial-intelligence algorithm probability constraint-satisfaction
person williamstome    schedule 11.06.2013    source источник
comment
Вы можете предположить что-нибудь о независимости? Я полагаю, что в этом примере у вас могут быть два друга, которые встречаются на дегустации сыра и бросают все это дело.   -  person Dan Garant    schedule 11.06.2013
comment
Я не совсем уверен, что понимаю ваш вопрос; хотя, возможно, мой пример был плох. Я хочу рассматривать набор предикатов P как набор ограничений на возможные переменные, которые можно подставить в эти предикаты. К сожалению, мы можем только с ограниченной степенью достоверности оценить, выполняется ли предикат при подстановке.   -  person williamstome    schedule 11.06.2013

Ответы (3)


arrow_upward
1
arrow_downward

Для пропозициональной модели (где каждая переменная имеет свое имя) вам следует взглянуть на вероятностные графические модели (в частности, на марковские сети). Они очень тесно связаны с SAT и CSP, поскольку в основном представляют собой обобщение, но по-прежнему относятся к тому же классу сложности #P.

Если вас интересует краткое представление этих моделей первого порядка, вам следует изучить статистическое реляционное обучение или вероятностные модели первого порядка (синонимы). Здесь модель выражена в «приподнятой» форме. Например. возможно, вероятностные ограничения следующей формы, использующие переменные в пределах некоторой предметной области:

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

Выводы с этими моделями, которые не полагаются на создание наземной модели, выполняются в области повышенного вероятностного вывода.

person ziggystar    schedule 12.06.2013
comment
Я согласился с тем, что CSP не являются правильным способом решения моей проблемы, но в конце концов я решил, что графические модели в целом не являются подходящим решением, особенно потому, что я не пытаюсь выполнить вывод, а скорее унификацию/разрешение ссылок. Я принимаю этот ответ, потому что, хотя это и не было решением моей проблемы, это было результатом того, что моя проблема была представлена ​​​​в неправильном свете, и этот ответ был наиболее информативным. Мои проблемы продолжаются здесь!: stackoverflow.com/questions/17090385/ - person williamstome; 13.06.2013

arrow_upward
1
arrow_downward

Это больше похоже на статистическое реляционное обучение, чем на удовлетворение ограничений. См., в частности, Вероятностные логические сети.

person Special Touch    schedule 11.06.2013
comment
Можете ли вы объяснить, почему вы так думаете? Информации о польских злотых очень мало... - person williamstome; 12.06.2013
comment
Из Википедии: основная цель PLN - обеспечить достаточно точный вероятностный вывод... Это не похоже на то, что я хочу. В моем сценарии у меня есть набор значений. Периодически я буду получать наборы предикатов, и мне нужно будет вернуть комбинацию этих значений, которая удовлетворяет набору предикатов. Если бы я мог получить доступ к дискретным значениям истинности для подстановок значений переменных, это был бы простой CSP. Твист — это неопределенность замены. Что ж, другой нюанс заключается в том, что я работаю в открытом мире, но давайте пока проигнорируем это. - person williamstome; 12.06.2013
comment
Похоже, вы пытаетесь вывести замены значений переменных, которые максимизируют вероятность набора условных предикатов. Вот почему я предложил PLN (или какую-то другую статистическую реляционную модель). Если это не то, что вы имеете в виду, можете ли вы быть более строгим в отношении того, что означает удовлетворение ограничений в этом контексте? Как вы узнаете, что достигли этого? - person Special Touch; 12.06.2013

arrow_upward
1
arrow_downward

Если вас интересуют унифицирующие аспекты вероятностного вывода, вам нужно, как указывает Special Touch, обратить внимание на статистические реляционные модели. Наиболее известными в этой области являются логические сети Маркова (http://en.wikipedia.org/wiki/Markov_logic_network< /а>). В оригинальной статье даже есть очень близкий к вашему пример «друзья и курильщики».

Одним из способов решения MLN и других вероятностных реляционных моделей является поднятый вероятностный вывод, который явно включает такие вопросы, как унификация. Вот ссылка на учебник: https://www.biostat.wisc.edu/~natarasr/tutorials/lifted.htm. Однако это относительно новое направление исследований, и вряд ли его можно легко применить на практике.

Другой, еще более поздней линией вероятностных реляционных моделей является вероятностное программирование (прямо сейчас идет грант DARPA на эту тему). Возможно, вы захотите проверить языки Church, BLOG (байесовская логика) и Figaro, но опять же, это недавние темы исследований, и их не так просто использовать.

person user118967    schedule 12.03.2015