Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
1999-04-07
2003-06-17
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Neural network
Learning task
C382S243000
Reexamination Certificate
active
06581047
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to methods and systems of prediction. The main object of the present invention is an extension of cognitive predicting methods on non-stationary processes.
2. The Prior Art
Every process can be viewed as a product of some entity's functioning. From that position, we may look at the process as the entity's output. We also may use the term object of prediction meaning the entity whose output shall be predicted. The binary process is frequently used for a representation of any other process that permits such mapping. All further descriptions will be done in view of the binary process prediction.
The majority of known methods, algorithms, and systems, which are capable of prediction of the entity's output, use a priori knowledge of that entity's properties. Typically, the entity's properties are described in the form of various types of mathematical models such as sets of algebraic, differential, integral, stochastic equations, and their combinations. The predicting systems that employ the entity's model span the wide range between the first attempts for extrapolation by Newton, Lagrange, etc. [G. A. Korn, 1961], and modern adaptive predictors [U.S. Pat. No. 5,424,942, 07/1995, 364#164, Dong,]. The degree of complexity of prediction rises continuously. The development of cognitive predicting algorithms was inspired by a problem of an accurate prediction for an entity that is not able to provide complete information about its varying parameters and structure. These algorithms use cloning of evolutionary principals of biological systems. They belong to a set of genetic algorithms whose theory Dr. J. Holland developed in 1975. There are important features that describe uniqueness of the predicting systems utilizing a genetic algorithm approach [J. Holland, 1975, J. R. Koza, 1992, U.S. Pat. No. 5,136,686, 08/1992, Koza, K. De Jong and W. Spears, 1993]:
Object of prediction is stationary or quasi-stationary
The process to be predicted, employs a binary string as its internal representation
A Genetic Algorithm Representative Schema is a set of predicting solutions that are functions of the process' argument. Every generation of such schema is a product of a multi-step optimization procedure that includes the Natural Selection Algorithm for an appropriate selection of the predicting solutions; Evolutionary Operators such as crossover, mutation, permutation, proportional reproduction, inversion, etc., for the new solutions generation; and a Fitness Function to be a measure of performance for each of those solutions
The representative schema optimization procedure acts on the specified interval of the binary process history to train the predicting system in recognizing of specifics of the process that is subjected to prediction
The predicting system produces a prediction of the forthcoming process element via calculating an output of the optimal predicting function at the next value of its argument.
A powerful extended genetic algorithm developed by J. Koza [U.S. Pat. No. 5,136,686, 08/1992] is a good material for a discussion of strengths and weaknesses of the genetic algorithm approach in the context of non-stationary process prediction. The J. Koza's genetic algorithm is nonlinear. It not only includes the natural selection method and evolutionary operators, but also breaks down a problem into a hierarchy of subordinating sub-problems. This algorithm is free of the uniformity constraint that requires keeping the same size for all members of the population of predicting solutions. The J. Koza's genetic algorithm was not specifically designed for prediction. In the most general form given in the patent disclosure, this algorithm has the following description. “The process of the present invention operates upon a population of entities which accomplish tasks and can vary in size and shape. Each iteration of the process comprises activating, selecting, choosing, performing, and adding. First, each entity activates to accomplish its goal and produces a result. Second, a value is associated with the result of each activation and assigned to the corresponding entity. Third, at least one entity having a relatively high associated value is selected. Next, an operation is chosen from crossover, fitness proportionate reproduction, mutation, or permutation. If crossover is chosen, then the selected entity performs the crossover operation. Crossover creates new entities by combining portions of at least one selected entity with portions of at least one another entity. Fitness proportionate reproduction retains the selected entity in the population. Mutation randomly alters a small random part of an entity. Permutation reorders the parts of an entity without a net gain or loss. Finally, the newly produced entities are added to the population.
“Many seemingly different problems can be reformulated into a problem requiring discovery of mathematical expression or computer program that produces some desired output for particular inputs. When viewed in this way, the process of solving these seemingly different problems becomes equivalent to searching a space of possible mathematical expressions or computer programs for a most fit individual mathematical expression or computer program.” Naturally, Dr. Koza suggested to use this algorithm for prediction of “. . . the future elements of a sequence of numbers from a sampling of early numbers from the sequence [U.S. Pat. No. 5,136,686, 08/1992, p. 221].”
A possible binary process element predicting system that corresponds to the described above genetic algorithm may be presented with a block diagram depicted on the FIG.
1
. The following conventions are present in the above illustration.
H
Binary Process Storage
PFG
Predicting Functions Generator
F
Predictor
&PHgr;
Fitness Function Operator
x(&tgr;)
binary process; &tgr; = (t
1
, t
2
, . . . , t
p
) - discrete
argument;
h[x(&tgr;), t
q
, t
r
]
Binary string of the binary process
history;
PF
Set of predicting functions
pf
opt
(&tgr;, t
q
, t
r
)
optimal predicting function
f(&tgr;) ≡ f(t
i+i
)
the state of an i + 1 element in the binary
process prediction; i < p - retrospective
prediction;
i ≧ p
actual prediction
There are two types of predicting procedures in the system. The first procedure is an actual predicting procedure. The second procedure is a retrospective predicting procedure. An operator F that has the following definition provides both procedures.
∀&tgr;=(
t
1
,t
2
, . . . , t
p
),&tgr;=
t
i
F[x
(&tgr;)]≡
f
(
t
i−1
) (1.1)
f
(
t
i+1
)=
x
(
t
i+1
)
“correct prediction”
t
i
=t
p
f
(
t
i+1
)−actual prediction
t
i
<t
p
f
(
t
i−1
)−retrospective prediction
Here t
p
is a value of the latest existing discrete argument &tgr;=(t
1
, t
2
, . . . , t
p
) of the binary process x(&tgr;). When the retrospective predicting procedure is active, it is assumed that the forthcoming element of the binary process is unknown. This procedure is used at the stage of genetic algorithm representative schema optimization. When the actual predicting procedure is active, it means that the forthcoming element of the binary process is really unknown. The discrete argument &tgr; of the binary process x(&tgr;) is not necessarily a time variable.
The binary process predicting system that is based on the described above genetic algorithm operates as follows. Each element of the binary process x(&tgr;) goes to the storage (H) where it becomes a binary string h[x(&tgr;),t
i
] element; t
i
is an observer's position point, i=1,2, . . . , p. The system selects an interval [t
q
,t
r
], t
q
<t
r
≲t
p
on that binary string. Then, the Predicting Functions Generator (PFG) inserts an initial population of the binary process' predicting functions pf
k
(&tgr;,t
q
,t
Raykhman Alexander M.
Vinarskiy Ilya
Inesa, Inc.
McCormick Paulding & Huber LLP
Starks, Jr. Wilbert L.
LandOfFree
Method for a sequential prediction of binary element's... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for a sequential prediction of binary element's..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for a sequential prediction of binary element's... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3087370