Лекция 9. Структура ошибки выпуклых комбинаций_ комитетные методы_ логическая коррекция (2014 Лекции (Сенько))
Описание файла
Файл "Лекция 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 , которыеоднако одинаково классифицируются алгоритмами ансамбля.