ot.regpath
正则化路径OT求解器
函数
- ot.regpath.complement_schur(M_current, b, d, id_pop)[源]
此函数使用Schur余子矩阵计算正则化路径中设计矩阵的逆。可能会出现两种情况：
案例 1：一个变量被添加到活动集合
\[\begin{split}M_{k+1}^{-1} = \begin{bmatrix} M_{k}^{-1} + s^{-1} M_{k}^{-1} \mathbf{b} \mathbf{b}^T M_{k}^{-1} \ & - M_{k}^{-1} \mathbf{b} s^{-1} \\ - s^{-1} \mathbf{b}^T M_{k}^{-1} & s^{-1} \end{bmatrix}\end{split}\]其中 :
\(M_k^{-1}\) 是上一个迭代中设计矩阵 \(H_A^tH_A\) 的逆
\(\mathbf{b}\) 是 \(M_{k}\) 的最后一列
\(s\) 是 Schur 余子式，由 \(s = \mathbf{d} - \mathbf{b}^T M_{k}^{-1} \mathbf{b}\) 给出
案例 2：从活跃集移除一个变量。
\[M_{k+1}^{-1} = M^{-1}_{k \backslash q} - \frac{r_{-q,q} r^{T}_{-q,q}}{r_{q,q}}\]其中 :
\(q\) 是要删除的列和行的索引
\(M^{-1}_{k \backslash q}\) 是去掉 \(q\) 列和 \(q\) 行的前一个逆矩阵
\(r_{-q,q}\) 是 \(M^{-1}_{k}\) 第 \(q\) 列，去掉第 \(q\) 个元素
\(r_{q, q}\) 是 \(M^{-1}_{k}\) 中第 \(q\) 列和第 \(q\) 行的元素
- Parameters:
- Returns:
M – 当前迭代的 \(H_A^tH_A\) 的逆矩阵
- Return type:
ndarray，形状（size(A)，size(A)）
参考文献
- ot.regpath.compute_next_removal(phi, delta, current_gamma)[源]
如果在正则化路径的下一次迭代中移除一个变量，则此函数计算下一个gamma值。
我们寻找正则化参数的最大值，使得当前解的一个元素消失
\[\max_{j \in A} \frac{\phi_j}{\delta_j}\]其中 :
A是当前活动集
\(\phi_j\) 是当前解的截距的 \(j\) 项
\(\delta_j\) 是当前解的第\(j\)个斜率元素
- Parameters:
phi (ndarray, shape (size(A), )) – 当前迭代解决方案的截距
delta (ndarray, shape (size(A), )) – 当前迭代时解的斜率
current_gamma (float) – 当前迭代开始时正则化参数的值
- Returns:
next_removal_gamma (float) – 如果在下一次迭代中移除某个变量，则为伽玛值
next_removal_index (int) – 下一次迭代中要移除的变量的索引
参考文献
- ot.regpath.compute_transport_plan(gamma, gamma_list, Pi_list)[源]
给定正则化路径，该函数可以计算任何值的gamma的运输计划，这得益于路径的分段线性。
\[t(\gamma) = \phi(\gamma) - \gamma \delta(\gamma)\]其中：
\(\gamma\) 是正则化参数
\(\phi(\gamma)\) 是相应的截距
\(\delta(\gamma)\) 是相应的斜率
\(\mathbf{t}\) 是传输矩阵的扁平化版本
- Parameters:
- Returns:
t – 与给定的gamma值对应的运输计划的向量化
- Return type:
np.ndarray (dim_a*dim_b, )
示例
>>> import ot >>> import numpy as np >>> n = 3 >>> xs = np.array([1., 2., 3.]).reshape((n, 1)) >>> xt = np.array([5., 6., 7.]).reshape((n, 1)) >>> C = ot.dist(xs, xt) >>> C /= C.max() >>> a = np.array([0.2, 0.5, 0.3]) >>> b = np.array([0.2, 0.5, 0.3]) >>> t, pi_list, g_list = ot.regpath.regularization_path(a, b, C, reg=1e-4) >>> gamma = 1 >>> t2 = ot.regpath.compute_transport_plan(gamma, g_list, pi_list) >>> t2 array([0. , 0. , 0. , 0.19722222, 0.05555556, 0. , 0. , 0.24722222, 0. ])
参考文献
使用 ot.regpath.compute_transport_plan 的示例
- ot.regpath.construct_augmented_H(active_index, m, Hc, HrHr)[源]
此函数构造了半放松正则化路径第一次迭代的增强矩阵
\[\begin{split}\text{增强}_H = \begin{bmatrix} 0 & H_{c A} \\ H_{c A}^T & H_{r A}^T H_{r A} \end{bmatrix}\end{split}\]其中 :
\(H_{r A}\) 是由索引属于活跃集合 A 的 \(H_r\) 的列构成的子矩阵
\(H_{c A}\) 是由属于活跃集 A 的列构成的 \(H_c\) 的子矩阵
- ot.regpath.fully_relaxed_path(a: array, b: array, C: array, reg=0.0001, itmax=50000)[源]
该函数给出了l2惩罚的UOT问题的正则化路径
要优化的问题是l2惩罚的UOT的Lasso重述：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|{H} \mathbf{t} - \mathbf{y}\|_2^2\\s.t. \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \({C}\) 的展平版本
\(\gamma = 1/\lambda\) 是 l2 正则化系数
\(\mathbf{y}\) 是向量 \(\mathbf{a}\) 和 \(\mathbf{b}\) 的连接，定义为 \(\mathbf{y}^T = [\mathbf{a}^T \mathbf{b}^T]\)
\({H}\) 是一个设计矩阵，参见 [41] 以了解 \({H}\) 的设计。矩阵乘积 \(H\mathbf{t}\) 计算源边际和目标边际。
\(\mathbf{t}\) 是传输矩阵的扁平化版本
- Parameters:
- Returns:
t (np.ndarray (dim_a*dim_b, )) – 最优运输矩阵的扁平化向量
t_list (list) – 正则化路径中的解列表
gamma_list (list) – 正则化路径中的正则化系数列表
示例
>>> import ot >>> import numpy as np >>> n = 3 >>> xs = np.array([1., 2., 3.]).reshape((n, 1)) >>> xt = np.array([5., 6., 7.]).reshape((n, 1)) >>> C = ot.dist(xs, xt) >>> C /= C.max() >>> a = np.array([0.2, 0.5, 0.3]) >>> b = np.array([0.2, 0.5, 0.3]) >>> t, _, _ = ot.regpath.fully_relaxed_path(a, b, C, 1e-4) >>> t array([1.99958333e-01, 0.00000000e+00, 0.00000000e+00, 3.88888889e-05, 4.99938889e-01, 0.00000000e+00, 0.00000000e+00, 3.88888889e-05, 2.99958333e-01])
参考文献
- ot.regpath.ot_next_gamma(phi, delta, HtH, Hty, c, active_index, current_gamma)[源]
该函数计算在正则化路径的下一个迭代中添加变量时，gamma的下一个值。
我们寻找最大的gamma值，使得非活动变量的梯度消失
\[\max_{i \in \bar{A}} \frac{\mathbf{h}_i^T(H_A \phi - \mathbf{y})} {\mathbf{h}_i^T H_A \delta - \mathbf{c}_i}\]其中 :
A是当前活动集
\(\mathbf{h}_i\) 是设计矩阵 \({H}\) 的 \(i\) 列
\({H}_A\)是由\({H}\)的列构成的子矩阵，其索引属于活跃集合A
\(\mathbf{c}_i\) 是成本向量 \(\mathbf{c}\) 的第 \(i\) 个元素
\(\mathbf{y}\) 是源分布和目标分布的连接
\(\phi\) 是当前迭代中解的截距
\(\delta\) 是当前迭代中解的斜率
- Parameters:
phi (np.ndarray (size(A), )) – 当前迭代中解的截距
delta (np.ndarray (size(A), )) – 当前迭代点解的斜率
HtH (np.ndarray (dim_a * dim_b, dim_a * dim_b)) – 矩阵乘积 \({H}^T {H}\)
Hty (np.ndarray (dim_a + dim_b, )) – \({H}^T \mathbf{y}\)的矩阵乘积
c (np.ndarray (dim_a * dim_b, )) – 成本矩阵 \({C}\) 的扁平化数组
active_index (list) – 活跃变量的索引
current_gamma (float) – 当前迭代开始时正则化参数的值
- Returns:
next_gamma (float) – 如果在下一次迭代中将变量添加到活动集，则gamma的值
next_active_index (int) – 要激活的变量的索引
参考文献
- ot.regpath.recast_ot_as_lasso(a, b, C)[源]
此函数将 l2 惩罚的 UOT 问题重新表述为 Lasso 问题。
回忆一下l2惩罚的UOT问题，定义在 [41]
\[ \begin{align}\begin{aligned}\text{UOT}_{\lambda} = \min_T + \lambda \|T 1_m - \mathbf{a}\|_2^2 + \lambda \|T^T 1_n - \mathbf{b}\|_2^2\\s.t. T \geq 0\end{aligned}\end{align} \]其中 :
\(C\) 是成本矩阵
\(\lambda\) 是 l2 正则化参数
\(\mathbf{a}\) 和 \(\mathbf{b}\) 是源分布和目标分布
\(T\) 是用于优化的运输计划
上述问题可以重新表述为一个非负的惩罚线性回归问题，特别是Lasso
\[ \begin{align}\begin{aligned}\text{UOT2}_{\lambda} = \min_{\mathbf{t}} \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|H \mathbf{t} - \mathbf{y}\|_2^2\\s.t. \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \(C\) 的扁平化版本
\(\mathbf{y}\) 是向量 \(\mathbf{a}\) 和 \(\mathbf{b}\) 的串联
\(H\) 是一个度量矩阵，关于\(H\)的设计请参见[41]。矩阵乘积\(H\mathbf{t}\) 计算源边际和目标边际。
\(\mathbf{t}\) 是运输计划 \(T\) 的扁平化版本
- Parameters:
a (np.ndarray (dim_a,)) – 维度为 dim_a 的直方图
b (np.ndarray (dim_b,)) – 维度 dim_b 的直方图
C (np.ndarray, shape (dim_a, dim_b)) – 成本矩阵
- Returns:
H (np.ndarray (dim_a+dim_b, dim_a*dim_b)) – 只包含0和1的设计矩阵
y (np.ndarray (ns + nt, )) – 直方图\(\mathbf{a}\)和\(\mathbf{b}\)的拼接
c (np.ndarray (ns * nt, )) – 成本矩阵的展平数组
示例
>>> import ot >>> a = np.array([0.2, 0.3, 0.5]) >>> b = np.array([0.1, 0.9]) >>> C = np.array([[16., 25.], [28., 16.], [40., 36.]]) >>> H, y, c = ot.regpath.recast_ot_as_lasso(a, b, C) >>> H.toarray() array([[1., 1., 0., 0., 0., 0.], [0., 0., 1., 1., 0., 0.], [0., 0., 0., 0., 1., 1.], [1., 0., 1., 0., 1., 0.], [0., 1., 0., 1., 0., 1.]]) >>> y array([0.2, 0.3, 0.5, 0.1, 0.9]) >>> c array([16., 25., 28., 16., 40., 36.])
参考文献
- ot.regpath.recast_semi_relaxed_as_lasso(a, b, C)[源]
该函数将半放松的l2-UOT问题重新表述为Lasso问题。
\[ \begin{align}\begin{aligned}\text{半放松的UOT} = \min_T + \lambda \|T 1_m - \mathbf{a}\|_2^2\\s.t. T^T 1_n = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(C\) 是度量成本矩阵
\(\lambda\) 是 l2 正则化参数
\(\mathbf{a}\) 和 \(\mathbf{b}\) 是源分布和目标分布
\(T\) 是用于优化的运输计划
上述问题可以重新表述为以下内容
\[ \begin{align}\begin{aligned}\text{半放松的 UOT2} = \min_t \gamma \mathbf{c}^T t + 0.5 * \|H_r \mathbf{t} - \mathbf{a}\|_2^2\\s.t. H_c \mathbf{t} = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \(C\) 的扁平化版本
\(\gamma = 1/\lambda\) 是 l2 正则化参数
\(H_r\) 是一个度量矩阵，计算运输计划 \(T\) 行的总和
\(H_c\) 是一个度量矩阵，用于计算运输计划 \(T\) 列的总和
\(\mathbf{t}\) 是 \(T\) 的扁平化版本
- Parameters:
a (np.ndarray (dim_a,)) – 维度为 dim_a 的直方图
b (np.ndarray (dim_b,)) – 维度 dim_b 的直方图
C (np.ndarray, shape (dim_a, dim_b)) – 成本矩阵
- Returns:
Hr (np.ndarray (dim_a, dim_a * dim_b)) – 由0和1组成的辅助矩阵，用于计算运输计划 \(T\) 的行总和
Hc (np.ndarray (dim_b, dim_a * dim_b)) – 由0和1组成的辅助矩阵，用于计算运输计划 \(T\) 的列总和
c (np.ndarray (ns * nt, )) – 成本矩阵的扁平数组
示例
>>> import ot >>> a = np.array([0.2, 0.3, 0.5]) >>> b = np.array([0.1, 0.9]) >>> C = np.array([[16., 25.], [28., 16.], [40., 36.]]) >>> Hr,Hc,c = ot.regpath.recast_semi_relaxed_as_lasso(a, b, C) >>> Hr.toarray() array([[1., 1., 0., 0., 0., 0.], [0., 0., 1., 1., 0., 0.], [0., 0., 0., 0., 1., 1.]]) >>> Hc.toarray() array([[1., 0., 1., 0., 1., 0.], [0., 1., 0., 1., 0., 1.]]) >>> c array([16., 25., 28., 16., 40., 36.])
- ot.regpath.regularization_path(a: array, b: array, C: array, reg=0.0001, semi_relaxed=False, itmax=50000)[源]
此函数提供l2-UOT问题的正则化路径的所有解 [41]。
要优化的问题是l2惩罚的UOT的Lasso重述：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|{H} \mathbf{t} - \mathbf{y}\|_2^2\\s.t. \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \({C}\) 的展平版本
\(\gamma = 1/\lambda\) 是 l2 正则化系数
\(\mathbf{y}\) 是向量 \(\mathbf{a}\) 和 \(\mathbf{b}\) 的连接，定义为 \(\mathbf{y}^T = [\mathbf{a}^T \mathbf{b}^T]\)
\({H}\) 是一个设计矩阵，参见 [41] 以了解 \({H}\) 的设计。矩阵乘积 \(H\mathbf{t}\) 计算源边际和目标边际。
\(\mathbf{t}\) 是传输矩阵的扁平化版本
对于半放松问题，它优化了l2惩罚的UOT的Lasso重构：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|H_r \mathbf{t} - \mathbf{a}\|_2^2\\s.t. H_c \mathbf{t} = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]- Parameters:
- Returns:
t (np.ndarray (dim_a*dim_b, )) – 没有正则化的最优运输矩阵的扁平化向量
t_list (list) – 正则化路径的所有最优运输向量的列表
gamma_list (list) – 路径中正则化参数的列表
参考文献
使用 ot.regpath.regularization_path 的示例
- ot.regpath.semi_relaxed_next_gamma(phi, delta, phi_u, delta_u, HrHr, Hc, Hra, c, active_index, current_gamma)[源]
此函数计算当一个变量在半放松UOT的正则化路径中处于活动状态时gamma的下一个值。
通过采用问题的拉格朗日形式，我们获得了类似于双侧放松的 UOT 的更新
\[\max_{i \in \bar{A}} \frac{\mathbf{h}_{ri}^T(H_{rA} \phi - \mathbf{a}) + \mathbf{h}_{c i}^T\phi_u}{\mathbf{h}_{r i}^T H_{r A} \delta + \ \mathbf{h}_{c i} \delta_u - \mathbf{c}_i}\]其中 :
A是当前活动集
\(\mathbf{h}_{r i}\) 是矩阵 \(H_r\) 的第 i 列
\(\mathbf{h}_{c i}\) 是矩阵 \(H_c\) 的第 i 列
\(H_{r A}\) 是由索引属于活跃集合 A 的 \(H_r\) 的列构成的子矩阵
\(\mathbf{c}_i\) 是成本向量 \(\mathbf{c}\) 的第 \(i\) 个元素
\(\phi\) 是当前迭代中解的截距
\(\delta\) 是当前迭代中解的斜率
\(\phi_u\) 是当前迭代中拉格朗日参数的截距
\(\delta_u\) 是当前迭代中拉格朗日参数的斜率
- Parameters:
phi (np.ndarray (size(A), )) – 当前迭代中解的截距
delta (np.ndarray (size(A), )) – 当前迭代点解的斜率
phi_u (np.ndarray (dim_b, )) – 当前迭代中拉格朗日参数的截距
delta_u (np.ndarray (dim_b, )) – 当前迭代的拉格朗日参数的斜率
HrHr (np.ndarray (dim_a * dim_b, dim_a * dim_b)) – \(H_r^T H_r\) 的矩阵乘积
Hc (np.ndarray (dim_b, dim_a * dim_b)) – 计算运输计划 \(T\) 列和的矩阵
Hra (np.ndarray (dim_a * dim_b, )) – \(H_r^T \mathbf{a}\) 的矩阵乘积
c (np.ndarray (dim_a * dim_b, )) – 成本矩阵的扁平化数组 \(C\)
active_index (list) – 活跃变量的索引
current_gamma (float) – 当前迭代开始时正则化系数的值
- Returns:
next_gamma (float) – 如果在下一次迭代中将变量添加到活动集，则gamma的值
next_active_index (int) – 要激活的变量的索引
参考文献
- ot.regpath.semi_relaxed_path(a: array, b: array, C: array, reg=0.0001, itmax=50000)[源]
这个函数给出了半放松 l2-UOT 问题的正则化路径。
要优化的问题是l2惩罚的UOT的Lasso重述：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T t + 0.5 * \|H_r \mathbf{t} - \mathbf{a}\|_2^2\\s.t. H_c \mathbf{t} = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \(C\) 的扁平化版本
\(\gamma = 1/\lambda\) 是 l2 正则化参数
\(H_r\) 是一个计算运输计划 \(T\) 行之和的矩阵
\(H_c\) 是一个计算运输计划 \(T\) 列总和的矩阵
\(\mathbf{t}\) 是运输计划 \(T\) 的扁平化版本
- Parameters:
- Returns:
t (np.ndarray (dim_a*dim_b, )) – 没有正则化的最优运输矩阵的扁平化向量
t_list (list) – 正则化路径的所有最优运输向量的列表
gamma_list (list) – 路径中正则化参数的列表
示例
>>> import ot >>> import numpy as np >>> n = 3 >>> xs = np.array([1., 2., 3.]).reshape((n, 1)) >>> xt = np.array([5., 6., 7.]).reshape((n, 1)) >>> C = ot.dist(xs, xt) >>> C /= C.max() >>> a = np.array([0.2, 0.5, 0.3]) >>> b = np.array([0.2, 0.5, 0.3]) >>> t, _, _ = ot.regpath.semi_relaxed_path(a, b, C, 1e-4) >>> t array([1.99980556e-01, 0.00000000e+00, 0.00000000e+00, 1.94444444e-05, 4.99980556e-01, 0.00000000e+00, 0.00000000e+00, 1.94444444e-05, 3.00000000e-01])
参考文献
- ot.regpath.complement_schur(M_current, b, d, id_pop)[源]
此函数使用Schur余子矩阵计算正则化路径中设计矩阵的逆。可能会出现两种情况：
案例 1：一个变量被添加到活动集合
\[\begin{split}M_{k+1}^{-1} = \begin{bmatrix} M_{k}^{-1} + s^{-1} M_{k}^{-1} \mathbf{b} \mathbf{b}^T M_{k}^{-1} \ & - M_{k}^{-1} \mathbf{b} s^{-1} \\ - s^{-1} \mathbf{b}^T M_{k}^{-1} & s^{-1} \end{bmatrix}\end{split}\]其中 :
\(M_k^{-1}\) 是上一个迭代中设计矩阵 \(H_A^tH_A\) 的逆
\(\mathbf{b}\) 是 \(M_{k}\) 的最后一列
\(s\) 是 Schur 余子式，由 \(s = \mathbf{d} - \mathbf{b}^T M_{k}^{-1} \mathbf{b}\) 给出
案例 2：从活跃集移除一个变量。
\[M_{k+1}^{-1} = M^{-1}_{k \backslash q} - \frac{r_{-q,q} r^{T}_{-q,q}}{r_{q,q}}\]其中 :
\(q\) 是要删除的列和行的索引
\(M^{-1}_{k \backslash q}\) 是去掉 \(q\) 列和 \(q\) 行的前一个逆矩阵
\(r_{-q,q}\) 是 \(M^{-1}_{k}\) 第 \(q\) 列，去掉第 \(q\) 个元素
\(r_{q, q}\) 是 \(M^{-1}_{k}\) 中第 \(q\) 列和第 \(q\) 行的元素
- Parameters:
- Returns:
M – 当前迭代的 \(H_A^tH_A\) 的逆矩阵
- Return type:
ndarray，形状（size(A)，size(A)）
参考文献
- ot.regpath.compute_next_removal(phi, delta, current_gamma)[源]
如果在正则化路径的下一次迭代中移除一个变量，则此函数计算下一个gamma值。
我们寻找正则化参数的最大值，使得当前解的一个元素消失
\[\max_{j \in A} \frac{\phi_j}{\delta_j}\]其中 :
A是当前活动集
\(\phi_j\) 是当前解的截距的 \(j\) 项
\(\delta_j\) 是当前解的第\(j\)个斜率元素
- Parameters:
phi (ndarray, shape (size(A), )) – 当前迭代解决方案的截距
delta (ndarray, shape (size(A), )) – 当前迭代时解的斜率
current_gamma (float) – 当前迭代开始时正则化参数的值
- Returns:
next_removal_gamma (float) – 如果在下一次迭代中移除某个变量，则为伽玛值
next_removal_index (int) – 下一次迭代中要移除的变量的索引
参考文献
- ot.regpath.compute_transport_plan(gamma, gamma_list, Pi_list)[源]
给定正则化路径，该函数可以计算任何值的gamma的运输计划，这得益于路径的分段线性。
\[t(\gamma) = \phi(\gamma) - \gamma \delta(\gamma)\]其中：
\(\gamma\) 是正则化参数
\(\phi(\gamma)\) 是相应的截距
\(\delta(\gamma)\) 是相应的斜率
\(\mathbf{t}\) 是传输矩阵的扁平化版本
- Parameters:
- Returns:
t – 与给定的gamma值对应的运输计划的向量化
- Return type:
np.ndarray (dim_a*dim_b, )
示例
>>> import ot >>> import numpy as np >>> n = 3 >>> xs = np.array([1., 2., 3.]).reshape((n, 1)) >>> xt = np.array([5., 6., 7.]).reshape((n, 1)) >>> C = ot.dist(xs, xt) >>> C /= C.max() >>> a = np.array([0.2, 0.5, 0.3]) >>> b = np.array([0.2, 0.5, 0.3]) >>> t, pi_list, g_list = ot.regpath.regularization_path(a, b, C, reg=1e-4) >>> gamma = 1 >>> t2 = ot.regpath.compute_transport_plan(gamma, g_list, pi_list) >>> t2 array([0. , 0. , 0. , 0.19722222, 0.05555556, 0. , 0. , 0.24722222, 0. ])
参考文献
- ot.regpath.construct_augmented_H(active_index, m, Hc, HrHr)[源]
此函数构造了半放松正则化路径第一次迭代的增强矩阵
\[\begin{split}\text{增强}_H = \begin{bmatrix} 0 & H_{c A} \\ H_{c A}^T & H_{r A}^T H_{r A} \end{bmatrix}\end{split}\]其中 :
\(H_{r A}\) 是由索引属于活跃集合 A 的 \(H_r\) 的列构成的子矩阵
\(H_{c A}\) 是由属于活跃集 A 的列构成的 \(H_c\) 的子矩阵
- ot.regpath.fully_relaxed_path(a: array, b: array, C: array, reg=0.0001, itmax=50000)[源]
该函数给出了l2惩罚的UOT问题的正则化路径
要优化的问题是l2惩罚的UOT的Lasso重述：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|{H} \mathbf{t} - \mathbf{y}\|_2^2\\s.t. \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \({C}\) 的展平版本
\(\gamma = 1/\lambda\) 是 l2 正则化系数
\(\mathbf{y}\) 是向量 \(\mathbf{a}\) 和 \(\mathbf{b}\) 的连接，定义为 \(\mathbf{y}^T = [\mathbf{a}^T \mathbf{b}^T]\)
\({H}\) 是一个设计矩阵，参见 [41] 以了解 \({H}\) 的设计。矩阵乘积 \(H\mathbf{t}\) 计算源边际和目标边际。
\(\mathbf{t}\) 是传输矩阵的扁平化版本
- Parameters:
- Returns:
t (np.ndarray (dim_a*dim_b, )) – 最优运输矩阵的扁平化向量
t_list (list) – 正则化路径中的解列表
gamma_list (list) – 正则化路径中的正则化系数列表
示例
>>> import ot >>> import numpy as np >>> n = 3 >>> xs = np.array([1., 2., 3.]).reshape((n, 1)) >>> xt = np.array([5., 6., 7.]).reshape((n, 1)) >>> C = ot.dist(xs, xt) >>> C /= C.max() >>> a = np.array([0.2, 0.5, 0.3]) >>> b = np.array([0.2, 0.5, 0.3]) >>> t, _, _ = ot.regpath.fully_relaxed_path(a, b, C, 1e-4) >>> t array([1.99958333e-01, 0.00000000e+00, 0.00000000e+00, 3.88888889e-05, 4.99938889e-01, 0.00000000e+00, 0.00000000e+00, 3.88888889e-05, 2.99958333e-01])
参考文献
- ot.regpath.ot_next_gamma(phi, delta, HtH, Hty, c, active_index, current_gamma)[源]
该函数计算在正则化路径的下一个迭代中添加变量时，gamma的下一个值。
我们寻找最大的gamma值，使得非活动变量的梯度消失
\[\max_{i \in \bar{A}} \frac{\mathbf{h}_i^T(H_A \phi - \mathbf{y})} {\mathbf{h}_i^T H_A \delta - \mathbf{c}_i}\]其中 :
A是当前活动集
\(\mathbf{h}_i\) 是设计矩阵 \({H}\) 的 \(i\) 列
\({H}_A\)是由\({H}\)的列构成的子矩阵，其索引属于活跃集合A
\(\mathbf{c}_i\) 是成本向量 \(\mathbf{c}\) 的第 \(i\) 个元素
\(\mathbf{y}\) 是源分布和目标分布的连接
\(\phi\) 是当前迭代中解的截距
\(\delta\) 是当前迭代中解的斜率
- Parameters:
phi (np.ndarray (size(A), )) – 当前迭代中解的截距
delta (np.ndarray (size(A), )) – 当前迭代点解的斜率
HtH (np.ndarray (dim_a * dim_b, dim_a * dim_b)) – 矩阵乘积 \({H}^T {H}\)
Hty (np.ndarray (dim_a + dim_b, )) – \({H}^T \mathbf{y}\)的矩阵乘积
c (np.ndarray (dim_a * dim_b, )) – 成本矩阵 \({C}\) 的扁平化数组
active_index (list) – 活跃变量的索引
current_gamma (float) – 当前迭代开始时正则化参数的值
- Returns:
next_gamma (float) – 如果在下一次迭代中将变量添加到活动集，则gamma的值
next_active_index (int) – 要激活的变量的索引
参考文献
- ot.regpath.recast_ot_as_lasso(a, b, C)[源]
此函数将 l2 惩罚的 UOT 问题重新表述为 Lasso 问题。
回忆一下l2惩罚的UOT问题，定义在 [41]
\[ \begin{align}\begin{aligned}\text{UOT}_{\lambda} = \min_T + \lambda \|T 1_m - \mathbf{a}\|_2^2 + \lambda \|T^T 1_n - \mathbf{b}\|_2^2\\s.t. T \geq 0\end{aligned}\end{align} \]其中 :
\(C\) 是成本矩阵
\(\lambda\) 是 l2 正则化参数
\(\mathbf{a}\) 和 \(\mathbf{b}\) 是源分布和目标分布
\(T\) 是用于优化的运输计划
上述问题可以重新表述为一个非负的惩罚线性回归问题，特别是Lasso
\[ \begin{align}\begin{aligned}\text{UOT2}_{\lambda} = \min_{\mathbf{t}} \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|H \mathbf{t} - \mathbf{y}\|_2^2\\s.t. \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \(C\) 的扁平化版本
\(\mathbf{y}\) 是向量 \(\mathbf{a}\) 和 \(\mathbf{b}\) 的串联
\(H\) 是一个度量矩阵，关于\(H\)的设计请参见[41]。矩阵乘积\(H\mathbf{t}\) 计算源边际和目标边际。
\(\mathbf{t}\) 是运输计划 \(T\) 的扁平化版本
- Parameters:
a (np.ndarray (dim_a,)) – 维度为 dim_a 的直方图
b (np.ndarray (dim_b,)) – 维度 dim_b 的直方图
C (np.ndarray, shape (dim_a, dim_b)) – 成本矩阵
- Returns:
H (np.ndarray (dim_a+dim_b, dim_a*dim_b)) – 只包含0和1的设计矩阵
y (np.ndarray (ns + nt, )) – 直方图\(\mathbf{a}\)和\(\mathbf{b}\)的拼接
c (np.ndarray (ns * nt, )) – 成本矩阵的展平数组
示例
>>> import ot >>> a = np.array([0.2, 0.3, 0.5]) >>> b = np.array([0.1, 0.9]) >>> C = np.array([[16., 25.], [28., 16.], [40., 36.]]) >>> H, y, c = ot.regpath.recast_ot_as_lasso(a, b, C) >>> H.toarray() array([[1., 1., 0., 0., 0., 0.], [0., 0., 1., 1., 0., 0.], [0., 0., 0., 0., 1., 1.], [1., 0., 1., 0., 1., 0.], [0., 1., 0., 1., 0., 1.]]) >>> y array([0.2, 0.3, 0.5, 0.1, 0.9]) >>> c array([16., 25., 28., 16., 40., 36.])
参考文献
- ot.regpath.recast_semi_relaxed_as_lasso(a, b, C)[源]
该函数将半放松的l2-UOT问题重新表述为Lasso问题。
\[ \begin{align}\begin{aligned}\text{半放松的UOT} = \min_T + \lambda \|T 1_m - \mathbf{a}\|_2^2\\s.t. T^T 1_n = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(C\) 是度量成本矩阵
\(\lambda\) 是 l2 正则化参数
\(\mathbf{a}\) 和 \(\mathbf{b}\) 是源分布和目标分布
\(T\) 是用于优化的运输计划
上述问题可以重新表述为以下内容
\[ \begin{align}\begin{aligned}\text{半放松的 UOT2} = \min_t \gamma \mathbf{c}^T t + 0.5 * \|H_r \mathbf{t} - \mathbf{a}\|_2^2\\s.t. H_c \mathbf{t} = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \(C\) 的扁平化版本
\(\gamma = 1/\lambda\) 是 l2 正则化参数
\(H_r\) 是一个度量矩阵，计算运输计划 \(T\) 行的总和
\(H_c\) 是一个度量矩阵，用于计算运输计划 \(T\) 列的总和
\(\mathbf{t}\) 是 \(T\) 的扁平化版本
- Parameters:
a (np.ndarray (dim_a,)) – 维度为 dim_a 的直方图
b (np.ndarray (dim_b,)) – 维度 dim_b 的直方图
C (np.ndarray, shape (dim_a, dim_b)) – 成本矩阵
- Returns:
Hr (np.ndarray (dim_a, dim_a * dim_b)) – 由0和1组成的辅助矩阵，用于计算运输计划 \(T\) 的行总和
Hc (np.ndarray (dim_b, dim_a * dim_b)) – 由0和1组成的辅助矩阵，用于计算运输计划 \(T\) 的列总和
c (np.ndarray (ns * nt, )) – 成本矩阵的扁平数组
示例
>>> import ot >>> a = np.array([0.2, 0.3, 0.5]) >>> b = np.array([0.1, 0.9]) >>> C = np.array([[16., 25.], [28., 16.], [40., 36.]]) >>> Hr,Hc,c = ot.regpath.recast_semi_relaxed_as_lasso(a, b, C) >>> Hr.toarray() array([[1., 1., 0., 0., 0., 0.], [0., 0., 1., 1., 0., 0.], [0., 0., 0., 0., 1., 1.]]) >>> Hc.toarray() array([[1., 0., 1., 0., 1., 0.], [0., 1., 0., 1., 0., 1.]]) >>> c array([16., 25., 28., 16., 40., 36.])
- ot.regpath.regularization_path(a: array, b: array, C: array, reg=0.0001, semi_relaxed=False, itmax=50000)[源]
此函数提供l2-UOT问题的正则化路径的所有解 [41]。
要优化的问题是l2惩罚的UOT的Lasso重述：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|{H} \mathbf{t} - \mathbf{y}\|_2^2\\s.t. \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \({C}\) 的展平版本
\(\gamma = 1/\lambda\) 是 l2 正则化系数
\(\mathbf{y}\) 是向量 \(\mathbf{a}\) 和 \(\mathbf{b}\) 的连接，定义为 \(\mathbf{y}^T = [\mathbf{a}^T \mathbf{b}^T]\)
\({H}\) 是一个设计矩阵，参见 [41] 以了解 \({H}\) 的设计。矩阵乘积 \(H\mathbf{t}\) 计算源边际和目标边际。
\(\mathbf{t}\) 是传输矩阵的扁平化版本
对于半放松问题，它优化了l2惩罚的UOT的Lasso重构：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T \mathbf{t} + 0.5 * \|H_r \mathbf{t} - \mathbf{a}\|_2^2\\s.t. H_c \mathbf{t} = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]- Parameters:
- Returns:
t (np.ndarray (dim_a*dim_b, )) – 没有正则化的最优运输矩阵的扁平化向量
t_list (list) – 正则化路径的所有最优运输向量的列表
gamma_list (list) – 路径中正则化参数的列表
参考文献
- ot.regpath.semi_relaxed_next_gamma(phi, delta, phi_u, delta_u, HrHr, Hc, Hra, c, active_index, current_gamma)[源]
此函数计算当一个变量在半放松UOT的正则化路径中处于活动状态时gamma的下一个值。
通过采用问题的拉格朗日形式，我们获得了类似于双侧放松的 UOT 的更新
\[\max_{i \in \bar{A}} \frac{\mathbf{h}_{ri}^T(H_{rA} \phi - \mathbf{a}) + \mathbf{h}_{c i}^T\phi_u}{\mathbf{h}_{r i}^T H_{r A} \delta + \ \mathbf{h}_{c i} \delta_u - \mathbf{c}_i}\]其中 :
A是当前活动集
\(\mathbf{h}_{r i}\) 是矩阵 \(H_r\) 的第 i 列
\(\mathbf{h}_{c i}\) 是矩阵 \(H_c\) 的第 i 列
\(H_{r A}\) 是由索引属于活跃集合 A 的 \(H_r\) 的列构成的子矩阵
\(\mathbf{c}_i\) 是成本向量 \(\mathbf{c}\) 的第 \(i\) 个元素
\(\phi\) 是当前迭代中解的截距
\(\delta\) 是当前迭代中解的斜率
\(\phi_u\) 是当前迭代中拉格朗日参数的截距
\(\delta_u\) 是当前迭代中拉格朗日参数的斜率
- Parameters:
phi (np.ndarray (size(A), )) – 当前迭代中解的截距
delta (np.ndarray (size(A), )) – 当前迭代点解的斜率
phi_u (np.ndarray (dim_b, )) – 当前迭代中拉格朗日参数的截距
delta_u (np.ndarray (dim_b, )) – 当前迭代的拉格朗日参数的斜率
HrHr (np.ndarray (dim_a * dim_b, dim_a * dim_b)) – \(H_r^T H_r\) 的矩阵乘积
Hc (np.ndarray (dim_b, dim_a * dim_b)) – 计算运输计划 \(T\) 列和的矩阵
Hra (np.ndarray (dim_a * dim_b, )) – \(H_r^T \mathbf{a}\) 的矩阵乘积
c (np.ndarray (dim_a * dim_b, )) – 成本矩阵的扁平化数组 \(C\)
active_index (list) – 活跃变量的索引
current_gamma (float) – 当前迭代开始时正则化系数的值
- Returns:
next_gamma (float) – 如果在下一次迭代中将变量添加到活动集，则gamma的值
next_active_index (int) – 要激活的变量的索引
参考文献
- ot.regpath.semi_relaxed_path(a: array, b: array, C: array, reg=0.0001, itmax=50000)[源]
这个函数给出了半放松 l2-UOT 问题的正则化路径。
要优化的问题是l2惩罚的UOT的Lasso重述：
\[ \begin{align}\begin{aligned}\min_t \gamma \mathbf{c}^T t + 0.5 * \|H_r \mathbf{t} - \mathbf{a}\|_2^2\\s.t. H_c \mathbf{t} = \mathbf{b}\\ \mathbf{t} \geq 0\end{aligned}\end{align} \]其中 :
\(\mathbf{c}\) 是成本矩阵 \(C\) 的扁平化版本
\(\gamma = 1/\lambda\) 是 l2 正则化参数
\(H_r\) 是一个计算运输计划 \(T\) 行之和的矩阵
\(H_c\) 是一个计算运输计划 \(T\) 列总和的矩阵
\(\mathbf{t}\) 是运输计划 \(T\) 的扁平化版本
- Parameters:
- Returns:
t (np.ndarray (dim_a*dim_b, )) – 没有正则化的最优运输矩阵的扁平化向量
t_list (list) – 正则化路径的所有最优运输向量的列表
gamma_list (list) – 路径中正则化参数的列表
示例
>>> import ot >>> import numpy as np >>> n = 3 >>> xs = np.array([1., 2., 3.]).reshape((n, 1)) >>> xt = np.array([5., 6., 7.]).reshape((n, 1)) >>> C = ot.dist(xs, xt) >>> C /= C.max() >>> a = np.array([0.2, 0.5, 0.3]) >>> b = np.array([0.2, 0.5, 0.3]) >>> t, _, _ = ot.regpath.semi_relaxed_path(a, b, C, 1e-4) >>> t array([1.99980556e-01, 0.00000000e+00, 0.00000000e+00, 1.94444444e-05, 4.99980556e-01, 0.00000000e+00, 0.00000000e+00, 1.94444444e-05, 3.00000000e-01])
参考文献