автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Иерархия корректных классов алгоритмов вычисления оценок

(И

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ПЕДАГОГИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ жжзяя В. П. ЛЕНИНА

Специализированный Совет К 053.01.16

п и 1\1

На правах рукописи

РИГЕР Татьяна Викторовна

ИЕРАРХИЯ КОРРЕКТНЫХ КЛАССОВ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ ОЦЕНОК

Специальность 05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание учепой степени кандидата физико-математических наук

Москва 1993

Работа выполнена в Московском педагогическом государственном университете им. В. И. Ленина.

Научные руководители:

доктор физико-математических наук, академик РАО, профессор МАТРОСОВ В. Л.,

кандидат физико-математических наук, профессор ЩЕГОЛЬКОВ Е. А.

Официальные оппоненты:

доктор физико-математических наук, ст. научный сотрудник РУДАКОВ К. В.,

кандидат физико-математических наук, научный сотрудник УГОЛЫШКОВА Б. 3.

Ведущая организация: Центральный научно-исследовательский институт экономики, информатики л систем управления (г. Москва).

Защита состоится « и. на заседании специализированного совета К 053.01.16 по защите диссертаций на соискание ученой степени кандидата физико-математических наук в Московском ордена Лешша и ордена Трудового Красного Знамени педагогическом государственном университете им. В. И. Лешша по адресу: 107140, Москва, Краснопрудная ул., д. 14, математический факультет МИГУ им. В. И. Л(шина^______----

С диссертацией можно ознакомиться в фундаментальной библиотеке МПГУ им. В. И. Ленина по адресу: 119882, Москва, Малая Пироговская ул., д. 1.

Автореферат разослап «..^/....»..К^г&^ш993 года.

Ученый се^етарь специализированного совета

Э. И. КУЗНЕЦОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. К числу наиболее актуальных проблем теории распознавания образов относится задача синтеза из алгоритмов мололи с помощью корректирующих операций оптимальных по точности распознавать алгоритмов.

Один из подходов к решению этой задачи связан с понятием "корректора по результатам". Суть подхода состоит в том, чтобы корректирующие операции выполнялись над информационными матрицами, вырабатываемыми алгоритмами модели.

В семидесятых: годах школой Журавлева Ю.И. начал активно разрабатываться иной подход, получивший название алгебраического. Он предусматривает введение так называемого пространства оценок, промежуточного по отношению к исходным описаниям и допустимым ответам (информационным матрицам). Алгоритм распознавания при этом рассматривается как суперпозиция двух алгоритмов. В частности, Всякий алгоритм вычисления оценок можно представить как последовательное выполнение двух алгоритмов: оператора вычисления оценок и решающего правила. Оператор строит для набора классифицируемых объектов числовую матрицу оценок, а решающее правило по полученной матрице оценок строит информационную матрицу. При таком представлении распознающего алгоритма корректирующие операции можно вводить'не над информационными матрицами, а на болев раннем этапа - над матрицами оценок. Тем самым возможности выбора корректирунцих операций значительней расширяются, а сами операции существенно обогащаются свойствами.

Много внимания в исследованиях школы Журавлева Ю.И. уделяется трем операциям: операциям сложения и умножения операторов и умножения оператора на число (им соответствуют операции покомпонентного сложения и умножения матриц оценок и умножения матрицы оценок на число). Рассматриваются линейные и алгебраические замыкания различных моделей алгоритмов относительно названных операций. Исследуется корректность этих замыканий и их подмножеств как над классом всех регулярных задач, так и над всевозможными его подклассами.

В работах Матросова В.Л. было доказано, что линейное аамыкание и алгебраическое замыкание второй степени семейства алгоритмов вычисления оценок некорректны над множеством всех регулярных задач.

Принципиальный характер имеет вопрос: будут ли обладать свойством корректности алгебраические замыкания степени К при К}3, т.е. подклассы из алгебраического замыкания, содержащие алгоритмические многочлены степени не выше К ?

Для практического применения имеет значение оценка степени алгебраического замыкания семейства алгоритмов, корректного для фиксированной задачи или некоторого класса задач.

В работах. Журавлева Ю.И. получена асимптотическая оценка степени К алгебраического замыкания семейства алгоритмов вычисления оценок, содержащего корректный' алгоритм для произвольной регулярной задачи: при <£—<*> К~ Сп$ ( £ - длина контрольной выборки задачи). Эта оценка улучшена сначала в исследованиях Матрооова В.Л.: К «<}, + £ -2, а затем Рудаковым К.В.: К = [ (сд2 <}Д ] ( С - число классов, по которым ведется распознавание; ^ - длина контрольной выборки).

Конкретные примеры показывают, что в отдельных случаях оценку К » I 1 можно понизить.

Наряду с оценкой степени корректного замыкания не меньшее практическое значение имеет разработка критериев корректности различных семейств алгоритмов для регулярных задач.

Эта проблема глубоко исследуется в работах Матросова В.Л., исследования продолжены Кукулиевым Б.М., Ивановой Е.А. и могут быть развиты дальше.

Цель работы. Целью настоящего исследования является:

1) Доказательство некорректности алгебраического замыкания степени К семейства алгоритмов вычисления оценок над классом всех регулярных задач для любого ЮЗ.

