Fundamentos de aprendizaje automático

Universidad del Valle de Guatemala

Profesor Pedro AguilarNotas de clase de Rodrigo Leonardo

1

Contents

1 Probabilidad 41.1 Espacios muestrales, eventos e independencias . . . . . . . . . . . . . 41.2 Valor esperado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Cota de la unión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Función caracteŕıstica . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Varianza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.6 Teorema del ĺımite central . . . . . . . . . . . . . . . . . . . . . . . . 61.7 Distribuciones de probabilidad . . . . . . . . . . . . . . . . . . . . . 61.8 Regla de Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Modelo Formal de Aprendizaje 82.1 Minimización de riesgo emṕırico (ERM) . . . . . . . . . . . . . . . . 92.2 ERM con sesgo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Clase de hipótesis finitas . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Aprendizaje PAC 113.1 Complejidad de la muestra . . . . . . . . . . . . . . . . . . . . . . . 123.2 Aprendizaje PAC agnóstico . . . . . . . . . . . . . . . . . . . . . . . 123.3 Error emṕırico y real . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.4 Predictor óptimo de Bayes . . . . . . . . . . . . . . . . . . . . . . . . 123.5 Funciones de pérdida generalizadas . . . . . . . . . . . . . . . . . . . 13

4 Aprendizaje bajo convergencia uniforme 144.1 Clases de hipótesis finitas son PAC aprendibles . . . . . . . . . . . . 14

5 Predictores Lineales 175.1 Espacios mitad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.2 Perceptrón . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.3 Regresión lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.4 Regresión loǵıstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

6 VC dimension 196.1 Teorema Fundamental del aprendizaje PAC . . . . . . . . . . . . . . 206.2 Función de crecimiento . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7 Aprendizaje no uniforme 217.1 Minimización estructural de riesgo . . . . . . . . . . . . . . . . . . . 217.2 Longitud de mı́nimo descripción . . . . . . . . . . . . . . . . . . . . 237.3 Longitud de mı́nima descripción (MDL) . . . . . . . . . . . . . . . . 25

8 Complejidad computacional de aprendizaje 25

2

9 Selección y validación de modelo 269.1 Validación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269.2 Cross validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3

1 Probabilidad

Definición 1.1. El resultado de lanzar una moneda al aire es una variable aleatoriaX. Al espacio de valores que toma la variable aleatoria le llamamos el espaciomuestral. En este caso, X = {0, 1}. Sobre S podemos definir una distribución deprobabilidad de forma que p(0) = p(1) = 1/2.

Para Z+, podemos definir p(i) = 6π2· 1i2, i ∈ S. En otros casos no podemos

definir una distribución de probabilidad. Por ejemplo si S = R, entonces se defineuna distribución de probabilidad, i.e.:

P(a < x < b) =∫ bap(x)dx (1)

Definición 1.2. La distribución de probabilidad cumulativa es:

F (a) =

∫ a−∞

p(x)dx = P(x < a) (2)

1.1 Espacios muestrales, eventos e independencias

Definición 1.3. Supongamos que lanzamos n veces una moneda, entonces tenemosvariables aleatorieas x1, . . . , xn. El espacio muestral está dado por X = {0, 1}n.Definimos un evento como un subconjunto del espacio muestral.

Definición 1.4. Sean A y B dos eventos. La ocurrencia de A y B se denota porA∩B. Definimos la probabilidad condicional de que ocurra A después de que ocurrael evento B. Denotado por:

P(A|B) = P(A ∩B)P(B)

(3)

Definición 1.5. Los eventos A y B son independientes si: P(A|B) = P(A), entoncesP(A)P(B) = P(A ∩B).

Definición 1.6. Dos variables aleatorias X, Y son independientes si para cua-lesquiera eventos A y B de valores de X y Y , respectivamente, A y B son indepen-dientes. Para una colección de variables aleatorieas x1, . . . , xn independientes:

P(x1 ∈ A1, . . . , xn ∈ An) =n∏i=1

P(xi ∈ Ai) (4)

4

1.2 Valor esperado

Definición 1.7. Definimos E(X) =∑xp(x) o E(X) =

∫∞−∞ xp(x)dx como el valor

esperado para una variable aleatoria X. Nótese que:

E(X + Y ) =∫S

(x+ y)p(x, y)dΣ

=

∫Sxp(x, y)dΣ +

∫Syp(x, y)dΣ

= E(X) + E(Y )

1.3 Cota de la unión

Nota 1.1. Consideremos los eventos A1, . . . , An, entonces:

P(n⋃i=1

Ai) =n∑i=1

P(Ai)−n∑

i,j=1

P(Ai ∩Aj)± · · · ± P(⋂{Ai})

≤n∑i=1

P(Ai)

1.4 Función caracteŕıstica

Definición 1.8. Consideremos S y A ⊆ S, el espacio muestral y un evento. Defin-imos a la función caracteŕıstica:

χA(x) =

{1 x ∈ A0 x /∈ A

(5)

Supongamos que S = {1, . . . , n}. Por ejemplo, consideremos Σ = {1, . . . , n} y A esel subconjunto de puntos fijos bajo σ ∈ A(Σ) = Sn. El tamaño de A es Σni=1χA(i),entonces:

E(n∑i=1

χA(i)) =n∑i=1

E(χA(i))

= nE(χA(1)) =n(n− 1)!

n!= 1

1.5 Varianza

Definición 1.9. La varianza de una variable X se denota por σ2 o V(X), y se definecomo:

σ2 = E((x− E(x))2) (6)

Definición 1.10. Definimos la desviación estándar σ =√V(X).

5

Propiedad 1.1. Podemos probar que:

σ2 = E(X − E(X))2 = E(X2)− 2E(XE(X)) + (E(X))2

= E(X2)− 2E2(X) + E2(X) = E(X2)− E2(X)

Propiedad 1.2. La varianza de la suma de variables aleatorias:

V(X + Y ) = E(X + Y )2 − (E(X + Y ))2

= E(X2) + 2E(XY ) + E(Y 2)− E2(X)− 2E(X)E(Y )− E2(Y )= V(X) + V(Y ) + 2E(XY )− 2E(X)E(Y )

Propiedad 1.3. Si X y Y son independientes, V(X + Y ) = V(X) + V(Y ). SiX1, . . . , Xn son v.a. independientes:

V(n∑i=1

Xi) =

n∑i=1

V(Xi) (7)

1.6 Teorema del ĺımite central

Ejemplo 1.1. Supongamos que X1, . . . , Xn son v.a. idéntica e independientementedistribuidas (iid). Sean E(Xi) = 12 , V(Xi) =

12(0−

12)

2 + 12(1−12)

2 = 14 , donde:

Xi =

{0 con probabilidad 121 con probabilidad 12

(8)

Sea S = X1 + · · · + Xn =⇒ E(S) = n2 , V =n4 y σ =

√n2 . Nótese que

σE(S) → 0

cuando n→∞. Si las Xi están iid con desviación estándar σ, entonces S =∑n

i=1 χitiene desviación estándar

√nσ. Por lo tanto, 1√

n

∑ni=1 χi tiene distribución σ.

Teorema 1.1 (Ĺımite central). Sean X1, . . . , Xn una colección de v.a. iid conE(X) = µ y V(Xi) = σ2, ∀i = 1, . . . , n. La distribución de:

1√n

(

n∑i=1

Xi − nµ)

converge a la distribución de una gaussiana con media 0 y varianza σ2, N(0, σ2).

1.7 Distribuciones de probabilidad

Definición 1.11. La distribución normal/gaussiana N(µ, σ) se define como:

p(x) =1√2πσ

e−(x−µ)2

2σ2 (9)

6

Nota 1.2. Note que: ∫Re−x

2dx =

√π (10)

Definición 1.12. Un experimento A,B con probabilidades p, 1−p respectivamente.Repetimos el experimento n veces y queremos la probabilidad de obtener A k veces:

B(n, p) =

(n

k

)pk(1− p)n−k (11)

La media es np y la varianza np(1− p).

Propiedad 1.4. El valor esperado de la distribución binomial es np. En efecto:

E(K) =n∑k=0

KBk(n, p) =

n∑k=0

Kn!

k!(n− k)!pk(1− p)n−k

= np

n∑k=0

(n− 1)!(k − 1)!((n− 1)− (k − 1))!

pk−1(1− p)(n−1)−(k−1)

= np

n∑k=1

(n− 1)!(k − 1)!((n− 1)− (k − 1))!

pk−1(1− p)(n−1)−(k−1)

= npn−1∑k=0

(n− 1)!k!((n− 1)!− k!)

pk(1− p)n−1−k = np

La varianza:

V(X) = p(1− p)2 + (1− p)(0− p)2 = p(1− p)2 + (1− p)p2

= (1− p)(p− p2 + p2) = p(1− p)

Entonces, V(K) = np(1− p).

Nota 1.3. La distribución normal cumple con:

P(µ± σ) = e−1/2√

2πσ=

1√2πeσ

(12)

Definición 1.13. Si en la distribución binomial considera a d = np, entonces sin >> k:

nk

k!(d

n)2(1− d

n)n ≈ d

k

k!e−d

Entonces la distribución de Poisson es:

Poisson(λ) =λke−λ

k!(13)

7

1.8 Regla de Bayes

Definición 1.14. La regla de Bayes relaciona la probabilidad condicional P(A|B)con P(B|A):

P(A|B) = P(A ∩B)P(B)

=P(B ∩A)P(A)

(14)

Se le conoce a P(A) como la probabilidad a priori y a P(A|B) como la probabilidada posteriori.

Ejemplo 1.2. Sea A el evento en el que un producto es defectuoso y B el eventoen el que una prueba dice que el producto es defectuoso. Supóngase que P(A) =0.001, P(B|A) = 0.99 y P(B|Ac) = 0.02. Entonces:

P(B) = P(B|A)P(A) + P(B|Ac)P(Ac)= P(B ∩A) + P(B ∩Ac)= 0.99 · 0.001 + 0.02 · (1− 0.001) = 0.02087

Finalmente:

P(A|B) = P(B|A)P(A)P(B)

= 0.0471

2 Modelo Formal de Aprendizaje

Nota 2.1. ¿Cuándo se necesita machine learning? Para replicar actividades querealizan humanos, tomando en cuenta la adaptabilidad del sistema y la capacidadsobrehumana en cuanto a memoria.

Nota 2.2. Tipos de aprendizaje:

1. Supervisado vs No supervisado: datos etiquetados para que el aprendiz entrenecon valores de verdad se conoce como aprendizaje supervisado. Si el aprendizrecibe datos con el objetivo de clasificarlos de acuerdo a caracteŕısticas innatas,se le conoce como aprendizaje no supervisado.

2. Aprendiz activo vs pasivo: un aprendiz activo interactúa con los datos en elentrenamiento

3. Ayuda del maestro: al aprendiz se le evalúa en un peor escenario para que,al momento de encontrar un maestro cualquiera, pueda adaptarse a mejorescondiciones.

4. Online vs protocolo de aprendizaje por lotes: velocidad de respuesta y necesi-dad de la misma. Algunos aprendices rinden mejor luego de aprender degrandes cantidades de información sin siquiera realizar una predicción.

8

En machine learning se hace énfasis en asumir lo menos posible acerca de los datoscon los que se trabajará.

Nota 2.3. Lo que conoce el aprendiz:

1. Dominio: un conjunto arbitrario X. Si x ∈ X es un ejemplo, X es el espaciode ejemplos.

2. Espacio de etiquetas: un conjunto finito Y .

3. Datos de entrenamiento: son ejemplos etiquedatos,

S = {(x1, y1), . . . , (xn, yn)} ⊂ X × Y, ninZ+

Lo que esperamos del aprendiz:

1. Predicción: h : X → Y , le llaman predictor, hipótesis o clasificador.

Un modelo de generación de datos:

1. Los datos en S se generan de la siguiente manera: sea D una distribución deprobabilidad definida en X que extrae datos aleatoriamente.

2. Se etiequeta según una función f (ambas desconocidas por el aprendiz). Se

genera (xi, yi) por XD−→ xi

f−→ yi.

Definición 2.1. La medida de éxito se define como el error del aprendiz, el cuales la probabilidad de que si se extrae algún xD ∼ X, h(x) 6= f(x). La medida deerror, conocido como una función de pérdida, es una probabilidad

LD,f (h) = D({x|h(x) 6= f(x)}) (15)

es el tamaño del evento de los ejemplos que no se clasifican correctamente, dado ladistribución.

Nota 2.4. Sea A ⊂ X y π(x) la función caracteŕıstica. Entonces A = {x ∈ χ 3π(x) = 1}.

Nota 2.5. A LD,f (h) se le conoce como el error de generalización, riesgo o errorverdadero de h.

2.1 Minimización de riesgo emṕırico (ERM)

Nota 2.6. Dado que el aprendiz no tiene acceso a D ni a f , si se obtienen ejemplos

S = {(x1, y1), . . . , (xm, ym)}, m ∈ Z+, con χD,f−−→ S.

Definición 2.2. El error de entrenamiento se define como:

LS(h) =∣∣{i ∈ {1, . . . ,m} : h(xi) 6= f(yi)}∣∣ (16)

9

Nota 2.7. A la definición anterior se le conoce como minimización de riesgo emṕırico(ERM).

Ejemplo 2.1. Sea:

h(x) =

{yi si ∃i 3 xi = x0 en otro caso

Entonces Ls(h) = 0. Si la distribución es uniforme, LD,f (h) = 1/2. Esto se llamaoverfitting o sobreajuste.

2.2 ERM con sesgo

Definición 2.3. Del conjunto de predictores {f : X → Y } definimos a H como laclase de hipótesis, h ∈ H un predictor tal que h : X → Y . Realizando ERM sobrela clase H:

ERMH ∈ arg minh∈H

LS(h)

2.3 Clase de hipótesis finitas

Nota 2.8. Vamos a demostrar que con estas clases se evita el sobreajuste y podemosacercarnos lo suficiente al clasificador real. Dada una clase de hipótesis H escoge-mos el predictor que minimiza el error de entrenamiento hs ∈ arg minh∈H LS(h) yconsideramos las siguientes hipótesis.

1. Hipótesis de realizabilidad: ∃h∗ ∈ H 3 LD,f (h∗) = 0. Esto implica queLS(h

∗) = 0 y hS ∈ ERMH , LS(hS) = 0.

2. Suposición de iid: los ejemplos en el conjunto de entrenamiento S están inde-pendiente e idénticamente distribuidos. Se denota por S ∼ Dm, donde D esla distribución dada.

Notemos que hay un riesgo en escoger elementos de S que no sean significativos deldominio.

Definición 2.4. Definimos δ como la probabilidad de extraer una muestra no rep-resentativa. Definimos el parámetro de confianza como 1− δ.

Definición 2.5. Si LD,f (hS) > �, el aprendiz falló. Si LD,f (hS) ≤ �, el aprendiztuvo éxito y se ha generado un predictor aproximadamente correcto.

Nota 2.9. Ahora proponemos una cota de la probabilidad de que el aprendizfalle. Extraemos m elementos del dominio: S|X = (x1, . . . , xm). Queremos aco-tar Dm({S|X : L(D,f)(hS) > �}). Sea HB el conjunto de malas hipótesis, i.e.

HB = {h ∈ H : L(D,f)(h) > �} (17)

10

Sea M = {S|X : ∃h ∈ HB, LS(h) = 0}, el conjunto de datos de prueba engañosos.Supongamos que tenemos una muestra S|X 3 LD,f (hS) > �, LS(hS) = 0 =⇒{S|X : L(D,f)(hS) > �} ⊆ M . Notemos que M =

⋃h∈HB{S|X : LS(h) = 0},

entonces:

Dm({S|X : L(D,f)(hS) > �}) ≤ Dm(M) = Dm(⋃

h∈HB

{S|X : L(h) = 0})

≤∑h∈HB

Dm({S|X : L(h) = 0})

Pero:

Dm({S|X : Ls(h) = 0}) =m∏i=1

D({xi|f(xi) = h(xi)})

=

m∏i=1

(1− LD,f (h)) =∑m

m∏i=1

(1− �) = (1− �)m ≤ e−�m

Finalmente,

Dm({S|X : L(D,f)(hS) > �}) ≤∑h∈HB

e−�m

= |HB| e−�m

Corolario 2.1. Sea H una clase de hipótesis finita. Sea δ ∈ (0, 1), � > 0 y m ∈Z+ 3 m ≥ ln(|H|/δ)� . Entonces para una función de clasificación f , una distribuciónD, con la condición de realizabilidad y con probabilidad de al menos 1 − δ en laelección de la muestra iid de tamaño m, tenemos que para cada hipótesis ERMH , hS

L(D,f)(hS) ≤ �

Se dice que el proceso de ERM es probablemente aproximado correcto (PAC).

3 Aprendizaje PAC

Definición 3.1. Una clase de hipótesis H es PAC aprendible si existe una funciónmH : (0, 1)

2 → N y un algoritmo de aprendizaje con la siguiente propiedad. Paratodo �, δ ∈ (0, 1), para cada distribución D y función de clasificación f : X → {0, 1}.Si se satisface realizabilidad, entonces si para algúnm ≥ mH datos de entrenamiento,el algoritmo produce la hipótesis h tal que L(D,f)(h) < �, con probabilidad 1 − δ(sobre la elección de S). Se hacen dos aproximaciones:

1. �: parámetro de precisión, controla el error de la hipótesis.

2. δ: parámetro de confianza, probabilidad de que la hipótesis alcance dicho error.

11

3.1 Complejidad de la muestra

Definición 3.2. La complejidad de la muestra se define como mH : (0, 1)2 → N.

Nota 3.1. mH es la función mı́nima dado H, � y δ. Además, mH es el mı́nimoentero para el cual H es PAC aprendible.

Nota 3.2. Cada clase de hipótesis finita es PAC aprendible con complejidad de lamuestra:

mH(�, δ) ≤ln(|H|/δ

)�

Entonces se pueden generalizar los modelos de aprendizaje:

1. Relajando la hipótesis de realizabilidad.

2. Clasificación binaria.

3.2 Aprendizaje PAC agnóstico

Suponemos que D es una distribución sobre X × Y sobre el dominio y las etique-tas. Podemos pensarlo como una distribución DX que extrae datos del dominio yD((x, y)|x) es una distribución para las etiquedas para cada punto x.

3.3 Error emṕırico y real

Nota 3.3. Extraemos datos de entrenamiento según una distribuciónD sobreX×Y .Entonces podemos medir la probabilidad de que una hipótesis falle como:

LD(h) = D({(x, y) : h(x) 6= y}) = P(x,y)∼D(h(x) 6= y) (18)

Definición 3.3. El error emṕırico lo definimos como:

LS(h) =

∣∣{i ∈ {1, . . . ,m} : h(xi) 6= yi∣∣m

(19)

Con S = {(x1, y1), . . . , (xm, ym)}.

Nota 3.4. Nosotros queremos una hipótesis h ∈ H que minimice el error verdaderoprobablemente aproximadamente.

3.4 Predictor óptimo de Bayes

Definición 3.4. Dado una distribución D sobre χ× {0, 1}, definimos el predictor:

fD(x) =

{1 si P(y = 1|x) ≥ 120 si P(y = 0|x) < 12

(20)

fD es óptimo en el sentido de que LD(fD) ≤ LD(g), ∀g : X → Y .

12

Definición 3.5 (Aprendizaje PAC agnóstico). Una clase de hipótesis H es PACagóstica si ∃mH : (0, 1)2 → Z+ y un algoritmo de aprendizaje que satisface que∀�, δ ∈ (0, 1) y cada distribución D sobre X ×Y si tomamos m > mH(�, δ) ejemplosde entrenamiento iid, entonces el resultado h del algoritmo de entrenamiento es talque:

LD(h) < infh′∈H{Lp(h′)}+ � (21)

con probabilidad 1− δ.

Nota 3.5. 1. La clasificación multiclase tiene a X como dominio y a Y comoconjunto discreto.

2. La regresión tiene a X como dominio y a Y como conjunto continuo de formaque

LD(h) = E(x,y)∼D((h(x)− y)2) (22)

content...

3.5 Funciones de pérdida generalizadas

Definición 3.6. Sea H nuestra clase de hipótesis y Z un dominio. El espacio dondeestá definida la distribución en el caso anterior, Z = X × Y . Se dice que ` es unafunción de pérdida ` : H × Z → R+.

Definición 3.7. Definimos la función de riesgo como el valor esperado para unclasificador h ∈ H sobre los elementos de Z con la distribución D,

LD(h) = EZ∼D(`(h, z)) (23)

Definición 3.8. Definimos el riesgo emṕırico para una muestra S = (z1, . . . , zn)como

LS(h) =1

m

m∑i=1

`(h, zi)

Ejemplo 3.1. 1. Binario, la variable z ∈ X × Y ,

`(h, (x, y)) =

{0 si h(x) = y

1 si h(x) 6= y

2. Pérdida cuadrática, la variable z está en X × Y

`(h, (x, y)) = (h(x)− y)2

13

4 Aprendizaje bajo convergencia uniforme

Definición 4.1. Fijamos Z = X × Y, D, ` y H. Decimos que una muestra S es�-representativa si ∀h ∈ H

|LD(h)− LS(h)| < �

Lema 4.1. Supongamos que S es �2 -representativa. Entonces el resultado de hS deERMH satisface

LD(hS) < minh∈H

LD(h) + �

Proof. Sea h ∈ H,

LD(hS) < LS(hS) + �

≤ LS(h) + �< LD(h) + �, ∀h ∈ H

Definición 4.2. Una clase de hipótesis H tiene convergencia uniforme (una vezfijado el dominio y el error) si existe una función mucH : (0, 1)

2 → N 3 ∀�, δ ∈ (0, 1)y cada D, se satisfaga que S es una muestra con m elementos, m ≥ mucH , entoncesS es �-representativo con probabilidad 1− δ.

Corolario 4.1. Si H es una clase de hipótesis con convergencia uniforme, entoncesH es PAC agnóstica con complejidad mH(�, δ) ≤ mucH (�/2, δ), usando ERMH .

4.1 Clases de hipótesis finitas son PAC aprendibles

Teorema 4.1 (Desigualdad de Houffding). Sean θ1, . . . , θn un conjunto de variablesaleatorias iid con E(θi) = µ y P(a ≤ θi ≤ L) = 1, ∀i = 1, . . . , n. Entonces ∀� > 0

P(| 1m

m∑i=1

θi − µ| > �) ≤ 2 exp{−2m�2

(b− a)2}

Nota 4.1. Queremos mostrar que si H es una clase finita, entonces H tiene conver-gencia uniforme. Sean �, δ ∈ (0, 1). Queremos un tamaño de muestra tal que, conprobabilidad 1− δ,

|LS(h)− LD(h)| < �, ∀h ∈ H

Como S se extrae iid,

Dm({S : ∀h ∈ H, |LS(h)− LD(h)| < �}) ≥ 1− δ

de manera equivalente,

Dm({S : ∃h ∈ H, |LS(h)− LD(h)| ≥ �}) < δ

14

Nótese que

{S : ∃h ∈ H, |LS(h)− LD(h)| > �} =⋃h∈H{S : |LS(h)− LD(h)| > �}, entonces

Dm({S : ∃h ∈ H, |LS(h)− LD(h)| > �}) = Dm(⋃h∈H{S : |LS(h)− LD(h)} > �)

≤∑h∈H

Dm({S : |LS(h)− LD(h)| > �})

Por otro lado,

LD(h) = EZ∼D[`(h, z)], LS(h) =1

m

m∑i=1

`(h, zi)

Si z es aleatoria, h fijo, entonces `(h, z) es aleatoria y E(LS(h)) = LD(h) =⇒|LS(h)− LD(h)| es una medida de la desviación.

Si `(h, zi) es nuestra variable aleatoria, E(`(h, z)) = LD(h). Suponemos que`(h, z) ∈ [0, 1]. Entonces

Dm({S : |LS(h)− LD(h)| > �}) = P(|1

m

m∑i=1

`(h, zi)− LD(h)| > �) ≤ 2e−2m�2, entonces

Dm({S : h ∈ H, |LS(h)− LD(h)| > �}) ≤ 2|H|e−2m�2 ≤ �

Por lo tanto

m =ln(2|H| δ

)2�2

Problema 4.1. Recordemos los PAC no agnósticos, entonces ∃p(x) 3 sign(p(x)) =h(x).

h(x) =

{yi si x = xi

1 en otro caso

Consideremosp(x) =

∏xi, yi=0

(x− xi)2

Problema 4.2. Demuestre E(LS(h)) = LD(h), S = {(x1, y1), . . . , (xm, ym)}.

Proof. Note que LS(h) =1m

∑mi=1 `(h, xi) =⇒

E(LS(h)) = E(1

m

m∑i=1

`(h, xi)) =1

m

m∑i=1

E(`(h, xi))

15

Si S está formado por datos idénticamente distribuidos, entonces

LS(h) =1

m

m∑i=1

LD(h) = LD(h)

Problema 4.3. Recordemos la definición de PAC aprendible. Si fijamos δ y tomamos0 < �1 < �2 < 1, entonces mH(�2, δ) ≤ mH(�1, δ). Si Sm tiene m datos, m ≥mH(�H , δ), entonces LD(h) < �1 < �2 =⇒ m ≥ mH(�2, δ). Por lo tantomH(�1, δ) ≥ mH(�2, δ). Entonces mH es mutuamente creciente respecto a �. Simi-larmente, podemos demostrar que es monótonamente respecto a δ.

Propiedad 4.1. H es una clase agnóstica PAC aprendible =⇒ H es PACaprendible.

Ejemplo 4.1. Sea X un conjuto finito y sea H = {hz} ∪ {h−} donde

hz(h) =

{1 x = z

0 x 6= z, h−(x) = 0

Estamos asumiendo realizabilidad. Sea S una muestra con m elementos. S ={(x1, y1), . . . , (xm, ym)}. Sea x0 el único punto tal que f(x0) = 1. Si x0 /∈ {x1, . . . , xm},ERM =⇒ h−. Si x0 ∈ {x1, . . . , xm}, ERM =⇒ hx0 . Dado �, δ, queremos en-contrar mH(�, δ),

Dm({Sm : LD(h) < �}) > 1− δ ⇐⇒ Dm({Sm : LD(h) > �}) < δ

Supongamos que queremos aprender h−, formamos Sm =⇒ (ERM) h− con LD(h−) =0. Si queremos aprender hx0 , formamos Sm (que contiene x0) =⇒ (ERM) hx0 . Siqueremos aprender hx0 , formamos Sm y x0 /∈ Sm. ERM → h−, � < LD(h) = P(x :h−(x) 6= hx0(x)) = P({x0}). Entonces P(x : x 6= x0) < 1− �.

Dm({S : Lp(h) > �}) < (1− �)m < δ =⇒ m =ln(δ)

ln(1− �)

Siguiendo hipótesis de realizabilidad, X = R2, y = {0, 1}, H = {hr}

hr(x) =

{1 |x| < r0 othw

Sm, entonces ERM =⇒ ćırculo con menor radio que contiene a todos los puntos declase 1. Fijamos �, δ, queremos encontra m 3 Dm({S : LD(h) > �}). Sea h∗ el discoque queremos aprender. Sea h� el disco tal que P(x : x ∈ h∗ − h�) = �. Sea Sm unamuestra tal que LD(h) > �. Esto significa que ningún punto en {x1, . . . , xm} está en

16

h∗−h�. La probabilidad de que x ∈ h∗−h� = � =⇒ P(x : x /∈ h∗−h�) = 1−� =⇒la probabilidad de formar Sm donde ningún punto está en h∗−h� es (1−�)m < δ =⇒

m <ln δ

ln(1− �)

Pero (1− �)m < e−m� < δ =⇒ m > ln(1/δ)� .

5 Predictores Lineales

Nota 5.1. Algunas clases de hipótesis son espacios mitad, regresión lineal y re-gresión loǵıstica. Los algoritmos de clasificación son programación lineal, regresiónlineal y regresión loǵıstica.

Definición 5.1. Definimos a la clase de funciones afines en Rd como

Ld = {hw,b : w ∈ Rd, b ∈ R}

tal que hw,b : Rd → R, donde

hw,b(x) = 〈w, x〉+ b =d∑i=1

wixi + b

Entonces, Ld = {x 7→ 〈w, x〉 + b, x, w ∈ Rd, b ∈ R}. Podemos absorber a b en elvector w. Definimos

w′ = (b, w1, . . . , wd), x′ = (1, x1, . . . , xd), hw,b(x) = 〈w′, x′〉

5.1 Espacios mitad

Definición 5.2. Dada la labor de clasificación binaria, X = Rd → Y = {±1}.Definimos la clase de hipótesis HSd (half-spaces) como

HSd = {h : Rd → {±1} 3 h(x) = sign(hw,b(x)), hw,b ∈ Ld}

Sean S = {(x1, y1), . . . , (xm, ym)}, xi ∈ Rd, yi ∈ {±1}. Como estamos suponiendorealizabilidad, ERM → hS y LS(hS) = 0. Por otro lado, hw(x) − 〈w, x〉 =⇒sign(〈w, xi〉) = yi, ∀i = 1, . . . ,m. Nótese que, excluyendo puntos frontera, yi〈w, xi〉 >0.

Definición 5.3. Definimos γ = mini〈w, xi〉 y w̃ = w∗

γ , donde w∗ = EMR. Entonces,

yi〈w̃, xi〉 = 1γ 〈w∗, xi〉 ≥ 1, ∀i = 1, . . . ,m =⇒ A = yixij y v =

1...1

=⇒ Aw̃ ≥ v.17

5.2 Perceptrón

Definición 5.4. Si tenemos S = {(x1, y1), . . . , (xm, ym)}. Sea w(1) = (0, . . . , 0), si∃(xi, yi) mal clasificado, i.e. yi〈xi, w〉 < 0, entonces w(1) = w(0) + yixi. En general,

w(t+1) = w(t) + xiyi (24)

Podemos probar que

yi〈xi, x(t+1)〉 = yi〈xi, w(t) + yixi〉= yi〈xi, w(t)〉+‖xi‖2

Sea R = maxi|xi| yB = | inf{w : yi〈w, xi〉 > 1, ∀i}|

El número de pasos máximo del algoritmo de perceptrón es RB2.

5.3 Regresión lineal

Definición 5.5. Sean X ⊆ Rd, Y ⊆ R. La clase de hipótesis es

HREG = {x 7→ 〈w, x〉+ b, w ∈ Rd, b ∈ R}

Definición 5.6. La función de pérdida continua es `(h, (x, y)) = (h(x)− y)2.

Definición 5.7. La función de riesgo es LS(h) =∑m

i=1(h(xi)− yi)2.

Definición 5.8. La función de mı́nimos cuadrados es

arg minwLS(hw) = arg min

w

1

m

m∑i=1

(〈w, xi〉 − yi)2 (25)

Nota 5.2. En la definición anterior,

d

dwLS(hw) =

2

m

m∑i=1

(〈w, xi〉 − yi)xi

Definimos (xai) = (~x1, ~x2, . . . , ~xm). Entonces

0 =m∑i=1

(〈w, xi〉 − yi)xbi =m∑i=1

d∑a=1

(waxai − yi)xbi

=

m∑i=1

d∑a=1

xbixTiawa − xbiyi = (XXTw)b − (Xy)b

18

Lo cual implica que XXT︸ ︷︷ ︸A

w = Xy︸︷︷︸b

=⇒ Aw = b. Como A = XXT , entonces A

es simétrica. Entonces, A = V DV T =⇒ A−1 = V D−1V T , pero si D no tieneinversa, definimos D+ 3 D+ii = 0 ssi Dii = 0 y D

+ii =

1Dii

ssi Dii 6= 0. Entonces,A+ = V D+V T . Definimos ŵ = A+b, entonces

Aŵ = (V DV T )A+b = (V DV T )V D+V T b

= V DD+V T b =∑

i:Dii 6=0ViV

Ti b = b

5.4 Regresión loǵıstica

Definición 5.9. Sea h : Rd → [0, 1], X = Rd, y = {±1}. Y h(xi) es la probabildiadde que yi sea 1. Sea

σ(z) =1

1 + e−z

yHsig = σ ◦ Ld = {x 7→ σ(〈w, x〉+ b) : w ∈ Rd, b ∈ R}

Y definimos su función de pérdida

`(h, (x, y)) = ln(1 + exp{−y〈w, x〉}

)(26)

con

LS(h) =1

m

m∑i=1

ln(1 + exp{−yi〈w, xi〉}

)6 VC dimension

En términos de conjuntos, para todo B ⊂ A, ∃Xn ∩A = B.

Ejemplo 6.1. X = R2, y = {0, 1}, H rectángulos alineados con ejes VCdim(H) =4. No puede ser 5 dado que, si considera los puntos con coordenadas min/max enx, y, el quinto punto se encuentra necesariamente dentro del cuadrado.

Ejemplo 6.2. X = Rn y clase de hipótesis anterior. Entonces VCdim(H) = 2n con

xi = (0, . . . , 0,±1, 0, . . . , 0)

Propiedad 6.1. Si H ⊂ H ′, entonces VCdim(H) ≤ VCdim(H ′).

Propiedad 6.2. 2n = |H| ≥ 2VCdim(H) =⇒ n ≥ VC dim(H).

19

Ejemplo 6.3. Sea X = {0, 1}n. Sea I ⊆ {1, 2, . . . , n}. Definimos una función deparidad asociada a I. Sea (x1, . . . , xn), hI(x) =

∑i∈I xi mod 2. Entonces

Hn-parity = {hI : I ⊆ {1, . . . , n}}

Entonces para hI = ∅ funciona en R3. Ahora,

hI(ek) =∑i∈I

xi mod 2 = 1

y es 0 para el resto. Sea B un subconjunto de {ei, i = 1, . . . , n}, I = {i : ei ∈ B}

hI(ei) =

{1 i ∈ I0 i /∈ I

6.1 Teorema Fundamental del aprendizaje PAC

Teorema 6.1. Sea H una clase de hipótesis, H = {h : X → {0, 1}}. Sea la funciónde pérdida la función 0–1. Entonces son equivalentes

1. H tiene convergencia uniforme.

2. Cualquier algoritmo ERM es un aprendiz PAC agnóstico exitoso para H.

3. H es PAC agnóstico aprendible.

4. H es PAC aprendible.

5. Cualquier algoritmo ERM es un aprendiz PAC exitoso para H.

6. H tiene dimensión VC finita.

6.2 Función de crecimiento

Definición 6.1. Sea H una clase de hipótesis. La función de crecimiento de H, τH :

N→ N se define comoτH(m) = max

C⊂X:|C|=m|Hc|

Ejemplo 6.4. Si VCdim(H) = d, para m ≤ d, τH(m) = 2m.

Lema 6.1. Sea H una clase de hipótesis con dimensión VCdim(H) ≤ d < ∞.Entonces, para todo m

τH(m) ≤d∑i=0

(m

i

)En otras palabras, para m > d+ 1,

τH(m) ≤(em

d

)d20

Teorema 6.2. Sea H una clase de hipótesis y sea τH su función de crecimiento.Entonces, para cada D y cada δ ∈ (0, 1), tenemos

|LD(h)− LS(h)| ≤4 +

√ln τH(2m)

δ√

2m

con probabilidad 1− δ.

Nota 6.1. H dimensión VC= d. Para m > d, τH(m) ≤ (em/d)d. Entonces

|LD(h)− LS(h)| ≤4 +

√d ln(em/d

)δ√

2m

7 Aprendizaje no uniforme

Definición 7.1. Una clase de hipótesis es no-uniformemente aprendible si existe unalgoritmo A y una función mNUH : (0, 1) × (0, 1) × H → N tal que si �, δ ∈ (0, 1) yhinH, entonces para toda distribución D, se tiene que

LD(A(S)) ≤ LD(h) + �

Nota 7.1. Comparación con esquema PAC agnóstico.

Ejemplo 7.1. Sea X = R, y = {±1}. H = {hp}, hp(x) = sgn(p(x)). VCdim(H)→∞. Si H2 = {hp}, hp(x) = sgn(a+ bx+ cx2), VCdim(H2) = n+ 1.

Teorema 7.1. Sea H una clase de hipótesis que satisfaga

1. H =⋃n∈NHn

2. Cada Hn tiene la propiedad de convergencia.

entonces H es no-uniformemente aprendible.

Teorema 7.2. Una clase de hipótesis es no-uniformemente aprendible ssi H es unaunión contable de clases de hipótesis PAC agnósticas.

Proof. Si H =⋃h∈H Hn, donde Hn es PAC-aprendible, entonces por el TFAS, Hn

tiene la propiedad de convergencia uniforme y H es NU .

7.1 Minimización estructural de riesgo

Definición 7.2. Sea H una clase no uniformemente aprendible. Entonces, H =⋃nHn donde Hn tiene la propiedad de convergencia uniforme. Definimos �n : N ×

(0, 1)→ (0, 1)�n(m, δ) = min{� ∈ (0, 1) : mUCHn (�, δ) ≤ m}

21

Y �n es el mı́nimo error que se puede alcanzar aprendiendo Hn con ciertos ejemplosy cierta confianza. Entonces

|LD(h)− Ls(h)| < �n(m, δ), ∀h ∈ Hn

con probabilidad 1 − δ. Sea w : N → [0, 1] una función tal que∑

nw(n) ≤ 1. Estaes una función que le asigna un peso a H1, . . . .

Teorema 7.3. Sea w una función de peso. Sea H una clase de hipótesis tal queH =

⋃nHn donde cada Hn tiene convergencia uniforme. Entonces, para cada

δ ∈ (0, 1) y distribución con probabilidad 1−δ sobre S ∼ Dm, se satisface para cadan ∈ N y h ∈ Hn

|LD(h)− Ls(H)| ≤ �n(m,w(n)δ)

Entonces, para cada δ ∈ (0, 1) y distribución D con probabilidad al menos 1−δ, ∀h ∈H

LD(h) ≤ LS(h) + minn:h∈Hn

�(m,w(n)δ)

Proof. Para cada n, tomamos δn = w(n)δ. Entonces, como Hn tiene convergenciauniforme,

∀h ∈ Hn, |LD(h)− LS(h) ≤ �n(m, δn)

Entonces, existe h ∈ Hn,

|LD(h)− LS(h)| > �n(m, δn)

con probabilidad δn. Por lo tanto

PS∼Dm [∃h ∈ H : |LD(h)− LS(h)| > �n∀n] ≤∑n

P[∃h ∈ Hn : |LD(h)− LS(h)| > �n]

≤∑n

δn =∑n

δw(n) ≤ δ

Entonces, con probabilidad 1− δ, sobre S ∼ Dm, ∀h ∈ H

LD(h) ≤ LS(h) + minn:h∈Hn

�(m,w(n)δ) = LS(h) + �n(h)(m,w(n)δ)

si definimos n(h) = min{n : h ∈ Hn}.

Nota 7.2. Lo que sé es H =⋃n con Hn convergencia uniforme, m

UCH , w función

de peso,∑

nw(n) ≤ 1. Definimos �n, n(h). La entrada es S ∼ Dm, δ. Y la salida es

h ∈ arg minh∈H

LS(h) + �n(h)(m,w(n(h))δ)

22

Teorema 7.4. Sea H una clase de hipótesis tal que H =⋃nHn con cada Hn con

convergencia uniforme. Entonces, usando SRM, H es no-uniformemente aprendible,con complejidad

mNULH (�, δ, h) ≤ mUCHn(h)(�/2, w(n)δ)

donde w es la función de peso.

Proof. Usando SRM como nuestro algoritmo A, respecto a una función de pesow. Sean, �, δ ∈ (0, 1) y h ∈ H. Sea m > mUCHn(h)(�, w(n(h))δ). Entonces, conprobabilidad 1− δ, usando el teorema anterior

LD(h) ≤ LS(h) + �n(h)(m,w(n(h))δ)

En particular para el resultado A(S) de SRM,

LD(A(S)) ≤ minh′∈H

[LS(h′) + �n(h′)(m,w(n(h

′))δ)]

≤ LS(h) + �n(h)(m,w(n(h))δ)

Si m ≥ mUCHn(h)(�/2, w(n(h))δ), entonces �n(h)(m,w(n(h))δ) ≤ �/2. Entonces, comoHn(h) tiene convergencia uniforme, LS(h) ≤ LD(h) + �/2 con probabilidad 1 − δ,entonces

LD(A(S)) ≤ LD(h) + �/2 + �/2,∀h ∈ H

7.2 Longitud de mı́nimo descripción

H es una clase de hipótesis numerable

H =⋃n∈N

Hn =⋃n∈N{hn}

Entonces

θ =1

m

m∑i=1

`(h, zi) (27)

tal queEz∼D[`(h, z)] = LD(h)

y

P[| 1m

m∑i=1

`(h, zi)− LD(h)| > �] ≤ 2e−2m�2< δ (28)

Cada clase {hm} tiene complejidad de muestra

mUCHn (�, δ) =ln(2/δ)

2�2

23

En este caso, podemos ver a w : H → [0, 1] y SRM

h ∈ arg minh′∈H

LS(h′) +

√−ln(w(h)) + ln

(2/δ)

2m

Vamos a asignar pesos w en relación con la representación de las hipótesis. Sea Huna clase de hipótesis y sea Σ un conjunto finito de caracteres Σ = {0, 1}. Unapalabra es una secuencia finita de śımbolos en Σ y Σ∗ es el conjunto de śımbolos delongitud finita en Σ. Por ejemplo, σ = {10010} ∈ Σ∗, con |σ| = 5. Entonces, Σ∗ eslibre de prefijos si, dados σ, σ′ ∈ Σ∗, entonces σ no es un prefijo de σ′. Definimosun lenguaje para representar a H como un mapeo d : H → Σ∗, dada h tenemos surepresentación d(h).

Lema 7.1 (Desigualdad de Kraft). Sea S ⊂ {0, 1}∗ libre de prefijos, entonces

Σσ∈S1

2|σ|≤ 1 (29)

Dada la palabra σ, P (σ) es la probabilidad de formar la palabra σ, entonces

P (σ) =1

2|σ|

Como las probabilidades suman hasta 1∑σ∈S

1

2|σ|≤ 1

y

h ∈ arg minh∈H

LS(h) +

√|d(h) + ln

(2/δ)|

2m, w(h) =

1

2|d(h)|

Teorema 7.5. Sea H una clase de hipótesis numerable y d : H → {0, 1}∗ unlenguaje para representar a H libre de prefijos. Entonces, para cada m, δ,D, conprobabilidad no menor que 1− δ, tenemos que

∀h ∈ H, LD(h) ≤ LS(h) +

√|d(h)|+ ln

(2/δ)

2m

Teorema 7.6 (Desigualdad de Hoeffing). Si tenemos variables aleatoriasX1, . . . , Xmtales que E[xi] = µ y definimos

θ =1

m

m∑i=1

Xi

entonces

P[| 1m

m∑i=1

Xi − µ| > �] ≤ 2

24

7.3 Longitud de mı́nima descripción (MDL)

Lo que sabemos, H clase numerable, d : H → {0, 1}, |d(h)| = |h|. La entrada esS ∼ Dm, δ. y salida

h ∈ arg minh∈H

LS(h) +

√|d(h) + ln

(2/δ)|

2m

8 Complejidad computacional de aprendizaje

Un algoritmo A. Tenemos un dominio Z = X × Y , una clase de hipótesis H, unafunción de pérdida ` : H × Z → R, S ∼ Dm extráıda de Z según una distribuciónD de manera iid. Queremos que A genere h ∈ H tal que, dados �, δ,

LD(h) ≤ minh′∈H

LD(h) + �

con probabilidad 1− δ. Complejidad de muestra

magH (�, δ) =2ln(2|H|/δ)

�2

Definición 8.1 (Complejidad computacional de aprendizaje estad́ıstico). Dada unafunción f : (0, 1)2 → N, un problema de aprendizaje (X × Y,H, `) y un algoritmoA, decimos que A resuelve el problema de aprendizaje en un tiepo O(f) si existe unnúmero c tal que, dados �, δ ∈ (0, 1) y para toda D,

1. A termina en un tiempo no mayor a cf(�, δ).

2. El resultado de A puede ser usado para predecir la etiqueta de un ejemplonuevo.

3. El resultado de A es PAC.

Dada una secuencia (Xn×Yn, Hn, `n)∞n=1 de problemas de apredizaje y un algoritmoA aplicable a esta secuencia, una función g : N × (0, 1)2 → N, decimos que lacomplejidad computacional es O(g) su para todo n el problema se resuelve en untiepo O(fn), donde fn(�, δ) = g(n, �, δ). Por otro lado,

g(d, �, δ) = dmH(�, δ)

=d ln(|H|/δ

)�

Entonces decimos que A es eficiente si su complejidad es O(p(n, 1� ,1δ )).

25

9 Selección y validación de modelo

Regresión de L : R→ RUsando SRM, H1, H2, . . .

mUCHd (�, δ) ≤g(d) ln

(1/δ)

�2

Con g : N → N monótona creciente. Usando SRM, tenemos una hipótesis H queminimiza

LD(h) ≤ LS(h) +

√g(d)(ln

(1/δ)

+ 2 ln d+ ln(π2/b

)m

con probabilidad 1− δ sobre S ∼ Dm.

9.1 Validación

Sea V = {(x1, y1), . . . , (xmv , ymv)} conjunto de validación y S = {(x1, y1), . . . , (xm, ym)}.

Teorema 9.1. Sea h un predictor cualquiera y /ell : H ×Z → [0, 1] una función depérdida. Entonces, si δ ∈ (0, 1), tenemos que

|LD(h)− Lv(h)| ≤

√ln(2/δ)

mv(30)

con probabilidad 1− δ sobre VDm.

Proof. Sea h una hipótesis. Entonces `(h, z) es una variable aleatoria. Usando ellema de Hoeffding,

PV∼Dmv [|1

mv

mv∑i=1

`(h, zi)− LD(h)| >

√ln(2/δ)

mv]

Podemos usar validación para seleccionar un modelo m. Si tenemos H1, . . . ,Hr,definimos H = {h1, . . . , hr} como los resultados de nuestro algoritmo de aprendizajesobre cada una de las clases y usamos los datos en V para aprender sobre H.

Teorema 9.2. Sea H = {h1, . . . , hr}, ` una función de pérdida con valores en [0, 1].Usamos V con m ejemplos. Entonces tenemos

∀h ∈, |LD(h)− LV (h)| ≤

√ln(2|H|/δ

)2mV

con probabilidad al menos 1− δ.

Proof. |LD(h)− LV (h)| ≤√

ln(2|H|/δ)2mV

con probabilidad 1− δ|H|

26

9.2 Cross validation

entradaS datos de entrenamientoparámetrosalgoritmo Aentero k

Se hace una partición de S en S1, . . . , Sk. Para cada parámetro θ ∈ Θpara cada i ∈ [1, . . . , k]hi,θ = A(S/Si,θ)

L(θ) =∑k

i=1 LSi(hi,θ)salida

θ∗ ∈ arg min(L(θ))hθ∗ = A(S, θ

∗)

Nota 9.1. Note que

LD(h) = LD(h∗)︸ ︷︷ ︸

error de aprox.

+LD(h)− LD(h∗)︸ ︷︷ ︸error de est.

El error de aproximación depende de D, H y no depende de S. Se busca aumentarH, que sea más complejo. El error de estimación mejora al aumentar S, reducir H.

Nota 9.2. Ahora,

LD(hS) = (LD(hS)− LV (hS)) + LV (hS)− LS(hS)︸ ︷︷ ︸sobreajuste

+LS(hS)︸ ︷︷ ︸subajuste

Ejemplo 9.1.∞∑i=0

x2 − y − α+ ℵ0

dim VC aprendizaje no uniforme

27

ProbabilidadEspacios muestrales, eventos e independenciasValor esperadoCota de la uniónFunción característicaVarianzaTeorema del límite centralDistribuciones de probabilidadRegla de Bayes

Modelo Formal de AprendizajeMinimización de riesgo empírico (ERM)ERM con sesgoClase de hipótesis finitas

Aprendizaje PACComplejidad de la muestraAprendizaje PAC agnósticoError empírico y realPredictor óptimo de BayesFunciones de pérdida generalizadas

Aprendizaje bajo convergencia uniformeClases de hipótesis finitas son PAC aprendibles

Predictores LinealesEspacios mitadPerceptrónRegresión linealRegresión logística

VC dimensionTeorema Fundamental del aprendizaje PACFunción de crecimiento

Aprendizaje no uniformeMinimización estructural de riesgoLongitud de mínimo descripciónLongitud de mínima descripción (MDL)

Complejidad computacional de aprendizajeSelección y validación de modeloValidaciónCross validation