Information Lattice Learning
Authors: Haizi Yu
James Evans
Lav R. Varshney
Venue:  (2021)

Abstract: Information Lattice Learning (ILL) is a general framework to learn decomposed representations, called rules, of a signal such as an image or a probability distribution. Each rule is a coarsened signal used to gain some human-interpretable insight into what might govern the nature of the original signal. To summarize the signal, we need several disentangled rules arranged in a hierarchy, formalized by a lattice structure. ILL focuses on explainability and generalizability from "small data", and aims for rules akin to those humans distill from experience (rather than a representation optimized for a specific task like classification). This paper focuses on a mathematical and algorithmic presentation of ILL, then demonstrates how ILL addresses the core question "what makes X an X" or "what makes X different from Y" to create effective, rule-based explanations designed to help human learners understand. The key part here is \emph{what} rather than tasks like generating X or predicting labels X,Y. Typical applications of ILL are presented for artistic and scientific knowledge discovery. These use ILL to learn music theory from scores and chemical laws from molecule data, revealing relationships between domains. We include initial benchmarks and assessments for ILL to demonstrate efficacy.

Under review as a conference paper at ICLR 2021
INFORMATION LATTICE LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Information Lattice Learning (ILL) is a general framework to learn decomposed representations, called rules, of signal such as an image probability distri- bution. Each rule is a coarsened signal used to gain some human-interpretable insight into what might govern the nature of the original signal. To summarize the signal, we need several disentangled rules arranged in a hierarchy, formalized by a lattice structure. ILL focuses explainability and generalizability from "small data", and aims for rules akin to those humans distill from experience (rather than a representation optimized for a specific task like classification). This paper focuses on a mathematical and algorithmic presentation of ILL, then demonstrates how ILL addresses the core question "what makes X X" or "what makes X differ- ent from Y" to create effective, rule-based explanations designed to help human learners understand. The key part here what rather than tasks like generating X predicting labels X.Y. Typical applications of ILL are presented for artistic and scientific knowledge discovery. These use ILL to learn music theory from scores and chemical laws from molecule data, revealing relationships between domains. We include initial benchmarks and assessments for ILL to demonstrate efficacy.
INTRODUCTION
With rapid progress in AI, there is an increasing desire for general Al (Goertzel & Pennachin 2007 Chollet. 2019) and explainable AI (Adadi & Berrada 2018 Molnar 2019). which exhibit broad. human-like like cognitive capacities. One common pursuit is to move away from "black boxes" designed for specific tasks to achieve broad generalization through strong abstractions made from only a few examples, with neither unlimited priors nor unlimited data ("primitive priors" & "small data" instead). wormeewor--Iffrmmae
In this pursuit, we present a new, task-nonspecific to learn representations akin to human -iittlllde rules, c.g., producing much of standard music theory curriculum as well as new rules in a form directly interpretable by students (shown at the end).
Lattice Learning (II..)-
The term information lattice was first defined by SShanno (1953), but remains largely conceptual and unexplored. In the context of abstraction and representation learning, we independently develop representation lattices that coincide with Shannon's 's information lattice when restricted to his context. Instead of inventing a new name, we adopt Shannon's. However, we not only generalize the original definition-an information lattice here is hierarchical distribution of representations- we also bring learning into the lattice, yielding the name ILL.
ILL explains a signal (e.g., a probability distribution) by disentangled representations, called rales. A rule explains some but not all aspects of the signal, but together the collection of rules aims to capture a large part of the signal. ILL is specially designed to address the core question "what makes X an X" or "what makes X different from Y", emphasizing the what rather than generating X or predicting labels X, Y in order to facilitate effective, rule-based explanations designed to help human learners understand. A music AI classifying concertos, or generating one that mimics the masters, does not necessarily produce human insight about what makes a concerto concerto or the hest rules novice composer might employ to write one. Our focus represents shift from much representation--eanmee learnnin work (Bengio et al. 20133) that aim to find the best representation for solving a specific task (c.g., classification) rather than strong concern for explainability. Instead of optimizing task-specific objective function (e.g., classification error), ILL balances more general objectives that favor fewer, simpler rules for interpretability, and more essential rules for effectiveness all formalized later.
One intuition behind ILL is to break the whole into simple pieces, similar to breaking a signal into Fourier series. Yet, rather than decomposition via projection to orthonormal basis and synthesis

---

