Sistemas Periciais: abordagem baseada em Modelos
Sistemas Periciais Baseados em
Conhecimento Empírico
Aquisição conhecimento
Moroso, difícil
BC incompletas / inconsistentes
Explicações de Baixo Nível
Lidar com Problemas não previstos: como?
Validação difícil (grandes BC, ambientes
dinâmicos)
Aplicáveis em domínios restritos
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
SP baseados em Modelos
Conhecimento Profundo vs Conhecimento
Superficial
SP:Modelos
Conhecimento
Quantitativos
Ernesto Costa
Inferência
Qualitativos
Propagação de Restrições
Sistemas Periciais: abordagem baseada em Modelos
Modelos Quantitativos
I
V
R
V=R*I
Lei de Ohm
I
C
V
I C
dV
dt
As equações estabelecem restrições sobre os
valores que as variáveis podem assumir!
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Modelos Qualitativos
Abstracção qualitativa
[V] = [I]
[I] = [dV]
Características
Aceita informação imprecisa
Inferências rápidas
Computacionalmente custosa
Resultados eventualmente ambíguos
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Inferência: propagação de restrições
F=m*a
Quantitativa
F=40; m=4
a=10
Qualitativa
[a] = + ; [m] = 0
[F]= +
Ambiguidade
a=10
F=? ; m= ?
[a]=+ ; [m] = [F]=?
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Aplicação ao Diagnóstico
Metodologia Geral
Definir as equações do modelo
Definir valores iniciais
Propagar valores (respeitando as restrições) e definir
os valores esperados
Observar os valores reais
Se diferente: estabelecer diagnóstico
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Exemplo
in1
in2
(Reiter)
M1
out
A1
in1
in2
M2
out
A2
in1
in2
Ernesto Costa
M3
Sistemas Periciais: abordagem baseada em Modelos
Sistema S=(DS,COMP)
DS = descrição
COMP = componentes
Descrição
Genérica:
Mul(m)  AB(m)  out(m)  in1(m) * in2(m)
Som(a)  AB(a)  out(a)  in1(a)  in2(a)
Axiomas
Concretos: AB(M 1)  out(M 1)  in1(M 1) * in2(M 1)
Topológicos: out(M1)  in1( A1)
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Componentes
Mul(M1); Mul(M2); Mul(M3) ; Som(A1); Som(A2)
Observações (OBS)
in1(M1)=3
in2(M1)=2
in1(M2)=3
in2(M2)=2
in1(M3)=3
in2(M3)=2
out(A1)=10
out(A2)=12
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Diagnóstico
Problema
3
2
in1
in2
DS {AB(c1 ),...,AB(cn )} OBS 
M1
out
A1
3
2
in1
in2
M2
out
A2
3
2
Ernesto Costa
in1
in2
M3
10
12
Sistemas Periciais: abordagem baseada em Modelos
Um diagnóstico para S=(DS,COMP,OBS) é um
conjunto mínimo   COMP tal que:
DS  OBS {AB(c) | c  } {AB(c) | c  COMP  }
é consistente!
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Determinar o diagnóstico
Conjunto de conflito
Todo o subconjunto de componentes{c1,...,ck}:
DS  OBS {AB(c1 ),...,AB(ck )}
é inconsistente!
Mínimo: se nenhum subconjunto próprio for de
conflito
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Conjunto de Candidatos (“hitting set”)
Seja C uma colecção de conjuntos. Um CC para C é um
conjunto H:
H   S : H  S {}, S  C
SC
Será mínimo se nenhum subconjunto próprio de H for
CC para C
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Teorema
é um diagnóstico para (DS,COMP,OBS)
sse  for um CC mínimo para a colecção de
conjuntos de conflito para (DS,COMP,OBS)
  COMP
Como calcular o conjunto de candidatos?
Através da árvore de conjunto de candidatos, ÁrvoreCC
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Árvore-CC
Como construir?
Seja F uma colecção de conjuntos. Uma Árvore-CC, A
para F é uma Árvore-CC sse for a árvore etiquetada
mais pequena com as seguintes propriedades:
A sua raiz terá etiqueta  se F for o conjunto vazio; caso
contrário a raiz terá por etiqueta um elemento de F.
Se n for um nó de A, seja L(n) o conjunto das etiquetas
associadas aos lados que ligam a raiz a n. Se n tiver por
etiqueta  então n não terá sucessores. Se n tiver por
etiqueta um conjunto  de F, então terá tantos sucessores
quantos o número dos seus elementos. Cada arco terá por
etiqueta um elemento de . Cada novo nó ns terá por
etiqueta um conjunto S de F cuja intersecção com L(ns) for o
conjunto vazio, caso esse conjunto exista, caso contrário a sua
etiqueta será  .
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Propriedades de uma Árvore-CC A para F
[consistência] Se n for um nó com etiqueta 
então L(n) é um conjunto de candidatos para F;
[completude]Cada conjunto de candidatos
mínimo para F é dado por L(n) para algum nó n
da árvore que tenha etiqueta  .
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Exemplo
F={{2,4,5},{1,2,3},{1,3,5},{2,4},{1,6}}
{2,4,5}
2
5
4
{1,3,5}
1
{1,2,3}

{1,6}
1
1
5
3
6
1
6
3
2

