Backtracking search algorithm for CSPs

• Backtrack($x$, $w$, Domains):

  • If $x$ is complete assignment: update best and return
  • Choose unassigned variable $X_i$ (MCV)
  • Order values in Domain${}_i$ of chosen variable $X_i$ (LCV)
    
  • For each value $v$ in that order:
    • $\delta \leftarrow {\prod }_{f_j\in D(x,X_i)}{f}_j(x\cup \{X_i:v\left\}\right)$
    • If $\delta =0$: continue (new partial assignment is inconsistent)
    • Domains${}^{\prime }\leftarrow$ Domains via lookahead
      
    • If any Domains${}_i^{\prime }$ is empty: continue
    • Backtrack($x\cup \{X_i:v\}$, $w\delta$, Domains${}^{\prime }$)

• In the above algorithm, the blue contents are the ones that can be optimized

• One-step lookahead: forward checking. After assigning a variable $X_i$, eliminate inconsistent values from the dominas of $X_i$’s neighbors

Dynamic ordering

• Choose an unassigned variable: choose the most constrained variable (MCV), i.e., the variable that has the smallest domain).
  • If going to fail, fail early (more pruning)
  • Because we need to find an assignment for every variable
  • This is useful when some factor are constraints (can prune assginemnts with weight 0)
• Order values of a selected variable: least constrained value (LCV), descending order of the sum of consistent values of neighboring variables
  • Choose value that is most likely to lead to solution
  • Because for each variable only need to choose some values
  • Useful when all factors are constraints (Only need to find an assignment with weight 1)

Arc consistency

• A variable $X_i$ is arc consistent wrt $X_j$ if for each $x_i\in {\text{Domain}}_i$, there exists $x_j\in {\text{Domain}}_j$ such that $$f\left(\right\{X_i:x_i,X_j:x_j\left\}\right)\ne 0$$ for all factors $f$ whose scope contains $X_i$ and $X_j$.

• AC-3 algorithm: repeatedly enforce arc consistency on all variables

Beam search

• Greedy search: we assume we have a fixed ordering of the variables. Then in every step of assigning a value to a variable, greedy search is to use the assignment with the highest weight

Figure source: Stanford CS221 spring 2025, lecture slides week 6

• Beam search: keep track of (at most) $K$ best partial assignments at each level of the search tree
  • Note: these candidates are not guaranteed to be the $K$ best at each level
  • Time complexity of beam search is $O\left(nKb\right)$
    • Depth: number of variables $n$
    • Branching factor $b=|{\text{Domain}}_i|$
    • Beam size $K$
  • Beam size $K$ controls trade-off between efficiency and accuracy
    • $K=1$: greedy search, $O\left(nb\right)$ time
    • $K=\infty$: BFS, $O\left(b^n\right)$ time

Figure source: Stanford CS221 spring 2025, lecture slides week 6

Local search

• The goal is to improve an old complete assignment.

• Locality: When evaluating possible re-assignments to $X_i$, only need to consider the factors that depend on $X_i$.

• Iterated conditional modes (ICM) algorithm

  • Initialize $x$ to a random complete assignment
  • Loop through $i=1,\dots ,n$ until convergence:
    • Compute weight of $x_v=x\cup \{X_i:v\}$ for each $v$
    • $x\leftarrow x_v$ with highest weights

• ICM can stuck at local optima

• ICM has linear time complexity

Forward Backward: estimate $H$

• Lattice representation

Figure source: Stanford CS221 spring 2025, lecture slides week 7

• Edge start $\to H_1=h_1$ has weight $p\left(h_1\right)p(e_1\mid h_1)$

• Edge $H_{i-1}=h_{i=1}\to H_i=h_i$ has weight $p(h_i\mid h_{i-1})p(e_i\mid h_i)$

• Each path from start to end is an assignment with weight equal to the product of edge weights

• Forward: sum of weights of paths from start to $H_i=h_i$ $$\begin{array}{cc}{F}_i\left(h_i\right)& =\sum _{h_{i-1}}{F}_{i-1}\left(h_{i-1}\right)\cdot \text{Weight}(H_{i-1}=h_{i-1},H_i=h_i)\\ & =\sum _{h_{i-1}}{F}_{i-1}\left(h_{i-1}\right)\cdot p(h_i\mid h_{i-1})p(e_i\mid h_i)\end{array}$$

