PaperlayerView exact revision on arXiv

Source-linked AI summary

Informed proposals for local MCMC in discrete spaces

Giacomo Zanella

arXiv:1711.07424v1stat.COmath.PR

TL;DR

고차원 이산 공간을 위한 informed Metropolis-Hastings proposal 설계 방법은 여전히 명확하지 않다. 이 논문은 locally-balanced proposal을 개발하고, 고차원에서의 Peskun-optimality를 증명하며, 대안적 방법보다 몇 자릿수 높은 효율 향상을 보고한다.

  • 문제

    proposal 선택이 sampling efficiency에 큰 영향을 미치는데도, informed MCMC proposal을 이산 공간으로 적절히 확장하는 방법은 여전히 명확하지 않다.

  • 방법

    이 논문은 pointwise informed proposal을 정식화하고, locally-balanced proposal을 규명하며, regularity assumption하에서 그 optimality를 분석한다.

  • 결과

    locally-balanced proposal은 점근적으로 Peskun-optimal이며, simulated 및 real-data 실험에서 대안적 방법보다 몇 자릿수 높은 효율 향상을 제공한다.

  • 시사점 및 한계

    이 framework는 고차원 이산 문제에서 informed MCMC proposal을 설계하기 위한 실용적이고 쉽게 구현 가능한 방법론적 지침을 제공한다.

  • 시사점 및 한계

    이론적 분석은 symmetric base kernel을 가정하므로, general base kernel로의 확장은 향후 연구 과제로 남는다.

Abstract

from arXiv · show

There is a lack of methodological results to design efficient Markov chain Monte Carlo (MCMC) algorithms for statistical models with discrete-valued high-dimensional parameters. Motivated by this consideration, we propose a simple framework for the design of informed MCMC proposals (i.e. Metropolis-Hastings proposal distributions that appropriately incorporate local information about the target) which is naturally applicable to both discrete and continuous spaces. We explicitly characterize the class of optimal proposal distributions under this framework, which we refer to as locally-balanced proposals, and prove their Peskun-optimality in high-dimensional regimes. The resulting algorithms are straightforward to implement in discrete spaces and provide orders of magnitude improvements in efficiency compared to alternative MCMC schemes, including discrete versions of Hamiltonian Monte Carlo. Simulations are performed with both simulated and real datasets, including a detailed application to Bayesian record linkage. A direct connection with gradient-based MCMC suggests that locally-balanced proposals may be seen as a natural way to extend the latter to discrete spaces.

1 서론

MCMC 효율은 proposal 설계에 크게 좌우된다. 정보가 없는 random-walk 방식은 mixing이 나쁠 수 있는 반면, 기존 informed 방법은 주로 연속 공간에 맞춰져 있다. 본 연구는 고차원 이산 및 연속 문제를 위한 통합적이고 이론적 근거를 갖춘 접근법으로 locally-balanced proposal을 개발하며, 경험적으로 상당한 효율 향상을 보인다.

  • Metropolis-Hastings의 효율은 proposal distribution과 target의 상호작용에 크게 좌우되며, 수렴 속도에 영향을 미친다.
  • Random-walk proposal은 구현하기 쉽지만 target 정보 없이 맹목적으로 제안하므로 mixing이 나빠지고 수렴이 느려질 수 있다.
  • Gradient-based proposal과 HMC를 포함한 연속 공간의 informed 방법은 MCMC 성능을 향상시키지만, 이산 공간에는 자연스러운 위상을 보존하는 실현 가능한 embedding이 부족한 경우가 많다 [Neal, 2011, Girolami and Calderhead, 2011].
  • 본 논문은 연속 및 이산 설정을 통합하는 간단한 framework를 통해 informed proposal을 정식화하고, 고차원 이산 문제를 위한 locally-balanced proposal을 도입한다.
  • 본 논문은 local-limit exactness를 통해 locally balanced proposal을 특성화하고, 고차원 Peskun optimality를 확립하며, 이를 Barker’s algorithm 과 연결하고 경험적으로 평가한다.

2 국소 균형 제안

