Debian Codegraph @

src/Persistence_representations/doc/Persistence_representations_doc.h

raw
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Pawel Dlotko
4 *
5 * Copyright (C) 2016 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11 #ifndef DOC_GUDHI_STAT_H_
12 #define DOC_GUDHI_STAT_H_
13
14 namespace Gudhi {
15
16 namespace Persistence_representations {
17
18 /** \defgroup Persistence_representations Persistence representations
19 *
20 * \author Pawel Dlotko
21 *
22 * @{
23 *\section Persistence_representations_idea Idea
24
25 In order to perform most of the statistical tests and machine learning algorithms on a data one need to be able to
26 perform only a very limited number of operations on them. Let us fix a representation of
27 data of a type A. To perform most of the statistical and machine learning operations one need to be able to compute
28 average of objects of type A (so that the averaged object is also of a type A), to
29 compute distance between objects of a type A, to vectorize object of a type A and to compute scalar product of a pair
30 objects of a type A.
31
32 To put this statement into a context, let us assume we have two collections \f$ c_1,\ldots,c_n\f$ and
33 \f$d_1,...,d_n\f$ of objects of a type A. We want to verify if the average of those two collections
34 are different by performing a permutation test.
35 First of all, we compute averages of those two collections: C average of \f$ c_1,\ldots,c_n \f$ and D average of
36 \f$d_1,\ldots,d_n\f$. Note that both C and D are of a type A. Then we compute \f$d(C,D)\f$,
37 a distance between C and D.
38 Later we put the two collections into one bin:
39 \f[B = \{ c_1,...,c_n,d_1,...,d_n \}\f]
40 Then we shuffle B, and we divide the shuffled version of B into two classes: \f$B_1\f$ and \f$B_2\f$ (in this case, of
41 the same cardinality). Then we compute averages \f$\hat{B_1}\f$ and \f$\hat{B_2}\f$
42 of elements in \f$B_1\f$ and \f$B_2\f$. Note that again, \f$\hat{B_1}\f$ and \f$\hat{B_2}\f$ are of a type A.
43 Then we compute their distance \f$d(\hat{B_1},\hat{B_2})\f$. The procedure of shuffling and dividing the set \f$B\f$
44 is repeated \f$N\f$ times (where \f$N\f$ is reasonably large number).
45 Then the p-value of a statement that the averages of \f$c_1,...,c_n\f$ and \f$d_1,...,d_n\f$ is approximated by the
46 number of times \f$d(\hat{B_1},\hat{B_2}) > d(C,D)\f$ divided by \f$N\f$.
47
48 The permutation test reminded above can be performed for any type A which can be averaged, and which allows for
49 computations of distances.
50
51 The Persistence\_representations contains a collection of various representations of persistent homology that
52 implements various concepts described below:
53
54 \li Concept of a representation of persistence that allows averaging (so that the average object is of the same type).
55 \li Concept of representation of persistence that allows computations of distances.
56 \li Concept of representation of persistence that allows computations of scalar products.
57 \li Concept of representation of persistence that allows vectorization.
58 \li Concept of representation of persistence that allows computations of real-valued characteristics of objects.
59
60
61 At the moment an implementation of the following representations of persistence are available (further details of
62 those representations will be discussed later):
63
64 \li Exact persistence landscapes (allow averaging, computation of distances, scalar products, vectorizations and real
65 value characteristics).
66 \li Persistence landscapes on a grid (allow averaging, computation of distances scalar products, vectorizations and
67 real value characteristics).
68 \li Persistence heat maps – various representations where one put some weighted or not Gaussian kernel for each point
69 of diagram (allow averaging, computation of distances, scalar products,
70 vectorizations and real value characteristics).
71 \li Persistence vectors (allow averaging, computation of distances, scalar products, vectorizations and real value
72 characteristics).
73 \li Persistence diagrams / barcodes (allow computation of distances, vectorizations and real value characteristics).
74
75
76 Note that at the while functionalities like averaging, distances and scalar products are fixed, there is no canonical
77 way of vectorizing and computing real valued characteristics of objects. Therefore the
78 vectorizations and computation of real value characteristics procedures are quite likely to evolve in the furthering
79 versions of the library.
80
81 The main aim of this implementation is to be able to implement various statistical methods, both on the level of C++
82 and on the level of python. The methods will operate on the functionalities offered
83 by concepts. That means that the statistical and ML methods will be able to operate on any representation that
84 implement the required concept (including the ones that are not in the library at the moment).
85 That gives provides a framework, that is very easy to extend, for topological statistics.
86
87 Below we are discussing the representations which are currently implemented in Persistence\_representations package:
88
89 \section sec_persistence_landscapes Persistence Landscapes
90 <b>Reference manual:</b> \ref Gudhi::Persistence_representations::Persistence_landscape <br>
91 Persistence landscapes were originally proposed by Bubenik in \cite bubenik_landscapes_2015. Efficient algorithms to
92 compute them rigorously were proposed by Bubenik and Dlotko in \cite bubenik_dlotko_landscapes_2016. The idea of
93 persistence landscapes is shortly summarized in below.
94
95 To begin with, suppose we are given a point \f$(b,d) \in \mathbb{R}^2\f$ in a
96 persistence diagram. With this point, we associate a piecewise
97 linear function \f$f_{(b,d)} : \mathbb{R} \rightarrow [0,\infty)\f$, which is
98 defined as
99
100 \f[f_{(b,d)}(x) =
101 \left\{ \begin{array}{ccl}
102 0 & \mbox{ if } & x \not\in (b, d) \; , \\
103 x - b & \mbox{ if } & x \in \left( b, \frac{b+d}{2}
104 \right] \; , \\
105 d - x & \mbox{ if } & x \in \left(\frac{b+d}{2},
106 d \right) \; .
107 \end{array} \right.
108 \f]
109
110 A persistence landscape of the birth-death
111 pairs \f$(b_i , d_i)\f$, where \f$i = 1,\ldots,m\f$, which constitute the given
112 persistence diagram is the sequence of functions \f$\lambda_k : \mathbb{R} \rightarrow [0,\infty)\f$ for \f$k \in
113 \mathbb{N}\f$, where \f$\lambda_k(x)\f$
114 denotes the \f$k^{\rm th}\f$ largest value of the numbers \f$f_{(b_i,d_i)}(x)\f$,
115 for \f$i = 1, \ldots, m\f$, and we define \f$\lambda_k(x) = 0\f$ if \f$k > m\f$.
116 Equivalently, this sequence of functions can be combined into a single
117 function \f$L : \mathbb{N} \times \mathbb{R} \to [0,\infty)\f$ of two
118 variables, if we define \f$L(k,t) = \lambda_k(t)\f$.
119
120 The detailed description of algorithms used to compute persistence landscapes can be found in
121 \cite bubenik_dlotko_landscapes_2016.
122 Note that this implementation provides exact representation of landscapes. That have many advantages, but also a few
123 drawbacks. For instance, as discussed
124 in \cite bubenik_dlotko_landscapes_2016, the exact representation of landscape may be of quadratic size with respect
125 to the input persistence diagram. It may therefore happen
126 that, for very large diagrams, using this representation may be memory--prohibitive. In such a case, there are two
127 possible ways to proceed:
128
129 \li Use non exact representation on a grid described in the Section \ref sec_landscapes_on_grid.
130 \li Compute just a number of initial nonzero landscapes. This option is available from C++ level as a last parameter of
131 the constructor of persistence landscape (set by default to std::numeric_limits<size_t>::max()).
132
133
134
135 \section sec_landscapes_on_grid Persistence Landscapes on a grid
136 <b>Reference manual:</b> \ref Gudhi::Persistence_representations::Persistence_landscape_on_grid <br>
137 This is an alternative, not--exact, representation of persistence landscapes defined in the Section \ref
138 sec_persistence_landscapes. Unlike in the Section \ref sec_persistence_landscapes we build a
139 representation of persistence landscape by sampling its values on a finite, equally distributed grid of points.
140 Since, the persistence landscapes that originate from persistence diagrams have slope \f$1\f$ or \f$-1\f$, we have an
141 estimate of a region between the grid points where the landscape cab be located.
142 That allows to estimate an error make when performing various operations on landscape. Note that for average
143 landscapes the slope is in range \f$[-1,1]\f$ and similar estimate can be used.
144
145 Due to a lack of rigorous description of the algorithms to deal with this non--rigorous representation of persistence
146 landscapes in the literature, we are providing a short discussion of them in below.
147
148 Let us assume that we want to compute persistence landscape on a interval \f$[x,y]\f$. Let us assume that we want to
149 use \f$N\f$ grid points for that purpose.
150 Then we will sample the persistence landscape on points \f$x_1 = x , x_2 = x + \frac{y-x}{N}, \ldots , x_{N} = y\f$.
151 Persistence landscapes are represented as a vector of
152 vectors of real numbers. Assume that i-th vector consist of \f$n_i\f$ numbers sorted from larger to smaller. They
153 represent the values of the functions
154 \f$\lambda_1,\ldots,\lambda_{n_i}\f$ ,\f$\lambda_{n_i+1}\f$ and the functions with larger indices are then zero
155 functions) on the i-th point of a grid, i.e. \f$x + i \frac{y-x}{N}\f$.
156
157 When averaging two persistence landscapes represented by a grid we need to make sure that they are defined in a
158 compatible grids. I.e. the intervals \f$[x,y]\f$ on which they are defined are
159 the same, and the numbers of grid points \f$N\f$ are the same in both cases. If this is the case, we simply compute
160 point-wise averages of the entries of corresponding
161 vectors (In this whole section we assume that if one vector of numbers is shorter than another, we extend the shorter
162 one with zeros so that they have the same length.)
163
164 Computations of distances between two persistence landscapes on a grid is not much different than in the rigorous
165 case. In this case, we sum up the distances between the same levels of
166 corresponding landscapes. For fixed level, we approximate the landscapes between the corresponding constitutive
167 points of landscapes by linear functions, and compute the \f$L^p\f$ distance between them.
168
169 Similarly as in case of distance, when computing the scalar product of two persistence landscapes on a grid, we sum up
170 the scalar products of corresponding levels of landscapes. For each level,
171 we assume that the persistence landscape on a grid between two grid points is approximated by linear function.
172 Therefore to compute scalar product of two corresponding levels of landscapes,
173 we sum up the integrals of products of line segments for every pair of constitutive grid points.
174
175 Note that for this representation we need to specify a few parameters:
176
177 \li Begin and end point of a grid -- the interval \f$[x,y]\f$ (real numbers).
178 \li Number of points in a grid (positive integer \f$N\f$).
179
180
181 Note that the same representation is used in TDA R-package \cite Fasy_Kim_Lecci_Maria_tda.
182
183 \section sec_persistence_heat_maps Persistence heat maps
184 <b>Reference manual:</b> \ref Gudhi::Persistence_representations::Persistence_heat_maps <br>
185 This is a general class of discrete structures which are based on idea of placing a kernel in the points of
186 persistence diagrams.
187 This idea appeared in work by many authors over the last 15 years. As far as we know this idea was firstly described
188 in the work of Bologna group in \cite Ferri_Frosini_comparision_sheme_1 and \cite Ferri_Frosini_comparision_sheme_2.
189 Later it has been described by Colorado State University group in \cite Persistence_Images_2017. The presented paper
190 in the first time provide a discussion of stability of the representation.
191 Also, the same ideas are used in construction of two recent kernels used for machine learning:
192 \cite Kusano_Fukumizu_Hiraoka_PWGK and \cite Reininghaus_Huber_ALL_PSSK. Both the kernel's construction uses
193 interesting ideas to ensure stability of the representation with respect to Wasserstein metric. In the kernel
194 presented in \cite Kusano_Fukumizu_Hiraoka_PWGK, a scaling function is used to multiply the Gaussian kernel in the
195 way that the points close to diagonal got low weight and consequently do not have a big influence on the resulting
196 distribution. In \cite Reininghaus_Huber_ALL_PSSK for every point \f$(b,d)\f$ two Gaussian kernels
197 are added: first, with a weight 1 in a point \f$(b,d)\f$, and the second, with the weight -1 for a point \f$(b,d)\f$.
198 In both cases, the representations are stable with respect to 1-Wasserstein distance.
199
200 In Persistence\_representations package we currently implement a discretization of the distributions described above.
201 The base of this implementation is 2-dimensional array of pixels. Each pixel have assigned a real value which
202 is a sum of values of distributions induced by each point of the persistence diagram. At the moment we compute the
203 sum of values on a center of a pixels. It can be easily extended to any other function
204 (like for instance sum of integrals of the intermediate distribution on a pixel).
205
206 The parameters that determine the structure are the following:
207
208 \li A positive integer k determining the size of the kernel we used (we always assume that the kernels are square).
209 \li A filter: in practice a square matrix of a size \f$2k+1 \times 2k+1\f$. By default, this is a discretization of
210 N(0,1) kernel.
211 \li The box \f$[x_0,x_1]\times [y_0,y_1]\f$ bounding the domain of the persistence image.
212 \li Scaling function. Each Gaussian kernel at point \f$(p,q)\f$ gets multiplied by the value of this function at the
213 point \f$(p,q)\f$.
214 \li A boolean value determining if the space below diagonal should be erased or not. To be precise: when points close
215 to diagonal are given then sometimes the kernel have support that reaches the region
216 below the diagonal. If the value of this parameter is true, then the values below diagonal can be erased.
217
218 In addition to the previous method, we also provide two more methods to perform exact calculations, in the sense that we use functions
219 instead of matrices to define the kernel between the points of the diagrams.
220 Indeed, in both of these exact methods, the kernel is no longer provided as a square matrix, or a filter (see parameters above), but rather as
221 a function assigning a real value to a pair of points in the plane.
222
223 In the first of these exact methods, we aim at obtaining a finite-dimensional representation of the diagram, so we still use a grid of pixels.
224 On the other hand, in the second exact method, we represent diagrams implicitly as functions (i.e. infinite-dimensional representations). This way, we no longer require grids,
225 but only scalar products and distances are available with these implicit representations. This type of representations is known as
226 kernel methods (see \ref sec_persistence_kernels below for more details on kernels).
227
228 Names can be a bit confusing so we recall that, with this second exact method, we implicitly define a kernel representation of diagrams that is built from a kernel between points
229 in the plane. Hence, we have two kernels here, which are independent. One is defined between points in the plane (its type in the code is Kernel2D), and is a template parameter,
230 whereas the other is defined between persistence diagrams (it is the scalar product of the infinite-dimensional representations of the diagrams).
231
232 \section sec_persistence_vectors Persistence vectors
233 <b>Reference manual:</b> \ref Gudhi::Persistence_representations::Vector_distances_in_diagram <br>
234 This is a representation of persistent homology in a form of a vector which was designed for an application in 3d
235 graphic in \cite Carriere_Oudot_Ovsjanikov_top_signatures_3d. Below we provide a short description of this
236 representation.
237
238 Given a persistence diagram \f$D = \{ (b_i,d_i) \}\f$, for every pair of birth--death points \f$(b_1,d_1)\f$ and
239 \f$(b_2,d_2)\f$ we compute the following three distances:
240
241 \li \f$d( (b_1,d_1) , (b_2,d_2) )\f$.
242 \li \f$d( (b_1,d_1) , (\frac{b_1,d_1}{2},\frac{b_1,d_1}{2}) )\f$.
243 \li \f$d( (b_2,d_2) , (\frac{b_2,d_2}{2},\frac{b_2,d_2}{2}) )\f$.
244
245 We pick the smallest of those and add it to a vector. The obtained vector of numbers is then sorted in decreasing
246 order. This way we obtain a persistence vector representing the diagram.
247
248 Given two persistence vectors, the computation of distances, averages and scalar products is straightforward. Average
249 is simply a coordinate-wise average of a collection of vectors. In this section we
250 assume that the vectors are extended by zeros if they are of a different size. To compute distances we compute
251 absolute value of differences between coordinates. A scalar product is a sum of products of
252 values at the corresponding positions of two vectors.
253
254 \section sec_persistence_kernels Kernels on persistence diagrams
255 <b>Reference manual:</b> \ref Gudhi::Persistence_representations::Sliced_Wasserstein <br>
256 <b>Reference manual:</b> \ref Gudhi::Persistence_representations::Persistence_heat_maps <br>
257
258 Kernels for persistence diagrams can be regarded as infinite-dimensional vectorizations. More specifically,
259 they are similarity functions whose evaluations on pairs of persistence diagrams equals the scalar products
260 between images of these pairs under a map \f$\Phi\f$ taking values in a specific (possibly non Euclidean) Hilbert space \f$k(D_i, D_j) = \langle \Phi(D_i),\Phi(D_j)\rangle\f$.
261 Reciprocally, classical results of learning theory ensure that such a \f$\Phi\f$ exists for a given similarity function \f$k\f$ if and only if \f$k\f$ is <i>positive semi-definite</i>.
262 Kernels are designed for algorithms that can be <i>kernelized</i>, i.e., algorithms that only require to know scalar products between instances in order to run.
263 Examples of such algorithms include Support Vector Machines, Principal Component Analysis and Ridge Regression.
264
265 There have been several attempts at defining kernels, i.e., positive semi-definite functions, between persistence diagrams within the last few years. We provide implementation
266 for the <i>Sliced Wasserstein kernel</i>---see \cite pmlr-v70-carriere17a, which takes the form of a Gaussian kernel with a specific distance between persistence diagrams
267 called the <i>Sliced Wasserstein distance</i>: \f$k(D_1,D_2)={\rm exp}\left(-\frac{SW(D_1,D_2)}{2\sigma^2}\right)\f$. Other kernels such as the Persistence Weighted Gaussian kernel or
268 the Persistence Scale Space kernel are implemented in Persistence_heat_maps.
269
270 When launching:
271
272 \code $> ./Sliced_Wasserstein
273 \endcode
274
275 the program output is:
276
277 \code $> Approx SW kernel: 0.0693743
278 $> Exact SW kernel: 0.0693218
279 $> Distance induced by approx SW kernel: 1.36428
280 $> Distance induced by exact SW kernel: 1.3643
281 \endcode
282
283 */
284 /** @} */ // end defgroup Persistence_representations
285
286 } // namespace Persistence_representations
287 } // namespace Gudhi
288
289 #endif // Persistence_representations