Confundido sobre el supuesto de realizabilidad y las ecuaciones de límite superior

Question

Estoy leyendo el primer capítulo de Comprender el aprendizaje automático desde la teoría hasta los algoritmos y dijeron que:

Dejemos que $H_B$ sea el conjunto de hipótesis "malas", es decir

$H_B=\left\{h \in H:L_{(D,f)(h)}\gt e\right\}$ ( $e$ es el parámetro de precisión)

Dejemos que

$M=\left\{S|_x : \exists \ h \in H_B, L_s(h) =0 \right\}$

sea el conjunto de muestras engañosas: Es decir, para cada $S|_x \in M$ Hay una hipótesis "mala", $h \in H_B$ , que parece una "buena" hipótesis sobre $S|_x$ . Ahora, recordemos que queremos acotar la probabilidad del evento $L_{(D,f)} \gt e$ . Pero, como la hipótesis de realizabilidad implica que $L_s(h_s)=0$ se deduce que el evento $L_{(D,f)}(h_s)\gt e$ sólo puede ocurrir si para algunos $h \in H_B$ tenemos $L_s(h) = 0$ . En otras palabras, este evento sólo se producirá si nuestra muestra está en el conjunto de muestras engañosas $M$ . Formalmente, hemos demostrado que

$\left\{S|_x : L_{(D,f)}(h_S)\gt e \subseteq M\right\}$

Estoy muy confundido con esta conclusión. ¿Puede alguien explicarme esto? Gracias por su tiempo.

Answer 1

Formulemos el problema de forma más clara.

SUPUESTOS :

• $h_s = \underset{h\in\mathcal{H}}{\arg\min} \, L_{S}(h) \qquad$ (definición de ERM)
• $\exists h^{*} \in \mathcal{H}: L_{(\mathcal{D}, f)}(h^{*}) = 0 \qquad$ (hipótesis de realización)
• $\mathcal{H}_B = \{ h \in \mathcal{H}: L_{(\mathcal{D}, f)}(h) > \epsilon \}$
• $M = \{ S\vert_x: \exists h\in \mathcal{H}_{B}, \, L_{S}(h) = 0 \}$

PRUEBA : $\{S\vert_x: L_{(\mathcal{D}, f)}\left(h_{S} \right) > \epsilon \} \subseteq M$

PROOF : Para demostrar que un conjunto A es un subconjunto del conjunto B, o $A \subseteq B$ necesitamos demostrar que todo elemento del conjunto A está en el conjunto B. Aquí, dada la definición de $\mathcal{H}_{B}$ podemos reescribir el conjunto M como

$M = \{ S\vert_{x}: h \in \mathcal{H}, \, L_{(\mathcal{D}, f)}(h) > \epsilon, \, L_{S}(h) = 0 \}$ .

Así, para ser un elemento del conjunto $M$ debe satisfacer las 3 condiciones especificadas en el conjunto M.

Cada elemento del conjunto del lado derecho satisface ya dos condiciones:

• $h_{S} \in \mathcal{H}$
• $L_{(\mathcal{D}, f)}\left(h_{S} \right) > \epsilon$ .

Por lo tanto, demostrar $L_{S}(h_{S}) = 0$ completarían la prueba. Esto puede hacerse empleando la definición de ERM y el supuesto de realizabilidad.

De la hipótesis de realizabilidad combinada con el hecho de que $S$ es una muestra de $\mathcal{D}$ :

$L_{(\mathcal{D}, f)}(h^{*}) = 0 \implies L_{S}(h^{*}) = 0$ .

De la definición de ERM:

$L_{S}(h_S) \le L_{S}(h^{*}) = 0 \quad \implies L_{S}(h_S) = 0$ .

Answer 2

La verdad es que yo también me quedé atascado en esto durante un rato...

Recuerda cómo $h_S$ se define: $$h_S \in \underset{h\in H}{\mathrm{argmin}} (L_S(h))$$ La suposición de realizabilidad te dirá que hay un perfecto $h^*$ . (Suposición muy fuerte). Este $h^*$ tendrá $L_S(h^*)=0$ por definición.

Así que cuando $h_S$ se define como el argmin - es necesariamente 0 con probabilidad 1. (Esto no es lo mismo que la función de Pérdida logrando 0 en cada muestra).

1. Así que estamos buscando una clase de predictores $h_S$
2. La hipótesis de realizabilidad nos dice que $L_S(h^*)=0$
3. si $\exists h \in H_B$ s.t. $L_S(h)=0$ Esto implica que $h \in argmin$

El resto se deduce que el conjunto que queremos definir está contenido en $M$ . No creo que esto no sea una prueba constructiva - no te dice cómo encontrar un $h$ En última instancia, muestra que hay un límite superior en el tamaño de las muestras que crearía las condiciones para crear un mal predictor. En realidad no hablan de la mensurabilidad pero había una nota a pie de página que suprimía esos detalles y $H$ ¡era finito, así que asumo que todo funciona!