Ingeniero Civil Industrial / El crecimiento acelerado de internet ha creado un aumento sostenido de los sitios web para todo tipo de empresas, organizaciones y particulares, provocando un nivel de oferta inmensamente alto. Estos sitios comienzan cada vez más a ser un importante canal tanto de comunicación directa con el cliente como de ventas, por lo que se hace necesario tratar de generar estrategias que permitan atraer a más usuarios al sitio y además hacer que los actuales usuarios continúen utilizándolo. Esto lleva a preguntarse qué tipo de información resulta de utilidad para el usuario final y como poder identificar esa información. Anteriormente se ha tratado de abordar este problema mediante técnica de web mining a las áreas de contenido, estructuras y usabilidad de un sitio web, de modo de poder encontrar patrones que permitan generar información y conocimiento sobre estos datos. Estos a su vez permitirían tomar mejores decisiones respecto de la estructura y contenido de los sitios web. Sin embargo este tipo de técnicas incluía la conjunción de datos objetivos (web logs) con datos subjetivos (encuestas y focus group principalmente), los cuales poseen una alta variabilidad tanto personal como interpersonal. Esto provoca que el análisis posterior de los datos pueda contener errores, lo que redunda en peores decisiones. Para resolver en cierta manera eso, este proyecto de memoria desarrolló algoritmos de web mining que incluyen análisis de exploración visual y neurodatos. Al ser ambas fuentes de datos objetivas, se elimina en cierta parte la variabilidad de los resultados posteriores, con la consecuente mejora en las decisiones a tomar. El resultado principal de este proyecto son algoritmos de web mining y modelos de comportamiento del usuario que incluyen información de análisis de exploración visual y datos obtenidos a través de ténicas de neurociencia. Se incluyen también una lsita de website keyobjects encontrados en la página de prueba para este proyecto. Se incluyen además una revisión general acerca de los principales temas sobre los que el proyecto se basa: la web e internet, el proceso KDD, Web Mining, sistemas de eye tracking y website keyobjects. Por otra parte se especificaron los alcances del proyecto de memoria, tanto técnicos como de investigación. Se concluye que el resultado del trabajo fue exitoso, incluso siendo el resultado de los algoritmos similares a la metodología previa. Sin embargo se abre un nuevo camino en cuanto al análisis de sitio dadas las relaciones encontradas entre el comportamiento pupilar y el análisis del sitio. Son incluidas ciertas consideraciones y recomendaciones para continuar y mejorar este trabajo.

Ingeniero Civil en Computación / Para investigación en el área de robótica autónoma, el Laboratorio RyCh (Robótica y Computación en Chile) del Departamento de Ciencias de la Computación de la Universidad de Chile dispone del robot PR2, que provee de una plataforma completa para implementación y testeo de algoritmos orientados a solucionar problemas de este ámbito. Una de las materias altamente estudiadas globalmente es el de la capacidad de manipulación de los robots en ambientes cotidianos, con mínima o nula intervención humana sobre las acciones del robot en el proceso. El presente trabajo de memoria aborda el problema de placing (posicionamiento) autónomo de objetos, para entregar así al robot PR2 una funcionalidad hasta ahora ausente y de alta utilidad. Para lograr este cometido, se llevó a cabo en una primera etapa un proceso de investigación sobre el tema y las herramientas a utilizar, para luego pasar a las etapas de diseño, implementación y testeo de una solución computacional que resuelva este problema. Específicamente, en las primeras etapas del trabajo, se investigó acerca de la constitución lógica y física del robot, sobre sus alcances y limitaciones y estándares para el trabajo con esta plataforma. Paralelamente, se trabajó sobre el robot a modo de corroboración de los conceptos aprendidos y se destinó una gran parte del tiempo a realizar indagaciones acerca de trabajos similares realizados sobre este y otros sistemas robóticos autónomos. A continuación se analizó a fondo el problema a resolver, pudiendo así identificar sus posibles aristas y acotar el trabajo realizable con los recursos disponibles, llegando a la definición exacta de lo que se busca desarrollar: Un algoritmo de posicionamiento de objetos desconocidos en superficies planas para el robot PR2. Se prosiguió con el diseño, implementación y testeo de los cinco módulos principales de la solución: Modelamiento del objeto, Cálculo de Pose Estable, Búsqueda de Superficie, Desplazamiento hacia Superficie y Posicionamiento cuyas subcomponentes funcionales formaron la estructura total del software, dando origen a mecanismos de control motriz del robot y a algoritmos específicos para escaneo tridimensional de objetos en una tenaza del robot, detección de superficie de apoyo estable óptima para objetos de diversas geometrías, búsqueda autónoma de una superficie adecuadas para posicionamiento basada en segmentación y traducción de pose estable del objeto a posiciones de la tenaza que lo sostiene, entre otros. Se creó también un módulo preliminar: Preparación del Robot, para llevar al PR2 al estado inicial de posicionamiento de objeto. El desarrollo de estas componentes se realizó de forma independiente, testeando y ajustando parámetros de cada algoritmo. La unificación de todas estas partes dio origen finalmente al programa completo de placing , que resultó en el posicionamiento exitoso de objetos de diversa complejidad geométrica. Los casos fallidos se deben casi exclusivamente a la mala elección del espacio en la superficie utilizada. Se ofrece al final del documento detalles y análisis sobre su aplicación en diversos casos de estudio, mostrando sus fortalezas en la estimación de estabilidad, y debilidades en elección de superficies de posicionamiento. Mejoras al programa son propuestas luego en la sección Trabajo Futuro. El trabajo permitió entender mejor el modo de desarrollo actual para la robótica y en este proceso sentó las bases para la entrega de un sistema funcional.

No description available.

Magíster en Ciencias, Mención Computación / Ingeniero Civil en Computación / En el campo de la cosmología, los vacíos son regiones del espacio cuya densidad es nota- blemente menor que la densidad de fondo, abarcando distancias en el rango de 20 50 Mpc/h (1 Mpc/h ∼ 2,10 × 1019 km). Los primeros vacíos fueron descubiertos en los primeros catá- logos sistemáticos de galaxias lejanas a fines de la década de 1970. Sus propiedades han sido reconocidas como críticas para la comprensión de la estructura a gran escala del universo. Múltiples esfuerzos han sido destinados al estudio de los vacíos cósmicos para una mejor com- prensión de las etapas tempranas y posterior evolución del universo a gran escala, mediante el refinamiento y validación de los modelos cósmicos actuales. La tarea de detectar vacíos, sin embargo, no es trivial y es subjetiva pues la definición de vacío es algo ambigua. Hasta el día de hoy diversos autores continúan investigando este campo, por ejemplo mediante el diseño de mejores algoritmos para detectarlos dentro de catálogos o surveys de galaxias. Considerando lo anterior, hemos desarrollado un algoritmo de detección de vacíos basado en teselaciones de Delaunay: el algoritmo DELFIN (DELaunay Edge Void FINder) que se caracteriza por ser robusto, eficiente y extensible (tanto en 2-d y 3-d), aplicable en grandes catálogos de galaxias. Hemos alcanzado estas características mediante modificaciones y ex- tensiones sobre el algoritmo de Hervías et al. publicado en 2014. Nuestro algoritmo comparte algunas similitudes elementales con otros trabajos, pero las teselaciones de Delaunay proveen mayor maleabilidad y mejor rendimiento. Además, hemos validado nuestro algoritmo tanto con datos artificiales como reales, evaluándonos frente a un algoritmo buscador de vacíos ya existente (Foster y Nelson, 2008), con resultados alentadores. Tanto la implementación 2-d como la implementación 3-d (bajo ciertos supuestos) corren en tiempo O(n log n), donde n es el número de galaxias. Finalmente, proponemos algunas áreas para futura investigación, a partir de las cuales este algoritmo se vería beneficiado, así como también algunas sugerencias sobre cómo abordar y resolver algunos problemas asociados.

