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

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

Карпович Павел Алексеевич

К-СИНГУЛЯРНЫЕ СИСТЕМЫ ТОЧЕК В АЛГЕБРАИЧЕСКОМ ПОДХОДЕ К РАСПОЗНАВАНИЮ ОБРАЗОВ

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

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

о 3 ОсЗ 2011

Москва - 2011

4853799

Работа выполнена на кафедре «Математические методы прогнозирования» факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова

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

Дьяконов Александр Геннадьевич Официальные оппоненты: доктор физико-математических наук

Сенько Олег Валентинович кандидат физико-математических наук Дайняк Александр Борисович Ведущая организация: Московский физико-технический институт

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

Защита состоится « 18 » февраля 2011 г. в _11_ часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В. Ломоносова по адресу 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.su в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан » 2011 г.

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

Н.П. Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Задачи распознавания образов (классификации) возникают при решении практических проблем во многих областях (экономика, социология, информационные технологии и т.д.). Во второй половине XX века академиком РАН Ю.И. Журавлевым была предложена модель алгоритмов вычисления оценок (ABO) для решения задач классификации. Универсальность модели позволяет представлять широкий класс алгоритмов распознавания образов, и большинство известных на данный момент правил классификации могут быть описаны в рамках данной модели. Работы Ю.И. Журавлева стали началом большого количества исследований модели ABO. В первую очередь интерес вызывали вопросы о возможности эффективных алгоритмических реализации моделей. Явная реализация ABO практически невозможна в связи с ее большой вычислительной сложностью. При попытке решить данную проблему появилось два основных направления исследований: получение эффективных формул вычисления оценок (Ю.И. Журавлев, A.A. Алексанян, С.Н. Мирошник, М. Михалевич, В.В. Никифоров, Н.М. Ка-милов, Ш.Е. Туляганов, И.Б. Гуревич, А.Г. Дьяконов) и поиск параметров моделей, при которых возможна эффективная реализация ABO ( Ю.И. Журавлев, A.A. Алексанян, А.Г. Дьяконов).

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

и систем опорных множеств, при которых осуществляется свертка формулы вычисления оценок близости. В работе A.A. Алексаняна и Ю.И. Журавлева показывается, что возможность упрощения формул существенно зависит от выбора системы опорных множеств и предлагается общий подход к изучению задачи об эффективной реализации моделей ABO. Для конкретного класса функций близости А. Г. Дьяконовым были найдены все системы опорных множеств, для которых возможно осуществить свертку определенного вида. При этом актуальными остаются вопросы полного описания систем опорных множеств, при которых допустимы такие упрощения формул для других классов функций близости.

В конце 1970х годов Ю.И. Журавлевым был предложен алгебраический подход к решению задач распознавания образов. Центральным понятием алгебраического подхода является корректность семейств алгоритмов распознавания. На практике оно означает возможность получения любой классификации объектов задачи при помощи алгоритмов семейства. Исследованию вопросов корректности было посвящено множество работ. Членом-корреспондентом РАН К.В. Рудаковым была разработана теория локальных и универсальных ограничений для анализа общих семейств алгоритмов и доказаны критерии корректности. Первые критерии корректности для алгебраических замыканий модели ABO описаны в работах академика РАН В.Л. Матросова. В работах А.Г. Дьяконова устанавливается, что свойство корректности алгебраических замыканий семейства ABO для конкретной задачи эквивалентно отсутствию свойства fc-сингулярности у набора системы точек признаковых описаний распознаваемых объектов. Поэтому актуальным является исследование понятия ¿-сингулярности в рамках алгебраического подхода к распознаванию. Система q точек в конечномерном пространстве называется fc-сингулярной, если размерность пространства значений полино-

мов степени не выше к (с поэлементным умножением) от столбцов матрицы попарных расстояний системы меньше q.

Цель работы.

1. Исследование возможности эффективных реализаций моделей ABO в зависимости от выбора функций близости и системы опорных множеств.

2. Исследование свойства fc-сингулярности в рамках алгебраического подхода к распознаванию, получение алгебраических критериев к-сингулярности.

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

- Описан частичный порядок и его свойства для класса О-эффективных систем опорных множеств (широкий класс систем опорных множеств, при которых допустима эффективная реализация ABO).

- Доказана NP-полнота задачи поиска контрпримера к свойству 0-эффективности при дополнительных ограничениях.

- Доказан алгебраический критерий для свойства /с-сингулярности.

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

