Алгоритм обратного распространения ошибки (Back propagation algorithm). Алгоритм обучения многослойной нейронной сети методом обратного распространения ошибки

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

Обновление правила цепочки

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

F(x)=A(B(C(x)))

A, B, и C — на различных слоях. Пользуясь правилом цепочки, мы легко вычисляем производную f(x) по x:

F′(x)=f′(A)⋅A′(B)⋅B′(C)⋅C′(x)

Что насчёт производной относительно B ? Чтобы найти производную по B , вы можете сделать вид, что B (C(x)) является константой, заменить ее переменной-заполнителем B , и продолжить поиск производной по B стандартно.

F′(B)=f′(A)⋅A′(B)

Этот простой метод распространяется на любую переменную внутри функции, и позволяет нам в точности определить влияние каждой переменной на общий результат.

Применение правила цепочки

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

Учитывая сеть, состоящую из одного нейрона, общая потеря нейросети может быть рассчитана как:

Cost=C(R(Z(XW)))

Используя правило цепочки, мы легко можем найти производную потери относительно веса W.

C′(W)=C′(R)⋅R′(Z)⋅Z′(W)=(y^−y)⋅R′(Z)⋅X

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

Какова производная от потери по Wo ?

C′(WO)=C′(y^)⋅y^′(ZO)⋅Z′O(WO)=(y^−y)⋅R′(ZO)⋅H

А что насчет Wh ? Чтобы узнать это, мы просто продолжаем возвращаться в нашу функцию, рекурсивно применяя правило цепочки, пока не доберемся до функции, которая имеет элемент Wh .

C′(Wh)=C′(y^)⋅O′(Zo)⋅Z′o(H)⋅H′(Zh)⋅Z′h(Wh)=(y^−y)⋅R′(Zo)⋅Wo⋅R′(Zh)⋅X

И просто забавы ради, что, если в нашей сети было бы 10 скрытых слоев. Что такое производная потери для первого веса w1?

C(w1)=(dC/dy^)⋅(dy^/dZ11)⋅(dZ11/dH10)⋅(dH10/dZ10)⋅(dZ10/dH9)⋅(dH9/dZ9)⋅(dZ9/dH8)⋅(dH8/dZ8)⋅(dZ8/dH7)⋅(dH7/dZ7)⋅(dZ7/dH6)⋅(dH6/dZ6)⋅(dZ6/dH5)⋅(dH5/dZ5)⋅(dZ5/dH4)⋅(dH4/dZ4)⋅(dZ4/dH3)⋅(dH3/dZ3)⋅(dZ3/dH2)⋅(dH2/dZ2)⋅(dZ2/dH1)⋅(dH1/dZ1)⋅(dZ1/dW1)

Заметили закономерность? Количество вычислений, необходимых для расчёта производных потерь, увеличивается по мере углубления нашей сети. Также обратите внимание на избыточность в наших расчетах производных . Производная потерь каждого слоя добавляет два новых элемента к элементам, которые уже были вычислены слоями над ним. Что, если бы был какой-то способ сохранить нашу работу и избежать этих повторяющихся вычислений?

Сохранение работы с мемоизацией

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

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

Для начала мы вычисляем ошибку выходного слоя и передаем результат на скрытый слой перед ним. После вычисления ошибки скрытого слоя мы передаем ее значение обратно на предыдущий скрытый слой. И так далее и тому подобное. Возвращаясь назад по сети, мы применяем 3-ю формулу на каждом слое, чтобы вычислить производную потерь по весам этого слоя. Эта производная говорит нам, в каком направлении регулировать наши веса , чтобы уменьшить общие потери.

Примечание: термин ошибка слоя относится к производной потерь по входу в слой. Он отвечает на вопрос: как изменяется выход функции потерь при изменении входа в этот слой?

Ошибка выходного слоя

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

C′(Zo)=(y^−y)⋅R′(Zo)

Чтобы упростить запись, практикующие МО обычно заменяют последовательность (y^−y)∗R"(Zo) термином Eo . Итак, наша формула для ошибки выходного слоя равна:

Eo=(y^−y)⋅R′(Zo)

Ошибка скрытого слоя

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

Eh=Eo⋅Wo⋅R′(Zh)

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

Производная потерь по любому весу

Вернемся к нашей формуле для производной потерь по весу выходного слоя Wo .

