安定性（学習理論）

安定性（アルゴリズム安定性とも呼ばれる）は、計算学習理論における、入力への小さな変動によって機械学習アルゴリズムの出力がどのように変化するかという概念です。安定した学習アルゴリズムとは、トレーニング データがわずかに変更されても予測があまり変化しないアルゴリズムです。たとえば、手書きのアルファベットの文字を認識するようにトレーニングされている機械学習アルゴリズムを考えてみましょう。トレーニング セットとして、手書きの文字とそのラベル (「A」から「Z」) の 1000 個の例を使用します。このトレーニング セットを変更する 1 つの方法は、例を 1 つ除外して、手書きの文字とそのラベルの 999 個の例のみを使用することです。安定した学習アルゴリズムは、1000 要素と 999 要素の両方のトレーニング セットで 同様の分類子を生成します。

安定性は、学習される情報の種類ではなく学習プロセスの特性であるため、言語学習から物理学や工学の逆問題まで、多くの種類の学習問題について研究することができます。安定性の研究は、一般化との関連があることが示された2000年代に、計算学習理論において重要性を増しました。^{[1]大規模な学習アルゴリズム、特に}経験的リスク最小化アルゴリズムでは、特定の種類の安定性が良好な一般化を保証することが示されました。

機械学習システムを設計する際の中心的な目標は、学習アルゴリズムが一般化すること、つまり有限の数の例でトレーニングした後で新しい例に対して正確に実行することを保証することです。 1990 年代には、教師あり学習アルゴリズムの一般化境界を得ることにおいて画期的な出来事が達成されました。一般化を証明するために歴史的に使用されてきた手法は、経験的量の平均値への一様収束特性を使用して、アルゴリズムが一貫していることを示すことでした。この手法は、大規模な経験的リスク最小化(ERM) アルゴリズムの一般化境界を得るために使用されました。ERM アルゴリズムは、トレーニング セットでの経験的誤差を最小化するように仮説空間からソリューションを選択するアルゴリズムです。 ${\displaystyle H}$${\displaystyle S}$

ERM バイナリ分類アルゴリズムについてVladimir Vapnikによって証明された一般的な結果は、任意のターゲット関数と入力分布、 VC 次元を持つ任意の仮説空間、およびトレーニング例に対して、アルゴリズムは一貫しており、真のエラーから最大で(プラス対数係数) のトレーニング エラーを生成するということです。この結果は後に、一意の最小化子を持たない関数クラスを持つほぼ ERM アルゴリズムに拡張されました。 ${\displaystyle H}$ ${\displaystyle d}$${\displaystyle n}$${\displaystyle O\left({\sqrt {\frac {d}{n}}}\right)}$

Vapnik の研究は、後にVC 理論として知られるようになった理論を用いて、学習アルゴリズムの一般化と学習される関数の仮説空間の特性との関係を確立しました。しかし、これらの結果は、無制限の VC 次元の仮説空間を持つアルゴリズムには適用できませんでした。言い換えれば、学習される情報の複雑さが測定できないほど大きい場合、これらの結果は適用できませんでした。最も単純な機械学習アルゴリズムのいくつか (たとえば回帰) は、無制限の VC 次元の仮説空間を持っています。別の例としては、任意の長さの文を生成できる言語学習アルゴリズムがあります。 ${\displaystyle H}$

安定性分析は、2000年代に計算学習理論のために開発され、一般化境界を取得するための代替方法です。アルゴリズムの安定性は、仮説空間の直接的な特性ではなく、学習プロセスの特性であり、最近傍法などの無制限または未定義の VC 次元を持つ仮説空間を持つアルゴリズムで評価できます。安定した学習アルゴリズムとは、トレーニング セットがわずかに変更されても、たとえば例を除外しても、学習した関数があまり変化しないアルゴリズムです。Leave one out エラーの尺度は、Cross Validation Leave One Out (CVloo) アルゴリズムで使用され、損失関数に関する学習アルゴリズムの安定性を評価します。したがって、安定性分析は、機械学習への 感度分析の応用です。${\displaystyle H}$

