From 842475615841f864b4ce41a2a4b69f1e189a2946 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 15:02:32 +0200 Subject: created wasserstein repo --- src/python/gudhi/wasserstein/barycenter.py | 158 +++++++++++++++++++++++++++++ 1 file changed, 158 insertions(+) create mode 100644 src/python/gudhi/wasserstein/barycenter.py (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py new file mode 100644 index 00000000..079bcc57 --- /dev/null +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -0,0 +1,158 @@ +# This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. +# See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. +# Author(s): Theo Lacombe +# +# Copyright (C) 2019 Inria +# +# Modification(s): +# - YYYY/MM Author: Description of the modification + + +import ot +import numpy as np +import scipy.spatial.distance as sc + +from gudhi.wasserstein import wasserstein_distance + + +def _mean(x, m): + ''' + :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} + :param m: total amount of points taken into account, + that is we have (m-k) copies of diagonal + :returns: the weighted mean of x with (m-k) copies of the diagonal + ''' + k = len(x) + if k > 0: + w = np.mean(x, axis=0) + w_delta = (w[0] + w[1]) / 2 * np.ones(2) + return (k * w + (m-k) * w_delta) / m + else: + return np.array([0, 0]) + + +def lagrangian_barycenter(pdiagset, init=None, verbose=False): + ''' + :param pdiagset: a list of size m containing numpy.array of shape (n x 2) + (n can variate), encoding a set of + persistence diagrams with only finite coordinates. + :param init: The initial value for barycenter estimate. + If None, init is made on a random diagram from the dataset. + Otherwise, it must be an int + (then we init with diagset[init]) + or a (n x 2) numpy.array enconding + a persistence diagram with n points. + :param verbose: if True, returns additional information about the + barycenter. + :returns: If not verbose (default), a numpy.array encoding + the barycenter estimate of pdiagset + (local minima of the energy function). + If pdiagset is empty, returns None. + If verbose, returns a couple (Y, log) + where Y is the barycenter estimate, + and log is a dict that contains additional informations: + - groupings, a list of list of pairs (i,j), + That is, G[k] = [(i, j) ...], where (i,j) indicates + that X[i] is matched to Y[j] + if i = -1 or j = -1, it means they + represent the diagonal. + - energy, a float representing the Frechet + energy value obtained, + that is the mean of squared distances + of observations to the output. + - nb_iter, integer representing the number of iterations + performed before convergence of the algorithm. + ''' + X = pdiagset # to shorten notations, not a copy + m = len(X) # number of diagrams we are averaging + if m == 0: + print("Warning: computing barycenter of empty diag set. Returns None") + return None + + # store the number of off-diagonal point for each of the X_i + nb_off_diag = np.array([len(X_i) for X_i in X]) + # Initialisation of barycenter + if init is None: + i0 = np.random.randint(m) # Index of first state for the barycenter + Y = X[i0].copy() + else: + if type(init)==int: + Y = X[init].copy() + else: + Y = init.copy() + + nb_iter = 0 + + converged = False # stoping criterion + while not converged: + nb_iter += 1 + K = len(Y) # current nb of points in Y (some might be on diagonal) + G = np.full((K, m), -1, dtype=int) # will store for each j, the (index) + # point matched in each other diagram + #(might be the diagonal). + # that is G[j, i] = k <=> y_j is matched to + # x_k in the diagram i-th diagram X[i] + updated_points = np.zeros((K, 2)) # will store the new positions of + # the points of Y. + # If points disappear, there thrown + # on [0,0] by default. + new_created_points = [] # will store potential new points. + + # Step 1 : compute optimal matching (Y, X_i) for each X_i + # and create new points in Y if needed + for i in range(m): + _, indices = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) + for y_j, x_i_j in indices: + if y_j >= 0: # we matched an off diagonal point to x_i_j... + if x_i_j >= 0: # ...which is also an off-diagonal point. + G[y_j, i] = x_i_j + else: # ...which is a diagonal point + G[y_j, i] = -1 # -1 stands for the diagonal (mask) + else: # We matched a diagonal point to x_i_j... + if x_i_j >= 0: # which is a off-diag point ! + # need to create new point in Y + new_y = _mean(np.array([X[i][x_i_j]]), m) + # Average this point with (m-1) copies of Delta + new_created_points.append(new_y) + + # Step 2 : Update current point position thanks to groupings computed + to_delete = [] + for j in range(K): + matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] + new_y_j = _mean(matched_points, m) + if not np.array_equal(new_y_j, np.array([0,0])): + updated_points[j] = new_y_j + else: # this points is no longer of any use. + to_delete.append(j) + # we remove the point to be deleted now. + updated_points = np.delete(updated_points, to_delete, axis=0) + + # we cannot converge if there have been new created points. + if new_created_points: + Y = np.concatenate((updated_points, new_created_points)) + else: + # Step 3 : we check convergence + if np.array_equal(updated_points, Y): + converged = True + Y = updated_points + + + if verbose: + groupings = [] + energy = 0 + log = {} + n_y = len(Y) + for i in range(m): + cost, edges = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) + groupings.append(edges) + energy += cost + log["groupings"] = groupings + energy = energy/m + print(energy) + log["energy"] = energy + log["nb_iter"] = nb_iter + + return Y, log + else: + return Y + -- cgit v1.2.3 From c36080ab9e478cd0d44bfd8d5bb8f4726a8aa937 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Wed, 1 Apr 2020 20:24:01 +0200 Subject: improved doc readability --- src/python/gudhi/wasserstein/barycenter.py | 54 ++++++++++++++++-------------- 1 file changed, 28 insertions(+), 26 deletions(-) (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index 079bcc57..fae6b68f 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -33,35 +33,37 @@ def _mean(x, m): def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' - :param pdiagset: a list of size m containing numpy.array of shape (n x 2) - (n can variate), encoding a set of + :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` + (`n` can variate), encoding a set of persistence diagrams with only finite coordinates. :param init: The initial value for barycenter estimate. - If None, init is made on a random diagram from the dataset. - Otherwise, it must be an int - (then we init with diagset[init]) - or a (n x 2) numpy.array enconding - a persistence diagram with n points. - :param verbose: if True, returns additional information about the + If ``None``, init is made on a random diagram from the dataset. + Otherwise, it can be an ``int`` + (then initialization is made on ``pdiagset[init]``) + or a `(n x 2)` ``numpy.array`` enconding + a persistence diagram with `n` points. + :type init: int, (n x 2) np.array + :param verbose: if ``True``, returns additional information about the barycenter. - :returns: If not verbose (default), a numpy.array encoding - the barycenter estimate of pdiagset - (local minima of the energy function). - If pdiagset is empty, returns None. - If verbose, returns a couple (Y, log) - where Y is the barycenter estimate, - and log is a dict that contains additional informations: - - groupings, a list of list of pairs (i,j), - That is, G[k] = [(i, j) ...], where (i,j) indicates - that X[i] is matched to Y[j] - if i = -1 or j = -1, it means they - represent the diagonal. - - energy, a float representing the Frechet - energy value obtained, - that is the mean of squared distances - of observations to the output. - - nb_iter, integer representing the number of iterations - performed before convergence of the algorithm. + :type verbose: boolean + :returns: If not verbose (default), a ``numpy.array`` encoding + the barycenter estimate of pdiagset + (local minimum of the energy function). + If ``pdiagset`` is empty, returns ``None``. + If verbose, returns a couple ``(Y, log)`` + where ``Y`` is the barycenter estimate, + and ``log`` is a ``dict`` that contains additional informations: + + - `"groupings"`, a list of list of pairs ``(i,j)``. + Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates + that ``pdiagset[k][i]`` is matched to ``Y[j]`` + if ``i = -1`` or ``j = -1``, it means they + represent the diagonal. + + - `"energy"`, ``float`` representing the Frechet energy value obtained. + It is the mean of squared distances of observations to the output. + + - `"nb_iter"`, ``int`` number of iterations performed before convergence of the algorithm. ''' X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging -- cgit v1.2.3 From 731358cbfe3880b02a58c70923b5a990ddff7644 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Wed, 1 Apr 2020 20:27:27 +0200 Subject: improved doc, adding double quot for init --- src/python/gudhi/wasserstein/barycenter.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index fae6b68f..e879b7dd 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -42,7 +42,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): (then initialization is made on ``pdiagset[init]``) or a `(n x 2)` ``numpy.array`` enconding a persistence diagram with `n` points. - :type init: int, (n x 2) np.array + :type init: ``int``, or (n x 2) ``np.array`` :param verbose: if ``True``, returns additional information about the barycenter. :type verbose: boolean -- cgit v1.2.3 From 4cfe8411f808f52bee0ba37e28fa9f6cc3519abb Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 3 Apr 2020 17:27:47 +0200 Subject: removed the print of energy in verbose mode, added by error --- src/python/gudhi/wasserstein/barycenter.py | 1 - 1 file changed, 1 deletion(-) (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index e879b7dd..99f29a1e 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -150,7 +150,6 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): energy += cost log["groupings"] = groupings energy = energy/m - print(energy) log["energy"] = energy log["nb_iter"] = nb_iter -- cgit v1.2.3 From dd96965e521313b6210391f511c82cced9b2a950 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Mon, 6 Apr 2020 19:37:58 +0200 Subject: Remove trailing whitespace --- src/python/doc/wasserstein_distance_user.rst | 72 +++++++++++++------------- src/python/gudhi/wasserstein/barycenter.py | 42 +++++++-------- src/python/gudhi/wasserstein/wasserstein.py | 14 ++--- src/python/test/test_wasserstein_barycenter.py | 6 +-- src/python/test/test_wasserstein_distance.py | 2 +- 5 files changed, 68 insertions(+), 68 deletions(-) (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index b821b6fa..c24da74d 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -10,10 +10,10 @@ Definition .. include:: wasserstein_distance_sum.inc The q-Wasserstein distance is defined as the minimal value achieved -by a perfect matching between the points of the two diagrams (+ all -diagonal points), where the value of a matching is defined as the +by a perfect matching between the points of the two diagrams (+ all +diagonal points), where the value of a matching is defined as the q-th root of the sum of all edge lengths to the power q. Edge lengths -are measured in norm p, for :math:`1 \leq p \leq \infty`. +are measured in norm p, for :math:`1 \leq p \leq \infty`. Distance Functions ------------------ @@ -54,9 +54,9 @@ The output is: Wasserstein distance value = 1.45 -We can also have access to the optimal matching by letting `matching=True`. +We can also have access to the optimal matching by letting `matching=True`. It is encoded as a list of indices (i,j), meaning that the i-th point in X -is mapped to the j-th point in Y. +is mapped to the j-th point in Y. An index of -1 represents the diagonal. .. testcode:: @@ -84,7 +84,7 @@ An index of -1 represents the diagonal. The output is: .. testoutput:: - + Wasserstein distance value = 2.15 point 0 in dgm1 is matched to point 0 in dgm2 point 1 in dgm1 is matched to point 2 in dgm2 @@ -94,32 +94,32 @@ The output is: Barycenters ----------- -A Frechet mean (or barycenter) is a generalization of the arithmetic -mean in a non linear space such as the one of persistence diagrams. -Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is -defined as a minimizer of the variance functional, that is of -:math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. -where :math:`d_2` denotes the Wasserstein-2 distance between -persistence diagrams. -It is known to exist and is generically unique. However, an exact -computation is in general untractable. Current implementation -available is based on (Turner et al., 2014), +A Frechet mean (or barycenter) is a generalization of the arithmetic +mean in a non linear space such as the one of persistence diagrams. +Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is +defined as a minimizer of the variance functional, that is of +:math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. +where :math:`d_2` denotes the Wasserstein-2 distance between +persistence diagrams. +It is known to exist and is generically unique. However, an exact +computation is in general untractable. Current implementation +available is based on (Turner et al., 2014), :cite:`turner2014frechet` -and uses an EM-scheme to -provide a local minimum of the variance functional (somewhat similar -to the Lloyd algorithm to estimate a solution to the k-means +and uses an EM-scheme to +provide a local minimum of the variance functional (somewhat similar +to the Lloyd algorithm to estimate a solution to the k-means problem). The local minimum returned depends on the initialization of -the barycenter. -The combinatorial structure of the algorithm limits its -performances on large scale problems (thousands of diagrams and of points -per diagram). +the barycenter. +The combinatorial structure of the algorithm limits its +performances on large scale problems (thousands of diagrams and of points +per diagram). + +.. figure:: + ./img/barycenter.png + :figclass: align-center -.. figure:: - ./img/barycenter.png - :figclass: align-center - - Illustration of Frechet mean between persistence - diagrams. + Illustration of Frechet mean between persistence + diagrams. .. autofunction:: gudhi.wasserstein.barycenter.lagrangian_barycenter @@ -127,16 +127,16 @@ per diagram). Basic example ************* -This example estimates the Frechet mean (aka Wasserstein barycenter) between +This example estimates the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. It is initialized on the 4th diagram. -As the algorithm is not convex, its output depends on the initialization and +As the algorithm is not convex, its output depends on the initialization and is only a local minimum of the objective function. -Initialization can be either given as an integer (in which case the i-th -diagram of the list is used as initial estimate) or as a diagram. -If None, it will randomly select one of the diagrams of the list +Initialization can be either given as an integer (in which case the i-th +diagram of the list is used as initial estimate) or as a diagram. +If None, it will randomly select one of the diagrams of the list as initial estimate. -Note that persistence diagrams must be submitted as +Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. @@ -152,7 +152,7 @@ Note that persistence diagrams must be submitted as pdiagset = [dg1, dg2, dg3, dg4] bary = lagrangian_barycenter(pdiagset=pdiagset,init=3) - message = "Wasserstein barycenter estimated:" + message = "Wasserstein barycenter estimated:" print(message) print(bary) diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index 99f29a1e..de7aea81 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -18,7 +18,7 @@ from gudhi.wasserstein import wasserstein_distance def _mean(x, m): ''' :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} - :param m: total amount of points taken into account, + :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal :returns: the weighted mean of x with (m-k) copies of the diagonal ''' @@ -33,14 +33,14 @@ def _mean(x, m): def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' - :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` - (`n` can variate), encoding a set of - persistence diagrams with only finite coordinates. - :param init: The initial value for barycenter estimate. - If ``None``, init is made on a random diagram from the dataset. - Otherwise, it can be an ``int`` + :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` + (`n` can variate), encoding a set of + persistence diagrams with only finite coordinates. + :param init: The initial value for barycenter estimate. + If ``None``, init is made on a random diagram from the dataset. + Otherwise, it can be an ``int`` (then initialization is made on ``pdiagset[init]``) - or a `(n x 2)` ``numpy.array`` enconding + or a `(n x 2)` ``numpy.array`` enconding a persistence diagram with `n` points. :type init: ``int``, or (n x 2) ``np.array`` :param verbose: if ``True``, returns additional information about the @@ -48,16 +48,16 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): :type verbose: boolean :returns: If not verbose (default), a ``numpy.array`` encoding the barycenter estimate of pdiagset - (local minimum of the energy function). + (local minimum of the energy function). If ``pdiagset`` is empty, returns ``None``. If verbose, returns a couple ``(Y, log)`` where ``Y`` is the barycenter estimate, and ``log`` is a ``dict`` that contains additional informations: - `"groupings"`, a list of list of pairs ``(i,j)``. - Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates + Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates that ``pdiagset[k][i]`` is matched to ``Y[j]`` - if ``i = -1`` or ``j = -1``, it means they + if ``i = -1`` or ``j = -1``, it means they represent the diagonal. - `"energy"`, ``float`` representing the Frechet energy value obtained. @@ -70,13 +70,13 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): if m == 0: print("Warning: computing barycenter of empty diag set. Returns None") return None - + # store the number of off-diagonal point for each of the X_i - nb_off_diag = np.array([len(X_i) for X_i in X]) + nb_off_diag = np.array([len(X_i) for X_i in X]) # Initialisation of barycenter if init is None: i0 = np.random.randint(m) # Index of first state for the barycenter - Y = X[i0].copy() + Y = X[i0].copy() else: if type(init)==int: Y = X[init].copy() @@ -90,8 +90,8 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): nb_iter += 1 K = len(Y) # current nb of points in Y (some might be on diagonal) G = np.full((K, m), -1, dtype=int) # will store for each j, the (index) - # point matched in each other diagram - #(might be the diagonal). + # point matched in each other diagram + #(might be the diagonal). # that is G[j, i] = k <=> y_j is matched to # x_k in the diagram i-th diagram X[i] updated_points = np.zeros((K, 2)) # will store the new positions of @@ -111,7 +111,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): else: # ...which is a diagonal point G[y_j, i] = -1 # -1 stands for the diagonal (mask) else: # We matched a diagonal point to x_i_j... - if x_i_j >= 0: # which is a off-diag point ! + if x_i_j >= 0: # which is a off-diag point ! # need to create new point in Y new_y = _mean(np.array([X[i][x_i_j]]), m) # Average this point with (m-1) copies of Delta @@ -123,19 +123,19 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] new_y_j = _mean(matched_points, m) if not np.array_equal(new_y_j, np.array([0,0])): - updated_points[j] = new_y_j + updated_points[j] = new_y_j else: # this points is no longer of any use. to_delete.append(j) # we remove the point to be deleted now. - updated_points = np.delete(updated_points, to_delete, axis=0) + updated_points = np.delete(updated_points, to_delete, axis=0) # we cannot converge if there have been new created points. - if new_created_points: + if new_created_points: Y = np.concatenate((updated_points, new_created_points)) else: # Step 3 : we check convergence if np.array_equal(updated_points, Y): - converged = True + converged = True Y = updated_points diff --git a/src/python/gudhi/wasserstein/wasserstein.py b/src/python/gudhi/wasserstein/wasserstein.py index e1233eec..35315939 100644 --- a/src/python/gudhi/wasserstein/wasserstein.py +++ b/src/python/gudhi/wasserstein/wasserstein.py @@ -30,9 +30,9 @@ def _build_dist_matrix(X, Y, order=2., internal_p=2.): :param Y: (m x 2) numpy.array encoding the second diagram. :param order: exponent for the Wasserstein metric. :param internal_p: Ground metric (i.e. norm L^p). - :returns: (n+1) x (m+1) np.array encoding the cost matrix C. - For 0 <= i < n, 0 <= j < m, C[i,j] encodes the distance between X[i] and Y[j], - while C[i, m] (resp. C[n, j]) encodes the distance (to the p) between X[i] (resp Y[j]) + :returns: (n+1) x (m+1) np.array encoding the cost matrix C. + For 0 <= i < n, 0 <= j < m, C[i,j] encodes the distance between X[i] and Y[j], + while C[i, m] (resp. C[n, j]) encodes the distance (to the p) between X[i] (resp Y[j]) and its orthogonal projection onto the diagonal. note also that C[n, m] = 0 (it costs nothing to move from the diagonal to the diagonal). ''' @@ -59,7 +59,7 @@ def _perstot(X, order, internal_p): :param X: (n x 2) numpy.array (points of a given diagram). :param order: exponent for Wasserstein. Default value is 2. :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); Default value is 2 (Euclidean norm). - :returns: float, the total persistence of the diagram (that is, its distance to the empty diagram). + :returns: float, the total persistence of the diagram (that is, its distance to the empty diagram). ''' Xdiag = _proj_on_diag(X) return (np.sum(np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order))**(1./order) @@ -67,16 +67,16 @@ def _perstot(X, order, internal_p): def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): ''' - :param X: (n x 2) numpy.array encoding the (finite points of the) first diagram. Must not contain essential points + :param X: (n x 2) numpy.array encoding the (finite points of the) first diagram. Must not contain essential points (i.e. with infinite coordinate). :param Y: (m x 2) numpy.array encoding the second diagram. :param matching: if True, computes and returns the optimal matching between X and Y, encoded as a (n x 2) np.array [...[i,j]...], meaning the i-th point in X is matched to the j-th point in Y, with the convention (-1) represents the diagonal. :param order: exponent for Wasserstein; Default value is 2. - :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); + :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); Default value is 2 (Euclidean norm). - :returns: the Wasserstein distance of order q (1 <= q < infinity) between persistence diagrams with + :returns: the Wasserstein distance of order q (1 <= q < infinity) between persistence diagrams with respect to the internal_p-norm as ground metric. If matching is set to True, also returns the optimal matching between X and Y. ''' diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index f686aef5..f68c748e 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -17,7 +17,7 @@ __license__ = "MIT" def test_lagrangian_barycenter(): - + dg1 = np.array([[0.2, 0.5]]) dg2 = np.array([[0.2, 0.7]]) dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) @@ -28,12 +28,12 @@ def test_lagrangian_barycenter(): dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) dg8 = np.array([[0., 4.], [4, 8]]) - + # error crit. eps = 1e-7 - assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < eps + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < eps assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.empty(shape=(0,2))) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < eps Y, log = lagrangian_barycenter(pdiagset=[dg4, dg8], verbose=True) diff --git a/src/python/test/test_wasserstein_distance.py b/src/python/test/test_wasserstein_distance.py index 0d70e11a..7e0d0f5f 100755 --- a/src/python/test/test_wasserstein_distance.py +++ b/src/python/test/test_wasserstein_distance.py @@ -70,7 +70,7 @@ def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True, test_mat assert np.array_equal(match , [[0, -1], [1, -1]]) match = wasserstein_distance(diag1, diag2, matching=True, internal_p=2., order=2.)[1] assert np.array_equal(match, [[0, 0], [1, 1], [2, -1]]) - + def hera_wrap(delta): -- cgit v1.2.3 From f47b9607519b5c8c89bbe40341cf5bcc1382f5ef Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Sun, 26 Apr 2020 10:08:29 +0200 Subject: Fix barycenter sphinx warnings --- src/python/doc/alpha_complex_user.rst | 2 +- src/python/gudhi/wasserstein/barycenter.py | 53 +++++++++++++----------------- 2 files changed, 24 insertions(+), 31 deletions(-) (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/doc/alpha_complex_user.rst b/src/python/doc/alpha_complex_user.rst index 60a2f94e..02d85389 100644 --- a/src/python/doc/alpha_complex_user.rst +++ b/src/python/doc/alpha_complex_user.rst @@ -94,7 +94,7 @@ Filtration value computation algorithm for i : dimension → 0 do for all σ of dimension i if filtration(σ) is NaN then - filtration(σ)=α2(σ) + filtration(σ)=α²(σ) end if for all τ face of σ do // propagate alpha filtration value if filtration(τ) is not NaN then diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index de7aea81..1cf8edb3 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -18,8 +18,7 @@ from gudhi.wasserstein import wasserstein_distance def _mean(x, m): ''' :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} - :param m: total amount of points taken into account, - that is we have (m-k) copies of diagonal + :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal :returns: the weighted mean of x with (m-k) copies of the diagonal ''' k = len(x) @@ -33,37 +32,31 @@ def _mean(x, m): def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' - :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` - (`n` can variate), encoding a set of - persistence diagrams with only finite coordinates. + :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` (`n` can variate), encoding a set of persistence + diagrams with only finite coordinates. :param init: The initial value for barycenter estimate. - If ``None``, init is made on a random diagram from the dataset. - Otherwise, it can be an ``int`` - (then initialization is made on ``pdiagset[init]``) - or a `(n x 2)` ``numpy.array`` enconding - a persistence diagram with `n` points. + If ``None``, init is made on a random diagram from the dataset. + Otherwise, it can be an ``int`` (then initialization is made on ``pdiagset[init]``) + or a `(n x 2)` ``numpy.array`` enconding a persistence diagram with `n` points. :type init: ``int``, or (n x 2) ``np.array`` - :param verbose: if ``True``, returns additional information about the - barycenter. + :param verbose: if ``True``, returns additional information about the barycenter. :type verbose: boolean - :returns: If not verbose (default), a ``numpy.array`` encoding - the barycenter estimate of pdiagset - (local minimum of the energy function). - If ``pdiagset`` is empty, returns ``None``. - If verbose, returns a couple ``(Y, log)`` - where ``Y`` is the barycenter estimate, - and ``log`` is a ``dict`` that contains additional informations: - - - `"groupings"`, a list of list of pairs ``(i,j)``. - Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates - that ``pdiagset[k][i]`` is matched to ``Y[j]`` - if ``i = -1`` or ``j = -1``, it means they - represent the diagonal. - - - `"energy"`, ``float`` representing the Frechet energy value obtained. - It is the mean of squared distances of observations to the output. - - - `"nb_iter"`, ``int`` number of iterations performed before convergence of the algorithm. + :returns: If not verbose (default), a ``numpy.array`` encoding the barycenter estimate of pdiagset + (local minimum of the energy function). + If ``pdiagset`` is empty, returns ``None``. + If verbose, returns a couple ``(Y, log)`` where ``Y`` is the barycenter estimate, + and ``log`` is a ``dict`` that contains additional informations: + + - `"groupings"`, a list of list of pairs ``(i,j)``. + + Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates that ``pdiagset[k][i]`` is matched to ``Y[j]`` + if ``i = -1`` or ``j = -1``, it means they represent the diagonal. + + - `"energy"`, ``float`` representing the Frechet energy value obtained. + + It is the mean of squared distances of observations to the output. + + - `"nb_iter"`, ``int`` number of iterations performed before convergence of the algorithm. ''' X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging -- cgit v1.2.3 From 627772e4c5bc7038b0814182dbb918b08356c892 Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau <10407034+VincentRouvreau@users.noreply.github.com> Date: Mon, 11 May 2020 08:42:40 +0200 Subject: Fixed by @tlacombe MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Théo Lacombe --- src/python/gudhi/wasserstein/barycenter.py | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index 1cf8edb3..7eeeae7a 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -52,9 +52,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates that ``pdiagset[k][i]`` is matched to ``Y[j]`` if ``i = -1`` or ``j = -1``, it means they represent the diagonal. - - `"energy"`, ``float`` representing the Frechet energy value obtained. - - It is the mean of squared distances of observations to the output. + - `"energy"`, ``float`` representing the Frechet energy value obtained. It is the mean of squared distances of observations to the output. - `"nb_iter"`, ``int`` number of iterations performed before convergence of the algorithm. ''' @@ -149,4 +147,3 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): return Y, log else: return Y - -- cgit v1.2.3 From 779e4c4e8225e279ef8322988d4d06a6c2e06529 Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau <10407034+VincentRouvreau@users.noreply.github.com> Date: Mon, 11 May 2020 08:43:06 +0200 Subject: Fixed by @tlacombe MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Théo Lacombe --- src/python/gudhi/wasserstein/barycenter.py | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'src/python/gudhi/wasserstein/barycenter.py') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index 7eeeae7a..d67bcde7 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -47,10 +47,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): If verbose, returns a couple ``(Y, log)`` where ``Y`` is the barycenter estimate, and ``log`` is a ``dict`` that contains additional informations: - - `"groupings"`, a list of list of pairs ``(i,j)``. - - Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates that ``pdiagset[k][i]`` is matched to ``Y[j]`` - if ``i = -1`` or ``j = -1``, it means they represent the diagonal. + - `"groupings"`, a list of list of pairs ``(i,j)``. Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates that `pdiagset[k][i]`` is matched to ``Y[j]`` if ``i = -1`` or ``j = -1``, it means they represent the diagonal. - `"energy"`, ``float`` representing the Frechet energy value obtained. It is the mean of squared distances of observations to the output. -- cgit v1.2.3