Лекция 10 (2012 Лекции МОТП (Сенько))

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 10Коллективные методыОдним из способов получения ансамбля является использованиеалгоритмов, обученных по разным обучающим выборкам,возникающим в результате случайного процесса, лежащего воснове исследуемой задачи. Обычно при решении прикладнойзадачи в распоряжении исследователя имеется обучающаявыборка St  {s1,, sm} ограниченного объёма. Однакопроцесс генерации семейства выборок из генеральнойсовокупности может быть имитирован с помощью процедурыбутстрэп (bootstrap), которая основана на выборках свозвращениями из St .Коллективные методы (бэггинг)В результате получаются выборки Sbg , включающие объекты изобучающей выборки St .

Однако некоторые объекты могутвстречаться более одного раза, а другие объекты отсутствовать.Предположим, что с помощью процедуры бутстрэп полученовыборок Sbg , Выберем метод , который далее используется Tдля обучения отдельных алгоритмов распознавания. Вbgрезультате у нас будет получено T алгоритмов A1 ,, ATbg . Дляполучения коллективного решения может быть использованпростейший комитетный метод , относящий объект в тот класс,куда его отнесло большинство алгоритмов.Коллективные методы(бэггинг)Данная процедура носит название бэггинг (bagging), что являетсясокращением названия BootstrapбэггингпоказываетвысокийAggregating.приростПроцедураобобщающейспособности по сравнению с алгоритмом, обученным спомощью базового метода по исходной обучающей выборке St ,в тех случаях, когда вариационная составляющая ошибкибазового метода высока. К таким моделям относятся вчастности решающие деревья и нейросетевые методы.

Прииспользованиивкачествебазовогометодарешающихдеревьев процедура бэггинг приводит к построению ансамблейрешающих деревьев (решающих лесов).Коллективные методы (бустинг)Основнойидеейнаращиваниеалгоритмаансамблябустингалгоритмов.присоединяется к ансамблю навыборке,котораяявляетсяпошаговоеАлгоритм,которыйk -ом шаге обучается поформируетсяизобъектовисходнойобучающей выборки St . В отличие от метода бэггинг объектывыбираютсянеравноправно,аисходяизнекотороговероятностного распределения, заданного на выборке StДанноераспределениеклассификацииспредыдущем шаге.вычисляетсяпомощьюансамбля,по.результатамполученногонаКоллективные методы (бустинг)Приведём схему одного из наиболее популярных вариантовметода бустинг AdaBoost (Adaptive boosting) более подробно.На первом шаге присваиваем начальные значения весов( w11,, w1m ) объектам обучающей выборки. Поскольку весаимеют вероятностнуюинтерпретаци, то для них соблюдаютсяmограничения1w j 1j 1w,1j [0,1].

Обычно начальноераспределение выбирается равномерным1w  ,m1jj  1,,m. Выбираем число итераций T .Коллективные методы (бустинг)bsНа k -ой итерации генерируем выборку S k из исходной выборкиk(wSt согласно распределению задаваемому весами1,, wmk ) .bsAОбучаем распознающий алгоритм k по выборке S kbs .mВычисляем взвешенную ошибку по формуле  k   wkj ekjj 1bsAгде e  1 , если алгоритм k неправильно классифицировалkjbsобъект s j  Sk иekj  0 в противном случае.

В том случае,если  k  0.5 или  k  0игнорируем шаг и зановоbsSгенерируем выборку k исходя из весовых коэффициентов1w  ,mkjj  1,,m,Коллективные методы (бустинг) k  (0,0.5) вычисляем коэффициентыВ случае еслиkk 1 kwи пересчитываем веса объектов по формулеk 1j1ekjw ( k )kjmkw j ( k )1ekjj  1,,mj 1Процесс продолжается до тех пор, пока не выполнено Tитераций .

