Transcript Meta-controlled Boltzmann Machine

A Modified
Meta-controlled Boltzmann Machine
Tran Duc Minh, Le Hai Khoi (*), Junzo Watada (**), Teruyuki Watanabe (***)
(*) Institute Of Information Technology-Viet Nam Academy of Science & Technology
(**) Graduate School of Information, Production and System, Waseda University, Japan
(***) Osaka Institute of Technology
03/2004
CONTENT
• Introduction
• The portfolio selection problem
• Inner behaviors of the Meta-controlled
Boltzmann machine
• A Modified Meta-controlled Boltzmann
machine
• Conclusion
2
Introduction
• H. Markowitz proposed a method to allocate an
amount of funds to plural stocks for investment
• Model of Meta-controlled Boltzmann Machine
• The ability of Meta-controlled Boltzmann
Machine in solving the quadratic programming
problem
3
The portfolio selection problem
n
Maximize
 m x
i 1
n
Minimize
i
i i
n

i 1 j 1
n
Subject to
m x
i 1
i i
ij
mi xi m j x j
 1 and
n
m
i 1
i
S
with mi  {0, 1}, i = 1, .., n
where ij denotes a covariance between stocks i and j, i is an expected return rate
of stock i, xi is investing rate to stock i, n denotes the total number of stocks
and S denotes the number of stocks selected, and finally, mi denotes a selection
variable of investing stocks.
4
The portfolio selection problem
Convert the objective function into the energy
functions of the two components that are Metacontrolling layer (Hopfield Network) and the
Lower-layer (Boltzmann Machine) as described
below:
n
1 n n
Meta-Controlling layer Eu    ij si s j  Ku  i si ,
2
Lower Layer
i 1 j 1
i 1
n
n
n
n

1 n n
El    ij xi x j  2 xi x j   2 xi  K l  i xi
2  i 1 j 1
i 1 j 1
i 1
i 1

where Ku, Kl are weights of the expected return rate for each layer and si is the
output value of the ith unit of the Meta-Controlling layer.
5
Algorithm of the Meta-controlled
Boltzmann machine
Step 1. Set each parameter to its initial value.
Step 2. Input the values of Ku and Kl.
Step 3. Execute the Meta-controlling layer.
Step 4. If the output value of a unit in the Meta-controlling layer is 1, add some
amount of value to the corresponding unit in the lower layer. Execute the
lower layer.
Step 5. After executing the lower layer the constant number of times, decreases
the temperature.
Step 6. If the output value is sufficiently large, add a certain amount of value to
the corresponding unit in the Meta-controlling layer.
Step 7. Iterate from Step 3 to Step 6 until the temperature reaches the restructuring
temperature.
Step 8. Restructure the lower layer using the selected units of the Meta-controlling
layer.
Step 9. Execute the lower layer until reaching at the termination.
6
Inner behaviors of the Metacontrolled Boltzmann machine
•
•
•
•
•
•
Some times, the Hopfield layer may converge to a local minimum but the
disturb values make it to get over
The changes of Meta layer’s energy function are very small, while the
lower layer’s energy function’s is quite large
The number of cycles to execute the Meta layer is much smaller than the
cycles for the lower layer
Similar to the simulated annealing that we will “try to go downhill most of
the time instead of always going downhill”
The time to converge is much shorter than a conventional Boltzmann
machine
All the neurons that are “encouraged” will be selected before the system
goes to the final computation.
7
Chart of behaviors of Meta-controlled Boltzmann Machine
Disturb back value = 80%
8
Chart of behaviors of Meta-controlled Boltzmann Machine
Disturb back value = 1 %
9
Comparison of computing time between a Conventional Boltzmann
machine and a Meta-controlled Boltzmann Machine (1286 units)
Co m p a r i s o n o f t h e c o m p u t i n g t i m e b e t we e n a
Co n v e n t i o n a l B o l t z m a n n M a c h i n e a n d a M e t a -
350
300
250
200
150
100
50
0
Conventional BM
0.00001
0.000012
0.000014
0.000018
0.000024
0.000036
0.000072
Meta-controlled BM
Temperature
Co m p u t i n g t i m e (s e c )
contr ol l ed Bol tz ma nn Ma chi ne
10
Some hints on accelerating the Metacontrolled Boltzmann machine
• Trying to use only a layer of Boltzmann
Machine, modify the algorithm of original
Boltzmann Machine by removing the
discouraged units before goes into final
computation.
• Modify the original Boltzmann Machine by
replacing deterministic neurons by stochastic
neurons since the disturb from the lower layer
to the upper layer may not be worth.
11
A Modified
Meta-controlled Boltzmann machine
Step 1. Set each parameter to its initial value.
Step 2. Input the values of Ku , Kl.
Step 3. Execute the Meta-controlling layer.
Step 4. If the output value of a unit in the Meta-controlling layer is 1, add
some amount of value to the corresponding unit in the lower layer.
Execute the lower layer.
Step 5. After executing the lower layer the constant number of times,
decreases the temperature.
Step 6. Iterate Step 4, 5 until the temperature reaches the restructuring
temperature.
Step 7. Restructure the lower layer using the selected units of the Metacontrolling layer.
Step 8. Execute the lower layer until reaching at the termination.
Algorithm of the Modified Meta-controlled Boltzmann machine
12
13
Actual Hopfield layer's energy function
790
730
670
610
550
490
430
370
310
250
190
130
70
-1
-1.5
-2
-2.5
-3
Timing
Actual Boltzmann layer's energy function
0.001385
0.00138
0.001375
0.00137
Timing
14
100
91
82
73
64
55
46
37
28
19
10
0.001365
1
Value
Value
-0.5
10
0
Comparing performance
9.2
9
8.8
8.6
8.4
8.2
8
7.8
7.6
T im e
HPBM
17
9
13
-1.0007
5
-1.00065
1
Energy values
S equence num ber
C om pare Energy values
18
15
12
9
6
3
T im e
M odified
HPBM
Seq
Seconds
C om pare tim e to converge
Energy
H PB M
-1.00075
Energy
M odified
H PB M
-1.0008
-1.00085
-1.0009
S equence num ber
15
CONCLUSION
• The trend of accelerating algorithms is focused mainly on
heuristic modification and numeric optimization technique,
i.e. toward the faster convergence of algorithms whereas
keeping the correctness for them.
• The Meta-controlled Boltzmann Machine can be used to
solve quadratic programming problems.
• Future works:
 Try the model with other quadratic programming problem.
 Evaluate the modified Meta-controlled Boltzmann Machine.
16
THANK YOU!
17