Inteligência Artificialhome.iscte-iul.pt/~luis/aulas/ia/Sistemas baseados em regras.pdf · Existem dois tipos de ... O raciocínio usado com este método de representação de conhecimento

1

Inteligência Artificial

Apontamentos para as aulas

Luís Miguel Botelho

Departamento de Ciências e Tecnologias da Informação

Instituto Superior de Ciências do Trabalho e da Empresa

Julho de 2015

2

Sistemas Baseados em Regras

Índice

1 REGRAS CONDIÇÃO-CONCLUSÃO 4

1.1 RACIOCÍNIO DEDUTIVO ENCADEADO PARA A FRENTE 5

Novos factos 5

Raciocínio 5

1.2 RACIOCÍNIO DEDUTIVO ENCADEADO PARA TRÁS 5

2 REGRAS CONDIÇÃO-AÇÃO (REGRAS DE PRODUÇÃO) 7

1.3 RESOLUÇÃO DE CONFLITOS 8

3 GERAÇÃO AUTOMÁTICA DE EXPLICAÇÕES 10

1.4 SISTEMA PARA AVALIAÇÃO DE PEDIDOS DE FINANCIAMENTO 10

1.5 GERAÇÃO AUTOMÁTICA DE EXPLICAÇÕES 12

Explicações “Why” 12

Explicações “How” 13

4 VALIDAÇÃO DA BASE DE CONHECIMENTOS 15

4.1 VERIFICAÇÃO DE CONSISTÊNCIA 15

4.2 BASE DE CONHECIMENTOS NÃO COMPLETA 16

5 IMPLEMENTAÇÃO EM PROLOG DE MECANISMOS DE REPRESENTAÇÃO E

RACIOCÍNIO 20

5.1 META-INTERPRETADORES (PROLOG EM PROLOG) 20

5.2 EXPLICAÇÕES “WHY” 22

5.3 EXPLICAÇÕES “HOW” 24

5.4 VALIDAÇÃO DA BASE DE CONHECIMENTOS 26

5.4.1 Incompletude da Base de Conhecimentos 26

5.4.2 Inconsistência da Base de Conhecimentos 27

5.5 IMPLEMENTAÇÃO DE UM SISTEMA DE REGRAS DE PRODUÇÃO 28

6 REFERÊNCIAS 31

3

Sistemas Baseados em Regras

As regras SEENTÃO são as estruturas mais usadas para representar conhecimento em sistemas

baseados em conhecimento, sobretudo em sistemas periciais (“expert systems”). Existem dois tipos de

regras: as regras condição-conclusão e as regras condição-ação (mais vulgarmente chamadas regras de

produção). Em ambos os casos, as regras podem ser descritas através de estruturas com o formato IF LHS

THEN RHS, em que LHS significa o lado esquerdo da regra (“left hand side”) e RHS significa o lado

direito da regra (“right hand side”).

O raciocínio usado com este método de representação de conhecimento pode ser encadeado para trás

(no caso das regras condição-conclusão) ou encadeado para a frente (tanto nas regras condição-conclusão

como nas regras condição-ação).

4

1 Regras condição-conclusão

As regras condição-conclusão são regras que especificam a conclusão que pode ser gerada quando uma

determinada condição é verdadeira. Dito de outra forma, uma regra condição-conclusão diz que a

conclusão é verdade quando a condição é verdade.

Em geral, uma regra condição-conclusão representa-se através de uma estrutura de representação com

o formato IF condição THEN conclusão. Também é relativamente vulgar deparar-se com a notação

condiçãoconclusão. Esta última notação realça a semelhança que existe entre a representação baseada

em regras e a representação baseada em lógica.

Na maioria dos sistemas de representação baseados em regras, a condição pode ser uma condição

atómica ou uma condição composta através das conectivas lógicas not, and e or, enquanto que a

conclusão é, em geral, uma proposição atómica.

Para exemplificar a utilização de regras condição-conclusão, considere-se o caso em que uma pessoa

ou uma empresa pretendem escolher o sistema operativo a instalar nos seus computadores. Para isso,

poderão recorrer a um conjunto de regras simples como as apresentadas na Figura 1.

Regra 1

SE

o ambiente de utilização é um ambiente empresarial; e

é necessário usar software aplicativo da Microsoft

ENTÃO

o sistema operativo selecionado é o Windows NT

Regra 2

SE

o ambiente de utilização é um ambiente particular; e


ENTÃO

o sistema operativo selecionado é o Windows98

Regra 3

SE

o sistema operativo selecionado é o Windows NT; e

é necessário disponibilizar serviços a vários clientes

ENTÃO

a versão do sistema operativo é Windows NT Server

Regra 4

SE

é necessário usar Excel

ENTÃO


Regra 5

SE

é necessário usar Access

ENTÃO


Figura 1 - Regras condição-conclusão para escolha de um sistema operativo

As regras exibidas na Figura 1 poderão integrar a base de conhecimentos de um sistema pericial. Para

utilizar as regras para responder a perguntas ou para reagir à introdução de nova informação, o sistema

tem que efetuar raciocínio.

Em geral, o tipo de raciocínio mais usado com este método de representação é o raciocínio dedutivo,

isto é, o raciocínio em que se usam as regras de inferência da dedução (e.g., o modus ponens, o modus

tolens, a introdução e eliminação da conjunção e da disjunção, ver capítulo Error! Reference source not

5

found.). No entanto, também seria possível usar regras condição-conclusão através de outros tipos de

raciocínio, entre os quais a abdução (ver capítulo Error! Reference source not found.) e uma forma

muito particular de raciocínio não monótono conhecida pela hipótese do mundo fechado (CWA, “Closed

world assumption”, capítulo Error! Reference source not found.).

Qualquer destes tipos de raciocínio pode ser encadeado para trás ou encadeado para a frente. Em

certas ferramentas computacionais usadas para representar conhecimento através de regras utiliza-se um

encadeamento misto.

1.1 Raciocínio dedutivo encadeado para a frente

As regras condição-conclusão da Figura 1 podem ser usadas por um mecanismo de inferência com

encadeamento para a frente (“forward reasoning”, ou “forward chaining”) também conhecido por

encadeamento guiado pelos dados (“data-driven”). Neste modo de utilização, o raciocínio é desencadeado

por dados geralmente introduzidos pelo utilizador (ou por outro programa) ou por resultados produzidos

pelo próprio sistema. O sistema determina as regras com as condições satisfeitas e produz as conclusões

especificadas. As conclusões produzidas juntamente com os factos previamente existentes são, de novo,

comparadas com as condições das regras e o processo é repetido. A figura mostra uma interação do

sistema em que a introdução de nova informação despoleta um raciocínio.

Novos factos Raciocínio

Utilizador: é necessário disponibilizar serviços a vários clientes

Utilizador: é necessário usar o Access

Sistema: é necessário usar software aplicativo da Microsoft Regra 5

Utilizador: o ambiente de utilização é um ambiente empresarial

Sistema: o sistema operativo selecionado é o Windows NT Regra 1

Sistema: a versão do sistema operativo é Windows NT Server Regra 3

Figura 2 - Interação guiada pelos dados

(Raciocínio encadeado para a frente)

Na interação, assume-se que todos os novos factos são memorizados pelo sistema na sua memória de

trabalho. No primeiro passo da interação, o utilizador informa o sistema que é necessário disponibilizar

serviços a vários clientes. Este novo facto memorizado pelo sistema é usado para verificar se há regras

com a condição satisfeita. Nesta altura, nenhuma regra fica com as condições totalmente satisfeitas.

Apenas uma parte da condição da regra 3 fica satisfeita, mas não toda a condição. No segundo passo da

interação, o utilizador informa o sistema que é necessário usar o MS-Access. Este facto é memorizado e o

sistema determina se a condição de alguma das suas regras fica satisfeita. A condição da regra 5 fica

completamente satisfeita dando origem à geração da conclusão especificada, i.e., o sistema produz o novo

facto “é necessário usar software aplicativo da Microsoft” que é memorizado. Dado que existe um novo

facto, o sistema volta a verificar a satisfação das condições das regras. Tanto a regra 1 como a regra 5 têm

a condição satisfeita. Desta vez, a regra 5 não é usada porque nenhuma regra pode ser usada duas vezes

com a mesma informação. Aplicando a regra 1, o sistema produz o novo facto “o sistema operativo

selecionado é o Windows NT”. Dado que existe um novo facto, as regras são de novo verificadas. As

regras 1 e 5 têm a condição satisfeita mas não são usadas porque as regras não podem ser usadas mais do

que uma vez com a mesma informação. Mas a condição da regra 3 fica agora totalmente satisfeita, pelo

que a conclusão especificada é produzida, gerando o novo facto “a versão do sistema operativo é

Windows NT Server” que é igualmente memorizado. Agora nenhuma regra está em condições de poder

ser aplicada.

1.2 Raciocínio dedutivo encadeado para trás

As regras da Figura 1 podem ser usadas de forma diferente da usada na interação descrita na secção 1.1.

Em vez de introduzir informação de forma voluntária, o utilizador poderá fazer perguntas ao sistema. Para

responder, o sistema percorre toda a sua base de conhecimentos procurando um facto ou uma regra cujo

lado direito (i.e., conclusão) emparelhe com a pergunta do utilizador. Quando uma regra adequada é

6

encontrada, o sistema verifica se a condição é verdadeira. Para isso, volta a procurar regras (ou factos) e o

