machine-learning - 円のVC次元、特殊なケース

Question

円は2D空間で3点を粉砕する可能性があることを読みました。これは、実際には円のVC次元です。

3つのポイント（5,2）（5,4）と（5,6）があるとしましょう。（5,2）と（5,6）が（5,4）なしで含まれている円を描くにはどうすればよいですか？それは可能ではありません！
粉砕できない場合は、どうして円のVC次元が3になるのでしょうか。または、VC次元の定義でそれを仮定するのは間違っていますか。仮説は、空間のすべての可能なサブセットのすべての可能なシナリオを粉砕する必要がありますか？

Answer 1

VC次元は、粉砕できるポイントの最大数です。{（5,2）、（5,4）、（5,6）}は円で粉砕できませんが、{（5,2）、（5,4）、（6,6）}は円で粉砕できますしたがって、VC次元は少なくとも3です。正確に3であることを証明するのは困難です。

ここには、Qnanの回答に関連する技術的なポイントがあります。円分類器が常に円の内側の点を1として分類し、円の外側の点を0として分類する場合、{（5,2）、（5,4）、（5,6）}を粉砕することはできません。一方、円分類器が円内の点も0として分類できる場合は、Qnanの説明に従って、{（5,2）、（5,4）、（5,6）}を粉砕できます。

Qnan、あなたのコメントに関して、nがプロパティPを持つポイントの最大数であると言う場合、n> = mであることを証明するには、プロパティPを持つmポイントのコレクションを見つけるだけで十分です。プロパティPを持たない1000セットのmポイントは、nについて何も証明しません。（サイズmの可能なすべてのポイントのセットを列挙していない限り。）

VC次元は、粉砕できるポイントの最大数です。分類器のVC次元が100の場合でも、分類器によって粉砕できない3つの点を見つけることができる可能性があります。サイズn以下のすべてのセットを粉砕できるように、VCB次元を最大数nと定義できます。Asymptoteの元の例は、デカルト平面上の円形分類子のVCB次元（円の内側に1、円の外側に0を想定）が2以下であることを示しています。これは、これらの3つの点を粉砕できないためです。ただし、Asymptoteの例では、粉砕できるサイズ3のポイントのセットが他にもあるため、VC次元が3未満であることは示されていません。

Answer 2

ポイントは、1つのクラスに属するすべてのポイントが内側にあり、残りが外側にあるように円を描くことができるということです。ラベルを交換するために必要なのは分類子を反転するだけなので、どのクラスがどれであるかは関係ありません。

あなたの場合、（5,2）と（5,6）を（5,4）から分離することは、後者だけを円に含めることによって簡単に行われます。分類器の場合、「内部」と「外部」は関係ありません。重要なのは、それらが0エラーで分類できることです。

編集 厳密に言えば、VC次元はパラメーター化された分類子に対して定義され、複数の分類子があり、その境界は「円」として記述されます。たとえば、f(x)=(x-x0)*(x-x0)1つの線上の3つの点のセットを粉砕することはできませんが、粉砕することはf(x)=a*(x-x0)*(x-x0)できます。両方の分類器には円形の境界があります。2番目のVC次元は実際には3ですが、最初のVC次元は2です。