Transcript Document

Design of Experiments
------Morris Method
Yaomin Jin
01-03-2002
Outline of the presentation




Introduction of screening technique
Morris method
Examples
Conclusions
Screening technique

large-scale models

requirement of considerable computer time for each run

depend on a large number of input variables
Input
factors
x1
x2
x3
…
xk
Model
Output
y=f(x1,x2,…,xk)
Which factor is important?
Morris method(1991)



OAT(one factor at a time)
the baseline changes at each step wanders in
the input factors space
Estimate the main effect of a factor by computing
r number of local measures at x1,x2,…xr in the
input space then take average.
Elementary effects

Reduce the dependence on the specific
point that a local experiment has.

Determine which factor have:

negligible effects
linear and additive effects
non-linear and interaction effects


Elementary effects



k dimensional factors vector x for the
simulation model has components xi that have
p-values in the set {0, 1/(p-1),…,1}
The region of the experiment is a k
dimensional p level grid. In practical
applications, the values sampled in are
subsequently rescaled to generate the actual
values of the simulation factors.
Δ=1/(p-1).
Elementary effects
of i-th factor at given point x
di ( x) 
[ y ( x1 , x2 ,..., xi 1 , xi  , xi 1 ,..., xk )  y ( x)]
where x is any value in  selected such that the perturb x 
point is still in  . A finite distribution Fi of elementary
effects for the i-th input factor is obtained by sampling x
from  . The number of elements of each Fi is p [ p  ( p 1)]
k 1
Economy of Morris method

In the simplest form, the total computational effect
required for a random sample of r values from
each distribution Fi is n=2rk runs. Each
elementary effect requires the evaluation of y
twice.
 Economy of

design 
# of elementary effects estimated by the design
# of runs
The simplest form of Morris design has an
economy rk/2rk=1/2.
Economical design
Based on the construction of a matrix B* with rows that
represent input vectors x, for which the corresponding
experiment provides k elementary effects (one for each input
factor) from k+1 runs. Economy of the design is k/(k+1).
assume that p is even and  p /[2( p 1)] , each of the p [ p  ( p 1)]  p 2
elementary effects for the i-th input factor has equal probability
of being selected. The key idea is:
Base value x* is randomly chosen from the vector x, each
component xi being sampled from the set 0, 1(p-1) ,...,1- 
One or more of the k components of x* are increased by such
that vector x(1) still in 
k 1
k
Economical design (continue)
The estimated elementary effect of the i-th component
of x(1) (if the i-th component of x(1) has been changed
by )
[ y ( x , x ,..., x , x  , x ,..., x )  y( x )]
d (x ) 
if x(1) increased by Δ;
(1)
(1)
1
(1)
2
(1)
i 1
(1)
i
(1)
i 1
(1)
k
(1)
i
di ( x ) 
(1)
(1)
(1)
(1)
[ y( x (1) )  y( x1(1) , x2(1) ,..., xi(1)
1 , xi  , xi 1 ,..., xk )]
if x(1) decreased by Δ.
Let x(2) be the new vector ( x ,..., x , x  ,..., x ,) select a
third vector x(3) such that differs from x(2) only one
component j:
(3)
(2)
(1)
1
xj  xj , j  i
(1)
i 1
(1)
i
(1)
k
Economical design (continue)
d j ( x (2) ) 
[ y ( x (3) )  y( x (2) )]
else
d j ( x (2) ) 
[ y ( x (2) )  y ( x (3) )]
Repeat the upper step get the k+1 input vectors
x(1),x(2),…,x(k+1) , any component i of x* is selected at least
once to be increased by . To estimate one elementary
effect for each factor.
Economical design (continue)
The rows of orientation matrix B* are the vectors
x , x ,..., x
describe above. This provides a single
elementary effect per factor.
To build B*,
 p
 2  p  1 
Restrict attention: a. p is even; b.
Firstly, selection of sampling matrix B with
elements that are 0 or 1, such that every column there are
two rows of that differ in only one element.
(1)
(2)
( k 1)
Economical design (continue)
0
1

B  1

...
 1
0
0
1
...
1
0 ... 0 
0 ... 0 
0 ... 0 

