{'fraction_non_alphanumeric': 0.05272544866793, 'fraction_numerical': 0.019563036450785866, 'mean_word_length': 4.005020920502092, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A note on the geometry of the MAP partition in some Normal Bayesian Mixture Models

We investigate the geometry of the maximal a posteriori (MAP) partition in the Bayesian Mixture Model where the component distribution is multivariate Normal with Normal-inverse-Wishart prior on the component mean and covariance. We prove that in this case the clusters in any MAP partition are quadratically separable. Basically this means that every two clusters are separated by a quadratic surface. In connection with results of Rajkowski (2018), where the linear separability of clusters in the Bayesian Mixture Model with a fixed component covariance matrix was proved, it gives a nice Bayesian analogue of the geometric properties of Fisher Discriminant Analysis (LDA and QDA). We also describe a simple model where the covariance shape is fixed but there is a scaling parameter which may change from cluster to cluster. We prove that in any MAP partition for this model every two clusters are separated by an ellipsoid.


Introduction
In the standard setting of Bayesian Mixture Models we assume that the target distribution is a random mixture of distributions from some parametrized family. We assume that the probabilities of components are sampled from a (perhaps infinitely dimensional) simplex and the parameters of the component distribution are sampled independently for each component (Tatarinova and Schumitzky [2015]). A prominent example is the Dirichlet Process Mixture Model (Antoniak [1974]), where the prior distribution on the probability weights is Sethuraman's stick breaking process (Sethuraman [1994]).
A popular choice of the component distribution is multivariate Normal, which gives Normal Bayesian Mixture Model. There are two standard conjugate prior distributions on the component mean and covariance matrix (Gelman et al. [2013], Chapter 3.6): Normal distribution on the mean with fixed component covariance matrix or Normal-inverse-Wishart distribution (here the terminology is adopted from Murphy [2007]), where the component covariance matrix follows the inverse-Wishart distribution and the component mean (conditioned on the component covariance matrix) is Normal. The exact specification of these priors is given in Section 2.2.
Bayesian Mixture Models give a basis for cluster analysis. Indeed, one can translate the distribution on component probabilities into a discrete prior distribution on the possible data partitions -just like Sethuraman's construction translates in to the Generalised Pólya Urn Scheme (Blackwell et al. [1973]), also known as the Chinese Restaurant Process (Aldous [1985]). The inference about clusters is based on the posterior distribution on the space of partitions. Analysing partition which maximises the posterior probability (the MAP partition) seems to be a natural choice.
In Rajkowski [2018] it is proved that in the Normal Bayesian Mixture Model, when the component covariance matrix is fixed and the prior on the component mean is Normal, the MAP partition is convex, i.e. the convex hulls of clusters are disjoint. An equivalent formulation is: for every two clusters in the MAP there exists a hyperplane that separates them.
Placing an inverse-Wishart prior on the cluster covariance structure, with covariances for different clusters, independent of each other, gives better modelling possibilities, since it is unusual for the covariance to be known a priori and the same for different clusters. It would be of interest to characterise the boundaries of the MAP partition in this case. Since cluster covariance structures are no longer fixed, we might expect quadratic boundaries, analogously to the Fisher's Quadratic Discriminant Analysis (Friedman et al. [2001]). This is indeed what happens and it is the goal of the article to prove this.
2 The Setup 2.1 Bayesian Mixture Models and the MAP partition Let Θ ⊂ R p be the parameter space and {g θ : θ ∈ Θ} be a family of probability densities on the observation space R d . Consider a prior distribution on Θ given by its density π. Let P be a probability distribution on the m-dimensional simplex ∆ This is a Bayesian Mixture Model. It can model possible clusters within data; they are defined by deciding which g θ i generated a given data point. In order to formally define the clusters, we need to rewrite (2.1) as (2.2) Then the clusters are the classes of abstraction of the equivalence relation i ∼ j ≡ φi = φj. In this way the distribution on m dimensional simplex generates a probability distribution on the partitions of set [n] into at most m subsets. According to Pitman [2002] this leads to an exchangeable partition, i.e. a random partition whose probability function is invariant with respect to permutations of indices.
In order to indicate that Π is an exchangeable random partition of [n] we use a generic notation Π ∼ ERPn. Moreover we use the notation pn(I) := P(Π = I).
(2.4) Let ERPn be the exchangeable probability distribution on the space of partitions generated by P. We see that (2.1) is equivalent to I ∼ ERPn xI := (xi)i∈I | I ∼ f |I| independently for all I ∈ I. (2.5) We stress the fact that the independent sampling on the 'lower' level of (2.5) relates to the independence between clusters (conditioned on the random partition); within one cluster the observations are (marginally) dependent. To make the notation more concise we define (2.6) Then (2.5) becomes I ∼ ERPn x | I ∼ f (· | I). (2.7) Example 2.2. Consider the Dirichlet Process Mixture Model (Antoniak [1974]). Let α > 0, G0 be a probability measure on Θ with density π and DP (α, G0) be the Dirichlet Process on Θ (Ferguson [1973]). The Dirichlet Process Mixture Model is defined by By Sethuraman [1994] by setting P to be the distribution of p = (p1, p2, . . .) we get that (2.8) is equivalent to (2.1). The exchangeable random partition that P generates is the Generalized Polya Urn Scheme (Blackwell et al. [1973]) or the Chinese Restaurant Process (Aldous [1985]) with the probability weight given by where α (n) = α(α + 1) . . . (α + n − 1). Again, setting ERPn to be the Chinese Restaurant Process with parameter α we get the equivalence between (2.8) and (2.7). pn(I)f (xI | I) ≤ pn(Î)f (xI |Î). (2.10) Notation. Here and below, argmax a∈A φ(a) is the set of maximisers of function φ on the set A (note that the maximiser may not be unique). Hence the MAP partition of x in a Bayesian Mixture Model (2.7) can be defined bŷ

Specification of the Normal Bayesian Mixture Models
In the paper we consider Normal Bayesian Mixture Models in which the component distributions are multivariate Normal. This means that the parameter space Θ is the product of R d (component mean µ) and the space of symmetric, positive definite, d × d matrices S + (component covariance matrix Λ). We investigate the following three conjugate choices of prior distribution on Θ: Normal-inverse-Wishart, Normal (fixed covariance) and Normalinverse-Gamma. In each prior we compute the expected within-group covariance matrix (which is E Λ) and the between group covariance matrix (i.e. V(µ)). Moreover we present the marginal density of a random vector u = (u1, . . . , u k ) | (µ, Λ) iid ∼ N (µ, Λ).
Notation. We use two standard notations to denote the determinant of a square matrix Λ: det Λ and |Λ|. The latter may seem ambiguous as we also use the symbol | · | to denote the cardinality of a set. However, the meaning of this symbol is always clear from the context.

Normal-inverse-Wishart
Here the hyperparameters are κ0, η0 > 0, µ0 ∈ R d and Σ0 ∈ S + . This prior is listed in Gelman et al. [2013] with a slightly different hyperparameters, but we made this modification to obtain which is consistent with the remaining two priors.
(2.18) Proposition 2.5. Let θ = (µ, Λ) have the distribution given by (2.17) and let u = (u1, . . . , u k ) | θ iid ∼ N (µ, Λ). Then the marginal distribution of u is given by where Γ d is the multivariate Gamma function and Proof. Note that it is enough to prove (2.5) only for µ0 = 0; in general it follows by translation. The case µ0 = 0 is contained in Rajkowski [2018] as a part of the proof of Remark 2.1.

Comparison of the models
If we assume that the component parameters in the Normal Bayesian Mixture Model are distributed by (2.17) then we assume that the covariance matrix in each component is equal to Σ0 which is known to us. The results of Rajkowski [2018] imply that the misspecification of this hyperparameter may lead to serious inference issues regarding the number of clusters, at least as far as the MAP partition is concerned. In the light of these findings, (2.12) seems to be a safer choice of the prior for the component parameters. In this case the covariance matrix is chosen independently for each component according to the inverse-Wishart distribution. Note that although the Normal-inverse-Wishart prior gives more flexibility in terms of the component covariances, it imposes some modelling restriction, namely the expected within and between group covariance matrices are proportional, as is shown by (2.13). This does not affect the fixed-covariance model, cf. (2.18).
This is the reason for which we propose the Normal-inverse-Gamma prior. It is not listed in Gelman et al.
[2013] and we were not able to find any reference to it in the literature. It only allows a 1-parameter variation of the covariance function, but no restrictions are imposed on the within-group means, unlike the Normal-inverse-Wishart prior. At the same time, by allowing the component covariance matrix to scale between clusters can be a remedy to the drawbacks of fixed covariance prior that were pointed out in Rajkowski [2018].
As a final point we note that Normal-inverse-Gamma prior is a generalisation of the Normal prior in the sense that (2.22) becomes (2.17) as β0 → ∞. Analogously, Normal-inverse-Wishart prior is a quasi-extension of the Normal prior, since as η0 → ∞, (2.12) converges to (2.17), but with Ψ0 = Σ0/κ0.

Formal statement of the result
We now define what we mean by linear, quadratic and elliptic separation of clusters.
Definition 3.1. Let X be a family of subsets of R d and L a family of real functions on R d . We say that X is separated by • if L is the union of convex and concave quadratic functions, i.e.
(a) This family is linearly separable.
(b) This family is elliptically, but not linearly separable.
(c) This family is not quadratically separable. Notation. For the notational convenience we will use the separability notions also with respect to the sets of sequences in R d . For example, if x1, . . . , xn ∈ R d and I, J are disjoint subsets of [n] then the expression xI is linearly separated from xJ means that {xi : i ∈ I}, {xj : j ∈ J} is linearly separated.
In Rajkowski [2018] it is proved that in the Normal Bayesian Mixture Model with Normal distribution on the component mean and fixed covariance matrix, when the prior on the space of partitions is the Chinese Restaurant Process, the convex hulls of the clusters in the MAP partition are disjoint. Equivalently, the MAP is linearly separable. The same is true for an arbitrary exchangeable random partition prior. Proof. The proof for the general exchangeable random partition prior is analogous to the proof in the case of the Chinese Restaurant Process, which is contained in Rajkowski [2018]. We give it in Section 5 for completeness.
The main result of this paper is an analogue of the Theorem 3.2 for Normal Bayesian Mixture Model with Normal-inverse-Wishart prior on the component parameters. Proof. The proof is left for Section 5.
By applying the same techniques as in the proof of Theorem 3.3 we can show that the MAP partition in the Normal Bayesian Mixture Model with Normal-inverse-Gamma prior on the component parameters is elliptically separable.
Theorem 3.4. Let x1, . . . , xn ∈ R d be pairwise distinct and letÎ be the MAP partition of x1, . . . , xn in the Normal Bayesian Mixture Model where the prior on component parameters is given by (2.22). Then the family {xI : I ∈Î} is elliptically separable.
Proof. The proof is left for Section 5.

Discussion of potential applications
We proved linear or quadratic separability of the MAP partition in most popular Normal Bayesian Mixture Models. Apart from an aesthetic analogy to the properties of Fisher Discriminant Analysis, the benefits of such result may be twofold.
In Rajkowski [2018] the linear separability of the MAP partition is crucial for establishing the existence of 'limits' of the MAP partitions when the prior on partitions is the Chinese Restaurant Process and the data is independently and identically distributed with some 'input distribution'. The limit is related to the partitions of observation space which maximises a given functional ∆ (which depends only on the hypeerparameter Σ0 and the input distribution). The linear separability is important for two reasons: firstly, it is possible to consider the limits of sequences of convex sets and secondly: it is possible to apply the Uniform Law of Large Numbers for the family of convex sets. Theorem 3.3 should enable an analogous approach for the Normal-inverse-Wishart and Normal-inverse-Gamma priors on the component parameters.
The other kind of application is more practical; Theorem 3.3 shows that the search for an MAP partition may be restricted to situations where clusters are quadratically separated.
The space of such partitions is still far too large for an exhaustive search, but may help in finding a partition whose score approximates the MAP score.

Proof of Proposition 2.6
Consider the model of Proposition 2.6 1) where α0 is defined by (2.25). The conditional density of λ, µ given u is (5.2) Recall the definition of Ψ k (2.20). This is the update of the cluster covariance. Let This is the update of the cluster centre given the data. To get the part inside the exponential in a useful format: Recall the definition of Ξ k (2.27). Note that Let us write where β(·) is given by (2.26). Note that by (5.7) we have β k ≥ β0 > 0 and hence by (5.5): We can now compute the marginal density of u. It is the density of (Λ, µ, u) divided by the conditional density of (Λ, µ | u). We have By definition of Ψ k , µ k , β k in the quotient of (5.9) and (5.10) the exponent function cancels out, leaving By (5.7) β k = β(u) and the proof follows.

Two important Lemmas
Lemma 5.1. Let L be a family of real functions on R d . Let x1, . . . , xn ∈ R d and letÎ be the MAP partition for x1, . . . , xn in some Bayesian Mixture Model, given by (2.5). If for any U ⊂ [n], k, l ∈ N such that k + l = |U| andÎ k,U such that observations xÎ k,U and x U \Î k,U are separated by L then {xI : I ∈Î} is separated by L.
Proof. Firstly note that by (2.11)

I ∈ argmax
partitions I of [n] ln pn(I) + and hence ln f k (xĨ ) + ln f l (xJ ) > ln f k (xÎ ) + ln f l (xĴ Proof. Consider the set of all possible sums of k distinct vectors zi, i.e. S k = { i∈I zi : I ⊂ [n], |I| = k} and letŝ k ∈ argmin s∈S k h(s). Since h is strictly concave, thenŝ k is a vertex of conv S k . This means that there exist a vector v0 ∈ R d such thatŝ k ∈ argmax s∈S k s, v0 (cf. Moszynska [2006], Corollary 3.3.6), where ·, · is a standard Euclidean scalar product. I can also choose v0 so that zi, v0 are are all different (because we are dealing with a discrete set). Let z (

Proof of Theorem 3.2
The proof of Theorem 3.2 when the prior distribution on the space of partitions is the Chinese Restaurant Process is contained in Rajkowski [2018]; the proof for general exchangeable random partitions does not differ from it. On the other hand, it is a direct consequence of Lemma 5.1 and Lemma 5.2, so we present it here for the completeness.
Let U ⊆ [n], k, l ∈ N andÎ k,U be as in Lemma 5.1. Let S = U xi. Plugging the formula for f N k (2.19) into (5.12) gives: Clearly, w is a strictly convex quadratic function and hence by Lemma 5.2 xÎ k,U and x U \Î k,U are linearly separable. By Lemma 5.1 this concludes the proof.

Löwner partial order, matrix convexity and concavity
Let S + be the set of positive definite matrices. Note that det A > 0 for all A ∈ S + and hence log det is a well defined function on S + .
where X ⊥ is the space perpendicular to X. We prove by induction that Vi = Wi for i ≤ r.
The case i = 0 is clear. Assume that it is true for j ≤ (i − 1). Take any 0 = w ∈ Wi. Using (5.21), the inequality A B and the assumption Vj = Wj for j ≤ (i − 1) and hence w t Aw w t w =λi and w ∈ Vi. This proofs that Wi ⊂ Vi and since dim Wi = dim Vi we get Wi = Vi for i = 1, 2, . . . , r. This means that A = B, which is a contradiction.
Corollary 5.7. The function f (A) = ln det A is strictly increasing on S + with respect to the Löwner partial order.
Proof. The proof follows from Lemma 5.6.
Lemma 5.9. Let φ : R d → R d×d be given by φ(u) = uu t . Then φ is strictly matrix-convex.
(5.31) Let V2 = σ −1 2 (S + ). In the same way as before we can prove that V2 is a convex set, I x i ∈ V2 for all I ⊆ U and ln det σ2(z) is strictly concave on V2. Hence we have that where ν k ln det σ1(·) + ν l ln det σ2(·) is a strictly concave function on V = V1 ∩ V2. Therefore by Lemma 5.2 we obtain that xÎ k,U and x U \Î k,U are linearly separable (i.e. in terms of the base functions). Obviously this yields quadratic separability of xÎ k,U and x U \Î k,U and the proof follows.

Proof of Theorem 3.4
This proof has strong similarities to the proof of Theorem 3.3, but the additional structure leads to sharper results, which require different details. We therefore present the proof in full.
(5.38) Now we show that b1(z) is a strictly concave function. It is a quadratic function and to prove its strict concavity it is enough to show that (I d −Ξ k ) is positive definite, i.e. I d Ξ k (cf. Definition 5.4). This is equivalent toΞ k −1 I d (cf. Horn et al. [1990], Corollary 7.7.4), which in turn is equivalent to Ξ k −1 Σ0. The latest is obvious as Ξ k −1 = Σ0 + kΨ0.