Author: Ariana Talamantes Alvarez

Aprendizaje basado en ejemplos mediante el grafo de semi-espacios proximales

Instance-based learning using the half-space proximal graph

Ariana Talamantes Alvarez (2021)

El problema de clasificación en el aprendizaje automático consiste en identificar a cuál, de entre un conjunto de categorías, pertenece una nueva observación. El aprendizaje basado en ejemplos (Instance-based learning, en inglés) es un tipo de aprendizaje automático que utiliza los objetos almacenados en una base de datos para predecir la clase de objetos que no se han visto. Su implementación no necesita de entrenamiento y se adapta a los datos que se tienen disponibles, por lo que resulta útil para problemas donde no se tiene una distribución no estacionaria. El filtrado y clasificación de correo es un ejemplo de clasificación donde la distribución de las clases no es estacionaria, ya que co-evolucionan el spammer y el detector, con lo que la clasificación cambia con el tiempo. Hay esencialmente un algoritmo de aprendizaje basado en ejemplos y es el algoritmo de k vecinos más cercanos o kNN (k nearest neighbors, en inglés) el cual es muy popular por su simplicidad. La principal desventaja de kNN es que cuenta con el hiperparámetro k que es muy difícil de sintonizar. En los últimos años se han propuesto varios métodos para solucionar este problema pero no se ha llegado a un resultado conclusivo en la literatura. En el presente trabajo se presenta el primer algoritmo de aprendizaje basado en ejemplos que no necesita de parámetros a sintonizar. La clasificación se hace mediante el uso del grafo de semi-espacios proximales o HSP (Half Space Proximal, en inglés). Su desempeño se compara con el estado del arte y los resultados obtenidos muestran que el clasificador HSP obtiene mayor exactitud de clasificación que kNN, con cualquier k, en una variedad de ejemplos de datos de altas dimensiones, aún cuando se toman en cuenta diferentes reglas de votación. Más aún, la mejora se mantiene incluso cuando se implementa una heurística para aproximar el clasificador HSP y se utiliza un índice probabilístico para acelerar las consultas.

The classification problem in machine learning consists in designating the class that best fits a new observation, given a set of possible classes. Instance-based learning refers to a family of machine learning algorithms predicting the class of new problem instances by comparing them to instances stored in memory. Its implementation does not need training and adapts to available data, therefore it is useful for problems with a non-stationary distribution. Mail filtering and classification is an example of classification where the class distribution is non-stationary, since the spammer and the detector co-evolve, the classification changes over time. There is essentially one instancebased learning algorithm and it is the k Nearest Neighbors rule or kNN, which is quite popular for its simplicity. The main disadvantage of kNN is the hyperparameter k, which is very difficult to tune. In recent years, various methods have been proposed to solve this problem but a conclusive result has not been reached in the literature. The present work presents the first instance-based learning algorithm without tuning parameters. The classification is done through the use of the Half-Space Proximal Graph or HSP. Its performance is compared to the state of the art. The results obtained show the HSP classifier achieves higher classification accuracy than kNN, for any given k, in a variety of high-dimensional datasets, even when applying different voting rules. Furthermore, the improvement sticks even when a heuristic is implemented to approximate the HSP classifier and a probabilistic index is used to speed up queries.

Master thesis

aprendizaje basado en ejemplos, grafo de semi-espacios proximales, clasificación, regresión instance-based learning, half-space proximal graph, classification, regression INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES ENSEÑANZA CON AYUDA DE ORDENADOR ENSEÑANZA CON AYUDA DE ORDENADOR