Structural Deep Embedding for Hyper-Networks 阅读笔记

所谓的Network Embedding就是指,对于一个网络(或者简单地说,图),给每个节点一个特征向量X_i,而该特征向量能够表征网络中节点的结构信息。这篇文章是Network-Embedding中的一篇较为重要的文章。


Abstract

网络嵌入(Network Embedding)近年来吸引了很多人的注意,传统的方法多局限于由点与点二元组关系形成的图,但是,在实际生活中,图本身很难是标准的二元组关系,在有些情况下,一条关系(relationship)会涉及到三个甚至更多的主体,我们可以称之为超边(hyperedge)。当超边成为一个不可分割的独立整体,则传统算法会遇到不少困难。本文将介绍一种算法,用于对于超网络(hyper-network)的嵌入。并且证明,传统算法不可能成功Embedding存在不可分割超边的网络。

Introduction

对于hyper-network的embedding,一个非常简单的方式是将其转化为普通图,这里有两种常用做法,一种是直接将图中的超边转化为一个“团(clique)”,另一种是为超边本身分配一个虚拟节点,并向其包含的所有元素连边。他们分别被称作clique expansion和star expansion。在这些算法中,我们都假设了超边是可分的,即,一个超边包含的点集的子集仍然是有意义的,这在实际生活中是不存在的。上述的算法的诸多问题便是这篇文章需要解决的——

  • 节点的不可分解性:如电影的推荐中的<user, moive, tag>三元组的子集 <user,tag>是不合法的。
  • 结构保留特性:实现局部细节的embed是相对简单的,但是网络整体结构的embed却相对复杂。而我们还需要解决同时embed局部、全局的特征。

对于第一个问题,文章设计了不可分解的多元组相似性函数,这种函数本身的结构保证了超边的子集不会存在。我们从理论上证明该函数是非线性性的,如果使用带非线性层的神经网络实现,则可以实现强力的非线性性。

对于第二个问题,我们使用自编码器来保证相似的节点拥有相似的embedding。

Related Work

早期的图Embedding使用了线性代数的方式,使用图的主特征向量来作为图的编码。由于线性代数中的特征向量分解是一个相对昂贵的方式,因此实际上这种做法并不常用

近年来,一个叫做RamdomWalk的算法提出新的思路,通过刻画一系列随机游走的路径来Embed一个图。在此之后,很多学者都在其基础上进行了创新,诸如使用更好的刻画函数,或者引入深度学习来优化。

然而,上述所有的算法,假设了图是标准的由边的二元组构成的。在存在超边的途中,现有的算法不是无法保证超边的不可分解性,就是过于低效。

Notations and Definitions

术语

如右图所示,相比于图论中的“无向图”,我们的超图更类似于

一个“有向图”。也可类比于之前提到的<user,movie,tag>三元组,节点本身是有类别的。我们定义点集

V = \{V_t\}_{t=1}^{T}

表示所有节点可以按照类别分为T类。

超边边集则可以表示为

E=\{(v_1,v_2,\dots,v_{n_i})\} (n_i \geq 2)

最终第j类的第i个节点的Embedding可以计算为

X_i^j

对于N个节点,我们可以定义相似性函数

\mathcal{S}(X_1,X_2,\dots,X_n)

相似性

节点的一阶相似性(First-order Proximity)刻画了N个节点的直接相似性,其定义非常简单,只要这N个节点组成一个超边,则这N个节点的一阶相似性是1。当然,这里就隐含定义了这N个节点的任意子集都不存在一阶相似性。

显然,单纯的一阶相似性定义是不完善的,这时,我们可以进一步定义二阶相似性。

二阶相似性定义在任意两个节点上,当两个节点x_ix_j共有邻居时,他们应该是二阶相似的。这也应该反映到节点的Embedding上面。举一个例子,在上面那张图上,A_1的邻居应该是\{(L_2,U_1),(L_1,U_2)\},而由于A_1A_2拥有共同的邻居(L_1,U_2)则他们应该是二阶相似的。

Deep Hyper-Network Embedding

模型设计

我们计算的网络Embedding需要保证一阶相似性,即对于模型生成的Embedding值X_i,倘若一个点集组成了超边,则他们的X_i的一阶相似性函数应该尽可能大,反之尽可能小——

特征1:我们令X_i为模型生成的Embedding值,则

  • (v_1, v_2, \dots , v_n) \in E, \mathcal(S)(X_1, X_2, \dots, X_n)应该尽可能大(或者说至少得大于某个比较大的阈值)
  • (v_1, v_2, \dots , v_n) \notin E, \mathcal(S)(X_1, X_2, \dots, X_n)应该尽可能小(或者说至少得小于某个比较小的阈值)

