分布学習理論

分布学習理論、または確率分布の学習は、計算学習理論の枠組みです。これは、 1994 年にMichael Kearns、Yishay Mansour、Dana Ron、Ronitt Rubinfeld、Robert Schapire、Linda Sellieによって提案され^{[ 1 ]} 、 Leslie Valiantによって導入されたPAC フレームワークから着想を得ています。^{[ 2 ]}

このフレームワークでは、入力は特定の分布クラスに属する分布から抽出された複数のサンプルです。目標は、これらのサンプルに基づいて、サンプルが抽出された分布を高い確率で特定する効率的なアルゴリズムを見つけることです。このフレームワークはその汎用性から、機械学習、近似アルゴリズム、応用確率論、統計学など、さまざまな分野で活用されています。

この記事では、計算理論の観点から、このフレームワークにおける基本的な定義、ツール、および結果について説明します。

させて${\displaystyle \textstyle X}$関心のある分布のサポートとする。Kearns らの元の研究^{[ 1 ]}と同様に、${\displaystyle \textstyle X}$有限であるため、一般性を失うことなく、${\displaystyle \textstyle X=\{0,1\}^{n}}$どこ${\displaystyle \textstyle n}$は、任意の値を表現するために使用しなければならないビット数です。${\displaystyle \textstyle y\in X}$我々は確率分布に焦点を当てる${\displaystyle \textstyle X}$。

確率分布には2つの表現方法がある。${\displaystyle \textstyle D}$以上${\displaystyle \textstyle X}$。

• 確率分布関数（または評価器）評価器${\displaystyle \textstyle E_{D}}$のために${\displaystyle \textstyle D}$入力として任意のものを受け取る${\displaystyle \textstyle y\in X}$実数を出力する${\displaystyle \textstyle E_{D}[y]}$これは、${\displaystyle \textstyle y}$によると${\displaystyle \textstyle D}$つまり${\displaystyle \textstyle E_{D}[y]=\Pr[Y=y]}$もし${\displaystyle \textstyle Y\sim D}$。
• 発電機 発電機${\displaystyle \textstyle G_{D}}$のために${\displaystyle \textstyle D}$入力として真にランダムなビット列を受け取る${\displaystyle \textstyle y}$出力${\displaystyle \textstyle G_{D}[y]\in X}$分布によると${\displaystyle \textstyle D}$ジェネレータは、分布からのサンプリングをシミュレートするルーチンとして解釈できます。${\displaystyle \textstyle D}$公平なコイン投げのシーケンスが与えられた場合。

分布${\displaystyle \textstyle D}$生成器（または評価器）が存在し、多項式時間で計算できる場合、その生成器（または評価器）は多項式時間を持つと呼ばれる。

させて${\displaystyle \textstyle C_{X}}$X 上の分布のクラス、つまり${\displaystyle \textstyle C_{X}}$は、すべての${\displaystyle \textstyle D\in C_{X}}$サポートを持つ確率分布${\displaystyle \textstyle X}$.${\displaystyle \textstyle C_{X}}$次のように書くこともできます${\displaystyle \textstyle C}$簡略化のため。

