Inteligência Artificial
Interpretação de linguagem humana
Você está em: MarMSX >> Cursos >> AI
No capítulo 5 vimos como "quebrar" a frase de uma linguagem humana em tokens (pedaços), identificar a classe gramatical de cada token, analisar a correção gramatical da frase (análise sintática) e verificar se a frase faz sentido ou não (análise semântica).
Esse capítulo extra tem como proposta apresentar algumas técnicas para auxiliar a identificar o sentido de uma frase.
Busca por palavras-chave
A busca por palavras-chave tenta identificar palavras em uma frase, texto ou que estejam contidas em um dicionário que faz parte da base de dados de um sistema.
Através da palavra-chave, podemos identificar, por exemplo, sua classe gramatical, entender seu significado, tomar decisões, buscar por palavras sinônimas ou até mesmo palavras correspondentes em outra língua (tradução).
Para entender como funciona a busca por palavras-chave, vejamos o programa a seguir. Ele contém uma base de dados com 15 nomes de jogos de MSX e a descrição correspondente de cada jogo.
10 SCREEN 0:WIDTH 40:KEY OFF:COLOR 15,0,0:MX=15
20 PRINT"Exemplo de busca por palavras-chave":GOSUB 500
30 PRINT:PRINT"Busca por jogo de MSX"
40 INPUT J$
50 I=1
60 IF J$=TB$(I,1) THEN PRINT TB$(I,1);" - ";TB$(I,2):GOTO 30
70 I=I+1
80 IF I>MX THEN PRINT"Nao encontrei o jogo.":GOTO 30
90 GOTO 60
500 ' Insere dados na memoria
510 DIM TB$(MX,2)
520 FOR I=1 TO MX
530 READ TB$(I,1):READ TB$(I,2)
540 NEXT I
550 RETURN
1000 ' Dicionario
1010 DATA "Aleste","Jogo de naves para MSX 1 e MSX 2"
1020 DATA "Soccer","Jogo de futebol da Konami"
1030 DATA "Matchday II","Jogo de futebol feito com sprites"
1040 DATA "Pitfall II","Jogo de labirinto"
1050 DATA "Arkanoid","Jogo de squash eletronico"
1060 DATA "Antartic Adventure","Jogo de pinguim"
1070 DATA "Penguin Adventure","Super jogo de pinguim"
1080 DATA "Zanac","Jogo de naves"
1090 DATA "Snake it","Jogo tipo Snafu que fala"
1100 DATA "Macattack","Jogo tipo Burgertime"
1110 DATA "Butragueno","Jogo de futebol"
1120 DATA "Hyper Sports","Jogo de esportes da Konami"
1130 DATA "Hyper Rally","Jogo de corrida da Konami"
1140 DATA "Wec Le Mans","Jogo de corrida de 24 horas de Le Mans"
1150 DATA "Aspar","Jogo de corrida de motos"
Exemplo de execução:
Exemplo de busca por palavras-chave
Busca por jogo de MSX
? Arnakoid
Arkanoid - Jogo de squash eletronico
Busca por jogo de MSX
? Jagur
Nao encontrei o jogo.
O programa apresentado cria uma tabela com duas colunas. Na primeira coluna, temos os nomes dos jogos, enquanto que na segunda coluna temos as descrições.
Quando o usuário insere um termo de busca, que é o nome de um jogo de MSX, o programa varre a primeira coluna da tabela em busca do nome solicitado. Se o encontra, retorna o nome do jogo com a sua descrição. Caso não encontre, imprime uma mensagem de erro.
A comparação de strings é sensível à caixa, ou seja, leva em consideração letras maiúsculas e minúsculas. Em outras linguagens, podemos ter toda nossa base de dados em caixa alta ou baixa e converter, através de uma função específica, a string de busca para o mesmo tipo de caixa da base de dado. Isto evitaria erros de comparação de termos iguais, como por exemplo, "Pingum veloz" sendo atribuído como diferente de "PINGUIM veloz".
O Basic do MSX não possui uma função nativa como um uppercase() ou lowcase() para converter strings para maiúsculo ou minúsculo. Dessa forma, é necessário criar uma, caso se deseje utilizar.
Podemos incluir nossa busca por palavras-chave na descrição do jogos. Assim, alteramos as linhas:
50 I=1:F=0
60 IF J$=TB$(I,1) OR INSTR(TB$(I,2),J$) THEN PRINT TB$(I,1);" - ";TB$(I,2):F=1
70 I=I+1
80 IF I>MX THEN IF F=0 THEN PRINT"Nao encontrei o jogo.":GOTO 30 ELSE GOTO 30
Agora listamos todas as ocorrências, em vez de parar na primeira ocorrẽncia.
Exemplo de uso:
Exemplo de busca por palavras-chave
Busca por jogo de MSX
? nave
Aleste - Jogo de naves para MSX 1 e MSX 2
Zanac - Jogo de naves
Silogismo
Dadas duas frases relacionadas entre si, o silogismo é capaz de deduzir uma terceira que contém informação não apresentada explicitamente à máquina [1].
Segundo Aristóteles, as regras que determinam a validade de um silogismo são [1]:
Premissa 1: A é um B
Premissa 2: C é um A
Conclusão: C é um B
Um exemplo seria:
Um canário é um pássaro
Um pássaro tem asas
Logo um canário tem asas
Vejamos como isso funciona na prática.
O programa a seguir analisa uma frase e primeiramente verifica se ela é uma afirmação ou pergunta (identificada pela presença do ponto de interrogação "?"). Em caso de pergunta, removemos o ponto de interrogação da frase.
Antes seguir viagem na avaliação da sentença, precisamos obter os termos A e B em separado da frase fornecida pelo usuário. Dessa forma, procuramos nessa frase por artigos, pronomes ou o verbo "ser" contidos em um dicionário (busca por palavras-chave), de forma a eliminá-los da sentença. Além disso, utilizamos esses mesmos elementos para determinar a fronteira entre os termos A e B da frase.
Exemplo:
Frase: "Um canario e' um passaro"
Dicionário: "o,a,os,as,um,uma,uns,umas,e'"
Análise:
"Um" - dic=1 - termo(1)=""
"canario" - dic=0 - termo(1)="canario"
"e'" - dic=1 - encerra termo(1) e inicia termo(2)=""
"um" - dic=1 - termo(2)=""
"passaro" - dic=0 - termo(2)="passaro"
Resultado:
termo(1): "canario"
termo(2): "passaro"
Quando o token analisado pertencer ao dicionário, NADA fazemos com o termo atual. Entretanto, quando o token NÃO pertencer ao dicionário, preenchemos o termo atual com esse token, até que um novo token do dicionário seja encontrado. Nesse caso, encerramos o termo atual e começamos o próximo.
Uma vez obtidos A e B, podemos:
- Caso a sentença seja uma afirmativa, inserir a relação em uma tabela.
- Caso a sentença seja uma pergunta, verificar se a relação existe na tabela.
Uma tabela de 25 linhas por 25 colunas é criada para guardar a relação entre os termos. A primeira linha de cada coluna armazena um termo e as demais linhas armazenam as relações.
Veja o exemplo a seguir:
Frase: "Um canario e' um passaro"
Tabela - termos reconhecidos
1 2
1 canario passaro
Tabela - termos e relações
1 2
1 canario passaro
2 passaro canario
Uma relação mais complexa:
Frases:
"Um canario e' um passaro"
"Um passáro e' voador"
"Um voador e' um cantor"
Tabela
1 2 3 4
1 canario passaro voador cantor
2 passaro canario passaro voador
3 voador cantor
Analisando os exemplos acima, basta que os termos A e B sejam encontrados ao mesmo tempo em qualquer coluna da tabela para que a pergunta seja verdadeira.
O programa é apresentado a seguir.
10 SCREEN 0:WIDTH 40:COLOR 15,0,0:KEY OFF:CLEAR 5000
20 PRINT"Silogismo":PRINT
30 PRINT"Entre com sentencas do tipo:"
40 PRINT"A e' B"
50 PRINT:PRINT"Por exemplo:"
60 PRINT"O gato e' um animal"
70 PRINT"Um animal e' peludo"
80 PRINT:PRINT"E o MSX aprende coisas com voce."
90 PRINT:PRINT"Quando inserimos uma pergunta com '?':"
100 PRINT"O gato e' peludo?"
110 PRINT"Perguntamos ao MSX e ele responde, se souber."
120 PRINT:PRINT
130 PRINT"Tente voce agora."
140 DIM M$(25,25)
200 ' Rotina principal
210 INPUT FR$
220 C=INSTR(FR$,"?"): IF C THEN Q=1:FR$=LEFT$(FR$,C-1) ELSE Q=0
230 GOSUB 1000 ' Obtem sentencas A e B
240 IF Q=0 THEN GOSUB 500 ELSE GOSUB 700
300 GOTO 210
500 '
510 ' Insere dados na matriz
520 '
530 IF SB$(1)=SB$(2) THEN PRINT SB$(1);" e' ";SB$(2);" nao faz sentido para mim.":RETURN
540 S=1
550 J=1 ' Procura sentenca
560 IF M$(1,J)="" THEN M$(1,J)=SB$(1):GOTO 590
570 IF M$(1,J)=SB$(1) THEN 590
580 J=J+1:IF J>25 THEN PRINT"Estou com a memoria cheia.":RETURN ELSE 560
590 I=1 ' Procura por correspondencia
600 IF M$(I,J)="" THEN M$(I,J)=SB$(2):GOTO 630
610 IF M$(I,J)=SB$(2) THEN PRINT"Isso eu ja sei.":RETURN
620 I=I+1:IF I>25 THEN PRINT"Estou com a memoria cheia.":RETURN ELSE 600
630 IF S<2 THEN S=S+1:SWAP SB$(1),SB$(2):GOTO550
640 PRINT"Ok.":RETURN
700 '
710 ' Analisa dados na matriz - procura por A e B na mesma coluna
720 '
730 F=0:FOR J=1 TO 25
740 IF M$(1,J)=SB$(1) OR M$(1,J)=SB$(2) THEN F=F+1
750 NEXT J
760 IF FS<2 THEN PRINT"Isso eu nao sei responder.":RETURN
770 J=1
780 I=1:F=0
790 IF M$(1,J)="" THEN PRINT"Nao.":RETURN
800 IF M$(I,J)=SB$(1) OR M$(I,J)=SB$(2) THEN F=F+1
810 IF F=2 THEN PRINT"Sim.":RETURN
820 IF M$(I,J)="" THEN J=J+1:GOTO 780
830 I=I+1
840 IF I>25 THEN J=J+1:GOTO 780
850 IF J>25 THEN PRINT"Nao.":RETURN
860 GOTO 800
1000 '
1010 ' Parsing - obtem sentenças A e B
1020 '
1030 S=1:S$="":DC$="e',o,a,os,as,um,uma,uns,umas,E',O,AS,OS,AS,UM,UMA,UNS,UMAS,"
1035 DC$=DC$+"Os,As,Um,Uma,Uns,Umas,sao,tem,SAO,TEM"
1040 IF LEN(FR$)=0 THEN IF S$<>"" THEN SB$(S)=S$:RETURN ELSE RETURN
1050 P=INSTR(FR$," "):IF P=0 THEN TK$=FR$:FR$="":GOTO 1070
1060 TK$=LEFT$(FR$,P-1):FR$=MID$(FR$,P+1,LEN(FR$)-P)
1070 IF INSTR(DC$,TK$) THEN SB=0 ELSE SB=1
1080 IF SB=0 AND S$<>"" THEN SB$(S)=S$:S$="":S=S+1
1090 IF SB=1 THEN IF S$="" THEN S$=TK$ ELSE S$=S$+" "+TK$
1100 GOTO 1040
Exemplos para testar o programa:
Tente voce agora.
? Um canario e' um passaro
Ok.
? Um passaro tem pelo
Ok.
? O canario tem pelo?
Sim.
? O cachorro e' um animal
Ok.
? E' um passaro o cachorro?
Não.
? O cachorro tem pelo
Ok.
? E' um passaro o cachorro?
Sim.
Observamos pelo exemplo acima, que, no silogismo, basta um elemento de ligação para uma sentença ser verdadeira. Quando dissemos que o cachorro tem pelo, ele o ligou ao pássaro.
Tradutor
O tradutor é uma das aplicações da busca por palavras-chave. Nesse caso, procuramos por alguns termos e seus correspondentes em outra língua. Um parsing (analisador de frases) é utilizado, de forma a encontrar os termos separados por espaços em branco.
O programa a seguir traduz uma frase do português para o inglês. Um arquivo de dicionário com 190 termos foi criado, onde em cada linha contém um termo em português e o seu correspondente em inglês, separados por vírgula.
10 SCREEN 0:WIDTH 40:KEY OFF:COLOR 15,0,0:CLEAR 5000
20 ' Lê dicionario
30 DIM DI$(200,2):PRINT"Lendo dicionario ...":N=194
40 OPEN"DIC_PTEN.DAT" FOR INPUT AS #1
50 FOR I=1 TO N
60 INPUT #1,DI$(I,1):INPUT #1,DI$(I,2)
70 NEXT I:CLOSE1
80 PRINT:PRINT"Entre com uma frase em portugues":PRINT
100 ' Loop
110 INPUT FR$
120 IF FR$="" THEN PRINT:GOTO 110
130 P=INSTR(FR$," ")
140 IF P THEN TK$=LEFT$(FR$,P-1):FR$=MID$(FR$,P+1,LEN(FR$)-P) ELSE TK$=FR$:FR$=""
150 GOSUB 500 ' Busca traducao
160 PRINT TK$;" ";
170 GOTO 120
500 ' Procura pelo termo
510 I=1
520 IF TK$=DI$(I,1) THEN TK$=DI$(I,2):RETURN
530 I=I+1
540 IF I>N THEN RETURN ELSE 520
Obs: o arquivo de dicionário pode ser obtido aqui.
Exemplos de uso:
Entre com uma frase em portugues
? EU QUERO COMER UMA MACA
I WANT TO EAT A APPLE
? PAOLA AMA CACHORRO
PAOLA LOVES DOG
? MEU PAI COME PIPOCA
MY FATHER EATS POPCORN
? A BOLA E' VERDE
THE BALL IS GREEN
Obs: utilizar sempre letras maiúsculas.
É evidente que falta muita coisa ainda para o tradutor se tornar eficiente. Por exemplo, ele não é capaz de trabalhar com contextos, plurais, conjugações etc.
Como vimos no exemplo da MACA, o tradutor não é capaz de identificar que um substantivo começando por uma vogal em inglês deve ter um "AN" em vez de "A".
Acelerando a pesquisa com "busca binária"
Podemos acelerar a busca por palavras-chave utilizando o mecanismo de busca binária. Para isso, devemos classificar o dicionário em ordem alfabética.
Este mecanismo consiste em dividir inicialmente todo o espaço de busca pela metade. Então, compara-se a palavra pesquisada com o elemento central do vetor dicionário. Caso seja igual, pára a busca e retorna. Senão, verifica se a palavra buscada está na metade inferior ou superior à palavra central. Dessa forma, continuamos a busca na metade onde a palavra provavelmente está e eliminamos a outra metade.
Repetimos o procedimento de divisão do vetor resultante pela metade até que não reste elementos ou a palavra seja encontrada.
O código modificado no programa anterior é apresentado a seguir.
500 ' Procura pelo termo - busca binária
510 PI=1:PF=N
520 I=INT((PI+PF)/2)
530 IF TK$=DI$(I,1) THEN TK$=DI$(I,2):RETURN
540 IF TK$<DI$(I,1) THEN PF=I-1 ELSE PI=I+1
550 IF PF<PI THEN RETURN ELSE 520
Sinônimos
Se você teve a curiosidade de olhar o arquivo de dicionário do tradutor, pôde observar que há diversos termos que possuem o mesmo correspondente em inglês.
Podemos simplificar um dicionário de correspondências, criando um dicionário extra de sinônimos. Nesse dicionário, cada linha possui os termos sinônimos.
No exemplo da seção anterior, temos um dicionário utilizando o seguinte modelo:
Tabela
1 2
1 COMO EAT
2 COMEMOS EAT
3 COMEM EAT
4 QUERO WANT
5 QUEREMOS WANT
6 QUEREM WANT
Poderemos simplificá-lo da seguinte forma:
Tabela sinonimo
1 2 3
1 COMO COMEMOS COMEM
2 QUERO QUEREMOS QUEREM
Tabela traducao
1
1 EAT
2 WANT
Assim, quando eu desejar procurar por um termo, primeiro procuro ele na tabela "sinonimo". O índice da linha onde esse termo for encontrado é utilizado para encontrar a tradução correspondente na tabela "traducao".
Diálogo com o MSX
A última seção desse capítulo extra, vamos analisar um famoso programa feito originalmente em Basic para dialogar com humanos: o Eliza Doctor. O programa foi criado entre 1964 e 1966 pelo professor de Ciência da Informática no Massachussetts Institute of Technology, Joseph Weizenbaum [1], com o intuito de desempenhar o papel de um psicólogo.
Como funciona o programa
O usuário digita uma frase e o programa varre esta frase em busca de uma sentença (palavra-chave) que esteja em sua base de dados, como por exemplo "COMO", "NAO SEI" ou "AMIGO". Para cada sentença, há um grupo de frases associadas para serem enviadas como resposta. Por exemplo:
Sentença encontrada na frase do usuário: AMIGO
Respostas do computador para esta sentença:
1. POR QUE SE REFERE AO PROBLEMA DE SEU AMIGO?
2. QUAL A SUA MELHOR RECORDACAO DE UM AMIGO?
3. POR FAVOR, DIGA-ME MAIS SOBRE ESSA AMIZADE...
Então, o computador escolhe aleatoriamente uma das respostas disponíveis e escreve para o usuário. Se a sentença do usuário não estiver no base de dados do programa, ele recorre a dois artifícios:
- Utiliza uma frase do próprio usuário armazenada no sistema, de forma a construir uma pergunta em cima dela.
- Utiliza uma frase genérica, a partir de um conjunto de frases genéricas criadas para esse fim.
No primeiro caso, o programa extrai de uma frase do usuário um determinado trecho "K$" e armazena na memória. A extração de um trecho é feita com base na presença de um pronome possessivo na frase do usuário como MEU, MEUS, MINHA, MINHAS. Por exemplo, na frase:
EU SAI ONTEM COM MINHA NAMORADA
O trecho "K$" extraído seria: "MINHA NAMORADA".
A partir disso, seleciona uma das frases disponíveis para esse caso e adiciona o trecho K$ com o pronome corrigido.
"FALE-ME MAIS SOBRE " + K$
"REFERIU-SE A " + K$ + ". FALE-ME MAIS SOBRE O ASSUNTO"
"ISSO TEM ALGO A VER COM " + K$ + "?"
"EXISTE ALGUMA RELACAO ENTRE ISSO E " + K$ + "?"
"POR QUE NAO VOLTAMOS ATRAS E DISCUTIMOS SOBRE " + K$ + " UM POUCO MAIS?"
"PENSA HAVER ALGUMA RELACAO ENTRE ISSO E " + K$ + "?"
"PREFERE FALAR SOBRE " + K$
"PENSO QUE TALVEZ SE DEIXE ARRASTAR PELAS PREOCUPACOES QUANTO " + K$ + "..."
Por exemplo, o programa poderia sortear aleatoriamente a segunda frase. Então a resposta ficaria:
REFERIU-SE A SUA NAMORADA. FALE-ME MAIS SOBRE O ASSUNTO
Obs: mais adiante falaremos sobre a troca do pronome possessivo de K$.
Já a outra estratégia seleciona aleatoriamente uma frase genérica:
QUE LHE SUGERE ISSO?
NAO TENHO CERTEZA DE ESTAR COMPREENDENDO ISSO
POR FAVOR, ESCLARECA-ME MELHOR
ISSO E' MUITO INTERESSANTE
BOM... POR FAVOR, CONTINUE...
POR QUE?
E DEPOIS ?
COMPREENDO... DIGA-ME MAIS SOBRE ISSO.
  O uso de uma dessas estratégias é feito aleatoriamente.
