Sistemas Expertos basados en Reglas

Tópicos

1. Introducción

2. Base de Hechos

3. Base de Conocimiento

4. Motor de inferencia

5. Métodos de encadenamiento

6. Técnicas de equiparación

7. Algoritmo RETE

8. Técnicas de resolución de Conflictos

1.-IntroducciónEn nuestra vida diaria encontramos muchas situaciones complejas gobernadas por reglas deterministas: sistemas de control de tráfico, sistemas de seguridad, transacciones bancarias, etc. Los sistemas basados en reglas son una herramienta eficiente para tratar estos problemas. Las reglas deterministas constituyen la más sencilla de las metodologías utilizadas en sistemas expertos. La base de conocimiento contiene las variables y el conjunto de reglas que definen el problema, y el motor de inferencia obtiene las conclusiones aplicando la lógica clásica a estas reglas. Por regla se entiende una proposición lógica que relaciona dos o más objetos e incluye dos partes, la premisa y la conclusión. Cada una de estas partes consiste en una expresión lógica con una o más afirmaciones objeto-valor conectadas mediante los operadores lógicos y, o, o no. Una regla se escribe normalmente como “Si premisa, entonces conclusión".

2.- Base de Hechos

Es una memoria auxiliar que contiene los datos del usuario Es una memoria auxiliar que contiene los datos del usuario (hechos iníciales que describen el problema a resolver) y los (hechos iníciales que describen el problema a resolver) y los resultados intermedios obtenido a lo largo del procedimiento resultados intermedios obtenido a lo largo del procedimiento de deducciónde deducción..

Definición

Ejemplo: Ejemplo: Diagnóstico de enfermedadesDiagnóstico de enfermedades

Datos personales del paciente: Datos personales del paciente: (nombre, dirección, N° de seguro)(nombre, dirección, N° de seguro)

Síntomas del paciente:Síntomas del paciente:(s1 s2 s3 s4 ....sk)(s1 s2 s3 s4 ....sk)

3.- Base del Conocimiento

DefiniciónDefinición

Es una estructura de datos que contiene el Es una estructura de datos que contiene el conjunto de conocimiento especializado conjunto de conocimiento especializado introducido por el experto del dominio (área del introducido por el experto del dominio (área del saber)saber)

3. Base de Conocimiento …

DefiniciónDefinición

Reglas de inferenciasReglas de inferencias

Es una estructura de representación del conocimiento que Es una estructura de representación del conocimiento que tiene la siguiente forma: tiene la siguiente forma:

Si ASi A11, A, A22,... A,... Aaa Entonces C Entonces C11, C, C22,... C,... Ccc

Patrones Si

Antecedentes

Patrones Entonces

Consecuente

3. Base de Conocimiento …

Ejemplo: Diagnóstico de EnfermedadesEjemplo: Diagnóstico de Enfermedades

• SiSi Síntoma11, Síntoma12, Síntoma13, ... Síntoma1k Síntoma11, Síntoma12, Síntoma13, ... Síntoma1k EntoncesEntonces Enfermedad 1 Enfermedad 1

• SiSi Síntoma21, Síntoma22, Síntoma23, ... Síntoma2k Síntoma21, Síntoma22, Síntoma23, ... Síntoma2k EntoncesEntonces Enfermedad 2 Enfermedad 2

• ......

• SiSi Síntoma n1, Síntoma n2, Síntoma n3, ... Síntoma nk Síntoma n1, Síntoma n2, Síntoma n3, ... Síntoma nk EntoncesEntonces Enfermedad Enfermedad nn

4.- Motor de Inferencia

Definición

Es la unidad lógica con la que se extraen conclusiones de la base de conocimientos, una conclusión se produce mediante aplicación de las reglas sobre los hechos presentes.

Decide que se debe aplicar, que se debe hacer, resuelve conflictos nuevos, hace uso de la base de conocimiento.

5 Métodos de Encadenamiento

