Probabilistic Reasoning and Learning

Conditional probability tables (CPTs)

Noisy-OR CPT

$$P\left(Y=1 \mid X_{1}, X_{2}, \ldots, X_{k}\right)=1-\prod_{i=1}^{k}\left(1-p_{i}\right)^{X_{i}}$$

Sigmoid CPT

$$P(Y=1 \mid X_1,X_2,\ldots,X_k)~=~\sigma\left(\sum_{i=1}^k\theta_iX_i\right)$$

$$\sigma(z)=\frac1{1+e^{-z}}$$

d-separation

Blocked paths

1. $Z \in E$, edges align
2. $Z \in E$, edges diverge
3. $Z \notin E, \mathrm{desc}(Z)\cap{E}=\varnothing$ , edges converge

Polytrees

Inference

$$P(X=x \mid E) \propto \underbrace{P\left(X=x \mid E_{X}^{+}\right)}_{\text {from above }} \underbrace{P\left(E_{X}^{-} \mid X=x\right)}_{\text {from below }}$$

$$P\left(X=x \mid E_{X}^{+}\right)=\sum_{\vec{u}} \underbrace{P(X=x \mid \vec{U}=\vec{u})}_{\text {CPT }} \prod_{i=1}^{m} \underbrace{P\left(U_{i}=u_{i} \mid E_{U_{i} \backslash X}\right)}_{\text {recursive instance }}$$

$$P\left(E_{Y_{j} \backslash X} \mid X=x\right) \propto \sum_{y_{j}} \underbrace{P\left(E_{Y_{j}}^{-} \mid Y_{j}=y_{j}\right)}_{\text {recursive instance }} \sum_{\vec{z}_{j}} \underbrace{P\left(y_{j} \mid \vec{z}_{j}, x\right)}_{\text {CPT }} \prod_{k} \underbrace{P\left(z_{j k} \mid E_{Z_{j k} \backslash Y_{j}}\right)}_{\text {recursive instance }}$$

Exact inference in loopy BNs

Node clustering

• CPTs grow exponentially when nodes are clustered.

Cutset conditioning

• The number of times that we must run the polytree algorithm grows exponentially with the size of the cutset.

Approximate inference in loopy BNs

Rejection sampling

$$P(Q=q \mid E=e) \approx \frac{N(q, e)}{N(e)}=\frac{\sum_{i=1}^{N} I\left(q, q_{i}\right) I\left(e, e_{i}\right)}{\sum_{i=1}^{N} I\left(e, e_{i}\right)}$$

Likelihood weighting

$$P(Q=q \mid E=e) \approx \frac{\sum_{i=1}^{N} I\left(q, q_{i}\right) P\left(E=e \mid pa(E)=p_{i}\right)}{\sum_{i=1}^{N} P\left(E=e \mid pa(E)=p_{i}\right)}$$

Markov chain Monte Carlo

• Initialization

  Fix evidence nodes to observed values $e, e'$.

  Initialize non-evidence nodes to random values.

• Repeat $N$ times

  Pick a non-evidence node $X$ at random.

  Use Bayes rule to compute $P(X \mid B_X)$.

  Resample $x \sim P(X \mid B_X)$.

  Take a snapshot of all the nodes in the BN.

• Estimate

  $$P(Q=q \mid E=e)~\approx\frac{N(q)}N$$

Learning in BNs

Computing the log-likelihood

$$\begin{aligned} \mathcal{L} & =\sum_{i=1}^{n} \sum_{t=1}^{T} \log P\left(x_{i}^{(t)} \mid \mathrm{pa}_{i}^{(t)}\right) \\ & =\sum_{i=1}^{n} \sum_{x} \sum_{\pi} \operatorname{count}\left(X_{i}=x, \mathrm{pa}_{i}=\pi\right) \log P\left(X_{i}=x \mid \mathrm{pa}_{i}=\pi\right) \end{aligned}$$

Maximum likelihood CPTs

$$P_{\mathrm{ML}}(X_i=x)=\frac{\mathrm{count}(X_i=x)}T=\frac{1}{T} \sum_{t} I\left(x_{i t}, x\right)$$

$$P_{\mathrm{ML}}(X_i=x \mid \mathrm{pa}_i=\pi)=\frac{\mathrm{count}(X_i=x,\mathrm{pa}_i=\pi)}{\mathrm{count}(\mathrm{pa}_i=\pi)}=\frac{\sum_{t} I\left(x_{i t}, x\right) I\left(\mathrm{pa}_{i t}, \pi\right)}{\sum_{t} I\left(\mathrm{pa}_{i t}, \pi\right)}$$

Linear regression

