Separating Topological Noise from Features Using Persistent Entropy

Separating Topological Noise from Features Using Persistent Entropy Nieves Atienza1, Rocio Gonzalez-Diaz1, and Matteo Rucco2 1Applied Math Department, School of Computer Engineering, University of Seville, Seville, Spain {natienza,rogodi}@us.es 2Computer Science Division, School of Science and Technology, University of Camerino, Camerino, Italy [email protected] Abstract. Topology is the branch of mathematics that studies shapes and maps among them. From the algebraic definition of topology a new set of algorithms have been derived. These algorithms are identified with “computational topology” or often pointed out as Topological Data Analysis (TDA) and are used for investigating high-dimensional data in a quantitative manner. Persistent homology appears as a fundamental tool in Topological Data Analysis. It studies the evolution of k−dimensional holes along a sequence of simplicial complexes (i.e. a filtration). The set of intervals representing birth and death times of k−dimensional holes along such sequence is called the persistence barcode. k−dimensional holes with short lifetimes are informally considered to be topological noise, and those with a long lifetime are considered to be topological feature associated to the given data (i.e. the filtration). In this paper, we derive a simple method for separating topological noise from topological features using a novel measure for comparing persistence barcodes called persistent entropy. Keywords: Persistent homology ·Persistence barcodes ·Shannon entropy ·Topological noise ·Topological features 1 Introduction Persistent homology studies the evolution of k−dimensional holes along a sequence of simplicial complexes. Persistence barcode is the collection of intervals representing birth and death times of k−dimensional holes along such sequence. In persistence barcode, k−dimensional holes with short lifetimes are informally considered to be “topological noise”, and those with a long lifetime are “topological features” of the given data. In general, “very” long living intervals (long lifetime) are considered topological features since they are stable to “small” changes in the filtration. Nevertheless, the definition of what a “topological feature” is, depends on the application. This way, the technique presented in this paper should be considered as an option that can be used for discriminating between topological features and topological noise. Moreover, we claim it is very easy (and fast) to compute, and easy to adapt depending on the application. In [1] a methodology is presented for deriving confidence sets for persistence diagrams to separate topological noise from topological features. The authors focused on simple, synthetic examples as proof of concept. Their methods have a simple visualization: one only needs to add a band around the diagonal of the persistence diagram. Points in the band are consistent with being noise. The first three methods are based on the distance function to the data. They started with a sample from a distribution Psupported on a topological space C.The bottleneck distance is used as a metric on the space of persistence diagrams. The last method uses density estimation. The advantage of the former is that it is more directly connected to the raw data. The advantage of the latter is that it is less fragile; that is, it is more robust to noise and outliers. Persistent entropy (which is the Shannon entropy of the persistence barcode) is a tool formally defined in [2] and used to measure similarities between two persistence barcodes. A precursor of this definition was given in [3]tomeasure how different the intervals of a barcode are in length. In this paper, we use the difference of persistent entropy to measure similarities between two persistent barcodes. More concretely, we derive a simple method for separating topological noise from topological features of a given persistence barcode obtained from a given filtration (ie., a sequence of simplicial complexes) using the mentioned persistent entropy measurement. 2 Related Work Persistent homology based techniques are nowadays widely used for analyzing high dimensional dataset and they are good tool for shaping these dataset and for understanding the meaning of the shapes. There are several techinques for building a topological space from the data. The main approach is to complete the data to a collection of combinatorial objects, i.e. simplices. A nested collection of simplices forms a simplicial complex. Simplicial complexes can be obtained from graphs and point cloud data (PCD) [4,5]. For example, PCD can be completed to simplicial complexes by using the Vietoris-Rips approach. Vietoris-Rips filtration is a versatile tool in topological data analysis. It is a sequence of simplicial complexes built on a metric space to add topological structure to an otherwise disconnected set of points. It is widely used because it encodes useful information about the topology of the underlying metric space. The mathematical details of Vietoris-Rips filtration are given in Sect. 3. Let’s take a look at Fig. 1, it represents a collection of RNA secondary suboptimal structures within different bacteria. All the shapes are characterized by several circular substructures, each of them is obtained by linking different nucleotides. Each substructure encodes functional properties of the bacteria. Persistent homology properly identifies these substructures. For the love of preciseness, Mamuye et al. [6], used Vietoris-Rips complexes and persistent homology Fig. 1. From left to right: RNA secondary suboptimal structures within different bacteria. for certifying that there are different species but characterized with the same RNA suboptimal secondary structure, thus these species are functionally equivalent. In [7], the authors proposed a new methodology based on information theory and persistent homology for classifying real length noisy signals produced by small DC motors. They introduced an innovative approach based on “auto mutual information” and the “CAO’s method” for providing the time delay embedding of signals. The time delay embedding transforms the signal into a point cloud data in Rd, where dis the dimension of the new space. Vietoris-Rips complex is then computed and analyzed by persistent homology. The authors classified the signal in two classes, respectively “properly working” and “broken”. However, Vietoris-Rips based analysis suffers of the selection of the parameter . Generally speaking, for different , different topological features can be observed. In [7], was selected as the euclidean distance among the points in the new space. We remark that the parameter does not have a unique physical meaning and it depends on the problem under analysis. For example, in [8], several applications of Vietoris-Rips based analysis to biological problems have been reported and examples of different with different meaning were found. In order to select the best , some statistics have been provided what it is known as “persistence landscape” [9]. Landscape is a powerful tool for statistically assessing the global shape of the data over different . Technically speaking, a landscape is a piecewise linear function that basically maps a point within a persistent diagram (or barcode) to a point in which the x−coordinate is the average parameter value over which the feature exists, and the y−coordinate is the half-life of the feature. Landscape analysis allows to identify topological features and which are not. In Sect. 5we propose an alternative approach to landscape. The main difference between landscape and our method is that the former uses the average of , while the latter works directly on a fixed . 3 Background This section provides a short recapitulation of the basic concepts needed as a basis for the presented method for separating topological noise from features. Informally, a topological space is a set of points each of them equipped with the notion of neighboring. A simplicial complex is a kind of topological space constructed by the union of n-dimensional simple pieces in such a way that the common intersection of two pieces are lower-dimensional pieces of the same kind. More concretely, an abstract simplicial complex Kis composed by a set K0of 0−simplices (also called vertices V, that can be thought as points in Rn); and, for each k≥1, a set Kkof k−simplices σ={v0,v 1,...,v k}, where vi∈Vfor all i∈{0,...,k}, satisfying that: –eachk−simplex has k+ 1 faces obtained removing one of its vertices; – if a simplex σis in K, then all faces of σmust be in K. The underlying topological space of Kis the union of the geometric realization of its simplices: points for 0-simplices, line segments for 1-simplices, filled triangles for 2-simplices, filled tetrahedra for 3-simplices and their n-dimensional counterparts for n-simplices. We only consider finite (abstract) simplicial complexes with finite dimension, i.e., there exists an integer n(called the dimension of K) such that for k>n,Kk=∅and for 0 ≤k≤n,Kkis a finite set. See [10,11]for an introduction to algebraic topology. Two classical examples of abstract simplicial complexes are each complexes and Vietoris-Rips complexes (see [12, Chapter 3]). Let Vbe a finite set of points in Rn.Theech complex of Vand rdenoted by r(V) is the abstract simplicial complex whose simplices are formed as follows. For each subset Sof points in V, form a closed ball of radius r/2 around each point in S, and include Sas a simplex of r(V) if there is a common point contained in all of the balls in S. This structure satisfies the definition of abstract simplicial complex. The Vietoris- Rips complex denoted as VR r(V) is essentially the same as the ech complex. Instead of checking if there is a common point contained in the intersection of the (r/2)−ball around vfor all vin S, we may just check pairs adding Sas a simplex of r(V) if all the balls have pairwise intersections. We have r(V)⊆ VR r(V)⊆√2r(V). See Fig. 2. Fig. 2. [12, p. 72] Nine points with pairwise intersections among the disks indicated by straight edges connecting their centers, for a fixed time . The ech complex (V) fills nine of the ten possible triangles as well as the two tetrahedra. The Vietoris-Rips complex VR (V) fills the ten triangles and the two tetrahedra. Homology is an algebraic machinery used for describing topological spaces. The k−Betti number βkrepresents the rank of the k−dimensional homology group of a given simplicial complex K. Informally, β0is the number of connected components, β1counts the number of loops in R2or tunnels in R3,β2can be thought as the number of voids and, in general, βkcan be thought as the number of k-dimensional holes. Persistent homology is a method for computing k−dimensional holes of K at different spatial resolutions. The key idea is as follows: First, the space must be represented as a simplicial complex and a distance function must be defined on the space. Second, a filtration of the simplicial complex, that is a nested sequence of increasing subsets (referred above as different spatial resolutions), is computed. More concretely, a filtration of a simplicial complex Kis a collection of simplicial complexes {K(t)|t∈R}of Ksuch that K(t)⊂K(s)fort<sand there exists tmax ∈Rsuch that Ktmax =K. The filtration time (or filter value) of a simplex σ∈Kis the smallest tsuch that σ∈K(t). Then, persistent homology describes how the homology of a given simplicial complex Kchanges along filtration. If the same topological feature (i.e., k−dimensional hole) is detected along a large number of subsets in the filtration, then it is likely to represent a true feature of the underlying space, rather than artifacts of sampling, noise, or particular choice of parameters. More concretely, a k−dimensional Betti interval, with endpoints [tstart,t end),corresponds to a k−dimensional hole that appears at filtration time tstart and remains until filtration time tend. The set of intervals representing birth and death times of homology classes is called the persistence barcode associated to the corresponding filtration. For more details and a more formal description we refer to [12]. 4 Persistent Entropy In order to measure how much the construction of a filtered simplicial complex is ordered, a new entropy measure, the so-called persistent entropy, were defined in [2]. A precursor of this definition was given in [3] to measure how different the intervals of a barcode are in length. In [13], persistent entropy is used for addressing the comparison between discrete piece-wise linear functions. Given a ech or Vietoris-Rips filtration F={K(t)|t≤T}(in practice one will never construct the filtration up to the end and will stop at a certain time T), and the corresponding persistence barcode B={[ai,b i):1≤i≤n},let L={i=bi−ai:1≤i≤n}.Thepersistent entropy Hof the filtration Fis: HL=− n  i=1 i SL log i SL ,being SL= i∈I i. Note that the maximum persistent entropy would correspond to the situation in which all the intervals in the barcode are of equal length. Conversely, the value of the persistent entropy decreases as more intervals of different lengths are present. More concretely, if Bhas nintervals, the possible values of the persistent entropy HLassociated with the barcode Blie in the interval [0,log(n)]. The following result supports the idea that persistent entropy can differentiate long from short intervals as we will see in the next section. Theorem 1. Forafixedintegeri,1≤i≤n,letLi={i+1,... n},Si= n j=i+1 jand let Hibe the persistent entropy associated to Li.Let L(i)={ 1,...,  i, i+1,..., n},where  j=Si/eHi,for 1≤j≤i. Then HL≤HL(i). Proof. Let us prove that HL(i) is the maximum of all the possible persistent entropies associated to lists of intervals with nelements, such that the last n−i elements of any of such lists is {i+1,..., n}.LetM={x1,...,x i, i+1,..., n} (where xj>0for1≤j≤i) be any of such lists. Let Sx=i j=1 xj. Then, the persistent entropy associated to Mis: HM= i  j=1 xj Sx+Si log xj Sx+Si+ n  j=i+1 j Sx+Si log j Sx+Si. In order to find out the maximum of HMwith respect to the unknown variables xk,1≤k≤i, we compute the partial derivative of HMwith respect to those variables: ∂HM ∂xk =1 (Sx+Si)2⎛ ⎝−SiHi+Silog Si xk+ j=k xjlog xj xk⎞ ⎠. Finally, {xk=Si eHi:1≤k≤i}is the solution of the system {∂HM ∂xk=0:1≤ k≤i}. 5 Separating Topological Features from Topological Noise Let us start with a sample Vfrom a distribution Psupported on a topological space C. Suppose the Vietoris-Rips filtration Fis computed from V, and the persistence barcodes Bis computed from F. The following are the steps of our proposed method, based on persistent entropy, to separate topological noise from topological features in the persistence barcode B, estimating, in this way, the topology of C. 1. Order the intervals in Bby decreasing length. Then L={i=bi−ai:1≤ i≤n}satisfies that i≤jfor i<j; 2. Compute the persistent entropy HLof B. Denote HL(0) := HL. 3. From i=1toi=n, a. Compute the persistent entropy HL(i)for L(i)={ 1,...,  i, i+1,..., n}, being  k=Si eHifor 1 ≤k≤ias in Theorem 1. b. Compute Hrel(i)=(HL(i)−HL(i−1))/(log(n)−HL). c. If Hrel(i)>i n, then the associated interval [ai,b i) represents a topological feature. Otherwise, the interval [ai,b i) represents noise. Steps 1, 2 and 3.a can be considered as a general method for any kind of application. For 1 ≤i≤n,HL(i)is the entropy of the barcode obtained by replacing the intervals 1,..., iby iintervals that maximize the entropy. Observe that HL(0) =HL,HL(i)<H L(j)for 0 ≤i<j≤nand HL(n)= log(n)by Theorem 1. Step 3.b and 3.c are used to test a possible dissimilarity measure to differentiate topological features from noise. These two steps could be modified later depending on the application. In this paper, we use HL(i)−HL(i−1) to measure the influence of the current interval iin the initial persistent entropy HL.It is in order to appreciate this influence, why we divide HL(i)−HL(i−1) by the difference of the possible maximal entropy (which is log(n)) and HL. Then, we compare the resulting Hrel(i) with i nsince Hrel(i)is affected by the total number of intervals and the number of intervals we are replacing. Fig. 3. Left: 30 data points sampled from a circle of radius 2. Middle: Balls of radius 0.5 centered at the sample points. Right: Balls of radius 0.8 centered at the sample points. We have applied our methodology to two different scenarios. First, we take 30 data points sampled from a circle of radius 2 (see Fig. 3(Left)). This example has been taken from paper [1]. Vietoris-Rips complex for t=0.5 can be deduced from the picture shown in Fig. 3(Middle) which consists of two connected components and zero loops. Looking at Vietoris-Rips complex for t=0.8 (see Fig. 3(Right)), we assist at the birth and death of topological features: at t=0.8, one of the connected components has died (was merged with the other one), and a loop appears; this loop will die at t= 2, when the union of the pink balls representing the distance function becomes simply connected. In our method, an interval is considered to be a feature if Hrel(i)>i n.In Table 1(Left), we have applied our method to the intervals that make up the barcode (without differentiating dimension). This way, only the intervals with length 2 (that corresponds to the connected component that survives until the end) and 1.2 (that correspond to the loop that appears at t=0.8 and disappears at t= 2) are considered features. Later, in Table 1(Right) we have applied our method to the intervals that make up the 0-barcode (i.e., the lifetime of the connected components along the filtration). This way, the intervals with length 2 and 0.7 (that corresponds to the connected components that dies just before the loop is created) are considered features. This example highlight that we the results may be different depending on if we apply our method to the whole set of intervals of the barcode or if we do it dimension by dimension. Table 1. Results of our method applied to the intervals that make up: (Left) the barcode (i.e., without differentiating dimension); and (Right) the 0-barcode; both associated to the Vietoris-Rips filtration obtained from 30 data points sampled from a circle of radius 2 (see Fig. 3(Left)). i Hi log(n)Hrel(i)Feature 2. 0.967011 0.542391 yes 1.2 0.985761 0.260088 yes 0.7 0.991422 0.07853 no 0.45 0.992506 0.0150434 no 0.45 0.993746 0.0171948 no ... ... ... ... li Hi log(n)Hrel(i)Feature 2. 0.985109 0.77248 yes 0.7 0.991032 0.0905039 yes 0.45 0.992167 0.0173301 no 0.45 0.993463 0.0198057 no 0.4 0.994199 0.0112466 no ... ... ... ... Consider now a set Vof 400 points sampled from a 3D torus. The barcodes (separated by dimension) computed from the Vietoris-Rips filtration associated to Vare showed in Fig. 4. We have applied our method to the 0-barcode (lifetime of connected components along the V-R filtration) and the 1-barcode (lifetime of loops along the V-R filtration). See Table 2(Left) and (Right), respectively. The interval of length 1.9 in the table on the left corresponds to the connected component that survives until the end. The intervals of length 1.531 in the table on the right corresponds to the two tunnels of the 3D torus. In Table 3we show the results of our method applied to all the intervals of the barcode without separating by dimensions. We can see in this case that we obtain the same features as before plus the interval representing the void. Table 2. Results of our method applied to the 0-barcode (table on the left) and the 1-barcode (table on the right) associated to the Vietoris-Rips filtration obtained from 400 points sampled from a 3D torus. i Hi log(n)Hrel(i)Feature 1.9 0.996295 0.442767 yes 0.396 0.996325 0.00449624 no 0.387 0.996351 0.00386916 no 0.387 0.996376 0.00389884 no 0.387 0.996403 0.00392887 no ... ... ... ... i Hi log(n)Hrel(i)Feature 1.531 0.918238 0.238936 yes 1.531 0.950752 0.302654 yes 0.27 0.952044 0.012028 no 0.261 0.953275 0.011451 no 0.234 0.954209 0.00869544 no ... ... ... ... Table 3. Results of our method applied to the barcode (without differentiating dimension) associated to the Vietoris-Rips filtration obtained from 400 points sampled from a 3D torus. i i L i  i L(i) HL(i) log(n)Hrel(i)Feature 1.9 0.0145219 0.268369 0.00207708 0.971259 0.0799069 yes 1.531 0.0117016 0.262812 0.00205432 0.972992 0.0554616 yes 1.531 0.0117016 0.257239 0.00203115 0.974775 0.0570812 yes 1.234 0.00943158 0.253276 0.00201566 0.975978 0.0385369 yes 0.396 0.00302667 0.252916 0.00201511 0.976021 0.00137745 no ... ... ... ... ... ... ... Fig. 4. Barcodes (separated by dimension) computed from the Vietoris-Rips filtration associated to a point cloud lying on a 3D torus. Left: lifetimes of connected components. Middle: lifetimes of tunnels. Right: lifetimes of voids. 6 Conclusions and Future Work In this paper, we have derived a method for separating topological noise from topological features using the Shannon entropy of persistence barcode. We have proven that the method is consistent by proving that in step iof the method we replace iintervals by the same number of intervals but with the length that maximizes the entropy. This way we “neutralize” the effect of such iintervals and, by computing the difference of the entropies obtained in step i−1 and step i, we can deduce if the interval at position iis a topological feature or not. We intend to adapt our method to study RNA data from healthy and unhealthy cells. We argue the method will let to highlight the topological features that are formed by the most relevant genes associated to pathologies. Acknowledgments. Authors are partially supported by IMUS, University of Seville under grant VPPI-US and Spanish Government under grant MTM2015-67072-P (MINECO/FEDER, UE). We also thank the reviewers for their valuable and constructive comments.