Programando la huida...

Entrenando un Perceptrón para que resuelva operaciones lógicas

2010-05-17T11:39:00.004-03:00

Como nos indica el título de este post, hoy voy a mostrar como entrenar un perceptrón para que resuelva operaciones lógicas básicas linealmente separables entre dos variables proposicionales. Como preámbulo, podemos decir por un lado que un perceptrón es una neurona artificial, la unidad de una red neuronal y por otro que una operación es linealmente separable si las clases (resultados distintos) pueden dividirse con una recta. En caso de que esto último no sea posible debe implementarse una solución a partir de redes de preceptrones.

La magia del perceptrón, su diferenciación y la forma en que resuelve las operaciones reside en su vector de pesos que no es ni mas ni menos que un vector numérico que multiplicado por el vector de entrada (datos de usuario) devuelve el resultado correspondiente.

Se puede plantear a grandes rasgos que el periodo de "creación" de un perceptrón consta de las siguientes etapas:

- Presentación de los patrones al perceptrón (se le muestra que tiene que devolver)

- Entrenamiento del perceptrón (se lo prepara para que devuelva lo que debería)

- Se devuelven los resultados con los pesos de su Vector de pesos.

Pasada ya la explicación de que es un perceptrón, a muuuuuuuuy alto nivel y no apta para estudio, vamos a lo que realmente creo que puede ser mi granito de arena. Este granito consta de una simple implementación en python de un perceptrón que resuelve operaciones lógicas linealmente separables. Digo aporte no por la complejidad de este algoritmo sino porque me costó, y en realidad no pude encontrar, en la red algo parecido.

Para correr el script se debe tener instalado:

- numpy

- Gnuplot

Ahi va el código de perceptron.py:

# -*- encoding: utf-8 -*-
# Inteligencia Artificial - UNLu
# Juan Manuel Fernández - 89937

import numpy, Gnuplot, random
from functions import *

ITERATIONS = 50

X00 = raw_input("Patron para (0, 0): ")
X01 = raw_input("Patron para (0, 1): ")
X10 = raw_input("Patron para (1, 0): ")
X11 = raw_input("Patron para (1, 1): ")
VELOCIDAD = raw_input("Velocidad de Aprendizaje: ")
print "Vector de Pesos inicial"
VectorPesos = [0, 0, 0]
VectorPesos[0] = raw_input("Wio[0]: ")
VectorPesos[1] = raw_input("Wio[1]: ")
VectorPesos[2] = raw_input("Wio[2]: ")

if not(VELOCIDAD):
    VELOCIDAD = 1
else:
    VELOCIDAD = int(VELOCIDAD)

PesosDefinitivos = []
for Peso in VectorPesos:
    if not(Peso):
        Peso = round(random.uniform(-0.1 , 0.1), 2)
    else:
        Peso = round(float(Peso), 2)
    PesosDefinitivos.append(Peso)

print PesosDefinitivos

# Inicialización del vector pesos con -0.1 < wio < 0.1
Wio = numpy.array([PesosDefinitivos[0], PesosDefinitivos[1], PesosDefinitivos[2]])

patron = [  [numpy.array([0, 0, 1]), int(X00)],
            [numpy.array([0, 1, 1]), int(X01)],
            [numpy.array([1, 0, 1]), int(X10)],
            [numpy.array([1, 1, 1]), int(X11)]  ]

clase0, clase1 = dividirPuntosPorClase(patron)

encontro_solucion = False
for i in range(ITERATIONS):
    cambios = 0
    for pattern in patron:
        vector_input = pattern[0]
        valor_esperado = pattern[1]
        temp = numpy.dot(Wio, vector_input)
        if ((valor_esperado == 1) and (temp <= 0)):
            Wio += VELOCIDAD * vector_input
            cambios += 1
        elif ((valor_esperado == 0) and (temp >= 0)):
            Wio -= VELOCIDAD * vector_input
            cambios += 1
    if (cambios == 0):
        encontro_solucion = True
        break

if encontro_solucion:
    graficarRecta(Wio, clase0, clase1)
    print "La solucion se encuentra en la iteración " + str(i)
    print "El vector de pesos Wio es " + str(Wio)
else:
    print "El problema no es linealmente separable."
raw_input("-Perceptrón- ha terminado su ejecución...")

Y ahi el código de functions.py:

# -*- encoding: utf-8 -*-
import Gnuplot
from functions import *

def graficarRecta(Wio, clase0, clase1):
    # Despejamos y para formar la ecuación de la recta
    y = Wio[1]
    x = str(-((Wio[0])/y))
    b = str(-(Wio[2])/y)
    # Especificamos en texto plano la ecuación
    f = x + '*x + ' + b
    # Se inicializa el objeto de la gráfica
    g = Gnuplot.Gnuplot()
    g.title('Gráfica de la solución del Perceptron')
    g.xlabel('x')
    g.ylabel('y')
    g('set xrange [0:2]')
    g('set yrange [0:2]')
    g('set pointsize 2')
    g.plot(f, clase0, clase1)   
    raw_input("Presione cualquier tecla...")

# Divido las clases en clase0 y clase1
def dividirPuntosPorClase(patron):
    clase0 = []
    clase1 = []
    for pattern in patron:
        valor_punto = pattern[1]
        punto_recta = [pattern[0][0], pattern[0][1]]
        if (valor_punto == 0):
            clase0.append(punto_recta)
        if (valor_punto == 1):
            clase1.append(punto_recta)
    return clase0, clase1

Hasta aca todo, la seguimos en la próxima!

Jugando con Pygame

2010-02-06T11:54:00.004-03:00

