Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: 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 al., 2016) to predicting the structure of the human proteome (Jumper et al., 2021), 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. Specifically, deep learning models suffer from a lack of interpretability since ANNs are sub-symbolic, nested, non-linear structures. This means they the way predictions are generated can be difficult to understand (Samek et al., 2017; Ribeiro et al., 2016; Doshi-Velez & Kim, 2017). Furthermore, deep learning models can also struggle to learn hierarchical representations 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 resemble 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 grouping by proximity. To get an intuition for chunking, try to read through the following sequence of letters: “DFJKJKJKDFDFJKJKDFDF”. 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 as 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 & Steele, 2012; Rosenbaum et al., 1983), and in visual structures Hinton (1979); Brady et al. (2009); Egan & Schwartz (1979). The extracted chunks have been argued to facilitate memory compression (Gobet et al., 2001; Miller, 1956), compositional
generalization (Schulz et al., 2017), predictive processing (Koch & Hoffmann, 2000; Müssgens & Ullén, 2015), and communication (Schulz et al., 2020).
In the current work, we propose a 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 is a dynamical graph that is a 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.

heading: 2 HIERARCHICAL CHUNKING MODEL
text: When talking about chunks in a sequence, a chunk is defined as a unit created by concatenating several atomic sequential units together. Take the training sequence shown in Figure 1a as an example. The sequence consists of discrete, size-one atomic units from an atomic alphabet A0: in this case A0 = {0, 1, 2}. A chunk c is made up of a combination of one or more atomic units in A0\{0}. 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 submelodies in a 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 can be perceived one chunk at
a time, instead of one sequential unit at a 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.
More formally, HCM acquires a belief set B of chunks, and uses chunks from the belief set to parse the sequence one chunk at a time. HCM assumes that a sequence is generated from samples of independently occurring chunks with probability of PB(c) evaluated on the belief set B. The probability of observing a sequence of parsed chunks c1, c2, ..., cN can be denoted as P (c1, c2, ..., cN ) = ∏ ci∈B PB(ci). 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 is 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 a hierarchically structured sequence as illustrated in Figure 1a, HCM gradually builds up a hierarchy of chunks starting from an empty belief set. It first identifies a set of atomic chunks to construct its initial belief set B. 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 M(ci) for each chunk ci in B, a vector with size |B| and the transition frequency T between chunk ci followed by chunk cj , as illustrated in Figure 1b. 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 cR have a significant adjacency dependence based on their entries in M and T , they are chunked together to become cL ⊕ cR, which augments the belief set B by one. One example of chunk merging is shown in Figure 1c.
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 1 and 2 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 dependent 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.

heading: 2.1 HCM BUILDS REPRESENTATIONS FROM THE GROUND UP
text: As HCM learns from a sequence, it starts with no representation and gradually builds up the representations which can be readily interpreted at any learning stage. The representation can be described by a chunk hierarchy graph Ĝ with the vertex set being the chunks and edges pointing from chunk constituents to the constructed chunks. Shown in Figure 1d is the gradual build-up of one such chunk hierarchy graph as the model learns from a training sequence coming from the generative hierarchy displayed in Figure 1a. At t = 10, HCM learns only the atomic chunks, at t = 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.

heading: 3 HIERARCHICAL GENERATIVE MODEL
text: To study learning guarantee of the HCM, a generative model with a random hierarchy of chunks is constructed. The relation between chunks and their constructive components in the generative model is described by a chunk hierarchy graph Gd with vertex set VAd and edge set EAd . One example is illustrated in Figure 1a. Ad is the set of chunks used to construct the sequence. The depth d specifies the number of chunks created in the generative process.
Starting with an initial set of atomic chunks A0, at the i-th iteration, two chunks cL, cR are randomly chosen from the current set of chunks Ai and are concatenated into a new chunk cL⊕cR, augmenting Ai by one to Ai+1. Meanwhile, an independent occurrence probability is assigned to each chunk under the condition that the probability of occurrence for every new chunk ci in the construction process evaluated on the support set Ai carries the largest probability mass.
To generate a 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.

heading: 3.1 LEARNING GUARANTEE
text: Theorem: As the length of the sequence approaches infinity, HCM learns a hierarchical chunking graph Ĝ isomorphic to the generative hierarchical graph G. Proof Sketch: 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 to form its initial belief set. This procedure guarantees that Ĝ0 = G0. 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 Bi at step i contains the same chunks as the alphabet set Ai 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 a chunk to extend the belief set: this chunk is the same chunk node created by the hierarchical 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 = Ad.

heading: 3.2 LEARNING CONVERGENCE
text: 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 d. Figure 2a displays an example of a random generative hierarchy with a depth of d = 3. We used the Kullback-Leibler 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 2b shows the KL-divergence between the learned and ground-truth distribution for different depths d of the generative 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 to the generative model.
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 training sequence increased, the KL-divergence also converged but at a much slower rate. Note that HCM’s competitive advantage increased further as the depth of the generative hierarchy increased. Thus, HCM learns quickly about the hierarchical generative model and does so faster than a neural network.

heading: 3.3 HCM PERMITS TRANSFER BETWEEN ENVIRONMENTS WITH OVERLAPPING STRUCTURE
text: 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 Gi and Gj from their past experience. These might lie on the graph construction path (G0,G1,G2, ...,Gd). The HCM with a chunk hierarchy graph ‘closer’ to the ground truth chunk Gd on the path, takes fewer iteration to arrive at Gd. This also applies when the chunk hierarchies starting out are not along the graph construction path but only showing partial overlap.
Similarly, the chunk hierarchy Gi learned by an HCM might facilitate its performance in a new environment where Gi lies along the graph construction path to the true Gd, i.e. there is partial overlap between the chunk hierarchies. We demonstrate this in Figure 3. Here, HCM was trained on a random hierarchical generative model and acquired the representation shown in Figure 3a. Knowing this representation, we also know that an environment with a hierarchical generative graph as shown in Figure 3b allows for positive transfer, i.e. the HCM that already contains the chunk hierarchy Figure 3a would learn faster than a naive one by transferring its previously learned chunks. As shown in Figure 3c, the trained HCM learns faster than a naive HCM which had to learn about the structure from scratch.
Vice versa, we might have a 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 3d. The shaded chunks need to be learned anew by the HCM trained on Figure 3a, yet the previously acquired chunks might mislead HCM causing it to adapt to the new environment more slowly. As a result, the performance of the pre-trained HCM suffers more from an interfering environment than a naive HCM (Figure 3e). 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 is that with visibility into the chunks learned, we have a better a priori sense of whether transfer 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 a naive model.

heading: 4 GENERALIZING TO VISUAL TEMPORAL CHUNKS VIA THE PRINCIPLE OF PROXIMAL GROUPING
text: Humans are not only able to identify sequential chunks but also to find structure in 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 to one another appear to form groups (Wagemans et al., 2012). This principle has been argued to play a key role in human perceptual grouping (Compton & Logan, 1993) and benefit working memory (Peterson & 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 can be seen as 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 to also learn visual temporal chunks.
Visual temporal chunks not only subsume temporal length but also varying visual slices in each temporal slice. One can imagine visual temporal chunks as having a 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 are 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 temporal volume is chosen to explain parts of the visual-temporal observations. Multiple visual temporal chunks can be identified to occur simultaneously. Starting at the visual temporal time point marked by the previous chunk, chunks are identified and stored in M . The transition matrix T is modified to 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. A hypothesis test is conducted every time when a pair of adjacent chunks are identified, chunks that violate the hypothesis test are grouped together to augment the belief set which is then used to parse future sequences.

heading: 4.1 LEARNING PART-WHOLE RELATIONSHIP BETWEEN VISUAL COMPONENTS
text: We let HCM learn chunks in a visual domain by learning from a sequence of images. To this end, a hierarchical generative model in the pixel-wise image domain shown in Figure 4a 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 in the hierarchy occurred independently according to a draw from a Dirichlet flat distribution. To 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.
HCM learns a hierarchy of visual chunks from a sequence of visually correlated but temporally independent images sampled from the visual hierarchical model. Shown in Figure 4b are the chunk representations learned by HCM at different stages. Having no knowledge about the image parts before starting to learn, HCM acquires the individual pixels as chunks to explain the observations. As HCM proceeds with learning, visual correlations among the pixels are discovered and larger chunks are formed. As the number of observations increases, the model learns more sophisticated yet still interpretable chunks.

heading: 4.2 LEARNING VISUAL-TEMPORAL MOVEMENT HIERARCHIES
text: Instead of seeing one image after another sampled from an independent, identically distributed distribution, real world experiences contain correlations in 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 objects together as a whole (Bill et al., 2020). To emulate this type of environment as a learning task, an animated GIF of a squid swimming in the sea as shown in Figure 5a was used as a visual-temporal sequence to 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 5b and c. There are visual-temporal chunks that mark movements of a tentacle and the rising-up motion of a bubble. Additionally, there are visual chunks that resemble a part of the squid’s eye and face.

heading: 5 LEARNING CHUNKS FROM REALISTIC LANGUAGE DATA
text: We so far have only shown demonstrations of HCM learning chunks on simple sequences. Thus, one step further is to run HCM on real world datasets that contain complex hierarchical structures. One immediate testbed containing such structures is natural language. To this end, we trained HCM to 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 preand 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 as “come”, “sing”, “leave”, “try”; nouns such as “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 as “prim”, “death”, “hunger”, and “district 12”.
After having seen 300,000 characters of the book, HCM learns more 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”.

heading: 6 RELATED WORK
text: 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-Schreiber & Anderson, 1990; Perruchet & Vinter, 1998), as well as models that can extract chunks from visual inputs (Mareschal & French, 2016). HCM can be viewed as a principled version of these earlier cognitive models because it uses hypothesis testing in its decision to chunk elements together instead of using chunking heuristics. Therefore, HCM comes with learning guarantees for a fairly general class of hierarchically structured 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-parametric extension of n-gram models has been put forward (Teh, 2006). A Bayesian non-parametric n-gram model builds up structure as evidence is accumulated. That is, it flexibly reduces to a 1-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 Teh (2006)’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 a similar vein, extending 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 computational tractability of simple Markov processes, they still lack the adaptive recombination and reuse of pre-existing components. Fragment grammars (O’Donnell et al., 2009) address this by balancing 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 era of deep learning, both natural language processing and image processing became increasingly dominated by neural networks, with one of their primary tasks being the extraction and prediction of chunks (Zhai et al., 2017; Si et al., 2020; Ortmann, 2021). Commonly, these so-called
sequence chunks are used as units of segmentation for other downstream tasks such as text translation. 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 as an interpretable and transparent alternative to neural networks for some of these tasks.
A final related line of research attempts to learn explicit representations by inducing programs (Lake et al., 2015). Fore example, in a recent approach to this challenge, the interpretable structures returned by program induction algorithms was combined with a deep neural network to learn meaningful representations from data (Ellis et al., 2021). Yet in these approaches the retrieved representations are highly dependent on the initial set of building blocks which are usually specified by the experimenter. HCM, in comparsion, is task-agnostic and requires no primitive program description.

heading: 7 DISCUSSION
text: We have proposed the Hierarchical Chunking Model (HCM) as a cognitively-inspired method for learning representations from the ground up. HCM starts out by learning atomic units from sequential data which it then chunks together, gradually building up a hierarchical representation that can be expressed as a 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 a 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 are 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 to 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 in the sequences. This feature was inspired by the Gestalt principle of grouping by proximity. Yet many patterns observed 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 a grouping criterion to allow for non-adjacent relationships to be chunked together remains an open challenge. Furthermore, HCM currently assumes that there is a hierarchy of chunks which occur independently in the observational sequence. This set-up was intended to be a simplifying assumption for a first approach toward building a 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 a 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 on whether or not to chunk, although other statistical tests are conceivable. One general class of tests could be to assess whether or not chunks are causally related with each other, in an attempt to find the best causal structure to explain the sequential, observational data Heinze-Deml et al. (2018). This would make HCM a useful model of causal representation learning (Schölkopf et al., 2021).

