Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 244
Текст из файла (страница 244)
По мере того как достигается все лучшее понимание этих проблем, теория вычислительного обучения предоставляет все более ценную помощь исследователям в области машинного обучения, для которых важно предсказать или модифицировать обучающую способность созлаваемых ими алгоритмов. Кроме сп исков решений, важные результаты были получены почти для всех известных подклассов булевых функций, для множеств высказываний первого порядка 1глава 19) и для нейронных сетей (глава 20). Эти результаты показывают, что чистые задачи индуктивного обучения, в которых агент приступает к работе без априорных знаний о целевой функции, обычно являются очень трудными.
Как будет показано в главе 19, использование априорных знаний для управления индуктивным обучением дает возможность изучать весьма крупные множества высказываний на основе приемлемого количества примеров, даже если используется столь выразительный язык, как логика первого порядка. 18.6. РЕЗЮМЕ Настоящая глава главным образом посвящена изложению темы индуктивного обучения детерминированных функций на основе примеров. Основные вопросы, рассматриваемые в этой главе, перечислены ниже. 896 Часть 'Л. Обучение ° Обучение принимает много разных форм в зависимости от характера производительного элемента, компонента, подлежащего усовершенствованию, и доступной обратной связи.
° Если доступна обратная связь либо от учителя, либо от среды, позволяющая получать правильные значения, относящиеся к примерам, то задача обучения относится к типу контролируемого обучения. Такая задача, называемая также индуктивным обучением, сводится к изучению некоторой функции на примерах ее входных и выходных данных. Изучение функции с дискретными значениями называется классификацией; изучение непрерывной функции называется регрессией. ° Индуктивное обучение сводится к поиску совместимой гипотезы, которая согласуется с примерами. При этом должен соблюдаться принцип бритвы Оккама, согласно которому следует всегда выбирать наиболее простую совместимую гипотезу.
Сложность решения этой задачи зависит от выбранного способа представления. ° Деревья решений позволяют представить любые булевы функции. Эвристика, определяющая приращение информации, может стать основой эффективного метода поиска простого, совместимого дерева решений. ° Производительность обучающего алгоритма измеряется кривой обучения, которая показывает прогностическую точность применения алгоритма к проверочному множеству как функцию от размера обучающего множества.
° Методы обучения ансамбля деревьев решений, такие как усиление, часто показывают более высокую производительность по сравнению с методами обучения отдельных деревьев решений. ° Для анализа выборочной и вычислительной сложности индуктивного обучения применяется теория вычислительного обучения. Эта теория позволяет найти компромисс между выразительностью языка гипотез и легкостью обучения. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ История философских исследований в области индуктивного обучения описана вглаве 1.
Уильям из Окхема (!280 — !349), наиболее влиятельный философ своей эпохи, внесший в средние века наибольший вклад в развитие эпистемологии, логики и метафизики, заслужил признание потомков за то, что выдвинул важный принцип, называемый "бритвой Оккама", который на латыни выражается словами "Епйа поп ьвп1 шп11)р1!санда ргаегег песезз11агегп", а в переводе звучит так; "Не следует множить сущности без необходимости". К сожалению, это замечательное изречение не удалось найти в его трудах точно в такой формулировке.
Одной из первых систем, в которой использовались деревья решений (или, как они в ней именовались, различительные сети (йзсппппаг)оп пега)), была система ЕРАМ (Е!епзеп(агу Регсегхег Апг( Мешог!хег) Фейгенбаума 1457). Система ЕРАМ предназначалась для применения в качестве модели имитации познания в процессе обучения человека новым понятиям. В системе С).8 (707) для формирования деревьев решений использовался эвристический прогностический метод. В системе 1ОЗ Глава 18.
Обучение на основе наблюдений 897 [1256) была дополнительно реализована крайне важная идея о том, что для обеспечения функционирования эвристической функции может применяться информационное содержание. Сама теория информации была разработана Клодом Шенноном для использования в качестве средства исследования процессов связи [1394). Важный вклад, сделанный Шенноном, состоит также в том, что он разработал первые образцы систем, действующих по принципу машинного обучения, в частности механическую мышь, получившую имя Тпезецз (Тезей), которая обучалась прохождению через лабиринт по методу проб и ошибок. Метод у' отсечения ветвей деревьев был описан Куинланом [1257].
Описание пакета С4.5 производственного назначения, который основан на использовании деревьев решений, можно найти в [1259]. В литературе по статистике существует отдельное направление, посвященное исследованиям в области деревьев решений. Одним из основных источников информации по этой теме является книга С1ат~кагГоп апг) 71ехгеззьал Тгеез [180), известная под названием книги "С4йТ". Предпринимались также попытки применить многие другие алгоритмические подходы к обучению.
Подход, основанный на использовании текущей наилучшей гипотезы, предусматривает сопровождение единственной гипотезы, а также ее уточнение, если обнаруживается, что она слишком широка, и обобщение, если она оказывается слишком узкой. Такой принцип проведения исследований уже давно применяется в философии [1049].
Кроме того, даже ранние работы в области когнитивной психологии показали, что в этом состоит естественная форма изучения концепций людьми [199]. В искусственном интеллекте такой подход наиболее тесно связан с работой Патрика Уинстона, в докторской диссертации которого [1602) рассматривается проблема изучения описаний сложных объектов. В методе пространства версий [! 061], [1062] принят другой подход, в котором сопровождается множество всех совместимых гипотез и удаляются оказавшиеся несовместимыми с новыми примерами.
Такой подход был реализован в экспертной системе Мега-Рената!, применяемой в химии [202), а затем — системе Митчелла [.ех [1066], которая обучалась решению задач исчисления. Третье влиятельное направление возникло под влиянием работы Михальского и его коллег над рядом алгоритмов АО, применявшихся для изучения множеств логических правил [1038], [1041). Метод обучения ансамбля деревьев решений все чаще применяется для повышения производительности обучающих алгоритмов. Первый эффективный метод такого типа, называемый ск созданием мультимножеств [179], предусматривает формирование комбинаций гипотез, изученных на основе многочисленных наборов данных начальной загрузки, каждый из которых формируется путем выборки подмножества из первоначального множества данных.
Метод усиления, описанный в данной главе, впервые был изложен в теоретической работе Шейпира [1361]. Алгоритм лс1авоовс был разработан Фрейндом и Шейпиром [50!], а результаты его теоретического анализа приведены в [1360]. В [505) принципы работы метода усиления описаны с точки зрения специалиста по статистике. Теоретический анализ обучающих алгоритмов начался с работы Голда [569) по проблеме идентификации в пределе. Стимулом к развитию этого подхода отчасти явились модели научного открытия, разработанные в рамках философии науки [1229], но этот подход в основном применялся к задаче изучения грамматик на примерах предложений [1162]. 898 Часть УТ.
Обучение Подход, основанный на изучении "идентификации в пределе", в основном посвящен достигаемой в конечном итоге сходимости, а исследования Ж колмогоровской сложности, или алгоритмической сложности, проведенные независимо Соломоновым [1445] и Колмогоровым [828], представляют собой попытку дать формальное определение понятия простоты, используемого в принципе бритвы Оккама.
Чтобы исключить проблему, связанную с тем, что простота зависит от способа представления информации, было предложено измерять простоту как длину кратчайшей программы для универсальной машины Тьюринга, которая правильно воспроизводит наблюдаемые данные. Хотя существует много возможных универсальных машин Тьюринга и поэтому много возможных "кратчайших" программ, было обнаружено, что эти программы отличаются по длине не больше чем на некоторую константу, независимую от объема данных. Это — великолепное открытие, которое по сути показывает, что любое искажение в первоначальном представлении данных в конечном итоге должно быть преодолено с помощью самих же данных.
Его широкому применению препятствует лишь то, что задача вычисления длины кратчайшей программы является неразрешимой. Однако вместо точного значения длины могут применяться такие приближенные критерии, как Ъ. минимальная длина описания, или МОЕ (Мшппшп Резсг!рг!оп Ееп81]з) [1291], которые позволяют добиться на практике превосходных результатов. Наилучшим источником сведений по проблеме колмогоровской сложности является книга Ли и Витаньи [927]. Теория вычислительного обучения (т.е. теория РАС-обучения) была выдвинута Лесли Валиантом [1528]. В работе Валианта подчеркивается важность вычислительной и выборочной сложности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
