Tema 13: Razonamiento con conocimiento estructurado

Índice

1. Árboles como términos
2. Grafos generados por un predicado
3. Grafos de resolución SLD
4. Ejemplo de conocimiento estructurado con herencia
5. Redes de clasificación
6. Redes semánticas
7. Marcos
8. Bibliografía

1. Árboles como términos

Los árboles se pueden representar por términos. Por ejemplo. el árbol
```
   s
  / \
 /   \
c     p
|    / \
2   3   4
```
se puede representar por el término
```
s(c(2),p(3,4))
```

termino_arbol(A,R,S) se verifica si A es el término que representa al árbol de raíz R y subárboles S. Por ejemplo,

?- termino_arbol(s(c(2),p(3,4)),R,S).
R = s,
S = [c(2),p(3,4)].

?- termino_arbol(A,s,[c(2),p(3,4)]).
A = s(c(2),p(3,4)).

Su definición es

termino_arbol(Arbol,Raiz,Subarboles) :-
   Arbol =.. [Raiz|Subarboles].

termino_raiz(+A,?R) se verifica si R es la raíz del árbol representado por el término A. Por ejemplo,
```
?- termino_raiz(s(c(2),p(3,4)),R).
R = s.
```
Su definición es
```
termino_raiz(Arbol,Raiz) :-
   termino_arbol(Arbol,Raiz,_).
```

termino_subtermino(A,S) se verifica si S es un subárbol del árbol representado por el término A. Por ejemplo,

?- termino_subtermino(s(c(2),p(3,4)),S).
S = c(2) ;
S = p(3,4).

Su definición es

termino_subtermino(Arbol,Subarbol) :-
   termino_arbol(Arbol,_,S),
   member(Subarbol,S).

termino_arco(A,Arco) se verifica si Arco es un arco del árbol A. Por ejemplo,

?- termino_arco(s(c(2),p(3,4)),Arc).
Arc = s-c ;
Arc = s-p ;
Arc = c-2 ;
Arc = p-3 ;
Arc = p-4 ;
false.

Su definición es

termino_arco(Arbol,Raiz-SR) :-
   termino_raiz(Arbol,Raiz),
   termino_subtermino(Arbol,Subarbol),
   termino_raiz(Subarbol,SR).
termino_arco(Arbol,Arco) :-
   termino_subtermino(Arbol,Subarbol),
   termino_arco(Subarbol,Arco).

termino_camino(A,C) se verifica si C es un camino en el árbol A. Por ejemplo,

?- termino_camino(s(c(2),p(3,4)),C).
C = [s,c] ;
C = [s,p] ;
C = [c,2] ;
C = [p,3] ;
C = [p,4] ;
C = [s,c,2] ;
C = [s,p,3] ;
C = [s,p,4] ;
false.

termino_camino(Arbol,[Nodo1,Nodo2]) :-
   termino_arco(Arbol,Nodo1-Nodo2).
termino_camino(Arbol,[Nodo1,Nodo2|Nodos]) :-
   termino_arco(Arbol,Nodo1-Nodo2),
   termino_camino(Arbol,[Nodo2|Nodos]).

Nota: El código de esta sección se encuentra en arbol_termino.pl.

2. Grafos generados por un predicado

Los grafos se pueden representar mediante el predicado binario arco. Por ejemplo, el grafo

   s
  / \
 /   \
c     p
|    / \
2    3  4

se representa por

arco(s,c).
arco(s,p).
arco(c,2).
arco(p,3).
arco(p,4).

Ventajas sobre la representación anterior:
- Mejor para árboles grandes.
- Posibilidad de representar grafos.

camino(C) se verifica si C es un camino en el grafo definido por arco/2. Por ejemplo,

?- camino(C).
C = [s,c] ;
C = [s,p] ;
C = [c,2] ;
C = [p,3] ;
C = [p,4] ;
C = [s,c,2] ;
C = [s,p,3] ;
C = [s,p,4] ;
false.

