Catálogo de publicaciones

Esta tesis investiga posibles incrementos de la performance en las soluciones de ciertos problemas de optimización combinatorial NP-duros. Ejemplos de esto son los problemas de secuenciamiento puros. Se realiza una reseña de los métodos convencionales, comparándolos con los pertenecientes al campo de la Computación Evolutiva, conjuntamente con la propuesta de eventuales mejoras a estos últimos. Las aplicaciones prácticas discutidas en esta tesis se encuentran fuertemente relacionadas con la administración, el diseño de redes en general, y el diseño de circuitos.

Los sitios de redes sociales como por ejemplo MySpace, Facebook o Twitter atraen a millones de usuarios, quienes comparten información cotidiana sobre sus actividades, intereses y opiniones. Dichos sitios se caracterizan principalmente por proporcionar una forma simple de comunicación con un especial énfasis en su brevedad, la cual permite a los usuarios compartir imágenes, tweets, comentarios y mensajes en la forma de textos cortos. Asimismo, la participación de los usuarios en los medios sociales ya no se encuentra limitada a un único sitio, dado que usualmente utilizan múltiples sitios sociales, los cuales proporcionan fuentes de información heterogéneas y complementarias para la descripción de un usuario en particular, sus intereses y relaciones sociales. Una tarea que puede beneficiarse enormemente de la existencia de estas múltiples y ricas fuentes de información es el aprendizaje de texto a gran escala, el cual tiene implicaciones prácticas importantes en el desarrollo de técnicas de personalización o recomendación. Las tareas tradicionales de aprendizaje de texto se caracterizan por la alta dimensionalidad de los espacios de características o atributos a analizar. La selección de características (en inglés, feature selection) es una de las técnicas más utilizadas para reducir el impacto de la alta dimensionalidad del espacio de características en textos, el cual es reducido mediante la eliminación de aquellas características redundantes e irrelevantes. Las técnicas estándar de selección de características asumen la existencia de un conjunto fijo de instancias y, por lo tanto, de un espacio de características completamente conocido de antemano. Sin embargo, en aplicaciones del mundo real, tales suposiciones podrían no ser válidas. En estas situaciones, es necesario aplicar técnicas de selección de características online (en inglés, online feature selection) en la que las instancias y sus correspondientes características aparecen en un flujo continuo. Las técnicas de selección de características online involucran elegir un sub-conjunto de características y su correspondiente modelo de aprendizaje en diferentes momentos temporales. Sin embargo, la mayoría de los trabajos existentes en la literatura se centran en el desarrollo de soluciones batch, presentando así dificultades para adaptarse a los entornos del mundo real. El desarrollo de técnicas eficientes y escalables de selección de características online se constituye como un requerimiento muy relevante en numerosas aplicaciones sociales a gran escala. Los textos cortos acentúan los desafíos planteados por la alta dimensionalidad del espacio de características debido a su contexto limitado y raleza, la utilización de lenguaje y estilo informal, la propensión a errores ortográficos y gramaticales y la reducción de la significancia de las frecuencias de palabras, lo que aumenta las posibilidades de expresión de un único concepto. La mayoría de las técnicas de FS están diseñadas para datos que contienen entidades uniformes, es decir, características que se suponen típicamente independientes e idénticamente distribuidas. No obstante, los datos de los medios sociales no siguen esa suposición ya que las publicaciones realizadas por los usuarios no solo proporcionan información textual sino también información topológica debido a las relaciones entre dichas publicaciones y los usuarios. A su vez, la naturaleza vinculada de los datos de medios sociales hace que se añadan nuevas dimensiones (como las relaciones de amistad entre usuarios) al espacio de características. Por ejemplo, las publicaciones de un mismo usuario o de dos usuarios que comparten una relación de amistad tienen una mayor probabilidad de referirse a temas similares. La creciente cantidad de datos no solo afecta a la complejidad computacional de los algoritmos, sino que también plantea nuevos desafíos sobre cómo representar y procesar los nuevos datos y cómo efectivamente aprovecharlos para mejorar el rendimiento de las tareas de aprendizaje sobre texto. En este sentido, la disponibilidad de información de las relaciones entre los datos permite realizar investigaciones avanzadas en técnicas de FS. El propósito de esta Tesis es abordar la tarea de selección de características online para textos cortos en problemas de gran dimensionalidad, creados en forma continua. De esta forma, se podrán desarrollar nuevos y más eficientes modelos para la personalización y la recomendación de contenido en medios sociales. En particular, esta Tesis se centra en la clasificación en tiempo real de textos cortos continuamente generados en las redes sociales, a partir de la propuesta de una técnica de selección de características online basada en el análisis de factores sociales y del contenido publicado por los usuarios. A diferencia de los enfoques presentes en la literatura, que en su mayoría ignoran la naturaleza social de los datos, la técnica propuesta aprovecha las estructuras vinculadas en forma de redes compuestas por las publicaciones y los usuarios que las han escrito. La técnica se divide en dos etapas principales: la etapa de Análisis Social y la etapa de Análisis de Contenido. La etapa de Análisis Social pretende descubrir relaciones implícitas entre nuevas puestas y aquellas ya conocidas para superar los problemas derivados de la raleza inherente a los textos cortos y aumentar su contexto disponible. Luego, la etapa de Análisis de Contenido considera grupos de publicaciones socialmente relacionadas y analiza su contenido con el fin de seleccionar un conjunto de características no redundantes y relevantes para describir cada uno de los grupos descubiertos. Por último, las características seleccionadas son utilizadas para entrenamiento de diferentes modelos de aprendizaje para la clasificación de nuevas publicaciones. La evaluación experimental realizada en tres conjuntos de datos de medios sociales del mundo real demostró que la técnica OFS propuesta ayuda a mejorar los resultados de la clasificación en comparación con técnicas de selección de características tradicionales y del estado del arte tanto batch como online. Los resultados obtenidos evidenciaron la necesidad de considerar las relaciones sociales entre los usuarios para la clasificación de textos cortos en las redes sociales y sus ventajas para seleccionar el conjunto de características más relevante.

