§ 8.3. Применение метода Монте — Карло для оценки эффективности логических систем распознавания

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

Число испытаний необходимое для того, чтобы вероятность отклонения оценки величины от своего истинного значения меньше чем на 26 превышала определяется по формуле

Исходными данными для метода Монте — Карло в задаче служат:

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

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

3. Запрограммированный на ЭВМ алгоритм нахождения решения системы булевых уравнений:

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

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

Опишем алгоритм работы рассматриваемой модели. Предположим, что указанные исходные данные занесены в память ЭВМ. Обозначим через реализацию случайной величины , равномерно распределенной в интервале (0, 1]. вырабатывается соответствующим ДСЧ каждый раз независимо. Предположим, что произведено разбиение отрезка раз на три части, пропорциональные и еще раз на три части, пропорциональные

Испытания проводятся последовательно для каждого типа объекта Пусть объекту типа соответствует некоторая колонка сокращенного базиса Перенесем эту колонку в рабочую ячейку памяти ЭВМ. В этой ячейке значения истинности элементов равные 0 или 1, случайным образом подвергаются изменению в соответствии со значениями вероятностей Для колонки с номером процедура изменения значений истинности производится в такой последовательности. При помощи операции

сравнения устанавливают содержимое разряда ячейки. Если то переходят к проверке условий:

если то проверяют условия

где реализация случайной величины равномерно распределенной в [0, 1].

Если и выполняется первое условие (8.38), содержимое разряда ячейки не изменяется; если выполняется второе условие (8-38), то заменяется на если имеет место последнее неравенство (8.38), то заменяется на

Если и удовлетворяется первое из условий (8.39), то сохраняется неизменным; если выполняется второе условие (8.39), то заменяется на если выполняется последнее условие (8.39), то содержимое разряда ячейки заменяется на

Переходят к следующему разряду ячейки и для очередной реализации случайной величины проверяются условия (8.38) или (8.39).

Измененная в соответствии с данными правилами ячейка поступает на вход алгоритма решения задачи (8.37). После получения решения устанавливается, какой из случаев

реализуется при заданном типе распознаваемого объекта Врезультате многократного повторения описанного процесса подсчитываются количества выпадений каждого из случаев (8.40) и определяются оценки величин (8.35).