Математическая оптимизация для управления цепями поставок - Лекция 4.3

00:18 Введение
02:18 Основы
12:08 Зачем оптимизировать? 1/2 Прогнозирование с помощью метода Хольта-Винтерса
17:32 Зачем оптимизировать? 2/2 - Проблема маршрутизации транспортных средств
20:49 До сих пор
22:21 Вспомогательные науки (краткое повторение)
23:45 Проблемы и решения (краткое повторение)
27:12 Математическая оптимизация
28:09 Выпуклость
34:42 Стохастичность
42:10 Многокритериальность
46:01 Проектирование решателя
50:46 Глубокие (обучающиеся) уроки
01:10:35 Математическая оптимизация
01:10:58 “Истинное” программирование
01:12:40 Локальный поиск
01:19:10 Стохастический градиентный спуск
01:26:09 Автоматическое дифференцирование
01:31:54 Дифференциальное программирование (около 2018 года)
01:35:36 Заключение
01:37:44 Предстоящая лекция и вопросы аудитории

Описание

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

Полный текст

Добро пожаловать на эту серию лекций по управлению цепями поставок. Я - Жоанн Верморель, и сегодня я буду рассказывать о “Математической оптимизации для управления цепями поставок”. Математическая оптимизация - это четко определенный, формализованный, вычислительно осуществимый способ определения наилучшего решения для данной проблемы. Все задачи прогнозирования могут быть рассмотрены как задачи математической оптимизации. Все ситуации принятия решений в цепях поставок и за их пределами также могут быть рассмотрены как задачи математической оптимизации. Фактически, математическая оптимизация настолько укоренилась в нашем современном представлении мира, что стало очень сложно определить глагол “оптимизировать” вне очень узкой рамки, которую нам дает парадигма математической оптимизации.

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

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

Я считаю, что этот раздел, когда мы говорим о прикладной математической оптимизации, в основном развивался под названием операционного исследования, которое мы определяем более конкретно как классическое операционное исследование, которое проходило с 1940-х годов до конца 1970-х годов XX века. Идея заключается в том, что классическое операционное исследование, в отличие от математической оптимизации, действительно заботилось о бизнес-проблемах. Математическая оптимизация заботится о общей форме задачи оптимизации, гораздо меньше о том, имеет ли проблема какое-либо деловое значение. Напротив, классическое операционное исследование в основном занималось оптимизацией, но не на любых проблемах - на проблемах, которые были определены как важные для бизнеса.

Интересно, что мы перешли от операционного исследования к математической оптимизации практически так же, как мы перешли от прогнозирования, которое возникло в начале XX века как область, связанная с общим прогнозированием будущих уровней экономической активности, обычно связанных с прогнозами временных рядов. Эта область в основном была замещена машинным обучением, которое заботилось о прогнозировании на гораздо более широком спектре проблем. Мы можем сказать, что у нас был примерно такой же переход от операционного исследования к математической оптимизации, как от прогнозирования к машинному обучению. Теперь, когда я сказал, что классическая эра операционного исследования продолжалась до конца 70-х годов, у меня была очень конкретная дата в виду. В феврале 1979 года Рассел Аккофф опубликовал потрясающую статью под названием “Будущее операционного исследования - это прошлое”. Чтобы понять эту статью, которую я считаю действительно веховой в истории науки об оптимизации, нужно понять, что Рассел Аккофф является, по сути, одним из основателей операционного исследования.

Когда он опубликовал эту статью, он уже не был молодым человеком; ему было 60 лет. Аккофф родился в 1919 году и провел практически всю свою карьеру, работая над операционным исследованием. Когда он опубликовал свою статью, он фактически заявил, что операционное исследование потерпело неудачу. Оно не только не дало результатов, но и интерес к отрасли уменьшался, поэтому интереса к ней было меньше в конце 90-х годов, чем было в отрасли 20 лет назад.

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

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

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

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

Теперь, что касается этой серии лекций, что мы делаем, потому что вопросы, которые Рассел Аккофф поднимает в отношении операционного исследования, до сих пор остаются очень актуальными? Фактически, я уже начал решать самые большие проблемы, на которые указывал Аккофф, и в то время у него и его коллег не было решений, которые можно было бы предложить. Они могли диагностировать проблему, но у них не было решения. В этой серии лекций я предлагаю методологические решения, так же, как Аккофф указывает на глубокую методологическую проблему с этой перспективой операционного исследования.

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

