# An Analysis of Rhythmic Patterns with Unsupervised Learning
## 2 The Compositional Hierarchical Model for Rhythm Modeling
### Learning and Inference
#### 2.2.1 The Learning Algorithm  
We use a greedy approach to solve the set-cover problem. Learning takes place iteratively, where in each iteration, we pick a composition which covers the largest amount of uncovered events in the input and add it to the current layer. The learning algorithm is composed of two steps: finding a set of candidate compositions and adding compositions to the layer. To construct the set of candidate compositions for a new layer \(\mathcal{L}_{n}\), we first calculate activations of all parts from the layer \(\mathcal{L}_{0}\) up to the layer \(\mathcal{L}_{n-1}\). We then observe the co-occurrences of \(\mathcal{L}_{n-1}\) part activations on the training set within a time window. The co-occurrences indicate parts, which frequently activate simultaneously in a certain relationship and are therefore candidates for forming compositions, as they are assumed to form common concepts. They are estimated from histograms of co-occurring part activations, which are formed according to the distances and scales of activation pairs. New candidate compositions are formed from parts where the number of co-occurrences  
Figure 4: An \(\mathcal{L}_{1}\) part with three events is activated on a simple input signal. Four activations are shown, all occurring at the same time, but with different scales encoded in \(A_{S}\) (between 0.25 and 1). exceeds the learning threshold \(\tau_{L}\). The composition parameters \(\mu_{1},\mu_{2}\) and \(\sigma_{1},\sigma_{2}\) are estimated from the corresponding histograms (an example is given in Figure 5) and each new composition is added to the set of candidate compositions \(\mathcal{C}\). The pseudo-code of the procedure is shown in Figure 6.  
From the set of candidate compositions \(\mathcal{C}\), parts are iteratively chosen and added to the new layer as follows:  
Figure 5: An example of the activation co-occurrence histogram. The axes represent the relative scale and locations of activations of a pair of parts. Figure 6: The algorithm for generating histograms and candidate compositions. * coverage of each part (events that part activations explain in the training set) is calculated,
* the part that adds most to the coverage of the entire training set is chosen. This ensures that only compositions that provide enough coverage of \"new\" data with regard to the currently selected set of parts will be added,
* the algorithm stops when the added coverage falls below the learning threshold \(\tau_{C}\) or the overall coverage reaches the threshold \(\tau_{P}\). To avoid generating combinations, of which subpart activations are far apart, we limited the search with the \(withinWindow(Act_{1},Act_{2})\) function. The pseudo-code for selecting the candidate compositions is outlined in Figure 7. Although the algorithm, which performs a greedy selection of compositions, does not provide the optimal subset of part candidates, its output is sufficient for the use in our model. The problem of candidate selection can be translated to a set-cover problem, which is known to be NP-hard. The greedy approach therefore represents an approximation of the best solution. ```
1:procedure SELECTCOMPOSITIONS(\(\mathcal{C}\))
2:\(prevCov\gets 0\)
3:\(cov\leftarrow\emptyset\)
4:\(\mathcal{L}_{n}\leftarrow\emptyset\)
5:\(sumInput\leftarrow|\mathcal{I}|\)
6:repeat
7:for\(P\in\mathcal{C}\)do
8:\(c\gets 0\)
9:\(\mathcal{F}\gets coverage(\mathcal{L}_{n}\cup P)\)
10:\(c\gets c+|\mathcal{F}|\)
11:\(cov[P]\gets c/sumInput\)
12:endfor
13:\(chosen\leftarrow\operatorname*{argmax}(cov)\)
14:\(\mathcal{L}_{n}\leftarrow\mathcal{L}_{n}\cup\overset{P}{chosen}\)
15:\(\mathcal{C}\leftarrow\mathcal{C}\setminus\overset{}{chosen}\)
16:if\(cov[Chosen]-prevCov<\tau_{C}\)then
17:break
18:endif
19:\(prevCov\gets cov[Chosen]\)
20:until\(prevCov>\tau_{P}\vee\mathcal{C}=\emptyset\)
21:return\(\mathcal{L}_{n}\)
```  
**Figure 7. The greedy algorithm for selection of compositions from the candidate set \(\mathcal{C}\). Compositions that add the most to the coverage of information in the learning set are prioritized.