Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 247
Текст из файла (страница 247)
главу 9); в этой аналогии дизьюнкция гипотез соответствует выражению, а пример соответствует литералу, который взаимно уничтожается с одним из литералов выражения. Поэтому в принципе может быть обеспечено обучение на примерах обычной системы логического вывода путем удаления одной или нескольких гипотез. В частности, предположим, что пример оформлен в виде высказывания т„а пространство гипотез представляет собой высказывание н,чН,чн,чн,. В таком случае, если высказывание 7, несовместимо с выражениями и, и Им то система логического вывода может сформировать новое высказывание н,чн„соответствующее уточненному пространству гипотез. Таким образом индуктивное обучение в логической постановке задачи можно охарактеризовать как процесс постепенного устранения гипотез, несовместимых с примерами, и сужения пространства возможных гипотез.
Но поскольку пространство гипотез обычно является колоссальным (или даже бесконечным, в случае логики первого порядка), не рекомендуется даже пытаться создать систему обучения с использованием доказательства теорем на основе резолюции и полного перебора пространства гипотез. Вместо этого в этой главе будут описаны два подхода, которые позволяют находить логически совместимые гипотезы с гораздо меньшими усилиями.
Поиск текущей наилучшей гипотезы В основе метода поиска 'еь текущей наилучшей гипотезы лежит подход, предусматривающий сопровождение единственной гипотезы и ее корректировку по мере поступления новых примеров в целях поддержки совместимости. Основной алгоритм этого метода был впервые описан Джоном Стюартом Миллом 11049), но вполне мог быть изобретен еше раньше. Предположим, что в нашем распоряжении имеется определенная гипотеза, скажем н„которая нас полностью устраивает. До тех пор пока каждый новый пример остается с ней совместимым, не нужно ничего делать. Наконец, вслед за ними поступает ложно отрицательный пример, х, Что теперь следует делать? На рис. 19.1, а гипотеза н„показана схематически в виде области; все, что находится внутри прямоугольника, входит в состав расширения Н„.
Примеры, которые фактически встретились до сих пор, показаны как "~" или "-", и рисунок наглядно демонстрирует, что гипотеза н„правильно классифицирует все примеры как положительные или отрицательные примеры предиката Ю11ггазе. Показанный на рис. 19.1, бновый пример (обозначенный кружком) является ложно отрицательным — в гипотезе утверждается, что он должен быть отрицательным, но фактически этот пример положителен. Расширение гипотезы должно быть увеличено с целью его включения. Такая операция называется 'ъ. обобщением; одно из возможных обобщений показано на рис. 19.1, е.
После этого на рис. 19.1, г показан ложно положительный пример— в гипотезе утверждается, что новый пример (обозначенный кружком) должен быть положительным, но фактически этот пример отрицателен. Расширение гипотезы должно быть уменьшено в целях исключения данного примера. Такая операция называется 'в. уточнением; на рис. 19.1, д показано одно из возможных уточнений данной гипотезы.
Отношения "более общий чем" и "более конкретный чем" между гипотезами позволяют создать пространство гипотез с такой логической структурой, которая дает возможность осуществлять эффективный поиск. Глава 19. Применение знаний в обучении 907 Поэтому, чтобы сформировать обобщение гипотезы н„необходимо просто найти определение Гм которое логически следует из Сг. Такая задача решается довольно легко. НаПРИМЕР, ЕСЛИ Сг(Х) ПРЕДСтаВЛЯЕтСОбОй ВЫСКаЗЫВаНИЕА1ЕЕтПатЕ(Х) ЛРастОП5(Х, 5ОЛгЕ), тО ОДНО ИЗ ВОЗМОЖНЫХ ОбОбШЕНИй Заластеа В ВИДЕ Сг (Х) ЕРаетОП5 (Х, 5ОЮЕ) .
Такая форма операции обобщения называется ох удалением условий. Интуитивно ясно, что в результате такой операции формируется более слабое определение и поэтому гипотеза допускает использование более крупного множества положительных примеров. Может быть также предусмотрен целый ряд других операций обобщения, в зависимости от языка, в котором выражаются эти операции. Аналогичным образом, уточнение гипотезы может осуществляться путем введения дополнительных условий в ее потенциальное определение или путем удаления дизъюнктов из какого-то дизъюнктивного определения.
Рассмотрим, как могут быть выполнены подобные операции в задаче с рестораном, используя данные, приведенные в табл. 18.1. ° Первый пример, х,, является положительным. Выражение А1сетпасе(х,) имеет истинное значение, поэтому допустим, что начальная гипотеза имеет такой вид: Нг: )гх Яг111На1е(х) аг А1еетпаее(х) ° Второй пример, х„ отрицателен. Гипотеза и, предсказывает, что он должен быть положительным, поэтому данный пример — ложно положителен. Это означает, что необходимо уточнить гипотезу и,.
Это можно сделать, введя дополнительное условие, позволяющее исключить пример х,. Один из возможных вариантов состоит в следующем: нг: Ух нг11наге(х) ао А1еетпасе(х) л Растепа(х,5оаге) ° Третий пример, Х,, является положительным. Гипотеза Н, предсказывает, что он должен быть отрицательным, поэтому данный пример — ложно отрицательный. Это означает, что необходимо обобщить гипотезу и,. Удалим условие А1 еетпа се и получим следующее: Нг: )(Х Нг11магс(Х) СО Растаоа(Х,НОПЕ) ° Четвертый пример, х4, также положителен.
Гипотеза и, предсказывает, что он должен быть отрицательным, поэтому данный пример — ложно отрицательный. Это означает, что необходимо обобщить гипотезу и,. Условие Ра стопа удалить нельзя, поскольку такая операция приведет к созданию всеохватывающей гипотезы, которая будет несовместимой с примером х,.
Одна из возможностей состоит в добавлении дизъюнкта: Нгл ггх Н111махе(х) ао Растопа(х,Ноте) (Растепа (х, Ри11) л Ртз/5ас (х) ) Итак, гипотеза уже начинает выглядеть как приемлемая. Очевидно, что есть и другие варианты, совместимые с первыми четырьмя примерами; ниже приведены два из них. )гх н111нахе(х) аг наъенае1лгаее(х,30-60) н4' ': )(х вг111нахе(х) ао Раетопа(х,вота) и(Растопа(х,ли11) л НагЕЕасггвасе(х,10-30) ) 908 Часть У1. Обучение Алгоритм Сигсепс-иезс-ъеагпйпд описан здесь в недетерминированной форме, поскольку в любой момент может существовать возможность применить несколько вариантов уточнения или обобщения.
Выбранный вариант не всегда обеспечивает получение простейшей гипотезы и может привести также к безвыходной ситуации, в которой ни одна простая модификация гипотезы не будет совместимой со всеми данными. В подобных случаях программа должна выполнить возврат к предыдущей точке выбора. Алгоритм Оихсепс-Иезв-Ъеагпапп и его варианты использовались во многих системах машинного обучения, начиная с программы "обучения распознаванию арок" Патрика Уинстона [1602). Однако при большом количестве экземпляров примеров и большом пространстве гипотез возникают некоторые описанные ниже трудности. 1.
В алгоритме снова и снова проводится проверка всех предыдущих экземпляров при каждой модификации, а это требует больших затрат. 2. Процесс поиска может быть связан с очень интенсивным перебором с возвратами. Как было показано в главе 18, размеры пространства гипотез могут определяться двойной экспоненциальной зависимостью. Поиск на основе оценки наименьшего вклада Перебор с возвратами нозникает из-за того, что в подходе, предусматривающем поиск текущей наилучшей гипотезы, приходится выбирать конкретную гипотезу как наилучшее текущее предположение, даже несмотря на то, что еще отсутствует достаточный объем данных, позволяющий убедиться в правильности этого выбора. Вместо этого можно было бы просто "держать под рукой" те и только те гипотезы, которые являются совместимыми со всеми поступившими до сих пор данными. В таком случае каждый новый экземпляр данных либо не оказывает никакого влияния на состав гипотез, либо позволяет избавиться от некоторых гипотез.
Напомним, что первоначальное пространство гипотез может рассматриваться как следующее дизъюнктивное высказывание: Н1 и н| ч нз ж ... и и„ По мере обнаружения того, что различные гипотезы являются несовместимыми с примерами, эта дизъюнкция сужается и остаются только те гипотезы, которые еще не исключены. Это означает, что при условии, что первоначальное пространство гипотез действительно содержит правильный ответ, этот правильный ответ должен также содержаться в сокращенной дизъюнкции, поскольку были удалены только неправильные гипотезы.
Множество оставшихся гипотез называется 'сь пространством версий, а соответствующий алгоритм обучения (приведенный в листинге 19.2) называется алгоритмом обучения в пространстве версий (а также алгоритмом 'ш. удаления потенциальных гипотез). Листинг 19.2. Алгоритм обучения в пространстве версий. Он находит подмножество гипотез зг, совместимое с примерами вхамрзен Еипосьоп уегзьоп-Брасе-Ьеатпъпд[ехатрзез1 гесихпн пространство версий 1ооа1 жахьаЪ1ен: и', пространство версий — множество всех гипотез и' с в множество всех гипотез 909 Глава 19.
Применение знаний в обучении хот еаоЬ из примеров е в множестве примеров ехаглр1ез Е)о Ьв множество у не пусто Еиеп у < — уегвзоп-Брасе-црааое(у, е) вееитп випоеьоп чегзьоп-Брасе-прдаее(у, е) тееижпв обновленное пространство версий Гг е- (Л е Го гипотеза )з совместима с е) Одним важным свойством этого алгоритма является то, что он инкрементный,— при его использовании никогда не приходится возвращаться и повторно исследовать старые примеры, поскольку в любом случае гарантируется, что оставшиеся гипотезы остаются совместимыми с ними. Этот алгоритм также представляет собой алгоритм поиска с наименьшим вкладом, поскольку в нем не используются произвольные варианты выбора (сравните его с алгоритмом планирования с частичным упорядочением, который приведен в главе 11).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
