0%

在 17 世纪,德国数学家戈特弗里德·莱布尼茨(Gottfried Leibnitz)提出了一种机器,该机器可以读取任意数学陈述,并根据数学公理来判断其是否正确。但是,每个陈述都可以这样判定么?或者我们所能知道的东西是否存在着极限呢?这个问题被称为 Entscheidungsproblem(判定性问题)。

两个世纪后,另一位德国数学家戴维·希尔伯特(David Hilbert)乐观地宣布,判定性问题的答案必须是,是的,我们能并且会知道任何数学问题的答案。他于 1930 年在德国柯尼斯堡(Königsberg)的一次讲话中曾说:

Wir müssen wissen — wir werden wissen.(“我们必须知道 —— 我们会知道。”)

但是我们会知道吗?

数学的极限

历史表明希尔伯特的乐观主义是短暂的。同年,奥地利数学家库尔特·哥德尔(Kurt Gödel)通过证明他著名的不完备定理(incompleteness theorem)表明我们的数学知识是有极限的。

下面是理解哥德尔定理的简单方法。请考虑以下陈述。

命题 S:此命题不可被证明。

现在,假设在数学中我们可以证明 S 为真。但是这样一来,命题 S 本身将为假,从而不一致。好吧,那么让我们假设相反的情况,即我们无法在数学中证明 S。但这将意味着 S 本身为真,并且数学中包含至少一个无法证明为真的真命题。因此,数学要么不一致,要么不完备。如果我们假设它是一致的(命题不能同时为真和假),这只能得出数学是不完备的结论,即存在不能完全证明是真命题的真命题。

哥德尔(Gödel)对不完备定理的数学证明比我在此概述的要复杂得多,这从根本上改变了希尔伯特(Hilbert)所宣称的完整知识是可行的观点(“我们会知道”)。换句话说,如果我们假设数学是一致的,那么我们必然会发现无法证明的真命题。

例如,哥德巴赫猜想(The Goldbach conjecture),根据该猜想,每个偶数都是两个素数的和:

6 = 3 + 3
8 = 3 + 5
10 = 3 + 7
12 = 7 + 5,依此类推。

至今还没有人发现反例,如果猜想是真的,那也就不存在反例。得益于哥德尔的贡献,我们知道有无法证明的真命题,但不幸的是,我们没有办法找出这些命题。哥德巴赫猜想可能就是其中之一,如果是这样,那么尝试证明它就是浪费时间。

Kurt Gödel(左)和 Alan Turing(右)

计算的极限

艾伦·图灵(Alan Turing)第一次了解哥德尔不完备定理时还是剑桥大学的研究生。在那段时间里,图灵忙于做一种机器的数理设计。这种机器可以处理任何输入并计算结果,与莱布尼茨几个世纪前所设想的相似。今天这些概念化的机器被称为图灵机,是现代数字计算机的蓝图。简单来说,图灵机可以看作现代计算机程序。

图灵当时在研究所谓的停机问题,可以描述如下:

是否有一个程序可以确定另一个程序会停止(停机)还是不停(死循环)?

图灵证明了停机问题的答案是“否”,即不存在这样的程序。与哥德尔的工作类似,他也是用“反证法(proof by contradiction)”证明的。假设存在一个程序 halts(),它能确定给定程序是否将停止。但是,我们还可以构建以下程序:

1
2
3
4
def g():
if halts(g):
loop_forever()
return

看看这里发生了什么?如果 g 成立,则 g 不成立;如果 g 不成立,则 g 成立。无论哪种方式,我们都将得到一个矛盾。因此,程序 halts() 不存在。

哥德尔证明了数学是不完备的,而图灵证明了在某种意义上计算机科学也是“不完备的”。某些程序根本不存在。这不仅是理论上的好奇:停机问题在当今的计算机科学中具有许多实际意义。例如,如果我们希望编译器为给定的程序找到最快的机器码,那么我们实际上是在尝试解决停机问题 —— 而我们已经知道该问题是无法解决的。

一个复杂的蛋白质结构 —— 预测蛋白质如何折叠是一个 NP 问题(NP-problem)

知识的实际极限:P 与 NP 问题

哥德尔和图灵通过揭示存在着的一些根本无法解决的问题,证明了我们所能知道的在理论上存在极限。但是此外,还有其他问题是理论上可以解决,但是因为求解的时间太长了,而我们实际上无法解决的。这里我们将会说明 P 问题和 NP 问题的区别。

P 问题是可以在“合理的时间”内解决的问题。在这里,“合理的时间”的含义是“多项式(polynomial)时间”(因此称为 P)。求解这些问题的计算复杂性随问题输入规模的增长而倍数增加(想想乘法或排序问题)。

另一方面,NP 问题是无法在合理时间内解决的问题。NP 是非确定性多项式(non-deterministic polynomial)的英文缩写,它的含义是可以用多项式级的计算复杂度验证问题的一个解,但不能用多项式级的计算复杂度求解。求 NP 问题的解的复杂度是指数级的,而不是多项式的,这会产生巨大的实际差异。NP 问题的例子包括最佳调度,预测蛋白质的折叠方式,加密消息,解决数独难题,最佳包装(又称背包问题)或最佳路由(又称旅行商问题)。一些问题(例如找到函数的离散傅立叶变换)最开始属于 NP 问题,但由于开发了新的、巧妙的算法来简化求解,最终变成了 P 问题。

当今计算机科学领域中最大的未解之谜之一就是 P 与 NP 问题:P 是否等于 NP?换句话说,对于所有我们可以在合理时间内验证一个解的问题,我们是否能在合理的时间内解?

P 与 NP 问题非常重要,因此被列入“千禧年大奖难题(Millenium prize problems)”。如果找到答案,你会赢得一百万美元。再怎么夸大这个问题的重要性也不为过:P=NP 的世界与 P≠NP 的世界有着根本的不同。如果 P=NP,那么我们可以肯定地说,有一种更快的方法可以解决数独难题,或者预测蛋白质的折叠方式,我们只是还没有找到这种方法。毫无疑问,了解蛋白质的折叠方式会对现实世界产生全方面的影响,例如理解阿兹海默症的病理或治愈癌症。

如今,大多数科学家相信 P 不等于 NP,但是我们能确定吗?P 与 NP 问题本身可能类似于希尔伯特的 Entscheidungs 问题或图灵的停机问题:这个问题可能根本没有答案。

Read more »

68747470733a2f2f63646e2d696d616765732d312e6d656469756d2e636f6d2f6d61782f31323030302f312a742d64725f3543724b663435524530557577773273672e6a706567

通过本文,我们将熟悉树莓派 GPIO 及其技术规范。并且,我们将通过了一个简单例子,说明如何使用树莓派的 I/O 控制 LED 和开关。

你可能见过 “IoT” 这个术语,它是 Internet of Things(物联网) 的缩写。意思是,人们可以通过互联网控制一台设备(即“物” thing)。比如,用手机控制你房间内的智能电灯泡就是一种物联网的应用。

由于物联网设备可通过互联网控制,所以 IoT 设备需要始终与互联网相连。我们主要有两种方式将设备连接至互联网:以太网网线和 WiFi。

物联网设备可被用于各种目的。例如,你可以使用物联网来控制你家的室内温度、照明或者在回家前打开某些设备,所有这些操作都只需要通过你的手机便能实现。

那么,物联网设备的技术规范有哪些?简言之,它应该包含连接到互联网的工具,有一些输入和输出接口来读写设备的模拟或数字信号,并且使用最少的硬件来读取和执行程序指令。

一个物联网设备配有一个硬件组件,为外部设备读取数字数据和取电提供接口。该接口就是 GPIO 或称作 General Purpose Input Output(通用输入输出接口) 。这种硬件组件基本上都是由一系列可以连接到外部设备的引脚(或管脚,pin)构成。

这些 GPIO 引脚可以被程序控制。比如,在满足一些条件的情况下,我们可以给一个 GPIO 引脚施以 5V 的电压,任何连接到该引脚的设备都会被开启。程序也能够监听来自互联网的信号,并根据该信号对 GPIO 引脚进行控制。这就是物联网。

Read more »

css-vs-js

