Razonamiento y Aprendizaje¶
Razonamiento¶
Introducción. Sistemas expertos¶
Un sistema experto es un sistema informático (hardware o software) que simula a expertos humanos en cierta área de especialización dada.
Razonamiento aproximado. Tratamiento de la incertidumbre¶
Fuentes de incertidumbre¶
Se pueden clasificar las fuentes de incertidumbre en los siguientes grupos:
- Deficiencias de la información,
- características del mundo real, y
- deficiencias del modelo.
Tratamiento de la incertidumbre¶
Los métodos de razonamiento incierto se clasifican en dos grupos:
- Métodos numéricos.
- Métodos cualitativos.
Cuando el razonamiento incierto se realiza mediante métodos numéricos se habla de razonamiento aproximado.
Método probabilística clásico¶
Nota. La causalidad implica correlación, pero la correlación no implica causalidad.
Aplicación del teorema de Bayes¶
En la práctica, el teorema de Bayes se utiliza para conocer la probabilidad a posteriori de cierta variable dado un conjunto de hallazgos.
- Hallazgo: Es la determinación del valor de una variable a partir de un dato.
- Evidencia: Es el conjunto de todos los hallazgos disponibles en cierto momento.
- Probabilidad a priori: Es la probabilidad de una variable cuando no hay ningún hallazgo.
- Probabilidad a posteriori: Es la probabilidad de una variable dada cierta evidencia.
Redes bayesianas¶
Dado un grafo dirigido acíclico conexo y una distribución de probabilidad sobre sus variables, se dice que hay separación direccional si dado un nodo \(X\) el conjunto de sus padres separa condicionalmente este nodo de todo otro subconjunto en que no haya descendientes de \(X\). Es decir:
Una red bayesiana es un grafo dirigido acíclico conexo junto con una distribución de probabilidad sobre sus variables que cumple la propiedad de la separación direccional.
La puerta OR/MAX¶
Una variable graduada es la variable \(X\) que puede estar ausente o presente con \(g_X\) grados de intensidad. Tiene por tanto \(g_X+1\) valores posibles, a los que asignaremos enteros tales que \(X=0\) significa “ausencia de \(X\)" y los números sucesivos indican grados de mayor intensidad.
En una red bayesiana, dada una variable graduada \(X\) con \(n\) padres \(U_1,\dots U_n\) (también variables graduadas), decimos que interaccionan mediante una puerta MAX cuando se cumplen las dos condiciones siguientes:
-
\(P(X=0\,|\,\overline{U}=0)=1\)
-
\(P(X\leq x|\overline{u})=\prod_i P(X\leq x \,|\, U_i=u_i, \overline{U}_i=0)\)
Si \(X\) y las \(U_i\) son todas binarias se dice que interactúan mediante una puerta OR.
Modelo de factores de certeza¶
Propagación de la evidencia en una red de inferencia¶
Modus ponens incierto¶
Si \(E\) entonces \(H\), con \(FC(H,E)\)
\(E\), con \(FC(E)\)
\(H\), con \(FC(H)=f_{mp}(FC(E),FC(H,E))\)
donde
Combinación secuencial de reglas¶
Si \(A\) entonces \(B\), con \(FC(B,A)\)
Si \(B\) entonces \(C\), con \(FC(C,B)\)
Si \(A\) entonces \(C\), con \(FC(C,A)\)
donde \(\(FC(C,A)= \left\{ \begin{array}{ll} FC(B,A)\cdot FC(C,B) & \textrm{si } FC(B,A)\geq 0 \\ 0 & \textrm{si } FC(B,A)< 0 \end{array} \right.\)\)
Problemas del modelo de factores de certeza¶
Los problemas más importantes desde el punto de vista matemático que plantea el modelo de factores de certeza son los siguientes:
-
Reglas equivalentes conducen a conclusiones distintas.
-
No considera correlaciones entre proposiciones.
-
No considera correlaciones entre hallazgos.
-
Incoherencia de los valores calculados.
-
Falta de sensibilidad.
-
Pseudo-independencia condicional.
Lógica difusa¶
Lógica de proposiciones¶
Lógicas multivaluadas¶
Lógica difusa¶
En la lógica difusa se permite que \(v(p)\) tome cualquier valor entre \(0\) y \(1\), siendo una generalización de las lógicas multivaluadas.
Propiedades de las lógicas difusas¶
Límite clásico¶
Toda lógica difusa ha de ser una extensión de la lógica clásica, en el sentido de que cuando los valores de verdad de dos proposiciones están en \(\{0,1\}\), los valores de verdad de las proposiciones resultantes al aplicar las conectivas sean los mismos que en lógica clásica.
Funciones de negación¶
- Límite clásico, \(f_\neg(1)=0\), \(f_\neg(0)=1\).
- Involución, \(f_\neg(f_\neg(a))=a\).
- Monotonía-*v*, \(a\leq b \Rightarrow f_\neg(a)\geq f_\neg(b)\).
Funciones de conjunción: Normas triangulares¶
Es imposible definir funciones de conjunción y de disyunción difusas que conserven todas las propiedades de la lógica clásica. Se definen como normas triangulares aquellas funciones que cumplen las siguientes propiedades:
- Conmutativa, \(f_\wedge(a,b)=f_\wedge(b,a)\).
- Asociativa, \(f_\wedge(a,f_\wedge(b,c))=f_\wedge(f_\wedge(a,b),c)\).
- Elemento neutro, \(f_\wedge(a,1)=a\).
- Monotonía-v, \(a\leq b \Rightarrow f_\wedge(a,c)\leq f_\wedge(b,c)\).
La conjunción estándar viene dada por la función mínimo — \(f_\wedge(a,b)=\min(a,b)\) —, que es una norma triangular.
Funciones de disyunción: Conormas triangulares¶
Las conormas triangulares se definen como las funciones que cumplen las siguientes propiedades:
- Conmutativa, \(f_\vee(a,b)=f_\vee(b,a)\).
- Asociativa, \(f_\vee(a,f_\vee(b,c))=f_\vee(f_\vee(a,b),c)\).
- Elemento neutro, \(f_\vee(a,0)=a\).
- Monotonía-v, \(a\leq b \Rightarrow f_\vee(a,c)\leq f_\vee(b,c)\).
La disyunción estándar viene dada por la función máximo — \(f_\vee(a,b)=\max(a,b)\) —, que es una conorma triangular.
Aprendizaje automático¶
Introducción¶
El objetivo del aprendizaje automático (AA) o, simplemente, aprendizaje consiste en dotar a las computadoras de la capacidad de adquirir nuevos conocimientos automáticamente para poder resolver nuevos problemas o mejorar su comportamiento a partir de la experiencia.
Un sistema se dice que aprende si puede modificar su comportamiento después de un conjunto de experiencias, de forma que pueda o bien realizar una tarea previa de forma más eficiente, o bien realizar nuevas tareas.
Los objetivos que se persiguen cuando se realiza una actividad de aprendizaje automático son principalmente:
- Adquirir nuevos conceptos.
- Reducir los recursos necesarios.
Perspectivas del aprendizaje automático¶
Perspectiva biológica¶
- Aprendizaje genético, o computación evolutiva.
- Aprendizaje neuronal, o redes de neuronas artificiales (RNA). Tratan de emular los procesos que tienen que ver con los sentidos.
Planteamiento inferencial del aprendizaje¶
Según el tipo de razonamiento realizado, los sistemas de aprendizaje se clasifican como:
- Deductivos,
- inductivos,
- abductivos,
- analógicos.
Para distinguir las distintas posibilidades se utiliza la ecuación fundamental de inferencia: \(P\cup S \Rightarrow C\)
Esta ecuación expresa que la premisa \(P\), junto con lo sabido de antemano \(S\), determina de forma lógica el consecuente \(C\).
- Razonamiento deductivo
Dados \(P\) y \(S\) se puede obtener \(C\) por Modus Ponens. - Razonamiento inductivo
Dados varios pares \(P\) y \(C\) se obtiene \(S\). - Razonamiento abductivo
Dados \(C\) y \(S\) se infieren las posibles \(P\). - Razonamiento analógico
Es una combinación de razonamiento inductivo y deductivo.
Perspectiva histórica¶
- Etapa inicial: 1955–1965
Aproximación neurocibernética. Se aplican modelos de aprendizaje numéricos. - Etapa intermedia: 1962–1976
Desarrollo de los primeros lenguajes de manipulación simbólica (Lisp y Prolog). Introducción del uso del cálculo simbólico. - Etapa de asentamiento: 1976–1988
Primeras aplicaciones reales. Aprendizaje basado en la semejanza. - Etapa actual: desde 1988
Fundamentos¶
Tarea de aprendizaje¶
El objetivo de la tarea de aprendizaje es mejorar la realización de una tarea dada.
Conceptos básicos¶
Sesgos o bias¶
Se denominan bias al conjunto de los conocimientos establecidos “a priori" que puedan ayudar a reducir la incertidumbre que caracteriza la selección de hipótesis en el proceso de aprendizaje. Es decir, todo aquello que sirva para elegir unas hipótesis frente a otras.
Tipos¶
Los bias se pueden establecer de tres formas posibles:
- Definiendo un conjunto de restricciones sobre el espacio de hipótesis.
- Definiendo un criterio de preferencia entre las distintas hipótesis.
- Estableciendo una combinación de las dos anteriores.
Ruido¶
Hay diferencia entre el ruido en las entradas (posibilidad de que se produzcan errores en dichos datos) y la tolerancia a fallos (capacidad de generar una respuesta razonablemente correcta en función de los datos analizados).
Error de la muestra y error real¶
El error real se define estadísticamente como la proporción de errores sobre un gran número de nuevos casos cuya asíntota converge en el límite con la distribución real de la población.
Se define:
Si el número de casos tiende a infinito se habla del error real y si se refiere a la muestra se denomina error aparente.
Múltiples sistemas de aprendizaje¶
Comités de validación cruzada¶
Consiste en utilizar los \(k\) clasificadores, resultantes de las \(k\) iteraciones, de la \(k\)-veces validación cruzada junto con un árbitro. Cuando posteriormente se desea clasificar una nueva instancia, cada clasificador generará la clase en la que clasificaría la misma. A continuación, el árbitro generará la salida del comité en función de qué clase es mayoritaria (votación simple) o qué clase sale ganadora de una votación ponderada.
Bagging¶
El algoritmo crea \(k\) clasificadores a partir de \(k\) conjuntos nuevos de entrenamiento. Cada uno de ellos está formado por \(m\) ejemplos extraídos con reemplazamiento del conjunto original de \(m\) elementos. Para formar el conjunto de entrenamiento se escoge aleatoriamente un ejemplo del conjunto original, se copia en el de entrenamiento y se vuelve a introducir en el conjunto original. Así hasta \(m\) veces, tantas como ejemplos disponibles haya.
Una vez generados los \(k\) clasificadores, la manera de realizar una clasificación posterior es mediante voto mayoritario.
Boosting¶
Se van creando secuencialmente sucesivos clasificadores que se especializan en los ejemplos mal clasificados previamente por otros clasificadores. La clase se calcula como el voto ponderado de las clases que generan como salida los diferentes clasificadores formados. El número de clasificadores generados es un parámetro de entrada.
Stacking¶
Al contrario que las técnicas anteriores, stacking no se utiliza para combinar modelos del mismo tipo; se aplica a modelos construidos con algoritmos de aprendizaje diferentes.
Aprendizaje inductivo supervisado¶
El principal objetivo de las técnicas del aprendizaje inductivo supervisado es encontrar en un espacio de descripciones simbólicas un elemento inicialmente desconocido a partir de un conjunto de ejemplos y contraejemplos sobre el mismo.
Estas técnicas presuponen que los ejemplos están perfectamente etiquetados (clasificados como ejemplos positivos y negativos) y la esencia de la tarea realizada se traduce en buscar, en un espacio de descripciones simbólicas, una descripción que abarque todos los ejemplos positivos y excluya todos los negativos.
El aprendizaje inductivo supervisado se desarrolla mediante las siguientes técnicas:
- Espacio de versiones. LEX
- Aprendizaje de reglas de clasificación. \(A^q\)
Espacio de versiones¶
Objetivos¶
Obtener un grupo reducido de hipótesis que representen a todo el conjunto de las que pudieran haberse generado a partir de las instancias procesadas.
Entradas y salidas¶
Las entradas son ejemplos positivos y negativos correctamente etiquetados.
Entradas¶
- \(A\), conjunto de atributos.
- \(V\), conjunto de valores posibles de los atributos.
- \(C\), conjunto de clases: \(C_1=\{P\}\) y \(C_2=\{N\}\)
- \(E\), conjunto de instancias de entrenamiento, descritas en términos de \(A\), \(V\) y \(C\).
Salidas¶
Un conjunto de hipótesis formado por las que sean consistentes con los ejemplos presentados y sena máximamente generales y máximamente específicas.
Las hipótesis máximamente generales (\(G\)) son aquellas consistentes con los ejemplos presentados tales que no hay ninguna otra que sea consistente con dichos ejemplos y, a la vez, sea más general que alguna otra perteneciente a \(G\).
Las hipótesis máximamente específicas (\(S\)) son aquellas consistentes con los ejemplos presentados tales que no hay ninguna otra que sea consistente con dichos ejemplos y, a la vez, sea más específica que alguna otra perteneciente a \(S\).
Tarea¶
- Conjunto de estados. Cada estado será el conjunto de generalizaciones o hipótesis consistentes con los ejemplos presentados.
- Conjunto de operadores. Utiliza tres operadores que realizan tres tareas básicas.
- Estado inicial. \(S\) vacío y \(G\) con la descripción más general describible.
- Meta. Un conjunto de generalizaciones que sean consistentes con los ejemplos presentados y que resulten de la unión de \(S\) y \(G\).
- Parada. El concepto está totalmente aprendido cuando \(S\) y \(G\) coinciden.
- Heurística. Seleccionar un espacio de hipótesis lo más restringido posible que permita mantener la consistencia con todos los ejemplos presentados.
Algoritmo¶
El siguiente algoritmo fue desarrollado por Mitchell.
Algoritmo de eliminación de candidatos
Inicialización
\(P=N=S:=0\)
\(G:=\\{x_1,x_2,\dots,x_n\\}\)
Procedimiento \(EV(p,n)\)
si \(p\neq 0\) entonces
si \(p \notin P\) entonces
\(P:=P\cup \\{p\\}\)
\(G:=\textrm{especializar-}g(p,N,P,G)\)
\(S:=\textrm{generalizar-}s(p,N,P,S)\)
fin si
fin si
si \(n\neq 0\) entonces
si \(n \notin N\) entonces
\(N:=N\cup \\{n\\}\)
\(S:=\textrm{generalizar-}s(p,N,P,S)\)
\(G:=\textrm{especializar-}g(p,N,P,G)\)
fin si
fin si
si \(S=G\) entonces
devolver \(S\)
sino
devolver \(S\cup G\)
fin si
Bias¶
La única restricción en el proceso de búsqueda es la aportada por el propio lenguaje de descripción de hipótesis (LDC).
Ruido¶
En entradas¶
No trata ejemplos con ruido.
En estructura¶
No es tolerante a fallos.
Complejidad¶
Espacial¶
Del orden de \(O(s+g)\).
Temporal¶
El tiempo crece linealmente con el número de instancias de entrenamiento \(p+n\).
Fiabilidad¶
Si los ejemplos no tienen ruido, encuentra el conjunto de hipótesis que resumen el conjunto total de hipótesis consistentes con los ejemplos tratados. Con un número suficiente de ejemplos, el procedimiento encuentra una única hipótesis o concepto aprendido.
Aprendizaje de reglas de clasificación. \(A^q\)¶
Objetivos¶
Obtener un conjunto de reglas de clasificación que describan todos los ejemplos positivos y no describan ningún ejemplo negativo.
Entradas y salidas¶
Similares a los demás sistemas inductivos (clasificadores).
Entradas¶
- \(A\), conjunto de atributos.
- \(V\), conjunto de valores posibles de los atributos.
- \(C\), conjunto de clases.
- \(E\), conjunto de instancias de entrenamiento, descritas en términos de \(A\), \(V\) y \(C\).
- \(LEF\) (Función Lexicográfica de Evaluación), lista de criterios de preferencia de reglas. La proporciona el usuario. La función toma como entrada un conjunto de reglas candidatas a describir un ejemplo y elige cuál es la más apropiada según unos criterios de preferencia también proporcionados por el usuario.\ Los criterios de preferencia pueden ser –entre otros– los siguientes:
- Cobertura, número de ejemplos positivos cubiertos por la regla.
- Simplicidad, número de atributos que aparecen las condiciones de la regla.
- Coste, suma de los costes de calcular el valor de los atributos de la regla.
- Generalidad, definida como el número de ejemplos observados que describe la regla entre el número de ejemplos positivos.
Salidas¶
Un conjunto de reglas generales que engloban a todas las instancias positivas y a ninguna negativa.
Representación de las entradas¶
Los ejemplos vienen en función de los valores de los atributos.
Tratamiento de las entradas¶
En un solo paso.
Preprocesamiento de las entradas¶
No.
Fuente de las entradas¶
Externa.
Representación de la salida¶
Recubrimiento o conjunto de reglas.
Tarea¶
Los sistemas \(A^q\) realizan dos búsquedas. En la más externa (método estrella genérico) se busca un conjunto de reglas que clasifique correctamente a todos los ejemplos. En la más interna por cada ejemplo positivo se busca una regla que lo describa y no describa ningún ejemplo negativo.
Algoritmo¶
El algoritmo estrella es el correspondiente a la búsqueda externa. La búsqueda interna es particular de cada algoritmo \(A^q\), un ejemplo es el algoritmo induce.
Algoritmo estrella
Entradas: - \(P\): ejemplos positivos, - \(N\): ejemplos negativos, - \(LEF\): función lexicográfica
Salidas:
- \(R\): conjunto de complejos (reglas) que describen correctamente a los conjuntos \(P\) y \(N\)
Función Estrella (\(P\), \(N\), \(LEF\))
\(R:=0\)
mientras \(P\neq 0\) hacer
semilla \(:=\) elegir-ejemplo(\(P\))
estrella \(:=\) \(A^q\)(semilla, \(N\))
complejo \(:=\) elegir-complejo(estrella, \(LEF\))
\(R:=R \cup\) complejo
\(P:=P-\)ejemplos-cubiertos-por(\(P\),complejo)
fin mientras
devolver \(R\)
Algoritmo induce
Entradas: - \(p\): semilla, - \(N\): ejemplos negativos
Salidas:
- \(E\): estrella que contiene todos los complejos que describen a \(p\) y no describen ningún ejemplo negativo
Función Induce (\(p\), \(N\))
\(E:=0\)
\(L:=([])\)
\(S:=\)generar-todos-los-selectores-de(\(p\))
mientras \(P\neq 0\) hacer
\(E':=\{x\wedge y | x\in E, y\in S\} - E\)
para cada complejo \(C_i \in E'\) hacer
si válido \((C_i, N)\) entonces
\(E:=C_i\cup E\)
\(E':=E'-\{C_i\}\)
fin si
fin para
\(L:=E'\)
fin mientras
devolver estrella \(E\)
Bias¶
Un bias viene dado por la función \(LEF\) elegida por el usuario, otro viene dado por el lenguaje elegido
Ruido¶
En entradas¶
No trata con ejemplos con ruido.
En estructura¶
Es tolerante a fallos.
Complejidad¶
Espacial¶
El espacio ocupado por \(A^q\) es el ocupado por el recubrimiento. En el peor de los casos será proporcional a \(|A\times P|\) (un complejo por cada ejemplo positivo), y en el mejor de los casos será un único ejemplo vacío.
Temporal¶
Depende del número de atributos y del número de ejemplos negativos.
Fiabilidad¶
Si los ejemplos no tienen ruido, \(A^q\) encuentra el recubrimiento que describe correctamente a todos los ejemplos.
Aprendizaje deductivo¶
El aprendizaje deductivo supervisado se desarrolla mediante las siguientes técnicas:
- Macrooperadores. STRIPS
- Aprendizaje basado en la explicación. EBL
- EBL y utilidad. PRODIGY/EBL
Aprendizaje basado en la explicación (EBL)¶
El aprendizaje basado en la explicación o EBL representa un conjunto de métodos de aprendizaje derivados de los macrooperadores.
Objetivos¶
Un objetivo es mejorar el comportamiento de un sistema que resuelva problemas. Para ello, cada vez que se resuelve uno, se genera una descripción que condensa todo el trabajo realizado y que sirve, posteriormente, para la resolución de problemas parecidos.
Otro objetivo es encontrar una explicación operativa de porqué un determinado ejemplo es un ejemplo de un concepto meta.
Entradas y salidas¶
Definiciones previas¶
- Instancia
conjunción de literales instanciados utilizando un determinado conjunto de predicados.
- Concepto (concepto meta)
predicado definido sobre el conjunto de instancias que describe un subconjunto de ese conjunto.
- Teoría del dominio
conjunto de literales instanciados y reglas que pueden describir los diferentes conceptos que intervienen en el dominio.
- Definición (o descripción) del concepto
condiciones suficientes para que una instancia pueda ser considerada un ejemplo del concepto.
- Ejemplo (positivo)
instancia que cumple la definición del concepto.
- Ejemplo negativo
instancia que no cumple la definición del concepto.
- Generalización de un ejemplo
definición de un concepto que describe un subconjunto de instancias que contiene a dicho ejemplo.
Entradas¶
- Concepto meta (predicado) que se desea aprender, \(c\)
- Ejemplo del concepto meta, \(e\)
- Teoría del dominio, \(D\)
- Criterio de operatividad, \(o\), que especifica qué términos se consideran operativos y, por tanto, pueden aparecer en la generalización buscada del concepto meta.
Salidas¶
Generalización del ejemplo que sea una descripción suficiente del concepto meta y que satisfaga el criterio de operatividad.
Tarea¶
Desde un punto de vista de búsqueda, se puede definir al EBL de la siguiente forma:
- Conjunto de estados. Cada estado sería una teoría del dominio.
- Conjunto de operadores. Para pasar de una teoría del dominio a otra se pueden definir muchos operadores (por ejemplo, “añadir descripción").
- Estado inicial. Teoría del dominio de entrada.
- Metas. Se puede plantear de varias formas. La más utilizada es la de aprender una descripción por cada ejemplo de entrenamiento.
- Heurística. Es tan fuerte que convierte la búsqueda en un algoritmo.
Algoritmo¶
En el algoritmo EBL el procedimiento demostrar genera el árbol de búsqueda correspondiente a demostrar que el ejemplo se puede explicar por medio de las reglas que forman la teoría del dominio. La forma más usual de realizarlo es mediante encadenamiento hacia atrás desde el concepto meta.
El procedimiento generalizar primero parametriza las precondiciones, cambiando constantes por variables, salvo las que aparecen como constantes en las reglas de la teoría de dominio.
Función EBL(c, e, D,o): D
Entradas: - \(c\): concepto meta - \(e\): ejemplo del concepto meta - \(D\): descripción del dominio - \(o\): criterio de operatividad - \(g\): nueva regla generada al generalizar la demostración
Salidas: - \(D\): nueva teoría del dominio
\(d:=\) demostrar (\(c, e, D, o\));
\(g:=\) generalizar (\(d\));
devolver \(D:=D\cup \\{g\\}\)
Enfoques mixtos puramente simbólicos¶
Se desarrollan mediante las siguientes técnicas:
- Analogía por transformación.
- Analogía guiada por la derivación. PRODIGY/ANALOGY
- Programación lógica inductiva (IPL). FOIL
Técnicas inductivas mixtas¶
Se desarrollan mediante las siguientes técnicas:
- Árboles de decisión. ID3, C4.5
- Árboles de regresión. M5
- Técnicas de aprendizaje vago
- Clasificadores bayesianos
Árboles de decisión. ID3, C4.5¶
Estos algoritmos son unos de los más utilizados en el campo del aprendizaje automático.
Objetivos¶
Clasificar los ejemplos presentados en sus respectivas clases o categorías, manteniendo un alto grado de predicción sobre los ejemplos no presentados. Se trata de obtener un árbol de decisión simple que clasifique correctamente los ejemplos presentados y sea capaz de predecir correctamente las clases de futuros ejemplos.
Entradas y salidas¶
Las entradas son un conjunto de ejemplos descritos mediante una serie de pares atributo-valor. El conjunto de atributos es igual para todos los ejemplos presentados y sus valores pueden ser discretos o numéricos.
Entradas¶
- \(A\), conjunto de atributos.
- \(V\), conjunto de valores posibles de los atributos.
- \(E\), conjunto de instancias de entrenamiento descritas en términos de \(A\), \(V\) y un valor \(C_i\) que representa la clase ejemplo \(i\in E\).
Tarea¶
El método ID3 se puede caracterizar como una búsqueda en un espacio de árboles de decisión. El algoritmo realiza un búsqueda en escalada en dicho espacio que comienza con el conjunto vacío y que avanza recursivamente en la elaboración de una hipótesis que consiste en un árbol de decisión que clasifique adecuadamente los ejemplos analizados.
El proceso de búsqueda se define de la siguiente manera:
- Conjunto de estados. Cada estado es un árbol de decisión, en el que los nodos intermedios son preguntas sobre valores de los atributos, las ramas son los distintos valores posibles de dichos atributos, y los nodos hoja identifican un único valor de clase.
- Conjunto de operadores. El único operador es “introducir en un nodo la pregunta del atributo correspondiente".
- Estado inicial. Árbol de decisión vacío.
- Meta. Árbol de decisión que separa los ejemplos de entrenamiento dependiendo de su clase.
- Heurística. Elegir en cada nodo de decisión aquel atributo que tenga mayor capacidad de discriminación sobre los ejemplos asociados al nodo.
Algoritmo¶
ID3 realiza un proceso recursivo sobre todas las ramas del árbol generado. El proceso se realiza hasta que todos los ejemplos de la rama en cuestión pertenecen a una única clase, cuando esto sea posible.
Algoritmo ID3(E, A, N)
Entradas: - \(E\): conjunto de ejemplos - \(A\): conjunto de atributos con sus posibles valores - \(N\): nodo raíz del árbol de decisión
Salidas: - \(N\): árbol de decisión resultante
si \((A=0) \vee (\\{\not\exists x,y\in E \\, | \\, \textrm{clase}(x)\ne\textrm{clase}(y)\\})\) entonces
\(H:=\textrm{crear-nodo-hoja}(\textrm{clase-mayoritaria}(E))\)
si no
\(A_i=\textrm{mejor-atributo}(A)\)
pregunta\((N)=A_i\)
para cada \(v \in A_i\) hacer
\(H=\textrm{crear-nodo}(A_i,v)\)
\(\textrm{hijos}(N):=\textrm{hijos}(N)+H\)
\(E_i=\\{e\in E \\, | \\, \textrm{valor}(e,A_i)=v\\}\)
ID3(\(E_i,A - \\{A_i\\},H\))
fin para
fin si
devolver \(N\)
Bias¶
Sigue la hipótesis de la navaja de Occam: preferir siempre las hipótesis más sencillas que describan los datos. También favorece atributos con muchos valores.
Ruido¶
En entradas¶
Se permite el ruido.
En estructura¶
Es tolerante a fallos, debido a que si se elimina algún nodo del árbol todavía se podría seguir clasificando las instancias.
Técnicas de aprendizaje vago. \(k\)-vecinos más cercanos¶
Las técnicas de aprendizaje vago permiten realizar tareas de clasificación a partir de conjuntos de ejemplos de entrada, sin necesidad de crear estructuras abstractas de generalización de los ejemplos.
Objetivos¶
Realizar el menor esfuerzo computacional a la hora de aprender sin que, por ello, se resienta la tarea de aprendizaje.
Entradas y salidas¶
Entradas¶
- \(E\), conjunto de ejemplos de entrenamiento descritos por un conjunto de atributos y sus valores respectivos.
- \(M\), medida de similitud.
- \(k\), número de vecinos a considerar.
Salidas¶
\(E^q\), subconjunto de los ejemplos de entrenamiento. Permite realizar posteriores clasificaciones, predicciones, etc.
Tareas¶
La tarea en términos de búsqueda se describe como:
- Conjunto de estados. Conjunto de todos los posibles subconjuntos de \(E^q\) del conjunto de ejemplos \(E\).
- Conjunto de operadores. El único operador que se utiliza es almacenar un ejemplo en el subconjunto de los ejemplos \(E^q\).
- Estado inicial. Conjunto vacío.
- Metas. Encontrar un subconjunto \(E^q\subseteq E\) de forma que sea suficiente para clasificaciones posteriores.
- Heurística. Quedarse con aquellos ejemplos que sean significativos con respecto a la tarea a aprender.
Algoritmo¶
El algoritmo básico consiste en almacenar todos los ejemplos. Se puede hacer directamente sin utilizar ningún esquema de almacenamiento eficiente, o utilizando algún esquema de indexación.
Ruido¶
En entradas¶
El ruido lo suaviza mediante la función de similitud que utilizará cuando vaya a utilizar posteriormente el conjunto de ejemplos almacenados.
En estructura¶
Si se elimina o cambia alguno de los ejemplos se puede seguir funcionando.
Complejidad¶
Espacial¶
\(K=|E|\), el número de ejemplos de entrada.
Temporal¶
Dependerá de la estructura de almacenamiento. Normalmente, será menor que la complejidad polinómica.
Clasificadores Bayesianos¶
Objetivos¶
Encontrar un sistema (programa) que sea capaz de clasificar ejemplos, a partir de unos ejemplos de entrenamiento previos. La principal característica de este tipo de clasificadores es que el sistema generado sea capaz de predecir los ejemplos entrenamiento con máxima probabilidad.
Entradas y salidas¶
Entradas¶
- \(A\), conjunto de atributos.
- \(V\), conjunto de valores posibles de los atributos.
- \(C\), conjunto de clases.
- \(E\), conjunto de instancias de entrenamiento descritas en términos de \(A\), \(V\) y \(C\).
Salidas¶
Un clasificador basado en tres matrices:
- \(M_C\), matriz de probabilidad de clases.
- \(M_{AD}\), matriz de probabilidades condicionales de atributos discretos.
- \(M_{AC}\), matriz de probabilidades condicionales de atributos continuos.
Mediante estas matrices se puede clasificar instancias posteriores utilizando el Teorema de Bayes.
Referencias¶
- F.J.Díez] Introducción al Razonamiento Aproximado. UNED, 2004
- Enrique Castillo, José Manuel Gutiérrez y Ali S.Hadi. Sistemas expertos y modelos de redes probabilísticas.
- Daniel Borrajo, Jesús González y Pedro Isasi. Aprendizaje automático