Retokenizando con spaCy

Para los que no están en contexto, spaCy es una librería de Python que provee funciones de PLN (procesamiento de lenguage natural, “NLP” en inglés) de una forma por demás fácil en comparación con, por ejemplo, NLTK.

Aunque conocía de su existencia, no había trabajado con spaCy hasta ahora que lo probé en el proyecto que tengo entre manos en el trabajo. Me era más familiar NLTK a pesar de haberlo usando en su mayoría en la versión 1 (van en la 3.5 al momento de escribir esto), pero para varias tareas spaCy es mucho más “directo”. Digamos que NLTK te da mucho poder, pero hay que ser mucho más específico al momento de manejarlo. En cambio, spaCy realiza muchas más acciones con menos interacción, lo cual puede ser bueno o extremo dependiendo del objetivo.

Lo interesante aquí para mí es nlp.pipeline. Una simple función, que por lo general la llaman nlp (pero uno puede definir el nombre),  aplica una serie de algoritmos de análisis y reconocimiento, pero antes realiza el proceso de “tokenizar” el texto, es decir, dividirlo en entidades llamadas “tokens”, que son secuencias de caracteres agrupados en unidades semánticas. Es fácil irse con la finta de que todos los tokens son palabras, pero no es así. Existen además diferentes maneras de tokenizar, y dependiendo de la usada es el resultado que se tendrá. Por ejemplo, una de las maneras más fácil de tokenizar es agrupando caracteres en un texto separado por espacios, como este post, por ejemplo. Obviamente una tokenización así no serviría en idiomas como el japonés, donde las palabras no están separadas por espacios, pero ésa es otra historia. También es necesario destacar que separar por espacios tampoco es una forma ideal de tokenizar, incluso lenguajes como inglés, pero en sí no se puede dar una respuesta correcta sin saber cuál es el objetivo final. De eso depende la forma de crear tokens.

En el caso del análisis que estaba realizando (en inglés), requería manejar palabras como “well-known”, “state-of-the-art”, es decir, palabras compuestas por múltiples otras palabras, unidas por un guión (entre otros casos que no necesito nombrar), como un token. El problema es que el tokenizer de spaCy separa las palabras también por guiones, y estos a su vez forman tokens. Por ejemplo:

“well-known”

es tokenizado como

“well”, “-“, “known”

Cada elemento es un token, así que contiene más que el simple texto: su función gramatical, su forma base, entre otras cosas, todo gracias a que spaCy ejecuta las funciones de reconocimiento y análisis después de la tokenización, pero todo sucede dentro del mismo pipeline. Además, como cada token es identificado por separado, casos como el de “state-of-the-art” deben ser tratados ya que la palabra completa es un adjetivo, pero “art” por sí mismo es correctamente identificado como sustantivo. Algo se tiene que hacer.

Continue reading “Retokenizando con spaCy”

Título de canción de Spotify en Xmobar

Aunque sé que Xmobar tiene Mpris1 y Mpris2, resulta que no lo instalé con soporte para ninguno, por lo que si quería poner el título de la canción que está siendo reproducida en Spotify, tenía que hacerlo a mano.

Tenía un buen rato de no hacer un script de estos. Quizá haya mejores alternativas, pero para algo que me tomó unos 20 minutos, creo que cumple su objetivo:

#!/bin/bash

spotify_pid=`pgrep spotify | head -1`

if [[ ! -z $spotify_pid ]]; then
   found=false
   while [ "$found" = false ] && IFS= read -r line; do
      pid=`echo $line | awk '{ print $3 }'`
      if [ "$pid" = "$spotify_pid" ]; then
         title=`echo $line | awk '{$1=$2=$3=$4=""; print $0 }' | tr -s ' '`
         echo "Spotify: ${title} | "
         found=true
      fi
   done < <(wmctrl -lp)
fi

El resultado:

Applicative Functors

Como mencioné en el escrito anterior de esta serie, los Applicative Functors son extensiones naturales de los Functors. ¿Cuál es la diferencia entonces?

