実数値関数の擬似次元

Question

実数値関数の集合F = {f：X-> R}、Fの擬似次元を計算するには？

例を提供することは、私の理解に役立つでしょう。

：ケース X = { < X < 、0 < Y < B、0 < Z < C（X、Y、Z）}のような

*疑似次元はVC次元の一般化

Answer 1

このような寸法は、概念クラスの自由度の数を取得することを目的としています。このクラスの自由度は、あなたの質問にFと表示されます。直観的には、VCの次元と疑似次元は、多くの場合、自由度の数として推測できる数値に非常に近い数値になります。

たとえば、プレーン内の四角形のセットは、最大4つのポイントのセットを分解できるので、VCディメンション4です。 （+記号の終点に配置されている4点を選択し、適切な矩形を選択することで4点に任意の+/-符号を割り当てることができます）。特定の角の（x、y）を（幅、高さ）とともに指定することができるので、長方形を指定することができます。

擬似次元の場合、基本的にインジケータ集合{（x、y）：f（x）> y}をとり、その新しい集合のVC次元を取る。

たとえば、ある実数kに対してF = {f（x）：f（x）= kx}とします。そして、指標セットは各kについて{（x、y）：kx> y}となる。つまり、垂直線x = 0を除いて、原点を通る下半分の平面をすべて取得します。この集合はVC次元1しか持たないが、Fの唯一の自由度がkを選択することになるので理にかなっている。

ところで、この質問は、metaoptimize.comでも尋ねることができます。

Answer 2

ちょうどあなたが簡単たとえば、自由と無限のVC次元の1度を持つ関数の家族の例を作成することができ、VCの寸法にあまりにも混乱していない：

F = {1_ {罪を（斧）> 0、a \ in Reals}

これは1つの自由度しか持たないが、n個の要素ごとにこの要素群で分解できるn個の要素があることは容易にわかるので、VC次元は無限です。無限の量の自由パラメータを有するが、有限のVC次元を有するファミリの例もある。無限次元空間上の超平面w * x + bと同様ですが、wのノルムは有界です。