§ 40. Предсказание и индуктивный синтез логических программ

Полный набор фактов для класса моделей G составляет совокупность множеств F(N) = {A ¬| A – atom, N ⊨ A для любого состояния атома A}, N Î G. Любую конечную совокупность D конечных подмножеств D(N) Ì F(N), N Î G будем называть данными. Вероятностную Эрбранову модель M, согласованную с классом G, будем называть вероятностной моделью данных D.

Как следует использовать правила C = A ¬ B₁, ..., B_k, k ³ 1 для предсказания? Если посылка правила (B₁& ... &B_k)q истинна на некоторой случайно выбранной из G в соответствии с мерой m модели N (при некоторой подстановке q Î Q: {B₁q, ..., B_kq} Ì F(N)), то заключение Aq истинно на N с вероятностью m(Aq / (B₁& ... &B_k)q) ³ m(A / B₁& ... &B_k) = m(C). Вероятность m(C), определенная в параграфе 5 для правил со свободными переменными, дает нам нижнюю границу вероятностей предсказания атома Aq. Заметим, что предсказание нужно делать по данным D(N) какой-то одной случайно выбранной из G модели N. Обозначим множество всех P-правил с посылкой, содержащей хотя бы один атом, через P(M) Ì PR(M).

Определение 34. Для атома A сигнатуры W и некоторых данных D(N) правило C = A^’ ¬ B₁, ..., B_k; k ³ 1, C Î PR0, не содержащее одинаковых переменных с атомом A, будем называть наилучшим для предсказания атома A правилом по данным D(N) в вероятностной модели M, если:

1) существует подстановка q Î QG такая, что {B₁q, ..., B_kq} Ì D(N),

Aq = A^’q; m(C) > m(Aq);

2) на правиле достигается максимум условной вероятности среди правил, удовлетворяющих условию 1 и сравнимых по условию {B₁q, ..., B_kq}(это подмножество должно включаться в подмножества других правил);

3) правило C максимально по отношению Ø среди правил, удовлетворяющих условиям 1, 2.

Теорема 13. Все наилучшие для предсказания какого-либо атома A сигнатуры W (по некоторым данным D(N), N Î G в вероятностной модели данных M) правила являются вероятностными закономерностями с непустой посылкой, т. е. принадлежат множеству P(M).

Доказательство: Пусть правило C = A^’ ¬ B₁, ..., B_k; k ³ 1; C Î PR0 является наилучшим для предсказания атома A по данным D(N), и для некоторой подстановки q^’ Î QG выполняются соотношения {B₁q^’, ..., B_kq^’} Ì D(N), Aq^’ = A^’q^’, m(C) > m(A^’q^’). Предположим противное, что C Ï P(M) и значит C Ï PR(M). Отсюда следует, что существует правило C^’ Ø C, C^’ ΠPR0, C^’ = A^” ¬ B^’₁, ..., B^’_l и подстановка q^”, A^”q^” = A^’, {B^’₁q^”, ..., B^’_lq^”} Ì {B₁, ..., B_k}, такие, что m(C^’) ³ m(C) > m(A^’q^’) ³ m(A^’). Так как A^”q^” = A^’, то m(A^’) ³ m(A^”) и, следовательно, m(C^’) > m(A^”). Отсюда следует, что посылка правила C’ не пуста и l > 1. Покажем, что правило C’ лучше правила C для предсказания атома A, что противоречит условию. Включение {B^’₁q^”q^’, ..., B^’_lq^”q^’} Ì {B₁q^’, ..., B_kq^’} Ì D(N), равенство Aq^’ = A^”q^”q^’ и неравенство m(C^’) ³ m(C) > m(A^’q^’) говорит о выполнении условия 1. Соотношения m(C^’) > m(C), C^’ Ø C противоречат выполнению условий 2, 3 для правила C ■

Определение 35. ПРОЛОГ-программой индуктивно синтезированной по данным D и вероятностной модели данных M будем называть множество правил PR(M, N) = P(M) È D(N), где D(N) Î D, N – некоторая модель, случайно выбранная из G в соответствии с вероятностной моделью данных M.