Теперь, зачем мы хотим оптимизировать в первую очередь? Большинство алгоритмов прогнозирования имеют математическую оптимизационную проблему в своей основе. На этом экране вы можете увидеть очень классический мультипликативный алгоритм прогнозирования временных рядов Хольта-Винтерса. Этот алгоритм в основном представляет исторический интерес; я бы не рекомендовал современным цепям поставок фактически использовать этот конкретный алгоритм. Но для простоты это очень простой параметрический метод, и он настолько лаконичен, что вы можете полностью поместить его на один экран. Это даже не слишком подробно.

Все переменные, которые вы видите на экране, являются просто числами; здесь нет векторов. По сути, Y(t) - это ваша оценка; это ваш прогноз временного ряда. Здесь, на экране, он будет прогнозировать H периодов вперед, поэтому H - это горизонт. И вы можете думать, что вы фактически работаете с Y(t), который по сути является вашим временным рядом. Вы можете думать о недельных агрегированных данных о продажах или месячных агрегированных данных о продажах. У этой модели есть три компонента: это Lt, который представляет уровень (у вас есть один уровень на каждый период), Bt, который представляет тренд, и St, который представляет сезонную компоненту. Когда вы говорите, что хотите изучить модель Хольта-Винтерса, у вас есть три параметра: альфа, бета и гамма. Эти три параметра по сути являются просто числами от нуля до единицы. Итак, у вас есть три параметра, все числа от нуля до единицы, и когда вы говорите, что хотите применить алгоритм Хольта-Винтерса, это просто означает, что вы определите правильные значения для этих трех параметров, и все. Идея заключается в том, что эти параметры, альфа, бета и гамма, будут наилучшими, если они минимизируют вид ошибки, который вы указали для вашего прогноза. На этом экране вы можете видеть среднеквадратичную ошибку, которая является очень классической.

Суть математической оптимизации заключается в том, чтобы придумать метод для определения правильных значений параметров альфа, бета и гамма. Что мы можем сделать? Ну, самый простой и наиболее упрощенный метод - это что-то вроде поиска по сетке. Поиск по сетке означает, что мы просто будем исследовать все значения. Поскольку это дробные числа, существует бесконечное количество значений, поэтому мы фактически выберем разрешение, скажем, шаги 0,1, и будем двигаться с шагом 0,1. Поскольку у нас есть три переменные между 0 и 1, мы движемся с шагом 0,1; это около 1000 итераций, чтобы пройти и определить лучшее значение с учетом этого разрешения.

Однако это разрешение довольно слабое. 0,1 дает вам разрешение примерно на 10% от масштаба ваших параметров. Так что, возможно, вы хотите выбрать 0,01, что намного лучше; это разрешение на 1%. Однако, если вы сделаете это, количество комбинаций действительно взрывается. Вы переходите от 1000 комбинаций к миллиону комбинаций, и вы видите, что это проблема с поиском по сетке: очень быстро вы сталкиваетесь с комбинаторной преградой, и у вас есть огромное количество вариантов.

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

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

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

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

Например, проблему маршрутизации транспортных средств, которую вы видите на экране, можно рассматривать как проблему математической оптимизации. Речь идет о выборе списка точек. Я не записал формальную версию проблемы, потому что она относительно переменна и не приносит много понимания. Но если вы хотите об этом подумать, вы можете просто подумать: “У меня есть точки, я могу присвоить своего рода псевдо-ранг, который просто является оценкой для каждой отдельной точки, а затем у меня есть алгоритм, который сортирует все точки по псевдо-рангам в порядке возрастания, и это мой маршрут.” Цель алгоритма будет заключаться в том, чтобы определить значения для этих псевдо-рангов, которые дают вам лучшие маршруты.

Теперь, с этой проблемой, мы видим, что у нас есть проблема, когда решетчатый поиск даже отдаленно не является вариантом. У нас есть десятки точек, и если мы попытаемся все комбинации, это будет слишком большим. Кроме того, градиент не поможет нам, по крайней мере, не ясно, как он поможет нам, потому что проблема очень дискретная по своей природе, и нет ничего, что было бы похоже на очевидное градиентное спуск для этой проблемы.

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

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

