Мы с гордостью объявляем об немедленном запуске частной беты Lokad для дифференцируемого программирования, предназначенной для оптимизации количественной цепочки поставок. Дифференцируемое программирование является продолжением глубокого обучения и представляет собой слияние двух алгоритмических направлений: машинного обучения и числовой оптимизации.

Хронология дифференцируемого программирования в Lokad

Дифференцируемое программирование открывает доступ к ряду сценариев, которые ранее считались практически неразрешимыми: совместная оптимизация цен и запасов, оптимизация ассортимента с учетом лояльности, прогнозирование спроса на нестандартные товары (например, драгоценные камни, произведения искусства), оптимизация потоков на крупном многоуровневом уровне, совместная оптимизация в многоканальном режиме, оптимизация запасов при частично некорректных электронных данных, максимизация потоков в условиях множества ограничений и т.д. Для многих других сценариев, которые уже были доступны альтернативными методами, дифференцируемое программирование обеспечивает превосходные числовые результаты при значительно меньших затратах как с точки зрения усилий специалистов по данным, так и вычислительных ресурсов.

Применение к цепочкам поставок

В своей основе дифференцируемое программирование (DP) предлагает путь к объединению задач, которые слишком долго оставались разобщенными, и решает их совместно: ассортимент, ценообразование, прогнозирование, планирование, мерчендайзинг. Хотя такое объединение может показаться нереально амбициозным, на самом деле компании уже применяют неимоверное количество клейкой ленты к своим процессам, чтобы справиться с бесконечными проблемами, вызванными тем, что эти задачи изначально были изолированы внутри организации. Например, ценообразование, очевидно, влияет на спрос, однако и планирование, и прогнозирование почти всегда выполняются с полным игнорированием цен.

DP открывает огромные возможности для принятия приблизительно правильных решений с целостной точки зрения бизнеса, вместо того чтобы быть точно неправильными, смещая проблемы внутри организации, а не решая их. По опыту, стремление к приблизительной правильности при учете всего бизнеса – именно то, что характерно для большинства организаций, работающих на основе электронных таблиц; и в отсутствие технологии – такой как DP – способной охватить целостную перспективу бизнеса, электронные таблицы остаются наименее ужасающим вариантом.

Электронная коммерция: Возможность привязывать 100% проданных единиц к известным клиентам представляет собой огромный скрытый объем информации о рынке; однако, когда речь идет о ценообразовании и оптимизации запасов, информация о лояльности обычно даже не используется в настоящее время. DP предоставляет возможность перейти от прогнозирования на основе временных рядов к прогнозированию на основе временных графов, где каждая пара клиент-товар имеет значение; что приводит к более разумным решениям как для запасов, так и для цен.

Люксовые бренды: оптимизация ценообразования и ассортимента – вплоть до уровня магазина – давно считалась практически неразрешимой из-за разреженности данных, то есть очень низкого объема продаж на единицу товара в магазине – порой всего по одной единице за год. DP предлагает подходы для создания решений, работающих в условиях ультразаряженности, поскольку они сконструированы для обеспечения гораздо большей эффективности использования данных, чем обычные методы глубокого обучения.

Модные бренды: совместная оптимизация запасов и цен является очевидной необходимостью – так как спрос на многие товары может быть очень чувствителен к цене – однако совместная оптимизация закупок и ценообразования ранее не могла быть достигнута из-за отсутствия инструмента, способного уловить эту взаимосвязь – то есть способность покупать больше по более низкой цене вызывает больший спрос (и наоборот). DP предоставляет выразительные возможности для решения этой задачи.

Производство: числовая оптимизация крупных многоуровневых сетей рушится при использовании классических числовых решателей (см. «За пределами оптимизации методом ветвления и отсечения» ниже). Действительно, такие решатели становятся практически непригодными при работе с миллионами переменных или стохастическим поведением. К сожалению, в производстве наблюдаются и то, и другое: множество переменных и стохастическое поведение. DP предлагает практический подход к многоуровневой оптимизации, не жертвуя сложностью реальных потоков в сети.

MRO (обслуживание, ремонт, капитальный ремонт): Если отсутствует одна деталь, необходимая для ремонта системы (например, самолета), то вся система остается неработоспособной. Прогнозы на основе вероятностей являются первым шагом для решения таких нестабильных и прерывистых моделей спроса, но выяснение деталей совместного появления необходимых деталей и превращение этого анализа в конкретные рекомендации по инвентаризации оказалось слишком сложным для практического применения. DP упрощает решение таких проблем.

