Синтез полиномов над экстремальными алгоритмами вычисления оценок тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Вычислительный центр им А А Дородницына Российской академии наук

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

Докукин Александр Александрович

Синтез полиномов над экстремальными алгоритмами вычисления оценок

Специальность 01 01 09 — дискретная математика и математическая

кибернетика

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

Москва, 2008г

003171713

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

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

профессор, академик РАН Журавлев Юрий Иванович

Официальные оппоненты доктор физико-математических наук,

профессор, чл -корр РАН Матросов Виктор Леонидович

кандидат физико-математических наук, зам директора НИИ СИ РАН Кольцов Петр Петрович

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

Защита диссертации состоится «~1(7» {м^шИ 2008 г в Л'/Жа заседании диссертационного совета Д002 017.02 Вычислительного центра им А.А Дородницына Российской академии наук (119333, г Москва, ул Вавилова, 40, конференц-зал).

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

Ученый секретарь

диссертационного совета /)/? У

д ф -м н , профессор м Рязанов В В

Общая характеристика работы

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

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

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

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

Этот факт вызвал интерес к использованию полиномиальных конструкций при решении прикладных проблем При этом возникают новые задачи, среди которых основной является уменьшение сложности корректного полинома Значительное количество работ посвящено оценке его степени и числа слагаемых Этой задачей занимались- Ю И Журавлев, И В Исаев, В JI Мат-

росов, Т В Плохонина, К.В. Рудаков, А С Дьяконов. Важные результаты о связи сложности полиномиальных алгоритмов с устойчивостью распознавания также получены Ю И. Журавлевым и В Л Матросовым

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

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

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

Кроме того, разработан и реализован программно новый метод распознавания в классе полиномов второй степени над ABO, принципиальной особенностью которого является использование быстрого приближенного метода поиска слагаемых максимальной высоты

Практическая ценность. Одним из результатов диссертационной работы является программная реализация разработанного метода распознавания «АВО-полином», продемонстрировавшего высокое качество работы на ряде реальных прикладных задач в сравнении с другими методами.

Также в рамках исследования разработан и реализован вспомогательный метод генерации достаточно разнообразных тестовых выборок с заданным по построению ABO максимальной высоты, что позволяет проводить дальнейшее исследование различных приближённых схем оптимизации

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

1 Российский фонд фундаментальных исследований

• проект 02-01-00558-а «Индуктивные методы построения корректных или высокоточных алгоритмов распознавания в алгебраических и логических моделях»,

• проект 03-07-06141-мас «Программа поддержки молодых ученых (для проекта 02-07-90134)»,

• проект 03-01-00580-а «Разработка и исследование методов поиска систем устойчивых закономерностей в эмпирических данных»,

• проект 04-01-08045-офи_а «Мультиалгоритмическая поддержка принятия решений в задачах распознавания и прогнозирования»,

• проект 05-01-00332-а «Конструирование и исследование иерархии моделей типа вычисления оценок и алгебр над ними»,

2 Международная ассоциация содействия сотрудничеству с учеными из новых независимых государств бывшего Советского Союза (ИНТАС), проект YSF 03-55-1969 «Developement of fast methods for construction of correct algorithms of minimal complexity (optimal correct algorithms) m context of algebraic approach for pattern recognition»

Результаты диссертационной работы докладывались и обсуждались на

1 11-й всероссийской конференции «Математические методы распознавания образов (ММРО-11)», 2003, Пущино 2. 12-й всероссийской конференции «Математические методы распознавания образов (ММРО-12)», 2005, Звенигород

3 7-й международной конференции «Распознавание образов и анализ изображений новые информационные технологии», 2004, Санкт-Петербург

4 13-й всероссийской конференции «Математические методы распознавания образов (ММРО-13)», 2007, Санкт-Петербург

Публикации. По теме диссертации опубликовано 14 работ, в их числе 4 статьи в журналах, входящих в перечень, рекомендованный ВАК России, 4 статьи в других российских и иностранных журналах, 6 статей в сборниках трудов международных и всероссийских конференций В списке публикаций автореферата приведено 10 работ, отражающих основное содержание диссертации

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения и списка литературы Объем основного текста работы -102 страницы, список литературы включает 38 наименований

Личный вклад автора. Все новые теоретические результаты работы, в частности, разработка схемы и методов оптимизации высоты ABO и метода распознавания «АВО-полином», верхние оценки сложности, получены лично автором При формулировке и доказательстве утверждений раздела 4 5 автор активно консультировался с В К Леонтьевым.

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

• схема оптимизации алгоритмов вычисления оценок, основанная на максимизации высоты ABO по порограм функции близости,

• оптимальный алгоритм максимизации высоты ABO, оценка его сложности;

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

• быстрый приближенный алгоритм оптимизации высоты ABO,

• схема конструирования и минимизации степени корректного полинома на основе оптимальных слагаемых;

• метод распознавания «АВО-полином»

Краткое содержание работы

Во введении обозначена тема исследования, обоснованы её актуальность, новизна, практическая значимость; даны краткие сведения о методах исследования, структуре работы.

Глава 1 является вводной. В ней приводятся определения задачи распознавания образов и алгоритма вычислений оценок (ABO), вводится новое определение обобщенного ABO

Рассматриваются две выборки векторов из n-мерного признакового пространства обучающая и контрольная. Для определенности предполагается, что первая содержит т объектов Si, ,Sm, а вторая - q- S1, ,Sq

Предполагается также, что множество допустимых объектов разбито на I классов Классификация объекта 5 задается информационным вектором а(5) = («1(5), ,а„(5)) по системе предикатов Р.,(5)-«Р(5) = £ е К3» Классификация всех объектов известна - требуется построить алгоритм, который, используя информацию об обучающей выборке /о = {51, .., 0(5*1), , а(5т)}, восстанавливал бы классификацию контрольной.

Таким образом, задача распознавания Z определяется совокупностью из начальной информации и контрольных объектов Z = Z(IQ, 51, , 5®)

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

1 Каждому признаку приписывается некоторый вес р„ г = 1, ., п

2 Выделяются некоторые подмножества множества признаков, которые называются опорными Их совокупность обозначается Пд Каждому опорному множеству и € Пл приписывается вес, как сумма весов входящих признаков

3 Вводится функция близости двух объектов по опорному множеству Вш{£>, 5")- Если не оговорено особо, везде далее будет использоваться пороговая функция близости, с порогами е,, г = 1, , п

4 Свой вес 7(5;) приписывается каждому объекту З3 обучающей выборки ^ = 1» ,т

5 Оценка объекта за класс вычисляется по следующей формуле-

Г,(51) = ^(5') + х0ГЙ(51), (1)

= ^ Е (2)

ДО') = 7Г Е ^ Е (3)

Здесь использованы следующие переменные и обозначения-

^ = К3 П{5"ь , <5т} - множество объектов обучающей выборки из ]-го класса; СК3 - дополнение ^-го класса в обучающей выборке, т.е СК3 = •>5п»} \ К}> 5(5,5г) = 1 - 5(5,5'), ХЬХ0 е {0,1} - коэффициенты, <5о, <51 - также коэффициенты, отвечающие за нормировку

6 Алгоритм вычисления оценок определяется как произведение А — В-С, где B(I0,S\ - ||Г„||,Х1 - \\r3(S*)\\qxl, С(||Гч||,х1) = \\0Jqxl) В - распознающий оператор, С - решающее правило, /Зу G {0,1, А}- окончательный ответ о принадлежности объекта S1 классу (нет, да, не известно)

В диссертации обобщается эта конструкция. Формально обобщенный ABO определяется следующим образом Вводится предикат принадлежности объекта классу - P\(S, К3), и предикат близости двух объектов объектов

-ад «о

P2(S,S') = BU(S,S') (5)

Применительно к каждой тройке (S, S', К:), такой что S' е К:, пара предикатов (Pi(5, Kj), P2(S', S')) может принимать четыре различных значения, каждому из которых сопоставляется коэффициент zoo, ®oi, Xw, > О

Формулы оценки объекта за класс из пункта 5 определения ABO можно переписать, воспользовавшись стандартными обозначениями

гЕ

о=0,1,/?=0,1

Е KMS) Е рМ^Ф S1) (6)

Sü{S!, ,sm} uesiA

Глава 2 также содержит вводные сведения об операциях над ABO и алгебраическом замыкании семейства из трудов Ю И Журавлева

Любой алгортм распознавания образов А может быть представлен в виде композиции алгоритмов В и С, где В . (hfS1, ,Sq) —> ||Aj||gxi, Aj £ 1,0 <i<q,0<j<l, C(\\¡}ZJ\\qxl) = ||ay||,x¡,ay G {0,1, Д} На множестве распознающих операторов {В} вводятся операции сложения, умножения и умножения на скаляр. Рассматривается замыкание М{В} множества {В} относительно этих операций а также его замыкания конечной степени

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

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

В работах Ю И Журавлева вводятся следующие условия регулярности задач и доказывается существование для них корректного алгоритма

1 Ки Ф Kt, и — 1,2, . , /, t = 1,2, , и — 1, и + 1, I (условие неравенства классов),

2. SV'^SW> v = 1,2, ,q, w = 1,2, ,v - l,v + 1, ,q (условие попарной неизоморфности контрольных объектов);

3 {Si, , Sm] Р. {S1, , Sq} — 0 (условие отсутствия обучающих объектов в контрольной выборке)

В [1] автором диссертации было показано, что условие регулярности можно ослабить, и рассматривать обобщенные регулярные задачи, удовлятворя-ющие только пунктам 1 и 2 определения регулярности

Теорема 1. Алгебраическое, замыкание М(А) подкласса алгоритмов вычисления оценок корректно над множеством обобщённых регулярных задач

В работах Ю И Журавлева при ограничениях 1, 2 и 3 явно строится совокупность алгоритмов в линейной алгебре, таких что для каждого контрольного объекта S\% = 1,2, , q и для каждого класса Kj.j = 1,2, / в ней существует распознающий оператор В4, строящий матрицу оценок ||Ги1)||9)<г, в которой Гу > N,TUV < е при (u,v) Ф (i,j), где N,e - любые заданные наперед числа. Необходимо отметить, что это весьма затрудняет применение теоремы в качестве инструмента построения корректного алгоритма для конкретных задач распознавания, поскольку в этом случае надо построить 1(1 - 1) + lq{g — 1) элементарных операторов ABO Здесь Qj = 1(1 — 1) - количество элементарных операторов, необходимых для построения слагаемых Вп выделяющих оценку всех объектов за j-й класс, Q{ ~ lq(q — 1) - количество элементарных операторов, необходимых для построения слагаемых BJt, выделяющих оценку г-го объекта за j-й класс В реальной задаче известна классификация контрольной выборки, поэтому необходимо выделять толь-

ко некоторое их подмножество, которое является допустимым. Кроме того, можно выделять допустимые объекты группами

В качестве дополнения к теореме 1 приводится модифицированная схема построения корректного ABO для заданной задачи, позволяющая существенно упростить процесс Для новой схемы получены следующие оценки:

• Qf < 4lq2, где Ql' - количество элементарных операторов, необходимых для построения слагаемых при использовании разбиения объектов на допустимые и недопустимые пары;

• Q'j = если в контрольной выборке объектов каждый класс содержит хотя бы один объект, не принадлежащий ни одному из остальных классов,

• Qi' < + l)i если в контрольной выборке для любого объекта S1 = (ai,.a„) существует обучающий объект St = (h, , bn) и признак и, такие, что в проекции на этот признак не более к контрольных объектов изоморфны относительно данного обучающего объекта

Вводится определение высоты ABO как разности между минимальной оценкой правильной пары (объект, класс), те пары, объект которой принадлежит соответствующему классу, и максимальной оценкой неправильной пары.

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

е* - arg max i min Г,(Я») - max Г„(Я»)). (7)

e€(0,oo)n («,j)€Afi (u,Í))GAÍ0

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

В разделе 4.1 описывается построение вспомогательной выборки, которая позволяет нагляднее интерпретировать перебираемые точки пространства и результаты работы методов [5] Для каждой пары (St,Su), 1 < г < Щ1 < и < д, объектов из обучающей и контрольной выборки во вспомогаг тельную задачу объект добавляется ]St - S'a\ Модуль в данном случае понимается как покоординатная операция. Каждый объект заносится в один из

Ю

2q классов Если St и Su принадлежат одному классу, то объект относится в класс 1и, иначе в класс 0и. В некоторых ситуациях, когда будут не важны различия между объектами, порожденными различными контрольными векторами, вся совокупность классов 1„ 1 < г < ш называется первым классом, а Оц, 1 < и < q - нулевым

Области вида [0, ai] х х [0,а„], аг > 0, г = 1,2, , п называются прямоугольниками. Вводятся определения дополнений и надстроек прямоугольника Выделяются некоторые специальные виды прямоугольников, прямоугольник называется правильным, если это минимальный по вложению прямоугольник, содержащий заданную совокупность объектов класса 1, прямоугольник называется объемлющим, если это минимальный по вложению прямоугольник, содержащий все объекты задачи Z'.