Antes que nada quiero aclarar que de diseño de juegos, no tengo idea, si quieren a alguien que sepa de eso vayan al blog de mi amigo Alejandro Iglesias. Habiendo hecho la salvedad pertinente, les voy a pasar a contar un poquito de lo que vengo viendo (jugando) con pygame que, según Wikipedia, es un conjunto de módulos del lenguaje Python que permiten la creación de videojuegos. A videojuegos no vamos a llegar pero lo que voy a mostrar rapidamente es como, instalar en Ubuntu primero y dibujar una serie de formas despues, haciendo uso de estos módulos.

Pero primero lo primero; abrimos una consola y "sudo apt-get install python-pygame" mediante tenemos instalado el conjunto de módulos listo para usar.

Ahora un par de muestras (muuuuuuuuuuy pero muy pequeñas) de lo que pygames nos permite hacer con pocas, muy pocas, lineas de código:

# importamos los modulos a utilizar
import pygame
from pygame.locals import *
# inicializamos
pygame.init()

# Estas son las dimensiones y la declaracion de la pantalla
screen = pygame.display.set_mode((400, 300))

# Escribe el texto en la barra de la pantalla
pygame.display.set_caption('Figuras diversas!!')

# Pone visible el mouse
pygame.mouse.set_visible(True)

# Dibuja el cuadrado que sera de la medida de la pantalla creada
black_square_that_is_the_size_of_the_screen = pygame.Surface(screen.get_size())

# Le pone el color de fondo negro
black_square_that_is_the_size_of_the_screen.fill((0, 0, 0))

# Dibuja el cuadrado negro a partir de la posicion (0, 0)
screen.blit(black_square_that_is_the_size_of_the_screen, (0, 0))

# Actualiza el contenido de la pantalla
pygame.display.flip()

#Colores utilizados
red_color = (255, 0, 0)
blue_color = (0, 0, 255)
green_color = (0, 255, 0)
yellow_color = (255, 255, 0)
white_color = (255, 255, 255)

flag = True
while flag:
    # rectangulo
    pygame.draw.rect(screen, red_color, (50,  50,   60,   60))
    # poligono
    pygame.draw.polygon(screen, blue_color,  [(50, 140), (50, 170), (80, 210), (110, 170), (110, 140)])
    # circulo
    pygame.draw.circle(screen, green_color, (200, 200), 40)
    # elipse
    pygame.draw.ellipse(screen, yellow_color, (140,  50,   30,   60))
    # elipse parcial (es un pedazo)
    pygame.draw.arc(screen, white_color, (200,  50,   30,   60), 0, -45)
    pygame.display.flip()

    # Rescata la cantidad de eventos, si unos es del tipo QUIT (se presiona la cruz) cierra la ventana
    eventos = pygame.event.get()
    if len(eventos) > 0:
        if eventos[0].type == QUIT: flag = False

# Aqui llegamos al fin :P

Esto, pensé, puede ser una introducción muuuuuuuuy básica a pygame... Ahora bien, si quieren documentación de verdad, remitirse a la web de pygame o a la web de losersjuegos donde, por suerte para los mas vagonetas como yo, está la documentación traducida a nuestro idioma.

Hasta la próxima!

Summarization: Evaluación de Técnicas de Resumen sobre Artículos Científicos

2009-12-04T14:40:00.007-03:00

Resumen

Este trabajo tiene por objetivo evaluar diferentes técnicas de summarization (resumen automático de texto) para la generación de un corpus resumido sobre artículos cientificos. El fin perseguido es que los documentos pierdan la menor carga semántica posible, conservando su sentido original y reduciendo el tamaño de almacenamiento necesario para contener el corpus.

La intención de este experimento es encontrar una solución a la “sobrecarga de información” que dificulta la manipulación de la información disponible y hace indispensable poseer grandes volúmenes de hardware para poder procesarla.

Los métodos evaluados devolvieron resultados prometedores que hacen interesante la extensión de esta investigación, recurriendo a nuevos métodos de resumen y evaluación.

Palabras clave: resumen automático, reducción del corpus, sistemas de recuperación de información.

1. Introducción

Los grandes volúmenes de información disponibles en la actualidad en formato digital, generados por fenómenos como la web y la innovación en cuanto a la forma de expresión de la sociedad, han sido catapultantes directos para que se comience a dar mayor difusión e investigación a los Sistemas de Recuperación de Información que tienen por objetivo recuperar respuestas a las necesidades de información de los usuarios de forma rápida y precisa. Se puede mencionar rápidamente (estudios minuciosos sobre SRI se han desarrollado por ejemplo en [MIR] y [MAN]) de estos Sistemas que parten desde un corpus, que es un conjunto de documentos cuya temática puede ser homogenea o heterogenea, para luego pasar por un proceso de indexación con el fin de organizar los documentos sobre estructuras de datos de forma que sean computables con el objetivo de brindar un servicio de recuperación eficaz.

Los resúmenes, según [TOL] permiten caracterizar el contenido de un texto en una cantidad limitada de palabras u oraciones, de acuerdo a la necesidad y a la aplicación, modificando el procesamiento posterior que se requiere. Desde el punto de vista de la utilidad, los resúmenes permiten reducir el tiempo de procesamiento, los requisitos de almacenamiento y el tráfico de datos en las transferencias electrónicas.

La temática atacada en el presente trabajo se basa en evaluar la posible reducción del corpus de entrada al Sistema de Recuperación de Información con el fín de reducir los indices necesarios para contener la colección, dandole al sistema mayor escalabilidad y brindando a los profesionales la posibilidad de trabajar en la Recuperación de Información sin necesidad de recurrir a grandes unidades de hardware.

El gran desafio de las técnicas aplicadas para la summarization está en poder conservar la carga semántica de cada documento con el objetivo de no perder exhaustividad ni precision en las respuestas brindadas por el sistema, por lo tanto se considerará mas apropiada o mas apta para la tarea de summarization aquella técnica que permita reconocer con mayor nivel de claridad la idea principal del documento procesado.

Las técnicas de resumen utilizadas fueron extraidas de [TOL], se mencionan allí como las clásicas de este tipo de estudios, y son TF/ISF, Palabras Clave (a este método se aplicó una variante) y SIMTIT (Oración con mayor semejanza al Título del Texto).

La hipótesis de esta investigación se basa en suponer que un método de resumen eficaz conservará la idea principal del documento, permitiendo así al Sistema de Recuperación de Información, reconocer su relevancia frente a la necesidad de información del usuario conservando solo un resumen.

El resto del documento se encuentra dividido en las siguientes partes. A continuación, se presenta un trabajo relacionado al área de resumen automático que fue fundamental, como punto de partida, para la realización de esta experiencia junto con otros trabajos del área de Recuperación de Información ineludibles a la hora de abordar estos temas. En el apartado 3 se explican las técnicas de resumen utilizadas. Con posterioridad se describe la experiencia realizada y la forma en que se fueron resolviendo los desafios que aparecieron. Luego, se expresa una conclusión acerca de la experiencia y se proponen posibles trabajos futuros. Finalmente, se incluyó un anexo con la implementación en Perl de las técnicas de summarization utilizadas.

2. Trabajos Relacionados

El desarrollo de esta investigación se inició a partir de una linea de trabajo futuro propuesta por los autores Tolosa, Bordignon y Peri [TOL], que proponen la continuación de su experiencia a partir de la modificación de alguno de los algoritmos propuestos o el cambio de contexto en que se apliquen los algoritmos, ya que aquella fue realizada textos cortos correspondientes a noticias en español.

También se tuvo como referencia a reconocidos autores de esta área como Manning [MAN] y Baeza Yates [MIR] cuyos trabajos sirvieron como marco teórico general para esta investigación.

3. Métodos de Resumen utilizados

Para esta experiencia se utilizaron tres técnicas que pueden ser agrupadas según su fundamentación teórica.

Las técnicas TF/ISF y Palabras Clave, tienen su fundamentación en la frecuencia de aparición de los términos que componen las oraciones mientras que la técnica SIMTIT parte de la suposición de que el título, pese a ser corto como indicador de resumen, tiene un alto contenido semántico acerca del tema central del documento.

A continuación se exponen las formulas de estas técnicas y las observaciones sobre las modificaciones propuestas a éstas en los casos en que se hayan aplicado. En el Anexo I se incluye parte de las implementaciones de los algoritmos.

Como complemento, y a fín de eliminar el ruido en las ponderaciones aportado por las palabras vacías (palabras cuyo poder de discriminación del texto es muy bajo o nulo) fueron eliminadas para los cálculos.

3.1 TF/ISF

Esta técnica es una variante del método de ponderación para términos en Information Retrieval. Primero se ponderan los términos de cada frase y luego se realiza la sumatoria de los pesos de cada término por frase. Por último, según [TOL] en desacuerdo con Larroca, aquellas frases mas representativas del texto serán las que tengan menor peso.

La ponderación de los términos del documento se realiza a partir de:

donde,

P(w) = Peso de la palabra W.

F(W,O) = Frecuencia del término W en la oración O.

|O|d = Cantidad de oraciones O en el documento d.

DF(W) = Cantidad de oraciones en las cuales el término W ocurre.

Luego, por cada oración se hace la sumatoria del peso de sus términos normalizando por la cantidad de palabras que tiene cada oración para no distorsionar los resultados según la longitud de las mismas:

donde,

la sumatoria se aplica a todos los términos i de la oración O.

|W|o = Cantidad de términos W de la oración O.

3.2 Palabras Clave

Este método supone que los términos con mayor frecuencia son las palabras clave del documento. Por consiguiente, se calcula la frecuencia de cada uno de los términos que aparecen en el documento, las cuales ofician de peso de los mismos. Luego se realiza la sumatoria del peso de cada término por oración. Aquellas oraciones con mayor peso serán las que mejor identifiquen al documento.

Se define:

donde,

p(Wi) es la frecuencia en el texto de los terminos de la oración O.

A esta técnica se le aplicó una variante; con el fín de normalizar los pesos en aquellas frases de diferente longitud, se dividen los pesos obtenidos por oración por la cantidad de términos presentes en la misma.

3.3 SIMTIT (Oración con mayor semejanza al Título del Texto)

La técnica SIMTIT, como se dijo, parte de la suposición de que el título, pese a ser corto como indicador de resumen, tiene un alto contenido semántico acerca del tema central del documento. Partiendo del supuesto descripto, se calcula, mediante una métrica de semejanza, la similitud entre las frases del documento y el título del mismo. En esta experiencia se utilizó el coeficiente de DICE [TO2].

4. Trabajo Experimental

4.1. Datos de Prueba

La colección utilizada para la prueba está formada por 106 documentos técnicos que fueron presentados en CACIC (Congreso Argentino de Ciencias de la Computación) en 2004, cuya temática es compartida entre ellos y tiene que ver con la tecnología y las investigaciones dentro de este ambito.

El preprocesamiento de la colección fue común para todas las técnicas de summarization. Se normalizaron los caracteres llevándolos a minúsculas y luego se eliminaron las palabras vacías.

A continuación, se presentan algunas características de la colección, recogidas mediante un script en perl diseñado para tal fin:

Cantidad de documentos procesados: 106.
Cantidad de frases promedio por documento: 129.41.
Cantidad de terminos extraidos: 134788.
Promedio de terminos por documento: 1271.58.
Cantidad de terminos del documento mas corto (cacic2004-63_ok.txt): 551.
Cantidad de terminos del documento mas largo (cacic2004-210_ok.txt): 2322.
Cantidad promedio de la longitud de los terminos: 7.16.
Cantidad de terminos que aparecen una sola vez en la coleccion: 17396.
Cantidad de tokens extraidos: 116831.
Promedio de tokens por documento: 1102.17.
Catindad de tokens del documento mas corto (cacic2004-63_ok.txt): 468.
Cantidad de tokens del documento mas largo (cacic2004-210_ok.txt): 2007.

4.2 Desarrollo del experimento

4.2.1 Creación de las colecciones resumidas

Arbitrariamente, se aplicó sobre el corpus tres longitudes de resumen por cada una de las técnicas. Un primer resumen de 5 oraciones por documento, un segundo de 10 y el último de 20 oraciones. Las características principales de las nueve colecciones resultantes se presentan a continuación:

Método	Terminos extraidos	Terminos por documento	Tokens extraidos	Longitud promedio terminos	Terminos con frecuencia 1
PC-5	12662	119,45	9305	5,65	2895
TF/ISF-5	4804	45,32	3160	5,52	1241
SIMTIT-5	13960	131,69	10618	6,49	3148
PC-10	21402	203,82	16451	6,08	4277
TF/ISF-10	9622	90,77	6731	5,87	1981
SIMTIT-10	24260	228,86	19246	6,79	4577
PC-20	36858	347,71	29651	6,48	6291
TF/ISF-20	18966	178,92	14236	6,32	3192
SIMTIT-20	41249	389,14	33951	6,95	6567

Como se puede apreciar, algunas técnicas tienden a valorar mas las frases mas largas. También es importante aclarar que resulta llamativo el hecho de que la técnica de TF/ISF obtenga como resúmenes colecciones bastante mas pequeñas que las demás técnicas en cada una de las escalas. Esto puede deberse, en parte, al conflicto en la bibliografía acerca de su esquema de valoración y debiera evaluarse una revisión de la técnica como trabajo futuro.

4.2.2 Creación de las necesidades de información

A partir de la inspección de los temas tratados en los documentos se crearon 50 necesidades de información -querys- con el objetivo de poder probar las diferentes colecciones creadas. Las necesidades de información tienen entre 2 y 5 términos e intentan ser atinadas a los temas tratados en el corpus.

4.2.3 Creación de los pseudo-juicios de relevancia

A continuación se procedió a generar los juicios de relevancia con el fín de evaluar la respuesta de cada una de las colecciones resumidas a las necesidades de información creadas en el experimento.

El procedimiento para la creación de los pseudo-juicios de relevancia es el descripto a continuación:

Se indexó la colección original haciendo uso de la herramienta Lemur [LEM] con tres técnicas de ponderación (TF*IDF, BM25 y KL Divergence).
Se procedió a correr los querys sobre los indices resultantes de la aplicación de las tres técnicas de ponderación.
Luego, a partir de un script realizado en perl para tal fin, se sumó para cada documento, el ranking obtenido en cada query. Se penalizaron los documentos que no aparecieron rankeados en alguna técnica de ponderación. Se ordenaron en forma ascendente los resultados obtenidos y se tomaron los 20 primeros resultados de cada query como documentos relevantes.
El sentido del procedimiento explicado antes se basa en suponer que aquellos documentos que resultaran muy relevantes para los tres métodos de ponderación utilizados, serían efectivamente relevantes.

4.2.4 Procesamiento de las necesidades de información en las colecciones resumidas

A continuación se procesaron, también a partir de la herramienta Lemur, las 50 necesidades de información creadas a fin de evaluar las colecciones resumidas. Las colecciones resumidas se indexaron según el metodo de ponderación TF*IDF de la herramienta Lemur.

4.3 Resultados de la experiencia

Los resultados devueltos para cada una de las colecciones resumidas se procesaron mediante un script en perl creado para tal efecto, con el objetivo de ser compatibles con la herramienta trec_eval [TRE] a fin de evaluar los resultados obtenidos.

A continuación se presentan los datos obtenidos, diferenciando la prueba según las tres escalas de longitud de los resúmenes.

Resúmenes de 5 oraciones

	TF/ISF	Palabras Clave	SIMTIT
#Querys	45	43	46
#Respuestas	899	1001	1289
#Relevantes	868	836	846
#Relevantes devueltos	275	314	418
MAP	0,2	0,25	0,33
R-Precision	0,21	0,26	0,35
P at R = 0	0,92	0,93	0,99
P at R = 0,1	0,78	0,85	0,87
P at R = 0,2	0,39	0,55	0,72
P at R = 0,3	0,19	0,35	0,53
P at R = 0,4	0,14	0,17	0,36
P at R = 0,5	0,1	0,14	0,3
P at R = 0,6	0,06	0,08	0,13
P at R = 0,7	0,03	0,06	0,07
P at R = 0,8	0,03	0,04	0,06
P at R = 0,9	0,02	0,03	0,04
P at R = 1	0,01	0,02	0,02
P@5	0,53	0,65	0,69
P@10	0,34	0,43	0,53
P@15	0,26	0,33	0,39
P@20	0,2	0,25	0,33

Gráfica de Recall y Precision de las tres técnicas de resumen

Resúmenes de 10 oraciones

	TF/ISF	Palabras Clave	SIMTIT
#Querys	46	46	49
#Respuestas	1079	1205	1568
#Relevantes	873	881	894
#Relevantes devueltos	359	413	529
MAP	0,29	0,34	0,44
R-Precision	0,3	0,35	0,45
P at R = 0	0,97	0,99	1
P at R = 0,1	0,91	0,92	0,99
P at R = 0,2	0,65	0,77	0,92
P at R = 0,3	0,36	0,57	0,76
P at R = 0,4	0,25	0,36	0,57
P at R = 0,5	0,17	0,21	0,41
P at R = 0,6	0,12	0,15	0,25
P at R = 0,7	0,09	0,1	0,17
P at R = 0,8	0,05	0,05	0,09
P at R = 0,9	0,03	0,05	0,05
P at R = 1	0,02	0,03	0,03
P@5	0,67	0,77	0,83
P@10	0,47	0,56	0,63
P@15	0,37	0,43	0,5
P@20	0,29	0,34	0,41

Gráfica de Recall y Precision de las tres técnicas de resumen

Resúmenes de 20 oraciones

	TF/ISF	Palabras Clave	SIMTIT
#Querys	48	47	50
#Respuestas	1345	1516	1885
#Relevantes	888	886	895
#Relevantes devueltos	474	547	653
MAP	0,41	0,48	0,59
R-Precision	0,4	0,48	0,57
P at R = 0	0,98	1	1
P at R = 0,1	0,97	1	1
P at R = 0,2	0,88	0,9	0,99
P at R = 0,3	0,6	0,78	0,95
P at R = 0,4	0,48	0,66	0,86
P at R = 0,5	0,34	0,55	0,69
P at R = 0,6	0,23	0,34	0,52
P at R = 0,7	0,16	0,2	0,32
P at R = 0,8	0,09	0,11	0,22
P at R = 0,9	0,05	0,06	0,15
P at R = 1	0,03	0,04	0,06
P@5	0,82	0,87	0,9
P@10	0,61	0,71	0,75
P@15	0,47	0,57	0,62
P@20	0,38	0,46	0,51

Gráfica de Recall y Precision de las tres técnicas de resumen

Comparativa entre SIMTIT con resúmenes de 20 oraciones y la colección original

	Colección COMPLETA	SIMTIT
#Querys	50	50
#Respuestas	2755	1885
#Relevantes	895	895
#Relevantes devueltos	895	653
MAP	0,97	0,59
R-Precision	0,92	0,57
P at R = 0	1	1
P at R = 0,1	1	1
P at R = 0,2	1	0,99
P at R = 0,3	1	0,95
P at R = 0,4	1	0,86
P at R = 0,5	0,9952	0,69
P at R = 0,6	0,9888	0,52
P at R = 0,7	0,9796	0,32
P at R = 0,8	0,9594	0,22
P at R = 0,9	0,9336	0,15
P at R = 1	0,8237	0,06
P@5	0,9720	0,9
P@10	0,9280	0,75
P@15	0,8920	0,62
P@20	0,8180	0,51

Gráfica de Recall y Precision de la colección completa contra SIMTIT de 20 oraciones

4.4 Análisis de los resultados obtenidos

A partir de los resultados obtenidos puede verse, claramente, que al igual que en [TOL], la técnica que mejor aproxima la esencia de la colección es la de SIMTIT (Oración con mayor semejanza al Título del Texto) que, haciendo uso de parte de la estructura del texto -el título-, presenta una precisión, en lineas generales, aceptable o buena.

Como era de esperarse, a medida que el tamaño de los resúmenes crece, el nivel de precision y exhaustividad lo hace también, casi proporcionalmente, encontrandose los mejores resultados para los resúmenes mas extensos.

Resulta oportuno aclarar que aún utilizando la colección con resúmenes mas extensos (de 20 oraciones) y, partiendo de la base de que un documento en la colección original rondaba las 129 oraciones, se estaría utilizando una colección que tendría un tamaño del 20/129 = 15,5% de la colección original, con lo cual se potencian los resultados obtenidos en la evaluación de costo-beneficio.

Esta ecuación de costo-beneficio tendría como costo la perdida de exhaustividad y precisión y como beneficios, claros e ineludibles, la compresión de los indices, la reducción en el tiempo de procesamiento, la minimización de los requisitos de almacenamiento y la disminución del tráfico de datos en las transferencias electrónicas.

Como última apreciación, debe mostrarse que, al menos el Sistema de Recuperación de Información utilizado, no tiene dificultades en recuperar documentos precisos en los niveles de exhaustividad iniciales, propiedad que pierde conforme se va avanzando en estos niveles de exhaustividad. Este defecto se va corrigiendo a medida que la longitud de los resúmenes crece.

5. Conclusiones y Trabajos Futuros

Como ya se ha mencionado en el desarrollo de este trabajo, las técnicas de resumen vienen a aportar una posible solución a los problemas de escalabilidad y de sobrecarga de información generados en la actualidad a partir de fenomenos mencionados, como la web y la tendencia a una forma de expresarse digital.

En esta experiencia, se tomaron tres métodos de generación de resúmenes de la literatura tradicional de Information Retrieval y se intentó demostrar que un resumen de cada documento de la colección de entrada, puede ser un buen indicador de la esencia de dicho texto siempre y cuando las técnicas desarrolladas puedan retener lo mas importante de los mismos.

Pudo verse a partir de las pruebas que hay técnicas que demuestran conservar de mejor forma la esencia de los documentos, y sus resultados se muestran prometedores en la evolución de esta herramienta como forma de contrarrestar la problemática planteada al comienzo de esta conclusión.