Розничные сети: Каннибализация внутри розничных сетей – обычно между продуктами, а иногда и между магазинами – давно признана как вопрос первостепенной важности. Эта проблема усугубляется акциями, которые специально предназначены для переключения клиентов с одного бренда на другой. DP предлагает возможность решать проблему каннибализации в условиях проведения акций. Вместо того чтобы просто «прогнозировать акции», DP предоставляет возможность оптимизировать акции в их истинном смысле: как выгодные сделки, совместно реализуемые как каналом сбыта, так и брендом.

За пределами хайпа вокруг искусственного интеллекта

Искусственный интеллект (ИИ) безусловно был модным технологическим трендом 2018 года, и хайп вокруг него сохраняется и в 2019 году. Однако, хотя Lokad широко использует методы, которые обычно подпадают под определение ИИ – например, глубокое обучение, мы не стремимся акцентировать внимание на «ИИ»-части технологий Lokad. Ведь в вопросах количественной оптимизации цепочек поставок готовые ИИ-решения просто не работают. Цепочки поставок – это нечто иное, чем, скажем, компьютерное зрение: данные, метрики и задачи здесь крайне разнородны. В результате компании, приобретавшие якобы «готовые» ИИ-решения, начинают осознавать, что такие решения никогда не будут работать, разве что в самых простых случаях, когда «глупые» системы, основанные на жестких правилах, также могли бы срабатывать вполне удовлетворительно.

По своей сути, цепочки поставок – это сложные, созданные человеком системы, и обычно неразумно ожидать, что система ИИ, основанная только на данных, самостоятельно откроет фундаментальные инсайты о сфере, такие как:

  • проведение акций для люксового бренда категорически недопустимо.
  • отрицательные заказы в системе ERP на самом деле являются возвратами товаров.
  • свежие продукты должны транспортироваться в пределах заданных температурных диапазонов.
  • варианты по цвету могут быть хорошей заменой одежды, но не варианты по размеру1.
  • обслуживание самолетов определяется количеством часов полета и циклов полета.
  • продажи в Великобритании на самом деле проводятся в фунтах стерлингов, даже если в ERP отображается валюта в евро.
  • люди покупают запчасти для своих автомобилей, а не для себя.
  • каждый алмаз уникален, но цены в основном зависят от карата, чистоты, цвета и огранки.
  • отсутствие любой детали NOGO в самолете приводит к его остановке.
  • многим химическим заводам требуется недели на перезапуск после остановки.

В далеком будущем может наступить время, когда машинное обучение сможет эмулировать человеческий интеллект и достигать результатов при решении сложнейших проблем2, однако пока результаты получены только для относительно узких задач. Технологии машинного обучения год от года расширяют границы того, что считается «узкой» задачей, и после десятков лет усилий такие важные проблемы, как безопасное автономное вождение и достойный автоматический перевод, либо решены, либо находятся на грани решения.

Тем не менее, как видно из приведенного списка, цепочки поставок остаются слишком разнородными для прямого применения готовых алгоритмов машинного обучения. Даже если глубокое обучение обеспечивает самые мощные возможности обобщения на сегодняшний день, всё же необходимо участие специалиста по цепям поставок, чтобы сформулировать задачу достаточно узко для того, чтобы алгоритмы могли работать.

В этом отношении глубокое обучение оказалось чрезвычайно успешным, потому что, в отличие от многих прежних подходов в машинном обучении, глубокое обучение является глубоко композиционным: возможно широкое адаптирование структуры модели для более эффективного обучения в конкретной ситуации. Настройка структуры модели отличается от настройки входных данных – задачи, известной как инженерия признаков –, которая традиционно была единственным доступным вариантом для большинства алгоритмов, не относящихся к глубокому обучению, таких как метод случайных лесов3.

Однако, поскольку фреймворки глубокого обучения возникли из «больших проблем» машинного обучения, а именно компьютерного зрения, распознавания голоса, синтеза голоса, автоматического перевода, эти фреймворки были тщательно разработаны и настроены для сценариев, которые буквально не похожи на задачи цепочек поставок. Таким образом, хотя возможно использовать эти фреймворки4 для оптимизации цепей поставок, это не было ни легким, ни быстрым делом.

В заключение, с помощью фреймворков глубокого обучения можно многого добиться для цепочек поставок, однако несовместимость существующих фреймворков с реальными задачами цепочек поставок значительна; это увеличивает затраты, сроки реализации и ограничивает практическое применение этих технологий.

дифференцируемое программирование

За пределами оптимизации методом ветвления и отсечения

Большинство задач в цепочках поставок имеет как аспект обучения – вызванный неполным знанием будущего, текущего состояния рынка, а иногда даже самой системы цепочки поставок (например, неточности в данных инвентаризации) – так и аспект численной оптимизации. Решения необходимо оптимизировать с учетом экономических факторов, удовлетворяя множеству нелинейных ограничений (например, минимальный объем заказа при закупках или размеры партий при производстве).

В области численной оптимизации целочисленное программирование и связанные с ним методы, такие как ветвление и отсечение, доминируют уже десятилетиями. Однако эти алгоритмы и соответствующие программные решения в основном не смогли5 обеспечить ту гибкость и масштабируемость, которые необходимы для создания операционных решений для многих, если не большинства, проблем цепочек поставок. Целочисленное программирование является фантастически способным инструментом для решения узких задач с небольшим числом переменных (например, размещение компонентов в потребительском электронном устройстве), но демонстрирует серьезные ограничения при решении крупномасштабных задач, когда присутствует случайность (например, перераспределение запасов среди 10 миллионов SKU при наличии как вероятностного спроса, так и вероятностного времени транспортировки).

Один из наиболее недооцененных аспектов глубокого обучения заключается в том, что его успех обусловлен не только прорывами в области обучения, но и прорывами в области оптимизации. Научное сообщество обнаружило, что чрезвычайно эффективные алгоритмы выполняют крупномасштабные оптимизации6.

Эти алгоритмы оптимизации «глубокого обучения», полностью основанные на стохастическом градиентном спуске, не только существенно эффективнее своих аналогов, основанных на ветвлении и отсечении, но и гораздо лучше подходят для существующего у нас вычислительного оборудования, а именно для SIMD-CPU и (GP)GPU, что на практике дает прирост скорости в два или три порядка.

Эти прорывы в области чистой числовой оптимизации имеют высокую значимость для цепочек поставок с целью оптимизации решений. Однако, если фреймворки глубокого обучения уже были несколько не предназначены для решения обучающих задач в цепочках поставок, то они еще менее подходят для решения задач оптимизации. Действительно, эти задачи оптимизации еще больше зависят от выразительности фреймворка, чтобы специалисты по цепям поставок могли реализовать ограничения и метрики, которые необходимо обеспечить и оптимизировать.

К переходу к дифференцируемому программированию

В теории нет разницы между теорией и практикой. Но на практике разница существует. Walter J. Savitch, Pascal: An Introduction to the Art and Science of Programming (1984)

Дифференцируемое программирование (DP) – это ответ на то, как привнести в цепочки поставок лучшее, что может предложить глубокое обучение как в области обучения, так и в области числовой оптимизации. С помощью DP специалисты по цепям поставок могут максимально использовать свои человеческие инсайты для создания числовых рецептов, глубоко согласованных с бизнес-целями.

Не существует абсолютной границы между глубоким обучением и дифференцируемым программированием: это скорее континуум от наиболее масштабируемых систем (глубокое обучение) до наиболее выразительных систем (дифференцируемое программирование), при этом многие программные конструкции постепенно становятся доступными – ценой сырой масштабируемости – по мере перехода к дифференцируемому программированию.

Однако наш опыт в Lokad показывает, что переход от инструментов, разработанных преимущественно для компьютерного зрения, к инструментам, созданным для задач цепочек поставок, и есть та самая разница между «интересным» прототипом, который так и не выходит в производство, и промышленной системой, развернутой в масштабах.

Глубокое обучение Дифференцируемое программирование
Primary purpose Обучение Обучение+Оптимизация
Typical usage Обучение один раз, оценка много раз Обучение один раз, оценка один раз
Input granularity Объекты с высокой детализацией (изображения, голосовые последовательности, лидар-снимки, целые текстовые страницы) Объекты с низкой детализацией (товары, клиенты, SKU, цены)
Разнообразие ввода Однородные объекты (например, изображения с одинаковым соотношением высоты и ширины) Гетерогенные объекты (реляционные таблицы, графики, временные ряды)
Объем ввода От мегабайт до петабайт От килобайт до десятков гигабайт
Аппаратное ускорение Исключительно хорошее Хорошее
Выразительность Статические графы операций с тензорами (Почти) произвольные программы
Стохастические численные методы Встроенные То же самое

The typical usage is a subtle but important point. From the “Big AI” perspective, training time can be (almost) arbitrarily long: it’s OK to have a computational network being trained for weeks if not months. Later, the resulting computational network usually needs to be evaluated in real-time (e.g. pattern recognition for autonomous driving). This angle is completely unlike supply chains, where the best results are obtained by re-training the network every time. Moreover, from a DP perspective, the trained parameters are frequently the very results that we seek to obtain; making the whole real-time evaluation constraint moot.

