기술적 요약: 희소 컨텍스트 - 상태 전파를 통한 정밀 정규 제약 변수 차수 마르코프 생성

1. 문제 제기

시퀀스 생성 시스템은 종종 국소적 통계적 일관성과 명시적 전역 제어 사이에서 갈등을 겪습니다. 변수 차수 마르코프 (VOM) 모델은 관찰된 연속체가 있는 역사 (history) 의 가장 긴 접미사를 기반으로 각 심볼을 조건화함으로써 전자의 영역에서 탁월한 성능을 발휘하며, 고정 차수 모델의 경직성 없이 국소적 스타일 패턴을 보존합니다. 그러나 정규 제약(예: 고정 위치, 금지된 부분 문자열, 운율 패턴) 을 위한 기존 정밀 방법은 전파 (Belief Propagation, BP) 를 통해 1 차 마르코프 체인에 국한되어 있습니다.

해결하려는 핵심 문제는 다음 두 가지 방식 없이 VOM 생성과 정규 제약을 결합하는 방법입니다:

1. 메모리의 붕괴: 변수 차수 생성기를 1 차 체인으로 투영하여 서로 다른 역사를 병합하고, 올바른 변수 차수 확률에 필요한 구체적인 컨텍스트 정보를 상실하는 것.
2. 상태 공간의 확장: 모델을 밀집 차수-$K$ 상태 공간 (모든 가능한 $K$-튜플) 으로 승격시키는 것. 이는 계산적으로 처리 불가능 ($|V|^K$) 하며 실제 학습 데이터의 희소성을 무시합니다.

단순한 1 차 BP 를 가능성 마스크로 적용하는 방식은 제약 하에서 확률 질량이 낮은 "취약한" 미래와 "풍부한" 미래를 구별하지 못하므로 잘못된 조건부 분포를 초래하여 실패합니다.

2. 방법론

2.1 희소 컨텍스트 - 상태 추상화

본 논문은 희소 컨텍스트 - 상태 구성을 제안합니다. 마지막 방출된 심볼 (1 차) 이나 모든 가능한 $K$-튜플 (밀집 차수-$K$) 을 사용하는 대신, 추론 상태는 학습된 모델에서 관찰된 활성 컨텍스트로 정의됩니다.

• 컨텍스트 - 상태 집합 ($\mathcal{T}$): 백오프 규칙에서 요구되는 접미사에 대해 닫혀 있는 VOM 에 의해 저장된 관찰된 컨텍스트들의 집합.
• 전이 시스템: 전이는 심볼 $y$를 방출하고 새로운 역사의 가장 긴 접미사가 $\mathcal{T}$에 존재하도록 컨텍스트를 업데이트함으로써 정의됩니다.
• 가중치: 전이의 확률은 변수 차수 조건부 확률 $P_{VO}(y|s)$이며, 생성 시 정책 (예: 단일자 회피) 에 의해 수정될 수 있습니다.

2.2 정규 제약 통합

이 방법은 희소 컨텍스트 그래프와 정규 제약 오토마타 $\mathcal{A} = (Q, V, \delta, q_0, F)$ 사이의 곱 오토마타를 구성합니다.

• 상태 공간: 추론 상태는 활성 컨텍스트 $s \in \mathcal{T}$와 오토마타 상태 $q \in Q$인 쌍 $(s, q)$입니다.
• 전파 (Belief Propagation): 이 곱 그래프에서 표준 순방향 - 역방향 동적 프로그래밍이 수행됩니다.
  • 역방향 메시지 ($\beta$): 주어진 곱 상태로부터 지평선까지의 총 잔여 "수용 질량 (accepting mass)"을 계산합니다.
  • 샘플링: 조상 샘플링 (ancestral sampling) 은 로컬 전이 확률과 목적지 상태의 역방향 메시지의 곱에 비례하여 간선을 선택함으로써 수행됩니다.

2.3 생성 시 정책 처리

본 논문은 고정 확률적 소스의 정밀 조건부와 제약 생성 정책(예: Continuator 스타일의 백오프) 을 구분합니다.

• 차수 선택이 고정 소스 정의의 일부인 경우, BP 는 정밀 사후 확률을 산출합니다.
• 차수 선택이 동적 정책 (예: "단일자 연속체가 있는 고차 컨텍스트 건너뛰기") 인 경우, 본 논문은 BP 가 각 후보 차수 내에서 정밀한 미래 질량을 제공하고 정책이 가장 높은 실행 가능한 차수를 선택하는 순차 과정으로 이를 형식화합니다. 이는 의미적 명확성을 유지하기 위해 BP 추론과 정책 논리를 명시적으로 분리해야 합니다.

2.4 가역적 데이터 증강

이 프레임워크는 변환된 코퍼스를 물리적으로 생성하지 않고도 가역적 변환 (예: 피치 전위) 을 지원합니다. 변환 $g$ 하의 컨텍스트 $s$에 대한 카운트는 역방향 조회를 통해 계산됩니다:
$$N_G(s, y) = \sum_{g \in G} N(g^{-1}s, g^{-1}y)$$
이를 통해 BP 메커니즘은 원본 카운트 테이블만 저장하면서 "가상" 증강 소스에서 작동할 수 있습니다.

3. 주요 기여

