サプライチェーンの数理最適化 - 講義4.3

8月 25, 2021

supply chain lectures

00:18 イントロダクション
02:18 バックグラウンド
12:08 なぜ最適化するのか？1/2 Holt-Winters法による予測
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 今後の講義と視聴者の質問

説明

数理最適化は数学的な関数を最小化するプロセスです。ほとんどの現代の統計学習技術（つまり、サプライチェーンの視点を採用した予測）は、その中核に数理最適化を依存しています。さらに、予測が確立された後、最も利益の高い意思決定も、その中核に数理最適化を依存しています。サプライチェーンの問題は多くの変数を含みます。また、通常は確率的な性質を持ちます。数理最適化は現代のサプライチェーンの実践の基盤です。

フルトランスクリプト

スライド1

このサプライチェーン講義シリーズへようこそ。私はジョアネス・ヴェルモレルです。今日は「サプライチェーンの数理最適化」を紹介します。数理最適化は、与えられた問題に対して最適な解を特定するための明確で形式化された、計算可能な方法です。すべての予測問題は数理最適化問題と見なすことができます。サプライチェーン内外のすべての意思決定状況も、数理最適化問題と見なすことができます。実際、数理最適化の視点は、私たちの現代の世界観に非常に根付いており、数理最適化パラダイムによって与えられる非常に小さな枠外で「最適化」という動詞を定義することは非常に困難になっています。

数理最適化に関する科学文献は広範であり、数理最適化のツールを提供するソフトウェアエコシステムも同様です。残念ながら、サプライチェーンに関連するとしても、それらのほとんどは非常に役に立たず関連性がありません。この講義の目標は2つあります。まず、サプライチェーンの視点から、数理最適化にどのようにアプローチして、実用的で価値のあるものを得るかを理解することです。2つ目の要素は、この広大な領域の中で、見つけることができる最も価値のある要素のいくつかを特定することです。

スライド2

数理最適化の形式的な定義は簡単です。通常、損失関数と呼ばれる関数を考えます。この関数は実数値であり、単に数値を生成します。求めるのは、損失関数を最小化する最適な値を表す入力（X0）を特定することです。これが通常の数理最適化のパラダイムであり、見かけによらずシンプルです。この一般的な視点については、多くのことが言えることを見ていきます。

この分野は、私が応用数理最適化の観点で考えると、主にオペレーションズリサーチという名前で開発されました。オペレーションズリサーチは、20世紀の1940年代から1970年代末までのクラシックなオペレーションズリサーチとしてより具体的に定義されます。クラシックなオペレーションズリサーチは、数理最適化と比較して、実際のビジネス問題に関心を持っていました。数理最適化は最適化問題の一般的な形式に関心を持ちますが、問題がどのようなビジネス的意義を持つかにはあまり関心を持ちません。それに対して、クラシックなオペレーションズリサーチは、ビジネスに重要な問題に最適化を行っていました。

興味深いことに、オペレーションズリサーチから数理最適化への移行は、20世紀初頭に将来の経済活動レベルの一般的な予測に関心を持つ分野として登場した予測からの移行とほぼ同じように行われました。このドメインは、より広範な範囲の問題について予測を行うことに関心を持つ機械学習によって実質的に置き換えられました。オペレーションズリサーチから数理最適化への移行は、予測から機械学習への移行と同様の遷移を大まかに行ったと言えます。さて、クラシックなオペレーションズリサーチの時代が70年代末まで続いたと言ったとき、私は非常に具体的な日付を考えていました。1979年2月、ラッセル・アッコフは「オペレーションズリサーチの未来は過去である」という驚くべき論文を発表しました。この論文を理解するためには、最適化科学の歴史において本当に画期的なものと考えられるこの論文を理解するために、ラッセル・アッコフが実質的にオペレーションズリサーチの創始者の一人であることを理解する必要があります。

この論文を発表したとき、彼はもはや若い人ではありませんでした。彼は1919年に生まれ、ほぼ彼のキャリア全体をオペレーションズリサーチに取り組んで過ごしました。彼が論文を発表したとき、彼はオペレーションズリサーチが失敗したと述べました。それだけでなく、結果を出すことができなかっただけでなく、業界への関心も減少していたため、20年前のフィールドよりも90年代末には関心が低下していました。

理解するのに非常に興味深いことは、その原因は、当時のコンピュータが現在のコンピュータよりもはるかに弱かったという事実ではありません。問題は、処理能力の制限とは関係ありません。これは70年代末です。コンピュータは現在のものと比べて非常に控えめですが、合理的な時間枠内で数百万の算術演算を実行できます。問題は、処理能力の制限に関連していないことです。特に、処理能力が驚くほど速く進歩している時代においてはそうです。

ところで、この論文は素晴らしい読み物です。オーディエンスにはぜひ読んでいただきたいと思います。お気に入りの検索エンジンで簡単に見つけることができます。この論文は非常にアクセスしやすく、よく書かれています。アッコフがこの論文で指摘する問題の種類は、40年後の現在でも非常に強く響いており、多くの点で、この論文は現代のサプライチェーンにまだ悩みを抱えている多くの問題について非常に先見的です。

では、問題は何でしょうか？関数を最適化するこのパラダイムでは、最適化プロセスがいくつかの良い解または最適解を特定することを証明できます。しかし、実際に最適化している損失関数がビジネスにとって興味深いものであることをどのように証明しますか？最適化しているものが実際には空想である場合はどうでしょうか？最適化しようとしているものが、最適化しようとしているビジネスの現実と何の関係もない場合はどうでしょうか？

ここに問題の核心があり、ここに初期の試みがすべて失敗した理由があります。ビジネスの利益を表す数学的な表現を作り出すと、得られるものは数学的な空想です。これは、Russell Ackoffがこの論文で指摘していることです。彼は長い間このゲームをしてきたキャリアの中で、これが実質的にどこにもつながらないことを認識しています。彼はこの論文で、この分野が失敗したという見解を共有し、診断を提案しますが、解決策はほとんど提供しません。非常に興味深いことに、非常に尊敬され、認められた研究者の創始者の一人が、この研究の分野全体が行き詰まりだと言っています。彼はまだかなり長い人生を送りますが、ビジネス最適化の定量的な視点から質的な視点に完全に移行します。この転機の後、彼の人生の最後の30年間は質的な手法に取り組み、非常に興味深い研究を行います。

さて、この講義シリーズに関しては、Russell Ackoffが運用研究について指摘しているポイントは現在でも非常に有効です。実際に、私はAckoffが指摘していた最大の問題に既に取り組み始めており、当時の彼や彼の同僚は解決策を提供することができませんでした。彼らは問題を診断することはできましたが、解決策はありませんでした。この講義シリーズでは、私が提案している解決策は方法論的な性質です。Ackoffが指摘しているように、運用研究の視点には深刻な方法論的な問題があります。

私が提案する方法は基本的に2つあります。一方はサプライチェーンの人員であり、もう一方は数学的最適化に非常に補完的な実験的最適化という方法です。また、ビジネスの関心やビジネスの関連性を主張する運用研究とは異なり、私が今日問題に取り組む方法は、運用研究の視点やレンズではありません。私は数学的最適化の視点から問題に取り組んでおり、それをサプライチェーンの純粋な補助科学と位置付けています。数学的最適化にはサプライチェーンにとって本質的に基本的なものは何もありません。それは基礎的な興味の対象にすぎません。それは手段であり、目的ではありません。それが異なる点です。ポイントは非常にシンプルかもしれませんが、実際には予測グレードの結果を実現する際に非常に重要です。

では、まずなぜ最適化を行いたいのでしょうか？ほとんどの予測アルゴリズムは、数学的最適化問題を中心にしています。この画面に表示されているのは非常にクラシックな乗算型のHolt-Winters時系列予測アルゴリズムです。このアルゴリズムは主に歴史的な興味の対象です。現代のサプライチェーンには、この特定のアルゴリズムを活用することはお勧めしません。しかし、簡単さのために、これは非常にシンプルなパラメトリックな方法であり、非常に簡潔で、実際には1つの画面にまとめることができます。それほど冗長ではありません。

画面に表示されているすべての変数は、単なる数値です。ベクトルは関与していません。基本的に、Y(t)は推定値であり、これが時系列予測です。ここでは、H期先を予測しています。Hはホライズンのようなものです。そして、実際にはY(t)で作業していると考えることができます。週次集計された販売データや月次集計された販売データなどを考えることができます。このモデルには3つのコンポーネントがあります。レベルを表すLt、トレンドを表すBt、季節性のコンポーネントを表すStです。Holt-Wintersモデルを学習したいと言うとき、3つのパラメーター、アルファ、ベータ、ガンマがあります。これらの3つのパラメーターは、基本的に0から1までの数値です。つまり、3つのパラメーターの適切な値を特定するだけで、Holt-Wintersアルゴリズムを適用することになります。アイデアは、これらのパラメーター、アルファ、ベータ、ガンマが、予測のために指定したエラーを最小化する場合に最適であるということです。この画面では、非常にクラシックな平均二乗誤差が表示されています。