En particular, la técnica SIMTIT (Oración con mayor semejanza al Título del Texto) demostró que es capaz de conservar el sentido original de los documentos mostrando una precisión aceptable y creciente conforme lo hace el tamaño de los resúmenes.

Esto, sumado a que los resúmenes mas extensos solo representaron el 15% de la colección original, a que no se realizó stemming (técnica que podría mejorar la exhaustividad) y a que no se realizo una poda de los términos menos comunes según Luhn [LUH], hace pensar que los resultados pueden mejorar con la combinación de estas variantes.

Se considera fuera del alcance de esta investigación pero se deja abierta para el estudio, la inclusión en una experiencia similar de técnicas de stemming que permitan mejorar la exhaustividad en los resultados. Otro punto a desarrollar será la busqueda de técnicas de resúmenes no aplicadas en esta experiencia como así también la revisión de la técnica TF/ISF ya que resulta llamativa la diferencia en la extensión de los resúmenes en comparativa con las otras dos técnicas.

Otro punto interesante a inspeccionar será la aplicación de esta metodología de trabajo sobre colecciones mas heterogeneas ya que se utilizó para este articulo una colección, como se describió, homogenea; aunque se vislumbra que los resultados obtenidos con colecciones heterogeneas no será muy dispar del conseguido en este trabajo.

Por último, en esta experiencia se establecieron, arbitrariamente, resúmenes de 5, 10 y 20 oraciones por lo que queda también, como trabajo futuro la busqueda de aquel tamaño de resumen que pueda aportar la relación mas satisfactoria de costo-beneficio entre tamaño de la colección y precisión-exhaustividad.

6. Bibliografía

[TOL] Tolosa, G. H..; Peri, Jorge A. y Bordignon, Fernando R. A, “Experimentos con Métodos de Extracción de la Idea Principal de un Texto sobre una Colección de Noticias Periodísticas en Español ”, 2005.
[TO2] Gabriel H. Tolosa y Fernando R.A. Bordignon, “Introducción a la Recuperación de Información”, 2007.
[MIR] Baeza-Yates, R. y Ribeiro-Neto, B. “Modern Information Retrieval”. ACM Press. Addison Wesley. 1999.
[MAN] Christopher D. Manning, Prabhakar Raghavan y Hinrich Schütze “An Introduction to Information Retrieval ”, 2009.
[LUH] Luhn, H.P., “The automatic creation of literature abstracts”. IBM Journal of Research and Development, 2, 1pags. 59-165. 1958.
[LEM] The Lemur Toolkit for Language Modeling and Information Retrieval, www.lemurproject.org.
[TRE] Text REtrieval Conference (TREC) trec_eval 9.0, http://trec.nist.gov/trec_eval/.

Anexo I: Implementación de las técnicas en Perl

A continuación se presentan los fragmentos mas importantes de una implementación en Perl de las técnicas de summarization utilizadas en la experiencia.

Fragmento del código en Perl de la técnica de TF/ISF

Siendo la estructura de datos:

$TokensxFrase{$frase}{$token} = $frecuencia_de_token_en_la_oracion

$cantidad_oraciones_del_texto = $#sentences;

# Se calculan la cantidad de frases en que aparece cada token y su frecuencia en el documento

my %CantidadTerminos = ();

my %FrecuenciaEnTexto = ();

for $frase (sort keys %TokensxFrase ) {

for $token (sort keys %{ $TokensxFrase{$frase} } ) {

$FrecuenciaEnTexto{$token}++; # Cantidad de oraciones en las que aparece el token

$CantidadTerminos{$frase}++; # Cantidad de terminos por frase

} }

# Se calcula el peso de cada termino en la oracion

my %Peso = ();

for $frase (sort keys %TokensxFrase ) {

for $token (sort keys %{ $TokensxFrase{$frase} } ) {

$Peso{$frase}{$token} += $TokensxFrase{$frase}{$token} * log($cantidad_oraciones_del_texto/$FrecuenciaEnTexto{$token});

} }

# Se calcula el score de cada oracion

my %Score = ();

for $frase (sort keys %Peso ) {

$Score{$frase} = 0;

for $token (sort keys %{ $Peso{$frase} } ) {

$Score{$frase} += $Peso{$frase}{$token};

}

$Score{$frase} = $Score{$frase}/$CantidadTerminos{$frase};

}

Fragmento del código en Perl de la técnica de Palabras Clave

Siendo la estructura de datos:

$TokensxFrase{$frase}{$token} = $frecuencia_de_token_en_la_oracion;

$Frecuencia{$token} = $frecuencia;

# Contamos la cantidad de palabras por frase -PARA NORMALIZAR-

