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

, ar(j)n , bn ]для закономерности r(j) осуществляется сначала на некоторойнеравномерной сетке пространства, которая задается с помощьюразбиения интервала значений каждого из признаков. Посленахождения оптимальных границ на заданной сетке, поискпродолжается на заданной в окрестности этого оптимального решения,но уже на более мелкой сетке. Процесс заканчивается, если припереходе к более мелкой сетке не удается найти логическуюзакономерность с более высоким критерия качества Φ. . Задача поискаоптимальной логической закономерности на каждой сетке сводится кпоиску максимальной совместной подсистемы некоторой системынеравенств. Логические закономерности, построенные для случайновыбранных «опорных» эталонов класса Kj объединяются в одноej .множество RСенько Олег Валентинович ()МОТП, лекция 1013 / 22Статистически взвешенные синдромыКоллективные решения в методе СВС принимается по информации опринадлежности векторного описания распознаваемого объекта такe Подназываемым “синдромам” из некоторого множества Q."синдромом"понимается такая область признакового пространства, вкоторой содержание объектов одного из классов, отличается отсодержания объектов этого класса в обучающей выборке или покрайней мере в одной из соседних областях.

Пример синдромов,характеризующих разделение объектов из классов K1 ( ) и K2 ( )приведён на рисунке 2. Синдромы ищутся для каждого израспознаваемых классов с помощью построения оптимальныхразбиений интервалов допустимых значений единичных признаков илисовместных двумерных областей допустимых значений пар признаков.Сенько Олег Валентинович ()МОТП, лекция 1014 / 22Статистически взвешенные синдромыРис 2. Видно, описания объектов из сосредоточены главным образомв нижнем левом квадранте «синдроме».Сенько Олег Валентинович ()МОТП, лекция 1015 / 22Статистически взвешенные синдромыПри этом поиск производится внутри нескольких семейств разбиений,имеющих различный уровень сложности.

В ходе поиска выбираетсяразбиение с максимальным значением функционала качества.Используется два функционала качества, зависящих от обучающейвыборки Set , распознаваемого класса Kl , и разбиения R:интегральный Fi (Set , Kl , R);локальный Floc (Set , Kl , R).Обозначим через q1 , . . . , qr элементы некоторого разбиения R . Пустьν0l является долей объектов класса Kl в обучающей выборке Set , νil доля объектов Kl среди объектов, описания которых принадлежатэлементу qi , mi - число объектов, описания которых принадлежатэлементу qi . Интегральный функционал определяется формулойFi (Set , Kl , R) =rX(ν0l − νil )2 mi .i=1Сенько Олег Валентинович ()МОТП, лекция 1016 / 22Статистически взвешенные синдромыЛокальный функционал определяется формулойFi (Set , Kl , R) = max (ν0l − νil )2 mi .i=1,...,rПоиск разбиений с максимальным значением одного из функционаловпроизводится в рамках одного из четырёх семейств. Примерыразбиений для каждого из семейств приведены на рисунке.Семейство I включает всевозможные разбиения интерваловдопустимых значений отдельных признаков на два интервала спомощью одной граничной точки.Семейство II включает всевозможные разбиения интерваловдопустимых значений отдельных признаков на 3 интервала с помощьюдвух граничных точек.Сенько Олег Валентинович ()МОТП, лекция 1017 / 22Статистически взвешенные синдромыРис 3.

Примеры разбиений для каждого из четырёх семейств,используемых в методе СВС.Сенько Олег Валентинович ()МОТП, лекция 1018 / 22Статистически взвешенные синдромыСемейство III включает всевозможные разбиения совместныхдвумерных областей допустимых значений пар признаков на 4подобласти с помощью двух граничных точек ( по одной точке длякаждого из двух признаков).Семейство IV включает всевозможные разбиения совместныхдвумерных областей допустимых значений пар признаков на 2подобласти с помощью прямой граничной линии, произвольноориентированной относительно координатных осей.Найденные оптимальные разбиения используются для построениясистем синдромов, если соответствующая им максимальная величинафункционала качества превосходит некоторое заранее заданноепользователем пороговое значение δ.

Причём величина порога зависитот сложности модели разбиений. Порог является минимальным дляпростейшей одномерной модели I. Для моделей II-IV величина порогадомножается на величину , задаваемую пользователем, что позволяетрегулировать влияние эффекта переобучения.Сенько Олег Валентинович ()МОТП, лекция 1019 / 22Статистически взвешенные синдромыОдномерные разбиения, найденные внутри семейств I и II могут бытьиспользуются при построении не только одномерных, но также идвумерных синдромов. Предположим, что на этапе обучения дляe l . Предположим, чтокласса Kl найдена система синдромов Q∗описание x распознаваемого объекта s∗ принадлежит синдромамe l .

Оценка s∗ за класс Kl вычисляется поq1 , . . . , qr из системы QформулеPrwil νil∗,Γl (s ) = Pi=1rli=1 wiгде νil - доля класса Kl в синдроме qi , wil - вес синдрома приклассификации класса Kl . Вес синдрома вычисляется по формулеwil =mi1,lmi + 1 νi (1 − νil )где mi - число объектов обучающей выборки с описанием,принадлежащем qi .Сенько Олег Валентинович ()МОТП, лекция 1020 / 22Метод комитетовМетод комитетов представляет собой реализацию подхода к решениюзадач распознавания, объединяющего принципы линейногоразделения классов и вычисления коллективных решений. Рассмотримзадачу распознавания с двумя классами K1 и K2 .

Пустьfe = {f1 (x), . . . , fr (x)} является набором линейных функций видаfi (x) = a1i x1 + . . . + ani xn ,где x = (x1 , . . . , xn ) является вектор используемых для распознаванияпризнаков, (a1i , . . . , ani )- вектор вещественных параметров, задающихлинейную функцию fi (x). Каждая из функций из fe рассматривается вкачестве отдельного линейного классификатора, относящего объект сописанием x в класс K1 , если sign[fi x] > 0, и в класс K2 в противномслучае. .Сенько Олег Валентинович ()МОТП, лекция 1021 / 22Метод комитетовПредположим, что для классификации произвольного объекта s сописанием x используется следующее решающее правило методакомитетов:Pобъект s относится в класс K1 , если ri=1 sign[fi (x)] > 0;объектs с описанием x относится в класс K2 , еслиPri=1 sign[fi (x)]P< 0;в случае, если ri=1 sign[fi (x)] = 0 происходит отказ отраспознавания.Набор функций fe называется комитетом, если решающее правилометода комитетов правильно классифицирует объекты обучающейвыборки.Метод, основанный на поиске комитетов, потенциально позволяетпроизводить распознавание линейно неразделимых классов, реализуякусочно-линейную разделяющую поверхность.

Обучение сводится кпоиску оптимальных (минимальных по числу функций) комитетов.Теоретически показано существование комитета длянепротиворечивых данных.Сенько Олег Валентинович ()МОТП, лекция 1022 / 22.