Unsupervised Learning of Categorical Structure

We thank the reviewer for the comments on our manuscript. In addition to the general changes and comments, we highlight changes which address the reviewer's concerns specifically in brown.

(1) Regarding the introduction: We have reworded parts of the introduction (second paragraph) to more clearly motivate our desire for categorical latent variables, and also explicitly mention our contribution of efficient algorithms for SBMF in the final paragraph.

(2) Regarding fidelity: While the recovery of true latent structure is difficult to assess in the case of static word embeddings, our synthetic experiments demonstrate that the algorithm is capable of recovering ground truth. In the case that a representation comes from a neural network or other system, causal interventions are available, and while interesting, we are not investigating that application in this paper.

(3) Regarding Equation 3: We have replaced the optimization equation over pi with the centered MSE loss, which is more directly relevant to the binary version of the algorithm. A step-by-step equivalence between the two is provided in the Appendix as well.

Questions:

Q1: This is an important connection, and the basis of the sparse autoencoders that we now discuss directly in the improved prior work section. Given that we are mostly working with orthogonal encodings, we are actually assuming a different regime than superposition (which allows for correlated coding vectors), so in a sense we are offering a complementary lens for viewing representations.

Q2: We have corrected the unexplained introduction of this concept, and now only reference the size of the analogram (which is explained in the prior section). To clarify what we meant before: a binary embedding can be viewed as a subset of a hypercube, i.e. data are identified with some vertices of the cube. There will be other vertices which do not correspond with the embedding of any data point. Some of these vertices will be `in between' the data points, meaning that a shortest path between the points must pass through them, and those are what we call hidden nodes.

Q3: This is indeed an interesting application, and directly relevant to the concept bottleneck models that we now highlight in the introduction. In short, these models require that a network's output passes through a set of pre-specified concepts (binary nodes) in an effort to make the network more interpretable. Our method, given its speed, could potentially serve as an unsupervised concept layer, although we cannot anticipate how it would interact with the training procedure of a large network. Given that our model is just applying a rotation to the continuous representation, we would expect any benefits to be more in interpretability than in performance or generalization.

We thank the reviewer for the comments on our manuscript

(1) Regarding contribution: In response to the reviewer's concern, we have clarified our specific contributions in an improved introductory section. In short, we propose SBMF as a useful tool for constructing categorical representations, and provide algorithms which handle a broader set of cases than previous ones.

(2) Regarding motivation: Our inclusion of more conceptually relevant prior work, and a new contribution section, can hopefully provide some clarity about the relevance of this work to open problems in the field, such as concept bottleneck models and hashing.

(3) Regarding narrative structure: In our substantial revisions to the text, we have striven for more narrative clarity and consistency, especially in the word2vec section.

(4) Regarding the bigger picture: Related to the previous points, our improved section on prior work now provides a more complete sense of the positioning of our work, and we return to these motivating examples in the improved word2vec section. We have also cleaned up the notation and unnecessary introduction of new symbols, as was pointed out by other reviewers.

Q1: The variables are primarily for interpretation, essentially a non-disjoint clustering. However there are also potential practical uses, such as hashing (as the reviewer mentions) and in quasi-symbolic neural networks like concept bottleneck models.

Q2: In general we can use any positive definite matrix, including the linear kernel of some representation (as we do with word2vec) or a non-linear kernel. We have applied the method successfully to neural data and co-occurrence matrices from , but did not have the space to include it. The extent to which our binary generative model is appropriate for the data can only be assessed by inspecting the quality of the fit, since it is hard to tell from the geometry alone whether it admits a clean factorization.

Q3: This can indeed be seen as a method for locality sensitive hashing, and we now put greater emphasis on connection to prior work on this topic. Beyond its methodological differences, the hashing literature has a very different emphasis, and does not generally take the perspective of latent variable inference or assess the interpretability of the hashes. But it is possible our method would be nevertheless useful as a hashing tool.

Q4: It is not at all a bad thing for neural systems to use continuous representations, as the reviewer points out, it is just difficult to interpret. Our method is tailored for the case where there is some discrete structure which is hidden by a rotation in neural space, of which we provide some examples from the literature in the introduction.

Q5: The weighting of the variables allows us to capture a wider range of continuous geometries, but each variable is still binary in that it can take one of only two values -- rather than $\{0,1\}$, or $\{-1,1\}$, it can be $\{0,\pi\}$, or $\{-\pi,\pi\}$.

We thank the reviewer for the thorough evaluation of our manuscript. In addition to the general changes and comments, those changes addressing the reviewer's concerns are in orange.

(A) Regarding loose and sometimes cumbersome notation: We have substantially refined our writing to introduce fewer symbols and to write equations in terms that are more likely familiar to the average reader. In particular, we have added sentences in Section 2.1 which provide an intuitive introduction to the CKA before the definition. Equation 4 has also been replaced by the those of Hopfield energy function, and while it is still rather dense owing to space constraints, but we feel it is important to include the equations in the main text for reproducibility.

(B) Regarding many perspectives: This is an important narrative critique, and we have addressed it in part by substantially rewriting section 4. We (1) include a more explicit discussion of the geometry of the word2vec representations and how it relates to the discovered concepts through sparsity (Fig. 4b) and clarifying where the word2vec falls in the spectrum of low-rank to sparse concept spectrum of the synthetic tasks; (2) clarify the purpose of the plot in Fig. 4h; and (3) include a new analysis which is more clearly categorical in nature.

(C) Regarding informal language: We have corrected instances of imprecise language, including those explicitly mentioned by the reviewer.

(D) Novelty and contribution: Our rewritten prior work section, and new contributions section of the introduction now include more explicit connections to previous work, including the relevant work on tensor product representations of which we were not previously aware, and we highlight the ways that ours is conceptually and practically different. The practical contributions are bolstered by our much improved refinement algorithm.

(E) Discussion: We have replaced the introduction of this concept with a more general summary of our results and the novelty of our approach to this problem.

Questions:

Q1: The analogram provides a way of visualizing the discovered concepts, essentially saying ``these four words are arranged as a square with some word-specific deviations''. By construction, the distances on the graph match the Hamming distance in the binary embedding, so an analogram can be used to quantitatively inspect the distances. The binary embedding can also be recovered from the graph by cutting at all edges with the same color, which will result in a partition of the nodes. The graph is unfortunately not always as useful as a dendrogram in hierarchical clustering, because it often cannot be plotted without lots of intersections.

Q2: We hope that the new, more categorical analysis of the word2vec representations helps to clarify the utility of the categorical representations. While it is somewhat beyond the scope of this methods paper, we also expect that this technique could be useful as an unsupervised version of the ``concept bottleneck model'' which we now mention in the introduction -- briefly, the idea there is that a model's output is constrained to be computed as a function of some specified concepts, so that the model is ultimately more interpretable.

Regarding the complexity, it took around 2 hours on a laptop to fit 1000 concepts on the 3841 words, using a relatively slow annealing schedule. It can take half as long with a faster annealing schedule (and a worse fit).

We thank the reviewer for the comments on our manuscript.

(1) Regarding contributions: We agree that the paper suffered from lack of explicit discussion of the contributions, and so we have added a section about this to the introduction.

(2) Regarding notation: Owing to our new algorithm formulation, the conflicting use of some letters has been resolved (although we still use $p_0$ to refer to a probability distribution, which we hope is clear from context), and we have endeavoured to clean up our notation in other parts of the paper by limiting the introduction of new symbols.

Q1: While we do not have the space to include it in this paper, we have applied our method to neuroscience data (electrophysiology recordings) and to co-occurrence matrices from competitive pokemon games. A future version of this paper could highlight those analyses at the expense of some of the technical and theoretical parts.

Q2: In the general case, unfortuantely we cannot expect to get around the NP hardness of the problem, in the sense of having an efficient algorithm with guarantees on solution quality. Of course this does not preclude good heuristics, as we have shown ours to be one. However, the regularization can help to mitigate the non-identifiability, by selecting for (in our case) the sparsest solution among the many equally good ones.

Q3: The reviewer is correct to point out this statement, which was based on our experience with the solution quality achievable in smaller datasets but not on this one. We have indeed done better with our new algorithm (by about 0.01), but it is still an imprecise statement which we have removed.

We thank the reviewer for the thorough evaluation. In addition to the general changes in blue, changes which directly address these points are written in red.

(1) Regarding the justification of the sparsity regularization: We agree that a more quantitative argument would be more compelling, unfortunately it was difficult to arrive at a useful result. For now, we have given a general intuitive argument about the size of the sparse solution space being generally smaller than the dense solutions (i.e. there are n-choose-k concepts with k nonzero elements). We have also included a more broad appeal to sparsity as a useful inductive bias, based on compressed sensing and some results in cognitive science.

(2) Regarding the scalability: We hope that the improved refinement algorithm can address some of the concerns about scalablity, as it now scales competitively with two-layer autoencoders (with better results).

(3) Regarding subjectivity: We agree with this general criticism of interpretability methods, and that ours, like those, can require a secondary method for interpretation. We note that the output of our algorithm can be used in the same way as those of a sparse autoencoder, e.g. asking a language model to interpret (we now mention this is section 4). We also offer our complementary analysis methods in section 4 as new interpretability tools for binary embbeddings in particular.

(4) Regarding comparison: This was indeed an important analysis missing from our previous version, and we have addressed it by adding two baselines.

Q1: Having addressed the main scalability bottleneck, we nevertheless still have trouble on very large datasets (>10000 or so). Three ways we can see to improve this are (1) better code, it is written in python which brings a big penalty from the for loops involved; (2) batching, i.e. computing the updates with a subset of the data; and (3) pre-clustering, i.e. reducinig the dataset size with a disjoint clustering algorithm.

Q2: We thank the reviewer for pointing us to this very relevant paper, as it has encouraged us to discuss that literature more. We draw a connection in the second paragraph of the prior work section.

Q3: It is good to point out that sparsity is not always tied to complexity. They are related, because the ``hidden'' nodes of the graph come from the intersection of each item's categories, e.g. if item X has labels {a,b} and item Y has {b,c}, then there will be a hidden node with labels {b}. If items have sparser labels they will have fewer intersections on average, but there are exceptions. We have also tried directly penalising label intersections, and found it more generally effective, but it has a more complicated implementation which we did not have the time to fully put into practice.