Fusão e Tratamento de Ambiguidades em
Conhecimento Descoberto e Adquirido
Paulo Oliveira
FEUP, 17 de Dezembro de 2002
Nota Introdutória
FEUP, 17 de Dezembro de 2002
2
Organização

Enquadramento

Objectivos

Fusão de conhecimento

Arquitectura proposta

Estudo de caso

Conclusões

Trabalho futuro
FEUP, 17 de Dezembro de 2002
3
Enquadramento

Sistemas Periciais (SP)

Características





Detêm e usam conhecimento de peritos
Solucionam problemas de forma idêntica à efectuada pelos
peritos
Vasta divulgação, popularidade e sucesso comercial
Aplicados com sucesso em diversos domínios (produção,
medicina e engenharia)
Limitações

Conhecimento que se encontra na base de conhecimento

Obrigam à realização de operações de manutenção
FEUP, 17 de Dezembro de 2002
4
Enquadramento (II)

Descoberta de Conhecimento em Bases de Dados
(DCBD)

Objectivo


Utilização crescente


Extrair o conhecimento que se encontra implícito nos dados
Disseminação a diversos domínios (seguros, medicina,
telecomunicações, etc.)
Fonte de novo conhecimento

Integrado na Base de Conhecimento (BC) de um SP com o intuito
de superar as limitações mencionadas anteriormente
FEUP, 17 de Dezembro de 2002
5
Objectivos

Conceber uma arquitectura que permita efectuar a fusão do
conhecimento originário de DCBD com o conhecimento que
se encontre na BC de um Sistema Baseado em Regras
(SBR)

Requisito: obter uma nova BC consistente

Implementar um sistema de fusão de conhecimento

Aplicar o sistema desenvolvido a um caso, com o intuito de
demonstrar a sua validade
FEUP, 17 de Dezembro de 2002
6
Fusão de Conhecimento

Objectivo


“Formar uma única perspectiva ou ponto de vista, no fundo,
uma síntese ou um consenso.” [Cholvy e Hunter, 1997]
Caracterização do Problema

Importante



Reúne o conhecimento disperso
Permite a dedução de conhecimento adicional (implícito)
Não trivial

Existência de perspectivas conflituosas (inconsistências)
FEUP, 17 de Dezembro de 2002
7
Fusão de Bases de Conhecimento
Credibilidade
diferente às BC
Forçam a consistência
da BC resultante
Igual credibilidade
às BC
Aproximações
Revisão de
conhecimento
Actualização de
conhecimento
Arbitragem de
BC
Combinação de
BC
Lógicas multi-valor
Suportam a presença
de inconsistências na
BC resultante
Argumentação
Amalgamar BC
FEUP, 17 de Dezembro de 2002
8
Arquitectura do FUNDARE
BC SBR
BC SDCBD
Converter
BC
Dicionário
Editar
BC
Utilizador
(Perito / Eng.º
Conhecimento)
Ferramenta de
Verificação
(VERITAS)
Reunir
BC
Criar BC
Consistente
Conhecimento
eliminado
FEUP, 17 de Dezembro de 2002
9
Converter BC

Garantir a independência
sintáctica da arquitectura



Colocar as regras (SBR e
SDCBD) nas suas
respectivas formas
canónicas
Converter a BC resultante da
fusão na sintaxe utilizada na
BC do SBR
Homogeneizar a
heterogeneidade semântica
FEUP, 17 de Dezembro de 2002
BC SBR
BC SDCBD
Regras SBR (sintaxe x)
Regras (sintaxe x)
Regras SDCBD (sintaxe y)
Converter
BC
Significado
termo
Regras SBR
(forma canónica)
Dicionário
Regras
consistentes
Regras SDCBD
(forma canónica)
Editar
BC
Criar BC
Consistente
10
Editar BC

Permitir realizar operações
de edição sobre as BC

Consultas

Alterações

