On convex decision regions in deep network representations

Venue: ICLR_cc_2024_Workshop_Re-Align
Published: 2024-01-29 16:53:28

Abstract: Current work on human-machine alignment aims at understanding machine-learned latent spaces and their correspondence to human representations. G{\"a}rdenfors' conceptual spaces is a prominent framework for understanding human representations. Convexity of object regions in conceptual spaces is argued to promote generalizability, few-shot learning, and interpersonal alignment. Based on these insights, we investigate the notion of convexity of concept regions in machine-learned latent spaces. We develop a set of tools for measuring convexity in sampled data and evaluate emergent convexity in layered representations of state-of-the-art deep networks. We show that convexity is robust to relevant latent space transformations and, hence, meaningful as a quality of machine-learned latent spaces. We find that approximate convexity is pervasive in neural representations in multiple application domains, including models of images, audio, human activity, text, and medical images.
 Generally, we observe that fine-tuning increases the convexity of label regions.
 We find evidence that pretraining convexity of class label regions predicts subsequent fine-tuning performance.

Main paper: 
 introduction: 
 Understanding the barriers to human-machine alignment is as important as ever (see, e.g., Bender et al. (2021) ; Mahowald et al. (2023) ). Representational alignment is a first step towards a greater goal of understanding value alignment (Christian, 2020) . For understanding of alignment, it is fundamental to establish a common language for the regularities observed in human and machine representations. Here, we motivate and introduce the concept of convexity of object regions in machine-learned latent spaces.Representational spaces in the brain are described in several ways, for example, geometric psychological spaces informed by similarity judgements or, based in the neurosciences, representations derived from the measurement of neural activity (Balkenius & Gärdenfors, 2016; Tang et al., 2023) . Conceptual spaces as proposed by Gärdenfors are a mature approach to the former, i.e., humanlearned geometrical representations of semantic similarity (Gärdenfors, 2014) . The geometrical approach is rooted in work Shepard (1987) , which opens with the important observation: "Because any object or situation experienced by an individual is unlikely to recur in exactly the same form and context, psychology's first general law should, I suggest, be a law of generalization". This leads Shepard to favor geometrical representations in which concepts are represented by extended regions rather than single points, to allow for robust generalization. This is the view that has been comprehensively expanded and quantified in Gärdenfors (2014) . The cognitive science insights are complemented by extant work investigating alignment between learned representations in machine and human conceptual spaces (Chung & Abbott, 2021; Goldstein et al., 2022; Valeriani et al., 2023) , and numerous specific properties of the latent geometrical structure have been studied, such as the emergence of semantic separability in machine latent representations (Mamou et al., 2020) . New insights in the representational geometry are found using the intrinsic dimension measure (Valeriani et al., 2023) . The relevant geometries are not necessarily flat Euclidean spaces but are often better described as general manifolds (Hénaff & Simoncelli, 2016; Arvanitidis et al., 2018) . In fact, Hénaff et al. (2019) suggests that semantic separability emerges by flattening or straightening trajectories in latent spaces, such as was earlier proposed for machine representations (Brahma et al., 2015) .Similar reasoning was crucial for early methodological developments like ISOMAP (Tenenbaum et al., 2000) and kernel methods (Mika et al., 1998) .Based on Shephard's idea of objects as extended regions, Gärdenfors formulated the hypothesis that natural concepts form convex regions in human geometrical representations (Gärdenfors, 1990; 2014; Warglien & Gärdenfors, 2013; Douven et al., 2022) . Strößner (2022) elaborated on the notion of natural concepts as a social construct: "[Natural concepts] are often found in the core lexicon of natural languages-meaning that many languages have words that (roughly) correspond to such concepts-and are acquired without much instruction during language acquisition." One way to interpret the naturalness notion is to link it to independent physical mechanisms with macroscopic effects, i.e., effects that will be visible to all, hence, likely to appear in joint vocabularies. Such independent mechanisms play a core role in causal modeling (Parascandolo et al., 2018) . A more lowlevel interplay between human and machine conceptual representations was discussed in Bechberger & Kühnberger (2022) with a specific focus on grounding shape spaces. The work reports good correspondences between human shape representations as obtained by pairwise similarity judgments and machine representations of the shape obtained from supervised and unsupervised learning, however, without touching the question of the convexity of object regions in machines.Convexity is closely related to generalization in cognitive systems (Gärdenfors, 2001; Gärdenfors et al., 2018) . The defining property of convexity (see Definition 1) implies that categorization can be extended by interpolation. We also note that simple generalization based on closeness to prototypes leads to convex decision regions (Voronoi tesselation induces convex regions) (Gärdenfors & Williams, 2001) . Interestingly, convexity is also claimed to support few-shot learning (Gärdenfors, 2001) . When basic concepts are learned as convex regions, new labels can be formed by geometrically guided composition, leading to new convex regions (e.g., by conjunction) or by other inductions leading to sets of convex regions. Finally, it is observed that convexity supports communication and interaction and thus the negotiation of meaning between subjects and the emergence of socially universal concepts, i.e., natural concepts (Warglien & Gärdenfors, 2013) .The geometry-driven cognitive science insights motivate our investigation here: Are generalizable, grounded decision regions implemented as convex regions in machine-learned representations?The convexity of decision regions in machine-learned representations has not been addressed before, and therefore, we first need to develop the required investigative tools. Our contributions include:• the introduction :::::::::Introduction : of convexity as a new dimension in human-machine alignment.• recapitulation :::::::::::Recapitulation : of the salient properties of convex sets in flat and curved spaces.• proves :::::: Proofs ::: that convexity is stable to relevant latent space re-parametrization ::::::::::::transformations. • ::::::: Creating : an efficient workflow to measure Euclidean and graph convexity of decision regions in latent spaces. • we present empirical :::::::: Empirical evidence of pervasive convexity of decision regions in selfsupervised models for images, audio, movement, text, and brain images. • we present :::::::Empirical : evidence that convexity of a class decision region in a pretrained model predicts labelling accuracy of that class following fine-tuning, see Figure 1 .Let us first formalize classical convexity in Euclidean spaces. Definition 1 (Euclidean convexity). Boyd & Vandenberghe, 2004) .A subset S ⊂ R D is convex iff ∀x, y ∈ S ∀t ∈ [0, 1], z(t)= tx + (1 -t)y is also in S (From the definition, it follows that the intersection of two convex sets is also a convex set. Hence, conceptual conjunction ('AND' operation) preserves convexity. Disjunction ('OR' operation), Figure 1 : We measure the Euclidean and graph convexity of each class in the pretrained model and evaluate the recall of each class after fine-tuning. H θ is the pretrained model, H θ * is the fine-tuned model, and σ's are the classification heads trained to predict labels with fixed network representations ('pretrained') and during fine-tuning respectively. Fine-tuning involves all layers of the encoder. We present evidence (the inset and Figure 5 ) that higher convexity of downstream classes in the pretrained model is indicative of higher recall in the fine-tuned model. Hence, the convexity of a class decision region in the pretrained model is associated with subsequent learning of that class after fine-tuning. however, does not, since the union of convex sets is not necessarily convex (it is trivial to construct counter-examples) (Boyd & Vandenberghe, 2004) . Euclidean convexity is conserved under affine transformations, hence convexity is robust to re-parametrization :::::: relevant ::::: latent ::::: space :::::::::::::transformations in deep networks (see a more formal proof in Appendix A). Euclidean convexity is closely related to conjunctions of linear classifiers. In fact, a convex set can alternatively be defined as the intersection of linear half-spaces (possibly infinite), e.g., implemented by a set of linear decision functions resulting in a polyhedron (Boyd & Vandenberghe, 2004) .The relevant geometric structure of deep networks is not necessarily Euclidean, hence, we will also investigate convexity of decision regions in data manifolds. In a Riemannian manifold M with metric tensor g, the length L of a continuously differentiable curve z : [0, 1] → M is defined byL(z) = 1 0 g z(t) ( ż(t), ż(t))dt, where ż(t) := ∂ ∂t z(t).A geodesic is then a curve connecting z(0) = x and z(1) = y, minimizing this length, i.e. geodesic(x, y) = arg min z L(z). While geodesics are unique for Euclidean spaces, they may not be unique in manifolds. We can now generalize to geodesic convexity in manifolds: Definition 2 (Geodesic convexity). A region S ∈ M is geodesic convex, iff ∀x, y ∈ S, there exists at least one geodesic z(t) connecting x and y, that is entirely contained in S.When modeling latent spaces with sampled data, we must further transform the above definitions to data-driven estimators, such efforts are reported, e.g., in Hénaff & Simoncelli (2016); Arvanitidis et al. (2018) . In this work, we choose a simple approach inspired by ISOMAP, hence based on graph convexity in data manifolds: Definition 3 (Graph convexity, see e.g., (Marc & Šubelj, 2018) ). Let (V, E) be a graph and A ⊆ V . We say that A is convex if for all pairs x, y ∈ A, there exists a shortest pathP = (x = v 0 , v 1 , v 2 , . . . , v n-1 , y = v n ) and ∀i ∈ {0, . . . , n} : v i ∈ A.For reasonably sampled data, we can form a graph based on Euclidean nearest neighbors (as manifolds per definition are locally Euclidean). :in :::::::::: ISOMAP).We note two important properties of this estimator, first, the graph-based approximate convexity measure is invariant to isometric transformation and uniform scaling, and second, the samplebased estimator of convexity is consistent. Both aspects are discussed further in Appendix A. The invariance to isometry and uniform scaling means that the approximate convexity property is robust to certain network re-parametrization (Kim et al., 2018) .As we will measure convexity in labelled sub-graphs within larger graphs, Dijkstra's algorithm is preferred over Floyd-Warshall algorithm used in ISOMAP. Dijkstra's algorithm finds the shortest path from a given node to each of the other N nodes in the graph with E edges in O(N log N + E) (Dijkstra, 1959; Fredman & Tarjan, 1987) , while Floyd-Warshall efficiently finds the shortest distance between all vertices in the graph in O(N 3 ) (Cormen et al., 2022; Floyd, 1962) . As we have a sparse graph with E ≪ N 2 , Dijkstra's algorithm will be more efficient. With these approximations, we are in a position to create a graph-based workflow for quantifying convexity in Euclidean and manifold-based structures. Note, for sampled data, we expect a certain level of noise, hence, convexity will be graded.The consistency of sample/graph-based geodesic estimates has been discussed in connection with the introduction of ISOMAP (Bernstein et al., 2000) and more generally in Davis & Sethuraman (2019) . Graph connectivity-based estimates of geodesics from sample data are implemented using two procedures: The neighborhood graph can be determined by a distance cutoff ϵ, so that any points within Euclidean distance ϵ are considered neighbors, or by K-nearest neighbors (KNN) based on Euclidean distance. Consistency of these estimates, i.e., that the sample-based shortest paths converge to geodesics, is most straightforward to prove for the former approach (Bernstein et al., 2000; Davis & Sethuraman, 2019) . The consistency proof for the ϵ-based procedure is based on the smoothness of the metric, a uniformly bounded data distribution (1/c < p(x) < c) and scaling of the distance cutoff or K so the connectivity (number of edges per node) increases for large samples (cutoff decays slowly ϵ → 0 as sample size N → ∞) (Davis & Sethuraman, 2019) .In finite samples, a (too) large connectivity will bias the geodesics, while a (too) small connectivity can lead to disconnected graphs and noisy estimates. In pilot experiments, we tested the ϵ and KNN approaches for a range of ϵ and K and found that the KNN approach produces more stable results. Moreover, the differences for various values of K are negligible, so we are using KNN-based approach with K = 10 in the complete set of experiments. See Appendix C.6 for more details.Should we expect convexity of decision regions of neural network representations? Indeed, there are several mechanisms that could contribute to promoting convexity. First, the ubiquitous softmax is essentially a convexity-inducing device, hence, typical classification heads will induce convexity in their pre-synaptic activation layer. This is most easily seen by noting that softmax decision regions (maximum posterior decisions) are identical to the decision regions of a linear model, and linear models implement convex decision regions (see Appendix A). Secondly, several of our models are based on transformer architectures with attention heads. These heads contain softmax functions and are thus inducing convexity in their weighing of attention. Thirdly, typical individual artificial neurons, e.g., ReLUs, are latent half-space detectors and half-spaces are convex as noted above. Note that deep multi-layer perceptrons can approximate any non-convex decision region, including disconnected decision regions (Bishop et al., 1995) . :::: These ::::::findings ::::::: suggest ::: that :::::::: convexity :: is ::::::: possible :: in :::::: neural :::::::: networks, :::: even :::::: though :: it : is ::: not :::::: forced :: by :::::: design.An extensive body of work concerns the geometry of input space representations in ReLU networks and has led to a detailed understanding of the role of so-called 'linear regions': In networks based on ReLU non-linearity, the network's output is a piece-wise linear function over convex input space polyhedra, formed by the intersection of neuron half-spaces (Montufar et al., 2014; Hanin & Rolnick, 2019; Goujon et al., 2022; Fan et al., 2023) . Interestingly, in typical networks (e.g., at initialization or after training), the linear regions are much less in number and simpler in structure compared to theoretical upper bounds (Hanin & Rolnick, 2019; Goujon et al., 2022; Fan et al., 2023) . During training, the collection of convex linear regions is transformed and combined into decision regions through the later network layers. The resulting decision regions are, therefore, unions of convex sets and may in general be non-convex or non-connected, as noted in Bishop et al. (1995) . Our two measures of convexity, Euclidean and graph-based, probe different mechanisms of generalization, the former is associated with generalization by linear interpolation, while the latter is associated with generalization by interpolation along the data manifolds. As both mechanisms may be relevant for explaining generalization in cognitive systems, we are interested in the abundance and potential role of both measures of convexity. Note that a region may be convex in terms of the Euclidean measure but not the graph-based (e.g. a decision region formed by disconnected but linearly separated subsets) and a region may be graph convex, but not Euclidean convex (e.g. a general shaped connected region in the data manifold). For visual examples see Figure 2 . 
methods: 
 2.1 CONVEXITY MEASUREMENT WORKFLOWSWe are interested in measuring the approximate convexity of a decision region, here, a subset of nodes in a graph. A decision region for a specific class is a set of points that the model classifies as belonging to this class.We first create a graph that contains all the data points of interest. The points are nodes in the graph and the Euclidean distances between the nodes are the weights of the edges. To handle manifoldbased representation, for each node, we create an undirected edge only to the nearest neighbors (K = 10). This procedure creates a sparse undirected weighted graph with positive weights only.We now sample N s pairs of points within the given predicted class label and compute the shortest path in the graph between the pairs using Dijkstra's algorithm (Dijkstra, 1959) . For each path, we compute a score between 0 and 1. The path score is defined as the proportion of the number of nodes on the shortest path, without the endpoints, inside the decision region. If an edge directly connects the pair of nodes, the score is 1. If the points are not connected, the score is 0. We average the scores for all paths and all classes and get one number per layer. Error bars in the results show the standard error of the mean, where we set n to the number of points in the given class. This is likely a conservative estimate since the mean is based on many more pairs than there are points.The runtime complexity of this procedure is O N 2 (D + 1) + N c N s N (log N + K) , where N denotes the number of data points, D is the dimensionality of the representations, and N c is the number of classes. See Appendix A.4 for details.Euclidean convexity is also measured for each layer and class separately. To measure the convexity of class C in layer l, we first extract hidden representations at l of all points predicted to belong to class C. We sample N s pairs of points. For each pair, we compute N p = 10 equidistant points on the segment connecting the representations of the two endpoints. We feed the interpolated points to the rest of the network (after layer l). The score for each pair is then the proportion of the interpolated points that are also predicted to belong to class C. Finally, to get the score of Euclidean convexity for the whole class, we average the scores over all the pairs of points.The runtime complexity of this procedure is O (N c N s N p D), where N c denotes the number of classes, and D is the dimensionality of the representations. See Appendix A.4 for details.To gain more intuition about the two types of convexity and their differences, present examples of various properties of the graph and Euclidean convexity score on synthetic data. Figure 2 shows how different values of the sampled data and nearest neighbors influence the created graph and, therefore, also the graph convexity score.Note that we could consider two types of class labels: data labels (true classes) and model labels determined by the predictions of a model (decision regions). Figure 24 in Appendix C.6 illustrates the difference between these two in the last layer of a model. From Theorem 1 in Appendix A, we have that the last layer is always Euclidean convex for model labels. In previous work (Anonymous, 2023) , we considered data labels. In the present work, we focus on decision regions defined by model labels as they directly probe model representations and decision processes. Model labels are more 'expensive' to compute as propagation of many patterns through deep networks is required for Euclidean convexity.For the pretrained models, we obtain the predicted labels by training a linear layer on top of the last hidden layer (with the rest of the model frozen). This procedure is similar to linear-classifierbased probes that are widely used in natural language processing to understand the presence of concepts in latent spaces (Belinkov et al., 2017; Hewitt & Liang, 2019) . A prominent example of probe-based explanation in image classification is the TCAV scheme proposed by Kim et al. (Kim et al., 2018) , in which auxiliary labelled data sets are used to identify concept directions with linear classifiers (concept class versus random images). In our approach, we use a multi-label "probe" of the last layer to identify the model labels but we use these labels to compute and compare convexity throughout the network.The score depends on the number of classes, and also on the number of predicted data points per class. It follows that the exact numbers are not directly comparable across modalities. A scale for convexity can be set using a null hypothesis that there is no relation. Under this null, we can estimate convexity with randomized class assignments and get a baseline score (see Appendix C.7 for more details).Measurements based on neighbors in high-dimensional data can be sensitive to the so-called hubness problem (Radovanović et al., 2010) . We evaluate the hubness of the latent representations in terms of k-skewness and the Robinhood score. Results are deferred to Appendices C.1-C.5 since only mild hubness issues were detected for most domains. We decided to analyse convexity without adjustment for hubness, to avoid possible biases introduced by normalization schemes (Radovanović et al., 2010) .Image domain. We used ImageNet-1k images and class labels (Russakovsky et al., 2015; Deng et al., 2009) in our experiments. The validation set contains 1000 classes with 50 images per class. The network model is data2vec-base (Baevski et al., 2022) . For details on architecture and training, see Appendix B.1. We extracted the input embedding together with 12 layers of dimension 768 for geometric analysis.Human activity domain. In the human activity domain, we applied our methods to the Capture24 dataset (Willetts et al., 2018) . The dataset consists of tri-axial accelerometer data from 152 participants, recorded using a wrist-worn accelerometer in a free-living setting. In Walmsley et al. (2022) , the dataset was annotated for four classes, namely; sleeping, sedentary behavior, light physical activity behaviors, and moderate-to-vigorous physical activity behaviors, which we use for fine-tuning.We formed the graph by sampling 5000 points (or the maximum number available) from each of the decision regions. We sampled 5000 paths from each label class during convexity analysis.We used a pretrained human activity model from Yuan et al. (2022) to extract the latent representations. The model is pretrained in a self-supervised manner on a large unlabelled dataset from the UK Biobank. The model follows the architecture of ResNet-V2 with 1D convolutions and a total of 21 convolutional layers. The resulting feature vector after the final pretrained layer is of dimension 1024. For additional information on the network and the data see Appendix B.2.Audio domain. In the audio domain, we used the wav2vec2.0 model (Baevski et al., 2020) , pretrained on the Librispeech corpus consisting of 960h of unlabeled data (Panayotov et al., 2015) .The model consists of a CNN-based feature encoder, a transformer-based context network, and a quantization module. We were especially interested in the latent space representation in the initial embedding layer and the 12 transformer layers. After each layer, we extracted the feature vector of dimension 768.We fine-tuned the model to perform digit classification based on the AudioMNIST dataset (Becker et al., 2018) , which consists of 30000 audio recordings of spoken digits (0-9) in English of 60 different speakers (with 50 repetitions per digit). For additional information, see Appendix B.3.Our NLP case study is on the base version of RoBERTa (Liu et al., 2019) which is pretrained to perform Masked Language Modelling (Devlin et al., 2018) in order to reconstruct masked pieces of text. The model consists of an embedding layer followed by 12 transformer encoder layers.Fine-tuning was done on the 20 newsgroups dataset (Lang, 1995) which consists of around 18,000 newsgroups posts, covering 20 different topics, which was split into train, validation and test sets.For further details see Appendix B.4.For the medical imaging domain, we used digital images of normal peripheral blood cells (Acevedo et al., 2020) . The dataset contains 17,092 images of eight normal blood cell types: neutrophils, eosinophils, basophils, lymphocytes, monocytes, immature granulocytes (ig), erythroblasts and platelets. We fully pretrain a base-version of I-JEPA (Assran et al., 2023) , a self-supervised transformer-based architecture with 12 transformer blocks, a patch size of 16, and a feature dimension of 768. We used 80% of the available data for a total of 150 epochs for pretraining. We evaluated the pretrained model by freezing its weights, averaging over the patch dimension of the last layer of the encoder, and applying a linear classification probe. Equivalently, during fine-tuning, we attached a linear classifier and retrained the whole model. We validated our model on 1709 hold-out samples. We achieved a pretrained accuracy of 85.3% and a fine-tuning accuracy of 93.5%. Embeddings were extracted from the first layer and every second transformer block, and averaged along the patch dimension. 
results: 
 To gain intuition on the effect of fine-tuning, we first inspect t-SNE plots for a subset of classes (Figure 3 ) of the image domain. From Theorem 1 in Appendix A, we learn that the last layer of both the pretrained and fine-tuned models is Euclidean convex. The t-SNE plot illustrate this quite clearly for the fine-tuned model while the picture is not quite as evident for the pretrained model. We also see that points with the same predictions get clustered within earlier layers. The situation is similar for other modalities (see Appendices C.1-C.5). The observed structure in these low-dimensional representations adds motivation to our investigation of the convexity of class labels using Euclidean and graph methods in the high-dimensional latent spaces.We measure convexity for classes within the pretrained networks and after fine-tuning with class labels as targets. Figure 4 shows the results for all modalities. The convexity is pervasive both before and after fine-tuning. An important reason why the magnitudes of the convexity scores differ among modalities is the different amounts of data and number of classes. However, the trend is the same for all modalities. Random labelling yields the graph convexity scores approximately 1 C , where C is the number of classes (more details on baseline scores in Appendix C.7). All the convexity scores are significantly higher than these baselines. Generally, class convexity is increased by fine-tuning.Note that the graph convexity in the last layer is (in some cases considerably) lower than 1 ∼ 100%, even though this layer is always Euclidean convex. ). Note that the results are not directly comparable across modalities (see Section 2.1). In particular, we find less convexity in the image data containing a high number of classes (C=1000).For detailed results of the analysis of individual data modalities, see Appendices C.1-C.5.To test the cognitive science-motivated hypothesis that convexity facilitates few-shot learning, we plot the post-finetuning accuracy (recall) per class versus pretraining convexity scores as shown in Figure 5 for graph-based convexity (top) and Euclidean convexity (bottom). There is a strong association between both types of convexity measured in the pretrained model and the accuracy of the given class in the fine-tuned model. Indeed, there is a significant correlation in both cases. The Pearson correlation between the two types of convexity scores is 0.57 ± 0.04 for both pretrained models and the fine-tuned ones. These results are quantifying the hypothesis that the two convexity scores are related but different. Detailed results can be found in Appendices C.1-C.5. Machine representations are often found to be better described as curved spaces, hence, we recapitulated salient properties of convex sets in flat and curved spaces. In particular, we considered both conventional Euclidean and graph-based convexity. We found that convexity is stable to relevant latent space re-parameterizations ::::::::::::transformations : for deep networks. We developed workflows for the estimation of approximate convexity based on Euclidean and graph methods , which can be used to measure convexity with and without following manifold structure ::for ::::::::: measuring :::::::: convexity in latent spaces. We carried out extensive experiments in multiple domains including visual object recognition, human activity data, audio, text, and medical imaging. Our experiments included networks trained by self-supervised learning and next fine-tuned on domain-specific labels. We found evidence that both types of convexity are pervasive in both pretrained and fine-tuned models. On fine-tuning, we found that class :::::: decision : region convexity generally increases. Importantly, we find evidence that the higher convexity of a class decision region after pretraining is associated with the In this appendix, we present some mathematical background and intuition for the approximate convexity workflow.Theorem 1. The preimage of each decision region under the last dense layer and softmax function is a convex set. More precisely: Let us denote the output of the last dense layer bya k (z) = J j=1 w k,j z j (1)for z ∈ R n and the probabilitiesp k (z) = exp a k (z) K k ′ =1 exp a k ′ (z).(2)EQUATIONThen C k is a convex set for any k ∈ {1, . . . , K} (Bishop & Nasrabadi, 2006) .Proof. Let us define regionsEQUATIONBecause K k ′ =1 exp a k ′ > 0 and by the monotonicity of the exponential function, it holds thatEQUATIONTherefore,EQUATIONand we can from now on work with R k .Following the definitions from Bishop & Nasrabadi (2006) , pages 182-184: Let x A , x B ∈ R k and define any point x that lies on the line connecting the two:EQUATIONwhere 0 ≤ λ ≤ 1. Cf. equation 1, the discriminant functions, a k , are linear and it follows that:EQUATIONfor all k. From the definition of R k , we know that a k (x A ) > a j (x A ) and a k (x B ) > a j (x B ) for all j ̸ = k. Therefore, a k ( x) > a j ( x) for all j ̸ = k and x belongs to R k . Hence, R k = C k is convex.Theorem 2. Let f : R n → R n be an affine transformation (i.e., f (x) = Ax + b, where b ∈ R n and A : R n → R n is an invertible linear transformation). Let X ⊂ R n be a convex set. Then f (X) is convex (Boyd & Vandenberghe, 2010) .Proof. Let x, y ∈ f (X) and λ ∈ [0, 1]. There exist x, y ∈ X such that f (x) = x and f (y) = y. Since X is convex, we have λx + (1 -λ)y ∈ X. Therefore,EQUATIONMoreover, because of the linearity of A,EQUATIONFinally, we haveEQUATIONHence,f (λx + (1 -λ)y) = λx + (1 -λ)y (14) and λx + (1 -λ)y ∈ f (X). Therefore, f (X) is convex.Theorem 3. Graph convexity is invariant to isometry and uniform scaling.Proof. Isometry (with respect to Euclidean distance) is a mapEQUATION)Since isometry preserves distances, it induces the same distance graph. Therefore, graph convexity is invariant to isometries.Universal scaling is a map S : R n → R n such thatEQUATION) It holds that ∥S(x) -S(y)∥ 2 = ∥Cx -Cy∥ 2 = |C| • ∥x -y∥ 2 .(17) All the distances are scaled by |C|. It follows that the chosen nearest neighbours are the same. We show by contradiction that all the shortest paths are also the same. We denote G the graph with the original edges and G S the graph with the scaled edges. Given x, y ∈ R n , suppose that there exists a shortest path:EQUATIONfrom x to y, and a different path:EQUATIONfrom S(x) to S(y) such that L(Q) < L(S(P )), (20) where S(P ) = (S(p 0 ), S(p 1 ), . . . , S(p j )) (21) and L(•) is an operator measuring the length of a path. From equation 20, it follows that C ̸ = 0. Because all the edges are scaled by a factor |C|, it holds that L(S(P )) = |C|L(P ). Moreover, for every pair of nodes v 1 , v 2 , there exists an edge in G from v 1 to v 2 if and only if there exists an edge in G S from S(v 1 ) to S(v 2 ). Hence, there exists a path R from x to y such that Q = S(R). It follows that |C|L(R) = L(S(R)) < L(S(P )) = |C|L(P ).(22) Therefore, L(R) < L(P ) and that contradicts the assumption that P is the shortest path from x to y.We have a dataset D with N C classes each with N C C data points, N total data points, and each data point has a representation in z ∈ R D .Graph Convexity: Computing the graph convexity score requires three steps:1. Compute the nearest neighbor matrix. This cost 1/2N2 D. 2. Create the adjacency matrix. This cost 1/2N 2 . The adjacency matrix will at most have E = N K edges, where K is the K chosen for K-nearest neighbors 3. Compute the convexity score for each pair of data points for each class or concept using Dijkstra's algorithm. This cost1/2CN c (N c -1)(N log N + E).The total computational cost is thencost = 1/2N 2 D + 1/2N 2 + 1/2CN c (N C C -1) (N log N + N K) This simplifies to cost = O N 2 (D + 1) + CN C C (N C C -1)N (log N + K) Since N C N C C = N, and in most cases (N C C -1)(log N + K ≫ (D + 1), the dominating term will be the latter. This can be seen by rewriting: 2. Per point pair, generate N s representations equidistant on a line between z 1 and z 2 . This scales with N s . 3. For each generated representation, compute the classification. This scales with D.cost = O N 2 (D + 1) + N 2 (N C C -1) (log N + K) Instead ofSince all the costs are scaling linearly, the total cost of computing the Euclidean convexity score iscost = O (N c N s N p D) B DATA SETS B.1 IMAGE DOMAINWe used ImageNet-1k (Russakovsky et al., 2015; Deng et al., 2009) in our experiments. The validation set contains 50,000 images in 1000 classes, i.e. 50 images per class.We used data2vec-base (Baevski et al., 2022) architecture. It consists of 12 Transformer layers (Vaswani et al., 2017) and was trained to produce the same representations for an input image and its masked version. It was pretrained on an unlabelled version of ImageNet-1k. For fine-tuning, a linear layer was added on top of the mean-pooled output of the last layer. Both the pretrained model1 and the model fine-tuned 2 on ImageNet-1k (Russakovsky et al., 2015; Deng et al., 2009) were obtained from Hugging Face (Wolf et al., 2020) . Details on pretraining and fine-tuning can be found in the original paper (Baevski et al., 2022) . The final accuracy of the fine-tuned model on the validation set is 83.594%.We extracted the input embedding together with 12 layers. For each layer, we averaged the hidden states across patches to get 768-dimensional feature vectors.To get the predictions for the pretrained model, we trained a linear layer with a learning rate of 0.1, a polynomial scheduler, and a weight decay of 0.0001 for 1000 epochs with the whole training set of ImageNet-1k. The final accuracy on the validation set is 46.766%.In the human activity domain, we used the pretrained model from Yuan et al. (2022) to extract the latent representations. The model is pretrained on a large unlabelled dataset from the UK Biobank, which contains 700,000 person-days of free-living tri-axial accelerometer data. The pretraining procedure is a multi-task self-supervised learning schedule, where the model is trained to predict whether a number of augmentations have been applied or not. The model follows the architecture of ResNet-V2 with 1D convolutions and a total of 21 convolutional layers. The resulting feature vector after the final pretrained layer is of dimension 1024.The model is divided into 5 modules, 4 modules consisting of 2 ResNet blocks each and a final convolutional layer mapping the data to 1024 channels. We extracted the latent representations after each of the 5 modules. We added a single linear layer with softmax activation to obtain the decision regions for both the pretrained and the fine-tuned model. We flattened all the latent representations during the analysis.For testing the methods, we used the Capture-24 dataset (Willetts et al., 2018) . The Capture-24 dataset contains free-living wrist-worn activity tracking data from 152 participants. The participants were tracked for 24 hours and the data was subsequently humanly labelled into 213 categories based on a wearable camera also worn by the participants. Each of the 213 categories is associated with a metabolic equivalent of task (MET) score, which is a number describing the energy expenditure of each task. In Walmsley et al. (2022) , the original 213 labels were divided into 4 coarse labels, namely; sleeping, sedentary behaviour, light physical activity behaviours and moderate-to-vigorous physical activity behaviours based on the MET scores. These 4 labels are used as classes when fine-tuning the model.During fine-tuning, we randomly selected 30 subjects to hold out for testing. We optimized the entire network (encoder and classifier) jointly with a learning rate of 10 -4 . Following the authors in Yuan et al. (2022) , we selected a small validation set and used early-stopping with a patience of 5 epochs. The same procedure was used to obtain the decision regions for the pretrained model, however, the weights of the encoder were frozen.We achieved a balanced accuracy score of 77.0% when fine-tuning the entire model and 72.2% when optimizing only the last linear layer.For each decision region, we sampled 5000 points (or the maximum number available). We then analyzed the convexity of each decision region after each of the 5 modules in the network.In the audio domain, we used the pretrained wav2vec2.0 model (Baevski et al., 2020) , which is trained on the Librispeech corpus (960h of unlabeled data) (Panayotov et al., 2015) . During pertaining, the model learns meaningful latent audio/speech representations, the exact training objectives can be found in Baevski et al. (2020) . The model consists of a CNN-based feature encoder, a transformer-based context network and a quantization module. We were especially interested in the latent space representation in the 12 transformer layers. After each transformer layer, we extracted the feature vector of dimension 768.We fine-tuned the model to perform digit classification based on the AudioMNIST dataset (Becker et al., 2018) , which consists of 30000 audio recordings of spoken digits (0-9) in English of 60 different speakers (with 50 repetitions per digit). For fine-tuning, an average pooling layer and a linear layer were added to the network, to perform a classification task, the fine-tuning procedure was based on a tutorial 3 . The network was fine-tuned on 80% of the people while the remaining 20% were withheld for testing (resulting in 6000 audio files). Two different fine-tunings were performed. First, only the final linear layer was added and trained with a frozen model. This was done with a learning-rate of 1e -3 and early stopping. The final model reached an accuracy of 64%. In the second fine-tuning, only the initial CNN layers were frozen, while the transformer layers and the added linear layer were fine-tuned. The model was fine-tuned with early stopping for 1000 steps (batch-size 16), and the learning rate was set to 1e -4 . No hyperparameter search was performed as the first fine-tuning already led to a very high accuracy of 99.89%. The latent representations of the test set were extracted before and after fine-tuning for both scenarios.For text, we used the base version of RoBERTa 4 (Liu et al., 2019) which is pretrained to perform Masked Language Modelling (Devlin et al., 2018) in order to reconstruct masked pieces of text. The model consists of an embedding layer followed by 12 transformer encoder layers and a classification head. The pretraining of RoBERTa is performed on 160GB of uncompressed English-language text in order to learn latent representations of text which are expressed as 768-dimensional vectors. One notable difference that we make is that the classification head, which in a standard configuration of RoBERTa is a fully-connected dense layer followed by dropout and then lastly a linear projection head to the number of classes, we simply replace all of this with a single linear layer, projecting the hidden last hidden states into the classes.Fine-tuning was done on the 20 newsgroups dataset (Lang, 1995) which consists of around 18,000 newgroups posts, covering 20 different topics. Recommended pre-processing steps were performed to remove headers, signature blocks, and quotations from each new article, as the model would otherwise be likely to overfit to features generated from those fragments. The data was split into a training, validation and test set with 10,000, 1,000 and 7,000 posts, respectively. The data and exact splits that were used are available on HuggingFace5 The validation set was used to perform early stopping during training.We found that the model stopped after 3 epochs and reached an accuracy of 68.9%. This was with a learning rate of 10 -4 and weight-decay of 10 -2 . For the pretrained model, we froze everything up until the final linear projection and only trained the last linear layer. After training for 8 epochs, as dictated by early stopping, an accuracy of 60% was reached through this approach. The learning rate was increased to 10 -2 when training only the linear projection head.We investigated digital images of normal peripheral blood cells (Acevedo et al., 2020) . The dataset contains 17,092 images of eight normal blood cell types: neutrophils, eosinophils, basophils, lymphocytes, monocytes, immature granulocytes (ig), erythroblasts and platelets. Images were obtained with CellaVision DM96 in RGB colour space. The image size is 360 × 363 pixels. Images were labelled by clinical pathologists at the Hospital Clinic of Barcelona.We fully pretrained the base version of I-JEPA (Assran et al., 2023) with a patch size of 16, 12 transformer blocks with a feature dimension 768. I-JEPA is a masked image model, where the pretext task is to predict embeddings of hold-out image context from the embeddings of the encoder. The model was trained using a smooth L1 loss with default settings in PyTorch. The targets were 80% of the available data for a total of 150 epochs. Hyperparameters were kept consistent with the original work of Assran et al. (2023) . We chose a learning rate of 0.001 with cosine decay and a linear warmup of 20 epochs. We used the AdamW optimizer.After pretraining, we froze the model weights of the encoder and trained a linear layer for 50 epochs with the same optimizer and a learning rate of 0.005. The pretrained model with a linear layer achieves an accuracy of 85.3% on the validation set of 1709 subjects. Equivalently, during finetuning, we attached a linear classifier and retrained the whole model. The fine-tuned model reaches an accuracy of 93.5%. We used the 1709 hold-out samples for the convexity analysis. To extract features, we averaged over the patch dimension of the embeddings, resulting in a 768-dimensional vector per subject and layer.Figure 6 shows hubness metrics (k-skewness and Robinhood score) for all models and domains. It follows that hubness is not a problem for any of the domains. Figure 11 shows the t-SNE plots from the human activity domain with samples coloured by their predicted labels. The figure shows the tSNE plots of the representations after the first, third, and last (fifth) layers for both the pretrained and the fine-tuned model. For both models, it is clear that the decision regions change throughout the network. In the first layer, the decision regions are split into multiple different subregions. In the final layers, the regions appear more grouped, as would be expected. This is even more obvious in the fine-tuned model, where the decision regions also seem to have moved further apart. In the final layer, the decision regions are linearly separated in the true representation space. However, when projected into two dimensions by the t-SNE algorithm, it is clear that other structures in the data are also dominating the clustering.Figure 12 shows the convexity analysis for both the pretrained and fine-tuned networks in the human activity domain. In both models, we notice a clear pattern of increasing graph and Euclidean convexity between the first and the last layer. The Euclidean convexity for the pretrained model starts at ≈ 80% and ends, as expected, at 100%. For the fine-tuned model, the Euclidean convexity is even higher in the first layer and also increases to the expected 100%. Looking at the graph convexity scores, it is clear that these are lower compared to the Euclidean scores, and neither the pretrained nor the fine-tuned model have 100% graph convex decision regions in the last layer. It is difficult togive the exact answer as to why, but a plausible suggestion could be that the decision regions contain multiple disconnected subregions. A synthetic example of such a case can be seen in Figure 2 . This hypothesis could also be backed by the t-SNE plots, which indicate dominant substructures in the data that cause disconnectedness of data within decision regions. In general, these results indicate that the graph convexity score is able to capture other substructures in the data than what can be discovered from Euclidean convexity.Figure 13 shows the relation between Euclidean and graph convexity per class. This behaviour is also observed in the convexity analysis, where the convexity generally increases for the classes throughout the layers (Figure 15 ). Euclidean convexity is generally higher than the graph convexity, and the convexity is higher in the fine-tuned model.Figure 16 shows the relation between Euclidean and graph convexity per class. Plotting the graph and Euclidean convexity as in Figure 19 Figure 19 reveals that for the fine-tuned model we actually see some level of correlation between the two measurements. We also see that there is no particular correlation between the graph convexity and euclidean convexity for the pretrained network. This can be explained by the disconnectedness of decision regions in the pretrained network which highly impacts the graph convexity.It is also apparent from Figure 18 that the fine-tuned model does not reach 100% graph convexity in its final layer. Looking at the t-SNE embeddings in Figure 17 we see that some points with different classes are clustered closely together. This might be due to topics in the text being very closely related. This also causes the phenomena where the shortest path is traversed through the other, closely related, class, causing the graph convexity to go down. In Figure 20 , we show t-SNE plots for the pretrained and fine-tuned model. We show embeddings after patch embedding (layer 6), after the middlemost layer in the transformer (layer 6) and just before softmax (layer 12). Clusters of different classes can already be observed in the pretrained model, however, they become more prevalent in the fine-tuned model. We explore the role of the way we construct the graph. The analysis in Section 1.2.1 holds for a graph constructed with a distance cutoff ϵ. We compare it to graphs constructed by keeping Knearest neighbours and symmetrizing the graph. We chose the number of nearest neighbours to be 3, 5, 10 and 20. The respective ϵ values were chosen to keep approximately the same number of edges in the graph.Figure 23b shows that the graph constructed with a distance cutoff ϵ is very disconnected, and the scores computed with this type of neighborhood are biased towards zero (see Figure 23a ). If we skip the disconnected pairs and compute the score only from existing paths, the results are very close to the scores based on K-nearest neighbours (see Figure 23c ).Figure 23b also demonstrates that the role of the size of K is negligible.Figure 24 illustrates the difference between the data labels and the model labels in synthetic data.We repeat the workflow described in Section 2.1 with randomly assigned labels to get a sensible meaning of the convexity scores. This is similar to measuring accuracy -the information that the accuracy of a model is 50% itself does not say much about the performance since it has a completely different meaning if we have two classes (where random guessing would yield 50% accuracy) or if we have 100 classes (with 1% accuracy when randomly guessing). Table 1 shows the mean of baseline scores over the models for all modalities. Since we have classes of similar sizes for each modality, we see that they roughly correspond to https://huggingface.co/facebook/data2vec-vision-basehttps://huggingface.co/facebook/data2vec-vision-base-ft1khttps://colab.research.google.com/github/m3hrdadfi/soxan/blob/main/ notebooks/Eating_Sound_Collection_using_Wav2Vec2.ipynbhttps://huggingface.co/roberta-basehttps://huggingface.co/datasets/rasgaard/20_newsgroups 
 
 Appendix:  



Reviews: review: title: title: Good paper, requires generalization
main_review: main_review: This work explores the concept of convexity in object regions within machine-learned latent spaces as a fundamental aspect of understanding the alignment between human and machine representations. Drawing inspiration from geometric psychology and neuroscience, the paper suggests that measuring the convexity of decision regions in learned latent spaces can be a metric for assessing model generalization ability, establishing a correlation between model convexity and fine-tuned accuracy. 

**Clarity** and **Correctness**: The paper is well-written, and the experiments include various models in various domains, such as images, audio, and text. Perhaps it would be beneficial to explore generalization across other models within the same modality, given that only one model per modality has been tested. 

**Novelty**: The authors investigate the convexity of decision regions in machine-learned representations for the first time, connecting the idea of convex regions in NN spaces to the hypothesis that natural concepts form convex regions in the human brain. Thus, **the paper fits the workshop topic**.
strength_weakness: strength_weakness: The paper is well suited for the workshop since it uses, for the first time, convexity as a tool to understand if there is an alignment between human and machine representations. Furthermore, the authors conducted multiple experiments to support their conclusions.
title: title: Convexity of Deep Neural Network Decision Boundaries
main_review: main_review: Summary: The authors provide a thorough review of the literature surrounding the idea of convexity in cognitive science as well as in both natural and artificial neural network representations and how this is intuitively related to generalization. They then describe precisely how this idea of convexity can be measured empirically with two different metrics (graph convexity and euclidean convexity) and provide intuitive figures to understand the tradeoffs of each. They then evaluate this measure on an extremely wide range of models covering an impressive breadth of modalities (audio, text, image, video, medical images) and demonstrate that their theoretical insights regarding convexity indeed hold up to their empirical evaluation. Finally, they demonstrate, most interestingly, that there is a significant relation between the convexity of pre-trained model decision boundaries and the resulting class-recall of these models *after fine-tuning* -- meaning that convexity appears to be predictive of model performance after fine tuning. They take this to imply that convexity is beneficial for few-shot learning. 

