Magíster en Ciencias, Mención Computación / La estructura de la Web se puede modelar como un grafo, donde las páginas son los nodos y los hipervínculos las aristas. Estos grafos Web son ampliamente utilizados para diversas tareas de análisis de la Web, tales como el cálculo de Page-Rank o la detección de spam en la Web, entre otras. Una de las limitantes que se presentan al trabajar con estos grafos es su tamaño, por ejemplo, el 2005 se calculó que la Web pública y estática tenía 11.5 mil millones de nodos, y unas 15 aristas por nodo, lo que requiere más de 600 GB para su representación plana. De aquí surge la motivación de este trabajo, que consiste en la creación de estructuras de datos comprimidas para representar grafos de la Web. Una estructura comprimida busca almacenar la mayor cantidad de datos en el menor espacio posible, ya sea en memoria principal o en disco, soportando las consultas de interés sin la necesidad de descomprimir la estructura en su totalidad. La principal ventaja de estas estructuras es que se puede evitar mantener la información en disco o se disminuye la cantidad de transferencias necesarias. Esto es de vital importancia dado que el disco puede llegar a ser un millón de veces más lento que la memoria principal. Entre los resultados más importantes de este trabajo se presenta una estructura comprimida para grafos de la Web que mejora el estado del arte, ofreciendo el mejor compromiso espacio-tiempo conocido para recuperar listas de adyacencia. Además se muestra cómo extender esta estructura para soportar consultas más complejas, como vecinos reversos, manteniendo los requerimientos de espacio. Como productos agregados se incluyen resultados experimentales y propuestas para el problema de Rank y Select sobre secuencias generales, incluyendo estructuras no implementadas antes. Los resultados derivan en mejoras inmediatas para índices comprimidos para texto, en los cuales se reduce el espacio utilizado por los mejores índices existentes, a veces incluso sin penalización en el tiempo de búsqueda. Además se presenta un algoritmo aproximado para comprimir utilizando el método Re-Pair cuando la memoria principal es limitada. También se obtienen resultados en estructuras comprimidas para relaciones binarias, presentándose una nueva propuesta que, además de utilizar espacio proporcional a la entropía de la relación binaria, permite dinamizar la estructura, vale decir, aceptar inserciones y borrados de pares en la relación.

