优化|PLSA理论与实践

在这里插入图片描述
PLSA又称为概率潜在语义分析,是一种利用概率生成模型对文本集合进行话题分析的无监督学习方法。该模型最大的特点是加入了主题这一隐变量,文本生成主题,主题生成单词,从而得到单词-文本共现矩阵。本文将对包含物理学、计算机科学、统计学、数学四个领域的15000条文献摘要的数据集(保存在Task-Corpus.csv中)使用PLSA算法进行处理。

一、算法推导

1.1 E-steps

设单词集合为 w i ( i = 1 , ⋯   , M ) w_i(i = 1,\cdots,M) wi(i=1,,M),其中 M M M为单词数;文本集合为 d j ( j = 1 , ⋯   , N ) d_j(j = 1,\cdots, N) dj(j=1,,N),其中 N N N为文本数;主题集合为 z k ( k = 1 , ⋯   , K ) z_k(k = 1,\cdots,K) zk(k=1,,K),其中 K K K为主题数。对给定的文本,主题的分布是一个有 K K K个选项的多项分布,因此参数个数为 N × K N\times K N×K,设参数矩阵为 Λ \Lambda Λ。对给定的主题,单词的分布是一个有 M M M个选项的多项分布,因此参数个数为 K × M K\times M K×M,设参数矩阵为 Θ \Theta Θ。一般来说 K ≪ M K \ll M KM,这就避免了模型的过拟合。

如果主题未知,根据全概率公式有
p ( w i , d j ) = p ( d j ) ∑ k = 1 K p ( w i ∣ z k ) p ( z k ∣ d j ) p(w_i, d_j) = p(d_j)\sum_{k = 1}^K p(w_i | z_k)p(z_k | d_j) p(wi,dj)=p(dj)k=1Kp(wizk)p(zkdj)
因此非完全数据(主题未知)的似然函数为
L ( Θ , Λ ∣ X ) = p ( X ∣ Θ ) = ∏ i = 1 M ∏ j = 1 N ( p ( d j ) ∑ k = 1 K p ( w i ∣ z k ) p ( z k ∣ d j ) ) n ( w i , d j ) L(\Theta, \Lambda | X) = p(X | \Theta) = \prod_{i = 1}^M\prod_{j = 1}^N (p(d_j)\sum_{k = 1}^K p(w_i | z_k)p(z_k | d_j))^{n(w_i, d_j)} L(Θ,Λ∣X)=p(X∣Θ)=i=1Mj=1N(p(dj)k=1Kp(wizk)p(zkdj))n(wi,dj)
对数似然为
log ⁡ L ( Θ , Λ ∣ X ) = ∑ i = 1 M ∑ j = 1 N n ( w i , d j ) log ⁡ ( p ( d j ) ∑ k = 1 K p ( w i ∣ z k ) p ( z k ∣ d j ) ) \log L(\Theta, \Lambda | X) = \sum_{i = 1}^M \sum_{j = 1}^N n(w_i, d_j)\log(p(d_j)\sum_{k = 1}^K p(w_i | z_k)p(z_k | d_j)) logL(Θ,Λ∣X)=i=1Mj=1Nn(wi,dj)log(p(dj)k=1Kp(wizk)p(zkdj))
对数似然中包含求和的对数,因此难以处理。

