因式分解

在数学中,把一个数学因子(比如数字,多项式,或矩阵)分解其他数学因子的乘积。比如:整数15可以分解成两个质数3和5的乘积,一个多项式x^2 -4 可被因式分解为(x+2)(x-2)。

来源:Wikipedia
简介

在数学中,把一个数学因子(比如数字,多项式,或矩阵)分解其他数学因子的乘积。比如:整数15可以分解成两个质数3和5的乘积,一个多项式x^2 -4 可被因式分解为(x+2)(x-2)。

因子分解的目标通常是为了将复杂数学式简化到不能再分解的形式。因子分解可以分为整数分解和因式分解(多项式分解)。其中,大整数的分解是公钥加密算法的安全基础,比如RSA。因式分解的定理为:数域F上每个次数≥1的多项式f(x)都可以分解成数域F上一些不可约多项式的乘积,并且分解是唯一的,即如果有两个分解式f(x)=p1(x)p2(x)•••ps(x)=q1(x)q2(x)•••qt(x),

其中pi(x) (i=1, 2, ••• ,s)和qj(x) (j=1, 2, ••• ,t)都是数域F上的不可约多项式,那么必有s=t,而且可以适当排列因式的次序,使得pi(x)=ciqi(x)(i=1, 2, ••• ,s),其中ci(i=1, 2, ••• ,s)是一些非零常数。

此外,还有矩阵分解,将复杂矩阵分解成特殊矩阵的乘积形式,应用起来更加方便。

[描述来源:Wiki;URL:https://en.wikipedia.org/wiki/Factorization]

在机器学习中,有多种因子分解的模型,比如矩阵分解,平行因子分析,以及一些用于解决特定问题的因子分解模型(如SVD++, PITF和FPMC等)。这些模型通常不具有普适性。此外,还有因子分解机。它是一种融合了支持向量机优点的因子分解模型,可以处理任何实值特征向量,能够估计特征分量之间的相互作用关系,即使是在处理具有巨大稀疏性(比如推荐系统)的问题时也可以使用。

[描述来源:论文 Factorization Machines;URL:https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf]

发展历史

描述

Vera Sanford在她的'A Short History of Mathematics (1930)'中指出,“在求解二次方程的方法中,因式分解直到1631才在Harriot的工作中被用到,而且作者还忽视了负数根形式的分解。” 也有文章指出其实Harriot解出了正负根但是编辑在书中没有提及这一点。现代方法做因式分解运算快且高效,但是要用到复杂的数学思想。因子分解技术现在主要应用于计算机线性代数系统中,在机器学习中也被引入,比如因子分解机等。

主要事件

年份事件相关论文/Reference
1631Harriot的书被出版,其中论述了采用因式分解来解二次方程的方法Harriot, T. Artis analyticae praxis: ad æquationes algebraïcas nouâ, expedit â, & generali methodo, resoluendas. apud Robertvm Barker, typographium regium: et hæred. Io. Billii.
1999Lee, Daniel D.和 H. Sebastian Seung提出一种非负矩阵分解方法来学习面部或者文本语义特征Lee, D. D., & Seung, H. S. (1999). Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755), 788-791.
2005将非负张量分解方法用于统计和计算机视觉中Shashua, A., & Hazan, T. (2005, August). Non-negative tensor factorization with applications to statistics and computer vision. In Proceedings of the 22nd international conference on Machine learning (pp. 792-799). ACM.
2010Steffen Rendle提出一种基于矩阵分解的机器学习算法:因子分解机Rendle, S. (2010, December). Factorization machines. In Data Mining (ICDM), 2010 IEEE 10th International Conference on (pp. 995-1000). IEEE.
2013在深度神经网络的最后一个权重层中采用矩阵分解,可以减小训练模型的参数总量Sainath, T. N., Kingsbury, B., Sindhwani, V., Arisoy, E., & Ramabhadran, B. (2013, May). Low-rank matrix factorization for deep neural network training with high-dimensional output targets. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on (pp. 6655-6659). IEEE.

3. 发展分析

瓶颈

在面对大稀疏矩阵问题时,基本的因子分解方法往往无法分析各个特征向量之间的相互关系,算法复杂度高,导致计算速度慢以及效率低下。

未来发展方向

利用因子分解机解决大规模稀疏数据下的特征组合问题

相关人物
Daniel D. Lee
Daniel D. Lee
H Sebastian Seung
H Sebastian Seung
Steffen Rendle
Steffen Rendle
简介
相关人物