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))