如果主题已知,文章 d j d_j dj出现单词 w i w_i wi的概率为
p ( w i , d j ) = p ( d j ) p ( w i ∣ z k ) p ( z k ∣ d j ) p(w_i, d_j) = p(d_j)p(w_i | z_k)p(z_k | d_j) p(wi,dj)=p(dj)p(wizk)p(zkdj)
因此完全数据的似然函数为
L ( Θ ∣ X ) = ∏ i = 1 M ∏ j = 1 N ( p ( d j ) p ( w i ∣ z k ) p ( z k ∣ d j ) ) n ( w i , d j ) L(\Theta | X) = \prod_{i = 1}^M \prod_{j = 1}^N (p(d_j)p(w_i | z_k)p(z_k | d_j))^{n(w_i, d_j)} L(Θ∣X)=i=1Mj=1N(p(dj)p(wizk)p(zkdj))n(wi,dj)
对数似然为
log ⁡ L ( Θ ∣ X ) = ∑ j = 1 N n ( w i , d j ) log ⁡ ( p ( d j ) p ( w i ∣ z k ) p ( z k ∣ d j ) ) \log L(\Theta | X) =\sum_{j = 1}^N n(w_i, d_j) \log(p(d_j)p(w_i | z_k)p(z_k | d_j)) logL(Θ∣X)=j=1Nn(wi,dj)log(p(dj)p(wizk)p(zkdj))
Q函数为对数似然 log ⁡ L ( Θ ∣ X ) \log L(\Theta | X) logL(Θ∣X)在后验分布 p ( z k ∣ w i , d j ) p(z_k | w_i, d_j) p(zkwi,dj)下的期望
Q = ∑ k = 1 K p ( z k ∣ w i , d j ) ∑ i = 1 M ∑ j = 1 N n ( w i , d j ) log ⁡ ( p ( d j ) p ( w i ∣ z k ) p ( z k ∣ d j ) ) = ∑ i = 1 M ∑ j = 1 N n ( w i , d j ) ∑ k = 1 K p ( z k ∣ w i , d j ) log ⁡ ( p ( d j ) p ( w i ∣ z k ) p ( z k ∣ d j ) ) \begin{aligned}Q &= \sum_{k = 1}^K p(z_k | w_i, d_j) \sum_{i = 1}^M \sum_{j = 1}^N n(w_i, d_j) \log(p(d_j)p(w_i | z_k)p(z_k | d_j)) \\&= \sum_{i = 1}^M \sum_{j = 1}^N n(w_i, d_j)\sum_{k = 1}^K p(z_k | w_i, d_j)\log(p(d_j)p(w_i | z_k)p(z_k | d_j))\end{aligned} Q=k=1Kp(zkwi,dj)i=1Mj=1Nn(wi,dj)log(p(dj)p(wizk)p(zkdj))=i=1Mj=1Nn(wi,dj)k=1Kp(zkwi,dj)log(p(dj)p(wizk)p(zkdj))
其中后验概率
p ( z k ∣ w i , d j ) = p ( w i ∣ z k ) p ( z k ∣ d j ) ∑ k = 1 K p ( w i ∣ z k ) p ( z k ∣ d j ) (1) p(z_k | w_i, d_j) = \frac{p(w_i | z_k) p(z_k | d_j)}{\sum_{k = 1}^K p(w_i | z_k) p(z_k | d_j)}\tag{1} p(zkwi,dj)=k=1Kp(wizk)p(zkdj)p(wizk)p(zkdj)(1)

1.2 M-step

