Вероятность дизъюнкции на N зависимых событий в прологе

Question

Кто-нибудь знает, где найти алгоритм Пролога для вычисления вероятности дизъюнкции для N зависимых событий? Для N = 2 я знаю, что P (E1 ИЛИ E2) = P (E1) + P (E2) - P (E1) * P (E2), поэтому можно сделать:

prob_disjunct(E1, E2, P):- P is E1 + E2 - E1 * E2

Но как этот предикат может быть обобщен на N событий, когда входные данные являются списком? Может быть, есть пакет, который делает это?

С уважением / JCR

Answer 1

Рекурсивная формула из ответа Роберта Додье напрямую переводит на

p_or([], 0).
p_or([P|Ps], Or) :-
    p_or(Ps, Or1),
    Or is P + Or1*(1-P).

Хотя это работает отлично, например,

?- p_or([0.5,0.3,0.7,0.1],P).
P = 0.9055

хардкорные программисты Prolog не могут не заметить, что определение не является 't хвостовая рекурсия .Это действительно будет проблемой, только когда вы обрабатываете очень длинные списки, но поскольку порядок элементов списка не имеет значения, все легко изменить.Это стандартная техника, использующая вспомогательный предикат и «пару аккумуляторов» аргументов:

p_or(Ps, Or) :-
    p_or(Ps, 0, Or).

p_or([], Or, Or).
p_or([P|Ps], Or0, Or) :-
    Or1 is P + Or0*(1-P),
    p_or(Ps, Or1, Or).       % tail-recursive call

Answer 2

Я ничего не знаю о Прологе, но в любом случае удобно записать вероятность дизъюнкции ряда независимых элементов p_m = Pr (S_1 или S_2 или S_3 или ... или S_m) рекурсивно как

p_m = Pr(S_m) + p_{m - 1} (1 - P(S_m))

Вы можете доказать это, просто сняв последний элемент - посмотрите на Pr ((S_1 или ... или S_ {m - 1}) или S_m) и просто напишите это в терминах обычной формулы, записывая Pr (A или B) = Pr (A) + Pr (B) - Pr (A) Pr (B) = Pr (B) + Pr (A) (1 - Pr (B)), для A и Bнезависимый.

Формула выше - это пункт C.3.10 в моей диссертации: http://riso.sourceforge.net/docs/dodier-dissertation.pdf Это простой результат, и я полагаю, что это должно быть упражнение в некоторых учебниках, хотя я не помнювидя это.

Answer 3

Для любого события E я напишу E 'для дополнительного события (т. Е. E' происходит, если E нет).Тогда имеем:

P(E') = 1 - P(E)
(A union B)' = A' inter B'
A and B are independent iff A' and B' are independent

так что для независимого E1..En

P( E1 union .. union En ) = 1 - P( E1' inter .. inter En')
= 1 - product{ i<=i<=n | 1 - P(E[i])}