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

Введение.

Глава I. Польше замыкания семейств распознающих операторов

§ I.I. Описание модели алгоритмов в задачах с дискретной обучающей информацией.

§ 1.2. Доказательство полноты семейства операторов

Глава 2. Синтез корректного алгоритма

§ 2.1. Построение базисных операторов в алгебраических замыканиях.

§ 2.2. Задача разделения множеств.

Глава 3. Емкостные характеристики модели алгоритмов с дискретной обучающей информацией.

§ 3.1. Оценки для емкости линейного замыкания.

§3.2. Емкость алгебраического замыкания конечной степени

Теория распознавания и классификации образов в последние десятилетия является одной из центральных областей прикладной математики и математической кибернетики. Методы распознавания образов находят применение в важных прикладных задачах технической и медицинской диагностики, геологического и социологического прогнозирования, систем обработки информации и ряда других областей. Большое число появившихся к настоящему времени алгоритмов для решения задач распознавания позволило придать содержательной постановке таких задач четкие математические формулировки, а также определить некоторые общие требования к классам алгоритмов, способных успешно решать эти задачи. Переход от рассмотрения отдельных распознающих алгоритмов к классам или моделям алгоритмов, а в последнее время - к синтезу моделей из заданной совокупности моделей [12] - привел к исследованию проблемы выбора алгоритмов, удовлетворяющего определенным экстремальным условиям*

Будем под задачей распознавания 2 <1о, £?> со стандартной обучающей информацией 1о понимать проблему установления принадлежности объектов некоторого конечного подмножества из множества допустимых объектов И данным классам А"/,., К е. » образующим покрытие М .

Для ряда распространенных моделей распознавания ¡алгоритмов вычисления оценок, разделения, статистических, потенциальных функций и других алгебраическими методами установлен ряд результатов относительно существования в модели точной распознающей процедуры для произвольной задачи со стандартной информацией [4] , [II] , [18] . В работах [26] , [27] изучены общие вопросы, связанные с полнотой и построением экстремальных моделей алгоритмов.

Стандартная начальная информация 1о представляет совокупность описаний объектов из множества <=М с известной классификацией в пространстве признаков Мух. х Мц. Для изученных моделей алгоритмов важную роль играет то обстоятельство,что они применяются преимущественно к задачам, в которых множества описаний являются метрическими (или полуметрическими) пространствами с метриками ^/7-7^/7 • При этом метрика (в частности, евклидова) может служить мерой сходства распознаваемых объектов и эталонов по отдельным признакам, принимающим значения из некоторого основного континуума. Задачи такого рода будем называть задачами с непрерывной начальной информацией. Для таких задач при задании функции близости, использующей данные метрики и меры точности измерений <£/,., £п , можно получить богатые параметрические модели распознавания.

С другой стороны, существует ряд прикладных задач, в которых переменные (признаки) принимают дискретные значения. Эти переменные в отличие от шкал интервалов или порядка представляют скорее качественную, номинальную шкалу наименований, чем числительную шкалу. Необходимость в преимущественно дискретных (в частности, бинарных) измерениях появляется во многих практических системах распознавания либо из-за самой сущности задачи,как, например, классификация симптомов в автоматической диагностике заболеваний, либо из-за выбора признаков (при обработке и распознавании изображений, в геологическом прогнозировании и т.д.). Однако, несмотря на практическую важность задач с дискретной информацией существует немного математических средств, пригодных для их решения. В таких задачах возникают значительные трудности при построении точного классификатора. Для дискретных признаков изменение отдельных значений от одного уровня до другого может вызвать значительное изменение объекта. В отличие от непрерывного случая здесь не существует устойчивости, то есть настолько малых изменений переменных, что они оставляют образ неизмененным [дЗ] . В силу этого факта и отсутствия внутренней упорядоченности, трудно описать распределение векторов признаков простыми параметрическими моделями. При статистическом подходе, чтобы получить оценки распределения, приходится накладывать ряд ограничений (попарная независимость признаков). Другие методы, в частности, геометрические (метод ближайших соседей [9] , линейный дискриминант Фишера) трудноприменимы или малоэффективны в силу того,что евклидова метрика,использующаяся в них, не является, вообще говоря,в таких задачах мерой сходства.Можно выделить теорию "главных событий"/ЗЗ? и основанную на ней методику для построения дерева решений, чтобы получить множество прототипов для каждой категории образов /32/. Получающийся при этом алгоритм не всегда ведет к оптимально^ дереву решений.

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

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

Из класса алгоритмов, содержащихся в описанной модели, следует выделить тестовые алгоритмы, базирующиеся на введенном в [ЗИ] понятии теста для дискретных таблиц. Системой опорных множеств в этих алгоритмах служат наборы тупиковых тестов - минимальных описаний, не содержащихся более, чем в одном классе. Тестовые алгоритмы нашли успешное применение в ряде прикладных задач распознавания [в] , [19] , [20] . Проблема создания вычислительных методов, реализующих тестовые алгоритмы, привела к изучению свойств и характеристик тестов для бинарных таблиц [23] , [2.9], [зо] , и построению алгоритмов синтеза совокупности тупиковых тестов (Ш, Н) - таблиц при определенных соотношениях между ¡11 и П [10] .

Сходные идеи проявляются в других алгоритмах описанной модели. Так, в известном алгоритме "Кора" [ь] в качестве опорных множеств выбираются по каждому классу конъюнкции небольшого числа (двух-трех) переменных таким образом, чтобы каждая конъюнкция соответствовала только одному классу. При этом параметры выбираются из множества {о, I, -1} . Решение, как и в случае тестовых алгоритмов, принимается путем "голосования" полученных по каждому классу оценок принадлежности. Ряд других алгоритмов квазилинейного типа описан в [2] .

Все рассмотренные алгоритмы относятся к числу эвристических алгоритмов распознавания. Их характерной особенностью является то, что они базируются на некоторых интуитивных предположениях о классах решаемых задач, например, о законе распределения объектов, о геометрическом расположении распознаваемых образов и т.п. Применимость того или иного алгоритма при решении конкретной задачи определяется достаточно высоким качеством распознавания, В то же время эвристические алгоритмы могут неточно классифицировать часть предметов или явлений, подлежащих классификации. Рассматривая совокупность алгоритмов как параметрическую модель, можно выбирать оптимальный алгоритм, решая экстремальную задачу относительно некоторого функционала качества, например, обобщенной ошибки распознавания контрольной выборки. Другой путь связан с переходом к расширениям исходных моделей алгоритмов при помощи алгебраических операций ГП^ , Г12] . Этот способ позволяет избежать решения трудных задач многопараметрической оптимизации. Основной целью настоящей работы явилось исследование вопросов существования и синтеза алгоритмов в алгебраических пополнениях данных моделей, точно решающих произвольную задачу с дискретной обучающей информацией.

Определение. Алгоритм АС Ж) называется корректным для задачи I К То, З^У , заданной обучающей информацией То и описаниями предъявленной выборки Я*,., » если

А сг <то, г*?) = И ухе, где Д/ - значения предикатов Р^' (в1) К/, ¿=<2,.6

