Алгебраические замыкания обобщённой модели алгоритмов распознавания, основанных на вычислении оценок тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

ии^"■_

ДЬЯКОНОВ Александр Геннадьевич

Алгебраические замыкания обобщённой модели алгоритмов распознавания, основанных на вычислении оценок

Специальность.

01.01 09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва-2009

003476616

Работа выполнена на кафедре математических методов прогнозирования

факультета вычислительной математики и кибернетики Московского государственного университета имени М В Ломоносова

Научный консультант: академик РАН, доктор физико-

математических наук, профессор Журавлев Юрий Иванович.

Официальные

оппоненты: академик РАН, доктор физико-

математических наук, профессор Матросов Виктор Леонидович,

доктор технических наук, профессор Немирко Анатолий Павлович,

доктор физико-математических наук Устинин Михаил Николаевич.

Ведущая организация: Московский физико-технический институт

(государственный университет).

Защита диссертации состоится «2.Э » оу-тл^а 2009 г в _Иг7часов на заседании диссертационного совета Д 002.017 0 в Учреждении Российской академии наук Вычислительный цент им. А.А Дородницына РАН по адресу

119333, г. Москва, ул Вавилова, д 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан « ¿> » сектора. 2009 г.

Учёный секретарь диссертационного

совета Д 002.017.02, д.ф.-м.н., профессор в-в- Рязано

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

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

В конце 1970х годов ЮИ Журавлёвым был предложен алгебраический подход к решению задач распознавания, корректный алгоритм (который не делает ошибок на контрольный выборке) было предложено искать в виде алгебраического выражения над некорректными (эвристическими) алгоритмами. Над распознающими операторами были введены операции сложения, умножения на константу и умножения как операции над матрицами оценок, которые они получают (умножение проводилось поэлементно). При фиксированном решающем правиле эти операции индуцировали операции над алгоритмами распознавания Множество всех полиномов степени не выше к над алгоритмами некоторой модели было названо алгебраическим замыканием к-й степени этой модели (при к-\ -линейным замыканием) Для модели кусочно-линейных решающих поверхностей и ABO было доказано, что существует и в явном виде выписывается корректный алгоритм-полином над некорректными алгоритмами Основное достижение алгебраического подхода - строгое доказательство «чисто алгебраическими» методами того, что в теории распознавания возможно построение «хороших» алгоритмов

на базе «плохих» Позже в рамках алгебраического подхода К.В. Рудакову удалось создать язык для описания и исследования задач преобразования информации - теорию локальных и универсальных ограничений.

Исследования модели ABO, в основном, были сконцентрированы на оптимизации алгоритмов и алгебраических выражений над ними. Строились корректные алгоритмы из алгебраических замыканий, но не изучалось множество всех алгоритмов, т.е упускался важный объект исследования, алгебраические замыкания До настоящего времени они не были даже достаточно детально описаны, чтобы анализировать, есть ли в них «хорошие» алгоритмы, как их синтезировать и т.д. Технику анализа алгебраических конструкций в рамках классической теории удалось построить В JI Матросову для решения фундаментальной задачи о теоретическом обосновании надежности алгоритмических построений алгебраическом подходе. С ее помощью удалось решить нескольк важных проблем, связанных с корректностью алгебраических замы каний (возможностью получить операторами замыкания произволь ную матрицу оценок в рассматриваемой задаче распознавания) Эт результаты поставили, в определенном смысле, более сложны проблемы нахождения «наглядных» критериев корректности, полу чения пониженных оценок степени корректного алгебраическог замыкания, описания всех задач, разрешимых алгоритмами и алгебраического замыкания конечной степени

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

Цель работы — разработка теории, позволяющей детальн описать и исследовать алгебраические замыкания модели алгоритмо распознавания, основанных на вычислении оценок, в том числе дл

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

На защиту выносятся следующие результаты, полученные для введенной в работе обобщенной модели ABO (справедливые и для классической модели):

1. Предложена теория систем эквивалептностей для описания и исследования алгебраических замыканий конечных степеней. Каждой задаче распознавания сопостовляется система экви-валентностей, по которой строятся характеристическая матрица и матрица попарных -расстояний, в терминах которых описываются алгебраические замыкания модели. Переходу к алгебраическому замыканию фиксированной степени при этом соответствуют специальные преобразования матриц

2. Получены новые критерии корректности алгебраического замыкания конечной степени и критерии разрешимости задач алгоритмами из этого замыкания. Критерии позволяют описывать разделяющие поверхности алгоритмов алгебраических замыканий в пространстве контрольных объектов Найдены новые семейства корректных полиномов

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

4. Исследовано пополнение линейного замыкания множества полиномов ограниченной степени над ABO операциями нормировки и деления. Нормировка рассмотрена при различных способах ее определения: по сумме, максимуму, отрезку. Получены формулы

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

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

6. Исследована k-сингулярность конечной системы точек {неполнота размерности пространства значений полиномов ограниченной степени над столбцами матрицы попарных /г расстояний этой системы). Полностью описаны все ¿-сингулярные системы. Найдены новые критерии вырожденности матрицы попарных /i-расстояний конечной системы точек

Научная новизна. Все результаты (1)-(6) являются новыми. Теория (1) является обобщением техник К.В Рудакова и В Л. Матро сова В диссертации впервые получены метрические критери корректности и разрешимости (2), которые, в отличие от критерие В JI. Матросова (1981 г), допускают простую геометрическую интер претацию в терминах исходной задачи Впервые (более чем за 20 ле с момента постановки) полностью решена проблема описания все задач, для которых некорректно алгебраическое замыкание фиксиро ванной степени. Примеры таких задач (без описания всего мно жества) были найдены B.JI. Матросовым (1981 г) и Т.В Плохонино (1985 г.) Результаты (1)-(2) позволили продемонстрировать связ алгебраических замыканий ABO с некоторыми современными моде

ями (SVM, линейной регрессией и тд.). Впервые доказано, что тассические полиномы Ю И Журавлева образуют базис в тебраическом замыкании конечной степени Оценки степени орректного алгебраического замыкания были получены многими торами (Ю.И. Журавлёвым - 1977 г., В JI Матросовым - 1985 г, .Н. Плохониной - 1987 г). К.В. Рудаков получил неулучшаемую ценку для одной модели, содержащей все алгоритмы ABO (1989 г ) диссертации впервые (более чем за 25 лет исследований) получена еулучшаемая оценка для модели ABO, зависящая от числа классов и лины контрольной выборки (3). Операции нормировки и деления (4) о настоящего времени не исследовались Впервые найдены (естественные» операции, которые значительно упрощают критерии орректности, не делая их вырожденными Исследования коррект-ости относительно семейства решающих правил (5) ранее не роводились. Впервые обосновано понятие «корректность модели» и ыделен класс задач, в которых необходимо использовать еклассические понятия корректности Постановка задачи о к-ингулярности (6) является обобщением проблемы теории нтерполяции о критерии вырожденности матрицы попарных /г асстояний Проблема вытекает из серии работ И. Шёнберга IJ Schoenberg, 1937 - 1938 гг ), но впервые решена только в 1993 г Рейдом (L Reid) и 3. Саном (X Sun). В диссертации не только олучены новые критерии, но и решены смежные задачи, связанные с риложениями в алгебраическом подходе к распознаванию

В работе впервые рассмотрено обобщение модели ABO на -лучай произвольного способа задания объектов, впервые исследова-а модель с обобщением Ю И. Журавлёва и А.А. Докукина (связан-ым с учётом удаленности классифицируемого объекта от объектов ассматриваемого класса и близости к объектам других классов)

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

Практическая ценность. Работа носит теоретический характер. Для иллюстрации возможных практических применений в третьей части приложения описаны прикладные задачи, при решении которых использовались результаты диссертации Разработанный автором алгоритм классификации сигналов занял первое место (из 20) на Международном соревновании «Ford Classification Challenge» в рамках конгресса «World Congress on Computational Intelligence» (WCCI 2008, Hong Kong, China), показав результат 100% верных ответов

Апробация работы. Основные результаты работы и отдельные ее части докладывались на научном семинаре кафедры математических методов прогнозирования факультета ВМК МГУ (2009 г ); научном семинаре «Алгебрологические методы в задачах классификации и прогнозирования» (МГУ, ВМК, 1999 - 2000, 2003 - 2009 гг.); научном семинаре «Дискретный анализ» (МГУ, ВМК, 2003 г.); научном семинаре «Дискретная математика и математическая кибернетика» (МГУ, ВМК, 2008 г ); Ломоносовских чтениях (МГУ, ВМК, 2008 - 2009 г.); Международных научных конференциях «Интеллектуализация обработки информации - 2000, 2006, 2008» (Симферополь, Крымский НЦ HAH Украины, ТНУ) [11], [15], [19]; 7-й и 8-й Международных конференциях «Дискретные модели в теории управляющих систем» (Москва, 2006, 2009 гг.) [13]; 15-Г Международной конференции «Проблемы теоретической кибернети ки» (Казань, 2008 г.) [18]; 19-й Крымской осенней математическоГ школе-симпозиуме KROMSH (Украина, Крым, Ласпи-Батилиман 2008 г.), 12-й и 13-й Всероссийских конференциях «Математически методы распознавания образов» (Москва, 2005, 2007 гг.) [12], [17].

Материалы работы легли в основу обязательного кафедрального курса «Алгоритмы, модели, алгебры» для студентов 317 группы ф-та ВМК МГУ и спецкурса «Эффективное представление алгоритмов из алгебраических замыканий» для студентов ф-та ВМК МГУ.

Личный вклад. Все результаты получены автором лично и не имеют пересечений с его кандидатской диссертацией. Все публикации по теме работы выполнены без соавторов.

Публикации. Основные результаты диссертации описаны в 10 статьях журналов из перечня ВАК по специальности 01.01.09: четырёх сообщениях журнала «Доклады Академии наук» [1], [7] -[9], шести статьях «Журнала вычислительной математики и математической физики» [2]-[6], [10]. Результаты диссертации описаны также в статье журнала «Искусственный интеллект» [16], обзорной статье журнала «Таврический вестник информатики и математики» [20], учебном пособии [14], трудах конференции [13] и докладах конференций [11], [12], [15], [17]-[19]. Описания отдельных результатов включались в ежегодные научные отчеты ф-та ВМК МГУ, отчеты по проектам РФФИ, грантам Президента для молодых кандидатов и научных школ, программам научных исследований Президиума РАН и ОМН РАН

Структура и объем работы. Диссертация состоит из оглавления, введения, нулевого параграфа (с перечнем основных обозначений), шести глав, разбитых на параграфы (всего 28 параграфов), списка литературы (129 наименований), приложения (3 части). Используется тройная нумерация теорем, лемм, формул, примеров и рисунков: через точку указывается номер главы, номер параграфа и порядковый номер в этом параграфе. Основной текст занимает 258 страниц, приложение - 34 страницы.

СОДЕРЖАНИЕ РАБОТЫ Во введении дана общая характеристика работы, обоснована актуальность, определено направление исследований, даны обзоры исследований по теме диссертации и основных результатов.