Gaussian conditional distribution

$$P\left(y \mid \vec{x}\right)=\frac1{\sqrt{2\pi\sigma^2}}\exp\left\{-\frac{(y-\vec{w}\cdot\vec{x})^2}{2\sigma^2}\right\}$$

$$\mathcal{L}({\vec{w}},{\sigma^2})=-\frac12\sum_{t=1}^T\left[\log(2\pi{\sigma^2})+\frac{(y_t-\vec{w}\cdot\vec{x_t})^2}{\sigma^2}\right]$$

$$\begin{aligned} \mathbf{A} & =\sum_{t} \vec{x}_{t} \vec{x}_{t}^{\top} \\ \vec{b} & =\sum_{t} y_{t} \vec{x}_{t} \\ \vec{w}_{\mathrm{ML}}&=\mathbf{A}^{-1} \vec{b} \end{aligned}$$

Numerical optimization

Gradient ascent

$$\vec{\theta} \leftarrow \vec{\theta} + \eta_{t}\left(\frac{\partial f}{\partial \vec{\theta}}\right)$$

Newton’s method

$$\vec{\theta} \leftarrow \vec{\theta}-\mathbf{H}^{-1} \nabla f$$

Logistic regression

$$P(Y=1 \mid \vec{x})=\sigma(\vec{w} \cdot \vec{x})=\frac{1}{1+e^{-\vec{w} \cdot \vec{x}}}$$

$$\begin{aligned}\sigma(z) & =\frac{1}{1+e^{-z}} \\\sigma(-z) & =1-\sigma(z) \\\frac{d}{d z} \sigma(z) & =\sigma(z) \sigma(-z)\end{aligned}$$

$$\mathcal{L}(\vec{w})=\sum_{t=1}^{T}\left[y_{t} \log \sigma\left(\vec{w} \cdot \vec{x}_{t}\right)+\left(1-y_{t}\right) \log \sigma\left(-\vec{w} \cdot \vec{x}_{t}\right)\right]$$

$$\frac{\partial \mathcal{L}}{\partial w_{\alpha}}=\sum_{t=1}^{T} x_{\alpha t}\left[y_{t}-\sigma\left(\vec{w} \cdot \vec{x}_{t}\right)\right]$$

$$\frac{\partial^{2} \mathcal{L}}{\partial w_{\alpha} \partial w_{\beta}}=-\sum_{t=1}^{T} \sigma\left(\vec{w} \cdot \vec{x}_{t}\right) \sigma\left(-\vec{w} \cdot \vec{x}_{t}\right) x_{\alpha t} x_{\beta t}$$

Learning from incomplete data

Computing the log-likelihood with incomplete data

$$\mathcal{L}=\left.\sum_{t=1}^{T} \log \sum_{h} \prod_{i=1}^{n} P\left(X_{i}=x_{i} \mid \mathrm{pa}_{i}=\pi_{i}\right)\right|_{\left\{H_{t}=h, v_{t}=v_{t}\right\}}$$

Auxiliary functions

$$\vec{\theta}_{\text {new }}=\underset{\vec{\theta}}{\operatorname{~arg~max}}\ Q\left(\vec{\theta}, \vec{\theta}_{\text {old }}\right)$$

1. $Q(\vec{\theta}, \vec{\theta})=f(\vec{\theta})$ for all $\vec{\theta}$
2. $Q(\vec{\theta^{\prime}}, \vec{\theta}) \leq f(\vec{\theta^{\prime}})$ for all $\vec{\theta}, \vec{\theta^{\prime}}$

EM Algorithm

E-step

$$P\left(X_{i}=x \mid V_{t}=v_{t}\right)$$

$$P(X_i=x,pa_i=\pi \mid V_t=v_t)$$

M-step (Learning)

$$P(X_i=x) \longleftarrow \frac1T\sum_{t=1}^TP(X_i=x \mid V_t=v_t)$$

$$P(X_i=x \mid \text{pa}_i=\pi)\longleftarrow\frac{\sum_{t=1}P(X_i=x,\text{pa}_i=\pi \mid V_t=v_t)}{\sum_{t=1}^TP(\text{pa}_i=\pi \mid V_t=v_t)}$$

Hidden Markov models

Parameters of HMMs

$$a_{ij}=P(S_{t+1}=j \mid S_t=i)$$

$$b_{ik}=P(O_t=k \mid S_t=i)$$

$$\pi_i=P(S_1={i})$$

Forward algorithm

$${\alpha_{it}}={P(o_1,o_2,\ldots,o_t,S_t=i)}$$

$$\begin{array}{rcl}\alpha_{i1}&=&\pi_ib_i(o_1)\\\alpha_{j,t+1}&=&\sum_{i=1}^n\alpha_{it}a_{ij}b_j(o_{t+1})\end{array}$$

$$P(o_1,o_2,\ldots,o_T)=\sum_{i=1}^n\alpha_{iT}$$

Viterbi algorithm

$${\ell_{it}^*}=\max_{s_1,s_2,...,s_{t-1}}\log P(s_1,s_2,\ldots,s_{t-1},{S_t}=i,o_1,o_2,\ldots,o_t)$$

$$\begin{array}{rcl}\ell_{i1}^*&=&\log\pi_i+\log b_i(o_1)\\{\ell_{j,t+1}^*}&=&\max_i\left[\ell_{it}^*+\log a_{ij}\right]+\log b_j(o_{t+1})\end{array}$$

$$\Phi_{t+1}(j)=\mathrm{arg~max}_i\left[\ell_{it}^*+\log a_{ij}\right]$$

$$\begin{array}{rcl}s_T^*&=&\mathrm{arg}\max_i\left[\ell_{iT}^*\right]\\s_t^*&=&\mathrm{arg}\max_i\left[\ell_{it}^*+\log a_{is_{t+1}^*}\right]=\Phi_{t+1}(s_{t+1}^*)\end{array}$$

Backward algorithm

$$\beta_{i{t}}=P(o_{t+1},o_{t+2},\ldots,o_T \mid S_t=i)$$

$$\begin{array}{rcl}\beta_{i{T}}&=&1\\\beta_{i{t}}&=&\sum_{j=1}^na_{ij}b_j(o_{t+1})\beta_{j,t+1}\end{array}$$

EM algorithm for HMMs

E-step

$$P(S_t=i \mid o_1,\ldots,o_T)=\frac{\alpha_{it}\beta_{it}}{\sum_j\alpha_{jt}\beta_{jt}}$$

$$P(S_t=i,S_{t+1}=j \mid o_1,\ldots,o_T)=\frac{\alpha_{it}a_{ij}b_j(o_{t+1})\beta_{j,t+1}}{\sum_k\alpha_{kt}\beta_{kt}}$$

M-step

$$\pi_i\leftarrow P(S_1=i \mid o_1,o_2,\ldots,o_T)$$

$$a_{ij}\leftarrow{\frac{\sum_tP(S_{t+1}=j,S_t=i \mid o_1,o_2,\ldots,o_T)}{\sum_tP(S_t=i \mid o_1,o_2,\ldots,o_T)}}$$

$$b_{ik}\leftarrow\frac{\sum_tI(o_t,k)P(S_t=i \mid o_1,o_2,\ldots,o_T)}{\sum_tP(S_t=i \mid o_1,o_2,\ldots,o_T)}$$

Multivariate Gaussian distributions

$$P(\mathbf{x})~=~\frac1{\sqrt{(2\pi)^d\det({\Sigma})}}\exp\left\{-\frac12(\mathbf{x}-\mu)^\top{\Sigma}^{-1}(\mathbf{x}-\mu)\right\}$$

Maximum likelihood (ML) estimation

$$\mu_\mathrm{ML}=\frac1T\sum_{t=1}^Tx_t$$

$$\mathbf{\Sigma}_{\mathrm{ML}}=\frac1T\sum_{t=1}^T(\mathbf{x}_t-\mathbf{\mu}_{\mathrm{ML}})(\mathbf{x}_t-\mathbf{\mu}_{\mathrm{ML}})^\top$$

Clustering with GMMs

ML estimates for complete data

$$\boldsymbol{\mu}_i=\frac{\sum_{t=1}^T{I(z_t,i)}\boldsymbol{x}_t}{\sum_{t=1}^T{I(z_t,i)}}$$

$$\boldsymbol{\Sigma}_{i}=\frac{\sum_{t=1}^{T}{I(z_{t},i)(x_{t}-\mu_{i})(x_{t}-\mu_{i})^{\top}}}{\sum_{t=1}^{T}{I(z_{t},i)}}$$

EM updates for incomplete data

$$\begin{aligned}\mu_i\leftarrow\frac{\sum_{t=1}^TP(Z=i \mid \mathbf{x}_t)\mathbf{x}_t}{\sum_{t=1}^TP(Z=i \mid \mathbf{x}_t)}\end{aligned}$$

$$\boldsymbol{\Sigma}_i\leftarrow\frac{\sum_{t=1}^T{P(Z=i \mid x_t)(x_t-\mu_i)(x_t-\mu_i)^\top}}{\sum_{t=1}^T{P(Z=i \mid x_t)}}$$

— Dec 14, 2023

View / Make Comments

---