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

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 9Коллективные методыИспользованиеразличныхметодовпрогнозирования(распознавания), а также различных обучающих выборок илиподмножествпризнаковпозволяетполучитьпрогнозирующих (распознающих) алгоритмов:A1 ,набор, ArМожно попытаться увеличить обобщающую способность за счётвыбораалгоритмапрогнозирования.сминимальнойОднаконередкооценкойболееошибкиэффективнойпроцедурой является вычисление прогноза с использованиемвсех алгоритмов из A1 ,, Ar .Коллективные методыИспользованиеколлектива (ансамбля)алгоритмов, которыестроятся с помощью различных методов позволяет использоватьпри прогнозировании различные принципы экстраполяции,лежащих в основе этих методов.Статистическоеалгоритмовобоснованиедаётанализиспользованиюошибкивыпуклойансамблякомбинациипрогнозов, вычисляемых членами ансамбля. Предположим, чтоалгоритмы ансамбляменной YA1 ,, Arвычисляют прогноз пере-Коллективные методы.

Пустьf i - прогноз, вычисляемый алгоритмом Aii  E (Y  fi )2 -ошибка прогноза, вычисляемого Ai ,i  1,,r.2Введём обозначение ii  E ( fi  fi )-математическое ожидание квадрата отклонения друг от другапрогнозов, вычисляемых алгоритмами Ai и Ai .Пусть c1 ,.rci 1i, cr1-положительные коэффициентытакие, чтоКоллективные методыfˆОбозначим черезвыпуклую комбинацию прогнозов,rfˆ  c fвычисляемых алгоритмами ансамбля A , , A :1ri 1i iДля ошибки выпуклой комбинации справедливо выражениеrrr1ˆ  E (Y  fˆ )   ci i   cici ii2 i1 i1i 12Принимая во внимание, что все отклонениянеотрицательны, а коэффициентыrˆполучаем неравенство    ci  ii 1c1 ,iiвсегда, cr положительныКоллективные методыРассмотрим, случай, когда все алгоритмы участвуют в построенииколлективного решения равноправно.

В этом случае1ci  , i  1,r,mr1fˆ   fim i 1,rrr111ˆ  E (Y  fˆ )   i 2  iim i 12 m i1 i12Таким образом, ошибка коллективного метода, вычисляющегосредний прогноз по ансамблю равна средней ошибке по сем членамансамбля минус средний квадрат отклонений прогнозов междуучастниками ансамбля.Комитетные методы враспознаванииРассмотрим сначала несколько простейших эвристическихметодов принятия коллективных решений.Предположим, что у нас есть ансамбль алгоритмов распознаванияA1 ,, Ar , которые были использованы для классификации*sнекоторого объекта. Простейшим комитетным методомявляется является метод голосования по большинству,относящий объект к тому классу, к которому он был присвоенотносительным большинством алгоритмов.Комитетные методы враспознаванииНапомним, что произвольный рспознающий алгоритм являетсякомбинациейраспознающегооператора,вычисляющегооценки за классы и решающего правила, производящегоклассификацию по оценкам, вычисленным распознающимоператором.

Предположим, что il ( s* ) - оценка за класс K lвычисляемая алгоритмом Ai,. Коллективное решение можетстроится путём вычисления коллективных оценок за классыi*(sчерез оценки l ) , соответствующие отдельным алгоритмам.Комитетные методы враспознавании1) Коллективная оценка за класс вычисляется каксреднеарифметическое оценкам1 r i * ( s )   l ( s )r i 1avl*2) Коллективная оценка вычисляется как вычисляется какминимум всех оценок за данный класс полученных разнымиалгоритмамиlmin ( s* )  min[li ( s* )]i1, ,rКомитетные методы враспознавании3) Коллективная оценка вычисляется как вычисляется какмаксимум всех оценок за данный класс полученных разнымиалгоритмамиlmax ( s* )  max[il ( s* )]i1, ,r4) Еще одним употребительным способом построения комитетногорешения является произведение оценокr ( s )  [il ( s* )]prl*i 1Комитетные методы враспознаванииКдостоинствам комитетных методов относится их простота,высокая быстродействие.

Для применения этих методов нетребуется никакой дополнительнойпозволяетсразупереходитькпроцедуры обучения, чтораспознаваниюобъектовкомитетом обученных алгоритмов.Подобными же достоинствами обладает другой известный методпостроения коллективных решений – «Наивный байесовскийклассификатор».Наивный байесовскийклассификатор«Наивный байесовский классификатор». –является статистическимметодом,основанномнаоценкахвероятностейпринадлежности объекта классам в зависимости от результатовклассификации отдельными алгоритмами.Пусть для каждого из распознающих алгоритмовизвестна матрица оценок условных вероятностейˆ ( s*  K  | A ( s* )  " s*  K  ") |||| PlilLLA1 ,, ArНаивный байесовскийклассификаторПредположим, что алгоритмы A1 ,в классы Kt1 ,s*, Ar отнесли объект, Ktr соответственно.NB*(s) объектаДля вычисления коллективной оценки ls*закласс K l формально принимается гипотеза о независимостииклассификаторов A1 , , Ar .

В результате коллективная оценкавычисляется как произведение оценок, соответствующихотдельным классификаторамr ( s )   Pˆ ( s*  Kl | Ai ( s* )  " s*  Kti ")NBl*i 1Логическая коррекцияКомитетные методы и наивный байесовский классификатор являютсяпростейшими методами коллективной коррекции, не учитывающихвзаимодействие алгоритмов ансамбля или их относительнуюэффективность.Требование повышения обобщающей способности ансамбля засчётболееполногоучётаегоструктурыииспользованиявозможностей лежащих в его основе эвристик.

