關於VC尺寸的問題

如果我有輸入空間（1,2，... 999）。我有一個概念類C，有10個概念：C0，C1，C2 ... C9。關於VC尺寸的問題

給定一個輸入，那個輸入是ci的一個元素，如果它包含數字i的話。例如，數字123是c1和c2和c3的一個元素。

這個概念類C的VC Dimension是什麼？

2009-10-11 Saobi

聽起來像是作業...... – 2009-10-12 00:52:32

我不想在這裏發表的整體解決方案，但這裏的東西...

尋找VC維涉及到輸入空間，可通過C.

是shattered找到點集我可以很容易地找到一組可以被C破壞的三個點（14,24,3）。

很難找到一組可以被C破壞的四個點，但是（157,256,367,4）起作用。

找到可以被C破壞的五個點非常非常困難，這強烈地表明C（給定輸入空間）的VC維度爲4.但是，棘手的部分是證明不可能找到任意一組可以破碎的五點。

實際上，問題可能存在一些含糊之處。這取決於概念類能夠「正確分類」一組點的意義。即C1是否正確地分類（1，2）其中1被賦予一個負面的類別標籤，2被賦予正面的一個（因爲它正確地分割它），或者只有C2可以做到這一點？我認爲它可以，因爲這個問題稍微有趣一些。

2009-10-21 14:47:56 Stompchicken

你能解釋爲什麼'（157,256,367,4）'有效嗎？我看到了四個不同的概念 - 這將使得難以用直線對所有這些概念進行分類？（除非他們是按照數字排列的......他們是嗎？）請你澄清一下 – CodyBugstein 2014-03-17 11:42:58

這個答案是否正確？

破碎意味着對於您選擇的一組數據點，例如。（14,24,3），對於它的每一個可能的標籤，都存在與該標籤一致的概念。給出，這裏

但考慮例子（14,24,3）是所有可能的真/假labellings的列表這三個點，哪些類是與他們一致：

0 0 0 C_5， C_6，C_7，C_8，C_9，C_0僅此

0 0 1 C_3都一致（因爲第三數量是三個，只有類C_3包含它）

0 1 0 C_2和C_4（因爲「 24「包含2和4）

0 1 1 C_2，C_4和C_3

1 0 0 C_1及C_4

1 0 1沒有一致的類別（因爲「14」和「3」不共享任何位數）

1 1 0 C_4（因爲「14」和「24」都包含4）

111沒有一致的類

因此類集合不打破這個數據集。（或者我誤解了定義中的某些東西？）

2012-08-17 17:30:45

回答