- Получена оценка минимального числа таких подсистем.

Методика исследования: методы дискретной математики, комбинаторная оптимизация, теория матроидов.

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

Апробация работы. Материалы, изложенные в диссертации, докладывались на

- Международных конференциях студентов, аспирантов и молодых ученых «Ломоносов 2009» [1], «Ломоносов 2010» [5] (Москва, МГУ);

- 52-й научной конференции МФТИ «Современные и проблемы фундаментальных и прикладных наук» [4] (Долгопрудный, МФТИ);

- Всероссийской конференции «Математические методы распознавания образов - 14» [3] (Суздаль);

- Международной конференции «Интеллектуализация обработки информации - 2010» [7] (Пафос, Кипр);

Личный вклад. Основные результаты получены автором лично. В совместной публикации в материалах конференции [3] автору принадлежит алгебраический критерий /с-сингулярности (1с.), а в [7] - решение задачи разбиения на подсистемы без свойства 1-сингулярности и оценка на минимальное число таких подсистем (2с.).

Публикации. По теме диссертации опубликовано 7 работ [1-7], в том числе одна в ЖВМиМФ и одна в Вестнике Московского университета (журналы входят в перечень ВАК). Описание отдельных результатов включены в научные отчеты факультета ВМК и отчеты по проектам РФФИ 08-07-00305-а, 10-07-00609-а.

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы (69 ссылок). Основной текст занимает 80 страниц.

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

Во введении обосновывается актуальность работы и описываются основные направления исследований.

В первой главе приводятся необходимые определения и обзор предыдущих работ.

В §1.1 содержится постановка задачи распознавания. Имеется множество допустимых объектов М, разбитое на классы М = К\ U ... U K¡. Для каждого из допустимых объектов s € М существует полное признаковое описание (значение набора признаков) I(s) = (ai,..,a„) и вектор значений предикатов принадлежности к классам, на которые разбито множество допустимых объектов: á(s) = (a:i(s),.., a;(s)), где значение предиката "s G К^ равно ai(fl)e{0,l})í = l>2,..,í.

Для некоторого набора объектов S — {sí,sj} известны признаковые описания и значения предикатов принадлежности к классам распознавания {cij (5í)}¿¿i - Данное множество называется эталонным набором, а объекты из него называются эталонными объектами. Имеется также множество объектов 5 = {si,..,s9}, называемое контрольным набором. Задача состоит в построении алгоритма А, который по информации об эталонном наборе правильно классифицирует объекты контрольного набора.

В §1.2 кратко описана модель ABO. При построении модели алгоритмов вычисления оценок предполагается, что множество допустимых объектов М является декартовым произведением пространств значений признаков: М = М\ х ... х Мп, Mj - метрическое пространство значений j-ro признака с метрикой pj. Множество признаков Рп = {1,2, ..,п}.

Алгоритм модели ABO А строится в виде суперпозиции распознающего оператора и решающего правила: А = В о С. Оператор В вычисляет набор оценок близости распознаваемых объектов к классам Kj, на основании этой информации правило С принимает решение о вхождении объектов в тот или иной класс. Оценки близости к классам вычисляются по следующей формуле:

т = iiry[B]iu

1,1

ГУ[В]= £ хаЬ^ (1)

а,6=0,о шеПд

где гир € = {х е К | х > 0} при р е {1,... ,4} (вес р-го объекта), - система опорных множеств (система опорных множеств - семейство подмножеств признаков Рп = {1,2, ..,гг}), и>и € М+ при и £ Па - вес опорного множества ш),(а,Ь) е {0,1}2, хаЬ £ {0, (-1)0+ь},

А7 =

SDKj, а = 1, S\Kj, а = 0,

В5¿"b{sp, Si) - функция близости между объектами признакового пространства М.

В данной работе центральное место занимает исследование моделей ABO с пороговыми функциями близости. Для двух допустимых объектов sc,I(s°) = (ci,..,cn), sd,I(sd) = (di,..,dn) и набора числовых порогов е = (ei, ...,£■„) обозначим через 5E(sc,sd) = (¿i, ...,5п) вектор результатов пороговых сравнений в признаковых пространствах:

1, если pj(cj,dj) < £j 0, иначе.

Определение. Функция близости BÜJ](sc, sd), принимающая значения 0 и 1, называется пороговой, если она однозначно определяется значениями координат вектора 6 e(s°, sd), входящими в опорное множество Wj. Также для пороговых функций близости будет использоваться обозначение B(üjj, 5e(s°, sd)).

