0%

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

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

其中,一个很好的例子就是对类别数据(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 等方法可能可以提升效果。

本系列翻译自 Rodion Chachura 发布于 Medium 的系列文章 Linear Algebra with Javascript,旨在帮助复习线性代数的基本概念与运算,并了解如何使用 React、SVG、ThreeJS 等技术栈对线性代数的二维、三维向量、矩阵、线性变换进行可视化。

本系列共包含 5 篇文章:

  1. 用 React 制作线性代数教程示例:网格与箭头
  2. JavaScript 线性代数:向量
  3. JavaScript 线性代数:线性变换与矩阵
  4. JavaScript 线性代数:使用 ThreeJS 制作线性变换动画
  5. 线性代数:矩阵基本运算

本文发表于2007年,作者是来自多伦多大学计算机系的几位师生。虽然本文在领域内影响并不大,但我认为它的撰写非常清晰,有利于对“基于社会网络的推荐系统”这一课题的了解。

概述

作者提出了一种基于社会网络的推荐系统,这种推荐系统利用用户资料以及用户与用户之间的连接进行推荐(具体来说是通过用户的打分矩阵和对应的朋友关系来推荐)。

本文的数据来源于一个名为 BoardGameGeek(BGG)的网站,在数据一节详细描述

背景与相关工作

所谓推荐系统,是一种基于用户以往数据、通过某些算法计算,向用户推送新内容的一种机制,在 20 世纪互联网经济发展中被广泛使用。最早利用推荐系统扩大利润的是电商 Amazon,他们利用用户曾经购买或评分的商品来预测用户之后可能会购买的商品并进行推送,从而促使用户购买更多的商品。

推荐系统最常用的方式就是基于内容的协同过滤方法(这种方式在今天也被广泛使用,好处是推荐较为准确,坏处是计算量极大),具体来说就是通过计算多个用户喜好的相似,来推荐对应的对象。

推荐系统研究的一个难点就是数据的获取,使用用户数据容易触及隐私问题,因此各个公司都是在利用用户的公开数据来进行推荐系统的研究。这又有另一个问题:很多用户的公开数据并不完全(比如获取不到用户间的联系),导致困难重重。此外,传统的算法的前提假设为用户是独立的存在,因此无法利用用户的结构信息来进行推荐。

作者通过对社会学和机器学习的研究,为 boardgaming 开发了一种 Online Social Network-based(OSN)推荐系统,实现了较好的推荐效果。

最后作者还对数据的隐私问题和算法的应用进行了讨论。

数据

BoardGameGeek(BGG)是一个知名的游戏站点,人们在其中讨论各种游戏机和卡带,并且会对各个游戏、主机等产品进行评价、打分。比较特殊的是,这个网站包含了大量的公开社交信息(玩家会公开加好友,并进行讨论),因此适合用来使用社会网络来构建推荐系统。

最终,作者使用的数据包括:

  • 大约 3 万条被用户评价过的游戏数据
  • 大约 4 万条曾经评价过游戏的用户数据
  • 所有的任意用户对任意游戏的评价数据
  • 各个用户“愿望清单”的游戏列表
  • 用户与用户之间的好友关系

算法

作者使用了概率矩阵分解算法(probabilistic matrix factorization,简称 PMF 算法)。在此简单描述一下这个算法:

给定一个维数为 $M \times N$ 的评价矩阵 $R$,其中 $R_{ij}$ 可以表示用户 $i$ 对游戏 $j$ 的评价分数。而 PMF 算法的目的就是对评价矩阵 $R$ 进行矩阵分解,找到评价矩阵的因子:

其中 $U \in \mathcal { R } ^ { M \times D } $, $G \in \mathcal { R } ^ { D \times N }$。作者假设有一些“原型用户”(prototype user),这种用户具有评分和喜好的代表性。上式中的$D$就是这种“原型用户”的数量。因此上面的矩阵分解就能得出原型用户的评分矩阵。作者直接利用 FA、PCA 之类的矩阵分解算法,使用方差 $\left( \sum _ { i , j } R _ { i j } - U _ { i } ^ { T } G _ { j } \right) ^ { 2 }$ 作为损失函数,对矩阵分解算法进行优化。(注,这应该是非常稀疏的矩阵分析)

为了把社会网络的信息加入模型中,作者将社交信息定义为矩阵 $F$,其维数是 $M \times M$。在 $F$ 中,如果用户 $i$ 和 $j$ 是好友关系,则 $F_{ij} = 1$,否则为 0。由此,作者将前面的矩阵分析式子改写为:

转换问题,写作:

这样就可以继续用前文的方法求出原型用户的评分了。

实验

作者使用 SE(方差)loss 对矩阵分解进行优化,在训练迭代过程中 loss 下降情况如下图所示:

-w445

可以看到算法确实收敛了。(个人觉得可能过拟合了)

这个实验因为没有标注数据,所以也不好进行评价。因此作者用少数的数据作为测试集来验证效果,发现结果不错,最后直接将这个 baseline 做成了一款 Web 应用。

总结

本文提出了一种同时利用社会网络信息和用户评分信息的推荐算法,改善了推荐系统的效果。其意义是找了一种方法来把简单的社会网络信息给整合进传统的评分矩阵分解法中。总体来说整个文章的方法非常简单,而且实验不够置信,但可以用来参考了解“基于社会网络的推荐系统”这一课题。

此外,这篇文献的年代其实比较久远,目前已经有各种各样利用 Network Embedding 的方法,利用各种异构网络信息去做推荐系统,但其实主要的方法还是这篇文章中的方法:将评分矩阵与网络表示矩阵进行合并,然后再做矩阵分析。区别是本文的 Social Network 的表示实质上就是最简单的 one-hot Network Embedding,如果换成现代先进的 node2vec、deep walk 之类的方法应该会有所提升。