# Superregular grammars do not provide additional explanatory power but allow
for a compact analysis of animal song

Takashi Morita<EMAIL_ADDRESS>Hiroki Koda<EMAIL_ADDRESS>
###### Abstract

A pervasive belief with regard to the differences between human language and
animal vocal sequences (_song_) is that they belong to different classes of
computational complexity, with animal song belonging to regular languages,
whereas human language is superregular. This argument, however, lacks
empirical evidence since superregular analyses of animal song are
understudied. The goal of this paper is to perform a superregular analysis of
animal song, using data from gibbons as a case study, and demonstrate that a
superregular analysis can be effectively used with non-human data. A key
finding is that a superregular analysis does not increase explanatory power
but rather provides for compact analysis: Fewer grammatical rules are
necessary once superregularity is allowed. This pattern is analogous to a
previous computational analysis of human language, and accordingly, the null
hypothesis, that human language and animal song are governed by the same type
of grammatical systems, cannot be rejected.

Keywords: animal song $|$ gibbon $|$ language $|$ Bayesian analysis $|$
context-free grammar

##  1 Introduction

Language is often considered a property unique to humans, in contrast with
other animal behavior such as birdsong [7, 47, 6]. It is a commonly held
belief that human language and animal vocal sequences (which we term _song_
herein) belong to different classes of computational complexity. Animal song
belongs to the class of regular languages and is modeled by regular
expressions, finite-state automata, and left/right-branching grammars. Human
language, on the other hand, requires superregular analyses. This argument,
however, is not supported by empirical evidence, since superregular analyses
of animal song are significantly understudied. In particular, only regular
analyses have been performed in the original studies on animal song cited by
proponents of the argument [7, 47, 6]: e.g., Song of Bengalese finch—the most
popular example discussed in the literature—has been analyzed with $n$-gram
models [25], $k$-reversible finite-state automata [31], and hidden Markov
models [34], which are all regular and no study has yet assessed superregular
models. The goal of this paper is to perform a superregular analysis of animal
song and demonstrate that it can be applied to realistic non-human data. Song
data from gibbons were used, since the gibbon is an ape known for its long
vocal sequences [43, 20, 36]. This superregular analysis does not increase
explanatory power but, instead, provides a compact analysis, since fewer
grammatical rules are necessary once superregularity is included. This is in
accordance with the previous computational analysis of human language that is
reviewed in the next section. Given this, the null hypothesis that human
language and animal song are governed by the same kind of grammatical systems
cannot be rejected.

##  2 Preliminaries

A classic argument for the superregularity of human language is based on a
mathematical result from formal language theory. This argument assumes that
human language allows an unbounded depth of the center-embedding schematized
as $\textrm{N}^{m}\textrm{V}^{m}$ where N and V stand for noun and verb
(phrases) respectively and $m\in\mathds{N}$ represents the number of repeats.
For example, _The mouse died._ ($m=1$), _The mouse [the cat chased] died._
($m=2$), _The mouse [the cat [the dog bit] chased] died._ ($m=3$), …. Under
the assumption of unbounded center-embedding, human language is non-regular
[52, 1]. However, this is empirically unsupported since the depth of center-
embedding observed in corpora is $m\leq 3$ [33] and sentences with multiple
center-embedded clauses are extremely hard for people to process or accept
[11, 42, 19]. These empirical results imply that we would have little chance
of observing center-embedding in animal data even if the system behind the
data has a superregular architecture.

A better empirical argument for the superregularity of human language—in a
sense that the approach is more easily applicable to animal studies—comes from
probabilistic analysis. Perfors et al. showed that probabilistic context-free
grammar (PCFG), which is a superregular language model, is more probable for
the analysis of child-directed speech than regular grammars in the posterior
[51]. This finding is significant as it provides an important advantage of
PCFG analysis, which becomes visible when we decompose the posterior
probability. Using Bayes’ Theorem, it is found that the posterior probability
$p(g\mid d)$ of a grammar $g$ given data $d$ is proportional to the product of
the prior probability $p(g)$ of $g$ and the likelihood $p(d\mid g)$ of $d$
given $g$. Thus, taking the log of the probabilities:

$\displaystyle\log p(g\mid d)=\log p(g)+\log p(d\mid g)-\log p(d)$
$\displaystyle(-\log p(d)\textrm{ is the normalizing constant.})$

The likelihood encodes the grammars’ explanatory power of the data. The prior,
on the other hand, evaluates the compactness of the grammars, with smaller
grammars being more probable. Table 1 shows the log prior, likelihood, and
posterior (minus the constant normalizer term; i.e., the sum of the log prior
and likelihood) of the best PCFG and regular grammar found by Perfors et al.
The advantage of the PCFG over the regular grammar in the posterior comes from
the prior, not the likelihood. In other words, the empirical advantage of a
PCFG analysis of human language is not that it can explain more data than
regular grammars, even though hypothetical data exist that can be explained
only by superregular grammars (unbounded center-embeddings). Instead, PCFG is
a more compact analysis of human language than regular grammars.

Probability Type | PCFG | Regular
---|---|---
Log Prior | -1,111 | -1,943
Log Likelihood | -25,889 | -25,368
Total $=$ Log Posterior (- Normalizer) | -27,000 | -27,311
Table 1:  Log prior, likelihood, and posterior (minus the normalizing
constant) probabilities of PCFG and the regular grammar reported in [51].
Scores of the best grammars (“CFG-L” for PCFG and “REG-B” for regular) are
cited.

(a) Non-Regular

(b) Left-Branching (Regular)

(c) Right-Branching (Regular)

Figure 1:  Possible parses of a string of length 4. The terminal vertices at
the bottom of the tree graphs correspond to the individual data points of the
string.

##  3 Overview of the Materials & Methods

In this section, we outline our materials and methods. Technical details are
available later in the Materials & Methods section.

The data subject to the grammatical analysis are sequences of acoustic feature
vectors (mel-frequency cepstrum coefficients), measured at representative data
points of gibbon song recordings. This data format is different from outputs
of the standard PCFG: a PCFG outputs string of discrete symbols (called
_terminals_), such as words in human language syntax. Accordingly, we extend
the standard PCFG with multivariate Gaussian emission from terminals [cf. 38].
To generate a data sequence, our model first generates a string of terminals
using PCFG. Then, a Euclidean vector is generated according to a multivariate
Gaussian conditioned on each of the terminals. Our analysis can be viewed as a
joint inference of (i) the discrete categories—corresponding to the
terminals—of the acoustic feature tokens and (ii) the grammar behind the
sequential patterns of the categories. While these two components have been
analyzed in separate steps in the previous studies on animal song [25, 50, 31,
34, 35], simulation studies of human language learning have shown that a joint
inference of multiple aspects of the target language—capturing their
correlations—is more successful than separate learning of the components [27,
44, 29, 18]. Hence, we consider that the joint analysis is more reliable than
the previous two-step analysis.

