Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по системам закономерностей

Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по системам закономерностей (2014 Лекции (Сенько))

PDF-файл Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по системам закономерностей (2014 Лекции (Сенько)) (ММО) Методы машинного обучения (63132): Лекции - 10 семестр (2 семестр магистратуры)Лекция 10. Коллективные методы_ бэггинг_ бустинг_ голосование по системам закономерностей (2014 Лекции (Сенько)) - PDF (63132) - СтудИзба2020-08-25СтудИзба

Описание файла

Файл "Лекция 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Статистически взвешенные синдромыПри этом поиск производится внутри нескольких семейств разбиений,имеющих различный уровень сложности.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее