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,., ^) из пространства допустимых объектов 3 должны быть определены элементы /. где /. — совместное описание объекта? и класса К. при г е, д и Л е 1, /. Элементы / объединяются в матрицу / = У называемую матрицей информации для рассматриваемой задачи. Финальную информацию, то есть набор векторов (ах,., а), также удобно записывать в виде матрицы / = а. у называемой информационной матрицей задачи. дх1.
Теперь условие, выражающее прецедентную часть структурной информации, может быть записано в виде равенства а (1) = 7.
В дальнейшем договоримся обозначать пространства, а х Ьматриц над Л множеством Н символом ?7 (-Н). Тогда / е ?7 (?7), I е ?7. (?7). с?, /.
0.3 О теории универсальных и локальных ограничений.
Основная причина, породившая исходную для теории универсальных и локальных ограничений [35−39] проблему, состоит в том, что при решении очень многих задач явно недостаточно рассматривать только прецедентную информацию в качестве единственного фактора, влияющего на результат решения задачи распознавания. Данное соображение становится особенно актуальным в контексте алгебраического подхода, поскольку универсальность его конструкций позволяет при недостаточно точной постановке задачи с легкостью получать формально правильные, но явно бессмысленные с содержательной точки зрения результаты.
Действительно, в задачах классификации в простейшей постановке, например, прецедентная информация полностью описывается парой матриц.
А г^ Л ~.
70,/0), где /0 —матрица информации и /0 информационная матрица задачи. Если теперь ограничиться требованием, чтобы искомый алгоритм, а л.
Л. реализовывал отображение из 1 (?7) в ?7 (?7″) такое, что А (1{)) = /(), то, А формально правильным решением окажется алгоритм а0, который для всех i л из ?7 (?7) порождает /0, то есть реализует константу. Ясно, что удовлетворительная с содержательной точки зрения постановка исходной задачи должна «запрещать» подобные решения, то есть должна содержать дополнительные по отношению к прецедентным ограничения на вид отображений, которые могут реализовываться искомыми алгоритмами. Дополнительные ограничения, например, могут выражаться условием типа «все рассматриваемые объекты однородны и данные о них независимы» и т. п.
Прецедентные ограничения жестко связаны с пространствами ?7 и ?7 и потому рассматриваются и используются только для «целых» алгоритмов. Дополнительные ограничения, напротив могут применяться не только к целому" алгоритму и к классам алгоритмов, но и к конкретным процедурам и структурам, реализованных в алгоритмах. Первый тип ограничений «конечен», то есть за конечное число шагов можно установить, удовлетворяет ли реализуемое алгоритмом отображение этим ограничениям. Второй тип ограничений в принципе может и не допускать такой эффективной проверки. Следовательно, такие ограничения не только могут, но и с необходимостью должны использоваться при выборе или синтезе искомого алгоритма. Тогда получаемые алгоритмы будут удовлетворять таким ограничениям «по построению». Такие дополнительные к прецедентным ограничения называются универсальными ограничениями.
В связи с приведенными соображениями можно уточнить постановку задачи классификации: рассматриваются задачи, в которых структурная информация состоит из двух равноправных частей, выраженных в виде универсальных и локальных (прецедентных) ограничений.
В качестве примера приведем задачу с универсальными ограничениями монотонности. Данный класс задач характеризуется тем, что допускается гипотеза о том, что на множестве объектов 7 и на множестве ответов алгоритмов ?7 существует некоторое отношение порядка и искомые алгоритмы распознавания должны реализовывать монотонные отображения из множества объектов во множество ответов. Очевидно, что алгоритмы из класса, в котором проводится поиск оптимального алгоритма, реализуют не все возможные отображения из ?7 в «У, а только монотонные. Таким образом, в отличие от задачи распознавания, в которой не задано никаких универсальных ограничений, задача с монотонными ограничениями оказывается более точно поставленной.
0.4 Качество и надежность алгоритма.
Модели алгоритмов в задачах распознавания обычно являются параметрическими. Поэтому при поиске алгоритма, удовлетворяющего структурной информации задачи, выбирается такой параметр, когда соответствующий алгоритм доставляет максимум некоторому функционалу качества, определенному на множестве алгоритмов.
Приведем пример функционала качества алгоритма, рассмотренного в.
22].
Пусть,., 5″ есть совокупность допустимых объектов, называемая в дальнейшем контрольной выборкойаг'.=) истинные информационные векторы объектов 5″ - а ' = (аА ,., аА) — информационные 1 iq векторы, построенные для объектов алгоритмом а, / = 1,2. Обозначим через р{а, а') произвольную полуметрику в пространстве информационных векторов.
Рассмотрим последовательность функций / (х), /2 (х, х2),., /г (х,., хг), удовлетворяющую следующим условиям:
1)все /. определены х. > 0,/ = 1,2,.Д;
2) все /. не возрастают по каждой переменной;
3) функция ft достигает абсолютного максимума в точке (0,0,., 0), и этот максимум равен 1.
Определение. Функционалом качества (р{А) по контрольному множеству ,., называется величина.
Тогда оптимальный алгоритм, а в некотором семействе алгоритмов выбирается по критерию близости значения функционала качества (р{А) к своему максимуму на контрольной выборке. Однако на практике очень часто приходиться иметь дело лишь с небольшим числом известных прецедентов, поэтому рамки контрольной выборки ограничены обучающей выборкой. Тогда естественным образом возникает вопрос: какова вероятность того, что алгоритм, верно классифицирующий объекты обучающей выборки, будет правильно классифицировать объекты, не входящие в обучающую выборку. В целях разрешения этой проблемы в работах [9,10] была предложена теория обоснования качества алгоритма распознавания. Суть ее в следующем.
Принимается гипотеза, что на множестве допустимых объектов 3 задана функция распределения вероятностей Р (^), определяющая для каждого объекта 5 вероятность его появления среди элементов, подлежащих классификации. Тогда «потери» от ошибки на объекте 5 могут быть оценены величиной, пропорциональной вероятности появления этой ситуации. Для каждого алгоритма можно подсчитать средние потери от всех его ошибок. Наилучшим алгоритмом следует считать в этом случае тот, который дает минимальные средние потери, то есть обеспечивает минимальную вероятность ошибок при классификации. Существенно, что функция распределения вероятностей не известна. Не смотря на это, качество любого алгоритма может быть оценено эмпирически. Для этого случайно и независимо отбирается некоторое количество примеров, относительно которых известно к какому классу они относятся. На множестве этих примеров определяется процент ошибок, который и характеризует качество алгоритма точно так же, как вычисленная по конечной выборке частота характеризует вероятность.
В статистическом подходе к задачам обучения распознаванию образов предполагается, что обучающая выборка составлена из элементов, выбранных случайно и независимо согласно распределению вероятностей р{б). Однако при таком случайном подборе элементов уже нельзя требовать, чтобы обучение было безусловно успешным: не исключена вероятность того, что обучающая выборка будет составлена только из «нетипичных» случаев. Поэтому успех в обучении может быть гарантирован не наверняка, а лишь с некоторой вероятностью.
Таким образом, можно ввести два понятия: качество и надежность алгоритмов распознавания. Качеством алгоритма назовем вероятность неправильных классификаций алгоритмом элементов случайной и независимой выборки из множества допустимых объектов. Надежностью получения алгоритма с заданным качеством в результате решения задачи распознавания назовем вероятность получения заданного качества алгоритма. Следовательно, задача сводится к отысканию на основании структурной информации (в основном на основании обучающей выборки) в данном семействе алгоритмов такого алгоритма, качество которого с заданной надежностью было бы не ниже требуемого.
В работах [9,10] были получены достаточные условия существования алгоритмов с заданным качеством и надежностью получения этого качества. Результаты теории обоснования качества алгоритмов распознавания впервые были применены В. Л. Матросовым [29−31] к моделям алгоритмов вычисления оценок, для которых были получены достаточные условия существования оптимальных алгоритмов.
Данная теория была рассмотрена для задач распознавания в общем виде, когда вид структурной информации никак не конкретизировался. Достаточные условия, полученные в этой теории, оказываются тривиальными для задач с некоторыми типами универсальных ограничений. В связи с этим проблема обоснования качества решений таких задач остается открытой. Настоящая работа посвящена решению этой проблемы в отношении задач распознавания с универсальными ограничениями монотонности.
0.5 Цель, методы и содержание работы по главам.
Целью данной работы является исследование зависимости надежности получения решения задач распознавания заданного качества от дополнительной информации о монотонности.
Объектом исследования является алгебраическая теория универсальных и локальных ограничения для алгоритмов распознавания образов.
Предметом исследования служат задачи распознавания образов с универсальными ограничениями монотонности.
Проблемой исследования является проблема обоснования качества классов алгоритмов с универсальными ограничениями монотонности.
Для реализации поставленной цели потребовалось решить следующие задачи:
Ввести и исследовать характеристики отношения порядка, определяющие количественные характеристики влияния дополнительной информации о монотонности на надежность решения задач распознавания образов.
Определить понятие и провести исследование процедур линейного достроения частичного порядка на конечных множествах.
Получить оценки функционала качества для класса алгоритмов с универсальными ограничениями монотонности.
Оценить скорость сходимости функционала качества к нулю в зависимости от характеристик частичного порядка на множестве объектов и от разнообразия класса алгоритмов с ограничениями монотонности.
Методологическую основу работы составляют методы дискретного анализа, теории упорядоченных множеств, теории вероятностей, математической статистики, математической теории распознавания образов.
Научная новизна работы заключается в том, что впервые проведено исследование влияния наличия дополнительной информации о монотонности на надежность решения задач распознавания образов, впервые введены и исследованы характеристики частичного порядка — плотность и однородность порядка, определено понятие линейного достроения и исследованы процедуры линейного достроения, получены оценки функционала качества для класса алгоритмов с универсальными ограничениями монотонности и оценена скорость его сходимости в зависимости от характеристик частичного порядка на множестве объектов и характеристик самого класса алгоритмов.
В первой главе рассматриваются исходные положения алгебраической теории универсальных и локальных ограничений для классов алгоритмов распознавания. Рассматривается вопрос о постановке задач распознавания как частного случая общих задач преобразования информации. Далее вводятся понятия систем локальных и универсальных ограничений для задач классификации, где в качестве примера системы универсальных ограничений приводятся универсальные ограничения монотонности.
После этого формулируется проблема обоснования качества алгоритмов распознавания в общем случае. Рассматривается вопрос обоснования качества алгоритмов на рабочей выборке, классифицирующих обучающую выборку с заданным качеством. Приводятся основные результаты теории обоснования качества алгоритмов в задачах распознавания, в которых отсутствуют универсальные ограничения. Делается вывод о том, что описанные результаты непосредственно не позволяют адекватно оценивать качество разнообразных семейств алгоритмов, пригодных для класса задач распознавания с универсальными ограничениями монотонности.
С целью получения таких адекватных оценок изучается понятие линейного достроения частичного порядка на множестве объектов и рассматривается пример класса алгоритмов распознавания с универсальными ограничениями монотонности. Определяется структура таких алгоритмов, и условия, когда алгоритмы данного класса УКа допускают ошибки на рабочей выборке.
Как итог первой главы формулируется постановка задачи обоснования качества классов алгоритмов с универсальными ограничениями монотонности. Ставится задача исследования вопроса об условиях сходимости и о скорости сходимости функционала качества к нулю при бесконечно возрастающей длине объединенной выборки в зависимости от характеристик существующего на множестве объектов частичного порядка.
Вторая глава целиком посвящена оценкам верхней грани числа линейных достроений частичного порядка, определенного на конечном множестве. Сначала приводиться формальный способ построения линейного достроения частичного порядка, разбивающего конечное множество на две непересекающиеся взаимно несравнимые цепи. Далее выводится формула числа линейных достроений для таких частичных порядков и обобщается для частичных порядков, разбивающих конечное множество на к непересекающихся взаимно несравнимых цепей.
В качестве статистических характеристик частичного порядка на конечном множестве вводятся определения плотности и однородности порядка. Далее выводятся оценка верхней грани числа линейных достроений для одного класса частичных порядков с заданными плотностью и однородностью порядка, оценка верхней грани числа линейных достроений для порядков этого класса, для которых задана только плотность порядка. Как итог второй главы делается обобщение полученной оценки верхней грани числа линейных достроений для любых частичных порядков с известной плотностью порядка.
Третья глава посвящена исследованию вопроса обоснования качества алгоритмов с универсальными ограничениями монотонности. Рассматривается класс всех возможных монотонных отображений для двух крайних случаев линейно упорядоченно, и когда на множестве объектов не существует порядка. Далее рассматривается общий случай задания частичного порядка на множестве объектов и выводятся оценки функционала качества. Предлагается вывод формулы числа дихотомий конечного множества на два класса для случая частичного порядка, разбивающего конечное множество на две непересекающиеся взаимно несравнимые цепи. Далее приводится формальное доказательство сходимости функционала качества при условии существования частичного порядка на множестве объектов.
В конце третьей главы на основании полученных оценок числа линейных достроений на конечном множестве и оценки функционала качества исследуется скорость сходимости функционала качества в зависимости от характеристик частичного порядка, заданного на множестве объектов, и от свойств класса алгоритмов распознавания.
В заключении перечисляются основные результаты работы, а также обсуждаются возможные области их применения.
Основные результаты.
1. Введены и исследованы характеристики отношения порядка (плотность и однородность порядка), определяющие количественные характеристики влияния дополнительной информации о монотонности на надежность решения задач распознавания образов.
2. Введено понятие и проведено исследование процедур линейного достроения частичного порядка на конечных множествах.
3. Получены оценки функционала качества для класса алгоритмов с универсальными ограничениями монотонности.
4. Оценена скорость сходимости функционала качества к нулю в зависимости от характеристик частичного порядка на множестве объектов и от характеристики разнообразия класса алгоритмов с ограничениями монотонности.
В качестве решения любой задачи распознавания образов выступает корректный алгоритм распознавания. Полученные результаты позволяют для решения задачи распознавания с универсальными ограничениями монотонности предлагать также условия, когда это решение будет обладать заданным качеством.
Заключение
.
Задачи распознавания с универсальными ограничениями монотонности являются достаточно распространенными в таких областях, как медицинская и техническая диагностика, геологическое, социальное и экономическое прогнозирование. Настоящая работа посвящена проблеме обоснования качества алгоритмов, получаемых в результате решения задач распознавания с универсальными ограничениями монотонности. В данной работе впервые проведено исследование влияния наличия дополнительной информации о монотонности на надежность решения задач распознавания образов.