A PCFG consists of grammatical production rules associated with probability of
their use. A challenge in a PCFG analysis of animal data is that we do not
know a particular set of grammatical rules appropriate for the data as well as
probability of the rules. In the current study, we take a Bayesian inference
approach to this problem, estimating the posterior probability distribution
over PCFGs (both rules and their probability) conditioned on the gibbon data.
Importantly, regular grammars are a special case of PCFG that only generate
either the left-branching (Figure 1(b)) or right-branching (Figure 1(c))
structures. Hence, the posterior tells us how much probable regular grammars
are among PCFGs given the gibbon data.

There are infinitely many sets of context-free grammatical rules, and thus it
is not appropriate to assume the uniform prior over all the possible PCFGs
(improperness). This study adopts the hierarchical Dirichlet process (HDP) for
the prior over PCFGs [40, 41]. The HDP prior introduces a bias for _compact_
PCFGs: It assigns exponentially smaller prior probability to PCFGs whose
production probability mass are spread over a greater number of grammatical
rules, favoring those with a smaller number of reusable rules. The Bayesian
inference balances the PCFG likelihood (fit to the data) and the HDP prior
(compactness), and the posterior probable PCFGs are those that can generate
the data with high probability while reusing a limited number of production
rules. Similar balancing between the explanatory power (likelihood) and
compactness (prior) is widely adopted in scientific evaluation of models [54,
3, 23] as well as modern theories of learning [53, 58, 39, 51].

In practice, it is difficult to directly measure the posterior probability of
the regular and non-regular grammars (even with the help of approximation of
the posterior). Accordingly, we will report the expected counts of regular and
non-regular parses of the training data and held-out test data based on the
posterior. The logic is as follows: If the regular grammars are the only
probable accounts of the gibbon data in the posterior, then only the regular
parses of the data would have large expected counts. We will show that the
expected counts of non-regular parses are not small at all in reality (in
comparison with the counts of regular parses as well as a random baseline),
and thus non-regular grammars are unignorably probable analyses of the gibbon
data, countering the previous argument for their regularity [7, 47, 6].

The analysis outlined above will show that non-regular grammars are probable
analyses of the gibbon data. However, it would not tell us what made the non-
regular grammars probable: (i) Did the non-regular grammars enable better fit
to the data (explanatory power)?; (ii) Did the non-regular grammars allow for
a more compact explanation of the data, using a more limited variety of
production rules (compactness)? To address these questions, we will further
diagnose the induced posterior inference of PCFGs by comparing it with that of
hidden Markov models (HMMs) induced from the same data and the HDP prior [2,
40]. HMMs restrict possible grammars to the regular ones, and the comparison
helps us understand what kinds of contribution the non-regular grammars—only
possible when the hypothesis space is the PCFGs—make to the posterior
inference. The question about explanatory power of the non-regular grammars
(i) is addressed by comparing the PCFG- and HMM-based posterior predictive
probability of the held-out test data. The compactness of grammars (ii) is
evaluated by the expected type counts of production rules used for a PCFG/HMM
to generate the training data.

##  4 Results

###  4.1 Posterior Inference of PCFG

The “total” bar of Figure 2(a) shows the expected counts of left-branching,
right-branching, and non-regular parses of the training data. The parse of the
data strings shorter than 3 is unique and regular (both left- and right-
branching), and their counts are reported separately (“length$<$3”). A total
of $48.00\%$ of the training data ($1328.08$ strings of the total $N=2767$)
are expected to have non-regular parses. The ratio increases to $86.97\%$ when
we focus on the strings of a length of at least 4 ($N=1527$), for which non-
regular parses are logically possible. Note that these large proportions are
not due to the broader variations of non-regular parses than regular parses:
In other words, it is not the case that all the possible parses are almost
uniformly probable (i.e., induction failure) and the
$\frac{1}{l}\binom{2(l-1)}{(l-1)}-2$ non-regular parses of each string (whose
length is represented by $l$) ganged up against the only two regular parses.
We can see this from the “optimal” bar of Figure 2(a), which shows the
expected counts of the Bayes-optimal parses (with the greatest posterior
probability) [41]. The expected counts of the optimal parses tell us how
confidently the data were parsed: e.g., if a data string has a unique probable
parse ($=$ optimal parse), the expected count of that parse is almost $1$. If
all the possible parses of the data string are equally probable, on the other
hand, the expected count of the optimal parse is only
$l\binom{2(l-1)}{(l-1)}^{-1}$. Figure 2(a) shows that the expected counts of
the non-regular optimal parses of the training data are $717.35$ and smaller
than the total expected counts of the non-regular parses—meaning that there
was some uncertainty in the parsing. However, the expected counts of the non-
regular optimal parses are still an order of magnitude greater than the
uniform baseline ($56.11$, represented by the “uniform baseline” bar of Figure
2(a)). The expected counts of the non-regular optimal parses are also greater
than those of the left-branching parses ($105.92$ in total, $37.80$ for the
optimal) and the right-branching parses ($315.00$ in total, $378.33$ for the
optimal).

A similar pattern was observed with the held test data (Figure 2(b)). A total
of $54.13\%$ of the entire data ($3974.86$ strings of the total $N=7343$) and
$88.23\%$ of the strings of a length of at least 4 ($N=4505$) are expected to
have non-regular parses. The expected counts of the non-regular optimal parses
are $1895.36$, an order of magnitude greater than the uniform baseline
($166.23$). The expected counts of the non-regular optimal parses are also
greater than those of the left-branching parses ($217.72$ in total, $61.51$
for the optimal) and the right-branching parses ($886.42$ in total, $1144.21$
for the optimal).

In summary, the results suggest that a large portion of the gibbon data was
parsed in non-regular ways, and thus non-regular grammars are unignorably
probable analyses of the data in the posterior.

(a) Training Data  (b) Test Data

Figure 2:  Expected counts of parses of the training (2(a)) and test (2(b))
data. The “total” bar shows the total expected counts of each parse type. The
“optimal” bar shows the expected counts of the optimal parses. The “uniform
baseline” bar shows the expected counts of the non-regular parses under the
assumption of the uniform distribution over the logically possible parses of
each data string.

###  4.2 Predictive Power

Figure 3 shows the distribution of the log posterior predictive probability
density of the test data divided by the string lengths (and thus “per data
point”) with the induced PCFG (mean: $-42.900044$, std: $3.421662$) and HMM
(mean: $-42.797174$, std: $3.535390$). The mean density of the PCFG is
slightly smaller than that of the HMM. This generalization holds even when we
focus on the long-string portion of the data, whose length is 4 or greater and
non-regular parses are possible ($N=4505$; mean: $-41.954381$ and std:
$1.886496$ with PCFG; mean: $-41.794641$ and std: $1.964568$ with HMM). This
indicates that the non-regular parses allowed by the PCFG did not provide
extra predictive power beyond the regular parses produced by the HMM.

Figure 3:  Log per-data-point posterior predictive probability density of test
data ($N=7343$) with PCFG and HMM.