이 절에서는 target density의 함수로 국소 대칭 kernel을 재가중하는 pointwise informed proposal을 전개하고, reversible measure가 작은 스케일에서 target으로 수렴하는 성질을 통해 locally balanced kernel을 정의한다. 이 framework는 square-root reweighting이 국소 편향을 보정하는 이유를 설명하고, 더 효율적인 Metropolis-Hastings algorithm으로 이어지는 balancing function의 동기를 제시한다.

  • 동기: 제안을 π(y)로 순진하게 가중하면 작은 σ에서 적절하지 않다. reversible measure가 target인 π(x)dx가 아니라 π(x)^2dx로 수렴하기 때문이다.큰 σ에서는 동일한 제안이 근사적으로 target-reversible이므로, globally balanced proposal과 locally balanced proposal을 구분할 필요가 있다.
  • 동기: square-root weighting인 g(t)=√t는 reversible measure가 σ↓0에서 π(x)dx로 수렴하는 제안을 만들어 locally balanced proposal의 한 예를 제공한다.이 구성은 직접적인 density weighting으로 발생하는 local-limit distortion을 보정한다.
  • Pointwise informed proposal: Pointwise informed proposal은 대칭 kernel Kσ(x,dy)에 g(π(y))를 곱해 재가중하고 정규화하면서도 kernel의 위상 구조를 유지한다.이 class에는 g(t)=1인 uninformed proposal과 g(t)=t일 때 Kσ(x,y)π(y)에 비례하는 naively informed proposal이 포함되며, g는 연속이고 linear function으로 bounded하다고 가정한다.
  • Locally balanced kernel: Locally balanced kernel은 σ↓0에서 target으로 weakly converge하는 distribution에 대해 reversible하며, 이에 따라 국소 이동에 필요한 Metropolis-Hastings correction이 줄어든다.그 결과 acceptance가 높아지고 이동 거리가 길어져, 고차원에서 local-move regime가 나타날 때 효율이 향상된다.
  • Balancing function: Theorem 1은 어떤 함수 g가 pointwise informed proposal을 locally balanced하게 만드는지 정확히 규명하고, 후속 결과에서는 이들의 asymptotic efficiency를 다른 pointwise informed proposal과 비교한다.이러한 함수를 balancing function이라 부른다.

3 국소 균형 제안의 Peskun 최적성

이 절에서는 이산 공간에서 점별 정보를 반영하는 Metropolis–Hastings 방법들을 비교하기 위해 Peskun ordering을 사용한다. 제안 함수의 balancing이 효율 향상을 가져오며, 국소 고차원 조건에서 점근적으로 최적이 됨을 보인다.

  • Peskun ordering: Peskun ordering은 비대각 kernel 우월성을 spectral gaps 및 점근 분산을 통한 MCMC 효율 향상과 연결한다 [Peskun, 1973, Tierney, 1998].x ≠ y일 때 P1(x, y) ≥ cP2(x, y)이면 Gap(P1) ≥ cGap(P2)이고, 이에 상응하는 점근 분산 향상이 따른다.
  • 최적 balancing: 임의의 양의 제안 함수 g에 대해 balancing transform ˜g(t) = min{g(t), t g(1/t)}는 1/c_gc_˜g배 더 효율적인 MH 알고리즘을 산출한다.이 변환은 ˜g(t) = t˜g(1/t)를 만족하며, 효율 계수는 많은 차원 증가 모델에서 1로 수렴한다.
  • 고차원 최적성: 잘 behaved한 g에 대해 condition (A)가 성립하면 비교 계수가 1로 수렴하여, locally-balanced proposals가 점근적으로 Peskun-optimal이 된다.충분조건의 한 설정은 bounded-degree conditional-independence graph와 고정된 수의 변수를 갱신하는 base kernel이다.
  • 이산 예시: 이 framework는 local moves를 사용하는 이산 모델을 포괄하며, independent binary components, transposition을 사용하는 weighted permutations, single-bit flips를 사용하는 Ising models를 포함한다.첫 번째 모델은 명시적으로 분석하고, permutation 및 Ising target은 이후 예시를 위한 비자명한 응용 사례를 제공한다.
  • 충분조건: 이 세 예시에서는 확률, permutation weight 또는 Ising bias의 boundedness 조건이 모든 locally bounded g에 대해 condition (A)를 보장하기에 충분하다.구체적으로 binary probability는 균일하게 (0,1) 내부에 머물고, permutation weight는 위와 아래에서 bounded이며, Ising bias는 균일하게 bounded이다.

