{'fraction_non_alphanumeric': 0.033480835556712434, 'fraction_numerical': 0.009110431444003383, 'mean_word_length': 4.599380579340499, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Geometric Disentanglement by Random Convex Polytopes

Finding and analyzing meaningful representations of data is the purpose of machine learning. The idea of representation learning is to extract representations from the data itself, e.g., by utilizing deep neural networks. In this work, we examine representation learning from a geometric perspective. Especially, we focus on the convexity of classes and clusters as a natural and desirable representation property, for which robust and scalable measures are still lacking. To address this, we propose a new approach called Random Polytope Descriptor that allows a convex description of data points based on the construction of random convex polytopes. This ties in with current methods for statistical disentanglement. We demonstrate the use of our technique on well-known deep learning methods for representation learning. Specifically we find that popular regularization variants such as the Variational Autoencoder can destroy crucial information that is relevant for tasks such as out-of-distribution detection.


Introduction
Finding a meaningful data representation f (x) = z that captures the information that is relevant for some task or problem lies at the very core of any data-driven discipline such as statistics or machine learning. In contrast to handcrafted data features, representation learning [5] aims to learn such representations from the data itself. The concept of representation learning is also one of the fundamental principles of deep learning [33,47], which set a new state of the art in recent years in numerous domains such as computer vision, speech recognition, or natural language processing. Here, representation functions f θ are given by multi-layered neural networks that are parameterized by weights θ which are jointly optimized on some learning objective.
What makes a representation meaningful and which general principles are useful for representation learning is being actively discussed [5,15,53,35,54]. One prominent line of research considers the statistical nature of disentanglement [46,4,5,11,30,35,36], which is rooted in the idea that a learned representation should "separate the distinct, informative factors of variations in the data" [35]. While this is a valuable notion, other important properties of representation learning such as smoothness, the hierarchy of concepts, temporal and spatial coherence, or the preservation of natural clusters are also desired [5] and have been less studied. In this work, we focus on the convexity of classes and clusters in the image of deep neural network mappings and take a geometric perspective on representation learning.
Convexity is a very natural and fundamental representation property in machine learning in general. The separation of classes via multiple hyperplanes or half-spaces in supervised classification for instance, such as in Support Vector Machines (SVMs) [48] in the Reproducing Kernel Hilbert Space (RKHS) via the hinge loss or in deep neural networks (DNNs) [19] in the output space via the cross-entropy loss, forms polyhedra that are convex and generally unbounded. Moreover, many well-known unsupervised learning methods make explicit convexity assumptions on the support of the data representation, such as Voronoi cells in k-means clustering or ellipsoids in Gaussian Mixture Models (GMMs). Yet it is worth noting that convexity is also implicit in Gaussian prior assumptions in popular deep generative models such as Variational Autoencoders (VAEs) [27,42,53], Generative Adversarial Networks (GANs) [18,13,14], or Normalizing Flows [41,28,26]. Finally, one-class classification methods for support estimation such as the One-Class SVM [49] or (Deep) Support Vector Data Description (SVDD) [52,44] also rely on convexity assumptions on the data representation via maximum-margin hyperplane and minimum enclosing hypersphere descriptions, respectively.
Although a convex representation of classes and clusters is such a natural and commonly desired property, measuring convexity in a robust and efficient way in high-dimensional spaces is a challenging and fairly non-trivial problem. An approach that would aim to exactly solve the convex hull problem of a set of data points {x 1 , . . . , x n } in an idealized setting is prohibitively expensive to compute in high dimensions. Moreover, such an exact convex hull description would not be robust towards outliers and thus rather undesirable in terms of generalization.
In this work, we propose a scalable and robust method called Random Polytope Descriptor (RPD) for evaluating convexity in representation learning. Our method is based on concepts from convex geometry and constructs a polytope (a piecewise-linear, bounded convex body) around the training data in representation space. Since polytopes by themselves may also suffer from a combinatorial explosion, we construct our descriptor from random convex polytopes instead which also makes it more robust. Finally, using the proximities to such polytopes allows us to judge the geometric disentanglement of representations, i.e. how well classes and clusters are separated into convex bodies. Our main contributions are the following: • We propose the Random Polytope Descriptor (RPD) method which is based on the construction of random convex polytopes for evaluating convexity in representation learning and theoretically prove its scalability.
• We demonstrate the usefulness of RPD in experiments on well-known supervised as well as unsupervised deep learning methods for representation learning.
• We find that popular regularization variants of deep autoencoders such as the Variational Autoencoder can destroy crucial geometric information that is relevant for out-ofdistribution detection.

Related Work
How to evaluate the quality and usefulness of a representation is a difficult question to answer in general and subject of ongoing research [5,15,53,35,54]. If only one single task is of interest, a straightforward approach of course would be to evaluate the performance of a representation on some measure that is meaningful to the task at hand. Considering the supervised classification task for instance, one might evaluate the quality of a model and representation by using the accuracy measure, i.e. by how well the representation separates some test data via hyperplanes in agreement with the respective ground-truth labels. However, even in such a well-defined standard task as classification, other representation properties such as the robustness against out-of-distribution samples [38,20,31,34,44] or adversarial attacks [50,8,6,9], as well as interpretability aspects [32,45] might be desirable and thus relevant representation quality criteria. This matter becomes even more challenging in the unsupervised or self-supervised setting, where the aim is learn more generic data representations that prove useful for a variety of downstream tasks (e.g., multi-task or transfer learning) [55, 43,51]. Bengio et al. [5] have collected and formulated some well-known generic criteria, so-called generic priors for representation learning. These include smoothness (if x ≈x, then also f (x) ≈ f (x)), the hierarchy of concepts (e.g., for images going from pixel to object features), semi-supervised learning (representations for supervised and unsupervised tasks should align), temporal and spatial coherence (small variations across time and space should result in similar representations), the preservation of natural clusters (data generated from the same categorical variable should have similar representations), and statistical disentanglement (a representation should separate the distinct, informative factors of variations of the data). Different variants of the Variational Autoencoder (VAE) [27,42,21,30,25,10] which especially emphasize statistical disentanglement are currently considered to be the state of the art for unsupervised representation learning [53,35]. These approaches are closely related to earlier works on (non-linear) independent component analysis (ICA) which study the problem of recovering statistically independent (latent) components of a signal [12,3,22,2,24].
As mentioned above, the convexity of classes and natural clusters is another fundamental representation property that is often only expressed implicitly through certain model assumptions. The basic property that linear interpolations between data representations should result in representations from the same class or cluster naturally ties into the generic priors above. This also follows the simplicity principle from Bengio et al. [5] that "in good representations, the factors are related through simple, typically linear dependencies."

Methods
The applicability of our method depends on the general clustering assumption, that the training data is composed of different unobserved groups (classes), and that the joint density of observed variables is a mixture of class-specific densities. This assumption might be exemplified by assuming that the data come from a mixture of multivariate multinomial distributions, which is the natural assumption in data analysis. Moreover we assume, that the super-level sets of the density function for each of the summands in the mixture form a convex set, except maybe for regions of very low probability.
The method is designed to work well on embeddings into feature space, where each of the classes are embedded into mutually disjoint convex sets. Such assumption is at the foundation of classical methods e.g. SVMs and kernel methods. However these methods do not take into account the finiteness of training data simply partitioning the whole feature space among classes, i.e. usually most classes are given infinite regions. While such feature might seem desired, as it affords generalization properties for models, it also increases the surface for adversarial and out-of-distribution attacks. Here we attempt to remedy this limitation by explicitly partitioning the feature space into compact convex regions and an unbounded (non-convex) "out-of-distribution" set.
The general idea is to use the convex hull conv(X) of points from the given class and the distance to conv(X) as dissimilarity score. As mentioned earlier, both the convex hull computation and distance from a polytope are prohibitively expensive in higher dimensions, therefore we will replace both of these steps by their approximations. In this section we introduce the definition of (approximate) dual bounding body of X and show how such polytope can be turned into a descriptor separating the points in the set from the exterior. Instead of computing actual distance, we will use the substitute of scaling distance (a piecewise-linear scaling of euclidean distance) from a well defined central point of the polytope.

An idealized setting
We consider N distinct sets X 1 , X 2 , . . . , X N ⊂ R d , where X i is the set of samples of class i, considered in feature space R d . Associated with these classes are N convex sets P 1 , P 2 , . . . , P N , where If all pairwise intersections P i ∩ P j are disjoint, for i = j, then these convex sets provide perfect descriptors, provided that we have some oracle which can test whether a new sample z ∈ R d is contained in either of the sets P 1 , P 2 , . . . , P N or their complement.
In the applications below each class X i will be finite, whence the sets P i form convex polytopes; cf.
[56] for general background. We will return to the more general setting later; but for now we will stick to finite sets and polytopes. In this case an oracle for checking z ∈ P i is given by linear programming. While linear programs can be solved in (weakly) polynomial time, they are still somewhat expensive in high dimensions. If many samples need to be checked it is thus desirable to convert each set X i into a description in terms of linear inequalities. A minimal encoding of this kind is given by the facets of the polytope P i . Then the containment z ∈ P i can be decided in O(m i d) time, where m i is the number of facets of P i . We assume that each set X i affinely spans R d , whence P i is full-dimensional, and thus its facet description is unique.
Converting X i into the facets of P i = conv(X i ) is the convex hull problem. It is worth noting that the dual problem of computing the vertices of a polytope given in terms of finitely many linear inequalities (assuming that it is bounded) is equivalent to the convex hull problem by means of cone polarity. If we let n i be the cardinality of X i , then McMullen's upper bound theorem [37] says that That bound is actually tight as can be seen, e.g., from the cyclic polytopes. In view of cone polarity the same (tight) estimate holds for the number of vertices if the number of inequalities is given. This means that the number of vertices and the number of facets of a polytope may differ by several orders of magnitude. This sketch of a classification algorithm is too naive to be useful in practice. Yet it is instructive to keep this in mind as a guiding principle. We identify three issues.
1. The idealized setup does not deal with outliers, i.e. is generally not robust.
2. Computing the convex hull of each class can be prohibitively expensive.
3. The N classes may not be well represented by their convex hulls.
Our main algorithmic contribution is a concept for addressing all three issues simultaneously. For empirical data on convex hull computations see [1].

Random polytope descriptors
As our main contribution we propose a certain convex polytope as an approximate decription of some learned representation. Its algorithmic efficiency and its robustness to the presence of outliers can be tuned by a pair of parameters. Again we assume that X ⊂ R d is finite, and n = |X|. Definition 1. Let Y ⊂ S d−1 be a set of m unit vectors chosen uniformly at random, and let be a positive integer. The random polytope descriptor is the polyhedron where -max denotes the -th largest element of the set.
Tacitly we will assume that RPD m, (X) is bounded. This is the case if and only if Y is positively spanning. It is worth noting that the random polytope descriptors form a variation of dual bounding bodies; cf. Section A.
We briefly sketch what it means to compute RPD m, (X), and which cost this incurs. First we need m random unit vectors, which can be found in O(m); cf. [29, 3.4 There is no reason to be overly exact here; so it is adequate to assume that the coefficients of the random vectors are constantly bounded. Given X, we then evaluate mn scalar products to obtain the H-description (2) of RPD m, (X), resulting in a total complexity of O(mn). Throughout we take the number d of latent dimensions as a constant.
In the context of unsupervised anomaly detection (see Section 4) it is often beneficial to discard a fixed amount of data from X, i.e., label them as anomalous. The -max function serves as a "threshold" to eliminate the most extreme points from the training set. For (semi-)supervised learning there may be natural candidate functions to replace -max to define variants of RPD, e.g., based on density estimation, weights, or simply the label. However, for simplicity we stick to unsupervised anomaly detection. Figure 1: Convex hull conv(X) (red) and random polytope descriptor RPD 80,3 (X) (green). Here d = 3, and X ∼ N (0, 1) is a random Gaussian sample of 150 points with mean 0 and variance 1. In spite of 3% outliers, the descriptor closely approximates the convex hull of the normal class (i.e., the inner cluster).

Scaling distance and anomaly scores
Let P ⊂ R d be a full-dimensional convex polytope with a distinguished interior point c. The scaling distance of z ∈ R d to P with respect to c is the quantity This is the smallest number α ≥ 0 such that P inflated by a factor of α from the central point c contains x. The point z is contained in P if and only if sd c (z, P ) ≤ 1. If P is a descriptor, e.g., as in Definition 1, this may serve as a dissimilarity (anomaly) score, where the points further from P are assigned higher scores. Given z, c and an H-description of P in terms of m linear inequalities, we can compute sd c (z, P ) in O(m) time, for d constant, by evaluating scalar products. There are several natural candidates for the central point of an arbitrary polytope P , which differ with respect to computational complexity, when P is given in terms of inequalities. For instance, the centroid is the center of gravity of P ; this is hard even to approximate, cf. [39]. The vertex barycenter is the average of the vertices of P ; this is hard to compute exactly, cf. [17]; further results in loc. cit. make it unlikely that there is an efficient approximation procedure either. The Chebyshev central point is the center of the largest sphere inscribed to P ; this can be computed in O( √ m) time by linear programming, cf. [16] and [40]. Note that the latter worst case complexity assumes that the bit representation of each inequality in the H-description of P is constantly bounded. For the special case of P = RPD m, (X), where X is a normally distributed random sample, all the three central points discussed are arbitrarily close to the origin, provided that m is sufficiently large; cf. Fig. 1.
Let X = i X i be the training data partitioned into classes. For the estimated distance of a point z ∈ R d to the combined support of all classes we take the minimum of the scaling distances, where P i = RPD m, (X i ), and c i is the corresponding Chebyshev central point. Note that δ(z) is a random variable as the construction of polytopes P i is not deterministic. If the estimated distance to the combined support is larger than one, then evaluating (4) also assigns a class which is closest to z, namely the index i at which the minimum is attained. For generic z this is unique. It follows from our complexity analysis above that estimating the distance to the combined support takes O(m) time, for d and N fixed.

Convex separation
Since we do not use any a priori knowledge on the latent representation that we work with, it may happen that the random polytope desciptors of two (or more) classes intersect nontrivially. Again let X = i X i be partitioned into classes and P i = RPD m, (X i ) are the random polytope descriptors, for some fixed values of m and . Then we can define the confusion coefficient of classes i and j as i.e., a low value indicates good separation. This may be seen as a Monte Carlo style approximation of the integral of the probability density function of the test data over the intersection P i ∩ P j . Again by evaluating scalar products, computing one confusion coefficient is in O(mn).

Experiments
We conduct experiments on the MNIST and FMNIST datasets, to assess the feasibility of our method. Both datasets, MNIST and FMNIST, comprise ten classes each, i.e., N = 10. It should be stressed that we are primarily interested in the overall reliability of the classification process rather than individual performance scores. We train standard AE and VAE networks to embed the MNIST and FMNIST datasets into a d-dimensional latent space for various choices of d. The autoencoder architectures are of LeNet-type, having an encoder that has two 5×5 convolutional layers with max-pooling followed by two fully connected layers that map to an encoding of d dimensions. The decoder is constructed symmetrically where we replace convolution and max-pooling with deconvolution and upsampling respectively. We use batch normalization [23] and leaky ReLU activation functions these networks. For training, we take the entire training datasets, minimizing the reconstruction error (AE) and the reconstruction error regularized by the volume of the support of latent distribution (VAE). None on the networks are given any explicit convexity prior.
It is worth noting that constructing the H-representation (2) of the random polytope descriptor is very fast. On modern hardware 1 , it takes less than 3 seconds to create an RPD 640,2 (X) from a set X of 6000 points in R 20 . This includes computing its Chebyshev central point already. Evaluating the scaling distance (3) takes less than 0.001s per sample in this scenario.

Out-of-distribution detection
Our method suggests to consider the random polytope descriptors as a model for the supports of the individual class distributions in the training data. Here we check how well this approximation works to detect out-of-distributions samples.
Our experimental setup is as follows. For each of the ten classes of FMNIST training data X we constructed a random polytope RPD m,1 (X i ). Since this is a supervised learning scenario it's natural to chose = 1. In further experiments (see Section 4.2 and specifically Fig. 9) increasing m beyond 20d (where d is the dimension of the latent representation) had little to no influence on the performance, thus we settled on choosing m = max(320, 20d). Then we evaluated the estimated distance to the support (4) for test data from the FMNIST and MNIST datasets. The results are depicted in Fig. 3.
Comparison of AE and VAE networks. The minimal scaling distances for samples from FMNIST stay well below 1 for both networks; recall from (3) that this signals containment in one of the classes. So this behavior is expected and a first hint at a reasonable performance of random polytope descriptors for anomaly detection; cf. Section 4.2 for details.
However, we observe a very clear distinction between the AE and VAE networks with respect to out-of-distribution samples. Using AE network trained on FMNIST dataset, out of distribution MNIST test data are given significantly larger dissimilarity score. In sharp constrast the VAE network embedding of MNIST test set exhibits almost complete overlap with the support of the FMNIST training distribution. This means that the regularization step, which distinguishes VAE from AE, destroys information which may be exploited to 1 Timings given for i5-6200U laptop processor perform out-of-distribution attacks. We will come back to this when we will look at anomaly scores in Section 4.2.
It is worth noting that the FMNIST scores are not concentrated around 0 (as one would observe, e.g., in the case of a Gaussian distribution). Instead they seem to be distributed near a sphere of some radius increasing with the dimension. For instance, for the VAE networks mean and variance range from (0.68, 0.03) to (0.85, 0.006)).
Convex separation in classical networks. We picked ten different classes from the CIFAR-100 dataset, which to intuivie human understanding should be relatively close to each other. We evaluated convex separation of pre-trained, state-of-the-art image recognition networks: AlexNet, ImageNet and Resnet18 to form "confusion matrix" present below. Note that high confusion means that no linear separating hyperplane will provide good distinction between the classes.

Anomaly detection
As a second benchmark for the disentanglement of the learned representation we used an anomaly detection test. For each MNIST and FMNIST class an unsupervised anomaly detection scenario was created as follows. The training data X i consisted of all training data points from class i "enriched" by p|X i | data points chosen uniformly at random from the other classes, for some constant 0 < p < 1. This noisy data is then used to create a random polytope descriptor P i = RPD m,l (X i ), and its accuracy against the entire test data is evaluated in the AUC metric (area under receiver operating characteristic curve). This experiment may be understood as a stochastic approximation of the intersection P i ∩ j =i P j . Indeed, if two random polytope descriptors exhibit an intersection witnessed in the test data, the data points in the intersection will be counted as false negatives in the anomaly detection task.
All Comparison of AE and VAE networks. When fixing m, the number of hyperplanes, in Figs. 6 and 7 we can see the monotonous increase of scores with the dimension of the latent space. This aligns with the common understanding that higher the dimension, the better is reconstruction, hence more faithful representation of data.
When fixing d, the dimension, we can observe the dependence of the AUC score on the number of hyperplanes m defining an RPD m . The scores increase monotonously with m both for MNIST Fig. 8 and FMNIST Fig. 9 datasets. This agrees with our intuition, as with a larger number of hyperplanes the approximate bounding body tightens its approximation of the true convex hull. It seems that setting the number of hyperplanes m above 20d does not lead to significant improvement in performance.
For the MNIST dataset it seems that combining our descriptors with VAE is able separate the clusters in dimension d = 9 with improvement up to d = 12. Provided that the assumption on the convexity of clusters is satisfied, the deterioration of the performance for larger ds (for a fixed m) is expected, as in higher dimensions a larger number of hyperplanes is needed for similar quality of approximation. On the other hand, AE in general performs much poorer in this scenario but its performance does not deteriorate. The difference in behavior of AE and VAE networks suggest that the deterioration of performance for higher dimensions may be the consequence of overfitting by VAE networks.
A similar experiment on FMNIST, arguably more complex dataset, shows (Fig. 7) no deterioration of performance while increasing the dimension, and overall better performance of VAE networks.
A possible explanation of the phenomenon we observe with VAE networks is as follows. Since VAE networks try to pack data close to the origin, all classes necessarily will be in close proximity to each other. It is possible though that while achieving simple (convex) shapes of clusters in low dimensions, more space in higher results in complex shapes of embedded clusters, which might be an indicator of overfitting.
The sustained performance of VAE networks for FMNIST dataset might be an indicator that the intrinsic dimension of the dataset is higher than what have been studied here. On the practical side of network design, one may argue that the regularization in VAE network is too strong for MNIST dataset.

Contracting property of autoencoders
Autoencoder networks can be seen as pair of networks φ : optimized to be close to the identity (on the support of the training distribution). One may ask for the image of the reversed composition which follows the path of adversarial learning.
In particular we are interested in measuring how far from the identity is the composition Φ = φ • ψ, and whether the image of the map is closer to the support of the training data.
In the second case we may say that the network has contracting properties. Since the RPD's provide a natural "calibration" of the distance, we can sample vertices of an RPD at random (which are all of scaling distance 1) and observe the distribution of scaling distance of the image of Φ of those vertices.
Here we compare the behavior of RPDs with a classical k-means descriptor (based on Voronoi centers); see Fig. 2. We start with a sample of vertices V of a RPD for a fixed class (and hence of scaling distance to that class equal to 1) and apply map Φ to them. For comparison we also produce the histograms for (scaled) Euclidean distances to Voronoi center of a class. Such experiments are depicted in Fig. 5. Notice that while both networks exhibit strongly contractive behavior, the VAE network it is especially pronounced. The simplest explanation is networks nearly constant response on the entire Voronoi cell.

A Dual Bounding Bodies
A first key idea is to replace convex hulls by suitable dual bounding bodies, which form outer approximations. To explain the concept it suffices to consider a single class. Let X be a set of points in R d , and let Y ⊂ S d−1 be a finite set of directions.
Definition 2. The dual bounding body of X with respect to Y is the polyhedron By construction D Y (X) is convex, and it contains X; so it contains P := conv(X), too. If X is finite then the supremum in (6) is a maximum, µ y , that is attained for some x ∈ X, which only depends on y. In that case D Y (X) = P if and only if Y contains all facet normals of P .
In the sequel we will assume that both, X and Y , are finite, and Y is positively spanning, i.e., conv(Y ) contains the origin in its interior. As X is finite the latter property is satisfied if and only if the polyhedron D Y (X) is bounded, i.e., a polytope. Remark 1. If X is finite, positively spanning and contained in S d−1 , then D X (X) is the polar dual of the polytope P = conv(X). The facets of D X (X) are tangent to S d−1 , and µ x = 1 for all x ∈ X.

B Random Polytopes
The following observation will turn out to be practically relevant. It says that our random polytope descriptors are combinatorially benign, in contrast to the worst case scenario described by the upper bound theorem (1). Theorem 3. Let X ∼ N (0, 1) be normally distributed with mean zero (and constant variance). For arbitrary m and the number of vertices of RPD m, (X) is in the order of Θ(m), for d considered constant. Proof. The normal distribution is rotationally invariant, and so is the uniform choice of directions Y ⊂ S d−1 . Consequently, the construction of RPD m, (X) follows the Rotation-Symmetry Model of Borgwardt [7], and this yields the claim.
We use the stochastic approach of [7] of random polytope. There, a random model of polytopes is defined as follows: we say that where X is chosen uniformly over S d−1 ⊂ R d . Figure 3: Results of the out-of-distribution detection experiment. AE and VAE networks were trained on FMNIST data and used to embed MNIST test sets. The plot depicts the distribution of minimal scaling distance to one of the ten FMNIST random polytope descriptors in various dimensions up to 20 for fixed (m, ) = (320, 1). Five distinct AE and VAE networks were trained and independently five random polytopes were drawn for each of the dimensions. The lower plot shows a similar experiment with a simple descriptor based kmeans, which can be understand as Voronoi counterpart to polytopal descriptors. The vertical axis is the dimension normalized Euclidean distance defined as d(x, y) = 1 n i (x i − y i ) 2 for points x, y ∈ R n .          VAE in dimension 20 Figure 9: Results of the anomaly detection experiment on embedded FMNIST dataset. Each curve represents performance of RPDs for one class (mean and joint variance for 3 separately trained networks and 5 RPD constructions). On vertical axis is the AUC score; on horizontal axis the number of hyperplanes used to define RPD.