Bayesian networks - created from Mind Map

Página 1

<ul><li>Viewed in this way, Naïve Bayes classifiers, logistic regression models, deci-

sion trees, and so on, are just alternative ways of representing a conditional

probability distribution. Of course, they differ in representational power.

Naïve Bayes classifiers and logistic regression models can only represent simple

distributions, whereas decision trees can represent—or at least approximate—arbitrary distributions. However, decision trees have their drawbacks: they frag-

ment the training set into smaller and smaller pieces, which inevitably yield less

reliable probability estimates, and they suffer from the replicated subtree problem described in Section 3.2. Rule sets go some way toward addressing these

shortcomings, but the design of a good rule learner is guided by heuristics with

scant theoretical justification.

</li><li>BN:

a theoretically well-founded

way of representing probability distributions concisely and comprehensibly in

a graphical manner.

</li></ul>

all attributes are nominal and that there are no missing values

directed acyclic graph

Making predictions

Learning Bayesian networks

CREDIT SCORING SYSTEM<br><br><ul><li>The Bayesian model is a result of formal encoding of the domain expert

knowledge, the factors influencing the phenomenon and their mutual interactions.

</li></ul>

hidden attributes<br><br><ul><li>Some advanced

learning algorithms can create new attributes in addition to the ones present in the data

</li><li> hidden attributes whose values cannot be observed

</li><li> support better models if they represent salient features of the underlying

problem

</li><li> Bayesian networks provide a good way of using them at predic-

tion time

</li><li>However, they make both learning and prediction far more complex

and time consuming

</li></ul>

network of nodes<br><br><ul><li>

one for each attribute

</li></ul>

directed edges<br><br><ul><li>each attribute is connected by directed edges in

such a way that there are no cycles

</li></ul>

CPT<br><br><ul><li>On the left are

the values of Parent, and on the right are the corresponding probabilities for each

value of the attribute represented by the node.

</li><li>

the left side contains

a column for every edge pointing to the node

</li><li>each row of probabilities corresponds to one com-

bination of values of the parent attributes

the entries in the row show the

probability of each value of the node’s attribute given this combination

</li><li> each row defines a probability distribution over the values of the node’s

attribute. The entries in a row always sum to 1

</li></ul>

assuming that there are no missing values<br><br><ul><li> The instance specifies a value for each attribute

</li></ul>

node<br><br><ul><li>

look up the probability of the node’s attribute value

based on the row determined by its parents’ attribute values

</li><li> Then just multi-

ply all these probabilities together.

</li></ul>

joint probabilities<br><br><ul><li>Pr[play = no,E] and Pr[play = yes,E], where E denotes all the

evidence given by the instance’s attribute values

</li><li>Joint probabilities measure the

likelihood of observing an instance that exhibits the attribute values in E as well

as the respective class value

</li><li>

They only sum to 1 if they exhaust the space of all

possible attribute–value combinations, including the class attribute.

</li></ul>

Network<br><br><ul><li>Different Bayesian net-

works can be constructed for the same problem, representing exactly the same

probability distribution.

</li><li>done by altering the way in which the joint

probability distribution is factorized to exploit conditional independencies.

</li><li>The

network whose directed edges model causal effects is often the simplest one with

the fewest parameters.

</li></ul>

conditional probabilities<br><br><ul><li>To obtain the conditional probabilities Pr [play = no|E] and Pr [play = yes|E],

normalize the joint probabilities by dividing them by their sum.

</li></ul>

Conditional independence<br><br><ul><li>given values for each of a node’s parents, knowing the values

for any other ancestors does not change the probability associated with each of

its possible values.

</li><li>ancestors do not provide any information

about the likelihood of the node’s values over and above the information pro-

vided by the parents.

</li><li>Pr[node| ancestors] = Pr[node| parents],

Multiplication is valid pro-

vided that each node is conditionally independent of its grandparents, great-

grandparents, and so on, given its parents.

</li></ul>

correlations<br><br><ul><li>when machine learning techniques are applied to induce

models from data whose causal structure is unknown

all they can do is con-

struct a network based on the correlations that are observed in the data.

</li></ul>

Components<br><br><ul><li>The way to construct a learning algorithm for Bayesian networks is to define

two components

</li></ul>

a function for evaluating a given network based on the data

a method for searching through the space of possible networks

The quality of a given network is measured by the probability of the data given the network<br><br><ul><li>calculate the probability that the network accords to each instance and

multiply these probabilities together over all instances

</li><li>this quickly

yields numbers too small to be represented properly (called arithmetic underflow),

so we use the sum of the logarithms of the probabilities rather than their product.

</li></ul>

Nodes<br><br><ul><li>nodes in the network are predetermined, one for each attribute (includ-

ing the class)

</li><li>Learning the network structure amounts to

1. searching through the space of possible sets of edges, 2.estimating the conditional probability tables for

each set, and 3. computing the log-likelihood of the resulting network based on

the data as a measure of the network’s quality.

</li><li>Bayesian network learning

algorithms differ mainly in the way in which they search through the space of network structures.

</li></ul>

Search Algorithms<br><br><ul><li>Bayesian network learning

algorithms differ mainly in the way in which they search through the space of network structures. </li><li>If the log-likelihood is maximized based on the training

data, it will always be better to add more edges: the resulting network will simply

overfit.

</li></ul>

Overfitting Solution

K2<br><br><ul><li> simple and very fast learning algorithm

</li><li>starts with a given ordering

of the attributes (i.e., nodes)

Then processes each node in turn and greedily considers adding edges from previously processed nodes to the current one.

</li><li>each step it adds the edge that maximizes the network’s score. When there is no

further improvement, attention turns to the next node.

</li></ul>

tree augmented Naïve Bayes (TAN)<br><br><ul><li>it takes the Naïve Bayes

classifier and adds edges to it

</li><li>The class attribute is the single parent of each node of a Naïve Bayes network: TAN considers adding a second parent to each

node.

</li><li>If the class node and all corresponding edges are excluded from consid-

eration, and assuming that there is exactly one node to which a second parent

is not added, the resulting classifier has a tree structure rooted at the parentless

node—this is where the name comes from.

</li><li>This algorithm is linear in the number of instances and quadratic in the number of attributes.

</li><li>Tree Augmented Naive Bayes where the tree is formed by

calculating the maximum weight spanning tree using Chow and Liu algo-

rithm

</li></ul>

penalty for the complexity of the network<br><br><ul><li> .penalty for the complexity of the network based on the number of parameters, that is, the total number of independent estimates in all the probability

tables.

</li><li>For each table, the number of independent probabilities =

total number of entries - the number of entries in the last column

which can

be determined from the other columns because all rows must sum to 1

</li><li>

log-likelihood is negated, so the aim is to minimize these

scores.

</li><li>K = the number of parameters,

LL = the log-likelihood, and

N = the number of

instances in the data

</li></ul>

Cross validation

"Bayesian” approach<br><br><ul><li>assign a prior distribution over network structures

and find the most likely network by combining its prior probability with the

probability accorded to the network by the data.

</li><li>Depending on the prior distribution used, it can take

various forms

</li><li>assign a prior distribution over network structures

and find the most likely network by combining its prior probability with the probability accorded to the network by the data

Depending on the prior distribution used, it can take

various forms.

</li></ul>

Markov blanket<br><br><ul><li>ensure that every attribute in the data

is in the Markov blanket of the node that represents the class attribute.

</li><li>A node’s

Markov blanket includes all its parents, children, and children’s parents.

</li><li>It can be shown that a node is conditionally independent of all other nodes given values for the nodes in its Markov blanket.

</li><li>if a node is absent from the

class attribute’s Markov blanket, its value is completely irrelevant to the classi-

fication.

</li></ul>

Akaike Information Criterion (AIC)<br><br><ul><li>AIC score = - LL + K ,

</li></ul>

MDL metric based on the MDL principle<br><br><ul><li>MDL score = - LL + K/2 log N .

</li></ul>

true Bayesians<br><br><ul><li>true Bayesians would average over all possible network

structures rather than singling out a particular network for prediction. Unfor-

tunately, this generally requires a great deal of computation.

</li></ul>

simplified approach<br><br><ul><li>average over all network structures that are substructures of a given network. I

</li><li>It turns out that this can be implemented very efficiently by

changing the method for calculating the conditional probability tables so that the resulting probability estimates implicitly contain information from all sub-networks.</li></ul>

Overfitting avoidance Machenism<br><br><ul><li>the number of parents for each node can be

restricted to a predefined maximum

</li><li>However, the result depends on the initial ordering, so it makes

sense to run the algorithm several times with different random orderings.

</li></ul>

Markov Blanket<br><br><ul><li>if K2 finds a network that does not include a relevant attrib-

ute in the class node’s Markov blanket, it might help to add an edge that rectifies

this shortcoming. </li><li>A simple way of doing this is to add an edge from the attribute’s node to the class node or from the class node to the attribute’s node,

depending on which option avoids a cycle. </li></ul>

log-likelihood<br><br><ul><li>The resulting quantity is the log-likelihood of the network given the data.

</li></ul>

1. descriptive parameters of the model (nodes)<br><br><ul><li>At first the primary goal is defining descriptive parameters of the model

</li><li>the domain expert has a crucial work to

do. The topology of network and its detailed nature is then specified.

</li><li>Unspecified

parameters, lacking or misdirected connections between nodes result in inconsistencies of model, ambiguity of causal relationships and finally in inaccuracy of

expertise.

</li></ul>

2. quantitative specification of model,<br><br><ul><li>requires filling-up conditional probability tables. The computer aided, statistical analysis of historical data

can reveal strength of causal dependencies between nodes. During all procedures

the domain expert can moderate generation process.

</li></ul>

Model<br><br><ul><li>The aim of the economic model we work with in this article is to analyze

standing of an enterprise from crediting banks’ perspective. We defined nine groups

of factors (i.e. scope of analysis) used to classify customers according to credit risk-

level.

</li></ul>