... ... ...
1 ... 1  ( k 1)k
In particular, B may be chosen to be a strictly lower
triangular matrix of 1, consider B’ given by
Economical design (continue)
B '  J k 1,1 X  B
*
Jk+1,1 is a matrix of 1. B as a design matrix(i.e. each row a value for
x)
x* is randomly chosen base value of x. B’ could be used as a design
matrix. Each element is randomly assigned a value from
0, 1 (p-1) ,...,1-  with equal probability.
Since it would provide k elementary effects; one effect each input
factor, with a computation cost of k+1 runs. However the problem is that
the k elementary effects B’ produces would not be randomly selected.
Economical design (continue)
A randomised version of the design matrix is given by
B*  ( J k 1,1 x* 
 
 2B  J k 1,k  Dk*,k  J k 1,k  Pk*,k

2 
where
•D* is diagonal matrix in which each diagonal element is either +1
or -1
•P* is random permutation matrix, in which each column contains
one element equal to 1 and all the others equal to 0, and no two
columns have 1’s in the same position
•B* provides one elementary effect per factor that is randomly
selected.
Example
Suppose that p=4, k=4 and  2 3 , that is, four factors
that may have values in the set {0,1/3,2/3, 1}. Then
B5*4 is given by
0 0 0 0 
1 0 0 0 


B  1 1 0 0 


1 1 1 0 
1 1 1 1 
Example (continue)
and the randomly generated x*, D* and P* happen to be
1
1
x*  (0, , 0, )
3
3
 1 0 0
0 1 0
D*  
 0 0 1

0 0 0
0
0 
0

1
0
0
P*  
0

1
0
0
1
0
1
0
0
0
0
1 
0

0
Example (continue)


0

*
2   2 B  J k 1,k  D  J k 1,k    0

0
 0
0

0




0

0
2
3

0 0

0  
0  0
 
0 
   0


 0

0
0
2
3
2
3
2
3
2
3
2
3
2
3
0
0

0

0


0


0

2

3 
Example (continue)
1
3

1
3

1
B*  
3
1

3

1



1
1
1
1
3
1
3
1
1
3
1
3
1
3
1
3
1
3

1
3

1


1


1


1
1
1 1 1
1 1
1 1 1
1 1
x (1)  ( ,1,1, ), x (2)  ( ,1, , ), x (3)  ( ,1, ,1), x (4)  ( , , ,1), x (5)  (1, , ,1).
3
3
3 3 3
3 3
3 3 3
3 3
Elementary effects
To estimate the mean and variance of the distribution
Fi(i=1,…,k), take a random sample of r elements;
that is sample r mutually independent orientation
matrices. Since each orientation matrix provides one
elementary effect for every factor, the r matrices
together provide r×k dimensional samples, one for
each Fi(i=1,…,k). We use the classic estimate for
every factor’s mean and standard deviation.
Elementary effects
The characterization of the distribution Fi through its
mean and standard deviation gives useful
information about the influence on the output;
 a high mean indicates a factor with an important
overall influence on the output,
 a high standard deviation indicates either a factor
interacting with other factors or a factor whose
effect is non-linear.
Standard of importance
di  
2 Si
The lines constituting a wedge, are described by
r ;
where Si / r is the standard deviation of the mean
elementary effect. If the parameter has coordinates
2S
below the wedge, i.e. | d | r , this is a strong indication
that the mean elementary effect of the parameter is nonzero. A location of the parameter coordinates above the
wedge indicates that interaction effects with other
parameters or non-linear effects are dominant.
Example 1
f  10x1  25x2  40x3  75x4
Result of example 2
(p=4, Δ=2/3 and r=4)
Example 2
10
10
10
i
i j
i  j l
y   0   i wi   i , j wi w j   i , j ,l wi w j wl 
10

i  j l  s
i , j ,l ,s wi w j wl ws
where wi=2(xi-0.5) except for i=3,
wi=2(1.1xi/(xi+0.1)-0.5), otherwise.
Coefficients of relatively large value were assigned as
i  20,
i  1,...,5,
i , j  15,
i, j  1, 2,3
i, j ,l  10,
i, j, l  1, 2,3
i, j ,l ,s  5,
i, j, l  1, 2,3, 4
}
}
i , i , j ~ N (0,1)
i, j ,l , i, j ,l ,s  0, others
Result of example 2
(from graph)
•Input 1-5 are clearly separated from the cluster of
remaining outputs, which have means and standard
deviations close to 0.
•In particular, inputs 4,5 have mean elementary effects
that are substantially different from 0 while having small
deviations.
•Consider both means and standard deviations together,
we conclude that the first 5 inputs are important, and that
of these the first three appear to have effects that involve
either curvature or interactions.
•This is coincide with the model.
Conclusions




Economical for models with a large numbers
of parameters
Does not dependent on any assumptions
about the relationship between parameters
and outputs
Results are easily explained in a graph
Drawback is not consider the dependencies
between parameters(such as interactions)