В §1.3 содержится описание известных результатов об эффективных реализациях алгоритмов ABO. Предполагается, что вес опорного множества^ является суммой весов признаков, входящих в него. Большинство результа-

тов описывают способы свертки части

ГМ = (2)

UÉÍÍA

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

В §1.4 приведены основные определения алгебраического подхода к распознаванию и описываются результаты, связывающие понятие ¿-сингулярности системы точек с критериями корректности семейств распознающих операторов.

Определение. Система q точек в Rm с ^-расстоянием называется к-сингулярной, если размерность минимального линейного пространства, содержащего все полиномы степени не большей от столбцов матрицы попарных ¿i-расстояний, строго меньше q (умножение столбцов поэлементное). Таким образом, 1-сингулярные системы — системы с вырожденными матрицами попарных ^-расстояний.

Пространство полиномов степени не более чем к от столбцов матрицы Н (умножение поэлементное) обозначается через Uk(H).

В §1.5 излагаются определения теории матроидов и кратко описывается алгоритм Д. Кнута поиска минимального покрытия базы матроида независимыми множествами.

Вторая глава содержит основные результаты, связанные с построением эффективных реализаций ABO. Исследуется, когда вектор суммы

]ГхНв^(м)> (3)

ыеПл

содержит не более двух различных координат, где х(и) - характеристиче-

ский вектор опорного множества о». Рассматривается три семейства функций близости:

т«./ \ ) 1,еслихИ-2;>д1ИхИ-а;<д2, ВгиЧ2(ш,х) = ^

О, иначе,

В*'п+1(ш,х) — ^ еСЛИ =

О, иначе,

о* о/ \ I 1,еслихИ • х = х(и) ■ х{Рп),

В*'и(ш, х) = <

I 0, иначе,

где х - бинарный пороговый вектор, ш - опорное множество, и - дополнение ш до Рп (х(ш) + х(^) = х{Рп))> П0Д умножением (•) векторов понимается скалярное произведение.

Отдельно рассматриваются функции В?1'п+1 и В?ь0. Определение. Система опорных множеств П называется эффективной для семейства функций близости В~~, если для любой функции семейства В € В~'~ и бинарного вектора х вектор суммы

В(ш,х)

содержит не более двух различных координат. Класс эффективных систем для семейства пороговых функции Вбудем обозначать через КБ~~

В §2.2 содержится доказательство того, что верна цепочка вложений Ш1'92 С С КВ^п+1 ^ КВ*'° й КБ91-0.

В §2.3 изучен класс КВ*'°.

Определение. Эффективную систему опорных множеств из классаКВ*'° будем называть О-эффективной, если для любого бинарного векторах у суммы

шбП

в любой паре различных координат одна из них равна 0.

Для любой эффективной системы опорных множеств П из класса КВ*'° можно получить 0-эффективную систему опорных множеств, взяв множества, которые не содержат последней координаты из Рп.

Отношение эквивалентности для систем 0-эффективных опорных множеств вводится как транзитивное замыкание следующего отношения. Системы опорных множеств ПиП эквивалентны, если выполнено хотя бы одно из условий:

1. П и П определены для множества Р„, и О. переходит в П под действием некоторой перестановки набора признаков а, т. е. а - перестановка множества Рп = {1,-,™} и

