Permutree Process

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:56:31

Abstract: The permutree is an innovative mathematical concept recently introduced in the field of combinatorics. It encompasses permutations, trees, partitions, and binary sequences as its special cases, while also allowing for interpolations between them. In this paper, we present the permutree notion within the context of Bayesian machine learning. We exploit the fact that permutrees have a one-to-one correspondence with special permutations to propose a stochastic process on permutrees, and further propose two data modeling strategies analogous to the stick-breaking process and Chinese restaurant process that are frequently used in Bayesian nonparametrics. 
Permutations, trees, partitions, and binary sequences frequently appear as building blocks in Bayesian nonparametric models, and these models have been studied and developed independently. However, in practical situations, there are many complicated problems that require master craftsmanship to combine these individual models  into a  single giant model. Our models provide a framework for modeling such complicated tasks in a unified manner. As a significant application, we demonstrate the potential of our models for phylogenetic analysis of lineages, which involve coalescence, recombination, multiple ancestors, and mutation.

Main paper: 
 introduction: 
 Various combinatorial structures -Permutations, trees, partitions, and binary sequences have been frequently utilized in Bayesian modeling, and conventionally, various models have been studied separately for each subject. Permutations have been used in a wide range of applications such as Bayesian ranking [101, 63, 110, 73] , matrix reordering [70, 81, 99] , and the traveling salesman problem [102, 17, 105] . Various random permutation models, such as the Mallows model [54, 12, 16] , the permuton models [37, 7, 51, 6] and the modified Chinese restaurant process [57] , have been employed in Bayesian modeling. Trees are typically used for hierarchical clustering [22, 21] and multiple resolution regression [47, 25, 20] . In the Bayesian literature, the Dirichlet diffusion tree [62, 45] , the Mondrian process [88, 87] and the Pólya tree [56, 48, 27, 15] are particularly popular models.Partitions and binary sequences are fundamental tools in machine learning, with numerous examples of their usage in clustering, factor analysis, feature selection, and more. For the modeling of partitions and binary sequences, the Dirichlet process mixture model [23, 79, 100, 59] , the Pitman-Yor process mixture model [76] , the Chinese restaurant process [74] , and the stick-breaking process [89] for random partitions, and the beta-Bernoulli process and the Indian buffet process [29, 95, 93] for random binary sequences have frequently been employed.Combination of different combinatorial structures -In real-world applications of machine learning, it is often a useful strategy to combine several different combinatorial structures to model data, rather than using only one combinatorial structure. For example, the combination of partitioning and factor models is particularly popular, including the infinite factorial hidden Markov models [24, 97] , the subset infinite relational model [39] , the infinite latent factor model with the infinite mixuture model [111, 112] and the kernel beta process [83] . As another example, the combination of tree structures Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.Figure 1 : Overview of new combinatorial structures invented in [75] . Left: A permutree that is a combinatorial object that includes the concepts of permutations, binary trees, clusters, factors, etc., but can also interpolate between them. The permutree is, as defined, a "directed" tree, but for visibility, the direction of the edges from Parent to Child is omitted in the diagrams. Middle: Variant concepts required to represent stochastic processes on permutrees indirectly through decorated permutations in Section 3. Right: Special cases of permutrees. Remark 2.1 provides details on each interpretation. and partitioning have also been actively studied, including the hierarchical Dirichlet process [94] , the nested Dirichlet process [84, 64] , their hybrid models [2, 71, 50] , the infinite context-free grammar [49] and the tree-structured stick-breaking process [1, 65] . Furthermore, permutations are occasionally employed in conjunction with clustering to analyze relational data [61] . As we have discussed so far, this kind of strategy of combining multiple models into a single model is one promising direction for research and development. However, advancing research in this direction necessitates the evaluation of an enormous number of models in a combinatorial fashion, which becomes infeasible due to the exponentially increasing number of potential combinations. Consequently, we are striving to initiate a paradigm shift towards exploring an entirely new approach capable of unifying these models.Key insight -In our pursuit of creating a unified model capable of encompassing permutations, trees, partitions, and binary sequences, we are incorporating the concept of permutrees [75] , which has recently emerged in the field of combinatorics, into the realm of Bayesian nonparametric (BNP) machine learning. Permutrees not only serve as a framework that includes permutations, trees, partitions, and binary sequences as distinct cases but also exhibit intriguing properties of interpolation between them. Figure 1 (a)-(d ) provides a concise visual representation of the key characteristics.Our contributions -The main contribution of this paper is to produce, by using the concept of permutrees, a stochastic process that can represent combinatorial structures such as permutations, binary trees, partitions and binary sequences in a unified manner for the first time. Section 3 exploits the one-to-one correspondence between permutations and certain permutations using a two-dimensional marked point process to construct this process, which we call a permutree process.Section 4 derives a data modelling strategy using this stochastic process by analogy with the stickbreaking process that is frequently used in BNP machine learning. Section 5 demonstrates the application of phylogenetic analysis of DNA sequence data dealing with multiple biological events such as coalescence, recombination, mutation and multiple ancestry in a unified manner.2 Preliminaries: Permutree and related objects Permutree [75] -A permutree is a new mathematical tool invented recently in the field of combinatorics, which not only represent permutations, trees, partitions, and binary sequences as special cases, but can also interpolate between them [75] . Let us begin with the definition of a permutree.We consider a directed tree T with a vertex set V of n (n ∈ N) vertices of degree at least 2, and a set of terminal nodes of degree 1 (See also Figure 1 (a) ). For technical reasons (discussed immediately below), we dare to pay particular and explicit attention here to the set V of the "interior vertices" (i.e., vertices of degree at least 2) other than the terminal nodes. Each vertex v ∈ V is assigned a natural number p(v) as a label, using the bijective vertex labeling (one-to-one correspondence) p : V → [n] := {1, 2, . . . , n} based on the following permutree requirements (Definition 1 in [75] ):(C1) Each vertex v ∈ V has one or two parents, and one or two children.(C2) If a vertex v has a left parent (or child), then all labels in the subtree of the left ancestor (or descendant) of v are smaller than p(v). If v has a right parent (or child), then all labels in the subtree of the right ancestor (or descendant) of v are greater than p(v).A directed tree T that satisfies the above requirements can be expressed more intuitively and clearly by introducing the notion of decorations to the vertices V. See also Figure 1 (e). We introduce the n-tuple decorations δ(T) := (δ(T) 1 , . . . , δ(T) n ) ∈ { , , , } n , defined as follows: (i) { , } n are exactly the Cambrian trees proposed in [82, 13] . See Figure 1 (k) for an example.δ(T) p(v) = if vBinary sequence -Permutrees with decoration n have a one-to-one correspondence with binary sequences with length n -1. The ith element of the binary sequence is determined according to the following procedure: for any i ∈ [n -1], there exists p(v) = i and p(w) = i + 1, and if v is the parent of w, output 1, otherwise output 0. See Figure 1 (l) for 10010 as an example. Now that we have summarized the important property of permutrees, we will describe the findings necessary to construct a stochastic process on a permutree, which is the main focus of this paper. As a motivation for describing the following findings, imagine actually drawing an instance of permutree on a hand-drawn blackboard. At this point, we notice that the horizontal positional relationship of vertices V is explicitly given by the natural number label p(• ∈ V), however, the vertical positional relationship is still ambiguous (In Figure 1 , (f) is identical to (g) in terms of the permutree, but distinct in terms of the increasing tree). Hence, in order to construct a stochastic process on permutrees in a concise and clear manner, a mechanism to control the vertical positioning of the vertices of the permutrees is required. With this motivation in mind, we introduce two useful notions, an increasing tree (Figure 1 (g)) and a leveled permutree (Figure 1 Leveled permutree -To define the leveled permutree, we start by introducing an additional notion of an increasing tree. We consider a directed tree T with vertex set V. Each vertex v ∈ V is assigned a natural number label q(v), using the bijective vertex labeling (one-to-one correspondence)q : V → [n] such that, if v ∈ V is the parent of w ∈ V, then q(v) < q(w) is satisfied. Intuitively,the function q serves to label the vertices V from 1 to n vertically from bottom to top (Figure 1 (g)).Then, a leveled permutree is a directed tree T with a vertex set V endowed with two bijective vertex labelings p, q : V → [n] which respectively define a permutree and an increasing tree. By using two types of labels p and q, the horizontal and vertical arrangement of the vertices V can be explicitly specified, as shown in Figure 1 (h). The leveled permutree is a useful tool when considering the generative model of the permutree in Section 3, because its specification is clear.The notion of a leveled permutree so far has improved the prospects for dealing with permutrees.However, leveled permutrees are still combinatorial and geometric, and are not yet easy to handle computationally (in terms of Bayesian modeling, which is the main objective of this paper). Finally, we would like to wrap up this section by revealing one of the most important aspects of leveled permutrees: their relationship to decorated permutations. Decorated permutation -For the description of decorated permutations, the notion of a permutation table should be prepared first. A permutation table is a geometrical representation of a permutation σ with n length by the (n × n)-table, with rows labeled by positions from bottom to top and columns labeled by values from left to right, and with a dot at column i and row σ(i) for all i ∈ [n] [9] .Figure 2 (left) shows an example for a permutation 536214. Now that we are ready, we move on to the description of a decorated permutation. A decorated permutation is a permutation table where each dot is decorated by , , , or . Figure 2 (left bottom) shows an illustration of a decorated permutation. One of the important properties of decorated permutations is shown below. Proposition 2.2. (See Proposition 8 in [75] .) There exists one-to-one correspondence between decorated permutations with decorations δ ∈ { , , , } n and leveled permutrees with δ(T) = δ.Figure 2 : Left: One-to-one correspondence between decorated permutations and leveled permutrees. Right: Permutree process as marked point process -We introduce an intensity function λ on the plane [0, 1] × [0, 1] (top left). Next, we generate random locations l 1 , . . . , l n from the Poisson point process with intensity λ (middle left). Then, for each random location, we independently assign one of the decorations { , , , } from the categorical distribution as a random mark m i (i = 1, . . . , n) (bottom left). By reading the positional relationship of the points as a permutation table, the resulting marked point {(l i , m i ) : i = 1, 2, . . . n} can be converted to a decorated permutation. Furthermore, by the transformation used in Proposition 2.2 [75] , the decorated permutation can be converted to a leveled permutree, as follows. First, we draw auxiliary lines (dashed lines colored red) below decorations , and above decorations , . From this point on, we will stretch the permutree edges, and it is important to emphasize that the permutree edges do not cross these auxiliary lines. Next, focusing on the auxiliary lines extending to the bottom, we can view these as dividing the lower region into smaller subregions (indicated by the red ovals). The edges are then extended one by one from each subregion. As we extend the edges from the bottom to the top, when they reach the height of each vertex, we connect the adjacent edges to that vertex (indicated by the gray box). By doing this until all vertices are covered, we obtain a leveled permutree. Now that we have reviewed the permutree findings, the next and subsequent sections will address three challenges: (i) How can we construct a stochastic process that can represent any permutree (in Section 3)? (ii) How can we construct a BNP prior model of the data using the stochastic process on the permutree (in Section 4)? (iii) What likelihood models can we combine the BNP prior with in actual machine learning applications (in Section 5)? 
permutree processes: 
 The goal of this section is to construct a stochastic process that can represent any permutree; ideally, as is the basic philosophy of BNP, that stochastic process should also be able to simultaneously represent randomness with respect to complexity (in the context of permutrees, the number of vertices). In fact, our construction below can represent every permutree with an unlimited number of finite or infinite number of vertices in a unified manner, depending on certain hyperparameters. One thing to note in advance is that the stochastic process described in this section does not refer to any modeling of data.We will discuss data modeling in more detail in the next Section 4.Key insight -Our strategy is to use point processes. Recall that, as discussed in Section 2, permutrees can be represented through leveled permutrees (surjection), and furthermore, leveled permutrees have a one-to-one correspondence (bijection) with decorated permutations (Proposition 2.2). Thanks to these facts, instead of dealing directly with permutrees (seemingly difficult to handle), we can obtain a model of permutrees indirectly by considering a model of decorated permutations. So how can we model decorated permutations? We represent the random decorated permutations as a marked point process by considering random permutations as a point process and random decorations as marks.Marked point process for decorated permutations -We consider a marked point process consisting of a point process and associated marks, which can be expressed as {(l i , m i ) : i = 1, 2, . . . }, where l 1 , l 2 , . . . are locations and m 1 , m 2 , . . . are associated marks. Specifically, we employ the following Poisson process on a 2-dimensional plane [0, 1] × [0, 1] with discrete marks (Figure 2 right):• Random locations -We draw the random locations l 1 , l 2 , . . . from a Poisson point process on the plane [0, 1] × [0, 1] with the intensity function λ : [0, 1] × [0, 1] → R + , where R + = {r : r > 0, r ∈ R}. Although not essential, for the sake of simplicity, we use a homogeneous Poisson point process, that is, λ(A) = µ • Leb(A) for all measurable subset A of [0, 1] × [0, 1], where Leb(•) indicates the Lebesgue measure, and 0 < µ < ∞ is a tunable variable. For convenience, let l i = (l i,1 , l i,2 ), where l i,1 and l i,2 are the horizontal and vertical positions, respectively.• Random marks -We draw the random marks m 1 , m 2 , . . . , m n independently from a categorical distribution on { , , , }: Categorical(c , c , c , c ), where c * ≥ 0 ( * ∈ { , , , }) denotes the probability that decoration * is adopted.Transformation to leveled permutree -The above marked point process can immediately lead to a random leveled permutree with the following procedure. Recall that, as discribed in Section 2, the leveled permutree is defined by (i) the decorations on the vertices V and (ii) the two bijective vertex labelings p, q : V → [n]. For the decoration of vertices, we consider the point set of the marked point process as the vertex set V, and the mark m i assigned to the i-th point as the decoration of the i-th vertex v i ∈ V. Thus, the remainder to be considered is the setting of two functions p and q. By construction, we can obtain the indices a 1 , . . . , a n so that the random positions l 1 , . . . , l n are in ascending order in the horizontal direction, that is, l a1,1 < l a2,1 < • • • < l an,1 (Recall that l i = (l i,1 , l i,2 ), and l i,1 represents the horizontal position). Similarly, in the vertical direction, we can obtain the indices b 1 , . . . , b n so that l b1,2 < l b2,2 < • • • < l bn,2 . Now, if we choose to set p(v ai ) = i and q(v bi ) = i for i = 1, 2, . . . , n, then p and q satisfy the requirement of bijective functions. By the above, we have seen that indeed the marked point process provides us with what we need to define a leveled permutree, that is, the vertex decorations and two bijective functions p and q. Finally, Figure 2 (right) show the procedure for explicitly converting a marked point process to a random leveled permutree. Inheriting Proposition 2.2 and the result (with the proof procedure) of [75, Proposition 8] ,we can confirm that this transformation is well defined (See Appendix E for details). 
data modeling with permutree process: 
 The purpose of this section is to show how the permutree process described earlier can be used for modeling actual data. More specifically, this consists of the following two issues:• How to represent data using permutrees: As permutrees themselves are simply mathematical objects, we must be clear about how we relate them to data modeling and analysis. In fact, there are many possible ways to describe data by permutrees. We consider the situation where a data path (a lineage to describe the data in conjunction with some likelihood model, such as the evolutionary model in Section 5) from one of the lower terminal nodes to one of the upper terminal nodes on the permutree is assigned to each data (Figure 3 (a), top). For example, if we restrict the permutree to one of its special cases, the binary tree, this data path is attributed to the path from the root to the terminal node, which is a situation commonly used in hierarchical clustering (Figure 3 (a), bottom). 1 We show a strategy to represent this random data path using a special variant of the nested Chinese restaurant process [10] .• How to "implement" a permutree process: In the previous section, we have shown that a marked point process with an intensity function λ : [0, 1] × [0, 1] → R + can be used for the stochastic process on permutrees. On the other hand, another important topic is to clarify how to implement models (or more practically, what intensity function λ to use) suitable for data analysis. Our strategy is to use the analogy of the stick-breaking process [89] to represent the infinite number of marked points generated from the marked point process, which is the entity of the permutree process. This can be viewed as a special case of using beta intensity in the horizontal direction and uniform intensity in the vertical direction as the intensity function λ of the permutree process.Experts in the BNP field might remind themselves that there are many other strategy options for the above topics in the light of the various findings that have emerged in the history of the development of the BNP method over the last 20 years. We will, for the sake of space, summarize in Appendix D the various ideas and their respective advantages and disadvantages with respect to those historical findings, including whether it is possible to extend the conventional tool of the "ordered" Chinese restaurant process [77, 85] for random binary trees to random permutrees. The main body of this paper focuses on the most straighforward strategy. (a) Data path -We consider each data as having a data path (a lineage to describe the data in conjunction with some likelihood model) from one of the lower terminal nodes to one of the upper terminal nodes on the permutree (top). This will convince us of its generality and applicability, as it is attributed to the hierarchical clustering from one of the terminal nodes to the root when restricting the permutree to the special case of a binary tree (bottom). (b) Marked stick breaking process -Inspired by the stick-breaking representation [89] for the construction of Dirichlet processes [23] , in order to represent a random permutree of infinite size, we can represent the random vertex positions of the permutree by the stick-breaking process in the horizontal direction and uniform random measures in the vertical direction. (c) Two-table Chinese restaurant process (Variant of two-class Dirichlet allocation) -The data allocated to the lower terminal nodes are successively merged and distributed depending on the mark of each vertex, according to the law of the 'the rich get richer', to select paths.Permutree of infinite size -We first generate random positions l 1 , l 2 , . . . , l k = (l k,1 , l k,2 ), . . . in the point process of the permutree process, as shown in Figure 3 (b), using the stick-breaking process:EQUATIONwhere α > 0 is the concentration parameter. As in the original permutree process, each point markm k (k = 1, 2, . . . ) is generated from a categorical distribution: m k ∼ Categorical(c , c , c , c ).As mentioned earlier, by the procedure in Figure 2 (right), we can transform this sample (i.e., a set of infinite number of marked points) drawn from the permutree process into a uniquely single permutree.Data assignments to bottom terminal nodes -Next, we can represent data modeling by the paintbox scheme for the random permutree generated from the marked stick-breaking process described earlier. We associate one uniform random variable U j for each data indexed by j = 1, 2, . . . , N(N ∈ N): U j ∼ Uniform([0, 1]). Similar to Kingman's representation to the exchangeable partitions, called paintbox schemes [44, 11] , we choose which terminal node on the lower edge of the permutree to assign the jth data to, depending on which stick in the stick-breaking process this random variableU j is located on [0, 1], as shown in Figure 3 (b).Data path modeling -Finally, we model the path assignment for each data by choosing a path that starts at this assigned lower terminal node and reaches one of the upper terminal nodes through the following two- are the number of data allocated so far to the left and right tables respectively.• -We merge the sets of data flowing from the two lower branches and feed them into the upper.• -It would be straightforward to perform operations whose marks are and together.Another promising option is the representation of data flowing from the left parent to the left child and from the right parent to the right child. This can be interpreted as giving the mark the ability to partitioning. This interpretation also plays an important role in the validity of finite truncation, which will be discussed below.• -We pass on the whole data set that flows in, all the way to the top.For notational simplicity, we will denote the random variable for the jth data path by Z j . For a sample z of data paths between the upper and lower terminal nodes of the permutree (specified by a sequence of edges), the above generative probabilistic model allows us to evaluate the probability P[Z j = z] of the jth data choosing a data path sample z.Property #1: Exchangeability -Random data paths based on the generative probability model described above have exchangeability, an important property common to most BNP models [3, 36, 41] .Simply put, the model probability is invariant to the indexing of the data. As a result, it follows the philosophy of BNP models that even if the actual data to be observed is finite, the model itself, with infinite complexity, can reflect the uncertainty due to unobserved data. More specifically, this can be summarised as the following statement:Proposition 4.1 (Exchangeability). For any permutation σ of length N (N ∈ N), we haveP[Z 1 = z 1 , Z 2 = z 2 , . . . , Z N = z N ] = P[Z σ(1) = z 1 , Z σ(2) = z 2 , . . . , Z σ(N ) = z N ], where z j (j ∈ [N ]) is a sample of paths of random permutrees. (See Appendix A.1 for proof.)Property #2: Validity of finite truncation -The above generative probability model requires in principle an infinite number of random variables for its description, but finite truncation works reasonably well for a finite number of actual observed data. This poses an inherently non-trivial challenge that is not present in the validity of approximating the stick-breaking process [89] for the Dirichlet process [23] with a finite number of stick-breaking procedures, which is a typical topic in the past [94, 87, 67] . The reason for this non-triviality is that the substructure of a permutree with infinite size is, in principle, affected by an infinite numnber of all marked vertices. Therefore, restricting the structure of the permutree to only some marked vertices may have a significant impact on the structure of the permutree. However, as the following statement shows, the substructure of the permutree has the good property that it depends only on a subset of marked vertices.Proposition 4.2 (Finite truncation). In the above generative probability model of data indexed by j = 1, 2, . . . , N (N ∈ N), we consider an event that all random variables U j (j = 1, . . . , N ),representing the horizontal position of the jth data, falls in the range [0, 1 -ϵ) as a situation with a sufficiently high probabilityP[∧ N j=1 0 ≤ U j < 1 -ϵ] = N j=1 P[0 ≤ U j < 1 -ϵ] > 1 -ϵ • O(N ),where ϵ > 0 is a tiny real value. In this situation, there exists some natural number K < ∞, and all data paths are assigned with probability 1 only to paths on the finite-size random permutree generated from the random marked points l 1 , l 2 , . . . , l K . (See Appendix A.2 for proof.) 
application to phylogenetic permutree analysis: 
 This section presents an application example of using the prior model representation of data using permutrees, which has been described in Section 4, in conjunction with a likelihood model in a specific application. One of the most promising applications of permutrees would be phylogenetic tree analysis for DNA molecular sequence data (e.g., CAGTC). DNA sequences from one or more populations are related by a branching structure known as genealogy. The complex correlative structure of a collection of DNA sequences can be represented as a phylogenetic tree, a record of coalescence, recombination, and mutation events in the history of the target organism: coalescence refers to the event in which two sequences are attributed to a common ancestor, recombination refers to the event in which a lineage splits into two sub-lineages when looking back in time from the present to the past, and mutation refers to the change of each letter of a DNA sequence over time.Challenges of conventional methods -The most standard structure that has been used in phylogenetic analysis is the binary tree [66, 78, 58, 103, 98, 113, 107, 106, 60] . In fact, binary trees are very well suited to represent coalescence events in genealogy. However, one drawback of binary tree models is that they are not suitable for representing recombination events in a way that is compatible with coalescence events. To circumvent this drawback, the ancestral recombination graphs (ARGs) have sometimes been used as models that can represent both coalescence and recombination at the same time [52, 42, 80, 72, 90, 28] . However, it is not easy to model or infer ARGs directly, and often indirect ways of representing models by other perspectives (e.g., the fragmentation-coagulation process [92, 19] ) have been explored, or approximate models (e.g., the coalescent hidden Markov model [34, 53] and the sequentially Markov coalescent model [80] ) have been considered. Moreover, conventional phylogenetic tree analysis, including not only ARGs but also binary tree models, We note that the past (upper) to present (lower) direction (indicated by ↓) as biological events is the opposite of the parent (lower) to child (upper) direction (indicated by ↑) of the permutree as a purely mathematical object.generally imposes a strong assumption that observed DNA sequences or observed taxa have a single ancestor. In other words, this implies that the inferred phylogenetic tree should be a strongly connected graph. Needless to say, such an assumption is reasonable for taxa that have been carefully selected by biologists. On the other hand, when we want to use a large number of taxa that are too large to be selected by experts as observation data (i.e., the situation that BNP methods are really aiming for), a mechanism that allows multiple ancestors to be inferred in a data-driven manner will be very useful. In light of the above, phylogenetic tree analysis requires a model that can represent coalescence, recombination, multiple ancestors, and mutation in a unified manner.Phylogenetic permutree -As input observation data, we used DNA (molecular) sequences observed at letter length S over N species. For example, the sequence GAGTAC (i.e., N = 1 species) has length S = 6. We regard these DNA sequences as following a phylogenetic permutree. Specifically, we represent coalescence, recombination, multiple ancestry, and mutation events in genealogy by combining the four types of the decorations , , , with the following interpretations. We note that, to be consistent with the traditional notation of phylogenetic tree analysis, the past (upper) to present (lower) direction as biological events is the opposite of the parent (lower) to child (upper) direction of the permutree as a purely mathematical object that we have used in the diagrams so far.• Coalescence -A coalescence event represents two lineages (bottom side of Figure 4 • Partition -We give the decoration the role of division so that a single permutree can represent a phylogenetic tree with multiple ancestors. Specifically, as shown in Figure 4 (d),we connect the two left edges and connect the two right edges resulting in two tree structures unconnected to each other on either side of decoration .• Backward in time (optional) -We assume that no mutation occurs while going back in time from a vertex to a vertex with (Figure 4 (e) ). This allows us to set the mutation rate in the evolutionary model as a single parameter common to all branches, and the mutation rate can be adjusted according to the permutree itself.Evolutionary models on permutrees -Statistical models of gene mutation have a history of more than half a century, and a vast number of models have been proposed. An excellent recent review article can be found, for example, in [4] . For simplicity, we adopt two of the most popular models, the Jukes-Cantor model (JC) [40] and the generalized time reversible model (GTR) [91] , for DNA sequences (i.e., words with A, G, C, and T as letters of the alphabet {A,G,C,T}, such as CCTAAG).JC is defined as a Markov process in which (1) Demonstration -We use the following three benchmark datasets [60] for DNA sequences: RMPS (N = 64 species, S = 1008 length) [86] , HWB (N = 41, S = 1137) [33] , and ZB (N = 50, S = 1133) [108] . In addition, to establish a situation where the permutree notion would be useful (i.e., multiple ancestry derived from exclusive disconnected graphs), we extract the sequences of these datasets by S = 1000 length from the beginning and mix them to create a dataset we call COMB (N = 155). We use the marked stick-breaking process (referred to as MSBP; Section 4) as our proposed model. Since MSBP can easily adjust the representational capabilities of of its own model, as ablation studies, we use MSBP-bTree as the one restricted to binary trees (with the prior (c , c , c , c ) ∼ Dirichlet(ϵ/2, 0, 0, ϵ/2)), MSBP-cTree as the one restricted to Cambrian trees (with Dirichlet(ϵ/3, 0, ϵ/3, ϵ/3)), and MSBP-pTree as the main proposal permutrees (with Dirichlet(ϵ/4, ϵ/4, ϵ/4, ϵ/4)), where we set ϵ = 0.01. For the evolutionary model, we employ the mutation rate α ∼ Gamma(ϵ ′ , ϵ ′ ), where ϵ ′ = 0.1. We only present the case of K = 100 as the truncation level here, while we report the other cases in Appendix C. We compare these models to the hierarchical Dirichlet process hidden Markov model (HDPHMM) [8, 94, 5] , the fragmentation-coagulation process (FCP) [92] , and the binary tree model with the MrBayes [38, 46] , the probabilistic path Hamilton Monte Carlo (ppHMC) [18] , and the nested combinatorial sequential Monte Carlo (ncSMC) [60] . It is noted that HDPHMM and FCP do not use evolutionary models because they represent sequence data directly without tree structure. We held out 20% letters of the input sequences for testing, and each model was trained using the remaining 80% of the letters. Each inference method uses MCMC to estimate the posterior distribution by the following 100 samples: each method extracts 5 MCMC runs with different random numbers, and each MCMC run is sampled every 50 iterations after 2000 burn-in until 3000 iterations. We evaluate the models using perplexity as a criterion: perplexity(•) = exp(-(log p(•))/E), where E is the number of missing letters in the input sequences. Figure 5 shows the comparison of the prediction performance of each method for the four sets of data. As an overall trend, it can be seen that the Cambrian tree and permutree models show better prediction performance than the binary tree model, which has limited expressive power. 
discussion and limitation: 
 This paper (i) imports the notion of permutrees, recently invented in combinatorics, to Bayesian analysis, (ii) proposes the stochastic process that can represent various models such as permutations, trees, partitions, and factors in a unified manner, (iii) and applies it to phylogenetic permutree analysis.Limitations -While our proposed permutree process can represent various combinatorial structures in a unified "prior model," the likelihood model that describes the data (as we have shown in the context of phylogenetic tree analysis in Section 5, for example) must be prepared separately by the user or engineer. Thus, while the permutree process is a tool that allows data-driven inference of the model structure as a broad framework, the design of the likelihood model needs to be carefully done manually. In the near future, the exploration of representing this likelihood model in some kind of black box function model would be an important research direction.Remaining challenge -In the technical context of the BNP field, an important topic is whether a marginalized representation of the marked stick-breaking process, an infinite-dimensional intermediate random variable in the representation of data paths with exchangeability described in Section 4, can be obtained. This topic is a question closely related to the Aldous-Hoover-Kallenberg representation theorem for exchangeability in general [3, 36, 41] . As a more familiar analogy, it corresponds to the fact that if we marginalise the stick-breaking process representation in a Dirichlet process infinite mixture model, then we obtain the Chinese restaurant process representation. Our strategy and budding attempts on this question are summarized in Appendix D. This section provides proofs of Propositions 4.1 and 4.2 concerning two properties of the marked stick-breaking process omitted in Section 4 of the main text.One of the most important properties of random data paths drawn from the generative probabilistic model described in Section 4 is exchangeability, that is, the model probability is invariant to the indexing of the data. More specifically, this can be summarised as the following statement: Proposition A.1 (Exchangeability; Proposition 4.1). For any permutation σ of length N (N ∈ N),we have P[Z 1 = z 1 , Z 2 = z 2 , . . . , Z N = z N ] = P[Z σ(1) = z 1 , Z σ(2) = z 2 , . . . , Z σ(N ) = z N ],where z j (j ∈ [N ]) is a sample of paths of random permutrees.Proof. Broadly as a whole, we will check two following facts:(i) The random data assignments to bottom terminal nodes by the stick-breaking process [89] and the Kingman's paintbox scheme [44] are themselves exchangeable.(ii) The selection of data paths by the two-table Chinese restaurant process is exchangeable.Exchangeability of data assignments to bottom terminal nodes -We denote the index of the stick of the stick-breaking process to which the jth (j = 1, . . . , N ) data is assigned by the random variable Z bottom j . It follows from the model construction that, given a random partition of [0, 1] drawn from the stick-breaking process, the random variable U j (j = 1, . . . , N ) is independent. As a result, for any permutation σ of length N , we haveP Z (bottom) 1 = s N , . . . , Z (bottom) N = s N = N j=1 Z (bottom) j = s j = N j=1 Z (bottom) σ(j) = s j = P Z (bottom) σ(1) = s N , . . . , Z (bottom) σ(N ) = s N , (2)where s j (j = 1, . . . , N ) is a sample of stick indices (∈ N).Exchangeability of data path selection -Given the assignment of data to the terminal nodes, the choice of data paths follows a chain of the two-table Chinese restaurant process (see Figure 3 (c) in the main text) according to the decoration of each inner vertex of the permutree. It should be noted that in the two-table Chinese restaurant process, the data paths are chosen deterministically when the decorations are , , and . Therefore, we only need to focus on the case of table partitioning (Figure 3 (c), top) when the decoration is . It immediately from the model construction that the probability of partitioning the data when the decoration is is obtained as follows:EQUATIONwhere the variable s j is the index of bottom terminal nodes (i.e., the stick index of the stick-breaking process on [0, 1]) included in the path sample z j , the variable n (r) represents the number of data flowing to the rth permutree vertex from the bottom in the vertical direction in the collection of data path samples z 1 , . . . , z N , and N (r)Left and N (r)Right represent the number of data to be partitioned into the left and right tables at the rthth vertex (if the decoration at that vertex is ), respectively. It is important to note that the probability of selecting this datapath depends only on the number of data in the division of the table at each vertex. That is, in other words, it does not depend on the index of the data as follows:EQUATIONfor any permutation σ with length N . Thus, it can be checked that the selection of data paths is exchangeable. From Equations 2 and 4, we have completed our proof.The generative probability model (described in Section 4) requires in principle an infinite number of random variables for its description, but finite truncation works reasonably well for a finite number of actual observed data. More specifically, we can summarize this property as follows:Proposition A.2 (Finite truncation; Proposition 4.2). In the generative probability model (described in Section 4) of data indexed by j = 1, 2, . . . , N (N ∈ N), we consider an event that all random variables U j (j = 1, . . . , N ), representing the horizontal position of the jth data, falls in the range [0, 1 -ϵ) as a situation with a sufficiently high probabilityP[∧ N j=1 0 ≤ U j < 1 -ϵ] = N j=1 P[0 ≤ U j < 1 -ϵ] > 1 -ϵ • O(N ), where ϵ > 0 is a tiny real value. In this situation, there exists some natural number K < ∞, and all data paths are assigned with probability 1 only to paths on the finite-size random permutree generated from the random marked points l 1 , l 2 , . . . , l K .Proof. It follows from the construction that the uniformly random random random variables U j (j = 1, . . . , N ) are independent, so that the probability of an event for which all those random variables fall within the range [0, 1 ϵ ) can be checked as follows.EQUATIONThen, from the construction of the marked stick-breaking process on [0, 1], since there are countably infinite number of marked points in the range [1 -ϵ, 1] × [0, 1], the probability that there exists some natural number K < ∞ and the corresponding decoration of it is is 1. That is, we haveEQUATIONFrom the construction of the two-table Chinese restaurant process (described in Section 4) and the permutree requirement (C2) (described in Section 2), the data path assigned to the 1st to Kth bottom terminal nodes in the stick-breaking process never reaches the (K + 1)th and subsequent indexed permutree vertices. Therefore, each have a data path only on the edges of the finite permutree consisting of the 1st to Kth marked vertices. From the above, we have completed the proof.The purpose of this section is to provide additional information to help the reader better understand the characteristics of the permutree process as marked point process.We clarify the relationship between the permutree process and other existing stochastic processes.Specifically, the permutree process can lead to the uniform random permutations and the Mondrian process as its special cases. These relationships can be derived immediately from the fact that each can be expressed as a Poisson process of some sort. We will discuss each of these in specific detail with the intensity µ and the budget 1. By viewing the vertical position in the marked point process as the moment when the event of the cut in the Markov process (i.e., the Mondrian process) occurs, and the horizontal position as the location where the cut occurs, the special permutation process described above can be reduced to a Mondrian process.below. First of all, for self-containment, the core of the permutree process is restated, although it is the same as that detailed in the body of this paper.Permutree process -We consider a marked point process consisting of a point process and associate marks, which can be expressed as denotes the probability that decoration * is adopted.{(l i , m i ) : i = 1, 2, . . . },Connection to uniform random permutation -If we restrict the decoration weights for marks to (c , c , c , c ) = (1, 0, 0, 0) and make the Poisson process homogeneous (i.e., make the intensity function λ uniform), the permutree process leads to a stochastic process that generates a uniform random permutation. This fact can be easily derived by interpreting the permutation process as follows. See also Figure 6 (a) . By construction, we can obtain the indices a 1 , . . . , a n so that the random positions l 1 , . . . , l n are in ascending order in the horizontal direction, that is, l a1,1 < l a2,1 < • • • < l an,1 . If we choose to set p(v ai ) = i for the i-th vertex v i (i =W σ(1) < • • • < W σ(n) .Connection to Mondrian process -If we restrict the decoration weights to (c , c , c , c ) = (0, 0, 1, 0) and set λ(•) = µ • Leb(•), the permutree process leads to a stochastic process that simulates a Mondrian process [88, 87] on [0, 1] with the intensity µ and the budget 1. This fact can be easily derived by interpreting the permutation process as follows. In the above setup, the sample generated by the permutation process can be restricted to a binary tree by following the procedure described in Markov process with an intensity µ and a time limit of 1. Furthermore, if we consider the horizontal location of the marked point process as the position where the line segment of length 1 is cut, we can consider this time evolution as a hierarchical partition of the line segment. Therefore, this can be regarded as a Mondrian process.C Bayesian inference for phylogenetic permutree (omitted in Section 5)This section reveals the Bayesian inference algorithm for phylogenetic permutree analysis using our permutree processes. For the sake of generality, we will use the marked point process representation described in Section 3 in particular as a permutree process. This argument can also be applied, with minor modifications, to the special case of the marked stick-breaking process (with its finite truncation) described in Section 4.methods can be realized by sequentially iterating the following two update rules: (i) updating the permutree process (ii) updating the evolutionary model. Since the latter can be supported by standard inference methods to evolutionary models, it is the updating method of the former that is particularly important here. For the former, various inference algorithms that have been proposed for generic marked point processes and their extensions [68, 69, 26, 96, 43, 104, 30, 55, 31, 14, 35, 109] would be applicable, since the entity of the permutree process is a marked point process as shown in Section 3 of the main text. This section describes a useful inference method that exploits an important property of Poisson processes, namely, that a certain Poisson process can be obtained by thinning operations from another Poisson process with higher intensity. Section C.1 provides a brief description of the thinning operation for the Poisson process as a preliminary to our MCMC method. Then, Section C.2 once again writes down the whole generative probabilistic model, since it should be possible to see at a glance what the parameters to be inferred are in the permutree process and its phylogenetic tree described in Section 5. Finally, Section C.3 describes the MCMC inference algorithm.Our MCMC method uses important properties of Poisson processes. Specifically, we will discuss how to represent a certain Poisson process via another Poisson process with higher intensity.Homogeneous Poisson process -In this paper, we mainly consider homogeneous Poisson processes on [0, 1] × [0, 1], i.e., where the intensity function is given by a constant. A Poisson process on [0, 1] × [0, 1] with intensity µ (where 0 < µ < ∞) is a stochastic process for a random set of points, where the number of points belonging to (x 1 , x 2 ] × (y 1 , y 2 ] follows a Poisson distribution with the parameter µ(x 2 -x 1 )(y 2 -y 1 ) for any 0 ≤ x 1 < x 2 ≤ 1, 0 ≤ y 1 < y 2 ≤ 1. For notational simplicity, we will denote a Poisson process on [0, 1] × [0, 1] with intensity µ by PP(µ, [0, 1] × [0, 1]).We also recall that in the main text, we defined this homogeneous Poisson process as the Poisson process with the intensity function λ(•) = µ • Leb(•) as an equivalent expression, where Leb(•)indicates the Lebesgue measure.processes is that a Poisson process with a certain intensity can be obtained by applying the thinning operation from a Poisson process with a higher intensity. More specifically, a Poisson process with intensity µ can be constructed as follows:(i) We generate a random set of points from a Poisson process with intensity ν (> µ).(ii) For each point generated, independently decide whether or not to accept it with probability µ/ν.(iii) The set of only accepted points can be regarded as following the Poisson process with intensity µ.As input observation data, we consider DNA (molecular) sequences x j (j = 1, . . . , N ) observed at letter length S over N species. For example, the sequence x j = GAGTAC has length S = 6. by each element of the matrix correspond to the four different letters A,C,G, and T. We regard these DNA sequences as following a phylogenetic tree based on a permutree. First, we generate the marked points {(l i , m i ) : i = 1, 2, . . . n} and the corresponding permutree T from the permutree process. We recall that the transformation from marked points to permutree can be performed by the transformation in Figure 9 (which we will call MPP2PT). Then, we represent coalescence, recombination, multiple ancestry, and mutation events in genealogy by combining the four types of the decorations , , , with the following interpretations:• Coalescence -A coalescence event represents two lineages having a common ancestral lineage.• Recombination -A recombination event represents the joining of two exclusive subsequences of two lineages by one lineage.• Partition -We give the decoration the role of division so that a single permutree can represent a phylogenetic tree with multiple ancestors. Specifically, we connect the two left edges and similarly connect the two right edges to lead to two unconnected tree structures on either side of decoration .• Backward in time (optional) -We suppose that no mutation occurs when going back in time from a vertex to a vertex with . . Then, we generate random locations l 1 , . . . , l n from the Poisson point process of the intensity λ (middle figure). Finally, for each random location, we independently assign one of the decorations { , , , } from the uniform categorical distribution as a random mark m i (i = 1, . . . , n) (bottom figure). The resulting marked point process {(l i , m i ) : i = 1, 2, . . . n} can be regarded as a random decorated permutation. Right: Transformation to random permutree -Note that the marked points generated from the marked point process can be considered as a decorated permutation by noting its horizontal and vertical ordering. Since decorated permutations and leveled permutrees have a one-to-one correspondence, we are guaranteed to be able to construct their bijective transformation. First, auxiliary lines (red dashed lines) are drawn below decorations , and above decorations , . From this point on, we will extend the permutree edges, but it is important to emphasize that the permutree edges do not cross these auxiliary lines. Next, if we look at the auxiliary lines extending all the way to the bottom, we can see that this divides the lower region into smaller sub-regions (indicated by the red oval). Then, one edge is extended from each sub-region. The edges are extended from bottom to top, and when the height of each vertex is reached, the edges adjacent to that vertex are connected (indicated by the gray boxes). This is done until all vertices are covered, resulting in a leveled permutree. Finally, if we forget about the vertical position of each vertex in the leveled permutree and focus only on its structure as a directed tree, we obtain the corresponding permutree.(c , c , c , c ). We obtain the following joint probability density function:EQUATIONwhere P obs is the probability density function (PDF) of Equation ( 15), P evo is PDF of Equation ( 13), P PP is PDF of Equation ( 16), and subsequent terms are PDFs of the standard distributions. The posterior distribution of the parameters H, b, w, z, L, m, c to be estimated is proportional to this joint probability density.We can construct the MCMC algorithm by iteratively repeating the following update rules for the DNA evolution H on the phylogenetic permutree, the binary indicators b, the leaf node weights w, the observation assignments z, the redundant locations L, the redundant marks m, and the decoration weights c.Update rule for DNA evolution H -We recall that each element of the matrix H = (H s,j ) S×N consists of one of the letters A, C, G, or T. Using Equation ( 21), we calculate the joint probability that Then we obtain the following Gibbs update rule:H s,j ∼ Categorical(p A , p C , p G , p T ) (s = 1, . . . , S, and j = 1, . . . , N )Update rule for binary indicators b -For each i = 1, . . . , K, we can obtain the Gibbs update rule derived by calculating the posterior probability ratio for b i = 0 and b i = 1 using Equation (21) .Specifically, we suppose that the value of the joint density for b i = 0 is π 0 and the value for b i = 1 is π 1 , and then we obtain the following update rule:EQUATION)Update rule for leaf node weights w -From the conjugacy of the Dirichlet and Categorical distributions, we obtain the following Gibbs update rule:EQUATIONwhere N i (i = 1, . . . , |LN (T )|) indicates the number of the observation sequences x j (j = 1, . . . , N ) which is assigned to the ith leaf node of the phylogenetic permutree T .Update rule for observation assignments z -Using Equation ( 21), we calculate the joint probability that each observation sequence x j (j = 1, . . . , N ) is assigned to the ith (i = 1, . . . , |LN (T )|) leaf node of the phylogenetic permutree T , and let wi denote it. Then we obtain the following Gibbs update rule:EQUATIONUpdate rule for redundant locations L -We use the simple Metropolis-Hastings (MH) method.For each position, we generate a new candidate sample from the normalized probability measure λ of the intensity function λ, that is, li ∼ λ (i = 1, . . . , K), and decide whether to adopt it through the MH acceptance/rejection scheme using Equation (21) .Update rule for redundant marks m -Using Equation ( 21), we calculate the joint probability that each element mi has , , , , respectively, and let p , p , p , p denote them respectively.Then we obtain the Gibbs update rule: mi ∼ Categorical p , p , p , p (i = 1, . . . , K) where N * ( * ∈ { , , , }) indicates the number of the marks mi (i = 1, . . . , K) which has the decoration * .To investigate the empirical impact of finite censoring on the marked stick-breaking process described in Section 4, we report in Figure 15 the prediction performance for different levels of finite censoring, K = 25, 50, 100 and 150, in the same experimental setup as in the main text (Section 5). It can be seen that when the level of finite truncations is extremely restricted, the prediction performance has been reduced, while when some level of censoring is ensured, the prediction performance is not so reduced. This can be seen as reflecting the fact that the marked stick-breaking process can adjust its own real model complexity in a data-driven manner according to the observation data. Figure 13 : Illustration of simplest inference method for permutree process as marked point process.The current leveled permutree in Markov chain Monte Carlo inference corresponds to a certain state of the marked point process (left). One marked point (slightly enlarged and colored red) is chosen to be a candidate for updating. The region to be updated is quantized (center) to generate a new candidate marked point (slightly enlarged and colored blue) from the conditional posterior probability (or some proposal distribution). Finally, the generated new marked points are updated or not by the Metropolis-Hastings scheme, which is the next state of the Markov chain (right).The main difficulty in applying the permutree process to data modeling is how to handle its unlimited finite or infinite model complexity (i.e., number of vertices). Roughly speaking, it is not possible in principle to naively implement a model with infinite parameters on current computers. This is a central topic in the BNP field, and we have historically had two policies. One is to represent models of infinite complexity such that finite truncation works reasonably well. This corresponds just to the representation methods for the stick-breaking process [89] in Dirichlet process infinite mixture models [79] and the beta-Bernoulli process in infinite factor models [95, 93] . The other method is a model representation in which, in conjunction with the finite amount of observed data, the model activates only as many of the potentially infinite number of parameters as necessary. This corresponds to the Chinese restaurant process [74, 76] in the mixure models or the Indian buffet process [29] in the factor models. While Section 4 focuses on the former policy, this section will explore the latter.We begin our discussion with a representation using oCRP for binary trees, a special case of permutrees. Let θ > 0 be the concentration parameters and α > 0 the discount parameter. We will now take a so-called spinal decomposition (Figure 16 left) of the binary tree. In the metaphor of CRP, the customer can be viewed as as seeking a dish at the terminal node of the binary tree. The new customer can then either proceed to the existing subtree or create a new branch on one of the edges, according to the proportions shown in Figure 16 right. This can be viewed as CRP with random ordering of the CRP tables.Ordered Chinese restaurant process (oCRP) [77, 85] -This stochastic process is a generative prbabilistic model that constructs a random binary tree by means of a recursive structure as follows.Let α and θ be the discount parameter and the concentration parameter, respectively.• The first customer goes straight from the root to form one terminal node.• The second customer forms a split between the root and the terminal node where the first customer is located. At this stage, the advanced subtree of the second customer is assigned a weight of 1 -α and each edge of the split spinal cord is assigned a weight of α and θ, respectively.• The third and subsequent guests determine their own destination according to the proportion of weights assigned to the subtree and each edge on the spinal cord. If it chooses an edge on the spinal cord, it creates a new branch there to become a subtree and assigns weight α to the newly created edge on the spinal cord. If it moves on to an existing subtree, it recursively determines its own destination according to the nested oCRPs on that subtree and adds 1 to the weight of the subtree.One will notice that this stochastic process is very similar to the standard Chinese restaurant process (CRP). If each subtree is considered a table, the probability that a new customer will sit at an existing table is proportional to the weight of the number of customers already sitting at that table minus the discount parameter α. It will be seen that this is the same situation as in the standard CRP corresponding to the well-known Pitman-Yor process [76] . However, it differs from the standard CRP in that when a new table is seated, that table is determined by reference to the order of the existing tables. For this reason, this stochastic process is called an "ordered" CRP.One of the most important properties of oCRPs is exchangeablity:Theorem D.1 (Proposition 1 (a) [77] ). A random binary tree generated by the nested oCRPs with the discount parameter α and the concentration parameter θ has exchangeable leaf labels for all n ̸ = 1if and only if α = θ = 1/2.Strategy sketch and advance notice -Recalling the requirements of (C1) and (C2) for the definition of permutrees (Section 2), we could introduce the following metaphor of CRP (See also Figure 17 ):• Each customer is looking for a dish in a Chinese restaurant street and prefers a street that is popular with other customers, but is also willing to explore new streets on a whim. The development of the streets, with one customer after another searching for a dish, represents the permutree evolution.• The Chinese restaurant street has a recursive structure. The boulevard (main street) has side streets, and each side street becomes the next boulevard, with its own next side streets recursively.This recursive structure would be reminiscent of an existing oCRP or nested CRP that recursively calls smaller CRPs in the overall process. When a side street becomes a cross street, it represents a vertex with . If the side street extends only one way, it corresponds to a vertex with or . Chinese restaurant street (CRS) -CRS is given by the recursive structure of the streets, consisting of boulevards and side streets. Let θ 1 > 0 and θ 2 ≥ 0 be the concentration parameters and α > 0 the discount parameter. Figure 18 illustrates the situation where a new boulevard is a small CRS in a large CRS with the recursive structure. A CRS at a certain level consists of a boulevard and side streets, where each side of the boulevard is weighted by the concentration parameters θ 1 , θ 2 and the discount parameter α, and each side street is assigned a weight equal to the number of customers who proceeded to it minus the discount parameter α. When the next customer enters this boulevard, the next destination is determined according to the ratio of those weights. It would have been a wishful idea if this vanilla CRS could be used as a permutree model, but unfortunately, it does not satisfy the requirements (C1) and (C2) as it is.Properties -(1) The most important feature of CRS is that it is an extension of the existing oCRP.Specifically, in the case of θ 2 = 0 (i.e., a situation where both boulevards and side streets grow only to one side), CRS is equivalent to oCRP for random binary trees. ( 2) Another important property is exchangeability (i.e., invariance of probabilities with respect to the order in which customers enter the process), which is often the case with variants of CRPs. For our CRS, we can show that it is exchangeable in the case of α = θ 1 + θ 2 = 1/2, inheriting the result of exchangeability [77,Proposition 1] of oCRP. This property would be helpful in Bayesian inference.Theorem D.2. A random tree generated CRS with the discount parameter α and the two concentration parameters θ 1 and θ 2 (described in Section 3.2 of the main text) has exchangeable leaf labels for all n ̸ = 1 if and only if α = θ 1 + θ 2 = 1/2.Proof. This can be verified by inheriting the exchangeability of oCRPs described in Theorem D.1.We shall consider each subtree in oCRP as a table and assign natural numbers of labels to the tables, starting from 1 according to the order in which the tables were generated. By reducing the resolution of the leaf labels in Theorem D.1 to table labels, the ordered tables generated by oCRP are also exchangeable. Then, for the random tree generated by CRS, if we consider each subtree as a tableand set θ 1 + θ 2 = θ, this is also attributed to the random ordered tables of oCRP with the discount parameter α and the concentration parameter θ. Thus, by repeatedly applying the fact that the table labels of oCRP are exchangeable only when α = θ = θ 1 + θ 2 = 1/2, until each table eventually becomes a leaf node, we can confirm that the CRS has exchangeable leaf labels.This section verifies that the marked points {(l i , m i ) : i = 1, 2, . . . n} generated from the marked point process are correctly transformed into permutrees by the algorithm in Figure 9 (Algorithm 1 of the main text). This can be verified by the following procedure, which is similar to the method in the proof of Proposition 8 in [75] .(i) There is exactly one strand in each section separated along the auxiliary line (the red dotted line in Figure 9 ). This can be shown by mathematical induction on the number of nodes in the permutree.(ii) The graph created by the algorithm in Figure 9 has no cycles. This can be shown by using the proof by contradiction. If the graph had cycles, it would cross the red dotted line. However, by construction, the graph never crosses the red dotted line. When the new boulevard is opened up, which direction is the forward or backward road is determined with probability 1/2. The figure shows the case where the forward road is up. Given two concentration parameters θ 1 > 0 and θ 2 ≥ 0, the first customer to enter through the entrance chooses the forward road with probability θ 1 /(θ 1 + θ 2 ), otherwise the backward road, and receives the dish being served at the end. We assign weights θ 1 and θ 2 to the forward and back roads, respectively. At this stage, the one that the customers did not choose between the forward and backward roads (the lower backward road, represented by the dashed line in the figure ) has not yet been activated. Until both the forward and backward roads are activated, the entrance itself serves as another endpoint of this boulevard. (b): The next customer coming to this boulevard, entering through the entrance to this boulevard, will proceed to the side street on that side in the proportion according to the weights assigned to each side. This side street itself corresponds to the boulevard in the next smaller CRS in the recursive structure. That is, the forward direction of this side street (i.e., whether it extends to the left or right first in the figure) is determined by this customer with probability 1/2. The concept of whether the forward or backward road is chosen first on each side street determines whether the vertex corresponding to this side street in the permutree structure extends initially to the parent side or to the child side. (c): Given a discount parameter α ≥ 0, this side street is assigned a weight of 1 -α, which is the number of customers who have taken the side street minus the discount parameter α. The edge divided by the side street is assigned a weight of the discount parameter α.(d)-(e): When the next customer decides where to go based on the ratio of weights assigned to edges and side streets, she/he may choose an inactive road (dashed line in (c)). In that case, after the new side street is added (which also releases the entrance termination facility), the backstreet beyond it (dashed line in (d)) will continue to remain inactive. (f)-(g): The above procedures are repeated sequentially and recursively.(iii) From (i) and (ii), the graph generated by the algorithm in Figure 9 is a tree, and furthermore, since the red dotted line separates the left and right ancestor and descendant sub-trees, this is a leveled permutree.Justification: In general, phylogenetic tree analysis can sometimes have significant impacts in our daily lives. For example, during the SARS-CoV-2 pandemic, it has recently been used to analyze the spread and evolution of pathogens [52, 60] . We believe that the permutree process proposed in this study could be an important elemental technology for such phylogenetic tree analysis in the future. In order to focus on permutree methodology in machine learning, this paper uses the classical model for the DNA evolution model as is.However, it will be necessary to improve the model to a more sophisticated model that can represent real-world phenomena more precisely in order to provide some insights for real-world applications. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer Some readers may wish to consider another typical situation: a path where the data starts at one of the terminal nodes and "stops at an interior vertex" of the permutree. This modification can be easily achieved by additionally introducing a chain of Bernoulli trials[10] or a time limit by representing the growth of the path as a Markov process on a virtual time axis[88,87]. Therefore, we will focus on the most basic situation.This is equivalent to a categorical-Dirichlet hierarchical model with two classes (two tables). We can obtain the form described in the text by marginalising the intermediate Dirichlet variable in this hierarchical model. 
 
 Appendix:  


Decision: Summary of recommendation: Reviewers' scores for this paper were relatively high, but the actual content of their reviews was scant on strengths and reported a high degree of uncertainty and confusion about the paper's content. From the reviews, I was not convinced that the reviewers had been able to meaningfully evaluate the paper, partly due to the fact that much of the paper's technical content appears in the supplementary material. I read the paper myself and agree that the important ideas are very difficult to understand and evaluate from the main text, and believe the paper needs a major revision before it can be properly reviewed/evaluated at an ML conference.

This paper draws on a new concept in combinatorics called a permutree to construct a novel stochastic process---the permutree process---which can represent a range of "combinatorial structures such as permutations, binary trees, partitions, and binary sequences". The paper proposes this process as a Bayesian nonparametric prior which generalizes and unifies a large number of existing ones (e.g., CRP, IBP, Mondrian process, among many others). The reviewers were all impressed by the paper's sweeping generality, one reviewer saying: "an ambitious paper! [...] It has a large vision of building one grand unifying theory of discrete Bayesian nonparametrics". 

Several aspects of the paper are very clear. Its grand vision of a unifying framework of BNP processes as permutree processes is clear. What exactly a permutree is, along with other prerequisite concepts in combinatorics, is explained clearly (reviewers appreciated this). What exactly the proposed permutree process is---i.e., a marked Poisson point process on $[0,1] \times [0,1]$ with marks taking values in the set {$\vee, \wedge, |, \times$}---is also clear.

Several important aspects of the paper are not clear. What data analysis actually looks like using the permutree process is very hard to grasp from the main text. For instance, the main text does not include any example of a full model described mathematically according to its generative process. The paper reports one case study, where it builds a model based on permutree processes for phylogenetic tree analysis. However, basic facts about the model (e.g., its likelihood) are not described sufficiently, and appear only in highly condensed prose. After reading the main text, I was unable to write down for myself what the actual model discussed in Section 5 was; reviewers made similar comments to this effect. (Many of these details do appear in the supplementary material, including a full generative process, and a detailed description of the model's rationale; I'll return to this later.)

Another important aspect of the paper that is not made clear by the main text is whether the proposed framework really does succeed at unifying BNP processes under a useful abstraction. Reviewers complained about a lack of any clear example showing how a well-known process (e.g., a CRP) is an instance of a permutree process. For instance, the same reviewer quoted above goes on to say: "The subsequent developments of the theory and applications don’t quite live up to the grand vision set out earlier in the article. The authors struggle to represent the most widely-used discrete BNP object of the Dirichlet Process in this supposedly all-encompassing framework [...]". (Again, many more details along these lines do appear in the supplementary material.)  

Finally, taking as given that the proposed abstraction does indeed generalize most well-known BNP processes, the paper does not clearly demonstrate a benefit in doing so. I can imagine several potential benefits of an abstraction that unifies many BNP processes: one might use that abstraction to prove something that applies to many known models, one might use that abstraction to craft new BNP processes whose properties can be easily characterized, one might use that abstraction to build a general-purpose inference scheme, the list goes on. While the paper does build one model using the new abstraction, the details of that model are difficult to understand and evaluate, and the benefits of the abstraction are not clearly illustrated.

The lack of clarity that the reviewers commented on and that I have written about here is due mainly to the way the paper is structured, leaving critical details and necessary exposition in the supplementary material. There are  no guidelines at NeurIPS about how to structure a submission; however reviewers at NeurIPS (and most ML conferences) are not required to read the supplementary material, and often don't. In this case, I do not think the paper is understandable from the main text, and am not convinced that the reviewers were able to properly evaluate it. The paper reads like a journal article that was crammed into a conference paper. I think this paper needs to be rewritten so that its contributions can can be illustrated, demonstrated, and appreciated in the main text before it is ready for acceptance at a venue like NeurIPS.

Reviews: review: paper_summary: paper_summary: The authors describe the concept of permutrees, how to sample permutrees in a stochastic process, and how to model data with permutrees. They apply it to tracking DNA changes.
strength_weakness: strength_weakness: the figures are small and hard to read when printed in gray-scale
questions: questions: I do not know what a stick breaking process or Chinese restaurant process is?

>Fig.1 (l) 

It is not obvious how the binary number is generated.
Could one say if the line from one node to the next goes up it yields 1 and if it goes down it yields 0?

>p7 253 numnber 

number ?

>p7 261 "tiny real value"

how tiny is tiny ?

>p16 669 uniformly random random random variables Uj

is that more random than just a random variable?
limitations: limitations: yes
paper_summary: paper_summary: The authors introduce a prior for Bayesian nonparameterics called the permutree. They apply it to model complex phylogenetic data with both coalescence and recombination, a setting that previous processes such as the Kingman could not model; the model seems to perform state-of-the-art phylogenetic inference. In principle the process could also be used to model other combinatorial objects such as permutations or trees however this is not demonstrated.
strength_weakness: strength_weakness: The writing is very challenging. There are multiple points where the writing is strange, for example the use of "dare" in "For technical reasons (discussed immediately below), we dare to pay particular and explicit attention here to the set V of the “interior vertices” (i.e., vertices of degree at least 2) other than the terminal nodes." ". The exposition is also very verbose and proposition is challenging to understand without reading the proof. Figures 3(c) and 1(b)-(d) are never mentioned in the text, the later is quite confusing since it seems to suggest that the permutree can model many combinatorial objects.

It seems that there is a disconnect between the description of the methods in sections 3, 4, and the experiment in section 5. See questions.

The ultimate goal of phylogenetics is to infer ancestry which is not identical to maximizing likelihood. To validate a bone fide phylogenetic inference method that handles recombination, one should show that inferred recombination events are realistic.
questions: questions: In section 3 you state that you generate $l$ from a Poisson process then in section 4 you use a stick-breaking procedure. Which do you use in practice? In the genetics case, $l_k$ is stated to be drawn from a point process in eqn 7. if this is the case, is the data still modeled as part of an infinite exchangeable process? How could I query the posterior predictive for example?

In the genetics case, could you explain the role of the two table Chinese restaurant process? It seems that sequences are clustered by node and that the path does not affect their likelihood.

What is the form of the likelihood for recombination?
limitations: limitations: Discussed.
paper_summary: paper_summary: After giving an introduction to permutrees, a stochastic process on them is constructed by sampling the nodes according to an intensity function on the 2d unit interval and uniformly assigning the marks. It is shown how to add the edges to meet the requirements for the object being a labeled permutree. Paths from terminal nodes to other terminal nodes in the permutree can be used to represent sequential data. Finally, the model is used for an inference task involving DNA sequences.
strength_weakness: strength_weakness: * As a reader unfamiliar with phylogenetic analysis, I did not immediately understand what the task in this setting is (and I am still unsure if I fully got it): Do you have a set of DNA sequences where some of the letters are masked, and you want to predict the masked letters? 
* Besides not really understanding what the goal of this task is, I think Section 5 does not provide enough explanation of how this goal then is achieved, i.e., the length of the paper/ the level of detail in Section 5 is a problem. It's ok to defer details to the appendix as long as one can still follow the main section without them, but I struggle with that. Example given: I find it crucial to know the likelihood function when it comes to a Bayesian inference task, which is not mentioned in the main section.
questions: questions: * What is the task in the phylogenetic analysis application? 
* What would be other tasks where inference on permutrees is relevant in machine learning?
limitations: limitations: yes, there is a dedicated paragraph on limitations and I think it captures the limitations of the suggested concept appropriately.
paper_summary: paper_summary: This article adapts the recently-developed combinatoric concept of the “Pemutree” into a machine learning context, making links with existing methods in Bayesian nonparametrics, and providing a pathway for how to make the abstract mathematical concept relevant to data-driven approaches and inference. The theory is explained, and an example application in phylogenetic analysis is performed.
strength_weakness: strength_weakness: The subsequent developments of the theory and applications don’t quite live up to the grand vision set out earlier in the article. The authors struggle to represent the most widely-used discrete BNP object of the Dirichlet Process in this supposedly all-encompassing framework: perhaps this is doable in the future and represents work yet to be done, but the initial claims about the generality of permutree processes made in the article are not fully followed through on.

The article also (necessarily) spends a lot of time introducing the theoretical framework, quite heavily at the expense of presenting the data applications properly later in the manuscript. Squeezing all of the experimental results into “Demonstration” in half a page is really too brief to be very convincing, although there is a lot of interesting material in Appendix C that would ideally be in the main text. Many of the potentially thorny issues concerning inference and computation are therefore overlooked.

Some of the figures could be better designed: I found the visual interpretation of permutrees key to developing some understanding them, so making Figure 1 bigger and more prominent would be a help (I think figure 1 is more crucial than Figures 2/3/4 in this respect). The representation of the data in greenscale Figures 8 and 14 is very confusing: I don’t think I really learned anything from that representation.

Some of the language choices are a bit strange: line 69: “we dare to pay particular and explicit attention here”, line 869: “Roughly speaking, it is not possible in principle to naively implement a model with infinite parameters on current computers”, 

Line 250: “as an overall trend…” The analysis of the experimental results is not rigorous enough. You have real values and uncertainties for the perplexity. Do some tests or similar to establish more clearly the differences in performances rather than painting broad brushstrokes.

Line 80: some of the symbols used have already established meanings in a machine learning context, i.e. \otimes meaning kronecker product. Maybe make clear that this is a new notation that overrides any previous perceptions.
questions: questions: Line 219: “Data path modelling” the introduction of the two-table Chinese restaurant process is instructive, but might reveal the limitations of the model framework: are the only methods that can be captured by a permutree some variation on iterative applying of CRP-style binary splits and merges? Do you really think that this is a large enough “basic vocabulary” of operations to cover the entire world of discrete BNP methods out there? Is that a provable statement?
Line 336: epsilon = 0.01: where does that come from?

Appendix C.3: How would you describing performing the inference for this model? Did it need much fine tuning? Did it need lots of mixing time? Did it need a lot of computational resources? What about the comparison methods? Is this this “fancy but expensive” model? No shame if so, but it’s good to know this.

Line 887: “ordered Chinese Restaurant Process” - what are the material, practical implications of adding the ordering of tables on top of the standard chinese restaurant process? Can this model still answer the same type of statistical problems that a standard CRP does? Do the  categories/clusters observed in the data need to have some sort of ordering for this to be valid? Can the permutree represent a totally standard CRP without this ordering? If the permutree cannot represent the most widely used discrete BNP model then the claims towards the start of the paper about this being the grand unified framework need toning down.

Line 912: “Chinese Restaurant Street” - i worry that between the indian buffets and the Chinese Restaurant Franchises then the underlying metaphor is being overextended in this community. Why exactly have you proposed this model formulation? Do you consider it to be a useful new potential BNP model that has been underexplored so far? Is this the closest thing you can derive within this framework to a standard chinese restaurant process? This is unclear to me.

Random non-crucial question from an interested non-combinatorist: Can you define permutrees in a >2d space? This will surely change the topologically allowable relationships between nodes.
limitations: limitations: The practical models that are (presently) successfully captured in this framework are not the most widely used BNP models out there. The whole permutree framework seems best suited to the coalescent-type models pursued, and the other BNP models that have been successfully described, such as Mondrian processes, are interesting but not in widespread use.

Comments: title: response
Supplement to author response.
Supplement to author response.
comment: We would like to thank you again for your kind comments and constructive feedbacks. As you mention, it is very important to clarify the existing BNP models within our framework. Your enlightening points have made this point much clearer. We really appreciate that we have been able to discuss this point in this valuable forum.

With kindest regards,  

The Authors
We would like to thank you again for your valuable time and thoughtful comments. We are particularly pleased to have this valuable opportunity to discuss with you the potential applications of machine learning.

With kindest regards,  

The Authors
This was illuminating, thank you.

I think that clarification concerning how different existing BNP models fit within the permutree framework is important to really make the contribution of this article clear.
Thank you for the clarifications. I was a bit unsure about the relevance for the machine learning setting, but the answer to Q2 makes me more confident in that regard. I raise my score from 6 to 7.
We thank you again for your time and thoughtful comments. We are very appreciative of your comments, which have helped us to increase the clarity of our revised version even more.

We remain available in case any additional query arises.

With kindest regards,  

The Authors
Thank you for clarifying. Due to the challenging presentation and challenges in validating the genetics modeling case. I keep my score the same.
---
**[Q3] Motivation for Chinese restaurant street.**

>  “Chinese Restaurant Street” (...) Why exactly have you proposed this model formulation?

The motivation for Chinese restaurant street is to derive an alternative representation for stochastic processes with an inherently infinite dimensional parameter space that would work with only a finite number of parameters for a finite number of observations. This can be summarized as follows in contrast to the marked stick-breaking described in Section 4 of the main text.

| Model | Target combinatorial object | Parameter dimension |
| ---- | ---- | ---- |
| Marked stick-breaking process | Permutree | Infinite (even for finite observation) |
| Chinese restaurant street | Permutree-'like' | Finite (for finite observation) |

This relationship is a frequently discussed contrast in Bayesian nonparametric methods, where two model representation methods have often been explored, for example in infinite mixture models for partitions and infinite factor models for binary sequences, as follows.

| Model | Target combinatorial object | Parameter dimension |
| ---- | ---- | ---- |
| Stick-breaking process | Partition | Infinite |
| Chinese restaurant process | Partition | Finite |
| Beta-Bernoulli process | Binary sequence | Infinite |
| Indian buffet process | Binary sequence | Finite |

The main advantage of the Chinese restaurant street, the standard Chinese restaurant processes and the Indian buffet processes is that they do not require finite approximations in inference. In contrast, the marked stick-breaking process, the standard stick-breaking processes and the beta-Bernoulli process have infinite parameters with probability $1$, regardless of the size of the input observation data, so their parameter inference generally requires finite approximations as described in Section 4, and intricate mechanisms such as slice sampling.

Finally, we would like to note that the current Chinese restaurant street is not a perfect model, as discussed in the appendix. The sample that this stochastic process could generate certainly has a permutree-like structure, but it does not fulfill the exact definition. More specifically, of the two requirements mentioned in Section 2 - (C1) that each interior point has one or two parents and (C2) that each interior point can be horizontally aligned - the latter is not straightforwardly satisfied. However, we believe that this modeling strategy is worth discussing in the appendix to this paper, as it follows a natural extension of CRP -> oCRP -> Chinese restaurant street.

---
**[Q4] Practical computational cost.**

Roughly speaking, our model is only a minor modification (adding a new 'decoration mechanism') of the standard stick-breaking process for the Dirichlet process infinite mixture model, so the substantial increase in computational complexity is not cause for concern. We add a diagram of `MCMC iterations $\times$ perplexity’ and ‘wall-clock $\times$ x perplexity’. As there was not enough space in the one-page PDF of the global response, we would like to update it directly in the revised version.

---
**[Q5] Permutrees on high-dimensional space.**

> Can you define permutrees in a >2d space? This will surely change the topologically allowable relationships between nodes. 

This is a very interesting topic. We don't have a direct answer to your question, but we may be able to offer some relevant and interesting insights. We are interested in what is the continuous analogy for a discrete structure of the permutree. In the machine learning community, the hyperbolic space is often mentioned as a continuous analogue to the binary tree (e.g., [Nickel&Kiela, NeurIPS2017]), which is a special case of the permutree:

| Representation | Target combinatorial object | Space |
| ---- | ---- | ---- |
| Discrete | Binary tree | Ultrametric space |
| Continuous | Continuous analogy of binary tree (continuous hierarchy) | Hyperbolic space |
| Discrete | Permutree | Ultrametric / Euclidean |
| Continuous | Continuous analogy of permutree | (Future work) |

We expect that research could be developed in this direction in the near future. Very exciting question, thank you very much.

- [Nickel&Kiela, NeurIPS2017] Poincare embeddings for learning hierarchical representations, NeurIPS2017.

---
Finally, thanks again for your valuable comments.
---
**[Q4] Role of two-table Chinese restaurant process.**

> In the genetics case, could you explain the role of the two table Chinese restaurant process? It seems that sequences are clustered by node and that the path does not affect their likelihood. 

Thank you for your important question. We would like to address your concern as follows:

The role of the two-table Chinese restaurant process (2tCRP) serves to bring together DNA sequences that follow similar lineages (evolution over time) within a collection of observed DNA sequences. The tables that our 2tCRP have can be regarded as checkpoints for events (such as coalescence and recombination) in the time direction (vertical in the diagram) in gene evolution. The table serves to group together DNA sequences that can be regarded as having behaved identically at the checkpoints by means of table assignments. Our 2tCRP allows a collection of observed DNA sequences to be stored as data paths on a permutree to define a prior distribution. The likelihood of these data paths is then evaluated by using the evolutionary models such as the Jukes-Cantor model and the generalized time reversible model.

This modeling strategy can also be seen as an extension of the Dirichlet diffusion tree [Neal2003] for representing binary trees to a new model for representing permutrees. Dirichlet diffusion trees also represent data diffusions in a similar way to the table assignment probabilities we use when an event occurs. We would like to add an explanation of the motivation for the 2tCRP in terms of this extension of the Dirichlet diffusion tree.

- [Neal2003] Radford M. Neal. Density modeling and clustering using Dirichlet diffusion trees. Bayesian Statistics, 7:619–629, 2003. 

---
**[Q5] Likelihood for recombination.**

> What is the form of the likelihood for recombination? 

The recombination is just selecting a split position uniformly at random. That is, the likelihood model of recombination is the concatenation of two DNA subsequences at the mutation-free, non-informative uniform split position. More specifically, as a generative probabilistic model, given two sequences (e.g., ACGTTC and GCGTCA), the recombination can be viewed as a stochastic operation that

- The split position ( **** , ** ) of the sequence ( ****** ) is generated uniformly at random.
- The two sequences are converted into a sub-sequence ( ACGT** ) leaving only the left side and a sub-sequence ( ****CA ) leaving only the right side of this split position, which are then concatenated and recombined into a single sequence ( ACGTCA ).

It should also be emphasized that the likelihood model other than this uniform random split is separately represented by the evolutionary models. The recombination is assumed to be instantaneous and not accompanied by mutation. This means that the likelihood model for genetic mutation is separately represented by the JC and GTR models.

---
Finally, thanks again for your valuable comments.