Нейронная сеть Липпмана-Хемминга
Published 22 декабря 2024 г. 8:31
Приветствую тебя, дорогой читатель! Сейчас со всех сторон вещают о нейронных сетях и как они помогают во многих сферах человеческой деятельности. И это не только генерация фото котиков 🐱💻😺. Для многих работа нейросетей похожа на магию, хотя на самом деле их "мозг" можно описать несколькими математическими формулами.
В качестве примера давайте рассмотрим нейронную сеть Липпмана-Хемминга (или же НС Хемминга). Постараюсь, чтобы математики было немного, а картинок побольше).
Итак, рассматриваемая НС используется в качестве классификатора изображений. Она состоит из 2 слоев: первый слой содержит эталонные шаблоны, второй служит в качестве классификатора. Принцип её работы достаточно прост: на вход поступает вектор (размер вектора = размеру эталонного шаблона), на первом слое вычисляется "схожесть" входного вектора и эталонных, на втором слое выбирается эталонный шаблон, имеющий наибольшую "схожесть" с входным вектором. Количество нейронов в первом и втором слоях = количеству эталонных шаблонов.
Давайте подробнее остановимся на понятии "схожесть" (или кому-то больше нравится слово "похожесть"🙂). В сети Хемминга для определения того, насколько входной вектор "похож" на эталонный используется расстояние Хемминга (ба-дум-тссс).
Вычисление данного расстояния лучше всего показать на примере. Допустим, у нас есть 2 эталонных вектора:
- T1=[1,0,1,0,1,1],
- T2=[0,1,0,1,0,1]
(PS: здесь стоит упомянуть, что элементы векторов обычно принадлежат множеству {-1, 1}, в нормализированном виде {0, 1}).
И есть входной вектор X:
X=[1,0,1,0,1,0].
Сейчас будет немного математики :-). Расстояние Хемминга (количество отличий между двумя векторами), вычисляется по формуле:
Т.е.
d1 = |1-1| + |0-0| + |1-1| + |0-0| + |1-1| + |0-1| = 1
d2 = |1-0| + |0-1| + |1-0| + |0-1| + |1-0| + |0-1| = 6
Поздравляю, вы только что вычислили расстояние Хемминга! Только пока непонятно, что с ним делать). Тут мы начинаем вычислять, насколько наш входной вектор "похож" на каждый из шаблонов сети. Данное вычисление происходит следующим образом:
Здесь Si - количество совпадений между X и Ti. N - длина вектора. Чем больше Si, тем больше похожи входные данные и шаблон. В нашем случае:
S1 = 6 - 1 = 5
S2 = 6 - 6 = 0
Теперь у нас есть значения, которые показывают нам, насколько наш входной вектор близок к каждому из эталонных. Пора выбирать победителя!
На втором слое сети происходит выбор между вычисленными значениями. Данный метод получил название Winner Takes All (loser has to fall 🎵).
Суть заключается в следующем: выбирается нейрон с максимальным значением S. Это и будет наш победитель и выход нейронной сети.
Конечно, у данной сети есть ряд недостатков. Самый очевидный: случаи, когда у нас есть одинаковые вычисленные меры схожести (Si = Sj, i ≠ j). Как тогда выбирать? Можно добавить правило на такие случаи, но согласитесь, наша классификация потеряет точность.
Также эта сеть будет плохо работать с измененными изображениями. Если сместить наше эталонное изображение на несколько пикселей, то она уже наврядли сможет провести корректную классификацию (вспомните знаменитый набор цифр для тренировки сетей, тут данная сеть провалится с треском).
Чтобы обойти проблему с классификацией измененных изображений было разработано улучшение сети Хэмминга, которое будет описано далее. А пока предлагаю посмотреть реализацию данной НС на Python🐍
```
import numpy as np
class HammingNetwork:
def __init__(self, templates):
"""
Инициализация сети с заданными шаблонами.
:param templates: Список шаблонов (векторы эталонов).
"""
self.templates = np.array(templates)
self.num_templates = len(templates)
self.num_features = len(templates[0])
def hamming_distance(self, x, t):
"""
Вычисление расстояния Хэмминга между входным вектором x и шаблоном t.
:param x: Входной вектор.
:param t: Шаблон.
:return: Расстояние Хэмминга.
"""
return np.sum(np.abs(x - t))
def compare(self, input_vector):
"""
Сравнение входного вектора с шаблонами и выбор наиболее похожего.
:param input_vector: Входной вектор.
:return: Индекс шаблона-победителя.
"""
similarities = []
for template in self.templates:
# Количество совпадений = длина вектора - расстояние Хэмминга
distance = self.hamming_distance(input_vector, template)
similarity = self.num_features - distance
similarities.append(similarity)
# Нахождение индекса шаблона с максимальным значением похожести
winner_index = np.argmax(similarities)
return winner_index, similarities
# Пример использования
if __name__ == "__main__":
# Шаблоны сети
templates = [
[1, 0, 1, 0, 1, 1], # Шаблон T1
[0, 1, 0, 1, 0, 1], # Шаблон T2
[1, 1, 1, 0, 1, 0], # Шаблон T3
]
# Входной вектор
input_vector = [1, 0, 1, 0, 1, 0]
# Инициализация и запуск сети
network = HammingNetwork(templates)
winner_index, similarities = network.compare(input_vector)
print(f"Входной вектор: {input_vector}")
print(f"Сходства с шаблонами: {similarities}")
print(f"Победивший шаблон: T{winner_index + 1}")
```
Теперь рассмотрим немного усложненный вариант данной сети. Чтобы устранить проблему влияния шума на качество классификации было предложено использовать рекурретные связи от второго слоя к самому себе и использование нескольких итераций для выявления "победителя" (сейчас будет страшная картинка).
На деле всё не так страшно 🙂. Формула для значений нейрона во втором слое приобретет следующий вид:
где - предыдущее значение нейрона.
Тут можно заметить новую переменную ɑ, которая будет являться нашим регулятором "силы" связей. Если ɑ = 0, то сеть становится чисто прямой (обычная сеть Хемминга). Также у нас появляется ещё один гиперпараметр, который мы можем задать - число итераций. Оба этих параметра можно подбирать автоматически для достижения лучших результатов классификации.
После того, как мы прогнали нашу сеть по итерациям, принцип WTA позволяет нам выбрать класс "победитель". Ниже представлена реализация усложненной сети Хемминга:
```
import numpy as np
class RecurrentHammingNetwork:
def __init__(self, templates, alpha=0.5, iterations=5):
"""
Инициализация сети Хэмминга с обратными связями.
:param templates: Список шаблонов (эталонов).
:param alpha: Коэффициент затухания для обратных связей.
:param iterations: Количество итераций для обновления нейронов.
"""
self.templates = np.array(templates)
self.num_templates = len(templates)
self.num_features = len(templates[0])
self.alpha = alpha
self.iterations = iterations
def hamming_distance(self, x, t):
"""Расстояние Хэмминга между вектором x и шаблоном t."""
return np.sum(np.abs(x - t))
def forward_pass(self, input_vector):
"""
Прямой проход и итеративное обновление с обратными связями.
:param input_vector: Входной вектор.
:return: Значения нейронов на выходе.
"""
# Начальные значения для нейронов второго слоя
y = np.zeros(self.num_templates)
# Итеративное обновление с обратными связями
for iteration in range(self.iterations):
print(f"\nИтерация {iteration + 1}:")
for i, template in enumerate(self.templates):
# Сумма текущей похожести и обратной связи
distance = self.hamming_distance(input_vector, template)
y[i] = (self.num_features - distance) + self.alpha * y[i]
print(f"Шаблон T{i + 1}: значение нейрона = {y[i]:.2f}")
return y
def predict(self, input_vector):
"""
Получение результата сети.
:param input_vector: Входной вектор.
:return: Индекс шаблона-победителя.
"""
output_values = self.forward_pass(input_vector)
winner_index = np.argmax(output_values)
return winner_index, output_values
# Пример использования
if __name__ == "__main__":
# Шаблоны сети
templates = [
[1, 0, 1, 0, 1, 1], # Шаблон T1
[0, 1, 0, 1, 0, 1], # Шаблон T2
[1, 1, 1, 0, 1, 0], # Шаблон T3
]
# Входной вектор
input_vector = [1, 0, 1, 0, 1, 0]
# Инициализация и запуск сети
network = RecurrentHammingNetwork(templates, alpha=0.5, iterations=5)
winner_index, output_values = network.predict(input_vector)
print("\nФинальные значения нейронов второго слоя:", output_values)
print(f"Победивший шаблон: T{winner_index + 1}")
```
### Обучение сети
Как такого обучения данной сети не происходит, обычно у нас уже имеется матрица с эталонными шаблонами и мы просто подаем на вход данные для классификации. Но мы же не хотим каждый раз вбивать матрицы для классификации новых объектов, это было бы очень долго (да и вообще программисты любят автоматизировать такого рода задачи 🙂). Есть несколько способов решения данной проблемы:
- Использование алгоритмов кластеризации для создания шаблонов;
- Адаптивное обновление шаблонов (ибо всё меняется со временем, даже эталон). Например можно обновлять шаблоны по формуле:
где - скорость обновления, X - входной вектор:
```
class AdaptiveHammingNetwork(RecurrentHammingNetwork):
def update_template(self, input_vector, winner_index, eta=0.1):
"""
Адаптивное обновление шаблона-победителя.
:param input_vector: Входной вектор.
:param winner_index: Индекс шаблона-победителя.
:param eta: Коэффициент обучения.
"""
self.templates[winner_index] = (
(1 - eta) * self.templates[winner_index] + eta * input_vector
)
# Пример использования
if __name__ == "__main__":
# Шаблоны
templates = [
[1, 0, 1, 0, 1, 1],
[0, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 1, 0],
]
# Входной вектор
input_vector = [1, 0, 1, 0, 1, 0]
# Создание адаптивной сети
network = AdaptiveHammingNetwork(templates, alpha=0.5, iterations=5)
winner_index, _ = network.predict(input_vector)
print(f"Победитель до обновления: T{winner_index + 1}")
# Обновление шаблона
network.update_template(input_vector, winner_index, eta=0.2)
print("Обновленные шаблоны:")
print(network.templates)
```
На этом всё, дорогой читатель! Надеюсь, статья помогла в понимании работы сети Липпмана-Хемминга, также ниже представлены ссылки для более подробного изучения материала. До новых встреч!😉
Ссылка раз
Ссылка два
Ссылка три
Ссылка четыре (на английском)