El jueves 16 de mayo hablaré en el Grupo de Interés Local de Madrid de R sobre lematizadores probabilísticos.

Hablaré sobre el proceso de lematizacion y trataré de mostrar su importancia dentro del mundo del llamado procesamiento del lenguaje natural (NLP). La lematización es un proceso humilde dentro del NLP del que apenas nadie habla: su ejercicio solo ha hecho famoso a Martin Porter. Lo eclipsan otras aplicaciones más vistosas, como el siempre sobrevalorado análisis del sentimiento. Sin embargo, es una pieza fundamental que subyace (o debería subyacer) en cualquier aplicación seria que analice textos.

En la charla repasaré las tres grandes familias de soluciones para el problema de la lematización:

• las basadas en reglas duras,
• las basadas en diccionarios y, finalmente,
• las más interesantes, las probabilísticas.

Y, en particular, describiré con cierto detalle —aunque tratando de obviar los aspectos técnicos más áridos— un algoritmo que combina oportunísticamente diccionarios y modelos ocultos de Markov y que debería ver la luz en producción dentro del conjunto de APIs lingüísticas de Molino de Ideas.

Hace unos días implementé un proceso MapReduce usando mincedmeat, un pequeño entorno en Python para desarrollar este tipo de procesos distribuidos. El código y los datos pueden descargarse de este enlace.

Los datos de partida están en 249 ficheros de unos 25kb que contienen filas del tipo

journals/algorithmica/HarelS98:::David Harel::Meir Sardas:::An Algorithm for Straight-Line of Planar Graphs

es decir, publicación, autor (o autores) separados por :: y título de la publicación. Los tres campos están separados por :::.

El objetivo es contar, para cada autor, las palabras que aparecen en el título de sus publicaciones eliminando, si procede, signos de puntuación, palabras excesivamente corrientes (como the), etc.

Si uno ejecuta en su servidor central

carlos@tiramisu:~/curso_dm/prog_03/src$ python wrdcount_mincemeat.py

este quedará esperando a que otras máquinas se ofrezcan a trabajar en el proyecto. En mi caso, que trabajo sólo en una, puedo lanzar en varias sesiones

carlos@tiramisu:~/curso_dm/prog_03/src$ python mincemeat.py -p changeme localhost

También podría lanzarlas en servidores distintos (en cuyo caso tendría que cambiar localhost por la IP del servidor central). Además, casi seguro, habría utilizado una contraseña, changeme en este caso, menos obvia.

En cualquier caso, las otras sesiones que lanzo (en la misma u otra máquina) reciben instrucciones (código y datos) del servidor central y ejecutan las tareas de la parte map. Una vez que terminan, se les asignan las tareas reduce y el resultado final se agrega en un único fichero (predefinido en el programa wrdcount_mincemeat.py del servidor).

En wrdcount_mincemeat.py se definen dos funciones, mapfn y reducefn que son las que ejecutan los mapeadores y los reductores, es decir, las sesiones a las que el servidor central asignan tareas, y que son en este caso

def mapfn( key, value ):

	import re, string	

        #Truncated because of lack of space
        #The original dict contained a few docen terms
        allStopWords={'about':1, 'above':1, 'after':1, 'again':1} 

        for line in value.splitlines():
                trozos = line.split(":::")

                autores = trozos[1].split("::")

                palabras = trozos[2].split(" ")
                palabras = [ re.sub('[\W_]', '', x).lower() for x in palabras]

                palabras = list( set(palabras) - set( allStopWords.keys() ) )

                for autor in autores:
                        for palabra in palabras:
                                yield autor + "|" + palabra, 1

y

def reducefn(key, value):
        return key, len(value)

respectivamente. El resto del código en wrdcount_mincemeat.py se reduce a leer los ficheros de entrada,

text_files = glob.glob( "../hw3data/*")

def file_contents(file_name):
        f = open(file_name)
        try:
                return f.read()
        finally:
                f.close()

source = dict((file_name, file_contents(file_name)) for file_name in text_files)

en un diccionario (algo tal vez poco eficiente en términos de uso de la memoria) y a declarar un objeto de la clase Server y sus métodos mapfn y reducefn (así como recibir instrucciones sobre qué hacer con la salida del proceso) en

s = mincemeat.Server()

# The data source can be any dictionary-like object
s.datasource = source
s.mapfn = mapfn
s.reducefn = reducefn

results = s.run_server(password="changeme")

f = open("outfile_mincemeat.txt", "w")

print results

for clave, contador in results.values():
	#f.write( key + " " + str(value) + "\n" )
	f.write( clave + " " + str(contador) + "\n" )

f.close()

Nótese también cómo en ese pedazo de código se define la contraseña que deberán utilizar los mapeadores y los reductores.

No es mío, pero sí una pequeña joya que merece la pena dar a conocer. Además de tener aquí, en mi bitácora-vademécum para futura referencia. Es este tutorial para el análisis de datos de Twitter realizado por Gastón Sánchez.

Estoy limpiando mi cartera y antes de mandar unos cuantos legajos al archivador (o al contenedor de reciclaje) quiero dejar nota de sus contenidos para referencia mía y, quién sabe, si inspiración de otros.

El primer artículo es Tackling the Poor Assumptions of Naive Bayes Text Classifiers. Tiene esencialmente dos partes. La primera analiza críticamente el método de clasificación bayesiano ingenuo (naive Bayes) en el contexto de la minería de textos identificando una serie de deficiencias. En la segunda parte, los autores proponen una serie de modificaciones ad hoc para crear un algoritmo de clasificación mejorado.

El segundo, Formulating State Space Models in R with Focus on Longitudinal Regression Models, trata sobre el paquete sspir de R. Sirve para ajustar modelos similares a los lineales generalizados pero que contienen términos que varían en el tiempo. Puede ser usado para modelar series temporales influenciadas por variables adicionales o estudiar el impacto de estas últimas sobre datos que tienen una estructura temporal subyacente. Uno de los casos de uso citados en el artículo, por ejemplo, es el del estudio del efecto de la obligatoriedad del uso del cinturón de seguridad en la serie temporal de fallecidos en accidentes de tráfico.

El tercero, The origin of bursts and heavy tails in human dynamics, se plantea un problema muy interesante. En la sección (a) de

se muestra una sucesión típica de sucesos generados por un proceso de Poisson. En las secciones (b) y (c) se muestra el tiempo de espera entre sucesos consecutivos y su distribución. Sin embargo, en muchos procesos en que interviene el hombre, la distribución es más parecida a la que se muestra en (d). Por ejemplo, en el uso del correo electrónico: a periodos de mucho uso suelen seguir periodos de inactividad. El autor, Barabási, lista otra serie de ámbitos en los que se aprecian patrones similares. Y argumenta finalmente que este tipo de comportamiento es consistente con la coexistencia de varias colas con distintos grados de prioridad.

Es el caso de una persona en su actividad diaria, que incluye revisar su correo electrónico, revisar documentación, realizar llamadas telefónicas, etc. Y cada una de esas colas tienen prioridades diferentes. La actividad observada resultante tiene un comportamiento no poissoniano.

Uno de los pasos previos para realizar lo que se viene llamando minería de texto es lematizar el texto. Desafortunadamente, no existen buenos lematizadores en español. Al menos, buenos lematizadores libres.

Existen el llamado algoritmo de porter y snowball pero, o son demasiado crudos o están más pensados para un lenguaje con muchas menos variantes morfológicas que el español.

Sinceramente, no sé a qué se dedican —me consta que los hay— los lingüistas computacionales de la hispanidad entera: ¿no son capaces de liberar una herramienta de lematización medianamente decente que podamos usar los demás? Lo más parecido a esa herramienta aparentemente inexistente que conozco es Grampal, que funciona a través de una interfaz web.

Y me ha servido para construir un lematizador rudimentario y francamente perfectible:

require( XML )
 
lematiza <- function( frase ){
	palabra <- gsub( " ", "+", frase )
	base.url <- paste(
             "http://cartago.lllf.uam.es/grampal/grampal.cgi?m=etiqueta&e=",
             palabra, sep = "" )
	tmp <- readLines( base.url, encoding = 'utf8' )
	tmp <- iconv( tmp, "utf-8" )
	tmp <- gsub( "&nbsp;", " ", tmp )
	tmp <- readHTMLTable( tmp )
	tmp <- as.character( tmp[[1]]$V3 )
	tmp <- do.call( rbind, strsplit( tmp, " " ) )[,4]
	tmp
}

Con él, desde R,

