Transcript Physics Fluctuomatics / Applied Stochastic Process 2012-01

Physical Fluctuomatics
Applied Stochastic Process
1st Review of probabilistic information processing
Kazuyuki Tanaka
Graduate School of Information Sciences
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
Webpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/PhysicalFluctuomatics/2012/
Physical Fuctuomatics (Tohoku
University)
1
Textbooks
Kazuyuki Tanaka: Introduction of Image
Processing by Probabilistic Models, Morikita
Publishing Co., Ltd., 2006 (in Japanese) .
Kazuyuki Tanaka: Mathematics of Statistical
Inference by Bayesian Network, Corona
Publishing Co., Ltd., 2009 (in Japanese).
Physical Fuctuomatics (Tohoku
University)
2
References of the present lecture
K. Tanaka: Statistical-mechanical approach to image
processing (Topical Review), Journal of Physics A:
Mathematical and General, vol.35, no.37, pp.R81-R150, 2002.
Y. Kabashima and D. Saad: Statistical mechanics of lowdensity parity-check codes (Topical Review), J. Phys. A, vol.37,
no.6, pp.R1-R43, 2004.
H. Nishimori: Statistical Physics of Spin Glasses and
Information Processing, ---An Introduction, Oxford University
Press, 2001.
M. Opper and D. Saad D (eds): Advanced Mean Field Methods
--- Theory and Practice, MIT Press, 2001.
C. M. Bishop: Pattern Recognition and Machine Learning,
Springer, 2006.
M. J. Wainwright and M. I. Jordan: Graphical Models,
Exponential Families, and Variational Inference, now
Publishing Inc, 2008.
M. Mezard, A. Montanari: Information, Physics, and
Computation, Oxford University Press, 2009.
Physical Fuctuomatics (Tohoku
University)
3
Benefit of Information &
Communications Technology
Ubiquitous Computing
Ubiquitous Internet
Benefit of Information & Communications Technology
Demand for Intelligence
It cannot be satisfied only with it being only cheap
and being quick.
Physical Fuctuomatics (Tohoku
University)
4
Field of Information Processing
Information processing for numerical calculations
Definite Procedure has been given for each calculation.
Information processing according to theories
Inference from propositions
Realization by progress of computational processing capacity
Information processing in real world
Diversity of reason in phenomenon
Compete data is not necessarily obtained.
It is difficult to extract and select some important
information from a lot of data.
Uncertainty caused by the gap of knowing simply and
understanding actually.
We hope to deal successfully
with such uncertainty.
Physical Fuctuomatics (Tohoku
University)
5
Computer for next generations
Required Capacity
Capability to sympathize with a user （Knowledge)
Capability to put failure and experience to account in
the next chance （Learning）
How should we deal successfully with the uncertainty caused
by the gap of knowing simply and understanding actually?
Formulation of knowledge and uncertainty
Realization of information processing data with
uncertainty
Physical Fuctuomatics (Tohoku
University)
6
Computational model for information
processing in data with uncertainty
Mathematical expression of uncertainty
=>Probability and Statistics
Probabilistic Inference
modeling
Probabilistic model
with graphical structure
（Bayesian network）
Medical diagnosis
Failure diagnosis
Node is random variable.
Risk Management Arrow is conditional probability.
Inference system for data with uncertainty
Graph with cycles
Probabilistic information processing can give us unexpected
capacity in a system constructed from many cooperating
elements with randomness.
Important aspect
Physical Fuctuomatics (Tohoku
University)
7
Computational Model
for Probabilistic Information Processing
Bayes Formula
Probabilistic
Information Processing
Probabilistic Model
Algorithm
Monte Carlo Method
Markov Chain Monte Carlo Method
Randomized Algorithm
Genetic Algorithm
Approximate Method
Belief Propagation
Mean Field Method
Physical Fuctuomatics (Tohoku
University)
Randomness and
Approximation
8
Probabilistic Image Processing
K. Tanaka: J. Phys. A, vol.35, 2002.
A. S. Willsky: Proceedings of IEEE, vol.90, 2002.
Noise Reduction by
Probabilistic Image
Processing
The elements of such a
digital array are called pixels.
At each point, the intensity
of light is represented as an
integer number or a real
number in the digital image
data.
192
202
190
202
219
120
100
218
110
Conventional Filter
192 202 190


