Применяем градиентный спуск на реальной Земле

в 7:08, , рубрики: momentum optimization, Алгоритмы, алгоритмы оптимизации, градиентный спуск, инерция, машинное обучение, Работа с 3D-графикой

Обычная аналогия для объяснения градиентного спуска такая: человек застрял в горах во время сильного тумана и должен спуститься вниз. Самый логичный способ — осмотреть поверхность вокруг и медленно проложить путь, следуя вниз по склону.

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

Но вот важный вопрос: насколько хорошо градиентный спуск выполняется на реальной Земле?

Определение весов и функции стоимости

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

В нашем алгоритме земного путешествия цель — выйти на уровень моря с любой начальной позиции. То есть мы определим «веса» как широту и долготу, а «функцию стоимости» как текущую высоту над уровнем моря. Иными словами, градиентный спуск должен оптимизировать значения широты и долготы таким образом, чтобы минимизировать высоту над уровня моря. К сожалению, у нас нет математической функции для всей земной поверхности, поэтому рассчитаем значения стоимости по растровому набору данных по высотам от NASA:

import rasterio

# Open the elevation dataset
src = rasterio.open(sys.argv[1])
band = src.read(1)

# Fetch the elevation
def get_elevation(lat, lon):
    vals = src.index(lon, lat)
    return band[vals]

# Calculate our 'cost function'
def compute_cost(theta):
    lat, lon = theta[0], theta[1]
    J = get_elevation(lat, lon)
    return J

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

Применяем градиентный спуск на реальной Земле - 1

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

def gradient_descent(theta, alpha, gamma, num_iters):
    J_history = np.zeros(shape=(num_iters, 3))
    velocity = [ 0, 0 ]

    for i in range(num_iters):

        cost = compute_cost(theta)

        # Fetch elevations at offsets in each dimension
        elev1 = get_elevation(theta[0] + 0.001, theta[1])
        elev2 = get_elevation(theta[0] - 0.001, theta[1])
        elev3 = get_elevation(theta[0], theta[1] + 0.001)
        elev4 = get_elevation(theta[0], theta[1] - 0.001)

        J_history[i] = [ cost, theta[0], theta[1] ]
        if cost <= 0: return theta, J_history

        # Calculate slope
        lat_slope = elev1 / elev2 - 1
        lon_slope = elev3 / elev4 - 1 

        # Update variables
        theta[0][0] = theta[0][0] - lat_slope
        theta[1][0] = theta[1][0] - lon_slope

    return theta, J_history

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

Применяем градиентный спуск на реальной Земле - 2

Хм, похоже, он застрял! То же самое происходит при тестировании в большинстве других мест. Оказывается, наша Земля переполнена локальными минимумами, и градиентный спуск испытывает огромные трудности с поиском глобального минимума, если запускается из локальной области даже рядом с океаном.

Оптимизация с инерцией

Стандартный градиентный спуск — не единственный инструмент, поэтому попробуем оптимизацию с инерцией (momentum optimization). Инерция основана на реальной физике, так что её применение к градиентному спуску на реальной геометрии — привлекательная идея. К сожалению, если разместить на вершине Олимпа даже очень большой валун и отпустить, то вряд ли у него хватит инерции докатиться до океана, поэтому придётся использовать здесь некоторые нереалистичные (в физическом смысле) значения gamma:

def gradient_descent(theta, alpha, gamma, num_iters):
    J_history = np.zeros(shape=(num_iters, 3))
    velocity = [ 0, 0 ]

    for i in range(num_iters):

        cost = compute_cost(theta)

        # Fetch elevations at offsets in each dimension
        elev1 = get_elevation(theta[0] + 0.001, theta[1])
        elev2 = get_elevation(theta[0] - 0.001, theta[1])
        elev3 = get_elevation(theta[0], theta[1] + 0.001)
        elev4 = get_elevation(theta[0], theta[1] - 0.001)

        J_history[i] = [ cost, theta[0], theta[1] ]
        if cost <= 0: return theta, J_history

        # Calculate slope
        lat_slope = elev1 / elev2 - 1
        lon_slope = elev3 / elev4 - 1 

        # Calculate update with momentum
        velocity[0] = gamma * velocity[0] + alpha * lat_slope
        velocity[1] = gamma * velocity[1] + alpha * lon_slope

        # Update variables
        theta[0][0] = theta[0][0] - velocity[0]
        theta[1][0] = theta[1][0] - velocity[1]

    return theta, J_history

После некоторой настройки переменных у градиентного спуска должны увеличиться шансы найти океан:

Применяем градиентный спуск на реальной Земле - 3

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

Заключительные мысли

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

Думаю, из-за этого она предоставляет много интересных возможностей для изучения того, как методы оптимизации машинного обучения работают на осязаемых и понятных локальных геометриях. Похоже, на Олимпе они неплохо справились, так что будем считать обычную аналогию для объяснения градиентного спуска «подтверждённой»!

Если у вас есть мысли по этому поводу, дайте знать в твиттере!

Код проекта здесь.

Автор: m1rko

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js