学習可能な関数クラス

統計学習理論において、学習可能関数クラスとは、あらゆる確率分布において一様に期待リスクを漸近的に最小化するアルゴリズムを考案できる関数の集合である。学習可能クラスの概念は機械学習における正則化と密接に関連しており、特定の学習アルゴリズムに大規模サンプルの正当性を与える。

意味

背景

を標本空間とし、はラベル、は共変量（予測変数）とします。は にリンクすることが検討されているマッピング（関数）の集合です。は事前に与えられた損失関数（通常は非負）です。上の確率分布が与えられた場合、期待リスクを次のように定義します。 ${\displaystyle \Omega ={\mathcal {X}}\times {\mathcal {Y}}=\{(x,y)\}}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {F}}=\{f:{\mathcal {X}}\mapsto {\mathcal {Y}}\}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle L:{\mathcal {Y}}\times {\mathcal {Y}}\mapsto \mathbb {R} }$ ${\displaystyle P(x,y)}$ ${\displaystyle \Omega }$ ${\displaystyle I_{P}(f)}$

${\displaystyle I_{P}(f)=\int L(f(x),y)dP(x,y)}$

統計学習における一般的な目標は、期待リスクを最小化する関数を見つけることです。つまり、次の問題の解を見つけることです。^[1]${\displaystyle {\mathcal {F}}}$

${\displaystyle {\hat {f}}=\arg \min _{f\in {\mathcal {F}}}I_{P}(f)}$

しかし実際には分布は未知であり、学習タスクは有限のサンプルに基づいてしか実行できない。そこで我々は、経験的リスクを漸近的に最小化するアルゴリズム、すなわち、次式を満たす 関数列を求める。${\displaystyle P}$ ${\displaystyle \{{\hat {f}}_{n}\}_{n=1}^{\infty }}$

${\displaystyle \lim _{n\rightarrow \infty }\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}$

このようなシーケンスを見つけるための一般的なアルゴリズムの 1 つは、経験的リスク最小化です。

学習可能な関数クラス

収束がすべての確率分布に対して一様であることを条件とすることで、上記の式で与えられた条件をより強固なものにすることができます。つまり、

${\displaystyle \lim _{n\rightarrow \infty }\sup _{P}\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}$

1

より厳格な要件の背後にある直感的な根拠は次のとおりです。シーケンスが期待リスクの最小値に収束する速度は、さまざまな によって大きく異なる可能性があります。現実世界では真の分布は常に未知であるため、あらゆるケースにおいて良好なパフォーマンスを発揮するシーケンスを選択する必要があります。 ${\displaystyle \{{\hat {f}}_{n}\}}$ ${\displaystyle P(x,y)}$ ${\displaystyle P}$

しかし、「ノーフリーランチ定理」によれば、( 1 )を満たすようなシーケンスは、が複雑すぎる場合には存在しません。つまり、( 1 )を意味のある要件としたいのであれば、関数を「多く」許容しないように注意する必要があります。具体的には、( 1 )を満たすシーケンスの存在を保証する関数クラスは、学習可能クラスとして知られています。^[1]${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \{{\hat {f}}_{n}\}}$

注目すべきは、少なくとも教師あり分類問題と回帰問題においては、関数クラスが学習可能であれば、経験的リスク最小化は自動的に（1）を満たすということである。^{[2]このように、これらの設定では、（} 1 ）によって提起された問題が解けることが分かるだけでなく、その解を与えるアルゴリズムもすぐに得られる。

解釈

と の真の関係が である場合、適切な損失関数を選択することにより、 は常にすべての可能な関数における期待損失の最小値として表現できます。つまり、 ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y\sim f^{*}(x)}$ ${\displaystyle f^{*}}$

${\displaystyle f^{*}=\arg \min _{f\in {\mathcal {F}}^{*}}I_{P}(f)}$

ここで、を に写像するすべての可能な関数の集合とします。は実際のデータ生成メカニズムとして解釈できます。しかし、フリーランチ定理によれば、実際には有限サンプルでは 上の期待リスク最小化関数を探索することは期待できません。そのため、 のサブセット、、 について探索を行うことがよくあります。そうすることで、が の元ではない可能性があるというリスクが生じます。このトレードオフは数学的に次のように表現できます 。${\displaystyle {\mathcal {F}}^{*}}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {Y}}}$ ${\displaystyle f^{*}}$ ${\displaystyle {\mathcal {F}}^{*}}$ ${\displaystyle {\mathcal {F}}^{*}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle f^{*}}$ ${\displaystyle {\mathcal {F}}}$