Cuando hablamos de Functors, especificamos que estos saben cómo aplicar una función a los elementos que contienen, y el resultado queda “envuelto” en otro Functor del mismo tipo (lo que se conoce como endomorfismo). Pero ¿qué pasa si la función que queremos aplicar está contenida dentro de un Functor?

Recordemos que un para mapear una función en un Functor (levantarla a su contexto), la definición es:

map (f: A => B): F[A] => F[B]

Se puede apreciar que f es simplemente una función que toma valores de tipo A y regresa valores de tipo B; la función no está contenida en ningún contexto. Entonces, si tenemos algo como:

(f: F[A => B]): F[A] => F[B]

no concuerda con lo que map espera, puesto que la función ya está dentro del Functor, y map espera que no lo esté.

Los applicative entran en escena aquí. Definidos en una typeclass, definen 2 operaciones básicas:

Continue reading “Applicative Functors”

Functors – Más detalles

Ya he mencionado un poco acerca de Functors cuando hablé de Monads. Aquí ampliaré un poco al respecto.

Matemáticamente hablando, un functor es un tipo de “mapeo” entre categorías… sí, esa definición no ayuda mucho. Supongamos que tenemos dos conjuntos C y D, y objetos X que pertenecen a C.  Un functor F asocia a esas X con un objeto F(X) que pertenece a D (tomado tal cual de la definción en Wikipedia). Si hablamos de morfismos, asocia X -> Y que pertenecen a C con F(X) -> F(Y) que pertenecen a D.

functor

Muchas matemáticas de por medio…

En lo que concierne a programación funcional, un functor es una typeclass cuyos miembros deben saber mapear un morfismo que toma un valor y lo transforma en otro, sin tener que “sacarlo” para aplicarlo. Esos “morfismos” son simplemente funciones que toman un argumento del tipo de datos que envuelve el Functor y regresan otro tipo de datos (que puede ser que sea el mismo).

Demasiada confusión…

Continue reading “Functors – Más detalles”

Semigrupos y monoids

Una vez que hemos entendido lo que son las typeclasses y cómo implementarlas en Scala, lo que sigue es hablar de abstracciones,

Muchos programadores se asustan cuando leen algo que tiene que ver con teoría de categorías o matemáticas abstractas; después de todo, se puede programar bien sin meterse en tantos líos. No obstante, hay un principio que todo programador conoce: DRY (Don’t Repeat Yourself), que básicamente se refiere a no repetir el mismo código en diferentes partes; de hecho, es de lo más importante que se aprende cuando se aprende programación estructurada: si vas a usar una serie de instrucciones en más de un lugar, mejor júntalas, ponlas en un método por separado y mándalo llamar cada vez que lo necesites con los datos que necesites procesar. Simple.

Las abstracciones matemáticas son exactamente lo mismo, solamente llevado a más alto nivel: si existe un patrón que se repite constantemente en diferentes programas, ¿por qué no abstraerlo en código separado y llamarlas con los datos necesarios?

Continue reading “Semigrupos y monoids”

Typeclasses

Cuando se lee el término “typeclasses” por primera vez, causa confusión debido a que pensamos o en tipos o en clases, pero no en un término compuesto por ambas palabras. No obstante, el concepto es simple y muy poderoso, y seguramente quienes tienen experiencia con Java o lenguajes similares habrán usando algo similar sin saberlo.

Continue reading “Typeclasses”

Composición de funciones en Scala

La idea principal en programación funcional es llevar a cabo el proceso mediante la aplicación de funciones sin guardar estado (sin modificar los valores originalmente proveídos). Por ello, y al igual que en álgebra, es posible crear una función compuesta, que no es nada más que la aplicación sucesiva de dos funciones. Obviamente, hay que tener cuidado en que el valor de retorno de la primera función sea del tipo del argumento que la segunda función espera.

Wikipedia muestra una imagen que ilustra claramente el concepto de composición de funciones.

Compfun

La composición de funciones se define con el signo ・, que indica que la primera función se aplica al resultado de aplicar la segunda función al parámetro recibido. Usando el ejemplo de la imagen y definiendo h = g ・f, tenemos que h(a) = @, puesto que h se define aplicando g(f(a)).

