Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

add Hungarian solver from optax #598

Merged
merged 10 commits into from
Nov 19, 2024
Merged

add Hungarian solver from optax #598

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
f823c12
add Hungarian solver
marcocuturi Nov 18, 2024
39e56cb
bump optax
marcocuturi Nov 18, 2024
07ceaac
optax.
marcocuturi Nov 18, 2024
4fd262d
add `wass_p` to docs
marcocuturi Nov 18, 2024
8ac3ea5
Correct mistake on defining norm
marcocuturi Nov 18, 2024
74a3ed7
fixes
marcocuturi Nov 19, 2024
61f13eb
add combinatorial
marcocuturi Nov 19, 2024
ab0139b
using anonymous references for Wikipedia entries
marcocuturi Nov 19, 2024
b2d6973
`mu.norm` does not return ||.||^2!!
marcocuturi Nov 19, 2024
02193ef
fix doc for norm
marcocuturi Nov 19, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Correct mistake on defining norm
  • Loading branch information
@marcocuturi
marcocuturi committed Nov 18, 2024
commit 8ac3ea540c248bbe333d8f28e5396a16e1524a16
9 changes: 5 additions & 4 deletions src/ott/geometry/costs.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -348,22 +348,23 @@ def tree_unflatten(cls, aux_data, children): # noqa: D102


@jtu.register_pytree_node_class
class PNorm(TICost):
r""":math:`p`-norm between vectors.
class EuclideanP(TICost):
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please add to the docs.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ok. Don't want to surprise the user because there's no Legendre transform, but can add.

r""":math:`p`-power of Euclidean norm.

Uses custom implementation of `norm` to avoid `NaN` values when
differentiating the norm of :math:`x-x`.

Args:
p: Power of the p-norm in :math:`[1, +\infty)`.
p: Power used to raise Euclidean norm, in :math:`[1, +\infty)`.
"""

def __init__(self, p: float):
super().__init__()
self.p = p

def h(self, z: jnp.ndarray) -> float: # noqa: D102
return mu.norm(z, self.p) / self.p
# Computed by raising squared-norm to p/2.
return mu.norm(z) ** (self.p / 2.)

def tree_flatten(self): # noqa: D102
return (), (self.p,)
Expand Down
2 changes: 1 addition & 1 deletion src/ott/tools/unreg.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -84,6 +84,6 @@ def wassdis_p(x: jnp.ndarray, y: jnp.ndarray, p: float = 2.0) -> float:
Returns:
The p-Wasserstein distance between these point clouds.hungarian
"""
geom = pointcloud.PointCloud(x, y, cost_fn=costs.PNorm(p))
geom = pointcloud.PointCloud(x, y, cost_fn=costs.EuclideanP(p))
cost, _ = hungarian(geom)
return cost ** 1. / p
2 changes: 1 addition & 1 deletion tests/tools/unreg_test.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -46,7 +46,7 @@ def test_wass(self, rng: jax.Array, p: float):
n, m, dim = 12, 12, 5
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Would remove m

rng1, rng2 = jax.random.split(rng, 2)
x, y = gen_data(rng1, n, m, dim)
geom = pointcloud.PointCloud(x, y, cost_fn=costs.PNorm(p=p))
geom = pointcloud.PointCloud(x, y, cost_fn=costs.EuclideanP(p=p))
cost_hung, _ = unreg.hungarian(geom)
w_p = unreg.wassdis_p(x, y, p)
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please add jax.jit.

np.testing.assert_allclose(w_p, cost_hung ** 1. / p, rtol=1e-3, atol=1e-3)
Expand Down
Loading