heading: 8 REPRODUCIBILITY STATEMENT
text: Detailed information about the HCM algorithm, proof, generative model, independence test and experimental details and results can be found in the supplementary information section. The code used for the algorithm and experiments will be available as a comment to the reviewers and area chairs as a link to an anonymous repository as soon as the discussion forum for all submitted papers is open.

heading: B RATIONAL CHUNKING ALGORITHM
text: Algorithm 1: Rational Chunking Algorithm input : Seq, maxIter output: Bd, Ĝd, Td, Md d← 0, iter ← 0; Bd, Md, Td = getSingleElementSets(Seq); /* minimally complete atomic set */ while !IndependenceTest(Md, Td) or iter ≤ maxiter do Md, Td = Parse(Seq, Bd); cL, cR ← None; MaxChunk,MaxChunkP ← None; PreCk = {}; for (ci, cj) ∈ Bd\{0} × Bd\{0} do
Pd(ci ⊕ cj) = CalculateJoint(Md,Td, ci, cj); Pd+1(ci ⊕ cj) = Pd(ci⊕cj)1−Pd(ci⊕cj) ; if Pd+1(ci ⊕ cj) ≥ MaxChunkP and ci ⊕ cj /∈ PreCk and !IndependenceTest(ci, cj)
then cL ← ci, cR ← cj ; MaxChunkP ← Pd+1(ci ⊕ cj), MaxChunk ← ci ⊕ cj
end end c← cL ⊕ cR; Bd+1 ← Bd ∪ c; Ĝd+1 ←AugmentGraph(Ĝd, (cL, c), (cR, c)); PreCk.add(c);
end

heading: C ONLINE HCM WITH GENERALIZATION TO VISUAL-TEMPORAL SEQUENCES
text: HCM learns a chunk hierarchy graph Ĝ by training on a visual-temporal sequence. The visualtemporal chunks can 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 input chunk hierarchy graph Ĝ could be an empty graph which corresponds to the case that the HCM model has not been trained yet, or it can be a chunk hierarchy graph that HCM has acquired from training. M contains the frequency count of each chunk in the belief set B. 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. It then keeps checking whether adjacent chunks in 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̂, θ, DT output: Ĝ M , T ← Ĝ.M , Ĝ.T ; PreviousChunkBoundaryRecord← []; /* Record Chunk Endings */ ChunkTerminationTime.setall(-1); while Sequence not over do
CurrentChunks, ChunkTerminationTime = IdentifyTheLatestChunks(ChunkTerminationTime); ObservationToExplain← refactor(Seq, ChunkTerminationTime); for Chunk in CurrentChunks do
for CandidateAdjacentChunk in PreviousChunkBoundaryRecord do if CheckAdjacency(Chunk, CandidateAdjacentChunk) then
M ,T ,B, Ĝ ← LearnChunking(Chunk, CandidateAdjacentChunk. M ,T ,B, Ĝ);
end end ChunkTerminationTime.update(CurrentChunks)
end PreviousChunkBoundaryRecord.add(CurrentChunks); Forgetting(M ,T ,B, Ĝ, θ, DT , PreviousChunkBoundaryRecord);
end
The pseudocode for the Visual-Temporal HCM is shown in Algorithm 2. The input can be a visualtemporal sequence, an i.i.d visual sequence, or a temporal sequence.
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 ChunkTerminationTime. ChunkTerminationTime 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. Because 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 one or several chunks are identified to be ending at a time point, they are stored inside the PreviousChunkBoundaryRecord and their finishing time is updated for each visual pixel in ChunkTerminationTime. Corresponding entries in M are updated upon once a chunk has ended. The chunks
that finishes after the start of the current chunk is checked with each current chunk on whether there is a visual temporal adjacency. Additionally, the independence test between adjacent chunk pairs are carried out for the decision to possibly merge chunks.
Once a pair of adjacent chunks cL cR violates the independence testing criterion, they are combined into one chunk cL⊕ cR. A new entry is created in M with the estimated joint occurrence frequency for cL ⊕ cR, which is subtracted from the marginal record of cL and cR. The transition entries associated with cL ⊕ cR are initialized to be 1. Other chunks inherit the transition entries from cR 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 on their adjacencies.
Entries in M and T are subject to memory decay at the rate of θ. If any entry goes below the deletion threshold DT , their corresponding entries in M , T , B and Ĝ are deleted.

heading: D DETAILS TO THE PROOF OF RECOVERABILITY
text: D.1 DEFINITIONS
An observational sequence is made up of discrete, integer valued, size-one elementary observational unit coming from an atomic alphabet set A0, where 0 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 A0 = {0, 1, 2}. Definition 1 (Chunk)

heading: A chunk is composed of several non-empty, concatenated elementary observations, embedded in the
text: sequence. That is, a chunk can be made up from any combination of elements in A0 \ {0}
Examples of chunks from the observational sequence can be ‘1’, ‘21’, ‘211’, ‘12’, ‘2112’, ... etc. 0 represents an empty observation in the sequence.
Definition 2 (Belief Set)

heading: A belief set is the set of chunks that the HCM uses to parse training sequences. The belief set is denoted as B.
text: An example of a belief set that that the model has learned from S could be B = {0, 1, 21, 211, 12, 2112}. 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 is chosen to explain the observation. The end of the previous chunk parse initiates the next parse.
The sequence S parsed by the model that uses the belief set {0, 1, 21, 211, 12, 2112} results in the following partition. 0 1 0 0 21 0 0 2112 0 0 0.
We say that a belief set is complete if at any point when the model parses the sequence, the upcoming observations can be explained at least by one chunk within the belief set.
In this work, we only refer to complete belief sets.
Definition 4 (Parsing Length NB)

