§ 41. Вероятностный семантический вывод

Определение 36. Семантическим вероятностным выводом (P-выводом) произвольного атома A сигнатуры W будем называть максимальную последовательность правил C₁ ⊏ C₂ ⊏ ...; C₁, C₂, ... Î P(M); , i = 1, 2, ... такую, что атом A унифицируем с атомами A₁, A₂, ... . Если такой последовательности не существует, то P-вывод пуст.

2. Каждому P-выводу соответствует последовательность подстановок q₁, q₂, ... определения 6.1 отношения Ø. Подстановку q = q₁q₂ ... будем называть результатом вероятностного вывода.

Последнее правило в конечном P-выводе будем называть результирующим.

Лемма 19. D-правило в P-выводе может быть только результирующим.

P-деревом семантического вероятностного вывода атома A будем называть совокупность всех P-выводов (возможно пустую) цели A.

Определение 37. P-предсказанием некоторого атома A сигнатуры W программой PR(M, N) = P(M)ÈD(N) будем называть такой P-вывод C₁ ⊏ C₂ ⊏ ... ⊏ C_i ⊏ ...; C₁, C₂, ..., C_i, ... Î P(M) цели A, в котором:

1) существует правило и подстановка q, такие что { } Ì D(N); Aq = A_iq; m(A_iq) < m(C_i);

2) на правиле C_i достигается максимум условной вероятности m(C_i) среди всех правил, удовлетворяющих условию 1, всех P-выводов цели A;

3) если P-дерево вывода цели A пусто или требуемой подстановки не существует, то P-предсказание не определено;

4) результатом P-предсказания будем называть подстановку q_p = q₁q₂...q_i-1q, где q₁, q₂, ..., q_i-1 – подстановки P-вывода C₁ ⊏ C₂ ⊏ ... ⊏ C_i ;

5) оценкой P-предсказания будем называть величину h_p(A) = m(C_i). Если P-предсказание не определено, то оценка h_p(A) не определена.

Теорема 14. P-предсказание атома A сигнатуры W программой PR(M, N) = P(M) È D(N) определено тогда и только тогда, когда существует наилучшее для предсказания атома A правило C по данным D(N) в вероятностной модели данных M. Если P-предсказание атома A программой PR(M, N) определено, то оно осуществляется P-выводом, содержащим наилучшее для предсказания атома A правило C. Оценкой P-предсказания является величина h_p = m(C).

Доказательство: Пусть C – наилучшее для предсказания атома A правило C = A^’ ¬ B₁, ..., B_l. Тогда, по теореме, C Î P(M) Ì PR(M, N). В силу свойства 1 (определение 34) атом A унифицируем с атомом A’. Отсюда следует, что существует P-вывод, содержащий правило С. Из свойства 1 (определение 34) следует свойство 1 (определение 37). Следовательно, P-предсказание атома A определено.

Если P-предсказание определено, то существует, по крайней мере, одно правило C = A^’ ¬ B₁, ..., B_l, l ³ 1, C Î PR0 (так как C Î PR(M, N)) и подстановка q такие, что Aq = A^’q, {B₁q, ..., B_lq} Ì D(N), m(C) > m(A^’q). Таким образом, необходимые условия наилучшего для предсказания правила выполнены и, следовательно, наилучшее для предсказания правило существует.

Докажем вторую часть теоремы. Из первой части доказательства следует, что существует P-вывод, содержащий наилучшее для предсказания атома A правило C. В силу свойства 2 (определение 34) на этом правиле достигается максимум условной вероятности среди правил, удовлетворяющих условию 1 (определение 34) Но как показано в первой части доказательства, условию 1 (определение 34) удовлетворяют все правила P-дерева вывода цели A, которые могут использоваться для предсказания (удовлетворяют условию 1 (определение 37)). Отсюда следует свойство 2 (определение 37) P-предсказания ■