欢迎你踏上了一条在前端世界中饱含争议的道路!相信大部分读者会在关于如何在 JavaScript 应用中处理 CSS 这一话题上产生共鸣。

文章伊始,先声明一句:无论是在基于 Vue、Angular 还是 React 构建的应用,针对如何处理 CSS,世界上并没有任何放之四海而皆准的方法。各个项目皆有不同,每种方式也有可取之处!可能这么说显得含糊其辞,但就我所知,在我们的开发社区内,那些追寻新知识,推动网页开发向前发展的人举目皆是。

让我们放下对本文话题的感性认知,先领会下 CSS 世界架构的奇妙之处。

Read more »

Enhancing Pre-trained Chinese Character Representation with Word-aligned Attention 一文是我和组内同学、师兄的合作工作,作为短文录用于 ACL 2020。

说起来很奇妙,这个工作最开始是为了做 Aspect-extraction 相关工作而开始的,效果很一般。但是在调参的时候发现单纯作为序列标注任务的一个额外的特征输入,居然得到了一丁点提升。也就是这一点点提升,我决定把它应用在预训练语言模型中做一做实验。在经过大量的试错、调整和调参后,最终得到了这么一种新奇的方法,可以让预训练语言模型额外获得一些 word-level 的信息,在各个需要词信息的任务中都有那么一点提升。但这个方法相当的实验化且缺乏理论支撑,并且还有一些别的致命问题(如果没有这些问题谁会去投短文…),会在后面一一说明。下文将结合在会上做远程汇报的 slide,简单描述这个工作。

ppt 已经放在这里

反正就是想写个笔记给自己看,又不是写论文,就不用玩啥避重就轻之类的套路了,吐槽为主(反正没人看)。

概述

-w591

首先是预训练语言模型在最近有了很大的发展,上面那个图是 thunlp 组同学整理的。现在预训练语言模型发展方向就是在不断改进预训练任务和模型结构,让其能适配更大量的数据的数据,方便刷榜,看看 GPT-3 那 1700 亿个参数就心酸。当然也有许多做压缩模型、蒸馏的工作,这些现在应用起来反而更实用一些。还有一些工作在尝试融入额外信息,比如:清华 nlp 提出的 ERNIE 在 BERT 中融入知识图谱;百度的 ERNIE 1.0 融入实体信息,ERNIE 2.0 花式训练;香侬科技魔幻的 Glyce 融合字形;创新工场的 ZEN 用 n-gram 去融合分词信息。

-w399

但是不管怎样边,主流的预训练语言模型都和上图一样,分预训练和微调两个阶段(GPT-3 那种号称不用微调的除外),现在大家的主要工作也是集中在预训练阶段去做的。近些年这块最经典的工作当然非 BERT 莫属了,所以我后面都是在 BERT 上跑实验。

不管啥模型,第一件事都是 tokenizer。对于 BERT 来说,英文的 token 是 word-piece,中文的是字(这也对后面的实验造成了很大的麻烦,因为要对齐)。而且已经有相当多的工作证明了,对于中文在 character-level 建模会比较合适(香侬在 ACL2019 的那篇《Is Word Segmentation Necessary for Deep Learning of Chinese Representations》很是经典)。不过在实际应用中,包括很多 Application of NLP 领域的文章,还有我自己的文章,都发现将词信息融入到文本表示中会对应用有效果。

所以,这篇论文实质上就是在实验看有什么办法去各种拐着弯儿向 character-level 的表示模型融入词信息。

动机

至于动机也很简单。玄一些就是把一些眼动追踪的研究挪过来建模:

[1] Reading spaced and unspaced chinese text: Evidence from eye movements
[2] Parafoveal load of word N+1 modulates preprocessing effectiveness of word N+2 in Chinese reading
[3] Cognitive mechanisms in reading ancient Chinese poetry: evidence from eye movements

上图就是上面几篇论文的部分结论,总结起来就是人阅读中文的时候对每个词付出的“注意度”类似。

实在一些就是想找一些方法来改变 transformer 的 attention 分布,或者找一种可以折中 soft-attention 与 hard-attention 的方法,在维持原 attention 机制的情况下,用比较 soft 的方法来实现比较 hard 的效果,来方便某些任务(后记中有写)。

总之,我就是根据这些动机进行了实验。

模型

单个分词器下的情况

(在师兄指导下画的图,还挺好看的)

模型很简单,就是在预训练语言模型对下游任务进行微调时,中间插上一层 multi-head attention 的变体。

首先,可以使用分词工具将输入的文本进行分词,具体来说就是讲由字构成的序进行划分(parition),我们把这种划分策略称为 $\pi$。

得到划分 $\pi$ 后,将其应用于正常得到的 attention 权重矩阵上,可以得到按词划分的(word-based)字级别(character-level)的 attention 权重组合。

为了同时考虑:1. 句子中所有词的语义表示;2. 句子中最重要的词的语义表示 这两种情况,我们使用 mix-pooling 来对 mean-pooling 和 max-pooling 进行混合:

其中 $\lambda$ 为参数(后面做实验观察 $\lambda$ 发现,还是 MeanPooling 更重要一些)。

比如上图就是这种 attention 权重矩阵的可视化效果图。这个例子是从情感分类任务模型中拿出来试的,可以看到 attention 权重矩阵被转化为了 character-level to word-level 的形式,而实际上还是 character-level 的模型,保留了字建模的优秀表示,同时也做到了前面动机所说的接近 hard-attention 的效果。

把这样的 attention 权重再拿回 character-level 表示去调整它,就能得到最终的字表示,送往后续的下游任务。

多个分词器下的情况

然而,众所周知,分词器经常会出现问题。

上图是论文里的图(为了和平特意找了个都没分错的例子),这几个分词器得到的结果都是对的,但是其粒度不同。

为了减少分词错误,以及用上不同粒度级别的特征,我们找了一种简单的方法,同时用上多个分词工具的分词结果。

真的很简单,就是几个分词器的结果,分别得到下游表示之后过个线性层结合在一起而已。

实验证明这样是有一定效果的。

实验结果

都在原文里有,没啥槽点,就是做实验耗的时间太多了。

总结

总结一下这个工作的优缺点:

优点:

  • 提出了这么一种有意思的结构
  • 这么一种有意思的结构可以融入一些分词信息,并且对预训练语言模型的下游任务有一些帮助
  • 单纯融入一种分词信息不够,就多加几种分词信息

缺点:

  • 实在缺乏理论支撑
  • 预处理的真的特别特别慢(尤其是要用几种分词器来分词),并且数据预处理无比复杂(因为各个分词器的处理逻辑都不一样,各种特殊符号、数字、英语、日语、繁体啥的全部都要单独处理,尤其是 BERT 会将英语单词 tokenize 成 word-piece,导致 token 对不上,前期实验有 80% 以上的时间都是在搞这些预处理)
  • 在 forward 的时候把 transformer 的时间复杂度 $O(n^2)$ 变成了 $O(d n^2)$(这还好是常数级),但是要命的是,在这个方法中,每一条训练数据都会有各自不同的分词方式,都只能各自去分段计算 mix-pooling,这导致完全无法应用 cudnn 原语加速,也完全没可能写成矩阵运算来利用 GPU batch 加速,即使直接用 cuda 编程也没法改善。连 forward 都这么慢,backward 更不用说了……这点是致命的,让我的实验时间变得特别特别长,跑个 CMRC 数据集硬生生把 6 个小时的训练时间搞成了 28 个小时,心态都炸了。

总结下来,这个工作其实缺点其实挺明显的,主要集中在预处理和速度极慢这两块上。吐槽:但投稿时 call for short paper 写明白了就是欢迎分享这些不是很完善的 idea 呀,不懂为啥要使劲冲着缺陷打,没这些问题投长文不香吗?

优点主要还是这个结构足够新颖。由于这种东西的预处理实在太 dirty 了,跑起来也慢的令人抓狂,我是不打算 follow 这个工作继续做下去了。但是,这种有意思的结构可以用在其它一些 NLP 应用里面,还是可以做一做的。

后记

在郁博文师兄的帮助下第一次写这种实验性质的短文也是挺有意思的。我受到的指导,和我写的文章,一般都是发现问题->分析问题->分析方案->理论支撑方案->实验支撑理论这么个范式;而这篇文章是发现问题->分析问题->哇,有灵感了->实验结果还不错这么个流程,还是蛮奇妙的。但说到底还是缺乏理论支撑,我去年曾尝试用离散数学去建模分词和这个模型的过程(有图为证),还试图用正则化或者标准化等深度学习术语来解释这种模型,但都成功地浪费了大量的时间,在没有理论支撑的情况下,也只能这样了。

-w202

这篇文章的录用还是很侥幸的。在审稿 rebuttal 的时候,审稿人给的分和评价都很一般。正如前文所说,文本的确有很多问题,但几位审稿人最主要的关注点居然都主要集中在空间复杂度和训练参数数量上面,没有抓主要矛盾而是重点抓次要矛盾去了。所以简单回答这些关于参数、空间占用之类的问题值后,有位审稿人改了分,这才被录用。

最后这篇论文出来的时候真是命运多舛,赶上了 2020 年的疫情,不让回实验室,资料、代码啥的全在工位台式机上,又赶上组里的大工程和自己的毕设,只能抽空远程一点一点扒代码,扒到开会都没扒完;后来都有好几位老师同学发邮件索取了,都没办法直接发给人家可以直接跑的模型,只给一个老师发了最主要的那个 attention align 模块,也不知道有没有帮上他的忙;好在后来找了点办法能远程直连了,不然更难受。