4 balancing function의 최적 선택

이 절에서는 independent binary components에 대한 locally-balanced proposals 중 Barker balancing function, g(t) = t/(1 + t)가 최적임을 보인다. 이 결과는 각 bit가 독립적으로 flip되는 time-rescaled limiting process를 분석하고 그 flip rate를 최적화하여 얻어진다.

  • acceptance probabilities와의 연결: g(t)가 1로 bounded일 때 balancing functions는 Metropolis-Hastings acceptance probabilities에 대응하지만, 더 넓은 balancing-function class에는 g(t) = t와 같은 유효한 unbounded choice도 포함된다.acceptance-probability condition은 g(t) = t g(1/t)이며, balancing functions 자체가 probabilities일 필요는 없다.
  • Independent binary components: independent binary components의 경우 Barker balancing function g(t) = t/(1 + t)는 locally-balanced proposals 중 가장 작은 mixing time을 제공한다.비교는 두 단계의 asymptotic analysis를 사용한다. 먼저 limiting continuous-time process로 수렴시킨 뒤 mixing behavior를 최적화한다.
  • Limiting process: time rescaling 후, 고정된 개수의 components는 각 bit가 독립적으로 flip되는 continuous-time Markov chain으로 weakly converge한다.이 정리는 chain이 stationarity에서 시작한다고 가정하며, 추적하는 components의 개수가 모든 positive integer일 때 수렴을 보인다.
  • Optimization argument: limiting flip rates를 먼저 최적화하면 모든 component에 대해 c_i = 1/2를 얻으며, 이는 balancing condition g(t) = t g(1/t)와 정확히 일치한다.이는 locally-balanced proposals가 high dimensions에서 asymptotically optimal이라는 앞선 결론과 일치한다.
  • Optimal balancing function: optimal balancing function은 g_opt(t) = t/(1 + t)이며, neighboring states에 대한 proposal weights는 π^(n)(y)/(π^(n)(x) + π^(n)(y))에 비례한다.이는 acceptance probabilities에 대해 앞서 고려된 Barker choice다.

5 MALA 및 gradient-based MCMC와의 연결

연속 공간에서는 locally-balanced proposal이 계산하기 어려운 점별 target 평가를 국소 근사로 대체한다. 첫 번째 Taylor 근사는 MALA를 특정 locally-balanced proposal로 복원하며 유연한 gradient-based 확장을 시사한다.

  • 연속 공간에서의 동기: Pointwise informed proposal은 연속 공간에서 효율적인 샘플링에 대체로 실행 불가능하므로, 현재 상태 주변의 target에 대한 국소 근사가 필요하다.계산이 어려운 target 항 π(y)을 x 주변의 국소 근사로 대체한다.
  • 첫 번째 proposal: log π(y)의 첫 번째 Taylor expansion은 국소 gradient ∇log π(x)를 사용하는 first-order informed proposal family를 산출한다.근사는 elog π(y) ≈ elog π(x)+∇log π(x)·(y−x)이다.
  • MALA와의 연결: MALA는 g(t)=t 및 Gaussian kernel K_σ(x,·)=N(x,σ^2) 을 사용해 얻는 특정 locally-balanced proposal이다.이 구성은 first-order Taylor approximation과 (4)를 만족하는 symmetric K_σ를 사용한다.
  • 확장: 이 framework는 대안적인 balancing function, kernel 또는 π(y)에 대한 근사를 통해 확장할 수 있으며, gradient-based scheme에 대한 유연성을 보여준다.이러한 수정은 고전적인 gradient-based method를 확장하는 가능한 방법으로 제시된다.

6 시뮬레이션 연구

