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

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

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

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

Протестировать 312 решений

В первой части этого описания попытки решения интересной конкурсной задачи я рассказал о подготовке данных для анализа и о нескольких экспериментах. Напомню, условие задачи заключалось в том, чтобы с наибольшей вероятностью определить наличие слова в словаре, не имея доступа к этому словарю в момент выполнения программы и с ограничением на объем программы (включая данные) в 64K.

Как и в прошлый раз, под катом много SQL, JS, а также нейронные сети и фильтр Блума.

Часто задаваемые вопросы

1. Первое место: 3000 USD.
2. Второе место: 2000 USD.
3. Третье место: 1000 USD.
4. Возможно, мы решим отметить чьи-то чрезвычайно оригинальные решения двумя специальными призами в 400 USD.
5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите половину суммы приза (разумеется, не в ущерб награде победителя). За одного победителя такую награду может получить только один человек — тот, кто отправил ссылку первым.

Правила

Кратко о главном

Давай сразу код!

import numpy as np
X = np.array([ [0,0,1],[0,1,1],[1,0,1],[1,1,1] ])
y = np.array([[0,1,1,0]]).T
alpha,hidden_dim = (0.5,4)
synapse_0 = 2*np.random.random((3,hidden_dim)) - 1
synapse_1 = 2*np.random.random((hidden_dim,1)) - 1
for j in xrange(60000):
    layer_1 = 1/(1+np.exp(-(np.dot(X,synapse_0))))
    layer_2 = 1/(1+np.exp(-(np.dot(layer_1,synapse_1))))
    layer_2_delta = (layer_2 - y)*(layer_2*(1-layer_2))
    layer_1_delta = layer_2_delta.dot(synapse_1.T) * (layer_1 * (1-layer_1))
    synapse_1 -= (alpha * layer_1.T.dot(layer_2_delta))
    synapse_0 -= (alpha * X.T.dot(layer_1_delta))

Часть 1: Оптимизация

О чём статья

Дайте код!

X = np.array([ [0,0,1],[0,1,1],[1,0,1],[1,1,1] ])
y = np.array([[0,1,1,0]]).T
syn0 = 2*np.random.random((3,4)) - 1
syn1 = 2*np.random.random((4,1)) - 1
for j in xrange(60000):
    l1 = 1/(1+np.exp(-(np.dot(X,syn0))))
    l2 = 1/(1+np.exp(-(np.dot(l1,syn1))))
    l2_delta = (y - l2)*(l2*(1-l2))
    l1_delta = l2_delta.dot(syn1.T) * (l1 * (1-l1))
    syn1 += l1.T.dot(l2_delta)
    syn0 += X.T.dot(l1_delta)