Теперь, история до сих пор в этой серии лекций: эта лекция является частью серии лекций, и данная глава посвящена вспомогательным наукам цепочки поставок. В первой главе я представил свои взгляды на цепочку поставок как на область исследования и практику. Вторая глава была посвящена методологии, и в частности, мы представили одну методологию, которая имеет крайнюю релевантность для данной лекции, а именно, экспериментальную оптимизацию. Это ключ к решению очень важной проблемы, выявленной Расселом Аккоффом десятилетия назад. Третья глава полностью посвящена персоналу цепочки поставок. В этой лекции мы фокусируемся на выявлении проблемы, которую мы собираемся решить, в отличие от смешивания решения и проблемы. В этой четвертой главе мы исследуем все вспомогательные науки цепочки поставок. Есть прогрессия от самого низкого уровня в терминах аппаратного обеспечения, движущегося к уровню алгоритмов, а затем к математической оптимизации. Мы продвигаемся в терминах уровней абстракции на протяжении всей этой серии.

Краткое повторение вспомогательных наук: они предлагают перспективу на саму цепочку поставок. Настоящая лекция не о цепочке поставок как таковой, а скорее о одной из вспомогательных наук цепочки поставок. Эта перспектива делает существенную разницу между классической перспективой операционного исследования, которая должна была быть конечной, и математической оптимизацией, которая является средством к достижению цели, но не самой целью, по крайней мере, что касается цепочки поставок. Математическая оптимизация не заботится о конкретных бизнес-аспектах, и отношение между математической оптимизацией и цепочкой поставок подобно отношению между химией и медициной. С современной точки зрения, вам не обязательно быть блестящим химиком, чтобы быть блестящим врачом; однако врач, который утверждает, что ничего не знает о химии, покажется подозрительным.

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

Поэтому математическая оптимизация должна использоваться в сочетании с экспериментальной оптимизацией. Экспериментальная оптимизация, которую мы рассмотрели в предыдущей лекции, - это процесс, при котором вы можете итерироваться с обратной связью из реального мира к лучшим версиям самой проблемы. Экспериментальная оптимизация - это процесс мутации не решения, а проблемы, чтобы итеративно сходиться к хорошей проблеме. В этом и заключается суть вопроса, и здесь Расселл Аккофф и его коллеги тогда не имели решения. У них были инструменты для оптимизации заданной проблемы, но не инструменты для мутации проблемы до тех пор, пока проблема не станет хорошей. Если вы берете математическую проблему так, как вы можете ее записать в своей башне из слоновой кости, без обратной связи из реального мира, то получается фантазия. Вашей отправной точкой, когда вы начинаете процесс экспериментальной оптимизации, является просто фантазия. Для того, чтобы это работало, требуется обратная связь реального мира. Идея состоит в том, чтобы перемещаться вперед и назад между математической оптимизацией и экспериментальной оптимизацией. На каждом этапе вашего процесса экспериментальной оптимизации вы будете использовать инструменты математической оптимизации. Цель состоит в том, чтобы минимизировать вычислительные ресурсы и усилия в инженерии, позволяя процессу итерировать к следующей версии проблемы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует возражение, что если у вас есть стохастическая проблема, вы всегда можете преобразовать ее обратно в детерминированную проблему через выборку. Если вы оцениваете свою шумную функцию потерь 10 000 раз, вы можете получить приближенно детерминированную функцию потерь. Однако этот подход чрезвычайно неэффективен, потому что он вводит 10 000-кратное увеличение нагрузки на ваш процесс оптимизации. Математическая оптимизация направлена на получение наилучших результатов при ограниченных вычислительных ресурсах. Речь идет не о вложении бесконечного количества вычислительных ресурсов для решения проблемы. Мы должны иметь дело с конечным количеством вычислительных ресурсов, даже если это количество достаточно большое. Таким образом, когда мы рассматриваем решатели позже, мы должны иметь в виду, что наибольший интерес представляют решатели, которые могут нативно понимать стохастические проблемы, а не прибегать к детерминированному подходу.