Progresivo ó Encadenamiento hacia delanteProgresivo ó Encadenamiento hacia delanteLas inferencias se realizan desde los antecedentes Las inferencias se realizan desde los antecedentes hacia los consecuentes.hacia los consecuentes.

Regresivo ó Encadenamiento hacia atrásRegresivo ó Encadenamiento hacia atrásLas inferencias se realizan partiendo desde los Las inferencias se realizan partiendo desde los consecuentes hacia los antecedentesconsecuentes hacia los antecedentes

Reversibilidad Reversibilidad Reversibilidad Reversibilidad

Método de Encadenamiento Progresivo- Problema

Base de Conocimiento (BC):La base de conocimiento está conformado por un conjunto de reglas, La base de conocimiento está conformado por un conjunto de reglas, donde algunos antecedentes pueden ser consecuentes de otras reglas. donde algunos antecedentes pueden ser consecuentes de otras reglas. Además, solo existen interés de identificar determinados Además, solo existen interés de identificar determinados consecuentes, los cuales son llamados de consecuentes terminales.consecuentes, los cuales son llamados de consecuentes terminales.

Ejemplo : Base de Hechos(BH)

R1: Si A,B C BH = (H,I,K,M)

R2: Si D,E, F G Problema

R3: Si H,I J Determine el consecuente

R4: Si C,G K terminal asociado a BH

R5: Si G,J L

R6: Si K,L M

LCT : M Lista de Consecuentes terminales

Representación gráfica de las relaciones del

Problemas con sus 6 Reglas

Resumen Encadenamiento Progresivo

Se produce cuando el objetivo propuesto al sistema hace que se ejecute una regla, y la conclusión obtenida permite que se ejecute otra, y así sucesivamente hasta llegar a una respuesta, positiva o negativa. El punto final se detecta cuando no se pueden producir más encadenamientos, por ejemplo cuando se llega a un axioma ó hecho.

Ejemplo de Encadenamiento Progresivo

(1). SI (x ES JEFE_DPTO) ENTONCES (x ES CATEDRÁTICO)(2). CATEDRÁTICO("Mario Pérez")(3). CATEDRÁTICO("Manuel Fernandez")(4). CATEDRÁTICO("Maria Gonzalez")

Al evaluar el objetivo: "Mario Pérez es Jefe_Dpto"?, se dispara la R1, la cual a su vez se encadena con la R2 en este momento no se pueden producir más encadenamientos pues la regla R2 es un axioma. Llegado a este punto el Motor de Inferencia retrocede y da una respuesta positiva a la pregunta.

Encadenamiento RegresivoConsiste en, dado un objetivo, buscar una regla que permita establecer dicha conclusión, el proceso se repite hasta encadenar con la regla cuya conclusión satisfaga el objetivo propuesto, o se detecte que dicho problema no se puede resolver positivamente.

Por ejemplo para averiguar si "Mario Pérez es doctor" se busca un regla que tenga esta afirmación en sus consecuencias. Analizando las reglas anteriores vemos que la regla:

R5. SI (x ES CATEDRÁTICO) ENTONCES (x ES DOCTOR)Satisface estas condiciones; siguiendo esta regla hacia atrás tenemos que buscar una nueva que permita validar si "Mario Pérez" es catedrático, lo cual se hace con el axioma R2.

ConceptoConcepto

Se dice que una regla se dispara (equipara), si todos los Se dice que una regla se dispara (equipara), si todos los antecedente de dicha regla se verifican. antecedente de dicha regla se verifican.

Problemas :Problemas :1.- La equiparación del antecedente de las reglas con el 1.- La equiparación del antecedente de las reglas con el estado de la BH no siempre es obvia.estado de la BH no siempre es obvia.2.- La necesidad de examinar todas las reglas en cada ciclo 2.- La necesidad de examinar todas las reglas en cada ciclo de inferencias. Proceso poco eficiente, si hay que recorres de inferencias. Proceso poco eficiente, si hay que recorres toda la BC y ésta contiene numerosas reglas.toda la BC y ésta contiene numerosas reglas.

