Введение к работе
Актуальность темы и цель работы. В самых общих чертах задача распознавания (классификации) состоит в следующем. Исследуется некоторое множество объектов, представимое в виде объединения подмножеств, называемых обычно классами. Объекты описываются некоторой системой признаков. Имеется конечный набор объектов (обучающая выборка), для которых известно, к каким классам они принадлежат. Каждый объект из обучающей выборки представлен набором значений признаков. Требуется по предъявленному набору значений признаков, описывающему некоторый объект (не входящий, вообще говоря, в обучающую выборку), выяснить, каким классам этот объект принадлежит.
Теория и практика решения задач распознавания развивались в различных направлениях, и к настоящему моменту накопилось достаточно много подходов к их решению. Отметим, что в большинстве случаев центральной является проблема синтеза для заданной обучающей информации алгоритмов, экстремальных по точности в том или ином смысле.
Математические методы, применяемые в распознавании образов, можно условно разбить на четыре класса: 1 ) статистические методы; 2) методы оптимизации для многопараметрических моделей распознавания; 3) методы, основанные на идее совместного использования и коррекции наборов распознающих алгоритмов из эвристических семейств; 4) дискретные методы анализа исходной информации и синтеза алгоритмов. Реферируемая работа выполнена в рамках дискретного подхода, который стал интенсивно развиваться с конца 50-х годов. Основополагающими в этой области являются работы
чл.-корр. РАН СЕ. Яблонского и академика РАН Ю.И. Журавлева.
Задача распознавания часто решается в пространстве разнородных признаков очень большой размерности, исчисляемой несколькими десятками, а иногда и несколькими сотнями (при этом число описываемых признаками объектов в обучающей выборке может быть сравнительно невелико). Данное обстоятельство и послужило причиной возникновения методов анализа информации, которые принято называть дискретными (в их основе лежат методы дискретной математики). При использовании этих методов не требуется сильных предположений относительно свойств объекта изучения (предположений типа метризуемости, подчиненности вероятностным законам и т.д.). Основным предметом исследования является совокупность всех подмножеств формального множества признаков, в которой необходимо выбрать специальные наборы признаков. Такие наборы признаков содержат определенную информацию о классах, например, позволяют различать объекты из разных классов или отличать данный объект от объектов из других классов. Могут быть предъявлены и другие, более сложные требования информативности. Иногда представляют интерес наборы признаков, содержащие наоборот "неразличающую" информацию.
Следует сразу отметить, что в силу большой размерности исходного пространства признаков изучение совокупности его подмножеств является очень сложной задачей, поскольку мощность рассматриваемой совокупности экспоненциально зависит от числа признаков. Тем не менее для ее решения была создана специфическая дискретная техника, которая получила весьма широкое применение. Эта техника используется и в оптимизационных методах, и в методах коррекции (как при построении базовых алгоритмов, так и при построении
корректирующих операций), и т.д.. Выявление информативных наборов признаков дает возможность проводить качественный анализ исходной информации, например, с целью информационной классификации признаков и уменьшения их числа.
Дискретные методы привели также к появлению целого класса сложно устроенных эвристик, называемых логическими процедурами распознавания (при их конструировании используется аппарат логических функций). Имеются в виду прежде всего модели тестовых алгоритмов, алгоритмы голосования по представительным наборам и т.п. Эти алгоритмы по построению являются точными (корректными) на материале обучения и первоначально были предназначены для обработки целочисленной информации (в основном бинарной). В последнее время методами дискретного анализа решаются также задачи обработки вещественнозначной информации и на этой основе разрабатываются более универсальные модели распознающих процедур логического характера.
Целью диссертации является разработка асимптотически оптимальных методов дискретного анализа информации, в том числе построение и обоснование эффективных реализаций для распознающих процедур логического характера. Предложены асимптотически оптимальные алгоритмы поиска информативных наборов признаков. В основе этих алгоритмов лежит исключение части условий, которым должны удовлетворять искомые наборы. При этом найденное приближенное решение позволяет почти решить задачу, что означает, что построенная совокупность наборов признаков по мощности "почти всегда" асимптотически совпадает с искомой совокупностью (и, конечно, содержит ее в качестве подмножества).
Главные результаты получены на основе изучения
статистических свойств неприводимых (тупиковых) покрытий булевой матрицы. При этом для усовершенствования и обобщения методики построения информативных наборов признаков и получения необходимых асимптотических оценок введено и изучено понятие тупикового покрытия целочисленной матрицы.
Методы исследования. В работе использованы методы и аппарат дискретной математики, комбинаторной математики, теории вероятности, теории распознавания.
Соответствие исследовательским планам. Диссертация выполнена в соответствии с плановой НИР ВЦ РАН "Разработка математических методов и экспериментальных программных комплексов, ориентированных на интеллектуальные компьютеры, для задач распознавания, классификации, прогноза с неполной и противоречивой информацией" (ГНП "Перспективные информационные технологии, проект 05.05.1071) и проектами РФФИ: N93-01-00457 "Математические методы синтеза решений неклассических задач экстраполяции (в том числе задач распознавания, классификации и прогнозирования) на основе теории алгебр над алгоритмами, комбинаторно-логических конструкций и оптимизационных процедур", N96-01-00552 "Новые методы анализа начальной информации в задачах распознавания", N96-01-00553 "Новые методы распознавания разнородных видеоданных".
Научная новизна. Автором впервые были предложены и исследованы асимптотически оптимальные методы синтеза алгоритмов для широкого класса задач дискретного анализа информации в проблемах распознавания. Все полученные в диссертации результаты являются новыми.
Практическая значимость. Работа в основном имеет теоретический характер, однако предложенные в ней алгоритмы
были реализованы в виде программных модулей, включенных в ряд систем, разработанных в ВЦ РАН. С их помощью за последние 16 лет было успешно решено значительное число прикладных задач распознавания.
Апробация работы и публикации. Результаты диссертационной работы докладывались и обсуждались на Всесоюзных конференциях по проблемам теоретической кибернетики (4-я и 5-я Новосибирск, 1977 и 1980 гг.), на международной конференции по алгебре и логике (ВНР, Сегед, 1979 г.), на Всесоюзных конференциях "Математические метода распознавания образов" (1-я - Звенигород, 1983 г., 2-я - Дилижан, 1985 г., 3-я - Львов, 1987 г., 4-я - Рига, 1989 г., 5-я и 6-я - Звенигород, 1991 и 1993 гг., 7-я - Пущино, 1995 г.), на Советско-германских рабочих семинарах "Дискретная математика и ее применение в математической кибернетике" (ГДР, Берлин, 1983 г., и Йена, 1986 г.), на конференции с участием ученых из социалистических стран "Проблемы искусственного интеллекта и распознавания образов" (Киев, 1984 г.), на международной конференции "Интеллектуализация обработки информации" (Алушта, 1996 г.), на научных семинарах Вычислительного центра РАН, Московского государственного университета им. М.В. Ломоносова, Института социологии при университете им. Ед. Карделя (СФРЮ, Любляна, 1981 г.), Института математики, кибернетики и вычислительной техники АН Кубы (Куба, Гавана, 1989 г.), Института математики с вычислительным центром БАН (НРБ, София, 1989 и 1990 гг.).
Основное содержание работы отражено в 34 публикациях, из них 9 - в центральных научных журналах и книгах, выпущенных издательством "Наука".
Структура и объем работы. Диссертация состоит из введения.
- б -
пяти глав и списка литературы (207 наименовании). Объем работы - 232 страницы машинописного текста.