p ( w i ∣ z k ) , p ( z k ∣ d j ) p(w_i | z_k), p(z_k | d_j) p(wizk),p(zkdj)满足约束条件
∑ i = 1 M p ( w i ∣ z k ) = 1 , k = 1 , ⋯   , K \sum_{i = 1}^M p(w_i | z_k) = 1, k = 1,\cdots,K i=1Mp(wizk)=1,k=1,,K
∑ k = 1 K p ( z k ∣ d j ) = 1 , j = 1 , ⋯   , N \sum_{k = 1}^K p(z_k | d_j) = 1,j = 1,\cdots,N k=1Kp(zkdj)=1,j=1,,N
引入拉格朗日函数
J = Q + ∑ k = 1 K r k ( 1 − ∑ i = 1 M p ( w i ∣ z k ) ) + ∑ j = 1 N ρ j ( 1 − ∑ k = 1 K p ( z k ∣ d j ) ) J = Q + \sum_{k = 1}^K r_k(1 - \sum_{i = 1}^M p(w_i | z_k)) + \sum_{j = 1}^N\rho_j(1 - \sum_{k = 1}^K p(z_k | d_j)) J=Q+k=1Krk(1i=1Mp(wizk))+j=1Nρj(1k=1Kp(zkdj))
∂ J ∂ p ∗ ( w i ∣ z k ) = ∑ j = 1 N n ( w i , d j ) p ( z k ∣ w i , d j ) p ( w i ∣ z k ) − r k = 0 \frac{\partial J}{\partial p^*(w_i | z_k)} = \sum_{j = 1}^N \frac{n(w_i, d_j) p(z_k | w_i, d_j)}{p(w_i | z_k)} - r_k = 0 p(wizk)J=j=1Np(wizk)n(wi,dj)p(zkwi,dj)rk=0
因此
r k p ∗ ( w i ∣ z k ) = ∑ j = 1 N n ( w i , d j ) p ( z k ∣ w i , d j ) r_k p^*(w_i | z_k) = \sum_{j = 1}^N n(w_i, d_j) p(z_k | w_i, d_j) rkp(wizk)=j=1Nn(wi,dj)p(zkwi,dj)
i i i求和,就有
r k = ∑ i = 1 M ∑ j = 1 N n ( w i , d j ) p ( z k ∣ w i , d j ) r_k = \sum_{i = 1}^M \sum_{j = 1}^N n(w_i, d_j) p(z_k | w_i, d_j) rk=i=1Mj=1Nn(wi,dj)p(zkwi,dj)
p ∗ ( w i ∣ z k ) = ∑ j = 1 N n ( w i , d j ) p ( z k ∣ w i , d j ) ∑ i = 1 M ∑ j = 1 N n ( w i , d j ) p ( z k ∣ w i , d j ) ( 2 ) p^*(w_i | z_k) = \frac{\sum_{j = 1}^N n(w_i, d_j) p(z_k | w_i, d_j)}{\sum_{i = 1}^M \sum_{j = 1}^N n(w_i, d_j) p(z_k | w_i, d_j)} \qquad (2) p(wizk)=i=1Mj=1Nn(wi,dj)p(zkwi,dj)j=1Nn(wi,dj)p(zkwi,dj)(2)
同理
p ∗ ( z k ∣ d j ) = ∑ j = 1 N n ( w i , d j ) p ( z k ∣ w i , d j ) ∑ i = 1 M n ( w i , d j ) ( 3 ) p^*(z_k | d_j) = \frac{\sum_{j = 1}^N n(w_i, d_j) p(z_k | w_i, d_j)}{\sum_{i = 1}^M n(w_i, d_j)} \qquad (3) p(zkdj)=i=1Mn(wi,dj)j=1Nn(wi,dj)p(zkwi,dj)(3)

( 1 ) ( 2 ) ( 3 ) (1)(2)(3) (1)(2)(3)三式共同构成PLSA算法的迭代公式。

二、算法实现

用python实现PLSA算法。首先对数据集先做预处理。对给定的文本进行分词,利用wordnet语料库将同义词进行替换(例如单复数不同的词需要替换成同一个词),并将停用词排除(停用词表在网上下载,参见作业中的stopwords.dic文件)。然后对全体文本构成的单词集合进行词频统计,构建词频矩阵 n ( w i , d j ) n(w_i, d_j) n(wi,dj)。这一部分用到了python的nltk包。核心代码如下。

words = set()
    word_counts = []
    for document in documents:
        seglist = word_tokenize(document)
        wordlist = []
        for word in seglist:
            synsets = wordnet.synsets(word)
            if synsets:
                syn_word = synsets[0].lemmas()[0].name()
                if syn_word not in stopwords:
                    wordlist.append(syn_word)
            else:
                if word not in stopwords:
                    wordlist.append(word)
        words = words.union(wordlist)
        word_counts.append(Counter(wordlist))
    word2id = {words:id for id, words in enumerate(words)}
    id2word = dict(enumerate(words))

    N = len(documents) # number of documents
    M = len(words) # number of words
    X = np.zeros((N, M))
    for i in range(N):
        for keys in word_counts[i]:
            X[i, word2id[keys]] = word_counts[i][keys]

然后根据 ( 1 ) ( 2 ) ( 3 ) (1)(2)(3) (1)(2)(3)三式进行PLSA算法的编写。注意到这三个式子都可以写成矩阵的形式,提高运算效率。同时注意到这三个式子都和分子成正比,因此可以计算出份子再除以归一化常数即可。E-step的代码如下。

def E_step(lam, theta):
    # lam: N * K, theta: K * M, p = K * N * M
    N = lam.shape[0]
    M = theta.shape[1]
    lam_reshaped = np.tile(lam, (M, 1, 1)).transpose((2,1,0)) # K * N * M
    theta_reshaped = np.tile(theta, (N, 1, 1)).transpose((1,0,2)) # K * N * M
    temp = lam @ theta
    p = lam_reshaped * theta_reshaped / temp
    return p

M-step的代码如下。

