Description
 
This open house aims at exploring techniques for the analysis of (online) algorithms for learning the labeling of a graph. Learning over graphs is an emerging topic which shares intrinsic equivalences with the literature on kernel-based and similarity-based learning algorithms, but additionally aims at making explicit reference to results in graph theory. The focus here will lie on online algorithms which gradually refine a prediction rule as more information (labels) becomes available. The geometric arguments underlying online learning algorithms appear particularly appropriate to exploit graph structure, and in generality to learn how to exploit properties of the domain structure.
 
This precise learning topic was already explored e.g. in [3, 1, 4, 2], resulting in several algorithms each having its own analytical learning guarantees (e.g. perceptron-on-a-graph, POUNCE and the Graphtron). A particularly interesting question in this setting as set out in [1] is whether it is possible to device concept-free learning guarantees: while for comparing learning algorithms it is desirable to have complexity measures that depend on the underlying (unknown) concept, for making apriori reliable learning-cost estimates ('how hard is the learning task going to be?') it is desirable to have complexity measures that depend only on the structure of the underlying graph. The search for a relevant graph invariant was already partially answered in the above citations, and proposals include the minimum path cover size, the graph-diameter or the eigenspectrum of the graph. This fundamental question formed the motivation for organizing this project.
 
The practical merits of this short project is expected to be (i) an overview of appropriate principles for devising learning algorithms over a graph and related graph invariants; (ii) the identification of crucial open questions in the present context; (iii) a collection of benchmark-problems together with desired properties of complexity measures as well as, hopefully, examples of complexity measures satisfying these properties. This collection will serve to measure progress in this exciting area of learning.
 
 
 
Tentative Schedule
 
 
 
Mo.:                Arrival Monday evening at the Kaiser hotel
 
Tue.am.:        
    - 11.00 - 11.15    Opening,
    - 11.15 - 12.00   Settings.pdf   and Hyp.pdf
    - 12.00 - 13.00    Collection of interesting and Challenges.pdf cases (graphs)  
Tue.pm.:      
    - 14.30-17.00      Literature overview  
Tue.evening.:         Dinner    
 
 
 
Wed..:      One-day workshop        
        am
        - 10.00-10.50.  N. Cesa-Bianchi (TBA)
        - 10.50-11.40.  M. Herbster (TBA)        
        - 11.40-12.00.  Coffee  
        - 12.00-12.40.  T. Gaertner (TBA)
 
        pm
        - 02.30.-03.20  D. Pechyony:
                On the consistency of transductive algorithms
 
  1. Consistency of learning algorithm states that its
  2. error approaches the best possible one as the
  3. training sample increases. Many inductive algorithms
  4. are proven to be consistent. However in the
  5. transductive setting the results about consistency
  6. have only started to appear. In this talk we consider
  7. a family of offline graph-based transductive algorithms
  8. performing regularization in reproducing kernel Hilbert
  9. space. Using the stability-based transductive risk
  10. bounds we outline the conditions for the consistency
  11. of these algorithms. In particular, we show that the
  12. rate of convergence of the algorithms to the best
  13. hypothesis is determined by the geometry of the
  14. underlying graph and the alignment of the graph with
  15. the training labels.
 
        - 03.20 - 04.10 K. Pelckmans:
                The Graphtron for Online Learning over a Graph
 
        - 04.10 - 04.40 Coffee
        - 04.40 - 05.20 F. Vitale (TBC)
        - 05.20 - 05.50 G. Lever (TBC)
Wed.evening.: Dinner
 
 
Thu.am.:        
     - 11.00 - 13.00   Discussion on 'complexity' in graphs and learning algorithms.
Thu.pm.:  
     - 14.30 - 17.00   Collection of open questions
Thu.evening.: TBA
 
 
Fri.am:                 Departure
 
 
 
References
 
[1] T. Gartner and G.C. Garriga. The cost of learning directed cuts. In Proceedings of the 18th European Conference on Machine Learning, 2007.
 
[2] M. Herbster. Exploiting cluster-structure to predict the labeling of a graph. In Proceedings of The 19th International Conference on Algorithmic Learning Theory(ALT'08), 2008.
 
[3] M. Herbster and M. Pontil. Prediction on a graph with a perceptron. In B. Scholkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19, pages 577{584. MIT Press, Cambridge, MA,2007.
 
[4] K. Pelckmans and J.A.K. Suykens. An online algorithm for learning a labeling of a graph. Presented on MLG 2008, Helsinki, 2008.
 
                                    Open House on
Algorithms for Graph Label Prediction
 
 
  1. When: Monday 17 - Friday 21 November, 2008
  2.  
  3. Format: an open-house during 3 full days, centered around a one-day workshop with invited speakers.
  4.  
  5. Where: Bonn, Germany
  6. Fraunhofer Gesellschaft  -Institutszentrum Schloss Birlinghoven . Travel directions and  a Map of the campus. We'll be in building C1 (2nd floor, room c1-214) on Tue/Wed and in building B3 (3rd floor, room b3-318) on Thursday.
  7. .
  8. Who: Thomas Gaertner, Mark Herbster,, Kristiaan Pelckmans
  9.  
  10. Hotel: Kaiser Karl Hotel, Bonn
  11.  
  12. Contact: Kristiaan.pelckmans@esat.kuleuven.be