Variabele-orde Markov-model

In stochastische processen, een onderwerp in de wiskunde, Variable-orde Markov modellen zijn een belangrijke klasse van modellen die de bekende Markov keten modellen uit te breiden. In tegenstelling tot de Markov keten modellen, waarbij elke willekeurige variabele in een sequentie met een Markov eigenschap is afhankelijk van een vast aantal willekeurige variabelen, in VOM modellen dit aantal van conditionering willekeurige variabelen kunnen variëren op basis van de specifieke waargenomen realisatie.

Dit besef sequentie wordt vaak genoemd de context; daarom VOM modellen worden ook wel context bomen. De flexibiliteit van het aantal conditionering random variabelen blijkt van groot voordeel zijn voor vele toepassingen, zoals statistische analyse, classificatie en voorspelling.

Voorbeeld

Beschouw bijvoorbeeld een reeks van willekeurige variabelen, die elk met een waarde van het ternaire alfabet {a, b, c}. Specifiek, overwegen de aaabcaaabcaaabcaaabc ... aaabc reeks opgebouwd uit oneindig aaneenschakelingen van de sub-string aaabc.

De VOM model van de maximale orde 2 kunnen de bovenstaande string met behulp van alleen de volgende vijf voorwaardelijke kans componenten benaderen: {Pr = 0,5, Pr = 0,5, Pr = 1,0, Pr = 1,0, Pr = 1,0}.

In dit voorbeeld, Pr = Pr = 1,0; Daarom, hoe korter context b volstaat om het volgende teken te bepalen. Evenzo kan de VOM model van maximaal order 3 de snaar precies met slechts vijf conditionele waarschijnlijkheid onderdelen, die allemaal gelijk zijn aan 1,0 te genereren.

Om de Markov keten van orde 1 te construeren voor het volgende karakter in die string, moet men de volgende 9 voorwaardelijke kans componenten te schatten: {Pr, Pr, Pr, Pr, Pr, Pr, Pr, Pr, Pr}. {Pr, Pr, ..., Pr}: naar de Markov keten van orde 2 te construeren voor het volgende karakter, moet men 27 voorwaardelijke kans componenten te schatten. En om de Markov keten van orde drie te bouwen voor het volgende teken moet men de volgende 81 voorwaardelijke kans componenten te schatten: {Pr, Pr, ..., Pr}.

In de praktijk instellingen er zelden voldoende gegevens om nauwkeurig te schatten het exponentieel toenemende aantal voorwaardelijke waarschijnlijkheid componenten als de volgorde van de Markov keten toeneemt.

De variabele-orde Markov model veronderstelt dat in realistische instellingen, zijn er bepaalde realisaties van toestanden waarin sommige verleden toestanden onafhankelijk van de toekomstige toestanden; Dienovereenkomstig "een grote vermindering van het aantal modelparameters worden bereikt. '

Definitie

Laten een state ruimte van formaat | A |.

Overweeg een reeks met de eigenschap Markov van de realisaties van random variabelen, waar is de staat op positie 1≤≤, en de aaneenschakeling van staten en wordt aangeduid met.

Gegeven een training set van waargenomen toestanden ,, de constructie algoritme van de VOM modellen leert een model dat een kans opdracht voor elke staat in de reeks gezien haar verleden of de toekomst staten biedt.

Specifiek, de leerling genereert een voorwaardelijke kansverdeling voor een symbool gegeven context, waar de * teken staat voor een reeks van staten van elke lengte, met inbegrip van de lege context.

VOM modellen trachten te schatten voorwaardelijke verdelingen van de vorm waarin de context lengte || ≤ varieert afhankelijk van de beschikbare statistieken. Daarentegen gebruikelijke Markov modellen trachten schatten deze conditionele verdelingen onder aanname lengte vaste contexten '|| = en dus beschouwd kunnen worden als speciale gevallen van de VOM modellen.

Effectief voor een gegeven trainingsreeks, het VOM modellen blijken beter model parametrering dan de vaste-orde Markov modellen die leidt tot een betere variantie-vertekening afweging van de geleerde modellen te verkrijgen.

Toepassingsgebieden

Verscheidene efficiënte algoritmen zijn ontwikkeld voor het schatten van de parameters van het model VOM.

VOM modellen zijn met succes toegepast op gebieden zoals machine learning, informatietheorie en bioinformatica, waaronder specifieke toepassingen zoals codering en gegevenscompressie, document compressie, classificatie en identificatie van DNA en eiwitsequenties, statistische procesbeheersing, spamfilters, haplotyping ea .

(0)
(0)
Commentaren - 0
Geen commentaar

Voeg een reactie

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha