图的表达2

十七、PTE

  1. 传统的词袋模型bag-of-word:BOW 忽略了不同单词之间的语义相关性,因此存在诸如数据稀疏性sparsity 、一词多义polysemy、同义词synonymy 之类的问题。单词的分布式 representation 通过在低维空间中嵌入单词来有效缓解该问题。

    单词的embedding 有两种方式:

    • 基于无监督学习的文本 embedding 通用性更强,可应用于各种类型的任务中。典型的无监督文本 embedding 方法包括 SkipGramParagraph Vector 等。
    • 基于监督学习的文本 embedding 效果更好,因为它可以充分利用task-specific 的标记信息。典型的监督学习方法有 CNN 神经网络。

    无监督文本 embedding 方法具有很多优点:

    • 首先,深度神经网络,尤其是 CNN,在训练中需要大量的计算。
    • 其次,CNN 网络通常需要大量的标记数据,而这在很多任务中是不现实的。
    • 最后,CNN 的训练需要对很多超参数进行调优,这对专家而言非常耗时、对非专家而言甚至不可行。

    但是和监督学习相比,无监督文本 embedding 方法在 task-specific 上的预测效果较差。原因是这些文本 embedding 在学习文本embedding 过程中没有利用任务中的任何标记信息。

  2. 论文 《PTE:Predictive Text Embedding through Large-scale Heterogeneous Text Networks》 提出了 Predictive Text Embedding:PTE 方法,它同时具有无监督文本 embedding 计算量小、标记数据需求低、无需复杂调参的优点,同时也利用了task-specific 标记信息。

    PTE 是一种半监督学习方法,它可以从有限的标记数据和大量的未标记数据中共同学习单词的有效低维 representation

  3. PTE 首先通过 word-wordword-docword-label 不同level 级别的共现构建一个大规模的异质文本网络 Heterogeneous Text Network ,然后将该异质网络嵌入到低维向量空间。PTE 通过在低维向量空间中保持顶点之间的二阶邻近度来学习顶点的 embedding

    这种低维 embedding 不仅保留了单词和文档之间的语义关系,还对task-specific 具有很好的预测能力。

    一旦学到单词的 embedding,我们可以将句子/文档中单词 embedding 的均值作为句子/文档的 embedding

    我们在真实语料库上进行广泛实验,结果表明:

    • 在各种文本分类任务中,PTE 的文本 embedding 都远远优于最新的无监督 embedding 方法
    • 在和 CNN 的对比中,PTE 在长文本上效果更好、在短文本上效果和 CNN 相差无几。但是 PTE 计算效率更高、可以有效应用大规模未标记数据,并且对模型的超参数敏感性较低。
  4. 监督学习方法和无监督学习方法的主要区别在于如何在学习阶段利用标记信息和未标记信息。在 representation learning 阶段:

    • 无监督学习不包含任何标记信息,仅在学到数据的representation 之后,才使用标记信息来训练下游的分类器。

    • 监督学习直接在学习过程中使用标记信息。

      另外,监督学习也可以间接地使用未标记数据:通过无监督方法来预训练单词的 embedding

    和这两种方式相比,PTE 通过半监督方法来学习文本 embedding :在学习阶段直接利用少量的标记数据和大量的未标记数据。

  5. DeepWalkLINE 均为无监督学习方法,它们只能处理同质网络。PTE 扩展了 LINE 方法从而能够处理异质网络,并且能够融合监督信息。

