Title: Math and science / INF ML AI / probabilistic graphical models

Title: Motivation for graphical models
Daphne Koller describes the motivation for graphical models:
With the goal of representing a joint distribution \( P \) over some set of random variables \( \mathcal{X} = \{X_1, ..., X_n\} \). Even in the simplest case where these variables are binary-valued, a joint distribution requires specifying \( 2^n - 1 \) numbers. For all but the smallest \( n \), the explicit representation of the joint distribution is unmanageable from every perspective. It is expensive both in terms of computation and memory. The numbers can be very small and not correspond to events that people can reaonably contemplate. If we wanted to learn the distribution from data, we would need ridiculously large amounts of data to estimate this many parameters robustly. These problems were the main barrier to the adoption of probabilistic methods for expert systems until the development of the methodologies described in this book.
Probabilistic graphical models use a graph-based representation as the basis for compactly encoding a complex distribution over a high-dimensional space.
Source: Probabilistic Graphical Models
Daphne Koller

Title: Compression and modularity of probabilistic models
Q: A probability space with a sample space \( I \times G \times S \), intelligence \( I = \{i^0, i^1\} \), grade \( G = \{g^0, g^1, g^2 \} \) and SAT score \( S = \{s^0, s^1\} \) in general requires [...] independent parameters to define a probability measure.
[From here on we abuse the notions of random variables & probability distributions]
If we know that grade and SAT score are independent given intelligence (knowing the grade in addition to knowing the intelligence gives no extra information regarding the SAT score in comparison to [...]), then we can write:
\[ P(I, S, G) = P(S \vert I)P(G \vert I)P(I) \]
This is a factorization of the joint distribution into a product of three conditional probability distributions. The parameterization involves three bernoulli distributions, \( P(I), P(S \vert i^0) \), \( P(S \vert i^1) \), and two three-valued multinomial distributions,  \( P(G \vert i^0), P(G \vert i^1) \). The total independent parameter count is thus [...]. Thus, the representation is more compact.
It is important to note another advantage of this way of representing the joint: modularity. When we added the new variable G, the joint distribution changed entirely. Had we used the explicit representation of the joint, we would have had to write down twelve new numbers. In the factored representation, we could reuse our local probability models for the variables \( I \) and \( S \), and specify only the probability model for \( G \) - the CPD \( P(G \vert I) \). This property will turn out to be invaluable in modeling real-world systems.
A: 11; knowing the intelligence alone; 7

Title: Belief Networks (by Koller)
Koller's approach to Belief networks (which she calls Bayesian Networks) is more intuative than Barber's. Consider the student model:
Difficulty: difficulty of a test. Grade: a course grade received by the student. SAT: the student's SAT score. Letter: whether the student's letter of recommendation from the course professor was positive or not. The professor only consults the student's recorded course grade.
Koller proceeds by enumerating the independent assumptions in this model. We can reason that:
1. The professor's recommendation letter depends only on the student's grade in the class.
This can be expressed as:
\[ (L \perp I, D, S \vert G) \]
In other words, once we know the student's grade, our beliefs about the quality of the recommendation letter are not influenced by information about any of the other variables.
2. The student's SAT score depends only on the student's intelligence:
\[ (S \perp D, G, L \vert I) \]
3. Once we know that a student has high intelligence, his SAT score gives no additional information towards predicting his grade:
\[ (G \perp S \vert I, D) \]
4. Intelligence is independent of the test difficulty:
\[ (I \perp D) \]
5. Knowing that a student is smart (or not) does not influence our beliefs in the test difficulty:
\[ (D \perp I, S) \]
Koller describes this whole thing in more detail. She explains how, intuitively, a parent variable "shields" its descendants from probabilistic influence from other variables. Once I know the value of the parents, no information relating directly or indirectly to the parents or other ancestors can influence my beliefs.
With this model in mind, the formal definition follows quite naturally.
Bayesian network, definition
A Bayesian network structure \( G \) is a directed acyclic graph whose nodes represent random variables \( X_1, ..., X_n \). Let \( Pa_{X_i}^G \) denote the parents of \( X_i \) in \( G \), and \( \operatorname{NonDescendants}_{X_i} \) denote the variables in the graph that are not descendants of \( X_i \). Then \( G \) encodes the following set of conditional independence assumptions, called the local independencies, and denoted by \( \mathcal{I}_{l}(G) \):
\[ \text{For each variable } X_i: (X_i \perp \operatorname{NonDescendants}_{X_i} |Pa_{X_i}^{G}) \]
In other words, the local independencies state that each node \( X_i \) is conditionally independent of its nondescendants given its parents.
For the student case, the independence statements are the 5 above.