Лекции. ММО. Сенько (all in one) (1185303), страница 14
Текст из файла (страница 14)
По выборкамSeνl и Seνr рассчитывается статистика критерия и устанавливаетсясоответствующее p-значение. В том случае, если полученноеp-значение оказывается меньше заранее фиксированного уровнязначимости вершина ν считается внутренней. В противном случаевершина ν считается концевой.Использование критериев ранней остановки не всегда позволяетадекватно оценить необходимую глубину дерева. Слишком ранняяостановка ветвления может привести к потере информативныхпредикатов, которые могут быть на самом деле найдены только придостаточно большой глубине ветвления.Сенько Олег Валентинович ()МОТП, лекция 213 / 15Решающие деревья.
ПодрезкаВ связи с этим нередко целесообразным оказывается построениесначала полного дерева, которое затем уменьшается до оптимальногос точки зрения достижения максимальной обучающей способностиразмера путём объединения некоторых концевых вершин. Такойпроцесс в литературе принято называть «pruning» («подрезка»).При подрезке дерева может быть использован критерийцелесообразности объединения двух вершин, основанный на сравнениена контрольной выборке точности распознавания до и послепроведения «подрезки».Ещё один способ оптимизации обобщающей способности деревьевоснован на учёте при «подрезке» дерева до некоторой внутреннейвершины ν одновременно увеличения точности разделения классов наобучающей выборке и увеличения сложности, которые возникаютблагодаря ветвлению из ν.Сенько Олег Валентинович ()МОТП, лекция 214 / 15Решающие деревьяПри этом прирост сложности, связанный с ветвлением из вершины ν,может быть оценён через число листьев в поддереве Tsubполногоνрешающего дерева с корневой вершиной ν.
Следует отметить, чторост сложности является штрафующим фактором, компенсирующимприрост точности разделения на обучающей выборке с помощьювключения поддерева Tsubв решающее дерево. Разработан целый рядνэвристических критериев, которые позволяют оценитьцелесообразность включения Tsubν . Данные критерии учитываютодновременно сложность и разделяющую способность.Сенько Олег Валентинович ()МОТП, лекция 215 / 15Коллективные решения,ансамблиЛектор – Сенько Олег ВалентиновичКурс «Математические методы обучения»Сенько Олег Валентинович ()Коллективные решения1/8Содержание лекции1Ошибки выпуклых комбинацииСенько Олег Валентинович ()Коллективные решения2/8Коллективные решенияЗадачи прогнозирования некоторой величины Y с помощьюпредикторов Z1 , .
. . , ZM . Под предикторами понимаются некоторыеалгоритмы, прогнозирующие Y . Наборы алгоритмов, над которымистроятся коллективные решения в литературе по машинному обучениюпринято называть ансамблями. ПустьZccp =LXci Zi ,i=1гдеLXci = 1,i=1ci ≥ 0, i = 1, . . . , LСенько Олег Валентинович ()Коллективные решения3/8Структура ошибки ZccpВведём обозначение:δi = E(Y − Zi )2 − ошибка предиктора Zi .LXδi =i=1= E{LXci (Y − Zccp + Zccp − Zi )2 } =i=12= E{(Y − Zccp ) +LX2ci (Zccp − Zi ) + 2(Y − Zccp )i=1Сенько Олег Валентинович ()LX(Zi − Zccp )}i=1Коллективные решения4/8Структура ошибки ZccpОднакоLX(Zi − Zccp ) = 0i=1по определению ZccpСледовательно2δZccp = E(Y − Zccp ) =LXδi −i=1LX−E[ci (Zccp − Zi )2 ]i=1Сенько Олег Валентинович ()Коллективные решения5/8Структура ошибки ZccpРассмотрим слагаемое−LXci (Zccp − Zi )2i=1Ннетрудно показать, что оно может быть представлено в виде2Zccp−LXi=1Сенько Олег Валентинович ()ci Zi2 =LL XXci0 ci00 Zi0 Zi00 −i0 =1 i00 =1Коллективные решенияLXci Zi2i=16/8Структура ошибки ZccpВоспользуемся равенством1Zi0 Zi00 = − {(Zi0 − Zi00 )2 −2−Zi20 − Zi200 } =Откуда следуетL XLXci0 ci00 Zi0 Zi00 −i0 =1 i00 =1LXci Zi2 =i=1LL1XX=−ci0 ci00 (Zi0 − Zi00 )2 +2 0 00i =1 i =1+LLLX1X1 Xci0 Zi20 +ci00 Zi200 −ci Zi22 02 00i =1Сенько Олег Валентинович ()i =1Коллективные решенияi=17/8Структура ошибки ZccpОткуда следует−LXi=1LL1XXci (Zccp − Zi ) = −ci0 ci00 (Zi0 − Zi00 )22 0 002i =1 i =1Введём обозначениеρi0 i00 = E(Zi0 − Zi00 )2Сенько Олег Валентинович ()Коллективные решения8/8Структура ошибки ZccpδZccp =LXi=1Сенько Олег Валентинович ()LL1XXδi −ci0 ci00 ρi0 i002 0 00i =1 i =1Коллективные решения9/8Лекция 9Структура ошибки выпуклых комбинаций,комитетные методы, логическая коррекцияЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 91 / 30Содержание лекции1Впуклые комбинации алгоритмов2Комитетные методы3Наивный байесовский корректор4Логическая коррекция5Алгебраическая коррекцияСенько Олег Валентинович ()МОТП, лекция 92 / 30Ансамбли алгоритмовИспользование различных методов прогнозирования (распознавания),а также различных обучающих выборок или подмножеств признаковпозволяет получить набор прогнозирующих (распознающих)алгоритмов: A1 , .
. . , Ar Можно попытаться увеличить обобщающуюспособность за счёт выбора алгоритма с минимальной оценкойошибки прогнозирования. Однако нередко более эффективнойпроцедурой является вычисление прогноза с использованием всехалгоритмов из A1 , . . . , Ar . Использование коллектива (ансамбля)алгоритмов, которые строятся с помощью различных методовпозволяет использовать при прогнозировании различные принципыэкстраполяции, лежащих в основе этих методов.
Статистическоеобоснование использованию ансамбля алгоритмов даёт анализ ошибкивыпуклой комбинации прогнозов, вычисляемых членами ансамбля.Предположим, что алгоритмы ансамбля A1 , . . . , Ar вычисляютпрогноз переменной Y .Сенько Олег Валентинович ()МОТП, лекция 93 / 30Выпуклые комбинацииПусть 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 / 30Для ошибки выпуклой комбинации справедливо выражениеˆ = 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 / 30Рассмотрим, случай, когда все алгоритмы участвуют в построенииколлективного решения равноправно.
В этом случае 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 / 30Комитетные методыРассмотрим сначала несколько простейших эвристических методовпринятия коллективных решений.
Предположим, что у нас естьансамбль алгоритмов распознавания A1 , . . . , Ar , которые былииспользованы для классификации некоторого объекта s∗ .Голосование по большинству. Простейшим комитетным методомявляется является метод голосования по большинству, относящийобъект к тому классу, к которому он был присвоен относительнымбольшинством алгоритмов.Использование вещественных оценок за классы.Напомним, чтопроизвольный рспознающий алгоритм является комбинациейраспознающего оператора, вычисляющего оценки за классы ирешающего правила, производящего классификацию по оценкам,вычисленным распознающим оператором. Предположим, что Γil (∗) оценка за класс , вычисляемая алгоритмом Ai .
Коллективноерешение может строится путём вычисления коллективных оценок заклассы через оценки Γil (∗) , соответствующие отдельным алгоритмам.При этом могут использоваться различные варианты вычисленияСенько Олег Валентинович()МОТП, лекция 97 / 30коллективныхоценокКомитетные методы1) Коллективная оценка за класс Kl вычисляется каксреднеарифметическое оценок, вычисляемых алгоритмами изансамбля {A1 , . . . , Ar }:∗Γavl (s )=rXΓjl (s∗ ).j=12) Коллективная оценка за класс Kl вычисляется как вычисляется какминимум всех оценок за данный класс полученных алгоритмами изансамбля {A1 , . . .
, Ar }:Γmin(s∗ ) =lСенько Олег Валентинович ()minj∈{1,...,r}МОТП, лекция 9Γjl (s∗ ).8 / 30Комитетные методы3) Коллективная оценка за класс Kl вычисляется как вычисляется какмаксимум всех оценок за данный класс полученных алгоритмами изансамбля {A1 , . . . , Ar }:Γmin(s∗ ) =lmax Γjl (s∗ ).j∈{1,...,r}4) Еще одним употребительным способом построения комитетногорешения является использование произведений оценок, вычисляемыхалгоритмами из ансамбля {A1 , . . .
, Ar }:∗Γavl (s )=rYΓjl (s∗ ).j=1К достоинствам комитетных методов относится их простота, высокаябыстродействие. Для применения этих методов не требуется никакойдополнительной процедуры обучения, что позволяет сразу переходитьк распознаванию объектов комитетом обученных алгоритмов.Сенько Олег Валентинович ()МОТП, лекция 99 / 30Наивный байесовский корректорПодобными же достоинствами обладает другой известный методпостроения коллективных решений – «Наивный байесовскийклассификатор», который является статистическим методом,основанном на оценках вероятностей принадлежности объекта классамв зависимости от результатов классификации отдельнымиалгоритмами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
