Category Archives: Linear Algebra

Simple word2vec and doc2vec from PMI matrix decomposition

Earlier I made a post about decomposing PMI matrix as label embedding. It was turning the sparse label representation into a dense representation in the multilabel classification problem, that is to operate on the right-hand side of our AX = Y problem. The same technique works on the left-hand side too. Specifically, when working with text classification problem, we can use PMI matrix decomposition to get word vectors as well as a simple doc2vec transformation.

Here is a short code snippet demonstrating how it works:

We first constructed the simplest binary doc-term matrix M, use it to construct the PMI matrix PP and then decompose it into an embedding matrix E consists of word vectors of dimension 300.

Given the word boston, we can find similar words to it by computing and sorting words based on the cosine similarity between word vectors. And we see the top 20 similar words to boston are cities, places and sports-related words.

We can also transform the original new articles into 300 dimension vectors by simply taking the dot product between M and E, and feed the resulting matrix into downstream modeling tasks, like here we made a logistic regression that archives 0.82 on both recall and precision(as a result 0.82 on f1 too).

We can show the visualize the word vectors via TSNE.

It does showcase that the more frequent two words co-occurs the closer the two words in the embedding space.

Label Embedding in Multi-label classification

In the recent Kaggle competition, inclusive images challenge  I tried out label embedding technique for training multilabel classifiers, outlined in this paper by François Chollet.

The basic idea here is to decompose the pointwise mutual information(PMI) matrix from the training labels and use that to guide the training of the neural network model. The steps are as follow:

  1. Encode training labels as you would with multilabel classification settings. Let M (of size n by m, ie n training example with m labels) denote the matrix constructed by vertically stacking the label vectors.
  2. The PMI (of size m by m) is a matrix with PMI_{i,j}=log(\frac{P(i,j)}{P(i)*P(j)}), it can be easily implemented via vectorized operations thus very efficient in computing, even on large datasets. See more explanation of the PMI here.
  3. The embedding matrix E is obtained by computing the singular value decomposition on PMI matrix and then take the dot product between U and the first k columns of \sqrt{\Sigma}.
  4. We then can use the embedding matrix to transform the original sparse encoded labels into dense vectors.
  5. During the training of deep learning model, instead of using m sigmoid activations together with BCE loss in the end, now we can use k linear activation with cosine proximity loss.
  6. During inference time, we take the model prediction and search in the rows from the embedding matrix E and select the top similar vectors and find their corresponding labels.

Below is a toy example calculation of the label embedding procedure. The two pictures are the pairwise cosine similarity between item labels in the embedding space and a 2d display of items in the embedding space.

In my own experiments, I find the model trained on label embeddings are a bit more robust to label noises, it is faster in convergence and returns higher top k precision compared with models with logistic outputs.

I believe it is due to the high number of labels in the competition (m ~= 7000) problem contrasted with the small batches the model is trained on. As this label embedding is obtained from matrix factorization, it is similar to PCA that we keep crucial information and throw out some unnecessary detail/noise, except we are doing so on the labels instead of the inputs.

 

SVD Dimension Reduction 奇异值分解 降维

降维的意义:

  1. 找出隐含的相关关系
  2. 去除无意义的特征
  3. 便于理解、可视化、存储

方法一:奇异值分解

可以参见以前的文章
A = USigma V^T

例子:

输入矩阵:

  • A_{[m times n]} 表示m篇文档和n个术语

分解获得:

  1. U_{[mtimes r]}表示m篇文档和r个概念
  2. Sigma_{[rtimes r]}, r的值等于矩阵A的rank
  3. V_{[ntimes r]}表示n个术语和r个概念

沿用之前TF-IDF时候的代码:

矩阵M4times 35的矩阵,表示4篇文章和35个术语

奇异值分解的几个属性:

  1. 实数矩阵A,总是可以进行奇异值分解的
  2. 分解后的U,Sigma ,V都是唯一的
  3. U,V都是列正交的(每一列都是相互垂直的单位向量)
  4. Sigma是一个对角矩阵,对角线上的元素是奇异值,且均为正数,并且从左上往下按照大小排列

测试一下U是否是列正交的

看一下U矩阵的具体内容:

这个矩阵每一行代表一篇文档,每一列代表一个概念。

  • 文档1和概念2,4相关性较高
  • 文档2和概念2,3相关性较高
  • 文档3和概念3相关性较高
  • 文档4和概念1相关性较高

看一下Sigma矩阵:

这个矩阵可以理解为4个概念的强度,揭示的是将数据投影到低维度空间中时,在各个坐标方向数据的方差。

看一下V^T矩阵:

每一行代表一个概念,每一列代表一个术语,每个元素代表的是术语与概念之间的相关关系,是将高位数据进行投影时所依据的坐标系。

验证一下分解的正确性:

奇异值降解SVD提供的是”最佳"低维度坐标系,“最佳”的含义是:将高维度数据投影到该低维度坐标系后损失的信息最少。

