Лекция 9.1. Структура ошибки выпуклых комбинаций_ комитетные методы_ логическая коррекция (2015 Лекции (Сенько)), страница 2
Описание файла
Файл "Лекция 9.1. Структура ошибки выпуклых комбинаций_ комитетные методы_ логическая коррекция" внутри архива находится в папке "2015 Лекции (Сенько)". PDF-файл из архива "2015 Лекции (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
. . , 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 , . .
. , ωn );ε = (ε1 , . . . , εn )- вектор положительных пороговыхкоэффициентов, задающих близость объектов по каждому изпризнаков;(p1 , . . . , pn )-вектор положительных параметров, характеризующихважность признаков,(γ1 , . . . , γn ) вектор положительных параметров, характеризующихважность объектов.Сенько Олег Валентинович ()МОТП, лекция 927 / 30Алгебраическая коррекцияДля того, чтобы описать условия существования корректногоалгоритма в алгебраическом замыкании подмножества алгоритмовfвычисления оценок введём дополнительные определения.
Пусть Mнекоторое множество допустимых объектов.Определение 5. Объекты su и sν с описаниями (xu1 , . . . , xun ) иf,(xν1 , . . . , xνn ) называются изоморфными относительно множества Mfесли для произвольного объекта s с описанием (a1 , . . . , an ) ∈ Mвыполняются равенство(| xu1 − a1 |, .