Методы оптимизации нулевого порядка: урок 1

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

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

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

Визуализация минимумов и максимумов

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

В нашем примере функция явно имеет минимум в точке w=0, где g(0)=0. По мере удаления от начала координат значение функции становится все больше, указывая на то, что ее глобальный максимум лежит в бесконечности.

Если мы умножим нашу функцию на -1, мы получим новую функцию:

На графике видно, что функция теперь имеет глобальный максимум в начале координат, а ее глобальный минимум теперь находится в бесконечности. Теперь давайте построим новую функцию:

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

Условие оптимальности нулевого порядка

Из приведенных выше примеров мы можем вывести общую формулу для определения глобального минимума функции при заданном количестве входных данных w:

Если мы сложим все наши входные данные в n-мерный вектор, мы можем переписать формулу как:

Решая эту формулу, мы стремимся получить входное значение, такое что:

Это определение глобального минимума нулевого порядка. Точно так же мы можем определить глобальный максимум:

Это определение глобального максимума нулевого порядка. Обратите внимание, что связь между минимумами и максимумами определяется кратностью -1. То есть глобальный минимум функции g(w) всегда является глобальным максимумом функции -g(w) .

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

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

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

Методы глобальной оптимизации

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

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

Пример: минимизация квадратичной функции

Здесь мы применим два подхода к нахождению глобального минимума квадратичной функции:

Ясно, что функция имеет глобальный минимум в точке w=0. Для простоты мы ограничим диапазон w от -3,5 до 3,5:

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

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

Проклятие размерности

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

Наша цель — равномерно покрыть пространство. Теперь переходим к двумерной плоскости:

В двумерном пространстве нам нужно выбрать 3 x 3 = 9 входных точек. Теперь переходим в трехмерное пространство:

В трехмерном пространстве нам нужно будет выбрать 3 x 3 x 3 = 27 входных точек.

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

Обзор:

В этой статье вы изучили основы методов оптимизации нулевого порядка, в частности:

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

На уроке 2 мы рассмотрим методы локальной оптимизации и случайный поиск.