这个最佳的坐标系可以通过V^T矩阵获得,记得本例中的V矩阵的含义是:概念与术语之间的关系。

将原本表示“文档-术语"关系的矩阵M投影为"文档-概念",投影方法为:

QQ截图20150309182607

每一行代表一篇文档,每一列代表一个概念。

用SVD进行降维的方法:

  1. 进行SVD分解
  2. 若要降维至k维,用(U矩阵的前k列构成的矩阵)与(Sigma矩阵的前kk列构成的矩阵)进行点积
  3.  如果要将该低维度的数据表现恢复至高维度,则用2中结果与V^T矩阵的前k列所构成的矩阵进行点积

例如,投影到2维:

每一行代表一篇文章,每一列代表降至2维后,每篇文章在各个维度方向的投影。

将有损压缩的该低维度投影,恢复至原本的高维度:

原本数据是35维的,因而无法直接进行可视化。降至2维后,便可以了:

SVD_Plot

 

注意到,之前介绍过计算文档之间的相似程度,不妨用来验证一下,这个低维度的投影中,代表文档的点与点之间的距离,是否直觉上符合他们之间的相似度?

至于选择怎样的k来进行降维,通常会选择k使得,"能量"的损失在20%以内。

frac{sum_{i = 1}^{k}sigma_i^2}{sum_{i = 1}^{r}sigma_i^2} leq 0.8

Spectral Clustering 谱聚类

Notes on MMDS on Coursera

1 衡量聚类的“好坏”

什么样的聚集是好的聚集?

  1. 希望聚集内的相互连接尽量多
  2. 希望聚集内的节点与聚集外的节点之间连接尽量少

定义一个聚集的Cut指标(越低越好)为:网络内,只有一端节点在聚集内的边的数量。

先用AGM生成一个网络:

CutPlot1

假设现在有一个聚集A,包括三个节点[0,1,2],计算该聚集的cut指标:

Cut值并不是一个非常好的指标,如果包含度为1的节点,那么仅仅由节点一个节点构成的聚类,Cut值为1。

另一个可能的指标是Conductance(越低越好):

phi(A) = frac{text{cut(A)}}{min(vol(A), 2m-vol(A))}

其中:

  1. cut(A)是聚集A的cut分值
  2. vol(A)是聚集A的所有节点的度的和
  3. m 是网络内边的总数

2  图谱理论(Spectral Graph Theory)和谱聚类

分析表示网络的矩阵的“谱”。谱为按照对应特征值大小排列的矩阵特征向量。

CutPlot1

定义网络的拉普拉斯矩阵为网络的度矩阵与网络的邻接矩阵之差:

该矩阵有两个重要属性:

  1. 特征值都是非负实数
  2. 特征向量都是实数,并且相互垂直

一些通过线性代数可获得事实:

令拉普拉斯矩阵的特征值为lambda,特征向量为x

特征向量有两个重要属性:

  1. 是单位向量:sum_ix_i^2=1
  2. 与第一个特征向量垂直:sum_ix_icdot 1 = 0

特征值lambda _2是该表达式的最优解:

min_{x}frac{x^TMx}{x^Tx}=min_{x}sum_{i,j}(x_i-x_j)^2

