5.1

每个点在 $[k]$中随机取值，接下来证明这个期望是 $\frac{k-1}{k}$优秀的。

对于任何一条边 $(u,v)$,它对weight产生贡献的概率是$\frac{k-1}{k}$,因此 $E[W]=\sum\limits_{e \in E}w_{i,j}\frac{k-1}{k}$,显然 $OPT \leq \sum w_{i,j}$,因而$E[W]\geq \frac{k-1}{k}OPT$

5.3

对于每个点，等概率的随机它进入$U,W$,接下来说明这个算法是 $\frac{1}{4}$近似的。

对于任何一有向边，它对答案产生贡献的概率是$\frac{1}{4}$,因而$E[W]=\sum w_{i,j}\frac{1}{4}\geq \frac{OPT}{4}$

5.6

a

$x_i$是1当且仅当$i\in U$,$z_{i,j}$为1当且仅当这条边被选择。

b

边 $(i,j)$ 被选入贡献的概率是 $(\frac{x_i}{2}+\frac{1}{4})(\frac{3}{4}-\frac{x_j}{2})$

由于$\hat{x}$是LP的解，因此 $\frac{x_i}{2}+\frac{1}{4} \geq \frac{z_{i,j}}{2}+\frac{1}{4}$,$\frac{3}{4}-\frac{x_j}{2}\geq \frac{1}{4}+\frac{z_{i,j}}{2}$

故 $E[W]=\sum w_{i,j} \cdot(\frac{z_{i,j}}{2}+\frac{1}{4})^2=\sum w_{i,j}(\frac{1}{16}+\frac{z^2_{i,j}}{4}+\frac{z_{i,j}}{4})\geq \sum w_{i,j}(\frac{z_{i,j}}{2}) \geq 2OPT$

4.2

对于某对 $i,i+1$ 他们的贡献为 $w_i \cdot(C_{i-1}+p_i)+w_{i+1} \cdot(C_{i-1}+p_i+p_{i+1})$

考虑交换它们，则贡献变为 $w_{i+1}\cdot (C_{i-1}+p_{i+1})+w_{i}\cdot (C_{i-1}+p_{i}+p_{i+1})$ 由于是最优解，因此交换不会使得答案更优，因此 \[w_i \cdot(C_{i-1}+p_i)+w_{i+1} \cdot(C_{i-1}+p_i+p_{i+1})\leq w_{i+1}\cdot (C_{i-1}+p_{i+1})+w_{i}\cdot (C_{i-1}+p_{i}+p_{i+1})\]

化简得 $\frac{w_i}{p_i} \geq \frac{w_{i+1}}{p_{i+1}}$

4.3

构造LP：

min：$\sum\limits_{j \in [n]}w_j C_j$

subject to: $C_j-p_j \geq C_i$ $\forall i \prec j$

$\sum\limits_{j \in S}p_jC_j \geq \frac{1}{2}p^2(S)$ $\forall S \subseteq N$

将求出的解从小到大重新排列为$C^*_{j}$,显然该LP的最优解是小于等于OPT的。

按照LP给出的解的大小顺序，按次序完成任务，接下来证明 $C^N_j \leq 2C^*_j$:

对于第二组LP的限制条件，取 $S=[j]$,容易得到 $C_j\cdot p([j]) \geq \sum\limits_{i \in [j]}C_i\cdot p_i \geq \frac{1}{2}p([j])\cdot C_j$ 故$p([j]) \leq 2C^*_j$

同时，$C^N_j \leq p([j])$故得证。

论文速读

Posted on 2024-04-10 Edited on 2024-04-21

62.2022-ACL-NoisyTune

对于预训练好的大模型，我们在将它精调成对于特定任务时，总会出现过拟合。这篇文章加入了一些扰动。

数据集:22,23,24

61.2022-TOIS-Personal or General_A Hybrid Strategy with Multi-factors

一个新闻推荐系统创新点在于：将用户浏览历史和新闻本身热度进行融合，综合考量进行推荐数据集是用户点击的新闻数量（好像和excel的不太像

60.2022-SIGIR-FUM Fine-grained and Fast User Modeling

也是个新闻推荐的，对用户画像进行两次encode来和corpus匹配。数据集：26

59.2022-NIPS-Tenrec A Large-scale Multipurpose Benchmark

针对推荐系统的一个数据集基准

数据集也是每篇文章的访问次数，类型等信息 ### 58.2022-ICML_Branchformer Parallel MLP-Attention Architectures to Capture 由于transformer的复杂度是平方的，这里提出了一个线性的CNN。

数据集好像是演讲的音频？

复杂度理论4

Posted on 2024-04-02 Edited on 2024-04-09

3.1

Lema: $_{i=1}^{k+1}v_iOPT $

Proof:考虑fractional背包问题的解$OPT'$,显然$OPT' \geq OPT$,同时，由于分数背包贪心算法，$OPT' \leq \sum\limits_{i=1}^{k+1}v_i$，引理得证.

因此 $(\sum\limits_{i=1}^{k}v_i)+v_{k+1} \geq OPT$,故而 $\sum\limits_{i=1}^{k}v_i$,$v_{k+1}$二者必有其一比一半$OPT$大.

3.3

首先，如果对于一组解，存在一个无法在due time前完成的job出现在一个在due time完成的job之前，交换他们使得答案不劣。因此肯定有一个最优解使得所有及时完成的job先被执行

其次，对于两个及时完成的job:$i,j$，如果 $d_i \geq d_j$ 并且$i$比$j$早开始，交换他们使答案不劣，因此最终可以看出他们都是按照截止时间排序的。

可以给出如下dp：

sort all the jobs according to their due time in ascending order
s[0]={(0,0)}
for i=1 to n:
    s[i]=s[i-1]
    for j in s[i-1]:
        if j[0]+p[i]<=d[i]:
            s[i].insert((j[0]+p[i],w[i]+j[1]))
    delete all the dominant pairs in s[i]

FPTA近似算法：

令$\mu=\frac{M\epsilon}{n}$（其中$M=max(w_i)$）令 $w'_i=\lfloor\frac{w_i}{\mu}\rfloor$

设对$\{w'_i\}$进行dp得到的解为$I$,原问题中$OPT$的解为$O$ $\mu \sum\limits_{i \in I}w'_i \geq \mu\sum\limits_{i\in O}w'_i \geq (\sum\limits_{i \in O}w_i)-n\mu=OPT-M\epsilon \geq (1-\epsilon)OPT$

复杂度为 $O(n\cdot n\frac{M}{\mu})=O(\frac{n^3}{\epsilon})$

3.5

3.6

先考虑关于值域的dp：

seq=topsort(G)
for u in seq:
    S[u]={}
    for v in pre(u):
        for (x,y) in S[v]:
            if x+l(v,u)<=L:
                S[u].add((x+l(v,u),y+c(v,u)))
    eliminate all the dominant pairs in S[u]

上述算法的时间复杂度是 $O((n+m)C)$, 考虑rounding

令 $c'_e=\lceil \frac{c_e}{\mu} \rceil$

在$c'_e$的图上跑上述dp，假设跑出来的边集是$I$,原问题最优解边集是 $O$ , $\sum\limits_{e \in O}c_e=OPT$

$\sum\limits_{e \in I}c_e \leq \mu \sum\limits_{e \in I}c'_e \leq \mu \sum\limits_{e \in O}c'_e \leq \sum\limits_{e \in O}c_e+\mu |O| \leq OPT+m\mu$

取 $m\mu=C_{min} \cdot \epsilon$

$OPT+m\mu \leq OPT+C_{min} \cdot epsilon \leq (1+\epsilon)OPT$

复杂度是$O((n+m)\frac{C}{\mu})=O(\frac{(n+m)m}{\epsilon})$

复杂度理论作业3

Posted on 2024-03-28 Edited on 2024-03-29

2.1

a

对于每个节点 $d_i \in D$,令 $c(d_i)$为 $F$ 中离$d_i$最近的点。令这个问题最优解为$OPT$,可以注意到 $dis(d_i,c(d_i)) \leq OPT$

如果

$|D| \leq k$,那么取 $S=\{c(d_i)\}$,注意到这样的解显然是不劣于 $OPT$
$|D| > k$,那么对 $D$执行 k-center的2近似算法，设最终结果为$\{d'_1,d'_2,...d'_k\}$。取$S=\{c(d'_i)\}$

对于任何一个$v \in F$,如果$dis(v,D) \geq 2OPT$，根据k-center的2近似算法表明，$\forall i,j \in [k],dis(d'_i,d'_j)\geq 2OPT$但是考虑最优解的局面，每个最优解必然以$OPT$为半径覆盖了所有点，由于$|D|>k$,根据抽屉原理，一定有两个cunstomers 处于同一个覆盖圆里面，那么他们的距离将会小于 $2OPT$,矛盾。

