Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по сист. закономерностей (2015 Лекции (Сенько))
Описание файла
Файл "Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по сист. закономерностей" внутри архива находится в папке "2015 Лекции (Сенько)". PDF-файл из архива "2015 Лекции (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 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), . . .