学習可能な関数クラス

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

意味

背景

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

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

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

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

しかし実際には、分布は $P$ は未知であり、いかなる学習タスクも有限サンプルにしか基づかない。したがって、我々は経験的リスクを漸近的に最小化するアルゴリズム、すなわち関数のシーケンスを見つけることを目指す。 $\{{\hat {f}}_{n}\}_{n=1}^{\infty }$ 満たす

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

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

学習可能な関数クラス

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

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

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

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

解釈

もし真の関係が $y$ そして $x$ は $y\sim f^{*}(x)$ そして、適切な損失関数を選択することによって、 $f^{*}$ は常に、考えられるすべての関数の中で期待損失を最小化するものとして表現できます。つまり、

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

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

上記の分解では、 $(b)$ データに依存せず、非確率的です。これは、私たちの仮定からどれだけ離れているかを示します（ $\displaystyle {\mathcal {F}}}$ ）は真実から来ています（ $\displaystyle {\mathcal {F}}^{*}}$ ) $(b)$ 仮定が強すぎると、0 より厳密に大きくなります ( $\displaystyle {\mathcal {F}}}$ 小さすぎる）。一方、 $\displaystyle {\mathcal {F}}}$ 学習不可能になる原因となり、 $(a)$ 確率的に0に収束することはありません。これは、統計学や機械学習の分野でよく知られている過学習問題です。

例：チホノフ正則化

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

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

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

トレードオフ $(a)$ そして $(b)$ （２）は、RKHSにおけるティホノフ正則化により幾何学的に直感的である。 $\displaystyle \{{\mathcal {F}}_{\gamma }\}}$ 基本的にボールである ${\mathcal {F^{*}}}$ 中心が0にある。 $\gamma$ 大きくなる、 $\displaystyle {\mathcal {F}}_{\gamma }}$ 空間全体に近づき、 $(b)$ は小さくなる可能性が高い。しかし、収束速度も小さくなるだろう。 $(a)$ 最適な選択方法 $\gamma$ 有限サンプル設定では、通常は交差検証によって行われます。

経験過程理論との関係

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

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

ただし、^{[ 2 ]}では、学習可能性が一様収束と等価ではない一般学習設定に対する確率的凸最適化の例が著者らによって示されていることに注意してください。

参考文献

1 2 3ウラジミール・N・ヴァプニク（2013年4月17日）。統計的学習理論の本質。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-1-4757-2440-0。
1 2「学習可能性、安定性、均一収束」。機械学習研究ジャーナル。
↑「再生核を持つヒルベルト空間における学習可能性」。複雑性ジャーナル。
↑アンドレイ・ニコラエヴィチ・チホノフ。ヴァシリー・イ︠A︡コブレヴィチ・アルセニン（1977年）。不正設定問題の解決策。ウィンストン。ISBN 978-0-470-99124-4。
↑ AW van der vaart; Jon Wellner (2013年3月9日). Weak Convergence and Empirical Processes: With Applications to Statistics . Springer Science & Business Media. pp. 116–. ISBN 978-1-4757-2545-2。

[Vapnik2013-1] 1 2 3ウラジミール・N・ヴァプニク（2013年4月17日）。統計的学習理論の本質。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-1-4757-2440-0。

[:0-2] 1 2「学習可能性、安定性、均一収束」。機械学習研究ジャーナル。

[3] 「再生核を持つヒルベルト空間における学習可能性」。複雑性ジャーナル。

[TikhonovArsenin1977-4] アンドレイ・ニコラエヴィチ・チホノフ。ヴァシリー・イ︠A︡コブレヴィチ・アルセニン（1977年）。不正設定問題の解決策。ウィンストン。ISBN 978-0-470-99124-4。

[vaartWellner2013-5] AW van der vaart; Jon Wellner (2013年3月9日). Weak Convergence and Empirical Processes: With Applications to Statistics . Springer Science & Business Media. pp. 116–. ISBN 978-1-4757-2545-2。

[ 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

意味

背景

学習可能な関数クラス

解釈

例：チホノフ正則化

経験過程理論との関係

参考文献

関連するトピック

統計的学習理論

期待リスク

関数

集合のことである。学習可能なクラスの概念は、