п = {МлХ-^О'ОИ ш £ = {31,-,3к}}-

2. П - система для признаков Рп. Два признака с номерами п и п — 1 одновременно входят или не входят во все опорные множества системы П, в этом случае П определена для меньшего набора признаков Рп-\ и является набором опорных множества Г2, из которых удален признак с номером п, где он присутствует:

\ZwGO: пеш&п- = {ш\{п}|ш € Г2},

\ - оператор разности множеств.

3. - система для набора Р„, признак с номером п не входит ни в одно опорное множество из Я Тогда П - система для набора Рп-1 и просто состоит из опороных множеств, входящих в О (удаление незначащей координаты):

$шеП: га € ш =*> П = П.

Вводится отношение порядка для классов эквивалентности. Пусть есть два различных класса эквивалентности: Е\ для набора признаков Рп и Е2 для набора Рп-к(к > 1), Пвд и - их представители, причем - канонический представитель (система опорных множеств в классе эквивалентности, для которой размерность признакового пространства, где она определена, минимальна). Отношение Е\ > Е2 выполнено, если &е2 состоит из множеств, входящих вП^ и не содержащих координаты {п — к + 1,..., п}:

£1е2 = {ш\ и> € П^цГС -к + 1фш,..., п £ со}.

Обозначение У Е2 соответствует факту того, что Е\ > Е2 и не существует такого Ез, что Е\ > Ез > Е2

Теорема. Пусть А - класс эквивалентности О-эффективных множеств. Тогда длина любой цепочки А у А\ У А2 У ... у 2 одинакова.

В §2.4 содержатся сложностные результаты для следующей задачи.

Задача 3. Пусть Рп - множество {1,2, ...,п}. На нем задана некоторая система подмножеств О,, количество множеств ограничено полиномом от п. Верно ли, что существует подмножество У СР„с элементами 1 и 2 такое, что количество подмножеств У, входящих в Г2 и содержащих элемент 1, больше числа таких же множеств, содержащих элемент 2, и оба числа положительны: 1,2 6 У : е Л : ы с УД е ы}| > |{ш е П : Ы С у,2 € а>}| > О (контрпример к свойству О-эффективности, для которого условие нарушается для индексов 1 и 2).

Теорема. Задача 3 является NP-полной.

Третья глава посвящена результатам, связанным с понятием к-сингулярности. В §3.1 приведено доказательство алгебраического критерия ¿-сингулярности.

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

ч

]Tc¡/(s,s¡) = О,

¿=1

где р - метрика Хэмминга или ¿х-метрика(& < т).

В §3.2 рассмотрена задача о разбиении системы точек на минимальное число подсистем, каждая из которых не является 1-сингулярной. Показано существование полиномиального алгоритма, решающего данную задачу. Для задачи распознавания с двумя непересекающимися классами такой алгоритм позволяет разбивать множество контрольных объектов на "области компетентности", для каждой из которых линейное замыкание семейства операторов ABO является корректным. Показано, что система точек S и набор подмножеств S без 1-сингулярности являются матричным матроидом. Доказана оценка на минимальное число подсистем без 1-сингулярности, на которые может быть разбита произвольная система точек.

Для системы точек S можно построить набор отношений эквивалентности {#¿}£Li. Две точки Sk и st эквивалентны согласно отношению если у них равны г-е координаты. Нас будет интересовать матрица T(S) = [7i,..,Tm], где каждый из блоков T¿ составлен из характеристических д-мерных векторов всех классов эквивалентности для отношения 0,. Данная матрица T(S) называется характеристической матрицей классов эквивалентностей

Теорема. Для системы точек 5 пространства Мт и соответствующей ей матрицы Т(5) верно неравенство

т

и , Д"

1=1

где c¡ - количество значений, которые может принимать г-я координата точек из системы 5, Т(5) - матрица классов эквивалентностей.

В §3.3 рассматривается задача разделения системы точек на подсистемы без свойства ¿-сингулярности. Показано, что система точек 5 и набор подсистем без свойства ¿-сингулярности являются матроидом. И для разбиения на минимальное число подсистем без ¿-сингулярности можно воспользоваться полиномиальными алгоритмами Д. Кнута и Дж. Едмондса. Однако данные алгоритмы являются полиномиальными в предположении того, что процедура проверки подмножества точек на независимость используется как оракул. В параграфе предложена также полиномиальная процедура проверки на наличие свойства ¿-сингулярности у системы точек.'

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

Центральной темой §3.5 является построение эффективных процедур проверки на ¿-сингулярность для систем точек в Кт. Процедура проверки, используемая в алгоритме из §3.3, состоит в вычислении полинома Ок(х) = хк от матрицы Нз

т г=1

где Р5 - матрица попарных ^-расстояний для 5, -Е - д х д матрица из одних 1, - разница между максимальным и минимальным значением г-й координаты для системы 5, и проверки на невырожденность полученной матрицы-результата. Похожий способ проверки работает и для случая метрики Хэм-минга, используется только матрица Я5 и полиномы ^(ж):

к т

ад = £ аг П> - .7 + 1), я5 = тД -

г=0 з=1

