Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

I 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?)

Another 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 
Chater and Vitanyi, Simplicity: a unifying principle in cognitive science?, TICS, 2003.

review_title: A highly mathematical proposal for finding simple rules that explain a given signal

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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:

1. 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.

2. 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. 

3. 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? 
review_title: Technical contents can not match motivation

final_score: rating: 7: Good paper, accept
review_content: 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.

Authors 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?

The definition of signal seems very general and it can even include pmf's. How can we enforce restrictions on signals such as probability simplex?

Can authors comment on how to make a deep learning version of the proposed framework? Say, hierarchical info GAN, hierarchical VAE, etc.?

It would be interesting to compare their work with existing unsupervised deep learning algorithms that attempt to find disentangled representations.

review_title: Interesting new direction

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

The 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. 

General 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. 

The 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. 

review_title: A reasonable approach but leaves a lot to be desired.

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