TF-IDF: pesando las palabras

En el área de recuperación de información, la idea es obtener una serie de documentos considerados relevantes con respecto a ciertas palabras o expresiones. En términos generales, la idea es encontrar los documentos que más se acerquen a una búsqueda realizada con palabras clave o con expresiones más complicadas (como lenguaje natual propiamente). Ejemplo: una búsqueda en Google. Ponemos lo que estamos buscando y Google muestra una serie de resultados que calcula como importantes para esa búsqueda.

Es evidente que no existe una sola forma de encontrar los documentos, y más que encontrarlos, de asignarles un orden. Es muy fácil tener una colección de documentos y hacer una especie de consulta SQL donde regresemos solamente los documentos que contienen al menos una de las palabras buscadas, pero esto solo nos va a regresar los documentos en el orden que la base de datos los encuentra (o en el que le asignemos en el SELECT). Esta forma de búsqueda es la más simple de todas: búsqueda binaria. Pero, ¿se imaginan que ésta fuera la técnica que Google usara? ¿Cuántos documentos no tendríamos que revisar hasta encontrar (si es que lo hacemos) uno que en verdad contiene la información que se desea encontrar?

ejresgoogle

Google reporta 850,000 resultados para la búsqueda “Vacaciones en Cancún”, pero en la realidad solo muestra hasta el número 1,000. No obstante, son pocas y contadas las veces en las que revisamos más de 100 documentos. El orden importa, y es justamente lo que la recuperación de información trata de resolver.

Una búsqueda binaria no analiza más allá de si un documento contiene o no una o varias palabras; por tanto, así como regresa documentos en los que la palabra X aparece 1 vez, también regresa otros donde aparece 100 veces, por poner un ejemplo. ¿Cuál documento es entonces más importante?

La asignación de orden  se puede realizar de distintas maneras: fecha, autor, número total de palabras en el documento, etc. Entre las muchas formas de llevar a cabo esta tarea, existe la de asignarle peso a las palabras, es decir, de tratar de calcular qué palabras son más relevantes en un texto, y con base en eso decidir cuál documento es más probable que contenga la información buscada.

Una de las formas más fáciles de asignarle peso a las palabras es contar el número de veces que aparecen en un documento. Así, si buscamos por ejemplo “quetzal ave” dentro de una serie de documentos, en teoría los que contengan esas palabras con más peso son los que aparecerán primero. Pero, y como ya se pueden imaginar, esto tiene desventajas:

Supongamos que tenemos una colección de 3 documentos; en todos aparecen las palabras “quetzal” y “ave”, pero uno de los documentos contiene el triple o el cuádruple de tamaño que los otros dos, por lo que esas palabras aparecen más veces, lo que hacen que tengan más peso y, por ende, que ese documento sea, a primera vista, más “relevante” que otros. Es claro que un documento grande no forzosamente es más importante que uno más pequeño. Por tanto, contar solamente el número de palabras de un documento para asignar el peso a cada una necesita tomar en cuenta también la cantidad de documentos en los que aparece esa palabra, y con ese dato, normalizar el valor para tratar de nivelar todas las palabras que aparecerán en la colección.

Ya entrando en tecnisismos: contar el número de veces que una palabra aparece en un documento nos da el peso local de ella en el documento en cuestión. Contar el número de documentos en los que aparece ese palabra aunque sea una vez, nos da el peso global de ella con respecto a la colección de documentos que se está analizando.

Comprendiendo lo anterior, ahora es solamente cuestión de ponerle nombre bonito a esos conceptos y definirlos formalmente. El peso local se denomina Term Frequency (TF), y se calcula contando el número de veces que la palabra aparece en el documento dividido entre el número total de palabras contenidas en él. Es decir:

TFi,d = term count  /number of words

Por su parte, el peso global se denomina Inverse Document Frequency (IDF), y se calcula dividiendo el número total de documentos de la colección entre el número de documentos que contienen la palabra, y se calcula el logaritmo de ese valor:

IDFi = log (number of documents in collection /  number of documents containing word i)

Seguramente más de alguno se habrá fijado en el denominador de esta ecuación: si la palabra a buscar no está contenida en ningún documento, tenemos una división entre cero. Para evitarla, se acostumbra sumar 1 al denominador:

IDFi = log (number of documents in collection / 1 + number of documents containing word i)

IDF sirve para penalizar a palabras que estén en muchos documentos, y de la misma manera, para valorar más a palabras que estén en pocos. ¿Por qué? Porque se parte de la premisa que una palabra que no sea tan común proporciona más información (es más valiosa) que una que es más común (y por ende, que tiende a aparecer en un mayor número de documentos).

Ahora, solamente juntamos ambos pesos, y a esta técnica para asignar pesos a las palabras le llamamos simplemente TF-IDF (generalmente lo digo en inglés, pero en español es tal cual “te efe i de efe), y la fórmula para calcularlo es:

TF-IDFi,d = TFi,d x IDFi

Obviamente hay que hacer el cálculo para cada palabra en cada documento. En la fórmula de arriba, “i” es la palabra y “d” es el documento en cuestión, por lo que se leería “el tf-idf de la palabra i en el documento d es igual a…”.

Y con este método podemos comenzar a jugar de forma más entretenida 爆笑

Como ya se pueden imaginar, TF-IDF por sí solo nos podría servir para asignarle orden a una serie de documentos de acuerdo con el peso de los términos a buscar, pero por sí solo no es una técnica muy eficaz. No obstante, es un cálculo base para otras técnicas. El hecho de poder manejar matemáticamente las palabras de un documento abre la puerta a poder usar fórmulas o métodos ya establecidos y comprobados. siendo una de las más importante el álgebra lineal. Dicho sea de paso, el curso de esta materia que llevé en la universidad fue muy bueno… pero como por lo general no se utiliza para los problemas más comunes que se resuelven, es normal que poco a poco se vaya olvidando. Así que, si están estudiando o acaban de estudiar álgebra lineal, guarden los conceptos en la mente si es que quieren estudiar algo como procesamiento de imágenes o de lenguaje natural, porque les va a ser muy útil. En mi caso, he tenido que volver a repasar un montón de conceptos que estudié en el 2do. semestre de la universidad, allá en Guadalajara.