heading: A parsing length NB of a sequence parsed by a belief set B is the length of the parsing result after the sequence has been parsed by chunks within B.
text: Definition 5 (Count Function NB(c)) NB(c) denotes the count of how many times the chunk c in the belief set B appears in the parsed sequence.
The parsing length and the count function for all of the chunks c on a belief set B satisfy the following relation:
NB = ∑ c∈B NB(c) (3)
Definition 6 (NB(x → y)) The number of times chunk x is being parsed following the parse of chunk y. x and y are both chunks in the belief set B.
For any chunk x within any belief set B, one can relate NB(x) with NB(x→ y) by: NB(x) = ∑ y∈B NB(x→ y) (4)
When the length of the sequence becomes infinite, it is easier to work with probabilities instead of the count function. One can define a probability space over the belief set:
Definition 7 (Probability space of a belief set) With a belief set B, one can define a associated probability space (SB,FB,PB). SB is the sample space representing all of the possible outcomes of a chunk parse. An event space F is the space for all possible sets of events. F contains all the subsets of SB. Additionally, the probability function PAB : FB → R is defined on the event space SB. The probability function PAB satisfies the basic axioms of probability:
• PAB(E) ≥ 0 ∀E ∈ F . For any subset in the event space, the probability of an observation being in the subset is positive.
• M,N ∈ F , andM ∩N = E, then P (M ∪N) = 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 to the sample space is one.
The probability of a chunk c on a support set of chunks B, is the limiting case of this ratio when NB goes to infinity.
PB(c) = lim NB→∞
NB(c)
NB (5)
A learning model keeps track of the occurrence probability associated with each chunk in the belief set. For a current belief set, the model assumes that the chunks within the belief set occurs independently.
The occurrence probability of chunk ci with the belief set Bd is PBd(ci), which refers to the normalized frequency of observing chunk ci 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 c1, c2, ....cN can be denoted as P (c1, c2, ....cN ). The joint probability of observing any chunk in the generative process is:
P (c1, c2, ....cN ) = ∏ ci∈Bd PBd(ci) (6)
In this formulation, chunks as observation units serve as independent factors that disentangle observations in the sequence.
Definition 8 (Marginal Parsing Frequency Md) A vector that stores the number of parses for each chunk c in the belief set Bd.
Md contains size |Bd|. 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 9 (Td) The set of transition frequency from any chunk ci ∈ Bd to cj ∈ Bd
Definition 10 (Chunk Hierarchy Graph Gd) The relation between chunks and their constructive components in the generative model is described by a chunk hierarchy graph Gd with vertex set VAd and edge set EAd . One example of a chunk hierarchy graph is illustrated in Figure 1 a). In this hierarchical generative model, d is the depth of the graph and Ad is the set of chunks used as atomic units to construct the sequence. Each vertex in VAd 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 NB and the probability associated with the belief set PAB . Based on the definition of 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 of N to the constraints on probability updates.
We derive the relation between the probabilities when two chunks cL and cR ∈ Ad are concatenated together to form a new chunk cL ⊕ cR and update the alphabet to Ad+1.
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 Ad to Ad+1, and proceed to the update for the marginal N, and then the transitional N.
D.2.1 SUMMARY N
When going from Ad to Ad+1, cL and cR 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 cL and cR associated with the new chunk occurs. The chunks in Ad can be divided into three groups, cL, cR, and Ad \ {cL, cR}. The count function associated with chunks from the set Ad \ {cL, cR} does not change when Ad updates to Ad+1.
Since with the chunk update Ad+1, cL and cR are chunked together, they are recognized together as a whole, so every time when they are recognized together as a whole, the count reduces twofold. Nd+1(cL) and Nd+1(cR) are the number of counts for cL and cR when they do not occur together. This count is different from Nd(cL) and Nd(cR) because the occasions when they occur one after another is taken into the count by Nd+1(cL ⊕ cR). The relation between Nd and Nd+1 is:
Nd+1 = [ ∑ c∈Ad−cL−cR Nd(c) ] +Nd+1(cL) +Nd+1(cR) +Nd+1(cL ⊕ cR) (7)
Nd+1(cL) could occur in the case where cR does not follow cL. Nd+1(cL ⊕ cR) = Nd(cL → cR) (8)
Nd+1(cL) = Nd(cL)−Nd(cL → cR) (9) Nd+1(cR) = Nd(cR)−Nd(cL → cR) (10)
Nd+1(cL ⊕ cR) ∗ 2 +Nd+1(cL) +Nd+1(cR) = Nd(cL) +Nd(cR) (11) Chunking reduces the number of times sub-chunks are being parsed when sub-chunks occur right after each other by twofold.
Nd = ∑ c∈Ad Nd(c) = [ ∑ c∈Ad−cL−cR Nd(c) ] +Nd(cL) +Nd(cR) (12)
Comparing the above two equations we arrive at Nd −Nd(cL)−Nd(cR) = Nd+1 −Nd+1(cL)−Nd+1(cR)−Nd+1(cL ⊕ cR) (13)
Since: Nd(cL) +Nd(cR) = Nd+1(cL) +Nd+1(cR) + 2Nd+1(cL ⊕ cR) (14)
This is related to: Nd(cL → cR) = Nd+1(cL ⊕ cR) (15)
Because both are counting the number of times they occur consecutively. Nd+1(cL) +Nd+1(cR) = Nd(cL) +Nd(cR)− 2Nd(cL → cR) (16)
One can define Nd+1 in terms of counts in Nd as:
Nd+1 = [ ∑ c∈Ad−cL−cR Nd(c) ] +Nd(cL) +Nd(cR)− 2Nd(cL → cR) +Nd(cL → cR)
Nd+1 = [ ∑ c∈Ad−cL−cR Nd(c) ] +Nd(cL) +Nd(cR)−Nd(cL → cR)
(17)
Generally, the result is also the case with the total count Nd and Nd+1 when one switches from the alphabet set Ad to Ad+1 by chunking cL and cR in Ad together.
Nd+1 = [ ∑ c∈Ad−cL−cR Nd(c) ] +Nd(cL) +Nd(cR)−Nd(cL → cR) (18)
Nd+1 = Nd −Nd(cL → cR) (19)
D.2.2 MARGINAL N
To proceed into formulating the joint and conditional probability given a particular belief space, we need to formulate how the count of N(c) for a chunk changes when the belief space when switching from Ad to Ad+1, with the same division as before.
Of course, the count function should be 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 x in Ad − {cL, cR, cL ⊕ cR}:
Nd+1(x) = Nd(x) (20)
Nd+1(cR) = Nd(cR)−Nd(cL → cR) (21) Nd+1(cL) = Nd(cL)−Nd(cL → cR) (22) Nd+1(cL ⊕ cR) = Nd(cL → cR) (23)
D.2.3 TRANSITIONAL N
The following relationship needs to hold:
for all x, y in Ad \ {cL, cR, cL ⊕ cR}:
Nd+1(x→ y) = Nd(x→ y) (24)
Nd+1(x→ cL) = Nd(x→ cL)−Nd+1(x→ cL ⊕ cR) (25) Nd+1(x→ cR) = Nd(x→ cR) (26)
Nd+1(x→ cL ⊕ cR) = Nd+1(x)−Nd+1(x→ cR)−Nd+1(x→ cL)−Nd+1(x→ y) (27) Nd+1(x→ cL ⊕ cR) ≤ Nd(cL → cR) (28)
From cL we have this relation.
Nd+1(cL → x) = Nd(cL → x) (29)
Nd+1(cL → cL) = Nd(cL → cL)−Nd+1(cL → cL ⊕ cR) (30) Nd+1(cL → cR) = 0 (31)
Nd+1(cL → cL⊕ cR) = Nd+1(cL)−Nd+1(cL → cR)−Nd+1(cL → cL)−Nd+1(cL → x) (32) Nd+1(cL → cL ⊕ cR) ≤ Nd(cL → cR) (33) Nd+1(cL → cL ⊕ cR) ≤ Nd(cL → cR) (34)
From cR we have the following relation:
Nd+1(cR → y) = Nd(cR → y)−Nd+1(cL ⊕ cR → y) (35)
Nd+1(cR → cL) = Nd(cR → cL)−Nd+1(cL ⊕ cR → cL) (36) Nd+1(cR → cR) = Nd(cR → cR)−Nd+1(cL ⊕ cR → cR) (37)
Nd+1(cR → cL⊕cR) = Nd+1(cR)−Nd+1(cR → cR)−Nd+1(cR → cL)−Nd+1(cR → y) (38) Nd+1(cR → cL ⊕ cR) ≤ Nd(cL ⊕ cR) (39)
From the chunked unit cL ⊕ cR we have the following relation: Nd+1(cL ⊕ cR → x) ≤ min(Nd(cL ⊕ cR), Nd+1(cR ⊕ x)) (40) Nd+1(cL ⊕ cR → cL) ≤ min(Nd(cL ⊕ cR), Nd(cR ⊕ cL)) (41)
Nd+1(cL ⊕ cR → cR) ≤ min(Nd+1(cL ⊕ cR), Nd+1(cR ⊕ cR)) (42) Nd+1(cL ⊕ cR → cL ⊕ cR) ≤ min(Nd+1(cL ⊕ cR), Nd(cR ⊕ cL)) (43)
Finally, we need to satisfy the marginal constraint, that is:
Nd+1(cL⊕cR) = Nd+1(cL⊕cR → cL)+Nd+1(cL⊕cR → x)+Nd+1(cL⊕cR → cR)+Nd+1(cL⊕cR → cL⊕cR) (44)
D.3 PROBABILITY DENSITY SWITCH WHEN Ad EXPANDS TO Ad+1
The constraint is: the number of counts N for all chunks defined for the support set Ad must remain the same for the support set sAd+1, so that the definition of PAd for all relevant chunks within Ad remains the same when Ad expands to Ad+1.
Relating the number of counts to probability: The probability of a chunk occurring in the alphabet set Ad is defined as:
PAd(c) = lim Nd→∞
Nd(c)
Nd (45)
Because Nd and Nd+1 are only a constant away, both go to infinity if one of them does, so there is a relation between the definition of probability PAd(c) and PAd+1(c). For any chunk x in Ad that is not cL and cR, Nd+1(x) = Nd(x):
PAd+1(x) = lim Nd+1→∞
Nd+1(x)
Nd+1 = lim Nd→∞
Nd(x)
Nd −Nd(cL → cR) (46)
That is, the probability of a chunk of this category at d and d+1 satisfies this relationship:
lim Nd+1→∞ PAd+1(x)Nd+1 = lim Nd→∞ PAd(x)Nd (47)
PAd+1(x) = PAd(x) limNd→∞Nd
limNd+1→∞Nd+1 (48)
PAd+1(x) = PAd(x) limNd→∞Nd
limNd+1→∞Nd −Nd(cL → cR) (49)
For cL and cR in Ad+1:
PAd+1(cL) = lim Nd+1→∞
Nd+1(cL)
Nd+1 (50)
PAd(cL) = lim Nd+1→∞
Nd(cL)
Nd (51)
PAd+1(cR) = lim Nd+1→∞
Nd+1(cR)
Nd+1 (52)
PAd(cR) = lim Nd→∞
Nd(cR)
Nd (53)
Because: Nd+1(cL) = Nd(cL)−Nd(cL ⊕ cR) (54)
PAd+1(cL) = lim Nd+1→∞ Nd(cL)−Nd(cL ⊕ cR) Nd+1
(55)
PAd+1(cL) = lim Nd→∞ Nd(cL)−Nd(cL → cR) Nd −Nd(cL → cR)
(56)
PAd+1(cR) = lim Nd→∞ Nd(cR)−Nd(cL → cR) Nd −Nd(cL → cR)
(57)
Finally:
PAd+1(cL ⊕ cR) = lim Nd+1→∞ Nd+1(cL ⊕ cR) Nd+1
(58)
PAd(cL ⊕ cR) = lim Nd→∞ Nd(cL → cR) Nd
(59)
since Nd(cL → cR) = Nd+1(cL ⊕ cR), we have
PAd+1(cL ⊕ cR) = lim Nd→∞ PAd(cL ⊕ cR)Nd Nd+1
(60)
D.3.1 SUMMARY PROBABILITIES
Nd+1 = Nd −Nd(cL ⊕ cR) = Nd −NdPd(cL ⊕ cR) (61) Nd+1 Nd = 1− Pd(cL ⊕ cR) (62)
D.3.2 MARGINAL PROBABILITIES
The constraints on marginal probabilities when the support set changes from Ad to Ad+1, derived from the constraints on the marginal counts, are the following:
Pd+1(x) = Pd(x)
1− Pd(cL ⊕ cR) (63)
Pd+1(cR) = Pd(cR)− Pd(cL ⊕ cR)
1− Pd(cL ⊕ cR) (64)
Pd+1(cL) = Pd(cL)− Pd(cL ⊕ cR)
1− Pd(cL ⊕ cR) (65)
Pd+1(cL ⊕ cR) = Pd(cL ⊕ cR)
1− Pd(cL ⊕ cR) (66)
With this set of formulations, we have defined the next level marginal probability measures as a function of the previous level observations and their implied probability measures.
D.3.3 TRANSITIONAL PROBABILITIES
for all x, y in Ad − {cL, cR, cL ⊕ cR}, from x we have this relation:
0 ≤ Pd+1(·|x) ≤ 1 (67)
Pd+1(y|x) = Pd(y|x) (68) Pd+1(cR|x) = Pd(cR|x) (69)
Pd+1(cL|x) + Pd+1(cL ⊕ cR|x) = Pd(cL|x) (70) This equation is sampled so that both Pd+1(cL|x) and Pd+1(cL ⊕ cR|x) satisfy the following constraints:
Pd+1(cL|x) ≤ Pd+1(cL)
Pd+1(x) (71)
Pd+1(cL ⊕ cR|x) ≤ Pd+1(cL ⊕ cR)
Pd+1(x) (72)
Basically, Pd+1(cL|x) is sampled from the range [ 0,min{1, Pd+1(cL)Pd+1(x) , Pd(cL|x)} ] . Additionally, Pd+1(cL ⊕ cR|x) is constrained to be within this range:[ 0,min{1, Pd+1(cL⊕cR)Pd+1(x) , Pd(cL|x)} ] .
From cL we have this relation:
Pd+1(x|cL) = Pd(x|cL)
1− Pd(cR|cL) (73)
Pd+1(cR|cL) = 0 (74)
Pd+1(cL|cL) = Pd(cL|cL)− (1− Pd(cR|cL))Pd+1(cL ⊕ cR|cL)
1− Pd(cR|cL) (75)
Put into simplified terms:
Pd+1(cL|cL) + Pd+1(cL ⊕ cR|cL) = Pd(cL|cL)
1− Pd(cR|cL) (76)
Pd+1(cL|cL) ≤ Pd+1(cL)
Pd+1(cL) = 1 (77)
Pd+1(cL ⊕ cR|cL) ≤ Pd+1(cL ⊕ cR) Pd+1(cL)
(78)
Additionally, Pd+1(cL|cL) is constrained to fall within this range: [ 0,min{1, Pd(cL|cL)1−Pd(cR|cL)} ] .
Pd+1(cL ⊕ cR|cL) within the range [ 0,min{1, Pd+1(cL⊕cR)Pd+1(cL) , Pd(cL|cL) 1−Pd(cR|cL)} ] From cR we have the following relation:
0 ≤ Pd+1(·|cR) ≤ 1 (79)
Pd+1(y|cR) = Pd(y|cR)Pd(cR)− Pd+1(y|cL ⊕ cR)Pd(cL ⊕ cR)
Pd(cR)− Pd(cL ⊕ cR) (80)
Pd+1(cL|cR) = Pd(cL|cR)Pd(cR)− Pd+1(cL|cL ⊕ cR)Pd(cL ⊕ cR)
Pd(cR)− Pd(cL ⊕ cR) (81)
Pd+1(cR|cR) = Pd(cR|cR)Pd(cR)− Pd+1(cR|cL ⊕ cR)Pd(cL ⊕ cR)
Pd(cR)− Pd(cL ⊕ cR) (82)
Pd+1(·|cR) ≥ Pd+1(·|cL ⊕ cR) (83)
Additionally, Pd+1(cL ⊕ cR|cR) and Pd+1(cL ⊕ cR|cL ⊕ cR) needs to satisfy:
Pd+1(cL ⊕ cR|cR) = 1− Pd+1(y|cR)− Pd+1(cR|cR)− Pd+1(cL|cR) (84)
Pd+1(cL ⊕ cR|cL ⊕ cR) = 1−Pd+1(y|cL ⊕ cR)−Pd+1(cR|cL ⊕ cR)−Pd+1(cL|cL ⊕ cR) (85)
For the generative model, when the alphabet set goes from Ad to Ad+ 1 by chunking cL and cR together, the above constraints associated with chunks in Ad and Ad+1 need to be satisfied.
D.4 HIERARCHICAL GENERATIVE MODEL
At the beginning of the generative process, the atomic alphabet set A0 is specified. Another parameter, d, specifies the number of additional chunks that are created in the process of generating the hierarchical chunks. Starting from the alphabet A0 with initialized elementary chunks ci from the alphabet, the probability associated with each chunk ci in A0 needs to satisfy the following criterion:∑
ci∈A0
PA0(ci) = 1 (86)
Meanwhile, P (ci) ≥ 0, ∀ci ∈ A0. 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 construction in the generative model follows the rule that the combined chunk with the biggest probability on the support set of pre-existing chunk sets is chosen to be added to the set of chunks.
cL ⊕ cR = argmax cL,cR∈Ad\{0} PAd(cL ⊕ cR) (87)
Under the constraint that:
PAd(cL)PAd(cR) ≤ PAd(cL ⊕ cR) ≤ min{PAd(cL), PAd(cR)} (88)
This can be calculated from the transitional and marginal probability of the previous step.
cL ⊕ cR = argmax cL,cR∈Ad\{0} PAd(cL ⊕ cR) = argmax cL,cR∈Ad\{0} PAd(cL)PAd(cR|cL) (89)
Once the chunk of the next step: cL⊕cR is chosen, the support set changes from Ad to Ad+1, which is one size bigger. On the new support set, the marginal probability is specified by the marginal update. That is, the marginal and transitional probability defined on the support set Ad fully specifies the marginal probability of the support set Ad. Going from generating a new chunk from the support set Ad to the set Ad+1, the transitional probabilities between chunks in Ad need to satisfy the following constraints:
• PAd+1(cL|x) + PAd+1(cL ⊕ cR|x) = PAd(cL|x) for all x in Ad • PAd+1(cL|cL)(1− PAd(cR|cL)) + PAd+1(cL ⊕ cR|cL)(1− PAd(cR|cL)) = PAd(cL|cL) • PAd+1(y|cR)(PAd(cR) − PAd(cL ⊕ cR)) + PAd+1(y|cL ⊕ cR)PAd(cL ⊕ cR) = PAd(y|cR)PAd(cR) • PAd+1(cL|cR)(PAd(cR) − PAd(cL ⊕ cR)) + PAd+1(cL|cL ⊕ cR)PAd(cL ⊕ cR) = PAd(cL|cR)PAd(cR) • PAd+1(cR|cR)(PAd(cR) − PAd(cL ⊕ cR)) + PAd+1(cR|cL ⊕ cR)PAd(cL ⊕ cR) = PAd(cR|cR)PAd(cR)
• Pd+1(cL ⊕ cR|cR) = 1− Pd+1(y|cR)− Pd+1(cR|cR)− Pd+1(cL|cR) • Pd+1(cL⊕ cR|cL⊕ cR) = 1−Pd+1(y|cL⊕ cR)−Pd+1(cR|cL⊕ cR)−Pd+1(cL|cL⊕ cR)
In total, there are |x| + |y| + 3 degrees of freedom. Since |x| = |y| = |Ad| − 2, at each step, there are 2|Ad| − 1 number of values to be specified. In practice, after the chunks are specified in Ad, the probability value associated with chunks in A0 are sampled from a flat Dirichlet distribution, which is then sorted so that the smaller sized chunks contain more of the probability mass and the null-chunk carries the biggest probability mass. Then, the above constraint is checked for the assigned probability on each of the newly generated chunk with their associated alphabet set Ai. 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 cd,i ⊕ cd,j and the change of probability, PAd is still a valid probability distribution. Proof: ∑ cd,k∈Ad PAd(cd,k) = ∑ cd,k∈Ad−1−cd−1,i−cd−1,j PAd−1(cd−1,k)+
+ PAd−1(cd−1,i)− PAd−1(cd−1,j |cd−1,i)PAd−1(cd−1,i) + PAd−1(cd−1,j) + PAd−1(cd−1,j |cd−1,i)PAd−1(cd−1,i) = 1
(90)
Theorem 2 (Conditional Probability Space Preservation). The conditional probability Pd+1(z|c) for any c ∈ Ad+1 after sampling is still a valid distribution. Proof: Show by manipulating the equations, that the sum of the conditions on c sums to 1, and each of them is bigger than 0.
Theorem 3 (Measure Space Preservation). Given that at the end of the generative process with depth d one ends up having an alphabet set Ad, the probability space defined on Ai, which includes the marginal and joint probability of any chunk and combinations of chunks in Ai, i = 0, 1, 2, . . . d, which are predecessor alphabet sets of Ad, all values in the set Md and Td 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 A0, the probability of PA0(c), c ∈ A0, and the probability of PA1(xy), x, y ∈ A0, for all valid c, x, y, when the alphabet is A1. Going from A0 to A1, N0(c), N0 and N0(x → y) does not change, therefore PA0(c) and PA0(x→ y) at the alphabet A1 is the same as that when the alphabet is A0.
• Induction Step: starting from the initialized alphabet set Ad, the probability of PAd(c), c ∈ Ad, and the probability of PAd(xy), x, y ∈ Ad, for all valid c, x, y, when the alphabet is Ad+1. Going from Ad to Ad+1, Nd(c), Nd and Nd(x → y) does not change, therefore PAd(c) and PAd(x→ y) at the alphabet Ad+1 is the same as that when the alphabet is Ad.
Theorem 4. The order of PAi(xy), x, y ∈ Ai for any i = 0, 1, 2, . . . d at 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: Ad. The probability space defined on Ai, which includes the marginal and joint probability of any chunk and combinations of chunks in Ai, i = 0, 1, 2, . . . d is preserved, hence the order is preserved.
The generative process can be described by a graph update path. The specification of the initial set of atomic chunks A0 corresponds to an initial graph G0 with the atomic chunks as its vertices. At the i-th iteration, as the generative graph goes from GAi to graph GAi+1 , two none zero chunks cL, cR chosen from the pre-existent set of chunks Ai and are concatenated into a new chunk cL ⊕ cR,
augmenting Ai by one to Ai+1. The vertex set also increments from VAi to VAi+1 = VAi ∪ cL ⊕ cR. Moreover, two directed edges connecting the parental chunks to the newly-created chunk are added to the set of edges: EAi to EAi = EAi ∪ (cL, cL⊕ cR)∪ (cR, cL⊕ cR). The series of graphs created during the chunk construction process going from GA0 to the final graph GAd with d constructed chunks can be denoted as a graph generating path P (GA0 ,GA0) = (GA0 ,GA1 ,GA2 , ...,GAd).
D.5 LEARNING THE HIERARCHY
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 → ∞, the chunk construction graph learned by the model Ĝ is the same as the chunk construction graph of the generative model: Ĝ = G, which entails that they have the same vertex set: V̂ = VG and the same edge set: Ê = EG . Additionally, the belief set learned by the chunk learning model Bd = Ad, and the marginal probability evaluated on the learned belief set MBd associated with each chunk is the same as the marginal probability imposed by the generative model on the generative belief set MAd . Proof: Given that all of the empirical estimates are the same as the true probabilities defined by the generative model, we prove that starting with B0, the learning algorithm will learn BD = AD. 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 elementary atomic chunks learned by the model is the same as the elementary alphabet imposed by the generative model, i.e. B0 = A0. Hence, the root of the graph, which contains the nodes without their parents, is the same, Ĝ = G; put differently, V̂0 = V0
Additionally, the learning model approximates the probability of a specific atomic chunk as P̂A0(ai). As n→∞, for all chunks c in the set of atomic elementary chunks in B0, the empirical probability evaluated on the support set is the same as the true probability assigned in the generative model with the alphabet set A0:
P̂B0(c) = lim n→∞
N0(c)
N0 = PA0(c) (91)
Induction hypothesis: Assume that the learned belief set Bd at step d contains the same chunks as the alphabet set Ad in the generative model.
The HCM, by keeping track of the transition probability between any pairs of chunks, calculates P̂Bd(ci|cj) for all ci, cj in Bd. Afterwards, it finds the pair of chunks ci, cj , such that the chunk created by combining ci and cj together contains the maximum joint probability violating the independence test as candidate chunks to be combined together.
P̂Bd(ci ⊕ cj) = sup ci,cj∈Bd P̂Bd(ci)P̂Bd(cj |ci) (92)
We know that in the generative step the supremum of the joint probability with the support set Ad 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:
PAd(ci ⊕ cj) = sup ci,cj∈Ad PAd(ci)PAd(cj |ci) (93)
Since PAd(cj |ci) = P̂Bd(cj |ci), PAd(ci) = P̂Bd(ci), the chunks ci and cj 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 a belief set Bd that is the same as the generative alphabet set Ad. At this point Ĝ = G

