Category: Programación

Scala permite definir valores, funciones y objetos implícitos. Esto es: que se pueden usar sin necesidad de ser llamados directamente (explícitamente).  Aquí nos ocuparemos de los primeros dos, y hablaré de los objetos implícitos en otro tema donde son ampliamente usados.

Continue reading “Valores y funciones implícitas 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.

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.

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:

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)  

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)  

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 r y s, 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”