{1,6}
{2,4}
{1,6}
1
6
2
{1,6}
1
4
{1,6}
6
1
6
{1,6}
1
6
 
   
  
 
L(n)={1,2,4} é um CC para F
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Árvore-CC Truncada
Critérios de corte
(1) n=  ;n': L(n)  L(n' )  cortar
n'
(2) L(n)  L(n' )  cortar
n'
(3) S , S ' A, S '  S  cortar  :   S  S '
{2,4,5}
2
(3)
5
4
{1,3,5}
1
{1,6}
1
6
1
(1)
1
6
{2,4}
3
2

{1,6}
× 
×
Ernesto Costa
(2)
5
3

(1)
{1,2,3}
{1,6}
1
6
{1,6}
1
 × 
×
(1)
(1)
6

2
4
×
{1,6}
1
6
 
Sistemas Periciais: abordagem baseada em Modelos
Teorema
Seja F uma colecção de conjuntos, e A a ÁrvoreCC truncada para F. Então
{L(n) | n  A, n   }
é a colecção dos conjuntos de candidatos
mínimos para F.
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
De novo o Exemplo
Algoritmo
(1) Calcular a colecção dos conjuntos de conflito para
(DS,COMP,OBS), F.
(2) Construir a Árvore-CC truncada para F, A
(3) Devolver como diagnósticos possíveis a colecção
dos conjuntos de candidatos mínimos para F:
{L(n) | n  A, n   }
Para (1) é necessário um demonstrador de teoremas
DT(DS,COMP,OBS) que devolve um conjunto de conflito
caso exista, caso contrário devolve 
Princípio de Resolução
Propagação de restrições
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Construção
3 in1
2 in2
M1
out
A1
3
2
in1
in2
M2
out
A2
3 in1
2 in2
12
M3
DT(DS,{M1,M2,M3,A1,A2},OBS)
Ernesto Costa
10
{A1,M1,M2}
Sistemas Periciais: abordagem baseada em Modelos
Porquê {A1,M1,M2}?
Propagação de restrições
De
AB(M 1)  out(M 1)  in1(M 1) * in2(M 1)
AB(M 2)  out(M 2)  in1(M 2) * in2(M 2)
AB( A1)  out( A1)  in1( A1)  in2( A2)
out(M 1)  in1( A1)
out(M 2)  in2( A1)
Conclui-se
AB(M 1)  out(M 1)  6
AB(M 2)  out( M 2)  6
AB( A1)  AB(M 1)  AB(M 2)  out( A1)  12
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
A Árvore-CC
{A1}
{M1}

DT(DS,{M1,M2,M3,A2},OBS)
DT(DS,{M1,M3,A1,A2},OBS)
{A1,M1,M2}

DT(DS,{M2,M3,A1,A2},OBS)
{M2}
{M1,M3,A1,A2}
{M1}
×
(1)
{M3}

DT(DS,{M1, A1,A2},OBS)
{A1}
{A2}
×

(1)
DT(DS,{M1, M3,A1},OBS)
Diagnóstico = {{A1}, {M1}, {M2,M3}, {A2,M2}}
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
That’s All Folks
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Exemplo
(Garcia e Morales)
H
A2
A
C
F
A1
M1
B
D
E
M2
Modelo
G
I
A3
I=((A*B)*(C+D))+(C+D)
H=(A*B)-(C+D)
Restrições
E=A*B; G=E*F; I=G+F; F=C+D; H=E-F
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Espaço de Candidatos (25=32)
[]
A1
A1,A2
A1,A2,A3
A1,A2,A3,M1
A2
A3
A1,A3
M1
A1,M1 A1,M2
...
A1,A2,M1 A1,A2,M2 A1,A3,M1 ...
A1,A2,A3,M2
A1,A2,M1,M2...
A1,A2,A3,M1,M2
Ernesto Costa
M2
Sistemas Periciais: abordagem baseada em Modelos
Valores Iniciais
Valor
Lista de Dependências
A=1 [] 0
B=2 [] 0
C=2 [] 0
D=3 [] 0
Ambiente
Propagando
E=2 [M1] 0
F=5 [A1] 0
G=10 [A1,M1,M2] 0
H=-3 [A1,A2,M1] 0
I=15 [A1,A3,M1,M2] 0
Ernesto Costa
Valores Esperados!
Sistemas Periciais: abordagem baseada em Modelos
Observando!
I=11 [] 1
Conjunto de Conflito Mínimo
[A1,A3,M1,M2]
A2 Eliminado!
Propagando (usando as restrições)
G=6 [A1,A3] 1
E=6/5 [A1,A3,M2] 1
H=-19/5 [A1,A2,A3,M1] 1
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Observando
E= 2 [] 2
E associado a M1 está OK!
Eliminar M1 do CMS e todos os seus super-conjuntos
Eliminar M1 das listas de Dependências
Propagando
G= 10 [A1,M2] 2
H= -3 [A1,A2] 2
Ernesto Costa
Sistemas Periciais: abordagem baseada em Modelos
Observando...
G= 7 [] 3
Conjugando com o passado...
G= 6 [A1,A3] 1
A1 não é responsável!
G= 10 [A1,M2] 2
Candidatos: A3 ; M2 ; A3,M2
Ernesto Costa