17.1 模型

  1. PTE 的基本思想是:在学习文本 embedding 时同时考虑标记数据和未标记数据。为了达到该目的,我们采用统一的表达形式来对这两种类型的数据进行编码。

    为此,我们提出了三种不同类型的网络,它们分别捕获了不同级别 level 的单词共现信息 :

    • word-word 共现网络: 网络 ,其中 为词表集合, 为单词之间的边的集合。定义单词 之间的权重 为:给定窗口大小的上下文窗口中,单词 之间的共现次数。

      捕获了局部上下文中单词的共现信息,即word 级别的信息。

    • word-doc 共现网络:网络 ,其中 为文档集合, 为单词和文档之间的链接。定义单词文档 之间的权重 为:单词 出现在文档 中的次数。

      是一个二部图,它捕获了文档中单词的共现的信息,即 doc 级别的信息。

    • word-label 共现网络:网络 ,其中 为标签集合, 为单词和标签之间的链接。定义单词标签 之间的权重 为:单词 出现在类别为 的所有文档中的总次数。

      也是一个二部图,它捕获了相同标签中单词的共现信息,即 label 级别的信息。

    定义异质文本网络 Heterogeneous Text Network 的组合,它们捕获了不同级别的单词共现,并且同时包含了标记信息和未标记信息。

  2. 异质文本网络也可以泛化为:集成不同level 信息的网络,如word-word 网络、 word-sentence 网络、word-paragraph 网络、word-doc 网络、doc-label 网络、word-label 网络等。但是论文中我们仅以三种典型的网络为例。并且,我们重点关注word 网络,以便将 word 嵌入到低维空间中。然后我们可以通过聚合wordembedding 来计算其它文本单元(如 sentence,paragraph,doc )的表示。

  3. 给定大量为标记数据和部分已标记数据的文本数据, Predictive Text Embedding:PTE 问题的目标是:通过将数据集合构成的异质文本网络嵌入到低维向量空间中,从而学习单词的低维表示。

    由于异质文本网络由三个二部图组成,因此我们首先介绍单个二部图的 embedding 方法。我们复用 LINE 模型来学习二部图的 embedding ,基本思想是:假设具有相似领居的顶点彼此相似,因此它们在低维空间中应该 embed 在一起。

    给定一个二部图 ,其中 是两组不同顶点类型、且不相交的顶点集合, 为二部图的边。

    令顶点 embedding ,定义给定 的条件下生成顶点 的概率为:

    对于每个顶点 ,我们定义了一个条件概率分布 ,这个条件概率分布的经验分布函数为:

    其中 为顶点 的度。

    为了在低维空间中保留二阶邻近度,我们最小化目标函数:

    其中 为两个分布之间的距离函数,通常选择为 KL 散度; 为顶点 在网络中的重要性,通常选择为顶点 degree

    如果忽略常数项,则我们得到目标函数:

    我们可以采用带边采样edge sampling 和负采样 nagative sampling 的随机梯度下降法来求解该最优化问题。在梯度下降的每一步:

    • 首先以正比于权重 的概率随机采样一条二元边 binary edge ,即 edge sampling
    • 然后通过noise distribution 来随机采样若干条负边,即 nagative sampling
  4. word-word 网络、word-doc 网络、word-label 网络都可以使用上述目标函数来优化学习。事实上对于 word-word 网络我们可以将无向边视为两条有向边, 定义为有向边的源点、 定义为有向边的重点,则word-word 网络就成为一个二部图。

    因此,异质文本网络由三个二部图组成,其中单词顶点在这三个网络之间共享。要学习异质文本网络的 embedding,最直观的方法是将三个二部图共享单词 embedding

    其中 为相应的条件概率, 为相应的边权重。

    该目标函数可以通过不同的方式优化,这取决于如何利用标记信息,即 word-label 网络。

    • 一种方法是同时使用标记信息和未标记信息,我们称之为联合训练。

      在联合训练过程中,我们同时训练三种不同类型的网络。在梯度更新过程中,我们轮流从三种类型的边中交替采样,从而更新模型。

    • 另一种方法是:先从未标记信息中无监督学习word embedding,然后在 word-label 中利用预训练的 embedding 对网络进行微调 fine-tuning 。该方法是受到深度学习中预训练pretrain 和微调 fine-tuning 思想的启发。

  5. PTE 联合训练算法:

    • 输入:

      • 异质文本网络
      • 迭代次数 (也称作采样次数,或训练样本数量)
      • 负采样数
    • 输出:所有单词的 embedding

    • 算法步骤:

      循环迭代,直到迭代了 step 。迭代过程为:

      • 采样一条正边和 个负边,更新单词 embedding
      • 采样一条正边和 个负边,更新单词 embeddingdoc embedding
      • 采样一条正边和 个负边,更新单词 embeddinglabel embedding
  6. PTE 预训练和微调算法:

    • 输入:

      • 异质文本网络
      • 迭代次数 (也称作采样次数,或训练样本数量)
      • 负采样数
    • 输出:所有单词的 embedding

    • 算法步骤:

      预训练阶段:循环迭代,直到迭代了 step 。迭代过程为:

      • 采样一条正边和 个负边,更新单词 embedding
      • 采样一条正边和 个负边,更新单词 embeddingdocument embedding

      微调阶段:循环迭代,直到迭代了 step 。迭代过程为:

      • 采样一条正边和 个负边,更新单词 embeddinglabel embedding