有了上述定义,文章进一步通过列举反例,证明了倘若\mathcal(S)仅仅是依赖于X_1,X_2,\dots, X_n的一个线性函数\mathcal(S) = \sum_i W_i X_i,是无法正确刻画特征1的。当然,了解过深度学习的读者应该就能发现,这恰好是深度学习中的非线性层引入的动机。

后续讨论我们默认N=3,更大的N对应算法很容易在N=3的情况修改得到。下图是网络的结构图——

在输入节点Embeding (X_i, X_j, X_k),我们可以通过非线性函数将他们映射到一个非线性空间L中。

L_{ijk} = \sigma(W_a^{(2)} X_i^a + W_b^{(2)} X_j^b + W_c^{(2)} X_k^c + b^{(2)})

而我们进一步将L映射到一个概率空间S

S_{ijk} = \mathcal{S} (X_i^a, X_j^b, X_k^c) =  \sigma(W^{(3)} * L_{ijk} + b^{(3)})

上面两层共同构成了我们的非线性相似性函数\mathcal{S},最终的目标函数定义如下

\mathcal{L}_1 = -(R_{ijk} \log S_{ijk} + (1-R_{ijk}) \log (1-S_{ijk}))

上式中的R_{ijk}被定义为“节点i,j,k是否组成一个超边”的0\1值函数。

接下来,我们考虑如何生成二阶相似性。之前我们介绍了模型中的第二层和第三层,而模型的第一层就是用来保证二阶相似性的。从图中,我们可以发现,模型使用了一个AutoEncoder,那么任何AutoEncoder都需要一个可供编码的东西,我们这里使用AutoEncoder编码什么呢?作者设计了一个编码矩阵A_i.

H表示在图G(V,E)的关联矩阵,h(v,e)=1当且仅当v \in e,而D表示图的度数矩阵。令A = H H^T -D。在离散数学中,可以证明,A矩阵的第i行A_i刻画了节点i的邻居的信息。而AutoEncoder就可以如下构造——

X_i = \sigma(W^{(1)} * A_i + b_i)

\hat{A}_i = \sigma(\hat{W}^{(1)} * X_i + b_i)

对于AutoEncoder的损失函数,我们有一个小优化,即只计算A_i不等于0的项。

\mathcal{L}_2 = \sum_t ||sign(A_i^t) \cdot (A_i^t-\hat{A}_i) ||_F^2

最终模型的损失为

\mathcal{L} = \mathcal{L}_1 + \alpha \mathcal{L}_2

模型训练

使用SGD算法训练。

Experiment

Conclusion

 

原创文章地址:【Structural Deep Embedding for Hyper-Networks 阅读笔记】转载时请注明出处mhy12345.xyz

Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 实现与分析

由于篇幅太长,这篇文章的Introduction和Related Work在另一篇文章里。


PQT的简介

乘积量化树(Product Quantization Tree)是基于多层倒排表(Inverted Multi-Index)和分层PQ算法形成的。其核心思想将之前的一个码书(Codebook)修改为基于层次化的树形结构。树形结构可以加速实时的查询,以及离线的排序。相比于之前的多层倒排表,PQT拥有更多地簇(Bins)。最后PQT还巧妙地运用一些技巧在重排序中服用之前计算过的距离值。

右图阐述了一个PQT查询的例子。查询向量[x]_1[x]_2的各个部分一次经过4个Cluster的粗排序和5个Cluster的精排序。对于第一层而言,只有w个最佳的Cluster可以到下一层继续搜索,如图中阴影部分所示(w=2)。

PQT的结构

将样本集合中所有的向量x \in \mathcal{X}归类为簇B_l从而形成若干个互不相交的子集,\mathcal{X} = \bigcup_{k=1}^{K} B_k。接下来,我们将详述如何将一个向量映射到簇中,即如何构造映射m : \mathcal{X} \rightarrow \mathcal{I}_1 \times \mathcal{I}_2 \times \dots \times \mathcal{I}_P

索引树包含两层量化器,第一层是传统的P部分(P part)的PQ量化器,在这个量化器中,每一部分的码表含有k_1个码字。在第一层量化器之后,选出的簇进一步使用第二层k_2个码字的量化器量化。这种方法中,总共存在的簇有K = (k_1 \cdot k_2)^P个。

对于码书的训练,每一部分独立生成码书,首先量化器使用Lloyd Iteration中的Linde-Buzo-Gray算法生成,所有第一层量化器分出的簇进一步使用第二层量化。