Algumas frases de resposta possuem um asterisco "*" no final. Esse asterisco indica ao programa que inclua o trecho "K$" extraído da frase do usuário. Exemplo:
Palavra chave: VOCE E'
Uma das respostas: POR QUE PENSA QUE SOU*
Quando utilizamos essa palavra chave:
? VOCE E' INTELIGENTE
POR QUE PENSA QUE SOU INTELIGENTE
O programa ainda possui um dicionário para a troca de termos equivalentes, com o intuito de mudar a pessoa da frase do usuário. Por exemplo:
Usuário: EU SOU ALTO
Computador: VOCE E' ALTO
Dicionário:
SOU,SAO
ERA,ERAM
EU,VOCE
MEU,SEU
TEM,TENHO
SEU,MEU
SAO,SOU
MEUS,SEUS
SEUS,MEUS
MINHA,SUA
SUA,MINHA
MINHAS,SUAS
SUAS,MINHAS
E',SOU
SEU,MEU
VOCE,EU
EU,VOCE
O programa "elizadr.bas" [1], adaptado para o MSX por mim, mais os dados "eliza.dat" pode ser obtidos aqui.
Alguns exemplos de diálogo [1]:
O DOUTOR ESTA'...
POR FAVOR, PREPARE-SE...
BEMVINDO A OUTRA SESSAO COM O DOUTOR...
OLA'...
? OLA
OLA... PRAZER EM VE-LO!
? TENHO UM PROBLEMA GRAVE
COMO O PODEREI AJUDAR NISSO?
? TEM A VER COM O MEU PROFESSOR MALUCO
COMPREENDO, O SEU PROFESSOR MALUCO
? ISSO
ISSO E' MUITO INTERESSANTE
? TENHO PENSADO NO ASSUNTO DIA E NOITE
E' OBVIO QUE TEM PENSADO NO ASSUNTO DIA E NOITE
? TUDO COMECOU QUANDO EU TINHA DEZ ANOS DE IDADE
MUITO INTERESSANTE
? AGORA TENHO MEDO DE IR A ESCOLA
VEIO FALAR COMIGO PORQUE TEM MEDO DE IR A ESCOLA AGORA
Podemos aumentar a base de dados desse programa, acrescentando novos termos no dicionário e novos diálogos.
Download
ling.zip - programas e dados desse capítulo.
Referências
1. Inteligência Artificial no Seu Spectrum e Spectrum +, T. Hartnell. Editorial Presença, Portugal, 1984.