Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 242
Текст из файла (страница 242)
А после применения метода усиления (при м=5) пронзволительность становится выше и достигает 93% после обработки 100 примеров. 0,6 0 20 40 60 80 Объем обучающего множества а) 50 )00 )50 200 Количество гипотезМ б) )00 Рис. !8.8. Анализ производительности алгоритмов: график, показывающий, как изменяется щюизводительность усиленных одноузловых деревьев решений при н«б по сривнению с неусиленными одноузловыми деревьями решений на примере данных о ресторане (а); доля правильных ответов, полученных на обучающем множестве и проверочном множестве, как функция от н (от количества гипотез в ансамбле) (б).
Обратите вншиание на то, что точность распознавания примеров из проверочного множества немного повышается даже после того, как точность распознавания примеров из обучающего множестви достигаегп 7, т.е. после того, как ансамбль гипотез полностью согласуется с данными По мере увеличения размера ансамбля )ч обнаруживается интересное явление.
На рис. 18.8, б показана производительность обучающего множества (на 100 примерах) как функция от м. Обратите внимание на то, что ошибка достигает нуля (как и следует из определения метода усиления), когда р) становится равным 20; это означает, что взвешенная мажоритарная комбинация из 20 одноузловых деревьев решений вполне позволяет определить точное соответствие для !00 примеров. По мере введения в ансамбль дополнительных одноузловых деревьев решений ошибка остается равной нулю. Этот график также показывает, что св производительность обработки проверочного множества продолжает возрастать в течение долгого времени после того, как ошибка на обучающем множестве достигает нуля. При О)«2 0 производи- ) д 0,95 оо 085 в 0,75 оп ай 0,65 о(Я О 55 0,5 0 1 ж 0,95 й " 0,9 «ф 085 Яо ОЯ Ео 075 б$ 07 от.
шо 0,65 889 Глава 18. Обучение на основе наблюдений тельность на проверочном множестве равна 0,95 (что соответствует 0,05 ошибки) и после чего увеличивается до 0,98 при таком большом значении, как эг=137, прежде чем постепенно уменьшиться до 0,95. Эта особенность, которая неизменно проявляется в самых разных наборах данных и пространствах гипотез, после ее обнаружения впервые показалась исследователям весьма неожиданной. Согласно принципу бритвы Оккама, не следует создавать гипотезы, более сложные, чем необходимо, а этот график говорит нам о том, что по мере усложнения гипотезы-ансамбля предсказания улучшаются! Для объяснения этого феномена было предложено несколько трактовок. Один из подходов к анализу такого явления состоит в том, что в процессе усиления аппроксимируется байесовское обучение (см, главу 20), притом что можно доказать, что байесовский алгоритм является оптимальным обучающим алгоритмом, а аппроксимация улучшается по мере введения дополнительных гипотез.
Еше одно возможное объяснение состоит в том, что введение дополнительных гипотез позволяет добиться того, что ансамбль проводит все более определенное различие между положительными и отрицательными примерами, а это свойство способствует лучшей классификации новых примеров. 18.5. ПРИНЦИПЫ ФУНКЦИОНИРОВАНИЯ АЛГОРИТМОВ ОБУЧЕНИЯ: ТЕОРИЯ ВЪ|ЧИСЛИТЕЛЪНОГО ОБУЧЕНИЯ Один из важных вопросов, поставленных в разделе 18.2, на который не был получен ответ, состоял в следуюшем: как можно убедиться в том, что в результате применения разработанного кем-то обучающего алгоритма была создана теория, позволяюшая правильно предсказывать будущее? Формально этот вопрос можно переформулировать следующим образом: как определить, насколько гипотеза ?з близка к целевой функции б, если неизвестно, каковой является сама функция б! Подобные вопросы были предметом размышлений ученых в течение нескольких столетий. До тех пор, пока на них не будут получены ответы, машинное обучение в лучшем случае может рассматриваться лишь как научная область, причины успешных достижений которой остаются необъяснимыми.
Подход, принятый в данном разделе, основан на 'ах теории вычислительного обучения — научной области, которая находится на стыке искусственного интеллекта, статистики и теоретических компьютерных наук. Принцип, лежащий в ее основе, состоит в следующем: 3 любая гипотеза, которая содержит серьезные ошибки, почти наверняка будет "открыта" с большои вероятностью после обработки небольшого количества примеров, поскольку она дает неправильные предсказания. Поэтому любая гипотеза, согласованная с достаточно большим множеством обучающих примеров, с меньшей вероятностью будет содержать серьезные ошибки; это означает, что она обязательно будет гк приблизительно правильной с определенной вероятностью. Любой обучаюший алгоритм, вырабатывающий гипотезы, которые с определенной вероятностью являются приблизительно правильными (РгоЬаЫу Арргохппаге!у Соггесг — РАС), называется алгоритмом 'а.
РАС-обучения. При анализе приведенных выше доводов необходимо учитывать некоторые нюансы. Основной вопрос состоит в том, какова связь между обучающими и проверочными примерами; в конечном итоге желательно, чтобы гипотеза была приблизительно правильной 890 Часть Ъ"). Обучение применительно к проверочному множеству, а не только к обучающему множеству. Основное предположение состоит в том, что и обучаю)цее, и проверочное множества примеров извлекаются случайно и независимо друг от друга из одной и той же популяции примеров с одним и тем же распределением вероятностей.
Это предположение называется предположением о 'ъ. стационарности. Если не принято предположение о стационар- ности, то теория вычислительного обучения не позволяет формулировать вообще какие- либо утверждения о будущем, поскольку не определена необходимая связь между будущим и прошлым. Предположение о стационарности равносильно тому предположению, что процесс, в котором осуществляется отбор примеров, не подвержен неблагоприятному влиянию. Очевидно, что если обучающее множество состоит только из надуманных примеров (например, фотографий двухголовых собак), то обучающий алгоритм не сможет сделать ничего иного, кроме как предложить безуспешные обобщения, касающиеся того, как распознавать обычных собак.
Оценка количества необходимых примеров Для того чтобы перевести эти предположения на практическую почву, необходимо ввести некоторые описанные ниже обозначения. ° Обозначим символом х множество всех возможных примеров. ° Обозначим символом )) распределение, из которого извлекаются примеры. ° Обозначим символом н множество возможных гипотез. ° Обозначим символом ))) количество примеров в обучающем множестве. Первоначально будем предполагать, что истинная функция Г является элементом множества н. Теперь можно определить Ж ошибку гипотезы Л применительно к истинной функции Г, если дано распределение вероятностей Р по примерам, описывающее вероятность того, что гипотеза Л отлична от функции Е на некотором примере: еггог(Ы = Р(Л)х)иг)х) )х извлечен из )З) Это — такое же количество, которое измерялось экспериментально с помощью кривых обучения, описанных выше в данной главе.
Гипотеза Л называется приблизительно правильной, если еггог ( Л) <е, где а — небольшая константа. Примем к действию план решения этой проблемы, который состоит в том, чтобы доказать, что после просмотра л) примеров все совместимые гипотезы с высокой вероятностью станут приблизительно правильными.
Приблизительно правильная гипотеза может рассматриваться как "близкая" к истинной функции в пространстве гипотез: она находится внутри так называемого 'ск е-шара, который окружает истинную функцию Г. На рис. ! 8.9 показано множество всех гипотез н, которое подразделяется на е-шар, окружающий функцию г, и все остальные гипотезы, принадлежащие к множеству, которое мы будем называть ггь.а Вероятность того, что гипотеза Лье н„„содержащая "серьезную ошибку", будет согласована с первыми д) примерами, можно вычислить следующим образом. Известно, что ег гог ( Л„) >а. В таком случае вероятность того, что эта гипотеза согласуется с заданным примером, равна по меньшей мере 1-е.
Граничное значение этой вероятности для д) примеров равно: Р)дн согласует с а) примерами) < )а-е) Глава 18. Обучение на основе наблюдений 891 н 1згс. 18.9. Схематическое изображение пространства гипотез, на котором показан с-шар, окружающий ис- тинную функцию й Вероятность того, что множество н„о содержит по меньшей мере одну совместимую гипотезу, ограничивается суммой отдельных вероятностей: Р(нми содержит совместимую гипотезу) < )нъ о((1-е) < (н((1-с)" где учитывался тот факт, что ~ и„о ~ < ! н (. Желательно уменьшить вероятность этого события так, чтобы она не превышала некоторого небольшого числа 6: (Н( (1-е) < 6 С учетом того, что 1-е<е ', такой цели можно добиться, предоставив алгоритму возможность обработать следующее количество примеров: )о > -(1п — т 1п)и() 1 1 Е (1а.1) Таким образом, если обучающий алгоритм возвратит гипотезу, совместимую с этим или большим количеством примеров, то с вероятностью, по меньшей мере равной 1-6, он будет иметь, самое большее, ошибку е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