for $frase (sort keys %TokensxFrase ) {

$c = 0;

for $token (sort keys %{ $TokensxFrase{$frase} } ) {

$c++;

}

$Palabras{$frase} = $c;

my %Score = ();

# Se calculan las frases con mayor score y se normaliza por cantidad de palabras de la frase

for $frase (sort keys %TokensxFrase ) {

for $token (sort keys %{ $TokensxFrase{$frase} } ) {

$Score{$frase} = $Score{$frase} + $TokensxFrase{$frase}{$token} * $Frecuencia{$token};

}

$Score{$frase} = $Score{$frase}/$Palabras{$frase};

}

Fragmento del código en Perl de la técnica SIMTIT

Siendo la estructura de datos:

$TokensxFrase{$frase}{$token} = $frecuencia_de_token_en_la_oracion;

# Se calcula la sumatoria de las frecuencias al cuadrado de los terminos

my %SumatoriaCuadrados = ();

for $frase (sort keys %TokensxFrase ) {

for $token (sort keys %{ $TokensxFrase{$frase} } ) {

$SumatoriaCuadrados{$frase} += $TokensxFrase{$frase}{$token} * $TokensxFrase{$frase}{$token}

}

#Se calcula el coeficiente de dice entre el titulo $frase = 0 y las demas $frases

my %Score = ();

for $frase (sort keys %TokensxFrase ) {

$Score{$frase} = 0;

for $token (sort keys %{ $TokensxFrase{$frase} } ) {

$Score{$frase} += $TokensxFrase{$frase}{$token} * $TokensxFrase{0}{$token};

}

$Score{$frase} = (2 * $Score{$frase}) / ($SumatoriaCuadrados{$frase} + $SumatoriaCuadrados{0});

}

Despues de un tiempo de inactividad...

2009-12-04T13:55:00.000-03:00

...me propuse empezar a postear con mas asiduidad. Estuve afuera por la enfermedad de un familiar bien directo pero ya estoy volviendo al ruedo!
Nos vemos en la próxima posteada, para la cual tengo algo preparado de Summarization en Information Retrieval y también algo de una red P2P que interconecta a usuarios con intereses comunes que hicimos con mi amigo David Conde.

Hasta la próxima!

Error inaceptable en Windows Vista Home Premium Edition

2009-09-29T17:27:00.004-03:00

Ultimamente estoy usando 80% Ubuntu, 20% Windows por lo que para mi es importante tener los dos S.O. operativos y actualizados. No soy un talibán ni nada por el estilo y puedo reconocer ventajas y desventajas en ambos. Por estos días actualicé mi Ubuntu de 8.04 a 8.10 y todavía estoy teniendo problemas con el Gestor de Paquetes Synaptic y el Gestor de Actualizaciones por lo que no puedo decir que en mi Ubuntu sean todas buenas pero la verdad es que todavía estoy indignado por la causa del error que me hizo perder su buen tiempo en Windows.
La historia empieza cuando bajé una colección de prueba para indexar en el software Lemur, que estoy usando por estos días para Information Retrieval, y accidentalmente descomprimí los 3000 documentos de esta colección sobre el Escritorio de mi Windows Vista, sin darme cuenta, pensando que el Winrar generaría una carpeta para descomprimirlos. Pero no, resulta que deperdigó por todo mi escritorio sus hermosos html. En el momento noté que la máquina empezó a (la vieja y conocida frase) "andar mas lenta" pero le resté importancia. El tema es que cuando intenté reiniciar, mi Windows era una carreta y no terminaba nunca de cargar el escritorio viendose todo negro y sin barra de inicio.
Sintesis y Solución: Parece que la basta cantidad de documentos sobrecargó mi escritorio (si, parece un chiste, pero no lo es!) y ya no podía cargarse. La solución fue iniciar desde mi Ubuntu, borrar los 3000 documentos de la colección y por las dudas Restaurar el Sistema a una fecha anterior al "accidente". De ahí que no tuve mas problemas pero sinceramente es algo que quería compartir con ustedes, especialmente los linuxeros que se deben estar matando de risa con esto...

Hasta la próxima!

Error Python: 'module' object has no attribute 'AF_INET' en socket.py

2009-09-28T11:14:00.004-03:00

Como conté antes, estoy aprendiendo Python para una materia de la Universidad y , la verdad que en general, creo que me voy enamorando de algunas de las ya conocidas bondades del lenguaje pero tiene sus secretillos, como todas las demás... :)
La historia empieza cuando quise correr el típico ejemplo de sockets en Python al que llamé, obviamente, socket.py.
El ejemplo es un pequeño cliente/servidor orientado a la conexión que hace una implementación del protocolo echo donde el servidor le replica al cliente un mensajito enviado por este:

#Código correspondiente al servidor
#==================================
import socket

host = 'XXX.XXX.X.X'  # IP o Hostname donde escucha
port = 3500   # Puerto de escucha, se recomienda un efímero
bytes = 1024   # Cantidad maxima de bytes a aceptar

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind((host,port)) # Indicamos al socket la direccion IP y Port de escucha
while 1:
    client, address = s.accept()  # Acepta las conexiones   
    data = client.recv(bytes)  # Se obtienen los datos desde el sock cliente 
    print "Conexion desde: %s:%i" %(address[0],address[1])
    if data:
        client.send(data)   # Enviamos el echo al cliente 
    client.close()     # Cerramos el sock cliente



#Código correspondiente al cliente
#=================================
import socket

host = 'XXX.XXX.X.XXX'
port = 3500
bytes = 1024

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((host,port))
s.send('Datos a enviar')
data = s.recv(bytes)
s.close()
print 'Echo de los datos enviados: ', data

Este codigo no es mio ni mucho menos y se puede encontrar en cualquier rincón de la web que trate de sockets pero la anecdota es que cuando fui a hacer el "python socket.py" para correr el servidor me dió el siguiente error:

Traceback (most recent call last):
  File "socket.py", line 7, in 
    import socket
  File "/home/juan/Escritorio/Python/TP3/ejercicio1/socket.py", line 15, in 
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
AttributeError: 'module' object has no attribute 'AF_INET'
Error in sys.excepthook:
Traceback (most recent call last):
  File "/usr/lib/python2.5/site-packages/apport_python_hook.py", line 38, in apport_excepthook
    from apport.packaging_impl import impl as packaging
  File "/usr/lib/python2.5/site-packages/apport/__init__.py", line 1, in 
    from apport.report import Report
  File "/usr/lib/python2.5/site-packages/apport/report.py", line 14, in 
    import subprocess, tempfile, os.path, urllib, re, pwd, grp, os, sys
  File "/usr/lib/python2.5/urllib.py", line 26, in 
    import socket
  File "/home/juan/Escritorio/Python/TP3/ejercicio1/socket.py", line 15, in 
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
AttributeError: 'module' object has no attribute 'AF_INET'

Original exception was:
Traceback (most recent call last):
  File "socket.py", line 7, in 
    import socket
  File "/home/juan/Escritorio/Python/TP3/ejercicio1/socket.py", line 15, in 
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
AttributeError: 'module' object has no attribute 'AF_INET'

El tema es que busqué y busqué y no había forma de darme cuenta cual era el error, hasta q se me ocurrio cambiarle el nombre a socket.py por client_echo.py y... Bingo!
No soy muy apto tecnicamente para hablar de Python pero parece que el import socket importaba el script server pegado mas arriba y no el módulo socket original que tiene todas las definiciones de clase y funciones.
En fín, era para comentarles una de esas cosas que nos pueden tener renegando un buen rato con el objetivo de que ustedes se ahorren su rato haciendo uso del mio. :)