heading: E EXPERIMENT DETAIL: CHUNK RECOVERY AND CONVERGENCE
text: To test the model’s learning behavior on this type of sequential data, random graphs of chunk hierarchies 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 A0 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 a set of chunks A. In total, there are |A0|+ d number of chunks in the generative alphabet A, with chunk c from the alphabet set having an occurrence probability of PA(c) on the sample space A.
Once the hierarchical generative model is specified, it is then used to produce training sequences with varying length N to 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 chunking graph Ĝ. To test how good the representation learned by the chunking graph is compared to the ground truth generative model G, a discrete version of Kullback–Leibler divergence is used to compare the ground truth probability PA(c) of every chunk on the sample space of the ground truth alphabet, to the learned probability Q(c) of the chunking model.
KL(P ||Q) = ∑ c∈A PA(c) log2( PA(c) QA(c) ) (94)
While PA is clearly defined by the generative model, QA(c) needs to be calculated from what the model has learned. Note that the set of chunks B learned by HCM may or may not be the same as A, as B also augments or shrinks in different learning stages.
To evaluate QA(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 probability of each chunk c in A(c) is used to evaluate Q, comparing the HCM’s learned representation with the ground truth.
KL divergence is used to evaluate the deviation of learned representations in the hierarchical chunking model from the original representations on the corresponding support set of the original representations.
For the comparsion, we used the same sequence used for training HCM to train a 3 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 = 3, epoch = 1, so that the data used 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 KL divergence as before.
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 be taken.

heading: F EXPERIMENT DETAIL: VISUAL HIERARCHICAL CHUNKS
text: The visual hierarchical chunks are crafted by hand as binary arrays. The dark pixels correspond to having a array value of 1 and background a value of 0. Each image in the generative hierarchy is 25 dimensional (5 x 5) in the visual domain and size 1 in the temporal domain. An empty array is included to denote no observation. The alphabet A 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 a flat dirichlet distribution with the empty observation retaining the highest mass, this is to emulate the process that real world observatipons are mostly sparse in the environment.
The parameters (α1, .., αK) with K = |A| are all set to one, and PA(c), c1, ..., cK ∈ A are sampled from the probability density function
f(x1, ..., xk;α1, ..., αK) = 1
B(a) K∏ i=1 xαi−1i ) (95)
Where the beta function when expressed using gamma function is: B(a) = ∏K i=1 Γ(αi)
Γ( ∑K i αi) , and a =
(α1, .., αK).
To generate the sequence, images in the hierarchy are sampled from the occurrence distribution and appended to the end of the sequence. As a result, there are visual correlations in the sequence defined by the hierarchy, but temporally, each image slice is i.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 t = 10, t = 100, t = 1000 respectively.

heading: G EXPERIMENT DETAIL: GIF MOVEMENT
text: The gif file is converted into an [T x H x W] sized tensor. With T being the temporal dimension of the spatial vision sequence. The entire moment is 10 frames of 25 x 25 images. Each color in the gif file is mapped to a unique integer, with the background having a value of 0. TO construct the training sequence for spatial temporal chunks. In this way, the gif file is converted into a tensor with size 10 x 25 x 25. The entire movement is repeated 100 times and trained on HCM.

heading: H EXPERIMENT DETAIL: THE HUNGER GAMES
text: The first book of The Hunger Games is stored as ’test_data.txt’ with the code in the supplementary material. The text file contains approximately 520,000 characters in total.
To convert the book into a 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 a forgetting rate of 0.99 and a chunk deletion threshold of 1e−5. Empty spaces are also mapped onto a nonzero integer to enable the model to 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 at different stages of learning are displayed in Table 2. 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.

Review summaries:
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.   HCM 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.   I 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.

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.

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.

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.