Авторефераты по всем темам >>
Авторефераты по разное
На правах рукописи
ДЬЯКОНОВ Александр Геннадьевич
Алгебраические замыкания обобщённой модели алгоритмов распознавания, основанных на вычислении оценок
Специальность:
01.01.09 - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание учёной степени доктора физико-математических наук
Москва - 2009
Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.
Научный консультант: академик РАН, доктор физико- математических наук, профессор Журавлёв Юрий Иванович.
Официальные оппоненты: академик РАН, доктор физико- математических наук, профессор Матросов Виктор Леонидович, доктор технических наук, профессор Немирко Анатолий Павлович, доктор физико-математических наук Устинин Михаил Николаевич.
Ведущая организация: Московский физико-технический институт (государственный университет).
Защита диссертации состоится л_______________ 2009 г.
в ____ часов на заседании диссертационного совета Д 002.017.в Учреждении Российской академии наук Вычислительный центр им. А.А. Дородницына РАН по адресу:
119333, г. Москва, ул. Вавилова, д.40.
С диссертацией можно ознакомиться в библиотеке ВЦ РАН.
Автореферат разослан л_______________ 2009 г.
Учёный секретарь диссертационного совета Д 002.017.02, д.ф.-м.н., профессор В.В. Рязанов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В начале 1970х годов Ю.И. Журавлёвым была описана модель алгоритмов вычисления оценок (АВО) для решения задач распознавания. Каждый алгоритм модели являлся суперпозицией распознающего оператора и решающего правила. Распознающий оператор строил матрицу оценок принадлежности контрольных объектов (которые алгоритм должен классифицировать) классам.
Решающее правило на основе этой матрицы классифицировало контрольные объекты. В АВО были отражены многие эвристические методы, применявшиеся при решении прикладных задач, и модель стала весьма универсальным языком описания алгоритмов распознавания.
В конце 1970х годов Ю.И. Журавлёвым был предложен алгебраический подход к решению задач распознавания: корректный алгоритм (который не делает ошибок на контрольный выборке) было предложено искать в виде алгебраического выражения над некорректными (эвристическими) алгоритмами. Над распознающими операторами были введены операции сложения, умножения на константу и умножения как операции над матрицами оценок, которые они получают (умножение проводилось поэлементно). При фиксированном решающем правиле эти операции индуцировали операции над алгоритмами распознавания. Множество всех полиномов степени не выше k над алгоритмами некоторой модели было названо алгебраическим замыканием k-й степени этой модели (при k = 1 - линейным замыканием). Для модели кусочно-линейных решающих поверхностей и АВО было доказано, что существует и в явном виде выписывается корректный алгоритм-полином над некорректными алгоритмами. Основное достижение алгебраического подхода - строгое доказательство чисто алгебраическими методами того, что в теории распознавания возможно построение хороших алгоритмов на базе плохих. Позже в рамках алгебраического подхода К.В. Рудакову удалось создать язык для описания и исследования задач преобразования информации - теорию локальных и универсальных ограничений.
Исследования модели АВО, в основном, были сконцентрированы на оптимизации алгоритмов и алгебраических выражений над ними. Строились корректные алгоритмы из алгебраических замыканий, но не изучалось множество всех алгоритмов, т.е.
упускался важный объект исследования: алгебраические замыкания.
До настоящего времени они не были даже достаточно детально описаны, чтобы анализировать, есть ли в них хорошие алгоритмы, как их синтезировать и т.д. Технику анализа алгебраических конструкций в рамках классической теории удалось построить В.Л. Матросову для решения фундаментальной задачи о теоретическом обосновании надёжности алгоритмических построений в алгебраическом подходе. С её помощью удалось решить несколько важных проблем, связанных с корректностью алгебраических замыканий (возможностью получить операторами замыкания произвольную матрицу оценок в рассматриваемой задаче распознавания). Эти результаты поставили, в определённом смысле, более сложные проблемы: нахождения наглядных критериев корректности, получения пониженных оценок степени корректного алгебраического замыкания, описания всех задач, разрешимых алгоритмами из алгебраического замыкания конечной степени.
Поэтому актуальным было проведение исследований, с помощью которых будут эффективно описаны алгебраические замыкания и решены перечисленные выше проблемы.
Цель работы - разработка теории, позволяющей детально описать и исследовать алгебраические замыкания модели алгоритмов распознавания, основанных на вычислении оценок, в том числе для описания всех задач, разрешимых алгоритмами из алгебраического замыкания конечной степени, и получения неулучшаемых оценок степени корректного замыкания, как меры сложности алгебраических конструкций.
На защиту выносятся следующие результаты, полученные для введённой в работе обобщённой модели АВО (справедливые и для классической модели):
1. Предложена теория систем эквивалентностей для описания и исследования алгебраических замыканий конечных степеней. Каждой задаче распознавания сопостовляется система эквивалентностей, по которой строятся характеристическая матрица и матрица попарных l1-расстояний, в терминах которых описываются алгебраические замыкания модели. Переходу к алгебраическому замыканию фиксированной степени при этом соответствуют специальные преобразования матриц.
2. Получены новые критерии корректности алгебраического замыкания конечной степени и критерии разрешимости задач алгоритмами из этого замыкания. Критерии позволяют описывать разделяющие поверхности алгоритмов алгебраических замыканий в пространстве контрольных объектов. Найдены новые семейства корректных полиномов.
3. Получена неулучшаемая в общем случае оценка степени корректного алгебраического замыкания модели АВО. Для важных частных случаев получены пониженные оценки (например, для задачи распознавания с непересекающимися классами и подмоделей модели АВО).
4. Исследовано пополнение линейного замыкания множества полиномов ограниченной степени над АВО операциями нормировки и деления. Нормировка рассмотрена при различных способах её определения: по сумме, максимуму, отрезку. Получены формулы для размерности соответствующих замыканий и критерии корректности. Показана представимость замыканий в стандартной форме (в алгебраических выражениях нет вложений новых операций).
5. Исследовано понятие корректности модели относительно семейства решающих правил. Получены общие критерии реализации классификации алгоритмом из линейного замыкания произвольной модели с решающим правилом, на которое накладываются требования частичной монотонности. Рассмотрены специальные требования: построчная монотонность, постолбцовая монотонность, реализация классификаций из заданного множества. Показано, что последнее требование следует накладывать в задаче с непересекающимися классами.
6. Исследована k-сингулярность конечной системы точек (неполнота размерности пространства значений полиномов ограниченной степени над столбцами матрицы попарных l1расстояний этой системы). Полностью описаны все k-сингулярные системы. Найдены новые критерии вырожденности матрицы попарных l1-расстояний конечной системы точек.
Научная новизна. Все результаты (1) - (6) являются новыми.
Теория (1) является обобщением техник К.В. Рудакова и В.Л. Матросова. В диссертации впервые получены метрические критерии корректности и разрешимости (2), которые, в отличие от критериев В.Л. Матросова (1981 г.), допускают простую геометрическую интерпретацию в терминах исходной задачи. Впервые (более чем за 20 лет с момента постановки) полностью решена проблема описания всех задач, для которых некорректно алгебраическое замыкание фиксированной степени. Примеры таких задач (без описания всего множества) были найдены В.Л. Матросовым (1981 г.) и Т.В. Плохониной (1985 г.). Результаты (1) - (2) позволили продемонстрировать связь алгебраических замыканий АВО с некоторыми современными моделями (SVM, линейной регрессией и т.д.). Впервые доказано, что классические полиномы Ю.И. Журавлёва образуют базис в алгебраическом замыкании конечной степени. Оценки степени корректного алгебраического замыкания были получены многими авторами (Ю.И. Журавлёвым - 1977 г., В.Л. Матросовым - 1985 г., Т.Н. Плохониной - 1987 г.). К.В. Рудаков получил неулучшаемую оценку для одной модели, содержащей все алгоритмы АВО (1989 г.).
В диссертации впервые (более чем за 25 лет исследований) получена неулучшаемая оценка для модели АВО, зависящая от числа классов и длины контрольной выборки (3). Операции нормировки и деления (4) до настоящего времени не исследовались. Впервые найдены лестественные операции, которые значительно упрощают критерии корректности, не делая их вырожденными. Исследования корректности относительно семейства решающих правил (5) ранее не проводились. Впервые обосновано понятие корректность модели и выделен класс задач, в которых необходимо использовать неклассические понятия корректности. Постановка задачи о kсингулярности (6) является обобщением проблемы теории интерполяции о критерии вырожденности матрицы попарных l1расстояний. Проблема вытекает из серии работ И. Шёнберга (I.J. Schoenberg, 1937 - 1938 гг.), но впервые решена только в 1993 г.
. Рейдом (L. Reid) и З. Саном (X. Sun). В диссертации не только получены новые критерии, но и решены смежные задачи, связанные с приложениями в алгебраическом подходе к распознаванию.
В работе впервые рассмотрено обобщение модели АВО на случай произвольного способа задания объектов, впервые исследована модель с обобщением Ю.И. Журавлёва и А.А. Докукина (связанным с учётом удалённости классифицируемого объекта от объектов рассматриваемого класса и близости к объектам других классов).
Методика исследования: методы алгебраического подхода к решению задач распознавания, теории булевых функций, теории систем линейных неравенств, комбинаторики, теории графов, линейной алгебры, теории метрик и разрезов.
Практическая ценность. Работа носит теоретический характер.
Для иллюстрации возможных практических применений в третьей части приложения описаны прикладные задачи, при решении которых использовались результаты диссертации. Разработанный автором алгоритм классификации сигналов занял первое место (из 20) на Международном соревновании Ford>
Апробация работы. Основные результаты работы и отдельные её части докладывались на научном семинаре кафедры математических методов прогнозирования факультета ВМК МГУ (2009 г.);
научном семинаре Алгебрологические методы в задачах классификации и прогнозирования (МГУ, ВМК, 1999 - 2000, 2003 - 2009 гг.);
научном семинаре Дискретный анализ (МГУ, ВМК, 2003 г.);
научном семинаре Дискретная математика и математическая кибернетика (МГУ, ВМК, 2008 г.); Ломоносовских чтениях (МГУ, ВМК, 2008 - 2009 г.); Международных научных конференциях Интеллектуализация обработки информации - 2000, 2006, 2008 (Симферополь, Крымский НЦ НАН Украины, ТНУ) [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 части).
Используется тройная нумерация теорем, лемм, формул, примеров и рисунков: через точку указывается номер главы, номер параграфа и порядковый номер в этом параграфе. Основной текст занимает 2страниц, приложение - 34 страницы.
СОДЕРЖАНИЕ РАБОТЫ
Во введении дана общая характеристика работы, обоснована актуальность, определено направление исследований, даны обзоры исследований по теме диссертации и основных результатов.
В з0 представлены обозначения, используемые в работе:
1 = (1,Е,1)т, 0 = (0,Е,0)т, ei = (0,Е,0,1,0,Е,0)т (i -я координата равна единице), E - матрица, состоящая из одних единиц, col(H ) - ab множество столбцов матрицы H, X - множество матриц размера a b с элементами из множества X, || hij ||ab - матрица размера a b с элементами hij, i {1,2,Е,a}, j {1,2,Е,b}, Цнаибольшее целое x число, не превосходящее числа x, rg(X ) - максимальное число линейно независимых векторов во множестве X (над полем Q ), k 2X = {Y | Y X }, CX = {Y 2X | |Y |= k}, QL = {1,2,Е,q}{1,2,Е,l}, Ind() = {i {1,2,Е,l} | i 0} и ()i = i для вектора = (1,Е,l )т, mat(X ) = [x1Еxr ] для множества векторов X = {x1,Е, xr}: | X |= r, L(X ) - пространство векторов ортогональных ко всем векторам множества X, F(|| hij ||ab) =|| F(hij ) ||ab для преобразования F : Q Q, {xi}i{i,Е,ir } = {xi,Е, xi }, (xi )i{i,Е,ir } = (xi,Е, xi ) (иногда вместо {xi}iI 11 r 11 r пишем {xi}i, не указывая явно множество I, если оно очевидно).
В главе 1 введены основные понятия, определён главный объект исследований - алгебраические замыкания, изложены начала теории систем эквивалентностей. В з1.1 поставлена обобщённая задача распознавания (при произвольном способе задания объектов) и описана модель алгоритмов для её решения. Множество допустимых объектов M содержит объединение множеств Kj, j {1,2,Е,l}, называемых классами. Каждому объекту S M соот ветствует бинарный вектор классификации (S) = (1(S),Е,l (S)), где j(S) - значение предиката S Kj , j {1,2,Е,l}. Для каждой пары (St,Si ) M M можно вычислить значения функций (St, Si )Z, Z, Z - конечное множество параметров, Z - частично упорядоченное множество. Функция играет ту же роль, что и расстояние в классической постановке. Задача распознавания состоит в том, чтобы построить алгоритм A, который по набору m Sm = {St}t=1 эталонных объектов с известными векторами q (S1),Е,(Sm) для набора Sq = {St}t=1 контрольных объектов строит их векторы классификаций - классифицирует (распознаёт).
Алгоритм обобщённой модели вычисления оценок является суперпозицией распознающего оператора (РО) B и решающего правила (РП) C : A = B C. Для объектов из Sq РО B получает матрицу [B] =|| ij[B] ||ql, ij-й элемент которой - оценка принадлежности объекта Si к классу K - j 1, e ij[B] = xab( j) wtw(),b(St,Si ), a,b=0,0 A StKa j где wt Q+ = {x Q | x 0} при t {1,2,Е,m} (вес t -го объекта), e w()Q+ при A (вес учёта -й близости), e Z, ,b(St, Si ) - функция близости такая, что Sm Kj, a = 1, 1, (St, Si ) e, e e ,1(St, Si ) = 1- ,0(St, Si ) = 0, (St, Si ) e, Ka = j / Sm \ Kj, a = 0.
Пока считаем, что A = Z. Далее в работе рассматриваем модель АВО с параметрами xab = xab( j){0,(-1)a+b} для всех j {1,2,Е,l}, a {0,1}, b{0,1} (модель без нормировок). РП по матрице оценок классифицирует объекты. Простейшее РП - пороговое правило Cс,c2 :
1, , ij c2, Cc,c2 (|| ij[B] ||ql ) =||ij ||ql, (i, j)QL ij = с1 ij < c2, 0, ij < c1, с1 Q, с2 Q, с1 с2. Символ обозначает отказ от классификации.
При с1 = c2 = c получаем полное пороговое РП Cc с порогом c.
Выше определены задача и модель в канонической форме. В форме с семейством порогов рассматриваются частично упорядочен ные множества , функции : M M и пороги e , Z. Рассмотрим задачу распознавания в стандартной постановке, когда допустимые объекты задаются признаковым описанием S = ( f1(S),Е, fn(S)) M1 Е Mn, Mi - метрическое пространство с метрикой pi. Простое сведение этой задачи к задаче с семейством порогов: Z = {1,2,Е,n}, (St, Si ) = p( f(St ), f(Si )), = [0,+).
Соответствующая модель при A =Z называется моделью АВО с системой (всех) одноэлементных опорных множеств. В более общем Z случае выбирается множество A 2 \ {} - система опорных множеств (СОМ), а функция описывает различие объектов на подмножестве множества признаков.
В з1.2 определена алгебра над алгоритмами, введённая Ю.И. Журавлёвым. Следующие операции над РО индуцируют соответствующие операции над алгоритмами при фиксированном РП:
[B1 + B2] = [B1] + [B2], [cB] = c[B], [B1 B2] = [B1] [B2].
Символ используем для обозначения адамарова (поэлементного) умножения. Для произвольного множества X векторов линейного пространства над полем Q с ассоциативной операцией умножения вводим понятия: линейного замыкания L(X ) = {c1x1 +Е+ crxr | r {1,2,Е}, c1,Е,cr Q, x1,Е, xr X}, алгебраического замыкания k -й степени Uk (X ) = L({x1 Е xs | x1,Е, xs X, 1 s k}), k алгебраического замыкания U(X ) = U (X ).
k =Для матрицы H выражение Uk (H ) означает Uk (col(H )), аналогично для L(H ) и U(H ) (далее все обозначения вводим только для Uk () ).
Считаем, что U0(X ) = L({1}) - множество, состоящее из векторов, у которых все координаты равны. Множества алгоритмов (операторов) будем также называть моделями алгоритмов (операторов).
Большинство определений, введённых для множества операторов АВО, естественным образом переносится на саму модель АВО (множество алгоритмов).
Определение. Оператор D,t,a,e, который получает ненулевую матрицу оценок [D,t,a,e ]: ij[D,t,a,e ] = I[j(St ) = a] I[(St, Si ) = e], (i, j)QL, называется оператором разметки. Здесь и далее I[ ] = 1, если выполняется условие , I[ ] = 0 - в противном случае.
Теорема 1.2.1. Если B* - множество операторов обобщённой модели АВО, D* = {D,t,a,e},t,a,e, тогда Uk (B*) = Uk (D*).
В з1.3 получены результаты для систем эквивалентностей, заданных на множестве X = {1,2,Е,q} с естественным порядком, которые в дальнейшем существенно используются при анализе алгебраических замыканий.
Определение. Множеством характеристических векторов классов эквивалентности ~ называется такое множество бинарных ненулевых q -мерных векторов (~), что (i, j) X X i ~ j !(x1,Е, xq)т (~) : xi = xj = 1.
m Определение. Система {~t}t=1 эквивалентностей называется регулярной, если (i, j) X X [i = j t {1,2,Е,m} i ~t j].
m m m m Пусть ({~t}t=1) = (~ ), Uk ({~t}t=1) = Uk (({~t}t=1)).
t t=m Определение. Конъюнкцией системы эквивалентностей {~t}t=k m степени k, k m, называется система &[{~t}t=1]={~t,Е,tk }(t,Е,tk )C{1,2,Е,m} :
k (i, j) X X [i ~t,Е,tk j (i ~t j) &Е& (i ~t j) ], 1 1 k m m 0 m &k[{~t}t=1] = &m[{~t}t=1] при k > m, &[{~t}t=1] = {}: () = {1}.
m m Лемма 1.3.1. Uk ({~t}t=1) = L(&k[{~t}t=1]).
m Определение. Произведением системы {~t;1}t=1 эквивалентm ностей, заданных на множестве Q, и системы {~t;2}t=1 эквивалентm ностей, заданных на множестве Q, называется система {~t}t=1 эквивалентностей, заданных на множестве Q1 Q2, такая, что для всех t {1,2,Е,m}, (i, j)Q1 Q2, (a,b)Q1 Q(i, j) ~t (a,b) (i ~t;1 a) & ( j ~t;2 b).
m Произведение {~t}t=1 регулярно тогда и только тогда, когда реm m k m гулярны системы {~t;1}t=1, {~t;2}t=1 (лемма 1.3.4), а система &[{~t}t=1] km является произведением систем эквивалентностей &[{~t;1}t=1] и km &[{~t;2}t=1] (лемма 1.3.5).
В з1.4 описаны свойства операций внешнего и покоординатного произведений (здесь не приводятся). X Y = {x yт | x X, y Y}, где X Qq, Y Ql ; X Y = {x y | x X, y Y}, где X Y Qq (здесь для произвольных фиксированных q и l ).
В з1.5 описаны матрицы оценок операторов из алгебраических L замыканий. Пусть ,t = (~Q ), t = (~,t ) при t {1,2,Е,m}, ,t L A, где ~Q и ~,t - эквивалентности соответственно на ,t множествах {1,2,Е,q} и {1,2,Е,l} такие, что L i ~Q j (St, Si ) = (St, Sj ), i ~,t j i(St ) = (St ).
,t j L L Для эквивалентности ~,t используем также символ ~t (она не зависит от A). Пусть *,k = {[B] | B Uk (B*)}.
Лемма 1.5.1. Множество матриц *,1 является линейным замыканием множества m (1.5.1) (,t t ).
t=1 A Множество (1.5.1) состоит из характеристических векторов (представленных в матричной форме) классов эквивалентностей L произведения {~,t},t систем {~Q },t и {~,t},t. Переход к Uk (B*) со,t k ответствует переходу к &[{~,t},t ] (см. леммы 1.3.5, 1.3.1), поэтому *,k описывается аналогично (при более сложно устроенных t ):
m t (1.5.2) ( t ).
t=Определение. Задача распознавания называется регулярной, 1 если выполняются условия: 1. |{K1,Е, Kl }|= l (регулярность системы L m q эквивалентностей {~,t},t ). 2. |{(((St, Si )) )t=1}i=1 |= q (регулярA ность системы эквивалентностей {~Q },t ). 3. Sm Sq =.
,t Определение. Модель РО R* называется корректной (относительно задачи распознавания), если Qql B R*: [B] = .
В противном случае модель называется некорректной.
Определение корректности (и последующих обобщений этого понятия) вводится для конкретной задачи: при заданных (St ) и (St, Si ), St Sm, Si Sq, Z. Из простых свойств отношений эквивалентностей и матриц операторов разметки в виде критерия получаем центральный результат алгебраического подхода к распознаванию лалгебраическое замыкание U(B*) является корректным над множеством регулярных задач (теорема Ю.И. Журавлёва):
Теорема 1.5.1. Модель U(B*) корректна тогда и только тогда, когда выполнены первое и второе условия регулярности.
В главе 2 получены критерии корректности алгебраических замыканий и разрешимости задач с помощью алгоритмов из этих m замыканий. В зз2.1 - 2.3 продолжено изучение системы {~t}t=1 (см.
з1.3). По ней можно построить характеристическую матрицу m char({~t}t=1) =|| hij ||qq : hij = hji =|{t {1,2,Е,m} | i ~t j}|, m (i, j){1,2,Е,q}2, нумерующую матрицу num({~t}t=1) =|| xit ||qm :
t {1,2,Е,m} (i1,i2){1,2,Е,q}2 i1 ~t i2 xi t = xi t.
1 В терминах этих матриц просто записываются критерии регулярности (леммы 2.1.2 - 2.1.3). При формулировках результатов используются семейства функций Fk, k {1,2,Е}, подробно изученнные в конце з2.2. Передставителями семейства Fk являются, в частности, функции Fk (x) = ak fk (x) +Е + a1 f1(x) + a0, ak -1,Е,a1,a0 0, ak > 0, где fr(x) = x(x -1) Е(x - r +1). Например, xk Fk.
m Теорема 2.1.1. Пусть H = char({~t}t=1), Fk Fk при k {1,2,Е}, m тогда справедливо равенство L(Fk (H )) = Uk ({~t}t=1).
m Полуметрику H (i, j) = m - hij : H =|| hij ||qq = char({~t}t=1) на множестве {1,2,Е,q} назовём полуметрикой системы эквивалентностей m {~t}t=1. Из леммы 2.2.1 вытекает корректность определения и то, что функция H (i, j) является метрикой тогда и только тогда, когда система эквивалентностей регулярна.
m Теорема 2.2.2. Пусть {~t}t=1 - регулярная система эквивалентностей, q > 1, Fk Fk, k {1,2,Е}, тогда матрица m Pk = E - Fk (char({~t}t=1)) Fk (m) является матрицей метрики (q q -матрицей попарных расстояний m в некоторой метрике на {1,2,Е,q}2 ), причём L(Pk ) = Uk ({~t}t=1).
Теорема 2.2.3 - лемма 2.2.4. Пусть для всех натуральных k множество функций Fk обладает тем свойством, что F Fk тогда и только тогда, когда для произвольной системы эквивалентностей m m {~t}t=1 выполняется равенство F(char({~t}t=1)) = char({~s}s ) для некоm торой системы эквивалентностей {~s}s : L({~s}s ) = Uk ({~t}t=1). Тогда 1 если F(x)Fk, G(x)Fk, a {1,2,Е}, то 1 1 F(x) + G(x)Fmax[k,k2 ], F(x) G(x)Fk +k2, a F(x)Fk.
В з2.3 результаты зз2.1 - 2.2 представлены для обобщённой m характеристической матрицы H =|| hij ||qq системы {~t}t=1:
(i, j){1,2,Е,q}2 hij = ct, c1,Е,cm > 0.
t{1,2,Е,m}: i~t j m Равенство L(Fk (H )) = Uk ({~t}t=1) справедливо при Fk = ak xk +Е+ a1x + a0, ak > 0, ak -1,Е,a0 0.
Разрезный конус CUTq является множеством l1-полуметрик на всевозможных q -точечных множествах пространств Rr, r {1,2,Е}.
m Теорема 2.3.1. Для регулярной системы {~t}t=1 функция k сt k : {1,2,Е,q}2 [0,1], k (i, j) = 1-t: i~t j m , c t t=1 c1,Е,cm > 0, является метрикой из конуса CUTq, для которой m справедливо равенство Uk ({~t}t=1) = L(P) при q > 1, P =|| k (i, j) ||qq.
В з2.4 получены критерии корректности и разрешимости в общем случае. Пусть оператор разметки B,t,(i, j) такой, что [B,t,(i, j)] = = т, = (1,Е,q)т ,t, = (1,Е,l )т t, i = 1, = 1. Пусть j m B(i, j) = B,t,(i, j).
t=1 A Считаем, что F(B) = akBk +Е+ a1B + a0BE при F(x) = ak xk +Е+ a1x + +a0, где [BE ] = E (очевидно, что BE L(B*) ). Классификацией (q объектов по l классам) будем называть бинарную матрицу размера q l, а также любое выражение, которое определяет значения некоторых её элементов. Следующая теорема обобщает результат Ю.И. Журавлёва о реализации произвольной классификации в регулярной задаче с помощью алгоритмов вида c(a,b)B(k. (2.4.1) a,b) (a,b)QL Теорема 2.4.1. При Fk Fk, k {1,2,Е}, справедливо равенство L({Fk (B(i, j))}(i, j)QL) = Uk (B*).
Следствие. Если матрица оценок может быть получена оператором из Uk (B*), то она может быть получена оператором вида c(a,b)Fk (B(a,b)) при Fk Fk, в частности, оператором вида (2.4.1).
(a,b)QL Зафиксируем на множестве QL лексикографический порядок и в соответствии с ним выпишем матрицу Hk размера ql ql, в которой ((i, j),(a,b)) -й элемент равен числу Fk (ij[B(a,b)]).
Теорема 2.4.2. Алгебраическое замыкание Uk (B*) корректно тогда и только тогда, когда det(Hk ) 0.
Теорема 2.4.3. Алгоритм из {B Cc | B Uk (B*)}, c Q, реализует классификацию ||ij ||ql{0,1}ql тогда и только тогда, когда совместна система неравенств (относительно x11,Е, xql ) hk x11 +Е+ h(k xql > 0, (i, j) I1, i, j),(1,1) i, j),(q,l ) h(k x11 +Е + h(k xql < 0, (i, j) I0, (i, j),(1,1) i, j),(q,l ) h(k = Fk (ij[B(a,b)]), Fk Fk, I = {(i, j)QL | ij = }, {0,1}.
i, j),(a,b) Теорема 2.4.4. Пусть в регулярной задаче распознавания ql > 1, тогда функция k : QL QL [0,1], k ((i, j),(a,b)) = k |{(,t) | ((St, Si ) = (St,Sa )) & (j(St ) = b(St ))}| = 1-, m | A | является метрикой из CUTql, для которой Uk (B*) = L({P(a,b)}(a,b)QL) при ij[P(a,b)] = k ((i, j),(a,b)), (i, j)QL, и для которой определитель ql ql -матрицы метрики отличен от нуля тогда и только тогда, когда замыкание Uk (B*) корректно.
Лемма 2.4.1. Для любой метрики из конуса CUTq, q > 1, существует задача распознавания с одним классом, в которой *,1 = L(P), где P - матрица метрики .
В з2.5 подробно рассмотрена задача распознавания с двумя непересекающимися классами: (S){(1,0)т,(0,1)т} при S М. Пусть Oqq - нулевая матрица размера q q. Из леммы 2.5.1 и равенства char(&k[{~Q },t ]) Oqq ,t char(&k[{~,t},t ]) = Oqq char(&k[{~Q },t ]) ,t следует, что такая задача сводится к задаче с одним классом (в каждом векторе классификации удаляется вторая координата). Изучение алгебраических замыканий сводится к изучению регулярных систем эквивалентностей и метрик, заданных на множестве контрольных объектов (поскольку эквивалентность на множестве {1,2,Е,q} инду цирует эквивалентность на Sq ).
Лемма 2.5.1. В задаче распознавания с двумя непересекающимися классами для множеств I1, I2 : I1 I2 {1,2,Е,q} и классификации л Si K1 \ K2 при i I1, Si K2 \ K1 при i I2 () следующие утверждения эквивалентны:
1. A{B Cc | B Uk (B*), c Q}: A реализует классификацию ().
2. A{B Cmax | B Uk (B*)}: A реализует классификацию (), где Сmax(||ij ||ql ) =||ij ||ql : (i, j)QL ij = 1 ij = max[i1,i2].
3. B Uk (B*) : i I1 j I2 i1[B] >j1[B].
Теорема 2.5.1. В регулярной задаче распознавания с двумя непересекающимися классами и q контрольными объектами 1. Существуют операторы B1,Е, Bq L(B*) такие, что любую классификацию объектов Sq можно получить алгоритмом вида q k Сmax log2 q. (2.5.2) cB , k i i i= 2. Если некоторая классификация (), I1 I2 {1,2,Е,q}, мо жет быть получена алгоритмом из {B Cmax | B Uk (B*)}, тогда её можно получить алгоритмом вида (2.5.2).
3. Классификация (), I1 I2 {1,2,Е,q}, реализуется алгоритмом из {B C0 | B Uk (B*)} тогда и только тогда, когда совместна система неравенств hk x1 +Е + hik xq > 0, i I1, 1 q hik x1 +Е+ hik xq < 0, i I2, i1 q k hij =|{(,t) | i ~Q j}|k, i {1,2,Е,q}, j {1,2,Е,q}.
,t Теорема 2.5.2. Линейное замыкание L(B*) в задаче с двумя классами корректно тогда и только тогда, когда оно корректно в задаче (с непересекающимися классами), которая получается из начальной удалением эталонных объектов, одновременно содержащихся в обоих классах. Для замыкания Uk (B*) теорема неверна.
В главе 3 найдены оценки степени корректного алгебраического замыкания. В з3.1 описана модель АВО с СОМ (см. с. 12) и общей Z функцией близости. Пусть Z = {1,2,Е,n}, A 2 \ {} (СОМ), |{ | (St,Si ) e}| q1, e1 n ,Е,e ; q1,q2 (St, Si ) = 1 |{ | (St, Si ) e}| q2, / A, q1 {0,1,Е,n}, q2 {0,1,Е,n}, e при Z. Частные e1 n e1 n случаи такой функции близости: ,Е,e ; q1 (St,Si ) = ,Е,e ; q1,n(St, Si ), e1 n e1 n ,Е,e (St, Si) = ,Е,e ; ||,n(St, Si ). (3.1.2) Модель АВО (множество её операторов) с произвольными СОМ и функцией близости вида будем обозначать через B*().
e1 n e1 n e1 n Лемма 3.1.2. L(B*(,Е,e ; q1,q2 )) = L(B*(,Е,e ; q1 )) = L(B*(,Е,e )).
e1 n Теорема 3.1.1. Линейное замыкание L(B*(,Е,e ; q1,q2 )) совпадает с линейным замыканием модели АВО с СОМ A = {{1,2,Е,n}} и функцией близости вида (3.1.2).
Пусть ~Q - эквивалентность на множестве {1,2,Е,q}:
t i ~Q j {1,2,Е,n} (St, Si ) = (St,Sj ).
t e1 n Лемма 3.1.3. Множество матриц оценок модели L(B*(,Е,e ; q1,q2 )) является линейным замыканием множества (1.5.2), где t = (~Q ), t t = {(St ),1 -(St )} \ {0}, t {1,2,Е,m}.
Множество ненулевых бинарных векторов одинаковой размер ности, сумма которых равна вектору 1, называется 1D -множеством.
m Теоремы 3.1.2 - 3.1.3. Пусть {t}t=1 - семейство 1D -множеств q-мерных векторов, тогда в пространстве M = M1 Е Mn {a,b,c}n, : (a, a) < (a, c), (b, a) = (b, c), {1,2,Е,n}, существует задача распознавания с n признаками, в которой (~Q ) =t для всех t {1,2,Е,m}. Для любого набора 1,Е,m t бинарных l -мерных векторов существует задача распознавания с признаковым пространством M = Qn, признаковыми метриками (x, y) =| x - y |, {1,2,Е,n}, в которой множество матриц оце e1 n нок линейного замыкания L(B*(,Е,e ; q1,q2 )) совпадает с линейным замыканием множества (1.5.2) при t = {t,1 -t}.
В з3.2 получена неулучшаемая оценка степени корректного замыкания: в регулярной задаче распознавания существует k q + l, для которого модель Uk (B*) корректна.
log2 log Теорема 3.2.1. Модель U(B*) корректна тогда и только тогда, когда корректна модель Uk (B*), где k q + l.
log2 log Теорема 3.2.2. Для любых натуральных параметров q и l, q + l > 2, существует регулярная задача, в которой модель Uk (B*) некорректна при k < q + l (неулучшаемость оценки).
log2 log Определение. Матрица || lij ||ql называется ЛЗ-матрицей модели (множества операторов) R*, если R R* ij[R]lij = 0.
(i, j)QL В з3.3 получена неулучшаемая оценка степени корректного алгебраического замыкания в задаче распознавания с непересекающиm мися классами, т.е. при l 2 и {(St )}t=1 {ej}l (решается в j= предположении, что S M (S){ej}l ). Переход L(B*) Uk (B*) j=соответствует преобразованию (которое может быть проинтерпретировано как введение виртуальных эталонов в нашу задачу) j k = (j Uk -1()), где j =t, поскольку справедливы j t: (St )=ej Теоремы 3.3.2 - 3.3.3. В задаче с l непересекающимися классами множество *,k совпадает с множествами l l kk k L () 1) (U ( {ej}), L( {ej,1 - ej}).
j j j=1 j= Теоремы 3.3.1, 3.3.4. В задаче с l непересекающимися классами модель U(B*) корректна тогда и только тогда, когда корректна модель Uk (B*), где k max[log2 q,1] при l = 2 и k q +1 при logl > 2. Оценки являются неулучшаемыми.
В з3.4 рассмотрена задача распознавания в стандартной постановке при M1 =Е = Mn = Q, pr(x, y) =| x - y | при r {1,2,Е,n}, и модель АВО с системой всех одноэлементных опорных множеств.
Такая задача называется задачей с разнесёнными эталонами, если m r {1,2,Е,n} {(St )}t=1 t1 T (): t2 T () : fr(St ) fr(St ), где T () = {t {1,2,Е,m} | ((St ) = ) ((St ) = 1 -)}.
Теорема 3.4.1. В задаче с разнесёнными эталонами второе усло вие регулярности выполняется тогда и только тогда, когда | Sq |= q.
Теорема 3.4.2. В задаче с разнесёнными эталонами множество матриц оценок *,k алгебраического замыкания k -й степени модели АВО с системой всех одноэлементных опорных множеств есть n L Uk (~ ) Uk (), {r} r=1 где эквивалентности ~{r} такие, что num({~{r}}n ) =|| f (Si ) ||qn.
r=1 j В рассматриваемой задаче добавление новых эталонных объектов не оказывает влияние на корректность алгебраических замыканий e1 n исследуемой модели. Отметим, что, модель L(B*(,Е,e ; q1,q2 )), например, можно сделать корректной, добавив эталонные объекты в задачу.
Теорема 3.4.3. Для любых непустых множеств {0,1}q и {0,1}q существует задача распознавания с разнесёнными эталонами, в которой множество матриц оценок операторов линейного замыкания модели АВО с системой всех одноэлементных опорных множеств совпадает с множеством L(({1}) ( {1})).
Теорема 3.4.4. В регулярной задаче с разнесенными эталонами алгебраическое замыкание k -й степени модели АВО с системой всех одноэлементных опорных множеств корректно при k max[min[n, q], l]. Оценка является неулучшаемой.
log2 log В з3.5 исследованы подмодели B*(xij )(i, j)P модели АВО. В формулах вычисления оценок подмодели B*(xij )(i, j)P параметры xij при (i, j) P равны нулю (остальные могут варьироваться). Очевидно, L(B*(x11, x01, x10, x00)) = L(B*(x11, x01, x10)) = L(B*(x11, x01, x00)) = L(B*(x11, x01)) L(B*(x11, x10)) = L(B*(x11)), L(B*(x11, x10, x00)) = L(B*(x11, x00)).
Лемма 3.5.1. Если выполнено третье условие регулярности и A : (S,S ) M M [(S, S ) (S, S) S = S ] (например, если одна из функций - метрика на M ), тогда L(B*(x11, x00)) = L(D*).
Лемма 3.5.2. BE L(B*(x11, x00)) L(B*(x11, x00)) = L(D*).
Теорема 3.5.1. Пусть в задаче распознавания выполнено первое q условие регулярности и j {1,2,Е,l} |{((St,Si ))S K, A}i=1 |= q t j (второе условие регулярности для B*(x11) ), тогда модель Uk (B*(x11)) корректна при k min (ql +1), q + (l +1) .
log2 log2 log В главе 4 исследовано пополнение линейного замыкания (модели B* или Uk (B*) ) операциями нормировки и деления. Поскольку *,k при любом k {1,2,Е} имеет вид (1.5.2), обозначим это множество q l -матриц через *, считая, что t - 1D -множество q -мерных векторов, t - 1D -множество l -мерных векторов, t {1,2,Е,m} (т.е.
здесь m не обязательно число эталонных объектов). По нашим договорённостям будем также использовать системы эквивалентностей L L {~t}t, {~Q}t, {~t }t (вместо систем {~,t},t, {~Q },t, {~,t},t, см. з3.1).
t ,t Считаем, что выполняются первые два условия регулярности и m m t t = t, 0 =t, 0 = \{1}.
, = , E = t=1 t=t : t ={1} t : t {1} В з4.1 введены обозначения и определения пополненных замыканий множеств матриц, которые индуцируют соответствующие замыкания моделей операторов и алгоритмов.
Определение. Стандартным замыканием относительно операции Op : M* Qql, M* Qql, множества матриц H* называется множество LOpL(H*) = L({Op(H ) | H L(H*) M*} H*). Замыканием относительно операции Op множества матриц H* называется множество UOp(H*) = LOpL(H*) LOpL(LOpL(H*)) Е.
В з4.2 исследована операция нормировки по сумме N :
l ij N(||ij ||ql ) =, , i ql i = is s=определённая на матрицах ||ij ||ql, в которых i {1,2,Е,q} i 0.
Лемма 4.2.2. Пусть = UN(*), тогда = LNL(*) и rg() = q(rg() -1) + rg().
Теорема 4.2.1. Замыкание UN(Uk (B*)) (и LNL(Uk (B*))) корректно тогда и только тогда, когда выполняются равенства L rg((&k[{~Q}t ])) = q, rg((&k[{~t }t ])) = l.
t Теорема 4.2.2. Если замыкание LNL(Uk (B*)) корректно, то замыкание U2k (B*) корректно. В обратную сторону утверждение теоремы, вообще говоря, не выполняется.
В з4.3 исследована операция нормировки по максимуму Nmax :
ij Nmax(||ij ||ql ) =, max[i1,Е,il ] ql определённая на матрицах ||ij ||ql : max[{ij}l ] 0 при i {1,2,Е,q}.
j= Лемма 4.3.1. Пусть max = UNmax(*), тогда max = LNmaxL(*) и rg(max ) = rg() при l = 1, rg(max ) = q rg() при l > 1.
Теорема 4.3.1. Замыкание UNmax (Uk (B*)) (и LNmaxL(Uk (B*))) корректно тогда и только тогда, когда L rg((&k[{~t }t ])) = l, при l > 1, rg((&k [{~Q}t ])) = q, при l = 1.
t В з4.4 исследована операция нормировки по отрезку [0,1] N[0,1]:
ij - min[i1,Е,il ] N[0,1](||ij ||ql ) =, max[i1,Е,il ] - min[i1,Е,il ] ql определённая на матрицах ||ij ||ql, в которых нет строк из одинаковых элементов. Пусть i ~ j, если i -я и j -я строки матрицы mat(0) равны, T = (~), q =|T |, (20 - E) = {2 - 1 | 0}. В теореме 4.4.1 предполагаем, что множества , E, T, , 0 построены для алгебраического замыкания Uk (B*), например =(&k[{~Q}t ]).
t Определение. Задача распознавания называется задачей с чёт ной классификацией, если x col(mat(0)т ) [1 - x col(mat(0)т ) ], в противном случае - задачей с нечётной классификацией.
Теорема 4.4.1. В задаче с нечётной классификацией пространство матриц оценок операторов замыкания UN[0,1](Uk (B*)) есть L((T 0) ({1})), его размерность равна q rg() + rg() - - rg(L() L(T )) = q (rg() -1) + rg(E T ) ; модель UN[0,1](Uk (B*)) корректна тогда и только тогда, когда q = q и rg() = l. В задаче с чётной классификацией пространство матриц оценок операторов замыкания UN[0,1](Uk (B*)) есть L((T (20 - E)) ( {1})), его размерность равна q (rg() -1) + rg() ; модель UN[0,1](Uk (B*)) кор ректна тогда и только тогда, когда rg() = q = q и rg() = l.
В теореме 4.4.2 описан базис пространства, ортогонального к пространству матриц оценок операторов из UN[0,1](Uk (B*)) (не приводится из-за громоздких формулировок). Для замыканий UN(Uk (B*)), UNmax(Uk (B*)) базисы получены при доказательстве лемм 4.2.2, 4.3.1.
В з4.5 проведено сравнение различных видов нормировок и исследована операция деления. Нормировка является пока единственной лестественной операцией, для которой строение замыканий и критерии корректности не зависят от точного разбиения множеств и на подмножества t, t (не учитывается геометрия классов), t {1,2,Е,m}. Нормировка N[0,1] частично учитывает геометрию классов, поскольку rg(UN[0,1](Uk (B*))) и корректность зависят от q.
Теорема 4.5.1. В регулярной задаче распознавания с двумя непересекающимися классами замыкания UN(B*), UN[0,1](B*), L(B*) корректны / некорректны одновременно. В регулярной задаче распознавания с двумя классами замыкание UNmax (B*) корректно.
Теорема 4.5.2. Замыкание L DL(B*) корректно тогда и только тогда, когда замыкание U(B*) корректно, где D - операция взятия обратной по Адамару матрицы:
D(|| hij ||ql ) =, hij ql M*(D) = {|| hij ||ql | (i, j)QL hij 0}.
Корректный алгоритм в алгебре с делением (индуцируется поэлементным делением матриц оценок) может быть представлен в виде c D(B1 + ciB2) C, где {B1, B2} L(B*).
j j i В главе 5 исследована нестандартная корректность. Модель R* РО называется C*-корректной (корректной относительно мно жества РП C*), если {0,1}ql B R*, C C* : C([B]) = .
В з5.1 введены основные определения, формализующие естественные требования на РП: частичной монотонности (поскольку РП алгоритма должно верить РО и относить объект к тем классам, оценка принадлежности к которым выше). Пусть X - система непустых подмножеств множества QL (быть может, не всех).
Определение. Решающее правило (РП) - отображение из Qql в {0,1,}ql. РП С называется X -монотонным, если для любой матрицы ||ij ||ql С(||ij ||ql ) =||ij ||ql и для всех Y X справедливо (i, j)Y, (t, s)Y ij = 0, ts = 1 ij < ts.
Множество X -монотонных РП будем обозначать через C*(X ).
В з5.2 изложены общие критерии получения классификации. В теореме 5.2.1 - в виде специального представления ЛЗ-матрицы. Теорема 5.2.2 является наглядной переформулировкой этого результа та. По системе X и матрице =||ij ||ql{0,1}ql можно построить двудольный граф G(X, ) = (V1(G),V0(G), E(G)), множество вершин первой доли - V1(G) = {(i, j) | ij = 1}, второй - V0(G) = {(i, j) | ij = 0}, V (G) = V0(G) V1(G) = QL, множество ребер - Е(G) = {{(i, j),(t, s)} | Y X : (i, j)Y,(t, s)Y, ij = 1,ts = 0}.
Помеченный двудольный граф G(X,,|| lij ||ql ) получается приписыванием каждой вершине (i, j) веса w((i, j)): w((i, j)) = lij при (i, j)V1, w((i, j)) =-lij при (i, j)V0.
Определение. Пусть E[v] - множество всех ребер, инцидентных вершине v. Разметкой рёбер помеченного графа G называется функция w : E(G) {0,1,2,Е}, v V (G) w(v) = w(e).
eE[v] Теорема 5.2.2. С помощью РО модели L(R*) и X -монотонного РП можно получить классификацию {0,1}ql тогда и только тогда, когда не существует ненулевой ЛЗ-матрицы L (модели R*), для которой найдется разметка рёбер графа G(X, , L).
Лемма 5.2.1 (простое обобщение теоремы Холла) устанавливает критерий существования разметки рёбер помеченного целыми неотрицательными весами графа G( X, , L).
В з5.3 получены критерии корректности относительно семейств построчно и постолбцово монотонных РП. Пусть XП = XГ XВ, q XГ = {{(i, j) | j {1,2,Е,l}}}i=1, XВ = {{(i, j) | i {1,2,Е,q}}}l.
j= Определение. Классификация (q l Цматрица) ||ij ||ql{0,1}ql согласована с матрицей || lij ||qlQql, если для всех (i, j)QL lij > 0 ij = 1, lij < 0 ij = 0.
Лемма 5.3.2. Классификацию из {0,1}ql нельзя реализовать РО из Uk (B*) и X -монотонным РП, X = {Y1,Е,Yr}, Y1 ЕYr = QL, |Y1 | +Е+ |Yr |= ql, тогда и только тогда, когда она согласована с ненулевой ЛЗ-матрицей || lij ||ql этой модели, для которой Y X lij = 0.
(i, j)Y Теорема 5.3.1. Модель Uk (B*) C*(XГ) -корректна тогда и только тогда, когда она корректна или l = 1. Модель Uk (B*) C*( XВ)корректна тогда и только тогда, когда она корректна или q = 1.
Теорема 5.3.2. Модель Uk (B*) одновременно является / не является корректной, C*(XП )-корректной, C*({QL})-корректной.
В з5.4. исследована корректность в задаче распознавания с l непересекающимися классами, l 2.
Теорема 5.4.1. Матрица L = [1Еl ] является ЛЗ-матрицей модели L(B*) тогда и только тогда, когда для её столбцов 1,Е,l l L t , j L t , j j=1 tT ( ) jInd( ) tT ( ) где = {(St ) | 1(St ) = 1, t = 1,m}{1 - (St ) | 1(St ) = 0, t = 1,m}.
Теорема 5.4.2. В задаче распознавания с непересекающимися классами матрица L = [1Еl ] является ЛЗ-матрицей модели Uk (B*) тогда и только тогда, когда для её столбцов 1,Е,l l l L (k ), j {1,2,Е,l} j L(k ).
j j j j=1 j= Определение. Пусть C* - множество РП, * - множество классификаций (q l -матриц). Будем называть модель R* РО C*- * корректной, если * B R*, C C* : C([B]) =.
Определение. РП С называется РП по максимуму, если С(||ij ||ql ) =||ij ||ql : при |{ j {1,2,Е,l} | ij = max[i1,Е,il ]}| 2 спра ведливо (ij )l = (,Е,), а иначе (ij )l = es, где is = max[i1,Е,il ].
j=1 j=* q Будем называть Cmax -{0,1}нпl -корректную модель НП-корректной, где * q Cmax - множество всех РП по максимуму, {0,1}нпl - множество бинарных q l -матриц, у которых в каждой строке ровно одна единица.
Теорема 5.4.3. Следующие утверждения эквивалентны: 1. Существует ненулевая ЛЗ-матрица модели Uk (B*), в каждой строке которой не более одного положительного элемента и не менее одного неотрицательного. 2. Модель Uk (B*) не является НП-корректной.
q 3. Модель Uk (B*) не является C*( X) -{0,1}нпl -корректной. 4. Модель q Uk (B*) не является C*({QL})-{0,1}нпl -корректной.
В задаче с l непересекающимися классами вместо корректности следует требовать от модели НП-корректность, поскольку их критерии совпадают лишь при l = 2.
Теорема 5.4.4. При любом с Q классификация из {0,1}ql реализуется алгоритмом из {B Cc,c2 | B Uk (B*)}, с1 с2, тогда и только тогда, когда она реализуется алгоритмом из {B Cc | B Uk (B*)}.
В з5.5 исследовано сведение одной задачи распознавания к другой с помощью перекодировки векторов классификаций. Пусть Zнп3 - задача распознавания с тремя непересекающимися классами, а задача с двумя (пересекающимися) классами Zп2 получается из исходной следующим изменением векторов классификаций:
(1,0,0) (1,0), (0,1,0) (0,1), (0,0,1) (1,1).
Теорема 5.5.1. Если модель Uk (B*) в задаче Zнп3 НП-корректна (или просто корректна), то модель Uk (B*) корректна и в задаче Zп2.
Если модель Uk (B*) в задаче Zп2 корректна, то модель Uk +1(B*) корректна (и НП-корректна) в задаче Zнп3. Утверждение нельзя усилить, заменив модель Uk +1(B*) замыканием Uk (B*).
Рис. 5.5.1. Символическое изображение утверждения теоремы 5.5.1.
Пусть Zнпl - задача с l непересекающимися классами, а Z2 - набор задач Z2j, j {1,2,Е,l}, таких, что Z2j получается из Zнпl переко дировкой: ej (1,0), ei (0,1) при i {1,2,Е,l} \ { j}. Аналогично, Z3 - это набор задач Z3,i, j, j {1,2,Е,l}, i {1,2,Е,l} \ { j}: ej (1,0), ei (0,1), а эталонные объекты S, для которых (S){ei,ej} в Zнпl, в задаче Z3,i, j отсутствуют. Модель корректна в Z2 (Z3) тогда и только тогда, когда она корректна во всех задачах этого набора. Для краткости, утверждения теоремы 5.5.2 показаны на рис. 5.5.2.
Рис. 5.5.2. Символическое изображение утверждений теоремы 5.5.2.
Глава 6 посвящена отдельной математической проблеме, которая имеет приложения не только в теории распознавания, но и в теории интерполяции: критериям вырожденности матрицы попарных l1-расстояний конечной системы точек в Rm и их обобщениям. В з6.введены основные обозначения и получены некоторые критерии. Для функции f : X R пусть N[ f ] = {x X | f (x) 0} (носитель функции f ), f (Y ) = { f (x) | x Y}, где Y X. Пусть задана система точек q S = {si}i=1 Rm : |S |= q 2, A = A1 Е Am: At = {at0,Е,atp(t )} = = {(si )t | i {1,2,Е,q}}, at0 < Е < atp(t), p(t) 1 при t {1,2,Е,m}.
Пусть PS - матрица попарных l1-расстояний. Лемма 6.1.1 описывает множество Uk[S] = Uk (PS ).
Определение. Система точек S называется k -сингулярной, если размерность пространства Uk[S] меньше q.
kk Теорема 6.1.1. Пусть z :{1,2,Е,Cm} C{1,2,Е,m} - биективное q отображение. Система точек {si}i=1 k -сингулярна тогда и только k q m тогда, когда является 1-сингулярной система точек {di}i=1 RC :
k t {1,2,Е,Cm} [(di )t = (d )t r z(t) (si )r = (sj )r ].
j Теорема 6.1.2. Система точек S не является k -сингулярной при k m тогда и только тогда, когда любая функция f (x1, x2,Е, xm) на точках системы S может быть представлена в виде конечной суммы функций, каждая из которых зависит от k переменных. Любая функция f (x1, x2,Е, xm) на точках множества S может быть представлена в виде конечной суммы функций, каждая из которых зависит от log2 | S | переменных.
Пусть G - минимальная группа (с операцией суперпозиция), содержащая преобразования g : Rm Rm, t {1,2,Е,m}, {x, y} R :
t,x, y st {x, y}, (s (s1,Е, sm), g ((s1,Е, sm)) =,Е, st-1, y, st+1,Е, sm), st = x, t,x, y (s1,Е, st-1, x, st+1,Е, sm), st = y.
Лемма 6.1.2. Для любого преобразования g G справедливо равенство Uk[S] = Uk[g(S)]. Например, система точек S k -сингулярна тогда и только тогда, когда k -сингулярна система точек g(S).
Достаточно ограничиться рассмотрением точек на целочисленной q q решётке, поскольку Uk[{(a1,b(i,1),Е,am,b(i,m))}i=1] = Uk[{(b(i,1),Е,b(i,m))}i=1].
q Теорема 6.1.3. Система точек S = {si}i=1 является 1-сингулярной тогда и только тогда, когда существует такое подмножество X {1,2,Е,q}, что для любого преобразования g G система точек {g(si )}iX не отделима от системы точек {g(si )}i{1,2,Е,q}\ X гиперплоскостью. В условии отделимость гиперплоскостью можно заменить отделимостью с помощью фиксированной гиперплоскости с уравнением a1x1 +Е+ amxm + a0 = 0, 0{a1,Е,am}.
q Теорема 6.1.4. Система точек S = {si}i=1 пространства Rm является 1-сингулярной тогда и только тогда, когда q (c1,Е,cq)т Rq \ {0}: s Rm c (s, si ) = 0, i i=где - метрика Хэмминга или l1-метрика. Теорема перестаёт быть верной при изометричном вложении S в другое пространство.
m Пусть функция : Rm R такая, что N () X = {at,bt}, t=r =|{t {1,2,Е,m} | at bt}|. Если (X ) = {+1} или (X ) = {-1}, то функция называется константным параллелепипедом (к.п.) размерности r, а если в каждой точке (c1,Е,cm) множества X она равна (-1)c, c =|{t {1,2,Е,m} | сt = at}|, то называется размеченным параллелепипедом (р.п.) размерности r. Элементы множества X называются вершинами р.п. (к.п.). Параллелепипед называется последовательным относительно множества A, если m t t N () = Y, t {1,2,Е,m} r {1,2,Е, p(t)}: Y {at,r-1,atr}.
t= Теорема 6.2.2. Система точек S k -сингулярна тогда и только тогда, когда найдётся конечная сумма функций из множества k, для которой N[] S. Утверждение справедливо для множеств k следующих функций: 1. К.п. размерности больше k с одной общей вершиной. 2. Р.п. размерности больше k с одной общей вершиной. 3. Р.п. размерности (k +1). 4. Последовательных относительно A р.п. размерности (k +1). 5. Последовательных относительно A к.п. размерности (k +1).
Доказательства (теорема 6.2.2, следствие, леммы 6.2.4 - 6.2.5) следуют из теоремы 6.2.1 (не приводится из-за громоздких обозначений), основная идея которой - сведение задачи о k -сингулярности к задаче о свойствах множества булевых векторов, линейное замыкание которого описывает пространство L(Uk[S]).
В з6.3 показано приложение результатов о k -сингулярных системах к распознаванию. По теореме 2.4.4 некорректность модели Uk (B*) эквивалентна k -сингулярности системы QL, заданной матрицей попарных l1-расстояний. При представлении подсистемы k -сингулярной системы точек в виде носителя суммы р.п. в явном виде получается ненулевой вектор пространства L(Uk[S]), а применительно к задаче распознавания - ненулевая ЛЗ-матрица модели (и классификация, не реализуемая оператором из Uk (B*) и пороговым РП).
Теорема 6.3.1. В задаче распознавания с двумя непересекающимися классами и разнесёнными эталонами для любого оператора B из алгебраического замыкания k -й степени модели АВО с системой всех одноэлементных опорных множеств существуют функции gr,Е,rk, 1 r1 < Е < rk n, от k переменных, для которых i1[B] = gr,Е,rk ( fr (Si ),Е, fr (Si )).
11 k 1r1<Е В заключении перечислены основные результаты работы (см. раздел На защиту выносятся). Приложение состоит из трёх частей. В первой части дан перечень обозначений, введённых по ходу изложения. Во второй части описано решение проблемы нахождения критерия эффективной реализации АВО, которая более двадцати лет оставалась открытой (вынесено в приложение, поскольку вопрос практической реализации алгоритмов модели не является центральным для данной работы). Z Рассмотрен случай Z = {1,2,Е,n}, СОМ A : A 2, w() = w(), e1 n модели B*(x11) с функцией близости ,Е,e ; q1,q2 (результаты легко обобщаются на другие случаи). Описаны все СОМ A, для которых при всех параметрах и аргументах функции близости найдутся I Z, {, } {0,1,2,Е}: e1 n w(). (7.1) w(),Е,e ; q1,q2 (St,Si ) = w() + A I Z \ I Из теоремы Ю.И. Журавлёва следует необходимость эффективного вычисления (7.1) для практической реализации алгоритма. По теореме 7.1 нужный класс СОМ исчерпывается всеми подмножестваr ми множеств C{1,2,Е,n} {{1,2,Е,n},}, r {1,n -1}, и СОМ вида r1 rs C{1,2,Е,n} Е C{1,2,Е,n}, 0 r1 < Е < 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. - C.916 - 927. 7. Дьяконов А.Г. Критерии корректности алгебраических замыканий модели алгоритмов вычисления оценок // Докл. РАН. - 2008. - Т.420. - №6. - С.732 - 735. 8. Дьяконов А.Г. Алгебраические замыкания обобщенной модели алгоритмов вычисления оценок // Докл. РАН. - 2008. - Т.423. - №4. - С.461 - 464. 9. Дьяконов А.Г. Критерии вырожденности матрицы попарных l1-расстояний и их обобщения // Докл. РАН. - 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. Дьяконов А.Г. Корректность относительно семейства решающих правил // Интеллектуализация обработки информации: тез. докл. Междунар. науч. конф. - Симферополь. Крымский научный центр НАН Украины, 2006. - С.77 - 78. 16. Дьяконов А.Г. Корректность относительно семейства решающих правил // Искусственный интеллект. - 2006. - №2. - С.61 - 64. 17. Дьяконов А.Г. Анализ кластерных конфигураций в одной проблеме фильтрации спама // Сборник докладов XIII Всероссийской конференции ММРО-13. - М.: МАКС Пресс, 2007. - С.476 - 478. 18. Дьяконов А.Г. Метрические критерии корректности в теории распознавания образов // Проблемы теоретической кибернетики. Тез. докл. XV междунар. конф. - Казань: Отечество, 2008. - C.31. 19. Дьяконов А.Г. Исследование алгебраических замыканий алгоритмов распознавания: операторы разметки // Интеллектуализация обработки информации: тез. докл. Междунар. науч. конф. - Симферополь. Крымский НЦ НАН Украины, 2008. - С.96 - 98. 20. Дьяконов А.Г. Исследование алгебраических замыканий алгоритмов распознавания: операторы разметки // Таврический вестник информатики и математики. - 2008. - №1. - С.199 - 203.