print "3. Обучение"
mlp.load()
try:
N = 10000
for p in range(N):
errSum = 0.0
for d in range(batch):
mlp.forwardPass(inputs[d])
mlp.backPass(inputs[d], targets[d])
errSum += mlp.calcError(inputs[d], targets[d])
print "Step", p, "error", errSum
except KeyboardInterrupt:
pass
mlp.save()
Всего было проведено около 50000 итераций на блоке размером 50 цифр, весь массив в 60000 цифр не использовался. Обучение сети заняло порядка 2х часов на компьютере с Core i7. Разумеется, этот проект учебный, и программа никак не оптимизирована по быстродействию. С использованием специальных фреймворков типа Keras тренировка такой сети занимает не более 5 минут.
Тестирование сети
И наконец, тестирование. В качестве теста, “от руки” была нарисована цифра “3”, которая получилась в виде массива примерно такой:
t = [[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ] +
[ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ]]
Следующий код выводить на экран цифру, и значения параметров выходного слоя:
for digit in t:
printDigit(digit)
mlp.forwardPass(digit)
mlp.printOutput()
Результат весьма интересен:
[0.019443, 0.0102247, 0.0091067, 0.467039, 0.0000103, 0.0150096, 0.0008709, 0.0004573, 0.655264, 0.0867915]
На тренировочных значениях сеть должна была выдавать “1” в том разряде, который соответствует “загаданному” числу. И хотя нигде явным образом это не планировалось и специально не программировалось, сеть выдала максимальные значения в тех разрядах массива, где “по ее мнению”, степень схожести максимальна. Как можно видеть, эти разряды соответствуют числам “3” и “8”, что визуально действительно похоже на нарисованное число. Строго говоря, результат не совсем верный, картинка больше похожа на “3” чем на ”8”, но и тренировка не была закончена полностью.
Для следующего теста число нейронов было увеличено до 128, а количество итераций обучения было увеличено до 75000.
Результаты теста на том же массиве:
[0.0044085, 0.219943, 0.0118179, 0.816858, 0.0002372, 0.06267359, 0.0008674, 0.00020319, 0.55439027, 0.00061541]
Максимальное значение теперь действительно соответствует числу “3”, можно сказать что сеть работает как задумывалось.
Для тех кто захочет поэкспериментировать самостоятельно, исходный текст программы и база чисел MNIST находятся в архиве, ссылка на который есть в начале книги.
21. Фракталы
Фракталы - интересные математические объекты, которые долгое время не замечались математиками. В 1872 году, объекты такого типа впервые описал немецкий математик Карл Вейерштрасс, “придумавший” функцию следующего вида:
Это непрерывная функция, но при этом не являющаяся гладкой, для нее невозможно вычислить производную ни в одной из точек.
В Википедии можно найти ее график:
Во времена Вейерштрасса математики назвали такую функцию “оскорблением здравого смысла”, практической применимости не мог найти никто. Лишь через 100 лет, в историческом плане совсем недавно, в 1975 году, математик Мандельброт ввел термин “фрактал”. Фракталы стали широко известны после выхода в 1977 году его книги “Фрактальная геометрия природы” - как оказалось, такие структуры распространены в природе гораздо чаще, чем это можно представить. От ветвей деревьев или рисунка береговой линии, до сосудов человека или колебаний курса акций - все эти процессы имеют природу, схожую с фрактальной.
Основное свойство фракталов - самоподобие, увеличенный фрагмент повторяется большое (в идеале бесконечное) число раз. Простейший пример, знакомый каждому - ветви дерева. Возьмем линию, которая через определенное расстояние делится надвое, для каждой из половинок повторим вышеуказанное правило. Получим знакомый рисунок:
Другим примером служит так называемый “парадокс береговой линии”. При измерении длины государственной границы между Испанией и Португалией, выяснилось, что по измерениям из Португалии, длина границы составила 987км, а по измерениям с Испанской стороны - 1214км. Т.к. противоречие было налицо, им заинтересовался английский математик Льюис Ричардсон, который выяснил, что все дело в масштабе - чем меньше масштаб, тем больше получается длина. Поразительным оказалось то, что при теоретически бесконечном масштабе, длина линии также будет бесконечной!
Впрочем, фигуры такого типа были известны и раньше (хотя их рассматривали скорее как математический курьез), например описанная в 1904 году кривая Коха. Построить ее весьма просто: возьмем линию, разделим ее в центре равносторонним треугольником, для каждой новой линии повторим процесс:
Эта фигура теоретически также имеет конечную площадь, но при этом бесконечную длину края. Также как и функция Вейерштрасса, кривая Коха нигде не дифференцируема. Также очевидно, что при увеличении любого фрагмента кривой Коха, он не будет отличаться от “оригинала”, деление будет продолжаться и дальше.
Если замкнуть 3 такие линии, получится так называемая “снежинка Коха”. Нарисовать ее несложно на языке Python, благодаря встроенной библиотеке рисования Turtle. Она позволяет управляя виртуальной “черепашкой”, рисовать примитивы простыми командами, типа “повернуть на угол” или “сдвинуться на расстояние”.
Для рисования линии Коха, нам потребуются всего 3 команды: сдвинуться вперед, повернуть на 60 градусов, и повернуть на -60 градусов. Повторив процедуру 3 раза, мы получим “снежинку Коха”.
Код на языке Python выглядит так:
import turtle
def koch(size, order):
if order > 0:
koch(size/3, order - 1)
turtle.left(60)
koch(size/3, order - 1)
turtle.right(120)
koch(size/3, order - 1)
turtle.left(60)
koch(size/3, order - 1)
else:
turtle.forward(size)
turtle.ht()
turtle.speed(20)
for i in range(3):
koch(size=400, order=4)
turtle.right(120)
turtle.exitonclick()
В результате работы программы мы получаем следующую картинку:
Можно увеличив количество итераций и размер картинки, убедиться что шаблон повторяется.
Может возникнуть вопрос, как длина линии может быть бесконечной при конечной длине. Примерной аналогией может быть сумма ряда:
S = 0.9 + 0.09 + 0.009 + …
Как нетрудно догадаться, сам по себе ряд бесконечный, но его сумма стремится ко вполне определенному числу 0.999999… = 1.
“Снежинка Коха” интересна своей простотой, но есть и более сложные варианты фракталов. Рассмотрим множество Мандельброта, которое строится по следующему алгоритму: для каждой точки c=x + j*y на комплексной плоскости, эта точка попадает в множество при условии что ряд Zn+1 = Zn2 + c не расходится при z0 = 0.
Рассмотрим пример.
При c = (0,0) = 0 + 0j, ряд очевидно, всегда равен нулю, т.е. не расходится, значит точка (0,0) попадает в множество.
При с = (0.5, 0.5) = 0.5 + 0.5j, получаем следующие значения:
Z0 = 0
Z1 = Z0 + c = 0.5+0.5j
Z2 = Z1 + c = 0.5+1j
Z3 = Z2 + c = -0.25+1.5j
Z4 = Z3 + c = -1.6875-0.25j
Z5 = Z4 + c = 3.28515625+1.34375j
Z6 = Z5 + c = 9.48658752+9.32885j
Легко видеть, что ряд расходящийся, числа увеличиваются, значит (0.5, 0.5) не попадает в множество.
При с = (0.25, 0.25) = 0.25 + 0.25j, имеем следующий ряд:
Z0 = 0
Z1 = Z0 + c = 0.25+0.25j
Z2 = Z1 + c = 0.25+0.375j
Z3 = Z2 + c = 0.171875+0.4375j
Z4 = Z3 + c = 0.088134+0.400390625j
Z5 = Z4 + c = 0.09745508+0.32057666j
Z6 = Z5 + c = 0.15672809+0.31248365j
Z7 = Z6 + c = 0.17691766+0.34794993j
Z8 = Z7 + c = 0.160230+0.37311697j
Z9 = Z8 + c = 0.1364575+0.36956959j
Как можно видеть, ряд не расходится, т.е. точка (0.25, 0.25) попадает в множество.
Разумеется, вручную делать такие проверки было бы крайне неудобно, собственно это одна из основных причин, по которой фракталы не были известны до появления компьютеров. Чтобы заметить какие-либо закономерности фрактальной природы, необходима возможность их автоматического рисования. Кстати, сам Мандельброт работал в IBM и имел доступ к весьма мощным компьютерам своего времени.
На языке Python проверку попадания точки в множество легко записать в виде функции. Для нас удобно то, что Python умеет работать с комплексными числами, что делает запись кода более короткой.
Сама функция имеет следующий вид:
def countMandelbrotIterationsForPt(pt):
z = 0
c = pt
threshold = 64
for iteration in xrange(threshold):
z = z*z + c
if abs(z) > 4:
break
return iteration
Здесь вычисляется 64 итерации, которых вполне достаточно чтобы определить, является ли ряд расходящимся или нет.
Чтобы сохранить весь фрактал, нужно перебрать все точки в диапазоне [-2, 2], программа, сохраняющая фрактал в файл, приведена ниже:
from PIL import Image
points = 1000
img = Image.new('RGB', (2*points,2*points), "black")
pixels = img.load()
# Range.X: -2..2,
# Range.Y: -2..2
for ix in xrange(-points, points, 1):
for iy in xrange(-points, points, 1):
pt = complex(2.0*ix/points, 2.0*iy/points)
i = countMandelbrotIterationsForPt(pt)
if i > 16:
colR, colG, colB = 4*i, 4*i, 0
if colR >= 255: colR = 255
if colB >= 255: colB = 255
if colB >= 255: colB = 255
img_x = points + ix
img_y = points + iy
pixels[img_x, img_y] = (colR, colG, colB)
if ix % 10 is 0:
print "Done: {}%".format(100.0*(ix + points)/(2*points))
img.save("fractal.png")
Как можно видеть, программа содержит 2 вложенных цикла ix, iy, затем значение преобразуются в комплексное число, для которого и выполняется описанная выше функция проверки.
Результат выполнения программы для 1000 точек, показан на рисунке:
Если в несколько раз увеличить количество точек, можно увидеть структуру верхней части более детально:
Немного изменив формулу, можно получить другие виды фракталов. Например, множество Жюлиа, описывается также, но Z0 = pt, и c = const. Казалось бы, небольшое отличие, приводит к совершенно другому рисунку фрактала:
Кстати, этот рисунок напоминает сорт цветной капусты “Романеско”:
Наконец, если в формуле фрактала Мандельброта Zn+1 = Zn2 + c, вычислять абсолютное значение Z*Z в виде (|a| + j|b|)*(|a| + j|b|), мы получим фрактал с названием “горящий корабль”: