Bayesian inference for partial orders from random linear extensions: power relations from 12th Century Royal Acta

기술적 요약: 무작위 선형 확장에서 유도된 부분 순서에 대한 베이지안 추론

문제 제기
본 논문은 근본적인 구조가 완전한 (전체) 순서가 아닐 수 있는 순위 데이터로부터 진화하는 사회적 위계를 추론하는 통계적 난제를 다룬다. 저자들은 12 세기 영국 및 노르만 왕실의 Acta(법적 문서) 371 건에 기록된 67 명의 주교들의 등재 순서를 분석한다. 역사가들은 이 순서가 지위, 연공서열, 정치적 영향력에 기반한 사회적 위계를 반영한다고 가정한다. 그러나 데이터는 노이즈가 있으며 불완전하다 (각 목록마다 주교들의 부분 집합만 나타남). 또한 근본적인 위계는 단일 선형 순위가 아니라 비교 불가능한 행위자 쌍을 포함하는 부분 순서일 수 있다. Mallows 및 Plackett-Luce 와 같은 기존 순위 데이터 모델들은 일반적으로 전체 순서나 문맥 독립적 확률을 가정하는데, 이는 전이성이 기대되지만 순서가 부분적인 이러한 역사적 맥락에는 부적절할 수 있다.

방법론
저자들은 잠재 상태가 진화하는 부분 순서 (poset) 이고 관측 데이터가 해당 poset 의 무작위 선형 확장이 되는 베이지안 은닉 마르코프 모델 (HMM) 을 제안한다.

1. 잠재 변수 매개변수화:

   • 시간 $t$에서의 poset 인 $h(t)$는 잠재 $K$ 차원 지위 행렬 $Z(t)$에서 생성된다.
   • 각 주교 $j$에 대해 잠재 권위 벡터 $U^{(t)}_j$는 1 차 벡터 자기회귀 (VAR) 로 시간 경과에 따라 진화한다.
   • 연공서열에 기반한 공변량 효과 $\beta_{s_{t,j}}$가 권위 벡터에 추가되어 지위 벡터를 형성한다: $Z^{(t)}_j = U^{(t)}_j + \mathbf{1}_K \beta_{s_{t,j}}$.
   • poset $h(t)$는 $Z(t)$의 열들에서 유도된 $K$ 개의 전체 순서들의 교집합으로 정의된다. 주교 $i$가 poset 에서 주교 $j$보다 앞서기 위한 필요충분조건은 모든 $k=1,\dots,K$에 대해 $Z^{(t)}_{i,k} > Z^{(t)}_{j,k}$인 것이다.
   • 차원 $K$는 $\lfloor D/2 \rfloor$ (여기서 $D$는 활성 주교들의 최대 수) 로 선택되어, 모델이 가능한 모든 poset 을 표현할 수 있도록 한다 (보편적 표현 성질).

2. 관측 모델 (줄서기 점프):

   • 관측된 목록들은 진정한 poset 의 "노이즈가 있는" 선형 확장으로 모델링된다.
   • 저자들은 "줄서기 점프" 메커니즘을 도입한다: 확률 $p$로 목록의 다음 행위자는 poset 제약 조건을 무시하고 균일하게 무작위로 선택된다. 그렇지 않으면, 나머지 부분 순서의 무작위 선형 확장에 따라 행위자가 선택된다.
   • 이는 관측된 순서가 근본적인 위계와 모순되는 "노이즈"를 허용하면서도 유효한 선형 확장이 더 확률적이라는 제약을 유지한다.
   • 이 모델은 현재 존재하는 행위자들이 유도한 부분 순서에 조건을 부여함으로써 불완전한 목록 (주교들의 부분 집합) 을 처리한다.

3. 사전 분포와 일관성:

   • poset 과정에 대한 사전 분포는 **변량 일관성 (marginally consistent)**이 있도록 구성된다. 즉, (행위자의 부분 집합에 의해 유도된) 부분 순서의 분포는 전체 순서의 분포와 일관된다. 이는 잠재 벡터 $U$와 상관 매개변수 $\rho$에 대한 특정 사전 분포를 사용하여 달성된다.
   • 초매개변수 $\rho$는 poset 의 "깊이" (가장 긴 사슬의 길이) 를 조절한다. 사전 분포는 깊이와 관련하여 무정보적이도록 설계되어, 모든 poset 에 대한 균일 사전 분포에서 관찰되는 깊이 3 의 poset 에 대한 집중을 피한다.
   • 연공서열 효과 $\beta$는 연공서열이 지위와 상관된다는 역사적 기대를 반영하여 순서화되도록 ($\beta_1 > \beta_2 > \dots$) 제약되지만, 제약이 없는 모델도 테스트된다.

4. 추론:

   • 사후 추론은 Metropolis-Hastings 업데이트를 사용하는 마르코프 연쇄 몬테 카를로 (MCMC) 를 통해 수행된다.
   • 가능도는 선형 확장의 계수를 포함하며, 이는 #P-완전 문제이다. 저자들은 이 데이터셋에서의 소수 행위자 ($m \le 22$) 에 대해 실행 가능한 재귀적 계수 알고리즘 (특히 lecount 패키지) 을 활용하지만, 이는 더 큰 문제의 확장성을 제한한다.

주요 기여

• 새로운 모델 클래스: 본 논문은 근본적인 구조가 부분 순서인 시계열 순위 데이터를 모델링하기 위한 일반적 프레임워크를 도입하여 Mallows 및 Plackett-Luce 와 같은 기존 모델을 일반화한다.
• 변량 일관성: 저자들은 poset 에 대한 잠재 변수 사전 분포가 변량 일관성을 가지며, 이는 부분 순서에 대한 임의의 사전 분포에서 종종 위반되는 성질임을 유도하고 증명한다.
• 보편적 표현: 잠재 차원 $K \ge \lfloor D/2 \rfloor$를 사용하면 모델이 가능한 모든 poset 시계열을 표현할 수 있음을 보여줌으로써 복잡한 위계에 대한 구조적 편향이 없음을 보장한다.
• 역사적 적용: 이는 12 세기 왕실 Acta 증인 목록을 부분 순서로 명시적으로 모델링하여 사회적 위계를 분석한 최초의 통계적 분석으로, 연공서열의 효과와 개인적 권위를 분리한다.

결과

• 모델 적합도: poset 기반 모델은 적합도 (Leave-One-Out 교차 검증 및 베이지스 인자 측정) 측면에서 더 단순한 대안들 (Vertex-Series-Parallel 순서, Bucket Order) 및 Plackett-Luce 시계열 혼합 모델보다 우수하다.
• 연공서열 대 권위: 분석은 지위가 연공서열에 강력하게 의존함을 확인하며, 연공서열의 효과는 순위 번호가 증가함에 따라 감소한다. 그러나 모델은 "권위"(연공서열에서의 편차) 를 성공적으로 분리해낸다.
• 역사적 통찰:
  • 노르만 주교들: 모델은 12 세기 초부터 영국 주교들에 비해 아브랑슈, 바이외, 에브뢰 출신의 노르만 주교들의 지위가 하락하는 것을 감지하는데, 이는 이전에 정량화되지 않았던 경향이다.
  • 정치적 영향력: 헨리 드 블루아 (스텝 왕의 형제) 와 나이젤 오브 일리와 같은 특정 주교들의 지위는 연공서열과 독립적으로 정치적 호의나 실각과 상관되는 방식으로 변동한다.
  • 위계 구조: 재구성된 합의 poset 은 상대적으로 얕으며, 일반적으로 몇 개의 중간 순위 주교 그룹과 그 위나 아래에 있는 소수의 행위자로 구성되며, 깊고 경직된 위계보다는 그렇지 않다.

의의 및 주장
본 논문은 노이즈가 있고 불완전한 순위 데이터로부터 진화하는 부분 순서를 추론하기 위한 통계적으로 엄격한 방법론 개발을 주요 기여로 주장한다. 이를 역사적 Acta에 적용함으로써 저자들은 12 세기에 사회적 위계가 어떻게 기능했는지에 대한 정량적 증거를 제공하며, 특히 구조적 연공서열과 유동적인 정치적 권위를 구별한다.

저자들은 방법론의 계산적 확장성에 대해 겸손하게 언급하며, 선형 확장의 계수라는 #P-완전 성질이 모델을 약 20 명의 소수 행위자를 가진 데이터셋으로 제한한다고 인정한다. 그들은 더 큰 데이터셋의 경우 VSP 나 Bucket Order 와 같은 제한된 poset 클래스가 필요한 타협일 수 있다고 제안한다. 또한 모델이 데이터를 잘 적합시키지만, "노이즈" 모델이 오류가 한 방향 (줄서기 점프) 에서 발생한다고 가정하며, 향후 작업은 양방향 노이즈 모델을 탐구할 수 있다고 지적한다.

궁극적으로 본 논문은 이러한 유형의 사회 데이터에 대해 전체 순서를 가정하는 것 (표준 순위 모델과 같이) 은 정당화되지 않으며, 부분 순서 모델이 역사적 사회 구조에 대해 더 정확하고 해석 가능한 표현을 제공한다고 주장한다.