автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Проблема обоснования качества классов алгоритмов с универсальными ограничениями монотонности

у*

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

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

СЁМОЧКИН Александр Николаевич

ПРОБЛЕМА ОБОСНОВАНИЯ КАЧЕСТВА КЛАССОВ АЛГОРИТМОВ С УНИВЕРСАЛЬНЫМИ ОГРАНИЧЕНИЯМИ МОНОТОННОСТИ

05.13 Л 7 - Теоретические основы информатики

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

действительный член РАО, 0г доктор физико-математических наук,

ч» профессор В.Л. Матросов

Москва —1998

ОГЛАВЛЕНИЕ

Введение

0.1 Эволюция задачи распознавания образов.....................................................4

0.2 Об исходных конструкциях алгебраического подхода...............................10

0.3 О теории универсальных и локальных ограничений..................................13

0.4 Качество и надежность алгоритма...............................................................15

0.5 Цель, методы и содержание работы по главам...........................................18

Глава I Проблема обоснования качества решения задачи распознавания с универсальными ограничениями монотонности

1.1 Исходные положения алгебраической теории универсальных

и локальных ограничений для алгоритмов распознавания..........................22

1.2 О полноте универсальных ограничений для алгоритмов классификации................................................................................................27

1.3 Проблема обоснования качества решения задачи распознавания...............30

1.4 Определение линейного достроения частичного порядка...........................35

1.5 Описание одного класса алгоритмов распознавания с универсальными ограничениями монотонности.......................................................................37

1.6 Постановка задачи..........................................................................................44

Глава II Линейные достроения частичного порядка на конечных множествах

2.1 Число линейных достроений для частичного порядка, задающего две непересекающиеся цепи.................................................................................47

2.2 Плотность и однородность частичного порядка...........................................54

2.3 Оценки числа линейных достроений частичного порядка с заданными характеристиками порядка.............................................................................57

Глава III Оценки функционала качества для класса

алгоритмов с универсальными ограничениями монотонности

3.1 Исследования класса всех монотонных отображений..................................63

3.2 Случай диагонального частичного порядка..................... ..............................65

3.3 Случай линейного порядка.............................................................................66

3.4 Общий случай задания частичного порядка на множестве объектов..........69

3.5 Исследование применимости полученных оценок........................................77

3.6 Оценка количества монотонных дихотомий для одного класса частичных порядков на конечном множестве...............................................80

3.7 Оценки скорости сходимости функционала качества...................................84

Заключение........................................................................................................87

Литература........................................................................................................88

Введение

0.1 Эволюция задачи распознавания образов

Одной из ключевых проблем информатики является разработка,

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

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

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

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

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

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

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

моделирование и составило основную цель исследований. История этого направления началась с момента создания первого персептрона [32], затем была создана система General Problem Solver [12] и т.д. В последствии работы в данном направлении приобрели практическую направленность в контексте синтеза экспертных систем.

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

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

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

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

Таким образом, предпринимались попытки строить единообразные описания принципов формирования отдельных семейств эвристических алгоритмов. Подобные семейства задаются указанием переменных, объектов, функций, параметров и точным определением областей их вариации. Фиксация переменных, объектов, функций, параметров позволяет выделить из соответствующего семейства (модели алгоритмов) некоторый конкретный алгоритм. Для каждой практической задачи теперь оставалось лишь выбрать наиболее подходящее из интуитивных соображений параметрическое семейство алгоритмов и выбрать такие значения параметров, которые выделяют из семейства оптимальный для данной конкретной задачи алгоритм. Впервые в виде модели был представлен класс алгоритмов вычисления оценок [2,18], позднее появились описания моделей алгоритмов, основанных на принципе комитетных решений [5,28], на методе потенциальных функций [1,40], статистические [9,10] и структурные [17,13] семейства. Отметим, что модели

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

При всем разнообразии моделей общей принципиальной сложностью является проблема поиска в рамках модели оптимальных алгоритмов для конкретных задач. Для многих задач эта проблема имеет классические аналоги: поиск экстремумов функций, метод минимизации среднего риска. Например, модель распознавания, в которой строится разделяющая гиперплоскость, имеет родственную классическую задачу максимизации некоторой квадратичной формы в положительном квадранте, поэтому алгоритмы перцептронного типа реализуют модифицированный метод подъема Гаусса-Зейделя [9].

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

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

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

путь: из имеющихся семейств можно определенным образом выбирать некоторые алгоритмы и, используя подходящие операции над алгоритмами (корректирующие операции), целенаправленно строить оптимальные алгоритмы для конкретных задач. Эта идея была использована в исходных работах [22-25], в которых в качестве корректирующих операций применялись некоторые операции над действительными матрицами, а в качестве исходных семейств алгоритмов рассматривались алгоритмы, основанные на принципе разделения, и алгоритмы вычисления оценок.

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

Перейдем к математической постановке задачи распознавания образов или классификации.

0.2 Об исходных конструкциях алгебраического подхода

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

Существенно, что число классов / заранее известно и фиксировано для рассматриваемого множества задач или конкретной задачи.

Информация о принадлежности объекта £ классу к обычно выражается элементами некоторого множества ¿7={0,1,Д}, где 0 интерпретируется как решение £ ек, 1 — 5 <£к, а — как отказ от принятия решения. В общем случае множество «допустимых ответов» ¿7 определяется содержательной стороной дела.

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

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

функция И:3 —» которая сопоставляет объектам £ их допустимые

описания £>(£).

В простейшем случае алгоритмы в «рабочем режиме» реализуют отображения из й' в с7 . Иначе говоря, при поступлении на вход алгоритма а

описания е еТ^ объекта £0 из множества Б (/0 = )) на выходе

порождается вектор , в котором /? является допустимым ответом

алгоритма а на вопрос о принадлежности объекта ^ классу к] при

У е{1,...,/}.

Обозначим через предикат, выражающий априорно

известную информацию о принадлежности объекта £ классу с номером у, через сг (5) е<_7 результат работы алгоритма, содержащий информацию о

принадлежности объекта £ классу с номером у

Определение 0.2.1. Вектор а =(а1,...,а1) е ¿7' называется информационным

вектором для объекта Я, если а/ = aJ(S). Информационный вектор объекта &

называется полным, если а/ Ф А,/ = 1,...,/. Вектор а называется корректным

для 5, если из условия а] * А следует, что а] = Р](5), у = 1,2,...,/. Корректный

для £ полный вектор а называется истинным для

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

% е. 34 е , называемом обучающей выборкой, и сопоставленный этому набору объектов набор информационных векторов (ап...,ач) из множества (С71 у. Информационные векторы объектов ^ (при /е1,д) обозначим - (ап,...,аи) £¿7', где величины ау интерпретируются как описания информации о принадлежности объекта классу К] (а. £¿7).

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

£ е5,г е , он порождал финальную информацию (а^,...,ач).

Пусть определено пространство ¿7, элементы которого суть допустимые совместные описания объектов и классов (классы характеризуются содержащимися в них объектами). При наличии выборки (5,,..., ^ ) из

пространства допуст