17.2 实验

  1. 数据集:我们选择了长文本、短文本两种类型的数据集:

    • 长文本数据集:

      • 20newsgroup 数据集:广泛使用的文本分类数据集,包含 20 个类别。

      • wiki 数据集:20104 月的维基百科数据集,包含大约 200 万篇英文文章。

        我们仅保留 2010 年维基百科中出现的常见词汇。我们选择了七种不同类别,包括 Art, History, Human, Mathematics, Nature, Technology, Sports 。每种类别我们随机选择 9000 篇文章作为带标签的文档来训练。

      • Imdb 数据集:一个情感分类数据集。为避免训练数据和测试数据之间的分布偏差,我们随机混洗了训练数据和测试数据。

      • RCV1 数据集:一个大型文本分类基准语料库。我们从数据集中抽取了四个子集,包括 Corporate, Economics, Government and Market 。在 RCV1 数据集中,文档已经被处理为 BOW 的格式,因此单词的顺序已经被丢失。

    • 短文本数据集:

      • DBLP 数据集:包含来自计算机科学领域论文的标题。我们选择了六个方向的论文,包括 database,arti cial intelligence, hardware, system,programming languages, theory 等。对于每个方向,我们选择该方向具有代表性的会议并收集该会议中发表的论文作为带标签的文档。
      • MR 数据集:一个电影评论数据集,每条评论仅包含一句话。
      • Twitter 数据集:用于情感分类的 Tweet 语料库,我们从中随机抽取了 120Tweets 然后拆分为训练集和测试集。

    我们并没有在原始数据上执行进一步的文本归一化,如删除停用词或者词干化。下表给出了数据集的详细统计信息。

  2. 对比模型:

    • BOW:经典的 BOW 方法。每篇文档使用一个 维的向量来表达,向量第 个元素为单词 TFIDF 值。

    • SkipGram:根据 SkipGram 训练得到单词的 embedding,然后我们使用单词embedding 的均值来作为文档的 embedding

    • PVDBOW:一种 paragraph embedding 版本,其中文档内单词的顺序被忽略。

    • PVDM :另一种paragraph embedding 版本,其中文档内单词的顺序被考虑。

    • LINE:我们使用 LINE 模型分别学习 word-word 网络和 word-doc 网络,分别记作 。另外,我们也考虑联合学习 word-word 网络和 word-doc 网络,记作

    • CNN:基于 CNN 模型来监督学习文本 embedding。尽管原始论文用于建模句子,我们这里将其改编为适用于长文本在内的一般单词序列。

      CNN 也可以通过预训练无监督单词的embedding 从而利用未标记数据。

    • PTEPTE 有多种变体,它们使用 word-wordword-docword-label 的不同组合。

      • 为仅使用 word-label 的版本
      • 为使用 word-wordword-label 的版本
      • 为仅使用 word-docword-label 的版本
      • 为使用 word-wordword-doc 进行无监督训练,然后使用 word-label 来微调的版本
      • PTE(joint) 为联合训练异质文本网络的版本
  3. 实验配置:

    • SkipGram,PVDBOW,PVDM,PTE,PTE 模型:

      • 随机梯度下降的 mini-batch size 设为 1
      • 学习率设为 ,其中 T 为总的迭代步数,
      • 负采样次数为 K=5
    • SkipGram, PVDBOW,PVDM,PTE 模型:共现窗口大小为 5

    • CNN 模型:我们使用 《Convolutional neural networks for sentence classi cation》 中的 CNN 结构。该结构使用一个卷积层,然后是最大池化层和全连接层。

      • 卷积层的窗口大小设为 3
      • feature map 数量设为 100
      • 随机选择训练集的 1% 作为验证集来执行早停
    • 所有embedding 模型的词向量维度为 100

  4. 评估方式:我们首先学习文档的 embedding,然后对不同的模型使用相同的训练数据和测试数据来执行分类任务。

    训练集中的所有文档都在representation learning 阶段和分类学习阶段使用。

    • 如果使用无监督 embedding 方法,则在 representation learning 阶段不使用这些文档的类别标签,这些类别标签仅在分类学习阶段才使用。
    • 如果使用predictive embedding 方法,则在representation learning 阶段和分类学习阶段都使用文档的类别标签。

    测试集中的所有文档在 representation learning 阶段和分类评估阶段使用。注意:在 representation learning阶段保留所有测试数据的标签,即这一阶段模型看不到测试数据的标签。

    在分类阶段我们使用 LibLinear 软件包的 one-vs-rest 逻辑回归模型。最终我们通过分类的 micro-F1macro-F1 指标来衡量模型效果。

    每一种配置我们都执行十次,并报告指标的均值和方差。