最近申博士也很难受,因为特总美国学校鸽了、欧洲学校因为疫情考不了雅思并且因为经济下滑很多组都没有 fund、国内那两所学校又卷到没有坑留、找工作还没来得及刷题,整个人都不好了。。
真希望以后不要再有这样的日子了,赶紧刷题复习去:(

因为图省硬盘,直接用了 --depth=1 命令 clone,导致在本地追踪不到远程的分支,并且用 git branch -a 看不到远程分支,当然也不能 checkout 到 origin/remote 上去。git fetch allgit fetch origin 也都拿不到内容。

因为有 slash 的内容和已经准备好的 commit,又不想重新去 clone,想起来 git 使用 fetch 时就是去找 .git/config 文件里的 remote origin 字段,因此直接改了这个文件的内容:

1
vim .git/config

找到

1
2
3
[remote "origin"]
url = https://github.com/xxx/xxx
fetch = +refs/heads/master:refs/remotes/origin/master

果然 head 和 remote origin 都指向 master,把 master 改成 *:

1
2
3
[remote "origin"]
url = https://github.com/xxx/xxx
fetch = +refs/heads/*:refs/remotes/origin/*

接着 git fetch --all,就拿到了全部的分支,现在就可以直接去 checkout 了~

上季度,我在学校辅助一门 Python 课程的教学,在此过程中学到了很多图像处理的知识。我希望通过本文分享一些关于边缘检测的知识,包括边缘检测的理论以及如何使用 Python 实现边缘检测。


为何检测边缘?

我们首先应该了解的问题是:“为什么要费尽心思去做边缘检测?”除了它的效果很酷外,为什么边缘检测还是一种实用的技术?为了更好地解答这个问题,请仔细思考并对比下面的风车图片和它的“仅含边缘的图”:

Image of pinwheel (left) and its edges (right)

可以看到,左边的原始图像有着各种各样的色彩、阴影,而右边的“仅含边缘的图”是黑白的。如果有人问,哪一张图片需要更多的存储空间,你肯定会告诉他原始图像会占用更多空间。这就是边缘检测的意义:通过对图片进行边缘检测,丢弃大多数的细节,从而得到“更轻量化”的图片。

因此,在无须保存图像的所有复杂细节,而 “只关心图像的整体形状” 的情况下,边缘检测会非常有用。


如何进行边缘检测 —— 数学

在讨论代码实现前,让我们先快速浏览一下边缘检测背后的数学原理。作为人类,我们非常擅长识别图像中的“边”,那如何让计算机做到同样的事呢?

首先,假设有一张很简单的图片,在白色背景上有一个黑色的正方形:

Our working image

在这个例子中,由于处理的是黑白图片,因此我们可以考虑将图中的每个像素的值都用 0(黑色)1(白色) 来表示。除了黑白图片,同样的理论也完全适用于彩色图像。

现在,我们需要判断上图中绿色高亮的像素是不是这个图像边缘的一部分。作为人类,我们当然可以认出它图像的边缘;但如何让计算机利用相邻的像素来得到同样的结果呢?

我们以绿色高亮的像素为中心,设定一个 3 x 3 像素大小的小框,在图中以红色示意。接着,对这个小方框“应用”一个过滤器(filter):

对局部像素框应用纵向过滤器

上图展示了我们将要“应用”的过滤器。乍一看上去很神秘,让我们仔细研究它做的事情:当我们说 “将过滤器应用于一小块局部像素块” 时,具体是指红色框中的每个像素与过滤器中与之位置对应的像素进行相乘。因此,红色框中左上角像素值为 1,而过滤器中左上角像素值为 -1,它们相乘得到 -1,这也就是结果图中左上角像素显示的值。结果图中的每个像素都是用这种方式得到的。

下一步是对过滤结果中的所有像素值求和,得到 -4。请注意,-4 其实是我们应用这个过滤器可获得的“最小”值(因为原始图片中的像素值只能在 0 到 1 之间)。因此,当获得 -4 这个最小值的时候,我们就能知道,对应的像素点是图像中正方形顶部竖直方向边缘的一部分。

为了更好地掌握这种变换,我们可以看看将此过滤器应用于图中正方形底边上的一个像素会发生什么:

可以看到,我们得到了与前文相似的结果,相加之后得到的结果是 4,这是应用此过滤器能得到的最大值。因此,由于我们得到了 4 这一最大值,可以知道这个像素是图像中正方形底部竖直方向边缘的一部分。

为了把这些值映射到 0-1 的范围内,我们可以简单地给其加上 4 再除以 8,这样就能把 -4 映射成 0(黑色),把 4 映射成 1(白色)。因此,我们将这种过滤器称为纵向 Sobel 过滤器,可以用它轻松检测图像中垂直方向的边缘。

那如何检测水平方向的边缘呢?只需简单地将纵向过滤器进行转置(按照其数值矩阵的对角线进行翻转)就能得到一个新的过滤器,可以用于检测水平方向的边缘。

如果需要同时检测水平方向、垂直方向以及介于两者之间的边缘,我们可以把纵向过滤器得分和横向过滤器得分进行结合,这个步骤在后面的代码中将有所体现。

希望上文已经讲清楚了这些理论!下面看一看代码是如何实现的。


如何进行边缘检测 —— 代码

首先进行一些设置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt

# 定义纵向过滤器
vertical_filter = [[-1,-2,-1], [0,0,0], [1,2,1]]

# 定义横向过滤器
horizontal_filter = [[-1,0,1], [-2,0,2], [-1,0,1]]

# 读取纸风车的示例图片“pinwheel.jpg”
img = plt.imread('pinwheel.jpg')

# 得到图片的维数
n,m,d = img.shape

# 初始化边缘图像
edges_img = img.copy()
  • 你可以把代码中的“pinwheel.jpg”替换成其它你想要找出边缘的图片文件!需要确保此文件和代码在同一工作目录中。

接着编写边缘检测代码本身:

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
%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt

# 定义纵向过滤器
vertical_filter = [[-1,-2,-1], [0,0,0], [1,2,1]]

# 定义横向过滤器
horizontal_filter = [[-1,0,1], [-2,0,2], [-1,0,1]]

# 读取纸风车的示例图片“pinwheel.jpg”
img = plt.imread('pinwheel.jpg')

# 得到图片的维数
n,m,d = img.shape

# 初始化边缘图像
edges_img = img.copy()

# 循环遍历图片的全部像素
for row in range(3, n-2):
for col in range(3, m-2):

# 在当前位置创建一个 3x3 的小方框
local_pixels = img[row-1:row+2, col-1:col+2, 0]

# 应用纵向过滤器
vertical_transformed_pixels = vertical_filter*local_pixels
# 计算纵向边缘得分
vertical_score = vertical_transformed_pixels.sum()/4

# 应用横向过滤器
horizontal_transformed_pixels = horizontal_filter*local_pixels
# 计算横向边缘得分
horizontal_score = horizontal_transformed_pixels.sum()/4

# 将纵向得分与横向得分结合,得到此像素总的边缘得分
edge_score = (vertical_score**2 + horizontal_score**2)**.5

# 将边缘得分插入边缘图像中
edges_img[row, col] = [edge_score]*3

# 对边缘图像中的得分值归一化,防止得分超出 0-1 的范围
edges_img = edges_img/edges_img.max()

有几点需要注意:

  • 在图片的边界像素上,我们无法创建完整的 3 x 3 小方框,因此在图片的四周会有一个细边框。
  • 既然是同时检测水平方向和垂直方向的边缘,我们可以直接将原始的纵向得分与横向得分分别除以 4(而不像前文描述的分别加 4 再除以 8)。这个改动无伤大雅,反而可以更好地突出图像的边缘。
  • 将纵向得分与横向得分结合起来时,有可能会导致最终的边缘得分超出 0-1 的范围,因此最后还需要重新对最终得分进行标准化。

在更复杂的图片上运行上述代码:

得到边缘检测的结果:


以上就是本文的全部内容了!希望你了解到了一点新知识,并继续关注更多数据科学方面的文章〜

掘金链接:https://juejin.im/post/5e3d4b53e51d4526c26fadd4

入门机器学习应用,尤其是需要对实际数据进行处理时,是很困难的。

一般来说,机器学习教程会推荐你或要求你,在开始拟合模型之前,先以特定的方式准备好数据。

其中,一个很好的例子就是对类别数据(Categorical data)进行 One-Hot 编码(又称独热编码)。

  • 为什么 One-Hot 编码是必要的?
  • 为什么你不能直接使用数据来拟合模型?

在本文中,你将得到上述重要问题的答案,并能更好地理解机器学习应用中的数据准备工作。

Read more »

本文作于 2018 年,被 AAAI 2019 接收。作者是浙大博士,在 Northwestern University 做博后期间做出了此工作。文章中开源了实现代码:https://github.com/yao8839836/text_gcn

概述

本文解决的是自然语言处理中最基础的任务 - 文本分类任务。利用近年大火的图神经网络,作者通过词与文章的共现信息和 TF-IDF 权重和互信息权重将无结构数据文本进行了构图,并利用 Graph Convolutional Network(GCN)捕获图中的文档-词、词-词、文档-文档关系,从而进行文本分类。

具体来说,本文主要有以下两个贡献点:

  1. 提出了使用图神经网络来解决文本分类问题,有效利用了文档、词等的异构信息
  2. 在 benchmark 上达到了 state-of-the-art 的效果

背景与相关工作

文本分类

传统的文本分类方法主要依靠特征工程,在深度学习兴起后,各种深度学习框架代替了这个步骤。人们利用文本的分布式表示(embedding),使用各种 CNN、RNN、LSTM 等神经网络来捕获 embedding 中的语义信息,进行分类。本文就是在此基础之上,用 GCN 来捕获 Graph 中的 语义信息从而实现准确分类。

图网络

近些年为了突破传统神经网络只能应用于对齐的 grid 数据的限制,出现了可以应用于 Graph 的图神经网络。其中,GCN 方法简单有效,在图的各个节点上计算其邻居的聚合信息表示。因此,作者 employ 了 GCN 方法,将其用于图结构的学习。

数据

作者在 5 个常用的公开数据集上进行了实验。这 5 个数据集的基本信息如下:

-w692

在实验前,作者利用 NLTK 去除了前 4 个数据集的停用词,并去除了频次小于 5 的低频次。MR 数据集因为句子太短了,没有必要再删。

方法

构图方法

作者最终构成的图结构如下图所示:

-w922

在图中,左边是文本构成的图,右边是经过 GCN 得到的图表示。在左图中,以“O”开头的节点是文档节点,白色圈里有单词的节点是单词节点,黑色的线是文档-单词关系,灰色的线是单词-单词关系。右图中的$R(x)$表示文档或单词$x$的表示。

具体来说,在这个情景中,构图主要在于如何对文档-单词和单词-单词的边赋权。作者使用了下面公式所示的构图方式:

$A_{ij}$表示从节点 i 连到节点 j 的边的权重。简单来说,就是对文档-单词的边算 TF-IDF 作为权重,对单词-单词的边使用 PMI 做权重。PMI 是单词与单词的互信息,具体计算方式是:

其中,#W 是滑动窗口,具体来说,PMI 就是算单词 i 和单词 j 同时出现的概率比上单词 i 和单词 j 单独出现的概率。

分类算法

在 GCN 框架内,使用 BP 算法来优化节点表示,并在 GCN 后加一层 Dense 层和激活层,利用 softmax 来进行分类。作者将其表示如下:

其中,$ \tilde { A } X W _ { 0 } $ 和前面的公式 $L ^ { ( 1 ) } = \rho \left( \tilde { A } X W _ { 0 } \right)$ 一致,都是通过对 W 的优化来进行节点的表示。对上面的公式进一步拆解,可以记为:

$E_1$ 就是对单词和文档节点的表示。

$E_2$ 就是对节点的第二层级表示。因此,本文相当于用了 2 层 GCN 进行图表示,然后用 softmax 进行分类。在分类优化时,采用了交叉熵损失函数:

实验

baseline 设置

作者设置了多种 baseline,包括:

  • TF-IDF + 线性分类器
  • CNN 文本分类(Convolutional neural networks for sentence classification,EMNLP)
  • LSTM 文本分类(Recurrent neural network for text classification with multi-task learning,IJCAI)
  • Bi-LSTM
  • PV-DBOW(Distributed representations of sentences and documents,ICML)
  • PV-DM(同上)
  • PTE(Automatic lymphoma classification with sentence subgraph mining from pathology reports)
  • FastText(Bag of tricks for efficient text classification,EACL)
  • SWEM(Baseline needs more love: On simple wordembedding-based models and associated pooling mechanisms,ACL)
  • LEAM(Joint embedding of words and labels for text classification,ACL)
  • Graph-CNN-C(Convolutional neural networks on graphs with fast localized spectral filtering,NIPS)
  • Graph-CNN-S(Spectral networks and locally connected networks on graphs,ICLR)
  • Graph-CNN-F(Deep convolutional networks on graphstructured data)

可以看到,作者的实验非常完善且置信,应用了当时几乎全部的文本分类方法来进行对比。

实验设置

作者用了 200 维作为 embedding 维数,20 作为滑动窗口大小,学习率设为 0.02,Dorpout 设为 0.5,分别随机采样 10 % 数据作为验证集和测试集。

实验结果

最终,得到了如下表所示的实验结果:

-w1067

该表有两个维度,数据集和模型。从此也可以看出,作者实验做的非常充分。

结果分析

从上表可以看到,除了 MR 数据集外,作者提出的 Text GCN 方法在其余全部数据集上都得到了最好的结果。猜测可能是由于 MR 数据集中数据过于短,构图效果不佳造成的。

此外,作者利用 t-SNE 方法(Visualizing data using t-sne,JMLR)对结果进行了可视化,用于分析训练得到的 embedding 的效果。结果如下:

-w513

可以看到,作者提出的 Text GCN 方法得到的文档表示在 t-SNE 表现是可分的,类间距离较大,优于用来对比的其余两种方法。

总结

作者提出的 Text GCN 方法在文本分类任务中,在多个数据集上得到了最好的结果。我认为其最大创新点在于:1、引入了 GCN 来做文本分类 2、提出了这种构建带权边图的方式。整个工作非常完备,应该要做的实验基本都做了,令人信服,我们做文本分类应当也要学习本文的实验方式。此外,文章最后的节点表示可视化也很有说服力。

对于后续工作,我觉得一个是可以 follow 一些新的构图方式和 GNN 框架,再有就是在 loss 方面进行改进,优化表示的空间分布。此外,可以考虑结合一些最新的语言模型方法(BERT、XLNET 等)改善结果。以及,可以对分类器那块进行一些改进,比如引入 Attention 等方法可能可以提升效果。