## 2 The Symbolic Compositional Hierarchical Model
### Constructing a Hierarchy of Parts  
The model is built layer-by-layer with unsupervised learning on a single or multiple musical pieces. In the 'intra-opus' pattern discovery task experiment described in this paper, we build a model for each musical piece separately. The learning process is an optimization problem, where for each layer a set of all possible part compositions of the layer is searched for a minimal subset of compositions that covers a maximal amount of events in the training set. The learning process is driven by statistics of part activations that capture regularities in the input data. It consists of two main steps: (1) finding a set of all possible compositions, denoted candidate compositions, and (2) selecting compositions that explain a maximal amount of events in the training set. To construct a new layer \(\mathcal{L}_{n}\), a set of new candidate compositions \(\mathcal{C}\), which will be considered for inclusion in the new layer, is first formed (Step 1). This set of candidate compositions is obtained by inferring the hierarchy with the training data and generating activations of parts layer-by-layer from \(\mathcal{L}_{0}\) to \(\mathcal{L}_{n-1}\), as explained in Section 2.3. The candidate compositions for layer \(\mathcal{L}_{n}\) are generated from histograms of co-occurrences of \(\mathcal{L}_{n-1}\) part activations within the time window \(\tau_{W}\) (see also Equation (4)). Frequent co-occurrences indicate the presence of underlying patterns. New compositions are formed from combinations of \(\mathcal{L}_{n-1}\) parts where the number of co-occurrences exceeds the learning threshold \(\tau_{C}\). The composition parameter \(\mu\) is estimated from the corresponding histogram. The \(\mathcal{L}_{1}\) candidate compositions are thus constructed as a relative structure of two co-occurring \(\mathcal{L}_{0}\) part activations, both occurring within the time window \(\tau_{W}\). This procedure is repeated on all consecutive layers, where activations of parts co-occurring within the time window on a previous layer \(\mathcal{L}_{n-1}\) compose new part candidates on the next layer \(\mathcal{L}_{n}\). Since the model allows for partial overlapping of the covered structure (e.g., \(P_{1}^{2}\) in Figure 1), the structures on these layers represent 3-4 music events. Consequently, the \(\mathcal{L}_{N}\) candidate compositions include all combinations of \(\mathcal{L}_{N-1}\) part pairs representing structures of \(2^{N-1}\)-\(2^{N}\) music events. In the second step, a subset of compositions from \(\mathcal{C}\) that covers a maximum number of events in the input data is selected. As the problem of selecting a set of compositions from \(\mathcal{C}\) which optimally cover the input data is NP (nondeterministic polynomial time) complete, a greedy approach, which selects a subset of compositions and leaves a minimal amount of events in the input uncovered, was introduced in [41]. The composition selection uses part coverage as a measure of the part's suitability for selection. The coverage of the part \(P_{i}^{m}\) can be obtained by projecting its activations to the input layer and observing the covered events. For a single activation of the part \(P_{i}^{m}\) at the time \(T\) and the location \(L\), coverage is defined as the union of coverages of its subparts:\[C(A(P_{i}^{n}))=\bigcup_{j=0}^{K-1}C(A(P_{k_{j}}^{n-1})). \tag{6}\]  
When the input layer is reached, the coverage is defined by the presence of an event at the given location and time as:  
\[C(A(P_{1}^{0}))= \begin{cases}A_{L}(P_{1}^{0}):&A_{M}(P_{1}^{0})>0\\ \emptyset:&\text{otherwise}\end{cases} . \tag{7}\]  
Based on coverage, the greedy composition selection approach is defined as follows:  
* the coverage of each part from \(\mathcal{C}\) is calculated as a union of events in the training data covered by all activations of the part,
* parts are iteratively added to the new layer \(\mathcal{L}_{n}\) by choosing the part that adds most to the coverage of the entire training set in each iteration.