• 1900 年代初頭- 学習理論における安定性は、学習マップの連続性という観点から最初に説明され、アンドレイ・ニコラエヴィッチ・ティホノフ^[要出典]に遡ります。${\displaystyle L}$
• 1979年- デヴロイとワグナーは、アルゴリズムの「一つを除外する」動作が、サンプル内の小さな変化に対する感度に関連していることを観察しました。^[2]
• 1999年- カーンズとロンは有限VC次元と安定性の関係を発見した。^[3]
• 2002年- 画期的な論文で、ブスケとエリセエフは学習アルゴリズムの均一仮説安定性の概念を提唱し、それが一般化誤差が低いことを意味することを示しました。しかし、均一仮説安定性は強力な条件であり、仮説空間が2つの関数のみであるERMアルゴリズムを含む、多くのアルゴリズムには適用されません。^[4]
• 2002年- クティンとニヨギは、ブスケとエリセエフの結果を拡張し、彼らがほぼどこでも安定性と呼ぶいくつかのより弱い安定性の一般化境界を提供しました。さらに、彼らはおそらくほぼ正しい（PAC）設定でのERMアルゴリズムの安定性と一貫性の関係を確立するための最初の一歩を踏み出しました。^[5]
• 2004年- Poggioらは、安定性とERM一貫性の一般的な関係を証明した。彼らは、CVEEEloo安定性と呼ぶ、leave-one-out安定性の統計形式を提案し、それがa)制限された損失クラスでの一般化に十分であり、b)二乗損失、絶対値、バイナリ分類損失などの特定の損失関数に対するERMアルゴリズムの一貫性（したがって一般化）に必要かつ十分であることを示した。^[6]
• 2010年- Shalev Shwartzらは、仮説空間と損失クラスの複雑な関係により、Vapnikの元の結果に問題があることに気付きました。彼らは、異なる損失クラスと、教師あり学習と教師なし学習の異なるタイプの学習を捉える安定性の概念について議論しました。^[7]
• 2016年- モーリッツ・ハートらは、仮説に関する特定の仮定と、各インスタンスがモデルの更新に使用される回数を前提として、勾配降下法の安定性を証明した。^[8]

学習アルゴリズムのトレーニング セットに関連するいくつかの用語を定義します。これにより、安定性を複数の方法で定義し、この分野の定理を提示できるようになります。

機械学習アルゴリズムは学習マップとも呼ばれ、ラベル付けされた例の集合であるトレーニングデータセットをからまでの関数にマッピングします。ここで、と はトレーニング例と同じ空間内にあります。関数はと呼ばれる関数の仮説空間から選択されます。 ${\displaystyle L}$${\displaystyle (x,y)}$${\displaystyle f}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle f}$${\displaystyle H}$

アルゴリズムが学習するトレーニングセットは次のように定義されます。

${\displaystyle S=\{z_{1}=(x_{1},\ y_{1})\ ,..,\ z_{m}=(x_{m},\ y_{m})\}}$

そして大きさは${\displaystyle m}$${\displaystyle Z=X\times Y}$

未知の分布Dからiidを抽出しました。

したがって、学習マップはから へのマッピングとして定義され、トレーニング セットをからへの関数にマッピングします。ここでは、 がに関して対称である、つまりトレーニング セット内の要素の順序に依存しない決定論的アルゴリズムのみを検討します。さらに、すべての関数は測定可能であり、すべてのセットは可算であると仮定します。 ${\displaystyle L}$${\displaystyle Z_{m}}$${\displaystyle H}$${\displaystyle S}$${\displaystyle f_{S}}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle L}$${\displaystyle S}$

例に関する仮説の損失は次のように定義されます。 ${\displaystyle V}$${\displaystyle f}$${\displaystyle z=(x,y)}$${\displaystyle V(f,z)=V(f(x),y)}$

の経験的誤差はです。 ${\displaystyle f}$${\displaystyle I_{S}[f]={\frac {1}{n}}\sum V(f,z_{i})}$

の本当の誤りは${\displaystyle f}$${\displaystyle I[f]=\mathbb {E} _{z}V(f,z)}$

サイズmのトレーニングセットSが与えられた場合、すべてのi = 1....,mに対して、次のように変更されたトレーニングセットを構築します。

• i番目の要素を削除することで

${\displaystyle S^{|i}=\{z_{1},...,\ z_{i-1},\ z_{i+1},...,\ z_{m}\}}$

• i番目の要素を置き換えることによって

${\displaystyle S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i}',\ z_{i+1},...,\ z_{ m}\}}$

次の条件が成り立つ場合、アルゴリズムは損失関数 V に関して仮説安定性 β を持ちます。 ${\displaystyle L}$

${\displaystyle \forall i\in \{1,...,m\},\mathbb {E} _{S,z}[|V(f_{S},z)-V(f_{S^{|i}},z)|]\leq \beta .}$

