Determining Similarity and Inferring
Relations in a Lexical Knowledge Base
Dissertação de Doutoramento de
Stephen D. Richardson
City University of New York
1997
Apresentado por:
Nuno Seco
Estrutura da Tese
●
Introdução
●
Extracção de Relações Semânticas
●
Atribuição de Pesos às Relações
●
Quantificação de Semelhanças Semânticas
●
Inferência de Novas Relações
●
Conclusões
Objectivos e Motivação
●
Criação de uma Base de Conhecimento
Lexical (Ontologia Lexical, Rede Lexical, ...).
Porquê?? Para que Serve??
Objectivos e Motivação
●
Aplicações:
–
Ferramentas de auxílio à escrita
–
Desambiguação
–
Sumarização
–
Recolha de Informação
Abordagens
●
Duas estratégias seguidas na obtenção da
Ontologia Lexical:
●
Manualmente: WordNet, Cyc, HowNet…
●
(Semi -) Automáticamente: MindNet
Extracção de Relações Semânticas
●
Conversão de dicionários (LDOCE) para um
formato mais formal.
–
●
MIND – MIcrosoft Natural Language Dictionary
Porquê dicionários?
–
Vocabulário fechado
–
Linguagem simples
Extracção de Relações Semânticas
●
Exemplo:
–
fruit --- “an object that grows on a tree or bush,
contains seeds, is used for food, but is not
usually eaten with meat or with salt“.
Extracção de Relações Semânticas
(1 - Árvores Sintácticas)
fruit:
"an object that grows on a tree or bush, contains seeds, is used
for food, but is not usu. eaten with meat or with salt"
NP1
DETP1
NOUN1*
RELCL1
ADJ1*
"an"
"object"
NP2
PRON1*
VP1
VERB1*
PP1
CONJP1
VP2
CONJP2
VP3
CONJ4*
VP4
CONJ2*
VERB2*
NP5
CONJ3*
AUXP1
VERB4*
PP3
"but"
AUXP2
AVP1
VERB6*
PP5
"that"
"grows"
PP2
PREP1*
DETP2
ADJ2*
NP3
NOUN2*
CONJ1* "or"
NP4
NOUN3*
","
"contains"
NOUN4* "seeds"
","
VERB3* "is"
"used"
PP4
PREP2*
NOUN5* "food"
CHAR1
","
VERB5*
AVP2
ADV2*
"eaten"
PP6
CONJ5*
PP8
"is"
ADV1*
"usu."
PP7
NOUN6*
"or"
PP9
NOUN7*
"on"
"a"
"tree"
"bush"
"for"
"not"
PREP3*
"meat"
"with"
PREP4*
"salt"
"with"
Extracção de Relações Semânticas
(2 - Forma Lógica)
fruit:
"an object that grows on a tree or bush, contains seeds, is used
for food, but is not usu. eaten with meat or with salt"
object1
Prop but1
Crds
grow1
Ptcl
Dsub
Dobj
on1
object1
or1
Crds tree1
bush1
contain1
Dsub object1
Dobj seed1
use1
Dsub x1
Dobj object1
for
food1
eat1
Dsub x2
Dobj object1
Mods usu.1
or2
with meat1
with salt1
Tenta-se normalizar o
texto, tratando de
questões como:
• Voz Passiva
• ex: “eaten”
• Anáfora
Extracção de Relações Semânticas
●
Utilização de heurísticas:
–
“If the head verb of phrase is use and it is postmodified by a prepositional phrase containing the
preposition for, then create a Purpose relation
between the word being defined and the object
of for.”
Fruit
Purp
Food
Extracção de Relações Semânticas
(3 – Forma Semântica Relacional )
fruit :
"an object that grows on a tree or bush,
contains seeds, is used for food, but
is not usu. eaten with meat or with salt"
fruit
Hyp >
Part >
Purp >
< Tsub
< Tobj
object
seed
food
grow
Locn >
eat
tree
bush
Extracção de Relações Semânticas
●
São identificadas 16 tipos de relações a
extrair, alguns exemplos são:
–
Causalidade
–
Hyperonímia
–
Sinonímia
–
Meronímia
–
Objecto_Típico_de
–
Sujeito_Típico_de
Extracção de Relações Semânticas
●
Ponto da Situação:
–
–
–
Deriva-se as árvores sintácticas das definições.
Efectua-se um conjunto de transformações e
obtém-se as representações lógicas.
Efectuam-se mais transformações e obtém-se a
forma semântica relacional.
●
Permite a extracção de triplos (“SEMRELS”):
–
●
x1R x2
Será que não se pode fazer mais?
Extracção de Relações Semânticas
car:
"a vehicle with 3 or usu. 4 wheels and driven
by a motor, esp. one for carrying people"
car
Hyp>
Part>
<Tobj
Purp>
●
vehicle
wheel
drive
Means>
carry
Tobj>
motor
people
Serão estas as únicas relações que se
conseguem extrair para “car” ?
Extracção de Relações Semânticas
●
E as definições que contêm a palavra “car”?
hood :
"the bonnet covering the engine of a car"
hood
Hyp >
< Tsub
bonnet
cover
Tobj >
<
engine
Part
demist :
"to clean steam from (the windows of a car)"
demist
Hyp >
Tobj >
clean
Tobj >
window
Part
<
steam
car
car
Extracção de Relações Semânticas
●
Através de um processo de inversão obtemos:
hood:
"the bonnet covering the engine of a car"
inversion paraphrase:
"a car has an engine, which is covered by a hood, which is a bonnet"
car
Part>
engine
<Tobj
cover
Tsub >
hood
Hyp>
bonnet
demist:
"to clean steam from (the windows of a car)"
inversion paraphrase:
"a car has a window, which is demisted, which is cleaning steam (from)"
car
Part>
window
<Tobj
demist
Hyp >
clean
Tobj>
steam
Extracção de Relações Semânticas
●
●
LDOCE contém:
–
33,000 entradas de substantivos
–
12,000 entradas de verbos
Processo de extracção obteve:
–
●
Processo de inversão produz:
–
●
147,000 semrels (x1 R x2)
180,000 semrels
78% das relações (com um erro de -/+ 5%) estão
correctas
Atribuição de Pesos às Relações
●
É importante quantificar a importância dos
SEMRELS ou um “caminho” de SEMRELS
entre duas palavras.
Semrel:
car --- Poss ---> people
Caminho de Semrels:
car --- Purp ---> carry --- Tobj ---> people
Atribuição de Pesos às
Relações
●
Formalizando um pouco mais:
–
SEMREL
●
–
–
w1Rw2 (car --- Purp ---> carry)
Caminho de SEMRELS
●
w1R1w2R2w3 (car --- Purp ---> carry --- Tobj ---> people)
●
w1R1w2…wnRn+1wn+1
Partes do SEMREL
●
w1R1
●
R1w2
Atribuição de Pesos Utilizando
tf.idf
• Adaptação de métricas utilizadas em RI.
N
wik  tfik. log 2 
 nk 
