From a54775103541ea37f54269de1ba1e1396a6d7b30 Mon Sep 17 00:00:00 2001 From: Rémi Flamary Date: Fri, 24 Apr 2020 17:32:57 +0200 Subject: exmaples in sections --- examples/gromov/plot_fgw.py | 175 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 175 insertions(+) create mode 100644 examples/gromov/plot_fgw.py (limited to 'examples/gromov/plot_fgw.py') diff --git a/examples/gromov/plot_fgw.py b/examples/gromov/plot_fgw.py new file mode 100644 index 0000000..73e486e --- /dev/null +++ b/examples/gromov/plot_fgw.py @@ -0,0 +1,175 @@ +# -*- coding: utf-8 -*- +""" +============================== +Plot Fused-gromov-Wasserstein +============================== + +This example illustrates the computation of FGW for 1D measures[18]. + +.. [18] Vayer Titouan, Chapel Laetitia, Flamary R{\'e}mi, Tavenard Romain + and Courty Nicolas + "Optimal Transport for structured data with application on graphs" + International Conference on Machine Learning (ICML). 2019. + +""" + +# Author: Titouan Vayer +# +# License: MIT License + +# sphinx_gallery_thumbnail_number = 3 + +import matplotlib.pyplot as pl +import numpy as np +import ot +from ot.gromov import gromov_wasserstein, fused_gromov_wasserstein + +############################################################################## +# Generate data +# --------- + +#%% parameters +# We create two 1D random measures +n = 20 # number of points in the first distribution +n2 = 30 # number of points in the second distribution +sig = 1 # std of first distribution +sig2 = 0.1 # std of second distribution + +np.random.seed(0) + +phi = np.arange(n)[:, None] +xs = phi + sig * np.random.randn(n, 1) +ys = np.vstack((np.ones((n // 2, 1)), 0 * np.ones((n // 2, 1)))) + sig2 * np.random.randn(n, 1) + +phi2 = np.arange(n2)[:, None] +xt = phi2 + sig * np.random.randn(n2, 1) +yt = np.vstack((np.ones((n2 // 2, 1)), 0 * np.ones((n2 // 2, 1)))) + sig2 * np.random.randn(n2, 1) +yt = yt[::-1, :] + +p = ot.unif(n) +q = ot.unif(n2) + +############################################################################## +# Plot data +# --------- + +#%% plot the distributions + +pl.close(10) +pl.figure(10, (7, 7)) + +pl.subplot(2, 1, 1) + +pl.scatter(ys, xs, c=phi, s=70) +pl.ylabel('Feature value a', fontsize=20) +pl.title('$\mu=\sum_i \delta_{x_i,a_i}$', fontsize=25, y=1) +pl.xticks(()) +pl.yticks(()) +pl.subplot(2, 1, 2) +pl.scatter(yt, xt, c=phi2, s=70) +pl.xlabel('coordinates x/y', fontsize=25) +pl.ylabel('Feature value b', fontsize=20) +pl.title('$\\nu=\sum_j \delta_{y_j,b_j}$', fontsize=25, y=1) +pl.yticks(()) +pl.tight_layout() +pl.show() + +############################################################################## +# Create structure matrices and across-feature distance matrix +# --------- + +#%% Structure matrices and across-features distance matrix +C1 = ot.dist(xs) +C2 = ot.dist(xt) +M = ot.dist(ys, yt) +w1 = ot.unif(C1.shape[0]) +w2 = ot.unif(C2.shape[0]) +Got = ot.emd([], [], M) + +############################################################################## +# Plot matrices +# --------- + +#%% +cmap = 'Reds' +pl.close(10) +pl.figure(10, (5, 5)) +fs = 15 +l_x = [0, 5, 10, 15] +l_y = [0, 5, 10, 15, 20, 25] +gs = pl.GridSpec(5, 5) + +ax1 = pl.subplot(gs[3:, :2]) + +pl.imshow(C1, cmap=cmap, interpolation='nearest') +pl.title("$C_1$", fontsize=fs) +pl.xlabel("$k$", fontsize=fs) +pl.ylabel("$i$", fontsize=fs) +pl.xticks(l_x) +pl.yticks(l_x) + +ax2 = pl.subplot(gs[:3, 2:]) + +pl.imshow(C2, cmap=cmap, interpolation='nearest') +pl.title("$C_2$", fontsize=fs) +pl.ylabel("$l$", fontsize=fs) +#pl.ylabel("$l$",fontsize=fs) +pl.xticks(()) +pl.yticks(l_y) +ax2.set_aspect('auto') + +ax3 = pl.subplot(gs[3:, 2:], sharex=ax2, sharey=ax1) +pl.imshow(M, cmap=cmap, interpolation='nearest') +pl.yticks(l_x) +pl.xticks(l_y) +pl.ylabel("$i$", fontsize=fs) +pl.title("$M_{AB}$", fontsize=fs) +pl.xlabel("$j$", fontsize=fs) +pl.tight_layout() +ax3.set_aspect('auto') +pl.show() + +############################################################################## +# Compute FGW/GW +# --------- + +#%% Computing FGW and GW +alpha = 1e-3 + +ot.tic() +Gwg, logw = fused_gromov_wasserstein(M, C1, C2, p, q, loss_fun='square_loss', alpha=alpha, verbose=True, log=True) +ot.toc() + +#%reload_ext WGW +Gg, log = gromov_wasserstein(C1, C2, p, q, loss_fun='square_loss', verbose=True, log=True) + +############################################################################## +# Visualize transport matrices +# --------- + +#%% visu OT matrix +cmap = 'Blues' +fs = 15 +pl.figure(2, (13, 5)) +pl.clf() +pl.subplot(1, 3, 1) +pl.imshow(Got, cmap=cmap, interpolation='nearest') +#pl.xlabel("$y$",fontsize=fs) +pl.ylabel("$i$", fontsize=fs) +pl.xticks(()) + +pl.title('Wasserstein ($M$ only)') + +pl.subplot(1, 3, 2) +pl.imshow(Gg, cmap=cmap, interpolation='nearest') +pl.title('Gromov ($C_1,C_2$ only)') +pl.xticks(()) +pl.subplot(1, 3, 3) +pl.imshow(Gwg, cmap=cmap, interpolation='nearest') +pl.title('FGW ($M+C_1,C_2$)') + +pl.xlabel("$j$", fontsize=fs) +pl.ylabel("$i$", fontsize=fs) + +pl.tight_layout() +pl.show() -- cgit v1.2.3 From e65c1f745cf2eacc6672727e7a3869efd8318768 Mon Sep 17 00:00:00 2001 From: Romain Tavenard Date: Mon, 4 May 2020 11:19:35 +0200 Subject: [WIP] Improved docs and changed scipy version (#163) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * Improved docs and changed scipy version * Fixed dependency bug in setup.py * dependencies set to minimal versions for tests * add requirements file * added minimal version build for scipy (testing 1.2) * bugfix in minimal deps build * (yet another) bugfix in minimal deps build * minimal deps now reflect README.md * minimal deps: no autograd nor pymanopt * refactored workflow names * minimal deps: no doctests * minimal deps: numpy 1.16 * trigger GH Actions on PR * better merge * re-add minimal-deps... * bugfix in yaml * enforce np>=1.16 * enforce scipy and cython versions too * requires / install_requires * requires / install_requires / requires * setup_requires Co-authored-by: Rémi Flamary --- .github/requirements_strict.txt | 7 ++ .github/workflows/build_tests.yml | 32 ++++++- README.md | 2 +- .../barycenters/plot_free_support_barycenter.py | 6 +- examples/domain-adaptation/plot_otda_d2.py | 2 +- examples/domain-adaptation/plot_otda_mapping.py | 4 +- .../plot_otda_mapping_colors_images.py | 1 + examples/gromov/plot_barycenter_fgw.py | 11 ++- examples/gromov/plot_fgw.py | 10 +- examples/plot_compute_emd.py | 4 +- examples/plot_optim_OTreg.py | 6 +- examples/plot_screenkhorn_1D.py | 7 +- examples/plot_stochastic.py | 101 +++++++++------------ requirements.txt | 2 +- setup.py | 3 +- 15 files changed, 110 insertions(+), 88 deletions(-) create mode 100644 .github/requirements_strict.txt (limited to 'examples/gromov/plot_fgw.py') diff --git a/.github/requirements_strict.txt b/.github/requirements_strict.txt new file mode 100644 index 0000000..d7539c5 --- /dev/null +++ b/.github/requirements_strict.txt @@ -0,0 +1,7 @@ +numpy==1.16.* +scipy==1.0.* +cython==0.23.* +matplotlib +cvxopt +scikit-learn +pytest diff --git a/.github/workflows/build_tests.yml b/.github/workflows/build_tests.yml index 652655f..41b08b3 100644 --- a/.github/workflows/build_tests.yml +++ b/.github/workflows/build_tests.yml @@ -2,9 +2,9 @@ name: build on: push: - branches: - - '**' + pull_request: + create: branches: - 'master' @@ -49,6 +49,34 @@ jobs: codecov + linux-minimal-deps: + + runs-on: ubuntu-latest + strategy: + max-parallel: 4 + matrix: + python-version: [3.6] + + steps: + - uses: actions/checkout@v1 + - name: Set up Python ${{ matrix.python-version }} + uses: actions/setup-python@v1 + with: + python-version: ${{ matrix.python-version }} + - name: Install dependencies + run: | + python -m pip install --upgrade pip + pip install -r .github/requirements_strict.txt + pip install pytest + pip install -U "sklearn" + - name: Install POT + run: | + pip install -e . + - name: Run tests + run: | + python -m pytest -v test/ ot/ --ignore ot/gpu/ + + macos: runs-on: macOS-latest strategy: diff --git a/README.md b/README.md index b9b8f45..5ee4cee 100644 --- a/README.md +++ b/README.md @@ -69,7 +69,7 @@ year={2017} The library has been tested on Linux, MacOSX and Windows. It requires a C++ compiler for building/installing the EMD solver and relies on the following Python modules: -- Numpy (>=1.11) +- Numpy (>=1.16) - Scipy (>=1.0) - Cython (>=0.23) - Matplotlib (>=1.5) diff --git a/examples/barycenters/plot_free_support_barycenter.py b/examples/barycenters/plot_free_support_barycenter.py index 64b89e4..27ddc8e 100644 --- a/examples/barycenters/plot_free_support_barycenter.py +++ b/examples/barycenters/plot_free_support_barycenter.py @@ -4,7 +4,7 @@ 2D free support Wasserstein barycenters of distributions ==================================================== -Illustration of 2D Wasserstein barycenters if discributions that are weighted +Illustration of 2D Wasserstein barycenters if distributions are weighted sum of diracs. """ @@ -21,7 +21,7 @@ import ot ############################################################################## # Generate data # ------------- -#%% parameters and data generation + N = 3 d = 2 measures_locations = [] @@ -46,7 +46,7 @@ for i in range(N): ############################################################################## # Compute free support barycenter -# ------------- +# ------------------------------- k = 10 # number of Diracs of the barycenter X_init = np.random.normal(0., 1., (k, d)) # initial Dirac locations diff --git a/examples/domain-adaptation/plot_otda_d2.py b/examples/domain-adaptation/plot_otda_d2.py index f49a570..d8b2a93 100644 --- a/examples/domain-adaptation/plot_otda_d2.py +++ b/examples/domain-adaptation/plot_otda_d2.py @@ -25,7 +25,7 @@ import ot import ot.plot ############################################################################## -# generate data +# Generate data # ------------- n_samples_source = 150 diff --git a/examples/domain-adaptation/plot_otda_mapping.py b/examples/domain-adaptation/plot_otda_mapping.py index ded2bdf..d21d3c9 100644 --- a/examples/domain-adaptation/plot_otda_mapping.py +++ b/examples/domain-adaptation/plot_otda_mapping.py @@ -9,8 +9,8 @@ time both the coupling transport and approximate the transport map with either a linear or a kernelized mapping as introduced in [8]. [8] M. Perrot, N. Courty, R. Flamary, A. Habrard, - "Mapping estimation for discrete optimal transport", - Neural Information Processing Systems (NIPS), 2016. +"Mapping estimation for discrete optimal transport", +Neural Information Processing Systems (NIPS), 2016. """ # Authors: Remi Flamary diff --git a/examples/domain-adaptation/plot_otda_mapping_colors_images.py b/examples/domain-adaptation/plot_otda_mapping_colors_images.py index 9d3a7c7..ee5c8b0 100644 --- a/examples/domain-adaptation/plot_otda_mapping_colors_images.py +++ b/examples/domain-adaptation/plot_otda_mapping_colors_images.py @@ -9,6 +9,7 @@ estimation [8]. [6] Ferradans, S., Papadakis, N., Peyre, G., & Aujol, J. F. (2014). Regularized discrete optimal transport. SIAM Journal on Imaging Sciences, 7(3), 1853-1882. + [8] M. Perrot, N. Courty, R. Flamary, A. Habrard, "Mapping estimation for discrete optimal transport", Neural Information Processing Systems (NIPS), 2016. diff --git a/examples/gromov/plot_barycenter_fgw.py b/examples/gromov/plot_barycenter_fgw.py index 77b0370..3f81765 100644 --- a/examples/gromov/plot_barycenter_fgw.py +++ b/examples/gromov/plot_barycenter_fgw.py @@ -4,14 +4,15 @@ Plot graphs' barycenter using FGW ================================= -This example illustrates the computation barycenter of labeled graphs using FGW +This example illustrates the computation barycenter of labeled graphs using +FGW [18]. Requires networkx >=2 -.. [18] Vayer Titouan, Chapel Laetitia, Flamary R{\'e}mi, Tavenard Romain - and Courty Nicolas - "Optimal Transport for structured data with application on graphs" - International Conference on Machine Learning (ICML). 2019. +[18] Vayer Titouan, Chapel Laetitia, Flamary Rémi, Tavenard Romain +and Courty Nicolas +"Optimal Transport for structured data with application on graphs" +International Conference on Machine Learning (ICML). 2019. """ diff --git a/examples/gromov/plot_fgw.py b/examples/gromov/plot_fgw.py index 73e486e..97fe619 100644 --- a/examples/gromov/plot_fgw.py +++ b/examples/gromov/plot_fgw.py @@ -4,12 +4,12 @@ Plot Fused-gromov-Wasserstein ============================== -This example illustrates the computation of FGW for 1D measures[18]. +This example illustrates the computation of FGW for 1D measures [18]. -.. [18] Vayer Titouan, Chapel Laetitia, Flamary R{\'e}mi, Tavenard Romain - and Courty Nicolas - "Optimal Transport for structured data with application on graphs" - International Conference on Machine Learning (ICML). 2019. +[18] Vayer Titouan, Chapel Laetitia, Flamary Rémi, Tavenard Romain +and Courty Nicolas +"Optimal Transport for structured data with application on graphs" +International Conference on Machine Learning (ICML). 2019. """ diff --git a/examples/plot_compute_emd.py b/examples/plot_compute_emd.py index 3340115..527a847 100644 --- a/examples/plot_compute_emd.py +++ b/examples/plot_compute_emd.py @@ -4,8 +4,8 @@ Plot multiple EMD ================= -Shows how to compute multiple EMD and Sinkhorn with two differnt -ground metrics and plot their values for diffeent distributions. +Shows how to compute multiple EMD and Sinkhorn with two different +ground metrics and plot their values for different distributions. """ diff --git a/examples/plot_optim_OTreg.py b/examples/plot_optim_OTreg.py index 51e2fdc..5eb15bd 100644 --- a/examples/plot_optim_OTreg.py +++ b/examples/plot_optim_OTreg.py @@ -6,7 +6,7 @@ Regularized OT with generic solver Illustrates the use of the generic solver for regularized OT with user-designed regularization term. It uses Conditional gradient as in [6] and -generalized Conditional Gradient as proposed in [5][7]. +generalized Conditional Gradient as proposed in [5,7]. [5] N. Courty; R. Flamary; D. Tuia; A. Rakotomamonjy, Optimal Transport for @@ -14,8 +14,8 @@ Domain Adaptation, in IEEE Transactions on Pattern Analysis and Machine Intelligence , vol.PP, no.99, pp.1-1. [6] Ferradans, S., Papadakis, N., Peyré, G., & Aujol, J. F. (2014). -Regularized discrete optimal transport. SIAM Journal on Imaging Sciences, -7(3), 1853-1882. +Regularized discrete optimal transport. SIAM Journal on Imaging +Sciences, 7(3), 1853-1882. [7] Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). Generalized conditional gradient: analysis of convergence and applications. diff --git a/examples/plot_screenkhorn_1D.py b/examples/plot_screenkhorn_1D.py index 840ead8..785642a 100644 --- a/examples/plot_screenkhorn_1D.py +++ b/examples/plot_screenkhorn_1D.py @@ -4,8 +4,11 @@ 1D Screened optimal transport =============================== -This example illustrates the computation of Screenkhorn: -Screening Sinkhorn Algorithm for Optimal transport. +This example illustrates the computation of Screenkhorn [26]. + +[26] Alaya M. Z., Bérar M., Gasso G., Rakotomamonjy A. (2019). +Screening Sinkhorn Algorithm for Regularized Optimal Transport, +Advances in Neural Information Processing Systems 33 (NeurIPS). """ # Author: Mokhtar Z. Alaya diff --git a/examples/plot_stochastic.py b/examples/plot_stochastic.py index 742f8d9..3a1ef31 100644 --- a/examples/plot_stochastic.py +++ b/examples/plot_stochastic.py @@ -1,10 +1,18 @@ """ -========================== +=================== Stochastic examples -========================== +=================== This example is designed to show how to use the stochatic optimization -algorithms for descrete and semicontinous measures from the POT library. +algorithms for discrete and semi-continuous measures from the POT library. + +[18] Genevay, A., Cuturi, M., Peyré, G. & Bach, F. +Stochastic Optimization for Large-scale Optimal Transport. +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. +International Conference on Learning Representation (2018) """ @@ -19,16 +27,14 @@ import ot.plot ############################################################################# -# COMPUTE TRANSPORTATION MATRIX FOR SEMI-DUAL PROBLEM -############################################################################# -############################################################################# -# DISCRETE CASE: +# Compute the Transportation Matrix for the Semi-Dual Problem +# ----------------------------------------------------------- # -# Sample two discrete measures for the discrete case -# --------------------------------------------- +# 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. +# Sample two discrete measures for the discrete case and compute their cost +# matrix c. n_source = 7 n_target = 4 @@ -44,12 +50,7 @@ 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.solve_semi_dual_entropic and plot the -# results. method = "SAG" sag_pi = ot.stochastic.solve_semi_dual_entropic(a, b, M, reg, method, @@ -57,14 +58,12 @@ sag_pi = ot.stochastic.solve_semi_dual_entropic(a, b, M, reg, method, print(sag_pi) ############################################################################# -# SEMICONTINOUS CASE: +# Semi-Continuous 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. +# case, the points where source and target measures are defined and compute the +# cost matrix. n_source = 7 n_target = 4 @@ -81,13 +80,8 @@ 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.solve_semi_dual_entropic and plot the -# results. +# case. method = "ASGD" asgd_pi, log_asgd = ot.stochastic.solve_semi_dual_entropic(a, b, M, reg, method, @@ -96,23 +90,17 @@ print(log_asgd['alpha'], log_asgd['beta']) print(asgd_pi) ############################################################################# -# # Compare the results with the Sinkhorn algorithm -# --------------------------------------------- -# -# Call the Sinkhorn algorithm from POT sinkhorn_pi = ot.sinkhorn(a, b, M, reg) print(sinkhorn_pi) ############################################################################## -# PLOT TRANSPORTATION MATRIX -############################################################################## - -############################################################################## -# Plot SAG results -# ---------------- +# Plot Transportation Matrices +# ```````````````````````````` +# +# For SAG pl.figure(4, figsize=(5, 5)) ot.plot.plot1D_mat(a, b, sag_pi, 'semi-dual : OT matrix SAG') @@ -120,8 +108,7 @@ pl.show() ############################################################################## -# Plot ASGD results -# ----------------- +# For ASGD pl.figure(4, figsize=(5, 5)) ot.plot.plot1D_mat(a, b, asgd_pi, 'semi-dual : OT matrix ASGD') @@ -129,8 +116,7 @@ pl.show() ############################################################################## -# Plot Sinkhorn results -# --------------------- +# For Sinkhorn pl.figure(4, figsize=(5, 5)) ot.plot.plot1D_mat(a, b, sinkhorn_pi, 'OT matrix Sinkhorn') @@ -138,17 +124,14 @@ pl.show() ############################################################################# -# COMPUTE TRANSPORTATION MATRIX FOR DUAL PROBLEM -############################################################################# -############################################################################# -# SEMICONTINOUS CASE: +# Compute the Transportation Matrix for the Dual Problem +# ------------------------------------------------------ # -# Sample one general measure a, one discrete measures b for the semicontinous -# case -# --------------------------------------------- +# Semi-continuous 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. +# Sample one general measure a, one discrete measures b for the semi-continuous +# case and compute the cost matrix c. n_source = 7 n_target = 4 @@ -169,10 +152,7 @@ M = ot.dist(X_source, Y_target) ############################################################################# # # Call the "SGD" dual method to find the transportation matrix in the -# semicontinous case -# --------------------------------------------- -# -# Call ot.solve_dual_entropic and plot the results. +# semi-continuous case sgd_dual_pi, log_sgd = ot.stochastic.solve_dual_entropic(a, b, M, reg, batch_size, numItermax, @@ -183,7 +163,7 @@ print(sgd_dual_pi) ############################################################################# # # Compare the results with the Sinkhorn algorithm -# --------------------------------------------- +# ``````````````````````````````````````````````` # # Call the Sinkhorn algorithm from POT @@ -191,8 +171,10 @@ sinkhorn_pi = ot.sinkhorn(a, b, M, reg) print(sinkhorn_pi) ############################################################################## -# Plot SGD results -# ----------------- +# Plot Transportation Matrices +# ```````````````````````````` +# +# For SGD pl.figure(4, figsize=(5, 5)) ot.plot.plot1D_mat(a, b, sgd_dual_pi, 'dual : OT matrix SGD') @@ -200,8 +182,7 @@ pl.show() ############################################################################## -# Plot Sinkhorn results -# --------------------- +# For Sinkhorn pl.figure(4, figsize=(5, 5)) ot.plot.plot1D_mat(a, b, sinkhorn_pi, 'OT matrix Sinkhorn') diff --git a/requirements.txt b/requirements.txt index bee22f7..331dd57 100644 --- a/requirements.txt +++ b/requirements.txt @@ -1,5 +1,5 @@ numpy -scipy>=1.0 +scipy>=1.3 cython matplotlib autograd diff --git a/setup.py b/setup.py index 4640d00..91c24d9 100755 --- a/setup.py +++ b/setup.py @@ -67,7 +67,8 @@ setup(name='POT', scripts=[], data_files=[], requires=["numpy", "scipy", "cython"], - install_requires=["numpy", "scipy", "cython"], + setup_requires=["numpy>=1.16", "scipy>=1.0", "cython>=0.23"], + install_requires=["numpy>=1.16", "scipy>=1.0", "cython>=0.23"], classifiers=[ 'Development Status :: 5 - Production/Stable', 'Intended Audience :: Developers', -- cgit v1.2.3