Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 264

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 264)

параметрическим обучением. Методы параметрического обучения часто бывают простыми и эффективными, но предположение о том, что в данных воплощено конкретное ограниченное семейство моделей, часто слишком упрощает то, что происходит в реальном мире, из которого поступают эти данные. Верно, что при наличии очень малого объема данных нельзя надеяться определить в процессе обучения параметры сложной и подробной модели, но представляется неразумным по-прежнему придерживаться гипотезы с той же фиксированной сложностью, даже после того, как доступный набор данных становится очень большим! В отличие от параметрического обучения, методы Ж непараметрического обучения позволяют увеличивать сложность гипотезы по мере роста объема данных.

Чем больше данных поступает в распоряжение исследователя, тем более развитой может становиться гипотеза. В данном разделе рассматриваются два очень простых семейства методов непараметрического 'еь обучения на основе экземпляра (или обучения иа основе 973 Глава 20. Статистические методы обучения содержимого памяти), получивших такое название потому, что они позволяют конст- руировать гипотезы непосредственно на основе самих обучающих экземпляров. Модели ближайшего соседа Ключевая идея моделей Ж ближайшего соседа состоит в том, что свойства любой конкретной входной точки х, по-видимому, должны быть подобными свойствам точек, соседних по отношению к х. Например, если требуется выполнить оценку плотности (т.е.

оценить значение неизвестной плотности вероятности в точке х), то можно просто измерить ту плотность, с какой расположены точки, рассеянные в окрестности и. Такая задача на первый взгляд может показаться очень простой, пока не станет очевидно, что нужно точно определить, что подразумевается под понятием "окрестность". Если окрестность слишком мала, то не будет содержать ни одной точки данных, а если слишком велика, то может включить все точки данных, в результате чего будет получена всюду одинаковая оценка плотности. Одно из возможных решений состоит в том, чтобы определить окрестность как достаточно большую для включения й точек, где и достаточно велико для обеспечения получения осмысленной оценки. При постоянном значении й размеры окрестности изменяются— если данные являются разреженными, то окрестность велика, а если данные расположены плотно, то окрестность мала. На рис.

20.!2, а показан пример данных, рассеянных в двух измерениях, а на рис. 20.13 приведены результаты оценки плотности по К ближайшим соседним точкам на основании этих данных при й=З, 10 и 40 соответственно. При я= 3 оценка плотности в любой точке основана только на 3 соседних точках и весьма изменчива. При )с=10 полученная оценка представляет собой хорошую реконструкцию истинной плотности, показанной на рис, 20.12, б. При )с=40 окрестность становится слишком большой и информация о структуре данных полностью теряется.

На практике хорошие результаты для большинства наборов данных с малым количеством размерностей можно получить с помощью значения )с, находящегося примерно между 5 и 10. Подходяшее значение для )г можно также выбрать с использованием перекрестной проверки. Для выявления соседних точек, ближайших к точке запроса, нужна метрика расстояний 17(х„х, ) . В двухмерном примере, приведенном на рис. 20.12, используется евклидово расстояние.

Но такая метрика становится неподходящей, если каждая размерность пространства измеряет что-то другое (например, рост и вес), поскольку изменение масштаба одной размерности приводит к изменению множества ближайших соседних точек. Одним из решений является стандартизация масштаба для каждой размерности.

Для этого измеряется среднеквадратичное отклонение каждой характеристики по всему набору данных и значения характеристик выражаются как кратные среднеквадратичного отклонения для этой характеристики (это — частный случай 'а. расстояния Махалаиобиса, в котором также учитывается ковариация характеристик). Наконец, для дискретных характеристик можно использовать 'в. расстояние Хеммиига, в котором п(м,, х,) определяется как количество характеристик, по которым отличаются точки х, и х,.

Оценки плотности, подобные приведенным на рис. 20.13, определяют совместные распределения по пространству входных данных. Но в отличие от байесовской сети, представление на основе экземпляра не может содержать скрытых перемен- Часть т(Е Обучение 974 ных, а зто означает, что может выполняться неконтролируемая кластеризация, как зто было в случае с моделью смешанного гауссова распределения.

Тем не менее оценка плотности все еще может использоваться для предсказания целевого значения у по входным значениям характеристики х путем вычисления вероятности Р)у)х) =Р)у, х) 1Р)х), при условии, что обучающие данные включают значения для соответствующей целевой характеристики. Плотность 18 16 14 12 10 8 6 4 2 0 о 0,6 0,4 ! 8 о,г о 0 0,2 0,4 0,6 0,8 1 а) б) Рис. 20. 12.

