## 2 Methodology for Jazz Standard Cross-Harmonization
### Supported Constraint Hidden Markov Model  
In the typical Hidden Markov Model method, inferring the sequence of a set of known hidden states for each time step \(t\), the Viterbi algorithm is employed, which iteratively accumulates probabilities for each chord being the chord of choice in a matrix \(\Delta\) and keeps track of the best possible previous chord for each current chord through a matrix of \"best previous chord\" indexes, \(\psi\). The probabilities in \(\Delta\) are calculated using the following components:  
1. The transition probabilities \(T^{N\times N}\). 2. The melody-related fitness of each chord, expressed through the \(O^{N\times K}\) matrix. 3. The accumulated \(\Delta\) value of the best possible previous, based on the transition probability and the melody fitness of the above mentioned matrices. Specifically, the probability calculated for each chord, \(j\), is the maximum of the element-wise product of each chord being the one in the previous step, times the probability of the examined chord to harmonize the given melody:  
\[\Delta[j,t]=\max[\left(\Delta[:,t-1]\odot T[:,j]\right)O[j,t]]\]  
If \(T\) is sparse enough, which is expected in the case for a transition matrix of a single song (Song B), or if there is a misalignment between melody emissions and the learned melodic relative pitch classes for each chord (resulting from the large negative penalty for chord-melody mismatch discussed in Section 2.1), all elements of the current time step column (\(\Delta[:,t]\)) can be zero. A common practice in HMM models is to \"smoothen\" all the incorporated matrices by replacing zero values with a small arbitrary value, for preventing all-zero occurrences in columns of \(\Delta\). This allows the continuation of all paths in the trellis diagram until the end of the graph, preventing the Viterbi algorithm from \"crushing\", i.e., having all final states of the trellis paths with zero accumulated probability values [38]. Note that zeroing out all the \(\Delta\) values in a single column will lead to zeroing out all values in all subsequent columns. Smoothing will indeed give a chance to the non-zero component in the computation of \(\Delta[j,t]\) to be the deciding factor; i.e., if zero comes as a result of transition impotency, then best melody matching will determine chord selection and vice versa. Smoothing, however, introduces improbably transitions or melody-to-chord mismatches that are irrelevant to the underlying musical idiom of the jazz standards. The presented method attempts to resolve this issue by providing idiom-relevant solutions to transition or melody incompatibilities. One way this issue is addressed is through chord grouping, as discussed in Section 2.2. This step not only makes transitions more dense, since previously unrelated chords are now connected with non-zero transition probabilities, but also gives more options when it comes to chord-melody matching, since chords with various extensions within a group are simultaneously considered. Group transitions within a piece, however, might as well be too sparse, since a jazz standard is not necessary to involve transitions between all possible chord groups, let alone \begin{table}
\begin{tabular}{c c c} \hline \hline
**Group** & **Rule** & **Num. of Chords** \\ \hline Dominant & \(\{4,10\}\in t\vee(\{4,8\}\in t\wedge 11\
otin t)\) & 30 \\ Suspended & \(5\in t\wedge\{3,4\}\
otin t\) & 6 \\ Diminished & \(\{3,6\}\in t\wedge 10\
otin t\) & 2 \\ Major & \(4\in t\wedge 10\
otin t\) & 13 \\ Minor & \(3\in t\wedge t\
ot\in\) Diminished & 17 \\ Other & Not in other groups & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Chord grouping method and number of chords per group. Chord types are represented by their pitch class set relative to the chord root. chords in all groups. To this end, a transition \"_support_\" (\(S[i,j]\)) method is proposed that incorporates the transition probabilities of groups of the entire learned idiom.