Ingeniero Civil Matemático / En este trabajo se presenta una metodología para de detectar estrellas variables en estampillas de 21 x 21 píxels provenientes de imágenes astronómicas a partir de un pipeline de procesamiento de imágenes para el telescopio Dark Energy Camera (DECam). Para aquello se realizará un aprendizaje con una muestra de imágenes que están etiquetadas como estrellas y no estrellas con el objetivo de detectar nuevas estrellas variables en imágenes desconocidas. Los objetos astronómicos que se observan en las imágenes, pueden ser agrupados en las categorías de: estrellas variables, estrellas fijas, rayos cósmicos, fuentes puntuales falsas, malas restas, supernovas y objetos desconocidos. Para la labor de detectar estrellas se ocuparon 2 algoritmos basados en NMF (Nonnegative matrix factorization) y un tercer algoritmo basado en Análisis de Componentes Principales (PCA). El enfoque del primer algoritmo NMF es la rapidez, mientras que el segundo se enfoca en la dispersión de información. Para el uso de los algoritmos anteriores se generó una metodología con la que trabajarán, los cuales ocupan técnicas de optimización no lineal y descomposición de matrices; finalmente se demuestra cual es el mejor de ellos para detectar estrellas gracias a una herramienta llamada Curva ROC. Una vez escogido el mejor método se realiza un estudio de sensibilidad de parámetros para mejorar la detección de estrellas y obtener una representación más genérica a través de la descomposición de matrices. El resultado final es que utilizando uno de los algoritmos basados en NMF, se obtienen los mejores resultados de clasificación, esto se concluye del análisis de la Curva ROC.

Doctor en Ciencias, Mención Computación / En las últimas décadas han crecido la cantidad de trabajos que buscan encontrar metodos eficientes que describan el comportamiento macroscópico de los sistemas de spin, a partir de una definición microscópica. Los resultados que se obtienen de estos sistemas no solo sirven a la comunidad fı́sica, sino también a otras áreas como dinámica molecular, redes sociales o problemas de optimización, entre otros. El hecho de que los sistemas de spin puedan explicar fenómenos de otras áreas ha generado un interés global en el tema. El problema es, sin embargo, que el costo computacional de los métodos involucrados llega a ser muy alto para fines prácticos. Por esto, es de gran interés estudiar como la computación paralela, combinada con nuevas estrategias algorı́tmicas, puede generar una mejora en velocidad y eficiencia sobre los metodos actuales. En esta tesis se presentan dos contribuciones; (1) un algoritmo exacto multi-core distribuido de tipo transfer matrix y (2) un método Monte Carlo multi-GPU para la sim- ulación del modelo 3D Random Field Ising Model (RFIM). La primera contribución toma ventaja de las relaciones jerárquicas encontradas en el espacio de configuraciones del problema para agruparlas en árboles de familias que se solucionan en paralelo. La segunda contribución extiende el método Exchange Monte Carlo como un algoritmo paralelo multi-GPU que in- cluye una fase de adaptación de temperaturas para mejorar la calidad de la simulación en las zonas de temperatura mas complejas de manera dinámica. Los resultados muestran que el nuevo algoritmo de transfer matrix reduce el espacio de configuraciones desde O(4^m ) a O(3^m ) y logra un fixed-size speedup casi lineal con aproxi- madamente 90% de eficiencia al solucionar los problemas de mayor tamaño. Para el método multi-GPU Monte Carlo, se proponen dos niveles de paralelismo; local, que escala con GPUs mas rápidas y global, que escala con múltiples GPUs. El método logra una aceleración de entre uno y dos ordenes de magnitud respecto a una implementación de referencia en CPU, y su paralelismo escala con aproximadamente 99% de eficiencia. La estrategia adaptativa de distribución de temperaturas incrementa la taza de intercambio en las zonas que estaban mas comprometidas sin aumentar la taza en el resto de las zonas, generando una simulación mas rápida aun y de mejor calidad a que si se usara una distribución uniforme de temperaturas. Las contribuciones logradas han permitido obtener nuevos resultados para el área de la fı́sica, como el calculo de la matriz transferencia para el kagome lattice en m = 9 y la simulación del modelo 3D Random Field Ising Model en L = {32, 64}.

Ingeniero Civil Matemático / En los últimos años, el procesamiento de lenguaje natural (Natural Language Proces-sing, o NLP) ha experimentado importantes avances. Específicamente, en 2013, Google lanzó "word2vec", un algoritmo que propone, a partir de un corpus dado, una representación vecto-rial de las palabras que lo componen. Dicho algoritmo ha tenido un gran éxito principalmentepor dos razones: La primera es el bajo costo computacional de su entrenamiento que permitióun uso masivo, mientras que la segunda es la intuitiva topología inducida por la representación vectorial ilustrada por el popular ejemplo: word2vec("king") - word2vec("man") + word2vec("woman") = word2vec("queen") En esta memoria, presentamos en un primer lugar un ejemplo ilustrativo del algoritmo "word2vec" mediante su implementación para determinar preguntas duplicadas en Quora, una competencia propuesta por el sitio Kaggle.com. Una vez familiarizados con el algoritmo, nos enfocamos en un problema más abierto que considera el análisis de 45 obras de literatura francesa. En particular, queremos atacar la siguiente pregunta: ¿cómo se puede definir una distancia entre dos libros? Después de haber preparado los libros con el propósito de poder usar el algoritmo, propondremos varios métodos originales para comparar pares de libros. Luego, nos interesará representar estas obras en un espacio, y determinar si dicha representación revela propiedades literarias de las obras consideradas tales como la paternidad o el estilo literario.

Memoria para optar al título de Ingeniero Civil Eléctrico / En este trabajo se evaluarán distintos algoritmos de trackeo para el problema de seguimiento de peatones, donde teniendo un video obtenido de una camara de seguridad, nos interesa reconocer correctamente cada individuo a traves del tiempo, buscando minimizar la cantindad de etiquetas mal asignadas y objetos (peatones) no identificados. Para esto se ocuparán algorimos basados en el concepto de Conjuntos Aleatorios Finitos (Random Finite Sets - RFS), los cuales usan mediciones pasadas de los objetos para predecir posiciones futuras de todos ellos simultaneamente, mientras que también se consideran los casos de nacimientos y muertes de los objetos. Estos algoritmos fueron concebidos para el trackeo de objetos con movimientos simples y predecibles en condiciones de una gran cantidad ruido en las mediciones. mientras que las condiciones en las que se evaluarán son drasticamente opuestas, con un nivel muy alto de certeza en las mediciones pero con movimientos altamente no linear y muy impredecible. Se ocupará una libreria abierta creada por el investigador Ba Tuong Vo, donde están implementados varios de los más clásicos algoritmos en esta área. Es por esto que el trabajo se basará más en el análisis de los resultados en estas nuevas condiciones y observar como se comparán a los algoritmos actuales del area de Computer Vision (CV)/ Machine Learning (ML), usando tanto métricas de RFS como del área de CV.

Memoria para optar al título de Ingeniero Civil en Computación / ROS (Robot Operating System), es un framework para escribir software para robots. Con una colección de herramientas, librerías y convenciones que tienen como objetivo simplificar la tarea de crear comportamiento complejo y robusto para robots. ROS promueve la colaboración entre grupos en el desarrollo de software. Por esto, provee herramientas y librerías open source creadas por su comunidad que son alojadas en su mayoría en Github. Desarrollar software para robots involucra profesionales de distintas disciplinas que se enfocan en temas específicos. La ventaja de usar ROS, es que facilita herramientas que usuarios pueden usar sin la necesidad de especializarse en ellas para saber cómo funcionan. Es decir, por simplicidad, es una caja negra que recibe entradas y produce salidas. El problema ocurre cuando una herramienta no funciona como los usuarios creen, dado que fue desarrollada por especialistas en otros temas, entonces no tienen conocimiento suficiente para solucionar su problema. Es entonces cuando los usuarios recurren a ROS Answers, una plataforma de preguntas y respuestas. Dado que las preguntas publicadas en ROS Answers tratan temas específicos a las herramientas en sí, es importante encontrar a una persona que pueda guiar a quienes no tienen conocimiento sobre esos temas. Actualmente en ROS Answers, al igual que en StackOverflow \cite{site:StackOverflow}, las preguntas son organizadas según tags o tópicos, y cada usuario puede dar un voto positivo o negativo a una pregunta o respuesta, dependiendo de si cree que un aporte es útil o no. Estos votos en las preguntas y respuestas de un usuario, más su historial de participación dentro de esa comunidad, es la única información disponible para identificar si un usuario domina un tema, y por ende confiar en su respuesta. ROS y ROS Answers forman un ecosistema de software. Un ecosistema, es una colección de sistemas de software, que se desarrollan y evolucionan en un mismo ambiente, en este caso el ambiente es la comunidad de robótica open source. Sin embargo, falta considerar una parte importante de este ecosistema, Github. Este posee información relevante sobre la experiencia y conocimiento de usuarios que han colaborado a la comunidad, no sólo respondiendo preguntas, sino también participando activamente en el desarrollo de las herramientas que componen cada una de las distribuciones de ROS. En esta memoria se presenta una herramienta desarrollada para obtener información de usuarios de Github y ROS Answers (plataforma de preguntas y respuestas), se implementa un algoritmo de recomendación de usuarios para responder una pregunta en ROS Answers, y por último se crea un verificador para evaluar localmente el algoritmo, utilizando preguntas ya respondidas en ROS Answers. También se logra verificar la correctitud del algoritmo implementado realizando una encuesta web a usuarios de ROS Anwers, donde se consulta sobre su conocimiento para responder preguntas sobre temas que el algoritmo sugiere que ellos manejan. Este trabajo está abierto a futuras extensiones, como por ejemplo, incluir más algoritmos.

Tesis para optar al grado de Magíster en Ciencias, Mención Computación / El modelo cosmológico actual y más aceptado del universo se llama Lambda Cold Dark Matter. Este modelo nos presenta el modelo más simple que proporciona una explicación razonablemente buena de la evidencia observada hasta ahora. El modelo sugiere la existencia de estructuras a gran escala presentes en nuestro universo: Nodos, filamentos, paredes y vacíos. Los vacíos son de gran interés para los astrofísicos ya que su observación sirve como validación para el modelo. Los vacíos son usualmente definidos como regiones de baja densidad en el espacio, con sólo unas pocas galaxias dentro de ellas. En esta tesis, presentamos un estudio del estado actual de los algoritmos de búsqueda de vacíos. Mostramos las diferentes técnicas y enfoques, e intentamos deducir la complejidad algorítmica y el uso de memoria de cada void-finder presentado. Luego mostramos nuestro nuevo algoritmo de búsqueda de vacíos, llamado ORCA. Fue construido usando triangulaciones de Delaunay para encontrar a los vecinos más cercanos de cada punto. Utilizando esto, clasificamos los puntos en tres categorías: Centro, borde y outliers. Los outliers se eliminan como ruido. Clasificamos los triángulos de la triangulación en triángulos de vacíos y centrales. Esto se hace verificando un criterio de distancia, y si los triángulos contienen outliers. Este método nos permite crear un algoritmo de búsqueda de vacíos rápido y robusto. Adicionalmente, se presenta una versión paralela del algoritmo.