早期終了

機械学習において、早期停止は、勾配降下法などの反復法でモデルをトレーニングする際に過剰適合を避けるために使用される正則化の一種です。このような方法では、各反復でモデルを更新して、トレーニング データにより適合するようにします。ある程度までは、これによりトレーニング セット外のデータ (検証セットなど) に対するモデルのパフォーマンスが向上します。ただし、その時点を超えると、トレーニング データへのモデルの適合性を向上させると、一般化エラーが増加するという代償が伴います。早期停止規則は、学習器が過剰適合し始める前に実行できる反復回数に関するガイダンスを提供します。早期停止規則は、さまざまな機械学習方法で採用されており、理論的根拠の程度はさまざまです。

このセクションでは、早期停止方法の説明に必要な基本的な機械学習の概念のいくつかを紹介します。

機械学習アルゴリズムは、有限のトレーニング データ セットに基づいてモデルをトレーニングします。このトレーニング中、モデルはトレーニング セットに含まれる観測値をどれだけ正確に予測できるかに基づいて評価されます。ただし、一般的に、機械学習スキームの目標は、一般化、つまり、これまでに見たことのない観測値を予測するモデルを作成することです。モデルがトレーニング セットのデータによく適合している一方で、一般化エラーが大きくなると、過剰適合が発生します。

機械学習の文脈における正則化とは、過剰適合を防ぐために学習アルゴリズムを変更するプロセスを指します。これは通常、学習したモデルに何らかの平滑性制約を課すことを伴います。^[1] この平滑性は、モデル内のパラメータの数を固定するか、ティホノフ正則化のようにコスト関数を拡張することによって明示的に強制することができます。ティホノフ正則化は、主成分回帰や他の多くの正則化スキームとともに、フィルターの適用を特徴とする正則化であるスペクトル正則化の傘下にあります。早期停止もこのクラスの方法に属します。

勾配降下法は、一次反復最適化法です。各反復では、目的関数の勾配の負の方向にステップを踏むことで、最適化問題の近似解を更新します。ステップ サイズを適切に選択することで、このような方法で目的関数の局所的最小値に収束させることができます。勾配降下法は、機械学習で、トレーニング セットに対する学習者のエラーを反映する損失関数を定義し、その関数を最小化することで使用されます。

早期停止は、機械学習で遭遇するノンパラメトリック回帰問題を正規化するために使用できます。与えられた入力空間、、出力空間、、および未知の確率測度、、から抽出されたサンプルに対して、このような問題の目標は、次式で与えられる 回帰関数、を近似することです。${\displaystyle X}$${\displaystyle Y}$${\displaystyle \rho}$${\displaystyle Z=X\times Y}$${\displaystyle f_{\rho}}$

${\displaystyle f_{\rho }(x)=\int _{Y}y\,d\rho (y\mid x),\,x\in X,}$

ここで、はによって誘導されるにおける条件付き分布です。^[2] 回帰関数を近似するための一般的な選択肢の 1 つは、再生核ヒルベルト空間からの関数を使用することです。^[2]これらの空間は無限次元になる可能性があり、その場合、任意のサイズのトレーニング セットに過剰適合するソリューションを提供することができます。したがって、これらの方法では正則化が特に重要です。ノンパラメトリック回帰問題を正則化する 1 つの方法は、勾配降下法などの反復手順に早期停止規則を適用することです。 ${\displaystyle \rho (y\mid x)}$${\displaystyle x}$${\displaystyle \rho}$

これらの問題に対して提案された早期停止規則は、反復回数の関数としての一般化誤差の上限の分析に基づいています。これにより、解法プロセスを開始する前に計算できる反復回数の規定が得られます。^{[3] [4]}

（Yao、Rosasco、Caponnetto、2007 ^[3]より改変）

サンプルの集合が与えられ ている${\displaystyle X\subseteq \mathbb {R} ^{n}}$${\displaystyle Y=\mathbb {R} .}$

${\displaystyle \mathbf {z} =\left\{(x_{i},y_{i})\in X\times Y:i=1,\dots ,m\right\}\in Z^{m},}$

から独立して描画され、機能を最小限に抑える ${\displaystyle \rho}$

${\displaystyle {\mathcal {E}}(f)=\int _{X\times Y}(f(x)-y)^{2}\,d\rho }$

