Оценки достоверности импликативных и функциональных закономерностей при распознавании в булевом пространстве признаков

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

О •
Введение

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

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

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

§ 2. Верхняя оценка Д/ и оценка погрешности для оценки

§ 3. Нижние оценки р-(т,ус, С) , Р~(т,У),1)

и определение максимального допустимого значения ранга имшшкативных закономерностей....
Глава II. МОДЕЛЬ СТОХАСТИЧЕСКИХ ИМШШКАТИВНЫХ ЗАКОНОМЕРНОСТЕЙ И РАСПОЗНАВАНИЕ ОБРАЗОВ
§ 4. Стохастические импликативные закономерности и оценки степени достоверности соответствующих
гипотез
§ 5. Аппроксимация оценок известными вероятностными распределениями
§ 6. Логико-статистические правила предсказания
Глава III. МОДЕЛЬ ФУНКЦИОНАЛЬНЫХ ЗАКОНОМЕРНОСТЕЙ И ЛОГИЧЕСКОЕ РАСПОЗНАВАНИЕ ОБРАЗОВ
§ 7. Описание модели и необходимые сведения
§ 8. Оценки степени достоверности гипотез о
функциональных закономерностях
§ 9. Некоторые свойства системы частичных булевых функций, представляющих данную схему функциональных закономерностей
§ 10. Распознавание как логический вывод
Литература

В настоящей работе предлагаются некоторые методы распознавания образов в булевом пространстве признаков. Они основываются на решении задачи "реконструкции" множества абстрактных объектов, представляемых соответствующими точками булева пространств ва, по его случайной выборке при предположении, что структура упомянутого множества удовлетворяет определенным свойствам или "закономерностям". Рассматриваются некоторые типы закономерностей. Оценивается степень достоверности соответствующих гипотез в зависимости от их сложности, размера булева пространства и объема обучающей выборки. На базе закономерностей, обнаруживаемых при обучении, отроятся процедуры дифференцированного предсказания, позволяющие обоснованно распознавать любой признак частично описанных объектов, не вошедших в обучающую выборку.
Предлагаемые методы можно отнести к числу логических методов в теории распознавания образов, где для построения решающих правил привлекаются аппарат алгебры логики, исчисление высказываний или теория логических выводов [1-5, 12-14, 29] . Одновременно подход к решению задачи реконструкции множества и использованию найденной системы закономерностей для распознавания образов, восходящий к работе [12] , намечается в рамках более общей проблемы обнаружения закономерностей в потоке данных, проблемы преобразования последних в "знание", т.е. некую адекватную модель исследуемого класса данных, позволяющую оперативно находить решение разнообразных задач типа распознавания образов, классификации, прогнозирования, автоматической группировки, заполнения пропусков в экспериментальных таблицах [5-10]
Наиболее известными среди логических алгоритмов распознавания являются алгоритм Ю.И.Журавлева, основанный на использовании понятия "тупиковых тестов" [I] и алгоритм КОРА [2,31 , предназначенный для определения логических закономерностей в виде конъюнкций значений признаков. Решающее правило в обоих случаях задается в виде алгоритмической процедуры: для распознавания объектов используется голосование либо по конъюнкциям, либо по "тупиковым тестам".
В работах Ханта и других [4] рассматриваются вопросы построения процедур формирования понятий, использующих различные эвристические соображения. В основном это сводится к анализу и выбору наименьшего числа правил, разделяющих эталонные классы объектов.
В работах [П-14] строятся логические разделители для классов в задаче распознавания образов на основе методов минимизации ДНФ булевых и частичных булевых функций.
Более полное и систематическое введение, развитие и применение аппарата исчисления высказываний и методов алгебры логики для решения задачи распознавания в булевом случае признаков изложено в работе А.А.Горелика и В.А.Скрипкина [б]
В последнее время возрос интерес к проблеме обнаружения закономерностей в таблицах экспериментальных данных. Современное состояние этой проблемы отражено в материалах трех всесоюзных симпозиумах: МОЗ-1 (Новосибирск, 1976), МОЗ-П (Рига, 1979) и МОЗ-Ш (Новосибирск, 1980) [7,8,9] и также в монографиях Н.Г.За-горуйко [б] , Г.С.Лбова [Ю] .С точки зрения машинных методов обнаружения закономерностей(МОЗ) задача распознавания образов является лишь частичным случаем задачи эмпирического предсказания [б] и процедура распознавания обычно распадается на два этапа. Первый этап (обучение) представляет собой процесс обнаруже-

мент Д -го порядка В^ (т;п,£; N1) случайной величшш 'Щ
есть математическое ожидание случайной величины , поэтому:

=^11С] Ры(^ = 0= РСА^.^А^).,
1=Л Н4<-<^4т
где Р(Ац Ау) - вероятность того, что данная конъюнкция имплицируется по крайней мере ] фиксированными строками ,
^ , ... . ^ выборки. Следовательно,
В;(т,п,Е,Ы) = Ст^ГУ1г,4е д
smri
Нам достаточно доказать, что при выполнении условий утверждения Р„№-0 стремится к вероятности Роо^-0 того,
что ^ - I , где случайная величина распределена по
-°г
Пуассону с параметром Л = в . Будем использовать технику, изложенную в §§ 2,3 главы У1 работы [Зб] , согласно которой из сходимости биномиальных моментов распределения ^ к биномиальным моментам распределения Пуассона с параметром Л следует сходимость и самого распределения к распределению Пуассона
с тем же параметром Л
Исследуем поведение (щпЛм) если т , п , Р , N
со , но остаются удовлетворяющими условиям утверждения. Имеем:
В;(тА1(М) =^П1(1-А^)
6 д ■ к-о
Используя неравенство ^ ^ ^ ~^ О <^ < I
получаем: