¿Cómo puedo demostrar que el riesgo empírico medio es igual al riesgo verdadero para un clasificador binario?

Question

Supongamos que

• $h \in \mathcal{H}$ es una hipótesis en alguna clase de clasificadores binarios $\mathcal{H}$ ,
• $\mathcal{D}_n$ es un conjunto de datos de entrenamiento de tamaño $n$ ,
• $\mathcal{L}$ es la función de pérdida para el problema de clasificación binaria definida como $$\mathcal{L}(x,h) = \begin{cases} 1, & s(x) \not= h(x) \\ 0, & \text{otherwise} \end{cases}$$ donde $s(x)$ es el sistema que intentamos modelar,
• $R_e(h)$ es el riesgo empírico de $h$ sobre un conjunto de datos determinado $\mathcal{D}_n$ definido como $$R_e(h) = \frac1n\sum_{i=1}^{n}\mathcal{L}(x_i, h(x_i))$$
• y $R(h)$ es el riesgo verdadero de la hipótesis $h$ .

¿Cómo puedo demostrar que $$\mathbb{E}_{\mathcal{D}_n}\left[R_e(h)\right] = R(h)$$ donde la expectativa en el LHS es sobre todos los posibles conjuntos de datos de entrenamiento $\mathcal{D}_n$ de tamaño $n$ .

Lo que he probado hasta ahora

Desde $$R_e(h) = \frac1n\sum_{i=1}^{n}\mathcal{L}(X_i, h(x_i))$$ entonces $$\begin{align} \mathbb{E}_{\mathcal{D}_n}\left[R_e(h)\right] &= \int_{\mathcal{D}_n}{R_e(h)p(\mathcal{D}_n)} \\ &= \frac{1}{n}\int_{\mathcal{D}_n}{\sum_{x_i \in \mathcal{D}_n}\mathcal{L}(x_i, h)p(\mathcal{D}_n)} \end{align}$$ Ahora quiero manipular esto para convertirlo en $$R(h) = \int_{x}{\mathcal{L}(x,h)p(x)dx}$$ Pensé en agrupar todos los $x_i$ de la ecuación anterior, pero no pude encontrar una manera de obtener el $p(x)$ y aquí es donde estoy atascado. Estoy buscando pistas progresivas que me ayuden a resolver esto por mí mismo.

Answer 1

Supongamos que el conjunto de datos es $\mathcal{D} = \{X_1, \dots, X_n\}$ donde cada punto de datos $X_i$ se extrae i.i.d. de alguna distribución $f_X$ . El verdadero riesgo es:

$$R(h) = E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

Demuestra que $E_{\mathcal{D}_n}[R_e(h)] = R(h)$

1. Empieza por el LHS:

$$E_{\mathcal{D}_n}[R_e(h)]$$

2. Introduzca la expresión del riesgo empírico $R_e(h)$ :

$$= E_{\mathcal{D}_n} \left [ \frac{1}{n} \sum_{i=1}^n \mathcal{L}(X_i, h(X_i)) \right ]$$

3. Por linealidad de la expectativa:

$$= \frac{1}{n} \sum_{i=1}^n E_{\mathcal{D}_n}[\mathcal{L}(X_i, h(X_i))]$$

4. Porque $\mathcal{L}(X_i, h(X_i))$ sólo depende de $X_i$ la expectativa conjunta (sobre los conjuntos de datos) es igual a la expectativa marginal (sobre el punto de datos $X_i$ ):

$$= \frac{1}{n} \sum_{i=1}^n E_{X_i}[\mathcal{L}(X_i, h(X_i))]$$

5. El valor esperado es el mismo para todos $X_i$ porque están idénticamente distribuidos. Por lo tanto, podemos sustituir $X_i$ con una variable genérica $X$ extraídas de la misma distribución $f_X$ :

$$= \frac{1}{n} \sum_{i=1}^n E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

6. Simplifica:

$$= E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

Esto es igual al riesgo real $R(h)$ .

---

Alternativa

He aquí una forma equivalente de proceder, empezando después del paso (3) anterior.

Escriba explícitamente el valor esperado sobre conjuntos de datos. Dado que los puntos de datos son independientes, la distribución conjunta del conjunto de datos es igual al producto de las distribuciones marginales de los puntos de datos.

$$= \frac{1}{n} \sum_{i=1}^n \int \cdots \int \left ( \prod_{j=1}^n f_X(x_j) \right ) \mathcal{L}(x_i, h(x_i)) \ dx_1 \cdots dx_n$$

Reordena las integrales (véase el teorema de Fubini) y extrae los términos que implican $x_i$ hacia el exterior:

$$= \frac{1}{n} \sum_{i=1}^n \int f_X(x_i) \mathcal{L}(x_i, h(x_i)) \left [ \int \cdots \int \left ( \prod_{j \ne i} f_X(x_j) \right ) \ dx_1 \cdots dx_{i-1} \ dx_{i+1} \cdots dx_n \right ] dx_i$$

La expresión dentro de los paréntesis es simplemente la integración de una distribución, por lo que es igual a uno:

$$= \frac{1}{n} \sum_{i=1}^n \int f_X(x_i) \mathcal{L}(x_i, h(x_i)) dx_i$$

La integral es el valor esperado de $\mathcal{L}(\cdots)$ con respecto a $f_X$ :

$$= \frac{1}{n} \sum_{i=1}^n E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

Esto es lo mismo que el resultado del paso (5) anterior, así que proceda con (6).

Answer 2

En realidad es una consecuencia inmediata del hecho de que $R_e(h)$ es un estimador de Monte Carlo para $R(h)$ ( para h fijo ). Esto es evidente si, en lugar de la terrible notación utilizada a menudo en algunos libros de introducción al Aprendizaje Automático, donde se consideran "conjuntos de datos", consideramos más propiamente un vector aleatorio $\mathbf{X}$ cuyo $n$ componentes son iid. El vector aleatorio tiene una distribución de probabilidad

$$p(\mathbf{X})=p(X_1,\dots,X_n)$$

Ahora, obviamente $R_e(h(X_1),\dots,h(X_n))=f(\mathbf{X})$ es una variable aleatoria y realmente queremos calcular su expectativa:

$$\mathbb{E}_{\mathbf{X}\sim p(\mathbf{X})}[R_e(h)]$$

Pero esto es inmediato si nos fijamos en que

$$f(\mathbf{X})=\frac{1}{n} \sum_{i=1}^n \mathcal{L}(X_i, h(X_i))=\frac{1}{n} \sum_{i=1}^n g(X_i)=\frac{1}{n} \sum_{i=1}^n Y_i$$

no es más que el estimador Monte Carlo de la media de $Y=g(X)$ una variable aleatoria cuya media no es más que el riesgo real. Prueba: todos $Y_i$ son iid y tenemos

$$\mathbb{E}[Y]=\mathbb{E}_{X\sim p(X)}[g(X)]=\mathbb{E}_{X\sim p(X)}[\mathcal{L}(X, h(X))]=R(h)$$

Ahora bien, el estimador de Monte Carlo tiene muchas propiedades interesantes , pero sólo necesitamos dos (en realidad una, pero gracias a la segunda también te mostraré una interesante propiedad del Riesgo Empírico, sobre la que no preguntaste):

1. es un imparcial estimador del riesgo verdadero, es decir, su media es igual a la media de $Y$ . De hecho,

$$\mathbb{E}_{\mathbf{X}\sim p(\mathbf{X})}[R_e(h(X_1),\dots,h(X_n))]=\mathbb{E}[Y]=R(h)$$

2. es un coherente estimador del riesgo real, es decir, el estimador de Monte Carlo converge a.s. a la media de $Y$ para el tamaño de la muestra $n\to\infty$ . En otras palabras

$$R_e(h)\overset{a.s.}\to R(h) \ \text{as} \ n\to\infty$$