Information Technology Reference
In-Depth Information
6.
Parameter estimation problem
: Parameter estimation is the problem
of determining the parameters of a model given experimental data. Let us
consider the following model using exponential sums:
y
(
t
)=
x
1
exp(
−
x
2
t
)+
x
3
exp(
−
x
4
t
)+
x
5
exp(
−
x
6
t
)
In the real-world a series of measures (
t
i
,y
i
) is known and the aim is to
determine the
x
i
's such that every measure verifies the model. In the fol-
lowing let us compute the data by simulation. The series of timings is fixed
as
t
=(0
,
1
,
4
,
9
,
16
,
25
,
36
,
49
,
69
,
81
,
100). The exact parameter values are
defined by (10
,
1
,
5
,
0
.
1
,
1
,
0
.
01) and the
y
i
's are computed as
y
(
t
i
). Now let
us try to compute the parameters values in the box
−
10
3
,
10
3
]
10
3
,
10
3
]
10
3
,
10
3
]
[
−
×
[0
.
5
,
2]
×
[
−
×
[0
.
05
,
0
.
5]
×
[
−
×
[0
,
0
.
05]
.
The main idea is to combine terms from the same columns. Given the projec-
tion constraints
x
k
exp(
−
x
k
+1
t
i
)
∈
I
and
x
k
exp(
−
x
k
+1
t
j
)
∈
J
, the following
redundant constraint is derived:
x
k
exp(
−
x
k
+1
t
i
)
I
J
−
x
k
+1
t
i
)
I
J
exp(
div
−→
exp
−→
x
k
+1
t
j
)
∈
x
k
+1
t
j
)
∈
x
k
exp(
−
exp(
−
I
J
The redundant constraint may be used to reduce further the domain of
x
k
+1
.
Since
x
k
+1
occurs once the reduction may be computed by a direct interval
expression
x
k
+1
←
I
J
lin
−→
exp(
x
k
+1
t
j
−
x
k
+1
t
i
)
∈
exp((
t
j
−
t
i
)
x
k
+1
)
∈
t
i
)
−
1
can be evaluated only once. As a consequence the reduction is very cheap
since it needs evaluating three interval operations.
t
i
)
−
1
(
t
j
−
·
log(
I/J
). Furthermore the term (
t
j
−
Table 1 summarizes the results. In the table, Name denotes the problem and
n
stands for the number of constraints. The next columns present the computation
time in seconds and the number of boxes of the solving process for the classical
bisection algorithm, the bisection algorithm using term sharing and combination,
and the improvement on the number of boxes. A “?” stands for problems that
cannot be solved in less than one hour.
Term sharing transforms Brown's system as a gentle problem for consistency
techniques. There is clearly a great interest in sharing complex terms occurring in
many constraints. The improvement for Wood and Transistor is less impressive
since only small terms are shared among a subset of constraints. However, the
improvement is still more than one order of magnitude.
The product and extended product problems are eciently solved using term
combination. In this case, the constraints are simplified enough to greatly im-
prove constraint processing. The improvement is smaller for the estimation prob-
lem since the constraints to be combined are complex, and only small parts of
them are combined and simplified. Our approach is clearly very ecient for
problems with many small constraints having similar expressions. For the other
problems, it remains a technique of choice since the process of evaluating the
new constraints is cheap.
Search WWH ::
Custom Search