2) Оценка степени корректного алгебраического замыкания семейства алгоритмов вычисления оценок для произвольной регулярной задачи.

3) Получение условий корректности алгебраического замыкания степени К семейства алгоритмов вычисления оценок для

произвольно выбранной регулярной задачи.

Научная новизна. В основе диссертационной работы лежит теорема о сводимости, в которой построена "базисная" Совокупность матриц оценок, являющихся булевыми.

Использование "базисной" совокупности булевых матриц оценок позволяет получить следующие основные результаты:

1) Доказать некорректность алгебраического замыкания. степени К семейства алгоритмов вычисления оценок над классом всех регулярных задач (для любого натурального К > 3).

2) Доказать необходимые и достаточные условия корректности алгебраического замыкания "степени К семейства алгоритмов вычисления оценок для произвольной регулярной задачи, которые сводятся к исследованию совместности системы неравенств специального вида.

3) Доказать, что алгебраическое замыкание степени К семейства алгоритмов вычисления оценок корректно над классом всех регулярных задач, объем обучающей информации которых нэ превосходит К; причем К является минимальной корректной степенью для такого класса задач.

4) Уточнить оценки степени корректного замыкания семейства алгоритмов вычисления оценок для произвольно выбранной регулярной задачи.

Все эти результаты являются новыми и получены впервые автором дассертвции.

Методологическую основу работы составляют методы булевой алгебры, линейной алгебры, алгебраической теории распознавания.

Диссертация выполнена в соответствии с планом научно-исследовательской работы кафедры (номер государственной регистрации

0812702% 19).

Научная и практическая значимость работы.

Результаты, полученные в работе, имеют прежде всего теоретическое значение. Предложенная в работе методика исследования свойств алгебраических замыканий конечной степени семейства алгоритмов вычисления оценок с помощью булевых матриц может быть развита и применена в дальнейших исследованиях подобного рода.

Апробация работы. Материалы диссертации докладывались на научных семинарах математического факультета Московского педагогического государственного университета имени В.И.Ленина (1985-1993 гг.); на научно-технических конференциях Ульяновского политехнического института (1992-1993 гг.); на научно-техническом совещании "Логико-алгебраические

модели представления знаний в экономических, технических и организационных системах" (г.Ашхабад, 1983 г.); на I Всесоюзной конференции "Математические метода распознавания образов" (г.Дилижан, 1985 г.); на 17 Всесоюзной конференции "Математические методы распознавания образов" (г.Рига, 1989 г.) и опубликованы в семи печатных работах (их список приведен в конце автореферата).

Структура и объем диссертации. Работа состоит из введения, трех глав и списка использованной литературы. Она содержит 126 страниц основного текста, 59 наименований использованной литературы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ.

' Во введении дается краткий обзор литературы, посвященной математическим методам распознавания, обосновывается актуальность и ставится цель работы, а также кратко изложены основные результаты.

При дальнейшем изложении работы будем пользоваться следующими со,. крашениями. Символы V и К обозначают множества натуральных и действительных чисел соответственно; К+ = {эСбЖ|^->0}. Сокращения 0В0 и ABO обозначают "операторы вычисления оценок" и "алгоритмы вычисления оценок" соответственно.

