SVD的原理及LSA的求解

之前介绍PCA时提到了SVD,本文主要介绍SVD基本概念以及在NLP上的应用。

SVD的定义

SVD(Singular Value Decomposition)即奇异值分解,奇异值分解区别于特征值分解可用来分解非方阵矩阵问题。假设矩阵 \(A \in R^{m\times n}\) 是一个 \(m\times n\) 的矩阵,则它的奇异值分解可分解为三个矩阵:

\[A_{m\times n} = U_{m\times m} \Sigma _{m\times n} V^{T}_{n\times n} \tag{1}\]

其中 \(U\)\(V^{T}\) 称为酉矩阵, \(\Sigma\) 称为奇异矩阵,它的形式一般为:

\[\Sigma = \begin{bmatrix} \sigma_{1} & 0 & ... & 0\\ 0 & \sigma_{i} & ... & ...\\ ... & 0 & \sigma_{k} & ...\\ 0 & ... & 0 & ...\\ ... & 0 & ... & 0 \\ \end{bmatrix}\]

\(\lambda_{1} ... \lambda _{m}\) 称为奇异值

更一般的我们更希望奇异矩阵是方阵,因此矩阵\(A\)可近似分解为

\[A_{m\times n} \approx U_{m\times k} \Sigma _{k \times k} V^{T}_{k\times n} \tag{2}\]

此时奇异矩阵 \(\Sigma\)

\[\Sigma = \begin{bmatrix} \sigma_{1} & ... & 0\\ 0 & \sigma_{i} & ... \\ ... & 0 & \sigma_{k} \\ \end{bmatrix}\]

看起来是不是和特征值分解的对角矩阵很类似,非方阵的PCA降维原理就是利用这个奇异矩阵进行的

关于PCA请查阅另一篇文章 从特征值特征向量去理解PCA

SVD的求解

SVD的求解还是要回到方阵求解上,也就是要回到特征值特征向量上

可知 \(A\)\(m\times n\)矩阵,那么 \(A^{T} \in R^{n\times m}\),则有两种情况可构成方阵:

  • \(AA^{T} \in R^{m\times m}\)
  • \(A^{T}A \in R^{n\times n}\)

\((1)\) 可知, \(U \in R^{m\times m}\),此时我们用 \(AA^{T} \in R^{m\times m}\) 来求解,得到特征值特征向量如下:

\[(AA^{T})u_{i} = \lambda_{i} u_{i} \tag{3}\]

计算可求得m个特征值和m个特征向量\(u\),这些特征向量称为A的左奇异向量,酉矩阵 \(U = [u_{1}...u_{m}]\)

同理,\(V^{T} \in R^{n\times n}\),可用 \(A^{T}A\) 来求解

\[(A^{T}A) v_{i} = \lambda_{i} v_{i} \tag{4}\]

计算可求得n个特征值和n个特征向量\(v\),这些特征向量称为A的右奇异向量,酉矩阵 \(V = [v_{1}...v_{n}]\)

对于 \(\Sigma = [\sigma_{1} ... \sigma_{k}]\) 的求解有

\[\begin{align*} & A = U\Sigma V^{T} \\\\ & \Rightarrow AV = U\Sigma \\\\ & \Rightarrow Av_{i} = u_{i}\sigma_{i} \\\\ & \Rightarrow \sigma_{i} = A(v_{i} / u_{i}) \end{align*}\]

因此奇异值 \(\sigma_{i}\) 是由对应的左右奇异向量 \(u_{i}\)\(v_{i}\) 求得的

LSA的原理与示例

NLP中PCA和LSA的原理就是SVD,PCA上面已经做了简要介绍,这里主要说说LSA

LSA(Latent Semantic Analysis) 潜在语义分析的原理就是 SVD,它可以同时完成三个任务

  • 近义词分类 (利用的是 \(U\) 矩阵)
  • 主题(文档)分类 (利用的是 \(V^{T}\) 矩阵)
  • 类词和主题的相关性 (利用的是 \(\Sigma\))

LSA 的核心思想是将词和文档映射到潜在语义空间,再比较其相似性。

下面举个实例讲解,如图有

矩阵 \(X\)

矩阵 \(X\) 代表词表到文档的矩阵,其中每行代表词典中的词,每一列代表一篇文档,\(X_{ij}=k\) 代表第 \(j\) 篇文档中出现了 \(k\) 次词 \(i\) (也可用TF-IDF代替),可知该矩阵是不包含位置信息的

假设现在有四个文档:

1
2
3
4
5
6
7
8
9
10
doc1 = """计算机科学是系统性研究信息与计算的理论基础以及它们在计算机系统中如何实现与应用的实用技术的学科"""

doc2 = """自然语言处理是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言;自然语言认知则是指让电脑“懂”人类的语言。
自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。"""

doc3 = """人工智能是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,
该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等"""

doc4 = """《瓦尔登湖》是美国作家梭罗独居瓦尔登湖畔的记录,描绘了他两年多时间里的所见、所闻和所思。
该书崇尚简朴生活,热爱大自然的风光,内容丰厚,意义深远,语言生动"""

对每个文档进行分词,去停用词

1
2
3
4
5
6
7
8
9
10
11
12
def build_vocab(self, docs):
for doc in docs:
doc = doc.strip()
# 为了简单仅仅保留词的长度大于1的
words = list(filter(lambda x: len(x) > 1, self.tokenizer(doc)))
self.docs.append(words)
self.vocabs.update(words)

self.vocabs = list(self.vocabs)
self.word2idx = dict(zip(self.vocabs, range(len(self.vocabs))))

print(self.vocabs)

输出词典得到:

1
'方式', '基础', '美国作家', '生动', '易于', '人工智能', '语言', '计算机系统', '语言学', '实质', '瓦尔登湖', '生活', '计算机', '机器人', '独居', '相似', '人类', '内容', '电脑', '实现', '所闻', '计算机程序', '系统', '理解', '理论', '探讨', '该书', '它们', '数据', '了解', '处理', '企图', '以及', '学科', '生产', '包括', '图像识别', '两年', '分支', '一种', '机器', '如何', '风光', '丰厚', '描绘', '认知', '记录', '简朴', '应用', '智能', '做出', '时间', '自然语言', '所思', '崇尚', '系统性', '识别', '梭罗', '形式', '大自然', '深远', '计算', '信息', '意义', '专家系统', '生成', '所见', '研究', '一个', '运用', '转化', '领域', '实用技术', '计算机科学', '热爱', '反应'

构造词到文档的矩阵,在这里实现了词袋模型和TF-IDF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 使用词袋特征来做权值
def build_bow_matrix(self):
matrix = np.zeros([len(self.vocabs), len(self.docs)])
for docidx, words in enumerate(self.docs):
for word in words:
matrix[self.word2idx[word], docidx] += 1
return matrix

# 使用tf-idf来做权值
def build_tfidf_matrix(self):
tf = self.build_bow_matrix()
df = np.ones([len(self.vocabs), 1])

for docidx, words in enumerate(self.docs):
tf[:, docidx] /= np.max(tf[:, docidx])
for word in words:
df[self.word2idx[word], 0] += 1
idf = np.log(len(self.docs)) - np.log(df)
return tf*idf

得到的矩阵为

词袋模型

1
2
3
4
5
6
7
8
9
[[0. 0. 0. 1.]
[0. 1. 1. 1.]
[0. 2. 0. 0.]
.............
[0. 0. 0. 1.]
[0. 0. 1. 0.]
[1. 0. 0. 0.]]

shape = (vocab_size, doc_size)

TF-IDF

1
2
3
4
5
6
7
8
9
[[ 0.          0.          0.          0.34657359]
[ 0. 0. 0. 0. ]
[ 0. 0.08219488 0. 0. ]
.....
[ 0. 0. 0. 0.34657359]
[ 0. 0. 0.23104906 0. ]
[ 0.69314718 0. 0. 0. ]]

shape = (vocab_size, doc_size)

\(U\) 矩阵的应用

分解得到的 \(U \in R^{m\times m}\) 矩阵每一行代表一类近义词,我们一般对每一行的权值进行逆序排序获得top k个权值最大的下标,这些下标对应的词即为近义词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def sim_words(self, k=3):
if self.kernel == 'tfidf':
matrix = self.build_tfidf_matrix()
else:
matrix = self.build_bow_matrix()

U, S, Vt = np.linalg.svd(matrix)

# 对权值逆序排序
sort_idx = np.argsort(-U)
# 一般不取第一列,第一列的词往往是本身
topk = sort_idx[:, 1:k+1]
print("word \t similarity")
for widx, word in enumerate(self.vocabs):
line = word + ":\t"
idxs = topk[widx]
for idx in idxs:
line += str(self.vocabs[idx]) + " "
print(line)

得到的结果

1
2
3
4
计算机系统:	自然语言 领域 如何
数据: 智能 计算机科学 研究
计算机: 智能 计算机科学 研究
语言: 如何 处理 计算

由于只是作为演示用,文档太少,不能得到较好的效果,可用大文本尝试一下

\(V^{T}\) 矩阵的应用

\(V^{T} \in R^{n\times n}\) 矩阵每一列代表一个主题,列中每一行代表主题相关文档,我们对每一列的权值进行逆序,得到对应下标,这样每一列对应的下标代表同一类别的相关文档下标

1
2
3
4
5
6
7
8
9
10
11
12
13
def topic_relate(self, k=2):
if self.kernel == 'tfidf':
matrix = self.build_tfidf_matrix()
else:
matrix = self.build_bow_matrix()

U, S, Vt = np.linalg.svd(matrix)

# 按列逆序排序
sort_idx = np.argsort(-Vt, axis=1)
# 一般不取第一行,第一行是自己本身
topk = sort_idx[1:k+1, :]
print(topk)

输出

1
2
[[2 3 0 1]
[2 0 1 3]]

\(\Sigma\) 矩阵的作用

\(\Sigma \in R^{m\times n}\) 代表类词和文章类之间的相关性

由此可见LSA可谓一举三得啊!

LSA的缺点及改进

LSA的缺点在于采用暴力SVD矩阵分解,如果维数大了,矩阵大了就难以计算了,加上SVD的分布式计算又是很难实现的,所以在大规模文档中可能不用直接用LSA

pLSA

即概率LSA,把LSA变成从概率的角度理解,一般采用的是EM的方式学习

由于pLSA的推导和求解一般涉及到上帝算法EM(我把它认为是魔鬼算法,因为它原理简单,但是推导要命)在此不做深入讨论

后记

上述例子均为博主本人生造的,因为网上关于LSA的代码示例很多只做到SVD分解部分,没具体到酉矩阵的应用。

上述实例的完整代码地址: github/nlp_learning/lsa

Refrence

[1] https://blog.csdn.net/KIDGIN7439/article/details/69831490

[2] 《数学之美》

sean lee wechat
欢迎关注我的公众号!
感谢支持!