通过潜在树形图形模型建模高维数据的分布是多个科学域中的一种普遍存在的方法。常见的任务是推断底层树结构,仅给出其终端节点的观察。树恢复的许多算法是计算密集型的,这将其适用于中等大小的树木。对于大树,一种共同的方法,被称为剥夺和征服,是以两步恢复树结构。首先,将结构分别恢复终端节点的多个可能随机子集。其次,合并生成的子树以形成一棵树。在这里,我们开发频谱自上而下的恢复(STDR),确定性分割和征服方法来推断出大潜在树模型。与以前的方法不同,STDR基于与观察到的节点相关的合适的LAPLACIAN矩阵的FIEDLER向量,以非随机方式分配终端节点。我们证明,在某些条件下,这种分区与树结构一致。反过来,这导致了小远子的显着更简单的合并程序。我们证明了STDR在统计上是一致的,并绑定了以高概率准确恢复树所需的样本数量。使用来自近几种常见树模型的模拟数据在系统发育中,我们证明STDR在运行时具有显着的优势,具有改善或类似的准确性。
translated by 谷歌翻译
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain $\textit{subquadratic}$ time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from $\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel graphs, $\textit{simulating random walks}$ on kernel graphs, and $\textit{importance sampling}$ on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in $\textit{sublinear}$ (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.
translated by 谷歌翻译
我们考虑从数据学习树结构ising模型的问题,使得使用模型计算的后续预测是准确的。具体而言,我们的目标是学习一个模型,使得小组变量$ S $的后海报$ p(x_i | x_s)$。自推出超过50年以来,有效计算最大似然树的Chow-Liu算法一直是学习树结构图形模型的基准算法。 [BK19]示出了关于以预测的局部总变化损耗的CHOW-LIU算法的样本复杂性的界限。虽然这些结果表明,即使在恢复真正的基础图中也可以学习有用的模型是不可能的,它们的绑定取决于相互作用的最大强度,因此不会达到信息理论的最佳选择。在本文中,我们介绍了一种新的算法,仔细结合了Chow-Liu算法的元素,以便在预测的损失下有效地和最佳地学习树ising模型。我们的算法对模型拼写和对抗损坏具有鲁棒性。相比之下,我们表明庆祝的Chow-Liu算法可以任意次优。
translated by 谷歌翻译
分层聚类研究将数据集的递归分区设置为连续较小尺寸的簇,并且是数据分析中的基本问题。在这项工作中,我们研究了Dasgupta引入的分层聚类的成本函数,并呈现了两个多项式时间近似算法:我们的第一个结果是高度电导率图的$ O(1)$ - 近似算法。我们简单的建筑绕过了在文献中已知的稀疏切割的复杂递归常规。我们的第二个和主要结果是一个US(1)$ - 用于展示群集明确结构的宽族图形的近似算法。该结果推出了以前的最先进的,该现有技术仅适用于从随机模型产生的图表。通过对合成和现实世界数据集的实证分析,我们所呈现的算法的实证分析表明了我们的工作的重要性,以其具有明确定义的集群结构的先前所提出的图表算法。
translated by 谷歌翻译
社区检测和正交组同步是科学和工程中各种重要应用的基本问题。在这项工作中,我们考虑了社区检测和正交组同步的联合问题,旨在恢复社区并同时执行同步。为此,我们提出了一种简单的算法,该算法由频谱分解步骤组成,然后是彼此枢转的QR分解(CPQR)。所提出的算法与数据点数线性有效且缩放。我们还利用最近开发的“休闲一淘汰”技术来建立近乎最佳保证,以确切地恢复集群成员资格,并稳定地恢复正交变换。数值实验证明了我们算法的效率和功效,并确认了我们的理论表征。
translated by 谷歌翻译
Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.
translated by 谷歌翻译
We consider the problem of learning the structure underlying a Gaussian graphical model when the variables (or subsets thereof) are corrupted by independent noise. A recent line of work establishes that even for tree-structured graphical models, only partial structure recovery is possible and goes on to devise algorithms to identify the structure up to an (unavoidable) equivalence class of trees. We extend these results beyond trees and consider the model selection problem under noise for non tree-structured graphs, as tree graphs cannot model several real-world scenarios. Although unidentifiable, we show that, like the tree-structured graphs, the ambiguity is limited to an equivalence class. This limited ambiguity can help provide meaningful clustering information (even with noise), which is helpful in computer and social networks, protein-protein interaction networks, and power networks. Furthermore, we devise an algorithm based on a novel ancestral testing method for recovering the equivalence class. We complement these results with finite sample guarantees for the algorithm in the high-dimensional regime.
translated by 谷歌翻译
随机奇异值分解(RSVD)是用于计算大型数据矩阵截断的SVD的一类计算算法。给定A $ n \ times n $对称矩阵$ \ mathbf {m} $,原型RSVD算法输出通过计算$ \ mathbf {m mathbf {m} $的$ k $引导singular vectors的近似m}^{g} \ mathbf {g} $;这里$ g \ geq 1 $是一个整数,$ \ mathbf {g} \ in \ mathbb {r}^{n \ times k} $是一个随机的高斯素描矩阵。在本文中,我们研究了一般的“信号加上噪声”框架下的RSVD的统计特性,即,观察到的矩阵$ \ hat {\ mathbf {m}} $被认为是某种真实但未知的加法扰动信号矩阵$ \ mathbf {m} $。我们首先得出$ \ ell_2 $(频谱规范)和$ \ ell_ {2 \ to \ infty} $(最大行行列$ \ ell_2 $ norm)$ \ hat {\ hat {\ Mathbf {M}} $和信号矩阵$ \ Mathbf {M} $的真实单数向量。这些上限取决于信噪比(SNR)和功率迭代$ g $的数量。观察到一个相变现象,其中较小的SNR需要较大的$ g $值以保证$ \ ell_2 $和$ \ ell_ {2 \ to \ fo \ infty} $ distances的收敛。我们还表明,每当噪声矩阵满足一定的痕量生长条件时,这些相变发生的$ g $的阈值都会很清晰。最后,我们得出了近似奇异向量的行波和近似矩阵的进入波动的正常近似。我们通过将RSVD的几乎最佳性能保证在应用于三个统计推断问题的情况下,即社区检测,矩阵完成和主要的组件分析,并使用缺失的数据来说明我们的理论结果。
translated by 谷歌翻译
在本文中,我们提出了一个基于树张量网状状态的密度估计框架。所提出的方法包括使用Chow-Liu算法确定树拓扑,并获得线性系统通过草图技术定义张量 - 网络组件的线性系统。开发了草图功能的新颖选择,以考虑包含循环的图形模型。提供样品复杂性保证,并通过数值实验进一步证实。
translated by 谷歌翻译
在本文中,我们考虑了一个$ {\ rm u}(1)$ - 连接图,也就是说,每个方向的边缘都赋予了一个单位模量复杂的数字,该数字在方向翻转下简单地结合了。当时,组合laplacian的自然替代品是所谓的磁性拉普拉斯(Hermitian Matrix),其中包括有关图形连接的信息。连接图和磁性拉普拉斯人出现,例如在角度同步问题中。在较大且密集的图的背景下,我们在这里研究了磁性拉普拉斯的稀疏器,即基于边缘很少的子图的光谱近似值。我们的方法依赖于使用自定义的确定点过程对跨越森林(MTSF)进行取样,这是一种比偏爱多样性的边缘的分布。总而言之,MTSF是一个跨越子图,其连接的组件是树或周期根的树。后者部分捕获了连接图的角不一致,因此提供了一种压缩连接中包含的信息的方法。有趣的是,当此连接图具有弱不一致的周期时,可以通过使用循环弹出的随机行走来获得此分布的样本。我们为选择Laplacian的自然估计量提供了统计保证,并调查了我们的Sparsifier在两个应用中的实际应用。
translated by 谷歌翻译
This article explores and analyzes the unsupervised clustering of large partially observed graphs. We propose a scalable and provable randomized framework for clustering graphs generated from the stochastic block model. The clustering is first applied to a sub-matrix of the graph's adjacency matrix associated with a reduced graph sketch constructed using random sampling. Then, the clusters of the full graph are inferred based on the clusters extracted from the sketch using a correlation-based retrieval step. Uniform random node sampling is shown to improve the computational complexity over clustering of the full graph when the cluster sizes are balanced. A new random degree-based node sampling algorithm is presented which significantly improves upon the performance of the clustering algorithm even when clusters are unbalanced. This framework improves the phase transitions for matrix-decomposition-based clustering with regard to computational complexity and minimum cluster size, which are shown to be nearly dimension-free in the low inter-cluster connectivity regime. A third sampling technique is shown to improve balance by randomly sampling nodes based on spatial distribution. We provide analysis and numerical results using a convex clustering algorithm based on matrix completion.
translated by 谷歌翻译
This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models-including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation-which exploits a certain tensor structure in their low-order observable moments (typically, of second-and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin's perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models.
translated by 谷歌翻译
我们提出了对学度校正随机块模型(DCSBM)的合适性测试。该测试基于调整后的卡方统计量,用于测量$ n $多项式分布的组之间的平等性,该分布具有$ d_1,\ dots,d_n $观测值。在网络模型的背景下,多项式的数量($ n $)的数量比观测值数量($ d_i $)快得多,与节点$ i $的度相对应,因此设置偏离了经典的渐近学。我们表明,只要$ \ {d_i \} $的谐波平均值生长到无穷大,就可以使统计量在NULL下分配。顺序应用时,该测试也可以用于确定社区数量。该测试在邻接矩阵的压缩版本上进行操作,因此在学位上有条件,因此对大型稀疏网络具有高度可扩展性。我们结合了一个新颖的想法,即在测试$ K $社区时根据$(k+1)$ - 社区分配来压缩行。这种方法在不牺牲计算效率的情况下增加了顺序应用中的力量,我们证明了它在恢复社区数量方面的一致性。由于测试统计量不依赖于特定的替代方案,因此其效用超出了顺序测试,可用于同时测试DCSBM家族以外的各种替代方案。特别是,我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。
translated by 谷歌翻译
我们开发了第一个快速频谱算法,用于分解$ \ mathbb {r}^d $排名到$ o的随机三阶张量。我们的算法仅涉及简单的线性代数操作,并且可以在当前矩阵乘法时间下在时间$ o(d^{6.05})$中恢复所有组件。在这项工作之前,只能通过方形的总和[MA,Shi,Steurer 2016]实现可比的保证。相反,快速算法[Hopkins,Schramm,Shi,Steurer 2016]只能分解排名最多的张量(D^{4/3}/\ text {polylog}(d))$。我们的算法结果取决于两种关键成分。将三阶张量的清洁提升到六阶张量,可以用张量网络的语言表示。将张量网络仔细分解为一系列矩形矩阵乘法,这使我们能够快速实现该算法。
translated by 谷歌翻译
我们在一般随机块模型下研究现实网络中的社区层次结构,其中连接概率在二叉树中构造。在这种模型中,标准递归双分区算法基于非通知图拉普拉斯的Fiedler向量将网络分成两个社区,并重复分割,直到停止规则指示不进一步的社区结构。我们在广泛的模型参数下证明了这种方法的强大一致性,它包括稀疏网络,节点度为$ O(\ log n)$。此外,与大多数现有工作不同,我们的理论涵盖了多尺度网络,其中连接概率可能因数量级而异,这包括一类实际相关但技术上挑战处理的重要阶段。最后,我们展示了我们对综合性数据和实际示例算法的表现。
translated by 谷歌翻译
我们根据计算一个扎根于每个顶点的某个加权树的家族而构成的相似性得分提出了一种有效的图形匹配算法。对于两个erd \ h {o} s-r \'enyi图$ \ mathcal {g}(n,q)$,其边缘通过潜在顶点通信相关联,我们表明该算法正确地匹配了所有范围的范围,除了所有的vertices分数外,有了很高的概率,前提是$ nq \ to \ infty $,而边缘相关系数$ \ rho $满足$ \ rho^2> \ alpha \ ailpha \大约0.338 $,其中$ \ alpha $是Otter的树木计数常数。此外,在理论上是必需的额外条件下,可以精确地匹配。这是第一个以显式常数相关性成功的多项式图匹配算法,并适用于稀疏和密集图。相比之下,以前的方法要么需要$ \ rho = 1-o(1)$,要么仅限于稀疏图。该算法的症结是一个经过精心策划的植根树的家族,称为吊灯,它可以有效地从同一树的计数中提取图形相关性,同时抑制不同树木之间的不良相关性。
translated by 谷歌翻译
我们提出了改进的算法,并为身份测试$ n $维分布的问题提供了统计和计算下限。在身份测试问题中,我们将作为输入作为显式分发$ \ mu $,$ \ varepsilon> 0 $,并访问对隐藏分布$ \ pi $的采样甲骨文。目标是区分两个分布$ \ mu $和$ \ pi $是相同的还是至少$ \ varepsilon $ -far分开。当仅从隐藏分布$ \ pi $中访问完整样本时,众所周知,可能需要许多样本,因此以前的作品已经研究了身份测试,并额外访问了各种有条件采样牙齿。我们在这里考虑一个明显弱的条件采样甲骨文,称为坐标Oracle,并在此新模型中提供了身份测试问题的相当完整的计算和统计表征。我们证明,如果一个称为熵的分析属性为可见分布$ \ mu $保留,那么对于任何使用$ \ tilde {o}(n/\ tilde {o}),有一个有效的身份测试算法Varepsilon)$查询坐标Oracle。熵的近似张力是一种经典的工具,用于证明马尔可夫链的最佳混合时间边界用于高维分布,并且最近通过光谱独立性为许多分布族建立了最佳的混合时间。我们将算法结果与匹配的$ \ omega(n/\ varepsilon)$统计下键进行匹配的算法结果补充,以供坐标Oracle下的查询数量。我们还证明了一个计算相变:对于$ \ {+1,-1,-1 \}^n $以上的稀疏抗抗铁磁性模型,在熵失败的近似张力失败的状态下,除非RP = np,否则没有有效的身份测试算法。
translated by 谷歌翻译
我们开发了一种高效的随机块模型中的弱恢复算法。该算法与随机块模型的Vanilla版本的最佳已知算法的统计保证匹配。从这个意义上讲,我们的结果表明,随机块模型没有稳健性。我们的工作受到最近的银行,Mohanty和Raghavendra(SODA 2021)的工作,为相应的区别问题提供了高效的算法。我们的算法及其分析显着脱离了以前的恢复。关键挑战是我们算法的特殊优化景观:种植的分区可能远非最佳意义,即完全不相关的解决方案可以实现相同的客观值。这种现象与PCA的BBP相转变的推出效应有关。据我们所知,我们的算法是第一个在非渐近设置中存在这种推出效果的鲁棒恢复。我们的算法是基于凸优化的框架的实例化(与平方和不同的不同),这对于其他鲁棒矩阵估计问题可能是有用的。我们的分析的副产物是一种通用技术,其提高了任意强大的弱恢复算法的成功(输入的随机性)从恒定(或缓慢消失)概率以指数高概率。
translated by 谷歌翻译
我们在非均匀超图随机块模型(HSBM)下的稀疏随机超图中的社区检测问题,是社区结构的随机网络的一般模型和高阶交互。当随机超图具有界定的预期度时,我们提供了一种频谱算法,该频谱算法输出分区,其中至少有$ \ gamma $分数正确分类,其中$ \ gamma \ in(0.5,1)$取决于信号 - 模型的噪声比(SNR)。当SNR随着顶点的数量转到无限的时,SNR慢慢地增长,我们的算法达到了弱的一致性,这改善了Ghoshdastidar和Dukkipati(2017)的上一个结果,用于非均匀的HSBMS。我们的谱算法由三个主要步骤组成:(1)HIFFEGE选择:选择某些尺寸的超高率,为诱导的子图像提供最大信噪比; (2)光谱分区:构造正则化邻接矩阵,并基于奇异向量获得近似分区; (3)纠正和合并:将超代表信息从邻接张于升级升级错误率保证。我们的算法的理论分析依赖于稀疏非均匀随机超图的邻接矩阵的浓度和正则化,这可以是独立的兴趣。
translated by 谷歌翻译
图形模型是用于描述结构化的高尺寸概率分布的有用工具。利用最少数据学习图形模型的高效算法的开发仍然是一个有源研究主题。描述描述离散变量统计的图形模型是一个特别具有挑战性的问题,最大似然方法是棘手的。在这项工作中,我们提供了基于交互筛选框架的第一种样本有效的方法,该方法允许一个以任意基于基础指定的节点特定的离散字母和多主体交互来证明一个完全通用的离散因子模型。我们确定与模型参数化相关的单一条件,导致在任何误差规范中恢复模型结构和参数的严格保证,并且对于大类模型,可以易于验证。重要的是,我们的界限在适用于模型和用作算法的输入的参数之间进行明确区分。最后,我们表明互动筛查框架包括以前在文献中考虑的所有模型作为特殊情况,我们的分析显示了样本复杂性的系统改善。
translated by 谷歌翻译