computer-science - manhattan - primero el mejor inteligencia artificial
¿Cuál es la diferencia entre la monotonicidad y la admisibilidad de una heurística? (3)
Estoy leyendo mi libro de texto de AI y tengo curiosidad acerca de cuál es la diferencia entre la monotonicidad y la admisibilidad de las heurísticas (sé que no son mutuamente excluyentes).
Por lo que puedo decir, una heurística admisible simplemente significa que está asegurado de obtener el camino más corto hacia una solución, si existe.
Con lo que estoy luchando es con el concepto de la propiedad monotónica. ¿Alguien me puede describir esto de una manera que pueda entender?
De manera similar, ¿cómo puedo determinar si una heurística dada es monotónica / admisible? Uno de los ejemplos dados en el libro es el rompecabezas deslizante de 8 piezas. Una de las heurísticas que estoy considerando es el número de mosaicos fuera de lugar, e intuitivamente puedo decir que sé que es admisible pero no tengo una forma formal de mostrar si es admisible / monótono.
Admisibilidad
Un algoritmo de búsqueda es admisible si está garantizado para encontrar un camino mínimo hacia una solución siempre que exista dicha solución. La primera búsqueda de amplitud es admisible, ya que analiza todos los estados en el nivel n antes de considerar cualquier estado en el nivel n + 1.
Monotonicidad: esta propiedad pregunta si un algoritmo es admisible localmente, es decir, siempre subestima el costo entre dos estados en el espacio de búsqueda. Recuerde que A * no requiere que g (n) = g * (n). Una función heurística, h es monótona si: 1. Para todos los estados ni y nj, donde nj es un descendiente de ni, h (ni) - h (nj) <= costo (ni, nj).
2.La evaluación heurística del estado del objetivo es 0: h (Objetivo) = 0.
Russel y Norvig, 2ed page 99 dice:
La segunda solución es garantizar que la ruta óptima a cualquier estado repetido sea siempre la primera seguida, como es el caso de la búsqueda de costo uniforme. Esta propiedad es válida si imponemos un requisito adicional a
h(n), es decir, el requisito de consistencia (también llamado monotonicidad ).
Cuando se habla de funciones, monotono significa que una función aumenta o disminuye, pero no ambas. En otras palabras, el orden en el rango se mantiene igual en todo el dominio. Por esta razón, en su problema, la solución mantiene el camino más corto sin importar en qué paso comience.
La propiedad de admisibilidad de un heurístico significa que el costo para alcanzar la meta nunca se sobreestima (es decir, es optimista) (página 98).
El aprendizaje monótono es cuando un agente no puede aprender ningún conocimiento que contradiga lo que ya sabe. Por ejemplo, no puede reemplazar una declaración con su negación. Por lo tanto, la base de conocimiento solo puede crecer con nuevos hechos de manera monotónica. Las ventajas del aprendizaje monotónico son:
1. Mantenimiento de la verdad muy simplificado.
2. Mayor elección en estrategias de aprendizaje.
El aprendizaje no monotónico es cuando un agente puede aprender un conocimiento que contradice lo que ya sabe. Por lo tanto, puede reemplazar el conocimiento antiguo con el nuevo si cree que hay razones suficientes para hacerlo. Las ventajas del aprendizaje no monotónico son:
1. mayor aplicabilidad a dominios reales,
2. Mayor libertad en el orden en que se aprenden las cosas.
Una propiedad relacionada es la consistencia del conocimiento. Si una arquitectura debe mantener una base de conocimientos consistente, cualquier estrategia de aprendizaje que utilice debe ser monótona.