Cómo llegar a la conclusión de que la dimensión VC para el hiperplano en $\mathbb{R^{3}}$ es estrictamente menor que $\mathbb{R^{4}}$ ?

Question

Dados cuatro puntos en $\mathbb{R^{3}}$ espacio real,

$S = \{(1, 1, 1), (1, 1, -1), (-1, -1, 1), (-1, -1, -1)\} \in \mathbb{R^{3}}$ .

¿Serán estos cuatro puntos destrozados por un hiperplano en $\mathbb{R^{3}}$ ?

Y cómo justificar esa dimensión VC para el hiperplano en $\mathbb{R^{3}}$ es estrictamente menor que $\mathbb{R^{4}}$ ?

Answer 1

En primer lugar, hay que tener en cuenta que tanto el desmenuzamiento como la dimensión VC se aplican a un conjunto de instancias y a un espacio de hipótesis, por ejemplo, el conjunto de todos los hiperplanos tridimensionales, y no a una sola hipótesis. A partir de las palabras de Mitchell Aprendizaje automático :

Un conjunto de instancias $S$ es destrozado por espacio de hipótesis $H$ si y sólo si para cada dicotomía de $S$ existe alguna hipótesis en $H$ consistente con esta dicotomía.

Para determinar si $H$ puede destrozar $S$ uno puede o bien..:

1. Demuestre que algún subconjunto de $S$ puede clasificar correctamente todas las posibles divisiones de instancias en $S$ .
2. Demuestra que no existe tal subconjunto.

En tu ejemplo, verás que ningún plano puede clasificar las esquinas opuestas como clases diferentes. (Para confirmarlo, intenta encontrar un plano que clasifique $(1,1,1)$ y $(-1,-1,-1)$ diferente de los otros puntos).

Esto no dice mucho sobre si $VC(H)=4$ . También de Mitchell:

El Dimensión Vapnik-Chervonenkis , $VC(H)$ del espacio de la hipótesis $H$ definido sobre el espacio de instancia $X$ es el tamaño del mayor subconjunto finito de $X$ destrozado por $H$ . Si los conjuntos finitos de $X$ puede ser destrozado por $H$ entonces $VC(H) \equiv \infty.$

Desde $VC(H)$ se refiere al mayor subconjunto de $X$ para demostrar que $VC(H)\ge 4$ sólo hay que demostrar que $|S| = 4$ para algunos $S \subseteq X$ que es destrozado por $H$ . Es decir, $H$ no tiene por qué romperse cada juego de cuatro puntos en $X$ , sólo algunos conjunto de cuatro puntos. Por ejemplo, en $\mathbb{R}^3$ planos puede destrozar los vértices de cualquier tetraedro -en realidad un conjunto cualquiera de cuatro puntos que no se encuentran en el mismo plano- de donde sabemos que $VC(H) \ge 4$ .

Para su segunda pregunta, se puede demostrar que la dimensión VC de los hiperplanos en $\mathbb{R}^d$ es $d+1$ . (Véase el esquema de la prueba aquí .) De ello se desprende que $VC(H)$ para los hiperplanos en $\mathbb{R}^d$ y $\mathbb{R}^{d+1}$ son $d+1, d+2$ respectivamente.

Answer 2

Puedes destrozar S en $\mathbb{R}^3$ . Para los hiperplanos en $\mathbb{R}^d$ la dimensión VC es $d+1$ . Por ejemplo, puede consultar este , p. 5/14.