Randomized Iterative Algorithms for Fisher Discriminant Analysis
Randomized Iterative Algorithms for Fisher Discriminant Analysis
复制标题
DOI：
--
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Agniva Chowdhury;Jiasen Yang;P. Drineas
中科院分区：
文献类型：
--
作者：
Agniva Chowdhury;Jiasen Yang;P. Drineas
Fisher判别分析（FDA）是一种广泛使用的分类和降低方法的方法。当预测变量的数量大大超过观测值的数量时，常规FDA的替代方案之一是正规的Fisher判别分析（RFDA）。在本文中，我们提出了一种简单的，迭代的基于草图的RFDA算法，与传统方法相比，它具有可证明的准确性保证。我们的分析基于两个简单的结构结果，这些结果归结为随机矩阵乘法，这是对随机线性代数的基本和良好理解的原始原始。我们分析了当脊杠杆率和标准杠杆分数用于选择预测变量时，RFDA的行为，我们证明可以通过样本来实现准确的近似值，该样品的大小取决于RFDA问题的有效自由度。我们的结果对现有方法产生了重大改进，我们的经验评估支持我们的理论分析。
Fisher discriminant analysis (FDA) is a widely used method for classification and dimensionality reduction. When the number of predictor variables greatly exceeds the number of observations, one of the alternatives for conventional FDA is regularized Fisher discriminant analysis (RFDA). In this paper, we present a simple, iterative, sketching-based algorithm for RFDA that comes with provable accuracy guarantees when compared to the conventional approach. Our analysis builds upon two simple structural results that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized linear algebra. We analyze the behavior of RFDA when the ridge leverage and the standard leverage scores are used to select predictor variables and we prove that accurate approximations can be achieved by a sample whose size depends on the effective degrees of freedom of the RFDA problem. Our results yield significant improvements over existing approaches and our empirical evaluations support our theoretical analyses.