Проблема и очевидные методы решения
Одна и главных задач при работе с данными - нахождение минимума функции
Это нужно:
- В машинном обучении, когда модель выдаёт какую-то ошибку предсказаний и задача так её подогнать, чтобы ошибка была минимальной (метод наименьших квадратов этим и занимается).
- В экономике нужно минимизировать риски (их тоже можно выразить как функцию) и затраты.
- В физике многие законы построены на минимизации. Например, принцип наименьшего действия или наименьшей энергии.
Примеров можно придумать ещё много, но суть в том, что эта задача невероятно важна для различных приложений
Попробуем представить задачу геометрически
Пусть мы находимся в лесной или горной местности
Наша задача найти наименьшую точку в какой-то области
Но мы при этом, очень слепы
У нас очень сильный туман, поэтому, мы можем видеть только под собой и, может быть, ощущать уровень наклона земли
Ограничений по перемещению у нас нет, но каждое измерение занимает время или дорого обходится (иначе можно было бы просто кучу раз измерить, заполнив весь лес)
Например, одномерный лес может выглядеть как график обычной функции:
А в случае двумерной функции вот так (x, y - входные параметры, z - выходной параметр):
Первый вариант - просто перебрать кучу точек
Можно подобрать такие оптимальные точки, чтобы среднее расстояние до ближайших точек и краёв было минимальным
Тогда мы “покроем” максимальную площадь с минимальным расстоянием до реальной точки минимума
Например, если у нас есть одна попытка, то надо проверять центр (хотя это достаточно туповатое решение конечно)
Если два измерения, то уже сложнее
Например, в случае квадрата это будут две точки, которые по одной их осей лежат в центре, а по другой расположены так, чтобы расстояние до угла было:
И так далее, нам это не сильно важноВажно то, что это не приведёт к успеху
Объясняется это проклятьем размерности (которое обсуждалось в начале третьего модуля)
Как мы помним, объём при увеличении размерности сильно уходит по краям сферы и по углам куба
И даже сфера радиусом 99% от изначальной в случае размерности 1000 где-то в 25000 раз меньше, чем изначальная сфераЭто приводит к тому, что точек для нахождения примерного минимума нужно очень много (экспоненциально, с ростом размерности)
Например, пусть у нас вся функция расставлена на кубе со стороной 1
И мы хотим точность в 0.1 (то есть, попасть от точки минимума на расстояние не более, чем 0.1)
Сколько понадобится измерений?
В одномерном случае для получения такой точности нам понадобиться 10 точек
В многомерном аналогичная логика, только по каждой из оси
Получается, что нужное количество точек растёт экспоненциально:
Если у нас функция хотя бы 20 параметров (а их в машинном обучении бывает и сильно больше), то нам нужно уже точек
Я думаю понятно, что возможности проверять такое количество точек у нас нет
И при том, точность в 0.1 достаточно плохая и если её пытаться увеличить, то будет ещё сильно хуже
Кому-то может прийти идея расставлять точки случайно, ведь часто в стохастические алгоритмы помогают
Но в данном случае это сделает только хуже, я и так работал с оптимальным вариантом
В следующем уроке мы разберём самый известный алгоритм, решающий данную задачу