Article

CarpeDiem: an algorithm for the fast evaluation of SSL classifiers

Authors:

Roberto Esposito,

Daniele P. RadicioniAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 257 - 264

https://doi.org/10.1145/1273496.1273529

Published: 20 June 2007 Publication History

Get Access

Abstract

In this paper we present a novel algorithm, CarpeDiem. It significantly improves on the time complexity of Viterbi algorithm, preserving the optimality of the result. This fact has consequences on Machine Learning systems that use Viterbi algorithm during learning or classification. We show how the algorithm applies to the Supervised Sequential Learning task and, in particular, to the HMPerceptron algorithm. We illustrate CarpeDiem in full details, and provide experimental results that support the proposed approach.

References

[1]

Austin, S., Peterson, P., Placeway, P., Schwartz, R., & Vandergrift, J. (1990). Toward a Real-Time Spoken Language System Using Commercial Hardware. DARPA Speech and Natural Language Workshop (pp. 72--77).

Digital Library

Google Scholar

[2]

Collins, M. (2002). Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. Proc. of the Conf. on Empirical Methods in Natural Language Processing.

Digital Library

Google Scholar

[3]

Cormen, T. H., Leiserson, C., & Rivest, R. L. (1990). Introduction to Algorithms. Cambridge, MASS: MIT Press.

Digital Library

Google Scholar

[4]

Dietterich, T. (2002). Machine Learning for Sequential Data: A Review. Structural, Syntactic, and Statistical Pattern Recognition (pp. 15--30). Springer-Verlag.

Digital Library

Google Scholar

[5]

Fano, R. M. (1963). A heuristic discussion of probabilistic decoding. IEEE T. Inform. Theory, 9, 64--73.

Digital Library

Google Scholar

[6]

Felzenszwalb, P. F., Huttenlocher, D. P., & Kleinberg, J. M. (2003). Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis. Advances in Neural Information Processing System.

Google Scholar

[7]

Lafferty, J., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proc. of the Eighteenth International Conference on Machine Learning (pp. 282--289). San Francisco, CA: Morgan Kaufmann.

Digital Library

Google Scholar

[8]

McCallum, A., Freitag, D., & Pereira, F. (2000). Maximum entropy Markov models for information extraction and segmentation. Proc. 17th International Conf. on Machine Learning (pp. 591--598). Morgan Kaufmann, San Francisco, CA.

Digital Library

Google Scholar

[9]

Pardo, B., & Birmingham, W. P. (2002). Algorithms for Chordal Analysis. Comput. Music J., 26, 27--49.

Digital Library

Google Scholar

[10]

Rabiner, L. R. (1989). A tutorial on hidden markov models and selected applications in speech recognition. Proc. of the IEEE, 77, 267--296

Digital Library

Google Scholar

[11]

Radicioni, D. P., & Esposito, R. (2006). A Conditional Model for Tonal Analysis. Foundations of Intelligent Systems (pp. 652--661). Berlin: Springer-Verlag.

Digital Library

Google Scholar

[12]

Siddiqi, S. M., & Moore, A. W. (2005). Fast Inference and Learning in Large-State-Space HMMs. Proc. of the 22nd International Conf. on Machine Learning.

Digital Library

Google Scholar

[13]

Viterbi, A. J. (1967). Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. IEEE T. Inform. Theory (pp. 260--269).

Google Scholar

Cited By

View all

Radicioni DEsposito R(2010)BREVE: An HMPerceptron-Based Chord Recognition SystemAdvances in Music Information Retrieval10.1007/978-3-642-11674-2_7(143-164)Online publication date: 2010
https://doi.org/10.1007/978-3-642-11674-2_7
Fujiwara YSakurai YKitsuregawa M(2009)Fast likelihood search for hidden Markov modelsACM Transactions on Knowledge Discovery from Data10.1145/1631162.16311663:4(1-37)Online publication date: 4-Dec-2009
https://dl.acm.org/doi/10.1145/1631162.1631166
Esposito RRadicioni D(2009)Empirical Assessment of Two Strategies for Optimizing the Viterbi AlgorithmProceedings of the XIth International Conference of the Italian Association for Artificial Intelligence Reggio Emilia on Emergent Perspectives in Artificial Intelligence10.1007/978-3-642-10291-2_15(141-150)Online publication date: 17-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-10291-2_15
Show More Cited By

CarpeDiem: an algorithm for the fast evaluation of SSL classifiers
1. Computing methodologies

Recommendations

CarpeDiem: Optimizing the Viterbi Algorithm and Applications to Supervised Sequential Learning

The growth of information available to learning systems and the increasing complexity of learning tasks determine the need for devising algorithms that scale well with respect to all learning parameters. In the context of supervised sequential learning, ...
A low complexity detection/decoding algorithm for NB-LDPC coded PRCPM system

This paper studies the combination of non-binary low-density parity-check (NB-LDPC) codes and M -ary partial response continuous phase modulation (PRCPM). A low-complexity joint detection/decoding algorithm is proposed, which is referred to as the Max-...
Reduced complexity decoding algorithms for low-density parity check codes and turbo codes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Radicioni DEsposito R(2010)BREVE: An HMPerceptron-Based Chord Recognition SystemAdvances in Music Information Retrieval10.1007/978-3-642-11674-2_7(143-164)Online publication date: 2010
https://doi.org/10.1007/978-3-642-11674-2_7
Fujiwara YSakurai YKitsuregawa M(2009)Fast likelihood search for hidden Markov modelsACM Transactions on Knowledge Discovery from Data10.1145/1631162.16311663:4(1-37)Online publication date: 4-Dec-2009
https://dl.acm.org/doi/10.1145/1631162.1631166
Esposito RRadicioni D(2009)Empirical Assessment of Two Strategies for Optimizing the Viterbi AlgorithmProceedings of the XIth International Conference of the Italian Association for Artificial Intelligence Reggio Emilia on Emergent Perspectives in Artificial Intelligence10.1007/978-3-642-10291-2_15(141-150)Online publication date: 17-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-10291-2_15
Fujiwara YSakurai YYamamuro MLi YLiu BSarawagi S(2008)SPIRALProceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/1401890.1401924(247-255)Online publication date: 24-Aug-2008
https://dl.acm.org/doi/10.1145/1401890.1401924
Radicioni DEsposito R(2007)Tonal Harmony AnalysisProceedings of the 10th Congress of the Italian Association for Artificial Intelligence on AI*IA 2007: Artificial Intelligence and Human-Oriented Computing10.1007/978-3-540-74782-6_55(638-649)Online publication date: 10-Sep-2007
https://dl.acm.org/doi/10.1007/978-3-540-74782-6_55
Esposito RRadicioni D(2007)Trip Around the HMPerceptron AlgorithmProceedings of the 10th Congress of the Italian Association for Artificial Intelligence on AI*IA 2007: Artificial Intelligence and Human-Oriented Computing10.1007/978-3-540-74782-6_22(242-253)Online publication date: 10-Sep-2007
https://dl.acm.org/doi/10.1007/978-3-540-74782-6_22

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

CarpeDiem: Optimizing the Viterbi Algorithm and Applications to Supervised Sequential Learning

A low complexity detection/decoding algorithm for NB-LDPC coded PRCPM system

Reduced complexity decoding algorithms for low-density parity check codes and turbo codes