Transformation knowledge in pattern analysis with kernel methods - distance and integration kernels

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 (SVM) for classification or regression tasks. Further examples are kernel principal component analysis for feature extraction or other linear classifiers like the kernel perceptron. The fundamental ingredient in these methods is the choice of a kernel function, which computes a similarity measure between two input objects. For good generalization abilities of a learning algorithm it is indispensable to incorporate problem-specific a-priori knowledge into the learning process. The kernel function is an important element for this. <br> <br>This thesis focusses on a certain kind of a-priori knowledge namely transformation knowledge. This comprises explicit knowledge of pattern variations that do not or only slightly change the pattern's inherent meaning e.g. rigid movements of 2D/3D objects or transformations like slight stretching, shifting, rotation of characters in optical character recognition etc. Several methods for incorporating such knowledge in kernel functions are presented and investigated: <br> <br> (1) Invariant distance substitution kernels (IDS-kernels): In many practical questions the transformations are implicitly captured by sophisticated distance measures between objects. Examples are nonlinear deformation models between images. Here an explicit parameterization would require an arbitrary number of parameters. Such distances can be incorporated in distance- and inner-product-based kernels. <br> <br> (2) Tangent distance kernels (TD-kernels): Specific instances of IDS-kernels are investigated in more detail as these can be efficiently computed. We assume differentiable transformations of the patterns. Given such knowledge, one can construct linear approximations of the transformation manifolds and use these efficiently for kernel construction by suitable distance functions. <br> <br> (3) Transformation integration kernels (TI-kernels): The technique of integration over transformation groups for feature extraction can be extended to kernel functions and more general group, non-group, discrete or continuous transformations in a suitable way. <br> <br>Theoretically, these approaches differ in the way the transformations are represented and in the adjustability of the transformation extent. More fundamentally, kernels from category 3 turn out to be positive definite, kernels of types 1 and 2 are not positive definite, which is generally required for being usable in kernel methods. This is the motivation to investigate the theoretical meaning of such indefinite kernels. The finding is that on given data these kernels correspond to inner products in pseudo-Euclidean spaces. Here certain kernel methods, in particular SVMs, have a reasonable geometrical and theoretical interpretation. <br> <br>Practical applicability of the kernels is demonstrated in addition to the theoretical properties. For these experiments, support vector classification on various types of data has been performed. The datasets comprise standard benchmark datasets for optical character recognition like USPS and MNIST or real-world biological data resulting from micro-Raman-spectroscopy with the goal of bacteria identification. <br> <br>In addition to the demonstration that transformation knowledge can be involved in kernel functions in different ways and that these can be practically applied, there are more fundamental findings and perspectives. We demonstrate and theoretically argue that indefinite kernels can be used or tolerated by kernel methods, as exemplified for the SVM. There exist statements about the training-algorithm, the resulting solutions and a reasonable geometric interpretation. This opens up mainly two directions. Firstly, these insights facilitate the process of kernel design, which hitherto is mainly restricted to positive definite functions. In particular, this enables SVMs to be used widely in other fields like distance-based learning, i.e. in all analysis problems, where dissimilarities between objects are available. Secondly, the investigation of suitability or robustness of other kernel methods than SVMs with respect to indefinite kernels seems very promising.

Author dc:creator

• Haasdonk, Bernard

Contributors dc:contributor

• Burkhardt, Hans

• Distanzbasierte Kerne
• Haar-Integration
• Optische Zeichenenkennung
• Bakterienerkennung
• distance-based kernels
• optical character recognition
• bacteria recognition

Repository record source_url

https://freidok.uni-freiburg.de/data/2376

OAI identifier oai:identifier

oai:freidok.uni-freiburg.de:2376