Coherencia del proceso de aprendizaje

Question

Tengo dos preguntas relacionadas con el concepto de "consistencia del aprendizaje" para aquellos que estén familiarizados con la teoría del aprendizaje estadístico a la Vapnik.

Pregunta 1.
El proceso de aprendizaje se denomina consistente (para la clase de funciones $\mathcal{F}$ y la distribución de probabilidad $P$ ) si

$$ R_{emp}(f^*_l) \buildrel P \over \to \inf_{f \in \mathcal{F}} R(f),\;l \to \infty $$ y $$ R(f^*_l) \buildrel P \over \to \inf_{f \in \mathcal{F}} R(f),\;l \to \infty $$

Estas dos condiciones son independientes. En la página 83 de "Statistical Learning Theory" de Vapnik hay un ejemplo de un conjunto de clasificadores $\mathcal{F}$ de manera que la segunda convergencia tenga lugar pero la primera no. Estaba pensando en un ejemplo de un conjunto de clasificadores tal que la primera se produce la convergencia, pero el segundo uno no, y no se le ocurrió nada. ¿Alguien puede ayudarme?

Pregunta 2.
El proceso de aprendizaje se denomina consistente no trivial (o consistente estricto) (para la clase de funciones $\mathcal{F}$ y la distribución de probabilidad $P$ ) si para cualquier número real $c \in R$ tal que el conjunto $\Lambda(c) = \{ f | R(f) \geq c \}$ no es vacío que tenemos:

$$ \inf_{f_l \in \Lambda(c)}R_{emp}(f_l) = R_{emp}(f^*_l) \buildrel P \over \to \inf_{f \in \Lambda(c)} R(f),\;l \to \infty $$

P. 81 de "Statistical Learning Theory" de Vapnik proporciona una ilustración de por qué queremos considerar la consistencia estricta en lugar de la consistencia definida en la Pregunta 1, es decir, por qué queremos introducir $\Lambda(c)$ y considerar $\inf_{f \in \Lambda(c)}$ para cualquier $c$ . Todos los demás textos que consideran la consistencia estricta duplican esencialmente la ilustración de Vapnik cuando quieren explicar los fundamentos del concepto de consistencia estricta. Sin embargo, la ilustración de Vapnik no me satisface por dos razones: en primer lugar, está hecha en términos de funciones de pérdida $Q(z, \alpha)$ y no los clasificadores, y, en segundo lugar, la Fig. 3.2. del libro no tiene realmente sentido cuando consideramos la función de pérdida común para los problemas de clasificación, es decir, la función que es igual a 0 cuando la etiqueta de clase predicha es igual a la etiqueta de clase verdadera y a 1 en caso contrario.

Entonces, ¿es posible dar otra ilustración, más sensata, de la razón de ser del concepto de coherencia estricta? Esencialmente, necesitamos un ejemplo de un conjunto de clasificadores tal que estos clasificadores no sean consistentes (en términos de la definición de la Pregunta 1) y algún nuevo clasificador que funcione mejor que cualquiera de los clasificadores del conjunto, de modo que cuando añadimos este clasificador al conjunto acabemos con el caso de "consistencia trivial". ¿Alguna idea?

Answer 1

Para su pregunta 1, tengo un ejemplo, pero requiere la función de pérdida tome el valor $\infty$ . Estoy seguro de que podemos dar un ejemplo que sólo requiere una función de pérdida no limitada, pero eso sería un poco más trabajo para construir. Una pregunta abierta es si hay un ejemplo con una función de pérdida acotada.

Consideremos el escenario de la clasificación, donde la distribución de probabilidad $P$ está en un espacio $\mathcal{Z}=\mathcal{X}\times\{0,1\}$ . Denotaremos denotar un ejemplo por $z=(x,y)$ con $x\in\mathcal{X}$ y $y\in\{0,1\}$ . Sea $\mathcal{F}=\mathcal{X}^{\{0,1\}}$ sea el espacio de todas las clasificaciones sobre $\mathcal{X}$ . Definir la función de pérdida

$$ Q(z,f)=Q\left((x,y),f\right)=\begin{cases} 0 & \text{for }f(x)=y\\ \infty & \mbox{otherwise,} \end{cases} $$ para cualquier $f\in\mathcal{F}$ . En otras palabras, tanto si te equivocas en un ejemplo o todos ellos mal, su riesgo es $\infty$ .

Ahora, supongamos que $\mathcal{X}=\left\{ x_{1},x_{2},\ldots\right\} $ es un conjunto contablemente infinito, y que $P$ sea cualquier distribución de probabilidad para la cual $P(\{x_{i}\})>0$ para todos $i=1,2,\ldots$ . Además, supongamos que existe una función de clasificación determinista, es decir, que existe $c\in\mathcal{F}$ para lo cual $y_{i}=c(x_{i})$ para $i=1,2,...$ . Esto implica que $\inf_{f\in\mathcal{F}}R(f)=0$ .

Entonces, para cada $l$ , $R_{emp}(f_{l}^{*})=0$ pero $R(f_{l}^{*})=\infty$ (a menos que haya una elección extremadamente afortunada de $f_{l}^{*}$ entre todos esos $f\in\mathcal{F}$ que tienen $0$ error empírico). Así, $R_{emp}(f_{l}^{*})\to\inf_{f\in\mathcal{F}}R(f)$ , pero $R(f_{l}^{*})$ no converge a ese valor.

Para la pregunta 2, estoy de acuerdo en que su ejemplo no parece aplicarse al caso de la clasificación, y no veo una manera obvia de hacer tal ejemplo .