Vapnik (Statistical Learning Theory) describe el caso "optimista más simple" de aprendizaje con minimización del riesgo empírico como el caso en el que al menos una de las funciones entre las que estamos seleccionando tiene una probabilidad de error de $0$ . Más formalmente:
Consideremos el problema de minimizar el funcional de riesgo: $$R(Q_i) = \int Q_i(z)dF(z)$$ dada una muestra empírica $z_1, z_2 ...z_l$ sobre el conjunto finito de funciones indicadoras $\{Q_i(\cdot)\}_{i=1}^N$ . En otras palabras, buscamos minimizar el riesgo empírico:
$$\hat{R}(Q_i) = \frac{1}{l}\sum_j^l Q_i(z_j)$$
Dado que al menos una de las funciones $Q_i$ tiene verdadero riesgo $R(Q_i) = 0$ entonces tenemos la siguiente cota para funciones con $0$ riesgo empírico:
$$\mathbb{P}\left(\sup_{1\leq k \leq N}\left | R(Q_k) - \hat{R}(Q_k) \right | I(\hat{R}(Q_k)=0) > \epsilon\right) \leq (N-1)(1-\epsilon)^l$$
aplicando un límite de unión y puesto que una función $Q_k$ con riesgo $R(Q_k) \geq \epsilon$ tiene un riesgo empírico de $0$ con una probabilidad máxima de $(1-\epsilon)^l$ .
Vapnik afirma que este límite es estricto y que la igualdad se consigue en el caso de que nuestro conjunto de $N$ contiene una única función con un riesgo de $0$ y el resto $N-1$ funciones forman sucesos estadísticamente independientes $A_k = \{z | Q_k(z) > 0\}$ y tienen el mismo valor de riesgo $R(Q_k) = \epsilon$ para todos $k$ .
Lo que he probado
La probabilidad en cuestión es igual a la probabilidad de que cualquiera de los $N-1$ funciones restantes tienen un riesgo empírico superior a $\epsilon$ . En lugar de un límite de unión podemos considerar el complemento del suceso: ninguno de los $N-1$ funciones restantes tienen un riesgo empírico mayor que $\epsilon$ . El riesgo empírico de cualquiera de estas $N-1$ funciones restantes es igual a $0$ con probabilidad $(1-\epsilon)^l$ . Como cada uno de estos sucesos es independiente, podemos tomar el producto: $$\mathbb{P}\left(\sup_{1\leq k \leq N}\left | R(Q_k) - \hat{R}(Q_k) \right | I(\hat{R}(Q_k)=0\right) = (1-\epsilon)^{l(N-1)}$$
pero esto no demuestra que el límite mostrado anteriormente sea estricto.
Debo haber cometido un error en alguna parte. Me vendría bien recibir comentarios sobre mi explicación y mi razonamiento.