Другой аспект, который также представляет особый интерес, - это многокритериальная оптимизация. В наивном выражении математической оптимизационной задачи я сказал, что функция потерь по сути является однозначной, поэтому у нас есть одно значение, которое мы хотим минимизировать. Но что, если у нас есть вектор значений, и мы хотим найти решение, которое дает наименьшую точку согласно лексикографическому порядку всех векторов, таких как f1, f2, f3 и т. д.?

Почему это даже представляет интерес с точки зрения цепочки поставок? Реальность заключается в том, что если вы принимаете эту многокритериальную перспективу, вы можете выразить все ваши ограничения как одну специальную функцию потерь. Вы можете сначала иметь функцию, которая подсчитывает нарушения ваших ограничений. Почему у вас есть ограничения в цепочке поставок? Что ж, у вас есть ограничения повсюду. Например, если вы размещаете заказ на покупку, вам нужно убедиться, что у вас достаточно места на складе для хранения товаров по их прибытии. Таким образом, у вас есть ограничения на место хранения, производственные мощности и т. д. Идея состоит в том, чтобы вместо решателя, где вам нужно особо рассматривать ограничения, было бы интереснее иметь решатель, который может работать с многокритериальной оптимизацией и где вы можете выразить ограничения как одну из целей. Вы просто подсчитываете количество нарушений ограничений и хотите минимизировать это, приводя количество нарушений к нулю.

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

Теперь давайте немного подробнее обсудим проектирование солвера. С высокоуровневой точки зрения на то, как мы хотим создать программное обеспечение, которое будет создавать решения для очень широкого класса проблем, есть два очень заметных аспекта проектирования, которые я хотел бы подчеркнуть. Первый аспект, который следует учесть, - это то, будем ли мы работать с белым ящиком или черным ящиком. Идея черного ящика заключается в том, что мы можем обрабатывать любую произвольную программу, поэтому функция потерь может быть любой произвольной программой. Нам все равно; мы рассматриваем это как полный черный ящик. Единственное, что нам нужно, это программа, в которой мы можем оценить программу и получить значение предварительного решения. Напротив, подход с белым ящиком подчеркивает тот факт, что сама функция потерь имеет структуру, которую мы можем изучить и использовать. Мы можем заглянуть внутрь функции потерь. Кстати, когда я рассказывал о выпуклости несколько слайдов назад, все эти модели и чисто математические солверы были действительно подходами с белым ящиком. Они являются крайним случаем подходов с белым ящиком, где вы не только можете заглянуть внутрь проблемы, но и проблема имеет очень жесткую структуру, такую как полуопределенное программирование, где форма очень узкая. Однако, не прибегая к чему-то такому жесткому, как математическая система, вы можете, например, сказать, что в рамках белого ящика у вас есть что-то вроде градиента, который поможет вам. Градиент функции потерь представляет особый интерес, потому что внезапно вы можете знать, в каком направлении вы хотите двигаться, чтобы снизиться, даже если у вас нет выпуклой проблемы, где простой градиентный спуск гарантирует хороший результат. Как правило, если вы можете использовать белый ящик для своего солвера, у вас будет солвер, который работает на порядки быстрее по сравнению с черным ящиком.

Теперь, как второй аспект, у нас есть офлайн и онлайн солверы. Офлайн солвер обычно работает пакетно, поэтому офлайн солвер просто берет проблему, выполняет ее, и вам придется подождать, пока она завершится. На данный момент, когда солвер завершает работу, он дает вам лучшее решение или что-то, что является лучшим идентифицированным решением. Напротив, онлайн солвер работает гораздо больше с подходом “лучший результат”. Он будет идентифицировать решение, которое является приемлемым, а затем вкладывать вычислительные ресурсы в итерацию к лучшим и лучшим решениям по мере того, как проходит время и вы вкладываете больше вычислительных ресурсов. Действительно важно то, что при подходе к проблеме с онлайн солвером означает, что вы в принципе можете приостановить процесс в любой момент времени и получить раннее кандидатское решение. Вы даже можете возобновить процесс. Если мы вернемся к математическим солверам, они обычно являются пакетными солверами, где вам приходится ждать до конца процесса.

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

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

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

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

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

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