Пример применения оценки плотности с )с ближаишими соседними точками: частичная выборка динных, показанных ни рис. 20. В, а, состоящая из 12В точек, наряду с двумя точкими запроса и их окрестностями, которые включают 10 ближаиших соседних точек (а); трехмерныи график смешанного гауссова распределения, на основании которого бьии получены эти данные (б) Пл Пл Пл ,8 а) б) в) Рис. 20. 13. Результаты применения метода оценки плотности с использованиелт окрестностей, включающих )с ближайших соседних точек, к данным, приведенным на рис. 20. 12, а, при К =3, 2 0 и 4 0 соответственно Идею оценки характеристик с помощью ближайшей соседней точки можно также непосредственно использовать в контролируемом обучении.

Если имеется проверочный пример с входными данными х, то выходное значение у=)т )х) можно получить на основании значений удля )с ближайших соседних точек точки х. В дискретном случае единственное предсказание можно получить с помощью мажоритарного голосования, а в непрерывном случае — предусмотреть усреднение по )с значениям 975 Глава 20. Статистические методы обучения или применить локальную линейную регрессию, подгоняя гиперплоскость к )е точкам и предсказывая значение в точке х с помощью этой гиперплоскости.

Алгоритм обучения с помогдью )г ближайших соседних точек является очень простым для реализации, требует весьма небольшой настройки и часто показывает достаточно приемлемую производительность. Вполне целесообразно, столкнувшись с новой задачей обучения, вначале попытаться воспользоваться этим алгоритмом. Но при наличии больших наборов данных требуется эффективный механизм поиска соседних точек, ближайших к точке запроса х, поскольку выполнение метода, в котором просто вычисляется расстояние до каждой точки, занимает слишком много времени. Было предложено много остроумных методов, позволяющих повысить эффективность этого этапа, которые основаны на предварительной обработке обучающих данных. Но, к сожалению, большинство из этих методов не достаточно хорошо масштабируются с увеличением количества размерностей пространства (т.е.

количества характеристик). При использовании многомерных пространств возникает егде одна проблема, связанная с тем, что ближайшие соседние точки в таких пространствах в действительности часто находятся очень далеко! Рассмотрим набор данных с размером вг в д-мерном единичном гиперкубе и предположим, что нужно найти гиперкубическую окрестность с размером .Ь и объемом )за (те же рассуждения относятся к гиперсферам, но формула объема гиперсферы является более сложной). Чтобы в нее вошло )еточек, средняя окрестность должна занимать долю Ю)ч всего объема гиперкуба, который равен 1. поэтому ьа=)еу)ч, или ь= ()гул)) "~.

до сих пор все шло хорошо. А теперь допустим, что количество характеристик с) равно 100, и предположим, что )с равно 1О, а л) равно 1 000 000. В таком случае получаем, что 2~0. 89, те. что окрестность должна охватывать почти все пространство входных данных! Эти расчеты говорят о том, что методам с ближайшими соседними точками нельзя доверять, когда дело касается многомерных данных, а в случае малого количества размерностей не возникает никаких проблем; при с)=2 получаем В= О . О О 3.

Ядерные модели В еь ядерной модели каждый обучающий экземпляр рассматривается как самостоятельно вырабатывающий небольшую функцию плотности (Ъ.ядерную функцию). Оценка всей плотности в целом представляет собой нормализованную сумму всех небольших ядерных функций. Обучающий экземпляр в точке х„вырабатывает ядерную функцию К(х, х,), которая присваивает определенную вероятность каждой точке х в пространстве. Поэтому оценка плотности принимает такой вид: 1 Р(х) = 7 К(х,х,) с=1 Ядерная функция обычно зависит только от расстояния )з(х, х,) между точкой х и экземпляром х,. Наиболее широко применяемой ядерной функцией (безусловно) является гауссово распределение.

Для упрощения предполагается использование сферического гауссова распределения со среднеквадратичным отклонением ы вдоль каждой оси, т.е. следующего распределения: 976 Часть Ч1. Обучение Р(х,х-) ' 2 нс к(х,х,) е ( нгт)2х) л гле с) — количество размерностей в точке х.

Характеристики

Список файлов книги