Первая глава диссертации посвящена реализации идеи о сводимости бесконечного семейства ОБО к линейной оболочке некоторой конечной совокупности ОБО.

Теорема о сводимости дает метод для дальнейших исследований свойств полноты и корректности алгебраических замыканий конечной степени _семейств_0В0-И ABO соответственно.-

В §1.1 даны все основные определения, формулируется задача классификации со ставдарткой обучаидвй^информацией, охарактеризована параметрическая модель Ш ( £ , fí . Í , зс ) ABO с одним из вариантов флодии близости: В дальнейшем все результаты доказываются для подмодели 7Лг модели Til ABO, какдкй алгоритм которой имеет одноэлементную систему опорных множеств.

Рассматривается пространство допустимых объектов

такое, что сМ » О StV , где классы tfCT , / = 1,2, ... ,f

Ы i * á

имеот, вообще говоря, непустые пересечения. На каадом признаковом

множестве сЖ^ определена полуметрика , к = 1, 2, ... ,п . Тогда кавдой паре допустимых объектов 5 = ( А, , <*2 ,..., С1п ) и

£>' ( » ^г.....) из пространства сЖ можно поставить в

соответствие вектор

£<$.$')-< ( а£, а^), ( а2. а^),..., у>п < ап. а;)).

Иногда будем обозначать < > ) = & , $' )•

Рассмотрим задачу распознавания в следующем виде: задано стандартное описание начальной информации^ классах , ... , Ж( -1т ■ ( $т . <С ( $т )). где -($,,.... $т ) - Обучающая выборка допустимых объектов из пространства ;

$1 - ( «ч,, ... , <и„), <- = 1. 2, ... , ш ;

Л ( ) = II *1 - матрица размерности т * { с элементами из множества {0,1} , причем ¿ц = ( $^ ), где ¿¡^ - предикат принадлежности классу , т.е. для любого 5 6<Д

П, если 6 6 ЗГ; ; $ )«{ ■

^ 1о, если $ 4 . I -ую строку матрица оС ( ) будем обозначать </ ( ) и надавать истинным информационным вектором длины £ объекта . ^ Предъявляется так называемая рабочая (или контрольная) выборка

& = ( .....) объектов из пространства , для каждого

объекта ¡3* =» ( , ... , ) ( 4 » 1, 2, ... , ^ ) которой надо вычислить значения ^ ( ) предикатов принадлежности по классам ЗГу , j п 1, 2.....£ . ^

Задача распознавания = ЭГ ( 1т . 5 ) состоит в построении алгоритма А , корректного на паре ( 5г ), т.е. такого, что для любого 5*«

А ( 1т , ) = ( е£{{ , . .. , аСц ), где ¿Ц - с^- ( ), j = 1, 2, ... ,( .

В дальнейшем будем рассматривать только так называемые регулярные задачи.

Определим понятие регулярной задачи. Определение

Объекты и называются изоморфными относительно нвчальной

информации 1т » ( $т , Л ( £>т )), если для каждого объекта

6 • » 5т] выполнено равенство

^ ( , $1 ) < . )•

Наличие изоморфизма обозначают: ~ 1щ)> а его отсутствие: ~ ( ).

Пусть .....Зт} 0 ЭГ/ ,

.....$т}\ ХК} . / " 1. 2.....I .

Определение ^.2. ^ _

Задача % (1т , б* ) с начальной информацией 1т -ми и контрольной выборкой называется регулярной, если она удовлетворяет условиям: ^ Л

1) Для всех I , {е{1, 2.....1} , j / Ь , ;

2) Для всех V , 1Й6 (1. 2....., V ф 1Д> , = ^ (1т)

3) 1$,.....П .....$4} = 0 .

Совокупность всех регулярных задач обозначим через Ж. •

Перейдем к описанию модели алгоритмов вычисления оценок (обозначим ее 731 ). Кавдый алгоритм А вычисления оценок определяется как последовательное выполнение алгоритмов И и С , называемых соответственно оператором вычисления оценок и решающим правилом (записывают: А ■ Л • С ).

Оператор Ц вычисления оценок строит по начальной информации 1т для контрольной выборки матрицу оценок

