Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 248
Текст из файла (страница 248)
Но при использовании этого алгоритма возникает одна очевидная проблема. Как уже было сказано, пространство гипотез часто имеет огромные размеры; как же в таком случае можно записать соответствующую ему огромную дизъюнкцию? Для анализа этой ситуации можно применить следую)цую очень полезную простую аналогию. Как представить все действительные числа в интервале между 1 и 2? В конце концов, ведь количество этих чисел бесконечно велико! Ответ на этот вопрос состоит в том, что должно использоваться интервальное представление, в котором задаются границы этого множества, (1,21. Это представление применимо в связи с тем, что во множестве действительных чисел задано упорядочение.
В пространстве версий также существует отношение упорядочения, а именно отношение обобщения/уточнения. Но это — отношение частичного упорядочения, поэтому каждая граница пространства представляет собой не точку, а скорее множество гипотез, называемое заграничным миожесп)ом. Превосходной особенностью подхода, основанного на понятии граничного множества, является то, что он позволяет прелставить все пространство версий с использованием только двух граничных множеств — наиболее общего граничного множества ('ю б-множества, где Π— сокращение от яепега1) и наиболее конкретного граничного множества (Ъ. Я-множества, где б — сокращение от Брес!Вс).
При этом гарантируется совместимость с примерами всех версий, которые находятся в пределах между этими двумя множествами. Прежде чем перейти к доказательству этого утверждения, подытожим сказанное выше в настоящей главе. ° Текущее пространство версий представляет собой множество гипотез, совместимых со всеми примерами, встретившимися до сих пор, Это пространство представлено с помощью В- и О-множества, каждое из которых представляет собой множество гипотез.
° Каждый элемент В-множества является совместимым со всеми полученными до сих пор результатами наблюдений, и нет ни одной совместимой гипотезы, которая была бы более конкретной, чем этот элемент. ° Каждый элемент О-множества является совместимым со всеми полученными до сих пор результатами наблюдений, и нет ни одной совместимой гипотезы, которая была бы более общей, чем этот элемент. 912 Часть УЕ Обучение своими непосредственными уточнениями, при соблюдении условия, что они остаются более общими, чем любой элемент Б-множества. 4.
Ложно отрицательный пример для би Появление такого примера означает, что гипотеза С, является слишком конкретной, но (по определению) совместимое обобщение для гипотезы С, отсутствует, поэтому ее необходимо исключить из О-множества. Указанные выше операции продолжаются применительно к каждому новому экземпляру примера до тех пора, пока не произойдет одно из перечисленных ниже событий. 1. В пространстве версий останется одно и только одно определение некоторой концепции, и в этом случае оно будет возвращено как уникальная гипотеза. 2. Пространство версий свернется (либо Я-, либо О-множество станет пустым), и это будет означать, что для данного обучаюшего множества не существуют совместимые гипотезы.
Такая ситуация аналогична неудачному завершению поиска, которое возникает в простом варианте алгоритма формирования дерева решений. 3. Примеры закончатся, а в пространстве версий останется несколько гипотез. Это означает, что пространство версий представляет собой дизъюнкцию гипотез. Если при поступлении любого нового примера все дизъюнкты этой дизъюнкции согласуются, то можно возвратить определяемую ими классификацию данного примера. Если же они не согласуются, один из вариантов состоит в использовании мажоритарного голосования.
Рекомендуем читателю в качестве упражнения попытаться применить алгоритм Уегэзоп-Ярасе-Ьеахпзпд к данным о ресторане. Описанный здесь подход к использованию пространства версий характеризуется описанными ниже принципиальными недостатками. ° Если проблемная область характеризуются наличием шума или недостаточного количества атрибутов для точной классификации, то пространство версий всегда свертывается.
° Если в пространстве гипотез допускается наличие неограниченного количества дизъюнкций, то Я-множество всегда будет содержать единственную наиболее конкретную гипотезу, а именно дизъюнкцию описаний положительных примеров, встретившихся до сих пор. Аналогичным образом, О-множество будет содержать просто отрицание дизъюнкции описаний отрицательных примеров. ° Для некоторых пространств гипотез количество элементов в Я- или в С-множестве может увеличиваться в экспоненциальной зависимости от количества атрибутов, что не позволяет решить задачу обучения, даже несмотря на то, что для этих пространств гипотез существуют эффективные алгоритмы обучения. Полностью эффективное решение проблемы шума не найдено до сих пор. Проблемы дизъюнкции можно решить, допуская использование ограниченных форм дизъюнкции или включая ек иерархию обобщения более обших предикатов.
Например, вместо применения дизъюнкции (уадедэеуглаее(х,ЗО-б01 ч ыаХедэсдтасе(х,>60) можно Глава 19. Применение знаний в обучении 913 ввести в действие единственный литерал г спдвгаз с (х) . Для реализации такого полхола можно легко дополнить множество операций обобщения и уточнения. Рассматриваемый в этом разделе чистый алгоритм сопровождения пространства версий был впервые применен в системе Мега-ГЗепг(га!, которая была предназначена для изучения правил предсказания того, как молекулы разделяются на фрагменты в массовом спектрометре [202). Система Мега-Г)епдга! показала свою способность вырабатывать правила, которые оказались достаточно новаторскими, чтобы гарантировать их публикацию в журнале аналитической химии; это были первые реальные научные знания, полученные с помощью компьютерной программы.
Такой алгоритм использовался также в изящной системе Ьех [!066), которая проявила способность к обучению методам решения задач символического интегрирования, анализируя свои собственные удачи и неудачи. Хотя методы сопровождения пространства версий, по-видимому, не могут найти практического применения в большинстве реальных задач обучения, в основном из-за проблемы шума, они позволяют многое понять в отношении того, какова логическая структура пространства гипотез. 19.2. ПРИМЕНЕНИЕ ЗНАНИЙ В ОБУЧЕНИИ В предыдущем разделе описывалась простейшая постановка задачи индуктивного обучения.
А в этом разделе речь пойдет о логических связях между гипотезами, описаниями примеров и классификациями, что позволяет понять роль априорных знаний. Допустим, что реясл1рг!опя обозначает конъюнкцию всех описаний примеров в обучающем множестве, а С2аяяз Гаса азспя — конъюнкцию всех классификаций примеров. В таком случае гипотеза, которая позволяет "объяснить результаты наблюдений", должна удовлетворять следующему свойству (напомним, что 1 означает "влечет за собой логически"): нурселеяця л пеясгтреколя 1 с1аяяцексаезоля (19.31 Мы будем называть связь такого рода 'ск ограничением логического следствия, в котором нурса)зеяз я представляет собой "неизвестное".
Чисто индуктивное обучение сводится к разрешению этого ограничения, притом что гипотеза нурса)з еяз я извлекается из некоторого заранее определенного пространства гипотез. Например, если дерево решений рассматривается как логическая формула (см. уравнение 19.1), то дерево решений, совместимое со всеми примерами, будет удовлетворять уравнению 19.3. Если же на логическую форму гипотезы не налагаются никакие ограничения, то, разумеется, условие нурса!зеязя=С1аяязйзса сзспя также удовлетворяет этому ограничению.
Согласно принципу бритвы Оккама, следует отдавать предпочтение небольшим, совместимым гипотезам, поэтому мы должны попытаться найти лучшее решение, чем просто запоминание примеров. Такой простой подход к индуктивному обучению, в котором не предусматривалось использование знаний, господствовал в искусственном интеллекте до начала 1980-х годов. А современный подход состоит в том, что должны проектироваться агенты, которые сге улсе хое-что злаков и пытаются освоить в процессе обучения некоторую дополнительную информацию. На первый взгляд открытие, приведшее к такой смене подходов, не кажется чрезвычайно глубоким, но оно стало причиной 914 Часть УЕ Обучение весьма существенного изменения способа проектирования агентов.
Кроме того, это открытие может иметь определенное отношение к рассматриваемым в данной книге теориям о том, как развивается сама наука. Общая идея этого открытия показана на рис. 19.4. Наблюдения Предсказания Рис. 19.4. Схема, которая показывает, как в процессе обучении с накоплением знание используется и со временем обогаицоется запас фоновых зниниб Если должен быть создан автономный обучающийся агент, который использует фоновые знания, то в этом агенте необходимо предусмотреть некоторый метод получения в первую очередь фоновых знаний, для того, чтобы их можно было использовать в новых эпизодах обучения. Применяемый при этом метод сам должен представлять собой процесс обучения. Поэтому история существования агента должна быть таковой, чтобы ее можно было охарактеризовать как поступательное, или инкрементное, развитие. Разумеется, что агент может начать свое существование без какого-либо запаса знаний, осуществляя индуктивные выводы в условиях отсутствия знаний, как и добрая старая программа чисто индуктивного вывода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
