今天我在水木想找找fervvac (高远)发的帖子,无意间找到了这篇文章。
fervvac是我的偶像,我向他学习,要努力并且低调,帮助别人。
生活的快乐也许就是,在下班时往家赶的时候,家里人在分别了一天之后再次团聚,其乐融融。
---------------------------------------------------------------------------------------
发信人: pennyliang (pennyliang), 信区: SearchEngineTech
标 题: 稀疏向量的计算方法
发信站: 水木社区 (Sun Mar 16 09:09:12 2008), 站内
鉴于很多网友来信问此问题,我一并答复一下。
首先,我们来看什么是向量计算
假定向量A:{x1,x2,....xn}
向量B:{y1,y2,....yn}
现在要想知道A*B=?(这里的*为向量的点乘)
最直接的计算方法就是 x1*y1+x2*y2+...xn*yn (这里的*为一般乘法)
这里假定乘法和加法代价相同,浮点计算不被考虑,这样的计算方法代价为2N-1
次计算。N为向量维度。
然而,在实际环境中,N很大可能上百万,甚至亿万,而向量中大部分元素为0,
因此0和0相乘是没有意义的。
于是第一个优化的想法是将向量变为这样的模式
向量A:{<x1',loc1'>,<x2',loc2'>...<xn',locn'>}
向量B:{<y1',loc1'>,<y2',loc2'>...<yn',locn'>},这里locx表示元素的位置信
息。
每个向量都不含零元素,或者接近于零的浮点数。显然向量数量远小于n,且向
量A,B的长度取决于各自的非零元,不妨设向量A长度为m,向量B长度为n.
那么计算A*B,可以采用在向量A中循环,在向量B中二分的方法,例如找到向量A
的首原素,<x1',loc1'>,将其位置loc1'在向量B中折半查找,直到找到,或者失
败。
这样计算代价为mlogn + min(m,n),前部为查找代价,后部为加法代价,加法代
价必然比min(m,n)还要小,最大情况下为min(m,n)-1。
进一步来看,如果在计算向量A和向量B乘法时,我们已经知道了它们各自的长
度,那么可以在小的向量上循环,在大向量上二分,这样代价为min(m,n)log(max
(m,n))+min(m,n)
当然也可以不使用二分,采用哈希,假定认为哈希的代价为O(1),那么总代价为
2min(m,n)这里创建哈希也需要代价。
至此,我们由原来2N-1的计算,降低到2min(m,n),
如果N极大,而m,n也不小,这样等待一次向量计算也不短,而如果是矩阵相乘,
向量相乘只是其中的一部,那么速度也无法容忍的话,可以采用并行计算的方法,
通过切分,把一个大计算的一部分派遣到某台机器,而另一部分派遣到另一台机
器,最后综合计算结果。并行处理软件包有很多,比如MPI,都可以尝试使用。
本文只讨论思想,不涉及细节,希望给大家带来一些启发。最后我再次推销一
下这几个思想
precomputing
caching
mirroring
distributing
once-computing
有了难题都从这几个方面考虑,就有解了。。。
--
硕士要啥自行车啊
发信人: fervvac (高远), 信区: SearchEngineTech
标 题: Re: 稀疏向量的计算方法
发信站: 水木社区 (Sun Mar 16 12:40:08 2008), 站内
Nice article. Just add a few comments
1) An importnt property is that dimensions are sorted according to a
global
order and all sparse vectors encoded in that order as well. Therefore,
the
plain binary search * m times (m < n) is redundant in that the key to
probe in
the other vector is monotonically increasing. A simple rememdy is to
keep
a bookmark of the last matching position (if no match, the largest i
s.t v[i]
<x) and the next binary search only need to be done within v[i+1, |v|].
This can be viewed as a nice marriage of index-based and merge-based
approaches.
More sophisticated methods and their analysis can be found in
http://www.cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf
http://siam.org/proceedings/alenex/2007/alx07_008sandersp.pdf
2) many application actually only want those <x, y> >= t, where t is a
threhsold
(e.g., near duplicate detection)
If the vector is of binary type (only 0 or 1), prefix filtering can be
used to
consider only those pairs s.t. their intersection (in binary case, <x,
y> is
intersection) *may* exceed t.
In the general case, one can keep tract of the maximum value among the
suffix
of the vector and use it to prune candidate pairs.
For more details, see
http://www2007.org/papers/paper342.pdf
(they've also published their source code)
分享到:
相关推荐
支持向量回归机是一种解决回归问题的重要方法,其预测速度与支持向量的稀疏性成正比。为了改进支持向量回归机的稀疏性,提出了一种直接稀疏支持向量回归算法DSKR(Direct Sparse Kernel Support Vector Regression)...
基于稀疏贝叶斯学习的稀疏向量恢复算法,里面包含多个情景下的仿真程序和说明
稀疏表达:向量、矩阵与张量
通过正交匹配追踪算法,实现迭代得到稀疏向量
稀疏矩阵 设矩阵A mn 中有s个非零元素,若s远远小于矩阵元素的... 将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素),并依次存放在向量中,这种稀疏矩阵的顺序 存储结构称为三元组表。
稀疏矩阵向量乘的FPGA设计与实现.pdf
网络游戏-训练神经网络的方法和装置以及确定稀疏特征向量的方法.zip
学了一个学期的java,什么都没懂··做了这个课程设计后才有点了解,所以希望能帮助像我一样的人···
使用稀疏贝叶斯相关向量机方法对数据进行优化处理,
作为典型的不规则算法,稀疏矩阵向量乘的计算过程具有非常低的访存局部性和计算访存比,因此在基于cache的通用处理器上计算效率很低。提出了一种面向可重构计算平台的基于IEEE-754浮点数据格式标准的稀疏矩阵向量乘...
根据信道补偿后的说话人i-向量的均值向量估计其信道偏移空间,在该空间采用主成分分析方法提取低维信道偏移主分量,用于重新计算说话人i-向量,从而达到进一步抑制i-向量中信道干扰的目的;将新的i-向量作为字典原子...
java版的 leedcode部分代码,刷题专用,找工作过程中十分有用~
这类应用的本质是模式识别 , 将表征对象主要的或本质的特征构造稀疏向量, 这些特征具有类间的强区分性。利用稀疏表示方法得到这些特征的值, 并根据稀疏向量与某类标准值的距离, 或稀疏向量间的距离判别完成模式...
稀疏表示和支持向量机相融合的非理想环境人脸识别.pdf
矩阵主特征向量(principal eigenvectors computing, PEC)的求解是科学与工程计算中的一个重要问题。随着图形处理单元通用计算(general-purpose computing on graphics processing unit, GPGPU)的兴起, 利用GPU 来...
基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化.pdf
Sparse Bayesian Learning and the Relevance Vector ...2001年的一篇早期资料,论述了贝叶斯框架下的回归与分类问题,并且结合了相关向量机方法进行学习。对于我们今天学习了解贝叶斯理论,SVM,依然有指导作用。
维基百科词向量 sgns.wiki.char.bz2解压后文件后缀名是.char, 可以通过一些方法得到.txt结尾的文件,有35万多个字词和符号,300维的向量表示。将词向量作为词嵌入层时需要加载全部的词向量到内存,如果计算机的内存...
稀疏最小二乘支持向量机及其应用,衷路生,陈立勇,提出基于特征向量选择(FVS)的稀疏最小二乘支持向量机(SLS-SVM)模型,解决最小二乘支持向量机(LS-SVM)稀疏化问题。首先,采用FVS在特征空��
计算机视觉-稀疏表示MATLAB源码 稀疏表示(Sparse Representation)也叫作稀疏编码(Sparse Coding),就是...学习的目标函数是找到所有样本在这些原子的线性组合表示下是稀疏的,即同时估计字典和稀疏表示的系数这两个