Целые числа и неопределенность в дифференцируемом программировании
Markus Leopoldseder (Директор по знаниям - Глобальное производство и Практика управления цепями поставок в 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, состоит в генерации траекторий - сгенерированных временных рядов, отражающих потоки будущих событий - из базовых вероятностных распределений, а затем позволяющих функции целевой функции работать в соответствии с шаблоном Монте-Карло. Этот подход предлагает возможность моделировать сложные дискретные взаимодействия в системе - такие как последствия каскадных BOM (ведомостей материалов), даже если вероятностные распределения - используемые в качестве входных данных - доступны только для будущего спроса на готовые продукты.
Этот подход не нов. Вариационные автокодировщики - хотя и созданные с совершенно иной точки зрения - используют аналогичную стратегию, принимая параметризацию распределения (гауссовское для VAE) в качестве входных данных и производя отклонения в качестве выходных данных. Как уже обсуждалось выше, когда мы уже упоминали вариационные автокодировщики, мы часто используем счетные распределения, которые производят целочисленные отклонения, а не непрерывные распределения, такие как гауссовские.
Этот генеративный подход - когда распределения превращаются в наблюдения (траектории) - также может быть полностью внутренним в процессе DP. Вместо того, чтобы принимать вероятностные распределения в качестве входных данных и оптимизировать решения на их основе, распределения могут быть изучены во время выполнения оптимизации. Например, прогнозирование спроса может выполняться совместно с оптимизацией ценообразования, так как стратегия ценообразования сильно влияет на спрос, эти два аспекта действительно нельзя анализировать изолированно друг от друга.
Генеративная часть, упомянутая выше, уже присутствует в генеративно-состязательных сетях, которые имели огромный успех в генерации фотореалистичных изображений. При рассмотрении временных рядов LSTM и GRU (более простой и современный эквивалент LSTM) предлагают способы генерации сложных временных рядов, которые не могли быть явно смоделированы через вероятностные распределения.
DP предлагает большую гибкость для использования этих возможностей с точки зрения цепочки поставок при работе с более гетерогенными объектами (графы, временные ряды, реляционные данные) по сравнению с сценариями, обычно рассматриваемыми с точки зрения глубокого обучения. Опять же, большая часть усилий Lokad была сосредоточена на точке зрения цепочки поставок, чтобы убедиться, что инструментарий соответствует конкретным требованиям, возникающим при оптимизации запасов, цен, закупок, производства, ассортимента и т. д., а не на изображения, голоса и обработку естественного языка.