###  4.3 Compactness

Table 2 reports the expected type counts of production rules used for a
PCFG/HMM to generate the training data: PCFG is expected to generate training
data with 52 (counted with $\mathds{1}[\cdot\geq 1]$) or 77 (with $\tanh$)
fewer rules and thus allows for a more compact analysis than HMM.

Activation Function | HMM | PCFG
---|---|---
$\geq 1$ | 274.000000 |  222.000000
$\tanh$ | 307.523023 | 230.429057
Table 2:  Expected type counts of production rules used for a PCFG/HMM to
generate training data. The type counts were calculated in two ways by
applying the step function $\mathds{1}[\cdot\geq 1]$ and
$\tanh\left*\cdot\right\lparen$ to the expected token frequency of rules.

##  5 Discussion and Conclusion

The parse induction result shows that non-regular parses were more probable
latent structures of gibbon song than the regular parses. This implies a
superregular strong generative capacity of the gibbon’s grammar, which
contradicts the previous opinion that regular grammars are sufficient to
analyze animal song [7, 47, 6]. We neither claim that the gibbon is an
exceptional species that exhibits a superregular system (due to, for example,
its phylogenetic closeness to humans compared to songbirds) nor that the
superregular vs. regular boundary is contiguous between primates and non-
primates. Superregular analyses of animal song are currently understudied, and
thus, it is an open question whether such analyses are appropriate for other
specific species.

Given that animal song and human language both deserve a superregular
analysis, their comparative studies could be more meaningful for our
understanding of human language evolution than previously claimed by
theoretical linguists [6]. The skepticism on the effectiveness of such
comparative studies was based on the assumption that animal song was regular
and thus there was no hope to find grammatical similarities between human
language and animal song. By analyzing human language and animal data with the
same class of grammars, we would obtain a deeper understanding of their
similarities and differences, which could in turn help us build a more
sophisticated theory of human language evolution.

Another key finding in the present study is that PCFG does not improve fit to
the gibbon data in comparison with HMM. Instead, the advantage of the
superregular analysis of gibbon song is its compactness: Fewer rules are
necessary to analyze the data if non-regular parses are allowed. Note that
this pattern is consistent with previous observations of human syntax: A PCFG
is more probable than HMMs/regular grammars given human language sentences,
because it reduces the grammar size and thus enables greater prior
probability, even though its predictive power (i.e., likelihood) is smaller
[51]. The importance of the compactness metric in grammar evaluation has long
been emphasized in the field of theoretical linguistics (by the proponents of
the regular vs. superregular difference between animal song and human
language) [14, 5]. However, the previous studies of animal song have evaluated
models solely by the predictive power of the data [34, 35], and the
compactness metric has been overlooked. For future studies on animal song
syntax, it is important to remember that the advantages of PCFG and other
superregular hypotheses may be expressed in the form of compactness/greater
prior, rather than improved model explanatory power or likelihood. Bayesian
inference and similar approaches (e.g., minimum description length [23, 39])
combine the two metrics in a mathematically natural way.

Finally, note that the (posterior distribution of) PCFG induced here is not
guaranteed to match the actual system behind gibbon song. The induced PCFG is
just a computationally optimal hypothesis for the gibbon data at this point,
and its biological validity should be assessed in future experimental studies
(e.g., callback experiment). Moreover, our hypothesis space was still limited
to the class of PCFGs, whereas the actual gibbon grammar might go beyond the
context-free generative capacity. Sticking to the same PCFG hypothesis space
in future studies would lead to the same error as the previous assumption of
regularity. Importantly, linguists have suggested that (P)CFG is insufficient
to fully describe human language [26, 16], and that at least mildly context-
sensitive computational power is necessary [30]. The recent success of
language models based on recurrent neural networks further implies that some
aspects of linguistic data are better captured by a more powerful, Turing-
complete architecture. PCFG itself has also been improved so that it better
captures frequently recurring structural patterns [28]. We—researchers of
animal song—should open our eyes to these more recent achievements in
computational and theoretical linguistics and adopt the new analytical
techniques to make the comparative studies more fruitful.

##  6 Materials & Methods

###  6.1 Data

We recorded songs of three male gibbons in captivity at the Primate Research
Institute, Kyoto University. One was an agile gibbon (_H. agilis_ , age: 44 y
or older), and the others were hybrids of _H. agilis_ and _H. albibarbis_
(age: 19 & 18 y). (Note that _H. albibarbis_ was long considered a subspecies
of _H. agilis_ [43, 12] until a recent DNA study [24], and thus, the two
species are phylogenetically similar.) The songs were originally recorded on
an eight-channel microphone array (TAMAGO-03, System in Frontier, Inc., with
the FPGA customized such that $-12$ dBSPL of additional gain was applied), and
we used the recordings’ first channels for the analysis. The training data
were recorded between Aug. 10–19, 2017, between 6:00 and 9:00 AM. The test
data were recorded between Sep. 1–30, 2017, during the same morning periods.
The sampling rate was 16,000 Hz.

The multi-channel recordings were intended for use in localization of the
sound sources (i.e., singer identification) and separation of sounds from
different sources, but neither the localization nor separation was successful
in our recording environment (we used the HARK programs with the default and
customized transfer functions [49]). Nevertheless, previous observations of
wild gibbons suggest our recorded songs would have overlapped little among the
three singers: It has been reported that males typically vocalized in turn,
with those in adjacent territories staying silent during another’s singing
[57, 21, 46]. The rarity of overlaps is also in accordance with our impression
of the recordings. In addition, we suspect that the existence of overlaps (if
any) would not make significant differences in the results of our grammatical
analysis reported here. It is easily proved that switching among multiple
finite-state automata can be seen as one large finite-state automaton, and
thus, data strings produced by such a process constitute a regular language in
terms of formal language theory. Although our approach is probabilistic and
thus such a claim from formal language theory does not guarantee the validity
of our conclusion, the proof above still suggests that data strings produced
by multiple individuals do not immediately lead to superregularity. (Note,
however, that female gibbons are known to vocalize simultaneously—a type of
song called _great calls_ , and communication among multiple individuals is of
major interest to researchers of the species [20]. Hence, the sound
localization and separation are an important issue that should be addressed in
future studies on gibbon song.)

###  6.2 Preprocessing

The inputs to our grammatical analyses were strings of acoustic features at
representative points in the recorded sound streams. We first detected regions
containing gibbon song in the sound streams by calculating the ratio $r$ of
the energy in the song-sound band (500–1500 Hz) to that in the total frequency
band (0-8000 Hz). Each frequency band’s energy was the sum of the squared
amplitudes in the band obtained from the sound spectrum calculated by the
discrete Fourier transform (DFT-windows: 20 ms, DFT-overlap: 10 ms). A region
of length $\geq$ 500 ms was judged to contain song if $r>0.6$ at every point
in the region.

