Category Archives: Uncategorized

Optimización combinatoria

La optimización combinatoria es la búsqueda de los valores de ciertos elementos (variables) que optimicen una función objetivo definida sujeta a un conjunto de restricciones. Dado que son varios los elementos que se buscan, la combinación de diferentes valores en cada variable forman conjunto de soluciones posibles.

Cuando el espacio de búsqueda es "infinito" se aplican diferentes técnicas y algoritmos que ayuden a encontrar una buena solución en vez de la mejor (la que optimiza la función) ya que el costo (tiempo) de realizar la búsqueda de la mejor puede ser demasiado. Entonces se evalúa el costo-beneficio del problema para aceptar una buena solución encontrada.

Bibliografía básica: 

  • Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization : Algorithms and Complexity

  • Bernhard Korte, Jens Vygen; Combinatorial Optimization: Theory and algorithms

Procesamiento de lenguaje natural

El campo de Procesamiento de Lenguaje Natural (PLN) tiene como objetivo conseguir que las computadoras realicen tareas útiles que involucren al lenguaje humano, tales como permitir la comunicación humano – máquina, mejorar la comunicación humano – humano, o simplemente procesar texto o voz de forma útil.

Uno de los mayores retos que debe ser afrontado en el campo de PLN proviene del hecho que el lenguaje natural, a diferencia del lenguaje de máquina, es frecuentemente ambiguo. Se dice que un texto es ambiguo si es que existen múltiples alternativas de estructuras lingüísticas que pueden ser construidas para él. Por ejemplo, en la oración “Estuve esperándote en el banco” no se sabe si la persona estuvo sentada en un banco o en una institución financiera.

Debido a la frecuencia con la que se presentan estos casos de ambigüedad y las complicaciones que genera para conseguir un entendimiento pleno de lo que se está expresando, la investigación en PLN presenta varios desafíos y es promete ser útil en una gran variedad de aplicaciones como: traducción automática, sistemas de preguntas y respuestas, extracción de información, elaboración automática de resúmenes, simplificación textual, entre otros.

En GRPIAA, los proyectos en PLN están principalmente abocados a dos líneas de investigación: implementación de herramientas de apoyo para la redacción de textos científicos, y análisis de complejidad y simplificación de textos en español. Para ambas líneas, los proyectos involucran el uso de métodos de aprendizaje de máquina basados en corpus.

 

Bibliografía básica: 

  • JURAFSKY, Daniel; MARTIN, James H. 2007          Speech and Language Processing: An introduction to Natural Language Processing, Computations Linguistics, and Speech Recognition. Upper Saddle River: Pearson Prentice Hall.

  • MANNING, Christopher; SHUTZE, Hinrich. 1999       Foundations of Statistical Language Processing. Segunda edición. Londres: Instituto Tecnológico de Massachusetts.

  • BIRD, Steven; KLEIN, Ewan; LOPER, Edward. 2009            Natural Language Processing with Python. s/c: Natural Language Toolkit.

Herramientas y software recomendado:

  • FreeLing: An open source suite for language analyzers (http://nlp.lsi.upc.edu/freeling/) Brinda diferentes herramientas para procesar texto en diferentes idiomas, incluido es Español.

  • Weka 3: Data Mining Software in Java (http://www.cs.waikato.ac.nz/ml/weka/) Proporciona una colección de algoritmos de aprendizaje de máquina.

  • NLTK: Natural Language Toolkit (http://www.nltk.org/) Plataforma para construir programas en Python que trabajen con datos del lenguaje humano.

Representación del conocimiento

En sus inicios, la investigación en Inteligencia Artificial (IA) se centró en el desarrollo de formalismos, mecanismos de inferencia y herramientas para poner en práctica Sistemas Basados en Conocimiento (SBC). Típicamente, los esfuerzos de desarrollo se limitaron a la realización de SBC pequeños, a fin de estudiar la viabilidad de nuevos enfoques. Aunque estos estudios dieron a luz resultados prometedores, la transferencia de esta tecnología para la construcción de SBC comerciales fracasó en muchos casos. Esta situación fue comparable con la “crisis del software” de la años 60.

Así como la crisis del software trajo como resultado el establecimiento de la disciplina de Ingeniería de Software (IS), la situación insatisfactoria en la construcción de SBC puso de manifiesto la necesidad de enfoques más metodológicos. De esta manera, el objetivo de la Ingeniería del Conocimiento (IC) es similar al de la IS: tornar la construcción de SBC en un proceso sistemático y controlable. Esto requiere análisis de los procesos de construcción y mantenimiento así como el desarrollo de métodos, lenguajes y herramientas adecuadas.

La nueva Ingeniería del Conocimiento surge para disminuir esta brecha y para hacer del Ingeniero del Conocimiento, el principal actor e interface entre la tecnología y la gestión. Para esto, reconoce la importancia del proceso de modelado y de la visión sistémica del ingeniero. Pero esta no es una tarea fácil ya que generalmente la Gestión del Conocimiento desconoce la existencia de la IC, atribuyendo la parte tecnológica a las TICs.

Bibliografía básica: 

Sobre Ingeniería del Conocimiento

  • R. Studer, V. R. Benjamins, and D. Fensel, “Knowledge engineering: Principles and methods,” Data & Knowledge Engineering, vol. 25, no. 1–2, pp. 161-197, 1998.

  • R. Studer, S. Decker, D. Fensel, and S. Staab, “Situation and perspective of knowledge engineering,” Knowledge Engineering and Agent Technology, 2000.

  • G. Schreiber, H. Akkermans, A. Anjewierden, R. d. Hoog, N. Shadbolt, W. V. d. Velde, and B. Wielinga, Knowledge engineering and management: the CommonKADS methodology, Cambridge Massachussets: The MIT Press, 1999.

Sobre Ontologías

  • T. R. Gruber, “A translation approach to portable ontology specifications,” Knowledge acquisition, vol. 5, no. 2, pp. 199-220, 1993.

  • T. R. Gruber, “Toward principles for the design of ontologies used for knowledge sharing?,” International Journal of Human-Computer Studies, vol. 43, no. 5–6, pp. 907-928, 1995.

  • M. Uschold, and M. Gruninger, “Ontologies: Principles, methods and applications,” Knowledge engineering review, vol. 11, no. 2, pp. 93-136, 1996.

  • B. Chandrasekaran, J. R. Josephson, and V. R. Benjamins, “What are ontologies, and why do we need them?,” IEEE Intelligent Systems and their Applications, vol. 14, no. 1, pp. 20-26, 1999.

  • O. Corcho, and A. Gómez-Pérez, "A roadmap to ontology specification languages," Knowledge Engineering and Knowledge Management Methods, Models, and Tools, pp. 80-96: Springer, 2000.

Sobre Web Semántica

  • T. Berners-Lee, J. Hendler, and O. Lassila, “The semantic web,” Scientific American, 2001.

  • M. C. Daconta, L. J. Obrst, and K. T. Smith, The Semantic Web: a guide to the future of XML, Web services, and knowledge management: Wiley. com, 2003.

  • J. Davies, D. Fensel, and F. V. Harmelen, Towards the semantic web: Wiley Online Library, 2003.

  • G. Antoniou, A semantic web primer: the MIT Press, 2004.

Sobre Anotación Semántica

  • S. Staab, A. Maedche, and S. Handschuh, “An Annotation Framework for the Semantic Web,” 2001.

  • A. Kiryakov, B. Popov, I. Terziev, D. Manov, and D. Ognyanoff, “Semantic annotation, indexing, and retrieval,” Web Semantics: Science, Services and Agents on the World Wide Web, vol. 2, no. 1, pp. 49-79, 2004.

  • O. Corcho, “Ontology based document annotation: trends and open research problems,” International Journal of Metadata, Semantics and Ontologies, vol. 1, no. 1, pp. 47-57, 2006.

Sobre Recuperación de Información

  • J. v. Rijsbergen, Information Retrieval, 2 ed.: London: Butterworths, 1979.

  • G. Salton, “A blueprint for automatic indexing,” SIGIR Forum, vol. 16, no. 2, pp. 22-38, 1981.

  • P. Ingwersen, Information retrieval interaction: Taylor Graham Publishing, 1992.

  • R. A. Baeza-Yates, and B. Ribeiro-Neto, Modern Information Retrieval: Addison-Wesley Longman Publishing Co., Inc., 1999.

  • M. Mitra, and B. B. Chaudhuri, “Information Retrieval from Documents: A Survey,” Inf. Retr., vol. 2, no. 2-3, pp. 141-163, 2000

  • L. Cerulo, and G. Canfora, “A taxonomy of information retrieval models and tools,” Journal of Computing and Information Technology, vol. 12, no. 3, pp. 175-194, 2004.

Sobre Extracción de Información

  • J. R. Hobbs, “The generic information extraction system,” in Proceedings of the 5th conference on Message understanding, Baltimore, Maryland, 1993, pp. 87-91.

  • K. Zechner, "A literature survey on information extraction and text summarization," Computational Linguistics Program, Carnegie Mellon University, 1997.

  • H. Cunningham, "Information Extraction-A User Guide," University of Sheffield, UK, 1999.

  • M. Abolhassani, N. Fuhr, and N. Gövert, “Information extraction and automatic markup for XML documents,” Lecture Notes in Computer Science, vol. 28, no. Intelligent Search on XML Data, pp. 159-174, 2003.

  • D. Maynard, K. Bontcheva, and H. Cunningham, “Towards a semantic extraction of named entities,” Recent Advances in Natural Language Processing, 2003.

  • J. Turmo, A. Ageno, and N. Catala, “Adaptive information extraction,” ACM Comput. Surv., vol. 38, no. 2, pp. 4, 2006.

Herramientas

Procesamiento de imágenes y visión computacional

Visión por computador (o interpretación de imágenes) representa un sub-area de la Inteligencia Artificial que tiene como objetivo el análisis y la interpretación de la información visual. La comprensión de la imagen se considera como un proceso que parte en una imagen o secuencia de imágenes (por ejemplo, proyecciones 2D de una escena estática o dinámica) y termina en una descripción interna de la escena. Los problemas de la interpretación de imágenes son el núcleo de los esfuerzos actuales para permitir hacer una máquina que tenga interacciones "inteligentes" con su entorno. Los sensores se utilizan para obtener información de su entorno 3D que puede ocurrir en forma de lenguaje natural, imágenes, sonidos, etc.. Esta información se procesa con el fin de llegar a las diferentes formas de representación interna, permitiendo que la máquina interactúe con el medio ambiente, ya sea en forma lingüística o por alguna acción del robot. Las representaciones internas forman el "conocimiento" o los "modelos" de la visión por computador basada en el conocimiento. De acuerdo a la metodología convencional, la complejidad de los pasos del proceso se domina mediante la formulación y el estudio de cada problema cognitivo en tres niveles independientes entre sí, los niveles de la teoría computacional, algoritmos e implementación(Marr D. 1982. Vision).

Aprendizaje de máquina

Es una rama de inteligencia artificial cuyo objetivo es desarrollar algoritmos que permitan a los computadores aprender automáticamente e ir mejorando tal aprendizaje con la experiencia. Entiéndase por aprender a, reconocer patrones complejos y tomar decisiones inteligentes basadas en dichos patrones.  De esta forma, los computadores serán capaces de generalizar comportamientos a partir de cierta información suministrada en forma de ejemplos. Cabe destacar que esta es una área multidisciplinaria, que tuvo-tiene-tendrá un gran impacto en múltiples aplicaciones como: procesamiento de lenguaje, previsión del clima, reconocimiento de patrones, juegos, minería de datos, sistemas expertos, robótica, entre otras.


Bibliografía básica: 

  • The Elements of Statistical Learning Data Mining, Inference and Prediction. Trevor Hastie, Robert Tibshirani and Jerome Friedman.  (url: http://statweb.stanford.edu/~tibs/ElemStatLearn/)

  • Foundations of Machine Learning. Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar.

  • An Introduction to Statistical Learning with Applications in R. Gareth James, Daniela Witten, Trevor Hastie and Robert Tibshirani. (url: http://www-bcf.usc.edu/~gareth/ISL/) 

  • Pattern Recognition and Machine Learning. Bishop, Christopher M.


Herramientas:  

  • Weka (url:http://www.cs.waikato.ac.nz/ml/weka/)

  • ML Demos (url:http://mldemos.epfl.ch/)

  • Scikit-Learn.Python (url:http://scikit-learn.org/stable/)

Desarrollo de algoritmos paralelos para la recuperación por contenido en imágenes médicas

paralelosLos sistemas de recuperación de imágenes basadas en el contenido (Content-based image retrieval – CBIR) se refieren a la capacidad de recuperar imágenes considerando el contenido de las mismas. Dada una imagen de consulta, el objetivo de un sistema CBIR es buscar dentro de una base de datos y recuperar las “n” imágenes más similares a aquella dada en la consulta, basado en algún criterio definido.

 

El presente trabajo de investigación está orientado a la generación de vectores de características de un sistema CBIR orientando la aplicación final para base de datos de imágenes médicas. Un vector de características es una representación numérica de una imagen, o de una porción de ella, sobre sus características más representativas. Este vector de características es un vector n-dimensional que contiene elementos cuyos valores describen en forma sucinta el contenido de una imagen. Esta nueva representación de la imagen puede ser almacenada en una base de datos y así permitir una rápida recuperación de imágenes. Una alternativa para facilitar este proceso es utilizar técnicas de transformación de dominio. La principal ventaja de una transformación, es su efectiva caracterización de las propiedades locales de la imagen. Hace pocos años atrás que investigadores de las áreas de matemática aplicada y de procesamiento de señales desarrollaron una técnica de transformación de señales, denominada de wavelet para la representación multi-escala y análisis de señales. Las transformadas de wavelets, a diferencia de la tradicional técnica de Fourier, localizan la información en el espacio de tiempo-frecuencia, en forma particular, tienen una capacidad para intercambiar una resolución por otra, lo cual hace de ellas especialmente indicadas para el análisis de señales en distintas bandas de frecuencia, donde cada resolución tiene su correspondiente escala. Estas transformadas fueron aplicadas con mucho éxito en aplicaciones como compresión de imágenes, mejoramiento, análisis, clasificación y recuperación. Una de las privilegiadas áreas de aplicación donde estas propiedades fueron encontradas como relevantes es el área médica.

En este proyecto se describe una estrategia CBIR para base de datos de imágenes médicas a fin de extraer características basadas en descomposición multi-resolución, bajo plataforma GPU aplicando algoritmos paralelos. Aspecto importante de la presente investigación está en cómo hacer para caracterizar (indexar) las imágenes de forma que el proceso de recuperación pueda retornar las imágenes visualmente más similares en el dominio de interés y en forma eficiente, en términos de recurso computacional.

cropped-GRPIAA_logo3.png