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

Лекция 9. Структура ошибки выпуклых комбинаций_ комитетные методы_ логическая коррекция (2014 Лекции (Сенько))

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

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

Файл "Лекция 9. Структура ошибки выпуклых комбинаций_ комитетные методы_ логическая коррекция" внутри архива находится в папке "2014 Лекции (Сенько)". PDF-файл из архива "2014 Лекции (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст из PDF

Лекция 9Структура ошибки выпуклых комбинаций,комитетные методы, логическая коррекцияЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 91 / 24Содержание лекции1Впуклые комбинации алгоритмов2Комитетные методы3Наивный байесовский корректор4Логическая коррекция5Алгебраическая коррекцияСенько Олег Валентинович ()МОТП, лекция 92 / 24Ансамбли алгоритмовИспользование различных методов прогнозирования (распознавания),а также различных обучающих выборок или подмножеств признаковпозволяет получить набор прогнозирующих (распознающих)алгоритмов: A1 , .

. . , Ar Можно попытаться увеличить обобщающуюспособность за счёт выбора алгоритма с минимальной оценкойошибки прогнозирования. Однако нередко более эффективнойпроцедурой является вычисление прогноза с использованием всехалгоритмов из A1 , . . . , Ar . Использование коллектива (ансамбля)алгоритмов, которые строятся с помощью различных методовпозволяет использовать при прогнозировании различные принципыэкстраполяции, лежащих в основе этих методов. Статистическоеобоснование использованию ансамбля алгоритмов даёт анализ ошибкивыпуклой комбинации прогнозов, вычисляемых членами ансамбля.Предположим, что алгоритмы ансамбля A1 , . . .

, Ar вычисляютпрогноз переменной Y .Сенько Олег Валентинович ()МОТП, лекция 93 / 24Выпуклые комбинацииПусть fi - прогноз, вычисляемый алгоритмом Ai . Тогда∆i = EΩ (Y − fi )2вляется математическим ожиданием квадрата ошибки прогнозированидля Ai , . Введём обозначение ρi0 i00 для математического ожиданияквадрата отклонения друг от друга прогнозов, вычисляемыхалгоритмами Ai0 и Ai00 . То естьρi0 i00 = EΩ (fi0 − fi00 )2 .PПусть c1 , . .

. , cr -положительные коэффициенты такие, что ri=1 ci = 1Обозначим через fˆ выпуклую комбинацию прогнозов, вычисляемыхалгоритмами ансамбля A1 , . . . , Ar . То естьfˆ =rXci fi .i=1Сенько Олег Валентинович ()МОТП, лекция 94 / 24Для ошибки выпуклой комбинации справедливо выражениеˆ = EΩ (Y − fˆ)2 =∆rXci ∆i −i=1rr1XXci0 ci00 ρi0 i002 0 00(1)i =1 i =1Принимая во внимание, что все квадратичные отклонения ρi0 i00 всегданеотрицательны, а коэффициенты c1 , .

. . , cr положительны получаемнеравенствоrXˆ∆≤ci ∆i .i=1Иными словами математическое ожидание квадрата ошибки выпуклойкомбинации всегда не превышает аналогичную выпуклую комбинациюматематических ожиданий квадратов ошибок отдельных алгоритмовансамбля.Сенько Олег Валентинович ()МОТП, лекция 95 / 24Рассмотрим, случай, когда все алгоритмы участвуют в построенииколлективного решения равноправно. В этом случае ci = 1r ,i = 1, .

. . , r. Выпуклая комбинация становится просто среднимзначениемr1 Xfˆ =fi .mi=1Математическое ожидание квадрата ошибки усреднённого поансамблю прогноза вычисляется по формулеrrrX1 1 XXˆ = EΩ (Y − fˆ)2 = 1∆∆i −ci0 ci00 ρi0 i00m2 m2 0 00i=1(2)i =1 i =1Таким образом математическое ожидание квадрата ошибкиусреднённого по ансамблю прогноза представляет собой разницумежду средней по ансамблю величиной математического ожиданияквадрата ошибки и средней величиной квадратичного отклонениямежду прогнозами вычисляемыми различными алгоритмами.Сенько Олег Валентинович ()МОТП, лекция 96 / 24Комитетные методыРассмотрим сначала несколько простейших эвристических методовпринятия коллективных решений.

Предположим, что у нас естьансамбль алгоритмов распознавания A1 , . . . , Ar , которые былииспользованы для классификации некоторого объекта s∗ .Голосование по большинству. Простейшим комитетным методомявляется является метод голосования по большинству, относящийобъект к тому классу, к которому он был присвоен относительнымбольшинством алгоритмов.Использование вещественных оценок за классы.Напомним, чтопроизвольный рспознающий алгоритм является комбинациейраспознающего оператора, вычисляющего оценки за классы ирешающего правила, производящего классификацию по оценкам,вычисленным распознающим оператором.

Предположим, что Γil (∗) оценка за класс , вычисляемая алгоритмом Ai . Коллективноерешение может строится путём вычисления коллективных оценок заклассы через оценки Γil (∗) , соответствующие отдельным алгоритмам.При этом могут использоваться различные варианты вычисленияСенько Олег Валентинович()МОТП, лекция 97 / 24коллективныхоценокКомитетные методы1) Коллективная оценка за класс Kl вычисляется каксреднеарифметическое оценок, вычисляемых алгоритмами изансамбля {A1 , .

. . , Ar }:∗Γavl (s )=rXΓjl (s∗ ).j=12) Коллективная оценка за класс Kl вычисляется как вычисляется какминимум всех оценок за данный класс полученных алгоритмами изансамбля {A1 , . . . , Ar }:Γmin(s∗ ) =lСенько Олег Валентинович ()minj∈{1,...,r}МОТП, лекция 9Γjl (s∗ ).8 / 24Комитетные методы3) Коллективная оценка за класс Kl вычисляется как вычисляется какмаксимум всех оценок за данный класс полученных алгоритмами изансамбля {A1 , . . .

, Ar }:Γmin(s∗ ) =lmax Γjl (s∗ ).j∈{1,...,r}4) Еще одним употребительным способом построения комитетногорешения является использование произведений оценок, вычисляемыхалгоритмами из ансамбля {A1 , . . . , Ar }:∗Γavl (s )=rYΓjl (s∗ ).j=1К достоинствам комитетных методов относится их простота, высокаябыстродействие. Для применения этих методов не требуется никакойдополнительной процедуры обучения, что позволяет сразу переходитьк распознаванию объектов комитетом обученных алгоритмов.Сенько Олег Валентинович ()МОТП, лекция 99 / 24Наивный байесовский корректорПодобными же достоинствами обладает другой известный методпостроения коллективных решений – «Наивный байесовскийклассификатор», который является статистическим методом,основанном на оценках вероятностей принадлежности объекта классамв зависимости от результатов классификации отдельнымиалгоритмами.

