Learning Structure from the Ground up---Hierarchical Representation Learning by Chunking
Authors: Shuchen Wu
Noemi Elteto
Ishita Dasgupta
Eric Schulz
Venue: ICLR 2022 Submitted (2022)
Keywords: representation learning
interpretability
cognitive science

Abstract: From learning to play the piano to speaking a new language, reusing and recombining previously acquired representations enables us to master complex skills and easily adapt to new environments. Inspired by the Gestalt principle of grouping by proximity and theories of chunking in cognitive science, we propose a hierarchical chunking model (HCM). HCM learns representations from non-i.i.d sequential data from the ground up by first discovering the minimal atomic sequential units as chunks. As learning progresses, a hierarchy of chunk representation is acquired by chunking previously learned representations into more complex representations guided by sequential dependence. We provide learning guarantees on an idealized version of HCM, and demonstrate that HCM learns meaningful and interpretable representations in visual, temporal, visual-temporal domains and language data. Furthermore, the interpretability of the learned chunks enables flexible transfer between environments that share partial representational structure. Taken together, our results show how cognitive science in general and theories of chunking in particular could inform novel and more interpretable approaches to representation learning.

Under review as a conference paper at ICLR 2022
LEARNING STRUCTURE FROM THE GROUND UP- HIERARCHICAL REPRESENTATION LEARNING BY CHUNKING
Anonymous authors Paper under double-blind review
ABSTRACT
From learning to play the piano to speaking new language, reusing and recom- bining previously acquired representations enables to master complex skills and easily adapt to new environments. Inspired by the Gestalt principle of grouping by proximity and theories of chunking in cognitive science, we propose hierarchi- cal chunking model (HCM). HCM learns representations from non-i.i.d sequential data from the ground up by first discovering the minimal atomic sequential units chunks. As learning progresses. hierarchy of chunk representation is acquired by chunking previously learned representations into more complex representations guided by sequential dependence. We provide learning guarantees on an idealized version of HCM, and demonstrate that HCM learns meaningful and interpretable representations in visual, temporal, visual-temporal domains and language data. Furthermore, the interpretability of the learned chunks enables flexible transfer be- tween environments that share partial representational structure. Taken together, our results show how cognitive science in general and theories of chunking in particular could inform novel and more interpretable approaches representation learning.
INTRODUCTION
The last decade has witnessed a meteoric rise in the abilities of artificial systems, in particular deep learning models (LeCun et al. 2015). From beating the world champion of Go (Silver et 2016) to predicting the structure of the human proteome @umper et al., (021), deep learning models have accomplished impressive end-to-end learning achievements. Yet, researchers were quick to point out shortcomings (Marcus 2018 Lake et al.) 2017). Two such shortcomings concern the hierarchical structure and interpretability of the representations learned by neural network architectures. Specif- ically, deep learning models suffer from lack of interpretability since ANNs are sub- sub-symbolic, nested, non-linear structures. This means they the way predictions are generated can difficult to understand (Samek et al.) 2017 Ribeiro al. 2016 Doshi Velez. & Kim 2017). Furthermore, deep learning models can also struggle to learn hierarchical representations a altogether (Lake & Baroni, 2018 Fodor & Pylyshyn| 1988). To address these shortcomings, it has been suggested that machine learning researchers could seek inspiration from cognitive science and construct models that resem- ble the hierarchical and interpretable representations observed in human learners (Chollet 2017
Lake et al. 2015).
We take inspiration from the cognitive phenomenon of chunking and the Gestalt principle of group- ing by proximity. To get an intuition for chunking, try to read through the following sequence of letters: DOFFKIKIKDFFFFKKKKDD"""" Upon reaching the end, if you were tasked to repeat the letters from memory, you might recall fragments of the sequence such as "DF" or "JK". By parsing the sequence of letters only once, one detects frequently occurring patterns within and memorize of them together units, i.e. chunks. Chunking has been observed in a range of sensory modalities. We perceive units and structures when learning a language (Perruchet et al.) 2014: McCauley & Christiansen 2017). in action sequences (Penhune & Stecle| visual structures Hinton 1179); Brady et al. (2009);[Egan & Schwwrtz/ 1979). The extracted chunks
al. 1983). and in
have been argued to facilitate memory compression (Gobet 2001 Miller 1956). compositional

---

Müssgens & Under review as a conference paper at ICLR 2022
a) Generative Hierarchy
b) Chunking Decision
Marginal
Transition
High
2
d=5
Low
c) Chunking
Nonindependent Transition Entries
C₁
CR
Training Sequence:
C7
d) Gradual Representation Build-up
e) Final Chunk Hierarchy
60
T= 100
t= 150
Simple
Intermediate
Complex
Figure 1: Schematic of the Hierarchical Chunking Model. a) Example of hierarchical model generating training sequences. b) Intermediate representation of learned marginal and transition matrices. The most frequent transition that violates the independence testing criterion is marked in red and can be turned into new chunk. c) HCM combines the two chunks and eR to form new chunk. d) As HCM observes longer sequences, gradually learns hierarchical representation of chunks. e) HCM arrives at the finally chunk hierarchy isomorphic to the generative hierarchy.
generalization (Schulz al., 2017), predictive processing (Koch Hoffmann 2000 Ullén 2015), and communication (Schulz et al. 2020).
In the current work, propose hierarchical chunking model (HCM) that learns chunks from non-i.i.d sequential data with a hierarchical structure. HCM starts out learning an atomic set of chunks to explain the sequence and gradually combines them into increasingly larger and more complex chunks, thereby learning interpretable hierarchical structures. The output of the model dynamical graph that is trace of the evolving representation. The resulting representations are therefore easy to interpret, and flexibly reusable (e.g. we can choose to re-use specific parts). We derive learning guarantees on an idealized generative model and demonstrate convergence on sequential data coming from this generative model. Furthermore, we show that our model can benefit from having learned previous structures with shared components, leading to flexible transfer and generalization. Finally, we demonstrate that HCM can return interpretable representation in discrete sequential, visual, and language domains, in several small-scale experiments. Taken together, our results show how cognitive science in general and theories of chunking and grouping by proximity in particular can inform novel and more interpretable approaches to representation learning.
2 HIERARCHICAL CHUNKING MODEL
When talking about chunks sequence, a chunk is defined unit created by concatenating sev- eral atomic sequential units together. Take the training sequence shown in Figure as example. The sequence consists of discrete, size-one atomic units from an atomic alphabet Ag: in this case As {0, 1, A chunk is made up of combination of one more atomic units in Ag A00. 0 denotes an empty observation in the sequence.
Intuitively, if the training sequence contains inherent hierarchical structure, then there are patterns which span several sequential units sharing these internal structures, like repeated melodies and sub- melodies in piece of music. If the pattern occurs in the sequence, observations between sequential units within the pattern will be correlated. In this case, chunking patterns within a sequence as units simplifies perceptual processing in the sense that the sequence be perceived one chunk
2

---

More formally, HCM acquires a belief set B of chunks, and uses chunks from the belief set to parse the sequence one chunk time. HCM assumes that sequence is generated from samples of independently occurring chunks with probability of Pa(c) evaluated on the belief set Under review as a conference paper at ICLR 2022
time, instead of one sequential unit at time. Furthermore, the acquired "primary" chunks serve as building blocks to discover larger chunks that are embedded within the intricate hierarchy of the sequential structure.
B. The probability of observing sequence of parsed chunks ci2 C2, ..., Co can be denoted as P2c,, CN) Ie, g2 (c()). Chunks as perceiving units serve as independent factors that disentangle observations in the sequence.
From the beginning of the sequence, HCM 'perceives" sequential units one chunk at a time, in other words, the training sequence parsed by HCM into chunks. At every parsing step, the longest chunk in the belief set that is consistent with the upcoming sequence is chosen to explain the up-coming sequential observations. The end of the previous chunk parse initiates the next parse.
Observing hierarchically structured sequence as illustrated in Figure HCM gradually builds up a hierarchy of chunks starting from an empty belief set. It first identifies set of atomic chunks to construct its initial belief set IB. Initially, these will be chunks of length one, yielding one-by-one processing of the primitive elements.
For one belief set B, HCM keeps track of the marginal parsing frequency ((c) for each chunk ca in IB, a vector with size [B] and the transition frequency T between chunk e; followed by chunk cj. as illustrated in Figure Tp. Entries in M and T are used to test the hypothesis that consecutive chunk parses have a correlated consecutive occurrence within the sequence. If two chunks CL and eR have significant adjacency dependence based on their entries in M and T, they are chunked together to become ey @ en. which augments the belief set B by one. One example of chunk merging is shown in Figure DC.
There are two different versions of HCM. The Rational Chunk Learning HCM produces chunks in an idealized way which we use to study learning guarantees. The online version of HCM is an approximation to the rational HCM that can be adapted to different environments and processes sequences online. Pseudo-code for both algorithms can be found in Algorithm and in the SI.
Rational Chunk Learning: HCM as an Ideal Observer The model is initiated with an empty belief set, and it first finds a minimally complete belief set after the first sequence parse. In each iteration, the entire sequence is parsed to evaluate M and T. which are used to find consecutive chunk parses in the existing belief set fulfilling the dependence testing criterion. From these depen- dent chunk pairs, the pair with the largest estimated joint probability is combined into a new chunk. The new chunk enlarges the belief set by one. The chunks in the new belief set are used to parse the sequence in the next iteration. This process repeats until all of the chunks in the belief set pass an independence testing criterion.
Online Chunk Learning The online chunk learning HCM approximates the ideal observer HCM by learning new chunks when the training sequence is processed online. To have a feature that encourages adaptation to new environmental statistics, entries in M and T can be subject to memory decay. We use the ideal observer model to demonstrate learning guarantees, but use the online model to learn representations in realistic and more complex set-ups.
2.1 HCM BUILDS REPRESENTATION FROM THE GROUND UP
As HCM learns from a sequence, starts with no representation and gradually builds up the rep- resentations which can be readily interpreted at any learning stage. The representation can be de- scribed by chunk hierarchy graph 9 with the vertex set being the chunks and edges pointing from chunk constituents to the constructed chunks. Shown in Figure [ is the gradual build-up of one such chunk hierarchy graph the model learns from a training sequence coming from the genera- tive hierarchy displayed in Figure Dp. At = 10, HCM learns only the atomic chunks, at f = 60, HCM has already constructed two additional chunks; when t 100, two more additional chunks are constructed based on the previously acquired chunks, and at t = 150, HCM arrives at the final chunk hierarchy.
3

---

Under review as a conference paper at ICLR 2022
a)
3
5
d
diveggnnce
08
Model
06
HICM
RNN
0.4
02
d-3
1000
2000
5000
1000
2000
3000
1000
2000
3000
Training Longth
Training Longth
Training Longth
Figure 2: a) Example graph generated from the hierarchical generative model with depth of d = 3. b) Learning performance of HCM and RNN with increasing training length and for different depths. Performance averaged over 30 generratd graphs.
3 HIERARCHICAL GENERATIVE MODEL
To study learning guarantee of the HCM, generative model with random hierarchy of chunks is constructed. The relation between chunks and their constructive components in the generative model deseribed by chunk hierarchy graph Ga with vertex set VA and edge set EA.- One example is illustrated in Figure h Ad is the set of chunks used to construct the sequence. The depth d specifies the number of chunks created the generative process.
Starting with an initial set of atomic chunks Ag, at the i-th iteration, two chunks cz, eR are randomly chosen from the current set of chunks A, and are concatenated into new chunk ez &CR, augmenting A by one to A,-1. Mcanwhile, an independent occurrence probability is assigned to each chunk under the condition that the probability of occurrence for every new chunk e in the construction process evaluated on the support set A. carries the largest probability mass.
To generate sequence from a constructed hierarchical graph, chunks are sampled independently from the set of all chunks and appended after each other, under the constraint that no two chunks with a child chunk should be sampled consecutively.
3.1 LEARNING GUARANTER
As the length of the sequence approaches infinity, HCM learns hierarchical chunking graph & isomorphic to the generative hierarchical graph G.
Theorem:
We approach this proof by induction. Further details can be found in SI. Base step: The first step of the rational chunking algorithm is to find the minimally complete atomic set of chunks form its initial belief set, This procedure guarantees that Čo Go. Additionally, the probability mass of the learning model at step 0 and the generative model at step 0 is asymptotically the same as the sequence length approaches infinity. Induction hypothesis: Assume that the learned belief set B, at step i contains the same chunks as the alphabet set A; in the generative model, the chunk combination pair with the biggest evaluated joint occurrence probability violating the independence test is picked to be concatenated into chunk to extend the belief set: this chunk is the same chunk node created by the hicrarchical generative model. End step: The chunk learning process stops once the independence criterion is passed. This is the case once the chunk learning algorithm has learned a belief set Bd- = Add-
3.2 LEARNING CONVERGENCE
HCM's learning performance with increasing sequence length is evaluated and shown in Figure 2 For this, HCM was trained on random graph hierarchies constructed from the hierarchical generative model over 3000 trials while also varying the depth Figure 2h displays an example of a random generative hicrarchy with depth of d = 3. We used the Kullback-Leibhe divergence to evaluate the deviation of HCM's learned representations from the generative hierarchical model. This was done by using HCM's representation to produce "imagined" sequences, which were then compared to the ground truth probability for each chunk in the used generative model. Figure Zp shows the KL-divergence between the learned and ground-truth distribution for different depths d of the gener- ative graphs. For each depth, the KL-divergence is evaluated on 30 random generative models with sequence length increasing from 50 to 3000 in each model. Overall, the KL-divergence decreased as the length of training sequence increased and converged with larger training sequences. This shows empirically that HCM learns representations bearing closer resemblance the generative model.
4

---

Under review as a conference paper at ICLR 2022
a) Learned Represemaation
bi Factitaative Enstronment
<) Facilitation
di Interfering Emvioomment
Interference
68
divegence
39hwd Typo
Tyde
Figure 3: a) Example of representation learned by an HCM. b) An environment facilitative to the learned representation. Gray shadows mark the chunks that can be directly transferred. Average performance over the first 500 trials after environment change in the facilitative environment. d) In- terfering environment. Gray shadows marks chunks that the learned representation needs to acquire from scratch. e) Average performance over the first 500 trials after environment changes into an the interfering environment.
We used the same sequences to train a 3-layer Recurrent Neural Network (RNN) with 40 hidden units and the same method to measure the Kl.-divergence by using "imagined" sequences produced by the RNN evaluated on the support set of the generative hierarchy. As the length of the train- ing sequence increased, the Kl.-divergence also converged but much slower rate. Note that HCM's competitive advantage increased further the depth of the generative hierarchy increased. Thus, HCM learns quickly about the hierarchical generative model and does so faster than a neural network.
3.3 HCM PERMITS TRANSFER BETWEEN ENVIRONMENTS WITH OVERLAPPING STRUCTURE
After training on a sequence, HCM acquires an interpretable representation. Knowing what the model has learned enables us to directly know what type of hierarchical environment would facilitate or interfere with the learned representations. This is impossible to do using standard neural networks because we generally would not know what representation they have learned, and therefore do not have fine-grained control over retaining or removing parts of it.
More formally, two HCM models might have acquired different hierarchical chunking graphs G. and 9, from their past experience. These might lie on the graph construction path (Go, G1, 92. Ga)- The HCM with chunk hierarchy graph 'closer' to the ground truth chunk Ga on the path, takes fewer iteration to arrive at Ga. This also applies when the chunk hicrarchies starting out are not along the graph construction path but only showing partial overlap.
Similarly, the chunk hierarchy G; learned by an HCM might facilitate its performance in a new environment where G; lies along the graph construction path to the true Ga. i.c. there is partial overlap between the chunk hicrarchies. We demonstrate this in Figure 3 Here, HCM was trained on random hierarchical generative model and acquired the representation shown in Figure Bp. Knowing this representation, we also know that an environment with a hierarchical generative graph as shown in Figure 3p allows for positive transfer, i.e. the HCM that already contains the chunk hierarchy Figure 3h would learn faster than naive one by transferring its previously learned chunks. As shown in Figure 3p. the trained HCM learns faster than naive HCM which had to learn about the structure from scratch.
Vice versa. we might have situation in which transfer is detrimental. For example, there is no overlap in the chunk hierarchy learned by the HCM in Figure 3a with the graph shown in Figure Bd. The shaded chunks need to learned anew by the HCM trained on Figure 3p. yet the previously acquired chunks might mislead HCM causing it to adapt to the new environment more slowly. As result, the performance of the pre-trained HCM suffers more from an interfering environment than a naive HCM (Figure 3b). This is similar to catastrophic interferences in neural networks (Sharkey & Sharkey 1995), where performance on one task interferes with others. The advantage of the HCM that with visibility into the chunks leamned, will be facilitative or interfering. This means that we can examine whether to re- use the previously learned chunks, or to start from scratch with naive model.
have better priori sense of whether transfer
5

---

Under review as a conference paper at ICLR 2022
a)
Visual Hierarchical Model
b)
Simple
Intermediate
Complex
Sequence:
Figure 4: a) A designed visual hierarchical model where elementary components compose more complex images. b) Initial, intermediate, and complex chunks learned by HCM trained on sequences of images generated by the visual hierarchical model.
4 GENERALIZING TO VISUAL TEMPORAL CHUNKS VIA THE PRINCIPLE OF PROXIMAL GROUPING
Humans are not only able to identify sequential chunks but also to find structure in visual- visual-temporal stimuli and group visual points as a whole. For example, despite the fact that our retina receives pixel-wise visual inputs that vary across temporal slices, we are able to perceive complex moving objects. The Gestalt principle of grouping by proximity states that objects that are close one an- other appear to form groups (Wagemans et al. 2012). This principle has been argued to play key role human perceptual grouping (Compton & Logan 1993) and benefit working memory (Peter- son & Berryhill 2013) and the reduction of visual complexity (Donderi 2006). Indeed, in humans and other animals, learning of adjacent relationships prevails over non-adjacent ones (Malassis et al,, 2018). Therefore, the adjacent dependency structure be seen the primary driver of chunking in visual temporal domains (Froyen et al., 2015). To emulate this ability of chunking via proximal grouping in visual temporal perception, we extend HCM also learn visual temporal chunks.
Visual temporal chunks not only subsume temporal length but also varying visual slices in each tem- poral slice. One can imagine visual temporal chunks as having 3D shape the first two height and width dimensions are the visual part of the chunk, the length of the object is the temporal part, made of stacked visual-temporal pixels. Within each temporal slice the visual features identified by the chunk. Since nearby points are more likely to be in the same chunk, this assumption is an implementation of the principle of grouping by proximity in the visual-temporal domain. As the model iterates through data across its temporal slice, the chunk that attains the biggest visual tempo- ral volume chosen to explain parts of the visual-temporal observations. Multiple visual temporal chunks can be identified to occur simultancously. Starting at the visual temporal time point marked by the previous chunk, chunks are identified and stored in M. The transition matrix is modified account for the temporal lag-difference between adjacent chunk pairs and records the frequency that one chunk transitions into another one with a given time-lag. every time when pair of adjacent chunks are identified, chunks that violate the hypothesis test grouped together to augment the belief set which is then used to parse future sequences.
hypothesis test is conducted
LEARNING PART- WHOLE RELATIONSHIP BETWEEN VISUAL COMPONENTS
We let HCM learn chunks in a visual domain by learning from sequence of images. To this end, hierarchical generative model in the pixel-wise image domain shown in Figure 4 was constructed to test HCM's visual chunking ability. Specifically, a set of elementary visual units in the lowest level of the hierarchy are combined to construct intermediate and more complex visual units higher up in the hierarchy. An empty image is included to denote pauses. All of the constructed elements draw from Dirichlet flat distribution. To
in the hierarchy occurred independently according generate the sequence which was used to train HCM, images in the hierarchy were sampled from the generative distribution and appended to the end of the sequence. In this way, despite the visual correlations in each image described by the hierarchy, each image slice was temporally independent from other slices.

---

Under review as a conference paper at ICLR 2022
Squid Movement GIF
Visual Parts:
b) Visual Temporal Parts:
Figure 5: a) A GIF of a moving squid used as sequence to train HCM. b) Examples of temporal chunks learned by HCM. e) Examples of visual chunks learned by HCM.
HCM learns hierarchy of visual chunks from a sequence of visually correlated but temporally independent images sampled from the visual hierarchical model. Shown in Figure are the chunk representations learned by HCM different stages. Having no knowledge about the image parts before starting to learn, HCM acquires the individual pixels chunks to explain the observations. As HCM proceeds with learning, visual correlations among the pixels are discovered and larger chunks formed. As the number of observations increases, the model learns more sophisticated yet still interpretable chunks.
4.2 LEARNING VISUAL-TEMPORAL
TEMPORAL MOVEMENT HIERARCHIES
Instead of seeing one image after another sampled from independent, identically distributed dis- tribution, real world experiences contain correlations both the visual and temporal dimension. From observing object movements across space and time, the visual system learns structures from correlated visual and temporal observations, decomposes motion structure and groups moving ob- jects together whole (Bill et al. 2020). To emulate this type of environment a learning task, an animated GIF squid swimming in the sea as shown in Figure 5p was used as a visual-temporal sequence train HCM. As learning advances, HCM learns chunks spanning both the visual and temporal domain. Examples of such visual-temporal chunks are shown in Figure 5p and c. There visual-temporal chunks that mark movements of tentacle and the rising-up motion of bubble. Additionally, there are visual chunks that resemble part of the squid's eye and face.
5 LEARNING CHUNKS FROM REALISTIC LANGUAGE DATA
We so far have only shown demonstrations of HCM learning chunks on simple sequences. Thus, step further is to run HCM real world datasets that contain complex hierarchical structures. One immediate testbed containing such structures is natural language. To this end, we trained HCM learn chunks on the first book of The Hunger Games.
HCM starts with learning individual English letters and punctuation. After having seen 10,000 characters of the book, HCM acquires frequently used chunks that resemble common English pre- and suffixes such as "ity", "ing", "re", and "ith": definite and indefinite articles such as "a", "an", "the": conjunctions such as "and", "but", "that", and "as"; prepositions such as "of, "to", "in", "at". variants of "is". " "are", "was": and pronouns such as "he", "my", "me", "we", "she".
After having seen 100,000 characters of the book, HCM learns intermediate chunks that include various commonly used verbs such "come", "sing". "leave", "try"; nouns such "bed", "day". "mother"; common word combinations such as "in the". "lose to", "the wood". Additionally, HCM has acquired words specific to The Hunger Games such "prim", "death", "hunger", and "district 12"
After having 300,000 characters of the book, HCM leams complex phrases from the previously learned words, such as the commonly used phrases "it is not just", "in the school", "our district", and "cause of the".

---

Under review as a conference paper at ICLR 2022
Table I:
Example Chunks Learned from The Hunger Games
Simple Chunks
ann,, in 'be', at', "me', 'le', "a'' 'a', 'ar', 're', 'and" 've', "ing" 'on'. 'st', 'se", 'to 'oo" 'he", "my" ' 'te', 'pe", "ou", 'we', 'ad', dee, 'li', 'the', 'ce", 'is', 'a''s.' 'il', 'ch', 'al', 'no', "she', 'ing', 'am'. 'ack', 'we'. 'raw", 'on the", "day". "ear', "oug'. "bea', 'tree", 'sin', 'that', 'log', 'ters', 'wood', 'now", "was', 'even', 'leven', "ater', 'ever', 'but', 'ith', "ity" "this', "pas', "eak', 'if", 'sing'. 'bed'. "men". 'raw", 'ay'. "in the", 'link', 'for', onee", 'the wood', 'bell', 'other', ... "lose to', 'hunger', 'mother', 'death'. 'would'. 'district 12', 'try'. 'under', 'prim', 'beg'. 'then', 'into', "gale', 'read'. 'come', 'he want', 'leave', 'where', 'older', 'says', "might', 'dont', 'add', 'know', 'man who', 'of the"
Intermediate Chunks
Complex Chunks
'out of", , 'it out', "our district', 'capitol', 'raaping. 'fair'. 'berries', 'the last', 'fish', 'again', aas well', 'the square', 'scomers' 'fully', but the :. 'in the school', "at the', 'you can', 'tribute', 'to remember', 'it is not just', 'I can', 'peace', 'feel', 'ouu have to', know', 'bother', 'in our', 'kill', 'cause of the', 'the pig', 'to the haker', 'I have', 'what was'
6
RELATED WORK
Our model is successor to decades of work on different approaches to chunk learning. In cognitive science, researchers have put forward models that produce qualitatively similar chunks as humans learning a natural or artificial languages (Servan- Sehhen-S & Anderson, 1990. Perruchet & Vinter, 1998), as well models that can extract chunks from visual inputs (Mareschal & French| [016)) HCM can be viewed as a principled version of these earlier cognitive models because it uses hy- pothesis testing in its decision chunk elements together instead of using chunking heuristics. Therefore, HCM comes with learning guarantees for a fairly general class of hierarchically struc- tured environments. Additionally, HCM extends past cognitive models to the higher dimensional domain of visual-temporal chunking.
The primary approach to chunk learning in the language domain were n-gram models, dating all the way back to |Shannon (1948). An n-gram model learns the marginal probabilities of all chunks of size n. A major limitation of this approach is that the number of chunks grows exponentially as a function of chunk length. For instance, with an alphabet of 26 letters, the number of possible 5-letter words already goes beyond 10 million. Due to the large vocabulary size, building word-level n-gram models is virtually unfeasible. To this end, a Bayesian non non-parametric extension of n-gram models has been put forward (Thh 2006). A Bayesian non-parametric n-gram model builds up structure as evidence is accumulated. That is, it flexibly reduces to I-gram model if chunks are not present or 'opens up' higher and higher n-gram levels depending on the size of chunks. Teh (2006) 's model is different from HCM in several regards. Instead of using the chunks to 'look forward' and parse the sequence in large steps, it 'looks back' and predicts only one element conditioning on the context of the previous elements. Then, instead of storing an explicit bag of chunks, it represents a chunk distribution weighted by evidence. For prediction, it smooths over the evidence of all chunks that are consistent with the current context. A shortcoming of Tch (2006)'s 's model and n-gram models in general is that they do not leverage the concatenation process observed in humans but the chunks are built up primitive element-wise.
Hierarchical hidden Markov models (Fine et al. 1998) were developed in similar vein, extend- ing hidden Markov models to be able to capture multi-scale sequential structure. Although these models are able to capture larger patterns than non-hierarchical versions while maintaining the com- putational tractability of simple Markov processes, they still lack the adaptive recombination and reuse of pre-existing components. Fragment grammars (O'Donnell et al., (009) address this by bal- ancing the creation and re-use of chunks by Bayesian principles, while also preserving the symbolic interpretability. However, fragment grammars are intractable and their inference is exceptionally costly.
In the of deep learning, both natural language processing and image processing became in- creasingly dominated by neural networks, with one of their primary tasks being the extraction and Ortmann 2021). Commonly, these so-called
prediction of chunks (Zhai et al. 2017 Si et al. 2020
8

---

Under review as a conference paper at ICLR 2022
sequence chunks are used units of segmentation for other downstream tasks such as text trans- lation. However, in these approaches, the architecture needs to be pre-specified before training as compared to HCM, where no such specification is required. HCM can therefore be seen an interpretable and transparent alternative to neural networks for some of these tasks.
A final related line of research attempts learn explicit representations by inducing programs (Lake et al. 2015). Fore example, in a recent approach to this challenge, the interpretable structures re- turned by program induction algorithms was combined with deep neural network to learn mean- ingful representations from data (Eliis et al. 202T). Yet in these approaches the retrieved represen- tations are highly dependent on the initial set of building blocks which are usually specified by the experimenter. HCM, in comparsion, is tank-agnostic and requires no primitive program description.
DISCUSSION
We have proposed the Hierarchical Chunking Model (HCM) as sennttively-inspire method for learning representations from the ground up. HCM starts out by learning atomic units from se- quential data which then chunks together, gradually building up a hierarchical representation that can be expressed dynamical and intepretable graph. We have provided learning guarantees for an idealized version of HCM, shown how HCM's interpretability can facilitate generalization, and demonstrated that HCM learns meaningful representations from visual, temporal, visual-temporal, and language data.
Although we have showcased HCM's abilities across set of diverse experiments, some challenges remain. First of all, HCM is currently not computationally efficient, such that we needed to run the online version for most of the presented tasks. There several directions that could enhance HCM's computational efficiency. One method to speed up learning could be to stitch multiple chunks together in one decision. Another direction could be have the chunk decision process between all of the acquired chunks separated from the process of parsing observations, which could be used for parallelized implementations. We believe that scaling HCM up will be beneficial to learn in increasingly more complex data sets than the ones we have applied here.
Secondly, all patterns of chunks in the current project came from adjacent events the sequences. This feature was inspired by the Gestalt principle of grouping by proximity. Yet many patterns ob- served in natural data sets might exhibit non-adjacent dependencies in space or time. The adjacency assumption therefore limits the model from detecting such patterns. How to relax the adjacency assumption as grouping criterion to allow for non-adjacent relationships to chunked together remains an open challenge. Furthermore, HCM currently assumes that there is hierarchy of chunks which occur independently in the observational sequence. This set-up was intended to a simpli- fying assumption for a first approach toward building cognitively plausible hierarchical chunking model. Nonetheless, our approach can and should be extended to more sophisticated assumptions such as higher order Markovian dependencies between chunks. Finally, HCM passes visual data "as is" and does not take into consideration any additional assumptions about visual inputs such as translation or rotational symmetries, which humans can detect when perceiving visual structures.
There are also several avenues for future investigations. One immediate step is to run HCM on other, more complex data sets such as musical scores, neural data, and large natural language corpora, to name but a few. Furthermore, we intend to not only run HCM on raw visual inputs directly but also to employ neural networks to compress inputs into latent space and then train HCM on these latent dimensions (Franklin et al. 2020). Additionally, one could also use deep learning models to label parts of objects and then train HCM on the movements of these labelled parts (Insafutdinov et al.) 2016). Finally, we are currently only testing for independence when deciding chunk, although other statistical tests are conceivable. One general class of tests could be to assess whether not chunks structure to explain the sequential, observational data Heinze-Denn et al. (2018). This would make HCM useful model of causal representation learning (Schölkopf al. 2021
whether not to
causally related with each other, in attempt to find the best causal

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
Detailed information about the HCM algorithm, proof, generative model, independence test and experimental details and results can found in the supplementary information section. The code used for the algorithm and experiments will be available as comment to the reviewers and area chairs as a link an anonymous repository as soon as discussion forum for all submitted papers is open.
REFERENCES
Johannes Bill, Hrag Pailian, Samuel Gershman, and Jan Drugowitsch. Hierarchical structure is employed by humans during visual motion perception. Proceedings of the National Academy of Sciences, 117(39):24581 24589, 2020. ISSN 0027-8424. doi: 2..073/pnas.200086111 URL
https: www pwws..na............. /ttp://onte///11//3/1/111 39//2//27/9//
Timothy Brady, Talia Konkle, and George A. Alvarez. Compression in Visual Working Mem- ory: Using Statistical Regularities to Form More Efficient Memory Representations. Journal of Experimental Psychology: General, 138(4), 2009. ISSN 00963445, doi: 10.1037/a0016797.
Francois Chollet. Deep Learning with Python. Manning Publications Co., USA, 1st edition, 2017.
ISBN 1617294438.
Brian J Compton and Gordon D Logan. Evaluating a computational model of perceptual grouping by proximity, Perception & Psychophysics, 53(4):403-421, 1993.
Don C Donderi. Visual complexity: review. Psychological bulletin, 132(1):73, 2006.
Finale Doshi- Velez and Been Kim. Towards rigorous science of interpretable machine learning.
arXiv preprint arXiv:/702.0800 7702008608 2017.
Dennis E. Egan and Barry J. Schwartz. Chunking in recall of symbolic drawings. Memory &
Cognition, 7(2), 1979. ISSN 0090502X. doi: 10.3758/BF03195595
Kevin Ellis, Catherine Wong. Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt,
Luc Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. Dreamcoder: Bootstrapping in-
ductive program synthesis with wake-sleep library learning. Proceedings of the 42nd ACM SIG-
PLAN International Conference Programming Language Design and Implementation, PLDI 2021, pp. 835-850, New York, NY, USA, 2021. Association for Computing Machinery. ISBN
9781450383912. doi: 10.1145/3453443.34440000 URL 34534B3.345400
Shai Fine, Yoram Singer, and Naftali Tishby. The hierarchical hidden markov model: Analysis and applications. Machine learning, 32(1):41 1998.
Jerry A. Fodor and Zenon W. Pylyshyn. Connectionism and cognitive architecture: A critical anal- ysis. Cognition, 28(1-2)::3111111111111 1988. doi: 10.1016001000277833900555
Nicholas T Franklin, Kenneth A Norman, Charan Ranganath, Jeffrey M Zacks, and Samuel J Ger- shman. Structured event memory: A neuro-symbolic model of event cognition. Psychological Review, 127(3):327, 2020.
Vicky Froyen, Jacob Feldman, and Manish Singh. Bayesian hierarchical grouping: Perceptual grouping mixture estimation. Psychological Review, 122(4):575, 2015.
Fermand Gobet, Peter C.R. Lane, Steve Croker, Peter C.H. Cheng, Gary Jones, Iain Oliver, and Julian M. Pine. Chunking mechanisms in human learning. Trends in Cognitive Sciences, 5(6), 2001. ISSN 13646613. doi: 10. 11166//164-6613/// 3604-66611000011666-4444
Christina Heinze-Deml, Marloes H. Maathuis, and Nicolai Meinshausen. Causal Structure Learn- ing. Annual Review of Statistics and Its Application, 2018. ISSN 2326-8298. doi: 10.1
annuev-statistcs-001117.. 100630.
10

---

Under review as a conference paper at ICLR 2022
Geoffrey Hinton. Some demonstrations of the effects of structural descriptions in men- tal imagery*. Cognitive Science. 3(3):231-250, 1979. doi: http:://doi.or//1... $15516709cog030311 3. URL https://oninellbrrrry www.orrrr...wll..l.oo..om www.w.cco//o/////../e.o. 1207/s155 (ttpe/155517799ooooo0 7799co0333333
Eldar Insafutdinov, Leonid Pishchulin, Bjoemn Andres, Mykhaylo Andriluka, and Bernt Schiele. Deepercut: A deeper, stronger, and faster multi-person pose estimation model. In European Conference on Computer Vision, pp. 34-50. Springer, 2016.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger,
Kathryn Tunyasuvumakool, Russ Bates, Augustin Zídek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(78733:583--88) 2021.
Iring Koch and Joachim Hoffmann. Patterns, chunks, and hierarchies in serial caation-timee tasks. Psychological Research, 63(1), 2000. ISSN 14302772. doi: 10.1007//L00008
B. Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequenee recurrent networks. In ICML, 2018.
B. Lake, R. Salakhutdinov, and J. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350: 1332 - 1338, 2015.
Brenden M. Lake, Tomer D. Ullman, Joshua B. Tenenbaum, and Samuel J. Gershman. Building machines that learn and think like people. Behavioral and Brain Sciences, 40:e253, 2017. doi: 10. 10:00175004452551001133333
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7533)436-4444 2015.
Raphaëlle Malassis, Arnaud Rey, and Joël Fagot. Non-adjacent dependencies processing human and non-human primates. Cognitive Science, 42(5):1677-1699, 2018.
G. Marcus. Deep learning: A critical appraisal. ArXiv, abs/ abs/1801.00631, 2018. 2018
Denis Mareschal and Robert French. Tracx2: a connectionist autoencoder using graded chunks to model infant visual statistical learning. Philosophical Transactions of the Royal Society B: Biological Sciences, $72:20160057, 11 2016. doi: 10. 10.1098/rstb.2216.0055
Stewart M McCauley and Morten H Christiansen. Computational investigations of multiword chunks in language learning. Topics in Cognitive Science, 9()):337-652 2017.
George Miller. The magical number seven, plus or minus two: some limits on our capacity for
processing information. Psychological Review, 1956. ISSN 0033295X. doi: 10. 10.103//
Diana M Müssgens and Fredrik Ullén. Transfer in Motor Sequence Learning: Effects of Practice Schedule and Sequence Context. 9(November), 2015, doi: ....389ffhumm220550000
Timothy J O' Donnell, Joshua Tenenbaum, and Noah D Goodman. Fragment grammars: Exploring computation and reuse in language. 2009.
Katrin Ortmann. Chunking historical german. In NODALIDA, 2021.
Virginia B. Penhune and Christopher J. Steele. Parallel contributions of cerebellar, striatal and M1
mechanisms to motor sequence learning. 2012. ISSN 01664328.
Pierre Perruchet and Annie Vinter. Parser: A model for word segmentation. Journal of Mem- ory and Language, 39(2):246 263, 1998. ISSN 0749-596X. 1998 2576. URL 1m9..1998.22. 50 65749596X98925765
doi: https://doi.org/10..u 1006/ www.:scceneeiie.co rect.. com//scieenc//rtiille/pp..
Pierre Perruchet, Bénédicte evidence for chunk- models in word segmentation. Acta psychologica, 149:1-8, 2014.
Barbara Tillmann, and Ronald Peereman. New
Dwight J Peterson and Marian E Berryhill. The gestalt principle of similarity benefits visual working memory. Psychonomic bulletin & review, 20(6): 1282-1289 20133

---

Under review as a conference paper at ICLR 2022
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '16. pp. 1135-1144, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342322. doi: 10.1145/2939672. 2939778. URL httpps:/:///
David A. Rosenbaum, Sandra B. Kenny, and Marcia A. Derr. Hierarchical control of rapid movement sequences. Journal of Experimental Psychology: Human Perception and Performance, 1983.
ISSN 00961523. doi: 10.1037/0096- 1100066-5522:.0 1523.9.1.86.
Wojeiech Samek, Thomas Wiegand, and Klaur-Robert Müller. Explainable artificial intelligence: Understanding, visualizing and interpreting deep learning models. ITU Journal: ICT Discoveries Special Issue 1 The Impact of Artificial Intelligence (Al) on Communication Networks and Services, 1:1-10, 10 2017.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5):612-61) 2021.
Eric Schulz, Joshua B. Tenenbaum, David Duvenaud, Maarten Speekenbrink, and Samuel J. Ger- shman. Compositional inductive biases function learning. Cognitive Psychology, 2017. ISSN 00100285. doi: co006ff.cogssyc.2011... 1.002.
Eric Schulz, Francisco Quiroga, and Samuel Gershman. Communicating compositional patterns. Open Mind, 4:25-39, 2020.
Emile Servan-Schreiber and John Anderson. Learning artificial grammars with competitive chunk- ing. Journal of Experimental Psychology: Learning, Memory, and Cognition, 16:592-608, 07
1990. doi: 10. 01137/0277--7333114.444
Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 2773):379-423, 1948.
Noel E Sharkey and Amanda JC Sharkey. An analysis of catastrophic interference. Science, 1995.
Connection
Sun Si, Chenyan Xiong, Zhenghao Liu, Zhiyuan Liu, and Jie Bao. Joint keyphrase chunking and salience ranking with bert, 04 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Yee Whye Teh. A hierarchical bayesian language model based on pitman- processes. Proceed- ings of the 21 International Conference Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pp. 985-992, 2006.
Johan Wagemans, Jacob Feldman, Sergei Gepshtein, Ruth Kimchi, James Pomerantz, Peter A Van der Helm, and Cees Van Leeuwen. A century of gestalt psychology in visual perception: li. conceptual and theoretical foundations. Psychological bulletin, 138(6):1218, 2012.
Feifei Zhai, Saloni Potdar, Bing Xiang, and Bowen Zhou. Neural models for sequence chunking. In AAAI, 2017.
A INDEPENDENCE TEST
We use hypothesis testing on the assumption of independence to decide whether there exists an association between consecutive parses of any two chunks с,, and eR in the current belief set. If the independence test is violated, then the two chunks are combined together. Another independence test is used to evaluate if there still statistical associations between chunk observations for each possible chunks in the current belief set; this is used as criterion to continue or halt the chunking process.
12

---

Under review as a conference paper at ICLR 2022
We use x--test of independence to assess if the consecutive parses of cL and eR observed in T violate the independence criterion. Observations of e7 and eR in parses are categorical variables and can be represented that ez. = 1 or any other observations (Cr. = 0) consists of the row entries, indicating observations of cz, while the number of observations e 1 and en 0 make up the column entries. The table, therefore, consists of two rows and two columns.
and columns of contingency table. The number of observations
The null hypothesis is that the occurrence of the consecutive observations is statistically indepen- dent. Given the hypothesis of independence, the theoretical frequency for observing cr. followed by CR is Elcc CR 1]= = Np(cz 1)p(CR 1), with N being the total number of parses.
p(cL= = =) N(cc) bec + N(c, <<R) pp(cn = 1) = N(eR) N(e + N
N( (e teg)
N
N
N
N
N
N(e ln =r) Elce = cn r]
x²
Σ Σ
Elcl L, = r|
[=(0.1)
(1)
Nleg -le ) p(cl = =pp(eR==1 =))
=N E plc = 1)p(en = r)
N
plcz = 1)p(eR =
(=.1)
The degree of freedom for this test is 1. A x2 probability of less than equal to 0.05 is used criterion for rejecting the hypothesis independence.
The independence test is also employed evaluate whether there still statistical associations between chunk observations for each possible chunk in the current belief set, which we use as a criterion continue to halt the chunking process. For this test, the contingency table contains rows and columns corresponding to all possible chunks the current belief set, and the x -taatisstic calculated as:
N(cL, CR) F(CL.Cn] = ElcL,CRl
N(CL p(eL)p(CR)
x Σ Σ
Σ Σ p(el)p(CH) p(eL)p(CR) OL E&B CR
CL CR=BB
(2)
The degrees of freedom (I=BI 1) (IsB) 1). and p-value of 0.05 is again used criterion to reject the null hypothesis and therefore as evidence to continue the chunking process.
B RATIONAL CHUNKING ALGORITHM
Algorithm 1: Rational Chunking Algorithm
input Seq, maxIter
output: Bd, Gd, Ta. Md
d + 0. iter t- 0;
Bd, Ma. TĄ geiSinglefleeeenSsssssss..
minimally complete atomic set
*/
while !IndependeeneeTssttMMa Ta) or iter maxiter do Ma, Ta Parse(Seq. Ba);;
CL CR +- None; M MarChunk, MazChunkP + None; PreCk (}:
for (c, cg. Ba\{0} Ba {00 do
Pa(c; 1 cz) = (CleaulateJoone(Maa Pa(c:(e;)
Pati(c a (g) PPlc)
if Pa+i(c; 1 (c)) > MaxChunkP and θc & PreCk and !IndependenceTesstc, eÿ) then
CL + c CR t cj; MarChunkP + (a @cj), MaxChank + - G
end
end
C + Cr. ① Cnj Bas + Ba U e; Gass AugmentGraphh(G.. (ct, c) (CR,C))
PreCk.addl(c): end
13

---

Under review as a conference paper at ICLR 2022
C ONLINE HCM WITH GENERALIZATION TO VISUAL-TEMPORAA SEQUENCES
HCM learns a chunk hierarchy graph 9 by training on a visual-temporal sequence. The visual- temporal chunks retain various continuous shapes and may not fill the entire space, which means that there are no jumps from any visual temporal pixel within a chunk to another. Within a chunk, there is always a path that connects any two visual temporal pixels.
The imput chunk hierarchy graph 9 could be an empty graph which corresponds the case that the HCM model has not been trained yet, or it can be chunk hierarchy graph that HCM has acquired from training. M contains the frequency count of each chunk in the belief set IB T stores pairs of parsed adjacent chunks and their difference in temporal lag. The temporal lag is the time difference between the end of the previous chunk and start of the following chunk. The generative model of the world assumed by the chunk learning model is such that each visual temporal chunk occurs independently for each parse. then keeps checking whether adjacent chunks the visual and temporal domain violate the independence testing criterion. If so, then the visual/temporal adjacent chunks are grouped together. The constituent parts of a chunk remains in the belief set.
Algorithm 2: Visual-Temporal Chunking
input Seq, G, 0, DT
output: g
M. T + G.M.G.T;
BreviousChunkBBuunayyykeeee ChunkTerminationn/ l'ime.setalle (-ta while Sequence not over do CurrentChunks, TetunnTTemiinniioTTTneee Identify TeeeiiffTThhaaaae ChaaarCCnnnnncCuuunnTematnnnntnn
+ II:
/x Record Chunk Endings +/
TorevattioTTTxEpaaii +- refactor(Seq. ChunkTerminationnTmme)) for Chunk in CurrentChunks do for CheckAdjacencyl Chunk, CandidatehdiacentChunkk then
in PrevionsCham&BBBuddryyRee do
M, T, IB, 9 + CearnChunking(Chunl CandidateAGjicennCuunk M, T, B 9);
end end end
PrevousChum&BomddrReeodddd haaped/rrrreooodaaaauurrnnnnnnC add((CureenChhunkk):
Forgetting(M1 T, 1B, G. 0, DT, PreviousCCuunkBBBudddyyyyCool) end
The pseudocode for the Tisual-Temporal HCM is shown in Algorithm 2 temporal sequence, i.i.d visual sequence, or a temporal sequence.
The input can be a visual-
To process and update chunks online, HCM iterates through the visual temporal sequence, identifies chunks, and marks the termination time corresponding to each visual dimension stored in Chunk- TerminationTime
ShunkTerminatinn Time is a matrix with its size being the same as the visual dimension that stores the end point in each visual dimension that the previous chunk finished. Be- cause chunks could finish at different time points in each visual temporal dimension, the algorithm explain chunks starting at the end point in each visual temporal dimension when the last identified chunk is finished up until the current time point to identify current, on-going chunks. The chunks with the biggest visual temporal volume are prioritized to explain the relevant observations up to the current time point. As multiple visual temporal chunks can be identified to occur simoutaneously, CurrentChunks is a set that stores the identified chunk that has not reached its end point.
Once several chunks are identified to be ending at time point, they stored inside the Pre- BebunkBounddryReeoo and their finishing time is updated for each visual pixel in ChunkTer: minationTime Corresponding entries in M are updated upon once chunk has ended. The chunks
14

---

Under review as a conference paper at ICLR 2022
that finishes after the start of the current chunk is checked with each current chunk whether there a visual temporal adjacency. Additionally, the independence test between adjacent chunk pairs carried out for the decision to possibly merge chunks.
Once a pair of adjacent chunks ez en violates the independence testing criterion, they are combined into chunk ez en- new entry is created in M with the estimated joint occurrence frequency for Cr ① CR. which is subtracted from the marginal record of с₁ and cR- The transition entries associated with ep CR are initialized to be Other chunks inherit the transition entries from OR to other chunks.
At each time step the visual temporal chunking algorithm does the following things:
1. Identifies the chunks biggest in volume that explain observation in each dimension from the time point when the last chunk ended to the current time point, mark their time point, and store them in the set of current chunks.
2. Identifies adjacent chunks in previous chunks with each of the currently ending chunk and updates their marginal and transition counts.
3. Modifies the set of chunks used to parse the sequence based their adjacencies.
Entries in M and T are subject to memory decay at the rate of 6, If any entry goes below the deletion threshold DT, their corresponding entries in M, T, IB and & are deleted.
D DETAILS TO THE PROOF OF RECOVERABILITY
D.I DEFINITIONS
An observational sequence made up discrete, integer valued, size-one elementary observational unit coming from an atomic alphabet set Ag. where O represents the empty observation set.
One example of such an observational sequence S is:
010021002112000
The elementary observation units such as '0', '1', and '2' come from the atomic alphabet set Ag
{0, 1,2).
Definition (Chunk)
A chunk is composed of several non-empty, concatenated elementary observations, embedded in the
sequence. That is, a chunk can be made up from any combination of elements in Ang" \ {0}
Examples of chunks from the observational sequence be '1', '21', '211', '12', 22112' etc. represents an empty observation in the sequence.
Definition 2 (Belief Set)
A belief set is the set of chunks that the HCM uses to parse training sequences. The belief set is denoted as B.
An example of belief set that that the model has learned from S could be B
(0, 12,
Definition 3 (Parsing)
The parsing of chunks initiates from the beginning of the sequence. At every parsing step, the biggest chunk in the belief set that matches the upcoming sequence chosen to explain the observation. The end of the previous chunk parse initiates the next parse.
The sequence 5 parsed by the model that uses the belief set (0, 211, 12, 2112] results in the following partition. Q 0 0 21 0 2112222222 0.0
We say that belief set is complete if at any point when the model parses the sequence, the upcoming observations be explained at least by one chunk within the belief set.
15

---

Under review as a conference paper at ICLR 2022
C
CR
Cr. CR
Independence Test
t-3
t=1
t=o
CR
C₁. Figure 6: Illustration of Visual Temporal Chunks
CL CR
In this work, only refer complete belief sets. Definition 4 (Parsing Length N₂)
A parsing length N3 of sequence parsed by belief set is the length of the parsing result after the sequence has been parsed by chunks within B.
Definition (Count Function Nn(c))
Ns(c) denotes the count of how many times the chunk in the belief set BB appears in the parsed sequence.
The parsing length and the count function for all of the chunks con a belief set I satisfy the following relation:
NB Σ Ns(c)
(3)
CER
Definition 6 (Ng y))
The number of times chunk is being parsed following the parse of chunk y. x and y both chunks in the belief set B.
For any chunk x within any belief set B. one can relate (n(x)) with Na(x - y) by:
Nn(x)= Σ Nn +
yEB
When the length of the sequence becomes infinite, it is easier work with probabilities instead of the count function. One can define probability space over the belief set:
Definition 7 (Probability space of a belief set)
With belief set B. space representing all of the possible outcomes of a chunk parse.
define a associated probability space (Sn, Fr, Pa). S5. is the sample
An event space F the space for all possible sets of events. F contains all the subsets of Sg. Additionally, the probability function PAa FB + IR is defined on the event space Sg. The proba- bility function PAs satisfies the basic axioms of probability:
PAg (F) O F. For any subset in the space, the probability of an observation being in the subset is positive.
M, N E F, and MON E. then P(MUN) = P(M)+ P(N). For two non-intersecting subsets in the event space, the probability of observing any element that falls within the union of the two subsets is the sum of the probability of observing any event within one subset and the probability of observing any event from the other subset.
P(S) 1. The probability of observing any event that belongs the sample space is one.
16

---

Under review as a conference paper at ICLR 2022
The probability of chunk support set of chunks IB, is the limiting case of this ratio when Ng goes to infinity.
Nn(c)
Pr(C)
lim
(5)
Ng 700 NB
A learning model keeps track of the occurrence probability associated with each chunk in the be- lief set. For a current belief set, the model assumes that the chunks within the belief set occurs independently.
The occurrence probability of chunk o, with the belief set Ba is (c,( which refers to the nor- malized frequency of observing chunk e; when the number of parsing the sequence using chunks from the belief set goes to infinity. In this way, the probability of observing a sequence of chunks Cis C2: CN be denoted P(ci, CN.).. The joint probability of observing any chunk in the generative process is:
P(c1,C2
II (c)
(6)
c
In this formulation, chunks as observation units serve as independent factors that disentangle obser- vations in the sequence.
Definition 8 (Marginal Parsing Frequency Ma)
vector that stores the number of parses for each chunk the belief set Ba.
Ma contains size [Bal Additionally the model keeps track of the transition probability from one
chunk to another, as they are used to test whether two chunks have immediate temporal adjacency association.
Definition (Ta)
The set of transition frequency from any chunk q E Bd to cy E By
Definition (Chunk Hierarchy Graph Ga)
The relation between chunks and their constructive components in the generative model is described by chunk hierarchy graph Ga with vertex set Va,, and edge Ex.- One example of chunk hierarchy graph is illustrated in Figure In this hierarchical generative model, d is the depth of the graph and A is the set of chunks used as atomic units to construct the sequence. Each vertex in Vaa is a chunk, and edges connect the parent chunk vertices to their child chunk vertices.
As the belief set B keeps changing when one modifies the chunks in a sequence, so does the parsing length N3 and the probability associated with the belief set PAg. Based on the definition N on how chunks are parsed when the support set changes, this change of N changes a set of constraints on the probabilities defined on the new, augmented support set. To do this, we need to:
Formulate the definition of probability based on N.
Identify all relevant changes of N before and after the chunk update.
Translate this change to the constraints on probability updates.
We derive the relation between the probabilitics when two chunks с, and cn E Ar are concatenated together to form new chunk ez en and update the alphabet to A441.
D.2 IDENTIFY N UPDATES
This is how the count function changes before and after the update. We start with the update of the summary N when the alphabet goes from Ag to A and proceed to the update for the marginal N, and then the transitional N.
17

---

Under review as a conference paper at ICLR 2022
QR
CR
CR
CL
CL CR
CL
CR
CL CR
D.2.1 SUMMARY N
When going from Aa to Ad41s Cr, and eR are both chunks in Ad and merged together as a new chunk to augment Ad.
The number of parses changes only in places where the ez and eR associated with the new chunk occurs. The chunks in Ad be divided into three groups. CL, CR, and Aa \ {cL, cR). The count function associated with chunks from the set As {cL, CR} does not change when Ad updates to A++1-
Since with the chunk update Ad+1, CL and CR are chunked together, they are recognized together whole, every time when they recognized together whole, the count reduces twofold. N4+11 (Cr.) and N4+1 (CR) are the number of counts for ct. and CR when they do not occur together. This count is different from Na(er. and Na(eR) because the occasions when they another is taken into the count by Na+1(cp (cz @ CR). The relation between Ng and No41 is:
after
No+1
Σ
Nalc) + Nat1(eL) + Nat1(cR) + Nat1(e1 @ @CR)
LoEAd-OL
Net1(cL) could occur in the case where CR does not follow CL.
Nat1(ez @ CR) Na(CL CR)
(8)
Na+1(e1) = No(c1) - NaleL + CR)
(9)
Na+1(en) Na(en) Nalcl - cR)
(10)
Nat1(cL CR) # NN+1(eLL + +N++1(eR) Na(cL) Na(CR)
(11)
Chunking reduces the number of times sub-chunks are being parsed when sub-chunks occur right after each other by twofold.
NJ Σ Na(c)=
Σ
Na(e) + + Na(CR)
(12)
CEA.
Lo
Comparing the above two equations arrive
Na Na(eL) - Na(CR) Na+1 Nat1(eL) -N+n(C)))) - Nati $ cC))
(13)
Since:
Na(c1) + Na(eR) Net1(cL) Na+1(eR) 2Na41 @cn)
(14)
This is related to:
Na(CL + CR) Net1 @ CR)
(15)
Because both counting the number of times they occur consecutively. Nat1(eL) + Net1(cR) Na(e2) Na(cR) 2Na(e1 CR)
(16)
One can define N4+1 in terms of counts in NJ as:
Nd+1
Σ
Nale)
+ Na(cz) +N(cn) 2Na(e1 + +C) + NNlcs + cn)
LoEk
(17)
Nd+1
Σ
Na(c)
Na(ee) Na(CR) Naler CCR
LOEAA-CC-CN
18

---

Under review as a conference paper at ICLR 2022
Generally, the result is also the case with the total count Na and N4+1 when switches from the alphabet set Ad to Adf1 by chunking eL and eR in Ad together.
N4+1
E
Nalo) NN(ec)) -Nlee) CR)
(18)
LE oR
Na+1 = No- Nalc1 + cR)
(19)
D.2.2 MARGINAL N
To proceed into formulating the joint and conditional probability given a particular belief space, we need formulate how the count of (c) for chunk changes when the belief space when switching from Ad to As+1, with the same division as before.
Of course, the count function should fixed. However, the probability function associated with the chunks will change based on the update of the belief set. We use the update of the count function to find the relation between the probability updates.
For all in Ad- {CL, Cns + en):
N4+1(x) = Na(x)
(20)
Nati(cR) = Na(eR) - NalCt + CR)
(21)
Na+1(cL) = No(eL) - NalCL + CR)
(22)
N4t1(e1 @ cn) Na(CL - cR)
(23)
D.2.3 TRANSITIONAL N
The following relationship needs to hold:
for all x, y in Ad! CR, cL + cR):
Nat1 = +)
(24)
N4t1(1 + el) -L) N2 4C)
(25)
(z + = Na(x CR)
(26)
Nat1(æ + ecR
- - cR) Na + cL) Not1 9)
(27)
Na-(E cr @ cR) < Na(c1 CR)
(28)
From e₁ we have this relation.
Na+1 (cr, + xx = Na(cI. +x)
(29)
N4t1(C1 + + = Na(e1 + CL) - Nati(eL + cz @cn)
(30)
Na+1(e1 + cn) =0
(31)
Nat1(ct + cc 0cR) = NN+1(CL) - Nat1(c1 + CR) - (N411 + (L) - NN+1(cc + x)
(32)
Na+1(eL - t9 @ CR) v Na(eL + CR)
(33)
Nati(eL + 19 @ CR) I Na(cL + CR)
(34)
From en we have the following relation:
Nati(eR + y) Na(CR + 3) Ne+1 @ ca +
(35)
Nati(en c1)) Na(cn + C1.) Na-1 @ cn - CL)
(36)
Nat1(Cn + en) Na(CR - cn) Nati(ei @ cn + en)
(37)
Nati (cn ez. (cn) Nati(en) Na+i(eR cn) Nat1(en + cτ.) N4+1 - y) (38)
Nat1 (cn cz cn) Na(cr @ en)
(39)
19

---

Under review as a conference paper at ICLR 2022
From the chunked unit eg eR we have the following relation:
Na+1 (cg @ cR - =) S min(Naler @ eR), ((x1(cR(2))
(40)
Na+1 (cz, @ en + cL) I miin(Na(es @ en), Na(en @ ec)
(41)
Nat1 @ CR + CR) & min(Na=1(es @ Ne ( Na+1 @ cn + cr. @ CR) S Smin(Na41 (er. @ CR), N Finally, we need to satisfy the marginal constraint, that is:
(42)
(43)
Nay1 (Cr. N441 (cr, (CR +N.4 (Cr,CR + Na4) + cR)+ Na+1 (cr, @CR - (2,
(44)
D.3 PROBABILITY DENSITY SWITCH WHEN Ad EXPANDS TO Ad++1
The constraint is: the number counts N for chunks defined for the support set Aa must remain the same for the support set 8A4+1, so that the definition of Pad for all relevant chunks within Aa remains the same when Aa expands to Ad+1.
Relating the number of counts to probability: The probability of chunk occurring in the alphabet set Ad is defined as:
Na(c)
(c. = lim
(45)
Na-000 Na
Because N& and N6 are only a constant away, both go to infinity if of them does, there is a relation between the definition of probability Pa,(c) and Paayi (c). For any chunk x in Ad that is ez and CR. Nat1(a)) (ar Na(æ):
Na)1 lim Na-oo Na Na(CL CR)
Na(x)
PAota (z)
lim
(46)
No01
Na+1
That is, the probability of chunk of this category at and d+I satisfies this relationship:
lim No01
Ma)n(e)Na-11 = lim PA,(x)Na
(47)
Na-00
1o Na
PA (x) (x)
(48)
lim No+1
lim No
PAoHI (x) =P)]
(49)
lim lim No Nale1 + cCR
For ez and en in A241:
N4t1(C1))
Paoti Na41
Paat((LL= (CL)
lim
(50)
Na
NalcL)
PAa(C))
lim
(51)
Na11
Na
Na41(CR)
lim
(52)
Nas
Na41
Na(en)
PA((on) lim
(53)
Na
No
Because:
Nati(eL) = -Nacc)) Na(es $ cC)
(54)
Na(C1.) Nalei cR)
(Ct)) lim N
(55)
Na
Na(c)) - Na(e1 - CR)
PA (CL) = lim
(56)
No0
Na Nalet + CR)
20

---

Under review as a conference paper at ICLR 2022
Nalen) - NaleL - cR)
lim No
(57)
No Noler + Cc)
Finally:
Nat1(cs @ CR)
PA @ CR)
lim
(58)
Na41 700
Na+1
Naler + cn)
PAa(cL @ cn)
lim
(59)
Na0
Na
since Na(ez - cR) Nat1 @ CR), we have
Paalel ca)
PA (CL + cR) lim Na-
(60)
Na+1
D.3.1 SUMMARY PROBABILITIES
Na+1 Na Na(CL cn) Na NaPa(ce @e)
(61)
Nat1 =1 Pa(cL @ Cn)
(62)
N₂
D.3.2 MARGINAL PROBABILITIES
The constraints on marginal probabilities when the support set changes from Ad to Ad41, derived from the constraints the marginal counts, the following:
Pa(x)
Pati(æ) 1 1- Pu(cL CR)
(63)
PatI(cR) Pa(CR) Paler + CR)
(64)
1- Pa(CL ① CR)
Pa(CL) - Pa(cI 2 CR)
Pat1(CE) = 1 Pa(cr, @ CR)
(65)
Pa(CL $ CR)
Pat1(eL OcR) Pa(eL @ CR)
(66)
With this set of formulations, we have defined the next level marginal probability measures function of the previous level observations and their implied probability measures.
D.3.3 TRANSITIONAL PROBABILITIES
for x, y in Aa fCL, cR. ez cR), from x we have this relation:
0 Pa+1(11)) S
(67)
Pat1(v|x) = Pa(y(æ)
(68)
Pa+ = Pa(cR(æ)
(69)
Pat1(er/z) + (ct @ cR|z) Pa(en|æ)
(70)
This equation is sampled so that both (ati(c and Pati(cs @ cnlæ) satisfy the following con- straints:
Pa=1(cr(a) < Pati(c1)
(71)
Pa)
Pati(cs @ CR)
Pati(es @cRlz) <
(72)
Pati(1)
21

---

Under review as a conference paper at ICLR 2022
Marginals
Transitooss
CR
x
CL
CL
CR
CL CH
CL
CR
C.
Basically, Pa+ (cr.(2) is sampled from the range
0, min
Patiler)
(ats(x) Pa(en|=))3
Additionally, Patiler min (oLO()) Pa(ce|=))
cRl
constrained
be
within
this
range:
Pa-1(z)
From eg we have this relation:
Pa(xler)
Pa41(1le1) 1 Pa(cHleL)
(73)
Pati(enleL) =
(74)
Pasi(erlez) Pa(erler) (1 Pa(eR (e(eeRle)))) (er @ cR(C1)
(75)
- Pa(en(c1)
Put into simplified terms:
(ari(e) Pati(er @ (enle)) = Pa(czleL)
(76)
Pa(enle1)
Pati(eL|CL) S Pati(el)
(77)
Pati(c1)
Patiles cclle)) s Pati(el @cn)
(78)
Pat1(e1)
Paleeles) Additionally, Pa-1(eLlez)) is constrained to fall within this range: (0, min(1, I- I-Patenlez) }]
Pati(ei @ cale1) within the range (0. min(1, Paplesseal Palezles), Passles) 1-Pascelee)) }]
From eR we have the following relation:
0 s Pati(1en) $
(79)
Pa-i(yleR) = Palvlen) Pati @ Pa(c @ CR)
(80)
Pa(cR) Paler @c))
22

---

Under review as a conference paper at ICLR 2022
Pat1(er|oR) PalerloR)Pa(cx) Pati @ PaR) @ CR)
(81)
Pa(eR) Pa(en, @ CR) Pa+I(enlen) Pa(en) Pati(enle2 @ Pale @c))
(82)
Palen) Pa(c1 @ @cn)
Pati(1CRR) 2 Pat1 (-ler @ cR)
(83)
Additionally, Pa-1 (ez. cRlen) and Pa+i (er caler. @ en) needs satisfy:
Pat1(C1 @ en en) = 1 Pati - Pati(enlen) - Pa+1(celen)
(84)
Pa+i (cr @elle @ CR)
Pa+i @ CR) Pa+ (cRler @ CR) Pa+ @ CR) (85)
For the generative model, when the alphabet set goes from Ad to Ad + 1 by chunking and CR together, the above constraints associated with chunks in Ad and Ad+1 need be satisfied.
D.4 HIERARCHICAL GENERATIVE MODEL
At the beginning of the generative process, the atomic alphabet set Ao is specified. Another param- eter, d, specifies the number of additional chunks that are created in the process generating the hierarchical chunks. Starting from the alphabet Ag with initialized elementary chunks c; from the alphabet, the probability associated with each chunk C₁ in Ag needs to satisfy the following criterion:
Σ A
PAo (c:) =1
(86)
Mcanwhile, P(c)) 2 0, Vc, Ag.
We assume that at each step the marginal and transitional probability of the previous steps are known. The next chunk is chosen as the combined chunks with the biggest probability. The order of con- struction in the generative model follows the rule that the combined chunk with the biggest proba- bility the support set of pre-existing chunk sets chosen be added to the set of chunks.
CL CR arg max Pag (CL @ en)
(87)
CL.cREAd((U)
Under the constraint that:
Pa. Pca(c))Pa $ Paalel 4 cR) $ (LL)
(88)
This can be calculated from the transitional and marginal probability of the previous step.
CL + CR
arg CL.CnEdJ \(03
PA (cr @ CR) arg PA.(ee)) CL.enEba\(0)
(89)
Once the chunk of the next step: eg cR is chosen, the support changes from A to Aat1. which is one size bigger. On the new support set, the marginal probability is specified by the marginal update. That the marginal and transitional probability defined the support set Aa fully spec- ifies the marginal probability of the support set Ag- Going from generating a new chunk from the support set Aa the set Ad+1, the transitional probabilities between chunks in Ag need to satisfy the following constraints:
(Psu((CE/z)) + PAL. (cL @ (RR()) = (As(cz()) for all x in Aa (c (cR(c))))) + PARts (cL @ cR|CL)( (As(cR(O)) (As(CL)eL)
PA (PA, PAa(CL CR)) PAu (vles @ (R)PAs(CL e eR)
PAaly(CR) PAN(CR)
PA (CL (PL) P PA,
PAl(CL cR)) + Paln PA CR)
(n (P)((C)) PAG(Cr @ CR)) + (elne e PR, e cR) =
(an(Cn))R) (CR)
23

---

Under review as a conference paper at ICLR 2022
Patilci calea) = Pa-1 - Pati(cnleR) - Pa+1(cLleR))
Pati(er Ocn @CR) = 111-P44 (yler, + (C)) Pat (CRler. @ @CR) - Pa+1 (er/er @CR)
In total, there are |x|| + |u| + 3 degrees of freedom. Since
|a|| = lyl = AAa - 2, at each step, there
are 2 Aal number of values to be specified.
In practice, after the chunks are specified in Ag. the probability value associated with chunks in As are sampled from flat Dirichlet distribution, which is then sorted that the smaller sized chunks contain more of the probability mass and the null-chunk carries the biggest probability mass. Then, the above constraint checked for the assigned probability on each of the newly generated chunk with their associated alphabet set A, This process repeats until the probability drawn satisfies the condition for every newly created chunk.
Theorem 1 (Marginal Probability Space Conservation). After the addition of ca. ca. and the change of probability, PA, is still valid probability distribution.
Proof:
Σ Pao(can)= =
Σ
PAL (ca-1xk)
CLAEAd
S.MEAs ct 14-11
P PAL-1 (C-- - (d- P.a) (Ca-1,))
(90)
+ PAa (cd-1.)) + PAa-I (c-- (AL-:- (cd-1,))
Theorem 2 (Conditional Probability Space Preservation). The conditional probability (zl1( for any e E Aa+1 after sampling is still valid distribution.
Show by manipulating the equations, that the sum of the conditions on с sums to 1, and each of them is bigger than O.
Proof:
Theorem 3 (Measure Space Preservation). Given that at the end of the generative process with depth d one ends up having an alphabet has the probability space defined on A;, which includes the marginal and joint probability of any chunk and combinations of chunks in AG, i = 0, 2...... d, which are predecessor alphabet sets of As, all values in the set M4 and Ta remain the same no matter how the future support set changes according to the generative model.
Proof: By induction.
Base case: starting from the initialized alphabet set Ag, the probability of (c) e Aos and the probability of PA, (zy), Going from Ag to A1, No).), No and No(x - y) does not change, therefore PA, (c) and PAo > y) the alphabet A₁ is the same as that when the alphabet is Ap
Ao. for all valid c, y. when the alphabet is A1-
Induction Step: starting from the initialized alphabet set Ag, the probability of (A,(c), (c), Aa. and the probability of PA (zy), E Ad. for all valid c, x, when the alphabet is Aat1. Going from Ad to A4t1. Na(c), Na and Na(r y) does not change, therefore PA (c) and PAA - y) at the alphabet Ad-1 is the same as that when the alphabet is Ad-
Theorem 4. The order of PA, (zy), N. for any 0,1,2,... any previous belief space is preserved throughout the update.
Proof: At the end of the generative process with depth d, one ends up having such an alphabet set: Ag. The probability space defined A, which includes the marginal and joint probability of any chunk and combinations of chunks in A,, = 0, 1, 2.... d preserved, hence the order is preserved.
The generative process can be described by a graph update path. The specification the initial set of atomic chunks As corresponds to an initial graph Go with the atomic chunks its vertices. At the i-th iteration, as the generative graph goes from Gz, to graph GA... two none zero chunks cna en chosen from the pre-existent set of chunks 4 and are concatenated into chunk er @ en-
24

---

Under review as a conference paper at ICLR 2022
augmenting A, by one to As+1- The vertex set also increments from Va. to VA VA, Jc @ CR- Moreover, two directed edges connecting the parental chunks to the newly-created chunk are added to the set of edges: Ex, Ex, Es. (cr, Cr. @ cn) U (CR, er @C)) The series of graphs created during the chunk construction process going from Gro to the final graph Gr, with d constructed chunks can be denoted as graph generating path P(gng ((Gng:Gao) (Ghg: 9h, Gkg. -. 9..))
D.5 LEARNING THE HIBRARCHY
The rational chunking model is initialized with one minimally complete belief set, the learning algorithm ranks the joint probability of every possible new chunk concatenated by its pre-existing belief set, and picks the one with the maximal occurrence joint probability on the basis of the current set of chunks as the next new chunk to enlarge the belief set. With the one-step agglomerated belief set, the learning model parses the sequence again. This process repeats until the chunks in the belief set pass the independence testing criterion.
Theorem 5 (Learning Guarantees on the Hierarchical Generative Model). As N + oc, the chunk construction graph learned by the model & is the same as the chunk construction graph of the generative model: 9 = G. which entails that they have the same vertex set: V Vg and the same edge set: È- Eg. Additionally, the belief set learned by the chunk learning model IB, = Ads and the marginal probability evaluated on the learned belief set Ms. associated with each chunk is the same as the marginal probability imposed by the generative model on the generative belief set Ma.
Proof: Given that all of the empirical estimates are the same the true probabilities defined by the generative model, we prove that starting with Bo, the learning algorithm will learn Bn = An- AD is the belief set imposed by the generative model. We approach this proof by induction.
Base Step: As the chunk learner acquires a minimal set of atomic chunks that can be used to explain the sequence at first, the set of clementary atomic chunks learned by the model is the same as the elementary alphabet imposed by the generative model, i.e. Bp = Ag- Hence, the root of the graph, which contains the nodes without their parents, is the same, 9 = G; put differently, Vo- = =oo
Additionally, the learning model approximates the probability of a specific atomic chunk as P.Ao (a:). As n - oc, for all chunks e in the set of atomic elementary chunks in Bo, the empirical probability evaluated on the support set is the same as the true probability assigned in the generative model with the alphabet set An:
No(c) No
Pro (c) lim
PRo (c)
(91)
Induction hypothesis: Assume that the learned belief set Ba step d contains the same chunks as the alphabet set A in the generative model.
The HCM, by keeping track of the transition probability between any pairs of chunks, calculates (c:lc)) for all q. Cj in B,. Afterwards, it finds the pair of chunks c, Cj. such that the chunk created by combining G; and ej together contains the maximum joint probability violating the inde- pendence test as candidate chunks be combined together.
(B @c₁)
sup cieeEBa
Ps.(c))Paeelle
(92)
We know that in the generative step the supremum of the joint probability with the support set A. is being picked to form the next chunk in the representation graph, so each step of the process at step d satisfies the condition that:
Pa
sup (A.(e))A,(ele)) c.aaEAu
(93)
Since Pad(cyless- = Pea(syla;) Paales) Pba(c:), the chunks e; and cy chosen by the learning model will be the same ones as those created in the generative model.
End step: The chunk learning process stops once an independence test has been passed, which means that the sequence is better explained by the current set of chunks than any of the other possible next-step chunk combinations. This is the case once the chunk learning algorithm has learned belief set B. that is the same the generative alphahet set Ag. At this point g
25

---

Under review as a conference paper at ICLR 2022
E EXPERIMENT DETAIL: CHUNK RECOVERY AND CONVERGENCE
To test the model's learning behavior this type of sequential data, random graphs of chunk hi- erarchies with an associated occurrence probability for each chunk are specified by the hierarchical generative process. To do so, an initial set of specified atomic chunks Ao and a pre-specified level of depth (new chunks) d is used to initiate the generation of a random hierarchical generative graph G. In the end, the generative model generates set of chunks A. In total, there are |Apl + d number of chunks in the generative alphabet A, with chunk с from the alphabet set having an occurrence probability of PA (c) on the sample space
Once the hierarchical generative model is specified, it is then used to produce training sequences with varying length N test the chunk recovery.
The rational chunk model is trained on the the sequence S with increasing sizes (from 100 to 3000 with steps of 100) generated by the hierarchical generative graph, and it learns a hierarchical chunk- ing graph G. To test how good the representation learned by the chunking graph is compared to the ground truth generative model G. discrete version of Kullback-eeiller divergence is used to compare the ground truth probability Pa (c) of every chunk on the sample space the ground truth alphabet, to the learned probability Q(c) of the chunking model.
Pa(c) QA(c)
KL(PIIQ) P log2
(94)
CEA
While Pa is clearly defined by the generative model, (c(c) needs to be calculated from what the model has learned. Note that the set of chunks IB learned by HCM may may not be the same as A. as B also augments or shrinks in different learning stages.
To evaluate (c(c), the hierarchical chunk graph with their occurrence probability associated with each chunk is used to produce "imagined" sequences of length 1000. Imagined sequences are the sequences that HCM produces based on its learned representations. After that, the occurrence prob- ability of each chunk in ((c) is used to evaluate Q, comparing the HCM's learned representation with the ground truth.
KI. divergence is used to evaluate the deviation of learned representations in the hierarchical chunk- ing model from the original representations on the corresponding support set of the original repre- sentations.
For the comparsion, we used the same sequence used for training HCM train layer recurrent neural network (one embedding layer with 40 hidden units, one LSTM with drop-out rate 0.2, and one fully connected layer with batch size 5, sequence length for training is the same as N) of the training sequence, and used it to generate imagined sequences which are then used to calculate the KI. divergence as before.
epoch 1. that the data used
To generate the KL divergence plot for Figure 2 sequences with varying size N were used to train HCM. HCM was then used to generate imaginative sequence so that KL measurements can taken.
F EXPERIMENT DETAIL: VISUAL HIERARCHICAL CHUNKS
The visual hierarchical chunks are crafted by hand as binary arrays. The dark pixels correspond to having array value of and background a value of O. Each image in the generative hierarchy is 25 dimensional x 5) in the visual domain and size in the temporal domain. An empty array is included denote observation. The alphabet & of the generative model include all 14 the images in the generative hierarchy.
The probability of occurrance for each generative visual chunk is drawn from flat dirichlet distri- bution with the empty observation retaining the highest mass, this is to emulate the process that real world observatipons mostly sparse in the environment.
26

---

Under review as a conference paper at ICLR 2022
The parameters (a1,... ... (gk) with K = [A] are all set to one, and (c),), c1,..., CK & are sampled from the probability density function
K
fi,, Tbi a1 ax) =
II
0:
(95)
((a) 1=
I [(ar) and T a.)
Where the beta function when expressed using gamma function is: B(a) (a1...,kk))
To generate the sequence, images the hierarchy are sampled from the occurrence distribution and appended to the end of the sequence. As result, there are visual correlations in the sequence defined by the hierarchy, but temporally, each image slice is i..d. from the dirichlet distribution.
Examples of chunk representations learned by the hierarchical chunking model at different stages is shown are collected at the learning stages of = 10, = 100, t= 1000 respectively.
G EXPERIMENT DETAIL: GIF MOVEMENT
The gif file is converted into an [T x W] sized tensor. With T being the temporal dimension of the spatial vision sequence. The entire moment is 10 frames of 25 25 images. Each color in the gif file is mapped to a unique integer, with the background having a value of TO construct the training sequence for spatial temporal chunks. In this way, the gif file is converted into tensor with size 10x x 25 25. The entire movement repeated 100 times and trained on HCM.
H EXPERIMENT DETAIL: THE HUNGER GAMES
The first book The Hunger Games is stored as "tett_de dattddatta.. txt with the code in the supple- mentary material. The file contains approximately 520,000 characters in total.
To convert the book into temporal sequences, a unique mapping between each character and an integer is created. This sequence of integer is used to train the online HCM, with forgetting rate of 0.99 and chunk deletion threshold of le 5. Empty spaces are also mapped onto a nonzero integer enable the model learn chunks with the inclusion of empty spaces. The HCM trains on sequences of 1,000 characters in length at each step. More examples of learned chunks taken from M different stages of learning are displayed in Table Simple representation examples are taken from chunks learned after 10,000 characters in the book. Intermediate examples are taken after 100,000 characters have been parsed, and Complex chunks are taken when HCM reaches 300,000 characters of the book.
27

---

Under review as a conference paper at ICLR 2022
Table 2: Representation Learned in Hunger Games
Simple Chunks
'an', 'in 'be'. 'at'. 'me', 'le', "ar', 're', aand 've', 'ing', 'on', 'st', 'se", 'to ; 'i' 'n', "of", 'he', 'my 'te', 'pe', 'ou', 'we', 'dd'. 'de'. 'li', 'oo', 'bu', 'fo', "ave', 'the", 'ce", 'is'. 'as", ''s',"il' 'ch', 'al', 'no", 'she', 'ing'. 'am', "ack', "we", 'raw', 'on the", dddy',,",, 'ear', 'oug". 'bea', 'tree', 'sin', 'that', 'logg. "ters', "wood", 'now,, 'was', "even', 'leven', 'ater', 'ever', 'but', 'ith', 'ity", 'if" ,'te wood", 'bell', 'other' 'ol'', 'ather', as 'under. waa.., day'. 'hunger', 'very'. death "ping', 'the seam', 'add', 'ally'. 'king'. 'lose', 'sing', 'loser', 'money', 'man who', 'in the', 'says'. 'tome', 'might', 'rave', 'even', 'ick', 'wood', 'he want', 'for', 'into', 'leave', 'reg', 'lose to', 'lock', 'where', 'up". 'gale', 'older', "ask', "come', 'raw', 'real', 'bed', 'ing for', 'from'. 'link', 'few", 'close', "arrow', 'ull', 'cater', 'this', 'one', "almo", 'lack', 'shop'. 'year', 'ring', 'cause', 'is the', 'ugh', "eve". 'are', 'the leap'. 'Ily', 'still', 'heal', 'tow,, "never', 'try', 'prim', 'iting" 'bread', 'ould', but', 'Now', 'beg', 'liday', 'arm', 'quick, 'hot', 'men', "know", 'then', 'bell', 'pan', "mother', 'only,, 'war', "eak", "high', 'read', 'district 12', "can', 'would', 'pas'.
Intermediate Chunks
Complex Chunks
'arent', hhe may", 'I want', 'gather', 'capitol', "been', 'trip', baker', but', 'madge,, 'heir', 'mouth', 'you can', 'a few', 'berries', 'fully', 'tribute', 'I can', "cause of the", 'feel', "to the baker', 'its not just', 'he want', 'slim', 'hand', 'the ball', 'quick', 'green', 'the last', 'peace', 'off', 'you have to', 'kill', 'of the', 'the back', 'they', 'scomers' 'have been', 'reaping", "as well', but the 'cent', 'thing", remem- ber', "ally', 'though', 'again', 'dont', 'need', 'in the school', 'the pig', 'in our', 'them', 'to remember', 'fair, 'bother', "at the', 'older', 'the square', 'I know', 'house', 'its not', 'once', 'what was', "out of", 'it is not just', "our district', 'too', have', 'it out'
28


Reviews:
[{"review_id": "wTixXDmf7p", "reviewer": "Reviewer_mjpW", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "**Strengths**\n\n- I believe the paper's main strength lies in its motivation. I believe the core of the presented idea is compelling, and would be of interest to the community.\n- The paper is clearly written, and the method is simple.\n\n**Weaknesses**\n\n- The paper presents primarily qualitative results for the majority of datasets/tasks used. The experiment performed on a text corpora only presents a table of examples with learned chunks, and the visual-temporal experiment only presents a figure with some of the learned visual chunks. It is not clear to me from the presented experiments how to compare this method to alternatives. There is one experiment comparing against an RNN baseline, showing that HCM converges faster — however, RNNs are not the current SOTA in sequence modeling (i.e. why wasn't a transformer model used?).\n- I am concerned that the method as currently defined cannot generalize to real world data. HCM parses chunks from a sequence by matching them exactly to subsequences, which to me means that this method groups segments together purely based on form rather than semantics. My perspective is that the promise of hierarchical representations is that you can decompose complex objects and patterns into their parts (e.g. a person into [head, arms, legs] — head into [eyes, ear, nose], etc...). However, in modalities such as vision the same parts can appear with drastically different color values. The paper alludes to this in its Discussion section, but does not present a solution to this problem, which is something that I think would need to be shown.\n- Related to my point above, I'm not entirely sure I understood the thesis of the paper in terms of the narrative it is trying to convey, and would appreciate hearing the authors thoughts on this. Is this meant to be received as a paper for the cognitive science community, showing an operationalization of grouping by proximity? Or is it being presented for the machine learning community as a representation learning method for use in downstream tasks? If it's the former, I believe this work would be much more appropriately submitted at a cognitive science conference. If it's the latter, I believe much more empirical evidence of the learned representations' usage needs to be shown.\n- The related work section mainly focuses on historical NLP methods, with little discussion over similar methods in computer vision, which I believe is needed given that it presents experiments on visual data. I would suggest works such as:\n    - Normalized Cuts and Image Segmentation by Shi and Malik 2000\n    - Selective Search for Object Recognition by Uijlings et al. 2012\n    \n    as places to start. Additionally, I think work on unsupervised grammar induction could also be relevant here.", "summary_of_the_paper": "This paper presents HCM, an approach for chunking a sequence of data into a hierarchical representation. More specifically, HCM learns a tree with atomic units (ie the low-level inputs, in this case integers representing things like text characters or quantized pixel values) as the leaves and increasingly complex groupings of them higher up the tree. \n\nHCM learns by iteratively parsing the provided data (ie stream of tokens), in each pass computing marginals for the current set of chunks as well as transition frequencies between them. After updating its marginals and transition frequencies, the two chunks with highest joint probability are combined into one. The process continues until all pairs of chunks pass an independence test. \n\nI believe the main contribution of this paper is in that it presents an idea for interpretable grouping based on the principle of grouping by proximity from cognitive science, and a largely qualitative proof of concept for it.", "summary_of_the_review": "Although I believe the motivating idea is very compelling, I don't believe this paper is ready for publication. In summary, I believe the paper currently lacks: \n\n- More thorough empirical evaluations comparing against other methods.\n- Experiments showing the method's potential for generalizing to more naturalistic data, as well as its usefulness for downstream tasks.\n- A more clearly focused narrative motivating why it's appropriate for a venue like ICLR as opposed to a cognitive science publication, as well as more thorough contextualization among related work (particularly comparing against recent alternative methods for this problem).\n\nI thank the authors in advance for their response, and am also interested in seeing other reviewers' thoughts. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "mFiFOXmBtBR", "reviewer": "Reviewer_LNDm", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\nThe paper is clear. I rarely had trouble following, although I didn’t understand that the decision to chunk was based on a chi^2 test until I read the appendix, which seems crucial. I enjoyed reading about the relative sample efficiency of the classical algorithm vs the RNN, though I would have rather seen a fair comparison with a TreeRNN or some other system that involves latent tree structure, as well as a comparison to other classical dependency parsers. The application of a classic parsing algorithm to video was a nice adaptation.\n\nThe overall problem I had with this paper was the fact that it is presenting a classic parsing algorithm but contains no citations to any work from the age of classic parsing algorithms. I found this lack of background disturbing because as far as I can tell this algorithm is a statistical stack based parser, and the authors should have looked into whether they were reproducing existing work. The problems they have with efficiency of their own algorithm are resolved by many statistical parsing algorithms. Even allowing partial parses (as they do) is a property in a number of non neural parses such as https://www.cs.cmu.edu/~nschneid/twparser.pdf (A Dependency Parser for Tweets by Kong et al.). Ironically, I also had trouble looking for specific classical parsing algorithms to compare with this while reviewing, because the literature has exclusively contained neural parsing algorithms for so long. The general area of structured prediction is one that has a long history, and the authors seem not have a particular background in the problem space. I recommend reading Slav Petrov’s thesis (https://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-116.pdf) for a deep background on the topic from the age of classical parsing.\n\nAlthough the paper described the problem of a lack of inductive bias towards hierarchical parse structures, there were no citations to the literature which attempts to resolve this problem (treeRNNs, RNNGs, etc.). There was also no discussion of non-neural hierarchical algorithms for structured prediction on video (e.g., structured prediction cascades), which seems necessary in a paper with experiments on a non neural hierarchical algorithm for video.\n\nBeyond the lack of discussion of the existing field of algorithmic hierarchical parsing, the discussion of limitations does confront the possibility of non projective grammars, which cannot be covered by this sort of chunking (“How to relax the adjacency assumption as a grouping criterion to allow for non adjacent relationships to be chunked together remains an open challenge”), but does not to discuss it in terms that have been used historically in parsing, or acknowledge the existing parsers that cover non-projective cases. I was somewhat confused by the decision to use The Hunger Games as a corpus for training natural language parsers on, as there are a number of more common corpora that would have compared more easily to the existing literature (The Little Prince, PTB, or wikitext come to mind). I was confused by the reference to Teh 2006 alone as an extension of ngram models, given that there was no other discussion of backoff (e.g., Katz back-off, or smoothing) in ngram models, which has a much longer history. \n\nI was not surprised that introducing a parsing algorithm with a strong inductive bias was more sample efficient than using an RNN. This phenomenon is the reason why, for years, NLP did not use neural networks until large quantities of data and compute became easily available.\n\nMINOR\n\nPlease explain how the hypothesis testing works in the main text of the paper, and not just in the appendix, or at least emphasize appendix A in the main text of the paper while describing the algorithm.\n\nTypos:\n“they the way”\nHinton (1979) should be a parenthetical but is instead inline citation.\n\n Questions: \n\nHow does catastrophic interference relate to gradient starvation?", "summary_of_the_paper": "This paper proposes a non neural system of parsing natural language text by chunking sequences to form hierarchical structures. The algorithm strongly resembles classical parsing algorithms. Decisions about when to chunk a phrase into a constituent are based on chi^2 tests of independence, where a pair of chunks that are considered to be dependent are joined into a single constituent. They test this chunking algorithm on natural language data against an RNN,  concluding that the classical parsing algorithm is more sample efficient in achieving a low KL-divergence from the true sequence data. They also provide some examples of how this algorithm can be applied to temporal image data or video.", "summary_of_the_review": "This paper is missing significant background on classic hierarchical structured prediction. Because it is presenting a classical parsing algorithm without a single citation to pre-neural structured prediction as a field, I believe that it is extremely similar to existing algorithms that are rarely in use today.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dii89aXe-V7", "reviewer": "Reviewer_zfT1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n- This paper is particularly well-written and understandable. I appreciated the intuitive explanations of chunking in cognitive science and its extension to common machine learning use cases like language and visual data. The examples of instances where hierarchical chunk learning could both help and hurt a learned model were well-chosen. The figures effectively demonstrated the training process and the learned representations in each domain. Even the theorems were more interpretable than I typically see, being subdivided and laid out piece by piece.\n- The method is reasonably novel and broadly applicable. The paper shows HCM applied to temporal, visual, visuo-temporal, and language domains. Given a domain with some hierarchical structure, a fairly reasonable assumption, this method is able to find that hierarchy with some guarantees. The learned hierarchy itself, as the authors note in the conclusion, could be applied to down-the-line endpoints such as -causal learning.\n- This method really leans into explainability/interpretability and could thus be more compatible in human-ML frameworks\n\nWeaknesses:\n- While the method is novel and seems to recover structure quite well, the results are not as convincing as I’d like.  To lay this out:\nGiven a toy generative hierarchical model, HCM is able to more effectively predict sequences than a basic RNN, particularly as the levels of hierarchy increased. Not to be too glib, but I should hope so!\n\n- In an environment where the HCM representations overlap with the underlying model, it outperforms a learned-from-scratch HCM, while in the opposite case, it underperforms. The authors suggest that the nature of the HCM (as compared to something like a DNN) allows users to understand a priori whether their pretrained model will work well, which I agree with\n- In toy visual domains with and without temporal correlations, HCM learns reproduces the underlying representations. But how does its ability to reproduce the actual sequences compare with appropriate baselines.\n\n- Finally, HCM is applied to a corpus from the Hunger Games and is able to learn commonly-repeated phrases over time.\n\nMy main concern with all of this is the lack of actual baselines. I agree that the models are interpretable and useful, but they aren’t applied to any previously-used datasets or compared (empirically) to other SOTA methods. HCM doesn’t necessarily need to *win* in performance, given its other advantages, but I’d like to see whether it’s competitive\n\n- On a related note, the authors provide both idealized and online HCM algorithms. Even the “online” algorithm, while theoretically tractable, seems practically quite slow, which I assume is why the chosen domains are simple. While the online algorithm seems to work well for these domains, I would imagine the loss of guarantees is more likely to be impactful in harder domains.\nIt was not clear to me how the chunks were generated until I read the independence tests section in the appendix, and I think that this is too important to push out of the body of the paper. It also introduces the hyperparameter of statistical significance p, which isn’t really discussed.\n", "summary_of_the_paper": "This paper proposes a method for learning representations of non- i.i.d. data in terms of hierarchical sets of chunks, inspired by cognitive theories of grouping by proximity. These sets are assembled over time from the initial set of primitive data points by finding correlations between temporally/spatially sequential primitives/chunks and appending to the set. The authors show that this learning method is tractable, has convergence w.r.t. hierarchically-decomposable problems, and learns intuitively and practically reasonable chunk sets.", "summary_of_the_review": "I like this algorithm and think it has potential. I can see how it can be applied both to standard ML tasks, but also how it could unlock a more symbiotic human-ML collaboration through its interpretability. The motivation and build-up from cognitive science is clear, and all else aside, because of its writing, I felt this paper gave me a lot more valuable insights than most. That said, I’m just not convinced by the current set of experiments. I can’t glean how well HCM will *actually* perform (vs. baselines on standard datasets), particularly the online variant, and I suspect it’s not computationally that practical either. With some of these comparisons added, I think I could accept, but for now it’s a reject from me.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4o4QVslSUV", "reviewer": "Reviewer_1Nwa", "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": "Strengths:\nThe paper is very well written, with very clear, intuitive explanations for how their method works, and justifications for the authors’ design choices.\n\nThe paper provides several well-considered experiments to demonstrate the HCM method quantitatively and qualitatively. First, purely sequential data is generated from several random (but known) heirarchically-structured graphs and the HCM method is shown to learn this underlying hierarchical structure well, compared to a vanilla RNN. Secondly, the paper verifies that the learned model shows positive and negative transfer to similarly or differently structured heirarchical environments, as might be expected from a chunk learning algorithm. Fianlly, the paper explores how the HCM model performs qualitatively in spatial, spatiotemporal or english-language chunking, with interpretable (although unquantified) results in each.\n\nThe connections to animal chunk learning are well thought through. Interestingly, for the case of spatiotemporal chunking, without considering a priori the spatial proximity of pixels, spatially connected chunks are learned. So it is by virtue of the fact that objects tend to move smoothly in space and time that online HCM will learn to group visual spatial chunks smoothly in the height x width plane too. This has really interesting close ties to theories for animal learning of object permanence (although obviously the implementation is very different), as the authors note.\n\nWeaknesses:\n\nThe paper mentions that this method should offer more interpretable learned representations, but for what sort of task or application is this envisaged? Regarding the transfer of learned chunks to new data sequences, it seems that a human (or other model) would have to know the underlying generative process of the target data sequence in order to know whether the original learned chunking model should work well in the new setting or not (unless of course, the data is generated from the exact same process as the training data). If a human (or other model) knows that then is it not true that you don’t need the model to do the chunking in the first place?\n\n\nIt would have been nice to see quantitative demonstrations of performance for the spatial, spatiotemporal and language-chunk learning experiments. I appreciate its not immediately obvious what the right metric for this performance would be (at least to me), but if the authors were willing and able to find an appropriate one and use this to compare their method to other chunk-learning algorithms it would definitely strengthen the paper.\n\nIn the learning plots vs the vanilla RNN, the paper would also have benefitted from comparisons to other explicit chunk-learning algorithms.\n", "summary_of_the_paper": "The paper proposes a graph-learning model (HCM) for learning hierarchical chunks from sequential data. The paper first proposes an idealised HCM method, for which the paper provides learning guarantees via a proof by induction, and an online approximation to this idealised method, which is more computationally feasible and which is used to perform experiments in temporal, visual, visuotemporal and language sequential data domains. The paper demonstrates that the online method learns interpretable chunks at multiple levels of abstraction and demonstrates positive (and negative) transfer to other hierarchically structured environments with similar (and different) structures.", "summary_of_the_review": "A well-written description of a method for a chunk-learning algorithm, with learning guarantees and qualitative demonstrations of sensible-looking chunks across a variety of domains. Quantification of results was a bit lacking.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper develops an approach to learning hierarchical representations from sequential data. The reviewers were very positive about the overall approach, finding it well motivated and interesting with strong potential, and thought that the paper was extremely well written with clear examples throughout. There was a good back-and-forth between the reviewers and the authors, discussing several aspects of the paper and providing constructive suggestions for improvement. In particular, the reviewers suggested improvements in terms of independence testing, comparison to further baselines, further experiments, and other improvements as detailed in the reviews. The authors were extremely receptive of these suggestions, which is to be commended and is very much appreciated, and in a response state that they are planning to take the time needed to revise this paper before publication.
Decision: Reject