《浅谈保序回归问题》学习笔记

管理员

1.偏序关系

设 $preceq $ 是集合 (S) 上的一个二元关系,若 (R) 满足:

  • 自反性:(forall x in S)(x preceq x)
  • 反对称性:(forall x, y in S)(x preceq y, y preceq x Rightarrow x = y)
  • 传递性:(forall x, y, z in S)(x preceq y, y preceq z Rightarrow x preceq z)

2.问题描述

给定正整数 (p) 和一个偏序关系(DAG),每个点有权值 ((w_i, y_i)),你需要给每个点附上一个权值 (f_i),使得 (forall x, y, s.t. x preceq y)(f_x leq f_y),最小化回归代价:

[sumlimits_{i in S}w_i|f_i - y_i|^p ]

特别地,当 (p to infty) 时,回归代价为 (max_{iin S}w_i|f_i - y_i|)

对于一个给定的 (p),称上面的问题是 (L_p) 问题。

3.(L_p) 均值及其性质

定义 (L_p) 均值为使得 (sum_{iin S}w_i|k - y_i|^p) 最小的 (k),即 (f_i) 均相同时的答案,可以对目标式求导,导数为 0 即是答案。

(p = 1) 时,(L_1) 均值是大家幼儿园都知道的带权中位数;当 (p = 2) 时,是带权平均数,即 ((sumlimits_{i in S}w_iy_i)/(sumlimits_{i in S}w_i))

(p > 1) 时,(L_p) 均值唯一。且对于任意一组 (L_p) 问题的最优解 ({f_i}),存在 (S) 的一个子集 (T),使得 (T)(L_p) 均值为 (f_i)

4.一般问题的算法

(L_p) 问题的基础上而外加入限制 (S = {a, b}(a < b)),使得 (forall i, a leq f_i leq b)

(p = 1) 的情况

(p = 1) 时,一个点集 (U)(L_p) 均值可能是一段区间,同时显然存在一个最优解使得 (f_i in {y_i}) 中,移动 (f_i) 的改变量是一些一次函数。

引理 1 :在 (L_1) 问题中,若存在区间 ((a, b)) 使得所有 (y_i) 不在 ((a, b)),且存在一组最优解 (z_i) 使得 (z_i) 也不在 ((a, b))。定义一个集合对区间 (S = (a,b)) 取整为 (z^S):若 (z_i leq a)(z_i = a);若 (z_i geq b)(z_i = b);否则不变。则 (z^S)(S) 问题的一组最优解。

根据引理,可以进行整体二分。二分到 ([l, r]) 时,计算 (S = (y_{mid}, y_{mid+1})) 的最优解,根据 (z_i) 的取值情况继续划分成 ([l, mid])([mid+1,r]) 的两个子问题。

(1 < p <infty) 的情况

(1 <p < infty),其 (L_p) 均值唯一,且代价函数在 (< L_p) 时递减,(>L_p) 时递增。

整体二分,找一个极小的 $epsilon $ 使得任意 (y_i, f_i) 不在 ((mid, mid+epsilon)) 中,根据引理,每个 (f_i) 只能等于 (mid) 或 $mid+epsilon $。 若 (U) 中任意一点选择了 $mid+epsilon $,则所有满足 (x in U, i preceq x) 的点都只能选择 (mid+epsilon),等价于闭合子图模型。钦定所有点先选择 (mid),若选择 $mid+epsilon $ 的改变量为 (w_i[(mid+epsilon)^p - y_i]-w_i[mid^p - y_i]) ,然后跑最小权闭合子图即可。

但可能精度误差较大。此时可以将 (mid) 看做变量 (x),两边同时除以 (epsilon),变成 (x)(mid) 时的导数,此时不会出现精度误差。

特殊情况的解法

对于树上的情况,可以 DP 维护分段函数,也可以直接整体二分后跑树形 DP。

5.例题

[省选联考 2020 A 卷] 魔法商店

【2018集训队互测Day2】有向图