Лекции. ММО. Сенько (all in one) (1185303), страница 15
Текст из файла (страница 15)
Предположим, что алгоритмы {A1 , . . . , Ar } отнеслиобъект s∗ в классы KJ(1) , . . . , KJ(r) соответственно. Факт отнесенияобъекта s в класс Ki алгоритмом Aj далее будем обозначатьAj (s) = Pti (s), где Pti (s) является предикатом, обозначающимотнесение s в класс Ki . Наибольшую точность распознаванияобеспечивает байесовский классификатор, относящий объект в классKi∗ , для которого максимальной является условная вероятностьP [s∗ ∈ Ki∗ | A1 (s∗ ) = PtJ(1) (s∗ ), . . . , Ar (s∗ ) = PtJ(r) (s∗ )](3)Условная вероятность (1) для класса Ki может быть вычислена поформуле БайесаСенько Олег Валентинович ()МОТП, лекция 910 / 30Наивный байесовский корректор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 / 30Наивный байесовский корректорВ качестве оценок вероятностей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 / 30Логическая коррекцияКомитетные методы и наивный байесовский классификатор являютсяпростейшими методами коллективной коррекции, не учитывающихвзаимодействие алгоритмов ансамбля или их относительнуюэффективность. Требование повышения обобщающей способностиансамбля за счёт более полного учёта его структуры и использованиявозможностей лежащих в его основе эвристик.
привело к созданиюсредств алгебраической и логической коррекции. Методы логическойкоррекции учитывают только окончательные результатыклассификации. Пусть у нас имеется некоторая выборкаSec = {s1 , . . . , sq } объектов, принадлежащих классам K1 , . . . , KL , покоторой мы собираемся произвести коррекцию. Данной выборкеможет быть сопоставлена информационная матрица kαli kL×q , , гдеαli = 1 при si ∈ Kl и αij = 0 в противном случае..Сенько Олег Валентинович ()МОТП, лекция 913 / 30Логическая коррекцияВыборке 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 / 30Логическая коррекцияПредположим, что отсутствуют противоречия типа существования ввыборке Sec объектов si0 и si00 с неодинаковыми αli0 и αli00 , которыеоднако одинаково классифицируются алгоритмами ансамбля.
То естьβlij 0 = βlij 00 при j = 1, . . . , r.В случае, если задана какая-либо функция g, а множество векторов{(βli1 , . . . , βlir ) | i = 1, . . . , r}включает всё множество вершин единичного куба Er , логическаяфункция Fl оказывается полностью определённой. В противномслучае задача построения логического корректора включает в себязадачу доопределения логической функции естественным путёмзаданной на выборке Sec на весь единичный куб Er .Сенько Олег Валентинович ()МОТП, лекция 915 / 30Логическая коррекцияОдним из способов логической корреции является построениемонотонных корректоров, которое сводится к поиску такой функции g,что логическая функция Fl , правильно вычислющая элнментыинформационной матрицы, является монотонной.
То есть ищетсяфункция g(i), котораяа) удовлетворяет равенствуg(1)g(r)Fl [βli , . . . , βli ] = αliпри i = 1, . . . , q;б) для любых векторов (z10 , . . . , zr0 ) и (z100 , . . . , zr00 ), удовлетворяющихусловию(z10 , . . . , zr0 ) (z100 , . . . , zr00 )выполняется неравенствоFl (z10 , . . . , zr0 ) Fl (z100 , . . . , zr00 ).Сенько Олег Валентинович ()МОТП, лекция 916 / 30Логическая коррекцияПостроение монотонных корректоров сводится к следующей схеме.
Висходном наборе A1 , . . . , Ar для каждого класса Kl выбираетсяподнабор Af (1) , . . . , Af (k) . Объект s относится монотоннымлогическим корректором в класс Kl в том и только в том случае, еслион отнесён в Kl всеми алгоритмами из Af (1) , . . . , Af (k) и ещё однималгоритмом из набора A1 , . . . , Ar , который не принадлежитAf (1) , . .
. , Af (k) .Сенько Олег Валентинович ()МОТП, лекция 917 / 30Алгебраическая коррекцияУниверсальным способом построения оптимального распознающегоалгоритма по набору исходных алгоритмов A1 , . . . , Ar являетсяиспользование алгебраических методов коррекции. В отличие отлогических методов коррекции алгебраические методы используют нетолько окончательные результаты классификации, содержащиеся вматрицах kβlij kL×q , но также матрицы оценок kγlij kL×q , вычисляемыеоператорами R1 , .
. . , Rk , входящими в алгоритмы A1 , . . . , Ar .Элемент γlij является оценкой объекта si за класс Kl , вычисляемаяоператором Rj , i = 1, . . . , q,l = 1, . . . , L, j = 1, . . . , r. Основы теорииалгебраической коррекции были разработаны Ю.И.Журавлёвым в1976-1978 годах. Задача распознавания в алгебраической теориирассматривается как задача построения по начальной информации I оклассах K1 , . . . , KL для предъявленной для распознавания выборкиjkL×q . .Sec = {s1 , .
. . , sq } правильной информационной матрицы kαliСенько Олег Валентинович ()МОТП, лекция 918 / 30Алгебраическая коррекцияПоследнюю задачу мы будем называть задачей Z(I, Sec , Pt1 , . . . , PtL )или просто задачей Z. Примером начальной информации о классахявляется таблица признаковых описаний эталонных объектов классови их информационная матрица.
Предположим, что у нас имеетсямножество алгоритмов {A} , переводящих пару (I, Sec ) в матрицыkβlij kL×q , составленные из элементов {0, 1, ∆} , где значения 1 и 0 каки раньше соотвествуют истинности или ложности предикатов,вычисленными алгоритмами из множества {A} , значение ∆соответствует отказу от вычисления значения предиката.Определение 1. Алгоритм A называется корректным для задачи Z,если выполнено равенствоA(I, Sec , Pt1 , .
. . , PtL ) = kαli kL×q .Алгоритм, не являющийся корректным для задачи Z , называетсянекорректным.Сенько Олег Валентинович ()МОТП, лекция 919 / 30Алгебраическая коррекцияСовокупность {A} состоит из вообще говоря некорректныхалгоритмов. Алгебраический подход к решению задач распознаваниявключает в себя введение алгебраических операций над алгоритмамииз {A} , позволяющих строить корректные алгоритмы по наборамалгоритмов из {A} . Поскольку каждый распознающий алгоритмможет быть представлен как последовательное выполнениераспознающего оператора и решающего правила, множеству {A}соответствуют множества операторов {R} и множество решающихправил {C} .
Каждый из операторов из множества {R} вычисляет длязадачи Z матрицу оценок за классыR∗ (I, Sec ) = kγli∗ kL×qНа множестве операторов {R} вводятся операции сложения,умножения и умножения на скаляр.Сенько Олег Валентинович ()МОТП, лекция 920 / 30Алгебраическая коррекцияПредположим, что R0 и R00 являются операторами из {R}. При этомR0 (I, Sec ) = kγ 0 li kL×q и R00 (I, Sec ) = kγ 00 li kL×q .
Пусть b являетсянекоторой скалярной величиной. Операция умножения на скалярпреобразует оператор R0 в оператор (b • R0 ), задаваемый формулой(b • R0 )(I, Sec ) = kbγ 0 li kL×q ,(4)Сумма операторов (R0 + R00 ) задаётся формулой(R0 + R00 )(I, Sec ) = kγ 0 li + γ 00 li kL×q ,(5)Произведение операторов (R0 • R00 ) задаётся формулой(R0 + R00 )(I, Sec ) = kγ 0 li · γ 00 li kL×q ,Сенько Олег Валентинович ()МОТП, лекция 9(6)21 / 30Алгебраическая коррекцияИспользование операций (4)-(6) позволяет строить новыераспознающие операторы, являющиеся полиномами от операторов изисходного множества видаNpXai [Rt(1,i) • . .
. • Rt(k(i),i) ]i=1Функция t(j, i) указывает на оператор, находящийся в позиции jслагаемом с номером i, ki -число сомножителей в слагаемом сномером i. Очевидно, что замыкание L{R} множества операторов{R} относительно операций (4) и (5) является линейным векторнымпространством. Обозначим через U{R} алгебраическое замыканиемножества {R} относительно операций (4)-(6).Рассмотрим условия, существования корректного алгоритма длянекоторой задачи Z(I, Sec , Pt1 , . .
. , PtL ).Сенько Олег Валентинович ()МОТП, лекция 922 / 30Алгебраическая коррекция. Определение 2. Если множество матриц {R(I, Sec )} , где операторыпробегают множество {R}, содержит базис в пространстве числовыхматриц размерности L × q , то задача Z(I, Sec , Pt1 , . . .
, PtL )называется полной относительно {R}.Определение 3. Решающее правило C называется корректным , еслидля всякой выборки длины q существует хотя бы одна числоваяматрица kγ 0 li kL×q такая, чтоC(kγ 0 li kL×q ) = kαli kL×qПусть {A} является множество алгоритмов вида A = R ⊗ C ∗ , гдеR ∈ {R}, C ∗ - некоторое корректное решающее правило.Определение 4. Множества алгоритмов вида A = R ⊗ C ∗ , будутобозначаться L{A} и U{A}, если R ∈ L{R} и R ∈ U{R}соответственно.Сенько Олег Валентинович ()МОТП, лекция 923 / 30Алгебраическая коррекцияПусть C ∗ - некоторое корректное решающее правило.Теорема 1. Если множество {Z} состоит лишь из задач , полныхотносительно {R}, то линейное замыкание L{A = R ⊗ C ∗ }, являетсякорректным относительно {Z}.Доказательство.
Пусть M является матрицей, которая может бытьпереведена решающим правилом C ∗ в информационную матрицуkαli kL×q . Существование матрицы M следует из корректностирешающего правила C ∗ . При фиксированном q базис в пространствечисловых матриц размерности L × q состоит из Lq матрицM1 , . . . , MLq .Тогда существуют такие числа c1 , . . .
, cLq , чтоPM = Lqi=1 ci Mi .Сенько Олег Валентинович ()МОТП, лекция 924 / 30Алгебраическая коррекцияВ том случае, если матрицы M1 , . . . , MLq построены из {I, Sec } спомощью операторов R1 , . . . , RLq из {R} , корректный алгоритм Acorrможетбыть представлен в видеAcorr =LqXci Ri ⊗ C ∗i=1Теорема доказана.Следствие 1. Пусть {A} - совокупность некорректных алгоритмов,{R} - соответствующее множество операторов, C ∗ - некотороефиксированное корректное решающее правило. Тогда L{A = R ⊗ C ∗ }является корректным относительно {Z} , если {Z} состоит из задач,полных относительно {R}.Сенько Олег Валентинович ()МОТП, лекция 925 / 30Алгебраическая коррекцияСледствие 2. Пусть выполнены все условия следствия 1. Тогда U{A}является корректным относительно {Z}, если {Z} состоит из задач,полных относительно замыкания U{A}.Линейные и алгебраические замыкания могут строится не только надконечными наборами заранее обученных алгоритмов, но также и надмножествами алгоритмов, принадлежащих некоторой модели иимеющих в общем случае мощность континуума.
Рассмотрим вкачестве примера рассмотрим один из вариантов модели алгоритмоввычисления оценок, в котором оценки за класс Kl вычисляются поформулеnX X XΓl (s∗ ) =(pj ωj )Bω (s∗ , sµ , ε)+(7)sµ ∈Kl ω∈Ω j=1+XnX X(pj ωj )B̄ω (s∗ , sµ , ε)e l ω∈Ω j=1sµ ∈S\KСенько Олег Валентинович ()МОТП, лекция 926 / 30Алгебраическая коррекцияВ формуле (7) используются следующие обозначенияB̄ω (s∗ , sµ , ε) = 1 − Bω (s∗ , sµ , ε) является функцией антиблизостиобъекта к эталону по опорному множеству, описываемомубинарным характеристическим вектором ω = (ω1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
