diff options
| -rw-r--r-- | examples/plot_stochastic.py | 135 | ||||
| -rw-r--r-- | ot/__init__.py | 2 | ||||
| -rw-r--r-- | ot/stochastic.py | 415 | ||||
| -rw-r--r-- | test/test_stochastic.py | 115 |
4 files changed, 667 insertions, 0 deletions
diff --git a/examples/plot_stochastic.py b/examples/plot_stochastic.py new file mode 100644 index 0000000..9071ddb --- /dev/null +++ b/examples/plot_stochastic.py @@ -0,0 +1,135 @@ +""" +========================== +Stochastic examples +========================== + +This example is designed to show how to use the stochatic optimization +algorithms for descrete and semicontinous measures from the POT library. + +""" + +# Author: Kilian Fatras <kilian.fatras@gmail.com> +# +# License: MIT License + +import matplotlib.pylab as pl +import numpy as np +import ot + + +############################################################################# +# COMPUTE TRANSPORTATION MATRIX +############################################################################# + +############################################################################# +# DISCRETE CASE +# Sample two discrete measures for the discrete case +# --------------------------------------------- +# +# Define 2 discrete measures a and b, the points where are defined the source +# and the target measures and finally the cost matrix c. + +n_source = 7 +n_target = 4 +reg = 1 +numItermax = 10000 +lr = 0.1 + +a = ot.utils.unif(n_source) +b = ot.utils.unif(n_target) + +rng = np.random.RandomState(0) +X_source = rng.randn(n_source, 2) +Y_target = rng.randn(n_target, 2) +M = ot.dist(X_source, Y_target) + +############################################################################# +# +# Call the "SAG" method to find the transportation matrix in the discrete case +# --------------------------------------------- +# +# Define the method "SAG", call ot.transportation_matrix_entropic and plot the +# results. + +method = "SAG" +sag_pi = ot.stochastic.transportation_matrix_entropic(a, b, M, reg, method, + numItermax, lr) +print(sag_pi) + +############################################################################# +# SEMICONTINOUS CASE +# Sample one general measure a, one discrete measures b for the semicontinous +# case +# --------------------------------------------- +# +# Define one general measure a, one discrete measures b, the points where +# are defined the source and the target measures and finally the cost matrix c. + +n_source = 7 +n_target = 4 +reg = 1 +numItermax = 500000 +lr = 1 + +a = ot.utils.unif(n_source) +b = ot.utils.unif(n_target) + +rng = np.random.RandomState(0) +X_source = rng.randn(n_source, 2) +Y_target = rng.randn(n_target, 2) +M = ot.dist(X_source, Y_target) + +############################################################################# +# +# Call the "ASGD" method to find the transportation matrix in the semicontinous +# case +# --------------------------------------------- +# +# Define the method "ASGD", call ot.transportation_matrix_entropic and plot the +# results. + +method = "ASGD" +asgd_pi = ot.stochastic.transportation_matrix_entropic(a, b, M, reg, method, + numItermax, lr) +print(asgd_pi) + +############################################################################# +# +# Compare the results with the Sinkhorn algorithm +# --------------------------------------------- +# +# Call the Sinkhorn algorithm from POT + +sinkhorn_pi = ot.sinkhorn(a, b, M, 1) +print(sinkhorn_pi) + + +############################################################################## +# PLOT TRANSPORTATION MATRIX +############################################################################## + +############################################################################## +# Plot SAG results +# ---------------- + +pl.figure(4, figsize=(5, 5)) +ot.plot.plot1D_mat(a, b, sag_pi, 'OT matrix SAG') +pl.show() + + +############################################################################## +# Plot ASGD results +# ----------------- + +pl.figure(4, figsize=(5, 5)) +ot.plot.plot1D_mat(a, b, asgd_pi, 'OT matrix ASGD') +pl.show() + + +############################################################################## +# Plot Sinkhorn results +# --------------------- + +pl.figure(4, figsize=(5, 5)) +ot.plot.plot1D_mat(a, b, sinkhorn_pi, 'OT matrix Sinkhorn') +pl.show() diff --git a/ot/__init__.py b/ot/__init__.py index 1500e59..1dde390 100644 --- a/ot/__init__.py +++ b/ot/__init__.py @@ -18,6 +18,8 @@ from . import utils from . import datasets from . import da from . import gromov +from . import smooth +from . import stochastic # OT functions from .lp import emd, emd2 diff --git a/ot/stochastic.py b/ot/stochastic.py new file mode 100644 index 0000000..541f456 --- /dev/null +++ b/ot/stochastic.py @@ -0,0 +1,415 @@ +# Author: Kilian Fatras <kilian.fatras@gmail.com> +# +# License: MIT License + +import numpy as np + + +def coordinate_gradient(b, M, reg, v, i): + ''' + Compute the coordinate gradient update for regularized discrete + distributions for (i, :) + + The function computes the gradient of the semi dual problem: + .. math:: + \W_varepsilon(a, b) = \max_\v \sum_i (\sum_j v_j * b_j + - \reg log(\sum_j exp((v_j - M_{i,j})/reg) * b_j)) * a_i + + where : + - M is the (ns,nt) metric cost matrix + - v is a dual variable in R^J + - reg is the regularization term + - a and b are source and target weights (sum to 1) + + The algorithm used for solving the problem is the ASGD & SAG algorithms + as proposed in [18]_ [alg.1 & alg.2] + + + Parameters + ---------- + + b : np.ndarray(nt,), + target measure + M : np.ndarray(ns, nt), + cost matrix + reg : float nu, + Regularization term > 0 + v : np.ndarray(nt,), + optimization vector + i : number int, + picked number i + + Returns + ------- + + coordinate gradient : np.ndarray(nt,) + + Examples + -------- + + >>> n_source = 7 + >>> n_target = 4 + >>> reg = 1 + >>> numItermax = 300000 + >>> lr = 1 + >>> a = ot.utils.unif(n_source) + >>> b = ot.utils.unif(n_target) + >>> rng = np.random.RandomState(0) + >>> X_source = rng.randn(n_source, 2) + >>> Y_target = rng.randn(n_target, 2) + >>> M = ot.dist(X_source, Y_target) + >>> method = "ASGD" + >>> asgd_pi = stochastic.transportation_matrix_entropic(a, b, M, reg, + method, numItermax, + lr) + >>> print(asgd_pi) + + References + ---------- + + [Genevay et al., 2016] : + Stochastic Optimization for Large-scale Optimal Transport, + Advances in Neural Information Processing Systems (2016), + arXiv preprint arxiv:1605.08527. + + ''' + + r = M[i, :] - v + exp_v = np.exp(-r / reg) * b + khi = exp_v / (np.sum(exp_v)) + return b - khi + + +def sag_entropic_transport(a, b, M, reg, numItermax=10000, lr=0.1): + ''' + Compute the SAG algorithm to solve the regularized discrete measures + optimal transport max problem + + The function solves the following optimization problem: + .. math:: + \gamma = arg\min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma) + s.t. \gamma 1 = a + \gamma^T 1= b + \gamma \geq 0 + where : + - M is the (ns,nt) metric cost matrix + - :math:`\Omega` is the entropic regularization term + :math:`\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})` + - a and b are source and target weights (sum to 1) + The algorithm used for solving the problem is the SAG algorithm + as proposed in [18]_ [alg.1] + + + Parameters + ---------- + + a : np.ndarray(ns,), + source measure + b : np.ndarray(nt,), + target measure + M : np.ndarray(ns, nt), + cost matrix + reg : float number, + Regularization term > 0 + numItermax : int number + number of iteration + lr : float number + learning rate + + Returns + ------- + + v : np.ndarray(nt,) + dual variable + + Examples + -------- + + >>> n_source = 7 + >>> n_target = 4 + >>> reg = 1 + >>> numItermax = 300000 + >>> lr = 1 + >>> a = ot.utils.unif(n_source) + >>> b = ot.utils.unif(n_target) + >>> rng = np.random.RandomState(0) + >>> X_source = rng.randn(n_source, 2) + >>> Y_target = rng.randn(n_target, 2) + >>> M = ot.dist(X_source, Y_target) + >>> method = "SAG" + >>> sag_pi = stochastic.transportation_matrix_entropic(a, b, M, reg, + method, numItermax, + lr) + >>> print(asgd_pi) + + References + ---------- + + [Genevay et al., 2016] : + Stochastic Optimization for Large-scale Optimal Transport, + Advances in Neural Information Processing Systems (2016), + arXiv preprint arxiv:1605.08527. + ''' + + n_source = np.shape(M)[0] + n_target = np.shape(M)[1] + v = np.zeros(n_target) + stored_gradient = np.zeros((n_source, n_target)) + sum_stored_gradient = np.zeros(n_target) + for _ in range(numItermax): + i = np.random.randint(n_source) + cur_coord_grad = a[i] * coordinate_gradient(b, M, reg, v, i) + sum_stored_gradient += (cur_coord_grad - stored_gradient[i]) + stored_gradient[i] = cur_coord_grad + v += lr * (1. / n_source) * sum_stored_gradient + return v + + +def averaged_sgd_entropic_transport(b, M, reg, numItermax=300000, lr=1): + ''' + Compute the ASGD algorithm to solve the regularized semi contibous measures + optimal transport max problem + + The function solves the following optimization problem: + .. math:: + \gamma = arg\min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma) + s.t. \gamma 1 = a + \gamma^T 1= b + \gamma \geq 0 + where : + - M is the (ns,nt) metric cost matrix + - :math:`\Omega` is the entropic regularization term + :math:`\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})` + - a and b are source and target weights (sum to 1) + The algorithm used for solving the problem is the ASGD algorithm + as proposed in [18]_ [alg.2] + + + Parameters + ---------- + + b : np.ndarray(nt,), + target measure + M : np.ndarray(ns, nt), + cost matrix + reg : float number, + Regularization term > 0 + numItermax : int number + number of iteration + lr : float number + learning rate + + + Returns + ------- + + ave_v : np.ndarray(nt,) + optimization vector + + Examples + -------- + + >>> n_source = 7 + >>> n_target = 4 + >>> reg = 1 + >>> numItermax = 300000 + >>> lr = 1 + >>> a = ot.utils.unif(n_source) + >>> b = ot.utils.unif(n_target) + >>> rng = np.random.RandomState(0) + >>> X_source = rng.randn(n_source, 2) + >>> Y_target = rng.randn(n_target, 2) + >>> M = ot.dist(X_source, Y_target) + >>> method = "ASGD" + >>> asgd_pi = stochastic.transportation_matrix_entropic(a, b, M, reg, + method, numItermax, + lr) + >>> print(asgd_pi) + + References + ---------- + + [Genevay et al., 2016] : + Stochastic Optimization for Large-scale Optimal Transport, + Advances in Neural Information Processing Systems (2016), + arXiv preprint arxiv:1605.08527. + ''' + + n_source = np.shape(M)[0] + n_target = np.shape(M)[1] + cur_v = np.zeros(n_target) + ave_v = np.zeros(n_target) + for cur_iter in range(numItermax): + k = cur_iter + 1 + i = np.random.randint(n_source) + cur_coord_grad = coordinate_gradient(b, M, reg, cur_v, i) + cur_v += (lr / np.sqrt(k)) * cur_coord_grad + ave_v = (1. / k) * cur_v + (1 - 1. / k) * ave_v + return ave_v + + +def c_transform_entropic(b, M, reg, v): + ''' + The goal is to recover u from the c-transform. + + The function computes the c_transform of a dual variable from the other + dual variable: + .. math:: + u = v^{c,reg} = -reg \sum_j exp((v - M)/reg) b_j + + where : + - M is the (ns,nt) metric cost matrix + - u, v are dual variables in R^IxR^J + - reg is the regularization term + + It is used to recover an optimal u from optimal v solving the semi dual + problem, see Proposition 2.1 of [18]_ + + + Parameters + ---------- + + b : np.ndarray(nt,) + target measure + M : np.ndarray(ns, nt) + cost matrix + reg : float + regularization term > 0 + v : np.ndarray(nt,) + dual variable + + Returns + ------- + + u : np.ndarray(ns,) + + Examples + -------- + + >>> n_source = 7 + >>> n_target = 4 + >>> reg = 1 + >>> numItermax = 300000 + >>> lr = 1 + >>> a = ot.utils.unif(n_source) + >>> b = ot.utils.unif(n_target) + >>> rng = np.random.RandomState(0) + >>> X_source = rng.randn(n_source, 2) + >>> Y_target = rng.randn(n_target, 2) + >>> M = ot.dist(X_source, Y_target) + >>> method = "ASGD" + >>> asgd_pi = stochastic.transportation_matrix_entropic(a, b, M, reg, + method, numItermax, + lr) + >>> print(asgd_pi) + + References + ---------- + + [Genevay et al., 2016] : + Stochastic Optimization for Large-scale Optimal Transport, + Advances in Neural Information Processing Systems (2016), + arXiv preprint arxiv:1605.08527. + ''' + + n_source = np.shape(M)[0] + n_target = np.shape(M)[1] + u = np.zeros(n_source) + for i in range(n_source): + r = M[i, :] - v + exp_v = np.exp(-r / reg) * b + u[i] = - reg * np.log(np.sum(exp_v)) + return u + + +def transportation_matrix_entropic(a, b, M, reg, method, numItermax=10000, + lr=0.1): + ''' + Compute the transportation matrix to solve the regularized discrete + measures optimal transport max problem + + The function solves the following optimization problem: + .. math:: + \gamma = arg\min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma) + s.t. \gamma 1 = a + \gamma^T 1= b + \gamma \geq 0 + where : + - M is the (ns,nt) metric cost matrix + - :math:`\Omega` is the entropic regularization term + :math:`\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})` + - a and b are source and target weights (sum to 1) + The algorithm used for solving the problem is the SAG or ASGD algorithms + as proposed in [18]_ + + + Parameters + ---------- + + a : np.ndarray(ns,), + source measure + b : np.ndarray(nt,), + target measure + M : np.ndarray(ns, nt), + cost matrix + reg : float number, + Regularization term > 0 + methode : str, + used method (SAG or ASGD) + numItermax : int number + number of iteration + lr : float number + learning rate + n_source : int number + size of the source measure + n_target : int number + size of the target measure + + Returns + ------- + + pi : np.ndarray(ns, nt) + transportation matrix + + Examples + -------- + + >>> n_source = 7 + >>> n_target = 4 + >>> reg = 1 + >>> numItermax = 300000 + >>> lr = 1 + >>> a = ot.utils.unif(n_source) + >>> b = ot.utils.unif(n_target) + >>> rng = np.random.RandomState(0) + >>> X_source = rng.randn(n_source, 2) + >>> Y_target = rng.randn(n_target, 2) + >>> M = ot.dist(X_source, Y_target) + >>> method = "ASGD" + >>> asgd_pi = stochastic.transportation_matrix_entropic(a, b, M, reg, + method, numItermax, + lr) + >>> print(asgd_pi) + + References + ---------- + + [Genevay et al., 2016] : + Stochastic Optimization for Large-scale Optimal Transport, + Advances in Neural Information Processing Systems (2016), + arXiv preprint arxiv:1605.08527. + ''' + n_source = 7 + n_target = 4 + if method.lower() == "sag": + opt_v = sag_entropic_transport(a, b, M, reg, numItermax, lr) + elif method.lower() == "asgd": + opt_v = averaged_sgd_entropic_transport(b, M, reg, numItermax, lr) + else: + print("Please, select your method between SAG and ASGD") + return None + + opt_u = c_transform_entropic(b, M, reg, opt_v) + pi = (np.exp((opt_u[:, None] + opt_v[None, :] - M[:, :]) / reg) + * a[:, None] * b[None, :]) + return pi diff --git a/test/test_stochastic.py b/test/test_stochastic.py new file mode 100644 index 0000000..829f781 --- /dev/null +++ b/test/test_stochastic.py @@ -0,0 +1,115 @@ +""" +========================== +Stochastic test +========================== + +This example is designed to test the stochatic optimization algorithms module +for descrete and semicontinous measures from the POT library. + +""" + +# Author: Kilian Fatras <kilian.fatras@gmail.com> +# +# License: MIT License + +import numpy as np +import ot + +############################################################################# +# +# TEST SAG algorithm +# --------------------------------------------- +# 2 identical discrete measures u defined on the same space with a +# regularization term, a learning rate and a number of iteration + + +def test_stochastic_sag(): + # test sag + n = 15 + reg = 1 + numItermax = 300000 + rng = np.random.RandomState(0) + + x = rng.randn(n, 2) + u = ot.utils.unif(n) + + M = ot.dist(x, x) + + G = ot.stochastic.transportation_matrix_entropic(u, u, M, reg, "sag", + numItermax=numItermax) + + # check constratints + np.testing.assert_allclose( + u, G.sum(1), atol=1e-04) # cf convergence sag + np.testing.assert_allclose( + u, G.sum(0), atol=1e-04) # cf convergence sag + + +############################################################################# +# +# TEST ASGD algorithm +# --------------------------------------------- +# 2 identical discrete measures u defined on the same space with a +# regularization term, a learning rate and a number of iteration + +def test_stochastic_asgd(): + # test asgd + n = 15 + reg = 1 + numItermax = 300000 + lr = 1 + rng = np.random.RandomState(0) + + x = rng.randn(n, 2) + u = ot.utils.unif(n) + + M = ot.dist(x, x) + + G = ot.stochastic.transportation_matrix_entropic(u, u, M, reg, "asgd", + numItermax=numItermax, + lr=lr) + + # check constratints + np.testing.assert_allclose( + u, G.sum(1), atol=1e-03) # cf convergence asgd + np.testing.assert_allclose( + u, G.sum(0), atol=1e-03) # cf convergence asgd + + +############################################################################# +# +# TEST Convergence SAG and ASGD toward Sinkhorn's solution +# -------------------------------------------------------- +# 2 identical discrete measures u defined on the same space with a +# regularization term, a learning rate and a number of iteration + + +def test_sag_asgd_sinkhorn(): + # test all algorithms + n = 15 + reg = 1 + nb_iter = 300000 + lr = 1 + rng = np.random.RandomState(0) + + x = rng.randn(n, 2) + u = ot.utils.unif(n) + zero = np.zeros(n) + M = ot.dist(x, x) + + G_asgd = ot.stochastic.transportation_matrix_entropic(u, u, M, reg, "asgd", + numItermax=nb_iter, + lr=1) + G_sag = ot.stochastic.transportation_matrix_entropic(u, u, M, reg, "sag", + numItermax=nb_iter) + G_sinkhorn = ot.sinkhorn(u, u, M, reg) + + # check constratints + np.testing.assert_allclose( + zero, (G_sag - G_sinkhorn).sum(1), atol=1e-03) # cf convergence sag + np.testing.assert_allclose( + zero, (G_sag - G_sinkhorn).sum(0), atol=1e-03) # cf convergence sag + np.testing.assert_allclose( + zero, (G_asgd - G_sinkhorn).sum(1), atol=1e-03) # cf convergence asgd + np.testing.assert_allclose( + zero, (G_asgd - G_sinkhorn).sum(0), atol=1e-03) # cf convergence asgd |