Случайны выбор дневника Раскрыть/свернуть полный список возможностей


Найдено 104590 сообщений
Cообщения с меткой

математика - Самое интересное в блогах

Следующие 30  »
nataliij

Совершенное число 108

Суббота, 27 Августа 2016 г. 16:04 (ссылка)

Это цитата сообщения Мираж_ок Оригинальное сообщение


dzen (700x437, 67Kb)



108 – это мистическое число из ведической нумерологии, точнее говоря из ведической культуры. Ведическая культура самая древняя на планете и насчитывает тысячи различных писаний из самых различных сфер жизни: религии, экономики, общества, семьи, здоровья, быта, самопознания. Число 108 в Ведах – считается магическим числом совершенства и успеха.



Совершив в каком-либо виде деятельности 108 попыток: тренировок, повторений и т.п., человек достигает определённой ступени совершенства. Это связано с тем, что человеческая память состоит из двух частей: временной и постоянной. Временная память предназначена для кратковременного хранения информации в период пока выполняется действие, постоянная память сохраняет информацию в течение всей нашей жизни. Повторив длинное число, например свой номер телефона 108 раз – информация о нём навсегда помещается во внутреннюю память. По этой причине классические чётки состоят из 108 бусин, таким образом повторённая на них 108 раз молитва становится частью постоянной памяти.



Число 108 – это совершенное число, оно представляет собой все бытие. И вот некоторые аргументы, показывающие, почему это так:



Читать далее



 



 

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

[Из песочницы] Алгоритм Левенберга — Марквардта для нелинейного метода наименьших квадратов и его реализация на Python

Пятница, 26 Августа 2016 г. 19:16 (ссылка)





Нахождение экстремума (минимума или максимума) целевой функции является важной задачей в математике и её приложениях (в частности, в машинном обучении есть задача curve-fitting). Наверняка каждый слышал о методе наискорейшего спуска (МНС) и методе Ньютона (МН). К сожалению, эти методы имеют ряд существенных недостатков, в частности — метод наискорейшего спуска может очень долго сходиться в конце оптимизации, а метод Ньютона требует вычисления вторых производных, для чего требуется очень много вычислений.



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





Алгоритм Левенберга — Марквардта используется для решения нелинейного метода наименьших квадратов. Статья содержит:




  • объяснение алгоритма

  • объяснение методов: наискорейшего спуска, Ньтона, Гаусса-Ньютона

  • приведена реализация на Python с исходниками на github

  • сравнение методов



В коде использованы дополнительные библиотеки, такие как numpy, matplotlib. Если у вас их нет — очень рекомендую установить их из пакета Anaconda for Python



Зависимости



Алгоритм Левенберга — Марквардта опирается на методы, приведённые в блок-схеме







Поэтому, сначала, необходимо изучить их. Этим и займёмся



Определения






  • inline_formula — наша целевая функция. Мы будем минимизировать inline_formula. В этом случае, inline_formula является функцией потерь

  • inline_formula — градиент функции inline_formula в точке inline_formula

  • inline_formulainline_formula, при котором inline_formula является локальным минимумом, т.е. если существует проколотая окрестность inline_formula, такая что inline_formula

  • inline_formula — глобальный минимум, если inline_formula, т.е. inline_formula не имеет значений меньших, чем inline_formula

  • inline_formulaматрица Якоби для функции inline_formula в точке inline_formula. Т.е. это таблица всех частных производных первого порядка. По сути, это аналог градиента для inline_formula, так как в этом случае мы имеем дело с отображением из inline_formula-мерного вектора в inline_formula-мерный, поэтому нельзя просто посчитать первые производные по одному измерению, как это происходит в градиенте. Подробнее

  • inline_formulaматрица Гессе (матрица вторых производных). Необходима для квадратичной аппроксимации



Выбор функции





В математической оптимизации есть функции, на которых тестируются новые методы. Одна из таких функция — Функция Розенброка. В случае функции двух переменных она определяется как





Я принял inline_formula.Добавлен множитель 0.5 перед первой частью для удобства. Т.е. функция имеет вид:





Будем рассматривать поведение функции на интервале inline_formula





Эта функция определена неотрицательно, имеет минимум inline_formula в точке inline_formula



В коде проще инкапсулировать все данные о функции в один класс и брать класс той функции, которая потребуется. Результат зависит от начальной точки оптимизации. Выберем её как inline_formula. Как видно из графика, в этой точке функция принимает наибольшее значение на интервале.



functions.py



class Rosenbrock:
initialPoint = (-2, -2)
camera = (41, 75)
interval = [(-2, 2), (-2, 2)]

"""
Целевая функция
"""
@staticmethod
def function(x):
return 0.5*(1-x[0])**2 + 0.5*(x[1]-x[0]**2)**2

"""
Для нелинейного МНК - возвращает вектор-функцию r
"""
@staticmethod
def function_array(x):
return np.array([1 - x[0] , x[1] - x[0] ** 2]).reshape((2,1))

@staticmethod
def gradient(x):
return np.array([-(1-x[0]) - (x[1]-x[0]**2)*2*x[0], (x[1] - x[0]**2)])

@staticmethod
def hesse(x):
return np.array(((1 -2*x[1] + 6*x[0]**2, -2*x[0]), (-2 * x[0], 1)))

@staticmethod
def jacobi(x):
return np.array([ [-1, 0], [-2*x[0], 1]])

"""
Векторизация для отрисовки поверхности
Детали: http://www.mathworks.com/help/matlab/matlab_prog/vectorization.html
"""
@staticmethod
def getZMeshGrid(X, Y):
return 0.5*(1-X)**2 + 0.5*(Y - X**2)**2


Метод наискорейшего спуска (Steepest Descent)



Сам метод крайне прост. Принимаем inline_formula, т.е. целевая функция совпадает с заданной.



Нужно найти inline_formula — направление наискорейшего спуска функции inline_formula в точке inline_formula.



inline_formula может быть линейно аппроксимирована в точке inline_formula:







где inline_formula — угол между вектором inline_formula. inline_formula следует из скалярного произведения



Так как мы минимизируем inline_formula, то чем больше разница в inline_formula, тем лучше. При inline_formula выражение будет максимально( inline_formula, норма вектора всегда неотрицательна), а inline_formula будет только если вектора inline_formula будут противоположны, поэтому





Направление у нас верное, но делая шаг длиной inline_formula можно уйти не туда. Делаем шаг меньше:





Теоретически, чем меньше шаг, тем лучше. Но тогда пострадает скорость сходимости. Рекомендуемое значение inline_formula



В коде это выглядит так: сначала базовый класс-оптимизатор. Передаём всё, что понадобится в дальнейшем (матрицы Гессе, Якоби, сейчас не нужны, но понадобятся для других методов)