processo repete-se.

Supondo que o utilizador pergunta se P é verdade, o sistema vai procurar o facto P na sua base de

conhecimentos ou uma regra com o formato SE condição ENTÃO P. Tendo encontrado esta regra, o

sistema só pode responder afirmativamente se a condição for verdadeira. Supondo que a condição tem a

forma AB, o sistema tem que verificar se A é verdade e se B também é verdade. Para isso procura os

factos A e B na sua base de conhecimentos ou regras que permitam concluir A e B. Para isso, o processo

repete-se. A este método de encadeamento das regras chama-se encadeamento para trás (“backward

chaining”, “backward reasoning”) ou raciocínio guiado pelos objetivos (“goal-driven”) porque é aquilo

que se pretende provar que guia a seleção de regras na base de conhecimentos.

Vejamos agora o que acontece quando o utilizador pretende saber que sistema operativo deve instalar.

A Figura 3 (b) representa uma interação entre o utilizador e um sistema com raciocínio encadeado para

trás. Assume-se que a base de conhecimentos do sistema é constituída pelas regras apresentadas na Figura

1 e pelos factos representados na Figura 3 (a).

(a) Factos

É necessário usar o Access

O ambiente de utilização é um ambiente empresarial

(b) Interação

Utilizador: Qual é o sistema operativo selecionado?

Sistema: O sistema operativo selecionado é o Windows NT

Figura 3 - Interação guiada pelos objetivos

Na interação da Figura 3, o utilizador pergunta qual é o Sistema Operativo selecionado (sugerido) pelo

sistema. Para responder a esta pergunta, o sistema percorre a sua base de conhecimentos procurando um

facto ou uma regra que permitem responder afirmativamente à pergunta do utilizador. Se não encontrar,

falha. Neste caso, encontra a Regra 1 cuja conclusão é “o sistema operativo selecionado é o Windows

NT”. Para poder responder afirmativamente ao utilizador, o sistema tem que verificar se a condição da

regra está satisfeita. Neste caso, tem que verificar se “o ambiente de utilização é um ambiente

empresarial” e se “é necessário usar software aplicativo da Microsoft”. Começando pela primeira parte da

condição, o sistema tenta encontrar o facto “o ambiente de utilização é um ambiente empresarial” ou uma

regra com esta conclusão. O facto 2 permite-lhe satisfazer esta parte da condição. Agora tem que verificar

se é necessário usar software da Microsoft. A conclusão da Regra 4 diz que é necessário usar software

Microsoft. Para que o sistema possa usar esta regra, tem que verificar se a sua condição está satisfeita, isto

é, tem que verificar se “é necessário usar Excel”. Dado que não existe qualquer regra nem facto que

permitam satisfazer esta condição, a Regra 5 é abandonada. No entanto, a Regra 6 também permite

concluir que é necessário usar software aplicativo da Microsoft. Para isso é necessário verificar se “é