数理最適化についてのポイントは、α、β、およびγの適切なパラメータ値の同定方法を考案することです。何ができるでしょうか？まず、最も簡単で単純な方法は、グリッドサーチのようなものです。グリッドサーチでは、すべての値を探索することになります。これらは分数の数値なので、無限の数の値があります。したがって、解像度を選択します。例えば、0.1のステップで進めることにします。0から1の間に3つの変数があるので、0.1ずつ進めます。これにより、約1,000回の反復が必要になります。これにより、最適な値を特定することができます。

しかし、この解像度はかなり弱いです。0.1では、パラメータのスケールに対して約10％の解像度が得られます。したがって、より良い解像度である0.01を選択することができます。これは1％の解像度です。しかし、それを行うと、組み合わせの数が爆発的に増加します。組み合わせの数が1,000から1,000,000になります。これがグリッドサーチの問題です。非常に速く、組み合わせの壁にぶつかり、膨大な数のオプションが生じます。

数理最適化は、問題に投入する計算リソースの量に対して、より効果的な解を得るアルゴリズムを考案することです。単なるブルートフォースの探索よりもはるかに優れた解を得ることはできるでしょうか？答えは、はい、絶対に可能です。

では、この場合に実際により良い解を得るためには、どのような方法があるでしょうか？まず、いくつかの勾配を使用することができます。Holt-Wintersの全体的な式は、1つの除算を除いて完全に微分可能です。この除算は比較的簡単に処理できる特殊なケースです。したがって、この式全体、損失関数を含めて、完全に微分可能です。勾配を使用して探索を誘導することができます。

別のアプローチとしては、実際の供給チェーンでは、多くの時系列データがあるかもしれません。したがって、すべての個々の時系列データを独立して扱う代わりに、最初の1,000の時系列データに対してグリッドサーチを行い、投資を行い、alpha、beta、およびgammaの組み合わせを特定します。その後、他のすべての時系列データに対しては、この候補のショートリストから最適な解を選択します。

ご覧のように、純粋なグリッドサーチアプローチよりもはるかに優れた方法はたくさんあります。数理最適化の本質は、さまざまな意思決定問題も通常数理最適化問題として見ることができます。

例えば、画面に表示されている車両ルーティング問題は、数理最適化問題として見ることができます。これはポイントのリストを選ぶことに関するものです。問題の形式的なバージョンは書きませんでしたが、それは比較的変動するものであり、多くの洞察をもたらしません。しかし、考えてみると、「ポイントがあり、各ポイントにスコアとしての擬似ランクを割り当てることができ、すべてのポイントを擬似ランクの昇順でソートするアルゴリズムがあり、それが私のルートです」と考えることができます。アルゴリズムの目標は、最適なルートを与えるための擬似ランクの値を特定することです。

この問題では、グリッドサーチはまったく選択肢ではありません。ポイントが数十個あり、すべての組み合わせを試すと非常に大きくなります。また、勾配も役に立ちません。少なくとも、この種の問題に対して明らかな勾配降下法は存在しません。

しかし、このような問題に取り組む場合、文献で特定された非常に強力なヒューリスティックが存在することがわかります。たとえば、1958年にCroesによって発表された2-optヒューリスティックは、非常にシンプルなヒューリスティックを提供します。ランダムなルートから始め、このルートで交差が発生するたびに交差を解消するための置換を適用します。つまり、ランダムなルートから始め、最初の交差が観察されたら、交差を解消するための置換を行い、それを繰り返します。ヒューリスティックを使用してプロセスを繰り返し、交差が残らなくなるまで繰り返します。この非常にシンプルなヒューリスティックからは、非常に良い解が得られます。真の数学的意味で最適ではないかもしれませんが、非常に良い解を比較的少ない計算リソースで得ることができます。

2-optヒューリスティックの問題は、非常に優れたヒューリスティックですが、この1つの問題に特化しすぎています。数学的最適化にとって本当に興味深いのは、1つの特定のバージョンの問題に対してのみ機能するヒューリスティックではなく、大きな問題クラスに対して機能する方法を特定することです。したがって、非常に一般的な方法を持ちたいのです。

スライド5

これまでの講義シリーズの経緯：この講義はシリーズの一部であり、この章はサプライチェーンの補助科学に捧げられています。最初の章では、サプライチェーンについての私の考えを学問として、そして実践として紹介しました。2章では方法論に焦点を当て、特に実験的最適化という非常に関連性の高い方法論を紹介しました。それは、数十年前にラッセル・アコフによって特定された非常に妥当な問題に対処するための鍵です。3章は完全にサプライチェーンの人員に捧げられています。この講義では、解決策と問題を混同するのではなく、解決する問題を特定することに焦点を当てています。この第4章では、サプライチェーンの補助科学をすべて調査しています。ハードウェアの最低レベルからアルゴリズムのレベル、そして数学的最適化のレベルまで、抽象化のレベルで進んでいます。

スライド6

補助科学についての簡単なまとめ：それらはサプライチェーン自体についての視点を提供します。この講義はサプライチェーンそのものではなく、サプライチェーンの補助科学の1つについてです。この視点は、古典的な運用研究の視点とは大きく異なります。古典的な運用研究は目的そのものであるのに対して、数学的最適化は手段であり、少なくともサプライチェーンに関しては目的そのものではありません。数学的最適化はビジネスの具体的な事項には関心を持ちませんし、数学的最適化とサプライチェーンの関係は、化学と医学の関係に似ています。現代の視点からは、優れた医師であるためには優れた化学者である必要はありませんが、化学について何も知らないと主張する医師は怪しいと思われるでしょう。

スライド7

数学的最適化は問題が既知であることを前提としています。問題の妥当性には関心がありませんが、最適化の観点からは、与えられた問題に対して最大限の利益を得ることに焦点を当てています。ある意味では、それは顕微鏡のようなものです。非常に強力ですが、非常に狭い焦点を持っています。運用研究の将来についての議論に戻ると、顕微鏡を間違った場所に向けると、興味深いが最終的には関係のない知的な課題に気を取られる可能性があります。

そのため、数学的最適化は実験的最適化と組み合わせて使用する必要があります。前の講義で説明した実験的最適化は、実世界からのフィードバックを受けながら問題自体の改善バージョンに向けて反復するプロセスです。実験的最適化は、解決策ではなく問題自体を変異させるプロセスであり、反復的に良い問題に収束することができます。これが問題の核心であり、当時のラッセル・アッコフと彼の仲間たちが解決策を持っていなかった場所です。彼らは与えられた問題を最適化するためのツールを持っていましたが、問題が良いまで問題を変異させるためのツールを持っていませんでした。実際の世界からのフィードバックを受けずに象牙の塔で数学的な問題を書くと、得られるものは幻想です。実験的最適化プロセスを開始するときの出発点は、ただの幻想です。それを機能させるためには、実際の世界のフィードバックが必要です。数学的最適化と実験的最適化の間を行き来することが目的です。実験的最適化プロセスの各段階で、数学的最適化ツールを使用します。目標は、計算リソースとエンジニアリングの努力を最小限に抑え、プロセスが次のバージョンの問題に向かって反復できるようにすることです。

スライド8

この講義では、まず数学的最適化の視点を洗練させます。形式的な定義は見かけによらず単純ですが、供給チェーンの目的において実用的な関連性を実現するために意識する必要がある複雑さがあります。次に、数学的最適化の最先端を代表する2つの広範なソルバーを探求します。

スライド9

まず、凸性と数学的最適化の初期の研究について説明しましょう。運用研究は最初に凸損失関数に焦点を当てました。関数が凸であるとは、特定の性質を満たすと言われています。直感的には、関数が凸であるとは、関数によって定義される多様体上の任意の2点について、それらの点を結ぶ直線は、それらの点の間で関数が取る値よりも常に上にあるということです。

凸性は真の数学的最適化を可能にするための鍵です。直感的には、凸関数を持つとき、関数の任意の点（任意の候補解）について、周囲を見回して下降できる方向を常に見つけることができます。どこから始めても常に下降でき、下降は常に良い動きです。下降できない唯一の点は、本質的に最適な点です。ここでは簡略化していますが、非一意の解や解が存在しない場合など、いくつかの例外的なケースもあります。しかし、いくつかの例外的なケースを除いて、凸関数では最適な点以外でさらに最適化することは常にできます。それ以外の場合は常に下降でき、下降は良い動きです。

