2024年9月

前置芝士

$\LARGE {关于二叉搜索树及平衡树无聊的一大串子定义}$

二叉搜索树(BST树)

定义

二叉搜索树是一种二叉树的树形数据结构,其定义如下:

  • 空树是二叉搜索树。

  • 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。

  • 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。

  • 二叉搜索树的左右子树均为二叉搜索树。

复杂度

二叉搜索树上的基本操作所花费的时间与这棵树的高度成
\(\color{#40c0bb}{正比}\)
。对于一个有
\(n\)
个结点的二叉搜索树中,这些操作的最优时间复杂度为
\(O(\log n)\)
,最坏为
\(O(n)\)
。随机构造这样一棵二叉搜索树的
\(\color{#40c0bb}{期望高度}\)

\(O(\log n)\)

性质

其实也就是定义


\(x\)
是二叉搜索树中的一个结点。

如果
\(y\)

\(x\)
左子树中的一个结点,那么
\(y.key≤x.key\)

如果
\(y\)

\(x\)
右子树中的一个结点,那么
\(y.key≥x.key\)

在二叉搜索树中:

  1. 若任意结点的左子树不空,则左子树上所有结点的值均不大于它的根结点的值。

  2. 若任意结点的右子树不空,则右子树上所有结点的值均不小于它的根结点的值。

  3. 任意结点的左、右子树也分别为二叉搜索树。

用途

二叉搜索树通常可以高效地完成以下操作:

  1. 查找最小/最大值

  2. 搜索元素

  3. 插入一个元素

  4. 删除一个元素

  5. 求元素的排名

  6. 查找排名为 k 的元素

平衡树

定义

由二叉搜索树的复杂度分析可知:操作的复杂度与树的高度
\(h\)
有关。

那么我们可以通过一定操作维持树的高度(平衡性)来降低操作的复杂度,这就是
\(\color{#40c0bb}{平衡树}\)

\(\color{#40c0bb} \large \textbf{平衡性}\)
通常指每个结点的左右子树的高度之差的绝对值(平衡因子)最多为
\(1\)

平衡的调整过程——树旋转

定义

树旋转是在二叉树中的一种子树调整操作, 每一次旋转并
\(\color{#40c0bb}{不影响}\)
对该二叉树进行
\(\color{#40c0bb}{中序遍历}\)
的结果。
树旋转通常应用于需要调整树的局部平衡性的场合。树旋转包括两个不同的方式,分别是
\(\color{#40c0bb}{左旋(Left Rotate 或者  zag)}\)

\(\color{#40c0bb}{右旋(Right Rotate 或者 zig)}\)
。 两种旋转呈镜像,而且互为逆操作。

具体操作

右旋

对于结点
\(A\)
的右旋操作是指:将
\(A\)
的左孩子
\(B\)
向右上旋转,代替
\(A\)
成为根节点,将
\(A\)
结点向右下旋转成为
\(B\)
的右子树的根结点,
\(B\)
的原来的右子树变为
\(A\)
的左子树。

左旋

完全同理

具体情况

其实你只需要知道二叉搜索树的几条基本性质即可:

  1. 每个结点都满足左子树的结点的值都
    小于
    自己的值,右子树的结点的值都
    大于
    自己的值,
    左右子树也是二叉搜索树

  2. 中序遍历二叉搜索树可以得到一个由这棵树的所有结点的值组成的
    有序
    序列。(即所有的值排序后的结果)

正片

背景

不难发现
\(BST树\)
的一种极端情况:
\(\color{#40c0bb}{退化情况}\)

这种
毒瘤
数据让时间复杂度从
\(O(log(n))\)
退化到了恐怖的
\(O(n)\)

于是就有各种各样的科学家们,开始思考人生,丧心病狂地创造出了各种优化BST的方法...

Splay

定义

啥是
\(Splay\)

她实际上就是一种可以旋转的平衡树。
她可以通过
Splay/伸展操作
不断将某个节点旋转到根节点,使得整棵树仍然满足二叉查找树的性质,能够在均摊
\(O(\log n)\)
时间内完成插入,查找和删除操作,并且保持平衡而不至于退化成链。

原理&实现

节点维护信息

rt tot fa[N] ch[N][2] val[N] cnt[N] sz[N]
节点编号 父节点 子节点 左0右1 权值 节点大小 子树大小

基本操作

首先你要了解的就是一些基本操作:

  • \(maintain(x)\)
    :在改变节点位置后,将节点
    \(x\)

    \(\text{size}\)
    更新。
  • \(get(x)\)
    :判断节点
    \(x\)
    是父亲节点的左儿子还是右儿子。
  • \(clear(x)\)
    :清空节点
    \(x\)

void maintain(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
	
bool get(int x){
	return x==ch[fa[x]][1];
}
	
void clear(int x){
	ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
}

很简单对吧?

接下来可就要上难度了。

旋转操作(rotate)

由定义可知,我们要将某个节点旋转到根节点。

而要想知道怎么将一个节点旋转到根节点,首先要考虑怎么将她旋转到父亲节点。

当该节点为左儿子时

如图,方框表示子树,圆框表示节点

现在,我们要将
\(x\)
节点往上爬一层到他的父节点
\(y\)
,为了保证不改变中序遍历顺序,我们可以让
\(y\)
成为
\(x\)
的右儿子。

但是原来的
\(x\)
节点是有右儿子
\(B\)
的,显然我们要把
\(B\)
换一个位置才能达到目的。

我们知道:
\(x\)
节点的右子树必然是大于
\(x\)
节点的;
\(y\)
节点必然是大于
\(x\)
节点的右子树和
\(x\)
节点本身的(因为
\(x\)
节点及其右子树都是原来
\(y\)
的左子树,肯定比
\(y\)
小(根据二叉搜索树性质))

因此我们可以把
\(x\)
节点原来的右子树放在
\(y\)
的左儿子的位置上,达成目的。

实际上,这也就是
\(\color{#40c0bb}\textbf{右旋}\)
的原理。

当该节点为右儿子时

原理相同。

旋转为

通解

若节点
\(x\)

\(y\)
节点的位置
\(z\)
(
\(z=0\)
为左节点,
\(z=1\)
为右节点 )


  1. \(y\)
    节点放到
    \(x\)
    节点的
    \(z \oplus 1\)
    的位置.(也就是,
    \(x\)
    节点为
    \(y\)
    节点的右子树,那么
    \(y\)
    节点就放到左子树,
    \(x\)
    节点为
    \(y\)
    节点左子树,那么
    \(y\)
    节点就放到右子树位置)

  2. 如果说
    \(x\)
    节点的
    \(z \oplus 1\)
    位置上,已经有节点,或者一棵子树,那么我们就将原来
    \(x\)
    节点
    \(z \oplus 1\)
    位置上的子树,放到
    \(y\)
    节点的位置
    \(z\)
    上面.

这里有个小口诀:“
左旋拎右左挂右,右旋拎左右挂左

看懂文字了,就可以尝试理解一下代码了。

实现

void rotate(int x){
	int y=fa[x],z=fa[y],chk=get(x);
    //y为x的父亲,z为x的爷爷,chk判断x是左儿子还是右儿子

	ch[y][chk]=ch[x][chk^1];
	if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
	ch[x][chk^1]=y;
	fa[y]=x;
	fa[x]=z;
	if(z) ch[z][y==ch[z][1]]=x;
	maintain(y),maintain(x);
}

Splay操作

Splay(x,to)
是要将
\(x\)
节点旋转至
\(to\)
节点。

单旋

很暴力的办法,对于
\(x\)
节点,每次上旋至
\(fa[x]\)
,直到
\(to\)
节点。

但是,如果你真的这么写可能会
T成SB
被某些毒瘤数据卡成

\(n^2\)

所以不要看单旋简单好写,这里更推荐双旋的写法。

双旋

双旋的优化在于:

  1. 如果当前处于共线状态的话,那么先旋转
    \(y\)
    ,再旋转
    \(x\)
    。这样可以强行让他们不处于共线状态,然后平衡这棵树.

  2. 如果当前不是共线状态的话,那么只要旋转
    \(x\)
    即可。

void splay(int x,int goal=0){
	if(goal==0) rt=x;
	while(fa[x]!=goal){
		int f=fa[x];
		if(fa[fa[x]]!=goal){
			rotate(get(x)==get(f)?f:x);
		}
		rotate(x);
	}
}

查找操作

当然你也可以不写。

查找操作是因为查
\(k\)
的前驱后继时需要将
\(k\)
旋到根节点的位置。

实际上你也可以直接
splay(k,0)
或先插入
\(k\)
查询后再将它删去。

Splay也是一颗二叉搜索树,因此满足左侧都比他小,右侧都比他大。

因此只需要相应的往左/右递归即可。

void find(int x){
    int u=root;
    if(!u)return;//树空
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}

插入操作

  • 如果树空了,则直接插入根并退出。
  • 如果当前节点的权值等于
    \(k\)
    则增加当前节点的大小并更新节点和父亲的信息,将当前节点进行 Splay 操作。
  • 否则按照二叉查找树的性质(左侧都比他小,右侧都比他大)向下找,找到空节点就插入即可。
void ins(int k){//insert
	if(!rt){
		val[++tot]=k;
		cnt[tot]++;
		rt=tot;
		maintain(rt);
		return;
	}
	int cur=rt,f=0;
	while(1){
		if(val[cur]==k){
			cnt[cur]++;
			maintain(cur);
			maintain(f);
			splay(cur);
			break;
		}
		f=cur;
		cur=ch[cur][val[cur]<k];
		if(!cur){
			val[++tot]=k;
			cnt[tot]++;
			fa[tot]=f;
			ch[f][val[f]<k]=tot;
			maintain(tot);
			maintain(f);
			splay(tot);
			break;
		}
	}
}

查询
\(x\)
的排名

  • 如果
    \(x\)
    比当前节点的权值小,向其左子树查找。
  • 如果
    \(x\)
    比当前节点的权值大,将答案加上左子树(
    \(size\)
    )和当前节点(
    \(cnt\)
    )的大小,向其右子树查找。
  • 如果
    \(x\)
    与当前节点的权值相同(已存在),将答案加
    \(1\)
    并返回。
int rk(int k){//the rank of "k"
	int res=0,cur=rt;
	while(1){
		if(k<val[cur]){
			cur=ch[cur][0];
		}else{
			res+=sz[ch[cur][0]];
			if(!cur) return res+1;
			if(k==val[cur]){
				splay(cur);
				return res+1;
			}
			res+=cnt[cur];
			cur=ch[cur][1];
		}
	}
}

查询排名
\(x\)
的数

  • 如果左子树非空且剩余排名
    \(k\)
    不大于左子树的大小
    \(size\)
    ,那么向左子树查找。
  • 否则将
    \(k\)
    减去左子树的和根的大小。如果此时
    \(k\)
    的值小于等于
    \(0\)
    ,则返回根节点的权值,否则继续向右子树查找。
int kth(int k){//the number whose rank is "k"
	int cur=rt;
	while(1){
		if(ch[cur][0] && k<=sz[ch[cur][0]]){
			cur=ch[cur][0];
		}else{
			k-=cnt[cur]+sz[ch[cur][0]];
			if(k<=0){
				splay(cur);
				return val[cur];
			}
			cur=ch[cur][1];
		}
	}
}

查询前驱&后继

前驱就是
\(x\)
的左子树中最右边的节点

后继就是
\(x\)
的右子树中最左边的节点

前驱

int pre(){//precursor
	int cur=ch[rt][0];
	if(!cur) return cur;
	while(ch[cur][1]) cur=ch[cur][1];
	splay(cur);
	return cur;
}

后继

其实就是查前驱的反面

int nxt(){//next or successor
	int cur=ch[rt][1];
	if(!cur) return cur;
	while(ch[cur][0]) cur=ch[cur][0];
	splay(cur);
	return cur;
}

查前驱后继有好多种写法,如果想偷懒只写一遍就可以酱紫

int prenxt(int x,int k){//0 pre 1 nxt
	find(x);
	int cur=rt;
	if(!k && val[cur]<x) return cur;
	if(k && val[cur]>x) return cur;
	cur=ch[cur][k];
	while(ch[cur][!k]){
		cur=ch[cur][!k];
	}
	return cur;
}

删除操作

首先将
\(x\)
旋转到根的位置。

  • 如果
    \(cnt[x]>1\)
    (有不止一个
    \(x\)
    ),那么将
    \(cnt[x] - 1\)
    并退出。

  • 否则,合并它的左右两棵子树即可。

void del(int k){//delete
	rk(k);
	if(cnt[rt]>1){
		cnt[rt]--;
		maintain(rt);
		return;
	}
	if(!ch[rt][0] && !ch[rt][1]){//树空
		clear(rt);
		rt=0;
		return;
	}
	if(!ch[rt][0]){
		int cur=rt;
		rt=ch[rt][1];
		fa[rt]=0;
		clear(cur);
		return;
	}
	if(!ch[rt][1]){
		int cur=rt;
		rt=ch[rt][0];
		fa[rt]=0;
		clear(cur);
		return;
	}
	int cur=rt,x=pre();
	fa[ch[cur][1]]=x;
	ch[x][1]=ch[cur][1];
	clear(cur);
	maintain(rt);
}

那么恭喜你,你已经学完了Splay的基本操作。

至于区间翻转什么的...

下次丕定

Code

Elaina's Code
struct Slpay{
	int rt;//根 
	int tot;//节点编号 
	int fa[N];//父节点 
	int ch[N][2];//子节点 左0右1 
	int val[N];//权值 
	int cnt[N];//节点大小 
	int sz[N];//子树大小 
	
	void maintain(int x){
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
	}
	
	bool get(int x){
		return x==ch[fa[x]][1];
	}
	
	void clear(int x){
		ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
	}
	
	
	void rotate(int x){
		int y=fa[x],z=fa[y],chk=get(x);
		ch[y][chk]=ch[x][chk^1];
		if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y;
		fa[y]=x;
		fa[x]=z;
		if(z) ch[z][y==ch[z][1]]=x;
		maintain(y);
		maintain(x);
	}
	
	void splay(int x,int goal=0){
		if(goal==0) rt=x;
		while(fa[x]!=goal){
			int f=fa[x];
			if(fa[fa[x]]!=goal){
				rotate(get(x)==get(f)?f:x);
			}
			rotate(x);
		}
	}
	
	void ins(int k){//insert
		if(!rt){
			val[++tot]=k;
			cnt[tot]++;
			rt=tot;
			maintain(rt);
			return;
		}
		int cur=rt,f=0;
		while(1){
			if(val[cur]==k){
				cnt[cur]++;
				maintain(cur);
				maintain(f);
				splay(cur);
				break;
			}
			f=cur;
			cur=ch[cur][val[cur]<k];
			if(!cur){
				val[++tot]=k;
				cnt[tot]++;
				fa[tot]=f;
				ch[f][val[f]<k]=tot;
				maintain(tot);
				maintain(f);
				splay(tot);
				break;
			}
		}
	}
	
	int rk(int k){//the rank of "k"
		int res=0,cur=rt;
		while(1){
			if(k<val[cur]){
				cur=ch[cur][0];
			}else{
				res+=sz[ch[cur][0]];
				if(!cur) return res+1;
				if(k==val[cur]){
					splay(cur);
					return res+1;
				}
				res+=cnt[cur];
				cur=ch[cur][1];
			}
		}
	}
	
	int kth(int k){//the number whose rank is "k"
		int cur=rt;
		while(1){
			if(ch[cur][0] && k<=sz[ch[cur][0]]){
				cur=ch[cur][0];
			}else{
				k-=cnt[cur]+sz[ch[cur][0]];
				if(k<=0){
					splay(cur);
					return val[cur];
				}
				cur=ch[cur][1];
			}
		}
	}
	
	int pre(){//precursor
		int cur=ch[rt][0];
		if(!cur) return cur;
		while(ch[cur][1]) cur=ch[cur][1];
		splay(cur);
		return cur;
	}
	
	int nxt(){//next or successor
		int cur=ch[rt][1];
		if(!cur) return cur;
		while(ch[cur][0]) cur=ch[cur][0];
		splay(cur);
		return cur;
	}
	
	void del(int k){//delete
		rk(k);
		if(cnt[rt]>1){
			cnt[rt]--;
			maintain(rt);
			return;
		}
		if(!ch[rt][0] && !ch[rt][1]){
			clear(rt);
			rt=0;
			return;
		}
		if(!ch[rt][0]){
			int cur=rt;
			rt=ch[rt][1];
			fa[rt]=0;
			clear(cur);
			return;
		}
		if(!ch[rt][1]){
			int cur=rt;
			rt=ch[rt][0];
			fa[rt]=0;
			clear(cur);
			return;
		}
		int cur=rt,x=pre();
		fa[ch[cur][1]]=x;
		ch[x][1]=ch[cur][1];
		clear(cur);
		maintain(rt);
	}


    void find(int x){
		int cur=rt;
		if(!cur) return;
		while(ch[cur][x>val[cur]]&&x!=val[cur]){
			cur=ch[cur][x>val[cur]];
		}
		splay(cur,0);
	}
	
	int get_pre(int x){
		find(x);
		int cur=rt;
		if(val[cur]<x) return cur;
		cur=ch[cur][0];
		while(ch[cur][1]){
			cur=ch[cur][1];
		}
		return cur;
	}
	
	int get_nxt(int x){
		find(x);
		int cur=rt;
		if(val[cur]>x) return cur;
		cur=ch[cur][1];
		while(ch[cur][0]){
			cur=ch[cur][0];
		}
		return cur;
	}

    int prenxt(int x,int k){//0 pre 1 nxt
		find(x);
		int cur=rt;
		if(!k && val[cur]<x) return cur;
		if(k && val[cur]>x) return cur;
		cur=ch[cur][k];
		while(ch[cur][!k]){
			cur=ch[cur][!k];
		}
		return cur;
	}
}tr;

signed main(){
	int m=rd;
	while(m--){
		int opt=rd,x=rd;
		if(opt==1){
			tr.ins(x);
		}else if(opt==2){
			tr.del(x);
		}else if(opt==3){
			printf("%lld\n",tr.rk(x));
		}else if(opt==4){
			printf("%lld\n",tr.kth(x));
		}else if(opt==5){
			tr.ins(x),printf("%lld\n",tr.val[tr.pre()]),tr.del(x);
		}else{
			tr.ins(x),printf("%lld\n",tr.val[tr.nxt()]),tr.del(x);
		}
	}
	return Elaina;
}

学了这么久 奖励你张图吧

才不是我自己想看

前提条件,使用最新版的
17.12.0 Preview2
,并且有有效的Copilot AI订阅,那么可以体验这些新鲜好用的功能

增强了Copilot AI对IEnumerable Visualizer的可编辑表达式功能

image

image

我们可以通过AI实现一些复杂的条件筛查,并且可以即时验证结果是否符合预期,对于开发和调试提供了极大的便利性!

提供对单元测试验证失败的信息帮助

当单元测试失败的时候,可以询问AI,为什么失败了,AI会给出相应的断点建议,
当它遇到断点时,Copilot提供受监视变量的值和期望值予以比较
如果存在多个验证错误,你可以继续追问,直到认为满意的解决办法为止!

image

提供对调试时变量的基本分析功能

当你对特定变量感兴趣时,你只需要点击询问AI即可获得此变量的一手信息,修复建议以及调用链等情况

image

标记压缩通过减少冗余标记的数量(例如,修剪不重要的标记或合并相似的标记)来加快视觉变换器(
ViTs
)的训练和推理。然而,当这些方法应用于下游任务时,如果训练和推理阶段的压缩程度不匹配,会导致显著的性能下降,这限制了标记压缩在现成训练模型上的应用。因此提出了标记补偿器(
ToCom
),以解耦两个阶段之间的压缩程度。该插件通过在预训练模型上额外执行了一个快速参数高效的自蒸馏阶段获得一个小型插件,描述了不同压缩程度下模型之间的差距。在推理过程中,
ToCom
可以直接插入到任何下游现成模型中,无论训练和推理的压缩程度是否匹配,都能获得通用的性能提升,而无需进一步训练。

来源:晓飞的算法工程笔记 公众号,转载请注明出处

论文: Token Compensator: Altering Inference Cost of Vision Transformer without Re-Tuning

Introduction


视觉变换器(
ViTs
)在计算机视觉的多个领域取得了显著成功,包括图像分类、目标检测、语义分割等。然而,随着
ViTs
规模的快速增长,计算成本的增加已成为一个迫切问题。因此,大量研究工作集中在加速
ViTs
的训练和推理上。
ViTs
的特点在于能够处理可变数量的输入标记,除了卷积神经网络中广泛使用的传统技术,如模型剪枝、量化和蒸馏,近期的研究通过标记压缩来加速
ViTs
,例如修剪不重要的标记或合并相似的标记。

与剪枝和蒸馏等技术相比,标记压缩技术具有明显的优势。一些标记压缩方法(例如,
ToMe
)可以以零样本的方式应用于现成模型或用于加速训练。与量化不同,标记压缩方法不需要对低精度操作符的支持。此外,标记压缩方法与上述其他技术在操作上是正交的,使其在
ViTs
中具有广泛的适用性。

然而,当标记压缩应用于下游任务时,论文观察到如图
1
所示的以下缺点:

  1. 尽管一些标记压缩技术可以应用于现成模型,但通常会导致显著的性能下降。
  2. 即使标记压缩仅在训练期间应用以加速过程,而在推理期间不进行压缩,模型的性能仍然低于未经标记压缩训练的模型。
  3. 总之,当训练和推理阶段的标记压缩程度不一致时,模型的性能表现不佳。

论文指出,经过不同标记压缩程度微调的模型在参数层面存在一定的差距,这导致在推理过程中改变压缩程度时性能下降。此外,这一差距可以在不同的下游数据集之间转移。基于此,论文提出标记补偿器(
Token Compensator
,简称
ToCom
),这是一种旨在解耦训练和推理过程中的标记压缩程度的预训练插件。
ToCom
是一个参数高效的模块,仅包含少量参数,用于描述具有不同压缩程度的模型之间的差距。为了获得
ToCom
,在预训练数据集上通过不同压缩程度之间的快速自蒸馏过程进行训练。具体来说,教师模型和学生模型都是相同的冻结预训练模型,其中学生模型包括
ToCom
。在每一步中,教师模型和学生模型被随机分配不同的压缩程度,同时
ToCom
通过蒸馏学习它们之间的差距。此外,为不同的压缩程度设置分配不同
ToCom
参数的子集,使
ToCom
能够通过单一的训练过程适应各种压缩程度对。

在推理过程中,将
ToCom
直接集成到在下游任务上进行微调的现成模型中,而无需进一步训练。通过选择
ToCom
参数的子集,微调后的模型可以直接应用于各种标记压缩程度,并达到与训练和推理压缩程度一致时相当的性能。重要的是,
ToCom
只需预训练一次,即可应用于在任意下游数据集上经过微调的模型,不论其标记压缩程度如何,从而使任何单一的现成模型能够处理动态延迟约束,而无需修改参数。

论文在超过
20
个数据集上进行了实验,涵盖了各种压缩程度设置。实验结果表明,
ToCom
作为一个即插即用的模块,能够有效地解耦训练和推理过程中的标记压缩程度。例如,在
VTAB-1k
基准测试中,
ToCom

DeiT-B
的平均性能上比
ToMe
最高可提升
2.0%
,如图
1
所示。
ToCom
还可以应用于不同规模的模型或在不同对象上预训练的模型,或者用于增强各种标记压缩方法,包括标记合并和标记剪枝。

Delve into Token Compression


Impact of Compression Degrees

首先,对
ViTs
中的标记压缩方法进行公式化。
ViTs
的单层由两个模块组成,即多头自注意力(
MHSA
)和多层感知机(
MLP
)。该层可以被形式化为

\[\begin{equation}
\widetilde{\mathbf{X}}^l=\mathbf{X}^l+\textrm{MHSA}(\textrm{LN}(\mathbf{X}^l)), \quad \mathbf{X}^{l+1}=\widetilde{\mathbf{X}}^l+\textrm{MLP}(\textrm{LN}(\widetilde{\mathbf{X}}^l)),
\end{equation}
\]

其中,
\(\mathbf{X}^l \in \mathbb{R}^{N \times d}\)
是第
\(l\)
层的输入,具有长度
\(N\)
和维度
\(d\)

LN
表示层归一化。

论文主要关注一种具有代表性且最先进的无训练标记压缩方法
ToMe
,并进一步推广到其他方法。
ToMe

MHSA

MLP
模块之间操作,利用图像块标记的键来评估它们的相似性,并通过二分软匹配将
\(r\)
个相似的标记进行合并。


ToMe
中,每层合并的标记数量被视为超参数,以调整
ViTs
的吞吐量,这通常在训练之前根据推理需求来确定。合并的标记越多,模型在训练和推理时的速度就越快,如图
3
所示。然而,在实际场景中,训练期间的压缩程度(称为源压缩程度)和推理期间的压缩程度(称为目标压缩程度)可能不一定相等。也就是说,一个在某一压缩程度下训练好的现成模型,可能会在没重新训练的情况下进行不同的压缩程度下的应用。这种情况具有实际意义,例如,使用下载的
checkpoint
而无法访问训练数据或重新训练资源时,或根据服务器负载动态调整推理期间的压缩程度。此外,在现有计算资源有限的情况下,可能需要在训练期间使用较高的压缩程度以减少内存和时间开销,但在推理期间恢复到较低的压缩程度以确保性能。

为了研究标记压缩方法在源压缩程度与目标压缩程度不一致时的性能,论文在五个下游数据集上进行了实验。如图
2
所示,论文对
DeiT-B
进行了
ToMe

\(r=0\)

\(16\)
的微调,并报告了在推理期间使用
\(r=0, 2, 4, \ldots, 16\)
的性能。可以看到,对于特定的目标压缩程度,当源压缩程度与其匹配时,模型的表现更好。源压缩程度与目标压缩程度之间的差距越大,性能下降的程度就越显著。

然而,由于在较低压缩程度下训练的模型在训练期间接触到了更多的标记,这意味着它们遇到的信息范围比在较高压缩程度下训练的模型更广泛,因此,前者在各种目标压缩程度下理应优于后者。这表明,不同源压缩程度下训练的模型之间存在差距,使得在不同压缩程度之间的迁移效果较差。

Transfer across Tasks

对于具有不同源压缩程度的模型之间的差距,是否可以在不同任务之间转移?更具体地说,令
\(\mathcal{M}_m^{\mathcal{D_A}}\)

\(\mathcal{M}_{n}^{\mathcal{D_A}}\)
表示在数据集
\(\mathcal{D_A}\)
上以压缩程度
\(m\)

\(n\)
训练的模型,
\(\mathcal{M}_m^{\mathcal{D_B}}\)

\(\mathcal{M}_{n}^{\mathcal{D_B}}\)
表示在数据集
\(\mathcal{D_B}\)
上训练的模型。如果这种差距是可转移的,应该有

\[\begin{equation}
\mathcal{M}_{m}^{\mathcal{D_A}} - \mathcal{M}_n^{\mathcal{D_A}} \approx \mathcal{M}_{m}^{\mathcal{D_B}} - \mathcal{M}_n^{\mathcal{D_B}},
\label{eq:transfer}
\end{equation}
\]

其中
\(+\)

\(-\)
分别是逐元素的加法和减法。为了验证这一点,将公式重新写为

\[\begin{equation}
\mathcal{M}_{m}^{\mathcal{D_A}} - \mathcal{M}_n^{\mathcal{D_A}} + \mathcal{M}_n^{\mathcal{D_B}} \approx \mathcal{M}_{m}^{\mathcal{D_B}},
\label{eq:transfer2}
\end{equation}
\]

这意味着
\((\mathcal{M}_{m}^{\mathcal{D_A}} - \mathcal{M}_n^{\mathcal{D_A}} + \mathcal{M}_n^{\mathcal{D_B}})\)
在以目标压缩程度
\(m\)
对数据集
\(\mathcal{D_B}\)
进行评估时,应当比
\(\mathcal{M}_n^{\mathcal{D_B}}\)
的表现更好。换句话说,
\((\mathcal{M}_{m}^{\mathcal{D_A}} - \mathcal{M}_n^{\mathcal{D_A}})\)
在数据集
\(\mathcal{D_A}\)
上的差距可以转移到
\(\mathcal{D_B}\)
,并有助于缩小
\(\mathcal{M}_{m}^{\mathcal{D_B}}\)

\(\mathcal{M}_n^{\mathcal{D_B}}\)
之间的差距。


ToMe
上进行初步实验,使用
CIFAR100
作为
\(\mathcal{D_A}\)

\(m=16\)

\(n=0\)
。在表
1
中,展示了使用不同
FGVC
数据集作为
\(\mathcal{D_B}\)
时的结果。通过添加
\((\mathcal{M}_{16}^{\mathcal{D_A}} - \mathcal{M}_0^{\mathcal{D_A}})\)

\(\mathcal{M}_0^{\mathcal{D_B}}\)

\(r=16\)
下的表现明显提高,验证了在不同任务中存在源压缩程度之间的模型差距的正向迁移,这表明可以使用通用插件来建模这种差距,从而在各种下游任务中提高具有不等源和目标压缩程度的标记压缩性能。

Token Compensator


Arithmetic of Parameter-Efficient Modules

当训练和推理过程中的压缩程度不相等时,由于不同压缩程度的模型在行为上存在差异,导致其参数空间中出现不同的局部最小值,从而使模型性能下降。为了在这种情况下提升标记压缩的性能,尤其是在现成模型上,论文打算寻找一个通用插件以弥补具有不同压缩程度的模型之间的差距,假设两个特定压缩程度的模型在不同数据集上表现出类似的差距。假设有一个插件
\(\mathcal{P}_{m\rightarrow n}\)
,可以弥补在
ToMe
训练下的模型
\(\mathcal{M}_m\)
(压缩程度
\(r=m\)
)和模型
\(\mathcal{M}_{n}\)
(压缩程度
\(r=n\)
)之间的差距。如果
\(\mathcal{M}_m\)
是现成模型,可以期望

\[\begin{equation}
\mathcal{M}_m \oplus \mathcal{P}_{m\rightarrow n} = \mathcal{M}'_n \approx \mathcal{M}_n,
\label{eq:plugin}
\end{equation}
\]

其中
\(\oplus\)
表示架构层面的聚合,
\(\mathcal{M}'_n\)
是用于以
\(r=n\)
进行推理的合成模型。

然而,由于压缩程度选择的范围广(例如,
DeiT-B

ToMe
中的
\(r \in \{0, 1, ..., 16\}\)
),为所有可能的压缩程度对(即
\(16\times17\)

\((m,n)\)
组合)训练和存储这些插件会导致显著的训练和存储开销。为此,论文从三个方面解决这个问题。

首先,受到参数高效微调的启发,该方法使用轻量级模块来描述预训练模型与微调模型之间的差距,论文也采用了参数高效模块来描述具有不同压缩程度的模型之间的差距。具体来说,使用
LoRA
作为
\(\mathcal{P}_{m\rightarrow n}\)
,即对
\(\mathcal{M}'_n\)
的所有权重矩阵
\(\mathbf{W}\in\mathbb{R}^{d_1\times d_2}\)
,有

\[\begin{equation}
\begin{cases}
\mathbf{W}_{\mathcal{M}'_n} = \mathbf{W}_{\mathcal{M}_m} + s\cdot\mathbf{A}\mathbf{B},\quad&\textit{if}\ \mathbf{W} \in\{\mathbf{W}_q,\mathbf{W}_v\},\\
\mathbf{W}_{\mathcal{M}'_n} = \mathbf{W}_{\mathcal{M}_m}, \quad&\textit{otherwise},
\end{cases}
\end{equation}
\]

其中,
\(\mathbf{W}_q\)

\(\mathbf{W}_v\)
是查询和值变换的权重矩阵,
\(s\)
是一个超参数,
\(\mathbf{A}\in\mathbb{R}^{d_1\times h}\)

\(\mathbf{B}\in\mathbb{R}^{h\times d_2}\)

LoRA
模块。
LoRA
模块仅占模型参数的约
0.1%
,并且在推理时不会增加额外的计算。

其次,使用
LoRA
来估计仅相邻压缩程度之间的差距,即
\(n=m+1\)
。对于
\(n>m+1\)
的情况,简单地累积
\(m\)

\(n\)
之间的所有插件,即

\[\begin{equation}
\mathcal{M}_m \oplus \left( \bigoplus_{i=m}^{n-1}\mathcal{P}_{i\rightarrow i+1}\right) = \mathcal{M}'_n \approx \mathcal{M}_n.
\label{eq:plus}
\end{equation}
\]

第三,假设模型之间的差距是可逆的,即
\(\mathcal{P}_{n\rightarrow m}=\ominus \mathcal{P}_{m\rightarrow n}\)
。当
\(n<m\)
时,插件被“减去”,即

\[\begin{equation}
\mathcal{M}_m \ominus \left( \bigoplus_{i=n}^{m-1}\mathcal{P}_{i\rightarrow i+1}\right) = \mathcal{M}'_n \approx \mathcal{M}_n,
\label{eq:minus}
\end{equation}
\]

其中,
\(\ominus\)

\(\oplus\)
的逆运算。为了实现
\(\ominus\)
,我们从权重中减去
LoRA
乘积
\(\mathbf{A}\mathbf{B}\)
,而不是加上它。

现在,只需训练和存储
16

LoRA
插件,以支持所有压缩程度对,这些插件的大小仍然相对于
ViT
主干来说微不足道,这些插件的集合称为
Token Compensator

ToCom
)。由于
ToCom
的轻量特性,它可以以最小的开销加载到
RAM
中,从而实现实时推理吞吐量切换。

Training ToCom

如前所述,
ToCom
应该是一个适用于任何下游数据集的通用插件。为了增强
ToCom
的泛化能力,将
ToCom
的训练整合为
ViT
主干的预训练阶段的扩展。具体而言,利用预训练数据(例如
ImageNet
)来训练
ToCom

为了获得支持任意压缩程度对的
ToCom
,论文提出了一种自蒸馏方法来训练它。以
ToMe
为例,使用
\(\widehat{\mathcal{M}}_n\)
来表示通过在现成的预训练模型上直接应用
ToMe

\(r=n\)
)得到的模型。训练损失的构造如下,

\[\begin{equation}
\mathcal{L} = \begin{cases}
\mathcal{L}_{KD}\left(\widehat{\mathcal{M}}_m \oplus \left( \bigoplus_{i=m}^{n-1}\mathcal{P}_{i\rightarrow (i+1)}\right), \widehat{\mathcal{M}}_n\right),&\textit{if}\ n > m \\
\mathcal{L}_{KD}\left(\widehat{\mathcal{M}}_m \ominus \left( \bigoplus_{i=n}^{m-1}\mathcal{P}_{i\rightarrow (i+1)}\right), \widehat{\mathcal{M}}_n\right),&\textit{if}\ n < m
\end{cases}
\end{equation}
\]

其中
\(m\)

\(n\)
在每次训练步骤中随机抽取,且满足
\(m \neq n\)

\(\mathcal{L}_{KD}\)
是带有软目标的知识蒸馏损失,即,

\[\begin{equation}
\mathcal{L}_{KD}(\mathcal{M}_{s}, \mathcal{M}_{t})=\textrm{KL}(\mathcal{M}_{s}(\boldsymbol{x}), \mathcal{M}_{t}(\boldsymbol{x})),
\end{equation}
\]

其中
\(\textrm{KL}\)
表示
Kullback

Leibler
散度,
\(\boldsymbol{x}\)
是输入。

如图
4
所示,在蒸馏过程中,冻结所有预训练的参数,包括分类头,只更新参数高效的
ToCom
。值得注意的是,虽然
ToCom
需要在大规模数据集上进行训练,但它的模型较轻量且收敛迅速。因此,与主干网络的预训练相比,它的训练开销可以忽略不计。

在训练完成
ToCom
后,可以直接将其部署到任何在下游任务上微调的现成模型上,进行任何源度数到目标度数的转换。将
ToCom

LoRA
产物加到或减去现成模型的权重上,用于推理而无需进一步训练。

Experiments




如果本文对你有帮助,麻烦点个赞或在看呗~
更多内容请关注 微信公众号【晓飞的算法工程笔记】

work-life balance.

根据与源表相联接的结果,对目标表进行插入、更新、删除等操作。 例如,对目标表,如果源表存在的数据则更新,没有的则插入,就可以使用MEREG进行同步。

基本语法

MERGE INTO target_table
USING source_table
ON condition
WHEN MATCHED THEN 
XXX
WHEN NOT MATCHED THEN 
XXX

这里的Source table 不限于单独的表格,也可以是子查询的内容

示例

INSERT tbl_A (col, col2)
SELECT col, col2
FROM tbl_B
WHERE NOT EXISTS (SELECT col FROM tbl_A A2 WHERE A2.col = tbl_B.col);

上面的SQL是为了向 tbl_A 中插入 tbl_B 含有的,但是 tbl_A 不包含的col
改为MERGE可以写为

MERGE INTO tbl_A  t  
    USING tbl_B v  
    ON t.col = v.col  
    WHEN MATCHED THEN   
        UPDATE SET y.c2 = v.c2  
    WHEN NOT MATCHED THEN  
        INSERT (col, col2) VALUES (v.c1, v.c2);

(这里为了展示更多的选项,加多了一句UPDATE)
当一个表需要依托于另一个表进行更新操作的时候,使用MERGE可以快捷的实现

前言

万字长文!这里有我的一些思考和领会,网络上的教程都太潦草了。

并且我
发现了新的反演公式

概述

二项式反演用于转化两个具有特殊关系的函数
\(f\)

\(g\)
,从而方便求解问题。一般来说,直接计算恰好满足
\(n\)
个限制的答案不好求,但是可以计算出“至少” / “至多”满足
\(n\)
个限制的答案,运用二项式反演,就能求出“恰好”满足
\(n\)
个限制的答案。

想直接看结论的可以
戳我

证明 & 推导

一些引理

引理
\(1\)
:二项式定理

普通二项式定理为:

\[\large (a + b) ^ n = \sum _ {i = 0} ^ n \binom{n}{i} a^i b^{n-i}
\]

证明可以用数学归纳法,不做展开。本篇主要利用
\(a = -1, b = 1\)
的特殊情形,即:

\[\begin{aligned}
& \quad \ \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i \\
&= \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i 1^{n-i} \\
&= \Big (1 + (-1) \Big )^n \\
&= 0 ^ n
\end{aligned}
\]

注意到当
\(n = 0\)
的时候,没有意义。观察原式发现此时
\(\dbinom{0}{0} (-1)^0 = 1\)
。所以我们有:

\[\large \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i = [n = 0]
\]

引理
\(2\)
:多步容斥


\(S_i\)

\(1 \leq i \leq n\)
)表示一个集合,我们有:

\[\large \left \vert \bigcup_{i = 1}^{n} S_i \right \vert = \sum _ {1 \leq i \leq n} \Big \vert S_i \Big \vert - \sum _ {1 \leq i \lt j \leq n} \Big \vert S_i \cap S_j \Big \vert + \cdots + (-1) ^ {n - 1} \Bigg \vert \bigcap _ {i = 1} ^ n S_i \Bigg \vert
\]

即:

\[\large \left \vert \bigcup_{i = 1}^{n} S_i \right \vert = \sum _ {m = 1} ^ n (-1) ^ {m - 1} \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert
\]

证明该式等价于证明
\(\forall x \in \bigcup \limits_{i = 1}^{n} S_i\)
,其在右边
\(\sum \limits _ {a_i < a_{i + 1}} \Bigg \vert \bigcap \limits _ {i = 1} ^ m S_{a_i} \Bigg \vert\)
计算的系数之和为
\(1\)
。记所有包含
\(x\)
的集合为
\(T_1, \ldots, T_m\)

\(m \neq 0\)
),则有:

\[\begin{aligned}
& \quad \ \Big \vert \{ T_i \mid 1 \leq i \leq m \} \Big \vert - \Big \vert \{ T_i \cap T_j \mid 1 \leq i \lt j \leq m \} \Big \vert + \cdots \\
&= \binom{m}{1} - \binom{m}{2} + \cdots + \cdots (-1) ^ {m - 1} \binom{m}{m} \\
&= \sum _ {i = 1} ^ {m} (-1)^{i - 1} \binom{m}{i} \\
&= - \sum _ {i = 1} ^ {m} (-1)^i \binom{m}{i} \\
&= \binom{m}{0} - \sum _ {i = 1} ^ {m} (-1)^i \binom{m}{i} \\
&= 1 - [m = 0] \\
&= 1
\end{aligned}
\]

故成立。

引理
\(3\)
:组合数

我们考虑变换
\(\dbinom{n}{i} \dbinom{i}{j}\)
。其组合意义为,
\(n\)
个小球里选出
\(i\)
个,再从
\(i\)
个里面选出
\(j\)
的方案数。我们也可以先从
\(n\)
个里面选出
\(j\)
个,再从剩下
\(n - j\)
里选出
\(i - j\)
个。表达为:

\[\dbinom{n}{i} \dbinom{i}{j} = \binom{n}{j} \binom{n - j}{i - j}
\]

当然也可以代数证明:

\[\begin{aligned}
\dbinom{n}{i} \dbinom{i}{j} &= \frac{n!}{i! (n-i)!} \frac{i!}{j! (i-j)!} \\
&= \frac{n!}{(n - i)! (i - j)! j!} \\
&= \frac{n! (n - j)!}{(n - i)! (i - j)! (n - j)! j!} \\
&= \frac{n!}{j! (n - j)!} \frac{(n - j)!}{(n - i)! \Big ((n - j) - (n - i) \Big)!} \\
&= \binom{n}{j} \binom{n - j}{i - j}
\end{aligned}
\]

引理
\(4\)

\(-1\)
的幂次特点

\((-1) ^ {a + b} = (-1) ^ {a - b}\)
。这还用证明?

\[\begin{aligned}
2b &\equiv 0 & \pmod {2} \\
b &\equiv -b & \pmod {2} \\
a + b &\equiv a - b & \pmod {2}
\end{aligned}
\]

模型
\(0\)

\[\large f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i)
\]

容斥证明

不妨记
\(\overline{S_i}\)
表示
\(S_i\)
的补集,有:

\[\begin{aligned}
\left \vert \bigcap_{i = 1}^{n} \overline{S_i} \right \vert &= \left \vert \bigcup_{i = 1}^{n} S_i \right \vert - \left \vert \bigcup_{i = 1}^{n} \overline{S_i} \right \vert \\
&= \left \vert \bigcup_{i = 1}^{n} S_i \right \vert - \sum _ {m = 1} ^ n (-1) ^ {m - 1} \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\
&= \left \vert \bigcup_{i = 1}^{n} S_i \right \vert + \sum _ {m = 1} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\
&= \sum _ {m = 0} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\
\end{aligned}
\]

由于
\(\overline{\ \overline{S_i}\ } = S_i\)
,所以得到类似的式子:

\[\left \vert \bigcap_{i = 1}^{n} S_i \right \vert = \sum _ {m = 0} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m \overline{S_{a_i}} \Bigg \vert
\]

发现形式很像,但是还差一步构造。我们假设能够早出一组
\(S_i\)
,使任意
\(k\)
个集合的交集大小相等。

不妨记
\(f(x)\)
表示任意
\(x\)
个补集的交集大小,对于原集同理记
\(g(x)\)
,上式可以分别改写为:

\[f(n) = \sum _ {i = 0} ^ n (-1) ^ i \binom{n}{i} g(i)
\]

\[g(n) = \sum _ {i = 0} ^ n (-1) ^ i \binom{n}{i} f(i)
\]

即证。

代数证明

容斥比较抽象,尝试代数证明。我们把
\(g\)
带到
\(f\)
中去,得到:

\[\begin{aligned}
f(x) &= \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} \sum _ {j = 0} ^ i (-1) ^ j \binom{i}{j} f(j) \\
&= \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{j}{i} \binom{x}{j} \\
&= \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x}{i} \binom{x - i}{j - i} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x - i}{j - i} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ {2i + j} \binom{x - i}{j} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ j \binom{x - i}{j} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} f(i) [x - i = 0] \\
&= f(x)
\end{aligned}
\]

即证。

模型
\(1\)
:“至少”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(i)
\]

为了解决实际问题,考虑实际意义。考虑有
\(n\)
个限制,
\(f(x)\)
表示至少满足
\(x\)
个限制,
\(g(x)\)
表示恰好满足
\(x\)
个限制。

注意到,
\(f\)
不是简单
\(g\)
的前缀和,因为会重复计数。

\(g(x)\)
即为我们的答案,而
\(f(x)\)
就是我们通过其他算法求出的结果。

通常来说,我们会钦定
\(x\)
个限制必须满足,剩下的限制可以满足可以不满足,这样就能不用考虑限制的问题,求出
\(f\)

考虑如何用
\(g\)
表示出
\(f\)
。有两种思考方式:

  1. 我们考虑求
    \(g(x)\)
    的过程。初始令
    \(g(x) \gets f(x)\)
    ,这显然是不对的。我们考虑一个
    \(i > x\)

    \(g(i)\)

    \(f(x)\)
    中贡献次数是
    \(\dbinom{i}{x}\)
    ,所以得到:


    \[g(x) = f(x) - \sum _ {i = x + 1} ^ n \binom{i}{x} g(i)
    \]


    移项后就有:


    \[\begin{aligned}
    f(x) &= g(x) + \sum _ {i = x + 1} ^ n \binom{i}{x} g(i) \\
    &= \sum _ {i = x} ^ n \binom{i}{x} g(i)
    \end{aligned}
    \]

  2. 更直接的思考方式为,我们考虑枚举钦定
    \(x\)
    个限制必须满足后,还有
    \(i - x\)
    个限制也被满足了,即一共有
    \(i\)
    个限制被满足,其中任选
    \(x\)
    个都能被计数,乘上
    \(\dbinom{i}{x}\)
    后,求和就能不重不漏:


    \[f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i)
    \]

这就是左边那一条等式了。证明右边等式是对的,可将其带入。

\[\begin{aligned}
f(x) &= \sum _ {i = x} ^ n \binom{i}{x} \sum _ {j = i} ^ n (-1)^{j - i} \binom{j}{i} f(j) \\
&= \sum _ {i = x} ^ n f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{j}{x} \binom{i}{j} \\
&= \sum _ {i = x} ^ n f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{i}{x} \binom{i - x}{j - x} \\
&= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{i - x}{j - x} \\
&= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = 0} ^ {i - x} (-1) ^ {i - (j + x)} \binom{i - x}{j} \\
&= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = 0} ^ {i - x} (-1) ^ {i - x - j} \binom{i - x}{j} \\
&= \sum _ {i = x} ^ n \binom{i}{x} f(i) [i - x = 0] \\
&= f(x)
\end{aligned}
\]

即证。

模型
\(2\)
:“至多”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \Leftrightarrow g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i)
\]

当然我们可以直接采用模型
\(1\)
的方式推式子。记
\(f(x)\)
表示至多满足
\(x\)
个限制的方案,
\(g(x)\)
表示恰好。

首先用
\(g\)
表示出
\(f\)
,这可以枚举并钦定
\(i \leq x\)
个限制,最后求和得出:

\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i)
\]

然后把它带到
\(g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i)\)
中。

\[\begin{aligned}
g(x) &= \sum _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} \sum _ {j = 0} ^ i \binom{i}{j} g(j) \\
&= \sum _ {i = 0} ^ x g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x}{j} \binom{j}{i} \\
&= \sum _ {i = 0} ^ x g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x}{i} \binom{x - i}{j - i} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x - i}{j - i} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = 0} ^ {x - i} \binom{x - i}{j} (-1) ^ {x - (j + i)} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = 0} ^ {x - i} \binom{x - i}{j} (-1) ^ {x - i - j} 1 ^ {j} \\
&= \sum _ {i = 0} ^ x \binom{x}{i} g(i) [x - i = 0] \\
&= g(x)
\end{aligned}
\]

得证。

当然,如果不考虑问题的实际意义,利用模型
\(0\)
也可以证明。设
\(h(x) = (-1) ^ x g(x)\)
,有:

\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} h(i)
\]

那么有:

\[g(x) = \frac{h(x)}{(-1) ^ x} = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i)
\]

则:

\[\begin{aligned}
h(x) &= \sum _ {i = 0} ^ x (-1) ^ {x + i} \binom{x}{i} f(i) \\
&= \sum _ {i = 0} ^ x (-1) ^ {x - i} \binom{x}{i} f(i) \\
\end{aligned}
\]


\(h\)
视作命题中的
\(g\)
,即证。

更多思考

注意到「至多满足
\(x\)
个条件」,可以看做「至少不满足
\(n - x\)
个条件」;同理,「至少满足
\(x\)
个条件」,可以看做「至多不满足
\(n - x\)
个条件」,然后就可以相互推导,形成新的一对反演公式,我愿称它们为形式
\(2\)

模型
\(1\)
:“至少”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \Leftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i)
\]


\(f(x) = f'(n - x)\)
,表示至少满足
\(x\)
个条件,其中
\(f'\)
就符合模型
\(2\)
了。有
\(f'(x) = \sum \limits _ {i = 0} ^ x \dbinom{x}{i} g'(i)\)
,其中
\(g'(x)\)
表示恰好不满足
\(x\)
个条件,相当于
\(g(n - x)\)
,即恰好满足
\(n - x\)
个条件,可以得到:

\[\begin{aligned}
f(n - x) &= \sum _ {i = 0} ^ x \binom{x}{i} g(n - i) \\
f(x) &= \sum _ {i = 0} ^ {n - x} \binom{n - x}{i} g(n - i) \\
&= \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \\
\end{aligned}
\]

由于
\(g'(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f'(i)\)
,所以有:

\[\begin{aligned}
g(n - x) &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{x}{i} f(n - i) \\
g(x) &= \sum _ {i = 0} ^ {n - x} (-1)^{(n - x) - i} \binom{n - x}{i} f(n - i) \\
&= \sum _ {i = x} ^ n (-1)^{(n - x) - (n - i)} \binom{n - x}{n - i} f(i) \\
&= \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i) \\
\end{aligned}
\]

所以成立。

模型
\(2\)
:“至多”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \Leftrightarrow g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i)
\]