• wik - peso do termo Tk do documento Di
• tfik – frequencia Tk no documento Di
• N – nº total de documentos (colecção)
• nk – nº de documentos com Tk
Peso de w1Rw2 para entrada w1
Frequência de _Rw2 na entrada w1
Nº de entradas na BCL
Nº de entradas na BCL com _Rw2
Atribuição de Pesos Utilizando
tf.idf
Quais são as partes mais importantes/salientes
de um carro?
Relações Semânticas
Frequência
Frequência
tf.idf
(SemRels)
(SemRels)
(2ª parte)
carPartengine
3
8
34.511
carPartwheel
3
28
29.089
carPartwindow
2
4
25.007
carParttop
2
50
17.720
carPartclutch
1
1
14.504
carPartdicky
1
1
14.504
carPartfender
1
1
14.504
carPartscoop
1
1
14.504
carParttrunk
1
4
12.504
carParthorn
1
11
11.044
Atribuição de Pesos Utilizando
tf.idf
●
Alguns problemas com o tf.idf.
–
As palavras mais discriminatórias (w2) não
representam a maior saliência cognitiva.
–
Não é uma métrica simétrica:
●
sc(w1Rw2) != sc(w2Rw1)
Atribuição de Pesos Utilizando
Informação Mútua
●
Informação Mútua (“Mutual Information”)
 Px, y  

IM ( x, y)  log 2
 Px .P y  
