Generating apparatus, generation method, information processing method and program

• US 9,858,592 B2
• Filed: 06/24/2015
• Issued: 01/02/2018
• Est. Priority Date: 03/14/2014
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Osogami, Takayuki
• Primary Examiner(s): Feacher, Renae
• Application Number:
  US14/748,264
• Publication Number:
  US 20150294354A1
• Time in Patent Office: 923 Days
• Field of Search: 705 711, 705 29, 705 37
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 30/0254 based on statistics

Abstract

A generating apparatus generates a set of gain vectors with respect to a transition model having observable visible states and unobservable hidden states and expressing a transition from a present visible state to a subsequent visible state according to an action, the set of gain vectors being generated for each visible state and used for calculation of a cumulative expected gain at and after a reference point in time, the apparatus including a setting section for setting, with respect to each hidden state, a probability distribution over the hidden states for selection used to select vectors to be included in the set of gain vectors from the gain vectors including a component for a cumulative gain, and a selection section for including, in the set of gain vectors, with priority, the gain vector giving the maximum of the cumulative expected gain with respect to the probability distribution for selection.

Claims

1. A computer implemented method for generating a set of gain vectors with respect to a transition model having observable visible states and unobservable hidden states and expressing a transition from a present visible state to a subsequent visible state according to an action, the set of gain vectors being generated for each visible state and used for calculation of a cumulative expected gain at and after a reference point in time, the method comprising:

setting, with respect to each hidden state, a probability distribution over the hidden states for selection used to select vectors to be included in the set of gain vectors from gain vectors including a component for a cumulative gain; and

Selection by including, in the set of gain vectors, with priority, a gain vector giving the maximum of the cumulative expected gain with respect to the probability distribution for selection; and

selecting an optimum action based on the set of gain vectors by;

setting initial conditions for visible and hidden states for an environment to be simulated;

selecting the gain vector which maximizes the cumulative expected gain with respect to the probability distribution over the hidden states at the present point in time;

selecting an action that corresponds to the selected gain vector;

executing the selected action to cause a probabilistic transition from a visible state based on a state transition probability corresponding to the selected action and a present probability distribution over the hidden states; and

updating the probability distribution over the hidden states on the basis of the state transition probability corresponding to the selected action and the present probability distribution over the hidden states.

2. The method of claim 1, further comprising recursively generating the set of gain vectors by retroacting from a future point in time to the reference point in time.

3. The method of claim 2, further comprising setting in the probability distribution for selection a vector having a length corresponding to the number of hidden states and having, with respect to each hidden state, 1 as a component corresponding to the hidden state.

4. The method of claim 2, further comprising setting a probability distribution over the hidden states updated according to a selected action corresponding to the gain vector returning the maximum of the cumulative expected gain from the set of gain vectors generated in the generation.

5. The method of claim 2, further comprising initializing the set of gain vectors at a future point N in time, wherein N is an integer equal to or larger than 2.

6. The method of claim 2, recursively generating a set Λ

_n(s) of gain vectors α

_s,n with respect to a visible state, s (sε

S, where S is a set of visible states) at a point n in time on the basis of a set Λ

_n+1(s′

) of gain vectors α

<sub>s′

,n+1</sub> with respect to each visible state, s′

(s′

ε

S) at a subsequent point n+1 in time.

7. The method of claim 6, further comprising generating a set Λ

_n(s) of gain vectors α

_s,n further on the basis of a state transition probability of transition from one visible state, s to another visible state, s′ and

an expected gain in the visible state, s′

.

8. The method of claim 1, wherein the acquisition includes obtaining a state transition probability P^a_s,i,s′

of transition from one visible state, s to another visible state, s′

in a state set S when one action a is input in a hidden state i, and wherein the selection includes causing a transition from the visible state, s in response to execution of the action a selected in the action selection on the basis of the state transition probability P^a_s,i,s′

corresponding to the selected action a and the present probability distribution over the hidden states.

9. The method of claim 8, wherein the transition includes updating a probability distribution b over the hidden states on the basis of the state transition probability P^a_s,i,s′

and the present probability distribution over the hidden states.

10. The method of claim 9, further comprising updating the probability distribution b over the hidden states by determining a probability b(i) of the hidden state being i in response to the action selected in accordance with the expression:

11. The method of claim 9, further comprising updating the probability distribution b over the hidden states by determining a probability b(i) of the hidden state being i in response to the action selected in accordance with the expression:

12. The method of claim 8, further comprising setting as the probability distribution for selection the probability distribution updated in the transition.

13. The method of claim 12, further comprising repeating:

executing the update of the probability distribution by selecting an action with respect to a predetermined time period; and

receiving the probability distribution updated by the selection method and updating the set of gain vectors by setting the probability distribution b as the probability distribution for selection.