学習拡張アルゴリズム

学習拡張アルゴリズムは、予測を利用してパフォーマンスを向上させることができるアルゴリズムです。 ^[1] 通常のアルゴリズムでは問題インスタンスのみが入力されますが、学習拡張アルゴリズムは追加のパラメータを受け入れます。この追加のパラメータは、多くの場合、ソリューションの何らかの特性の予測です。この予測は、アルゴリズムによって実行時間や出力の品質を向上させるために使用されます。

学習拡張アルゴリズムは通常、入力 を受け取ります。ここでは問題インスタンス 、アドバイス は、最適解の特定のプロパティに関する予測です。問題インスタンスのタイプと予測はアルゴリズムによって異なります。学習拡張アルゴリズムは通常、次の 2 つのプロパティを満たします。 ${\displaystyle ({\mathcal {I}},{\mathcal {A}})}$${\displaystyle {\mathcal {I}}}$${\displaystyle {\mathcal {A}}}$

• 一貫性。学習拡張アルゴリズムは、正確な予測が与えられたときにアルゴリズムが優れたパフォーマンスを発揮することが証明されれば、一貫性があると言われます。^[1]通常、これは予測の誤差に依存するパフォーマンスの限界を与えることによって定量化されます。
• 堅牢性。与えられた予測が不正確であっても、最悪の場合のパフォーマンスが制限される場合、アルゴリズムは堅牢であると呼ばれます。^[1]

学習拡張アルゴリズムでは、一般的に予測をどのように行うべきかは規定されません。この目的のために機械学習を使用することができます。^{[引用が必要]}

バイナリ検索アルゴリズムは、ソートされたリストの要素を見つけるためのアルゴリズムです。長さのリストから既知の値を持つ要素を見つけるには、ステップが必要です。の位置を予測することで、次の学習拡張アルゴリズムを使用できます。^[1]${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle O(\log(n))}$${\displaystyle x}$${\displaystyle n}$${\displaystyle i}$${\displaystyle x}$

• まず、リスト内の位置を確認します。 の場合、要素が見つかりました。${\displaystyle i}$${\displaystyle x_{i}=y}$
• の場合、を含むインデックスが見つかる まで位置を調べます。${\displaystyle x_{i}<y}$${\displaystyle i+1,i+2,i+4,\ldots }$${\displaystyle j}$${\displaystyle x_{j}\geq y}$
  • ここで、 に対してバイナリ検索を実行します。${\displaystyle x_{i},\ldots ,x_{j}}$
• の場合、前の場合と同じようにしますが、代わりに を考慮します。${\displaystyle x_{i}>y}$${\displaystyle i-1,i-2,i-4,\ldots }$

誤差は と定義されます。ここで はの実際のインデックスです。学習拡張アルゴリズムでは、位置の調査にステップがかかります。次に、最大 のサイズのリストに対してバイナリ検索が実行され、 ステップがかかります。これにより、アルゴリズムの合計実行時間は になります。したがって、誤差が小さい場合、アルゴリズムは通常のバイナリ検索よりも高速です。これは、アルゴリズムが一貫していることを示しています。最悪の場合でも、誤差は最大 になります。この場合、アルゴリズムは最大ステップを要するため、アルゴリズムは堅牢です。 ${\displaystyle \eta =|i-i^{*}|}$${\displaystyle i^{*}}$${\displaystyle y}$${\displaystyle i+1,i+2,i+4,\ldots }$${\displaystyle \log _{2}(\eta )}$${\displaystyle 2\eta }$${\displaystyle \log _{2}(\eta )}$${\displaystyle 2\log _{2}(\eta )}$${\displaystyle n}$${\displaystyle O(\log(n))}$

学習拡張アルゴリズムは次のようなことで知られています。

• スキーレンタル問題^[2]
• 最大重量マッチング問題^[3]
• 重み付けページング問題^[4]

• 機械学習

• 拡張アルゴリズムの学習に関する出版物の概要