KMA-α:一个支持向量机核矩阵的近似计算算法

核矩阵计算是求解支持向量机的关键,已有精确计算方法难以处理大规模的样本数据.为此,研究核矩阵的近似计算方法.首先,借助支持向量机的凸二次约束线性规划表示,给出支持向量机和多核支持向量机的二阶锥规划表示.然后,综合Monte Carlo方法和不完全Cholesky分解方法,提出一个新的核矩阵近似算法KMA-α,该算法首先对核矩阵进行Monte Carlo随机采样,采样后不直接进行奇异值分解,而是应用具有对称置换的不完全Cholesky分解来计算接近最优的低秩近似.以KMA-α输出的近似核矩阵作为支持向量机的输入,可提高支持向量机二阶锥规划求解的效率.进一步,分析了KMA-α的算法复杂性,证明了KMA-α的近似误差界定理.最后,通过标准数据集上的实验,验证了KMA-α的合理性和计算效率.理论分析与实验结果表明,KMA-α是一合理、有效的核矩阵近似算法.