Предположим, что алгоритмы {A1 , . . . , Ar } отнеслиобъект s∗ в классы KJ(1) , . . . , KJ(r) соответственно. Факт отнесенияобъекта s в класс Ki алгоритмом Aj далее будем обозначатьAj (s) = Pi (s), где Pti (s) является предикатом, обозначающимотнесение s в класс Ki . Наибольшую точность распознаванияобеспечивает байесовский классификатор, относящий объект в классKi∗ , для которого максимальной является условная вероятностьP [s∗ ∈ Ki∗ | A1 (s∗ ) = PtJ(1) (s∗ ), . .

. , Ar (s∗ ) = PtJ(r) (s∗ )](3)Условная вероятность (1) для класса Ki может быть вычислена поформуле БайесаСенько Олег Валентинович ()МОТП, лекция 910 / 24Наивный байесовский корректорP [s∗ ∈ Ki | A1 (s∗ ) = PtJ(1) (s∗ ), . . . , Ar (s∗ ) = PtJ(r) (s∗ )] =P (Ki )P [A1 (s∗ ) = PtJ(1) (s∗ ), . . . , Ar (s∗ ) = PtJ(r) (s∗ ) | s∗ ∈ Ki ]=.P [A1 (s∗ ) = PtJ(1) (s∗ ), .

. . , Ar (s∗ ) = PtJ(1) (s∗ )]Условная вероятностьP [A1 (s∗ ) = PtJ(1) (s∗ ), . . . , Ar (s∗ ) = PtJ(1) (s∗ ) | s∗ ∈ Ki ]может быть оценена исходя из гипотезы о независимости входящих вансамбль классификаторов. То естьP [A1 (s∗ ) = PtJ(1) (s∗ ), . . . , Ar (s∗ ) = PtJ(r) (s∗ ) | s∗ ∈ Ki ] ==rYP [A1 (s∗ ) = PtJ(j) (s∗ ) | s∗ ∈ Ki ].j=1Сенько Олег Валентинович ()МОТП, лекция 911 / 24Наивный байесовский корректорВ качестве оценок вероятностейP (K1 ), . . . , P (Kl )P [A1 (s∗ ) = PtJ(j) (s∗ ) | s∗ ∈ Ki ],приj = 1, . .

. , r, i = 1, . . . , rмогут быть использованы соответствующие доли объектов обучающейвыборки. Отметим, что вероятностьP [A1 (s∗ ) = PtJ(1) (s∗ ), . . . , Ar (s∗ ) = PtJ(r) (s∗ )]является одинаковым для всех классов множителей, который может неучитываться при вычислении окончательного решения.Сенько Олег Валентинович ()МОТП, лекция 912 / 24Логическая коррекцияКомитетные методы и наивный байесовский классификатор являютсяпростейшими методами коллективной коррекции, не учитывающихвзаимодействие алгоритмов ансамбля или их относительнуюэффективность.

Требование повышения обобщающей способностиансамбля за счёт более полного учёта его структуры и использованиявозможностей лежащих в его основе эвристик. привело к созданиюсредств алгебраической и логической коррекции. Методы логическойкоррекции учитывают только окончательные результатыклассификации. Пусть у нас имеется некоторая выборкаSec = {s1 , . . . , sq } объектов, принадлежащих классам K1 , . . . , KL , покоторой мы собираемся произвести коррекцию. Данной выборкеможет быть сопоставлена информационная матрица kαli kL×q , , гдеαli = 1 при si ∈ Kl и αij = 0 в противном случае..Сенько Олег Валентинович ()МОТП, лекция 913 / 24Логическая коррекцияВыборке Sec может быть также сопоставлен набор матриц{kβlij kL×q | j = 1, . .

. , r}.Элемент βlij = 1, если Aj (si ) = Ptl (si ), и βlij = 0 в противном случае.Поиск оптимального логического корректора сводится к поиску длякаждого класса такой логической функции Fl (z1 , . . . , zr ) от булевыхпеременных z1 , . . . , zr , чтобы равенствоg(1)g(r)Fl [βli , . . . , βli ] = αliвыполнялось для возможно большего числа объектов выборки Sec .Функция g(i) устанавливает связь между переменными z1 , .

. . , zr иалгоритмами A1 , . . . , Ar . Использование g позволяет учитыватьинформативность алгоритмов для оценки принадлежностираспознаваемых объектов классу Kl , через их место в логическойфункции.Сенько Олег Валентинович ()МОТП, лекция 914 / 24Логическая коррекцияПредположим, что отсутствуют противоречия типа существования ввыборке Sec объектов si0 и si00 с неодинаковыми αli0 и αli00 , которыеоднако одинаково классифицируются алгоритмами ансамбля.

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