Statistical properties of probabilistic context-sensitive grammars

Hierarchical structures underlie many real-world phenomena, including natural languages. A context-free grammar (CFG), a fundamental concept in formal language theory, was originally introduced to analyze hierarchical syntactic structures in natural languages [1]. Furthermore, it provides a basis for describing more general hierarchical structures that are not limited to natural languages. A CFG, defined by a set of production rules, generates strings with trees in a formal way. The strings correspond to sentences, whereas the trees describe the hierarchical syntactic structures behind the sentences. A probabilistic extension of a CFG, known as a probabilistic context-free grammar (PCFG) or stochastic context-free grammar [2], introduces probabilities into the production rules. According to the rules, this model generates trees in a probabilistic manner. This probabilistic grammar has been used to model syntactic structures of a natural language [3] or a programming language [4], and to study many other phenomena with tree or hierarchical structures in fields such as music [5, 6], human cognition [7], long-short-term-memory network [8], RNA [9], cosmic inflation [10], or a more abstract model [11, 12, 13]. Additionally, other frameworks are closely related to a PCFG, including a branching process and a Lindenmayer system (or L-system) [14, 15, 16].

An essential property of a PCFG is that the distribution of a subtree depends only on its root, not on the context, which we will designate as context-free independence. This property allows an exact mathematical analysis of the statistical properties of PCFGs. Indeed, earlier studies have analyzed and resolved various aspects of PCFGs, including the probability of symbol occurrence [17], the correlation function [11, 12], mutual information between nodes [8], the mean sentence length [18], entropy [19, 20], branching rates [19, 20], tree size [20], and the conditions for sentence generation to terminate with probability $1$ [18, 21]. At the same time, this property is too strict to impose on real-world phenomena. Particularly, it is well known in linguistics that some languages in the real world cannot be described using a CFG because of its inability to represent cross-serial dependencies [22, 23]. In natural language processing, empirical evidence suggests that a naive parser relying on a PCFG is insufficient for inferring syntactic structures [3]. Moreover, certain parsers that relax context-free independence in technical manners can express more complex distributions and can achieve higher accuracy [24, 25]. Outside of language-related domains, the possibility that introducing context sensitivity is useful for describing music is also discussed [5]. Therefore, the distributions that a PCFG can express are regarded as severely limited.

To understand more realistic phenomena with hierarchical structures, it is necessary to introduce and analyze a model that captures the distribution of a tree beyond context-free independence. For this purpose, one can naturally consider context-sensitive grammars (CSGs) [26], which form the class one level higher than CFGs in the hierarchy of expressive power: the so-called Chomsky hierarchy. Similarly to a PCFG, a probabilistic context-sensitive grammar (PCSG) can be formulated as a probabilistic extension of a CSG. A PCSG explicitly relaxes context-free independence. Consequently, the theoretical analyses developed for a PCFG are not applicable to a PCSG. The statistical properties of a PCSG have only rarely been analyzed, either theoretically or numerically.

To address this point, for this work, we defined a simple PCSG and investigated its statistical properties by numerical simulations systematically, mainly examining whether a qualitative difference from a PCFG exists, or not. To be more precise, we implemented a PCSG to measure the distribution of a symbol, mutual information between two nodes, and mutual information between two pairs of children of nodes on which the symbols are fixed. Here, we present a comparison of the observed similarities and differences between PCFG and PCSG: No qualitative difference was found in the distribution of a symbol between a PCSG and a PCFG.This result suggests that the properties observed in PCFGs are likely to be preserved in PCSGs. Given that the absence of a singularity in the distribution in an ensemble of PCFGs has been proven [17], it is reasonable to infer that PCSGs would not exhibit the singularity, similarly to PCFGs. This singularity is relevant for the discussion on a phase transition in the random language model (RLM) [27, 28], which might be analogous to discontinuity in human language acquisition according to earlier research.

However, the behaviors of mutual information between two nodes differ between a PCFG and a PCSG. The mutual information in a PCFG decays exponentially with the distance between two nodes, i.e., the path length in a tree graph. In contrast, in a PCSG, the mutual information decays exponentially with the effective distance, which is defined by considering the effect of context sensitivity.