Теперь, что если я перейду к представлению временного ряда по секундам? Это та же самая история продаж, но вместо того, чтобы представлять мои данные о продажах в ежедневных агрегатах, я собираюсь представить этот временной ряд, тот же самый временной ряд, в агрегатах по секундам. Это означает, что в каждом дне содержится 86 400 секунд, поэтому я увеличу размер и размерность представления проблемы на 86 000.

Но если мы начнем думать о внутренней размерности, то это не означает, что я увеличиваю сложность или размерность проблемы на 1 000 только потому, что у меня есть история продаж и я перехожу от агрегации по дням к агрегации по секундам. Скорее всего, если я перейду к агрегации продаж по секундам, временной ряд будет чрезвычайно разреженным, поэтому практически все ячейки будут содержать нули. Я не увеличиваю интересную размерность проблемы в 100 000 раз. Глубокое обучение показывает, что проблема не является фундаментально сложной только потому, что у вас есть представление проблемы с большим количеством измерений.

Еще один аспект, связанный с размерностью, заключается в том, что хотя вы можете доказать, что некоторые проблемы являются NP-полными, например, проблема коммивояжера (упрощенная версия проблемы маршрутизации транспортных средств, представленная в начале этой лекции), коммивояжер технически является тем, что известно как NP-трудная проблема. То есть, если вы хотите найти лучшее решение в общем случае, это будет экспоненциально затратно с увеличением количества точек на вашей карте. Но на самом деле эти проблемы очень легко решаются, как показано на примере эвристического метода двухоптимального решения; вы можете получить отличные решения с минимальным количеством вычислительных ресурсов. Поэтому будьте осторожны с математическими доказательствами, демонстрирующими, что некоторые проблемы очень сложны. Они не говорят вам о том, что если вам подходит приближенное решение, приближение может быть отличным, и иногда это даже не приближение; вы получите оптимальное решение. Просто вы не можете доказать, что оно оптимально. Это ничего не говорит о том, можно ли приблизительно решить проблему, и очень часто эти проблемы, предположительно страдающие от проклятия размерности, легко решаются, потому что их интересные размерности не так высоки. Глубокое обучение успешно показало, что многие проблемы, считавшиеся невероятно сложными, на самом деле не такие сложные, как казалось изначально.

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

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

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

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

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

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

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

Так почему люди используют перекрестную энтропию? Она обеспечивает невероятно крутые градиенты, и, как показало глубокое обучение, все дело в скорости спуска. Если у вас есть очень крутые градиенты, вы можете очень быстро спускаться. Люди могут возразить и сказать: “Если я хочу оптимизировать среднеквадратичное значение, почему я должен использовать перекрестную энтропию? Это даже не та же цель”. Реальность заключается в том, что если вы оптимизируете перекрестную энтропию, у вас будут очень крутые градиенты, и в конце концов, если вы оцениваете свое решение по среднеквадратичному значению, вы также получите лучшее решение согласно критерию среднеквадратичного значения, очень часто, если не всегда. Я упрощаю для объяснения. Идея заменяющих функций заключается в том, что истинная проблема не является абсолютной; это просто то, что вы будете использовать для контроля и оценки окончательной правильности вашего решения. Это не обязательно то, что вы будете использовать во время работы решателя. Это полностью противоречит идеям, связанным с математическими решателями, которые были популярны в последние несколько десятилетий.

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

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

Глубокое обучение - это набор рецептов, которые позволяют вам сформулировать проблему на основе вашего решателя, чтобы вы получили максимальную отдачу от вашего оптимизатора. Большая часть разработок в сообществе глубокого обучения была сосредоточена на создании этих рецептов, которые очень хорошо обучаются, играя в рамках парадигмы решателей, которые у них есть (например, TensorFlow, PyTorch, MXNet). Вывод заключается в том, что вам действительно хочется сотрудничать с инженером-проблемщиком или, в терминах цепей поставок, специалистом по цепям поставок.

Теперь перейдем ко второму и последнему разделу этой лекции о наиболее ценных элементах литературы. Мы рассмотрим два широких класса решателей: локальный поиск и дифференцируемое программирование.

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

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

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

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

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

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