6. Equiparación

6. Equiparación …

Soluciones :

1.-Técnicas de indexación .- Consisten en añadir a las reglas nuevas condiciones relacionadas con el punto de inferencia. Esto permite dividir el problema en varias etapas y agrupar las reglas en función de la etapa en la que se aplican.

La indexación suele ser un factor importante para la eficiencia de los SBR.

2.-Técnicas que aceleran el proceso de equiparación, sin necesidad de examinar toda la BC. Método más conocido es el algoritmo RETE

Algoritmo RETE

• El algoritmo Rete es un algoritmo de reconocimiento de patrones eficiente para implementar un sistema de producción de Reglas. Fue creado por el Dr. Charles L.Forgy en la Carnegie Mellon University,1979.

• Rete es hoy en día la base de muchos SE muy famosos, incluyendo CLIPS, Jess, JBoss Rules y Soar.

Algoritmo RETE …

El algoritmo RETE lo que hace primero es compilar la memoria de reglas en la red.

– Los círculos representan las pruebas de predicado.

– Los rectángulos representan acciones: añadir E, añadir D, borrar A.

– Los cuadrados representan unificaciones ó restricciones: A=B significa que las soluciones de las pruebas de A y de B deben ser las mismas; A=D lo mismo, respectivamente para A y D .

– Memoria de Trabajo WM = {A(1), A(2), B(2), B(3), B(4), C(5)} A(x) B(y) D(x) => sumar E(x)A(x) B(x) C(y) => sumar D(x)A(x) B(x) E(z) => borrar A(x)

PARAMETROS

Algoritmo RETE …

Algoritmo RETE…

Desventajas• Consume gran cantidad de memoria para incrementar velocidad de

procesamiento.

Ventajas • Elimina la duplicación en la reglas. Esta red se modifica luego de una

incorporación o una eliminación.• La fase de solución de conflictos sirve para decidir cuál de las sugerencias se va

a aceptar,  a esta fase se la puede considerar como la estrategia de control. • Algunas de las estrategias son:

– No duplicación. No aplica dos veces la misma regla a los mismos argumentos.

– Novedad. Prefiere aquellas reglas que se refieren a elementos de la memoria de trabajo de reciente creación.

– Especificidad. Da preferencia a aquellas reglas que sean más específicas. – Prioridad de operación. Prefiere aquellas reglas que tienen mayor prioridad,

según lo especificado por cierto sistema de calificación

Método de Encadenamiento Progresivo

Algoritmo Algoritmo

1.1. ReadRead(BC); (BC); ReadRead(BH);(BH);2.2. sw_sol sw_sol False; False; sw_di sw_di True; True;3. 3. WhileWhile not(sw_sol) not(sw_sol) and (sw_di) and (sw_di)3.1 3.1 Verificar c/regla de BC Verificar c/regla de BC3.23.2 Resolver_conflicto(Rx, Cx, sw_di)Resolver_conflicto(Rx, Cx, sw_di)3.33.3 IfIf (sw_di) (sw_di)3.4 3.4 thenthen BH BH BH + Cx BH + Cx3.5 3.5 IfIf Cx Cx ЄЄ LCT then sw_sol LCT then sw_sol

True;True;4.4. IfIf (sw_sol) (sw_sol)4.1 4.1 thenthen WriteWrite(“Solución =”, Cx),(“Solución =”, Cx),4.2 4.2 else else Write(“No hay Solución”); Write(“No hay Solución”);

MOTOR DE INFERENCIA

ParámetrosParámetros

sw_sol: sw_sol: es una variable lógica que indica si se es una variable lógica que indica si se encontró (True) o no (False) una solución. encontró (True) o no (False) una solución.

sw_di: sw_di: es una variable lógica que indica si se es una variable lógica que indica si se dispara (True) o no (False) una regla.dispara (True) o no (False) una regla.

