《5月10日@实验室《lsi、矩阵分解、cuda技术》》由会员分享，可在线阅读，更多相关《5月10日@实验室《lsi、矩阵分解、cuda技术》（20页珍藏版）》请在金锄头文库上搜索。
1、2012年年5月月10日日实验实验室室LSI、矩阵分解、矩阵分解、CUDA技术技术讲个例子，看看理解对不对Cite:http:/ (Latent Semantic Indexing)隐语义索引隐语义索引 设Doc1,Doc2,Doc3是三个文件.一些术语在这三个文件中的出现情况如下表:Doc1Doc2Doc3-accessX document XretrievalXXinformationX*X*theoryXdatabaseXindexingXcomputerX*X*-这里,假定用information和computer作为主题词进行检索,那么Doc2和Doc3与之精确匹配,因而中选.然而,
2、Doc2是用户并不想要的文件,Doc1才是想要的查不出来.问题：由于一词多义,基于精确匹配的检索算法会报告许多用户不要的东西;由于一义多词,基于精确匹配的检索算法又会遗漏许多用户想要的东西。3继续继续1首先,以术语(terms)为行,文件(documents)为列做一个大矩阵(matrix).设一共有t行d列,矩阵名为X.矩阵的元素为术语在文件中的出现频度.数学上可以证明:X可以分解为三个矩阵T0,S0,D0(D0的转置)的积.其中T0和D0的列向量都是正交归一化的,S0是对角矩阵.T0是t*m矩阵,S0是m*m矩阵,D0是d*m矩阵,m是X的秩.这种分解叫做单值分解(singlarvalue
3、decomposition,简称SVD).X=T0*S0*D0一般要求T0,S0,D0都是满秩的.不难做到把S0的元素沿对角线从大到小排列.现在,把S0的m个对角元素的前k个保留,后m-k个置0,我们可以得到一个新的近似的分解:Xhat=T*S*DXhat在最小二乘意义(?)下是X的最佳近似!这样,我们实际上有了一个降维的途径4继续继续2(?)1.做“正向”乘法:Xhat * Xhat = T * S * D * D * S * T = T * S2 * T(D * D = I, 因为D已经是正交归一的). 它的第i行第j列表明了术语i和j的相似程度.2.做“逆向”乘法:Xhat * Xhat
4、 = D * S * T * T * S * D = D * S2 * D(T * T = I, 因为T已经是正交归一的). 它的第i行第j列表明了文件i和j的相似程度.3.比较一个文件和一个术语恰巧就是Xhat本身. 它的第i行第j列表明了术语i和文件j的相关联程度. Application:可以把主题词的集合认为是一个虚拟的文件.查询的任务说白了是把这个虚拟的文件和其他文件做相似性比较,挑选最相似的出来(挑选到什么程度打住,要看实际问题的要求）5我的理解我的理解1.把一个大矩阵拆解成简单矩阵2.把两个大矩阵计算变成简单矩阵间的计算6SVD(singlar value decompositi
5、on)NMF(Non-negative Matrix Factorization )Cite:TheRelationshipsAmongVariousNonnegativeMatrixFactorizationMethods.pdf矩阵的三角分解（Cholesky分解、LU分解等）矩阵的正交三角分解(QR分解等)矩阵的满秩分解(?)矩阵的奇异值分解(SVD)Cite:http:/ Linear Algebra Subprograms(Fortran)一个最基础的库，其他软件在对它进行优化ATLASAutomatically Tuned Linear Algebra Software(C and
6、 Fortran)对BALS加强，提供更加灵活的接口LAPACKLinear Algebra PACKage(C and Fortran)对BLAS进行封装，提供专门对矩阵的处理接口比如：matrix factorizations (LU, Cholesky, QR, SVD, Schur, generalized Schur)缺点：慢，调用难CUBLAS NVIDIA CUDA Basic Linear Algebra SubroutinesCUDA版本的基础线性代数库12基于多核多处理器以及机群的数学库基本上是根据硬件对BLAS的进行定制：MKLIntel Math Kernel Libr
7、aryIntel处理器数学库核心ACMLAMD Core Math Library (ACML)AMD处理器数学库核心GotoBLAS2多处理器并行化提高效率 PLASMA多核处理器并行化缺点：还是不够快，没有考虑GPU的优势13基于GPU并行加速的解决方案SVD_1张舒没有源代码QR-SVD 没有源代码赵佳只是个ppt，没有源代码http:/www.nku-isc.org/zhaojia/Fast SVD on Graphics Processors没有源代码http:/gamma.cs.unc.edu/NUMERIC/SVD/ ISVD-CUDA没有源代码http:/ 14基于GPU并行加
8、速的解决方案SVD_2CULA一个商业软件，功能齐全，dense版本是免费CULA是LAPACK的cuda版主要功能：Linear EquationsOrthogonal FactorizationsLeast Squares SolversSymmetric EigenproblemsNonsymmetric EigenproblemsSingular Value DecompositionNote:自己编写代码，可以成功运行缺点：商业软件，无法获得源代码15基于GPU并行加速的解决方案SVD_3MAGMA一个开源软件，功能齐全MAGMA也是LAPACK的cuda版解决:LU, QR, an
9、d Cholesky factorizations SVDEigen and singular value problem Note:需要和ATLAS或者GotoBLAS2搭配使用还没写出矩阵分解程序。接口没搞懂。16基于GPU并行加速的解决方案NMF求解：NMFGPUMLib提供NMF计算，接口不清晰，需摸索NMF-CUDA某个图像研究生的程序，但是功能不清晰修改过代码，可以跑17总结总结软件基本都是Linux安装复杂，依赖关系复杂显然有部分人实现了矩阵分解的CUDA并行化，但是没有公开代码，根据论文描述，似乎还并不太完善。功能丰富的软件例如MAGMA和CULA都有各自不足。商业软件，不开放
10、源代码，无法全面评估，以及适用于研究领域，不具开源优势。MAGMA是开源中做得最好的，但是对别的软件依赖性太强，光是安装就花费了两天时间才摸索出来。没有一个软件能让我们DIY。我们必须借鉴他们的已有做法，从基础库开发，实现CUDA版本。18下一步下一步学习分解算法或者根据一个应用实例，在找到的源代码基础上修改。19Reference:1.Singular Value Decomposition on GPU using CUDA2.LU, QR and Cholesky Factorizations using Vector Capabilities of GPUs3.A GPU-based
11、Approximate SVD Algorithm4.Non-negative Matrix Factorization Implementation Using Graphic Processing Units5.The Relationships Among Various Nonnegative Matrix Factorization Methods6.Non-negative Matrix Factorization on GPU7.Parallel Algorithms for the Singular Value Decomposition8.基于CUDA的矩阵奇异值分解9.推荐系统中的矩阵分解技术进展20