17.2.1 实验结果

  1. 我们在 20NG,Wiki,IMDB 数据集上的长文本效果对比如下。

    首先我们比较无监督文本 embedding 方法,可以看到:

    • 的效果最好
    • PVDM 性能不如 PVDBOW,这和原始论文中的结论不同。不幸的是我们始终无法得出他们的结论。

    然后我们比较 predictive embedding 方法,可以看到:

    • 或者PTE(joint) 效果最好。

    • 所有带 word-label 网络PTE 方法都超越了对应的无监督方法(即 LINE 模型),这表明了在监督学习下 PTE 的强大能力。

    • PTE(joint) 超越了 ,这表明了使用未标记数据可以显著改善监督学习的质量。

    • PTE(joint) 也超越了PTE(pretrain),这表明联合训练未标记数据和标记数据,要比将它们分别独立训练更有效。

    • PTE(joint) 始终优于 CNN 模型。

      另外我们通过 学到的单词 embedding 来对 CNN进行预训练,然后使用 label 信息对其进行微调。出乎意料的是:预训练 CNN20NGIMDB 数据集上显著提高,并且在 Wiki 上几乎保持不变。这意味着训练良好的无监督 embeddingCNN 预训练非常有用。

      但是,即使是预训练的 CNN,其性能仍然不如 PTE(joint) 。这可能的因为 PTE 模型可以联合训练未标记数据和已标记数据,而 CNN 只能通过预训练和微调两阶段来各自独立的使用它们。

    • PTE(joint) 也始终优于经典的 BOW 模型,经管 PTE(joint)embedding 向量维度远小于 BOW 的向量维度。

  2. 我们在 RCV1 数据集上的长文本效果对比如下。由于单词之间的顺序丢失,因此要求保留单词顺序信息的 embedding 方法不适用。这里我们观察到了类似的结论:

    • predictive embedding 方法超越了无监督 embedding
    • PTE(joint) 方法比 PTE(pretrain) 方法更有效。

  3. 我们比较了 CNNPTE(joint)IMDB 数据集上的训练实践。我们采用异步随机梯度下降算法,在 1T 内存、2.0G HZ40CPU 上执行。平均而言 PTE(joint) 要比 CNN10 倍以上。

    在使用 pretrain 时,CNN 虽然训练速度加快,但是仍然比 PTE(joint) 慢 5倍以上。

  4. 我们在短文本上比较了模型性能如下。

    首先我们比较无监督文本 embedding 方法,可以看到:

    • 效果最好。

    • 使用局部上下文级别单词共现的 要优于使用文档级别单词共现的 。这和长文本实验中结论相反。

      这是因为在短文本中,文档级别的单词共现非常稀疏。我们在主题模型中也观察到了类似的结果。

    • PVDM 性能仍然不如 PVDBOW 性能,这和长文本中结论一致。

    然后我们比较 predictive embedding 方法,可以看到:

    • PTEDBLP,MR 数据集上性能最佳,CNNTwitter 数据集上性能最好。

    • 融合了word-label 网络的 PTE 方法超越了对应的无监督embedding 方法(即 LINE 模型),这和长文本中结论一致。

    • PTE(joint) 超越了 ,这证明了融合未标记数据的有效性。

    • PTE(joint) 超越了 PTE(pretrain),这证明了对标记数据和未标记数据联合训练的优势。

    • 我们观察到 PTE(joint) 并不能始终超越 CNN。原因是单词歧义 ambiguity 问题,这类问题在短文本中更为严重。

      CNN 通过在卷积核中使用局部上下文的单词顺序来减少单词歧义问题,而 PTE 抛弃了单词顺序。我们认为:如果利用了单词顺序,则 PTE 还有很大提升空间。

17.2.2 标记数据 & 未标记数据

  1. 我们考察标记样本规模的变化对 CNNPTE 的影响。我们考虑两种模式:

    • 监督学习:不包含未标记数据。如 CNN
    • 半监督学习:包含未标记数据。如 PTE(joint)CNN 等。

    在半监督学习中,我们还比较了讲点的半监督方法:带 EM 的朴素贝叶斯NB+EM、标签传播算法 label propagation:LP

    可以看到:

    • CNNPTE 随着标记数据规模的增加,性能持续改善。
    • 在监督学习的 CNN 之间, 均优于CNN 或可与 CNN 媲美。
    • 在半监督学习的 CNN(pretrain)PTE(joint) 之间,PTE(joint) 始终优于 CNN(pretrain)
    • PTE(joint) 还始终优于经典的 NB+EMLP 方法。

    另外我们还注意到:

    • 当标记数据规模不足时,使用无监督 embeddingCNN 预训练非常有效,尤其是在短文本上。
    • 当标记数据规模增加时,对 CNN 的预训练并不总是能够改善其性能,如 DBLPMR 数据集。
    • 对于 SkipGram 模型,增加标记数据规模几乎不会进一步改善其性能。
    • DBLP 数据集上,当标记样本太少时 PTE 性能甚至不如 SkipGram 。原因是当标记数据太少时,word-label 网络的噪音太多。PTEword-label 网络与噪音较少的 word-word, word-doc 网络同等对待。一种解决办法是:在标签数据不足时,调整 word-label, word-word,word-doc 网络的采样概率。

  2. 我们考察未标记样本规模的变化对 CNN(pretrain)PTE 的影响。由于篇幅有限,这里我们仅给出 20NGDBLP 数据集的效果。

    20NG 数据集上,我们使用 10% 文档作为标记数据,剩余文档作为未标记数据;在 DBLP 数据集上,我们随机抽取其它会议发表的 20 万篇论文的标题作为未标记数据。

    我们使用 作为 CNN 的预训练模型。可以看到:

    • 当未标记数据规模增加时,CNNPTE 性能都有改善。
    • 对于 PTE 模型,未标记数据和标记数据联合训练的效果要优于单独训练。

17.2.3 参数敏感性与可视化

  1. PTE 模型除了训练步数 T 之外,大多数超参数对于不同训练集都是不敏感的(如学习率、batch size ),所以可以使用默认配置。

    我们在 20NGDBLP 数据集上考察了 PTE(joint) 对于参数 T 的敏感性。可以看到:当 T 足够大时,PTE(joint) 性能会收敛。

    实际应用中,我们可以将 T 的数量设置称足够大。经验表明:T 的合理范围是异质文本网络中所有边的数量的几倍。

  2. 我们给出了无监督 embedding (以 为代表)和 predictive embedding (以 为代表)在 20NG 数据集上采用 tSNE 可视化的结果。

    我们对训练集和测试集的文档均进行了可视化,其中文档的 embedding 为文档内所有单词的平均 embedding。可以看到:在训练集和测试集上,predictive embedding 均比无监督 embedding 更好地区分了不同的类别。这直观表明了 predictive embedding 在文本分类任务中的效果。

