Файл: Учебнометодическое пособие по лабораторному практикуму. Спб ниу итмо, 2013. 35 с. В учебнометодическом пособии предлагаются лабораторные работы, охватывающие основные понятия теории искусственного интеллекта.pdf

МИНИСТЕРСТВО
ОБРАЗОВАНИЯ
И
НАУКИ
РОССИЙСКОЙ
ФЕДЕРАЦИИ
САНКТ
-
ПЕТЕРБУРГСКИЙ
НАЦИОНАЛЬНЫЙ
ИССЛЕДОВАТЕЛЬСКИЙ
УНИВЕРСИТЕТ
ИНФОРМАЦИОННЫХ
ТЕХНОЛОГИЙ
,
МЕХАНИКИ
И
ОПТИКИ
А
.
С
.
Потапов
,
О
.
В
.
Щербаков
,
И
.
Н
.
Жданов
ТЕХНОЛОГИИ ИСКУССТВЕННОГО
ИНТЕЛЛЕКТА
:
Учебно
-
методическое
пособие
по
лабораторному
практикуму
Санкт
-
Петербург
2013

2
Потапов А.С., Щербаков О.В., Жданов И.Н. Технологии искусственного интеллекта: Учебно-методическое пособие по лабораторному практикуму.
– СПб: НИУ ИТМО, 2013. – 35 с.
В учебно-методическом пособии предлагаются лабораторные работы, охватывающие основные понятия теории искусственного интеллекта.
Особое внимание уделяется машинному обучению и распознаванию образов.
Предназначено для студентов, обучающихся по направлению подготовки
200700 – «Фотоника и оптоинформатика».
Рекомендовано советом факультета Фотоники и оптоинформатики НИУ
ИТМО для использования в качестве учебно-методического пособия для студентов высших учебных заведений, обучающихся по направлению подготовки 200700 – «Фотоника и оптоинформатика».
В 2009 году
Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория
«Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования
«Санкт-
Петербургский государственный университет информационных технологий, механики и оптики» на 2009–2018 годы.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2013

А. С. Потапов, 2013
© О.В. Щербаков 2013
© И.Н. Жданов 2013