Рангом прямоугольника называется количество объектов класса 1, содержащихся в нем. Качеством прямоугольника называется высота соответствующего ему ABO Прямоугольник называется оптимальным для задачи Z, если он имеет максимальное качество среди всех прямоугольников

Следующая теорема [3] описывает структуру оптимальных порогов близости.

Теорема 2. Справедливо равенство тах ( min тах Г, (5й)) =

£e[0,oo]n (íj)eAfi (u,v)£Mo

= тах( min - тах TV(SV)), (8)

£6Ф (íj)eMi (u,v)eM0

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

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

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

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

В разделе 4.3 строится алгоритм перебора правильных прямоугольников вспомогательной задачи для n-мерного случая, в предположении доказанности результатов раздела 4.4

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

Итак, пусть зафиксирован ранг правильного прямоугольника к Это число далее будет также называться размером скользящего окна Дальнейшая идея метода заключается в последовательном исключении признаков Зафиксировав те значения ведущего признака, которые позволяют образовать прямоугольник ранга к, можно перейти к проекции вспомогательной задачи меньшей размерности Повторяя этот процесс, в итоге достигнем размерности 2, для которой разработан специальный алгоритм

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

Теорема 3. Число вычислений высоты ABO I(n,w,k) для п признаков w объектов и размера окна к удовлетворяет следующей оценке•

