9.7. Усвоение понятий

Обучение в основном заключается в том, чтобы путем абстракции и индукции усвоить общую ситуацию, исходя из небольшого числа примеров. Этот процесс можно направлять и ускорять, используя контрпримеры, которые будут теперь произвольными, а не только “почти примерами”. Рассматриваемые ситуации могут быть достаточно сложными, и для их представления может применяться несколько вложенных уровней с операциями разъединения и отрицания. Это позволяет, в частности, хранить в резерве все возможности проверки сходства и различия между ситуациями.

Сначала обратим внимание на механизм абстрагирования.

Абстракция и обобщение

Обычная унификация основана на подстановке термов на место переменных. Такие подстановки по природе являются дедуктивными и строгими. Обобщать — это идти как раз в противоположном направлении: рассматриваемый терм становится абстрактным, когда он заменяется на переменную. В подстановке такого типа, которую называют индуктивной, необходимо уточнять, в каком случае данный терм нужно заменить, так как в отличие от унификации здесь нет вынужденных подстановок.

Например, ничто не обязывает повсюду заменять некоторый терм одной и той же переменной.

Индуктивная подстановка О характеризуется, следовательно, последовательностью троек:

где — терм, — экземпляр, замененная переменная.

Пусть имеется следующее выражение :

Дедуктивная подстановка

преобразует Е в выражение

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

Так как для проверки соответствия системы необходимо возвращаться к исходным примерам, в дальнейшем в индуктивных подстановках мы потребуем следующее:

1) двум разным объектам соответствует одна переменная;

2) повторно используются переменные того выражения, которое обобщается.

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

Таким образом, выражение

является более общим, чем

потому что существует постановка

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

В нашем примере сцеплением является

а дополнением —

Разумеется, для данных может существовать несколько подстановок которые удовлетворяют соотношению

В частности, они могут давать одинаковые сцепления и разные остатки.

Можно рассматривать разные подходы к определению индуктивных подстановок: от жестких, когда требуется минимальное число изменений, до самых свободных, разрешающих любые подстановки. Мы ограничимся классом допустимых подстановок, которые но определению удовлетворяют (кроме указанных выше требований 1) и еще двум новым требованиям:

3) один и тот же терм заменяется во всех подстановках на одну и ту же переменную;

4) терм заменяется только в случае необходимости, в частности терм из остатка заменяется только в том случае, если он заменен в сцеплении.

Теперь можно не указывать разные случаи расположения термов в допустимых подстановках.

Из этого определения следует, что всякое выражение является собственным обобщением, а также обобщением любого выражения, выводимого из него простым переименованием переменных.

Обобщение выражения будет строгим тогда и только тогда, когда 30, для которого (строго) или при условии, что переименование.

Отношение влечет за собой отношение но не наоборот. Так же как в арифметике вводится наибольший общий делитель или максимум в булевой алгебре, можно определить — общее максимальное обобщение двух выражений следующим образом:

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

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

Например,

“Некоторое тело находится на красном объекте, И на этом красном объекте нет другого объекта, отличного от куба, ИЛИ же у не является кубом”.

Заметим, что в этих описаниях обозначение

более предпочтительно, чем

из-за простоты процесса обучения, связанного с первым вариантом.

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

Однако член может теперь поправить слишком сильно, что приведет к исключению некоторых примеров. Так появляется новое условие с отрицанием и т. д. Так как исходные формулы конечны и общее число возможных случаев также конечно, процесс обязательно сходится к некоторому конечному выражению. В наихудшем случае оно будет представлять просто объединение всех отдельных предъявленных ситуаций. В

общем случае Е будет трансформироваться в более компактное выражение С, которое в сжатой форме отразит характеристики, разделяющие примеры и не встречающиеся в контрпримерах. Общая форма С имеет вид

Она сразу указывает на аналогию со знакопеременными сходящимися рядами вида

Последовательные члены представляют собой символические выражения, а не мономы, принимающие числовые значения.

Проиллюстрируем процедуру построения общего максимального обобщения С на следующем примере. Система получает описания четырех примеров и четырех контрпримеров (рис. 9.14).

Общим максимальным обобщением для четырех примеров будет

Контрпример исключается, так как куб в не зеленый. Однако покрываются и их следует исключить добавлением корректирующего члена Этот член должен устранить остатки для и 4 и соответствующих

Выражение должно покрывать эти три новых примера; оно принимает значение их общего максимального выражения которое в данном случае достаточно простое:

Описание искомого понятия принимает вид

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

Рис. 9.14. Примеры (а) и контр-примеры (б) при изучении понятия.

а) Примеры Описание:

б) Контр-примеры

Описание.

остается множитель который является собственным ОМО и последним корректирующим членом. Таким образом, описание понятия, которое определяется рис. 9.14, принимает окончательную форму

Может оказаться, что процедура формирования общего максимального обобщения приведет на каком-то этапе не к одному, а к нескольким выражениям. Разъединения в таком случае

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

Программа С. Вере написана на языке ICECUBE — диалекте языка SNOBOL — и производит обобщения за несколько секунд на машине IBM 370/158. Она также способна обобщать правила повторной записи, описывающие, например, сборку конструкций из кубиков и обратную процедуру разбора. Хотя эту программу следовало бы усовершенствовать, обогатив словарь описаний другими типами отношений, она представляется одной из лучших программ, хорошо формализованных и пригодных для задач обучения. Усваиваемые при этом понятия обладают достаточной сложностью, которая, возможно, превышает сложность тех понятий, которые может сформировать и запомнить сам человек.