数学之美梳理（六）矩阵运算和文本处理中的两个分类问题

发表于 更新于 分类于 Waline：

在自然语言处理中，最常见的两个分类问题是：将文本按主题归类（如将所有介绍奥运会的归类到体育类）和将词汇按意思分类（如将各种体育项目的名称归类到体育类）。这两个问题都可以通过矩阵运算来圆满地，一次性解决。

矩阵运算与文本分类

新闻分类乃至各种分类其实是一个聚类问题，关键是计算两篇新闻的相似性。为了完成这个过程，我们需要将新闻变成代表它们内容的实词，然后再变成一组数，具体来说是向量，最后求这两个向量的夹角。当这两个向量的夹角很小时，新闻就相关；当两者垂直或者说正交时，新闻则无关。

从理论上讲，这种算法非常漂亮，但是因为要对所有新闻做两两计算，而且要进行很多次迭代，耗时会特别长，尤其是新闻的数量很大，且词汇表的数量也很大时。

此时我们希望有一个办法，一次就能把所有新闻相关性计算出来，这个一步到位的方法就是利用矩阵运算的奇异值分解。

让我们看一下奇异值分解是怎么回事。首先，我们用一个大的矩阵来描述成千上万篇文章和几十上百万个词的关联性。在这个矩阵中，每一个行对应一片文章，每一列对应一个词，如果有M篇文章，N个词，那我们就得到了一个M×NM \times N 的矩阵 A

其中第i行，第j列的元素aija_{ij} ，是字典中第j个词在第i篇文章中出现的加权词频，如TF-IDF。大家可能会猜到，这个矩阵非常大，比如M=1000000，N=500000，那么这个矩阵就有5000亿个元素。

奇异值分解，就是把上面这样一个大的矩阵，分解成三个小矩阵相乘，如刚才这个矩阵，可以分解成一个100万乘100的矩阵X，一个100乘100的矩阵B和一个100乘50万的矩阵Y。这三个矩阵的元素加起来不过1.5亿个，不到原来的三千分之一，相应的存储量和计算量都会小三个数量级以上。

这三个矩阵都有着非常清晰的物理含义：

  1. 第一个矩阵X是对文本进行分类的一个结果，每一行代表一个文本，每一列代表一个主题
  2. 第三个矩阵Y是对词进行分类的一个结果，每一行代表一个语意相近的词类，每一列代表一个词
  3. 中间的第二个矩阵表明的是主题和词类的关系，每一行代表一个主题，每一列代表一个词类

第一个矩阵和第二个矩阵相乘的结果是文本和不同词类的相关性，再和第三个矩阵相乘得到的是文本和不同词的相关性

因此，只要对关联矩阵A进行一次奇异值分解，就可以同时完成近义词分类和文章分类。另外还能得到每个主题和各个词的的语义类之间的相关性。

奇异值分解的方法和应用场景

在严格的数学定义上的奇异值分解是这样的，矩阵A可以分解成三个矩阵相乘：

AMN=XMM×BMN×YNNA_{MN} = X_{MM} \times B_{MN} \times Y_{NN}

其中X是一个酉矩阵（Unitary Matrix），Y则是一个酉矩阵的共轭矩阵。与其共轭矩阵转置相乘等于单位阵的矩阵叫做酉矩阵，因此酉矩阵及其共轭矩阵都是方形的矩阵。而B是一个对角阵，即只有对角线上是非零值。

从这个公式来看，未做近似的奇异值分解没有像我们刚才讲的那样降低矩阵的维度。但是由于对角矩阵B对角线上的元素很多值相对其他值非常小，甚至为0，故可以省略。因此，奇异值分解后，一个超大矩阵就变成我们上一节中三个小矩阵的乘积。

奇异值分解一般分两步走，首先，将矩阵A变成一个双对角矩阵，这个过程的计算量是O(MN2)O(MN^2)，当然这里M>NM \gt N，否则就是O(NM2)O(NM^2)，当然我们可以利用A的稀疏性极大降低计算时间，第二步是将双对角矩阵变成奇异值分解的三个矩阵，这一步的计算量只是第一步的零头。

在文本分类中，M对应文本数量，N对应词典大小，如果比较奇异值分解的计算复杂度和余弦定理一次迭代计算文本相似度的时间，他们处于同一个量级，但是前者不需要多次迭代，因此计算量减少不少。奇异值分解的另一个问题是存储量较大，整个矩阵都需要在内存中，而余弦定理则不需要。