Elias Hernandis - 21 Jan 2020
Búsqueda genérica en árbol
function búsqueda-en-árbol (problema, estrategia)
;; devuelve solución o fallo
;; lista-abierta contiene los nodos de la frontera del árbol de búsqueda
Inicializar árbol-de-búsqueda con nodo-raíz
Inicializar lista-abierta con nodo-raíz
Iterar
If (lista-abierta está vacía) then return fallo
Elegir de lista-abierta, de acuerdo a la estrategia, un nodo a expandir.
If (nodo satisface test-objetivo)
then return solución (camino desde el nodo-raíz hasta el nodo actual)
else eliminar nodo de lista-abierta
expandir nodo
añadir nodos hijo a lista-abiertaBúsqueda en grafo o con eliminación de estados repetidos: añadir una lista de cerrados que contiene los nodos ya explorados (= expandidos). No se introducen en la lista de abiertos aquellos nodos que ya estén en la lista de cerrados.
La estrategia determina la ordenación de la lista abierta:
¿Qué queremos?
Completitud: encontrar la solución siempre que exista.
Optimalidad: encontrar siempre la solución de menor coste \(g\).
\(A^\ast\) (A-estrella): ordenar la lista de abiertos por valor de \(f = g + h\) ascendente.
| Tiempo | Memoria | Completa? | Óptima? | |
|---|---|---|---|---|
| en anchura | \(O(b^d)\) | \(O(b^d)\) | Sí1 | Sí2 |
| en profundidad | \(O(b^m)\) | \(b\cdot m + 1\) | No | No |
| Dijkstra | \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) | \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) | Sí (\(\varepsilon > 0\)) | Sí |
| avariciosa | \(O(b^m)\) | \(O(b^m)\) | No | No |
| \(A^\ast\) | \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) | \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) | Sí* | Sí* |
perder = -1, empatar = 0, ganar = 1 en el ajedrez da un juego de suma cero ya que si uno pierde, el otro gana y por tanto sus valores de utilidad suman 0. Ocurre lo mismo si los dos empatan.perder = 0, empatar = 1, ganar = 2 en el ajedrez da una juego de suma constante ya que si una pierde y el otro gana la suma de las utilidades desde ambos puntos de vista es 2. Ocurre lo mismo si los dos empatan (\(1+1 = 2\)).Modelización de un problema con dos jugadores.
Al que juega primero le llamamos max, al otro min.
Esta estrategia encuentra la jugada óptima para max.
Definimos el valor minimax(n) para un nodo:
Optimalidad: minimax es óptimo si el oponente lo es. Si no lo es hay maneras mejores de ganarle (esto es peligroso).
Complejidad temporal \(O(b^m)\) y espacial \(O(b\cdot m)\).
Con poda \(\alpha-\beta\):
min se actualiza \(\beta = \min(\beta, \alpha_i \text{ de los hijos })\)max se actualiza \(\alpha = \max(\alpha, \beta_i \text{ de los hijos})\)Hay que acordarse de:
mejorAmigoDe(persona) es una función mientras que ViveEn(ciudad, persona) es un predicado.\[\forall x,y [(\lnot I(x,y) \land I(padreDe(x), padreDe(y))) \iff H(x, y)]\]
\[\forall x,y,c [C(c, x, y) \iff (I(c, enlace(x,y)) \lor \exists z,m,n (\lnot I(m,n) \land C(m, x, z) \land C(n, z, y)]\]
\[\forall u [Universal(u) \implies \forall t, d (comp(t, d) = comp(u, descr(t_2, d))]\]
Problema: dado un conjunto de pares (atributos, clase) donde atributos es un vector, elaborar un modelo que permita asignar una clase de entre un conjunto de clases a otros vectores de atributos.
Definiciones:
El prior \(P(\text{clase})\)
La evidencia \(P(\text{atributos})\)
La verosimilitud \(P(\text{atributos}\mid \text{clase})\)
El posterior \(P(\text{clase} \mid \text{atributos}\). Para un vector de atributos dado, la suma de los posteriores sobre cada clase da siempre 1, es decir, \(\sum P(\text{clase}_i \mid \text{atributos}) = 1\).
Modelos:
Un modelo de predicción nos asigna una clase a un vector de atributos dado en base a los datos (pares (atributos, clase)) de los que partimos.
Modelo basado en priores: predecir, para cualquier vector de atributos, la clase con mayor prior (ignorar los atributos de un dato para clasificarlo).
ML = Maximum Likelihood o Máxima verosimilitud: predecir la clase que maximiza \(P(\text{atributos} \mid \text{clase})\).
Calsificador de Bayes o MAP o maximizar los posteriores: predecir la clase que maximiza \(P(\text{clase}\mid \text{atributos})\). Bayes es óptimo = minimiza el error.
Clasificador Naïve Bayes: asume que los atributos son independientes entre sí y por tanto solo dependen de la clase, difiere del clasificador de Bayes en la manera de descomponer \(P(\text{clase}\mid \text{atributos})\): \[ P(\text{clase} \mid \text{atributos}) = \frac{P(\text{atributos}\mid \text{clase}) \cdot P(\text{clase})}{P(\text{atributos})} = \frac{(\prod P(\text{attributo}_i\mid \text{clase}))P(\text{clase})}{P(\text{atributos})} \]
Predice la clase que maximiza \(P(\text{clase} \mid \text{atributos})\) como hace MAP.
Clasificador según una red bayesiana: dadas las dependencias entre los atributos(el grafo) descomponemos \(P(\text{clase}\mid \text{atributos})\) según estas. Predice la clase que maximiza \(P(\text{clase} \mid \text{atributos})\) como hace MAP.
Nota: si tenemos clases uniformes, es decir, si \(P(\text{clase}_i) = P(\text{clase}_j)\) para toda clase de nuestro problema, entonces MAP y ML predicen siempre la misma clase (no necesariamente con la misma probabilidad).
Construir de manera automática modelos para clasificación.
Dado un conjunto de entrenamiento formado por pares (atributos, clase) donde atributos es un vector, generar un modelo que permita asignar una clase de entre un conjunto de clase a otros vectores de atributos.
Problema: minimizar la profundidad del árbol.
Solución: poner más arriba decisiones que aporten más información, es decir, poner como raíz del árbol la decisión sobre el atributo que maximice la ganancia de información.
Dos algoritmos muy parecidos:
ID3: genera árboles propiamente dichos a partir de datos que pueden ser cualitativos. Un nodo del árbol representa la decisión basada en un atributo y por tanto tiene tantas ramas como valores toma el atributo. Permite atributos cualitativos.
C4.5: genera particiones del espacio \(R^n\) donde \(n\) es el número de atributos. En cada iteración nos da una partición del dominio del atributo tal que se maximiza la ganacia de información. Requiere atributos cuantitativos (que pueden obtenerse asignando valores a los atributos cualitativos pero entonces no se diferencia de ID3).