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

Введение

Глава I. НЕКОТОРЫЕ ОЦЕНКИ СТЕПЕНИ ДОСТОВЕРНОСТИ ГИПОТЕЗ ОБ

ИМШШКАТИВНЫХ ЗАКОНОМЕРНОСТЯХ.

§ I. Модель импликативных закономерностей и логическое распознавание образов, необходимые сведения.

§ 2. Верхняя оценка и оценка погрешности для оценки У\/{м>пЛ).

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

Глава II. МОДЕЛЬ СТОХАСТИЧЕСКИХ ИМПЛИКАТИВНЫХ ЗАКОНОМЕРНОСТЕЙ И РАСПОЗНАВАНИЕ ОБРАЗОВ.

§ 4. Стохастические импликативные закономерности и оценки степени достоверности соответствующих гипотез.

§ 5. Аппроксимация оценок известными вероятностными распределениями.

§ 6. Логико-статистические правила предсказания.

Глава III. МОДЕЛЬ ФУНКЦИОНАЛЬНЫХ ЗАКОНОМЕРНОСТЕЙ И ЛОГИЧЕСКОЕ РАСПОЗНАВАНИЕ ОБРАЗОВ.

§ 7. Описание модели и необходимые сведения.

§ 8. Оценки степени достоверности гипотез о функциональных закономерностях.

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

§ 10. Распознавание как логический вывод

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

Предлагаемые методы можно отнести к числу логических методов в теории распознавания образов, где для построения решающих правил привлекаются аппарат алгебры логики, исчисление высказываний или теория логических выводов [1-5, 12-14, 29] . Одновременно подход к решению задачи реконструкции множества и использованию найденной системы закономерностей для распознавания образов, восходящий к работе [12] , намечается в рамках более общей проблемы обнаружения закономерностей в потоке данных, проблемы преобразования последних в "знание", т.е. некую адекватную модель исследуемого класса данных, позволяющую оперативно находить решение разнообразных задач типа распознавания образов, классификации, прогнозирования, автоматической группировки, заполнения пропусков в экспериментальных таблицах [5-10 ] .

Наиболее известными среди логических алгоритмов распознавания являются алгоритм Ю.И.Журавлева, основанный на использовании понятия "тупиковых тестов" [I] и алгоритм КОРА [2,3} , предназначенный для определения логических закономерностей в виде конъюнкций значений признаков. Решающее правило в обоих случаях задается в виде алгоритмической процедуры: для распознавания объектов используется голосование либо по конъюнкциям, либо по "тупиковым тестам".

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

В работах [П-14] строятся логические разделители для классов в задаче распознавания образов на основе методов минимизации ДНФ булевых и частичных булевых функций.

Более полное и систематическое введение, развитие и применение аппарата исчисления высказываний и методов алгебры логики для решения задачи распознавания в булевом случае признаков изложено в работе А.А.Горелика и В.А.Скрипкина [5] .

В последнее время возрос интерес к проблеме обнаружения закономерностей в таблицах экспериментальных данных. Современное состояние этой проблемы отражено в материалах трех всесоюзных симпозиумах: МОЗ-1 (Новосибирск, 1976), МОЗ-П (Рига, 1979) и МОЗ-Ш (Новосибирск, 1980) [7,8,9] и также в монографиях Н.Г.За-горуйко [б] , Г.С.Лбова [10] .С точки зрения машинных методов обнаружения закономерностей(МОЗ) задача распознавания образов является лишь частичным случаем задачи эмпирического предсказания [б] и процедура распознавания обычно распадается на два этапа. Первый этап (обучение) представляет собой процесс обнаружения (поиска) закономерностей определенных типов. Второй этап (распознавания) - использование найденных закономерностей ("знание") для предсказания значения целевого признака новых объектов. Некоторые рано возникшие логические методы распознавания можно разбирать также по этой схеме (например, алгоритмы: КОРА, "Тупиковых тестов" .). Отметим, что проблема представления закономерностей, проблема поиска закономерностей и проблема их использования для решения задач эмпирического предсказания (классификацию таких задач можно найти в [iö] ) являются главными вопросами направления исследований, известных под названием МОЗ ( [7] - с. 2-3, [8] - с. 3-4 ).