В §0 представлены обозначения, используемые в работе1 1 = (1, . ,1)т, б = (0,. ,0)т, ё( =(0, ,0,1,0, ,0)т (z-я координата равна единице), Е - матрица, состоящая из одних единиц, col(#) -множество столбцов матрицы Я, Ха*ь - множество матриц размера а х Ъ с элементами из множества X, || htJ - матрица размера ахb с

элементами h^, i е{1,2,...,д}, ye {1,2,. ,b}, [_;cj -наибольшее цело число, не превосходящее числа х, rg(X) - максимальное числ линейно независимых векторов во множестве X (над полем Q) 2x = {Y\YcX}, Ckx = {Ye2х \ |Г|=А}, QL = {1,2,...,^}х{1,2, ,/} Ind(a) = {z е {1,2,...,/} | а, *0} и (а), =at для вектора а = (а„ mat(X) = [х, ...icj для множества векторов X - {хр . ,хг}: \X\-r L^X) - пространство векторов ортогональных ко всем вектора1 множества X, Р{\\кц La) Для преобразования F,Q->Q

,.,} = Ц> •>*.,) (иногда вместо {х,},£

пишем {х;}(, не указывая явно множество I, если оно очевидно)

В главе 1 введены основные понятия, определён главный объек исследований - алгебраические замыкания, изложены начала теори систем эквивалентностей В §1.1 поставлена обобщённая задач распознавания (при произвольном способе задания объектов) описана модель алгоритмов для ее решения. Множеств допустимых объектов М содержит объединение множеств К}

j е{1,2,...,/}, называемых классами. Каждому объекту SeM coo-ветствует бинарный вектор классификации a(S) = (а,(£),...,а,(S))

где cCj(S) - значение предиката «SeKj», ye{1,2,.. ,/}. Для каждой пары (S'iS,) еМхМ можно вычислить значения функций pn(S',S,)s Ez, QeQ2, Qz - конечное множество параметров, Ez -частично упорядоченное множество. Функция рп играет ту же роль, что и «расстояние» в классической постановке. Задача распознавания состоит в том, чтобы построить алгоритм А, который по набору S"1 - эталонных объектов с известными векторами

5(5'), ,á{Sm) для набора Sq - контрольных объектов строит

их векторы классификаций - классифицирует (распознает)

Алгоритм обобщенной модели вычисления оценок является суперпозицией распознающего оператора (РО) В и решающего правила (РП) С: А = В-С. Для объектов из Sq РО В получает матрицу Г[Л] = [| ГДЛ] ||?х/, у-й элемент которой - оценка принадлежности объекта St к классу К] -

Г„[*]= I Xab(j) I S

а,6=0,0 ПеП,, ¿zK]

где м/ gQ+ = {xeQ |х>0} при t е {1,2,...,т} (вес t-го объекта), w(í2)eQ+ при Q е {вес учёта Q-й близости), eeEz, В^'(S^S,) -функция близости такая, что

tín (¿ -1 tín (ó ,!>,)-10( KJ-[sa\Kj, а = 0.

Пока считаем, что ClA = Qz Далее в работе рассматриваем модель ABO с параметрами хаЬ = xab(j) е{0,(-1)о+А} для всех у g {1,2, .,/}, а е {0,1}, Ъ е {0,1} (модель без нормировок). РП по матрице оценок классифицирует объекты Простейшее РП - пороговое правило Сс^Л.

1. г,* С,,

Д, с}<ги<с2,

О, г < ci>

с, gQ, с2 еQ, с, <с2 Символ А обозначает отказ от классификации. При с, = с2 = с получаем полное пороговое РП Сс с порогом с.

Выше определены задача и модель в канонической форме В форме с семейством порогов рассматриваются частично упорядоченные множества Еп, функции рп.МхМ->Efi и пороги ёпеЕп, Q е Qz. Рассмотрим задачу распознавания в стандартной постановке, когда допустимые объекты задаются признаковым описанием S = (fi(S)>-- >/„($))е Щ Mt - метрическое пространство с

метрикой pt Простое сведение этой задачи к задаче с семейством порогов- Qz = {1,2, ..,п}, pn(S',Sl) = pn(fn(S'),fn(Sl)), En=[0,+co). Соответствующая модель при QA = Qz называется моделью ABO с системой (всех) одноэлементных опорных множеств В более обще! случае выбирается множество С1Л с 2n¡¡ \ {0} - система опорны. множеств (СОМ), а функция рп описывает различие объектов н подмножестве Q множества признаков

В §1.2 определена алгебра над алгоритмами, введенна Ю.И. Журавлевым Следующие операции над РО индуцирую соответствующие операции над алгоритмами при фиксированном РП Г^+^П^ + ВД, Г[сВ] = сГ[В], Г[5, • 52] = Г[5,]оГ[52]. Символ о используем для обозначения адамарова (поэлементного умножения Для произвольного множества X векторов линейног пространства над полем Q с ассоциативной операцией умножени вводим понятия: линейного замыканш

L(X) = {c,x,+ . +crxr | г б {1,2, .....creQ,x„ ,хгеХ},

алгебраического замыкания к -й степени

00

алгебраического замыкания U(X) = (J U* (X)

k=\

Для матрицы Я выражение U*(#) означает и*(со1(Я)), аналогично для ЦЯ) и U(Я) (далее все обозначения вводим только для U*()). Считаем, что U°(Z) = L({1}) - множество, состоящее из векторов, у которых все координаты равны. Множества алгоритмов (операторов) будем также называть моделями алгоритмов (операторов). Большинство определений, введенных для множества операторов ABO, естественным образом переносится на саму модель ABO (множество алгоритмов).

Определение. Оператор DnAal, который получает ненулевую

матрицу оценок T[Da^]: TIJ[DniaJ] = I[aJ{S') = a] I[pn(S',S,) = ё], (i,j) б QL, называется оператором разметки. Здесь и далее 1[п] = \, если выполняется условие п, 1[л] = 0 - в противном случае.

Теорема 1.2.1. Если В' - множество операторов обобщенной модели ABO, D" = {D^J^, тогда \Jk{B') = \]h(D')

В §1.3 получены результаты для систем эквивалентностей, заданных на множестве Х-{1,2, . ,q) с естественным порядком, которые в дальнейшем существенно используются при анализе алгебраических замыканий.

Определение. Множеством характеристических векторов классов эквивалентности ~ называется такое множество бинарных ненулевых q -мерных векторов 0(~), что

V(i,j)eXxX z~;oB!(x„ ,xj 6 ©(-)•*, = Xj =1.

Определение. Система эквивалентностей называется

регулярной, ест V(i,j)eXxX [i = j <=> Vt е {1,2, . ,т} г у].

пусть 0(b);,) = иЧЬ}:,) = иЧ©(Ь}м))

r=i

Определение. Конъюнкцией системы эквивалентностей {степени к, к <т, называется система &*[{-,}L]={~, ,}, г> :

I» ' * VI» J][ .да}

W(i,j)eXxX [/-,„ л у о у)& . &(/- у)],

^[ЬК,] = &"[{-,К,] при к>т, &°[Ь}:,]-Н- ©(-) = {!}•

Лемма 1.3.1. и*(Ь>Г-.) = L(&*[{~}".])

Определение. Произведением системы {~MKIi эквивалентностей, заданных на множестве Qv и системы 2}™i эквивалентностей, заданных на множестве Qv называется система эквивалентностей, заданных на множестве Qx х Q2, такая, что для все te{l,2,...,m}, (i,j)sQxxQ2, (,a,b)eQ(xQ2

(i,j)~,(a,b) о (j~ xa)&(j~u2b).

Произведение {~ , регулярно тогда и только тогда, когда ре гулярны системы {-^Д^, {~,t2)Z\ (лемма 1.3.4), а система &*[{-,}",] является произведением систем эквивалентностей &*[{~м}™|] &*[{~,,2}Г=1] (лемма 1.3.5).

В §1.4 описаны свойства операций внешнего и покоординатног произведений (здесь не приводятся). X<S>Y -{х-у1 \ х еХ,у е У}, гд XqQ4, FeQ'; X°Y = {xoy\xeX,yeY), где Xu7cQ? (здес для произвольных фиксированных q и /).

В §1.5 описаны матрицы оценок операторов из алгебраически замыканий. Пусть ©а'=0(~£г), А' =©(-„,) при tе{1,2,...,т}

ОеО^, где и - эквивалентности соответственно на множествах {1,2, и {1,2,...,/} такие, что

} « = г-^ ) о а, (Л =

Для эквивалентности , используем также символ (она не зависит от ПеП,). Пусть Г*1' = {Г[Я]|Яеи*(Я')}.

Лемма 1.5.1. Множество матриц Г*'1 является линейным замыканием множества

т

ии(®п,'®А') (15Л)

(=1 ПеП,,

Множество (1.5.1) состоит из характеристических векторов (представленных в матричной форме) классов эквивалентностей произведения {~а,}а, систем и {~п,}п,. Переход к и*{В") со-

ответствует переходу к &*[{~п,}а,] (см. леммы 1.3.5, 1.3.1), поэтому Г*'* описывается аналогично (при более сложно устроенных А')

т

и(©'®А'). (15 2)

<=1

Определение. Задача распознавания называется регулярной, если выполняются условия: 1. | {А?,1, .,Щ}\=1 (регулярность системы эквивалентностей 2 | |=<? (регуляр-

ность системы эквивалентностей 3. §т = 0.

Определение. Модель РО Я* называется корректной {относительно задачи распознавания), если \/Г е 0?х/ ЗВ е Я' • Г[5] = Г. В противном случае модель называется некорректной

Определение корректности (и последующих обобщений этого понятия) вводится для конкретной задачи: при заданных а(£') и рп (5", <!>,), 5'е5т, Из простых свойств отношений

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

Теорема 1.5.1. Модель 11(5*) корректна тогда и только тогда, когда выполнены первое и второе условия регулярности

В главе 2 получены критерии корректности алгебраических замыканий и разрешимости задач с помощью алгоритмов из этих замыканий. В §§2.1-2.3 продолжено изучение системы (см.

§13) По ней можно построить характеристическую матрицу сЬаг( {-,}",) ||?х?: \ =|{*е{1,2,. Л1,

О,;) е {1,2, нумерующую матрицу пшп({-}",) =|| х„ : У/б{1,2,. ..от} У(^)е{1,2,. ,?}2 ц-^о хц=хнг

В терминах этих матриц просто записываются критерии регулярности (леммы 2.1.2-2.1.3). При формулировках результатов используются семейства функций ГА, к е {1,2, ..}, подробно изученнные в конце §2.2. Передставителями семейства Е* являются, в частности, функции Рк(х) = ак /к(х) + .. + а, ф) + ай, аы,...,я„я0 >0, ак> 0,

где /г(х) = х(х -1) •... • (х - г +1). Например, хк еР1.

Теорема2.1.1. Пусть # = сЬаг({-,}",), ^еБ* при ке{ 1,2,...}, тогда справедливо равенство Ц./^(#)) = и*({~}",)

Полуметрику рн(г,]) = т-к{/ Я=[|\|Ц=сЬаг({~ }",) на множестве {1,2, назовём полуметрикой системы эквивалентностей {-,}", Из леммы 2.2.1 вытекает корректность определения и то, что функция рИ{1,]) является метрикой тогда и только тогда, когда система эквивалентностей регулярна

Теорема 2.2.2. Пусть - регулярная система эквивалент-ностей, #>1, Рке¥к, к е{1,2,...}, тогда матрица

1

Рк=Е-

Рк{т)

^(сЬагСЬ)",))

вляется матрицей метрики х q -матрицей попарных расстояний некоторой метрике на {1,2,..., <у}2), причем = и*({~ }",)

Теорема 2.2.3 - лемма 2.2.4. Пусть для всех натуральных к множество функций ¥к обладает тем свойством, что Р е¥к тогда только тогда, когда для произвольной системы эквивалентностей выполняется равенство F(char({~ }",)) = с1тг({~1}1) для неко-орой системы эквивалентностей {-*}/ = и4Тогда

ели Е(х)е¥'4, в(х)<=¥к\ ае{ 1,2,. .}, то

Р{х) + С{х)е¥ттл\ Р(х)-С(х)е¥к>+кг, а Е(х)е¥к> В §2.3 результаты §§21-2.2 представлены для обобщенной арактеристической матрицы Н =|| /гу Ц^ системы :

У(г,;)е{1,2,.. ,д}2 £ с,, с„ ,ст>0.

(€{1,2, ,т] ¡-,1

авенство Ц^(#)) = и'({-}",) справедливо при

рк=акхк+- - + а\Х + а0, ак >0, акА, ,а0> 0. Разрезный конус СиТ? является множеством /,-полуметрик на

севозможных д-точечных множествах пространств г е {1,2,,,} Теорема 2.3.1. Для регулярной системы функция

г _ . \*

рк.{ 1,2,...,9}2->[0,1], рк{г,]) = 1-

cl,...,cm > 0, является метрикой из конуса CUT?, для которой справедливо равенство U*({~,}£,) = L(i>) при q> 1, P=\\pk(iij)\\qxq

В §2.4 получены критерии корректности и разрешимости в общем случае. Пусть оператор разметки Bni(lj) такой, что Y[Bnt {i j)\ =

= в-а\ # = = ,а,УеА', а,=1 Пусть

т

1=1 ПеП,

Считаем, что F(B) = akBk +... + + а0ВЕ при F(x) - akx" +... + ахх + +а0, где Т[Ве\ = Е (очевидно, что ВЕ eL(B*)). Классификацией {q объектов по / классам) будем называть бинарную матрицу размера qxl, а также любое выражение, которое определяет значения некоторых ее элементов Следующая теорема обобщает результат Ю.И. Журавлева о реализации произвольной классификации в регулярной задаче с помощью алгоритмов вида

Z (2-4Л)

(a,b)zQL

Теорема 2.4.1. При FlceFk, ke {1,2,...}, справедливо равенство

Следствие. Если матрица оценок может быть получена оператором из Uк(В*), то она может быть получена оператором вида Z с(а,ь)Рк(В{аь)) пРи ^it е F4, в частности, оператором вида (2.4 1).

(a,b)sQL

Зафиксируем на множестве QL лексикографический порядок и в соответствии с ним выпишем матрицу Нк размера qlxql, в которой ((/,;), (а,Ъ)) -й элемент равен числу Fk (Гу [B(aJ})])

Теорема 2.4.2. Алгебраическое замыкание U*(5*) корректш тогда и только тогда, когда det(Ht) 0.

= 1-

Теорема 2.4.3. Алгоритм из {В Сс\В еИк(В')}, с реализует классификацию || ау Ц^е {О,!}*"' тогда и только тогда, когда совместна система неравенств (относительно хп.....хд1)

\К,М 1,1)Хп+- • + Кмялх91>0' О'.Лб/,, Кд(1,.)*п + ■ . + < (г> Л е 'о.

Кжа,ь)-^(Гц[В{а>Ь)]), Рке¥к, 1а={(^)едЬ \ ау=а},ае{ 0,1}

Теорема 2.4.4. Пусть в регулярной задаче распознавания д1 > 1, тогда функция рк. 0,1], р*((г,у),(а,6)) =

'I{(0,0 | (рп(5'>5,) = рп(5,,5я))&(ау(^) = аД5,))}Г*

V т\ал\

является метрикой из СиТ9/, для которой и* (В*) = Ь( }(а Ь)е(21) при Г Д/^] = рк((г,]),{а,Ь)), (г,у) е (ЗЬ, и для которой определитель д/ х -матрицы метрики отличен от нуля тогда и только тогда, когда замыкание 11к(В*) корректно

Лемма 2.4.1. Для любой метрики р из конуса СиТ?, д>\, существует задача распознавания с одним классом, в которой Г*'1 = Ь{Р), где Р - матрица метрики р.

В §2.5 подробно рассмотрена задача распознавания с двумя непересекающимися классами а(5) е {(1,0)т,(0,1)т} при Я е М. Пусть О^ - нулевая матрица размера дх д. Из леммы 2 5.1 и равенства

сЬаг(&А[{~01}п,]) =

сЬаг(&Д{~п,}п,]) О,

Очхч сЬаг(&ДНи,г])

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

объектов (поскольку эквивалентность на множестве {1,2,...,<7} индуцирует эквивалентность на Sq).

Лемма 2.5.1. В задаче распознавания с двумя непересекающимися классами для множеств /,, /2: и/2 с {1,2,.. ,q} и классификации «S\ еК{\К2 при i е /,, S¡eK2\ К{ при iel2» (*)

следующие утверждения эквивалентны:

1. ЗА g {В ■ Сс | В е U* (5*), с е Q}: А реализует классификацию (*) 2 ЗЛ е {5 • С^ |i?e U*(■#*)}' ^ реализует классификацию (*), где

CmaxdlTv IU) =11 °v IU: e@L aú = 1 ° h = тах[Мг]-3. Э^иЧи*)- V/е/, У/ е/2 ГП[Я]>Г;1[Я].

Теорема 2.5.1. В регулярной задаче распознавания с двумя непересекающимися классами и q контрольными объектами

1. Существуют операторы B[,...,Bq е L(B') такие, что любую классификацию объектов Sq можно получить алгоритмом вида

ít^Xc^k^q] (2 5.2)

V 1=1

2. Если некоторая классификация (*), /, и/2 c{l,2,...,q}, может быть получена алгоритмом из {В-С'тзх \ В е U^-S*)}, тогда ei можно получить алгоритмом вида (2.5.2)

3. Классификация (*), /,и/2с {1,2,. ,q}, реализуется алгорит

мом из {В-С0 \ В е U¿(i?')} тогда и только тогда, когда совместт система неравенств

í^Xi+... + h'Xq> О, ге/„ • + пщхц < 0, г е/2,

= ¡ {(О, О И Л Г, ^ е {1,2,..., gr}, 7 е {1,2,..., gr).

Теорема 2.5.2. Линейное замыкание L(B') в задаче с двумя классами корректно тогда и только тогда, когда оно корректно в задаче (с непересекающимися классами), которая получается из начальной удалением эталонных объектов, одновременно содержащихся в обоих классах Для замыкания U*(£*) теорема неверна.

В главе 3 найдены оценки степени корректного алгебраического замыкания. В §3.1 описана модель ABO с СОМ (см. с 12) и общей функцией близости. Пусть Qz = {1,2,...,и}, Q^ с 2Пг \{0} (СОМ),

ф А. м/с» си«

QeQ^, #,е{0,1, .,«}, q2e{0,1,...,л}, ёа)еЕа при oeQz. Частные случаи такой функции близости: Á■71 (5",S¡) = В^ Л• *(S',S¡),

а(5',5<) = В*' ^' ^(S^S,). (3.1.2)

Модель ABO (множество ее операторов) с произвольными СОМ и функцией близости вида В будем обозначать через В*(В).

Лемма 3.1.2. ЦЯ*(В*' Л'9"?2)) = Ц5*(В^ *••«)) = ЦВ'(В% )).

Теорема 3.1.1. Линейное замыкание L(5*(B^' 'е",Ч1'Яг)) совпадает с линейным замыканием модели ABO с СОМ О,, = {{1,2,...,и}} и функцией близости вида (3.1.2)

Пусть - эквивалентность на множестве {1,2,...,^}: '~F J о V®e{l,2,.. ,и} pC](Sl,Sl) = p0](S',SJ).

Лемма 3.1.3. Множество матриц оценок модели L(fi*(B^" 'е",9|,й)) является линейным замыканием множества (1.5 2), где 0' =0(~f), A'={a(5'),í-a(5")}\{6},/€{l,2,...,m}.

Множество ненулевых бинарных векторов одинаковой размерности, сумма которых равна вектору 1, называется ID-множеством

Теоремы 3.1.2-3.1.3. Пусть {©'}", - семейство Ш-множеств q -мерных векторов, тогда в пространстве М = Л/, х х Мп ¡э 2{<я,Ъ,с}п, ра\ рш(а, а)< ра{а, с), ра(Ь, а) = ра(Ь, с), юе{1,2,...,«}, существует задача распознавания с п признаками, в которой 0(~f) = 0' для всех t е{\,2,...,т} Для любого набора а,,...,ат бинарных 1-мерных векторов существует задача распознавания с признаковым пространством M = Q", признаковыми метриками ра(х,у)-\х- у\, сое. {1,2, ,п}, в которой множество матриц оценок линейного замыкания L(5*(B^' ,е"'?1 'ь)) совпадает с линейным замыканием множества (1.5 2) при А' = {а„\-а,}.

В §3.2 получена неулучшаемая оценка степени корректного замыкания: в регулярной задаче распознавания существует k < |_log2 qj + |_log2 /J, для которого модель U*(l?*) корректна

Теорема 3.2.1. Модель U(5*) корректна тогда и только тогда, когда корректна модель U*(B*), где k > [_log2 + [log2 / J

Теорема 3.2.2. Для любых натуральных параметров qui, q +1 >2, существует регулярная задача, в которой модель IГ(В) некорректна при k < [log2 q J + [log2 / J (неулучшаемость оценки)

Определение. Матрица || /у называется ЛЗ-матрицей модели

(множества операторов) R*, если Viiei?* ^ Гу[7?] 10=0

С ,))zQL

В §3.3 получена неулучшаемая оценка степени корректного алгебраического замыкания в задаче распознавания с непересекающимися классами, те при />2 и {a(S')}^ c{Sj}'J=l (решается в

предположении, что VSeM a(S) е {ё7}^=1) Переход Ь(Б*)->и4(5') соответствует преобразованию (которое может быть проинтер-

претировано как введение виртуальных эталонов в нашу задачу) 0, -» 0* = (0у о и*"1 (©)), где 0; = У 0', поскольку справедливы

I а&Щ

Теоремы 3.3.2 - 3.3.3. В задаче с I непересекающимися классами множество Г*'* совпадает с множествами

(U*(0)®í)u[j(0* ® {ё,})

Теоремы 3.3.1, 3.3.4. В задаче с I непересекающимися классами модель U(i?*) корректна тогда и только тогда, когда корректна модель и*(5'), где Л: > max[j_log2 при 1 = 2 и ¿ > |_log2 <¡rj +1 при

l> 2 Оценки являются неулучшаемыми

В §3.4 рассмогрена задача распознавания в стандартной постановке при Ml=... = Mn = Q, рг{х,у)=\х-у\ при г е{\,2, ..,п}, и модель ABO с системой всех одноэлементных опорных множеств Такая задача называется задачей с разнесенными эталонами, если Vre{l,2, .,«} VÓ€{a(S')}r=1 3/, еГ(5) 3t2eT(á) fr(S!')* fr(S'>), где T(á) = {te{l,2,...,m} | (á(S1 ) = á)v(á(S') = \-á)}

Теорема 3.4.1. В задаче с разнесенными эталонами второе условие регулярности выполняется тогда и только тогда, когда | | =

Теорема 3.4.2. В задаче с разнесенными эталонами множество матриц оценок Г*'* алгебраического замыкания k-й степени модели ABO с системой всех одноэлементных опорных множеств есть

/■ г ■к

и* и°Н») ®и*(А)

Чг=1 / у

где эквивалентности ~{г] такие, что пит({~,г(}"=|) -|| /Д51,) Ц^^.

В рассматриваемой задаче добавление новых эталонных объектов не оказывает влияние на корректность алгебраических замыканий

исследуемой модели. Отметим, что, модель L(B'(Be¿' напри-

мер, можно сделать корректной, добавив эталонные объекты в задачу.

Теорема 3.4.3. Для любых непустых множеств 0c{O,lf и А' с {0,1}? существует задача распознавания с разнесёнными эталонами, в которой множество матриц оценок операторов линейного замыкания модели ABO с системой всех одноэлементных опорных множеств совпадает с множеством L((© u {1}) ® (А' и {1}))

Теорема 3.4.4. В регулярной задаче с разнесенными эталонами алгебраическое замыкание к -й степени модели ABO с системой всех одноэлементных опорных множеств корректно при k > max[mm[«,|_log2 q J],|_log2 / J]. Оценка является неулучшаемой

В §3.5 исследованы подмодели В\хv)(lj)g/> модели ABO В формулах вычисления оценок подмодели В'(x,j){lJ)sP параметры х1} при (/,_/) <£Р равны нулю (остальные могут варьироваться) Очевидно,

ЦЯ* (*ц,*о1>*1о.*оо)) = ЦЯ'(*п>*<н>*ю)) = ЦЯ'^,,^,,^)) = L(5*(*n>*oi)) UB' (*, t,x¡0)) = L (В' (х{,)), L (В* (x¡1,xlo,xao)) = L{B'(xtl,xooy). Лемма 3.5.1. Если выполнено третье условие регулярности и ЗОеО^ V(S,S')eMxM [pn(S,S')< pa(S,S) => S = S'] (например, если одна из функций рп - метрика на М), тогда

ив\хи,х00)) = Ц^) Лемма 3.5.2. ВЕ еЬ(В*(хи,х00)) <=> L(5*(xn,x00)) = L(Z)*). Теорема 3.5.1. Пусть в задаче распознавания выполнено первое условие регулярности и V/ е {1,2, .., /} | {(рп (S', S¡ ))s, }/=11=q

J* *

(второе условие регулярности для В*(хи)), тогда модель U* (В* (я,,)) корректна при k > min[ [log2(^/ + l)J, [_log2#J + [_log2(/ + l)J ]

В главе 4 исследовано пополнение линейного замыкания (модели В' или и*(В')) операциями нормировки и деления. Поскольку Г*'* при любом 1,2,...} имеет вид (1 5.2), обозначим это множество # х/-матриц через Г*, считая, что ©' - Ш-множество ц-мерных векторов, А' - Ш-множество /-мерных векторов, ?е{\,2,...,т} (т.е. здесь т не обязательно число эталонных объектов). По нашим договорённостям будем также использовать системы эквивалентностей Ы,> {-?},. ЬЧ (вместо систем {~а,}а(, Н,г}а,, {~пЛ.,> см. §3 1) Считаем, что выполняются первые два условия регулярности и

т т

& = [)&', А = 0А', ©£ = и ©', ©°= и ©', А0 = А\{1}

1=1 (=1 ( А'={1} 1 А'#{1}

В §4.1 введены обозначения и определения пополненных замыканий множеств матриц, которые индуцируют соответствующие замыкания моделей операторов и алгоритмов

Определение. Стандартным замыканием относительно операции Ор: М* -> (3?х/, М* с О9*', множества матриц Я* называется множество ЬОрЦЯ*) = Ь({Ор(Я) | Я е ЦЯ*)пМ*}иЯ') Замыканием относительно операции Ор множества матриц Я* называется множество

и Ор(Я*) = Ь Ор ЦН') и Ь Ор Ь(Ь Ор Ь(Я*)) и.. .

В §4.2 исследована операция нормировки по сумме Ыг.

у.

1ух/

определенная на матрицах || уи Ц^,, в которых V/ е {1,2, ,д}

Лемма 4.2.2. Пусть ^ = ШЕ(Г'), тогда = Щ.ЦГ*) и Г§(Ме) = 9(ге(А)-1) + Г§(0)

/у '

' '' ах!

Теорема 4.2.1. Замыкание тгфк{&)) (и ЩХ(и*СВ'))) корректно тогда и только тогда, когда выполняются равенства

г8(0(&*[Н}(])) = ?,ге(0(&*[Н},])) = /•

Теорема 4.2.2. Если замыкание ЦУгЦик(В')) корректно, то замыкание и" (5*) корректно В обратную сторону утверждение теоремы, вообще говоря, не выполняется.

В §4.3 исследована операция нормировки по максимуму Ытш.:

Ги

Лтах(11гД»<>) =

дх!

определённая на матрицах | \уу Ц^: тах[{^}'=1]^0 при /е{ 1,2,

Лемма 4.3.1. Пусть Мтах = Штах(Г), тогда Ктах - Щ^ЦГ) и ГБ(Ктах) = ^(0) при 1 = 1, Г£(Мтах) = д-щ{к) при 1>\.

Теорема 4.3.1. Замыкание Штзх(\]к(В')) (и Щ^Цик(В*))) корректно тогда и только тогда, когда

|г8(0(&*[Н},])) = /, при /> 1, 1гё(0(&<[{~?},])) = <7, при 1 = 1.

В §4.4 исследована операция нормировки по отрезку [0,1] 7/[01]:

уч -тт^р ,у,]

•^[0,1] (II у у 11^) =

дх1

тах[г,1> >УА~Ш»[у,1»- ->Га\

определенная на матрицах ¡| у^ в которых нет строк из одинаковых элементов. Пусть 1~ ], если г -я и у -я строки матрицы та^©0) равны, Г = 0(~), ч'=\Т\, (2 А0 - £) = {2 • а -1 | а е А0}. В теореме 4.4.1 предполагаем, что множества 0, 0Е, Т, А, А0 построены для алгебраического замыкания и4(В"), например 0 = 0(&*[{~р},]).

Определение. Задача распознавания называется задачей с четной классификацией, если Vxеcol(mat(A°)T) [1-хеcol(mat(A°)T)], в противном случае - задачей с нечетной классификацией

Теорема 4.4.1. В задаче с нечетной классификацией пространство матриц оценок операторов замыкания IW[01](U*(.S')) есть

Ц(Г® А°)и(0<8>{1})), его размерность равна g'rg(A) + rg(0)--rg(L(0) nL(7")) = ^'(rg(A) -1) + rg(0£ u T); модель IW[01](U<(5')) корректна тогда и только тогда, когда q = q' и rg(A) = /. В задаче с четной классификацией пространство матриц оценок операторов замыкания UJV[0tIJ(U*(^*)) есть Ц(Г ® (2А° - £)) и (0 ® {!})), его

размерность равна q'(rg(A) -1) + rg(0); модель UiV[01](U*(5*)) корректна тогда и только тогда, когда rg(0) = q = q' и rg(А) = I.

В теореме 4.4.2 описан базис пространства, ортогонального к пространству матриц оценок операторов из ILV[W](U*(.6*)) (не приводится из-за громоздких формулировок) Для замыканий UiVz(U* (£*))> UA^(U4(В*)) базисы получены при доказательстве лемм 4 2.2, 4 3.1.

В §4.5 проведено сравнение различных видов нормировок и исследована операция деления Нормировка является пока единственной «естественной» операцией, для которой строение замыканий и критерии корректности не зависят от точного разбиения множеств 0 и А на подмножества 0', А' (не учитывается «геометрия классов»), ie{l,2,. ,т} Нормировка iV[01] частично учитывает «геометрию

классов», поскольку rg(lW[0il](U*(Z?*))) и корректность зависят от q'.

Теорема 4.5.1. В регулярной задаче распознавания с двумя непересекающимися классами замыкания IЖГ(Б*), UyV[01](5*), L(В )

корректны / некорректны одновременно В регулярной задаче распознавания с двумя классами замыкание и№тт(В') корректно

Теорема 4.5.2. Замыкание ЬБЦБ*) корректно тогда и только тогда, когда замыкание и (В*) корректно, где Б - операция взятия обратной по Адамару матрицы1.

о(|| и*/) =

У\

> Af(D) = {\\hu\\qxlMi,j)eQL h^O}.

qxl

Корректный алгоритм в алгебре с делением (индуцируется поэлементным делением матриц оценок) может быть представлен в виде +с1В2)-С,те {£„&,} с L(5*).

j i

В главе 5 исследована «нестандартная» корректность. Модель R' РО называется С? -корректной (корректной относительно множества РП С*), если VAе{0,1}?х/ BBeR', 3СеС*: С(Г[Я]) = А. В §5.1 введены основные определения, формализующие естественные требования на РП: частичной монотонности (поскольку РП алгоритма «должно верить» РО и относить объект к тем классам, оценка принадлежности к которым выше) Пусть X - система непустых подмножеств множества QL (быть может, не всех)

Определение. Решающее правило (РП) - отображение из Q?x/ в {0,1,A}?W. РП С называется X-монотонным, если для любой матрицы ||у, ||?х/ С(||ry IU) =11 av IU и Д™ всех Y&x справедливо V(/J) е Y, V(t,s)e Y av = 0, = 1 => YlJ <yls.

Множество X -монотонных РП будем обозначать через С'(Х).

В §5.2 изложены общие критерии получения классификации. В теореме 5.2.1 - в виде специального представления ЛЗ-матрицы. Теорема 5 2.2 является «наглядной» переформулировкой этого результа-

та По системе X и матрице Ä=||aff [|?x/e{0,l}i,!/ можно построить двудольный граф G(X,Ä) = (Vl(G),V0(G),E(G)), множество вершин первой доли - Vt(G) = {(/,;) 1^=1}, второй - V0(G) = {(/,;) | а„ = 0}, V(G) = V0(G) и rt(G) = QL, множество ребер -

E(G) = {{(i,j),(t,s)} | 3YeX:(i,j)€Y,(t,s)eY, atJ = l,a„ = 0}

Помеченный двудольный граф G(X,Ä,\\lu ||9></) получается приписыванием каждой вершине (i,j) веса w((z,y))' w((i,j)) = lIJ при (i,j) eVlt w((hj)) = ~l,j при (i,j)eV0

Определение. Пусть £[v] - множество всех ребер, инцидентных вершине v. Разметкой ребер помеченного графа G называется функция w.E(G) -> {0,1,2, . }, VveF(G) w(v)=£w(e).

<?e£[v]

Теорема 5.2.2. С помощью PO модели L(Fi) и X-монотонного РП можно получить классификацию А е {0,I}9*' тогда и только тогда, когда не существует ненулевой ЛЗ-матрицы L (модели R'), для которой найдется разметка ребер графа G(X, А, L)

Лемма 5.2.1 (простое обобщение теоремы Холла) устанавливает критерий существования разметки ребер помеченного целыми неотрицательными весами графа G(X,A,L)

В §5.3 получены критерии корректности относительно семейств построчно и постолбцово монотонных РП Пусть Xyi = ХГ yj Хй,

Xr = {{(i,j)\je{\,2, ,1}}}U,Xb = {{(I,J)\I<={\,2, . ,д}}}'Г_г

Определение. Классификация (qx/-матрица) \\atJ 11^ е {0,1}'*' согласована с матрицей || /у. ||9х,е Q?x/, если для всех (i,j) е QL lu>0 => ау=\, !d<0 => a,j-0

Лемма 5.3.2. Классификацию из {0,1}?х/ нельзя реализовать РО из и* (Я*) и X-монотонным РП, X = {У1з...,ГГ}, ^ =

|+... + |Уг тогда и только тогда, когда она согласована с ненулевой ЛЗ-матрицей |] Ц^ этой модели, для которой

ЧУеХ £/„ = О

Теорема 5.3.1. Модель ик(В') С (ХГ)-корректна тогда и только тогда, когда она корректна или I = 1. Модель ик(В') С'(ХВ)-корректна тогда и только тогда, когда она корректна или д = 1.

Теорема 5.3.2. Модель IIк(В') одновременно является / не является корректной, С*(Хп)-корректной, С* ({(¿Ь))-корректной

В §5.4. исследована корректность в задаче распознавания с / непересекающимися классами, / > 2.

Теорема 5.4.1. Матрица 1 = [Л,. Л,] является ЛЗ-матрицей модели Ь(5*) тогда и только тогда, когда для ее столбцов Я1,...,Я1

и ©'1 Е^ь^и®'.

7=1 ае А* \'еГ(й) / JeЫ^a) \!еТ(а) у

где А* = {¿(5') | а,(5') = 1, / = Т^И) и {I - а(5') | а, (5') = 0, / =

Теорема 5.4.2. В задаче распознавания с непересекающимися классами матрица Ь = \)л Л,] является ЛЗ-матрицей модели и*(Л*) тогда и только тогда, когда для ее столбцов

¿Я^П^С©;), У/е{1,2,..,/} Я, 6^(0)).

у=1 7=1

Определение. Пусть С* - множество РП, А* - множество классификаций /-матриц). Будем называть модель Я' РО С*-А*-корректной, если У А е А* 35 е Я', ЭС е С*. С(Г[В]) = А

Определение. РП С называется РП по максимуму, если СО^Дх/И^Дх/' при | {/ е {1,2, ..,1}\г„= тахО,„. .,/,,]} 1*2 справедливо (а,,)'=1 =(А, . ,Д), а иначе (аД=1 = где = гаах[/, Будем называть С* ах-{0,1}^'-корректную модель НП-корректной, где С'щ - множество всех РП по максимуму, {0,1}'*' - множество бинарных ^ х / -матриц, у которых в каждой строке ровно одна единица.

Теорема 5.4.3. Следующие утверждения эквивалентны'. 1. Существует ненулевая ЛЗ-матрица модели и*(В*), в каждой строке которой не более одного положительного элемента и не менее одного неотрицательного 2 Модель ик(В") не является НП-корректной 3 Модель ик(В') не является С*(ХГ)-{0,1}'*'-корректной А. Модель и*(В*) не является С' ({£)£})- {0,1}'*'-корректной

В задаче с I непересекающимися классами вместо корректности следует требовать от модели НП-корректность, поскольку их критерии совпадают лишь при / = 2

Теорема 5.4.4. При любом с е <3 классификация из {0,1}4"' реализуется алгоритмом из {В С. С1 | В е и* (#')}, с, <с2, тогда и только

тогда, когда она реализуется алгоритмом из {В Сй \ В е и* (5*)}.

В §5.5 исследовано сведение одной задачи распознавания к другой с помощью перекодировки векторов классификаций. Пусть 2пЛ - задача распознавания с тремя непересекающимися классами, а задача с двумя (пересекающимися) классами Zп2 получается из исходной следующим изменением векторов классификаций' (1,0,0)->(1,0), (0,1,0)->(051), (0,0,1)->(1,1). Теорема 5.5.1. Если модель ик(В*) в задаче Zнп3 НП-корректна (или просто корректна), то модель Ик(В*) корректна и в задаче

Если модель и*(В*) в задаче 2п2 корректна, то модель и*+|(В') корректна (и НП-корректна) в задаче 2тЪ Утверждение нельзя усилить, заменив модель и*+1(5*) замыканием и* (5*)

Рис. 5.5.1. Символическое изображение утверждения теоремы 5 5 1 Пусть 2НП, - задача с / непересекающимися классами, а 2г - набор задач 21р у е {1,2...../}, таких, что 2^ получается из 2аЫ перекодировкой. ёу->(1,0), ё,->(0,1) при I е {1,2,...,/}\{_/}. Аналогично, 2г - это набор задач 2Х1], ;е{1,2,.. ,/}, ге{1,2,...,/}\{;}: ^ —>(1,0), ё, -> (0,1), а эталонные объекты 5, для которых а(5) г {ё,,ё7} в 2т1, в задаче 2Ъ1] отсутствуют. Модель корректна в Z2 (23) тогда и только

тогда, когда она корректна во всех задачах этого набора Для краткости, утверждения теоремы 5.5.2 показаны на рис. 5.5.2.

Рис. 5.5.2. Символическое изображение утверждений теоремы 5 5 2 Глава 6 посвящена отдельной математической проблеме, которая имеет приложения не только в теории распознавания, но и в теории интерполяции- критериям вырожденности матрицы попарных /, -расстояний конечной системы точек в Я™ и их обобщениям В §6.1 введены основные обозначения и получены некоторые критерии. Для функции /•^'->11 пусть ЛЧЛ = {хеХ |/(х) ^ 0} (носитель функции /), /(У) = {/(х) | х е Г}, где У с X. Пусть задана система точек

5 = Ж, с К" |5А = А,х...хАт. А, = {а,0, .,а1р{1)} = = {($), |»б{1,2,...,?}}, а!0< <аш, р(0>1 при /е{1,2, ,т}

<----ТТГ"—«-

ИЫ(5 )

Ц*(Д*)

Ь(-З')

Пусть Р^ - матрица попарных /,-расстояний. Лемма 6.1.1 описывает множество U4 [S] = U* (PJ).

Определение. Система точек S называется к -сингулярной, если размерность пространства U* [5] меньше q.

Теорема6.1.1. Пусть z:{l,2,...,C*}С{* 2 т, - биективное отображение Система точек {s,}f=I к-сингулярна тогда и только тогда, когда является 1 -сингулярной система точек {с/,}^, с R^': Vi€{1,2,. .,Ckn} [Ц), = (<?,), « Vrez(i) ($),=(*,),].

Теорема 6.1.2. Система точек S не является к-сингулярной ри к<т тогда и только тогда, когда любая функция f(xx,x2,...,xm) а точках системы S может быть представлена в виде конечной суммы функций, каждая из которых зависит от к переменных Лю-ая функция /(х,,х2, . ,хт) на точках множества S может быть редставлена в виде конечной суммы функций, каждая из которых ависит от |_log21S |J переменных

Пусть G - минимальная группа (с операцией суперпозиция), со-ержащая преобразования g Rm -» Rra, t е {1,2,...,/я}, {x,^} с R •

0„ ,sm), s,£{x,y),

(Sp • >Sm)> St =y

Лемма 6.1.2. Для любого преобразования geG справедливо ра-енство и* [5] = и* [£(£)] Например, система точек Б к-сингулярна югда и только тогда, когда к-сингулярна система точек g(S)

Достаточно ограничиться рассмотрением точек на целочисленной ешетке, поскольку и*[{(д1Л)>1), -.,ат,4(,,т))},!,] = и4[{(6(/,1), .¿0,/я))},?=1].

Теорема 6.1.3. Система точек £ = является 1-сингулярной тогда и только тогда, когда существует такое подмножество

X с {1,2,...,<7}, что для любого преобразования gsG система точек {&(•*,)},<=* не отделима от системы точек {&(£,)},е!|2, Д\\х гиперплоскостью В условии отделимость гиперплоскостью можно заменить отделимостью с помощью фиксированной гиперплоскости с уравнением alxi+... + aMxm+a0=0,0e{al,...,am}.

Теорема 6.1.4. Система точек S = {s,}'=1 пространства Rm является 1 -сингулярной тогда и только тогда, когда

3(с„ ,cjeR?\{Ö}. V~seRm ¿с,/>(ЗД = О,

1=1

где р - метрика Хэмминга или /, -метрика Теорема перестаёт быть верной при изометричном вложении S в другое пространство.

т

Пусть функция П• Rm —► R такая, что N(Tl)<zX = X{at,bt},

r=\{tz{\,2.....m}\at*bt}\. Если П(Х) = {+1} или П(Х) = {-1}, то

функция П называется константным параллелепипедом (кп) размерности г, а если в каждой точке (с,, ..,ст) множества X она равна

(-1)с, с =| {i е{1,2, ..,т} | ct =at}\, то называется размеченным параллелепипедом (рп) размерности г Элементы множества X называются вершинами рп (кп) Параллелепипед называется последовательным относительно множества А, если

т

N(U) = xr, Vi б {1,2, ..,т) Зге {1,2,. ,p(t)}. 7'c{V„fl,J.

Теорема 6.2.2. Система точек S к -сингулярна тогда и только тогда, когда найдется конечная сумма £ функций из множества П*, для которой 0 Ф ЛА[£] с S Утверждение справедливо для множеств

П4 следующих функций- 1. К.п размерности больше к с одной общей вершиной 2. Р.п. размерности больше к с одной общей вершиной 3. Р.п. размерности (к +1). 4. Последовательных относитель-

но А р.п. размерности (£ + 1). 5. Последовательных относительно А к.п. размерности (к +1)

Доказательства (теорема 6.2.2, следствие, леммы 6.2.4 - 6.2.5) следуют из теоремы 6.2.1 (не приводится из-за громоздких обозна-ений), основная идея которой - сведение задачи о к -сингулярности задаче о свойствах множества булевых векторов, линейное замыка-ие которого описывает пространство 1/(и*[5]).

В §6.3 показано приложение результатов о к -сингулярных истемах к распознаванию. По теореме 2.4.4 некорректность модели U* (-6*) эквивалентна £-сингулярности системы QL, заданной матри-ей попарных /,-расстояний. При представлении подсистемы к -син-/лярной системы точек в виде носителя суммы р.п. в явном виде поучается ненулевой вектор пространства 1/(11* [S1]), а применительно задаче распознавания - ненулевая ЛЗ-матрица модели (и класси-икация, не реализуемая оператором из U*(5*) и пороговым РП)

Теорема 6.3.1. В задаче распознавания с двумя непересекающимися классами и разнесенными эталонами для любого оператора В из алгебраического замыкания k-й степени модели ABO с системой всех одноэлементных опорных множеств существуют функции g 1 < <. ,<rk<n, от к переменных, для которых

S mís,),...,/^))

l£/¡< <rk<n

Для модели и задачи в теореме 6.3.1 роль системы S играют контрольные объекты в признаковом пространстве Q" Замыкание U*(В*) некорректно тогда и только тогда, когда система Sq k-

сингулярна. Расположение эталонных объектов роли не играет (при условии разнесенности). Алгоритмы линейного замыкания с пороговым РП являются, в некотором смысле, суперпозициями элементов

группы G и линейного классификатора Это определяет вид разделяющих поверхностей в пространстве Sq для модели L(5*).

В заключении перечислены основные результаты работы (см. раздел «На защиту выносятся»)

Приложение состоит из трёх частей В первой части дан перечень обозначений, введенных по ходу изложения. Во второй части описано решение проблемы нахождения критерия эффективной реализации ABO, которая более двадцати лет оставалась открытой (вынесено в приложение, поскольку вопрос практической реализации алгоритмов модели не является центральным для данной работы) Рассмотрен случай D.z = {1,2,.. ,п), СОМ €1А: Q^ с 2fiz,

w(ß) = ]Tw(<ö),

йк=П

модели В'(хи) с функцией близости В^' 'е"'Ч[ 41 (результаты легко обобщаются на другие случаи) Описаны все COM QÄ, для которых при всех параметрах и аргументах функции близости найдутс /с Qz,K/?}c{0,l,2,...}.

X ^(S^S^a^W + ß I (7 1

íiefi^ aeíJ <ае/ шеПг\!

Из теоремы Ю.И. Журавлёва следует необходимость эффективног вычисления (7.1) для практической реализации алгоритма. П теореме 7.1 нужный класс СОМ исчерпывается всеми подмножества ми множеств С[12 п)и{{1,2,...,и},0}, ге{1,л-1}, и СОМ вид C{i,2, ,п\> ■< rs<n В третьей части описань

некоторые прикладные задачи, решённые автором в последние годь (см раздел «Практическая ценность»)

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Дьяконов А Г О выборе системы опорных множеств для эффективной реализации алгоритмов распознавания типа вычисления оценок//Докл РАН.-2000 -Т.371 -№6 - С 750-752.

2. Дьяконов А Г О выборе системы опорных множеств для эффективной реализации алгоритмов распознавания типа вычисления оценок // Ж вычисл. матем и матем физ - 2000. - Т.40. - №7 -С 1104-1118

3. Дьяконов А Г Алгебра над алгоритмами вычисления оценок, минимальная степень корректного алгоритма // Ж. вычисл. матем и матем физ -2005 -Т 45.-№6.-С. 1134-1145

4 Дьяконов А Г Алгебра над алгоритмами вычисления оценок-монотонные решающие правила // Ж вычисл. матем. и матем физ. - 2005.-Т 45 -№10. - С.1893 - 1904

5. Дьяконов А Г Алгебра над алгоритмами вычисления оценок нормировка и деление // Ж вычисл матем. и матем. физ. - 2007 -Т47 - №6. - С 1099- 1109.

6. Дьяконов А Г Метрики алгебраических замыканий в задачах распознавания образов с двумя непересекающимися классами // Ж вычисл матем. и матем физ. - 2008. - Т.48 - №5 - С.916 - 927.

7. Дьяконов А Г Критерии корректности алгебраических замыканий модели алгоритмов вычисления оценок // Докл РАН - 2008. -Т420 -№6.-С 732-735

8. Дьяконов А Г Алгебраические замыкания обобщенной модели алгоритмов вычисления оценок // Докл. РАН - 2008. - Т.423 -№4 -С461 -464

9. Дьяконов А Г Критерии вырожденности матрицы попарных /, -расстояний и их обобщения // Докл. РАН - 2009 - Т 425 - №1 -С. 11-14.

10 Дьяконов А Г Алгебра над алгоритмами вычисления оценок, нормировка по отрезку // Ж вычисл матем и матем физ - 2009 -Т.49. - №1. - С.200 - 208

ОСТАЛЬНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

11. Дьяконов А Г Эффективная реализация алгоритмов распознавания // Интеллектуализация обработки информации, тез. докл. Междунар. науч. конф. - Симферополь, 2000. - С.32.

12. Дьяконов А Г Об одном подходе к решению задач из области BCI // Сборник докладов XII Всероссийской конференции ММРО-12. - М -МАКС Пресс, 2005. - С.95 - 97.

13. Дьяконов А Г Графовые и матричные критерии корректности алгоритмов распознавания образов // Тр VII междунар конф. ДМвТУС - М : МАКС Пресс, 2006. - С.114 - 118

14. Дьяконов А Г Алгебра над алгоритмами вычисления оценок: Учебное пособие. - М • Издательский отдел ф-та ВМиК МГУ им М В Ломоносова, 2006 - 72 с (ISBN 5-89407-252-2).

15. Дьяконов А Г Корректность относительно семейства решающих правил// Интеллектуализация обработки информации: тез. докл. Междунар. науч. конф. - Симферополь. Крымский научный центр HAH Украины, 2006. - С 77 - 78

16. Дьяконов А Г Корректность относительно семейства решающих правил // Искусственный интеллект - 2006. - №2 - С.61 - 64.

17 Дьяконов А Г Анализ кластерных конфигураций в одной проблеме фильтрации спама // Сборник докладов XIII Всероссийской конференции ММРО-13. - М. МАКС Пресс, 2007. - С.476 - 478.

18. Дьяконов А Г Метрические критерии корректности в теории распознавания образов // Проблемы теоретической кибернетики Тез докл. XV междунар. конф - Казань1 Отечество, 2008. - С 31.

19 Дьяконов А Г Исследование алгебраических замыканий алгоритмов распознавания операторы разметки // Интеллектуализация обработки информации тез докл Междунар. науч. конф. -Симферополь Крымский НЦ HAH Украины, 2008 - С.96 - 98.

20. Дьяконов А Г Исследование алгебраических замыканий алгоритмов распознавания: операторы разметки // Таврический вестник информатики и математики. -2008. -№1. - С. 199 -203.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 08 07 2009 г Формат 60x90 1/16 Услпечл 2,0 Тираж 100 экз Заказ 365 Тел 939-3890 Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им МВ Ломоносова, 2-й учебный корпус, 627 к

Введение

§0. Обозначения

Глава 1. Описание алгебраических замыканий обобщённой модели алгоритмов вычисления оценок

§1.1. Модель алгоритмов вычисления оценок (АВО)

§1.2. Алгебра над алгоритмами

§1.3. Системы эквивалентностей

§1.4. Операции внешнего и покоординатного произведений

§ 1.5. Матрицы оценок операторов из алгебраических замыканий

Глава 2. Критерии корректности и разрешимости

§2.1. Характеристические матрицы систем эквивалентностей

§2.2. Метрики систем эквивалентностей

§2.3. Обобщённые характеристические матрицы и метрики систем эквивалентностей

§2.4. Описание корректных полиномов

§2.5. Характеристические матрицы в задачах распознавания с двумя классами

Глава 3. Оценки степени корректного алгебраического замыкания

§3.1. Модель АВО с общей функцией близости

§3.2. Неулучшаемая оценка степени корректного алгебраического замыкания

§3.3. Задачи распознавания с непересекающимися классами

§3.4. Модель АВО с системой одноэлементных опорных множеств

§3.5. Исследование некоторых подмоделей

Глава 4. Алгебра над алгоритмами, пополненная операциями нормировки и деления

§4.1. Основные определения. Замыкания относительно операций

§4.2. Нормировка по сумме

§4.3. Нормировка по максимуму

§4.4. Нормировка по отрезку

§4.5. Сравнение различных видов нормировок. Деление матриц распознающих операторов)

Глава 5. Корректность относительно множества решающих правил

§5.1. Решающие правила

§5.2. Общие критерии получения классификации

§5.3. Критерии корректности относительно семейств построчно и постолбцово монотонных решающих правил

§5.4. Корректность в задаче распознавания с непересекающимися классами

§5.5. Сведение задач распознавания

Глава 6. Критерии вырожденности матрицы попарных 1Х -расстояний и их обобщения

§6.1. к -сингулярные системы точек

§6.2. Описание А:-сингулярных систем точек

§6.3. Приложение результатов о &-сингулярных системах к распознаванию

В начале 1970х годов Ю.И. Журавлёвым была описана модель алгоритмов вычисления оценок (АВО) для решения- задач распознавания^ [ЖН71], [ЖКТ74]. Каждый алгоритм модели представлялся в виде суперпозиции распознающего оператора и решающего правила. Распознающий оператор строил матрицу оценок принадлежности контрольных объектов (которые алгоритм должен классифицировать) классам, анализируя схожести подописаний контрольных и эталонных объектов (классификация которых уже известна). Решающее правило на основе этой матрицы оценок классифицировало контрольные объекты. В АВО5были-отражены многие эвристические методы, которые применялись тогда при решении прикладных задач, и модель стала своеобразным универсальным языком описания алгоритмов распознавания [Ж98]. Например, представителями модели были тестовые алгоритмы [ДЖК66], [Яд71] и алгоритмы «Кора» [Бн67], [Вн73], успешно зарекомендовавшие себя на практике.

В конце 1970х годов Ю.И.Журавлёвым был предложен алгебраический, подход к решению • задач распознавания: корректный-алгоритм (который не делает ошибок на контрольный выборке) было предложено искать в виде алгебраического выражения над некорректными (эвристическими) алгоритмами [Ж77а], [Ж776], [Ж77в]. Над распознающими операторами были введены операции сложения, умножения на константу и умножения как операции над их матрицами оценок (умножение проводилось поэлементно). При фиксированном решающем правиле эти операции индуцировали операции над алгоритмами распознавания. Множество алгоритмов, состоящее из всех полиномов степени не выше к над алгоритмами- некоторой^ модели, было* названо алгебраическим замыканием к-й степени этой модели. Множество всех полиномов - алгебраическим замыканием (если ясно из контекста, то

- Задачу распознавания образов по традиции российской научной литературы последних лет называем задачей распознавания (изначально термин «образ» был не совсем корректен РКГ89]). алгебраическим замыканием также называется алгебраическое замыкание конечной степени). Для модели кусочно-линейных решающих поверхностей и АВО было доказано, что существует и в явном виде выписывается корректный алгоритм-полином над некорректными алгоритмами. Отметим, что основное достижение алгебраического подхода — строгое доказательство того, что в теории распознавания возможно построение «хороших» алгоритмов на базе «плохих», устраняя недостатки одного конкретного алгоритма достоинствами остальных. Эту идею используют многие конструкции, в том числе самые современные и практически эффективные: комитеты- [Мз71], [Мз90], бустинг (boosting) [Sc90], [FS95], смешение мнений экспертов (mixtures of experts) [JJ91], усреднение по ансамблю [Н98], модульное обучение (modular learning) [OWS90], области компетентности [РЭ81], нелинейные монотонные корректирующие операции [В98], [BQ0], [РВ99]. Само доказательство было проведено «чисто алгебраическими» методами, что продемонстрировало возможность применения- «классической» математики в . неформализованных областях анализа данных, в которых изначально господствовали лишь эвристические методы и для-каждой новой задачи заново создавался свой алгоритм.

Алгебраический подход к решению1 задач распознавания интенсивно развивался- [ЖР87], [Ж88], [Ж98], [РЧОЗ]. В нём можно выделить отдельную ветвь - теорию локальных и универсальных ограничений К.В'. Рудакова [Р89], [Р92], [Р871], [Р872], [Р873], [Р874], [Р881], которая поставила своей целью создание универсального языка, пригодного для-описания и исследований задач преобразования, информации. В процессе своего развития алгебраический подход приобрёл не только- сторонников, но и противников. В основном, критика алгебраического- подхода фокусирует внимание на «непрактичность теории» и невозможность в явном виде применять корректные алгоритмы-полиномы при решении прикладных задач. B.JI. Матросов показал, что существуют подмодели алгебраических замыканий АВО, которые содержат корректные алгоритмы и «ничем не хуже» большинства современных моделей

- б с точки зрения общепринятой теории надёжности В.Н. Вапника -А.Я.Червоненкиса [ВЧ74], [V98]. К.В. Воронцов предложил методы эффективного использования конструкций алгебраического подхода для решения прикладных задач [В98], [В99], [В00].

Отметим, что все исследования, в основном, были сконцентрированы на оптимизации алгоритмов модели [Рз76], [Рз88], [ЖРС06] и алгебраических выражений над ними [В99]. При этом и сторонниками и противниками алгебраического подхода упускался важный объект исследования; Напомним, что в классических работах [Ж77а], [Ж776], [Ж77в] предложено искать алгоритмы в рамках алгебраических замыканий. Доказано, что там существуют корректные алгоритмы. Доказательства являются^ типичными теоремами существования. Не постулируется, что решать прикладные задачи нужно именно с помощью алгоритмов, построенных в этих доказательствах. Таким образом, предметом исследований могут быть (и должны быть) алгебраические замыкания как таковые, но до настоящего- времени они не были даже достаточно хорошо» описаны. Споры, которые велись вокруг алгебраического подхода (например, по вопросам его практической эффективности) концентрировались вокруг методов.построения алгоритмов, свойств.этих алгоритмов и т.д., но не вокруг алгебраических замыканий. Только имея полное и точное описание алгебраических замыканий, можно анализировать: есть ли в них «хорошие» алгоритмы, как их синтезировать, и т.д.

Технику анализа алгебраических конструкций в рамках классической теории1 удалось построить В.Л. Матросову [М85], [М89]. Изначально она рассматривалась как аппарат для решения задачи о теоретическом обосновании надёжности^ алгоритмических построений^ в алгебраическом подходе [М80], [М81ж], [М82], [М84ж], [М84], [М85ж]'. Наверное поэтому, с её помощью удалось решить лишь несколько, но очень важных проблем, связанных с

- «Классической» здесь называем теорию, которая непосредственно связана с работами [Ж77а], [Ж776], [Ж77в]. В ней исследуется такая же модель АВО и такой же вид алгебраических замыканий. корректностью алгебраических замыканий (возможностью получить операторами замыкания произвольную матрицу оценок в рассматриваемой задаче распознавания1): найти критерии корректности алгебраических замыканий (В.Л: Матросов [М81]), оценку степени корректного алгебраического замыкания (B.JI. Матросов- [М85], Т.В. Плохонина [П87]), примеры задач распознавания, которые не решаются (точно) алгоритмами из алгебраического замыкания конечной степени (В.JI. Матросов [М81], Т.В. Плохонина [П85]). Эти результаты, в определённом смысле, поставили гораздо больше проблем, причём, более сложных: нахождение «наглядных» критериев- корректности, получение пониженных оценок, описание всех задач, разрешимых алгоритмами из алгебраического замыкания конечной степени.

Настоящая работа посвящена исследованию алгебраических замыканий конечных степеней модели АВО. Отметим; что все результаты получены для обобщённой, модели АВО-(и справедливы для стандартной). Основной целью работы было исследование именно классической модели (сохраняя, все традиционные алгебраические конструкции)-. Обобщения вызваны* желанием сделать модель «более современной», адаптировав её'для решения прикладных задач, которые появляются в последнее десятилетие. Первое обобщение модели связано с введением в формулу вычисления' оценок слагаемых, которые учитывают удалённость классифицируемого объекта от объектов рассматриваемого класса и его близость к объектам других классов. Идея, подобного изменения формулы принадлежит Ю.И. Журавлёву и реализована в работе А.А. Докукина [До08] (без исследования специфики новой- модели). Второе обобщение связано с изменением учёта близости между объектами, которая в классическом случае определялась как взвешенная* сумма близостей признаковых подописаний этих объектов [Ж78а]. Модель выписывается для

- При наложении на решающее правило необременительных требований (см. дальше по тексту) это гарантирует решение задачи алгоритмами замыкания при любой классификации контрольных объектов.

2 Для стандартной модели АВО в работе часто удаётся получить более сильные результаты. произвольного способа задания объектов, в том числе отличного от признакового. Единственное требование - возможность вычислять для любой пары объектов значение функции, которая является аналогом расстояния, но на которую не накладывается никаких существенных ограничений. В задаче может быть задано семейство таких функций (каждая формализует своё понятие «похожести» пары объектов), при этом их значения принадлежат некоторому частично упорядоченному множеству. Ниже перечислим основные результаты, полученные в работе, с кратким историческим обзором предыдущих исследований.

Получение «наглядных» конструкций алгебраического подхода

До настоящего времени не была разработана техника, которая не только предоставляет арсенал методов для анализа алгебраических замыканий модели АВО, но и даёт простую геометрическую интерпретацию алгебраических конструкций. Большинство известных алгоритмов распознавания имеют очень простые и наглядные описания определяемых ими разделяющих поверхностей (в задаче с двумя непересекающимися классами это поверхность в признаковом пространстве, по одну сторону которой лежат объекты, которые алгоритм относит к первому классу, а по другую - ко второму). Например, для линейного классификатора - это гиперплоскость [TF78], для метода ближайшего соседа — последовательность рёбер диаграммы Вороного [ПШ89], для нейросети с несколькими слоями и персептронными элементами — граница полиэдрального множества [Мс]. Алгоритмы алгебраических замыканий конечных степеней до сих пор подобного описания разделяющих поверхностей не имели, несмотря на полученные критерии корректности алгебраических замыканий АВО и разрешимости задач. Критерии [М81], [М85] были изложены в терминах теории систем линейных неравенств G.H. Черникова. [468] и не допускали простой интерпретации в терминах самой задачи распознавания. В. работе получены именно геометрические критерии корректности модели и разрешимости задач алгоритмами модели, описан вид разделяющих поверхностей, в терминах преобразования метрики представлен переход от линейного замыкания к алгебраическому замыканию конечной степени (гл. 2, 6, [Д085] [Д08д] [Д09д]).

Отметим, что параллельно предложена новая техника анализа алгебраических конструкций: техника систем эквивалентностей (гл. 1, 2 [Д08о]). Показано, что матрица оценок оператора алгебраического замыкания конечной степени является' линейной комбинацией характеристических векторов (записанных в матричной форме) классов эквивалентностей некоторой системы эквивалентностей. Элементарно описывается преобразование системы, соответствующее переходу от линейного замыкания модели к алгебраическому произвольной степени, при этом весь анализ во многих случаях может быть проведён лишь для линейного замыкания. Отметим также, что между задачами распознавания и системами эквивалентностей имеется соответствие (гл. 2, 3), которое позволяет весь анализ проводить в терминах систем. Большинство классических результатов, например центральный результат алгебраического подхода о корректности алгебраического замыкания модели АВО в классе регулярных задач, является следствием простых свойств-эквивалентностей (и даже получается в более общем виде, см. гл. 1). Описание всех задач, для,которых некорректно алгебраическое замыкание конечной' степени

После создания B.JI. Матросовым техники описания алгебраических замыканий модели АВО много результатов удалось получить буквально «слёту». Была обоснована некорректность алгебраического замыкания второй степени на множестве всех регулярных задач [М81], затем некорректность алгебраического замыкания произвольной конечной степени [П85]1. Следующая естественная проблема — полное описание класса (регулярных) задач, для которых алгебраическое замыкание фиксированной, степени некорректно.

- Данная публикация имеет неточное название: вместо «конечной степени» в заглавии написано «второй степени», что вводит в заблуждение многих исследователей, см., например, [Ро08]. Отметим, что в [М85] также упоминается некорректность алгебраического замыкания произвольной конечной степени, но строгого доказательства не приводится.

Однако более 20 лет существенных продвижений в решении этой задачи не было. В работе такие классы задач описаны, причём в самом общем случае (см. гл. 6, [Д09д]). Отметим, что параллельно описаны семейства алгоритмов, содержащие корректные алгоритмы минимальной степени (гл. 2). В частности, одно из таких семейств - множество классических полиномов Ю.И. Журавлёва над алгоритмами [Ж776].

Теоретическое обоснование понятия, корректность

В алгебраическом подходе к решению задач распознавания- принято рассматривать модели алгоритмов с фиксированным-решающим правилом. На него накладывают достаточно необременительное требование: корректность решающего правила (сюръективность. реализуемого им отображения), а на множество распознающих операторов — достаточно жёсткое требование: корректность модели (возможность получить произвольную матицу оценок в рассматриваемой задаче распознавания). Единственная цель всех этих ограничений — гарантировать получение произвольной* классификации* контрольных объектов; Так почему же изначально не сделать это определением корректности модели? Этот вопрос не исследовался; и строгих обоснований- традиционно-принимаемых допущений- нет. В работе- исследована корректность относительно семейства решающих правил (гл. 5, [Д05м], [ДОби]). Модель называется корректной относительно семейства (в задаче распознавания), если для любой классификации контрольных объектов существует распознающий оператор модели и решающее правило семейства, суперпозиция которых даёт эту классификацию. Оказалось, что для «естественных» семейств решающих правил понятия корректность и корректность относительно семейства совпадают. На семейства решающих правил, при этом, накладывались лишь незначительные ограничения частичной монотонности. Такая формализация понятия «естественное отображение» принадлежит К.В. Рудакову [Р95],

РВ99]: правила не должны «портить» оценки принадлежности, полученные распознающими операторами1.

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

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

Степень корректных алгоритмов-полиномов, построенных Ю.И. Журавлёвым в [Ж776] асимптотически равнялась qlogq, где q - число контрольных объектов (1977г.). Хотя вопрос оценки'сложности обычно встаёт первым при построении подобного рода конструкций, проблема имеет достаточно долгую* историю. Первая нетривиальная, оценка степени к -корректного алгебраического замыкания модели АВО была получена B.JI. Матросовым: к <q + 1 -2, где / — число классов в задаче распознавания (1985г., [М85]). Отметим, что оценки Ю.И. Журавлёва и B.JL Матросова были получены для модели АВО с одноэлементными опорными множествами (частный случай модели при специальном выборе основного её параметра — системы опорных множеств). Используя разработанную в [М85] технику, Т.В. Плохонина получила оценку к<т, где т - число эталонных объектов (1987г., [П87]). С помощью методов теории категорий К.В. Рудакову удалось получить оценку k<\\og2ql\ (1989г., [Р89]), которая долгое время ошибочно1 считалась

1 Изначально требования монотонности накладывались на корректирующие операции. неулучшаемой для модели АВО (считалось, что для любых натуральных qui существует задача распознавания, в которой некорректно алгебраическое замыкание степени к при l<^<|log2^r/J). Отметим, что в [Р89] исследовался другой тип алгебраических замыканий: вместо «классических» полиномов над распознающими операторами с нулевым свободным членом рассматривались полиномы с ненулевым свободным членом, который интерпретировался как оператор, получающий матрицу оценок с одинаковыми, элементами1. Хотя, как следует из полученных ниже результатов, для модели АВО это не имеет значения. В данной работе впервые более чем за четверть века исследований удалось получить неулучшаемую оценку, зависящую от параметров q и I гл. 3, [Д05с]). Для важных частных случаев получены пониженные неулуч-шаемые оценки (гл. 3, [Д08о]). Пополнение алгебры над алгоритмами

Классическая алгебра над алгоритмами распознавания содержит операции сложения, умножения и умножения на константу. Пополнение этой алгебры новыми операциями или замена умножения другой операцией уже исследовались (см. [Р92]). Однако особого интереса результаты этих исследований не представляли, поскольку эксплуатировали стандартную идею: новая операция, применённая к представителям «хорошего» множества матриц оценок, должна получить базис пространства матриц. «Хорошим» множество считалось, если в нём для любой позиции существует матрица, в которой элемент на этой позиции по модулю больше остальных. До сих пор не были найдены «естественные» операции, которые значительно упрощают критерии корректности, не делая их вырожденными. В работе найдены и исследованы такие операции: нормировки (гл. 4, [Д07], [Д09]). До сих пор также не было исследовано пополнение алгебры над алгоритмами операцией деления. В данной работе показано, что деление является достаточно «мощной»

- Это факт часто не учитывается исследователями. алгебраической операцией (гл. 4, [Д07]). Попутно в работе введено понятие «замыкание в стандартной форме» (когда алгебраические выражения с новой операцией строятся специальным «простым» способом). Почти все замыкания, представленные в работе, достаточно рассматривать в стандартной форме. Например, алгебра алгоритмов с делением эквивалентна замыканию в стандартной форме относительно операции взятия обратной (по Адамару) матрицы1. Связь алгебраических замыканий модели АВО с другими моделями алгоритмов распознавания

В описании модели АВО нашли отражение многие идеи «успешных» методов распознавания XX века. В работе продемонстрирована связь между алгебраическими замыканиями АВО и некоторыми современными моделями алгоритмов распознавания (гл. 2, 6, [Д085]). Например, переход к алгебраическим замыканиям АВО соответствует применению специальных ядер в методе опорных векторов (SVM) [BGV], [Виг]. Эта связь позволяет учитывать достоинства одного метода при настройке другого. Например, при построении классических корректных алгоритмов-полиномов над АВО неявно использовался переход в пространство, в котором есть линейное разделение объектов-, а затем само разделение производилось фиксированной гиперплоскостью. Естественно, такие конструкции непрактичны, переобучены [В04] и служат лишь для доказательств теорем существования. Из результатов, полученных в работе, следует способ синтеза более надёжных алгоритмов, используя идею SVM построения оптимальной (а не какой-нибудь) разделяющей гиперплоскости. Причём её можно строить и при отсутствии линейного разделения объектов, не переходя в • алгебраическое замыкание высокой степени (при этом будет получен, вообще говоря, некорректный алгоритм). С другой стороны, в SVM можно использовать идею АВО работать

- Это, видимо, объясняет, почему алгебра алгоритмов с делением не встречалась в литературе: не было найдено удобной формы для представления результатов.

- Здесь слово «объект» используется в общем смысле (т.е. не обязательно это объект распознавания, см. гл. 2). не в исходном признаковом пространстве (объекты часто вообще задаются не признаковым описанием), а в пространстве значений функций близости1 В алгебраических замыканиях АВО, по сути, используются два ядра: одно -функция близости, второе - полиномиальное (для перехода в соответствующее алгебраическое замыкание). В работе также показана связь линейного замыкания ^ АВО с линейной регрессией и жёсткой интерполяцией (гл. 6), из которой следуют методы настройки алгоритмов'из алгебраических замыканий. Отметим, что эти- методы в работе не излагаются, поскольку выходят за рамки основной тематики. Работа, помимо всего прочего, иллюстрирует то, что в современном распознавании мало принципиально различных методов. Все используют одни и те же идеи, часто «превращаются» друг в друга- при специальном- выборе параметров, имеют схожие геометрические интерпретации. И чем сложнее модель, тем к большему числу других моделей- она» сводится (примером также могут служить нейронные сети, см. [Н98]), естественно, тем актуальнее проблема эффективной- настройки параметров модели. При этом алгебраические замыкания (сложной)' модели АВО достаточно просто описываются.

Нахождение критериев вырожденности матрицы попарных 1Х-расстояний и их обобщений

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

- Отметим, что на похожей идее базируются результаты теории беспризнакового распознавания в гильбертовом пространстве [Ср01].

Матрицы попарных расстояний возникают во многих задачах, связанных с интерполяцией, например с помощью радиальных базисных функций (RBF) [Вх91] или жёстких функций (riddle functions) [RS93]. Один из результатов, полученных И.Шёнбергом в серии работ [S37], [S38], [S38a] о вложении-метрических пространств в гильбертово, - невырожденность таких матриц для конечной системы попарно различных точек пространства R"1 и метрики lp, 1 <р<2, q> 1. Особый интерес представляет случай р = 1, для- которого многие' исследователи пытались найти «геометрический» критерий вырожденности матрицы попарных расстояний1. В' [DLC] показано, что системы точек плоскости R , которые соответствуют вырожденным, матрицам, л должны содержать замкнутые пути- (closed^ paths) — подсистемы вида {(al,bl),(alibl+l)Yl=l, br+x = bx. Прямое обобщение' этого понятия* на случай пространства R'" при произвольном натуральном т даёт только достаточное условие- вырожденности матрицы, см. [L89], [RS93]. Критерий был впервые получен в [RS93] с помощью-техники размеченных прямоугольников (signed rectangles). В» этой работе используется обобщение этого- понятия' — размеченные параллелепипеды. Отметим, что подобные конструкции часто встречаются в теоретических работах по теории интерполяции. Например, введённый в [ВР93] брусок (brick) является проекцией размеченного параллелепипеда на плоскость.

В. работе показано, что задача о невырожденности матрицы попарных ^-расстояний, возникает также при нахождении критериев корректности алгебраических замыканий конечной степени модели АВО (гл. 2; [Д08д]). Более того, интерес представляет задача' о размерности пространства значений

- Для полноты исторического обзора можно упомянуть работу [GP71], в которой доказано, что определитель матрицы попарных расстояний» вершин дерева зависит только от числа вершин и отличен от нуля, если в дереве больше одной вершины.

- Идея «замкнутого пути» появилась в [DS51] (эта работа, согласно [L89] и [Мд92], содержит неточности). Такая же конструкция под названием «замкнутая молния» использовалась при решении тринадцатой проблемы Гильберта [А57]. всевозможных полиномов степени не выше к от столбцов такой матрицы (с адамаровым умножением). В работе введено понятие А:-сингулярности, формализующее «полноту» пространства таких полиномов. Получены критерии А;-сингулярности (один из критериев является обобщением результата [RS93], при этом предлагается неиндукционный способ доказательства), в том числе новые критерии вырожденности матрицы /, -расстояний (гл. 6, [Д09д]).

Ниже дадим дополнительную характеристику работы.

Методика исследования: методы алгебраического подхода-к решению задач распознавания, теории булевых функций, теории систем линейных неравенств, комбинаторики, теории графов, линейной алгебры, теории метрик и разрезов:

Практическая ценность. Работа носит теоретический характер. Для иллюстрации возможных практических применений в приложении описаны прикладные задачи, при решении которых использовались результаты работы. Задачи были поставлены в рамках Международных соревновании учёных по интеллектуальному анализу данных (data mining).

Публикации. Результаты работы изложены в четырёх сообщениях журнала «Доклады Академии наук» [ДООд], [Д08д], [Д08о], [Д09д], шести статьях «Журнала вычислительной математики- и математической физики» [Д00], [Д05с]; [Д05м], [ДО7], [Д085], [Д09], статье журнала «Искусственный интеллект» [ДОби], обзорной- статье журнала «Таврический вестник информатики и математики» [Д08т], учебном пособии [Д06], трудах конференции [Д06т]> и докладах конференций [ДООт]; [Д05Ь], [ДОбк], [Д07т], [Д08к], [Д08и] (всего 20 публикаций). Описания отдельных результатов работы включались в ежегодные научные отчёты факультета ВМК МГУ, а также в научные отчёты по проектам РФФИ 08-07-00305-а, 08-01-00636-а, 08-01-90016-Бела, 06-01-08045-офи, 05-01-00332-а, 02-01-00558-а, 99-01-00433-а, грантам Президента МК-533.2007.9, МК-1660.2005.9, НШ-5294.2008.1, НШ-5833.2006.1, программам научных исследований Президиума РАН и ОМН РАН.

Личный вклад. Все результаты получены автором лично и не имеют пересечений с его кандидатской диссертацией. Все публикации по теме работы выполнены без соавторов:

Апробация работы. Основные результаты работы и отдельные её части докладывались на

- научном семинаре кафедры, математических методов прогнозирования факультета ВМК МГУ (2009 г.);

- научном семинаре «Алгебрологические методы в задачах классификации и прогнозирования» (руководитель: Ю.И. Журавлёв, Москва, МГУ, ВМК, 1999 - 2000, 2003 - 2009 г.);

- научном семинаре «Дискретный анализ» (руководители: А.А. Сапоженко, Н.Н.< Кузюрин, Москва, МГУ, ВМК, 2003'г.);

- научном семинаре «Дискретная математика и математическая кибернетика» (руководители: В.Б. Алексеев, А.А. Сапоженко, С.А. Ложкин, Москва, МГУ, ВМК, 2008 г.);

- Ломоносовских чтениях (Москва, МГУ, ВМК, 2008 - 2009 г.);

- Международных научных конференциях «Интеллектуализация обработки информации - 2000, 2006, 2008» (Симферополь, Крымский научный центр НАН Украины, ТНУ, 2000; 2006, 2008 гг.) [ДООт], [ДОбк], [Д08и];

- 7й и 8й Международных конференциях «Дискретные модели в теории управляющих систем» (Москва,- 2006, 2009 гг.) [ДОбт];

- 15й Международной конференции «Проблемы теоретической кибернетики» (Казань, 2008 г.) [Д08к];

- девятнадцатой Крымской осенней математической школе-симпозиуме KROMSH-2008 (Украина, Крым, Ласпи-Батилиман, 2008 г.);

- 12-й и 13-й Всероссийских конференциях «Математические методы распознавания образов» (Москва, 2005, 2007 гг.) [Д05Ь], [Д07т].

Материалы работы легли в основу обязательного кафедрального курса лекций «Алгоритмы, модели, алгебры» для студентов 317 группы ф-та ВМК МГУ и спецкурса «Эффективное представление алгоритмов из алгебраических замыканий» для студентов ф-та ВМК МГУ.

За цикл работ [Д05с], [Д05м], [ДОби], [Д07], [Д085], [Д08д] автору была присуждена Медаль РАН для молодых учёных (постановлением Президиума РАН №59 от 24.02.2009), за цикл работ [ДООд], [ДООт], [Д00] - Медаль РАН для студентов ВУЗов (постановлением Президиума РАН №197 от 6.09.2001). За цикл работ «Алгебра над алгоритмами вычисления оценок» [Д05с], [Д05м], [Д05Ь], [ДОбт], [Д06] был получен грант поддержки талантливых студентов, аспирантов и молодых учёных Московского государственного университета имени М.В. Ломоносова 2006 года. Также во время выполнения работы автор был лауреатом конкурса «Грант Москвы» в области естественных наук (2001 г.), поддержан стипендиями МГУ для молодых преподавателей и учёных, добившихся значительных результатов в преподавательской и научной деятельности (присуждены решениями Ученого Совета МГУ от 24.12.07 и 22.12.08).

Структура работы. Работа состоит из оглавления, введения, нулевого параграфа (с перечнем основных обозначений), шести глав, разбитых на параграфы (всего 28 параграфов), списка литературы (129 наименований), приложения. В списке литературы все публикации перечислены в алфавитном порядке по фамилиям авторов, публикации одного автора (группы авторов) следуют в хронологическом порядке. Публикации автора работы приведены отдельно в конце общего списка. В работе используется тройная нумерация: в номерах теорем, лемм, формул, примеров и рисунков через точку указывается номер главы, номер параграфа и порядковый номер в этом параграфе идентифицируемого объекта. Для удобства номера сносок напечатаны полужирным подчёркнутым шрифтом. В работе утверждение называется леммой не только в случае, если носит технический характер (служит для доказательства других утверждений), но и в случае, если оно носит иллюстративный характер (и не представляет особой теоретической ценности, по сравнению с другими теоремами данной главы). Доказательство теоремы (леммы) заканчивается словами «теорема доказана» («лемма доказана»). Все примеры, кроме 1.1.1 и 2.5.1, занимают ровно один абзац (поэтому не отделяются пустой строкой от основного текста). В приложении дан перечень обозначений, которые вводились по ходу изложения (не в нулевом параграфе), приведены некоторые результаты об эффективной реализации алгоритмов модели АВО на ЭВМ (при каких значениях параметров такая реализация возможна), а также информация о1 прикладных задачах, решённых автором в 2005—2008 гг. Основной текст занимает 258 страниц, приложение занимает 34 страницы.

Автор выражает огромную благодарность своему учителю, Юрию Ивановичу Журавлёву, который оказал значительное влияние на формирование научного мировоззрения автора, а также всем своим коллегам из МГУ и ВЦ РАК

§0. ОБОЗНАЧЕНИЯ

Используем следующие обозначения: 1 = (1,.,1)т - вектор, состоящий из одних единиц; 0 = (0,.,0)т - вектор, состоящий из одних нулей; et = (0,.,0,1,0,.,0)т — бинарный вектор1, /-я координата которого равна единице, а остальные координаты равны нулю; Е — матрица, состоящая из одних единиц (размерность векторов и размеры матриц будут ясны из контекста), I - бинарная матрица размера q х q, у которой только элементы на главной диагонали равны единице. Для вектора а = (al,.,al)r введём также следующие обозначения: а = 1 - a- (\-ax,.,\-aiY, lnd{a) = {iG{l,2,.,l}\ai ^0}, \\а \\=ах + . + «/, через (a)i будем обозначать его i -ю координату ai. Если вектор а является бинарным, то вектор а называется его инверсией (или отрицанием), а число || а || - его нормой. Для конечного множества векторов Х = {х1,.,хг}, \Х\=г все элементы в котором попарно различны), обозначим через mat(X) = [3cj. xr ] матрицу, составленную из всех векторов этого множества (порядок записи вектор-столбцов в матрице не будет играть роли или будет специально оговорен). Для матрицы Н обозначим через row(Н) множество её строк, через col(#) — множество её столбцов. Запись || htJ ||ахй обозначает матрицу hu . hlb К\ ••• Кь

- Бинарным вектором называется вектор, состоящий из нулей и единиц.

- В работе не используются мультимножества, поэтому, например, |/|=2 и ^а, =ах+а2 при I = {1,2,2,1,1}. часто будем указывать размеры матрицы с помощью нижнего индекса: НахЬ — матрица Н размера axb. ХахЬ - множество матриц размера axb с элементами из множества X.

Пусть R — поле (множество) вещественных чисел, Q — поле (множество) рациональных чисел, Z - кольцо (множество) целых чисел. Любой из этих символов с верхним индексом «+» обозначает подмножество всех неотрицательных чисел соответствующего множества, например R+ = [0,+00),

Z+={0,1,2,.}. Большинство результатов, полученных в работе, будет сформулировано с использованием символа Q (для поля рациональных чисел), который может быть заменён символом R (все они справедливы и для поля вещественных чисел), если не оговорено противное. Выражение F(|| hy ||ах6) при некотором преобразовании F: Q -» Q обозначает матрицу || F(hj) \\axb.

Запись {xj/e/ обозначает множество (Jl*,}. Если из. контекста ясно, iel какое множество пробегает индекс i, то это множество не будем указывать-, используя обозначение {х(}г-. Аналогичные обозначения используем, если элементы множества параметризованы набором индексов. При I = {ix,.,ik},

111= к, считаем, что порядок на множестве / не будет важен или будет указан), а также a,-)!=i ••>«/) •

Для любого множества X векторов линейного пространства над полем Q через щ{Х) обозначаем максимальное число линейно независимых векторов в этом множестве. В случае конечного множества X эта величина

- Сам индекс указывается, поскольку {х,} - множество, состоящее из одного элемента xt. совпадает с рангом матрицы mat(X). Для матрицы Н выражение щ{Н) обозначает её ранг, а выражение det(i/) - её определитель.

Далее используем также обозначения: [х] — целая часть числа х снизу (наибольшее целое число, не превосходящее числа х ), [х~] - целая часть числа х сверху (наименьшее целое числом: х < у),

QL = {О', j) I ie {1,2,., q), j е {1,2,., /} },

2Л = {Y | Y <z X} - множество всех подмножеств множества X,

Ckx={Ye 2Х\ | Y\=k}.

Для множеств

15.,^)|1 <tx<.<tk<n}\, \{{tx,.,tk}\\<tx<.<tk<n}\ используем одно обозначение: (это не вызовет путаницы), ск-\ск I-п] число всех сочетаний из п элементов без повторений объёма к (из п по к).

Как принято, системы равенств и неравенств записываем, объединяя все равенства и неравенства, входящие в систему, фигурной скобкой (слева). Таким образом, фигурная скобка обозначает логическое условие «и». По аналогии, логическое условие «или» обозначаем квадратной скобкой, например, запись х = 1 х = 2 эквивалентна записи л; е {1,2}.

ЗАКЛЮЧЕНИЕ

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

Описана обобщённая модель алгоритмов вычисления оценок (АВО) для решения задач распознавания при произвольном способе задания объектов, для-которой получены следующие результаты, (справедливые и для классической модели):

1Л. Предложена теория* систем, эквивалентностей* для описания' И' исследования- алгебраических, замыканий конечных степеней. Каждой задаче распознавания, ставится в соответствие система эквивалентностей; по которой строятся характеристическая матрица и матрица попарных 1\-расстояний. В терминах этих матриц просто описываются алгебраические замыкания модели. Переходу к алгебраическому замыканию фиксированной степени соответствуют специальные преобразования матриц.

2. Получены новые критерии корректности^ алгебраического замыкания конечной степени и критерии разрешимостш задач алгоритмами этого замыкания: Критерии имеют простую геометрическую интерпретацию, позволяют описывать разделяющие поверхности алгоритмов, алгебраических замыканий в пространстве контрольных объектов. Найдены простые семейства корректных полиномов (в частности, доказано, что классические полиномы Ю.И: Журавлёва образуют базис в алгебраическом замыканииконечной степени).

3. Получена1 неулучшаемая* в общем случае оценка степени» корректного алгебраическогозамыкания модели АВО!, Для важных частных случаев получены пониженные оценки: для задачи распознавания с непересекающимися классами, для-.задачи с разнесёнными эталонами и модели

АВО с системой всех одноэлементных опорных множеств, для подмоделей модели АВО (при обнулении параметров учёта близости и антиблизости).

4. Исследовано пополнение новой операцией^ линейного замыкания множества полиномов ограниченной степени^ над АВО. В качестве новой операции рассматривались нормировка (при различных способах её определения: по сумме, максимуму, отрезку) и деление. Во всех случаях получена формула для размерности соответствующего замыкания, найдены критерии корректности. Показано, что многие замыкания* (в том числе при пополнении другими операциями) пред ставимы в стандартной форме (алгебраические выражения» можно строить не используя вложение новых операций).

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

6. Исследована^-сингулярность конечной-системы точек (неполнота размерности пространства значений полиномов ограниченной степени над* столбцами матрицы попарных /i-расстояний этой системы).* Показана связь ^-сингулярности с 1-сингулярностью. Полностью описаны все ^-сингулярные системы (как содержащие подсистемы, специального вида). Найдены новые критерии вырожденности матрицы попарных 1\-расстояний конечной системы точек, в частности связанные с разделимостью её подмножеств гиперплоскостью.

1. АБР. Айзерман М.А., Браверманн Э.М., Розоноэр Л.И. Метод потенциальных функций в.теории обучения машин. -М.: Наука, 1970.

2. АЖ85. Алексанян А.А., Журавлёв Ю.И. Об одном подходе к вопросу построения эффективных алгоритмов распознавания // Ж. вычисл. матем. и матем. физ. 1985. - Т.25. - №2. - С.283-291.

3. А57. Арнольд В.И. О функциях трёх переменных // Докл. АН СССР. 1957. — Т. 114. — №4. — С.679-681.

4. Бн67. Бонгард ММ Проблема узнавания. М.: Наука, 1967.

5. Вн73. Ванцвайг М.Н. Алгоритм обучению распознаванию образов «Кора» // Алгоритмы обучению распознаванию образов. — М.: Сов: радио, 1973. — С.82-91.

6. ВЧ74. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974.

7. В 98. Воронцов КВ. О «проблемно-ориентированной оптимизации базисов задач распознавания // Ж. вычисл. матем. и матем. физ. 19981 - Т.38. - №5. -С.870-880.

8. В99. Воронцов КВ. Локальные базисы в алгебраическом подходе к проблеме распознавания: Дис. . канд. физ.-матем. наук / ВЦ РАН. М., 1999. -107 с.

9. В00. Воронцов КВ. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Ж. вычисл. матем. и матем. физ: — 20001 — Т.40. — №1. — С. 166-176.

10. В04. Воронцов КВ. Обзор современных исследований- по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. Симф. 2004. - №1. - С.5-24.

11. Вл. Воронцов КВ. Курс лекций «Математические методы обучения по прецедентам»//http://www.ccas.ru/voron/ (на 17.11.08).

12. Гу04. Гуров С.И. Упорядоченные множества и универсальная алгебра (вводный курс): Учебное пособие. — М.: Издательский отдел ф-та ВМиК МГУ, 2004г. 104 с.

13. ДЛ01. ДезаМ.М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001.-736с.дм74. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. М.: Наука, 1974. - 312с.

14. ДЖК66. Дмитриев А.Н., Журавлёв Ю.И., Кренделев Ф.П. О математических принципах' классификации предметов и явлений // Дискретный анализ. — Новосибирск: Наука, 1966. Вып.7. - С.3-15.

15. До01. Докукин А.А. О построении в алгебраическом замыкании одного алгоритма распознавания // Ж. вычисл. матем. и матем. физ. — 2001. — Т.41. — № 12.-С. 1873-1877.

16. До08. Докукин А.А. Синтез, полиномов над экстремальными» алгоритмами вычисления' оценок: Дис. . канд. физ.-матем. наук. / ВЦ РАН. — М., 2008.- 102 с.

17. Д11. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и матем. физ. 2002. - Т.42. - №5. - С.741-753.

18. Ж76. Журавлёв Ю.И. Непараметрические задачи распознавания образов // Кибернетика. 1976. - №6. - С.93-103.

19. Ж77а. Журавлёв Ю.И. Корректные алгоритмы над множествами некорректных (эвристических) алгоритмов. I // Кибернетика. — 1977. — №4. С.5-17.

20. РК776. Журавлёв Ю.И. Корректные алгоритмы над множествами-некорректных (эвристических) алгоритмов. П7/ Кибернетика. — 1977. — №6. — С.21—27.

21. Ж77в. Журавлёв Ю.И. Корректные алгоритмы над множествами некорректных (эвристических) алгоритмов. III // Кибернетика. — 1978. №2. - С.35-43.

22. Ж78а. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Пробл. кибернетики. — М.: Наука, 1978.-Вып. 33.-С. 5-68.

23. Ж88. Журавлёв Ю.И. Об алгебраических методах в . задачах распознавания и классификации // Распознавание, классификация, прогноз. 1988. — Т.1. -С.9-16.

24. Ж98. Журавлёв Ю.И. Избранные научные труды. — М.: «Магистр», 1998. — 420 с.

25. ЖГ89. ЖуравлёвЮ.И., ГуревичИ.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1989. — Вып. 2. - С. 5-72.

26. ЖИ79. Журавлёв Ю.И., Исаев ИВ. Построение алгоритмов распознавания,, корректных для заданной контрольной выборки // Ж. вычисл. матем. и матем. физ. 1979. - Т.19. - № 3: - С.726-738.

27. ЖКТ74. ЖуравлёвЮ.И, Каминов М.М., Туляганов Ш.Е. Алгоритмы вычисленияюценок и их применение. «ФАН»,Ташкент, 1974.

28. ЖН71. Журавлёв Ю.И, Никифоров В:В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. — 1971*. №3. - С. 1-11.

29. ЖР87. Журавлёв Ю.И, Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования)- информации1 // Проблемы прикладной математики 1987. - С. 187-198.

30. ЖРС06. ЖуравлёвЮ.И, Рязанов В.В., Сенъко О.В «РАСПОЗНАВАНИЕ». Математические методы. Программная система. Практические применения. М.: Фазис, 2006. - 176 с. (ISBN 5-7036-0108-8).

31. ЖФВ06. Журавлёв Ю.И, Флёров Ю.А., Вялый М:Н. Дискретный анализ. Основы высшей алгебры. М.: МЗ Пресс, 2006. — 208 с.

32. Зыков А'.А. Теория конечных графов I. Сибирское отделение. Наука, 1969.-543 с.

33. Зыков А.А. Основы теории графов. -М.: Наука, 1987.

34. ИК98. Ильин В.А., КимГ.Д. Линейная алгебра и аналитическая геометрия: Учебник. -М.: Изд-во Моск. ун-та, 1998. 320 с.

35. Кс77. Кострикин А.И: Введение в алгебру. М.: «Наука», 1977. - 496 с.

36. Крбб. Куратовский К. Топология: В 2 т. -М.: Мир, 1966-1969. Т. 1-2.

37. Мй04. Майсурадзе А.И. Об оптимальных разложениях конечных метрических конфигураций в задачах распознавания образов // Ж. вычисл. матем. и матем. физ. 2004. - Т.44. - №9. - С. 1697-1707.

38. Мз71. Мазуров В:Д. Комитеты системы неравенств и задача распознавания // Кибернетика. 1971. -№ 3. - С. 140-146.

39. Мз90. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. -М.: Наука, 1990.

40. Мл97. Малюгин ВД. Параллельные логические вычисления посредством арифметических полиномов. М.: Наука. Физматлит, 1997.

41. ММ04. Маркус М., МинкХ. Обзор по теории матриц и матричных неравенств. М.гЕдиториал УРСС, 2004. - 232 с.

42. М80.< Матросов В. JI. Корректные алгебры ограниченной ёмкости над множествами некорректных алгоритмов // Докл. АН СССР! 1980. — Т.253. — № 1. — С.25-30.

43. М81ж. Матросов В.Л. Корректные алгебры ограниченной ёмкости над множеством алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. 1981.-Т.21.-№5.-С. 1276-1291.

44. М81. Матросов В.Л. О критериях полноты модели алгоритмов вычисления оценок и её алгебраических замыканий // Докл. АН СССР. 1981. —. Т.258. — №4. — С.79Г—796.

45. М82. Матросов В.Л. Оптимальные алгебры в алгебраических замыканиях операторов вычисления оценок // Докл. АН СССР. — 1982. — Т.262. №4. -С.818-822.

46. М84ж. Матросов B.JI. Нижние оценки ёмкости многомерных алгебр алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. —1984. Т.24. - №12. - С. 1881-1892.

47. М84. Матросов B.JI. Ёмкость алгебраических расширений модели алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. — 1984. — Т.11. — №5. С. 1719—1730.

48. М85ж. Матросов В.Л. Ёмкость полиномиальных расширений множества алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ.1985. Т.25. — №1. - С.122—133.

49. М85. Матросов В.Л. Корректные алгебры алгоритмов1 распознавания ограниченной ёмкости: Дис. . докт. физ.-матем. наук. / Гос. пед. инст-т им. В .И. Ленина. М., 1985. - 220 с.

50. М89. Матросов В.Л. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания // Распознавание, классификация, прогноз. Математические методы и их применение. — М.: Наука, 1989. Вып. 1. - С. 149-176.

51. Мд92. Медведев В.А. Опровержение одной теоремы Дилиберто и Страуса // Мат. заметки. 1992. - Т. 51. - № 4 - С. 78-80.

52. Мс. Местецкий Л.М. Математические методы распознавания образов. Курс ■ лекций, ВМиК МГУ, кафедра ММП. - 2002. // http://www.ccas.ru/frc/ papers/mestetskii04course.pdf (на 17.11.08).

53. Оре О. Теория графов М.: Наука, 1980. - 336 с.

54. П85. Плохонина Т.В. О некорректности алгебраического замыкания второй степени семейства алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. 1985.-Т.25.-№7.-С.1073-1086.

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

56. ПШ89. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989.

57. Пр70. Проскуряков И.В. Сборник задач по линейной алгебре. М.: Наука, 1970.-384 с.

58. РЭ81. Растригин Л.А., Эренштейн P.X. Коллективные правила распознавания. М.: Энергия, 1981.-244 с.

59. Ри82. РиорданДж. Комбинаторные тождества. — М.: Наука, 1982.

60. Ро08. Романов М.Ю. Построение обобщённых полиномов минимальной степени над алгоритмами вычисления оценок: Дис. . канд. физ.-матем. наук. / ВЦ РАН. М., 2008. - 81 с.

61. Р871. Рудаков КВ. О симметрических и функциональных ограничениях для алгоритмов классификации // Докл. АН СССР. 1987. - Т.297. - №1. — С.43—46.

62. Р872. Рудаков КВ. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов // Кибернетика. 1987. - №2. — С.30-35.

63. Р873. Рудаков КВ. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. — 1987. -№3.-С.106-109.

64. Р874. Рудаков КВ. Симметрические и функциональные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. - №3. - С.73-77.

65. Р881. Рудаков КВ. О применении универсальных ограничений при исследовании алгоритмов классификации // Кибернетика. 1988. — №1. -С. 1-5.

66. Р89. Рудаков KB: Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1989. — Вып. 1. - С.176—201.

67. Р92. Рудаков КВ. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: Дис. . докт. физ.-матем. наук. / ВЦ РАН. М., 1992. - 144 с.I

68. Р95. Рудаков КВ. Монотонные и унимодальные корректирующие операции для алгоритмов распознавания // Математические методы распознавания образов—VII: Тез. Докл. -М.: 1995.

69. РВ99. Рудаков КВ., Воронцов КВ. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Докл. РАН. 1999. - Т.367. - №3. - С.314-317.

70. РЧОЗ. Рудаков КВ., Чехович Ю.В. Алгебраический подход к проблеме синтеза обучаемых алгоритмов выделения трендов // Докл. РАН. 2003. - Т.388. — №1. — С.33-36.

71. Рз76. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк // Ж. вычисл. матем. и матем. физ. 1976. - Т. 16. — №6. - С. 1559-1570.

72. Рз88. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1988. - Вып. 1. - С.229-279.

73. С77. Сачков В.Н. Комбинаторные методы дискретной математики. М.: Наука, 1977. - 320 с.

74. Ср01. Середин О. С. Методы и алгоритмы беспризнакового распознавания образов: Дис. . канд. физ.-матем. наук. / ТулГУ, ВЦ РАН. М., 2001. — 142 с.

75. Т88. Татт У. Теория графов. М.: Мир, 1988. - 424 с.

76. ТГ78. ТуДж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

77. У77. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. - 208 с.

78. Х63. Халмош П. Конечномерные векторные пространства. М.: Физматгиз, 1963.-264 с.

79. Черников С.Н. Линейные неравенства. М. Наука, 1968. - 488 с.

80. Я01. Яблонский С.В. Введение в дискретную математику: Учебное пособие для вузов. / Под ред. В.А. Садовничего. 3-е изд., стер. - М.: Высш.шк.; 2001.-384 с.

81. As80. AssouadP. Caracte'risations de sous-espaces norme's de L\ de dimension finie // Se'minaire d'Analyse Fonctionnelle. — Ecole Polytechnique Palaiseau, 1979-1980.-№19.

82. Av77. Avis D. Some Polyhedral Cones Related to Metric Spaces: PhD thesis / Stanford University, 1977.

83. Bx91. Baxter B.J.C. Conditionally positive functions and/?-Norm distance matrices // Constr. Approx. 1991. - №7. - Pp.427-440.

84. Bh05. BhatiaR. Infinitely Divisible Matrices // Indian Statistical Institute, Delhi Centre, -http://www.isid.ac.in/~statmath/eprints (на 17.11.08).

85. BGV. Boser В., Guy on I., Vapnik V.N. A training algorithm for optimal margin classifiers // Fifth Annual Workshop on Computational Learning Theory. — San Mateo, С A: Morgan Kauftnann, 1992. Ppi 144-152.

86. BP93. Braess D., Pinkus A. Interpolation by ridge functions // J. Approx. Theory. -V.73. — 1993. Pp.218-236.

87. BG04. Breitenbach M., Grudic G.Z. Clustering with Local and Global Consistency // Technical Report CU-CS-973-04. 2004. - http://www.cs.colorado.edu/ department/publications/reports/greggrudic.html (на 20.01.09).

88. Bur. Burges C.J.C. A Tutorial on Support Vector Machines for Pattern Recognition I I Data Mining and Knowledge Discoveiy. 1998. - V.2. - №2. - Pp.121167.

89. DD02. Deza M., Dutour M. Data mining for cones of metrics, quasi-metrics, hemi-metrics and super-metrics. // CNRS/ENS Paris, Tokyo: 2002. - http:// arxiv.org/pdf/math/0201011 (на 17.11.08).

90. DS51. Diliberto S.P., Straus E.G. On the approximation of a function of several variable by the sum of functions of fewer variables // Pacific J. Math. — 1951.1. — Pp.195-210.

91. DLC. Dyn N., Light W:A., Cheney E. W. Interpolation by piecewise-linear radial basis functions // J. Approx. Theory. 1989. - №59. - Pp.202-223.

92. FS95. Freund Y., Schapire R.E. A decision-theoretic generalization of on-line learning and an application to boosting // European- Conference on Computational Learning'Theory. 1995. — Pp.23-37.

93. GP71. Graham R.L., PollakH.O. On the addressing problem for loop-switching // Bell System Tech. J. 1971. - №50. - Pp.2495-2519.

94. H135. Hall P. On representatives of subsets // J. London Math. Soc. 1935. - V.10.1. Pp.26-30.

95. H98. Haykin S.S. Neural Networks: A Comprehensive Foundation. Prentice-Hall, second edition, 1998. (перевод: Хайкин С. Нейронные сети: полный курс, 2-е издание. — М. Издательский дом «Вильяме», 2006. - 1104'с.)

96. JJ91. Jacobs R.A., Jordan M.I., Nowlan S.J., Hinton G.E. Adaptive mixtures of local experts //Neural Computation. 1991. - №3. - Pp:79-87.

97. Light W.A. The singularity of distance matrices // Multivariate Approximation Theory. Birkhauser-Verlag, 1989. -Pp.233-240.

98. Mi86. Micchelli C.A. Interpolation of scattered data: Distance matrices and conditionally positive definite functions // Constructive Approximation. -1986.-V.2.-Pp. 11-22.

99. OWS90. Osherson D.N., Weinstein S., Stoli M. Modular learning // Computational Neuroscience. Cambridge, MA: MIT Press, 1990. - Pp.3 69-3 77.

100. RS93.Reid L., SunX. Distance matrices and ridge function interpolation // Canadian Journal of Mathematics. 1993. - V.45. -Pp.1313-1323.

101. Sc90. Schapire R.E. The strength of weak learnability // Machine Learning. — 1990. -V.5.-Pp. 197-227.

102. S37. Schoenberg I.J. On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in Hilbert space // Ann. Math. — 1937. — №38: — Pp.787—793.

103. S3 8. Schoenberg I.J. Metric spaces and positive definite functions // Trans. Amer. Math. Soc. 1938. - №44. - Pp:522-536.

104. S3 8a.', Schoenberg I.J. Metric spaces and: completely monotone functions // Ann. Math. 1938. - №39. - Pp.811-841.

105. Sn93. SunX. Solvability of multivariate interpolation by radial or related functions // Journal of Approximation Theory. 1993. - №72. - Pp.252-267.

106. V98. Vapnik V. Statistical Learning Theoiy. Wiley, New York, 1998.

107. Zd65.'Zadeh L.A. Fuzzy sets // Information and Control. 1965. - V.8. - Pp.338353.1. Список работ автора

108. ДООд. Дьяконов А.Г. О выборе системы опорных множеств для эффективной реализации алгоритмов распознавания типа вычисления оценок // Докл. РАН. 2000. - Т.371. - №6. - С.750-7521.

109. ДОО. Дьяконов А.Г. О выборе системы опорных множеств для эффективной реализации алгоритмов распознавания типа вычисления оценок // Ж. вычисл. матем. и матем. физ. 2000. - Т.40. - №7. —

110. С.1104-1118. (перевод: D'yakonov A.G. On the choice of a system of support sets for an efficient implementation of recognition algorithms of the estimate-computing type // Comput. Math. Math. Phys. 2000. - V.40. - №7. -Pp. 1060-1074.)

111. Д05Ь. Дьяконов А.Г. Об одном подходе к решению задач из области BCI // Сборник докладов XII Всероссийской конференции ММРО-12. М.: МАКС Пресс, 2005. - С.95-97.

112. ДОбт. Дьяконов А.Г. Графовые и матричные критерии корректности алгоритмов распознавания образов // Труды VII международной конференции «Дискретные модели в теории управляющих систем», Покровское, 4-6 марта 2006 г. М.: МАКС Пресс, 2006. - С. 114-118.

113. Д06. Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: Учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ им. М.В. Ломоносова, 2006. - 72 с. (ISBN 5-89407-252-2).

114. ДОбк. Дьяконов А.Г. Корректность относительно семейства решающих правил // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции. Симферополь. Крымский научный центр НАН Украины, 2006. - С.77-78.

115. ДОби., Дьяконов А:Г. Корректность относительно семейства решающих правил // Искусственный интеллект. 2006. - №2. — С.61-64.

116. Д07т. Дьяконов А.Г. Анализ кластерных конфигураций в одной проблеме фильтрации спама // Математические методы распознавания- образов: 13"-я Всероссийская конференция: Сборник докладов. — М.: МАКС Пресс, 2007. С.476-478.

117. Д08тYДьяконов А.Г. Исследование алгебраических замыканий алгоритмов распознавания: операторы разметки» // Таврический вестник информатики и математики. 2008. — №1г. — G.199—2031

118. Generalizations // Dokl. Math. 2009. - V.79. - №.2. - Pp. 150-152.)