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

• Автор: Ицков, Александр Григорьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Ижевск
• Количество страниц: 80 c. : ил

Глава I. Полные замыкания семейств распознающих операторов • 14 § 1.1. Описание модели алгоритмов в задачах с дискретной

обучающей информацией

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

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

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

замыканиях

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

Глава 3. Емкостные характеристики модели алгоритмов с

дискретной обучающей информацией

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

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

Теория распознавания и классификации образов в последние десятилетия является одной из центральных областей прикладной математики и математической кибернетики. Методы распознавания образов находят применение в важных прикладных задачах технической и медицинской диагностики, геологического и социологического прогнозирования, систем обработки информации и ряда других областей. Большое число появившихся к настоящему времени алгоритмов для решения задач распознавания позволило придать содержательной постановке таких задач четкие математические формулировки, а также определить некоторые общие требования к классам алгоритмов, способных успешно решать эти задачи. Переход от рассмотрения отдельных распознающих алгоритмов к классам или моделям алгоритмов, а в последнее время - к синтезу моделей из заданной совокупности моделей [12] - привел к исследованию проблемы выбора алгоритмов, удовлетворяющего определенным экстремальным условиям.
Будем под задачей распознавания Ъ<1о, со стандартной обучающей информацией 1о понимать проблему установления принадлежности объектов некоторого конечного подмножества £>? из множества допустимых объектов М данным классам Л'/ Ке. » образующим покрытие М
Для ряда распространенных моделей распознавания:алгоритмов вычисления оценок, разделения, статистических, потенциальных функций и других алгебраическими методами установлен ряд результатов относительно существования в модели точной распознающей процедуры для произвольной задачи со стандартной информацией [А] , [II] , [18] . В работах [26] , [24] изучены общие

вопросы, связанные с полнотой и построением экстремальных моделей алгоритмов.
Стандартная начальная информация 1о представляет совокупность описаний объектов из множества ^ ^ <=М с известной классификацией в пространстве признаков МуХ...х Мн. Для изученных моделей алгоритмов важную роль играет то обстоятельство,что они применяются преимущественно к задачам, в которых множества описаний являются метрическими (или полуметрическими) пространствами с метриками . При этом метрика (в частности, евклидова) может служить мерой сходства распознаваемых объектов и эталонов по отдельным признакам, принимающим значения из некоторого основного континуума. Задачи такого рода будем называть задачами с непрерывной начальной информацией. Для таких задач при задании функции близости, использующей данные метрики и меры точности измерений £/г...,£/7 , можно получить богатые параметрические модели распознавания.
С другой стороны, существует ряд прикладных задач, в которых переменные (признаки) принимают дискретные значения. Эти переменные в отличие от шкал интервалов или порядка представляют скорее качественную, номинальную шкалу наименований, чем числительную шкалу. Необходимость в преимущественно дискретных (в частности, бинарных) измерениях появляется во многих практических системах распознавания либо из-за самой сущности задачи,как, например, классификация симптомов в автоматической диагностике заболеваний, либо из-за выбора признаков (при обработке и распознавании изображений, в геологическом прогнозировании и т.д.). Однако, несмотря на практическую важность задач с дискретной информацией существует немного математических средств, пригодных для их решения. В таких задачах возникают значительные трудности
■ 50'
/№) множество У= {уіУЄЕН} ь где У і соответствует подмножеству признаков Ос мощности /- 1и>сЫ /+ МГПф Т ,
І=ї>2,. . . ,Л,
НгапоТ
/7= ХИТ (гапо Тб/?-/).

Следующий очевидный результат показывает, что функция Р(х,да>) не возрастает по второму аргументу.
Утверждение 2.3. Пусть заданы два отображения
§4п)
такие, что
д<(*)£дгсх)
_ * о
для всех X Є . Если X - решение уравнения
Г(2,^ (X)) =0,
то Х° является решением уравнения
Г (.%,дг(х))= 0.
Пусть 32; (х) - система тупиковых тестов таблицы обу-

чения, соответствующей разбиению X € . Приведенный
ниже пример показывает, что уравнение (2.7) может не иметь решений по 32 і (X) . Пусть
А*(0,4,у), *,*(0,0,0), 3,*(/,А/) , Ь‘У0ЛО Л/, є К*, $з, ви є /Ґг
Непосредственно проверяется, что для любого разбиения
Зс ~ $4 (X) 3] , Є {/, 2,3, */}, £'*
Следующее условие является достаточным для существования решения в задачах с большими таблицами.