凸関数に関する大量の研究が行われ、さまざまなプログラミングパラダイムが年々登場しています。LPは線形計画法を表し、他のパラダイムには二次錐計画、幾何計画（多項式を扱う）、半正定計画（正の固有値を持つ行列を含む）、幾何錐計画などがあります。これらのフレームワークは、構造化された凸問題を扱う共通点があります。損失関数と解の制約の両方が凸であるという点です。

これらのフレームワークは非常に高い関心を持っており、多くの科学的文献が生み出されています。しかし、その見た目に反して、これらのパラダイムは非常に表現力がありません。単純な問題でも、これらのフレームワークの能力を超えています。例えば、1960年代の基本的な予測モデルであるホルト・ウィンタースのパラメータの最適化は、これらのフレームワークのどれもできることを超えています。同様に、車両ルーティング問題や巡回セールスマン問題など、単純な問題もこれらのフレームワークの能力を超えています。

だから最初に言ったように、膨大な文献が存在する一方で、実際にはほとんど活用されていません。最適点以外には、さらに下降することはできません。ここでは簡略化していますが、非一意の解や解が存在しないエッジケースもあります。しかし、いくつかのエッジケースを除いて、凸関数では最適点以外は常に下降できますし、下降は良い選択です。

凸関数に関する研究は非常に多くあり、年々さまざまなプログラミングパラダイムが登場しています。LPは線形計画法を表し、他のパラダイムには二次錐計画法、幾何計画法（多項式を扱う）、半正定計画法（正の固有値を持つ行列を含む）、幾何錐計画法などがあります。これらのフレームワークは、構造化された凸問題に取り組む共通点があります。損失関数と解の制約の両方が凸です。

これらのフレームワークは非常に高い関心を持っており、多くの科学的文献が生み出されています。しかし、その見た目に反して、これらのパラダイムは非常に表現力がありません。単純な問題でも、これらのフレームワークの能力を超えています。例えば、1960年代の基本的な予測モデルであるホルト・ウィンタースのパラメータの最適化は、これらのフレームワークのどれもできることを超えています。同様に、車両ルーティング問題や巡回セールスマン問題など、単純な問題もこれらのフレームワークの能力を超えています。

だから最初に言ったように、膨大な文献が存在する一方で、実際にはほとんど活用されていません。問題の一部は、純粋な数学的最適化ソルバーに焦点を当てていたことです。これらのソルバーは数学的な観点から非常に興味深いですが、おもちゃのような問題や完全に作り上げた問題にしか使用できません。現実世界では失敗し、ここ数十年間、これらの分野ではほとんど進展がありませんでした。サプライチェーンに関しては、いくつかのニッチを除いて、これらのソルバーに関連性があるものはほとんどありません。

オペレーションリサーチの古典時代に完全に無視されていたもう一つの側面は、ランダム性です。ランダム性または確率論は、2つの根本的に異なる方法で重要です。最初の方法は、ソルバー自体でランダム性を取り扱う必要があることです。現在では、最先端のソルバーは内部で広範に確率過程を利用しています。これは完全に決定論的なプロセスを持つこととは対照的で非常に興味深いです。数学的最適化技術を実装するソフトウェアの一部であるソルバーの内部動作について話しています。

最先端のソルバーが広範に確率過程を利用する理由は、現代のコンピューティングハードウェアの存在方法に関係があります。解を探索する際のランダム性の代替手段は、過去に行ったことを覚えておくことで、同じループにはまらないようにすることです。覚えておく必要がある場合、メモリを消費します。問題は、多くのメモリアクセスを行う必要があることです。ランダム性を導入する方法は、通常、ランダムなメモリアクセスの必要性を大幅に軽減する方法です。

プロセスを確率的にすることで、最適化したい問題の可能な解の中でテスト済みまたは未テストのデータベースを調査する必要がなくなります。少しランダムに行いますが、完全にはランダムではありません。これはほとんどの現代のソルバーにおいて重要な要素です。確率的プロセスを持つことのいくつかの直感に反する側面の一つは、確率的なソルバーを持つことができる一方で、出力はまだかなり決定論的であることです。これを理解するために、ふるいのシリーズの類推を考えてみてください。ふるいは基本的に物理的な確率過程であり、ランダムな動きを適用してふるい分けが行われます。プロセスは完全に確率的ですが、結果は完全に決定論的です。最終的に、ふるい分けプロセスから完全に予測可能な結果を得ることができます。プロセス自体は基本的にランダムであったにもかかわらず、これが適切に設計された確率的ソルバーで起こることです。これは現代のソルバーの重要な要素の一つです。

ランダム性に関連するもう一つの側面は、問題自体の確率的な性質です。これは、古典的な運用研究の時代にはほとんど存在しませんでした。つまり、損失関数がノイズを含んでおり、それに関するどんな測定値もある程度のノイズを持つという考え方です。これはほとんどの場合、サプライチェーンにおいて当てはまります。なぜなら、サプライチェーンでは、意思決定を行う際には将来の出来事を予測しているからです。何かを購入することを決めるのは、将来その商品が必要になると予測しているからです。未来は書かれていないので、将来についての洞察を持つことはありますが、その洞察は完璧ではありません。今日生産するというあなたの意思決定の品質は、将来の不確実な状況に依存しており、したがって、サプライチェーンで行うすべての意思決定は、制御できないこれらの将来の状況に依存して変動する損失関数を持つことになります。将来の出来事との関連で生じるランダム性は、削減できないものであり、それは基本的に確率的な問題を扱っていることを意味します。

しかし、古典的な数学的ソルバーに戻ると、この側面は完全に欠落していることがわかります。これは大きな問題です。なぜなら、数学的最適化を適用したい問題は、確率的な性質を持つものになるからです。私は損失関数のノイズについて話しています。

ある異議があります。確率的な問題がある場合、サンプリングを通じてそれを確定的な問題に変換することが常にできます。ノイズのある損失関数を10,000回評価すれば、ほぼ確定的な損失関数を得ることができます。しかし、このアプローチは非常に効率が悪いです。なぜなら、最適化プロセスに10,000倍のオーバーヘッドを導入するからです。数学的最適化の視点は、限られた計算リソースで最良の結果を得ることに関するものです。問題を解決するために無限に多くの計算リソースを投資することではありません。私たちは有限な計算リソースを扱わなければなりません。それがかなり大きい量であってもです。したがって、後でソルバーを見る際には、確定的なアプローチにデフォルトで戻るのではなく、確率的な問題を本来的に理解できるソルバーを持つことが最も重要です。

もう一つの重要な視点は、多目的最適化です。数学的最適化問題の単純な表現では、損失関数は基本的に単一の値であると述べました。しかし、もし値のベクトルがある場合、すべてのベクトルの辞書順に最も低い点を与える解を見つけたいとします。例えば、f1、f2、f3などです。

なぜサプライチェーンの観点からこれが興味深いのでしょうか？実際のところ、この多目的の視点を採用すると、すべての制約を専用の損失関数として表現することができます。制約があるのはなぜでしょうか？サプライチェーンには制約がたくさんあります。例えば、購入注文をする場合、商品が到着したときに倉庫に十分なスペースがあることを確認する必要があります。したがって、ストレージスペース、生産能力などに制約があります。制約を特別なケースとして扱うソルバーを持つよりも、多目的最適化に対応できるソルバーを持ち、制約を目的の一つとして表現する方が興味深いです。制約違反の数を数え、それを最小化し、違反数をゼロにすることが目標です。

このマインドセットがサプライチェーンにとって非常に関連性がある理由は、サプライチェーンが直面する最適化問題が暗号パズルではないからです。これらは、解があるかどうかであり、それが良い解であるかどうかであるような非常に厳密な組み合わせ問題ではありません。サプライチェーンでは、制約を満たす解と呼ばれることが一般的には非常に簡単です。制約を満たす解を特定することは大変な作業ではありません。非常に困難なのは、制約を満たすすべての解の中から、ビジネスにとって最も利益が高い解を特定することです。ここが非常に難しいところです。制約を違反しない解を見つけることは非常に簡単です。これは他の分野では異なります。例えば、産業設計の数理最適化では、携帯電話内部の部品配置を行いたい場合です。これは非常に厳密に制約された問題であり、1つの制約を犠牲にして携帯電話に小さな突起を持たせることはできません。これは非常に厳密で組み合わせ的な問題であり、制約をまず最優先に扱う必要があります。これは、サプライチェーンのほとんどの問題には必要ないと私は考えています。したがって、多目的最適化に対応できる技術を持つことは非常に興味深いです。

