{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T11:59:52Z","timestamp":1743076792154,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319244853"},{"type":"electronic","value":"9783319244860"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24486-0_12","type":"book-chapter","created":{"date-parts":[[2015,10,3]],"date-time":"2015-10-03T21:20:50Z","timestamp":1443907250000},"page":"179-193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Rademacher Complexity of Weighted Automata"],"prefix":"10.1007","author":[{"given":"Borja","family":"Balle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehryar","family":"Mohri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,31]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Abe, N., Warmuth, M.K.: On the computational complexity of approximating distributions by probabilistic automata. Machine Learning (1992)","DOI":"10.1007\/BF00992677"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Albert, J., Kari, J.: Digital image compression. In: Handbook of weighted automata. Springer (2009)","DOI":"10.1007\/978-3-642-01492-5_11"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Baier, C., Gr\u00f6\u00dfer, M., Ciesinski, F.: Model checking linear-time properties of probabilistic systems. In: Handbook of Weighted automata. Springer (2009)","DOI":"10.1007\/978-3-642-01492-5_13"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Bailly, R., Denis, F., Ralaivola, L.: Grammatical inference as a principal component analysis problem. In: ICML (2009)","DOI":"10.1145\/1553374.1553379"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Bailly, R., Denis, F.: Absolute convergence of rational series is semi-decidable. Inf. Comput. (2011)","DOI":"10.1016\/j.ic.2010.11.004"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Balle, B., Carreras, X., Luque, F., Quattoni, A.: Spectral learning of weighted automata: A forward-backward perspective. Machine Learning (2014)","DOI":"10.1007\/s10994-013-5416-x"},{"key":"12_CR7","unstructured":"Balle, B., Hamilton, W., Pineau, J.: Methods of moments for learning stochastic languages: unified presentation and empirical comparison. In: ICML (2014)"},{"key":"12_CR8","unstructured":"Balle, B., Mohri, M.: Spectral learning of general weighted automata via constrained matrix completion. In: NIPS (2012)"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Balle, B., Mohri, M.: Learning weighted automata. In: CAI (2015)","DOI":"10.1007\/978-3-319-23021-4_1"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Balle, B., Panangaden, P., Precup, D.: A canonical form for weighted automata and applications to approximate minimization. In: Logic in Computer Science (LICS) (2015)","DOI":"10.1109\/LICS.2015.70"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-44581-1_15","volume-title":"Computational Learning Theory","author":"PL Bartlett","year":"2001","unstructured":"Bartlett, P.L., Mendelson, S.: Rademacher and gaussian complexities: risk bounds and structural results. In: Helmbold, D.P., Williamson, B. (eds.) COLT 2001 and EuroCOLT 2001. LNCS (LNAI), vol. 2111, pp. 224\u2013240. Springer, Heidelberg (2001)"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Berstel, J., Reutenauer, C.: Noncommutative rational series with applications. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511760860"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Boots, B., Siddiqi, S., Gordon, G.: Closing the learning-planning loop with predictive state representations. In: RSS (2009)","DOI":"10.15607\/RSS.2010.VI.036"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Carlyle, J.W., Paz, A.: Realizations by stochastic finite automata. J. Comput. Syst. Sci. 5(1) (1971)","DOI":"10.1016\/S0022-0000(71)80005-3"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Cortes, C., Mohri, M., Rastogi, A.: Lp distance and equivalence of probabilistic automata. International Journal of Foundations of Computer Science (2007)","DOI":"10.1142\/S0129054107004966"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Devroye, L., Lugosi, G.: Combinatorial methods in density estimation. Springer (2001)","DOI":"10.1007\/978-1-4613-0125-7"},{"key":"12_CR17","unstructured":"Eilenberg, S.: Automata, Languages and Machines, vol. A. Academic Press (1974)"},{"key":"12_CR18","unstructured":"Fliess, M.: Matrices de Hankel. Journal de Math\u00e9matiques Pures et Appliqu\u00e9es 53 (1974)"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"de Gispert, A., Iglesias, G., Blackwood, G., Banga, E., Byrne, W.: Hierarchical phrase-based translation with weighted finite-state transducers and shallow-n grammars. Computational Linguistics (2010)","DOI":"10.1162\/coli_a_00006"},{"key":"12_CR20","unstructured":"Hamilton, W.L., Fard, M.M., Pineau, J.: Modelling sparse dynamical systems with compressed predictive state representations. In: ICML (2013)"},{"key":"12_CR21","unstructured":"Hsu, D., Kakade, S.M., Zhang, T.: A spectral algorithm for learning hidden Markov models. In: COLT (2009)"},{"key":"12_CR22","doi-asserted-by":"crossref","unstructured":"Ishigami, Y., Tani, S.: Vc-dimensions of finite automata and commutative finite automata with k letters and n states. Discrete Applied Mathematics (1997)","DOI":"10.1016\/S0166-218X(96)00050-9"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Knight, K., May, J.: Applications of weighted automata in natural language processing. In: Handbook of Weighted Automata. Springer (2009)","DOI":"10.1007\/978-3-642-01492-5_14"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Koltchinskii, V., Panchenko, D.: Rademacher processes and bounding the risk of function learning. In: High Dimensional Probability II, pp. 443\u2013459. Birkh\u00e4user (2000)","DOI":"10.1007\/978-1-4612-1358-1_29"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Kuich, W., Salomaa, A.: Semirings, automata, languages. In: EATCS. Monographs on Theoretical Computer Science, vol. 5. Springer-Verlag, Berlin-New York (1986)","DOI":"10.1007\/978-3-642-69959-7_2"},{"key":"12_CR26","unstructured":"Kulesza, A., Jiang, N., Singh, S.: Low-rank spectral learning with weighted loss functions. In: AISTATS (2015)"},{"key":"12_CR27","unstructured":"Kulesza, A., Rao, N.R., Singh, S.: Low-rank spectral learning. In: AISTATS (2014)"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Massart, P.: Some applications of concentration inequalities to statistics. In: Annales de la Facult\u00e9 des Sciences de Toulouse (2000)","DOI":"10.5802\/afst.961"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Mirsky, L.: A trace inequality of John von Neumann. Monatshefte f\u00fcr Mathematik (1975)","DOI":"10.1007\/BF01647331"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Mohri, M.: Weighted automata algorithms. In: Handbook of Weighted Automata. Monographs in Theoretical Computer Science, pp. 213\u2013254. Springer (2009)","DOI":"10.1007\/978-3-642-01492-5_6"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"Mohri, M., Pereira, F.C.N., Riley, M.: Speech recognition with weighted finite-state transducers. In: Handbook on Speech Processing and Speech Comm. Springer (2008)","DOI":"10.1007\/978-3-540-49127-9_28"},{"key":"12_CR32","unstructured":"Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of machine learning. MIT press (2012)"},{"key":"12_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-Theoretic Aspects of Formal Power Series","author":"A Salomaa","year":"1978","unstructured":"Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag, New York (1978)"},{"key":"12_CR34","unstructured":"Tropp, J.A.: An Introduction to Matrix Concentration Inequalities (2015). ArXiv abs\/1501.01571"},{"key":"12_CR35","unstructured":"Vershynin, R.: Lectures in Geometrical Functional Analysis. Preprint (2009)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24486-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,14]],"date-time":"2023-08-14T22:36:54Z","timestamp":1692052614000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24486-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319244853","9783319244860"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24486-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"31 October 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}