Su definición es

camino([Nodo1,Nodo2]) :-
   arco(Nodo1,Nodo2).
camino([Nodo1,Nodo2|Nodos]) :-
   arco(Nodo1,Nodo2),
   camino([Nodo2|Nodos]).

hoja(N) se verifica si N es una hoja del grafo definido por arco/2. Por ejemplo,
```
?- hoja(3).
true.

?- hoja(s).
false.
```
Su definición es
```
hoja(N) :-
   not(arco(N,_)).
```

camino_hasta_hoja(N,C) se verifica si C es un camino en el grafo definido por arco/2 desde el nodo N hasta una hoja. Por ejemplo,

?- camino_hasta_hoja(s,C).
C = [s,c,2] ;
C = [s,p,3] ;
C = [s,p,4] ;
false.

Su definición es

camino_hasta_hoja(Hoja,[Hoja]) :-
   hoja(Hoja).
camino_hasta_hoja(Nodo1,[Nodo1|Nodos]) :-
   arco(Nodo1,Nodo2),
   camino_hasta_hoja(Nodo2,Nodos).

Nota: El código de esta sección se encuentra en grafo_predicado.pl.

3. Grafos de resolución SLD

Los programas lógicos se pueden definir usando el operador (<-/2). Por ejemplo,

suma(s(X),Y,s(Z)) <- [suma(X,Y,Z)].
suma(0,Y,Y) <- [].

alumno(A,P) <- [estudia(A,C), enseña(P,C)].
estudia(ana,ia) <- [].
estudia(ana,pl) <- [].
estudia(eva,ra) <- [].
enseña(jose_a,ia) <- [].
enseña(jose_a,ra) <- [].
enseña(rafael,pl) <- [].

arco(Xs,Ys) se verifica si Ys es la lista de objetivos obtenida aplicándole al primer objetivo de Xs una regla del programa lógico definido por el operador <-. Por ejemplo,

?- arco([alumno(A,jose_a)],Xs).
Xs = [estudia(A,_6944),enseña(jose_a,_6944)].

?- arco([estudia(A,_C),enseña(jose_a,_C)],Xs).
A = ana,
Xs = [enseña(jose_a,ia)] ;
A = ana,
Xs = [enseña(jose_a,pl)] ;
A = eva,
Xs = [enseña(jose_a,ra)].

?- arco([enseña(jose_a,ia)],Xs).
Xs = [].

?- arco([suma(X,Y,s(s(0)))],Xs).
X = s(_67111562),
Xs = [suma(_67111562,Y,s(0))] ;
X = 0,
Y = s(s(0)),
Xs = [].

?- arco([suma(X,Y,s(0))],Xs).
X = s(_67113946),
Xs = [suma(_67113946,Y,0)] ;
X = 0,
Y = s(0),
Xs = [].

?- arco([suma(X,Y,0)],Xs).
X = Y, Y = 0,
Xs = [].

Su definición es

arco([A|As],L) :-
   (A <- Cuerpo),
   append(Cuerpo,As,L).

hoja(Xs) se verifica si Xs es la lista vacía de objetivos.
```
hoja([]).
```

camino_hasta_hoja(N,C) se verifica si C es un camino en el grafo definido por arco/24 desde el nodo ~N hasta una hoja. Por ejemplo,

?- camino_hasta_hoja([alumno(A,jose_a)],_).
A = ana ;
A = eva ;
false.

?- camino_hasta_hoja([suma(X,Y,s(s(0)))],_).
X = s(s(0)),
Y = 0 ;
X = Y, Y = s(0) ;
X = 0,
Y = s(s(0)) ;
false.

Su definición es

camino_hasta_hoja(Hoja,[Hoja]) :-
   hoja(Hoja).
camino_hasta_hoja(Nodo1,[Nodo1|Nodos]) :-
   arco(Nodo1,Nodo2),
   camino_hasta_hoja(Nodo2,Nodos).

Nota: El código de esta sección se encuentra en grafo_SLD.pl.

4. Ejemplo de conocimiento estructurado con herencia

En las siguiente secciones usaremos este ejemplo de conocimiento estructurado: Todos los elementos son personas (que, por defecto, viven en Sevilla) y se clasifican en dos grupos: los alumnos (que, por defecto, son solteros) y los profesores (que, por defecto, están casados). Hay dos alumnos: Juan (que tiene 19 años) y Luis (que tiene 24 años y está casado). Hay dos profesores: Pablo (que tiene 44 años y vive en Mairena) y Pedro (que tiene 47 años).

El conocimiento anterior se puede resumir por

Personas [ciudad: Sevilla]
 * Alumnos [estado: soltero]
   * Juan [edad: 19]
   * Luis [edad: 24, estado: casado]
 * Profesores [estado: casado]
   * Pablo [edad: 44, ciudad: Mairena]
   * Pedro [edad: 47]

5. Redes de clasificación

5.1. Representación mediante una red de clasificación

Las clases se representan mediante predicados: personas, alumnos y profesores
La relaciones de inclusión entre clases se representan mediante cláusulas:
- Todos los alumnos son personas:
```
persona(X) :- alumno(X).
```
- Todos los profesores son personas:
```
persona(X) :- profesor(X).
```
Las instancias se representan mediante constantes: juan, luis, pablo y pedro.
Las relaciones de pertenencia a clase se representa mediante hechos:
```
alumno(juan).
alumno(luis).
profesor(pablo).
profesor(pedro).
```
En la red hay 4 atributos:
- ciudad, con dos posibles valores (sevilla o mairena);
- estado, con dos posibles valores (soltero o casado) y
- edad, con valor nun entero positivo.
atributos(As) se verifica si As es la lista de los atributos que aparecen en la red.
```
atributos([ciudad,estado,edad]).
```

ciudad(I,C) se verifica si C es la ciudad de I.

ciudad(pablo,mairena).
ciudad(X,sevilla) :- persona(X).

estado(I,E) se verifica si E es el estado de I.

estado(luis,casado).
estado(X,soltero) :- alumno(X).
estado(X,casado) :- profesor(X).

edad(I,E) se verifica si E es la edad de I.

edad(juan,19).
edad(luis,24).
edad(pablo,44).
edad(pedro,47).

Nota: En la definición de los atributos se escriben antes las cláusulas más específicas.

5.2. Razonamiento con redes de clasificación

propiedades(I,P) se verifica si P es la lista de las propiedades (es decir, pares de atributos y valores) de la instancia I. Por ejemplo.

?- propiedades(juan,P).
P = [ciudad:sevilla,estado:soltero,edad:19].

?- propiedades(luis,P).
P = [ciudad:sevilla,estado:casado,edad:24].

?- propiedades(pablo,P).
P = [ciudad:mairena,estado:casado,edad:44].

?- propiedades(pedro,P).
P = [ciudad:sevilla,estado:casado,edad:47].

Su definición es

propiedades(Inst,Props) :-
   atributos(Atrs),
   propiedades(Atrs,Inst,Props).

propiedades([],_Inst,[]).
propiedades([Atr|Atrs],Inst,[Atr:Valor|Props]) :-
   apply(Atr,[Inst,Valor]), !,
   propiedades(Atrs,Inst,Props).

Nota: El código de esta sección se encuentra en redes_de_clasificacion.pl.

5.3. Comentarios sobre redes de clasificación

Se puede dar conflictos entre propiedades. Por ejemplo.

?- estado(luis,X).
X = casado ;
X = soltero ;
false.

?- propiedades(luis,_P), member(estado:X,_P).
X = casado ;
false.