Strengths:
- (Clarity) This paper is exceptionally well written and clear. I would argue that it is one of the clearest and most well illustrated and explained papers I have read in the past few years. I commend the authors for this feat, especially when describing such a technically complex subject.
- (Correctness) To the best of my understanding the experiments, claims, and evaluations made by the authors appear rigorous, although I did not check the proofs in detail. The main claims of the paper however do appear correct and in-line with the provided evidence. 
- (Novelty) I believe measuring convexity of decision boundaries and relating it to cognitive science in this way is indeed novel and something that could be very valuable to the community. 
- (Relevance) As above, this topic is timely, extremely well evaluated, and I think would be of utmost interest to the community. 

Weaknesses:
- Virtually None
- Minor: On page one: "The geometrical approach is rooted in work Shepard (1987)" should use \citep.
strength_weakness: strength_weakness: The paper is extremely well written and evaluated. The topic is timely, interesting and novel. I see no reason to give a lower score.
title: title: Review: On convex decision regions in deep network representations
main_review: main_review: In the paper under review, the authors present an novel idea of quantifying the convexity of activations in specific layers of trained models. They provide a comprehensive recapitulation of the various properties of different convex spaces and introduce a methodology for measuring the convexity of latent spaces. The authors empirically demonstrate that the convexity of a class decision region in a pretrained model can predict the labelling accuracy of that class following fine-tuning.

 - *Clarity*: The paper is well-articulated, offering a broad overview of existing works. The narrative of the paper is well-structured, and the reasoning and results are clearly articulated.
 - *Correctness*: The claims within the paper are well-founded, and proofs are provided to substantiate them.
- *Novelty*: The proposed idea exhibits novelty and is interesting.
- *Interest to the Community*: This paper will be of interest to the representation alignment community due to its novel approach and relevant findings.
strength_weakness: strength_weakness: Positive arguments include the novelty of the idea, clear fit to the workshop theme, well-grounded claims and interesting result.