Искусственный интелект

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

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

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

Исходя из полученных выводов, в данной работе была использована нейронная сеть для  распознавания графических образов.

 

 

2.  Генератор псевдослучайных величин

 

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

Аппаратные  ГСЧ представляют собой устройства, преобразующие в цифровую форму  какой-либо параметр окружающей среды  или физического процесса. Параметр и процесс выбираются таким образом, чтобы обеспечить хорошую «случайность»  значений при считывании. Очень часто  используются паразитные процессы в  электронике (токи утечки, туннельный пробой диодов, цифровой шум видеокамеры, шумы на микрофонном входе звуковой карты и т.п.). Формируемая таким  образом последовательность чисел, как правило, носит абсолютно  случайный характер и не может  быть воспроизведена заново по желанию  пользователя.

К программным  ГСЧ относятся различные алгоритмы  генерирования последовательности чисел, которая по своим характеристикам  напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Любые программные  ГСЧ, не использующие внешних «источников  энтропии» и формирующие очередное  число только алгебраическими преобразованиями, не дают чисто случайных чисел. Последовательность на выходе такого ГСЧ выглядит как  случайная, но на самом деле подчиняется  некоторому закону и, как правило, рано или поздно повторяется. Такие числа называются псевдослучайными.

В дальнейшем мы будем рассматривать лишь программные  генераторы псевдослучайных чисел.

 

1. Генератор псевдослучайных величин, построенный методом обратной функции (непрерывная величина).

 

Исходными данными  для формирования НПСВ методом обратной функции является функция плотности f(y).

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

Построение  генератора осуществляется следующим  образом: путем интегрирования функции  плотности находится функция  распределения 

.

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

Взаимно однозначная  монотонная функция Y=F^-1(X) преобразует равномерно распределенную на интервале [0, 1] величину X в Y с требуемой плотностью f(y) [7].

Чтобы получить число, принадлежащее последовательности чисел {y_i}, имеющих функцию плотности f(y), нужно разрешить относительно y_i уравнение

                 (1.1)

Алгоритм  работы генератора:

1. Т.к. диапазон значений функции распределения – [0, 1], то от генератора БПСВ формируется очередное значение x в диапазоне [0, 1].
2. Вычисляется y - значение функции, обратной функции распределения, в точке х.

 

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

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

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

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

 

2. Генератор псевдослучайных величин, построенный методом обратной функции (дискретная величина).

 

Исходными данными для формирования ДПСВ методом обратной функции является дифференциальное распределение вероятностей, т. е. множество пар  , где y_i – перечень значений ДПСВ, P_i – перечень вероятностей появления этих значений. При этом интегральная функция распределения

; ; 1, 2, …;

; .

Если X - равномерно распределенная на интервале [0, 1] случайная величина, то искомая случайная величина Y получается с помощью преобразования , где - функция, обратная [8].

Таким образом, данный метод формирования ДПСВ заключается  в использовании частичных сумм вероятностей в качестве функции, обратной функции распределения, для получения  ДПСВ с заданным распределением.

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

Алгоритм  работы генератора:

1. Т.к. диапазон значений функции распределения – [0, 1], то от генератора базовой ПСВ (БПСВ) формируется очередное значение x в диапазоне [0, 1].
2. Сгенерированное значение x БПСВ последовательно сравнивается с частичными суммами вероятностей:

если x£p₁, то y=у₁, иначе,

если х£р₁+р₂, то y=у₂, иначе,

× × ×

если  то y=у_k .

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

 

3. Генератор псевдослучайных величин, построенный универсальным методом.

 

Исходными данными  для формирования НПСВ универсальным  методом является функция плотности f(y).

Данный метод  основан на кусочной аппроксимации  функции плотности. Пусть требуется  получить последовательность псевдослучайных  чисел {у_i} с функцией плотности f(y), возможные значения которой лежат в интервале (а, b). Представим f(у) в виде кусочно-постоянной функции, т. е. разобьем интервал (а, b) на т интервалов, и будем считать f(y) на каждом интервале постоянной. Тогда ПСВ Y можно представить в виде Y= y_k + Y_k^*, где y_k - абсцисса левой границы k-го интервала; Y_k^* - ПСВ, возможные значения которой располагаются равномерно внутри k-го интервала, т. е. на каждом участке (y_k,y_k+1) величина Y_k^* считается распределенной равномерно. Чтобы аппроксимировать f(у) наиболее удобным для практических целей способом, целесообразно разбить (а, b) на интервалы так, чтобы вероятность попадания ПСВ Y в любой интервал (y_k,y_k+1) была постоянной, т. е. не зависела от номера интервала k [8].

В уравнении 

,

где k = 0, 1,…, m, неизвестной величиной является y_k+1.

Построение  генератора данным методом заключается  в нахождении правых границ интервалов. Т.е. основным результатом проектирования генератора являются пороговые значения y, в рамках которых вероятность попадания значения ПСВ одинакова.

Диапазон  изменения БПСВ также разбивается  на m равновероятных интервалов.

Алгоритм  работы генератора сводится к последовательному  выполнению следующих действий:

1. От генератора БПСВ формируется очередное значение x_i в диапазоне [0, 1].
2. Определяется, какому из интервалов это число принадлежит, т.о. определяется случайно номер интервала, а точнее его левая граница y_k.
3. От генератора БПСВ формируется следующее значение x_i+1, которое масштабируется с целью приведения к интервалу (y_k,y_k+1), т.е. умножается на коэффициент (y_k+1 - y_k).
4. Вычисляется псевдослучайное значение y_i=y_k+(y_k+1 - y_k)× x_i+1

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

 

4. Проверка качества случайных величин

 

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

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

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

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

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

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

.

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

,

.

Возможно  определять степень расхождения, суммируя не абсолютные, а относительные отклонения с весами

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

Пирсон предложил метрику расстояний с такими коэффициентами , которые делают независимым распределение самой степени расхождения как случайной величины от закона распределения моделируемой случайной величины, так и от размера выборки n ( ). Метрика, в которой , особая и обозначается

.

 

Критерий согласия Пирсона

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

,

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

При таком  выборе коэффициентов мера расхождения  обозначается c²

.

Распределение c² зависит от параметра r, называемого числом «степеней свободы» распределения. Число «степеней свободы» определяется следующим образом: r = k – s, где k – число интервалов, s – количество ограничений, накладываемых на практическое распределение. Примерами таких ограничений могут быть требование того, чтобы сумма частот P_i^* была равна единице (это требование накладывается во всех случаях), требование совпадения теоретического и практического математических ожиданий, требование совпадения теоретической и практической дисперсии и т.д.