El mismo concepto se aplica en programación funcional. Supongamos que tenemos las siguientes funciones:

 def toInt(s: String) = s.toInt
 def addOne(i: Int) = i + 1
 def by4(i: Int) = i * 4

Scala tiene 2 operadores para componer funciones: compose y andThen. La diferencia es que mientras f compose g es f(g(x)), f andThen g es g(f(x)). Por tanto, si queremos definir una función que primero convierta la cadena recibida en entero y después le sume uno a ese entero, podemos hacerlo de dos formas:

  /*
    With compose:
    composed1 = addOne(toInt(x))
   */
  val composed1 = addOne _ compose toInt

  /*
    With andThen
    composed2 = addOne(toInt(x))
   */
  val composed2 = toInt _ andThen addOne

Es entonces fácil ver que estas 2 funciones compuestas (composed3 y composed4) no son lo mismo:

val composed3 = addOne _ compose by4
val composed4 = addOne _ andThen by4

Aplicando las funciones compuestas definidas:

val strFunctions = List(composed1, composed2)
val intFunctions = List(composed3, composed4)

strFunctions foreach (f => println(f("3")))
intFunctions foreach (f => println(f(4)))

Y los resultados son:

4
4
17
20

El concepto de composición de funciones es realmente muy simple, y facilita mucho la creación de nuevas funciones basadas en algunas que ya tengamos definidas.

Como nota adicional, en Haskell es mucho más fácil crear una función compuesta, ya que solo es necesario usar “.”:

import Control.Monad

main = do
 f ← liftM(composed1) $ getLine
 print f
 where composed1 = addOne . toInt
 
addOne ∷ Int → Int
addOne = (+1)

toInt ∷ String → Int
toInt x = read x ∷ Int

El “.” en Haskell funciona como el compose en Scala; además, hay diferentes formas de hacer un programa como el de arriba, pero en este caso escogí usar liftM.

Cabe mencionar que en Scala también es posible componer 2 funciones monádicas en una usando algo llamado composición Kleisli, pero hay que usar Scalaz para tener acceso a ella. Y no es necesario entender teoría de categorías para usarlas; simplemente hay que cuidar los parámetros y los tipos de datos que regresan las funciones.  Esto es tema de otro post, pero lo pongo aquí por si alguien se interesa pueda ir investigando por su cuenta.

Detectando si hay monitor conectado en el puerto HDMI con Haskell

Generalmente hay 2 lugares en donde uso la laptop:

  • En mi escritorio, donde la conecto a un par de monitores, uno de ellos por HDMI).
  • En cualquier otro lugar.

Como uso XMonad, la posición de algunas barras personalizadas varía dependiendo de si estoy usando el monitor de la laptop o el de HDMI. El cambio siempre lo he he hecho manualmente comentando o habilitando un par de líneas en el xmonad.hs, pero quería automatizar el proceso de ser posible. Tenía rato que no usaba Haskell en forma, así que…

Básicamente, lo que necesito es hacer esto en Haskell:

xrandr | grep HDMI1 | cut -d " " -f2

Me eché un clavado en la documentación, y encontré la librería System.Process, concretamente la función createProcess, la cual está definida de la siguiente forma:

createProcess :: CreateProcess -> IO (Maybe Handle, Maybe Handle, Maybe Handle, ProcessHandle)

Donde CreateProcess está definido como se menciona acá:

http://hackage.haskell.org/package/process-1.2.0.0/docs/System-Process.html#t:CreateProcess

Lo que necesito entonces es crear un proceso por cada comando que quiero ejecutar, pero pasar los resultados de uno al siguiente (pipe).  Por tanto, necesito  declarar CreateProcess de la siguiente manera:

Continue reading “Detectando si hay monitor conectado en el puerto HDMI con Haskell”

Implementando PageRank

Tuve oportunidad de leer este artículo técnico de Stanford, titulado “Searching the Web”:

 http://ilpubs.stanford.edu:8090/457/

Básicamente, es una explicación de cómo funcionan las búsquedas en internet; muestra lo que era el state-of-the-art en ese tópico, incluyendo el algoritmo que fue el comienzo de Google: PageRank.

