layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 𧬠Spatial Correlation Extraction (Anisotropic) ### via Gaussian Process Regression @luk036 π¨βπ» Β· 2026 π --- ### π Agenda .pull-left[ **Part 1: Motivation** π― - Why Anisotropic? π€ - Isotropic vs Anisotropic βοΈ - Real Chip Examples π **Part 2: Formulation** π - Anisotropic Kernel Functions 𧩠- Separable Kernels π - **Data Generation via Cholesky** π² - Optimization Landscape β°οΈ ] .pull-right[ **Part 3: Results** π - Correlation Surfaces π - Extraction Accuracy β - Sample Size Sensitivity π **Part 4: Practical Guide** π‘ - Isotropic Assumption Error β οΈ - Detecting Anisotropy π - Recommendations π― ] --- class: nord-light, middle, center ## Part 1: Motivation π― --- ### π€ Why Anisotropic? In real chip manufacturing, variations often have **different correlation lengths** in x and y directions: .mermaid[ <pre> graph TD subgraph "Isotropic π΅" direction TD I1["Same correlation\nin all directions"] I2["l1 = l2"] I3["CMP: circular\npolishing pattern"] end subgraph "Anisotropic πΆ" direction TD A1["Different correlation\nper direction"] A2["l1 β l2"] A3["Litho scan: stripe\npattern in y-direction"] end style I1 fill:#bbdefb style I2 fill:#64b5f6,color:#fff style I3 fill:#e3f2fd style A1 fill:#ffe0b2 style A2 fill:#ff9800,color:#fff style A3 fill:#fff3e0 </pre> ] **Common causes:** π - **Lithography scan direction** β longer correlation along scan axis π¦ - **CMP polishing** β direction-dependent material removal βοΈ - **Chemical-mechanical planarization** β wafer-scale trends π --- ### π Real Chip Examples .pull-left[ **Lithography induced** π¦: - Scan direction: ${\color{green} \ell_y > \ell_x}$ - Gate CD varies more slowly along scan - Impacts timing across the chip **CMP induced** βοΈ: - Polish direction: ${\color{green} \ell_x > \ell_y}$ - Metal thickness varies with pattern density - Creates directional variability ] .pull-right[ **Key question:** β > If we assume **isotropic** correlation when the true process is **anisotropic**, how wrong are we? **Spoiler:** π¨ - You'll systematically **underestimate** correlation in one direction - And **overestimate** in the other - Leading to incorrect timing margins! ] --- ### βοΈ Isotropic vs Anisotropic .mermaid[ <pre> graph TD subgraph "Isotropic Model β" WRONG["Assume l1 = l2\nOne length scale"] ERR1["Underestimates\nx-correlation"] ERR2["Overestimates\ny-correlation"] WRONG --> ERR1 WRONG --> ERR2 end subgraph "Anisotropic Model β " RIGHT["Estimate l1, l2\nseparately"] OK1["Correct\nx-correlation"] OK2["Correct\ny-correlation"] RIGHT --> OK1 RIGHT --> OK2 end style WRONG fill:#ffcdd2 style ERR1 fill:#ef9a9a style ERR2 fill:#ef9a9a style RIGHT fill:#c8e6c9 style OK1 fill:#a5d6a7 style OK2 fill:#a5d6a7 </pre> ] **Isotropic extraction with anisotropic data** β the optimizer finds a compromise ${\color{red} \ell}$ that doesn't represent either direction well. π« --- class: nord-light, middle, center ## Part 2: Formulation π --- ### 𧩠Anisotropic Kernel Formulation **Isotropic** (single distance $r$): $$ r = \frac{\sqrt{dx^2 + dy^2}}{\ell} $$ **Anisotropic** (per-dimension distances): $$ r_{12} = \sqrt{\frac{dx^2}{{\color{green} \ell_1}^2} + \frac{dy^2}{{\color{orange} \ell_2}^2}} $$ **Gaussian kernel:** $$ k(\mathbf{x}, \mathbf{x'}) = {\color{darkmagenta} \sigma^2} \exp\left(-\frac{1}{2}\left[\frac{(x-x')^2}{{\color{green} \ell_1}^2} + \frac{(y-y')^2}{{\color{orange} \ell_2}^2}\right]\right) $$ **Matern kernel** ($\nu = 3/2$): $$ k(r) = {\color{darkmagenta} \sigma^2}\left(1 + \sqrt{3}\, r\right) \exp\left(-\sqrt{3}\, r\right) $$ --- ### π Separable Kernel Structure An anisotropic kernel is **separable** β it factorizes into x and y components: $$ k(\mathbf{x}, \mathbf{x'}) = {\color{darkmagenta} \sigma^2} \cdot {\color{green} k_1(x, x'; \ell_1)} \cdot {\color{orange} k_2(y, y'; \ell_2)} $$ For the Gaussian case: $$ k(\mathbf{x}, \mathbf{x'}) = {\color{darkmagenta} \sigma^2} \cdot \exp\left(-\frac{(x-x')^2}{2{\color{green} \ell_1}^2}\right) \cdot \exp\left(-\frac{(y-y')^2}{2{\color{orange} \ell_2}^2}\right) $$ .mermaid[ <pre> graph LR K["k(x, x')"] --> K1["kβ(x, x')\nββ in x"] K --> K2["kβ(y, y')\nββ in y"] style K fill:#9c27b0,color:#fff style K1 fill:#2196f3,color:#fff style K2 fill:#ff9800,color:#fff </pre> ] This separability is what makes anisotropic GPs computationally efficient. β‘ --- class: nord-light, middle, center ## Data Generation: Computer Simulated Correlated Data π² --- ### π² Generating Correlated Random Fields To test the extraction algorithm, we need **ground-truth data** β data generated from a **known kernel** with known parameters. **Core idea:** Use **Cholesky decomposition** to transform independent noise into correlated samples: $$ {\color{orange} \mathbf{y}} \sim \mathcal{N}\big(0,\, {\color{blue} K_\theta} + {\color{coral} \sigma_n^2 I}\big) $$ .mermaid[ <pre> graph LR W["x ~ N(0, I)\nIndependent noise π²"] --> M["y = L @ x\nLinear transform"] C["K = LLα΅\nCholesky factor"] --> M M --> Y["y ~ N(0, K)\nCorrelated field β "] style W fill:#e3f2fd style C fill:#f3e5f5 style M fill:#ffcc80 style Y fill:#c8e6c9 </pre> ] This is the **exact reverse** of the extraction problem: we know the kernel β generate data β then verify extraction recovers the kernel. π --- ### π Cholesky Decomposition Method **Algorithm:** π 1. **Define** observation locations $s_1, \dots, s_n \in \mathbb{R}^2$ π 2. **Build** true covariance matrix $K_{ij} = {\color{darkmagenta} \sigma^2}\, k({\color{green} \ell_1}, {\color{orange} \ell_2}; \|s_i - s_j\|)$ 𧩠3. **Add** nugget: $V = K + {\color{coral} \sigma_n^2} I$ (ensures positive definiteness) β 4. **Factor**: $V = {\color{blue} L}{\color{blue} L}^\mathsf{T}$ via Cholesky decomposition π· 5. **Draw** ${\color{orange} M}$ independent samples: $$ \mathbf{x}_m \sim \mathcal{N}(0, I), \quad \mathbf{y}_m = {\color{blue} L} \mathbf{x}_m $$ 6. **Compute** sample covariance: $$ {\color{red} Y} = \frac{1}{M} \sum_{m=1}^M \mathbf{y}_m \mathbf{y}_m^\mathsf{T} $$ --- ### 𧩠Why Cholesky? .mermaid[ <pre> graph TD subgraph "Why Cholesky? π€" A["We want correlated\nsamples y ~ N(0, K)"] --> B["We can generate\nuncorrelated x ~ N(0, I)"] B --> C["Need transform:\ny = f(x)"] C --> D["Cholesky: K = LLα΅"] D --> E["Then: y = Lx\nworks perfectly! β "] end style A fill:#e3f2fd style B fill:#fff9c4 style C fill:#ffe0b2 style D fill:#f3e5f5 style E fill:#c8e6c9 </pre> ] **Why not other methods?** βοΈ .font-sm[ | Method | Pros | Cons | |:-------|:-----|:-----| | **Cholesky** β | Exact, simple | O(nΒ³) for large n | | Eigendecomposition π· | Also exact | More expensive | | Spectral method π | Fast for grids | Grid-only | | Circulant embedding π | Fast for stationary | Approximate | ] **For our test case** (n β 80 sites), Cholesky is fast and exact. β‘ --- ### π Python Implementation ```python import numpy as np from scipy.linalg import cholesky def simulate_anisotropic_2d(X, *, kernel_type="gaussian", length1=1.0, length2=4.0, sigma=2.0, noise=0.01, n_samples=200): """Generate n_samples realisations of an anisotropic GP.""" # 1. Build true covariance matrix V = make_true_kernel(kernel_type, length1, length2, sigma, noise)(X) # 2. Cholesky decomposition L = cholesky(V + 1e-10 * np.eye(len(X)), lower=True) # 3. Generate n_samples independent realisations # Each column is one "chip" of measurements rng = np.random.default_rng(42) return L @ rng.standard_normal((len(X), n_samples)) # Y has shape (n_sites, n_samples) Y = simulate_anisotropic_2d(X, kernel_type="gaussian", length1=1.0, length2=4.0, sigma=2.0, noise=0.01) ``` --- ### πΌοΈ Visualising Generated Data For an anisotropic field with $\ell_1 = 1.0$, $\ell_2 = 4.0$: ```text Single realisation (one "chip"): βββββββββββββββββββββββββββββββββββββββββββββββ β βββββββ ββββββ βββββ ββββ ββββββββ β β y-direction β βββββββ ββββββ βββββ ββββ ββββββββ β correlation β βββββββ ββββββ βββββ ββββ ββββββββ β is longer β βββββββ ββββββ βββββ ββββ ββββββββ β (ββ = 4.0) β βββββββ ββββββ βββββ ββββ ββββββββ β βββββββββββββββββββββββββββββββββββββββββββββββ β x-direction correlation is shorter (ββ = 1.0) β ``` **Test strategy:** π― 1. Generate ${\color{orange} M}$ chips from known ${\color{green} \ell_1}, {\color{orange} \ell_2}, {\color{darkmagenta} \sigma}, {\color{coral} \sigma_n}$ 2. Compute sample covariance ${\color{red} Y} = \frac{1}{M} \sum \mathbf{y}_m \mathbf{y}_m^\mathsf{T}$ 3. Run extraction MLE on ${\color{red} Y}$ 4. Compare estimated $\hat{\theta}$ vs true $\theta$ β **verify correctness** β --- ### βοΈ Optimization: 4 Parameters .pull-left[ **Isotropic** (3 params): $$ \theta = \{{\color{green} \ell}, {\color{darkmagenta} \sigma}, {\color{coral} \sigma_n}\} $$ $$ \min_\theta \; -\log p(\mathbf{Y} \mid X, \theta) $$ **Anisotropic** (4 params): $$ \theta = \{{\color{green} \ell_1}, {\color{orange} \ell_2}, {\color{darkmagenta} \sigma}, {\color{coral} \sigma_n}\} $$ $$ \min_\theta \; -\log p(\mathbf{Y} \mid X, \theta) $$ ] .pull-right[ **sklearn implementation:** ```python # Anisotropic: pass array of length scales RBF(length_scale=[1.0, 1.0]) # Isotropic: pass scalar RBF(length_scale=1.0) ``` **Multi-realisation MLE:** ```python def nlml_multi_aniso(params, X, Y, ...): log_l1, log_l2, log_sig, \ log_noi = params ... ``` ] --- ### π Anisotropic Extraction Pipeline .mermaid[ <pre> graph LR D["2D Data\nX: (nΓ2)"] --> S["Compute\nAnisotropic Distances"] S --> K["Build\nCovariance Matrix\nV = K(lβ,lβ) + ΟβΒ²I"] K --> L["Cholesky\nV = LLα΅"] L --> N["Negative Log Likelihood\n-log L / M"] N --> O["Optimizer\nL-BFGS-B\n4 params: lβ,lβ,Ο,Οβ"] O --> Q{"Converged?"} Q -->|No| K Q -->|Yes| R["Estimated ΞΈΜ\nlβ, lβ, Ο, Οβ"] style D fill:#2196f3,color:#fff style K fill:#9c27b0,color:#fff style L fill:#e91e63,color:#fff style O fill:#f44336,color:#fff style R fill:#4caf50,color:#fff </pre> ] **Key difference from isotropic:** The distance computation uses separate ${\color{green} \ell_1}$ and ${\color{orange} \ell_2}$, and the optimizer searches a 4D space instead of 3D. π― --- ### β°οΈ Optimization Landscape Challenge .mermaid[ <pre> graph TD subgraph "3D search (isotropic)" I["β only β line search"] end subgraph "4D search (anisotropic)" A["ββ, ββ β plane search\nMore local minima β οΈ"] end style I fill:#bbdefb style A fill:#ffe0b2 </pre> ] **Consequences:** β‘ - More random restarts needed (10 β 12+) - Wider bounds required (ββ, ββ can differ by 10Γ) - Risk of **parameter swapping** (ββ β ββ is symmetric) **Mitigation:** π‘οΈ - Multi-start with 12 random initializations - Use true-value-initialized start when available - Check that ββ and ββ are well-separated --- class: nord-light, middle, center ## Part 3: Results π --- ### π Anisotropic Correlation Surfaces  *Anisotropic correlation functions C(dx, dy) for different kernel types and length scale ratios. Elliptical contours reveal the directional dependence.* πΆ --- ### β Extraction Accuracy (n=200)  *Length scale estimation error for GPR (single chip) vs MLE (multi-realisation) across 6 anisotropic configurations at n=200.* π --- ### π Accuracy Table **MLE results at ${\color{red} n=200}$:** .font-sm[ | Kernel | True ($\ell_1$, $\ell_2$) | Est $\ell_1$ | Est $\ell_2$ | $\sigma$ err | |:-------|:------------------------:|:------------:|:------------:|:------------:| | Gaussian β¨ | 1.0, 4.0 | **1.010** β | **4.010** β | 0.020 β | | Gaussian β¨ | 3.0, 1.0 | **2.992** β | **1.004** β | 0.002 β | | Gaussian β¨ | 1.5, 6.0 | **1.503** β | **6.010** β | 0.013 β | | MatΓ©rn-3/2 β | 1.0, 4.0 | **1.009** β | **4.018** β | 0.011 β | | MatΓ©rn-5/2 π | 4.0, 1.0 | **3.978** β | **1.008** β | 0.003 β | | Exponential π | 2.0, 6.0 | **1.950** β | **5.845** β | 0.015 β | ] **Key finding:** Both $\ell_1$ and $\ell_2$ recovered within **< 1%** for Gaussian/MatΓ©rn, **~3-5%** for Exponential. β --- ### π Sample Size Sensitivity  *Total length error $(|\ell_1 - \hat{\ell}_1| + |\ell_2 - \hat{\ell}_2|)$ vs number of samples for three anisotropic configurations.* π --- ### π Key Sample Size Findings .pull-left[ **Rule of thumb for anisotropic extraction:** π | Samples | Reliability | Notes | |:-------:|:-----------|:------| | 200+ π’ | Excellent | Both ββ, ββ < 2% error | | 100 π‘ | Good | Slight degradation | | 50 π | Marginal | ββ error may double | | <20 π΄ | Poor | Cannot resolve anisotropy | ] .pull-right[ **Why anisotropic needs more samples:** π€ $$ \text{Isotropic:} \quad 3 \text{ parameters} $$ $$ \text{Anisotropic:} \quad 4 \text{ parameters} $$ More parameters β more data needed to constrain them. **Advice:** If you suspect anisotropy, use **at least 100β200 chips**. π― ] --- ### β οΈ What If You Assume Isotropic? Suppose data is **anisotropic** ($\ell_1 = 1.0, \ell_2 = 4.0$) but you fit an **isotropic** kernel: .mermaid[ <pre> graph LR A["True: lβ=1.0, lβ=4.0\nπΆ"] --> F["Fit: isotropic β"] F --> BAD["β compromise β 2.0\nunderestimates x, overestimates y"] BAD --> E1["x-dir: over-estimate\ncorrelation range β"] BAD --> E2["y-dir: under-estimate\ncorrelation range β"] style A fill:#ffe0b2 style F fill:#ffcdd2 style BAD fill:#ef9a9a style E1 fill:#ffab91 style E2 fill:#ffab91 </pre> ] **Result:** π - **Design becomes non-optimal** in both directions π« - Over-optimistic in one axis, over-conservative in the other βοΈ - **Worst case:** The isotropic model doesn't capture the true spatial structure, leading to yield loss π --- class: nord-light, middle, center ## Part 4: Practical Guide π‘ --- ### π Detecting Anisotropy How do you know if your data requires an anisotropic model? π€ .pull-left[ **Method 1: Visual inspection** ποΈ - Plot empirical semivariogram in x and y directions separately - If they differ significantly β anisotropic **Method 2: Model comparison** π ```text Fit isotropic: get β, log L_iso Fit anisotropic: get ββ, ββ, log L_aniso if log L_aniso - log L_iso > threshold: β anisotropic ``` ] .pull-right[ **Method 3: Ratio test** π $$ \text{Ratio} = \frac{\max(\ell_1, \ell_2)}{\min(\ell_1, \ell_2)} $$ - Ratio < 1.5 β isotropic is fine β - Ratio 1.5β3.0 β moderate anisotropy β οΈ - Ratio > 3.0 β strong anisotropy, must use anisotropic π΄ **Rule of thumb:** If $\ell_1 / \ell_2 > 2$, the isotropic model will introduce significant error. π― ] --- ### π Anisotropic Kernel Selection Guide | Scenario π― | β ratio | Recommended Kernel 𧩠| |:------------|:--------|:---------------------| | **Litho scan** π¦ | $\ell_y \gg \ell_x$ | MatΓ©rn-3/2 β | | **CMP direction** βοΈ | $\ell_x \gg \ell_y$ | MatΓ©rn-5/2 π | | **Random + systematic** π² | moderate (1.5β3) | Gaussian β¨ | | **Unknown** π€· | any | Fit both iso + aniso, compare | **Always:** Fit both isotropic and anisotropic models and compare their log likelihoods. The data will tell you which is appropriate. π¬ --- ### π‘ Key Takeaways 1. **Anisotropic correlation exists in real chips** π β lithography scan direction and CMP create directional dependencies 2. **GP regression handles it naturally** β β sklearn's `RBF([l1, l2])` and our custom MLE both support per-dimension length scales 3. **4 parameters instead of 3** β ββ, ββ, Ο, Οβ β requires more data (β₯100 chips recommended) π 4. **Isotropic assumption is dangerous** β οΈ β if your data is anisotropic and you fit isotropic, you get wrong correlation in both directions 5. **Detect before you decide** π β always fit both isotropic and anisotropic models, compare likelihoods 6. **Code available** π β `github.com/luk036/corr-solver` --- ### π References .pull-left[ **Related lectures:** π - [Spatial Correlation (lec03a)](lec03a-remark.html) 𧬠- [Non-parametric (lec03b)](lec03b-remark.html) π - [Anisotropic (this talk)](spatial-aniso-remark.html) πΆ **Papers:** π - Q. Fu, W.-S. Luk, et al., ISQED 2008 π¬ - Q. Fu, W.-S. Luk, et al., IEICE Trans. Fundamentals, 2009 π ] .pull-right[ **Textbooks:** π - Rasmussen & Williams, *GP for ML* π§ - Stein, *Interpolation of Spatial Data* π - Cressie, *Statistics for Spatial Data* π **Software:** π» - [corr-solver](https://github.com/luk036/corr-solver) π - `scikit-learn` β `RBF`, `Matern` kernels - `scipy.optimize.minimize` β L-BFGS-B .mermaid[ <pre> graph LR ISO["Isotropic\nlec03a"] --> ANISO["Anisotropic\nthis talk"] ISO --> NONPARA["Non-parametric\nlec03b"] style ISO fill:#64b5f6,color:#fff style ANISO fill:#ff9800,color:#fff style NONPARA fill:#4caf50,color:#fff </pre> ] ] --- count: false class: nord-dark, middle, center # π Q&A ### Questions? Discussion? π¬ --- count: false class: nord-dark, middle, center # π Thank You ### Code: github.com/luk036/corr-solver π ```text experiments/gp_corr_extraction.py β demo_aniso() for anisotropic extraction ``` Slides built with Remark.js π | KaTeX π | Mermaid 𧩠| Nord Theme π