| 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 |