Bayesian Network Structure Learning

• Previous chapters, we know in advance the networks structure, or we decide on one. In this part, we consider learning in situations where we do not know the structure.
  • Strong assumption: the data set is fully observed.
  • We assume the data $D$ are generated i.i.d from an underlying distribution $P^{\ast }(\mathcal{X})$, $P^{\ast }$ is induced by some Bayesian networks ${\mathcal{G}}^{\ast }$ over $\mathcal{X}$.
• Reasons for learning
  • knowledge discovery: learn the dependency structure relating variables by examining the dependencies in the learned network.
  • density estimation: to estimate a statistical model of the underlying distribution
• Other method for correlations:
  • statistical independence test
  • BN reveals finer structure: distinguish between direct and indirect dependencies.
• Even if two events are independent, we do not expect the observed empirical distribution to satisfy independence.
  • toss two coins 100 times: 27HH, 22 HT, 25 TH, 26 TT
• It is hard to be sure the true underlying model has an edge between them or not.
  • $X=x^0$ if 'rain' appears in the article, $X=x^1$ if not
  • $Y=y^0$ if 'football' appears in the article, $Y=y^1$ otherwise.
  • We suspect that there is some weak connection.
• We hope for equivalence class:
  • include more edges: a model contains spurious edges
  • include fewer edges, we may miss dependencies. It is better, with an overly complex structure, we can still capture underlying distribution
  • the decision of whether it is better to have spurious correlations or spurious independencies depends on the application.
• Data fragmentation issue
  • 20 data case: 3HH, 6HT, 5TH, 6TT. First toss $X$, second toss $Y$
  • 20 instances: $P(X=H)=0.45$, $P(Y=H)=0.4$
  • 9 instances: $P(Y=H|X=H)=1/3$
  • 11 instances: $P(X=H|Y=H)=5/11$
  • The standard deviation of the MLE behaves as $1/\sqrt{N}$. When we add more parents to the variable Y, the data used to estimate the CPD fragment into more bins, leaving fewer instances in each bin to estimate the parameters and reducing the quality.
  • In the CPD, the number of bins grows exponentially with the number of parents, so the statistical cost of adding a parent can be very large.

Constraint-based structure learning

• test for conditional dependence and independence in the data
• and then find a network that best explains these dependencies and independencies.
• find the best minimal I-map for the domain.
• Build-PDAG procedure: independence tests, deviance measure

Score-based structure learning

• model selection
• hypothesis space of potential models:
  • superexponential number of structures $2^{O(n^2)}$, $\mathcal{NP}$ hard
  • heuristic search techniques
• scoring function: measure how well the model fits the observed data.
• disadvantage: they may not have an efficient and elegant solution

Maximum likelihood parameters:

• a pair $(\mathcal{G},{\theta }_{\mathcal{G}})$, to find both a graph $\mathcal{G}$ and parameters ${\theta }_{\mathcal{G}}$ that maximize the likelihood.

$$\begin{array}{rl}\underset{\mathcal{G},{\theta }_{\mathcal{G}}}{max}L((\mathcal{G},{\theta }_{\mathcal{G}}):D)& =\underset{\mathcal{G}}{max}[\underset{{\theta }_{\mathcal{G}}}{max}L((\mathcal{G},{\theta }_{\mathcal{G}}):D)]\\ & =\underset{\mathcal{G}}{max}[L((\mathcal{G},{\hat{\theta }}_{\mathcal{G}}):D)]\end{array}$$

find the graph structure $\mathcal{G}$ that achieves the highest likelihood when using the MLE parameters for $\mathcal{G}$.

• Score

$$score_L(\mathcal{G} : D) = \ell((\mathcal{G}, \hat{\theta}_\mathcal{G}) : D)$$ the logarithm of the likelihood function, and $\hat{\theta}_\mathcal{G}$ are the MLE parameters for $\mathcal{G}$. - It follows that the maximum likelihood network will exhibit a conditional independence only when that independence happens to hold exactly in the empirical distribution. Due to statistical noise, exact independence almost never occurs, and therefore, in almost all cases, the maximum likelihood network will be a _fully connected_ one. In other words, the likelihood score overfits overfitting the training data learning a model that precisely fits the specifics of the empirical distribution in our training set. This model therefore fails to generalize well to new data cases: these are sampled from the underlying distribution, which is not identical to the empirical distribution in our training set. - avoid overfitting: learning networks with a fixed indegree ## Bayesian Score - a structure prior $P(\mathcal{G})$ a prior probability on different graph structures - a parameter prior $P(\theta_{\mathcal{G}} | \mathcal{G})$, a probability on different choice of parameters once the graph is given. - Bayes rule $$

P(\mathcal{G} | D) = \frac{P(D | \mathcal{G}) P(\mathcal{G})}

$$Thedenominatorisanormalizingfactorthatdoesnothelpdistinguishbetweendifferentstructures.-Bayesianscore:$$

score_B(\mathcal{G} : D) = \log P(D | \mathcal{G}) + \log P(\mathcal{G})

$$Theterm\$P(D|\mathcal{G})\$takesintoconsiderationouruncertaintyovertheparameters$$

\log P(D | \mathcal{G}) = \int_{\theta_{\mathcal{G}}} P(D | \theta_{\mathcal{G}}, \mathcal{G}) P(\theta_{\mathcal{G}} | \mathcal{G}) d\theta_{\mathcal{G}}

$$-where-\$P(D|{\theta }_{\mathcal{G}},\mathcal{G})\$isthelikelihoodofthedatagiventhenetwork\$⟨\mathcal{G},{\theta }_{\mathcal{G}}⟩\$;-\$P({\theta }_{\mathcal{G}}|\mathcal{G})\$istheprioroverdifferentparametersforthenetwork\$\mathcal{G}\$.-\$P(D|\mathcal{G})\$iscalledthemarginallikelihoodofthedatagiventhestructure,sincemarginalizeouttheunknownparameters.-MLEscorev.s.marginallikelihoodscore-MLEreturnsthemaximumofthisfunction.Itisoverlyoptimisticinitsevaluationofthescore.Thisestimateisrealisticonlyiftheseparametersarealsoreflectiveofthedataingeneral(neveroccurs).-marginallikelihoodscoreistheaveragevalueofthefunction,averagebasedonthepriormeasure\$P({\theta }_{\mathcal{G}}|\mathcal{G})\$.Itgivestheparameters\$\hat{\theta }\$isthemostlikelygiventhetrainingset\$\mathcal{D}\$,itisnottheonlychoice.-holdouttestingmethod:consideringdifferentnetworksstructures,parameterizedbythetrainingsetandtesttheirpredictivenessonthevalidationset.1.\ast \ast Bayesianmodelaveragingmethods\ast \ast -averagethepredictionofallpossiblestructures2.\ast \ast Summary\ast \ast -twomainissues:statisticalprinciplesthatguidethechoicebetweennetworkstructures-computationalproblemofapplyingtheseprinciples.$$