necessário usar Access”. O facto 1 satisfaz esta parte da condição. Assim, a condição da Regra 1 (“o

ambiente de utilização é um ambiente empresarial; e é necessário usar software aplicativo da

Microsoft”) é satisfeita. Emparelhando a conclusão da regra (“o sistema operativo selecionado é o

Windows NT”) com a pergunta (“o sistema operativo selecionado é Qual?”, obtém-se a instanciação da

variável Qual com a expressão “Windows NT”. É o valor desta variável que é exibido ao utilizador.

7

2 Regras condição-ação (regras de produção)

As regras usadas nos exemplos anteriores são regras condição-conclusão. Nesta secção apresenta-se um

exemplo com regras de produção, isto é, com regras que especificam a execução de ações quando a sua

condição se encontra satisfeita. As regras de produção são encadeadas para a frente.

No exemplo usado para apresentar este assunto, temos um mundo quadriculado com um vilão e um

herói, como se mostra na

Figura 4.

Figura 4 - O mundo do vilão

O vilão ocupa uma quadrícula fixa no mundo (1,2), e o herói vai movimentar-se de acordo com a

aplicação de um conjunto de regras de produção apresentadas na Figura 5. O objetivo é controlar o herói

desde a sua posição atual (3,3) até à mesma posição do vilão. Quando o herói tiver atingido o vilão,

deverá liquidá-lo. As regras são escritas do ponto de vista do herói.

Regra 1 SE a posição atual for a mesma que a posição do vilão

ENTÃO Liquidar o vilão

Regra 2 SE o número da coluna da posição atual for superior ao número da coluna da posição do

vilão

ENTÃO Dar um passo para a esquerda

Regra 3 SE o número da coluna da posição atual for inferior ao número da coluna da posição do

vilão

ENTÃO Dar um passo para a direita

Regra 4 SE o número da linha da posição atual for inferior ao número da linha da posição do vilão

ENTÃO Dar um passo para baixo

Regra 5 SE o número da linha da posição atual for superior ao número da linha da posição do vilão

ENTÃO Dar um passo para cima

Figura 5 - Regras de produção

As ações possíveis no mundo do vilão são “liquidar o vilão” e “dar um passo” para baixo, para cima, para

a direita e para a esquerda. Além das regras, um sistema baseado em regras de produção tem que ter um

mecanismo de aplicação das regras e a programação das ações.

8

Figura 6 - Sequências de ações do herói

Na Figura 6 mostra-se a sequência de ações efetuadas pelo herói, de acordo com as regras de produção

representadas na Figura 5. No início, as posições do vilão (1,2) e do herói (3,3) são introduzidas. O

sistema determina as regras com a condição satisfeita. Tanto a regra 2 como a regra 5 têm a condição

satisfeita. Em princípio qualquer delas poderia ser usada. O sistema escolhe a regra 2 (não há razão

especial para preferir a regra 2 em relação à regra 5). De acordo com a regra 2, o herói dá um passo para a

esquerda, alterando a representação interna do estado atual (a posição do herói passa a ser (3,2). A

segunda configuração exibida na Figura 6 representa o resultado desta ação.

Devido à alteração na posição do herói, o sistema volta a verificar se alguma regra tem a condição

satisfeita. Apenas a regra 5 tem a condição satisfeita pelo que o herói dá um passo para cima ficando na

posição (2,2).

Devido à nova alteração da posição do herói, o sistema volta a verificar as suas regras. De novo, a

regra 5 é a única com a condição satisfeita. Ela é usada porque a satisfação da sua condição foi obtida à

custa de novos dados. No passo anterior, as posições do vilão e do herói eram (1,2) e (3,2)

respetivamente. Na situação atual, as suas posições são (1,2) e (2,2). A regra 5 especifica que o herói dá

um passo para cima. Como resultado desta ação, o herói e o vilão ficam ambos na posição (1,2) (quarto

quadro da Figura 6).

A alteração da posição do herói conduz o sistema a verificar as condições das suas regras. Desta vez, a

regra 1 é a única cuja condição está satisfeita. De acordo com a regra 1, o herói mata o vilão.

1.3 Resolução de conflitos

Quando é usado raciocínio encadeado para a frente, pode acontecer que as condições de mais que uma

regra fiquem satisfeitas. Nesta eventualidade o sistema tem que escolher a que vai usar porque não poderá

usar mais do que uma. De facto, ao executar a ação da primeira regra com a condição satisfeita, o estado

do mundo altera-se e, consequentemente, é possível que as regras que tinham a condição satisfeita deixem

de a ter.

Ao conjunto de regras com a condição satisfeita chama-se conjunto de conflito (“conflict set”). Aos

critérios usados pelo sistema para selecionar apenas uma regra do conjunto de conflito chama-se política

ou estratégia de resolução de conflitos (“conflict resolution strategy”). Os vários sistemas usam diferentes

políticas de resolução de conflitos constituídas por vários critérios, entre os quais os seguintes:

1 Nenhuma regra pode ser usada duas vezes com os mesmos dados

2 Escolhe-se a regra que depende dos dados mais recentes

3 Escolhe-se a regra mais específica (i.e., a regra cuja condição é constituída pelo maior número de

subcondições)

9

4 Escolhe-se a regra mais importante (neste caso, as regras têm que ser associadas a um fator de

importância ou prioridade).

5 Escolhe-se a regra cuja ação seja a mais importante

O primeiro critério é bastante útil porque evita que a mesma regra possa continuar a ser usada devido aos

mesmos factos. Ainda assim, há muitos sistemas que não implementam esse critério, nas suas políticas de

resolução de conflitos. Nesse caso cabe ao programador criar mecanismos que invalidem a utilização

repetida da regra.

A escolha da regra que depende de factos mais recentes (critério 2) é muito útil em sistemas que

devem reagir rapidamente às alterações do mundo em que existem. De facto, se o sistema continuar a

reagir a informação mais antiga, negligenciando alterações recentes, pode acontecer que o seu

comportamento se torne desatualizado. No entanto, haverá aplicações em que seria preferível reagir a

alterações mais antigas.

De acordo com o critério 3, quando duas ou mais regras têm a condição satisfeita, escolhe-se a

regra mais específica. De facto, se o programador criou regras mais específicas do que outras é porque

tinha em menta a sua utilização, sempre que as circunstâncias o permitissem.

Os critérios 4 e 5 permitiriam ao programador atribuir graus de importância (ou de prioridade) às

regras ou mesmo às ações. Desta forma, se duas regras tiverem a condição satisfeita, seria natural que o

sistema escolhesse aquela com maior importância ou aquela cujas ações fossem mais importantes.

Infelizmente, este critério tem sido muito criticado porque as importâncias de regras e de ações pode

variar, de acordo com as circunstâncias.

10

3 Geração automática de explicações

Este capítulo centra-se na descrição de funcionalidades desejáveis dos sistemas baseados em

conhecimento e das ferramentas computacionais usadas para o seu desenvolvimento. Entre as

funcionalidades dos sistemas baseados em conhecimento, analisa-se a capacidade de geração automática

de explicações para o utilizador. Esta funcionalidade pode ser criada graças à arquitetura dos sistemas

baseados em conhecimento. Para facilitar a sua compreensão, recorre-se a um exemplo de aplicação de

sistemas baseados em conhecimento. Trata-se de um sistema para avaliar o mérito de pedidos de

financiamento para subsidiar atividades de investigação e desenvolvimento (I&D) num centro de

investigação.

A primeira secção deste capítulo descreve os aspetos mais relevantes do sistema, a segunda secção

descreve a geração automática de explicações.

1.4 Sistema para avaliação de pedidos de financiamento

A UIDIA (Unidade de Investigação e Desenvolvimento em Inteligência Artificial)1 é uma organização

que faz a gestão de fundos para o financiamento de atividades de investigação e desenvolvimento em

áreas da inteligência artificial, nomeadamente em Sistemas Baseados em Conhecimento, e em Sistemas

de Agentes, entre outros.

A UIDIA financia diversos tipos de despesas, tais como a aquisição de livros, a aquisição de

equipamentos, e a deslocação a reuniões de organizações de I&D e a conferências científicas. De todas

estas despesas, as mais significativas são as deslocações a reuniões e a conferências.

Esta secção analisa muito sumariamente um sistema baseado em conhecimento para avaliar o mérito

das propostas de financiamento para suportar a deslocação a conferências dos membros da UIDIA.

Os critérios de que depende a avaliação do mérito de uma proposta de financiamento são o seu mérito

quanto à apresentação de trabalhos na dita conferência, o seu mérito quanto à participação na organização

da conferência e a importância da conferência para a UIDIA.

O mérito quanto à apresentação de trabalhos depende não linearmente do número de trabalhos. O

mérito da proposta será tende a aumentar com o número de trabalhos a apresentar, mas o aumento não é

linear.

O mérito relativo à participação na organização da conferência depende não linearmente da

quantidade de papéis desempenhados pelo delegado nas comissões e cargos da conferência: comissão de

programa ("program committee"), comissão de organização local ("local-arrangements committee"),

presidente da conferência ("conference chairman"), ou presidente de sessão ("session chairman"). O mais

importante é a participação em uma destas comissões ou o desempenho de um desses cargos. Se o

delegado desempenhar mais do que um papel, o mérito do pedido será maior mas o aumento não é linear.

A importância da conferência para a UIDIA depende da relação entre os temas da conferência e as

atividades científicas da UIDIA, e da importância da conferência em termos da sua projeção internacional

e do seu reconhecimento pelas entidades que atribuem o financiamento geral à UIDIA.

A concessão de financiamento depende de muitos outros fatores além do mérito da proposta. O mais

importante desses fatores é a disponibilidade orçamental na altura em que o pedido é feito. Outro fator

importante é a capacidade de previsão dos proponentes. Se uma deslocação for prevista com antecedência

(i.e., no início do ano), a proposta tem mais possibilidades de ser contemplada do que se não for prevista.

Seguidamente, apresentam-se regras que ilustram o conhecimento usado no sistema.

1 A unidade de investigação UIDIA não tem existência real; foi inventada para estes apontamentos. No

entanto, o problema descrito é um problema real das unidades de investigação.

11

Regra 1

Se o mérito da proposta em termos da participação na organização

da conferência tem o valor MéritoParticipação, e

o mérito da proposta em termos da apresentação de trabalhos tem

o valor MéritoApresentação, e

a importância da conferência para a UIDIA tem o valor

Importância

Então o mérito global da proposta tem o valor

Mérito 0.4MéritoApresentação

0.4MéritoParticipação

0.2Importância

Regra 2

Se o número de artigos apresentados é maior ou igual a 2

Então o mérito da proposta em termos da apresentação de trabalhos tem

o valor MéritoApresentação5

Regra 3

Se o número de artigos apresentados é 1



Regra 4




Regra 5

Se a importância da conferência para a área científica da UIDIA

tem valor ImportânciaAreaCientifica, e

a importância da conferência para o reconhecimento da UIDIA tem

valor ImportânciaReconhecimento

Então a importância da conferência para a UIDIA é

Importância 0.4 ImportânciaAreaCientifica

0.6 ImportânciaReconhecimento

Regra 6

Se o delegado à conferência pertence ao Program Committee, e

o delegado à conferência NÃO pertence ao Local-Arrangements

Committee

Então o mérito devido à participação na organização da conferência é

MéritoParticipação4

Regra 7

Se o delegado à conferência pertence ao Local-Arrangements

Committee, e

o delegado à conferência NÃO pertence ao Program Committee



Regra 8

Se o delegado à conferência pertence ao Program Committee e ao

Local-Arrangements Committee



Figura 7 – Exemplos de regras do sistema de avaliação de mérito

A Figura 7 não contém todo o conhecimento do sistema; apenas um número significativo de regras. O

sistema de avaliação do mérito de propostas de financiamento de deslocações a conferências pode conter

outras regras e também factos.

12

As regras da Figura 7 serão usadas seguidamente para ilustrar o conceito de geração de explicações e

o funcionamento dos mecanismos que as geram.

1.5 Geração automática de explicações

Uma das vantagens da utilização de representações explícitas é a possibilidade de usar o próprio

conhecimento do sistema para gerar explicações acerca do seu raciocínio. Esta característica dos Sistemas

Baseados em Conhecimento (os quais têm forçosamente representações explícitas) tem as seguintes

vantagens:

Facilita a tarefa de depurar, atualizar e gerir o conhecimento do sistema.

Contribui para que o utilizador perceba e reforce a sua confiança nas sugestões do sistema.

Existem essencialmente dois tipos de explicações que um SBC pode gerar: explicações “why” e

explicações “how”. Quando o sistema faz uma pergunta ao utilizador para poder prosseguir o seu

raciocínio, o utilizador pode querer saber por que razão o sistema fez a pergunta. A explicação

apresentada neste tipo de situação é uma explicação “why” (i.e., “Porque razão perguntas isso?”). Quando

o sistema apresenta uma conclusão, uma sugestão ou qualquer outro tipo de resultado, o utilizador poderá

querer saber como é que o sistema chegou ao resultado apresentado. As explicações apresentadas pelo

sistema, em situações deste tipo, são explicações “how” (i.e., “Como chegaste a esse resultado?”).

Pelo facto de ser possível usar o conhecimento armazenado na base de conhecimento para produzir

quer as soluções para os problemas apresentados ao sistema, quer para gerar explicações

automaticamente, a geração de explicações é desempenhada pelo próprio mecanismo de inferência, sem

ter de ser programado pelo programador do sistema. O programador tem apenas de preencher o

conhecimento na base de conhecimento do sistema. Tanto a resolução de problemas como a geração de

explicações estão a cargo do seu mecanismo de inferência, o qual é oferecido pela ferramenta usada para

a criação do sistema baseado em conhecimento.

Explicações “Why”

Um sistema gera uma explicação “why” quando, após ter pedido ao utilizador para este lhe fornecer uma

dada informação, o utilizador lhe pergunta “Porque queres saber isso?” (“Why do you ask?”). A

explicação “why” consiste em mostrar a regra que se pretende usar e salientar que a utilização dessa regra

depende da informação pedida e permite produzir uma determinada conclusão (intermédia ou final).

Considerando o exemplo do sistema baseado em conhecimento para auxiliar na tomada de decisões de

financiamento de deslocações a conferências (secção 1.4), as explicações “why” podem ser

compreendidas através da interação representada na Figura 8.

Sistema: O delegado à conferência pertence ao Program Committee (sim / não / why)?

Utilizador: why // Porque queres saber isso?

Sistema: Porque se o delegado à conferência pertencer ao program committee e não pertencer

ao local arrangements committe, o mérito devido à participação na organização da

conferência é MeritoParticipação = 4, e eu preciso saber qual é o valor de

MeritoParticipação.

O delegado à conferência pertence ao Program Committee (sim /não / why)?

Utilizador: não.

Figura 8 - Explicações “why” numa interação

Na Figura 8, a explicação do sistema consiste em apresentar a regra usada no seu raciocínio. Neste caso, o

texto da explicação obtém-se da regra 6: “se o delegado à conferência pertencer ao program committee e

não pertencer ao local arrangements committe, o mérito devido à participação na organização da

conferência é MeritoParticipação = 4”. Esta é exatamente uma das regras da BC do sistema, a regra que

despoleta a pergunta do sistema. Se, na interação, em vez de ter respondido à segunda vez que o sistema

apresenta a pergunta (mostrando a sua satisfação com a explicação), o utilizador voltasse a pedir

explicações, o sistema daria uma explicação baseada na regra que utiliza a conclusão da regra 6 (usada na

explicação anterior). A regra 6 produz a variável MeritoParticipação. A regra 1 utiliza o valor dessa

variável para determinar o mérito global da proposta de financiamento. Seria produzida uma explicação

com base na regra 1:

13

“Porque se o mérito da proposta em termos da participação na organização da conferência tem o

valor MéritoParticipação, o mérito da proposta em termos da apresentação de trabalhos tem o valor

MéritoApresentação, e a importância da conferência para a UIDIA tem o valor Importância, então o

mérito global da proposta tem o valor

Mérito 0.4 MéritoApresentação 0.4 MéritoParticipação 0.2 Importância,

e eu preciso saber qual é o valor de Mérito.”

Se, depois desta explicação, o utilizador voltasse a exigir mais explicações, o sistema procuraria a regra

que iria utilizar o resultado da regra 1, a qual fi usada na última explicação. Como não existe nenhuma

regra que use o valor do mérito global (Mérito), o sistema não teria mais explicações a dar.

A próxima secção ocupa-se da geração de explicações do tipo “How”.

Explicações “How”

Um sistema gera uma explicação “how” quando o utilizador pretende que o sistema explique como é que

chegou a um determinado resultado. Recorrendo ao exemplo da avaliação de propostas de deslocação a

conferências, podemos admitir que o utilizador não percebe por que razão o sistema produziu uma dada

avaliação para uma determinada proposta. Neste caso, o sistema pode apresentar as regras que usou para

produzir essa avaliação. A interação da Figura 9 mostra este tipo de explicações.

Sistema: A proposta A tem mérito 2 (numa escala de 0 a 5).

Utilizador: How? (Como foi produzida essa avaliação?)

Sistema: Se o mérito da proposta em termos da participação do seu delegado na organização da

conferência tem o valor MéritoParticipação, o mérito da proposta em termos da

apresentação de trabalhos tem o valor MéritoApresentação, e e a importância da

conferência para a UIDIA tem o valor Importância, então o mérito global da proposta

tem o valor dado pela fórmula

Mérito0.4MéritoApresentação0.4MéritoParticipação0.2Importância.

O mérito da proposta em termos da participação do seu delegado na organização tem o

valor MéritoParticipação0.

O mérito da proposta em termos da apresentação de trabalhos tem o valor

MéritoApresentação3.

A importância da conferência para a UIDIA tem o valor Importância4.

Portanto o mérito global da proposta é Mérito0.430.400.242

Utilizador: Como se conclui que o mérito da conferência em termos da apresentação de trabalhos

tem o valor 3?

Sistema: Se o número de artigos apresentados é 1 então o mérito da proposta em termos da

apresentação de trabalhos tem o valor MéritoApresentação3.

O número de artigos a apresentar é igual a 1

Portanto, o mérito da proposta em termos da apresentação de trabalhos é

MéritoApresentação3.

Figura 9 - Interação com explicações “how”

Para que o sistema produza uma explicação “how”, o utilizador tem que perguntar como é que ele chegou

a determinado resultado. Em reposta, o sistema mostra a regra e os factos que lhe permitiram chegar ao

resultado.

Na geração automática de explicações que serviu de base à interação da Figura 9, o sistema mostra a

regra usada para produzir o resultado final, neste caso, a regra 1. Essa regra depende de resultados que

podem ser conhecidos do sistema (i.e., são factos na base de conhecimento) ou que podem ser gerados

pela utilização de outras regras. A explicação produzida na Figura 9 apresenta apenas os resultados

usados pela regra que usou para gerar a explicação, sem explicar se eles eram conhecidos pelo sistema ou

se foram produzidos por outras regras. Neste caso, o sistema apresenta os seguintes resultados:

14

O mérito da proposta em termos da participação do seu delegado na organização tem o valor

MéritoParticipação0.

O mérito da proposta em termos da apresentação de trabalhos tem o valor MéritoApresentação3.

A importância da conferência para a UIDIA tem o valor Importância4.

No entanto, quando o utilizador pretende obter mais explicações sobre um destes resultados intermédios,

o sistema de geração automática de explicações apresenta a forma como ele foi produzido. No caso desta

interação, o utilizador pretende obter explicações adicionais sobre o mérito da proposta em termos da

apresentação de trabalhos (MéritoApresentação). Mais uma vez, o sistema apresenta uma explicação que

consiste em mostrar a regra usada para produzir MéritoApresentação (regra 3) e os resultados intermédios

de que essa regra depende (neste caso, o número de artigos apresentados):

Se o número de artigos apresentados é 1 então o mérito da proposta em termos da apresentação de

trabalhos tem o valor MéritoApresentação3.

O número de artigos a apresentar é igual a 1.

Tal como acontece com a geração automática de explicações do tipo “Why”, a geração automática de

explicações do tipo “How” também recorre ao conhecimento explicitamente representado na base de

conhecimentos para gerar a explicação. Se esse conhecimento não estivesse explicitamente representado,

não poderiam ser geradas explicações automáticas sem que o programador do sistema, para cada

aplicação específica, tivesse de programar as próprias explicações. Pelo contrário, num sistema com

conhecimento representado explicitamente, as explicações podem ser automaticamente geradas pelo

mecanismo de inferência do sistema, sem que o programador tenha de a programar.

A próxima secção trata da validação automática da base de conhecimentos, a qual é também uma

possibilidade que se deve à representação explícita de conhecimento.

15

4 Validação da base de conhecimentos

Uma ferramenta computacional para desenvolvimento de sistemas baseados em conhecimento pode

permitir a validação automática da base de conhecimentos em termos da sua consistência e completude.

Em termos de consistência pode verificar-se se os conhecimentos que a compõem são contraditórios.

A verificação de inconsistência consiste em determinar se é possível derivar uma proposição (P) e a

sua negação (P) a partir da base de conhecimentos do sistema.

Em termos de completude, podem fazer-se duas coisas: verificar se os factos existentes na base de

conhecimento e se as conclusões geradas pelas regras são usados (noutras regras), e verificar se existe a

informação necessária à avaliação das condições das regras.

Estas validações podem ser feitas por mecanismos existentes no motor de inferência, sem qualquer

intervenção do programador do sistema baseado em conhecimento. Como o conhecimento é representado

explicitamente, os mecanismos de validação da base de conhecimentos limitam-se a percorrer toda a base

de conhecimentos e detetar as deficiências para que tiverem sido concebidos. Se não fossem usadas

representações explícitas, seria impossível (ou muito difícil) criar mecanismos capazes de examinar o

conhecimento do sistema e detetar deficiências.

Os exemplos que ilustram os mecanismos de validação da base de conhecimentos foram inspirados

num sistema pericial, descrito na secção Error! Reference source not found., concebido para auxiliar

decisões de atribuição de financiamento a deslocações a conferências científicas, numa unidade de

investigação imaginada, designada UIDIA (Unidade de Investigação e Desenvolvimento em Inteligência

Artificial)2.

4.1 Verificação de consistência

Para explicar em que consiste a deteção de contradições / inconsistências, considerem-se as três regras e

os dois factos apresentados na Figura 10. As duas primeiras regras são versões deficientes das regras 6 e 7

da Figura 7.

2 A unidade de investigação UIDIA não tem existência real; foi inventada para estes apontamentos. No

entanto, o problema descrito é um problema real das unidades de investigação.

16

Regra 1

Se o delegado à conferência pertence ao Program Committee



Regra 2

Se o delegado à conferência pertence ao Local-Arrangements

Committee



Regra 3

Se o delegado à conferência pertence ao Program Committee e ao

Local-Arrangements Committee



Facto 1

o delegado à conferência pertence ao Program Committee

Facto 2

o delegado à conferência pertence ao Local-Arrangements Committee

Figura 10 - Regras e factos inconsistentes

A base de conhecimentos apresentada na Figura 10 é inconsistente no sentido em que é possível derivar

que o mérito da proposta devido à participação na organização tem o valor 4 (regra 1 e facto 1; ou regra 2

e facto 2) e também é possível derivar que o mérito tem o valor 5 (i.e., não tem o valor 4).

Seria útil que a ferramenta computacional usada para implementar o sistema de avaliação do mérito de

pedidos de financiamento pudesse detetar este tipo de inconsistências.

4.2 Base de conhecimentos não completa

A base de conhecimentos da Figura 11 serve de exemplo para ilustrar dois tipos de não completude: a BC

contém factos que não são usados; e a BC tem regras que dependem de factos que não são conhecidos

nem se podem derivar, nem se podem perguntar ao utilizador.

17

Regras

Regra 1

Se o mérito da proposta em termos da participação na organização

da conferência tem o valor MéritoParticipação, e

o mérito da proposta em termos da apresentação de trabalhos tem

o valor MéritoApresentação, e

a importância da conferência para a UIDIA tem o valor

Importância

Então o mérito global da proposta tem o valor

Mérito 0.4 MéritoApresentação

0.4 MéritoParticipação

0.2 Importância

Regra 2

Se o número de artigos apresentados é maior ou igual a 2



Regra 3




Regra 4




Regra 5

Se a importância da conferência para a área científica da UIDIA

tem valor ImportânciaAreaCientifica, e

a importância da conferência para o reconhecimento da UIDIA tem

valor ImportânciaReconhecimento

Então a importância da conferência para atividades existentes na área

da UIDIA é

ImportânciaUIDIA 0.4 ImportânciaAreaCientifica

0.6 ImportânciaReconhecimento

Informação que pode ser pedida ao utilizador

Número de artigos a apresentar

Importância da conferência para a área científica da UIDIA

Importância da conferência para o reconhecimento da UIDIA

Figura 11- Base de conhecimentos incompleta

para o sistema de atribuição de financiamento da UIDIA

As regras incluídas na base de conhecimento apresentada na Figura 11 constituem versões com alterações

das regras realmente existentes na base de conhecimento do sistema (Figura 7). Nomeadamente, o

resultado produzido pela versão alterada da regra 5 designa-se ImportânciaUIDIA, enquanto a versão

original da regra produz o resultado Importância. Esta alteração foi introduzida propositadamente para

que o mecanismo de deteção de incompletude pudesse detetar um problema.

Para facilitar a compreensão do problema de determinar que conhecimento/informação faltam na base

de conhecimento, apresenta-se uma representação gráfica do conhecimento nela armazenado e das

relações entre os seus diversos componentes. Para isso recorremos aos diagramas de dependências da

metodologia de análise e conceção de sistemas baseados em conhecimento descrita em [Botelho e Ramos

1992]. Os diagramas de dependência são constituídos por unidades de decisão que representam

dependências entre variáveis do domínio. Cada unidade de decisão é representada graficamente por um

triângulo. As variáveis do domínio são representadas por retângulos. As variáveis de input (variáveis

18

independentes) são também representadas por retângulos mas com um ponto de interrogação antes do seu

nome.

A Figura 12 representa o diagrama de dependências correspondente à Base de Conhecimentos “de

papel” da Figura 11.

Figura 12 - Diagrama de decisão

para o sistema de atribuição de financiamento da UIDIA

Os dois retângulos da Figura 12 com linha a tracejado não fazem parte do diagrama de decisão; apenas

servem para indicar explicitamente a insuficiência do conhecimento disponível.

Falta de informação

Uma ferramenta computacional para sistemas baseados em conhecimento pode analisar o conhecimento

disponível e detetar possíveis insuficiências.

Em termos simplistas, a deteção de insuficiências de informação consiste essencialmente em

determinar se existe alguma implicação AB e não se pode provar se A nem se A a partir da Base de

Conhecimentos, nem se pode perguntar se A é verdade.

Usando, como exemplo, a base de conhecimentos descrita na Figura 11 e na Figura 12, a deteção de

informação insuficiente produziria o seguinte resultado:

O mérito da proposta depende do mérito devido à apresentação de trabalhos (MéritoApresentação), do

mérito devido à participação na organização da conferência (MéritoParticipação) e da importância da

conferência para a UIDIA (Importância).

A importância da conferência para a UIDIA (Importância) não é conhecida nem é perguntada ao

utilizador.

O mérito da proposta devido à participação na organização da conferência (MéritoParticipação) não é

conhecida nem é perguntada ao utilizador.

Repare-se que esta variável não é conhecida porque, talvez por engano, a unidade de decisão U3 produz

um resultado com a designação ImportânciaUIDIA em vez de Importância. Não há pois uma ligação

entre o resultado da unidade de decisão U3 e a unidade de decisão U1. Relativamente ao mérito devido à

participação na organização da conferência (MéritoParticipação), de facto essa variável não é conhecida,

nem pode ser perguntada, nem pode ser determinada por uma ou mais regras.

Factos e conclusões não usadas

Além da deteção de informação insuficiente, a ferramenta de desenvolvimento de sistemas baseados em

conhecimento poderá também detetar se existem factos inúteis na base de conhecimento ou se podem ser

geradas conclusões não usadas.

Em termos simples, a deteção de informação não usada consiste essencialmente em determinar se

existe algum facto B ou alguma implicação AB e não existe nenhuma implicação DC, tal que D seja

igual ou contenha B..

19

Considere-se uma vez mais o exemplo da Figura 11 e da Figura 12. Por exemplo, a importância da

conferência para atividades existentes no âmbito da UIDIA (variável ImportânciaUIDIA, unidade de

decisão U3) é determinada por uma das regras da base de conhecimentos e não é usada. A análise da base

de conhecimentos em termos de informação não usada produziria o seguinte relatório.

A importância da conferência para atividades existentes no âmbito da UIDIA (variável

ImportânciaUIDIA) é determinada pela regra 5 e não é usada.

O mérito global da conferência (variável Mérito) é determinado pela regra 1 e não é usado.

O mérito global da proposta é determinado e não usado em nenhuma outra regra, no entanto este é o

objetivo final do sistema. Ou seja, o aviso produzido pelo mecanismo de deteção de insuficiências na base

de conhecimento, relativamente à variável Mérito pode ser ignorado.

20

5 Implementação em Prolog de mecanismos de representação e raciocínio

5.1 Meta-interpretadores (Prolog em Prolog)

Os mecanismos de geração automática de explicações são mecanismos que usam o próprio conhecimento

do domínio do sistema para gerar explicações que podem ser exibidas ao utilizador. Idealmente, a geração

destas explicações não exige nenhum trabalho adicional ao Engenheiro do Conhecimento que cria o

sistema. O Engenheiro do Conhecimento apenas tem que representar o conhecimento da aplicação. A

utilização desse conhecimento para gerar explicações é da exclusiva responsabilidade do sistema.

Esta secção analisa a implementação de um sistema de raciocínio dedutivo encadeado para trás. Este

programa será estendido em secções posteriores.

Os mecanismos de geração de explicações apresentados são definidos para o caso concreto do

raciocínio dedutivo encadeado para trás. Para outros tipos de raciocínio ou para outras estratégias de

encadeamento teriam que ser criados outros mecanismos de geração de explicações.

Através de uma tecnologia de programação muito simples chamada meta-programação é possível criar

um programa em Prolog capaz de interpretar o próprio Prolog. Este programa não tem qualquer utilidade

por si só, mas a sua análise permite compreender mecanismos indispensáveis noutras secções deste

documento.

Um programa capaz de interpretar Prolog é um programa que recebe um objetivo Prolog e verifica se

o objetivo pode ser satisfeito pela instanciação de variáveis. Para isso, o programa verifica se o objetivo

que recebe é o objetivo verdade, ou se é uma conjunção cujos componentes são objetivos que se podem

satisfazer, ou se existe alguma cláusula na base de conhecimentos do Prolog que possa ser usada na

satisfação do objetivo. Posteriormente, o programa será sofisticado com a verificação de outras condições

(negações e objetivos “built-in”).

A Figura 13 mostra a definição do predicado solve/1 o qual é capaz de verificar se um objetivo Prolog

se pode satisfazer.

solve(verdade).

solve((A, B)):-

solve(A), solve(B).

solve(P):-

clause(P, Body),

solve(Body).

Figura 13 – Meta-interpretador de Prolog

Embora simples, o predicado solve/1 constitui a base do Prolog.

solve(P) tem sucesso, se o objetivo P puder ser satisfeito, isto é, se existir uma instanciação das

variáveis de P tal que P seja verdade (i.e., tal que P se possa derivar da Base de Conhecimentos).

A primeira cláusula da definição de solve/1 (Figura 13) diz que o objetivo verdade é verdade.

A segunda cláusula de solve/1 diz que uma conjunção (A, B) pode ser satisfeita se tanto A com B

puderem ser satisfeitos. É importante referir que, devido ao mecanismo de associatividade do Prolog, (A,

B) pode ser uma conjunção com mais do que dois argumentos. A é o primeiro argumento da conjunção, B

é o resto (eventualmente, outra conjunção).

A terceira cláusula de solve/1 diz que o objetivo P pode ser satisfeito se existir uma cláusula para P

com o formato P:-Body e se Body puder ser satisfeito. Para verificar se existe uma cláusula para um dado

objetivo, usa-se o predicado especial clause/2. clause(Head, Body) tem sucesso se existir uma clausula

com o formato Head:-Body na Base de Conhecimentos. Isto é, clause/2 devolve o corpo de cada cláusula

de um determinado predicado. Para verificar se Body pode ser satisfeito, solve/1 recorre a si próprio.

Para melhor compreender o funcionamento de solve/1, analisa-se um exemplo simples. A Figura 14

mostra uma pequena Base de Conhecimentos com cláusulas de relações familiares.

21

avo(X, Y):-

pai(X, Z),

pai(Z, Y).

avo(X, Y):-

pai(X, Z),

mae(Z, Y).

pai(bernardo, luis).

pai(luis, miguel).

Figura 14 – Pequena base de conhecimentos

A Figura 15 ilustra a utilização do predicado solve/1 no interpretador de Prolog. Na interação usa-se a

pequena Base de Conhecimentos da Figura 14.

?- solve(avo(bernardo, miguel)).

yes

?- solve(avo(X, Y)).

Xbernardo, Ymiguel;

no

?-

Figura 15 – Interação com o predicado solve/1

Na segunda interação, o Prolog não pode usar a primeira cláusula da definição de solve/1 porque o

objetivo avo(X, Y) não emparelha com verdade. A segunda cláusula da definição também não pode ser

usada porque o objetivo avo(X, Y) não emparelha com a conjunção (A, B). Como existe a cláusula avo(X,

Y):- pai(X, Z), pai(Z, Y), o Prolog tenta usar a terceira cláusula da definição de solve/1. De acordo com a

terceira cláusula, avo(X, Y) pode ser satisfeito se (pai(X, Z), pai(Z, Y)) também puder ser satisfeito.

Portanto, o objetivo inicial solve(avo(X, Y)) é substituído pelo novo objetivo solve((pai(X, Z), pai(Z, Y))).

A primeira cláusula da definição não pode ser usada porque (pai(X, Z), pai(Z, Y)) não emparelha com

verdade. A segunda cláusula pode ser usada porque (pai(X, Z), pai(Z, Y)) emparelha com (A, B).

Seguindo a segunda cláusula, a conjunção (pai(X, Z), pai(Z, Y)) pode ser satisfeita se o objetivo pai(X, Z)

puder ser satisfeito e se o objetivo pai(Z, Y) também puder ser satisfeito. O objetivo inicial é agora

substituído pelos dois objetivos solve(pai(X, Z)) e solve(pai(Z, Y)).

Mais uma vez, o objetivo solve(pai(X, Z)) não pode ser resolvido pela primeira nem pela segunda

cláusula de solve/1. O mesmo acontece em relação ao objetivo solve(pai(Z, Y)). Como um facto P é

equivalente à cláusula P:-verdade, a terceira cláusula pode ser aplicada para resolver o objetivo

solve(pai(X, Z)), desde que Xbernardo, Zluis e Bodyverdade. Consequentemente, solve(pai(X, Z)) é

substituído por solve(verdade).

solve(verdade) é resolvido pela primeira cláusula da definição de solve/1. A instanciação da variável

Y é propagada para o segundo objetivo por resolver, nomeadamente solve(pai(luis, Y)).

solve(pai(luis, Y)) é resolvido por um processo análogo ao da resolução de solve(pai(X, Z)), resultando

na instanciação de X com a constante bernardo.

Como solve(pai(X, Z)) e solve(pai(Z, Y)) foram resolvidos, então solve((pai(X, Z), pai(Z, Y))) também

foi resolvido. Consequentemente, solve(pai(X, Y)) também foi resolvido.

O predicado solve/1 definido na Figura 13 pode ser facilmente aumentado de modo a que a negação

por falha seja resolvida. Para isso basta dizer que not(P) é satisfeito se a satisfação de P falha.

Em Prolog, a satisfação de diversos predicados e a avaliação de diversos operadores recorrem a

procedimentos específicos: são os chamados predicados e operadores “built-in”. Destes destacam-se os

operadores aritméticos, certos predicados relacionais, e procedimentos para ler e escrever, operadores de

manipulação da base de conhecimentos (i.e., assert e retract) e operadores de controlo. Um

meta-interpretador pode recorrer ao predicado call/1 para avaliar a satisfação de predicados

pré-construídos na linguagem.

Na Figura 16 apresenta-se a extensão do meta-interpretador solve/1 com a negação e com predicados

pré-construídos.

22

solve(verdade).

solve((A, B)):-

solve(A), solve(B).

solve(not(P)):-

\+ solve(P).

solve(P):-

clause(P, Body),

solve(Body).

solve(P):-

system(P),

call(P).

Figura 16 – Meta-interpretador com negação e predicados “built-in”

Na última cláusula da Figura 16, surge o predicado especial system/1. system/1 serve para testar se um

predicado é pre-construído a linguagem. A sintaxe de system/1 não é sempre a mesma, varia de

implementação para implementação. Em certas implementações, o argumento do predicado system/1 é

um termo formado pelo nome do predicado e pela sua aridade, por exemplo write/1. Também pode

acontecer que system/1 nem sequer exista e que tenha que se utilizar outro com o mesmo objetivo.

5.2 Explicações “Why”

Quando o sistema faz uma pergunta ao utilizador, este pode não perceber porque razão o sistema o faz. Se

o sistema tiver a capacidade de gerar explicações “Why”, será capaz de explicar ao utilizador qual é a

finalidade da pergunta. A interação da Figura 17 ilustra esta situação. O sistema explica ao utilizador que

quer saber se o Luís é pai da Catarina porque se o Bernardo é pai do Luís e o Luís é pai da Catarina, então

o sistema conclui que o Bernardo é avô da Catarina que é o que ele está a tentar fazer.

?- avo(bernardo, catarina).

pai(luis, catarina) (sim/nao/porquê)? porquê

Porque

Se pai(bernardo, luis) e pai(luis, catarina)

Então avo(bernardo, catarina)

pai(luis, catarina) (sim/nao/porquê)? sim

yes

?-

Figura 17 – Interação com explicações “Why”

Como as explicações do tipo “Why” servem para o sistema explicar por que razão faz determinada

pergunta, este mecanismo de geração de explicações está intimamente ligado à possibilidade de fazer

perguntas ao utilizador.

O meta-interpretador que vamos analisar tenta provar se um determinado objetivo é verdade. Se

necessário, pede ao utilizador para dizer se uma dada proposição é verdade ou falsa. Para isso tem que se

poder especificar que factos podem ser perguntados ao utilizador. Vamos usar o predicado especial

askable/1. askable(P) significa que o sistema pode perguntar ao utilizador se P é verdade ou falso.

Quando o meta-interpretador tenta provar um dado objetivo P, e o sistema não sabe que P é falso e P

não é igual a verdade, nem é uma conjunção, nem é uma negação, nem há uma cláusula para P, e P pode

ser perguntado, então o meta-interpretador pergunta se P é verdade. Se o utilizador responder que sim, P é

acrescentado à base de conhecimentos. Se o utilizador responder que não, untrue(P) é acrescentado à base

de conhecimentos. Se o utilizador quiser saber porque razão o sistema faz a pergunta, este apresenta uma

explicação de tipo “why”. Se o sistema guardar as regras usadas no seu raciocínio, poderá apresentá-las

como explicação daquilo que tenta provar em cada passo. Para isso, o predicado solve/2 terá dois

argumentos: objetivo que se pretende provar e a lista das regras usadas até ao passo de prova atual.

23

solve(verdade, _).

solve((A,B), Reasons):-

solve(A, Reasons),

solve(B, Reasons).

solve(P, Reasons):-

clause(P, Body),

solve(Body, [(P:-Body)|Reasons]).

solve(P, Reasons):-

askable(P),

\+ untrue(P),

ask(P, Answer),

process_answer(P, Answer, Reasons).

ask(P, Answer):-

write(P), write(' yes/no/why? '),

read(Answer).

process_answer(P, yes, _):-

!,

assert(P).

process_answer(P, no, _):-

!,

assert(untrue(P)),

fail.

process_answer(P, why, [(Q:-R)|Reasons]):-

!,

display_rule((Q:-R)), nl,

ask(P, Answer),


process_answer(P, why, []):-

!,

write('I have no more explanations to give '), nl,

ask(P, Answer),

process_answer(P, Answer, []).

process_answer(P, _, Reasons):-

!,

ask(P, Answer),


display_rule((Q:-R)):-

write('IF '), display_cond(R), nl,

write_list(['THEN ', Q]).

display_cond((P, Cond)):-

write_list([P, ' and ']),

display_cond(Cond).

display_cond(P):-

P \= (_, _),

write(P).

Figura 18 – Meta-interpretador para explicações “Why”

O meta-interpretador da Figura 18 é inteiramente baseado no meta-interpretador explicado na secção 5.1.

As únicas diferenças são o argumento extra para conter a lista das regras usadas até ao passo atual da

prova, e a cláusula extra que pergunta se uma dada proposição atómica é verdadeira ou falsa e que

apresenta explicações se o utilizador quiser. Esta cláusula extra usa o predicado process_answer/3 para

processar a resposta do utilizador.

Se o utilizador disser que P é verdade (yes), process_answer/3 acrescenta P à Base de Conhecimentos.

Se o utilizador disser que P é falso (no), process_answer/3 acrescenta untrue(P) à Base de Conhecimentos

e falha. Se o utilizador pretender explicações (why), process_answer/3 apresenta a explicação ao

utilizador e volta a perguntar se P é verdade ou falso e processa a resposta recursivamente. Se a resposta

do utilizador não for nenhuma destas três possibilidades, process_answer/3 volta a perguntar ao utilizador

se P é verdade ou falso.

24

Se o utilizador voltar a pedir explicações, o predicado process_answer/3 explicará porque razão

pretende chegar a essa conclusão.

O meta-interpretador solve/2 apenas permite fazer perguntas fechadas ao utilizador, isto é, perguntas

com um conjunto limitado de respostas possíveis (yes, no, why). Numa aplicação mais interessante,

solve/2 tem que ser melhorado para permitir perguntar perguntas abertas ao utilizador, por exemplo

“Quem é o pai da Catarina?” ou mesmo “Introduza valores de X e de Y tal que pai(X, Y)”.

Tendo o predicado solve/2 definido na Figura 18, pode criar-se um predicado solve/1 de mais simples

utilização, o qual chamará solve/2.

solve(P):-

solve(P, []).

Figura 19 – Interface com o meta-interpretador com explicações “why”

solve/1 definido na Figura 19 pode ser usado em interações como a da Figura 17.

5.3 Explicações “How”

As explicações “How” são usadas para explicar ao utilizador como é que o sistema chegou a uma dada

conclusão. Para isso, o funcionamento do sistema será constituído por dois passos. No primeiro passo, um

meta-interpretador resolve o problema apresentado e cria uma estrutura de dados com a representação de

todos os passos da dedução. No segundo passo, um outro predicado é chamado com a estrutura de dados

criada. O processo de geração de explicações efetuado por este segundo predicado consiste em apresentar

a estrutura que representa os passos da dedução num formato legível para o utilizador. A Figura 20 exibe

a definição do predicado principal do novo meta interpretador. solve(P):-

solve(P, Tree),

explain_tree(Tree).

Figura 20 – Meta-interpretador com explicações “How”

Para perceber o funcionamento de um meta-interpretador com explicações “how” é necessário

compreender primeiro no que consiste uma estrutura com a representação dos passos de uma dada

dedução, isto é, no que consiste uma árvore de prova. Para isso, consideremos a Base de Conhecimentos

da Figura 14. Qual é a árvore de prova da interrogação avo(bernardo, miguel)? avo(bernardo, miguel) é

verdade se pai(bernardo, Z) e pai(Z, miguel) puder ser satisfeito. pai(bernardo, Z) é verdade se a variável

Z for instanciada com a constante luis, e pai(luis, miguel) é verdade. A Figura 21 mostra a árvore de

prova do objetivo avo(bernardo, miguel) e a estrutura de dados que a representa.

Representação gráfica Estrutura de dados

avo(bernardo, miguel)

(pai(bernardo, Z) verdade,

pai(luis, miguel) verdade)

Figura 21 – Árvore de prova de avo(bernardo, miguel)

O predicado solve/2 tem apenas que criar uma estrutura de representação de uma árvore de prova,

enquanto que o predicado explain_tree/1 tem que imprimir uma árvore de prova ao utilizador.

A árvore de prova de verdade é verdade, a árvore de prova de uma conjunção é a “conjunção” das

árvores de prova, e a árvore de prova de P é (P Prova) se existir uma cláusula com o formato P:-Body

na base de conhecimentos e Prova for a árvore de prova de Body.

25

:- op(‘’, 1200, xfy).

solve(verdade, verdade).

solve((A, B), (ProofA, ProofB)):-

solve(A, ProofA), solve(B, ProofB).

solve(P, P Proof):-

clause(P, Body),

solve(Body, Proof).

Figura 22 – Predicado para criar árvores de prova

O comando op(‘’, 1200, xfy) serve para declarar o operador infixo com associatividade à esquerda e

com precedência 1200. Tal como o meta-interpretador da Figura 13, o meta-interpretador da Figura 22

deve ser expandido para poder enfrentar outras situações. Para já apresenta-se o predicado explain_tree/1

para geração de uma explicação com base numa árvore de prova produzida por solve/2.

explain_tree((Pverdade)):-

!, write(P), wrtite(‘ is a fact in the knowledge base.’), nl.

explain_tree((PTree)):-

!,

first_level_explanation(Tree, Heads),

present_conclusion(P), write(‘ because’), nl,

display_implication(P, Heads), nl,

explain_tree(Tree).

explain_tree((TreeA, TreeB)):-

explain_tree(TreeA), wrtie(‘ AND’), nl,

explain_tree(TreeB).

first_level_explanation(PTree, [P]).

first_level_explanation((P1Tree1, Tree2), [P1|Heads]):-

first_level_explanation(Tree2, Heads).

present_conclusion(P):-

write(P), write(‘ is verdade’).

display_implication(P, Cond):-

write(‘IF ‘), display_antecedent(Cond), nl,

write(‘THEN ‘), write(P).

display_antecedent([Cond1, Cond2|Conds]):-

write(Cond1),

write(‘AND ‘),nl,

display_antecedent([Cond2|Conds]).

display_antecedent([Cond]):-

write(Cond), write(‘.’).

Figura 23 – Predicado para imprimir uma explicação “how” com base numa árvore de prova

Para perceber o predicado explain_tree/1 é fundamental definir que explicação se pretende obter para

uma dada árvore de prova. Uma explicação adequada para a árvore da Figura 21 seria algo como

avo(bernardo, miguel)é verdade porque

SE pai(bernardo, luis)e

pai(luis, miguel)

ENTÃO avo(bernardo, miguel).

pai(bernardo, luis) é um facto na base de conhecimentos.

pai(luis, miguel) é um facto na base de conhecimentos.

Figura 24 – Explicação do tipo “how”

Para que esta explicação seja imprimida quando a árvore da Figura 21 é atravessada tem que se separar a

conclusão (raiz da árvore) das condições (resto da árvore). first_level_explanation/2 é o predicado que

efetua esta separação. A principal observação a fazer é que uma árvore com a forma (P (QQTree,

RRTree)) deve dar origem a uma regra com a forma “Se Q e R Então P”. As árvores QTree e RTree

não contribuem para esta regra. QTree (árvore de prova de Q) e RTree (árvore de prova de R) são

processadas recursivamente pelo predicado explain_tree/1. Para que se possa imprimir a regra “Se Q e R

26

Então P” a partir de (P (QQTree, RRTree)), é necessário extrair Q e R de (QQTree, RRTree).

É esse o papel de first_level_explanation/2.

Para uma árvore com o formato RootRest, o predicado first_level_explanation/2 cria uma lista com

as raízes de Rest. Se Rest for uma estrutura arborizada composta por uma única árvore, a lista criada por

first_level_explanation/2 tem um único elemento (primeira cláusula de first_level_explanation/2) – a raiz

da árvore Rest. Se Rest for uma estrutura arborizada composta por várias árvores, a lista gerada por

first_level_explanation/2 obtém-se por construção da raiz da primeira dessas subárvores com a lista que

resulta da aplicação de first_level_explanation/2 ao resto da estrutura arborizada (segunda cláusula de

first_level_explanation/2).

5.4 Validação da base de conhecimentos

Este capítulo ocupa-se da definição e análise de ferramentas computacionais que suportem o

desenvolvimento de bases de conhecimento através da automatização de alguns mecanismos de

verificação do seu conteúdo. Uma das áreas de verificação consiste em detetar falhas (omissões) no

conhecimento de uma BC. Pretende-se automatizar a deteção de conhecimento que não é usado e a

existência de conhecimento que depende de informação que não é conhecida e aparentemente não pode

ser determinada.

Outro tipo de validação consiste em criar mecanismos capazes de detetar potenciais inconsistências

numa base de conhecimento. Existe uma inconsistência potencial, por exemplo quando a base de

conhecimento contém as regras “Se A Então P” e “Se A Então P”. Na realidade, uma base de

conhecimento formada por estas duas regras não é inconsistente (i.e., não contém a contradição). No

entanto, se a proposição A for acrescentada à BC, esta torna-se imediatamente inconsistente.

A utilização de ferramentas computacionais para o desenvolvimento de Sistemas Baseados em

Conhecimento capazes de detetar falhas e inconsistências potenciais numa BC facilita a tarefa de

assegurar a correção de uma Base de Conhecimentos. A próxima secção trata da deteção de falhas numa

BC. A secção seguinte centra-se na análise de algoritmos que podem ser usados para detetar

inconsistências (potenciais) numa BC.

5.4.1 Incompletude da Base de Conhecimentos

Nesta secção analisa-se o problema da criação de algoritmos capazes de detetar falhas no conhecimento

representado numa base de conhecimento. Assume-se que a BC é uma coleção de regras e de factos e que

o motor de inferência efetua raciocínio dedutivo apenas, excetuando a aquisição de informação através de

instruções de leitura.

A ideia de base destas verificações consiste em percorrer todas as regras e todos os factos de uma base

de conhecimento e detetar falhas relativas a esses factos e regras.

Como o Prolog não dispõe de nenhum mecanismo que permita a enumeração de todas as cláusulas da

sua BC, as regras “Se Antecedente Então Consequente” são representadas por factos com o formato

rule(Antecedente, Consequente); e os factos são representados através de factos com o formato fact(P).

Factos e conclusões não usados

Um facto ou uma conclusão P não são usados se não existir nenhuma regra com uma condição que

contenha P. Um facto ou uma conclusão P não usados devem ser detetados dado que podem constituir

falhas na base de conhecimentos.

O algoritmo de deteção de falhas que se descreve nesta secção percorre todos as estruturas fact(P) e

rule(Q, P) da BC e verifica se P não aparece na condição de nenhuma regra.

27

detet_useless_knowledge:-

knowledge(P),

useless(P),

write(P), write(‘ is useless.’), nl,

fail.

detet_useless_knowledge.

knowlege(P):-

fact(P); rule(_, P).

knowlege(untrue(P)):-

untrue(P); rule(_, untrue(P)).

useless(P):-

rule(Q, _),

contains(Q, P),

!,

fail.

useless(_).

contains(A, A).

contains((A, B), A).

contains((A, B), C):- contains(B, C).

Figura 25 – Predicado para detetar conhecimento não usado numa BC

knowledge/1 enumera todos os factos e potenciais conclusões da BC. useless(P) determina se P não surge

em nenhuma regra da BC. useless(P) falha se descobre uma regra cuja condição contém P. contains(A, B)

determina se uma condição A com a forma geral de conjunção contém a expressão B. Este predicado não

é geral mas dá uma ideia do tipo de raciocínio necessário.

Regras que dependem de informação não determinável

O algoritmo descrito nesta secção percorre todas as regras da BC e deteta aquelas cujas condições contêm

literais P que não são factos, nem são conhecidamente falsos, nem podem ser perguntados ao utilizador,

nem podem ser concluídos por nenhuma regra da BC.

missing_knowledge:-

rule(Q, _),

contains(Q, P),

missing_link(P),

write(P), write(‘ is a missing link in the knowledge base.’), nl,

fail.

missing_knowledge.

missing_link(P):-

(fact(P); untrue(P); askable(P); rule(_, P); rule(_, untrue(P)),

!,

fail.

missing_link(_).

Figura 26 – Predicado para detetar regras que dependem de informação não determinável

Naturalmente, o facto de haver uma regra cuja conclusão é P, não garante só por si, que se possa

determinar se P é verdade. Seria necessário determinar se a condição da regra pode ser avaliada.

5.4.2 Inconsistência da Base de Conhecimentos

Nesta secção apresenta-se a implementação de dois algoritmos para detetar inconsistências potenciais e

inconsitências explícitas numa base de conhecimentos. O primeiro algoritmo deteta todas as fórmulas

atómicas P tais que tanto P como untrue(P) pertencem à BC. O segundo algoritmo deteta todas as regras

rule(Q, P) representadas na BC para as quais existe pelo menos uma regra rule(R, untrue(P)) na BC tal

que R contém ou está contida em Q.

28

detet_contradictions:-

fact(P),

fact(untrue(P)),

show_contradiction(P),nl,

fail.

detet_contradictions.

show_contradiction(P):-

write(‘The kb contains ‘),

write(P), write(‘ and ‘),

write(untrue(P)), write(‘.’).

Figura 27 – Deteção de contradições explícitas

detet_contradictions/0 percorre todos factos da base de conhecimento. Para cada facto P verifica se existe

um facto untrue(P). Se existir o facto untrue(P), imprime a contradição no monitor através do predicado

show_contradiction/1, falha e retrocede até que considera o próximo facto. Se não existir o facto

untrue(P), falha e retrocede imediatamente para o próximo facto. Quando não há mais factos, a primeira

cláusula de detet_contradictions/0 falha, passando-se para a segunda cláusula a qual tem sucesso.

detet_potential_contradictions:-

rule(Q, P),

rule(R, untrue(P)),

(includes(Q, R); includes(R, Q)),

show_contradictory_rules(Q, R, P), nl,

fail.

detet_potential_contradictions.

includes(Q, (R1, R)):-

contains(Q, R1),

includes(Q, R).

includes(Q, R):-

R \= (_, _),

contains(Q, R).

show_contradictory_rules(Q, R, P):-

write(‘The KB contains the rule’), nl,

display_rule(rule(Q, P)), nl,

write(‘and the rule’), nl,

display_rule(rule(R, untrue(P))).

Figura 28 – Deteção de potenciais contradições

O ciclo principal de detet_potential_contradictions/0 é semelhante ao de detet_contradictions/0. A

diferença é que detet_potential_contradictions/0 percorre todas as regras da BC. Para cada uma verifica

se existe uma regra potencialmente contraditória. Se existir, chama o predicado

show_contradictory_rules/3 para imprimir a contradição e falha, retrocedendo para a próxima regra. Se

não existir uma regra contraditória, falha (sem imprimir) e retrocede para a próxima regra. Quando todas

as regras da BC tiverem sido percorridas, o processo termina.

A deteção de uma regra potencialmente contraditória recorre aos predicados r_contains_q/2 e

q_contains_r/2, um dos quais é definido à custa do outro.

q_contains_r(Q, R) verifica se a conjunção de literais Q é igual ou contém todos os literais da

conjunção de literais R. Para isso, percorre cada literal de R e chama o predicado contains/2 para verificar

se ele aparece em Q. contains/2 é definido na Figura 25.

O predicado show_contradictory_rules/3 recorre ao predicado display_rule/1 definido na Figura 18

para imprimir uma regra.

5.5 Implementação de um sistema de regras de produção

A presente secção centra-se na implementação de um sistema de representação de conhecimento e de

raciocínio com regras de produção. No capítulo 0 e na secção 1 foram exploradas várias aplicações

usando um mecanismo de inferência com encadeamento para trás semelhante ao usado no Prolog. Aqui

analisa-se a implementação de um mecanismo de inferência encadeado para a frente.

29

Um sistema de regras de produção tem três componentes fundamentais: uma base de conhecimento

constituída por um conjunto de regras de produção, uma memória de trabalho onde se armazenam os

factos temporários que são criados e removidos pelas ações especificadas as regras, e um motor de

inferência que avalia as condições das regras de acordo com o conteúdo da memória de trabalho e executa

as ações das regras cuja condição estiver satisfeita.

A ideia de base do raciocínio encadeado para a frente com regras de produção é a seguinte. Em cada

ciclo do raciocínio são verificadas todas as condições de todas as regras da BC. As regras com a condição

satisfeita são agrupadas numa estrutura chamada Conjunto de Conflito (“conflict set”). As ações das

regras do conjunto de conflito não podem ser todas executadas porque a execução da ação de uma das

regras poderá invalidar as condições de outras regras do conjunto de conflito. Consequentemente,

escolhe-se apenas uma das regras do conjunto de conflito e executa-se a sua ação. Este processo repete-se

até que o conjunto de de conflito é o conjunto vazio.

psys :-

repeat,

conflict_set(Set),

process_conflict_set(Set), !.

process_conflict_set([]):- !.

process_conflict_set(Set):-

select_rule(Set, rule(_,Action)),

perform_action(Action),

!,

fail.

conflict_set(Set):-

findall(rule(Cond, Act), (rule(Cond, Act), satisfied(Cond)), Set).

% simple minded conflict resolution strategy

select_rule([R|_], R).

% simple, but maybe sufficient, condition evaluator

satisfied(Cond):- call(Cond).

perform(A):-

trace_level(0),

!,

call(A).

perform(A):-

action_notice(A, Msg),

write(Msg), nl,

call(A).

Figura 29 – Ciclo principal do raciocínio num sistema de produção

O predicado conflict_set/1 cria o conjunto de regras da base de conhecimentos cuja condição está

satisfeita (i.e., o conjunto de conflito), e o predicado process_conflict_set/1 processa o conjunto de

conflito produzido. Se este for o conjunto vazio, o processamento termina. Caso contrário, é selecionada

uma regra do conjunto de conflito e a sua ação é executada resultando numa possível alteração da

memória de trabalho.

O predicado satisfied/1 serve para determinar se uma condição está satisfeita. Se o formato das

condições for igual ao usado na linguagem Prolog e se os factos forem factos em Prolog, satisfied/1 é o

mesmo que call/1. Se o formato das condições ou a forma como os factos são armazenados for diferente

do usado no Prolog, satisfied/1 terá de ser alterado.

O predicado perform/1 depende igualmente do formato com que as sequências de ações são

especificadas. Se esse formato for o mesmo do formato de uma sequência de objetivos Prolog, perform/1

será o mesmo que call/1. Na definição da Figura 29, perform/1 tem uma função adicional. Se o nível de

notificação pretendido (trace-level) for 0, a execução das ações é muda. Se o nível de notificação

pretendido for 1, a execução das ações é acompanhada da impressão de mensagens. O nível de

notificação está definido no predicado trace_level/1. As mensagens estão definidas na tabela

action_notice/2.

30

Além de se poder ligar e desligar a exibição de mensagens antes da execução das ações, este

mecanismo de notificação tem a vantagem de permitir definir novas ações com base em ações já

existentes sem herdar obrigatoriamente a impressão de mensagens de notificação. Se pretendermos herdar

a notificação, em vez de se usar diretamente uma ação, usa-se o procedimento perform/1.

Além do ciclo principal, um sistema de regras de produção tem que ter as definições das ações

primitivas que podem ser usadas na parte direita das regras e que podem ser usadas também na definição

das ações do domínio da aplicação. Como a implementação é em Prolog, todas as ações do Prolog podem

ser usadas nas regras de um sistema (e.g., write, read, assert, retract).

As mensagens a serem exibidas antes da execução de cada mensagem devem ser definidas pelo

predicado action_notice/2 com se exemplifica na Figura 30.

action_notice(conclude(P), Msg):-

list_to_string([P, was, concluded], Msg).

action_notice(remove(P), Msg):-

list_to_string([P, is, no, longer, verdade], Msg).

action_notice(create_goal(P), Msg):-

list_to_string([goal(P), was, created], Msg).

action_notice(remove_goal(P), Msg):-

list_to_string([goal(P), was, removed], Msg).

action_notice(retract, ‘’).

Figura 30 – Mensagens a imprimir para cada ação

list_to_string/2 tem que ser implementado usando os mecanismos de conversão de dados da

implementação específica de Prolog usada. No caso do Win-Prolog da LPA, cria-se um predicado que

percorre toda a lista e imprime todos os seus componentes separados por espaços e terminados por um

ponto final. O resultado da impressão é redirecionado para uma string em vez do terminal.

list_to_string(L, Msg) :-

print_msg(L) ~> Msg.

print_msg([A, B | Rest]):-

write(A), write(‘ ‘),

print_msg([B | Rest]).

print_msg([A]):-

write(A), write(‘.’).

Figura 31 – Conversão de uma lista de palavras numa string

O operador infixo ~>/2 faz com que o output produzido por um ação de impressão seja redireccionado

para uma string de caracteres.

Para utilizar o mecanismo de inferência analisado, primeiro cria-se a base de conhecimento, incluindo

as ações do domínio e as mensagens a serem imprimidas antes da execução de cada ação. Depois usa-se o

assert/1 do Prolog para inicializar a memória de trabalho. Finalmente, chama-se o predicado psys/0 para

efetuar a inferência.

31

6 Referências

[Botelho e Ramos 1992] Botelho, L.M.; e Ramos, P.N. 1992

Documents

Inteligência Artificialhome.iscte-iul.pt/~luis/aulas/ia/Sistemas baseados em regras.pdf · Existem dois tipos de ... O raciocínio usado com este método de representação de conhecimento