시뮬레이션 연구는 permutation 및 Ising target에서 informed 및 random-walk MCMC scheme을 비교하며, 특히 highly non-uniform distribution에서 locally balanced proposal이 상당한 효율 향상을 제공할 수 있음을 보인다. 또한 acceptance rate, computational cost, target concentration, initialization, single-site update의 적용 범위를 검토한다.

  • 시뮬레이션 설계와 범위: 시뮬레이션은 공통 base kernel을 사용하는 여섯 가지 scheme을 비교하며, chain의 거동은 initialization에 좌우될 수 있고 특수한 global-update algorithm은 비교 대상에서 제외된다.target에서 멀리 떨어진 상태로 initialization된 chain은 정체되어 거의 모든 move를 reject할 수 있다. multimodal Ising target에서는 global method가 더 나은 성능을 보일 수 있지만, 이는 연구 대상인 single-site scheme과 상호보완적이다.
  • permutation target: permutation target에서는 차원이 증가함에 따라 LB1과 LB2의 acceptance rate가 1에 가까워지지만, efficiency 비교에서는 더 높은 iteration당 computational cost를 고려한다.단위 computation time당 successful flip 수가 이 연구의 주요 cost-adjusted diagnostic이다.
  • permutation target: 대각선에서 멀어질수록 weight가 감소하는 structured permutation target에서는 결과가 i.i.d. case와 유사하며, HB는 LB1과 LB2보다 효율이 크게 낮다.structured-weight 실험에서는 HB와 locally balanced scheme 사이의 efficiency gap이 더욱 두드러진다.
  • Ising model: locally balanced scheme인 LB1과 LB2는 highly non-uniform Ising target에서 대안 scheme보다 orders of magnitude 더 효율적이다.이 이점은 단위 time당 effective sample size로 측정되며, target concentration이 증가할수록 특히 두드러진다.

7 Bayesian record linkage에의 적용

이 응용에서는 locally-balanced proposals를 사용해 bipartite record-linkage 문제의 고차원 discrete matching을 갱신한다. 이탈리아 survey data에서 LB는 sampling efficiency를 크게 향상시키며 posterior pairwise matching probabilities를 거의 십억 개까지 처리할 수 있도록 확장된다.

  • 모형과 sampler: locally-balanced proposals는 bipartite record linkage에서 고차원 이산 매칭 객체 M을 효율적으로 갱신하는 문제를 해결한다.이 과제는 데이터베이스 간에는 중복이 있지만 각 데이터베이스 내부에는 중복이 없는 두 데이터베이스를 통합하는 것으로, 일반적으로 연구되는 bipartite 경우다 (Sadinle [2017]).
  • 지역별 record linkage: 이 연구는 평균 약 1,300명의 개인으로 구성된 20개 이탈리아 지역 linkage 과제에 네 가지 MCMC scheme—RW, GB, LB, HB—를 적용한다.데이터는 2008년 및 2010년 Italian Survey on Household and Wealth에서 수집되었으며, 개인별로 11개 변수를 포함한다.
  • 지역별 record linkage: LB는 20개 지역 linkage 과제 전반에서 RW와 GB보다 대략 two orders of magnitude, HB보다 one order 높은 relative efficiency를 보인다.효율성은 computation time당 effective sample size로 측정하며, 다섯 가지 Hamming-distance statistics에 대해 평균을 내고 RW 대비 상대값으로 보고한다.
  • 지역별 record linkage: LB는 HB보다 어떤 record pair가 matched되었는지를 나타내는 posterior probabilities를 더 신뢰성 있게 제공한다.지역별 실험에서는 각 지역에 대해 LB를 35,000 iterations 실행했으며, 지역당 평균 약 120 seconds가 소요되었다.
  • 전체 데이터셋 linkage: 지역별 blocking 없이 전체 이탈리아 데이터셋에 적용했을 때, LB는 40분 이내에 posterior pairwise matching probabilities를 거의 십억 개 추정한다.전체 데이터 구현에서는 Section 6.4의 block-wise method를 사용하며, 지역 간 가능한 matching을 제외하지 않는다.

8 논의 및 향후 연구 · A 추가 계산 및 증명

이 논문은 고차원 최적성 보장을 갖추면서 구현이 쉬운 locally-balanced proposal framework를 제시한 뒤, gradient-based method, multiple-try Metropolis, 구현 및 이론과 관련된 확장 방향을 제시한다.

  • 8 논의 및 향후 연구: 이 framework는 pointwise informed proposal과 locally-balanced criterion을 통해 discrete space에서 informed Metropolis-Hastings proposal 설계를 다루며, regularity assumption하에서 고차원 최적성을 증명한다.저자들은 이 framework가 단순하고 독창적이며 구현에 유용하다고 규정한다.
  • 8 논의 및 향후 연구: MALA와의 연결은 gradient-based MCMC의 강건성을 높이고 gradient-based scheme의 tuning 부담을 줄일 수 있다.
  • 8 논의 및 향후 연구: Multiple-Try Metropolis로 분석을 확장할 것을 제안한다. 그 selection weight가 pointwise informed proposal의 multiplicative biasing term과 유사하기 때문이다.저자들은 결과가 해당 맥락으로 자연스럽게 확장될 것으로 예상한다.
  • 8 논의 및 향후 연구: 향후 구현 연구에서는 block-wise implementation과 informed term의 더 저렴한 근사를 포함해 iteration당 computational cost와 statistical efficiency 사이의 tradeoff를 연구해야 한다.informed term을 근사하더라도 Metropolis-Hastings accept/reject 단계에서는 exact target을 계속 사용한다.
  • 8 논의 및 향후 연구: locally-balanced proposal의 sampling은 자명하게 병렬화할 수 있으므로 GPU가 informed proposal의 computational overhead를 줄일 수 있다 [Lee et al., 2010].
  • 8 논의 및 향후 연구: 이론적 확장으로 locally balanced proposal과 globally balanced proposal 사이를 보간하고, 필요한 interpolation level을 적응적으로 학습하며, 충분 최적성 조건을 일반화하는 방향이 있다.이 방향들은 local behavior와 global behavior 사이의 중간 regime 및 더 넓은 이론적 설정을 대상으로 한다.

A.1 정리 1의 증명

증명은 g에 대한 선형 성장 조건하에서 정규화 적분을 제어한 뒤 kernel concentration과 Scheffé 정리를 통해 충분성을 증명하여 Theorem 1을 확립한다. 필요성은 condition (4)가 성립하지 않을 때 two-state 반례를 통해 따른다.

  • A.1 정리 1의 증명: g(t) ≤ a + bt라는 선형 bound와 bounded π, 그리고 concentrating symmetric kernels를 함께 사용하면 σ ↓ 0일 때 Zg,σ와 관련 적분을 제어할 수 있다.Lemma 1에서는 pointwise convergence, Fatou’s lemma, bounded convergence, kernel reversibility를 사용해 필요한 적분 bound를 확립한다.
  • A.1 정리 1의 증명: 조건 (4)하에서 normalized proposal density는 pointwise하게 π로 수렴하며, Scheffé’s theorem이 proposal이 locally balanced임을 보이는 충분성 증명을 완성한다.Kernel concentration은 g-dependent term에 필요한 극한을 제공하고, Lemma 1은 normalization control을 제공한다.
  • A.1 정리 1의 증명: 조건 (4)가 어떤 t0 > 0에서 성립하지 않으면, (1, t0)에 비례하는 확률을 갖는 two-state target이 general bounded continuous densities에 대한 local balance의 counterexample을 제공한다.구성에서는 X = {0, 1} 위의 counting measure를 사용하고, Kσ가 identity에 concentrate할 때 limiting proposal behavior를 살핀다.

A.2 정리 2의 증명 · A.3 정리 3의 증명 · A.4 명제 1의 증명

이 부록에서는 lazy reversible kernel의 variance 및 spectral gap 비교를 증명하고, symmetrized informed proposal의 일반적인 upper 및 lower bound를 확립하며, permutation 예제에서 proposal ratio의 제어를 검증한다.

  • A.2 정리 2의 증명: A.2에서는 reversible kernel을 factor c로 lazy화하면 varπ(h, P̃) = c^-1 varπ(h, P) + (1−c)c^-1 varπ(h)가 됨을 증명한다.증명에서는 공통 eigenfunction과 변환된 eigenvalue λ̃_i = cλ_i + (1−c)를 사용한다.
  • A.2 정리 2의 증명: A.2에서는 lazy화 항등식과 Peskun ordering [1973, Thm.2.1.1]을 결합하여 c > 1과 c ≤ 1인 두 경우 모두에서 정리 2의 variance comparison을 증명한다.이에 대응하는 spectral-gap 명제는 Gap(P)의 정의에서 바로 따른다.
  • A.3 정리 3의 증명: A.3에서는 bounded target density, symmetric Markov kernel, Radon–Nikodym proposal ratio를 사용하여 Theorem 3부터 Theorem 5까지를 continuous space로 확장한다.이 결과는 대응하는 Metropolis–Hastings kernel에 대해 upper 및 lower bound를 모두 제공한다.
  • A.3 정리 3의 증명: A.3에서는 더 balanced한 proposal을 강제하기 위해 g를 g̃(t) = min{g(t), t g(1/t)}로 대체하고 Pg와 Pg̃를 비교한다.증명에서는 proposal의 Radon–Nikodym derivative, normalization inequality, imbalance constant bg의 정의로부터 bound를 도출한다.
  • A.3 정리 3의 증명: A.3에서는 min{g̃(txy), txy g̃(tyx)}를 사용해 symmetrized proposal의 기여를 bound한 뒤, (28)의 upper 및 lower bound를 얻는다.제시된 중간 관계식 (31)–(34)가 최종 비교를 뒷받침한다.
  • A.4 명제 1의 증명: A.4에서는 compact interval I에서 g의 infimum 및 supremum과 gρ를 비교하여 permutation transposition에 대한 Proposition 1을 증명한다.g와 1/g의 local boundedness는 이러한 extrema가 유한하고 양수임을 보장한다.
  • A.4 명제 1의 증명: A.4에서는 변경되지 않은 permutation coordinate가 대응하는 proposal ratio를 보존한다고 관찰하고, Examples 1 및 3의 증명도 유사하다고 서술한다.논증에서는 i0 < j0인 ρ′ = ρ ◦ (i0, j0)를 고정하고 transposed coordinate만 비교한다.

A.5 Theorem 4의 증명 · A.5.1 product chain의 mixing time 관련 참고문헌 · B 시뮬레이션 연구 보충 자료

부록에서는 유한 성분 dynamics가 독립 성분 continuous-time Markov chain으로 수렴함을 보임으로써 Theorem 4를 증명한 뒤, mixing time을 최악 성분의 flipping rates와 연결한다. 또한 관련 mixing-time quantity를 최적화하는 상수 scaling 선택을 언급하고 추가적인 simulation diagnostics를 제시한다.

  • A.5 Theorem 4의 증명: Lemma 3은 Theorem 4의 증명에서 첫 k개를 넘어서는 성분들의 rate contributions를 제어하는 데 필요한 보조 bound를 제공한다.증명에서는 관련 terms의 boundedness와 vanishing-probability argument도 사용한다.
  • A.5 Theorem 4의 증명: 각 k에 대해 S1:k는 independent components를 갖는 product chain이므로, Theorem 4를 product-chain mixing 및 cutoff에 관한 기존 결과와 연결한다.인용된 참고문헌에는 Diaconis and Saloff-Coste [1996, Thm.2.9]와 Levin et al. [2009, Ch.20.4]가 포함된다.
  • A.5.1 product chain의 mixing time 관련 참고문헌: 관련 mixing-time quantity는 성분 전반에서 vi를 상수로, 즉 모든 i에 대해 vi = ¯v로 선택할 때 최대화되며, 따라서 mixing time은 최소화된다.해당 quantity는 flipping rates에 대한 명시된 가정하에서 ¯Z(v)^−1 lim inf_i→∞ vi이다.
  • B 시뮬레이션 연구 보충 자료: 보충 simulation 자료는 Section 6.2의 연구에 대한 추가 traceplots, acceptance rates, effective sample sizes를 제공한다.제공된 문단은 이러한 diagnostics를 식별하지만 수치나 비교 결과는 보고하지 않는다.

B.1 Section 6.2 보충 … C.3 Metropolis-within-Gibbs sampler

