Оглавление
Часть 1 — линейная регрессия
Часть 2 — градиентный спуск
Часть 3 — градиентный спуск продолжение
Введение
Этим постом я начну цикл «Нейронные сети для новичков». Он посвящен искусственным нейронным сетям (внезапно). Целью цикла является объяснение данной математической модели. Часто после прочтения подобных статей у меня оставалось чувство недосказанности, недопонимания — НС по-прежнему оставались «черным ящиком» — в общих чертах известно, как они устроены, известно, что делают, известны входные и выходные данные. Но тем не менее полное, всестороннее понимание отсутствует. А современные библиотеки с очень приятными и удобными абстракциями только усиливают ощущение «черного ящика». Не могу сказать, что это однозначно плохо, но и разобраться в используемых инструментах тоже никогда не поздно. Поэтому моей первичной целью является подробное объяснение устройства нейронных сетей так, чтобы абсолютно ни у кого не осталось вопросов об их устройстве; так, чтобы НС не казались волшебством. Так как это не математический трактат, я ограничусь описанием нескольких методов простым языком (но не исключая формул, конечно же), предоставляя поясняющие иллюстрации и примеры.
Цикл рассчитан на базовый ВУЗовский математический уровень читающего. Код будет написан на Python3.5 с numpy 1.11. Список остальных вспомогательных библиотек будет в конце каждого поста. Абсолютно все будет написано с нуля. В качестве подопытного выбрана база MNIST — это черно-белые, центрированные изображения рукописных цифр размером 28*28 пикселей. По-умолчанию, 60000 изображений отмечены для обучения, а 10000 для тестирования. В примерах я не буду изменять распределения по-умолчанию.
Пример изображений из MNIST:
![](https://habrastorage.org/files/b1f/29c/ced/b1f29cced9254432bcd6ce3fb338a0ed.png)
Я не буду заострять внимание на структуре MNIST и просто выложу код, который загрузит базу и сохранит в нужном формате. Этот формат в дальнейшем будет использован в примерах:
loader.py
import struct
import numpy as np
import requests
import gzip
import pickle
TRAIN_IMAGES_URL = "http://yann.lecun.com/exdb/mnist/train-images-idx3-ubyte.gz"
TRAIN_LABELS_URL = "http://yann.lecun.com/exdb/mnist/train-labels-idx1-ubyte.gz"
TEST_IMAGES_URL = "http://yann.lecun.com/exdb/mnist/t10k-images-idx3-ubyte.gz"
TEST_LABELS_URL = "http://yann.lecun.com/exdb/mnist/t10k-labels-idx1-ubyte.gz"
def downloader(url: str):
response = requests.get(url, stream=True)
if response.status_code != 200:
print("Response for", url, "is", response.status_code)
exit(1)
print("Downloaded", int(response.headers.get('content-length', 0)), "bytes")
decompressed = gzip.decompress(response.raw.read())
return decompressed
def load_data(images_url: str, labels_url: str) -> (np.array, np.array):
images_decompressed = downloader(images_url)
# Big endian 4 числа типа unsigned int, каждый по 4 байта
magic, size, rows, cols = struct.unpack(">IIII", images_decompressed[:16])
if magic != 2051:
print("Wrong magic for", images_url, "Probably file corrupted")
exit(2)
image_data = np.array(np.frombuffer(images_decompressed[16:], dtype=np.dtype((np.ubyte, (rows * cols,)))) / 255,
dtype=np.float32)
labels_decompressed = downloader(labels_url)
# Big endian 2 числа типа unsigned int, каждый по 4 байта
magic, size = struct.unpack(">II", labels_decompressed[:8])
if magic != 2049:
print("Wrong magic for", labels_url, "Probably file corrupted")
exit(2)
labels = np.frombuffer(labels_decompressed[8:], dtype=np.ubyte)
return image_data, labels
with open("test_images.pkl", "w+b") as output:
pickle.dump(load_data(TEST_IMAGES_URL, TEST_LABELS_URL), output)
with open("train_images.pkl", "w+b") as output:
pickle.dump(load_data(TRAIN_IMAGES_URL, TRAIN_LABELS_URL), output)
Линейная регрессия
Линейная регрессия — метод восстановления зависимости между двумя переменными. Линейная означает, что мы предполагаем, что переменные выражаются через уравнение вида:
![](https://habrastorage.org/files/8c4/5ac/db7/8c45acdb73ed43cdb1681fdd40238c7c.png)
![](https://habrastorage.org/files/a2f/09c/780/a2f09c780ce64c318767d83edd313fe3.png)
![](https://habrastorage.org/files/055/53d/a7c/05553da7c2b243a2b3a39536b55731e9.png)
![](https://habrastorage.org/files/cf3/81f/50a/cf381f50ad1946999b466658a3d63d66.png)
generate_linear.py
import numpy as np
import matplotlib.pyplot as plt
TOTAL = 200
STEP = 0.25
def func(x):
return 0.2 * x + 3
def generate_sample(total=TOTAL):
x = 0
while x < total * STEP:
yield func(x) + np.random.uniform(-1, 1) * np.random.uniform(2, 8)
x += STEP
X = np.arange(0, TOTAL * STEP, STEP)
Y = np.array([y for y in generate_sample(TOTAL)])
Y_real = np.array([func(x) for x in X])
plt.plot(X, Y, 'bo')
plt.plot(X, Y_real, 'g', linewidth=2.0)
plt.show()
В результате должно получиться что-то вроде этого — достаточно случайно для неподготовленного человеческого глаза:
![](https://habrastorage.org/files/619/e50/5fd/619e505fd9a043e3aaba9c91d5e8f0e1.png)
Зеленая линия — это «база» — сверху и снизу от этой линии случайным образом распределены данные, распределение равномерное. Уравнение для зеленой линии:
![](https://habrastorage.org/files/078/9fa/304/0789fa3044a741eeb12ac666401f5f21.png)
Метод наименьших квадратов
Суть МНК заключается в том, чтобы отыскать такие параметры
![](https://habrastorage.org/files/c10/905/40f/c1090540f0894d4890a6c0595b0abe76.png)
Код
import matplotlib.pyplot as plt
plt.plot([1, 2, 3, 4, 5], [4, 2, 9, 9, 5], 'bo')
plt.plot([1, 2, 3, 4, 5], [3, 5, 7, 9, 11], '-ro')
plt.show()
![](https://habrastorage.org/files/384/33e/76f/38433e76f019465a901fd6b9149c9323.png)
Наиболее близким — значит, что вектор
![](https://habrastorage.org/files/46e/bfe/349/46ebfe349e5d40dc8b5c5ae2e112931b.png)
![](https://habrastorage.org/files/c10/905/40f/c1090540f0894d4890a6c0595b0abe76.png)
![](https://habrastorage.org/files/94b/afc/814/94bafc814ece473ea868c446f05ba9f7.png)
![](https://habrastorage.org/files/092/270/b05/092270b05729423a87d18191c7413bc3.png)
Математически это выглядит так:
![](https://habrastorage.org/files/4d6/df4/454/4d6df4454ed844798c8a5c47d638a28c.png)
![](https://habrastorage.org/files/db1/1f1/9df/db11f19df492419bbbe446412f565fe4.png)
![](https://habrastorage.org/files/790/30e/696/79030e6960af4a8e8518c78745761b57.png)
![](https://habrastorage.org/files/89a/91f/0fb/89a91f0fb0f04659ba5f67861ebda926.png)
![](https://habrastorage.org/files/ded/59c/f03/ded59cf03fb742d19005507a7d0e0d5d.png)
Я долго думал, стоит ли сразу переходить к векторизации кода и в итоге без нее статья слишком удлиняется. Поэтому введем новые обозначения:
![](https://habrastorage.org/files/1c3/315/cd7/1c3315cd7e894aafb9fdaf4de136cbc2.png)
![](https://habrastorage.org/files/25d/1dc/17b/25d1dc17b3c34c479a3ee005a4a05d50.png)
![](https://habrastorage.org/files/db1/1f1/9df/db11f19df492419bbbe446412f565fe4.png)
![](https://habrastorage.org/files/3b0/0d3/d43/3b00d3d439114fa1abfed39895235480.png)
A — матрица из значений свободной переменной x. В данном случае первый столбец равен 1 (отсутствует x_0) —
![](https://habrastorage.org/files/bf9/536/c68/bf9536c68cab45c7b765ed8091834430.png)
![](https://habrastorage.org/files/805/0e0/ad1/8050e0ad168a48749a2ce8de106f57f9.png)
После новых обозначений уравнение линии переходит в матричное уравнение следующего вида:
![](https://habrastorage.org/files/e38/1f8/3a5/e381f83a570247498a06618af38caf15.png)
![](https://habrastorage.org/files/4cc/6bb/35b/4cc6bb35babd480f84fe466b28f6af44.png)
![](https://habrastorage.org/files/ea6/1db/9ed/ea61db9ed9744c0bb23bc9833022b163.png)
Казалось бы, что все известно — и вектор Y, и вектор X — остается только решить уравнение. Большая проблема заключается в том, что система может не иметь решений — иначе, у матрицы A может не существовать обратной матрицы. Простой пример системы без решения — любые три\четыре\n точки не на одной прямой\плоскости\гиперплоскости — это приводит к тому, что матрица А становится неквадратной, а значит по определению нет обратной матрицы
![](https://habrastorage.org/files/cfc/925/709/cfc925709586475eb87d298478316e3f.png)
Наглядный пример невозможности решения «простым способ» (каким-нибудь методом Гаусса решить систему):
![](https://habrastorage.org/files/5ee/5b3/af5/5ee5b3af5a374494bbfa07bc1db8d5dc.png)
Система выглядит так:
![](https://habrastorage.org/files/006/d22/cc9/006d22cc9e054276a518d12270ce0660.png)
Как итог невозможно построить линию через эти три точки — можно лишь построить примерно верное решение.
Такое отступление — это объяснение того, зачем вообще понадобился МНК и его братья. Минимизации функции стоимости (функции потерь) и невозможность (ненужность, вредность) найти абсолютно точное решение — одни из самых базовых идей, что лежат в основе нейронных сетей. Но до них еще далеко, а пока вернемся к методу наименьших квадратов.
МНК говорит нам, что необходимо найти минимум суммы квадратов векторов вида:
![](https://habrastorage.org/files/83e/9fa/3fe/83e9fa3fe9d44e1ca1266eff76e748e9.png)
![](https://habrastorage.org/files/a02/bb5/3b4/a02bb53b48f74f44ab079de7f1cfda1b.png)
У меня не повернется язык назвать это тривиальным преобразованием, новичкам бывает довольно сложно уйти от простых переменных к векторам поэтому я распишу все это выражение полностью в «раскрытых» векторах. Опять-таки, чтобы ни одна строка не была непонятым «волшебством».
Для начала просто «раскроем» вектора в соответствии с их определением:
![](https://habrastorage.org/files/a3c/885/96c/a3c88596cdb9479cacdd9f660200eb41.png)
Проверим размерность — для матрицы А она равна (n;p), а для вектора
![](https://habrastorage.org/files/db1/1f1/9df/db11f19df492419bbbe446412f565fe4.png)
![](https://habrastorage.org/files/1c3/315/cd7/1c3315cd7e894aafb9fdaf4de136cbc2.png)
![](https://habrastorage.org/files/758/f24/717/758f2471788044b59d4ba3919947af7d.png)
Сверимся с определением — по определению выходит, что каждая строка правой матрицы равна
![](https://habrastorage.org/files/f36/880/bf2/f36880bf23474afc95655b89ec77d21c.png)
![](https://habrastorage.org/files/f53/b1c/a29/f53b1ca29e22455693c229044c026285.png)
![](https://habrastorage.org/files/bce/a84/be5/bcea84be52dd4491aaab398ddfbd985a.png)
![](https://habrastorage.org/files/e0d/d07/0f4/e0dd070f4dcb49cb88339c693fdbeef2.png)
![](https://habrastorage.org/files/e6c/1fc/678/e6c1fc678230406d926a1c7f43c7b0d1.png)
![](https://habrastorage.org/files/198/5d0/566/1985d0566f414e788357aac4e4a07538.png)
В итоге последняя строка и есть сумма квадратов длин, как нам и нужно. Каждый раз, конечно же, такие фокусы в уме проворачивать довольно долго, но к векторной нотации можно привыкнуть быстро. У этого есть и плюс для программиста — удобней работать и портировать код для GPU, где ехал вектор через вектор. Я как-то портировал генерацию шума Перлина на GPU и примерное понимание векторной нотации неплохо облегчило работу. Есть и минус — придется постоянно лезть в интернет, чтобы вспомнить тождества и правила линейной алгебры. После доказательства верности векторной нотации перейдем к дальнейшим преобразованиям:
![](https://habrastorage.org/files/ab7/6d6/f24/ab76d6f24d164ba690e82295c1cde3b6.png)
![](https://habrastorage.org/files/0d7/807/73b/0d780773b5e34470a8f73fbf258dd233.png)
Здесь использованы свойства транспонирования матриц — а именно транспонирование суммы и произведения. А также тот факт, что выражения
![](https://habrastorage.org/files/58a/62a/ad4/58a62aad427845b592a6864c0c3d381d.png)
![](https://habrastorage.org/files/ef2/def/500/ef2def50032a4cd1b7afc4a317f6131e.png)
![](https://habrastorage.org/files/75b/e04/b20/75be04b2008941e3a027422f57f66c36.png)
Константу можно представить как симметричную матрицу, следовательно:
![](https://habrastorage.org/files/08b/f4f/4d4/08bf4f4d40ae47aca630756ddbb6d504.png)
После преобразований и раскрытия скобок, приходит время решить-таки поставленную задачу — найти минимум данного выражения, учитывая
![](https://habrastorage.org/files/a77/498/ddc/a77498ddc5504ce8aac2b0e97372784d.png)
![](https://habrastorage.org/files/a77/498/ddc/a77498ddc5504ce8aac2b0e97372784d.png)
Итак,
![](https://habrastorage.org/files/aa4/dfe/ec8/aa4dfeec8dc348e68d8f661b27eb9d1b.png)
![](https://habrastorage.org/files/e3e/135/310/e3e135310be94b1082abbac0e4e84aee.png)
![](https://habrastorage.org/files/680/eca/b56/680ecab564ce4b379dcafbed9ecc2ca3.png)
![](https://habrastorage.org/files/9e7/3ad/81d/9e73ad81dc0c4cf398e26d8e234115aa.png)
![](https://habrastorage.org/files/146/694/43c/14669443c3fd4307979635139dc7d49b.png)
![](https://habrastorage.org/files/5b3/404/178/5b34041783234f8ba413ead773f47b17.png)
Часть
![](https://habrastorage.org/files/ec3/f2b/b5e/ec3f2bb5ed5f4ac89e6dc53368b5ca35.png)
Теперь в наличии все нужные формулы. Последовательность действий такая:
1) Сгенерировать набор экспериментальных данных.
2) Создать матрицу A.
3) Найти псевдообратную матрицу
![](https://habrastorage.org/files/bf3/a89/b1c/bf3a89b1c63f448d95359e5f1c859cb5.png)
4) Найти
![](https://habrastorage.org/files/a77/498/ddc/a77498ddc5504ce8aac2b0e97372784d.png)
После этого задача будет решена — у нас в распоряжении будут параметры прямой линии, наилучшим образом обобщающей экспериментальные данные. Иначе, у нас окажутся параметры для прямой, наилучшим образом выражающей линейную зависимость одной переменной от другой — именно это и требовалось.
generate_linear.py
import numpy as np
import matplotlib.pyplot as plt
TOTAL = 200
STEP = 0.25
def func(x):
return 0.2 * x + 3
def prediction(theta):
return theta[0] + theta[1] * x
def generate_sample(total=TOTAL):
x = 0
while x < total * STEP:
yield func(x) + np.random.uniform(-1, 1) * np.random.uniform(2, 8)
x += STEP
X = np.arange(0, TOTAL * STEP, STEP)
Y = np.array([y for y in generate_sample(TOTAL)])
Y_real = np.array([func(x) for x in X])
A = np.empty((TOTAL, 2))
A[:, 0] = 1
A[:, 1] = X
theta = np.linalg.pinv(A).dot(Y)
print(theta)
Y_prediction = A.dot(theta)
error = np.abs(Y_real - Y_prediction)
print("Error sum:", sum(error))
plt.plot(X, Y, 'bo')
plt.plot(X, Y_real, 'g', linewidth=2.0)
plt.plot(X, Y_prediction, 'r', linewidth=2.0)
plt.show()
И результаты:
![](https://habrastorage.org/files/7c2/d3d/f3b/7c2d3df3b13f4a46ade26320ec02717b.png)
Красная линия была предсказана и почти совпадает с зеленой «базой». Параметры в моем запуске равны: [3.40470411, 0.19575733]. Попробовать предсказать значения не выйдет, потому что пока неизвестно распределение ошибок модели. Все, что можно сделать, так это проверить, правда ли для данного случая МНК будет подходящим и лучшим методом для обобщения. Условий три:
1) Мат ожидание ошибок равно нулю.
2) Дисперсия ошибок — постоянная величина.
3) Отсутствует корреляция ошибок в разных измерениях. Ковариация равна нулю.
Для этого я дополнил пример вычислением необходимых величин и провел измерения дважды:
generate_linear.py
import numpy as np
import matplotlib.pyplot as plt
TOTAL = 200
STEP = 0.25
def func(x):
return 0.2 * x + 3
def prediction(theta):
return theta[0] + theta[1] * x
def generate_sample(total=TOTAL):
x = 0
while x < total * STEP:
yield func(x) + np.random.uniform(-1, 1) * np.random.uniform(2, 8)
x += STEP
X = np.arange(0, TOTAL * STEP, STEP)
Y = np.array([y for y in generate_sample(TOTAL)])
Y_real = np.array([func(x) for x in X])
A = np.empty((TOTAL, 2))
A[:, 0] = 1
A[:, 1] = X
theta = np.linalg.pinv(A).dot(Y)
print(theta)
Y_prediction = A.dot(theta)
error = Y - Y_prediction
error_squared = error ** 2
M = sum(error) / len(error)
M_squared = M ** 2
D = sum([sq - M_squared for sq in error_squared]) / len(error)
print("M:", M)
print("D:", D)
plt.plot(X, Y, 'bo')
plt.plot(X, Y_real, 'g', linewidth=2.0)
plt.plot(X, Y_prediction, 'r', linewidth=2.0)
plt.show()
![](https://habrastorage.org/files/0ab/b58/659/0abb586596ae42ffa2623c65056e9be8.png)
Неидеально, но все без обмана работает так, как и ожидалось.
Следующая часть.
Полный список библиотек для запуска примеров: numpy, matplotlib, requests.
Материалы, использованные в статье — https://github.com/m9psy/neural_nework_habr_guide