Существуют и другие хорошо известные эвристики, и если вам нужен очень хороший синтетический обзор того, что требуется для реализации современного локального поискового движка, вы можете прочитать статью “LocalSolver: A Black-Box Local-Search Solver for 0-1 Programs”. Компания, которая разрабатывает LocalSolver, также имеет продукт с тем же названием. В этой статье они дают инженерный взгляд на то, что происходит под капотом их производственного солвера. Они используют мультистарт и имитацию отжига для лучших результатов.

Одно замечание, которое я бы добавил о локальном поиске, заключается в том, что он не очень хорошо или естественным образом работает с стохастическими проблемами. Со стохастическими проблемами не так просто сказать “у меня есть лучшее решение” и сразу же решить, что оно становится лучшим решением. Это более сложно, и вам нужно приложить некоторые дополнительные усилия, прежде чем перейти к решению, оцененному как новое лучшее.

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

Стохастический градиентный спуск предполагает, что функция потерь может быть аддитивно разложена на ряд компонентов. В уравнении Q(W) представляет функцию потерь, которая разбивается на ряд частичных функций, Qi. Это актуально, потому что большинство задач обучения можно рассматривать как задачу обучения предсказанию на основе ряда примеров. Идея заключается в том, что вы можете разложить функцию потерь как среднюю ошибку, допущенную на всем наборе данных, с локальной ошибкой для каждой точки данных. Многие проблемы снабжения также могут быть аддитивно разложены таким образом. Например, вы можете разложить вашу сеть снабжения на ряд показателей для каждого отдельного SKU, с функцией потерь, привязанной к каждому SKU. Истинная функция потерь, которую вы хотите оптимизировать, - это общая функция потерь.

Когда у вас есть такое разложение, которое очень естественно для задач обучения, вы можете итерировать с помощью процесса стохастического градиентного спуска (SGD). Вектор параметров W может быть очень большим, так как самые большие модели глубокого обучения имеют триллион параметров. Идея заключается в том, что на каждом шаге процесса вы обновляете свои параметры, применяя небольшое количество градиента. Eta - это скорость обучения, небольшое число, обычно между 0 и 1, часто около 0,01. Nabla Q - это градиент для частичной функции потерь Qi. Удивительно, этот процесс работает хорошо.

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

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

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

Что также интересно в градиентном спуске, так это то, что это стохастический процесс, но он может бесплатно справляться со стохастическими проблемами. Если Qi - стохастическая функция с шумом и дает случайный результат, который меняется при каждом ее вычислении, вам даже не нужно менять ни одну строку алгоритма. Стохастический градиентный спуск является особо интересным, потому что он дает вам нечто, что полностью соответствует парадигме, которая актуальна для целей цепочки поставок.

Второй вопрос: откуда берется градиент? У нас есть программа, и мы просто берем градиент частичной функции потерь, но откуда берется этот градиент? Как получить градиент для произвольной программы? Оказывается, есть очень элегантная, минималистическая техника, открытая давно, называемая автоматическим дифференцированием.

Автоматическое дифференцирование появилось в 1960-х годах и было усовершенствовано со временем. Существуют два типа: прямой режим, открытый в 1964 году, и обратный режим, открытый в 1980 году. Автоматическое дифференцирование можно рассматривать как трюк компиляции. Идея заключается в том, что у вас есть программа для компиляции, и с помощью автоматического дифференцирования у вас есть ваша программа, которая представляет функцию потерь. Вы можете перекомпилировать эту программу, чтобы получить вторую программу, и выход второй программы не является функцией потерь, а градиентами всех параметров, участвующих в вычислении функции потерь.

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

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

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

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

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

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

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

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

Как и в случае с глубоким обучением, проблема состоит из двух частей: дифференцируемое программирование в качестве базового уровня и оптимизация или техники обучения поверх этого. Сообщество глубокого обучения стремится определить архитектуры, которые хорошо работают с дифференцируемым программированием, такие как трансформеры. Аналогично, необходимо определить архитектуры, которые хорошо работают для целей оптимизации. Это то, что было сделано для изучения игры в Го или шахматы в высококомбинаторных средах. Мы обсудим техники, которые хорошо работают для оптимизации, специфичной для цепей поставок, в последующих лекциях.

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

Теперь давайте посмотрим на вопросы.

