Целые числа и неопределенность в дифференцируемом программировании
Markus Leopoldseder (Директор по знаниям - Global Manufacturing и Практика управления цепями поставок в McKinsey) поднял два важных вопроса относительно применимости дифференцируемого программирования (DP) для нужд цепей поставок. В этом достаточно техническом посте мы попытаемся дать некоторое представление о том, как обрабатываются ограничения целых чисел и как неопределенность учитывается в DP. Это лишь первый взгляд на подход Lokad. Мы планируем опубликовать расширенные рецепты на docs.lokad.com в более поздней публикации.
Как DP применяется к целочисленным переменным? Ведь если целевая функция принимает целые числа в качестве входных данных, она может быть недифференцируемой.
С точки зрения цепей поставок, большинство решений являются дискретными: мы не можем заказать 4.2 единицы продукта, это либо 4, либо 5. Таким образом, мы ищем – как с точки зрения обучения, так и оптимизации – методы, хорошо работающие с целыми числами. Как остро заметил наш читатель, параметры в DP являются числами, и эти параметры не могут быть ограничены целыми числами, поскольку эта точка зрения несовместима со стохастическим градиентным спуском, который лежит в основе DP.
Существует несколько способов получения дискретных решений и соответствующих дискретных целевых функций через DP, варьирующихся от наивных, но прямолинейных, до чрезвычайно сложных, но не имеющих себе равных в области численной оптимизации.
Самый простой подход заключается в интерполяции целевой функции во время обучения и округлении результатов во время оценки. Например, если мы ищем количество для заказа, которое должно быть целым числом, целевую функцию можно расширить на произвольные числа с помощью интерполяции. Это хорошо работает для систем, которые, несмотря на дискретность, демонстрируют достаточно линейное поведение. Однако при наличии сильной нелинейности, такой как ограничение MOQ (минимальный объем заказа), этот подход не работает так эффективно.
Для решения подобных ситуаций целевая функция может быть заменена вспомогательной функцией, которая аппроксимирует исходную целевую функцию, но делает это гладко и дифференцируемо. Например, ступенчатую функцию, обычно ассоциируемую со штрафными затратами за нарушение MOQ-ограничения, можно заменить сигмоидной функцией. Эпоха за эпохой вспомогательная функция постепенно деформируется, чтобы стать численно ближе к исходной целевой функции.
С нашей точки зрения в цепях поставок, на основании нашего опыта, вспомогательные функции работают удивительно хорошо. Действительно, ситуации, в которых невозможно плавно продвигаться к хорошим решениям, встречаются редко. Проблемы цепей поставок не являются криптографическими задачами, где изменение одного бита в решении полностью портит его. Например, если оформление заказа на 490 единиц приносит прибыль, а MOQ составляет 500, то высока вероятность, что заказ на 500 единиц также будет прибыльным.
Затем существуют более сложные подходы, вдохновленные вариационными автокодировщиками: дробные выходы слоя (как в «слоях глубокого обучения») преобразуются в случайное целочисленное значение, полученное из произвольного распределения, например распределения Пуассона. Благодаря этому механизму программа, работая лишь с дробными параметрами, всё же генерирует целочисленные выходные значения, которые затем могут быть использованы в целевой функции. Стохастический градиентный спуск повторяет процесс множество раз, в стиле Монте-Карло, обеспечивая тем самым, чтобы законы регулировали генерацию случайных целочисленных отклонений должным образом.
Наконец, самые сложные подходы, такие как AlphaZero, опираются на введение сложного набора слоев (например, «глубокой» вычислительной сети), обычно заканчивающейся слоем, подобным Softmax, для генерации дискретных решений. Эти подходы демонстрируют передовые результаты по решению крайне нелинейных задач оптимизации, как показала победа AlphaGo (позже переименованного в AlphaZero) над Ли Седолом. DP также может использовать эти методы – достаточно просто снизить глубину и сложность сети, чтобы контролировать вычислительные затраты. К счастью, на практике, хотя решение задачи MOQ довольно сложно, это ни в коей мере не так трудно, как победить чемпиона мира по Го, и «поверхностные» сети (по меркам глубокого обучения) уже достигают многого.
Предоставление более прямых и практичных способов решения дискретных задач, которые часто встречаются в цепях поставок, было одной из основных причин, по которой мы в Lokad разработали собственный стек программного обеспечения DP вместо адаптации существующего фреймворка; именно для того, чтобы иметь больше возможностей для внедрения специальных конструкций, разработанных специально для этих ситуаций.
Некоторые из этих конструкций представляют собой не что иное, как «стандартная» библиотека функций, написанных самим языком DP – способ смягчить повторяющиеся задачи и избежать определенных ошибок. Однако некоторые из этих конструкций являются более тонкими и вплетенными в стохастический градиентный спуск, чтобы предложить специализированные возможности, которые невозможно было бы реализовать с помощью «чистой» автоматической дифференциации.
Как вы справляетесь с неопределенностью в DP? Ведь DP может оптимизировать любую сложную целевую функцию, настраивая параметры с помощью стохастического градиентного спуска, оптимизирующего нейронную сеть, которая сама по себе является особой функцией. Как учитываются распределения вероятностей?
Основной подход, который мы используем для работы с неопределенностью в DP, заключается в генерации траекторий – созданных временных рядов, отражающих потоки будущих событий, – из базовых распределений вероятностей, а затем в использовании целевой функции по схеме Монте-Карло. Этот подход предоставляет возможность моделировать сложные дискретные взаимодействия внутри системы – например, последствия каскадных ведомостей материалов даже если входные распределения вероятностей были доступны только для будущего спроса на готовую продукцию.
Этот подход не является новшеством. Вариационные автокодировщики – хотя и разработаны с несколько иной точки зрения – используют схожую стратегию, принимая параметризацию распределения (например, гауссовское для VAE) в качестве входных данных и генерируя отклонения в качестве выходных. Как уже обсуждалось выше, когда мы упоминали вариационные автокодировщики, мы часто используем счётные распределения, которые генерируют целочисленные отклонения, а не непрерывные распределения, как гауссовы.
Этот генеративный подход – когда распределения превращаются в наблюдения (то есть траектории) – может быть полностью встроен в процесс DP. Вместо того чтобы принимать распределения вероятностей в качестве входных данных и оптимизировать решения на их основе, сами распределения могут изучаться параллельно с оптимизацией. Например, прогнозирование спроса может осуществляться совместно с оптимизацией цен, так как ценовая стратегия оказывает сильное влияние на спрос, и эти два аспекта не могут быть рассмотрены изолированно друг от друга.
Генеративная часть описанного выше рецепта уже используется в генеративных состязательных сетях, которые были чрезвычайно успешны в создании фотореалистичных изображений. При рассмотрении временных рядов LSTM и GRU (более простой и современный эквивалент LSTM) предлагают способы генерации сложных временных рядов, которые не могли быть явно смоделированы с помощью распределений вероятностей.
DP предлагает большую гибкость для использования этих возможностей с точки зрения цепей поставок, работая с более гетерогенными объектами (графами, временными рядами, реляционными данными) по сравнению со сценариями, обычно рассматриваемыми в контексте глубокого обучения. Опять же, большинство инженерных усилий Lokad были сосредоточены на перспективах цепей поставок, чтобы обеспечить соответствие инструментов специфическим требованиям, возникающим при оптимизации запасов, цен, закупок, производства, ассортиментов и т.д. – вместо того, чтобы сосредотачиваться на изображениях, голосовых данных и обработке естественного языка.
