Исследование и реализация алгоритмов распознавания по представительным наборам на базе решения специальных систем булевых уравнений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

Глава I. МОДЕЛЬ РАСПОЗНАНИЯХ АЛГОРИТМОВ, ОСНОВАННЫХ

НА ВЫДЕЛЕНИИ ПРЕЩСТАВИТЕЛЬШХ НАБОРОВ.II

§ 1.1. Исходные определения.

§ 1.2. Представительные наборы. Определения и некоторые свойства

§ 1.3. Синтез множества представительных наборов

§ 1.4. Модель распознающих операторов. Описание и исследование полноты.

Глава 2. ЧИСЛЕННЫЕ МЕТОЛУ РЕАЛИЗАЦИИ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ПО ПРЕЩСТАЕИТЕЛЬШМ НАБОРАМ.

§ 2.1. Решение систем булевых уравнений специального вида.

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

Глава 3. ВЫЧИСЛИТЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ПО ПРЕДСТАВИТЕЛЬНЫМ НАБОРАМ.

§ 3.1. Общее описание комплекса программ АЛКОРА

§ 3.2. Описание отдельных блоков программного комплекса.

§ 3.3. Практическое применение программного комплекса АЛКОРА.

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

Методы первого типа /3,12,16,21,28/ состоят в том, что априори выбирается параметрическая модель алгоритмов распознавания с пороговыми решающими правилами. В этом случае условия правильного распознавания заданных контрольных объектов с использованием обучающих объектов описываются в виде систем неравенств. Задача оптимальной адаптации или выбора оптимального по точности алгоритма состоит, в этом случае, в подборе значений параметров, выделении в модели фиксированного алгоритма таких, что при этом выполняется максимальное число неравенств указанной выше системы.

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

А эта задача - одна из эталонно трудных задач вычислительной математики.

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

Описанные выше обстоятельства делают актуальным исследования хорошо зарекомендовавших себя на практике эвристических алгоритмов и разработку эффективных вычислительных методов для реализации таких алгоритмов на ЭВМ. Вывод об актуальности подобных исследований подкрепляется также тем, что второй класс современных методов, основанных на алгебраической /22-25,40,41/ или логической /27,31/ коррекции распознающих алгоритмов требует использования очень больших массивов памяти и поэтому далеко не всегда применяются на практике.

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

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

Различные алгоритмы, основанные на применении указанного принципа, описывались в разных терминах и получали разные названия: "Тест", "Кора", "Метод перебора конъюнкций" и т.д. /1-3,9,11-13,25,29,30,33,34/. На самом деле все эти алгоритмы могут быть описаны единым способом. Все они в той или иной форме связаны с построением и анализом полных или частичных совокупностей так называемых "представительных наборов" или, в другой терминологии, допустимых конъюнкций для всюду определенных булевых функций.

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

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

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

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

На базе проведенных исследований в диссертации разработан алгоритм, позволяющий в приемлемое время решать задачи распознавания с бинарной информацией, основанный на выделении максимальных интервалов частичных булевых функций или соответствующих им минимальных (тупиковых) представительных наборов. Алгоритм реализован на ЭВМ БЭСМ-6 на языке Ф0РТРАН-1У. С помощью алгоритма решены прикладные задачи.

Диссертация выполнялась в лаборатории проблем распознавания Вычислительного центра АН СССР.

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

1. Бонгард M.M. Проблемы узнавания. - M.: Наука, 1967. - 320 с.

2. Вайнцвайг М.Н. Алгоритм обучения распознавания "Кора". -В кн.: Алгоритмы обучения распознавания образов. М.:1973, с.110-116.

3. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. - М.: Наука, 1974. - 415 с.

4. Глаголев В.В. Некоторые оценки дизъюнктивных нормальных форм функций алгебры логики. В кн.: Проблемы кибернетики, вып.19, М.: Наука, 1967, с.75-94.

5. Голыптейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 374 с.

6. Гренандер У. Лекции по распознаванию образов. T.I, М.: Мир, 1979. 383 с.

7. Гренандер У. Лекции по распознаванию образов. Т.2, М.: Мир, 1981. 446 с.

8. Гренандер У. Лекции по распознаванию образов. Т.З, М. : Мир, 1983. 430 с.9. 11уберман Ш.А., Марипов Т.М. Оценка перспективности месторождений гидротермальных руд с применением ЭВМ. Труды МИНХ и Ц им. 1>бкина, вып.62, М.: Недра, 1966.

9. Дискретная математика и математические вопросы кибернетики, /под ред. Яблонского C.B., Лупанова О.Б., т.1, М.: Наука,1974. 305 с.

10. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.Г. О математических принципах классификации предметов и явлений. Сб.:Дискретный анализ, вып.7, Новосибирск, ИМ СО АН СССР, 1966, с.З-П.

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

12. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания. Дис.канд.физ.-матем.наук, М.:ВЦ АН СССР, 1978. 127 с.

13. Журавлев Ю.И. Об отделимости подмножеств /? -мерного единичного куба. Труды математического института им.В.А.Стек-лова АН СССР, т.51, М.: 1958, с.143-157.

