De meerwaarde van imprecisie: algoritmen voor het schatten van toestandsrijen in imprecieze verborgen Markovmodellen

Cedric De Boom
Wanneer twijfel ook een nut kan hebben“Rond de ochtend komen al gauw stapelwolken opzetten, en tegen de middag verwachten we enkele hevige buien over het westen van het land. Dit is gelukkig van korte duur, want rond de klok van vijf zal het meteen opklaren.” Aldus een doordeweeks weerbericht op uw favoriete radiozender. De weersvoorspeller van dienst lijkt zeker van zijn stuk. Zijn voorspellingen zijn vaak gebaseerd op computermodellen. Maar wat als deze computermodellen niet 100 procent exact zijn?

De meerwaarde van imprecisie: algoritmen voor het schatten van toestandsrijen in imprecieze verborgen Markovmodellen

Wanneer twijfel ook een nut kan hebben

“Rond de ochtend komen al gauw stapelwolken opzetten, en tegen de middag verwachten we enkele hevige buien over het westen van het land. Dit is gelukkig van korte duur, want rond de klok van vijf zal het meteen opklaren.” Aldus een doordeweeks weerbericht op uw favoriete radiozender. De weersvoorspeller van dienst lijkt zeker van zijn stuk. Zijn voorspellingen zijn vaak gebaseerd op computermodellen. Maar wat als deze computermodellen niet 100 procent exact zijn? Willen we dan niet liever dat de weerman zegt dat het morgen kan regenen, maar dat het evengoed droog kan blijven? Misschien waagt u dan wel de kans om een buitenactiviteit te doen in plaats van een hele dag binnen te blijven?

Imprecieze waarschijnlijkhedenComputermodellen worden gebruikt in haast elk systeem dat informatie verwerkt. Beursanalysten gebruiken dergelijke systemen om de koers van een aandeel te voorspellen, ingenieurs om de kans op een tsunami in Japan te achterhalen, en dokters om kanker diagnosticeren. Deze modellen gaan steevast uit van waarschijnlijkheden: de kans dat u aan kanker lijdt is bijvoorbeeld 10% indien er een ander bekend geval is binnen uw familiekring. Waarschijnlijkheden als deze kunnen aangeleerd worden door het verwerken van enorme hoeveelheden data, of kunnen opgelegd worden door een domeinexpert. Er zijn echter twee grote problemen met deze klassieke aanpak: enerzijds is het niet altijd eenvoudig om op een goedkope en snelle manier aan veel data te geraken, en anderzijds kan zelfs de beste expert niet vertellen of de kans op goed weer 13% dan wel 14% is.

We kunnen dit probleem eenvoudig uit de weg gaan door het gebruik van zogenaamde imprecieze waarschijnlijkheden. Daarmee willen we bijvoorbeeld zeggen: “We zijn niet zeker of de kans op kanker exact 10% is; de kans ligt eerder tussen 5% en 15%.” Met andere woorden, we geven toe dat we ons model gewoonweg niet precies genoeg kunnen opstellen. Toepassingen die gebruik maken van imprecieze waarschijnlijkheden kunnen dan ook eenvoudig duidelijk maken wanneer ze niet zeker zijn van een bepaalde voorspelling.

Het voorspellen van reeksenStel dat het weer op dag één zonnig is, op dag twee bewolkt en op dag drie regenachtig. Op deze manier krijgen we een opeenvolging van drie weerstoestanden, een zogenaamde toestandsreeks. Als we het weer op iedere dag reeds kennen, valt er uiteraard niets meer te voorspellen. We sluiten ons, bij wijze van experiment, een week lang op in een kamer zonder vensters, en we meten op iedere dag de luchtdruk. Op basis van onze waarnemingen, ook wel observaties genoemd, proberen we vervolgens het weer van de afgelopen week te voorspellen. Dit doen we aan de hand van een waarschijnlijkheidsmodel: de kans dat we een hoge luchtdruk waarnemen bij zonnig weer is bijvoorbeeld 70%, terwijl deze kans slechts 20% is bij bewolkt weer en 10% bij regen. De kans om een zonnige dag te hebben na een regenachtige dag is bijvoorbeeld 25%, daar waar de kans op twee opeenvolgende regendagen 40% is.

