aprendizaje automáticohallende/bajadas/redes/apuntes%20curso%20ann... · 6 teorema de equivalencia...

1

Aprendizaje automático y la guerra contra el overfitting

Ricardo Ñanculef Alegrí[email protected]

10.04.2007

Aprendizaje AutomáticoObjetivo general

� Desarrollo de algoritmos que permitan a un sistema artificial aprender es decir, mejorar automáticamente producto de la experiencia

� Infinitas Aplicaciones� Búsqueda web� Interfaces � Seguridad� Biomédicas y BioInformáticas� Aprendizaje: aspecto crítico del comp. inteligente.

� Aspecto crítico del comp. inteligente


“ (...) Arguably, the problem of learning represents a gateway to understanding intelligence in brains and machines, to discovering how the human brain works, and to making intelligent machines that learn from experience and improve their competences as children do …”

T. Poggio and S. Smale. “The Mathematics ofLearning: Dealing with Data”, Notices of the AMS,

May 2003


� Herramientas para extraer modelos, patrones, relaciones o reglas desde conjuntos de datos difícilmente explorables por humanos

� En vez de programación explícita, se presentan casos que deben ser generalizados

� Datos son sintetizados, para obtener descripciones de alto nivel, válidas más allá de los ejemplos particulares.

Ejemplosspam filtering

Ejemplosanálisis de patrones de expresión genéticos

2

Ejemplosdocument organization and ranking

Ejemplosbiometric authentication

Aprendizaje Automáticoaspectos centrales

� Representación del problema� Selección de características: ¿cómo representar un

objeto: un correo electrónico, una cara, una célula, un documento?

� Medidas de similaridad, geometría del espacio: ¿quéesta cerca de qué: documentos? ¿qué se parece a qué: caras?


� Clase de modelo a construir� Reglas IF-THEN� Árboles de decisión� Redes neuronales� Grafos: redes bayesianas� Hiperplanos y discriminantes� Polinomios� Modelo de vecinos más cercanos


� ¿cómo elegir una familia de modelos? � … ¿y un modelo dentro de la familia?� ¿qué modelo es mejor?� capacidad de generalización

� casos nuevos, no conocidos� model assessment: qué tanto generaliza el modelo� model selection: cómo seleccionar un modelo que

generalice relativamente bien

Agenda

� Definición del Problema� Teoría VC (Vapnik-Chervonenkis)� Estabilidad Algorítmica� Regularización � Evaluación de un modelo� Ensamblados

3

Modelo básico supervisado

System� �

Learner ��

��

�

Definiciones

� Training Set: S = {z1=(x1,y1), ..., zn=(xn, yn)}� Z = X × Y� Distribución desconocida µ(x, y)

� Espacio de Hipótesis: H� Hypothesis fS ∈ H: X → Y

� Algoritmo de Aprendizaje:�

� Regresión: fS es continua � Clasificación: fS es discreta

� ��

≥→

� � ��

{ }( ) �� ==== ��

Definiciones

� Loss Function: V(f, z)�

� Elecciones típicas en regresión:� V(f, z) = (f(x) – y)2 squared loss� V(f, z) = |f(x) – y| absolute loss

� Elecciones típicas en clasificación � V(f, z) = I(f(x) � y) 0-1 loss� V(f, z) = exp(-yf(x)) exponential loss (margin)� V(f, z) = - binomial deviance

�� →×�

��

Definiciones

� Loss Function: V(f, z)�

� Error Esperado (Prediction Error, True Error, Risk)

� Objetivo del algoritmo: minimizar el error esperado.� Problema: no podemos evaluarlo!!

�=�

��

�� →×�

Principio de Inducción

� Idea: reemplazar el error esperado por algo que podamos medir y “se le parezca „ ...

� ERM: Minimizar Error Empírico (Training Error)

� histograma ...

�=

=�

�

� ��

��

��

� −=≈�

�� δµµ

Generalización del ERM

� Convergencia en probabilidad

� Teorema de Glivenko-Cantelli

