Inteligência Artificial
Universidade da Madeira
Inteligência Artificial
Representação de Conhecimento
e
Inferência
Agenda
z
Parte 3
z Lógicas
Não Monótonas
z Mundo
Fechado (Closed
(Closed World Assumption)
Assumption)
z Lógica por Omissões (Ló
(Lógica Default)
Default)
z
Parte 4
z Mudanças
no Mundo e Revisão de Crenças
z Revisão
de Crenç
Crenças
z Cálculo Situacional
1
Inteligência Artificial
Universidade da Madeira
Imaginem um macaco ….
Era este?
2
Inteligência Artificial
Universidade da Madeira
Ou este?
Agora imaginem a Ronaldo …
3
Inteligência Artificial
Universidade da Madeira
Porquê que agora perguntaram
qual?
Qual é o beco mais seguro?
4
Inteligência Artificial
Universidade da Madeira
Exemplo
Dei a minha esposa um anel de diamantes
z O diamante risca o vidro
z A nossa janela é de vidro
z Um dia ela tentou riscar a janela com o
anel, mas não ficou riscado
z
z
O que podemos concluir ? …
O que é que todos estes exemplos
têm em comum?
Não possuímos informação completa
z Utilizamos “o nosso bom senso”
z Pensamos nas “hipóteses mais viáveis”
z Nova informação pode fazer-nos mudar
de opinião
z
5
Inteligência Artificial
Universidade da Madeira
Lógicas Não Monótonas
Hipótese de Mundo Fechado
Closed World Assumption - CWA
z
Esta suposiç
suposição baseiabaseia-se em assumir que toda a
informaç
informação positiva que é necessá
necessário saber está
está na
nossa KB.
z
Esta suposiç
suposição permite obter informaç
informação negativa. A
informaç
negativa
não
está
representada
informação
está
frequentemente de uma maneira explí
explícita.
z
A informaç
informação que não é mencionada na KB assumeassume-se
como falsa,
falsa, isto é, se não encontraencontra-se uma instância
positiva na KB, então é valida a negaç
negação.
6
Inteligência Artificial
Universidade da Madeira
Hipótese de Mundo Fechado
Closed World Assumption - CWA
z
É uma té
técnica usada na inteligência artificial, na teoria
da base de dados e na programaç
programação em ló
lógica.
z
Uma convenç
convenção usual entre os seres humanos que se
tem acerca de um tema, é toda a informaç
informação possí
possível do
mesmo. Em informá
informática existem numerosos exemplos
para aqueles que usam esta convenç
convenção. Um exemplo
típico ocorre nas consultas a base de dados
convencionais.
convencionais.
Hipótese de Mundo Fechado
z
SuponhaSuponha-se por exemplo:
Que a informaç
informação acerca dos professores de uma
Universidade da Madeira está
está registada numa base de
dados. Para verificar se Dan Hirsch é um professor
desta universidade, o procedimento normal é consultar a
base de dados para ver se apareceu tal nome. Se não
for tal o caso, a conclusão é que Dan Hirsch não é
professor desta universidade.
z
Estas conclusões não são as mais correctas, porque o
facto de não aparecer tal nome pode deverdever-se a muitas
causas; pode ser um docente novo que ainda não foi
inserido os seus dados, por alguma falha no sistema da
KB.
7
Inteligência Artificial
Universidade da Madeira
Hipótese de Mundo Fechado
z
Esta ideia pode ser expressa de vá
várias formas, por
exemplo:
z
z
z
z
A informaç
informação positiva que temos numa BD é toda a
informaç
informação positiva possí
possível.
Se não temos a certeza de que uma crenç
crença é
verdadeira então supomos que é falsa.
A única verdade é o que se sabe, todo o resto é
falso.
Se ao supor que algo é falso e consistente com as
crenç
crenças disponí
disponíveis, então supõesupõe-se falso.
Hipótese de Mundo Fechado
z
Assumamos a seguinte base de dados de voos entre
Funchal e Lisboa:
z
z
Partida
Destino
Hora
FNC
LIS
08:10
FNC
LIS
19:25
LIS
FNC
09:50
LIS
FNC
21:15
Uma consulta sobre a existência de um voo de FNC a LIS as 08:10
se responderá
responderá afirmativamente.
afirmativamente.
Uma consulta sobre a existência dum voo de FNC a LIS as 17:00
se responderá
negação da existência está
está
responderá negativamente,
negativamente, isto é, a negaç
certa.
8
Inteligência Artificial
Universidade da Madeira
Hipótese de Mundo Fechado
z
Formalmente:
CWA(
CWA(KB)
KB) = KB ∪ { ¬p(t) se KB
p(t) }
onde p(t) é uma instância fixa (ground
), e o operador
(ground),
CWA(
CWA(⋅) representa a clausura da KB pela Hipó
Hipótese de
Mundo Fechado
É importante notar que este tipo de raciocí
raciocínio não é
monó
monótono,
tono, isto é, pode acontecer que KB1 ⊆ KB2 e
CWA(
CWA(KB1) { CWA(
CWA(KB2).
z
No exemplo dos voos, se agregarmos um voo ás
17:00 de FNC a LIS a negaç
negação já
já não pode ser
inferida
Hipótese de Mundo Fechado
z
Se incluí
incluímos informaç
informação disjuntiva podem aparecer
problemas. Seja KB = { a ∨ b }, de esta base de
conhecimento não podem ser inferidas nem a nem b.
z
A CWA(
CWA(KB)
KB) = KB ∪ { ¬p(t) si KB
p(t) },
}, isto é
{ a ∨ b } ∪ { ¬a, ¬b } ∪ N = { a ∨ b, ¬a, ¬b } ∪ N
onde N é o resto dos literais ¬p(t) tais que
p(t)
z
Então da CWA(
CWA(KB)
KB) podepode-se inferir a e b.
z
Isto, CWA(
CWA(KB)
KB) é inconsistente.
KB
9
Inteligência Artificial
Universidade da Madeira
Hipótese de Mundo Fechado
z
Existe uma relação entre a Hipótese de Mundo
Fechado e a Negação por Defeito (vista em
Programação Lógica).
z
No caso de ter um programa lógico definido P
e um elemento A da base de Herbrand de P
se a consulta A tem uma árvore SLD que falha
finita mente então A não é consequência de P
e pode-se inferir ¬A.
Lógica de Omissões (Default Logic):
Breve História
z
Introduzida por R. Reiter em 1980
z
Lógica não monó
monótona baseada na consistência
z
Usada para formalizar tarefas de diferentes raciocí
raciocínios
z
Exemplo:

z
Heranç
Heranças (Etherington
(Etherington,, 1987)
DiferenciaDiferencia-se de outras abordagens pela maneira como representa
omissões, nomeadamente, como regras de inferência com uma
verificaç
verificação adicional de consistência.
10
Inteligência Artificial
Universidade da Madeira
Lógica de Omissões (Default Logic)
z
Lógica de omissões = Ló
Lógica Clá
Clássica + Regras de omissão
z
Uma regra de omissão é uma regra de inferência revogá
revogável na
forma:
F:G
H
Onde F, G, H são frases da linguagem, chamadas,
respectivamente, pré
pré-requisito, justificaç
justificação e conclusão da regra de
omissão.
z
z
A interpretaç
interpretação da regra é: se F é conhecida e não há
há qualquer
prova de que G seja falsa, então H pode ser inferida.
z
Uma regra por omissão normal é uma regra de omissão da forma:
F:G
G
Exemplo:
z
A maioria das aves voa. Tweety é uma ave. Tweety voa?
z
Formalizaç
Formalização de primeira ordem:
(∀ X) (ave (X) ∧ ¬ pinguim (X) ∧ ¬ avestruz (X) ∧ …)→ voa (X)
z
Problemas:
z
Não sabemos todas as excepç
excepções.
z
Não podemos concluir que o Tweety não pertence a uma
destas excepç
excepções.
Ideia: Gostarí
Gostaríamos de concluir que o Tweety voa por omissão
(default)
default)
11
Inteligência Artificial
Universidade da Madeira
Raciocínio de omissão (Default reasoning):
z
Regras de omissão:
ave (X): voa (X)
voa (X)
z
Excepç
Excepções {(∀
{(∀ X) (pinguim (X) → ¬ voa (X)),
(∀ X) (avestruz (X) → ¬ voa (X)),
…
z
Mas como pode a consistência ser definida?
z
Alguns objectos de tipo s têm a propriedade p
Consistência:
z
A aplicaç
aplicação de uma regra de omissão requer que uma condiç
condição
consistente seja satisfeita.
z
O que torna esta condiç
condição complicada é o facto de a consistência
depender da aplicaç
aplicação ou não aplicaç
aplicação de todas as regras por
omissão na teoria.
z
Alé
Além disso, as regras podem interagir de maneiras complexas.
z
Com o objectivo de definir uma semântica precisa para esta ló
lógica,
Reiter introduziu a noç
noção de extensão no lugar dos modelos da
lógica clá
clássica.
12
Inteligência Artificial
Universidade da Madeira
Extensões de Teorias de
Omissão:
z
Uma Teoria de Omissão é um par (D, W) sendo W um conjunto de
frases de uma Linguagem de Primeira Ordem e D um conjunto de
regras por omissão na forma:
A : B1, …, Bn
C
onde A, Bi e C são fó
fórmulas clá
clássicas
z
D representa a informaç
informação rigorosa ou antecedente e W representa
a informaç
informação revogá
revogável.
z
As Teorias de Omissão estendem as teorias dadas por D usando as
regras de omissão W - extensões. Podem haver zero, uma ou mais
extensões.
Exemplo:
W = {a, ¬ b, ¬ c}
D= a:b
b
, a:c
c
z
Uma extensão conté
contém b, a outra conté
contém c.
z
Intuitivamente: Uma extensão é um conjunto de
crenç
crenças resultantes de D e W
13
Inteligência Artificial
Universidade da Madeira
Definição formal de Extensão:
z
Seja (D, W) uma Teoria de Omissões, S um conjunto de fó
fórmulas e
Γ(S ) o menor conjunto tal que:
1. W ⊆ Γ(S ) ,
2. Th(Γ
Th(Γ(S ) )= Γ(S ) ,
3. se A:B1, …, Bn/ C ∈ D, A ∈ Γ(S ) e para todo i (1≤
(1≤ i ≤ n) ¬ Bi ∉ S
, então C ∈ Γ(S ) ,
E é uma extensão de (D, W) se e só
só se E = Γ(S )
Exemplo:
z
Seja D = { ave (X) : voa (X) ∧ ¬ pinguim (X) / voa (X),
pinguim (X) : ¬ voa (X) / ¬ voa (X) }
W = { ave (Tweety), pinguim (Tweety) }
A única extensão neste caso será
será:
Th (W ∪ { ¬ voa (Tweety) }
14
Inteligência Artificial
Universidade da Madeira
Restrições:
z
A existência de extensões não é garantida.
z
Em algumas situaç
situações a Ló
Lógica de Omissões não nos fornece resultados
intuitivamente esperados.
z
Noutros, fornece conclusões demasiado fortes.
z
Estas dificuldades levaram a numerosas propostas de modificaç
modificação.
z
No entanto, Reiter provou que para teorias de omissões normais existem
sempre extensões e que estas são semisemi-monó
monótonas no seguinte sentido:
se E é uma extensão de uma teoria de omissões normal, (D, W), então a
teoria de omissões normal (D ∪ D’, W) onde D’ é um conjunto arbitrá
arbitrário de
omissões normais, possui uma extensão E’ tal que E ⊆ E’.
z
Infelizmente, a expressividade das teorias de omissões normais nem
nem
sempre é suficiente.
Extensões – Conclusões:
z
Podemos concluir que não existe nenhum processo iterativo que
permita construir uma extensão.
z
Cada pessoa tem de adivinhar o conjunto de frases E e,
posteriormente, verificar que satisfazem a definiç
definição.
z
A partir das extensões podemos definir as seguintes:
z
z
Semântica Cré
Crédula: As consequências da Teoria de Omissões são as
frases numa determinada extensão da Teoria.
Semântica Cé
Céptica: As consequências da Teoria de Omissões são as
frases pertencentes a todas as extensões da Teoria.
15
Inteligência Artificial
Universidade da Madeira
Lógica de Omissão - Conclusões
z
A Ló
Lógica de Omissão parece ser muito difí
difícil de trabalhar em ní
níveis
computacionais porque:
z
z
As extensões são conjuntos infinitos de fó
fórmulas
A definiç
definição de extensão é não construtiva
z
Na realidade, o raciocí
raciocínio de omissão de primeira ordem não é
sequer semisemi-decidí
decidível.
vel.
z
O raciocí
raciocínio de omissão é extremamente difí
difícil de implementar.
FIM PARTE 3
16
Inteligência Artificial
Universidade da Madeira
Introdução
à
Inteligência Artificial
Representação de Conhecimento
e
Inferência
Agenda
z
Parte 3
z Lógicas
Não Monótonas
z Mundo
Fechado (Closed
(Closed World Assumption)
Assumption)
z Lógica por Omissões (Ló
(Lógica Default)
Default)
z
Parte 4
z Mudanças
no Mundo e Revisão de Crenças
z Revisão
de Crenç
Crenças
z Cálculo Situacional
17
Inteligência Artificial
Universidade da Madeira
Cálculo Situacional
Como representar realmente as mudanças?
Exemplo: o agente foi de [1,1] para [1,2]
ª
Apagar da BC (Base de Conhecimento) sentenç
sentenças que já
já não são
verdade?
ª MAU! Perdemos o conhecimento sobre o passado, o que
impossibilita previsões de diferentes futuros
ª
Representar cada estado por uma BC diferente?
ª MAU! Pode explorar situaç
situações hipoté
hipotéticas, poré
porém não pode
raciocinar sobre mais do que uma situaç
situação ao mesmo tempo.
ª
Solução: Cálculo Situacional
ª
ª
Uma maneira de escrever mudanç
mudanças no tempo em LPO;
Representaç
Representação de diferentes situaç
situações na BC.
18
Inteligência Artificial
Universidade da Madeira
Cálculo Situacional
ªO
mundo consiste numa sequência
de situaç
situações.
Situaç
Situação NÎacç
acçãoÎ
ãoÎsituaç
situação N+1
ªPredicados
que mudam com tempo têm
o argumento situaç
situação adicional.
Em vez de:
Em(Agente,Local)
Em(Agente,Local)
teremos:
(Em(Agente,[1,1], S0, Em(Agente,[1,2],S1))
Cálculo Situacional
ª
Predicados que denotam propriedades que não mudam com o
tempo.
ƒ Não necessitam de argumentos de situaç
situação;
Exemplo no mundo wumpus:
wumpus:
parede(0,1) e parede(1,0)
ª
Para representar as mudanç
mudanças no mundo: Funç
Função Resultado
resultado(acç
resultado(acção,situaç
ão,situaçãoN)
ãoN)=situaç
=situação N+1
19
Inteligência Artificial
Universidade da Madeira
Exemplo de Cálculo Situacional
Descrição das acções no Cálculo
Situacional
ª
As acç
acções são descritas pelos seus efeitos.
ª Especificando as propriedades da situaç
situação resultante da
realizaç
realização da acç
acção;
ª Por meio dos axiomas de efeito e dos axiomas de frame.
frame.
ª
Axiomas de efeito: descrevem como o mundo muda.
ª O agente estará
estará segurando algo se ele acabou de pegá
pegá-lo
∀ x,s Presente(x,s)
Presente(x,s) ∧
Portá
Segurando(x,Resultado(Pegar,s))
))
Portável(x)=>
vel(x)=>Segurando(x,Resultado(Pegar,s
ª O agente não estará
estará segurando nada depois de realizar uma
acç
acção de Soltar.
∀ x,s ¬ Segurando(x,Resultado(Soltar,s))
Segurando(x,Resultado(Soltar,s))
20
Inteligência Artificial
Universidade da Madeira
Como descrever acções no
Cálculo Situacional?
ªO
problema é que o axioma do efeito diz o
que muda, mas não diz o que fica igual!
ª Representar
todas as coisas que ficam
iguais é o chamado “FRAME PROBLEM”.
“ Frame Problem”
z
É necessário encontrar uma solução
eficiente para representar as coisas que se
mantêm num mundo em mudança.
Uma forma de ultrapassar este problema é definir
axiomas de Frame.
21
Inteligência Artificial
Universidade da Madeira
“ Frame Problem”
ªAxiomas
ª
ª∀
de frame:
frame: descrevem como o mundo permanece igual.
Se o agente está
está segurando em algo e não o soltou, então
continua segurando.
a,x,s Segurando(x,s) ∧ (a ≠Soltar)
Soltar) =>Segurando(x,Resultado(a,s))
ª
∀a,x,s
Se o agente não esta segurando algo e não pegou em nada,
então continua com as mãos vazias.
¬ Segurando(x,s) ∧ (a ≠Pegar ∨ ¬(Presente(x,s) ∧Portá
Portável(x))
ª=>
¬ Segurando(x,Resultado(a,s))
“ Frame Problem”
ª Como
igual?
representar o que muda e o que fica
Axioma_efeito + Axioma_Frames = Axioma Estado-Sucessor
Descrição completa de como o mundo evolui.
ª Successor- State Axiom:
Action is possible Æ (Fluent is true in result state ⇔
Action’s effect made it true ∨ It was true before and
action left it alone).
ªÉ necessário escrever um axioma Estado-Sucessor para
cada predicado que pode mudar o seu valor no tempo.
22
Inteligência Artificial
Universidade da Madeira
Guardando localizações
ª
ª
ª
ª
ª
ª
O agente precisa saber por onde andou e o que viu.
O agente precisa saber:
ƒ
Localizaç
Localização inicial
Em (Agente,[1,1],S0)
ƒ
Orientaç
Orientação:
ão: a direcç
direcção do agente (em graus).
Orientaç
Orientação(Agente,S0) = 0
ƒ
Localizaç
Localização um passo à frente:
frente: funç
função de locais e orientaç
orientações.
∀ x,y Pró
PróximaLocalizaç
ximaLocalização([x,y],0)
ão([x,y],0) = [x+1,y]
∀ x,y Pró
PróximaLocalizaç
ximaLocalização([x,y],90)
ão([x,y],90) = [x,y+1]
∀ x,y Pró
PróximaLocalizaç
ximaLocalização([x,y],180)
ão([x,y],180) = [x[x-1,y]
∀ x,y Pró
PróximaLocalizaç
ximaLocalização([x,y],270)
ão([x,y],270) = [x,y[x,y-1]
FIM
23