次の条件が成り立つ場合、アルゴリズムは損失関数 V に関して点ごとの仮説安定性 β を持ちます。 ${\displaystyle L}$

${\displaystyle \forall i\in \\{1,...,m\},\mathbb {E} _{S}[|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|]\leq \beta .}$

次の条件が成り立つ場合、アルゴリズムは損失関数 V に関して誤差安定性 β を持ちます。 ${\displaystyle L}$

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},|\mathbb {E} _{z}[V(f_{S},z)]-\mathbb {E} _{z}[V(f_{S^{|i}},z)]|\leq \beta }$

次の条件が成り立つ場合、アルゴリズムは損失関数 V に関して均一な安定性 β を持ちます。 ${\displaystyle L}$

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta }$

均一安定性 β の確率バージョンは次のようになります。

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},\mathbb {P} _{S}\{\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta \}\geq 1-\delta }$

の値がに応じて減少する場合、アルゴリズムは安定していると言われます。 ${\displaystyle \beta}$${\displaystyle O({\frac {1}{m}})}$

次の条件が成り立つ場合、アルゴリズムは損失関数 V に関して CVloo 安定性 β を持ちます。 ${\displaystyle L}$

${\displaystyle \forall i\in \{1,...,m\},\mathbb {P} _{S}\{|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|\leq \beta _{CV}\}\geq 1-\delta _{CV}}$

(CVloo) 安定性の定義は、前に見た点ごとの仮説安定性と 同等です。

アルゴリズムが安定性を持つのは、各 n に対して次の条件を満たす aと a が存在する場合です。 ${\displaystyle L}$${\displaystyle Eloo_{err}}$${\displaystyle \beta _{EL}^{m}}$${\displaystyle \delta _{EL}^{m}}$

${\displaystyle \forall i\in \{1,...,m\},\mathbb {P} _{S}\{|I[f_{S}]-{\frac {1}{m}}\sum _{i=1}^{m}V(f_{S^{|i}},z_{i})|\leq \beta _{EL}^{m}\}\geq 1-\delta _{EL}^{m}}$、およびゼロになると${\displaystyle \beta _{EL}^{m}}$${\displaystyle \delta _{EL}^{m}}$${\displaystyle m,\rightarrow \infty }$

BousquetとElisseeff（02）より：

制限された損失を持つ対称学習アルゴリズムの場合、アルゴリズムが上記の確率的定義で均一安定性を持つ場合、アルゴリズムは一般化されます。

均一安定性は、すべてのアルゴリズムが満たすわけではない強力な条件ですが、驚くべきことに、大規模で重要な正規化アルゴリズムのクラスでは満たされています。一般化の境界は、この記事で示されています。

Mukherjee et al. (06)より：

• 制限された損失を持つ対称学習アルゴリズムの場合、アルゴリズムが上記で定義したLeave-one-out 相互検証 (CVloo) 安定性と Expected-leave-one-out error ( ) 安定性の両方を備えている場合、アルゴリズムは一般化されます。${\displaystyle Eloo_{err}}$
• どちらかの条件だけでは一般化には不十分です。ただし、両方を組み合わせることで一般化が保証されます (逆は真ではありません)。
• 特に ERM アルゴリズムの場合 (たとえば、二乗損失の場合)、Leave-one-out クロス検証 (CVloo) の安定性は、一貫性と一般化のために必要かつ十分です。

これは学習理論の基礎にとって重要な結果です。なぜなら、アルゴリズムのこれまでは無関係だった 2 つの特性、安定性と一貫性が ERM (および特定の損失関数) では同等であることを示しているからです。一般化の境界は記事に記載されています。

これは、安定していることが示されているアルゴリズムのリストと、関連する一般化境界が提供されている記事です。

• 線形回帰^[9]
• {0-1}損失関数を持つk-NN分類器。^[2]
• 有界カーネルと再生カーネルヒルベルト空間のノルムである正則化子を持つサポートベクターマシン（SVM）分類。正則化定数が大きいほど安定性が高くなります。^[4]${\displaystyle C}$
• ソフトマージンSVM分類。^[4]
• 正規化最小二乗回帰^[4]
• 分類のための最小相対エントロピーアルゴリズム。^[4]
• バギング正則化子のバージョンで、回帰子の数はとともに増加する。^[10]${\displaystyle k}$${\displaystyle n}$
• 多クラスSVM分類^[10]
• ティホノフ正則化を用いたすべての学習アルゴリズムは均一安定性基準を満たしており、したがって一般化可能である。^[11]