精华内容
下载资源
问答
  • TransE算法

    千次阅读 2018-04-11 18:35:59
    TransE算法中存在一个设定,它将关系看作是实体间的平移向量,也就是说对于一个三元组(h,r,t)对应的向量lh,lr,lt,希望 lh+lr =lt 这源于Mikolov等人在2013年提出的word2vec词表示学习模型,他们发现词向量...

    TransE算法中存在一个设定,它将关系看作是实体间的平移向量,也就是说对于一个三元组(h,r,t)对应的向量lh,lr,lt,希望

    lh+lr =lt

    这源于Mikolov等人在2013年提出的word2vec词表示学习模型,他们发现词向量空间存在着平移不变现象,如
    C(king)C(queen)C(man)C(woman)C(king)−C(queen)≈C(man)−C(woman)

    其中,C(w)就是word2vec学习到的词向量表示。我们可以看到,词向量可以获取词之间的某种隐含关系。

    因此TransE中,对于给定一个由三元组 (h,r,t) 组成的训练集S,其中h,t属于实体集合E,r属于关系集合L,模型学习实体和关系的向量嵌入,通过不断的调整h,r,t,使得尽量接近上面提到的平移设定。每个元组有一个energy等于相似性度量 d(h+l,t),d代表曼哈顿距离或者欧氏距离。也就是说,当一个三元组的energy越小时,它越符合我们的期望,即lh+lr=lt。我们的目标就是降低正确三元组的energy。在训练集中有如下目标函数:

    1 (1)

    其中[x]+表示x大于0时取原数值,小于0时取0,γγ 是一个边际参数,它是采用支持向量机(SVM)的思想,最大化正确三元组与错误三元组的距离,因此还需要构造错误三元组:
    (2)

    如公式(2)所示,通过随机选择实体替换头实体或者尾实体来构成错误的训练三元组。相比错误的元组,损失函数(1)更有利于降低正确元组的energy增加错误元组的energy。

    优化方法选用随机梯度下降法(minibatch模型),对h,t,t有一些附加约束,实体嵌入的欧式距离值为1(对关系嵌入没有约束)。此约束可以有效地收敛。

    所有实体按照算法提出的随机方式进行初始化。算法的每次迭代,都要先归一化实体嵌入向量。然后,从训练集中选取一部分元组为样例充当minibatch的训练元组。对每个这样的元组,取样一个错误元组。然后通过一定的学习率的梯度步骤更新参数。
    算法的流程如下:
    这里写图片描述

    参考文献
    Bordes A, Usunier N, Garcia-Duran A, et al. Translating Embeddings for Modeling Multi-relational Data[C]// International Conference on Neural Information Processing Systems. Curran Associates Inc. 2013:2787-2795.

    展开全文
  • TransE算法详解

    万次阅读 多人点赞 2018-12-25 20:31:31
    TransE 算法详解 @(机器学习)[知识图谱|知识表示|TransE] 文章目录TransE 算法详解算法背景知识图谱是什么知识表示是什么基本思想算法描述梯度参考文献 算法背景 知识图谱是什么 一条知识图谱可以表示为一个三元组...

    TransE 算法详解


    算法背景

    知识图谱是什么

    一条知识图谱可以表示为一个三元组(sub,rel,obj)。举个例子:小明的爸爸是大明,表示成三元组是(小明,爸爸,大明)。前者是主体,中间是关系,后者是客体。主体和客体统称为实体(entity)。关系有一个属性,不可逆,也就是说主体和客体不能颠倒过来。
    知识图谱的集合,链接起来成为一个图(graph),每个节点是一个一个实体,每条边是一个关系,或者说是一个事实(fact)。也就是有向图,主体指向客体。
    三元组的一个例子是

    (姚明,出生于,上海)

    (姚明,职业, 篮球运动员)

    (姚明,性别,男)

    为了简化起见,我们使用(h,r,t)来表示三元组。其中:

    • h表示头实体
    • r表示关系
    • t表示尾实体

    知识表示是什么

    知识表示 实际上是让知识图谱的实体和关系向量化
    具体的说,我们的目标是将知识库中所有的实体、关系表示成一个低纬度的向量。即(h,r,t)(h,r,t)(h,r,t) \rightarrow (\vec h,\vec r,\vec t)
    这样的话,姚明就不是一个符号了,而是一个低维度的稠密的向量,例如:

    [0.01, 0.04, 0.8, 0.32, 0.09, 0.18]

    上面的向量取了6维,实际情况中的维度一般会比这个大, 大概在50~200左右。
    在知识表示的大概念中,这种向量一般有一个专门的名称:embedding。

    基本思想

    算法描述

    TransE算法认为,一个正确的三元组的embedding(h,r,t)会满足h+r=t\vec h + \vec r = \vec t
    Alt text

    也就是说,头实体embedding加上关系embedding会等于尾实体embedding。同理,如果是一个错误的三元组,那么它们的embedding之间就不满足这种关系。

    于是我们认为定义一个距离d(x,y)d(\vec x , \vec y)来表示两个向量之间的距离,一般情况下,我们会取L1,或者L2 normal 。那么我们需要的是对一个正确的三元组(h,r,t)(h, r, t)来说,其距离d(h+r,t)d(\vec h + \vec r , \vec t)越小越好,相反对于一个错误的三元组(h,r,t)(h', r, t')来说距离d(h+r,t)d(\vec {h'} + \vec r , \vec {t'})越大越好,因此给出目标函数:

    min(h,r,t)S(h,r,t)S[γ+d(h+r,t)d(h+r,t)]+ \min {\sum _ {(h,r,t) \in S} \sum _{(h', r, t') \in S'} [\gamma + d(h + r, t) - d(h' + r , t')]_+}

    其中

    • Δ\Delta 表示正确的三元组集合
    • Δ\Delta ' 表示错误的三元组集合
    • γ\gamma 表示正负样本之间的间距, 是一个常数
    • [x]+[x]_+ 表示max(0,x)\max(0,x)

    通常为了方便训练并避免过拟合,会加上约束条件
    h1,r1,t1, ||h|| \leq 1, ||r|| \leq 1, ||t|| \leq 1,

    论文中的算法描述

    blob:https://maxiang.io/b610c1d3-7d27-4ec6-b0e5-6e3e56adeba6

    梯度

    以L2 normal 为例,梯度的计算相对比较简单,目标函数变为
    loss=(h,r,t)S(h,r,t)S[γ+(h+rt)2(h+rt)2]+loss = {\sum _ {(h,r,t) \in S} \sum _{(h', r, t') \in S'} [\gamma + (h + r - t)^2 - (h' + r - t')^2]_+}
    举例来说,对某一个正确关系组中的头元素的参数hih_i来说losshi=(hi,r,t)S(h,r,t)S[γ+(hi+rt)2(h+rt)2]+hi\frac{\partial loss}{\partial h_i} = \sum_{(h_i,r,t)\in S} \sum _{(h', r, t') \in S'}\frac{\partial [\gamma + (h_i + r - t)^2 - (h' + r - t')^2]_+}{\partial h_i}
    [γ+(hi+rt)2(h+rt)2]+hi={2(hi+rt)γ+(hi+rt)2(h+rt)2>00γ+(hi+rt)2(h+rt)2<0\frac{\partial [\gamma + (h_i + r - t)^2 - (h' + r - t')^2]_+}{\partial h_i}= \begin{cases} 2(h_i + r - t) & \gamma + (h_i + r - t)^2 - (h' + r - t')^2 > 0\\ 0 & \gamma + (h_i + r - t)^2 - (h' + r - t')^2 < 0 \end{cases}

    其他参数的偏导求解方式与hih_i的求导方式差异不大,这里不再赘述。

    参考文献

    https://xiangrongzeng.github.io/knowledge graph/transE.html
    http://www.voidcn.com/article/p-wpxtiwou-cz.html
    Bordes A, Usunier N, Garcia-Duran A, et al. Translating embeddings for modeling multi-relational data[C]//Advances in neural information processing systems. 2013: 2787-2795.

    展开全文
  • TransE算法解析

    2020-12-04 21:17:54
    transE算法是一个非常经典的知识表示学习,用分布式表示(distributed representation)来描述知识库中的三元组。 原理 transE算法利用了word2vec的平移不变性,TransE的直观含义,就是TransE基于实体和关系的分布式...

    transE(Translating Embedding)详解+简单python实现

    概念

    transE算法是一个非常经典的知识表示学习,用分布式表示(distributed representation)来描述知识库中的三元组。

    原理

    transE算法利用了word2vec的平移不变性,TransE的直观含义,就是TransE基于实体和关系的分布式向量表示,将每个三元组实例(head,relation,tail)中的关系relation看做从实体head到实体tail的翻译(其实就是向量相加),通过不断调整h、r和t(head、relation和tail的向量),使(h + r) 尽可能与 t 相等,即,实体向量 + 关系向量 = 实体向量 (h+l = t)

    损失函数

    img

    1️⃣ ( h ′ , l , t ′ )称为corrupted triplet,通过随机替换头或尾实体得到的

    2️⃣ 正样本 - 即原有样本,公式中的d(h+l, t)

    3️⃣ 负样本 - 随机替换h或者l, 不同时替换,公式中的d(h’+l, t’)

    4️⃣ γ>0为 margin(一个边际参数),表示正负样本之间的间距

    5️⃣ transE针对给定三元组进行二分类任务

    ​ 其中的负例是通过替换自行构造的,目标是使得最相近的正负例样本距离最大化。

    6️⃣ 距离度量方式

    ​ L1和L2范数

    7️⃣ 关系向量 (l)需要归一化,避免训练时带来实体向量的尺度变化

    8️⃣ 让正样本的距离最小,也就是m i n ( d i s t a n c e ( h + r , t ) ),让负样本的相反数最小也就是min(-distance(h’+r’,t’)),对于每一个正样本和负样本求和,再增加一个常数的间距margin,就是整体距离的最小值。也就是我们的目标函数。

    9️⃣ 如何产生负样本
    通过随机替换头实体的方式来实现一个错误的三元组,或者采用随机替换一个错误的尾实体的方式来形成一个错误的三 元组。

    在这里插入图片描述

    同时,为了避免出现生成的负例其实存在于知识库中的情况,我们在替换形成的三元组也存在于知识图谱中,我们需要在替换之后进行过滤

    训练方式采用SGD训练法
    SGD的收敛没有GD好,但是,这反而是优点,因为在机器学习领域,过于best的结果反而是害处,因为用于过拟合(overfitting)。也就是,尽管叫做D(下降),但整个过程我们难保一直D下去。只能保证在forever可以做到D。

    通常为了方便训练并避免过拟合,会加上约束条件
    ∣ ∣ h ∣ ∣ ≤ 1 , ∣ ∣ r ∣ ∣ ≤ 1 , ∣ ∣ t ∣ ∣ ≤ 1 ,

    具体的优化过程

    1️⃣ 所有实体和关系的嵌入首先按照随机过程进行初始化;
    2️⃣ 在算法的每次主要迭代中,对实体的嵌入向量进行归一化;
    3️⃣ 从训练集中采样一个小的三元组集合,作为小批的训练三元组;
    4️⃣ 对于每一个这样的三元组,我们取样一个损坏的三元组;
    5️⃣ 然后以恒定的学习速率梯度更新参数。

    下图是论文里的算法描述:
    在这里插入图片描述

    代码从网上下载即可。
    运行的部分结果:
    在这里插入图片描述

    论文:Translating Embeddings for Modeling Multi-relational Data

    展开全文
  • TransE算法介绍

    2021-05-12 22:55:36
    Translating Embeddings for Modeling Multi-relational Data 一个简单的python版本的复现: 复现代码 ...同时TransE算法也是后续改进版的TransD,TransH系列算法的基础。 在知识图谱中,一条内容可以.

    Translating Embeddings for Modeling Multi-relational Data

    一个简单的python版本的复现:  复现代码

    TransE 算法是一种用于表示图结构中节点及关系的嵌入表示的算法,可以广泛应用于后续各类基于图谱的任务,如基于知识图谱的推荐算法CFKG利用transE对图谱中的entity及relation进行embedding用于后续的推荐任务。同时TransE算法也是后续改进版的TransD,TransH系列算法的基础。

    在知识图谱中,一条内容可以表示为一个不可逆的三元组(sub,rel,obj),其中sub和obj用节点表示,均为entity,rel利用边进行表示,为relation(例如(Beijing, is capital of, China),在此三元组中Beijing和China均为entity用图谱中结点表示, is capital of是一种relation,用图谱中的边表示)。

    (题外话:嵌入的目的是将以上的entity和relation利用向量进行表示。当然给图中每个结点一个编号1->n来表示,给每个边一个编号(n+1) -> m来表示 ,这样m个编号也可以唯一表示图中所有内容,这也是一种embedding,但是存在的问题是这样的方式很难携带更多的信息来表示这些结点和边之间的关系,例如上例中的Beijing和China应该有很近的关系,但在这种顺序编号表示方法中他们可能会差的很大。这对后续利用一些基于距离的模型而言会造成很多困扰。因此需要更有效的方法来对图谱中的内容进行嵌入表示。)

    在TransE算法中,其用相同长度的向量来表示每一个结点和关系,因此entity和relation之间可以进行各种向量运算。

    该算法为实现以上目的,核心的优化目标h + l \approx t,即对于(sub + rel) 得到的向量尽可能等于obj向量

    该算法比较简单,具体步骤如上所示:

    其中1-5行的初始化,主要参考了Xavier Initialization,因此选择了

    uniform(-\frac{6}{\sqrt{k}},\frac{6}{\sqrt{k}})

    这样一个分布进行初始化,关于该初始化分布的取值可以参考Xavier Initialization的论文有相关证明

     

    第6行是随机采样一个minibatch用于改embedding的训练。

     

    第7-11行是对该采样后的minibatch S_batch构造"负样本"(corrupted triplet),构造过程是对于一个给定的triplet(h, l, t),保持其h和l或l和t不变,将原triplet中的t或h替换为随机选择的一个entity t‘或h’,即构造后的corrupted triplet为(h', l, t) 或(h, l, t') ,注意,不要同时改变h和t,针对每个triplet仅生成一个corrupted triplet(h', l, t) 或(h, l, t')

     

    第12行是优化训练过程,论文使用了SGD,使优化目标函数(或称loss)尽可能的小,对于优化函数

    [\gamma + d(\emph{\textbf{h}} + \emph{\textbf{l}}, \emph{\textbf{t}} )-d(\emph{\textbf{h'}}+ \emph{\textbf{l}}, \emph{\textbf{h'}} )]_{+}

    第一个距离d(h+l,t)是正样本之间的距离,应当尽可能的小,第二个d(h'+l, t')是假样本之间的距离,因此应该尽可能的大,而\gamma是一个超参数,为了让整体优化函数可以大于零

    优化函数中的d可以采用L1距离或L2距离,\gamma是一个超参数,为了让整体优化函数可以大于零,对于不同的距离,其求导如下:

     

    L1 距离:

    \frac{\partial (\gamma +|h + l - t| -|h' + l - t'|)}{\partial h} = \left\{ \begin{array}{rcl} 1 & & h + l -t > 0\\ -1 & & h + l - t < 0\\ \end{array} \right.

    \frac{\partial (\gamma +|h + l - t| -|h' + l - t'|)}{\partial t} = \left\{ \begin{array}{rcl} -1 & & h + l -t > 0\\ 1 & & h + l - t < 0\\ \end{array} \right.

    \frac{\partial (\gamma +|h + l - t| -|h' + l - t'|)}{\partial l} = \left\{ \begin{array}{rcl} 2 & & h + l -t > 0, h' + l - t' < 0\\ 0 & & h + l - t < 0, h' + l - t' <0\\ 0 & & h + l - t > 0, h' + l - t' >0 \\ -2 & & h + l - t < 0, h'+l-t'>0\\ \end{array} \right.

    \frac{\partial (\gamma +|h + l - t| -|h' + l - t'|)}{\partial h'} = \left\{ \begin{array}{rcl} 1 & & h' + l -t' > 0\\ -1 & & h' + l - t' < 0\\ \end{array} \right.

    \frac{\partial (\gamma +|h + l - t| -|h' + l - t'|)}{\partial t'} = \left\{ \begin{array}{rcl} -1 & & h' + l -t' > 0\\ 1 & & h' + l - t' < 0\\ \end{array} \right.

     

    L2距离:

    \frac{\partial (\gamma +(h + l - t)^2 -(h' + l - t')^2)}{\partial h} = -2 (t-h-l)

    ......

    \frac{\partial (\gamma +(h + l - t)^2 -(h' + l - t')^2)}{\partial l} = -2 (t-h-l) + 2(t' - h' - l)

    根据以上求导结果利用随机梯度下降的方法可以对优化目标函数[\gamma + d(\emph{\textbf{h}} + \emph{\textbf{l}}, \emph{\textbf{t}} )-d(\emph{\textbf{h'}}+ \emph{\textbf{l}}, \emph{\textbf{h'}} )]_{+}进行优化。

     

     

    展开全文
  • 知识图谱 - TransE算法

    2020-08-11 11:10:54
    这里写自定义目录标题论文TransE算法概览核心思想Tips参考代码问题 论文 Translating Embeddings for Modeling Multi-relational Data TransE 算法概览 核心思想 实体向量 + 关系向量 = 实体向量 (h+l = t) Tips ...
  • TransE算法(Translating Embedding)

    万次阅读 多人点赞 2016-03-27 14:42:17
    介绍TransE算法(Translating Embedding)
  • transE by Python Train transE.py and test test.py. If shut down during training, also can run reTrans.py to continue. Finally, also can use pca.py to dimensionality reduction, and plot in .png THANKS...
  • TransE算法(Translating Embedding) 一、引言 &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;网络上已经存在了大量知识库(KBs),比如OpenCyc,WordNet,Freebase,...
  • 本代码来源于github项目地址,项目实现了TransE算法。下面结合项目代码,对TransE算法原理及实现进行详细说明。 2基本思想 TransE是一篇Bordes等人2013年发表在NIPS上的文章提出的算法。它的提出,是为了解决多...
  • TransE算法的整理

    2019-12-10 21:24:52
    TransE 1 TransE的作用 TransE 作用就是把三元组翻译成embedding词向量的方法 三元组,也就是(头实体,关系,尾实体)的形式,头实体和尾实体统称为实体。为了简化起见,我们用(h,r,t)来表示三元组。其中 h表示头...
  • TranSE算法实现及测试

    2019-04-26 09:20:55
    这是我自己的代码,主要用来存储,若能帮到其他人,我也很愿意。
  • TransE算法原理与案例

    千次阅读 热门讨论 2019-09-04 17:42:47
    文章目录TransE知识图谱基础知识表示算法描述代码分析数据 TransE 知识图谱基础 三元组(h,r,t) 知识表示 即将实体和关系向量化,embedding 算法描述 思想:一个正确的三元组的embedding会满足:h+r=t 定义距离d...
  • TransE 算法学习笔记

    2019-03-12 15:15:00
    http://yaoleo.github.io/2017/10/27/TransE%E7%AE%97%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3/ tranE是在模型中嵌入知识图谱等三元组类的一个方法,就像是句子利用词典嵌入一样。 转载于:...
  • TransE算法代码学习

    2020-03-28 22:30:29
    sample from numpy import * from copy import deepcopy class TransE: def __init__(self, entityList, relationList, tripleList, margin = 1, learingRate = 0.00001, dim = 10, L1 = True): self.margin = ...
  • 前言 原理 详细算法流程 前言 TransE算法是知识图谱补全的经典方法。 目前网络上存在大量知识库(KBs):如OpenCyc、WordNet、Freebase、Dbpedia等等,它们因不同目的建成,因此很难用到其他系统上。为发挥知识库的...
  • TransE的直观含义,就是TransE基于实体和关系的分布式向量表示,将每个三元组实例(head,relation,tail)中的关系relation看做从实体head到实体tail的翻译 1.初始化向量 def initialize(self): ''' 初始化向量,...
  • 原文地址:https://blog.csdn.net/elaine_bao/article/details/52012537

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 121
精华内容 48
关键字:

transe算法