We then downsampled the song regions, leaving only representative data points
whose acoustic features constituted data strings that would be subject to the
grammatical analyses. By the definition of the song regions above, there were
no identifiable silent intervals inside the regions that could define smaller
units of the song akin to birdsong syllables [50]. On the other hand, the song
regions often consisted of multiple components similar to human speech
syllables (Figure 4), each of which was considered to correspond to an atomic
event of vocal production. Accordingly, acoustic features at local peaks of
the wideband envelope were used as the unit components of the string data for
the grammatical analysis. The local peaks were systematically detected by the
recent method using the Hirbert-transformed signals based on the bandpass-
filters designed to model human auditory functions [13]. The acoustic local
peaks identified by this method are said to correspond to the articulatory
local maxima of mouth opening in the production of human speech syllables.
Given the anatomical similarities between the vocal tract of the human and the
gibbon [37], we considered that the method was appropriate to locate
representative data points of the gibbon song.

The details of the local peak detection algorithm are as follows. We first
bandpass-filtered waveforms in the song regions into six frequency bands with
cut-off frequencies at 80, 260, 600, 1240, 2420, 4650, and 7999 Hz [55, 13].
The resulting bandpassed signals were then Hilbert-transformed, and the
absolute values of the six transformed signals (narrowband envelopes) were
summed to obtain a wideband envelope [13]. The search for the local peaks of
the wideband envelope started with the detection of their candidates. Each
local peak candidate was the peak within a 300 ms search window slid 10 ms at
a time throughout the recordings. The candidates were adopted as local peaks
if the following two conditions were met: (i) the difference between the local
peak and the minimum in the 300 ms search window was at least 1.0 (Hirbert
unit); and (ii) a local peak was not preceded by another one within 150 ms.

Figure 4: Local peaks in a single song region. The top and bottom rows show
the raw sound wave and the spectrogram containing the song region,
respectively. The vertical dotted lines stretching from the middle row to the
sound wave represent the local peaks detected by the algorithm.

Finally, we calculated the thirteen Mel-Frequency Cepstrum Coefficients
(MFCCs) of the 100 ms window starting from each of the local peaks. While MFCC
was originally designed to capture acoustic features of human speech, it has
also been adopted in analyses of vocal activities of primates [45] and other
species [15]. The present study also followed this standard approach. Note,
however, that neural networks have recently started replacing MFCC in the
field of computational linguistics [32], and future studies on gibbon song and
other animal vocal activities should also consider such new methods, just as
we suggested for grammatical analyses of animal data.

The MFCC vectors calculated at the local peaks were clustered into strings by
the song regions containing the peak locations. This yielded 2767 strings of
training data and 7343 strings of test data. (The reason behind the smaller
amount of training data than that of the test data was that the induction of
PCFG was time-consuming and the amount adopted here was almost the maximum
possible given our limited computational resources. The size of the test data,
on the other hand, did not have such restrictions, so we used the greater
amount—recordings over a month.) We fed these strings of MFCC vectors to the
grammatical analyses described below.

###  6.3 Generative Models

We adopted the basic design of PCFG with an HDP prior (HDP-PCFG) discussed in
[40, 41]. We modified their HDP-PCFG in three ways. First, we assumed that the
roots of PCFG parse trees could be variable, instead of assuming a unique node
label like Chomsky normal forms. This modification allowed us to analyze
incomplete data strings that appear in naturalistic data. For instance,
English corpora can involve subjectless sentences (e.g., _Just came back from
the party._) and strings solely consisting of a noun phrase (e.g., _Great
job._). Variable roots enable a uniform treatment of such incomplete strings
and substrings of complete strings. For example, _just came back from the
party_ could be parsed as a verb phrase whether it stands alone or appears
within a complete sentence like _John just came back from the party_.
Secondly, our data were MFCC vectors (of $D:=13$ dimensions) rather than
discrete symbols, and thus, the terminal symbols were latent variables in our
HDP-PCFG. Accordingly, we also imposed an HDP prior on the terminal production
rules. Finally, we assumed a Gaussian emission of the MFCC vectors conditioned
on terminals of the HDP-PCFG, with Gaussian and Inverse Wishart priors on the
mean and covariance matrix parameters respectively [8, 22, 18]. This
generative model is formally described in Figure 5(a) and 5(c).

We also followed [40] and imposed an HDP prior on the HMM (HDP-HMM). The only
difference was that MFCC vectors, rather than discrete symbols, were emitted
conditioned on the hidden states [22]. This model is summarized in Figure 5(b)
and 5(c).

The free concentration parameters of the HDPs and beta distributions, denoted
by $\alpha$ with subscripts, were all set to $1$. The scale matrix of the
Inverse Wishart prior of the Gaussian emission was the identity matrix, and
the degree of freedom was $\nu_{0}=D-1+0.001=12.001$. The mean
$\mathbf{m}_{0}$ of the Gaussian prior was set to the sample mean of all the
MFCC vectors, and the scalar of the covariance matrix was
$k_{0}=\nu_{0}=12.001$ [cf. 18].

$\displaystyle\boldsymbol{\beta}\sim$
$\displaystyle\mathrm{GEM}\left*\alpha_{\textsc{NonTerm}}\right\lparen$ draw
top-level non-terminal probabilities $\displaystyle\boldsymbol{\gamma}\sim$
$\displaystyle\mathrm{GEM}\left*\alpha_{\textsc{Term}}\right\lparen$ draw top-
level terminal weights $\displaystyle\phi^{(R)}\mid\boldsymbol{\beta}\sim$
$\displaystyle\mathrm{DP}\left*\alpha_{\textsc{Rt}},\boldsymbol{\beta}\right\lparen$
draw root-labeling weights For each non-terminal $z$,
$\displaystyle\phi^{(T)}_{z}\mid z\sim$
$\displaystyle\mathrm{Beta}\left*\alpha_{\textsc{TpB}},\alpha_{\textsc{TpE}}\right\lparen$
draw rule type probabilities $\displaystyle\phi^{(B)}_{z}\mid
z,\boldsymbol{\beta}\sim$
$\displaystyle\mathrm{DP}\left*\alpha_{\textsc{Br}},\boldsymbol{\beta}\boldsymbol{\beta}^{\mathrm{T}}\right\lparen$
draw branching rule probabilities $\displaystyle\phi^{(E)}_{z}\mid
z,\boldsymbol{\gamma}\sim$
$\displaystyle\mathrm{DP}\left*\alpha_{\textsc{Em}},\boldsymbol{\gamma}\right\lparen$
draw terminal production rule probabilities For each data string $j$,
$\displaystyle r_{j}\mid\phi^{(R)}\sim$
$\displaystyle\mathrm{Categorical}\left*\phi^{(R)}\right\lparen$ choose root
non-terminal For each node $i$ labeled with non-terminal $z_{i}$,
$\displaystyle t_{i}\mid z_{i},\phi^{(T)}_{z_{i}}\sim$
$\displaystyle\mathrm{Bernoulli}\left*\phi^{(T)}_{z_{i}}\right\lparen$ choose
child type (non-terminals or terminal)
$\displaystyle\left*z_{c_{1}(i)},z_{c_{2}(i)}\right\lparen\mid
z_{i},\phi^{(B)}_{z_{i}},t_{i}=0\sim$
$\displaystyle\mathrm{Categorical}\left*\phi^{(B)}_{z_{i}}\right\lparen$
generate child non-terminals $\displaystyle s_{i}\mid
z_{i},\phi^{(E)}_{z_{i}},t_{i}=1\sim$
$\displaystyle\mathrm{Categorical}\left*\phi^{(E)}_{z_{i}}\right\lparen$
generate child terminal (a) HDP-PCFG with Variable Root