学習可能性を評価するためには、近似分布がどの程度正確であるかを測定する方法が必要である。${\displaystyle \textstyle D'}$サンプリングされた分布に適合する${\displaystyle \textstyle D}$2つの分布間の乖離を測定する方法はいくつかあります。一般的な可能性としては、次の3つが挙げられます。

• カルバック・ライブラー情報量
• 確率尺度の全変動距離
• コルモゴロフ距離

全変動とコルモゴロフ距離は真の指標である一方、KLダイバージェンスはそうではない（対称性に欠ける）。これらの尺度は収束の強さによって順序付けられる。KLダイバージェンスが近いということは、全変動が近いことを意味し（ピンスカーの不等式による）、さらに全変動が近いということは、コルモゴロフ距離が近いことを意味する。したがって、KLダイバージェンスの下で証明された学習可能性の結果は、より弱い尺度の下でも自動的に成り立つが、その逆は成り立たない。

特定の用途では特定の対策がより適切である可能性があるため、${\displaystyle \textstyle d(D,D')}$分布間の選択された乖離を示す${\displaystyle \textstyle D}$そしてその分布${\displaystyle \textstyle D'}$。

分布を学習するために使用する基本的な入力は、その分布によって抽出されたサンプルの数です。計算上の観点からは、そのようなサンプルは一定時間内に与えられるという前提があります。つまり、オラクルにアクセスできるようなものです。${\displaystyle \textstyle GEN(D)}$分布からサンプルを返す${\displaystyle \textstyle D}$時間計算量の測定とは別に、特定の分布を学習するために使用しなければならないサンプル数を測定することが目的となる場合もある。${\displaystyle \textstyle D}$分布のクラスにおいて${\displaystyle \textstyle C}$この量は、学習アルゴリズムのサンプル複雑度と呼ばれます。

分布学習の問題をより明確にするために、^{[ 3 ]}で定義されている教師あり学習の問題を考えてみましょう。この統計的学習理論の枠組みでは、トレーニングセット${\displaystyle \textstyle S=\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$そして目標は、ターゲット関数を見つけることです。${\displaystyle \textstyle f:X\rightarrow Y}$これは、例えば二乗損失関数など、何らかの損失関数を最小化する。より厳密には${\displaystyle f=\arg \min _{g}\int V(y,g(x))d\rho (x,y)}$、 どこ${\displaystyle V(\cdot ,\cdot )}$損失関数は、例えば${\displaystyle V(y,z)=(yz)^{2}}$そして${\displaystyle \rho (x,y)}$トレーニングセットの要素がサンプリングされる確率分布。条件付き確率分布${\displaystyle \rho _{x}(y)}$が既知であれば、目的関数は閉形式となる。${\displaystyle f(x)=\int _{y}yd\rho _{x}(y)}$なので、セットは${\displaystyle S}$確率分布からのサンプルの集合${\displaystyle \rho (x,y)}$分布学習理論の目標は、${\displaystyle \rho }$与えられた${\displaystyle S}$これは、目的関数を見つけるために使用できます。${\displaystyle f}$。

学習可能性の定義

分布の一種${\displaystyle \textstyle C}$は、すべての に対して効率的に学習可能であるとみなされる。${\displaystyle \textstyle \epsilon >0}$そして${\displaystyle \textstyle 0<\delta \leq 1}$アクセス権を与えた${\displaystyle \textstyle GEN(D)}$未知の分布の場合${\displaystyle \textstyle D\in C}$多項式時間アルゴリズムが存在する${\displaystyle \textstyle A}$学習アルゴリズムと呼ばれる${\displaystyle \textstyle C}$分布の生成器または評価器を出力する${\displaystyle \textstyle D'}$そのため

${\displaystyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta }$

もし私たちがそれを知っているなら${\displaystyle \textstyle D'\in C}$それから${\displaystyle \textstyle A}$は適切な学習アルゴリズムと呼ばれ、そうでない場合は不適切な学習アルゴリズムと呼ばれます。

場合によっては、分布のクラスは${\displaystyle \textstyle C}$は、一連のパラメータで記述できる、よく知られた分布を持つクラスです。たとえば${\displaystyle \textstyle C}$すべてのガウス分布のクラスである可能性がある${\displaystyle \textstyle N(\mu ,\sigma ^{2})}$この場合、アルゴリズムは${\displaystyle \textstyle A}$パラメータを推定できるはずです${\displaystyle \textstyle \mu ,\sigma }$。 この場合${\displaystyle \textstyle A}$これはパラメータ学習アルゴリズムと呼ばれます。

単純な分布のパラメータ学習は、統計的推定と呼ばれる非常に研究が進んでいる分野であり、様々な種類の既知の単純な分布に対する様々な推定量に関する膨大な文献が存在することは明らかです。しかし、分布学習理論は、より複雑な記述を持つ分布のクラスを学習することを扱います。

Kearns らは、その先駆的な研究において、次のようなケースを扱っている。${\displaystyle \textstyle A}$これは有限多項式サイズの回路として記述され、彼らは特定のクラスの分布について以下を証明した。^{[ 1 ]}

• $または$この種の分布に対するゲート分布には、多項式サイズの評価器は存在しない。${\displaystyle \textstyle \#P\subseteq P/{\text{poly}}}$一方、このクラスはジェネレーターを使えば効率的に学習できる。
• パリティゲート分布このクラスは、ジェネレータと評価器の両方を使用して効率的に学習できます。
• ハミングボールの混合クラスは、ジェネレーターとエバリュエーターの両方を使用して効率的に学習できます。
• 確率的有限オートマトンこのクラスは、PAC学習フレームワークにおける不可能な仮定であるノイズパリティ仮定の下では、評価器を使用して効率的に学習することはできません。

分布のクラスに対する学習アルゴリズムを見つけるための非常に一般的な手法の1つ${\displaystyle \textstyle C}$まず小さなものを見つけること${\displaystyle \textstyle \epsilon -}$表紙${\displaystyle \textstyle C}$。

意味

セット${\displaystyle \textstyle C_{\epsilon }}$と呼ばれる${\displaystyle \textstyle \epsilon }$-表紙${\displaystyle \textstyle C}$すべての${\displaystyle \textstyle D\in C}$があります${\displaystyle \textstyle D'\in C_{\epsilon }}$そのため${\displaystyle \textstyle d(D,D')\leq \epsilon }$. アン${\displaystyle \textstyle \epsilon -}$カバーは、記述するパラメータに関して多項式サイズである場合に小さい。${\displaystyle \textstyle D}$。

効率的な手順があれば、${\displaystyle \textstyle \epsilon >0}$小さなものを見つける${\displaystyle \textstyle \epsilon -}$カバー${\displaystyle \textstyle C_{\epsilon }}$C の場合、残りのタスクは以下から選択することです${\displaystyle \textstyle C_{\epsilon }}$分布${\displaystyle \textstyle D'\in C_{\epsilon }}$それは分布に近い${\displaystyle \textstyle D\in C}$それは学ばなければならないことだ。

問題は、${\displaystyle \textstyle D',D''\in C_{\epsilon }}$どのように比較できるかは些細なことではない${\displaystyle \textstyle d(D,D')}$そして${\displaystyle \textstyle d(D,D'')}$どれが一番近いかを決めるために${\displaystyle \textstyle D}$、 なぜなら${\displaystyle \textstyle D}$不明です。したがって、${\displaystyle \textstyle D}$これらの比較を行うには、を使用する必要があります。当然ながら、比較結果には常にエラーの確率があります。したがって、このタスクは、ノイズのある比較を使用して要素の集合内の最小値を見つけるのと似ています。この目標を達成するための古典的なアルゴリズムは多数あります。最も優れた保証を達成する最新のアルゴリズムは、DaskalakisとKamath ^{[ 4 ]}によって提案されました。このアルゴリズムは、要素間の高速トーナメントを設定します。${\displaystyle \textstyle C_{\epsilon }}$勝者は${\displaystyle \textstyle D^{*}}$このトーナメントの要素は${\displaystyle \textstyle \epsilon -}$近い${\displaystyle \textstyle D}$（つまり）${\displaystyle \textstyle d(D^{*},D)\leq \epsilon }$少なくとも${\displaystyle \textstyle 1-\delta }$そのために彼らのアルゴリズムは${\displaystyle \textstyle O(\log N/\epsilon ^{2})}$サンプルから${\displaystyle \textstyle D}$そして走る${\displaystyle \textstyle O(N\log N/\epsilon ^{2})}$時間、${\displaystyle \textstyle N=|C_{\epsilon }|}$。

単純でよく知られた分布の学習はよく研究されている分野であり、使用できる推定器は多数存在します。より複雑な分布のクラスとして、単純分布に従う変数の和の分布があります。これらの学習手順は、和が無限和に近づくときに同じ対象を調べる傾向があるため、中心極限定理などの極限定理と密接な関係があります。最近、ポアソン二項分布の学習と独立整数確率変数の和の学習という2つの結果がここで説明されています。以下の結果はすべて、距離尺度として全変動距離を使用した場合に成り立ちます。

確率変数${\displaystyle \textstyle X\sim N(\mu _{1},\Sigma _{1})}$そして${\displaystyle \textstyle Y\sim N(\mu _{2},\Sigma _{2})}$確率変数を定義する${\displaystyle \textstyle Z}$これは、${\displaystyle \textstyle X}$確率で${\displaystyle \textstyle w_{1}}$そして同じ値${\displaystyle \textstyle Y}$確率で${\displaystyle \textstyle w_{2}=1-w_{1}}$ならば${\displaystyle \textstyle F_{1}}$密度は${\displaystyle \textstyle X}$そして${\displaystyle \textstyle F_{2}}$密度は${\displaystyle \textstyle Y}$密度${\displaystyle \textstyle Z}$は${\displaystyle \textstyle F=w_{1}F_{1}+w_{2}F_{2}}$。 この場合${\displaystyle \textstyle Z}$はガウス分布の混合に従うと言われています。ピアソン^{[ 8 ]}は、分析したいデータと同じデータから得られた確率分布を説明しようとした際に、ガウス分布の混合という概念を初めて導入しました。彼は多くの手計算を行った後、最終的にデータをガウス分布の混合に適合させました。この場合の学習課題は、混合のパラメータを決定することです。${\displaystyle \textstyle w_{1},w_{2},\mu _{1},\mu _{2},\Sigma _{1},\Sigma _{2}}$。

この問題を解決しようとした最初の試みはダスグプタによるものであった。^{[ 9 ]}この研究において、ダスグプタはガウス分布の2つの平均値が互いに十分に離れていると仮定している。これは、距離に下限が存在することを意味する。${\displaystyle \textstyle ||\mu _{1}-\mu _{2}||}$この仮定を用いることで、ダスグプタとその後の多くの科学者は混合のパラメータを学習することができた。学習手順は、ある指標を最小化してサンプルを2つの異なるクラスターにクラスタリングすることから始まる。ガウス分布の平均が互いに高い確率で離れているという仮定を用いると、最初のクラスターのサンプルは最初のガウス分布のサンプルに対応し、2番目のクラスターのサンプルは2番目のガウス分布のサンプルに対応する。これでサンプルが分割され、${\displaystyle \textstyle \mu _{i},\Sigma _{i}}$単純な統計的推定値から計算でき、${\displaystyle \textstyle w_{i}}$クラスターの大きさを比較することによって。

もし${\displaystyle \textstyle GM}$は、2 つのガウス分布のすべての混合の集合であり、上記の手順を使用すると、次のような定理を証明できます。

定理^{[ 9 ]}

させて${\displaystyle \textstyle D\in GM}$と${\displaystyle \textstyle ||\mu _{1}-\mu _{2}||\geq c{\sqrt {n\max(\lambda _{max}(\Sigma _{1}),\lambda _{max}(\Sigma _{2}))}}}$、 どこ${\displaystyle \textstyle c>1/2}$そして${\displaystyle \textstyle \lambda _{max}(A)}$最大の固有値${\displaystyle \textstyle A}$すると、与えられたアルゴリズムが存在する。${\displaystyle \textstyle \epsilon >0}$、${\displaystyle \textstyle 0<\delta \leq 1}$およびアクセス${\displaystyle \textstyle GEN(D)}$近似値を見つける${\displaystyle \textstyle w'_{i},\mu '_{i},\Sigma '_{i}}$パラメータの${\displaystyle \textstyle \Pr[||w_{i}-w'_{i}||\leq \epsilon ]\geq 1-\delta }$（それぞれ${\displaystyle \textstyle \mu _{i}}$そして${\displaystyle \textstyle \Sigma _{i}}$このアルゴリズムのサンプル複雑度は${\displaystyle \textstyle M=2^{O(\log ^{2}(1/(\epsilon \delta )))}}$そして実行時間は${\displaystyle \textstyle O(M^{2}d+Mdn)}$。

上記の結果は、以下のように一般化することもできます。${\displaystyle \textstyle k-}$ガウス分布の混合。^{[ 9 ]}

2つのガウス分布の混合の場合、それらの平均値間の距離を仮定しない学習結果が得られます。例えば、全変動距離を距離尺度として使用する以下の例などです。

定理^{[ 10 ]}

させて${\displaystyle \textstyle F\in GM}$すると、与えられたアルゴリズムがある${\displaystyle \textstyle \epsilon >0}$、${\displaystyle \textstyle 0<\delta \leq 1}$およびアクセス${\displaystyle \textstyle GEN(D)}$発見する${\displaystyle \textstyle w'_{i},\mu '_{i},\Sigma '_{i}}$もし${\displaystyle \textstyle F'=w'_{1}F'_{1}+w'_{2}F'_{2}}$、 どこ${\displaystyle \textstyle F'_{i}=N(\mu '_{i},\Sigma '_{i})}$それから${\displaystyle \textstyle \Pr[d(F,F')\leq \epsilon ]\geq 1-\delta }$このアルゴリズムのサンプル複雑度と実行時間は次のとおりです。${\displaystyle \textstyle {\text{poly}}(n,1/\epsilon ,1/\delta ,1/w_{1},1/w_{2},1/d(F_{1},F_{2}))}$。

間の距離${\displaystyle \textstyle F_{1}}$そして${\displaystyle \textstyle F_{2}}$アルゴリズムの結果の品質には影響せず、サンプルの複雑さと実行時間のみに影響します。^{[ 9 ] [ 10 ]}