где Р^ - матрица расстояний в метрике Хэмминга, ак > 0, Ьк > 0, щ > О, Ь{ > 0 при г 6 {0,1,.., А; — 1}, к < тп. В параграфе поставлен вопрос об описании всех полиномов, которые могут быть использованы в такого рода критериях и доказана следующая теорема:

Теорема. Рассмотрим систему точек £ в пространстве Кга. Если полином Р(х) обладает следующими двумя свойствами:

- для произвольной системы 5 в Жр попарно различных точек выполнено равенство С/1(Р(Я5)) - С^(Р5) (р < ш),

- для произвольной системы 5в1р попарно различных точек найдется система 5 такая, что Р(Я£) = (р < ш);

то он является одним из полиномов вида

г=0 ' ¿=1

с целочисленными положительными коэффициентами аг.

Из доказательства данной теоремы также вытекают два следующих замечания.

Замечание. Для матрицы Я5 системы точек 5 верно равенство

Н3 = Т(5)Г(5)г. 15

Если второе условие утверждения заменить на условие:

- для произвольной системы точек S в MP (р < т) найдется матрица Т такая, что F(HS) = ТТт,

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

Замечание. Многочлен F(Hs) обладает свойством, что для любой системы точек S найдется система точек S такая, что выполнено равенство F(Hs) = тогда и только тогда, когда он имеет вид

к г

r=0 ' i=1

и хотя бы один из коэффициентов оо или ai отличен от нуля.

Для критерия fc-сингулярности с метрикой 1\ доказана следующая теорема.

Теорема. Если полином F(x) обладает следующими двумя свойствами:

- для произвольной системы S попарно различных точек с целочисленными координатами выполнено равенство Ul(F(Hs)) — Uk(Ps),

- для произвольной системы S попарно различных точек с целочисленными координатами найдется матрица Т такая, что F(Hs) = ТТГ;

то он является одним из полиномов вида Fk(x) с положительными коэффициентами Oj.

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

1. Карпович П. А. Критерий /с-сингулярности системы точек и оптимальное разбиение на подсистемы // Материалы XVI Международной конференции студентов, аспирантов и молодых ученых: секция ВМК. — М.: Изд. отд. ф-та ВМК МГУ, МАКС Пресс, 2009. - С. 33.

2. Карпович П. А. Эффективная реализация алгоритмов распознавания образов // Ж. вычисл. матем. и матем. физ. 2009.49. № 8 С. 1510-1516.

3. Карпович П. А., Дьяконов А. Г. Критерии к-сингулярности систем точек в алгебраическом подходе к распознаванию // Материалы XIV Всероссийской конференции 'Математические методы распознавания образов'. М.: МАКС Пресс, 2009. С. 41-44.

4. Карпович П. А. О задаче разделения системы точек в пространстве на подсистемы с невырожденными матрицами попарных растояний // Материалы 52-й научной конференции МФТИ 'Современные проблемы фундаментальных и прикладных наук'. Часть VII. Управление и прикладная математика. М:МФТИ. 2009. - С. 70-73.

5. Карпович П. А. Разделение системы точек на подмножества с невырожденными матрицами попарных расстояний // Материалы XVII Международной конференции студентов, аспирантов и молодых ученых: секция ВМК. - М.: Изд. отд. ф-та ВМК МГУ, МАКС Пресс, 2010. - С. 87-88.

6. Карпович П. А. Критерии ¿-сингулярности и разделения 1-сингулярных систем // Вестник Московского университета (серия 15) 'Вычислительная математика и кибернетика'. 2010. 34. № 4 С. 164-171.

7. Карпович П. А., Дьяконов А. Г. /с-сингулярные системы точек, приложения в алгебраическом подходе к распознаванию образов // Интеллектуализация обработки информации: 8-я международная конференция. — Республика Кипр, г. Пафос. М.: МАКС Пресс, 2010. - С. 61-64.

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

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

Введение.

Глава 1. Основные определения и обзор предыдущих работ.

1.1.Задача распознавания образов.

1.2Алгоритмы вычисления оценок.

1.3.Эффективные реализации ABO.

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

1.5.Теория матроидов.

Глава 2.Эффективная реализация модели ABO.

2.1.Постановка задачи и результаты.

2.2.Эффективные системы опорных множеств.

2.3.0-эффективные системы опорных множеств.

2.4Алгоритмы распознавания свойства О-эффективиости

Глава 3.Корректность моделей ABO и fc-сигнулярность.

3.1 Алгебраический критерий fc-сингулярности.

3.2.Раз деление систем точек на подсистемы без 1-сингулярности

3.3.Разделение систем точек на подсистемы без /с-сингулярности

3.4.Разделение на подсистемы для пространства IR

3.5.Эффективные критерии k-сингулярности.

Методы теории распознавания образов широко используются для решения практических задач во многих областях науки (биология, социология, экономика и т.д.). Предполагается, что исследуемые объекты принадлежат некоторому множеству М. Данное множество может быть представлено в виде объединения конечного набора классов: М = К\ U . U Задача распознавания образов (задача классификации) состоит в следующем: по конечному набору пар S = {(si,?/i)> ■••■> (5n,2/n)} (s¿ - объект из множества М, yi -информация о принадлежности объекта s¿ к классам распознавания) требуется построить алгорим А, который для произвольного допустимого объекта s множества М вычисляет значение предикатов принадлежности к классам ши

Для решения задач распознавания в начале 1970х годов академиком РАН Журавлевым Ю.И. была предложена модель алгоритмов вычисления оценок (ABO) [1G, 19]. Благодаря своей универсальности модель предоставляет широкие возможности для описания правил классификации. Многие известные эвристические алгоритмы являются частными случаями алгоритмов вычисления оценок при специальном выборе параметров. Алгоритм в модели ABO для распознавания набора из q объектов строит числовую (g х ¿)-матрицу оценок близости, в которой элемент на пересечении i-й строки и j-го столбца характеризует близость г-го объекта к j-му классу. По этой матрице оценок близости осуществляется классификация объектов.

Модель ABO широко применяется на практике, однако прямая численная реализация систем распознавания с использованием классических формул вычисления оценок близости практически невозможна. Возникающие препятствия связаны с большой вычислительной сложностью явных реализаций ABO. Множество работ посвящены именно алгоритмической оптимизации моделей ABO [1, 1G, 19, 8, 11, 12, 9]. Многие результаты исследований в данном направлении описывают способы упрощения формул вычисления оценок близости и их эффективной алгоритмической реализации при определенном выборе параметров модели.

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

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

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

Первые корректные семества алгоритмов распознавания были построены Журавлевым Ю.И.[16]. В общем случае (для достаточно богатых моделей алгоритмов) корректность семейств полностью исследована в работах Рудакова К.В.[50, 51, 52, 55, 57]. Первые критерии корректности моделей ABO ограниченной мощности были получены Матросовым B.JI. [35, 3G, 39, 40, 41, 42].

Для класса моделей ABO с пороговыми функциями близости критерий корректности при некоторых ограничениях был получен Дьяконовым А.Г. [10]. Оказывается, что корректность алгебраического замыкания степени к эквивалентна отсутствию свойства /¿-сингулярности у системы точек признаковых описаний контрольных объектов. Система q точек в конечномерном пространстве называется fc-сингулярной, если размерность пространства значений полиномов (с поэлементным умножением) от столбцов матрицы попарных расстояний системы меньше q. В работе [10] получен геометрический критерий /¿-сингулярности для конечномерных пространств с ^-метрикой и метрикой Хэмминга. Понятие /¿-сингулярности также возникает в задачах, связанных с теорией интерполяции [10, 62]. Возможность представления произвольной функции, определенной на конечном множестве точек S в ]Rm, в виде суммы функций от меньшего числа аргументов зависит от наличия свойства /¿-сингулярности у системы S.