3
1. Изучение классических методов поиска – градиентного спуска и
моделирования отжига
Цель работы – ознакомиться с методами поиска в непрерывном пространстве состояний в случаях отсутствия и наличия вторичных минимумов. Данная работа имеет два варианта выполнения.
Вариант 1
Задание по работе:
1.
Изучить теоретическую часть работы.
2.
Реализовать методы градиентного спуска и моделирования отжига.
3.
Для функций двух видов: вогнутой и с вторичными минимумами применить методы поиска, оценить скорость их сходимости и возможность нахождения глобального минимума.
Теоретическая часть
Метод градиентного спуска
Метод градиентного спуска – это классический метод поиска минимума дифференцируемой функции с аргументами, принимающими вещественные значения. Данный метод, как правило, применяется для многомерных функций, поскольку в одномерном случае существуют более эффективные методы поиска.
Как известно, градиент некоторый функции
( )
x
f
в некоторой точке показывает направление локального наискорейшего увеличения функции.
Этот факт используется в методах градиентного спуска (подъема).
Эти методы описываются следующей последовательностью действий:
1.
Выбрать начальную точку
)
,...
(
0
,
0
,
1 0
n
x
x
=
x
Установить номер итерации
: i=0.
2.
Для текущей точки определить значение градиента
:
( )
( )
( )






∂
∂
∂
∂
=
∇
i
n
i
i
x
f
x
f
f
x
x
x
,...,
1
(1)
В
случае если градиент не может быть вычислен аналитически
, его компоненты могут быть оценены
:
( )
x
f
x
x
x
x
x
x
f
x
f
i
i
n
i
j
i
j
i
j
i
i
j
∆
−
∆
+
≈
∂
∂
+
−
)
(
)
,...,
,
,
,...,
(
,
,
1
,
,
1
,
1
x
x
(2)
3.
Определить положение следующей точки
:
( )
( )
i
i
i
i
f
f
d
x
x
x
x
∇
∇
−
=
+
1
,
(3)

4 где
d – параметр
, определяющий скорость спуска
, и
положить
i=i+1.
4.
Перейти к
шагу
2, если не выполнен критерий останова
Существует несколько способов ввода критерия останова
Самый простой
– это наложить ограничение на количество итераций
Другие способы связаны с
проверкой того
, что текущая точка или значение функции
f меняются мало
При фиксированном шаге
d изменение положения текущей точки происходит всегда на одну и
ту же величину
Однако в
этом случае можно проверять изменение за несколько итераций и
сравнивать с
d:
kd
k
i
i
−
−
x
x
Существует также возможность адаптивного выбора шага
d
Для этого на каждой итерации осуществляется выбор такого значения из
dw
d
w
d
d
d
d
=
=
=
2 1
0
,
/
,
(
где
w
– некоторый параметр
, как правило
(
]
2
,
1
∈
w
), что значение функции в
точке
( )
( )
i
i
j
i
j
i
f
f
d
x
x
x
x
∇
∇
−
=
+
)
(
1
минимально
Таким образом
, если при большом
d
метод градиентного спуска
«
проскакивает
» минимум
, то
d
будет уменьшаться
Уменьшение
d
ниже заданного порога также служит критерием остановка
Напротив
, на пологих участках значение
d
будет увеличиваться
При условии существования глобального минимума функции
f
метод градиентного спуска обычно сходится
(
за исключением случаев
, когда вдоль некоторого направления функция
, монотонно убывая
, стремится к
некоторому конечному пределу при
∞
→
x
).
Сходимость метода обеспечивается тем
, что на каждой итерации выбирается такая точка
i
x
, что
)
(
)
(
1
−
<
i
i
f
f
x
x
Метод
, однако
, не гарантирует нахождения глобального минимума
, поскольку при достижении любого локального минимума метод не в
состоянии определить направление на более глубокий минимум
(
и вообще обнаружить его существование
) и
останавливается в
соответствии с
выбранным критерием останова
В
связи с
этим
, выбор начальной точки может существенным образом сказываться на получаемом результате
Метод моделирования отжига
Метод моделирования отжига предназначен для поиска глобального минимума некоторой функции
R
S
f
→
:
, где
S
– некоторое пространство
(
необязательно непрерывное
), элементы которого интерпретируются как состояния некоторой воображаемой физической системы
, а
значения самой функции
– как энергия этой системы
E
=
f
(
x
) в
состоянии
S
x
∈

5
В
методе моделирования отжига система в
каждый момент времени находится в
некотором состоянии
x
i
, а
также обладает некоторой температурой
T
, которая является управляемым параметром
На каждой итерации система случайным образом переходит в
новое состояние
1
+
→
i
i
x
x
Механизм выбора нового состояния состоит из двух частей
:
1.
Сначала выбирается
1
+
i
x
в соответствии с
некоторой функцией распределения
)
,
,
(
1
T
x
x
g
i
i
+
Как правило
, эта функция зависит только от расстояния
i
i
x
x
−
+
1
, причем с
увеличением этого расстояния вероятность перехода понижается
2.
После случайного выбора
1
+
i
x
проверяется вероятность перехода в
это новое состояние
, исходя из разности энергий и
текущей температуры
:
)
,
(
T
E
h
∆
,
)
(
)
(
1
i
i
x
f
x
f
E
−
=
∆
+
Здесь
)
,
(
T
E
h
∆
показывает вероятность перехода в
состояние с
другой энергией
Проверка производится следующим образом
: выбрасывается случайное число из диапазона
[0, 1].
Если это число оказывается меньше
, чем значение вероятности
)
,
(
T
E
h
∆
, то новое состояние
1
+
i
x
принимается
, в
противном случае шаг
1 повторяется
Функция
)
,
(
T
E
h
∆
, как правило
, стремится к
1 при
E
∆
, стремящемся в
минус бесконечность
, и
стремится к
0 при
E
∆
, стремящемся в
плюс бесконечность
(
то есть предпочтение в
среднем отдается состояниям с
меньшей энергией
).
Поскольку метод моделирования отжига базируется на физических принципах
, то и
функции распределения вероятностей
)
,
,
(
1
T
x
x
g
i
i
+
и
)
,
(
T
E
h
∆
также часто заимствуются из физики
В
частности
, достаточно популярен больцмановский отжиг
, в
котором
:
)
2
/
|
|
exp(
)
2
(
)
,
,
(
2 1
2
/
1
T
x
x
T
T
x
x
g
i
i
D
i
i
−
−
π
=
+
−
+
,
(4) где
D
– размерность пространства
S
;
T
E
T
E
T
E
h
/
)
/
exp(
1 1
)
,
(
∆
−
≈
∆
+
=
∆
(5)
Таким образом
, температура
T
определяет
, насколько в
среднем может меняться текущее состояние
i
x
, а
также то
, насколько в
среднем может меняться энергия системы при переходе в
новое состояние
Поскольку переход в
состояния с
меньшей энергией более вероятен
, чем переход в
состояния с
более высокой энергией
, то система будет больше времени проводит именно в
низкоэнергетических состояниях
Чтобы обеспечить сходимость системы к
некоторому состоянию с
наименьшей энергией
, температуру системы понижают с
переходом к
следующей итерации
В
больцмановском отжиге применяется следующий закон понижения температуры
:

6
,
)
1
ln(
0
i
T
T
i
+
=
(6) где номер итерации
0
>
i
. Такой закон может, однако, потребовать большое число итераций, особенно при больших значениях начальной температуры T
0
, в связи с чем используется более быстрое понижение температуры:
i
T
T
i
+
=
1 0
(7)
Начальная температура неявно задает область, в которой будет осуществляться поиск глобального минимума, а также определяет необходимое для сходимости число итераций.
Экспериментальная часть
В данной работе проводят сравнительный анализ методов градиентного спуска и моделирования отжига. Суть сравнительного анализа в данном случае заключается в построении графиков зависимости точности находимого решения от числа итераций для обоих методов и сопоставлении этих графиков для функций различных типов. Для этого необходимо последовательно выполнить следующие действия.
1. Реализовать методы градиентного спуска и моделирования отжига и описать детали выбранной реализации.
2. Для нескольких вогнутых (обладающих единственным минимумом) функций построить графики зависимости
*
x
x
−
i
(где
*
x - истинное положение глобального минимума) от номера итерации i для обоих методов. Выбранные для исследования функции должны различаться средним значением модуля градиента (крутизной). Следует обратить внимание на выбор начальной точки
0
x , которая должна отличаться от искомого минимума
*
x . В методе моделирования отжига следует также обратить внимание на задание начальной температуры T
0
и ее влиянии на скорость сходимости.
3. Для нескольких функций с многими локальными минимумами определить условия сходимости обоих методов к глобальному минимуму.
Для градиентного спуска определить, с какой вероятностью метод сходится к глобальному минимуму при случайном выборе (из некоторого фиксированного диапазона) начальной точки. Для метода моделирования отжига определить, какая начальная температура обеспечивает сходимость к глобальному минимуму. Для исследования следует брать функции с разным числом минимумов.
4.
Проанализировать полученные результаты.
Определить предпочтительность использования каждого из методов при поиске

7 минимума функции с одним и многими минимумами, опираясь на скорость сходимости и на легкость нахождения глобального минимума.
Сделать выводы по работе.
Литература
1.
Назаров, А.В. Нейросетевые алгоритмы прогнозирования и
оптимизации систем / А.В. Назаров, А.И. Лоскутов. – СПб.: Наука и
Техника, 2003. – С. 237-238.
Вопросы для самопроверки:
1.
Какое условие сходимости метода градиентного спуска к глобальному минимуму?
2.
Каков смысл параметра температуры в методе моделирования отжига?
3.
На что влияет выбор начальной температуры в методе моделирования отжига?
4.
Пусть в методе моделирования отжига используется закон уменьшения температуры
)
1
/(
0
i
T
T
i
+
=
и пусть
100 0
=
T
. Сколько требуется итераций, чтобы обеспечить точность нахождения минимума 10
-4 5.
Какое основное отличие методов моделирования отжига и градиентного спуска?
6.
Как можно было бы совместно использовать два этих метода?
Вариант 2
Задание по работе:
1.
Изучить теоретическую часть работы.
2.
Реализовать генетический алгоритм поиска минимума.
3.
Для функций двух видов: вогнутой и с вторичными минимумами применить генетические алгоритмы и оценить скорость сходимости и возможность нахождения глобального минимума в зависимости от размера начальной популяции и скорости мутаций.
Теоретическая часть
Генетические алгоритмы и эволюционные стратегии поиска
Генетические алгоритмы (ГА) предназначены для нахождения экстремумов функций от произвольных объектов, используя при этом приемы, заимствованные у естественной эволюции. Сами объекты трактуются как некоторые организмы, а оптимизируемая функция – как приспособленность организмов, или фитнесс-функция. Множество

8 возможных объектов взаимно однозначно отображается на некоторое подмножество множество битовых строк (обычно фиксированной длины).
Эти строки трактуются как хромосомы (геномы).
Особенность генетических алгоритмов заключается в том, что они работают с битовыми строками, не опираясь на структуру исходных объектов, что позволяет применять ГА без модификации для любых объектов. Единственно, что требуется для такого применения, – это перекодирование объектов в геномы.
Эволюционные стратегии отличаются от генетических алгоритмов лишь в том, что в первых используются структурированные описания объектов, то есть такие описания, элементы которых имеют вполне четкий смысл в той предметной области, к которой относятся данные объекты.
Двумя основными механизмами эволюции, наиболее часто моделируемыми в генетических алгоритмах и эволюционных стратегиях, являются скрещивание и мутации. При этом схема эволюционных методов поиска выглядит следующим образом.
1. Сгенерировать начальную популяцию (случайную совокупность объектов).
2. Выбрать родительские пары.
3. Для каждой родительской пары с использованием оператора скрещивания породить потомство.
4. В хромосомы порожденного потомства внести случайные искажения оператором мутации.
5. Произвести отбор особей из популяции по значению их фитнесс- функции.
6. Повторять шаги 2-4, пока не выполнится критерий остановки.
Рассмотрим каждый из шагов чуть подробнее.
1. Генерация начальной популяции обычно производится равномерно по пространству генов (или по пространству описаний объектов). Размер популяции – установочный параметр.
2. Выбор родительских пар может осуществляться различными способами. Выбор родителей осуществляется в два этапа: выбор первого родителя и формирование пары. При выборе одного родителя обычно используется один из следующих способов:
- с равной вероятностью выбирается любая особь из имеющейся популяции;
- особь выбирается случайно с вероятностью, пропорциональной значению фитнесс-функции; то есть в этом случае значение фитнесс- функции сказывается не только на том, какие особи останутся в популяции в результате отбора, но и на то, сколько потомства они произведут.

9
Выбор второго родителя осуществляется по одному из следующих критериев:
- независимо от уже выбранного родителя (то есть второй родитель выбирается абсолютно так же, как и первый);
- на основе ближнего родства;
- на основе дальнего родства.
В последних двух случаях выбор одного родителя влияет на выбор другого родителя: с большей вероятностью формируются пары, состоящие из особей, которые больше похожи друг на друга (то есть ближе находятся в пространстве геномов или описаний объектов) в случае использования ближнего родства и меньше похожи – в случае дальнего родства. В генетических алгоритмах в качестве меры близости обычно используется расстояние Хемминга.
3. Оператор скрещивания – это оператор, который определяет, как из хромосом родителей формировать хромосомы их потомства. Часто применяется следующий оператор скрещивания: хромосомы делятся в некоторой случайной точке и обмениваются этими участками (то есть, все, что идет до этой точки, берется от одного родителя, а все, что после, – от другого).
Это одноточечный кроссинговер.
В многоточечном кроссинговере таких участков обмена больше.
При равномерном скрещивании каждый бит хромосомы берется от случайного родителя.
4. Мутации обычно осуществляются как случайная замена одного бита хромосомы. Скорость мутаций выражается в том, как часто они осуществляются. Это управляемый параметр, который влияет на скорость сходимости и вероятность попадания в локальный экстремум.
5. Отбор особей в новую популяцию чаще всего осуществляется одной из двух стратегий:
- пропорциональный отбор, при котором вероятность того, что некая особь останется в следующей популяции, пропорциональна значению фитнесс-функции этой особи;
- элитный отбор, при котором из популяции отбираются лучшие по значению фитнесс-функции особи, и они детерминированным образом переходят в следующую популяцию.
Формирование новой популяции может осуществляться как на основе потомков и родителей, так и на основе только потомков в зависимости от конкретной реализации.
6. Основные критерии останова базируются либо на числе сменившихся поколений (количестве выполненных итераций), либо на некотором условии стабильности популяции. Число поколений не является адаптивным по отношению к виду фитнесс-функции, поэтому используется обычно в качестве не основного критерия. Проверка стабильности популяции в общем виде, как правило, требует значительных