17.2.4 讨论

  1. 无监督 embedding 使用的基本信息是局部上下文级别或者文档级别的单词共现。

    • 在长文本中,我们可以看到文档级别的单词共现比局部上下文级别的单词共现效果更好,并且二者的结合并不能进一步改善效果。

    • 在短文本中,局部上下文级别的单词共现比文档级别的单词共现效果更好,并且二者的结合可以进一步改善效果。

      这是因为文档级别的单词共现受到文本长度太短的困扰,即文本太稀疏。

  2. predictive embedding 中:

    • PTE 相比, CNN 模型可以更有效地处理标记信息,尤其是在短文本上。这是因为 CNN 的模型结构比 PTE 复杂得多,尤其时 CNN 可以在局部上下文中利用词序从而解决单词的歧义问题。

      因此,在标记数据非常稀疏的情况下,CNN 可以超越 PTE,尤其是在短文本上。但是这个优势是以大量的计算、详尽的超参数优化为代价的。

    • CNN 相比,PTE 训练速度更快、超参数调整更容易(几乎没有需要调整的超参数)。当标记数据更为丰富时,PTE 的性能至少和 CNN 一样好甚至更好。

      PTE 模型的一个明显优势是它可以联合训练标记数据和未标记数据。相比之下 CNN 只能通过预训练来间接利用未标记数据。当标记数据非常丰富时,这种预训练并不总是有帮助的。

  3. 实践指南:

    • 当没有标记数据时:

      • 在长文本上使用 来学习无监督文本 embedding
      • 在短文本上使用 来学习无监督文本 embedding
    • 当只有少量标记数据时:

      • 在长文本上使用 PTE 来学习文本 embedding
      • 在短文本上使用 CNN(pretrain) ,其中预训练采用
    • 当有大量标记数据时:

      • 在长文本上使用 PTE(joint) 来学习文本 embedding
      • 在短文本上从 PTE(joint)CNN 或者 CNN(pretrain) 三者之间选择,其中主要考虑训练效率和模型效果之间的平衡

十八、HNE

  1. 社交网络中包含Graph 以及相关的数据,如何学到数据的representation 具有挑战:

    • 首先,社交网络上的数据规模呈指数型增长

    • 其次,社交网络上的数据类型多种多样,不仅包含文本,还有图像、视频。

    • 最后,社交网络上的数据并不是孤立的,而是相互产生关联。这些关联可以通过数据之间的链接来显式或隐式的构成:

      • 显式关联:如果文本和图像出现在同一个网页中,则该文本和图像之间构成显式关联;如果两个网页之间存在超链接,则这两个网页之间存在显式关联。
      • 隐式关联:用户的活动可以视为隐式反馈,它提供了数据之间的隐式关联。例如,如果用户使用相似的 tag 描述了多张图片,那么这些图片之间存在隐式的语义关联。

    因此,如此大规模的数据导致异常复杂的异质网络heterogeneous network,这对学习数据的统一表达提出了巨大挑战。

    为解决该问题,论文 《Heterogeneous Network Embedding via Deep Architectures》 提出了一种被称作异质网络嵌入 Heterogeneous Network Embedding:HNE 的新的方法来学习学习网络的representatioin

    • HNE 方法同时考虑顶点的内容信息和顶点之间的链接信息。
    • HNE 将不同的异质顶点映射到一个统一的潜在空间中,以便可以直接比较不同类型的顶点。

18.1 模型

  1. 定义异质网络 heterogeneous network ,其中: 为顶点集合、 为边集合。

    定义顶点的类型映射函数为: ,其中 为顶点类型集合。定义顶点的链接映射函数为: ,其中 为链接类型集合。

    • 对于同质网络 homogeneous network,我们有
    • 对于异质网络,我们有

    为便于讨论,假设网络中存在两种类型的顶点:文本类型顶点 、图像类型类型顶点 。假设网络中存在三种类型的边:text-text 类型的边 text-image 类型的边 image-image 类型的边 。并且它们满足:

    对于每个顶点,我们抽取其内容作为特征:

    • 对于文本顶点 ,我们选择该文本的 TF-IDF 向量(或者 BOW 向量)作为顶点的特征,记作 。其中 为文本顶点特征向量的维度。
    • 对于图像顶点 ,我们选择该图像的张量(如RGB 空间中的原始像素)作为顶点的特征,记作 。其中 为图像顶点张量的尺寸。

    我们采用简单的对称邻接矩阵 来表示链接关系:

    .

18.1.1 线性 HNE

  1. 假设图像顶点 的内容 映射到一个 维的空间,映射后的向量为 。最简单的映射方式是:将 按照矩阵的列进行拼接。

    我们使用两个线性变换将图像顶点、文本顶点映射到统一的低维空间:

    • 图像顶点:
    • 文本顶点:

    其中 为统一的低维空间的维度。

    顶点的相似性可以通过顶点在低维空间中的内积来实现:

    其中:

  2. 异质顶点之间存在显式或隐式的交互,这些交互具体表现为异质网络中的链接。如果两个顶点之间产生链接,则它们之间的相似性要比未链接的两个顶点的相似性更大。

    考虑一对图像顶点 ,我们定义一个pariwise 函数来编码顶点之间的链接信息:

    我们选择 ,其中 为一个偏移量。

    则定义损失函数为:

    • 存在链接时 ,此时 越大则损失越小
    • 不存在链接时 ,此时 越大则损失越大

    text-text 顶点pair 对、image-text 顶点 pair 对之间的损失函数也类似,只需要替代 函数为对应值即可。类似的偏移项替代为

    最终我们的损失函数为:

    其中:

    • 表示image-image 链接的数量,即 表示text-text 链接的数量,即 表示 image-text 链接的数量,即
    • 为平衡系数,用于平衡不同类型损失以及正则化项。
    • 等偏置项既可以从数据中学习得到,也可以设为固定值。为简单考虑,我们都设置为固定值。
  3. 上述最优化问题可以通过坐标下降法coordinate descent 得到有效解决,每次固定一个变量从而求解另一个变量:

    • 首先固定参数 从而求解参数

    • 然后固定参数 从而求解参数

      .

18.1.2 深度 HNE

  1. 在前面的介绍中,我们将不同的异质顶点映射到统一的低维潜在空间。但是,这类 embedding 函数是线性的,缺乏对复杂网络进行建模的能力。这里我们引入深度学习框架。

    前面部分我们的解决方案可以分为两个步骤:

    • 手动构造顶点的特征表示:对于文本顶点,使用其 TF-IDF 向量;对于图像顶点,使用其原始 RGB 像素点拼接而成的向量。
    • 将不同的特征表示嵌入到公共的低维空间中。

    这里我们通过深度学习将特征表示的学习、公共空间的嵌入合并为一步。

  2. 特征表示的学习:

    • 定义图像特征抽取的非线性函数为 ,其参数为 。通常我们使用 CNN 来抽取图像特征。下图为一个图像特征抽取模型,它由五个卷积层、两个全连接层组成。所有层都采用 ReLU 非线性激活函数。

      该模块称作 deep image 模块。

    • 定义文本特征抽取的非线性函数为 ,其参数为 。由于文本是非结构化的,不包含空间信息,因此通常使用全连接层FC 对文本的 TF-IDF 输入来抽取特征。

      该模块称作 deep text 模块。

    则我们的损失函数变为:

  3. 公共空间的嵌入:我们可以通过一个额外的线性嵌入层来级联deep image 模块和 deep text 模块。

    定义 ,其中 ;定义 ,其中

    则目标函数变为:

    其中:

    • 我们使用 dropout 代替了 正则化项,因此上式没有 对应的项

    • 我们使用新的损失函数:

      与前面的 相比,这里的损失函数移除了偏置项。

    该目标函数可以通过随机梯度下降SGD 来求解。

  4. 为进行端到端的 HNE 学习,我们将deep image 模块和 deep image 模块连接起来。我们以 text-text 链接为例,另外两种类型的链接也是类似的。下图包含两个deep text 模块,它们构成了pairwise text-text 模块。

    • deep text 模块包含两个FC 全连接层,然后是一个线性 embedding 层。
    • 线性 embedding 层的输出是公共潜在空间中的低维向量,该低维向量进一步送到预测层 prediction layer 来计算损失函数。
    • text-text 模块是对称的,下图中相同颜色的神经元共享相同的权重和偏差,箭头表示前向传播的方向。

  5. HNE 的整体架构如下图所示,图中展示了三个模块,从左到右依次为 image-image 模块、image-text 模块、text-text 模块。这些模块分别连接到prediction layer 来计算损失函数。

    下图中,相同的颜色代表共享权重。箭头表示前向传播和反向传播的方向。

  6. 目前为止我们仅展示了两种类型顶点的异质网络embedding 方法。事实上,我们的框架也支持多种类型顶点的异质网络 embedding

    另外,我们提出的方法是无监督学习方法,因此可以作为下游fine-tuning 微调阶段的预训练pretraining 步骤来使用。

    也可以将prediction layer 替换为 softmax 层,从而将整个深度网络转换为 task-specific 的端到端有监督训练模型。