Hay dependencia del orden de las cláusulas en las propiedades específica.
Es difícil razonar sobre clases; por ejemplo, para calcular las subclases de persona.

6. Redes semánticas

6.1. Representación del conocimiento mediante una red semántica

Utilizaremos el mismo conocimiento sobre las personas de la sección anterior.
Las clases se representan por constantes: persona, alumno y profesor.
La relaciones de inclusión entre clases se representan mediante hechos de forma que es_un(C1,C2) se verifica si C1 es una subclase de C2 (además se añade la clase inicio para señalar el principio de la jerarquía de clases).
```
es_un(persona,inicio).
es_un(alumno,persona).
es_un(profesor,persona).
```
Las instancias se representan mediante constantes: juan, luis, pablo y pedro.
Las relaciones de pertenencia a clase se representa mediante hechos de forma que inst(I,C) se verifica si I es una instancia de la clase C.
```
inst(juan,alumno).
inst(luis,alumno).
inst(pablo,profesor).
inst(pedro,profesor).
```

Las propiedades se representan por la relación prop(X,P,V) que se verifica si el valor de la propiedad P de X es V.

prop(persona,ciudad,sevilla).
prop(alumno,estado,soltero).
prop(profesor,estado,casado).
prop(juan,edad,19).
prop(luis,edad,24).
prop(luis,estado,casado).
prop(pablo,edad,44).
prop(pablo,ciudad,mairena).
prop(pedro,edad,47).

6.2. Razonamiento con una red semántica

propiedades_especificas(X,Ps) se verifica si Ps es la lista de las propiedades específicas de X. Por ejemplo,

?- propiedades_especificas(persona,P).
P = [ciudad:sevilla].

?- propiedades_especificas(juan,P).
P = [edad:19].

?- propiedades_especificas(luis,P).
P = [edad:24,estado:casado].

Su definición es

propiedades_especificas(X,Props) :-
   findall(Atr:Valor,prop(X,Atr,Valor),Props).

propiedades_rs(I,Ps) se verifica si Ps es la lista de las propiedades de la instancia I. Por ejemplo.

?- propiedades_rs(juan,P).
P = [ciudad:sevilla,estado:soltero,edad:19] 

?- propiedades_rs(luis,P).
P = [ciudad:sevilla,edad:24,estado:casado] 

?- propiedades_rs(pablo,P).
P = [estado:casado,edad:44,ciudad:mairena] 

?- propiedades_rs(pedro,P).
P = [ciudad:sevilla,estado:casado,edad:47]

Su definición es

propiedades_rs(Inst,Props) :-
   propiedades_especificas(Inst,P_Especificas),
   inst(Inst,Clase),
   herencia_rs(Clase,P_Especificas,Props).

herencia_rs(inicio,Props,Props).
herencia_rs(Clase,P_Actuales,Props) :-
   propiedades_especificas(Clase,P_Generales),
   actualiza(P_Actuales,P_Generales,N_P_Actuales),
   es_un(Clase,Super_clase),
   herencia_rs(Super_clase,N_P_Actuales,Props).

actualiza(Props,[],Props).
actualiza(P_Actuales,[Atr:_Valor|P_Generales],Props) :-
   member(Atr:_V,P_Actuales),
   actualiza(P_Actuales,P_Generales,Props).
actualiza(P_Actuales,[Atr:Valor|P_Generales],
                     [Atr:Valor|Props]) :-
   not(member(Atr:_V,P_Actuales)), 
   actualiza(P_Actuales,P_Generales,Props).

Nota: El código de esta sección se encuentra en redes_semanticas.pl.

6.3. Comentarios sobre redes semánticas

El razonamiento es independiente del orden de las cláusulas en las propiedades específicas
Se puede razonar sobre clases; por ejemplo, se puede calcular las subclases de persona:
```
?- es_un(X,persona).
X = alumno ;
X = profesor.
```
La estrategia de herencia se especifica declarativamente.
Es posible implementar estrategias de herencia múltiple