スライド12

さて、ソルバーの設計についてもう少し詳しく話しましょう。非常に広範な問題のクラスに対して解を生成するソフトウェアを設計するために、2つの非常に注目すべき設計要素があります。最初の要素は、ホワイトボックスまたはブラックボックスの観点で操作するかどうかです。ブラックボックスの観点では、任意のプログラムを処理できるため、損失関数は任意のプログラムになります。私たちは気にしません。私たちが望むのは、プログラムを評価し、仮の解の値を取得できるプログラムだけです。一方、ホワイトボックスのアプローチは、損失関数自体に私たちが調査し活用できる構造があることを強調します。損失関数の内部を見ることができます。ちなみに、前のスライドで凸性について話していたとき、それらのモデルと純粋な数学的なソルバーは本当にホワイトボックスのアプローチでした。それらはホワイトボックスアプローチの極端なケースであり、問題の内部を見ることができるだけでなく、問題が非常に狭い形式であるような半正定計画法のような非常に厳格な構造を持っています。ただし、数学的なフレームワークほど厳格ではないものを採用する場合でも、ホワイトボックスの一部として、勾配のようなものがあるとします。損失関数の勾配は非常に興味深いものです。突然、降下する方向を知ることができます。単純な勾配降下法が良い結果を保証する凸問題を持っていなくてもです。経験則として、ソルバーをホワイトボックス化できる場合、ブラックボックスソルバーと比較して桁違いにパフォーマンスが向上します。

さて、2番目の側面として、オフラインとオンラインのソルバーがあります。オフラインのソルバーは通常バッチで動作するため、問題を実行し、完了するまで待つ必要があります。この時点で、ソルバーが完了すると、最良の解決策または最良の特定された解決策が得られます。それに対して、オンラインのソルバーは、よりベストエフォートのアプローチで動作します。それは通過可能な解決策を特定し、時間が経過し、より多くの計算リソースを投資するにつれて、より良い解決策に向けて反復します。本当に興味深いのは、オンラインのソルバーで問題に取り組むと、いつでもプロセスを一時停止して早期の候補解を得ることができるということです。プロセスを再開することさえできます。数学的なソルバーに戻ると、通常はプロセスの終了まで待たなければなりません。

供給チェーンの世界での運営は非常に波乱万丈なものになることがありますが、これはこのシリーズの以前の講義で取り上げられています。通常、数時間かけてこの数学的最適化プロセスを実行する余裕がある場合もありますが、ITの問題、現実世界の問題、または供給チェーンの緊急事態が発生することもあります。そのような場合、通常3時間かかる作業を5分後に中断して回答を提供できると、命綱になります。たとえ悪い回答であっても、何も回答がないよりはずっと良いです。軍隊には「最悪の計画は計画がないこと」という言葉がありますので、何もないよりも大まかな計画を持つ方が良いです。これがオンラインのソルバーが提供するものです。これらは、以下の議論で心に留めておくべき重要な設計要素です。

さて、数学的最適化に取り組むこの講義の最初のセクションを締めくくるために、ディープラーニングのレッスンを見てみましょう。ディープラーニングは機械学習の分野において完全な革命を起こしました。しかし、その核心には数学的最適化の問題もあります。私は、ディープラーニングが数学的最適化自体に革命をもたらし、最適化問題を見る方法を完全に変えたと考えています。ディープラーニングは、数学的最適化の最先端として考えられるものを再定義しました。

現在、最大のディープラーニングモデルは1兆以上のパラメータを扱っています。これは1,000億を超えるものです。ちなみに、ほとんどの数学的ソルバーは、1,000の変数すら扱うのに苦労し、数万の変数で崩壊する傾向があります。どれだけの計算ハードウェアを投入してもです。それに対して、ディープラーニングは、大量の計算リソースを使用しているとは言え、実現可能です。1兆以上のパラメータを持つプロダクションのディープラーニングモデルがあり、それらのパラメータは最適化されています。つまり、1兆のパラメータにスケールする数学的最適化プロセスがあるということです。これは非常に驚くべきことであり、クラシックな最適化のパフォーマンスとはまったく異なります。

興味深いことに、囲碁やチェスなどの完全に決定論的な問題は、完全に確率的で統計的な手法で最も効率的に解決されています。これは、囲碁やチェスを離散最適化問題と見なすことができるにもかかわらず、20年前の科学界の直感に反しています。

ディープラーニングによって解き明かされた数学的最適化に関する理解を見直してみましょう。まず、次元の呪いを完全に見直す必要があります。私はこの概念はほとんど間違っていると考えており、ディープラーニングはこの概念が最適化問題の難しさを考える方法ではないことを証明しています。数学的な問題のクラスを見ると、特定の問題が完全に解決するのは非常に困難であることを数学的に証明できます。たとえば、NP困難な問題について聞いたことがあるかもしれませんが、問題に次元を追加すると、解決が指数関数的に困難になります。各追加の次元は問題をより難しくし、累積的な障壁があります。限られた計算リソースで問題を完全に解決するためのアルゴリズムは存在しないことを証明できます。しかし、ディープラーニングは、この視点がほとんど間違っていることを示しました。

まず、問題の表現の複雑さと問題の固有の複雑さを区別する必要があります。これらの2つの用語を例で説明しましょう。最初に与えられた時系列予測の例を見てみましょう。売上履歴があり、3年間の日次集計が行われているとします。したがって、約1,000日の日次集計の時間ベクトルがあります。これが問題の表現です。

では、もしも私が秒ごとの時系列表現に移行した場合はどうでしょうか？これは同じ売上履歴ですが、日次集計ではなく、秒ごとの集計で売上データを表現することにします。つまり、1日あたり86,400秒ありますので、問題の表現のサイズと次元を86,000倍に膨らませることになります。

しかし、固有の次元について考え始めると、売上履歴があるからといって、日ごとの集計から秒ごとの集計に移行するからといって、問題の複雑さや次元の複雑さが1,000倍に増加するわけではありません。おそらく、秒ごとに集計された売上の場合、時系列は非常に疎になるため、ほとんどのバケットにはほとんどゼロが入ります。問題の興味深い次元を100,000倍に増やしているわけではありません。ディープラーニングは、多次元の表現を持つ問題が基本的に難しいわけではないことを明確にしています。

次元の関連性に関連する別の視点は、特定の問題がNP完全であることを証明できるとしても、例えば、巡回セールスマン問題（この講義の最初に紹介された車両ルーティング問題の簡略化バージョン）の場合、巡回セールスマンは技術的にはNP困難な問題として知られています。つまり、一般的な場合に最適な解を見つけるためには、地図にポイントを追加するごとに指数関数的にコストがかかります。しかし、現実的には、これらの問題は非常に簡単に解決できます。2-optヒューリスティックで示されているように、最小限の計算リソースで優れた解を得ることができます。数学的な証明がいくつかの問題が非常に難しいことを示しているとしても、それは欺瞞的なものかもしれません。それらは、近似解を受け入れることができれば、近似解が優れていることもありますし、時には近似解ではなく最適解を得ることもあります。ただし、最適であることを証明することはできません。これは問題の近似を行うことができるかどうかについて何も言っていませんし、次元の呪いによって苦しめられるとされるそれらの問題は、興味深い次元がそれほど高くないため、解決は非常に簡単です。ディープラーニングは、非常に困難と考えられていた多くの問題が実際にはそれほど難しくないことを成功裏に示しました。

第2の重要な洞察は、局所最小値です。数理最適化やオペレーションリサーチに取り組んでいる研究者の大部分は、局所最小値が存在しない凸関数に取り組んできました。長い間、凸関数ではないものに取り組んでいる人々は、局所最小値に陥るのを避ける方法について考えていました。ほとんどの努力は、メタヒューリスティックなどの方法に注がれました。ディープラーニングは、局所最小値については気にしないという新たな理解を提供しました。この理解は、ディープラーニングコミュニティから生まれた最近の研究に由来しています。

問題の次元が非常に高い場合、局所最小値は次元が増加するにつれて消えていくことが示されています。局所最小値は低次元の問題では非常に頻繁に発生しますが、問題の次元を数百または数千に増やすと、統計的に言って、局所最小値は非常に起こりにくくなります。非常に大きな次元（数百万など）を見ると、局所最小値は完全に消えます。

次元の呪いと関連付けられていたように、より高い次元が敵ではなく、問題の次元を膨らませて局所最小値がまったく存在しないほど大きくすることはできないでしょうか？実際、これがディープラーニングコミュニティや兆個のパラメータを持つモデルで行われていることです。このアプローチにより、非常にクリーンな降下が可能になります。

本質的に、ディープラーニングコミュニティは、降下の品質や最終的な収束についての証明は無関係であることを示しました。重要なのは降下の速さです。非常に良い解に向かって迅速に反復し、降下することが望ましいです。降下速度が速ければ、最適化の観点でより進むことができます。これらの洞察は、数理最適化の一般的な理解、または20年前の主流の理解とは異なります。

ディープラーニングから得られる他の教訓もあります。ディープラーニングは非常に豊かな分野です。その1つはハードウェアへの共感です。コニックプログラミングや幾何学的プログラミングなどの数学的なソルバーの問題は、まず数学的な直感に焦点を当てており、計算ハードウェアには注意を払っていません。計算ハードウェアと基本的に対立するソルバーを設計してしまうと、数学がどれほど優れていても、計算ハードウェアの効率の悪さにより非常に非効率になる可能性があります。

ディープラーニングコミュニティの重要な洞察の1つは、計算ハードウェアと協調して設計し、それを受け入れるソルバーを作成することです。これが、私が現代のサプライチェーンのための補助科学の講義シリーズを開始した理由です。持っているハードウェアとそれを最大限に活用する方法を理解することは重要です。このハードウェアへの共感により、兆個のパラメータを持つモデルを実現することができます。ただし、大規模なコンピュータクラスターまたはスーパーコンピューターが必要です。

ディープラーニングからのもう1つの教訓は、代替関数の使用です。従来の数学的なソルバーは、それ自体の問題を最適化することを目指しており、それから逸脱しませんでした。しかし、ディープラーニングは、代わりに代替関数を使用する方が良い場合があることを示しました。たとえば、予測の場合、ディープラーニングモデルでは平均二乗誤差の代わりにクロスエントロピーをエラーメトリックとして非常に頻繁に使用します。現実の世界では、ほとんどの人はクロスエントロピーをメトリックとして興味を持っていませんが、それはかなり奇妙です。

ではなぜクロスエントロピーを使用しているのでしょうか？それは非常に急な勾配を提供するためであり、ディープラーニングが示したように、降下の速さが重要です。非常に急な勾配があれば、非常に迅速に降下することができます。人々は異論を唱えて、「平均二乗を最適化したいのであれば、なぜクロスエントロピーを使用する必要があるのですか？それはまったく同じターゲットではありません。」と言うかもしれません。しかし、実際には、クロスエントロピーを最適化すると、平均二乗基準に基づいて非常に頻繁に、ほとんど常に、より良い解が得られます。この説明のために単純化しています。代替関数のアイデアは、真の問題は絶対的なものではなく、最終的な解の妥当性を評価するための制御に使用するものです。ソルバーが進行中の間は必ずしも使用する必要はありません。これは、過去数十年間に人気のあった数学的なソルバーとはまったく異なるアイデアです。

最後に、パラダイムでの作業の重要性があります。数学的最適化では、エンジニアリングの労働力を組織化するために暗黙のうちに分業が関与しています。数学的ソルバーに関連付けられた暗黙の分業は、数学的ソルバーのエンジニアリングを担当する数学エンジニアと、数学的ソルバーによって処理可能な形式で問題を表現する責任を持つ問題エンジニアの2つの側面です。この分業は一般的であり、問題エンジニアが問題を最小限かつ純粋な形式で表現するだけで、ソルバーが仕事をすることができるようにすることが目的でした。

ディープラーニングは、この視点が非常に非効率であることを示しました。この任意の分業は、問題に取り組む数学エンジニアにとっては、状況が非常に困難になる結果となります。問題エンジニアが問題を数学的最適化のためにより適した方法で再構築するために、少し余分な努力をすることがはるかに良い方法です。

ディープラーニングは、ソルバーの上に問題をフレームするための一連のレシピです。これにより、最適化プログラムを最大限に活用することができます。ディープラーニングコミュニティのほとんどの進展は、これらのレシピの作成に焦点を当てており、彼らが持っているソルバー（例：TensorFlow、PyTorch、MXNet）のパラダイム内でうまく学習することができるものです。結論として、問題エンジニア、またはサプライチェーンサイエンティストと協力することが本当に重要です。

スライド14

さて、この講義の2つ目で最後のセクションに移りましょう。文献の中で最も価値のある要素について見ていきます。2つの大きなクラスのソルバー、ローカルサーチと微分可能プログラミングについて見ていきます。

スライド15

まず、再び「プログラミング」という用語について説明します。この言葉は非常に重要です。サプライチェーンの観点からは、私たちは直面している問題、または私たちが直面していると思っている問題を表現できるようにしたいのです。私たちは、問題を円錐体などの半ばばかげた数学的仮説に合わせるだけの超低解像度バージョンの問題ではなく、真のプログラミングパラダイムにアクセスしたいのです。

これまでの数十年間、線形計画法、二次錐計画法、幾何計画法などの数学的ソルバーはすべてプログラミングキーワードとともに提供されてきました。しかし、プログラミングパラダイムに対する期待は劇的に進化しています。現在では、ほぼ任意のプログラム、ループ、分岐、および可能なメモリ割り当てなどが含まれるプログラムを扱えるものが求められています。私たちは、数学的な特性を持つ興味深いおもちゃのような制限付きバージョンではなく、できるだけ任意のプログラムに近いものが欲しいのです。サプライチェーンでは、正確に間違っているよりもおおよその正確さが求められます。

スライド16

一般的な最適化に対処するために、まずローカルサーチから始めましょう。ローカルサーチは、見かけによらず非常にシンプルな数学的最適化手法です。疑似コードでは、ランダムな解から始め、それをビットのパックとして表現します。その後、解をランダムに初期化し、解の近傍を探索するためにビットをランダムに反転させます。このランダムな探索によって、より良い解が見つかれば、それが新しい基準解となります。

この驚くほど強力なアプローチは、文字通り任意のプログラムとして機能し、任意の既知の解から再開することもできます。このアプローチをより良くする方法はたくさんあります。1つの方法は、微分計算ですが、微分可能計算とは異なります。微分計算は、プログラムを特定の解で実行し、1ビットを反転させることで、同じプログラムを微分実行することができるという考えです。もちろん、結果は異なる場合もありますし、問題の構造に非常に依存します。プログラム自体を高速化することでプロセスを加速する方法もあります。ただし、黒箱プログラムに関する追加情報を活用するのではなく、プログラム自体を高速化することが重要です。なぜなら、毎回プログラム全体を再実行する必要がないからです。

ローカルサーチを改善するための他のアプローチもあります。行う動作の種類を改善することができます。最も基本的な戦略は、kフリップと呼ばれるもので、非常に小さな数（数個から数十個）のビットを反転させます。ビットを反転させるだけでなく、問題エンジニアが解に適用する変異の種類を指定することもできます。たとえば、問題に順列を適用したいと表現することができます。このようなスマートな動作は、問題の制約の満足を保つことが多く、ローカルサーチプロセスの収束を早めるのに役立ちます。

ローカルサーチを改善する別の方法は、完全にランダムに空間を探索するのではなく、適切な方向を学習し、反転の最も有望な領域を特定することです。最近の論文では、ローカルサーチの上に小さなディープラーニングモジュールを組み込むことで、ジェネレーターとして機能することが示されています。ただし、このアプローチはエンジニアリングの観点でトリッキーな場合があります。機械学習プロセスによって導入されるオーバーヘッドが、計算リソースの面でプラスの効果をもたらすことを確認する必要があるからです。

他にもよく知られたヒューリスティックがあります。現代のローカルサーチエンジンを実装するために必要な要点を総合的に理解するには、「LocalSolver: A Black-Box Local-Search Solver for 0-1 Programs」という論文を読むことができます。LocalSolverを運営する会社は同じ名前の製品も持っています。この論文では、彼らの製品グレードのソルバーの内部で何が起こっているかについてのエンジニアリングの見通しを提供しています。彼らはより良い結果を得るためにマルチスタートとシミュレーテッドアニーリングを使用しています。

ローカルサーチについて付け加える注意点は、確率的な問題とはあまりうまく対処できないことです。確率的な問題では、単に「より良い解がある」と言ってすぐに最良の解になるとは限りません。それはそれよりもトリッキーであり、新しい最良の解として評価される解にジャンプする前に、いくらかの追加の努力を必要とします。

さて、今日議論する2番目のソルバーに移りましょう。それは微分可能プログラミングです。しかし、まず、微分可能プログラミングを理解するために、確率的勾配降下法を理解する必要があります。確率的勾配降下法は、反復的な勾配ベースの最適化技術です。これは、1950年代初頭に先駆的な技術として開発された一連の技術として登場し、ほぼ70年前のものです。それはほぼ60年間は比較的ニッチな存在であり、ディープラーニングの進歩を待たなければ、確率的勾配降下法の真の潜在能力とパワーを実現することはありませんでした。