18.2 实验

  1. 数据集:我们使用来自现实世界社交网络的两个公开数据集:

    • BlogCatalog:一个博客社交网络,用户可以在预定义的类别下对该用户的博客进行分类。

      我们根据“关注”行为来构建用户之间的链接,并使用每个用户的所有博客内容的 TF-IDF 向量作为用户的内容特征。最终我们得到一个无向、同质图,每个顶点代表一个用户,顶点的特征为TF-IDF 向量。

      最终该图包含 5196 个顶点、171743 条边、类别数量 6、内容向量维度 8189,并且该数据集各类别是平衡的。

    • NUS-WIDEFlickr 上的图片和文本数据,包含 269648 张关联有 tag 的图像,其中 tag 集合大小为 5018 。每一组image-tag 标记有一个 label ,一共 81 个类别。

      • 由于原始数据中包含很多不属于任何类别的噪音样本,因此这些样本被删除。
      • 另外,我们将频次最高的 1000tag 作为文本并抽取其 TF-IDF 向量作为特征。
      • 我们进一步删除了不包含任何这 1000tag 的样本。

      最终我们分别随机抽样了 5384436352 个样本进行训练和测试。我们将图像和文本分别视为独立的顶点来构建异质网络,训练网络包含 107688 个顶点、测试网络包含 72704 个顶点。如果两个顶点共享至少一个概念 concept,则构建它们之间的语义链接。我们对每个顶点最多随机采样 30 个链接,从而构建稀疏的邻接矩阵

      我们以 out-of-sample 方式来评估不同的算法,即:训练样本绝对不会出现在测试数据集中。

  2. 对于所有配置我们随机重复执行五次,并取结果的平均值。

  3. 我们从 BlogCatalog 数据集中随机选择 500 个顶点,然后可视化其链接,其中每个顶点的颜色代表其类别。

    可以看到:

    • 相对而言,“关注” 关系倾向于将具有相似属性的用户聚合在一起
    • 绝对而言,这种聚合之中存在大量噪音。统计表明:59.89% 的链接连接到了不同类别的顶点。

  4. 我们考察 HNE 算法训练过程中重建链接的准确性。我们评估了算法学习 embedding 过程中,训练集每个 mini-batch 的链接重建准确性 accuracy :预估正确的 pair 对的数量, 除以所有的 pair 对的数量。其中 mini-batch = 128

    横轴表示 epoch ,每个 epoch 包含 500step 。红线表示每个 epoch 重建准确性的均值。

    可以看到:随着学习的推进,算法能够正确地重建 80% 以上的链接。

  5. 我们在 BlogCatalog 数据集上比较了以下模型来无监督抽取特征:

    • Content:基于原始空间的内容特征,即用户所有博客的 TF-IDF 特征向量
    • Links:基于原始空间的链接特征,即用户的邻接关系作为特征
    • Link-Content:将内容和邻接关系都视为特征
    • LUFS:针对内容和链接的无监督特征抽取框架
    • LCMF:基于链接和内容的矩阵分解方法
    • HNE:我们提出的异质网络特征抽取方法

    对于这些抽取出来的特征,我们使用标准的 kNN 分类器来评估特征的分类效果。为确保公平比较,所有方法的 embedding 维度固定为 100 。对于 Content/Links/Link-Content 方法抽取的特征,我们使用 PCA 算法投影到 100 维的空间。

    这些模型的分类准确率如下所示。可以看到:

    • 在不同规模的训练集中,HNE 始终优于其它的 baseline 方法。这是因为网络链接可以编码很多有用的信息。

    • 如果将 embedding 视为预训练步骤,并通过将多类 softmax 替换掉 predict layer 来微调整个模型,则我们的效果会进一步提升。

      这表明了无监督的 embedding 学习对于有监督分类任务提供了很好的初始化,并能进一步提升性能。

  6. 我们还比较了BlogCatalog 数据集上不同方法得到的 embedding 的聚类表现。与分类任务相比,聚类任务是完全无监督的,并很大程度上依赖于相似性度量函数。这里我们采用最常见的余弦相似度。

    我们根据聚类后的结果以及label 信息,同时给出了准确率和互信息 normalized mutual information :NMI 作为评估指标。

    结果表明:

    • 类似分类任务,仅使用链接会带来最差的结果。这可能是因为:在没有全局内容信息指导的条件下,相似性往往是局部的,并且对噪音非常敏感。
    • 仅内容相似性不足以捕获关系信息。
    • 通过链接和内容的简单组合,这可以提供与其它 baseline 相当的性能。
    • 我们的 HNE 模型优于所有其它 baseline 模型。

  7. BlogCatalog 相比,NUS-WIDE 数据集构成了一个包含图像、文本的异质网络。该数据集上的对比模型包括:

    • Canonical Correlation Analysis: CCA:根据输入的多个数据源的关系将它们嵌入到共同的潜在空间。
    • DT:一种迁移学习方法,通过潜在 embedding 来减少图像和文本之间的语义距离。
    • LHNEHNE 的线性版本。

    我们为所有其它baseline 方法抽取了 4096 维的特征,但是由于我们的HNE 方法是端到端的,因此不需要为图像手动抽取特征。

    由于 NUS-WIDE 数据集是类别不平衡的,因此我们用平均精度 average precsision:AP 来评估每种可能的标签结果的分类性能。

    为了方便比较,所有方法的公共嵌入空间的维度为 400 维,并且使用线性支持向量机 SVM 来作为所有方法产出的 embedding 的通用分类器。之所以用 SVM 是因为计算 AP 需要预估一个概率值,而这不方便从深度神经网络分类器中取得。

    我们比较了三种配置:

    • image only:仅在图像顶点上学习 embedding,然后训练 SVM、执行分类测试。
    • text only:仅在文本顶点上学习 embedding,然后训练 SVM、执行分类测试。
    • image + text:同时使用图像顶点和文本顶点学习 embedding,然后后训练 SVM、执行分类测试。

    可以看到:

    • 在所有配置中,仅使用文本数据进行分类效果最差。这可能是由于:和图像输入相比,文本输入非常稀疏。
    • 仅使用线性的 HNE ,我们就可以获得与 DT 相当的结果。
    • 非线性HNE 在所有三种配置中进一步提高性能,这表明使用非线性函数同时优化特征学习和潜在 embedding 的优势。

  8. 为进一步验证 HNE 的能力,我们在 cross-modal 检索任务中将我们的方法和 baseline 进行比较。

    我们的目标是希望通过文本 query 来召回对应的图片。在所有 81label 中,有 75 个出现在 TF-IDF 文本向量中。因此我们基于这 75label 单词来构建 query 向量:

    其中query 向量长度为 1000, 除了第 label 对应的位置为 1,其它所有位置为零。query 向量一共有 75 个。

    根据学到的 embedding 函数,我们将这些 query 向量都映射到公共潜在空间中,并通过欧式距离来检索测试集中的所有图像。我们报告了 average precision at rank k:p@ktop k 结果中的平均precision 值) 的结果。 可以看到:HNE 明显优于其它 baseline

    然后我们给出一些检索的案例。可以看到:

    • Mountain 的第三个检索结果不正确,这可能是由于其它Mountain 图像和带有牛的Mountain图像之间存在极大的视觉相似性。

    • Cow 的检索结果中包含三只鹿,这是因为这些图像具有多个tag,并通过“动物” 概念进行链接。

      由于我们的方法以及 ranking 函数完全是无监督的,因此 cowdeer 等对象之间的联系会混淆我们的 embedding 学习。我们预期使用监督 ranking 可以提升性能。

  9. 我们展示了HNEBlogCatalog 数据集上目标函数的变化,从而验证模型的收敛性。其中 x 轴代表 epoch

    可以看到:目标函数经过 60epoch 的持续性降低之后趋向于平稳,这表明算法可以收敛到稳定结果。

  10. AP 就是P-R 曲线下的面积,mAP 就是所有类别的 AP 的均值。

    事实上,AP 就是把 recall 的取值根据 一共 11 个水平,然后取对应的 Precision 的平均值。在 P-R 曲线上这等价于曲线的线下面积。