В данной работе приводится алгебраический критерий /¿-сингулярности, описывающий свойство /¿-сингулярности в виде линейной зависимости системы антипотеициальных функций pk(s,si), где р - ^-метрика или метрика Хэмминга, Si - точка системы.

Описан алгоритм разделения системы точек в пространстве с 1\метрикой на подсистемы с невырожденными матрицами попарных расстояний. В рамках постановки задачи классификации, предложенной в работе [10], такой алгоритм позволяет разбивать множество контрольных объектов на "области компетентности", для каждой из которых линейное замыкание операторов ABO является корректной моделью. Получена оценка иа минимальное число подсистем без свойства 1-сингулярности, на которые может быть разбита произвольная система точек.

Основными результатами являются:

• описание 0-эффективных систем опорных множеств для моделей ABO и частичного порядка для таких систем;

• доказательство NP-полноты задачи распознавания свойства 0-эффективности с дополнительными ограничениями;

• алгебраический критерий /с-сингулярности для систем точек в Rm;

• алгоритм разбиения произвольной конечной системы точек вМт на минимальное число подсистем с невырожденными матрицами попарных ¿i-расстояний и верхняя оценка на число таких подсистем.

Результаты диссертации докладывались на следующих конференциях:

• Международных конференциях студентов, аспирантов и молодых ученых «Ломоносов 2009» [28], «Ломоносов 2010» [32] (работа заняла третье место в конкурсе научных работ студентов и аспирантов факультета ВМК) (Москва, МГУ);

• 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» [31] (работа отмечена дипломом победителя (3 место) конкурса научно-исследовательских работ студентов и аспирантов) (Долгопрудный, МФТИ);

• Всероссийской конференции «Математические методы распознавания образов - 14» [30] ( работа отмечена дипломом II степени за победу в конкурсе докладов молодых ученых) (Суздаль);

• Международной конференции «Интеллектуализация обработки информации - 2010» [34] (Пафос, Кипр).

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

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

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

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

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

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

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

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

9. Дьяконов А.Г. Эффективные формулы вычисления оценок для алгоритмов распознавания с произвольными системами опорных множеств // Ж. вычисл. матем. и матем. физ. 1999 Т.39. № 11. С.1904-1918

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

11. Гуревич И.Б. О выборе ансамбля признаков распознающих систем по принципу распознавания // Автоматика. Киев. 1974. № 5. С.43-52

12. Гуревич И.Б. Проблема распознавания изображений // Распознавание, классификация, прогноз. 1989. Вып. 2. С.280-329.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир, 1982.

14. Деза М.М., Лоран М. Геометрия разрезов и метрик // М.: МЦНМО. 2001. 736с.

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

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

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

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

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

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

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

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

23. Журавлев Ю.И. Избранные научные труды // М.: "Магистр". 1998. 420 с.

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

25. Журавлев Ю.И., Камилов М. М. Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение // "ФАН". Ташкент. 1974.

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

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

28. Карпович П. А. Критерий ^-сингулярности системы точек и оптимальное разбиение на подсистемы // Материалы XVI Международной конференции студентов, аспирантов и молодых ученых: секция ВМК. — М.: Изд. отд. ф-та ВМК МГУ, МАКС Пресс, 2009. С. 33.

29. Карпович П. А. Эффективная реализация алгоритмов распознавания образов // Ж. вычисл. матем. и матем. физ. 2009. 49. № 8 С. 1510-1516.

30. Карпович П. А., Дьяконов А. Г. Критерии k-сингулярности систем точек в алгебраическом подходе к распознаванию // Материалы XIV Всероссийской конференции 'Математические методы распознавания образов'. М.: МАКС Пресс, 2009. С. 41-44.

31. Карпович П. А. Критерии /¿-сингулярности и разделения 1-сингулярных систем // Вестник Московского университета (серия 15) 'Вычислительная математика и кибернетика'. 2010. 34. № 4 С. 164-171.

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

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

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

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

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

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

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

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

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

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

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

43. Полесский В. П. Покрытие конечного графа минимальным числом лесов // Пробл. передачи информ. 1976. № 12:2 С. 76-82

44. Прасолов В. В. Могочлены // М.: МЦНМО. 2001. С. 100-101

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

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

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

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

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

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

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

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

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

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

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

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

57. Dyn N., Light W. A., Cheney E. W. Interpolation by piecewise-linear radial basis functions // J. Approx. Theory. 1989. N 59. P. 202-223.

58. Light W. A. The singularity of distance matrices // Multivariate Approximation Theory. Berlin: Birkhauser-Verlag, 1989. P. 233-240.

59. Reid L., Sun X. Distance matrices and ridge function interpolation // Canadian Journal of Mathematics. 1993. N 45. P. 1313-1323.

60. Baxter B. J. C. Conditionally positive functions and p-Norm distance matrices // Constr. Approx. —1991. — N 7. — P. 427-440.

61. Edmonds J. Matroid partition // Math. Decision Sciences. Proceedings 5th Summer Seminary Stanford. Part 1 (Lectures of Applied Mathematics 11). 1968. P. 335-345.

62. 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. N 38. Pp.787-793.

63. Schoenberg I. J. Metric spaces and positive definite functions // Trans. Amer. Math. Soc. 1938. N44. Pp.522-536.

64. Schoenberg I.J. Metric spaces and completely monotone functions // Ann. Math. 1938. N39. Pp.811-841.

65. Schrijver A. Combinatorial optimization: polyhedra and efficiency. Berlin: Springer., 2003. 1. P. 651-761.

66. Knuth D.E. Matroid patrtitioning // Stanford University STAN-CS-73-342 1973 - P. 1-12