14. Журавлев Ю.И. Об алгоритмах выделения совокупностей существенных переменных ескщ определенных функций алгебры логики. В кн.: Проблемы кибернетики, еып.П, 1964, с.271-275.

15. ЖуравлеЕ Ю.И. Экстремальные задачи, возникающие при обосновании эвристических процедур. Сб.: Проблемы прикладной математики и механики. М.: Наука, 1971.

16. Журдаев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок. Кибернетика, 3, Киев, 1971, c.I-II.

17. Журавлев Ю.И. Алгоритмы распознавания, основанные на вычислении оценок. Содержательный смысл параметров, задающих алгоритм. Труды международного симпозиума по практическим применениям методов распознавания образов. М.: ВЦ АН СССР, 1973, с.205-218.

18. Журавлев Ю.И., Камилов М.М., ТуляганоЕ Ш.Е. Алгоритмы вычисления оценок и их применение. Ташкент: ФАН, 1974. -119 с.

19. Журавлев Ю.И., Михалевич М. Алгоритмы распознавания, основанные на вычислении оценок, для задач с непересекающимися классами. Труды ЕЦ Польской АН, вып.145, Варшава,1974.

20. Журавлев Ю.И. Непараметрические задачи распознавания образов. Кибернетика, J5 6, Киев, 1976, с.93-103.

21. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов I. Кибернетика, № 4, Киев, 1977, с.14-21.

22. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов II. Кибернетика, № 6, Киев, 1977, с.21-27.

23. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов III. Кибернетика, $ 2, Киев, 1978, с.35-43.

24. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации. В кн.: Проблемы кибернетики, вып.33, М.: 1978, с.5-68.

25. Журавлев Ю.И., Платоненко И.М. Об экономном умножении булевых уравнений. Журнал вычисл.математики и матем.физики, т.24, В I, 1984, с.164-166.

26. ЗуеЕ Ю.А. Метод повышения надежности классификации при наличии нескольких классификаторов, основанный на принципе монотонности. Журнал вычисл.математики и матем.физики, т.21, № I, 1981, с.157-167.

27. Катериночкина H.H. Поиск максимального верхнего нуля монотонной функции алгебры логики. Доклады АН СССР, т.224,гё 3, 1975, с.557-560.

28. Константинов P.M., Королева З.Е., Кудрявцев Е.Б. О комбинаторно-логическом подходе к задачам прогноза рудоносно-сти. В кн.: Проблемы кибернетики, вып.31, 1976, с.5-33.

29. Королева З.Е. О сравнении тестовых алгоритмов распознавания. Журнал вычисл.математики и матем.физики, т.13, № 3, 1975, с.749-756.

30. Краснопрошин В.В. Об оптимальном корректоре совокупности алгоритмов распознавания. Журнал вычисл.математики и матем.физики, т.19, В I, 1979, с.204-216.

31. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 450 с.

32. Кудрявцев В.Б., Кудрявцев В.Б. О тестовом подходе к задаче о перспективности населенных пунктов. Сб.: Исследование операций. М.: ВЦ АН СССР, 1972.

33. Кузнецов В.Е. Об одном стохастическом алгоритме вычисления информационных характеристик таблиц по методу тестов. -Сб.: Дискретный анализ, еып.23, Новосибирск, ИМ СО АН СССР, 1973, с.8-23.

34. Мазный Г.Л. Программирование на БЭСМ-6 в системе "Дубна".- М.: Наука, 1978. 272 с.

35. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. - 318 с.

36. Носков В.Н. О тупиковых и минимальных тестах для одного класса таблиц. Сб.: Дискретный анализ, вып.12, Новосибирск, 1968, с.27-49.

37. Платоненко И.М. О реализации алгоритмов типа "Кора" с помощью решения систем булевых уравнений специального вида.- М.: ВЦ АН СССР, 1983. 21 с.

38. Рудаков К.В. О некоторых классах алгоритмов распознавания (общие результаты). М.: ВЦ АН COOP, 1980. - 66 с.

39. Рудаков К.В. О некоторых классах алгоритмов распознавания (параметрические модели). М.: ВЦ АН СССР, 1981. - 48 с.

40. Рудаков К.В. О некоторых классах алгоритмов распознавания. Дис.канд.физ.-матем.наук, М. : ВЦ АН СССР, 1981. - 100 с.

41. Салтыков А.И., Макаренко Г.И. Программирование на языке Фортран. М.: Наука, 1976. - 256 с.

42. Фу К. Структурные методы е распознавании образоЕ. М.: Мир, 1977. - 319 с.

43. Чегис И.А., Яблонский C.B. Логические способы контроля электрических схем. Труды математического института им.В.А.Стеклова АН СССР, т.51, M.: 1958, с.270-360.

44. Яблонский C.B. Функциональные построения е К значной логике. Труды математического института им.В.А.Стеклова АН СССР, т.51, с.5-142.

45. Nelson R.I. Simplest normal iruth f unctions . У- $умЁ>Ло9,'с,20ул/2, <f$553 -с. 105 - юр.