Bayesian NetworkProbability Theory

Probability Space

• Sample space $\mathrm{\Omega }$
  • a set of all possible outcomes of a random experiment.
• Event
  • an event is a subset of the sample space $\mathrm{\Omega }$.
• $\sigma$-algebra $\mathcal{F}$ on sample space:
  • a collection of events for which it makes sense to assign probability, satisfies
    • i. The empty set $\mathrm{\varnothing }$ is in $\mathcal{F}$;
    • ii. The union of any set in $\mathcal{F}$ is also in $\mathcal{F}$;
    • iii. If a set $S$ is in $\mathcal{F}$, the complement $S^c$ is also in $\mathcal{F}$.
• A measurable event
  • A measurable event $S\subseteq \mathrm{\Omega }$ is a subset of the sample space, to which we are willing to assign probability.
  • $S_{female}=\{\text{female students}\}$ is an event that the randomly selected student is female.
  • Number of events: $2^{|\mathrm{\Omega }|}$ where $|\mathrm{\Omega }|$ is the number of samples.
  • A measurable event that is an element of the $\sigma$-algebra satisfies these three basic properties:
    1. It contains empty event $\mathrm{\varnothing }$, or say $\mathrm{\varnothing }$ is in the $\sigma$-algebra.
    2. [Closed under union] If $\alpha ,\beta$ are measurable, then $\alpha \cup \beta$ is measurable. Or say, the union of these events is in the $\sigma$-algebra.
    3. [Closed under complementation] If $S$ is measurable, then the complement $S^c$ is also measurable.

Properties of Probability

Probability distribution

A Probability distribution $P$ over $(\mathrm{\Omega },S)$ is a function mapping a measurable $S$ to real values, satisfying the following conditions:

1. $P(\alpha )\ge 0,\mathrm{\forall }\alpha \in S$. Probabilities are nonnegative.

2. $P(\mathrm{\Omega })=1$, trivial event: all possible outcomes have the maximal probability of 1.

3. Additivity: If $\alpha ,\beta \in S$ and are disjoint events $\alpha \cap \beta =\mathrm{\varnothing }$, then

   $$P(\alpha \cup \beta )=P(\alpha )+P(\beta )$$

   The probability that one of the two mutually exclusive (disjoint) events will occur is the sum of the two, which also implies:

   $$P(\alpha \cap \beta )=P(\mathrm{\varnothing })=0$$$$P(\alpha \cup \beta )=P(\alpha )+P(\beta )-P(\alpha \cap \beta )$$

---

Example: $|\mathrm{\Omega }|$ be the number of all UIC students. We can define the probability measure:

$$P(S_{female})=\frac{|S_{female}|}{|\mathrm{\Omega }|}$$

so $P(S_{female})$ is the fraction of female students in UIC.

---

Key properties:

1. Monotonicity: If $A\subseteq B$, then $P(A)\le P(B)$.

2. Intersection bound: $P(A\cap B)\le min(P(A),P(B))$.

3. Union bound: $P(A\cup B)\le P(A)+P(B)$.

4. Complement rule: $P(\mathrm{\Omega }\setminus A)=1-P(A)$.

5. Law of total probability: If $A_1,A_2,\dots ,A_k$ are disjoint events such that $\bigcup _{i=1}^k{A}_i=\mathrm{\Omega }$, then:

   $$\sum _{i=1}^{k}P(A_i)=1$$

---

A probability space $(\mathrm{\Omega },\mathcal{F},P)$ consists of:

1. A sample space $\mathrm{\Omega }$;
2. A $\sigma$-algebra $\mathcal{F}$ of measurable events;
3. A probability measure $P$.

Random variable

Random variable: is defined by a function associated with each outcome $\omega \in \mathrm{\Omega }$:

---

Discrete random variables:

1. Categorical (or discrete), e.g. gender, faculty.
2. The probability mass function of a random variable $X$:$$P(X):{\mathrm{\Omega }}_X\to [0,1]$$Example:$$P(\text{gender}=f)=\frac{1}{5}$$
3. $P(x)=p_X(x)=P(X=x)$ with properties:
   • $0\le p_X(x)\le 1$
   • $\sum _{x\in A}{p}_X(x)=P(X\in A)$ (countable unions of disjoint sets)

• $\sum _{x\in \mathrm{\Omega }}{p}_X(x)=P(\mathrm{\Omega })=1$

---

Continuous random variables:

1. Values in a given range, e.g. height, weight.

2. The probability density function (PDF): $f(x)\ge 0$, and:

   $${\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(x)dx=1$$

3. The cumulative distribution function (CDF):

   $$P(X\le x)=F(x)={\int }_{-\mathrm{\infty }}^{x}f(x)dx$$

   Then we have $F(-\mathrm{\infty })=0$ and $F(\mathrm{\infty })=0$.

   We have:

   $$P(a\le X\le b)={\int }_a^{b}f(x)dx=F(b)-F(a)$$

   And note that:

   $$P(X=a)=0$$

   For continuous random variables, the probability at a point is zero.

Domain of a random variable ${\mathrm{\Omega }}_X$:

Example: ${\mathrm{\Omega }}_{\text{gender}}=\{f,m\}$, ${\mathrm{\Omega }}_{\text{height}}=(0,3)$.

For any state $x$ of a random variable $X$, $\{\omega \in \mathrm{\Omega }\mid X(\omega )=x\}$ is an event.

Multivariate probability

Multivariate Probability: Suppose there are two random variables $X$ and $Y$.

(a) A joint probability mass function $P(X,Y)$ over these random variables is

$$P(X=x,Y=y)$$

It describes the probability distribution of multiple variables together.

(b) Example: Students at university with random variables:

1. Intelligence: low $i^0$, high $i^1$
2. Scores: low $s^0$, high $s^1$

Example table of joint distribution $P(I,S)$:

$I$	$S$	$P(I,S)$
$i^0$	$s^0$	$0.665$
$i^0$	$s^1$	$0.035$
$i^1$	$s^0$	$0.06$
$i^1$	$s^1$	$0.24$

Table 1: Joint distribution $P(I,S)$.

The joint probability $P(I,S)$ is given in the table below:

i. The joint distribution $P(X,Y)$ contains information about all aspects of the relations among these 2 random variables.
ii. In theory, one can answer any query about relations among the variables based on the joint distribution.

(c) Marginal distribution $P(X)$ is the sum of the joint distribution over a set of random variables:

$$P(X=x)=\sum _{y}P(X=x,Y=y)$$

It is obtained by summing out other variables from the joint distribution.

i. Query 1: Based on the joint distribution table, what is the probability of a randomly selected student being intelligent $I=i^1$ (sum over $s$)?

$$P(i^1)=P(i^1,s^0)+P(i^1,s^1)=0.06+0.24=0.3$$

$P$	$i^0$	$i^1$	$P(S)$
$s^0$	0.665	0.06	0.725
$s^1$	0.035	0.24	0.275
$P(I)$	0.7	0.3	1

Table 2: Table with joint and marginal distribution.

ii. Query 2: What is the probability that a random student has received low scores $S=s^0$?

$$P(s^0)=\sum _{n=0}^{1}P(i^n,s^0)=P(i^0,s^0)+P(i^1,s^0)=0.665+0.06=0.725$$

Conditional Probability

Conditional Probability: $\alpha$ is an event of non-zero probability, the conditional probability of any event $\beta$ given $\alpha$ is defined as:

$$P(\beta \mid \alpha )=\frac{P(\alpha ,\beta )}{P(\alpha )}$$

So the joint distribution can also be written as by rearranging the conditional probability definition formula:

$$P(\alpha ,\beta )=P(\alpha )P(\beta \mid \alpha )$$

---

(a) Query 3: What is the probability an intelligent student gets low scores? And what is the probability they get high scores?
Note that here intelligent student $i^1$ is a condition. Based on this condition, we want to find out the chance for them to get high or low scores.

$$P(s^0\mid i^1)=\frac{P(s^0,i^1)}{P(i^1)}=\frac{0.06}{0.3}=0.2$$$$P(s^1\mid i^1)=\frac{P(s^1,i^1)}{P(i^1)}=\frac{0.24}{0.3}=0.8$$

Note that:

$$\sum _{n=0}^{1}P(s^n\mid i^1)=1$$

---

(b) Query 4: What is the probability a student got a high score is not intelligent?

$$P(i^0\mid s^1)=\frac{P(s^1,i^0)}{P(s^1)}=\frac{0.06}{0.275}\approx 0.218$$

Marginal Independence

Marginal Independence: An event $\alpha$ is independent of event $\beta$ if:

$$P(\alpha \mid \beta )=P(\alpha )$$

or

$$P(\beta )=0$$

Alternative definition: $\alpha$ and $\beta$ are independent if and only if:

$$P(\alpha ,\beta )=P(\alpha )P(\beta )$$

Intuitively, $\alpha$ and $\beta$ are independent means that observing $\beta$ does not have any effect on the probability of $\alpha$.
For example: $\alpha$: the first toss of a coin is head, $\beta$: the second toss of a coin is head.

---

(a) Query 5: Are intelligence and scores independent?

$$P(s^0,i^0)\ne P(s^0)P(i^0)$$

Actually, $P(S,I)\ne P(S)P(I)$, so these two variables are NOT independent.
It means knowing the intelligence gives us some knowledge about their scores, and vice versa.

Bayes’ theorem, inverse conditional probability

$$P(\alpha \mid \beta )=\frac{P(\alpha ,\beta )}{P(\beta )}=\frac{P(\alpha )P(\beta \mid \alpha )}{P(\beta )}$$

because:

$$P(\alpha ,\beta )=P(\alpha )P(\beta \mid \alpha )=P(\beta )P(\alpha \mid \beta )$$

---

Example 1: Medical Testing
Suppose a disease affects 1% of the population. We also have a test for this disease that is 99% accurate.
This means that if a person has the disease, the test will be positive 99% of the time, and if a person does not have the disease, the test will be negative 99% of the time.
Now, if a person tests positive, what is the probability that they actually have the disease?

This is not immediately obvious because, although the test is 99% accurate, the disease only affects 1% of the population. We can use Bayes' Theorem to find out.

---

Solution

• Let $\alpha$ be the event that the person has the disease, $\mathrm{\neg }\alpha$ (or ${\alpha }^c$) is the complement (does not have the disease).
• Let $\beta$ be the event that the person tests positive, and $\mathrm{\neg }\beta$ (or ${\beta }^c$) be the event that the person tests negative.

We want to find $P(\alpha \mid \beta )$. Now we know:

1. Prior distribution: $P(\alpha )=0.01$ (marginal probability of $\alpha$), the probability that a person has the disease is 1%.
2. $P(\mathrm{\neg }\alpha )=0.99$
3. $P(\beta \mid \alpha )=0.99$ (conditional probability): The probability that the person tests positive given that they have the disease is 0.99 (because the test is 99% accurate).
4. $P(\beta \mid \mathrm{\neg }\alpha )=0.01$

---

Joint Probabilities:

• $P(\beta ,\alpha )=P(\beta \mid \alpha )P(\alpha )=0.99\times 0.01=0.0099$
• $P(\beta ,\mathrm{\neg }\alpha )=P(\beta \mid \mathrm{\neg }\alpha )P(\mathrm{\neg }\alpha )=0.01\times 0.99=0.0099$

---

Marginal Probability $P(\beta )$:

• $P(\beta )=P(\beta ,\alpha )+P(\beta ,\mathrm{\neg }\alpha )$
• $P(\beta )=0.0099+0.0099=0.0198$

---

Posterior Distribution:

Finally, substitute into Bayes' theorem to find the posterior distribution:

$$P(\alpha \mid \beta )=\frac{P(\beta ,\alpha )}{P(\beta )}=\frac{P(\alpha )P(\beta \mid \alpha )}{P(\beta )}=\frac{0.99\times 0.01}{0.99\times 0.01+0.01\times 0.99}=0.5$$

---

Although the test is 99% accurate, a person who tests positive $\beta$ only has a 50% chance of actually having the disease. This is because the disease is so rare ($P(\alpha )=0.01$ in the population).

Chain Rule

$$P(\alpha ,\beta )=P(\alpha )P(\beta \mid \alpha )$$$$P(\alpha ,\beta ,\gamma )=P(\alpha )P(\beta \mid \alpha )P(\gamma \mid \alpha ,\beta )$$

This is how we compute the joint probability. And it is the direct result of conditional probability.

---

$$P(\beta \mid \alpha )=\frac{P(\alpha ,\beta )}{P(\alpha )}$$

and

$$P(\gamma \mid \alpha ,\beta )=\frac{P(\alpha ,\beta ,\gamma )}{P(\alpha ,\beta )}=\frac{P(\alpha ,\beta ,\gamma )}{P(\alpha )P(\beta \mid \alpha )}$$

---

If $\alpha$ and $\beta$ are independent, we have:

$$P(\alpha ,\beta )=P(\alpha )P(\beta )$$

which means:

$$P(\beta \mid \alpha )=P(\beta )$$

Conditional Independence

(a) Two events $X$ and $Y$ are conditionally independent given $Z$ if:

$$P(X\mid Y,Z)=P(X\mid Z)$$

Then $X$ is conditionally independent of $Y$ given $Z$, written as:

$$(X\perp Y\mid Z)$$

---

Meaning:

(b) If we know $Z$ already, knowing $Y$ does not give us additional information about $X$.

(c) $Y$ might contain some information about $X$, but all this information is also contained in $Z$.

---

(d) Symmetry:
If $(X\perp Y\mid Z)$, then:

$$(Y\perp X\mid Z)$$

(e) Equivalent definition

$$P(X,Y|Z)=P(X|Z)P(Y|Z)$$

Proposition

Proposition: $(X\perp Y\mid Z)$ if and only if one of the following conditions hold:

(a)

$$P(X\mid Y,Z)=P(X\mid Z)$$

(b)

$$P(X,Y\mid Z)=P(X\mid Z)P(Y\mid Z)$$

(c)

$$P(X,Y,Z)=P(X\mid Z)P(Y\mid Z)P(Z)\text{if}P(Z)>0$$

---

Exercise:

i. (a) $\to$ (b) given and using the chain rule:

$$P(X\mid Y,Z)=\frac{P(X,Y,Z)}{P(Y,Z)}$$

Expanding using the chain rule:

$$P(X\mid Y,Z)=\frac{P(X,Y\mid Z)P(Z)}{P(Y\mid Z)P(Z)}$$

Simplify the equation:

$$P(X\mid Y,Z)=\frac{P(X,Y\mid Z)}{P(Y\mid Z)}=P(X\mid Z)$$

So, rearranging this equation, we have (b).

ii. (a) $\to$ (c) given and using the chain rule:

$$P(X\mid Y,Z)=\frac{P(X,Y\mid Z)}{P(Y\mid Z)}=\frac{P(X,Y,Z)}{P(Y,Z)}=P(X\mid Z)$$$$P(X,Y,Z)=P(Y,Z)P(X\mid Z)$$$$P(X,Y,Z)=P(X\mid Z)P(Y\mid Z)P(Z)$$

Expectation

Expectation

(a) Expectations: weighted average of discrete variables

$$E_p[X]=\sum _{x\in \text{val}(X)}x\cdot P(X=x)$$

(b) Properties:
i. Constant $E[a]=a$
ii. Linearity of expectation:

$$E[X+Y]=E[X]+E[Y]$$$$E[aX]=aE[X]$$

(c) Products of two variables:
i. If $X$ and $Y$ are independent, then

$$E[X\cdot Y]=E[X]E[Y]$$

(d) Conditional expectation

$$E_p[X\mid y]=\sum _{x}x\cdot P(x\mid y)$$

Variance

Variance: a measure of how concentrated the distribution of $X$ is around its mean.

(a) A variance is defined as

$${\text{var}}_p[X]=E[(X-E[X]{)}^2]$$

or

$${\text{var}}_p[X]=E[X^2]-(E[X]{)}^2$$

This is a very useful formula to compute the variance. Try to derive this using the properties of expectations!

(b) Properties:
i. Constant

$$\text{var}[a]=0$$

ii. Quadratic scale

$$\text{var}[aX]=a^2\text{var}[X]$$

iii. If $X$ and $Y$ are independent, then

$$\text{var}[X+Y]=\text{var}[X]+\text{var}[Y]$$

(c) Standard deviation

$${\sigma }_X=\sqrt{\text{var}[X]}$$

a normalized measure of distance from the expectation.

Discrete Random Variables

(a) Bernoulli trials: $X\sim \text{Bernoulli}(p)$ where $0\le p\le 1$, the outcome of a single trial, e.g., flip a coin $(H=1,T=0)$ comes up heads with probability $p$

$$P(x)=\{\begin{array}{ll}p& x=1\\ 1-p& x=0\end{array}$$

• 期望 (Mean): $E[X]=p$
• 方差 (Variance): $Var[X]=p(1-p)$

---

(b) Binomial distribution: $X\sim \text{Binomial}(n,p)$: $X$ is the number of heads in $n$ independent flips with heads probability $p$,

$$P(X=k)=(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k}$$

$k$ is the number of successes in $n$ independent trials.

• 期望 (Mean): $E[X]=np$
• 方差 (Variance): $Var[X]=np(1-p)$

---

(c) Multinomial distribution: $X=(X_1,X_2,...,X_k)$ represents the number of outcomes in each of $k$ categories in $n$ independent trials, where the probability of outcome $i$ is $p_i$

$$P(X=x)=\frac{n!}{x_1!x_2!\cdots x_k!}{p}_1^{x_1}{p}_2^{x_2}\cdots p_k^{x_k}$$

with

$$\sum _{i=1}^k{x}_i=n,\sum _{i=1}^k{p}_i=1$$

• 期望 (Mean): $E[X_i]=n{p}_i$ (其中 $X_i$ 是第 i 个类别中的事件数量)
• 方差 (Variance): $Var[X_i]=n{p}_i(1-p_i)$
• 协方差 (Covariance): $Cov(X_i,X_j)=-n{p}_i\ast p_j$ (其中 $i!=j$，表示不同类别之间的协方差)