Learning Structure from Data and Its Application to Ozone Prediction.
In this paper we propose an algorithm for structure learning in predictive expert systems based on a probabilistic network representation. The idea is to have the simplest structure (minimum number of links) with acceptable predictive capability. The algorithm starts by building a tree structure based on measuring mutual information between pairs of variables, and then it adds links as necessary to obtain certain predictive performance. We have applied this method for ozone prediction in Mxico City, where the ozone level is used as a global indicator for the air quality in different parts of the city. It is important to predict the ozone level a day, or at least several hours in advance, to reduce the health hazards and industrial losses that occur when the ozone reaches emergency levels. We obtained as a first approximation a tree-structured dependency model for predicting ozone in one part of the city. We observe that even with only three parameters, its estimations are acceptable.A causal network representation and the structure learning techniques produced some very interesting results for the ozone prediction problem. Firstly, we got some insight into the dependence structure of the phenomena. Secondly, we got an indication of which are the important and not so important variables for ozone forecasting. Taking this into account, the measurement and computational costs for ozone prediction could be reduced. And thirdly, we have obtained satisfactory short term ozone predictions based on a small set of the most important parameters.
Introduction
Learning is defined as "any process by which a
system improves its performance" [1]. Since the
first days of research in artificial intelligence, the
ability to learn has been considered as one of the
essential attributes of an "intelligent system", and
a considerable amount of research has been done
in this area. Learning has focused in acquiring
concepts from examples in what is called inductive
learning. The development of expert systems
has motivated further research in learning to automate
the process of knowledge acquisition. This is
considered one of the main problems for the construction
of knowledge-based systems.
An important aspect in inductive learning is
to obtain a model which represents the domain
knowledge, and is accessible to the user. In par-
ticular, it is useful to obtain the dependency information
between the variables involved in the
phenomena. That is, those factors that are important
for certain variable, and those that are not.
This is of particular interest in predictive expert
systems, when we want to forecast some variables
based on known parameters. It is useful to know
the parameters which have more incidence in the
unknowns, and the ones that have not much influ-
ence. A knowledge representation paradigma that
captures this dependency information is a probabilistic
network.
Probabilistic networks (PN) [3], also known as
Bayesian networks, causal networks or probabilistic
influence diagrams, are graphical structures
used for representing expert knowledge, drawing
conclusions from input data and explaining the
reasoning process to the user. A PN is a directed
acyclic graph (DAG) whose structure corresponds
to the dependency relations of the set of variables
represented in the network (nodes), and which
is parameterized by the conditional probabilities
(links) required to specify the underlying distri-
bution. The structure of the network makes explicit
the dependence and independence relations
between the variables, which are important: (i)
in representing the knowledge of the domain, and
(ii) for efficient probability propagation.
Fig. 1. A probabilistic network.
If we use a PN representation, learning is divided
naturally into two aspects: parameter learning
and structure learning [2]. Parameter learning
has to do with obtaining the required probability
distributions for a certain structure. Structure
learning has to do with obtaining the topology of
the network, including which variables are relevant
for a particular problem, and their depen-
dencies. We are interested in this second aspect,
that is in obtaining the dependency structure of
certain phenomena, to get a better understanding
of it and to use it as a predictive tool.
In section 2 we give a brief introduction to
probabilistic networks. Section 3 reviews previous
work on structure learning, and section 4 introduces
our methodology for obtaining a dependency
structure for predictive systems. In section
5 we describe the problem of Ozone prediction in
Mexico City, and we present some experimental
results in section 6. Finally, we give some conclusions
and possible directions for future work.
2. Probabilistic Networks
A probabilistic network is a graphical representation
of dependencies and independencies for probabilistic
reasoning in expert systems. Each node
represents a discrete random variable and each arc
a probabilistic dependency. The variable at the
end of a link is dependent on the variable(s) at
its origin, e.g. C is dependent on A in the PN
in figure 1, as indicated by link 1. We can think
of the graph in figure 1 as representing the joint
probability distribution of the variables A; B; :::; G
as:
Equation (1) is obtained by applying the chain
rule and using the dependency information represented
in the network.
The topology of a PN gives direct information
about the dependency relationships between
the variables involved. In particular, it represents
which variables are conditionally independent
given another variable. By definition, A is
conditionally independent of B, given C, if:
This is represented graphically by node C "sep-
arating" A from B in the network. In general, C
will be a subset of nodes from the network that if
removed will make the subsets of nodes A and B
"disconnected". Independence in a PN network is
tested with a criteria called D-separation [2].
A DAG representation G of a probability distribution
P is an I-map [2] if all the independencies
represented in G are present in P . It is a minimal
I-map if it is an I-map with the minimum number
of links, that is, if any link is removed, there
will be an independency relation in G that is not
present in P . Formally, a probabilistic network is
minimal I-map for a joint probability distribution
P [2]. In other words, it is a graph with the minimum
number of links that faithfully represents all
the probabilistic independencies for a set of random
variables.
Given a knowledge base represented as a probabilistic
network, it can be used to reason about
the consequences of specific input data, by what
is called probabilistic reasoning. This consists in
instantiating the input variables, and propagating
their effect through the network to update the
probability of the hypothesis variables. In contrast
with previous approaches (e.g., MYCIN and
(c)
(a)
(b)
Fig. 2. Network structures: (a) tree, (b) polytree, and (c)
multiply-connected.
Prospector [4]), the updating of the certainty measures
is consistent with probability theory, based
on the application of Bayesian calculus and the
independencies represented in the network.
Probability propagation in a general network
is a complex problem, but there are efficient algorithms
for certain restricted structures, and
alternative approaches for more complex net-
works. Pearl [3] developed a method for propagating
probabilities in networks which are tree-
structured, i.e. each node has only one incoming
link or one parent. An example of a probabilistic
tree is shown in figure 2 (a).
In a probabilistic tree every node has only one
parent except one node, denoted root, which has
no incoming links. Given certain evidence V , represented
by the instantiation of the corresponding
variables, the posterior probability of any variable
taking its i value (B i ), by Bayes' theorem will
be:
Given the dependencies represented in the tree,
separates it into two independent subtrees, one
formed by all the descendants of B and the other
by every other node. Thus, we can decompose the
evidence variables into two sets, V \GammaB which represents
all the data rooted at B, and V +B for the
data contained in the rest of the network. So (3)
can be written as:
Given that the two subtrees are conditionally independent
given B:
Substituting (5) in (4), and applying some alge-
bra, we obtain:
Where ff is a normalizing constant. Equation (6)
provides a product rule for updating the probability
on every node in the network by combining the
evidence coming from its descendants with the one
coming from its parent. It shows that a prior probability
is not required, except for the root node
(A) for which P
the following terms [2]:
Then we can write (6) as:
Equation constitutes the basis for the propagation
mechanism in a probabilistic tree. For
this we only need to store the vectors - and - in
each node, and update them with the corresponding
parameters from its neighbors; and the fixed
conditional probability matrix P for that node.
This can be implemented by a message passing
scheme in which each node acts as a simple process
which communicates with its neighbours (fa-
ther and sons). Initially the network is in equi-
librium. When information arrives, some nodes
called data nodes, are instantiated and the information
is propagated through the network by
each node sending messages to its parent and sons.
Each node uses this information to update its local
parameters, and update its posterior probability if
required. After the messages reach the root node,
they will propagate top-down until they reach the
leaf nodes, where the propagation terminates and
the network comes to a new equilibrium. So the
information propagates through the tree in a single
pass, in a time (in parallel) proportional to the
diameter of the network.
An extension for polytrees, was proposed by
Kim and Pearl [5]. In a polytree each node can
have multiple parents, but it is still a singly connected
graph. A polytree is depicted in figure 2
(b). The main difference with the algorithm for
trees, is that for multi-parent nodes, the conditional
distribution given all their parents is re-
quired. The time for propagation is still linearly
proportional to the diameter of the network.
For more complex, multiply connected net-
works, see fig. 2 (c), there are alternative techniques
for probability propagation, such as clustering
[6], conditioning [2], and stochastic simulation
[2]. These methods are efficient for certain
types of structures, mainly sparse networks. But
in general, probability propagation in a complex
network is an NP-hard problem [7].
Thus, for efficiency reasons, and also for clarity
and expressiveness, it is important to obtain the
simplest structure, with the minimum number of
links, which models appropriately the phenomena
of interest. A complete graph will be a trivial Imap
of any probability distribution, but it would
not be useful in terms of knowledge representation
or computational efficiency.
3. Structure Learning Approaches
Structure learning consists in finding the topology
of the network, that is the dependency relationships
between the variables involved. Most expert
systems obtain this structure from the expert, representing
in the network the expert's knowledge
about the causal relations in the domain. But for
complex problems there might be no expert that
has a complete understanding of the domain to
obtain all these dependency (and independency)
relations, and if so, her/his knowledge could be de-
ceiving. Also, knowledge acquisition could be an
expensive and time consuming process. So we are
interested in using empirical observations to obtain
and improve the structure of a probabilistic
network. Some previous research has been done
on inducing the structure of a PN from statistical
data. Chow and Liu [8] presented an algorithm for
representing a probability distribution as dependency
tree, and this was later extended by Rebane
and Pearl [9] for recovering causal polytrees.
Chow and Liu's [8] motivation was reducing the
memory requirements for storing a n-dimensional
discrete probability distribution. For this they developed
a method for approximating a probability
distribution by a product of second-order dis-
tributions, which is equivalent to a probabilistic
tree. Thus, the joint probability distribution will
be represented as:
Y
Where X j(i) is the cause or parent of X i . Each
variable has one parent, except one (the root)
which has no parent, so the method is restricted
to a tree structure. They considered the approximation
of the original distribution by a dependency
tree as an optimization problem, and used
a quantity that measures the difference in information
contained in the two distributions. That
is:
x
Where the problem is reduced
to finding the tree dependency distribution
that approximates the original distribution P
such that I(P; P   ) is minimal. To find the optimum
tree, they use the entropy measure for the
mutual information between two variables, defined
as:
x
log(P
If we assign to every branch in the tree the
weight that corresponds to the mutual information
between the variables connected by that link,
then the weight of the tree is the sum of the
weights for all the branches. It can be shown
[8] that maximizing the total branch weight is
equivalent to minimizing the closeness measure
so the tree with the maximum weight
will be the optimum tree dependency approximation
of P . This result makes it possible to find the
optimum tree structure by a simple algorithm that
uses only the n(n \Gamma 1)=2 second-order distributions
that correspond to all the possible branches for n
variables. These are ordered according to their
weight, and the two with maximum weight are selected
as the first two branches in the tree. Then
the other branches are selected in decreasing order
whenever they do not form a cycle with the
previously selected ones, until all the variables are
covered branches). Thus, to obtain a tree-structured
PN from sample data, we just need to
estimate the joint frequencies and mutual information
for all pairs of variables, and then construct
the optimum tree by the previous algorithm.
Rebane and Pearl [9] extended Chow's method,
developing a similar algorithm for the construction
of a polytree from statistical data. A polytree
is a singly connected network in which each
each node can have multiple parents. So the joint
probability distribution can be expressed as:
Y
Where fX is the set of parents
of the variable X i . The algorithm for constructing
a polytree starts by using the tree recovering
algorithm for constructing the skeleton,
that is the network without the directionality in
the links. Then it checks for the local dependencies
between variables and uses this information to
determine the directionality of the branches. The
local dependency tests is applied to all connected
variable triples and, by checking if
all variable pairs are dependent or independent,
it can partially determine the directionality of the
corresponding links. This test is applied to all
nodes starting from the outermost ones (leafs) in-
wards, until all possible directionalities are found.
In general, it is not possible to find the direction
of all the branches, and external semantics are
needed for completion [2].
Recent work has focused in two aspects: to
combine statistical data with expert knowledge;
and to induce multiply-connected networks from
data. The first approach is based on combing expert
knowledge and data to overcome the limitations
of the previous techniques, and obtain a
more general and complete dependence structure.
Sucar et al. [10] start from a structure derived
from subjective rules as an initial topology. Then
they develop a methodology based on statistical
techniques to improve the structure by testing the
independence assumptions, and altering the structure
if any of them is not satisfied. Kwoh and
Gillies [11] extended this work, by creating hidden
nodes to improve the structure of a Bayesian tree
when the independence assumptions do not hold.
Srinivas et al. [12] combine expert knowledge and
dependence information (which can be obtained
from statistical tests) in an iterative algorithm for
approximating the structure of a Bayesian net-
work. The expert knowledge they use includes
which variables are hypothesis (root nodes), which
are evidence (leaf nodes), and partial knowledge
6 THE AUTHORS???
about causality and independence between some
of the variables.
In the second approach, Cooper and Herskovits
[13] developed a Bayesian Method for the induction
of probabilistic networks from data. Given
certain assumptions about the probability distri-
butions, they developed an algorithm for obtaining
the most probable Bayesian network given a
database of cases. With this algorithm the probability
of certain structure given the data can
also be obtained, and it can handle missing data
and hidden variables. Recently, Lam and Bacchus
[14] developed and alternative technique for inducing
multiply-connected networks based on Rissa-
nen's minimal description length (MDL) principle.
Their algorithm tries to make a trade off between
the accuracy and complexity of the structure ob-
tained. That is, favoring simpler structures even
if they are not as accurate as a more complex one.
Chow and Liu's algorithm has two important
limitations: (i) it is restricted to tree structures,
and (ii) it does not obtain the directions of the
links (causality). Rebane and Pearl's extension
is still restricted in both aspects, generality and
directionality. As Lam and Bacchus [14] point
out, the approach in [13] assumes a uniform distribution
over all possible network structures, so it
could favor a much more complex structure even
if it is only slightly more accurate. The approach
based on the MDL principle [14] overcomes this
difficulty by considering both, accuracy and com-
plexity. Still, it is based on certain heuristics so
that it can not always obtain the optimum solu-
tion. The other approaches assume the existence
of expert knowledge which is not always available.
The special case of predictive systems have certain
characteristics, as we explain in the following
section, that make the previous algorithms inap-
propriate. In particular, most previous techniques
consider all the variables at the same level, while
in predictive systems accuracy in terms of the un-
is the most important factor.
4. Structure Learning for Predictive System