class Optimizer:
def _init_(self, function, initialPoint, gradient=None, jacobi=None, hesse=None,
interval=None, epsilon=1e-7, function_array=None, metaclass=ABCMeta):
self.function_array = function_array
self.epsilon = epsilon
self.interval = interval
self.function = function
self.gradient = gradient
self.hesse = hesse
self.jacobi = jacobi
self.name = self.class.name.replace('Optimizer', '')
self.x = initialPoint
self.y = self.function(initialPoint)

"Возвращает следующую координату по ходу оптимизационного процесса"
@abstractmethod
def next_point(self):
pass

"""
Движемся к следующей точке
"""
def move_next(self, nextX):
nextY = self.function(nextX)
self.y = nextY
self.x = nextX
return self.x, self.y


Код самого оптимизатора:



class SteepestDescentOptimizer(Optimizer):
...
def next_point(self):
nextX = self.x - self.learningRate * self.gradient(self.x)
return self.move_next(nextX)


Результат оптимизации:






























Итерация X Y Z
25 0.383 -0.409 0.334
75 0.693 0.32 0.058
532 0.996 0.990 inline_formula


Бросается в глаза: как быстро шла оптимизация в 0-25 итерациях, в 25-75 уже медленне, а в конце потребовалось 457 итераций, чтобы приблизиться к нулю вплотную. Такое поведение очень свойственно для МНС: очень хорошая скорость сходимости вначале, плохая в конце.



Метод Ньютона



Сам Метод Ньютона ищет корень уравнения, т.е. такой inline_formula, что inline_formula. Это не совсем то, что нам нужно, т.к. функция может иметь экстремум не обязательно в нуле.



А есть ещё Метод Ньютона для оптимизации. Когда говорят о МН в контексте оптимизации — имеют в виду его. Я сам, учась в институте, спутал по глупости эти методы и не мог понять фразу «Метод Ньютона имеет недостаток — необходимость считать вторые производные».



Рассмотрим для inline_formula



Принимаем inline_formula, т.е. целевая функция совпадает с заданной.



Разлагаем inline_formula в ряд Тейлора, только в отличии от МНС нам нужно квадратичное приближение:





Несложно показать, что если inline_formula, то функция не может иметь экстремум в inline_formula. Точка inline_formula в которой inline_formula называется стационарной.



Продифференцируем обе части по inline_formula. Наша цель, чтобы inline_formula, поэтому решаем уравнение:





inline_formula — это направление экстремума, но оно может быть как максимумом, так и минимумом. Чтобы узнать — является ли точка inline_formula минимумом — нужно проанализировать вторую производную. Если inline_formula, то inline_formula является локальным минимумом, если inline_formula — максимумом.



В многомерном случае первая производная заменяется на градиент, вторая — на матрицу Гессе. Делить матрицы нельзя, вместо этого умножают на обратную (соблюдая сторону, т.к. коммутативность отсутствует):





Аналогично одномерному случаю — нужно проверить, правильно ли мы идём? Если матрица Гессе положительно определена, значит направление верное, иначе используем МНС.



В коде:



def is_pos_def(x):
return np.all(np.linalg.eigvals(x) > 0)

class NewtonOptimizer(Optimizer):
def next_point(self):
hesse = self.hesse(self.x)
# Если H - положительно определённая - Ок, иначе мы идём не в том направлении, используем МНС
if is_pos_def(hesse):
hesseInverse = np.linalg.inv(hesse)
nextX = self.x - self.learningRate * np.dot(hesseInverse, self.gradient(self.x))
else:
nextX = self.x - self.learningRate * self.gradient(self.x)

return self.move_next(nextX)


Результат:




























Итерация X Y Z
25 -1.49 0.63 4.36
75 0.31 -0.04 0.244
179 0.995 -0.991 inline_formula


Сравните с МНС. Там был очень сильный спуск до 25 итерации (практически упали с горы), но потом сходимость сильно замедлилась. В МН, напротив, мы сначала медленно спускаемся с горы, но затем движемся быстрее. У МНС ушло с 25 по 532 итерацию, чтобы дойти до нуля с inline_formula. МН же оптимизировал inline_formula за 154 последних итераций.



Это частое поведение: МН обладает квадратичной скоростью сходимости, если начинать с точки, близкой к локальному экстремуму. МНС же хорошо работает далеко от экстремума.



МН использует информацию кривизны, что было видно на рисунке выше (плавный спуск с горки). Ещё пример, демонстрирующий эту идею: на рисунке ниже красный вектор — это направление МНС, а зелёный — МН







[Нелинейный vs линейный] метод наименьших квадратов



В МНК у нас есть модель inline_formula, имеющая inline_formula параметров, которые настраиваются так, чтобы минимизировать inline_formula, где inline_formulainline_formula-е наблюдение.



В линейном МНК у нас есть inline_formula уравнений, каждое из которых мы можем представить как линейное уравнение





Для линейного МНК решение единственно. Существуют мощные методы, такие как QR декомпозиция, SVD декомпозиция, способные найти решение для линейного МНК за 1 приближённое решение матричного уравнения inline_formula.



В нелинейном МНК параметр inline_formula может сам быть представлен функцией, например inline_formula. Так же, может быть произведение параметров, например inline_formula и т.д.



Здесь же приходится находить решение итеративно, причём решение зависит от выбора начальной точки.



Методы ниже имеют дело как раз с нелинейным случаем. Но, сперва, рассмотрим нелиненый МНК в контексте нашей задачи — минимизации функции





Ничего не напоминает? Это как раз форма МНК! Введём вектор-функцию inline_formula





и будем подбирать inline_formula так, чтобы решить систему уравнений (хотя бы приближённо):





Тогда нам нужна мера — насколько хороша наша аппроксимация. Вот она:





Я применил обратную операцию: подстроил вектор-функцию inline_formula под целевую inline_formula. Но можно и наоборот: если дана вектор-функция inline_formula, строим inline_formula из (5). Например:





Напоследок, один очень важдный момент. Должно выполняться условие inline_formula, иначе методом пользоваться нельзя. В нашем случае условие выполняется



Метод Гаусса-Ньютона



Метод основан на всё той же линейной аппроксимации, только теперь имеем дело с двумя функциями:





Далее делаем то же, что и в методе Ньютона — решаем уравнение (только для inline_formula):





Несложно показать, что вблизи inline_formula:





Код оптимизатора:



class NewtonGaussOptimizer(Optimizer):
def next_point(self):
# Решаем (J_t * J)d_ng = -J*f
jacobi = self.jacobi(self.x)
jacobisLeft = np.dot(jacobi.T, jacobi)
jacobiLeftInverse = np.linalg.inv(jacobisLeft)
jjj = np.dot(jacobiLeftInverse, jacobi.T) # (J_t * J)^-1 * J_t
nextX = self.x - self.learningRate * np.dot(jjj, self.function_array(self.x)).reshape((-1))
return self.move_next(nextX)


Результат превысил мои ожидания. Всего за 3 итерации мы пришли в точку inline_formula. Чтобы продемонстрировать траекторию движения я уменьшил learningrate до 0.2







Алгоритм Левенберга — Марквардта



Он основан на одной из версий Методе Гаусса-Ньютона ("damped version" ):





Для больших inline_formula получается метод наискорейшего спуска, для маленьких — метод Ньютона.

Сам алгоритм в процессе оптимизации подбирает нужный inline_formula на основе gain ratio, определяющийся как:





Если inline_formula, то inline_formula — хорошая аппроксимация для inline_formula, иначе — нужно увеличить inline_formula.



Начальное значение inline_formula задаётся как inline_formula, где inline_formula — элементы матрицы inline_formula.



inline_formula рекомендовано назначать за inline_formula. Критерием остановки является достижение глобального минимуму, т.е. inline_formula





В оптимизаторах я не реализовывал критерий остановки — за это отвечает пользователь. Мне нужно было только движение к следующей точке.



class LevenbergMarquardtOptimizer(Optimizer):
def __init__(self, function, initialPoint, gradient=None, jacobi=None, hesse=None,
interval=None, function_array=None, learningRate=1):
self.learningRate = learningRate
functionNew = lambda x: np.array([function(x)])
super().__init__(functionNew, initialPoint, gradient, jacobi, hesse, interval, function_array=function_array)
self.v = 2
self.alpha = 1e-3
self.m = self.alpha * np.max(self.getA(jacobi(initialPoint)))

def getA(self, jacobi):
return np.dot(jacobi.T, jacobi)

def getF(self, d):
function = self.function_array(d)
return 0.5 * np.dot(function.T, function)

def next_point(self):
if self.y==0: # Закончено. Y не может быть меньше нуля
return self.x, self.y

jacobi = self.jacobi(self.x)
A = self.getA(jacobi)
g = np.dot(jacobi.T, self.function_array(self.x)).reshape((-1, 1))
leftPartInverse = np.linalg.inv(A + self.m * np.eye(A.shape[0], A.shape[1]))
d_lm = - np.dot(leftPartInverse, g) # moving direction
x_new = self.x + self.learningRate * d_lm.reshape((-1)) # линейный поиск
grain_numerator = (self.getF(self.x) - self.getF(x_new))
gain_divisor = 0.5* np.dot(d_lm.T, self.m*d_lm-g) + 1e-10
gain = grain_numerator / gain_divisor
if gain > 0: # Ок, хорошая оптимизация
self.move_next(x_new) # ok, шаг принят
self.m = self.m * max(1 / 3, 1 - (2 * gain - 1) ** 3)
self.v = 2
else:
self.m *= self.v
self.v *= 2

return self.x, self.y


Результат получился тоже хороший:


























Итерация X Y Z
0 -2 -2 22.5
4 0.999 0.998 inline_formula
11 1 1 0


При learningrate =0.2:



Сравнение методов







































Название метода Целевая функция Достоинства Недостатки Сходимость
Метод наискорейший спуск дифференцируемая -широкий круг применения

-простая реализация



-низкая цена одной итерации

-глобальный минимум ищется хуже, чем в остальных методах



-низкая скорость сходимости вблизи экстремума

локальная
Метод Нютона дважды дифференцируемая -высокая скорость сходимости вблизи экстремума



-использует информацию о кривизне

-функция должны быть дважды дифференцируема



-вернёт ошибку, если матрица Гессе вырождена (не имеет обратной)



-есть шанс уйти не туда, если находится далеко от экстремума

локальная
Метод Гаусса-Нютона нелинейный МНК -очень высокая скорость сходимости



-хорошо работает с задачей curve-fitting

-колонки матрицы J должны быть линейно-независимы



-налагает ограничения на вид целевой функции



локальная
Алгоритм Левенберга — Марквардта нелинейный МНК -наибольная устойчивость среди рассмотренных методов



-наибольшие шансы найти глобальный экстремум



-очень высокая скорость сходимости (адаптивная)



-хорошо работает с задачей curve-fitting

-колонки матрицы J должны быть линейно-независимы



-налагает ограничения на вид целевой функции



-сложность в реализации

локальная


Несмотря на хорошие результаты в конкретном примере рассмотренные методы не гарантируют глобальную сходимость (найти которую — крайне трудная задача). Примером из немногих методов, позволяющих всё же достичь этого, является алгоритм basin-hopping



Совмещённый результат (специально понижена скорость последних двух методов):







» Исходники можно скачать с github



» Источники




  1. K. Madsen, H.B. Nielsen, O. Tingleff (2004): Methods for non-linear least square

  2. Florent Brunet (2011): Basics on Continuous Optimization

  3. Least Squares Problems


Original source: habrahabr.ru.

https://habrahabr.ru/post/308626/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
Veta_160

Учимся считать

Пятница, 26 Августа 2016 г. 20:20 (ссылка)








Положите на тарелки угощение.
Количество угощения должно соответствовать цифре
указанной рядом с друзьями Хрюши.
1 (600x512, 192Kb)
Пошли играть2 (37x45, 10Kb)

Здесь еще игры→

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Математика для искусственных нейронных сетей для новичков, часть 3 — градиентный спуск продолжение

Пятница, 26 Августа 2016 г. 14:41 (ссылка)

Часть 2 — градиентный спуск начало



В предыдущей части я начал разбор алгоритма оптимизации под названием градиентный спуск. Предыдущая статья оборвалась на писании варианта алгоритма под названием пакетный градиентный спуск.



Существует и другая версия алгоритма — стохастический градиентный спуск. Стохастический = случайный.



Повторять, пока не сойдется



{

for i in train_set

{



}

}



Также напомню как выглядит пакетный:



Повторять, пока не сойдется

{



}



Формулы похожи, но, как видно, пакетный градиентный спуск вычисляет один шаг, используя сразу весь набор данных, тогда как стохастический за шаг использует только 1 элемент. Можно два этих варианта скрестить, получив мини-пакетный (mini-batch) спуск, который за раз обрабатывает, к примеру, 100 элементов, а не все или один.



Два этих варианта ведут себя похоже, но не одинаково. Пакетный спуск действительно следует в направлении наискорейшего спуска, тогда как стохастический, используя только один элемент из обучающей выборки, не может верно вычислить градиент для всей выборки. Это различие проще пояснить графически. Для этого я модифицирую код из первой части, в котором вычислялись коэффициенты линейной регрессии. Функция стоимости для нее выглядит следующим образом:



Как видно, это немного вытянутый параболоид. И также его «вид сверху», где крестом отмечен истинный минимум, найденный аналитически.



Сперва рассмотрим, как ведет себя пакетный спуск:



Код
def batch_descent(A, Y, speed=0.001):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
theta.reshape((len(theta), 1))
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
derivatives = [0] * len(theta)
# ---------------------------------------------
for j in range(len(theta)):
summ = 0
for i in range(len(Y)):
summ += (Y[i] - A[i]@theta) * A[i][j]
derivatives[j] = summ
# Выполнение требования одновремменности
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
# ---------------------------------------------
current_cost = cost_function(A, Y, theta)
print("Batch cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
return theta




Пакетный-анимация




Из-за того, что параболоид вытянутый, по его «дну» проходит «овраг», в который мы попадаем. Из-за этого последние шаги вдоль этого оврага очень маленькие, но тем не менее рано или поздно градиентный спуск доберется до минимума. Спуск происходит по линии антиградиента, каждый шаг приближаясь к минимуму.



Теперь та же самая функция, но для стохастического спуска:



Код
def stochastic_descent(A, Y, speed=0.1):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
# --------------------------------------
# for i in range(len(Y)):
i = np.random.randint(0, len(Y))
derivatives = [0] * len(theta)
for j in range(len(theta)):
derivatives[j] = (Y[i] - A[i]@theta) * A[i][j]
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
current_cost = cost_function(A, Y, theta)
print("Stochastic cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
# --------------------------------------
current_cost = cost_function(A, Y, theta)
return theta




В определении сказано, что выбирается только один элемент — в этом коде каждый последующий элемент выбирается случайным образом.



Стохастический-анимация




Как видно, в случае стохастического варианта, спуск идет не по линии антиградиента, а вообще непонятно как — каждый шаг отклоняясь в случайную сторону. Может показаться, что такими случайными дергаными движениями к минимуму можно прийти только случайно, однако было доказано, что стохастический градиентный спуск сходится почти наверное. Пару ссылок, например.



Весь код целиком
import numpy as np
import matplotlib.pyplot as plt

TOTAL = 200
STEP = 0.25
EPS = 0.1
INITIAL_THETA = [9, 14]


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


def cost_function(A, Y, theta):
return (Y - A@theta).T@(Y - A@theta)


def batch_descent(A, Y, speed=0.001):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
theta.reshape((len(theta), 1))
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
derivatives = [0] * len(theta)
# ---------------------------------------------
for j in range(len(theta)):
summ = 0
for i in range(len(Y)):
summ += (Y[i] - A[i]@theta) * A[i][j]
derivatives[j] = summ
# Выполнение требования одновремменности
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
# ---------------------------------------------
current_cost = cost_function(A, Y, theta)
print("Batch cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
return theta


def stochastic_descent(A, Y, speed=0.1):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
# --------------------------------------
# for i in range(len(Y)):
i = np.random.randint(0, len(Y))
derivatives = [0] * len(theta)
for j in range(len(theta)):
derivatives[j] = (Y[i] - A[i]@theta) * A[i][j]
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
# --------------------------------------
current_cost = cost_function(A, Y, theta)
print("Stochastic cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
return theta

X = np.arange(0, TOTAL * STEP, STEP)
Y = np.array([y for y in generate_sample(TOTAL)])

# Нормализацию вкрячил, чтобы парабалоид красивый был
X = (X - X.min()) / (X.max() - X.min())

A = np.empty((TOTAL, 2))
A[:, 0] = 1
A[:, 1] = X

theta = np.linalg.pinv(A).dot(Y)
print(theta, cost_function(A, Y, theta))

import time
start = time.clock()
theta_stochastic = stochastic_descent(A, Y, 0.001)
print("St:", time.clock() - start, theta_stochastic)

start = time.clock()
theta_batch = batch_descent(A, Y, 0.001)
print("Btch:", time.clock() - start, theta_batch)




На 200 элементах разницы в скорости почти никакой нет, однако, увеличив количество элементов до 2000 (что тоже очень мало) и подкорректировав скорость обучения, стохастический вариант бьет пакетный, как хочет. Однако, в силу стохастической природы, иногда метод промахивается, осциллируя возле минимума без возможности остановиться. Как-то так:







Этот факт делает неприменимой чистую реализацию. Чтобы как-то призвать к порядку и снизить «случайность» можно снизить скорость обучения. На практике применяют mini-batch вариацию — от стохастической она отличается тем, что вместо одного случайно выбранного элемента выбирают больше одного.



О разнице, плюсах и минусах данных двух подходов написано достаточно много, вкратце подведу итог:



— Пакетный спуск хорош для строго выпуклых функций, потому что уверенно стремится к минимуму глобальному или локальному.

— Стохастический в свою очередь лучше работает на функциях с большим количеством локальных минимумов — каждый шаг есть шанс, что очередное значение «выбьет» из локальной ямы и конечное решение будет более оптимальным, нежели для пакетного спуска.

— Стохастический вычисляется быстрее — на каждом шаге нужны не все элементы из выборки. Вся выборка целиком может не влезть в память. Но требуется больше шагов.

— Для стохастического легко добавить новые элементы во время работы («онлайн» обучение).

— В случае mini-batch, можно также векторизовать код, что значительно ускорит его выполнение.



Также у градиентного спуска существует множество модификаций — momentum, наискорейшего спуска, усреднение, Adagrad, AdaDelta, RMSProp и другие. Здесь можно посмотреть короткий обзор некоторых. Частенько они используют значения градиента с предыдущих шагов или автоматически вычисляют наилучшее значение скорости для данного шага. Использование этих методов для простой гладкой функции МНК не имеет особого смысла, но в случае нейронных сетей и сетей с большим количеством слоев\нейронов, функция стоимости становится совсем грустной и градиентный спуск может застрять в локальной яме, так и не достигнув оптимального решения. Для таких проблем подходят методы на стероидах. Вот пример функции простой для минимизации (двумерная линейная регрессия с МНК):



И пример нелинейной функции:







Градиентный спуск — метод оптимизации первого порядка (первая производная). Также существует много методов второго порядка — для них необходимо вычислять вторую производную и строить гессиан (довольно затратная операция — ). Например, градиентный спуск второго порядка (скорость обучения заменили на гессиан), BFGS, сопряженные градиенты, метод Ньютона и еще огромное количество других методов. В общем, оптимизация — это отдельный и очень широкий пласт проблем. Впрочем, вот пример (правда, всего лишь презентация) работы + видео Яна Лекуна, в который он говорит, что можно не парится и просто использовать градиентные методы. Даже учитывая, что презентация 2007 года, многие последние эксперименты с большими ИНС использовали градиентные методы. Например.



На голых циклах далеко не уедешь — код нуждается в векторизации. Основной алгоритм для векторизации — пакетный градиентный спуск, с оговоркой, что , где k — количество элементов в тестовой выборке. Таким образом векторизация подходит для mini-batch метода. Как и в прошлый раз я выпишу все в раскрытых векторах. Обратите внимание что первая матрица транспонирована —







Для доказательства, пройдем пару шагов в обратную сторону:











В предыдущей формуле, в каждой строке индекс j зафиксирован, а i — изменяется от 1 до n. Свернув сумму:







Это выражение точно такое же, что и в определении градиентного спуска. Наконец, завершающий шаг — сворачивание векторов и матриц:







Стоимость одного такого шага — , где n — количество элементов, p — количество признаков. Много лучше . Также встречается выражение, тождественное этому:







Обратите внимание, что поменялись местами предсказанное значение и реальное, что привело к изменению знака перед скоростью обучения.



» Для запуска примеров необходимы: numpy, matplotlib.

» Материалы, использованные в статье — github.com/m9psy/neural_network_habr_guide
Original source: habrahabr.ru (comments, light).

https://habrahabr.ru/post/308604/

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Навигатор 2ГИС: Экстраполяция позиции автомобиля

Пятница, 26 Августа 2016 г. 10:26 (ссылка)





В приложении 2ГИС теперь есть навигатор. Мы научились «ехать» по треку, озвучивать манёвры, автоматически перестраивать маршрут, рассчитывать время в пути, доводить пользователя до входа в здание или организацию, учитывая заборы и шлагбаумы, — и всё это в честном офлайне. Пробки (вот разве что для них нужен интернет), разведённые мосты и перекрытые улицы учитываем давно. Пока в нашем навигаторе — необходимый минимум. Чуть позже научим его предупреждать о слишком высокой скорости, лежачих полицейских и камерах ГИБДД, настроим ночной режим, сделаем маршруты по платным и грунтовым дорогам опциональными. Чтобы воспользоваться им, нужно обновить 2ГИС в своем смартфоне или скачать в AppStore или Windows Store. Для Android обновление выходит постепенно, начиная с 22 августа (будет доступно на всю аудиторию к сентябрю).



А сегодня расскажем, как навигатор 2ГИС предугадывает положение автомобиля и плавно перемещает стрелочку по маршруту. Ведь именно качество ведения пользователя по маршруту определяет эргономику интерфейса любого современного навигатора, простоту ориентирования на местности и своевременность совершения манёвров.



Большую часть времени водитель автомобиля вынужден следить за дорогой, поэтому даже беглого взгляда на экран устройства с программой-навигатором должно быть достаточно, чтобы получить максимально точную и своевременную информацию о собственном местоположении относительно маршрута и окружающих объектов. Эта с виду простая функциональность требует решения множества технических проблем для своей реализации. Некоторые из них мы и рассмотрим.



Маркер GPS и маршрут



Чтобы обозначить местоположение пользователя на карте, многие навигаторы (и наш не стал исключением) используют специальный маркер GPS в виде наконечника стрелы или просто треугольника, который интуитивно понятным образом указывает направление движения. Кроме того, маркер должен быть хорошо заметен на карте, поэтому его цвет обычно сильно отличается от фона, края дополнительно обведены и т.д.



В самом простом случае можно отображать позицию устройства на местности, считывая координаты с датчика GPS и размещая маркер в соответствующее место на карте. Уже здесь мы сталкиваемся с первой проблемой — измерительной погрешностью, которая даже в условиях неплохого сигнала вполне может достигать 20–30 метров.



Для ответа на обычный вопрос «Где я нахожусь?» такого способа отображения будет вполне достаточно, особенно если вокруг маркера нарисовать ещё и круг точности с радиусом, равным оценке погрешности. Однако для навигации нужно придумать что-то получше, ведь водителя, движущегося по городской улице, вряд ли устроит маркер GPS, расположенный внутри соседнего дома или, того хуже, на каком-нибудь внутриквартальном проезде.



Решить проблему помогает маршрут, построенный программой до точки назначения и всегда присутствующий в сценарии навигации. При помощи некоторых ухищрений мы можем «притянуть» точку на карте к маршруту, нивелируя некоторую часть измерительной погрешности датчика GPS. В первом приближении притяжку можно рассматривать как проецирование точки на линию маршрута. Рассмотрение же нюансов, а также способов обнаружения схода с маршрута, к сожалению, выходит за рамки данной статьи.



Взяв на вооружение обозначенный приём притяжки, мы можем абстрагироваться от двумерных географических координат (широты-долготы или любых других) и перейти к одномерной координате — смещению относительно начала маршрута, измеряемому, например, в метрах. Такой переход упрощает как теоретические модели, так и вычисления, выполняемые на устройствах пользователей.



Отображение геопозиции во времени



Дискретный характер поступления данных от датчика GPS — ещё одна проблема при реализации ведения пользователя по маршруту. В идеальном случае координаты обновляются один раз в секунду. Рассмотрим несколько вариантов отображения геопозиции во времени и выберем наиболее подходящий для наших задач.



1. Самый простой способ заключается в том, чтобы при получении каждого нового отсчёта от датчика тут же выполнять притяжку к маршруту и отображать соответствующее местоположение на карте. Среди достоинств стоит отметить исключительную лёгкость реализации, высокую в некотором смысле точность (ведь здесь мы просто отображаем спутниковые данные, не внося в них каких-либо серьёзных изменений) и минимальную вычислительную трудоёмкость. Главный недостаток в том, что маркер в этом случае не движется по карте в привычном понимании, а «телепортируется» из точки в точку. В основном сценарии навигации камера (виртуальный наблюдатель — термин из области компьютерной графики) привязана к маркеру GPS, поэтому подобные его телепортации приводят к резкому «проматыванию» карты вдоль маршрута и, как следствие, к дезориентации водителя, особенно на высоких скоростях, когда за время между отсчётами геопозиции автомобиль преодолевает значительное расстояние. Наша задача — помочь пользователю, а не сбить его с толку, поэтому указанного изъяна уже достаточно, чтобы исключить данный вариант из рассмотрения.



Единственная возможность избежать дезориентации состоит в том, чтобы перемещать маркер GPS плавно, без «телепортаций», а значит, двигать его нужно существенно чаще, чем приходят отсчёты геопозиции. Чтобы обеспечить такое движение, требуется каким-либо образом вычислять промежуточные точки между реальными отсчётами с датчика и использовать их, пока не будет получен очередной отсчёт. Конкретному подходу к вычислению этих промежуточных точек стоит уделить особое внимание, так как он в конечном итоге сильно повлияет на общую эргономику программы-навигатора.



2. Второй способ отображать местоположение пользователя связан с самым очевидным подходом к генерации промежуточных точек — интерполяции между последними реальными отсчётами GPS. Смысл в том, чтобы двигать маркер от предпоследнего отсчёта к последнему в течение некоторого заданного времени, вычисляя промежуточные точки с требуемой частотой по одной из известных математических функций (простейший вариант — линейная интерполяция). Пользоваться навигатором при таком способе значительно удобнее, но недостатки у него тоже есть.



Один из самых безобидных — необходимость заранее задавать время интерполяции. Установка его в одну секунду будет хорошо работать только в упомянутом выше идеальном случае, когда именно столько времени будет проходить между отсчётами GPS. Если времени пройдёт меньше — не беда, можно просто начать двигаться из текущей позиции в новую целевую. А вот если больше — придётся маркеру стоять на месте и ждать новых координат от датчика, хотя автомобиль пользователя вполне может в это время двигаться.



Есть и более серьёзная проблема. В момент поступления нового отсчёта маркер в лучшем случае находится в предыдущей реальной точке. С точки зрения пользователя мы вносим ещё одну погрешность позиционирования, величина которой не меньше, чем расстояние, преодолеваемое автомобилем за время между отсчётами. При скорости в 100 км/ч это значение достигает почти 28 метров, что вкупе с возможной измерительной погрешностью делает информацию, выдаваемую пользователю, мягко говоря недостоверной.



Мы могли бы сделать маркер GPS огромных размеров и загородить им четверть экрана, тщательно маскируя недочёты описываемого способа позиционирования, но идти на прямой подлог было бы неуважением к пользователям и к самим себе. Точность и своевременность отображаемых данных — ничуть не менее важный критерий при разработке навигатора, чем внешняя красота и плавность движения.



3. С учётом появившегося требования к точности позиционирования стоит заметить, что теперь от нас требуется незадолго до прихода нового отсчёта GPS расположить маркер в точке, максимально приближенной к этому новому отсчёту. То есть, по сути, заглянуть будущее, пусть и ненадолго. Хотя с изобретением машины времени у человечества пока дела обстоят из рук вон плохо, для нас спасение всё же есть. Движение автомобиля инертно, поэтому скорость и направление его движения не могут меняться мгновенно, а раз так, мы можем попытаться с некоторой точностью спрогнозировать, где пользователь будет находиться в интервале между последним отсчётом позиции и будущим. Если нам удастся добиться того, что ошибка прогнозирования в большинстве случаев будет меньше, чем погрешность второго способа, то мы здорово облегчим жизнь пользователей нашего навигатора.



Такого рода прогнозирование в точных науках называется экстраполяцией. Именно этим путём мы пойдём в попытке разработать третий способ ведения по маршруту, удовлетворяющий всем перечисленным выше критериям. Далее нам придётся прибегнуть к более формальному языку изложения, коль скоро речь пойдёт о математических моделях.



Ведение по маршруту с экстраполяцией позиции



Ранее упоминалось, что благодаря притяжке геопозиции пользователя к маршруту навигации мы можем перейти от двумерных географических координат к одномерной координате — смещению относительно начала маршрута (для краткости дальше будем использовать термин «смещение» без уточнений).



Вспомним поступающие к нам данные и введём для них обозначения:

s_i, i\in \mathbb{N} — реальные отсчёты смещения, получаемые притяжкой позиции GPS к линии маршрута;

t_i, i\in \mathbb{N} — время прихода соответствующих отсчётов смещения.

На этом, собственно, список входных данных и заканчивается. Придётся выжимать из них максимум полезной информации.



В конечном итоге нам необходимо построить функцию экстраполяции смещения s=s(t),t \in [t_0; +\infty), которая будет приближена к реальной динамике автомобиля и при этом обеспечит плавность движения маркера GPS по всему нашему маршруту (его длина ни на что не повлияет, так как завершение маршрута обрабатывается отдельно, поэтому условно будем считать маршрут бесконечным). Для обеспечения хорошей визуальной плавности достаточно будет условия гладкости s(t), то есть ни позиция, ни скорость маркера не должны меняться скачком. Другими словами, функция s(t) обязана быть непрерывной вместе со своей первой производной (здесь и далее — по времени) на всей области определения.



Обратим внимание, что каждый реальный отсчёт смещения несёт существенно новую информацию о движении. Например, если в течение длительного времени автомобиль ехал равномерно, а затем стал ускоряться, то «почувствовать» ускорение навигатор сможет только с приходом очередного отсчёта. Так как заглянуть в будущее на сколь угодно длительный срок мы не можем, все поступающие новые отсчёты GPS будут в общем случае изменять поведение искомой функции s(t), что не позволяет задать её одним аналитическим выражением. Вместо этого попытаемся определить функцию кусочно. Для этого решим сперва более простую задачу.



Непосредственная кусочная экстраполяция



Построим такую функцию экстраполяции смещения s_i (t),t\in[t_i;+\infty), чтобы после i-го отсчёта её значения предсказывали реальное расположение пользователя в течение достаточного времени до прихода (i+1)-го отсчёта. Все полезные данные, которыми мы обладаем, — последовательность отсчётов до i-го включительно вместе со временем получения каждого из них.



Вспомнив про конечные разности, отметим, что у нас есть возможность оценить скорость движения автомобиля в i-й момент времени, разделив длину отрезка между последним и предпоследним смещением на соответствующий временной интервал:



v_i\approx \frac{s_i-s_{i-1}}{t_i-t_{i-1}}=s_i{^'} (t_i)


, где v_i — оценка скорости по отсчётам, а s_i{^'} (t_i) — производная экстраполяционной функции s_i (t), которую мы пытаемся построить.



Аналогично для производных более высокого порядка — ускорения, рывка и т.д.:



\left\{\begin{aligned}<br />
a_i\approx \frac{v_i-v_{i-1}} {t_i-t_{i-1}} = s_i^{''} \\<br />
j_i\approx \frac{a_i-a_{i-1}} {t_i-t_{i-1}} = s_i^{'''} \\<br />
\end{aligned}<br />
\right.


Как видно из этих формул, для получения оценки всё более старших производных смещения требуется учитывать всё больше отсчётов, предшествующих текущему: для определения скорости нужны два отсчёта, для ускорения — три, для рывка — четыре и т.д. С одной стороны, чем больше динамических характеристик движения мы будем учитывать в своём прогнозе, тем большую моделирующую способность получим; с другой — полезная информация, содержащаяся во всё более «старых» отсчётах, драматически теряет актуальность. Например, тот факт, что мы ехали со скоростью 30 км/ч минуту назад ничем не поможет нам в текущий момент времени: с тех пор можно было несколько раз разогнаться, затормозить или вообще остановиться. По этой причине оценки всё более старших производных смещения становятся всё дальше от реальности; кроме того, вклад погрешности вычисления некоторой производной в общую аналитическую модель смещения тоже растёт с увеличением порядка этой производной. Раз так, то, начиная с какого-то порядка, динамические характеристики, оценённые при помощи конечных разностей, вместо уточнения будут только портить нашу модель.



По результатам проверок на реальных данных выяснилось, что оценка рывка j_i, особенно в случаях «среднего» качества сигнала GPS, уже достаточно плоха, чтобы от неё было больше вреда, чем пользы. С другой стороны, к счастью, наиболее частые сценарии динамики автомобиля — это покой, равномерное и равнопеременное движение, описываемые полиномиальными уравнениями 0-й, 1-й и 2-й степени от времени соответственно.



Получается, квадратичной модели равнопеременного движения нам будет вполне достаточно для описания большинства дорожных ситуаций, и для неё у нас как раз хватает более-менее качественных оценок динамических характеристик — скорости и ускорения. Вспомнив школьный курс физики, мы уже можем вчерне составить аналитическое выражение для искомой экстраполяционной функции:



s_i (t)=s_i+v_i t+\frac12 a_i t^2


Осталось сделать всего один шаг: область определения s_i (t) начинается с момента времени t_i, поэтому время в вычислениях удобнее считать с этого же момента.



В итоге функция примет вид:



s_i (t)=s_i+v_i (t-t_i )+\frac12 a_i (t-t_i )^2,t

https://habrahabr.ru/post/308500/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Математика на пальцах: давайте посчитаем хотя бы один ряд Фурье в уме

Четверг, 25 Августа 2016 г. 18:33 (ссылка)

Нужно ли вам читать этот текст?



Давайте проверим. Прочтите следующее:



Тригонометрическим рядом Фурье функции

https://habrahabr.ru/post/308526/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

[Перевод] Музыка, Mathematica и вычислительная вселенная: автоматическое создание музыки на основе клеточных автоматов

Среда, 24 Августа 2016 г. 17:03 (ссылка)



Перевод поста Стивена Вольфрама (Stephen Wolfram) "Music, Mathematica, and the Computational Universe" о замечательном ресурсе WolframTones, работа которого была недавно возобновлена на новой площадке Wolfram Cloud (сайт, созданный в 2005 г., был недоступен пару лет, так как использовал не поддерживаемые современными браузерами решения).

Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.



Насколько сложно создать человеческую музыку? Такую, чтобы пройти музыкальный аналог теста Тьюринга?



Хотя музыка обычно имеет определенную формальную структуру, что отмечали пифагорейцы ещё 2500 лет назад, по своей сути она весьма человечна: отражение чистого творчества, которое есть суть определяющая характеристика человеческих способностей.



Но что есть творчество? Это то, что было необходимо в течение всей биологической и культурной эволюции? И может ли оно также существовать в системах, которые не имеют ничего общего с людьми?



В своей работе над книгой Новый вид науки (A New Kind of Science) я исследовал вычислительную вселенную возможных программ и обнаружил, что даже очень простые программы могут показывать поразительно богатый и сложный характер, наравне, например, с тем, что можно встретить в природе. И, опираясь на разработанный принцип вычислительной эквивалентности, я пришел к убеждению, что не может быть ничего, что принципиально отличает наши человеческие способности от любых процессов, которые происходят в природе, или даже в очень простых программах.



Но что можно сказать о музыке? Некоторые люди, выступая против принципа вычислительной эквивалентности, в качестве аргумента использовали свою веру в то, что "не могут существовать простые программы, которые смогут произвести серьёзную музыку".



И мне стало любопытно: действительно ли музыка есть что-то особенное и исключительно человеческое? Или всё таки её можно прекрасно создавать автоматически, с помощью вычислений?



В 2003 году, после десятка лет моей затворнической работы над A New Kind of Science, мне постепенно переставали быть чужды мирские проблемы, и одна из них заключалась в том, что рингтон на моём сотовом был как у всех. Так что я подумал: если какая-то оригинальная индивидуализированная музыка на самом деле может создаваться автоматически, то можно было бы просто поменять всем мелодии на мобильном, и каждый бы имел свою собственную.



Спустя некоторое время мы решили поэкспериментировать с возможностями создания музыки с помощью программ.



Получилась долгая история попыток создания музыки по правилам. Большинство полученного производило впечатление слишком "роботского" или случайного. Но то, к чему я пришёл в A New Kind of Science, казалось, давало нам новые возможности, ведь там было убедительно показано, что даже с правилами простых программ можно создавать такие сложные и живые вещи, которые мы наблюдаем в природе и которыми мы восхищаемся.



Мы начали с самого простого эксперимента: взяли столь знакомые нам клеточные автоматы (статья в Википедии) и использовали фрагменты производимых ими шаблонов для формирования партитуры. У меня не было ни малейшего представления о том, что мы получим в результате. И, конечно, некоторые клеточные автоматы с простыми моделями поведения производили абсолютно скучную музыку. Однако, к некоторому моему удивлению, в вычислительной вселенной за клеточным автоматом, порождающим весьма богатые и приятные фрагменты музыки, далеко ходить не пришлось.



Факт в том, что за логикой в музыке всегда стоит какая-то простая программа. Но ключевым моментом A New Kind of Science является то, что основная программа может быть простой, однако производить богатую и сложную картину.



Но будет ли в этом эстетика? Что касается визуальной части, то мне уже давно было известно, что клеточные автоматы могут производить нечто весьма занятное и интересное. А с учётом того, что мы знали о клеточных автоматах, это не было особо удивительно. Потому что я знал, что они могут уловить суть многих процессов в природе. И поскольку мы находим природу эстетичной, то тоже самое должно быть справедливо и для клеточных автоматов.



Но в то время как природа использует лишь несколько определенных видов правил, вселенная клеточных автоматов бесконечна. В некотором смысле вычислительная вселенная обобщает нашу реальную Вселенную. Она содержит основные механизмы, но допускает бесконечное множество вариаций, каждый с эстетикой, которая обобщает эстетику нашего мира.



В начале 90-х Mathematica обзавелась поддержкой генерации звука. И, со всей мощью символьного языка, Mathematica становится идеальной платформой для того, чтобы реализовывать наши алгоритмы и начать создавать музыку. Результаты значительно превзошли даже наши самые смелые ожидания. Мы использовали идеи из теории музыки для облачения пока ещё «голых» клеточных автоматов, и очень скоро мы уже создавали оркестровые музыкальные отрывки, и звучали они удивительно хорошо.



Проходящие мимо нашего офиса люди, слыша воспроизводящуюся музыку, часто останавливались и спрашивали: "Что это за песню вы слушаете?" Мы делали музыку, которая была достаточно хороша для того, чтобы люди считали её сделанной людьми; можно сказать, что мы успешно прошли аналог теста Тьюринга для музыки.



Что ж, недавно мы закончили делать сайт WolframTones. И многие начали его использовать. Должен сказать, что я думал, что это был просто интересный эксперимент, и, может быть, хороший способ для создания простых мелодий, то есть ничего серьёзного с точки зрения музыки не предполагалось.







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



Я рассматривал это как хорошую проверку принципа вычислительной эквивалентности. Как выразился один исследователь: "Стоит услышать музыку, производимую простыми программами, как они начинают выглядеть гораздо более похожими на нас".



В вычислительном мире каждая программа фактически определяет свой собственный искусственный мир — чьи звуки и логику мы воспринимаем в воспроизводимой ею музыке. Некоторые из этих миров скучные, бесплодные земли, которые порождают тусклую и монотонную музыку. Другие изобилуют случайностью и шумом. Однако одна из сотни или тысячи программ несёт в себе что-то прекрасное: богатые, фактурные, иногда знакомые, а иногда экзотические музыкальные формы.



image

(Прослушать аудио, соответствующее данному клеточному автомату)



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







Сайт WolframTones был запущен 16 сентября 2005 года. И вот, с тех пор он есть в интернете и с помощью Mathematica создаёт музыку. Должен признаться, что я некоторое время не смотрел его логи. Однако заглянув туда сейчас, я обнаружил, что он использовался десятки миллионов раз для создания десятков миллионов музыкальных композиций.



image

(Прослушать аудио, соответствующее данному клеточному автомату)



По меркам, к примеру, использования Wolfram|Alpha — это ничто. Но для музыкальных композиций это огромная цифра. Itunes в настоящее время содержит около 14 миллионов музыкальных композиций и представляет собой большинство того, что когда-либо было выпущено.  Но всего за несколько лет WolframTones создал большее количество композиций. Используя лишь вычисления, он в некотором смысле превзошёл наш вид в создании музыкальной продукции, в одиночку создав больше оригинальной музыки, чем за всё время до него.



Для того, чтобы результат выдавался мгновенно, сайт кодирует музыку в MIDI (то, что Mathematica теперь поддерживает напрямую в символьном виде). Было создано множество композиций WolframTones в MP3 формате. Полным перераспределением ролей можно назвать случай, когда я несколько лет назад ходил на концерт, где люди играли на скрипках фрагмент, полностью созданный с помощью WolframTones.



Могут ли простые программы полностью создать целую симфонию? Композиции в WolframTones ведают нам некоторые истории из вычислительного мира, которые имеют продолжительность, пожалуй, не более минуты. Судя по моему опыту, для того, чтобы создать больший фрагмент — тот, что поведает нам какую-то более длинную историю — нам потребуются структуры более высокого уровня. Однако у нас нет каких-то препятствий в создании простой программы, которая бы обеспечила подобную структуру. Главенствующая история может быть абсолютно полной, как и многие другие истории, что звучат в нашем мире музыкой законов природы.



Однако как много можно получить из столь малого? Как выглядит максимально короткая программа, создающая какой-то интересный музыкальный фрагмент?



Очень легко начать создавать программы в Mathematica:



Sound[
Map[
Function[
SoundNote[DeleteCases[3 * Range[21] * Reverse[#], 0] - 24,
0.1
]
],
Transpose @ CellularAutomaton[90, {{1}, 0}, 20]
]
]






(Прослушать аудио, соответствующее данному клеточному автомату)



Sound[
Map[Function[SoundNote[#, 1 / 6, "Warm"]],
Map[Pick[{0, 5, 9, 12, 16, 21}, #, 1] &,
CellularAutomaton[30,
{{1, 0, 0, 0, 0, 0}, 0},
13,
{13, 5}
]
]
]
]






(Прослушать аудио, соответствующее данному клеточному автомату)



И мы планируем устроить конкурс, чтобы посмотреть, насколько хороших результатов можно добиться, особенно с использованием различных современных алгоритмических инструментов наподобие обработки изображений, которые имеются в Mathematica. Но в конечном итоге мы не сможем здесь полагаться на одно лишь человеческое творчество. Ведь мы хотим, по сути, автоматизировать творчество, уйти за пределы того, что люди могли себе представить, а не просто исследовать вычислительную вселенную в поисках интересных нам программ и идей.



При создании музыки мы можем работать на уровне нот, сочетания нот или даже звуковых сигналов, обобщая пути построения приятных для человека сигналов, которые традиционно использовали физические музыкальные устройства (или их цифровые аналоги).



Конечно, творчество в вычислительной вселенной не ограничивается музыкой. Было, к примеру, довольно много исследований касательно изобразительного искусства, архитектуры. Можем ли мы создать здание с использованием лишь одного простого правила? Если да, то сама логика структуры здания сможет нам многое поведать об эргономике.



Могут ли быть для нас поистине ценны автоматически созданные вещи, такие как музыка или что бы то ни было? Или нам всегда нужна история, связывающая то, что мы видим, со всем телом человеческой культуры? Возвращаясь к ранее сказанному — наше понимание природы ясно даёт понять, что нет никакой необходимости в человеческой истории. Вместо этого необходимой представляется связь с определенной всеобъемлющей логикой, которая, по сути, является именно тем, что обеспечивает концепция вычислительной вселенной.



Когда я смотрю на Wolfram|Alpha, меня захватывает радость от осознания того, как много человеческих знаний можно запечатлеть и сделать их вычислимыми. Новый рубеж — запечатлеть не только знания, но и творчество. Чтобы иметь возможность, например, добиваясь некоторой цели, понять творческий путь её достижения. Музыка есть суть плод чистого творчества, и то, что мы узнали, как предполагает принцип вычислительной эквивалентности, что даже в этой области, такие вещи, как WolframTones, удивительно хороши в получении творчески насыщенного результата.



Мы хотим воплотить более высокий уровень автоматизации, тем самым резко расширив творческие возможности, что, без сомнения, добавит множество новых увлекательных возможностей.
Original source: habrahabr.ru.

https://habrahabr.ru/post/308428/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Комментарии (0)КомментироватьВ цитатник или сообщество

Следующие 30  »

<математика - Самое интересное в блогах

Страницы: [1] 2 3 ..
.. 10

LiveInternet.Ru Ссылки: на главную|почта|знакомства|одноклассники|фото|открытки|тесты|чат
О проекте: помощь|контакты|разместить рекламу|версия для pda