Constrained Hidden Markov Models. Hidden Markov models (HMMs) have been extensively used for the automatic harmonization of a given melody, since their formalization describes the targeted task very well: given a sequence of observed notes (melody), find the most probable (hidden) sequence of chords that is compatible with the observations, according also to a chord transition matrix. In several studies of HMM– based melodic harmonization methodologies, a straightforward distinction is made on the role that some chords play to the composition – mainly the cadence of the phrase. For instance, the cadences of produced harmonizations by the HMM developed in [5] were utilized to evaluate the system’s performance, by comparing the cadence patterns that were produced by the system to the ones observed in the dataset. Several HMM approaches discuss the utilization of some methodological tools to amplify the role of the cadence in the harmonization process. For instance, in [1] and [18] a backwards propagation of the HMM methodology is proposed, i.e. by examining the prior probabilities of the final chord given the final melodic note. The Markov decision process followed in [42] rewards the authentic cadences, thus providing higher probabilities to chord sequences that end with an authentic cadence. In [43] the phrases are divided in tonic, subdominant, dominant, and parallel tonic chords, allowing a trained HMM to acknowledge the positions of cadences, although the selection of chords is performed through a rule–based process. A commercial application utilizing HMM for melodic harmonization is mySong [39], which receives the melody by the singing voice of the user, extracts the pitches of the melody and employs an HMM algorithm to provide chords for the melody. According to the HMM approach utilized in mySong, prior probabilities are considered not only for the beginning chord of a piece, but also for the ending one, a fact that further biases the choice of solutions towards ones that incorporate first and final chords that are more often met in the training dataset. The approach presented in this section is motivated by the research in the aforementioned works, but it is different on a fundamental aspect: it allows the deterministic (not probabilistic) in- sertion of chords at any place in the chord sequence. Such an approach is important since it permits the extension of the “learned” transitions, potentially allowing to build composite harmonization that comprise characteristics from various...