� Generalización de ERM: Error de entrenamiento debeser un buen indicador del error esperado

( ) ��

�

∞→

→− µµ

( ) �� >∀=>−∞→

��

�� =−∞→

��

4


� Problemas� GV implica generalización?: Notemos que la función

seleccionada por el algoritmo depende de S!� Bajo qué condiciones ERM generaliza?� Nuestra inferencia es con una cantidad finita y en

general reducida de observaciones ¿que tan rápida es la convergencia?


Descomp. bias-varianza

� Para el error cuadrático, condicionando a x

��

�� =−=

( ) ( )��

�

��

� �� −+−+= σ

( ) ��

�� ++= σ

( )��

� �� −=σ �� =σε+= ��

Diferencia esperada entre predicción y valor verdadero

Variabilidad de la estimación



� consideremos por ejemplo, un modelo lineal

� la descomp. toma la forma

εβ += ��

�� −=β

( ) ��

�

�

��

�

�

� �� εε σσ �� +−+==−

��

�� −=

� �� =

��

��

�=�

��

�

� ��

�� ββ == �


� Si evaluamos en los ejemplos ...

� Supongamos que la funcion verdadera es lineal con q características de x y estimamos secuencialmente, diferentes modelos lineales con 1, 2, 3, .. p caract.

� ¿qué ocurre con el sesgo?� ¿qué ocurre con la varianza?� ¿qué ocurre con el error de entrenamiento?

� =−=�

� ��

( ) �� εε σσ�

��

�

�� +−+= �

� =−=�

� ��

5


� El sesgo del modelo debiera reducirse hasta que llegamos a incluir q características pues el modelo lineal es insesgado si el modelo real es lineal.

� La varianza aumenta monótamente� El aumento de la varianza se justifica hasta que

llegamos a q características� El error de entrenamiento decrece monótonamente,

incluso más allá de q!!� Si q=n el error de entrenamiento es cero independiente

de cómo se organizen las observaciones!!

�� ββ == �


� otro ejemplo, k-nearest neighbors

�∈

=��

��

��

�

��

��

��

�∈

==��

��

��

��

��

��

�� k vecinos más cercanos de x

Descomp. bias-varianza� en este caso la descomp. toma la forma

� La varianza aumenta cuando k disminuye� La reducción del sesgo no necesariamente compensa� Sin embargo el error de entrenamiento es cero con k mínimo (k=1) y en

general aumentará con k

� Podemos elegir el modelo en base ERM??

( ) �� εσσ

��

�

�� +−+= �

��

� �� =−=

Teoría VC

Qué propiedad debe tener el espacio H para que el ERM

generalice bien?

ERM: Minimizar el error de training sobre H:• elegir el modelo más consistente con los ejemplos• aquí ��

�� ∈

=

Teoría VC

� Consistencia� El riesgo de la función obtenida al entrenar con la muestra

S converge en probabilidad al mínimo riesgo alcanzable en el espacio H

� Para ERM consistencia = generalización

��!�� =��

�� +>>∀

∈∞→��

��

�

��! ��

�

� ∈∞→

→

Teorema de Equivalencia(Vapnik, Statistical Learning Theory, Pag.88)

� Theorem: A necessary and sufficient condition for generalization and consistency of ERM is that VH is a uniform Glivenko-Cantelli (uGC) class:

� Convergencia uniforme de las medias a las esperanzas� Generalización = análisis del peor caso!!� Condiciones sobre el espacio resultante al componer V y H

�� =��

��

� >−>∀∈∞→

��

�

6

Teorema de Equivalencia(Alon et al. , Scale-sensitive dimensions, uniform convergence and learnability, Journal of ACM 44, 1997 )

� Theorem: A necessary and sufficient condition for generalization and consistency of ERM is that H is a uniform Glivenko-Cantelli (uGC) class:

� Para funciones de costo razonables� lipschitz

��

� ��

=��

��

�>−>∀ � �

=∈∞→

�

��

��

�

��

�

Teoría VC

� Bajo que condiciones VH es un clase uGC?� Supongamos que H es finito

� condición

��

��

� >−∈

��

( )�=

>−≤�

�

��

��

( )�� "�� ε−≤

��

��

��

��

� −= ��

� ��

"�� ε

��

∞→→��

�

Chernoff inequality

Medidas de Capacidad

� Si H no es finito, N se debe reemplazar por una medida del tamaño o complejidad de VH

� Supongamos que VH toma solo 2 valores� Coeficiente de Shattering de un espacio Q: Número

de funciones que se pueden distinguir por sus evaluaciones en una muestra de tamaño n

�� ≤


� Entropy:

� Annealed Entropy:

� Growth function:

� VC dimension: tamaño máximo de S para el cual la función de cremiento es m, es decir alcanza su máximo valor

( )�� =

( )�� =

( )��

=


� Para obtener consistencia del ERM es suficiente que

� Las medidas corresponden al espacio VH� pequeñas modificaciones generan necesidad!� Para obtener consistencia exponencial del ERM

��

�� =∞→ �

��

�

��

�� =∞→ �

��

�


� Para obtener consistencia del ERM independiente de la distribución de los datos es suficiente tener

� Es decir, la dimensión VC es finita!� En este caso la convergencia es exponencial

��

�� =∞→ �

�

�

7

Cotas VC

� Con probabilidad

� Uniformente en H� Un error observado nulo no implica riesgo nulo! La

estructura pesa!

��

�#1

Característica estructural

��

��

� +δ$

��%

!"#��

��+

Desempeño medido

confianza

Cotas VC

� Lo anterior implica que es posible acotar mediante una función exponencial en el número de ejemplos, la peor diferencia entre el error empírico y el error esperado

� Comparar con el caso H finito

�

� �

��

��

��

��

� −−<��

��

� >−∈

��

��

��

��"��$�� ε

��

��

��

��

� −= ��

� ��

"�� ε

Generalizaciones

� Cotas independientes de la distribución se obtienen al reemplazar la entropía por la dimensión VC

� Para el caso de funciones de costo que toman valores continuos se obtienen resultados similares.

Generalizaciones

� epsilon-net: cover con precisión epsilon sobre VH� Minimal epsilon-net� epsilon-entropy� Condición suficiente para consistencia

� Es posible derivar las cond. necesarias� Es posible derivar cotas exponenciales

�� ε�

�� εε �� =

��

�� =∞→ �

�

�

ε ε∀

Síntesis: Teoría VC

� Caracterización completa de las condiciones suficientes y necesarias para la buena generalización de algoritmos ERM

� Limitaciones:� Las cotas VC son poco tight� Las condiciones dependen del espacio VH o H, no del

algoritmo propiamente tal.� ¿son todos los algoritmos ERM?

Nuevas Ideas� Estabilidad implica

Generalización� Un algoritmo de aprendizaje

es estable si pequeñas perturbaciones en el conjunto de entrenamiento no generan cambios violentos en los modelos obtenidos

� Las condiciones se ponen sobre el algoritmo!

8

Estabilidad

� Por ejemplo, que ocurre si eliminamos un punto de la muestra

� Es posible caracterizar formalmente la capacidad de generalización de un algoritmo en estos términos?

Original Training Set S

Perturbed Training Set Si

Hypothesis Space

Learning Map

ERM versus no ERM

� Algunos Algoritmos ERM

� Regresión de Mínimos Cuadrados� Árboles de decisión� ANN con backpropagation estándar

� No son (completamente) ERM

� Support Vector Machines� k-Nearest Neighbors� Bagging, Boosting� Regularization

Estabilidad UniformeBousquet, Elisseeff: Stability and Generalization, Journal of Machine Learning Research 2, 2001

� Un algoritmo de aprendizaje L is uniformly stable si

�

$��

�

� ≤−∈∀∈∀∈

�� &��'�

� La variación del error al eliminar un ejemplo debe ser pequeña para todos los puntos z: medida de influencia.

� Establidad uniforme implica generalización!!� Sin embargo muy pocos algoritmos son uniformemente

estables. La mayoría de los ERM no lo son.

Estabilidad CVlooMukherjee, Niyogi, Poggio, Rifkin: Statistical Learning: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization, MIT 2003

� Cross-Validation leave-one-out stability

�

� Solo mide la variación del error al predecir el punto que se ha eliminado

remove zi

error at xi

�� &��'

��

� =−∈∞→

Equivalence for ERMMukherjee, Niyogi, Poggio, Rifkin: Statistical Learning: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization, MIT 2003

� Theorem: For good loss functions the following statements are equivalent for ERM:� L is distribution-independent CVloo stable� ERM generalizes and is universally consistent� H is a uGC class

� Estabilidad CVloo asegura generalización de otros (no ERM) algoritmos?

Contraejemplo

� X uniforme en [0, 1]� Y ∈ {-1, +1}� Target f *(x) = 1� algoritmo L:

� Clamente el algoritmo es CVloo stable� Pero no generaliza!

� �

−−

= +(��"��

�")"�� "��

��

�

��

� �

−=

=(��"��

��

��

��

�

�

9

Criterios adicionales

� Estabilidad en error de predicción (Eloo)

� Estabilidad en error empírico (EEloo)

�*��*"�� &��'

=−∈∞→

��

��

�*��*"�� &��'

=−∈∞→

��

��

Estabilidad CVEEEloo

� Un algoritmo L es estable CVEEEloo si� es estable CVloo

� es estable Eloo

� es estable EEloo

� Theorem: If L is CVEEEloo stable and the loss function is bounded, then fS generalizes

� Estabilidad CVEEEloo no es garantía de consistencia

Remarks

� Teoría VC� � Occams Razor: preferir modelos sencillos

� Estabilidad algorítmica� � Robustez del proceso de aprendizaje

� Las idea de estabilidad como condición para la generalización podría estar mejor conectada con el aprendizaje humano

� Foco en el algoritmo: simplifica el diseño� Teoría más computacional que matemática

Regularización

� Moralejas de la teoría revisada: Control de Capacidad y Estabilidad

� Regularización: Técnicas de control explícito de la complejidad de un modelo usualmente llevado a cabo mediante la incorporación a la función objetivo de un funcional que castiga modelos complejos

��

�

�%��

��

�

�

�&'

⋅+= �=

λ

regularizadorparámetro de regularización

• Castiga capacidad• Proporciona estabilidad

Regularización

� Regularización de Tikhonov: problemas inversos� Dado un operador resolver para f

� equivalente a resolver� Problema: que ocurre si las observaciones de F

tienen ruido o sólo podemos observar F de manera aproximada ...

�� ()*� =

��* →�

�

��

��(*� −

∈

Regularización

� Sea la solución de

� ¿Qué tan cercana es a f(t)?

�

��

��(*� δ−

∈+�

+�

�−*

� �

10

Regularización

� Cómo no necesariamente es continuo, soluciones cercanas en N no necesariamente corresponden a funciones cercanas en M

� Si ocurre lo anterior se dice que el problema estámal condicionado. En otro caso bien cond.

� Observación clave de Tikhonov:� Si M es compacto y A continuo, el problema es bien cond.� Podemos hacer que el problema esté bien condicionado si

lo resolvemos restringiendo apropiadamente el espacio N

�−*

Regularización

� Regularización de Tikhonov: Elegir f para minimizar un funcional

� donde el funcional es tal que todos los conjuntos son compactos

� Si la solución al problema existe en el dominio de definición de W, el problema está bien condicionado en el sentido de Tikhonov

��

��%(�*(��

��⋅+−= γγ

�� ≥�%

{ }��%�� ≤= ��

(*� =

Regularización

� Si A es lineal (en general problema convexo en f?), el problema anterior resulta equivalente a

� Es decir, resolvemos el problema en un subespacio compacto del original

��

�� %(�*(��

��⋅+−= γγ

�

��

��

(�*�� −�� γ)%!�#)� ≤

Regularización

� Teorema: Supongamos que en vez de observar observamos tal que .Supongamos que el parámetro se elige tal que

entonces las funciones que minimizan

satisfacen:

��

�� %(�*(��

��⋅+−= γδ

γ

(δ( δδ ≤− ((

γ��

�→→

δδγ∞<

→ ��

�

� δγδ

δ

γδ�

(*��

�

−

→=→

δ

γδ

Regularización

� Elecciones típicas ...

� en general, se busca la solución en subconjuntos de los espacios de sobolev

� mientras más alto es m, más suavidad exigimos!

��

��% = �

��

��% =

�� "

∞<��

��

� ��

"�

smoothing splinesridge regression

Regularización

� Problema de aprendizaje está mal condicionado!!� Intentamos aproximar una función en base a la

observación de sus imágenes en ciertos puntos (los x´s que tenemos como ejemplos).

� En general observamos con ruido� Podemos tener F´s cercanos (es decir y´s) pero

funciones f corresp. no cercanas: overfitting!!

( ) ��*� =operador de evaluación(para espacios de hilbert es lineal)

ε+= ��

11

Regularización

� Regularización funciona en la práctica!!� Por ejemplo: Modelo Lineal

� Ridge Regression

εβ += ��

�� ββ �� −== −

� �� =

�+�

�� βγββ +−= ��'&

��

��

�+

�

γβ

ββ

)

��'&

≤

−=

Regularización

� Ridge Regression

� Consideremos la descomp. SVD de X=UDV´

( ) ��'& �� −⋅+= γβ

�� −=β

( ) +

+

+�� ,�, ⋅=�=�

��β ( ) +

+

+

+

+

��'& ,�,�

�⋅⋅

��

�

�

��

�

�

+=�

=��

�

��γ

β

Regularización

� Regularización selecciona mejores direcciones

� Se puede hacer directamente, por ejemplo PLS

( )�+-

��-

+

�

<∀==

��

��

αα

( )�+-

��./��-

+

�

<∀=⋅=

��

��

ααα

Regularización

� Redes Neuronales

�

�

�

��

"

�

�

��""�� = =

��

��

�+��

��

�+= � βαασββα

&

&

&

+=

+=

��

��

#σ

Regularización

� Back-Propagation

� Dado que la minimización del funcional anterior es un problema mal condicionado, la estabilidad de las soluciones obtenidas no esta garantizada

( )( )��= =

−==�

�

$

�

��

�� θθθ

θ

"�

)

)

"�

)

"�

�

βθηββ

∂∂−= − ��

�"

)

�"

)

�"

�

αθηαα

∂∂−= − ��

Regularización

� Regularization by weight-decay

� Notemos que si los pesos son pequeños, una sigmoidal es aproximadamente lineal: salida del modelo lineal se penaliza!

�� %0�1�� &" ⋅γ

�� +=�"

�"

"�

�"�% �� αβ �� ++

+=

�" �"

�"

"� "�

"��%�

�

�

�

��

αα

ββ

12

Regularización

� Regularization by output smoothing

� Las integrales pueden ser aproximadas por medios estándar (por ejemplo trapezoidales).

�� %0�1�� &" ⋅γ

�

��+�� "��% −=

Regularización� Supongamos que en vez de observar la funcion que

queremos aproximar f, observamos y

� Entonces es posible mostrar que bajo condiciones de regularidad sobre las funciones de activación, y para elecciones apropiadas de secuencias de de y´s convergentes son mapeadas a funciones f´s convergentes a f, por ambos métodos.

Detalles: Burger, Neubauer. Analysis of Tikhonov Regularization for Function Approximation by Neural Networks.

ε+= ��

γ

Estimación del Error Esperado

� En casos con gran cantidad de datos, el approach típico consiste en dividir el conjunto en 3 partes

� En la práctica no podemos desperdiciar datos

Train Validation Test

Early Stopping

Validation set

Training epochs

Early Stopping

� Justificación en NN: Si partimos de pesos cercanos a ceros el modelo es aproximadamente lineal.

� A medida que entrenamos el modelo se hace menos lineal, es decir, más complejo.

� Detener este crecimiento observando el error de validación.

� Al margen: otra técnica ampliamente utilizada para prevenir overfitting en redes neuronales es entrenar con ruido aleatorio. Es posible mostrar que bajo niveles de ruido moderados y parámetros de regularización pequeños las técnicas son equivalentes

Cross-validation

� Ampliamente el método más utilizado� K-fold cross-validation

� dividir el conjunto de datos en K bloques. � Para un bloque k, retirar el bloque, entrenar con el resto de los

datos el modelo y medir el error en el bloque faltante. � Repetir esto con todos los bloques� La media de los errores es un estimador del error esperado

13

Cross-validation

� Formalmente:

� Es posible usar cross-validation para seleccionar el parámetro de regularización.

� ¿Qué valor de K utilizar?

��

��

��=

−=�

�

�

��

� ��

.� αα

Función obtenida entrenandosin el bloque que contiene a i

Cross-validation

� Formalmente:

� Es posible usar cross-validation para seleccionar el parámetro de regularización.

� ¿Qué valor de K utilizar?

��

��

��=

−=�

�

�

��

� ��

.� αα

Función obtenida entrenandosin el bloque que contiene a i

Cross-validation Cross-validation

� En general un gran valor de K genera un estimador poco sesgado del error de predicción, pero con alta varianza.

� Con K=n crossvalidation se denomina leave-one-out crossvalidation CVloo. Costoso.

� Si la curva de aprendizaje tiene una pendiente elevada, es más seguro usar CVloo. En otro caso usar K=10,5.

� Generalized Cross-Validation

��==

−��

�

�

��

�

�

−=�=

�

� ��

��

�

�

�

�

��

��

�

�

�

�

�

��

��

αα

Bootstrap� Método general para estimar la distribución de un

estimador y sus momentos.

Bootstrap

� Para estimar el error de predicción: remuestreamos con reemplazo la muestra original hasta obtener n observaciones.

� Esto se repite B veces para obtener B replicaciones bootstrap de la muestra original.

� Entrenamos el modelo con cada replicación� Medimos el error de cada modelo obtenido sobre la

muestra original.

��=

=2

�

�

�

2

�2//) ��

��

+ ��

�

14

Bootstrap

� Este estimador tiende a ser optimista� Ejemplo: Modelo knn-1 con 2 clases independientes de x� Error esperado real: 0.5, Error Boot: 0.5 x 0.368 = 0.184 � Idea: considerar solo las observaciones que cada modelo

no ha visto, imitando a CV.

��

�� +

�

�� −∈=

−=�.2

�

2

�

�

��

��.�

��

Bootstrap

� El numero medio de observaciones diferentes en una muestra bootstrap es 0.632 x n, es decir, parecido CV con K=2!! Alto Bias (upward).

� Este estimador tiende a ser pesimista� Idea: combinar uno pesimista y uno optimista

� Buen estimador en la práctica

��,-�� ,-��-,%�� &" +=

Ensembles

� Otra idea para controlar complejidad: construir un modelo haciendolo crecer gradualmente mediante ensamblaje de pequeñas piezas.

� ¿cómo elegirlas? ¿cómo combinarlas?

3� 3�

4�

3�

4�

5�

�� ⊕=

�

Ensembles Modulares

4

��

��

� −= ��

�� 3�

4�

5�

6�

G

3�

4�5�

6��

��

��

∂∂=

�

��

��

∂∂=�

Ensembles no-modulares

� La clave es que las máquinas compensen sus errores mutuamente (exhiban diversidad constructiva)

3� 3�

4�

3�

4�

5�

�

�

� �7( �=

�

��≠=

−−+−=−+�

+��

)

�

�� 7��7(��

�

��

Ejemplo: Boosting

� Idea: Manejar pesos por ejemplo

� Ajustar los pesos de cada ejemplo para dar más importancia a aquellos puntos mal clasificados

��8) (peso del ejemplo i tiempo t)

�� 8�8 ))) −− ⋅= β (ajuste)

15

Ejemplo: Boosting

� Construcción adaptiva de las máquinas

� Resultado clave: si las máquinas son un poquito mejor que aleatorias, el resultado mejora exponencialmente con el número de máquinas

3�

3� 4� 5��

4�3β 5�

4β��"�� +�+ )) −−= αβ

Ejemplo: Boosting� Boosting como Gradiente Funcional

3�

4�

5�

6�

9�

�� 3−∇ ��

�=

=�

�

��

��

3

3 ��

Cambiando R podemos obtener “cualquier boosting”!!

Ejemplo: Bagging

3�3� 4� 5�

�

4�3β 5�

4β

3�3� 4� 5�

�

4� 5�

�

bootstrap

Ejemplo: Bagging

� ¿Porqué Bagging funciona? � Explicación original (Breiman): Bajo ciertas condiciones es

posible mostrar que Bagging logra reducir la varianza del estimador original sin incrementar sustancialmente su bias

��

�� =−=

( ) ��

�� ++= σ

Diferencia esperada entre predicción y valor verdadero

Variabilidad de la estimación

Ejemplo: Bagging

� Nuevas perspectivas (Poggio et. al): bagging mejora la estabilidad del algoritmo base

� Estabilidad CVloo

� Si el algoritmo original es débilmente estable, bagging logra convertir el algoritmo original en fuertemente estable

�� ∀∈∀ � α≤−∈

�� :�: ��

��

��

�=�

�2�''

αα

Ejemplo: Bagging

� Nuevas perspectivas (Grandvalet): bagging funciona aún sin reducir la varianza. Su efecto principal es ecualizar la influencia de los ejemplos.

� La probabilidad de que un punto aparezca en una muestra bootstrap es app. 0.632. Es decir, app. la mitad de los predictores no tienen en cuenta un punto en particular.

� Puntos “comunes” aparecen en grupos. Remover uno, deja el modelo app. igual.

� Los puntos más castigados son aquellos cuya remoción del conjunto de aprendizaje es altamente inestabilizadora.

16

Nuevos algoritmos

� Si la idea anterior es correcta, la independencia de los learners característica de bagging no es importante.

� Idea: combinar métodos que promuevan una cooperación explícita de los learners en un ensemble, con la potencia estabilizadora de bagging.

� Ejemplo: Learning with Negative Error Correlation

��≠=

−−+−=−+�

+��

)

�

�� 7��7(��

�

��

�≠

−−+−=+�

+�++ �� λ

Coupled Bagging

�−+8�−+� +� �++�

�

+8 �++8

�

bootstrap

�≠

−−+−=+�

+�++ �� λ pero sobre +8

� Idea: Introducir visibilidad entre learners y entrenarlos para cooperar explícitamente

Locally Coupled Bagging

�∈

−−+−=+��

+�++ �� λ sobre +8

� Idea: Imponer una función de vecindad sobre el conjunto de máquinas de manera de permitir sólo visibilidad parcial sobre otros learners

Algunas fuentes

� T. Hastie, R. Tibshirani, J. Friedman: The elements of statistical Learning, Springer, 2001

� T. Mitchell: Machine Learning, McGraw-Hill, 1997� B. Scholkopf, A. Smola: Learning with Kernels: Support

Vector Machines, Regularization, Optimization and Beyond, MIT Press, 2002

� V. Vapnik. Statistical Learning Theory. Wiley, � T. Poggio, R. Rifkin, S. Mukherjee, P. Niyogi: General

conditions for predictivity in learning theory, Nature Vol. 428, S. 419-422, 2004

Fin.

aprendizaje automáticohallende/bajadas/redes/apuntes%20curso%20ann... · 6 teorema de equivalencia...

Documents