C′(WO)=(y^−y)⋅R′(ZO)⋅H

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

C′(Wo)=Eo⋅H

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

C′(w)=CurrentLayerError⋅CurrentLayerInput

Примечание: вход относится к активации с предыдущего слоя, а не к взвешенному входу, Z.

Подводя итог

Вот последние 3 уравнения, которые вместе образуют основу обратного распространения.

Вот процесс, визуализированный с использованием нашего примера нейронной сети выше:

Обратное распространение: пример кода

Многослойная искусственная нейронная сеть (рис. 6) может содержать произвольное количество слоев (K ), каждый слой состоит из нескольких нейронов, число которых также может быть произвольно (Н k – количество нейронов в слое), количество входов n , количество выходов H=H k – числу нейронов в выходном (последнем) слое.

Рис. 6. Многослойная нейронная сеть прямого распространения

Слои между первым и последним называются промежуточными или скрытыми. Веса в такой сети имеют три индекса i -номер нейрона следующего слоя, для которого связь входная, j -номер входа или нейрона текущего слоя, для которого связь выходная, k -номер текущего слоя в нейронной сети (для входов, вектора X, k=0 ).

Многослойные нейронные сети прямого распространения обучаются методом обратного распространения ошибки.

Алгоритм обучения методом обратного распространения ошибки:

1 шаг: инициализация матриц весов случайным образом (в циклах).

2 шаг: предъявление нейронной сети образа (на вход подаются значения из обучающей выборки – вектор Х ) и берется соответствующий выход (вектор D ).

3 шаг (прямой проход): вычисление в циклах выходов всех слоев и получение выходных значений нейронной сети (вектор Y ).

где – выход i -нейрона k -слоя, f – функция активации, – синаптическая связь между j -нейроном слоя k-1 и i-нейроном слоя k , – входное значение.

4 шаг (обратный проход): изменение весов в циклах по формулам:

– для последнего (выходного) слоя,

– для промежуточных слоев,

где t – номер текущей итерации цикла обучения (номер эпохи), – коэффициент обучения задается от 0 до 1, – выход i -го нейрона k -го слоя,

– синаптическая связь между j- нейроном слоя k- 1 и i -нейроном слоя k , d i – желаемое выходное значение на i -нейроне, y i – реальное значение на i -нейроне выходного слоя.

5 шаг: проверка условия продолжения обучения (вычисление значения ошибки и/или проверка заданного количества итераций). Если обучение не завершено, то 2 шаг, иначе заканчиваем обучение. Среднеквадратичная ошибка вычисляется следующим образом:

где Q – общее число примеров, H - количество нейронов в выходном слое, d i – желаемое выходное значение на i-нейроне, y i - реальное значение на i -нейроне выходного слоя.

Пример решения задачи

Задача . Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется сигмоидальная функция активации (k=0,9), а во втором – 1, линейная (l=0,7) функция. В качестве обучающей выборки использовать таблицу истинности для операции «штрих Шеффера»

Описание процесса решения. Для обучения нейронной сети методом обратного распространения ошибки необходимо:

1) Графически отобразить структуру нейронной сети. Определить размерность и количество матриц синаптических весов (для каждого слоя своя матрица).

2) Определить обучающую выборку, представив ее в табличном виде.

3) Выбрать входные данные, на которых будет рассматриваться итерация цикла обучения.

4) Следуя алгоритмы обучения методом обратного обучения ошибки просчитать одну итерацию цикла и представить новые синаптические веса в матричном виде.

Решение.

1) По заданию нейронная сеть состоит из трех нейронов, два входных, один выходной, значит синаптических весов 6. Первый слой нейронов имеет сигмоидальную функцию активации, второй – линейная.

2) По заданию нейронная сеть бинарная, поэтому на ее входы могут подаваться только нули и единицы, так как входа 2, то возможных комбинаций входных значений будет 4 (обучающая выборка будет состоять из 4 векторов). Выход нейронной сети согласно заданию соответствует оператору «штрих Шеффера». Поэтому таблица с обучающей выборкой будет выглядеть следующим образом:

2 шаг: вектор X={0,1}, D ={1}.

3 шаг (прямой проход): вычисление в циклах выходов всех слоев и получение выходных значений нейронной сети (вектор Y).

4 шаг (обратный проход): изменение весов:

5 шаг:

