불확실성에 대한 제약 조건 만족

제약 조건의 만족도를 항상 확인할 수있는 문제를 해결하려고합니다. 나는 유연한 제약 조건 만족에 대한 많은 논문을 찾을 수 있지만 그건 내가 원하는 것만은 아니다. 여기 예가 있습니다 :불확실성에 대한 제약 조건 만족

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

찰리는 치즈를 좋아하는 두 친구에 대해 이야기하고 있습니다. 그는 누구에게 가장 가능성이 높습니까?

나는 현재 제약 만족 문제로 이것을보고있어 : CSP의이 유형을 다루는

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

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

가 기존 있습니까 방법?

CSP를 사용해도 문제의 프레임을 구성 할 수 있습니까?

출처

2013-06-11 williamstome

독립성에 대해 아무 것도 생각할 수 있습니까? 나는이 예에서 치즈 샘플링에서 만난 두 친구를 가질 수 있으며 모든 것을 던질 것입니다. –

나는 당신의 질문을 잘 모르겠다. 아마 나의 예는 나빴다. 나는 술어'P'를 술어로 대체 할 수있는 가능한 변수에 대한 제한 조건 세트로 취급하려고합니다. 불행히도 우리는 조건부의 확실성을 가지고 조건부 치환을 유지하는지 여부 만 평가할 수 있습니다. – williamstome

, 당신은 (특히 마르코프 네트워크에서) 확률 그래픽 모델을 살펴 있어야합니다. 그들은 기본적으로 일반화 되었기 때문에 SAT와 CSP와 매우 밀접하게 관련되어 있지만 여전히 동일한 복잡성 등급 #P에 속합니다.

당신이이 모델의 간결, 첫 번째 순서 표현에 관심이 있다면, 당신은 통계 관계형 학습 또는 첫 번째 순서 확률 모델 (동의어)로 보일 것입니다. 여기서 모델은 "해제 된"형식으로 표현됩니다. 예 : 일부 개체 도메인에 이르기 변수를 사용하여 다음과 같은 형식의 가능성 확률 제약 : 지상 모델을 생성에 의존하지 않는 이러한 모델

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

추론이 의 분야에서 수행되는이 확률 적 추론을 해제.

출처

2013-06-12 09:38:48 ziggystar

필자는 CSP가 내 문제를 해결하는 올바른 방법이 아니라고 인정했지만 결국 일반적으로 그래픽 모델이 적절한 솔루션이 아니라고 결론을 내 렸습니다. 특히 추론을 시도하지 않고 통일/참조 해결을 수행하기 때문입니다. . 내 문제에 대한 해결책이 아니었지만 이것이 내 문제가 잘못된 빛에 누명을 씌운 결과 였고이 답변이 가장 유익했기 때문에이 대답을 수락합니다. 내 문제는 계속됩니다! : http://stackoverflow.com/questions/17090385/ai-partial-unification-in-open-world-reference-resolution – williamstome

이것은 제약 조건 만족보다 statistical relational learning과 비슷합니다. 특히 Probabilistic logic networks을 참조하십시오.

(각 변수가 서로 다른 이름을 가진) 명제 모델의 경우

출처

2013-06-11 20:12:32

이것이 왜 그렇게 생각하는지 설명 할 수 있습니까? PLN에 사용할 수있는 정보가 거의 없습니다 ... – williamstome

위키 백과에서 : "PLN의 기본 목표는 합리적으로 정확한 확률론을 제공하는 것입니다 ..." 이것은 내가 원하는 것과 관련이없는 것 같습니다. 제 시나리오에는 일련의 가치가 있습니다. 주기적으로, 나는 술어의 집합을 얻을 것이고, 술어의 집합을 만족시키는 이들 값의 조합을 반환 할 필요가있다. 변수 값 대체에 대한 개별적인 진리 값에 액세스 할 수 있다면 그것은 직설적 인 CSP가 될 것입니다. 트위스트는 대체에 대한 불확실성입니다. 다른 트위스트는 내가 열린 세상에서 일하고 있지만 지금은 무시해 보겠습니다. – williamstome

일련의 조건부 술어의 가능성을 최대화하는 변수 값 대체를 추측하려고하는 것 같습니다. 그래서 PLN (또는 다른 통계적 관계형 모델)을 제안했습니다. 그것이 당신이 의미하는 것이 아니라면,이 맥락에서 만족의 제약이 무엇을 의미하는지에 대해 더욱 엄격해질 수 있습니까? 당신이 그것을 성취했을 때 어떻게 알 수 있습니까? –

확률 론적 추론의 통일 측면에 관심이 있다면 통계적 관계형 모델에서 Special Touch가 지적한 것처럼보아야합니다. 그 분야에서 가장 두드러진 것은 Markov Logic Networks (http://en.wikipedia.org/wiki/Markov_logic_network)입니다. 원래의 종이에는 "친구와 흡연자"의 예가 있습니다.

MLN 및 기타 확률 론적 관계 모델을 해결하는 한 가지 방법은 확률 적 추론을 해제하는 것으로 통일과 같은 문제를 명시 적으로 포함합니다. 다음은 튜토리얼 링크 https://www.biostat.wisc.edu/~natarasr/tutorials/lifted.htm입니다. 그러나 이는 비교적 최근의 연구이며 실제로는 쉽게 적용 할 수 없을 것입니다.

확률 론적 관계 모델의 또 다른 라인은 확률 적 프로그래밍입니다 (현재 진행중인 주제에 대한 DARPA 승인이 있습니다). 교회, BLOG (베이지안 논리), 피가로 등의 언어를 확인하고 싶을 수도 있습니다. 그러나 최근의 연구 주제이며 사용하기 쉽지 않습니다.

출처

2015-03-12 18:40:39 user118967

불확실성에 대한 제약 조건 만족

답변

관련 문제