Одним из центральных понятий МОЗ является понятие "закономерность". Формулировка этого понятия представляется довольно сложной проблемой и обсуждается в работах [l6,I7J . В общих словах это понятие сводится к следующему: закономерность есть некоторое гипотетическое утверждение об определенных свойствах изучаемых объектов и само обладающее определенными характеристиками (такими как простота, мощность, подтвержденность, красота . ). До сих пор задачу определения этого понятия нельзя считать полностью решенной. Несмотря на это предлагают все больше методов эмпирического предсказания. При этом в каждом отдельном случае понятие закономерности конкретизируется. Эвристический выбор типа закономерностей и различие методов их использования объясняют разнообразие существующих методов эмпирического предсказания. Остановимся на некоторых важных работах.

Видимо, первыми алгоритмами, описанными в рамках МОЗ являются алгоритм ЭМП-1 Н.Г.Загоруйко и Б.П.Гаврилко [18] и алгоритм ЭМП-2 Е.Е.Витяева [19] . В алгоритме ЭМП-1 используются многоместные отношения на объектах и для выбора допустимых решений применяется критерий предпочтения отношений по их простоте. Алгоритм ЭМП-2 предназначается для предсказания значения многоместного предиката относительно некоторого объекта и ищет закономерность в виде "посылок-следствий", если последняя связь удовлетворяет некоторому статистическому критерию. Процедура предсказания основана на дополнительном цредположении о независимости найденных закономерностей и оценке достоверности предсказуемого значения данного предиката на совокупностях закономерностей "за" и закономерностей "против".

В.И.Котюков в работе [20 ] предлагает метод "обобщающих закономерностей" для распознавания образов в случае булевых признаков. В этом методе решающее правило синтезируется на классе условных парных корреляций признаков.

Для многозначных признаков В.Е.Голендер в работе [21] излагает метод обнаружения логических закономерностей в виде конъюнкций значений признаков.

В работе Л.А.Растригина [22] рассматривается проблема синтеза эффективного правила предсказания значения выхода объекта по значениям входа, содержащимся в обучающей выборке. Алгоритм синтеза основан на методе многомерной линейной экстраполяции.

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

10] уделяется алгоритмической цроблеме перебора при поиске закономерностей и реализации метода на ЭВМ.

Как отмечают многие авторы, например, в [Ю, 23-25] , в работах по распознаванию образов, основанных на поиске наилучшего решающего правила из некоторого класса без предварительного восстановления функций распределения вероятности при ограниченной выборке, возникает задача определения связи между сложностью класса и объемом выборки. Этот вопрос является наиболее важным и трудным в общих теоретических исследованиях.

В работе В.Н.Вапника и А.ЯДервоненкиса [23] для решения данной задачи используется понятие равномерной сходимости частот появления событий к их вероятностям. Эта работа установила важный теоретический результат: для надежного распознавания необходимо ограничиться классами решающих правил небольшой сложности. Однако оценка объема обучающей выборки, рассматриваемая в [23] слишком завышена, что не позволяет точно количественно определить указанную связь.

Подобные задачи для различных типов классификаторов исследовались в работе Ш.Ю.Раудиса [24] , где мерой сложности классификаторов служит размерность пространства переменных и предполагается, что имеет место нормальное распределение.

Для произвольного распределения Г.С.Лбов (см., например, [ю] ) предлагает один Байесовский подход к решению данной проблемы. Приведен: пример, показывающий преимущество данного подхода по сравнению с подходом В.Н.Вапника. Однако, в большинстве случаев, не удается выразить изучаемую зависимость в явном виде.

Для практического табулирования указанной зависимости обычно используются моделирование на ЭВМ, аналитический метод или асимптотические разложения. Например, в [10] применяется метод моделирования, в [24] - метод моделирования в сочетании с аппроксимацией, приближенного вычисления, в [25] - асимптотический метод.

Вопросы о соотношении сложности класса решающих правил и объема выборки в задачах предсказания количественного признака рассмотрены в работе [26] , для метода распознавания образов, основанных на логических решающих функциях - в работе [27] , а для задачи упорядочения объектов - в работе [28] .

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

10] - с. 14, с. 38; [21] - с. III; [34] - с. 79 .) и таким образом остается нестрого обоснованным.

А.Д.Закревский в работах [12,30,31] предлагает основывать распознавание образов в булевом пространстве признаков на цред-варительном построении "области запрета", описываемой посредством ДНФ с конъюнкциями ограниченного ранга. Упомянутые конъюнкции, задающие запретные интервалы в булевом пространстве, интерпретируются как импликативные закономерности. Простота этой закономерности оценивается, естественно, числом переменных, входящих в нее, т.е. рангом конъюнкции, а мощность - объемом области запрета. Распознавание основано на решении задачи реконструкции множества "реальных" объектов, подчиняющегося определенным имплика-тивным закономерностям по его случайной выборке. При этом необходимо определить степень достоверности гипотезы об импликативных закономерностях, выдвигаемой при анализе выборки. В работе [12] было предложено оценить эту степень достоверности через вероятность Р (м, п, С) появления хотя бы одной закономерности данного типа ранга Ь в случайной выборке объема по при фактическом отсутствии всяких закономерностей в пространстве п признаков.

Введение величины Р и условие РСт'пЛ) ^ & . где 6 - достаточно малое пороговое значение, позволяют установить зависимость между параметрами м , п ,{ и обосновывают выбор максимального допустимого значения ранга Ь при заданных т.п.