Resolver_conflicto (Rx, Cx, sw_di):Resolver_conflicto (Rx, Cx, sw_di):Es una rutina que verifica que regla de la Es una rutina que verifica que regla de la

BC BC se dispara, selecciona una regla Rx de se dispara, selecciona una regla Rx de consecuente Cx en el caso se dispara al consecuente Cx en el caso se dispara al menos una regla (sw_di menos una regla (sw_di True) o True) o proporciona False para la variable sw_di proporciona False para la variable sw_di

en el en el caso que ninguna regla se dispara.caso que ninguna regla se dispara.

Método de Encadenamiento Progresivo

Estrategias para resolver conflictosEstrategias para resolver conflictos Resolver_conflicto (Rx, Cx, sw_di)Resolver_conflicto (Rx, Cx, sw_di)

1)1) Seleccionar la primera regla que se dispara (equipara)Seleccionar la primera regla que se dispara (equipara)2)2) Seleccionar la regla que presenta mayor prioridadSeleccionar la regla que presenta mayor prioridad3)3) Seleccionar una regla que no se haya ejecutado antes (principio de Seleccionar una regla que no se haya ejecutado antes (principio de

refracción) refracción) 4)4) Seleccionar arbitrariamente una regla.Seleccionar arbitrariamente una regla.5)5) Seleccionar la regla más general, esto es que presente menos Seleccionar la regla más general, esto es que presente menos

antecedentes.antecedentes.

Para resolver el problema de conflictos de reglas, esto es, de Para resolver el problema de conflictos de reglas, esto es, de seleccionar una regla a procesar entre las disparadas (equiparadas), se seleccionar una regla a procesar entre las disparadas (equiparadas), se puede usar cualquiera de las estrategias, incluso en forma combinada. puede usar cualquiera de las estrategias, incluso en forma combinada.

Método de Encadenamiento Progresivo

ObservacionesObservaciones

1)1) El algoritmo propuesto se aplica a problemas donde la respuesta del El algoritmo propuesto se aplica a problemas donde la respuesta del sistema es una sola. Esta situación ocurre cuando los consecuentes que sistema es una sola. Esta situación ocurre cuando los consecuentes que pertenecen al LCT son excluyente, por ejemplo, en los problemas de pertenecen al LCT son excluyente, por ejemplo, en los problemas de segmentación de mercados, clasificación por tipo de riesgo, etc.segmentación de mercados, clasificación por tipo de riesgo, etc.

2)2) El algunos casos los consecuentes terminales no son excluyentes como El algunos casos los consecuentes terminales no son excluyentes como en los problemas de diagnóstico de enfermedades, en el cual un paciente en los problemas de diagnóstico de enfermedades, en el cual un paciente puede tener más de una enfermedad. En este caso se requiere generar puede tener más de una enfermedad. En este caso se requiere generar todos los consecuente terminales que se verifican.todos los consecuente terminales que se verifican.

3)3) En algunas situaciones las reglas deben ser procesadas según una En algunas situaciones las reglas deben ser procesadas según una prioridad establecida. Para este caso bastará con ordenar la BC de prioridad establecida. Para este caso bastará con ordenar la BC de acuerdo a la prioridad antes de usar el motor de inferencia, o se podrá acuerdo a la prioridad antes de usar el motor de inferencia, o se podrá considerar la prioridad en la estrategia para resolver conflictoconsiderar la prioridad en la estrategia para resolver conflicto

Método de Encadenamiento Progresivo

Método de Encadenamiento Progresivo

Algoritmo - Todos los consecuentes terminalesAlgoritmo - Todos los consecuentes terminales

1.1. ReadRead(BC); (BC); ReadRead(BH);(BH);2.2. LS LS { }; { }; sw_di sw_di True; True;3. 3. WhileWhile (sw_di)(sw_di)3.1 3.1 Verificar c/regla de BC Verificar c/regla de BC3.23.2 Resolver_conflicto(Rx, Cx, sw_di)Resolver_conflicto(Rx, Cx, sw_di)3.33.3 IfIf (sw_di) (sw_di)3.4 3.4 thenthen BH BH BH + Cx BH + Cx3.5 3.5 IfIf Cx Cx ЄЄ LCT then LS LCT then LS LS + LS +

