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

р ^ 0 Д РОССИЙСКАЯ АКАДЕМИЯ НАУК

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

'"-> лгч и ^ Ч-'СЙ

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

Д Ю К О В А Елена Всеволодовна

Асимптотически оптимальные методы дискретного анализа информации в задачах распознавания

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

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

Москва - 1996

Работа выполнена в Вычислительном центре РАН Официальные оппоненты:

доктор физико-математических наук, профессор В.И. Донской

доктор технических наук, профессор А.П. Немирко

доктор физико-математических наук, профессор Ю.А. Флеров

Ведущая организация:

НИИ прикладной математики и кибернетики при Нижегородском государственном университете им. Н.И. Лобачевского

Защита состоится

«ЛИ" Ф^Ра/ь! 199/ г. б Ы часов на заседании диссертационного совета Д002.32.06 при Вычислительном центре РАН г. Москва, ул. Вавилова, д. 40

С диссертацией можно ознакомиться в библиотеке Математического института им. В.А. Стеклова РАН

Автореферат

Ученый секретарь диссертационного совета Д002.32.06

кандидат физ.-мат. наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Математические методы, применяемые в распознавании образов, можно условно разбить на четыре класса: 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 страницы машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

/к..... хп) , специальным образом построенной по обучающей

выборке. Функция / равна 1 на наборах, являющихся описаниями обучающих объектов из класса К , и равна 0 на наборах, описывающих остальные обучающие объекты, т.е. /к -это характеристическая функция класса К на обучающей выборке.

Искомые конъюнкции строятся на основе п семейств предикатов.

Предположим, что для признака с номером J , j £ {1,

2..... п) , задано конечное семейство предикатов ^ .

Предикаты из ^ - функции, равные 0 или 1 и определенные на множестве допустимых значений признака с номером 3 . Если,

например, множество допустимых значений признака с номером 3

есть множество {0, 1..... {-1> , то в качестве ^ может быть

использован набор (.х0 ,..., х*~1} , где х° = 1 тогда и только тогда, когда х = о . Точно также можно считать, что ха = 1 тогда и только тогда, когда х > а ,

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

Э.к. 93 над переменными х^,..., хп называется почти допустимой для /к , если интервал Ш]3 пересекается с множеством наборов ^ , на которых функция fк равна 1

Э.к. © над переменными д^,..., хп называется допустимой для , если Ну П Ак 1 0 и интервал Яд не пересекается с множеством наборов Вк , на которых функция равна 0 .

Э.к. 93 над переменными х1..... хп называется почти

люксижиъной для , если 93 является почти допустимой и не существует э.к. 93' такой, что г/щ с и мощность множества NП Вк равна мощности множества П Вк .

Э.к. 93 над переменными хл,..., хп называется максижиъной для /к , если © является допустимой конъюнкцией и не существует допустимой э.к. такой, что с гг0> .

Стандартным образом вводятся понятия дизъюнктивной нормальной формы (д.н.ф.) и конъюнктивной нормальной формы (к.н.ф.).

Пусть © - почти допустимая конъюнкция функции fк вида Р1 & ... & Рг ,

где Р{ е ф , е {1, 2..... п} при « = 1,2..... г , и

пусть й с П Ак , Б = (а^..... ап) . Поднабор (а^ .....

а, ) набора 5 называется элежшщмш классьфинатором дм

V

класса К , порождаемым конъюнкцией © .

В общем случае элементарный классификатор - фрагмент описания обучающего объекта 5 с заданными свойствами. Эти

свойства определяются предикатами Р1 ..... Рг . Элементарный

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

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

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

Как правило, для порождения множества элементарных классификаторов Р. используется та или иная часть множества

ГОК всех допустимых конъюнкций функции /к . Например, берутся все максимальные конъюнкции или вводится ограничение на величину ранга конъюнкции (предполагается, что ранг конъюнкции не должен превосходить некоторого заданного числа). Могут быть наложены и другие условия. Вместо Юк может рассматриваться и множество ГО* , состоящее из всех почти допустимых конъюнкций

функции /к . В зависимости от характера условий, налагаемых на

выбор множества ? , наиболее известные алгоритмы из

описанного выше класса делятся на два основных типа: 1)

тестовые модели; 2) алгоритмы типа "Кора" или модели с

представительными наборами.

Материал обучения обычно задается в виде таблицы (таблицы

обучения), столбцы которой соответствуют отдельным признакам, а

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

из объектов. Строки таблицы разбиты на непересекающиеся классы

так, что каждый класс содержит те и только те строки, которые

описывают объекты из одного и того же класса.

Пусть Т - таблица обучения, строки которой разбиты на I

классов К......К, , с и ЗЛ* и ... и ГО* - множество

1 г к1 к2 кг

конъюнкций, сответствующее распознающему алгоритму А .

