面向线性模型的矩阵压缩算法研究及其应用

论文摘要

爆炸式的数据增长对于信息化时代来说是一柄双刃剑,大规模数据矩阵带来大量信息的同时,也增加了计算机的存储压力和带宽压力,给数据存储以及机器学习模型的优化效率带来了很大的挑战。因而,对大规模数据矩阵进行有效压缩,并设计基于压缩形式的压缩矩阵操作是解决这项挑战的关键技术。研究发现,用于机器学习的大规模数据矩阵存在较大的压缩潜力,但通用的压缩软件以及支持SpMV（Sparse Matrix Vector Multiplication）的稀疏矩阵压缩算法均不能很好地解决这一问题。因此,有必要研究支持高效随机访问矩阵行与列的实数矩阵压缩算法及压缩矩阵操作,并将其应用于线性模型。本文提出了一种支持高效随机访问矩阵行与列的无损实数矩阵压缩算法COMC（Column-oriented Matrix Compression）,该算法采用基于列的压缩框架,对矩阵每列进行两层结构的压缩。第一层使用字典编码,将列中高频出现的元素映射成较小的整数,从而实现逻辑层的压缩,将逻辑层的输出矩阵称为字典码矩阵;第二层使用整数编码,对字典码矩阵进行比特层的编码,比特层输出压缩矩阵与辅助信息。COMC算法充分利用了用于机器学习的大规模数据矩阵的普遍特征,从轻量级压缩的角度出发,有效地平衡了压缩率与解压缩效率。本文提出了随机访问矩阵行AccessR（k）与列AccessC（k）算法,支持COMC压缩矩阵上高效的压缩矩阵操作,并在访问算法中应用了SIMD（Single Instruction Multiple Data）指令,进一步实现了访问算法的加速。在简单线性回归模型和逻辑回归模型等线性模型的优化过程中,计算量主要集中于矩阵操作a?X,vT?X和X?v等。由此,本文实现了COMC压缩矩阵上高效的压缩矩阵操作a?C,vT?C和C?v等,并进一步实现了以压缩矩阵操作为主要计算量的压缩简单线性回归模型和压缩逻辑回归模型的优化。通过随机访问矩阵行与列,在不完全解码整个矩阵的情况下,完成了COMC压缩矩阵上的压缩矩阵操作a?C,vT?C和C?v等。压缩简单线性回归模型和压缩逻辑回归模型以COMC压缩矩阵C为输入样本,通过随机访问矩阵行与列,实现压缩矩阵操作,进一步实现模型系数的优化过程。本文对比了COMC算法,通用压缩软件以及支持SpMV的稀疏矩阵压缩算法,在压缩率,解压缩效率,压缩矩阵操作效率以及压缩线性模型优化效率上,对上述算法性能进行了评价与分析。实验结果表明,综合考量压缩率与解压缩效率,COMC算法表现较好,且由于支持高效随机访问矩阵行与列,而在压缩矩阵操作中更具备灵活性。进一步从压缩矩阵操作效率和压缩线性模型优化效率两方面分析,COMC算法能够较好的平衡压缩率与压缩矩阵操作效率和压缩线性模型优化效率,因此,COMC算法可作为压缩线性模型的一个较好的压缩方案。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 研究现状
•     1.2.1 线性模型
•     1.2.2 矩阵压缩
•   1.3 问题定义及本文工作
•     1.3.1 问题定义
•     1.3.2 本文工作
• 第二章 预备知识
•   2.1 线性模型
•   2.2 SIMD指令
•   2.3 本章小结
• 第三章 矩阵压缩与随机访问
•   3.1 算法整体框架
•   3.2 矩阵压缩算法COMC
•   3.3 矩阵随机访问
•     3.3.1 访问矩阵列
•     3.3.2 访问矩阵行
•   3.4 算法性能分析
•   3.5 本章小结
• 第四章 压缩矩阵操作与压缩线性模型
•   4.1 压缩矩阵操作及性能分析
•   4.2 压缩线性模型及性能分析
•   4.3 本章小结
• 第五章 实验结果与分析
•   5.1 实验环境与数据源
•   5.2 算法性能
•     5.2.1 COMC与通用压缩软件性能对比
•     5.2.2 COMC与稀疏矩阵压缩算法性能对比
•   5.3 压缩矩阵操作性能
•   5.4 压缩线性模型性能
•   5.5 本章小结
• 第六章 总结与展望
•   6.1 总结
•   6.2 展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 包梦雪

导师: 霍红卫

关键词: 无损压缩,字典编码,整数编码,随机访问,压缩矩阵操作,压缩线性模型

来源: 西安电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 西安电子科技大学

分类号: TP181;O157.4

DOI: 10.27389/d.cnki.gxadu.2019.001927

总页数: 84

文件大小: 2632K

下载量: 51