The expectations surrounding the data inputs both in granularity, variariety and volume are also widely different. Typically, the “Big AI” perspective emphasizes near infinite amounts of training data (e.g. all the text pages of the web) where the prime challenge is to find tremendously scalable methods that can effectively tap into those massive datasets. In contrast, supply chain problems have to be addressed with a limited amount of highly structured yet diverse data.

This steers deep learning toward tensor-based frameworks, which can be massively accelerated through dedicated computing hardware, initially GPUs and now increasingly TPUs. Differentiable Programming, being based on stochastic gradient descent also exhibit many good properties for hardware acceleration, but to a reduced degree when compared to static graphs of tensor operations.

The importance of the stochastic numerical recipes is twofold. First, these recipes play an important role from a learning perspective. Variational auto-encoders or dropouts are examples of such numerical recipes. Second, these recipes also play an important role from a modeling perspective in order to properly factor probabilistic behaviors within the supply chain systems (e.g. varying lead times).

Conversely, there is a huge gap between differentiable programming and mixed integer programming - the dominant approach over the last few decades has been to perform complex numerical optimizations.

Смешанное целочисленное программирование Дифференцируемое программирование
Основное назначение Оптимизация Обучение+Оптимизация
Детализация и разнообразие ввода Тонкие объекты, гетерогенные Аналогично
Объем ввода От байт до десятков мегабайт От килобайт до десятков гигабайт
Аппаратное ускорение Плохое Хорошее
Выразительность Неравенства с линейными и квадратичными формами (Почти) произвольные программы
Стохастические численные методы Отсутствуют Встроенные

In defense of mixed integer programming tools, those tools - when they succeed at tackling a problem - can sometimes prove - in the mathematical sense - that they have obtained the optimal solution. Neither deep learning nor differentiable programming provides any formal proof in this regard.

Выводы

Differentiable Programming is a major breakthrough for supply chains. It is built on top of deep learning, which proved tremendously successful in solving many “Big AI” problems such as computer vision, but re-engineered at the core to be suitable for real-world challenges as faced by real-world supply chains.

Lokad has been building upon its deep learning forecasting technology to transition toward Differentiable Programming, which is the next generation of our predictive technology. However, DP is more than just being predictive, it unifies optimization and learning unlocking solutions for a vast amount of problems which had no viable solutions before.

Interested in taking part in our private beta? Drop us an email at contact@lokad.com


  1. По опыту, существует сегмент, где размеры одежды не играют такой роли и по-прежнему служат хорошей заменой — это одежда для детей. Действительно, родители с ограниченным бюджетом часто покупают несколько размеров вперед для своих детей, предвидя их рост, когда им предлагают значительную скидку. ↩︎

  2. Многие, если не большинство, проблем в цепочках поставок являются «сложными» в том смысле, что их социальная сложность означает, что у них нет определенной точки завершения. См. сложная проблема в Википедии. ↩︎

  3. Метод случайных лесов предлагает несколько небольших опций для метапараметризации самой модели: максимальная глубина дерева, коэффициент выборки. Это означает, что какие бы закономерности случайный лес ни упустил, их приходится выделять признаками из-за отсутствия лучших вариантов. См. также Столбцовые случайные леса↩︎

  4. тот факт, что фреймворки глубокого обучения работают вообще для задач цепочек поставок, свидетельствует о колоссальной силе, стоящей за этими прорывными технологиями, чьи открытые принципы выходят далеко за рамки первоначальной области исследования, давшей начало этим фреймворкам. См. также Глубокое обучение в Lokad. ↩︎

  5. Программное обеспечение для оптимизации, такое как CPLEX, Gurobi и теперь их эквиваленты с открытым исходным кодом, существует уже более 3 десятилетий. Теоретически, каждая ситуация закупок, сталкивающаяся с MOQ (минимальное количество заказа) или ценовыми скидками, должна была решаться с помощью программного обеспечения, обеспечивающего подобные возможности. Однако, несмотря на то, что за последнее десятилетие у меня была возможность общаться с более чем 100 компаниями из различных секторов, я никогда не видел, чтобы какой-либо отдел закупок использовал эти инструменты. Мой собственный опыт показывает, что немногие задачи действительно укладываются в набор статических неравенств, включающих только линейные и квадратичные формы. ↩︎

  6. Алгоритм Adam (2015) вероятно является лучшим представителем тех простых, но чрезвычайно эффективных алгоритмов оптимизации, которые позволили всему полю машинного обучения сделать качественный скачок. ↩︎