ML-легушька

Зачем нам вся эта математика бахнем ML все и так заработает. Или нет?
Сегодня разберем следующую 'оптимизационную' задачу. Мы хотим найти максимум ф-ии f на некотором ограниченном домене, при это f отделима от нуля на этом домене и монотонна. В чем же сложность, если f - монотонная ф-ия? В том, что есть дополнительное условие - xf(x) <= b. Существуют задачи в индустрии, на которых завязано много денег и которые формулируются подобным образом. Фактически, нужно решить уравнение xf(x)=b.
Дополнительная проблема в том, что мы не знаем вид функции f, и даже не можем взять ее градиент. Все что мы можем - измерить значение f в некоторой точке. В оптимизации это называется оракулом нулевого порядка. Соответственно, оракул 1ого порядка - знаем значение функции и ее градиента, второго порядка - то же что и ранее + гессиан, и так далее.
Вспомним метод простой итерации. Как он формулируется? Нужно найти сжимающее отображение, которое в итоге будет сходиться к нужной точке. Однако алгоритмически подобрать сжимающее отображение не очень возможно. К счастью, тут его придумать просто.
Например, отображение g(x) = a* x + (1 - a) * b/f(x). Идейно понятно, почему оно сходится к решению - если x слишком большой, тогда b/f(x) < x, и мы его уменьшим, иначе увеличим. На картинке приведено доказательство, почему для этого отображения наше решение - неподвижная точка.
Почему это круто? Ну... Метод сходится геометрически, на практике за 4-5 итераций, что важно, если измерить значение функции f сложно. Подобную тактику можно использовать для подбора гиперпараметров каких-то моделей, если мы идейно представляем, как устроена зависимость лосса от конкретно этого гиперпараметра. Также подобный метод никак не привязан ко времени, и адаптируется, если ф-ия f между итерациями меняется, но не сильно.
Вот так простая математика позволяет зарабатывать деньги. Формальное доказательство что это сжимающее отображение приводить не буду ибо оно немного громоздкое и также следует из свойств метода простой итерации.
Также легко обобщается на стохастический случай, можете попробовать в комментариях :)

🔥37❤8🥰4🤡2🤮1

www.tgoop.com/BDataScienceM/2686

3.2K viewsedited  Feb 9 at 17:50

Зачем нам вся эта математика бахнем ML все и так заработает. Или нет?
Сегодня разберем следующую 'оптимизационную' задачу. Мы хотим найти максимум ф-ии f на некотором ограниченном домене, при это f отделима от нуля на этом домене и монотонна. В чем же сложность, если f - монотонная ф-ия? В том, что есть дополнительное условие - xf(x) <= b. Существуют задачи в индустрии, на которых завязано много денег и которые формулируются подобным образом. Фактически, нужно решить уравнение xf(x)=b.
Дополнительная проблема в том, что мы не знаем вид функции f, и даже не можем взять ее градиент. Все что мы можем - измерить значение f в некоторой точке. В оптимизации это называется оракулом нулевого порядка. Соответственно, оракул 1ого порядка - знаем значение функции и ее градиента, второго порядка - то же что и ранее + гессиан, и так далее.
Вспомним метод простой итерации. Как он формулируется? Нужно найти сжимающее отображение, которое в итоге будет сходиться к нужной точке. Однако алгоритмически подобрать сжимающее отображение не очень возможно. К счастью, тут его придумать просто.
Например, отображение g(x) = a* x + (1 - a) * b/f(x). Идейно понятно, почему оно сходится к решению - если x слишком большой, тогда b/f(x) < x, и мы его уменьшим, иначе увеличим. На картинке приведено доказательство, почему для этого отображения наше решение - неподвижная точка.
Почему это круто? Ну... Метод сходится геометрически, на практике за 4-5 итераций, что важно, если измерить значение функции f сложно. Подобную тактику можно использовать для подбора гиперпараметров каких-то моделей, если мы идейно представляем, как устроена зависимость лосса от конкретно этого гиперпараметра. Также подобный метод никак не привязан ко времени, и адаптируется, если ф-ия f между итерациями меняется, но не сильно.
Вот так простая математика позволяет зарабатывать деньги. Формальное доказательство что это сжимающее отображение приводить не буду ибо оно немного громоздкое и также следует из свойств метода простой итерации.
Также легко обобщается на стохастический случай, можете попробовать в комментариях :)

BY ML-легушька