Каждый алгоритм из рассматриваемых моделей представляется в виде последовательного выполнения двух операторов: А - В°С Здесь В - распознающий оператор, вычисляющий по каждому классу оценки принадлежности объекта, С - решающее правило алгоритма, производящее окончательную классификацию. В работах ГII], [127 сформулирована общая теорема существования корректного алгоритма над классом задач /"¿Г < То,

Теорема. Если семейство распознающих операторов {8} является полным над классом задач { £ , в $ , то в линейном замыкании ^ {в} 0 С- при произвольном корректном решающем правиле С для любой задачи ¿Г существует корректный алгоритм А (Е<1о, Р^}) .

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

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

Алгоритм в замыкании, вырабатываемый по обучающей выборке, как указывалось выше, может безошибочно классифицировать элеменV ты контрольного множества 3 ° . Очевидно, если контрольная выборка достаточно большая и представительная, то лучшее решение задачи распознавания сводится к подбору параметров, позволяющих выбрать алгоритм, совершающий как можно меньше ошибок на этой выборке. Для точного анализа ошибок классификации алгоритма применима теория минимизации эмпирического риска Г 6 Л , £77.

Дело в том, что безошибочность на контрольной выборке сама по себе еще не гарантирует алгоритму хорошего качества распознавания других объектов. Задача построения алгоритма, обеспечивающего высокую точность распознавания, может решаться, как правило, в тех случаях, когда искомый алгоритм заведомо принадлежит достаточно узкому классу алгоритмов. Уточнение понятия "достаточно узкий класс" сделано в работе С 7 1. Основная идея заключается в следующем. Класс алгоритмов характеризуется вели

- е чиной, называемой емкостью класса и показывающей величину объема максимальной выборки объектов, делящейся всеми возможными способами с помощью алгоритмов данного класса. Исследование ряда классов правил показало, что в большинстве случаев емкость класса ограничена и равна числу настраиваемых при обучении параметров £61, Г7 3 , Г 331. Для классов с конечной емкостью можно установить гарантированные оценки качества распознавания, другими словами, решая непараметрическую задачу распознавания и не пользуясь никакими сведениями о вероятностных распределениях, получить оценки вероятности ошибки распознавания и минимизировать функционал риска.

В работах Г 231 , [ 24 3 , рассмотрена задача о выполнении достаточных условий равномерной сходимости частот ошибок распознающих алгоритмов к их вероятностям для подклассов алгебраического замыкания алгоритмов вычисления оценок и получены верхние оценки емкости корректных алгебраических замыканий для задач с непрерывной обучающей информацией.

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

Приведем содержание работы по главам. В первой главе дается описание двух основных рассматриваемых моделей алгоритмов, предназначенных для решения задач с дискретной обучающей информацией. Рассматриваются параметрические семейства операторов с т + п, /Т7+Г7+2 вещественными параметрами, соответственно, и корректное решающее правило С зачисления в класс по максимуму, оценки. Обучающая информация задается в виде дискретной таблицы обучения Tnm£ , разбитой на i классов и содержит описания объектов обучения SSm&fyx,xМл » где каждое Mi является дискретным множеством значений I -го признака.

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

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

Klo ,S*> и доказаны теоремы:

Теорема I.I. Пусть для задачи £ <" 1о, ¿^У выполнено условие разделимости двух произвольных контрольных объ

U V ектов S & S по начальной информации 1о . Тогда семейство операторов Ы ({ß-f} U {А , где ЛJ - операторы-константы, J в I, 2, , полно относительно

Теорема 1.2. Если для задачи 2 <То, дополнительно выполняется условие неисчезания любого контрольного объекта в1 по каждое классу Л/ , / = I, 2, ,

1,2,.,/ ,то ¿М {в*} полно относительно 2 ¿То,

Теорема 1.3. Пусть Е* - пространство признаков, в котором каждый признак входит в некоторый тупиковый тест таблицы обучения Тнт€ . Если для задачи Е < То, 5 выполнено условие разделимости двух произвольных контрольных объектов 3 й ф Л* " по начальной информации Ь , то алгебраическое замыкание семейства тестовых алгоритмов ¿8г} полно относительно

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

Вьщелено конечное множество алгоритмов в замыкании, содержащее корректный алгоритм и доказана

Теорема 2.1 Корректный алгоритм может быть записан в виде

А(2)-[£ Г А/ в (с,/)] о с, где е £о, -/} - значения предикатов Р; ( Я1 ),

В(с,])е ся{в}.

В параграфе 2.2 рассмотрены критерии проверки выполнимости условий полноты. Сформулирована задача разделения исходного информационного массива на два множества с заданными свойствами .

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

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

Теорема 3.1. Емкость модели не превосходит произведения размерностей векторов параметров = и р*(р*,.,р»>.

4 777/7 и, соответственно,

ХШ'С * 2 тп

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

В параграфе 3.2 оценивается емкость корректного алгебраического замыкания **{3}°С конечной степени @ . Показано, что з семейство алгоритмов из (Я , содержащее корректный алгоритм, вкладывается в множество алгоритмов разделения гиперплоскостями в пространстве размерности С^ , где $в ^¿т Х{в}. в качестве следствия получена

Теорема 3.2 гб*.?-/;/

3/(3

Далее рассмотрено асимптотическое поведение степени алгебраического замыкания как функции параметров таблицы обучения, при котором емкость оценивается величиной бесконечно малой относительно объема пространства объектов распознавания. Пусть а (т,п) = о(еп£елт)> ОМ <т(п)4 £

7,/77 со.

Тогда

Н^ а 4 2 П<< , /7 — во.

Основное содержание диссертации изложено в публикациях [14], [ 15 ] , [ 16] . Результаты работы докладывались на II республиканской конференции молодых ученых УАССР, на семинаре в Вычислительном центре АН СССР, на ряде семинаров в Ижевском механическом институте.

Автор выражает искреннюю признательность Ю.И.ЖУРАВЛЕВУ и сотрудникам лаборатории проблем распознавания Вычислительного центра АН СССР за сотрудничество и подцержку. Автор глубоко благодарен научно^ руководителю Н.И.КАЛЕДИНУ за помощь и постоянное внимание к работе.

1. Айдарханов M.Б. Алгоритмы распознавания в континуальной обучающей информации. 1. - Ж. вычисл. матем. и матем. физ., 1981, т. 21, îfi 6, с. I544-1551.

2. Алгоритмы обучения распознаванию образов. Под редакцией В.Н.Вапника. М.: Советское радио, 1973. - 200 с.

3. Алексеев В.М., Тихомиров В.М., Фомин C.B. Оптимальное управление. М.: Наука, 1979. - 432 с.

4. Бак Хынг Кханг. 0 полноте модели статистических алгоритмов распознавания. Ж. вычисл. матем. и матем. физ., 1978,т. 18, № I, с. 183-196.

5. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов "Кора". В кн.: Алгоритмы обучения распознаванию образов. - М. : Советское радио, 1973, с. II0-II5.

6. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. - 448 с.

7. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов.-IL : наука, 1974. 416 с.

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

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

10. Дюкова Е.В. Об асимптотически оптимальном алгоритме построения тупиковых тестов для бинарных таблиц. В кн.: Проблемы кибернетики. Вып. 34. М.: Наука, 1978, с. 169-186.

11. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I. Кибернетика, 1977,4, с. 14-21, II. Ш 6, с. 21-27, III - 1978, № 2, с.35-43.

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

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

14. Йцков А.Г. О классификационных свойствах модели тестовых алгоритмов. В кн.: Дискретные системы обработки информации. Вып. 3. Ижевск, 1981, с. 89-95.

15. Ицков А.Г. О построении корректного тестового алгоритма. Депонировано в ВИНИТИ, 1981, $ 3350-81 ДЕГ'1. с. 1-18.

16. Ицков А.Г. О емкости модели распознающих алгоритмов вычисления оценок. Ж. вычисл. матем. и матем, физ., 1982. т.22, №4, с. 975-981.

17. Катериночкина И.Н. Поиск максимального верхнего нуля монотонной функции алгебры логики. Докл. АН СССР, 1975,т. 224, № 3, с. 557-560.

18. Колтовой H.A. О полноте линейного пространства распознающих операторов типа вычисления оценок и потенциальных функций. Ж. вычисл. матем. и матем. физ., 1979,т.19,.*2,с. 496-507.

19. Константинов Р.М., Королева З.Е. Применение тестовых алгоритмов к задачам геологического прогнозирования. в кн.: Труды Международного симпозиума по практическим применениям методов распознавания образов. Ы.: ВЦ АН СССР, 1973, с. 194-204.

20. Королева З.Е. 0 сравнении тестовых алгоритмов распознавания. Ж. вычисл. матем. и матем. физ., 1975, т. 15, № 3, с. 749-756.

21. Кристофидес Н. Теория графов. М.: Мир, 1978, - 432 с.

22. Кульянов Е.Г. Алгоритм поиска максимального верхнего нуля произвольной монотонной функции алгебры логики. Ж. вычисл. матем. и матем. физ., 1975, т. 15, № 4, с. 1080-1082.

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

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

25. Носков В.Н. 0 тупиковых и минимальных тестах для одного класса таблиц. В кн.: Дискретный анализ. Вып. 12. Новосибирск: Наука, 1968, с. 27-49.

26. Рудаков К.В. 0 некоторых классах алгоритмов распознавания (общие результаты). М.: ВЦ АН СССР, 1980. - 66 с.

27. Рудаков К.В. 0 некоторых классах алгоритмов распознаванияпараметрические модели). M.: ВЦ АН СССР, 1981. - 48 с.

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

29. Слепян В.А. Вероятностные характеристики распределения тупиковых тестов. В кн.: Дискретный анализ. Вып. 12. Новосибирск: Наука, 1968, с. 50-74.

30. Слепян В.А. Параметры распределения тупиковых тестов и информационные веса столбцов в бинарных таблицах. В кн.: Дискретный анализ. Вып. 14. Новосибирск: Наука, 1969,с. 28-43.

31. Соловьев H.A. Тесты. Новосибирск: Наука, 1978, - 200 с.

32. Чегис И.А., Яблонский C.B. Логические способы контроля электрических схем.- В кн.: Труды Матем. ин-та им. В.А. Стеклова АН СССР. М.: Наука, 1958, т. 51, с. 270-360.

33. Bttfu/t, J.K. Capacity ortet efficiency Ц AlUUcvs -function* ~ IEBB ТЪШ. Comfwt., I m, v. С-26, л/И,р. Ж?Н1Я.