Обобщение, уточнение и тэта-классификация

Как обычно принято в области машинного обучения, пространство возможных гипотез в методе ILP является частично упорядоченным с помощью отношений обобщения "более общий, чем" или "более конкретный, чем". Гипотеза Bi является более общей, чем .-._, если Hi охватывает, по меньшей мере, все случаи, охваченные с помощью Н_:. Применяемый оператор усовершенствования соответствует подобному отношению обобщения между гипотезами. Это отношение обобщения между гипоте­зами может быть определено синтаксически — усовершенствования представляют собой просто синтаксические операции над гипотезами.

В методе ILP часто используется еще одно отношение обобщения, называемое мята- классификацией. Несмотря на то что в программах этой главы тэта-классификация непосредственно не применяется, рассмотрим здесь эту тему для полноты изложения.

!

Часть II. Применение языка Prolog в области искусственного интеллекта

Вначале определим понятие подстановки 6 (тэта). Подстановка 6 = {Varl/Terml, Var2/Term2, . . . } представляет собой отображение переменных Varl, Var2 и т.д. на термы Terml, Term2 и т.д. Подстановка 9 применяется к предложению С путем замены переменных предложения термами в соответствии с отображением, заданным в 9. Результат применения подстановки 9 к приложению С записывается в виде С9, например, как показано ниже.

С = has_daughter(X) :- parent(X,Y), female(Y). Э = { X/tom, Y/liz} CG = has_daughter(torn) :- parent(torn,liz), female(liz).

Теперь мы можем определить понятие тэта-классификации. Оно представляет собой отношение обобщения между предложениями. Предложение тэта-классифи-цирует предложение С..-, если существует подстановка 9, такая, что каждый литерал в CiO встречается в с_;. Например, предложение

parent(X,Y).

может служить для тэта-классификации предложения

parent(X,liz) .

где 9 = ( Y/liz) , а предложение

has_daughter(X) :-parent(X, Y) .

может служить для тэта-классификации предложения

has daughter(X) : - parent(X,Y), female(Y) .

где 9 = { }. Понятие тэта-классификации может стать основой способа синтаксиче­ской проверки существования отношения обобщения между предложениями. Если предложение с, тэта-классифицирует предложение Сг, то С логически следует из с_ь поэтому Ci является более общим, чем С₂. Таким образом, с наряду с остальными гипотезами позволяет истолковать (или, как принято называть эту ситуацию, ох­вати тъ), по меньшей мере, все примеры, охваченные предложением с и остальны­ми гипотезами. Между применяемым оператором усовершенствования и тэта-классифи­кацией существует простая связь. Оператор усовершенствования принимает предложе­ние и вырабатывает предложение с , такое, что с тэта-классифицирует Сг.