Processamento de
Linguagem Natural
Ilson Wilmar Rodrigues Filho, Dr.
http://www.inf.ufsc.br/~ilson
[email protected]
João Bosco da Mota Alves, Dr.
[email protected]
Bibliografia
BARROS, F. A.; ROBIN, J. – Processamento de Linguagem Natural.
Departamento de Informática, Universidade Federal de Pernambuco,
Recife, março de 1997.
FERNANDO, P.; MENEZES, B. – Linguagens Formais e Autômatos.
Porto Alegre: Instituto de Informática da UFRGS: Sagra Luzzatto Editores,
1997.
GAL, A.; LAPALME, G. – Prolog for Natural Language Processing. John
Wiley & Sons Ltd., 1991.
GAZDAR, G.; MELLISH, C. – Natural Language in Prolog. AddisonWeslwy Publishing Company, 1989,
JOSÉ NETO, J. – Introdução à Compilação. Rio de Janeiro. LTC – Livros
Técnicos e Científicos Editora S. A., 1987.
Bibliografia
MONARD, M. C. & NICOLETTI, M. do C. – Programas Prolog para
Processamento de Listas e Aplicações, Janeiro de 1993 – Versão 2.0
MOREIRA, N. – Processamento de Linguagem Natural, Mestrado de
Lingüística Portuguesa Descritiva, Faculdade de Letras da Universidade
do Porto
NUNES, M. das G. V. at al. – Introdução ao Processamento das Línguas
Naturais. São Carlos: Notas Didáticas do ICMC No. 38, Instituto de
Ciências Matemáticas e de Computação, 1999.
PINERO, R. B. – Lenguajes Formales y Autómatas. Centro de
Inteligencia Artificial, Instituto Tecnológico y de Estudios Superiores de
Monterrey. Enero de 1997.
TOWSEND, C. – Técnicas Avançadas em Turbo Prolog, Rio de Janeiro:
Editora Campus, 1990.
Avaliação
Exercícios para serem resolvidos individualmente e um
trabalho (que pode ser feito em grupo) que deve ser
entregue no dia da apresentação (seminário).
Média Final = N1 x 0.4 + N2 x 0.3 + N3 x 0.3
onde:
N1 = Média Aritmética dos exercícios
N2 = Nota do Trabalho
N3 = Nota da Apresentação do trabalho (seminário)
Processamento de Linguagem
Natural
O processamento de linguagem natural
é o estudo dos sistemas
computacionais para compreensão e
geração de línguas naturais faladas e
escritas.
Divisões do PLN
• lingüística computacional ou
processamento de linguagem natural:
tratamento da língua escrita.
• reconhecimento e síntese de voz: tratamento
da língua falada.
Outras Denominações
 Processamento
de Linguagem Natural:
Inteligência Artificial
 Lingüística Computacional: Lingüística
 Outros termos propostos: Processamento
Computacional das Línguas, Engenharia da
Linguagem. Especificamente para a língua
portuguesa tem sido sugerido: Processamento
Computacional do Português,
Processamento Computacional da Língua
Portuguesa.
Histórico
 PLN
nasceu com o computador:
 2a Guerra: militares americanos tinham
interesse de traduzir automaticamente
conversações gravadas dos russos;
 A comunidade científica precisava de
traduções de trabalhos estrangeiros - a cada
dia fazia-se novas descobertas científicas.
Tradução Automática
 A possibilidade
de fazer tradução
automática de publicações sobre tecnologia
e ciência deixou os cientistas animados.
Essa foi uma das razões para que
pesquisas fossem financiadas na área.
Primeiros Sistemas de PLN
 Primeiros
trabalhos sobre PLN:
 tradução automática - começaram em
1946. Eram trabalhos sobre tradução
russo-inglês.
 tradução palavra por palavra;
 traduções: listas de palavras
chaves.
Histórico
1948: Preocupação com as regras de
construção de frases foi levada em
consideração (num trabalho do inglês
Pichens).
 Primeiro congresso sobre tradução
automática foi realizado no ano de 1952,
nos EUA, no MIT – Massachusetts Institute
of Technology com a participação de 18
pesquisadores.

O Relatório ALPAC