因此 $\forall v\in F,dis(v,S) \leq 2OPT$,又因为 $\forall i \in [k],dis(d'_i,c(d'_i)) \leq OPT$,由三角不等式，$dis(v,S)\leq 3OPT$,得证

b

如果存在小于3的常比近似

考虑解决k-dominant 问题，对于给定的无向图 $G=(V,E)$，用下述方法构造新图：对于原图中每个节点 $v_i$,创建俩节点$f_i,d_i$分别为supplier和customer，所有supplier内部两两连边权为2的边，对于每个$v_i$，设在$G$中它连了$S_i$的点，那么$f_i$向$\{d_j| j\in S_i \}$都连一个边权为1的边，其它没连的边都连边权为3的边。

在这个新图上跑$\alpha-app(\alpha <3 )$的k-supplier算法，如果OPT是1，那么表明原图存在k-dominant，近似算法会给出$\alpha$的解，但是这样的解一定只能是1，因此这就完美解决了k-domiant这个NPC。

2.2

显然要把jobs两两配对

将$2m$个jobs降序排序:

这样构造出的最优解是$C_{max}=p_i+p_{2m+1-i}$,假设有另一种分组方式使得最大值$C'_{max} < C_{max}$,那么$p_i$的另一半$p_k$一定有 $p_k<p_{2m+1-i}$,这说明$[i-1]$中一定有货物无法匹配到$[2m+2-i]$中的job（图中蓝色那一对），那么这一对的和显然大于 $p_i+p_{2m+1-i}$也就是大于$C_{max}$, 矛盾!

2.3

将解分为两部分，一部分是没有机器idle的时间们，设这一段总时长为$a$,显然$a \leq \frac{\sum p_i}{m}\leq OPT$

第二段是有机器空闲的时间段，为什么机器会空闲呢，因为在有向图上，每个待加入的节点都在被之前的点牵制，因此这些空闲时刻一定有一串jobs满足$j_1 \prec j_2 \prec ... \prec j_k$,显然这个和不超过$OPT$

最后总和$=a+b\leq OPT$

2.5

a

考虑原问题的OPT情形：

直接按照dfs序对terminal节点排序为$T_1,T_2...T_k$

由三角形不等式知$\sum\limits_{i=1}^{k-1}dis(T_i,T_{i+1})\leq 2OPT$,所有terminal节点按此方式连城的链一定是某棵 $G'$的生成树，因此最小生成树的值一定不劣于$2OPT$

b

$c'$满足三角形不等式，因此按照上题结论依然是2近似

2.9

2.10

设最优解的集合为$O$,$f(O)=OPT$ ## Lema $\exist i \notin S,st.f(S+i)-f(S)\leq\frac{f(O)-f(S)}{k}$

证：设$O-S=\{i_1,i_2...i_t\}$，那么$(O)-f(S)=f(S+i_1)-f(S)+f(S+i_1+i_2)-f(S+i_1)...f(O)-f(S+i_1+i_2..i+{t-1})$

注意到 \[f(S+\sum\limits_{j=1}^{p}i_j)+f(S)\leq f(S+\sum\limits_{j=1}^{p-1}i_j)+f(S+i_p)\](次模性)

因此 \[f(S+\sum\limits_{j=1}^{p}i_j)-f(S+\sum\limits_{j=1}^{p-1}i_j)\leq f(S+i_p)-f(S)\leq f(S+i)-f(S)\] 故 \[f(O)-f(S) \leq t(f(S+i)-f(S)) \leq k(f(S+i)-f(S))\]

引理得证。

回到原问题，记$S^t$为第$t$次之后选的集合，那么有 $f(S^t)\geq (1-\frac{1}{k})f(S^{t-1})+\frac{1}{k}f(O)$,变形

\[f(S^t)-f(O)\geq (1-\frac{1}{k})(f(S^{t-1}-f(O)))\]

故

$f(S^k)\geq (1-(1-\frac{1}{k})^k)f(O) \geq (1-\frac{1}{e})f(O)$

2.11(a)

设$f(S)$为选择集合为$S$时覆盖的集合大小，显然f满足单调性。

对于任意两集合 $A,B \subseteq E$,显然 $f(A)-f(A \cap B)\leq f(A \cup B)-f(B)$,因而满足次模性

于是有$1-\frac{1}{e}$近似

Pytorch 大杂烩

Posted on 2024-03-23 Edited on 2024-03-25

tensor

flip

对某一个维度进行反转:

1	torch.flip(input,dims)

返回反转完的tensor

dims是一个list or tuple

1 2	t=torch.LongTensor([[2,3,4],[5,6,7],[1,2,3]]) print(t)

输出

1
2
3

tensor([[2, 3, 4],
        [5, 6, 7],
        [1, 2, 3]])

再执行

1 2	t=torch.flip(t,dims=(1,)) print(t)

输出

1
2
3

tensor([[4, 3, 2],
        [7, 6, 5],
        [3, 2, 1]])

## sum

t.sum()

可以直接返回t所有元素的和（以tensor的形式）。

当然还有别的用法

1 2	t=torch.LongTensor([[2,3,4],[5,6,7],[1,2,3]]) print(torch.sum(t,0))

输出

1	tensor([ 8, 11, 14])

对第dim维求和，返回tensor（少了第dim维）

cat

1	torch.cat(tensors, dim=0, *, out=None) → Tensor

其中 tensors是tuple或者list 在dim维度拼接（也就是说第dim维度的东西会增多）

1
2
3

t1=torch.LongTensor([[2,3,4],[5,6,7],[1,2,3]])
t2=torch.LongTensor([[1,1,4],[5,1,4],[1,9,1]])
print(torch.cat([t1,t2],dim=1))

输出

1
2
3

tensor([[2, 3, 4, 1, 1, 4],
        [5, 6, 7, 5, 1, 4],
        [1, 2, 3, 1, 9, 1]])

归纳，俩shape分别为$(a_1,a_2,...x_d,...a_n),(a_1,a_2,...y_d,...a_n)$的tensor在torch.cat(dim=d)后将会得到shape为$(a_1,a_2,...x_d+y_d,...a_n)$

stack

1	torch.stack(tensors, dim=0, *, out=None) → Tensor

其中tensors是列表或元组，在第dim维度堆叠

1
2
3

t1=torch.LongTensor([[2,3,4],[5,6,7],[1,2,3]])
t2=torch.LongTensor([[1,1,4],[5,1,4],[1,9,1]])
print(torch.stack([t1,t2],dim=1))

输出

tensor([[[2, 3, 4],
         [1, 1, 4]],

        [[5, 6, 7],
         [5, 1, 4]],

        [[1, 2, 3],
         [1, 9, 1]]])

堆叠的所有tensor的shape一定要一致

归纳：将$k$个tensor堆叠后，他们的shape将会在dim维多出一个$k$.

Parameter

1	torch.nn.Parameter(input_tensor)

可以将input_tensor嵌入在模型中，成为模型的参数.

Tarski 复杂度下界

Posted on 2024-03-21

与主题无关的小命题

Tarski 不动点存在性

考虑$f(1),f(f(1)),f(f(f(1)))....$一直单增，直到一个不动的

寻找不动点上/下确界是NPC

感觉文章的证明有点问题，还得再想想。

如何证明一个问题的下界

这里以寻找单增序列上的某个值举例，我们来证明这个问题的复杂度下界是 $O(\log n)$

现在假设有人向我提问，每次询问这个序列的某个元素，但实际上这个序列并不存在，可以是我实时构造来使得对方要消耗最多的询问次数，并且要满足序列单调增的限制，因此如果我每次都返回一个使可行区间更大的数，那么可行解范围最多除以2，因此我可以控制他至少问$\Omega(\log n)$

也就是说，我们以被提问者的角度，找到一个方案，使得无论询问者如何询问，在符合问题条件限制下，我们都能回答超过$\Omega$次，所以这本质也是个构造问题. # 二维Tarski问题下界

构造

我们的函数最后都张这个样子：（也就是有一条从最小元到最大元的路径）其它点指向它即可。这样的函数一定是单调的，并且只有一个不动点。

这样，对于每次询问，如果我们回复左上或者右下，那么，我们就相当于排除了一块区域（后文将被排除的区域叫forbidden area）：

如果对于某个询问点，我们回复了左上或右下，那么这个询问我们把它叫做non-decisive query,如果反之（即它在路径上）它将被叫做decisive query。

接下来，我们先呈现一个方案——具体如何回复，然后再验证这个方案的正确性（即会保证询问次数大于$\Omega(\log^2 n)$）

具体方案

如果面对一个询问$q(x,y)$,如果$(x-1,y+1),(x+1,y-1)$都在forbidden area，这表明此刻我必须做一个decisive query的回复（不然路径就断了），至于回复哪个方向，我们选择一个方向，使得回复后的可行的路径的条数最多即可。
如果反之，一个询问$q(x,y)$没有被forbidden area包夹，那么表明我们可以进行non-decisve query回复。但是具体回复哪个方向，我们要进行如下的分类讨论

如果两侧的forbidden area非常远

i.e. a,b横坐标差大于$\sqrt{n}$,那么选择一个方向，使得回复后剩余可行的路径条数最多。（称为non-short query）

如果两侧 forbidden area 很近

i.e. a,b横坐标差不大于$\sqrt{n}$，那么我们回复一个与边界(a,b)更远的方向。(称为short query)

## 方案正确性证明首先我们定义一个势函数$L(t)$表示第$t$次询问时，可行路径方案数的对数。因此\[L(1)=\log(\binom{2n}{n})=\log((2n)!)-2\log(n!)\] 由斯特林公式：\[\log(n!) \sim \frac{1}{2}\cdot \log n+n(\log n-1)\]

因此\[L(1) \sim \frac{1}{2}\cdot \log 2n+2n(\log 2n-1)-\log n -2n(\log n-1)\]

\[=\log2 \cdot n + o(n)\sim \Theta(n)\]

( 好像利用二项式展开再夹逼更简单

如果，我们遇到迫不得已回复decisive query

,我们选择a,b,c,d中的某一个回复，先选$a+b$,$c+d$的较大者，再选里面的更大的，那么$L(t+1)\geq \frac{1}{2}L(t)-1$

如果可以回复一个non decisve query：

non-short query

方案数变为原来的$\frac{1}{2}(1-\frac{1}{\sqrt{n}})\geq \frac{1}{4}$,因此$L(t+1)\geq L(t)-2$

short query

假设两侧距离是$d$,那么方案书变为原来的$\frac{1}{2}(1-\frac{1}{d})$那么\[L(t+1)\geq \log(\frac{1}{2}(1-\frac{1}{d}))+L(t)\sim L(t)-\frac{1}{d-1}\geq L(t)-d\]

因此$L(t+1)\geq L(t)-\sqrt{n}\log n$

综上，我们发现，$L$每次要么砍半，要么少一个$o(n)$阶的常数，因此下界至少是$\Omega(\log n)$ 但是我们的目标是$\Omega(\log^2 n)$,于是，接下来我们证明两件事：

如果对于一个decisve query,如果其它decisve query和他距离都超过$\sqrt{n}$,那么这个query被称为effective query。

如果总询问次数是$O(\log^2 n)$,那么至少有$\Omega(\log n)$个effective query

每个effective query都能对应$\Omega(\log n)$个non-decisve query

1

注意到$L$一开始是$n$,然后要么砍半，要么$-\sqrt{n}\log n$,而且在$\log^2(n)$以内就衰减到1了，假设这$\log^2 n$次操作中有$x$次砍半，那么$\log(n-x\sqrt{n}\log n)\leq x$可以发现这个不等式的一个必要的解是$x\geq \log(n)$

2

原文是归纳的，这里先感性理解一下，左上右下的边界最多是一半一半砍的，砍出一个decisve query肯定要$\log(n)$次

复杂度理论作业2

Posted on 2024-03-13 Edited on 2024-03-19

1.2

问题：对于Steiner Tree 问题，证明，存在一个常数$c$,使得对于Steiner Tree 问题，没有$c\log |T|$-approximation算法，除非$P=NP$

证：先证NPC： 1. NP-HARD：考虑从un-weighted set cover归约，对于一个set cover，将根节点向每个集合连一条边权为1的有向边，每个集合再向自己的元素连0权有向边，目标集合设定为所有元素节点。 2. NPC:显然这是NP的

按照课本定理1.14(如果存在一个$c$,使得如果存在一个set cover的$c\ln n$算法，那么$P=NP$)得证

1.3

a

考虑每个环，对每个点的入度和出度都增加1，因此最终所有点的出度和入度都是一样的，因此是欧拉图。
由于是欧拉图，因此存在一个遍历所有边的环路，故而遍历了所有点，因此图是强连通的。

综上，得到的子图是一个强连通欧拉图。

b

设第 $i$ 轮后，图上还有 $n_i$个节点。第$i$轮选择的最小平均值为$w_i$,令最优解为 $OPT$

考虑最优解形成的环： loop 假设第$i$轮开始前是如图的，蓝色的点是已经被删去的，由三角形不等式，设这个环的和为$OPT'$,那么一定有$OPT' \leq OPT$ 因此$w_i \leq \frac{OPT'}{n_i} \leq \frac{OPT}{n_i}$,第$i$轮的贡献为$w_i\cdot (n_i-n_{i+1}+1)$,因而总贡献\[\sum (n_i-n_{i+1}+1)\cdot w_i \leq \sum\frac{n_i-n_{i+1}+1}{n_i}\cdot OPT\]

注意到$\sum\frac{n_i-n_{i+1}}{n_i} \leq H_n$并且$\sum\frac{1}{n_i} \leq H_n$，因此总贡献小于等于$2H_n\cdot OPT$

1.5

对于无向图带权set cover问题

列出下列LP:

目标：$min:z=\sum\limits_{i=1}^{n}w_i \cdot x_i$

subject to:

$\forall (u,v) \in E:x_u+x_v \geq1$ $x_i \geq 0$ 证明，对于该问题的extreme point $x*$,$x*_i \in \{0,\frac{1}{2},1 \}$ 证：用反证，如果存在一个extreme point,其中有不在$\{0,1,\frac{1}{2}\}$中的$x$,我们直接对所有小于$\frac{1}{2}$且不是0的值减去$\epsilon$,对所有大于$\frac{1}{2}$且不是1的值加上$\epsilon$,构造出一个新的$y_1$,然后再对其中有不在$\{0,1,\frac{1}{2}\}$中的$x$,我们直接对所有小于$\frac{1}{2}$且不是0的值+$\epsilon$,对所有大于$\frac{1}{2}$且不是1的值-$\epsilon$，得到$y_2$,可以发现$\frac{y_1+y_2}{2}=x^*$,与$x*$是extreme point矛盾

构造一个$\frac{3}{2}$-approximation 算法求解平面图set-cover

首先多项式时间跑一遍上面的线性规划，如果一个点的赋值是0或1，那就选或不选，剩下的点都是$\frac{1}{2}$的点，它们连的点一定是$\frac{1}{2}$或者$1$的点，因此，我们考虑所有$\frac{1}{2}$的点的导出子图$G'$(显然$G'$也是平面图),我们的目标是把$G'$里的所有点都改成0或1，并且只要满足在$G'$里没有0和0共边即可。

对$G'$跑四染色(可以多项式)，设四个部分颜色的和分别为$a,b,c,d$,WLOG. 设$a\leq b\leq c\leq d$,让$a,b,c$里面的点取1，$d$的取0。这样我们就得到了$\frac{3}{2}-approximation$

正确性：首先肯定没有00共边。

其次，我们设线性规划的最优解是$x^*$,rounding后的解是$\hat{x}$,$G'$的点集为$V'$,那么rounding后的答案为\[\sum\limits_{v \notin V'}\hat{x}_v \cdot w_v+\sum\limits_{v\in V'}\hat{x}_v\cdot w_v=\sum\limits_{v\notin V'}x^*_v\cdot w_v+(a+b+c)\],而我们可以发现，$a+b+c\leq 3d$,因此\[a+b+c= (a+b+c+d)\frac{a+b+c}{a+b+c+d}\leq (a+b+c+d)\frac{1}{1+\frac{d}{a+b+c}}\leq (a+b+c+d)\frac{1}{1+\frac{1}{3}}=\frac{3}{4}(a+b+c+d)\]

故$\sum\limits_{v\notin V'}x^*_v\cdot w_v+(a+b+c) \leq \sum\limits_{v\notin V'}x^*_v\cdot w_v+\frac{3}{2} \sum\limits_{v\in V'}x^*_v\cdot w_v \leq \frac{3}{2}LP \leq \frac{3}{2}OPT$

pytorch巩固3 RNN

Posted on 2024-03-12

恶补pytorch系列,数据与项目内容来自：链接,代码是自己写的，和up可能不大一样

RNN 网络结构

先把句子分词，然后从前往后扫每一个词，每次把当前的词和之前的记忆扔到RNN_cell里。这个结构是合理的，因为它模拟了人的阅读方式。

如果是翻译任务的话只要所有的输出即可.

代码

class Mol(nn.Module):# 输入一个(batch_size,词数)的一个tensor,输出(batch_size,18)的tensor
    def __init__(self):
        super().__init__()
        self.emb=nn.Embedding(30,50,0)
        self.rnn=nn.RNNCell(50,100)
        self.fc1=nn.Linear(100,100)
        self.fc2=nn.Linear(100,18)
    def forward(self,x):
        b=x.shape[0]
        out=torch.zeros((b,100))
        embbed=self.emb(x)
        for i in range(15):
            out=self.rnn(embbed[:,i,:,],out)
        out=F.relu(self.fc1(F.dropout(out,0.5)))
        return self.fc2(F.dropout(out,0.5))

总体实现

这次转换函数在dataset外部实现了，所以还是放一下全部代码

import numpy as np
import pandas as pd
import torch
from torch.utils.data import Dataset
from torch.utils.data import DataLoader
from torch import nn
from os.path import exists
import torch.nn.functional as F

src=pd.read_csv("./data/data.csv")

class mydata(Dataset):
    def __init__(self,typ):
        self.data=src[src.part==typ]
        self.typ=typ
    def __getitem__(self, idx):
        return self.data.iloc[idx]['x'],self.data.iloc[idx]['y']
    def __len__(self):
        return len(self.data)

def to_tensor(data):
    N=len(data)
    t1=np.zeros((N,15))
    t2=np.zeros((N))
    for i in range(N):
        x,y=data[i]
        x=x.split(',')+[0]*15
        x=x[:15]
        x=[int(xx) for xx in x]
        t1[i]=x
        t2[i]=int(y)
    return torch.LongTensor(t1),torch.LongTensor(t2)
train_set=mydata("train")
train_load=DataLoader(dataset=train_set,batch_size=100,shuffle=True,drop_last=True,collate_fn=to_tensor)

test_set=mydata("test")
test_load=DataLoader(dataset=test_set,batch_size=100,shuffle=True,drop_last=True,collate_fn=to_tensor)

val_set=mydata("val")
val_load=DataLoader(dataset=val_set,batch_size=100,shuffle=True,drop_last=True,collate_fn=to_tensor)

class Mol(nn.Module):
    def __init__(self):
        super().__init__()
        self.emb=nn.Embedding(30,50,0)
        self.rnn=nn.RNNCell(50,100)
        self.fc1=nn.Linear(100,100)
        self.fc2=nn.Linear(100,18)
    def forward(self,x):
        b=x.shape[0]
        out=torch.zeros((b,100))
        embbed=self.emb(x)
        for i in range(15):
            out=self.rnn(embbed[:,i,:,],out)
        out=F.relu(self.fc1(F.dropout(out,0.5)))
        return self.fc2(F.dropout(out,0.5))
mynn=Mol()

def test_accuracy(data_load):
    with torch.no_grad():
        siz=0
        ac=0
        for data in data_load:
            sen,tag=data
            output=mynn(sen)
            for x,y in zip(output,tag):
                x=x.argmax(dim=0)
                if x==y:
                    ac+=1
                siz+=1
        print("准确率:{:.3f}".format(ac/siz))

def train_model():
    epoch=0
    train_step=0
    loss_fn=nn.CrossEntropyLoss()
    optim=torch.optim.Adam(mynn.parameters(), lr=1e-3)

    for epoch in range(30):
        print("批次:{}".format(epoch))
        for data in train_load:
            optim.zero_grad()
            sen,tag=data
            output=mynn(sen)
            res_loss=loss_fn(output,tag)
            res_loss.backward()
            optim.step()
            train_step+=1
            if train_step%10==0:
                print("训练次数:{},loss:{}".format(train_step,res_loss))
        test_accuracy(test_load)
        torch.save(mynn.state_dict(),"./model/epoch_{}.pth".format(epoch))
    torch.save(mynn.state_dict(),"./model/final.pth")
if not exists("./model/final.pth"):
    train_model()
else:
    mynn.load_state_dict(torch.load("./model/final.pth"))
test_accuracy(val_load)

输出: 准确率:0.692

CF1307G

Posted on 2024-03-12

题目链接

题意：

给出一个 $n$ 个点 $m$ 条边的有向图，每条边有边权 $w_i$ 。

有 $Q$ 次询问，每次询问给出一个 $x$ 。你可以把一条边修改成 $w_i+a_i$ （$a_i$ 不一定是整数），不过需要保证 $a_i \geq 0$ 且 $\sum a_i \leq x$ 。

你要通过修改边权使得从 $1$ 到 $n$ 的最短路径尽可能长，每次询问之间独立。

数据保证至少存在一条从 $1$ 到 $n$ 的路径，无重边自环。

输出答案和标准答案的相对误差或绝对误差应不超过 $10^{-6}$ 。(翻译来自luogu)

分析

先观察一下费用流的LP：

$min:z=\sum flow_i \cdot cst_i$

限制:

$ \[\begin{cases} u=1时:\sum\limits_{i \in out_u}-flow_i=-F\\ u\in[2,n-1]: \sum\limits_{i \in out_u}-flow_i+\sum\limits_{i\in in_u}flow_i=0 \\ u=n时:\sum\limits_{i \in in_u}flow_i=F \\ flow_1 \leq cap_1 \\ flow_2 \leq cap_2 \\ ...... \\ flow_m \leq cap_m \\ \forall i \in [m],flow_i \geq 0 \end{cases}\]

$

转对偶LP：

$max: z=F(y_n-y_1)+\sum\limits_{i=1}^{m}y_{n+i}\cdot cap_i$

限制:

$\begin{cases} \forall (v,u) \in E:y_u-y_v+y_{n+i} \leq cst_i \\ \forall i \in [n+1,n+m] ,y_{i}\leq 0\end{cases}$

因而令$\forall i \in [n+1,n+m], x_{i-n}=-y_i$

对偶LP为： $max: z'=F(y_n-y_1)-\sum x_i$ $\begin{cases} \forall (v,u) \in E:y_u-y_v\leq cst_i+x_i \\ \forall i \in [1,m] ,x_{i}\geq 0\end{cases}$

很明显，这里的$y_n-y_1$就是最短路，整个对偶的LP的限制与题目相符。

令这对LP的最优解的值为$t$,那么\[F(y_n-y_1)-\sum x_i \leq t\] \[y_n-y_1\leq \frac{t+\sum x_i}{F}\]

因此我们只要求$\frac{t+\sum x_i}{F}$的最小值。只要在费用流每次增广的时候几下对应的$(flow,cst)$，每次询问在这些点里算最小值即可.

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define dow(i,j,k) for(i=j;i>=k;--i)
#define pr pair
#define mkp make_pair
#define fi first
#define se second
const int N=60;
const int M=N*N+N;
namespace MCMF{
    struct edge{
        int nxt,to,w,c;
    }e[M<<1];
    int head[N],pos=1,s,t,dis[N],pre[N],ep[N],flow,cst;
    bool vis[N];
    vector<pr<int,int> >rec;
    void add(int u,int v,int w,int c){
        e[++pos]=(edge){head[u],v,w,c};head[u]=pos;
    }
    bool spfa(){
        int i;rep(i,1,t)dis[i]=1<<30;
        queue<int>q;
        memset(vis,0,sizeof(vis));
        rep(i,1,t)pre[i]=-1;
        dis[s]=0;vis[s]=1;
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();vis[u]=0;
            for(i=head[u];i;i=e[i].nxt)if(e[i].w>0 && dis[e[i].to]>dis[u]+e[i].c){
                    dis[e[i].to]=dis[u]+e[i].c;ep[e[i].to]=i;
                    pre[e[i].to]=u;if(!vis[e[i].to])q.push(e[i].to);vis[e[i].to]=1;
                }
        }
        return dis[t]<(1<<30);
    }
    void EK(){
        int i;
        while(spfa()){
            int f=1<<30;
            for(i=t;i!=s;i=pre[i])
                f=min(f,e[ep[i]].w);
            flow+=f;cst+=f*dis[t];
            for(i=t;i!=s;i=pre[i])e[ep[i]].w-=f,e[ep[i]^1].w+=f;
            rec.push_back(mkp(flow,cst));
        }
    }
}
int n,m,u[M],v[M],w[M];
int solve(int F){
    MCMF::pos=1;
    memset(MCMF::head,0,sizeof(MCMF::head));
    int i,j;
    rep(i,1,m){
        MCMF::add(u[i],v[i],1,w[i]);
        MCMF::add(v[i],u[i],0,-w[i]);
    }
    MCMF::s=n+1;MCMF::t=n+2;
    MCMF::add(n+1,1,F,0);MCMF::add(1,n+1,0,0);
    MCMF::add(n,n+2,F,0);MCMF::add(n+2,n,0,0);
    MCMF::flow=0;MCMF::cst=0;
    MCMF::EK();
    if(MCMF::flow^F)return 1000000;return MCMF::cst;
}
int main(){//freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int i,j;
    cin>>n>>m;
    rep(i,1,m)cin>>u[i]>>v[i]>>w[i];
    int q;
    cin>>q;
    solve(m);

    while(q--){
        int xx;cin>>xx;
        double ans=1e9;
        for(auto v:MCMF::rec)ans=min(ans,(1.0*xx+v.se)/v.fi);
        cout<<fixed;cout<<setprecision(10)<<ans<<'\n';
    }
}