introduccion.tex

% Created 2017-01-14 sáb 04:04
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{marvosym}
\usepackage{wasysym}
\usepackage{amssymb}
\usepackage{hyperref}
\tolerance=1000
\usepackage{minted}
\usepackage[spanish]{babel}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{dsfont}
\newtheorem{theorem}{Teorema}
\newtheorem{fact}{Proposición}
\newtheorem{lemma}{Lema}
\newtheorem{corollary}{Corolario}
\newtheorem{definition}{Definición}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1em}
\usepackage{color}
\everymath{\displaystyle}
\usepackage{titlesec}
\newcommand{\sectionbreak}{\clearpage}
\author{ncordon}
\date{}
\title{PAC learning}
\hypersetup{
  pdfkeywords={},
  pdfsubject={},
  pdfcreator={Emacs 25.1.1 (Org mode 8.2.10)}}
\begin{document}

\input{./titlepage}
\maketitle
\tableofcontents

Estos apuntes son una adptación en su mayoría del contenido del libro \cite{shwartz_understanding_ml}
\section{Introducción}
\label{sec-1}
Damos unas notaciones/definiciones básicas que utilizaremos de aquí en adelante.

\begin{itemize}
\item \textbf{Dominio}: $\mathcal{X}$, sobre el que tenemos definida una $\sigma$ álgebra de conjuntos. Llamamos una instancia a $x\in \mathcal{X}$
\item \textbf{Conjunto de etiquetas}: $\mathcal{Y}$ consideramos $\{0,1\}$, lo que nos restringe al paradigma binario.
\item \textbf{Verdadero etiquetado}: Asumimos la existencia de una función $f: \mathcal{X} \rightarrow \mathcal{Y}$ que devuelve el verdadero etiquetado de todas las instancias.
\item \textbf{Generación de instancias}: Asumimos la existencia de una distribución de probabilidad $\mathcal{D}$ sobre $\mathcal{X}$, para la $\sigma$ álgebra de conjuntos mencionada anteriormente, que nos da información sobre la probabilidad de extraer cada posible instancia desde $\mathcal{X}$.
\item \textbf{Conjunto/Secuencia de entrenamiento}: $S = ((x_1,y_1), \ldots (x_m, y_m))$ secuencia con cada elemento perteneciente a $\mathcal{X}\times \mathcal{Y}$. A veces lo llamaremos conjunto, por abuso de notación, pero se trata de una tupla en $(\mathcal{X} \times \mathcal{Y})^m$ en la que pueden repetirse ejemplos. Podemos ver el conjunto de entrenamiento como una m.a.s (muestra aleatoria simple) $(\mathcal{X}_1,\ldots \mathcal{X}_m)$, idéntica e independientemente distribuida, donde cada $X_i$ sigue la misma distribución que $\mathcal{X}$, $X_i \sim \mathcal{D}$ y se etiqueta por $f$. Lo notaremos $S \sim \mathcal{D}^m$, por abuso de notación.
\item \textbf{Resultado del aprendizaje}: una función $h: \mathcal{X} \rightarrow \mathcal{Y}$ que llamaremos hipótesis/clasificador. Se usa la notación $A(S)$ para denotar la hipótesis que un algoritmo $A$ devuelve para una secuencia de entrenamiento $S$.
\item \textbf{Error del clasificador}: Definimos el error del clasificador, suponiendo $\{x\in \mathcal{X} : h(x) \neq f(x)\}$ en la $\sigma$ álgebra, como:
\end{itemize}

\[L_{D,f}(h) :=  P_{x\sim \mathcal{D}} [h(x)\neq f(x)]\]

Por simplificar la escritura, omitiremos a partir de ahora el hecho de que sobre $\mathcal{X}$ tenemos una $\sigma$ álgebra de conjuntos, y que todas las distribuciones asignan probabilidad convenientemente a los conjuntos de dicha $\sigma$ álgebra. Además, consideraremos que la función de verdadero etiquetado y los clasificadores son funciones medibles para que la definición de los errores sean correctas.

\subsection{Minimización del riesgo empírico (ERM)}
\label{sec-1-1}

\begin{definition}
\textbf{Riesgo empírico (ER)}

Definimos el riesgo empírico o error empírico como:

\[L_S(h) = \frac{\#\{i\in {1\ldots m}: h(x_i) \neq y_i\}}{m}\]
\end{definition}

Podemos pensar en él como el error del clasificador sobre el conjunto de entrenamiento. Un algoritmo que obtiene hipótesis que minimizan el error empírico recibe el nombre de \emph{ERM} y notamos $ERM(S)$ al clasificador que obtiene, para un determinado conjunto de entrenamiento $S \sim \mathcal{D}^m$.

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]\subset \mathbb{R}$, y la siguiente función:

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


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

\[h_S(x) = \left\{\begin{array}{lcl}
y_i && \exists i\in \{1\ldots m\} : x=x_i\\
0 && \nexists i\in \{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 \in \mathcal{X}$ de entrada.

Este clasificador es perfecto respecto a la minimización de riesgo empírico, pero $L_{\mathcal{D}, f}(h_S) = 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 \textbf{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:

\begin{fact}
\textbf{Relación entre ER y error del clasificador}

Sea $\mathcal{H}$ clase de clasificadores binarios sobre un dominio $\mathcal{X}$. Sea $\mathcal{D}$ una distribución desconocida sobre $\mathcal{X}$. Sea $f$ una hipótesis objetivo en $\mathcal{H}$. Se fija $h\in \mathcal{H}$. Probar que: 

\[\mathbb{E}_{S\sim \mathcal{D}} [L_S(h)] = L_{\mathbb{D},f}(h)\]
\end{fact}

Llamamos $P=\mathbb{P}_{x\sim \mathcal{D}}(f(x)\neq h(x))$

\begin{align*}
\mathbb{E}_{S\sim \mathcal{D}} [L_S(h)] &= \sum_{k=0}^m \frac{k}{m} \binom{m}{k} P^k(1-P)^{m-k} = \sum_{k=1}^m \frac{k}{m} \binom{m}{k} P^k(1-P)^{m-k} =\\
&= \sum_{k=1}^m \binom{m-1}{k-1} P^k(1-P)^{m-k} = \sum_{k=0}^{m-1} \binom{m-1}{k} P^{k+1}(1-P)^{m-1-k} = \\
&= P\cdot \sum_{k=0}^{m-1} \binom{m-1}{k} P^{k}(1-P)^{m-1-k} = P(1+(1-P))^{m-1} = P
\end{align*}

\subsection{ERM con \emph{sesgo inductivo}}
\label{sec-1-2}

Se intenta corregir el ERM 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}\rightarrow \mathcal{Y}$. Llamamos a esto \emph{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 = ERM_{\mathcal{H}}(S)$, y lo definimos de manera que:

\[h_S \in argmin_{h\in \mathcal{H}} L_S(h)\]

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

\begin{definition}
\textbf{Propiedad de factibilidad}

Existe  $\bar{h} \in \mathcal{H}$ verificando $L_{D,f}(\bar{h}) = 0$.
\end{definition}

La hipótesis de factibilidad implica que $P_{S\sim \mathcal{D}^m}[L_S(\bar{h})=0] = 1$, y por tanto $P_{S\sim \mathcal{D}^m}[L_S(h_S)=0]=1$.

El valor $L_{\mathcal{D},f}(h_S)$ dependerá del conjunto de entrenamiento $S$, y la elección del mismo está sometida al azar. Además, necesitamos una medida de la bondad de una predicción.

\section{Aprendizaje PAC.}
\label{sec-2}

\begin{definition}
\textbf{Aprendizaje PAC (Probablemente Aproximadamente Correcto)}

Una clase de funciones definidas sobre $\mathcal{X}$, $\mathcal{H}$ es PAC learnable si existe una función $m_{\mathcal{H}} : ]0,1[^2\rightarrow \mathbb{N}$, llamada complejidad muestral, y un algoritmo $A$ verificando que si $0 < \epsilon, \delta < 1$, entonces para toda distribución $\mathcal{D}$ sobre $\mathcal{X}$ y para toda función de verdadero etiquetado $f:\mathcal{X} \rightarrow \{0,1\}$, si la propiedad de factibilidad se cumple, ejecutando el algoritmo para un conjunto de entrenamiento $S\sim \mathcal{D}^m$ etiquetado mediante $f$, con $m\ge m_{\mathcal{H}}(\epsilon, \delta)$ el algoritmo devuelve una hipótesis $A(S) = h\in \mathcal{H}$ verificando que:

\[P_{S\sim \mathcal{D}^m}[L_{\mathcal{D},f}(h) \le \epsilon] \ge 1-\delta\]
\end{definition}

$(1-\delta)$ es la \emph{confianza de la predicción} (probablemente) y $(1-\epsilon)$ la \emph{exactitud} (correcto).

Podemos considerar $m_{\mathcal{H}}$ única en el sentido de que para cada $(\delta, \epsilon)$ nos devuelve 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.

\subsection{Aprendizaje con clases finitas}
\label{sec-2-1}

\begin{theorem}
\textbf{Las clases finitas de funciones son PAC learnable}

Sea $\mathcal{H}$ una clase finita de funciones definidas sobre un conjunto $\mathcal{X}$. Sean $0 < \epsilon, \delta < 1$, y un natural $m\in \mathbb{N}$ verificando:

\[m \ge \frac{1}{\epsilon}log\left(\frac{|\mathcal{H}|}{\delta}\right)\]

Entonces para toda función de verdadero etiquetado $f: \mathcal{X}\rightarrow \{0,1\}$, y para toda distribución $\mathcal{X}\sim \mathcal{D}$ para la que se verifique la \textbf{propiedad de factibilidad} entonces las hipótesis que obtenemos a través del algoritmo ERM son con una confianza superior a $1-\delta$, $1-\epsilon$ exactas.

Como consecuencia, deducimos que la complejidad muestral es menor o igual a $\left\lceil \frac{1}{\epsilon}log \left(\frac{|\mathcal{H}|}{\delta} \right) \right\rceil$
\end{theorem}

\begin{proof}
Fijada una distribución $\mathcal{D}$ y una función de etiquetado $f$, notamos:

\[\mathcal{H}_B = \{h\in \mathcal{H}: L_{\mathcal{D},f}(h) > \epsilon\}\]

Se tiene:

\[P_{S\sim \mathcal{D}^m}[L_{\mathcal{D},f}(h_S) > \epsilon] \le  P_{S\sim \mathcal{D}^m}[\exists h\in \mathcal{H}_B : L_S(h) = 0] \le \sum_{h\in \mathcal{H}_B} P_{S\sim \mathcal{D}^m}[L_S(h) = 0] \]

La primera desigualdad viene dada porque dada $h_S$ se verifica, por la propiedad de factibilidad, que $L_S(h_S)=0$. La segunda por subaditividad.

Además, fijada $h\in \mathcal{H}_B$, como $L_{\mathcal{D},f}(h) > \epsilon$:

\begin{align*}
P_{S\sim \mathcal{D}^m}[L_S(h) = 0] = P_{(x_1, \ldots x_n)\sim \mathcal{D}^m} [\forall i \quad h(x_i) = f(x_i)] =\\
= \prod_{i=1}^m P_{x\sim \mathcal{D}}[h(x)=f(x)] = \prod_{i=1}^m (1 - L_{\mathcal{D},f}(h)) \le (1-\epsilon)^m \le e^{-\epsilon m}
\end{align*}


Las dos desigualdades probadas, junto a la hipótesis del enunciado, y usando $\mathcal{H}_B \subseteq \mathcal{H}$ dan lugar a:

\[P_{S\sim \mathcal{D}^m}[L_{\mathcal{D},f}(h_S) > \epsilon] \le |\mathcal{H}|e^{-\epsilon m} \le \delta\]
\end{proof}

\subsection{Aprendizaje con clases no finitas}
\label{sec-2-2}

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

\begin{definition}
\textbf{Clasificadores de rectángulo}

Un clasificador de rectángulo es un clasificador que asigna 1 a los puntos que se quedan dentro de un cierto rectángulo en el plano real.

\[h_{a,b,c,d}(x,y) = \left\{\begin{array}{lcl}
1 && a\le x\le b, c\le y\le d\\
0 && si \quad no
\end{array}\right.\]

La clase de clasificadores de rectángulo en el plano se define por:

\[\mathcal{H}^2_{rec} = \{ h_{a,b,c,d}: a\le b, c\le d\}\]
\end{definition}


\begin{fact}
\textbf{Los rectángulos son PAC learnables}

Asumiendo propiedad de factibilidad, los rectángulos son PAC learnables
\end{fact}

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$.

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})$. Por tanto debe verificarse que $h_S$ debe contener a todos los ejemplos positivos del conjunto de entrenamiento, 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 learnable.

Sea $R^{\ast} = R(a,b,c,d)$ el rectángulo del apartado 1. Entonces $P_{S\sim \mathcal{D}^2}[f(R^{\ast})=\{1\}] = 1$

Tomamos $R_1 = R(a,a^{\ast},c,d)$ un rectángulo que concentra una masa de probabilidad menor o igual a $\epsilon/4$, con $a\le a^{\ast}$.

$R_2=(b^{\ast},b,c,d), R_3=(a,b,c,c^{\ast}), R_4=(a,b,d^{\ast},d)$ se definen de forma análoga.


Llamando $h_R=A(S)$, $R$ el rectángulo obtenido como resultado de aplicar el algoritmo del ejercicio. Es claro que con probabilidad 1, $R\subset R^{\ast}$. 

Si se tiene $\forall i : R\cap R_i \neq \emptyset$:

\begin{align*}
L_{\mathcal{D},f}(h_R) &= P_{x\sim \mathcal{D}}[h_R(x)\neq f(x)] \le P_{x\sim \mathcal{D}}\left(\cup_i [h_R(x)\neq f(x)]\cap R_i\right) \le\\
&\le P_{x\sim \mathcal{D}}\left(\cup_i R_i\right) \le 4\frac{\epsilon}{4} = \epsilon
\end{align*}


La demostración acaba probando que:

\[P(\exists i : S\cap R_i = \emptyset) \le \sum_{i=1}^4 P(S\cap R_i = \emptyset) = 4(1-\frac{\epsilon}{4})^m \le 4e^{-m}\]

\section{Generalización aprendizaje PAC: PAC agnóstico}
\label{sec-3}
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} \times \mathcal{Y}$, y la noción de error para $h: \mathcal{X} \rightarrow \mathcal{Y}$ quedaría:

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

Con estos conceptos revisitados, podríamos asegurar que la hipótesis que menor error comete para $\mathcal{Y} = \{0,1\}$ es el llamado \textbf{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.

\begin{definition}
\textbf{Función de pérdida}

Dados un conjunto $\mathcal{H}$, $Z$ y una $\sigma$ álgebra de conjuntos sobre $Z$, se denomina función de pérdida de $\mathcal{H}$ sobre $Z$ a cualquier función de la forma:

\[l : \mathcal{H} \times Z \rightarrow \mathbb{R}^{+}\]

que verifique que la función $l(h, \cdot)$ sea medible $\forall h\in \mathcal{H}$ sobre la $\sigma$ álgebra inicial.
\end{definition}

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

\begin{align*}
L_{\mathcal{D}} (h) := \mathbb{E}_{z\sim \mathcal{D}}[l(h,z)]\\
L_{S} (h) := \frac{1}{m} \sum_{i=1}^m l(h,z_i)
\end{align*}

\begin{definition}
\textbf{Aprendizaje PAC agnóstico}

Una clase de funciones $\mathcal{H}$ definidas en $\mathcal{X}$ y con imagen en $\mathcal{Y}$ es agnósticamente PAC learnable respecto a $Z = \mathcal{X} \times \mathcal{Y}$ (sobre el que tenemos definida una $\sigma$ álgebra de conjuntos) y a una función de pérdida $l: \mathcal{H} \times Z \rightarrow \mathbb{R}^{+}$ si existe una función $m_{\mathcal{H}} : ]0,1[^2\rightarrow \mathbb{N}$ y un algoritmo $A$ verificando que si $0 < \epsilon, \delta < 1$, entonces para toda distribución $\mathcal{D}$ sobre $Z$ ejecutando el algoritmo para un conjunto de entrenamiento $S\sim \mathcal{D}^m$, con $m\ge m_{\mathcal{H}}(\epsilon, \delta)$ el algoritmo devuelve una hipótesis $A(S) = h\in \mathcal{H}$ verificando que:

\[P_{S\sim \mathcal{D}^m}[L_{\mathcal{D}}(h) \le inf_{h'\in \mathcal{H}} L_{\mathcal{D}}(h') + \epsilon] \ge 1-\delta\]
\end{definition}


Notamos que esta definición, en caso de cumplirse la propiedad de factibilidad, tomando una \textbf{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 \notin \mathcal{H}$, de manera que $h \in \mathcal{H}'$ y $\mathcal{H} \subset \mathcal{H}'$ una clase de funciones a donde la función de pérdida es extendible de manera natural, el aprendizaje recibe el nombre de \textbf{aprendizaje impropio}. La definición aquí dada se ha hecho para \textbf{aprendizaje propio}.

\section{Condiciones suficientes para ser PAC learnable}
\label{sec-4}
\begin{definition}
\textbf{Conjunto de entrenamiento $\epsilon$ representativo}

Un conjunto de entrenamiento $S$ se dice $\epsilon$ representativo respecto a un dominio $Z$, a una clase de hipótesis $\mathcal{H}$, una función de pérdida $l$ y una distribución $\mathcal{D}$ sobre $Z$ si:

\[\forall h\in \mathcal{H}, |L_S(h)-L_{\mathcal{D}}(h)| \le \epsilon\]
\end{definition}

\begin{lemma}
Sea un conjunto de entrenamiento de tamaño $S$, $\frac{\epsilon}{2}$ representativo respecto a un dominio $Z$, a una clase de hipótesis $\mathcal{H}$, una función de pérdida $l$ y una distribución $\mathcal{D}$. Entonces:

\[L_{\mathcal{D}} (ERM_{\mathcal{H}}(S)) \le inf_{h\in \mathcal{H}} L_{\mathcal{D}}(h) + \epsilon\]
\end{lemma}

\begin{proof}
Para $h \in \mathcal{H}$ arbitrario:

\[L_{\mathcal{D}}(h_S) \le L_{\mathcal{S}}(h_S) + \frac{\epsilon}{2} \le L_{\mathcal{S}}(h) + \frac{\epsilon}{2} \le L_{\mathcal{D}}(h) + \frac{\epsilon}{2} + \frac{\epsilon}{2} =  L_{\mathcal{D}}(h) + \epsilon\]
\end{proof}

\begin{definition}
\textbf{Convergencia uniforme}

Decimos que una clase de hipótesis $\mathcal{H}$ tiene la propiedad de convergencia uniforme respecto a un dominio $Z$, y a una función $l$ si para todo $0 < \delta, \epsilon < 1$ existe $m_{\epsilon, \delta}$ verificando que para toda distribución $\mathcal{D}$ sobre $Z$, si $S$ es un conjunto de entrenamiento de tamaño mayor o igual a $m_{\epsilon, \delta}$, entonces:

\[P_{S\sim \mathcal{D}^m} [\forall h\in \mathcal{H}, |L_S(h) - L_{\mathcal{D}}(h)| \le \epsilon] \ge 1-\delta\]
\end{definition}

\begin{theorem}
\textbf{La convergencia uniforme es condición suficiente para ser PAC learnable}

Sea $\mathcal{H}$ una clase de hipótesis con la propiedad de convergencia uniforme. Entonces es PAC learnable con complejidad muestral menor o igual al $m_{\frac{\epsilon}{2}, \delta}$ dado en la definición anterior y el algoritmo ERM
\end{theorem}

\begin{proof}
La prueba es trivial desde el lema y la definición de convergencia uniforme.
\end{proof}

\begin{fact}
\textbf{Las clases finitas tienen la propiedad de convergencia uniforme}

Sea $\mathcal{H}$ una clase de hipótesis finita, $Z$ un dominio y sea $l : \mathcal{H} \times Z \rightarrow [a,b]$ una función de pérdida. Entonces $\mathcal{H}$ verifica la propiedad de convegencia uniforme con: 

\[m_{\epsilon, \delta} \le \left\lceil \frac{log(2|\mathcal{H}|/\delta)(b-a)^2}{2\epsilon^2} \right\rceil\]
\end{fact}

\begin{lemma}
\textbf{Desigualdad de Hoeffding}

Sean $X_1, \ldots X_n$ una muestra aleatoria simple de una variable $X$, $\bar{X} = \frac{1}{m} \sum_{i=1}^m X_i$ con $E[\bar{X}] = \mu$ y $P[a \le X_i \le b] = 1$. Entonces para todo $\epsilon > 0$

\[P\left[\left| \bar{X} - \mu \right| > \epsilon \right] \le 2e^{-2m \left(\frac{\epsilon}{(b-a)}\right)^2} \]
\end{lemma}

\begin{proof}
Sea $\mathcal{H}$ una clase de hipótesis finita.

Fijamos $0 < \delta, \epsilon < 1$. Necesitamos encontrar $m\in \mathbb{N}$ verificando:

\[P_{S\sim \mathcal{D}^m} [\exists h\in \mathcal{H} |L_S(h) - L_{\mathcal{D}}(h)| > \epsilon] < \delta\]

Partimos de la siguiente desigualdad, que usaremos más adelante, obtenida por subaditividad:

\[P_{S\sim \mathcal{D}^m} [\exists h\in \mathcal{H} |L_S(h) - L_{\mathcal{D}}(h)| > \epsilon] \le \sum_{h \in \mathcal{H}} P_{S\sim \mathcal{D}^m} [|L_S(h) - L_{\mathcal{D}}(h)| > \epsilon]\]
Fijamos $h \in \mathcal{H}$.

Dado un conjunto de entrenamiento $S = (z_1, \ldots z_m)$, recordamos que $L_{\mathcal{D}} (h) = \mathbb{E}_{z\sim \mathcal{D}} [l(h,z)]$ y que $L_S(h) = \frac{1}{m} \sum_{i=1}^m l(h,z_i)$

Donde $z_i \sim \mathcal{D}$ y por tanto $\mathbb{E}_{S \sim \mathcal{D}^m} [L_S(h)] = \mathbb{E}_{z \sim \mathcal{D}} [l(h,z)] = L_{\mathcal{D}} (h)$. Además, llamando $X_i = l(h,z_i)$, por ser $z_i$ realizaciones muestrales de una m.a.s se tiene que las $X_i$ son independientes e idénticamente distribuidas, con $P[a < X_i < b] = 1$. Estamos en condiciones de aplicar la desigualdad de Hoeffding.

Por tanto:

\[P_{S \sim \mathcal{D}^m} \left[\left| \frac{1}{m} \sum_{i=1}^m X_i - L_{\mathcal{D}} (h) \right| > \epsilon\right] = P_{S\sim \mathcal{D}^m} [|L_S(h) - L_{\mathcal{D}}(h)| > \epsilon] \le 2e^{-2m \left( \frac{\epsilon}{b-a} \right)^2}\]

Y por tanto:

\[P_{S\sim \mathcal{D}^m} [\exists h\in \mathcal{H} |L_S(h) - L_{\mathcal{D}}(h)| > \epsilon] < |\mathcal{H}| 2e^{-2m \left( \frac{\epsilon}{b-a} \right)^2}\]
\end{proof}

Recordemos hasta ahora el resultado que habíamos obtenido era su carácter PAC learnable, donde agnósticamente PAC learnable y learnable 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 learnable de clases de funciones con propiedad de convergencia uniforme, en particular las finitas, generaliza el resultado para cualquier funciones de pérdida acotada.

\begin{theorem}
\textbf{Las clases finitas son agnósticamente PAC learnable}

Sea $\mathcal{H}$ una clase de hipótesis finita, $Z$ un dominio y sea $l : \mathcal{H} \times Z \rightarrow [a,b]$ una función de pérdida. Entonces $\mathcal{H}$ es PAC learnable con complejidad muestral:

\[m_{\mathcal{H}}( \epsilon, \delta ) \le \left\lceil \frac{2 log(2|\mathcal{H}|/\delta)(b-a)^2}{\epsilon^2} \right\rceil\]
\end{theorem}

\section{Equilibrio error-varianza \emph{bias-complexity tradeoff}}
\label{sec-5}
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:

\begin{lemma}
\textbf{Desigualdad de Markov}

Dada una variable aleatoria $Z$ no negativa. Entonces para todo $a\ge 0$

\[P[Z \ge a] \le \frac{\mathbb{E}[Z]}{a}\]
\end{lemma}

\begin{theorem}
\textbf{Teorema de No Free Lunch}

Sea $A$ cualquier algoritmo de aprendizaje para clasificación binaria con respecto a la función de pérdida 0-1 sobre el dominio $\mathcal{X}$. Sea un conjunto de entrenamiento de tamaño $m < |\mathcal{X}|/2$. Entonces existe una distribución $\mathcal{D}$ sobre $\mathcal{X} \times \{0,1\}$ verificando:

\begin{enumerate}
\item Existe una función $f: \mathcal{X} \rightarrow \{0,1\}$ con $L_{\mathcal{D}}(f)=0$
\item $P_{S\sim \mathcal{D}^m} [L_{\mathcal{D}} (A(S)) \ge 1/8] \ge 1/7$
\end{enumerate}
\end{theorem}

\begin{proof}
Sea un conjunto de entrenamiento (consideramos un conjunto y no una secuencia) de tamaño $2m$, $C$. Hay $T = 2^{2m}$ posibilidades de etiquetado del conjunto, esto es, $2^{2m}$ posibles hipótesis, $f_i: C\rightarrow \{0,1\}$, que vamos a extender a $\mathcal{X}$ llamándolas $\bar{f}_i$ de forma que $\bar{f}_{i|C} = f_i$ y $\bar{f}_i(x) = 0 \quad \forall x\in \mathcal{X}\setminus C$. Vamos a tomar para cada una de ellas una distribución $\mathcal{D}_i$ definida sobre $\mathcal{X} \times \{0,1\}$ definida por:


\[\forall (x,y)\in \mathcal{X} \times \{0,1\} \qquad P_{z\sim \mathcal{D}_i} [z = (x,y)] = \left\{\begin{array}{ll}
1/|C| & \exists x_i \in C : y=f(x_i)\\
0     & si \quad no
\end{array}\right.\]

Claramente $L_{\mathcal{D}_i}(f_i) = 0$

Vamos a probar que:

\[\exists i\in \{1, \ldots 2m\} : \mathbb{E}_{S\sim \mathcal{D}_i^m} [L_{\mathcal{D}_i} (A(S))] \ge \frac{1}{4}\]

Hay $k = (2m)^m$ posibles secuencias de entrenamiento de tamaño $m$, $S_j, j=1, \ldots k$ tomadas desde $C$. Siendo $S_j = (x_1, \ldots x_m)$ notamos $S_j^i = ((x_1, f_i(x_1)), \ldots, (x_m, f_i(x_m)))$. Cada $S_j$ tiene la misma probabilidad de ser nuestro conjunto de entrenamiento (extracción de $m$ valores con reemplazamiento desde el conjunto $C$), verificándose:

\[\mathbb{E}_{S\sim \mathcal{D}_i^m} [L_{\mathcal{D}_i} (A(S))] = \frac{1}{k} \sum_{j=1}^k L_{\mathcal{D}_i} (A(S_j^i))\]

Recordando que hemos llamado $k=(2m)^m$, $T=2^{2m}$, se tiene:

\begin{align*}
max_{i \in \{1,\ldots T\}} \frac{1}{k} \sum_{j=1}^{k} L_{\mathcal{D}_i} (A(S_j^i)) &\ge 
       \frac{1}{T} \sum_{i=1}^{T} \frac{1}{k} \sum_{j=1}^{k}  L_{\mathcal{D}_i} (A(S_j^i))   =\\
&=     \frac{1}{k} \sum_{j=1}^{k} \frac{1}{T} \sum_{i=1}^{T}  L_{\mathcal{D}_i} (A(S_j^i)) \ge\\
&\ge min_{j \in \{1, \ldots k\}} \frac{1}{T} \sum_{i=1}^{T}  L_{\mathcal{D}_i} (A(S_j^i))
\end{align*}


Además fijado $j \in \{1,\ldots k\}$, se tiene que que para todo $i \in \{1,\ldots T\}$:

\[L_{\mathcal{D}_i} (h) = \frac{1}{|C|} \sum_{x\in C} \mathds{1}_{[A(S^i_j)(x) \neq f_i(x)]} = \frac{1}{2m} \sum_{x \in C} \mathds{1}_{[A(S^i_j)(x) \neq f_i(x)]}\]


Por tanto:

\begin{align*}
\frac{1}{T} \sum_{i=1}^{T}  L_{\mathcal{D}_i} (A(S_j^i)) &\ge
\frac{1}{T} \sum_{i=1}^{T}  \frac{1}{2m} \sum_{x \in C} \mathds{1}_{[A(S^i_j)(x) \neq f_i(x)]} = \\
&= \frac{1}{2m} \sum_{x \in C} \frac{1}{T} \sum_{i=1}^{T}  \mathds{1}_{[A(S^i_j)(x) \neq f_i(x)]} \ge \\
&\ge \frac{1}{2} min_{x\in C} \frac{1}{T} \sum_{i=1}^{T}  \mathds{1}_{[A(S^i_j)(x) \neq f_i(x)]}
\end{align*}


Como dado un $x\in C$ cualquiera, la mitad de clasificadores $f_i$ clasificarán $x$ bien y la otra mitad mal, se tiene:

\[\frac{1}{2} min_{x\in C} \frac{1}{T} \sum_{i=1}^{T}  \mathds{1}_{[A(S^i_j)(x) \neq f_i(x)]} = \frac{1}{2} \frac{1}{T} \frac{T}{2} = \frac{1}{4}\]

Y uniendo toda esta información:

\[max_{i \in \{1,\ldots T\}} \frac{1}{k} \sum_{j=1}^{k} L_{\mathcal{D}_i} (A(S_j^i)) \ge \frac{1}{4}\]

Sea $k = argmax_{i \in \{1,\ldots T\}} \frac{1}{k} \sum_{j=1}^{k} L_{\mathcal{D}_i} (A(S_j^i))$

Si $\mathcal{D} = \mathcal{D}_k$ cumple la parte 2 del enunciado del teorema, es nuestra distribución buscada, y como función buscada en el apartado 1. podemos tomar $f=f_k$

Como $L_{\mathcal{D}} (A(\cdot))$ puede ser vista como una variable aleatoria donde $S \sim \mathcal{D}^m$ y que toma valores en $[0,1]$, tenemos que tomando $Z = 1-L_{\mathcal{D}}(A(\cdot))$, $a=\frac{7}{8}$ en el lema previo llegamos a:

\[P_{S\sim \mathcal{D}^m} \left(\frac{1}{8} \ge L_{\mathcal{D}}(A(S)) \right) \le \frac{3}{4} \cdot \frac{8}{7} = 24/28\]

donde $\mathbb{E}(Z) = \mathbb{E} (1 - L_{\mathcal{D}}(A(\cdot))) = 1 - \mathbb{E} (L_{\mathcal{D}}(A(\cdot))) \le \frac{3}{4}$

Es decir:

\[P_{S\sim \mathcal{D}^m} \left( L_{\mathcal{D}}(A(S)) \ge \frac{1}{8} \right) \ge \frac{4}{28} = \frac{1}{7}\]
\end{proof}


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.



\bibliography{references}
\bibliographystyle{IEEEtran}
% Emacs 25.1.1 (Org mode 8.2.10)
\end{document}