В результате мы получаем совокупностьbsраспознающих алгоритмов A1 ,, ATbs .Коллективные методы (бустинг)*Предположим, что нам требуется распознать объект s . Оценкаобъекта s* за* класс K lsTl ( s* )   ln(k 11kвычисляется по формуле) l ( s* ) где l ( s* )  1 , если объект s* отнесёнbs*A(s)  0 в противном случае.в класс K l алгоритмом k иl*Объект s будет отнесён к классу, оценка за котороймаксимальна.Описанный вариант метода носит название AdaBoost. M1.Коллективные методы (бустинг)Эффективность процедур бустинга подтверждаетсямногочисленными экспериментами на реальных данных.В настоящее время существует большое количествовариантов метода, имеющих разное обоснование.Коллективные методы, основанные наголосовании по системамзакономерностейОднимизэффективныхподходовкрешениюзадачпрогнозирования и распознавания является использованиеколлективных решений по системам закономерностей.Подзакономерностьюилипрогностическийпонимаетсяалгоритм,распознающийопределённыйнанекоторойподобласти признакового пространства или связанный снекоторым подмножеством признаков.Коллективные методы, основанные наголосовании по системам закономерностейВ качестве примера закономерностей могут быть приведеныпредставительныенаборы,являющиесяпосутиподмножествами признаковых описаний, характерных дляодногоизраспознаваемыхклассов.Аналогомпредставительный наборов в задач с вещственнозначнойинформацией являются логические закономерности классов.Методы, основанные на голосовании посистемам логических закономерностейПод логической закономерностьюK l понимаетсяпризнаковогоклассаобластьпро-странства, имеющаяформугиперпарал-лелепипеда и содер-жащаяобъекты K l .толькоМетоды, основанные на голосовании посистемам логических закономерностейЛогическая закономерность r задаётся с помощью конъюнкцийпредикатов видаPi r (s)  "birl  xi (s)  birr "При этом для характеризующего закономерность класса K lпредикатаPr ( s)  P1r ( s) && Pnr ( s)Должны выполняться следующие условия1) s j*  Kl  St , Pr (s j* )  1Методы, основанные на голосовании посистемам логических закономерностей2) s j*  St , s j*  Kl , Pr (s j* )  03) Pr ( s) доставляет экстремум некоторому функционалукачества  (P) , заданному на множестве всевозможныхпредикатов, удовлетворяющих условиям 1), 2).На практике используются такие функционалы качества  (P)как число объектов из St  Kl , для которых Pr ( s)  1, доляобъектовSt  Kl , для которых Pr ( s)  1.Методы, основанные на голосовании посистемам логических закономерностейНаряду с полными логическими закономерностями, для которыхвыполняются все условия 1) – 3), используются также частичныелогические закономерности, для которых допускаютсянекоторые нарушения условия 2).

То есть допускаетсясуществование небольшой доли нарушений условия 2) для техобъектов, для которых выполняется условие Pr ( s)  1На этапе обучения для каждого из классов K l ищется множествологических закономерностей Rl .Методы, основанные на голосовании посистемам логических закономерностейПредположим, что нам требуется распознать новый объектs* . Для каждого из классов K l ищется число закономерностейr*из Rl для которых P ( s )  1 .

При этом доля такихзакономерностей считается оценкой за класс K l . Дляклассификации используется стандартное решающееправило, т.е. объект относится в класс, оценка за которыймаксимальна.Методы, основанные на голосовании посистемам логических закономерностейПоиск оптимальной системы логических закономерностейпроизводится по набору случайно выбранных из обучающейвыборки эталонных объектов (опорных эталонов). Для каждогоиз опорного эталона Siпоиск оптимальных границ(b1rl , b1rr ),осуществляется сначала на некоторой,(bnrl , bnrr )неравномерной сетке пространства, котораязадается спомощью разбиения интервала значений каждого изпризнаков. После нахождения оптимальной закономерности назаданной сетке, поиск продолжается на заданной в окрестностиэтого оптимального решения, но уже на более мелкой сетке.Методы, основанные на голосовании посистемам логических закономерностейПроцесс заканчивается, если при переходе к более мелкой сеткене удается найти ЛЗ с более высоким критерия качества  (P) .• Задача поиска оптимальной ЛЗ на каждой сетке сводится кпоиску максимальной совместной подсистемы некоторойсистемы неравенств.

Далее все вычисления повторяются для kслучайно выбранных «опорных» эталонов класса K j , а всенайденные логические закономерности объединяются в одно• множество P j .Метод статистически взвешенныхсиндромов (СВС)КоллективныеинформациирешенияовметодепринадлежностиСВСпринимаетсяповекторного x* описанияраспознаваемого объекта “синдромам” из некоторой заранеезаданной системыQ. Под синдромом понимается такаяобласть признакового пространства, в которой содержаниеобъектов одного из классов, отличается от содержания объектовэтого класса в обучающей выборке или по крайней мере водной из соседних областях.Метод статистически взвешенныхсиндромов (СВС)Пример синдромов,характеризующихразделение объектов изклассовK2K1(+)и(O)приведён на рисунке 2.Видно, описания объетов изK1сосредоточены главнымобразом в нижнем левомРисунок 2квадранте «синдроме».Метод статистически взвешенныхсиндромов (СВС)Синдромы ищутся для каждого из распознаваемых классов спомощью построения оптимальных разбиений интерваловдопустимых значений единичных признаков или совместныхдвумерных областей допустимых значений пар признаков.

Приэтом поиск производится внутри нескольких семействразбиений, имеющих различный уровень сложности. В ходепоиска выбирается разбиение с максимальным значениемфункционала качества. Используется два функционала качества:интегральный Fs ( K j , St , R) и локальный. FL ( K j , St , R)Метод статистически взвешенныхсиндромов (СВС)Обозначим черезr1 ,, rtэлементы некоторого разбиения R .jПусть 0 - доля объектов класса K j в обучающей выборке St , i j - доля объектов K j , описания которых принадлежатэлементу ri , mi - число объектов, описания которыхпринадлежат элементу ri .Интегральный функционал определяется формулойtFs ( K j , St , R)   ( 0j  i j ) 2 mii 1Метод статистически взвешенныхсиндромов (СВС)Локальный функционал качества задаётся в видеFL ( K j , St , R)  max ( 0j  i j )2 mii{1, ,t }Поиск разбиений с максимальным значением одного изфункционалов производится в рамках одного из четырёхсемейств.