Average202 219 120  173
100 218 110


192
202
190
202
173
120
100
218
110
Modeling of Probabilistic Image Processing based on Conventional Filters
Markov Random Filed Model
Algorithm
Physical Fuctuomatics (Tohoku
University)
Probabilistic Image
Processing
9
Probabilistic Image Processing
K. Tanaka: J. Phys. A, vol.35, 2002.
A. S. Willsky: Proceedings of IEEE, vol.90, 2002.
Degraded Image (Gaussian Noise）
Probabilistic Image Processing
MSE:520
MSE: 2137
Lowpass Filter
MSE:860
Wiener Filter
MSE:767
Physical Fuctuomatics (Tohoku
University)
Median Filter
MSE:1040
10
Error Correcting Code
Y. Kabashima and D. Saad: J. Phys. A, vol.37, 2004.
010
000001111100000
error
001001011100001
code
majority rule
Error Correcting Codes
0
1
0
decode
010
Parity Check Code
Turbo Code, Low Density Parity Check (LDPC) Code
High Performance Decoding Algorithm
Physical Fuctuomatics (Tohoku
University)
11
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 9  X 3  X 4  X 6 (mod2)
 x1   1 
   
 x2   1 
 x  0
 3 
 x4   0 
x   
 5  1
 x  1
 6  
14 January, 2010
Hokkaido University GCOE Tutorial
(Sapporo）
12
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 7  1  1  0 (mod 2)  0
X 9  X 3  X 4  X 6 (mod2)
X 9  0  0  1 (mod 2)  1
X 8  1  0  1 (mod 2)  0
 x1   1 
   
 x2   1 
 x  0
 3 
 x4   0 
x   
 5  1
 x  1
 6  
14 January, 2010
Hokkaido University GCOE Tutorial
(Sapporo）
13
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 7  1  1  0 (mod 2)  0
X 9  X 3  X 4  X 6 (mod2)
X 9  0  0  1 (mod 2)  1
 x1   1 
   
 x2   1 
 x  0
 3 
 x4   0 
x   
 5  1
 x  1
 6  
14 January, 2010
X 8  1  0  1 (mod 2)  0
 x1   1 
   
 x2   1 
 x  0
 3  
 x4   0 
x   
 5   1
 x6   1 
   
 x7   0 
 x  0
 8   
Code Word  x9   1 
Hokkaido University GCOE Tutorial
(Sapporo）
14
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 7  1  1  0 (mod 2)  0
X 8  1  0  1 (mod 2)  0
X 9  X 3  X 4  X 6 (mod2)
 x1   1 
   
 x2   1 
 x  0
 3 
 x4   0 
x   
 5  1
 x  1
 6  
14 January, 2010
X 9  0  0  1 (mod 2)  1
1 p
1
1
 x1   1 
   
p
 x2   1 
0
 x  0
 3    Binary Symmetric
 x4   0 
Channel
x   
 5   1
p 1
 x6   1 
0
   
 x7   0 
 x  0 1  p
0
 8   
Code Word  x9   1 
Hokkaido University GCOE Tutorial
(Sapporo）
Received Word
 y1   1 
   
 y2   1 
 y  1
 3  
 y4   0 
y   
 5   1
 y6   1 
   
 y7   1 
 y  0
 8   
 y9   1 
15
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 9  X 3  X 4  X 6 (mod2)
14 January, 2010
Hokkaido University GCOE Tutorial
(Sapporo）
16
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 9  X 3  X 4  X 6 (mod2)
14 January, 2010
Hokkaido University GCOE Tutorial
(Sapporo）
17
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 9  X 3  X 4  X 6 (mod2)
14 January, 2010
Hokkaido University GCOE Tutorial
(Sapporo）
18
Error Correcting Codes and
Belief Propagation
X 7  X 1  X 2  X 3 (mod2)
X 8  X 2  X 3  X 5 (mod2)
X 9  X 3  X 4  X 6 (mod2)
Fundamental Concept for Turbo Codes and LDPC Codes
14 January, 2010
Hokkaido University GCOE Tutorial
(Sapporo）
19
CDMA Multiuser Detectors in Mobile Phone Communication
T. Tanaka, IEEE Trans. on Information Theory, vol.48, 2002
Relationship between mobile phone communication
and spin glass theory
Noise
Signals of
User A
Wireless
Communication

Spreading Code
Sequence
Coded
Signals of
User A
Spreading Code
Sequence

Decode
Coded Signals
of Other Users Received Data
Physical Fuctuomatics (Tohoku
University)
Probabilistic model for
decoding can be
expressed in terms of a
physical model for spin
glass phenomena
20
Artificial Intelligence
Bayesian Network
J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of
Plausible Inference (Morgan Kaufmann, 1988).
AC
AR
AS
AW
Probabilistic inference system
Practical algorithms
by means of belief
propagation
Physical Fuctuomatics (Tohoku
University)
21
System of a lot of elements with mutual relation
Common Concept between Information Sciences and Physics
Main Interests
Information Processing:
Data
Physics:
Material,
Natural Phenomena
Some physical concepts
in Physical models are
useful for the design of
computational models in
probabilistic
information processing.
Data is constructed from many bits
０,1
Bit
101101
110001
01001110111010
10001111100001
10000101000000
11101010111010
1010
Data
A sequence is formed by deciding the arrangement of bits.
A lot of elements have mutual relation of each other
Materials are constructed from a lot of molecules.
Molecule
Material
Molecules have interactions of each other.
Physical Fuctuomatics (Tohoku
University)
22
Horizon of Computation
in Probabilistic Information Processing
Compensation of expressing uncertainty
using probability and statistics
It must be calculated by taking account of both events
with high probability and events with low probability.
Computational Complexity
It is expected to break throw the computational
complexity by introducing approximation algorithms.
Physical Fuctuomatics (Tohoku
University)
23
What is an important point in
computational complexity?
How should we treat the
calculation of the
summation over 2N
configuration?
a  0;
for(x1  T or F){
for(x2  T or F){
    f x , x ,, x 
x1 T,F x2 T,F
xN T,F
1
2
N
If it takes 1 second in the case of
N=10, it takes 17 minutes in
N=20, 12 days in N=30 and 34
years in N=40.

for(x N  T or F){
a  a  f  x1 , x2 , , xL ;
}

}
}
Physical Fuctuomatics (Tohoku
University)
N fold loops
24
Why is a physical viewpoint effective in probabilistic
information processing?
Matrials are constructed from a lot of molecules.
23
(10 molecules exist in 1 mol.)
Molecules have intermolecular forces of each other
 f x , x ,, x 
1
x1
x2
2
N
xN
Theoretical physicists always have to
treat such multiple summation.
Development of Approximate Methods
Probabilistic information processing is also usually reduced
to multiple summations or integrations.
Application of physical approximate methods
to probabilistic information processing
Physical Fuctuomatics (Tohoku
University)
25
Academic Circulation between
Physics and Information Sciences
Statistical
Mechanical
Informatics
Common Concept
Academic
Circulation
Understanding and prediction
of properties of materials and
natural phenomena
Physics
Statistical
Sciences
Probabilistic
Information
Processing
Academic
Circulation
Extraction and processing of
information in data
Information Sciences
Physical Fuctuomatics (Tohoku
University)
26
Summary of the present lecture
Probabilistic information processing
Examples of probabilistic information processing
Common concept in physics and information sciences
Application of physical modeling and approximations
Future Lectures
Fundamental theory of probability and statistics
Linear model
Graphical model
.
.
.
Physical Fuctuomatics (Tohoku
University)
27