Comments 35
Можете на пальцах объяснить, что такое порядковый оракул и как он работает? Мне сложно представить, как можно минимизировать функцию, не вычисляя ее значений
Всё объяснение тут заключено здесь "позволяют сравнивать значения функции, не обращаясь к ее значениям непосредственно".
Значения вычислять не можем, а сравнивать два значения можем между собой.
А можно подробнее, на примере, как это делается?
Пусть, например, есть точки x = a и x = b. Мы не знаем и не можем узнать, чему равны f(a) и f(b), но порядковый оракул дает ответ на вопрос, верно ли, что f(a) > f(b) или f(a) < f(b).
В практических задачах редко бывает, когда значение совсем никак узнать нельзя, но часто бывает ситуация, когда вычисление значения функции гораздо дороже, чем вычисление сравнения двух значений. В таких случаях актуально использование алгоритмов, которые используют порядковые оракулы.
А как они получают результат сравнения без вычисления собственно сравниваемых?
При моделировании абстрактного алгоритма они обычно этого не делают. А так много разных случаев есть, тут в комментариях описаны некоторые примеры. Например, можно приближенно вычислять значение с точностью, достаточной для сравнения, но не большей.
А как они приближенно вычисляют? Суть вопроса кажется не особо поменялась. Если она чёрная коробка, то каким-нибудь биномом ньютона пройтись не выйдет. Или речь идёт про момент, когда уже есть условно натренированная нейронка, которая умеет дешево считать примерные значения?
А в этой работе оракул - это чёрный ящик. Там не важно, как он это делает, важна оценка количества таких операций сравнения.
Так я уже ответил на этот вопрос. Никак они это не вычисляют. Смысл модели оракула в алгоритме в том, что они этого вообще не делают.
А если вы хотите применить алгоритм на практике, то возможны все эти описанные в комментариях варианты и многие другие.
ну то же определение 
подразумевает, что происходит вычисление функций от параметров. Каким образом получить эти значения не вычисляя функцию - как раз тот самый вопрос. Как оракул формирует их? Единственный вариант который мне известен - иметь плохо натренированную нейронку, которая даст приблизительно верное значение, но быстрее чем вычислить функцию напрямую.
Правильные вопросы задаете!
Я конечно понимаю, что содержание статьи больше смахивает на новость с обычного сайта, но нама тута эти хайповые заголовки без конкретики — просто не интересны.
Не знаю как делает оракул для сложных функций, но, например, для f(x) = x^99999, не обязательно возводить икс в такую большую степень, чтобы сравнить значения, можно сравнить аргументы.
Например, в сложных климатических или физических моделях полный расчет одного набора параметров может занимать недели. Иногда проще запустить два укороченных расчета и по промежуточным результатам определить, какой из них "более перспективный", не дожидаясь финального значения.
Или, к примеру, для AB-тестирования, мы сравниваем качество вариантов между собой, но обычно нет простого показателя качества.
Дегустация вкуса, как тут было отмечено - отличный пример.
Вы оптимизируете рецепт глинтвейна, по десятку параметров: количество ингредиентов, температура, продолжительность варки и тд. Никакого значения у функции нет, но оракл-дегустатор может сказать, какой из двух вариантов ему нравится больше.
Впечатление, что автор сознательно не хочет пояснить смысл основного алгоритма!
Как я понял, оракул это некоторая функция О, которая возвращает информацию о значении исходной функции f в окрестности всех точек этой функции (например, x^3 хорошо показывает поведение функции x^333 на всей её области определения и её очевидно проще вычислять). Но честно говоря, неочень понятно в чём достижение статьи и в чём открытие учёных из МФТИ, если про этот такой подход есть и статья в Википедии достаточно старая и в книгах Нестерова и Немировского про это тоже писалось.
Нет, оракул возвращает результат сравнения двух значений функции. Значения самой функции он не возвращает.
У Нестерова есть похожий алгоритм, так в этой работе они его обогнали по скорости, написано же.
Я почитал саму статью... зачем там что-то в конце писали про стартап с кофе-машиной? У меня это, скажем так, вызывает улыбку.
Определение порядкового оракула из статьи
φ(x, y) = sign [f(x) − f(y) + δ(x,y)]
f(x) и f(y) — это значения целевой функции в точках x и y, которые мы хотим сравнить. Сами эти значения нам неизвестны.
sign[...] — это математическая функция знака. Она возвращает:
+1, если выражение в скобках больше нуля (означает, что f(x) > f(y)).
-1, если выражение меньше нуля (означает, что f(x) < f(y)).
0, если выражение равно нулю (означает, что f(x) = f(y)).
δ(x,y) — это ограниченный шум. Шум означает, что сравнение может быть неточным, но ошибка этого сравнения (δ) не превышает некоторого известного предела.
Таким образом, порядковый оракул — это механизм (черный ящик), который на вход получает две точки x и y и сообщает, какая из них "лучше" (где значение функции меньше или больше), возможно, с небольшой погрешностью.
Если значения f(x) и f(y) неизвстны, то как проводится операция "-"?
Результат сравнения запрашивается у оракула. Операцию "-" никто не делает.
В этом смысл самого термина "оракул".
Как оракул проводит эту операцию? Это же не магия, оракул тоже должен как-то производит вычисление.
Авторы не описывают внутренний механизм оракула (например, как работает мозг дегустатора). Они описывают его внешнее поведение или интерфейс — что он принимает на вход и что выдает на выходе. Преимущество заключается не в оракуле, а в алгоритме, который может эффективно работать, имея доступ только к такому примитивному оракулу. Вот ключевые прорывы их метода:
А. Он вообще работает (и работает эффективно)
Проблема: Классические алгоритмы (вроде градиентного спуска) здесь бесполезны. Им нужен градиент, которого нет.
Решение авторов: Они придумали, как "обмануть" систему. Они интегрировали Порядковый Оракул в метод координатного спуска (coordinate descent) с помощью линейного поиска (line search).
Как это работает (упрощенно):
Алгоритм выбирает одно направление для улучшения, например, "давай попробуем изменить только количество сахара" (это одна координата).
Далее ему нужно решить, насколько сильно изменить количество сахара. Для этого он использует линейный поиск.
Он "просит" Порядкового Оракула сравнить несколько вариантов: "Какой кофе лучше: с 1 ложкой сахара или с 1.5 ложками?", "А если сравнить 1.5 и 1.7?".
С помощью серии таких простых сравнений (статья упоминает метод золотого сечения) алгоритм находит оптимальный шаг в выбранном направлении, не зная ни точных значений "вкуса", ни градиента!
Б. Он обеспечивает УСКОРЕНИЕ (главный результат статьи)
Это и есть ответ на вопрос, вынесенный в заголовок "Acceleration Exists!".
Контекст: Методы, использующие Порядковый Оракул, существовали и раньше. Но они были "медленными", не ускоренными.
Преимущество: Авторы статьи впервые в мире представили ускоренный алгоритм оптимизации (названный ими OrderACDM), который работает исключительно на сравнениях. "Ускоренный" — это технический термин, означающий, что он сходится к оптимальному решению значительно быстрее, чем его не ускоренные аналоги.
Наглядное доказательство: На Рисунке 2 (страница 9) это показано очень четко. Линия их ускоренного метода (OrderACDM, фиолетовая) уходит вниз (то есть находит лучшее решение) гораздо быстрее, чем все остальные методы, включая классические не ускоренные аналоги.
В. Он адаптивный
За счет использования линейного поиска на каждом шаге, их алгоритм (OrderRCD) автоматически подбирает оптимальный размер шага. Ему не нужно заранее сообщать параметры функции (например, константу гладкости), что делает его более простым в применении на практике.
Один из авторов статьи работал над стартапом по созданию "умной" кофемашины. Клиент, пробуя два напитка с разным составом, выступает в роли оракула, говоря, какой из них ему нравится больше. Оценка клиента "какой из напитков лучше" - играет роль порядкового оракула. Умная кофемашина, используя оценки клиента, оптимизирует состав кофе.
Ну так клиент когда пробует эти оба напитка, оценивает их (то есть вычисляет значение функции насколько ему это кофе нравится) и потом возвращает в кофемашину свой ответ, что ему больше понравилось. Да, сама кофемашина не знает значений функции насколько тот или иной кофе вкусный, но это просто потому, что клиент ей этого не передал, но само вычисление значений функции произошло – разве нет?
Не очень понял, это ведь тот же RLHF только в профиль? Почему не сравнивались с методами из RL? С хорошей теорией по идее можно и RLHF ускорить, но сравнение пока у них только с принципиально более проигрышными методами?
Как интересно...
"С недавним появлением концепции порядковых оракулов исследователи начали изменять подходы к оптимизации"
То есть в математике концепция "порядковых оракулов" появилась недавно? А вот в программировании такая концепция существует уже много десятилетий. Все классические алгоритмы сортировки основаны на этой концепции, бинарный поиск, дерево поиска, а затем по цепочке притягиваются базы данных и вообще весь IT. Потому что эти алгоритмы определены для любых объектов, и необходимо только задать функцию оракула сравнения, которая попарно может сравнивать эти объекты и выдавать результат больше, меньше или равно. В точности как описано в этой статье.
Значит, раньше программирование брало всё из математики. Теперь пришло время математики заимствовать что-то обратно.
Ученые научились быстрее находить положение минимума функции, не вычисляя ее значений