Изначально рассматривался случай, когда Г - бинарная таблица,

fк - булева функция, £ = 1, 2,..., I , и конъюнкции из

ч

о, а

1 _ г „„■„„ ~о

имеют вид х,...х, , где символ вида х при х и с •ч т*

из (0, 1) задает предикат, равный 1 тогда и только тогда, когда х - а .

СТ1 *

Каждая конъюнкция Ъ = х,... х, из Ю1„ , К € 1КЛ

Jr к _ 1

Кг) , определяет две следующие подтаблвды и Г^ таблицы Т . Подтаблица Г^ образована столбцами с номерами ]г

и строками, описывающими объекты из К . Легко видеть, что эта подтаблица содержит хотя бы одну строку вида (с^,..., ог) . Подтаблица образована столбцами с номерами ,..., Jv и строками, не являющимися описаниями объектов из К . Если 53 -допустимая конъюнкция, то, согласно сказанному выше, в нет ни одной строки вида (сог) . Это условие не выполняется, если 95 не является допустимой конъюнкцией. В первом случае набор (о,,..., а ) назовем представительным для

класса, К по опорному множеству (1/1..... Jr) , во втором -

почти предстабшелънш. Будем считать, что каждый представительный набор является одновременно и почти представительным.

Набор (а1..... о ) , являющийся представительным (почти

представительным) для К по опорному множеству (>/1,..., ,

назовем тупиковым, если э.к. х, ... х, является

•М V

максимальной (почти максимальной) для /к . Тупиковому

представительному набору соответствует несжимаемый

информативный фрагмент описания обучающего объекта, т.е.

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

Набор столбцов таблицы Т с номерами .....Jr

назовем шестом, ест для каждой функций /„ ,{€{1,2,...,

{

с. о

1} , каждая почти допустимая конъюнкция вида х.\.. х,

'М т*

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

подмножество не является тестом.

Понятия (тупикового) теста и (тупикового) представительного набора легко обобщаются на случай, когда Т - целочисленная таблица.

В тестовых распознающих алгоритмах множество РА чаще всего порождается тупиковыми тестами, в алгоритмах типа "Кора" в качестве элементов множества РА используются тупиковые представительные или тупиковые почти представительные наборы. Все сведения о множестве элементарных классификаторов для этих алгоритмов содержатся в специальной булевой матрице Ъх {жжрице сравнения таблицы Г ). В рассматриваемом случае, т.е., когда Г - бинарная таблица и конъюнкции, порождающие элементарные классификаторы, определены стандартным образом, эта матрица образуется в результате попарного сложения по тоб2 строк таблицы Г , принадлежащих разным классам.

Основы асимптотических оптимальных методов дискретного анализа информации в задачах распознавания были заложены еще в 70-х годах при исследовании сложности реализации тестовых процедур.

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

Пусть X - произвольная булева матрица. Набор столбцов Я матрицы X назовем покрытием, если каждая строка матрицы X в

пересечении хотя бы с одним из столбцов, входящих в Я , дает 1 (т.е. в подматрице матрицы L , образованной столбцами из H , не должно быть строки вида (0,..., 0) ). Покрытие назовем неприводимым (тупиковым), если никакое его собственное подмножество не является покрытием. Нетрудно видеть, что свойство тупиковости означает, что в подматрице матрицы I , образованной столбцами набора Я , должна быть каждая из строк

(1, О, О,..., О, 0), (0, 1, 0.....О, 0),,.., (О, О,..., О, 1),

т.е. набор столбцов Я должен содержать подматрицу, в каждой строке и в каждом столбце которой в точности один элемент равен 1 . Такая подматрица называется единичной.

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

Понятие теста и тупикового теста первоначально было введено C.B. Яблонским в связи с задачей контроля управляющих систем. Для обнаружения неисправности в управлящей системе необходимо построить тест пары (Т, G) , где Т - бинарная таблица, a G - специальный граф, множество вершин которого совпадает с множеством строк таблицы Т . Тест пэры (Т, G) представляет собой набор столбцов таблицы Т , позволяющий различать строки, смежные в графе G . Для того, чтобы задача обнаружения неисправности решалась с минимальной сложностью, необходимо построить тест минимальной длины. Поскольку минимальный тест - один из тупиковых, то проблема его нахождения может быть увязана с проблемой построения

эффективной процедуры перебора всех тупиковых тестов пары (Т, О) .

В распознавании образов понятие теста впервые было использовано в работах Ю.И. Журавлева при решении задач геологического прогнозирования.

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

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

Пусть п) - множество всех таких пар (Т.в) , что таблица Т имеет п столбцов и в графе <7 две вершины соединены ребром, если соответствующие строки таблицы Т описывают объекты из разных классов. Поведение указанных

числовых характеристик множества тупиковых тестов изучалось для почти всех пар (Т,0) из п) при п -» <» .

Ю.И. Журавлев, В.Н, Носков и В.А. Слепян получили первые асимптотические оценки числа тупиковых тестов и длины тупикового теста для почти всех пар (Г,О в случае, когда Т - бинарная таблица. Основные результаты были получены для практически важного случая, когда число вершин в графе О достаточно мало по сравнению с числом признаков п . При этом предполагалось, что С? - полный граф. Конструкция таблиц определялась тем, что в первоначальном описании тестового алгоритма каждый класс в таблице обучения Т был представлен одним объектом. Такая таблица аналогична таблице неисправностей, рассматриваемой в задачах контроля управляющих систем. Получение указанных оценок явилось технически очень сложной задачей, необходимость решения которой была связана с прогнозом сложности реализации тестового алгоритма и качества проводимого им распознавания. Таким образом, фактически были разработаны технические основы получения асимптотик типичных значений числа неприводимых покрытий и длины неприводимого покрытия.

Далее автором данной работы в [6-143 был предложен подход к построению асимптотически оптимальных распознающих процедур тестового типа. Подход основан на анализе сложности решения задачи построения множества всех неприводимых покрытий матрицы сравнения 1Т таблицы обучения Т . Рассмотрим его на примере построения неприводимых покрытий для произвольной булевой матрицы Ъ размера и * п . Отметим сразу, что практически интересен случай, когда в матрице I нет одинаковых столбцов. Поэтому естественно предполагать, что и 2 1оёР п .

Для случая п < и ^ п1~с {£ > 0) был построен

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

Сокращение перебора достигается за счет следующего приема. Исходная задача заменяется логически более простой задачей, а именно задачей построения всех таких наборов столбцов матрицы I , для которых выполнено лишь условие "тупиковости" из приведенного выше определения неприводимого покрытия булевой матрицы. Фактически строятся все единичные подматрицы матрицы 1 . Оказывается, что в рассматриваемом случае почти всегда (для почти всех матриц Ь размера и * п) число единичных подматриц матрицы Ъ асимптотически при п - °о совпадает с числом неприводимых покрытий и, следовательно, набор столбцов, содержащий единичную подматрицу, почти всегда является неприводимым покрытием.

Метод был проверен в машинных экспериментах. В его программной реализации , подробно описанной в [6], строятся единичные подматрицы, являющиеся в определенном смысле максимальными, и после построения каждой такой подматрицы проверяется, является ли соответствующий набор столбцов покрытием. Алгоритм экономичен и в смысле использования памяти ЭВМ. С помощью данного алгоритма были достаточно эффективно • решены задачи детерминированного и стохастического построения тупиковых тестов и построены соответствующие процедуры распознавания. Реализации этих процедур были включены в пакет прикладных программ ПАРК [28], диалоговую систему анализа и распознавания образов ДИСАРО [31, 33, 34] и систему ОБРАЗ [1, 21. Перечисленные программные комплексы разработаны в ВЦ РАН.

При теоретическом обосновании эффективности алгоритмов построения тупиковых тестов в работах автора [7-14] получены асимптотики типичных значений числа тупиковых тестов и длины тупикового теста для целочисленных таблиц, строки которых разбиты на два класса, т.е. для случая, когда в - полный двудольный граф. При этом предполагалось, что число ребер q{G) в графе (? заключено в отрезке [Тоз2^ п, ] (£ > 0), где I - значность таблицы Т . В [12] с целью обоснования стохастического подхода к построению тупиковых тестов были получены асимптотические оценки для величин, характеризующих информативность признаков в детерминированных и стохастических тестовых алгоритмах.

Задача о числе тупиковых тестов (для произвольного графа О, как уже отмечалось выше, была в определенном смысле решена окончательно после публикации работ А.Е. Андреева, в частности был разобран ранее мало исследованный случай, когда число строк в таблице Т не меньше числа столбцов. А.Е. Андреевым был также предложен асимптотически наилучший алгоритм нахождения тупиковых тестов в случае, когда 1ой2д(0) = оп) , п -- а> (при построении алгоритма и его обосновании использовались те же принципы, что и в работах автора [6-14]).

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

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

Автором в работах [15, 16, 18-21, 33, 343 было показано, что задачу построения множества всех тупиковых представительных наборов можно эффективно (с асимптотически минимальной сложностью) решать на основе построения неприводимых покрытий для ряда булевых матриц (подматриц матрицы Ъг ). Для построения неприводимых покрытий использовалась модификация алгоритма из [6]. Данный подход позволяет обрабатывать не только бинарную, но и целочисленную информацию. Эффективность метода подтверждена экспериментами на ЭВМ. Эксперименты проводились для случая, когда число обучающих объектов не превосходит числа признаков. Построены соответствующие алгоритмы распознавания. Реализации этих алгоритмов на ЭВМ были также включены в вышеупомянутые системы ДИСАРО и ОБРАЗ.

В работах автора [15, 18, 21, 221 на основе модификации алгоритма из [6] было получено асимптотически оптимальное решение задачи построения сокращенной д.н.ф. булевой функции от п переменных Р^ , заданной к.н.ф. й . При этом рассматривались случаи, когда к.н.ф. й является совершенной, не содержит отрицаний переменных и , наконец, не обязательно является совершенной и может содержать отрицания переменных. В каждом из перечисленных случаев предполагалось, что число

1 —Л

элементарных дизъюнкций в исходной к.н.ф. не превосходит п

(£ > 0) . Сложность решения оценивалась числом операций "&" , совершаемых при преобразовании нормальных форм. Было показано, что это число почти всегда (для почти всех к.н.ф. рассматриваемого вида) при п « асимптотически не превосходит длины искомой сокращенной д.н.ф. Отметим, что задача решалась на основе построения вспомогательнной д.н.ф., состоящей из всех почти максимальных конъюнкций функции .

Асимптотики типичных значений числа тупиковых представительных наборов и длины тупикового представительного набора для класса К (сначала бинарной, а затем и целочисленной) таблицы обучения были получены автором в [16, 17, 21, 25, 26) при условии, что число обучающих объектов, не принадлежащих классу К , не превосходит п1~с (£ > 0) .В [20, 23, 25, 26] для достаточно широкого класса бинарных таблиц автором были получены также асимптотики типичных значений аналогичных числовых характеристик множества представительных наборов.

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

В реферируемой работе изложенная методика построения неприводимых покрытий булевой матрицы обобщена на случай целочисленной матрицы. С этой целью введено понятие тупикового покрытия целочисленной матрицы. Асимптотически оптимальный алгоритм построения неприводимых покрытий для булевой матрицы [6] модифицирован на случай целочисленной матрицы. При обосновании асимптотической оптимальности данного алгоритма

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

Асимптотически оптимальные методы построения тупиковых покрытий были применены автором при разработке новых более совершенных моделей распознающих процедур, использующих в качестве элементарных классификаторов тупиковые представительные и тупиковые почти представительные наборы 43, 5, 20, 21, 24, 29, 30, 32]. Данные модели могут использоваться для обработки произвольной числовой информации.

Глава 1 является центральной. В этой главе вводится понятие тупикового покрытия целочисленной матрицы, обобщающее известное понятие тупикового (неприводимого) покрытия булевой матрицы. Проводится анализ сложности решения задачи построения множества всех тупиковых покрытий для двух типов покрытий: <а>-покрытия и Л(ст)-покрытия. Описывается асимптотически оптимальный алгоритм. Приводятся асимптотики типичных значений числа тупиковых покрытий и длины тупикового покрытия. Результаты, полученные в данной главе , а также методика получения этих результатов принципиально важны для последующих глав.

В разделе 1.1 вводятся основные понятия.

Пусть , fe > 2, - множество всех й-ичных наборов длины

г .

Рассмотрим а е , k 2 , а = (о1.....а ) .

Введем следующие обозначения: Д(ст) - множество всех таких

наборов ..... (3^) в , для которых (3^ * о} при J £

€ {1, 2,..., г> ; Qp(o) , р £ С1, 2,..., г), - множество всех

таких наборов (р1..... рг) в , для которых р ^ и

= Oj при J е (1, 2,г) \ (р) .

Пусть Е с е£ , Е = {а115 а(ч)} . Положим

Q

Q (В) = f U б (асл) 1 \ Е .

J=1 '

Пусть L = (а{ ) , i = 1, 2,..., т , J = 1, 2..... п , -

матрица с элементами из (0, 1..... fc-1) , i И , Я - набор

из г различных столбцов матрицы Ъ , Iя - подматрица матрицы I , образованная столбцами набора Н .

Множество строк подматрицы 1н можно рассматривать как некоторое подмножество Ен наборов из Е£ . Набор столбцов Я называется Е-покрытием, если Ен П Е = 0 . Набор столбцов И , являющийся Е-покрытием, называется тупшовъш, Е-покршиэм, если для любого р из (1, 2г) можно указать пару

ft* f tr f f f

наборов {a , a ) такую, что о € Er , о £ E и наборы а и о'' различаются в разряде с номером р , а в остальных разрядах совпадают.

Таким образом, набор столбцов Н матрицы L является тупиковым Е-покрытием, если подматрица iH матрицы L , образованная столбцами набора Н , обладает следующими двумя свойствами:

1) 1н не содержит ни одной строки из Е ;

2) если р £ {1, 2.....г> , то LH содержит хотя бы одну

строку из множества О (В) .

С практической точки зрения наравне с общим случаем наиболее важными являются два следующих случая: В = La) , ст £ € ЕГ , и Е = Я (о), о £ ЕГ . Тупиковые покрытия общего вида и,

в особенности, тупиковые {(0,..., 0)}-покрытия возникают при изучении метрических свойств множества тупиковых тестов и построении алгоритмов поиска тупиковых тестов (в данной работе при изучении тестовых алгоритмов рассматриваются тупиковые

{(0..... 0)Ьпокрытия). Случай Е = io) , ст € , нужен для

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

Через В(1,Е) обозначим множество всех пар вида (Я, Е) , где Н - тупиковое Е-локрытие матрицы L (в случае, когда В = = (о> , будем также пользоваться обозначением В (L) )•

Пусть набор Я состоит из столбцов матрицы Ъ с номерами Jr , <...< Jr . Набор элементов (о{ , ..... а{ , }

11 г г

матрицы L называется совместимым относительно Е , если в подматрице LK строка с номером I принадлежит Q (Е) при р = 1, 2,..., г. Обозначим через S(L,E) совокупность всех пар вида (Q, Е) , где Q - совместимый относительно Е набор элементов матрицы £ (в случае, когда Е = (а) , а € Е£ , будем пользоваться также обозначением S (I) ).

Нетрудно видеть, что набор столбцов Я матрицы I с номерами J1,..., Jr является тупиковым Е-покрытием тогда и только тогда, когда в Ъ можно указать набор элементов вида (а, , а. , } , совместимый относительно Е , и подматрица

1Г1 г г

£н не содержит ни одной строки из Е .

В разделе 1.2 изучаются статистические свойства тупиковых покрытий.

Введем обозначения: 14! - мощность множества А ; а ~ b ,

11 TT- TL

п ■*■ оо , означает, что lim а /Ь =1 ; - совокупность всех

п-.оо n n mn

матриц размера т * п , с элементами из (0, 1,..., й-1> , й > > 2 ; Е^ - множество, состоящее из одного набора длины г вида (1,..., 1) ; - интервал

1 logd ш - hogd logd mn - logd logd logd n ,

1 l0gd mn - hogä l0gd Ш + I0gd logd logd n

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

двух случаях: а) Е = (о) , ст € ; б) Е = й(о), о € Е£ , й-1 < < t < к . В каждом из этих случаев вычисляются значения аналогичных числовых характеристик сответствующего множества совместимых наборов. Выявление типичной ситуации будет связано с высказыванием типа "для почти всех матриц Ъ из при

п - со выполнено свойство 43 ", причем свойство iß также может иметь предельный характер. Это означает, что доля тех матриц из , для которых с е-точностью выполнено свойство ф , стремится к 1 и одновременно е стремится к 0 при п - » . Например, если на матрицах из И^ заданы два функционала F(L) и G(L) , то мы будем говорить, что для почти всех матриц I ю # при п -* оо выполнено F ~ G (Р асимптотически

mn г

равно G ), если существуют две положительные бесконечно

убывающие функции а{п) и ß(n) такие, что для всех

достаточно больших п выполнено 1 - I ^ а(п) , где SJt

1 1 тптх *

- множество матриц L из , для которых выполнено 1 -

- p(n) < F(L) / G(L) < 1 + p(n) .

Для L € Яр , Й-1 äs t ^ k , положим

ттъ

3,(1) = Д и Вв(Ь) , В*(Ь) = Д и В(Ь,Д(о)) ,

5,(1) = Д и 5а(Ь) , = Д и 3(1,Й(о)) .

Имеет место следующая основная для реферируемой работы Теорема 1.2.1.1) Если та $ п ^ , а > 1 , & £ > 2 , то Зля почти бсех матриц Ъ из при п -> <»

справедливо

13,(1)1 «1^(1)1» V с; с; г!(й-1)г йг-г2

и для почти бсег пар из В,(Ъ) 5лшы тупиковых покрытий принадлежат интервалу Фл(т) .

2) Если та ^ п 4 (й/(й- 1 )Г , а > 1 , 2е > 2 , Й-1 $ Г ^ < й , то для почти всех матриц Ъ из при п -* <»

справедливо

._, 2 2

|В*(1)| ~ ~ У СгпСгт гир№- 1)г "г

и Эля почти бсед: пар из 3^(1) блины тупиковых покрытий принадлежат интервалу Фл(т) , г<3е = й/(й-1 ) .

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

В Главе 2 проведено построение ряда логических

распознающих процедур.

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

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

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

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

Задача ставится следующим образом. По таблице обучения Т , содержащей вещественные числа, строится специальная булева матрица Ъ , столбцы которой разбиты на п групп, где п -размерность признакового пространства. Требуется построить набор столбцов матрицы Ъ , являющийся покрытием я содержащий по крайней мере по одному столбцу из каждой группы. Каждое такое покрытие определяет некоторую перекодировку таблицы Т ,

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

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

Каждый из обучающих объектов С{ , £ = 1, 2,..., т , задает подтаблицу Т{ таблицы Г , образованную описанием объекта С{ и описаниями объектов, не вошедших в тот же класс, что и С{ . Пусть С{ принадлежит классу К . По таблице , аналогично построениям, проводимым при конструировании матрицы Ъ , строится булева матрица 1{ размера т(,К) « , где т(К) -число объектов, не вошедших в класс К , а 2п.

Матрица I является подматрицей матрицы L . Покрытия для L{ порождают множество перекодировок nt = (Hj4'

которые называются частичными. Значность частичной перекодировки не выше трех.

Произвольная частичная перекодировка Н € П4 задает преобразование таблицы Т{ в таблицу Т^ с элементами•из (О, 1,2} . При этом описание объекта Ct преобразуется в строку S* . Строки в з» разбивается на два класса, к первому относится строка S^ , ко второму - остальные строки. В простейшей модификации фрагмент описания объекта С{ называется представительным для класса X , порождаемым перекодировкой Я, если соответствующий фрагмент строки S^ не встречается по данному набору признаков среди строк второго класса таблицы Г^ . Обычным образом вводится понятие тупикового представительного набора.

Таким образом, каждая пара (С{,я|{)) , t е (1, 2,..., т), J € tl, 2,..., v{} , порождает множество тупиковых представительных наборов P(Ci,H^1)) . Построена модель распознающих алгоритмов, в которой используется процедура голосования по наборам из

771 V ^

Р(Т) = и и P(C,,Hi.i)) .

1=1 J=1 1 J

Для построения множества Р(!Г) решается задача поиска всех неприводимых покрытий в матрице Li .

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

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

В Главе 3 изучаются метрические свойства множества представительных наборов. Используются асимптотические оценки, полученные в Главе 1 для тупиковых {о>-покрытий.

Несложные дополнительные построения позволяют получить асимптотики типичных значений числа тупиковых представительных наборов и длины тупикового представительного набора для класса

К таблицы обучения Г с элементами из СО, 1.....} , й >

> 2 . Эти оценки получены в разделе 3.1.

Пусть т1 - число строк в Т , описывающих объекты из класса К , тг - число строк в Т , описывающих объекты из остальных классов, РК(Т) - множество тупиковых представительных наборов для класса К . Таблицу Г можно рассматривать как пару матриц вида (Е,, I.) , где Е. е , Е„ € ЗК3* . Пусть

А А 12 1 т.^ п 2 ш^п

т п - множество всех пар матриц указанного вида.

Доказана следующая

тэ

Теорема 3.1.1. Если т^^п^й, а > 1 >2, по для почти всех таблиц Т из при п ■* со

справедливо

|рк(Т)1 ~ ^ (1-(1-й~г)1) с; с; г! (Й-1 )г &г-г

г€Фа(т2) 2

и длины почти всех наборов из принадлежат

интервалу •

В разделе 3.2 рассмотрена задача об устойчивости множества представительных и множества "коротких" представительных наборов к случайному искажению обучающей информации.

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

В Главе 4 ставится и решается задача построения сокращенной д.н.ф. двузначной функции &-значной логики

от . п переменных.

В разделах 4.1 и 4.2 рассматривается случай, когда функция Рд задана к.н.ф. К из т элементарных дизъюнкций. Показано, что данная задача сводится к построению множества всех тупиковых й(а)-покрытий целочисленной матрицы размера

т * п . Использование результатов, изложенных в Главе 1, позволяет в случае т < п1_е (£ > 0) сократить перебор в некотором смысле до минимального. При этом исходная задача заменяется логически более простой задачей построения д.н.ф. , состоящей из всех почти максимальных конъюнкций функции . Д.н.ф. ^ по своим свойствам достаточно близка к д.н.ф. Од и ее длина почти всегда (для почти всех к.н.ф. рассматриваемого вида) асимптотически совпадает с длиной д.н.ф.

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

предлагаемый подход к построению сокращенной д.н.ф. функции Р позволяет решать задачу в определенном смысле с асимптотически минимальной сложностью. Наравне с общим случаем изучен случай, когда к.н.ф. Я является совершенной. Для построения тупиковых Я(о)-покрытий используется алгоритм из раздела 1.3. Главы 1.

Отметим, что из оценок, полученных для тупиковых А(а)-покрытий, прямо следуют асимптотики типичных значений длины Ю>я) д.н.ф. Вя и ранга входящей в нее конъюнкции. В частном случае асимптотика величины дает асимптотику

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

В разделе 4.3 рассмотрена задача построения частичной двузначной функции, определенной на &-ичных п-мерных наборах, которая может быть сведена как к построению тупиковых Л(а)-покрытий, так и к построению тупиковых {о)-покрытий.

В Главе 5 приводится обоснование асимптотической

оптимальности тестовых процедур распознавания, построенных в Главе 2. Изучаются метрические свойства множества тупиковых тестов. Рассматриваются вопросы, связанные с исследованием условий применения стохастических тестовых процедур. Показано, что при определенных условиях величины, вычисляемые стохастическими тестовыми алгоритмами, почти всегда асимптотически совпадают с величинами, вычисляемыми детерминированными тестовыми алгоритмами. Доказательства основных утверждений базируются на изучении статистических свойств множества всех неприводимых покрытий матрицы сравнения 1Т таблицы обучения Т . Используются те же технические приемы, что и в Главе 1;

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

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

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

практически важного случая, а именно, для случая, когда число строк булевой матрицы достаточно мало по сравнению с числом ее столбцов.

3. При обосновании асимптотической оптимальности построенных алгоритмов получены асимптотики типичных значений числа неприводимых покрытий и длины неприводимого покрытия булевой матрицы размера и * п при условии 1ой2 п ^ и ^ п1-е {€ > 0) .

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

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

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

моделей. А именно, таких характеристик, как число представительных наборов и длина представительного набора, а также аналогичных характеристик множества тупиковых представительных наборов и множества тупиковых тестов.

7. Предложены асимптотически оптимальные методы построения сокращенных д.н.ф. двузначных функций (частичных и всюду определенных). Синтез максимальных конъюнкций проводится на основе предварительного построения и анализа множества всех почти максимальных конъюнкций.

8. Изучены метрические (количественные) свойства сокращенных д.н.ф. двузначных функций. В частности, получены асимптотики типичных значений числа (почти) максимальных конъюнкций и ранга (почти) максимальной конъюнкции для функции от п переменных при условии, что число ее нулей не превосходит п1-с (£ > 0) .

9. Доказана устойчивость множества представительных и множества "коротких" представительных наборов к случайному искажению обучающей информации.

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

Основные результаты работы отражены в следующих публикациях:

1. Бушманов О.Н., Дюкова Е.В., Журавлев Ю.И., Кочетков Д.В., Рязанов В.В. Система анализа и распознавания образов // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука, 1989. Вып. 2. С. 250-273.

2. Бушманов О.Н., Дюкова Е.В., Рязанов В.В. Система

распознавания, таксономии и анализа стандартных данных // Тез. III Всес. конф. "Мат. методы распознавания образов". Львов: Изд-BO АН УССР, 1987. С.8-9.

3. Валев В., Беликов М., Дюкова Е.В. Программный комплекс для решения задач распознавания на основе построения эмпирических закономерностей . М.: ВЦ АН СССР, 1988. 20 с.

4. Воликов Ю.К., Дюкова Е.В., Левашов Е.А., Рязанов В,В. Применение методов распознавания образов для прогнозирования свойств твердых сплавов группы СТИМ. М: ММСИС, 1988. С. 40-43.

5. Долгоруков А.Ю., Дюкова Е.В. Об одном способе вычисления информационных характеристик обучающей выборки // Тез. докл. Всерос. конф. "Матем. методы распознавания образов (ММРО-6)". Москва, 1993. С. 22-23.

6. Дюкова Е.В. Об одном алгоритме построения тупиковых тестов для бинарных таблиц // Сборник работ по дискретной математике. М.: ВЦ АН СССР, 1976. Вып. 1. С. 167-185.

7. Дюкова Е.В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. Т. 233, Л 4. С. 527-530.

8. Дюкова Е.В. Об асимптотически оптимальном алгоритме построения тупиковых тестов для одного класса й-значных таблиц // Тез. докл. IV Всесоюз. конф. по проблемам теоретической кибернетики. Новосибирск: Изд-во СО АН СССР, 1977. С. 197-199.

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

10. Дюкова Е.В. Построение тупиковых тестов для й-значных таблиц // ДАН СССР. 1978. Т. 238, № 6. С. 1279-1282.

11. Дюкова Е.В. Об асимптотической эквивалентности

стохастического и детерминированного подходов в тестовых алгоритмах распознавания // Тез. докл. V Всесоюз. конф. по проблемам теоретической кибернетики. Новосибирск: Изд-во СО АН СССР, 1980.

12. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания // Проблемы кибернетики. Вып. 39. М.: Наука, 1982. С. 165-199.

13. Дюкова Е.В. О тестовых алгоритмах распознавания // Тез. докл. Советско-германского рабочего семинара "Дискретная математика и ее применение в мат. кибернетике". Берлин (ГДР): Университет им. Гумбольда, 1984. С. 17-23.

14. Дюкова Е.В. О стохастическом подходе в тестовых алгоритмах распознавания // Тез. докл. научн. конф. с участием ученых из социалистических стран "Проблемы искусственного интеллекта и распознавания образов". Секция 2: Распознавание образов. Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1984. С. 119-121.

15. Дюкова Е.В. О построении систем опорных множеств для специальных классов алгоритмов распознавания // Тез. докл. II Всес. конф. "Мат. методы распознавания образов". Ереван: Изд-во АН АрмССР, 1985. С. 70-72.

16. Дюкова Е.В. О релизации и некоторых метрических свойствах алгоритмов типа "Кора" // Тез. докл. симпозиума "Метода и программное обеспечение обработки информации и прикладного статистического анализа данных на ЭВМ". Минск. 1985. С. 141-142.

17. Дюкова Е.В. О метрических свойствах алгоритмов типа "Кора" для одного класса бинарных таблиц. М.: ВЦ АН СССР, 1986. 17 с.

18. Дюкова Е.В. О сложности реализации некоторых процедур распознавания // Ж. вычисл. матем. и матем. физ. 1987. Т. 27,

Л 1. С. 114-127.

19. Дюкова Е.В. Алгоритмы распознавания, основанные на построении различающих комбинаций признаков // Тез. докл. III Всес. конф. "Мат. методы распознавания образов". Львов: Мзд-во АН УССР, 1987. С. 62-63.

20. Дюкова Е.В. Об одной параметрической модели алгоритмов распознавания типа "Кора". М.: ВЦ АН СССР, 1988, 23 с.

21. Дюкова Е.В. Алгоритмы распознавания типа "Кора": сложность реализации и метрические свойства // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука, 1989. Вып. 2. С. 99-125.

22. Дюкова Е.В. 0 решении систем булевых уравнений квазинельсоновского типа // Вопросы кибернетики / Дискретная математика. Методы и применение / М.: АН СССР, Научный Совет по комплексной проблеме "Кибернетика", 1989. с. 5-19.

23. Дюкова Е.В. О числе устойчивых представительных наборов // Тез. докл. IV Всес. конф. "Матем. методы распознавания образов". Рига: Изд-во СМ ЛатвССР, 1989. С. 50-51.

24. Дюкова Е.В. Модель распознающих алгоритмов, основанная на построении частичных перекодировок // Тез. докл. V Всесоюзн. конф. "Матем. методы распознавания образов", Москва, 1991. С. 47-48.

25. Дюкова Е.В. О метрических свойствах щожества представительных наборов в логических алгоритмах распознавания // Тез. Всерос. конф. "Матем. метода распознавания образов СММРО-6)". Москва, 1993. С. 24-25.

26. Дюкова Е.В. Асимптотические оценки некоторых характеристик множества представительных наборов и задача об устойчивости // Ж. вычисл. матем. и матем. физ. 1995. Т. 35, Л 1. С. 123-134.

27. Дюкова E.B. Асимптотически оптимальные методы построения тупиковых покрытий в задачах распознавания и анализа информации // Тез. докл. межд. конф. "Интеллектуализация обработки информации (МОИ'96)". Алушта, 1996. С. 11.

28. Дюкова Е.В., Журавлев Ю.И., Зенкин A.A. и др. Пакет прикладных программ для решения задач распознавания и классификации (ПАРК). М.: ВЦ АН СССР, 1981. 23 с.

29. Дюкова Е.В., Журавлев Ю. И., Рудаков К. В. Об алгебро-логической коррекции элементарных алгоритмов распознавания // Тез. докл. межд. конф. "Матем. методы распознавания образов (ММРО-7)". Москва, 1995. С. 25-26.

30. Дюкова Е.В., Журавлев Ю.И., Рудаков К.В. Об алгебро-логическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // Ж. вычисл. матем. и матем. физ. 1996. Т. 36, JÉ 8. С. 217-225.

31. Дюкова Е.В., Журавлев Ю.И., Рязанов В.В. Диалоговая система анализа и распознавания образов. М.: ВЦ АН СССР, 1988, 40 с.

32. Дюкова Е.В., Карнеева И.Л. Модели распознающих алгоритмов, основанные на различных способах перекодировки исходной информации // Матем. методы в распознавании образов и дискретной оптимизации. М.: ВЦ АН СССР, 1990. С. 43-56.

33. Дюкова Е.В., Рязанов В.В. Исследование задач распознавания в диалоговых распознающих системах // Тез. докл. II Всес. конф. "Мат. методы распознавания образов". Ереван: Изд-во АН АрмССР, 1985. С. 76-78.

34. Дюкова Е.В., Рязанов В.В. О решении прикладных задач алгоритмами распознавания, основанными на принципе голосования. М.: ВЦ АН СССР, 1986. 26 с.