Los métodos formales se están usando actualmente para la construcción de sistemas reales, ya que contribuyen a aumentar la calidad y confiabilidad del software. Sin embargo, generalmente sólo son accesibles a especialistas. Esto resulta inconveniente sobre todo durante las primeras etapas del proceso de desarrollo de software cuando la participación de los stakeholders, no familiarizados con estos formalismos, es crucial. Con el objetivo de aportar una solución a este problema, presentamos en esta tesis una técnica para derivar una especificación formal inicial escrita en el Lenguaje de Especificación RAISE a partir de modelos de requisitos basados en lenguaje natural. En particular, usamos el Léxico Extendido del Lenguaje (LEL) y el Modelo de Escenario, dos modelos de la Requirements Baseline que están más cercanos al lenguaje de los stakeholders. La derivación de la especificación está estructurada en tres etapas, proponemos un conjunto de heurísticas que muestran cómo derivar tipos y funciones, y cómo estructurarlos en módulos usando la información generalmente disponible después del análisis del problema. También proponemos representar la jerarquía de módulos obtenida usando una arquitectura por niveles, que es la base para comenzar aplicar las etapas del Método RAISE. Mostramos cómo llegar a una especificación concreta, partiendo de la especificación aplicativa y parcialmente abstracta derivada, para luego obtener automáticamente un primer prototipo para validar la especificación.

La primera etapa del trabajo consistió en el análisis de las diferentes técnicas de modelado orientado a objetos y su influencia sobre el proceso de desarrollo de software basado en modelos. Este análisis nos condujo a reconocer las claras ventajas que ofrece la integración de técnicas de modelado formales con técnicas no formales aceptadas y usadas por los ingenieros de software típicos. El siguiente paso consistió en estudiar las propuestas existentes acerca de cómo efectivizar la mencionada integración, con el objetivo de identificar aspectos potencialmente mejorables. Finalmente y como consecuencia del análisis previo, definimos una nueva propuesta de integración la cual aporta los beneficios esperados para un método de integración standard pero además incorpora ciertas características que no han sido cubiertas satisfactoriamente por las propuestas anteriores, tales como evolución, reusabilidad y métricas de modelos. Además nuestra propuesta se basa en una estructura formal de primer orden que, en contraste con las estructuras de orden superior, facilita los procedimientos para calcular la validez de las fórmulas. La parte restante de esta tesis está organizada de la siguiente forma: En los capítulos 2 y 3 describimos detalladamente un lenguaje gráfico de especificación (UML) y un lenguaje formal (Lógica Dinámica) respectivamente. En el capítulo 4 discutimos las distintas propuestas para lograr la integración de ambas técnicas. En el capítulo 5 presentamos nuestra propuesta: la M&D-theory. El capítulo 6 contiene ejemplos de los principales beneficios standard provistos por la M&D-theory. En los capítulos 7, 8 y 9 demostramos la utilidad de nuestra formalización para expresar evolución de modelos, métricas de calidad y temas de reuso tales como contratos y patrones de diseño. Finalmente el capítulo 10 contiene conclusiones, reflexiones y comentarios acerca del trabajo presentado.