$\displaystyle\boldsymbol{\omega}\sim$
$\displaystyle\mathrm{GEM}\left*\alpha_{\textsc{State}}\right\lparen$ draw
top-level state weights $\displaystyle\phi^{(R)}\mid\boldsymbol{\omega}\sim$
$\displaystyle\mathrm{DP}\left*\alpha_{\textsc{Init}},\boldsymbol{\omega}\right\lparen$
draw probabilities of initial states For each state $s$,
$\displaystyle\phi^{(H)}_{s}\mid s\sim$
$\displaystyle\mathrm{Beta}\left*\alpha_{\textsc{Halt}},\alpha_{\textsc{Move}}\right\lparen$
draw probability of halt at state $s$ $\displaystyle\phi^{(S)}_{s}\mid
s,\boldsymbol{\omega}\sim$
$\displaystyle\mathrm{DP}\left*\alpha_{\textsc{Tr}},\boldsymbol{\omega}\right\lparen$
draw probabilities of transitions from state $s$ For each data string $j$,
$\displaystyle r_{j}\mid\phi^{(R)}\sim$
$\displaystyle\mathrm{Categorical}\left*\phi^{(R)}\right\lparen$ choose
initial state For each time step $i$, given that the current state is $s_{i}$,
$\displaystyle t_{i}\mid s_{i},\phi^{(H)}_{s_{i}}\sim$
$\displaystyle\mathrm{Bernoulli}\left*\phi^{(H)}_{s_{i}}\right\lparen$ choose
halt ($t_{i}=0$) or move-on ($t_{i}=1$) $\displaystyle s_{i+1}\mid
s_{i},\phi^{(S)}_{s_{i}},t_{i}=1\sim$
$\displaystyle\mathrm{Categorical}\left*\phi^{(S)}_{s_{i}}\right\lparen$
choose next state (b) HDP-HMM (Inter-State Transitions)

for each terminal/state $s$, $\displaystyle\Sigma_{s}\mid s\sim$
$\displaystyle\mathcal{W}^{-1}\left*\Psi_{0},\nu_{0}\right\lparen$ draw
covariance matrix parameters of the Gaussian emission
$\displaystyle\boldsymbol{\mu}_{s}\mid s,\Sigma_{s}\sim$
$\displaystyle\mathcal{N}\left*\mathbf{m}_{0},\frac{\Sigma_{s}}{k_{0}}\right\lparen$
draw mean parameters of the Gaussian emission For each node $i$ labeled with
terminal/state $s_{i}$ $\displaystyle\mathbf{x}_{i}\mid
s_{i},\mu_{s_{i}},\Sigma_{s_{i}}\sim$
$\displaystyle\mathcal{N}\left*\mu_{s_{i}},\Sigma_{s_{i}}\right\lparen$ emit
the MFCC vector (c) Gaussian Emission

Figure 5:  HDP-PCFG with variable root and Gaussian emission conditioned on
terminals (5(a) \+ 5(c)), and HDP-HMM with variable initial state and Gaussian
emission (5(b) \+ 5(c)).

###  6.4 Posterior Inference

Obtaining the true posterior distribution of the HDP-PCFG/HMM given data is
computationally intractable. Accordingly, we approximated the posterior by
_variational inference_ [8, 40, 41, 22]. Variational inference approximates
the intractable posterior distribution $p(\boldsymbol{\theta}\mid\mathbf{x})$,
where $\boldsymbol{\theta}$ bundles the latent variables of the PCFG/HMM in
Figure 5, by another distribution $q(\boldsymbol{\theta})$ that belongs to a
class of tractable distributions. We adopted the _mean-field method_ and
assumed the independence of the latent variables in $q(\boldsymbol{\theta})$,
with $q(\boldsymbol{\theta})$ equal to the product of $q(\boldsymbol{\beta})$,
$q(\boldsymbol{\gamma})$, $q(\phi^{(R)})$, $q(\phi^{(T)}_{z})$,
$q(\phi^{(B)}_{z})$, $q(\phi^{(E)}_{z})$, $q(\boldsymbol{\tau})$
($\tau:=\left*\mathbf{r},\mathbf{t},\mathbf{z},\mathbf{s}\right\lparen$), and
$q(\mu_{s},\Sigma_{s})$ for the HDP-PCFG, with a similar factorization assumed
for the HDP-HMM. The individual factor distributions were defined as follows.
For all types of rule probabilities $\phi$, $q(\phi)$ was a Dirichlet
distribution. $q(\boldsymbol{\tau})$ for parses $\boldsymbol{\tau}$ was a
Multinomial distribution. $q(\mu_{s},\Sigma_{s})$ was a Gaussian-Inverse-
Wishart distribution. Finally, $q(\boldsymbol{\beta})$ and
$q(\boldsymbol{\gamma})$ were degenerate distributions such that they upper-
bounded the possible number of (non-)terminals by positive integers
$K_{\boldsymbol{\beta}}$ and $K_{\boldsymbol{\gamma}}$ respectively:
$q(\beta_{z}>0)=0$ for $\forall z>K_{\boldsymbol{\beta}}$ and
$q(\gamma_{s}>0)=0$ for $\forall s>K_{\boldsymbol{\gamma}}$. We set
$K_{\boldsymbol{\beta}}=40$ and $K_{\boldsymbol{\gamma}}=100$, and similarly
upper-bounded the possible number of HDP-HMM states by
$K_{\boldsymbol{\omega}}=100$. Only 35 non-terminals, 64 terminals, and 58
states had expected frequencies greater than 0.05 for the training data, and
so we considered the truncation levels to be sufficiently large. Each
variational factor distribution was updated iteratively so that the updates
minimized the Kullback–Leibler (KL) divergence of the variational distribution
$q(\boldsymbol{\theta})$ to the true posterior
$p(\boldsymbol{\theta}\mid\mathbf{x})$ (_coordinate ascent algorithm_). See
[40, 41] for the details on updates of the factor distributions for the HDP-
PCFG/HMM latent variables (Figure 5(a), 5(b)), and [8, 22] for those related
to the Gaussian emission (Figure 5(c)). See also [4] for updates of the
degenerate factor distributions $q(\boldsymbol{\beta})$,
$q(\boldsymbol{\gamma})$, and $q(\boldsymbol{\omega})$. The coordinate ascent
algorithm only leads to a local minimum of the KL divergence, and accordingly,
we tried 500 different sets of initial values for the parameters of $q$ and
reported the best run among them. Each run terminated either when the
improvement in the KL divergence was smaller than $0.1$ or when the number of
maximum iterations ($=300$) was achieved.