確率的勾配降下法は、損失関数を一連の部分関数に加法的に分解できると仮定しています。式中のQ(W)は損失関数を表し、一連の部分関数Qiに分解されます。これは、ほとんどの学習問題が一連の例に基づいて予測を学習する必要があると見なすことができるため、関連性があります。アイデアは、損失関数をデータセット全体に対して評価する必要があるということで、各データポイントに対するローカルエラーを持つデータセット全体の平均エラーとして損失関数を分解できるということです。多くのサプライチェーンの問題もこのように加法的に分解できます。たとえば、サプライチェーンネットワークを各SKUごとのパフォーマンスの一連のものに分解し、各SKUに関連付けられた損失関数を持つことができます。最適化したい真の損失関数は合計です。

このような分解がある場合、つまり学習問題に非常に自然な場合、確率的勾配降下法（SGD）プロセスで反復することができます。パラメータベクトルWは非常に大きなシリーズになる可能性があります。最大のディープラーニングモデルは兆個のパラメータを持っています。アイデアは、プロセスの各ステップでパラメータを更新し、少量の勾配を適用することです。Etaは学習率であり、通常0から1の間の小さな数値であり、0.01程度が一般的です。Qのナブラは部分損失関数Qiの勾配です。驚くべきことに、このプロセスはうまく機能します。

SGDは確率的であると言われています。なぜなら、次のi要素をランダムに選び、データセットをジャンプしてパラメータにわずかな勾配を適用するからです。これが確率的勾配降下法の本質です。

それはほぼ60年間は比較的ニッチな存在であり、大きなコミュニティにはほとんど無視されていました。なぜなら、確率的勾配降下法が全く機能すること自体が非常に驚くべきことだからです。それは、損失関数のノイズと損失関数へのアクセスの計算コストとの間で優れたトレードオフを提供するために機能します。確率的勾配降下法では、データセット全体に対して評価する必要のある損失関数を持つ代わりに、1つのデータポイントを取り、わずかな勾配を適用することができます。この測定値は非常に断片的でノイズが多いですが、このノイズは実際には問題ありません。なぜなら、非常に高速だからです。データセット全体を処理するのと比べて、桁違いに多くの小さなノイズ最適化を行うことができます。

驚くべきことに、導入されたノイズは勾配降下法を助けます。高次元空間の問題の1つは、局所最小値が比較的存在しなくなることです。しかし、勾配降下法では、勾配が非常に小さい場所の大きな領域に直面することがあり、降下のための方向を選ぶことができません。ノイズによって、より急な、よりノイズの多い勾配が得られ、降下に役立ちます。

勾配降下法の興味深い点は、それが確率的なプロセスである一方で、確率的な問題を無料で処理できることです。もしQiがノイズを含んだ確率的な関数であり、評価するたびに異なる結果を与えるランダムな結果を出す場合、アルゴリズムの1行も変更する必要はありません。確率的勾配降下法は、供給チェーンの目的に完全に合致するものを提供するため、非常に興味深いものです。

2番目の質問は、勾配はどこから来るのかということです。プログラムがあり、部分的な損失関数の勾配を取るだけですが、この勾配はどこから来るのでしょうか？任意のプログラムに対して勾配をどのように取得するのでしょうか？実は、以前に発見された非常に優れたミニマリスティックな技術があります。それが自動微分と呼ばれるものです。

自動微分は1960年代に登場し、時間の経過とともに洗練されました。2つのタイプがあります。1964年に発見された前方モードと、1980年に発見された逆方向モードです。自動微分は、コンパイルのトリックと見なすことができます。アイデアは、コンパイルするプログラムがあり、自動微分では、損失関数を表すプログラムを持っています。このプログラムを再コンパイルして、損失関数の計算に関与するすべてのパラメータの勾配ではなく、2番目のプログラムの出力を得ることができます。

さらに、自動微分は、初期のプログラムと基本的に同じ計算複雑性を持つ2番目のプログラムを提供します。つまり、勾配を計算するための2番目のプログラムを作成する方法だけでなく、2番目のプログラムは最初のプログラムと同じパフォーマンスの計算特性を持っています。計算コストに関しては、定数倍の膨張です。ただし、実際のところ、得られた2番目のプログラムは、初期のプログラムとまったく同じメモリ特性を持っているわけではありません。細かい点はこの講義の範囲を超えていますが、質問の際にそれについて議論することができます。基本的に、2番目のプログラムである逆方向は、初期のプログラムよりも多くのメモリを必要とし、いくつかの病的な状況では、初期のプログラムよりもはるかに多くのメモリを必要とすることがあります。メモリが増えると、一様なメモリアクセスを想定できないため、計算パフォーマンスに問題が生じます。

自動微分の概要を少し示すために、前方モードと逆方向モードの2つのモードがあります。学習の観点やサプライチェーンの最適化の観点からは、私たちにとって興味のあるモードは逆方向モードだけです。画面に表示されているのは、完全に作り上げられた損失関数Fです。前方トレースと呼ばれる、2つの与えられた入力値X1とX2に対して関数を計算するために行われる一連の算術または基本的な操作が表示されます。これにより、最終値を計算するために行われるすべての基本的なステップが得られます。

アイデアは、すべての基本的なステップに対して、ほとんどが乗算や加算などの基本的な算術演算である逆方向モードが、同じステップを逆の順序で実行するプログラムであるということです。前方の値ではなく、アジョイントを持つことになります。すべての算術演算に対して、その逆の対応物があります。前方の操作から対応物への移行は非常に簡単です。

複雑に見えるかもしれませんが、前方の実行と逆方向の実行があり、逆方向の実行は単なる要素ごとの変換であることに注意してください。逆方向の最後には、勾配が得られます。自動微分は複雑に見えるかもしれませんが、そうではありません。私たちが実装した最初のプロトタイプは100行未満のコードでしたので、非常に簡単で本質的には安価なトランスパイルトリックです。

これは興味深いことです。私たちは確率的勾配降下法を持っていますが、これは非常に強力な最適化メカニズムです。非常にスケーラブルで、オンラインで、ホワイトボードであり、確率的な問題とネイティブに動作します。唯一の問題は、勾配をどのように取得するかですが、自動微分を使用することで、ほぼ任意のプログラムに対して固定のオーバーヘッドまたは定数倍で勾配を得ることができます。最終的に得られるものは、微分可能なプログラミングです。

スライド19

興味深いことに、微分可能なプログラミングは確率的勾配降下法と自動微分の組み合わせです。これらの2つの技術、確率的勾配降下法と自動微分は数十年前から存在していましたが、微分可能なプログラミングは、FacebookのAI責任者であるYann LeCunが2018年初頭にこの概念について話し始めたときに注目を浴びるようになりました。LeCunはこの概念を発明したわけではありませんが、それを広める上で重要な役割を果たしました。

たとえば、ディープラーニングコミュニティは最初は自動微分ではなくバックプロパゲーションを使用していました。ニューラルネットワークに詳しい方にとっては、バックプロパゲーションは自動微分よりもはるかに複雑なプロセスであり、実装するのもはるかに困難です。自動微分はすべての面で優れています。この洞察により、ディープラーニングコミュニティはディープラーニングにおける学習の構成要素を洗練させました。ディープラーニングは数学的最適化とさまざまな学習技術を組み合わせ、非学習部分を分離したクリーンなコンセプトとしての微分可能なプログラミングが生まれました。

トランスフォーマーモデルなどの現代のディープラーニング技術は、その下に微分可能なプログラミング環境を想定しています。これにより、研究者は上に構築された学習の側面に焦点を当てることができます。微分可能なプログラミングは、ディープラーニングの基礎であるだけでなく、サプライチェーンの最適化やサプライチェーンの学習プロセス（統計的予測など）にも非常に関連しています。

ディープラーニングと同様に、問題は2つの部分に分かれています。基礎となる微分可能なプログラミングと、その上に構築された最適化または学習技術です。ディープラーニングコミュニティは、トランスフォーマーなどの微分可能なプログラミングとうまく機能するアーキテクチャを特定することを目指しています。同様に、最適化の目的に適したアーキテクチャを特定する必要があります。これは、高度な組み合わせ設定での囲碁やチェスのプレイ方法を学ぶために行われてきたことです。後の講義では、サプライチェーン固有の最適化に適した技術について説明します。

スライド20

しかし、ここで結論を述べる時が来ました。サプライチェーンの文献のかなりの部分、そしてそのソフトウェア実装のほとんどは、数学的最適化に関して非常に混乱しています。この側面は通常、適切に識別されていないことがあり、その結果、実践者、研究者、さらにはエンタープライズソフトウェア企業のソフトウェアエンジニアさえも、数学的最適化に関してかなり無秩序に数値レシピを組み合わせる傾向があります。彼らは大きな問題を抱えています。数学的最適化の性質を持つコンポーネントが特定されていないため、そして人々が文献で利用可能なものについてさえも認識していないため、彼らはしばしば荒っぽいグリッドサーチや急なヒューリスティックを使って不規則で一貫性のないパフォーマンスを得てしまいます。この講義の結論として、これからは、サプライチェーンの数値計算手法やサプライチェーンソフトウェアについて、どのような数学的最適化が行われているのか、何が行われているのかを自問する必要があります。もしプロバイダがこの視点について明確な見解を提供していないことに気づいた場合、おそらくあなたは図の左側にいることになります。そして、それはあなたがいたくない場所です。

さて、質問を見てみましょう。

スライド21

質問: オペレーションにおいて、計算手法への移行は必須のスキルであり、オペレーションの役割は廃れるか、あるいはその逆ですか？

まず、いくつかのことを明確にさせてください。このような懸念をCIOに押し付けるのは間違いだと思います。人々はCIOに対してあまりにも多くの期待を抱いています。チーフインフォメーションオフィサーとして、コンピュータリソース、低レベルのトランザクションシステム、ネットワークの整合性、サイバーセキュリティなど、ソフトウェアインフラストラクチャの基盤層に対処する必要があります。CIOには、サプライチェーンに対して実際に価値のあることをするために必要な理解を持っていることを期待すべきではありません。

問題は、多くの企業で、コンピュータに関連する何も知らない人々が絶望的にいるため、CIOがすべての問題の担当者になってしまうことです。現実の問題は、CIOがインフラストラクチャの基盤層に対処し、それから各専門家が彼らの特定のニーズに対して利用可能な計算リソースとソフトウェアツールで対応することです。

オペレーションの役割が廃れるという点については、あなたの役割が一日中Excelのスプレッドシートを手作業で処理することであれば、非常に可能性が高いです。これは、1979年にラッセル・アッコフが彼の論文を発表して以来、既知の問題です。問題は、意思決定に関わるこの方法が将来ではないことは人々が知っていたが、長い間ステータスクオのままであったことです。問題の核心は、企業が実験プロセスを理解する必要があるということです。私は企業がこれらのスキルを再獲得し始める過渡期があると信じています。第二次世界大戦後、多くの大きな北米企業は、役員の中にオペレーションリサーチに関する知識を持っていました。それは注目される新しいトピックであり、大企業の取締役会はオペレーションリサーチについての知識を持っていました。ラッセル・アッコフが指摘するように、結果が出なかったため、これらのアイデアは会社の階層の下に押し込まれ、最終的には完全に外部委託されました。それらはほとんど関係なく、具体的な結果をもたらしませんでした。私は、オペレーションリサーチが結果を出さなかった古典的な時代からの教訓を学ぶことが人々によってのみ戻ってくると信じています。CIOはこの取り組みにほんのわずかな貢献しかできません。それは主に会社内部の人々の付加価値を再考する問題です。

あなたは資本主義的な貢献をしたいと思うでしょうし、それは私の以前の講義の1つに関連しています。サプライチェーン向けのソフトウェア製品の意味での製品指向のデリバリーについてです。問題は、あなたが会社にどのような資本主義的な付加価値を提供するかということです。もし答えがないのであれば、あなたはおそらく会社がなるべきであり、将来なるであろうものの一部ではないかもしれません。

質問: Excelソルバーを使用してMRMSC値を最小化し、アルファ、ベータ、ガンマの最適値を見つけることはできますか？

この質問は、Holt-Wintersの場合に関連していると思います。ここでは、グリッドサーチで解を見つけることができます。ただし、Excelソルバーでは何が起こっているのでしょうか？それは勾配降下法なのでしょうか、それとも別の方法なのでしょうか？もしExcelの線形ソルバーを指しているのであれば、それは線形の問題ではないため、Excelではその場合には何もできません。Excelに他のソルバーやアドインがある場合は、それらが動作することができますが、これは非常に時代遅れの視点です。それはより確率的な視点を受け入れておらず、得られる予測は非確率的な予測であり、時代遅れのアプローチです。

Excelは使用できないと言っているわけではありませんが、問題はExcelでどのようなプログラミングの能力が開放されているかということです。Excelで確率的勾配降下法を行うことはできますか？おそらく、専用のアドインを追加すればできるでしょう。Excelは任意のプログラムを上にプラグインすることができます。Excelで微分可能なプログラミングを行うことは可能でしょうか？はい。Excelでそれを行うことは良いアイデアでしょうか？いいえ。なぜなら、Excelで何がうまくいかないかを理解するために、製品指向のソフトウェアデリバリーコンセプトに戻る必要があるからです。それはプログラミングモデルと、チームの努力で時間をかけて作業を維持できるかどうかに関わります。

質問: 最適化問題は通常、車両ルーティングや予測に偏っています。なぜ供給チェーン全体の最適化を考慮しないのですか？それは孤立した領域を見るよりもコストを削減することになりませんか？

完全に同意します。供給チェーン最適化の難題は、サブ問題に対してローカル最適化を行うと、問題を解決するのではなく、問題を移動させる可能性が高いということです。私も完全に同意していますし、より複雑な問題を考え始めると、ハイブリッド問題に取り組むことになります。例えば、車両ルーティング問題と補充戦略の組み合わせです。問題は、制約に縛られたくないので、非常に汎用的なソルバーが必要です。非常に汎用的なソルバーを持っている場合、2-optのようなスマートなヒューリスティックではなく、車両ルーティングにはうまく機能するが、補充と車両ルーティングの両方のハイブリッドには適していないものを使用する必要があります。

この包括的な視点に移行するためには、次元の呪いを恐れてはいけません。20年前、人々はこれらの問題は既に非常に困難でNP完全であると言っていました。旅行セールスマン問題のような問題を、別の問題と絡め合わせてさらに困難な問題を解決したいと思うのです。その答えは「はい」です。任意のプログラムに対応できるソルバーを持つことが重要なのです。なぜなら、解決策は多くの絡み合った問題の統合かもしれないからです。

実際には、孤立した問題を解決するという考え方は、すべてを解決するという考え方に比べてはるかに弱いです。正確に間違っているよりもおおよその正解の方が良いです。非常に強力なローカル最適化よりも、供給チェーン全体をシステムとして取り組む非常に弱いソルバーを持つ方が良いです。ローカルにマイクロ最適化するだけで他の場所で問題を引き起こすだけです。システムの真の最適化は、すべての部分にとって必ずしも最適な最適化ではないため、会社全体とその供給チェーンの他の側面を考慮に入れると、ローカルに最適化されるわけではありません。

質問: 最適化の演習を行った後、新しい制約がいつでも現れる可能性を考慮すると、いつシナリオを再評価すべきですか？ 答えは、最適化を頻繁に再評価する必要があるということです。これは、このシリーズの第2回の講義で紹介した供給チェーン科学者の役割です。供給チェーン科学者は必要に応じて最適化を繰り返し行います。巨大な船がスエズ運河を塞いだような新たな制約が現れた場合、それは予期しないものですが、供給チェーンで対処する必要があります。そうしないと、設置したシステムは虚偽の条件下で動作するため、無意味な結果を生成します。緊急事態に対処する必要がなくても、会社に最も大きなリターンを生み出す可能性のあるアングルについて考えるために時間を投資したいと思うはずです。これは基本的に研究開発です。システムが稼働しており、システムを改善できる領域を特定しようとしているだけです。これは非常に資本主義的で不規則な応用研究プロセスになります。供給チェーン科学者としては、数値計算法をテストするだけで、既に持っているものよりも良い結果を提供しない日があります。ある日はわずかな調整を行い、会社に数百万ドルを節約することができる幸運な日もあります。不規則なプロセスですが、平均的には大きな成果が得られるでしょう。

質問: 線形計画法、整数計画法、混合計画法以外の最適化問題のユースケースは何ですか？

私は質問を逆にします。どの供給チェーン問題において線形計画法が関連していると思われますか？線形な供給チェーン問題はほとんどありません。私の異議は、これらのフレームワークが非常に単純化されており、おもちゃの問題にも対応できないということです。先ほど言ったように、線形計画法のような数学的フレームワークは、古い低次元パラメトリック予測モデルのハードウィンター最適化のようなおもちゃの問題にも対応できません。旅行セールスマン問題やほとんどの他の問題にも対応できません。

整数計画法や混合整数計画法は、変数の一部が整数であることを追加するための一般的な用語ですが、これらのプログラミングフレームワークは、供給チェーン問題に対処するために必要な表現力には程遠いものです。

最適化問題のユースケースについて尋ねられた場合、供給チェーンのペルソナに関する私のすべての講義をご覧いただくことをお勧めします。私たちはすでに供給チェーンのペルソナのシリーズを持っており、数多くの問題が数学的最適化を通じてアプローチできることを示しています。供給チェーンのペルソナに関する講義では、パリ、マイアミ、アムステルダム、ワールドシリーズなど、さまざまな問題がリストアップされています。私たちはアプローチが必要な多くの問題を抱えており、適切な数学的最適化の視点でアプローチする価値があります。ただし、これらの問題のほとんどは、これらの数学的フレームワークから生じる非常に厳密で奇妙な制約の中に収めることはできません。再度言いますが、これらの数学的フレームワークは主に凸性に関するものであり、これは供給チェーンには適切な視点ではありません。私たちが扱うポイントのほとんどは非凸です。しかし、大丈夫です。非凸であるからといって、それが非常に難しいというわけではありません。利益については、最終的に数学的な証明を持っているかどうかではなく、あなたが生産、補充、価格、アソートメントなどに関して正しい意思決定ができるかどうかが重要です。数学的な証明がそれらの意思決定に添付されているかどうかは関係ありません。

質問: 学習アルゴリズムのデータはどのくらいの期間保存すべきですか？

現在のデータストレージは非常に安価なので、なぜ永久に保存しないのでしょうか？データストレージは非常に安価です。たとえば、スーパーマーケットに行けば、1テラバイトのハードドライブの価格が約60ドル程度であることがわかります。非常に安価です。

ただし、個人データがデータに含まれている場合、保持するデータは責任の所在となります。ただし、供給チェーンの観点からは、まず個人データを削除する必要があると仮定します。通常、最初から個人データを保持する必要はありません。クレジットカード番号や顧客の名前を保持する必要はありません。顧客識別子などを保持するだけで十分です。データから個人データを完全に削除した場合、どのくらいの期間保存すべきですか？永久に保持してください。

供給チェーンでは、データが限られているという点が重要です。画像認識などの深層学習の問題とは異なり、ウェブ上のすべての画像を処理し、ほぼ無限のデータベースにアクセスできるわけではありません。供給チェーンでは常にデータが限られています。将来の需要を予測するために、過去10年以上を見ることが真に関連していると統計的に言える産業はほとんどありません。ただし、必要に応じてデータを切り捨てる方が、データを破棄してしまい、それが不足していることに気付くよりも簡単です。私の提案は、すべてのデータを保持し、個人データを削除し、データパイプラインの最後に非常に古いデータをフィルタリングするかどうかを確認することです。それは産業によって異なるかもしれません。たとえば、航空宇宙産業では、4年間の運用寿命を持つ部品や航空機があり、過去40年間のデータがシステムに関連しています。

質問: 多目的プログラミングは、複数の目的（例：複数の関数を最小化する合計）の関数ですか？

多目的プログラミングのアプローチ方法は複数あります。それは単なる合計関数を持つことではありません。なぜなら、合計関数がある場合、それは単に損失関数の分解と構造の問題になるからです。実際には、ベクトルを持つことが重要です。実際には、多目的プログラミングにはさまざまなバリエーションがあります。最も興味深いバリエーションは、レキシコグラフィックな順序を選択するものです。サプライチェーンに関しては、多くの関数の平均値や最大値を取る最小化が興味深いかもしれませんが、私はあまり確信がありません。制約条件を実際に注入し、制約条件を通常の最適化の一部として扱う多目的アプローチは、サプライチェーンの目的に非常に興味深いです。他のバリエーションも興味深いかもしれませんが、私はあまり確信がありません。それらが興味深くないと言っているわけではありません。ただ、私自身は確信が持てないと言っているだけです。

質問: 最適化された解に対して近似解を使用するタイミングはどのように決定しますか？

つまり、質問の意味があまり理解できません。ディープラーニングから学ぶべき教訓は、最適な解は存在しないということです。すべてはある程度の近似です。数値を持っていると言っても、コンピュータでは数値は無限の精度ではなく、有限の精度で表現されます。そして、この有限の精度は、特定の状況では問題を引き起こすことがあります。ですから、答えは常に近似です。完璧な解が存在すると考えることは幻想です。持っているすべての解は近似値であり、その中にはより近似したものとそうでないものがあります。ですから、質問の意味についてはあまり確信がありませんが、数学的最適化の観点から言えば、品質を評価するための損失関数があり、競合する2つの解がある場合、どちらが最良かを評価するために損失関数を使用します。それが操作方法です。

質問: なぜ時系列データは、履歴データとして86,400で割られるのですか？

そうではありません。それは例でした。私は単に、時系列予測アルゴリズムであるクラシカルな時系列を採用する場合に、どのように状況を極端な状態に押し出すかを示したかったのです。時系列を表現する方法はたくさんありますが、時系列の最も一般的な表現方法は、等間隔の時系列です。これは通常、日次集計や週次集計で得られるものです。同じ長さのバケットで集計されるバケットを持っているということです。シリーズはベクトルのような構造を持っています。

しかし、私が指摘しているのは、それは大いに任意性があるということです。データを日次データとして表現することを選択することができますが、秒単位でデータを表現することも選択することができます。秒単位でデータを表現することは意味があるでしょうか？答えはイエスです。問題の種類によります。たとえば、電力会社であり、グリッドを管理したい場合、電力供給と消費のバランスを正確に保つために、秒単位で電力を管理する必要があります。このバランスは実際には秒単位で調整されます。したがって、データを秒単位で表現することが意味を持つ状況があります。地元の店舗での販売には意味がないかもしれません。ところで、86,400という数字を使ったのは、単に24時間×60分×60秒であり、常にデータの表現があること、そしてその表現が特定の次元性を持つデータの本質的な次元性とは異なる次元を持つ場合があることを明確にしたかったのです。表現は、大部分が完全に作り上げられたものであり、任意性があります。これにより、データの数値的な指標が得られます。たとえば、3年分のデータがあるので、次元が1000のベクトルが得られます。しかし、この1000は、データを日次集計するという決定に基づいて大部分が作り上げられたものです。他の代替期間を選択した場合、異なる次元が得られます。それが私が伝えたかったポイントであり、それがディープラーニングが本当に正しかったことです：データの表現方法の任意の選択に惑わされないようにするために、他の要素を持つことです。表現に依存しないようにしたいのです。

質問: 確率的予測を導入することで、コスト関数と制約条件が確率的な性質を持つようになります。これが解決策の見つけ方にどのような影響を与えるでしょうか？

まあ、非常に基本的で根本的な制約があります。もし問題を処理できないソルバーを持っている場合、そして再度言いますが、非確率的な問題を非常に多数のサンプルにわたって平均化することで確定的な問題に戻ることが常にできるということを覚えておいてください、それならば、計算コストの点で困難になります。つまり、代替解に比べて満足のいく解にたどり着くために、10,000倍以上の処理能力を費やさなければならないということです。その結果、数学的最適化ツール、およびインフラストラクチャが確率的な問題に対応できるようにする必要があります。それが微分可能プログラミングで得られるものであり、ローカルサーチではあまり得られませんが、ローカルサーチを改良してそのような状況でもスムーズに動作するようにすることもできます。

基本的に、確率的予測を行うと、将来を見る方法だけでなく、それらの予測を扱うためのツールや計器の種類にも大きな変革がもたらされます。それはまさにLokadが過去10年間に開発してきたツールです。その理由は、供給チェーンで必然的に生じる確率的な問題にうまく対応できるツールが必要だからです。ほとんどすべての供給チェーンの問題には不確実性の要素が含まれており、したがってある程度の確率的な問題を扱っています。

素晴らしいです。次の講義は同じ曜日、水曜日に行われます。その間には休暇があります。次の講義は9月22日に行われ、皆さんにお会いできることを楽しみにしています。今回はサプライチェーンのための機械学習について話し合います。それでは、またお会いしましょう。

参考文献

The Future of Operational Research Is Past, Russell L. Ackoff, February 1979
LocalSolver 1.x: A black-box local-search solver for 0-1 programming, Thierry Benoist, Bertrand Estellon, Frédéric Gardi, Romain Megel, Karim Nouioua , September 2011
Automatic differentiation in machine learning: a survey, Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, Jeffrey Mark Siskind, last revised February 2018

Lokad TVに戻る ›

PREVIOUS EPISODES