Graph kernels between point clouds

ABSTRACT

Point clouds are sets of points in two or three dimensions. Most kernel methods for learning on sets of points have not yet dealt with the specific geometrical invariances and practical constraints associated with point clouds in computer vision and graphics. In this paper, we present extensions of graph kernels for point clouds, which allow one to use kernel methods for such objects as shapes, line drawings, or any three-dimensional point clouds. In order to design rich and numerically efficient kernels with as few free parameters as possible, we use kernels between covariance matrices and their factorizations on probabilistic graphical models. We derive polynomial time dynamic programming recursions and present applications to recognition of handwritten digits and Chinese characters from few training examples.

REFERENCES

• 1: Francis R. Bach , Gert R. G. Lanckriet , Michael I. Jordan, Multiple kernel learning, conic duality, and the SMO algorithm, Proceedings of the twenty-first international conference on Machine learning, p.6, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015424]
• 2: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 3: Karsten M. Borgwardt , Cheng Soon Ong , Stefan Schönauer , S. V. N. Vishwanathan , Alex J. Smola , Hans-Peter Kriegel, Protein function prediction via graph kernels, Bioinformatics, v.21 n.1, p.47-56, January 2005 [doi>10.1093/bioinformatics/bti1007]
• 4: Tiberio S. Caetano , Terry Caelli , Dale Schuurmans , Dante A. C. Barone, Graphical Models and Point Pattern Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.10, p.1646-1663, October 2006 [doi>10.1109/TPAMI.2006.207]
• 5: Olivier Chapelle , Bernhard Schölkopf , Alexander Zien, Semi-Supervised Learning (Adaptive Computation and Machine Learning), The MIT Press, 2006
• 6: Diestel, R. (2005). Graph theory. Springer-Verlag.
• 7: David A. Forsyth , Jean Ponce, Computer Vision: A Modern Approach, Prentice Hall Professional Technical Reference, 2002
• 8: Holger Fröhlich , Jörg K. Wegner , Florian Sieker , Andreas Zell, Optimal assignment kernels for attributed molecular graphs, Proceedings of the 22nd international conference on Machine learning, p.225-232, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102380]
• 9: Kristen Grauman , Trevor Darrell, The Pyramid Match Kernel: Efficient Learning with Sets of Features, The Journal of Machine Learning Research, 8, p.725-760, 5/1/2007
• 10: Harchaoui, Z., & Bach, F. (2007). Image classification with segmentation graph kernels. Proc. CVPR.
• 11: Kashima, H., Tsuda, K., & Inokuchi, A. (2004). Kernels for graphs. Kernel Methods in Comp. Biology. MIT Press.
• 12: Kondor, R. I., & Jebara, T. (2003). A kernel between sets of vectors. Proc. ICML.
• 13: Lauritzen, S. (1996). Graphical models. Oxford U. Press.
• 14: LeCun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based learning applied to document recognition. Proc. IEEE, 86, 2278--2324.
• 15: Huma Lodhi , Craig Saunders , John Shawe-Taylor , Nello Cristianini , Chris Watkins, Text classification using string kernels, The Journal of Machine Learning Research, 2, p.419-444, 3/1/2002 [doi>10.1162/153244302760200687]
• 16: Mahé, P., & Vert, J.-P. (2006). Graph kernels based on tree patterns for molecules (Tech. report HAL-00095488).
• 17: Michel Neuhaus , Horst Bunke, Edit distance-based kernel functions for structural pattern classification, Pattern Recognition, v.39 n.10, p.1852-1863, October, 2006 [doi>10.1016/j.patcog.2006.04.012]
• 18: Parsana, M., Bhattacharyya, C., Bhattacharya, S., & Ramakrishnan, K. R. (2008). Kernels on attributed pointsets with applications. Adv. NIPS.
• 19: Jian Qiu , Martial Hue , Asa Ben-Hur , Jean-Philippe Vert , William Stafford Noble, A structural alignment kernel for protein structures, Bioinformatics, v.23 n.9, p.1090-1098, March 2007 [doi>10.1093/bioinformatics/btl642]
• 20: Ramon, J., & Gäärtner, T. (2003). Expressivity versus efficiency of graph kernels. First International Workshop on Mining Graphs, Trees and Sequences.
• 21: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 22: Srihari, S. N., Yang, X., & Ball, G. R. (2007). Offline Chinese handwriting recognition: A survey. Frontiers of Computer Science in China.
• 23: Vert, J.-P. (2008). The optimal assignment kernel is not positive definite (Tech. report HAL-00218278).
• 24: Vert, J.-P., Saigo, H., & Akutsu, T. (2004). Local alignment kernels for biological sequences. Kernel Methods in Comp. Biology. MIT Press.
• 25: Vishwanathan, S. V. N., Borgwardt, K. M., & Schraudolph, N. (2007). Fast computation of graph kernels. Adv. NIPS.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Design, Theory