Hasta la próxima!

Hablando en Python

2009-09-22T14:01:00.001-03:00

Por este tiempo estoy cursando la asignatura "Taller Libre II: Programación de Red". Esta asignatura propone la programación en python de protocolos de aplicación TCP/IP. Esto nos topa con dos desafíos:

Implementar los protocolos estudiados teoricamente en el curso de Redes.
y aprender Python... pasemos a hablar del lenguaje.

Realmente, conocía muy poco de Python, una de las cosas que mas me sorprendió es su simplicidad y la cantidad de módulos que extienden el lenguaje y que nos ayudan con diversas tareas. Con el poco conocimiento que tengo, ya me animaría a decir que no debe haber .py de complejidad considerable que no tenga un import. Ahora veamos, a modo de ejemplo, lo simple que puede ser en python crear un pequeño cliente POP3 que liste, borre y devuelva mails de una cuenta de correo:

#-*- coding: utf8 -*-
import poplib

#Servidor POP3
pop = poplib.POP3('pop3.servidor.com')

#Datos de teclado
user = raw_input("Usuario: ")
password = raw_input("Pasword: ")

#Autenticacion
pop.user(user)
pop.pass_(password)

#Menu ultra primitivo
print "1- Listar Mensajes"
print "2- Recuperar Mensaje"
print "3- Borrar Mensaje"
opcion = int(raw_input("Opcion -Salir con Otra Tecla-: "))

if opcion == 1:
 mensajes = pop.list()[1]
 print mensajes
elif opcion == 2:
 nro_msj = raw_input("Numero de mensaje a recuperar: ")
 print "Mensaje N°" + nro_msj
 print pop.retr(nro_msj);
elif opcion == 3:
 nro_msj = raw_input("Numero de mensaje a borrar: ")
 print pop.dele(nro_msj);
 print "Se ha borrado el mensaje N°" + nro_msj

pop.quit();

Me sorprende sobremanera el nivel de abstracción al que se ha llegado. Esto lo dice alguien que balbucea inglés, pero se observa a simple vista que Python es tan claro que se acerca muchisimo a ser un pseudo-código de los que aprendimos en las asignaturas introductorias a la programación y esto realmente ayuda sobre todo a leer code ajeno.

Por ahora, hasta acá llegamos con Python pero prometo mas posts a medida que vaya investigando.

Hasta la próxima!

Resaltar Código en Blogger

2009-09-22T11:27:00.002-03:00

La primer entrada referida al tema que nos convoca que pensé en publicar era un ejemplo de sockets en Python, que es el lenguaje que (junto con Perl) estoy usando por estos días. Pero me encontré con un problema, en realidad con una necesidad, la de resaltar el código para que quede mas "lindo" y legible. Empecé a buscar "resaltar códido en blogger", "python blogger", etc, etc y llegué a Syntax Highlighter.
Es un "resaltador de código" desarrollado integramente en JavaScript muy versatil y completo.

Tenemos varias formas de utilizarlo en nuestra web/blog pero la mas simple que encontré es la que publicó en su blog Alejandro Sanchez de Venezuela.

Ahi va un ejemplo de un código PHP que use para un proyecto (parser de noticias) resaltado con Syntax Highlighter:

function parser_perfil() {
  include_once "/htdocs/ej/librerias/simplepie.inc";
  $urlfeed = "http://www.perfil.com/";
  $vfeed = new SimplePie();
  $vfeed->set_feed_url($urlfeed);
  $vfeed->init();
  $vfeed->handle_content_type();
  $vmax = $vfeed->get_item_quantity();
  $noticias = "";
  for ($x = 0; $x < 3; $x++) { 
   $vitem = $vfeed->get_item($x);
   #$noticias .= $vfeed->get_title();
   }
  return $noticias;
  }

Mi primer post!

2009-09-21T22:34:00.001-03:00

Nada mas trillado que el saludo del primer post, el voy a escribir de esto, me interesa lo otro, soy soltero/viudo/casado y todo lo demás...
Con tanta gente inteligente que hace esto, no veo el motivo de que sea yo quien rompa con esta regla.
Empezando... Estudio Licenciatura en Sistemas de Información en la Universidad Nacional de Luján y actualmente me quedan 4 materias + Trabajo Final para egresar (esperemos que sea pronto).
Cuando me decidi a crear el blog creo que fui motivado a aportar eso que googleando, yahooando, bingeando no pude encontrar y luego resolví solo (son los menos) o no (son los mas).
Por estas horas lo que mas me atrapa y roba horas de sueño es la programación así que...
Allá vamos...