An Expert System for Chorale Harmonization

Kemal EbciogluAAAI 1986

Abstract

The CHORAL system is a pioneering expert system that harmonizes four-part chorales in the style of J.S. Bach using over 270 rules of first-order logic. To achieve computational feasibility, the system utilizes BSL (Backtracking Specification Language), a logic programming language that compiles into efficient C code. By employing a multiple-viewpoint paradigm, including Schenkerian analysis, CHORAL captures deep musical structures beyond simple chord transitions, producing high-quality harmonizations that adhere to classical counterpoint and harmonic rules.

Introduction

Harmonizing a melody in the style of J.S. Bach is a non-trivial task that requires balancing complex rules of counterpoint, harmony, and hierarchical structure. In the mid-1980s, existing AI languages like Lisp and Prolog were often too slow to handle the massive computational resources required for high-quality music generation. The CHORAL system was developed to address two main challenges: the efficiency of logic-based search in a massive space of musical possibilities and the representation of deep musical knowledge beyond local transitions.

Methods

BSL (Backtracking Specification Language)

To overcome the performance limitations of contemporary logic environments, the author designed BSL. Unlike standard Prolog, BSL uses a Lisp-like syntax but follows an "Algol-class" non-deterministic execution model. Key technical features include:

  • Single-Assignment Variables: Facilitates parallelism and efficient backtracking.
  • C-Compilation: BSL programs are compiled into C, significantly outperforming interpreted logic languages of the era.
  • Intelligent Backtracking: A "tagging" mechanism allows the system to jump back to the most "responsible" step when a constraint fails, rather than performing a blind search.

The Multiple Viewpoint Paradigm

The CHORAL system avoids treating music as a single stream. Instead, it uses a round-robin scheduling chain of processes that view the chorale from different angles:

  • Chord Skeleton: Manages high-level harmonic progression and modulations.
  • Fill-in: Generates ornamentations and passing tones.
  • Time-slice: Enforces vertical harmonic constraints, such as avoiding parallel fifths.
  • Melodic String: Focuses on the horizontal flow of individual voices.
  • Schenkerian Analysis: A hierarchical view that "parses" the music to ensure it follows a deep structural logic, such as a descending sequence of notes accompanied by a specific bass movement.
Hierarchical Schenkerian analysis produced by the system.

Knowledge Representation

The system’s knowledge base was manually engineered from the 371 Four-Part Chorales of J.S. Bach (Terry edition), traditional music treatises by Louis, Thuille, and Koechlin, and the author’s own musical intuitions. Musical style is codified as a set of logical constraints and heuristics. For instance, complex first-order formulas are used to define "false relations" or other harmonic errors. Heuristics are weighted to bias the search toward "Bachian" solutions rather than merely valid ones.

Results

The CHORAL system successfully harmonized various melodies, including Chorale no. 48 ("Als vierzig Tag' nach Ostern war"). The output was produced in both conventional music notation and Schenkerian slur-and-notehead notation.

Harmonization output in conventional music notation.

The final system utilized over 270 production rules and constraints. BSL proved to be significantly faster than Prolog or Lisp in traditional RISC environments, enabling the generation of complex musical structures that were previously computationally prohibitive.

Discussion and Limitations

While the system represents a significant step in automated composition, several limitations were identified. The program tends to be "too greedy" for modulations, changing keys more frequently than Bach typically would. Additionally, some generated rhythmic patterns on strong beats were deemed "objectionable" by musicians. While the Schenkerian parser was functional, the knowledge base for this deep analysis remained relatively small due to the inherent complexity of the research. Future work would involve expanding these hierarchical rules and refining the rhythmic heuristics to better capture the nuances of the Bachian style.

Summary updated

BibTeX
@inproceedings{ebcioglu1986expert,
  author = {Kemal Ebcioglu},
  title = {{An Expert System for Chorale Harmonization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure