0%

Fully Test Time Adaptation by Entropy Minimization

来自ArXiv,by DeepAI和伯克利,ICLR’21高分论文。

一、Motivation:

  • 1.focus on一个独特的任务设置,这篇工作希望解决的setting是,当模型训练好之后,在没有任何监督信息的测试数据上使用时,只有parameter和test data,如何自适应的进行预测从而在测试数据上表现最佳。下表展示了fully test-time adaptation和之前的几种setting的区别。
  • 2.之前的类似任务上的方法为什么不能直接应用过来,它们的不足(fine-tune着力于训练阶段,领域自适应也需要训练数据,TTT比较相似但是在训练&测试同时进行adaption)。

背景知识:

1.高熵代表不确定性(根据最大熵原理在满足已知条件的模型中,预测熵最大的模型是最好的模型)【label smoothing或者dropout都可以看作是一种软最大熵约束】;低熵代表高置信度。

2.领域自适应的方法一般是应用在训练时,主要利用特征对齐、对抗不变性、共享代理目标等学习一个目标领域的表示。即使是最近的source-free的方法也需要利用生成建模和伪标签等、效率比较低。

二、创新点&设计思路:

  • 引入测试熵

    • 熵非常general与任务无关,但相比于自监督学习,熵又是task-specific的不需要手工设计目标。(自监督:补全context、rotation预测、添加噪声的自编码目标)而且,熵和performance具有反向相关性。

  • 测试阶段的normalization

    • 从测试数据中以滑动平均的方式估计μ和σ,利用熵作为目标函数学习β和γ。adaption一个Epoch。
阅读全文 »

When Bert Forgets How To POS: Amnesic Probing of Linguistic Properties and MLM Predictions

http://arxiv.org/abs/2006.00995, by 巴伊兰大学和AI2。

利用一种改进的Probe方法来对黑盒NN模型的行为进行分析,判断。

1.常用的Probe方法及其不足。

什么是probe?增强神经网络模型可解释性的方法。理解这个黑盒子,尝试回答比如BERT的每个head编码了哪些信息?哪些hidden state的维度被实际用在了预测中?如果去掉某些信息会怎么样?等问题。probe是解决这类问题的一种方法,也可以叫做auxilliary prediction【辅助预测】或者diagnostic classification【诊断分类】。

probe的过程?固定pre-train的原始模型的feature层,通过在原始模型的上层训练一个简单的分类网络,以对某种属性property的预测准确率来证明该信息被编码到了原始模型的隐藏表示中。

不足?只能证明信息被encode到了隐藏表示中,无法证明原始模型有效利用了这些信息。

2.这篇文章提出的方法:Amnesic Probing。

改进方式:反事实推理,假设某种属性P被解决任务T的原始模型有效使用了,那么把P去掉肯定会影响原始模型解决T的能力 。因此如果去掉P不影响解决T的能力,那么P中的信息就没有被有效利用。Intervention介入:这个工作和之前一些工作不同的地方在于它通过修改表示层来介入。其实很像是ablation,只是这里不能重新训练原始模型,算是黑盒子版本的ablation。

步骤:

阅读全文 »

一、最小生成树

给你一个points 数组,表示 2D 平面上的一些点,其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 :|xi - xj| + |yi - yj| ,其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时,才认为所有点都已连接。

Prim:从点的视角出发,优点就是不用一次计算所有的边的权重。某个节点出发,把它放到队列里面。

然后循环以下操作直到所有节点都已经访问:从队列中弹出距离最小的节点,如果还没访问就设置为访问,加入总代价。然后计算当前节点和所有没访问的节点之间的权重,放到优先级队列里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from queue import PriorityQueue


class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
calcu_distance = lambda x, y: abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1])
n = len(points)
pq = PriorityQueue() # 利用优先级队列以logN时间开销存储
un_visit = set([i for i in range(n)])
res = 0
cur = (0, 0) # distance, node index
pq.put(cur)
while un_visit:
dist, cur = pq.get()
# print('{}'.format(un_visit))
if cur not in un_visit:
continue
un_visit.remove(cur)
res += dist
for each in un_visit:
dist = calcu_distance(cur, each)
pq.put((dist, each))
# print('{}'.format(list(pq.queue)))
return res

kruskal算法 + 并查集实现:从边的视角出发。初始化并查集。

1.计算出所有边的权重并排序。

2.在边的集合中按从小到大循环:

如果加入当前边会形成环(也就是两个节点已经有通路了,并查集),那么就跳过。

否则就加入当前边(加入总代价,并连通两个节点)。

阅读全文 »

Recent Language Model Papers

最近的语言模型和词嵌入的文章,有的读的仔细点,有的略读,不断更新中。

1.AlBert

https://openreview.net/forum?id=H1eA7AEtvS ,ICLR’20, by Google, SOTA in GLUE.

一个轻量级的BERT但是效果更好。它所做的修改主要有:

  • 首先把词向量矩阵分解了,这样使词向量矩阵的维度和hidden_size解耦,否则词向量矩阵参数量太大。

  • 把每层的参数共享了,减少参数数量。

  • 在这个基础上,能够把hidden_size提高到6144这种量级。

  • 为了对句子级别进行建模,ALBERT增加了一个sentence order prediction(SOP)任务而不是被证明太简单基本无效的NSP任务,给定当前句子与其下一句,或者是顺序翻转的两句话,希望模型预测句子序是否准确。

2.GPT-3,一个看看就好的单向语言模型

http://arxiv.org/abs/2005.14165 ,By OpenAI。

回想去年年底,我在尝试在GPT-2 Small(127M参数)模型的基础上搞点东西的时候,还在想这玩意fine-tune有点慢,batch size设不大啊。害,现在拿到论文只能看看人实验结果了,连下载模型的想法都不会有~

GPT-3,一个最大175Billion参数的基于Transformer-decoder的单向自回归语言模型。希望解决的就是pretrain-fineTune这套框架。他们觉得这套框架虽然解决了task-specific Model的问题,但是没有解决task-specific data的问题,所以领域相关数据还是导致应用很受限。

阅读全文 »

稀疏图计算的实现

遇到图中元素很稀疏时可以使用sparse tensor计算所需要的值,然后再转化为dense tensor。假如涉及图的运算中稀疏程度很大、或者中间结果的维度很高,都能够有效的降低时间跟内存开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 选择所有非0元素的索引
indices = torch.nonzero(x)
# 从参与计算的tensor中取值
values = x[tuple(indices[i] for i in range(indices.shape[0]))]
# 进行需要的索引变换
j_indices = indices.clone()
value_indices = list(j_indices[i] for i in range(j_indices.shape[0]))
value_indices[1] = value_indices[1].zero_()
# 从某个参与计算的tensor中取相应的值
emb_j = node_j[tuple(value_indices)]
# 进行计算
final_values = func(values, emb_j)
# 最后可能需要再次对索引进行变换(比如加上一维)
extra_indices = torch.arange(0, window_size).to(indices.device).unsqueeze(1).repeat(1, n_num).t().reshape(
(1, n_num, window_size))
indices = torch.cat([indices[0:1], extra_indices, indices[1:]], dim=0)
indices = indices.reshape((4, -1))
# 最后生成sparse tensor,再转换回来
x_typename = torch.typename(x).split('.')[-1]
sparse_tensortype = getattr(torch.sparse, x_typename)
res = sparse_tensortype(indices, final_values, (b, window_size, l, l, 1)).requires_grad_(True).to_dense()

另外,中间尝试了把几个计算涉及的tensor分别转为sparse tensor然后运算最后再转回来,但是在backward的时候会出错,用tensor.contiguous()也没解决。

阅读全文 »

PLUG AND PLAY LANGUAGE MODELS: A SIMPLE APPROACH TO CONTROLLED TEXT GENERATION

https://arxiv.org/pdf/1912.02164.pdf,by Uber AI。

大规模预训练语言模型的效果不错,但如何利用它们生成属性可控的文本(比如说某一领域、某种风格、某种情感),fine-tune是一种方法,本文提出了一种不需要重新训练的方式。

无需fine-tune或者重新训练LM。其具体的做法是根据梯度将Transformer-decoder每一层的hidden state向LM和attribute的方向改变一步。

对于attribute,进行了两类属性的控制,1)情感,通过一个预训练的二分类器判断生成的候选文本的误差;2)主题,通过指定一个中心词,找到wordnet的相关词集合,以multi-hot的方式将这些词列为vocabulary中的ground-truth-labels来计算误差。

分为三步,第一步通过一个前向过程获取$p(a|x),p(x)$,第二步通过反向传播获取相对于H的梯度并更新H,第三步利用更新之后的$\tilde H$来预测此时刻的vocab分布。

计算$H_t$的更新值$\nabla H_t$通过若干次重复计算梯度并衰减求和得到。

为了生成文本的流畅度,增加一项KL项,缩小输出的分布和之前的分布的KL值。

最后,最后采样的分布是未改变的分布和改变后的分布的加权之和。

最后的最后,根据$p(a|x)$,采样出来的候选seq集合还可以根据与attribute一致的程度进行排序。下图来自论文原文。

阅读全文 »

软核机器学习,记录结论和性质,推导细节省略。

所有向量默认是列向量。

零、Basics

Sum Rule:

Product Rule:

Chain Rule:

Bayesian Rule:

观测数据$X = {\cdots, x_i, \cdots}$, 标签$Y = {\cdots, y_i, \cdots}$,隐变量$Z = {\cdots, z_i, \cdots}$

生成模型:能够以某种方式估计到观测数据的分布,比如计算联合分布或者边缘分布来求解参数。

判别模型:无法获取观测数据的分布,只能估计条件分布$p(y|x)$。

阅读全文 »

Bilinear Attention Networks

Pub in NeuraIPS’18, by Jin-Hwa Kim, 首尔国立大学。

VQA的任务,主要关注attention部分。下图来自原论文Figure 1。

image-20191117174946648

1.输入矩阵X和Y,分别表示文本和图像两个部分的feature map。

其中文本特征矩阵X的长度是(对应原文的),图像特征图Y的长度是(对应原文的,这里的是图像检测的object数量)。

2.计算Raw Attention Weight。

目标是得到一个矩阵,而后可以从dim1或者dim2进行softmax:

  • dot attention:,需要两个feature的维度相同,而且缺少feature维度的线性变换。
  • bilinear attention:,可以认为线性变换之后的X feature map与Y进行dot attention,但是W参数量可能很大。
  • low-rank bilinear attention: , 把W分解为,其中
  • Optimized:上面的计算等价于,也就是Figure 1中的计算。
  • low-rank bilinear pooling:如果我们把上面一步的矩阵运算分开来,也就是一个向量一个向量的计算,并引入pooling矩阵,那么得到:,这里得到的,也就是得到了G个raw attention weight。

3.计算attention weight并使用。

阅读全文 »

Several Papers about Syntactic Structure Utilization

近期读的几篇关于如何有效利用句法信息的论文。

1.《Syntax Encoding with Application in Authorship Attribution》

EMNLP’18, By Richong.

希望解决的问题:设计出一种通用的能够解析句法结构表示的方法,此方法需要能够和各种不同的NLP方法结合使用。同时为了验证该方法,作者将其应用到Authorship Attribution任务中(句法结构可以认为是作者的写作风格)。

已有的方法:利用句法信息的方法可以分为两类,一类抽取句法结构树中的特征,这种方法需要人工设计特征提取过程而且丢弃掉了很多句法结构信息;一类利用句法结构复制语义编码,其核心任务还是语义编码只是利用句法信息更好地生成语义表示,此类任务大多在LSTM模型基础上做,和CNN等方法难以结合。

本文的方法(思路):

首先,每个单词$w_i$对应一个Syntax Path: $r(w_i) = {t_1, \cdots, t_L}$,而任意一个句法路径的无序集合$R = {(i, R(w_i))}$都可以用来完整的恢复一个句子中的句法信息。而后,把每个句法路径编码为一个向量$\bar R(w)\in R^K$,这里作者使用了句法符号和其所在的句法树层次的embedding的按元素乘的结果之和作为句法路径的向量表示,比如are这个token的句法路径embedding就是$emb(VP)^t\circ emb^d(p_1) + emb^t(VBP)\circ emb^{d}(p_2)$。作者引入并证明了两个引理,说明只要K足够大,这种Syntax Encoding的方法就不会有句法信息的损失。这样即使不同的NLP下游任务需要不同侧重点的句法信息,也可以保证都包含在encode之后的表示里面。

模型过程:N-Gram的CNN卷积抽取内容信息(语义信息),句法编码抽取句法信息。

阅读全文 »

Recent Language Model Papers

On-LSTM

ICLR’19的Best Paper, By YiKang。

1.解决的问题

RNN把序列顺序的处理,但是语言本身常常是具有非序列化结构的(比如树结构)。这样可以获取语言组合性语义的影响,学习到层次化的表示。首先,无监督的Grammer Induction还是一个open problem,通常训练的模型倾向于产生trivial的结构(左分支/右分支树)或者在利用RL学习branching策略的时候有困难。其次LSTM本质上适合建模链式结构的数据,虽然已有的研究表明它能够学习到语言中的树形结构,但是显式的引入一个带有树形结构的inductive bias会不会帮助LSTM更好的建模呢?

2.相关的方法

1.一些工作尝试LSTM中引入结构化信息,但是没有解决如何从观测数据中推导结构化信息的问题;2.也有一些工作针对1中的问题,即grammar induction;3.在recurrent结构模型中引入不同scale的recurrent结构从而让链式的先验具有层次化。(比如ClockWorkRNN和nested dropout,但是本文提出的方法更灵活更具有泛化能力)

3. 提出的方法(Ordered Neurons)思路

预先在模型中定义神经元的序,高阶神经元更新的更久代表长程/全局信息,低阶神经元更新步数更少代表较小的constituent,当高阶神经元的信息在某个step被抹去其对应的子神经元的信息也应当被抹去(对应一个constituent结束)。神经元的序被如下定义,由parse得到的成分句法树决定。

阅读全文 »

Survey on GNN

一、GNN相关研究Survey

0.Preliminary

关于图的一些概念和符号:

图的表示:节点集合$\mathcal{V}$,边集合$\mathcal\epsilon$。

邻接矩阵A,$a_{ij}$表示第i个节点到第j个节点的边的权重。

对角度矩阵(度矩阵)D,$d_{ii}$表示第i个节点的度。

拉普拉斯矩阵L = D - A,D是对角度矩阵。A是邻接矩阵。归一化的拉普拉斯矩阵是图的鲁棒的数学表示。

转移矩阵$P = D^{-1}A$

K近邻:$N_k(i)$,邻居节点$N_1(i) = N(i)$

阅读全文 »

最大化网格幸福感

给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格,和两种类型的人:内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。

请你决定网格中应当居住多少人,并为每个人分配一个网格单元。 注意,不必 让所有人都生活在网格中。

思路

每个点都有三种状态:不住人、住内向的人或者住外向的人。

1.状态压缩DP,由于矩阵大小n比较小,用长度为n的三进制数字记录每一行的状态,一共有种状态,预先计算出行内和行间不同状态间的得分变化。再进行回溯就可以,回溯的单位是行,每次选择的范围是。因此时间复杂度为

2.插头DP(轮廓线DP),记录上一行当前元素到这一行j - 1个元素一共n个元素的状态,可以在时间算出行内和行间得分。进行记忆化搜索就可以,搜索的单位是每个点,每次选择的范围是3,时间复杂度是

实现

第一种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def getMaxGridHappiness_matrix_dp(self, m: int, n: int, ic: int, ec: int) -> int:
NO, IC, EC = 0, 1, 2

def line_extra(cur, prev):
if cur == NO or prev == NO:
return 0
if cur == IC and prev == IC:
return -60
if cur == EC and prev == EC:
return 40
return -10

# 当前行状态数量,每个格子是3种,所以是3 ** 6
state_n = 3 ** n
# 用来方便的计算下面的1和2
mask = [[0] * n for _ in range(state_n)]
# 1.mask的状态对应的ic和ec数量
ic_count = [0 for _ in range(state_n)]
ec_count = [0 for _ in range(state_n)]
# 2.mask的状态对应的行内和行间得分
line_score = [0 for _ in range(state_n)]
outline_score = [[0] * state_n for _ in range(state_n)]
# dp table
dp = [[[[-1] * (ec + 1) for _ in range(ic + 1)] for _ in range(m)] for _ in range(state_n)]

# 预先计算, O(3 ** n * n)
for i in range(state_n):
cur = i
j = 0
while cur != 0 and j <= n:
mask[i][j] = cur % 3
cur //= 3
j += 1
for j in range(n):
# 计算ic和ec数量以及行内得分
if mask[i][j] != NO:
if mask[i][j] == IC:
ic_count[i] += 1
line_score[i] += 120
elif mask[i][j] == EC:
ec_count[i] += 1
line_score[i] += 40
if j > 0: # 计算行内相邻得分
line_score[i] += line_extra(mask[i][j], mask[i][j - 1])
# 计算行间得分,O(3 ** n * 3 ** n * n)
for i in range(state_n):
for i2 in range(i, state_n):
for j in range(n):
outline_score[i][i2] += line_extra(mask[i][j], mask[i2][j])
outline_score[i2][i] = outline_score[i][i2]

# O(3 ** n * 3 ** n * m * ic * ec)
def dfs(last_mask, row, ic, ec):
if row == m or ic + ec == 0:
return 0
if dp[last_mask][row][ic][ec] != -1:
return dp[last_mask][row][ic][ec]
# 做选择
best = 0
for state in range(state_n):
# 剪枝
if ic_count[state] > ic and ec_count[state] > ec:
break
if ic_count[state] > ic or ec_count[state] > ec:
continue
score = line_score[state] + outline_score[state][last_mask]
best = max(best, score + dfs(state, row + 1, ic - ic_count[state], ec - ec_count[state]))
dp[last_mask][row][ic][ec] = best
return best

return dfs(0, 0, ic, ec)

第二种:

阅读全文 »

一、题目要求

所有房子排列成一个二叉树的结构。

如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

二、分析

用递归比较选择和不选择当前节点的最大收益,并把结果缓存起来。

三、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
mem = {}
class Solution:
def rob(self, root: TreeNode) -> int:
if root == None:
return 0
if root in mem:
return mem[root]
res = root.val

left_go = self.rob(root.left.left) + self.rob(root.left.right) if root.left else 0
right_go = self.rob(root.right.left) + self.rob(root.right.right) if root.right else 0

left = self.rob(root.left) if root.left else 0
right = self.rob(root.right) if root.right else 0

total = max(res + left_go + right_go, left + right)
mem[root] = total
return total
阅读全文 »