对比在多层倒排表中,使用了两级的乘积量化,其中第二级用于排序,我们也用两级索引,至于为什么是两级,只是从经验上来看,两级能够最好得平衡簇的总个数。

PQT的询问操作

一个实际的询问操作包含四个步骤——

  • tree traversal
  • bin proposal
  • vector proposal
  • re-ranking

在tree-traversal步骤中,正如之前对PQT结构的叙述,每一个向量都能归类为一个level-2的簇中。通过剪枝的策略,tree-traversal步骤使用的向量比较次数实际上是相对较少的。在比较了所有k_1个level-1簇后,询问向量距离每一个簇的距离被排序,并且只有最近的w个簇被进一步计算。在提取出了最近的w个level-1簇,接下来这些level-1簇所对应的level-2簇的中心再和询问向量进行比较。在标准参数下,在四百万簇的数据集下,只需要80次向量比较。具体细节可参见论文。

在bin-proposal步骤中,从我们获取的“最好的”簇i=(i_{1,1},i_{2,1},\dots,i_{P,1})开始,我们仍然需要一系列临近的簇,以保证在后续的处理中,有足够多的向量可供选择。正如右图所示,我们需要找到一个顺序,合理组织“次好”的向量,使得遍历完所有较近向量的这组合。着这种便利,通常来说,可以看做是一个斜线从左下向右上方移动维护的下方区域。具体的实现方式,绿线是Dijkstra-based traverse,但是无法再GPU上面实现,而红色、绿色线则是可行的。对于每一个簇,我们都可以在离线阶段预处理出最近的簇。

使用Line Quantization进行重排序

通过上述的索引,每一个询问向量都被归类于最近的簇,并获得了一个量化损失(quantization loss)。在传统方法中,我们就需要依次对于簇所包含的所有向量进行比较,但是显然这样会有巨大的花销。而在我们的算法中,我们重用了一些信息以达到更优的效率。

离线预处理

在传统方法中,一个簇所包含的所有向量是不可分的,这就导致了我们必须花巨大的计算力去依次比较所有的向量。 文中提出的Line Quantization巧妙地解决了向量不可分的问题。即,虽然每一个向量【黑点】相对于level-2簇中心【红点】是不可区分。但是他却可以被投影到两个最近level-1簇中心的连线上【紫点】。巧妙的是,对于所有level-1中心,询问的x_1点与他们的距离都是已经算过的!

右图描述了如何计算对于任意询问向量y距离某一个数据库样本x的距离。其中,c_i,c_j为两个距离x很近的level-1簇中心。

 

(1)   \begin{align*} d(y,x) &= \sum_{p=1}^{P} d([y]_p, [x]_p)^2 \\ & \apporx \sum_{p=1}^{P} h_p(y,x)^2 \\ & \apporx \sum_{p=1}^{P} (b_p^2 + \lambda_p^2 \cdot c_p^2 + \lambda_p \cdot (a_p^2-b_p^2-c_p^2)) \end{align*}

通过这个式子,我们可以用我们之前计算过的,询问向量距离level-1簇中心的距离信息,为x找到一个更加精确的距离估计值。

在GPU上实现

这个模型非常适合在GPU上面实现,不过由于我并不太了解GPU的实现,顾就不在这里赘述,读者可以对照论文自行理解。

原创文章地址:【Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 实现与分析】转载时请注明出处mhy12345.xyz

The Design Philosophy of the DARPA Internet Protocols 论文阅读报告

本文介绍了Internet中最基本的协议——TCP/IP协议的设计思想。由David.D Clack所著,他作为整个TCP/IP协议设计的参与者,见证了协议从1973年最初的版本,逐渐被改进,到最终成型的一系列尝试。在文章中,作者总结了设计中的一系列目标,以及存在的问题。让我们得以窥见这一段艰辛的摸索之路。

各种协议的设计,其基本目标无非两个: 1) 能够尽可能的兼容协议发布之前已存在的硬件设施; 2)能够尽可能的有利于协议发布之后的因特网发展。这些基本目标不仅为我们理解TCP/IP的后续发展有帮助,也能够让我们知道,为什么在计算机科学领域,很多的实现都是建立在“协议”上的。

在基本目标之上,人们基于对于因特网的畅想,设计出了一系列有严格层次关系的次级目标,如稳定性,经济性,可解释性等。由于Internet协议的设计流程过于复杂,常常会遇到两种不同实现方式的权衡取舍,由于实现确立了稳定性、经济性这一类不同目标的重要性排序,故可以基于此进行取舍。这种目标导向的协议构建,一方面确实省去了非常多的试错的时间,另一方面,却会缺少一些长远的考虑(例如由于对性能的要求并没有卸载目标中,导致性能在早期完全没有被重视等等,又例如一对多的信息传递没有在早期协议中支持,导致在长时间无法实现)。

互联网协议的稳定性作为最重要的目标,毫无疑问来自于互联网历史上的军方背景。也在之后的普及中发现其局限性,报文协议(UDP)的诞生或多或少的解决了这个尴尬的境地。不过UDP能够成功诞生还是算非常幸运的了,通常来说协议的修改总是耗时耗力,有时还会和原来的协议冲突,诸如一对多的广播就一直没有能够成功的引入。总之,协议设计者的远见与用心真的是非常的重要。而TCP/IP协议的设计流程,从文中提到的寥寥几句可以推测出,确实不是设计者拍脑袋的结果,而是无数次试验,并用一篇篇论文推动而来的。反观现在良莠不齐的学术论文,我觉得在协议设计中的这种,基于某个具体目标驱动的研究,才是能让学术界向前推进的正确方法。

由于网络的协议的更改需要兼容之前的功能,而论文写作至今又过去了接近30年,TCP/IP协议在30年前存在的缺陷,随着互联网体量的增大,在现在解决更需要花费巨大的人力财力。IPV6协议的创立可能会解决少量表层问题,但是很多结构上的缺陷仍然无从修复。可能这是计算机网络领域的一大难题。期待在未来,能有技术上的爆炸性突破,其力量,能够足以颠覆计算机领域坚守了三十余年的TCP/IP协议。也许量子通信就是这样的潜力吧。

原创文章地址:【The Design Philosophy of the DARPA Internet Protocols 论文阅读报告】转载时请注明出处mhy12345.xyz

Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍

由于篇幅太长,这篇文章的讲述了文章的Introduction和Related Work部分。而文章的主体部分在Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 实现与分析 这篇文章里面。


摘要

这篇论文讲的是在高维空间的最近点搜索问题(ANN)的一个实现算法,该算法继承自 乘积量化(Product Quantization) 算法。在该算法中,提出了如下几点:

  • 将原来的乘积量化算法进行分层,使用树形结构减少向量的比较次数
  • 提出了一个重排序算法,该算法有更好的并行度

简介

最近点搜索问题(NN)就是在D维空间中,对于一个向量y,找寻样本集合\mathcal{X}中,最近点的问题,形式化表达——

(1)   \begin{equation*} N(y) =\mathop{\arg\min}_{x \in \mathcal{X}} d(y,x) \end{equation*}

在视觉识别的领域的很多课题中,该问题的维数D变得非常大,引入了一种称之为 “维数灾难” 的现象。形象的解释这个问题,对于一个体积a^128的128维高维立方体,一个体积0.1 \times a^128的立方体,边长也是0.1^{\frac{1}{128}} = 0.982\times a。从这个例子可以看到,由于高维立方体体积增长速度过于迅速,我们基本不可能通过遍历区域的方式进行搜索。例如,在128维空间中,即使我们只要访问10%的体积,这些体积分配到单维度上也超过了98%。

给予上述瓶颈,大多数应用中,我们都是用了临近点搜索的方式(ANN),搜索一个相对较近的邻居。对于该问题,人们已经研究出了很多基于CPU的实现,从KD树(KD-tree),到随机KD森林(Randomized KD forest),和KD-mean Trees。这一系列算法都试图将搜索空间缩减到一个包含询问点的尽量小的邻域。

另一个截然不同的实现方式是局部敏感哈希算法(Local Sensitive Hashing),这个方法将整个数据库的向量的一系列随机投影使用哈希表储存,在询问中,对于和询问向量落在了同一个哈希项中的样本向量进行额外的距离检查。

上述基于CPU的ANN算法在像GPU迁移的时候都会遇到或多或少的问题,而基于GPU的算法则很多都是纯粹暴力算法。而在这篇文章中提出的算法,不仅高效利用了GPU,甚至其CPU版本都和上述算法匹敌。

在效率评估上,由于在实际生产中,存在一个“离线预处理”阶段计算所有询问无关的数据,以及一个“在线计算”阶段,实时处理询问相关的计算。因此,最科学的方式应该是将两个阶段的用时分别测量。

向量量化(Vector Quantization)是一个简单的ANN算法,它将样本集\mathcal{X}中所有的向量进行聚类。对于某个询问向量,距离其最近的聚类中心所对应的样本集子集\mathcal{X}_k \subset \mathcal{X}是最有可能存在最近点的。然而倘若询问点恰好位于两个聚类的边界上,则算法就不那么容易找到最近点了。另一方面,一个聚类簇在V图上的相邻聚类簇的个数随着维数的增加指数级增长。

乘积量化(Product Quantization)算法是当下很多最前沿ANN算法的核心,一般来说,基于PQ的算法都有如下几步

  1. 通过一个高效但是低精度的算法,选出一系列候选点集。
  2. 在重排序过程(re-ranking step)中,使用近似距离将候选点集进一步排序。
  3. 排序后的前面K个候选点重新计算实际距离并取最近者。

在PQ类算法的基础上,我们平行提出了一个称之为Product Quantization Tree的算法(PQT),这个算法的贡献点有

  1. 二级乘积和树形结构,减少计算量
  2. 引入Dijkstra算法的松弛操作
  3. 一个O(P)复杂度的近似排序算法,其中P为询问向量的分段数

背景

向量量化与乘积量化

由于我们的算法是基于PQ算法的,因此下面将介绍PQ算法。

首先,乘积算法(Product Quantization)的鼻祖是向量量化(Vector Quantization)算法。已知最初的样本集合\mathcal{X} = \{x_1,x_2,x_3,\dots,x_n\},以及一个码表(codebook)\mathcal{C} = \{c_1,c_2,\dots,c_k\},我们可以定义映射c(x) = \arg \min _{c \in \mathcal{C}} d(x,c),将每个样本点映射到最近的码字。同时,对于每个码字也控制了一系列样本点,令这些点集为C_kC_k =\ {x \in \mathbb{R}^D | c(x) = c_k\},这个点集也成为簇(cluster)或盒子(bin)。直接使用码字代表样本点,虽然引入了一些距离上的不精确,但是在后续寻找相似向量中很有用。在上述算法中,关键点集合可以通过一个叫Lloyd Iteration的算法得到。

在PQ算法中,高维的向量空间可以等价于若干低维向量空间的乘积,假设D = P \cdot m,那么对于所有的样本向量都可以进行分解,x \in ([x]_1,[x]_2,\dots,[x]_p)^T, [x]_i \in \mathbb{R}^m. 对于x \in \mathbb{R}^D,我们可以将该高维空间中的码表定义为C = C_1 \times C_2 \times \dots \times C_P,这个集合里面实际上包含了k^P个D维码字,但是却只需要k \cdot P个m维码字。由于码字变得非常非常多,我们可以对于高维向量进行更加精细的匹配。最终,一个向量的编码(Canonical Projection)定义为其P个独立组成部分的码字组合而成——

    \[c_p : \mathcal{X} \rightarrow \mathcal{C}_p, x\mapsto c_p(x) := \mathop{\arg \min}_{c \in C_p}  d([x]_p,c)\]

    \[c(x) = (c_1(x),c_2(x), c_3(x), \dots, c_p(x))^T\]

从上式可以发现,对于P个部分的量化操作使用了不同的码书,这些码书和VQ一样,都可以使用Lloyd Iteration生成。

诚然,查询任意一个向量处于哪一个簇是非常简单的。但是任意向量所归属的簇在大部分情况下都是空的,这是因为数据分布的稀疏性。不过,在实际使用中,查询向量通常和样本有相同分布,在这个条件下,我们确实可以成功的依照簇找到最近的向量。即使如此,我们还是需要考虑最坏的情况。

一些研究者为了实现更加精确的乘积量化方式,找到了一些解决方式,比如对于所有询问x,统一使用一个线性变换R修饰。及每次查询Rx。不过这个方法在GPU上并不怎么方便。

右图的四部分就分别介绍了“向量量化(Vector Quantization)”和“乘积量化(Product Quantization)”对应的中心点分布图。下层的两幅图则尝试按照不同的“粒度”实现树状查询,在之后会详细讨论。

 

倒排文件系统

对于一个询问y \in \mathbb{R}^D,有的文章使用了含“非对称距离计算”的倒排系统实现。在这个实现中,首先一次VQ,在规模k的码书中提取一系列候选码字(原文中是在8192个向量中,提取0.05%,即64个候选)。不过,即使是64个候选码字也廊括了524288个样本向量。

在这个实现中,选择一组合理的码字消耗了k个D维向量距离运算,在计算了k次距离之后,其中最近的w个码字对应的样本集合的并集\mathcal{L}_c \in \mathcal{X}就是“极有可能包含答案的向量集合”。这一系列向量进一步在基于PQ算法的重排序(re-ranking)。按照中心向量c_wy的距离r_w = y-c_w,从小到大排序,在之前文章中,由于询问向量y事先知道,所以这个距离被放在了查找表(lookup-table)中。

询问向量y和其最近的候选向量可以在集合\mathcal{L}_c中使用相似的方式查找到。只不过这一次,候选集合\mathcal{L}_c小了很多,而码书包含了更多(k_2个词).通过新的码书对应的距离函数,重排序得到更加靠谱的候选集合\mathcal{L}_s,最终,在\mathcal{L}_s中,选择前几个进行最精确的距离计算。

上述步骤意味着共有k_1 + w \cdot k_2次距离计算,在论文默认的规模中,意味着24576次高维向量距离计算每询问。

一个层次化的实现会将总共的距离计算次数将至200,不过,在NVIDIA Titan X架构下,16k的向量距离计算比256次计算慢62倍,因此,在这个问题上,就近多少次距离计算是运行效率的瓶颈。

多索引倒排

相比于之前,在整个数据及上使用VQ,多层次倒排索算法使用了PQ算法,减少了询问向量与中心向量的距离计算次数,而增加了Cluster的总数。

对于y的每一部分,都给定了其到k个中心向量的距离。这些距离经过排序生成如下表格——

(2)   \begin{align*} [y]_1 \rightarrow \{i_{10}, i_{11}, i_{12}, \dots, i_{1k-1}\} \\ [y]_2 \rightarrow \{i_{20}, i_{21}, i_{22}, \dots, i_{2k-1}\} \\ \vdots \\ [y]_P \rightarrow \{i_{P0}, i_{P1}, i_{P}, \dots, i_{Pk-1}\} \\ \end{align*}

上面式子中i_{23}指的是询问向量第二部分的第三近的向量。在此基础上的NN搜索,使用启发式算法,从i=(i_{10},i_{20},\dots,i_{P0})开始。可以使用优先队列,一次访问最近的一个簇中的向量,直到足够多的向量被访问。

讨论

上述的基于VQ和基于PQ的查询算法都能达到很好的精准度。基于VQ的算法需要很大的内含D维向量的码书,即使基于PQ算法的码书会小一些,但是从总量上也非常大。另一方面,两个算法都需要与询问相关的离线初始化操作。这在实时的查询中是不可行的。

对于之前提到的诸多问题,在接下来一章中,我们将使用乘积量化树(Product Quantization Tree)来解决上述的问题,并提出不同的Cluster选择算法,和基于投影的重排序算法。最后,我们将讨论该算法如何在GPU上面运算。

参考文章

理解 product quantization 算法

K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比

原创文章地址:【Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍】转载时请注明出处mhy12345.xyz

Separating Style and Content for Generalized Style Transfer 阅读笔记

【由于笔者在尝试优化这个模型,因此在一些步骤中会加入自己的一些点评,以方括号指示,读者尽可无视他们】


在汉字风格迁移领域,有很多不同的尝试,学者在网络结构,损失计算等模块,都有不同的尝试。在之前的实现中,汉字的风格通常在训练过程中被记忆在了网络结构中,当需要生成一个新风格的字体时,网络需要在新的数据集下重新训练。而在本文中,汉字风格由给定的少数输入样本给定,由模型实时提取并输出。

文中的模型称之为EMD,在结构上包含风格编码器、内容编码器、混合器和解码器。训练数据集的每一项都是由R_S_i,R_C_j,I_{ij}组成,其中R_S_iR_C_j分别是风格(Style)和内容(Content)的指示集合,而I_{ij}是目标图像。换句话来说,模型通过同一汉字不同风格的一组图像刻画了内容,又用同一风格不同汉字的一组图像刻画了风格,再将两个模块的特征向量组合,形成字体和内容的融合。

模型的详细结构如下图——

实际上,这张图片已经描述了几乎所有的细节。图中提及了down-sampling 和 up-sampling,这两个过程实际上就是图像的“压缩”和“放大”,在文中使用了经典的卷积层和反卷积层

【反卷积层或许可以搞一些花样提高模型效果】

在Encoder模块,两个集合的所有输入数据,拼接在一起,每张图片作为一个Channel,传入后续的卷积层中。

【这里有一些小问题,不知道实现的时候有没有解决,由于输入的图片集合是无序的,而Channel本身是有序的,若将每一个图片都视为一个独特的Channel,则每一个不同位置的图片都会有不同的卷积层提取特征,这个情况本身就是不靠谱的。】

在Mixer模块,使用了BiLinear层。用数学语言来描述,设两个特征器提取出的向量分别是S_iC_j,那么Mixer层的输出应该是S_i W C_j^T,其中W是一个形状(dim(S_i),dim(C_j))的向量。

Decoder模块使用了若干反卷积层。具体细节图片已经说得很明白了。上述的多层卷积和反卷积层中间都间隔了BatchNorm和LeakyReLU。

还有一些实现上的细节,诸如从Content Encoder的第一层连了一条通路到Decoder的最后一层。及Content Encoder进过粗特征可直接被答案的生成所运用。

【这一步骤会让人比较怀疑这条通路中间的东西是不是真的学到了东西,模型本身很容易直接学到“和输入一模一样”的输出(因为这样的输出只经过两层),而不容易学到风格信息(风格信息的传输至少会经过十多层)。】

 

原创文章地址:【Separating Style and Content for Generalized Style Transfer 阅读笔记】转载时请注明出处mhy12345.xyz

Recurrent Attention Network on Memory for Aspect Sentiment Analysis 阅读笔记

原文链接:Recurrent Attention Network on Memory for Aspect Sentiment Analysis

Abstract

文章提出了一个基于神经网络的,提取“关键词的情感倾向”的模型,拥有如下特点:

  • 创造了一种称之为“加权记忆(weighted-memory)”的机制
  • 使用GRU实现注意力(attention)

Introduction

提出问题

“I bought a mobile phone, its camera is wonderful but the battery life is short”

这一部分,以一个句子的情感分析为例进行分析。在分析中,我们需要对于每一个关键词(target),分析其情感语义,比如camera对应wonderful。选取最近情感词是通常手段,但是显然这种手段会在某些精心构造的句子中失效,比如下面这句话蕴含了中性情感而非消极情感。

“Its camera is not wonderful enough.”

针对上述问题,TD-LSTM是一个解决方案,这种解决方案也有一个缺点,就是特征的传递是逐词的,这在长句子中,当目标(target)与特征词(feature word)相距很远时,又会出现问题。进一步,注意力机制被引入,已表征特征重要性。然而,当实际的注意力点较多时,这种机制的表现也不太好。

“Except Patrick, all other actors don’t play well”

上述的问题便是这片文章准备解决的东西。

引入模型

模型层次结构依次为——

  • 一个双向LSTM生成一系列“记忆片(memory slice)”
  • 所有的内存片按照距离目标词(target)的相对距离加权,使得句子里不同的目标词拥有不同的特征向量
  • 在生成的加权记忆片中,使用注意力机制合并,这里使用的是循环层GRU

在本文中,就如何组合不同的注意力这个问题,提出了新的解决方案。从某一个方面来看,比较像一个普通人的认知——最初看到句子的最开头,然后在继续阅读的过程中不停“注意到”知识,并在最后将注意力集中的几个语言拼接。

对于Introduction中的最后一句话,我们通常会先看到“Except”,接着被“don’t play well”吸引,最终对于“Patrick”生成一种积极的情感。在本文之前,多数文章提出的结构都无法解决多注意力的问题。而我们提出结构中的GRU曾可以很好的解决。

Related Work

对于特定实体的感情分类问题,有很多传统做法基于规则、统计概率,这些做法不是有繁琐的模型构造,就是需要依赖很多额外的语法信息。

这时神经网络就可以发挥作用了~神经网络本身曾被用在语法分析,句子整体情感分析,诸如有名的递归神经网络(Recursive NN)。然而,递归神经网络在语法分析低效的非标准文本(比如推特评论等短文本)中效果不好。

对于指定目标的情感分析,曾经有人提到过TD_LSTM算法,这个算法将需要的目标词放在中间,从两边分别使用LSTM传递信息。这种做法在长句子中效果会大幅减弱,因为很远的情感词必须经过非常多层才能到达终点。

最后,神经图灵机在2014年被提出,其中定义的注意力机制被证明在很多地方适用。其创新之处是引入了外部储存,大大提高了神经网络的能力!从某种方面来说,本文就是在这个模型基础上修改而成的。

Our Model

右图是文章提出模型的结构。

在输入层,所有输入的文本都通过经典的wordtovec算法,将每个词压缩为一个d维向量。

接下来,使用了双向LSTM神经网络(BLSTM)提取每一个词的“记忆信息” u_t,实际上,这种实现方式就是普通的bi-directional-lstm。

接下来,对于不同的位置,有一个二次加权,成为“加权记忆”(weighted memory),加权的意义不太清楚,可能使得较远的信息更容易传播吧。具体来说,文中的加权含义将以中心词的两端t_{max}距离的词,按照距离中心的距离线性加权拼接在一起。

最后,文章使用GRU层将加权记忆再“捣鼓”一番,这里的“捣鼓”是指循环N词,每次通过上一次“捣鼓”的记忆e_{t-1},以及整个“加权记忆”得到第t个“注意力”的加权矩阵,进而通过GRU的形式更新e_t,关于选择GRU模型的原因,文章解释说因为GRU的参数较少。

Experiments

表现优于传统模型

Conclusions and Future Work

在这一部分,作者谈到了选择固定个注意力(Attention)显得有些冗余,在未来的工作中会考虑自适应注意力个数能够得到更好的结果。

点评

在Introduction模块,文章点出了在NLP领域,各种算法面临的共同问题,这种归纳确实很有意思。关于这类模型共同的要点罗列如下——

  • 如何将单词编码,至少本文还是用的经典算法
  • 如何解决远距离传输问题,本文使用weighted-memory机制
  • 如何在不增加太多参数的条件下,增加模型的“深度”,对应了本文中多注意力机制
  • 如何尽量在模型的选择上减少训练参数,对应本文的GRU选取

这篇文章中Related Work里面提到的神经图灵机感觉会很有意思,之后可以找一找相关的论文阅读一下,虽然在NLP方面感觉有些束手束脚,但是在其他领域可能会有很大的作为。

对于本文提到的模型,却是可以看出是仿照人类对于句子阅读的认知,每一个步骤都可以通过人类阅读的认知来解释,不过这种仿照是否能够带来很好的效果就不太好说了。至少文章写的是效果很好,那就姑且相信吧。

由于读的比较粗,关于每一层输出的具体维数还是有点晕,可能也有作者没有表述清楚的锅。

原创文章地址:【Recurrent Attention Network on Memory for Aspect Sentiment Analysis 阅读笔记】转载时请注明出处mhy12345.xyz

A Hierarchical Neural Autoencoder for Paragraphs and Documents

论文链接:A Hierarchical Neural Autoencoder for Paragraphs and Documents

这篇文章的核心目标是:输入一个文段,通过神经网络,将该文段压缩为一个低维特征向量,尽可能的记住尽量多的东西,再通过神经网络,将低维特征向量映射回原文段。整个模型就是一个自编码器(Autoencoder)。

其中,模型输入的文段是一个包含若干句话的文段,其中每句话又包含若干单词,单词可以用词向量算法转化为向量表示。模型运用了LSTM模型以及Autoencoder模型的思想,在这里就不赘述了。

paper提出的模型有三个,都是从LSTM出发改良而成的,分别是:基础LSTM,带有层次信息的LSTM,带有层次信息和注意力机制的LSTM。这三种模型的流程图如下:

第一个模型就是将一个LSTM的模型的尾部接到第二个LSTM模型的头部完成的。显然,由于LSTM本身对于信息的承载量优先,而一篇文章通常由上千个单词组成,完全无法指望LSTM能够提取出太多有用的信息。

第二个模型,增添了层次结构,其设计初衷就是为了解决第一个模型的不足之处:单词本身携带的信息太少了,要让模型从一篇文章中定位到一个关键词太过复杂。解决方式是在“文段”和“单词”之间增添一个过渡桥梁,即“句子”。通过一个LSTM从句子中提取出一个特征向量,对于每个句子提出的特征向量,我们再通过另一层LSTM提取出文段的特征向量。

第三个模型就比较玄学了。可以感性理解其优于第二个模型的地方。即,由于LSTM每次只提取最后一个Cell的输出,等同于默认了最后一个Cell的输入,即最后一个词是最重要的,这与实际不符。因此对于压缩器LSTM的所有节点,同时增加一个判别器D,可以通过该节点本身的输出与最终编码器总结出来的特征向量,求出一个类似于相关程度的量v。实际上解码器所获得的输入,应该是每个Cell的v值通过类softmax的函数进行加权求和得到的。用这样的特征向量替代之前的特征向量,等于说将重要的东西变得更重要了。

总之,这篇文章里面的内容其实挺基础的,LSTM本身是15年发明出来的东西,在现在已经有3年的时间了,很多特性已经被挖掘出来,Autoencoder思想则更早。也就是说时效性可能已经过了。

不过算法本身非常的general,可以套用到NLP中的很多地方,我们需要做的还有实现词向量算法。

原创文章地址:【A Hierarchical Neural Autoencoder for Paragraphs and Documents】转载时请注明出处mhy12345.xyz