Efficient and Distributed Generalized Canonical Correlation Analysis for Big Multiview Data
Efficient and Distributed Generalized Canonical Correlation Analysis for Big Multiview Data
复制标题
DOI：
10.1109/tkde.2018.2875908
复制
发表时间：
2019-12
影响因子：
8.9
通讯作者：
Xiao Fu;Kejun Huang;E. Papalexakis;H. Song;P. Talukdar;N. Sidiropoulos;C. Faloutsos;Tom M. Mitchell
中科院分区：
文献类型：
--
作者：
Xiao Fu;Kejun Huang;E. Papalexakis;H. Song;P. Talukdar;N. Sidiropoulos;C. Faloutsos;Tom M. Mitchell
广义典型相关分析（GCCA）集成了从多个特征空间（或“视图”）获取的数据样本中的信息，以产生低维表示-这是经典的两视图CCA的扩展。自20世纪60年代以来，由于其在数据分析中的重要性，（G）CCA在统计学，机器学习和数据挖掘中引起了广泛的关注。尽管做出了这些努力，现有的GCCA算法仍存在严重的复杂性问题。现有算法的存储器和计算复杂度通常分别作为问题维度（样本/特征的数量）的二次和三次函数增长-例如，使用$\approx \！\！处理视图1，000 $1，000个使用这种算法的功能已经占用了$\approx \！\！10^6 $106内存，每次迭代的复杂度为$\approx\！\！10^9 $109次失败-这使得很难进一步推动这些方法。为了规避这些困难，我们首先提出了一个GCCA算法，其内存和计算成本分别在问题维度和非零数据元素的数量上线性扩展。因此，该算法可以很容易地处理非常大的稀疏视图，其样本和特征维度都超过$\approx\！\！十万块十万块。我们的第二个贡献在于提出了两个分布式算法GCCA，并行计算不同的视图的规范组件，从而可以进一步减少运行时显着，如果多个计算代理可用。我们提供了详细的收敛性分析所提出的算法，并表明，所有的大规模GCCA算法收敛到Karush-Kuhn-Tucker（KKT）点至少次线性。设计合理的合成和真实数据的实验来展示所提出的算法的有效性。
Generalized canonical correlation analysis (GCCA) integrates information from data samples that are acquired at multiple feature spaces (or ‘views’) to produce low-dimensional representations—which is an extension of classical two-view CCA. Since the 1960s, (G)CCA has attracted much attention in statistics, machine learning, and data mining because of its importance in data analytics. Despite these efforts, the existing GCCA algorithms have serious complexity issues. The memory and computational complexities of the existing algorithms usually grow as a quadratic and cubic function of the problem dimension (the number of samples / features), respectively—e.g., handling views with $\approx \!\!1,000$≈1,000 features using such algorithms already occupies $\approx \!\!10^6$≈106 memory and the per-iteration complexity is $\approx\!\!10^9$≈109 flops—which makes it hard to push these methods much further. To circumvent such difficulties, we first propose a GCCA algorithm whose memory and computational costs scale linearly in the problem dimension and the number of nonzero data elements, respectively. Consequently, the proposed algorithm can easily handle very large sparse views whose sample and feature dimensions both exceed $\approx\!\! 100,000$≈100,000. Our second contribution lies in proposing two distributed algorithms for GCCA, which compute the canonical components of different views in parallel and thus can further reduce the runtime significantly if multiple computing agents are available. We provide detailed convergence analyses of the proposed algorithms and show that all the large-scale GCCA algorithms converge to a Karush-Kuhn-Tucker (KKT) point at least sublinearly. Judiciously designed synthetic and real-data experiments are employed to showcase the effectiveness of the proposed algorithms.