粉砕されたセット

無料辞書『ウィクショナリー』で「shattered set」を調べてください。

ある集合のクラスが別の集合を粉砕するとは、その集合の任意の要素を交差を使って「取り出す」ことができる場合を言います。粉砕された集合の概念は、VC 理論としても知られるVapnik-Chervonenkis 理論で重要な役割を果たします。粉砕と VC 理論は、経験的プロセスの研究だけでなく、統計的計算学習理論でも使用されます。

Aが集合で、C が集合のクラスであるとする。クラスC が 集合A を破壊するのは、 Aの各部分集合aに対して、 Cの要素c が存在し、

${\displaystyle a=c\cap A.}$

同様に、C とA の交差がAのべき集合に等しい場合、 C はA を粉砕します: P ( A ) = { c ∩ A | c ∈ C }。

文字 C は 、Vapnik–Chervonenkis クラス (VC クラス) のように、セットの「クラス」または「コレクション」を指すために使用します。経験的プロセスでは、有限のデータ ポイント セットの分解に関心があるため、 セットA は有限であると想定されることがよくあります。

平面（2次元空間）内のすべての円板のクラスは単位円上の4点のすべての集合を粉砕するわけではないが、平面内のすべての凸集合のクラスは単位円上のすべての有限の点の集合を粉砕することを示します。

A を単位円上の 4 つの点の集合とし、Cをすべての円のクラスとします。

C がA を粉砕する場所をテストするために、Aのすべての点のサブセットの周りに円を描いてみます。まず、孤立した各点のサブセットの周りに円を描きます。次に、点のペアのすべてのサブセットの周りに円を描いてみます。これは、隣接する点には実行可能ですが、円の反対側の点には不可能であることがわかります。反対側の点を含めようとすると、必然的にそのペアにない他の点が含まれます。したがって、反対の点のペアは、クラスCとの交差を使用してAから分離することができず、したがってCはA を粉砕しません。

以下に視覚化します:

• 
  個々のポイントはディスクで分離できます (4 つすべてを表示)。
• 
  隣接するポイントの各サブセットは、ディスク (4 つのうちの 1 つを表示) を使用して分離できます。
• 
  単位円の反対側にある点のサブセットは、ディスクで分離することはできません。

C内のどの円板によっても分離できない部分集合が存在するため、A はCによって分割されないと結論付けられます。そして、少し考えれば、このCによって分割される 4 点の集合は存在しないことを証明できます。

しかし、 C をすべての楕円ディスクのクラスとして再定義すると、上記のすべてのサブセットと、以前は問題だった点を分離できることがわかります。したがって、この特定の 4 つの点のセットは、楕円ディスクのクラスによって粉砕されます。以下に視覚化します。

• 
  Aの対角点は楕円によって分離可能になりました（2つのうちの1つを表示）
• 
  Aの3点の各部分集合は、楕円によって分離可能である（4つのうちの1つを示す）

少し考えれば、単位円上の任意の有限点の集合は、すべての凸集合のクラスによって打ち砕かれる可能性があると一般化できます(点をつなげて視覚化します)。

集合の集合Cの豊かさを定量化するために、シャッタリング係数(成長関数とも呼ばれる)の概念を使用します。集合の集合C は任意の空間 (多くの場合は標本空間) であり、 Cのn^番目のシャッタリング係数を次のように 定義します。${\displaystyle s\subset \Omega }$${\displaystyle \オメガ}$

${\displaystyle S_{C}(n)=\max _{\forall x_{1},x_{2},\dots ,x_{n}\in \Omega }\operatorname {card} \{\,\{\,x_{1},x_{2},\dots ,x_{n}\}\cap s,s\in C\}}$

ここで、は集合の濃度を表し、はn点の任意の集合です。 ${\displaystyle \operatorname {カード} }$${\displaystyle x_{1},x_{2},\dots ,x_{n}\in \Omega }$

${\displaystyle S_{C}(n)}$は、 n点 の集合Aと集合C内の集合の交差によって形成される、 任意の集合Aの部分集合の最大数です。

