Transcript Fractals and BBN Inference - Kansas State University

KDD Group Presentation
Fractal and Bayesian Networks Inference
Saturday, Oct. 12, 2001
Haipeng Guo
KDD Research Group
Department of Computing and Information Sciences
Kansas State University
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Presentation Outline
• Simple Tutorial on Fractals
• Bayesian Networks Inference Review
• Joint Probability Space’s Fractal Property and its
Possible Application to BBN Inference
• Summary
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Part I
Introduction to Fractals
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Fractals Introduction
•
•
•
•
Definition
Examples: Man-made & Nature Fractals
Fractal Dimension
Fractal Applications
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Fractal – “broken, fragmented, irregular”
“I coined fractal from the Latin adjective fractus. The corresponding
Latin verb frangere means "to break" to create irregular fragments. It is
therefore sensible - and how appropriate for our need ! - that, in
addition to "fragmented" (as in fraction or refraction), fractus should
also mean "irregular", both meanings being preserved in fragment. ”
B. Mandelbrot :
The fractal Geometry of Nature, 1982
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Definition: Self-similarity
– A geometric shape that has the property of self-similarity, that is,
each part of the shape is a smaller version of the whole shape.
Examples:
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Mathematical fractal: Konch Snowflake
•
Step One.
Start with a large equilateral triangle.
• Step Two.
Make a Star.
1. Divide one side of the triangle into
three parts and remove the middle section.
2. Replace it with two lines the same
length as the section you removed.
3. Do this to all three sides of the triangle.
• Repeat this process infinitely.
•
The snowflake has a finite area bounded
by a perimeter of infinite length!
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Real world fractals
A cloud, a mountain, a flower, a tree
or a coastline…
The coastline of Britain
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Fractal geometry: the language of nature
• Euclid geometry: cold and dry
• Nature: complex, irregular, fragmented
“Clouds are not spheres, mountains are not
cones, coastlines are not circles, and bark is
not smooth, nor does lightning travel in a
straight line.”
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Euclid dimension
• In Euclid geometry, dimensions of objects are
defined by integer numbers.
• 0 - A point
• 1 - A curve or line
• 2 - Triangles, circles or surfaces
• 3 - Spheres, cubes and other solids
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Fractal dimension
• Fractal dimension can be non-integers
• Intuitively, we can represent the fractal dimension
as a measure of how much space the fractal
occupies.
• Given a curve, we can transform it into 'n' parts (n
actually represents the number of segments), and
the whole being 's' times the length of each of the
parts. The fractal dimension is then :
d = log n / log s
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Example: Knoch snowflake
• After the first step, we get four
segments(it's then divided into 4 parts).
• The whole curve is composed of three
of these new segments.
• So, the fractal dimension is :
d=log 4/log 3=1.2618...
• It takes more space than a
1 dimensional line segment,
but it occupies less space than a
filled two-dimensional square.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Another example: Cantor Set
•
The oldest, simplest, most famous fractal
1 We begin with the closed interval [0,1].
2 Now we remove the open interval (1/3,2/3);
leaving two closed intervals behind.
3 We repeat the procedure, removing
the "open middle third" of each
of these intervals
4 And continue infinitely.
•
•
•
Fractal dimension:
D = log 2 / log 3 = 0.63…
Uncountable points, zero length
Challenge problem: is ¾ in Cantor set?
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Devil’s staircase
•
•
•
•
Take a Cantor Set, which is composed of an infinite number of points.
Consider turning those points into dots and letting a Pacman eat them
As our Pacman eats the dots, he gets heavier. Imagine that his weight after
eats all the dots is 1.
Graph his weight with time, we get devil’s staircase.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Cantor square
• Fractal dimension: d = log 4 / log 3 = 1.26
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
The Mandelbrot Set
• The Mandelbrot set is a connected set of points in the complex plane
• Calculate: Z1 = Z02 + Z0, Z2 = Z12 + Z0, Z3 = Z22 + Z0
• If the sequence Z0, Z1, Z2, Z3, ... remains within a distance of 2 of the
origin forever, then the point Z0 is said to be in the Mandelbrot set.
• If the sequence diverges from the origin, then the point is not in the set
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Colored Mandelbrot Set
• The colors are added to the points that are not
inside the set. Then we just zoom in on it
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Applications of fractals
• Astronomy: the struture of our universe
• Superclusters - clusters – galaxies- star systems(Solar system) planets - moons
• Every detail of the universe shows the same clustering patterns.
• It can be modeled by random Cantor square
• The fractal dimension of our universe: 1.23
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Applications of fractals
• Rings of Saturn
•
•
•
•
•
Originally, it was believed that the ring is a single one.
After some time, a break in the middle was discovered, and scientists
considered it to have 2 rings.
However, when Voyager I approached Saturn, it discovered that the two ring
were also broken in the middle, and the 4 smaller rings were broken as well.
Eventually, it identified a very large number of breaks, which continuously
broke even small rings into smaller pieces.
The overall structure is amazingly similar to... Cantor Set
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Application of Fractals
• Human Body
THE LUNGS:
•
•
Formed by splitting lines
Fractal Canopies
The brain:
•
•
The surface of the brain contains a large number of folds
Human, the most intelligent animal, has the most folded
surface of the brain
• Geometrically, the increase in folding means the increase
in dimension
• In humans, it is obviously the highest, being as large as
between 2.73 - 2.79
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Plants
• a tree branch looks similar to the entire tree
• a fern leaf looks almost identical to the entire fern
• One classic way of creating fractal plants is by means of lsystems(Lindenmayer)
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Bacteria Cultures
• A bacteria culture is all bacteria that originated from a single ancestor
and are living in the same place.
• When a culture is growing, it spreads outwards in different directions
from the place where the original organism was placed.
• The spreading of bacteria can be modeled by fractals such as the
diffusion fractals
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Data Compression
• A color full-screen GIF image of Mandelbrot Set occupies about 35
kilobytes
• Formula z = z^2 + c, 7 bytes! (99.98% )
• It could work for any other photos as well
• The goal is too find functions, each of which produces some part of
the image.
• IFS (Iterated function system) is the key.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Weather
• Weather behaves very unpredictably
• Sometimes, it changes very smoothly. Other times, however, it
changes very rapidly
• Edward Lorenz came up with three formulas that could model the
changes of the weather.
• These formulas are used to create a 3D strange attractor, they form
the famous Lorenz Attractor, which is a fractal pattern.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Fractal Antenna
• Practical shrinkage of 2-4 times are realizable for
acceptable performance.
• Smaller, but even better performance
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Electronic Transmission Error
•
•
•
•
During electronic transmissions, electronic noise would sometimes interfere with the
transmitted data.
Although making the signal more powerful would drown out some of this harmful noise,
some of it persisted, creating errors during transmissions.
Errors occurred in clusters; an period of no errors would be followed by a period with
many errors.
On any scale of magnification(month, day, hour, 20 minutes, …), the proportion of errorfree transmission to error-ridden transmission stays constant.
• Mandelbrot studied the mathematical process that enables us to create random
Cantor dust describing perfectly well the fractal structure of the batches of
errors on computer lines
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Network Traffic Model
Packets delays gain as a function of time in a WAN environment:
• the top diagram - absolute values of RTT parameter in virtual
channel;
• the bottom diagram - fractal structure of packets flow that
excessed 600 msec threshold.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Fractal Art
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Fractal Summary
•
•
•
•
•
Fractals are self-similar or self-affine structures
Fractal object has a fractal dimension
It models many natural objects and processes.
It is the nature’s language.
It has very broad applications.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Part II
Bayesian Networks
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Bayesian Networks Review
•
•
•
•
Bayesian Networks
Examples
Belief Update and Belief Revision
The joint Probability Space and Brute Force
Inference
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Bayesian Networks
• Bayesian Networks, also called Bayesian Belief networks, causal
networks, or probabilistic networks, are a network-based
framework for representing and analyzing causal models involving
uncertainty
• A BBN is a directed acyclic graph (DAG) with conditional
probabilities for each node.
–
–
Nodes represent random variables in a problem domain
Arcs represent conditional dependence relationship among these
variables.
– Each node contains a CPT(Conditional Probabilistic Table) that
contains probabilities of this node being specific values given the
values of its parent nodes.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Family-Out Example
•
" Suppose when I go home at night, I want to know if my family is home before I try the
doors.(Perhaps the most convenient door to enter is double locked when nobody is home.) Now,
often when my wife leaves the houses, she turns on an outdoor light. However, she sometimes turns
on the lights if she is expecting a guest. Also, we have a dog. When nobody is home, the dog is put in
the back yard. The same is true if the dog has bowel problems. Finally, if the dog is in the back yard, I
will probably hear her barking(or what I think is her barking), but sometimes I can be confused by
other dogs. "
Family-Out
Light-On
Bowel-problem
Dog-out
Hear-bark
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Asia Example from Medical Diagnostics
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Why is BBN important?
• Offers a compact, intuitive, and efficient graphical representation
of dependence relations between entities of a problem domain.
(model the world in a more natural way than Rule-based systems
and neural network)
• Handle uncertainty knowledge in mathematically rigorous yet
efficient and simple way
• Provides a computational architecture for computing the impact of
evidence nodes on beliefs(probabilities) of interested query nodes
• Growing numbers of creative applications
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Alarm Example: the power of BBN
•
The Alarm network
37 variables, 509 parameters (instead of 237)
MINVOLSET
PULMEMBOLUS
PAP
KINKEDTUBE
INTUBATION
SHUNT
VENTMACH
VENTLUNG
DISCONNECT
VENITUBE
PRESS
MINOVL
ANAPHYLAXIS
SAO2
TPR
HYPOVOLEMIA
LVEDVOLUME
CVP
PCWP
VENTALV
PVSAT
ARTCO2
EXPCO2
INSUFFANESTH
LVFAILURE
STROEVOLUME
FIO2
CATECHOL
HISTORY
ERRBLOWOUTPUT
CO
HR
HREKG
ERRCAUTER
HRSAT
HRBP
BP
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Applications
•
•
•
•
•
•
•
•
•
Medical diagnostic systems
Real-time weapons scheduling
Jet-engines fault diagnosis
Intel processor fault diagnosis (Intel);
Generator monitoring expert system (General
Electric);
Software troubleshooting (Microsoft office
assistant, Win98 print troubleshooting)
Space shuttle engines monitoring(Vista project)
Biological sequences analysis and classification
……
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Bayesian Networks Inference
• Given an observed evidence, do some computation to
answer queries
• An evidence e is an assignment of values to a set of
variables E in the domain, E = { Xk+1, …, Xn }
– For example, E = e : { Visit Asia = True, Smoke = True}
• Queries:
– The posteriori belief: compute the conditional probability of a
variable given the evidence,
•
•
P(Lung Cancer| Visit Asia = TRUE AND Smoke = TRUE) = ?
This kind of inference tasks is called Belief Updating
– MPE: compute the Most Probable Explanation given the evidence
An explanation for the evidence is a complete assignment { X1 =
x1, …, Xn = xn } that is consistent with evidence. Computing a MPE is
finding an explanation such that no other explanation has higher
probability
•
This kind of inference tasks is called Belief revision
•
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Belief Updating
•
The problem is to compute P(X=x|E=e): the probability of query nodes X,
given the observed value of evidence nodes E = e.
For example: Suppose that a patient arrives and it is known for certain that he h
recently visited Asia and has dyspnea.
- What’s the impact that this evidence has on the probabilities of the other
variables in the network ? P(Lung Cancer) = ?
Visit to
Asia
Tuberculosis
Smoking
Lung Cancer
tub. or
lung cancer
X-Ray
Bronchitis
Dyspnea
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Belief Revision
Let W is the set of all nodes in our
given Bayesian network
Let the evidence e be the observation
that the roses are okay. Our goal is to
now determine the assignment to all
nodes which maximizes P(w|e).
We only need to consider
assignments where the node
roses is set to okay and
maximize P(w), i.e. the most
likely “state of the world” given
the evidence that rose is ok in
“this world”.
The best solution
then becomes P(sprinklers = F, rain = T, street = wet, lawn = wet, soil = wet, roses = okay) = 0.2646
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Complexity of BBN Inference
• Probabilistic Inference Using Belief Networks is NP-hard.
[Cooper 1990]
• Approximating Probabilistic Inference in Bayesian Belief
Networks is NP-hard [Dagum 1993]
• Hardness does not mean we cannot solve inference. It
implies that
– We cannot find a general procedure that works efficiently for all
networks
– However, for particular families of networks, we can have provably
efficient algorithms either exact or approximate
– Instead of a general exact algorithm, we seek for special case,
average case, approximate algorithms
– Various of approximate, heuristic, hybrid and special case
algorithms should be taken into consideration
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
BBN Inference Algorithms
• Exact algorithms
–
–
–
–
–
Pearl’s message propagation algorithm(for single connected networks only)
Variable elimination
Cutset conditioning
Clique tree clustering
SPI(Symbolic Probabilistic Inference)
• Approximate algorithms
– Partial evaluation methods by performing exact inference partially
– Variational approach by exploiting averaging phenomena in dense networks(law of
large numbers)
– Search based algorithms by converting inference problem to an optimization
problem, then using heuristic search to solve it
– Stochastic sampling also called Monte Carlo algorithms
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Inference Algorithm Conclusions
•
•
•
•
•
•
The general problem of exact inference is NP-Hard.
The general problem of approximate inference is NP-Hard.
Exact inference works for small, sparse networks only.
No single champion either exact or inference algorithms.
The goal of research should be that of identifying effective approximate
techniques that work well in large classes of problems.
Another direction is the integration of various kinds of approximate and exact
algorithms exploiting the best characteristics of each algorithm.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Part III BBN Inference using fractal?
•
•
•
•
Joint Probability Distributions Space of a BBN
Asymmetries in Joint Probability Distributions (JPD)
Fractal Property of JPD
How does it help to do approximate inference?
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Joint Probability Distribution
• Asia revisited:
- Each node has 2 states: Y or N
- Total states: 28 = 256
Instance#
Instance 0:
Instance 1 :
Instance 2 :
Instance 3 :
Instance 4 :
Instance 5 :
Instance 6 :
Instance 7 :
abcdefgh
Smoking
Visit to
Asia
- Eight binary nodes
Tuberculosis
Lung Cancer
Probability
00000000
0.000274
00000001
0.000118
00000010
0
00000011
0
00000100
0
00000101
0
00000110
0
00000111
0
tub. or
lung cancer
X-Ray
Bronchitis
Dyspnea
………..
………..
Instance 252: 1 1 1 1 1 1 0 0
Instance 253: 1 1 1 1 1 1 0 1
Instance 254: 1 1 1 1 1 1 1 0
Instance 255: 1 1 1 1 1 1 1 1
0.001698023
0.015282209
0.032262442
0.290361976
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
JPD of Asia
• 256 states
0.35
0.3
• Max: 0.290362
0.25
•
0.15
•
Conclusion: There is usually a small set fraction
of states that covers a large portion of the total
Probability space with the remaining states having
Practically negligible probabilities.
KDD Presentations: Fractals and BBN Inference
Series1
0.1
0.05
253
232
211
190
169
148
127
106
85
64
43
22
0
1
•
Spreads over 9 orders of magnitude
0,1.50E-09, …, 0.290362
Top 30 most likely states cover 99.2524%
of the total probability space.
0.2
1
2
Kansas State University
Department of Computing and Information Sciences
Why is the JPD so skew?
• When we know nothing about the domain, JPD should be flat.
• The more we know about a domain, the more asymmetry individual
probabilities will show.
• When the domain and its mechanism are well-known, probability
distributions tend to be extreme.
Conclusion:
Asymmetries in the individual distributions result in joint probability
distributions exhibiting orders of magnitude differences in
probabilities of various states of the model.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
How does this help inference?
• Considering only a small number of probabilities of individual states
can lead to good approximations in Belief updating.
• The result can be refined by exploring more high likely states.
• Problem: Where to locate these “peaks”?
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
The global map of JPD of Asia
• To locate these peaks, let’s first make the map.
Nodes order: visit to Asia?|smoking?|tuberculosis?|either tub. or lung cancer?|positive X-ray?|lung
cancer?|bronchitis?|dyspnoea?
CPT arrangements: let small numbers go first, for example 0.01 0.99, 0.3 0.7 in order to shift high
values to the same area.
3.50E-01
Most “peaks” are in the second half of the map
Clusters of high “peaks”
3.00E-01
2.50E-01
2.00E-01
Series1
1.50E-01
1.00E-01
5.00E-02
KDD Presentations: Fractals and BBN Inference
241
221
201
181
161
141
121
101
81
61
41
21
0.00E+00
1
•
•
Kansas State University
Department of Computing and Information Sciences
Self Similarity (or self affine) Property
3.50E-01
3.00E-01
2.50E-01
2.00E-01
Series1
1.50E-01
1.00E-01
5.00E-02
KDD Presentations: Fractals and BBN Inference
241
221
201
181
161
141
121
101
81
61
41
21
1
0.00E+00
Kansas State University
Department of Computing and Information Sciences
Self Similarity (or self affine) Property
3.50E-01
3.00E-03
3.00E-01
2.50E-03
2.50E-01
2.00E-03
2.00E-01
Series1
1.50E-03
Series1
1.50E-01
2.50E-03
121
111
91
101
81
71
61
51
41
31
21
1
241
221
201
181
161
141
121
101
81
61
0.00E+00
41
0.00E+00
21
5.00E-04
1
5.00E-02
11
1.00E-03
1.00E-01
1.40E-04
1.20E-04
2.00E-03
1.00E-04
1.50E-03
Series1
8.00E-05
Series1
6.00E-05
1.00E-03
4.00E-05
5.00E-04
2.00E-05
31
28
25
22
19
16
13
10
7
4
0.00E+00
1
61
56
51
46
41
36
31
26
21
16
11
6
1
0.00E+00
Scale first half(256,0-128, 0-64, 0-32)
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Self Similarity (or self affine) Property
3.50E-01
3.50E-01
3.00E-01
3.00E-01
2.50E-01
2.50E-01
2.00E-01
2.00E-01
Series1
3.50E-01
0.35
3.00E-01
0.3
2.50E-01
0.25
2.00E-01
121
111
101
91
81
71
61
51
41
31
21
1
241
221
201
181
161
141
121
0.00E+00
101
0.00E+00
81
5.00E-02
61
5.00E-02
41
1.00E-01
1
1.00E-01
21
1.50E-01
11
Series1
1.50E-01
0.2
31
28
25
22
19
16
13
10
7
61
56
51
46
41
36
31
0
26
0.00E+00
21
0.05
16
5.00E-02
6
0.1
11
1.00E-01
1
0.15
4
Series1
1.50E-01
1
Series1
Scale second half(1-256,129-256, 193-256, 224-256)
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
More Observations
• How the skewed “map” is being formed?
• First, suppose we know nothing about the domain, i.e., all numbers are
0.5
• Then, we explore the nodes one by one to set the numbers of its CPT
to its actual values (most likely asymmetry, for example, 0.01/0.99,
0.2/0.8).
• We draw the JPD after each node’s CPT is updated. Thus we get 8
graphs.
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
The process of getting skew JPD
0.0045
9.00E-03
1.80E-02
0.004
8.00E-03
1.60E-02
0.0035
7.00E-03
1.40E-02
0.003
6.00E-03
1.00E-02
Series1
3.50E-02
7.00E-02
1.40E-01
3.00E-02
6.00E-02
1.20E-01
2.50E-02
5.00E-02
1.00E-01
2.00E-02
4.00E-02
Series1
1.00E-02
2.00E-02
5.00E-03
241
221
201
4.00E-02
2.00E-02
241
221
201
181
161
141
121
101
81
61
41
1
21
0.00E+00
241
221
201
181
161
141
121
101
81
61
41
1
21
0.00E+00
241
221
201
181
161
141
121
101
81
61
41
21
1
181
Series1
6.00E-02
1.00E-02
0.00E+00
161
8.00E-02
Series1
3.00E-02
141
1
241
221
201
181
161
141
121
81
101
61
41
1
21
248
229
210
191
172
153
134
96
115
77
0.00E+00
58
0.00E+00
39
2.00E-03
0
1
1.00E-03
20
2.00E-03
121
4.00E-03
0.001
0.0005
81
6.00E-03
101
3.00E-03
1.50E-02
Series1
8.00E-03
0.0015
61
4.00E-03
41
0.002
1.20E-02
5.00E-03
Series1
21
0.0025
1.80E-01
3.50E-01
1.60E-01
1.40E-01
3.00E-01
1.20E-01
2.50E-01
1.00E-01
Series1
8.00E-02
2.00E-01
Series1
1.50E-01
6.00E-02
4.00E-02
1.00E-01
2.00E-02
5.00E-02
KDD Presentations: Fractals and BBN Inference
241
221
201
181
161
141
121
81
101
61
41
1
0.00E+00
21
241
221
201
181
161
141
121
101
81
61
41
21
1
0.00E+00
Kansas State University
Department of Computing and Information Sciences
Putting together
0.35
0.3
Series1
Series2
0.25
Series3
0.2
Series4
0.15
Series5
Series6
0.1
Series7
Series8
0.05
KDD Presentations: Fractals and BBN Inference
253
235
217
199
181
163
145
127
109
91
73
55
37
19
1
0
Kansas State University
Department of Computing and Information Sciences
What fractal is this?
• Cantor Set Recall
0.35
0.3
Series1
Series2
0.25
Series3
0.2
Series4
0.15
Series5
Series6
0.1
Series7
Series8
0.05
253
235
217
199
181
163
145
127
109
91
73
55
37
19
1
0
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
The Devil's Staircases
1.00E+00
9.00E-01
8.00E-01
7.00E-01
6.00E-01
5.00E-01
Series1
4.00E-01
3.00E-01
2.00E-01
1.00E-01
0.00E+00
1 21 41 61 81 101 121 141 161 181 201 221 241
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
The process of building Devil’s Staircase (Asia)
1
1.00E+00
1.00E+00
0.9
9.00E-01
9.00E-01
0.8
8.00E-01
8.00E-01
0.7
7.00E-01
7.00E-01
0.6
6.00E-01
0.5
Series1
6.00E-01
5.00E-01
Series1
5.00E-01
0.4
4.00E-01
4.00E-01
0.3
3.00E-01
3.00E-01
0.2
2.00E-01
2.00E-01
0.1
1.00E-01
1.00E-01
0
0.00E+00
0.00E+00
1
1
21 41 61 81 101 121 141 161 181 201 221 241
1.00E+00
9.00E-01
8.00E-01
7.00E-01
6.00E-01
21 41 61 81 101 121 141 161 181 201 221 241
1
1.00E+00
1.00E+00
9.00E-01
9.00E-01
8.00E-01
8.00E-01
7.00E-01
7.00E-01
6.00E-01
5.00E-01
Series1
Series1
5.00E-01
4.00E-01
4.00E-01
3.00E-01
3.00E-01
3.00E-01
2.00E-01
2.00E-01
2.00E-01
1.00E-01
1.00E-01
1.00E-01
0.00E+00
0.00E+00
0.00E+00
21 41 61 81 101 121 141 161 181 201 221 241
21 41 61 81 101 121 141 161 181 201 221 241
6.00E-01
5.00E-01
4.00E-01
1
Series1
1
21 41 61 81 101 121 141 161 181 201 221 241
1.00E+00
1.00E+00
9.00E-01
9.00E-01
8.00E-01
8.00E-01
7.00E-01
7.00E-01
6.00E-01
6.00E-01
Series1
1
21 41 61 81 101 121 141 161 181 201 221 241
5.00E-01
5.00E-01
Series1
4.00E-01
4.00E-01
3.00E-01
3.00E-01
Series1
2.00E-01
2.00E-01
1.00E-01
1.00E-01
0.00E+00
0.00E+00
1
21 41 61 81 101 121 141 161 181 201 221 241
KDD Presentations: Fractals and BBN Inference
1
21 41
61 81 101 121 141 161 181 201 221 241
Kansas State University
Department of Computing and Information Sciences
Multifractal
•
•
•
Consider again the Cantor set, but let the original
bar have a uniformly distributed mass 1.
Suppose the mass is conserved in the
bisection process.
Suppose at each bisection step, the mass
carried by any element is assigned in an
asymmetry wat, say, to the left with
probability P = 0.25.
1
0.25
0.25x0.25, 0.75x0.25
0.25x0.25x0.25
0.25x0.25x0.75 ……
0.75
0.25x0.75,
……
……
0.75x0.75
…… 0.25x0.75x0.75,0.75x0.75x0.75
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Random Multifractal?
–Both are self affine
–Both have clusters of high peaks
–More mass distributions assigned
to the right end
–BBN JPD more irregular, more
random, the probability distributions
are more extreme.
3.50E-01
3.00E-01
2.50E-01
2.00E-01
Series1
1.50E-01
1.00E-01
5.00E-02
KDD Presentations: Fractals and BBN Inference
241
221
201
181
161
141
121
101
81
61
41
21
1
0.00E+00
Kansas State University
Department of Computing and Information Sciences
The cumulative Mass Distributions
• Three Devil’s Staircases:
1.00E+00
9.00E-01
8.00E-01
7.00E-01
6.00E-01
5.00E-01
Series1
4.00E-01
3.00E-01
2.00E-01
1.00E-01
0.00E+00
1 21 41 61 81 101 121 141 161 181 201 221 241
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
Future Problems
• Construct the proper “random multifractal models” for given Bayesian
networks.
• Locate these “clusters of high peaks” from the fractal model. Once we
know that information, other algorithms, for example GA, can be used
to explore the local optimal.
• Identify “Backbone nodes” to help to find out these “high peaks”
• Use these “high peaks” to do approximate inference.
• Design an anytime inference algorithm from the above scheme
• Identify the characteristics of BBNs on which this algorithms work
best(should be related to the asymmetry of these BBNs’ CPTs).
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences
The End
• Any Questions ?
• Thank you!
KDD Presentations: Fractals and BBN Inference
Kansas State University
Department of Computing and Information Sciences