The statistical values reported in the Results section were estimated as
follows based on the variational approximation. The expected count of a parse
$\mathbf{z}_{\iota}$ of a training/test data string $\mathbf{x}_{\iota}$ was
proportional to the exponential of its expected log probability,
$\mathrm{exp}\left*\mathrm{E}_{q(\boldsymbol{\theta}_{\mathrm{PCFG}})}[\log
p(\mathbf{z}_{\iota}\mid\mathbf{x}_{\iota},\boldsymbol{\theta}_{\mathrm{PCFG}})]\right\lparen$,
where $\boldsymbol{\theta}_{\mathrm{PCFG}}$ bundles the latent variables of
the HDP-PCFG in Figure 5(a) and 5(c) [41]. The Bayes-optimal parses are those
maximize this expected log probability. While there are an intractable number
of parse types, computation of the expected counts of the left-branching,
right-branching, and Bayes-optimal parses is tractable: We computed the
exponential of their expected log probability and normalized it by the total,
$\sum_{\mathbf{z}_{\iota}}\mathrm{exp}\left*\mathrm{E}_{q(\boldsymbol{\theta}_{\mathrm{PCFG}})}[\log
p(\mathbf{z}_{\iota}\mid\mathbf{x}_{\iota},\boldsymbol{\theta}_{\mathrm{PCFG}})]\right\lparen$,
which can be computed by dynamic programming (we adopted Earley’s algorithm in
particular [17, 56]). The expected counts of the non-regular parses are just
the total counts minus the expected counts of the left- and right-branching
parses. The posterior predictive probability density of the test data under
PCFG/HMM was given by
$\log\mathrm{E}_{q(\boldsymbol{\theta}_{\mathrm{PCFG}})}[p(\mathbf{z}_{\iota}\mid\mathbf{x}_{\iota},\boldsymbol{\theta}_{\mathrm{PCFG}})]$
[9, 10]. Finally, the expected number of production rules (root-labeling,
branching, and terminal production rules for the PCFG; initial and inter-state
transitions for the HMM) used for the training data were estimated by applying
$\mathds{1}[\cdot\geq 1]$ and $\tanh$ to the expected token frequency of the
rules. The expected frequency of a rule $A\to\lambda$ was given by the
parameters of its Dirichlet variational distribution $q(\phi_{A\to\lambda})$
minus its base counts $\alpha_{\textsc{Em}}\gamma_{\lambda}$ (for terminal
production rules), $\alpha_{\textsc{Br}}\beta_{B}\beta_{C}$ (for branching
rules such that $\lambda=\left*B,C\right\lparen$), or $\alpha\beta_{\lambda}$
(for other rules).

## Ethics

This article does not present research with ethical considerations.

## Data Accessibility

The data used in this paper are available at Dryad [48]. The code for the
Preprocessing is available at https://github.com/hkoda/gibbon_peak_mfcc, and
that for the Posterior Inference is available at https://bitbucket.org/tkc-
morita/vi_hdphmm_hdppcfg.

## Authors’ Contributions

TM participated in the data collection and performed the grammatical analyses
of the data. HK participated in the data collection and performed the acoustic
preprocessing of the data.

## Competing Interests

We have no competing interests.

## Funding

