Group theoretical methods in machine learning

1. 1. A philosophical introduction to groups and representations. [intro.pdf]
2. Groups as systems of transformations. Group axioms. Classes of groups: finite, countable, and Lie.
3. Representations: equivalence and reducibility. Harmonic analysis: commutative and non-commutative.
4. Structure: isomorphism, homomorphism, normal subgroups. Direct product and semi-direct product. Classification of groups.
5. Groups in the real world: quantum mechanics, robotics, permutations.
6. The three key themes: non-commutativity, representations, group actions.  
2. 2. Harmonic analysis on the symmetric group. [symmetric.pdf]
3. Permutations. Cycle notation and cycle type. Partial rankings. Subgroups and normal subgroups.
4. Harmonic analysis: commutative and non-commutative. Unitarity, convolution theorem and Plancherel’s theorem. Decomposition of the group algebra: isotypal components.
5. Young diagrams, Young tableaux and representations. Young’s orthogonal representation.
6. Application: spectral analysis of ranking data.
7. Fast Fourier transforms. The Cooley-Tukey algorithm and its interpretation in terms of subgroups.  Clausen’s FFT for S_n. The SnOB software library.
8. Application: multi-object tracking.
9. Extension: wreath product groups.
3. 3. Lie groups and invariance. [invariants.pdf]
4. Definition of Lie groups. Generators, the exponential map and Lie algebra. Examples.
5. The rotation groups: parametrization and representations. Connection to spherical harmonics. Homogeneous spaces.  
6. The Euclidean motion groups.
7. Application: fast pattern matching.
8. The classical spectrum and bispectrum and their generalization to non-commutative groups.  Kakarala’s completeness results.
9. Application: rotation and translation invariant features in image processing.

Risi Kondor (Columbia University)

Preliminary list of topics:

Tutorial at ICML 2007, June 20

The use of algebraic methods -- specifically group theory, representation theory, and even some concepts from algebraic geometry -- is an emerging new direction in machine learning. The purpose of this tutorial is to give an entertaining but informative introduction to the background to these developments and sketch some of the many possible applications. The tutorial is intended to be palatable by a non-specialist audience with no prior background in abstract algebra.

References:

1.   Chirikjian, G. S., Kyatkin, A. B.: Engineering applications of noncommutative harmonic analysis. CRC Press, 2001.
2.   Clausen, M.: Fast generalized Fourier transforms. Theor. Comput. Sci., pages 55-63, 1989
3.   Cuturi, M.: Permanents, transportation polytopes and positive definite kernels on histograms. IJCAI, 2007.
4.   Diaconis, P.: Group Representation in Probability and Statistics. Volume 11 of IMS Lecture Series. Institute of Mathematical Statistics, 1988.
5.   Kanatani, K.: Group theoretical methods in image understanding. Springer-Verlag, 1990.
6.   Kondor, R.: A complete set of rotationally and translationally invariant features for images. [pdf]
7.   Kondor, R., Howard, A., Jebara, T.: Multi-object tracking with representations of the symmetric group [pdf].
8.   Lenz, R.: Group theoretical methods in image processing. Springer-Verlag, 1990.
9.   Maslen, D and Rockmore D.: Generalized FFTs: a survey of some recent results. In Groups and Computation II, volume 28 of DIMACS Series in Discrete Mathematics, 1997.