因此上面的最小化问题的物理意义是将节点一部分放在<0出,另一部分放在>0处(sum_ixi=0)  ,并且使得连接两端的边尽量地小(min_{x}sum_{i,j}(x_i-x_j)^2

具体参见Rayleigh quotientFiedler vector,以及一个挺有帮助的slides

谱聚类步骤:

  1. 预处理:用拉普拉斯矩阵表示网络
  2. 分解:计算矩阵的特征值和特征向量,找到lambda_2对应的特征向量x(这样每一个节点就用一个值来表示了)
  3. 聚类:决定若干分割值,根据特征向量的值与分割值的关系,将各个节点归属到不同聚集

分割点的选择:

  1. 简单地选择0或者中位数
  2. 尝试最小化正则化的1维cut值

如果希望有多个聚集,方法有两类:

  1. 递归地进行2分聚类
  2. lambda_2lambda_3等后续特征值对应的特征向量进行K-means

奇异值分解 Singular Value Decomposition,SVD

用矩阵A乘以向量x,将获得一个新的向量y。其中,矩阵A对向量x可以进行两种变换:

  1. 旋转
  2. 伸缩

例如:

matrixtransformationofvectors

(a)中即旋转又伸缩,(b)中仅仅进行旋转,(c)中仅仅进行伸缩。

奇异值分解是对矩阵的一种因素分解,将一个矩阵分解成若干个各有其应用意义的成分。


以一个几何例子来讨论奇异值分解。

280px-Singular_value_decomposition

一个单位球在任何一个{m}times{n}矩阵下的投影都是一个超椭圆:

mathbb{R}^m下的超椭圆可以被看做是将mathbb{R}^m下的单位球沿着正交方向{u}_{1},{u}_{2},...,{u}_{m}inmathbb{R}^m进行以{sigma}_{1},{sigma}_{2},...,{sigma}_{m}inmathbb{R}^m为系数的伸缩后得到的结果。

为了方便讨论,假设{u}_{j}为单位向量,即{| {u}_{j} |}_{2}=1。则{sigma}_{j}{u}_{j}是超椭圆的主要半轴(principal semiaxes),而{sigma}_{j}为长度。

下图是一个mathbb{R}^2中的例子:

geometric example

通过矩阵A将单位圆Sinmathbb{R}^2变换为椭圆ASinmathbb{R}^2

其中{sigma}_{1},{sigma}_{2}为矩阵A的奇异值(singular values)。

注意:

  1. 如果矩阵A秩(rank)为r,则r个长度{sigma}_{j}不为0
  2. 如果矩阵Am times n矩阵,并且有m data-recalc-dims=n" />,则至多有n个长度{sigma}_{j}不为0
  3. 如果矩阵A满秩(full rank),则矩阵An个奇异值为矩阵AS中主要半轴的长度{sigma}_{j}
    通常将奇异值按照递减顺序排列,即{sigma}_{1}geq{sigma}_{2}geqldotsgeq{sigma}_{n} data-recalc-dims=0" />

一般地,在mathbb{R}^n中的该变换表示为:

A{v}_{j}={sigma}_{j}{u}_{j},1leq j leq n

一共有n个向量被A进行了变换。

更加紧凑的表达形式为:

AV=hat{U}hat{Sigma}

其中:

  1. A{m}times{n}
  2. V{n}times{n}的酉矩阵(unitary matrix)。
  3. hat{U}{m}times{n},其中列是标准正交(orthonormal)的。
  4. hat{Sigma}{n}times{n}的对角线矩阵(diagonal matrix )。如果A满秩,则 hat{Sigma}对角线值均为正。

因为V是酉矩阵,在上式两边同时乘以共轭矩阵(conjugate){V}^{*}获得:

A=hat{U}hat{Sigma}V^{*}

这个公式被称为简化奇异值分解(reduced SVD)

下图揭示了各个矩阵的维度:

dimension


通常对简化奇异值分解进行如下改进将其变为标准的奇异值分解:

  1. hat{U}矩阵中增加额外的m-nhat{U}中原有的列呈标准正交的列,构成矩阵U
    构建好的U{m}times{m},并且为酉矩阵
  2. hat{Sigma}矩阵中增加额外的m-n行0

上述过程是针对满秩矩阵而言的,对于秩亏矩阵,只需要将上述过程中的n用矩阵秩r代替即可。

得到的标准奇异值分解公式为:

A=U{Sigma}V^{*}

其中:

  1. Uinmathbb{C}^{{m}times{m}}为酉矩阵
  2. Vinmathbb{C}^{{n}times{n}}为酉矩阵
  3. Sigmainmathbb{R}^{{m}times{n}}为对角线矩阵

并且:

  • Sigma矩阵对角线上的值为非负且按照递减顺序排列
    {sigma}_{1}geq{sigma}_{2}geqldotsgeq{sigma}_{p}geq 0,p=min(m,n)

下图揭示了各个矩阵的维度:

dimension2

结合几何例子,将矩阵A的奇异值分解理解为:

  1. 首先,通过V^{*}矩阵进行酉变换,对例子中的单位球而言,该变换的效果只是旋转
  2. 然后,通过Sigma矩阵进行伸缩变换,本例中为将旋转后的单位球进行伸缩变换,形成超椭圆
  3. 最后,通过U矩阵进行酉变换,本例中为将上面形成的超椭圆进一步旋转

即,通过矩阵A进行的变换,可以视为上述3个变换的组合。


重要的定理:

  • 任何矩阵A{in}mathbb{C}^{{m}times{n}}均有一个奇异值分解,并且,奇异值{sigma}_{j}有唯一确定值。

计算奇异值分解

上面的定理确定了奇异值分解的存在,但是其值仍需要计算。

考虑如下矩阵乘法:

{A}^{T}{A} = {(U{Sigma}V^{*})}^{T}{(U{Sigma}V^{*})} ={V{Sigma}{U}^{*}}{U{Sigma}{V}^{*}} ={V}{Sigma}^{2}{V}^{*}

{A}{A}^{T} = {(U{Sigma}V^{*})}{(U{Sigma}V^{*})}^{T} ={U{Sigma}{V}^{*}}{V{Sigma}{U}^{*}} ={U}{Sigma}^{2}{U}^{*}

对上述两式分别在两边同时乘以VU有:

{A}^{T}AV = V{Sigma}^{2}

A{A}^{T}U = U{Sigma}^{2}

这样便将奇异值分解转换成了特征值的求解问题。

如果能针对这两个公式找到标准化的特征向量,则特征值的平方根即为奇异值。

在Matlab中,奇异值分解的语句为:[U,S,V]=svd(A)

Reference:

Nathan, Kutz. Computational Methods for Data Analysis Lecture Notes.