보충 자료는 discrete target이 더 거칠어질수록 locally balanced proposal이 대안보다 우수함을 보이고, Ising benchmark와 Bayesian record-linkage model, likelihood, Metropolis-within-Gibbs sampler를 자세히 설명한다. Record-linkage sampler는 Gibbs step으로 hyperparameter를 업데이트하고, local matching move에 기반한 경쟁 Metropolis scheme을 통해 matching structure를 업데이트한다.

  • B.1 Section 6.2 보충: Figure 8은 n = 500에서 Hamming-distance traceplot과 추정된 autocorrelation function을 사용해 Section 6.2의 다섯 MCMC 방법을 비교한다.
  • B.1 Section 6.2 보충: 거친 target에서는 locally balanced scheme이 경쟁 sampler보다 크게 우수한 반면, 더 평탄한 target에서는 uninformed random-walk proposal이 가장 좋은 성능을 보인다.더 평탄한 target에서는 HB가 약간 더 우수하지만 target의 난도가 증가하면 붕괴한다.
  • B.2 Section 6.3 보충: Section 6.3 benchmark는 image analysis를 위해 Ising-model distributions를 사용하며, pixel variable은 객체 또는 배경 분류를 나타내고 Potts model은 다중 객체 일반화를 제공한다.Ising-type prior는 인접 variable 사이에 양의 상관을 유도하여 biasing term을 갖는 Ising posterior를 생성한다.
  • B.2 Section 6.3 보충: Ising experiment는 grid size를 20에서 1000까지 변화시키고, spatial correlation과 점점 더 informative해지는 external field를 통해 target concentration을 조절한다.Target은 μ = 0, 0.5, 1, 2, 3 및 σ = 0, 1.5, 3, 3, 3을 사용한다. Target 0은 uniform하므로 모든 scheme이 동일한 transition kernel을 공유한다.
  • C Record Linkage application 보충: Record-linkage application은 두 data list 사이의 unknown matching M을 model하며, 주로 Miller et al. [2015]와 Zanella et al. [2016]에 기반한 prior와 Copas and Hilton [1990] 및 Steorts et al. [2016]의 likelihood 아이디어를 따른다.
  • C.1 Matching structure에 대한 prior distribution: Matching prior는 permutation-invariant하며, 전체 entity 수는 matched pair와 singleton을 통해 결정된다. Simulation에서는 p_match와 λ에 약하게 informative한 independent prior를 사용한다.Exchangeability assumption에 따라 고정된 count를 갖는 각 matching은 같은 확률을 가지며, count component는 λ와 p_match에 조건부로 independent Poisson distribution을 따른다.
  • C.2 Likelihood distribution: Likelihood는 discrete spike-and-slab model로, singleton은 empirical field distribution을 따르고 matched record는 distortion probability β = 0.001로 latent field value를 공유한다.Field parameter θ_s는 Zanella et al. [2016]과 같은 standard empirical Bayes procedure에 따라 real-data application에서 empirical하게 추정한다.
  • C.3 Metropolis-within-Gibbs sampler: Metropolis-within-Gibbs sampler는 p_match와 λ에 대한 Gibbs update와 M에 대한 Metropolis update를 교대로 수행하며, Beta 및 truncated-Gamma full conditional과 공통 local-move kernel을 사용한다.Kernel은 index pair를 uniform하게 sampling한 뒤 add, delete, single-switch, double-switch move를 제안한다. M의 업데이트가 계산상 가장 어려운 단계이며 RW, GB, LB, HB 사이에서 비교한다.

C.4 블록화 구현

전체 informed proposal은 n_x와 n_y가 커질수록 비용이 증가하므로, 구현에서는 불변성을 유지하면서 index의 sub-block에 MCMC update를 적용한다. Section 7에서는 크기 300인 block을 uniform random selection과 가능한 match를 선호하는 feature-based selection 사이에서 번갈아 선택한다.

  • C.4 블록화 구현: Sub-block update는 n_x와 n_y가 클 때 GB, LB, HB에서 sampling하는 계산 비용을 줄인다.구현에서는 전체 state space가 아니라 선택된 index subset I와 J에 informed scheme을 적용한다.
  • C.4 블록화 구현: I × J에서의 MCMC kernel이 이에 대응하는 restricted target에 대해 불변이면, block-wise chain은 Q에 대해 여전히 불변이다.
  • C.4 블록화 구현: Section 7에서는 두 index subset I와 J의 size를 300으로 설정했다.이 절차는 다른 random 또는 deterministic subset-selection scheme도 허용한다.
  • C.4 블록화 구현: 구현에서는 uniform random block selection과, 무작위로 선택한 세 feature에서 값이 일치하는 index를 묶는 feature-based block을 번갈아 사용했다.크기가 과도하게 큰 블록은 300개로 균일하게 서브샘플링했으며, 균일 무작위 선택은 기약성을 보장하고 feature 매칭은 가능성 높은 매칭을 선호했다.
Loading 1711.07424v1…