Построение систем распознавания образов (стр. 20 из 36)

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

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

-отработку и отладку программного обеспечения сложной системы;

-оценку характеристик отдельных средств и получение исходных данных для полной оценки системы.

Л Е К Ц И Я 5.3

Метод статистических испытаний

(метод Монте-Карло)

5.3.1. Основное определение

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

Приемлемость указанного метода обусловливается тем, что

1)расчет оценок выходных параметров осуществляется с использованием достаточно простых алгоритмов обработки.

2)просто и точно определяется необходимый объем моделирования из условия достижения заданной точности оценок выходных показателей.

3)методика организации экспериментов на модели достаточно проста и хорошо программно реализуема.

В этом легко убедиться на простых примерах. А пока рассмотрим определение.

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

Рассмотрим простейшие примеры.

А. Пусть необходимо определить вероятность P_ч того, что суммарное число попаданий при стрельбе в “десятку” мишени при 10 выстрелах - четно.

Известно, что если вероятность попадания в “десятку” при одном выстреле равна p , то искомая вероятность согласно биномиальному закону распределения вероятностей вычисляется так:

Здесь

- число сочетаний из 10 по 2k.

Если предварительно подсчитать все числа сочетаний при k=0…5 или использовать готовую таблицу сочетаний, то вычисления P_ч по указанной формуле потребуют 26 операций.

Вместо такого расчета можно было бы экспериментально выполнить N серий стрельб по 10 выстрелов и определить из их числа количество серий n_ч , в которых число попаданий в “десятку” - четное. Тогда при достаточно большом N имеем

Однако при таком подходе для получения достоверными в оценке Pч двух знаков после запятой потребуется около 10 000 серий по 10 выстрелов.

Оказывается, что ЭВМ позволяет выполнить решение указанной задачи третьим способом.

Как известно многие языки программирования имеют в составе стандартных функций датчик случайных чисел, позволяющий формировать случайную последовательность равномерно распределенных чисел на интервале [0,1].

Поэтому вместо выстрела по мишени достаточно выбрать из датчика указанное число со значением x и проверить выполнение неравенства x<p. Если оно выполнено, то это соответствует попаданию в “десятку” с вероятностью p. Покажем это.

Действительно вероятность попадания случайной величины в интервал [0;p] равна

,

где w(x) - плотность распределения вероятности

В нашем случае имеем дело с равномерным распределение на единичном интервале, то есть w(x) = 1. Поэтом P_0;р = p.

Выбираем теперь серии из 10 чисел x. Если при этом число “попаданий” (выполнения неравенства x<p) будет четным, считаем серию удачной.

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

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

Таким образом задача в рассмотренном случае была решена (согласно определению метода Монте-Карло) путем построения случайной последовательности с параметром, равным искомой величине P_ч. Эта последовательность была построена следующим образом:

-формирование на первом этапе равномерно распределенной последовательности на интервале [0,1] ;

-формирование на втором этапе новой случайной последовательности (N серий) группировкой полученных на первом этапе значений в серии по 10;

-формирование на третьем этапе искомой случайной последовательности путем выборки из последовательности серий второго этапа размера N таких, в которых неравенство x<p выполняется четное число раз.

Количество серий третьего этапа формирования и определяет частость

которая при N ®¥ стремится к искомой величине P_ч .

Б.Еще один пример, но из области непосредственного применения метода Монте-Карло к вычислению интегралов.

Пусть необходимо вычислить

При этом будем считать, что 0<=x<=1 и 0<= g(x) <=1 , то есть вся функция лежит в единичном квадрате.

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

Y

1

y = g(x)

x

1

Рис.5.3.1.

Будем рассматривать две области на плоскости (x,y)

W - область, заданная неравенствами

0<= x <=1

0<= y <=1

w - область, ограниченная кривой y = g(x) и ординатами x=0 и x = 1.

Площадь области W равна единице S1=1, а площадь области w_S2 = I.

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

Плотность заданного распределения вероятностей f(x,y) = 1

Ïîýòîìó âåðîÿòíîñòü ïîïàäàíèÿ òî÷êè â îáëàñòü w ðàâíà

Таким образом, I = S₂.

Если теперь мы располагаем возможностью имитировать случайные точки с координатами x_i, y_i в соответствии с заданной плотностью, то после N испытаний, подсчитав число тех из них (m), которые попали в область w , получим частость

Вспоминаем, что частота при N ®¥ стремится к истинному значению, а в качестве приближенного значения интеграла следует использовать указанную частоту.

Подводя итог рассмотренному примеру с точки зрения введенного определения метода Монте-Карло, отметим, что

-решаемая задача относится к области вычислительной математики;

-для решения задачи формировалась случайная последовательность чисел как выборка значений из последовательности с равномерной плотностью распределения вероятностей, попадающих в область w;

-искомая величина определялась как отнесение числа попаданий в область w к общему числу экспериментов.

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