Kernel conditional random fields: representation and clique selection

ABSTRACT

Kernel conditional random fields (KCRFs) are introduced as a framework for discriminative modeling of graph-structured data. A representer theorem for conditional graphical models is given which shows how kernel conditional random fields arise from risk minimization procedures defined using Mercer kernels on labeled graphs. A procedure for greedily selecting cliques in the dual representation is then proposed, which allows sparse representations. By incorporating kernels and implicit feature spaces into conditional graphical models, the framework enables semi-supervised learning algorithms for structured data through the use of graph kernels. The framework and clique selection methods are demonstrated in synthetic data experiments, and are also applied to the problem of protein secondary structure prediction.

REFERENCES

• 1: Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003). Hidden Markov support vector machines. ICML'03.
• 2: Belkin, M., & Niyogi, P. (2002). Semi-supervised learning on manifolds (Technical Report TR-2002-12). University of Chicago.
• 3: Chapelle, O., Weston, J., & Schoelkopf, B. (2002). Cluster kernels for semi-supervised learning. NIPS'02.
• 4: Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.1-8, July 06, 2002 [doi>10.3115/1118693.1118694]
• 5: Cuff, J., & Barton, G. (1999). Evaluation and improvement of multiple sequence methods for protein secondary structure prediction. Proteins, 34, 508--519.
• 6: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 7: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 8: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 9: Jones, D. (1999). Protein secondary structure prediction based on position-specific scoring matrices. J Mol Biol., 292, 195--202.
• 10: Kabsch, W., & Sander, C. (1983). Dictionary of protein secondary structure: Pattern recognition of hydrogen-bonded and geometrical features. Biopolymers, 22, 2577--2637.
• 11: Kim, H., & Park, H. (2003). Protein secondary structure prediction based on an improved support vector machines approach. Protein Eng., 16, 553--60.
• 12: Kimeldorf, G., & Wahba, G. (1971). Some results on Tchebychean spline functions. J. Math. Anal. Applic., 33, 82--95.
• 13: Kumar, S., & Hebert, M. (2003). Discriminative fields for modeling spatial dependencies in natural images. NIPS'03.
• 14: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 15: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 16: McCallum, A. (2003). Efficiently inducing features of conditional random fields. UAI'03.
• 17: David Pinto , Andrew McCallum , Xing Wei , W. Bruce Croft, Table extraction using conditional random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860479]
• 18: Fei Sha , Fernando Pereira, Shallow parsing with conditional random fields, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.134-141, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073473]
• 19: Smola, A., & Kondor, R. (2003). Kernels and regularization on graphs. COLT'03.
• 20: Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin Markov networks. NIPS'03.
• 21: Zhu, J., & Hastie, T. (2001). Kernel logistic regression and the import vector machine. NIPS'01.
• 22: Zhu, X., Gharahmani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. ICML'03.