Tema 3: Representación del conocimiento estructurado · conocimiento estructurado José A. Alonso Jiménez Carmen Graciani D´ıaz Francisco Jesus´ Mart´ın Mateos José Luis

Inteligencia Artificial II Curso 2003–2004

Tema 3: Representacion delconocimiento estructurado

Jose A. Alonso Jimenez

Carmen Graciani Dıaz

Francisco Jesus Martın Mateos

Jose Luis Ruiz Reina

Dpto. de Ciencias de la Computacion e Inteligencia Artificial

Universidad de Sevilla

IA-II 2003–2004 CcIa Representacion del conocimiento estructurado 3.1

Clasificacion de formalismos

Conceptos

x Objeto–atributo–valor

Relaciones entre conceptos

x Redes semanticas

x Marcos

x Logicas descriptivas


Redes semanticas

x C.S. Pierce, finales s. XIX: propone representar oraciones logicas con“grafos existenciales”

x El uso de grafos es tradicional en Filosofıa y Filologıa

x R. Quilliam, 1968: representar la semantica de las palabras

u Lenguaje natural y traduccion

x Redes asociativas: relaciones entre conceptos y/u objetos

x Precursoras de los marcos y estos, a su vez, de la programacion orientadaa objeto


Definicion basica

x Grafo dirigido y etiquetado

x Nodo: concepto (objeto o conjunto de objetos)

u Valores de propiedades

x Arco: relacion o asociacionu parte-de: una clase de objetos es una subclase de otra, ⊆u es-un: un objeto pertenece a una clase de objetos, ∈u relacion: entre los conceptos asociados

Propiedades

x Estructura jerarquica

x Transitividad

x No monotono


Ejemplo

casado

persona ciudadSevilla

part

e−de

profesor estado

es−

un

es−

un

Luis Juan

parte−de

alumnoestado

soltero

es−

un

casadoPablo

19

es−

un

Pedro

24

Jaen

4447

edad edad edadedad

estadociudad

inicioparte−de


Razonamiento

Equiparacion

x Construir una red con los elementos de la pregunta

x Cotejarla con la Base de Conocimiento equiparando los nodos

Herencia

x Simple

x Con excepciones

x Herencia multiple

x Herencia y cambios


Herencia simple con excepciones

FUNCION PROP_ESPECIFICAS_RS(CONCEPTO)

Devolver el conjunto de pares (PROP, VAL) (con PROP distinto de es-un y

parte-de) para los que CONCEPTOPROP−−→ VAL

FUNCION PROPIEDADES_RS(CONCEPTO)

1. Sea PE el conjunto de PROP_ESPECIFICAS_RS(CONCEPTO)

2. Sea PH el conjunto HERENCIA_RS(CONCEPTO, PE)

3. Devolver PE ∪ PH

FUNCION HERENCIA_RS(CONCEPTO, P_CONOCIDAS)

1. Si CONCEPTO = inicio (es decir, se trata de la clase inicial)

entonces

1.1 Devolver el conjunto vacıo

2. Si CONCEPTOprop−−→ CLASE (donde prop es es-un o parte-de)

entonces

2.1 Devolver PROPIEDADES_RS(CLASE) menos los pares (PROP, VAL) tales

que exista un par (PROP, VAL’) ∈ P_CONOCIDAS


Ejemplos

?- [redes_semanticas].

% ...

Yes

?- propiedades_rs(juan, P).

P = [edad:44, ciudad:jaen, estado:casado]

Yes

?- propiedades_rs(pedro, P).

P = [edad:24, estado:soltero, ciudad:sevilla]

Yes

?- propiedades_rs(pablo, P).

P = [estado:casado, edad:19, ciudad:sevilla]

Yes

?- es_un(pablo, C).

C = alumno

Yes

?- propiedades_rs(alumno, P).

P = [estado:soltero, ciudad:sevilla]

Yes


