Algoritmos

Algoritmos de clasificación

perceptrón multicapa es una red neuronal artificial (RNA) formada por múltiples capas, esto le permite resolver problemas que no son linealmente separables, lo cual es la principal limitación del perceptrón (también llamado perceptrón simple). El perceptrón multicapa puede ser totalmente o localmente conectado. En el primer caso cada salida de una neurona de la capa "i" es entrada de todas las neuronas de la capa "i+1", mientras que en el segundo cada neurona de la capa "i" es entrada de una serie de neuronas (región) de la capa "i+1".

Tipos

Las capas pueden clasificarse en tres tipos:

• Capa de entrada: Constituida por aquellas neuronas que introducen los patrones de entrada en la red. En estas neuronas no se produce procesamiento.
• Capas ocultas: Formada por aquellas neuronas cuyas entradas provienen de capas anteriores y cuyas salidas pasan a neuronas de capas posteriores.
• Capa de salida: Neuronas cuyos valores de salida se corresponden con las salidas de toda la red.

La propagación hacia atrás (también conocido como retropropagación del error o regla delta generalizada), es un algoritmo utilizado en el entrenamiento de estas redes, por ello, el perceptrón multicapa también es conocido como red de retropropagación (no confundir con la red de contrapropagación).

Historia

En 1969, Minsky y Papert, demuestran que el perceptrón simple y ADALINE no puede resolver problemas no lineales (por ejemplo, XOR). La combinación de varios perceptrones simples podría resolver ciertos problemas no lineales pero no existía un mecanismo automático para adaptar los pesos de la capa oculta. Rumelhart y otros autores, en 1986, presentan la "Regla Delta Generalizada" para adaptar los pesos propagando los errores hacia atrás, es decir, propagar los errores hacia las capas ocultas inferiores. De esta forma se consigue trabajar con múltiples capas y con funciones de activación no lineales. Se demuestra que el perceptrón multicapa es un aproximador universal. Un perceptrón multicapa puede aproximar relaciones no lineales entre los datos de entrada y salida. Esta red se ha convertido en una de las arquitecturas más utilizadas en el momento.¹

Características

• Las funciones de transferencia de los elementos de procesado (neuronas) han de ser derivables.

Limitaciones

• El Perceptrón Multicapa no extrapola bien, es decir, si la red se entrena mal o de manera insuficiente, las salidas pueden ser imprecisas.

• La existencia de mínimos locales en la función de error dificulta considerablemente el entrenamiento, pues una vez alcanzado un mínimo el entrenamiento se detiene aunque no se haya alcanzado la tasa de convergencia fijada.

Cuando caemos en un mínimo local sin satisfacer el porcentaje de error permitido se puede considerar: cambiar la topología de la red (número de capas y número de neuronas), comenzar el entrenamiento con unos pesos iniciales diferentes, modificar los parámetros de aprendizaje, modificar el conjunto de entrenamiento o presentar los patrones en otro orden.

Aplicaciones

El perceptrón multicapa (de aquí en adelante MLP, MultiLayer Perceptron) se utiliza para resolver problemas de asociación de patrones, segmentación de imágenes,compresión de datos, etc.

Compresión de datos

Considerese un MLP de 3 capas, una de entrada, una oculta y la de salida. La capa de entrada está formada por N neuronas, la capa oculta por M (M < N) neuronas y la capa de salida posee N neuronas al igual que la capa de entrada. Se entrena dicho MLP para que cuando se le dé como entrada un vector de datos (x₁, x₂,..., x_N) devuelva ese mismo vector con M datos como salida, con ello estamos enseñando al MLP a transformar un vector de N componentes en uno de M componentes (recordemos que M < N) y a recuperar el vector original a partir del vector "comprimido".

Una vez que el MLP esté entrenado se procede de la siguiente forma:

• Compresión: Para comprimir los datos utilizamos un MLP de dos capas, la de entrada con N neuronas y la de salida con M, los pesos de estas dos capas son los de la capa de entrada y oculta respectivamente, del MLP que entrenamos anteriormente.

• Descompresión: Para descomprimir los datos utilizamos un MLP de dos capas, la de entrada con M neuronas y la de salida con N, los pesos de estas dos capas son los de la capa oculta y la de salida respectivamente, del MLP que entrenamos anteriormente.

El MLP no conseguirá (al menos normalmente) un error nulo durante el entrenamiento, por lo que se trata de un sistema de compresión con pérdidas. Obviamente cuanto mayor queramos que sea el factor de compresión, más error se cometerá.

El perceptron multicapa (MLP)

Este es uno de los tipos de redes más comunes. Se basa en otra red mas simple llamada perceptrón simple solo que el número de capas ocultas puede ser mayor o igual que una. Es una red unidireccional (feedforward). La arquitectura típica de esta red es la siguiente:

Figura 3-2. Representación de un Perceptrón Multicapa (MLP)

Las neuronas de la capa oculta usan como regla de propagación la suma ponderada de las entradas con los pesos sinápticos w_ij y sobre esa suma ponderada se aplica una función de transferencia de tipo sigmoide, que es acotada en respuesta.

Figura 3-3. Forma funcional de una sigmoide

El aprendizaje que se suele usar en este tipo de redes recibe el nombre de retropropagacion del error (backpropagation). Como funcion de coste global, se usa el error cuadratico medio. Es decir, que dado un par (x_k, d_k) correspondiente a la entrada k de los datos de entrenamiento y salida deseada asociada se calcula la cantidad:

Ecuación 3-1. Error cuadrático medio

que vemos que es la suma de los errores parciales debido a cada patrón (índice p), resultantes de la diferencia entre la salida deseada d_p y la salida que da la red f(.) ante el vector de entrada x_k. Si estas salidas son muy diferentes de las salidas deseadas, el error cuadratico medio sera grande. f es la función de activación de las neuronas de la capa de salida e y la salida que proporcionan las neuronas de la ultima capa oculta.

Sobre esta función de coste global se aplica algun procedimiento de minimización. En el caso del MLP se hace mediante un descenso por gradiente. Las expresiones que resultan aplicando la regla de la cadena son las siguientes:

Ecuación 3-2. Términos delta

Siendo y_k las salidas de la capa oculta.

El aprendizaje por backpropagation queda como sigue:

1. Inicializar los pesos y los umbrales iniciales de cada neurona. Hay varias posibilidades de inicialización siendo las mas comunes las que introducen valores aleatorios pequeños.
2. Para cada patrón del conjunto de los datos de entrenamiento
   
   
   1. Obtener la respuesta de la red ante ese patrón. Esta parte se consigue propagando la entrada hacia adelante, ya que este tipo de red es feedforward. Las salidas de una capa sirven como entrada a las neuronas de la capa siguiente, procesandolas de acuerdo a la regla de propagación y la función de activación correspondientes.
   2. Calcular los errores asociados según la ecuación 3-2
   3. Calcular los incrementos parciales (sumandos de los sumatorios). Estos incrementos dependen de los errores calculados en 2.b
3. Calcular el incremento total ,para todos los patrones, de los pesos y los umbrales según las expresiones en la ecuación 3-2
4. Actualizar pesos y umbrales
5. Calcular el error actual y volver al paso 2 si no es satisfactorio.

Random forest (o random forests) también conocidos en castellano como '"Selvas Aleatorias"' es una combinación de árboles predictores tal que cada árbol depende de los valores de un vector aleatorio probado independientemente y con la misma distribución para cada uno de estos. Es una modificación sustancial de bagging que construye una larga colección de árboles no correlacionados y luego los promedia.

El algoritmo para inducir un random forest fue desarrollado por Leo Breiman¹ y Adele Cutler y Random forests es su marca de fábrica. El término aparece de la primera propuesta de Random decision forests, hecha por Tin Kam Ho de Bell Labs en 1995. El método combina la idea de bagging de Breiman y la selección aleatoria de atributos, introducida independientemente por Ho,^2 3 Amit y Geman,⁴ para construir una colección de árboles de decisión con variación controlada.

La selección de un subconjunto aleatorio de atributos es un ejemplo del método random subspace, el que, según la formulación de Ho, es una manera de llevar a cabo la discriminación estocástica⁵ propuesta por Eugenio Kleinberg.

En muchos problemas el rendimiento del algoritmo random forest es muy similar a la del boosting, y es más simple de entrenar y ajustar. Como una consecuencia el random forests es popular y es ampliamente utilizado.

Definición de Random forests

La idea esencial del bagging es promediar muchos modelos ruidosos pero aproximadamente imparciales, y por tanto reducir la variación. Los árboles son los candidatos ideales para el bagging, dado que ellos pueden registrar estructuras de interacción compleja en los datos, y si crecen suficientemente profundo, tienen relativamente baja parcialidad. Producto de que los árboles son notoriamente ruidosos, ellos se benefician grandemente al promediar.

Cada árbol es construido usando el siguiente algoritmo:

1. Sea N el número de casos de prueba, M es el número de variables en el clasificador.
2. Sea m el número de variables de entrada a ser usado para determinar la decisión en un nodo dado; m debe ser mucho menor que M
3. Elegir un conjunto de entrenamiento para este árbol y usar el resto de los casos de prueba para estimar el error.
4. Para cada nodo del árbol, elegir aleatoriamente m variables en las cuales basar la decisión. Calcular la mejor partición a partir de las m variables del conjunto de entrenamiento.

Para la predicción un nuevo caso es empujado hacia abajo por el árbol. Luego se le asigna la etiqueta del nodo terminal donde termina. Este proceso es iterado por todos los árboles en el ensamblado, y la etiqueta que obtenga la mayor cantidad de incidencias es reportada como la predicción.

Características (o rasgos) y Ventajas

Las ventajas del random forests son:⁶

• Es uno de los algoritmos de aprendizaje más certeros que hay disponible. Para un set de datos lo suficientemente grande produce un clasificador muy certero.⁷
• Corre eficientemente en bases de datos grandes.
• Puede manejar cientos de variables de entrada sin excluir ninguna.
• Da estimados de qué variables son importantes en la clasificación.
• Tiene un método eficaz para estimar datos perdidos y mantener la exactitud cuando una gran proporción de los datos está perdida.
• Computa los prototipos que dan información sobre la relación entre las variables y la clasificación.
• Computa las proximidades entre los pares de casos que pueden usarse en los grupos, localizando valores atípicos, o (ascendiendo) dando vistas interesantes de los datos.
• Ofrece un método experimental para detectar las interacciones de las variables.

Desventajas

• Se ha observado que Random forests sobreajusta en ciertos grupos de datos con tareas de clasificación/regresión ruidosas.⁸
• A diferencia de los árboles de decisión, la clasificación hecha por random forests es difícil de interpretar por el hombre.⁹
• Para los datos que incluyen variables categóricas con diferente número de niveles, el random forests se parcializa a favor de esos atributos con más niveles. Por consiguiente, la posición que marca la variable no es fiable para este tipo de datos. Métodos como las permutaciones parciales se han usado para resolver el problema^10 11
• Si los datos contienen grupos de atributos correlacionados con similar relevancia para el rendimiento, entonces los grupos más pequeños están favorecidos sobre los grupos más grandes.¹²

Visualización

Datos de entrenamiento.

Visualización de Random Forest después del entrenamiento.

Modelo de regresión logística después de entrenamiento.

Para formar una visualización intuitiva del espacio-modelo representado por un random forest, se creó un set de datos que consiste en 200 puntos aleatorios (100 puntos verdes y 100 puntos rojos). Los puntos verdes eran obtenidos a partir de una distribución Gaussiana con un centroide en (0,1), y los puntos rojos eran obtenidos de una distribución de Gaussiana con un centroide en (1,0). En ambos casos, la variación era circular con un radio medio de 1.

El modelo del random forest, consistente de 50 árboles, entrenados usando estos datos. La pureza del color indica la porción de los 50 árboles que votaron de acuerdo. Un over-fit (sobre ajuste) significativo puede ser observado en la visualización de Random Forest después del entrenamiento.

En contraste, se presenta la visualización de un modelo de regresión logístico (menos propenso al sobre ajuste), que también fue entrenado usando estos mismos datos.