{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T05:50:39Z","timestamp":1718862639257},"reference-count":21,"publisher":"Walter de Gruyter GmbH","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We propose a new algorithm for spectral learning of Hidden Markov Models (HMM).\nIn contrast to the standard approach, we do not estimate the\nparameters of the HMM directly, but\nconstruct an estimate for the joint probability distribution.\nThe idea is based on the representation of a joint probability distribution\nas an N-th-order tensor with low ranks represented in the <jats:italic>tensor train<\/jats:italic> (TT) format.\nUsing TT-format, we get an approximation by minimizing the Frobenius distance between the empirical\njoint probability distribution and tensors with low TT-ranks with core tensors normalization constraints.\nWe propose an algorithm for the solution of the optimization problem that is based on the\nalternating least squares (ALS) approach and develop its fast version for sparse tensors.\nThe order of the tensor <jats:italic>d<\/jats:italic> is a parameter of our algorithm. We have compared the performance of our algorithm\nwith the existing algorithm by Hsu, Kakade and Zhang proposed in 2009 and found that it is much more robust if the number of hidden states is overestimated.<\/jats:p>","DOI":"10.1515\/cmam-2018-0027","type":"journal-article","created":{"date-parts":[[2018,8,11]],"date-time":"2018-08-11T22:16:33Z","timestamp":1534025793000},"page":"93-99","source":"Crossref","is-referenced-by-count":3,"title":["Tensor Train Spectral Method for Learning of Hidden Markov Models (HMM)"],"prefix":"10.1515","volume":"19","author":[{"given":"Maxim A.","family":"Kuznetsov","sequence":"first","affiliation":[{"name":"Skolkovo Institute of Science and Technology , Skolkovo Innovation Center Moscow, 143025 , Moscow , Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan V.","family":"Oseledets","sequence":"additional","affiliation":[{"name":"Skolkovo Institute of Science and Technology , Skolkovo Innovation Center Moscow, 143025 , Moscow , Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2018,8,11]]},"reference":[{"key":"2023033110133774899_j_cmam-2018-0027_ref_001_w2aab3b7e1759b1b6b1ab2b1b1Aa","unstructured":"A.  Anandkumar, R.  Ge, D.  Hsu, S. M.  Kakade and M.  Telgarsky,\nTensor decompositions for learning latent variable models,\nJ. Mach. Learn. Res. 15 (2014), 2773\u20132832."},{"key":"2023033110133774899_j_cmam-2018-0027_ref_002_w2aab3b7e1759b1b6b1ab2b1b2Aa","doi-asserted-by":"crossref","unstructured":"B. W.  Bader and T. G.  Kolda,\nEfficient MATLAB computations with sparse and factored tensors,\nSIAM J. Sci. Comput. 30 (2007\/08), no. 1, 205\u2013231.","DOI":"10.1137\/060676489"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_003_w2aab3b7e1759b1b6b1ab2b1b3Aa","doi-asserted-by":"crossref","unstructured":"L. E.  Baum, T.  Petrie, G.  Soules and N.  Weiss,\nA maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains,\nAnn. Math. Statist. 41 (1970), 164\u2013171.","DOI":"10.1214\/aoms\/1177697196"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_004_w2aab3b7e1759b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"J. D.  Caroll and J. J.  Chang,\nAnalysis of individual differences in multidimensional scaling via n-way generalization of Eckart\u2013Young decomposition,\nPsychometrika 35 (1970), 283\u2013319.","DOI":"10.1007\/BF02310791"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_005_w2aab3b7e1759b1b6b1ab2b1b5Aa","doi-asserted-by":"crossref","unstructured":"V.  de Silva and L.-H.  Lim,\nTensor rank and the ill-posedness of the best low-rank approximation problem,\nSIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1084\u20131127.","DOI":"10.1137\/06066518X"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_006_w2aab3b7e1759b1b6b1ab2b1b6Aa","doi-asserted-by":"crossref","unstructured":"L.  Grasedyck,\nHierarchical singular value decomposition of tensors,\nSIAM J. Matrix Anal. Appl. 31 (2009\/10), no. 4, 2029\u20132054.","DOI":"10.1137\/090764189"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_007_w2aab3b7e1759b1b6b1ab2b1b7Aa","doi-asserted-by":"crossref","unstructured":"W.  Hackbusch and S.  K\u00fchn,\nA new scheme for the tensor representation,\nJ. Fourier Anal. Appl. 15 (2009), no. 5, 706\u2013722.","DOI":"10.1007\/s00041-009-9094-9"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_008_w2aab3b7e1759b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"D.  Hsu, S. M.  Kakade and T.  Zhang,\nA spectral algorithm for learning hidden Markov models,\nJ. Comput. System Sci. 78 (2012), no. 5, 1460\u20131480.","DOI":"10.1016\/j.jcss.2011.12.025"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_009_w2aab3b7e1759b1b6b1ab2b1b9Aa","unstructured":"X. D.  Huang, Y.  Ariki and M. A.  Jack,\nHidden Markov Models for Speech Recognition,\nEdinburgh University, Edinburgh, 1990."},{"key":"2023033110133774899_j_cmam-2018-0027_ref_010_w2aab3b7e1759b1b6b1ab2b1c10Aa","doi-asserted-by":"crossref","unstructured":"H.  Jaeger,\nObservable operator models for discrete stochastic time series,\nNeural Comput. 12 (2000), no. 6, 1371\u20131398.","DOI":"10.1162\/089976600300015411"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_011_w2aab3b7e1759b1b6b1ab2b1c11Aa","doi-asserted-by":"crossref","unstructured":"T. G.  Kolda and B. W.  Bader,\nTensor decompositions and applications,\nSIAM Rev. 51 (2009), no. 3, 455\u2013500.","DOI":"10.1137\/07070111X"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_012_w2aab3b7e1759b1b6b1ab2b1c12Aa","doi-asserted-by":"crossref","unstructured":"A.  Krogh, B.  Larsson, G.  Von Heijne and E. L. L.  Sonnhammer,\nPredicting transmembrane protein topology with a hidden Markov model: Application to complete genomes,\nJ. Mol. Biol. 305 (2001), no. 3, 567\u2013580.","DOI":"10.1006\/jmbi.2000.4315"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_013_w2aab3b7e1759b1b6b1ab2b1c13Aa","doi-asserted-by":"crossref","unstructured":"I. V.  Oseledets,\nTensor-train decomposition,\nSIAM J. Sci. Comput. 33 (2011), no. 5, 2295\u20132317.","DOI":"10.1137\/090752286"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_014_w2aab3b7e1759b1b6b1ab2b1c14Aa","unstructured":"I.  Oseledets, M.  Rakhuba and A.  Uschmajew,\nAlternating least squares as moving subspace correction,\npreprint (2017), https:\/\/arxiv.org\/abs\/1709.07286."},{"key":"2023033110133774899_j_cmam-2018-0027_ref_015_w2aab3b7e1759b1b6b1ab2b1c15Aa","doi-asserted-by":"crossref","unstructured":"I. V.  Oseledets and E. E.  Tyrtyshnikov,\nBreaking the curse of dimensionality, or how to use SVD in many dimensions,\nSIAM J. Sci. Comput. 31 (2009), no. 5, 3744\u20133759.","DOI":"10.1137\/090748330"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_016_w2aab3b7e1759b1b6b1ab2b1c16Aa","doi-asserted-by":"crossref","unstructured":"L.  Rabiner,\nA tutorial on hidden Markov models and selected applications in speech recognition,\nProc. IEEE 77 (1989), no. 2, 257\u2013286.","DOI":"10.1109\/5.18626"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_017_w2aab3b7e1759b1b6b1ab2b1c17Aa","doi-asserted-by":"crossref","unstructured":"T.  Rohwedder and A.  Uschmajew,\nOn local convergence of alternating schemes for optimization of convex problems in the tensor train format,\nSIAM J. Numer. Anal. 51 (2013), no. 2, 1134\u20131162.","DOI":"10.1137\/110857520"},{"key":"2023033110133774899_j_cmam-2018-0027_ref_018_w2aab3b7e1759b1b6b1ab2b1c18Aa","unstructured":"S. M.  Siddiqi, B.  Boots and G. J.  Gordon,\nReduced-rank hidden Markov models,\nInternational Conference on Artificial Intelligence and Statistics,\nPMLR, (2010), 741\u2013748."},{"key":"2023033110133774899_j_cmam-2018-0027_ref_019_w2aab3b7e1759b1b6b1ab2b1c19Aa","unstructured":"L.  Song, M.  Ishteva, A.  Parikh, E.  Xing and H.  Park,\nHierarchical tensor decomposition of latent tree graphical models,\nProceedings of the 30th International Conference on Machine Learning (ICML-13),\nPMLR (2013), 334\u2013342."},{"key":"2023033110133774899_j_cmam-2018-0027_ref_020_w2aab3b7e1759b1b6b1ab2b1c20Aa","unstructured":"L.  Song, E. P.  Xing and A. P.  Parikh,\nA spectral algorithm for latent tree graphical models,\nProceedings of the 28th International Conference on Machine Learning (ICML-11),\nPMLR (2011), 1065\u20131072."},{"key":"2023033110133774899_j_cmam-2018-0027_ref_021_w2aab3b7e1759b1b6b1ab2b1c21Aa","doi-asserted-by":"crossref","unstructured":"K.  Stratos, M.  Collins and D.  Hsu,\nUnsupervised part-of-speech tagging with anchor hidden Markov models,\nTrans. Assoc. Comput. Linguist. 4 (2016), 245\u2013257.","DOI":"10.1162\/tacl_a_00096"}],"container-title":["Computational Methods in Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/cmam\/19\/1\/article-p93.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2018-0027\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2018-0027\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,31]],"date-time":"2023-03-31T11:34:53Z","timestamp":1680262493000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2018-0027\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,11]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2018,7,7]]},"published-print":{"date-parts":[[2019,1,1]]}},"alternative-id":["10.1515\/cmam-2018-0027"],"URL":"https:\/\/doi.org\/10.1515\/cmam-2018-0027","relation":{},"ISSN":["1609-9389","1609-4840"],"issn-type":[{"value":"1609-9389","type":"electronic"},{"value":"1609-4840","type":"print"}],"subject":[],"published":{"date-parts":[[2018,8,11]]}}}