Вопрос: Является ли переход к вычислительным методам предварительным навыком в операционной деятельности, и станут ли операционные роли устаревшими, или наоборот?

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

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

Что касается устаревания операционных ролей, если ваша роль заключается в ручной обработке таблиц Excel spreadsheets весь день, то да, ваша роль, скорее всего, устареет. Эта проблема была известна с 1979 года, когда Расселл Аккофф опубликовал свою статью. Проблема заключается в том, что люди знали, что этот метод принятия решений не является будущим, но он оставался статус-кво на очень долгое время. Суть проблемы заключается в том, что компании должны понять экспериментальный процесс. Я считаю, что будет переход, когда компании начнут восстанавливать эти навыки. Многие крупные североамериканские компании после Второй мировой войны имели некоторые знания в области исследований операций среди своих руководителей. Это была горячая новая тема, и советы директоров крупных компаний знали вещи об исследованиях операций. Как отмечает Расселл Аккофф, из-за отсутствия результатов эти идеи были смещены вниз по иерархии компании, пока они полностью не были аутсорсингованы, так как они были в основном несущественными и не давали осязаемых результатов. Я считаю, что исследования операций вернутся только тогда, когда люди извлекут уроки из того, почему классическая эра исследований операций не дала результатов. CIO внесет лишь скромный вклад в это дело; это в основном вопрос переосмысления добавленной стоимости людей внутри компании.

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

Вопрос: Что насчет использования солвера Excel для минимизации значения MRMSC и нахождения оптимального значения для альфа, бета и гамма?

Я считаю, что этот вопрос актуален для случая Хольта-Уинтерса, где вы действительно можете найти решение с помощью поиска по сетке. Однако что происходит в этом солвере Excel? Это градиентный спуск или что-то еще? Если вы имеете в виду линейный солвер Excel, то это нелинейная проблема, поэтому Excel не может ничего сделать для вас в этом случае. Если у вас есть другие солверы в Excel или дополнения, то да, они могут работать, но это очень устаревшая точка зрения. Она не принимает во внимание более стохастическое представление; прогноз, который вы получаете, является непробабильным прогнозом, что является устаревшим подходом.

Я не говорю, что нельзя использовать Excel, но вопрос в том, какие возможности программирования открываются в Excel? Можете ли вы использовать стохастический градиентный спуск в Excel? Возможно, если вы добавите специальное дополнение. Excel позволяет вам подключать любую произвольную программу поверх него. Можете ли вы потенциально использовать дифференцируемое программирование в Excel? Да. Хорошая идея ли это делать в Excel? Нет. Чтобы понять почему, вам нужно вернуться к концепции поставки программного обеспечения, ориентированного на продукт, которая подробно описывает, что идет не так с Excel. Это сводится к модели программирования и возможности поддерживать вашу работу со временем совместными усилиями команды.

Вопрос: Задачи оптимизации обычно смещены в сторону маршрутизации транспортных средств или прогнозирования. Почему бы не рассмотреть оптимизацию всей цепочки поставок? Разве это не позволит снизить затраты по сравнению с изолированными областями?

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

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

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

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

Вопрос: Какие могут быть применения задач оптимизации, отличные от линейного программирования, целочисленного программирования, смешанного программирования и в случае Вебера и стоимости товаров?

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

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

Когда вы спрашиваете о применении задач оптимизации, я приглашаю вас посмотреть все мои лекции о персонажах цепочки поставок personas. У нас уже есть серия персонажей цепочки поставок, и я перечисляю буквально тонны проблем, которые можно решить с помощью математической оптимизации. В лекциях о персонажах цепочки поставок у нас есть Париж, Майами, Амстердам и мировая серия, и их будет еще больше. У нас много проблем, которые нужно решать и которые заслуживают подхода с точки зрения правильной математической оптимизации. Однако вы увидите, что для каждой из этих проблем вы не сможете сформулировать их в рамках супер жестких и в основном странных ограничений, которые возникают из этих математических фреймворков. Опять же, эти математические фреймворки в основном основаны на выпуклости, и это не правильная перспектива для цепочки поставок. Большинство проблем, с которыми мы сталкиваемся, являются невыпуклыми. Но это нормально; это не значит, что они невозможно сложные. Вы видите, дело в том, что вашему боссу или вашей компании важна прибыль, а не то, есть ли у вас математическое доказательство, подтверждающее принятое решение. Им важно то, что вы можете принять правильное решение в терминах производства, пополнения запасов, цен, ассортимента и тому подобного, а не то, что у вас есть математическое доказательство, прикрепленное к этим решениям.