Так как мы рассматриваем одну итерацию цикла обучения, в любом случае выходим из цикла.

Задачи

1. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – пороговая (T=0,6) функция. В качестве обучающей выборки использовать таблицу истинности для операции «исключающее или» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

2. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – сигмоидальная (k=1) функция. В качестве обучающей выборки использовать таблицу истинности для операции импликации (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

3. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – линейная (k=0,6) функция. В качестве обучающей выборки использовать таблицу истинности для операции «штрих Шеффера» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

4. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – гиперболический тангенс (k=1). В качестве обучающей выборки использовать таблицу истинности для операции «стрелка Пирса» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

5. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется сигмоидальная функция активации (k=0,9), а во втором – 1, пороговая (T=0,7). В качестве обучающей выборки использовать таблицу истинности для операции «исключающее или» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

6. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется линейная функция активации (k=0,5), а во втором – 1, сигмоидальная (k=0,7) функция. В качестве обучающей выборки использовать таблицу истинности для операции импликации (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

7. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,4), а во втором – 1, линейная (k=0,6) функция. В качестве обучающей выборки использовать таблицу истинности для операции «штрих Шеффера» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

8. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,6), а во втором –1, гиперболический тангенс (k =2). В качестве обучающей выборки использовать таблицу истинности для операции «стрелка Пирса» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

9. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – линейная (k=0,6) функция.

10. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – сигмоидальная (k=1) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

11. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – пороговая (T=0,65) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

12. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – гиперболический тангенс (k=3) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

13. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется сигмоидальная функция активации (k=0,9), во втором – 2, пороговая (T=0,7).

Синаптические веса и обучающую выборку задать случайным образом (не нули).

14. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется линейная функция активации (k=0,5), во втором – 2, сигмоидальная (k=0,7) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

15. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,4), во втором – 2, линейная (k=0,6) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

16. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,6), во втором – 1, гиперболический тангенс (k=2).

Синаптические веса и обучающую выборку задать случайным образом (не нули).

17. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 3 слоёв, использующей пороговую функцию активации (T=0,5), в первом слое 2 нейрона, во втором – 2, в третьем - 1.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

18. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, использующей пороговую функцию активации (T=0,5), в первом слое 3 нейрона, во втором – 1. В качестве обучающей выборки использовать таблицу истинности для (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

19. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, использующей сигмоидальную функцию активации (k=0,5), в первом слое 3 нейрона, во втором –1. В качестве обучающей выборки использовать таблицу истинности для (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

20. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 3 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,6), во втором –2, гиперболический тангенс (k=2), в третьем 1, линейная (k=0,7).

Синаптические веса и обучающую выборку задать случайным образом (не нули).

Лабораторная работа № 6
Генетический алгоритм

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

Для моделирования эволюционных процессов в генетическом алгоритме используются операторы (таблица 10) и стратегии отбора (таблица 11).

Таблица 10.

Основные виды операторов генетических алгоритмов.

Таблица 11.

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

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

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

1 шаг . Формирование начальной популяции.

2 шаг . Оценка особей популяции (используется фитнесс-функция).

3 шаг . Отбор (используется один из методов отбора).

4 шаг . Скрещивание (используется оператор кроссовера).

5 шаг . Мутация (используется один или несколько операторов мутации).

6 шаг . Формирование новой популяции.

7 шаг . Если популяция не сошлась, то 2, иначе – останов (прекращение функционирования генетического алгоритма).

Пример решения задачи

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

фитнесс-функция – сумма всех бит, деленная на среднее значение суммы бит особей популяции; метод отбора – рулетка с принципом элитизма; оператор скрещивания – двухточечный кроссовер; оператор мутации – одиночная мутация.

Описание процесса решения .

Для использования генетического алгоритма необходимо:

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

2) Использовать последовательность шагов генетического алгоритма с соответствующими операторами.

Решение.

1) Фенотип (задаем десятичные значения случайным образом):

2) 1 шаг. Формирование начальной популяции.

Определено пять признаков, пусть особь содержит любые 2 из них (два первых – значения первого критерия, три последних второго), случайным образом сгенерируем 10 особей, каждая особь длиной 8 бит:

Особь 1: 00111110 Особь 6: 00111110

Особь 2: 11001110 Особь 7: 11000111

Особь 3: 00111001 Особь 8: 00110111

