From ab2fc5486005732d60714b76eecf59d1104346f6 Mon Sep 17 00:00:00 2001 From: Rémi Flamary Date: Thu, 15 Feb 2018 17:09:28 +0100 Subject: awesome documentation --- ot/gromov.py | 188 ++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 135 insertions(+), 53 deletions(-) diff --git a/ot/gromov.py b/ot/gromov.py index c3ce415..8d08397 100644 --- a/ot/gromov.py +++ b/ot/gromov.py @@ -204,11 +204,66 @@ def gwggrad(constC,hC1,hC2,T): """ return 2*tensor_product(constC,hC1,hC2,T) # [12] Prop. 2 misses a 2 factor -def gromov_wasserstein(C1,C2,p,q,loss_fun,log=False,**kwargs): + + +def update_square_loss(p, lambdas, T, Cs): """ - Returns the gromov-wasserstein discrepancy between the two measured similarity matrices + Updates C according to the L2 Loss kernel with the S Ts couplings + calculated at each iteration - (C1,p) and (C2,q) + Parameters + ---------- + p : ndarray, shape (N,) + masses in the targeted barycenter + lambdas : list of float + list of the S spaces' weights + T : list of S np.ndarray(ns,N) + the S Ts couplings calculated at each iteration + Cs : list of S ndarray, shape(ns,ns) + Metric cost matrices + + Returns + ---------- + C : ndarray, shape (nt,nt) + updated C matrix + """ + tmpsum = sum([lambdas[s] * np.dot(T[s].T, Cs[s]).dot(T[s]) + for s in range(len(T))]) + ppt = np.outer(p, p) + + return np.divide(tmpsum, ppt) + + +def update_kl_loss(p, lambdas, T, Cs): + """ + Updates C according to the KL Loss kernel with the S Ts couplings calculated at each iteration + + + Parameters + ---------- + p : ndarray, shape (N,) + weights in the targeted barycenter + lambdas : list of the S spaces' weights + T : list of S np.ndarray(ns,N) + the S Ts couplings calculated at each iteration + Cs : list of S ndarray, shape(ns,ns) + Metric cost matrices + + Returns + ---------- + C : ndarray, shape (ns,ns) + updated C matrix + """ + tmpsum = sum([lambdas[s] * np.dot(T[s].T, Cs[s]).dot(T[s]) + for s in range(len(T))]) + ppt = np.outer(p, p) + + return np.exp(np.divide(tmpsum, ppt)) + + +def gromov_wasserstein(C1,C2,p,q,loss_fun,log=False,**kwargs): + """ + Returns the gromov-wasserstein transport between (C1,p) and (C2,q) The function solves the following optimization problem: @@ -247,14 +302,21 @@ def gromov_wasserstein(C1,C2,p,q,loss_fun,log=False,**kwargs): Returns ------- - gw_dist : float - Gromov-Wasserstein distance + T : ndarray, shape (ns, nt) + coupling between the two spaces that minimizes : + \sum_{i,j,k,l} L(C1_{i,k},C2_{j,l})*T_{i,j}*T_{k,l} + log : dict + convergence information and loss References ---------- .. [12] Peyré, Gabriel, Marco Cuturi, and Justin Solomon, - "Gromov-Wasserstein averaging of kernel and distance matrices." - International Conference on Machine Learning (ICML). 2016. + "Gromov-Wasserstein averaging of kernel and distance matrices." + International Conference on Machine Learning (ICML). 2016. + + .. [13] Mémoli, Facundo. Gromov–Wasserstein distances and the + metric approach to object matching. Foundations of computational + mathematics 11.4 (2011): 417-487. """ @@ -270,73 +332,93 @@ def gromov_wasserstein(C1,C2,p,q,loss_fun,log=False,**kwargs): return gwggrad(constC,hC1,hC2,G) if log: - res,log=cg(p,q,0,alpha,f,df,G0,log=True,**kwargs) + res,log=cg(p,q,0,1,f,df,G0,log=True,**kwargs) log['gw_dist']=gwloss(constC,hC1,hC2,res) return res,log else: - return cg(p,q,0,alpha,f,df,G0,**kwargs) - - - -def update_square_loss(p, lambdas, T, Cs): - """ - Updates C according to the L2 Loss kernel with the S Ts couplings - calculated at each iteration - - Parameters - ---------- - p : ndarray, shape (N,) - masses in the targeted barycenter - lambdas : list of float - list of the S spaces' weights - T : list of S np.ndarray(ns,N) - the S Ts couplings calculated at each iteration - Cs : list of S ndarray, shape(ns,ns) - Metric cost matrices + return cg(p,q,0,1,f,df,G0,**kwargs) - Returns - ---------- - C : ndarray, shape (nt,nt) - updated C matrix +def gromov_wasserstein2(C1,C2,p,q,loss_fun,log=False,**kwargs): """ - tmpsum = sum([lambdas[s] * np.dot(T[s].T, Cs[s]).dot(T[s]) - for s in range(len(T))]) - ppt = np.outer(p, p) - - return np.divide(tmpsum, ppt) + Returns the gromov-wasserstein discrepancy between (C1,p) and (C2,q) + The function solves the following optimization problem: -def update_kl_loss(p, lambdas, T, Cs): - """ - Updates C according to the KL Loss kernel with the S Ts couplings calculated at each iteration + .. math:: + \GW_Dist = \min_T \sum_{i,j,k,l} L(C1_{i,k},C2_{j,l})*T_{i,j}*T_{k,l} + Where : + C1 : Metric cost matrix in the source space + C2 : Metric cost matrix in the target space + p : distribution in the source space + q : distribution in the target space + L : loss function to account for the misfit between the similarity matrices + H : entropy Parameters ---------- - p : ndarray, shape (N,) - weights in the targeted barycenter - lambdas : list of the S spaces' weights - T : list of S np.ndarray(ns,N) - the S Ts couplings calculated at each iteration - Cs : list of S ndarray, shape(ns,ns) - Metric cost matrices + C1 : ndarray, shape (ns, ns) + Metric cost matrix in the source space + C2 : ndarray, shape (nt, nt) + Metric costfr matrix in the target space + p : ndarray, shape (ns,) + distribution in the source space + q : ndarray, shape (nt,) + distribution in the target space + loss_fun : string + loss function used for the solver either 'square_loss' or 'kl_loss' + + max_iter : int, optional + Max number of iterations + tol : float, optional + Stop threshold on error (>0) + verbose : bool, optional + Print information along iterations + log : bool, optional + record log if True Returns + ------- + gw_dist : float + Gromov-Wasserstein distance + log : dict + convergence information and Coupling marix + + References ---------- - C : ndarray, shape (ns,ns) - updated C matrix + .. [12] Peyré, Gabriel, Marco Cuturi, and Justin Solomon, + "Gromov-Wasserstein averaging of kernel and distance matrices." + International Conference on Machine Learning (ICML). 2016. + + .. [13] Mémoli, Facundo. Gromov–Wasserstein distances and the + metric approach to object matching. Foundations of computational + mathematics 11.4 (2011): 417-487. + """ - tmpsum = sum([lambdas[s] * np.dot(T[s].T, Cs[s]).dot(T[s]) - for s in range(len(T))]) - ppt = np.outer(p, p) - return np.exp(np.divide(tmpsum, ppt)) + T = np.eye(len(p), len(q)) + + constC,hC1,hC2=init_matrix(C1,C2,T,p,q,loss_fun) + + G0=p[:,None]*q[None,:] + + def f(G): + return gwloss(constC,hC1,hC2,G) + def df(G): + return gwggrad(constC,hC1,hC2,G) + res,log=cg(p,q,0,1,f,df,G0,log=True,**kwargs) + log['gw_dist']=gwloss(constC,hC1,hC2,res) + log['T']=res + if log: + return log['gw_dist'],log + else: + return log['gw_dist'] def entropic_gromov_wasserstein(C1, C2, p, q, loss_fun, epsilon, max_iter=1000, tol=1e-9, verbose=False, log=False): """ - Returns the regularized gromov-wasserstein coupling between the two measured similarity matrices + Returns the gromov-wasserstein transport between (C1,p) and (C2,q) (C1,p) and (C2,q) -- cgit v1.2.3