In a predictive system there is one (or a few) variable
whose value is unknown, and which is estimated
based on other known variables. It is
possible to have spatial or temporal predictions.
In the first case, the unknown is not observable
and is estimated from other measured parameters.
In the second case, the unknown is in the future
and is predicted form present, and past, measure-
ments. For instance, in pollution prediction we
might want to estimate the pollution level in some
part where there are no measurements, or one day
in advance.
We are interested in obtaining dependence
structures for predictive systems, which have some
special characterists:
ffl There is usually only one variable which we
want to predict, so it can be considered the
hypothesis or root node.
ffl The other variables are evidence nodes which
can have different levels of influence in the hypothesis

ffl Not all the evidence nodes have direct influence
in the hypothesis, but there influence could be
through other evidence nodes.
Thus, we propose an algorithm for structure
learning in predictive expert systems based on the
previous observations. The idea is to have the
"simplest" structure (minimum number of links)
with acceptable predictive capability. Our approach
is to start with a PN with the minimum
possible number of links that connects all the variables
involved. For N variables, the smallest connect
graph is a tree, with arcs. This will
constitute the "skeleton" of the network. If the
predictive accuracy of a tree is good enough then
we consider this structure. Otherwise, we start to
add links, according to certain criteria, until we
obtain the desired performance.
The algorithm is the following:
1. Obtain an initial tree structure by Chow and
Liu's algorithm.
2. Make the hypothesis variable the root node.
This fixes the directions of the links.
3. Produce an ordering of the variables
Xng starting from the root, and
following the tree according to the order of
mutual information between variables.
4. Test the predictive capability of the network:
4.1 If it is satisfactory, stop(1).
play
outlook
temperature humidity
windy
Tree links
Other links
Fig. 4. Initial probabilistic tree for the golf example.
4.2 If not, and the number of links is less than
a maximum, add a link to the network and
to 4. A link is added with the highest
mutual information such that: (i) it
does not produce a cycle, (ii) the node at
the start of the link is a predecessor of the
node at the end, according to the previous
ordering.
4.3 If not, and the number of links is equal to
the maximum, stop(0).
Stop (1) indicates successful termination, and
stop (0) that it could not achieve the desired predictive
performance. The predictive capability is
tested statistically, by performing predictions on
different data than the training set, and comparing
the predictions with the actual values for the
unkown. Maximum is the number of links for a
completely connected graph, N (N \Gamma 1)=2.
The theoretical justification for step (4.2) in the
algorithm is based on a general procedure for obtaining
a minimal I-Map (a PN in which every
independence relation represented in the network
is valid) [15]. It consists on defining an ordering of
the variables, and constructing a graph such that
the "parents" of each variable are a subset of its
predecessors that makes it independent from the
rest of its predecessors.
If the number of arcs reaches the maximum, we
obtain a totally connected graph, which represents
the joint probability distribution of the N variables
without any independence assumptions. As
we mention before, this will be a trivial I-map for
any distribution. If the complete graph still does
not have the desired predictive accuracy, it means
that the training data is inadequate for generating
an appropriate structure. Either more cases
are required (larger sample), or other parameters
not included in the set of variables need to be considered

To illustrate the procedure, we use a small, hypothetical
example for "predicting when to play

Table

1 shows the variables and their
values for this examples, table 2 shows the set of
examples used for training, and table 3 the dependency
links (variable pairs) ordered by mutual in-
Table

1. Variables for the golf prediction example.
Variable Values
play Play, Don't Play
outlook sunny, overcast, rain
temperature continuous
humidity continuous
windy true, false

Table

2. Set of training data for the golf prediction example

outlook temp. hum. windy play
sunny 85 85 false false
sunny
overcast
rain 70 96 false true
rain 68 80 false true
rain
overcast
sunny 72 95 false false
sunny 69 70 false true
rain
sunny
overcast 72 90 true true
overcast 81 75 false true
rain 71 96 true false

Table

3. Set of links (variable pairs) ordered by mutual
information for the data in table ??.
Link Variables
9 windy - play
formation. This is a very small data set just used
to illustrate the ideas. The initial tree structure,
overimposed in the complete graph is depicted in
figure 4. A possible ordering for the variables in
these case will be: fplay, outlook, temperature,
humidity, windyg.
In figure 3, the next 3 steps in the algorithm
are shown, assuming that the tree structure is not
good enough (for this small example we did not
test the predictive accuracy). In each one a new
link is added according to the mutual informa-
tion, and its direction is determined by the variable
ordering. The algorithm will terminate when
we obtain the desired accuracy, or generate the
complete graph (10 links in this example).
An interesting aspect to notice is that, unless
we need the complete graph, we can usually eliminate
some variables for predicting the unknown.
For a tree structure, we can eliminate all the variables
but the ones directly connected to the hypothesis
(root) node. This is because of the independence
relations that are represented in the
PN. In a tree, a node is independent of all the
other variables given its direct parent and sons.
For the root node, these are only its direct sons.
In general, if the network is not complete (all links
present), a subset of nodes will make a node independent
of the remaining nodes. Thus, if all the
variables but one are known, we can use these independence
information to eliminate parameters
and simplify the estimation problem.
In the following section we introduce the problem
of Ozone prediction in Mexico City, and apply
the previous algorithm to obtain the dependence
structure of this phenomena.
play
outlook
temperature
humidity
windy
play
outlook
temperature
humidity
windy
play
outlook
temperature
humidity
windy
(a) (b) (c)
Fig. 3. Structures produced by the second stage in the structure learning algorithm for the golf example: (a) first additional
link, (b) second, (c) third.
5. Ozone Prediction in Mexico City
Air quality in M'exico City is a major problem.
Air pollution is one of the highest in the world,
with high average daily emissions of several primary
pollutants, such as hydrocarbons, nitrogen
oxides, carbon monoxide and others. The pollution
is due primarily to transportation and industrial
emissions. When the primary pollutants
are exposed to sunshine, they undergo chemical
reactions and yield a variety of secondary pollu-
tants, ozone being the most important. Besides
the health problems it may cause, ozone is considered
as an indicator of the air quality in urban
areas.
The air quality is monitored in M'exico City in
stations, with five of these being the most com-
plete. Nine variables are measured in each of the
5 main stations, including: wind direction and
velocity, temperature, relative humidity, sulphur
dioxide, carbon monoxide, nitrogen dioxide and
ozone. These are measured every minute 24 hours
a day, and are averaged every hour.
It is important to be able to forecast the pollution
level several hours, or even a day in advance
for several reasons, including:
1. To be able to take emergency measures if the
pollution level is going to be above certain
threshold.
2. To help industry to make contingency plans in
advance to minimize the cost of the emergency
measures.
3. To estimate the pollution in an area where
there are no measurements.
4. To take preventive actions in some places, as in
schools, to reduce the health hazards produced
by high pollution levels.
In M'exico City, the ozone level is used as a
global indicator for the air quality in the different
parts of the city. The concentrations of ozone are
given in IMECA (Mexican air quality index). So
it is important to predict the ozone level a day, or
at least several hours in advance using the other
variables measured in different stations.
Previous work [16] has been done in using neural
network techniques to forecast ozone in M'exico
City. The results are encouraging for estimating
the ozone level up to 4 hours in advance. The
problem with these techniques is that we do not
get any insight into the structure of the phenom-
ena. It will be useful to know the dependencies
between the different variables that are measured,
and specially their influence in the ozone concen-
tration. This will provide a better understanding
of the problem with several potential benefits:
ffl Determine which factors are more important
for the ozone concentration in M'exico City.
ffl Simplify the estimation problem, by taking into
account only the relevant information.
ffl Find out which are the most critical primary
causes of pollution in M'exico City which could
help for future plans to reduce it.
6. Experimental Results
We started by applying the learning algorithm to
obtain an initial structure of the phenomena. For
this we considered 47 variables [17]: 9 measurements
in 5 stations, plus the hour and month in
which they were taken. We used nearly 400 random
samples, and applied the first step in our
algorithm to obtain the tree structure that best
approximates the data distribution. This tree-structured
Bayesian network is shown in figure 5.
We then considered the ozone in one station
(Pedregal) as unknown, to estimate it one hour
in advance using the other measurements. So we
make ozone-Pedregal the hypothesis variable and
consider it as the root in the probabilistic tree,
as shown in figure 5. From this initial structure
we can get an idea of the relevance or influence of
the other variables for estimating ozone-Pedregal.
The nodes "closest" to the root are the most important
ones, and the "far-away" nodes are not so
important.
In this case we observe that there are 3 variables
(ozone-Merced, ozone-Xalostoc, and wind
velocity in Pedregal) that have the greatest influence
in ozone-Pedregal. What is more, if the tree
structure is a good approximation to the "real"
structure, these 3 nodes make ozone-Pedregal independent
from the rest of the variables (see figure
7). Thus, as a first test of this structure, we estimated
ozone-Pedregal using only these 3 variables.
The estimation is done with the probability propagation
algorithm for trees presented in section 2.
This algorithm works with discrete variables only,
so continuos variables are discretized in fixed size
intervals. We made two experiments: (1) estimate
ozone-Pedregal using 100 random samples taken
from the training data, and (2) estimate ozone-
Pedregal with other 100 samples taken from other
data, not used for training. The results for a sub-set
of 20 representative samples in each case are
shown in figures 6 and 8.
We observe that even with only three param-
eters, the estimations are quite good. For training
data the average error (absolute difference between
real and estimated ozone concentration) is
11.2 IMECA or 12.1%, and for not-training data
it is 26.8 IMECA or 22.1%. This results should
be judged taking into account that this is the first
approximation to a dependency model, and that
we are only considering 3 variables for estimating
the ozone at Pedregal. The neural network model
[16] with 46 inputs, has an average error of
with a similar set of test (not-training) data.
O3_T
O3_L O3_Q VV_T
CO_T
HORA
RH_F
TMP-T
O3_F
RH_L
RH_T
CO_Q
CO_L
CO_F
Fig. 5. A Bayesian tree that represents the ozone phenomena in 5 stations in M'exico City. The nodes represent the
variables according to the following nomenclature. For the measured variables, each name is formed by two parts,
"measurement-station", using the following abbreviations: the measurements, O3-ozone, SO2-sulphur dioxide, CO-carbon
monoxide, NO2-nitrogen dioxide, NOX-nitrogen oxides, VV-wind velocity, DV-wind direction, TMP-temperature, RH-
relative humidity; the monitoring stations, T-Pedregal, F-Tlanepantla, Q-Merced, L-Xalostoc, X-Cerro de la Estrella. The
other two variables correspond to the time when the measurements were taken, and they are: HORA-hour, MES-month.
The same data was used to train and test C4.5
[18]. The error on the test set was of 17.64%. The
tree produced by C4.5 is given in figure 9. It is
interesting to note that C4.5 considered the wind
direction in Pedregal as its principal attribute. A
north-south wind direction (? 120 increases the
levels of ozone, whether in a south-north direction
the ozone levels are mainly located within the first
intervals (below 70 IMECAS). We then tested the
accuracy of C4.5 by pruning its tree at different
depths, that is, considering only the most relevant
attributes. The leaves were labeled with the may-
ority class of the training set at that level. At
depth 4, the accuracy of C4.5 is 21.86%. Considering
only the three most important attributes
(i.e., at depth 2), and the mayority class for that
branch of the tree, C4.5 has an error of 24.80%.
Ozone
Pedregal
Ozone
Merced
Ozone
Xalostoc
Pedregal
Fig. 7. Reduced tree for predicting Ozone-Pedregal.
The accuracy of C4.5 with the complete tree is
higher than with our reduced dependency model,
with the tree pruned at depth 4 it is about the
same, and it is lower with 3 attributes. It is difficult
to compare both algorithms because they use
a different representation, so a decision node in
a decision tree and a variable node in a Bayesian
network are not the same. Still, we can consider
that the accuracy is similar with these two different
representations and learning algorithms, and
will expect a higher accuracy if the dependency
model is extended with more variables and relations

An advantage of the dependency model is that
it is generally easier to understand. The relevance
of each attribute for predicting certain variable is
explicitly represented. This is more difficult to obtain
from a decision tree, where an attribute can
be repeated as different nodes at different depths.
A second advantage is that it gives a probability
measure for each value (range) of the hypothesis,
which is, in general, not available with a decision
tree. Finally, a Bayesian network can be used to
predict any variable with any subset of attributes
known, while a decision tree is for one variable and
with all (or most) of the attributes known.
For practical purposes, the ozone measured
in IMECAS is divided in several intervals, each
of size 50. The air quality and corresponding
emergency measures are based on these intervals.
In our experiments with the probabilistic model,
aprox. 90% of the predictions fall in the same 50
IMECAS interval as the measured ozone level.
Fig. 6. Real vs. estimated levels for ozone-Pedregal using 3 variables and training data.
7. Conclusions and Future Work
A causal network representation and the structure
learning techniques produced some very interesting
results for the ozone prediction problem.
Firstly, we got some insight into the dependence
structure of the phenomena. For example, the
ozone in Pedregal is influenced by the ozone in
other stations and the wind velocity. This is due
to the fact that the pollution in the south (Pedre-
gal) of M'exico City, is, in large part, produced by
the industrial plants in the north and a dominant
north-south wind direction. Secondly, we got an
indication of which are the important and not so
important variables for ozone forecasting. Taking
this into account could reduce the measurement
and computational costs for ozone predic-
tion. Thirdly, this dependency information could
be used for improving other alternative prediction
techniques, such as neural networks.
With respect to ozone prediction in M'exico
City, we plan to continue this work in several aspects

ffl Improve the structure of the Bayesian network
by using the second part of our algorithm.
ffl Obtain the dependence structure for other variables
of interest, in particular the ozone in other
stations.
ffl Test its predictive capability using other vari-
ables, assuming that the most influential ones
are unknown or not reliable.
ffl Improve the longer term predictions by using
additional information, such as weather forecasting
variables.
In structure learning in Bayesian networks in
general, there are several research issues which remain
to be addressed. Firstly, there is the problem
of obtaining the optimal structure in the general
case, considering the model's accuracy and
computational complexity. Secondly, there is no
general algorithm for obtaining the directions of
all the links in the network. And thirdly, most
structure learning algorithms only consider the observable
variables. But, in many cases, the introduction
of other variables (called hidden or virtual
nodes) can produce simpler structures with an improved
predictive capability. We will be addressing
these issues in our future research work.
Fig. 8. Real vs. estimated levels for ozone-Pedregal using 3 variables and not-training data.
RH_F
RH_L
HORA
484 28687219227104323177Fig. 9. Decision tree for ozone-Pedregal produced with C4.5. Each node represents a decision over the value of a variable: if
the value is less than the value shown under the node, then the left branch is followed, otherwise the right one. The leaves
represent different classes for ozone-Pedregal (from C0 to C19), with the same discretization used in the Bayesian network.
Notes
1. Data taken from public domain file



--R

"Why Machines should Learn?"
Probabilistic Reasoning in Intelligent Sys- tems
"On Evidential Reasoning on a Hierarchy of Hypothesis"
"Uncertainty Management in Expert Systems"
"A Computational Model for Combined Causal and Diagnostic Reasoning in Inference Systems"
"Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems"
"The Computational Complexity of Probabilistic Inference Using Bayesian Networks"
"Approximating Probability Distributions with Dependence Trees"

"Objective Probabilities in Expert Systems"
"Using Hidden Nodes in Bayesian Networks"
"Automated Construction of Sparse Bayesian Networks from Unstructured Probabilistic Models and Domain Information"
"A Bayesian Method for the Induction of Probabilistic Networks from Data"
"Learning Bayesian Net- works: An Approach Based on the MDL Principle"
"Causal Networks: Semantics and Expressiveness"

"In- duction of Dependence Structures from Data and its Application to Ozone Prediction"

--TR

--CTR
Elias Kalapanidas , Nikolaos Avouris, Feature selection for air quality forecasting: a genetic algorithm approach, AI Communications, v.16 n.4, p.235-251, December
Ciprian-Daniel Neagu , Nikolaos Avouris , Elias Kalapanidas , Vasile Palade, Neural and Neuro-Fuzzy Integration in a Knowledge-Based System for Air Quality Prediction, Applied Intelligence, v.17 n.2, p.141-169, September-October 2002
structure learning;bayesian networks;predictive systems;decision trees;atmospheric pollution