Ventajas y desventajas

Ventajas

x Explıcito y condensado

x Reduce el tiempo de busqueda

x Evitar repeticiones y compartir conocimiento

Desventajas

x No se pueden representar negaciones, disyunciones, cuantificacion

x No se pueden incluir conocimientos procedimentales

x Sin interpretacion estandar

x Posibilidad de herencias inconsistentes en herencia multiple

x Explosion combinatoria


Marcos

x O. Selz, principios del siglo XX

u Resolver un problema es completar la informacion existente

x M. Minsky, 1975

u Control semantico en reconocimiento de patrones

x Construir ontologıas

u Metodologıas: Cyc, METHONTOLOGY, (KA)2, ...

u Lenguajes: LOOM, Ontolingua, RDF, OIL, DAML+OIL, OWL, ...

u Herramientas: Ontolingua, WebODE, Protege


Definicion

x Marco: conjunto de propiedades que caracterizan un concepto (objetoo conjunto de objetos)

u Los valores de las propiedades pueden ser procedimientos de calculo de valores y

actualizacion de informacion relacionada

x Sintaxis: nombre del marco + conjunto de pares atributo–valor (slot–fillers), donde cada valor puede ser:

u Dato

u Conjunto de pares faceta–dato

u Rango

u Por defecto

u Acciones: si se necesita (If-Needed), si se anade (If-Added), si se cambia (If-

Changed)


Ejemplo de marco

Marco AUTOMOVIL

Subclase de VEHICULO

Supercalse de : {MONOVOLUMEN TURISMO DEPORTIVO}

Fabricante:

Rango: {BMW FIAT RENAULT SEAT}

Por defecto: SEAT

Pais-de-fabricacion:

Rango: {ALEMANIA ITALIA FRANCIA ESPA~NA}

Por defecto: ESPA~NA

Modelo:

Rango: {}

Color:

Rango: {ROJO BLANCO GRIS AZUL}

Si-se-necesita: { CONSULTAR_FICHA CONSULTAR_FABRICANTE }

A~no:

Rango: 1980-2000

Si-se-cambia: {ERROR: El valor no se puede modificar}

Propietario:

Si-se-a~nade: {COMPROBAR_PERMISO A~NADIR_MATRICULA INGRESAR_IMPUESTOS}


Marcos: Jerarquıa e inferencia

x Taxonomıa: organizacion jerarquica de marcos (arbol)

u Usualmente solo relaciones de jerarquıa

x Inferenciau Equiparacion

u Herencia

u Simple

u Multiple

u Gestion dinamica de valores


Tipos de marcos

x Clase:u Conceptos o situaciones genericas

u Se describen por un conjunto de propiedades

x Instancia:u Objetos concretos o individuos

u Relacionados con un marco clase

u Heredan propiedades

Propiedades

x Marcos “superiores”: sus caracterısticas se consideran “fijas”

x Marcos “inferiores”: sus caracterısticas pueden variar, siguen el esquemade las superiores


Ejemplo

Inicio

MC

Persona Ciudad Por defecto: Sevilla

Rango: Soltero, Casado Edad Rango: 0−100

Estado

Profesor Estado Por defecto: Casado Categoria

Alumno Estado Por defecto: Soltero Titulacion

Luis Edad: 47 Categoria: Catedratico

Juan Edad: 44 Ciudad: Jaen Categoria: Asociado

Pablo Estado: Casado Edad: 19 Titulacion: II

Pedro Edad: 24 Titulacion: ITIS

MCMC

MC

MI

MI

MI

MI


Inferencia

Equiparacion

x Pregunta en forma de marco: conjunto de pares atributo–valor

x Marcos clase en los que se encuentra definida alguno de los atributos

x Descender en el arbol equiparando los restantes pares

Valores activos

x Al anadir: permite deducir valores de otras propiedades a partir delvalor de la propiedad asociada

x Al modificar: permite modificar otros valores en funcion del valor de lapropiedad asociada

x ...


Herencia simple con excepciones (sin facetas)

FUNCION PROPIEDADES_MARCO(CONCEPTO)

1. Sea PE el conjunto de pares (PROP, VAL) tales que PROP es una

propiedad del marco CONCEPTO y es posible obtener el valor asociado VAL

a partir de la informacion almacenada en el marco

2. Sea PH el conjunto HERENCIA_MARCO(CONCEPTO, PE)

3. Devolver PE ∪ PH

FUNCION HERENCIA_MARCO(CONCEPTO, P_CONOCIDAS)

1. Si CONCEPTO = inicio (es decir, se trata del marco inicial)

entonces

1.1 Devolver el conjunto vacıo

2. Si CONCEPTO −→ CLASE

entonces

2.1 Devolver PROPIEDADES_MARCO(CLASE) menos los pares (PROP, VAL) tales

que exista un par (PROP, VAL’) ∈ P_CONOCIDAS


Ejemplo

?- [marcos].

% ...

Yes

?- propiedades_marco(juan, P).

P = [edad:44, ciudad:jaen, categoria:asociado, estado:casado]

Yes

?- propiedades_marco(pedro, P).

P = [edad:24, titulacion:itis, estado:soltero, ciudad:sevilla]

Yes

?- propiedades_marco(pablo, P).

P = [edad:19, estado:casado, titulacion:ii, ciudad:sevilla]

Yes

?- pertenece_a(pablo, C).

C = alumno

Yes

?- propiedades_marco(alumno, P).

P = [estado:soltero, ciudad:sevilla]

Yes


Ventajas y Desventajas

Ventajas

x Facilita el procesamiento de la informacion

x Organizacion del conocimiento

x Capacidad de almacenar valores dinamicos

Desventajas

x Excepciones de los prototipos

x Acomodacion a nuevas situaciones

x Uso de conocimiento heurıstico


Objetos

x Objeto: conjunto de informacion que describe una entidad y descripcionde como manipularla

Propiedades

x Abstraccion: en los datos y procedimientos

x Encapsulamiento: ocultacion de informacion

x Herencia

x Polimorfismo: varios significados para un mismo operador y posibilidadde hacer referencia a diversas clases


Logica Descriptiva

x Permite definir categorıas en terminos de relaciones

x Inferenciau Subsuncion: determinar si una categorıa es subclase de otra, en funcion de sus

descripciones

u Clasificacion: determinar si un objeto pertenece a una determinada categorıa si-

guiendo su descripcion

x Polinomial en el tamano de la descripcion de una consulta

x Classic: Borgida, 1989


Bibliografıa

x Flach, P. “Simply Logical (Intelligent Reasoning by Example)” (JohnWiley, 1994)

x Lucas, P. y Gaag, L. v. d. “Principles of Expert Systems” (Addison–Wesley, 1991)

x Poole, D.; Mackworth, A. y Goebel, R. “Computational Intelligence(A Logical Approach)” (Oxford University Press, 1998)

x Russell, S y Norvig, P. “Inteligenica artificial (Un enfoque moderno)”(Prentice–Hall Hispanoamerica, 1996)

x Gonzalez, A. J. y Dankel, D. D. “The engineering of knowledge–basedsystems (Theory and practice)” (Prentice-Hall International Editions,1993)


Inteligencia Artificial II Curso 2003–2004

Tema 3 (anexo):Implementaciones en Prolog

Dpto. de Ciencias de la Computacion e Inteligencia Artificial

Universidad de Sevilla


Redes semanticas (nodos y arcos)

% Relaciones entre clases: parte_de(CLASE, SUPERCLASE)

parte_de(persona,inicio).

parte_de(alumno, persona).

parte_de(profesor, persona).

% Relaciones entre objeto y clase: es_un(OBJETO, CLASE)

es_un(juan, profesor). es_un(luis, profesor).

es_un(pablo, alumno). es_un(pedro, alumno).

% Propiedades de un objeto o clase: prop(CONCEPTO, ATRIBUTO, VALOR)

prop(persona, ciudad, sevilla).

prop(alumno, estado, soltero).

prop(profesor, estado, casado).

prop(juan, edad, 44). prop(pablo, estado, casado).

prop(juan, ciudad, jaen). prop(pablo, edad, 19).

prop(luis, edad, 47). prop(pedro, edad, 24).


Redes semanticas (herencia simple con excepciones) I

% propiedades_rs(+CONCEPTO, ?PROPIEDADES)

propiedades_rs(CONC, PROPS) :-

propiedades_especificas_rs(CONC, PE),

herencia_rs(CONC, PE, PH),

append(PE, PH, PROPS).

% propiedades_especificas_rs(+CONCEPTO, ?PROPIEDADES)

propiedades_especificas_rs(CONC, PE) :-

findall(Atr:Valor, prop(CONC, Atr, Valor), PE).

% herencia_rs(+OBJETO, +P_CONOCIDAS, ?PROPIEDADES)

herencia_rs(OBJ, PC, PROPS) :-

es_un(OBJ, CLASE),

propiedades_rs(CLASE, PROPCL),

elimina(PROPCL, PC, PROPS).


Redes semanticas (herencia simple con excepciones) II

% herencia_rs(+CLASE, +P_CONOCIDAS, ?PROPIEDADES)

herencia_rs(inicio, _PC, []).

herencia_rs(CLASE, PC, PROPS) :-

parte_de(CLASE, SUPERCLASE),

propiedades_rs(SUPERCLASE, PROPCL),


% elimina(+LP1, +LP2, ?PROPS)

elimina([], LP2, []).

elimina([Atr:_Valor| LP1], LP2, PROPS) :-

member(Atr:_V, LP2),

elimina(LP1, LP2, PROPS).

elimina([Atr:_Valor| LP1], LP2, [Atr:_Valor|PROPS]) :-

not(member(Atr:_V, LP2)),

elimina(LP1, LP2, PROPS).


Marcos (nodos y arcos)

% Marcos: marco(CONCEPTO, PROPIEDADES)

% Solo se implementan marcos sin facetas, solo recoge pares (PROP, VALOR)

marco(inicio, []).

marco(persona, [ciudad:sevilla]).

marco(alumno, [estado:soltero]).

marco(profesor, [estado:casado]).

marco(juan, [edad:44, ciudad:jaen, categoria:asociado]).

marco(luis, [edad:47, categoria:catedratico]).

marco(pablo, [edad:19, estado:casado, titulacion:ii]).

marco(pedro, [edad:24, titulacion:itis]).

% Relaciones entre marcos: pertenece_a(CONCEPTO, CLASE)

pertenece_a(persona, inicio).

pertenece_a(alumno, persona).

pertenece_a(profesor, persona).

pertenece_a(juan, profesor). pertenece_a(pablo, alumno).

pertenece_a(luis, profesor). pertenece_a(pedro, alumno).


Marcos (herencia)

% propiedades_marco(+CONCEPTO, ?PROPIEDADES)

propiedades_marco(CONC, PROPS) :-

marco(CONC, PE),

herencia_marco(CONC, PE, PH),

append(PE, PH, PROPS).

% herencia_marco(+OBJETO, +P_CONOCIDAS, ?PROPIEDADES)

herencia_marco(inicio, _PC, []).

herencia_marco(CONCEPTO, PC, PROPS) :-

pertenece_a(CONCEPTO, CLASE),

propiedades_marco(CLASE, PROPCL),



Documents

Tema 3: Representación del conocimiento estructurado · conocimiento estructurado José A. Alonso Jiménez Carmen Graciani D´ıaz Francisco Jesus´ Mart´ın Mateos José Luis