Eliminações
Utilizador
Converter
BC
Alterações
regras
Regras
Regras SBR
(forma canónica)
Editar
BC
Regras SDCBD
(forma canónica)
Regras SDCBD
alteradas
Regras SBR
alteradas
Reunir
BC
FEUP, 17 de Dezembro de 2002
11
Reunir BC


Agregar todo o conhecimento
existente numa única BC
Colocar o conhecimento no
formato de representação
requerido pela ferramenta de
verificação (VERITAS)
Editar
BC
Regras SBR
alteradas
Regras SDCBD
alteradas
Reunir
BC
Regras
reunidas
Criar BC
Consistente
FEUP, 17 de Dezembro de 2002
Regras
reunidas
VERITAS
12
Ferramenta de Verificação (VERITAS)

Objectivo


Modo de funcionamento


Detectar todas as anomalias que
possam existir na BC reunida,
recorrendo a técnicas de
verificação baseadas em métodos
formais (módulo externo)
Desenvolve todas as cadeias de
inferência (expansões) plausíveis
Anomalias tratadas

Circularidades indirectas

Ambivalências

Inconsistências
FEUP, 17 de Dezembro de 2002
Reunir
BC
Regras
reunidas
VERITAS
Anomalias
detectadas
Expansões
geradas
Criar BC
Consistente
13
Criar BC Consistente

Identificar todas as
soluções que permitem a
obtenção de Subconjuntos
Máximos Consistentes
(SMC) de regras
Solução
eliminação
Utilizador
Soluções
possíveis
eliminação
Factos
possíveis
PreferênciasRestrições
Classificação
anomalias-erros

Auxiliar o utilizador a
seleccionar um SMC
FEUP, 17 de Dezembro de 2002
Anomalias
detectadas
Criar BC
Consistente
Regras
reunidas
Reunir
BC
VERITAS
Expansões
geradas
Regras
Eliminadas
Regras
Consistentes
Converter
BC
R.Eliminadas
14
Criação da BC Consistente (II)
Identificação Expansões Finais
Classificação Anomalias-Erros
Separação Expansões Geradas
Definição Restrições
Geração Soluções Possíveis (Tuplos)
Definição Factos Possíveis
Aplicação Método Ordenação Tuplos
Selecção SMC Regras
FEUP, 17 de Dezembro de 2002
15
Identificação das Expansões Finais

Identificação das expansões
que não são susceptíveis de
qualquer desenvolvimento
adicional
Identificação Expansões Finais
Classificação Anomalias-Erros
Separação Expansões Geradas
Definição Restrições
expFBas( 1, `H1`, [`F1`], [`D-r1-L1`] ).
Geração Soluções Possíveis (Tuplos)
expFBas( 2, `H2`, [`F1`], [`D-r1-L1`,`D-r2-L1`] ).
Definição Factos Possíveis
expFBas( 3, `C1`, [`F1`], [`D-r1-L1`,`D-r2-L1`,`D-r3-L1`] ).
Método Ordenação Tuplos ).
expFBas( 4, `C2`, Aplicação
[`F1`], [`D-r1-L1`,`D-r2-L1`,`P-r8-L1`]
Selecção SMC Regras
FEUP, 17 de Dezembro de 2002
16
Classificação Anomalias - Erros

Anomalia = sintoma de um
possível erro
Identificação Expansões Finais
Classificação Anomalias-Erros

Classificação como erro
depende do utilizador
Separação Expansões Geradas
Definição Restrições
Anomalias
Erros

Na criação da BC
consistente, apenas se
consideram os erros
Geração Soluções Possíveis (Tuplos)
Definição Factos Possíveis
Aplicação Método Ordenação Tuplos
Selecção SMC Regras
FEUP, 17 de Dezembro de 2002
17
Separação das Expansões Geradas

Separar as expansões finais
geradas em:


Expansões afectadas por
erros
Expansões não afectadas por
erros
Identificação Expansões Finais
Classificação
ExpansõesAnomalias-Erros
finais
geradas
Expansões Separação
afectadas Expansões
Expansões
não
Geradas
por erros
afectadas por erros
Definição Restrições
Geração Soluções Possíveis (Tuplos)
Definição Factos Possíveis
Aplicação Método Ordenação Tuplos
Selecção SMC Regras
FEUP, 17 de Dezembro de 2002
18
Geração das Soluções Possíveis (Tuplos)

Determinar todas as combinações
possíveis de eliminação de regras
entre as expansões com erros
Identificação Expansões Finais
Expansões Afectadas por Erros
Classificação Anomalias-Erros
P-r1-L2; P-r4-L1; D-r5-L1
D-r1-L1; P-r8-L1
Separação Expansões Geradas

As restantes regras formam um
SMC



Subconjunto – Não inclui as
regras que constam do tuplo
Máximo – Basta a inclusão de
uma das regras do tuplo para que
a BC volte a ter erros
Consistente – Não é possível
detectar os erros anteriormente
identificados
FEUP, 17 de Dezembro de 2002
Tuplos
Definição Restrições
{P-r1-L2; D-r1-L1}
{P-r1-L2; P-r8-L1}
Geração Soluções Possíveis (Tuplos)
{P-r4-L1; D-r1-L1}
{P-r4-L1;
P-r8-L1}
Definição
Factos
Possíveis
{D-r5-L1; D-r1-L1}
Aplicação {D-r5-L1;
Método Ordenação
P-r8-L1} Tuplos
Selecção SMC Regras
19
Definição de Restrições

Objectivo


Tipos



Condicionar o processo de
geração dos tuplos
Regra não eliminável
Regra de eliminação obrigatória
Inexistência de factores de
certeza


Classificação Anomalias-Erros
Separação Expansões Geradas
Forma de definição

Identificação Expansões Finais
regra a regra
Existência de factores de
certeza


regra a regra
via filtro
FEUP, 17 de Dezembro de 2002
Definição Restrições
Geração Soluções Possíveis (Tuplos)
Definição Factos Possíveis
Aplicação Método Ordenação Tuplos
Selecção SMC Regras
20
Definição de Factos Possíveis

Informação sobre os factos
susceptíveis de serem
fornecidos

Irrelevante na verificação
formal de conhecimento

Informação importante sobre
as expansões não afectadas
por erros
FEUP, 17 de Dezembro de 2002
Identificação Expansões Finais
Classificação Anomalias-Erros
Exemplo:
r1: a  Separação
b
Expansões Geradas
r2: b  c
r3: c  d
Definição Restrições
Expansão gerada pelo VERITAS: r1; r2; r3
Mas,Geração
se b Soluções
for um facto
possível
de ser
Possíveis
(Tuplos)
fornecido, também se pode estabelecer a
seguinte sub-expansão da anterior: r2; r3.
Definição Factos Possíveis
Isto significa que a expansão gerada, no fundo,
representa duas expansões susceptíveis de se
Aplicação Método
Ordenação
Tuplos
estabelecerem
a partir da
BC.
Selecção SMC Regras
21
Métodos de Ordenação dos Tuplos

Hierarquizar os diferentes
tuplos em função da perda de
conhecimento que implicam
Identificação Expansões Finais
Classificação Anomalias-Erros
Separação Expansões Geradas

Auxiliar o utilizador a
seleccionar o tuplo a adoptar
como solução
Definição Restrições
Métodos Ordenação
Geração
Soluções Possíveis (Tuplos)
dos Tuplos
Definição Factos Possíveis
Expansões sem
Erros Afectadas
Alternativas Obtenção
Aplicação Método
Ordenação
Tuplos
Mesmos
Consequentes
Selecção SMC Regras
Inexistência FC
nas Regras
FEUP, 17 de Dezembro de 2002
Existência FC
nas Regras
Inexistência FC
nas Regras
Existência FC
nas Regras
22
Expansões sem Erros Afectadas
(inexistência de FC nas regras)
1.
Para cada tuplo, determinar o
número de expansões sem
erros afectadas
Tuplo: {P-r1-L2; P-r8-L1}
Métodos Ordenação
Tuplos por erros
Expansões não dos
afectadas
P-r1-L1; P-r4-L1; P-r5-L1; P-r7-L1; D-r3-L1
P-r1-L1; P-r4-L1; P-r5-L1; P-r7-L1; P-r8-L1
2.
3.
Ordenar os tuplos por ordem
crescente
Reordenar os tuplos (em
situação de igualdade) por
ordem crescente do n.º de
regras que os compõem
FEUP, 17 de Dezembro de 2002
P-r1-L2;
P-r4-L1;
P-r7-L1; P-r8-L1
Expansões
sem P-r5-L1; Alternativas
Obtenção
Erros Afectadas
D-r1-L1;
D-r2-L1; D-r3-L1 Mesmos Consequentes
D-r1-L2; D-r2-L1; D-r3-L1
D-r1-L2; D-r2-L1; P-r8-L1
P-r2-L1;
P-r7-L2;
Inexist.
FC P-r3-L1;
Exist. P-r6-L1;
FC
Inexist.
FCD-r3-L1
Exist. FC
Regras
Regras
Regras
Regras
P-r2-L1; P-r3-L1; P-r6-L1; P-r7-L2; P-r8-L1
P-r6-L2; P-r7-L2; D-r3-L1
P-r6-L2; P-r7-L2; P-r8-L1
N.º de Expansões Afectadas: 5
23
Expansões sem Erros Afectadas
(existência de FC nas regras)
1.
Para cada tuplo, determinar:


O número de expansões sem
erros afectadas
A certeza média com que se
obtêm conclusões


2.
Utilização do mecanismo de
propagação dos FC
Possibilidade de suavizar a
média à custa do desvio
padrão
Ordenar os tuplos por ordem
crescente das expansões sem
erros afectadas



Métodos Ordenação
dos Tuplos
Expansões sem
Erros Afectadas
Inexist. FC
Regras
Exist. FC
Regras
Alternativas Obtenção
Mesmos Consequentes
Inexist. FC
Regras
Exist. FC
Regras
Peso de importância relativa
de cada critério
Normalização dos valores
Utilização de uma métrica
FEUP, 17 de Dezembro de 2002
24
Alternativas de Obtenção dos Mesmos
Consequentes (inexist. FC nas regras)
1.
2.
3.
Para cada tuplo, determinar
o número de alternativas
que permitem obter os
mesmos consequentes
Ordenar os tuplos por
ordem crescente do número
de regras que não possuem
alternativa
Reordenar os tuplos (em
situação de igualdade), em
função da média do número
de alternativas

4.
Possibilidade de suavizar a
média à custa do desvio
padrão
Reordenar os tuplos (em
situação de igualdade) por
ordem crescente do n.º de
regras que os compõem
FEUP, 17 de Dezembro de 2002
P-r1-L1
ac
P-r7-L1
ce
bc
efp
P-r8-L1
d Métodos
f
Ordenação
jl
dos Tuplos
pr
lmo
km
op
no
Expansões sem
Erros Afectadas
gi
Alternativas Obtenção
pq
Mesmos Consequentes
ip
D-r3-L1
hi
Inexist. FC D-r1-L2
Exist. FC
Inexist. FC
Regras
Regras
Regras
1. Nº de Alternativas dos tuplos:
{P-r7-L1; P-r8-L1}  (4, 0)
{P-r8-L1; D-r3-L1}  (0, 0)
{P-r1-L1; D-r1-L2}  (1, 1)
Exist. FC
Regras
2. Ordenação dos tuplos:
{P-r1-L1; D-r1-L2}  (1, 1)
{P-r7-L1; P-r8-L1}  (4, 0)
{P-r8-L1; D-r3-L1}  (0, 0)
25
Alternativas de Obtenção dos Mesmos
Consequentes (existência FC nas regras)
1.
Para cada tuplo, determinar


O número de alternativas que
permitem obter os mesmos
consequentes
A certeza média com que se obtêm os
mesmos consequentes pelas
alternativas existentes

2.
3.
Utilização do mecanismo de
propagação dos FC
Ordenar os tuplos por ordem
crescente do número de regras que
não possuem alternativa
Reordenar os tuplos (em situação de
igualdade) em função da média do
número de alternativas e da certeza
média com que se obtêm as
conclusões




Métodos Ordenação
dos Tuplos
Expansões sem
Erros Afectadas
Inexist. FC
Regras
Exist. FC
Regras
Alternativas Obtenção
Mesmos Consequentes
Inexist. FC
Regras
Exist. FC
Regras
Peso de importância relativa atribuído
a cada critério
Possibilidade de suavizar a média à
custa do desvio padrão
Normalização dos valores
Utilização de uma métrica
FEUP, 17 de Dezembro de 2002
26
Selecção do SMC de Regras

A selecção do tuplo compete
ao utilizador

Classificação Anomalias-Erros
A eliminação das regras (do
tuplo) resultam num SMC de
regras (BC final consistente)

Identificação Expansões Finais
As regras eliminadas são
Separação Expansões Geradas
Definição Restrições
Geração Soluções Possíveis (Tuplos)
colocadas num repositório de
conhecimento eliminado

A BC final reúne condições
para se tornar na nova BC do
Definição Factos Possíveis
Aplicação Método Ordenação Tuplos
Selecção SMC Regras
SBR
FEUP, 17 de Dezembro de 2002
27
Estudo de Caso

Domínio: mediação de seguros


Área: contratos / apólices
Bases de conhecimento

Adquirido



Descoberto



Recolhida a partir de um perito da área
Composta por 21 regras
Utilização do SDCBD Clementine e do algoritmo de indução de regras
C5.0
Composta por 14 regras
Objectivo

Obter um BC consistente resultante da fusão do conhecimento
descoberto com o conhecimento adquirido
FEUP, 17 de Dezembro de 2002
28
Estudo de Caso (II)

Erros detectados



Método aplicado


Expansões sem erros afectadas (n.º e certeza média)
Diferentes cenários



Ambivalência ao longo de múltiplas cadeias de inferência
Inconsistência ao longo de múltiplas cadeias de inferência
Atribuídos pesos de importância relativa diferentes
Introduzidas restrições à geração de tuplos
Conclusões obtidas




Tuplos seriados em função da perda de conhecimento que implicam
A ordenação auxiliou na selecção do tuplo a adoptar
A eliminação das regras do tuplo resultou numa BC consistente
A nova BC permite a obtenção de novas conclusões quando
comparada com a BC adquirido inicial
FEUP, 17 de Dezembro de 2002
29
Conclusões

Análise, concepção e desenvolvimento de uma arquitectura
para a fusão de conhecimento

Baseada em aspectos sintácticos

Preocupação com outro tipo de erros, para além das inconsistências

Implementação do sistema de fusão de conhecimento

Aplicação a um caso na área da mediação de seguros,
confirmou a validade da arquitectura
FEUP, 17 de Dezembro de 2002
30
Trabalho Futuro

Incorporar conhecimento semântico (meta-conhecimento)
nos métodos de ordenação dos tuplos

Manipular erros do tipo redundância

Considerar, de alguma forma, no processo de fusão, o
conhecimento anteriormente eliminado

Aplicar o FUNDARE a novos casos de fusão de
conhecimento

Construir uma operatória que efectue uma análise
comparativa aos resultados obtidos em cada um dos
métodos
FEUP, 17 de Dezembro de 2002
31
Fusão e Tratamento de Ambiguidades em
Conhecimento Descoberto e Adquirido
Paulo Oliveira
FEUP, 17 de Dezembro de 2002