Лекция 9. Структура ошибки выпуклых комбинаций_ комитетные методы_ логическая коррекция (2014 Лекции (Сенько)), страница 2

То естьβlij 0 = βlij 00 при j = 1, . . . , r.В случае, если задана какая-либо функция g, а множество векторов{(βli1 , . . . , βlir ) | i = 1, . . . , r}включает всё множество вершин единичного куба Er , логическаяфункция Fl оказывается полностью определённой. В противномслучае задача построения логического корректора включает в себязадачу доопределения логической функции естественным путёмзаданной на выборке Sec на весь единичный куб Er .Сенько Олег Валентинович ()МОТП, лекция 915 / 24Логическая коррекцияОдним из способов логической корреции является построениемонотонных корректоров, которое сводится к поиску такой функции 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 / 24Логическая коррекцияПостроение монотонных корректоров сводится к следующей схеме. Висходном наборе A1 , . . . , Ar для каждого класса Kl выбираетсяподнабор Af (1) , . .

. , Af (k) . Объект s относится монотоннымлогическим корректором в класс Kl в том и только в том случае, еслион отнесён в Kl всеми алгоритмами из Af (1) , . . . , Af (k) и ещё однималгоритмом из набора A1 , . . . , Ar , который не принадлежитAf (1) , . . . , Af (k) .Сенько Олег Валентинович ()МОТП, лекция 917 / 24Алгебраическая коррекцияУниверсальным способом построения оптимального распознающегоалгоритма по набору исходных алгоритмов 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 / 24Алгебраическая коррекцияПоследнюю задачу мы будем называть задачей 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 / 24Алгебраическая коррекцияСовокупность {A} состоит из вообще говоря некорректныхалгоритмов. Алгебраический подход к решению задач распознаваниявключает в себя введение алгебраических операций над алгоритмамииз {A} , позволяющих строить корректные алгоритмы по наборамалгоритмов из {A} .

Поскольку каждый распознающий алгоритмможет быть представлен как последовательное выполнениераспознающего оператора и решающего правила, множеству {A}соответствуют множества операторов {R} и множество решающихправил {C} . Каждый из операторов из множества {R} вычисляет длязадачи Z матрицу оценок за классыR∗ (I, Sec ) = kγli∗ kL×qНа множестве операторов {R} вводятся операции сложения,умножения и умножения на скаляр.Сенько Олег Валентинович ()МОТП, лекция 920 / 24Алгебраическая коррекцияПредположим, что 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 / 24Алгебраическая коррекцияИспользование операций (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 / 24Алгебраическая коррекция. Определение 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 / 24Алгебраическая коррекцияПусть 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 / 24Алгебраическая коррекцияВ том случае, если матрицы M1 , . . . , MLq построены из {I, Sec } спомощью операторов R1 , .

. . , RLq из {R} , корректный алгоритм Acorrможетбыть представлен в видеAcorr =LqXci Ri ⊗ C ∗i=1Теорема доказана.Сенько Олег Валентинович ()МОТП, лекция 925 / 24.