Additionally, a more pronounced difference concerns the mutual information between pairs of children of symbol-fixed nodes. This novel metric, proposed in this research, quantifies context-free independence breaking. From a theoretical physics perspective, this metric represents the degree to which the network of interactions deviates from a tree structure. Linguistically, it represents the strength of mutual dependence between the structures of two constituents or phrases of given types. This metric not only detects whether context-free independence is broken; it also quantifies where and how strongly the breaking occurs. In a PCFG, the context-free independence breaking is always zero. By contrast, in a PCSG, it is positive and decays similarly to the mutual information between nodes. As a result, the most striking difference between a PCFG and a PCSG is in this metric. This quantification is intuitive and is definable for any distribution of a tree. Measuring this metric in other mathematical models or real-world phenomena will help deepen the understanding of them by investigating how their behavior differs from that of a PCFG.

Here, we provide a brief summary of the main contributions made in this paper. Our first main contribution is the systematic investigation of a PCSG, which is a simple model for generating hierarchical structures beyond those produced by PCFGs. A key distinction between a PCFG and a PCSG is in the distance that determines the decay of mutual information. Second, we propose a novel metric for the context-free independence breaking, which has not been quantified previously. This metric allows for further quantitative investigation of various hierarchical structures that violate the context-free independence. Our results show that this metric decays exponentially for a PCSG while it remains zero for a PCFG, demonstrating the usefulness of this metric.

This paper is structured as follows: The models, a PCFG and a PCSG, are introduced in Sec. II. The analysis of the distribution of a symbol in a PCSG and the argument about the phase transition in the RLM are presented in Sec. III. Then, in Sec. IV, a numerical analysis of the mutual information between two nodes is presented, including the definition of the effective distance. The introduction and analysis of the quantification of the context-free independence breaking are given in Sec. V. Finally, we summarize the results and briefly discuss future works in the last section.

As described in the preceding section, we examined the distribution of a symbol on a node, but we could find no significant difference between a PCFG and a PCSG. For the discussion in this section, we turn our interest to mutual information, which has a close relation to the two-point correlation function [37] and which has been used for measuring correlation in symbolic sequences such as formal and natural languages [38, 8, 39], music [8], birdsong [40], DNA [41], and so forth. We denote the mutual information between nodes $i$ and $j$, as depicted in Fig. 4, as

This measures the dependence between the two nodes. Although the behavior of mutual information in a PCFG is well known through theoretical analysis [8], this analysis is also based on context-free independence. Consequently, understanding what occurs in a PCSG regarding the mutual information, where the independence is broken, is non-trivial again.

Before presenting the results of the numerical analysis, we introduce some notations and quantities. In the following, we designate a node by a binary sequence that represents the path from the root to the node by assigning 0 and 1, respectively, to a left and right child. For example, nodes $()$, $(0)$, and $(0,1)$ represent the root, the left child of the root, and the right child of the left child of the root, respectively. To characterize the relative position of two nodes, we introduce the two distinct distances described in Fig. 5. The first is the structural distance, i.e., the length of the path between the two nodes. The second, designated as the horizontal distance, is the number of nodes lying horizontally between the two nodes. If the depths of the two nodes differ, then the horizontal distance is the number of nodes between the higher node and the lower node’s ancestor of the same depth as the former.

One of the two nodes was fixed at $i=(1,0,0,0,0,0)$, which is the leftmost node of depth $6$ in the subtree whose root is the right child of the root of the whole tree. The other node $j$ could be any node in the whole tree. The relation between structural and horizontal distances differs based on whether node $j$ belongs to the left or right subtree, as presented in Fig. 5. Presuming that the depth of node $j$ is fixed, then when $j$ is in the left subtree, i.e., $j=(0,\cdots)$, the structural distance is the same, irrespective of the horizontal distance. However, when $j$ is in the right subtree, i.e., $j=(1,\cdots)$, the horizontal distance is roughly exponential of the structural distance.

In the context-free case with $q=0$, the dependence of the mutual information on the two distances is already known. Lin and Tegmark [8] have proved that the mutual information decays exponentially with the structural distance. Recalling that the mutual information in a Markov chain decays exponentially with the chain length, this result is intuitively reasonable when considering context-free independence. When $j$ is in the left subtree, the mutual information is the same for any node $j$ of the same depth because the mutual information depends only on the structural distance, which is independent of the horizontal distance. However, when $j$ is in the right subtree, the mutual information decays according to a power law of the horizontal distance because the horizontal distance grows exponentially in the structural distance. One main claim of Lin and Tegmark [8] was that this power law might be the mechanism of the power-law decay of mutual information in natural language texts.

In the context-sensitive case with $q>0$, we examined the behavior of the mutual information. We sampled $10^{8}$ complete trees of depth $D=7$ and estimated $I$. Because the mutual information between $X$ and $Y$ is decomposed into $S(X)+S(Y)-S(X,Y)$ where $S(\cdot)$ is Shannon entropy, we computed the mutual information by estimating the entropy from the empirical distribution. This estimate has a bias from the entropy of the true distribution, resulting in biased mutual information, which is not negligible in the region of the small mutual information. Consequently, to compute the entropy in the present and the subsequent sections, we used the bias-reduced estimator proposed by Ref. [42]. This estimator is represented by

Therein, $\Psi$ is the digamma function, $x$ represents a state which $X$ takes, $n_{x}$ denotes the number of samples such that $X=x$, and $N=\sum_{x}n_{x}$ is the total number of samples.

Figure 6 shows $I$s for an $M$ generated with $\epsilon=10^{-2}$ and $q=1$, where rewriting always refers to the context. The structural distance dependences of $I$ for $j$ belonging to the left and right branches are shown respectively in Figs. 6(a) and  6(b). The horizontal distance dependence is also shown in Figs. 6(c) and  6(d). When $j$ belongs to the right branch, i.e., $j=(1,\cdots)$, as shown in the right subfigures (b) and (d), what is observed with a PCFG roughly holds. Here, $I$ decays exponentially in the structural distance and follows a power law in the horizontal distance. However, different behavior is observed when $j$ belongs to the left branch, i.e., $j=(0,\cdots)$, as shown in the left subfigures (a) and (c). In Fig. 6(a), $I$ has clearly different values even with the same structural distances, whereas it decays in the power law of the horizontal distance in Fig. 6(c), similarly to the case with $j=(1,\cdots)$. This result differs from the behavior found with a PCFG.

The mutual information between nodes in a PCSG depends explicitly on the horizontal distance. This observation can be attributed to the context sensitivity inherent in PCSG rules. If the context-free independence holds, then a node can correlate with other nodes only along the path in the tree graph. This result engenders the exponential decay with the structural distance. In contrast, in a PCSG where each rule involves the context $L$ and $R$ as well as $A$, a node can correlate with its left and right neighbors directly, even in the absence of a direct path between them. This horizontal correlation can bypass the long structural distance between two nodes belonging to different subtrees, leading to the effective distance. As shown in Fig. 7, the horizontal distance increases exponentially with the effective distance. If the mutual information does not decay exponentially with the structural distance, but instead with the effective distance, then the mutual information will decay in a power law in the horizontal distance, irrespective of whether node $j$ belongs to the left or the right branch.

The effective distance is definable as explained hereinafter. Presuming that nodes $i^{\prime}$ and $j^{\prime}$ are ancestors of $i$ and $j$, respectively, and that $i^{\prime}$ and $j^{\prime}$ are the horizontal neighbors of one another, then the effective distance between nodes $i$ and $j$ is the sum of the path length from $i$ to $i^{\prime}$ and from $j$ to $j^{\prime}$. Here, we assume that the effective distance is equal to the structural distance if one of the two nodes is the ancestor of the other. We plot the same $I$ as in Fig. 6, but against the effective distance, in Fig. 8(a). From this, it can be confirmed that the mutual information decays exponentially with the effective distance, as expected. This result indicates the existence of a typical effective distance that corresponds to a correlation length, which is the inverse of the decay rate. The mutual information is small beyond this typical distance.

It is intuitively reasonable to infer that the mutual information decays exponentially with the effective distance. Joint probability $P(\sigma_{0},\cdots,\sigma_{2^{D+1}-2})$ of all nodes is the product of all $2^{D}-1$ rewriting weights. For two nodes $i$ and $j$, marginalizing the remaining nodes yields the joint probability $P(\sigma_{i},\sigma_{j})$ of the two nodes. The greatest contribution to this is the product of the weights on the shortest effective path, described by the blue dashed line in Fig. 7. Although an effective path and its corresponding weights depend on the order of application of rules at each step, the length of the shortest effective path asymptotically equals the effective distance. Therefore, the joint probability of two nodes scales as an exponential function of the effective distance. This result implies that the mutual information scales in the same manner [8].

What we describe here is not unique to this instance. It is typically observed across the $M$s sampled. We measured $I$ for 10 $M$s under the same settings and computed the averages and the standard deviations of $\ln I$ over $j$s of each effective distance and over $M$s. Whereas mutual information is always non-negative, the estimate by the method in [42] sometimes takes negative values when the true value is small. We simply excluded non-positive estimates to compute the logarithm. This exclusion caused the average to be biased upward, but this bias was slight in this case. The results presented in Fig. 8(b) show that the exponential decay in the effective distance discussed above for a single $M$ is observed across $10$ $M$s. Figure 8(c) also presents histograms of $\ln I$ for the effective distance $5$, where the frequencies are normalized. The points are distributed around the average. The deviations in Fig. 8(b) and the distribution in Fig. 8(c) originate from differences in $j$s and $M$s rather than from sample fluctuations.

The rate of decay and the correlation length depend on weights $M$, causing the average rate to change as the parameter $\epsilon$ varies. One can infer that, as $\epsilon$ increases, the distribution of trees under generated weights $M$ tends to approach the uniform distribution. Therefore, the mutual information is expected to decay faster, meaning that the correlation length will become smaller. Additionally, the rate of decay depends on the context sensitivity $q$. With larger $q$, rewriting operations depend not only on the rewritten symbol but also on the context, with higher probability. This dependence seems to engender slower decay. The numerically computed mutual information with different $\epsilon$ and $q$, as presented in Supplemental Material, follows these expectations.

Finally, we investigate the effect of context sensitivity more directly by quantifying the extent to which the context-free independence is broken. This independence means that two subtrees are mutually independent under the condition that the symbols of their roots are fixed. Therefore, quantifying the breakage of the context-free independence involves the measurement of the mutual information between the subtrees under this condition. However, it requires extremely large amounts of data to obtain the distribution of a subtree when the subtree is large. To overcome this difficulty, we instead specifically examine the mutual information between the children of their roots, as shown in Fig. 9. We denote this mutual information as

Therein, $k$ and $l$ respectively represent the left and the right children of $i$; $m$ and $n$ are the children of $j$. This quantity is always zero for any $i$ and $j$ in a PCFG because of the context-free independence. This is the requirement that must be met for this quantity to be a meaningful metric of the breaking of independence.

In addition to measuring the degree of context-free independence breaking, the metric $J$ has other interpretations. One interpretation derives from theoretical physics. If the network of interactions forms a tree, where every interaction in the system is between a node and its child, then $J$ is zero. In the presence of loops in the network, as seen in a PCSG, $J$ can take a positive value. In this sense, $J$ represents the degree to which the network of interactions deviates from a tree. Another interpretation is linguistic: Suppose that two constituents or phrases, i.e. subtrees of a derivation, are, for example, a noun phrase and a verb phrase. Under this condition, the structures of the noun phrase and the verb phrase are mutually dependent; $J$ represents the strength of this dependence.

We measured the context-free independence breaking $J$ in the same manner as for the mutual information $I$ in the preceding section, under the same setting, where $i=(1,0,0,0,0,0)$, $q=1$, $\epsilon=10^{-2}$, and $10^{8}$ trees of the depth $7$ were sampled for each $M$. Our observations revealed that $J$ behaves very similarly to $I$. Figure 10(a) shows $J$ for $A=B=0$ against the effective distance for an $M$ generated from the lognormal distribution. It is evident that $J$ exhibits exponential decay with the effective distance. Again, this finding indicates that there exists a correlation length, or a typical effective distance beyond which the dependence between two subtrees is small. We computed the averages and the standard deviations of $\ln J$ over $j$’s of each effective distance, over $M$’s, and over $A$ and $B$, using the data size, i.e., the number of generated trees satisfying $\sigma_{i}=A$ and $\sigma_{j}=B$, as the weights. Additionally, we simply discarded non-positive estimates of $J$, which only led to a small bias. Figure 10(b) presents the results, suggesting that the exponential decay of $J$ with the effective distance occurs across different $M$s, as well as different $A$s and $B$s. Figure 10(c) shows the normalized histogram of $\ln J$ obtained for the effective distance $5$, where the data sizes were used as the weights. The distribution of $\ln J$s centers around the red vertical line representing the average.

The dependence of $J$ on the parameter $\epsilon$ and the context sensitivity $q$ exhibits similar tendencies to those observed for $I$. Particularly, as $\epsilon$ increases or $q$ decreases, the decay rate becomes more pronounced whereas the correlation length becomes smaller. Supplemental Materials provide additional results for different values of $\epsilon$ and $q$. In a general system, $I$ and $J$ do not necessarily behave similarly. Indeed, in a PCFG, $I$ is positive and decays exponentially with the structural distance, whereas $J$ is always zero. It is somewhat non-trivial that both $I$ and $J$ decay exponentially with the effective distance in a PCSG.

A PCFG, a simple mathematical model for randomly generating a tree, has been used to model various hierarchical phenomena, including natural languages. This model satisfies the assumptions of context-free independence. Although this feature allows for the theoretical analysis of various properties of a PCFG, the restriction is too strong for a PCFG to be expressive of distributions.

We introduced the simple PCSG by relaxing the context-free independence, and we analyzed its statistical properties systematically. First, we specifically examined the distribution of a symbol on a single node. This distribution is to a PCSG what magnetization is to a spin system. Although the context sensitivity affects the distribution, its effect brings only continuous and quantitative changes. Such changes can occur even without context sensitivity, for example in the interpolation between two PCFGs. Our numerical investigation also shows that the Binder parameter of the mean ratio of a symbol, which is an analytic function of $\epsilon$ in the context-free RLM, is unlikely to be discontinuous in a context-sensitive case.

The second quantity of interest is the mutual information between two nodes, which is related closely to the two-point correlation function [37]. It is noteworthy that mutual information decays exponentially with the effective distance between two nodes, which is a consequence of the horizontal correlation because of context sensitivity. This feature contrasts with the fact that the decay of the mutual information in a PCFG is exponential with respect to the structural distance, i.e., the path length.

In addition, to quantify the degree to which context-free independence is broken, we proposed the use of mutual information between two pairs of nodes under the condition that the parent symbols are fixed. This metric can also indicate the degree to which the network of interactions deviates from a tree in theoretical physics, and it can indicate the mutual dependence between the structures of two constituents in linguistics. This quantity emphasizes the most distinct difference between a PCFG and a PCSG. The context-free independence breaking decays exponentially with the effective distance in a PCSG, similar to the mutual information between two nodes, whereas the breaking always remains zero in a PCFG.

Possible future issues, in our view, are divisible into four main directions. First, it is necessary to develop methods for theoretical analysis and efficient numerical approximation to confirm and further investigate the behaviors of PCSGs observed in this study, such as the exponential decay of the mutual information and the context-free independence breaking. The main challenges are the exponential growth of tree sizes and the complex interactions due to context sensitivity.

Second, another important approach would be to examine specific PCSGs, particularly those exhibiting atypical behavior, in contrast to our analysis of the typical properties of randomly sampled PCSGs. It might be true that PCSGs with low probabilistic measures exhibit non-analytic behavior in $\Delta$ as a function of the context sensitivity $q$, or non-exponential decay of the mutual information or context-free independence breaking. The existence of such PCSGs and the mechanism underlying their atypical behavior are left as intriguing open problems.

Third, CSG is not the only linguistic framework beyond CFG. Although the CSG framework makes tree structures context-sensitive in a straightforward manner, modern linguists do not consider a CSG to be a relevant model of a natural language. This skepticism arises because a CSG can generate a set of sentences extending beyond natural languages [30]. Also, formal language theory predominantly addresses surface sentences rather than syntactic structures [43]. Conversely, several alternative models have been proposed as grammars closer to natural languages, such as Tree Adjoining Grammar [44], Combinatory Categorial Grammar [45], and Minimalist Grammar [46]. The natural progression is to introduce probabilistic extensions to these grammars and to investigate their statistical properties, as examined in this study. Particularly, all probabilistic extensions of a CSG and the three grammars described above will violate the context-free independence, but their independence breaking $J$ might decay exponentially, polynomial, or non-monotonically, depending on the grammar. If the decay is, for example, exponential in every model, then their decay rates might differ. These probabilistic grammars can be characterized by emphasizing the distinctions in their independence breaking $J$, thereby contributing to a comprehensive understanding of the grammars from a physical perspective.

As a fourth point, we discuss the application of our metric $J$ for the context-free independence breaking, which is applicable not only to probabilistic grammars such as PCFGs but also to any distribution of a tree, including those underlying human languages and birdsongs. Earlier research has demonstrated that the behavior of mutual information in PCFGs, human languages, and birdsongs is similar in that it decays as a power-law function of the horizontal distance or the sequence length [8, 40]. However, $J$ will allow us to detect and quantify the distinction between human languages and PCFGs, given the empirical knowledge that context-free independence breaking occurs in natural languages [24, 25]. It might also be possible to identify characteristics unique to human languages, which are not present in birdsongs, using $J$. By quantifying the degree of independence breaking, we can more deeply compare tree structures among different mathematical models or natural phenomena.