Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по системам закономерностей (2014 Лекции (Сенько))
Описание файла
Файл "Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по системам закономерностей" внутри архива находится в папке "2014 Лекции (Сенько)". PDF-файл из архива "2014 Лекции (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Лекция 10Коллективные метод,бэггинг, бустинг, голосование по системам закономерностейЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 101 / 22Содержание лекции1Коллектиные методы2бэггинг2бустинг3логические закономерности4Статистически взвешенные синдромы5метод комитетовСенько Олег Валентинович ()МОТП, лекция 102 / 22Коллективные методы ("бэггинг")Одним из способов получения ансамбля является использованиеалгоритмов, обученных по разным обучающим выборкам, которыевозникают в результате случайного процесса, лежащего в основеисследуемой задачи.
Обычно при решении прикладной задачи враспоряжении исследователя имеется обучающая выборкаSet = {s1 , . . . , sm } ограниченного объёма. Однако процесс генерациисемейства выборок из генеральной совокупности может бытьимитирован с помощью процедуры бутстрэп (bootstrap), котораяоснована на выборках с возвращениями из Set . В результатеполучаются выборки Se∗bg , включающие объекты из обучающейвыборки Set . Однако некоторые объекты Set могут встречаться в Se∗bgболее одного раза, а другие объекты отсутствовать.
Предположим, чтос помощью процедуры бутстрэп получено T выборок. C помощьюзаранее выбранного метода, используемого для обучения отдельныхалгоритмов распознавания, получим множество, включающее Tebg = {Abg , . . . , Abg }.распознающих алгоритмов A1TСенько Олег Валентинович ()МОТП, лекция 103 / 22Коллективные методы "бэггинг"Для получения коллективного решения может быть использованпростейший комитетный метод, относящий объект в тот класс, кудаего отнесло большинство алгоритмов . Данная процедура носитназвание бэггинг (bagging), что является сокращением названияBootstrap Aggregating. Процедура бэггинг показывает высокий приростобобщающей способности по сравнению с алгоритмом, обученным спомощью базового метода по исходной обучающей выборке Set , в техслучаях, когда вариационная составляющая ошибки базового методавысока.
К таким моделям относятся в частности решающие деревья инейросетевые методы. При использовании в качестве базового методарешающих деревьев процедура бэггинг приводит к построениюансамблей решающих деревьев (решающих лесов).Основной идеей алгоритма бустинг является пошаговое наращиваниеансамбля алгоритмов. Алгоритм, который присоединяется к ансамблюна шаге k обучается по выборке, которая формируется из объектовисходной обучающей выборки Set .Сенько Олег Валентинович ()МОТП, лекция 104 / 22Коллективные методы "бустинг"В отличие от метода бэггинг объекты выбираются не равноправно, аисходя из некоторого вероятностного распределения, заданного навыборке Set . Данное распределение вычисляется по результатамклассификации с помощью ансамбля, полученного на предыдущемшаге.
Приведём схему одного из наиболее популярных вариантовметода бустинг AdaBoost (Adaptive boosting) более подробно. На1 )первом шаге присваиваем начальные значения весов (w11 , . . . , wmобъектам обучающей выборки. Поскольку веса имеютPвероятностную1интерпретаци, то для них соблюдаются ограничения mj=1 wj = 1,wj1 ∈ [0, 1].
Обычно начальное распределение выбирается1, j = 1, . . . , m. Выбираем число итераций T . Наравномерным wj1 = mитерации k генерируем выборку Sekbs из исходной выборки Set согласноk ). Обучаемраспределению задаваемому весами (w1k , . . . , wmebsраспознающий алгоритм Absk по выборке Sk .Сенько Олег Валентинович ()МОТП, лекция 105 / 22Коллективные методы, "бустинг".Pk kВычисляем взвешенную ошибку по формуле εk = mj=1 wj ej , гдеbskej = 1, если алгоритм Ak неправильно классифицировал объект sj иekj = 0 в противном случае.
В том случае, если εk ≥ 0.5 или εk = 0игнорируем шаг и заново генерируем выборку Sekbs исходя из весовых1коэффициентов wj1 = m, j = 1, . . . , m. В случае если εk ∈ (0, 0.5)εkвычисляем коэффициенты τk = 1−εkи пересчитываем веса объектов по формулеkwjk+1wjk (τk )1−ej=Pmk1−ejkj=1 wj (τk )(1)при j = 1, . . . , m.Процесс, задаваемый формулой (1), продолжается до тех пор, пока невыполнено T итераций . В результате мы получаем совокупность из Tbsраспознающих алгоритмов Abs1 , . . . , AT .Сенько Олег Валентинович ()МОТП, лекция 106 / 22Коллективные методы, "бустинг".Предположим, что нам требуется распознать объект s∗ . Пустьk ∗βlk (s∗ ) = 1, если s∗ отнесён алгоритмом Absk в класс Kl , и βl (s ) = 0 в∗противном случае. Оценка объекта s за класс Kl вычисляется поформулеTX1∗Γl (s ) =ln βlk (s∗ ).τkk=1s∗Объектбудет отнесён к классу, оценка за которой максимальна.Описанный вариант метода носит название AdaBoost.
M1.Эффективность процедур бустинга подтверждается многочисленнымиэкспериментами на реальных данных. В настоящее время существуетбольшое количество вариантов метода, имеющих разное обоснование.Сенько Олег Валентинович ()МОТП, лекция 107 / 22Коллективные методы, основанные на голосовании по системамзакономерностейОдним из эффективных подходов к решению задач прогнозирования ираспознавания является использование коллективных решений посистемам закономерностей.
Под закономерностью понимаетсяраспознающий или прогностический алгоритм, определённый нанекоторой подобласти признакового пространства или связанный снекоторым подмножеством признаков. В качестве примеразакономерностей могут быть приведены представительные наборы,являющиеся по сути подмножествами признаковых описаний,характерных для одного из распознаваемых классов. Аналогомпредставительный наборов в задач с вещественнозначнойинформацией являются логические закономерности классов. Подлогической закономерностью класса Kl понимается областьпризнакового пространства, имеющая форму гиперпараллелепипеда исодержащая только объекты из Kl .Сенько Олег Валентинович ()МОТП, лекция 108 / 22Логическая закономерностьРис 1.
Пример логической закономерности.Сенько Олег Валентинович ()МОТП, лекция 109 / 22Логическая закономерностьЛогическая закономерность класса Kj , которую обозначим r(j),описывается с помощью предикатов видаr(j)P tir(j)= ”air(j)≤ Xi ≤ bi(2)где i = 1, . . . , n. Отметим, что для несущественных дляr(j) r(j)закономерности r(j) признаков отрезок [ai , bi ] соответствуетобласти допустимых значений Xi . Для существенных признаковr(j) r(j)отрезок [ai , bi ] является некоторым подмножеством областидопустимых значений Xi . Полностью r(j) задаётся конъюнкциейпредикатов (2):r(j)Ptr(j) = P tiСенько Олег Валентинович ()& .
. . &P tr(j).nМОТП, лекция 1010 / 22Логическая закономерностьДля конъюнкции Ptr(j) должны выполняться следующие условия:в обучающей выборке Set должен существовать объект s∗ изкласса Kj , для которого Ptr(j) = 1;в обучающей выборке Set не должно содержаться объектов, непринадлежащих класса Kj , для которых Ptr(j) = 1;Ptr(j) доставляет экстремум некоторому функционалу качестваΦ(Pt) , заданному на множестве всевозможных предикатов,удовлетворяющих условиям 1), 2)На практике используются следующие функционалы качества:число объектов из класса Kj в обучающей выборке, для которыхPtr(j) = 1;доля объектов из класса Kj в обучающей выборке, для которыхPtr(j) = 1;Сенько Олег Валентинович ()МОТП, лекция 1011 / 22Логическая закономерностьНаряду с полными логическими закономерностями, для которыхвыполняются все условия 1) – 3), используются также частичныелогические закономерности, для которых допускаются некоторыенарушения условия 2).
То есть допускается существование небольшойдоли нарушений условия 2) для тех объектов, для которыхвыполняется условие Ptr(j) = 1. На этапе обучения для каждого изej .классов Kj ищется множество логических закономерностей RПредположим, что нам требуется распознать новый объект s∗ . Дляej длякаждого из классов Kj ищется число закономерностей из Rr(j) ∗которых Pt (s ) = 1 . При этом доля таких закономерностейсчитается оценкой за класс Kj . Для классификации используетсястандартное решающее правило, т.е. объект относится в класс, оценказа который максимальна. Поиск оптимальной системы логическихзакономерностей производится по набору See случайно выбранных изобучающей выборки Set эталонных объектов (опорных эталонов).Сенько Олег Валентинович ()МОТП, лекция 1012 / 22Логическая закономерностьЗакономерности для класса Kj строится по каждому из опорныхэталонов si ∈ See .
При этом поиск оптимальных границr(j)[a1r(j), b1r(j), . . . , ar(j)n , bn ]для закономерности r(j) осуществляется сначала на некоторойнеравномерной сетке пространства, которая задается с помощьюразбиения интервала значений каждого из признаков. Посленахождения оптимальных границ на заданной сетке, поискпродолжается на заданной в окрестности этого оптимального решения,но уже на более мелкой сетке.
Процесс заканчивается, если припереходе к более мелкой сетке не удается найти логическуюзакономерность с более высоким критерия качества Φ. . Задача поискаоптимальной логической закономерности на каждой сетке сводится кпоиску максимальной совместной подсистемы некоторой системынеравенств. Логические закономерности, построенные для случайновыбранных «опорных» эталонов класса Kj объединяются в одноej .множество RСенько Олег Валентинович ()МОТП, лекция 1013 / 22Статистически взвешенные синдромыКоллективные решения в методе СВС принимается по информации опринадлежности векторного описания распознаваемого объекта такe Подназываемым “синдромам” из некоторого множества Q."синдромом"понимается такая область признакового пространства, вкоторой содержание объектов одного из классов, отличается отсодержания объектов этого класса в обучающей выборке или покрайней мере в одной из соседних областях.
Пример синдромов,характеризующих разделение объектов из классов K1 ( ) и K2 ( )приведён на рисунке 2. Синдромы ищутся для каждого израспознаваемых классов с помощью построения оптимальныхразбиений интервалов допустимых значений единичных признаков илисовместных двумерных областей допустимых значений пар признаков.Сенько Олег Валентинович ()МОТП, лекция 1014 / 22Статистически взвешенные синдромыРис 2. Видно, описания объектов из сосредоточены главным образомв нижнем левом квадранте «синдроме».Сенько Олег Валентинович ()МОТП, лекция 1015 / 22Статистически взвешенные синдромыПри этом поиск производится внутри нескольких семейств разбиений,имеющих различный уровень сложности.