기술 요약: 재즈 화성학에서의 E-graph 를 활용한 라이브러리 학습

문제 제기

본 논문은 재즈 화성학 영역 내의 음악 패턴 발견 (Musical Pattern Discovery, MPD) 과제의 난제를 다룹니다. 핵심적인 어려움은 동시에 다음 두 가지 조건을 만족하는 반복적인 음악적 규칙성을 식별하는 데 있습니다:

1. 충분히 추상적이어야 비정확한 반복을 포괄할 수 있어야 합니다 (단순 문자열 매칭이 아닌 '가족 유사성' 구조를 포착).
2. 분석적으로 유의미해야 구조적 해석을 지원할 수 있어야 합니다.

기존 접근법들은 종종 트레이드오프에 직면합니다: 매우 추상적인 패턴은 오탐지 (false positives) 를 생성할 위험이 있는 반면, 매우 구체적인 패턴은 변형을 포착하지 못합니다. furthermore, 전통적인 방법들은 파싱 (고정된 문법으로부터 유도 추론) 과 라이브러리 학습 (프로그램 코퍼스에서 재사용 가능한 추상화를 발견) 을 분리합니다. 저자들은 표면 데이터 (화성 진행) 에서 직접 패턴을 학습하는 비지도 설정에서 이 두 가지 문제는 상호 의존적이라고 주장합니다. 즉, 가능한 유도들의 공간은 사용 가능한 추상화에 의존하고, 추상화의 유용성은 특정 유도에서의 역할에 의존합니다. 순차적인 접근법 (먼저 파싱을 철저히 수행한 후 라이브러리를 학습) 은 파스 트리의 조합적 폭발 (카탈란 수에 비례하여 확장) 로 인해 계산적으로 비실용적입니다.

방법론

저자들은 E-graph(등식 그래프) 를 사용하여 연역적 파싱 (deductive parsing) 과 라이브러리 학습을 통합하는 비지도 계산 모델을 제안합니다. 이 시스템은 하향식 논리 프로그래밍을 지원하는 등식 포화 (equality saturation) 프레임워크의 선언적 확장인 egglog로 구현되었습니다.

1. 도메인 특화 언어 (DSL) 로서의 표현

화성 분석은 DSL 내의 생성적 프로그램으로 모델링됩니다.

• 기저 요소 (Primitives): 화음 기호를 다시 쓰는 대신, 문법은 화성적 관계를 나타내는 논리 술어 (예: V-I, Descending5th) 를 사용합니다. 이러한 관계는 화음 인스턴스 간의 제약 (예: root 간격, 화음의 질) 을 주장합니다.
• 구조: 유도는 이러한 관계들의 조합이며, 내부 노드가 구조화된 화음 객체를 연결하는 논리 술어인 트리를 형성합니다.

2. 통합 파이프라인

모든 파스 트리를 나열하는 조합적 폭발을 피하기 위해 이 모델은 세 가지 상호 연결된 단계로 작동합니다:

• 파싱 단계 (연역적 파싱):

  • 화성 진행은 논리적 사실 (공리) 로 인코딩됩니다.
  • E-graph 내에서 CYK 스타일의 연역적 절차가 구현됩니다.
  • 단일 파스 트리에 고정하는 대신, 시스템은 공유 패킹 파스 포레스트 (Shared Packed Parse Forest, SPPF) 표현을 유지합니다. 작품의 모든 유효한 유도는 단일 E-graph 내의 동등 클래스 (e-classes) 로 압축되어 저장되며, 동일한 하위 유도들이 병합됩니다.
  • 필터링 단계 (루트 연결성의 하향식 전파) 를 통해 작품의 완전한 파싱에 참여하는 유도만 유지되도록 보장합니다.

• 추상화 단계 (반-통일, Anti-unification):

  • 시스템은 E-클래스에 대한 반 - 통일 (anti-unification) 수행을 통해 후보 패턴을 식별합니다.
  • 반 - 통일은 두 하위 유도 간의 최소 일반화 (least general generalization) 를 계산하여, 불일치하는 하위 트리를 변수로 대체하고 매개변수화된 템플릿을 생성합니다.
  • 이 과정은 효율성을 보장하기 위해 E-graph 포화와 교차하여 수행되며, 개별 트리 대신 동등 클래스 간의 반 - 통일기를 계산합니다.

• 리팩토링 단계 (라이브러리 학습 및 비용 분석):

  • 후보 패턴은 E-graph 에 다시 쓰기 규칙으로 추가되어 이러한 새로운 추상화를 통해 얻을 수 있는 모든 동등한 유도를 탐색하는 등식 포화 (equality saturation) 를 트리거합니다.
  • 비용 집합 분석: 시스템은 최소 설명 길이 (Minimum Description Length, MDL) 목적 함수를 사용하여 후보 라이브러리를 평가합니다. E-graph 의 각 항은 (cost(ℒ), cost(𝒟|ℒ)) 쌍의 비용 집합과 연관되어 있으며, 이는 라이브러리의 복잡성과 해당 라이브러리를 기반으로 데이터를 인코딩하는 비용을 나타냅니다.
  • 빔 탐색 (beam-search) 휴리스틱은 검색 공간을 축소하여 총 설명 길이를 최소화하는 라이브러리 ℒ* 를 찾습니다: arg min (cost(ℒ) + cost(𝒟|ℒ)).
  • 최종 출력은 리팩토링된 코드베이스입니다: 학습된 화성 패턴 라이브러리와 해당 라이브러리의 관점에서 표현된 각 작품에 대한 압축된 유도들입니다.