> lematiza( "des" )
[1] "DAR"
> lematiza( "anduve" )
[1] "ANDAR"
> lematiza( "casitas" )
[1] "CASITA"
> lematiza( "comimos" )
[1] "COMER"
> lematiza( "queremos comer patatas" )
[1] "QUERER" "COMER"  "PATATA"

No es rapidísimo, debería mejorar el tratamiento de la codificación y muchas cosas más.

¿Se anima a mejorarlo alguno de mis lectores?

Es fácil predecir a toro pasado. Casi tan fácil que asestarle una gran lanzada al moro muerto (el refranero es así de incorrecto políticamente, lo siento).

Esas son las ideas que me sugirieron fundamentalmente la lectura del un tanto hagiográfico Superordenadores para ‘predecir’ revoluciones y del artículo al que se refería, Culturomics 2.0: Forecasting large-scale human behavior using news media tone in time and space.

El artículo nos explica cómo utilizando resúmenes de noticias de diversas fuentes era posible haber predicho las revoluciones de Egipto, Túnez y Libia. Y, casi, casi, cómo haber encontrado a Bin Laden.

Pero como en aquel episodio de Sherlock Holmes en el que el perro no ladró, la pieza fundamental no es lo que se cuenta sino lo que se calla: ¿qué otras revoluciones se predijeron erróneamente? ¿Qué de los falsos positivos? ¿No habremos redescubierto una suerte de Nostradamus de silicio?

Merece también la pena echar un vistazo al mapa de civilizaciones que revela el dispositivo:

¿Son Francia y Suráfrica parte de la misma civilización? ¿Y Suiza y Afganistán? ¿Y Canadá está más próximo a Marruecos o Irán que a EE.UU.? ¿Y qué tendrán que ver Noruega y Marruecos?

En fin, que la cosa está aún verde, verde, verde y que, en tanto,… cantos de sirena.

De acuerdo con una observación de Zipf (y supongo que de muchos otros y que no hay que confundir con su ley), la longitud de las palabras más corrientes es menor que las que se usan menos frecuentemente.

Un estudio reciente, Word lengths are optimized for efficient communication, matiza esa observación: la cantidad de información contenida en una palabra predice mejor la longitud de las palabras que la frecuencia de aparición pura. En una comparación entre diversos idiomas europeos, parece manifestarse que palabras que aportan poca información son breves; las que aportan mucha, más largas.

La cantidad de información que transmite una palabra depende del contexto. En un contexto c, la cantidad de información que contiene una palabra w es , el logaritmo de la probabilidad de que w ocurra en dicho contexto. La cantidad global de información que transmite una palabra es la media de dicha cantidad a través de los contextos en que aparece w, es decir

cantidad que puede aproximarse por

Para calcular pueden utilizarse varias técnicas. Por ejemplo, secuencias de palabras (o contextos) tales como “quiero beber…” condicionan la probabilidad del término subsiguiente. Y “cerveza”, “leche” o “agua” será menos informativo (es decir, más probable) que “hidromiel” o “electrones”.

De alguna manera, los hablantes tienden a mantener constante la tasa de transmisión de información acortando lo predecible y haciendo hincapié (y gastando tiempo y sílabas) en los puntos más informativos del discurso.

Y ahora entro en terreno que me es menos propio: la fijación de la sintaxis desde la creación de las primeras gramáticas, la difusión de los libros, la educación, etc. han mantenido el lenguaje relativamente invariable a través de los últimos siglos: los mayores impedimentos para entender textos de hace 400 años son puramente léxicos. Pero eso no ha impedido que hayan evolucionado los contextos y, por lo tanto, la regla que asocia cantidad de información y longitud de palabras.

¿Será el lenguaje que se utiliza en las redes sociales heraldo de movimientos de reajuste tectónico en el lenguaje que lo alinee con el nuevo equilibrio entre las palabras de antaño y los cambios de cantidad de información que han traído los nuevos tiempos?

O así nos cuenta Google. Y me explico rápidamente para que no me demande nadie.

Uno de los servicios de Google con los que he topado recientemente es Google Squared, un buscador muy particular —y que parece funcionar sólo en inglés— que devuelve tablas: uno puede buscar nikon lenses, o statistical software y obtendrá lo que verá al pinchar en los correspondientes enlaces: tablas en las que las filas corresponden a lentes de Nikon o paquetes estadísticos y las columnas a atributos. Es increíble que Google adivine que los relevantes para las lentes son, entre otros, la distancia focal o la apertura mientras que para el software estadístico lo son la licencia o el desarrollador.

