publication . Master thesis . 2010

Métodos de reducción de la carga computacional de clasificadores multiclase basados en máquinas de vectores soporte

Gonell Sánchez-Seco, Sara;
Open Access Spanish; Castilian
  • Published: 01 Jan 2010
  • Country: Spain
Abstract
En los últimos años se ha experimentado un incremento exponencial de la información que se espera que continúe creciendo en el futuro. Por este motivo es necesaria la organización por medios automáticos de toda esta información para facilitar el acceso, la búsqueda y el análisis de la misma. El aprendizaje automático se encarga de diseñar y desarrollar algoritmos que permitan a los ordenadores ser más eficientes y realizar tareas sin apenas supervisión humana. Este tipo de aprendizaje tratará de producir de manera automática modelos, reglas o patrones a partir de una serie de datos iniciales. El aprendizaje automático está por tanto íntimamente relacionado con campos tan extensos como pueden ser la minería de datos, la estadística o el reconocimiento de patrones, entre otros. En las últimas décadas, dada la gran demanda de estas aplicaciones, se ha visto incrementado de manera notable el desarrollo de nuevas técnicas de aprendizaje automático. En este Proyecto de Fin de Carrera se hará una introducción a los diferentes tipos de aprendizaje automático así como a su aplicación a diversos problemas de clasificación, sobre todo, en entornos multiclase. De entre éstos, se hará especial hincapié en los problemas de clasificación de textos e imágenes de dígitos manuscritos en los que se aplicará una técnica de aprendizaje automático supervisada. Este tipo de técnicas de aprendizaje se refieren a todas aquellas aplicaciones o procesos en los que se dispone de información como son los valores de entrada del sistema y los valores de salida deseados. Uno de los objetivos principales es utilizar la técnica de aprendizaje supervisado basada en máquinas de vectores soporte para realizar varias aproximaciones a problemas de multiclasificación con el fin de resolver algunas desventajas que presentan los algoritmos de combinación de clasificadores tradicionales como pueden ser la complejidad de estos métodos de clasificación así como la elevada carga computacional y temporal en la evaluación de los resultados. En este Proyecto de Fin de Carrera se explican detalladamente las dos aproximaciones propuestas para problemas multiclase en las que se aplicarán diversas estrategias de combinación de clasificadores. Por último, se realizará un estudio comparativo de estos algoritmos y de esta manera poder comprender mejor las características cualitativas y cuantitativas de éstos. ------------------------------------------------------------------------------------------------------------------------------------------------------- In recent years there has been an exponential increase of information that is expected to continue growing in the future. Therefore, it is necessary to organize all this information by automatic means to facilitate access, search and analysis of that information. Machine learning is responsible for designing and developing algorithms that allow computers to be more efficient and perform tasks without human supervision. This type of learning will automatically produce models, rules or patterns from a series of initial data. Therefore, machine learning is closely related to fields such as data mining, statistics or pattern recognition, among others. During the last decades, due the huge demand in these applications, the development of new machine learning techniques there has been increased. This Final Project makes a brief introduction to different types of machine learning techniques and its application to various classification problems, especially in multi-class environments. Among these, special interest will be paid to classification problems of texts or images of handwritten digits in which we apply a supervised machine learning technique. This type of learning techniques refers to all those applications or processes in which some information is available as the input values of the system and the desired output values. One of the main goals is to use a supervised learning technique based on support vector machines to perform several approaches to multi-class problems in order to try to solve some disadvantages that traditional combination of classifiers algorithms have. Some of these disadvantages can be the complexity of these classification methods and a huge temporal and computational cost in the evaluation of the results. This Final Project explains in detail the two approaches that have been proposed for multiclass problems in which we will apply various strategies for combining of classifiers. Finally, we will perform a comparison of those algorithms and so as to comprehend easily the qualitative and quantitative features of these. Ingeniería de Telecomunicación
Persistent Identifiers
Subjects
free text keywords: Aprendizaje automático, Máquinas de vectores soporte, Algoritmos de combinación de clasificadores, Informática
Related Organizations
57 references, page 1 of 4

EJEMPLOS DE PROBLEMAS DE CLASIFICACIÓN................................................................................. 6 Clasificación Automática de Textos .......................................................................................... 6 Clasificación Automática de Imágenes...................................................................................... 6

2.2. CLASIFICACIÓN CON MÁQUINAS DE VECTORES SOPORTE MULTICLASE ........................................ 15 2.2.1. Aproximación Directa ............................................................................................................. 15 2.2.2. División del problema multiclase en subproblemas binarios................................................... 15 2.2.2.1.Caso 1-contra-todos (1-vs-All).............................................................................................. 16 2.2.2.2.Caso 1-contra-1 (Pairwise) ................................................................................................... 17 2.2.2.3.Caso por Grafos Dirigidos (DAG) ........................................................................................ 18

2.2.2.4.Comparación de estas Técnicas de Multiclasificación ..........................................................18

2.3. PRESENTACIÓN DEL ARTÍCULO.......................................................................................................19 2.3.1. Estrategia utilizada: Muestreo basado en incertidumbre ..........................................................19 2.3.2. Método US-MSVM (Uncertainty sampling-based multi-SVM) ..............................................20 2.3.2.1.Fase de entrenamiento ...........................................................................................................20 2.3.2.2.Fase de Prueba ......................................................................................................................22 2.3.3. Resultados Experimentales ......................................................................................................22

LÍNEAS DE TRABAJO FUTURAS....................................................................................................... 82 Generalización del modelo ...................................................................................................... 82 Mejora del método US-MSVM ............................................................................................... 83 Uso de Técnicas de Aprendizaje Semi-supervisadas para SVM ............................................. 83

B.1. MÁQUINAS DE VECTORES SOPORTE SEMI-SUPERVISADAS O TRANSDUCTIVAS (S3VM O TSVM).............................................................................................................................. 87

B.2. APROXIMACIONES MULTICLASE DE LAS MÁQUINAS DE VECTORES SOPORTE SEMI-SUPERVISADAS ........................................................................................................................ 89

Figura 2.3: Transformación de un espacio de entrada linealmente no separable a un espacio linealmente separable mediante una función de kernel ............................................................................................ 13

Figura 2.4: Ejemplo de fronteras para clasificación 1-vs-All para un problema con 4 clases. El patrón * es el nuevo patrón que va a ser clasificado ....................................................................... 16

Figura 2.6: Ejemplo de fronteras para clasificación pairwise para un problema con 4 clases. El patrón * es el nuevo patrón que va a ser clasificado ....................................................................... 17

Figura 2.7: Ejemplo de clasificación para un problema de 4 clases combinando 6 clasificadores pareados El nuevo patrón * es clasificado como de clase 4 por mayoría de votos................................................... 17

Figura 2.8: Ejemplo de clasificación DAG para un problema de 4 clases combinando 6 clasificadores pareados 1-vs-1 en forma de árbol. El nuevo patrón * recorre todos los nodos del árbol y es clasificado como de clase 4 por el nodo hoja........................................................................................ 18

Figura 2.9: Algoritmo de Entrenamiento del método US-MSVM .................................................................. 21

Figura 2.10: Algoritmo de Test del método US-MSVM ................................................................................. 22

Figura 2.11: Fig.3 del artículo que muestra la influencia del número de clasificadores en los resultados de precision y recall para los conjuntos 10Newsgroups (b) y USPS (c) ................................................... 24

57 references, page 1 of 4
Abstract
En los últimos años se ha experimentado un incremento exponencial de la información que se espera que continúe creciendo en el futuro. Por este motivo es necesaria la organización por medios automáticos de toda esta información para facilitar el acceso, la búsqueda y el análisis de la misma. El aprendizaje automático se encarga de diseñar y desarrollar algoritmos que permitan a los ordenadores ser más eficientes y realizar tareas sin apenas supervisión humana. Este tipo de aprendizaje tratará de producir de manera automática modelos, reglas o patrones a partir de una serie de datos iniciales. El aprendizaje automático está por tanto íntimamente relacionado con campos tan extensos como pueden ser la minería de datos, la estadística o el reconocimiento de patrones, entre otros. En las últimas décadas, dada la gran demanda de estas aplicaciones, se ha visto incrementado de manera notable el desarrollo de nuevas técnicas de aprendizaje automático. En este Proyecto de Fin de Carrera se hará una introducción a los diferentes tipos de aprendizaje automático así como a su aplicación a diversos problemas de clasificación, sobre todo, en entornos multiclase. De entre éstos, se hará especial hincapié en los problemas de clasificación de textos e imágenes de dígitos manuscritos en los que se aplicará una técnica de aprendizaje automático supervisada. Este tipo de técnicas de aprendizaje se refieren a todas aquellas aplicaciones o procesos en los que se dispone de información como son los valores de entrada del sistema y los valores de salida deseados. Uno de los objetivos principales es utilizar la técnica de aprendizaje supervisado basada en máquinas de vectores soporte para realizar varias aproximaciones a problemas de multiclasificación con el fin de resolver algunas desventajas que presentan los algoritmos de combinación de clasificadores tradicionales como pueden ser la complejidad de estos métodos de clasificación así como la elevada carga computacional y temporal en la evaluación de los resultados. En este Proyecto de Fin de Carrera se explican detalladamente las dos aproximaciones propuestas para problemas multiclase en las que se aplicarán diversas estrategias de combinación de clasificadores. Por último, se realizará un estudio comparativo de estos algoritmos y de esta manera poder comprender mejor las características cualitativas y cuantitativas de éstos. ------------------------------------------------------------------------------------------------------------------------------------------------------- In recent years there has been an exponential increase of information that is expected to continue growing in the future. Therefore, it is necessary to organize all this information by automatic means to facilitate access, search and analysis of that information. Machine learning is responsible for designing and developing algorithms that allow computers to be more efficient and perform tasks without human supervision. This type of learning will automatically produce models, rules or patterns from a series of initial data. Therefore, machine learning is closely related to fields such as data mining, statistics or pattern recognition, among others. During the last decades, due the huge demand in these applications, the development of new machine learning techniques there has been increased. This Final Project makes a brief introduction to different types of machine learning techniques and its application to various classification problems, especially in multi-class environments. Among these, special interest will be paid to classification problems of texts or images of handwritten digits in which we apply a supervised machine learning technique. This type of learning techniques refers to all those applications or processes in which some information is available as the input values of the system and the desired output values. One of the main goals is to use a supervised learning technique based on support vector machines to perform several approaches to multi-class problems in order to try to solve some disadvantages that traditional combination of classifiers algorithms have. Some of these disadvantages can be the complexity of these classification methods and a huge temporal and computational cost in the evaluation of the results. This Final Project explains in detail the two approaches that have been proposed for multiclass problems in which we will apply various strategies for combining of classifiers. Finally, we will perform a comparison of those algorithms and so as to comprehend easily the qualitative and quantitative features of these. Ingeniería de Telecomunicación
Persistent Identifiers
Subjects
free text keywords: Aprendizaje automático, Máquinas de vectores soporte, Algoritmos de combinación de clasificadores, Informática
Related Organizations
57 references, page 1 of 4

EJEMPLOS DE PROBLEMAS DE CLASIFICACIÓN................................................................................. 6 Clasificación Automática de Textos .......................................................................................... 6 Clasificación Automática de Imágenes...................................................................................... 6

2.2. CLASIFICACIÓN CON MÁQUINAS DE VECTORES SOPORTE MULTICLASE ........................................ 15 2.2.1. Aproximación Directa ............................................................................................................. 15 2.2.2. División del problema multiclase en subproblemas binarios................................................... 15 2.2.2.1.Caso 1-contra-todos (1-vs-All).............................................................................................. 16 2.2.2.2.Caso 1-contra-1 (Pairwise) ................................................................................................... 17 2.2.2.3.Caso por Grafos Dirigidos (DAG) ........................................................................................ 18

2.2.2.4.Comparación de estas Técnicas de Multiclasificación ..........................................................18

2.3. PRESENTACIÓN DEL ARTÍCULO.......................................................................................................19 2.3.1. Estrategia utilizada: Muestreo basado en incertidumbre ..........................................................19 2.3.2. Método US-MSVM (Uncertainty sampling-based multi-SVM) ..............................................20 2.3.2.1.Fase de entrenamiento ...........................................................................................................20 2.3.2.2.Fase de Prueba ......................................................................................................................22 2.3.3. Resultados Experimentales ......................................................................................................22

LÍNEAS DE TRABAJO FUTURAS....................................................................................................... 82 Generalización del modelo ...................................................................................................... 82 Mejora del método US-MSVM ............................................................................................... 83 Uso de Técnicas de Aprendizaje Semi-supervisadas para SVM ............................................. 83

B.1. MÁQUINAS DE VECTORES SOPORTE SEMI-SUPERVISADAS O TRANSDUCTIVAS (S3VM O TSVM).............................................................................................................................. 87

B.2. APROXIMACIONES MULTICLASE DE LAS MÁQUINAS DE VECTORES SOPORTE SEMI-SUPERVISADAS ........................................................................................................................ 89

Figura 2.3: Transformación de un espacio de entrada linealmente no separable a un espacio linealmente separable mediante una función de kernel ............................................................................................ 13

Figura 2.4: Ejemplo de fronteras para clasificación 1-vs-All para un problema con 4 clases. El patrón * es el nuevo patrón que va a ser clasificado ....................................................................... 16

Figura 2.6: Ejemplo de fronteras para clasificación pairwise para un problema con 4 clases. El patrón * es el nuevo patrón que va a ser clasificado ....................................................................... 17

Figura 2.7: Ejemplo de clasificación para un problema de 4 clases combinando 6 clasificadores pareados El nuevo patrón * es clasificado como de clase 4 por mayoría de votos................................................... 17

Figura 2.8: Ejemplo de clasificación DAG para un problema de 4 clases combinando 6 clasificadores pareados 1-vs-1 en forma de árbol. El nuevo patrón * recorre todos los nodos del árbol y es clasificado como de clase 4 por el nodo hoja........................................................................................ 18

Figura 2.9: Algoritmo de Entrenamiento del método US-MSVM .................................................................. 21

Figura 2.10: Algoritmo de Test del método US-MSVM ................................................................................. 22

Figura 2.11: Fig.3 del artículo que muestra la influencia del número de clasificadores en los resultados de precision y recall para los conjuntos 10Newsgroups (b) y USPS (c) ................................................... 24

57 references, page 1 of 4
Any information missing or wrong?Report an Issue