|
Реферат: Математические основы нейронных сетей (Программирование)
В наши дни возрастает необходимость в системах, которые способны не
только выполнять однажды запрограммированную последовательность действий
над заранее определенными данными, но и способны сами анализировать вновь
поступающую информацию, находить в ней закономерности, производить
прогнозирование и т.д. В этой области приложений самым лучшим образом
зарекомендовали себя так называемые нейронные сети – самообучающиеся
системы, имитирующие деятельность человеческого мозга. Рассмотрим подробнее
структуру искусственных нейронных сетей (НС) и их применение в конкретных
задачах.
Искусственный нейрон.
Несмотря на большое разнообразие вариантов нейронных сетей все они имеют
общие черты. Так все они, также как и мозг человека, состоят из большого
числа однотипных элементов – нейронов, которые имитируют нейроны головного
мозга, связанных между собой. На рис.1 показана схема нейрона
[pic]
Из рисунка видно, что искусственный нейрон, так же как и живой, состоит
из синапсов, связывающих входы нейрона с ядром, ядра нейрона, которое
осуществляет обработку входных сигналов и аксона, который связывает нейрон
с нейронами следующего слоя. Каждый синапс имеет вес, который определяет
насколько соответствующий вход нейрона влияет на его состояние. Состояние
нейрона определяется по формуле
[pic] (1)
где
n - число входов нейрона
xi – значение i-го входа нейрона
wi – вес i-го синапса
Затем определяется значение аксона нейрона по формуле
Y = f(S) (2)
Где f - некоторая функция ,которая называется активационной. Наиболее
часто в качестве активационной функции используется так называемый сигмоид,
который имеет следующий вид:
[pic] (3)
Основное достоинство этой функции в том, что она дифференцируема на всей
оси абсцисс и имеет очень простую производную:
[pic] (4)
При уменьшении параметра ? сигмоид становится более пологим, вырождаясь
в горизонтальную линию на уровне 0,5 при ?=0. При увеличении ? сигмоид все
больше приближается к функции единичного скачка.
Нейронные сети обратного распространения.
Нейронные сети обратного распространения – это мощнейший инструмент
поиска закономерностей, прогнозирования, качественного анализа. Такое
название – сети обратного распространения (back propagation) они получили
из-за используемого алгоритма обучения, в котором ошибка распространяется
от выходного слоя к входному, т.е. в направлении, противоположном
направлению распространения сигнала при нормальном функционировании сети.
Нейронная сеть обратного распространения состоит из нескольких слоев
нейронов, причем каждый нейрон слоя i связан с каждым нейроном слоя i+1,
т.е. речь идет о полносвязной НС.
В общем случае задача обучения НС сводится к нахождению некой
функциональной зависимости Y=F(X) где X-вектор входной, а Y -выходной
векторы. В общем случае такая задача, при ограниченном наборе входных
данных имеет бесконечное множество решений. Для ограничения пространства
поиска при обучении ставится задача минимизации целевой функции ошибки НС,
которая находится по методу наименьших квадратов:
[pic] (5)
где
yj – значение j-го выхода нейросети
dj- целевое значение j-го выхода
p – число нейронов в выходном слое
Обучение нейросети производится методом градиентного спуска, т.е. на
каждой итерации изменение веса производится по формуле
[pic] (6)
где ?- параметр определяющий скорость обучения
[pic] (7)
где
yj- значение выхода j-го нейрона
Sj – взвешенная сумма входных сигналов, определяемая по формуле (1). При
этом множитель
[pic] (8)
где xi – значение i-го входа нейрона
Далее рассмотрим определение первого множителя формулы (7)
[pic] (9)
где k – число нейронов в слое n+1.
Введем вспомогательную переменную
[pic] (10)
Тогда мы сможем определит рекурсивную формулу для определения [pic] n-
ного слоя если нам известно [pic] следующего n+1-го слоя.
[pic] (11)
Нахождение же [pic] для последнего слоя НС не представляет трудности,
так как нам известен целевой вектор, т.е. вектор тех значений, которые
должна выдавать НС при данном наборе входных значений.
[pic] (12)
И наконец запишем формулу (6) в раскрытом виде
[pic] (13)
Рассмотрим теперь полный алгоритм обучения нейросети
1. подать на вход НС один из требуемых образов и определить значения
выходов нейронов нейросети
2. рассчитать [pic] для выходного слоя НС по формуле (12) и рассчитать
изменения весов [pic] выходного слоя N по формуле (13)
3. Рассчитать по формулам (11) и (13) соответственно [pic] и [pic] для
остальных слоев НС, n=N-1..1
4. Скорректировать все веса НС
[pic] (14)
5. Если ошибка существенна, то перейти на шаг 1
На этапе 2 сети поочередно в случайном порядке предъявляются вектора из
обучающей последовательности.
Повышение эффективности обучения НС обратного распространения
Простейший метод градиентного спуска, рассмотренный выше, очень
неэффективен в случае, когда производные по различным весам сильно
отличаются. Это соответствует ситуации, когда значение функции S для
некоторых нейронов близка по модулю к 1 или когда модуль некоторых весов
много больше 1. В этом случае для плавного уменьшения ошибки надо выбирать
очень маленькую скорость обучения, но при этом обучение может занять
непозволительно много времени.
Простейшим методом усовершенствования градиентного спуска является
введение момента ? ,когда влияние градиента на изменение весов изменяется
со временем. Тогда формула (13) примет вид
[pic] (13.1)
Дополнительным преимуществом от введения момента является способность
алгоритма преодолевать мелкие локальные минимумы.
Представление входных данных
Основное отличие НС в том, что в них все входные и выходные параметры
представлены в виде чисел с плавающей точкой обычно в диапазоне [0..1]. В
тоже время данные предметной области часто имеют другое кодирование. Так
это могут быть числа в произвольном диапазоне, даты, символьные строки.
Таким образом данные о проблеме могут быть как количественными так и
качественными. Рассмотрим сначала преобразование качественных данных в
числовые, а затем рассмотрим способ преобразования входных данных в
требуемый диапазон.
Качественные данные мы можем разделить на две группы: упорядоченные
(ординальные) и неупорядоченные. Для рассмотрения способов кодирования этих
данных мы рассмотрим задачу о прогнозировании успешности лечения какого-
либо заболевания. Примером упорядоченных данных могут например являться
данные, например, о дополнительных факторах риска при данном заболевании.
|Нет |Ожирение |Алкоголь |Курение |Гипертония |
А также возможным примером может быть например возраст больного
|До 25 лет |25-39 лет |40-49 лет |50-59 лет |60 и старше |
Опасность каждого фактора возрастает в таблицах при движении слева
направо.
В первом случае мы видим, что у больного может быть несколько факторов
риска одновременно. В таком случае нам необходимо использовать такое
кодирование, при котором отсутствует ситуация, когда разным комбинациям
факторов соответствует одно и то же значение. Наиболее распространен способ
кодирования, когда каждому фактору ставится в соответствие разряд двоичного
числа. 1 в этом разряде говорит о наличии фактора, а 0 о его отсутствии.
Параметру нет можно поставить в соответствии число 0. Таким образом для
представления всех факторов достаточно 4-х разрядного двоичного числа.
Таким образом число 10102 = 1010 означает наличие у больного гипертонии и
употребления алкоголя, а числу 00002 соответствует отсутствие у больного
факторов риска. Таким образом факторы риска будут представлены числами в
диапазоне [0..15].
Во втором случае мы также можем кодировать все значения двоичными
весами, но это будет нецелесообразно, т.к. набор возможных значений будет
слишком неравномерным. В этом случае более правильным будет установка в
соответствие каждому значению своего веса, отличающегося на 1 от веса
соседнего значения. Так число 3 будет соответствовать возрасту 50-59лет.
Таким образом возраст будет закодирован числами в диапазоне [0..4].
В принципе аналогично можно поступать и для неупорядоченных данных,
поставив в соответствие каждому значению какое-либо число. Однако это
вводит нежелательную упорядоченность, которая может исказить данные, и
сильно затруднить процесс обучения. В качестве одного из способов решения
этой проблемы можно предложить поставить в соответствие каждому значению
одного из входов НС. В этом случае при наличии этого значения
соответствующий ему вход устанавливается в 1 или в 0 при противном случае.
К сожалению данный способ не является панацеей, ибо при большом количестве
вариантов входного значения число входов НС разрастается до огромного
количества. Это резко увеличит затраты времени на обучение. В качестве
варианта обхода этой проблемы можно использовать несколько другое решение.
В соответствие каждому значению входного параметра ставится бинарный
вектор, каждый разряд которого соответствует отдельному входу НС. Например
если число возможных значений параметра 128, то можно использовать 7
разрядный вектор. Тогда 1 значению будет соответствовать вектор 0000000 а
128 - вектор 1111111, а ,например, 26 значению – 0011011. Тогда число
требуемых для кодирования параметров входов можно определить как
N=log2n (15)
Где
n- количество значений параметра
N- количество входов
Преобразование числовых входных данных
Для НС необходимо чтобы входные данные лежали в диапазоне [0..1], в то
время как данные проблемной области могут лежать в любом диапазоне.
Предположим что данные по одному из параметров лежат в диапазоне
[Min..Max]. Тогда паиболее простым способом нормирования будет
[pic] (16)
где x- исходное значение параметра
[pic]-значение, подаваемое на вход НС
К сожалению этот способ кодирования не лишен недостатков. Так в случае
если [pic] то распределение данных на входе может принять вид
[pic]
Т.е. распределение входных параметров будет крайне неравномерным, что
приведет к ухудшению качества обучения. Поэтому в подобных ситуациях , а
также в случае, когда значение входа лежит в диапазоне [pic] можно
использовать нормировку с помощью функции вида
[pic] (17)
-----------------------
Рис.1 Схема нейрона
Реферат на тему: Математическое программирование
Математическое программирование
1. Общая задача линейного программирования (ЗЛП):
[pic]
Здесь (1) называется системой ограничений , ее матрица имеет ранг r ( n,
(2) - функцией цели (целевой функцией). Неотрицательное решение (х10, x20,
... , xn0) системы (1) называется допустимым решением (планом) ЗЛП.
Допустимое решение называется оптимальным, если оно обращает целевую
функцию (2) в min или max (оптимум).
2. Симплексная форма ЗЛП. Для решения ЗЛП симплекс - методом необходимо ее
привести к определенной (симплексной) форме:
[pic](2`) f+cr+1xr+1 + ... + csxs + ... + cnxn = b0 ( min
Здесь считаем r < n (система имеет бесчисленное множество решений), случай
r = n неинтересен: в этом случае система имеет единственное решение и если
оно допустимое, то автоматически становится оптимальным.
В системе (1`) неизвестные х1, х2, ... , хr называются базисными
(каждое из них входит в одно и только одно уравнение с коэффициентом +1),
остальные хr+1, ... , xn - свободными. Допустимое решение (1`) называется
базисным (опорным планом), если все свободные неизвестные равны 0, а
соответствующее ему значение целевой функции f(x10, ... , xr0,0, ... ,0)
называется базисным.
В силу важности особенностей симплексной формы выразим их и словами:
а) система (1`) удовлетворяет условиям :
1) все ограничения - в виде уравнений;
2) все свободные члены неотрицательны, т.е. bi ( 0;
3) имеет базисные неизвестные;
б) целевая функция (2`) удовлетворяет условиям :
1) содержит только свободные неизвестные;
2) все члены перенесены влево, кроме свободного члена b0;
3) обязательна минимизация (случай max сводится к min по формуле max
f = - min(-f)).
3) Матричная форма симплекс-метода. Симплексной форме ЗЛП соответствует
симплекс - матрица :
1 0 ... 0 ... 0 a1,r+1 ... a1s ... a1n b1
0 1 ... 0 ... 0 a2,r+1 ... a2s ... a2n b2
.................................................................
0 0 ... 1 ... 0 ai,r+1 ... ais ... ain bi
.................................................................
0 0 ... 0 ... 1 ar,r+1 ... ars ... arn br
0 0 ... 0 ... 0 cr+1 ... cs ... cn b0
Заметим, что каждому базису (системе базисных неизвестных )
соответствует своя симплекс - матрица , базисное решение х =
(b1,b2, ... ,br, 0, ... ,0) и базисное значение целевой функции f(b1,b2,
... ,br, 0, ... ,0) = b0 (см. Последний столбец !).
Критерий оптимальности плана . Если в последней (целевой) строке симплекс-
матрицы все элементы неположительны, без учета последнего b0, то
соответствующий этой матрице план оптимален,
т.е. сj ( 0 (j = r+1, n) => min f (b1, ... ,b2,0, ... ,0) = b0.
Критерий отсутствия оптимальности. Если в симплекс-матрице имеется столбец
(S-й), в котором последний элемент сs > 0, a все остальные элементы
неположительны, то ЗЛП не имеет оптимального плана, т.е. сs > 0, ais ( 0
( i= 1,r ) => min f = -(.
Если в симплекс-матрице не выполняются оба критерия, то в поисках оптимума
надо переходить к следующей матрице с помощью некоторого элемента ais > 0 и
следующих преобразований (симплексных):
1) все элементы i-й строки делим на элемент a+is;
2) все элементы S-го столбца, кроме ais=1, заменяем нулями;
3) все остальные элементы матрицы преобразуем по правилу прямоугольника,
что схематично показано на фрагменте матрицы и дано в формулах:
[pic]
akl` = akbais - ailaks = akl - ailaks;
ais ais
bk` = bkais - biaks; cl` = clais - csail
ais ais
Определение. Элемент ais+ называется разрешающим, если преобразование
матрицы с его помощью обеспечивает уменьшение (невозрастание) значения,
целевой функции; строка и столбец, на пересечении которых находится
разрешающий элемент, также называются разрешающими.
Критерий выбора разрешающего элемента. Если элемент ais+ удовлетворяет
условию
bi = min bk
ais0 aks0+
где s0 - номер выбранного разрешающего столбца, то он является разрешающим.
4. Алгоритм симплекс-метода (по минимизации).
5) систему ограничений и целевую функцию ЗЛП приводим к симплексной форме;
6) составим симплекс-матрицу из коэффициентов системы и целевой функции в
симплексной форме;
7) проверка матрицы на выполнение критерия оптимальности; если он
выполняется, то решение закончено;
8) при невыполнении критерия оптимальности проверяем выполнение критерия
отсутствия оптимальности; в случае выполнения последнего решение
закончено - нет оптимального плана;
9) в случае невыполнения обоих критериев находим разрешающий элемент для
перехода к следующей матрице, для чего :
а) выбираем разрешающий столбец по наибольшему из положи
тельных элементов целевой
строки;
б) выбираем разрешающую строку по критерию выбора разрешающего
элемента; на их пересечении находится разрешающий элемент;
6) c помощью разрешающего элемента и симплекс-преобразований переходим к
следующей матрице;
7) вновь полученную симплекс-матрицу проверяем описанным выше способом (см.
п. 3)
Через конечное число шагов, как правило получаем оптимальный план ЗЛП или
его отсутствие
Замечания.
1) Если в разрешающей строке (столбце) имеется нуль, то в соответствующем
ему столбце (строке) элементы остаются без изменения при симплекс-
преобразованиях.
2) преобразования - вычисления удобно начинать с целевой строки; если при
этом окажется, что выполняется критерий оптимальности, то можно
ограничиться вычислением элементов последнего столбца.
3) при переходе от одной матрицы к другой свободные члены уравнений
остаются неотрицательными; появление отрицатель
ного члена сигнализирует о допущенной ошибке в предыдущих вычислениях.
4) правильность полученного ответа - оптимального плана - проверяется путем
подстановки значений базисных неизвестных в целевую функцию; ответы
должны совпасть.
5. Геометрическая интерпретация ЗЛП и графический метод решения (при двух
неизвестных)
Система ограничений ЗЛП геометрически представляет собой многоугольник или
многоугольную область как пересечение полуплоскостей - геометрических
образов неравенств системы. Целевая функция f = c1x1 + c2x2 геометрически
изображает семейство параллельных прямых, перпендикулярных вектору n
(с1,с2).
Теорема. При перемещении прямой целевой функции направлении вектора n
значения целевой функции возрастают, в противоположном направлении -
убывают.
На этих утверждениях основан графический метод решения ЗЛП.
6. Алгоритм графического метода решения ЗЛП.
7) В системе координат построить прямые по уравнениям, соответствующим
каждому неравенству системы ограничений;
8) найти полуплоскости решения каждого неравенства системы (обозначить
стрелками);
9) найти многоугольник (многоугольную область) решений системы ограничений
как пересечение полуплоскостей;
10) построить вектор n (с1,с2) по коэффициентам целевой функции f = c1x1 +
c2x2;
11) в семействе параллельных прямых целевой функции выделить одну,
например, через начало координат;
12) перемещать прямую целевой функции параллельно самой себе по области
решения, достигая max f при движении вектора n и min f при движении в
противоположном направлении.
13) найти координаты точек max и min по чертежу и вычислить значения
функции в этих точках (ответы).
Постановка транспортной задачи.
Приведем экономическую формулировку транспортной задачи по критерию
стоимости:
Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2,
..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется
доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn
соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки
(тариф) единицы продукта из Ai в Bj известна для всех маршрутов AiBj и
равна Cij (i=1,m; j=1,n). Требуется составить такой план перевозок, при
котором весь груз из пунктов отправления вывозиться и запросы всех пунктов
потребления удовлетворяются (закрытая модель), а суммарные транспортные
расходы минимальны.
Условия задачи удобно располагать в таблицу, вписывая в клетки количество
перевозимого груза из Ai в Bj груза Xij > 0, а в маленькие клетки -
соответствующие тарифы Cij:
[pic]
Математическая модель транспортной задачи.
Из предыдущей таблицы легко усматривается и составляется математическая
модель транспортной задачи для закрытой модели [pic]
Число r = m + n - 1, равное рангу системы (1), называется рангом
транспортной задачи. Если число заполненных клеток (Xij № 0) в таблице
равно r, то план называется невырожденным, а если это число меньше r, то
план вырожденный - в этом случае в некоторые клетки вписывается столько
нулей (условно заполненные клетки), чтобы общее число заполненных клеток
было равно r.
Случай открытой модели даi № дbj легко сводится к закрытой модели путем
введения фиктивного потребителя Bn+1 c потребностью bn+1=дai-дbj, либо -
фиктивного поставщика Аm+1 c запасом am+1=дbj-дai ; при этом тарифы
фиктивных участников принимаются равными 0.
Способы составления 1-таблицы (опорного плана).
Способ северо-западного угла (диагональный). Сущность способа заключается в
том, что на каждом шаге заполняется левая верхняя клетка (северо-западная)
оставшейся части таблицы, причем максимально возможным числом: либо
полностью вывозиться груз из Аi, либо полностью удовлетворяется потребность
Bj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются
запасы ai и не удовлетворяются потребности bj . В заключение проверяют, что
найденные компоненты плана Xij удовлетворяют горизонтальным и вертикальным
уравнениям и что выполняется условие невырожденности плана.
Способ наименьшего тарифа. Сущность способа в том, что на каждом шаге
заполняется та клетка оставшейся части таблицы, которая имеет наименьший
тариф; в случае наличия нескольких таких равных тарифов заполняется любая
из них. В остальном действуют аналогично предыдущему способу.
Метод потенциалов решения транспортной задачи.
Определение: потенциалами решения называются числа ai®Ai, bj®Bj,
удовлетворяющие условию ai+bj=Cij (*) для всех заполненных клеток (i,j).
Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n
неизвестными, имеющую бесчисленное множество решений; для ее определенности
одному неизвестному придают любое число (обычно a1=0), тогда все остальные
неизвестные определяются однозначно.
Критерий оптимальности. Если известны потенциалы решения X0 транспортной
задачи и для всех незаполненных клеток выполняются условия ai+bj Ј Ci j, то
X0 является оптимальным планом транспортной задачи.
Если план не оптимален, то необходимо перейти к следующему плану (таблице)
так, чтобы транспортные расходы не увеличились.
Определение: циклом пересчета таблицы называется последовательность клеток,
удовлетворяющая условиям:
одна клетка пустая, все остальные занятые;
любые две соседние клетки находятся в одной строке или в одном столбце;
никакие 3 соседние клетки не могут быть в одной строке или в одном столбце
.
Пустой клетке присваивают знак « + », остальным - поочередно знаки « - » и
« + ».
Для перераспределения плана перевозок с помощью цикла перерасчета сначала
находят незаполненную клетку (r, s), в которой ar+bs>Crs, и строят
соответствующий цикл; затем в минусовых клетках находят число X=min{Xij}.
Далее составляют новую таблицу по следующему правилу:
в плюсовые клетки добавляем X;
из минусовых клеток отнимаем Х;
все остальные клетки вне цикла остаются без изменения.
Получим новую таблицу, дающее новое решение X, такое, что f(X1) Ј f(X0);
оно снова проверяется на оптимальность через конечное число шагов
обязательно найдем оптимальный план транспортной задачи, ибо он всегда
существует.
Алгоритм метода потенциалов.
проверяем тип модели транспортной задачи и в случае открытой модели сводим
ее к закрытой;
находим опорный план перевозок путем составления 1-й таблицы одним из
способов - северо-западного угла или наименьшего тарифа;
проверяем план (таблицу) на удовлетворение системе уравнений и на
невыражденность; в случае вырождения плана добавляем условно заполненные
клетки с помощью « 0 »;
проверяем опорный план на оптимальность, для чего:
а) составляем систему уравнений потенциалов по заполненным клеткам;
б) находим одно из ее решений при a1=0;
в) находим суммы ai+bj=Cўij («косвенные тарифы») для всех пустых клеток;
г) сравниваем косвенные тарифы с истинными: если косвенные тарифы не
превосходят соответствующих истинных(Cўij Ј Cij) во всех пустых клетках, то
план оптимален (критерий оптимальности). Решение закончено: ответ дается в
виде плана перевозок последней таблицы и значения min f.
Если критерий оптимальности не выполняется, то переходим к следующему
шагу.
Для перехода к следующей таблице (плану):
а) выбираем одну из пустых клеток, где косвенный тариф больше истинного
(Cўij= ai+bj > Cij );
б) составляем цикл пересчета для этой клетки и расставляем знаки « + », « -
» в вершинах цикла путем их чередования, приписывая пустой клетке « + »;
в) находим число перерасчета по циклу: число X=min{Xij}, где Xij - числа в
заполненных клетках со знаком « - »;
г) составляем новую таблицу, добавляя X в плюсовые клетки и отнимая X из
минусовых клеток цикла
См. п. 3 и т.д.
Через конечное число шагов (циклов) обязательно приходим к ответу, ибо
транспортная задача всегда имеет решение.
| |