类似地,记
\(f(x) = f'(n - x)\)
,表示至多满足
\(x\)
个条件,其中
\(f'\)
就符合模型
\(1\)
了。有
\(f'(x) = \sum \limits _ {i = x} ^ n \dbinom{i}{x} g'(i)\)
,其中
\(g'(x)\)
表示恰好不满足
\(x\)
个条件,相当于
\(g(n - x)\)
,即恰好满足
\(n - x\)
个条件。可以得到:

\[\begin{aligned}
f(n - x) &= \sum \limits _ {i = x} ^ n \dbinom{i}{x} g(n - i) \\
f(x) &= \sum \limits _ {i = n - x} ^ n \dbinom{i}{n - x} g(n - i) \\
&= \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \\
\end{aligned}
\]

由于
\(g'(x) = \sum \limits_ {i = x} ^ n (-1)^{i - x} \dbinom{i}{x} f'(i)\)
,所以有:

\[\begin{aligned}
g(n - x) &= \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(n - i) \\
g(x) &= \sum _ {i = n - x} ^ n (-1)^{i - (n - x)} \binom{i}{n - x} f(n - i) \\
&= \sum _ {i = 0} ^ x (-1)^{(n - i) - (n - x)} \binom{n - i}{n - x} f(i) \\
&= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i) \\
\end{aligned}
\]

所以成立。

例题 & 习题

等有时间再写啦。

结论

模型
\(0\)

\[\Large f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i)
\]

模型
\(1\)
:“至少”
\(\Leftrightarrow\)
“恰好”

形式
\(1\)

\[\Large f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(i)
\]

形式
\(2\)

\[\Large f(x) = \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \Leftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i)
\]

模型
\(2\)
:“至多”
\(\Leftrightarrow\)
“恰好”

形式
\(1\)

\[\Large f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i)
\]

形式
\(2\)

\[\Large f(x) = \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i)
\]