Existen muchas páginas que describen en detalle cómo funciona esta técnica; incluso, el artículo mencionado arriba lo menciona de forma entendible, así que no ahondaré mucho en detalles: PageRank determina el grado de importancia de una página con base en el número de páginas que tienen ligas hacia ella. y del mismo grado de importancia de cada una de esas páginas. Es decir: una página será más relevante si muchas otras páginas ligan a ella, o también si las páginas que ligan a ella son a su vez relevantes.

Consideremos el caso de una red que sólo tiene 4 sitios: A, B, C y D, y que están ligados de la siguiente forma:

pagerank-example1

Gracias a PageRank, podemos determinar la relevancia de cada uno de estos sitios, usando la fórmula que aparece en el artículo arriba mencionado:

(1)   \begin{equation*} r(i) = \sum_{j \epsilon B(i)} r(j) / N(j) \end{equation*}

Donde r(i) es el pagerank de la página i, r(j) el pagerank de la página j, y N(j) es el número de links que salen de la página j. B(i) es el conjunto de páginas que tienen liga hacia la página i.

A ojo de buen cubero, la página C tendría un valor de relevancia mayor al de las otras páginas por haber 2 que ligan hacia ella (A y B).

Existen un par de problemas con esta fórmula: si encontramos una serie de páginas que sólo tienen ligas entre ellas, o si llegamos a una página que no tiene ligas a ningún lado, a final de cuentas la relevancia se centrará o en las páginas dentro de un cluster (para el primer caso) o convergerá a 0 (en el segundo caso). En el artículo, el primer caso se nombra como rank sink, mientras que el segundo se nombra rank leak.

Se propone también el modelo del Random Surfer para describir el comportamiento de un usuario: o bien puede seguir las ligas de una página a otra, o bien se puede aburrir y “brincar” directamente a una página.

Para resolver los problemas antes mencionados e implmentar al Random Surfer, lo siguiente es propuesto:

  • Eliminar todas la páginas que no tengan ligas externas (leaks). No necesariamente la mejor solución.
  • Suponer que los leak tienen ligas a todas las otras páginas.
  • Agergar un valor que modele al Random Surfer. Este valor se denomina d (decay factor), y es un valor 0 < d < 1, indicando qué tan frecuentemente el Random Surfer se “aburre” de una página y brinca a otra aleatoriamente.

La fórmula anterior entonces cambia a:

(2)   \begin{equation*} r(i) = d * \sum_{j \epsilon B(i)} r(j) / N(j) + (1 - d) / m \end{equation*}

Donde d es el decay factor explicado arriba, m es el número total de páginas en la red, y el factor (1 – d) / m hace que la suma de todos los pagerank de las páginas consideradas sea igual a 1. Por supuesto, dependiendo del manejo de los sinks y leaks, los resultados varían.

Para información más detallada, consulten el artículo.

Power iteration

Es obvio pensar que teniendo tantas páginas que revisar necesitamos un método que sea lo más eficiente posible. Page y Brin mencionan que es posible hacer el cálculo de PageRank usando el método llamado Power Iteration, y que en un número relativamente bajo de iteraciones ( < 100 ) los valores convergen. Omito aquí la explicación técnica de obtener el principal eigenvector de la matriz de pagerank, y me centro específicamente en explicar el método con estructuras simples:

  1. Inicializamos un vector s de longitud m = número de páginas. Cada valor es el pagerank de la página en cuestión. El valor inicial puede ser aleatorio, pero los autores lo inicializan en 1/m
  2. Usando la fórmula (2), calculamos los nuevos valores de pagerank y los guardamos en un vector r.
  3. Calculamos la L1 Norm de las diferencias absolutas entre rs, y las comparamos con un valor de error máximo e previamente determinado. Si la L1 Norm es menor a e, los valores han convergido y r contiene los pagerank finales de las páginas. Si no, ir a 4.
  4. Asignar a s los valores actuales de r y regresar 2.

Implementación

Como siempre, lo aquí establecido no es la verdad absoluta. Quienes estén interesados en mejorar la implementación o crear la suya propia, ¡adelante!
Continue reading “Implementando PageRank”