0%

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)$

阅读全文 »

1.Edit Distance

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符
删除一个字符
替换一个字符

即NLP中计算编辑距离。

思路

使用递归式的自顶向下的动态规划,并增加重叠子问题的缓存。

自底向上的动态规划,1)状态数组存储的是的最小编辑距离,2)起始状态就是当其中一个数组为空,编辑距离是另一个数组的长度,3)计算当前时刻的状态值如果当前时刻字符不相等就选择增删改中最小的(进行了这些操作之后肯定会变成已知的一种状态)。

状态列表可以优化空间到O(m + n)。

实现

阅读全文 »

一、题目要求

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

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

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

二、分析

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

三、实现

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
阅读全文 »

一、题目要求

实现一个对于正整数和“+, -, *, /, (, )”的计算器。每个表达式都是合法的。乘除法优先级较高。

二、分析

实际只需要一个操作数栈存储带正负号的操作数。遇到括号就递归处理。遇到优先级高的操作符乘除就直接算。

三、实现

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
72
73
74
75
76
77
78
79
nums = [str(a) for a in range(10)]


class Solution:
def calculate(self, s: str) -> int:
return cal(list(reversed(s)))


def cal(s):
stack = []
op_stack = []
v, valid = 0, False
sign = None
compute_flag = 0

while s:
c = s.pop()
if c == ' ':
continue

if c in nums:
valid = True
v = v * 10 + int(c)
else:
if valid:
if compute_flag != 1:
v = -v if sign == '-' else v # 加减法直接记录
stack.append(v)
if compute_flag == 1:
evaluation(stack, op_stack)
v, valid = 0, False
if c == '(':
stack.append( self.calculate(s))
elif c == ')':
break
else: # ['+', '-', '*', '/']
compute_flag = 1 if c in ['*', '/'] else 0
if compute_flag == 1:
op_stack.append(c)
else:
sign = c
# print('stack: {}'.format(stack))
# print('op_stack: {}'.format(op_stack))
if valid == True:
if compute_flag != 1:
v = -v if sign == '-' else v
stack.append(v)
if compute_flag == 1:
evaluation(stack, op_stack)
return greedy_evaluation(stack, op_stack)

def helper(op1, op2, sign):
if sign == '+':
return op1 + op2
if sign == '-':
return op2 - op1
if sign == '*':
return op1 * op2
if sign == '/':
return op2 // op1 if op2 >= 0 else -(-op2 // op1) # 除法判断一下

def evaluation(stack, op_stack):
if len(stack) < 2 or stack[-2] == '(':
return
sign = op_stack.pop()
op1, op2 = stack.pop(), stack.pop()
res = helper(op1, op2, sign)
stack.append(res)

def greedy_evaluation(stack, op_stack):
return sum(stack)
# 就不用憨憨的再一个一个pop
# res = None
# while op_stack:
# res = res if res != None else stack.pop(0)
# sign = op_stack.pop(0)
# op2 = stack.pop(0)
# res = helper(op2, res, sign)
# return res if res != None else stack[0]

有两个点需要注意:

1.不要用pop(0),因为是O(n)的开销。

2.加减法就不用存储到op栈了,记录操作符的sign然后给操作数修改一下就行。这样最后算的时候直接sum数据栈就行。

3.如果是用2的方法那么对除法要特殊处理,因为整除除法总是向0靠近。

阅读全文 »

一、题目要求

实现一个对于正整数和“+, -, (, )”的计算器。每个表达式都是合法的。

二、分析

两个栈,操作数栈存储操作数 + “(“,操作符栈存储其他操作符。数字直接入栈,操作符遇到右括号时将对应的左括号删除并求值,其他符号直接求值。

三、实现

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
72
73
74
75
76
77
78
79
from enum import Enum

State = Enum('State', ('begin', 'num', 'op'))

class Solution:
def calculate(self, s: str) -> int:
nums = [str(a) for a in range(10)]

def helper(op1, op2, sign):
# 顺序不要搞反了
if sign == '+':
return op1 + op2
if sign == '-':
return op2 - op1
if sign == '*':
return op1 * op2
if sign == '/':
return op2 / op1

def evaluation():
if len(stack) < 2 or stack[-2] == '(':
return
sign = op_stack.pop()
op1, op2 = stack.pop(), stack.pop()
res = helper(op1, op2, sign)
stack.append(res)

stack = []
op_stack = []
v = 0
compute_flag = 0
state = State.begin
if s[0] in nums:
state = State.num
else:
state = State.op

i = 0
while i < len(s):
c = s[i]
if c == ' ':
i += 1
continue
if state == State.num:
if c in nums:
v = v * 10 + int(c)
else:
state = State.op
stack.append(v)
# print('stack: {}'.format(stack))
v = 0
evaluation()
continue
elif state == State.op:
if c in nums:
state = State.num
continue
else:
if c == '(':
stack.append(c)
compute_flag = 0
elif c == ')':
last = stack.pop()
stack[-1] = last # 删除倒数第二个元素(对应的左括号)
evaluation()
else:
compute_flag = 1
op_stack.append(c)
else:
print('illegal state.')
i += 1
# print('stack: {}'.format(stack))
# print('op_stack: {}'.format(op_stack))

if state == State.num:
stack.append(v)
while op_stack:
evaluation()
return stack[0]
阅读全文 »

一、题目要求

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

二、分析

首先利用回溯能够没有遗漏的找到所有的组合,但是这样是会重复的。

我们可以首先对数组升序排列,然后对DFS搜索增加一个index,这样就控制了组合里面数的顺序,确保不会重复。

剪枝,如果当前的选择无法组合,那么当前轮之后的选择直接跳过。

三、思路

1.基础题

阅读全文 »