Вопрос: Как долго должны храниться данные обучающего алгоритма для помощи в обучении?

Я бы сказал, учитывая, что хранение данных в настоящее время невероятно дешево, почему бы не хранить их вечно? Хранение данных настолько недорогое; например, просто зайдите в супермаркет, и вы увидите, что цена на жесткий диск объемом один терабайт составляет около 60 или что-то в этом роде. Так что это невероятно дешево.

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

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

Вопрос: Многокритериальное программирование - это функция двух или более целей, таких как сумма или минимизация нескольких функций в одной цели?

Существует несколько вариантов подхода к многокритериальному программированию. Здесь не речь идет о функции, которая является суммой, потому что если у вас есть сумма, то это просто вопрос декомпозиции и структуры функции потерь. Нет, здесь речь идет о векторе. И действительно, существует несколько вариантов многокритериального программирования. Самый интересный вариант - это тот, где вы хотите получить лексикографическое упорядочение. Что касается цепочки поставок, то минимизация, когда вы хотите сказать, что вы берете среднее или максимум из многих функций, может быть интересной, но я не очень уверен. Я считаю, что многокритериальный подход, при котором вы можете вводить ограничения и рассматривать их как часть вашей обычной оптимизации, очень интересен с точки зрения цепочки поставок. Другие варианты также могут быть интересны, но я не уверен. Я не говорю, что они не интересны; я просто говорю, что не уверен.

Вопрос: Как бы вы решили, когда использовать приближенное решение вместо оптимизированного решения?

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

Вопрос: Почему временной ряд, с точки зрения исторических данных, в первую очередь делится на 86 400?

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

Но то, на что я указываю, в значительной степени произвольно. Вы можете решить представить данные в виде ежедневных данных, но вы можете решить представить данные по секундам. Было бы ли когда-нибудь иметь смысл представлять данные по секундам? Ответ - да, это зависит от типа проблем. Например, если вы являетесь поставщиком электроэнергии и хотите управлять сетью, то вам нужно управлять мощностью каждую секунду, чтобы у вас был точный баланс между предложением электроэнергии в вашей сети и потреблением энергии. И этот баланс настраивается по секунде. Таким образом, могут возникнуть ситуации, когда имеет смысл представлять данные по секундам. Для продажи в вашем местном магазине это может не иметь смысла. Что я хотел указать с помощью числа 86 400, кстати, это просто 24 часа умножить на 60 минут умножить на 60 секунд, и я хотел прояснить тот факт, что у вас всегда есть представление ваших данных, и вы не должны путать представление ваших данных, которое имеет определенную размерность, с внутренней размерностью ваших данных, которая может иметь совершенно другую размерность. Представление в значительной степени является произвольным и произвольным. Оно дает вам числовой индикатор, такой как наличие трехлетних данных, чтобы у вас был вектор размерностью тысяча. Но эта тысяча в значительной степени является произвольной, потому что она основана на решении агрегировать данные ежедневно. Если вы выбрали любой другой альтернативный период, вы получите другую размерность. Вот что я хотел сказать, и в этом действительно правильно понял глубокое обучение: иметь такие другие вещи, где вы не путаетесь из-за произвольных выборов представления данных. Вы хотите быть своего рода независимым от представления.

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

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

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

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

Ссылки

• Будущее операционного исследования - это прошлое, Рассел Л. Аккофф, февраль 1979 года
• LocalSolver 1.x: черный ящик локального поиска для 0-1 программирования, Тьерри Бенуа, Бертран Эстеллон, Фредерик Гарди, Ромен Мегель, Карим Нуиуа, сентябрь 2011 года
• Автоматическое дифференцирование в машинном обучении: обзор, Атилим Гунес Байдин, Барак А. Перлмуттер, Алексей Андреевич Радул, Джеффри Марк Сискинд, последнее обновление февраль 2018 года