Выборка, не содержащая ни одной импликативной закономерности ранга Ь » называется "протыкающей" (см. [Зб] ), так как в этом случае каждый интервал ранга £ в пространстве п признаков "протыкается" по крайней мере одной точкой из выборки. Оценки минимальной длины "протыкающей" выборки даются в работах [36,37]. А оценка числа "протыкающих" выборок, фактически, была получена впервые (снизу) в работе [30] .

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

Данный метод распознавания образов имеет следующие важные особенности:

1. Выбранная форма закономерностей универсальна в смысле описания любых закономерностей в булевом пространстве. Причем такая форма позволяет использовать хорошо развитую теорию минимизаций булевых функций для сжатого представления закономерностей в виде ДНФ-модели [12,31] . Практически удобные алгоритмы построения ДНФ-модели изложены в работах [32,33] .

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

3. Численные результаты по вычислению верхней оценки для вероятности показывают, что для выполнения условия ранг закономерностей должен быть малым по сравнению с размером цространства [30 ] . Это существенно ограничивает перебор, производимый при поиске закономерностей и делает реальной его реализацию на ЭВМ. Поэтому алгоритмическая проблема перебора не возникает.

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

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

В соответствии с вышепоставленными целями диссертация разбита на 3 главы и 10 параграфов. Приступаем к ее краткому изложению.

КРАТКИЕ ВЫВОДЫ

1. Предложена оценка для степени достоверности гипотезы о функциональных закономерностях р^Оч^Е) (40). Для ее практического вычисления доказано предельное соотношение (41). Проведены численные эксперименты на ЭВМ по вычислению величины и определению максимального допустимого значения ранга функциональных закономерностей, которые можно найти при ограниченной образующей выборки Мд . Полученные результаты подтверждают применимость цриближенной формулы (41) (таблица 9).

2. Оценена достаточная длина обучающей выборки Мэ для полного выявления всех булевых функций, представляющих данную структуру функциональных зависимостей 5(Х) (оценки (46), (48)).

3. Установлены некоторые свойства системы булевых функций, представляющих данную структуру функциональных зависимостей (утверждения 3.5 - 3.8).

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

1. Журавлев Ю.И., Дмитриев А.Н., Кренделев Ф.П. О математических принципах классификации предметов и явлений. - Дискретный анализ, 1966, вып. 7, с. 3-15.

2. Бонгард М.М. Проблема узнавания. М., Наука, 1967. 320 с.

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

4. Хант Э., Марин Дж., Стоун Ф. Моделирование процесса формирования понятий на вычислительной машине. М., Мир, 1970, 301 с.

5. Горелик A.A., Скрипкин В.А. Методы распознавания. М., Высшая школа, 1977. 222 с.

6. Загоруико Н.Г. Эмпирическое предсказание. Новосибирск, Наука, 1979, 124 с.

7. Машинные методы обнаружения закономерностей. Сборник статей под редакцией Загоруйко Н.Г. Новосибирск. Ин-т математики СО АН СССР, 1976. 168 с.

8. Машинные методы обнаружения закономерностей. Сборник статей под редакцией Растригина Л.А. Рига, Рижский политехнический институт, 1981. 200 с.

9. Вычислительные системы, 1979, вып. 79. Новосибирск, Наука,

10. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск, Наука, 1981. 160 с.

11. Журавлев Ю.И. Об отделимости подмножеств вершин П -мерного единичного куба. Труды Мат. ин-та АН СССР, 1958, 51, с • *

12. Закревский А.Д. Комбинаторные задачи искусственного интеллекта. Семиотика и информатика, вып.15, М.: ВИНИТИ ,1980, с. 3-17.

13. Гуревич И.Б., Журавлев Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания. Кибернетика, 1974, № 3, с 16-20.

14. Асланян Л.А. Об одном методе распознавания, основанном на разделении классов дизъюнктивными нормальными формами. -Кибернетика, 1975, № 5, с. 103-110.

15. Загоруйко Н.Г. Классификация задач прогнозирования на таблицах "объект-свойство" Вычислительные системы, 1981, вып. 88, с. 3-7.

16. Загоруйко Н.Г. Некоторые проблемы автоматического обнаружения закономерностей. В кн.: Машинные методы обнаружения закономерностей. Новосибирск, 1976, с. 6-15.

17. Загоруйко Н.Г. Об определении понятия "закономерностей". -Вычислительные системы, 1979, вып. 79, с. 1-4.

18. Гаврилко Б.П., Загоруйко Н.Г. Универсальный алгоритм эмпирического предсказания. Вычислительные системы, 1973, вып. 55, с. 134-138.

19. Витяев .В.Е. Алгоритм эмпирического предсказания. Вычислительные системы, 1975, вып. 61, с. 28-37.

