Category Archives: [UCSD] Artificial Intelligence

[Probability] Belief Network

Belief Network

A belief network is a DAG in which

  • nodes represent random variables
  • edges represent conditional dependencies
  • CPT denotes how each node depend on its parents

BN = DAG + CPTs

Constructing a BN

  1. Choose random variables
  2. Choose ordering of the nodes (best is to start with root cases, then what they influence)
  3. While there are variables left
    1. Add a node X to BN
    2. Set the parents of X to be the minimal set satisfying X
    3. Define CPT P(X|Parents(Xi)

Advantages of BN

  1. More compact representation of joint distributions (originally 2^k for k values, O(n 2^k) with BN)
  2. Clean separation of qualitative vs quantitative knowledge; DAG encodes (conditional independence), CPTs encode numerical influences.

[Probability] Probability

Syntax

Discrete random variable X
Domain of possible value {x_1, x_2, …, x_n}
Unconditional (prior) probability P(X=x_i)
Basic axioms

  • P(X=x_i) >= 0
  • sum P(X=x_i) = 1
  • P(X=x_i or X=x_j) = P(X=x_i) + P(X=x_j) if x_i ~= x_j

Conditional Probabilities

P(X=x_i|Y=y_j) : probability that X=x_i given Y=y_j
In general, P(X=x_i|Y=y_j) ~= P(X=x_i)
Axioms also apply

  • P(X=x_i|Y=y_j) >= 0
  • sum_i P(X=x_i | Y=y_j) = 1

Joint Probabilities

P(X=x_i, Y=y_j) : probability that X=x_i and Y=y_j

* Easier for experts to assess conditional probabilities over single events than joint probabilities over compound events.

Shorthand notation

Implied universality : P(X,Y) = P(X|Y)P(Y) = P(Y|X)P(X) implies that equality is true for all assignments
Implied assignment : P(x,y,z) = P(X=x, Y=x, Z=z)

Rules

General

Product Rule: P(A,B,C,…) = P(A)P(B|A)P(C|A,B)…
Bayes Rule: P(X|Y) = P(Y|X)P(X) / P(Y)
Marginalization: P(X) = sum_y P(X,Y=y)

Conditionalized

Product Rule: P(A,B,C,… | E) = P(A | E)P(B|A, E)P(C|A,B, E)…
Bayes Rule: P(X|Y, E) = P(Y|X, E)P(X | E) / P(Y | E)
Marginalization: P(X | E) = sum_y P(X,Y=y | E)

Independence

Marginal

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

Conditional

P(X|Y,E) = P(X|E)
P(Y|X,E) = P(Y|E)
P(X,Y|E) = P(X|E)P(Y|E)