Transcript Trees, Scenario Generation

Scenario Generation
based on
Quantization
Moscow, September 2009
A. Pichler
Department of Statistics and
Decision Support Systems
Outline of this Talk
• Approximation of
Probability measures
• Quantization
• Trees, Scenario Generation
Comparison of Measures
Given 2 measures, how can we link them
and assign a single number to account
for distance?
  P1 c P2
maximum
(comonotone)

  P1  P2
product measure

  P1 a P2
minimum
(antimonotone)
Earth Mover Distance
Distance for Measures
As the initial space obeys a distance
function, we thus may compute
 d x, y  dx, dy 
 d x, y   dx, dy
p
for every marginal distribution.
 A  X   PA
 p
d P, Q  : inf  d x, y  dx, dy  :

 X  B  QA

... is a metric, metrizing the
weak topology.
Summary
 A  X   PA
 p
d P, Q  : inf  d x, y  dx, dy  :

 X  B  QA

r
cost function
Distribution with adapted
marginals
is a metric on measures,
metrizing the weak topology.
Approximation
• Proxy for Expectation reads
 dP   p  q
qQ
q
• and convergence is to be understood in
the weak (*) sense,
Pn  P   :  dPn   dP
Metrizable
• The weak Topology is metrizable
Pn  P   :  dPn   dP
Pn  P  d Pn , P   0
• Elaborated since 18th century
G. Monge
Outline of this Talk
• Approximation of Probability
Measures
• Quantization
• Trees, Scenario Generation
Approximation
• Approximation via Dirac Measures
P   p q q
qQ
1 q  A
 q A : 
0 q  A
• Well defined?
Pq  pq
q Q
Discrete Situation
p
d
 x, y  dx, dy
original
distribution
P   p q q
qQ
Approximation
Linking the Concepts
Questions:
1. Where to place qQ?
2. How to choose the weights
pq?
P
P   p q q
qQ
Comparison of distances
Example: Approximation of Gaussian Distribution
3
3
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
2
3
n 1
 -1

1
sup F x   n 1, i  F x 
n
i 1


2
2
1
3
2
1
d x, y 
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
d 2  x, y 
1
2
3
3
2
1
1
2
3
1
2
3
d 10 x, y 
Associated Region
1.0
0.8
1.2
1.0
0.6
0.8
0.4
0.6
0.4
0.2
0.2
3
2
1
1
2
3
3
-
2
-
1
-
1
2
min qQ d ( x, q) r
Associated with given sample points are the intervals
containing points being closest to the sample point.
3
Voronoi Diagram
Георгий Феодосьевич Вороной
Борис Николаевич Делоне
in 2 dimensions ...
2
5
1
3
7
6
4
13
8
9
14
10
12
15
11
16
(c) Mathematica
... and in 3 dimensions
Lemma
1
2


pq q 
 min qQ d x, q  Pdx  d r  P, q
Q

r
Let
 
pq : P X q
then
3
r
.
with
X   Xq
qQ


d r  P,  pq q     d  x, q Pdx 
 qQ
 qQ X q
Let Xq be Voronoi and
 
pq : P X q , then



d r  P,  pq q    min qQ d x, q Pdx
 qQ

Solution to 1
Questions:
1. How to choose the weights pq?
2. Where to place qQ?
Answer Part 1:
• Compute the Voronoi
Tessellation Xq and set
r
• The even
 
pq : P X q


r


d r  P,  pq q    min qQ d x, q  Pdx
 qQ

Towards Question 2
The problem of finding the best
supporting nodes (Q) now transforms
into the problem of minimizing the
functional f Q
f Q  :  min qQ d x, q  Pdx 
r


 d r  P,  pq q 
 qQ

r
Lloyd Algorithm
f Q  :  min qQ d x, q  Pdx 
r


 d r  P,  pq q 
 qQ

r
Lloyd Algorithm repeats 2 steps:
• for Q, compute Xq and
 
pq : P X q
• for Xq, compute
Q : arg min




d
x
,
q
P
dx

r
Xq
Example
Optimal
supporting
nodes and
Voronoi
Diagram for
the
Bivariate
Normal
Distribution
Selected Solutions
Optimal supporting nodes are known in a
few selected sitations only. They include
(r=1)
• Uniform distribution
2i  1
qi :
2n
• Exponential distribution
n2  n
qi : 2 log
n 1 i
Towards Question 2
Both solutions have the form (for a
function z)
 2i  1 
qi  z 

 n 
1.2
1.0
0.8
0.6
0.4
0.2
3
-
Differentiating gives (R, r= 1)
2
-
1
-
1
2
q q 
0  0  2 F q1   F  1 2 
 2 
q q 
 q  qi 1 
0  F  i 1 i   2 F qi   F  i

2
2




F... the
cumulative
distribution
function,
q q 
0  F  n 1 n   2 F qn   1
2


f... the density
3
Asymptotic, motivation
• For n increasing, the difference
equation transforms into the differential
equation
r  1z" f z   z'
z'
z  


f
1
1 r
r 1
2
f ' z   0
f z   const .

x dx     f

1
1 r
x dx
again...
If P has density ...
f
dimension
... then the supporting
nodes have (asymptotic) ~ f
density ...
As a consequence, tails
get higher attention if r
is chosen big enough.
d
d r
Solution to 2
Questions:
1. How to choose the weights pq?
2. Where to place qQ?
Answer Part 2:
• Solve related equations, or
• use, for example, Lloyd Algorithm
• Asymptotically, compute quantiles of ~ f
d
d r
Example
Example: Approximation
of Gaussian Distribution
1.0
0.8
0.6
0.4
z ~ r  1  N 0,1
0.2
3
3
2
1
d x, y 
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
d 2  x, y 
1
2
1
2
3
3
2
1
1
2
3
1
2
3
d 10 x, y 
Theorem (Zador):
The error of the best approximation
Vn,r P  : inf
Q n
 min d x, q Pdx
r
qQ
satisfies


d 
lim n Vn,r P   Qr 0,1    f

r
d
d
d
Qr 0,1  inf n Vn ,r 0,1
r
d


n


d
d r

d 

d
d r
d
Note: this theorem links P to a simple uniform distribution
and discloses the rate of convergence.
The Constant...
... has the following bounds
1

Qr 0,1
d

r
d
d
 B0,1d
d r
cube proxy
0.7
r
p
0.6
1  d 


r 
2 1 p 
r

  2  
d

upper/ lower bound
0.5
d
r
p
0.4
0.3
0.2
0.1
(l2 Norm, r =1)
5
10
15
dimension d
20
25
30
Outline of this Talk
• Approximation of Probability
measures
• Quantization
• Trees, Scenario Generation
A tree is a Quantizer
A tree is a special quantizer on the multidimensional
space
T
X :  X t
T
t 0
PT : F T  0,1
Xt-1
Xt
Xt+1
Assume, there exist stochastic kernels describing the
Pt 1 : X t  Ft 1  0,1
transition
Theorem
Suppose that
      d x , y 
 d P. | x , Q. | x Q dx   
t
d P .| x , P .| y
t
t
then

 
t
t
t

d P ,Q  d P ,Q e
t
t
0
0
t
t
T
 T
Xt-1
Xt
Xt+1
Note: the statement gives exact bounds if   0 (independent).
Note: May be used to explicitely construct a tree (scenario)
with a distance given in advance.
Outlook 2010+
> Scenario Reduction
>> Römisch
> Include Decisions at stage t
>> Pflug
> Applications and numerous
implementations
>> Hochreiter
> Portfolio Optimization
>> Kovacevic
Thanks For Your Attention.