System and method for visualizing repetitively structured Markov models

• US 7,096,154 B1
• Filed: 12/30/2003
• Issued: 08/22/2006
• Est. Priority Date: 12/30/2003
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: Andrade-Cetto, Lucio
• Primary Examiner(s): Bui, Bryan
• Application Number:
  US10/749,770
• Time in Patent Office: 966 Days
• Field of Search: 702/19, 702/150, 702/152, 702/155, 702/181, 702/182, 702/188, 382/219, 382/228, 704/243, 704/246, 704/256, 435/6
• US Class Current: 702/181
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor

Abstract

A method of displaying the probabilities associated with a Markov model as a series of interactive plots is disclosed. Three dimensions of probability data associated with a Markov model are presented to a user in a concise manner. Heat maps are used to display probability data from a Markov model so that the user can identify and understand hidden patterns and information in the data such as state and emission transitions which are not possible to see with conventional state diagram plots.

Claims

1. In an electronic device, a data visualization method comprising the steps of:

providing a data structure holding a representation of a Markov model for a system being modeled;

populating said Markov model data structure with at least one of transition probability data and emission probability data for the system being modeled; and

displaying more than one dimension of said probability data from said Markov model in a heat map.

2. The method of claim 1 wherein said Markov model data structure is a Hidden Markov model data structure.

3. The method of claim 1 wherein a probability measure is displayed in color.

4. The method of claim 1 wherein a probability measure is displayed in grayscale.

5. The method of claim 1 wherein a probability measure is displayed graphically.

6. The method of claim 1 wherein said system being modeled is a protein family sequence.

7. The method of claim 1 wherein said system being modeled is one of a speech recognition system and a financial modeling system.

8. The method of claim 1, comprising the further step of:

displaying a model state along a first dimension, an output probability field along a second dimension, and a probability measure as a third dimension.

9. The method of claim 8 wherein said probability measure is scaled using one of plain probabilities, log-probabilities and log-odds ratios probabilities.

10. The method of claim 9 wherein the scale is non-contiguous.

11. The method of claim 8 wherein said output probability field is one of a symbol emission mass distribution function at every state and transition mass distribution function at every state.

12. The method of claim 8 wherein every state in said model is displayed.

13. The method of claim 1 wherein only a portion of said probability data is displayed.

14. The method of claim 1, comprising the further steps of:

estimating programmatically said probability data prior to displaying said probability data.

15. The method of claim 14 wherein at least one of the Baum-Welch algorithm, Viterbi training algorithm, (Expectation Maximization) EM algorithm, and custom algorithm are used to estimate said probability data.

16. The method of claim 1 wherein said probability data is displayed in a heat map and comprising the further step of:

displaying an exact value of a probability measure in response to a user input.

17. In an electronic device, a system, comprising:

a Markov model visualization process, said Markov model visualization process including a probability determining algorithm and a visualization function, said probability determining algorithm determining the probabilities of the occurrence of events in a system being modeled with a Markov model, said visualization function displaying the Markov model probabilities with three dimensions of data;

a storage location holding data for components of said system being modeled;

a display device interfaced with said electronic device, said display device displaying said three dimensions of data in a heat map to a user.

18. The system of claim 17 wherein the three dimensions of data are at least one model state, at least one output probability field, and at least one probability measure after scaling.

19. The system of claim 18 wherein said at least one probability measure after scaling is at least one of plain probabilities, log-probabilities and log-odds ratios probabilities.

20. The system of claim 18 wherein said output probability field is one of a symbol emission mass distribution function at every state and transition mass distribution function at every state.

21. The system of claim 17 wherein the system being modeled by the Markov model is a protein family.

22. A medium holding computer-executable instructions for a data visualization method, said instructions comprising:

instructions for providing a data structure holding a representation of a Markov model for a system being modeled;

instructions for populating said Markov model data structure with at least one of transition probability data and emission probability data for the system being modeled; and

instructions for displaying more than one dimension of said probability data from said Markov model in a heat map.

23. The medium of claim 22 wherein said Markov model data structure is a Hidden Markov model data structure.

24. The medium of claim 22 wherein a probability measure is displayed in color.

25. The medium of claim 22 wherein a probability measure is displayed in grayscale.

26. The medium of claim 22 wherein a probability measure is displayed graphically.

27. The medium of claim 22 wherein said system being modeled is a protein family sequence.

28. The medium of claim 22 wherein said system being modeled is one of a speech recognition system and a financial modeling system.

29. The medium of claim 22, wherein the instructions further comprise:

instructions for displaying a model state along a first dimension, an output probability field along a second dimension, and a probability measure as a third dimension.

30. The medium of claim 29 wherein said probability measure is scaled using one of plain probabilities, log-probabilities and log-odds ratios probabilities.

31. The medium of claim 30 wherein the scale is non-contiguous.

32. The medium of claim 29 wherein said output probability field is one of a symbol emission mass distribution function at every state and transition mass distribution function at every state.

33. The medium of claim 22 wherein every state in said model is displayed.

34. The medium of claim 22 wherein only a portion of said probability data is displayed.

35. The medium of claim 22, wherein said instructions further comprise:

instructions for estimating programmatically said probability data prior to displaying said probability data.

36. The medium of claim 35 wherein at least one of the Baum-Welch algorithm, Viterbi training algorithm, (Expectation Maximization) EM algorithm, and custom algorithm are used to estimate said probability data.

37. The medium of claim 22 wherein said probability data is displayed in a heat map and the instructions further comprise:

instructions for displaying an exact value of a probability measure in response to a user input.