1. BP-정규 기구의 변수 차수 확장: 본 논문은 1 차 투영의 불일치를 피하고 변수 차수 생성기에 기존 BP-정규 알고리즘을 실행할 올바른 희소 상태 공간 (관찰된 컨텍스트) 을 식별합니다.
2. 정밀 희소 구성: 관찰된 변수 차수 컨텍스트와 제약 오토마타의 곱에서 BP 를 실행함으로써 정밀 제약 생성이 달성될 수 있음을 보여주는 형식적 분해.
3. 복잡도 분석: 추론은 고정된 학습된 곱 그래프에 대해 시퀀스 지평선에 선형이며, 차수 $K$에 지수적인 것이 아니라 도달 가능한 곱 간선의 수에 대해 다항식입니다.
4. 정책 분리: 단일자 회피와 같은 생성 시 차수 정책과 정밀 BP 추론 간의 명확한 구별로, "정밀성"에 대한 주장이 의미적으로 정확하도록 보장합니다.
5. 가상 증강 인터페이스: 물리화된 코퍼스를 저장하지 않고도 원본 수준에서 가역적 데이터 증강을 처리하여 물리화된 코퍼스의 통계와 일치시키는 방법.

4. 실험 결과

4.1 정밀성 검증 (소규모 코퍼)

전체 제약 분포를 열거할 수 있는 작은 정수 코퍼스를 사용하여:

• 분할 함수: BP 로 계산된 분할 함수 ($Z_{BP}$) 는 브루트 포스 열거 ($Z_{brute}$) 와 정확히 일치했습니다 (부동 소수점 정밀도 내).
• 분포 정확도: BP 샘플러가 유도한 조건부 확률은 정밀 제약 분포와 일치했습니다.
• 제약 충족: 샘플링된 모든 시퀀스는 제약 (위치 및 금지된 부분 문자열) 을 충족했습니다.
• 비교: 1 차 지원 마스크는 올바른 분포를 생성하지 못하여 컨텍스트 - 상태 접근법의 필요성을 확인시켰습니다.

4.2 확장성 (바흐 전주곡 실험)

C 장조 바흐 전주곡의 피치 전용 인코딩 (592 개 이벤트, 25 개 피치) 에 대해 지평선 32 와 MAXORDER 제약 (복제된 5-그램 금지) 을 적용하여 확장성 테스트를 수행했습니다.

• 상태 공간 축소: 최대 차수 $K=6$에서 희소 도달 가능한 곱은 1,205 개 상태와 83,207 개 간선을 가졌습니다.
  • 이는 전체 곱 상한 (~340 만 개 간선) 과 밀집 승격 상태 공간 ($25^6 \approx 2.4 \times 10^8$ 개 상태) 보다 수 차수 작습니다.
• 성능: 역방향 통과 계산은 0.1 초 미만, 샘플링은 시퀀스당 0.4 ms 미만이었습니다.
• 정책 동작: 제약된 차수 스택 정책이 제약을 성공적으로 탐색하여, 단순한 고정 소스 조건부에서는 고차에 대해 영 (zero) 질량을 냈을 실행 가능한 연속체를 찾았습니다.
• 가상 증강: 12 키 전위 실험은 가상 증강이 원본 코퍼스만 저장하면서도 성공 질량과 분포 측면에서 명시적 물리화와 일치함을 보여주었습니다.

4.4 구현 비교

기존 Continuator 구현 (위치 제약으로 제한됨) 과 비교하여:

• 새로운 vo-regular-bp 구현은 $K \ge 3$인 경우 역방향 메시지를 훨씬 빠르게 계산했습니다.
• 엔드 - 투 - 엔드 생성 시간은 $K \ge 3$인 경우 더 빨랐습니다.

5. 중요성 및 주장

본 논문은 정규 제약 정보를 백오프를 매력적으로 만드는 변수 차수 구조를 포기하지 않고도 희소 컨텍스트 곱에서 정밀하게 계산할 수 있다고 주장합니다.

• 정확성: 이 방법은 서로 다른 역사를 병합하는 1 차 투영의 함정과 계산적으로 금지적인 밀집 승격의 함정을 피하면서 정규 제약에 조건화된 올바른 변수 차수 분포를 제공합니다.
• 실용성: 이 접근법은 작은 코퍼스와 특정 제약 (예: 표절 방지) 이 중요한 음악과 같은 창의적 분야에서 상호작용적 제약 생성을 가능하게 합니다.
• 겸손함: 저자들은 명시적으로 이 작업이 새로운 정규 제약 이론이나 일반적으로 정규 언어를 위한 BP 를 도입하지 않았다고 명시합니다. 참신함은 엄격하게 변수 차수 확장에 있으며, 알려진 기구를 올바른 희소 상태 추상화에 적용하는 것입니다.
• 한계: 정밀성 주장은 확률적 소스의 정의에 조건부입니다. 생성 시 정책 (예: 단일자 회피) 이 휴리스틱하게 적용되는 경우, 결과는 수정되지 않은 고정 차수 소스의 정밀 사후 확률이 아니라 정밀 제약 생성 정책입니다.

이 작업은 제어된 생성 시스템의 설계 공간에 대한 기술적 분해로서, 변수 차수 예측과 유한 지평선 정규 제어를 결합하는 구체적이고 정밀하며 확장 가능한 솔루션을 제공합니다.