Pero, ¿qué pasa si uno quiere la lista de los comunistas más prominentes? En la fecha de la publicación de esta entrada, junto a Lenin, Marx, Stalin y Trotsky, aparecen Ronald Reagan y Hitler. Y de éste último se dice que es judío (y es digno de mención, además, que en lugar de su foto aparece la del Che).

El motivo de este problema reside en la naturaleza de los algoritmos típicamente usados en minería de textos. Mi primer contacto con la disciplina ocurrió en 2004, cuando era empleado de SAS. Un potencial cliente quería un sistema automático de clasificación de sentencias judiciales y SAS había adquirido recientemente una empresa que desarrollaba algoritmos de minería de textos. Como se trataba de un proyecto raro dentro de los muy de andar por casa de la empresa, acabaron asignándomelo.

Y mi primera reacción al estudiar la naturaleza de los algoritmos que se empleaban fue de infinito asombro. Omitiendo los detalles, los análisis partían del estudio de las frecuencias de las distintas palabras en el texto: cada sentencia acababa transformada en un vector de recuentos. Suficiente, entiendo, para distinguir homicidios de cohechos, pero no tanto para reconstruir, aunque fuese esquemáticamente, qué ocurrió.

De las 30.000 palabras de las que consta la entrada sobre Hitler en la Wikipedia (en inglés), alrededor de 60 tienen que ver con el judaísmo y alrededor de 30 con el comunismo. Intuyo que estas yuxtaposiciones ocurren en muchos otros textos sobre dicho señor. E intuyo también que muchos métodos de predicción siguen basándose en los mismos métodos de preproceso para matematizar o vectorizar los textos, aplanando así la riqueza y sutileza del lenguaje.

No deja de sorprenderme lo que es posible lograr incluso de esta manera: incluso en este ejemplo que cito, es admirable que una máquina tonta, que no sabe (en nuestro sentido de saber) qué puede ser eso del comunismo, asocie esa cadena de caracteres a otras que identifican a un individuo que todos sabemos que algo tuvo que ver con eso.

También es cierto que experiencias como las de Watson, el ordenador de IBM que venció a los campeonísimos de Jeopardy!, un popular juego de preguntas y respuestas de la TV estadounidense; los traductores automáticos de textos como el de Google (que admiro tremendamente) y el mismo Google Squared parecen indicar que habrá progresos.

Pero en tanto llega el futuro, se me ocurren, entre los muchísimos que pudieran hacerse, dos comentarios. El primero: ¿estaremos delegando demasiadas decisiones en máquinas? A la vista de los errores que pueden llegar a cometer, ¿podemos fiarnos demasiado de que puedan gestionar, como apunta el anterior enlace, actividades tan importantes como nuestros ahorros e inversiones?

Y el segundo, tal vez relacionado con el anterior, ¿nos vamos a ver obligados a escribir para las máquinas? El hecho de que algunos de los lectores más importantes de cuanto escribimos sean ordenadores, ¿acabará haciéndonos adecuar nuestro lenguaje a su capacidad y limitaciones de comprensión? En particular, ¿debería yo en esta bitácora escribir como me diera la gana? ¿O me convendría más usar un lenguaje más romo para que Google entendiese mejor qué cuento para que me generase más visitas y fuese capaz de mostrar publicidad contextual más relevante?

¿Dictarán las limitaciones de los ordenadores el criterio para escribir correctamente en el futuro?

No sé si te lo habrás preguntado alguna vez. Ni siquiera lo sabe Google.

Sin embargo, me admira esto.

¿Usáis Wolfram Alpha? ¿Qué os parece?

Hadley Wickman, el autor de plyr, reshape y ggplot2, ha vuelto a la carga en su exitoso empeño por hacernos cambiar de forma de programar en R.

Con su nuevo paquete, stringr, aspira a facilitarnos aún más la vida. En un reciente artículo, enumera sus ventajas:

• Procesa factores y caracteres de la misma manera (de verdad, muy práctico)
• Da a las funciones nombres y argumentos consistentes
• Simplifica las operaciones de procesamiento de cadenas eliminando opciones que apenas se usan
• Produce salidas que pueden ser utilizadas fácilmente como entradas a otras funciones
• Incorpora funciones para procesar texto presentes en otros lenguajes pero no en R