Особь 4: 11001001 Особь 9: 10101010

Особь 5: 00110111 Особь 10: 01010101

2 шаг. Оценка особей популяции (используется фитнесс-функция равная сумме бит в особи).

Среднее значение суммы бит в популяции = 3,6.

3 шаг. Отбор (используется метод отбора – рулетка с принципом элитизма).

Строим рулетку (сектора пропорциональны приспособленности, рис.

7) и запускаем ее 8 раз (выбираем 4 пары, рис. 9):

Рис. 7. Рулетка для задачи генетического алгоритма

Запуски рулетки (случайным образом):

Рис. 8. Запуски рулетка для задачи генетического алгоритма

Таким образом, образовались следующие пары: 1 и 5, 7 и 5, 10 и 2, 8 и 6.

4 шаг. Скрещивание (используется оператор – двухточечный кроссовер).

Выбираем две точки разрыва (случайным образом, но числа должны различаться хотя бы на 2 и не быть равными 1 или длине особи): 2 и 5 и применяем оператор к выбранным парам особей:

Особь 1: 00|111|110 Особь 2.1: 00|110|110

Особь 5: 00|110|111 Особь 2.2: 00|111|111

Особь 7: 11|000|111 Особь 2.3: 11|110|111

Особь 5: 00|110|111 Особь 2.4: 00|000|111

Особь 10: 01|010|101 Особь 2.5: 01|001|101

Особь 2: 11|001|110 Особь 2.6: 11|010|110

Особь 6: 00|111|110 Особь 2.7: 00|110|110

Особь 8: 00|110|111 Особь 2.8: 00|111|111

5 шаг. Мутация (используется оператор – одноточечная мутация).

Определим вероятность мутации 30 % и бит – третий, подвергающийся мутации.

1-8 – наследники, 9-11 – матировавшие особи, 12 - сохраняем одну особь с максимальной приспособленностью – принцип элитизма.

7 шаг. Популяция достаточно разнообразна – нет признаков сходимости. Так как рассматривается лишь одна эпоха генетического алгоритма – выход из алгоритма.

Задачи

1. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на максимум суммы всех бит среди особей популяции; метод отбора – рулетка; оператор скрещивания – одноточечный кроссовер; оператор мутации – одиночная мутация.

2. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на минимум суммы всех бит среди особей популяции; метод отбора – турнирный отбор; оператор скрещивания – двухточечный кроссовер; оператор мутации – транслокация.

3. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на минимум суммы всех бит среди особей популяции; метод отбора – ранговый отбор; оператор скрещивания – равномерный кроссовер; оператор мутации – инверсия.

4. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, умноженная на минимум суммы всех бит среди особей популяции; метод отбора – отбор усечением; оператор скрещивания – равномерный кроссовер; оператор мутации – одноточечная мутация.

5. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на максимум суммы всех бит в особи в популяции; метод отбора – пропорциональный отбор; оператор скрещивания – одноточечный кроссовер; оператор мутации – инверсия.

6. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на количество бит в особи; метод отбора – рулетка с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – инверсия.

7. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество бит в особи; метод отбора – пропорциональный с использованием принципа элитизма; оператор скрещивания – одноточечный кроссовер; оператор мутации – одноточечная мутация.

8. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – ранговый с использованием принципа элитизма; оператор скрещивания – одноточечный кроссовер; оператор мутации – одноточечная мутация.

9. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – турнирный с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – транслокация.

10. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – отбор усечением с использованием принципа элитизма; оператор скрещивания – двухточечный кроссовер; оператор мутации – транслокация.

11. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на максимум суммы всех бит особи в популяции; метод отбора – рулетка; оператор скрещивания – двухточечный кроссовер; оператор мутации – одиночная мутация.

12. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на максимум суммы всех бит особи в популяции; метод отбора – турнирный отбор; оператор скрещивания – равномерный кроссовер; оператор мутации – инверсия.

13. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на минимум суммы всех бит особи в популяции; метод отбора – ранговый отбор; оператор скрещивания – одноточечный кроссовер; оператор мутации – инверсия.

14. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, умноженная на минимум суммы всех бит особи в популяции; метод отбора – отбор усечением; оператор скрещивания – равномерный кроссовер; оператор мутации – транслокация.

15. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на максимум суммы всех бит среди особей популяции; метод отбора – пропорциональный отбор; оператор скрещивания – одноточечный кроссовер; оператор мутации – транслокация.

16. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество бит в особи; метод отбора – рулетка с использованием принципа элитизма; оператор скрещивания – одноточечный кроссовер; оператор мутации – транслокация.

17. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество бит в особи; метод отбора – пропорциональный с использованием принципа элитизма; оператор скрещивания – двухточечный кроссовер; оператор мутации – инверсия.

18. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – ранговый с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – транслокация.

19. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – турнирный с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – одноточечная мутация.

20. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – отбор усечением с использованием принципа элитизма; оператор скрещивания – двухточечный кроссовер; оператор мутации – одноточечная мутация.

Лабораторная работа №7.
Разработка специальных моделей представления знаний
для БЗ и БД и правил для машины вывода

Порядок работ и их виды

Введение с указанием предметной области.

В разделе “I. Идентификация ” постановка (формулировка) проблемы, цели и задачи.

В разделе “II.. Концептуализация ” нужно представить следующие результаты разработки Содержательной и Концептуальной моделей.

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

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

Алгоритм обратного распространения ошибки (АОРО), являющийся обобщением дельта – правила, позволяет обучать ИНС ПР с любым количеством слоев. Можно сказать, что АОРО фактически использует разновидность градиентного спуска, перестраивая веса в направлении минимума ошибки.

При использовании АОРО предполагается, что в качестве активационной используется сигмоидная функция. Эта функция позволяет экономить вычислительные затраты, поскольку имеет простую производную:

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

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

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

1) Выбирается обучающая пара (X , Z* ), X подается на вход;

2) Вычисляется выходсети Z = F (Y );

3) Рассчитывается ошибка выхода E ;

4) Веса сети корректируются с целью минимизации ошибки;

Шаги 1 и 2 - это прямое распространение по сети, а 3 и 4 - обратное.

Перед обучением необходимо разбить имеющиеся пары «вход – выход» на две части: обучающие и тестовые.

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

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

1. Тестовые данные сильно отличаются от обучающих, т.е. обучающие пары охватывали не все области входного пространства.

2. Возникло явление «переобучения» (overfitting ), когда поведение НС оказывается более сложным, чем решаемая задача.

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

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

Описание алгоритма

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

Нелинейность такого вида удобна простотой расчета производной:

Для обучения сети используется P пар векторов сигналов: входной вектор I и вектор, который должен быть получен на выходе сети D. Сеть, в простом случае, состоит из N слоев, причем каждый нейрон последующего слоя связан со всеми нейронами предыдущего слоя связями, с весами w [n].

При прямом распространении, для каждого слоя рассчитывается (и запоминается) суммарный сигнал на выходе слоя (S [n]) и сигнал на выходе нейрона. Так, сигнал на входе i-го нейрона n-го слоя:

Здесь w (i,j) - веса связей n-го слоя. Сигнал на выходе нейрона рассчитывается применением к суммарному сигналу нелинейности нейрона.

Сигнал выходного слоя x [N] считается выходным сигналом сети O.

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

Для обучения сети используется градиент функции ошибки по весам сети. Алгоритм обратного распространения предполагает расчет градиента функции ошибки "обратным распространением сигнала" ошибки. Тогда частная производная ошибки по весам связей рассчитывается по формуле:

Здесь д - невязка сети, которая для выходного слоя рассчитывается по функции ошибки:

А для скрытых слоев - по невязке предыдущего слоя:

Для случая сигмоидной нелинейности и среднего квадрата отклонения как функции ошибки:

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

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

Реализация алгоритма обратного распространения ошибки на примере аппроксимации функции

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

В среде Matlab необходимо построить и обучить нейронную сеть для аппроксимации таблично заданной функции, i=1, 20. Разработать программу, которая реализует нейросетевой алгоритм аппроксимации и выводит результаты аппроксимации в виде графиков.

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

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

Задача. В среде Matlab необходимо построить и обучить нейронную сеть для аппроксимации таблично заданной функции (см. рисунок 5).

Рисунок 5. Таблица значений функции В математической среде Matlab в командном окне записываем код программы создания и обучения нейронной сети.

