blog

Overview and Motivation
- some of the usage: image segmentation, predisposing factors of symptoms, textual information extraction, multi-sensor integration (such as traffic)
- what is model: The model is a declarative representation of our understanding of the world. So it is a representation within the computer that captures our understanding of what these variables are and how they interact with each other.
- probabilistic -> uncertainty
- think of the world as a bunch of random variables and each capture some facet of the world. Goal is to capture the uncertainty of the world in terms of the probability distribution (joint distribution)
- Graphical models such as Bayesian networks (directed graph), Markov networks (undirected graph)
- Distribution:
  - Joint probability, independent (if there are 12 cases then 11 of them are independent because they sum to 1)
  - Conditioning: Reduction and renormalization
  - Marginalization: sum over one RV of a joint probability: $\sum _{I}P(I,D) = P(D)$
- Factor:
  - fundamental building block for defining distributions in high-dimentional spaces
  - set of basic operations for manipulating these probability distributions
  - A factor really is a function, or a table. It takes a bunch of arguments. In this case, a set of random variables X1 up to XK, and just like any function it gives us a value for every assignment to those random variables.
  - the scope of a factor is the RV it can take
  - one factor we will use is conditional probability distribution (CPD) such as P(G I,D)
  - factor product: it is like join two tables and multiply the corresponding factor value
  - factor marginalization: sum over one RV and reduce the table
  - factor reduction: eliminate a specific value of a RV or eliminate a RV (the difference betwee this and above is that one is elimination, the other is sum)

Bayesian network fundamentals

Semantics & Factorization

Construct Bayesian network for a student example, conditional probability distribution is used in a node that is linked by other nodes. For instance, we have P(D), P(I), P(G

I,D), P(S

I), P(L

We can apply chain rule to get joint distribution of all the RVs. For example P(D,I,G,S,L) = P(D)P(I)P(G

D,I)P(S

I)P(L

So in general a Bayesian network is a acyclic graph and for each node Xi we have a CPD P(Xi

Parent(Xi)). The bayesian network represents a joint distribution via the chain rule for BN: $P(X_1 … X_n) = \prod _{i} P(X_i

Parent_G (X_i))$

some notation: let G be a graph over X1…Xn; P factorizes over G if $P(X_1 … X_n) = \prod _{i} P(X_i

Parent_G (X_i))$ hold

Reasoning pattern: used to adjust posterior probability
- Causual reasoning: reason from top to down (condition on parent)
- evidence reasoning: reason from bottom to top (condition on child)
- intercausal reasoning: condition on both parent and child
Flow of probabilistic influence
- when can X influence Y
  - X -> Y yes
  - Y -> X yes
  - X -> W -> Y yes
  - X <- W <- Y yes
  - X <- W -> Y yes
  - X -> W <- Y (v structure) No
- A trail X1 … Xn is active if it has no v-structure
- When can X incluence Y given evidence about Z
  - X -> Y yes
  - Y -> X yes
  - X -> W -> Y yes if W is not in Z; otherwise no
  - X <- W <- Y yes if W is not in Z; otherwise no
  - X <- W -> Y yes if W is not in Z; otherwise no
  - X -> W <- Y (v structure) No if W and its descendant are not observed; otherwise yes

Bayesian networks independence

independence: P(a,b) = P(a)P(b); P(a

b) = P(a); P(b

a) = P(b). This applies for both a,b as events and RV

conditional independence:

For random variables X,Y,Z, P

= (satisfy) $(X \bot Y

Z)$ if P(X,Y

Z) = P(X

Z)P(Y

Z); or P(X

Y,Z) = P(X

Z); or P(Y

X,Z) = P(Y

conditioning can both give and lose independence

independencies in Bayesian networks

d-separation: X and Y are d-separated in G given Z if there is no active trail in G between X and Y given Z. Notation is d-sep_{G}(X,Y

Z). Theorem if p factorizes over G, and d-sep_{G}(X,Y

Z) then p satisfies (X \perpendicular Y

Any node is d-separated from its non-descendants given its parents -> if P factorizes over G, then in P, any variable is independent of its non-descendants given its parents

I-maps: independency map. My understanding of I-map is just the tree structure that connects every node. (G is an I-map of P, all independencies in G are also in P)

d-separation in G -> P satisfies corresponding independence statment I(G) = {(X \perpendicular Y

Z) : d-sep_{G}(X,Y

Z)}. independence corresponds to d-separation

If P satisfies I(G), we say that G is an I-map of P. Notice G represents the whole graph (not some nodes)
- As an example G1: D I; in this case I(G1) = {D \perpendicular I} since D and I are independent
- G2: D->I; I(G2) = none
Theorem: If P factorizes over G, then G is an I-map for P (can read from G independencies in P regardless of parameters)
Theorem: If G is an I-map for P, then P factorizes over G

Naive Bayes

observe features (x1…xn) and infer class (C)
assumption: (xi \perpendicular xj C) for all xi, xj

P(C, X1, …, Xn) = $P(C)\prod {i}^{n}P(X{i}

C)$ where P(C) is the prior probability

used for text classification. Effective in domains with many weakly relevant features. Strong independence assumptions reduce performance when many features are strongly correlated.