Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1999-04-27
2001-10-16
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C706S012000, C706S013000, C706S047000, C706S052000, C706S049000, C382S103000, C382S240000, C324S345000
Reexamination Certificate
active
06304833
ABSTRACT:
BACKGROUND OF THE INVENTION
(1) Field of the Invention
This invention is directed to a system and method for the efficient selection of hypotheses used in connection with mathematical modeling of the type used when estimating the motion of physical phenomena, for example, torpedoes, via the results of an evidential reasoner, and more particularly, to a system and method for assessing models of motion through a fluid, resulting in an acoustic signal, wherein the signal traverses an uncertain path and is received by sensors with uncertain biases in the presence of noise. Accordingly, a hypothesis selection criterion for use with the Dempster-Shafer (DS) frame of evidential reasoning that is both conceptionally simple and computationally efficient, is provided.
(2) Description of Prior Art
The Dempster-Shafer (DS) theory of evidential reasoning is one of several approaches for producing inferences from uncertain information. Its appeal for application to model assessment is that it intrinsically accommodates the expression of ignorance and naturally provides a convenient framework on which a Contact Management Model Assessment problem can be structured. The basic structure for DS evidential reasoning is the frame of discernment. Denoted by &thgr;, the frame of discernment is a set of mutually exclusive and exhaustive hypotheses:
&thgr;={
H
1
. . . H
N
} (1)
The power set is the set of all subsets in the frame of discernment and has
K=
2|&THgr;|−1 (2)
elements, where |&thgr;| is the cardinality of the set &thgr;, and the minus one accounts for the null set ø which is not considered a member of the power set in DS theory.
FIG. 4
illustrates a generic power set. A basic probability assignment (bpa) is assigned to each member of the power set, A
i
, and represents the belief that the hypotheses of A
i
are true. Denoted by m(A
i
), the individual bpa's are bounded between zero and one, while their sum is unity. Additionally, the measures of plausibility and support for each element can also be computed. The support for A
i
, denoted by s(A
i
), is the sum of the bpa's over all the subsets of A
i
, i.e.,
s
(
A
i
)
=
∑
a
⊆
A
i
m
(
a
)
(
3
)
where:
m=amount of bpa
a⊂A
i
=>summation over the entire power set
⊂=subset or equivalent
S(A
i
) represents the level of belief that directly supports the hypotheses of A
i
. The plausibility of A
i
, i.e. p(A
i
), is a measure of the lack of support in the complement of A
i
and is one minus the support in the complement of A
i
, i.e.,
p
(
A
i
)
=
1.0
-
S
(
A
i
)
=
∑
a
⋂
A
i
≠
φ
m
(
a
)
(
4
)
where ∩=intersection
In general, support is less than or equal to plausibility and both are bounded by zero and one. The uncertainty in assigning belief to the hypotheses contained in element A
i
is the difference between the plausibility and support. DS theory includes Bayesian probability as a special case when all belief is distributed among the singleton sets [H
1
], [H
2
], . . . , [H
N
]. If several bodies of evidence exist for a frame of discernment, the resulting beliefs can be combined using the DS combination rule,
m
c
(
A
i
)
=
1
a
∑
A
j
⋂
A
k
=
A
i
m
1
(
A
j
)
m
2
(
A
k
)
,
(
5
)
where m
1
(A
j
) and m
2
(A
k
) are the belief in A
j
and A
k
generated from two bodies of evidence represented in frames of discernment one and two, respectively. The term &agr; is the renormalization constant necessary to account for belief being placed into the null intersection Ø and is
α
=
1
-
∑
A
j
⋂
A
k
≠
φ
m
1
(
A
j
)
m
2
(
A
k
)
(
6
)
In both expressions, the indices j and k range over all the elements of the power set. DS combination rule is both commutative and associative. Compatibility relations, which are used to map belief in one frame of discernment to a different frame of discernment, are useful for combining belief that originates in dissimilar frames into belief in a common frame of discernment. The compatibility map defines the relationship between the elements of two frames of discernment &thgr;
A,B
where
&thgr;
A,B
⊂&thgr;
A
x&thgr;
B
(7)
and the compatibility mapping is defined by
C
A→B
(
A
k
)={
b
j
|(
a
1
,b
j
)&egr;&thgr;
A,B,
a
i
&egr;A
k
} (8)
where at least one pair (a
i
, b
j
) is specified for each of the A
K
in &thgr;
A
. With a network of compatibility relations, different frames of discernment can be linked together. The collection of frames of discernment and compatibility relations is called a gallery.
The prior art includes the various model selection processes, none of which are related to the Dempster-Shafer frame of evidential reasoning, which are discussed below.
U.S. Pat. No. 5,045,852 to Mitchell et al. discloses a system and method for maximizing data compression by optimizing model selection during coding of an input stream of data symbols. In the system and method, at least two models are run and compared, and the model with the best coding performance for a given-size segment or block of compressed data is selected such that only its block is used in an output data stream. The best performance is determined by 1) respectively producing comparable-size blocks of compressed data from the input stream with the use of the two, or more models and 2) selecting the model which compresses the most input data. In the preferred embodiment, respective strings of data are produced with each model from the symbol data and are coded with an adaptive arithmetic coder into the compressed data. Each block of compressed data is started by coding the decision to use the model currently being run and all models start with the arithmetic coder parameters established at the end of the preceding block. only the compressed code stream of the best model is used in the output and that code stream has in it the overhead for selection of that model. Since the decision as to which model to run is made in the compressed data domain, i.e., the best model is chosen on the basis on which model coded the most input symbols for a given-size compressed block, rather than after coding a given number of input symbols, the model selection decision overhead scales with the compressed data. Successively selected compressed blocks are combined as an output code stream to produce an output of compressed data, from input symbols, for storage or transmission. In Mitchell et al., the process disclosed always performs all the processing and chooses the best result after the processing is performed, without ranking which models produce the best results prior to processing.
U.S. Pat. No. 5,233,541 to Corwin et al. discloses an automatic target detection process. Accordingly, a data processing technique is provided for detecting, locating and identifying targets from a plurality of images generated by an imaging sensor such as an imaging lidar system. The process employs physical models of signals produced by target objects of interest. Such a model based detection system globally processes frames of data to determine the existence and location of component elements that characterize the target being modeled. Similar to Mitchell et al., the process disclosed in Corwin et al. chooses only the best result after all processing is finished instead of ranking and selecting models which could produce the best results, prior to processing. Also, the model developed by Corwin et al. is of a target's orientation in a still frame, thereby not taking into account target kinematics, environmental conditions and sensor characteristics.
The prior art discussed above relies strictly on Bayesian approaches, and unlike the present invention, it is not a selection method which is applicable to a broad range of systems such as the Bayesian system, the Dempster-Shafer syste
Ferkinhoff David J.
Gong Kai F.
Hammel Sherry E.
Nardone Steven C.
Lall Prithvi C.
McGowan Michael J.
Oglo Michael F.
Phan Thai
Teska Kevin J.
LandOfFree
Hypothesis selection for evidential reasoning systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hypothesis selection for evidential reasoning systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypothesis selection for evidential reasoning systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2592749