_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007).pdf), страница 10

Разумеется, если несломается система калибровки, не сгорит хотя бы один из трех процессоров, и за станок не сядеткакой-нибудь «естествоиспытатель»...5.2.2Примеры задач выбора моделиЗадача классификации методом опорных векторов• Решающее правило имеет видy(x) = signà nX!wi K(x, xi ) + bi=1• Оптимизационная задача для поиска весовnXi=1nXnwi −n1 XXti tj wi wj K(xi , xj ) → max2 i=1 j=1ti wi = 00 ≤ wi ≤ Ci=1• Коэффициент регуляризации C и ядровая функция K(x0 , x00 ) определяют модель метода опорныхвекторов (см. рис.

5.1, 4.10, 4.11)Глава 5. Задачи выбора модели60Рис. 5.1. Результаты классификации SVM с различными структурными параметрамиЗадача регрессии• Обобщенная линейная регрессияy(x) =mXwj φj (x)j=1• Веса регрессии вычисляются по следующей формуле¡¢−1 Tw = ΦT Φ + λIΦ t• Параметр регуляризации λ ≥ 0, система базисных функций {φj (x)}mj=1 и их количество m определяют модель(a)(b)(c)Рис. 5.2. Результаты восстановления регрессии с различным числом базисных функцийЗадача кластеризации• Большинство методов кластеризации предполагают задание пользователем количества кластеров,на которые будут разбиваться входные данные (см.

рис. 5.3)Глава 5. Задачи выбора модели61(a)(b)Рис. 5.3. Решение задачи кластеризации с помощью метода K средних с двумя кластерами (a) и с шестью кластерами (b)Нейронные сети• Выбор архитектуры нейронной сети (количество нейронов на каждом уровне) и функции активацииопределяют модель нейронной сетиxDскрытые нейроныzM(1)wMD(2)wKMyKвходывыходыy1x1(2)x0z1w10z0Рис. 5.4. Архитектура нейронной сети. Качества классификации нейронной сети существенно зависит от выбора ее структуры5.35.3.1Общие методы выбора моделиКросс-валидацияЧто такое общие методы выбора модели?• Под общими методами выбора модели будем понимать алгоритмы, позволяющие проводить автоматическую настройку любых структурных параметров для широкого множества задач машинногообучения (например, для всех задач классификации)Глава 5.

Задачи выбора модели62• На практике такой метод может использоваться для настройки лишь некоторых структурных параметров, но гипотетически он должен позволять определять любые характеристики наилучшеймоделиСкользящий контроль• Процедура скользящего контроля (кросс-валидации) заключается в последовательном исключениичасти объектов из обучающей выборки, обучении на оставшихся объектах и распознавании исключенных объектов• Тем самым эмулируется наличие тестовой выборки, которая не участвует в обучении, но для которойизвестны правильные ответы• Структурные параметры настраиваются путем минимизации ошибки на скользящем контроле• Процедура скользящего контроля является на сегодняшний день самым лучшим средством настройки структурных параметровСхема k-fold cross validation• Выборка разбивается на k непересекающихся (одинаковых по объему) частей. На каждой итерацииобучение проводится по k − 1 части, а тестирование на исключенных объектахРис.

5.5. Процедура 4-fold cross validation. Каждый раз из выборки исключается четверть объектов, на остальной частипроводится обучение, а затем исключенные объекты распознаются• На рисунке 5.5 приведена процедура 4-fold cross validation• При k = n процедура называется leave-one-out• Наилучшим режимом скользящего контроля считается 5 × 2-fold cross validation.Особенности скользящего контроля• Ошибка на скользящем контроле является довольно точной оценкой ошибки на генеральной совокупности (обобщающей способности)• Проведение скользящего контроля требует значительного времени на многократное повторное обучение алгоритмов и применимо лишь для «быстрых» методов машинного обучения• С помощью скользящего контроля можно настраивать не более двух-трех структурных параметров,т.к.

настройка производится путем полного перебора всевозможных сочетаний параметров• При его использовании для выбора модели ошибку на скользящем контроле нельзя рассматриватькак оценку ошибки на генеральной совокупности, т.к. она получается заниженной• Скользящий контроль неприменим в задачах кластерного анализа и прогнозирования временныхрядовГлава 5. Задачи выбора модели5.3.263Теория Вапника-ЧервоненкисаИдея теории структурной минимизации риска• Теория Вапника-Червоненкиса использует косвенные характеристики для оценки обобщающей способности (среднего риска)• Ключевым понятием является т.н. емкость (размерность Вапника-Червоненкиса, VC-dimension) модели• Идея данного подхода к выбору модели (структурной минимизации риска) заключается в следующем: Чем более «гибкой» является модель, тем хуже ее обобщающая способность• В самом деле, «гибкое» решающее правило способно настроиться на малейшие шумы, содержащиесяв обучающей выборкеПонятие емкости• Рассмотрим задачу классификации на два класса• (Несколько упрощая,) емкостью данной модели будем называть максимальное число объектов обучающей выборки, для которых при любой их разметке на классы найдется хотя бы один алгоритмиз модели, безошибочно их классифицирующий• По аналогии вводятся определения емкости для других задач машинного обучения• Важный пример модели, для которой известна емкость — классификатор, строящий линейную гиперплоскость.