Для решения воспользуемся функцией newff (.) - создание "классической" многослойной НС с обучением по методу обратного распространения ошибки, т.е. изменение весов синапсов происходит с учетом функции ошибки, разница между реальными и правильными ответами нейронной сети, определяемыми на выходном слое, распространяется в обратном направлении - навстречу потоку сигналов. Сеть будет иметь два скрытых слоя. В первом слое 5 нейронов, во втором - 1. Функция активации первого слоя - "tansig" (сигмоидная функция, возвращает выходные векторы со значениями в диапазоне от - 1 до 1), второго - "purelin" (линейная функция активации, возвращает выходные векторы без изменений). Будет проведено 100 эпох обучения. Обучающая функция "trainlm" - функция, тренирующая сеть (используется по умолчанию, поскольку она обеспечивает наиболее быстрое обучение, но требует много памяти) .

Код программы:

P = zeros (1, 20);

for i = 1: 20 %создание массива P (i) = i*0.1; %входные данные (аргумент) end T= ; %входные данные (значение функции) net = newff ([-1 2.09], ,{"tansig" "purelin"}); %создание нейронной сети net. trainParam. epochs = 100; %задание числа эпох обучения net=train (net,P,T); %обучение сети y = sim (net,P); %опрос обученной сети figure (1);

plot (P,T,P,y,"o"),grid; %прорисовка графика исходных данных и функции, сформированной нейронной сетью.

Результат работы нейронной сети.

Результат обучения (см. рис.2): график показывает время обучения нейронной сети и ошибку обучения. В этом примере нейронная сеть прошла все 100 эпох постепенно обучаясь и уменьшая ошибки, дошла до 10 -2,35 (0,00455531).

Рисунок 2. Результат обучения нейронной сети

График исходных данных и функции, сформированной нейронной сетью (см. рис.3): кружками обозначены исходные данные, а линия - функция, сформированная нейронной сетью. Далее по полученным точкам можно построить регрессию и получить уравнение аппроксимации (см. рисунок 8). Мы использовали кубическую регрессию, так как ее график наиболее точно проходит через полученные точки. Полученное уравнение имеет вид:

y=0.049x 3 +0.88x 2 -0.006x+2.1.

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

Рисунок 3. График исходных данных и функции, сформированной нейронной сетью

Рисунок 4. График функции аппроксимации

Алгоритм обратного распространения ошибки (Back propagation algorithm)

Синонимы: Алгоритм BackProp, Алгоритм Back Propagation, BackProp

Loginom: Нейросеть (классификация) (обработчик), Нейросеть (регрессия) (обработчик)

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

В основе идеи алгоритма лежит использование выходной ошибки нейронной сети:

для вычисления величин коррекции весов нейронов в её скрытых слоях, где - число выходных нейронов сети, - целевое значение, - фактическое выходное значение. Алгоритм является итеративным и использует принцип обучения «по шагам» (обучение в режиме on-line), когда веса нейронов сети корректируются после подачи на её вход одного обучающего примера.

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

где - вес i-й связи j-го нейрона, - параметр скорости обучения, который позволяет дополнительно управлять величиной шага коррекции с целью более точной настройки на минимум ошибки и подбирается экспериментально в процессе обучения (изменяется в интервале от 0 до 1).

Учитывая, что выходная сумма j-го нейрона равна

можно показать, что

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

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

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

В настоящее время разработано множество модификаций алгоритма обратного распространения. Например, используется обучение не «по шагам», когда выходная ошибка вычисляется, а веса корректируются на каждом примере, а «по эпохам» в режиме off-line , когда изменение весов производится после подачи на вход сети всех примеров обучающего множества, а ошибка усредняется по всем примерам.

Обучение «по эпохам» является более устойчивым к выбросам и аномальным значениям целевой переменной за счёт усреднения ошибки по многим примерам. Но при этом повышается вероятность «застревания» алгоритма в локальных минимумах. Вероятность этого для обучения «по шагам» меньше, поскольку использование отдельных примеров создаёт «шум», который «выталкивает» алгоритм из ям градиентного рельефа.

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

• неопределённо долгий процесс обучения:
• возможность «паралича сети», когда при больших значениях рабочая точка активационной функции оказывается в области насыщения сигмоиды и производная в выражении (1) становится близкой к 0, а коррекции весов практически не происходит и процесс обучения «замирает»;
• уязвимость алгоритма к попаданию в локальные минимумы функции ошибки.

Впервые алгоритм был описан в 1974 г.