典型相关分析(CCA)是一种线性表示学习方法,用于在多视图数据中寻找最大相关变量。非线性CCA将这一概念扩展到更广泛的转换族,这对于许多实际应用来说更加强大。给定联合概率,交替条件期望(ACE)为非线性CCA问题提供了最优解。然而,当仅有有限数量的观测可用时,它遭受有限的性能和增加的计算负担。在这项工作中,我们引入了一个信息理论框架,用于线性CCA问题(ITCCA),它扩展了传统的ACE方法。 Oursuggested框架寻求压缩的数据表示,允许最大程度的相关性。这样我们就可以控制表现的灵活性和复杂性之间的权衡。与有限样本体系中的非线性替代方案相比,我们的方法在减少的计算负担方面表现出有利的性能。此外,ITCCA提供理论界限和最优性条件,因为我们建立了与速率失真理论,信息瓶颈和远程信息编码的基本联系。此外,它意味着“软”维数降低,因为压缩水平是由原始噪声数据和我们提取的信号之间的相互信息测量(和控制)的。
translated by 谷歌翻译
集合方法属于最先进的预测建模方法。应用于现代大数据,这些方法通常需要大量的子学习者,其中每个学习者的复杂性通常随着数据集的大小而增长。这种现象导致对存储空间的需求增加,这可能是非常昂贵的。这个问题主要体现在基于asubscriber的环境中,其中用户特定的集合需要存储在具有严格存储限制的个人设备(例如蜂窝设备)中。在这项工作中,我们介绍了一种基于树的集合方法的无损压缩的新方法,重点是随机森林。我们建议的方法是基于整体树的概率建模,然后是通过Bregman散度的模型聚类。这使我们能够找到一组最小的模型,这些模型提供了树的准确描述,同时又足够小以便存储和维护。我们的压缩方案展示了各种现代数据集的高压缩率。重要的是,我们的方案能够从压缩格式预测并完美重建原始集合。此外,我们引入了一种理论上合理的有损压缩方案,它允许我们控制在失真和编码率之间的权衡。
translated by 谷歌翻译
独立成分分析(ICA)是一种统计工具,可将观察到的随机向量分解为尽可能统计独立的成分。有限域上的ICA是ICA的一个特例,其中观察和分解的分量都取有限字母表中的值。这个问题也称为最小冗余表示或因子编码。在这项工作中,我们专注于有限域上ICA的线性方法。我们引入一个基本的下界,它为任何线性解决方案解决这个问题的能力提供了基本的限制。基于此界限,我们提出了优于所有当前已知方法的协议算法。重要的是,随着问题规模的扩大,我们建议的算法(与下限相比)的开销通常会降低。此外,我们提供了我们建议的方法的次优变体,以相对较小的性能成本显着降低了计算复杂度。最后,我们讨论了与现有非线性解相比,随机向量的线性变换的通用能力。
translated by 谷歌翻译
大型微阵列数据的可用性导致过去十年中对聚类方法的兴趣日益增加。已经提出了几种算法来根据不同的相似性措施和在不同的约束条件下识别基因和条件的子集。在本文中,我们关注基因表达数据集的排他性双聚类问题,其中每一行只能是单个双聚类的成员,而列可以参与多个聚类。这种类型的双聚类可能是足够的,例如,用于聚集癌症患者组,其中预期每个患者(行)仅患有单一类型的癌症,而每种癌症类型与多个(并且可能重叠的)基因(列)相关联。我们提出了一种新方法,通过结合现有的双聚类算法和组合拍卖技术来识别这些独有的行双聚类。根据Gap统计方法的精神,基于与空模型的比较,我们设计了一种调整算法阈值的方法。我们在合成和现实基因表达数据上展示了我们的方法,并展示了它在识别大跨度非重叠行子矩阵时的能力,同时考虑了它们的独特性质。 Gap统计方法成功地在我们的所有示例中识别适当的阈值。
translated by 谷歌翻译
独立分量分析(ICA)是一种统计方法,用于将可观察的多维随机向量转换为彼此尽可能独立的分量。通常,ICA框架假设一个模型,根据该模型生成观察结果(例如带加性噪声的线性变换)。有限域上的ICA是ICA的一个特例,其中观察和独立分量都在有限字母表上。在本文中,我们考虑了有限域情形的一个公式,其中观察向量被分解为其独立的成分(尽可能多),而在生成它的过程中没有先验假设。这种概括也称为Barlow的最小冗余表示,被认为是一个开放的问题。我们提出了几个定理,并表明这个难题可以用Branchand绑定搜索树算法准确地解决,或者用一系列线性问题紧密地近似。此外,我们表明存在一个简单的变换(即,顺序置换),它提供了最优解的贪婪但非常有效的近似。我们进一步表明,虽然不是每个随机向量都可以有效地分解成独立的组件,但是随着维数的增加,绝大多数向量确实很好地分解(即,在小的恒定成本内)。此外,我们表明我们可以实际上实现这种有利的恒定成本,其复杂性在字母表大小上是偶然线性的。我们的贡献为理论和计算保证提供了巴洛问题的第一套解决方案。最后,我们在多源编码应用程序中演示了我们建议的框架。
translated by 谷歌翻译