Емкость линейного классификатора равна h = d+1, где d — размерность пространствапризнаков• Следствие: n ≤ d + 1 объектов всегда можно безошибочно разделить гиперплоскостьюФормула Вапника• Очевидно, что чем больше емкость, тем хуже. Значит нужно добиваться минимально возможногоколичества ошибок на обучении при минимальной возможной емкости• Ошибку на обучении (эмпирический риск) Ptrain (w), емкость h(Ω) и ошибку на генеральной совокупности (средний риск) Ptest (w) связывает известная формула Вапникаrh(Ω)(log(2n/h(Ω)) + 1) − log(η/4)Ptest (w) ≤ Ptrain (w) +nНеравенство верно с вероятностью 1 − η для ∀w ∈ Ω• Последовательно анализируя модели с увеличивающейся емкостью, согласно теории ВЧ, необходимовыбирать модель с наименьшей верхней оценкой тестовой ошибкиДостоинства и недостатки теории ВЧ• Достоинства– Серьезное теоретическое обоснование, связь с ошибкой на генеральной совокупности– Теория продолжает развиваться и в наши дни (эффективная емкость, локальная емкость, комбинаторный подход и т.д.)• Недостатки– Оценки сильно завышены– Для большинства моделей емкость не поддается оценке– Многие модели с бесконечной емкостью показывают хорошие результаты на практикеГлава 5.

Задачи выбора модели64Пути развития теории ВЧ (и не только ее)• Емкость вводится для всевозможных положений объектов выборки, в то время как реально приходится иметь дело с одной конкретной выборкой и опять-таки имеет смысл рассматривать степеньадаптируемости модели под эту конкретную выборку, а не под абстрактно возможную• В процессе обучения поиск алгоритма в модели ведется не по всем ее представителям, а лишь поконечному числу, которое и имеет смысл рассматривать при интерпретации емкости, как степениадаптируемости модели под данные• Искомая закономерность может обладать рядом дополнительных свойств, которые сокращают объемдопустимых алгоритмов модели5.3.3Принцип минимальной длины описанияПредпосылка метода• Из пункта А в пункт В передается закодированное сообщение о классификации обучающей выборки.Нужно добиться минимально возможного размера сообщения• Стратегия 1: передаем каждый объект и его метку класса {(xi , ti )}ni=1• Стратегия 2: передаем длинное описание сложного алгоритма, который можно использовать дляправильной классификации всей обучающей выборки Descr(A)• Стратегия 3: передаем короткое описание простого алгоритма Descr(A0 ) , который правильно классифицирует большинство объектов обучающей выборки, а классификацию неправильно распознанных объектов передаем отдельным списком{xik , tik }pk=1 , p < nСмысл метода• Чем точнее на обучающей выборке алгоритм, тем он сложнее, а значит тем длиннее будет его описание...• ...

но тем меньше будет список неправильно распознанных объектов (см. рис. 5.6)• Принцип минимальной длины описания (minimum decription length MDL, Rissanen, 1978) штрафуетизлишнюю алгоритмическую сложность решающего правилаОписаниеалгоритмаОписаниенеправильно распознанных объектовПростой алгоритмОптимальный алгоритмСложный алгоритмРис. 5.6. Иллюстрация метода минимальной длины описанияГлава 5.

Задачи выбора модели65Особенности подсчета длины описания• Существует множество подходов к оценке длины описания алгоритма вплоть до длины кода реализующей его программы• Необходимо отметить, что кодирование должно быть эффективным, т.к. даже самый простой алгоритм можно закодировать в очень длинное сообщение• Согласно теореме Шеннона, при оптимальном кодировании длина описания структуры пропорциональна логарифму ее вероятности, взятому с противоположным знакомЭквивалентность MDL и максимизации апостериорной вероятности• Пусть на множестве алгоритмов задано априорное распределение p(w)l(w) = − log p(w)• Длина описания данных тем меньше, чем выше вероятность данной классификации при использовании данного алгоритма, т.е.

чем выше правдоподобие p(t|X, w)l(t|w) = − log p(t|X, w)• Отсюда получаем выражение, объединяющее точность на обучении и сложность алгоритма в единое выражениеl(t, w) = − log p(t|X, w) − log p(w)arg min l(t, w) = arg max p(t|X, w)p(w)ww• Таким образом, MDL обосновывает идею максимизации регуляризованного правдоподобияОтличительные особенности MDL• MDL позволяет обосновать корректность регуляризации правдоподобия• Область применения MDL шире, чем у статистических методов обучения, т.е.

MDL можно применятьи там, где вводить вероятности некорректно или бессмысленно• При использовании MDL предполагается, что чем сложнее алгоритм, тем хуже его обобщающая способность. Современные исследования (в частности, boosting) показывают, что это далеконе всегда так5.3.4Информационные критерииИнформационный критерий Акаике• В 1973г. Акаике установил связь между правдоподобием (ключевое понятие статистики) и дивергенцией Кульбака-Лейблера (ключевое понятие в теории информации)• Ему удалось получить приблизительное соотношение между правдоподобием генеральной совокупности и правдоподобием обучающей выборки (т.е.

данных, по которым c помощью ММП производится настройка параметров решающего правила)AIC = log p(t|X, wM L ) − M,где M — число настраиваемых параметров• Пример использования: задача восстановления регрессии с известным гауссовским шумом в одномерном пространстве при помощи полинома степени k¶µ Pn2i=1 (ti − yk (xi ))+k+1k = arg min2σ 2Глава 5. Задачи выбора модели66Информационный критерий Шварца• Критерий Шварца (часто именуемый Байесовским информационным критерием) представляет собой простейшее приближение обоснованности, широко использующейся в байесовском обученииZBIC ≈ p(t|X, w)p(w)dw• Используя приближение интеграла гауссианой и сильно огрубляя, получаем1BIC = log p(t|X, wM P ) − M log n2• Пример использования: Задача восстановления регрессии с известным гауссовским шумом в одномерном пространстве при помощи полинома степени kµ Pn¶2√i=1 (ti − yk (xi ))k = arg min+ (k + 1) log n2σ 2Особенности информационных критериев• Оба критерия являются (весьма грубыми) приближениями более сложных выражений, часто не поддающихся аналитическому вычислению.