十九、AANE

  1. 在很多实际应用中,网络顶点通常会伴随着一组丰富的属性或特征,即属性网络 attributed network。因此,在对顶点embedding 建模的过程中考虑顶点属性会有所帮助,即 attributed network embedding:ANE 。但是,ANE 在以下三个方面具有挑战性:

    • 算法复杂度:较高的算法复杂度限制了某些 ANE 算法在实际任务中的应用。已有一些算法基于网络的结构信息和属性信息来学习顶点embedding,但是这些算法要么在每个迭代step 中使用了 复杂度的特征值分解, 要么使用了收敛速度很慢的梯度下降。

    • heterogeneous 异质信息:由于同时引入了结构信息和属性信息,因此如何在网络的结构和属性的联合空间中评估顶点的邻近度(即距离)是一个挑战。

      另外,随着网络规模的扩大,顶点的属性邻近度矩阵通常非常庞大,难以存储到单台计算机上,更别提对它进行操作。

    • 噪音:网络结构信息和顶点属性信息可能都是残缺的、带噪音的,这进一步加入了顶点 embedding 学习的难度。

    因此,现有方法无法直接应用于 scalableattributed network embedding 。为解决该问题,论文 《Accelerated Attributed Network Embedding》 提出了一种加速属性网络 embedding 算法 accelerated attributed network embedding:AANE

    一方面, AANE 将顶点属性纳入到顶点 embedding 过程中;另一方面,AANE 提出了一种分布式优化算法,该算法将复杂的建模和优化过程分解为很多子问题,从而能够以分布式方式完成联合学习。

19.1 模型

  1. 为一个网络,其中 为顶点集合, 为定输数量, 为边的集合, 为权重矩阵。定义顶点 的直接邻接顶点为 ,其大小为

    • 每条边 关联一个权重 。这里我们关注于无向图,因此有

      • 更大的 意味着顶点 之间产生更强的关联,或者说更大的相似性。
      • 意味着顶点 之间不存在边。
    • 定义顶点 的属性向量为 ,其中 为属性的维度。定义属性矩阵为 ,其中 的第 行。

    定义attributed network embedding 为:给定网络 以及属性矩阵 ,任务的目的是给出每个顶点 一个低维embedding 向量 ,使得embedding 向量能够同时保留顶点的结构邻近关系、顶点的属性邻近关系。

  2. ANE 需要保留网络的结构邻近关系,为此 AANE 提出两个假设:

    • 首先,假设基于图的映射在边上是平滑的,特别是对于顶点密集的区域。即图上映射的连续性假设。
    • 其次,边的权重更大的一对顶点更有可能具有相似的 embedding

    因此 AANE 提出以下损失函数来最小化相连顶点之间的 embedding 差异:

    较大时(顶点 相似性更大),为最小化 的距离将减小。

  3. ANE 需要保留网络的属性邻近关系,AANE 考虑利用顶点的 embedding 内积来逼近顶点的属性相似性。

    假设顶点 的属性相似性为 ,这里我们直接使用 cosin 相似度。因此有:

    AANE 提出以下损失函数来最小化顶点之间的属性损失: