Deducción Versus Inducción

Deducción Versus Inducción Deducción = razonamiento de lo general a lo específico Preserva la verdad Siempre es correcto Inducción = razonamiento desde lo específico a lo general el inverso de la deducción No preserva la verdad Puede haber evidencia estadística

DEDUCCIÓN INDUCCIÓN Todos los hombres son mortales Sócrates es mortal Sócrates es un hombre Sócrates es un hombre Sócrates es mortal Todos los hombres son mortales

Búsqueda de cláusulas del programa: inferencia y probabilidad Probabilidad de seleccionar un elemento de U siendo de P p(P)=|P| / |U| Dado un elemento seleccionado de U que es de Q, probabilidad de que sea de P p(P/Q)=p(P?Q) / p(Q) Teorema de Bayes: p(P/Q)=p(P) * p(Q/P) / p(Q) U P Q

Búsqueda de cláusulas del programa: inferencia y probabilidad Interpretación probabilística del cálculo de predicados de primer orden (Carnap) P representa el conjunto de modelos de Herbrand de la fórmula P (resp. Q) y U es 2H(P?Q). p(P)=p(P) son las interpretaciones de P que son modelo de P p(P/Q) son los modelos de Q que son modelo de P p(False)=0 p(True)=1 p(P?Q)= p(P?Q) p(P?Q)= p(P?Q) p(?P)=1- p(P) p(P)?p(Q) si P |= Q

Búsqueda de cláusulas del programa: inferencia y probabilidad Dados B y E, hay más de una hipótesis candidata. H = T= p(x1,…,xn) H = ?= E+ Teorema de Bayes: Sea E una evidencia de T. Entonces p(T/E)=p(T) * p(E/T) / p(E) Carnap: p(T) es la proporción de interpretaciones que son modelo de T ? PARADOJA Solomonoff: p(P)= 2-?(P), donde ?(P) es el contenido de información de la fórmula P (longitud en bits de la codificación mínima de P).

Búsqueda de cláusulas del programa: inferencia y probabilidad Teoría de la información de Shannon: I(P)=-log2p(P)

I(True) = 0 (p(True) = 1) I(False) = ? (p(False) = 0) I(P ?Q) = I(P) + I(Q) (p(P?Q) = p(P) . p(Q))

Información de Bayes: I(T|E) = I (T) + I (E|T) – I (E)

Búsqueda de cláusulas del programa: inferencia y probabilidad La teoría debe ser una explicación más simple que la propia evidencia I(T|E) ? I(B ?E) T comprime los ejemplos al tener menor contenido de información. p(T/E)=p(T) * p(E/T) / p(E) ? 1 p(T) * p(E/T) ? p(E) ? 0 ? I(E) ? I(T) + I(E/T) ? I(T|E) ? I(T) + I(E/T) ? I(B ?E) 0

Búsqueda de cláusulas del programa: inferencia y probabilidad Principio de la longitud de descripción mínima de Rissanen: minimizar I(T|E) Principio de la navaja de Ockham: minimizar I(T) Principio de la probabilidad máxima de Fisher: maximizar I(E|T) TEOREMA DE EQUIVALENCIA: Sea E una evidencia para un conjunto de teorías (potenciales) elegidas desde ?. minT?? I(T|E) = – log2 maxT?? p(T|E)

Búsqueda de cláusulas del programa Búsqueda en el espacio de las hipótesis estados: hipótesis de LH objetivo: encontrar una hipótesis que satisfaga el criterio de calidad (ej. completitud y consistencia) Algoritmo de generación y prueba para todo H? LH hacer si H es completa y consistente entonces output(H)? computacionalmente caro Restringir la búsqueda lenguaje: reducir el espacio de hipótesis búsqueda: reducir la búsqueda en el espacio de las hipótesis

Búsqueda de cláusulas del programa Estructura del espacio de hipótesis basado en una relación de generalidad G es más general que S iff covers(S)? covers(G)

Podando el espacio de búsqueda Si H no cubre un ejemplo e entonces tampoco cubrirá ninguna especialización de e ? usado con los ejemplos positivos para podar Si H cubre un ejemplo e entonces también cubrirá sus generalizaciones usado con los ejemplos negativos para podar Estas propiedades determinan el espacio de las soluciones posibles

Búsqueda de cláusulas del programa: espacio de hipótesis – + + + + – – – – muy general muy específico ¿Cómo estructurar el espacio de las hipótesis? ¿Cómo movernos desde una hipótesis a otra?

Búsqueda de cláusulas del programa: espacio de hipótesis Más general Más específico

Búsqueda de cláusulas del programa: espacio de hipótesis Más general Más específico e- cubierto ? ? ? ? e- no cubierto

Búsqueda de cláusulas del programa: espacio de hipótesis Más general Más específico flies(X)? flies(X)?bird(X) flies(X)?bird(X), normal(X)

Búsqueda de cláusulas del programa: espacio de hipótesis Más general Más específico flies(X)? flies(X)?bird(X) flies(X)?bird(X), normal(X) ? flies(oliver)? bird(oliver)

Búsqueda de cláusulas del programa: noción de generalidad Noción de generalidad ¿Cómo especializar las condiciones? ¿Cómo generalizar las condiciones?

Búsqueda de cláusulas del programa: noción de generalidad El conjunto de los términos de primer orden es un retículo t1 es más general que t2 iff para alguna sustitución ?: t1 ? = t2 especialización: aplicar una sustitución generalización: aplicar una sustitución inversa g(f(X),Y) g(f(X),X) g(f(f(a)),X) g(f(X),f(a)) g(f(f(a)),f(a))