Abstract
We propose a family of kernels based on the Binet-Cauchy theorem, and its extension to Fredholm operators. Our derivation provides a unifying framework for all kernels on dynamical systems currently used in machine learning, including kernels derived from the behavioral framework, diffusion processes, marginalized kernels, kernels on graphs, and the kernels on sets arising from the subspace angle approach. In the case of linear time-invariant systems, we derive explicit formulae for computing the proposed Binet-Cauchy kernels by solving Sylvester equations, and relate the proposed kernels to existing kernels based on cepstrum coefficients and subspace angles. We show efficient methods for computing our kernels which make them viable for the practitioner.
Besides their theoretical appeal, these kernels can be used efficiently in the comparison of video sequences of dynamic scenes that can be modeled as the output of a linear time-invariant dynamical system. One advantage of our kernels is that they take the initial conditions of the dynamical systems into account. As a first example, we use our kernels to compare video sequences of dynamic textures. As a second example, we apply our kernels to the problem of clustering short clips of a movie. Experimental evidence shows superior performance of our kernels.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aggarwal, G., Roy-Chowdhury, A., and Chellappa, R. 2004. A system identification approach for video-based face recognition. In Proc. Intl. Conf. Pattern Recognition, Cambridge, UK.
Aitken, A.C. 1946. Determinants and Matrices, 4th edition. Interscience Publishers.
Bach, F.R. and Jordan, M.I. 2002. Kernel independent component analysis. Journal of Machine Learning Research, 3:1–48.
Bakir, G., Weston, J., and Schölkopf, B. 2003. Learning to find pre-images. In Advances in Neural Information Processing Systems 16. MIT Press.
Barla, A., Odone, F., and Verri, A. 2002. Hausdorff kernel for 3D object acquisition and detection. In European Conference on Computer Vision ’02, number 2353 in LNCS, pp. 20. Springer.
Baxter, J. and Bartlett, P.L. 1999. Direct gradient-based reinforcement learning: Gradient estimation algorithms. Technical report, Research School of Information, ANU Canberra.
Bernstein D.S. 2005. Matrix Mathematics. Princeton University Press.
Blanz, V., Schölkopf, B., Bülthoff H., Burges, C., Vapnik, V., and Vetter, T. 1996. Comparison of view-based object recognition algorithms using realistic 3D models. In C. von der Malsburg, W. von Seelen, J.C. Vorbrüggen, and B. Sendhoff (eds.), Artificial Neural Networks ICANN’96, vol. 1112 of Lecture Notes in Computer Science, pp. 251–256. Berlin: Springer-Verlag.
Burges, C.J.C. and Vapnik, V. 1995. A new method for constructing artificial neural networks. Interim technical report, ONR contract N00014-94-c-0186, AT&T Bell Laboratories.
Burkhardt, H. 2004. Invariants on skeletons and polyhedrals. Technical report, Universität Freiburg, in preparation.
Chang, C.C. and Lin, C.J. 2001. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
Chapelle, O., Haffner, P., and Vapnik, V. 1999. SVMs for histogram-based image classification. IEEE Transactions on Neural Networks, 10(5).
De Cock, K. and De Moor, B. 2002. Subspace angles between ARMA models. Systems and Control Letter, 46:265–270.
Cortes, C., Haffner, P., and Mohri, M. 2002. Rational kernels. In Advances in Neural Information Processing Systems 15, vols. 14. Cambridge, MA: MIT Press.
Cristianini, N. and Shawe-Taylor, J. 2000. An Introduction to Support Vector Machines. Cambridge University Press, Cambridge, UK.
de Finetti, B. 1990. Theory of probability, vol. 1–2. John Wiley and Sons, 1990. reprint of the 1975 translation.
Doretto, G., Chiuso, A., Wu, Y.N., and Soatto, S. 2003. Dynamic textures. International Journal of Computer Vision, 51(2):91–109.
Gardiner, J.D., Laub, A.L., Amato, J.J., and Moler, C.B. 1992. Solution of the Sylvester matrix equation AXB ⊤ + CXD ⊤ = E. ACM Transactions on Mathematical Software, 18(2):223– 231.
Gärtner, T., Flach, P.A., and Wrobel, S. 2003. On graph kernels: Hardness results and efficient alternatives. In B. Schölkopf and M.K. Warmuth, (eds.) Sixteenth Annual Conference on Computational Learning Theory and Seventh Kernel Workshop, COLT. Springer.
Golub, G.H. and Van Loan, C.F. 1996. Matrix Computations, 3rd edition. Baltimore, MD: John Hopkins University Press.
Gretton, A., Herbrich, R., and Smola, A.J. 2003. The kernel mutual information. In Proceedings of ICASSP.
Gröbner, W. 1965. Matrizenrechnung. BI Hochschultaschenbücher.
Heisele, B., Ho, P., and Poggio, T. 2001. Face recognition with support vector machines: Global versus component-based approach. In Proceedings of the Eighth International Conference On Computer Vision (ICCV-01), pp. 688–694. Los Alamitos, CA: IEEE Computer Society.
Herbrich, R. 2002. Learning Kernel Classifiers: Theory and Algorithms. MIT Press.
Isidori, A. 1989. Nonlinear Control Systems. 2nd edition. Springer.
Joachims, T. 1998. Text categorization with support vector machines: Learning with many relevant features. In Proceedings of the European Conference on Machine Learning, pp. 137–142. Berlin: Springer.
Kashima, H., Tsuda, K., and Inokuchi, A. 2003. Marginalized kernels between labeled graphs. In Proceedings of the 20th International Conference on Machine Learning (ICML), Washington, DC, United States.
Kashima, H., Tsuda, K., and Inokuchi, A. 2004. Kernels on graphs. In K. Tsuda, B. Schölkopf, and J.P. Vert (Eds.), Kernels and Bioinformatics, Cambridge, MA: MIT Press.
Kondor, I.R. and Lafferty, J.D. 2002. Diffusion kernels on graphs and other discrete structures. In Proceedings of the ICML.
Luenberger, D.G. 1979. Introduction to Dynamic Systems: Theory, Models, and Applications. New York, USA:John Wiley and Sons, Inc., ISBN 0–471 - 02594 - 1.
Martin, R.J. 2000. A metric for ARMA processes. IEEE Transactions on Signal Processing, 48(4):1164–1170.
Nocedal, J. and Wright, S.J. 1999. Numerical Optimization. Springer Series in Operations Research. Springer.
Pinkus, A. 1996. Spectral properties of totally positive kernels and matrices. In M. Gasca and C.A. Miccheli (eds.), Total Positivity and its Applications, vol. 359 of Mathematics and its Applications, pp. 1–35. Kluwer.
Platt, J. 1999. Fast training of support vector machines using sequential minimal optimization. In B. Schölkopf, C.J.C. Burges, and A.J. Smola (eds.), Advances in Kernel Methods—Support Vector Learning, pp. 185–208, Cambridge, MA: MIT Press.
Ralaivola, L. and d’Alché Buc, F. 2003. Dynamical modeling with kernels for nonlinear time series prediction. In Se. Thrun, La. Saul, and Be. Schölkopf, (eds.) Advances in Neural Information Processing Systems 16. MIT Press.
Roweis, S. and Saul, L.K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326.
Saisan, P., Doretto, G., Wu, Y.N., and Soatto, S. 2001. Dynamic texture recognition. In Proceedings of CVPR, vol. 2, pp. 58–63.
Schölkopf, B. 1997. Support Vector Learning. R. Oldenbourg Verlag, Munich, Download: http://www.kernel-machines.org.
Schölkopf, B. and Smola, A. 2002. Learning with Kernels. Cambridge, MA: MIT Press.
Shashua, A., and Hazan, T. 2005. Algebraic set kernels with applications to inference over local image representations. In L.K. Saul, Y. Weiss, and L. Bottou (eds.), Advances in Neural Information Processing Systems 17, pp. 1257–1264, Cambridge, MA: MIT Press.
Shi, J. and Malik, J. 1997. Normalized cuts and image segmentation. IEEE Conf. Computer Vision and Pattern Recognition.
Smola, A.J. and Kondor, I.R. 2003. Kernels and regularization on graphs. In B. Schölkopf and M.K. Warmuth (eds.), Proceedings of the Annual Conference on Computational Learning Theory, Lecture Notes in Computer Science, pp. 144–158. Springer.
Smola, A.J. and Vishwanathan, S.V.N. 2003. Hilbert space embeddings in dynamical systems. In Proceedings of the 13th IFAC symposium on system identification. Rotterdam, Netherlands.
Soatto, S. Doretto, G., and Wu: Y.N. 2001. Dynamic textures. In Proceedings of the Eighth International Conference On Computer Vision (ICCV-01), pp. 439–446. Los Alamitos, CA: IEEE Computer Society.
Sutton, R.S. and Barto, A.G. 1998. Reinforcement Learning: An Introduction. MIT Press.
Vapnik, V. 1995. The Nature of Statistical Learning Theory. New York: Springer .
Vapnik, V. 1998. Statistical Learning Theory. New York: John Wiley and Sons.
Vidal, R., Ma, Y., and Sastry, S. 2005. Generalized Principal Component Analysis (GPCA). IEEE Transactions on Pattern Analysis and Machine Intelligence, In press.
Vishwanathan, S.V.N. 2002. Kernel Methods: Fast Algorithms and Real Life Applications. PhD thesis, Indian Institute of Science, Bangalore, India.
Vishwanathan, S.V.N., Borgwardt, K., and Schraudolph, Nicol N. 2006. Faster graph kernels. In International Conference on Machine Learning, submitted.
Vishwanathan, S.V.N., Smola, A.J., and Murty, M.N. 2003. SimpleSVM. In T. Fawcett and N. Mishra (eds.), Proceedings of the 20th International Conference on Machine Learning (ICML), Washington DC, AAAI press.
Willems, J.C. 1986b. From time series to linear system. I. Finite-dimensional linear time invariant systems. Automatica J. IFAC, 22(5):561–580.
Willems, J.C. 1986a. From time series to linear system. II. Exact modelling. Automatica J. IFAC, 22(6):675–694.
Willems, J.C. 1987. From time series to linear system. III. Approximate modelling. Automatica J. IFAC, 23(1):87– 115.
Wolf, L. and Shashua, A. 2003. Learning over sets using kernel principal angles. Jounal of Machine Learning Research, 4:913–931.
Author information
Authors and Affiliations
Corresponding author
Additional information
Parts of this paper were presented at SYSID 2003 and NIPS 2004.
Rights and permissions
About this article
Cite this article
Vishwanathan, S.V.N., Smola, A.J. & Vidal, R. Binet-Cauchy Kernels on Dynamical Systems and its Application to the Analysis of Dynamic Scenes. Int J Comput Vision 73, 95–119 (2007). https://doi.org/10.1007/s11263-006-9352-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-006-9352-0