7. Marcos

7.1. Representación del conocimiento mediante marcos

Utilizaremos el mismo conocimiento sobre las personas de la sección anterior.
Las clases se representan por constantes: persona, alumno y profesor.
Las instancias se representan mediante constantes: juan, luis, pablo y pedro.

clase(C1,C2,Ps) se verifica si C1 es una subclase de C2 y Ps es la lista de las propiedades específicas de C1.

clase(persona, inicio, [ciudad:sevilla]).
clase(alumno,  persona,[estado:soltero]).
clase(profesor,persona,[estado:casado]).

instancia(I,C,Ps) se verifica si I es una instancia de C y Ps es la lista de las propiedades específicas de I.

instancia(juan,alumno,[edad:19]).
instancia(luis,alumno,[edad:24,estado:casado]).
instancia(pablo,profesor,[edad:44,ciudad:mairena]).
instancia(pedro,profesor,[edad:47]).

7.2. Razonamiento con marcos

propiedades_marco(I,P) se verifica si P es la lista de las propiedades de la instancia I. Por ejemplo,

?- propiedades_marco(juan,P).
P = [ciudad:sevilla,estado:soltero,edad:19] 
?- propiedades_marco(luis,P).
P = [ciudad:sevilla,edad:24,estado:casado] 
?- propiedades_marco(pablo,P).
P = [estado:casado,edad:44,ciudad:mairena] 
?- propiedades_marco(pedro,P).
P = [ciudad:sevilla,estado:casado,edad:47]

Su definición es

propiedades_marco(Inst,Props) :-
   instancia(Inst,Clase,PropsInst),
   herencia_marco(Clase,PropsInst,Props).

herencia_marco(inicio,Props,Props).
herencia_marco(Clase,P_Actuales,Props) :-
   clase(Clase,Super_clase,P_Generales),
   actualiza(P_Actuales,P_Generales,N_P_Actuales),
   herencia_marco(Super_clase,N_P_Actuales,Props).

actualiza(Props,[],Props).
actualiza(P_Actuales,[Atr:_Valor|P_Generales],Props) :-
   member(Atr:_V,P_Actuales),
   actualiza(P_Actuales,P_Generales,Props).
actualiza(P_Actuales,[Atr:Valor|P_Generales],
                     [Atr:Valor|Props]) :-
   not(member(Atr:_V,P_Actuales)), 
   actualiza(P_Actuales,P_Generales,Props).

El código de esta sección se encuentra en marcos.pl.

7.3. Comentarios sobre los marcos

El razonamiento es independiente del orden de las cláusulas en las propiedades específicas
Se puede razonar sobre clases; por ejemplo, se puede calcular las subclases de persona:
```
?- clase(X,persona,_).
X = alumno ;
X = profesor.
```
La estrategia de herencia se especifica declarativamente.
Es posible implementar estrategias de herencia múltiple

8. Bibliografía

P. Flach. Simply logical (Intelligent reasoning by example). (John Wiley, 1994)
- Cap. 4: Representing structured knowledge.
M. Ginsberg. Essentials of Artificial Intelligence. (Morgan Kaufmann, 1993)
- Cap. 13: Putting knowledge to work: frames and semantic nets.
P. Lucas y L.v.d. Gaag. Principles of expert systems. (Addison–Wesley, 1991).
- Cap. 4: Frames and inherance.
N.J. Nilsson y N.J. Nilsson Artificial intelligence: A new synthesis.
- Cap. 18.3: Knowledge representation by networks.
D. Poole, A. Mackworth y R. Goebel Computational intelligence (A logical approach)} (Oxford University Press, 1998)
- Cap. 5: Representing knowledge.
S. Russell y P. Norvig. Artificial intelligence: A modern approach (4th ed.). (Pearson, 2022).
- Cap. 9: Inference in first-order logic.
- Cap. 10: Knowledge representation.