Improved Bounds on the Dot Product under Random Projection and Random Sign Projection
Improved Bounds on the Dot Product under Random Projection and Random Sign Projection
复制标题
随机投影和随机符号投影下点积的改进界限
DOI：
10.1145/2783258.2783364
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Kabán
中科院分区：
文献类型：
--
作者：
A. Kabán
点积是数据挖掘算法中的一个重要组成部分，在分类、回归、相关聚类、信息检索等领域都有广泛的应用。当数据是高维的时，随机投影的使用可以用作提供低失真保证和计算节省两者的通用维度缩减方法。然而，与已知的关于保持欧几里得距离的最佳保证相反，参见Johnson-Lindenstrauss引理，在当前的数据挖掘和机器学习文献中，现有的关于随机投影下的点积的保证是松散和不完整的。最近的一些文献甚至提出，当原始向量之间的角度为钝角时，可能无法保留点积。本文给出了点积在随机投影下的改进的上界，它与欧氏距离的最优上界相匹配。作为推论，我们阐明了在随机投影下，原始向量之间的角度对点积的相对失真的影响，并且我们表明钝角与锐角以相同的方式对称地表现。在进一步的推论，我们作出了一个链接到符号随机投影，在那里我们推广了早期的结果。数值模拟验证了理论解析的结果.最后，我们将所得结果应用于边界损失下压缩线性分类器的泛化误差界。
Dot product is a key building block in a number of data mining algorithms from classification, regression, correlation clustering, to information retrieval and many others. When data is high dimensional, the use of random projections may serve as a universal dimensionality reduction method that provides both low distortion guarantees and computational savings. Yet, contrary to the optimal guarantees that are known on the preservation of the Euclidean distance cf. the Johnson-Lindenstrauss lemma, the existing guarantees on the dot product under random projection are loose and incomplete in the current data mining and machine learning literature. Some recent literature even suggested that the dot product may not be preserved when the angle between the original vectors is obtuse. In this paper we provide improved bounds on the dot product under random projection that matches the optimal bounds on the Euclidean distance. As a corollary, we elucidate the impact of the angle between the original vectors on the relative distortion of the dot product under random projection, and we show that the obtuse vs. acute angles behave symmetrically in the same way. In a further corollary we make a link to sign random projection, where we generalise earlier results. Numerical simulations confirm our theoretical results. Finally we give an application of our results to bounding the generalisation error of compressive linear classifiers under the margin loss.