たとえば、集合A に3 つの点が含まれている場合、そのべき集合には要素が含まれます。 C がA を粉砕する場合、その粉砕係数 (3) は 8 になり、 S_C(2) は になります。ただし、 c 内の集合の 1 つがc内の交差によって取得できない場合、 S_C(3) は 7 になります。これらの集合のいずれも取得できない場合、 S_C(3) は 0 になります。さらに、たとえば S_C(2)=3 の場合、Aのすべての 2 点集合の集合には、 Cとの交差からは取得できない要素があります。このことから、 2点集合のより小さいべき集合で「欠けている」集合をすでに見つけているため、 S_C(3) も 8 未満になります (つまり、 C はA を粉砕しません)。${\displaystyle P(A)}$${\displaystyle 2^{3}=8}$${\displaystyle 2^{2}=4}$${\displaystyle P(A)}$

この例では、 のいくつかの特性を示します。 ${\displaystyle S_{C}(n)}$

1. ${\displaystyle S_{C}(n)\leq 2^{n}}$すべてのnに対して、なぜなら任意の に対してであるから。${\displaystyle \{s\cap A|s\in C\}\subseteq P(A)}$${\displaystyle A\subseteq \Omega }$
2. の場合、濃度nの集合が存在し、それがCによって破壊されることを意味します。${\displaystyle S_{C}(n)=2^{n}}$
3. 一部にとってならば、全員にとって。${\displaystyle S_{C}(N)<2^{N}}$${\displaystyle N>1}$${\displaystyle S_{C}(n)<2^{n}}$${\displaystyle n\geq N}$

3 番目の特性は、C が基数Nの任意の集合を破壊できない場合、より大きな基数のセットも破壊できないことを意味します。

AがCによって粉砕されない場合は、n が大きくなるにつれて、省略される可能性のあるセットが増えるため、粉砕係数 (n) が より小さくなるnの最小値があります。あるいは、 n が小さくなるにつれて、省略される可能性のあるセットが少なくなるため、 S_C(n) が のままであるnの最大値もあります。この極端な例は S_C(0) (空セットの粉砕係数) で、これは常に でなければなりません。これらのステートメントは、クラスCのVC 次元を次のように定義するのに役立ちます。 ${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$${\displaystyle 2^{0}=1}$

${\displaystyle VC(C)={\underset {n}{\min }}\{n:S_{C}(n)<2^{n}\}\,}$

あるいは、

${\displaystyle VC_{0}(C)={\underset {n}{\max }}\{n:S_{C}(n)=2^{n}\}.\,}$

に注意してください。VC 次元は通常、A を破る選択された点の最大濃度(つまり、となるn ) である VC_0 として定義されます。 ${\displaystyle VC(C)=VC_{0}(C)+1.}$${\displaystyle S_{C}(n)=2^{n}}$

あるいは、任意のnに対して、 Cによって破壊できる基数nの集合が存在する場合、すべてのnに対して、このクラスCの VC 次元は無限大になります。 ${\displaystyle S_{C}(n)=2^{n}}$

有限の VC 次元を持つクラスは、Vapnik–Chervonenkis クラスまたはVC クラスと呼ばれます。クラスCが一様 Glivenko–Cantelliとなるのは、それが VC クラスである場合のみです。

• ザウアー・シェラーの補題、集合族の濃度とその最大の破砕集合の大きさを関連付ける

• ウェンクール、RS; ダドリー、RM (1981)、「いくつかの特別なヴァプニク-チェルヴォネンキスクラス」、離散数学、33 (3): 313–318、doi : 10.1016/0012-365X(81)90274-0。
• Steele, JM (1975)、「組合せエントロピーと均一極限法則」、博士論文、スタンフォード大学、数学科
• Steele, JM (1978)、「経験的矛盾と部分加法過程」、Annals of Probability、6 (1): 118–227、doi : 10.1214/aop/1176995615、JSTOR  2242865。

• 「Shattered Sets」という用語の起源、J. Steele 著