ml_02_opt
Заметка 2. Оптимизационная задача.
курса Введение в машинное обучение.
Шокуров Антон В.
shokurov.anton.v@yandex.ru
http://машинноезрение.рф
Версия 0.11

Аннотация

Поиск "оптимального" решения путем минимизации функционала.

Это предварительная версия! Любые замечания приветствуются.

Приближенное решение

Минимизация

Пусть ${\{ (x_i,y_i) \}}_{i=1}^{i=N}$, где N количество данных. При решении задачи регресии (например, линейной) ищется такая функция $f_{a,b}(x)=ax+b$ дабы минимизировать среднеквадротичное отклонение от исходного значения, а именно -- решается задача: $$ \min_{a,b}\sum_{i=1}^{i=N}(f_{a,b}(x_i) - y_i )^2. $$ Точнее ищется именно параметр ($a,b$) для которого данный минимум достигается: $$ a^*, b^* = \underset{a,b}{\operatorname{argmin}}\sum_{i=1}^{i=N}(f_{a,b}(x_i) - y_i )^2. $$ Последнее показывает важность решения задачи минимизации.

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

Поэтому, ставится задача о приближенном поиске минимума. Подразумевается итеративное решение, т.е. когда приближение к искомому минимумому достигается за некотрое (может и сотни, тысячи) количество шагов. Так, решение начинается с некоторго $\theta_0$. Далее, $$ \theta_{i+1} = G(X, \theta_i). $$ Обновление $\theta_i$ происходит пока не будет достигнута нужное приближение к минимуму.

Поиск минимума

Парабола

Парабола нам хорошо известна. Например, то что экстремум (минимум/максимум) достигается в середине между корнями. Поэтому начнем с неё.

Iterations - Сколько в итоге было итераций. Current function value - Значение функции в последней точке. С точки зрения производительности важны: Function evaluations - Сколько раз было вычисленно значение функции. Gradient evaluations - Сколько раз был вычислен градиаент.

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

Полином четвертой степени

Теперь мы видим, что было 5 шагов. И вычисления подросли.

Как вывести промежуточные шаги. Это может быть интересно с точки зрения понимания что происходит при поиске минимума. И когда минимум будет плохо искаться увидеть наглядно в чем затык.

Не только полнином!

Увеличим масштаб.

График похож, но на самом деле это увеличение возле экстремума. Оно должно быть "впукло", т.е. яма. А ямы похожи друг на друга. Смотрим на ост X.

Поиск нулей

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

Двумерный случай

Отрисовка графики

По аналогии с одномерным случаем покажем как отрисовывать функции от двух переменных, т.е. 3-хмерные графики.

Кривая

Полным аналогом plot в 3трехмерном пространстве является тоже функция plot. Она отвечает за отрисовку одномерной кривой. Так, по аналогии с двумерным графиком функции подаются точки в прострастве которые нужно соеденить подряд. Токчи задаются тремя списками.

Трехмарность обеспечена вызовом plt.gca(projection='3d'). Функции plot были переданы три списка: x, y, z.

Поверхность

Для создание поверхности нам нужно задать сетку и значение функции в каждом узле данной сетки. Сетка задается прямоугольником: отсечками вдоль одной и дрйгой оси (X и Y).

Сетку можно визуализировать так:

Теперь необходимо получить координаты пересечения.

В качестве упражнения получити их самостоятельно через map или цикл for.

Оптимизация

Регуляризация

Сформируем данные

Допустим у нас есть кандидат на линейное уравнение. Как вычислить среднеквадратичную ошибку?

Теперь можно использовать любую ошибку.

Упр. Сведите все вместе. Применb идеалогию машинного обучения: а) случайное разбиение данных на "обучающие" и "проверочные", б) подбор параметров функции по "обучающим" данным, в) оценка делается по тестовым даным, г) интегральная оценка вычисляется как средняя ошибка по случайным разбиениям. Выбирите несколько функций приближения (например, приближение линейной, квадратичной, кубической, но можно и гораздо изошренее) и посчитайте среднею ошибку на случайных выборках. Та функция, на которой наилучший результат и считается искомой с точки зрнеия машинного обучения.

Функтор

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

Как сделать иначе? Как сделать так, чтобы к функции были "привязаны" данные?

Поиск минимума

Линейный способ

Совсем ручной

Ускоряемся

Градиентный</3>

Достигли цикла.

уменьшим шаг.

2D

Тестовое множество

Test

Случайная выборка