${\displaystyle I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)=\underbrace {I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)} _{(a)}+\underbrace {\inf _{f\in {\mathcal {F}}}I_{P}(f)-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)} _{(b)}}$

2

上記の分解において、 はデータに依存せず、非確率的です。これは、仮定（）が真実（）からどれだけ離れているかを表します。仮定が強すぎる（小さすぎる）場合、 は0より確実に大きくなります。一方、 に十分な制約を課さないと、 は学習不可能になり、 は確率的に0に収束しません。これは、統計学や機械学習の文献でよく知られている過剰適合の問題です。 ${\displaystyle (b)}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}^{*}}$ ${\displaystyle (b)}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle (a)}$

例: ティホノフ正規化

学習可能なクラスが用いられる良い例として、再生核ヒルベルト空間（RKHS）におけるいわゆるティホノフ正則化が挙げられます。具体的には、 RKHSを とし、その内積によって与えられるのノルムを とします。 ^[3]では、任意の有限正の に対して が学習可能なクラスであることが示されています。この問題の 双対形式に対する経験的最小化アルゴリズムは、${\displaystyle {\mathcal {F^{*}}}}$ ${\displaystyle ||\cdot ||_{2}}$ ${\displaystyle {\mathcal {F^{*}}}}$ ${\displaystyle {\mathcal {F}}=\{f:||f||_{2}\leq \gamma \}}$ ${\displaystyle \gamma }$

${\displaystyle \arg \min _{f\in {\mathcal {F}}^{*}}\left\{\sum _{i=1}^{n}L(f(x_{i}),y_{i})+\lambda ||f||_{2}\right\}}$

これは、ティホノフ^[4]によって、不適切問題を解くために初めて導入されました。多くの統計学習アルゴリズムは、このような形で表現できます（例えば、よく知られているリッジ回帰）。

( 2 )におけるとの間のトレードオフは、RKHSにおけるティホノフ正則化を用いると幾何学的により直感的になります。 の列を考えることができます。これは基本的に 0 を中心とする 内の球体です。 が大きくなるにつれて、は空間全体に近づき、 は小さくなる可能性があります。しかし、 における収束率も低下します。有限サンプル設定において最適な を選択する方法は、通常、交差検証を用いることです。 ${\displaystyle (a)}$ ${\displaystyle (b)}$ ${\displaystyle \{{\mathcal {F}}_{\gamma }\}}$ ${\displaystyle {\mathcal {F^{*}}}}$ ${\displaystyle \gamma }$ ${\displaystyle {\mathcal {F}}_{\gamma }}$ ${\displaystyle (b)}$ ${\displaystyle (a)}$ ${\displaystyle \gamma }$

経験的プロセス理論との関係

（２ ）の部分は統計学の経験的過程理論と密接に関連しており、経験的リスクは経験的過程として知られている。^[5]この分野では、確率収束を満たす 関数クラスは${\displaystyle (a)}$ ${\displaystyle \{\sum _{i=1}^{n}L(y_{i},f(x_{i})),f\in {\mathcal {F}}\}}$ ${\displaystyle {\mathcal {F}}}$

${\displaystyle \sup _{P}\mathbb {E} \sup _{f\in {\mathcal {F}}}|\sum _{i=1}^{n}L(y_{i},f(x_{i}))-I_{P}(f)|=0}$

3

は一様グリヴェンコ・カンテリ類として知られています。特定の正則性条件下では、学習可能類と一様グリヴェンコ・カンテリ類は同値であることが示されています。^[1]統計学の文献では、との間の相互作用はバイアスと分散のトレードオフとしてよく知られています。 ${\displaystyle (a)}$ ${\displaystyle (b)}$

しかし、^[2]では著者らが学習の一般設定に対する確率的凸最適化の例を示しており、学習可能性は一様収束と同等ではないことに注意する必要がある。

参考文献

1. Vladimir N. Vapnik (2013年4月17日). 統計学習理論の本質. Springer Science & Business Media. ISBN 978-1-4757-2440-0。
2. 「学習可能性、安定性、一様収束」。機械学習研究ジャーナル。
3. 「再生核を持つヒルベルト空間における学習可能性」。複雑性ジャーナル。
4. アンドレイ・ニコラエヴィチ・ティホノフ;ヴァシリー・イ︠A︡コブレヴィチ・アルセニン（1977年）。不適切な問題の解決策。ウィンストン。ISBN 978-0-470-99124-4。
5. AW van der vaart; Jon Wellner (2013年3月9日). 弱収束と経験的プロセス：統計への応用. Springer Science & Business Media. pp. 116–. ISBN 978-1-4757-2545-2。