Ассоциативная память и сети Хопфилда От нейронных сетей к сетям Хопфилда



Скачать 150.62 Kb.

Дата17.02.2017
Размер150.62 Kb.
Просмотров61
Скачиваний0

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Сети Хопфилда
Сергей Николенко
Академический Университет, весенний семестр 2011
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Outline
1
Ассоциативная память и сети Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
2
От нейронных сетей к сетям Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
3
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Как работает мозг
Как работает наша память? Мы запоминаем ассоциации.
Например, надеюсь, ѕ16 : 00 в средуї  ѕлекция по machine learningї.
Потом нам говорят  ѕ16 : 00 в вредуї или (что главное)
ѕвторая половина дня в средуї, а мы припоминаем  там же лекция будет.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Как работает компьютер
Как работает память компьютера? Компьютер запоминает массивы данных.
Можно, конечно, использовать избыточное кодирование и защититься от небольшого количества ошибок.
Но это не настоящая ассоциативность. Как добиться того,
чтобы по размытоошибочному образу появлялась нужная ассоциация?
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Зачем это надо
Зачем нужна ассоциативная память?
Первый пример  распознавание образов. Чем разные картинки похожи друг на друга? Как по искажјнной картинке получить ассоциацию на еј значение?
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Обучение по Хеббу
Обучение по Хеббу (Hebbian learning)  это математическая реализация ассоциативной памяти.
Пусть есть нейронная сеть, в которой каждый нейрон x i
отвечает за какое-то событие.
При этом каждый нейрон связан с каждым, и веса у них изменяются в соответствии с корреляцией между событиями:
dw ij dt
?
Corr(x i
,
x j
).
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Обучение по Хеббу
Теперь это работает так: каждый раз, когда в 16 : 00 в среду происходит лекция, вес между этими событиями увеличивается.
Поэтому потом, на стадии применения сети, когда сеть
ѕвспоминаетї одно из этих событий, она с высокой вероятностью ассоциирует его с другим.
Это обучение не требует учителей, тестовых примеров с готовыми ответами (unsupervised learning)  учится просто из происходящего.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Сети Хопфилда
Сети Хопфилда нужны как раз для того, чтобы научить компьютер ассоциативно мыслить.
Как вы уже догадались, сеть Хопфилда  это нейронная сеть, представляющая собой полный граф.
Нейроны  линейные с лимитом активации; для нейрона x
i
:
a i
=
j w
ij x
j
,
x i
(
a i
) =
1,
a ? 0
?
1, a < 0.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Синхронные и асинхронные обновления
Важный момент: поскольку сеть с обратной связью
(feedback), надо понять, синхронно или асинхронно мы проводим апдейты весов.
Синхронно  это когда все веса считают свой результат одновременно и одновременно меняются.
Асинхронно  когда по одному.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Суть метода
Суть в том, чтобы сеть Хопфилда сходилась к заранее заданному набору воспоминаний {x
(
i)
}
i
Тогда, с чего бы мы ни начали, мы придјм к одному из имеющихся воспоминаний, то есть вызовем самую близкую ассоциацию.
Воспоминание  это множество значений каждого веса
{x
(
i)
j
}
j
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Обучение сети Хопфилда
Если мы хотим запомнить набор {x
(
i)
}
i
, то весам присваиваем, по методу Хебба, значения, связанные с корреляциями:
w ij
= ?
k x
(
k)
i x
(
k)
j
Здесь ? никакой роли не играет, можно, например, сделать
?
обратной числу воспоминаний, чтобы веса не росли слишком.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
Непрерывные сети Хопфилда
То были дискретные сети. Бывают и непрерывные, где нейроны работают по tanh:
a i
=
j w
ij x
j
,
x i
=
tanh(a i
).
Тут уже значение ? имеет значение; или можно его фиксировать, а вместо этого ввести другой гиперпараметр x
i
=
tanh(?a i
).
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
О сходимости
Мы бы хотели, чтобы сети сходились куда нам надо.
Для этого неплохо было бы, чтобы они вообще сходились.
Давайте попробуем доказать, что непрерывная сеть
Хопфилда при известном правиле пересчјта весов действительно сходится.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Outline
1
Ассоциативная память и сети Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
2
От нейронных сетей к сетям Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
3
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Двунаправленная ассоциативная память
Начнјм со знакомого аппарата: нейронных сетей.
Рассмотрим нейронную сеть с двумя слоями: входным и выходным.
Входной слой получает вход, пересчитывает свои результаты и передајт их выходному слою.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Двунаправленная ассоциативная память
Новизна в том, что теперь второй слой, пересчитав свои результаты, отдајт их обратно входному слою.
И процесс итеративно продолжается.
Идея в том, чтобы сеть достигла какого-то равновесия,
стабильного состояния.
Такие сети называются резонансными, или двунаправленной ассоциативной памятью (BAM).
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Двунаправленная ассоциативная память
Если в первом слое n перцептронов, во втором k, то получается матрица весов W размером n Ч k.
На вход поступает вектор x
0
(строка), который преобразуется в вектор y
0
Мы будем использовать линейные перцептроны с лимитом активации:
y
0
=
sgn(x
0
W).
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Двунаправленная ассоциативная память
Потом y
0
подают на вход; новый шаг происходит как x
1
=
sgn(Wy
0
)
(получаем из вектора длины k вектор длины n).
И так далее; получается последовательность пар (x i
,
y i
)
:
y i
=
sgn(x i
W),
x i+1
=
sgn(Wy i
).
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Двунаправленная ассоциативная память
Вопрос: сойдјтся ли процесс? То есть дойдјм ли мы до векторов x и y:
y =
sgn(xW), x = sgn(Wy ).
Если да, получится ассоциативная память: мы дали один вектор, а потом после нескольких итераций сеть
ѕвспомнилаї дополнительный к нему вектор, и наоборот.
Более того, сеть вспомнила бы ассоциацию, даже если бы вектор был немножко не такой, как раньше  всј сошлось бы к ближайшей паре (x, y).
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Двунаправленная ассоциативная память
Чтобы обучить BAM, можно использовать хеббовское обучение.
Когда мы хотим запомнить всего одну ассоциацию,
матрица корреляций между двумя векторами  это просто
W = x y
. Тогда y =
sgn(xW) = sgn(xx y) = sgn(||x||
2
y) = y,
x
=
sgn(Wy ) = sgn(x yy ) = sgn(x ||y||
2
) =
x .
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Двунаправленная ассоциативная память
Но можно хранить и несколько ассоциаций
(
x
1
,
y
1
), . . . , (
x m
,
y m
)
:
W = x
1
y
1
+ . . . +
x m
y m
Для этого случая будет лучше, если векторы x i
и y i
будут между собой попарно ортогональны.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
BAM и еј функция энергии
Рассмотрим BAM со стабильным состоянием (x, y). Мы сейчас в положении (x
0
,
y
0
)
Определим вектор возбуждений (excitation vector):
e
=
Wy
0
Получается, что система в стабильном состоянии, если sgn(e) = x
0
То есть если вектор e достаточно близок к x
0
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
BAM и еј функция энергии
Значит, можно ввести энергию
E = ?x
0
e
= ?
x
0
Wy
0
,
и она будет тем меньше, чем ближе e к x
0
E получается мерой того, насколько мы близки к стабильному состоянию.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
BAM и еј функция энергии
Если обобщить это просто на BAM с матрицей W, то на шаге (x i
,
y i
)
функция энергии определяется как
E(x i
,
y i
) = ?
1 2
x i
Wy i
1 2
пригодится позже, просто для удобства.
Теперь мы можем доказать, что BAM рано или поздно сойдјтся к стабильному состоянию.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
BAM и еј функция энергии
Заметим, что E(x, y) можно переписать в двух разных видах:
E(x, y) = ?
1 2
k i=1
e i
y i
= ?
1 2
n i=1
g i
x i
,
где e = xW  возбуждения нейронов второго слоя, а g = Wy
 первого слоя.
Будем рассматривать асинхронные апдейты: во время t мы случайно выбираем, какой перцептрон пересчитывать.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
BAM и еј функция энергии
Состояние i-го перцептрона первого слоя изменится,
только если g i
и x i
не совпадают в знаке.
И в таком случае x i
заменится на x i
=
sgn(g i
)
Поскольку остальные при этом асинхронном апдейте не меняются, энергия изменяется как
E(x, y) ? E(x , y) = ?
1 2
g i
(
x i
?
x i
) >
0.
Значит, энергия уменьшается на каждом шаге, а всего комбинаций возможных состояний конечное число.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Вариационные методы
Теперь мы хотели бы перейти к общему доказательству для сетей Хопфилда.
Мы там не зря называли e вектором возбуждений  это действительно связано с системой из элементарных частиц.
Сейчас мы вспомним вариационные методы и докажем,
что сеть Хопфилда куда-нибудь сходится.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Вариационные методы
В статфизике часто бывают распределения типа p(x) =
1
Z
e
??
E(x,J)
,
где, например,
E(x, J) = ?
1 2
i,j
J
ij x
i x
j
?
i h
i x
i
Эта E  функция энергии системы элементарных частиц со спинами x.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Приближение E
Как нам обработать такую функцию?
Будем еј приближать более простым распределением:
Q(x, a) =
1
Z
e
?
i a
i x
i
Качество приближения будем оценивать посредством вариационной свободной энергии
?
F =
x
Q(x, a) ln
Q(x, a)
e
??
E(x,J)
Это на самом деле средняя энергия E по распределению Q
минус энтропия Q.
Чем ближе приближение к p, тем меньше ?
F.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Приближение E через Q: энтропия
В нашем конкретном случае энтропия Q  это сумма энтропий индивидуальных спинов
S
Q
=
x
Q ln
1
Q
=
i
H
2
(
q i
) =
i q
i ln
1
q
+ (
1 ? q) ln
1 1 ? q
Здесь q i
 вероятность того, что спин x i
равен +1, то есть q
i
=
e a
i e
a i
+
e
?
a i
=
1 1 + e
?
2a i
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Приближение E через Q: среднее по Q
Среднее по Q тоже будет достаточно просто получить:
i
Q(x, a)E(x, J) = ?
1 2
i,j
J
i,j
x i
x j
?
i h
i
x i
,
где x i
=
e ai
?
e
?
ai e
ai
+
e
?
ai
=
tanh a i
=
2q i
?
1.
Упражнение. Доказать эти формулы. Главное  то, что x i
и x j
в J
ij x
i x
j независимы.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Минимизация
Теперь надо минимизировать вариационную свободную энергию
?
F = ?
?
??
1 2
i,j
J
i,j
x i
x j
?
i h
i
x i
?
? ?
i
H
2
(
q i
).
Упражнение. Взять частные производные и доказать, что минимум достигается в a
k
= ?
i
J
ki
x i
+
h k
,
x k
=
tanh a k
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
От минимизации к алгоритму
В этих уравнениях a i
выражаются через x i
и наоборот.
Если пользоваться ими как итеративной процедурой, то
?
F будет уменьшаться.
Такая функция называется функцией Ляпунова. Если функция Ляпунова есть, то, значит, динамическая система точно сходится к точке или циклу, на котором функция
Ляпунова константна.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
Сети Хопфилда
В сетях Хопфилда всј то же самое:
?
F (x) = ??
1 2
x Wx ?
i
H
2 1 + x i
2
Но это сильно зависит от условий задачи.
Упражнение.
1
Приведите пример сети Хопфилда с несимметричными весами, которая не сходится к одному состоянию.
2
Приведите пример сети Хопфилда с синхронными апдейтами, которая не сходится к одному состоянию.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Outline
1
Ассоциативная память и сети Хопфилда
Ассоциативная память
Обучение по Хеббу
Сети Хопфилда: определения и обучение
2
От нейронных сетей к сетям Хопфилда
Двунаправленная ассоциативная память
Сходимость сетей Хопфилда
3
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Сети Хопфилда со временем
Нехорошо, что мы зависим от того, синхронные апдейты или асинхронные.
Поэтому можно на самом деле не зависеть, а считать реакцию нейронов функцией от времени.
Будем считать, что a i
(
t) =
j w
ij x
j
(
t) подсчитывается мгновенно, а нейрон реагирует по уравнению d
dt x
i
(
t) = ?
1
?
(
x i
(
t) ? f (a i
)),
где f (a)  функция активации (tanh).
Тогда, если матрица весов симметрична, эта динамическая система будет иметь ту же самую функцию Ляпунова.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Распознавание образов
Сети Хопфилда применяют, например, для распознавания образов.
При этом стабильные состояния системы  это образцы для распознавания, и работает так: при поступлении образа начинаем запускать сеть, пока не сойдјтся.
Если пытаться запихнуть слишком много образов,
получаются проблемы: ложные стабильные состояния,
неустойчивые стабильные состояния...
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Задачи оптимизации
А ещј можно попробовать приспособить сети Хопфилда для constraint satisfaction.
Например, для задачи коммивояжјра на K городах можно рассмотреть сеть с K
2
нейронами, каждый из которых соответствует тому, что город i находится на jом месте пути.
Веса должны обеспечивать, чтобы путь был правильный
(отрицательные веса на нейроны в одной строке и столбце), а остальные соответствуют расстояниям.
Но тут тоже надо аккуратно.
Сергей Николенко
Сети Хопфилда

Ассоциативная память и сети Хопфилда
От нейронных сетей к сетям Хопфилда
Другие замечания о сетях Хопфилда
Время в сетях Хопфилда
Применение сетей Хопфилда
Thank you!
Спасибо за внимание!
Сергей Николенко
Сети Хопфилда


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал