introduccion.org

PAC learning

Estos apuntes son una adptación en su mayoría del contenido del libro cite:shwartz_understanding_ml

Introducción

Damos unas notaciones/definiciones básicas que utilizaremos de aquí en adelante.

• Dominio: $\mathcal{X}$, sobre el que tenemos definida una $σ$ álgebra de conjuntos $\mathscr{B}$. Llamamos una instancia a $x∈ \mathcal{X}$
• Conjunto de etiquetas: $\mathcal{Y} \subseteq \mathbb{R}$ finito , que asumiremos como $\{0,1\}$ en lo que sigue hasta que se indique lo contrario. Esto nos restringe al paradigma de clasificación binario.
• Verdadero etiquetado: Asumimos la existencia de una función $f: \mathcal{X} → \mathcal{Y}$ que devuelve el verdadero etiquetado de todas las instancias.
• Generación de instancias: Asumimos la existencia de una distribución de probabilidad $\mathcal{D}$ sobre $\mathcal{X}$, para la $σ$ álgebra de conjuntos mencionada anteriormente, que nos da información sobre la probabilidad de extraer cada posible instancia desde $\mathcal{X}$.
• Conjunto de entrenamiento: Tenemos una muestra aleatoria simple $S = (\mathcal{X}_1, \ldots ,\mathcal{X}_m)$, idéntica e independientemente distribuida, donde $S ∼ \mathcal{D}^m$, esto es cada $X_i$ sigue la misma distribución que $\mathcal{X}$, $X_i ∼ \mathcal{D}$, y las distribuciones marginales son independientes entre sí. Notaremos $S_x$ a una realización muestral $(x_1, \ldots x_m)$. Cada elemento $x_i$ de una realización muestral $S_x = (x_1, \ldots x_n)$ se etiqueta por $f$, y llamando $f(x_i) = y_i$ definimos como conjunto de entrenamiento a la tupla $((x_1, y_1), \ldots ,(x_m, y_m))$. La relación entre la realización muestral y el conjunto de entrenamiento asociado es biunívoca, por lo que por abuso de notación llamaremos indiferentemente conjunto de entrenamiento a ambas tuplas.
• Resultado del aprendizaje: disponemos de un algoritmo de aprendizaje $A: (\mathcal{X} × \mathcal{Y})^m → \mathcal{Y}^\mathcal{X}$ que recibe un conjunto de entrenamiento y devuelve una función $h: \mathcal{X} → \mathcal{Y}$ que llamaremos hipótesis/clasificador. El algoritmo “desconoce” el valor de la verdadera función de etiquetado $f$ en los puntos no pertenecientes al conjunto de entrenamiento.
• Error del clasificador: Definimos el error de un clasificador $h: \mathcal{X} → \mathcal{Y}$ como:

\[L_\mathcal{D,f}(h) := P (\{x∈ \mathcal{X} : h(x)≠ f(x)\}) = P[f≠ h]\]

Por simplificar la escritura, omitiremos a partir de ahora el hecho de que sobre $\mathcal{X}$ tenemos definida una $σ$ álgebra de conjuntos, $\mathscr{B}$, y que todas las distribuciones asignan probabilidad a los conjuntos de alguna $σ$ álgebra que contenga a $\mathscr{B}$. Además, consideraremos que la función de verdadero etiquetado y los clasificadores son funciones medibles para que la definición de los errores sea correcta.

Minimización del riesgo empírico (ERM)

Para un conjunto de entrenamiento el riesgo empírico proporciona el error del clasificador sobre el conjunto de entrenamiento.

Un algoritmo que obtiene una hipótesis que minimiza el error empírico sobre un conjunto de entrenamiento recibe el nombre de ERM y notamos $ERM(S_x)$ al clasificador obtenido con dicho algoritmo.

Este error no es siempre óptimo. Pensemos en el siguiente ejemplo:

Sea $\mathcal{X} = \mathbb{R}$, $\mathcal{D}$ la distribución uniforme sobre $[0,2]⊂ \mathbb{R}$, y la siguiente función:

\[f(x) = \left\{\begin{array}{lcl} 1 && x∈ [0,1]
0 && x∈ \mathbb{R}\setminus [0,1] \end{array}\right.\]

Sea $((x_1,y_1), \ldots (x_m, y_m))$ un conjunto de entrenamiento de tamaño $m$ y el clasificador:

\[h(x) = \left\{\begin{array}{lcl} y_i && ∃ i∈ \{1\ldots m\} : x=x_i
0 && \nexists i∈ \{1\ldots m\} : x=x_i \end{array}\right.\]

Nótese que el conjunto de entrenamiento no puede tener elementos no repetidos puesto que se etiquetan mediante $f$, que es una función y no puede arrojar dos imágenes distintas para un mismo $x ∈ \mathcal{X}$ de entrada.

Este clasificador es perfecto respecto a la minimización de riesgo empírico, pero $L_\mathcal{D, f}(h) = 1/2$. Es decir, tiene el mismo nivel de acierto que el clasificador idénticamente 1. A este fenómeno, minimizar el riesgo empírico siendo un clasificador con un error muy alto, lo denominamos overfitting.

El hecho de tomar el error sobre el conjunto de entrenamiento como aproximación al verdadero error del clasificador se respalda por la siguiente proposición:

Llamamos $p=P [f ≠ h ] = L_\mathcal{D,f}(h)$

\begin{align*} \mathbb{E} [L_S(h)] &= ∑_k=0^m \frac{k}{m} \binom{m}{k} p^k(1-p)^m-k = ∑_k=1^m \frac{k}{m} \binom{m}{k} p^k(1-p)^m-k \\ & ∑_k=1^m \binom{m-1}{k-1} p^k(1-p)^m-k = ∑_k=0^m-1 \binom{m-1}{k} p^k+1(1-p)^m-1-k =
&= p⋅ ∑_k=0^m-1 \binom{m-1}{k} p^k(1-p)^m-1-k = p(1+(1-p))^m-1 = p \end{align*}

ERM con sesgo inductivo

Con objeto de corregir el ERM, para evitar overfitting, usamos el conocimiento previo sobre el problema (la información que dispongamos sobre el dominio, la distribución, etc) restringiendo el espacio de búsqueda, esto es, la clase de hipótesis $\mathcal{H}$ desde la que el algoritmo puede escoger un $h: \mathcal{X}→ \mathcal{Y}$. Llamamos a esto sesgo inductivo puesto que se asumirá una determinada clase de funciones $\mathcal{H}$ en función de las características del problema.

Notaremos a un clasificador obtenido con este paradigma $h_{S_x} := ERM_\mathcal{H}(S_x)$, y lo definimos de manera que:

\[h_{S_x} ∈ \underset{h∈ \mathcal{H}}{argmin} \{L_{S_x}(h)\}\]

La existencia de $\underset{h∈ \mathcal{H}}{min} \{L_{S_x}(h)\}$ está garantizada, ya que $m ⋅ L_{S_x}(h) ∈ \mathbb{N}$ para todo $h∈ \mathcal{H}$.

Enunciamos la propiedad de factibilidad, que usaremos más adelante.

La hipótesis de factibilidad implica que $P [L_S(\bar{h})=0] = 1$, ya que:

\begin{align*} P (\{(x_1, \ldots x_m): \bar{h}(x_i) = f(x_i), i=1, \ldots m\}) =
= ∏_i=1^m P [h=f] = ∏_i=1^m (1 - P[h≠ f]) = 1 \end{align*}

Por tanto $P [L_S(h_S)=0]=1$.

Para finalizar estos preliminares remarcamos que el valor de $L_\mathcal{D,f}(h_{S_x})$ dependerá del conjunto de entrenamiento, extraído y etiquetado a partir del vector aleatorio $S$, y la elección del mismo está sometida al azar. Asimismo, necesitamos una medida de la bondad de la predicción.

Aprendizaje PAC.

Llamamos a $(1-δ)$ confianza de la predicción y a $(1-ε)$ la exactitud. Estos dos parámetros explican el nombre aproximadamente ($↔$ confianza) correcto ($↔$ exactitud).

Podemos considerar $m_\mathcal{H}$ única en el sentido de que para cada $(δ, ε)$ nos devuelva el menor natural verificando las hipótesis del enunciado.

Nótese que las condiciones exigidas, cumplir la propiedad de factibilidad y que la hipótesis devuelta deba estar en $\mathcal{H}$, son muy fuertes. Relajaremos esta definición más adelante con el concepto de PAC agnóstico.

Aprendizaje con clases finitas

Aprendizaje con clases no finitas

¿Hay ejemplos de clases infinitas PAC cognoscibles? Veamos un ejemplo.

Sea $A$ el algoritmo que devuelve el rectángulo más pequeño que engloba a todos los ejemplos positivos del conjunto de entrenamiento $S_x$.

Partiendo de la propiedad de factibilidad, debe existir un clasificador de rectángulo $\bar{h} = h_a,b,c,d$ que haga el ERM nulo y que cumpla $L_\mathcal{D,f}(\bar{h}) = 0$. Por tanto debe verificarse que $h_{S_x}$ debe acertar en todas las instancias positivas (cuya etiqueta sea 1) del conjunto de entrenamiento, con probabilidad 1, ya que si valiese 0 en algún ejemplo positivo del conjunto de entrenamiento, el ERM sería mayor que 0.

El algoritmo que devuelve el mínimo rectángulo que engloba a todos los ejemplos positivos es por tanto un ERM.

Veamos que con este algoritmo minimizador del ERM la clase de rectángulos es PAC cognoscible.

Sea $R^∗ = [a,b]× [c,d]$ el rectángulo que materializa la propiedad de factibilidad. Fijamos $1 > ε, δ > 0$.

Tomamos $R_1 = [a,b^∗] × [c,d]$ un rectángulo verificando $L_\mathcal{D,f}(\mathds{1}_{R_1}) ≤ ε/4$, con $a≤ b^∗ ≤ b$.

$R_2= [a^∗,b] × [c,d], R_3=[a,b] × [c,d^∗], R_4=[a,b] × [c^∗,d]$ se definen de forma análoga.

Llamando $h_R=A(S)$, $R(S) = R$ el rectángulo obtenido como resultado de aplicar el algoritmo del ejercicio para cada conjunto de entrenamiento, es claro que $P_{S ∼ \mathcal{D}^m}[R ⊂ R^∗] = 1$.

Supongamos $∀ i : R ∩ R_i ≠ ∅$. Entonces:

\[L_\mathcal{D,f}(h_R) = P_{x∼ \mathcal{D}} [h_R ≠ f] ≤ P \left(∪_i [h_R ≠ f] ∩ R_i\right) ≤ P \left(∪_i R_i\right) ≤ 4\frac{ε}{4} = ε\]

La demostración acaba probando que:

\[P_{S∼ \mathcal{D}^m} [∃ i : R(S)∩ R_i = ∅] ≤ ∑_i=1^4 P [R(S)∩ R_i = ∅] = 4(1-\frac{ε}{4})^m ≤ 4e^{-ε m/4}\]

y tomando $m > \frac{4}{ε} log \left( \frac{4}{δ} \right)$.

Generalización aprendizaje PAC: PAC agnóstico

Hasta ahora tenemos dos problemas en la definición de PAC. Intentamos buscar una hipótesis sobre una función de verdadero etiquetado, $f$ determinista, que por tanto no podrá asignar dos imágenes distintas al mismo punto, y además, estamos suponiendo que se cumple la propiedad de factibilidad.

Para paliar esto, podríamos considerar $\mathcal{D}$ como la distribución conjunta sobre $\mathcal{X} × \mathcal{Y}$, y la noción de error para $h: \mathcal{X} → \mathcal{Y}$ quedaría:

\[L_\mathcal{D}(h):= P_{(x,y) ∼ \mathcal{D}} [h(x) ≠ y]\]

Con estos conceptos revisitados, podríamos asegurar que la hipótesis que menor error comete para $\mathcal{Y} = \{0,1\}$ es el llamado clasificador de Bayes:

\[f_\mathcal{D}(x) = \left\{\begin{array}{ll} 1 & P [y = 1 |x] >= 0.5
0 & \quad si \quad no \end{array}\right.\]

Pero deseamos ir aún más allá, y generalizar la definición para una función de pérdida arbitraria.

Aumiendo ya como $\mathcal{D}$ la distribución conjunta, con funciones de pérdida arbitrarias, redefiniríamos los conceptos de error y error empírico de la forma:

\begin{align*} L_\mathcal{D} (h) := \mathbb{E}_{z∼ \mathcal{D}}[l(h,z)]
L_{S_z} (h) := \frac{1}{m} ∑_i=1^m l(h,z_i) \end{align*}

Donde los conjuntos de entrenamiento se generan a partir de una muestra aleatoria simple $S = (Z_1 × \ldots × Z_m)$ con $Z_i = (\mathcal{X}× \mathcal{Y})_i ∼ \mathcal{D}$

Notamos desde esta definición tomando una función de pérdida 0-1:

\[l_0-1 (h,(x,y)) := \left\{\begin{array}{ll} 0 & h(x) = y
1 & si \quad no \end{array}\right.\]

equivale a la primera definición que dimos de aprendizaje PAC si asumimos propiedad de factibilidad. Por ello no distinguiremos en el uso de uno u otro concepto, sino que se deducirá de si estamos asumiendo propiedad de factibilidad o no.

Cuando permitimos que el algoritmo $A$ devuelva una función $h ∉ \mathcal{H}$, de manera que $h ∈ \mathcal{H}’$ y $\mathcal{H} ⊂ \mathcal{H}’$ una clase de funciones donde la función de pérdida es extensible de manera natural, el aprendizaje recibe el nombre de aprendizaje impropio. La definición aquí dada se ha hecho para aprendizaje propio.

Condiciones suficientes para ser PAC cognoscible

Recordemos hasta ahora el resultado que habíamos obtenido era su carácter PAC cognoscible, donde agnósticamente PAC cognoscible y cognoscible con funciones de pérdida 0-1 era un término equivalente. El teorema que enunciamos a continuación, deducible a partir del teorema sobre el caracter agnóstico - PAC cognoscible de clases de funciones con propiedad de convergencia uniforme, en particular las finitas, generaliza el resultado para cualquier funciones de pérdida acotada.

Equilibrio error-varianza

Veamos que dado un algoritmo de aprendizaje no puede ser el óptimo para aprender todas las distribuciones.

Damos un lema previo, la desigualdad de Markov:

Como consecuencia del teorema, podemos decir que no hay un algoritmo de aprendizaje óptimo para todas las distribuciones, puesto que para una dada por el resultado del teorema, el algoritmo ERM con $\mathcal{H} = \{f\}$ aprendería mejor.