No autorizado por el autor para ser publicada a texto completo / La cantidad de datos disponibles crece de forma dramática cada día. Esto trae consigo la necesidad de poder manejar éstos datos de forma adecuada, de manera de poder acceder a estos de forma eficiente y al mismo tiempo ahorrar espacio de almacenamiento. En particular, para manejar grandes cantidades de texto una herramienta clave son los índices de texto, y en el contexto de este trabajo los índices comprimidos, los cuales no sólo responden consultas de forma rápida sino que también almacenan sus datos y el texto en forma eficiente. El objetivo general del presente trabajo fue desarrollar un índice comprimido basado en listas de ocurrencias de los q-gramas del texto y comprimir este último. Se desea comparar la eficacia de este índice con los auto-índices ya desarrollados en el sitio Pizza&Chili (http://pizzachili.dcc.uchile.cl). Un índice invertido de q-gramas permite encontrar patrones en un texto. Para tal efecto las consultas se dividen en dos etapas. En la primera etapa se seleccionan las regiones del texto (llamadas bloques) donde ocurren todos los q-gramas del patrón y por lo tanto éste podría encontrarse. En la segunda etapa se verifica si efectivamente el patrón se encuentra en los bloques que fueron seleccionados. Además es necesario almacenar el texto de forma independiente. En la implementación realizada se mantiene el texto dividido en bloques comprimidos, los cuales se almacenan en memoria secundaria. Esto permite utilizar menos espacio y acceder a los bloques individualmente. Se implementaron diversos algoritmos para comprimir el índice y realizar consultas. Además se diseñaron y ejecutaron experimentos para medir el rendimiento de las distintas variantes obtenidas al combinar los diferentes algoritmos. En base a los resultados obtenidos se seleccionaron los algoritmos que presentaron mejor rendimiento tanto en velocidad como en niveles de compresión alcanzados. De la misma forma se implementaron y midieron experimentalmente alternativas para comprimir y buscar en el texto. Finalmente se comparó el rendimiento de las variantes seleccionadas del índice frente a los índices competitivos presentes en el sitio Pizza&Chili. Los resultados indican que el índice tiene un rendimiento competitivo para búsquedas de patrones pequeños.

No description available.

Magíster en Ciencias, Mención Computación / Las estructuras de datos compactas ofrecen funcionalidad y acceso a los datos usando poco espacio. En una estructura de datos plana se conservan los datos en su forma original y se busca minimizar el espacio extra usado para proveer la funcionalidad, mientras que en una estructura comprimida además se recodifican los datos para comprimirlos. En esta tesis se estudian estructuras de datos compactas para secuencias de bits (bitmaps) que proveen las operaciones rank y select: rankb(B,i) cuenta el número de bits b ∈ {0,1} en B[1..i] y selectb(B,i) retorna la posición de la i-ésima ocurrencia de b en B. En teoría ambas consultas se pueden responder en tiempo constante, pero la implementación práctica de estas soluciones no siempre es directa o con buenos resultados empíricos. Las estructuras de datos con un enfoque más práctico, usualmente no óptimas en teoría, pueden tener mejor desempeño que implementaciones directas de soluciones teóricamente óptimas. Esto es particularmente notorio para la operación select. Además, las implementaciones más eficientes para rank son deficientes para select, y viceversa. En esta tesis se definen nuevas estructuras de datos prácticas para mejorar el desempeño de las operaciones de rank y select, basadas en dos ideas principales. La primera consiste en, a diferencia de las técnicas actuales, que usan estructuras separadas para rank y select, reutilizar cada estructura también para acelerar la otra operación. La segunda idea es simular en tiempo de consulta una tabla de resultados precomputados en vez de almacenarla, lo que permite utilizar tablas universales mucho mayores que las que sería posible almacenar. Los resultados experimentales muestran que la primera idea, aplicada a estructuras planas, utiliza sólo 3% de espacio sobre el bitmap y ofrece tiempos similares a estructuras que usan mucho más espacio, para ambas operaciones. En estructuras de datos comprimidas se pueden combinar ambas ideas, obteniendo un espacio extra de menos de 7 % sobre el bitmap comprimido y manteniendo, para ambas operaciones, tiempos similares o mejores que las estructuras actuales (que usan 27 % de espacio extra).

Ingeniero Civil Eléctrico / El objetivo del presente trabajo de memoria fue desarrollar un sistema capaz de aprender de registros actigráficos nocturnos de adolescentes sanos y, en base a la información obtenida y a registros polisomnográficos simultáneos, generar un algoritmo que permita clasificar automáticamente los diferentes estados y etapas del sueño en base al registro actigráfico. La actigrafía es una técnica de extracción de información fisiológica que consiste en la ubicación de un dispositivo, denominado actígrafo, en la muñeca de la mano no dominante del paciente. El actígrafo graba la actividad de acelerómetros internos, registrando la actividad motora de la extremidad. Esta técnica ha despertado un creciente interés en la comunidad científica debido a su simplicidad, bajo costo y su carácter no invasivo, por lo que se han desarrollado numerosos estudios para el análisis de dicha señal. El archivo de registros del Laboratorio de Sueño y Neurobiología Funcional del INTA incluye numerosos registros de actigrafía, y polisomnogramas de los mismos pacientes. Se revisaron los registros, descartando aquellos que presentaban ruido o periodos sin mediciones. Luego se buscó sincronizar los registros actigráficos aptos con su respectivo polisomnograma. Se construyó una base de datos compuesta de 114 registros actigráficos muestreados a un dato por minuto, cada uno con su respectivo hipnograma, obtenido a partir del polisomnograma y validado por expertos en medicina del sueño para ser utilizados como ground thruth. Con esta base de datos se construyó un sistema compuesto por dos clasificadores basados en Redes Neuronales Artificiales, el primero es un clasificador que permite distinguir entre sueño y vigilia, mientras que el segundo permite clasificar entre los estados y etapas del sueño. El clasificador de sueño y vigilia utiliza 11 características extraídas de los registros actigráficos, las que fueron elegidas a través de un proceso de selección de características. Entre éstas se cuentan indicadores estadísticos, que miden tanto tendencia central como dispersión en una ventana de tiempo móvil, así como características de contexto temporal, es decir, en qué tiempo se localiza la ventana en relación con el sueño completo, y el contexto de actividad, es decir, información sobre la actividad previa y posterior a la ventana. Este clasificador tiene una precisión de 93,2%, con una detección de sueño de 96,2% y una detección de vigilia de 79,6%. Estos resultados constituyen una mejora respecto de los publicados a la fecha por otros grupos de investigación. El segundo clasificador utiliza las mismas características que el primero excepto dos, que fueron desechadas mediante un test estadístico por ser mutuamente redundantes con otras que entregan más información, lo que no es el caso para la clasificación sueño-vigilia. En esta clasificación se busca distinguir entre los minutos pertenecientes a cuatro etapas: Sueño Quieto 1 (SQ 1), SQ 2, SQ 3&4 y Sueño Paradójico (SP). El clasificador de estados y etapas del sueño tiene una precisión global del 61,0%, detectando el 12,2% de los minutos pertenecientes a la etapa SQ 1, 80,7% de los minutos pertenecientes a la etapa SQ 2, 68,8% de los minutos pertenecientes a SQ3&4 y 6,7% de los etiquetados como etapa SP. El bajo rendimiento del sistema de clasificación se debe a que los datos actigráficos no parecen ser adecuados para discriminar estados y etapas de sueño. No existen estudios con los cuales comparar este resultado. Combinando los ambos clasificadores se alcanzó una precisión de 62,4%.

Ingeniero Civil Eléctrico / El propósito de la presente memoria es analizar si las diferencias anteriormente reportadas en el sistema nervioso central entre pacientes con diagnóstico de esquizofrenia y sujetos de control pueden ser capturadas y cuantificadas a partir de la reactividad pupilar, y estudiar si es posible utilizar esta señal como un marcador fisiológico que pudiese delatar la patología. En primer lugar, se estudió, desarrolló y realizó un experimento por parte del grupo de neurocientíficos que fuese capaz de capturar la señal pupilar de los individuos, utilizando para esto conocimientos acerca del estado del arte en registros oculográficos y en estudios de la reactividad pupilar. Esta señal se extrae y se procesa gracias al desarrollo de un completo grupo de funciones computacionales, las cuales permitieron abordar el problema desde un punto de vista general con relación a los demás experimento enmarcados en el laboratorio de investigación. El problema de la clasificación se abordó en dos etapas. Primeramente se analizó las señales promedio resultantes entre los distintos grupos de interés y a partir de conocimientos de expertos se eligieron el conjunto de valores que caracterizarían la curva. A continuación se aplicó un análisis estadístico para validar los parámetros elegidos. La clasificación se generó a partir del entrenamiento supervisado de redes neuronales artificiales las cuales tuvieron un desempeño aceptable debido a que estas estaban orientadas a apoyar la decisión clínica y no se una única respuesta. Queda registrado como un indicio la diferenciación de la reactividad pupilar entre pacientes y sujetos de control, pero se necesita una mayor cantidad y diversidad de datos para tener resultado plenamente satisfactorios.

La Programación Orientada a Aspectos (AOP) apunta a mejorar la modularidad y reusabilidad en sistemas de software al ofrecer un mecanismo de abstracción para manejar crosscutting concerns. Sin embargo, en la mayoría de los lenguajes orientados a aspectos; los aspectos tienen poder casi sin restricciones, lo que eventualmente entra en conflicto con las metas anteriores. En este trabajo presentamos EffectiveAspects: un nuevo enfoque para incorporar el modelo AOP de pointcut/advice en un lenguaje funcional estáticamente tipeado como Haskell. Como primera contribución, definimos una incorporación completa del modelo de pointcut/advice al lenguaje, usando mónadas. La coherencia de tipos se garantiza explotando el sistema de tipos subyacente, en particular phantom types y una nueva type class que implemente un algoritmo de anti-unificación. Los aspectos son de primera clase, pueden ser desplegados dinámicamente, y el lenguaje de pointcuts es extensible; por lo tanto combina la flexibilidad de lenguajes de aspectos dinámicamente tipeados con las garantías de un sistema de tipos estático. Las mónadas nos permiten razonar directamente sobre los efectos tanto en los aspectos como en los programas base mediante técnicas monádicas tradicionales. Con esto, extendemos la noción de Open Modules propuesta por Aldrich con efectos y con pointcuts protegidos, que son interfaces que restringen la aplicación externa de advice. Estas restricciones son enforzadas estáticamente usando el sistema de tipos. También, adaptamos las técnicas de EffectiveAdvice para razonar y enforzar propiedades del flujo de control; así como también adaptamos su enfoque basado en parametricidad para controlar la interferencia de efectos. Luego de mostrar que este último enfoque no es suficiente en presencia de múltiples aspectos, proponemos un nuevo enfoque basado en monad views, una nueva técnica para manejar mónadas, desarrollada por Schrijvers y Olivera. Nuestra segunda contribución se basa en un poderoso modelo para razonar sobre la composición de componentes basados en mixins que incorporan efectos computacionales. Este modelo se basa en razonamiento ecuacional, parametricidad y leyes algebráicas de las mónadas. Nuestra contribución es mostrar cómo razonar sobre interferencia en la presencia de cuantificación sin restricción, a través de pointcuts. Mostramos que el razonamiento global puede ser composicional, lo que es clave para la escalabilidad de nuestro enfoque en el contexto de grandes sistemas que evolucionan. Demostramos un teorema general de equivalencia que se basa en algunas condiciones que pueden ser establecidas, reutilizadas y adaptadas por separado a medida que el sistema evoluciona. El teorema está definido en términos de un modelo abstracto de AOP monádico. Este trabajo desarrolla técnicas de razonamiento de efectos, basadas en tipos, para el modelo pointcut/advice, en un modelo que es expresivo y extensible; y que permite el desarrollo de aplicaciones orientadas a aspecto robustas y la experimentación con nuevas semánticas de AOP.

Seminario para optar al grado de Ingeniero Comercial, Mención Administración / El estudio evalúa la capacidad de un modelo GARCH, optimizado por algoritmo genético, para predecir la dirección del cambio del precio de un índice financiero, particularmente el IPSA. La particularidad de esta tesis es que incorpora en el modelo eventos o episodios de volatilidad pasados y así verificar la capacidad de estos modelos para modelar el comportamiento del IPSA y mejorar la capacidad de acertar a los cambios de variación de signo del índice. A modo de comparación se evaluó este modelo con modelos GARCH simples que no incorporan estos episodios de volatilidad. El índice utilizado fue el IPSA y los datos se tomaron desde una serie histórica de datos semanales, periodo que corresponde al 01 de Enero de 1995 y 28 de Diciembre del 2007. Los resultados arrojados mostraron que en general los modelos GARCH (p, q) no obtienen un buen PPS arrojando una media del 53,93% dentro de un intervalo al 95% de confianza en 53,13% y 54,73%. Sin embargo, al incluir los episodios de volatilidad como clusters y optimizar la función de máxima verosimilitud minimizando el error cuadrático medio ECM, se logran mejores resultados y muestra que, si bien la optimización de una estructura GARCH (p, q) no garantiza un buen PPS, en la medida que el ajuste aumenta, disminuyendo el ECM, se obtiene un mejor PPS. Sin duda que los mejores resultados tanto “Un modelo no lineal para la predicción de la variación del índice IPSA considerando volatilidades en clustering” en ECM como en PPS fueron canalizados por un mejor ajuste de la estimación que además permitió acertar mas veces al signo de la variación. Es posible que al incorporar al modelo la capacidad de los “traders” de reconocer episodios que alguna vez se dieron en el pasado para ajustar sus predicciones haya incorporado mayor realismo y por ende un mejor ajuste.

Ingeniero Civil Eléctrico / La fatiga mental se define como un cambio en los estados fisiológicos y psicológicos que experimenta una persona a medida que realiza una actividad cognitiva de alta demanda por un período de tiempo. Este trabajo de título diseña y aplica una metodología para la confección de un sistema detector de fatiga mental mediante el análisis de la variabilidad del ritmo cardiaco, con el fin de generar una herramienta que ayude a minimizar la tasa de accidentes en operaciones industriales. Dicha metodología contempla la generación de una base de datos con muestras de variabilidades del ritmo cardíaco (HRV), las cuales son extraídas del registro de electrocardiogramas (ECG) a sujetos con diversos niveles de cansancio mental. Para cada uno de los participantes de este estudio, se realiza una toma de muestra tanto al inicio como al final de su jornada laboral, a lo largo de una semana de trabajo, con la finalidad de obtener posibles tendencias en las características analizadas en el HRV, con respecto al transcurso de una jornada, o de la semana. Para lograr un análisis fidedigno entre el grado de cansancio real que tiene cada voluntario, y los cambios fisiológicos vinculados a estos niveles, se registran parámetros cognitivos y contextuales tales como el puntaje obtenido en un test de habilidad mental, las horas dormidas la noche anterior, y el nivel de fatiga mental auto reportado en una escala entre 0 y 10. A partir de estos parámetros, se implementa un sistema de etiquetado de muestras, para caracterizar tanto de forma continua como de forma binaria, el nivel de fatiga mental estimado en cada individuo, dado por las características de las HRV analizadas. Completado este proceso, se analiza en conjunto la relación entre las etiquetas generadas y las características medidas, para posteriormente desarrollar un algoritmo basado en los paradigmas de la inteligencia computacional clasificador del nivel de fatiga mental. Como resultado de esta metodología, se obtienen dos redes neuronales: la primera, entrenada para caracterizar el nivel de fatiga mental en una escala lineal porcentual entre 0 y 100%. La segunda, entrenada para clasificar de forma binaria entre los conjuntos No Fatiga y Fatiga . Para el primer algoritmo se obtuvo una correlación promedio porcentual de 18% entre las características de las muestras y las etiquetas generadas. Para el segundo algoritmo implementado, se obtuvo un promedio para la exactitud, precisión y sensibilidad de 58%, 61% y 83% respectivamente. La principal limitación del presente estudio fue la elección de los mecanismos utilizados para generar el sistema de etiquetado. En específico, la encuesta de auto reporte no contenía preguntas completamente claras para el voluntario, el juego cognitivo evidenció una tasa de aprendizaje que impedía visualizar cambios en los niveles de concentración, y la medición del electroencefalograma (EEG) presentó problemas de conectividad Bluetooth para recibir la data. Adicionalmente, la cantidad de muestras obtenidas se considera insuficiente para entrenar de forma eficaz una red neuronal. Esto sugiere que, para una próxima realización de este estudio, es necesario perfeccionar las herramientas utilizadas en esta metodología, con el fin de poder caracterizar y clasificar de forma más óptima la fatiga mental mediante el análisis de la variabilidad del ritmo cardiaco.

No description available.