W I L L K O M M E N
Universität Freiburg - Institut für Informatik
Lehrstuhl für Mustererkennung und Bildverarbeitung (LMB)
[-]LMB
   [+]People
   [-]Research
    |  | Gebiete:
    |  |-Invariant theory
    |  |-Design of Classifiers
    |  |-Computer Vision
    |  |-Motion and Depth Estimation
    |  |-Digital Image Filtering 
    |  |-Multi Spectral Image Analysis
    |  |-Fast and Parallel Algorithms
    |  | Laufende Projekte
    |  |-Computer Vision
    |  |-Invariance in Kernel Methods
    | [+]I-search
    |  |-OMIB
    |  |-OMNIBUSS
    |  | Abgeschl. Projekte
    |  |-NOBLESSE
    |  |-MOVIS ()
    |  |-SFB-238 ()
    |  |-Parallelisierung ()
    |  |-Automatische Sichtprüfung... ()
    |     ()
   [+]Studien-, Diplom- und Bachelor... ()
   [+]Lectures
    |-Events
    |-Publications
   [+]Awards
   [+]Jobs/Vacancies
    |-TILDA
   [+]Software
   [+]Interna ()


 Printer optimized version of this page

[keine Deutsche Seite verfügbar]

Invariance in Kernel Methods

Project Members

Introduction

Modern techniques for data analysis and machine learning are so called kernel methods. The most famous and successful one is represented by the support-vector machine for classification or regression tasks. The fundamental ingredient in these methods is the choice of a kernel function, which computes a similarity measure between two input objects. Many simple kernel functions already produce very good results on various application fields. Experience has demonstrated that these impressive results even can substantially be improved by incorporating problem specific a-priori knowledge. Intuitively this is also perspicuous, as e.g. elimination of known redundancies of data in a preprocessing stage will place emphasis on the non redundant contributions and simplify the further processing chain.

This project focusses on a certain kind of a-priori knowledge namely invariance knowledge. This comprises explicit or implicit knowledge of pattern transformations that do not or only slightly change the pattern's inherent meaning.
Explicit transformation knowledge means that one can explicitly parametrize the transformations of a pattern. Examples are global rigid transformations of 2D/ 3D objects in object detection or non rigid resp. only local transformation like slight stretching, shifting, rotation of characters in optical character recognition. The mathematical modelling is realized by transformation groups, subsets of transformations groups or arbitrary sets of transformations.
Implicit invariance means that the variations are implicitly captured by sophisticated comparison measures between objects. Examples are dynamic time warping techniques, which capture time variations in signals. Here an explicit parameterization would require arbitary many parameters. More generally, implicit invariances are often given by distance measures between objects.

These kinds of invariances are incorporated in kernel functions by approximation or integration techniques. Theoretical investigation of the kernels is performed and applicability is demonstrated by support vector classification of various types of data like optical characters, handwriting sequences or pollen classification.

References

  1. B. Schölkopf and A. Smola, Learning with Kernels. MIT Press, 2002.
    Comprehensive reference book for kernel methods. In particular Chapter 11 discusses invariance issues.

Links of related projects

Publications

  1. Haasdonk, B. Transformation Knowledge in Pattern Analysis with Kernel Methods. PhD thesis, Computer Science Department, University of Freiburg, submitted may 2005.

  2. Haasdonk, B., Vossen, A. and Burkhardt, H., Invariance in Kernel Methods by Haar-Integration Kernels. SCIA 2005, Scandinavian Conference on Image Analysis, pp. 841-851, Springer-Verlag, 2005.

  3. Haasdonk, B., Feature Space Interpretation of SVMs with Indefinite Kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(4):482-492, april 2005.

  4. Haasdonk, B., Bahlmann, C. Learning with Distance Substitution Kernels. DAGM 2004, Tübingen, August 2004.

  5. Haasdonk, B., Halawani, A., Burkhardt, H. Adjustable Invariant Features by Partial Haar-Integration. ICPR 2004, International Conference on Pattern Recognition, Cambridge, UK, August 2004.

  6. Haasdonk, B., Feature Space Interpretation of SVMs with non Positive Definite Kernels. Internal Report 1/03, IIF-LMB, University Freiburg, Germany, October 2003.

  7. O. Ronneberger, E. Schultz and H. Burkhardt. Automated Pollen Recognition using 3D Volume Images from Fluorescence Microscopy. Aerobiologia, 18: pages 107-115,2002.

  8. Haasdonk, B., Keysers, D., Tangent Distance Kernels for Support Vector Machines. ICPR 2002, International Conference on Pattern Recognition, Quebeq City, Canada, August 2002.

  9. Bahlmann, C., Haasdonk, B., Burkhardt, H., On-Line Handwriting Recognition with Support Vector Machines - A Kernel Approach. IWFHR-8, Eighth International Workshop on Frontiers in Handwriting Recognition, Ontario, Canada, August 2002. Best Paper Presentation Award.

Demos and Tools

A MATLAB toolbox called KerMet-Tools is available which implements various invariant kernel types and kernel methods. Some simple examples of invariance in kernel functions can be Illustrated in 2D with a corresponding graphical user interface. The incorporated transformations range from discrete to continuous, from linear to highly nonlinear transformations with adjustable parameter ranges. The plots indicate the kernel function k(x0,.), where the first argument x0 is fixed (blue dot). The second argument is taken from a suitable rectangle in RxR, the resulting kernel values are color coded. The lines indicate the parameter range of the transformations. More examples are available on the KerMet-Tools website.


reflexion and partial rotation


linear transformation


nonlinear transformation

This page is maintained by the project responsible.