Cx;Cx;4.4. IfIf (LS <> { }) (LS <> { })4.1 4.1 thenthen WriteWrite(“Soluciones =”, LS),(“Soluciones =”, LS),4.2 4.2 else else Write(“No hay Solución”); Write(“No hay Solución”);

MOTOR DE INFERENCIA

Método de Encadenamiento Progresivo

Algoritmo - Todos los consecuentes terminales Algoritmo - Todos los consecuentes terminales + prioridades+ prioridades

1.1. ReadRead(BC); (BC); ReadRead(BH); (BH); ReadRead(prioridades);(prioridades);2.2. LS LS { }; { }; sw_di sw_di True; Ordenar(BC, prioridades) True; Ordenar(BC, prioridades)3. 3. WhileWhile (sw_di)(sw_di)3.1 3.1 Verificar c/regla de BC Verificar c/regla de BC3.23.2 Resolver_conflicto(Rx, Cx, sw_di)Resolver_conflicto(Rx, Cx, sw_di)3.33.3 IfIf (sw_di) (sw_di)3.4 3.4 thenthen BH BH BH + Cx BH + Cx3.5 3.5 IfIf Cx Cx ЄЄ LCT then LS LCT then LS LS + LS +

Cx;Cx;4.4. IfIf (LS <> { }) (LS <> { })4.1 4.1 thenthen WriteWrite(“Soluciones =”, LS),(“Soluciones =”, LS),4.2 4.2 else else Write(“No hay Solución”); Write(“No hay Solución”);

MOTOR DE INFERENCIA

EjerciciosProblema : Acreditación Financiera Para efecto de hacer más eficiente el proceso de acreditación

financiera; las organizaciones financieras que usan lo más avanzado en tecnología de información realizan la acreditación financiera automática a través del uso de sistemas expertos. Esta automatización es indispensable para el posicionamiento en el mercado financiero, por dos razones: reduce el tiempo del proceso de préstamo de semanas a segundos, y reduce la tasa de morosidad ocasionada por la intervención humana. Considere la siguiente Base de Conocimiento de un pool de especialistas en acreditación de una organización financiera: R1: Sí Y, C6 XR2: Sí C1, C4 YR3: Sí C7, X, Y PR4: Sí C1, X C7R5: Sí C2, C7, Z RR6: Sí Y, C5 ZR7: Sí C1 C3 C4R8: Sí C4, C2 C6R9: Sí C3, C4 C5

Ejercicios

Los antecedentes de las reglas arriba, son dados por las características financieras asociado a los tipos de riesgos (Riesgo alto, riesgo normal, sin riesgo) y a la acreditación financiera (otorgar crédito, rechazar crédito), como son: ingreso personal y familiar, deudas vencidas, protestos, tipos de riesgo financiero, etc. El sistema deberá concluir con dar crédito (P) ó rechazar crédito R. El experto informa que por experiencia las reglas deben ser procesadas de acuerdo a una prioridad, e informa la siguiente prioridad (las reglas de mayor prioridad deberán ser primero procesadas):

Ejercicios

Reglas R1 R2 R3 R4 R5 R6 R7 R8 R9Prioridad 3 6 7 2 5 9 8 1 4

Responda:1. Presente el algoritmo de encadenamiento progresivo sugerido para

resolver el problema de segmentación financiera automática. Defina el LCT.

2. Los resultados de un sistema de consolidación financiera (sea de

Certicom ó Inforcorp) para un cliente con DNI No. 0644497910 presenta los siguientes resultados: C1,C2,C4. Determine si se debe dar ó rechazar crédito. Muestre en una tabla, iteración por iteracción los resultados del algoritmo.

3 Si el resultado no P ni R. ¿Qué usted podría sugerir al decisor?.