Упражнение. 19.2.Определите, сколько этапов усовершенствования требуется для получения це­ левой гипотезы из заданной выше начальной гипотезы

19.2.Определите, сколько этапов усовершенствования требуется для получения це­
левой гипотезы из заданной выше начальной гипотезы.

Теперь можно попытаться вызвать на выполнение программу MINIHYPER с этим определением задачи, но оказывается, что данная программа является для этого слишком неэффективной. Пространство поиска вплоть до требуемой глубины усо­вершенствования для нее слишком велико. Кроме того, процедура поиска повторно вырабатывает одинаковые гипотезы, достижимые с помощью разных путей усовер­шенствования. Это приводит к повторному формированию больших подпространств.

Доработка программы MINIHYPER с целью создания программы HYPER будет выполнена в следующем разделе. Тем не менее можно достаточно просто обеспечить успешное применение программы MINIHYPER для решения задачи изучения отно­шения predecessor с помощью следующего приема. Для управления сложностью поиска (не без привлечения своей "догадки" о том, каким будет результат обучения) мы можем ввести такое ограничение, что фоновые литералы parent (X,Y) и predecessor Y) должны вызываться с конкретизированным первым параметром X. Этого можно добиться, потребовав, чтобы X был атомом, т.е. применив следующее модифицированное определение фоновых знаний:

backliteraK [atom(X), parent (X, Y) ] , [X,Y]). backliteraK [atom(X) , predecessor (X, Y) ] , [X,Y]). prolog_predicate( parent(X,Y)). prolog_predicate( atom(X)).

Это означает, что при каждом усовершенствовании предложения к нему добавля­ется пара литералов и первым из них является литерал atom(X) . При проверке пол­ноты такой гипотезы попытка достижения цели в теле предложения оканчивается

Глава 19.Индуктивное логическое программирование 457


неудачей, если параметр X не конкретизирован (эта проверка осуществляется с по­мощью предиката atom(X)). Таким образом, многие бесполезные гипотезы станут неполными и поэтому будут немедленно исключены из процесса поиска. Теперь за­дача поиска становится проще, хотя и может все еще потребовать много времени, ко­торое составляет целые минуты или десятки минут, в зависимости от компьютера и реализации Prolog. В конечном итоге выполнение цели induce (H) приводит к полу­чению следующего результата:

Н = [[predecessor(А,В), [atom(A),parent(А,С)], [atom(С),predecessor <С,Б)]] / [А, С, В] , Ipredecessor(D,E) , [atom(D), parent(D,EJ ] ]/[D,E])

Безусловно, что этот результат представляет собой искомое определение отноше­ния predecessor.

Вполне очевидно, что программа MINIHYPER вскоре окажется полностью непри­годной, столкнувшись с более сложными задачами обучения. Поэтому в следующем разделе в нее будет введено несколько полезных дополнений.