Лекция 9 (1185274), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Обозначим через U{R} замыкание множества{R} относительно операций (1)-(3) - алгебраическое замыкание.Рассмотрим условия, существования корректного алгоритма длянекоторой задачи Z ( I , Sq , P1,, PL ) .Алгебраическая коррекцияОпределение 2. Если множество матриц {R( I , Sq )} (операторы Rпробегают множество R ) содержит базис в пространствечисловых матриц размерности L  q , то задача Z ( I , Sq , P1,, PL )называется полной относительно R .Определение 3. Решающее правило C называется корректным ,если для всякой выборки длины q существует хотя бы одначисловая матрица ||  ij ||Lq такая, что C (||  ij ||Lq ) || ij ||LqАлгебраическая коррекцияПусть { A} - множество алгоритмов видаA  R  C * , где R {R}C * - некоторое корректное решающее правило.Определение Множества алгоритмов вида A  R  C*, где будутобозначаться L{ A} и U{ A} , если R L{R} и R U{R}соответственно.Теорема 1 Если множество {Z } состоит лишь из задач , полныхотносительно R , то линейное замыкание L{R  C *}, где C * некоторое корректное решающее правило, являетсякорректным относительно {Z }Алгебраическая коррекцияДоказательство.

При фиксированном q базис в пространствечисловых матриц размерности L  qM1 ,, M Lq . Тогда существуют числа c1 ,состоит из L  q матриц, cLqтакие,L*qчтоM   ci * M ii 1где M является матрицей, которая можетбыть переведена решающим правилом C * в информационнуюматрицу ||  lj ||Lq . Существование матрицы M следует изКорректности решающего правила C * .Алгебраическая коррекцияПредставление (4) возможно в силу того, что матрицы M1, , M Lqобразуют базис в пространстве числовых матриц размерностиL  q . В том случае, если матрицы M1,, M Lq построены из {I , Sq }с помощью операторов R1, , RLq из R , коректныйалгоритм можетL*q*A(cR)CiiБыть представлен в виде. Теорема доказана.i 1Алгебраическая коррекцияСледствие 1.

Пусть{ A} - совокупность некорректных алгоритмов,*Cсоответствующеемножествооператоров,- некотороеRфиксированное корректное решающее правило. ТогдаL{ A}  L{R  C*} является корректным относительно {Z } , если{Z } состоит из задач, полных относительно R .Алгебраическая коррекцияСледствие 2. Пусть выполнены все условия следствия 1 и,кроме того, [R ] есть замыканиеR относительноопераций (1) – (3). Тогда U{ A}  {U{R}  C*} являетсякорректным относительно {Z } , если {Z }состоит из задач,полных относительно [R ]Алгебраическая коррекцияЛинейные и алгебраические замыкания могут строится не тольконад конечными наборами заранее обученных алгоритмов, нотакже и над множествами алгоритмов, принадлежащихнекоторой модели и имеющих в общем случае мощностьконтинуума.

Рассмотрим в качестве примера рассмотримодин из вариантов модели алгоритмов вычисления оценок,в котором оценки за классы вычисляются по формулеi ( s* ) n*(p)B(s  j j ω , s , ε ) s Ki ωj 1n*(5)(p)B(s,s,ε) j j ω s Ki ωj 1Алгебраическая коррекцияЗдесьBω (s* , s , ε)  1  Bω ( s* , s , ε)является функцией*sантиблизости объектак эталону s по опорному множеству,описываемому бинарным характеристическим векторомω  (1,,n ) , ε  (1,,  n ) - вектор положительных пороговыхкоэффициентов, задающих близость объектов по каждому из( p1, , pn ) признаков,вектор положительных параметров,характеризующих важность признаков,( 1,, n ) вектор положительных параметров, характеризующих важностьпризнаковАлгебраическая коррекцияДля того, чтобы описать условия существования корректногоалгоритма в алгебраическом замыкании подмножества алго-ритмов вычисления оценок введём дополнительные определения.

Пусть M - некоторое множество допустимых объектов.Определение Объекты sv и su с описаниями ( x1u ,( x1v ,, xnu ) и, xnv ) называются изоморфными относительно множестваM , если  s  M с описанием (a1 ,, an ) выполняютсяравенство(| x1u  a1 |,,| xnu  an |)  (| x1v  a1 |,,| xnv  an |)Алгебраическая коррекцияНетрудно видеть что корректный алгоритм в рамках моделиВычисления оценок не может существовать для задачиZ ( I , Sq , P1,, PL ) случаях, когдаа) в выборке S q существует два объекта s и , изоморфныхотносительно выборки эталонов S m , которая вместе со своейинформационной матрицей образует начальную информациюI ;б) объекты s и s принадлежат двум непересекающимся классам.Алгебраическая коррекцияДействительно в этом случае векторы оценок (1 (s),и (1 (s),, l ( s)), l ( s)) , вычисляемые произвольным операторомиз модели АВО будут одинаковы. Следовательно никакоемножество операторов модели АВО не может вычислять базисв пространстве вещественных матриц размера L  q .Будем называть задачу Z ( I , Sq , P1,, PL ) регулярной, еслиа)никакие два класса полностью не совпадают, т.е.

Kl  Kl приl  l ;Алгебраическая коррекцияб) никакие два объекта из S q не являются изоморфнымиотносительно выборки эталонов S m , где I  {Sm ,|| lj ||Lq } ;в)Sq  Sm   .Справедлива теорема.Теорема 2. Алгебраическое замыкание подкласса алгоритмовмодели АВО, в которой оценки за классы вычисляются поформуле (5) корректно над множеством регулярных задач..

Характеристики

Список файлов лекций