И < 1т ; .....) = %ш(

где Г^- = Г^ ( $1 ) - оценка объекта по классу ЭРу . Решавдее правило С по маурице оценок строит для контрольной выборки __информационную матрицу:---

) « , рц б { о, 1, д} .

Считаем, что алгоритм А относит й1 к классу 'К} , если ^Ву = 1; не заносит $1 в класс , если ^^ = 0; отказывается от классификации объекта 5е по классу , если = Д .Таким образом, результатом применения алгоритма А к задаче Э£ ( Хт » ) является некоторая информационная матрица , что записы-

вают следующим образом:

А ( % ) * 11**1 или

А ( 1т . ) - 11^-11 /

будем называть истинной

Л}

Определение КЗ.

Информационную матрицу И.Ау 11^x4 для контрольной выборки , если для любых 1,1 {е{1, 2, .... , 3 6(1, 2,

Лц- ( & >.

Определение 1.4. _

Алгоритм А ^назовем корректкым для задачи ( , $ ^ ), воли А ( I т , Ъ * ) я И Р1) II ^ х { - истшшая информационная матрица для выборки . ✓

Определение ]_.5.

Решающее правило С называется корректным, если для всякой выборки существует числовая матрица II Гу |Ц*с такая, что С переводит НГ^ (),«(, _ в истинную информационную

для выборки ( 5>

матрицу

Всякий оператор К вычисления оценок однозначно определяется параметрами £ , у , 6 , эс. и системой {Лд} так называемых

опорных множеств, где ЛАс 2, ... , П} ,{1,2,____ П) -

множество признаков. Система {Лд} может быть самой различной. В частности , она может состоять из одного подмножества

. ( 11.....¡-к) 5 (1.2.....п} .

Всякому Я. = { {£ булевый вектор го = ( 1, если

-

О, если

¿к} взаимно однозначно соответствует

) такой, что

I б нг,

¿к)

Если 5 - (

< ч 9 • • • • <4

г - 1 14 .

т - ( тх , ...

1 ш ( ^ , ...

Л» ЭС. - ( X,, х<

Рп К" Гт

£«>6 т1; 6 ({0,1} )

I 6 {£,2 . \ { ¿1.....¿„}.

а„ ), то через й>£ обозначается вектор аемый - частью объекта 5 .

- набор весов признаков;

- набор весов объектов обучающей выборки;

- набор порогов близости по каждому признаку;

- набор параметров, учитывающих "близость" своих и "удаленность" чужих объектов по каждому классу. '

Г

X

Оценка Гун объектй по классу 'ЗСц может быть вцчисле-

на по формуле:

г„к = ос£Гг£к + эс0 Гуц (V = 1,2..... % ; и " 1.2,..., I ),

ГД9 £ ~ ~ л ~ л9 ~

= ^ ^ («О ) в ( -и) , , £ ),

ГУЦ» -jr.fi {-и) ) & ( гй $1 , Ю$ ,6 ).

^ й€{йл} П

Здесь -¡г ( и> ) - р. • гЬ = В ( -и> ¿с . йй' . ? ) - функция близости. Всюду в дальнейшем будем использовать следующий вариант функции близости: при

£ = ( £>£,..., Ь ^ ~ [ .....

(1, если л ( {»¿, .....$*><£».»

Ь СЙ^.Л^. £ ) = ]

[о, в противном случае. Полагаем ~ <г "

В ( го $1 , Ю Ь ) = 1- Ь ( гб^г . ^ $ . £ >■ Обозначим: В = ЬГ , Ь = В° .

Тогда оцонку Т»гц можно записать так: ^

Г*ц - Ж эс^ 2 ^ 2 I1 ( Л ) Е»А ( го , и) , & ).

•¿ = 0,1 йс{й>А}^

Итак,полностью описан подкласс 131} распознающих операторов вычисления оценок. Если зафиксировать корректное рекащое правило С , то

подклассу {Л)_будет соответствовать .подкласс—{ А I А = Е'С }-

распознающие алгоритмов вычисления оценок.

Вводом на множество операторов {К} операции слоасошя, умножения и умнояазння оператора на скаляр. Пусть % ( Хт . ) - произвольная задача, ^ е Е , р, , В' б {&} ,

И <2 ) " ЯГгцИ*,* . ) - НГ;и11^£

Тогда

(Я + Н' )( Ж ) = (1 1\ги 4 (1-1)

( Б - И' НХ ) - !! гуц • КийVI <1-2>

( Л ' Ж )( ЭЕ ) - || ^ • Г,гц II Зшяшшие {р,}. миохеста {'Н} относительно опорацкя (*.') я (1.3)

является векторным пространством, а замыкание "И {й{ множества (в! относительно операций (1.1) - (1.3) является ассоциативной линейной алгеброй с коммутативным умножением.

Операторы из [В ] могут быть представлены в виде многочленов от операторов из {В} :

%{Н] ={2 ... | ;

« ; 16 V]. •

Степенью операторного многочлена В,-,

называется максимальное число операторов-сомножителей в слагаемых

Определение 1-6. ■ ■ • .

Множества ¡С {А} , И\к] алгоритмов А = И; С соотвё-тственно таких, что Л £ {Й} , В в И {5} , называются-соответственно линейным и алгебраическим замыканиями множества ' •

{А I А = 5 • С} .

Определение и?.

Множество всех операторных многочленов алгебраического замыкания , степень которых не превосходит числа К (К> 1, КбЛЛ ), называется алгебраическим замыканием степени К семейства {Е} операторов вычисления оценок и обозначается . ^"{й} .

■ Множество алгоритмов ^ ' .

Як{А} -{ А | А -Л-С , в б-гсК Ш)- - ,

где С - некоторое фиксированное корректное решанцве^правило, называется алгебраическим замыканием степени К семейства {А} алгоритмов вычисления оценок. ,

Согласно определению,

Полезно рассмотреть другое множество операторов:

Ясно, что = х ( {Й} )•

Всюду в дальнейшем будем рассматривать подкласс <$2с {к] операторов вычисления оценок, каждый оператор которого определяется системой опоргшх множеств, состоящей из одного опорного множества { {£ , ... ,1К} £ {1, 2, ... п} , причем но фиксировашюго, а ■произвольного. Выбор такого семейства обусловлен тем, что, как пока-

И* {к) с ( в каким бн

зал Матросов В.Л.,

для любого натурального К ни было семейство {!*}'&'(я) Определение _1.8.

Операторы "И и К.' назовем равносильными относительно задачи 3 ( - равносильными), если

) =

Б яЦ'.

- ИГ'уи - к ( а )•

В ( а

. Обозначим:

Определение _1.9. ,

Семейство операторов %К сводимо к семейству операторов <Я относительно задачи % (• Й - сводимо), если для всякого оператора Н £ ¿Я существует % - равносильный оператор В' 6 • Обозначим: Ж'.

Центральное место в главе I занимает теорема 1.1 (теорема о сводимости), доказанная в §1.2.

. Теорема _1И (теорема о сводимости). ^ ■

' Для всякой-регулярной задачи % ( Хт , 5* ) существует конечное множество <$г с ¿Я2 "базисных" операторов, такое, что

4 ), причем

§, дальнейших рассуждениях-удобнее иметь дело о системой операторов г {Но;.В^| у-1.2.....* (I ); < - 1,2,...,тп) с

Поясним, что это за система. Зафиксируем объект {>; € $ т .

¡■> на классы У/.....

Разобьем контрольную выборку

по свойству: два объекта , б попадают в один и тот ке

класс У/ тогда и только тогда, когда _/> ( . ¿* ) » ( ¿1 _, ).

Пусть {V,1 .....Уг(0}.....{V,"" } - последо-

вательность всех )п разбиений объектов контрольной выборки 5 * . Сопоставим ей последовательность классов характеристических векторов

множеств У^

1(Г/

ч

АН)

4 & } •

{ 1. 2, .. ...

г а

v а

«а

) , ¿е{1, 2,

. , где

'1, если

VI

I - 1. 2, ..

Обозначим Б

{¿л

( >1

10, если 1. 2.....

т

, т]

¡4 Г/ .

; д - о.|} -

в

совокупность информационных векторов об ( £¡, ) = ( ) объектов обучающей выборки и векторов «¿°($i ) » (1, ... JJ- «Z£(£j);

{«« .....¿¿(i)}. ' г

Как следует из теоремы 1.1, оператор В(д ■ 0,1; t 1,2,..., m ; У »1,2.....й ( i )) порождает булевую матрицу оценок

В il <« ) ,

в которой^элемент Ijt ■ 1 тогдв и "только тогда, когда координата -î> вектора -tfy1 равна 1 и координата t вектора Л* (Si-. ) равна 1

( 4 = 1,2..... £ ; t » 1,2..... i ).

Таким образом, всякая матрица H^i ( 3£ ) может быть однозначно описана парой булевых векторов jV и '( Si )• • Обозначим: ( S ) = D ( , «2> ( ) ). •, . ' Тогда ' • •

- [Bai (5É )l Д - 0,i;y « 1,2,..., I (i )•, i -1,2,

= {D (V/ , ¿> (Si ))| д - 0,1; y =■ 1,2.....t ( i ): « » '.2.....m} -

совокупность всех булевых матриц оценок, порождаемых операторами се-' мейства •

Из теоремы 1.1 вытекает, что любая другая матрица оценок, порождаемая произвольным оператором I 6 Лг , примененным к задаче •, ■ является линейной комбинацией булевьи матриц оценок совокупности £>(%). ■ Поэтому в дальнейшем- S>( Qi ) будем называть "базисной"- совокупностью.

Справедлива твкже 3? - сводимость:

Я"(<#а> Я?».

(<Й 2 ) и ( $ * ) порождают соответственно множества матриц оценок U* ( 3 { 5Î )) и J ( S> ( >), связанные соотношением: Г(9 ( % ))*•*£( UÎ {Я (Я )))• fi*( 5) (Si )) можно.охарактеризовать так:

«"( а )) = {D û/;« . (¿t, )•

«ZAt($tt)ea , ££ е t - 1,2,...,к}.

Пусть

S5 ( 2 )> - { ^...... 3>t и » ^¿i 11Ы '

■ t = 1,2,...., l ( к ). . . -( S£ ) = Ifj5{j II - истишш информационная матрица контроль-

ной выборки регулярной задачи %

• С ( f ) - фиксированное корректное решающее правило, где

- <4 - ( <Ч(1).....-<li(t ». i - 1,2.

О < c{( j ) < c2 ( j ), j = 1,2.....I .

Согласно решающему правилу,

$legCj , если Tij > C2( i ); PlVtj . если Tij < c£ <¿ );

не классифицируется алгоритмом, если £f ( j ) < Гд- < Сг( ¿ ). Следствие 2. (Критерий корректности).

Лусть % ( I,, , 5* ) - произвольная регулярная задача с истинной информационной матрицей контрольной выборки (г* -ja ( Й ) = l|jb¡j ||о,,( - и "базисной" совокупностью матриц оценок

< se )) -{i>t = «¿у li i í - i.2..... 5 ( к )}•

Для того чтобы алгебраическое замыкание К-ой-степени аИк (Лt) семейства оИ2 алгоритмов вычисления оценок с фиксированным решающим^ правилом С ( c¡, ct) было корректно для регулярной задачи "М необходимо и достаточно, чтобы система q, t неравенств (относительно переменных зс£.....^¿00 ■ • •

(-n^gx^ 4 <-1)^dí+Jiij(¿)

.( t = 1,2.....; j ¿ 1,2, ... , t )

была совместной. •

Особенность этой системы в том, что коэффициенты при переменных ( I = 1,2, ... , 5 ( к )) в каждом ее неравенстве либо 0 и 1, либо О И -1.

Аналогично доказывается критерий корректности для других разно_видностей_решащих_правил_____________

Глава 2 посвящена доказательству некорректности алгебраического замыкания К-ой степени семейства- ABO над классом всех регулярных задач для К > 3.

Методом математической индукции по степени К замыкания доказывается, что для замыкания любой степени можно построить задачу, не решаемую корректно в этом замыкании. Бри доказательстве' некорректности применяется критерий, полученный в глава 1 (следствие 2 теоремы 1.1).

Обозначим через 2Г ( (J, ) - подкласс всех таких регулярных за-да^, у которых длина контрольной выборки фиксирована и равна cj, .

Теорема 2.U

Алгебраическое замыкание 1/s( Лц ) некорректно над множеством регулярных задач Z (24).

Теорема 2.2. (Основная теорема).

Алгебраическое замыкание iín ( Л2) некорректно над множеством регулярных задач 2Z (2П 4-1) для любого П > 3.

Глава 3 посвящена выяснению условий корректности алгебраических замыканий конечной степени семейства А г. ABO для регулярных задач с неизвестной информационной матрицей контрольной выборки, а также уточнению степени корректного замыкания для регулярных задач.

Определение 3.|. _ . • . ' .

Регулярная задача ( , ) является полной относительно семейства Л операторов вычислешм оценок, если совокупность всех -матриц оценок, порождаемых операторами из 31 , примененными к данной _ задаче % (Im ), содержит базис в пространстве матриц денной

размерности. В противном случае задача % ( Im , $1 ) неполна отнб-сителыю Si .

Журавлевым Ю.И. было доказано, что если задача полна относительно какой-либо совокупности операторов вычисления оценок, то соответствую- . щее семейство алгоритмов вычисления оценок с фиксированным корректным .' решающим правилом корректно для этой задачи.

В §2 главы i были определены множества йи Т соответственно L - мерных и ч - мерных булевых векторов, о помощью которых для задачи 2f ( Im , ¿i ) строится "базисная" совокупность булевых матриц оценок. ,

Пусть

V?* ) - [íti •...•üt|ül.é V ; / - i,2.....I : UK} ,

114 ( G ) - Ui,e.-.».¿;t ¡2fj€ G '> j B 1'2.....t ÜU} ,

В §1 главы 3 доказаны теоремы:

Теорема 3.2. _ , • •

Пусть % ( I m , § Ч" ) - произвольная регулярная задача с соответствующими ей множествами векторов &J и . Если не содержит базиса С - мерного векторного пространства или не содержит базиса (j - мерного векторного пространства, то регулярная звдача % о указанными G* и Ф* неполна в алгебраическом замыкании ( ) степени К семейства 5te 0В0.

H

Теорема 3.4.

Если произвольная регулярная задача % ( Im , è ^) такова, что определяемые ею множества G * и Vtn содержат базисы соответственно I - мерного и - мерного векторных пространств, то она полна в алгебраическом 'замыкании Цк*п ) семейства ОЮ (К>1, ni 1).

' Следствие. •

Если множества^ Gtt и V~{ , определяемые произвольной регулярной задачей 2 (Im , ). содержат базисы соответственно I - мерного и £ - мерного векторных пространств, то алгебраическое замыкание степени ( к + п ) семейства ABO корректно для данной задачи ( К > 1, lié 1).

В §2 главы 3 рассматриваются теоремы, дающие оценки степени корректных алгебраических замыканий семейства S¿ для фиксированных регулярных задач с неизвестными информационными матрицами.

Теорема 3.5.

Всякая регулярная задача ( Im , {> ^ ) с начальной информацией ( & т)) полна в алгебраическом замыкании <Um( ¿fie ) степени m семейства ОБО.

Следствие.

Алгебраическое замыкание И ( ) степени m семейства алгоритмов вычисления оценок корректно для всякой регулярной задачи с длиной обучающей выборки, не превосходящей числа m .

В главе 2 были построены примеры регулярных задач с длиной m обучающей выборки, для которых алгебраическое замыкание степени (m-í)

семейства оАг abo не является корректным. Этот факт в совокупности_

со следствием из теоремы 3.5 позволяет утверждать, что минимальная степень алгебраического замыкания семейства , корректного да класса всех регулярных задач с длиной обучающей выборки, не превосходящей m ,. равна m .

Таким образом, можно считать, что построена бесконечная последовательность подклассов класса регулярных задач:

^t с <= ... с 2Z. п с. ... такая, что Цп ( ) корректно для класса регулярных аада'ч Жп , но некорректно для Zn+[ , где Жп - подкласс всех регулярных задач с длиной обучающей выборки, не превосходящей П .

Теорема 3.6.

Пусть % ( Im , S* ) - произвольная регулярная задача с соответствующей ей "базисной" совокупностью 3> ( % ). Если t - максимальное число линейно-независимых матриц множества §£> ( % ), то алгебраическое замыкание + П

семейства dt АВО корректно для данной задачи % ( Im , ô^ ), дли-' ны обучающей и контрольной выборок 'которой равны соответственно гп и ^ , а число классов равно I .

§3 главы 3 посвящен выяснению условий корректности алгебраических замыканий конечной степени семейства для неполных регулярных задач. • ■ ' .

Зафиксируем следующее корректное решающее правило С, ( Cf , ),

где ^ = ( ^ (1)..... CL ( t )), i = 1.2, -

О < Ct(j ) « Ct(j ), / = 1.2.....I :

если Гд < i ). то i Щ ; если fy > it(J ), ю i4 6 ; . если c{ ( j ) 4 f^;' 4 Сг( j ), то {>* не классифщируется алгоритмом.

Теорема 3.7.

Пусть - истинная информационная матрица произвольно

выбранной регулярной задачи % (1т , ),неполной в" алгебраическом замыкании 11к ( Лй ). Ест матрица \\Лц II линейно-выражается через матрицы оценок совокупности "Ц^ ( 2) ( % )), то задача % решается корректно в алгебраическом замыкании И к ( Лг ) семейства Jlt АВО.

§3 главы 3 содержит также критерий некорректности, в котором выясняется, при каких услових неполная задача не может быть решена корректно алгоритмами замыкания 1ЛК Критерий некорректности.

Пусть % il^TW) - произвольная регулярная задача, неполная относительно ^ 11к ( ¿Я 2 ), о истинной информационной Матрицей контрольной выборки - IXij 9 <j,»( - и соответствующей задаче совокупностью булевых матриц оценок _ fi*( 2> ( )) » {Dt|Dt = lMÎj 1Ц*£, t = 1,2..... 4 (К )} .

Алгебраическое замыкание Ик (Л2 ) степени К семейства *AZ АВО некорректно для задачи ( Im , S^ ) югдв и только тогда, когда

найдется ненулевая матрица , удовлетворяющая условиям:

а) для любогоЬ 4 £ {1,2, ... ,¿(к)}

я

.¿(к)}

в) длл любых I ,] С £ {1,2.....ч] , {1,2.....{}

в) длл любых I I 6 {1

Ац 4 О, если, ¿ц " 1;

Яц 5> О, если «¿и - 0.

Основное содержание диссертации отражено в работах:

1. Плохонина Т.В. О некорректности алгебраического замыкания Дп{й1!) алгоритмов вычисления оценок над множеством регулярных задач

Тезисы докладов научно-технического совецаниа "Логико-алгебраические модели представления знаний в экономических, технических и организационных системах". Ашхабад, 1933, с.17-18.

2. Плохонина Т.В. О некорректности алгебраического замыкания а -й степени семейства алгоритмов вычисления оценок. Ж.вычисл.матем. и ма-тем.физ., 1985, т.25, N27, с.1078-1085.

3. Плохонина Т.В. Вопросы корректности алгебраических замыканий конечной степени семейства алгоритмов вычисления оценок. Тезисы докладов Всесоюзной конференции "Математические методы распознавания ■образов". Дилижан, 1985, с.151-153.

4. Плохонина Т.В. Вопросы корректности алгебраических замыканий конечной степени семейства алгоритмов вычисления оценок для регулярных задач. Ж.вичисл.матем., и матем.физ., 1987, т.27, №6, с.763-770.

5. Ригер-Плохонина Т.В. Оценка степени корректных алгебраических— "замыканий семейства Л2 алгорйтмов вычислени оценок для регулярных задач. IV Всесоюзная конференция "Математические методы распознавания образов". Тезисы докладов. Рига, 1989, ч.2, с.126-128.

6. Ригер Т.В. Корректность алгоритмов вычисления оценок. Тезисы докладов XXVI научно-технической конференции. Ульяновск: УлПИ, 1992, с.73-74.

7. Ригер Т.В. Условия корректности алгебраических замыканий конечной стей<ш семейства «Л 2 алгоритмов вычисления оценок для неполных'регулярных задач. Тезисы докладов XXVII научно-технической конфег ренции: УлПИ, 1993, с.76-77.

/Работы 1-4 напечатаны под девичьей фамилией*. Плохонина Т.В./