Relatório ALPAC (Automatic Language
Processing Advisory Comitee) - relatório
encomendado pelo governo norteamericano à Academia de Ciências daquele
país sobre as pesquisas em tradução
automática. O relatório publicado em 1966
teve um teor fortemente negativo que
provocou o corte das verbas de
financiamento
Renascimento do Interesse na
Tradução Automática

Anos 80: renascimento do interesse na
tradução automática, na Europa, em função
da criação da Comunidade Européia.
 1982: projeto EUROTRA - sistema de
tradução automática para nove línguas
de países que constituíam a Comunidade
Européia.
Modelos Conceituais
Modelos formais ou modelos
baseados em regras;
 Modelos estatísticos;
 Modelos conexionistas

Áreas de Aplicação de técnicas
de PLN
(1) Acesso a banco de dados;
(2) Recuperação de informação;
(3) Extração de informação;
(4) Tradução automática;
(5) Geração de resumos.
Acesso a Banco de Dados
 Acesso
a banco de dados são feitos
usualmente utilizando-se “query languages”
Recuperação de Informação
Recuperação de Informação é o estudo e
desenvolvimento de técnicas que permitam
encontrar documentos relevantes de uma
coleção de documentos.

Recuperação de Informação
Extração de Informação
Na extração de informação procura-se por
informações diretamente nos textos ,
mostrando a informação ao invés de
documentos.
 Técnicas utilizadas: baseadas na busca de
determinadas palavras chaves (denominadas de
tags), tais como
- Nome de pessoas
- Nome de empresas;

Tradução Automática

Tradução automática é a tradução por
computador de frases dadas numa língua para
outra língua.

Os primeiros trabalhos utilizavam
dicionários bilingües e faziam tradução
palavra a palavra.
A teoria lingüística começou a ser incorporada
nos sistemas de tradução automática com os
trabalhos de Noam Chomsky.

Gramática
 Segundo Chomsky, o conhecimento que o falante de
uma língua natural teria da mesma poderia ser
descrita através de um conjunto finito de regras.
 Tais regras seriam universais, ou seja, valeriam
para todas as línguas. Elas poderiam gerar um
número infinito de frase de uma língua.
 Uma frase seria gramatical (pertencente à língua)
ou agramatical (não pertencente à língua).
Problemas em Processamento
de Linguagem Natural

Homonímia Lexical: um exemplo clássico
é: manga = parte de uma peça de vestuário
destinada a cobrir os braços / manga = fruto
da mangueira
Problemas em Processamento
de Linguagem Natural

Ambigüidade sintática: a sentença aceita
duas análises sintáticas diferentes. Exemplo:
Viajando pela primeira vez para a
Europa, cruzei com um grupo de jovens
brasileiros.
Quem viajou pela primeira vez? Eu ou o
grupo de jovens brasileiros?
Problemas em Processamento
de Linguagem Natural
 Ambigüidade de Escopo: Percebe-se às vezes que a
sentença indica dois ou mais escopos. Exemplos:
Apesar de ser exímio advogado, o procurador da
Universidade não cumpre todas as disposições
estatutárias.
Essa sentença poderia significar que:
- O procurador descumpre todas as disposições (Descumpre todas = tem por norma violar a legislação)
 O procurador cumpre as disposições, mas não todas
(não tem por norma violar a legislação, mas comete
falhas).
Problemas em Processamento
de Linguagem Natural

Diferentes correferências possíveis: é a
compatibilidade de um anafórico com dois
ou mais antecedentes distintos, também
chamada de ambigüidade anafórica.
Exemplo: O ladrão entrou na casa do prefeito
e tirou toda a sua roupa.
Conhecimento do Mundo
 A compreensão da linguagem natural implica num
determinado grau de conhecimento do mundo.
Exemplo: "as mães com filhos menores de dez anos".
Tal expressão poderia er as seguintes representações
lógicas:
1. {x | З y, M(x,y) ^ i(y) < 10};
2. {x | З y, M(x,y) ^ i(x) < 10};
3. {x | З (y,z), M(x,y) ^ M(x,z) ^ i(y) < 10} ^ i(x) < 10}
onde: M(x,y) significa x é mãe de y;
i(x) significa idade de x;
i(y) significa idade de y.
Fases do Desenvolvimento de
um Sistema de PLN
(1) Análise morfológica;
(2) Análise Sintática;
(3) Análise Semântica;
(4) Análise do Discurso;
(5) Análise Pragmática.
Análise Morfológica

É o estudo da estrutura e da classificação
das palavras em função do uso:
substantivos
artigos
adjetivos
pronomes
verbos
numerais
advérbios
preposições
conjunção
interjeição
Regras morfológicas
 As línguas naturais possuem regras morfológicas
que produzem as possíveis variantes de cada
palavra. Exemplo:
construir tem como variantes, entre outras,
construção e construído.
Um pedaço da palavra (constru) se repete nas
demais, que receberam a aposição do que
chamamos de sufixos. Este pedaço de palavra que
se mantém nas variantes, chamamos de lexemas.
Análise Sintática

É o estudo das unidades básicas da
linguagem - as sentenças.

Na fase da análise sintática, o sistema de
processamento de linguagem natural
verifica se a seqüência das palavras nas
sentenças são válidas para a gramática
utilizada.
Análise Semântica

Durante a análise semântica, utiliza-se a estrutura
gerada durante a análise sintática para construir
outras estruturas que representem o significado das
sentenças.

Formalismos utilizados nesta fase do
processamento de linguagem natural podem ser
classificados em fracos e fortes:
 Formalismos fracos: redes semânticas e
frames;
 Formalismos fortes: gramáticas de
casos, dependência conceitual e scripts.
Análise do Discurso

Análise do discurso é a identificação da
estrutura do discurso. O discurso é também
organizado em unidades constituídas por um
mais elementos denominados segmentos do
discurso.
Análise Pragmática

Na análise pragmática são estudados os
enunciados, ou seja, os significados das
frases, sob o ponto de vista dos
interlocutores. Esta análise é de suma
importância principalmente nos diálogos
onde é preciso determinar as intenções dos
interlocutores.
Fundamentos Matemáticos
para o Processamento de
Linguagem Natural
Conjuntos
 Conjunto é uma coleção de objetos, distintos, de
qualquer espécie (definição intuitiva).
 Aos objetos do conjunto
denominamos elementos do conjunto.
 Os elementos do conjunto
distinguem-se uns dos outros, ou
seja, não há repetição de
elementos no conjunto.
Relação de Pertinência entre
Elemento e Conjunto
 Vamos supor o conjunto das vogais::
V = {a,e,i,o,u}
 Para indicar que u pertence ao conjunto V e
que b não pertence, escrevemos:
u  V
b  V
Relação de Pertinência entre
Elemento e Conjunto
 Em Prolog, vamos utilizar listas:
V = [a,e,i,o,u]
pertence(u,[a,e,i,o,u]).
not(pertence(b,[a,e,i,o,u]).
Listas
 Uma lista em Prolog é uma coleção de elementos
separados por vírgulas e dentro de colchetes. O
primeiro elemento da lista é denominado cabeça de
lista e os demais elementos formam uma lista
denominada cauda da lista.
A Relação pertence/2
 a relação pertence/2 pode ser estabelecida
através de duas regras:
(1) Um objeto pertence a uma lista se ele for
a cabeça da lista;
(2) Um objeto pertence a uma lista se ele
pertence à cauda da lista.
pertence/2 em Visual Prolog
Domains
stringlist = string*
Predicates
nondeterm pertence(string,stringlist)
Clauses
pertence(X,[X|_]).
pertence(X,[_|T]):pertence(X,T).
pertence/2 - Exemplos
 Goal pertence(u,[a,e,i,o,u]).
yes
 Goal not(pertence(b,[a,e,i,o,u])).
yes
pertence/2 - Exemplos
 Se quisermos saber quais os objetos de um
dado conjunto (por exemplo: [a,e,i,o,u]),
perguntaríamos em Prolog:
Goal pertence(X,[a,e,i,o,u]).
X=a
X=e
X=i
X=o
X=u
5 Solutions
Conjunto Vazio
 Um conjunto sem objetos, denominado
conjunto vazio, é denotado por {} ou .
Para utilização de Prolog vamos representar
o conjunto vazio por [], ou seja,
 = []
Subconjunto
 Um dado conjunto A é subconjunto de B
se e somente se todo elemento de A
pertence também a B, que se representa
como:
A  B
e dizemos que o conjunto A está contido no
conjunto B, ou ainda que B contém A:
B  A
Subconjunto
em Prolog, teremos:
esta_contido(A,B).
contem(B,A).
esta_contido/2
Domains
stringlist = string*
Predicates
nondeterm esta_contido(stringlist,stringlist
nondeterm pertence(string,stringlist)
Clauses
esta_contido([],_).
esta_contido([H1|T1],L2):pertence(H1,L2),
esta_contido(T1,L2).
esta_contido/2 - Exemplos
Goal esta_contido([],[c,b,a]).
yes
Goal esta_contido([a,b],[c,b,a]).
yes
Goal esta_contido([a,b],[b,a]).
yes
Goal esta_contido([b,a],[c,b,a]).
yes
contem/2
Domains
stringlist = string*
Predicates
nondeterm contem(stringlist,stringlist)
nondeterm esta_contido(stringlist,stringlist)
Clauses
contem(B,A):esta_contido(A,B).
contem/2 - Exemplos
Goal contem([a,b],[]).
yes
Goal A = [a], B = [a,e,i,o,u],
contem(B,A).
A = [a]
B = [a,e,i,o,u]
yes
eh_subconjunto/2
 Para verificar se um conjunto A é subconjunto de um
conjunto B podemos criar o predicado
eh_subconjunto/2, que responda sim ou não (yes/no)
caso A seja subconjunto ou não de B. Basta utilizar
uma das relações definidas (esta_contido/2 ou
contem/2)
Igualdade de Conjuntos
 Dois conjuntos A e B são iguais quando
qualquer elemento que pertence a A
pertence também a B e vice-versa (todo
elemento que pertence a B pertence também
a A), isto é: A = B, se, e somente se,
A  B e B  A.
igual/2
Predicates
nondeterm igual(stringlist,stringlist)
Clauses
igual(A,B):esta_contido(A,B),
esta_contido(B,A).
igual/2 - Exemplos
Goal A = [a,b,c], B = [b,c,a],
igual(A,B).
A = [a,b,c]
B = [b,c,a]
1 Solution
Goal igual([a,b,c],[b,a,c]).
yes
OBS: Note-se pelos exemplos acima que a ordem dos
elementos dentro do conjunto não importa. Dados dois
conjuntos, se eles tiverem os mesmos objetos, eles são
considerados iguais.
Conjunto Potência
 Seja A um conjunto. Definimos como
conjunto potência de A ou conjunto das
partes de A, ao conjunto cujos elementos
são os subconjuntos de A. Sua denotação é:
2A. Assim:
2A = {S | S  A}
subconjunto/2
 Para definir em Prolog um predicado que
dê todos os subconjuntos de um conjunto
dado formando o seu conjunto potência,
vamos definir um predicado que gere
subconjuntos que vamos denominar de
subconjunto/2.
subconjunto/2 - regras
1 - Se A é um conjunto vazio ele só pode gerar um
conjunto vazio B;
2 - Se o primeiro elemento do conjunto A estiver
também no subconjunto B (vamos colocá-lo na
cabeça de B, pois como não importa a ordem dos
elementos de um conjunto vamos escolher esta
ordem preferencialmente), então a cauda de B é
subconjunto da cauda de A;
3 - Se o primeiro elemento do conjunto A não está no
subconjunto gerado B, então B é um subconjunto da
cauda de A.
subconjunto/2 - regras
 Esta três regras são escritas da seguinte maneira
em Prolog:
(1) subconjunto([],[]).
(2) subconjunto([CabecaA|CaudaA],[CabecaA|CaudaB]):subconjunto(CaudaA,CaudaB).
(3) subconjunto([_|CaudaA],ConjuntoB):subconjunto(CaudaA,ConjuntoB).
subconjunto/2 - regras em
Visual Prolog
Predicates
nondeterm subconjunto(stringlist,stringlist)
Clauses
subconjunto([],[]).
subconjunto([CabecaA|CaudaA],[CabecaA|CaudaB]):subconjunto(CaudaA,CaudaB).
subconjunto([_|CaudaA],ConjuntoB):subconjunto(CaudaA,ConjuntoB).
subconjunto/2 - Exemplo
Goal subconjunto([a,s,d],SUB).
SUB = [a,s,d] ;
SUB = [a,s] ;
SUB = [a,d] ;
SUB = [a] ;
SUB = [s,d] ;
SUB = [s] ;
SUB = [d] ;
SUB = '[]' ;
8 Solutions
Conjunto Potência
 O conjunto potência que é o conjunto formado por
todos os subconjuntos de um dado conjunto poderá ser
agora definido como:
Domains
stringlist = string*
llstring = stringlist*
Predicates
nondeterm potencia(stringlist,llstring)
Clauses
potencia([],[[]]).
potencia(A,P):findall(X,subconj(A,X),P).
Conjunto Potência - Exemplo
Goal potencia([a,s,d],P).
P = [[a,s,d],[a,s],[a,d],[a],[s,d],[s],[d],'[]']
1 Solution
Número de Elementos do
Conjunto Potência
 O número de elementos do conjunto das
partes de um conjunto (ou conjunto
potência) de n elementos é 2n.
 Se A tiver 3 elementos, o conjunto das
partes de A terá 23 = 8 elementos.
Exercício
 Determinar
em Visual Prolog o
tamanho do conjunto potência
definindo o predicado tamanho/2
Solução
Predicates
tamanho(llstring,integer)
Clauses
tamanho([],0).
tamanho([_|Cauda],TAM):tamanho(Cauda,TamCauda),
TAM = TamCauda + 1.
Operações com Conjuntos

Com conjuntos pode-se executar
algumas operações básicas tais como:
união;
intersecção;
diferença..
União de Conjuntos

Dados dois conjuntos A e B, a união
destes conjuntos, é o conjunto formado
com todos os elementos que pertencem
a A ou a B.
 A união
é representada por:
A  B
União de Conjuntos - Regras
1. A união de um conjunto vazio com um conjunto
qualquer A é o próprio conjunto A;
2. Dados dois conjuntos A e B, se a cabeça de A também
pertence a B a união de A com B será igual à união da cauda de
A com B pois como a cabeça de A também pertence a B, este
elemento aparecerá no conjunto formada pela união de B com a
cauda de A;
3. Se a cabeça de A não pertencer a B o conjunto união terá
como cabeça a cabeça de A e como cauda a união da cauda de
A como o conjunto B.
Exercício
 Construir
em Prolog as regras que
definem a união de dois conjuntos
Solução
Predicates
nondeterm uniao(stringlist,stringlist,stringlist).
Clauses
uniao([],C,C).
uniao([CabecaA|CaudaA],ConjuntoB,ConjuntoUniao):pertence(CabecaA,ConjuntoB),!,
uniao(CaudaA,ConjuntoB,ConjuntoUniao).
uniao([CabecaA|CaudaA],ConjuntoB,[CabecaA|CaudaUniao]):not(pertence(CabecaA,ConjuntoB)),
uniao(CaudaA,ConjuntoB,CaudaUniao).
União de Conjuntos - Exemplos
Goal uniao(["3","5","7"],["1","2","4","6"],UNIAO).
UNIAO = ["3","5","7","1","2","4","6"]
1 Solution
Goal uniao(["1","2","3"],["2","3","4","5"],U).
U = ["1,"2","3","4","5"]
i Solution
Intersecção de Conjuntos
 Dados dois conjuntos A e B, a intersecção
de A e B é o conjunto formado com os
elementos que pertencem a ambos ao
mesmo tempo. A intersecção é indicada por:
A  B
Intersecção de Conjuntos Regras
1. A interseção de um conjunto vazio com um
conjunto qualquer, é um conjunto vazio;
2. Dados dois conjuntos A e B, se a cabeça de A
também pertencer a B, o conjunto interseção
também terá como cabeça, a mesma cabeça de A, e
a sua cauda será formada pela interseção da cauda
de A com o conjunto B;
3. Se a cabeça do conjunto A não pertence ao
conjunto B, então, o conjunto interseção será obtido
pela interseção da cauda de A com o conjunto B.
Exercício

Construir em Prolog, as regras que
determinam a intersecção de
conjuntos.
Solução
Domains
stringlist = string*
Predicates
nondeterm intersecao(stringlist,stringlist,stringlist)
Clauses
intersecao([],_,[]).
intersecao([Cabeca_A|Cauda_A],Conjunto_B,[Cabeca_A|Cauda_Intersecao]):pertence(Cabeca_A,Conjunto_B),!,
intersecao(Cauda_A,Conjunto_B,Cauda_Intersecao).
intersecao([Cabeca_A|Cauda_A],Conjunto_B,Intersecao):not(pertence(Cabeca_A,Conjunto_B)),
intersecao(Cauda_A,Conjunto_B,Intersecao).
Diferença de Conjuntos
 Dados dois conjuntos A e B, denomina-se
diferença A - B ao conjunto formado pelos
elementos de A menos os elementos que
pertencem ao mesmo tempo a A e a B.
 Sejam A = {a,b,c,d,e} e B = {a,e,i,o,u}.
A - B = {b,c,d}.
Diferença de Conjuntos
Regras
1. A diferença entre um conjunto vazio e um conjunto
qualquer, é um conjunto vazio;
2. Dados dois conjuntos quaisquer A e B, se a cabeça de
A não pertencer a B, o conjunto diferença também terá
como cabeça, a mesma cabeça de A, e a sua cauda será
formada pela diferença entre a cauda de A com o
conjunto B;
3. Se a cabeça do conjunto A pertencer também ao
conjunto B, então, o conjunto diferença será obtido pela
diferença da cauda de A com o conjunto B (porque este
elemento será eliminado não fazendo parte do conjunto
diferença).
Exercício
 Construir
em Prolog as regras que
definem a diferença de dois
conjuntos
Solução
Predicates
nondeterm diferenca(stringlist,stringlist,stringlist)
Clauses
diferenca([],_,[]).
diferenca([Cabeca_A|Cauda_A],Conjunto_B,[Cabeca_A|Cauda_Diferenca]):not(pertence(Cabeca_A,Conjunto_B)),
diferenca(Cauda_A,Conjunto_B,Cauda_Diferenca).
diferenca([Cabeca_A|Cauda_A],Conjunto_B,Diferenca):pertence(Cabeca_A,Conjunto_B),
diferenca(Cauda_A,Conjunto_B,Diferenca).
Complemento
 Dados dois conjuntos A e B, denominamos
complemento de B em relação a A ao
conjunto
A – B = {x|x Є A e x  B}
 Se tivermos por exemplo os seguintes
conjuntos A = {a,s,d,f,g] e B = {d,f,h,j},
então:
A – B = {a,s,g} e B – A = {h}
Exercício
 Construir
em Prolog as regras que
definem o complemento de B em
relação a A.
Solução
Predicates
nondeterm complemento(stringlist,stringlist,stringlist)
Clauses
complemento(B,A,C):diferenca(A,B,C).
Par Ordenado
 Par ordenado é o par formado por dois
elementos de maneira que cada um deles
deve manter a sua posição em relação ao
outro, ou seja, o primeiro elemento do par
será sempre o da esquerda e o segundo
elemento do par será o da direita.
 se os elementos a e b formam um par
ordenado teremos:
(a,b)
Produto Cartesiano
 Sejam os conjuntos A e B. Podemos formar
com os elementos dos conjuntos A e B, um
conjunto de pares ordenados de forma que o
primeiro elemento do par seja do conjunto
A e o segundo elemento do conjunto B.
 A este conjunto de pares ordenados
denominamos de produto cartesiano.
Produto Cartesiano - Exemplo
A = {ponte1, ponte2}
B = {madeira, concreto, ferro}
Podemos formar o conjunto dos seguintes pares
ordenados:
{(ponte1,madeira),(ponte1,concreto),(ponte1,ferro),
(ponte2,madeira),(ponte2,concreto),(ponte2,ferro)}
Tarefa
 Programar
cartesiano
em Prolog o produto