PILOH – Desarrollo de una herramienta software para la resolución de problemas de ingeniería lingüística mediante optimización heurística (2007)

  • Name: PILOH – Desarrollo de una herramienta software para la resolución de problemas de ingeniería lingüística mediante optimización heurística
  • Principal investigator: Abraham Duarte
  • Funding entities: URJC y Comunidad de Madrid (URJC-CM-2006-CET-0603)
  • Duration: 01/01/2007 – 31/12/2007

El tratamiento y organización de la enorme cantidad de información en formato electrónico de la que se dispone actualmente se han convertido en una necesidad dentro de esta Sociedad de la Información en la que vivimos. En consecuencia, no tendría sentido disponer de grandes repositorios de información de carácter lingüístico en los que no pudiéramos extraer un conocimiento útil. Este proyecto se enmarca dentro del área de la optimización heurística aplicada a problemas del Procesamiento de Lenguaje Natural e Ingeniería Lingüística. En este proyecto se desarrollará un software para la optimización de diferentes problemas de optimización con el objetivo de dar solución a dos de los grandes problemas a los que se enfrenta actualmente el campo del Procesamiento del Lenguaje Natural: la clasificación automática y el agrupamiento, o clustering, de documentos.

Los problemas que se pretenden abordar están basados en modelos estructurados; es decir, en los que se conoce una descripción o formulación matemática completa. Se propondrán diferentes modelos de resolución eficientes basados en procedimientos metaheurísticos. Los métodos que se propongan serán comparados con los mejores métodos de resolución existentes para ese tipo de problemas, tanto en el ámbito académico como en el comercial. Se pretende que esto dé lugar, tanto a una aplicación que proporcione soluciones de gran calidad, como a publicaciones científicas de impacto internacional.

COSYO – COmplex SYstem Optimization (2009)

  • Name: COSYO – COmplex SYstem Optimization
  • Principal investigator: Abraham Duarte
  • Funding entities: URJC y Comunidad de Madrid (URJC-CM-2008-CET-3731)
  • Duration: 01/01/2009 – 31/12/2009

Existe un tipo de problemas de optimización especialmente difíciles de resolver en los que se dispone sólo de información parcial, denominados Sistemas Complejos. En ellos no se tiene una descripción explícita del problema ya que algunos de sus elementos característicos, como son la función objetivo o las restricciones, se obtienen de forma indirecta. Como consecuencia, éstos se tratan como una caja negra.

El proyecto de investigación se centrará en el diseño de un Solver genérico (Context-Independent Solver) para la optimización de sistemas complejos mediante técnicas metaheurísticas. El Solver desarrollado generará soluciones como entrada a la caja negra y posteriormente analizará el resultado devuelto, extrayendo información sobre las soluciones, de tal forma que iterativamente se vayan generando soluciones de mayor calidad

Para diseñar el Solver, en primer lugar se categorizarán los problemas en función de si están descritos mediante variables enteras, permutaciones de elementos o variables continuas. Posteriormente, se diseñará un método basado en metaheurísticas para resolver cada tipo de problema. El último paso del diseño del Solver genérico consistirá en la integración de los tres métodos en un único esquema general que seleccionará el más adecuado para la resolución de cada problema. El Solver se complementará con una implementación del mismo en una herramienta denominada COSYO.

COSYO será un Solver genérico para la optimización de sistemas complejos modelados como una caja negra. Se considerarán dos perfiles de usuario de la herramienta. Por un lado, investigadores o profesionales con conocimientos de optimización (usándolo como librería de programación) y, por otro lado, profesionales que no tengan conocimientos avanzados en optimización (usándolo desde la hoja de cálculo de OpenOffice.org)

Los métodos propuestos en el desarrollo del proyecto se compararán con los mejores métodos existentes para ese tipo de problemas tanto en el ámbito académico como en el comercial. Esto dará lugar tanto a una aplicación que proporcione soluciones de gran calidad como a publicaciones científicas de impacto internacional.

MA2VICMR – Mejorando el Acceso, el Análisis y la Visibilidad de la Información y los Contenidos Multilingües y Multimedia en Red para la Comunidad de Madrid (2010 – 2013)

  • Name: MA2VICMR – Mejorando el Acceso, el Análisis y la Visibilidad de la Información y los Contenidos Multilingües y Multimedia en Red para la Comunidad de Madrid
  • Principal investigator: Abraham Duarte
  • Funding entities: Comunidad de Madrid y Fondo Social Europeo (S2009/TIC-1542)
  • Duration: 01/01/2010 – 31/12/2013