20. Котюков В.И. Распознавание образов в булевом цространстве.-Вычислительные системы, 1971, вып. 44, с. 23-34.

21. Голендер В.В., Розенблит А.Б. Алгоритм выявления экспериментальных закономерностей и восстановления функциональной зависимости. В кн.: Распознавание образов, № I, "Зинатне", 1974, с. 118-127.

22. Растригин Л.А., Фабрикант М.И. Эмпирическое прогнозирование методом многомерной линейной экстраполяции. В кн.: Машинные методы обнаружения закономерностей, Новосибирск, 1976, с. 85-89.

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

24. Раудис Ш.Ю. Ограниченность выборки в задачах классификации Статистические проблемы управления, 1976, вып. 18, 180 с.

25. Деев А.Д. Асимптотические разложения распределений статистик дискриминантного анализа. Статистические методы классификации, 1972, вып. 31, с. 12-23.

26. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М., Наука, 1979, 447 с.

27. Монохин А.Н. Методы распознавания образов, основанные на логических решающих функциях. Вычислительные системы, 1976, вып. 67, с. 42-53.

28. Манохин А.Н. Об одном подходе к прогнозированию перспективности объектов. Вычислительные системы, 1978, вып. 74,с. 108-128.

29. Закревский А.Д. К формализации полисиллогистики. В кн.: Логический вывод. М., Наука, 1979, с. 300-309.

30. Закревский А.Д. К выбору гипотез при поиске закономерностей в булевом пространстве. ДАН БССР, 1981, т.25, J 3, с.236-238.

31. Закревский А.Д. Выявление импликативных закономерностей в булевом пространстве признаков и распознавание образов. -Кибернетика, 1982, » I, с. 1-6.

32. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М., Наука, 1971. 512 с.

33. Закревский А.Д. Логические уравнения. Минск, Наука и техника, 1975. 94 с.

34. Лбов Г.С. Об одном непараметрическом подходе в задачах эмпирического предсказания. В кн.: Адаптивные системы и их приложения. Новосибирск, 1978, с. 78-81.

35. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М., Наука, 1982. 382 с.

36. Нечипорук Э.И. О сложности вентильных схем, реализующих булевы матрицы с неопределенными элементами. ДАН СССР, 1965, т. 163, й I, с. 40-43.

37. Леонтьев В.К. Верхняя оценка ОС-глубины (0,1)-матриц. -Математические заметки, 1974, т.15, вып. 3, с. 421-429.

38. Кендалл М. Дж., Стьюарт А. Теория распределений. М., Наука, 1966. с. 587.

39. Болыиев Л.Н., Смирнов Н,В. Таблицы математической статистики. М., Наука, 1965. 464 с.

40. Большев Л.Н., Гладков Б.В., Щеглова М.В. Таблицы для вычисления Б" и распределении. Теория вероятностей и ее приложения, 1961, № 6, с. 446-455.

41. Неклюдова Е.А., Цаленко М.Ш. Синтез логической схемы реляционной базы данных. Программирование, 1979, № 6, с. 5868.

42. Дрибас В.П., Курскова Г.Л., Столяров Г.К. Введение в реляционные модели базы данных. Минск, ИМ АН БССР, препринт, 1977. 63 с.

43. Кокорева Л.В., Малашинин И.И. Проектирование банков данных. М., Наука, 1984, 256 с.

44. Брудно В.А. Реляционные модели базы данных вывод ответа на запрос. Программирование, 1977, № 2, с. 101-108.

45. Найденова К.А. Реляционная модель анализа экспериментальных данных Изв. АН СССР. Тех. кибернет., 1982, № 4, с. 103-119.

46. Закревский А.Д., Данг Динь Куанг. К выявлению функциональных закономерностей в булевом пространстве признаков. ДАН БССР, 1983, т.27, №3, с. 225-227.

47. Закревский А.Д., Данг Динь Куанг. К оценке степени достоверности имдликативных закономерностей в булевом пространстве признаков. ДАН БССР, 1984, т.28, № 12, с. 1094-1096.

48. Данг Динь Куанг. Функциональная модель обнаружения закономерностей и распознавание образов в булевом пространстве признаков. Минск, 1984, 30 с. Рукопись представлена редкол. журн.

49. Известия АН БССР, сер. физ.-мат. наук. Деп. в ВИНИТИ 19.06. 1984 г., £ 4070-84 Деп.

50. Данг Динь Куанг. Оценка степени достоверности гипотез о функциональных закономерностях в булевом пространстве признаков. -Вестн. Белорусского ун-та. Сер. I, физ., мат. и мех., 1985, В I, с. 29-33.

51. Феллер В. Введение в теорию вероятностей и ее приложений. -М., 1967, т.1.

52. РибйчйЛхлд (игыраку , , $80-£8Ъ.