주요 기여

1. 공동 추론 프레임워크: 본 논문은 개별 작품의 구조화된 유도들과 공유된 재사용 가능한 추상화 집합을 순차적 단계가 아닌 상호 의존 변수로 간주하여 공동으로 추론하는 새로운 아키텍처를 제안합니다.
2. 음악을 위한 E-graph 통합: 이 연구는 원래 프로그램 합성을 위해 개발된 Babble 알고리즘을 음악 이론 영역에 적용합니다. E-graph 를 활용함으로써 모델은 명시적인 나열 없이도 동등한 유도들의 기하급수적으로 큰 집합을 표현하고 조작할 수 있습니다.
3. 유형화된 추상화로서의 패턴 형식화: 이 작업은 음악 패턴을 표면 하위 문자열이 아닌, 완전한 화성 분석을 생성하는 데 재사용될 수 있는 구성적, 유형화된 빌딩 블록 (논리적 관계) 으로 형식화합니다.
4. egglog 구현: 저자들은 CYK 파싱과 반 - 통일을 효율적으로 표현하기 위해 하향식 논리 프로그래밍 기능을 활용하는 egglog 를 사용한 선언적 구현을 제공합니다.

결과

현재의 계산적 한계로 인해 더 크고 모호성이 높은 데이터셋 대신, 본 연구는 세 개의 재즈 스탠다드 (Red Clay, Valse Hot, Sunny) 로 구성된 소규모 코퍼스에서 개념 증명 평가를 제시합니다.

• 정량적 결과:

  • 압축: 공유 라이브러리를 통한 공동 학습은 기본 문법 기준 87 개 노드였던 총 유도 크기를 27 개 노드로 줄였습니다.
  • 효율성: 공동 학습의 정규화된 압축률 (CR) 은 1.5였으며, 이는 각 작품이 자체 라이브러리를 유도하는 조각별 학습 (piece-wise learning) 의 1.16과 비교됩니다. 이는 작품들을 고립적으로 처리하는 것보다 작품 간 추상화를 공유하는 것이 더 경제적인 설명을 산출함을 보여줍니다.
  • 저장 비용: 공유 라이브러리 오버헤드에도 불구하고, 공동 접근법은 조각별 접근법 (47) 에 비해 더 낮은 총 저장 비용 (31) 을 발생시켰습니다.

• 정성적 결과:

  • 모델은 ii-V-I, 5 진법 하행과 같은 표준 재즈 진행을 재사용 가능한 패턴으로 성공적으로 식별했습니다.
  • 범주 문법에서의 방향성 함수 적용과 일치하는 구조적으로 불완전한 구성 요소 (예: "도미넌트가 결여된 토닉"과 같은 왼쪽 가지 패턴) 를 발견했습니다.
  • 비전통적 해석: Red Clay에서 모델은 Jazz Harmony Tree Bank (JHTB) 의 전문가 주석과 다른 방식으로 시작 토닉에 깊은 구조적 역할을 부여하는 유도를 생성했습니다. 저자들은 이는 특정 추상화 (f6) 의 중첩된 영역 간 재사용을 가능하게 하는 압축 효율성에 의해 주도된 것이라고 지적합니다.
  • Sunny에서 모델은 VI-V 관계를 사용하여 복잡한 시퀀스를 올바르게 해석했으며, 장조 맥락에서 발생할 수 있는 유효하지 않은 적용된 도미넌트 해석을 피했습니다.

중요성과 주장

본 논문은 이 접근법이 음악 인지 및 이론에 대한 새로운 관점을 제공한다고 주장합니다:

• 인지적 타당성: 이 모델은 인간 청자가 가설과 수정의 반복적 사이클을 통해 음악적 이해를 습득하며, 시퀀스를 고차 단위인 "조각 (chunk)"으로 묶을 수 있게 해주는 재사용 가능한 스키마의 "라이브러리"를 구축할 수 있음을 시사합니다. 이는 소프트웨어 공학의 리팩토링 과정과 유사합니다.
• 압축으로서의 이론: 화성적 스키마와 공식적 원형과 같은 이론적 구성 요소는 반복적인 음악적 경험에 따른 암묵적 추상화와 재사용, 그리고 간결한 설명 (압축) 에 대한 압력으로 인해 등장할 수 있다고 가정합니다.
• 한계 및 향후 작업: 저자들은 현재 구현이 크고 모호성이 높은 코퍼스까지 확장 가능하지는 않다고 인정하며 주장에 대해 겸손한 태도를 보입니다. Red Clay의 "비전통적" 분석은 소규모 데이터셋의 한계를 반영할 수 있으며, 여기서 틈새 패턴이 압축에 최적인 것처럼 보일 수 있다고 지적합니다. 향후 작업은 구현 효율성 향상과 더 크고 다양한 데이터셋이 필요하여, 학습된 패턴이 특정 작품에 과적합되는 것이 아니라 장르 전반에 걸쳐 일반화되도록 해야 합니다.

본 논문은 모든 경우에 음악적으로 타당한 분석을 보장하지는 않지만, 압축 유도 라이브러리 학습의 프레임워크가 표면 데이터로부터 비지도 방식으로 구조화되고 재사용 가능한 음악 패턴이 어떻게 발견될 수 있는지에 대한 엄격한 계산적 가설을 제공한다고 결론지었습니다.