Los sistemas de acceso a la información multimedia que trabajan sobre colecciones de imágenes suelen tener acceso a dos tipos de datos: los descriptores textuales y el contenido visual de las imágenes. Tradicionalmente, estos sistemas han abordado o bien el problema de la recuperación de imágenes analizando la información textual asociada (Text­Based Information Retrieval, TBIR) o bien analizando el contenido visual (Content­Based Information Retrieval, CBIR). Hasta hace unos pocos años, las aproximaciones mixtas no aportaban ninguna ventaja a los resultados, además de ser bastante ineficientes.

Por un lado, investigadores de NLP&IR­UNED y del grupo de Vision Team de la Universitat de Valencia coordinaron su experiencia previa en recuperación textual y la basada en contenido de imágenes. Fruto de los trabajos de esta colaboración, ha sido una aproximación que no solo se aprovecha de la sinergia entre los aspectos visuales y de las anotaciones textuales conjuntamente, sino que además aporta un método de cálculo eficiente para la búsqueda de imágenes anotadas en grandes colecciones, a partir de una consulta multimedia, ya sea texto y una o varias imágenes. Este trabajo ha generado, además de participaciones en competiciones como ImageCLEF y MediEval, varias publicaciones en actas de congresos, un artículo en la revista IEEE Transactions on Multimedia Journal y una tesis doctoral en el grupo NLP&IR­UNED titulada Fusión Multimedia Semántica Tardía aplicada a la Recuperación de Información Multimedia.

Por otro lado, otro equipo mixto formado por integrantes de NLP&IR­UNED y GAVAB­URJC han integrado tecnologías previas para construir un sistema híbrido de búsqueda de imágenes. La propuesta, que combinaba rasgos de contenido y análisis del texto enriquecido con recursos lingüísticos como WordNet, participó en dos ediciones de la competición Photo Annotation Task de ImageCLEF.

DIETHA – Diseño, Implementación y Explotación de Técnicas Heurísticas Avanzadas (2013 – 2015)

  • Name: Diseño, Implementación y Explotación de Técnicas Heurísticas Avanzadas
  • Principal investigator: Abraham Duarte
  • Funding entities: Ministerio de Economía y Competitividad (TIN2012-35632-C02-02)
  • Duration: 01/01/2013 – 31/12/2015

There are a large amount of problems that are framed within the context of combinatorial optimization characterized by the high interest associated with their practical resolution. This project deals with five distinct families of combinatorial problems. These are:

  • Ordering problems: with applications in VLSI design or in the efficient resolution of systems of equations.
  • Location problems: with interest in telecommunication applications such as distribution of signal regenerators or network design.
  • Graph-based problems: with applications in the distribution of electronic devices in electronic boards or in image segmentation.
  • Routing problems: by focusing on multi-objective problems with applications in the transport of hazardous materials or in recommendation systems.
  • Selection problems: with applications in the construction of diverse groups or clustering of documents.

The methodology to solve the problems described above are metaheuristics procedures, among which we can highlight evolutionary algorithms, tabu search, variable neighborhood search or GRASP, to name some of the best known. For each combinatorial problem, we will propose the most suitable metaheuristic according to their mathematical structure or model. We will mainly focus on design of novel strategies to obtain high quality solutions. Besides, it is expected to figure out general strategies that can be easily applied to other related problems. We will also focus on the efficient and flexible implementation of those strategies, taking advantage of new language programming features and multi-core microprocessors. Finally we will focus on exploitation through a management platform, which integrates the problems addressed above. Simultaneously, we will develop an application to put into production (in the companies interested in our research project) the algorithms developed during the project.

In addition to solve the problems presented above, a second objective of the project is to develop the metaheuristic methodologies themselves. To successfully meet this challenge the research team has researcher Nenad Mladenovic, which developed in conjunction with Pierre Hansen the variable neighborhood search methodology.

All these problems will be integrated into Optsicom, a software tool that allow the execution of algorithms devoted to solve optimization problems and analyze the associated results. Optsicom can be used at two levels: as an end-user or as a researcher on heuristic methods. In this line, the problems integrated in Optsicom will also be available via the Web at Optsicom Repository, a web platform for comprehensive management of optimization problems. This platform will post all the information associated with an optimization problem. For each problem, it is expected to store the description, algorithms, instances, experimental results and relevant references. Furthermore, the results obtained by executing the algorithms can be compared using different statistical tests that are available as part of the software tool.