Het voorspellen van het weer gebeurt nu traditioneel op basis van het beroemde Viterbi-algoritme dat ontwikkeld werd eind jaren ‘60. Het werd reeds succesvol toegepast bij ruimtecommunicatie, het verwerken van spraak, het analyseren van DNA enz. In ons voorbeeld berekent het algoritme snel en efficiënt de meest waarschijnlijke reeks van weerstoestanden op basis van onze luchtdrukobservaties. Tot dusver nihil novi sub sole...Het voorspellen van reeksen, maar beterEr is echter een probleem met de klassieke aanpak van het probleem. Het Viterbi-algoritme maakt namelijk gebruik van een traditioneel waarschijnlijkheidsmodel. Indien dit model niet exact overeenkomt met de realiteit, hoe kunnen we dan zeker zijn van de voorspellingen die het algoritme maakt? Dit is het punt in het verhaal waar imprecieze waarschijnlijkheden ten tonele komen.

Ik heb zelf, onder helpende hand van Jasper De Bock, Arthur Van Camp en professor Gert de Cooman, een meer robuuste versie van het Viterbi-algoritme ontwikkeld: MaxiHMM, een soort ‘Viterbi 2.0’, zo u wil. Het algoritme is volledig gestoeld op het gebruik van imprecieze waarschijnlijkheidsmodellen en is qua efficiëntie vergelijkbaar met het traditionele Viterbi-algoritme. Door het gebruik van imprecieze modellen kan het algoritme op eenvoudige wijze zijn zekerheid of vertrouwen uitdrukken in de voorspellingen die het doet. Bij een aanzienlijke imprecisie zal MaxiHMM veel voorspellingen teruggeven die mogelijks juist kunnen zijn; bij weinig imprecisie berekent MaxiHMM in het beste geval slechts één voorspelling.

Stel dat MaxiHMM berekent dat het weer op dagen één, twee en drie ofwel zonnig-zonnig-bewolkt is, ofwel zonnig-bewolkt-bewolkt, en dit uitgaande van een imprecies waarschijnlijkheidsmodel. Ons algoritme is zeker van het weer op dagen één en drie, maar blijkt onzeker over het weer op dag twee. Het weer op dag twee kan dus zonnig, bewolkt of eventueel ergens daartussenin zijn. De gebruiker van het algoritme krijgt aldus een beter beeld van het vertrouwen dat hij moet hechten aan de voorspellingen die hem worden aangereikt.

Toepassingen: muziek, spraak, DNA, beurs...De toepassingen van het Viterbi-algoritme zijn legio, zoals bijvoorbeeld het verwerken van spraak, het analyseren van DNA-ketens en het voorspellen van beurskoersen. Al deze toepassingen kunnen vanaf nu eenvoudig gebruik maken van het MaxiHMM-algoritme. Op die manier kunnen ze meer en betere informatie verschaffen aan de eindgebruiker.

Ter illustratie behandelen we een ludieke toepassing die eigenhandig werd uitgewerkt. Hierbij wordt een muzikale melodie op automatische wijze voorzien van de gepaste akkoorden, die nadien gebruikt kunnen worden bij het begeleiden van deze melodie. Een voorbeeld wordt gegeven in Figuur 1. Het mooie is dat MaxiHMM meerdere akkoordopeenvolgingen kan genereren, zodat je zelf diegene kan uitkiezen die je het meest aanstaat. Uiteraard hoeft het niet beperkt te blijven tot akkoorden, maar kunnen bijvoorbeeld ook vingerzettingen worden berekend voor pianisten, of er kan een melodie worden gegenereerd op een gegeven akkoordenschema.

Ik hoop dat bij deze de meerwaarde en het nut van twijfel en imprecisie is aangetoond. Als u de volgende keer een weerbericht beluistert, en de voorspellingen blijken uiteindelijk niet te kloppen, had de weerman dan niet beter gezegd: “Mijn excuses, beste luisteraars, maar vandaag weet ik het niet.”

Bibliografie

