Deviance

Context

• The Deviance measure is based on the difference between the Entropy of the to-be-evaluated network $B$ and the Entropy of the complete (i.e., fully connected) network $C$.
• The closer the Deviance value is to 0, the better the network $B$ represents the dataset.

Definition

Deviance is formally defined as:

$D_B = 2N \times \ln(2) \times \left( H_B(\mathcal{D}) - H_C(\mathcal{D}) \right)$

where

• $H_B(\mathcal{D})$ is the Entropy of the dataset given the to-be-evaluated network $B$.
• $H_C(\mathcal{D})$ is the Entropy of the dataset given the complete (i.e., fully connected) network $C$. In the complete network, all nodes are directly connected to all other nodes. Therefore, the complete network $C$ is an exact representation of the chain rule. As such, it does not utilize any conditional independence assumptions for representing the Joint Probability Distribution.
• $N$ is the size of the dataset.