Under review as a conference paper at ICLR 2021
SIGNAL
PROBABILITY
Jerry
SYNTHESIZE (LIFT)
FREQ. COUNT
INFORMATION LATTICE
RULES
Tom
FINEST
JERRY PLAYS HIGHER KEYS
TOM PLAYS
RULE
COARSEST
CHEMISTRY RULES
Figure 1: ILL's main idea: decompose the signal into rules that individually simple but collectively expressive. lattice is first constructed regardless of the signal (prior-driven), yet the same lattice may be later used to learn rules (data-driven) of signals from different topics, e.g., music and chemistry.
via weighted sum, we decompose signal in hierarchical space called a lattice. Another intuition behind ILL is feature selection. Yet, rather than features, we use partitions to mimic human concepts and enable structured search in partition lattice to mimic human learning. The goal is to restore human-like, hicrarchical rule abstraction-aat -nd--calizzation through signal decomposition-ang and-synthesis in lattice (called projection-ante aad-onn--nn--iiiinngggg Figure left), resulting more than
of parts.
ILL comprises two phases: (a) lattice construction; (b) learning (i.c., searching) in the lattice. This is similar to many machine learning (ML) models comprising (a) function class specification then optimal parameters via crock--rppggaton--- in the network. ILL's construction phase is prior-efficient: it builds in universal priors that resemble human innate cognition (ef. the Core Knowledge priors (Spelke & Kinzler 2007)), then grows lattice of abstractions. The priors can be customized, however, to cater to particular human learner, or facilitate more exotic knowledge discovery. ILL's learning phase is data-efficient: learns from "small data" encoded by a signal, but searches for rich explanations of the signal via rule learning, wherein abstraction is key to "making small data large". Notably, the construction phase is prior-driven, not data-driven data comes in only at the learning phase. Hence, the same construction may be reused in different learning phases for different data sets or even data on different topics (Figure [ right). Featuring these two phases, ILL is thus a hybrid model that threads the needle between a full data-driven model and full prior-driven model, echoing the notion of "starting like a baby; learning like a child" (Hutson 2018).
(b) learning in the function class, e.g., constructing a neural network then learning-
ILL is related to many research areas. It draws ideas and approaches from lattice theory, information theory, group theory, and optimization. shares algorithmic similarity with a range of techniques including MaxEnt, data compression, autoencoders, and compressed sensing, but with much greater focus on achieving human-like explainability and generalizability. Below, we broadly compares ILL prominent, related models, leaving more comparisons to the Appendix for most similar ones.
Compared deep learning
ILL
a "white-box" model balancing human-explainabilit and task performance
Bayesian inference
modeling human reasoning with widely shared, common priors and few, simple rules rather than using probabilistic inference as driving force
tree-like models
structurally more general: a tree (e.g., decision tree or hierarchical clustering) is essentially a lincar lattice (called chain formally) depicting unidirectional refinement or coarsening process
concept lattice in FCA (Ganter & Wille 2012)
conceptually more general and may include both known and unknown concepts; ILL does not require but discovers domain knowledge (more details in Appendix
We illustrate ILL applications by learning music theory from scores, chemical laws from compounds, and show how ILL's common priors facilitate mutual interpretation between the two subjects. To begin, imagine Tom and Jerry are playing two 12-key pianos simultaneously, one note at time (Figure T right). The frequency of the played two-note chords gives a 2D signal plotted as 12 x 12 grayscale heatmap. Inspecting this heatmap, what might be the underlying rules that govern their co-play? (Check: all grey pixels have a larger "Jerry- coordinate" "Toomaxis") We elaborate ILI. and use it to distill rules for complex, realistic cases.
"eery-coordinate" and project to a black key along the
2

---

Under review as a conference paper at ICLR 2021
SIGNAL
PARTITION LATTICE
INFORMATION LATTICE
2D EXAMPLE
X 2 -
SIGNAL
LIFTING
SIGNAL
12
123
U2I
123
PARTITION
P (123
PROJECT
23
21
3 12
LIFT
23
31
3
RULE
P
2
RULE
2
PROJECTION
Figure 2: Basic information-lattice terms: signal, partition, rule, lattice, projection and lifting.
2 INFORMATION LATTICE: ABSTRACTIONS AND RULES OF A SIGNAL
Signal. A signal function { + For notational brevity and computational reasons, assume & is non-negative and X S I" is finite (not limitation: Appendix B). For example, a signal { {l.....6) + R being a probability mass function (pmf) of a dice roll, or a signal E: (0, ... 27}² R being 28 28 grayscale image. We denote the set of all signals on X by Sx.
Partition / abstraction. We use a partition P of set X to denote an abstraction of X; we call cell C'E an (abstracted) concept. The intuition is simple: a partition of a set renders a croarse-grained view" of the set, or more precisely, an equivalence relation on the set. In this view, we identify equivalence classes of elements (concepts) instead of individual elements. For example, the partition P = (11,3, (2, 4, }}} of the six outcomes of the roll of a die identify two concepts (odd, even).
Rule / representation. A rule of a signal& & X R is a "coarsened" signal rgg P + IR defined on a partition P of X with (C)) := Exec {(x) for any C' E P. In this paper, rule of signal what we mean by a representation of signal. If the signal is grayscale image, rule can be a special type of blurring or downsampling
the image; if the signal a probability distribution, rule can be a pmf of the "orbits" of the distribution for lifted inference algorithms (Holtzen et al. [219)] Kersting (0122). More generally, we define a rule (regardless of any signal) over a set X by any signal on any partition of X; accordingly, we denote the set of all rules over X by Rx- == e partitions of S)Sp.
Partition lattice. Abstractions are hicrarchical: one coarse-grained view can be coarser than another. Let the partition lattice (7xx 3) of X be the partially ordered set (poset) containing all partitions of X equipped with the partial order coarser than (=), or finer than (2), defined in the standard way. Let : {{x] x E ) and p := {X} denote the finest and the coarsest partition, respectively. Per general lattice theory (Davey & Priestley (2022). Dx is a complete lattice: every subset 3 C Xx has a unique supremum VO and unique infimum A33, where V is called the join of P denoting its coarsest common refinement and A&B is called the meel of Q denoting its finest common coarsening.
Information lattice. The information lattice (Rç, of signal E: X + R is the poset of all rules of & equipped with the partial order more general than: for any two rules r,r' E Rg, we say is more general than r' (or r' is more specific), denoted + r', if domain(r) < domain(r"). Notably, R. S Rxx and Re is isomorphic to the underlying partition lattice via projection defined below.
Projection and lifting. For any signal & E Sx we define the projection operator L5: Px + Rg by letting LE (P) be the rule of & on P. One can check that 1s: (xx, 3) + (Rg, is an isomorphism. Conversely, we define the general lifting operator x>x ; Rx + 2Sx by letting 1 (r) denote the set of all signals that satisfy the rule r, i.e., 1x (r)= == LE E Sx J (domain(r) = r C Sx. To make lifting unique and per Principles of Indifference (Eval 2019,, we introduce a special lifting xx (r) to pick the most "uniform" signal in 1x (r). Formally, define || ll. Sx + R by llEll (Ezex {(x:)9)1/0_ For any E E Sx satisfying ||El|a = I|C'|),, we say that is more uniform than E' (or E is more deterministic) if ||E||2 < ||'/|22 We define the (special) lifting operator 1x: Rx + Sx by 1x (r) == argmin x ||5||2 (can be computed by simply averaging). Notation here follows the convention as to function projections to quotient spaces (Kondor & Trivedi 2018). Lifting single rule to the signal domain can be extended in two ways: (a) lift to a finer rule domain P instead of X, i.e., 1t (r) or 7P (r): (b) lift more than one rules. Accordingly, we write 1 == 1 and {1$ (P) P E 2 C Rg to denote rule set, and write 1 (R) : nVER (r) = {1 E Sx (P) = R. and 1 (R) == argmin (R) |
t: Xx defaults, write R = - (
I to denote signals that satisfy all rules in R (general lifting) and the most uniform one (special lifting), respectively.
More computational details on lifting and its intimate relation to join are in Appendix C
3

---

Under review as a conference paper at ICLR 2021
3 INFORMATION LATTICE LEARNING (ILL)
We first formalize ILL as a single optimization problem and then solve it practically in two phases. Let ç X + R be signal we want to explain. By explaining, we mean to search for a rule set R = 18 (T) C Re such that: (a) R recovers & well, or R is essential; (b) R simple. The main idea agrees with Algorithm Information Theory (Chaitin 1987: Chater & Vitányi 2003), but use an information-ann lanttati based formulation focusing on explamaailityy. We start our formulation below.
We say rule set R recovers the signal exactly if 1 (R) ξ. Yet, exact recovery may not always be achieved. The information loss occurs for two reasons: (a) insufficient abstractions, i.c., the join v& is strictly coarser than P; (b) the choice made in favor of uniformity is inappropriate. Instead of pursuing exact recovery, we introduce A(t (R),,) () distance (e.g., lp distance) or a divergence (e.g., KL divergence) function
measure the loss, with smaller A indicating more essential R.
We say a rule set R is simpler if it contains fewer and simpler rules. Formally, we want R minimal, i.e., each rule r R is indispensable so as to achieve the same t (R). Also, we want each rule r R informationally simple, measured by smaller Shannon entropy Ent(r), so is more deterministic (Falk & Konold 1997), easier remember (Pape al. 2015) and closer to our common-sense definition of "rule", Notably, the partial order renders a tradeoff between the two criteria: r & r' implies is dispensable any 2 (r, r') but on the other hand Ent(r) - Ent(r'), so including more-specific rules makes the rule set small yet each individual rule (informationally) hard.
The main problem. The formal definition of an ILL problem is: given a signal { X R,
minimize (R) R_Re
subject to R is minimal; Ent(r) S for any R.
(1)
The search space involves the full information lattice (Rg, =), or isomorphically. the full partition lattice (Fx: 3). Yet, the size of this lattice, i.e., the Bell number B|x scales faster than exponentially in X|. It is unrealistic to compute all partitions of X (unless X is tiny). let alone the partial order. Besides computational concerns, there are two reasons to avoid the full lattice (but to leave it implicitly in the background): (a) the full lattice has unnecessarily high resolution, comprising many nearly- identical partitions particularly when X is large; (b) considering explainability, not every partition has an rasy-to-interpee criterion by which the abstraction is made. As such, Formulation (I is only conceptual and impractical. Next, we relax it and make it practical via two ILL phases.
3.1 PRACTICAL LATTICE CONSTRUCTION: TO START LIKE A BABY (PHASE I)
Information lattice construction plays a role similar to building a function class in ML, sometimes called meta-learning. While its importance is commonly understood, the construction phase many data-driven models is often treated cursorily-using basic templates and/or ad-hoc priors-leavine most of the computation to the learning phase. In contrast, we put substantial effort into our prior- driven construction phase. Pursuing generality and interpretability, that are -agnosic and close to the innate cognition of human baby (Marcus 2018). Here draw those from Core Knowledge (Spelke & Kinzler 2007 Chollet 2019), which include "the (small) natural numbers and elementary arithmetic prior" and "the elementary geometry and topology prior". We then give algorithms construct abstractions from these priors, and consider such construction prior-efficient if it is interpretable, expressive, and systematic. In the following flowchart, we summarize information lattice construction as generating a partition sublattice.
want universal, simple priors
PRIOR-DRIVEN STAGE
HIERARCHY STAGE
COMPLETION STAGE
SEEDS (PRIORS)
FEATURES/ SYMMETRIES
PARTITION MULTISET
PARTITION POSET
PARTITION SEMILATTICE
PARTITION SUBLATTICE
F,S
G(S)
(F,s Pagry U Patt
(B
(PFss))
(F.))))
1 2 Feature/ Symmetry--nnduced partitions. Unlike data clustering, our prior-driven partitions are induced from two data-independent sources-features and symmetries. We draw priors-in the form of seed features F and seed transformations S-from Core Knowledge as a basis, and then generate a set of partitions ((F.s) as follows: as an example, for X R?:
F- { W[z] Wp.2] sort, argsort, sum, diff, dive, ... divig, modg....,mod!!)
(2)
S = /horizontal, vertical, diagonal translations) U {rotations} U (reroonsssSrrreeeeftttffeeee (reftections)
(3)
4

---

Under review as a conference paper at ICLR 2021
((F): : set of features
generated by
via function composition
G(S): : set of subgroups
generated by subsets of S
via subgroup generation
Pa(F): : set of partitions
generated by features in ((F)
via preimages
Po(s)= set of partitions
generated by subgroups in G(S)
via orbits
In (2) wy denotes coordinate selection (like indexing/Slicing in python) and the other functions defined as in python (div and mod are like in python di divmod). Then, (rr,)) = Poiry U PS(s)-
3 Partition poset. We next sort D (F,s), computationally a multiset, into the poset (2 (s..),)) We import algorithmic skeleton from generie poset-sorting algorithms (Caspard al. 2012 Daskalakis et al. 2011) with an outer routine incrementally adding elements and querying an inner subroutine (an oracle) for pairwise comparison. Yet, our poset is special: its elements are called tagged partitions where a tag records the generating source(s) of its tagged partition, e.g., features and/or symmetries. So. we have specially designed both the outer routine DAD_PAATIOOON and the oracle COMPARE by leveraging (a) transitivity (valid for all posets), (b) partition size (valid for partitions), and (c) partition tag (valid for tagged partitions) to pre-determine or filter relations. We relegate details to Appendix E The data structures for posets include po matrix and hasse diagram, encoding the partial order (ancestoss/descendant)) and the cover relation <e (parents/childree)) respectively (Garg 2015).
4 (5) Partition semi/sublattice. To complete (F,r,,), 3) into a lattice, we compute the sublattice (ff xx) generated by ((F.s). We follow the idea of alternating-joit join--oo--nnnee and-meet completions borrowed from one of the two generic sublattice-compltton methods (Bertet & Morvan 1999). A discussion on our choice and other related methods is in Appendix [ However, we implement join-semilattice completion semilltemil is dual) in special context of tagged partitions, which echoes what we did in 3 and reuses ADD PARTITION. The adjustments are (a) changing tags from features and symmetries to join formulae and (b) changing the inner subroutine from pairwise comparison to computing join. We then run a sequence of alternating joins and meets to complete the lattice. For interpretability, one may want to stop early in the completion sequence. While a single join or meet remains simple for human interpretation-offee (e.g., the join of colored items and sized items gives items indexed by color and size)-having alternating joins and meets may hinder comprehension. More details on single-step soinleemllattic-- completion, the completion sequence, and tips on early stopping are relegated Appendix E
understood as the intersection or union of concepts
3.2 PRACTICAL. LATTICE LEARNING: TO LEARN LIKE CHILD (PHASE II)
Learning in an information lattice means solving the optimization Problem [ i.e., to search for minimal subset of simple rules from the information lattice of signal
to best explain that signal. Let P. be the sublattice (or semilattice, poset, if early stopped) from the construction phase. Projecting signal E X + RR to B. yields the information sublattice R. := $ (7.) S Rg. It is worth reiterating that (a) P. is constructed first and is data-independent; (b) & (data) comes after P.: (c) (R., +) isomorphic to (P., =): R. retains the partial order (po po.taii and hasse hasse_diagrs diagram) and interpretability from P.. As such, R. is what is given at the beginning of the learning phase.
The main problem (relaxed). For practicality, we relax Problem I instead of the full lattice Rg we restrict the search space to RR; instead of minimal rule sets, we consider only antichains (whose elements are mutually incomparable), necessary for minimality. This yields:
minimize (()(R) RCR.
subject R is an antichain; Ent(r) I c for any r E R.
(4)
To solve Problem 4
we adopt a (greedy) idea similar to principal component analysis (PCA): first search for the most essential rule-which decreases A most-in explaining the signal, then the second most essential rule in explaining the rest of the signal, and so on. Specifically, we start with an empty rule set (0) = 0. and add rules iteratively. Let (k()) be the rule set formed by Iteration (Iter) A and (k) fr E R. + r' for some r' E R(k) Let Ree := (r E R. Ent(r) S e). Then,
(A) (in Iter k + 1) minimize (R((() U (r)),E) subject to T E Reasibee = Rs. R(() (5)
We pre-compute R.ce (instead of the whole R.,) before iterations, which can be done by breadth-firs search (BFS) on T... 's hasse hasse_diagras .diagram, from bottom (the coarsest) up. As to the monotonicity of Ent w.r.t. the partial order (cf. the grouping axiom of entropy (Cover & Thomas 2012)), any BFS branch ends once the entropy exceeds e. (For later use, we save the set Ry. of ending rules in BFS, i.e., the lower frontier of R>c.) In contrast, Rk)) is computed per iteration (by querying S. po matrix).
5

---

Under review as a conference paper at ICLR 2021
A.
20
C.
0
GAP ( ( 2K SIGNAL DOMAIN
BFS FRONTIERS
RULE SET (R
PROJECTS
GAP (A) IN RULE DOMAIN
19
1K
ALL EDGES DOWN
ITER
B. ITER:
THE FULL LEARNING (SEARCH) PATH
D. 2-LINE SHORTHAND
0
K
Figure III. toy example: (A.) shows the Hasse diagram of an information lattice R. demarcated by six levels of e-frontiers. (B.) outlines the full search process along the e-solution path, where the red highlights the activated rules and the blue background shows the marching of the BFS frontier. (C.) shows ILL output-called rule trace-whert the up and down arrows show the alternating min-max (lift=project) optimization and each star marks the best rule set under an e, i.e., a solution to the main relaxed Problem (4). (D.) shows shorthand of
a two-line notation where the kth signal along the signal trace (top line) is recovered by lifting up the first rules along the rule trace (bottom line) then the (A- 1)th rule is extracted by projecting down the kth signal to the lattice.
Nested vs. alternating optimization. Computing 1 (RR()) (8) U (r)) requires solving minimization, so l1vlll, E). One may de-nest the two: instead of comparing rules by lifting them up to the signal domain, we compare them "downstairs" on their own rule domains. So, instead of minimizing 5 objective, we
Problem (5) is a nested optimization: argmin, (kR(k) (argmiin
Jegstble
maximize E 2
A ((L)((())) (domain(r)), (domain(r)) (
(R()) (domain(r))
(6)
The idea is to find the rule domain which the recovered 1 (R()) and the target signal exhibit the largest gap. Adding this rule to the rule set maximally closes the gap in (6). and tends to minimize the
original objective in 5 Nicely, in (6) the lifting does not involve r, so (5) is de-nested, which further
iterates into an alternating min-max (or lift=project) optimization. Let r. (k) be the solution and (a))
be the optimal value in Iter k. We update 14+1) (k) U (r 1 (r- (k++1),, 's descendants]
(so always an antichain), and proceed to the next iteration. Iterations end whenever the feasible set is empty, or may end early if the rule becomes less essential, measured by |A (R+1)
A
(k) in the
nested setting, and A (A) S y the alternating setting (for some 7).
The full learning path & complexity. We denote a solve process for Problem (6) by SOLVE(C, 7),
or SOLVE(e) if y is fixed ahead. To avoid tuning e manually, we solve an e-path. Tor éi < assume SOLVE(e:) takes K; iterations, we run the following to solve the main relaxed Problem (6
= R (0) + SOLVE(G) - (K) + SOLVE((2) + (K)
So, lattice learning boils down solving sequence of combinatorial optimizations on the Hasse diagram of a lattice. We walk through the full process ( via a toy example, starting with a signal { (0, ........ 27 + j0, denoting image of "7"" and toy-sized information lattice of the signal (Figure 3T. . The sequence of optimizations (7) proceeds at two paces concurrently: the slower pace indexed by ex; the faster pace is indexed by iteration number k. As mentioned earlier, the sets Res,,

---

Under review as a conference paper at ICLR 2021
pre-computed at the slower pace, with the (i 1)th BFS initialized from R>,, (the ending rules in the ith BFS). The monotonicity of Ent w.r.t. the partial order assures that these BFSs add up to a single (global) BFS on the entire Hasse diagram, climbing up the lattice from the bottom. This is shown in Figure 3 as the monotonic expansion of the blue region (R-se) explored by BFS. Locally at each iteration along the slower pace, solving Problem (6) is quadratic in the worst case when the feasible set is an antichain (i.c., no order), and linear in the best case when the feasible set is a chain (i.e., totally ordered). Since local BFSs add up single BFS with a standard linear complexity, the entire learning phase has a total complexity between linear and quadratic in the number of vertices and edges in the whole Hasse diagram. In general, the denser the diagram is, the lower the complexity is. This is because R.( tends to be large in this case with more descendants activated (i.e., red in Figure BB) which in turn effectively shrinks the feasible set (i.e.. the blue region minus red). For example, unlike the first three iterations in Figure the 4th iteration (e 3) activates more than one rules, including the one being extracted as well as all its unexplored descendants. Further, the upper bound rarely reached. Unlike in this toy example, BFS in practice often early stopped when c becomes large, i.e., when later rules become more random. Hence, targeting at more deterministic and disentangled rules only, not all vertices and edges are traversed by BFS. In the end of the learning process, for explanatory purposes, we store the entire e-path and the (R (4)) )=20 sequence instead of just the very last one. This yields rule trace as the standard ILI. output, which we present below.
How to read ILL output. ILLL outputs rule trace comprising an evolving sequence of rules, rule sets, and recovered signals (FigureBCC. The three sequences are indexed by iteration and by c-path, so the rule set by the last iteration under any (starred) is the returned solution to the main Problem (4). We depict rule by its lifting, since it sketches both the partition and the rule values. Figure 3 gives a full presentation of rule trace. We also introduce a two-line shorthand (Figure BP), keeping only the sequence of the recovered signals and that of the rules. A rule trace answers what makes & an &. or what are the best e-simple rules explaining& Ç. II.I. rules are more interpretable than just eyeballing patterns. (a) The interpretability of the trace is manifest in its controllability via 6, 7: smaller for simpler rules and larger y for more essential rules. (b) The interpretabllity of each rule is gained from its partition tag-the criteria by which the abstraction is made. A tag may contain several generating sources as different interpretations of the same rule abstraction. Like different proofs of a thcorem, a partition tag with multiple sources reveals equivalent characterizations of structure and thus, more insights of the signal. So, tags are not only computationally beneficial in constructing lattices, but also key to interpretation. We present in-depth analyses on tags in the applications below.
4 ILL EXAMPLES
We show typical ILL examples on knowledge discovery in art and science: learning music theory from scores and chemical laws from compounds (while relegating more analyses on handwritten digits to Appendix P.. For both, we fix the same priors-F, S in 3 the same lattice. We fix the same parameters: <-path is 0.2 < 3.2 < 6.2 < ... (tip: a small offset at the beginning, e.g., 0.2, is used to get -eerry-deterministiic rules) and ry is 20% of the initial signal gap. This fixed setting is used to show generality and for comparison. Yet, the parameters can be fine tuned in practice.
Signals are probability distributions of chords encoded as vectors of MIDI keys. Figure shows such a signal-the frequency distribution of two-note chords extracted from the soprano and bass parts of Bach's 's C-score chorales (Illiac Software, Inc., 2020) wiit the learned rule trace listed below. The first rule is tagged by argsort o W/1,2] and has probability all concentrated in one cell whose elements have a larger y-coordinate (the black region above the diagonal). So, this is a deterministic rule, echoing the law of "no voice crossing (N. (.C.)..." . i.e., soprano higher than bass. Checking later rule tags finds laws of voice range (V.R.), diatonic scale (D.S.), and consonant interval (C.I.) almost all of the main static rules on two-voice counterpoint. Notably, the third rule is tagged by both mod12 o W[i and vertical translation invariance. From both feature and symmetry views, this tag identifies the concept of all Cs, all Ds, etc., which is the music concept of pitch class. The feature view explicitly reveals a period of 12 in pitches- the notion of an octave (in defining pitch class); the symmetry view reveals the topology the manifold where the concepts lie in this case 2D torus.
Music illustration.
Chemistry illustration. Signals are boolean-valuse functions indicating the presence of compound formulae encoded as vectors of atomic numbers in molecule database. Figure 4p) shows a signal attained by collecting two-element compounds from the Materials Project database (Jain et al. 2013) of common compounds. The first rule tagged by divis o W[g is deterministic: Flement 2 can never be
7

---

Under review as a conference paper at ICLR 2021
SOPRANO
ELEMENT
D4
NaCl
Ma
No
No
48
Be
36
G2
He
Me
Mg
5. Ar K Ca
36
48
60
72
BASS
"ANION SCALE"
ELEMENT
vI((H)
SIGNAL
01234567
A V A
AAVAVAVA
DIATONIC SCALE
RULE
F
N.V.C. V.R.
D.S.
C.I.
D.S.
0123 012345678
Figure Music and chemical signals (top) with their rule traces learned from ILL (bottom).
Ar, K. Ca. nicely captures the visual pattern in Figure 4p) (the last three vacant columns) and hints suggestively at some chemistry rules. The second rule tagged by mods W(2] has peaks at cells tagged by feature values 1, 7, 0, 6. These cells, for Element 2, are halogens (+H), pnictogens, chalcogens, crystallogens. The third rule shows alkali metals, alkaline earth metals, crystallogens, icosagens the cells common for Element 1. Next rule shows the common combinations, e.g., alkali metals and halogens. Note that the 2nd, 3rd, 4th rules for chemistry and the 5th, 3rd, 4th rules for music share the same tags, except that mod12 becomes modg modg-period changes from 12 (a music octave) to 8 (number of main groups). So, when two chemical elements form a compound, they are like two music notes forming chord! The music concepts of pitch classes and intervals parallel the chemical concepts of groups and their distances. Although abstractions are shared, rules differ. Instead in Bach's is chorales, chemistry uses "cation scale" and an "anion scale". It is interesting that our intention to show ILL's generality (same lattice, parameters for different subjects) also suggests links between art and science by interpreting phenomena (signals) in one subject from the perspective of the other (Bodurow 2018 Applications that extend the experiment here beyond clustering model to restore the periodic table (Zhou al. 2018)) and render complex molecules in high dimensions ongoing, aiming to discover new laws, new interpretations of existing laws, and new materials.
diatonic scale
Real-world deployment & evaluation. We generalized the music illustration real app of an automatic music theorist (Yu et 2016 Yu & Varshney 2017). specially implements the alternat- ing min-max setting into "student=teacher"" model: the student a (music) generator and the teacher is a discriminator. The two form a loop where the teacher guides the student towards a target style through iterative feedback (extracting rules) and exercise (applying rules). This app extends the above music illustration considerably. It considers more music voices, so now signals are in higher dimensions and rules are on more complex chord structure. It considers temporal structure, so now signals include many (un (un)conditional chord distributions mmulti-n-grams)) yielding both context-free and context-dependent rules, new challenges too, namely rare contexts and contrudictory rules. ILL's core idea of abstraction makes "small data large" thus, rare contexts common (Yu & Varshney 2017), and a redesigned lifting operator solves contradiction (Yu et al. 2017). Further, parameters like c, y made into selff-xplanntorr knobs for users to personalize their learning pace.
We conducted two studies to assess rule- ule-learning capability and interpretability. We present the main results here and detail the procedures in Appendix G In the first study, compared ILL-discovered rules with human-com codified domain knowledge to see how much known can be reproduced and how much new be discovered. Trained just 370 Bach's chorales, model reproduced in explicit
8

---

Under review as a conference paper at ICLR 2021
A. HOW MUCH KNOWN?
B. HOW INTERPRETABLE"
C.
HOW MUCH NEW?
missed
Score Runge
Students
figured soprano entropy 4.76
figured alto entropy 4.78
50
[40,50)
hinted 26%
(3,44)
covered 66%
20,30)
figured bass entropy 4.34
figured tenor entropy 4.80
(0.200)
[0.10)
Figure 5: ILL assessments on knowledge discovery tasks.
forms 66% of standard music theory curriculum (Figure In the rest, about 26% (e.g.. harmonic functions and music forms) was implicitly hinted at by the current n-gram based model, modeling only transitions of abstructions but not explicitly abstructions of transitionss future direction. In the second study, we ran human-subject experiment in the form of homework for music class. The homework asked 23 students to write verbal interpretations of ILL-generated rules rendered as histograms over tagged partitions. Grading was based rubric of keywords generated via majority vote in a later discussion among students and teachers. Figure 53 shows that the majority (2/3) of the students who did the homework succeeded (w.r.t. the 30/50 passing grade) in the interpretation task, which in turn shows the interpretability of the Al-produced knowledge itself.
In the first study, our model also discovered new rules that interested our colleagues in the music school. (a) Tritone resolution is crucial in tonal music, yet in Bach's 's chorales. tritones sometimes do not resolve in typical ways, but consistently transition to other dissonances like minor seventh. (b) A new notion of "the interval of intervals" was consistently extracted in several rule traces. This "second derivative"" like acceleration in mechanics, might suggest new microscopic chord structure heretofore unconsidered. (c) New symmetry patterns reveal new harmonic foundations. As parallel concept of harmony traditionally built on figured bass (dominant in Bach's chorales confirmed by ILL). ILL reveals "figured soprano" as the next alternative in explaining Bach's 's music (Figure 5C). Although not the best view for explaining Bach according to ILL and is not included in any standard music theory class, it may be a valuable perspective for music starting deviating from classical. This was confirmed by domain experts (Sokol, 2016)) with more details in the end of Appendix G.1
5 DISCUSSION: LIMITATIONS AND CHALLENGES
As a first step, we devise a new ippresentation-laamiiee model intended to be both theoretically sound and intrinsically interpretable. This paper shows typical setups and applications, but ILL is general framework that admits new designs of its components, e.g., projection-and-lifiin or priors. Notably, designing a lattice not only sets the rule-learning capacity but also the "vocabulary" for interpretation which, like the Sapir-Whorf hypothesis for human language, limits how a lattice explains signals. Likewise, priors have pros and cons based on what we seek explain and to whom (e.g., not all signals are best explained by symmetry, nor can everyone reads symmetry equally well). One solution to explore multiple lattices while balancing expressiveness and computation common practice in picking MI. models too. Further, whether signal is indeed governed by simple rules requires rethinking. Sometimes, no rules exist, then IIL. will indicate this and a case-by-case study will be needed. Sometimes, rules are insufficient: is music in fact governed by music theory? Theory is better viewed as necessary but not sufficient for good music: great composers need not be great theorists.
Following studies comparing human-codified knowledge and using human-subject experiments for interpretability. more systematic ILL benchmarking and assessment remain challenging and need long-term efforts. Benchmarking is not easy as for task-specific settings (Chollet 2019). requiring better comparison schemes or a downstream task. Effective ILI assessments must focus on new discoveries and the ability assist people. Instead of Turing test for machine-genete -eeerrrted music, one may (at meta-level) consider tests between independent and machine-aided compositions, but both are done by humans. Further, ILL may be incorporated with other models, having an ILL version of deep learning or vice versa. For example, using ILL as a pre-processing or post-interpretation module in other models to achieve superior task performance as well as controllability and interpretability. One other possibility may use ILL to analyze attention matrices (as signals) learned from BERT or GPT (Rogers al. 2020). More future visions are in Appendix H

---

Under review as a conference paper at ICLR 2021
REFERENCES
Amina Adadi and Mohammed Berrada. Peeking inside the black-box: A survey on explainable artificial intelligence (XAI). IEEE Access, 6:52138-52160, 2018.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Trans. Pattern Anal. Mach. Intell.. 35(8):1798-13) 2013.
Karell Bertet and Michel Morvan. Computing the sublattice of lattice generated by a set of elements. In Proc. 3rd Int. Conf. Orders, Algorithms Appl., 1999.
Karell Bertet, Michel Morvan, and Lhouari Nourine. Lazy completion of partial order to the smallest lattice. In Proc. 2nd Int. Symp. Knowl. Retr. Use and Storage for Effic. (KRUSE 1997), pp. 72-81, 1997.
Christina Bodurow. Music and chemistry-waat what's the connection? Chem. Eng. News, 96(36):3--3, 2018.
Nathalie Caspard, Bruno Leclerc, and Bernard Monjardet. Finile Ordered Sets: Concepts, Results and Uses. Number 144 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2012.
Gregory Chaitin. Algorithmic Information Theory. Cambridge University Press, 1987.
Nick Chater and Paul Vitányi. Simplicity: A unifying principle cognitive science? Trends Cogn. Sci., 7(1):19-22, 2003.
François Chollet. On the measure of intelligence. 1rXiv:1911.0154722 [cs.A[], 2019.
Erhan Çınla. Probability and Stochastics, volume 261. Springer Science & Business Media, 2011.
Thomas M Cover and Joy A Thomas. Elements of Information Theory. John Wiley & Sons, 2012,
Constantinos Daskalakis, Richard M Karp, Elchanan Mossel, Samantha Riesenfeld, and Elad Verbin.
Sorting and selection in posets. SIAM J. Comput., 5073)5997-62,, 2011.
Brian A Davey and Hilary A Priestley. Introduction to Lattices and Order. Cambridge University Press, 2002.
Benjamin Eva. Principles of indifference. J. Philos., 116(():390-44) 411, 2019.
Ruma Falk and Clifford Konold. Making sense of randomness: Implicit encoding as basis for judgment. Psychol. Rev. 104(2):301, 1997.
Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foundations. Springer Science & Business Media, 2012.
Bernhard Ganter, Sergei Obiedkov, Sebastian Rudolph, and Gerd Stumme. Conceptual Exploration. Springer, 2016.
Vijay K Garg. Introduction Lattice Theory with Computer Science Applications. Wiley Online Library, 2015.
Ben Goertzel and Cassio Pennachin. Artificial General Intelligence, volume 2. Springer, 2007.
Lejaren Hiller and Leonard Maxwell Isaacson. Illiae Suite, for String Quartet. New Music Edition, 1957.
Steven Holtzen, Todd Millstein, and Guy Van den Broeck. Generating and sampling orbits for lifted probabilistic inference. M.Ki::1933.446220 [cs. 2019.
Matthew
Hutson. child.
How
researchers
are teaching AI to leam like
http://ww.sciencenattt org wwtp://gggg/////////////// boo.-seearcaass---teooooooooreer
how
2018.
Illiac Software, Inc. Harmonia.
httpa:://aarmon htt.:mmii...laaafffffffff com/ 2020.
10

---

Under review as a conference paper at ICLR 2021
Anubhav Jain, Shyue Ping Ong, Geoffroy Hautier, Wei Chen, William Davidson Richards, Stephen Dacek, Shreyas Cholia, Dan Gunter, David Skinner, Gerbrand Ceder, and Kristin A. Persson. The Materials Project: A materials genome approach to accelerating materials innovation. APL Materials, (1))01 1002, 2013.
Michael Jordan. Artificial intelligence- the revolution hasn't happened yet. Harvard Data Science Review, 2019.
David Kaiser and Jonathan Moreno. Self-censorship is not enough. Nature, 492(7429):345-347, 2012.
Martin Kauer and Michal Krupka. Subset-generated complete sublattices as concept lattices. In Proc. 12th Int. Conf. Concept Lattices Appl., pp. 11 11-21, 2015.
Kristian Kersting. Lifted probabilistic inference. In Proc. 20th European Conf. Artif. Intell. (ECAI 2012), pp. 33 33-38, 2012.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. arXiv:1802.03690v/ [stat.ML], 2018.
Holbrook Mann MacNeille. Partially ordered sets. Trans. Am. Math. Soc., 42(3):416 4601 1937.
Gary Mareus. Innateness, AlphaZero, and artificial intelligence. arXiv:1801.05667 [cs.AI], 2018.
Christoph Molnar. Interpretable Machine Learning. Lulu.com, 2019.
Andreas D Pape, Kenneth J Kurtz, and Hiroki Sayama. Complexity measures and concept learning. Math. Psychol., 64:66-75, 2015.
Uta Priss. Formal concept analysis in information science. Ann. Rev. Inform. Sci. Tech., 40(1): 521-543, 2006.
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. primer in BERTology: What we know about how BERT works. arXiv:2002.1232. [cs.CL], 2020.
Andrew D Selbst, Danah Boyd, Sorelle A Friedler, Suresh Venkatasubramannian. and Janet Vertesi. Fairness and abstraction in sociotechnical systems. In Proc. Conf. Fairness, Account. and Transpar. pp. 59-68, 2019.
Claude Shannon. The lattice theory of information. Trans. IRE Prof. Group Inf. Theory, 1(1):105-177 1953.
Charles Percy Snow. The Two Cultures. Cambridge University Press, 1959.
Casey Sokol. Figured soprano. https://casyyyool..cmm///ggg
2016.
Elizabeth S Spelke and Katherine D Kinzler. Core knowledge. Developmental Sci., 10(1):89-96. 2007.
Harini Suresh and John V Guttag. A framework for understanding unintended consequences of machine learning. arXiv:1901.1 100119001.00022 [cs.LG], 2019.
Dmitri Tymoczko. A Geometry of Music: Harmony and Counterpoint in the Extended Common Practice. Oxford University Press, 2010.
Haizi Yu and Lav R. Varshney. Towards deep interpretability (MUS-ROVER II): Learning hierarchical representations of tonal music. In Proc. 5th Int. Conf. Learn. Represent. (ICLR 2017), 2017.
Haizi Yu. Lav R Varshney, Guy Garnett, and Ranjitha Kumar. MUS-ROVER: self-learning system for musical compositional rules, In Proc. 4th Int. Workshop Music. Metacreation (MUME 2016), 2016.
Haizi Yu, Tianxi Li, and Lav Varshney. Probabilistic rule realization and selection. In Proc. 31th
Annu. Conf. Neural Inf. Process. Syst. (NeurIPS 2017), pp. 1561-1571, 2017.

---

Under review as a conference paper at ICLR 2021
Haizi Yu, Lav R. Varshney, and Genevieve L. Stein-O' Oriien. Towards learning human iema-ninterpretable laws of neurogenesis from single-cell ReA-seq data via information lattices. In Proc. 33th Annu. Conf. Neural Inf. Process. Syst. (NeurIPS 2019): Workshop Learn. Meaningful Represent. Life, 2019.
Quan Zhou, Peizhe Tang, Shenxiu Liu, Jinbo Pan, Qimin Yan, and Shou- Shou-Cheng Zhang. Learning atoms for materials discovery. Proc. Natl. Acad. Sei. U.S.A., 115128) 2018.
A CONNECTION TO CONCEPT LATTICE
Per our definition, a concept refers to a component of an abstraction, or more precisely, is a cell in a partition or equivalence class under an equivalence relation. This definition is consistent with
formal concept defined in formal concept analysis (FCA) (Ganter & Wille 2012 Ganter et al. 2016)] Priss 2006) set of objects (extent) sharing set of attributes (intent), which can be also treated as objects that are equivalent under the attributes. However, our definition of a concept generalizes that of formal concept in two ways. First, in our case, partition an equivalence relation is not induced from domain-specific attributes through formal logic and formal ontology, but from universal priors drawn from the Core Knowledge (detailed in Section 3.1 in the main paper). Second, specifying partition considers all of its concepts, whereas specifying set of formal concepts only considers those with respect to given formal context. As result, partition lattices in our case generalize concept lattices in FCA, and are not generated, hence not constrained, by domain knowledge such as those encoded in formal ontologies.
Mathematically, let ($x.=) be the partition lattice comprising all partitions of X and (2xx S) be the subset lattice comprising all subsets of X. Clearly, the power set 2 is the same as {C E P P E }. That is, the subset lattice is also the lattice comprising all concepts from all partitions of X, which can be then called the full concept lattice. So, one can define any concept lattice in FCA as sublattice of the full concept lattice (cf. Definition 3 in (Ganter et al. 2016)). Yet, such a concept sublattice does not have to include all concepts from a partition, and many cases, it tends to miss many concepts if they are not known in the existing ontology. We give two examples below to further illustrate the connection between a partition lattice and a concept lattice.
First, consider biological taxonomy. Dogs and cats are two concepts in species which is abstraction containing other concepts such as eagles. Likewise, mammals and birds are two concepts in class which is abstraction containing other concepts such reptiles and insects; further, animals and plants are two concepts in kingdom. In light of hierarchy, as abstractions. species > class > kingdom (in partition lattice); as concepts, dogs mammals C animals (in concept lattice). Note that when forming a concept lattice, one may not need to include say, all species. Yet when having species as an abstraction a partition lattice, this abstraction must contain all species including known species and unknowns, where the latter is usually of more interest for knowledge discovery.
Second, consider music theory. C major triads, C minor triads, and B diminished triads are concepts in an abstraction induced by music octave-shin and permutation invariance. Further, major triads, minor triads, and diminished triads are concepts in another abstraction induced by music octave-shift, permutation, and further transposition invariance. Clearly, for abstractions, the former abstraction is finer than the latter; for concepts, the set of C major triads a subset (or a special case) of the set of major triads. However, chords that are not defined in traditional music theory but appear as new concepts in a known abstraction (c.g., the two above) may be more interesting, since they may suggest new composition possibilities while still obeying the same music abstraction, in this case the same music symmetry. New concepts from new abstractions may push the composition boundary even further, suggesting new types of chords discovered from e.g., new symmetry (but possibly within known symmetry family). See the end of Appendix G. for more examples from new discoveries.
B MORE GENERALIZED FORMALISM FOR INFORMATION LATTICE
The mathematical setting in the main paper is for a non-negative signal on a finite domain. However, this is not limitation, but purely for notational brevity and computational reasons. First, regarding non-negativity, in many real scenarios, the signal is bounded and its value is only relative. In these cases, can simply add an offset to the signal to make it non-negative. More generally, we can
12

---

Under review as a conference paper at ICLR 2021
consider a signal to be any measurable function Ç concept, a rule, as well as the partial order can be generalized as in Table Hence, the notion of an information lattice is still well-defined in the generalized setting. The essence of the two settings lies in how we formalize an abstraction, whether using partition or a o-algehra. However, the two are not very different from each other: any partition of X generates o-algebra X, and any r-algebra on a countable X is uniquely generated by a partition of X (Cinlar) 2011).
R". Then the notions of abstraction,
Table I: Formulations in the main paper and their generalizations.
in the main paper
generalized
signal
Š X R, X finite
{ R measurable
abstraction
a partition P of X a cell C CET
a g-algebra Σ on X
concept
subset C
rule
r: P.P- RR (=, Ec
r Σ I ==CC)==fok du E Y
partial order
P P
Further, the main paper uses the summation functional in defining rule of a signal, or the projection operator. However, other options possible, e.g., mean, max, min, specially designed functional. The lifting operator can then be redesigned accordingly. In particular, besides always favoring the most uniform signal, the design of the special lifting can have extra freedom in considering other criteria for picking a signal from the general lifting.
C MORE INSIGHTS ON THE SPECIAL LIFTING
Consider the special lifting 1 (R) for any rule set R 45 ($) of a given signal &. Computing (R)) is simple if R {r} contains only single rule. In this case, (x) = (z) == r(C)/IC) for any I E C E domain(r), which requires simply averaging within each cell. However, computing (R) becomes much less trivial when |R| 1. By definition, we need to solve the minimization problem:
(R) := argmin (EN(R)) s
(8)
Instead of directly throwing the above problem 88 into a generic optimization solver, there is more efficient approach which also reveals more insights the special lifting. More specifically, check that any multi-rule lifting 1 (R) can be computed as a single-rule lifting 1 (r*) where the single rule r* is defined on the join VG and is computed as follows:
r(Cp2 C
with the weighted norm ||
Σ
So, instead of lifting R. directly to the signal domain X, we lift R to the join V$ first and then to X.
Since v V S |X], the minimization problem 99 is in a smaller dimension compared to the original problem (8) and thus, can be solved more efficiently. In the minimization problem (9). by definition, (vP) (R) == fr V + IR 4" (23 R}. Hence, every rule E (vB) (R) can be treated as single-rule summary of the rule set R. and y** is one of them-the one that yields the most uniform signal. Realizing the special lifting R - + (R) as the two-step lifting R + r- + + (r*)
(R) reveals the following insight: given rules abstracting & at different levels (coarser or finer), the best can hope to faithfully explain & is the level of the join. Determining E at any level finer than the join would then require additional assumptions other than the rule set itself, such as the preference of uniformity used here. This further explains the two sources of information loss (join and uniformity) discussed in the recovery process of a signal (cf. Section 3 in the main paper). Notably, to determine a signal even at the level of join may be ambigious, since the general lifting (vP) (R) to the join is not necessarily singleton. This particularly implies that r* as of the single-rule summaries of R of & is not necessarily a rule of E. i.c., there is no guarantee that y* = (V?). To make it so, we need more rules.
13

---

Under review as a conference paper at ICLR 2021
D EXISTING WORK ON SUBLATTICE GENERATION
General methods for computing the sublattice LB of a full lattice I. generated by a subset B C L fall into two basic families, depending on whether the full lattice needs to be computed. The first uses alternating join- and meet-completinns with worse-case complexity O the second characterizes the elements of L that belong to the sublattice, with complexity (mmin() [J (L), (L)) ([L and LL) denote the number of biiniireedueibles and meet-irreduuiibles, respectively (Bertet & Morvan 1999). The latter requires computing the full lattice, which is intractable in our case of partition lattices, as [4] = | grows faster than exponentially in |X|] whereas (3 is usually smaller than X So,
where
the first approach and compute alternating join- and meet-completions. The same principle of avoiding computing the full lattice has been applied to the special context of concept lattices (Kauer & Krupka 2015). yet the technique there still requires the full formal context corresponding to the full concept lattice. Note that sublattice completion is, by definition, computing the smallest sublattice LB (in a full lattice L) containing the input subset B C L. where L must inherit the meet and join operations from L. It generalizes but is not the same as -rrckinn-MaNNelllee
completion (Bertet & Morvan 1999 MacNeille 1937, Bertet et al. 1997.
E MORE DETAILS ON THE CONSTRUCTION PHASE
This section elaborates on the second half of Section 3.1 in the main paper, presenting more algo- rithmic details on poset construction and sublattice completion. The core data structures for posets are the so-called adjacency matrix and Hasse diagram, encoding the partial order - and the cover relation <.. respectively (Garg 2015). The former is best for querying ancestors and descendants of a partition within the lattice; the latter is best for querying parents and children of a partition. (A more advanced technique includes bhain-dccomposition, but the two here are sufficient for this paper.) More specifically,
P' is an ancestor of P PXP' P'
p' is parent P P P' P but no p satisfies P p" - P!).
We introduce few algorithmic notations. Given a partition poset (H, 3), we use B.pommarixx and Q hasseee_dieee di agram to denote the adjacency matrix and Hasse diagram of q. respectively. For any partition P Q, we use P. P.ancestors, P. P.descendants, P P.parents, and P. P.chillren to denote the sets of ancestors, descendants, parents, and children of P, respectively. Notably, the two data structures are not only important for the construction phase but for the subsequent learning phase as well. The core subroutine in the construction phase is ADD PED.PATTTIOON sketched as Algorithm [ It the key unit step both poset construction and memilllttteee completion.
Poset construction. This corresponds to Step 3 in the flowchart in Section 3.1 of the main paper. Recall that poset construction refers to the process of sorting a multiset (rr,s) of tagged partitions into a poset (F), 3). where the partition tags features and symmetries. Naively, if we write an inner subroutine COMPARE(P, P') an oracle in the related literature-to compare two partitions, sorting multiset into a poset amounts to (?) calls of this pairwise comparison where N is the size of the input multiset. So, the common idea shared in almost all poset sorting algorithms is to reduce the number of oracle calls as much as possible. As mentioned in the main paper, considering the additional properties in our case, we leverage (a) transitivity (valid for all posets), (b) partition size (valid for partitions), and (c) partition tag (valid for tagged partitions) pre-determine or pre-filter relations. In other words, we want to infer from the context as many pairwise relations as possible, so that the number of actual pairwise comparisons can be minimized.
More specifically, we start from an empty poset, and call ADD PARTITION to incrementally add partitions from the input multiset to the poset. As the outer subroutine, ADD PARTITION lever- ages transitivity and partition size by maintaining three live data structures, namely size2partns, po.matrix, and lissseddaagamm. so as to avoid calling COMPARE whenever possible. Conse- quently, COMPARE is called only at two places (underlined in Algorithm D one for = and one for <. When called as the inner subroutine, COMPARE(P, P') does not always perform an actual computation for pairwise comparison. Instead, it first checks if the tags are informative (c.g., com- positionns/superrrouss imply coarser partitions) and only if not, makes an actual comparison. With the additional information from partition size, an actual comparison be done in O((X)) time
14

---

Under review as a conference paper at ICLR 2021
Algorithm 1: ADD PARTITION (P::P)) adds tagged partition P, partition poset (9,
Input: a tagged partition Pr, where the tag T can be a feature/yymmerry or a join/meet formula; a partition poset (P; 3), with the following members and hash tables:
every & is unique partition (indexed by a unique identifier)
F p.patn2taggs [P] = {r P, P) denotes the of all tags inducing P
B siszeparrts [k] (P] [P| k} denotes the set of all P & with size k
B matrix encodes the partial order x, best for getting P. P.ancestors/ ?.ancestorrsdasscdaaats /dsccedantts
P hasse _atasee_daae agram encodes the cover relation <c. best for getting P. P.parents/ children
Step 1: determine if Pp is new by COMPARE(P, P+) (for -) for every
P E G. pisize2partns. [[P+]]
if P, p.size2partns [|pr|]: update P p..aatn2tags [P,] by adding :; return
else: create a new hash entry Q p.part22tags [P,1 {r}: proceed to Step 2
Step 2: add the new partition P, to Ff
(2a) update Pisize2partns [[pr]] by adding Pr
(2b) update iipommatrx and Q .digaam
for every existing size k < [P+ sorted in descending order:
for every P E Plsize2parrns [k]:
if P.parents n P,, desceeddanss * 0: update P. popoomatrix by adding P < Pr else: COMPARE(P, P-): update P.po matrix and I B.aass diagram if Pr (here one can check: is necessarily the case that P <e P.)
- do the above symmetrically for every existing size k >> |Pr| sorted in an ascending order (note: every P F..iiz2ppartss [k] for k |Pr is incomparable with P-)
clean cover relation: remove any Pa le P from Z hasse _diggram if Pa -e P, -e p
via a mapping process. More specifically, given two partitions P, P', without loss of generality, we assume [P| < [P']. An actual comparison is made by tentatively creating mapping P' P. One can check that such a exists if and only if P P'. Hence, if [P] = [P'| (resp. |P| < (P'), can determine (resp. <)) if v/ is created successfully or incomparability otherwise. The mapping complexity is linear in |X|. with linear coefficient 1 if mapping succeeds and with linear coefficient < 1 if mapping fails. In the worst case (e.g., if all partitions are incomparable), all (?) pairwise comparisons are required. Our algorithm works best when partitions richly related (i.e., the Hasse diagram is dense), which is indeed the case for our tagged partitions induced from systematically formed features and symmetries.
Semilattice completion. This corresponds to Step 4 in the flowchart in Section 3.1 of the main paper. Recall that join-semilattice completion refers the process of completing a partition poset into a semilattice. We only detail join-semilattice completion, since meet-semilee semtlatemi completion can be done symmetrically. Formally, we want to compute the som-aaeil of B generated by the input poset (F.)), z). We denote the resulting join semilattice by (96 (F,()))) By definition,
(PiF,s)) == (v33 & C (r.s;
Naively, if computing (F,s)) literally from the above definition, one has to iterate over all subsets of (F.S) and compute their joins. This amounts to 2 join computations where N = [ is the size of the input poset, and moreover, many of the joins are not pairwise. Yet, similar to our earlier poset construction,
may reduce the computations of joins by an incremental method, which also embeds ADD PARTITION as a subroutine and utilizes partition sizes and tags, but now the tags are join formulae instead of features symmetries.
More specifically, we start with an empty semilattice 3, and add partitions in P( to G one by one from smaller-sized to larger-sized (note: the size information is maintained B(r.s) (.r.s)... wizeepartza)) When a partition P E (r,ss is to be added, we make a tag named by itself, i.e., let P, := P with T = (P). and then call ADD AARTITION(P... F3). There are two possibilities here: P, already exists in 2 (call ends by Step 1) or P, is new (call ends by Step 2). In the former, we done with P..
15

---

Under review as a conference paper at ICLR 2021
In the latter, for every P' E B((P,), compute the pairwise join J(P') == V(P,, P") and its tags T(P)) == (TUT' F' E P.paatntaag [P']] }. and call ADD PARTPPTTOOOON((P COMPARE, computing join can be optimized by leveraging previously computed tags and partial order in the input poset (F.)) so as to avoid an actual join computation whenever possible. When inferring from the context is not possible, one can perform an actual join computation V(P, P') in O(IXI) time. This is done by collecting the unique pairs of cell IDs (C(x), (x)) for every 2: E X, where C(x) and (x) denote the cell IDs of x in P and P', respectively. In the worst case (e.g.. if all partitions incomparable and join-irreducible), the complexity is inevitably O(2*). However, like in poset construction, our algorithm works best when the partial order structure is rich.
P). Like
Practical tips for sublattice completion. This corresponds Step (5) in the flowchart in Section 3.1 of the main paper. Recall that constructing the sublattice of Fx generated by ((s follows the alternating process: Lu == (s.F), L1 == (Lo)², L2 = (I1)*, Ly == (L2) and so forth, which terminates as soon as - = Lxx- We denote the end result by (F (issF)))A.,, (AA",, which is the desired sublattice. However, we may want to stop early in the completion sequence, due to concerns from computation, interpretabilityy expressiveness, as well as their tradeoffs. We suggest a practical tip on deciding where stop. If the input poset F.F.)) is small, run alternating joins and meets, or even complete it to the sublattice if affordable. If (F.S) is moderate, complete the joins only (as join is closely related to rule lifting, see Appdenix C for more details). If B (P,S) is large, just use it.
F MORE ANALYSES IN THE LEARNING PHASE
This section elaborates on the last paragraph of Section 3.2 in the main paper, presenting more analyses and interpretations on the rule traces elicited from the toy handwritten-digit examples. Yet, as mentioned in the main paper, computer vision is currently not among the typical use cases of ILL. Learning rules of handwritten digits may not be of much independent interest unless for calligraphy. So. the analyses and interpretations here are for illustration purposes only. We refer readers to the Broader Impact section in the main paper for possible future directions on how ILL may be used, together with other MI models, to solve computer vision tasks.
Recall that the main use case of ILL is to explain a signal &, answering what makes an g. The same toy example illustrating an ILL. process is replayed here in Figure 3 The signal & (O....,.7 [0, 1] is grayscale image of a handwritten "7". In this case, a rule of &, or the projection of & to a partition of {0. 27)2, can be viewed as gathering "ink" within each partition cell. Accordingly, the (special) lifting can be viewed as redistributing the gathered "ink" (evenly) in each cell. Hence, we term this view the ink model. For visual convenience, we depict a rule of 2D signal by its lifting (i.e., another grayscale image), since with pixels in the same cell colored the same, we can use the lifting sketch both the partition and the rule values. More precisely, when lifting represents rule, it must be viewed in terms of blocks or superpixels; whereas a real lifting (i.e., a signal or a real image) is viewed normally by the regular pixels. To better clarify, all rules in Figure 3 are displayed in red boxes, whereas all liftings are in green ones.
-
For simple illustration, we draw small number of features and symmetries to generate a poset (Q.)) of 21 partitions. The corresponding part of the information lattice (R.) is shown by its Hasse diagram in 3 Further, on top of the Hasse diagram. we demarcate the frontiers of the sublevel sets (R.c)) by six blue dashed curves. Note that in this tiny diagram, we have sketched a full range of sublevel sets, yet for large diagrams, sublevel sets are constructed for small c-values only in a single-pass BFS. The right part of Figure 3 illustrates a complete ILL process in the alternating setting, with lift-project signified by the green up-arrows and red down-arrows, respectively. During the learning process, ILL tries to minimize the gap in the signal domain (upstairs) through iterative eliminations of the largest gap in the rule domain (downstairs). Eliminating a larger rule gap tends to imply larger drop in the signal gap, but not necessarily in every iteration, since the special lifting may accidentally recover a better signal if the assumed uniformity is, by chance, present in the signal. The rule set (A)) formed per iteration is presented in the middle of the right part of Figure 3 which joinly shows the complete rule trace continuously progressing along the c-path.
The rule set in the last iteration under any e (marked by * in Figure B is the returned solution to the main relaxed Problem (4) in the main paper. This rule set is used to answer what makes & an E. For example, let ry denote the rule with ID j (here a rule ID is the same as the partition ID, the unique identifier used in Algorithm I during the construction phase). Then, among all rules whose entropies
16

---

Under review as a conference paper at ICLR 2021
larger than = 2, the third rule set in the trace R(3) {rr. 718) best explains what makes & an Ç. However, more complex rules are allowed, say if all rule entropies are now capped by = 6, R((7) (r13; (15. (19) the best.
Recall that we do not just eyeball the rules to get intuitive understandings. Every rule is the projection of the signal to a tagged partition, where the tag, generated in prior-driven way, explicitly explains the underlying abstraction criteria. For example, r19 in Figure 3 comes from symmetry tag representing a permutation invariance, which visually renders as a reflection invariance. Rules r' and 79 come from two feature tags div, W[] and div, W()), respectively. These two feature tags represent the continuous and even collapsing in the first and the second coordinate, respectively, which visually render horizontal and vertical strips in either case. Both rules are later absorbed into r13 tagged by div, o ([.2)) .2]. since its rule domain is strictly finer. These rules (r's 79. F13) apparently summarize the horizontal and vertical parts of the handwritten "7". Further, the vertical part of the "7" is longer and slants more, so we see more vertically -patterred rules in the rule trace (rg, T11 r15). These rules are obtained from finer and finer abstractions along the horizontal direction, so to capture more details on the vertical part of that "7" such as its slope. Notably, among these vertically-patterned patteeredddeddd rules, F11 is induced from the symmetry representing a horizontal translation invariance, but is quickly absorbed into whose entropy is not much higher. This transient appearance of r implies that it plays less important role explaining this handwritten "7". In fact, from more experiments, symmetrics in general play less important role in explaining many "7"s. This is, however, not the case in explaining many "8"s, where symmetries occur much more often. For example, consider a symmetry fused from translation and permutation invariances whose fundamental domain is homeomorphic to Möbius strip. We hypothesize that this topological property might be related to the twisted nature of an "8". For visual comparison, present the rule traces learned from "7" and "8" below in Figure as well as the visual similarity between a Möbius strip and an "8"
7
A
8
8
A
V
X
8
Figure 6: A rule trace of a "7" and that an "8", together with a 2D Möbius strip.
G STUDIES ON ILL-BASED MUSIC APPLICATION
We introduce two tests associated with real-world application. The first is to assess rule-learning efficacy, where we compare machine-discovered rules to human-codified domain knowledge. The second is to assess human-ine auman-interpretabllii where we use human subject experiments on interpreting machine-gent -eeeeree-eeee rules.
The application here is our first step towards building an automatic music theorist and pedagogue, which to be deployed as an assistant in music research and education. The two tests are our initial effort towards a systematic benchmarking and assessment platform. In the continuing effort of bridging human and machine intelligence, new standards are to be set and commonly agreed upon, so as to reasonably compare machine-codified discoveries with human-codified knowledge, as well as to use numan-subject experiments for assessing interpretability. Fully developing assessment protocols challenging, long-term term endeavor. Here, from each. Respectively, the first experiment tests music rule discovery, basic requirement to a theorist; the second tests interpretability, a basic requirement be pedagogue.
the two tests starting points, and present results
17

---

Under review as a conference paper at ICLR 2021
HOME
chord
chord
Contents
Feature modez WE
Ride: -
R-grumc
Contents
Feature: modiz
Rute: 8/8
nigramm
Buli
Chon
Bude Leammnnnnng Setting
Composition
Analytics
Analytics
Eauch tands
Iacc Eiran
Copa
Studant sclver
Astomatic
Desiation
8070A
Comments: Sogeano Largelty diatonic.
(b)
Figure 7: ILL-based music web interface: (a) rule histogram; (b) user control panel.
ALMOST NO
A DIATONIC SCALE
DOMINANT RESOLVES
VOICE CROSSING
TRIAD (ROOT DOUBLING PREFERRED)
PARTITION
N-GRAM:
N-GRAM: FEATURE: mod12
N-GRAM: 2
FEATURE: argsort 11233.444
CONDITIONAL: 2,5,711
sort mod12 211233444
0 4 2
R
0,0,4,7 0,4,4,7
Figure 8: Examples of IL. ILL-generated music rule histograms: first two are context-free rules, the last one is comtext-dependent rule.
To conduct the two tests, we first build user-friendly web application, which is used to better see and control the II.I. learning process and results. Figure Tigure]iillstreen illlustratss the web interface. Users learn music rules-each histogram over tagged partition (i.e., machine-codified music concepts)-and and control their learning pace via self-explanatory knobs whose set values are automatically converted to internal parameters (e.g.. E, 7). One critical music-specific extension to the vanilla ILL presented in the main paper is adding a temporal component, since music highly contextual. This amounts to considering more than signal simultaneously, which include various (un conndiiionall chord distributions (multiple n-grams with varying n's and varying conditionals) encoding information of individual chords well melodic and harmonic progressions. Accordingly. ILI. produces both context-free and context-depender rules, each of which is indexed by partition and conditional under that partition. For example, given the partition that equivalent to classifying music chords into roman numerals and conditioned on the previous two chords being a I followed by V, rule specifies the probability distribution of the next roman numeral, and in this case reproduces the music rule on Cadential-66 -64. Note that in a context-dependent rule, not only is the query chord abstracted, also the conditional. This contrast with many classical r--rram models where no abstraction is present and thus may suffer from the problem of rare contexts, where a conditional occurs very few or even zero times in the training set. However here, the core idea of abstraction makes "small data" large and thus rare contexts common. More examples of context-free and deeendtdeeennden rules illustrated as histograms in Figure These rule histograms are generated from ILL based on 370 of Bach's four-part chorales (in the format of digital sheet music), and used in the two experiments detailed below.
G.1 COMPARISON HUMAN-CODIFE KNOWLEDGE
We compare rules learned from ILL to standard undergraduate music theory curriculum. We want to use known laws from music theory as benchmark to see how ILL-generated rules correspond to numan--odiiied music knowledge. In particular,
what is covered, what is new, and what different. Yet, the ultimate goal is not just to use known music theory as a ground truth for the purpose of driving ILI. to fully reconstruct what know, but eventually to discover new rules,
want
18

---

Under review as a conference paper at ICLR 2021
to gain new understandings of existing rules, to suggest new composition possibilities, as well as to teach rules in a personalized way.
A priori we aware of three major differences between human-codified music theory and ILL- generated rules. (a) In light of music raw representations (input), laws of music theory are derived from all aspects in sheet music whereas ILL--generated rules currently derived from only MIDI pitches and their durations. This is because we currently study ILL as a general framework. When a music-specific application is to be developed later, one can include more music raw representations such as letter pitches, meter, measure, beaming, and articulations. (b) In light of rule format (output), laws of music theory and ILL-generated rules have two different styles, with the former being more descriptive and absolute (hard), whereas the latter being more numerical and probabilistic (soft). For instance, music rule that completely forbids consecutive fifths reproduced by an -g.--reeer rule that assigns a small non-zero probability to the event. Therefore, while it is possible to "translate", with information loss, (precise) ILL--generated rule to a (verbal) rule in known theory, it may not make sense to "translate" in the opposite direction. Also, it is not a good idea to hardcode known rules as categorical labels in a supervised setting, since music rules are inherently flexible and hardcoding may lead to a rule-based AI that generates somewhat "mechanical" music such as the Illiac Suite (Hiller & Isaacson| 1957). (c) In light of purposes, laws of music theory are more intended for general pedagogical purposes, rather than to reflect the style of particular data set. For instance, while consecutive fifths are banned in homework and exams, they may be widely used in many pop songs. Even in our data set of Bach's 's chorales (which are supposed to follow the known rules quite well), we see Bach himself wrote a handful of consecutive perfect intervals. On the contrary, ILL-generated rules are specific the input data set. We may certainly find some data sets that follow the known rules quite well (e.g., Bach's 's chorales), but also others that break many known rules and even set their own rules.
Keeping these three differences in mind and by further isolating them from the comparison results, we can reveal the remaining differences that are due to the rule-learning process itself. To come up with the benchmark, we compiled a comprehensive syllabus of laws from music theory taught in our music school's theory review course, which runs through the full series of theory classes at a fast pace. This human-codified music knowledge is organized indexed by lecture number. On the other hand, ILL-ggenrated rules are indexed by partition (ID) and n-gram (n). The results summarized below in Table 2 where the colored crosses in the last column indicate topics that are missed by ILL due to different reasons.
rumning list of 75 topics and subtopics
Among the total 75 topics in Table 2 we first ignore 7 of them (red crosses) which require music raw representations beyond MIDI pitches and durations (e.g., accents and enharmonic respellings of some augmented sixth chords). ILL covered 45 out of the remaining 68 topics, yielding coverage of 66%. Among the 23 missed topics, 18 (blue crosses) are related to deeper-level temporal abstractions such as harmonic functions, key areas, and forms. These temporal abstractions may be better modeled as abstractions of transitions, which are implicitly captured but not explicitly recovered from our current multi- multi-abstrraction multi-n-gram language model, modeling only transitions of abstractions. The other 5 missed topics (black crosses) are tricky and require ad-hoc encodings, which are not explicitly learnable (but may be implicitly captured to some extent) from our current ILL implementation. Accordingly, the composition of the 30 = 7 + 18 + 5 uncovered topics suggest three future directions to possibly raise the rule-learning capacity of the current implementation: (a) include more music raw representations; (b) model abstractions of transitions; (c) either make music-specific adjustments when developing music apps or figure out a more expressive and more general framework in the long run. However, remember that the goal here is not to reproduce what know but to augment it. So, we may certainly stop after enabling abstractions of transitions, which in the best case can yield an improved coverage of 84% (i.e., 93% of the topics from MIDI notes only) which is good enough.
Lecture
Music Theory
Partition IDs
n-grom
1
music accents pitch pitch class interval
2
1-4
1
2
16-19
2
31-36
Table 2 (cont.)
19

---

Under review as a conference paper at ICLR 2021
Lecture
Music Theory
Partition IDs
T-gram
2
interval class
97-102
3
stepwise melodic motion (counterpoint)
1-4
2
3
consonant harmonic intervals (counterpoint)
97-102
3
beginning scale degree (counterpoint)
16-19
2
3
ending scale degree (counterpoint)
16-19
3
beginning interval class (counterpoint) ending interval class (counterpoint)
97-102
2
3
97-102
3
parallel perfect intervals (counterpoint)
97-102
3
directed perfect intervals (counterpoint)
3
law of recovery (counterpoint) contrapuntal cadence (counterpoint)
1-4
23
3
1-4,
97-102
2,3
3
melodic minor ascending line (counterpoint)
4
triads and seventh chords triads and seventh chords: quality
26-30
4
140-144
4
triads and seventh chords: inversion figured bass
113-117
5
113-117
1,2
5
roman numerals
81-85,129-133
6
melodic reduction (Schenkerian analysis)
7
passing tone (tones of figuration) neighbor tone (tones of figuration) changing (tones of figuration) appoggiatura (tones of figuration) escape tone (tones of figuration) suspension (tones of figuration) anticipation (tones of figuration) pedal point (tones of figuration) (un)accented (tones of figuration) chromaticism (tones of figuration) tonic (function) dominant (function) authentic cadence half cadence
1-4, 134- 144
3
7
1-4, 134-144
3
7
1-4, 134-144
4
7
1-4, 134-144
3
7
1-4, 134-144
7
1-4, 134-144
3
7
1-4, 134-144
7
1-4
3
7
7
8
8
8
1,4481-85,129-133
2,3
8
81-85,
1333
2,3
9
voice range (four-part texture) voice spacing (four-part texture) voice exchange (four-part texture) voice crossing (four-part texture)
1-4
9
31-41
9
20-25
2
9
53-63
9
voice overlapping (four-part texture)
9
tendency tone (four-part texture)
16-19
1,2
9
doubling (four-part texture)
86-91
10
harmonic reduction (sccond-Lew -evel analysis)
11
expansion chord
12
predominant (function)
13
phrase model pedal or neighbor (six-four chord) passing (six-four chord)
14
4,113-117
3
14
4.113-117
14
arpeggiated (six-four chord) cadential (six-four chord) embedded phrase model non-dominant seventh chord (function) tonic substitute (submediant chord) deceptive cadence (submediant chord) functional substitute (mediant chord) back-relating dominant
14
85,113-117,133
3,4
15
16
17
17
81-85,129-133
2,3
18
19
81-85,
2,3
20
period (I)
X
21
period (II)
22
period (III)
X
Table (cont.)
20

---

Under review as a conference paper at ICLR 2021
Lecture
Music Theory
Partition IDs
T--ram
23
applied chords (I)
81-85,129-133
2,3
24
applied chords (II)
81-85,129-133
2,3
25
applied chords (III)
81-85,129-133
2,3
26
modulation (I)
X
27
modulation (II)
28
binary form (I)
29
binary form (II)
30
modal mixture
31
Neapolitan
81-85,129-133
32
Italian sixth chord
1 140- 144
32
French sixth chord German sixth chord Swiss sixth chord ternary form sonata form
144
32
32
X
X
33
34
Table Comparison of ILL-generated rules human-codified laws of music theory taught in standard undergraduate music theory courses. Checks (45) in the last column denote topics recovered by ILL. Red crosses (7) denote topics not recoverable from our music raw representations; blue crosses (18) denote topics not recoverable from our n-gram transitions of abstractions (partitions); black crosses (5) denote topics not recoverable from the constructed lattice abstractions.
From another source of music theory considering music symmetries (Tymoczko 2010), we compare IIL--generated rules with a set of commonly used music operations, known as the OPTIC operations, namely octave shifts (O), permutations (P), transpositions (T), inversions (I), and cardinality changes (C), The results are summarized in Table 3 which shows that ILL covers the major four types of operations (OPTT). The music C operation
not recovered since it is not a transformation in the mathematical sense. Notations: fy denotes a translation by the translation vector v, i.e., (x) == x v; rA denotes a rotation (can proper or improper) by the rotation matrix A, i.e., 1' ( == Ax. As special type rotation matrices, p(.-) denotes permutation matrix where the superscript the cycle notation of permutation. Note that II.I., general framework, considers a much larger universe generic symmetries (from Core Knowledge) beyond those already considered in music. Therefore, ILL can not only study existing music symmetries, but also suggest new symmetries to be exploited new music styles as well as possible music interpretations of symmetries discovered in other fields like chemistry as described in the main paper.
Table 3: Comparison of ILL's iyddetry-induced rule abstractions to the music OPTIC operations.
Operation
Music Description
Subgroup
Octave shift
"Move any note into new octave."
(ftizer t12ez t12ey t1zea }
Permutation
"Reorder the object, changing which voice is assigned to which note."
((rpua) Ppca,s), P p(s.4)
Transposition
Transpose the object, moving all of its notes in the same direction the same amount."
({ta))
Inversion
"Invert the object by turning it 'upside down'."
(fr-11)
Cardinality Change
"Add new voice duplicating one of the notes in the object."
21

---

Under review as a conference paper at ICLR 2021
figured soprano (entropy = 4.76)
figured alto (entropy = 4.78)
figured tenor (entropy 4.80)
figured bass (entropy 4.34)
0.3
0.3
0.3
0.3
most probable figures (show top 20 only)
most probable figures (show top 20 only)
most probable figures (show top 20 only)
most probable figures (show top 20 only)
Figure 9: Rules on figured soprano, figured alto, figured tenor, and figured bass. Each histogram shows only the top 20 most probable figures (for brevity), while the entropy computed from the entire rule. Among the four cases, ILL shows that figured bass (with the smallest entropy) is most effective in explaining Bach's chorales, echoing its importance as a main topic in any standard music theory curriculum. ILL further reveals figured soprano as the next most effective.
Lastly, we mention a few new rules discovered by ILL that are interesting to our colleagues in the School of Music. First, tritone resolution plays an important role in tonal music and appears as an epitome in many more general harmonic resolutions. Yet, in Bach's ' chorales, tritones are sometimes not resolved in a typical way but consistently transition to another dissonance like the minor seventh, which behaves like a harmonic version of an escape tone or changing tone. Second, a new notion of "the interval of intervals" has been consistently extracted in several ILL--generaed rule traces. Such "second derivative", like acceleration in mechanics, might suggest a new microscopic chord structure to consider. Third, new symmetry patterns reveal new possible foundations for building chords, and thus new composition possibilities. For example, as a parallel concept of harmony traditionally built on figured bass (which indeed the dominant pattern in Bach's ' chorales confirmed by ILL), ILL reveals "figured soprano" as the next alternative in explaining Bach's 's music (Figure 9 Clearly, figured soprano is not the best view for explaining Bach according to III.. and indeed not included in any standard music theory class, yet it may be more efficient perspective to view other types of music (e.g., in some Jazz improvisations). This vision coincides with comments made by Casey Sokol (Sokol 2016), music professor at York University, which quote below: "The idea of Figured Soprano is simply a way of taking this thinking from the top-down and bringing it into greater prominence as creative gesture. So these exercises are not anything new in their ideation, but they can bring many new ideas, chord progressions and much else. It's a somewhat neglected area of harmonic study and it's lot of fun play with."
G.2 HUMAN SUBIECT EXPERIMENT FOR ASSESSING INTERPRETABILITY
Our second experiment is a human subject experiment, where we collect and assess numan-generatee verbal interpretations of ILL-generated music rules rendered as sophisticated symbolic and numeric objects. Our goal is to use the results here to reveal both the possibilities and challenges in such process of decoding expressive messages from Al sources. We treat this as a first step towards (a) a better design of AI representations that are human- -nteerperteeee and (b) general methodology to evaluate interpretability of Al-discovered knowledge representations. In this experiment, we want to test to what degree our ILL-ggneetted rules are interpretable. Our subject pool includes people who have entry-level math and music theory knowledge. So, by interpretability. we mean interpretable to them. The whole experimental procedure divides into two stages. At the first stage, we collect human interpretations of ILL-generated rules. At the second stage, we assess the collected interpretations to further evaluate the interpretability of Al-produced knowledge.
Collect Human Interpretations. The experiment was conducted in the form of a two-week written homework assignment for 23 students. Students came from the CS+Music degree program recently launched in our university. Entry-level knowledge of computer science, related math, and music theory is assumed from every student. However, all students are new to our Al system, and none have read any ILL-generated rules before. The homework contained three parts. Part provided detailed instructions on the format of the rules as exemplified in Figure 3 including both feature-related and probability-related instructions (symmetries were excluded from the tags since group theory is an unfamiliar subject to these students). More specifically, we provided verbal definition, mathematical representation, and typical examples for each of the following terms: chord, window (for coordinate selection), seed feature, feature, rule, n- r-gramm histogram, data set. A faithful understanding of these eight terms was the only prerequisite to complete the homework. The estimated reading time of the
22

---

Under review as a conference paper at ICLR 2021
instructions was about an hour. Once this self-training part was completed, the students were ready to go to the second and third parts- the main body of the homework. Part II contained eleven 1 1-gram rules-a histogram specified by window and seed feature(s); Part III contained fourteen 2 2-gram rules-a a histogram now specified by window, seed feature(s), and a conditional. The students were asked to freely write what they saw in each of the histograms guided by the following two questions. (a) Does the histogram agree or disagree with any of the music concepts/rules you know (write down the music concepts/rules in music-theoretic terms)? (b) Does the histogram suggest something new (i.e., neither an agreement nor disagreement, with no clear connection to any known knowledge)? Answers to each of the 25 rules came in the form of text, containing word descriptions that "decode" the histogram- symbolic and pictorial encoding. Students were explicitly instructed that writing out a description that was basically a literal repetition of the histogram (e.g., taking modulo of a chord results in 91 .1. chance of being 0, 0, 4, 7) is not acceptable: they must reveal the music behind the math. In fact, we made it clear to the students that we only want qualitative descriptions. Students were specifically told (in the instructions) to only pay attention to the relative values of the probabilities whose exact numbers are unimportant (e.g., what are most likely, what are more likely, what are almost impossible). This homework was due in two weeks. During the two-week period, we asked the students to complete it independently, with no group work or office hours.
Assess Human Interpretations. The homework was designed in way such that every rule histor- gram encoded at least one music concept/rule consistent with standard music theory. In addition, every histogram contained either one additional known music rule or something strange that either conflicted with a known rule or represented something new. We assigned two points per rule. Further, we made an initial rubric containing the (authoritative) music keywords used to describe every rule histogram. Because students' answers arrived in the form of qualitative text, to ensure credibility and fairness of the initial rubric, we held discussion session a regular lecture time (80 minutes) with all students as well as the teaching staff. During the discussion session, we went over all 25 rules one by one. For each, we first announced the keywords in the initial rubric and explained to the students that these keywords would later be used to grade their homework. However, in the discussion session, every student was encouraged to object to any of our announced keywords and/or to propose new keywords accompanied with a convincing explanation. New/modified keywords that were commonly agreed upon were added/updated to the initial rubric. By the end of discussion session, we compiled more inclusive rubric containing broadly accepted keywords. This rubric-generating process was transparent to all the students. In the final step, we manually graded every student's 's answer sheet against keywords in the rubric and computed their scores. A summary of the students' performances is presented in Table Except for cases where the student did not do the homework, major source of score deduction was from misunderstanding the n-gram (e.g.. the probability of the current chord conditioned on the previous chord was mistakenly interpreted as the probability of the previous chord conditioned on the current one). This may be largely due to unfamiliarity with the n-gram models for new CS+Music students. Nevertheless, the majority of the students who did the homework (2/3) succeeded (with respect to the 30/50 passing grade) in interpreting the rules generated from ILL, which in turn provides evidence on the interpretability of the Al-produced knowledge itself.
Table 4: Students' final scores.
Score Range
# of Students
50
40.50)
7
30,40)
2
20,33)
4
100200)
[0.10)
5
H CONCLUSION AND BROADER IMPACTS
Model transparency and interpretability are important for trustworthy AL. especially when interacting
directly with people such as scientists, artists, and even multidisciplinary researchers bridging the Two
23

---

Under review as a conference paper at ICLR 2021
Cultures (Snow 1959) (e.g., ... like music and chemistry). The core philosophy underlying ILL arises from a cuman-centered standpoint and our long-term pursuit of "getting humanity back into artificial intelligence". We strive to develop human-like artificial intelligence,, which in turn may help advance human intelligence- a goal at the intersection of AGI (artificial general intelligence (Goertzel & Pennachin 2007)), XAI (explainable artificial intelligence (Adadi & Berrada 2018)). and "Al as augmented intelligence" (Jordan 2019).
As such, the focus of interpretability in this line of research is just the end result of the model, but the entire learning process. This emphasis on process is not only manifest in this paper (e.g.. two-phase learning that "starts like baby and learns like a child" with a full rule trace output), but also in ongoing ILL-driven real-world projects aimed for beneficent societal impact. To name few: (a) IL--aided scientific research to accelerate new discoveries, as in biology (Yu et al. 2019h; (b) I.I.-- aided artistic creation to enable new ways and new dimensions in one's creative and/or collaborative experience (art as a process is about more than the work itself); (c) ILL-aidded personalized education. Discovered scientific knowledge, artistic expression, and educational curricula, may have dual use character (Kaiser & Moreno 2012). Nevertheless, making the discovery of abstract knowledge easier may lead to abstraction traps (Selbst et al. 2019) in deploying such learned knowledge in engineering design or policy making.
Evaluation for ILL and similar technologies should have humanist perspective, whether comparing to human-codiffed knowledge or with human subject experiments to assess interpretability. Moreover, evaluations for scientific discovery, artistic creativity, and personalized education should not only focus on model performance, but also on the human-centered criteria of how effectively they aid people in achieving their goals. Illuminating rules associated with practice not only helps human students be better rule-followers, but more creative rule-breakers and rule-makers. Instead of Turing test for machine- machine-generated music, one might more productively conduct artistic evaluation at a meta-level between Human--ritten music constructed with and without assistance from ILL.
Regarding biases in data, because ILL works in the "small data" regime makes casier curate data to avoid representation biases (Suresh & Guttag, 2019). Manually curating 370 music compositions possible, but manually curating billion is not.
ILL can be treated as complement to many existing Al models, with a special focus model transparency and explainability. Extensions to ILL could enable better cooperate with other models, e.g., a pre-processing or a post-interpretation tool to achieve superior task performance as well as controllability and interpretability. One such possibility could leverage ILL to analyze the attention matrices (as signals) learned from a cannsformr-bbsce. NLP model like BERT GPT (Rogers et al. 2020).
24


Reviews:
[{"review_id": "me5zCO-oyK8", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper has addressed a very ambitious goal about explainability and generalizability from “small data\" by generalizing the information lattice defined by Shannon. The topic of this paper is very significant but there are a few questions that I concern:\n\n1. The paper has tried to answer some well-known challenging problems in machine learning such as explainability and generalizability from a very different perspective. However, the authors simply introduce some kind of framework but not provide a persuasive analysis or theoretical/empirical results to show it addressing the problems in the introduction. In fact, I do not find a theorem or commonly recognized experiment comparison in this paper. Thus I can not evaluate the significance of the technical contents.\n\n2. The paper has used very complicated notations such as up/down arrows to show their results. However, is it really necessary? The tractability of the resulted problems (1) and the relaxed version (4) should be seriously concerned, not only providing a certain explanation or heuristic. Meanwhile, I recommend the authors to use simple and explicit enough formulations to show their framework so that we can know the tractability at the first glance, such as the convexity/nonconvexity, continuity/discontinuity, etc. \n\n3. The experiments may be of interest to domain experts. However, it is not very attractive to the general audience? If the structure is really useful, can it be used to generate new music or find new chemistry laws? As the authors concern about generalizability in the introduction, I believe such reports are necessary. Meanwhile, if the framework is really useful, can it be used in the commonly accepted tasks and be compared with state of the art methods such as the deep learning approach mentioned in the introduction? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "fbmbP-XaE21", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors perform a descriptive analysis of data by attempting to identify elements in the partial ordering of all partitions on the data which admit a compact definition. Compact definitions are those that are formed by composition of a small number of predefined (prior) set of mathematical operations. Projection and lifting operations are defined to relate descriptions of partition cells to one another through rules. The quality of a description is measured by the divergence between the data and the (special) lifting of the rule set, under the constraint that rules satisfy an upper bound on their entropy.\n\nThe approach is general, but due to the intractable size of the information lattice (set of all partitions), simplifications are necessary to produce tractable algorithms. Thus, the authors rely on predefined sets of mathematical operations. This set serves as the defacto language of the summarizations that result. The trouble is that, while the authors describe their method as interpretable, this reviewer finds it very difficult to interpret the summarizations even on the toy problems presented. Moreover, one might refute this difficulty by requiring the user to specify the terms in which they would like to describe the data. Even if a user were capable of doing this, many concepts humans might use are prohibitively difficult to define mathematically, both as a functions and compositions. \n\nGeneral human level summarization of data is a very important task in ML/AI. In the opinion of this reviewer, the community has not adequately solved this problem. The submitted work attempts to move the line forward, but faces a fundamental challenge. We may summarize a set of data by appealing to various groupings of said data (i.e. those that represent fundamental concepts), but we still face the problem of summarizing those groupings. We have only kicked the can down the road so to speak. \n\nThe paper is very dense in terminology, which is sometimes conflicting. The authors clearly state that a signal is a function from data to the reals, but then use the same term to describe images. The authors appear to use both 'X' and 'signal' to describe input data. The very heavy use of appendices appears to be a work-around to stuff a great deal of content into the 8-10 page limitation. It makes the paper feel disconnected. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "afIQKoSffg", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel learning framework called information lattice learning. It is formulated as an optimization problem that finds decomposed hierarchical representations that are efficient in explaining data using a two-phased approach. ILL generalizes Shannon's information lattice and authors demonstrate ILL can be applied to learning music theory from scores and chemical laws from molecular data. This paper is proposing a new research direction and I believe it is worth to be presented. One concern I have is the complexity and scalability of the proposed algorithm.\n\nAuthors emphasize \"small data\", but I don't see why the proposed approach cannot be applied to \"large data\". In page 15, authors mention the worst case complexity of O(2^N). Does it mean the proposed approach works only for \"simple\" examples such as discovering music theory and chemical laws considered in this paper? Can authors elaborate more on the complexity and the scalability issues of their algorithm? Did authors only consider \"small data\" regime due to the scalability problem?\n\nThe definition of signal seems very general and it can even include pmf's. How can we enforce restrictions on signals such as probability simplex?\n\nCan authors comment on how to make a deep learning version of the proposed framework? Say, hierarchical info GAN, hierarchical VAE, etc.?\n\nIt would be interesting to compare their work with existing unsupervised deep learning algorithms that attempt to find disentangled representations.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9gCOdmZ0GA", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose an approach to explain a given signal $\\xi$ (i.e., some function of interest, such as a 2D image, or a probability distribution) by learning simple \"rules\" that can accurately reconstruct it. They demonstrate their approach on a music dataset and a chemistry dataset.\n\nI like the authors' introduction, problem statement, and the somewhat unusual viewpoint and the datasets. Despite this, I cannot recommend this paper for publication. The main issue is that, starting on page 4 and without clear justification, the authors introduce a nearly-impenetrable thicket of mathematical definitions and notation. I would be more accepting of this style if the approach and results absolutely necessitated it. However, it is not clear to me that this is actually the case --- as far as I can tell, what the authors propose to do is basically (1) generate a set of simple features (functions of the input space, created by composing various primitives and symmetries), (2) select a simple subset of these features that explain the target signal $\\xi$ accurately. It seems to me that this kind of approach can be formulated without 90% of the machinery employed by the authors.  Even if it can't, the authors should start with a simple, understandable formulation of their approach, demonstrate the corresponding results, and -- if needed -- make it more complex in order to achieve better results.  Note also that, despite the high complexity, some basic elements of the approach, as are needed to understand the proposed objective function, are left undefined (for example, what does it mean to have the \"Shannon entropy of a rule\", $Ent(r)$, when $r$ is some arbitrary real-valued function?  What is the actual distance measure $\\Delta$ used?)\n\nAnother major issue with this paper is that the author seem largely unaware of the closely related, and very well-established,  theories of induction coming from algorithmic information theory (AIT), as developed by Solomonoff, Chaitin, Rissanen (via minimum description length), and others. It seems to me that the proposed approach, of explaining a signal by finding simple rules that accurately reconstruct it, is basically trying to find a *compressed* version of the signal, i.e., a simple program for the signal, which is example the approach advocated by AIT. The relevant literature is too vast to mention, but one starting point could be \nChater and Vitanyi, Simplicity: a unifying principle in cognitive science?, TICS, 2003.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been evaluated by four expert reviewers resulting in two rejections one marginal score and one acceptance recommendation. The authors provided rebuttals to the critiques, but they did not sway the reviewers' assessments. The prevailing impression is that the work is interesting but perhaps not yet mature nor organized enough to benefit the ICLR audience in its current form. There is also some vagueness left at the conceptual level, e.g. regarding the actual objectives -- some reviewers pointed out confusing entanglement of the concepts of simplicity and interpretability. Nonetheless, the paper presents an interesting work that will benefit from incorporating the constructive feedback received here 
Decision: Reject