4.1. Проблема и очевидные методы решения

Одна и главных задач при работе с данными - нахождение минимума функции

Это нужно:

1. В машинном обучении, когда модель выдаёт какую-то ошибку предсказаний и задача так её подогнать, чтобы ошибка была минимальной (метод наименьших квадратов этим и занимается).
2. В экономике нужно минимизировать риски (их тоже можно выразить как функцию) и затраты.
3. В физике многие законы построены на минимизации. Например, принцип наименьшего действия или наименьшей энергии.

Примеров можно придумать ещё много, но суть в том, что эта задача невероятно важна для различных приложений

Попробуем представить задачу геометрически

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

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

А в случае двумерной функции вот так (x, y - входные параметры, z - выходной параметр):

Первый вариант - просто перебрать кучу точек
Можно подобрать такие оптимальные точки, чтобы среднее расстояние до ближайших точек и краёв было минимальным
Тогда мы "покроем" максимальную площадь с минимальным расстоянием до реальной точки минимума

Например, если у нас есть одна попытка, то надо проверять центр (хотя это достаточно туповатое решение конечно)
Если два измерения, то уже сложнее
Например, в случае квадрата это будут две точки, которые по одной их осей лежат в центре, а по другой расположены так, чтобы расстояние до угла было$\frac{\sqrt{5}}{4}$:

И так далее, нам это не сильно важноВажно то, что это не приведёт к успеху

Объясняется это проклятьем размерности (которое обсуждалось в начале третьего модуля)
Как мы помним, объём при увеличении размерности сильно уходит по краям сферы и по углам куба
И даже сфера радиусом 99% от изначальной в случае размерности 1000 где-то в 25000 раз меньше, чем изначальная сфераЭто приводит к тому, что точек для нахождения примерного минимума нужно очень много (экспоненциально, с ростом размерности)

Например, пусть у нас вся функция расставлена на кубе со стороной 1
И мы хотим точность в 0.1 (то есть, попасть от точки минимума на расстояние не более, чем 0.1)
Сколько понадобится измерений?

В одномерном случае для получения такой точности нам понадобиться 10 точек
В многомерном аналогичная логика, только по каждой из оси
Получается, что нужное количество точек растёт экспоненциально: $10^d$

Если у нас функция хотя бы 20 параметров (а их в машинном обучении бывает и сильно больше), то нам нужно уже $100000000000000000000$ точек
Я думаю понятно, что возможности проверять такое количество точек у нас нет
И при том, точность в 0.1 достаточно плохая и если её пытаться увеличить, то будет ещё сильно хуже

Кому-то может прийти идея расставлять точки случайно, ведь часто в стохастические алгоритмы помогают
Но в данном случае это сделает только хуже, я и так работал с оптимальным вариантом

В следующем уроке мы разберём самый известный алгоритм, решающий данную задачу