def M_step(p, X):
    # p: K * N * M, X: N * M, lam: N * K, theta: K * M
    # update lam
    lam = np.sum(p * X, axis=2) # K * N
    lam = lam / np.sum(lam, axis=0) # normalization for each column
    lam = lam.transpose((1,0)) # N * K

    # update theta
    theta = np.sum(p * X, axis=1) # K * M
    theta = theta / np.sum(theta, axis=1)[:, np.newaxis] # normalization for each row
    
    return lam, theta

计算对数似然的代码如下。

def LogLikelihood(p, X, lam, theta):
    # p: K * N * M, X: N * M, lam: N * K, theta: K * M
    res = np.sum(X * np.log(lam @ theta)) # N * M
    return res

用随机数初始化 Θ , Λ \Theta,\Lambda Θ,Λ以避免落入局部最优。设定最大迭代次数为200。对数似然的阈值为10。当相邻两次对数似然的差小于阈值或者达到最大迭代次数时停止迭代。如果计算对数似然时报错,说明某个参数被舍入到0,此时也需要停止迭代。

三、结果分析

由于笔记本电脑的内存有限,从所给数据集中随机抽取1000篇文本进行实验。设定主题数为4。某次实验的结果如下。构建的字典中包含11342个单词。字典保存在dictionary.json文件中。

程序在迭代152次后停止。可以看到对数似然确实在不断上升。

每个文本的主题分布保存在DocTopicDistribution.csv文件中。每个主题的单词分布保存在TopicWordDistribution.csv文件中。每个主题中出现概率最高的9个单词保存在topics.txt文件中,如下图所示。可以看到出现概率最高的单词分别为astatine, network, Associate_in_Nursing, algorithm,分别对应了物理学、计算机科学、统计学、数学四个领域。这证明了PLSA方法的有效性。

项目开源

本项目开源在kungfu-crab/PLSA: A python implementation for PLSA(Probabilistic Latent Semantic Analysis) using EM algorithm. (github.com),仅作为学习交流使用,禁止转载与抄袭。

参考文献

[1] Hofmann, T. (1999). Probabilistic Latent Semantic Analysis. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (pp. 289-296). Morgan Kaufmann Publishers Inc.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/298107.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

嵌入式(五)通信协议 | 串行异步同步 UART SPI I2C 全解析

文章目录 0 串口通信协议1 通用异步收发传输器 UART1.1 串口配置1.2 串口初始化1.3 串口发送和接收方式1.3.1 轮询方式发送1.3.2 中断方式发送1.3.3 查询方式接收1.3.4 中断方式接收 2 串行外设接口 SPI2.1 标准的四线SPI接口2.2 SPI的四种模式2.3 配置2.4 发送和接收Master向S…

[python]gym安装报错ERROR: Failed building wheel for box2d-py

报错截图: box2d是一个游戏领域的2D图形C引擎,用来模拟2D刚体物体运动和碰撞。 swig是一个将c/c代码封装为Python库的工具(是Python调用c/c库的一种常见手段),所以在运行时box2d会依赖到swig。而swig并不是一个python库…

C#,简单选择排序算法(Simple Select Sort)的源代码与数据可视化

排序算法是编程的基础。 常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。本文搜集发布四种算法…

港口车路协同系统方案

目前,国内自动驾驶应用的两种主流路线是单车智能、单车智能V2X。国内多数港口仍采用4G通信技术,单车智能在港口应用的稳定性较差,比如可能受到金属集装箱干扰及移动通信速率不稳定的影响。单车智能V2X将降低对通信速率的要求,可以…

【BCC动态跟踪PostgreSQL】

BPF Compiler Collection (BCC)是基于eBPF的Linux内核分析、跟踪、网络监控工具。其源码存放于GitCode - 开发者的代码家园 想要监控PostgreSQL数据库的相关SQL需要在编译PostgreSQL的时候开启dtrace。下文主要介绍几个和PostgreSQL相关的工具,其他工具可根据需求自行了解。 …

移动通信原理与关键技术学习(第四代蜂窝移动通信系统)

前言:LTE 标准于2008 年底完成了第一个版本3GPP Release 8的制定工作。另一方面,ITU 于2007 年召开了世界无线电会议WRC07,开始了B3G 频谱的分配,并于2008 年完成了IMT-2000(即3G)系统的演进——IMT-Advanc…

Leetcode 剑指 Offer II 060. 前 K 个高频元素