• Backward: sum of weights of paths from $H_i=h_i$ to end $$\begin{array}{cc}{B}_i\left(h_i\right)& =\sum _{h_{i+1}}{B}_{i+1}\left(h_{i+1}\right)\cdot \text{Weight}(H_i=h_i,H_{i+1}=h_{i+1})\\ & =\sum _{h_{i+1}}{B}_{i+1}\left(h_{i+1}\right)\cdot p(h_{i+1}\mid h_i)p(e_{i+1}\mid h_{i+1})\end{array}$$

• Define: sum of weights of paths from start to end through $H_i=h_i$ $$S_i\left(h_i\right)=F_i\left(h_i\right)B_i\left(h_i\right)$$

• Base cases: $$F_1=p\left(h_1\right)p(e_1\mid h_1)$$ $$B_n=1$$

• Forward-backward algorithm for HMMs:

  • Compute $F_1,F_2,\dots ,F_n$
  • Compute $B_n,B_{n-1},\dots ,B_1$
  • Compute $S_i$ for each $i$ and normalize $$P(H_i=h_i\mid E=e)=\frac{S_i\left(h_i\right)}{{\sum }_v{S}_i\left(v\right)}$$

• Time complexity of forward-backward: $O\left(n|\text{Domain}{|}^2\right)$

Particle Filtering: estimate $H$

• Particle filtering is kind of like beam search for HMMs: keep $\le K$ partial assignments (particles)

• Particle filtering for HMMs: 3 steps

  1. Propose: For each old particle $(h_1,\dots ,h_{i-1})$, sample $H_i\sim p(h_i\mid h_{i-1})$
  2. Weight: For each old particle $(h_1,\dots ,h_{i-1},h_i)$, weight it by $p(e_i\mid h_i)$
  3. Resample: Normalize weights and draw $K$ samples to redistribute particles to more promising areas. The resulting distribution is approximately $P(H_1,\dots ,H_i\mid E_1,\dots ,E_i)$

Smoothing

• Laplace smoothing: for each distribution $d$ and partial assignment $(x_{\text{Parents}\left(i\right)},x_i)$, add $\lambda$ to count${}_d(x_{\text{Parents}\left(i\right)},x_i)$
  • This is like adding a Dirichlet prior

Expectation Maximization (EM) Algorithm

• Initialize $\theta$ randomly
• Repeat until converge
  • E step: fix $\theta$, update $H$
    • For each $h$ compute $$q\left(h\right)=P(H=h\mid E=e,\theta )$$
    • Create fully-observed weighted examples: $(h,e)$ with weight $q\left(h\right)$
  • M step: fix $H$, update $\theta$
    • Maximum likelihood (count and normalize) on weighted examples to get $\theta$
• Properties of the EM algorithm
  • EM algorithm deals with hidden variables $H$
  • Intuition: generalization of the K-means algorithm:
    • Cluster centroids = parameter $\theta$
    • Cluster assignments = hidden variables $H$
  • EM algorithm converges to local optima

A more general version of the EM algorithm

1. Choose the initial parameters ${\theta }^{\text{old}}$

2. E step: since the conditional posterior $p(Z\mid X,{\theta }^{\text{old}})$ contains all of our knowledge about the latent variable $Z$, we compute the expected complete-data log likelihood under it. $$\begin{array}{cc}Q(\theta ,{\theta }^{\text{old}})& =E_{Z\mid X,{\theta }^{\text{old}}}\left\{\log p\right(X,Z\mid \theta \left)\right\}\\ & =\sum _{Z}p(Z\mid X,{\theta }^{\text{old}})\log p(X,Z\mid \theta )\end{array}$$

3. M step: revise parameter estimate $${\theta }^{\text{new}}=\arg \underset{\theta }{max}Q(\theta ,{\theta }^{\text{old}})$$

   • Note in the maximizing step, the logarithm acts driectly on the joint likelihood $p(X,Z\mid \theta )$, so the maximizating will be tractable.

4. Check for convergence of the log likelihood or the parameter values. If not converged, use ${\theta }^{\text{new}}$ to replace ${\theta }^{\text{old}}$, and return to step 2.

See my EM algorithm notes for more details