DATA PROCESSING DEVICE, DATA PROCESSING METHOD AND PROGRAM

• US 20110288835A1
• Filed: 05/12/2011
• Published: 11/24/2011
• Est. Priority Date: 05/20/2010
• Status: Abandoned Application

• Current Assignee: Sony Corporation (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.)
• Inventors: Hasuo, Takashi, Kawamoto, Kenta
• Application Number:
  US13/106,071
• Publication Number:
  US 20110288835A1
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models

Abstract

A data processing device includes a parameter estimation unit and a structure adjustment unit. The structure adjustment unit notes each state of an HMM as a noted state, obtains, for the noted state, a value corresponding to an eigen value difference which is a difference between a partial eigen value sum and a total eigen value sum, as a target degree value indicating a degree for selecting the noted state as a division target or a mergence target, selects a state having the target degree value larger than a division threshold value, as a division target, and selects a state having the target degree value smaller than a mergence threshold value, as a mergence target.

Claims

1. A data processing device comprising:

a parameter estimation means that performs parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

a structure adjustment means that selects a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and performs structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment means notes each state of the HMM as a noted state;

obtains, for the noted state, a value corresponding to an eigen value difference which is a difference between a partial eigen value sum which is a sum of eigen values of a partial state transition matrix excluding a state transition probability from the noted state and a state transition probability to the noted state, from a state transition matrix having state transition probabilities from each state to each state of the HMM as components, and a total eigen value sum which is a sum of eigen values of the state transition matrix, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selects a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selects a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.

2. The data processing device according to claim 1, wherein the structure adjustment means obtains an average state probability which is obtained by averaging a state probability of the noted state in a time direction when a sample of the time series data at each time is observed, and obtains a synthesis value obtained by synthesizing the eigen value difference of the noted state with the average state probability as a target degree value of the noted state.

3. The data processing device according to claim 1, further comprising an evaluation means that evaluates an HMM after parameter estimation and determines whether or not to perform the structure adjustment based on a result of the estimation of the HMM.

4. The data processing device according to claim 3, wherein the evaluation means determines that the structure adjustment is performed if an increment of likelihood in which the time series data is observed in an HMM after parameter estimation with respect to a likelihood in which the time series data is observed in an HMM before the parameter estimation is smaller than a predetermined value.

5. The data processing device according to claim 1, wherein the division threshold value is a value larger than an average value of target degree values of all the states of the HMM by a standard deviation of the target degree values of all the states of the HMM, and the mergence threshold value is a value smaller than an average value of target degree values of all the states of the HMM by a standard deviation of the target degree values of all the states of the HMM.

6. The data processing device according to claim 1, wherein in the division of the division target, the structure adjustment means adds a new state, adds state transitions between the new state and other states having state transitions with the division target, a self transition, and a state transition between the new state and the division target as state transitions with the new state, and

wherein in the mergence of the mergence target, the structure adjustment means removes the mergence target, and adds state transitions between each of other states having state transitions with the mergence target.

7. A data processing method comprising the steps of:

causing a data processing device to perform parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

to select a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and to perform structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment step includes

noting each state of the HMM as a noted state;

obtaining, for the noted state, a value corresponding to an eigen value difference which is a difference between a partial eigen value sum which is a sum of eigen values of a partial state transition matrix excluding a state transition probability from the noted state and a state transition probability to the noted state from a state transition matrix having state transition probabilities from each state to each state of the HMM as components, and a total eigen value sum which is a sum of eigen values of the state transition matrix, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selecting a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selecting a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.

8. A program enabling a computer to function as:

a parameter estimation means that performs parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

a structure adjustment means that selects a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and performs structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment means notes each state of the HMM as a noted state;

obtains, for the noted state, a value corresponding to an eigen value difference which is a difference between a partial eigen value sum which is a sum of eigen values of a partial state transition matrix excluding a state transition probability from the noted state and a state transition probability to the noted state, from a state transition matrix having state transition probabilities from each state to each state of the HMM as components, and a total eigen value sum which is a sum of eigen values of the state transition matrix, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selects a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selects a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.

9. A data processing device comprising:

a parameter estimation means that performs parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

a structure adjustment means that selects a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and performs structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment means notes each state of the HMM as a noted state;

obtains, for the noted state, an average state probability which is obtained by averaging a state probability of the noted state in a time direction when a sample of the time series data at each time is observed, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selects a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selects a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.

10. The data processing device according to claim 9, further comprising an evaluation means that evaluates an HMM after parameter estimation and determines whether or not to perform the structure adjustment based on a result of the estimation of the HMM.

11. The data processing device according to claim 10, wherein the evaluation means determines that the structure adjustment is performed if an increment of likelihood in which the time series data is observed in an HMM after parameter estimation with respect to a likelihood in which the time series data is observed in an HMM before the parameter estimation is smaller than a predetermined value.

12. The data processing device according to claim 9, wherein the division threshold value is a value larger than an average value of target degree values of all the states of the HMM by a standard deviation of the target degree values of all the states of the HMM, and the mergence threshold value is a value smaller than an average value of target degree values of all the states of the HMM by a standard deviation of the target degree values of all the states of the HMM.

13. The data processing device according to claim 9, wherein in the division of the division target, the structure adjustment means adds a new state, adds state transitions between the new state and other states having state transitions with the division target, a self transition, and a state transition between the new state and the division target as state transitions with the new state, and

wherein in the mergence of the mergence target, the structure adjustment means removes the mergence target, and adds state transitions between each of other states having state transitions with the mergence target.

14. A data processing method comprising the steps of:

causing a data processing device to perform parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

to select a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and to perform structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment step includes

noting each state of the HMM as a noted state;

obtaining, for the noted state, an average state probability which is obtained by averaging a state probability of the noted state in a time direction when a sample of the time series data at each time is observed, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selecting a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selecting a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.

15. A program enabling a computer to function as:

a parameter estimation means that performs parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

a structure adjustment means that selects a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and performs structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment means notes each state of the HMM as a noted state;

obtains, for the noted state, an average state probability which is obtained by averaging a state probability of the noted state in a time direction when a sample of the time series data at each time is observed, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selects a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selects a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.

16. A data processing device comprising:

a parameter estimation unit that performs parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

a structure adjustment unit that selects a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and performs structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment unit notes each state of the HMM as a noted state;

obtains, for the noted state, a value corresponding to an eigen value difference which is a difference between a partial eigen value sum which is a sum of eigen values of a partial state transition matrix excluding a state transition probability from the noted state and a state transition probability to the noted state from a state transition matrix having state transition probabilities from each state to each state of the HMM as components, and a total eigen value sum which is a sum of eigen values of the state transition matrix, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selects a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selects a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.

17. A data processing device comprising:

a parameter estimation unit that performs parameter estimation for estimating parameters of an HMM (Hidden Markov Model) using time series data; and

a structure adjustment unit that selects a division target which is a state to be divided and a mergence target which is a state to be merged from states of the HMM, and performs structure adjustment for adjusting a structure of the HMM by dividing the division target and merging the mergence target,

wherein the structure adjustment unit notes each state of the HMM as a noted state;

obtains, for the noted state, an average state probability which is obtained by averaging a state probability of the noted state in a time direction when a sample of the time series data at each time is observed, as a target degree value indicating a degree for selecting the noted state as the division target or the mergence target; and

selects a state having the target degree value larger than a division threshold value which is a threshold value larger than an average value of target degree values of all the states of the HMM, as the division target, and selects a state having the target degree value smaller than a mergence threshold value which is a threshold value smaller than an average value of target degree values of all the states of the HMM, as the mergence target.