Detta papper handlar om algoritmer för förutsägelse av diskreta sekvenser över ett finit alfabet, med hjälp av variabel ordning Markov modeller. Klassen av sådana algoritmer är stor och inkluderar i princip all förlustfri komprimeringsalgoritm. Vi fokuserar på sex framstående förutsägelser algoritmer, inklusive Context Tree Weighting (CTW), Förutsägelse av Partial Match (PPM) och Probabilistic Suffix Trees (PST). Vi diskuterar egenskaperna hos dessa algoritmer och jämför deras prestanda med hjälp av verkliga livssekvenser från tre domäner: proteiner, engelsk text och musikstycken. Jämförelsen görs med avseende på förutsägelsekvaliteten mätt med den genomsnittliga log-förlusten. Vi jämför också klassificeringsalgoritmer baserade på dessa prediktorer med avseende på ett antal stora proteinklassificeringsuppgifter. Våra resultat indikerar att en "dekomponerad" CTW (en variant av CTW algoritm) och PPM överträffar alla andra algoritmer i sekvensförutsägelse uppgifter. Något överraskande, en annan algoritm, som är en ändring av Lempel-Ziv komprimeringsalgoritm, betydligt överträffar alla algoritmer på proteinklassificeringsproblem.
Enligt REF kan varje förlustfri komprimeringsalgoritm användas för förutsägelse.
On Prediction Using Variable Order Markov Models
{'venue': 'Journal Of Artificial Intelligence Research, Volume 22, pages 385-421, 2004', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}