I(n, w, к) < + - к + i)71"1)- (9)

Сложность алгоритма I(n,w) или общее число вычислений высоты ABO не превосходит

wn

l{n,w)<-r + 0{wn) (10)

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

Г(п, V)) < г1(тах1=1: 1Г|ш,|,ш)

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

В разделе 4.4 приводится алгоритм для двумерного случая, доказательство его оптимальности и оценки сложности

Наконец, в разделе 4.5 приводятся некоторые соображения о сложности поиска [6]

Вводится отношение частичного порядка на множестве прямоугольников и рассматривается одномерный случай, при котором правильные прямоугольники образуют цепь Кроме того, рассматривается контрольная выборка из одного элемента Таким образом, задача поиска оптимального порога сводится к нахождению максимума функции /(х) = х—д(х), заданной на конечном множестве точек {1, , где д(х) - некоторая монотонная функция Точки {1, , £} соответствуют правильным прямоугольникам или, что в данном случае равносильно, объектам класса 1 вспомогательной задачи Функция д (х) определяется количеством объектов класса 0, попадающих между соседними границами. Показывается, что для восстановления функции /(ж) необходимо знание ее значений «практически»во всех точках

Утверждение 1. Пусть функция /(ж) = х—д{х) определена на множестве Т = {1, ,£}, д(х) монотонна, 0 < д(х) < С? > Ь, и к - минимальное количество точек, которых достаточно для определения значения /(х) на всем множестве Т Тогда справедливо неравенство

Это утверждение даёт основание отказаться от поиска точного максимума высоты, который, видимо, требует перебора значительной части правильных прямоугольников, и искать приближенные схемы, позволяющие быстро работать с большими размерностями Такие схемы будут предложены в в главе 5

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

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

В разделах 5.2-5.4 приводятся описания приближенных методов поиска ABO максимальной высоты

Жадный алгоритм В качестве исходного прямоугольника берется объемлющий правильный прямоугольник После этого на каждом шаге рассматриваются все правильные подпрямоугольники максимального ранга, из которых выбирается один, наилучшего качества Этот прямоугольник выбирается в качестве основного для следующего шага Метод останавливается, когда качество найденного прямоугольника превышает текущий ранг

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

Метод Количество совпадений Отношение высот > 90%

Жадный 3 8

Покоординатный 9961 10000

Генетический 1 45 1737

Генетический 2 4555 9602

Генетический 3 3565 9843

Таблица 2 Время работы методов

Метод Время обработки 10000 задач, с

Жадный 22

Покоординатный 42

Генетический 1 108

Генетический 2 2228

Генетический 3 236

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

Генетический алгоритм оперирует небинаризованными векторами границ прямоугольников, с естественными операциями скрещивания и мутации

Раздел 5.5 посвящен сравнительному тестированию методов Проводился следующий тест, были сгенерированы 10000 таблиц с заданным оптимальным прямоугольником К каждой из таблиц применялись по очереди жадный алгоритм, метод покоординатного подъема и три генетических алгоритма с разным набором параметров В таблицах 1, 2 приводится количество задач, на которых произошло точное совпадение найденного результата с оптимальной высотой, количество задач, на которых отношение высот составило более 90%; и время обработки

Метод покоординатного подъема лидирует с большим отрывом Глава 6 посвящена реализации метода распознавания на базе элементарных оптимальных ABO

В разделе 6.1 описывается возможная схема уменьшения степени корректного полинома для конкретной задачи Схема основана на точном методе максимизации высоты, и поэтому практически не реализовывалась Вместо

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

Метод построения корректного полинома над ABO должен последовательно построить базовый набор алгоритмов и собственно полином, минимальной, по возможности, степени В разделе 6.1 рассматривается специальный класс ABO, состоящий из всех возможных разностей двух операторов {А — В], где А, В - ABO Показано, каким образом точный метод можно модифицировать для поиска алгоритма максимальной высоты в {А — В} Поскольку Ю И Журавлёвым доказано, что в этом классе существует набор базисных операторов, они будут найдены точным методом

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

¿МО*.

t=l

Здесь Вг - найденные элементарные слагаемые, сг - нормирующий коэффициент, однозначно определяемый по слагаемому Ви кг - степень слагаемого, которую надо найти.

В работе Ю И Журавлева и И В. Исаева, показано, что имея базис, корректный полином можно построить, взяв достаточно большие степени слагаемых Оптимизация проводится по переменным (ki, ,kq) G Zq, кг > О Необходимо минимизировать величину К (либо тахг(кг)), при этом должны быть выполнены неравенства, обеспечивающие корректность полинома, а именно1

||¿M0*Wlks,) > «¿MO^IUj = 1, . ,q}d¿K(S,)-t

