Лекции по системам искуственного интеллекта (V1.1)
Подождите немного. Документ загружается.
Лекция № 5
Распознавание образов с помощью нейронных сетей
1. Описание задачи и практические приложения задачи
распознавания образов.
Многие существующие задачи можно интерпретировать как задачи
распознавания (классификации). Например, имеется немало вариантов
изображения цифры 1, но все эти изображения должны принадлежать к
одному классу – классу «1»; распознавание слов в звуковой записи,
воспроизводимой динамиком магнитофона – тоже пример распознавания
(классификации).
Когда мы знаем, к какому классу относится каждый из учебных
примеров, можно использовать управляемое обучение. Задачей для сети
является ее обучение тому, как сопоставить предъявляемый образец с
контрольным целевым образцом, представляющим нужный класс. Например,
сети можно предъявить изображений цифры 1 и обучить сеть тому, что при
этом соответствующий 1 выходной элемент должен быть включен. А
выходные элементы, соответствующие другим цифрам - выключены. В этом
случае входной образец может быть набором значений. Характеризующих
пиксели изображения в оттенках серого, а целевой выходной образец –
вектором, значения всех координат которого должны быть равными 0, за
исключением координаты, соответствующей выходному элементу,
представляющему 1.
Чтобы понять каким образом работает НС при решении задачи
распознавания, рассмотрим тривиальную задачу и используем для решения
этой задачи самый простой тип сети.
Задача состоит в выработке правил классификации самолетов для
бомбардировщиков и истребителей в зависимости от их максимальной
скорости и максимального взлетного веса (рис. 1). Такие правила могут быть
заданы формально:
ЕСЛИ вес>0.80 И скорость < 0.55, ТО бомбардировщик,
ЕСЛИ вес<0.90 И скорость > 0.25, ТО истребитель,
Разделение, порожденное этими правилами, вполне успешно
классифицирует самолеты, но оказывается не слишком гибким, если по этим
правилам придется классифицировать новый самолет.
Рис. 1.
Кроме того, эти правила в указанном виде ничего не сообщают о том,
насколько точной будет классификация нового самолета.
Альтернативный подход к использованию правил заключается в
выводе функции классификации путем построения прямой, разделяющей два
класса. Для нового самолета нам нужно просто указать точку на плоскости,
соответствующую известным значениям максимальной скорости и
максимального взлета и посмотреть, по какую сторону от прямой будет
расположена эта точка. В данном случае для небольшого числа самолетов
рассмотрены два признака, скорость и вес, поэтому можно представить
данные в виде изображения на плоскости. Однако если придется иметь дело с
сотнями самолетов и значительно большим числом признаков, задачу
классификации в виде простой картинки представить будет невозможно.
- бомбардировщик
- истребитель
3
2.5
2
1.5
1
0.5
0 0.2 0.4 0.6 0.8 1
Выход заключается в использовании функции выбора решения.
Уравнение прямой, разделяющей два типа самолетов, записывается в
следующем виде:
х
2
=1.5х
1
+0.5
где х
1
представляет скорость, а х
2
– вес. Это уравнение можно
использовать для создания функции выбора решения:
5.0x5.1x)x,x(f
1221
+
+
−
=
⎩
⎨
⎧
<
≥
=
0)x,x(fесли,вщикбомбардиро
0)x,x(fесли,ьистребител
d
21
21
Например, истребитель, представленный точкой (0.4, 0.5), даст
6
.05.04.05.15.0
)
5.0,4.0
(
f
=
+
×
+
−
=
и функция выбора решения правильно классифицирует эту точку, как
истребитель.
Предлагаемую функцию выбора решения можно моделировать с
помощью нейронной сети и реализовать в виде аппаратных средств
2. Проблема разделения классов (проблема «исключающего ИЛИ»)
Для задачи классификации, например, выяснения типа самолетов, если
прямая (для размерности два) или гиперплоскость (для размерности n) может
разделить все образцы на соответствующие им классы, то проблема является
линейной. Если же для решения проблемы разделения классов требуется
несколько прямых или гиперплоскостей, то проблема называется
нелинейной. Широко известным примером нелинейной проблемы является
проблема моделирования отношения XOR. Определение отношения XOR
приведено в таблице 1.
Таблица 1.
х у z
1 1 0
1 0 1
0 1 1
0 0 0
Проблема XOR таким образом является нелинейной, и для ее решения
с помощью НС имеется две возможности: либо использовать сеть, которая
будет строить две или больше прямых для разделения данных, либо изменить
вид вводимых данных. Последняя возможность может превратить проблему
в линейную, если к двум имеющимся вводимым признакам добавить третий
и сделать пространство вводимых данных трехмерным (в результате два
класса будут размещаться в двух противоположных вершинах куба). Однако
данный подход не является нейронным решением, поэтому
предпочтительным является работа сети в условиях нелинейной проблемы.
Таким образом, мы сосредоточимся на решении, использующем две прямые
для разделения классов. Такая сеть потребует элемента, каждый из которых
получит на входе по два значения, чтобы представить две разделяющие
прямые, и третий элемент, объединяющий информацию об этих двух
прямых. Проблема моделирования отношения XOR приведена на рис. 2.
(0,1) (1,1)
Рис. 2.
Прямая 1
(1,0) (0,0)
Прямая 2
На рис. 3. приведена архитектура НС, которая будет моделировать две
разделяющие границы.
-
1
-
1
-
1
1.5
0.5
1
2
-
1
Входной слой
скрытый слой
выходной слой
Рис. 3.
Для элементов входного слоя будут использоваться индекс i , для
элементов скрытого слоя – j, а для элементов выходного слоя – k. В сети на
рис. 3. элементы разделены на три слоя. Элементы первого слоя являются
элементами ввода данных в сеть. Второй слой элементов называется
скрытым слоем – скрытые элементы связаны только с другими элементами и
не имеют непосредственных связей с внешней средой. Выходной слой
предназначен для передачи ответа сети во внешнюю среду.
В табл. 2. показаны комбинированный ввод и вывод (при
использовании пороговой функции) для элементов скрытого слоя при ответе
на вводимые данные проблемы XOR.
Таблица 2.
Комбинированный ввод
скрытого слоя
Вывод скрытого слоя
х у Элемент 1 Элемент 2 Элемент 1 Элемент 2
1 1 -0.5 -1.5 0 0
1 0 0.5 -0.5 1 0
0 1 0.53 -0.5 1 0
0 0 1.5 0.5 1 1
Вводимые образы преобразуются под воздействием весовых
коэффициентов первого слоя и скрытых элементов. Второй слой весов,
соединяющих скрытый слой с выходным слоем, тоже будет моделировать
прямую, поскольку у единственного выходного элемента также имеется два
вводимых значения и значение смещения. Если выходной элемент правильно
указывает класс, соответствующий каждому вводимому образцу, то данные
ввода для второго слоя весов должны быть линейно отделимы. Можно
проверит это с помощью нанесения на плоскость точек, соответствующих
выводу скрытых элементов, как показано на рис. 4.
(0,1)
Рис. 4.
(1,1)
(1,0)
Как видно из рис. 4. в результате прохождения первого слоя весов
исходная точка (0,1) переместилась в (1,0), а точки (0,0) и (1,1) поменялись
местами.
Прежде чем обратиться к рассмотрению алгоритма обучения, дающего
возможность сети научиться находить решения, необходимо подчеркнуть
важность функции преобразования (функции активности), связываемой с
каждым элементом сети. Примером нелинейной функции активности
является пороговая функция. Примером линейной функции является
тождественная функция, при которой вывод оказывается равным вводу.
3. Обучение по алгоритму обратного распространения ошибки
В общем случае задача обучения НС сводится к нахождению некой
функциональной зависимости Y=F(X) где X– входной, а Y– выходной
векторы. В общем случае такая задача, при ограниченном наборе входных
данных, имеет бесконечное множество решений. Для ограничения
пространства поиска при обучении ставится задача минимизации целевой
функции ошибки НС, которая находится по методу наименьших квадратов:
∑
=
−=
p
j
ji
)dy()w(E
1
2
2
1
(1)
где
y
j
– значение j-го выхода НС
d
j
– целевое значение j-го выхода
p– число нейронов в выходном слое
Обучение НС производится методом градиентного спуска, т.е. на
каждой итерации изменение веса производится по формуле
ij
ij
w
E
w
∂
∂
⋅−=
ηΔ
(2)
где h – параметр, определяющий скорость обучения.
ij
j
j
j
jij
w
S
dS
dy
y
E
w
E
∂
∂
⋅⋅
∂
∂
=
∂
∂
(3)
где
y
j
– значение выхода j-го нейрона
S
j
– взвешенная сумма входных сигналов, определяемая по формуле
∑
=
=
n
i
i
i
wxS
1
При этом множитель
i
ij
j
x
w
S
=
∂
∂
(4)
где
i
x – значение i-го входа нейрона
Далее рассмотрим определение первого множителя формулы (3)
∑∑
+
⋅⋅
∂
∂
=
∂
∂
⋅⋅
∂
∂
=
∂
∂
kk
)n(
jk
k
k
kj
k
k
k
kj
w
dS
dy
y
E
y
S
dS
dy
y
E
y
E
1
(5)
где
k – число нейронов в слое n+1.
Введем вспомогательную переменную
j
j
j
)n(
j
dS
dy
y
E
⋅
∂
∂
=
δ
(6)
Тогда мы сможем определить рекурсивную формулу для определения n-
ного слоя, если нам известно
)n(
j
δ
)n(
j
1
+
δ
следующего (n+1)-го слоя.
j
j
)n(
jk
k
)n(
k
)n(
j
dS
dy
w ⋅
⎥
⎦
⎤
⎢
⎣
⎡
⋅=
++
∑
11
δδ
(7)
Нахождение же для последнего слоя НС не представляет трудности, так
как нам известен целевой вектор, т.е. вектор тех значений, которые должна
выдавать НС при данном наборе входных значений.
)n(
j
δ
i
i
i
)N(
i
)N(
j
dS
dy
)dy( ⋅−=
δ
(8)
И наконец запишем формулу (6) в раскрытом виде
n
i
)n(
j
)n(
ij
xw ⋅⋅−=
δηΔ
(9)
Рассмотрим теперь полный алгоритм обучения НС:
1. подать на вход НС один из требуемых образов и определить значения
выходов нейронов НС
2. рассчитать
)N(
δ
для выходного слоя НС по формуле (8) и рассчитать
изменения весов
)N(
ij
w
Δ
выходного слоя N по формуле (9)
3. Рассчитать по формулам (7) и (9) соответственно
)N(
δ
и
)N(
ij
w
Δ
для
остальных слоев НС,
11,...,
N
n
−
=
4. Скорректировать все веса НС
)t(w)t(w)t(w
)n(
ij
)n(
ij
)n(
ij
Δ
+−= 1 (10)
5. Если ошибка существенна, то перейти на шаг 1
На этапе 2 сети поочередно в случайном порядке предъявляются
вектора из обучающей последовательности.
1
Лекция №6
Генетические алгоритмы
1. История появления генетических алгоритмов.
История эволюционных вычислений началась с разработки ряда
различных независимых моделей. Основными из них были генетические
алгоритмы и классификационные системы Голланда (Holland), опубликованные
в начале 60-х годов и получившие всеобщее признание после выхода в свет
книги, ставшей классикой в этой области, - "Адаптация в естественных и
искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В
70-х годах в рамках теории случайного поиска Растригиным Л.А. был
предложен ряд алгоритмов, использующих идей бионического поведения
особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по
эволюционному моделированию. Развивая идеи Цетлина М.Л. о
целесообразном и оптимальном поведении стохастических автоматов, Неймарк
Ю.И. предложил осуществлять поиск глобального экстремума на основе
коллектива независимых автоматов, моделирующих процессы развития и
элиминации особей. Большой вклад в развитие эволюционного
программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу
в подходах, каждая из этих "школ" взяла за основу ряд принципов,
существующих в природе, и упростила их до такой степени, чтобы их можно
было реализовать на компьютере.
2. Основные понятия.
Генетические Алгоритмы - адаптивные методы поиска, которые в
последнее время часто используются для решения задач оптимизации (поиска
оптимального решения). Они основаны на генетических процессах
биологических организмов: биологические популяции развиваются в течение
нескольких поколений, подчиняясь законам естественного отбора и по
принципу "выживает наиболее приспособленный", открытому Чарльзом