题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 给定一个整数数组 nums 和一个整数 k ,请返回其中出现…

缘分的计算

题目描述: 缘分是一个外国人难以理解的中文名词。大致说来,缘分是一种冥冥中将两人(通常是情人)结合的力量。仅管这是种迷信,很多人——特别是女生——喜欢去计算它。 不幸的是,644 也是这样。有天&#x…

【linux笔记】top、ps

【linux笔记】top命令 top(Table of process)是动态变化的。而ps是静态的。 PID — 进程id USER — 进程所有者 PR — 进程优先级 NI — nice值。负值表示高优先级,正值表示低优先级 VIRT — 进程使用的虚拟内存总量,单位kb。VI…

二叉树的最大深度,力扣

目录 题目地址: 题目: 我们直接看题解吧: 快速理解题解小建议: 审题目事例提示: 解题方法: 解题方法分析: 方法1后序遍历(DFS) 解题分析: 解题思路&#xff1…

启动 Mac 时显示闪烁的问号

启动 Mac 时显示闪烁的问号 如果启动时在 Mac 屏幕上看到闪烁的问号,这意味着你的 Mac 无法找到自身的系统软件。 如果 Mac 启动时出现闪烁的问号且无法继续启动,请尝试以下步骤。 1.通过按住其电源按钮几秒钟来关闭 Mac。 2.按一下电源按钮&#xf…

强化学习5——动态规划初探

动态规划具体指的是在某些复杂问题中,将问题转化为若干个子问题,并在求解每个子问题的过程中保存已经求解的结果,以便后续使用。实际上动态规划更像是一种通用的思路,而不是具体某个算法。 在强化学习中,被用于求解值函…

华为MDC610接口说明

1、MDC610对外功能接口 2、1、MDC610硬件技术规格

前端插件库-VUE3 使用 vue-codemirror 插件

VUE3 插件 vue-codemirror 使用步骤和实例、基于 CodeMirror ,适用于 Vue 的 Web 代码编辑器。 第一步:安装 vue-codemirror & codemirror 包 , 以及语言包 npm install codemirror --save npm install vue-codemirror --savenpm insta…

Linux第13步_安装“vim编辑器”及应用介绍

学习“磁盘重新分区”后,嵌入式Linux系统环境搭建进入安装“vim编辑器”这个环节。vim编辑器可以用来修改文件,在后期使用中,会经常用到。 1、安装“vim编辑器” 输入“sudo apt-get install vim回车”,就可以执行安装“vim编辑…

SpringIOC之support模块ContextTypeMatchClassLoader

博主介绍:✌全网粉丝5W+,全栈开发工程师,从事多年软件开发,在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战,博主也曾写过优秀论文,查重率极低,在这方面有丰富的经验✌ 博主作品:《Java项目案例》主要基于SpringBoot+MyBatis/MyBatis-plus+…

【Bootstrap学习 day11】

Bootstrap5字体图标 字体图标是在Web项目中使用的图标字体。 使用字体图标的好处是,可以通过应用CSS color属性来创建任何颜色的图标。此外,要更改图标的大小,只需使用CSS font-size属性即可。 获取字体图标 在网页中包含Bootstrap5图标的最…

opencv图像金字塔

下采样&#xff1a; #include <opencv2/opencv.hpp> #include <iostream>int main() {// 读取图像cv::Mat src cv::imread("C:/Users/10623/Pictures/adf4d0d56444414cbeb809f0933b9214.png");if (src.empty()) {std::cout << "无法加载图像…

【非关系型数据库】Redis概述及安装、命令使用

目录 前瞻 关系型数据库 非关系型数据库 关系型数据库和非关系型数据库区别 数据存储方式不同 扩展方式不同 对事务性的支持不同 非关系型数据库产生背景 总结 Redis简介 什么是Redis Redis具有的优点 Redis使用场景 哪些数据适合放入缓存中&#xff1f; Redis为什…

nodejs01

nodejs作用 Node.js 是一个免费的、开源的、跨平台的 JavaScript 运行时环境&#xff0c;允许开发人员在浏览器之外编写命令行工具和服务器端脚本. 是javascript的一个运行环境&#xff0c;&#xff0c;&#xff0c; nodejs stream 是前端工程化的基础 nodejs可以作为中间层&…