TRANGRAM: Transductive Analysis in Graph-based Methods

A MCYT research subproject (TIN2004-07925-C03-02) of the coordinated project GRAMMARS (TIN2004-07925-C03); also, a cooperation between the LARCA research group and the TALP research center.

This website attempts to facilitate communication and coordination of the project, and will offer downloadable deliverables both in form of papers and of software, either directly or through links to other pages

Come back every now and then!

Participants: JL Balcazar (PI; part time during the first year), J Castro, B Casas, M Martin (part time), Ll. Marquez (part time), X Carreras (part time)

Abstract: This subproject aims at making scientific progress towards three guiding ideas of high abstraction and temporal span: the models of supervised learning as simplified versions of a hypothetical notion of learning able to encompass as well unsupervised learning; the characterizations of this hypothetical notion of learnability in terms of combinatorics or topology; and the ability of the progress towards these abstract notions to orient the design of new algorithmic concepts and applications. This progress will develop along three action lines: predictive models based upon interaction, predictive models based upon examples, and transductive models.

A more detailed description (in Spanish w/o accents) follows.


Objetivos especificos

1/ Algoritmos de aprendizaje activo basados en intersecciones booleanas: Nuevos algoritmos, versiones abstractas que los generalicen, y nuevas aplicaciones de estos algoritmos, en particular para el manejo de funciones booleanas

2/ Algoritmos de aprendizaje pasivo basado en nucleos: Nuevos algoritmos y nuevas versiones de algoritmos existentes, en particular metodos incrementales transductivos, que en este momento no existen para determinadas aplicaciones

3/ Aplicaciones de los algoritmos anteriores en procesamiento del lenguaje natural y en problemas de layout de grafos

Metodologia y plan de trabajo

Este subproyecto se estructura metodologicamente en tres lineas de accion y, ortogonalmente, en ideas guia y objetivos. Las ideas guia son objetivos en nivel de abstraccion alto, cuyo alcance orienta el proyecto, pero que son de calibre elevado y se consideran inalcazables dentro del plazo del proyecto, por lo que no se consideran propiamente objetivos. El progreso hacia estas ideas guia se estructura en objetivos a lo largo de las tres lineas, que cooperan entre si en su progreso.

Las ideas guia son: los modelos de aprendizaje supervisado como versiones simplificadas de una nocion de orden superior capaz de capturar tambien el aprendizaje no supervisado; la caracterizacion combinatoria (o topologica) de la nocion de aprendibilidad; y la capacidad de ambas nociones abstractas para orientar el diseño de nuevos conceptos algoritmicos y aplicaciones. Puede verse una explicacion de la pertinencia de algunas de estas ideas guia en Balcazar 1999, en Balcazar, Dai y Watanabe 2001, y en Balcazar, Castro y Guijarro 2002, donde se presentan aproximaciones prometedoras.

Las tres lineas de accion son: (L:I) modelos predictivos basados en interaccion, (L:E) modelos predictivos basados en ejemplos y (L:T) modelos transductivos. Todos ellos se consideran en un contexto de aprendizaje supervisado.

Para cada una de las tres lineas de accion, describimos ahora los objetivos que nos marcamos para este subproyecto y las personas involucradas.

Linea L:I, O1: Algoritmos basados en intersecciones booleanas (JLB, JC; MH)

El punto de partida es la existencia de dos algoritmos adecuados para el aprendizaje de polinomios booleanos monotonos: el mas popular es el mas eficiente, pero existe una alternativa, basada en intersecciones, menos conocida, y que es la base para el aprendizaje de clausulas de Horn. Este ultimo algoritmo ha sido aplicado en multitud de areas aparentemente diferentes (incluyendo bases de datos e ingenieria del conocimiento). Debido a resultados recientes aun sin publicar (Balcazar 2004, en preparacion) tenemos motivos para esperar que este enfoque sea aun mas productivo de lo esperado, y deseamos aplicarlo (en cooperacion con M Hermo del subproyecto de San Sebastian) a las formulas propuestas por Sagiv (1980) en su trabajo sobre dependencias multivaluadas y a un modelo propuesto (en una cooperacion internacional) por nuestro grupo, las listas de decision con terminos monotonos; para este modelo aun no se conocen algoritmos generales de aprendizaje pero creemos que el enfoque basado en intersecciones podria permitir su obtencion.

Linea L:I, O2: Version abstracta que los generalice, y a un tiempo generalice el algoritmo L* (JLB, JC; MH)

El protocolo necesario para la aplicacion de Birkendorf y Simon 1998 que se explica mas adelante coincide con el estudiado para otra clase de representacion diferente en Balcazar, Diaz, Gavalda y Watanabe 1997, y que extiende el algoritmo L* de Angluin. No creemos que sea casualidad: deseamos intentar encontrar una manera de unificar el estudio recien mencionado, el algoritmo AFP, y, en su caso, los obtenidos en O1 en busca de una caracterizacion de aprendizaje eficiente en tiempo similar a las existentes para el aprendizaje eficiente en preguntas (Balcazar, Castro y Guijarro 2002).

Linea L:I, O3: Aplicabilidad de los algoritmos de O1 para la representacion de circuitos y funciones booleanas

Si lograramos extender los resultados de Guijarro, Lavin y Raghavan 2001 como pretendemos en O1, estariamos en condiciones de garantizar las condiciones suficientes caracterizadas en Birkendorf y Simon 1998 para la obtencion un modelo nuevo que permitiria una forma alternativa de sintesis de circuitos booleanos, que desarrollariamos en cooperación con el subproyecto de Barcelona; asimismo buscariamos oportunidades de cooperar con los propios Birkendorf y Simon de la universidad de Bochum.

Linea L:E, O4: Versiones de los algoritmos subcuadraticos de entrenamiento de SVM adaptadas a dimensionalidad alta (JLB, JC, XC, BC)

Las ideas desarrolladas a nivel puramente teorico en Balcazar, Dai y Watanabe 2001 son prometedoras, a condicion de aplicarse en contextos de dimensionalidad reducida, quiza artificialmente mediante un proceso de seleccion de atributos. Seria deseable tener alternativas igualmente solidas para el caso en que no se de esta condicion, asi como analisis mejorados de los factores constantes que seran influyentes en la practica.

Linea L:E, O5: Identificacion de los subsistemas mas adecuados para el uso de los algoritmos de O4 en las tareas que aparecen en el total del proyecto coordinado (JLB, LM, XC, MM, BC)

Dichos algoritmos, en efecto, reciben como parametro un "solver" local arbitrario; a efectos de correccion y del tiempo esperado de calculo, modulo constantes, la eleccion de ese parametro es irrelevante, pero en la practica influira en los factores constantes de manera importante, y se requiere un trabajo comparativo experimental para completar adecuadamente el dise~o.

Linea L:E, O6: Aplicacion de O4 y O5 al procesamiento de lenguaje natural (LM, XC, MM, BC)

Los algoritmos obtenidos podrian producir importantes avances, a juzgar por los resultados preliminares con predictores mas sencillos que las SVM obtenidos recientemente por tres investigadores del equipo (Marquez, Carreras y Castro 2003), especialmente en aplicaciones de analisis sintactico parcial, pero tambien, concebiblemente, en areas de "information extraction" y en alineamiento sintactico-semantico de "corpora". Esta ultima tarea, que ataca un tema en estos momentos candente, seria de gran interes si se obtuvieran progresos, ya que para la realizacion de sistemas de traduccion automatica estadistica el alineamiento frase a frase hoy disponible obliga a trabajar a nivel de palabra, y para poder trabajar a nivel de constituyente es preciso un alineamiento semantico adicional entre los arboles de analisis. El grupo dispone o dispondra en breve plazo de los "corpora" multiling"ues necesarios (en castellano, catalan e ingles).

Linea L:T, O7: Nuevos algoritmos, similares a los de O4, para entrenamiento de SVM transductivas (MM, LM, BC)

En los sistemas transductivos, se aplican metodos de aprendizaje supervisado en el caso en que, ademas del conjunto de entrenamiento, etiquetado, se dispone, aunque sin etiquetar, de la totalidad del conjunto de prueba. Esta situacion se da en muchos casos practicos, y resulta especialmente importante cuando el conjunto de entrenamiento es peque~o en relacion a la dimension Vapnik-Chervonenkis de la clase de hipotesis. Aun sin etiquetas, la mera identidad de los puntos en que se aplicara el modelo predictivo obtenido proporciona informacion util que mejora los resultados de modo importante. Existen diversos motivos para experimentar con SVM transductivas en vez de predictivas en este proyecto. De una parte, Joachims 2003 demuestra una relacion entre estos predictores y el analisis espectral de grafos, cuyo estudio exige obviamente la cooperacion entre este subproyecto y los demás que conforman el proyecto coordinado. Por otra, tanto en tareas de analisis sintactico parcial como de "information extraction", parece que seran preferibles, a la vista de los resultados existentes, y debido a que estas tareas han de desarrollarse a partir de un numero muy limitado de ejemplos en relacion a la complejidad de la tarea. La dificultad que imposibilita en estos momentos este desarrollo es que los sistemas disponibles para entrenar SVM transductivas no son incrementales, mientras que creemos que podriamos obtener algoritmos incrementales a partir de las estrategias desarrolladas en las tareas anteriormente enumeradas.

Linea L:T, O8: Aplicación de O7 al procesamiento de lenguaje natural (LM, XC, BC)

Este objetivo es el equivalente a O6 una vez se disponga de métodos incrementales transductivos.

Linea L:T, O9: Comparativa en la aplicación de O4 y O7 a problemas de "layout" de grafos (JLB, MM, BC) Este objetivo se corresponde con un permanente analisis comparativo de nuestros avances con los realizados en los otros subproyectos, de manera que podamos contribuir inmediatamente aplicando nuestros avances si se detecta la posibilidad de hacerlo.