La dimensión Vapnik-Chervonenkis en Ciencia de los datos

Facultad de Matem´ aticas Grado de Matem´ aticas Trabajo Fin de Grado La dimensi´on Vapnik-Chervonenkis en Ciencia de los datos Realizado por: Miguel V´azquez Caraballo Dirigido por: D. Joaqu´ın Borrego D´ıaz Departamento: Ciencias de la Computaci´on e Inteligencia Artificial Sevilla, Junio 2022 ´ Indice general Introducci´on 5 Objetivo.................................. 5 Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . 6 1. La dimensi´on Vapnik-Chervonenkis 7 1.1. Definici´on de la dimensi´on VC . . . . . . . . . . . . . . . . . . . 7 1.2. Propiedades de la dimensi´on VC . . . . . . . . . . . . . . . . . . 8 2. Ejemplos de Dimensi´on Vapnik-Chervonenkis 11 2.1. Clasesenelplano.......................... 11 2.2. Clases en la recta real . . . . . . . . . . . . . . . . . . . . . . . 13 2.3. Clases en el espacio de d dimensiones . . . . . . . . . . . . . . . 14 2.4. Funcionesreales........................... 16 3. Aprendizaje PAC 21 3.1. Definiciones b´asicas . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2. ElparadigmaERM......................... 23 3.3. Clases aprendible PAC . . . . . . . . . . . . . . . . . . . . . . . 25 3.3.1. Aprendizaje PAC para clasificaci´on binaria . . . . . . . . 26 3.3.2. Aprendizaje PAC agn´ostico para clasificaci´on binaria . . 29 III IV ´ Indice general 3.3.3. Aprendizaje PAC agn´ostico generalizado . . . . . . . . . 29 3.4. Convergencia uniforme . . . . . . . . . . . . . . . . . . . . . . . 30 3.5. Las clases finitas son aprendibles PAC agn´ostico............................... 31 4. El Teorema Fundamental del Aprendizaje Estad´ıstico 35 4.1. Teorema No-Free-Lunch . . . . . . . . . . . . . . . . . . . . . . 36 4.2. Las clases de hip´otesis infinitas pueden ser aprendibles . . . . . 40 4.3. Dimensi´on VC y aprendizaje PAC . . . . . . . . . . . . . . . . . 41 4.4. El Teorema Fundamental del Aprendizaje Estad´ıstico . . . . . . 42 Ap´endice 49 Conclusiones 53 Referencias 55 Resumen En esta memoria se expone la dimensi´on de VC, un concepto originalmente definido por V. N. Vapnik y A. Ya. Chervonenkis que es una medida de la capacidad que tiene una familia de funciones para realizar clasificaci´on binaria de un conjunto de datos, de gran importancia en la teor´ıa de Aprendizaje Estad´ıstico. Se aporta su definici´on y algunas propiedades importantes, as´ı como una colecci´on de ejemplos de su c´alculo. Para mostrar su relaci´on con la Ciencia de los datos, se desarrolla el marco de aprendizaje PAC como modelo fundacional de la noci´on de aprendibilidad automatizada de un problema. As´ı, se identifican las clases de funciones aprendibles a partir de su dimensi´on VC mediante el Teorema Fundamental del Aprendizaje Estad´ıstico. 1 Abstract In this report we present the VC dimension, a concept originally defined by V. N. Vapnik and A. Ya. Chervonenkis, which is a measure of the ability of a family of functions to perform binary classification of a data set, of great importance in Statistical Learning theory. Its definition and some important properties are provided, as well as a collection of examples of its computation. To show its relation to Data Science, the PAC learning framework is developed as a foundational model of the notion of automated problem learning. Thus, the classes of learnable functions are identified from their VC dimension by means of the Fundamental Theorem of Statistical Learning. 3 Introducci´on La teor´ıa del aprendizaje estad´ıstico ha desarrollado diferentes m´etodos y herramientas para cuantificar la capacidad y riqueza de un modelo de clasificaci´on binaria. Entre ´estos una de las m´as famosas es la dimensi´on de Vapnik- Chervonenkis. El problema del aprendizaje estad´ıstico se plantea como sigue. Asumiendo que los ejemplos est´an distribuidos seg´un una probabilidad desconocida Dsobre la poblaci´on, el algoritmo considera un conjunto hip´otesis Hde posibles conceptos, que son funciones que relacionan los datos con el valor objetivo a estudiar, recibe un conjunto de entrenamiento Sde datos escogidos seg´un Dy devuelve una hip´otesis hS∈ H a partir de S. El objetivo es que a partir de los datos en Sla hip´otesis se asemeje al concepto objetivo ca aprender que relaciona los datos con el valor objetivo real de la poblaci´on total. Para estudiar el problema te´oricamente, Leslie Valiant expone en 1984 el marco de aprendizaje Correcto Probablemente Aproximado (PAC por sus siglas en ingl´es). En el marco de aprendizaje PAC, se considera que una clase de conceptos es aprendible si existe un algoritmo de aprendizaje que al tomar un conjunto de datos i.i.d. seg´un cualquier distribuci´on sobre la poblaci´on, es capaz de devolver, con alta probabilidad, una hip´otesis con peque˜no error, provisto de una muestra de tama˜no suficiente. En este trabajo veremos los conceptos te´oricos del marco PAC y como esta noci´on de aprendizaje PAC est´a ´ıntimamente relacionada con la finitud de la dimensi´on Vapnik-Chervonenkis de una clase de funciones. Objetivo El objetivo principal del trabajo es presentar y comprender el concepto de dimensi´on de Vapnik-Chervonenkis. Para ello desarrollamos conceptos te´oricos 5 12 Cap´ıtulo 2. Ejemplos de Dimensi´on Vapnik-Chervonenkis de m´ınima ´area que los contenga. En cada arista hay al menos un punto. Identifiquemos un punto de este tipo por cada arista. Si un punto est´a en un esquina, puede ser identificado con ambas aristas. Si en una arista hay dos puntos o m´as, se elige uno cualquiera de ellos. Hemos definido un conjunto de a lo m´as cuatro puntos. Cualquier rect´angulo que contenga estos puntos contiene tambi´en a los dem´as, por lo tanto estos puntos no pueden ser desmenuzados del resto con rect´angulos con aristas paralelas a los ejes, y dimV C(R2,H) = 4. 2 Teorema 2.1.2 Sea Hla clase de las regiones planas determinadas por cuadrados con lados paralelos a los ejes. Entonces dimV C(R2,H)=3 Demostraci´ on: Existen tres puntos que pueden ser desmenuzados por cuadrados con lados horizontales y verticales. Veamos el ejemplo de puntos formando un tri´angulo rect´angulo. Desmenuzar los subconjuntos de 1 y 3 puntos es trivial. La siguiente imagen muestra como podemos desmenuzar dos puntos. Figura 2.2: Desmenuzado de los tres subconjuntos posibles de dos puntos Estudiemos ahora el caso de cuatro puntos. Llamemos Aal punto de mayor ordenada, Bal de menor ordenada, Ial de menor abscisa y Dal de mayor abscisa, asumiendo que se pueden definir de forma ´unica. Asumamos sin p´erdida de generalidad que la distancia de AaB es mayor que la de IaD. Entonces AyBno pueden ser desmenuzados por H. Si no se pueden definir estos puntos de forma ´unica, entonces o bien hay un punto contenido en el m´ınimo rect´angulo que encierra a los otros tres de forma que el subconjunto formado por esos tres puntos no puede ser desmenuzado, o los cuatro puntos est´an alineados y el subconjunto formado por los puntos de los extremos del segmento que une los cuatro puntos no es desmenuzable. Por lo tanto dimV C(R2,H) = 3. 2 Teorema 2.1.3 Sea Hla clase de los c´ırculos centrados en el origen. Entonces dimV C(R2,H) = 1 2.2. Clases en la recta real 13 Demostraci´ on: Consideremos un conjunto formado por un ´unico punto x∈ R. Existen dos subconjuntos, el vac´ıo y el propio conjunto. Para desmenuzar el vac´ıo escoger cualquier c´ırculo de radio r < ∥x∥2y para desmenuzar el propio conjunto tomar r > ∥x∥2. Consideremos ahora un conjunto de dos puntos en el plano. Si la distancia de los puntos al origen es la misma, Hno puede desmenuzar ning´un subconjunto formado por solo uno de los puntos, y si la distancia al origen es distinta, Hno puede desmenuzar el subconjunto formado por el punto m´as alejado del origen. Por lo tanto Hno puede desmenuzar ning´un conjunto de dos o m´as puntos y dimV C(R2,H)=1 2 Teorema 2.1.4 Sea Hla clase formada por todos los pol´ıgonos convexos en el plano. Entonces dimV C(R2,H) = ∞ Demostraci´ on: Dado n∈Nconsideremos npuntos en la circunferencia unidad. Tomando cualquier subconjunto de estos puntos se ordenan en sentido horario y se unen con segmentos en ese orden. Esto nos da un pol´ıgono convexo que contiene a este subconjunto y a ning´un otro punto que no pertenezca al subconjunto. As´ı esta familia puede desmenuzar subconjuntos arbitrariamente grandes y dimV C(R2,H) = ∞.2 2.2. Clases en la recta real Teorema 2.2.1 Sea Hla clase formada por los intervalos en los n´umeros reales. Entonces dimV C(R,H)=2 Demostraci´ on: Consideremos un conjunto A={x1, x2} ⊂ Rcon x1< x2. Hay cuatro subconjuntos de A. Para desmenuzar ∅tomar el intervalo (−∞, a] con a<x1. Para {x1}tomar (−∞, b] con x1< b < x2. Para {x2}tomar [b, +∞). Para {x1, x2}tomar R. 14 Cap´ıtulo 2. Ejemplos de Dimensi´on Vapnik-Chervonenkis Si tenemos un conjunto B={x1, x2, x3} ⊂ Rcon x1< x2< x3cualquier intervalo que contenga a x1yx3tambi´en contiene a x2, luego no existe ning´un intervalo que desmenuze {x1, x3}. Por lo tanto dimV C (R,H) = 2. 2 Teorema 2.2.2 Sea Hla clase formada por los pares de intervalos en los n´umeros reales definidos como la uni´on de dos intervalos reales. Entonces dimV C(R,H)=4 Demostraci´ on: Consideremos un conjunto de cuatro puntos reales. Desmenuzar los subconjuntos de uno, dos y cuatro puntos es trivial. Si tenemos un subconjunto de tres puntos o bien los tres son consecutivos y un intervalo que los contenga y no contenga al punto que no pertenece al subconjunto desmenuza al subconjunto o hay uno aislado de los otros dos por el punto que no pertenece al subconjunto y basta tomar un intervalo que contenga al punto aislado y otro que contenga al par de puntos restante y que no contengan al punto que no pertenece al subconjunto. Sin embargo, no existe ning´un conjunto de cinco puntos que sea desmenuzable, pues no podemos desmenuzar el subconjunto formado por el primer, tercer y quinto puntos con la uni´on de dos intervalos sin coger los otros dos. Luego dimV C(R,H) = 5. 2 2.3. Clases en el espacio de d dimensiones Teorema 2.3.1 Sea S(d) := {(−∞, t1]×(−∞, t2]×. . . ×(−∞, td]|(t1, ..., td)∈Rd} la clase de intervalos medios en Rd. Entonces dimV C(Rd, S(d)) = d Demostraci´ on: Consideremos los d vectores unitarios. Es posible desmenuzar cualquier subconjunto tomando ti= 1 si el vector i pertenece al subconjunto y ti= 0 si no pertenece. Sean d+ 1 puntos arbitrarios x1, ..., xd+1. Tomemos para cada 1 ≤i≤d, ti= m´ax1≤j≤d+1(xj)i. Hay como m´aximo dpuntos distintos en la frontera de (−∞, t1]×. . .×(−∞, td]. Estos puntos no pueden ser desmenuzados por ning´un conjunto de la familia S(d). 2 Teorema 2.3.2 Sea Hla clase formada por los semiespacios en ddimensiones. Entonces dimV C(Rd,H) = d+ 1 2.3. Clases en el espacio de d dimensiones 15 Se define un semiespacio como el conjunto de todos los puntos que quedan a un lado de un hiperplano, i.e. {x|aTx≥a0}. Demostraci´ on: Consideremos el conjunto consistente en el origen y los d vectores con coordenadas unitarias. Supongamos que tenemos un subconjunto Aarbitrario. Si el origen pertenece a A, tomemos el vector aque tiene un cero en las coordenadas correspondientes a los vectores unitarios que pertenecen a Ay un uno a los que no pertenecen. Entonces el semiespacio {x|aTx≤0} desmenuza A. Si el origen no pertenece a Ase toma el vector ade forma inversa al caso anterior y consideramos el semiespacio {x|aTx≥1}. Veamos ahora que ning´un conjunto de d+2 puntos puede ser desmenuzado por semiespacios. El teorema de Radon afirma que cualquier conjunto de d+2 puntos puede ser separado en dos subconjuntos disjuntos AyBtal que si convex(A) y convex(B) son sus respectivas envolventes convexas, entonces convex(A)∩convex(B)=∅. El teorema de Radon implica que ning´un conjunto de d+2 puntos puede ser desmenuzado por semiespacios. Tomando una partici´on disjunta A y B tal que convex(A)∩convex(B)=∅, si un semiespacio desmenuza estos dos conjuntos entonces el hiperplano que lo define separa sus envolventes convexas, por lo que convex(A)∩convex(B) = ∅, una contradicci´on. 2 Teorema 2.3.3 (Radon) Para todo conjunto S⊂Rdcon |S| ≥ d+ 2 existe una partici´on en dos conjuntos disjuntos A y B tal que convex(A)∩convex(B)= ∅. Demostraci´ on: Sin p´erdida de generalidad, asumir que |S|=d+ 2. Sea A la matriz que tiene en cada columna un punto de S. A es una matriz d×(d+ 2). Sea B la matriz (d+1)×(d+2) resultante de a˜nadir un fila de unos a A. Como el rango de B es a lo m´as d+ 1, sus columnas son linealmente dependientes. Sea x= (x1, x2, ..., xd+2) un vector no nulo con Bx= 0. Reordenar los elementos de xpara que x1, ..., xt≥0 y xt+1, ..., xd+2 <0. Normalizar xtal que t X i=1 |xi|= 1. Sean aiybilas i-´esimas columnas de A y B respectivamente. Entonces t X i=1 |xi|bi= d+2 X i=t+1 |xi|bi= 1 de donde t X i=1 |xi|ai= d+2 X i=t+1 |xi|aiy t X i=1 |xi|= d+2 X i=t+1 |xi|. Como t X i=1 |xi|= 1 y d+2 X i=t+1 |xi|= 1 cada lado de t X i=1 |xi|ai= 16 Cap´ıtulo 2. Ejemplos de Dimensi´on Vapnik-Chervonenkis d+2 X i=t+1 |xi|ai= 1 es una combinaci´on convexa de columnas de A y por lo tanto de puntos de S. Tomando el conjunto de los primeros tpuntos y otro conjunto de los puntos t+ 1 a d+ 2 tras la reordenaci´on tenemos una partici´on de S que satisface las propiedades del teorema. 2 Teorema 2.3.4 Sea H(d)la clase formada por las esferas en ddimensiones. Entonces dimV C(Rd,H(d)) = d+ 1 Una esfera en ddimensiones es un conjunto {x∈Rd| |x−x0| ≤ r}∈H(d) Demostraci´ on: En primer lugar mostremos que ning´un conjunto Sde d+ 2 puntos puede ser desmenuzado por esferas. Supongamos que cualquier partici´on A1yA2de Spuede ser desmenuzada por H(d). Entonces existen esferas B1, B2∈ H(d) tal que B1∩S=A1yB2∩S=A2. Si B1yB2no se intersecan, existe un hiperplano que las separa y entonces separa tambi´en a A1yA2. Si se intersecan, no hay puntos de Sen la intersecci´on, y hay un hiperplano perpendicular a la recta que une los centros de las dos esferas que deja los puntos de A1a un lado y los de A2a otro. Por lo tanto S ser´ıa desmenuzable por semiespacios, que es falso pues hay d+ 2 puntos en Sy los semiepacios tienen dimensi´on VC d+ 1. Veamos ahora que el conjunto Sde d+ 1 puntos formado por los vectores de coordenada unitaria y el origen es desmenuzable por esferas en ddimensiones. Sea A⊂Sun subconjunto y ael n´umero de vectores unitarios en A. Tomemos una esfera con centro a0la suma de los vectores de Ay radio r∈(√a−1,√a+ 1). La distancia de todo vector unitario perteneciente a A hasta a0es √a−1, y la de los vectores que no pertenecen a Aes √a+ 1. As´ı que esta esfera desmenuza A. Entonces las esferas en ddimensiones tienen dimensi´on VC d+ 1, al igual que los semiespacios en ddimensiones. 2 2.4. Funciones reales Teorema 2.4.1 La clase de funciones F={f|f(x) = sign(sen(ωx)), ω ≥0} 2.4. Funciones reales 17 con dominio X= [0,2π]tiene dimV C(X, F) = +∞ Demostraci´ on: Para demostrar que la dimensi´on VC de esta familia es infinita buscamos para cualquier n∈Nun conjunto de puntos en Xde tama˜no nque pueda ser desmenuzado por F. Consideremos {(2π10−i, yi)}n i=1 ⊂Xn× {−1,1}ndonde yies la etiqueta de cada punto xi= 2π10−i. Para un conjunto de este tipo escogeremos el par´ametro ω=1 2 1 + n X i=1 1−yi 210i! Primero probamos que se predicen correctamente los xicon etiquetas negativas. Se puede reescribir ωcomo ω=1 2 1 + X {i:yi=−1} 10i . Entonces, para cada jtal que yj=−1 ωxj=π10−j 1 + X {i:yi=−1} 10i  =π10−j 1 + 10j+X {i:yi=−1, i=j} 10i  =π 10−j+1+ X {i:yi=−1, i=j} 10i−j  =π 10−j+1+ X {i:yi=−1, i>j} 10i−j+X {i:yi=−1, i<j} 10i−j . Para i > j los t´erminos 10i−json potencias positivas de 10 y por lo tanto tambi´en n´umeros pares, as´ı que pueden ser reescritos como 2kipara ciertos ki∈N. Por lo que se tiene que X {i:yi=−1, i>j} 10i−j=X {i:yi=−1, i>j} 2ki= 2k 18 Cap´ıtulo 2. Ejemplos de Dimensi´on Vapnik-Chervonenkis Para cierto k∈N. Para el otro sumando se tiene X {i:yi=−1, i<j} 10i−j< +∞ X i=1 10−i= +∞ X i=0 1 10i −1 = 1 1−0,1−1 = 1 9. Ahora, usando esto y que 10−j<0,1, definimos ϵ= 10−j+X {i:yi=−1, i<j} 10i−j<1 10 +1 9= 1 se tiene que ωxj=π(1 + ϵ)+2kπ y como 0 <ϵ<1, finalmente sin(ωxj)<0 y por lo tanto f(xj) = sign(sen(ωxj)) = −1 = yjy todas las etiquetas negativas est´an bien clasificadas. Ahora probaremos que tambi´en se predicen correctamente los xicon etiquetas positivas. El procedimiento es similar al anterior, con la diferencia de que al tener yj= 1, el t´ermino 10jse anula ahora en la definici´on de ω. ωxj=π10−j 1 + X {i:yi=−1, i=j} 10i  =π 10−j+X {i:yi=−1, i>j} 10i−j+X {i:yi=−1, i<j} 10i−j  =πϵ + 2kπ y como 0 < ϵ < 1, y 0 < πϵ < π se tiene que f(xj) = 1 = yj. Por lo tanto esta familia de funciones clasifica correctamente el conjunto, y lo hace para toda n∈N, por lo que dimV C(X, F) = +∞ 2 Teorema 2.4.2 Sea F={f(·, t)|t∈R}la clase de funciones con f(x;t) = (1si x∈(−∞, t]∪[t+ 1,+∞) −1si x∈(t, t + 1) 2.4. Funciones reales 19 entonces dimV C(R,F) = 3 Demostraci´ on: Esta funci´on puede desmenuzar el siguiente conjunto de tres puntos Sin embargo, no puede desmenuzar conjuntos de cuatro puntos, ya que no puede desmenuzar el subconjunto formado por el primer y tercer punto. Por lo tanto, la dimensi´on VC de (R,F) es 3. 2 Cap´ıtulo 3 Aprendizaje PAC En este cap´ıtulo introducimos el marco de aprendizaje estad´ıstico aprendizaje correcto probablemente aproximado, o aprendizaje PAC por sus siglas en ingl´es. Para ello se han utilizado teoremas y demostraciones de [6] y [7]. Cuando se desarrollan y analizan algoritmos que aprenden a partir de ejemplos surgen preguntas fundamentales: ¿Qu´e puede ser aprendido? ¿C´omo de complejo es el aprendizaje? ¿C´omo influye el tama˜no del conjunto de datos en los resultados? ¿Hay un modelo general de aprendizaje? Para responder a estas preguntas se introdujo el marco de aprendizaje PAC. Valiant introdujo esta teor´ıa en 1984 en [10] para que los cient´ıficos de la Computaci´on estudiaran la eficiencia computacional de los algoritmos de aprendizaje. Aunando diferentes aproximaciones que se hab´ıan hecho hasta el momento sobre la idea de aprendizaje, consigui´o una noci´on de problemas de aprendizaje que son resolubles, en el sentido de que existe un algoritmo que los resuelve en tiempo polinomial, en analog´ıa a la clase Pde la Teor´ıa de la Complejidad cl´asica. Desde 1984 muchos inform´aticos te´oricos e investigadores de aprendizaje autom´atico han obtenido importantes resultados en esta teor´ıa, convirtiendo el aprendizaje PAC en el marco de aprendizaje mas importante dentro de la teor´ıa del aprendizaje computacional. Como se ha comentado el marco PAC aporta definiciones de la clase de conceptos aprendibles en funci´on del tama˜no de la muestra de datos necesario para alcanzar una soluci´on aproximada, y la complejidad del algoritmo en espacio y tiempo. En la siguiente secci´on se introducen los elementos fundamentales. 21 28 Cap´ıtulo 3. Aprendizaje PAC Demostraci´ on: Para ϵ > 0 se define Hϵ={h∈ H :RD(h)> ϵ} . La probabilidad de que un concepto h∈ Hϵsea consistente en un conjunto de entrenamiento Sseleccionado i.i.d. seg´un Dse puede acotar superiormente P[b RS(h) = 0] ≤(1 −ϵ)mde lo que se sigue Ph∃h∈ Hϵ:b RS(h) = 0i=Phb RS(h1)=0∨···∨ b RS(h|Hϵ|) = 0i ≤X h∈Hϵ Phb RS(h) = 0i≤X h∈Hϵ (1 −ϵ)m≤ |H|(1 −ϵ)m≤ |H|e−mϵ ≤δ Donde en la ´ultima desigualdad hemos utilizado que m≥1 ϵlog |H| δ. Finalmente, PS∼Dm[RD(h−S)≤ϵ] = 1 −Ph∃h∈ Hϵ:b RS(h)=0i≥1−δ 2 Una formulaci´on equivalente del teorema establece un l´ımite superior del error real. Corolario 3.3.2 Sea Hun clase de conceptos consistentes de XaY. Sea L un algoritmo tal que para todo c∈ H y para todo conjunto de entrenamiento S devuelve un concepto hip´otesis consistente hS:b RS(hS)=0. Entonces, ∀ϵ, δ ∈ (0,1), se tiene con probabilidad al menos 1−δ RD(hS)≤1 mlog |H| δ. En consecuencia a estos resultados, en el caso consistente toda clase de hip´otesis finita es aprendible PAC con complejidad de la muestra mH(ϵ, δ)≤1 ϵlog |H| δ Hay clases de conceptos infinitas que tambi´en son aprendibles PAC. M´as adelante mostraremos que lo que determina si una clase es aprendible no es su finitud, sino la dimensi´on VC. 3.3. Clases aprendible PAC 29 3.3.2. Aprendizaje PAC agn´ostico para clasificaci´on binaria Abordaremos ahora el caso en el que el concepto objetivo es una variable aleatoria sobre X, este es el caso en el que el conjunto de entrenamiento no es consistente, ya que la misma instancia xpuede tener distintas etiquetas escogidas seg´un una probabilidad P(y|x), y por lo tanto no se cumple el supuesto de realizaci´on (no existe una clase hip´otesis que anule el error real). Definici´on 3.3.3 (Aprendizaje PAC agn´ostico para clasificaci´on binaria) Una clase de conceptos Hes aprendible PAC agn´ostico si existe una funci´on mH: (0,1)2→Ny un algoritmo de aprendizaje tal que ∀ϵ, δ ∈(0,1), para toda distribuci´on de probabilidad Dsobre Z=X× {0,1}, si se ejecuta el algoritmo sobre m≥mH(ϵ, δ)ejemplos i.i.d. por D, entonces el algoritmo devuelve un concepto hip´otesis htal que, con probabilidad al menos 1−δse tiene que RD(h)≤minh′∈HRD(h′) + ϵ. Que una clase de hip´otesis Hsea aprendible PAC agn´ostico no garantiza que el error pueda hacerse arbitrariamente peque˜no con suficientes ejemplos de entrenamiento como en el caso determinista, pero s´ı garantiza que el error sea relativamente peque˜no respecto al mejor predictor que se puede obtener. 3.3.3. Aprendizaje PAC agn´ostico generalizado Hasta ahora solo hemos considerado problemas de clasificaci´on binaria. Trataremos ahora el caso general que comprende tambi´en problemas como clasificaci´on multiclase y regresi´on. La diferencia fundamental respecto a las dos anteriores definiciones es la consideraci´on de funciones p´erdida. Definici´on 3.3.4 (Aprendizaje PAC agn´ostico) Una clase de conceptos Hes aprendible PAC agn´ostico con respecto a un conjunto Zy una funci´on de p´erdida l:H×Z→R+si existe una funci´on mH: (0,1)2→Ny un algoritmo de aprendizaje tal que ∀ϵ, δ ∈(0,1), para toda distribuci´on de probabilidad D sobre Z, si se ejecuta el algoritmo sobre m≥mH(ϵ, δ)ejemplos i.i.d. por D, entonces el algoritmo devuelve un concepto hip´otesis htal que, con probabilidad al menos 1−δse tiene que RD(h)≤minh′∈HRD(h′) + ϵ, donde RD(h) = E z∼D l(h, z) 30 Cap´ıtulo 3. Aprendizaje PAC 3.4. Convergencia uniforme En la secci´on anterior se mostr´o que, bajo el supuesto de realizaci´on, toda clase de concepto finita es aprendible PAC. Ahora desarrollamos una herramienta, la convergencia uniforme, y la aplicamos para mostrar que toda clase finita es aprendible PAC agn´ostico siempre que el rango de la funci´on de p´erdida est´e acotado. Recordemos que, en el marco ERM, se busca el concepto hip´otesis h∈ H que minimiza el riego emp´ırico sobre el conjunto de entrenamiento Scon la esperanza de que as´ı se minimize el riesgo real sobre la distribuci´on completa D. Esto sucede si el riesgo emp´ırico de los conceptos pertenecientes a la clase de hip´otesis es una buena aproximaci´on del riesgo real. Procedamos a formalizar esta idea. Definici´on 3.4.1 Se dice que un conjunto de entrenamiento Ses ϵrepresen- tativo respecto a un dominio Z, clase de hip´otesis H, funci´on de p´erdida ly distribuci´on Dsi ∀h∈ H,|b RS(h)−RD(h)| ≤ ϵ Los conjuntos de entrenamientos que satisfacen esta condici´on garantizan que los estimadores obtenidos por un algoritmo ERM son una buena hip´otesis, ya que al minimizar el riesgo emp´ırico sobre estos conjuntos tambi´en se minimiza el riesgo real. Lema 3.4.1 Sea Sun conjunto de entrenamiento ϵ/2-representativo. Entonces toda salida de un algoritmo ERM sobre Hque toma como entrada S, i.e. todo hS=argminh∈H b RS(h), verifica: RD(hS)≤m´ın h∈H RD(h) + ϵ Demostraci´ on: Para todo h∈ H RD(hS)≤b RS(hS) + ϵ 2≤b RS(h) + ϵ 2≤RD(h) + ϵ 2+ϵ 2≤RD(h) + ϵ 2 Debido a este lema, para garantizar que Hes aprendible PAC agn´ostico, basta con que al escoger Sseg´un D, el conjunto de entrenamiento sea ϵrepresentativo con probabilidad al menos 1 −δ. 3.5. Las clases finitas son aprendibles PAC agn´ostico 31 Definici´on 3.4.2 (Convergencia Uniforme) Una clase de hip´otesis Htiene la propiedad de convergencia uniforme (respecto a un dominio Zy una funci´on p´erdida l) si existe una funci´on mUC H: (0,1)2→Nque para cada par ϵ, δ ∈(0,1) y para cada distribuci´on de probabilidad Dsobre Z, si S⊆Zes un subconjunto de m≥mUC H(ϵ, δ)ejemplos escogidos i.i.d. seg´un D, entonces Ses ϵ-representativo con probabilidad al menos 1−δ. Al igual que mHdeterminaba el tama˜no m´ınimo de Spara que un algoritmo devuelva probablemente un concepto hip´otesis aproximado, la funci´on mUC H mide el tama˜no m´ınimo de Spara que sea probablemente ϵ-representativo. El siguiente corolario se sigue directamente del Lema 3.4.1. Corolario 3.4.2 Si una clase Htiene la propiedad de convergencia uniforme con funci´on mUC H, entonces la clase es aprendible PAC agn´ostico con complejidad de muestra mH(ϵ, δ)≤mUC H(ϵ 2, δ). Por lo tanto, el paradigma ERMHes un aprendiz PAC agn´ostico para H. 3.5. Las clases finitas son aprendibles PAC agn´ostico En esta secci´on demostraremos que todas las clases de conceptos finitas tienen la propiedad de convergencia uniforme y por lo tanto son aprendibles PAC agn´ostico, siempre que la funci´on de p´erdida considerada tenga rango acotado. Teorema 3.5.1 Sea Huna clase de hip´otesis finita, sea Zel dominio, y l: H × Z→[0,1] una funci´on de p´erdida. Entonces, Htiene la propiedad de convergencia uniforme con mUC H(ϵ, δ)≤log(2|H|/δ) 2ϵ2 Adem´as, la clase es aprendible PAC agn´ostico con complejidad de muestra mH(ϵ, δ)≤mUC H(ϵ 2, δ)≤2log(|H|/δ) ϵ2 Para la demostraci´on del teorema se utilizar´a el siguiente lema. 32 Cap´ıtulo 3. Aprendizaje PAC Lema 3.5.2 (desigualdad de Hoeffding): Sean θ1, . . . , θmuna secuencia de variables aleatorias i.i.d tales que ∀iE(θi) = µyP[a≤θi≤b]=1. Entonces ∀ϵ > 0se tiene que P" 1 m m X i=1 θi−µ> ϵ#≤2exp −2mϵ2 (b−a)2 Demostraci´ on: Hay que encontrar mtal que para toda distribuci´on de probabilidad Dsobre Z, al tomar una muestra S={z1, . . . , zm}de melementos i.i.d. seg´un Dse tenga con probabilidad al menos 1 −δque ∀h∈ H,|b RS(h)−RD(h)| ≤ ϵ. Tenemos Dm({S:∀h∈ H,|b RS(h)−RD(h)| ≤ ϵ})≥1−δ ⇐⇒ Dm({S:∃h∈ H,|b RS(h)−RD(h)|> ϵ})≤δ Como {S:∃h∈ H,|b RS(h)−RD(h)|> ϵ}=[ h∈H{S:|b RS(h)−RD(h)|> ϵ} Se tiene entonces que Dm({S:∃h∈ H,|b RS(h)−RD(h)|> ϵ})≤X h∈H Dm({S:|b RS(h)−RD(h)|> ϵ}) Por la proposici´on 3.2.1 se tiene que ES∼Dmb RS(h) = RD(h) y tanto |b RS(h)− RD(h)|es la desviaci´on del error emp´ırico a su valor esperado. Sea la variable aleatoria θi=l(h, zi) para hfijo. Como zise han tomado i.i.d., θitambi´en son i.i.d. y se tiene que b RS(h) = 1 mPm i=1 l(h, zi) = 1 mPm i=1 θi yRD(h) = µ. Adem´as como rango(l) = [0,1] entonces θi∈[0,1]. Por lo tanto con la desigualad de Hoeffding {S:|b RS(h)−RD(h)|> ϵ}=P" 1 m m X i=1 θi−µ> ϵ#≤2exp −2mϵ2 Combinado con las inecuaciones anteriores llegamos a Dm({S:∃h∈ H,|b RS(h)−RD(h)|> ϵ}) ≤X h∈H 2exp −2mϵ2= 2|H|exp(−2mϵ2). 3.5. Las clases finitas son aprendibles PAC agn´ostico 33 Luego si tomamos m≥ log 2|H| δ ϵ2 entonces tenemos que Dm({S:∃h∈ H,|b RS(h)−RD(h)|> ϵ})< δ y en consecuencia las clases finitas tienen la propiedad de convergencia uniforme. Por ´ultimo, utilizando el corolario 3.4.2, tenemos que, adem´as, la clase de hip´otesis finita Hes aprendible PAC Agn´ostico con complejidad de muestra: mH(ϵ, δ)≤mUC H(ϵ 2, δ)≤2log(|H|/δ) ϵ2. 2 La propiedad de convergencia uniforme de una clase de hip´otesis implica que si el conjunto de entrenamiento es suficientemente grande, entonces los errores emp´ıricos de las hip´otesis de la clase son similares a los errores reales. Utilizando algoritmos ERM, la convergencia uniforme basta para asegurar el aprendizaje PAC agn´ostico en clases de hip´otesis finitas. Se puede encontrar informaci´on mas detallada en la referencia [5]. Con este resultado finalizamos el cap´ıtulo de introducci´on al Aprendizaje PAC. Cap´ıtulo 4 El Teorema Fundamental del Aprendizaje Estad´ıstico Hasta ahora hemos definido las ideas b´asicas del aprendizaje estad´ıstico, el concepto de aprendizaje PAC y la propiedad de convergencia uniforme. Recordemos que una clase de funciones Hes aprendible PAC si dado una muestra de entrenamiento finita con elementos escogidos i.i.d. seg´un una distribuci´on de probabilidad D, se puede encontrar un concepto hip´otesis hque minimize el error real respecto al mejor estimador en H. En el marco de aprendizaje estad´ıstico ERM, los algoritmos tratan de minimizar el error emp´ırico sobre el conjunto de entrenamiento con la intenci´on de minimizar tambi´en el error real sobre la distribuci´on. Una vez presentadas estas ideas surge de manera natural la pregunta de qu´e clases de conceptos son aprendibles PAC y qu´e las caracteriza. Ya demostramos que todas las clases de hip´otesis finitas son aprendibles, mediante un algoritmo ERM, si tenemos una muestra de O2log(|H|/δ) ϵ2ejemplos, pero de momento no mostramos nada sobre las que son infinitas. El resultado m´as importante sobre esta cuesti´on nos indica que las clases aprendibles no se caracterizan por su tama˜no, sino por su dimensi´on Vapnik-Chervonenkis. En este cap´ıtulo estableceremos en primer lugar el teorema No-Free- Lunch (NFL) [4], que establece que no existe un algoritmo de aprendizaje universal, es decir, un algoritmo que pueda aprender bien cualquier clase de problema, sea cual sea la distribuci´on de probabilidad de los datos. En tareas de clasificaci´on, para cada algoritmo de aprendizaje, siempre existir´a una distribuci´on de probabilidad D(que genera los datos entrada-salida) en la que falle. 35 36 Cap´ıtulo 4. El Teorema Fundamental del Aprendizaje Estad´ıstico Existen numerosas versiones de este teorema, la que se presenta en este trabajo proviene de [9]. A continuaci´on trataremos la dimensi´on VC en el contexto de aprendizaje PAC y su relaci´on con algoritmos de aprendizaje, finalizando con el resultado conocido como Teorema Fundamental del Aprendizaje Estad´ıstico (FTSL) que relaciona la aprendibilidad de una clase de hip´otesis con su dimensi´on VC y en un sentido muy fuerte: una clase es aprendible PAC si y solo si su dimensi´on VC es finita. 4.1. Teorema No-Free-Lunch Teorema 4.1.1 (No-Free-Lunch) Sea Lun algoritmo de aprendizaje ERM de clasificaci´on binaria para la funci´on p´erdida l0,1(h, (x, y)) = I(h(x) = y), con Ifunci´on indicatriz, sobre un dominio X. Sea m∈N,m≤ |X|/2. Entonces existe una distribuci´on de probabilidad Dsobre X×{0,1}tal que: •Existe un concepto f:X→ {0,1}con RD(f) = 0. •Con probabilidad al menos 1/7sobre un conjunto de entrenamiento S∼ Dmse tiene que RD(L(S)) ≥1/8. El teorema NFL indica que ning´un algoritmo de aprendizaje puede ser exitoso para todos los problemas. La formalizaci´on de esta idea es que, para todo algoritmo de aprendizaje, existe una distribuci´on de probabilidad para la cual el algoritmo falla. Es decir que existen ϵ, δ para los cuales el algoritmo no puede devolver con probabilidad 1 −δuna hip´otesis que acote el error seg´un ϵ, y esto se cumple aun cuando otro algoritmo s´ı es exitoso. Un ejemplo trivial es el de un algoritmo ERM sobre la clase de hip´otesis H={f}, y mas generalmente, uno con una clase de hip´otesis que contenga a fy con un conjunto de entrenamiento de tama˜no m≥8log(7|H|/6) (ver teorema 3.3.1). Antes de demostrar el teorema NFL consideremos el siguiente lema. Lema 4.1.2 Sea Zuna variable aleatoria que toma valores en [0,1] tal que E[Z] = µ. Entonces, para a∈(0,1) se tiene que P[Z > 1−a]≥µ−(1 −a) a Esto tambi´en implica que para todo a∈(0,1) P[Z > a]≥µ−a 1−a≥µ−a 4.1. Teorema No-Free-Lunch 37 Demostraci´ on: Sea Y= 1−Z, que es una variable aleatoria no negativa con E[Y]=1−µ. Aplicando la desigualdad de Markov se tiene: P[Z≤1−a]≥P[1 −Z≥1−a] = P[Y≥a]≤E[Y] a=1−µ a Y por lo tanto P[Z > 1−a]≥1−1−µ a=a+µ−1 a. Para la segunda inecuaci´on, basta considerar 1 −aen lugar de a.2 Demostremos ahora el teorema NFL 4.1.1: Demostraci´ on: Sea C⊆Xun subconjunto del dominio con tama˜no 2my sean f1, . . . , fTcon T= 22mtodas las posibles funciones de Ca{0,1}. Para cada i= 1, . . . , T sea Dila distribuci´on sobre Xdefinida como Di({(x, y)}) = (1/|C|si y=fi(x) 0 en otro caso que es una distribuci´on uniforme sobre los pares (x, y) tal que y=fi(x) y se cumple RDi(fi) = E (x,y)∼Di l0,1(fi,(x, y)) = 0. Sea Lun algoritmo de aprendizaje que recibe de entrada un conjunto Sde m ejemplos de C×{0,1}y devuelve como salida un concepto L(S) : C→ {0,1}. Denotamos por S1, . . . , Sklas k= (2m)mposibles secuencias de mejemplos de C. Para Sj= (x1, . . . , xm) denotamos por Si j= ((x1, fi(x1)),...,(xm, fi(xm))) la secuencia de los pares de instancias en Sjcon su etiqueta seg´un fi. Considerando la distribuci´on Dilos posibles conjuntos de entrenamiento que Lpuede recibir son Si 1, . . . , Si kcon la misma probabilidad de ser escogidos. Por lo tanto E S∼Dm i [RDi(L(S))] = 1 k k X j=1 RDi(L(Si j)) (4.1) Utilizando que el m´aximo de una muestra es mayor que su media, y que la media es, a su vez, mayor que su m´ınimo, tenemos que 44 Cap´ıtulo 4. El Teorema Fundamental del Aprendizaje Estad´ıstico Demostraci´ on: Sea a(m) = 4 + plog(π(X,H)(2m)) δ√2m. Demostraremos que E S∼Dmsup h∈H |RD(h)−b RS(h)|≤a(m)·δ(4.6) La desigualdad de Markov establece que si Xes una variable aleatoria y a > 0 , entonces P[|X| ≥ a]≤E[|X|] a. Como suph∈H |RD(h)−b RS(h)| ≥ 0 es una variable aleatoria sobre Dm, utilizando la desigualdad de Markov y la inecuaci´on (4.6), se llega a Phsuph∈H |RD(h)−b RS(h)| ≥ a(m)i≤ ES∼Dmhsuph∈H |RD(h)−b RS(h)|i a(m)≤δ y por lo tanto Ph|RD(h)−b RS(h)| ≤ a(m)i≤1−δ lo que finaliza la demostraci´on. Probemos entonces la ecuaci´on (4.6). E S∼Dmsup h∈H |RD(h)−b RS(h)|=E S∼Dmsup h∈H |E S′∼Dm[b RS′(h)] −b RS(h)| Por la desigualdad abs(E[X]) ≤E[abs(X)] se tiene E S′∼Dm[b RS′(h)−b RS(h)]≤E S′∼Dmh|b RS′(h)−b RS(h)|i y como el supremo del valor esperado es menor que el valor esperado del supremo, sup h∈H E S′∼Dmh|b RS′(h)−b RS(h)|i≤E S′∼Dmsup h∈H |b RS′(h)−b RS(h)| 4.4. El Teorema Fundamental del Aprendizaje Estad´ıstico 45 Por lo tanto E S∼Dmsup h∈H |RD(h)−b RS(h)|≤E S′,S∼Dmsup h∈H |b RS′(h)−b RS(h)| =E S′,S∼Dm"sup h∈H 1 m| m X i=1 (l(h, z′ i)−l(h, zi))|#. (4.7) En el ´ultimo valor esperado los vectores aleatorios z′yzson los pertenecientes a los conjuntos S′yS, respectivamente, que se escogen i.i.d. seg´un D. Como se escogen i.i.d., si se sustituye zipor z′ ino cambiar´ıa nada, por lo que (l(h, z′ i)−l(h, zi)) y −(l(h, z′ i)−l(h, zi)) son intercambiables para cada i. As´ı que para cada σ∈ {±1}mla ecuaci´on (4.7) equivale a E S′,S∼Dm[sup h∈H 1 m| m X i=1 σi(l(h, z′ i)−l(h, zi))|] Esto tambi´en sucede si cada σise escoge seg´un una distribuci´on U±uniforme sobre {±1}. Luego (4.7) es igual a E σ∼Um ± E S′,S∼Dm[sup h∈H 1 m| m X i=1 σi(l(h, z′ i)−l(h, zi))|] Fijados SyS′consideremos C=S∪S′. En este caso podemos considerar el supremo sobre la restricci´on de HaC E σ∼Um ± [sup h∈H 1 m| m X i=1 σi(l(h, z′ i)−l(h, zi))|] = E σ∼Um ± [ sup h∈HC 1 m| m X i=1 σi(l(h, z′ i)−l(h, zi))|] Fijado h∈ HC, denotemos θh=1 m m X i=1 σi(l(h, z′ i)−l(h, zi)). Como zyz′ provienen i.i.d. de la misma distribuci´on, sus respectivos valores esperados son iguales, por lo que se tiene que E[θh] = 0. Como θhes la media de variables independientes que toman valores en [−1,1], aplicando la desigualdad de Hoeffding del Lema 3.5.2 se tiene que para cada ρ > 0, P[|θh|> ρ]≤2 exp(−2mρ2). 46 Cap´ıtulo 4. El Teorema Fundamental del Aprendizaje Estad´ıstico y tomando el m´aximo en HC P[m´ax HC|θh|> ρ]≤2|HC|exp(−2mρ2). Aplicando el lema .0.6 del ap´endice se obtiene E[m´ax HC|θh|]≤4 + plog(|HC|) √2m. Estos resultados combinados con la definici´on de π(X,H)(n) muestran que (4.6) es cierto. 2 Tras probar el teorema 4.4.3 ya estamos en condiciones de demostrar la ´ultima parte del Teorema Fundamental del Aprendizaje Estad´ıstico. Para ello hay que probar que si la dimensi´on VC de un espacio de aprendizaje es finita, entonces la clase de hip´otesis tiene la propiedad de convergencia uniforme. Demostraci´ on: (4) ⇒(1). Para probar la convergencia uniforme daremos una cota de la funci´on mUC H(ϵ, δ) que depende de d=dimV C(X, H). Por el lema de Sauer 4.4.2 se tiene que para m > d, π(x,H)(2m)≤(2em/d)d. Esto, junto con el teorema 4.4.3 anterior muestra que, con probabilidad al menos 1−δ, se tiene |RD(h)−b RS(h)| ≤ 4 + pdlog(2em/d) δ√2m Por simplicidad, podemos asumir que pdlog(2em/d)≥4, ya que si es menor tomando un tama˜no m≥32/(δϵ)2tenemos |RD(h)−b RS(h)|est´a acotado por ϵ. Por lo tanto, |RD(h)−b RS(h)| ≤ 1 δr2dlog(2em/d) m y para asegurar que esto sea menor a ϵtomamos m≥2dlog(m) (δϵ)2+2dlog(2e/d) (δϵ)2 Mediante operaciones algebraicas expuestas en el Ap´endice .0.5 podemos demostrar que una condici´on suficiente para que se cumpla la anterior desigualdad es 4.4. El Teorema Fundamental del Aprendizaje Estad´ıstico 47 m≥42d (ϵδ)2log 2d (ϵδ)2+4dlog(2e/d) (ϵδ)2 Luego para satisfacer la propiedad de convergencia uniforme se puede tomar mUC H(ϵ, δ)≤416d (ϵδ)2log 16d (ϵδ)2+16dlog(2e/d) (ϵδ)2 Y con esto finaliza la demostraci´on del teorema fundamental del aprendizaje estad´ıstico. 2 Ap´endice Lema .0.4 (Ap´endice A.1) Sea a > 0. Entonces x≥2alog(a)⇒x≥ alog(x). Demostraci´ on: Para a∈(0,√e] la desigualdad siempre se cumple y la demostraci´on es trivial. Supongamos que a > √e. Consideremos la funci´on f(x) = x−alog(x), que tiene derivada f′(x) = 1 −a/x, que es positivo si x > a y por lo tanto la funci´on es creciente. Se tiene que 2alog(a)> a si a > √e, y evaluando la funci´on f(2alog(a)) = 2alog(a)−alog(2alog(a)) = 2alog(a)−alog(a)−alog(2log(a)) =alog(a)−alog(2log(a)) =alog a 2log(a)(8) C´omo a > 2log(a)∀a > 0 se tiene el resultado. 2 Lema .0.5 (Ap´endice A.2) Sea a≥1yb > 0. Entonces x≥4alog(2a) + 2b⇒x≥alog(x) + b Demostraci´ on: Como a≥1 entonces claramente x≥2b. Por otro lado, como b > 0, se tiene x≥4alog(2a), y aplicando el Lema .0.4 tenemos x≥2alog(x). Sumando las dos desigualdades 2x≥2alog(x)+2b.2 Lema .0.6 (Ap´endice A.3) Sea Xuna variable aleatoria y x′∈Run escalar. Si existen a > 0yb≥etales que ∀t≥0se cumple P[|X−x′|> t]≤2be−t2/a2, entonces E[|X−x′|]≤a(2 + plog(b)). 49 50 Cap´ıtulo 4. El Teorema Fundamental del Aprendizaje Estad´ıstico Demostraci´ on: Para i= 1,2, . . . denotamos ti=a(i+plog(b)). ties mon´otonamente creciente, por lo que E[|X−x′|]≤aplog(b) + ∞ X i=1 tiP[|X−x′|> ti−1] Desarrollando el sumatorio y usando las condiciones del lema se tiene ∞ X i=1 tiP[|X−x′|> ti−1]≤2ab ∞ X i=1 (i+plog(b))e−(i−1+√log(b))2 ≤2ab Z∞ 1+√log(b) xe−(x−1)2dx = 2ab Z∞ √log(b) (y+ 1)e−y2dy ≤4ab Z∞ √log(b) ye−y2dy = 2ab h−e−y2i∞ √log(b) = 2ab/b = 2a Combinando este resultado con la primera desigualdad completamos la prueba. 2 Lema .0.7 (Ap´endice A.4) Sean m, d ∈Ntales que d≤m−2. Entonces. d X k=0 m k≤em dd. Demostraci´ on: Por inducci´on. Para d= 1 se tiene 1+m≤em que es cierto. Supongamos ahora que es cierto para dy prob´emoslo para d+ 1. Por hip´otesis de inducci´on se tiene d+1 X k=0 m k≤em dd+m d+ 1 =em dd· 1 + d emdm(m−1)(m−2) ···(m−d) (d+ 1)d!! ≤em dd· 1 + d edm−d (d+ 1)d!! 4.4. El Teorema Fundamental del Aprendizaje Estad´ıstico 51 La f´ormula de Stirling est´a dada por d! = √2πd d ed e1 12d−1 360d3+1 1260d5−··· ≥√2πd d ed y aplic´andola a la desigualdad anterior ≤em dd· 1 + d edm−d (d+ 1)√2πd(d/e)d! =em dd·1 + m−d (d+ 1)√2πd =em dd·d+ 1 + (m−d)/√2πd d+ 1 ≤em dd·d+ 1 + (m−d)/2 d+ 1 =em dd·d/2 + 1 + m/2 d+ 1 ≤em dd·m d+ 1 Se usado que d≤m−2 en la ´ultima desigualdad. Continuamos por el otro lado em d+ 1d+1 =em dd·em d+ 1 ·d d+ 1d =em dd·em d+ 1 ·1 (1 + 1/d)d ≥em dd·em d+ 1 ·1 e =em dd·m d+ 1. Lo que finaliza la prueba 2 Conclusiones Para cumplir el objetivo de presentar y comprender el concepto de la dimen- si´on de Vapnik-Chervonenkis, a lo largo de esta memoria se han desarrollado las bases de la teor´ıa del aprendizaje estad´ıstico, fundamentado en el principio de minimizaci´on del riesgo emp´ırico. Cabe destacar la importancia de esto en la ciencia de los datos, ya que trata el problema de inferencia estad´ıstica de encontrar una funci´on predictiva basada en un conjunto de datos, y se ha aplicado con ´exito en problemas tecnol´ogicos actuales como la visi´on artificial, el reconocimiento del habla o el diagn´ostico de enfermedades. El resultado m´as relevante expuesto en este trabajo es el del Teorema Fundamental del Aprendizaje Estad´ıstico, que muestra claramente la importancia de la dimensi´on VC en los modelos de clasificaci´on binaria. La colecci´on de ejemplos de su c´alculo aporta una mayor comprensi´on sobre como act´ua la dimensi´on VC sobre distintas familias de funciones. En conclusi´on, considero que este trabajo aporta una base de conocimiento fundamental de la teor´ıa de aprendizaje estad´ıstico y explica el papel que juega la dimensi´on VC en la ciencia de datos. Trabajo Futuro Existen numerosos aspectos de la dimensi´on VC que se podr´ıan desarrollar m´as all´a de lo expuesto en esta memoria: •C´alculo de la dimensi´on VC de las clases de funciones devueltas por algoritmos com´unmente utilizados la ciencia de los datos como redes neuronales y ´arboles de decisi´on. 53