A survey of kernels for structured data
Tóm tắt
Kernel methods in general and support vector machines in particular have been successful in various learning tasks on data represented in a single table. Much 'real-world' data, however, is structured - it has no natural representation in a single table. Usually, to apply kernel methods to 'real-world' data, extensive pre-processing is performed to embed the data into areal vector space and thus in a single table. This survey describes several approaches of defining positive definite kernels on structured instances directly.
Từ khóa
Tài liệu tham khảo
N. Aronszajn . Theory of reproducing kernels . Transactions of the American Mathematical Society , 68 , 1950 .]] N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68, 1950.]]
M. Collins and N. Duffy . Convolution kernels for natural language . In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems , volume 14 . MIT Press , 2002 .]] M. Collins and N. Duffy. Convolution kernels for natural language. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2002.]]
T. Gärtner . Exponential and geometric kernels for graphs . In NIPS Workshop on Unreal Data: Principles of Modeling Nonvectorial Data , 2002 .]] T. Gärtner. Exponential and geometric kernels for graphs. In NIPS Workshop on Unreal Data: Principles of Modeling Nonvectorial Data, 2002.]]
T. Gärtner , P. A. Flach , A. Kowalczyk , and A. J. Smola . Multi-instance kernels. In C. Sammut and A. Hoffmann, editors , Proceedings of the 19th International Conference on Machine Learning , pages 179 -- 186 . Morgan Kaufmann , June 2002 .]] T. Gärtner, P. A. Flach, A. Kowalczyk, and A. J. Smola. Multi-instance kernels. In C. Sammut and A. Hoffmann, editors, Proceedings of the 19th International Conference on Machine Learning, pages 179--186. Morgan Kaufmann, June 2002.]]
D. Haussler . Convolution kernels on discrete structures. Technical report , Department of Computer Science , University of California at Santa Cruz , 1999 .]] D. Haussler. Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California at Santa Cruz, 1999.]]
T. Jaakkola and D. Haussler . Exploiting generative models in discriminative classifiers . In Advances in Neural Information Processing Systems , volume 10 , 1999 .]] T. Jaakkola and D. Haussler. Exploiting generative models in discriminative classifiers. In Advances in Neural Information Processing Systems, volume 10, 1999.]]
T. Jaakkola and D. Haussler . Probabilistic kernel regression models . In Proceedings of the 1999 Conference on AI and Statistics , 1999 .]] T. Jaakkola and D. Haussler. Probabilistic kernel regression models. In Proceedings of the 1999 Conference on AI and Statistics, 1999.]]
H. Kashima and A. Inokuchi . Kernels for graph classification . In ICDM Workshop on Active Mining , 2002 .]] H. Kashima and A. Inokuchi. Kernels for graph classification. In ICDM Workshop on Active Mining, 2002.]]
H. Kashima and T. Koyanagi . Kernels for semistructured data. In C. Sammut and A. Hoffmann, editors , Proceedings of the 19th International Conference on Machine Learning. Morgan Kaufmann , 2002 .]] H. Kashima and T. Koyanagi. Kernels for semistructured data. In C. Sammut and A. Hoffmann, editors, Proceedings of the 19th International Conference on Machine Learning. Morgan Kaufmann, 2002.]]
H. Kashima , K. Tsuda , and A. Inokuchi . Marginalized kernels between labeled graphs . In Proceedings of the 20th International Conference on Machine Learning , 2003 .]] H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th International Conference on Machine Learning, 2003.]]
R. I. Kondor and J. Lafferty . Diffusion kernels on graphs and other discrete input spaces. In C. Sammut and A. Hoffmann, editors , Proceedings of the 19th International Conference on Machine Learning , pages 315 -- 322 . Morgan Kaufmann , 2002 .]] R. I. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In C. Sammut and A. Hoffmann, editors, Proceedings of the 19th International Conference on Machine Learning, pages 315--322. Morgan Kaufmann, 2002.]]
S. Kramer N. Lavrač and P. A. Flach. Propositionalization approaches to relational data mining. In Džeroski and Lavrač {8} chapter 11.]] S. Kramer N. Lavrač and P. A. Flach. Propositionalization approaches to relational data mining. In Džeroski and Lavrač {8} chapter 11.]]
C. Leslie , E. Eskin , and W. Noble . The spectrum kernel: A string kernel for svm protein classification . In Proceedings of the Pacific Symposium on Biocomputing , pages 564 -- 575 , 2002 .]] C. Leslie, E. Eskin, andW. Noble. The spectrum kernel: A string kernel for svm protein classification. In Proceedings of the Pacific Symposium on Biocomputing, pages 564--575, 2002.]]
C. Leslie , E. Eskin , J. Weston , and W. Noble . Mismatch string kernels for svm protein classification . In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems , volume 15 . MIT Press , 2003 .]] C. Leslie, E. Eskin, J. Weston, and W. Noble. Mismatch string kernels for svm protein classification. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems, volume 15. MIT Press, 2003.]]
J. W. Lloyd . Logic for Learning . Springer-Verlag , 2002 .]] J. W. Lloyd. Logic for Learning. Springer-Verlag, 2002.]]
H. Lodhi , J. Shawe-Taylor , N. Christianini , and C. Watkins . Text classification using string kernels . In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems , volume 13 . MIT Press , 2001 .]] H. Lodhi, J. Shawe-Taylor, N. Christianini, and C. Watkins. Text classification using string kernels. In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2001.]]
P. Pavlidis , T. Furey , M. Liberto , D. Haussler , and W. Grundy . Promoter region-based classification of genes . In Proceedings of the Pacific Symposium on Biocomputing , pages 151 -- 163 , 2001 .]] P. Pavlidis, T. Furey, M. Liberto, D. Haussler, and W. Grundy. Promoter region-based classification of genes. In Proceedings of the Pacific Symposium on Biocomputing, pages 151--163, 2001.]]
C. Saunders , J. Shawe-Taylor , and A. Vinokourov . String kernels, fisher kernels and finite state automata . In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems , volume 15 . MIT Press , 2003 .]] C. Saunders, J. Shawe-Taylor, and A. Vinokourov. String kernels, fisher kernels and finite state automata. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems, volume 15. MIT Press, 2003.]]
B. Schölkopf and A. J. Smola . Learning with Kernels . MIT Press , 2002 .]] B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, 2002.]]
N. Smith and M. Gales . Speech recognition using SVMs . In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems , volume 14 . MIT Press , 2002 .]] N. Smith and M. Gales. Speech recognition using SVMs. In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2002.]]
K. Tsuda , M. Kawanabe , G. Rätsch , S. Sonnenburg , and K.-R. Müller . A new discriminative kernel from probabilistic models . In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems , volume 14 . MIT Press , 2002 .]] K. Tsuda, M. Kawanabe, G. Rätsch, S. Sonnenburg, and K.-R. Müller. A new discriminative kernel from probabilistic models. In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2002.]]
K. Tsuda , T. Kin , and K. Asai . Marginalized kernels for biological sequences . Bioinformatics , 2002 .]] K. Tsuda, T. Kin, and K. Asai. Marginalized kernels for biological sequences. Bioinformatics, 2002.]]
J.-P. Vert . A tree kernel to analyze phylogenetic profiles . Bioinformatics , 2002 .]] J.-P. Vert. A tree kernel to analyze phylogenetic profiles. Bioinformatics, 2002.]]
J.-P. Vert and M. Kanehisa . Graph driven features extraction from microarray data using diffusion kernels and kernel cca . In S. Becker, S. Thrun, and K. Ober mayer , editors, Advances in Neural Information Processing Systems, volume 15 . MIT Press , 2003 .]] J.-P. Vert and M. Kanehisa. Graph driven features extraction from microarray data using diffusion kernels and kernel cca. In S. Becker, S. Thrun, and K. Ober mayer, editors, Advances in Neural Information Processing Systems, volume 15. MIT Press, 2003.]]
S. Vishwanathan and A. Smola . Fast kernels for string and tree matching . In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems , volume 15 . MIT Press , 2003 .]] S. Vishwanathan and A. Smola. Fast kernels for string and tree matching. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems, volume 15. MIT Press, 2003.]]
C. Watkins . Dynamic alignment kernels. Technical report , Department of Computer Science, Royal Holloway , University of London , 1999 .]] C. Watkins. Dynamic alignment kernels. Technical report, Department of Computer Science, Royal Holloway, University of London, 1999.]]
C. Watkins . Kernels from matching operations. Technical report , Department of Computer Science, Royal Holloway , University of London , 1999 .]] C. Watkins. Kernels from matching operations. Technical report, Department of Computer Science, Royal Holloway, University of London, 1999.]]