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

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

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


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




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

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

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

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

Интернет-торговля

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

Роскошные бренды

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

Модные бренды

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

Производство

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

ТОиР (техобслуживание, ремонт, капитальный ремонт)

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

Розничные сети

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

Что стоит за хайпом на искусственном интеллекте

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

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

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

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

Что стоит за оптимизацией с помощью ветвления и алгоритма Гомори

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

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

Одним из самых недооцененных преимуществ глубинного обучения является то, что его успех в равной мере зависит и от прорывов в обучении, и от прорывов в оптимизации. Дело в том, что научное сообщество выяснило, что крупномасштабные оптимизации выполняются невероятно эффективными алгоритмами6. Это не только оптимизационные алгоритмы «глубинного обучения» — все здесь так или иначе пересекается с методом стохастического градиента, который намного более эффективен, чем метод ветвления и алгоритма Гомори. Эти алгоритмы намного лучше работают с нашей вычислительной техникой, а именно процессорами SIMD и (GP)GPU, которые на практике увеличивают скорость вычислений на два или три порядка. Эти прорывы в числовой оптимизации в чистом виде крайне важны для оптимизации решений в цепях поставок. Тем не менее, если системы глубинного обучения уже мало подходят для решения проблем с обучением в цепях поставок, то они еще менее пригодны для решения задач оптимизации в цепях поставок. В действительности задачи оптимизации в большей мере зависят от того, может ли специалист по обработке данных обеспечить надлежащий учет ограничений и метрик с помощью выразительных возможностей системы.

Навстречу дифференцируемому программированию

Теоретически между теорией и практикой нету разницы. На практике же она есть.

Уолтер Дж. Савич, Паскаль: Введение в искусство и науку программирования (1984)


Дифференцируемое программирование (ДП) — это возможность перенести все лучшее, что может предложить глубинное обучение, в цепи поставок как с точки зрения обучения, так и с точки зрения оптимизации. С помощью ДП специалисты по обработке данных могут максимально использовать свои человеческие знания для создания математических решений, согласованных — на глубинном уровне — с целями компании. Между глубинным обучением и дифференцируемым программированием нет четкой границы: это, скорее, плавный переход от наиболее масштабных систем (глубинное обучение) к наиболее выразительным (дифференцируемое программирование), при котором многие программные конструкции становятся доступны постепенно (ценой простой масштабности) при движении к дифференцируемому программированию. И все же опыт Lokad показывает, что в переходе от инструментов, предназначенных в первую очередь для компьютерного зрения, к инструментам, которые создавались непосредственно для цепей поставок, и заключается разница между «интересным» прототипом, который не идет в серию, и широко применяемой промышленной системой.

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

Применение — пункт сложный, но важный. С точки зрения «большого ИИ», время обучения может иметь (почти) произвольную длительность: вычислительной сети позволено учиться неделями, а то и месяцами. После этого вычислительную сеть, как правило, нужно оценить в режиме реального времени (например, по способности распознавать образы для беспилотных автомобилей). В этом плане цепи поставок значительно отличаются: в них лучшие результаты нужно получать после каждой новой тренировки сети. Более того, с точки зрения ДП, те параметры, которые тренирует система, зачастую и есть те самые результаты, которые мы ищем, что делает весь процесс оценки в реальном времени неактуальным. Отличия в детализации, разнообразии и объеме входящих данных также велики. Как правило, «большой ИИ» требует практически бесконечного количества тренировочных данных (например, все текстовые страницы в Интернете), и его главная задача — поиск адаптируемых методов для эффективной работы с массивными наборами данных. Задачи цепей поставок, напротив, должны решаться с помощью ограниченного количества хорошо структурированных, но разнообразных данных. Вследствие этого глубинное обучение уходит в сторону тензорных структур, которые могут быть значительно ускорены с помощью специального вычислительного оборудования; изначально использовались графические процессоры, а теперь все чаще применяются тензорные процессоры. Дифференцируемое программирование, которое основано на методе стохастического градиента, также имеет много полезных свойств с точки зрения аппаратного ускорения, но в меньшей степени, нежели статические графики тензорных операций. Стохастические математические предписания важны по двум причинам: во-первых, эти предписания играют важную роль в обучении. Примерами таких математических предписаний являются вариационные автокодировщики или результаты поиска. Во-вторых, эти предписания играют важную роль в моделировании, так как они позволяют надлежащим образом учитывать вероятностные изменения в системах цепей поставок (например, колебания времени выполнения заказа). В свою очередь, между дифференцируемым программированием и смешанным целочисленным программированием есть огромные отличия: последние несколько десятилетий большинство специалистов занимались сложной числовой оптимизацией.

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

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

Заключение

Дифференцируемое программирование — это крупный прорыв в цепях поставок. Оно основывается на глубинном обучении, которое показало замечательные результаты в решении задач «большого ИИ», таких как компьютерное зрение, но содержит ключевые изменения, которые необходимы, чтобы применять подобные системы для реальных задач в цепях поставок. Компания Lokad доработала свою технологию прогнозирования на базе глубинного обучения, чтобы перейти к дифференцируемому программированию, которое является новым поколением нашей системы. ДП — это не просто технология прогнозирования: оно объединяет в себе оптимизацию и обучение, что открывает широчайшие возможности решения задач, которые прежде считались нереализуемыми.

Хотите протестировать нашу эксклюзивную бета-версию? Напишите нам на contact@lokad.com