Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 246
Текст из файла (страница 246)
2 и О. 4. Возможно ли, что ошибка алгоритма обучения ансамбля будет хуже, чем в, если предположение о независимости будет исключено? 18.15.Это упражнение касается вопроса о выразительности списков решений (раздел !8.5). а) Покажите, что списки решений позволяют представить любую булеву функцию, если размер проверок не ограничен. б) Покажите, что если проверки могут включать самое большее?г литералов каждая, то списки решений позволяют представить любую функцию, которая может быть представлена с помощью дерева решений с глубиной )г. В этой главе рассматривается задача обучения в тех условиях, когда узке кое-что известно. Во всех подходах к обучению, описанных в предыдуших трех главах, основная идея состоит в том, что должна быть сформирована функция, входные и выходные данные которой соответствуют закономерностям, наблюдаемым в данных.
В каждом подобном случае методы обучения можно рассматривать как поиск в пространстве гипотез для обнаружения подходящей функции, начиная только с очень простых предположений о форме этой функции, таких как "полином второго порядка" или "дерево решений", и руководствуясь такими критериями, как "чем проще, тем лучше". Применение такого подхода равносильно требованию, что перед началом изучения чего-либо нового необходимо в первую очередь забыть (почти) все, что вы знаете. А в данной главе рассматриваются методы обучения, позволяющие воспользоваться Ъ. априорными знаниями о мире. В большинстве случаев априорные знания представлены в виде общих логических теорий первого порядка, поэтому вначале в этой главе необходимо систематизировать сведения о представлении знаний и обучении.
19.1. ЛОГИЧЕСКАЯ ФОРМУЛИРОВКА ЗАДАЧИ ОБУЧЕНИЯ В глава !8 было дано определение чисто индуктивного обучения как процесса поиска гипотезы, которая согласуется с наблюдаемыми примерами. В данной главе это определение уточняется и распространяется на тот случай, когда гипотеза представлена в виде множества логических высказываний. Описания примеров и определения классов также заданы в виде логических высказываний, а классификация нового примера может быть выполнена путем логического вывода классификационного высказывания из гипотезы и описания примера.
Такой подход обеспечивает инкрементное формирование гипотез путем послеловательного добавления каждый раз по одному предложению. Он также дает возможность использовать априорные знания, поскольку уже известные высказывания могут помочь при классификации новых примеров. На первый взгляд может показаться, что логическая формулировка 903 Глава 19. Применение знаний в обучении задачи обучения требует выполнения вначале больцюго объема дополнительной работы, но, как оказалось, она позволяет прояснить многие нерешенные проблемы обучения. Указанный подход дает возможность намного превзойти простые методь) обучения, описанные в главе !8, поставив на службу обучению всю мощь логического вывода. Примеры и гипотезы Вернемся к описанной в главе 18 задаче обучения с рестораном, в которой нужно было изучить правило принятия решения о том, при каких условиях следует ждать освобождения столика.
В этой главе для описания примеров применялись атрибуты, такие как А1 сетпа се, Ват, Рту/Вас н тд. В логической формулировке задачи любой пример представляет собой объект, для описания которого используется логическое высказывание, а атрибуты становятся унарными предикатами. Примем общее обозначение Х, для 1-го примера. В частности, первый пример, приведенный в табл. 18.1, может быть описан с помощью таких высказываний: А1сегпате(Х1) л Ваг(Х1) л лРг1!Нас(Х~) л Нипдгу(Х1) л Обозначение )э, (х,) будет использоваться для ссылки на описание х., где (э, может представлять собой любое логическое выражение, принимающее один параметр.
Классификация объекта определяется примерно таким высказыванием: )г111и .г (х ) Общее обозначение О(Х,) будет применяться, если пример является положительным, а — р(х,) — если отрицательным. В таком случае полное обучающее множество представляет собой конъюнкцию всех описательных и классификационных высказываний. Пелью индуктивного обучения в логической постановке задачи является поиск эквивалентного логического выражения для целевого предиката (э, который может использоваться для правильной классификации примеров. Подобное выражение, которое мы будем называть 'в.потенциальным определением целевого предиката, предлагается в каждой гипотезе.
Используя с, для обозначения потенциального определения, можно утверждать, что каждая гипотеза и, представляет собой высказывание в форме Чх О(х) ~=>С, (х) . В частности, дерево решений представляет собой утверждение, что целевой предикат принимает истинное значение по отношению к какому-то объекту тогда и только тогда, когда выполняются условия в одной из ветвей, ведущих к листовому узлу со значением етое. Таким образом, на рис. 18.4 в графической форме выражено следующее логическое определение (которому мы присвоим обозначение н, для использования его в будущем): Чг Ы11)га1е(г) ао Раетопе(т, Ноте) и Растепа(г,уи11) л Нипдгу(г) л Туре(г,ргепол) и Ратгопь (г, Ри11) л Нипдгу(т) л Туре(г, Тлад) л Рг1!Яае(г) и Ратгопе(г,уи11) л Нипдту(т) л Туре(т,Вигдег) (19.1) Каждая гипотеза предсказывает, что некоторое множество примеров (а именно множество тех примеров, которые соответствуют ее потенциальному определению) будет представлять собой примеры целевого предиката.
Такое множество называется 904 Часть ЪЧ. Обучение св расширением предиката. Это означает, что две гипотезы с разными расширениями являются логически несовместимыми друг с другом, поскольку они не согласуются в своих предсказаниях по меньшей мере в одном примере. А если две гипотезы имеют одно и то же расширение, они логически эквивалентны. Пространство гипотез н алгоритма обучения представляет собой множество всех гипотез (и,, ...и„), лля полдержки которых предназначен данный конкретный обучаю)ций алгоритм.
Например, алгоритм песувуоп-тгее-ьеагпупд способен поддерживать любую гипотезу в дереве решений, определенную в терминах заранее предусмотренных атрибутов, поэтому пространство гипотез этого алгоритма состоит из всех таких деревьев решений. Предполагается, что алгоритм обучения позволяет с полной уверенностью утверждать, что одна из гипотез является правильной; это означает, что данный алгоритм выражает опрелеленную степень уверенности в истинности следующего высказывания: (19.21 Нг ч Нз .
Нз ч,, о Н По мере поступления новых примеров появляется возможность исключать гипотезы, не совместимые с этими примерами. Рассмотрим более внимательно затронутое здесь понятие совместимости. Очевидно, что если гипотеза н, совместима со всем обучающим множеством, то она должна быть совместимой с каждым примером.
А что повлекла бы за собой его несовместимость с одним из примером? Такая ситуация может проявиться в одном из двух описанных ниже вариантов. ° Некоторый пример может оказаться 'ж ложно отрицательным для данной гипотезы, если гипотеза утверждает, что он должен быть отрицательным, нофактически этот пример положителен.
В частности, новый пример хзм описанный выражением Раегопа(Хзз ° Ьц11) л На1С(хгз,0-10) л Нцпдгу(хзз) л ... л гг111над с (х ) был бы ложно отрицателен для гипотезы н„приведенной выше. Из гипотезы н„и описания этого можем вывести и выражение й)111)уаус(х„), которое как раз является утверждением данного примера, и выражение й)111йгаз с (х„), которое представляет собой предсказание самой гипотезы. Поэтому в данном случае гипотеза и пример логически несовместимы. ° Пример может быть 'ак ложно положительным для данной гипотезы, если в гипотезе утверждается, что он должен быть положительным, но фактически он является отрицательным'.
Если некоторый пример является ложно положительным или ложно отрицательным применительно к некоторой гипотезе, то данный пример и данная гипотеза являются логически несовместимыми друг с другом. При условии, что рассматриваемый пример представляет собой правильное наблюдение факта, такая ситуация позволяет исключить данную гипотезу. С точки зрения логики соответствующая операция исключения гипотезы полностью аналогична операции применения пра- ' Термины "ложно положительный" и "ложно отрицательный" используются также в медицине для описания ошибочных результатов лабораторных исследований Результат исследования является ложно положительным, если он указывает, что у пациента имеется диагностируемое заболевание, тогда как в действительности у пациента этого заболевания нет. 905 Глава 19. Применение знаний в обучении вила резолюции в логическом выводе (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