This work is supported by the JSPS/MEXT KAKENHI (#18H03503 and
#4903(Evolinguistic), JP17H06380) and JST CREST #17941861 (#JPMJCR17A4).

## Acknowledgements

We thank Shigeru Miyagawa for discussions in the early stage of this study;
Norihiko Maeda, Takumi Kunieda, Hiroshi Okuno, Kazuhiro Nakadai, and the HARK
project for their support in the recording process; the KUPRI Center for Human
Evolution Modeling Research for their daily care of the gibbons.

## References

  * Bar-Hillel et al. [1961] Yehoshua Bar-Hillel, M. Perles, and E. Shamir.  On formal properties of simple phrase structure grammars.  _Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung_ , 14:143 – 172, 1961.  Reprinted in Y. Bar-Hillel. (1964). Language and Information: Selected Essays on their Theory and Application, Addison-Wesley 1964, 116–150.
  * Beal et al. [2002] Matthew J. Beal, Zoubin Ghahramani, and Carl E. Rasmussen.  The infinite hidden Markov model.  In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, _Advances in Neural Information Processing Systems 14_ , pages 577 – 584\. MIT Press, 2002.
  * Bernardo and Smith [1994/2000] José M. Bernardo and Adrian F. M. Smith.  _Bayesian Theory_.  Wiley Series in Probability and Statistics. John Wiley & Sons, Ltd, Chichester, 1994/2000.  ISBN 047149464X.
  * Bertsekas [1982] Dimitri P. Bertsekas.  Projected Newton methods for optimization problems with simple constraints.  _SIAM Journal on Control & Optimization_, 20:221 – 246, 1982.  ISSN 03630129.
  * Berwick [2015] Robert C. Berwick.  Mind the gap.  In Ángel J. Gallego and Dennis Ott, editors, _50 Years Later: Reflections on Chomsky’s Aspects_ , pages 1 – 12. MITWPL, 2015.
  * Berwick and Chomsky [2016] Robert C. Berwick and Noam Chomsky.  _Why Only Us: Language and Evolution_.  MIT Press, 2016.
  * Berwick et al. [2011] Robert C. Berwick, Kazuo Okanoya, Gabriel J.L. Beckers, and Johan J. Bolhuis.  Songs to syntax: the linguistics of birdsong.  _Trends in Cognitive Science_ , 15(3):113 – 121, 2011.
  * Bishop [2006] Christopher M. Bishop.  _Pattern recognition and machine learning_.  Information science and statistics. Springer, New York, 2006.  ISBN 0387310738.
  * Blei and Jordan [2006] David M. Blei and Michael I. Jordan.  Variational inference for Dirichlet process mixtures.  _Bayesian Analysis_ , 1(1):121 – 144, 2006.  ISSN 19316690.
  * Blei et al. [2017] David M. Blei, Alp Kucukelbir, and Jon D. McAuliffe.  Variational inference: A review for statisticians.  _Journal of the American Statistical Association_ , 112(518):859 – 877, 2017.  doi: 10.1080/01621459.2017.1285773.
  * Blumenthal [1966] Arthur L. Blumenthal.  Observations with self-embedded sentences.  _Psychonomic Science_ , 6(10):453 – 454, Oct 1966\.  ISSN 0033-3131.  doi: 10.3758/BF03328087.
  * Brandon-Jones et al. [2004] D. Brandon-Jones, A. A. Eudey, T. Geissmann, C. P. Groves, D. J. Melnick, J. C. Morales, M. Shekelle, and C.-B. Stewart.  Asian primate classification.  _International Journal of Primatology_ , 25(1):97 – 164, Feb 2004.  ISSN 1573-8604.  doi: 10.1023/B:IJOP.0000014647.18720.32.
  * Chandrasekaran et al. [2009] Chandramouli Chandrasekaran, Andrea Trubanova, Sébastien Stillittano, Alice Caplier, and Asif A. Ghazanfar.  The natural statistics of audiovisual speech.  _PLOS Computational Biology_ , 5(7):1 – 18, 07 2009.  doi: 10.1371/journal.pcbi.1000436.
  * Chomsky [1965] Noam Chomsky.  _Aspects of the Theory of Syntax_.  MIT Press, Cambridge, MA, 1965.
  * Clemins et al. [2005] Patrick J. Clemins, Michael T. Johnson, Kirsten M. Leong, and Anne Savage.  Automatic classification and speaker identification of african elephant (loxodonta africana) vocalizations.  _The Journal of the Acoustical Society of America_ , 117(2):956 – 963, 2005.  doi: 10.1121/1.1847850.
  * Culy [1985] Christopher Culy.  The complexity of the vocabulary of bambara.  _Linguistics and Philosophy_ , 8(3):345 – 351, 1985.  ISSN 01650157, 15730549.
  * Earley [1970] Jay Earley.  An efficient context-free parsing algorithm.  _Communications of the ACM_ , 13(2):94 – 102, February 1970.  ISSN 0001-0782.  doi: 10.1145/362007.362035.
  * Feldman et al. [2013] Naomi H. Feldman, Sharon Goldwater, Thomas L. Griffiths, and James L. Morgan.  A role for the developing lexicon in phonetic category acquisition.  _Psychological Review_ , 120(4):751 – 778, 2013\.  ISSN 0033295X.
  * Foss and Cairns [1970] Donald J. Foss and Helen S. Cairns.  Some effects of memory limitation upon sentence comprehension and recall.  _Journal of Verbal Learning and Verbal Behavior_ , 9(5):541 – 547, 1970.  ISSN 0022-5371.  doi: https://doi.org/10.1016/S0022-5371(70)80099-8.
  * Geissmann [2002] Thomas Geissmann.  Duet-splitting and the evolution of gibbon songs.  _Biological Reviews_ , 77(1):57 – 76, 2002.
  * Gittins [1984] S. P. Gittins.  The Lesser apes: Evolutionary and behavioural biology.  In H. Preuschoft, D. J. Chivers, W. Y. Brockelman, and N. Creel, editors, _The vocal repertoire and song of the agile gibbon_ , pages 354 — 375. Edinburgh University Press, Edinburgh, 1984.
  * Gruhl and Sick [2016] Christian Gruhl and Bernhard Sick.  Variational Bayesian inference for hidden Markov models with multivariate Gaussian output distributions.  _CoRR_ , abs/1605.08618, 2016.
  * Grünwald [2007] Peter D. Grünwald.  _The Minimum Description Length Principle_.  The MIT Press, Cambridge, MA, 2007.
  * Hirai et al. [2009] Hirohisa Hirai, Azusa Hayano, Hiroyuki Tanaka, Alan R. Mootnick, Hery Wijayanto, and Dyah Perwitasari-Farajallah.  Genetic differentiation of agile gibbons between sumatra and kalimantan in indonesia.  In Danielle Whittaker and Susan Lappan, editors, _The Gibbons: New Perspectives on Small Ape Socioecology and Population Biology_ , chapter 3, pages 37 – 49. Springer New York, New York, NY, 2009.  ISBN 978-0-387-88604-6.  doi: 10.1007/978-0-387-88604-6˙3.
  * Hosino and Okanoya [2000] Tikara Hosino and Kazuo Okanoya.  Lesion of a higher-order song nucleus disrupts phrase level complexity in bengalese finches.  _Neuroreport_ , 11(10):2091 – 2095, 2000.
  * Huybregts [1984] Riny Huybregts.  The weak inadequacy of context-free phrase structure grammars.  In Ger de Haan, Mieke Trommelen, and Wim Zonneveld, editors, _Van Periferie Naar Kern_ , pages 81 – 99. Foris Publications, Dordrecht, 1984.
  * Johnson [2008] Mark Johnson.  Using adaptor grammars to identify synergies in the unsupervised acquisition of linguistic structure.  In _Proceedings of ACL-08: HLT_ , pages 398 – 406. Association for Computational Linguistics, 2008.
  * Johnson et al. [2007] Mark Johnson, Thomas L. Griffiths, and Sharon Goldwater.  Adaptor grammars: A framework for specifying compositional nonparametric Bayesian models.  In B. Schölkopf, J. C. Platt, and T. Hoffman, editors, _Advances in Neural Information Processing Systems 19_ , pages 641 – 648\. MIT Press, 2007.
  * Johnson et al. [2010] Mark Johnson, Katherine Demuth, Bevan Jones, and Michael J. Black.  Synergies in learning words and their referents.  In J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, editors, _Advances in Neural Information Processing Systems 23_ , pages 1018 – 1026. Curran Associates, Inc., 2010.
  * Joshi [1985] Aravind K. Joshi.  Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?  In David R. Dowty, Lauri Karttunen, and Arnold M.Editors Zwicky, editors, _Natural Language Parsing: Psychological, Computational, and Theoretical Perspectives_ , Studies in Natural Language Processing, chapter 6, pages 206 — 250. Cambridge University Press, Cambridge, 1985.  doi: 10.1017/CBO9780511597855.007.
  * Kakishita et al. [2007] Yasuki Kakishita, Kazutoshi Sasahara, Tetsuro Nishino, Miki Takahasi, and Kazuo Okanoya.  Pattern extraction improves automata-based syntax analysis in songbirds.  _Lecture Notes in Artificial Inteligence_ , 4828:320 – 332, 2007.
  * Kamper et al. [2015] Herman Kamper, Micha Elsner, Aren Jansen, and Sharon Goldwater.  Unsupervised neural network based feature extraction using weak top-down constraints.  In _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 5818 – 5822, April 2015.  doi: 10.1109/ICASSP.2015.7179087.
  * Karlsson [2007] Fred Karlsson.  Constraints on multiple center-embedding of clauses.  _Journal of Linguistics_ , 43(2):365 – 392, 2007\.
  * Katahira et al. [2011] Kentaro Katahira, Kenta Suzuki, Kazuo Okanoya, and Masato Okada.  Complex sequencing rules of birdsong can be explained by simple hidden Markov processes.  _PLoS ONE_ , 6(9):1 – 9, 09 2011.  doi: 10.1371/journal.pone.0024516.
  * Kershenbaum et al. [2014] Arik Kershenbaum, Ann E. Bowles, Todd M. Freeberg, Dezhe Z. Jin, Adriano R. Lameira, and Kirsten Bohn.  Animal vocal sequences: not the Markov chains we thought they were.  _Proceedings of the Royal Society of London B: Biological Sciences_ , 281(1792), 2014.  ISSN 0962-8452.  doi: 10.1098/rspb.2014.1370.
  * Koda [2016] Hiroki Koda.  Gibbon songs: Understanding the evolution and development of this unique form of vocal communication.  In Ulrich H. Reichard, Hirohisa Hirai, and Claudia Beatriz Barelli, editors, _Evolution of Gibbons and Siamang: Phylogeny, Morphology, and Cognition_ , Developments in Primatology: Progress and Prospects, chapter 15, pages 349 – 359. Springer, New York, 2016.
  * Koda et al. [2012] Hiroki Koda, Takeshi Nishimura, Isao T. Tokuda, Chisako Oyakawa, Toshikuni Nihonmatsu, and Nobuo Masataka.  Soprano singing in gibbons.  _American Journal of Physical Anthropology_ , 149(3):347 – 355, 2012.  doi: 10.1002/ajpa.22124.
  * Lee et al. [2015] Chia-ying Lee, Timothy J. O’Donnell, and James Glass.  Unsupervised lexicon discovery from acoustic input.  _Transactions of the Association for Computational Linguistics_ , 3:389 – 403, 2015.  ISSN 2307-387X.
  * Li and Vitányi [2008] Ming Li and Paul M.B. Vitányi.  _An Introduction to Kolmogorov Complexity and Its Applications_.  Texts in Computer Science. Springer, New York, NY, USA, 2008.  ISBN 0387339981.
  * Liang et al. [2007] Percy Liang, Slav Petrov, Michael Jordan, and Dan Klein.  The infinite PCFG using hierarchical Dirichlet processes.  In _Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)_ , pages 688 – 697, Prague, Czech Republic, June 2007. Association for Computational Linguistics.
  * Liang et al. [2009] Percy Liang, Michael Jordan, and Dan Klein.  Probabilistic grammars and hierarchical Dirichlet processes.  In Anthony O’Hagan and Mike West, editors, _The Oxford Handbook of Applied Bayesian Analysis_ , Oxford handbooks, chapter 27. Oxford University Press, Oxford; New York, 2009.
  * Marks [1968] Lawrence E. Marks.  Scaling of grammaticalness of self-embedded english sentences.  _Journal of Verbal Learning and Verbal Behavior_ , 7(5):965 – 967, 1968.  ISSN 0022-5371.  doi: https://doi.org/10.1016/S0022-5371(68)80106-9.
  * Marshall and Marshall [1976] Joe T. Marshall and Elsie R. Marshall.  Gibbons and their territorial songs.  _Science_ , 193(4249):235 – 237, 1976.  ISSN 0036-8075.  doi: 10.1126/science.193.4249.235.
  * Maurits et al. [2009] Luke Maurits, Amy F. Perfors, and Daniel J. Navarro.  Joint acquisition of word order and word reference.  In N. A. Taatgen and H. van Rijn, editors, _Proceedings of the 31st Annual Conference of the Cognitive Science Society_ , pages 1728 — 1733, Austin, TX, 2009. Cognitive Science Society.
  * Mielke and Zuberbühler [2013] Alexander Mielke and Klaus Zuberbühler.  A method for automated individual, species and call type recognition in free-ranging animals.  _Animal Behaviour_ , 86(2):475 – 482, 2013.  ISSN 0003-3472.  doi: https://doi.org/10.1016/j.anbehav.2013.04.017.
  * Mitani [1988] John C. Mitani.  Male gibbon (hylobates agilis) singing behavior: Natural history, song variations and function.  _Ethology_ , 79(3):177 – 194, 1988.
  * Miyagawa et al. [2013] Shigeru Miyagawa, Robert Berwick, and Kazuo Okanoya.  The emergence of hierarchical structure in human language.  _Frontiers in Psychology_ , 4:71, 2013.  ISSN 1664-1078.  doi: 10.3389/fpsyg.2013.00071.
  * Morita and Koda [2019] Takashi Morita and Hiroki Koda.  Data from: Superregular grammars do not provide additional explanatory power but allow for a compact analysis of animal song.  Royal Society Open Science, 2019.  URL https://doi.org/10.5061/dryad.mn12jv2.  doi:10.5061/dryad.mn12jv2.
  * Nakadai et al. [2017] Kazuhiro Nakadai, Hiroshi G. Okuno, , and Takeshi Mizumoto.  Development, deployment and applications of robot audition open source software hark.  _Journal of Robotics and Mechatronics_ , 29(1):16 – 25, 2017.  doi: 10.20965/jrm.2017.p0016.
  * Okanoya [2004] Kazuo Okanoya.  Song syntax in Bengalese finches: proximate and ultimate analyses.  _Advances in the Study of Behavior_ , 34:297 – 345, 2004\.
  * Perfors et al. [2011] Amy Perfors, Joshua B. Tenenbaum, and Terry Regier.  The learnability of abstract syntactic principles.  _Cognition_ , 118(3):306 – 338, March 2011.
  * Rabin and Scott [1959] M. O. Rabin and D. Scott.  Finite automata and their decision problems.  _IBM Journal of Research and Development_ , 3(2):114 – 125, April 1959.  ISSN 0018-8646.  doi: 10.1147/rd.32.0114.
  * Rissanen and Ristad [1994] Jorma Rissanen and Eric Sven Ristad.  Language acquisition in the MDL framework.  In _Language Computations: DIMACS workshop on human language_ , pages 149 – 166, Philedelphia, 1994. American Mathemtatical Society.
  * Sakamoto et al. [1986] Yosiyuki Sakamoto, Makio Ishiguro, and Genshiro Kitagawa.  _Akaike information criterion statistics._ Mathematics and its applications. Japanese series. Tokyo: KTK Scientific Publishers; Dordrecht; Boston: D. Reidel; Hingham, MA: Sold and distributed in the U.S.A. and Canada by Kluwer Academic Publishers, 1986.  ISBN 9027722536.
  * Smith et al. [2002] Zachary M Smith, Bertrand Delgutte, and Andrew J Oxenham.  Chimaeric sounds reveal dichotomies in auditory perception.  _Nature_ , 416(6876):87 – 90, 03 2002.  doi: 10.1038/416087a.
  * Stolcke [1995] Andreas Stolcke.  An efficient probabilistic context-free parsing algorithm that computes prefix probabilities.  _Computational Linguistics_ , 21(2):165 – 201, 1995.
  * Tenaza [1976] Richard R. Tenaza.  Songs, choruses and countersinging of Kloss’ gibbons (hylobates klossii) in Siberut Island, Indonesia.  _Zeitschrift für Tierpsychologie_ , 40(1):37 – 52, 1976.  doi: 10.1111/j.1439-0310.1976.tb00924.x.
  * Vapnik [1998] Vladimir N. Vapnik.  _Statistical Learning Theory_.  John Wiley & Sons, Ltd, 1998.  ISBN 0471030031.