Vi presenterar en metod för att påskynda de dynamiska programalgoritmer som används för att lösa HMM-avkodnings- och träningsproblem för diskreta tidsoberoende HMMs. Vi diskuterar tillämpningen av vår metod på Viterbis avkodnings- och utbildningsalgoritmer (IEEE Trans). Informera. Teori IT-13:260-269, 1967), samt algoritmerna framåt-bakåt och Baum-Welch (ojämlikheter 3:1-8, 1972). Vårt tillvägagångssätt är baserat på att identifiera upprepade delsträngar i den observerade ingångssekvensen. Inledningsvis visar vi hur man utnyttjar upprepningar av alla tillräckligt små understrängar (detta liknar den fyraryssiska metoden). Därefter beskriver vi fyra algoritmer baserade på körlängdskodning (RLE), Lempel-Ziv (LZ78) tolkning, grammatikbaserad kompression (SLP) och byteparkodning (BPE). Jämfört med Viterbi algoritm, vi uppnå speedups av (log n) med hjälp av fyra ryssar metod, (med hjälp av RLE, ( log n k ) med LZ78, ( r k ) med SLP, och (r) med hjälp av BPE, där k är antalet dolda tillstånd, n är längden på den observerade sekvensen och r är dess kompressionsförhållande (under varje komprimeringsschema). Våra experimentella resultat visar att våra nya algoritmer verkligen är snabbare i praktiken. Vi diskuterar också ett parallellt genomförande av våra algoritmer.
I Ref föreslogs ett kompressionsbaserat tillvägagångssätt för att påskynda HMM-avkodningen.
Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}