Razonamiento y aprendizaje

Índice

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:

$$
P(x|pa(x),\overline{y})=P(x|pa(x))
$$

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

$$
f_{mp}(x,y)= \left\{
\begin{array}{ll}
x\cdot y & \textrm{si } x>0
\\
0 & \textrm{si } x\leq 0
\end{array}
\right.
$$

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:

$$
\textrm{proporción de errores}=\frac{\textrm{número de errores}}{\textrm{número de casos}}
$$

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