diff options
author | Vivien Seguy <vivienseguy@Viviens-MacBook-Pro.local> | 2018-07-06 01:58:47 +0900 |
---|---|---|
committer | Vivien Seguy <vivienseguy@Viviens-MacBook-Pro.local> | 2018-07-06 01:58:47 +0900 |
commit | 2c7b98009f33e278a2e7e95a035c6a6231bec44e (patch) | |
tree | 9c5b5730ec159f9cbb832bc1bf9d221092cbb14b | |
parent | e39f04a9465bd9f1447423eb2a592cc9356589a9 (diff) |
add free support barycenter algorithm
-rw-r--r-- | README.md | 3 | ||||
-rw-r--r-- | examples/plot_free_support_barycenter.py | 35 | ||||
-rw-r--r-- | ot/lp/cvx.py | 22 |
3 files changed, 30 insertions, 30 deletions
@@ -17,6 +17,7 @@ It provides the following solvers: * Entropic regularization OT solver with Sinkhorn Knopp Algorithm [2] and stabilized version [9][10] with optional GPU implementation (requires cudamat). * Smooth optimal transport solvers (dual and semi-dual) for KL and squared L2 regularizations [17]. * Non regularized Wasserstein barycenters [16] with LP solver (only small scale). +* Non regularized free support Wasserstein barycenters [20]. * Bregman projections for Wasserstein barycenter [3] and unmixing [4]. * Optimal transport for domain adaptation with group lasso regularization [5] * Conditional gradient [6] and Generalized conditional gradient for regularized OT [7]. @@ -225,3 +226,5 @@ You can also post bug reports and feature requests in Github issues. Make sure t [18] Genevay, A., Cuturi, M., Peyré, G. & Bach, F. (2016) [Stochastic Optimization for Large-scale Optimal Transport](arXiv preprint arxiv:1605.08527). Advances in Neural Information Processing Systems (2016). [19] Seguy, V., Bhushan Damodaran, B., Flamary, R., Courty, N., Rolet, A.& Blondel, M. [Large-scale Optimal Transport and Mapping Estimation](https://arxiv.org/pdf/1711.02283.pdf). International Conference on Learning Representation (2018) + +[20] Cuturi, M. and Doucet, A. (2014) [Fast Computation of Wasserstein Barycenters](http://proceedings.mlr.press/v32/cuturi14.html). International Conference in Machine Learning
\ No newline at end of file diff --git a/examples/plot_free_support_barycenter.py b/examples/plot_free_support_barycenter.py index 61671cf..42e22fc 100644 --- a/examples/plot_free_support_barycenter.py +++ b/examples/plot_free_support_barycenter.py @@ -21,7 +21,7 @@ import ot.plot # Generate data # ------------- #%% parameters and data generation -N = 6 +N = 3 d = 2 measures_locations = [] measures_weights = [] @@ -33,24 +33,25 @@ for i in range(N): mu = np.random.normal(0., 4., (d,)) A = np.random.rand(d, d) - cov = np.dot(A,A.transpose()) + cov = np.dot(A, A.transpose()) - xs = ot.datasets.make_2D_samples_gauss(n, mu, cov) - b = np.random.uniform(0., 1., (n,)) - b = b/np.sum(b) + x_i = ot.datasets.make_2D_samples_gauss(n, mu, cov) + b_i = np.random.uniform(0., 1., (n,)) + b_i = b_i / np.sum(b_i) - measures_locations.append(xs) - measures_weights.append(b) - -k = 10 -X_init = np.random.normal(0., 1., (k,d)) -b_init = np.ones((k,)) / k + measures_locations.append(x_i) + measures_weights.append(b_i) ############################################################################## # Compute free support barycenter # ------------- -X = ot.lp.cvx.free_support_barycenter(measures_locations, measures_weights, X_init, b_init) + +k = 10 +X_init = np.random.normal(0., 1., (k, d)) +b = np.ones((k,)) / k + +X = ot.lp.cvx.free_support_barycenter(measures_locations, measures_weights, X_init, b) ############################################################################## @@ -60,10 +61,10 @@ X = ot.lp.cvx.free_support_barycenter(measures_locations, measures_weights, X_in #%% plot samples pl.figure(1) -for (xs, b) in zip(measures_locations, measures_weights): - color = np.random.randint(low=1, high=10*N) - pl.scatter(xs[:, 0], xs[:, 1], s=b*1000, label='input measure') -pl.scatter(X[:, 0], X[:, 1], s=b_init*1000, c='black' , marker='^', label='2-Wasserstein barycenter') +for (x_i, b_i) in zip(measures_locations, measures_weights): + color = np.random.randint(low=1, high=10 * N) + pl.scatter(x_i[:, 0], x_i[:, 1], s=b * 1000, label='input measure') +pl.scatter(X[:, 0], X[:, 1], s=b * 1000, c='black', marker='^', label='2-Wasserstein barycenter') pl.title('Data measures and their barycenter') pl.legend(loc=0) -pl.show()
\ No newline at end of file +pl.show() diff --git a/ot/lp/cvx.py b/ot/lp/cvx.py index b74960f..c097f58 100644 --- a/ot/lp/cvx.py +++ b/ot/lp/cvx.py @@ -147,10 +147,7 @@ def barycenter(A, M, weights=None, verbose=False, log=False, solver='interior-po return b - - -def free_support_barycenter(measures_locations, measures_weights, X_init, b_init, weights=None, numItermax=100, stopThr=1e-6, verbose=False): - +def free_support_barycenter(measures_locations, measures_weights, X_init, b, weights=None, numItermax=100, stopThr=1e-6, verbose=False): """ Solves the free support (locations of the barycenters are optimized, not the weights) Wasserstein barycenter problem (i.e. the weighted Frechet mean for the 2-Wasserstein distance) @@ -168,7 +165,7 @@ def free_support_barycenter(measures_locations, measures_weights, X_init, b_init X_init : (k,d) np.ndarray Initialization of the support locations (on k atoms) of the barycenter - b_init : (k,) np.ndarray + b : (k,) np.ndarray Initialization of the weights of the barycenter (non-negatives, sum to 1) weights : (k,) np.ndarray Initialization of the coefficients of the barycenter (non-negatives, sum to 1) @@ -199,27 +196,27 @@ def free_support_barycenter(measures_locations, measures_weights, X_init, b_init iter_count = 0 d = X_init.shape[1] - k = b_init.size + k = b.size N = len(measures_locations) if not weights: - weights = np.ones((N,))/N + weights = np.ones((N,)) / N X = X_init - displacement_square_norm = stopThr+1. + displacement_square_norm = stopThr + 1. - while ( displacement_square_norm > stopThr and iter_count < numItermax ): + while (displacement_square_norm > stopThr and iter_count < numItermax): T_sum = np.zeros((k, d)) for (measure_locations_i, measure_weights_i, weight_i) in zip(measures_locations, measures_weights, weights.tolist()): M_i = ot.dist(X, measure_locations_i) - T_i = ot.emd(b_init, measure_weights_i, M_i) - T_sum = T_sum + weight_i*np.reshape(1. / b_init, (-1, 1)) * np.matmul(T_i, measure_locations_i) + T_i = ot.emd(b, measure_weights_i, M_i) + T_sum = T_sum + weight_i * np.reshape(1. / b, (-1, 1)) * np.matmul(T_i, measure_locations_i) - displacement_square_norm = np.sum(np.square(X-T_sum)) + displacement_square_norm = np.sum(np.square(X - T_sum)) X = T_sum if verbose: @@ -228,4 +225,3 @@ def free_support_barycenter(measures_locations, measures_weights, X_init, b_init iter_count += 1 return X - |