Probabilistic learning element

• US 4,593,367 A
• Filed: 01/16/1984
• Issued: 06/03/1986
• Est. Priority Date: 01/16/1984
• Status: Expired due to Term

• Current Assignee: ITT Corporation (ITT, Inc.)
• Original Assignee: ITT Corporation (ITT, Inc.)
• Inventors: Denenberg, Jeffrey N., Slack, Thomas B.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Grossman, Jon D.
• Application Number:
  US06/571,230
• Time in Patent Office: 869 Days
• Field of Search: 364/134, 364/148, 364/149, 364/200, 364/300, 364/513, 364/728, 364/877, 364/900, 382/15
• US Class Current: 706/12
• CPC Class Codes: G06F 18/00 Pattern recognition
• 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: G06N 20/00 Machine learning
• CPC Class Codes: G06V 10/70 using pattern recognition or machine learning optical pattern recognition or electronic computations therefor G06V10/88
• CPC Class Codes: G06V 10/85 Markov-related models; Markov random fields

Abstract

A probabilistic learning element particularly adapted for use as a task independent sequential pattern recognition device receives sequences of objects and outputs sequences of recognized states composed of objects and includes a plurality of memories for storing the received sequences of objects and previously learned states as well as predetermined types of knowledge relating to previously learned states. The sequences of received objects are correlated with the information relating to the previously learned states in order to assign probabilities to possible next states in the sequence of recognized states. Based upon the probabilities of the possible next states the most likely next state is determined and outputted as a recognized next state in the recognized state sequence when the element determines that a state has ended. The element additionally includes means for providing a rating of confidence in the recognized next state. The ratings of confidence for a sequence of recognized stated are accumulated and if the accumulated value exceeds a predetermined threshold level the element will be caused to store the recognized state sequence as a learned state sequence.

Claims

1. A probabilistic learning element, that sequentially receives objects and outputs sequences of recognized states, said learning element comprising:

means for sequentially receiving objects;

means for storing,

said received objects,

sequences of received objects,

previously learned sequences of states,

states contained in said previously learned sequences of states, and

predetermined types of knowledge relating to,

said previously learned sequences of states,

said states contained in said previously learned sequences of states,

objects contained in said previously learned sequences of states, and

sequences of objects contained in said previously learned sequences of states, whereby current object information relating to

said received objects and said sequences of received objects is stored as well as statistical information relating to previously learned sequences of states and said states, objects and sequences of objects contained in said previously learned sequences of states;

means for correlating said stored current object information with said stored statistical information for assigning probabilities to possible next states in the sequence of recognized states;

means, responsive to said probabilities of possible next states, for determining a most likely next state;

means, responsive to the stored current object information and statistical information, for providing a signal corresponding to the probability that a state has ended; and

means, responsive to said end of state signal, for outputting said most likely next state as a recognized next state in a recognized state sequence.

2. A probabilistic learning element as described in claim 1, additionally comprising means for providing a rating of confidence in said recognized next state.

3. A probabilistic learning element as described in claim 2, additionally comprising;

means for accumulating the ratings of confidence of the recognized states of the recognized state sequence; and

means, responsive to said accumulated ratings of confidence, for causing said means for storing to store the recognized state sequence as a previously learned sequence of states, and to store the objects, sequences of objects and states in the recognized state sequence and the predetermined types of knowledge relating to the objects, sequences of objects, states and sequences of states forming said recognized state sequence as statistical information relating to previously learned sequences of states when the accumulated ratings exceed a predetermined threshold level.

4. A probabilistic learning element as described in claim 1, additionally comprising learning supervision means, responsive to external reinforcement signals, for causing said means for storing to store the recognized state sequence as a previously learned sequence of states, and to store the objects, sequences of objects and states in the recognized state sequence and the predetermined types of knowledge relating to the objects, sequences of objects, states and sequences of states forming said recognized state sequence as statistical information relating to previously learned sequences of states.

5. A probabilistic learning element as described in claim 4, additionally comprising means for correcting a recognized state sequence prior to initiating an external reinforcement signal.

6. A probabilistic learning element as described in claim 1, additionally comprising:

means for providing a rating of confidence in said recognized next state;

learning supervision means, adapted to receive said rating of confidence and an external reinforcement signal, for providing an output signal in response to accumulated ratings of confidence of the recognized states of the recognized state sequence and the external reinforcement signal when either the accumulated ratings of confidence exceed a predetermined threshold level or an external reinforcement signal is received; and

means, responsive to the output signal from the learning supervision means, for causing said means for storing to store the recognized state sequence as a previously learned sequence of states, and to store the objects, sequences of objects, and states in the recognized state sequence and the predetermined types of knowledge relating to the objects, sequences of objects, states and sequences of states forming said recognized state sequence as statistical information relating to previously learned sequences of states.

7. A probabilistic learning element as described in claim 6, additionally comprising means for correcting a recognized state sequence prior to initiating an external reinforcement signal.

8. A probabilistic learning element as described in claim 1, wherein the predetermined types of knowledge that are stored include the number of occurrences of:

each stored object, each stored sequence of objects, each stored state and each stored sequence of states.

9. A probabilistic learning element as described in claim 8, wherein the predetermined types of knowledge that are stored additionally include state lengths and the number of their occurrences and sequenoes of state lengths and the number of their occurrences.

10. A probabilistic learning element as described in claim 9, wherein the predetermined types of knowledge that are stored additionally include state-length pairs and the number of their occurrences and sequences of state-length pairs and the number of their occurrences.

11. A probabilistic learning element as described in claim 1, wherein the means for correlating includes a first means for determining the probabilities that possible states will span an object sequence having a particular begin time and end time and second means for determining the probabilities of state-length pairs given the previous state-length pair context.

12. A probabilistic learning element as described in claim 11, additionally comprising means responsive to the previously mentioned probabilities for implementing an algorithm to provide probabilities of possible states, with a particular length that span an object sequence given the previous state-length pair context.

13. A probabilistic learning element as described in claim 1, wherein the means for storing stores information on a plurality of previously learned states and the objects contained therein, whereby several levels of context are stored and the means for correlating implements an nth order Markov process correlating several levels of stored context.

14. A method of recognizing a sequence of states from a sequence of inputted objects utilizing a probabilistic learning element, comprising the steps of:

correlating said sequence of inputted objects and predetermined types of knowledge relating to said sequence of inputted objects with stored information relating to previously learned states, objects and sequences of objects and predetermined types of knowledge relating to said previously learned states, objects and sequences of objects including the number of occurrences of each;

providing probabilities for possible next states in a sequence of states based on said correlations;

determining a most likely next state in the sequence of states each time a new object is received;

deriving from stored information a signal corresponding to the probability that a state has ended; and

outputting the most likely next state as a recognized next state in the sequence of recognized states in response to the end of state probability.