ここで、は再生核ヒルベルト空間の要素です。つまり、最小二乗損失関数の期待リスクを最小化します。 は未知の確率測度に依存するため、計算には使用できません。代わりに、次の経験的リスクを考えます。 ${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {E}}}$${\displaystyle \rho}$

${\displaystyle {\mathcal {E}}_{\mathbf {z} }(f)={\frac {1}{m}}\sum _{i=1}^{m}\left(f(x_{i})-y_{i}\right)^{2}.}$

および を、それぞれ期待リスクと経験的リスクに適用される勾配降下法のt回目の反復とします。ここで、両方の反復は原点で初期化され、両方ともステップ サイズ を使用します。は母集団反復 を形成し、 に収束しますが、計算には使用できません。一方、 は標本反復を形成し、通常は過剰適合解に収束します。 ${\displaystyle f_{t}}$${\displaystyle f_{t}^{\mathbf {z} }}$${\displaystyle \gamma_{t}}$${\displaystyle f_{t}}$${\displaystyle f_{\rho}}$${\displaystyle f_{t}^{\mathbf {z} }}$

サンプル反復の期待リスクと最小期待リスク、つまり回帰関数の期待リスクとの差を制御したいのです。

${\displaystyle {\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{\rho })}$

この差は、サンプル反復と母集団反復の間の期待リスクの差と、母集団反復と回帰関数の間の期待リスクの差という 2 つの項の合計として書き直すことができます。

${\displaystyle {\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{\rho })=\left[{\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{t})\right]+\left[{\mathcal {E}}(f_{t})-{\mathcal {E}}(f_{\rho })\right]}$

この方程式はバイアスと分散のトレードオフを示しており、これを解くことで未知の確率分布に依存する最適な停止規則が得られます。この規則には、一般化誤差の確率的境界が関連付けられています。早期停止規則と境界につながる分析については、元の論文を参照してください。^[3]実際には、データ駆動型手法、たとえばクロスバリデーションを使用して、適応型停止規則を取得できます。

ブースティングとは、一連の弱い学習器（真のプロセスとわずかに相関する学習器）を組み合わせて強い学習器を生成するアルゴリズムのファミリーを指します。いくつかのブースティングアルゴリズム（AdaBoostを含む）では、早期停止による正則化によって一貫性が保証され、つまりサンプル数が無限大になるほどアルゴリズムの結果が真の解に近づくことが示されています。^{[5] [6] [7] [8]}

ブースティング法は、上記の勾配降下法と密接な関係があり、損失に基づいたブースティング法として考えることができます：L ₂ブースト。^[3]${\displaystyle L_{2}}$

これらの早期停止ルールは、元のトレーニング セットを新しいトレーニング セットと検証セットに分割することによって機能します。検証セットのエラーは、オーバーフィッティングが始まったかどうかを判断する際に、一般化エラーのプロキシとして使用されます。これらの方法は、ニューラル ネットワークを含む多くの反復機械学習アルゴリズムのトレーニングに採用されています。Prechelt は、ホールドアウト ベースの早期停止の単純な実装について、次のように要約しています。^[9]

1. トレーニング データをトレーニング セットと検証セットに (たとえば 2 対 1 の比率で) 分割します。
2. トレーニング セットのみでトレーニングし、たとえば 5 エポックごとに、検証セットで例ごとのエラーを時々評価します。
3. 検証セットのエラーが前回チェックしたときよりも高くなったらすぐにトレーニングを停止します。
4. トレーニング実行の結果として、前のステップでネットワークが持っていた重みを使用します。
   —  Lutz Prechelt、早期停止 – しかし、いつ？

クロスバリデーションは 、時系列以外のシナリオにも適用できる代替手段です。クロスバリデーションでは、データの複数のパーティションをトレーニング セットと検証セットに分割します。トレーニング セットと検証セットに 1 つのパーティションを分割するのではなく、この単純な手順でも、トレーニング中に検証エラーが変動し、複数の局所最小値が発生する可能性があるため、実際には複雑になります。この複雑さにより、オーバーフィッティングが実際に始まったかどうかを判断するためのアドホック ルールが多数作成されました。^[9]

• 過剰適合、早期停止は過剰適合を防ぐために使用される方法の1つです。
• 一般化エラー
• 正規化（数学）
• 統計学習理論
• ブースティング（機械学習）
• クロスバリデーション、特に「検証セット」の使用
• ニューラルネットワーク