Universidad Central "Marta Abreu" de Las Villas

Facultad de Matemática Física y Computación

Departamento de Ciencia de la Computación

clasificación basada en instancias mediante el

aprendizaje de la función de distancia a partir de

restricciones apareadas locales

Autor: bac nguyen cong

Tutor: dr . carlos morell pérez

2014

Hago constar que el presente trabajo fue realizado en la Universidad CentralMarta Abreu de Las Villas como parte de la culminación de los estudios de laespecialidad de Ciencia de la Computación, autorizando a que el mismo seautilizado por la institución, para los fines que estime conveniente, tanto deforma parcial como total y que además no podrá ser presentado en eventosni publicado sin la autorización de la Universidad.

Los abajo firmantes, certificamos que el presente trabajo ha sido realizadosegún acuerdos de la dirección de nuestro centro y el mismo cumple conlos requisitos que debe tener un trabajo de esta envergadura referido a latemática señalada.

Firma de autorBac Nguyen Cong

Firma de tutorDr. Carlos Morell Pérez

DedicatoriaA mi mamá

We have seen that computer programming is an art,because it applies accumulated knowledge to the world,

because it requires skill and ingenuity, and especiallybecause it produces objects of beauty.

— Donald E. Knuth [Knuth, 1974]

Ser el más rico del cementerio no es lo que me importa,acostarme por las noches pensando que,he hecho algo genial . . .,eso es lo que más me importa.

— Steve Jobs

A G R A D E C I M I E N T O S

A mi tutor Carlos Morell Pérez por todas sus atenciones, apoyo durante larealización de esta tesis, por el tiempo dedicado así como la formación cien-tífica que he adquirido gracias a su dedicación y seriedad en el trabajo.

A mi familia, muy especialmente a mi mamá por su gran apoyo siempre.

A Nghia por confiar en mí y estar siempre a mi lado.

A los profesores de facultad y departamento por eseñarme en todos estosaños.

A mis compañeros tanto vietnamitas como cubanos por los buenos y malosmomentos.

A todos, muchas gracias.

iv

R E S U M E N

En el trabajo se estudia el problema de clasificación basada en instanciasusando el paradigma de aprendizaje de la función de distancia de Mahalano-bis. Se propone un método para construir la función de distancia a partir derestricciones apareadas locales. Los resultados experimentales muestran queel método propuesto para construir la función de distancia logra un buenresultado en el algoritmo de los K vecinos más cercanos. Se plantean cues-tiones importantes en la escalabilidad y el grado requerido de supervisiónde métodos existente de aprendizaje de distancia de Mahalanobis. Se realizóla incorporación del método de aprendizaje de distancia a la plataforma WE-KA. También se incorporó una adaptación del algoritmo de los K vecinos máscercanos para dar solución a problemas de clasificación usando distancia deMahalanobis. La incorporación de este método de aprendizaje de distanciaes de vital importancia para los investigadores del campo del AprendizajeAutomático al contar con nuevos métodos para dar solución a problemas declasificación.

v

A B S T R A C T

In this work the classification problem based on instances using the distan-ce metric learning paradigm is studied. A method for building the distancemetric starting from matched up local restrictions is proposed. The experi-mental results show that with the method proposed the building of distancemetric achieves a good result in the algorithm of k nearest neighbours. Weraise important issues on scalability and the required degree of supervisionof existing distance metric learning methods. The method of distance me-tric learning was incorporated to the platform WEKA. Furthermore an adap-tation of the algorithm of k nearest neighbours was incorporated to givesolution to classification problems using Mahalanobis distance. The incorpo-ration of this method of distance metric learning has a high importance forthe researches on the field of machine learning because this provides newmethods to give solution to classification problems.

vi

TA B L A D E C O N T E N I D O S

Introducción 1

1 aprendizaje de la función de distancia 7

1.1 Breve reseña sobre el Aprendizaje Automático 7

1.2 Solución del problema de clasificación con k-NN 8

1.2.1 Medidas para determinar las instancias similares al pro-blema 10

1.2.2 Ventajas del método k-NN 11

1.2.3 Desventajas del método k-NN 11

1.3 Aprendizaje de la función de distancia como una alternati-va 12

1.3.1 Aprendizaje de la métrica de distancia 12

1.4 Aprendizaje de funciones de distancia global 15

1.4.1 Restricciones por pares 16

1.4.2 Aprendizaje de métrica de distancia global por progra-mación convexa 17

1.4.3 Enfoque probabilístico para aprendizaje de métrica dedistancia global 18

1.5 Aprendizaje de métrica de distancia local 19

1.5.1 Local Linear Discriminative Analysis 19

1.5.2 Neighborhood Components Analysis 20

1.6 Aprendizaje de distancia basado en SVM 21

1.6.1 Large Margin Nearest Neighbour Metrics 22

1.6.2 Information Theoretic Metric Learning 24

1.7 Conclusiones parciales del capítulo 26

2 desarrollo del método de aprendizaje de la distancia

mahalanobis basado en una perspectiva de inferencia

estadística 27

2.1 Desarrollo 27

2.1.1 Estimador de matriz de covarianza 32

2.1.2 Ball Trees 34

2.2 Análisis de la complejidad computacional 36

2.3 Conclusiones parciales del capítulo 37

3 experimentos y validaciones 38

vii

tabla de contenidos viii

3.1 Configuración de experimentos 38

3.2 Resultados 40

3.3 Conclusiones parciales del capítulo 47

Conclusiones 48

a terminología básica 49

a.1 Distribución gaussiana 49

a.2 Prueba de razón de la función de verosimilitud 50

a.2.1 Razón de la función de verosimilitud 50

a.2.2 Prueba de razón de la función de verosimilitud 50

bibliografía 52

L I S TA D E F I G U R A S

Figura 1 El cóno S2+ de matrices 2× 2 simidefinidas positivas de

la forma

α β

β γ

14

Figura 2 Comparación entre distancia euclidiana y Mahalano-bis 15

Figura 3 Esquema del una entrada de datos antes del entrena-miento (izquierda) contra después del entrenamiento.Fuente: [Weinberger y Saul, 2009]. 23

Figura 4 Base de casos artificiales 28

Figura 5 Base de casos en el espacio transformado encontradopor el método propuesto. 29

Figura 6 Visualización del espacio de diferencia: a) S - espaciode diferencias de los vecinos de la misma clase y b) D- espacio de diferencias de los vecinos de la otra clase,c) y d) son función densidad de distribución en S y Drespectivamente. 30

Figura 7 Idea básica del método propuesto 32

Figura 8 Ball-tree 35

Figura 9 Visualización de la comparación entre exactitud y tiem-po de aprendizaje de los resultados obtenidos en lasTablas 2 y 3. 44

Figura 10 Visualización de la prueba post-hoc Dunn-Bonferronidesde Tabla 5 46

ix

L I S TA D E TA B L A S

Tabla 1 Descripción de los conjuntos de datos. 40

Tabla 2 Resultados obtenidos con la clasificación k-NN y me-diante varias funciones de distancia. 41

Tabla 3 Tiempo (en segundos) de aprendizaje mediante variasfunciones de distancia. 43

Tabla 4 Tabla de Holm / Hochberg con α = 0,05 44

Tabla 5 Resultados obtainidos por KISSNN , Naive Bayes, Sup-port Vector Machine, Multiplayer Perceptron y J48. 46

Tabla 6 Tabla de Holm / Hochberg con α = 0,05 46

x

I N T R O D U C C I Ó N

El Aprendizaje Automático del inglés Machine Learning se define como unsubcampo de la Inteligencia Artificial (IA) que se ocupa de aquellos progra-mas capaces de aprender a partir de la experiencia [Russell y Norvig, 1996].De manera más concreta se desarrollan algoritmos para modelar compor-tamientos a partir de información, se trata de crear programas capaces degeneralizar comportamientos a partir de una información estructurada sumi-nistrada en forma de ejemplos. Es, por lo tanto, un proceso de inducción delconocimiento. En muchas ocasiones el campo de actuación del AprendizajeAutomático se solapa con el de la Estadística, ya que las dos disciplinas sebasan en el análisis de datos. Sin embargo, el Aprendizaje Automático secentra más en el estudio de la Complejidad Computacional de los problemas.Muchos problemas son de clase NP-hard, por lo que gran parte de la inves-tigación realizada en esta rama se enfoca al diseño de soluciones factibles aesos problemas. El Aprendizaje Automático tiene una amplia gama de apli-caciones, incluyendo motores de búsqueda, diagnósticos médicos, detecciónde fraude en el uso de tarjetas de crédito, análisis del mercado de valores,clasificación de secuencias de ADN, reconocimiento del habla y del lenguajeescrito, juegos y robótica [Bishop et al., 2006; Mitchell, 1997].

Entre las problemáticas del Aprendizaje Automático se pueden citar: los pro-blemas de clasificación, asociación, formación de grupos o clustering y laselección de rasgos.

El problema de la selección de rasgos consiste en determinar con cuál sub-conjunto de rasgos de todos los que permiten describir los objetos del do-minio de aplicación se alcanza una mejor eficiencia o eficacia en el procesode aprendizaje, según sea el objetivo que se persigue. La determinación delsubconjunto de rasgos incide de diferentes formas en el aprendizaje, puededisminuir la información necesaria eliminando rasgos irrelevantes, o incre-mentar la precisión del conocimiento descubierto.

La problemática de la clasificación consiste en a partir de un conjunto deaprendizaje conformado por ejemplos del área de aplicación que se trateencontrar un algoritmo que permita clasificar un nuevo caso del dominio.

1

introducción 2

Cada ejemplo se describe por un conjunto de rasgos predictores de distintosdominios y al menos un rasgo objetivo cuyo dominio representa una clase,categoría o grupo del problema en cuestión. De esta forma, el conjunto deaprendizaje se compone por subconjuntos representativos de las diferentesclases del problema y sobre la base de los ejemplos se aprende a que clasepertenece un nuevo ejemplo.

Sin embargo, no siempre el rasgo objetivo del problema es un rasgo discretoque representa a una categoría, pudiera presentarse el caso de que este atribu-to se representa por un valor de dominio continuo. En estos casos estamos enpresencia de un problema de regresión o aproximación de funciones.

El resultado del aprendizaje puede ser conocimiento explícito o implícito. Esexplícito cuando producto del proceso de aprendizaje se obtiene conocimien-to en alguna forma, por ejemplo reglas u operadores; ejemplo de este tipo deaprendizaje es el algoritmo ID3 [Quinlan, 1986] y sus descendientes [Quin-lan, 1993]. Es implícito cuando no se obtiene conocimiento explícito desde elconjunto de ejemplos pero este sirve para que la computadora pueda resol-ver nuevos problemas o alcanzar mejores soluciones; también denominadoaprendizaje perezoso (lazy learning); los algoritmos de aprendizaje basado eninstancias son un ejemplo de este tipo de aprendizaje.

Uno de los métodos clásicos y más simples para clasificación basada en ins-tancias es los k vecinos más cercanos del inglés k-Nearest Neighbour (k-NN)[Cover y Hart, 1967]. La regla de k-NN clasifica cada instancia según la clasemayoritaria entre los vecinos más cercanos que se encuentran en el conjun-to de entrenamiento utilizando una función de distancia o similitud. Por lapropia naturaleza de su regla de decisión, la calidad de la clasificación delmétodo depende de la forma en que se calculan las distancias entre las dife-rentes instancias. Cuando no hay ningún conocimiento previo disponible, lamayoría de las implementaciones de k-NN utilizan la función de distanciaEuclidiana (suponiendo que los ejemplos se representan como entradas vec-toriales). La selección de una función de distancia adecuada es fundamentalpara un buen comportamiento de cualquiera de los algoritmos de clasifica-ción basados en instancias. Las funciones de distancia como la Euclidianaignoran cualquier regularidad estadística que obtenerse a partir del conjuntode entrenamiento. Idealmente, se podría adaptar la función de distancia a laaplicación específica que se desarrolla [Weinberger et al., 2006; Weinberger ySaul, 2009]. Suponga, por ejemplo, que se quiere clasificar imágenes de ros-tros según su edad y según su género. Difícilmente puede ser óptimo utilizar

introducción 3

la misma función de distancia para estos dos problemas, incluso si en ambastareas, las distancias se calculan entre el mismo conjunto de característicasextraídas (por ejemplo, los píxeles, histogramas de color). Motivado por es-tos problemas, un número de investigadores han demostrado que se puedemejorar la efectividad de la clasificación utilizando k-NN mediante el apren-dizaje de la función de distancia a partir de un conjunto de entrenamiento[Xing et al., 2002, 2003; Zhang et al., 2003; Weinberger et al., 2006; Friedman,1994].

La selección de una función de la distancia adecuada es fundamental paramuchos algoritmos de aprendizaje, tales como K-means, k vecinos más cer-canos, y otros. La selección tal función de distancia dicta el éxito o el fracasodel algoritmo de aprendizaje. Recientemente se ha demostrado que, inclu-so una simple transformación lineal de las características de entrada, puedeconducir a las mejoras significativas en la clasificación de k-NN [Weinbergeret al., 2006; Xing et al., 2003; Goldberger et al., 2004; Weinberger y Saul, 2009].Estos métodos funcionan mediante la explotación de información sobre lasdistancias entre las instancias que está intrínsecamente disponibles en losejemplos de entrenamiento. Por ejemplo, en el problema de recuperación deinformación, restricciones del tipo “el documento q es más similar al docu-mento a que al documento b” pueden ser escogidos mediante retroalimen-tación a parir del comportamiento del usuario. Estas restricciones contieneninformación importante para adaptar la función de distancia. En los casossupervisados, las restricciones se pueden inferir a partir de las instancias deentrenamiento partiendo del principio de que “la distancia entre instanciasde la misma clase debe ser más pequeña que la distancia entre instancias declases diferentes”. Los algoritmos existentes para el aprendizaje de la funciónde distancia han mostrado un buen desempeño y se caracterizan por tres re-quisitos básicos: en primer lugar, deben ser lo suficientemente flexibles parasoportar la variedad de restricciones utilizadas por los diferentes paradig-mas; en segundo lugar, el algoritmo debe ser capaz de aprender un funciónde distancia que generaliza bien a los datos de prueba no conocidos conanterioridad y, por último, el algoritmo debería ser rápido y escalable.

En general, los algoritmos para el aprendizaje de las funciones de distanciacasi siempre se traducen en problemas de optimización muy complejos cu-ya solución se encuentra mediante algún algoritmo iterativo que supone unconsumo grande de recursos. Es por ello en esta tesis abordamos el siguienteproblema científico:

introducción 4

¿Cómo aprender una función de distancia de forma eficiente a partir de lainformación contenida en los ejemplos para su uso en un algoritmo de clasi-ficación basado en instancias (k-NN)?

En esta tesis se propone un nuevo enfoque para el aprendizaje de una clasede funciones de distancia, conocida como distancia de Mahalanobis, plan-teando un problema de aprendizaje desde una perspectiva de inferencia es-tadística que tiene una solución exacta. El algoritmo considera dos tipos derestricciones binarias (xi debe ser similar a xj, o no) al igual que sus similaresen la literatura con la diferencia fundamental de que estas restricciones seestablecen entre objetos o instancias cercanos. Al tener una solución exactael método propuesto encuentra la función de distancia mediante el cálculodirecto resultando en un incremento de la eficiencia comparado con otros en-foques que se basan en un tedioso procedimiento iterativo de optimización.El método es, por tanto, escalable para grandes conjuntos de datos. La eficien-cia no puede estar reñida con la eficacia, de modo que el método propuestotambién debe garantizar un comportamiento adecuado en términos de sucapacidad predictiva ante ejemplos no utilizados para el aprendizaje.

preguntas de investigación

• ¿Cuáles algoritmos de aprendizaje de funciones de distancia pudieranconsiderarse para tareas de clasificación?

• ¿Cómo implementar un algoritmo de aprendizaje de métrica de distan-cia para la clasificación basada en instancias?

• ¿Resultaría eficiente un algoritmo de aprendizaje de métrica de distan-cia para la clasificación basada en instancias?

• ¿Qué ventajas puede presentar el método de clasificación propuesto encomparación con otros métodos de clasificación?

Para darle solución al problema científico se planteó el siguiente objetivo

objetivo general

Diseñar e implementar un método de clasificación eficiente y eficaz basadoen el aprendizaje de la distancia de Mahalanobis que utilize la información

introducción 5

contenida en el espacio de diferencias en la cercanía de cada instancia deaprendizaje.

objetivos específicos

1. Estudiar de los métodos existentes basado en el aprendizaje de la dis-tancia Mahalanobis.

2. Desarrollar un método de aprendizaje de una función de distancia parala clasificación basada en instancias.

3. Adicionar el método de clasificación basado en instancia a una platafor-ma de aprendizaje automático existente.

4. Validar el método de clasificación propuesto comparándolo con otrosmétodos de clasificación.

Después de haber construido el marco teórico se formulan las siguientes hi-pótesis de investigación como respuestas a las preguntas de investigación:

hipótesis de investigación

Si se utiliza la información contenida en el espacio de diferencias en la cerca-nía de cada instancia de aprendizaje es posible aprender de forma eficiente-mente una función de distancia que, utilizada en un método de clasificaciónvago, garantize un comportamiento efectivo.

justificación de la investigación

Los métodos de aprendizaje basado en instancias que aprenden una funciónde distancia se han aplicado satisfactoriamente para resolver problema declasificación. Se introduce aquí una estrategia simple pero efectiva para elaprendizaje de distancia dadas restricciones de equivalencia basada en unaperspectiva de inferencia estadística. En contraste con los métodos existentesesta propuesta no requiere de tantas iteraciones, ni es tan costoso; siendo estemétodo sustancialmente más rápido en comparación con otros del estado delarte. Los resultados de desafiantes pruebas de eficiencia de naturaleza diver-

introducción 6

sa permiten demostrar lo antes planteado. Se incluyen pruebas en ambientessin restricciones y clasificación de objetos.

Para una mejor comprensión del trabajo, el mismo ha sido dividido en trescapítulos:

• Capítulo I: Se realiza un estudio para la construcción de un marco teó-rico sobre el aprendizaje de la métrica de distancia y su aplicación enalgoritmos de clasificación basados en instancias.

• Capítulo II: En este capítulo se propone un método que aprende la unamétrica de distancia a partir de inferencia estadística basado en unaprueba de razón de verosimilitud.

• Capítulo III: En este capítulo se evalúa el algoritmo propuesto en variosconjuntos de datos comparando sus resultados con otros algoritmos declasificación. Son realizadas diferentes pruebas estadísticas para evaluarsu rendimiento y demostrar su eficiencia.

1A P R E N D I Z A J E D E L A F U N C I Ó N D E D I S TA N C I A

En este capítulo se realiza un estudio del estado del arte sobre los enfo-

ques y algoritmos de aprendizaje de funciones de distancia. Además, se

profundiza en la clasificación basada en instancias así como en la apli-

cabilidad del aprendizaje de las funciones de distancia a la clasificación.

Se analiza, como caso particular, la clasificación basada en los k veci-

nos más cercanos (del inglés k Nearest Neighbors o k-NN) [Cover y Hart,

1967].

1.1 breve reseña sobre el aprendizaje automático

El Aprendizaje Automático (del inglés Machine Learning) es una rama de laInteligencia Artificial (IA) cuyo objetivo es desarrollar técnicas que permitana las computadoras aprender, o sea, crear programas que puedan, en un sen-tido similar a lo realizado por los humanos, aprender por sí mismos [Simon,1983]. De forma más concreta, se trata de crear programas capaces de genera-lizar comportamientos a partir de información no estructurada suministradaen forma de ejemplos. Es, por lo tanto, un proceso de inducción del cono-cimiento. En muchas ocasiones el campo de actuación del mismo se solapacon el de la Estadística, ya que las dos disciplinas se basan en el análisis dedatos. Sin embargo, el Aprendizaje Automático se centra más en el estudiode la complejidad computacional de los problemas. Muchos problemas sonde clase NP-hard, por lo que gran parte de la investigación realizada en estarama se enfoca al diseño de soluciones factibles a esos problemas.

El Aprendizaje Automático tiene una amplia gama de aplicaciones, incluyen-do motores de búsqueda, diagnósticos médicos, detección de fraude en eluso de tarjetas de crédito, análisis del mercado de valores, clasificación desecuencias de ADN, reconocimiento del habla y del lenguaje escrito, juegosy robótica [Bishop et al., 2006; Mitchell, 1997].

7

1.2 solución del problema de clasificación con k-nn 8

Algunos sistemas de este tipo intentan eliminar toda necesidad de intuicióno conocimiento experto de los procesos de análisis de datos, mientras otrostratan de establecer un marco de colaboración entre el experto y la compu-tadora. De todas formas, la intuición humana no puede ser reemplazada ensu totalidad, ya que el diseñador del sistema ha de especificar la forma derepresentación de los datos y los métodos de manipulación y caracterizaciónde los mismos.

1.2 solución del problema de clasificación con k-nn

La esencia del aprendizaje basado en instancias es retornar como solución aun problema, la solución conocida a un problema similar. En los algoritmosde aprendizaje basados en instancias cada concepto se representa por un con-junto de ejemplos. Cada ejemplo puede ser una abstracción del concepto ouna instancia individual del concepto. Una extensión del aprendizaje basadoen instancias consiste en usar los k ejemplos más parecidos en lugar del máscercano, lo cual es apropiado cuando los ejemplos se describen mediante da-tos mezclados, no sólo mediante rasgos con dominio real. El método de losk vecinos más cercanos [Cover y Hart, 1967] constituye un algoritmo clásicodentro de esta corriente o forma solucionar problemas y ha sido empleadoen problemas de clasificación y regresión. El método básicamente consiste encomparar la nueva instancia a clasificar con los ejemplos o casos existentesdel problema en cuestión. Para ello, se recuperan los k casos más cercanos,a partir del parecido entre los atributos del nuevo caso con los casos de lamuestra de aprendizaje o entrenamiento. Como resultado del mismo se de-vuelve la clase mayoritaria contenida en los k casos más cercanos a él.

El algoritmo k-NN es un método de clasificación supervisada que sirve paraestimar la función de densidad F(x/Cj) de las predictoras x por cada claseCj. Este es un método de clasificación no paramétrico, que estima el valorde la función de densidad de probabilidad o directamente la probabilidada posteriori de que un elemento x pertenezca a la clase Cj a partir de la in-formación proporcionada por el conjunto de prototipos. En el proceso deaprendizaje no se hace ninguna suposición acerca de la distribución de lasvariables predictoras. El método básicamente consiste en comparar la nuevainstancia a clasificar con los datos o casos existentes (ejemplos de entrena-miento) del problema en cuestión, recuperando los k casos más cercanos, lo

1.2 solución del problema de clasificación con k-nn 9

cual depende de la similitud entre los atributos del nuevo caso con los casosde la muestra de aprendizaje o entrenamiento. Como resultado del mismo seclasifica seleccionando la clase mayoritaria de los k casos o instancias recupe-rados.

Los ejemplos de entrenamiento (X) son vectores en un espacio de caracte-rísticas multidimensional, cada ejemplo está descrito en términos de p atri-butos considerando q clases para la clasificación. Los valores de los atribu-tos del i-ésimo ejemplo (donde 1 6 i 6 n) se representan por el vectorp-dimensional

xi = (xi1, xi2, ..., xip,Ci) ∈ X (1)

El espacio se divide en regiones según las localizaciones y las etiquetas delos ejemplos de entrenamiento. Un punto en el espacio es asignado a la claseC si esta es la clase más frecuente entre los k ejemplos de entrenamiento máscercanos. En la etapa de entrenamiento del algoritmo solamente almacena losvectores característicos y las etiquetas de los ejemplos de entrenamiento. Enla etapa de clasificación, la nueva solicitud (ejemplo del que no se conoce suclase) se representa por un vector en el espacio de características. Se calculanlas distancias entre los vectores almacenados y el nuevo vector, y se seleccio-nan los k ejemplos más cercanos. Finalmente, se le asigna a la solicitud laetiqueta que más se repite en los vectores seleccionados.

Este método supone que los vecinos más cercanos proveen la mejor clasifi-cación y esto se hace utilizando todos los atributos; el problema de dichasuposición es que es posible que se tengan muchos atributos irrelevantes quedominen sobre la clasificación: dos atributos relevantes perderían peso anteotros veinte atributos irrelevantes. Para corregir el posible sesgo se puedeasignar un peso a cada atributo, dándole así mayor importancia a los atri-butos más relevantes. Otra posibilidad consiste en tratar de determinar oajustar los pesos con ejemplos conocidos de entrenamiento. Finalmente, an-tes de asignar pesos es recomendable identificar y eliminar los atributos quese consideran irrelevantes.

Dado un ejemplo x que debe ser clasificado, sean x1, ..., xk los k vecinos máscercanos a x en los ejemplos de aprendizaje, devolver:

f(x)← argmaxv∈Vk∑i=1

δ(v, f(xi)) (2)

1.2 solución del problema de clasificación con k-nn 10

donde

δ(a,b) =

1 si a = b

0 en otro caso(3)

El valor f(x) devuelto por el algoritmo como un estimador de f(x) es solo elvalor más común de f entre los k vecinos más cercanos a x. Si se elige k = 1;entonces el vecino más cercano a xi determina su valor.

1.2.1 Medidas para determinar las instancias similares al problema

Para seleccionar los k vecinos el método requiere de una función que de-vuelva la distancia entre la instancia a clasificar y las instancias almacenadas.Luego se seleccionan las k instancias más cercanas (de menor valor de ladistancia). En el método se pueden utilizar tanto distancias como funcionesde semejanza. Obviamente, si se calculan distancias se seleccionaran los kejemplos de menor distancia al problema, mientras que si se usan funcionesde semejanza se seleccionaran los k ejemplos más similares.

A continuación se describen algunas de las medidas de distancia más utili-zadas. Se considera que x e y son dos vectores de atributos que representanejemplos, m es la cantidad de atributos usados para describir cada ejemploy xa e ya son los valores del atributo a-ésimo en los ejemplos x e y respecti-vamente.

a. Distancia Euclídea:

E(x,y) =

√√√√ m∑a=1

(xa − ya)2 (4)

b. Distancia de Minkowski:

Lp(x,y) =

(m∑a=1

|xa − ya|p

)p(5)

c. Distancia de Chebychev:

Ch(x,y) = max |xa − ya|, a = 1, ...,m (6)

d. Distancia de Manhattan:

M(x,y) =m∑a=1

|xa − ya| (7)

1.2 solución del problema de clasificación con k-nn 11

e. Heterogeneous Euclidean Overlap Metric (HEOM):

HEOM(x,y) =

√√√√ m∑a=1

dh(xa − ya)2 (8)

dh(xa,ya) =

1 si xa o ya son desconocidos

σ(xa,ya) si a es simbólico

EN(xa,ya) =xa − ya

maxa −minapara el resto

σ(xa,ya) =

1 si xa 6= ya0 si xa = ya

1.2.2 Ventajas del método k-NN

Entre las ventajas del método se tiene que es de rápido aprendizaje y sucapacidad de solución a partir de pocos ejemplos.

1.2.3 Desventajas del método k-NN

Sin embargo, el k-NN tiene limitantes tales como:

• Costo computacional que se incrementa con las dimensiones del conjun-to de entrenamiento dado por el incremento del tiempo de respuesta,siendo la complejidad temporal O(nd), tal que O(d) es la complejidadde la distancia usada y O(n) lo que se requiere para explorar todo elconjunto de ejemplos y la complejidad espacial estará dada por la nece-sidad de almacenar los n ejemplos descritos por m rasgos.

• Deterioro de la eficacia en presencia de ruido, o con clases muy solapa-das.

• No trata eficientemente la relevancia.

1.3 aprendizaje de la función de distancia como una alternativa 12

1.3 aprendizaje de la función de distancia como una alter-nativa para mejorar el rendimiento de k-nn

La regla de k-NN clasifica cada instancia por la clase mayoritaria de sus kvecinos más cercanos en el conjunto de entrenamiento. Por la propia natura-leza de su regla de decisión, el rendimiento de la clasificación k-NN dependecrucialmente en la forma en que se calculan las distancias entre las diferentesinstancias. Cuando ningún conocimiento previo está disponible, la mayoríade las implementaciones de k-NN calculan la distancia euclidiana (suponien-do que los ejemplos se representan como entradas vectoriales). Desafortuna-damente, la distancia euclidiana ignora cualquier tipo de regularidad estadís-tica que pueden ser estimadas a partir del conjunto de entrenamiento. Mo-tivado por estos problemas, un número de investigadores han demostradoque la clasificación k-NN se puede mejorar mediante el aprendizaje de unafunción de distancia adecuada [Weinberger et al., 2006; Weinberger y Saul,2008; Chopra et al., 2005; Davis et al., 2007; Xing et al., 2003] . La selecciónde una función de distancia adecuada también es fundamental para otrosalgoritmos de aprendizaje, tales como k-means [Hartigan y Wong, 1979], elprototipo más cercano, y otros. En esta sección, se presentan los problemasgenerales del aprendizaje de funciones de distancia (en inglés Distance MetricLearning) y se presenta una revisión de algunos de los algoritmos más repre-sentativos para evaluar su aplicabilidad a problemas de clasificación basadosen instancias.

1.3.1 Aprendizaje de la métrica de distancia

Para tener una mayor comprensión del aprendizaje de métrica de distanciase exponen primeramente algunos términos básicos.

Definición 1 (Métrica) Un mapeo D : χ× χ → <+ sobre un espacio χ llamadouna métrica si para todos los vectores ∀xi, xj, xk ∈ χ se satisfacen las propiedades:

• D(−→xi ,−→xj ) +D(−→xj ,−→xk) > D(−→xi ,−→xk) (desigualdad triangular).

• D(−→xi ,−→xj ) > 0 (no negatividad).

• D(−→xi ,−→xj ) = D(−→xj ,−→xi ) (simetría).

• D(−→xi ,−→xj ) = 0⇔ −→xi = −→xj (distinguibilidad).

1.3 aprendizaje de la función de distancia como una alternativa 13

En sentido estricto, una función que satisface las tres primeras propiedadespero no la cuarta, se denomina un seudométrica. Sin embargo, para simpli-ficar la discusión, en lo que sigue a menudo se refieren las seudométricascomo métricas, señalando la distinción sólo cuando sea necesario.

Se obtiene una familia de métricas mediante χ por computar la distanciaeuclidiana después de realizar la transformación lineal−→x = L−→x . Esta métricacalcula la distancia cuadrada:

DL(−→xi ,−→xj ) = ‖L(−→xi ,−→xj )‖2 (9)

donde la transformación lineal en la ecuación (9) está parametrizada por lamatriz L. Se puede demostrar que la ecuación (9) define una métrica válida siL es una matriz de rango completo y una seudométrica válida. La distanciacuadrada se puede expresar en el término de la matriz:

M = LTL (10)

Cualquier matriz M formada por esta vía, se garantiza que es semidefinidapositiva (no tiene valores propios negativos). Entonces, la distancia se calculade la siguiente forma:

DM(−→xi ,−→xj ) = ‖L(−→xi −−→xj )‖2

= (L(−→xi −−→xj ))TL(−→xi −−→xj )= (−→xi −−→xj )TLTL(−→xi −−→xj )= (−→xi −−→xj )TM(−→xi −−→xj )

A una seudométrica de esta forma se hace referencia como métrica Mahala-nobis.

DM(−→xi ,−→xj ) = (−→xi −−→xj )TM(−→xi −−→xj ) (11)

Originalmente, este término era utilizado para describir las formas cuadráti-cas en distribuciones gaussianas, donde la matriz M desempeñó el papel dela matriz de covarianza inversa. Aquí se usa M ∈ SD+ , donde SD+ es el cónode las matrices simétricas semidefinidas positivas D×D de valores reales(ver Figura 1). Las distancias en la ecuación (9) y (11) se puede ver como unageneralización de la distancia euclidiana (ver Figura 2). En particular, las dis-tancias euclidianas se recuperan haciendo que M sea igual a la matriz iden-tidad. Una métrica de la distancia de Mahalanobis se puede parametrizar enfunción de la matriz L o de la matriz M. Se tiene en cuenta que la matriz L

1.3 aprendizaje de la función de distancia como una alternativa 14

00.2

0.40.6

0.81

−1

−0.5

0

0.5

10

0.2

0.4

0.6

0.8

1

αβ

γ

Figura 1: El cóno S2+ de matrices 2× 2 simidefinidas positivas de la forma

α β

β γ

define de forma única a la matriz M, mientras que la matriz M define L has-ta la rotación (que no afecta el cálculo de las distancias). Esta equivalenciasugiere dos enfoques diferentes de aprendizaje de distancia. En particular,se puede estimar una transformación lineal L o estimar una matriz positivasemidefinida M. Nótese que en el primer enfoque, la optimización es sinrestricciones, mientras que en el segundo enfoque, es importante para hacercumplir la restricción de que la matriz M sea semidefinida positiva. Aun-que por lo general es más complicado resolver un problema de optimizacióncon muchas restricciones, este segundo enfoque tiene ciertas ventajas que seexploran en las secciones posteriores. Muchos investigadores han propuestoformas de estimar la métrica Mahalanobis con el propósito de calcular dis-tancias en la clasificación k-NN [Weinberger et al., 2006; Weinberger y Saul,2009; Bar-Hillel et al., 2003]. Para la clasificación k-NN, se busca una trans-formación lineal tal que los vecinos más cercanos calculados a partir de lasdistancias en la ecuación (9) compartan las mismas etiquetas de clase.

En los últimos años ha habido una considerable investigación sobre el apren-dizaje de distancia [Bar-Hillel et al., 2003; Zhang et al., 2003; Xing et al., 2002;Davis et al., 2007; Friedman, 1994; Weinberger et al., 2006; Weinberger y Saul,2009]. Dependiendo de la disponibilidad de los ejemplos de entrenamien-to, los algoritmos para el aprendizaje de la función de distancia se puedendividir en dos categorías: aprendizaje de distancia supervisado (en ingléssupervised distance metric learning) y aprendizaje de distancia no supervisa-do (en inglés unsupervised distance metric learning). A diferencia de la mayorparte de los algoritmos de aprendizaje supervisado donde los ejemplos deentrenamiento son etiquetados a partir de sus clases, los ejemplos de entre-

1.4 aprendizaje de funciones de distancia global 15

M = LTL

M ≥ 0

Distancia Euclideana Distancia Mahalanobis

−→xi −−→xj 2 = (−→xi −−→xj )T (−→xi −−→xj )

−→xi −−→xj M = (−→xi −−→xj )TM(−→xi −−→xj )

Cículo de unidad

Figura 2: Comparación entre distancia euclidiana y Mahalanobis

namiento de aprendizaje supervisado de funciones de distancia se conviertenen restricciones por parejas: restricciones de equivalencia –son los pares deejemplos que pertenecen a las mismas clases— y restricciones no equivalen-tes —los pares de ejemplos que pertenecen a diferentes clases—. A su vez,el aprendizaje supervisado de métrica de distancia se puede dividir en doscategorías: aprendizaje de la función de distancia global y local. El primeroaprende la función de distancia en un sentido global, es decir, satisface todaslas restricciones por parejas al mismo tiempo. El segundo método consisteen aprender una función de distancia en un entorno local, es decir, sólo pa-ra satisfacer las restricciones de pares locales. Siendo este especialmente útilpara la recuperación de información y los clasificadores k-NN. Ambos méto-dos están influidos por los ejemplos de datos que están cerca de los ejemplosde prueba. En las siguientes secciones se detallan algunos aspectos tanto delaprendizaje de funciones de distancia global como local.

1.4 aprendizaje de funciones de distancia global

Los algoritmos de esta categoría intentan aprender una función de distanciaque asegure la cercanía de todos los ejemplos de datos de la misma clase yque separe de todos los ejemplos de datos de diferentes clases. El métodomás representativo de esta categoría es el propuesto por [Xing et al., 2002],que formula el aprendizaje de la función de distancia como un problemade programación convexa restringida (en inglés constrained convex program-ming). Este método aprende una función de distancia global que minimizala distancia entre los pares que forman las restricciones de equivalencia su-jetos a la restricción de que los pares no equivalentes están bien separados.

1.4 aprendizaje de funciones de distancia global 16

Esta sección se organiza de la siguiente manera. A continuación se abordanespecificidades de las restricciones por pares. Luego, se revisa [Xing et al.,2002] como un modelo de aprendizaje de métrica de distancia global. Porúltimo, se presentará un modelo probabilístico de aprendizaje de métrica dedistancia.

1.4.1 Restricciones por pares

A diferencia del aprendizaje supervisado típico, donde cada ejemplo de en-trenamiento se anota con su etiqueta de clase, la información de la etiquetaen el aprendizaje de funciones de distancia se especifica generalmente enforma de restricciones por pares: (1) las restricciones de equivalencia, queestablecen que los elementos de un par determinado son similares y debenestar cerca en el espacio métrico inducido por la función de distancia apren-dida, y (2) las restricciones no equivalentes, que indican que dos ejemplosdeterminados son diferentes y por tanto no deben estar cercanos en tal es-pacio. La mayor parte de los algoritmos de aprendizaje tratan de encontraruna función de distancia que mantiene juntos a todos los pares que formanparte de las restricciones de equivalencia, mientras que separa los ejemplosque forman parte de las restricciones no equivalentes. En [Domeniconi y Gu-nopulos, 2001], se ajustan los pesos de los rasgos de forma adaptativa paracada ejemplo de prueba para reflejar la importancia de las características enla determinación de la etiqueta de la clase de los ejemplos de prueba. En[Friedman, 1994], la función de distancia también se modifica en dependen-cia de la región donde se localiza la instancia a clasificar. En [Xing et al.,2002; Bar-Hillel et al., 2003], la función de distancia es explícitamente apren-dida para reducir al mínimo la distancia entre ejemplos de datos dentro delas restricciones equivalentes y maximizar la distancia entre puntos de datosen las restricciones no equivalentes.

Sea C = {x1, x2, x3, . . . , xn} una colección de puntos de datos, donde n es elnúmero de muestras de la colección. Cada x ∈ <m es un vector de datos,donde m es el número de rasgos. El conjunto de restricciones equivalentesdenotados por:

S = {(xi, xj)|xi y xj pertenecen a las mismas clases} (12)

1.4 aprendizaje de funciones de distancia global 17

y el conjunto de restricciones no equivalentes está denotado por:

D = {(xi, xj)|xi y xj pertenecen a diferentes clases} (13)

La función de distancia está denotada por la matriz A ∈ <m×n, y la distanciaentre dos puntos de datos cualesquiera x e y está expresada por:

d2A(x,y) = ‖x− y‖2A = (x− y)TA(x− y) (14)

1.4.2 Aprendizaje de métrica de distancia global por programación convexa

Dadas las restricciones equivalentes en S y las restricciones no equivalentesen D, [Xing et al., 2002] formula el problema del aprendizaje de métricade distancia como un problema de programación convexa [Vandenberghe yBoyd, 1996]:

mınA∈<m×n

∑(xi,xj)∈S

∥∥xi − xj∥∥2As.t A > 0,

∑(xi,xj)∈D

∥∥xi − xj∥∥2A > 1 (15)

Debe tenerse en cuenta que la restricción como un problema de semidefinidapositiva A > 0 es necesaria para garantizar las propiedades de no negati-vidad y de desigualdad triangular entre dos puntos de datos. Aunque elproblema en (15) cae en la categoría de programación convexa, no puedeser resuelto de manera eficiente debido a que no puede ser modelado comoun problema de programación cuadrática ni programación semidefinida. Enprimer lugar, no cae en ninguna clase especial de programación de convexa,tales como la programación cuadrática [Gill et al., 1981] y la programaciónsemidefinida [Vandenberghe y Boyd, 1996]. Como resultado, sólo puede serresuelto por el enfoque genérico, que es incapaz para tomar ventaja de lascaracterísticas especiales del problema. En segundo lugar, como se señaló en[Zhang et al., 2003], el número de parámetros en (15) es casi cuadrático conrespecto al número de rasgos. Esta propiedad es difícil de escalar a un grannúmero de rasgos. Otra desventaja con (15) es que es incapaz de estimar laprobabilidad de que cualquiera de los ejemplos de datos compartan la mismaclase.

1.4 aprendizaje de funciones de distancia global 18

1.4.3 Enfoque probabilístico para aprendizaje de métrica de distancia global

Dada la complejidad de cálculo del problema de optimización originalmentedescrito en [Xing et al., 2003], para simplificar el cálculo, un método probabi-lístico de aprendizaje de distancia global puede ser establecido sobre la basede la fórmula (15).

Siguiendo la idea de [Friedman, 1994], se asume un modelo de regresiónlogística en la estimación la probabilidad de que cualquiera de los dos puntosde datos xi y xj comparten la misma clase, es decir:

Pr(yi,j|xi, xj) =1

1+ exp(−yi,j(∥∥xi − xj∥∥2A − µ))

(16)

Donde

yi,j =

{1 (xi, xj) ∈ S

−1 (xi, xj) ∈ D

El parámetro µ representa el umbral. Dos puntos de datos xi y xj tendránla misma etiqueta de clase sólo cuando su distancia

∥∥xi − xj∥∥2 es menor queel umbral µ. Entonces el logaritmo total de verosimilitud tanto de las restric-ciones equivalentes S como de las restricciones no equivalentes D se expresacomo:

Lg(A,µ) = logPr(S) + logPr(D) (17)

Usando la estimación de máxima verosimilitud, se puede plantear el pro-blema de aprendizaje de métrica de distancia en el siguiente problema deoptimización:

mınA∈<m×n,µ∈<

Lg(A,µ)

s.t A > 0,µ > 0 (18)

La dificultad con la solución de la fórmula (18) se encuentra en la restric-ción semidefinida positiva A > 0. Para simplificar los cálculos, se modela lamatriz A, utilizando el espacio propio de ejemplos. Sea T = (x1, x2, . . . , xn)incluye todos los ejemplos de conjuntos de entrenamiento usados por las res-tricciones en S y D. Sea M = 1

n

∑ni=1 xix

Ti incluye los pares de la correlación

entre dos rasgos cualesquiera. Sea {vi}Ki=1 son los mejores K (K 6 m) vectores

1.5 aprendizaje de métrica de distancia local 19

propios de la matriz M. A continuación, suponga que A es una combinaciónlineal de los K vectores propios:

A =

K∑i=1

γxixTi ,γ > 0, i = 1, . . . ,K (19)

donde (γi, ...,γK) son los pesos no negativos para la combinación lineal.Usando la forma paramétrica (19), la ecuación (18) se escribe como:

mın{γi∈<}Ki=1,µ∈<

Leg({γi}Ki=1,µ ) = −

∑(xi,xj)∈S

log(1+ exp(−K∑k=1

γkwki,j + µ))

−∑

(xi,xj)∈Dlog(1+ exp(−

K∑k=1

γkwki,j + µ))

wki,j = (xi − xj)TA(xi − xj)

s.t µ > 0,γi > 0, i = 1, . . . ,K (20)

El problema de optimización anteriormente descrito es un problema de pro-gramación convexa que puede ser resuelto aplicando el método de Newton.Además, el método anterior permite el aprendizaje no supervisado. Esto esdebido que la matriz M puede ser construida utilizando tanto los datos eti-quetados como los no etiquetados.

1.5 aprendizaje de métrica de distancia local

Además de los algoritmos para el aprendizaje de la función de distancia, va-rios artículos [Domeniconi y Gunopulos, 2001; Friedman, 1994; Zhang et al.,2003] presentan enfoques para aprender las métricas durante la etapa de cla-sificación. Este enfoque permite mejorar los resultados del algoritmo k-NN.En específico, estos enfoques modifican los pesos de rasgos basados en losejemplos de prueba. Estos enfoques se conocen como algoritmos de aprendi-zaje adaptables.

1.5.1 Local Linear Discriminative Analysis

Se revisa brevemente el clasificador Linear Discriminative Analysis (LDA) conJ clases. Este clasificado hace una transformación lineal del espacio de re-presentación de los atributos y para ello encuentra los vectores propios de

1.5 aprendizaje de métrica de distancia local 20

la matriz T = S−1w Sb. Aquí Sw denota la covarianza entre las clases, y Sbdenota la covarianza interclase. S−1w captura la densidad de cada clase, y Sbrepresenta la separación de la clase. Así, los vectores propios principales deT mantendrán los puntos de datos de la misma clases cerca y mientras tantolos puntos de datos de diferentes clases separadas. A continuación, formaruna matriz de transformación ST apilando principales vectores propios de Tjuntos, y los rasgos discriminatorios y se calcula como y = Swx, donde x esla entrada de ejemplo de prueba.

Basado en el estándar LDA, [Domeniconi y Gunopulos, 2001] propone locali-zar tanto Sb y Sw a través de un procedimiento iterativo: Inicializa la funciónde distancia Σ como una matriz idéntica, es decir, se parte de una distanciaEuclidiana. En el primer paso, se calcula Sb y Sw utilizando los puntos quese encuentran en las cercanías del punto de prueba x0 medido por el Σ. Enel segundo paso, el estimado de Sb y Sw se utilizan para actualizar Σ de lasiguiente manera:

Σ = S−1

2w [S

−12

w SbS−1

2w + εI]S

−12

w

= S−1

2w [S∗b + εI]S

−12

w

1.5.2 Neighborhood Components Analysis

El algoritmo Neighborhood Components Analysis (NCA) propuesto en [Gold-berger et al., 2004] aprende una distancia de Mahalanobis para el clasificadork-NN maximizando la validación cruzada leave-one-out. A continuación sepresenta brevemente la idea central de la NCA.

El conjunto de datos etiquetados se denota por L = {((x1, c1), . . . , (xn, cn)}.Para garantizar que la matriz de distancia aprendida sea simétrica y posi-tiva semi-definida, [Goldberger et al., 2004] se asume que Q tiene la formaQ = ATA donde A puede ser cualquier matriz. Esta forma paramétrica ga-rantiza que la distancia entre dos puntos de datos x e y será positiva, dadoel hecho de que d(x,y) = (x− y)TQ(x− y) = (Ax−Ay)T (Ax−Ay).Dado un punto xi, un vecino soft de xi se define por pi,j, que es la probabili-dad para xj para ser seleccionado como el vecino de xi, y comparte la mismaetiqueta de clase con xi. La probabilidad pi,j se define como:

pi,j =exp(−

∥∥Axi −Axj∥∥2)∑k 6=i exp(‖Axi −Axk‖2)

(21)

1.6 aprendizaje de distancia basado en svm 21

El conjunto de puntos que comparten la misma clase con xi se denotadapor Ci = {j|ci = cj}. Entonces, la probabilidad de clasificar correctamentexi se expresa pi =

∑j∈Ci

pij, y el número esperado de puntos clasificadoscorrectamente es f(A) =

∑ni=1 pi. Tomando la derivada de f(A) con respecto

a primer orden, se obtiene:

∂f

∂A= 2A

n∑i=1

pi∑k 6=i

pi,k(xi − xk)(xi − xk)T −∑j∈Cj

(xi − xj)(xi − xj)T

(22)

En lugar de utilizar la exactitud promedio de clasificación, [Goldberger et al.,2004] sugiere el uso de la validación cruzada leave-one-out de la función obje-tivo f(A), es decir:

f(A) =

n∑i=1

log(∑j∈Ci

pi,j)

NCA tiene los siguientes inconvenientes:

a. NCA sufre del problema de escalabilidad ya que su función objetivo sediferencia w.r.t. la matriz de distancia y el número de parámetros enA tiene una dependencia cuadrática del número de rasgos. Por lo tan-to, la actualización de la matriz de distancia alcanzará una dimensiónintratable para problemas medianos.

b. El algoritmo del ascenso del gradiente propuesto por NCA no garantizala convergencia a máximos locales.

c. NCA tiende a sobre-aprendizaje de los datos de entrenamiento si elnúmero de ejemplos de entrenamiento es insuficiente . Esto ocurre amenudo cuando los puntos de datos están representados en el espaciode alta dimensión.

1.6 aprendizaje de distancia basado en svm

Para lograr una buena generalización en clasificación, una buena función dedistancia no solo logra consistencia alta, sino reserva el margen en la fronteraentre las clases diferente. [Weinberger et al., 2006] incorpora incremento má-ximo margen dentro de proceso de aprendizaje de distancia. Además, para

1.6 aprendizaje de distancia basado en svm 22

simplificar computación, SVMs se puede reformular en un problema de pro-gramación semidefinida (SDP). En esta sección, se describe el método LMNN(del inglés Large Margin Nearest Neighbor).

1.6.1 Large Margin Nearest Neighbour Metrics

Weinberger en [Weinberger et al., 2006; Weinberger y Saul, 2009] introdujo unmétodo que aprende una matriz de distancia M para mejorar los resultadosde k-NN conocido por LMNN 1. La intuición es que para cada ejemplo lafunción de distancia debe hacer que sus k vecinos más cercanos de la mismaclase —vecinos-diana— estén más cerca entre si que los ejemplos de clasesdiferentes. El objetivo se compone de dos términos. El primer término mini-miza las distancias entre los vecinos-diana, mientras que el segundo términoes una función de pérdida que penaliza la existencia de ejemplos de clasesdiferentes en la vecindad definida por los vecinos diana más un margen fijo.En lugar de aprender a partir de restricciones apareadas, como en los casosanteriores, este algoritmo emplea ternas (i, j, l) que significan que la distanciaentre los vecinos xi y xj debe ser menor que la distancia entre xi y xj. Segúnlas definiciones anteriores xj sería un vecino-diana y xl un impostor, siemprerelativo al ejemplo xi. Este tipo de restricciones permite tener en cuanta elcomportamiento local del algoritmo de los vecinos más cercanos.

Esto se realiza a través de la siguiente función objetivo:

mın ε(M) =∑j↪→i

[d2M(xi, xj) + µ

∑l

(1− yi,l)ξijl(M)

](23)

El primer término de la ecuación (23) minimiza la distancia entre los vecinosde destino xi, xj, indicado por j ↪→ i. El segundo término denota la cantidadde impostores que invaden el perímetro de i y j. Un impostor l es una en-trada de diferente clases (yil = 0) que tiene una variable de holgura positivaξijl(M) > 0:

ξijl(M) = 1+ d2M(xi, xj) − d2M(xi, xl).

En la Figura 3 se ilustra la idea principal detrás de la clasificación de LMNN.Antes del aprendizaje, un ejemplo cualquiera tiene tantos vecinos-diana co-mo impostores en su vecindad. Durante el aprendizaje, los impostores son

1 El código está disponible en http://www.cse.wustl.edu/~kilian/code/files/mLMNN2.3.

zip

1.6 aprendizaje de distancia basado en svm 23

empujados fuera del perímetro establecido por los vecinos-diana. Despuésde aprender, se crea un margen finito entre el perímetro y los impostores.La Figura 3 muestra la idea donde los errores de clasificación de k-NN enel espacio original son corregidos por el aprendizaje de una transformaciónlineal apropiada.

xixi

perímetro

xj

vecinos objetivos

impostoresxl

Clase 1

Clase 3

Clase 2

εempujar

εhalar

xixi

perímetro

xj

vecinos objetivos

Antes

impostores

xl

Despuésvecinos locales

Figura 3: Esquema del una entrada de datos antes del entrenamiento (izquierda)

contra después del entrenamiento. Fuente: [Weinberger y Saul, 2009].

La función de pérdida en la ecuación (23) es una función convexa de los ele-mentos en la matriz M. En particular, el primer término de la función de pér-dida (penalizando a las grandes distancias entre los vecinos-diana) es linealen los elementos de M, mientras que el segundo término (que penaliza losimpostores) se deriva de la pérdida de articulación convexa. Para formularla optimización de la ecuación (23) se puede utilizar un programa semidefi-nido (SDP por sus siglas en inglés: Semidefinite Program ), sin embargo, pararesolverla, hay que convertirla en una forma más estándar.

Un SDP se obtiene mediante la introducción de variables de holgura queimitan el efecto de la pérdida. En particular, se introducen las variables nonegativas de holgura ξijl para todos las ternas de vecinos-diana (j ↪→ i) y losimpostores −→xl . La variable holgura ξijl > 0 se utiliza para medir el margen en

1.6 aprendizaje de distancia basado en svm 24

que se viola la desigualdad en la ecuación (23). Se introducen las variables deholgura para controlar estas violaciones de margen y obtener el SDP:

Minimizar (1− µ)∑i,j↪→i

(−→xi −−→xj )TM(−→xi −−→xj ) + µ∑i,j↪→i,l

(1− yil)ξijl (24)

sujeto:

(1) (−→xi −−→xl )TM(−→xi −−→xl ) − (−→xi −−→xj )TM(−→xi −−→xj ) > 1− ξijl(2) ξijl > 0

(3) M > 0

Mientras que los SDP en esta forma pueden ser resueltos por los paquetesestándares, los solucionadores de propósito general tienden a decrecer no-tablemente la calidad de los resultados en cuanto aumenta el número derestricciones. Para este trabajo, se implementó un método propio especial,aprovechando el hecho de que la mayoría de las variables de holgura ξijlnunca alcanzan valores positivos. Las variables de holgura ξijl son dispersasporque la mayoría de las entradas −→xi y −→xl están bien separadas con respectoa la distancia entre −→xi y cualquiera de sus vecinos objetivos −→xj . Estos resultanen muy pocas restricciones activas en el SDP. Por lo tanto, se puede lograrun gran aumento de velocidad mediante la resolución de un SDP que sólosupervisa una fracción de las restricciones de margen. Luego se utiliza lasolución resultante como punto de partida para el SDP de interés.

1.6.2 Information Theoretic Metric Learning

En [Davis et al., 2007] adoptaron un enfoque de la teoría de la informaciónpara optimizar la matriz M bajo una amplia gama de posibles restriccionesy el conocimiento previo de la distancia de Mahalanobis 2. Esto se realizamediante la regularización de la matriz M tal que sea lo más cercana posiblede una matriz M0 conocida previamente. Esta cercanía se interpreta comouna divergencia Kullbach-Leibler entre las dos matrices gaussianas corres-pondientes a M y M0 respectivamente. Típicamente, las otras restriccionesserán de la forma dM(xi, xj) 6 u para los pares positivos y DM(xi, xj) > l pa-ra los pares negativos. El equilibrio entre la satisfacción de las restricciones yla regularización se controla en la función objetivo utilizando un parámetro

2 El código está disponible en http://www.cs.utexas.edu/~pjain/itml/download/itml-1.2.

tar.gz

1.6 aprendizaje de distancia basado en svm 25

adicional γ. Los parámetros M0, restricción superior u, restricción inferior ltienen que ser proporcionados.

KL(p(x;M0)||p(x;M) =

∫p(x;M0) log

p(x;M0)

p(x;M)dx (25)

La distancia (25) proporciona una medida fundada de “cercanía” entre dosfunciones de distancia de Mahalanobis y constituye la base problémica delmodelo. Teniendo en cuenta las parejas de ejemplos similares S y parejas dediferente clase D, el problema de aprendizaje de distancia es:

mınKL(p(x;M0)||p(x;M) Sujetos (26)

dM(xi, xj) 6 u (i, j) ∈ SdM(xi, xj) > l (i, j) ∈ D

Se demostró en [Davis et al., 2007] que la función objetivo (26) se puedeexpresar como un tipo particular de la función Divergencia Bregman, quese permite adaptar el método de Bregman [Censor, 1997] para resolver elaprendizaje de métrica. También, se muestra una equivalencia a un proble-ma propuesto low-rank kernel learning [Kulis et al., 2006], lo que permite lakernelización del algoritmo.

KL(p(x;M0)||p(x;M) =1

2Dld(M

−10 ,M−1)

=1

2Dld(M0,M) (27)

donde las matrices M y M0 son de tamaño n×n y

Dld(M,M0) = tr(MM−10 ) − logdet(MM−1

0 ) −n

Se puede aprovechar la equivalencia de (27) para expresar el problema deaprendizaje de distancia (26) de la siguiente manera:

mınM>0

= tr(MM−10 ) − logdet(MM−1

0 ) −n. Sujetos

tr(M(−→xi −−→xj )(−→xi −−→xj )T 6 u (i, j) ∈ Str(M(−→xi −−→xj )(−→xi −−→xj )T > l (i, j) ∈ D

La optimización se basa en la proyección Bregman, que proyecta la soluciónactual en una única restricción a través de la regla de actualización:

Mt+1 =Mt +βMtCijMt (28)

1.7 conclusiones parciales del capítulo 26

1.7 conclusiones parciales del capítulo

El desarrollo de métodos para el aprendizaje de la función de distancia apartir de los datos ha tenido un desarrollo imponente en los últimos años.En su mayoría los enfoques se acaracterizan por formular un problema deoptimización a partir de restricciones que se obtienen de los ejemplos deaprendizaje. El proceso de minimización o maximización de la función obje-tivo que codifica las restricciones se realiza mediante un costoso algoritmoiterativo. Estos métodos, cuando se utilizan de conjunto con un clasificadorvago como el k-NN, permiten incrementar la calidad de la clasificación alcosto de una complejidad computacional alta.

2D E S A R R O L L O D E L M É T O D O D E A P R E N D I Z A J E D E L AD I S TA N C I A M A H A L A N O B I S B A S A D O E N U N AP E R S P E C T I VA D E I N F E R E N C I A E S TA D Í S T I C A

En este capítulo se propone un método para la construcción de la matriz

de Mahalanobis a partir de las restricciones binarias construidas en la

vecindad de cada ejemplo. Se plantean cuestiones importantes en la esca-

labilidad y el grado requerido de supervisión de los métodos de apren-

dizaje de la distancia de Mahalanobis. La estrategia que se introduce es

simple y efectiva, siendo un método directo basado en la inferencia esta-

dística modelando un problema de aprendizaje equivalente en espacio

de diferencias. En contraste con los métodos existentes no se apoya en

problemas complejos de optimización que requieren de un número de

iteraciones muy costoso. De esta manera el método es comparativamen-

te más rápido que otros del estado del arte. Los resultados de desafian-

tes pruebas de eficiencia de naturaleza diversa permiten demostrar el

poder del mismo. Se incluyen pruebas en ambientes sin restricciones y

clasificación de objetos.

2.1 desarrollo

En la figura 4 se muestra un base de casos donde k-NN obtiene un bajorendimiento del por cientos de clasificación correctos 61%. Esta base de casose genera a partir de dos distribuciones guassianas con

µ1 =

−1,25

0,205

,Σ1 =

1,96 −0,55

−0,55 0,16

,µ2 =

0,60,07

,Σ2 =

1,96 −0,55)

−0,55 0,16

y 200 instancias con dos clases y dos atributos. El algoritmo k-NN tiene di-ficultades cuando las instancias de clases distintas están alineadas a amboslados de la superficie de decisión. Este efecto puede disminuirse se se aplicauna transformación lineal del espacio original, el por ciento de clasificacióncorrecto se aumenta a 99,5% ( ver figura 5). Se quiere investigar si es posible

27

2.1 desarrollo 28

obtener información en el espacio de diferencias para obtener la transfor-mación adecuada. En la figura 6 se puede observar cómo se distribuyen lasdiferencias entre un objeto cualquiera y sus vecinos más cercanos de la mis-ma clase. Se puede notar que la función de distribución está centrada en 0 ysu tallo es estrecho. En cambio, la función de distribución de las diferenciasentre un objeto cualquiera y sus vecinos más cercanos de otra clase tiene unaforma más ancha aunque también está centrada en cero. Parece posible apartir de la diferencia entre dos objetos determinar si ambos son de la mismaclase o no. Esta inferencia estadística se puede realizar utilizando una pruebade razón de verosimilitud.

−6 −4 −2 0 2 4−1.5

−1

−0.5

0

0.5

1

1.5

01

Figura 4: Base de casos artificiales

El método propuesto se basa en aprender a partir del espacio de diferenciaspara adaptar una función de distancia de Mahalanobis que posteriormenteserá empleada por el algoritmo k-NN. En principio se trata de lograr, enprimer lugar, que cada instancia xi de la entrada debe compartir la mismaclase yi como sus k vecinos más cercanos de la misma clase. En segundolugar, hay que lograr que los k vecinos más cercanos con clases diferentes auna instancia determinada estén separados de esta. Es específico, se quiereaprender una transformación lineal del espacio de entrada de forma que lasinstancias de entrenamiento satisfacen estas propiedades. Para facilitar esteobjetivo se definen los dos conceptos siguientes:

Definición 2 (k−Vecindad Positiva) k−Vecindad Positiva de la instancia−→x :N+k

(−→x )es un conjunto de los k vecinos más cercanos a −→x en el conjunto de entrenamientocuya clase coincide con la de −→x

2.1 desarrollo 29

−3 −2.5 −2−6

−4

−2

0

2

4

6x 10

−3

01

Figura 5: Base de casos en el espacio transformado encontrado por el método pro-

puesto.

Definición 3 (k−Vecindad Negativa) k−Vecindad Positiva de la instancia −→x :N−k

(−→x ) es un conjunto de los k vecinos más cercanos a −→x en el conjunto de entre-namiento cuya clase no coincide con la de −→x

Nuestro método se basa en aprender a partir de espacio de diferencias enla cercanía de cada instancia de aprendizaje. O sea, a partir de las instanciasde entrenamientos se crea dos espacios de diferencias: espacio de diferenciasnegativas (D) y espacio de diferencias positivas (S). Estos dos espacios con-sisten en las diferencias, componente a componente, de cada instancia consus vecinos de la misma (diferente) clases, es decir, vtxij =

−→xj −−→xi donde −→xjpertenece a la k-vecindad (negativa para caso de D y positiva para caso de S) de −→xi .

S =⋃{−→xij|−→xij = −→xj −−→xi ,−→xj ∈ N+

k (−→xi ), ∀i ∈ [1;N]

}D =

⋃{−→xij|−→xij = −→xj −−→xi ,−→xj ∈ N−k (−→xi ), ∀i ∈ [1;N]

}Desde el punto de vista de la inferencia estadística, la decisión óptima es-tadística sobre si un par (−→xi ,−→xj ) comparte la misma clase o no se puedeobtener por una prueba razón de función de verosimilitud (49). Por lo tanto,se prueba la hipótesis H0 (par (−→xi ,−→xj ) son de la clase diferente) que un par esdiferente en comparación con la alternativa H1 (par (−→xi ,−→xj ) son de la mismaclase):

σ(−→xi ,−→xj ) = log(p(−→xi ,−→xj |H0)p(−→xi ,−→xj |H1)

)(29)

2.1 desarrollo 30

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

1.2

-4 -3 -2 -1 0 1 2 3

(a)

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

-4 -3 -2 -1 0 1 2 3

(b)

−1.5−1

−0.50

0.51

1.5−0.4

−0.2

0

0.2

0.4

0

2

4

6

x1

x2

P

0

2

4

6

P (x1, x2)

(c)

−1.5−1

−0.50

0.51

1.5−0.4

−0.2

0

0.2

0.4

0

2

4

6

8

x1

x2

P

0

2

4

P (x1, x2)

(d)

Figura 6: Visualización del espacio de diferencia: a) S - espacio de diferencias de los

vecinos de la misma clase y b) D - espacio de diferencias de los vecinos

de la otra clase, c) y d) son función densidad de distribución en S y D

respectivamente.

Un valor alto de σ(−→xi ;−→xj ) significa que H0 (yij = 0) es válido. En el casocontrario, un valor bajo significa que se rechaza H0, se acepta H1 (yij = 1) yla pareja es considerado como similar. Para ser independiente de la localidadactual en el espacio de características, modelamos el problema en el espaciode las diferencias por pares (−→xij = −→xi −−→xj ) con media cero y se puede volvera escribir la ecuación (29) :

σ(−→xij) = log(p(−→xij|H0)p(−→xij|H1)

)(30)

Se tiene p(−→xij|H) una función de verosimilitud para una variable −→xij, elloimplica que:

p(−→xij|H) = f(−→xij|H) (31)

2.1 desarrollo 31

donde f(xij|H) es una función de densidad de probabilidad. Suponemos quelos datos se distribuyen según una distribución guassiana con media cero yla matriz covarianza ΣD (yij = 0), ΣS (yij = 1) para simplificar el problema.Al sustituir (31) y (47) en la ecuación (30), se obtiene:

σ(−→xij) = log(f(−→xij|µ;ΣD)f(−→xij|µ;ΣS)

)

= log

1(2π)d/2|ΣD|1/2

exp{−12(−→xij − µ)TΣ−1D (−→xij − µ)}

1(2π)d/2|ΣS|1/2

exp{−12(−→xij − µ)TΣ−1S (−→xij − µ)}

= log

1(2π)d/2|ΣD|1/2

exp{−12−→xijTΣ−1D

−→xij}1

(2π)d/2|ΣS|1/2exp{−1

2−→xijTΣ−1S

−→xij}

= log

(|ΣS|

12

)− log

(|ΣD|

12

)−1

2−→xijTΣ−1D

−→xij +1

2−→xijTΣ−1S

−→xij

= log(|ΣS|

12

)− log

(|ΣD|

12

)+1

2−→xijT

(Σ−1S − Σ−1D

)−→xij (32)

Además, se eliminan los términos constantes de la ecuación (32) para obteneruna forma simplificada:

σ(−→xij) ≈ −→xijT(Σ−1S − Σ−1D

)−→xij (33)

Finalmente, se obtiene la métrica Mahalanobis de distancia que refleja laspropiedades de la prueba de razón de verosimilitud logarítmica

DM(−→xi ,−→xj ) = −→xijTM−→xij (34)

Desde (33), para obtener la matriz M semidefinida positiva, se hace repro-yección de (Σ−1S − Σ−1D ) sobre el cono de las matrices semidefinidas positivasmediante el análisis de los valores propios. Esta proyección se calcula a partirde la diagonalización de (Σ−1S − Σ−1D ). Se expresa:

Σ−1S − Σ−1D = V∆VT

que denota la descomposición de valores propios, donde V es la matriz or-tonormal de vectores propios y ∆ es la matriz diagonal de valores propioscorrespondientes. También podemos descomponer ∆ = ∆−+∆+, donde δ+ =

max(∆, 0) contiene todos los valores propios positivos y ∆− = min(∆, 0) con-tiene todos los valores propios negativos. La proyección de (Σ−1S − Σ−1D ) en elcono de las matrices semidefinidas positivas está dada por:

PS(Σ−1S − Σ−1D ) = V∆+V . (35)

2.1 desarrollo 32

La proyección efectiva trunca los valores propios negativos de la etapa degradiente, haciéndolos igual a cero.

clase 1

clase 2clase 3

diferencia negativa

diferencia positiva

densidad de similitud

densidad de disimilitud

instancia disímil

instancia similar

(xj −−→xi )−→

(xj −−→xi )−→

Figura 7: Idea básica del método propuesto

Algorithm 1 KISSNN

Entrada: K > 0 : número de vecinos, P : conjunto de entrenamiento.Salida: Matriz Mahalanobis M

1: S⇐ Φ {espacio de diferencias positivas }2: D⇐ Φ {espacio de diferencias negativas}3: N⇐ Cantidad de ejemplos4: for i = 1→ N do . Construir S y D5: for J⇐ K do6: S⇐ S

⋃(N+

k [i][j] − P[i])

7: D⇐ D⋃(N−

k [i][j] − P[i])

8: end for9: end for

10: MS ⇐ Estimar (S)11: MD ⇐ Estimar (D)12: M⇐Proyectar al cono positivo de (M−1

S −M−1D )

2.1.1 Estimador de matriz de covarianza

Las matrices de covarianza ΣS y ΣD en (33) se puede obtener mediante elestimador de maxima verosimilitud:

ΣS =1

nS

∑−→xij∈S

−→xij−→xijT (36)

ΣD =1

nD

∑−→xij∈D

−→xij−→xijT (37)

2.1 desarrollo 33

Algorithm 2 Proyectar una matriz a su cono positivo

Entrada: M: Matriz entradaSalida: Mt: Matriz positiva definida

1: M→ V∆VT . eigen-decomposition de M2: ∆→ ∆− +∆+ . Factorizar la matriz diagonal ∆3: { ∆− = mın(∆, 0)}4: { ∆+ = max(∆, 0)}5: Mt ⇐ V∆+V . Proyectar M a su cono positivo

Muchos de los problemas de minimización de la varianza se resuelven invir-tiendo una matriz de covarianza. A veces la dimensión de la matriz puedeser grande. En tales situaciones, el estimador usual “la matriz de covarianzade muestra” no da buen desempeño. Cuando la dimensión de la matriz pes mayor que el número de observaciones n, la muestra de matriz de cova-rianza no es ni siquiera invertible. Cuando el radio p/n es menos de uno,pero no insignificante, la matriz de covarianza de muestra es teóricamenteinvertible, pero numéricamente mal condicionado, lo que significa que in-virtiendo amplifica error de estimación dramáticamente. Para p grande, esdifícil encontrar suficientes observaciones que formulen p/n insignificante.Por lo tanto, es importante desarrollar un estimador bien condicionado dematrices de covarianza para dimensiones grandes.

Si se quiere un estimador bien condicionado a cualquier costo, siempre sepuede imponer alguna estructura de la matriz de covarianza para forzarlo aestar bien condicionado, tales como diagonalidad o un modelo de factores.Pero, en ausencia de información previa sobre la verdadera estructura de lamatriz, esta estructura ad-hoc, en general, estará mal especificada. El estima-dor resultante puede estar tan alterado que puede tener poca semejanza conla matriz de covarianza real. Ningún estimador existente es a la vez biencondicionado y más preciso que la matriz de covarianza de muestra.

La matriz de covarianza de muestra es un estimador eficiente si el espacio delas matrices de covarianza es visto como un cono convexo extrínseca en RD×D.Muchas investigaciones en este campo han demostrado que no son buenosestimadores, y no resisten a la presencia de valores atípicos en el conjuntode datos. Ellos también muestran problemas en la inversión de matriz decovarianza se plantea en caso de que el número de observaciones es menorque el número de variables, es decir, no se puede invertir para calcular lamatriz de precisión. En este modelo se usa un estimador más preciso que

2.1 desarrollo 34

la matriz de covarianza de muestra. Este enfoque fue presentado en [Ledoit,1996]. Ledoit-Wolf estimador reduce la covarianza de la muestra hacia unamatriz de identidad a escala y propuso un coeficiente de contracción que esasintóticamente óptima para cualquier distribución. Que es una combinaciónlineal de la matriz de covarianza de muestra(S) con la matriz de identidad(I):

mınp1,p2

E[||Σ− Σ∗||2

], s.t. Σ∗ = p1 ∗ I+ p2 ∗ S (38)

Para muestras pequeñas, el estimador resultante regularizado Σ∗ se puededemostrar que tiene un mejor desempeño que el estimador de máxima vero-similitud. Además, para muestras grandes, la intensidad de la contracción sereduce a cero, por lo tanto, en este caso, el estimador de la contracción seráidéntico al estimador empírica. Además de una mayor eficiencia de la esti-mación de contracción tiene la ventaja adicional de que es bien condicionadoy siempre definida positiva. La solución de (38) es simple:

Σ∗ =β2

δ2µI+

α2

δ2S (39)

donde α2 = ||Σ− µI||2, β2 = E[||S− Σ||2] and δ2 = E[||S− µI||2].

2.1.2 Ball Trees

Varios autores han propuesto estructura de datos basada en árboles (trees)para mejorar el algoritmo k-NN. Por ejemplos, kd-trees [Moore, 1991], ball-trees [Nielsen et al., 2009; Omohundro, 1989] y cover-trees [Beygelzimer et al.,2006]. Todas estas estructuras de datos explotan la misma idea : para dividirla entrada de datos espaciales en las regiones jerárquicamente anidadas. Lasregiones garantizan que la distancia a partir de un ejemplo de prueba a unejemplo dentro de la región es al menos tan grande como la distancia delejemplo de prueba hasta la frontera de la región. Por lo tanto, para cadaejemplo de prueba, los ejemplos de entrenamiento dentro de la región sepueden descartar como k vecinos más cercanos si el entrenamiento k ya sehan encontrado los ejemplos que están más cerca de la frontera de la región.En este caso, k-NN puede ejecutar sin calcular explícitamente las distancias alos ejemplos de entrenamiento en la región. Esta poda de cálculos de distan-cia a menudo conduce a una aceleración significativa en tiempo de cálculode k-NN. Se ha experimentado con ball-tree [Liu y Yu, 2005], en el que las

2.1 desarrollo 35

xtc r xt − c − r

xt −xixi

xj

xt −xj−→

−→ −→ −→

−→ −→−→ −→

−→

−→

Figura 8: Ball-tree

regiones son hiper-esferas.

La figura 18 ilustra la idea básica detrás de ball-tree. Si el conjunto S de

ejemplos de entrenamiento está encapsulado dentro de una bola con el centro−→c y radio r , tal que: ∀−→x ∈ S :

∥∥−→x −−→c∥∥ 6 r, entonces para cualquier

ejemplo de prueba −→xt se puede acortar la distancia a cualquier ejemplo deentrenamiento dentro de la bola por el siguiente expresión :

∀−→xi ∈ S,∥∥−→xt −−→xi∥∥ > max(

∥∥−→xt −−→c ∥∥2 − r, 0) (40)

Ball-tree explotan esta desigualdad para construir una estructura de datosjerárquica. La estructura de datos se basa en forma recursiva dividiendo losejemplos de entrenamiento en dos conjuntos disjuntos. Los conjuntos estánencapsulados por hiper-esferas (o "bolas") que puede traslapar parcialmente.Los ejemplos de entrenamiento son recurrentemente divididos en gruposcada vez más pequeños hasta que ningún conjunto de la hoja contiene másde un número predefinido de ejemplos.

A partir de esta estructura de datos jerárquica, los k vecinos más cercano deun ejemplo de prueba pueden ser encontrados en una búsqueda basada en elárbol primero en profundidad. Cada nodo en el árbol tiene una hiper-esferaasociado que encierra los ejemplos de entrenamiento almacenados por susdescendientes. La búsqueda k-NN ejecuta por recorrer el árbol y la distanciase calcula de un ejemplo de prueba al centro de hiper-esfera de cada nodo.El árbol es recorrido por sub-árboles descendiente en orden de esta distancia.Antes de descender un subárbol, la ecuación (40) se comprueba para determi-nar si ejemplos de entrenamiento en la subárbol más lejos que los k vecinosmás cercano estimados actualmente. Si esto es cierto, el subárbol se poda des-de la búsqueda sin más cálculos. Cuando se alcanza un nodo hoja, todos los

1 Fuente [Weinberger et al., 2006]

2.2 análisis de la complejidad computacional 36

ejemplos de entrenamiento en el nodo hoja se comparan con los k vecinosmás cercano se estima en la actualidad, y las estimaciones son actualizarácuando sea necesario. Tenga en cuenta que los ball-tree soportan consultasexactas para la búsqueda de k-NN.

2.2 análisis de la complejidad computacional

Se analiza el desempeño computacional de KISSNN desde punto de vistateórico de complejidad. La fase de entrenamiento de KISSNN puede ser di-vidido en 4 pasos siguientes:

• La construcción del espacio de diferencias positivos tiene una compleji-dad

C∑i=1

Θ(Hi log2Hi +HiV+ logHi) (41)

• La construcción del espacio de diferencias negativas tiene una comple-jidad

C∑i=1

Θ(Mi log2Mi +MiV− logMi) (42)

• Estimación la matriz Mahalanobis tiene una complejidad

Θ(D2V+N+D2V−N) (43)

• Proyectar la matriz Mahalanobis en su cóno positivo tiene una comple-jidad

Θ(D3) (44)

dónde,

D dimensión del conjunto de entrenamiento

N número de instancias en el conjunto de entrenamiento

V+ tamaño de la vencidas positiva

V− tamaño de la vecindad negativa

C conjunto de las clases {1, 2, ..., |C|}

Hi número de instancias que cuya clase es i

Mi número de instancias que cuya clase es diferente que i

2.3 conclusiones parciales del capítulo 37

Tiempo de entrenamiento total, considerando el peor caso en la cual Hi = Ny Mi = N, ∀i = 1, ...,C sería:

C∑i=1

Θ(Hi log2Hi +HiV+ logHi) +C∑i=1

Θ(Mi log2Mi +MiV− logMi)+

Θ(D2V+N+D2V−N) +Θ(D3)

=Θ(CN log2N+CNV logN) +Θ(D2VN) +Θ(D3)

Si se considera razonablemente que los valores de V y C son pequeñoscomo ocurre en la práctica para los datos grandes, la complejidad seríaΘ(N log2N)

2.3 conclusiones parciales del capítulo

Se introdujo aquí una estrategia simple pero efectiva para el aprendizaje dedistancia dadas restricciones de equivalencia basada en una perspectiva deinferencia estadística. Como resultado, se desarrolla un nuevo procedimien-to que incluye: El cálculo directo de la función de distancia de Mahalanobisevadiendo así el uso de procedimientos de optimización que pueden resultarcostosos. El uso de de un estimador regularizado de las matrices de cova-rianza que garantiza su inversibilidad a la vez que está bien condicionado.El empleo de estructuras de datos del tipo ball-tree se integra de maneranatural con el nuevo método permitiendo disminuir considerablemente eltiempo de aprendizaje. La complejidad temporal del método es polinomialΘ(N log2N).

3E X P E R I M E N T O S Y VA L I D A C I O N E S

Con el objetivo de comparar la eficiencia y eficacia del método de apren-

dizaje de distancia propuesto se diseñaron experimentos que incluyen la

comparación de este con otros métodos. En particular se realizaron dos

comparaciones; la primera de ellas confronta el método con el LMNN,

ITML —descritos anteriormente— y la distancia euclidiana. Adicional-

mente se realiza una segunda comparación con los algoritmos clásicos

en Machine Learning.

3.1 configuración de experimentos

Para este estudio se emplearon conjuntos de datos reconocidos internacional-mente, descritos en Tabla 1. Estos 27 conjuntos de datos provienen del depósi-to de datos para aprendizaje automático disponibles en el KEEL 1(KnowledgeExtraction based on Evolutionary Learning).

Para el primer experimento, la base de pruebas empleada para la compa-ración fue el Matlab. Asimismo, los métodos LMNN, ITML y el euclidianoutilizados en los experimentos fueron implementados en Matlab.

Para el segundo experimento, se implementa KISSNN en el ambiente Waika-to Environment for Knowledge Analysis (WEKA) [Witten y Frank, 2005]. WEKAfue extendido con un nuevo tipo de datos y una nueva métrica de distan-cia KISSNN . Se compara KISSNN con los algoritmos clásicos en MachineLearning: Naive Bayes [John y Langley, 1995], Support Vector Machine [Platt,1999], árbol de decisión J48 [Quinlan, 1993] y Multilayer-perceptron [Hammery Villmann, 2003] implementados también en WEKA.

El comportamiento del algoritmo k-NN depende de la elección del númerode vecinos más cercanos. Para enfocar nuestra atención en el comportamientode las diferentes funciones de distancia, el valor de k permanecerá constante

1 http://sci2s.ugr.es/keel/datasets.php

38

3.1 configuración de experimentos 39

para todos los experimentos, es decir se selecciona k = 5. Los parámetros delos otros algoritmos quedan por defecto y V = 5 para KISSNN .

Durante los experimentos de divide un conjunto de datos en diez partes detamaño similar y con una balance similar entre clases, proceso conocido comoestratificación. Luego, se conforman diez conjuntos de aprendizaje tomandoen cada caso 9 de las particiones creadas. La décima partición se utiliza paraconformar el conjunto de prueba. Cada prueba consiste en crear un conjuntode entrenamiento usando el 90 % de los datos disponibles, y valorar el ren-dimiento sobre el conjunto de prueba (el 10 % restante). El rendimiento se secalcula en términos del por ciento de clasificaciones correctas en cada prueba.En las tablas se reporta el promedio de las diez pruebas con cada conjuntode datos. Todos los algoritmos empleados utilizan las mismas particiones delos datos para evitar cualquier influencia de la forma de particionar sobrealgún algoritmo en particular.

En este capítulo se siguen las recomendaciones [Demsar, 2006] y las extensio-nes presentadas en [Garcia et al.] en relación con los cálculos de los valorescríticos p. Se aplica primeramente un procedimiento estadístico de compa-ración múltiple para probar la hipótesis nula de que todos los algoritmosde aprendizaje obtuvieron los mismos resultados en promedio. Específica-mente, se utilizó la prueba no paramétrica de Friedman considerando el ta-maño de la muestra. Cuando la prueba Friedman rechaza la hipótesis nula,se aplicaron pruebas post-hoc. En primer lugar, se ha aplicado la prueba deBonferroni-Dunn, que define que un método de aprendizaje se desempeñade manera significativamente diferente del mejor método en el ranking siel rango medio correspondiente difiere por lo menos una distancia crítica.Como complemento a la comparación múltiple se utilizó el procedimientostep-down de Holm porque la prueba Bonferroni-Dunn se dice que es menospotente.

dataset #att #num #ord #nom #ins #classes

appendicitis 7 7 0 0 106 2

balance 4 4 0 0 625 3

banana 2 2 0 0 5300 2

bupa 6 1 5 0 345 2

ionosphere 33 32 1 0 351 2

iris 4 4 0 0 150 3

3.2 resultados 40

led7digit 7 7 0 0 500 10

letter 16 0 16 0 20000 26

magic 10 10 0 0 19020 2

monk-2 6 0 6 0 432 2

movement 90 90 0 0 360 15

optdigits 64 0 64 0 5620 10

page-blocks 10 4 6 0 5472 5

phoneme 5 5 0 0 5404 2

pima 8 8 0 0 768 2

ring 20 20 0 0 7400 2

satimage 36 0 36 0 6435 7

segment 19 19 0 0 2310 7

sonar 60 60 0 0 208 2

spambase 57 57 0 0 4597 2

texture 40 40 0 0 5500 11

twonorm 20 20 0 0 7400 2

vehicle 18 0 18 0 846 4

vowel 13 10 3 0 990 11

wdbc 30 30 0 0 569 2

wine 13 13 0 0 178 3

Tabla 1: Descripción de los conjuntos de datos.

3.2 resultados

dataset euclidean itml lmnn kissnn

appendicitis 85.00 86.00 88.82∗ 85.00

balance 86.24 91.84 84.64 96.16∗

banana 89.28 89.34 89.34 89.38∗

bupa 64.28∗ 62.05 61.90 64.18

ionosphere 85.17 87.17 89.75∗ 85.46

iris 95.33 94.67 96.00∗ 95.33

3.2 resultados 41

led7digit 70.40∗ 69.80 69.80 67.40

letter 95.55 95.37 96.72 97.71∗

magic 83.60 83.73 83.74 84.52∗

monk-2 94.75 89.43 97.04∗ 96.54

movement_libras 75.28 74.72 82.50∗ 82.22

optdigits 98.75 98.70 99.04∗ 98.86

page-blocks 95.78 96.03 96.24∗ 96.02

phoneme 87.75 87.75 87.43 87.88∗

pima 73.32 72.93 73.19 73.59∗

ring 69.12 81.54∗ 69.22 74.89

satimage 90.78 90.71 91.28 91.34∗

segment 95.41 96.36∗ 96.23 95.80

sonar 84.52 81.69 84.05 87.90∗

spambase 87.77 87.91 90.08∗ 89.15

texture 98.49 99.29 99.89 99.91∗

twonorm 96.99 97.08 96.97 97.34∗

vehicle 71.75 73.77 77.89 82.51∗

vowel 94.85 91.82 95.35 96.26∗

wdbc 97.01 96.83 96.30 97.71∗

wine 95.49 96.67 97.78∗ 97.71

wisconsin 97.09 96.80 97.10 97.39∗

Friedman Test 1.410×10−4

Rank 3.093 2.981 2.185 1.741

Position 4 3 2 1

Tabla 2: Resultados obtenidos con la clasificación k-NN y mediante varias funciones

de distancia.

Las Tablas 2 y 3 presentan los resultados experimentales con todos los con-juntos de datos seleccionados. En este experimento la precisión es medidacomo el porcentaje de clasificación correcto, y se obtiene para cada conjuntode datos y cada función de la distancia considerada.

3.2 resultados 42

Las dos últimas filas muestran el rango promedio de cada método usan-do las diferentes funciones de distancia (Rank) y su posición en el ranking(Position). Se analizó estadísticamente los resultados para detectar diferen-cias significativas entre los diferentes funciones de distancia y sus exactitudes.La prueba de comparación múltiple de Friedman rechazó la hipótesis nulade que todos los algoritmos tienen el mismo rendimiento en promedio conp = 1,410× 10−4. Por lo tanto, se aplicó la prueba post-hoc Dunn-Bonferroni(en α = 0,10) para detectar cuáles funciones de distancia son equivalentes ala distancia del mejor método. Según la prueba el rendimiento de los dos cla-sificadores difiere significativamente si el rango promedio correspondientees por lo menos la diferencia crítica calculada como:

CD = qα

√k× k+ 1

6N= 2,128

√4× 4+ 1

6× 27 = 0,748

La prueba Dunn-Bonferroni permite ilustrar gráficamente los resultados pormedio de la distancia crítica. La figura 9 permite visualizar fácilmente ladiferencia significativa entre las funciones de distancia al realizar una com-paración entre exactitud y tiempo de aprendizaje. Cualquier algoritmo conel rango fuera del área definida en la figura difiere significativamente del al-goritmo de control. KISSNN se comporta significativamente mejor que ITMLy EUCLIDEAN pero ligeramente mejor que LMNN en la exactitud.

dataset euclidean itml lmnn kissnn

appendicitis 0 3.84 1.07 0.01

balance 0 26.16 7.17 0.04

banana 0 9.07 256.05 1.69

bupa 0 4.28 5.09 0.01

ionosphere 0 3.93 2.6 0.01

iris 0 16.96 1.43 0

led7digit 0 50.22 0.3 0.01

letter 0 163.17 848.34 22.61

magic 0 81.28 610.43 25.46

monk-2 0 6.11 1.85 0.01

movement_libras 0 241.31 5.56 0.05

optdigits 0 117.39 29.02 1.95

page-blocks 0 43.87 181.86 1.83

3.2 resultados 43

phoneme 0 10.41 180.44 1.69

pima 0 4.85 23.53 0.03

ring 0 15.8 388.39 3.27

satimage 0 77.53 278.06 2.35

segment 0 57.05 147.06 0.27

sonar 0 3.48 2.29 0.02

spambase 0 9.84 372.18 1.36

texture 0 99.94 424.61 1.67

twonorm 0 13.72 205.21 3.59

vehicle 0 44.23 30.4 0.04

vowel 0 59.99 23.21 0.05

wdbc 0 5.62 5.94 0.09

wine 0 22.81 1.6 0

wisconsin 0 8.99 2.77 0.02

Friedman Test 4.595×10−11

Rank 1.037 3.481 3.518 1.963

Position 1 3 4 2

Tabla 3: Tiempo (en segundos) de aprendizaje mediante varias funciones de distan-

cia.

Para contrastar los resultados, también se aplica el procedimiento step-downde Holm (ver Tabla 4), que se dice que es más potente que la prueba Dunn-Bonferroni y no hace ninguna hipótesis adicional sobre los datos. La pruebastep-down de Holm en α = 0,05 detectó diferencias significativas con ITML yEUCLIDEAN, pero no con LMNN en la precisión.

3.2 resultados 44

i algoritmo z = (R0 − Ri)/SE p holm

3 EUCLIDEAN 3.847 1.194E-4 0.0333

2 ITML 3.531 4.137E-4 0.05

1 LMNN 1.265 0.206 0.1

Tabla 4: Tabla de Holm / Hochberg con α = 0,05

Los resultados estadísticos permiten concluir que:

• KISSNN muestra resultados ligeramente mejores con respecto a LMNN.

• KISSNN muestra diferencias significativas con respecto a ITML y EU-CLIDEAN.

• KISSNN muestra diferencias significativas con respecto a ITML y LMNNen el tiempo del aprendizaje.

KISSNN

ITMLLMNN

EUCLIDEAN

0 1 2 3 4

1

2

3

4

CD

CD

Exactitud

Tiempo

Figura 9: Visualización de la comparación entre exactitud y tiempo de aprendizaje

de los resultados obtenidos en las Tablas 2 y 3.

3.2 resultados 45

A continuación, se compara KISSNN con los algoritmos clásicos en MachineLearning: Naive Bayes (Bayes) [John y Langley, 1995] , Support Vector Machine(SMO) [Platt, 1999], árbol de decisión J48 (J48) [Quinlan, 1993] y Multilayer-perceptron (MLP) [Hammer y Villmann, 2003] para ponerlo en el contexto dediferentes enfoques. La Tabla 5 presenta resultados experimentales con losconjuntos de datos seleccionados. En este experimento, la exactitud se midiónuevamente como el porcentaje de clasificación correcto; se obtuvo para cadaconjunto de datos y cada clasificador considerado.

dataset kissnn bayes smo mlp j48

appendicitis 87.73∗ 85.91 87.64 85.82 85.91

balance 95.03∗ 90.56 86.39 91.67 78.23

banana 89.64∗ 61.11 55.17 72.09 89.04

bupa 70.15∗ 53.86 58.27 68.99 67.87

ionosphere 84.92 82.05 87.76 92.02∗ 90.60

iris 97.33∗ 94.00 94.67 97.33∗ 94.67

led7digit 71.00 70.80 73.80∗ 70.20 71.20

letter 97.56∗ 64.11 82.34 82.08 87.98

magic 83.43 72.69 79.15 85.87∗ 85.06

monk-2 100.00∗ 92.12 80.57 100.00∗ 100.00∗

movement 79.44 62.78 74.72 80.56∗ 69.72

optdigits 98.81∗ 91.33 98.33 98.26 90.69

page-blocks 96.16 90.00 92.74 96.38 97.06∗

phoneme 90.19∗ 76.04 77.24 80.98 86.42

pima 74.87 75.53 77.34∗ 76.04 74.35

ring 72.84 97.97∗ 76.43 91.07 90.95

satimage 91.00∗ 79.44 86.74 89.37 86.28

segment 97.06∗ 79.78 93.07 95.97 96.62

sonar 81.21∗ 67.88 75.00 80.33 72.12

spambase 91.08 79.68 90.36 90.73 92.93∗

texture 99.85∗ 77.42 98.93 99.82 93.13

twonorm 97.49 97.84∗ 97.77 96.96 85.12

vehicle 81.57 44.80 74.48 82.51∗ 72.59

vowel 84.04 67.07 69.60 84.14∗ 83.13

3.2 resultados 46

wdbc 95.44 92.98 97.89∗ 95.78 94.03

wine 95.49 97.75 98.30∗ 97.75 93.86

wisconsin 96.63 96.19 96.92∗ 96.33 95.90

Friedman Test 2,69× 10−6

Rank 2.07 4.25 3.05 2.43 3.20

Position 1 5 3 2 4

Tabla 5: Resultados obtainidos por KISSNN , Naive Bayes, Support Vector Machine,

Multiplayer Perceptron y J48.

La prueba de Friedman rechazó la hipótesis nula de que todos los clasifica-dores tienen el promedio con p = 2,69× 10−6. El método mejor clasificadofue KISSNN . Por lo tanto, se aplicó la prueba post-hoc Dunn Bonferroni (enα = 0,05) para detectar las diferencias significativas con los otros métodos.La distancia crítica para este nuevo experimento es:

CD = qα

√k× k+ 1

6N= 2,128

√5× 5+ 1

6× 27 = 0,916

No se detectan diferencias significativas entre KISSNN y Multilayer Perceptron.

KISS Bayes

J 48

SMO

MLP

0 1 2 3 4 5

CD=0.916

Figura 10: Visualización de la prueba post-hoc Dunn-Bonferroni desde Tabla 5

i algoritmo z = (R0 − Ri)/SE p holm

4 Bayes 5.16 2.534E-7 0.0125

3 J48 2.67 0.0078 0.0167

2 SMO 2.32 0.02 0.025

1 MLP 0.85 0.40 0.05

Tabla 6: Tabla de Holm / Hochberg con α = 0,05

3.3 conclusiones parciales del capítulo 47

3.3 conclusiones parciales del capítulo

Se mostró a través del estudio experimental con bases de datos internaciona-les el buen desempeño del método KISSNN , lo cual se resume en:

a. El método KISSNN basado en restricciones apareadas locales permitecalcular una función de distancias de Mahalanobis que minimiza lasdistancias de los pares de instancias similares y maximiza las distanciasde los pares de instancias no similares.

b. El método obtiene resultados comparables con los mejores exponentesde su tipo a la vez que lo hace en tiempos significativamente menores.

c. El método obtiene resultados comparables con los obtenidos por méto-dos clásicos del aprendizaje automático de otra naturales. En particularsupera a la mayoría de estos.

C O N C L U S I O N E S

Se plantearon las cuestiones importantes en la escalabilidad y el grado reque-rido de supervisión de los métodos existentes de aprendizaje de distanciaMahalanobis.

Se desarrolló un método para la determinación de una distancia de Mahala-nobis basado en restricciones apareadas locales, que permite obtener buenosresultado cuando se emplean en el algoritmo de los K vecinos más cercanos.Este método incorpora estrategias para lidiar con la complejidad temporalmediante el uso de estructuras de datos que minimizan el tiempo de accesoa los datos. También se incorpora al método un estimador no insesgado dela matriz de covarianza que garantiza su inversibilidad.

Mediante la realización de una validación empírica se ha podido comprobarque el nuevo algoritmo es competitivo con otros semejantes del estado delarte a la vez que los supera en cuanto a eficiencia computacional. El métodono solo es mejor que sus competidores cuando en el ámbito del aprendizajede funciones de distancia sino que cuando se contrasta su comportamientocon algoritmos de clásicos del aprendizaje automático en general obtieneresultados destacados.

El método implementado está disponible en las plataformas MatLab y Wekapara su empleo en el laboratorio de Inteligencia Artificial en particular y laFacultad de Matemática, Física y Computación en general.

48

AT E R M I N O L O G Í A B Á S I C A

a.1 distribución gaussiana

Se introducirá una de las más importantes funciones de densidad de dis-tribuciones en probabilidad para variables continuas, llamada distribuciónnormal o gaussiana.

Para el caso de una variable x de una dimensión, la distribución está definidapor:

ℵ(x|µ,σ2) =1

(2πσ2)12

e−1

2σ2(x− µ)2

(45)

La cual, está presentada por dos parámetros: µ, llamado la media, y σ2, lla-mado la varianza. En (45) se muestra que la distribución gaussiana satisfa-ce:

ℵ(x|µ,σ2) > 0 (46)

Cobra interés la distribución gaussiana definida sobre un vector x D-dimensional,dado por la fórmula:

ℵ(x|µ,∑

) =1

(2π)D2 |∑

|12

e−12 (x−µ)

T∑−1(x−µ) (47)

Donde el vector µ D-dimensional es la media y la matriz D×D la covarian-za.

Ahora si se supone que se tiene un conjunto de observaciones−→x = (x1, x2, x3, . . . , xn)representando N observaciones de la variable −→x . Las observaciones son da-das independientemente desde una distribución gaussiana, en la cual µ y∑

son desconocidos, y se tienen que determinar estos parámetros desde unconjunto de datos.

49

A.2 prueba de razón de la función de verosimilitud 50

Si se supone que los datos son centralizados (la media es nula), la matrizcovarianza se calcula como se muestra a continuación:∑

= E[x2] − E2[x]

= E[x2]

=1

n

n∑i=1

−→xi 2

=1

n

n∑i=1

−→xi−→xi T

Entonces, se obtiene que la matriz covarianza para conjuntos de datos centra-lizados es:∑

=1

n

n∑i=1

−→xi−→xi T (48)

a.2 prueba de razón de la función de verosimilitud

a.2.1 Razón de la función de verosimilitud

Se quieren realizar pruebas en la situación donde el modelo de probabilidadadoptado involucra varios parámetros desconocidos. Se debe denotar un ele-mento del espacio de parámetros por: θ = (θ1, θ2, . . . , θk). Se utiliza la razónde función de verosimilitud, λ(x), definida como:

λ(x) =sup{L(θ; x) : θ ∈ Θ0}sup{L(θ; x) : θ ∈ Θ} , x ∈ <nX (49)

Para una variable x, determina su mejor oportunidad de ocurrencia bajo dela hipótesis H0 y también su mejor oportunidad sobre todos. La razón deestas dos oportunidades no puede exceder una unidad, pero si es pequeña,implica que la hipótesis nula(H0) se rechaza.

a.2.2 Prueba de razón de la función de verosimilitud

Una prueba de razón de la función de verosimilitud consiste en probar H0 :θ ∈ Θ contra H1 : θ ∈ Θ es una prueba con región critica de la forma:

C1 = {x : λ(x) 6 k} (50)

A.2 prueba de razón de la función de verosimilitud 51

Donde k es un número real entre 0 y 1. La prueba tiene un nivel de significa-ción α si el k seleccionado satisface:

sup{P(λ(X) 6 k; θ ∈ Θ0)} = α. (51)

B I B L I O G R A F Í A

Aharon Bar-Hillel, Tomer Hertz, Noam Shental, y Daphna Weinshall. Lear-ning distance functions using equivalence relations. En ICML, tomo 3, págs.11–18. 2003. (Cited on pages 14 y 16.)

Alina Beygelzimer, Sham Kakade, y John Langford. Cover trees for nearestneighbor. En Proceedings of the 23rd international conference on Machine lear-ning, págs. 97–104. ACM, 2006. (Cited on page 34.)

Christopher M Bishop et al. Pattern recognition and machine learning, tomo 1.springer New York, 2006. (Cited on pages 1 y 7.)

Yair Censor. Parallel optimization: Theory, algorithms, and applications. OxfordUniversity Press, 1997. (Cited on page 25.)

Sumit Chopra, Raia Hadsell, y Yann Lecun. Learning a similarity metric dis-criminatively, with application to face verification. En In Proc. of ComputerVision and Pattern Recognition Conference, págs. 539–546. IEEE Press, 2005.(Cited on page 12.)

Thomas Cover y Peter Hart. Nearest neighbor pattern classification. Infor-mation Theory, IEEE Transactions on, 13(1):21–27, 1967. (Cited on pages 2, 7

y 8.)

Jason Davis, Brian Kulis, Suvrit Sra, y Inderjit Dhillon. Information-theoreticmetric learning. En in NIPS 2006 Workshop on Learning to Compare Examples.2007. (Cited on pages 12, 14, 24 y 25.)

Janez Demsar. Statistical comparisons of classifiers over multiple data sets.2006. (Cited on page 39.)

Carlotta Domeniconi y Dimitrios Gunopulos. Adaptive nearest neighbor clas-sification using support vector machines. En Advances in Neural InformationProcessing Systems, págs. 665–672. 2001. (Cited on pages 16, 19 y 20.)

Jerome H Friedman. Flexible metric nearest neighbor classification. Unpu-blished manuscript available by anonymous FTP from playfair. stanford. edu (seepub/friedman/README), 1994. (Cited on pages 3, 14, 16, 18 y 19.)

52

bibliografía 53

Salvador Garcia, Francisco Herrera, y John Shawe-taylor. An extension onstatistical comparisons of classifiers over multiple data sets for all pairwisecomparisons. Journal of Machine Learning Research, págs. 2677–2694. (Citedon page 39.)

Philip E Gill, Walter Murray, y Margaret H Wright. Practical optimization.1981. (Cited on page 17.)

Jacob Goldberger, Sam Roweis, Geoff Hinton, y Ruslan Salakhutdinov. Neigh-bourhood components analysis. En Advances in Neural Information Proces-sing Systems 17, págs. 513–520. MIT Press, 2004. (Cited on pages 3, 20 y 21.)

Barbara Hammer y Thomas Villmann. Mathematical aspects of neural net-works. En ESANN, págs. 59–72. Citeseer, 2003. (Cited on pages 38 y 45.)

J. A. Hartigan y M. A. Wong. A K-means clustering algorithm. AppliedStatistics, 28:100–108, 1979. (Cited on page 12.)

George H John y Pat Langley. Estimating continuous distributions in ba-yesian classifiers. En Proceedings of the Eleventh conference on Uncertainty inartificial intelligence, págs. 338–345. Morgan Kaufmann Publishers Inc., 1995.(Cited on pages 38 y 45.)

Donald E. Knuth. Computer Programming as an Art. Communications of theACM, 17(12):667–673, 1974. (Cited on page iv.)

Brian Kulis, Mátyás Sustik, y Inderjit Dhillon. Learning low-rank kernel ma-trices. En Proceedings of the 23rd international conference on Machine learning,págs. 505–512. ACM, 2006. (Cited on page 25.)

Olivier Ledoit. A well-conditioned estimator for large dimensional covarian-ce matrices. J. Multiv. Anal, 88:365–411, 1996. (Cited on page 34.)

Huan Liu y Lei Yu. Toward integrating feature selection algorithms for clas-sification and clustering. Knowledge and Data Engineering, IEEE Transactionson, 17(4):491–502, 2005. (Cited on page 34.)

Tom M Mitchell. Machine learning. wcb. 1997. (Cited on pages 1 y 7.)

Andrew W. Moore. An intoductory tutorial on kd-trees. 1991. (Cited onpage 34.)

Frank Nielsen, Paolo Piro, y Michel Barlaud. Tailored bregman ball treesfor effective nearest neighbors. En In European Workshop on ComputationalGeometry. 2009. (Cited on page 34.)

bibliografía 54

Stephen M. Omohundro. Five balltree construction algorithms. Inf. téc., 1989.(Cited on page 34.)

John C Platt. Fast training of support vector machines using sequential mini-mal optimization. 1999. (Cited on pages 38 y 45.)

J. Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81–106,1986. (Cited on page 2.)

John Ross Quinlan. C4. 5: programs for machine learning, tomo 1. Morgankaufmann, 1993. (Cited on pages 2, 38 y 45.)

Stuart J Russell y Peter Norvig. Inteligencia Artificial: un enfoque moderno. 1996.(Cited on page 1.)

Herbert A Simon. Why should machines learn? En Machine learning, págs.25–37. Springer, 1983. (Cited on page 7.)

Lieven Vandenberghe y Stephen Boyd. Semidefinite programming. SIAMreview, 38(1):49–95, 1996. (Cited on page 17.)

Kilian Weinberger, John Blitzer, y Lawrence Saul. Distance metric learning forlarge margin nearest neighbor classification. Advances in neural informationprocessing systems, 18:1473, 2006. (Cited on pages 2, 3, 12, 14, 21, 22 y 35.)

Kilian Q. Weinberger y Lawrence K. Saul. Fast solvers and efficient imple-mentations for distance metric learning. En In ICML. 2008. (Cited onpage 12.)

Kilian Q Weinberger y Lawrence K Saul. Distance metric learning for lar-ge margin nearest neighbor classification. The Journal of Machine LearningResearch, 10:207–244, 2009. (Cited on pages ix, 2, 3, 14, 22 y 23.)

Ian H Witten y Eibe Frank. Data Mining: Practical machine learning tools andtechniques. Morgan Kaufmann, 2005. (Cited on page 38.)

Eric P Xing, Michael I Jordan, Stuart Russell, y Andrew Ng. Distance metriclearning with application to clustering with side-information. En Advan-ces in neural information processing systems, págs. 505–512. 2002. (Cited onpages 3, 14, 15, 16 y 17.)

Eric P. Xing, Andrew Y. Ng, Michael I. Jordan, y Stuart Russell. Distance me-tric learning, with application to clustering with side-information. En AD-VANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 15, págs.505–512. MIT Press, 2003. (Cited on pages 3, 12 y 18.)

bibliografía 55

Zhihua Zhang, James T Kwok, y Dit-Yan Yeung. Parametric distance metriclearning with label information. En IJCAI, pág. 1450. Citeseer, 2003. (Citedon pages 3, 14, 17 y 19.)