i=i i=i

где K(S3) - номер класса, которому принадлежит j-й контрольный объект, ||B(S)||d - оценка объекта S за класс K¿ оператором В Взяв в качестве наг чального решения полином первой степени, и последовательно увеличивая на единицу одну из степеней таким образом, чтобы исключить максимум неправильных неравенств, получим в итоге корректный полином (аналогичная схема используется для второго функционала).

Основным недостатком схемы является низкая скорость при использовании точного метода, либо невозможность гарантировать положительность высоты слагаемых, при использовании приближенных аналогов Поэтому для решения практических задач применяется другой метод, не приводящий, вообще говоря, к построению корректного полинома Метод «АВО-полином»был реализован программно, его описание и результаты работы представлены в пунктах 6.2, 6.3

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

г,(5) = £ г ;(s)/d(s,n

1=1,п

где d - евклидово расстояние

Метод «АВО-полином»реализован программно. В разделе 6.3 приводятся результаты его сравнительного тестирования с одиночным алгоритмом вычисления оценок, методом «логические закономерности», линейной машиной Тестирование проводилось с использованием семи реальных задач, взятых из «UCI Repository of Machine Learning Databases» Abalone, Breast-canser, Ionosphere, Echocardiogram, Hepatitis, Image, Credit Все таблицы были заранее разбиты на обучающую и тестовую выборки. Последняя использовалась для проверки качества работы алгоритма и в обучении не участвовала Результаты численных экспериментов представлены в таблице 3 Можно утверждать, что построенный метод «АВО-полином»показал отличный результат

Задача Простой ABO ЛЗ JIM АВО-полином

Abalone 57 3 - 65.5 62 3

Breast-canser 06.3 94.1 95.5 961

Ionosphere 819 89 6 85 2 98.7

Echocardiogram 761 59 2 70 4 77.4

Hepatitis 79 5 83.1 78 3 88.0

Image 89 0 93.2 92 7 89 4

Credit 86.2 77 9 85 9 86.2

Список основных публикаций по теме диссертации

[1] Докукин А А О построении в алгебраическом замыкании одного алгоритма распознавания //Ж Выч Мат Мат Физ, 2001, т 41, №12, стр 1873-1877

[2] Докукин А.А Индуктивный метод построения корректного алгоритма в алгебрах над моделью вычисления оценок //Ж Выч Мат Мат Физ, 2003, т 43, №8, стр. 1311-1315.

[3] A A Dokukin One Approach for the Optimization of Estimates Calculating Algontms // International Journal „Information Theons k Applications", 2003, vol 10, pp 465-467.

[4] Докукин А А Об одном подходе к оптимизации ABO // Доклады 11-й Всероссийской конференции «Математические методы распознавания образов (ММРО-11)», 2003, стр 68-70.

[5] Dokukin A A Optimal method for constructing of AEC of maximal height m the context of pattern recognition // Pattern Recogn. and Image Analys V. 15. No. 1 2005 pp. 49-51

[6] Докукин А А О сложности поиска оптимального в некотором смысле ABO // Доклады 12-й Всероссийской конференции «Математические методы распознавания образов (ММРО-12)», 2005, стр. 299-302

[7] Докукин А А Об одном методе построения оптимального алгоритма вычисления оценок // Ж Выч Мат Мат. Физ, 2006, т 46, №4, стр. 754-760

[8] Докукин А А О построении выборок для тестирования приближенных методов оптимизации алгоритмов вычисления оценок //Ж Выч Мат

Мат Физ, 2006, т 46, №5, стр 978-983 [9] Dokukin A A Genenlization of the Method for Constructing Maximum-Height Estimate-Calculating Algorithms to Recognition Problems // Pattern Recogn and Image Analys V 16 No 4 2006 pp 689-694 [10] Докукин А А. Индуктивный поиск оптимального алгоритма вычисления оценок // Доклады 13-й Всероссийской конференции «Математические методы распознавания образов (ММРО-12)», 2007, стр 122-124

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

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

Введение

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

2 Операции над ABO. Алгебры.

3 Корректные алгоритмы. Теорема существования корректного алгоритма.

4 Оптимальный метод поиска ABO максимальной высоты.

4.1 Переход к вспомогательной задаче.

4.2 Обоснование оптимальности метода.

4.3 Метод поиска оптимального параллелепипеда во вспомогательном пространстве.

4.4 Метод поиска оптимального параллелепипеда во вспомогательном пространстве для двумерного случая.

4.5 О трудоёмкости задачи поиска оптимального прямоугольника.

5 Приближенные методы поиска оптимального прямоугольника.

5.1 Алгоритм построения тестовых выборок.

5.2 Жадный алгоритм.

5.3 Метод покоординатного подъема.

5.4 Генетический алгоритм

-35.5 Тестирование методов.

6 Реализация метода распознавания на основе алгоритмов поиска ABO максимальной высоты.

6.1 Оптимальная схема.

6.2 Приближённый метод, программная реализация.

6.3 Результаты тестирования.

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

Основой для исследований послужили результаты теории распознавания, полученные Ю.И. Журавлёвым в 70-х годах прошлого века. В частности, им была доказана возможность представления алгоритмов распознавания в виде композиции распознающего оператора и решающего правила [14], что позволило ввести разнообразные операции на множестве алгоритмов и перейти к рассмотрению алгебраических замыканий моделей алгоритмов.

Тогда же [15] в качестве модельного алгоритма для теоретических выкладок был предложен алгоритм вычисления оценок (ABO) [18,19]. Несмотря на то, что ABO во многом используется как некий универсальный язык описания алгоритмов распознавания, он может быть использован и использовался для решения прикладных задач самостоятельно. В частности, В.В. Рязановым предложен метод обучения ABO, основанный на оптимизации по параметрам, характеризующим представительность эталонных строк [33].

Понятие корректности алгоритма [14] возникло из практики проверки качества распознавания на независимой выборке. Алгоритм корректен для заданной выборки, если не делает на ней ошибок.

В [15] было введено понятие регулярности задачи распознавания и доказана теорема о существовании корректного алгоритма в алгебраическом замыкании ABO для любой регулярной задачи. Основным ограничением, которое накладывает определение регулярности, является неизморфность объектов контрольной выборки. В.Л. Матросо-вым позже было показано [25], что вероятность изоморфизма объектов в евклидовом пространстве равна нулю.

В [16] были получены первые оценки степени корректного полинома и рассмотрены вопросы его устойчивости.

Результаты Ю.И. Журавлёва получили дальнейшее развитие в работах его учеников. Основные исследования корректности алгебраических замыканий развивались в двух направлениях.

Во-первых, велись исследования по оценке степени корректного полинома для регулярных задач. Первые результаты были получены в работе [17]. Было показано, что степень полинома зависит от некоторой вычисляемой характеристики слагаемых, которая в дальнейшем для краткости будет называться высотой. Это разность минимальной среди оценок контрольных объектов за класс, к которому они принадлежат, и максимальной - за класс, к которому они не принадлежат. Идея максимизации высоты слагаемых является ключевой для настоящей диссертации.

Дальнейшие результаты по оцениванию степени корректного полинома были получены JI.B. Матросовым. В частности, им был доказан критерий корректности замыкания семейства ABO конечной степени [23]. На основании этого критерия была показана неполнота линейного замыкания модели ABO и квадратичного её замыкания, соответственно, JI.B. Матросовым [26] и Т.В. Плохониной [28]. Аналогичный результат был получен для общего случая: замыкание фиксированной степени не содержит корректного алгоритма для всех задач распознавания [27].

Также JI.B. Матросов улучшил верхние оценки степени и количества слагаемых для классического семейства ABO и его замыкания [24]. Кроме того, им было предложено обобщение ABO, так называемое, семейство ABO над упорядоченным полем G [27], в котором оценки принадлежности являются не числом, а элементом поля G. Было показано, что это семейство, расширенное с помощью дополнительных многоместных операций, содержит корректный алгоритм в линейном замыкании [27].

Неулучшаемая верхняя оценка степени корректного полинома была получена А.Г. Дьяконовым [13] с использованием введённых Л.В. Матросовым операторов разметки [22].

Параллельно К.В. Рудаковым была разработана теория универсальных и локальных ограничений [32]. В основе этой теории лежит идея, что одной прецедентной информации, или корректности на заданной выборке, недостаточно, чтобы гарантировать хорошее качество алгоритма. К.В. Рудаков предложил математический язык описания дополнительных ограничений на отображения, реализующие распознающий алгоритм, которые он назвал универсальными, в отличие от локальных прецедентных [29, 30]. В рамках этой теории были исследованы проблемы разрешимости задач и регулярности с точки зрения непротиворечивости локальных и универсальных ограничений; проблема полноты классов алгоритмов, т.е. разрешимости в его рамках всех регулярных задач [31].

Также К.В. Рудаковым были получены оценки минимальной степени полиномиальных семейств корректирующих операций [32]. Эти результаты отличаются от результатов А.Г. Дьяконова, поскольку К.В. Рудаков рассматривает распознающие операторы в виде композиции собственно распознающего оператора и корректирующей операции. Им же доказано, что неполнота семейства корректирующих операций не влечёт неполноты семейства алгоритмов, поскольку множество распознающих операторов может быть достаточно разнообразно само по себе.

Настоящая диссертация посвящена построению методов максимизации высоты ABO, а также созданию на их основе алгоритмов минимизации степени корректного полинома и методов построения высокоточных алгоритмов распознавания. Оптимизация слагаемых ведётся по порогам функции близости, что отличает схему от упомянутых результатов В.В. Рязанова. Работа состоит из шести глав.

1. Дивеев А.И., Северцев Н.А. Метод выбора оптимального варианта технической системы. М.: ВЦ РАН. 2003.

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

3. Докукин А.А. Индуктивный метод построения корректного алгоритма в алгебрах над моделью вычисления оценок // Ж. вычисл. матем. и матем. физ. 2003, т. 43, №8, стр. 1311-1315.

4. А.А. Dokukin. One Approach for the Optimization of Estimates Calculating Algoritms // International Journal „Information Theoris & Applications", 2003, vol. 10, pp. 465-467.

5. Докукин А.А. Об одном подходе к оптимизации АВО // Доклады 11-й Всероссийской конференции „Математические методы распознавания образов (ММРО-11)", 2003, стр. 68-70.

6. Dokukin А.А. Optimal method for constructing of AEC of maximal height in the context of pattern recognition // Pattern Recogn. and Image Analys. V. 15. No. 1. 2005. pp. 49-51.

7. Докукин А.А. О сложности поиска оптимального в некотором смысле АВО // Доклады 12-й Всероссийской конференции „Математические методы распознавания образов (ММРО-12)", 2005, стр. 299-302.

8. Докукин А.А. Об одном методе построения оптимального алгоритма вычисления оценок // Ж. вычисл. матем. и матем. физ.,-992006, т. 46, т, стр. 754-760.

9. Докукин A.A. О построении выборок для тестирования приближённых методов оптимизации алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ., 2006, т. 46, №5, стр. 978-983.

10. Dokukin A.A. Generilization of the Method for Constructing Maximum-Height Estimate-Calculating Algorithms to Recognition Problems // Pattern Recogn. and Image Analys. V. 16. No. 4. 2006. pp. 689-694.

11. Докукин A.A. Индуктивный поиск оптимального алгоритма вычисления оценок II Доклады 13-й Всероссийской конференции „Математические методы распознавания образов (ММРО-12)", 2007, стр. 122-124.

12. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976, 511 с.

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

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

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

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

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

18. Журавлёв Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение Ташкент: „Фан", 1971.

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

20. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука. Д984.

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

22. Матросов B.JI. О критериях полноты модели АВО и её алгебраических замыканий // Доклады академии наук СССР, 1981, т. 258, №4, стр. 791-796.

23. Матросов B.JI. Оптимальные алгоритмы в алгебраических замыканиях операторов вычисления оценок // Доклады академии наук СССР, 1982, т. 262, №4, стр. 818-822.

24. Матросов B.JI. О вероятности изоморфизма пар допустимых объектов регулярных задач // Ж. вычисл. матем. и матем. физ., 1983, т. 23, т.

25. Матросов B.JI. О неполноте модели ABO // Ж. вычисл. матем. и матем. физ., 1983, т. 23, №2.

26. Матросов B.JI. Корректные алгебры алгоритмов распознавания ограниченной ёмкости: Дис. . докт. физ.-матем. наук. М. 1985.

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

28. Рудаков К.В. О некоторых универсальных ограничениях для алгоритмов классификации // Ж. вычисл. матем. и матем. физ., 1986, т. 26, №11, стр. 1719-1726.

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

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

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

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

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

34. Ryazanov V.V. Recognition Algorithms Based on Local Optimality Criteria // Pattern Recognition and Image Analysis. 1994. Vol.4, no.2. pp. 98-109.

35. Ryazanov V.V. About some approach for automatic knowledge extraction from precedent data // Proceedings of the 7th international conference „Pattern recognition and image processing", Minsk, May 21-23, 2003, vol. 2, pp. 35-40.

36. Обухов А.С., Рязанов В.В. Применение релаксационных алгоритмов при оптимизации линейных решающих правил // Доклады 10-й Всероссийской конференции „Математические методы распознавания образов (ММРО-Ю)", Москва, 2001, 102-104.

37. William Н. Wolberg and O.L. Mangasarian Multisurface method of pattern separation for medical diagnosis applied to breast cytology // Proceedings of the National Academy of Sciences, U.S.A., Volume 87, December 1990, pp. 9193-9196.