00:19 イントロダクション
04:33 ‘アルゴリズム’ の2つの定義
08:09 ビッグオー記法
13:10 これまでの話
15:11 補助科学（まとめ）
17:26 モダンなアルゴリズム
19:36 ‘最適性’ の上回り
22:23 データ構造 - 1/4 - リスト
25:50 データ構造 - 2/4 - 木
27:39 データ構造 - 3/4 - グラフ
29:55 データ構造 - 4/4 - ハッシュテーブル
31:30 魔法のレシピ - 1/2
37:06 魔法のレシピ - 2/2
39:17 テンソルの理解 - 1/3 - ‘アインシュタイン’ 表記
42:53 テンソルの理解 - 2/3 - Facebook チームのブレイクスルー
46:52 テンソルの理解 - 3/3 - サプライチェーンの視点
52:20 メタ技術 - 1/3 - 圧縮
56:11 メタ技術 - 2/3 - メモ化
58:44 メタ技術 - 3/3 - 不変性
01:03:46 結論
01:06:41 今後の講義と視聴者の質問
説明
サプライチェーンの最適化は、数多くの数値問題を解決することに依存しています。アルゴリズムは、特定の計算問題を解決するために意図された高度にコード化された数値レシピです。優れたアルゴリズムは、より少ない計算リソースで優れた結果を得ることができます。サプライチェーンの特異性に焦点を当てることで、アルゴリズムのパフォーマンスを大幅に向上させることができます。過去数十年間に大きく進化したモダンなコンピュータの設計も、“サプライチェーン” アルゴリズムに取り入れる必要があります。
フルトランスクリプト
このサプライチェーン講義シリーズへようこそ。私はジョアネス・ヴェルモレルです。今日は「サプライチェーンのためのモダンなアルゴリズム」を紹介します。優れた計算能力は、優れたサプライチェーンのパフォーマンスを実現するために重要です。より正確な予測、より細かい最適化、より頻繁な最適化を実現することは、優れたサプライチェーンのパフォーマンスを達成するために望ましいことです。常に、手に入れることができる計算リソースのすぐ外側に優れた数値計算法が存在します。
アルゴリズムは、単純に言えばコンピュータを高速化するものです。アルゴリズムは数学の一分野であり、これは非常に活発な研究分野です。この研究分野の進歩は、コンピューティングハードウェアの進歩をしばしば上回ります。この講義の目標は、モダンなアルゴリズムの内容を理解し、特にサプライチェーンの視点から、サプライチェーンにおいてモダンなアルゴリズムを最大限に活用する方法を理解することです。
アルゴリズムに関しては、絶対的な参考書が1冊あります。それは1990年に初版が出版された『アルゴリズムイントロダクション』です。この本は必読書です。そのプレゼンテーションと執筆の品質は単純に最高です。この本は初版20年間で50万部以上売れ、学術的な執筆者の世代全体に影響を与えました。実際、この本に見られるスタイルとプレゼンテーションに強く影響を受けたことが、過去10年間に出版されたサプライチェーン理論に関するほとんどの最新のサプライチェーン書籍に頻繁に見られます。
個人的には、私は1997年にこの本を読みましたが、実際には初版のフランス語訳でした。この本は私のキャリア全体に深い影響を与えました。この本を読んだ後、私はソフトウェアを以前とは異なる視点で見るようになりました。ただし、この本は、‘80年代末から'90年代初頭に広まっていたコンピューティングハードウェアに関する視点を採用しています。このシリーズの前の講義で見たように、過去数十年間でコンピューティングハードウェアは劇的に進化しており、この本で行われたいくつかの仮定は比較的時代遅れに感じられます。たとえば、この本では、メモリアクセスが一定の時間で行われると仮定していますが、現代のコンピュータではもはやそのような動作はありません。
それにもかかわらず、私は、非常に高い明瞭さと簡潔さを得るために、単純化することが合理的な提案であると考えています。この本はこの点で素晴らしい仕事をしています。この本に記載されているキーの仮定が時代遅れであることを念頭に置いておくことをお勧めしますが、それでもまだ絶対的な参考書であり、全ての読者にお勧めします。
「アルゴリズム」という用語をあまり馴染みのない視聴者に対して明確にするために、定義を明確にしましょう。古典的な定義では、アルゴリズムは有限の明確なコンピュータ命令の連続です。これは教科書やウィキペディアで見つけることができるような定義です。アルゴリズムの古典的な定義には一定の価値がありますが、アルゴリズムに関連する意図を明確にしないため、あまり魅力的ではないと考えています。興味があるのは、任意の種類の命令の連続ではなく、非常に特定のコンピュータ命令の連続です。したがって、私は「アルゴリズム」という用語の個人的な定義を提案します：アルゴリズムとは、パフォーマンス志向の細かい問題解決ソフトウェアメソッドです。
この定義を解説しましょう。まず、問題解決の部分です。アルゴリズムは、解決しようとする問題によって完全に特徴付けられます。このスクリーンに表示されているのは、人気のあるよく知られたアルゴリズムであるクイックソートの疑似コードです。クイックソートは、次のようなソート問題を解決しようとします：データエントリが含まれる配列があり、すべてのエントリが昇順でソートされた同じ配列を返すアルゴリズムが必要です。アルゴリズムは、特定の明確な問題に完全に焦点を当てています。
2つ目の側面は、より優れたアルゴリズムを判断する方法です。より優れたアルゴリズムとは、より少ない計算リソースで同じ問題を解決できるものであり、実際にはより速く解決できるものです。最後に、細かい部分があります。私たちが「アルゴリズム」という用語を使うとき、私たちは非常に基本的な問題を見て、それらを無限に組み合わせてより複雑な問題を解決することを目指しています。それがアルゴリズムの本質です。
アルゴリズムの理論の重要な成果の1つは、アルゴリズムの性能をかなり抽象的な方法で特徴付けることです。今日はこの特徴付けと数学的な枠組みの詳細については触れませんが、アルゴリズムを特徴付けるためには、漸近的な振る舞いを見る必要があります。問題は、問題を特徴付けるいくつかの主要なボトルネック次元に依存しているということです。例えば、先ほど紹介したソート問題では、通常、ソートする要素の数が特徴的な次元です。問題は、ソートする要素の配列が非常に大きくなった場合に何が起こるかです。この特徴的な次元を「n」という記号で表すことにします。
さて、アルゴリズムを扱う際に見たことがあるかもしれないビッグO表記という記法があります。ここでは、何が起こっているのかを直感的に説明します。まず、例えば、データセットがあり、平均値などの単純な統計的指標を抽出したいとします。もし私がビッグOが1のアルゴリズムを持っていると言った場合、それはデータセットが小さいか大きいかに関係なく、この問題（平均値の計算）の解を一定の時間で返すことができるということです。一定の時間、つまりビッグOが1であることは、マシン間通信のリアルタイム性を実現するための絶対的な要件です。もし一定の時間を持つものがない場合、リアルタイムのパフォーマンスを実現することは非常に困難であり、場合によっては不可能です。
通常、もう1つの重要なパフォーマンスの側面はビッグOがNです。ビッグOがNというのは、アルゴリズムの複雑さが興味のあるデータセットのサイズに対して厳密に線形であることを意味します。これは、データを1回だけまたは固定回数だけ読み込むだけで問題を解決できる効率的な実装がある場合に得られるものです。ビッグOがNの複雑さは、通常、バッチ実行との互換性があります。オンラインかつリアルタイムなものを持ちたい場合、データセット全体を処理することはできません。ただし、データセットのサイズが固定であることがわかっている場合は除きます。
線形性を超えると、ビッグOがNの2乗になります。ビッグOがNの2乗は非常に興味深いケースであり、生産の爆発的な増加のスイートスポットです。これは、複雑さがデータセットのサイズに対して二次的に成長することを意味します。つまり、データが10倍増えるとパフォーマンスは100倍悪くなります。これは、プロトタイプでは問題が見えない場合が多いです。なぜなら、小さなデータセットで遊んでいるからです。テストフェーズでも同様で、小さなデータセットで遊んでいるため問題が見えません。しかし、本番環境に移行すると、ソフトウェアが完全に遅くなります。特に、エンタープライズソフトウェアの世界、特にサプライチェーンエンタープライズソフトウェアの世界では、フィールドで観察される多くの致命的なパフォーマンスの問題は、実際には特定されていない二次的なアルゴリズムによって引き起こされています。その結果、二次的な振る舞いが非常に遅いという問題が発生します。この問題は、現代のコンピュータは非常に高速であり、Nがかなり小さい限り、Nの2乗はそれほど悪くありませんので、初期段階では特定されませんでした。しかし、大規模な本番環境のデータセットを扱う場合は、非常に問題があります。
この講義は、サプライチェーンの講義シリーズの第4章の2番目の講義です。第1章では、プロローグとして、サプライチェーンを研究対象と実践の両方としての私の見解を述べました。私たちが見てきたのは、サプライチェーンは飼いならされた問題とは異なり、悪質な問題の大きな集合体であるということです。悪質な問題は単純な方法論ではアプローチできません。なぜなら、あらゆる場所で敵対的な行動が起こるため、方法論自体に多くの注意を払う必要があるからです。ほとんどの単純な方法は、かなり壮大な方法で失敗します。それが私が第2章で行ったことであり、それはサプライチェーンの研究とサプライチェーン管理の実践に適した方法論に完全に捧げられています。まだ完全ではない第3章は、問題の解決策ではなく、問題自体に焦点を当てる非常に特定の方法論であり、将来的には第3章と現在の章とを交互に進めていく予定です。現在の章は、サプライチェーンの補助科学についてです。
前回の講義では、より優れた、より現代的なコンピューティングハードウェアによって、サプライチェーンの計算能力を向上させることができることを見ました。今日は、別の視点から問題を見ています-私たちはより優れたソフトウェアを持っているため、より多くの計算能力を求めています。それがアルゴリズムについての話です。
簡単に振り返ると、補助科学はサプライチェーン自体の視点です。今日の講義は厳密にはサプライチェーンについてではありません。それはアルゴリズムについてです。しかし、私はそれがサプライチェーンにとって基礎的な重要性を持つと信じています。サプライチェーンは孤立した存在ではありません。サプライチェーンで達成できる進歩は、既に他の隣接分野で達成されている進歩に非常に依存しています。私はそれらの分野をサプライチェーンの補助科学と呼んでいます。
私は、この状況は19世紀の医学科学と化学の関係に非常に似ていると考えています。19世紀初頭には、医学科学は化学に全く関心を持っていませんでした。化学はまだ新参者であり、実際の患者に対する有効な提案とは見なされていませんでした。21世紀になると、化学について何も知らなくても優れた医師になることは完全にばかげたことと見なされるでしょう。優れた化学者であることが優れた医師であることを意味するわけではありませんが、現代の医学科学に関しては、体の化学について何も知らないと、能力がないと一般的に認識されています。私の将来の見通しは、21世紀になると、サプライチェーンの分野は19世紀を通じて医学科学が化学を見るように、アルゴリズムの分野をほぼ同じように見るようになるということです。
アルゴリズムは、研究の巨大な分野であり、数学の一分野です。今日は、この研究分野の表面しか触れません。特に、この研究分野は数十年にわたって驚くべき結果を積み重ねてきました。それはかなり理論的な研究分野かもしれませんが、それは単なる理論だけではありません。実際、この研究分野はかなり理論的な分野ですが、実際には多くの発見が実用化されています。
実際のところ、今日使用しているスマートフォンやコンピュータは、元々どこかで公開された何万ものアルゴリズムを使用しています。この実績は、サプライチェーン理論と比較して非常に印象的です。ほとんどのサプライチェーンは、まだサプライチェーン理論の発見に基づいて動作していません。現代のコンピュータとモダンなアルゴリズムに関しては、ソフトウェアに関連するほとんどすべてが、アルゴリズムの研究の数十年にわたる発見によって完全に駆動されています。これは、私たちが今日使用しているほとんどすべてのコンピュータの核心に非常に関連しています。
今日の講義では、現代のアルゴリズムのトピックに取り組むために知っておくべき内容を示すために、いくつかのトピックを選びました。まず、特にサプライチェーンにおいて、想定される最適なアルゴリズムを実際に上回る方法について議論します。次に、データ構造について簡単に見てみます。その後、魔法のレシピ、テンソル圧縮、最後にメタ技術について説明します。
まず、私が「サプライチェーンのためのアルゴリズム」と言うとき、サプライチェーン固有の問題を解決するためのアルゴリズムを意味しているわけではありません。正しい視点は、古典的な問題に対する古典的なアルゴリズムを見直し、サプライチェーンの視点からそれらの問題を改善できるかどうかを見ることです。答えは「はい、できます」ということです。
たとえば、クイックソートアルゴリズムは、一般的なアルゴリズムの理論によれば、クイックソートよりも優れたアルゴリズムを導入することはできないため、最適と言えます。したがって、この意味では、クイックソートは最善の状態になっています。しかし、特にサプライチェーンに焦点を当てると、驚くほどの高速化が可能です。特に、日付、価格、在庫レベル、カテゴリなど、データセットの基数が低いソート問題を見ると、これらはすべて基数が低いデータセットです。したがって、基数が低い状況などの追加の仮定がある場合、バケットソートを使用することができます。実際のプロダクションでは、クイックソートよりも500倍高速な速度向上を実現できる状況がたくさんあります。したがって、一般的なケースではなく、サプライチェーンのケースにあるため、想定される最適解よりも桁違いに高速になることができます。これは非常に重要なことであり、サプライチェーンのアルゴリズムを活用して驚くべき結果を得るための鍵がここにあると考えています。
この視点は、少なくとも2つの理由で誤解されていると私は考えています。まず、見てきたように、必ずしも標準のアルゴリズムが興味深いわけではありません。クイックソートのような最適なアルゴリズムがある一方で、同じ問題をサプライチェーンの視点から見ると、大幅な高速化が実現できることを見てきました。したがって、一般的なケースではなく、サプライチェーンのケースにあるため、アルゴリズムに精通していることが非常に重要です。
この視点が誤解されている第二の理由は、アルゴリズムは非常にデータ構造に関連しているということです。データ構造は、データをより効率的に操作するための方法です。興味深いことに、これらのデータ構造は一種の語彙を形成しており、この語彙にアクセスできることは、サプライチェーンの状況をソフトウェアに簡単に変換できるようにするために不可欠です。素人の言葉を使って説明を始めると、ソフトウェアに変換するのが非常に困難なものになることが通常です。サプライチェーンについて何も知らないソフトウェアエンジニアに、この変換を実装することを期待するのはトラブルのもとかもしれません。アイデアをソフトウェアに翻訳するためには、この語彙を知っている方がはるかに簡単です。
では、最も人気のあるかつ最もシンプルなデータ構造を見直してみましょう。最初に挙げるのはリストです。リストは、例えば、配達ルートを表すために使用することができます。配達ルートは、配達ごとに1つのエントリがあり、進行しながら配達ルートを列挙することができます。リストはまた、ワークフローを表すこともできます。ワークフローは、特定の機器を製造するために必要な操作のシーケンス、または決定を行うべき人物の連鎖です。
同様に、木構造も広く使われるデータ構造です。ところで、アルゴリズムの木構造は逆さまで、根が上部にあり、枝が下部にあります。木構造を使用すると、さまざまな階層を記述し、サプライチェーンには階層があります。例えば、材料明細書は木構造です。製造したい機器があり、この機器はアセンブリで作られています。各アセンブリはサブアセンブリで構成され、各サブアセンブリは部品で構成されています。材料明細書を完全に展開すると、木構造が得られます。同様に、製品カタログには製品ファミリー、製品カテゴリー、製品、サブカテゴリーなどがあり、非常に頻繁に木構造のアーキテクチャが付属しています。CEOが上部にいて、Cレベルの役員が下部にいる組織図も木構造で表されます。アルゴリズムの理論は、木構造を処理し、効率的に操作を実行するための多くのツールと方法を提供します。データを木構造として表現できる場合、数学的な方法を使って効率的に作業するための完全な方法論が利用できるため、これは非常に興味深いです。
さて、グラフはさまざまなネットワークを記述することができます。ところで、数学的な意味でのグラフは、頂点の集合と辺の集合で構成され、辺が2つの頂点を結びつけています。“グラフ"という用語は少し誤解を招くかもしれませんが、グラフはグラフィックスとは何の関係もありません。グラフは単なる数学的なオブジェクトであり、描画やグラフィカルなものではありません。グラフを探す方法を知っていると、サプライチェーンにはグラフがたくさんあります。
いくつかの例を挙げます。小売ネットワークのアソートメントは、基本的には二部グラフであり、製品と店舗を接続します。クライアントが時間の経過とともにどの製品を購入したかを記録するロイヤリティプログラムがある場合、クライアントと製品を接続する別の二部グラフがあります。自動車アフターマーケットでは、実行する修理がある場合、通常、興味のある車両と機械的な互換性のある部品のリストを示す互換性行列を使用する必要があります。この互換性行列は本質的にはグラフです。グラフに関連するさまざまなアルゴリズムについての文献が非常に多くありますので、問題をグラフ構造で特徴付けることができると非常に興味深いです。なぜなら、文献で知られているすべての方法がすぐに利用できるからです。
最後に、今日取り上げる最後のデータ構造はハッシュテーブルです。ハッシュテーブルは、アルゴリズムのスイスアーミーナイフのような存在です。新しいものではありません。紹介したデータ構造のいずれも、どれも最近のものではありません。ハッシュテーブルはおそらく最も新しいものであり、1950年代から存在しているので、最近のものではありません。それにもかかわらず、ハッシュテーブルは非常に便利なデータ構造です。キーと値のペアを含むコンテナです。このコンテナを使用すると、大量のデータを格納でき、ルックアップ、挿入、削除のパフォーマンスがO(1)で提供されます。データを追加するためのコンテナであり、データが存在するかどうかを調べることができます（キーを見ることによって）、そしてデータを削除することもできます。これは非常に興味深く、有用です。ハッシュテーブルは文字通りあらゆる場所にあり、他のアルゴリズムの内部で広範に使用されています。
一つ指摘しておくことがありますが、ハッシュテーブルのパフォーマンスは、使用しているハッシュ関数のパフォーマンスに非常に依存しているということです。
さて、魔法のレシピを見てみましょう。ここからはまったく異なる視点に切り替えます。魔法の数値は基本的にはアンチパターンです。前の講義で、サプライチェーンのネガティブな知識について話しましたが、アンチパターンは通常、良い意図から始まりますが、解決策によってもたらされるはずの利益を無効にする予期しない結果に終わります。魔法の数値はよく知られたプログラミングのアンチパターンです。このプログラミングのアンチパターンは、完全に突然現れるような定数でコードが埋め尽くされ、ソフトウェアの保守が非常に困難になります。定数がたくさんあると、なぜそれらの制約があるのか、どのように選ばれたのかがわかりません。
通常、プログラムで魔法の数値を見ると、それらの定数を管理しやすい場所に分離する方が良いです。ただし、定数の注意深い選択によって完全に予期しない結果が生じる場合もあります。そして、空から降ってきたかのような数値を使用することで、まるで魔法のような完全に予期しない利点が得られます。これが、ここで紹介する非常に短いアルゴリズムの内容です。
サプライチェーンでは、非常に頻繁にある種のシミュレーションを実現したいと思うことがあります。シミュレーションやモンテカルロプロセスは、サプライチェーンのさまざまな状況で使用できる基本的なトリックの一つです。ただし、シミュレーションのパフォーマンスは、ランダムな数値を生成する能力に非常に依存しています。シミュレーションを生成するためには、通常、生成されたランダム性が関与しており、そのためにはこのランダム性を生成するアルゴリズムが必要です。コンピュータにとっては、通常、疑似乱数です。真のランダム性ではなく、ランダムな数値の統計的属性を持つものですが、実際にはランダムではありません。
問題は、どれだけ効率的にランダムな数値を生成できるかということです。実際には、George Marsagliaによって2003年に発表された「Shift」というアルゴリズムが非常に印象的です。このアルゴリズムは非常に高品質なランダムな数値を生成し、2の64乗マイナス1ビットの完全な置換を作成します。これは、すべての64ビットの組み合わせを、1を固定点として、回転させることを意味します。これには、基本的に6つの操作が必要です。3つのバイナリシフトと3つの排他的論理和（XOR）演算です。シフトもビット演算です。
そこで、その中には3つの魔法の数値があることがわかります。13、7、17です。ちなみに、これらの数値はすべて素数です。これは偶然ではありません。これらの非常に特定の定数を選ぶと、非常に高速な優れた乱数生成器が得られます。ここで言う高速とは、秒間10メガバイトの乱数を生成できるということです。これは絶対に膨大な量です。前の講義に戻ると、このアルゴリズムが非常に効率的なのはなぜかがわかります。プロセッサなどの基礎となるコンピューティングハードウェアがネイティブにサポートする命令に直接マッピングされる6つの命令しかなく、分岐がないからです。テストもないため、このアルゴリズムは実行されると、分岐がないためプロセッサのパイプライニング容量を最大限に活用することができます。現代のプロセッサに備わっている深いパイプライニング容量を最大限に活用することができます。非常に興味深いです。
問題は、このアルゴリズムを動作させるために他の数値を選ぶことができるかということです。答えはノーです。実際に動作する数十個、おそらく100個程度の異なる数値の組み合わせしかありません。それ以外の組み合わせでは、非常に低品質な数値生成器が得られます。それが魔法の部分です。アルゴリズムの開発において、非常に予期しないものを見つけ出し、非常に予期しないバイナリ演算の組み合わせによって完全に予期しない利点を得るという最近のトレンドがあります。乱数生成はサプライチェーンにとって非常に重要です。
しかし、私が言っていたように、ハッシュテーブルはどこにでもあり、超高性能の汎用ハッシュ関数を持つことも非常に興味深いです。それは存在するのでしょうか？はい。数十年にわたって利用可能なハッシュ関数のクラスが存在していますが、2019年には記録を更新するパフォーマンスを提供する別のアルゴリズムが公開されました。これは画面上で見ることができるもので、“WyHash"というものです。基本的に、この構造はXORShiftアルゴリズムと非常に似ていることがわかります。XORShiftと同様に、分岐のないアルゴリズムであり、XOR演算も使用しています。このアルゴリズムは、4つのXOR演算と2つのMultiply-No-Flags演算の6つの命令を使用しています。
Multiply-No-Flagsは、2つの64ビット整数間の通常の乗算であり、その結果、上位64ビットと下位64ビットを収集します。これは、モダンなプロセッサで実装されたハードウェアレベルの実際の命令であり、1つのコンピュータ命令としてカウントされます。私たちはそれを2つ持っています。また、16進数形式で書かれた3つの魔法の数値があります。ちなみに、それらは再び素数ですが、完全に半魔法的です。このアルゴリズムを適用すると、メモリコピーの速度で動作する非暗号化ハッシュ関数が得られます。非常に高速で非常に興味深いものです。
さて、また完全に異なる話題に切り替えましょう。深層学習の成功や他の多くの現代の機械学習手法の成功は、専用のコンピューティングハードウェアによって大幅に加速できる問題に関するいくつかの重要なアルゴリズム的な洞察にあります。これについては、以前の講義でスーパースカラ命令を持つプロセッサや、さらに欲しい場合はGPUやTPUについて話しました。この洞察を再訪して、全体がどのように混沌として出現したかを見てみましょう。ただし、関連する洞察はここ数年で結晶化してきたと私は信じています。現在の立場を理解するためには、アルバート・アインシュタインが約100年前に彼の論文の1つで導入したアインシュタイン表記に戻る必要があります。直感的な考え方は簡単です。式yは、iが1から3までの範囲でc_y times x_yの和です。私たちはそのように書かれた式を持っており、アインシュタイン表記の直感は、このような状況では、和を完全に省略して書くべきだと言うことです。ソフトウェアの場合、和はforループになります。アイデアは、和を完全に省略し、意味のある変数iのすべてのインデックスに対して和を取るという規約であると言うことです。
この単純な直感により、非常に驚くべきがポジティブな結果が2つ得られます。1つ目は設計の正確さです。和を明示的に書くと、適切なインデックスがない可能性があり、ソフトウェアでインデックスが範囲外になるエラーが発生する可能性があります。明示的な和を削除し、有効なインデックス位置を定義によってすべて取ると宣言することで、設計による正確さが得られます。これだけでも非常に興味深く、私の以前の講義の1つで触れた配列プログラミングに関連しています。
2つ目の洞察は、最近のものであり、現在非常に興味深いものです。アインシュタイン表記が適用可能な形式で問題を書くことができる場合、実際には大規模なハードウェアアクセラレーションの恩恵を受けることができます。これはゲームチェンジングな要素です。
この理由を理解するために、Facebookの研究チームによって2018年に発表された非常に興味深い論文「テンソルコンプリヘンション」があります。彼らはテンソルコンプリヘンションという概念を紹介しました。まず、2つの単語を定義しましょう。コンピュータサイエンスの分野では、テンソルは本質的には多次元行列です（物理学では、テンソルはまったく異なります）。スカラー値は次元ゼロのテンソルであり、ベクトルは次元1のテンソルであり、行列は次元2のテンソルであり、さらに高次元のテンソルも持つことができます。テンソルは、それに関連付けられた配列のようなプロパティを持つオブジェクトです。
コンプリヘンションは、プラス、マイナス、乗算、除算などの四則演算と他の演算を含む、通常の算術代数よりも広範です。テンソル代数ではなく、テンソルコンプリヘンションを持っているのは、それがより包括的であるが、完全なプログラミング言語ほど表現力がないからです。コンプリヘンションを持つと、何をしたいかに比べて、何ができるかが制限されます。
アイデアは、MV関数（def MV）を見ると、基本的には関数であり、MVは行列-ベクトルを表しています。この場合、行列-ベクトルの乗算であり、この関数は基本的に行列AとベクトルXの間の乗算を実行しています。この定義では、アインシュタイン表記が使用されていることがわかります：C_i = A_ik * X_kと書かれています。iとkにはどのような値を選ぶべきですか？答えは、インデックスである変数のすべての有効な組み合わせです。すべての有効なインデックス値を取り、合計を行い、実際にはこれによって行列-ベクトルの乗算が得られます。
画面の下部には、同じMVメソッドがforループを使用して書き直されており、値の範囲を明示的に指定しています。Facebookの研究チームの主な成果は、テンソルコンプリヘンションのこの構文でプログラムを書くことができる場合、彼らが開発したコンパイラによって、GPUを使用したハードウェアアクセラレーションを大幅に活用できることです。基本的に、このテンソルコンプリヘンションの構文で書くことができるプログラムを加速することができます。この形式でプログラムを書くことができる場合、大規模なハードウェアアクセラレーションの恩恵を受けることができます。通常のプロセッサよりも2桁速いものになります。これはその成果自体で見ると驚くべき結果です。
さて、このアプローチでサプライチェーンの観点から何ができるか見てみましょう。現代のサプライチェーンの実践にとって重要な関心事の1つは、確率的予測です。確率的予測は、以前の講義で取り上げたように、興味のある変数のさまざまな確率を予測するという考えです。たとえば、リードタイムの予測を考えてみましょう。リードタイムを予測し、確率的なリードタイムの予測を行いたいとします。
さて、リードタイムは製造リードタイムと輸送リードタイムに分解できるとしましょう。現実には、おそらく製造リードタイムの確率的予測があります。これは、1日、2日、3日、4日などの時間を観測する確率を与える離散的な確率変数であり、製造リードタイムのこの期間を観測する確率を与える大きなヒストグラムと考えることができます。次に、輸送リードタイムに対しても同様のプロセスがあり、別の離散的な確率変数が確率的な予測を提供します。
さて、合計リードタイムを計算したいとします。予測されたリードタイムが数値であれば、単純な加算を行うだけです。しかし、2つの予測されたリードタイムは数値ではありません。それらは確率分布です。したがって、これら2つの確率分布を組み合わせて、合計リードタイムの確率分布を得る必要があります。実際には、製造リードタイムと輸送リードタイムの2つのリードタイムが独立であるという仮定を行うと、ランダム変数のこの和の計算に行うことができる操作は、1次元畳み込みです。これは複雑に聞こえるかもしれませんが、実際にはそれほど複雑ではありません。私が実装したものであり、画面上で見ることができるのは、製造リードタイムの確率のヒストグラムを表すベクトル（A）と輸送リードタイムの確率に関連するヒストグラム（B）の間の1次元畳み込みの実装です。その結果は、確率的なリードタイムの合計であり、テンソルの理解表記を使用すると、非常にコンパクトな1行のアルゴリズムで書くことができます。
さて、この講義で前に紹介したビッグO表記に戻ると、基本的には2次のアルゴリズムです。NをAとBの配列の特性サイズとします。先ほど述べたように、2次のパフォーマンスは予測の問題のスイートスポットです。では、この問題に対処するためにはどうすればよいでしょうか？まず、これがサプライチェーンの問題であることを考慮する必要があります。そして、私たちが利用できる小数の法則を利用することができます。前の講義で議論したように、サプライチェーンは主に小数に関するものです。リードタイムを見てみると、そのリードタイムは、たとえば400日よりも小さいと合理的に想定できます。これは、この確率のヒストグラムにとってはすでにかなり長い時間です。
したがって、N^2のビッグOが残りますが、Nは400よりも小さいです。400はかなり大きいかもしれません。400を400倍すると160,000になります。それはかなりの数ですし、この確率分布に加えることは非常に基本的な操作です。確率的な予測を行うと、予測をさまざまな方法で組み合わせたくなるでしょうし、おそらく何百万ものこれらの畳み込みを行うことになるでしょう。なぜなら、基本的には、これらの畳み込みはランダム変数の領域に投影された、ただの加算にすぎないからです。したがって、Nを400よりも小さく制約していても、ハードウェアアクセラレーションを取り入れることは非常に興味深いことです。それがテンソルの理解で実現できることです。
覚えておくべき重要なことは、そのアルゴリズムを書くことができるとすぐに、サプライチェーンの概念について知っていることを活用して、適用可能な仮定を明確にし、それからハードウェアアクセラレーションを得るために持っているツールキットを活用することです。
さて、メタテクニックについて話しましょう。メタテクニックは非常に興味深いものです。なぜなら、既存のアルゴリズムの上にレイヤー化することができるからです。したがって、アルゴリズムがあれば、そのパフォーマンスを向上させるためにこれらのメタテクニックのいずれかを使用できる可能性があります。最初の重要な洞察は、データの圧縮です。なぜなら、データが小さいほど処理が速くなるからです。前の講義で見たように、一様なメモリアクセスはありません。より多くのデータにアクセスするには、異なるタイプの物理メモリにアクセスする必要があります。メモリが増えるにつれて、はるかに効率の悪いメモリに到達します。プロセッサ内部のL1キャッシュは非常に小さく、約64キロバイトですが、非常に高速です。RAMまたはメインメモリは、この小さなキャッシュよりも数百倍遅く、テラバイトのRAMを持つことができます。したがって、データが可能な限り小さくなるようにすることは非常に重要です。これにより、ほとんどの場合、アルゴリズムがより速く実行されます。この点に関しては、いくつかのトリックがあります。
まず、データを整理して整頓することができます。これはエンタープライズソフトウェアの領域です。データに対して実行されるアルゴリズムがある場合、解決に寄与しない未使用のデータが多く存在することがよくあります。興味のあるデータが無視されることなく、データが交互に配置されないようにすることが重要です。
2つ目のアイデアはビットパッキングです。ポインタなどの他の要素の内部にいくつかのフラグをパックすることができる状況はたくさんあります。64ビットのポインタを持っているかもしれませんが、実際には64ビットのアドレス範囲が完全に必要なことは非常に稀です。いくつかのビットをポインタに犠牲にしてフラグを注入することで、ほとんどパフォーマンスの損失を伴わずにデータを最小化することができます。
また、精度を調整することもできます。サプライチェーンで64ビットの浮動小数点精度が必要ですか？実際にはこの精度が必要なことは非常に稀です。通常、32ビットの精度で十分であり、16ビットの精度で十分な状況もたくさんあります。精度を減らすことは重要ではないと思うかもしれませんが、データのサイズを2で割ることができると、アルゴリズムのスピードが2倍になるだけでなく、実際には10倍になります。データのパッキングは、実行速度の観点から完全に非線形の利益をもたらします。
最後に、エントロピー符号化があります。ただし、ZIPアーカイブに使用されるアルゴリズムほど効率的に圧縮する必要はありません。圧縮の効率よりも実行速度がはるかに速いものが必要です。
圧縮は基本的には、メモリの圧力を減らすために少しの追加CPU使用をトレードオフすることができるという考えに基づいています。ほとんどの場合、これが興味のあるトリックです。
ただし、CPUの消費を大幅に減らすためにメモリをトレードオフしたい場合もあります。それがメモ化のトリックです。メモ化は、解決策の実行中に関数が多く呼び出され、同じ関数が同じ入力で呼び出されている場合、関数を再計算する必要がないという考えです。結果を記録し、それを横に置いておくことができます（たとえば、ハッシュテーブルに）。同じ関数を再訪するときに、ハッシュテーブルにすでに入力に関連付けられたキーが含まれているか、ハッシュテーブルに結果がすでに含まれているかを確認することができます。メモ化する関数が非常に高価な場合、大幅なスピードアップが可能です。非常に興味深いのは、前の講義で見たように、メモ化をメインメモリではなくディスクやSSDに使用し始める場合です。ディスクやSSDは安価で豊富なため、SSDをCPUの圧力の削減と引き換えに使用することができます。これは、まさに先ほど説明した圧縮とは正反対のアイデアです。
最後のメタテクニックは不変性です。不変データ構造は、基本的に変更されないデータ構造です。変更は上に重ねられます。たとえば、不変なハッシュテーブルでは、要素を追加すると、古いハッシュテーブルに含まれるすべての要素と新しい要素を含む新しいハッシュテーブルを返します。非常に素朴な方法は、データ構造全体をコピーして返すことですが、非効率です。不変データ構造のキーとなる洞察は、データ構造を変更すると、変更のみを実装する新しいデータ構造を返すが、変更されていない古いデータ構造の部分は再利用するということです。
リスト、木、グラフ、ハッシュテーブルなど、ほとんどのクラシックなデータ構造には、不変性の対応するものがあります。多くの状況で、それらを使用することが非常に興味深いです。ちなみに、Clojureなどの現代のプログラミング言語は、完全に不変性に取り組んでいます。
なぜそれが非常に興味深いのでしょうか？まず第一に、アルゴリズムの並列化を大幅に簡素化するからです。前の講義で見たように、一般的なデスクトップコンピュータプロセッサで100 GHzで動作するプロセッサを見つけることはできません。ただし、2 GHzで動作する50個のコアを持つマシンを見つけることができます。これらの多くのコアを活用するためには、実行を並列化する必要がありますが、その並列化は競合状態と呼ばれる非常に厄介なバグのリスクがあります。コンピュータの同じメモリ領域に書き込もうとするさまざまなプロセッサが同時に存在する可能性があるため、自分が書いたアルゴリズムが正しいかどうかを理解するのは非常に難しくなります。
しかし、不変なデータ構造があれば、これは設計上起こりません。なぜなら、データ構造が提示された後は変更されないため、新しいデータ構造のみが現れるからです。したがって、不変なパスを使用することで、並列バージョンのアルゴリズムをより簡単に実装できるため、大幅なパフォーマンスの向上が実現できます。通常、アルゴリズムの高速化のボトルネックは、アルゴリズムを実際に実装するためにかかる時間です。何らかの恐れを知らない並行性の原則を適用できるものがあれば、プログラマの数に関するリソースを少なくして、アルゴリズムの高速化を実際に展開できます。不変なデータ構造のもう一つの重要な利点は、デバッグを大幅に容易にすることです。データ構造を破壊的に変更し、バグが発生した場合、そこにたどり着いた方法を特定するのは非常に難しいかもしれません。デバッガを使用すると、問題の特定が非常に困難な経験になる場合があります。不変なデータ構造の興味深い点は、変更が破壊的ではないため、以前のバージョンのデータ構造を見ることができ、どのようにして誤った動作に至ったのかをより簡単に把握できることです。
結論として、より良いアルゴリズムは超能力のように感じるかもしれません。より良いアルゴリズムにより、同じコンピューティングハードウェアからより多くの利益を得ることができ、これらの利点は無限です。これは一度の努力であり、その後は無限のメリットがあります。なぜなら、同じ量のコンピューティングリソースを供給チェーンの問題に割り当てた場合、優れた計算能力にアクセスできるからです。私はこの視点が供給チェーン管理の大幅な改善の機会を提供していると考えています。
ゲームなど、まったく異なる分野を見てみると、ゲーム体験に特化した独自のアルゴリズムの伝統と知見が確立されています。現代のビデオゲームで体験する見事なグラフィックスは、ゲームコミュニティが数十年にわたってアルゴリズムスタック全体を再考し、グラフィック体験の品質を最大化するために取り組んだ結果です。ゲームの視点は、物理的または科学的な観点から正しい3Dモデルを持つことではなく、プレイヤーのグラフィック体験の品質を最大化することです。そして、彼らは見事な結果を実現するためにアルゴリズムを微調整しています。
私は、供給チェーンに関しては、このような作業がほとんど始まったばかりだと考えています。企業の供給チェーンソフトウェアは停滞しており、現代のコンピューティングハードウェアが私たちに提供できるものの1%も使用していないというのが私の認識です。機会のほとんどはこれからであり、供給チェーンのアルゴリズムだけでなく、供給チェーンの視点からクラシックなアルゴリズムを再検討することで、途中で大幅な高速化を実現できます。
さて、質問を見てみましょう。
質問: 供給チェーンの特定の事例、例えば小規模な数値を持つ場合、潜在的な意思決定全体にわたって小規模な数値があることがわかっている場合、在庫報酬関数を計算するために使用されるホリスティックな予測の粒度レベルにどのような簡素化がもたらされると考えられますか？
まず、今日私が紹介したすべての内容は、Lokadで実際に製品化されています。これらの洞察は、供給チェーンに非常に適用可能です。現代のソフトウェアから得られるものは、計算ハードウェアの最大限の活用を目指して調整されていないことを認識する必要があります。私が前回の講義で紹介したように、数十年前と比べて、現在のコンピュータは1000倍も性能が向上しています。それらは1000倍も速く動作するのでしょうか？そうではありません。数十年前よりもはるかに複雑な問題に取り組むことができるのでしょうか？そうではありません。ですので、改善の余地は非常に大きいということを過小評価しないでください。
この講義で紹介したバケットソートは単純な例です。供給チェーンではソート操作が至る所で行われており、私の知る限り、供給チェーンの状況に適した専門のアルゴリズムを活用する企業向けのソフトウェアは非常に珍しいです。では、1つまたは2つのコンテナを持つことがわかっている場合、Lokadではそれらの要素を常に活用していますし、そのレベルで実装できるトリックもたくさんあります。
これらのトリックは通常、より低いレベルで行われ、利点は全体的な解決策に波及します。コンテナの充填問題をすべてのサブパートに分解することを考えてみてください。私が今日紹介したアイデアやトリックを低レベルで適用することで利益を得ることができます。
例えば、コンテナについてどのような数値の精度が必要ですか？たとえば、16ビットの数値で十分な場合があります。これによりデータが小さくなります。注文する異なる製品の数はどれくらいですか？おそらく数千の異なる製品しか注文していないので、バケットソートを使用できます。確率分布はより小さな数値ですので、理論的にはヒストグラムはゼロユニット、1ユニット、3ユニットから無限大までの範囲になりますが、無限大まで必要ですか？いいえ、必要ありません。おそらく、1,000ユニットを超えるヒストグラムに遭遇することは非常に稀ですので、近似することができます。1,000ユニットを含むコンテナを扱う場合、2ユニットの精度が必要ではありません。より大きなバケットを持つヒストグラムなど、近似することができます。これは、テンソルの理解などのアルゴリズム原則を導入することではなく、非常にクールな方法ですべてを簡素化するテンソルの理解のようなものではありません。ただし、最終的な結果としてのアルゴリズムの高速化のほとんどは、より高速ですがやや複雑なアルゴリズムになります。必ずしも単純ではないのです。最も単純なアルゴリズムは効率的ではないことが通常です。ケースに適したより適切なアルゴリズムは、少し長く書く必要があり、より複雑ですが、最終的にはより速く実行されます。これは常にそうではありませんが、魔法のレシピで見たように、私たちが実際にエンタープライズソフトウェアを構築するためには、基本的な構築ブロックを見直す必要があることを示したかったのです。
質問: これらの洞察は、ERPベンダーやAPS、GTAなどのベストオブブリードにどの程度実装されていますか？
興味深いことに、これらの洞察は、基本的にはトランザクションソフトウェアとは完全に互換性がありません。ほとんどのエンタープライズソフトウェアは、トランザクションデータベースを中心に構築されており、すべての操作がデータベースを介して行われます。このデータベースは、供給チェーン固有のデータベースではなく、財務、科学計算、医療記録など、思いつく可能性のあるすべての状況に対応できる汎用のデータベースです。
問題は、対象のソフトウェアがトランザクションデータベースを中心に構築されている場合、私が提案した洞察を設計上実装することはできないということです。ゲームビデオを見てみましょう。ゲームビデオの中でトランザクションデータベースの上に構築されているものはいくつありますか？答えはゼロです。なぜでしょうか？なぜなら、トランザクションデータベースの上にグラフィックスパフォーマンスを実装することはできないからです。トランザクションデータベースでコンピュータグラフィックスを行うことはできません。
トランザクションデータベースは非常に便利です。トランザクション性を提供してくれますが、ほとんどのアルゴリズムの高速化は適用できません。私たちがAPSについて考え始めるとき、これらのシステムには何も先進的なものはありません。これらのシステムは数十年間過去に取り残されており、アルゴリズムの分野で生まれた洞察を適用することができないためです。
それがエンタープライズソフトウェアの分野の問題の核心です。製品の設計の最初の月に行う設計上の決定は、実質的には時間の終わりまで、数十年間、あなたを苦しめることになります。製品の特定の設計を決めた後にアップグレードすることはできません。それに取り組むしかありません。まるで車を電気自動車に再設計することはできないのと同じです。非常に優れた電気自動車を作りたい場合、車を完全に電気エンジンを中心に再設計する必要があります。エンジンを交換して「ここに電気自動車があります」と言うだけではうまくいきません。これは、一度電気自動車の製造を決定したら、エンジンを中心にすべてを見直す必要がある、そのような設計原則の一つです。残念ながら、データベースを中心としたERPやAPSは、これらの洞察を利用することができません。これらのトリックを利用できる孤立したバブルが存在する可能性は常にありますが、それはコアにはなりません。
Blue Yonderの印象的な機能に関しては、LokadはBlue Yonderの直接の競合他社であるため、完全に公平ではない立場であるため、お許しください。エンタープライズソフトウェア市場では、競争力を維持するために非常に大胆な主張をしなければなりません。私はこの市場で誰もが印象的なものを持っているという前提には納得していません。
もしも何か驚くべきもの、超印象的なものを見たいのであれば、Unreal Engineの最新デモや専門のビデオゲームアルゴリズムを見てみてください。次世代のPlayStation 5のハードウェア上のコンピュータグラフィックスは、まったく見事です。エンタープライズソフトウェアの分野で同じような技術的な成果を持っているものはありますか？Lokadに関しては、私は非常に偏った意見を持っていますが、市場全体を見ると、関係データベースの限界を追求し続けてきた人々の海が広がっています。時にはグラフデータベースなど、他のタイプのデータベースを持ち込むこともありますが、それは私が提示した洞察のポイントを完全に見逃しています。サプライチェーンの世界に価値を提供するための実質的なものは何も提供していません。
ここでの重要なメッセージは、設計の問題です。エンタープライズソフトウェアの設計において最初の決定が、最初からこれらの技術を使用することを阻止するようなものであってはなりません。
次回の講義は3週間後の水曜日の午後3時に行われます。それは6月13日で、第3章であるサプライチェーンの人員、驚くべき性格特性、そして架空の会社について再訪します。次回はチーズについて話します。それではまた次回をお楽しみに！