P(x) – probabilidade de x ocorrer
P(y) – probabilidade de y ocorrer
P(x,y) – probabilidade de x e y co-ocorrerem
Atribuição de Pesos Utilizando
Informação Mútua
●
Fazendo a correspondência para o domínio
do problema --- MI(w1Rw2):
P(x)
P(w1R)
P(y)
P(Rw2)
P(x,y)
P(w1Rw2)
Atribuição de Pesos Utilizando
Informação Mútua
Quais são as partes mais importantes/salientes
de um carro?
Relações Semânticas
Frequência
Frequência
MI
(SemRels)
(SemRels)
(2ª parte)
carPartdicky
1
1
9,201
carPartfender
1
1
9,201
carPartscoop
1
1
9,201
carPartunderside
1
1
9,201
carPartwindow
2
5
7,879
carPartboot
1
3
7,616
carPartcockpit
1
3
7,616
carPartengine
3
11
7,327
carParttrunk
1
6
6,616
carPartwheel
3
32
5,786
Atribuição de Pesos Utilizando
Informação Mútua
●
As frequências muito baixas dos SEMRELS
podem ser a causa do problema.
●
Foram testadas algumas variações ao IM standard,
mas sem sucesso.
Atribuição de Pesos às
Relações
●
Lei de Zipf:
–
Ordenando as palavras por ordem de frequência
descendente (“rank”) e traçando a curva em relação
à frequência da palavra obtém-se uma curva
hiperbólica.
–
A posição classificativa (“rank”) de uma palavra
vezes a sua frequência aproxima uma constante K.
Atribuição de Pesos às Relações
Frequênciaia
Curva de Zipf
Classificação
Atribuição de Pesos às Relações
Frequênciaia
Curva de Zipf e Curva de Luhn
Classificação
Atribuição de Pesos às Relações
●
Será a Lei de Zipf válida para as relações
semânticas (SEMRELS)?
–
Existem muitos mais SEMRELS distintos do que
palavras.
–
As frequências de cada SEMREL são bastante
baixas.
●
–
Frequência de 90 é o máximo
Não existem palavras de função.
Atribuição de Pesos às Relações
●
Para obter uma curva equivalente à de Zipf
pode-se traçar uma curva que relaciona o
número de SEMRELS com uma determinada
frequência em relação à frequência.
Número de SEMRELS com uma Freq Freq ..
Atribuição de Pesos às Relações
100
80
60
40
20
vertex
0
0
20
40
60
Frequência
80
100
Atribuição de Pesos às Relações
●
●
●
Já sabemos como obter uma curva parecida
com a de Zipf.
Mas o que interessa saber é quais as
palavras que estão relacionadas por
relações perto de vértice.
Para isso temos que traçar um gráfico para
cada relação.
Atribuição de Pesos às Relações
Exemplo:
50
Frequency
Curva representando a
frequência de SEMRELS do
tipo TOBJ em relação ao
número de SEMRELS com
uma dada frequência.
40
30
20
10
0
0
10
20
30
40
Frequency of semrels containing Tobj
relation
50
Função de Frequência
“Verticial”


bR1 


FV  w1 R1w2   min  F  w1 R1w2  , 1  a R1 F  w1 R1w2  
50
40
30
20
10
0
0
10
20
30
40
50
Probabilidades “Verticiais”
●
Probabilidade de um SEMREL:
PV w1 R1w2  
FV w1 R1w2 
 F wi R j wk 
all i , j , k
●
Probabilidade das partes do SEMREL:
PV  w1 R1  
FV  w1 R1 
 F w R 
i
j
all i , j


PV R1w2 R1 
FV  R1w2 
 F R w 
1
all k
k
Probabilidade Estimada
●
●
Como as frequências de SEMRELS é baixa
a validade das estatísticas pode estar
comprometida.
Pode-se utilizar probabilidades estimadas
(“Averaged Probabilities”).
PV w1R1w2   Aw1R1w2 PV w1R1w2   Aw1R1w2 PV w1R1 PV R1w2 R1 
Probabilidade Estimada
●
Factores de Estimação:
A w1 R1w2  
F  w1 R1w2 
F  w1 R1w2   1
1
A w1 R1w2  
F  w1 R1w2   1
Atribuição de Pesos utilizando
Probabilidades Estimadas
Relações Semânticas
Frequência
Frequência
Probabilidade
(SemRels)
(SemRels)
(2ª parte)
Estimada
carPartengine
3
11
.0000163706
carPartwheel
3
32
.0000163627
carPartwindow
2
5
.0000097012
carParttop
2
61
.0000096967
carParthorn
1
11
.0000036557
carParttrunk
1
6
.0000036466
carPartboot
1
3
.0000036411
Determining Similarity and Inferring
Relations in a Lexical Knowledge Base
Dissertação de Doutoramento de
Stephen D. Richardson
City University of New York
1997
Apresentado por:
Nuno Seco