<gh_stars>0
\documentclass[a4paper]{article}
\usepackage[paperwidth=180mm,paperheight=285mm,left=3cm,top=4cm,right=3cm,bottom=2cm,head=2.0cm,includefoot]{geometry}
\usepackage{makeidx}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{url}
\usepackage{fancyvrb}
\usepackage{babelbib}
\usepackage{graphicx}
\usepackage{lscape}
\usepackage{fancyhdr}

\graphicspath{ {img/} }

%%%%%%%%%% Text with box
\usepackage{tikz}
\usetikzlibrary{shadows}

\newcommand{\raisedtext}[1]{
  \vspace{1mm}
  \begin{tikzpicture}
    [baseline=(X.base)]\node [drop shadow,fill=white,draw,very thin] (X) {#1};
  \end{tikzpicture}
  \vspace{1mm}
}
%%%%%%%%%%%%%%%%%%%


\newtheorem{definicion}{Definición} 

\urldef{\mails}\path|{<EMAIL>,<EMAIL>| 

\title{Módulo de resúmenes automáticos basado en TextRank con integración a Gensim}
\author{<NAME> \and <NAME>}

\lhead{\includegraphics[scale=0.06]{logo_fiuba.pdf}}
\chead{Módulo de Resúmenes Automáticos Basado\linebreak en TextRank con Integración a Gensim}
\rhead{}

\lfoot{Barrios -- López}
\rfoot{\thepage}
\cfoot{Mayo, 2015}

\begin{document}

\thispagestyle{empty}
% T\'itulo del documento.
\begin{center}
\includegraphics{logo-fiuba.png}\\
\vspace{1cm}
\textsc{\LARGE Universidad de Buenos Aires}\\[0.3cm]
\textsc{\LARGE Facultad de Ingeniería}\\[1.2cm]
\textsc{\LARGE Trabajo Profesional}\\[1.2cm]
\textsc{\LARGE Módulo de resúmenes automáticos basado en TextRank con integración a Gensim}\\[0.3cm]
\end{center}

\vspace{20 mm}

\begin{flushright}
{\large
<NAME> -- 91954\\
<NAME> -- 92278\\[0.1cm]
\vspace{2cm}
Mayo, 2015}
\end{flushright}

\pagestyle{fancy}
\newpage

\footnotesize


\newpage
\setcounter{page}{1}
\tableofcontents

\newpage
\section{Motivación}
Los resúmenes automatizados son muy utilizados en tareas relacionadas con el procesamiento de lenguaje natural y de aprendizaje automático. Su uso en motores de búsqueda, por ejemplo, mejora la eficiencia de indexación de textos y a su vez asiste en la presentación de resultados de manera efectiva. El incremento en la cantidad de información disponible en Internet ha intensificado su utilización en los últimos años y, en consecuencia, se ha dedicado enorme esfuerzo para mejorar los algoritmos existentes. 
El desarrollo de este Trabajo Profesional está motivado por el número de aplicaciones del tema en tareas de actualidad.


\section{Objetivos}
El presente trabajo consta de tres objetivos principales:
\begin{itemize}
\item Desarrollar el módulo para generar resúmenes automáticos usando un algoritmo conocido.
\item Analizar, diseñar e implementar modificaciones para intentar mejorar el rendimiento del algoritmo seleccionado.
\item Integrar las implementaciones a una herramienta de código abierto de procesamiento del lenguaje natural.
\end{itemize}

\section{Introducción teórica}

\subsection{Resúmenes: generación y clasificación}
Un resumen es una reducción a términos breves y precisos de lo esencial de una fuente de información. Su objetivo es el de extraer contenido intentando sintetizar sus conceptos más importantes, y su uso es altamente benéfico en tareas de aprendizaje debido a que:
\begin{itemize}
\item Facilitan la selección de información,
\item Acortan tiempos de lectura,
\item Simplifican búsquedas en textos,
\item Optimizan la creación de índices.
\end{itemize}

La investigación indica, además, que contribuyen en tareas automatizadas: su utilización para presentar resultados de motores de búsquedas atrajo el interés de académicos desde principios de la década del 2000, convirtiéndose hoy en día en una funcionalidad básica de los principales buscadores de Internet.

Sin embargo, si bien esta tarea puede no resultar costosa para un ser humano, durante muchos años fue considerada como difícil de automatizar. Este tema es uno de los que investiga el campo de procesamiento de lenguaje natural, dedicado a facilitar la interacción entre las computadoras y los seres humanos.


\subsubsection{Enfoque abstractivo y extractivo}

Existen dos métodos para generar resúmenes automatizados: abstractivos y extractivos.

Los primeros se construyen regenerando el contenido extraído del texto original; esto es, se reformulan las frases por medio de técnicas de generación de lenguaje natural: fusión, combinación o supresión de términos. De esta manera, se obtienen pasajes que en principio no pertenecían al texto de origen, similar al modo en que lo harían las personas. 

Por el contrario, los resúmenes extractivos se crean a partir de la selección de un conjunto de palabras u oraciones consideradas sobresalientes en el texto original. Las oraciones se obtienen literalmente, se unen libremente, y se presentan con el objetivo de crear un resumen del texto.

Las técnicas abstractivas son un área de creciente interés. Sin embargo, debido a la complejidad y las restricciones técnicas aparejadas, la investigación se ha volcado hacia el enfoque extractivo.


\subsubsection{Aprendizaje supervisado y no supervisado}
En el campo del aprendizaje automático, a los algoritmos que requieren de un conjunto de entrenamiento con datos etiquetados se denominan supervisados. Analizando estos ejemplos de entrenamiento, el sistema infiere funciones que pueden ser usadas para aplicarlas a nueva información.

Por el contrario, a los algoritmos que no son entrenados se los denomina no supervisados. Este grupo utiliza técnicas para encontrar patrones o grupos ocultos en los datos a analizar.


\subsubsection{Fuente de los datos}
Los algoritmos de generación de resúmenes también se categorizan de acuerdo a la cantidad de documentos que se toman como fuente, determinando sumarización de un documento y multi-documento.

Para este último caso se proporcionan textos con una temática afín. El resumen resultante permite a los lectores familiarizarse rápidamente con los tópicos principales de una colección de documentos.


\subsubsection{Propósito del resumen}
Los resúmenes de documentos pueden crearse de manera genérica o bien basados en consultas. 

Aquéllos resúmenes basados en consultas favorecen temas o aspectos específicos de un texto, de acuerdo a dicha consulta; teniendo en cuenta sus palabras clave o los tópicos a los que hace referencia. Los resúmenes genéricos, por otro lado, proporcionan los temas más relevantes tratados en el texto por sí solo.


\subsection{Extracción de palabras claves}
La extracción de palabras claves consiste en identificar el conjunto de términos que mejor describen a un documento de manera automatizada. Esto sirve como introducción a sus conceptos más relevantes, pues uno de los primeros pasos para modelar el conocimiento de una comunidad es tomar vocabulario del dominio. Es por ello que se han estudiado métodos para extraer este léxico técnico en base a documentos del área o comunidad en estudio.

Dichas palabras se pueden utilizar para construir índices de colecciones, clasificar textos, extraer terminología de dominio específica, o incluso pueden servir como un breve resumen.

El enfoque más sencillo para esta tarea ha empleado un criterio basado en la frecuencia de las palabras. Sin embargo, se han investigado otras debido a los malos resultados de esta técnica. Las principales se basan en métodos supervisados, donde el sistema es entrenado para reconocer palabras claves tomando en cuenta cuestiones sintácticas y/o léxicas. 

En la sección ‘TextRank para palabras claves’ se analiza y desarrolla la aplicación de TextRank como método no supervisado para esta tarea. Los resultados obtenidos se equiparan los de las técnicas principales en el área.


\section{Trabajo previo}
El campo de la generación automática de resúmenes ha atraido interés desde finales de la década de 1950 hasta la actualidad \cite{luhn}. Los métodos tradicionales tienen en cuenta la frecuencia de palabras o frases introductorias para identificar las oraciones más sobresalientes del texto. También se han desarrollado modelos estadísticos basados en corpus de entrenamiento para combinar varias heurísticas: palabras clave, posición de las oraciones, longitud de las oraciones, frecuencia de palabras y palabras contenidas en los títulos \cite{hovy}. Otros enfoques más modernos se basan en la representación del texto en forma de grafo: las oraciones importantes y los conceptos son las entidades altamente conectadas y, por esto, forman parte del resumen \cite{barzilay}. 

Con esta idea se usan métodos del campo de Recuperación de Información para identificar oraciones similares y determinar las más importantes, que formarán al resumen final \cite{salton}. El enfoque propuesto, tanto por Mihalcea y Tarau en TextRank \cite{mihalcea-tarau} como por Erkan y Radev en LexRank \cite{erkan}, consiste en utilizar el prestigio de las unidades léxicas (oraciones o palabras) dentro del grafo.


\section{Herramientas y fundamentos}

\subsection{PageRank}
PageRank es un algoritmo creado en 1996 por <NAME> y <NAME>, fundadores de Google, como parte de una investigación sobre motores de búsqueda. Su objetivo es asignar un valor numérico a cada nodo en una red, con el propósito de medir la importancia relativa de cada elemento del conjunto. Para esto analiza los vínculos que componen la red. La idea subyacente es que los nodos más relevantes de la red serán los que tengan la mayor cantidad y calidad de conexiones con otros nodos.

En sus orígenes, PageRank fue pensado para aplicarse sobre la red de Internet, pero puede aplicarse a cualquier otra red para estimar la importancia de los nodos. En términos matemáticos, PageRank brinda una manera iterativa de calcular el autovector principal de la matriz de adyacencia del grafo. Esto da como resultado la distribución de probabilidad de acceder a los nodos de la red, navegando de manera aleatoria a través de los vínculos o aristas.


\subsection{TextRank}
TextRank es un algoritmo no supervisado basado en grafos para realizar resúmenes automáticos extractivos u obtener palabras claves de un texto. Fue presentado en 2004 por <NAME> y <NAME> en \cite{mihalcea-tarau}.

El algoritmo aplica una variación de PageRank \cite{pageetal98} sobre un grafo especialmente diseñado para la tarea. De esta manera permite explotar la estructura del texto, identificando los conceptos principales, sin necesidad de datos previos de entrenamiento. Debido a que se basa en PageRank, se sirve de la noción del “prestigio” o “recomendación” entre los elementos del grafo. Por este motivo, TextRank puede ser aplicado a cualquier texto, incluso en distintos idiomas, generando un resumen basado sólo en las propiedades intrínsecas del texto.

El algoritmo modela el texto en base a un grafo, y luego, busca crear relaciones significativas (aristas) entre las entidades léxicas (vértices). Dependiendo de la aplicación que se desee dar al algoritmo, las entidades pueden ser palabras, frases, oraciones, párrafos, entre otros. De manera similar, también debe definirse el tipo de relación que se usa para unir los vértices: semántica, contextual, de superposición, y demás.

Los pasos principales que se llevan a cabo son los siguientes:

\begin{enumerate}
\item Identificar las unidades del texto y agregarlas al grafo como vértices.
\item Identificar relaciones que conectan a estas unidades, y agregarlas al grafo como aristas entre los vértices. Las aristas pueden ser dirigidas o no, y ponderadas o no.
\item Aplicar PageRank para asignarle un puntaje a cada vértice.
\item Ordenar los vértices de acuerdo al puntaje y utilizarlo para armar el resumen de acuerdo a algún criterio.
\end{enumerate}

\subsection{Gensim}
Gensim es una biblioteca de código libre, escrita en Python, para el modelaje de tópicos y la indexación de documentos que está diseñada para trabajar con conjuntos de textos de gran tamaño \cite{rehurek_lrec}. Su uso se ha expandido tanto en lo comercial como lo académico, apuntando especialmente al área de procesamiento del lenguaje natural y a la búsqueda y recuperación de la información.

Gensim utiliza un paradigma muy poderoso en el área de procesamiento de lenguaje natural, denominado VSM (modelo de espacio de vectores), en el cual se representan los documentos de un corpus como vectores de un espacio multidimensional. Esta representación explota la idea de que los textos en el área del modelado de tópicos se pueden expresar según un número de conceptos, lo que aumenta la eficiencia y también ayuda a eliminar ruido.

La biblioteca está diseñada para proveer independencia del tamaño del corpus, es decir, para poder analizar textos que sean más grandes que la memoria RAM del sistema. El proyecto, además apunta a exponer una interfaz mínima e intuitiva utilizando terminología de procesamiento de lenguaje.

Gensim proporciona implementaciones de algoritmos como TF-IDF, análisis semántico latente, proyecciones aleatorias y alocación de Dirichlet latente.


\subsection{Evaluación de resúmenes}
La herramienta por defecto para evaluar los sistemas generadores de resúmenes es \mbox{ROUGE} (Recall-Oriented Understudy for Gisting Evaluation) \cite{Lin2004a}. Este método fue desarrollado en la universidad de Southern California para automatizar la comparación entre resúmenes generados por el sistema bajo evaluación contra otros (ideales) escritos por seres humanos, tomados como referencia.

Históricamente, los puntajes asignados en tareas de competencias como DUC fueron manuales; juzgando coherencia, capitalización, cohesión, consistencia y contenido \cite{duc2002}. Todo este trabajo es caro y difícil de coordinar, demandando de al menos 3.000 horas hombre. El surgimiento de ROUGE atiende la necesidad de automatizar ese proceso, reemplazando un método llamado BLEU, cuyos resultados no siempre se correlacionaban con los asignados por los jurados.

El mecanismo de funcionamiento de los métodos del paquete ROUGE consiste en calcular la sensibilidad (recall) de unidades léxicas entre los resúmenes de sistema y los de referencia. Se generan así diferentes métricas:
\begin{itemize}
\item ROUGE-N: cuando se tienen en cuenta n-gramas (n palabras). Este método favorece a documentos con palabras compartidas por más candidatos.
\item ROUGE-L: cuando se tiene en cuenta la subsecuencia máxima común (LCS, longest common subsequence). Este método propone que un conjunto de documentos va a ser más parecido mientras más larga sea la subsecuencia común máxima.
\item ROUGE-W: le asigna pesos a las subsecuencias según su largo.
\item ROUGE-S: es similar a ROUGE-2, teniendo en cuenta bigramas pero permitiendo una cantidad arbitraria de espacios entre palabras.
\item ROUGE-SU: extiende la idea de ROUGE-S, pero además le otorga valor a las palabras que haya en común, sin importar que no verifiquen un orden.
\end{itemize}

ROUGE asigna un puntaje entre cero y uno a un esquema de evaluación conformado por una serie de documentos generados y sus referencias. Por diseño, se espera que buenos resúmenes tengan puntajes más altos; pero inevitablemente se requiere de trabajo humano para proveer las referencias.

Debido a que los resultados arrojados por las métricas se correlacionan con los asignados manualmente, las evaluaciones en las competencias de generación de resúmenes automáticos se llevan a cabo usando exclusivamente ROUGE \cite{mihalcea-tarau}.


\section{Implementación}
\subsection{Preprocesamiento}
El preprocesamiento del texto es una parte esencial en cualquier sistema que trate con datos del lenguaje natural. En esta fase se identifican las unidades léxicas que serán analizadas por la aplicación en las etapas subsiguientes. 

La calidad de este proceso tendrá un gran impacto en los resultados obtenidos. Es por ello que se deben seleccionar unidades léxicas significativas. Es decir, aquellas que contengan las características lingüísticas relevantes para el caso en estudio. A su vez, se deben filtrar las que no aportan información útil. En este proceso también, se unifica la codificación que pudiera existir en los distintos textos.

Aquí se detallan las etapas principales.

\subsubsection{Separación del texto}
Esta etapa, también conocida como \textit{tokenización} consiste en separar el texto en oraciones o palabras. Separar palabras suele resultar más sencillo, dado que los espacios en blanco son una buena aproximación como límite de separación. 

Separar por oraciones suele ser caso más complejo. Definir los límites es una cuestión realmente problemática en el área del lenguaje natural. Generalmente se utilizan los símbolos .!? como separadores, pero se deben tratar con cuidado excepciones como \textit{Ph.D.}, \textit{Dr.}, \textit{Lic.}, \textit{\$19.99}, \textit{p.m.} o \textit{RR.HH}. El enfoque más utilizado para resolver esta cuestión se basa en la aplicación de expresiones regulares, aunque existen otras alternativas que implementan algoritmos entrenados con datos específicos del área sobre la cual se esté trabajando.


\subsubsection{Filtrado}
Las palabras más frecuentes muchas veces no tienen tanto significado por sí solas. En muchas tareas de procesamiento de lenguaje natural estas palabras aportan “ruido”, y por lo tanto se las debe quitar. 

La forma de filtrar palabras consiste en crear una lista de “palabras prohibidas” (\textit{stopwords}) a ser eliminadas del texto.


\subsubsection{Stemming}
El proceso de \textit{stemming} o \textit{lemmatización} consiste en quitar la desinencia de las diferentes términos, para llevarlos a su raíz. Esta etapa se lleva a cabo con el objetivo de que el algoritmo detecte cuando se están tratando los mismos conceptos, dado que se utilizan las mismas palabras.
Por ejemplo, las palabras “canta”, “cantaba”, “cantando”, pueden ser asociadas al verbo “cantar”.

El stemming es un proceso complejo dado que puede haber muchos casos excepcionales, y se necesitan reglas muy diferentes para cada idioma. El stemmer más usado en inglés es el Porter Stemmer. Para cada idioma existe una adaptación. Sin embargo, todos estos algoritmos tienen cierta tasa de error.


\subsection{TextRank para extracción de oraciones}
El problema de la extracción de oraciones apunta a identificar las secuencias más representativas del texto. Para este caso, las unidades léxicas tenidas en cuenta para aplicar el algoritmo serán oraciones completas \cite{introductionir}.

Inicialmente, se construye un grafo en base al texto, agregando a cada oración como vértice. Para crear las aristas con su peso correspondiente, se debe definir una función de similitud entre dos oraciones dadas. Esta función será la que dicte cuánto una oración “recomienda” a otra por poseer contenidos similares y abordar los mismos conceptos.
    
La función utilizada formalmente por el algoritmo original se define de la siguiente manera:

\begin{definicion}
Sean $S_i$, $S_j$ dos oraciones representadas por un conjunto de $n$ palabras que en 
$S_i$ aparecen como $S_i = w_{1}^{i}, w_{2}^{i},..., w_{n}^{i}$. La función de similitud para $S_i$, $S_j$ se define como:

\begin{equation}
Similitud(S_{i},S_{j}) = \frac{ | \{   w_{k} | w_{k} \in S_{i} \& w_{k} \in S_{j}   \}  | }    
                              {  log(|S_{i}|) + log(|S_{j}|)  }
\end{equation}
\end{definicion}
    
El resultado de este proceso es el texto representado como un grafo altamente denso, al cuál se le aplicará PageRank para seleccionar los vértices más relevantes.
Finalmente, a las oraciones más importantes se las presenta de acuerdo al orden de aparición en el texto original.


\subsection{TextRank para palabras claves}
La otra aplicación que se le puede dar a TextRank es la extracción de palabras clave (\textit{keywords}) de un texto. Es un problema similar a la extracción de oraciones, dado que el objetivo es identificar un conjunto de unidades que sean representativas de dicho texto. Aquí, las unidades serán palabras, sueltas o combinadas.

Al igual que en el caso de la extracción de oraciones, luego de la etapa de preprocesamiento, las palabras no filtradas se agregan al grafo. Se pueden agregar filtros sintácticos adicionales para limitar el análisis sólo a, por ejemplo, sustantivos y verbos, o cualquier otra combinación. 

En lugar de una función de similitud, aquí se define una función de coocurrencia: dos vértices estarán conectados si las palabras que representan ocurren en el texto dentro de una ventana de n palabras, que suele tomar un valor entre dos y diez. Los vínculos de coocurrencia demuestran una relación entre los elementos sintácticos que sirve como indicador de la cohesión del texto. Es por ello que son útiles para indicar la relevancia de las palabras principales.

Con el grafo no ponderado y no dirigido construido, el valor de cada vértice se establece en uno, y se aplica el PageRank. Una vez asignados los puntajes, se toman los k vértices más relevantes, donde k suele ser un tercio de la cantidad de vértices totales. 

Finalmente, las palabras preseleccionadas se marcan en el texto. En caso que estas palabras formen secuencias adyacentes, se las une en un “concepto clave”. Por ejemplo, si se preseleccionan las palabras “Puerto” y “Rico”, y en el texto figuran juntas, se las combina en “Puerto Rico”.


\subsection{Métodos de evaluación}
Considerando que parte del alcance planteado incluye la propuesta de mejoras al método, se trabajó con el paquete ROUGE, desarrollado en lenguaje Perl. Se usó un proyecto de Python que funciona como wrapper para adaptar los textos de entrada (pyROUGE) y ejecutar automáticamente la evaluación. 

Se implementó, además, una capa de abstracción adicional para acotar la cantidad de opciones que se manejan, y para automatizar la corrida de múltiples textos de una base de datos.

Al ser un paquete de evaluación muy completo y versátil, ROUGE provee una gran cantidad de parámetros. Se configuraron sus opciones como se usan en las conferencias de DUC, calculando ROUGE-1, ROUGE-2 y ROUGE-SU4 en un intervalo de confianza del 95\% y aplicando un método de stemming \cite{duc2007}. 

Una de las restricciones que posee este método de evaluación es que requiere de resúmenes hechos por seres humanos para tomar como referencia, lo que implica un esfuerzo humano considerable si se quiere probar el rendimiento del método con varios textos. Se utilizó el corpus de DUC edición 2002, por ser en el que se desarrollaron las pruebas del paper original de TextRank.

Todos los resultados obtenidos se compararon contra un sistema de referencia (\textit{baseline}) que genera resúmenes que consisten de las primeras 100 palabras de cada texto \cite{baselines}.
Se configuró un ambiente de integración continua para permitir la ejecución de evaluaciones automatizadas y que además verifica la calidad del código programado. 


\section{Mejoras}
En esta sección se analizan las propuestas de mejora que arrojaron mejores resultados. Los métodos listados a continuación consisten en redefinir la similaridad entre las oraciones. El listado total de ensayos realizados y sus puntajes se puede consultar en el Anexo I.

\subsection{Propuestas}

\subsubsection{Subcadena común}
Dadas dos frases, el problema de la subcadena común más larga consiste en identificar la secuencia de caracteres de mayor extensión presente en ambas. Por ejemplo, entre “la cocina verde” y “una cocina vale más si es verde”, la secuencia más larga es “a cocina v” \cite{gusfield}.

La propuesta consiste en modificar la función de distancia de la implementación original y reemplazarla por el largo de la subcadena común más larga. En el ejemplo anterior, la similitud sería de 10, dado que es el largo de la secuencia “a cocina v”.


\subsubsection{Similitud coseno}
La similitud coseno es una medida del parecido entre dos vectores en un espacio que posee un producto interior, y resulta de evaluar el valor del coseno del ángulo comprendido entre ellos. Para poder hacer uso de esta propiedad se utiliza el modelo vectorial, modelando a los documentos como vectores.

Este modelo algebraico es utilizado para representar documentos en lenguaje natural de una manera formal, y tiene la característica de que favorece la dirección a la cuál apuntan los documentos independientemente de su longitud. Consecuentemente, textos que hablan de los mismos temas en distinta cantidad de palabras pueden tener una gran similitud con esta métrica \cite{singhal}. 

La propuesta se basa en aplicar este modelo para tratar a cada oración del texto como un vector n-dimensional (siendo n la cantidad de palabras distintas presentes en el documento), y luego compararlas utilizando la similitud coseno. Las componentes de cada vector estarán compuestas por el resultado de aplicar la función “frecuencia de término -- frecuencia inversa de documento” (TF--IDF de sus siglas en inglés) a cada palabra de la oración representada.

Tomando como ejemplo el documento “Esta bien. Todo bien.”, las oraciones quedarían modeladas como vectores de la siguiente forma:

\begin{center}
    \begin{Verbatim}[xleftmargin=3em]
    v1=[ TFIDF("Esta") , TFIDF("bien") ,       0       ]
    v2=[       0       , TFIDF("bien") , TFIDF("Todo") ]
    \end{Verbatim}
\end{center}

Dado que la imagen de la función TF--IDF está contenida en el intervalo [0,1], todos los vectores quedan conformados por entradas no negativas, haciendo que ninguna similitud sea menor a cero. 


\subsubsection{BM25}
BM25 / Okapi BM25 es una función de ranking utilizada como estado de arte para tareas de Recuperación de Información. 
Esta función es una variación del modelo TF--IDF usando un modelo probabilístico \cite{robertson}.

\begin{definicion}
Dadas dos oraciones R, S, BM25 se define como:

\begin{equation}
BM25(D,Q) = \sum_{i=1}^{n} IDF(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{avgDL})}
\end{equation}

donde $k$ y $b$ son parámetros establecidos a $1,2$ y $0,75$, respectivamente. $avgDL$ es el largo promedio de las oraciones en el texto.
\end{definicion}

Esta función define que el valor de aquellas palabras que aparecen en más de la mitad de los textos resulte negativo. 
Dado que este comportamiento puede traer problemas en las fases posteriores del algoritmo, se aplica la siguiente fórmula correctiva:
                
\begin{equation}
 IDF(q_i) =
  \begin{cases}
       log(N - n(q_i) + 0.5) - log(n(q_i) + 0.5)    & \text{si }  n(q_i) > N/2\\
       \varepsilon \cdot avgIDF                     & \text{si }  n(q_i) \leq N/2\\
  \end{cases}
\end{equation}                
                
donde $\varepsilon$ ronda entre 0,5 y 0,30 y avgIDF es el idf promedio para todos los términos.
También se ensayaron otras alternativas como establecer $\varepsilon = 0$ y usar modificaciones más simples a la fórmula clásica de IDF.

También se experimentó con una variante de este método, conocida como BM25+, que repara deficiencias de BM25 relacionadas a la frecuencia de término y a la penalización a documentos largos frente a documentos cortos irrelevantes \cite{lv}.

\subsection{Ejemplo}
En la Figura \ref{fig:text} se muestra un documento de ejemplo del conjunto de datos de la conferencia DUC del año 2002.
El resumen generado por el algoritmo de TextRank usando la función BM25 como similitud superó al original por un 30\% en la métrica de ROUGE-1 y por un 54\% en ROUGE-2.

Se muestran ambos resúmenes en las figuras \ref{fig:bm25} y \ref{fig:textrank}.

\begin{figure}[h!]
\caption{Documento de ejemplo del conjunto de datos de DUC 2002.}
\label{fig:text}
\raisedtext{{\scriptsize \parbox{\linewidth}{
\begin{enumerate}
\itemsep0em
\item Oscar Trophy Has No Copyright
\item By <NAME>
\item Associated Press Writer
\item LOS ANGELES (AP)
\item The Oscar statuette, one of the most recognizable images in the entertainment world, has no copyright protection, a federal judge has ruled.
\item The small Academy Award statue is part of the public domain, U.S. District Court Judge Laughlin Waters said in a ruling released Thursday.
\item The decision was a setback for the Academy of Motion Picture Arts and Sciences, which had sued a Chicago-based manufacturer of an employee-incentive trophy similar to the Oscar.
\item Academy President <NAME> said the ruling ``comes as a shock to me''.
\item The academy said it would appeal.
\item The academy claimed that the Star Award, the trophy look-alike made by Creative House Promotions, violated copyright laws, diluted the academy's trademark and represented unfair competition.
\item The Star Award depicted a naked, muscular male much like the Oscar, just two inches shorter and holding a star instead of a sword.
\item It had a gold finish similar to the Oscar, and stood on a circular gold cap mounted on a cylindrical base.
\item Although Waters acknowledged that the Creative House trophy is ``very similar'' to the Oscar, he rejected all of the academy's legal claims, saying that the statuette became part of the public domain prior to Jan. 1, 1978, the effective date of the Copyright Act of 1976.
\item The film industry's top award was distributed from the first ceremony in 1929 until about 1941 without the ``c'' mark indicating a copyright.
\item The judge ruled, too, that the Oscar not only was an honorary award but also was used to promote the film industry, and therefore did not have a ``limited purpose,'' as required by the copyright act.
\item The academy noted that the ruling applied only to the statuette and that the academy's trademark and service marks for the Oscar and the Academy Award names and symbols are unaffected.
\item ``We are surprised that the court would base its decision on events which occurred half a century ago, overlooking the meticulous fashion in which the Academy has protected the integrity of its institutional symbol for decades,'' Malden said in a statement.
\end{enumerate}
}}}
\end{figure}

\begin{figure}[h!]
    \caption{Resumen generado por TextRank usando similitud BM25.}
    \label{fig:bm25}
    \raisedtext{{\scriptsize \parbox{\linewidth}{
    The small Academy Award statue is part of the public domain, U.S. District Court Judge Laughlin Waters said in a ruling released Thursday.
The academy claimed that the Star Award, the trophy look-alike made by Creative House Promotions, violated copyright laws, diluted the academy's trademark and represented unfair competition.
Although Waters acknowledged that the Creative House trophy is ``very similar'' to the Oscar, he rejected all of the academy's legal claims, saying that the statuette became part of the public domain prior to Jan. 1, 1978, the effective date of the Copyright Act of 1976.
    }}}
\end{figure}

\begin{figure}[h!]
    \caption{Resumen generado por la versión original de TextRank.}
    \label{fig:textrank}
    \raisedtext{{\scriptsize \parbox{\linewidth}{
    Although Waters acknowledged that the Creative House trophy is ``very similar'' to the Oscar, he rejected all of the academy's legal claims, saying that the statuette became part of the public domain prior to Jan. 1, 1978, the effective date of the Copyright Act of 1976.
The judge ruled, too, that the Oscar not only was an honorary award but also was used to promote the film industry, and therefore did not have a ``limited purpose,'' as required by the copyright act.
The academy noted that the ruling applied only to the statuette and that the academy's trademark and service marks for the Oscar and the Academy Award names and symbols are unaffected.
    }}}
\end{figure}


\subsection{Resultados}
Los mejores resultados se obtuvieron usando BM25 y BM25+. El incremento más alto se logró al reemplazar los valores negativos por la constante $\varepsilon$ = 0,25 en la ecuación 3, dando una mejora total de 2,92\% para BM25 y 2,60\% para BM25+. En el Cuadro 1 se detallan las alternativas ensayadas.

\begin{table}
\caption{Resultados de las propuestas.}
\begin{center}
\begin{tabular}{l*{5}{c}r}
\hline
\rule{0pt}{12pt}
Método & ROUGE-1 & ROUGE-2 & ROUGE-SU4 & Mejora \\[2pt]
\hline\rule{0pt}{12pt}\mbox{}\par\nobreak
BM25 ($\varepsilon$ = 0,25) & 0,4042 & 0,1831 & 0,2018 & 2,92\% \\
BM25+ ($\varepsilon$ = 0,25) & 0,404 & 0,1818 & 0,2008 & 2,60\% \\
Similitud coseno & 0,4108 & 0,177 & 0,1984 & 2,54\% \\
BM25+ (IDF = log($N$/$N_i$)) & 0,4022 & 0,1805 & 0,1997 & 2,05\% \\ 
BM25 (IDF = log($N$/$N_i$)) & 0,4012 & 0,1808 & 0,1998 & 1,97\% \\ 
Subcadena común & 0,402 & 0,1783 & 0,1971 & 1,40\% \\
BM25+ ($\varepsilon$ = 0) & 0,3992 & 0,1803 & 0,1976 & 1,36\% \\ 
BM25 ($\varepsilon$ = 0) & 0,3991 & 0,1778 & 0,1966 & 0,89\% \\
\textbf{TextRank} & \textbf{0,3983} & \textbf{0,1762} & \textbf{0,1948} & \textbf{--}\\
BM25 & 0,3916 & 0,1725 & 0,1906 & -1,57\% \\
BM25+ & 0,3903 & 0,1711 & 0,1894 & -2,07\% \\
Referencia DUC & 0,39 & 0,1689 & 0,186 & -2,84\% \\ [2pt]
\hline
\end{tabular}
\end{center}
\end{table}


Los tiempos de ejecución también se superaron. Se pudieron procesar los 567 documentos de la base de datos de DUC2002 utilizando 84\% del tiempo requerido por la versión original.

El resultado de la métrica de similitud coseno también fue satisfactoria, presentando una mejora de 2,54\% por sobre el método original. A su vez, los métodos de secuencias de máxima longitud también mostraron una mejora considerable: cerca del 1,40\% por sobre TextRank. 

En la Figura 1 se comparan las distintas técnicas.

\begin{figure}[h!]
    \centering
    \includegraphics[width=1\textwidth]{rouge-scores.pdf}
    \caption{Comparación de métricas.}
\end{figure}


\section{Integración a Gensim}
La integración del módulo a Gensim\footnote{Pull request: \url{https://github.com/piskvorky/gensim/pull/324}} se desarrolló a partir de la última versión a la fecha, la 0.11.1-1. 
Se agregaron a la biblioteca las dos funcionalidades descriptas en el desarrollo del presente trabajo: la extracción de palabras claves y la generación automática de resúmenes extractivos.

En la integración se incluyen tres casos de uso:
\begin{itemize}
\item Generación de resúmenes automáticos dado un texto. En este caso la función requiere una cadena de texto con el documento a resumir, y devuelve el texto resumido. 
\item Selección de documentos más importantes dado un corpus. Este caso es similar al anterior, con la diferencia de que se recibe un listado de documentos (que pueden ser oraciones de un texto) y se devuelve un listado de aquéllos más importantes.
\item Obtención de palabras claves de un texto. En este caso se devuelve un listado de palabras clave dada una cadena de texto.
\end{itemize}


\section{Conclusiones}
En este trabajo se analizaron variantes al algoritmo de TextRank. A partir del mismo se propusieron e implementaron optimizaciones cuyos resultados fueron significativos: se obtuvo una mejoría del 2,92\% por sobre el método original. Este número es notable si se tiene en cuenta que TextRank por sí solo performa 2,84\% por sobre el estándar de comparación.

Las evaluaciones fueron hechas con los mismos conjuntos de datos y métricas utilizados en competencias internacionales, validando así las mediciones.

Finalmente, la adaptación a la biblioteca de lenguaje natural Gensim también resultó sencilla gracias a las facilidades que provee su interfaz de programación y su gran cantidad de métodos.

Queda para próximos trabajos explorar alternativas para la extracción de palabras claves, y el ensayo de distintos métodos algebraicos, haciendo uso del modelo del espacio vectorial.


\newpage
\section{Anexo I: modificaciones}
Además de las mejoras descriptas en la sección “Mejoras”, también se ensayaron otras ideas cuyos resultados no fueron tan destacables como los mencionados.

Como se explicó anteriormente, las modificaciones apuntan a cambiar el criterio de similaridad entre oraciones. Algunas de las que se tuvieron en cuenta tienen un concepto similar a la de subcadena común, que otorga puntajes de acuerdo a la cantidad de unidades léxicas en orden que estén presentes en las dos oraciones. Estas métricas utilizan las técnicas usadas por el paquete ROUGE: los métodos de subsecuencia de palabras común, subsecuencia de palabras común con peso, bigramas comunes y SU4 son idénticos a los usados por los métodos ROUGE-L, ROUGE-W, ROUGE-2 y ROUGE-SU4 respectivamente.

Se implementaron también métricas de distancias de Levenshtein \cite{levenshtein}, un método que pondera con un valor más alto a las palabras clave del texto, y una lógica de envejecimiento que asigna puntaje adicional a aquéllas palabras que se mencionaron más recientemente.

Finalmente, se experimentó también reemplazando el algoritmo de PageRank (que utiliza como solución el autovector asociado al valor asociado más grande de la matriz de similaridad) por el de HITS (que utiliza el vector singular asociado al valor singular más grande de la matriz) \cite{kleinberg}; y también se hicieron pruebas aproximando la solución al reducir el rango de la matriz con DVS. 

\subsection{Resultados}
\begin{tabular}{l*{5}{c}r}
    \hline
    \rule{0pt}{12pt}
	Método & ROUGE-1 & ROUGE-2 & ROUGE-SU4 & Mejora \\[2pt]
    \hline\rule{0pt}{12pt}\mbox{}\par\nobreak
	BM25 ($\varepsilon$ = 0,25) & 0,4042 & 0,1831 & 0,2018 & 2,92\% \\ 
	BM25+ ($\varepsilon$ = 0,25) & 0,404 & 0,1818 & 0,2008 & 2,60\% \\ 
	Similitud coseno & 0,4108 & 0,177 & 0,1984 & 2,54\% \\ 
	BM25+ (IDF = log($N$/$N_i$)) & 0,4022 & 0,1805 & 0,1997 & 2,05\% \\ 
	BM25 (IDF = log($N$/$N_i$)) & 0,4012 & 0,1808 & 0,1998 & 1,97\% \\ 
	Subcadena común & 0,402 & 0,1783 & 0,1971 & 1,40\% \\
	Subsec. palabras común & 0,4032 & 0,1773 & 0,1968 & 1,38\% \\ 
	Subsec. palabras común con peso & 0,4032 & 0,1773 & 0,1968 & 1,38\% \\ 
	BM25+ ($\varepsilon$ = 0) & 0,3992 & 0,1803 & 0,1976 & 1,36\% \\ 
	BM25 ($\varepsilon$ = 0) & 0,3991 & 0,1778 & 0,1966 & 0,89\% \\ 
	Distancia temporal & 0,3992 & 0,1762 & 0,195 & 0,48\% \\ 
	Levenshtein & 0,3961 & 0,1781 & 0,1955 & 0,38\% \\ 
	Subsecuencia común & 0,396 & 0,1775 & 0,1949 & 0,22\% \\ 
    \textbf{TextRank} & \textbf{0,3983} & \textbf{0,1762} & \textbf{0,1948} & \textbf{--} \\
	SU4 & 0,3955 & 0,1732 & 0,1924 & -0,73\% \\ 
	Prioridad keywords & 0,3952 & 0,1721 & 0,1915 & -1,03\% \\
	Peso de conceptos & 0,3953 & 0,1713 & 0,1914 & -1,14\% \\
	Distancia temporal invertida & 0,3913 & 0,1725 & 0,1912 & -1,53\% \\
	BM25 & 0,3916 & 0,1725 & 0,1906 & -1,57\% \\
	HITS & 0,3914 & 0,1699 & 0,1898 & -2,03\% \\
	BM25+ & 0,3903 & 0,1711 & 0,1894 & -2,07\% \\
	HITS + DVS & 0,3912 & 0,1686 & 0,189 & -2,33\% \\
	Referencia DUC & 0,39 & 0,1689 & 0,186 & -2,84\% \\
	Bigramas comunes & 0,393 & 0,1633 & 0,1842 & -3,42\% \\
	Weighted LCSubstring & 0,3755 & 0,1509 & 0,1729 & -8,79\% \\
	Levenshtein normalizado & 0,348 & 0,1374 & 0,1565 & -16,28\% \\
\end{tabular}

\newpage
\bibliography{informe}{}
\bibliographystyle{babunsrt}


\end{document}
