Conditional Independence

$𝐴$ and $𝐵$ are independent $\Rightarrow$ $𝑃 (𝐴 | 𝐵) = 𝑃 (𝐴)$ and $𝑃 (𝐵 | 𝐴) = 𝑃 (𝐵)$ .

Bayes theorem:

𝑃 (𝐺 | 𝐻) = \frac{𝑃 (𝐺 \cap 𝐻)}{𝑃 (𝐻)}

So, in the case $𝐴$ and $𝐵$ are independent,

\begin{matrix} 𝑃 (𝐴 | 𝐵) = \frac{𝑃 (𝐴 \cap 𝐵)}{𝑃 (𝐵)} = 𝑃 (𝐴) \\ 𝑃 (𝐴 \cap 𝐵) = 𝑃 (𝐴) 𝑃 (𝐵) \end{matrix}

For conditional independence, we say $𝐴$ and $𝐵$ are independent given $𝐶$ .

\begin{matrix} 𝑃 (𝐴 | 𝐵 \cap 𝐶) = 𝑃 (𝐴 | 𝐶) \\ 𝑃 (𝐵 | 𝐴 \cap 𝐶) = 𝑃 (𝐵 | 𝐶) \end{matrix}

In English, $𝑃 (𝐴)$ is the same as long as $𝐶$ has happened, regardless of whether or not $𝐵$ happens.

We want to show that since $𝐴$ and $𝐵$ are conditionally independent:

𝑃 (𝐴 \cap 𝐵 | 𝐶) = 𝑃 (𝐴 | 𝐶) 𝑃 (𝐵 | 𝐶)

Here,

𝑃 (𝐴 \cap 𝐵 | 𝐶) = 𝑃 (𝐵 | 𝐶) 𝑃 (𝐴 | 𝐵 \cap 𝐶)

means “assuming $𝐶$ is true, the probability of $𝐴$ and $𝐵$ both happening is the same as the probability $𝐵$ happens when C is first true, and then $𝐴$ happens on top of that”.

Bayes’ theorem backs this up:

\begin{matrix} 𝑃 (𝐴 | 𝐵 \cap 𝐶) = \frac{𝑃 (𝐴 \cap 𝐵 \cap 𝐶)}{𝑃 (𝐵 \cap 𝐶)} \\ 𝑃 (𝐵 | 𝐶) = \frac{𝑃 (𝐵 \cap 𝐶)}{𝑃 (𝐶)} \\ 𝑃 (𝐴 \cap 𝐵 | 𝐶) = \frac{𝑃 (𝐴 \cap 𝐵 \cap 𝐶)}{𝑃 (𝐶)} = \frac{𝑃 (𝐵 \cap 𝐶)}{𝑃 (𝐶)} \times \frac{𝑃 (𝐴 \cap 𝐵 \cap 𝐶)}{𝑃 (𝐵 \cap 𝐶)} \end{matrix}

So,

𝑃 (𝐴 \cap 𝐵 | 𝐶) = 𝑃 (𝐴 | 𝐶) \times 𝑃 (𝐵 | 𝐴 \cap 𝐶) = 𝑃 (𝐵 | 𝐶) \times 𝑃 (𝐴 | 𝐵 \cap 𝐶)

Remembering Eq. 3:

\begin{aligned} 𝑃 (𝐴 \cap 𝐵 | 𝐶) & = 𝑃 (𝐴 | 𝐶) \times 𝑃 (𝐵 | 𝐶) = 𝑃 (𝐵 | 𝐶) \times 𝑃 (𝐴 | 𝐶) \\ 𝑃 (𝐴 \cap 𝐵 | 𝐶) & = 𝑃 (𝐴 | 𝐶) \times 𝑃 (𝐵 | 𝐶) \end{aligned}

This is the naïve Bayes assumption (also called conditional independence of the evidence).

Once the class is known, the features do not influence each other:

𝑃 (𝑒_{1}, \dots, 𝑒_{𝑛} | ℎ) = 𝑃 (𝑒_{1} | ℎ) 𝑃 (𝑒_{2} | ℎ) \dots 𝑃 (𝑒_{𝑛} | ℎ) = \prod_{𝑘 = 1}^{𝑛} 𝑃 (𝑒_{𝑘} | ℎ) .

Without this assumption, the chain rule from Eq. 5 causes an uncontrolled explosion of terms:

𝑃 (𝑒_{1} | ℎ) 𝑃 (𝑒_{2} | ℎ, 𝑒_{1}) 𝑃 (𝑒_{3} | ℎ, 𝑒_{1}, 𝑒_{2}) \dots