привело к созданиюсредств алгебраической и логической коррекции.Методы логической коррекции учитывают только окончательныерезультаты классификации.Логическая коррекцияПусть у нас имеется некоторая выборка Sq  {s1 ,принадлежащих классам K1 ,, sq } объектов,, K L , по которой мы собираемсяпроизвести коррекцию. Данной выборке может бытьсопоставлена информационная матрица ||  lj ||Lq , гдеlj  1, если s j  Kl и lj  0 в противном случае . Инымисловами  lj является значением предиката Pl  " s  Kl " наобъекте s j .i||||LqИ набор матрицlji, где lj значение предиката Pl наобъекте s j , вычисленное алгоритмом Ai .,Логическая коррекцияПоиск оптимального логического корректора сводится к к поиску такойлогической функции от rчтобы равенство F ( ljg (1),переменных F ( z1 ,, ljg ( r ) )  lj, zr ),выполнялось для возможнобольшего числа объектов обучающей выборки, где перестановочнаяфункция g (i) устанавливает связь между переменными z1 ,алгоритмамиA1 ,, Ar.

В том случае, когда 2r  qпротиворечия типа равенства функцииFзначенияхзначенияминформационнойаргументовматрицы,разнымзадача, zrии отсутствуютпри одних и тех жепостроенияэлементовлогическогокорректора сводится к задаче доопределения логической функцииестественным путём заданной на выборке S qкубErна весь единичныйЛогическая коррекцияПриведем в качестве примера «монотонный логическийкорректор», в основу которого положена следующая идея. Висходном наборедля каждого классаKiвыбирается поднабор A , , A .

Объект s относитсяt1tkмонотонным логическим корректором в класс K i в том иA1 ,, Arтолько в том случае, если он отнесён в K i всеми алгоритмамииз At1 , , Atk и ещё одним алгоритмом из набораA1 ,, Ar , который не принадлежит At1 ,, Atk .Логическая коррекцияПостроение монотонного логического корректора, правильноклассифицирующих объекты выборки S q сводится кпостроению монотонной булевой функции, для которойF (ljg (1) ,, ljg ( r ) )  lj для всех объектов S q .Алгебраическая коррекцияУниверсальным способом построения оптимальногораспознающего алгоритма по набору исходных алгоритмовA1 ,, Ar является использование алгебраических методовкоррекции. В отличие от логических методов коррекцииалгебраические методы используют не только окончательныеi||||Lq ,результаты классификации, содержащиеся в матрицахlji||||Lq , вычисляемые операторамино также матрицы оценокljii, Rr , где  lj  l ( s j ) - оценка объекта s j  Sq за класс ,i  1, , r , j  1, , q , l  1, , L.вычисляемая оператором Ri ,R1,Алгебраическая коррекцияОсновы теории алгебраической коррекции были разработаныЮ.И.Журавлёвым в 1976-1978 годах.Задача распознавания в алгебраической теории рассматриваетсякак задача построения по начальной информации IK1 ,, KLSq  {s1,о классахдля предъявленной для распознавания выборки, sq }информационной матрицы ||  lj ||Lq .

Обозначимданную задачу как задачу Z ( I , Sq , P1,, PL ) или просто задачу Z .Примером начальной информации о классах является таблицапризнаковых описаний эталонных объектов классов и ихинформационная матрица.Алгебраическая коррекцияПредположим, что у нас имеется множество алгоритмов { A} ,i||||Lq , составленныепереводящих пару {I , Sq } в матрицыljиз элементов {0,1, } , где значения 0 и 1 как и раньшеявляются значениями предикатов, вычисленными алгоритмамииз множества { A}, значение  соответствует отказу отвычисления значения предиката.Определение .

АлгоритмA называется корректным для задачиZ , если выполнено равенствоA( I , Sq , P1,, PL ) || lj ||Lq .Алгебраическая коррекцияАлгоритм, не являющийся корректным для задачи Z , называетсянекорректным. Совокупность { A} состоит из вообще говорянекорректных алгоритмов.Алгебраический подход к решению задач распознаваниявключает в себя введение алгебраических операций надалгоритмами из { A}, позволяющих строить корректныеалгоритмы по наборам алгоритмов из { A} . Поскольку каждыйраспознающий алгоритм может быть представлен какпоследовательное выполнение распознающего оператораирешающего правила, множеству { A} соответствуют множестваоператоров {R} и множество решающих правил {C} .Алгебраическая коррекцияКаждый из операторов из множества {R}вычисляет для**R(I,S)||||Lqзадачи Z матрицу оценок за классыqljНа множестве операторов {R} вводятся операциисложения, умножения и умножения на скаляр.Пусть R, R {R}R( I , Sq ) ||  lj ||Lq R( I , Sq ) ||  lj ||Lqb скалярная величина.Определим операторы b  R (умножение на скаляр), R  R(сложение), R  R (умножени е) следующим образом.Алгебраическая коррекция(b  R)( I , Sq ) || b   lj ||Lq(1)( R  R)( I , Sq ) ||  lj   lj ||Lq (2)( R  R)( I , Sq ) ||  lj *  lj ||Lq(3)Использование операций (1)-(3) позволяет строить новыераспознающие операторы, являющиеся полиномами отоператоров из исходного множества видаNpa Ri 1it (1,i ) Rt ( ki ,i ) .Функция t ( j , i ) - указывает на оператор, являющийся j  ымсомножителем в i  ом слагаемом полинома.Алгебраическая коррекцияОчевидно, что замыкание L{R} множества операторов {R}относительно операций (1) и (2) является линейным векторнымпространством.