[1] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically op- timum decoding algorithm,” IEEE Transactions on Information Theory, vol. 13, no. 2, pp. 260 – 269, 1967.[2] J. Schiller, Mobile Communications, 2nd ed. Addison Wesley, 2003.[3] I. Glover and P. Grant, Digital Communications, 3rd ed. Prentice Hall, 2009.[4] G. de Cooman, Waarschijnlijkheidsrekening en Statistiek, 2010.[5] B. de Finetti, Theory of Probability. John Wiley & Sons, 1990.[6] P. Walley, Statistical Reasoning with Imprecise Probabilities. Chapman & Hall, 1991.[7] Wikipedia, “Extreme point — Wikipedia, The Free Encyclopedia,” http:// en.wikipedia.org/w/index.php?title=Extreme_point&oldid=609503320 [On- line; accessed 21-May-2014], 2014.[8] M. C. Troffaes, “Decision making under uncertainty using imprecise proba- bilities,” International Journal of Approximate Reasoning, vol. 45, no. 1, pp. 17–29, May 2007.[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and S. Clifford, Introduction to Algorithms. MIT Press, 2009.[10] J. De Bock and G. de Cooman, “State sequence prediction in imprecise hidden Markov models,” in ISIPTA ’11, 2011.[11] A. Drozdek, Data structures and algorithms in C++. Brooks/Cole, 2001.[12] C. Adams and R. Franzosa, Introduction to Topology, 1st ed., 2007.[13] R. Wrede and M. Spiegel, Schaum’s Outline of Advanced Calculus, 3rd ed., 2010.[14] N. Borrel-Jensen and A. H. Danielsen, “Computer-assisted music composition – A database-backed algorithmic composition system,” University of Copenhagen, 2010.[15] G. de Cooman, F. Hermans, A. Antonucci, and M. Zaffalon, “Epistemic ir- relevance in credal nets: the case of imprecise Markov trees,” International Journal of Approximate Reasoning, vol. 51, no. 9, pp. 1029—-1052, 2010.[16] G. Corani and M. Zaffalon, “Learning Reliable Classifiers From Small or Incomplete Data Sets : The Naive Credal Classifier 2,” Machine Learning, vol. 9, no. 1532-4435, pp. 581–621, 2008.[17] C. M. Bishop, Pattern Recognition and Machine Learning. Springer, 2007.[18] D.G. Brown and D. Golod, “Decoding HMMs using the k best paths: algorithms and applications.” BMC bioinformatics, vol. 11 Suppl 1, p. S28, Jan. 2010.[19] I. Couso, M. Serafín, and P. Walley, “Examples of Independence for Imprecise Probabilities,” in ISIPTA ’99, no. July, 1999, pp. 121–130.[20] Z. Huang, Y. Chang, B. Long, and J.-f. Crespo, “Iterative Viterbi A * Algorithm for K -Best Sequential Decoding,” in Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers, vol. 1, no. July, 2012, pp. 611–619.[21] E. Miranda, “A survey of the theory of coherent lower previsions,” International Journal of Approximate Reasoning, vol. 48, no. 2, pp. 628–658, Jun. 2008.[22] J. Norris, Markov chains. Cambridge University Press, 1998.[23] L. Rabiner and B.-H. Juang, Fundamentals of Speech Recognition. Prentice Hall, 1993.[24] T. Seidenfeld, “A contrast between two decision rules for use with (convex) sets of probabilities: Gamma-maximin versus E-admissibility,” 2002.[25] M. C. M. Troffaes and G. de Cooman, Lower Previsions. Wiley, 2014.[26] P. Walley, “Towards a unified theory of imprecise probability,” International Journal of Approximate Reasoning, vol. 24, pp. 125–148, 2000.[27] P. Walley, “Inferences from Multinomial Data : Learning about a Bag of Marbles,” Journal of the Royal Statistical Society. Series B, vol. 58, no. 1, pp. 3–57, 1996.

Universiteit of Hogeschool
Master of Science in de ingenieurswetenschappen: computerwetenschappen: informatie- en communicatietechnologie
Publicatiejaar
2014
Kernwoorden
@cedricdb
Share this on: