{'fraction_non_alphanumeric': 0.04686558562334634, 'fraction_numerical': 0.0119456160113169, 'mean_word_length': 4.162136578769439, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Probabilistic Rule Realization and Selection

Abstraction and realization are bilateral processes that are key in deriving intelligence and creativity. In many domains, the two processes are approached through rules: high-level principles that reveal invariances within similar yet diverse examples. Under a probabilistic setting for discrete input spaces, we focus on the rule realization problem which generates input sample distributions that follow the given rules. More ambitiously, we go beyond a mechanical realization that takes whatever is given, but instead ask for proactively selecting reasonable rules to realize. This goal is demanding in practice, since the initial rule set may not always be consistent and thus intelligent compromises are needed. We formulate both rule realization and selection as two strongly connected components within a single and symmetric bi-convex problem, and derive an efficient algorithm that works at large scale. Taking music compositional rules as the main example throughout the paper, we demonstrate our model's efficiency in not only music realization (composition) but also music interpretation and understanding (analysis).


Introduction
Abstraction is a conceptual process by which high-level principles are derived from specific examples; realization, the reverse process, applies the principles to generalize [1,2]. The two, once combined, form the art and science in developing knowledge and intelligence [3,4]. Neural networks have recently become popular in modeling the two processes, with the belief that the neurons, as distributed data representations, are best organized hierarchically in a layered architecture [5,6]. Probably the most relevant such examples are auto-encoders, where the cascaded encoder and decoder respectively model abstraction and realization. From a different angle that aims for interpretability, this paper first defines a high-level data representation as a partition of the raw input space, and then formalizes abstraction and realization as bi-directional probability inferences between the raw inputs and its high-level representations.
While abstraction and realization is ubiquitous among knowledge domains, this paper embodies the two as theory and composition in music, and refers to music high-level representations as compositional rules. Historically, theorists [7,8] devised rules and guidelines to describe compositional The main contribution of the paper is to propose and implement a unified framework that makes reasonable rule selections and realizes them in an efficient way, tackling the two challenges in one shot. As one part of the framework, we introduce a two-step dimensionality reduction technique-a group de-overlap step followed by a screening step-to efficiently solve music rule realization. As the other part, we introduce a group-level generalization of the elastic net penalty [15] to weight the rules for a reasonable selection. The unified framework is formulated as a single bi-convex optimization problem (w.r.t. a probability variable and a weight variable) that coherently couples the two parts in a symmetric way. The symmetry is beneficial in both computation and interpretation. We run experiments on artificial rule sets to illustrate the operational characteristics of our model, and further test it on a real rule set that is exported from an automatic music theorist [11], demonstrating the model's selectivity in music rule realization at large scale.
Although music is the main case study in the paper, we formulate the problem in generality so the proposed framework is domain-agnostic and applicable anywhere there are rules (i.e. abstractions) to be understood. Detailed discussion at the end of the paper demonstrates that the framework applies directly to general real-world problems beyond music. In the discussion, we also emphasize how our algorithm is non-trivial, not just a simple combinatorial massaging of standard models. Therefore, the techniques introduced in this paper offer broader algorithmic takeaways and are worth further studying in the future. 2 The Formalism: Abstraction, Realization, and Rule Abstraction and Realization We restrict our attention to raw input spaces that are discrete and finite: X = {x 1 , . . . , x n }, and assume the raw data is drawn from a probability distribution p X , where the subscript refers to the sample space (not a random variable). We denote a high-level representation space (of X ) by a partition A (of X ) and its probability distribution by p A . Partitioning the raw input space gives one way of abstracting low-level details by grouping raw data into clusters and ignoring within-cluster variations. Following this line of thought, we define an abstraction as the process: (X , p X ) → (A, p A ) for some high-level representation A, where p A is inferred from p X by summing up the probability masses within each partition cluster. Conversely, we define a realization as the process: (A, p A ) → (X , p X ), where p X is any probability distribution that infers p A .
Probabilistic Compositional Rule To put the formalism in the context of music, we first follow the convention [9] to approach a music piece as a sequence of sonorities (a generic term for chord) and view each moment in a composition as determining a sonority that fits the existing music context. If we let Ω be a finite collection of pitches specifying the discrete range of an instrument, e.g. the collection of the 88 keys on a piano, then a k-part sonority-k simultaneously sounding pitches-is a point in Ω k . So X = Ω k is the raw input space containing all possible sonorities. Although discrete and finite, the raw input size is typically large, e.g. |X | = 88 4 considering piano range and 4-part chorales. Therefore, theorists have invented various music parameters such as quality and inversion, to abstract specific sonorities. In this paper, we inherit the approach in [11] to formalize a high-level representation of X by a feature-induced partition A, and call the output of the corresponding abstraction (A, p A ) a probabilistic compositional rule.

Probabilistic Rule System
The interrelation between abstraction and realization (X , p X ) ↔ (A, p A ) can be formalized by a linear equation: Ap = b, where A ∈ {0, 1} m×n represents a partition (A ij = 1 if and only if x j is assigned to the ith cluster in the partition), and p = p X , b = p A are probability distributions of the raw input space and the high-level representation space, respectively. In the sequel, we represent a rule by the pair (A, b), so realizing this rule becomes solving the linear equation Ap = b. More interestingly, given a set of rules: (A (1) , b (1) ), . . . , (A (K) , b (K) ), the realization of all of them involves finding a p such that A (r) p = b (r) , for all r = 1, . . . , K. In this case, we form a probabilistic rule system by stacking all rules into one single linear system: (1) . . .
We call A (r) i a rule component, and m r = dim(b (r) ) the size (# of components) of a rule.

Unified Framework for Rule Realization and Selection
In this section, we detail a unified framework for simultaneous rule realization and selection. Recall rules themselves can be inconsistent, e.g. rules learned from different music contexts can conflict. So given an inconsistent rule system, we can only achieve Ap ≈ b. To best realize the possibly inconsistent rule system, we solve for p ∈ ∆ n by minimizing the error 2 , the sum of the Brier scores from every individual rule. This objective does not differentiate rules (or their components) in the rule system, which typically yields a solution that satisfies all rules approximately and achieves a small error on average. This performance, though optimal in the averaged sense, is somewhat disappointing since most often no rule is satisfied exactly (error-free). Contrarily, a human composer would typically make a clear separation: follow some rules exactly and disregard others even at the cost of a larger realization error. The decision made on rule selection usually manifests the style of a musician and is a higher level intelligence that we aim for. In this pursuit, we introduce a fine-grained set of weights w ∈ ∆ m to distinguish not only individual rules but also their components. The weights are estimates of relative importance, and are further leveraged for rule selection. This yields a weighted error, which is used herein to measure realization quality: If we revisit the two challenges mentioned in Sec. 1, we see that under the current setting, the first challenge concerns the curse of dimensionality for p, while the second concerns the selectivity for w. We introduce two penalty terms, one each for p and w, to tackle the two challenges, and propose the following bi-convex optimization problem as the unified framework: Despite contrasting purposes, both penalty terms, P p (p) and P w (w), adopt the same high-level strategy of exploiting group structures in p and w. Regarding the curse of dimensionality, we exploit the group structure of p by grouping p j and p j together if the jth and j th columns of A are identical, partitioning p's coordinates into K groups: g 1 , . . . , g K where K is the number of distinct columns of A. This grouping strategy uses the fact that in a simplex-constrained linear system, we cannot determine the individual p j s within each group but only their sum. We later show (Sec. 4.1) the resulting group structure of p is essential in dimensionality reduction (when K n ) and has a deeper interpretation regarding abstraction levels. Regarding the rule-level selectivity, we exploit the group structure of w by grouping weights together if they are associated with the same rule, partitioning w's coordinates into K groups: g 1 , . . . , g K where K is the number of given rules. Based on the group structures of p and w, we introduce their corresponding group penalties as follows: One can see the symmetry here: group penalty (4) on p is a squared, unweighted L 2,1 -norm, which is designed to secure a unique solution that favors more randomness in p for the sake of diversity in sonority generation [9]; group penalty (5) on w is a weighted L 1,2 -norm (group lasso), which enables rule selection. However, there is a pitfall of the group lasso penalty when deployed in Problem (3): the problem has multiple global optima that are indefinite about the number of rules to pick (e.g. selecting one rule and ten consistent rules are both optimal). To give more control over the number of selections, we finalize the penalty on w as the group elastic net that blends between a group lasso penalty and a ridge penalty: where α balances the trade-off between rule elimination (less rules) and selection (more rules). (3) is a bi-convex problem: fixing p it is convex in w; fixing w it is convex in p. The symmetry between the two optimization variables further gives us the reciprocal interpretations of the rule realization and selection problem: given p, the music realization, we can analyze its style by computing w; given w, the music style, we can realize it by computing p and further sample from it to obtain music that matches the style. The roles of the hyperparameters λ p and (λ w , α) are quite different. In setting λ p sufficiently small, we secure a unique solution for the rule realization part. However, for the rule selection part, what is more interesting is that adjusting λ w and α allows us to guide the overall composition towards different directions, e.g. conservative (less strictly obeyed rules) versus liberal (more loosely obeyed rules).

Model Properties
We state two properties of the bi-convex problem (3) as the following theorems whose proofs can be found in the supplementary material. Both theorems involve the notion of group selective weight. We say w ∈ ∆ m is group selective if for every rule in the rule set, w either drops it or selects it entirely, i.e. either w gr = 0 or w gr > 0 element-wisely, for any r = 1, . . . , K. For a group selective w, we further define supp g (w) to be the selected rules, i.e.
Thm. 1 implies a useful range of the λ w -solution path: if λ w is too large, w will converge to a known value that always selects all the rules; if λ w is too small, w can lose the guarantee to be group selective. This further suggests the termination criteria used later in the experiments. Thm. 2 considers rule selection in the consistent case, where the solution selects the largest number of rule components among all other consistent rule selections. Despite the condition λ p = 0, in practice, this theorem suggests one way of using model for a small λ p : if the primary interest is to select consistent rules, the model is guaranteed to pick as many rule components as possible (Sec. 5.1). Yet, a more interesting application is to slightly compromise consistency to achieve better selection (Sec. 5.2).

Alternating Solvers for Probability and Weight
It is natural to solve the bi-convex problem (3) by iteratively alternating the update of one optimization variable while fixing the other, yielding two alternating solvers.

The p-Solver: for Rule Realization
If we fix w, the optimization problem (3) boils down to: De-Overlap Making a change of variable: q k = 1 p g k = p g k 1 for k = 1, . . . , K and letting q = (q 1 , . . . , q K ), problem (7) is transformed to its reduced form: subject to q ∈ ∆ K , where A is obtained from A by removing its column duplicates. Problem (8) is a convex problem with a strictly convex objective, so it has a unique solution q . However, the solution to the original problem (7) may not be unique: any p satisfying q k = 1 p g k is a solution to (7). To favor a more random p (as discussed in Sec. 3), we can uniquely determine p by uniformly distributing the probability mass q k within the group g k : Dimensionality Reduction: Group De-Overlap Problem (7) is of dimension n, while its reduced form (8) is of dimension K (≤ n) from which we can attain dimensionality reduction. In cases where K n, we have a huge speed-up for the p-solver; in other cases, there is still no harm to always run the p-solve from the reduced problem (8). Recall that we have achieved this type of dimensionality reduction by exploiting the group structure of p purely from a computational perspective (Sec. 3). However, the resulting group structure has a deeper interpretation regarding abstraction levels, which is closely related to the concept of de-overlapping a family of groups, group de-overlap in short.
(Group De-Overlap) Let G = {G 1 , . . . , G m } be a family of groups (a group is a non-empty set), and We introduce a group assignment function g : G → {0, 1} m , such that for any x ∈ G, g(x) i = 1{x ∈ G i }, and further introduce an equivalence relation ∼ on G: We then define the de-overlap of G, another family of groups, by the quotient space The idea of group de-overlap is simple (Fig. 1), and DeO(G) indeed comprises non-overlapping groups, since it is a partition of G that equals the set of equivalence classes under ∼. Now given a set of rules (A (1) , b (1) ), . . . , (A (K) , b (K) ), we denote their corresponding high-level representation spaces by A (1) , . . . , A (K) , each of which is a partition of the raw input space X (Sec. 2). Let G = ∪ K k=1 A (k) , then DeO(G) is a new partition-hence a new high-level representation space-of G = X , and is finest (may be tied) among all partitions A (1) , . . . , A (K) . Therefore, DeO(G), as a summary of the rule system, delimits a lower bound on the level of abstraction produced by the given set of rules/abstractions. What coincides with DeO(G), is the group structure of p (recall: p j and p j are grouped together if the jth and j th columns of A are identical), since for any x j ∈ X , the jth column of A is precisely the group assignment vector g(x j ). Therefore, the decomposed solve step from q to p reflects the following realization chain: where the intermediate step not only computationally achieves dimensionality reduction, but also conceptually summarizes the given set of abstractions and is further realized in the raw input space.
Note that the σ-algebra of the probability space associated with (8) is precisely generated by DeO(G).
When rules are inserted into a rule system sequentially (e.g. the growing rule set from an automatic music theorist), the successive solve of (8) is conducted along a σ-algebra path that forms a filtration: nested σ-algebras that lead to finer and finer delineations of the raw input space. In a pedagogical setting, the filtration reflects the iterative refinements of music composition from high-level principles that are taught step by step.
Dimensionality Reduction: Screening We propose an additional technique for further dimensionality reduction when solving the reduced problem (8). The idea is to perform screening, which quickly identifies the zero components in q and removes them from the optimization problem. Leveraging DPC screening for non-negative lasso [16], we introduce a screening strategy for solving a general simplex-constrained linear least-squares problem (one can check problem (8) is indeed of this form): We start with the following non-negative lasso problem, which is closely related to problem (11): and denote its solution by β (λ). One can show that if β (λ ) 1 = 1, then β (λ ) is a solution to problem (11). Our screening strategy for problem (11) runs the DPC screening algorithm on the non-negative lasso problem (12), which applies a repeated screening rule (called EDPP) to solve a solution path specified by a λ-sequence: λ max = λ 0 > λ 1 > · · · . The 1 -norms along the solution path are non-decreasing: 0 = β (λ 0 ) 1 ≤ β (λ 1 ) 1 ≤ · · · . We terminate the solution path at λ t if β (λ t ) 1 ≥ 1 and β (λ t−1 ) 1 < 1. Our goal is to use β (λ t ) to predict the zero components in β (λ ), a solution to problem (11). More specifically, we assume that the zero components in β (λ t ) are also zero in β (λ ), hence we can remove those components from β (also the corresponding columns of X) in problem (11) and reduce its dimensionality.
While in practice this assumption is usually true provided that we have a delicate solution path, the monotonicity of β (λ)'s support along the solution path does not hold in general [17]. Nevertheless, the assumption does hold when β (λ t ) 1 → 1, since the solution path is continuous and piecewise linear [18]. Therefore, we carefully design a solution path in the hope of a β (λ t ) whose 1 -norm is close to 1 (e.g. let λ i = γλ i−1 with a large γ ∈ (0, 1), while more sophisticated design is possible such as a bi-section search). To remedy the (rare) situations where β (λ t ) predicts some incorrect zero components in β (λ ), one can always leverage the KKT conditions of problem (11) as a final check to correct those mis-predicted components [19]. Finally, note that the screening strategy may fail when the 1 -norms along the solution path converge to a value less than 1. In these cases we can never find a desired λ t with β (λ t ) 1 ≥ 1. In theory, such failure can be avoided by a modified lasso problem which in practice does not improve efficiency much (see the supplementary material).

The w-Solver: for Rule Selection
If we fix p, the optimization problem (3) boils down to: We solve problem (13) via ADMM [20]: In the w-update (14), we introduce the error vector e = (Ap − b) 2 (element-wise square), and obtain a closed-form solution by a soft-thresholding procedure [21]: for r = 1, . . . , K, In the z-update (15), we introduce the indicator function I ∆ m (z) = 0 if z ∈ ∆ m and ∞ otherwise, and recognize it as a (Euclidean) projection onto the probability simplex: which can be solved efficiently by a non-iterative method [22]. Given that ADMM enjoys a linear convergence rate in general [23] and the problem's dimension m n, one execution of the wsolver is cheaper than that of the p-solver. Indeed, the result from the w-solver can speed up the subsequent execution of the p-solver, since we can leverage the zero components in w to remove the corresponding rows in A, yielding additional savings in the group de-overlap of the p-solver.

Artificial Rule Set
We generate two artificial rule sets: Case A1 and A2, both of which are derived from the same raw input space X = {x 1 , . . . , x n } for n = 600, and comprise K = 5 rules. The rules in Case A1 are of size 80, 50, 60, 60, 60, respectively; the rules in Case A2 are of size 70, 50, 65, 65, 65, respectively. For both cases, rule 1&2 and rule 3&4 are the only two consistent sub rule sets of size ≥ 2. The main difference between the two cases is: in Case A1, rule 1&2 has a combined size of 130 which is larger than rule 3&4 and in Case A2 it is opposite. Under different settings of the hyperparameters λ w and α, our model selects different rule combinations exhibiting unique "personal" styles. Tuning the blending factor α ∈ [0, 1] is relatively easy, since it is bounded and has a nice interpretation. Intuitively, if α → 0, the effect of the group lasso vanishes, yielding a solution w that is not selective; if α → 1, the group elastic net penalty reduces to the group lasso, exposing the pitfall mentioned in Sec. 3. Experiments show that if we fix a small α, the model picks either all five rules or none; if we fix a large α, the group norms associated with each rule are highly unstable as λ w varies. Fortunately in practice, α has a wide middle range (typically between 0.4 and 0.9), within which all corresponding λ w -solution paths look similar and perform stable rule selection. Therefore, for all experiments herein, we fix α = 0.8 and study the behavior of the corresponding λ w -solution path.
We show the λ w -solution paths in Fig. 2. Along the path, we plot the group norms (top, one curve per rule) and the weighted errors (bottom). The former, formulated as w gr (λ w ) 2 , describes the options for rule selection; the latter, formulated as E(p (λ w ), w (λ w ); A, b), describes the quality of rule realization. To produce the trajectories, we start with a moderate λ w (e.g. λ w = 1), and gradually increase and decrease its value to bi-directionally grow the curves. We terminate the descending direction when w (λ w ) is not group selective and terminate the ascending direction when the group norms converge. Both terminations are indicated by Thm. 1, and work well in practice. As λ w grows, the model transitions its compositional behavior from a conservative style (sacrifice a number of rules for accuracy) towards a more liberal one (sacrifice accuracy for more rules). If we further focus on the λ w s that give us zero weighted error, Fig. 2a reveals rule 1&2, and Fig. 2b reveals rule 3&4, i.e. the largest consistent subset of the given rule set in both cases (Thm. 2). Finally, we mention the efficiency of our algorithm. Averaged over several runs on multiple artificial rule sets of the same size, the run-time of our solver is 27.2 ± 5.5 seconds, while that of a generic solver (CVX) is 41.4 ± 3.8 seconds. We attribute the savings to the dimensionality reduction techniques introduced in Sec. 4.1, which will be more significant at large scale.

Real Compositional Rule Set
As a real-world application, we test our unified framework on rule sets from an automatic music theorist [11]. The auto-theorist teaches people to write 4-part chorales by providing personalized   Figure 3: The λ w -solution path obtained from a real compositional rule set.
rules at every stage of composition. In this experiment, we exported a set of 16 compositional rules which aims to guide a student in writing the next sonority that follows well with the existing music content. Each voice in a chorale is drawn from Ω = {R, G 1 , . . . , C 6 } that includes the rest (R) and 54 pitches (G 1 to C 6 ) from human vocal range. The resulting raw input space X = Ω 4 consists of n = 55 4 ≈ 10 7 sonorities, whose distribution lives in a very high dimensional simplex. This curse of dimensionality typically fails most of the generic solvers in obtaining an acceptable solution within a reasonable amount of time.
We show the λ w -solution path associated with this rule set in Fig. 3. Again, the general trend shows the same pattern here: the model turns into a more liberal style (more rules but less accurate) as λ w increases. Along the solution path, we also observe that the consistent range (i.e. the error-free zone) is wider than that in the artificial cases. This is intuitive, since a real rule set should be largely consistent with minor contradictions, otherwise it will confuse the student and lose its pedagogical purpose. A more interesting phenomenon occurs when the model is about to leave the error-free zone. When log 2 (λ w ) goes from 1 to 2, the combined size of the selected rules increases from 2166 to 2312 but the realization error increases only a little. Will sacrificing this tiny error be a smarter decision to make? The difference between the selected rules at these two moments shows that rule 1 and 7 were added into the selection at log 2 (λ w ) = 2 replacing rule 6 and 8. Rule 1 is about the bass line, while rule 6 is about tenor voice. It is known in music theory that outer voices (soprano and bass) are more characteristic and also more identifiable than inner voices (alto and tenor) which typically stay more or less stationary as background voices. So it is understandable that although larger variety in the bass increases the opportunity for inconsistency (in this case not too much), it is a more important rule to keep. Rule 7 is about the interval between soprano and tenor, while rule 8 describes a small feature between the upper two voices but does not have a meaning yet in music theory. So unlike rule 7 that brings up the important concept of voicing (i.e. classifying a sonority into open/closed/neutral position), rule 8 could simply be a miscellaneous artifact. To conclude, in this particular example, we would argue that the rule selection happens at log 2 (λ w ) = 2 is a better decision, in which case the model makes a good compromise on exact consistency.
To compare a selective rule realization with its non-selective counterpart [11], we plot the errors A (r) p − b (r) 2 for each rule r = 1, . . . , 16 as histograms in Fig. 4. The non-selective realization takes all rules into consideration with equal importance, which turns out to be a degenerate case along our model's solution path for log 2 (λ w ) → ∞. This realization yields a "well-balanced" solution but no rules are satisfied exactly. In constrast, a selective realization (e.g. log 2 (λ w ) = 1) gives near-zero errors on selected rules, producing more human-like compositional decisions.

Discussion
Generality of the Framework The formalism of abstraction and realization in Sec. 2, as well as the unified framework for simultaneous rule realization and selection in Sec. 3, is general and domain-agnostic, not specific to music. The problem formulation as a bi-convex problem (3) admits numerous real-world applications that can be cast as (quasi-)linear systems, possibly equipped with some group structure. For instance, many problems in physical science involve estimating unknowns x from their observations y via a linear (or linearized) equation y = Ax [24], where a grouping of y i 's (say, from a single sensor or sensor type) itself summarizes x as a rule/abstraction. In general, the observations are noisy and inconsistent due to errors from the measuring devices or even the failure of a sensor. It is then necessary to assign a different reliability weight to every individual sensor reading, and ask for a "selective" algorithm to "realize" the readings respecting the group structure. So in cases where some devices fail and give inconsistent readings, we can run the proposed algorithm to filter them out.

Linearity versus Expressiveness
The linearity with respect to p in the rule system Ap = b results directly from adopting the probability-space representation. However, this does not imply that the underlying domain (e.g. music) is as simple as linear. In fact, the abstraction process can be highly nonlinear which involves hierarchical partitioning of the input space [11]. So, instead of running the risk of losing expressiveness, the linear equation Ap = b hides the model complexity in the A matrix. On the other hand, the linearity with respect to w in the bi-convex objective (3) is a design choice. We start with a simple linear model to represent relative importance for the sake of interpretability, which may sacrifice the model's expressiveness like other classic linear models. To push the boundary of this trade off in the future, we will pursue more expressive models without compromising (practically important) interpretability.
Differences from (Group) Lasso Component-wise, both subproblems (7) and (13) of the unified framework look similar to regular feature selection settings such as lasso [25] and group lasso [26]. However, not only does the strong coupling between the two subproblems exhibit new properties (Thm. 1 and 2), but also the differences in the formulation present unique algorithmic challenges. First, the weighted error term (2) in the objective is in stark contrast with the regular regression formulation where (group) lasso is paired with least-squares or other similar loss functions. Whereas dropping features in a regression model typically increases training loss (under-fitting), dropping rules, on the contrary, helps drive the error to zero since a smaller rule set is more likely to achieve consensus. Hence, the tendency to drop rules in a regular (group) lasso is against the pursuit of a largest consistent rule set as desired. This stresses the necessity of a more carefully designed penalty like our proposed group elastic net. Second, the additional simplex constraint weakens the grouping property of group lasso: failures in group selection (i.e. there exists a rule that is not entirely selected) are observed for small λ w s. The simplex constraint, effectively an 1 constraint, also incurs an " 1 cancellation", which nullifies a simple lasso (also an 1 ) on a simple parameterization of the rules (one weight per rule). These differences pose new model behaviors and deserve further study.
Local Convergence We solve the bi-convex problem (3) via alternating minimizations in which the algorithm decreases the non-negative objective in every iteration thus assures its convergence. Nevertheless, neither a global optimum nor a convergence in solution can be guaranteed. The former leaves the local convergence susceptible to different initializations, demanding further improvements through techniques such as random start and noisy updates. The latter leaves the possibility for the optimization variables to enter a limit cycle. However, we consider this as an advantage, especially in music where one prefers multiple realizations and interpretations that are equally optimal.
More Microscopic Views The weighting scheme in this paper presents the rule selection problem in a most general setting, where a different weight is assigned to every rule component. Hence, we can study the relative importance not only between rules by the group norms w gr 2 , but also within every single rule. The former compares compositional rules in a macroscopic level, e.g. restricting to a diatonic scale is more important than avoiding parallel octaves; while the latter in a microscopic level, e.g. changing the probability mass within a diatonic scale creates variety in modes: think about C major versus A minor. We can further study the rule system microscopically by sharing weights of the same component but from different rules, yielding an overlapping group elastic net.

Supplementary Material to 1 Proofs of Main Theorems
We copy the bi-convex problem from the main paper: Introduce e = (Ap − b) 2 where (·) 2 is taken element-wise, then the weighted error is written as: e gr w gr .
Recall that w ∈ ∆ m is group selective if for every rule in the rule set, w either drops it or selects it entirely, i.e. either w gr = 0 or w gr > 0 element-wise, for all r = 1, . . . , K.
Recall that for a group selective w, we introduce supp g (w) to be the set of the selected rule indices, i.e. supp g (w) = {r | w gr > 0 element-wise} ⊂ {1, . . . , K}.
We start with a lemma which will be used in the proof of Thm. 1 part (1).
Lemma 1. Fix any p ∈ R n , the bi-convex problem (1) is reduced to a convex problem w.r.t. w: subject to 0 w 1, 1 w = 1.
Let w be a solution to problem (2), then w is group selective if Proof of Lemma 1. (Proof by contradiction) Assume w is not group selective when λ m > α −1 e ∞ , i.e. there exists r ∈ {1, . . . , K} such that w gr 2 = 0, but (w gr ) i = 0, for some i.
Let L(w) be problem (2)'s objective function whose partial derivative ∂L/∂(w g k ) j for any group k such that w g k 2 = 0 is For r, i in particular, we have Within group r, let j = arg max j (w gr ) j . Since mr j=1 (w gr ) 2 j = w gr 2 2 > 0, we must have Take the direction vector δ t ∈ R m such that where t > 0 is sufficiently small such that w + δ t ∈ ∆ m . However, < 0 where inequality (4) holds since (e gr ) j ≥ 0, α ≤ 1, (w g k ) j ≥ 0; inequality (5) holds because of the lower bound (3); inequality (6) holds because of the condition λ w > α −1 e ∞ . The negative inner product in the above implies that δ t is a descent direction, which gives L(w + δ t ) < L(w ). This contradicts the fact that w is a minimizer, therefore, nullifies the assumption that w is not group selective and completes the proof. Theorem 1. Fix any λ p > 0, α ∈ [0, 1]. Let (p (λ w ), w (λ w )) be a solution path to problem (1).
Notice that the solution w to problem (7) must have uniform mass within each group, i.e.
(8) As a consequence, the group lasso penalty is always constant: Under the uniformity condition (8), the ridge penalty by the Cauchy-Schwarz inequality. The equality holds when That is w gr 1 = γm r . Then r w gr 1 = 1 gives γ = 1/m, which further yields This completes the proof and further shows that w is actually the uniform distribution on ∆ m , since applying the uniformity condition (8) to w gr 1 = γm r = m r /m gives w i = 1/m for all i.
Proof of Theorem 2. When λ p = 0, problem (1) becomes subject to 0 p 1, 1 p = 1, Under the error-free condition, it is clear that (p , w ) is also the solution to the following problem subject to supp g (w) ∈ C E(p, w; A, b) = 0 0 p 1, 1 p = 1.
which can be further rewritten as the following problem by the definition of C: subject to supp g (w) ∈ C 0 w 1, 1 w = 1.
The above problem is further equivalent to the following problem subject to supp g (w) = C, C ∈ C, Consider a class of problems {Q(C) | C ∈ C} such that each problem Q(C) is formulated as subject to supp g (w) = C 0 w 1, 1 w = 1.
The solution w to problem (12) is then the solution to problem (13) with the minimum objective among all the problems from {Q(C) | C ∈ C}, and further the corresponding p is probability distribution that gives E(p , w ; A, b) = 0.
Given any C ∈ C, let (p ,C , w ,C ) be the solution to the corresponding problem (13). This problem is a reduced problem (7) introduced in the proof of Thm. 1. The only difference is that here we constrain the nonzero groups to be C. Same argument for problem (7) gives w ,C gr = 1 r∈C m r 1 mr , for any r ∈ C.
Thus, the optimal objective of Q(C) for a given C is Finally, as w is the w ,C that achieves the minimum Q(C) objective among all C ∈ C, we have r∈suppg(w ) m r = max r∈C m r | C ∈ C .

Theoretical Justification for Screening
The screening procedure is needed when we solve for p after fixing w. In this section, we give detailed justifications about the procedure in its general form: a simplex constrained least-squares: subject to 0 p 1, 1 p = 1, We start from the observation that the solution p to the problem is expected to be sparse in most situations. To see this, we first introduce an relaxation problem for later discussions. Note that we can relax (14) to the following L 1 -constrained problem: subject to p 0 which is further is equivalent to the following problem: subject to p 0 for some positive (unknown) ρ = ρ .
Denote the solution of (16) with ρ to bep(ρ). We have the following result: Proposition 1. Any solution of (16) satisfying is a solution of (14).
Proof of Proposition 1. See the proof of Proposition 2.
It is well known that the lasso problem tends to encourage a sparse solution, so we may expect a sparse solution for p in (14). In practice, we observe that the solution of (14) is indeed very sparse in most experiments. This motivates us to screen out the positions of p that must be zeros according to the nonnegative lasso solution before solving the least square problem. Since negative lasso screening and solving can be done efficiently [1] in many situations, such strategy can sometimes reduce the problem scale dramatically.
The difference between (16) and (14) comes from the fact that we are relaxing the equality of L 1 norm p 1 = 1 by the inequality p 1 ≤ 1. Actually, in general they are not guaranteed to be equivalent. There are situations where the lasso solution path can never touch the L 1 unit ball and in such circumstances, the lasso solution cannot be used. However, we can make a small modification on (16) to achieve an exact equivalence between the simplex constrained least square problem and a nonnegative lasso problem. Specifically, we attach a row, c1 T to A and 2c to b, and denote the resulting matrices byÃ andb, where c is some constant that will be given soon.The modified nonnegative lasso problem is subject to p 0 The following proposition shows that the (18) is equivalent to (14). Proposition 2. Let T = min j A ·j 2 . If c 2 > 4T 2 + m, then 1. There exists a ρ, such that the solution of problem (18),p(ρ), satisfies (17).
Proof of Proposition 2. We first check the least square problem subject to p 0 For any p such that p 1 < 1, the last term in the squared error: (c1 T p − 2c) 2 > c 2 .