PDF de programación - TextRank

TextRank

Bringing order into texts

Índice

 PageRank
 TextRank
 Etiquetado: tareas y herramientas
 Una pequeña aportación

1

PageRank
Las dos ideas de Google en el 98

 Los artículos:

 The PageRank Citation Ranking: Bringing Order to the

Web. L. Page, S. Brin, R. Motwani, T. Winograd

 The Anatomy of a Large-Scale Hypertextual Web Search

Engine. S. Brin, L. Page

 Las ideas:

 PageRank: Método para calcular la relevancia de las

páginas independientemente de la consulta

 Índices inversos: Método para encontrar rápidamente los

documentos asociados a una palabra

PageRank
Todos los nodos son iguales, pero …

v

 In(v) = 4
 Out(v) = 1

2

PageRank
… algunos son más iguales que otros

v

El más
importante

PR(Vi) = (1-d) + d * ∑ j In(Vi) PR(Vj)

1

|Out(Vj)|

PageRank
Indexar por palabras

Vocabulario

Dada una
palabra w

Barril (rango de
palabras)

14 millones de
palabras (cabe
en memoria)

Hit list

Doc id

Doc id

Doc id

3

TextRank
PageRank aplicado a textos

 TextRank: Bringing Order into Texts. R.

Mihalcea, P. Tarau
 Buscar conexiones entre unidades de texto
 Construir un grafo
 Aplicar PageRank
 Usar el valor resultante para decidir algo sobre la

unidad textual

TextRank
Ponderado

 En internet no tiene mucho sentido tener

enlaces múltiples o parciales

 En los grafos de texto sí puede ser útil

j

wji

i

PR(Vi) = (1-d) + d * ∑ j In(Vi) PR(Vj)

wji

∑ j Out (Vi) wjk

4

TextRank
Grafos sin dirección

 En internet tampoco tiene sentido
 Pero en textos puede que sí

 In(v) = Out(v) = Número de arcos ligados a v

v

 In(v) = 5
 Out(v) = 5

TextRank
Generación de resúmenes

 Las unidades textuales son frases
 Arcos sin dirección
 El peso es una medida de distancia

5

TextRank
Extracción de palabras clave

 Las unidades textuales son palabras
 Dos palabras están conectadas si están a menos de

N palabras de distancia

 Se pueden filtrar por categorías sintácticas

TextRank
No supervisado pero potente

 En ninguna de las aplicaciones anteriores se

usa material de entrenamiento
 Corpus con palabras clave
 Corpus con resúmenes

 Sin embargo, consigue resultados similares a

otras propuestas que sí lo usan
 Supervisado: Ejemplos de train + test
 No supervisado: Sólo ejemplos de test

 ¿Porqué?

6

Etiquetado: tareas y herramientas
Algunas definiciones

 Tratamiento secuencial de textos
 Tratamiento basado en análisis sintáctico

 Parcial
 Completo

 Etiquetado POS (Part Of Speech)

 La tarea secuencial por excelencia
 Existen muchos recursos y herramientas

Etiquetado: tareas y herramientas
Etiquetado POS

APPG
NN
VVD
RP
AT
JJ
NN
YC

His
face
took
on
a
sudden
pallor
,
became VVD
beaded VVN
with
sweat
,
and
he
seemed VVD
…

IW
NN
YC
CC
PPHS

Corpus Susanne

7

Etiquetado: tareas y herramientas
Reconocimiento de entidades

Corpus CoNLL-2002

El
presidente
del
Consejo
por
la
Paz
,
organismo
observador
de
Perú
,
Francisco
Díez
Canseco I-PER
,
consideró
…

O
O
O
B-ORG
I-ORG
I-ORG
I-ORG
O
O
O
O
B-LOC
O
B-PER
I-PER

O
O

Etiquetado: tareas y herramientas
Análisis sintáctico superficial

Corpus CoNLL-2000

But
CC
analysts NNS
reckon
VBP
underlying VBG
NN
support
for
IN
NN
sterling
VBZ
has
VBN
been
VBN
eroded
by
IN
the
DT
chancellor NN
POS
's
NN
failure
TO
to
announce VB
any
DT
…

O
B-NP
B-VP
B-NP
I-NP
B-PP
B-NP
B-VP
I-VP
I-VP
B-PP
B-NP
I-NP
B-NP
I-NP
B-VP
I-VP
B-NP

8

Etiquetado: tareas y herramientas
TnT: Modelos de Markov

P(I-ORG|B-ORG)

P(B-ORG|O)

I-ORG

B-ORG

P(O|B-ORG)

...

O

...

P(B-LOC|B-ORG)

P(Extremadura|B-LOC)

Extremadura

B-LOC

...

P(Londres|B-LOC)

Londres

Etiquetado: tareas y herramientas
TreeTagger: Árboles de decisión

c1

c2

c3

2

3

1

...

10

6

5

6

...

6

4

3

1

...

1

c4

11

12

1

...

5

clase

A

A

B

...

A

c3<2

c3>=2

A

c1<3

B

c1>=3

A

9

Etiquetado: tareas y herramientas
fnTBL: Basado en transformaciones
TBL: Transformation
Based (Error driven)
Learning

W,T -> T’
W-1,T->T’
W-1,W,T->T’
…

Corpus
etiquetado

Plantillas
de reglas

del,VRB->NN
…

Reglas 1

…

al,VRB->NN
del,VRB->NN
…

Reglas N

…

C0-simple

C1

CN

Etiquetado: tareas y herramientas
MaxEnt: Máxima Entropía

 P(e,c): probabilidad de que la etiqueta e se

corresponda con el contexto c

 El Modelado de máxima entropía plantea calcular P

de manera que:
 Se ajuste lo mejor posible a los casos conocidos
 Distribuya el resto de la probabilidad uniformemente entre

los casos desconocidos

 Las características expresan una relación de co-

ocurrencia entre una predicción y algo en el contexto

1 si e = DET y palabra(c)=“that”

fj(e,c) =

0 en otro caso

10

Etiquetado: tareas y herramientas
MBT: Basado en memoria

 MBT: Memory Based Tagger
 MBL: Memory Based Learning
 Optimización del método de los k-vecinos

más cercanos

 Paquete adaptado para tareas PLN

Una pequeña aportación
Objetivo

 Implementar un método de etiquetado

basado en TextRank:
 Secuencial
 Supervisado

11

Una pequeña aportación
La idea

 Vértices:

 Extraídos del texto
 Pareja palabra-etiqueta

<abstract, NOM>
<abstract, ADJ>
<abstract, VER>

 Arcos:

 Sacados del corpus
 P(t|t-1) * P(w|t)

P(t|t-1) = C(t-1,t)/C(t-1)
P(w|t) = C(w,t)/C(t)

Una pequeña aportación
Un ejemplo

“The Ministry of Finance confirms the base rate of interest for half a year.”

confirms

VB

the
DT

base
NN

base
ADJ

base
VB

rate
NN

rate
VB

of

PRP

interest

NN

interest

VB

12

Una pequeña aportación
Un par de variantes

 Con trigramas y bigramas

rate

ADJ →VB

 Inverso: de izquierda a derecha

 Se utiliza la probabilidad P(t-1|t)

 Combinado con stacking

 Se genera una base de datos con las propuestas

del método original y del inverso

 Se aprende de esa base de datos

Una pequeña aportación
Resultados

13

Una pequeña aportación
Posibles ampliaciones

 Heurísticas para palabras desconocidas

 Ya incluidas por la mayoría de las herramientas

comparadas

 Aplicar la idea a otro tipo de problemas

 No secuenciales

14