An Active Learning Framework using Sparse-Graph Codes for Sparse Polynomials and Graph Sketching
An Active Learning Framework using Sparse-Graph Codes for Sparse Polynomials and Graph Sketching
复制标题
使用稀疏图代码进行稀疏多项式和图绘制的主动学习框架
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
K. Ramchandran
中科院分区：
文献类型：
--
作者：
Xiao Li;K. Ramchandran
设f：{-1，1}n → n是一个由2n个单项式组成的n元多项式，其中只有s ~ 2n个系数不为零.目标是通过查询f的值来学习多项式。我们引入了一个主动学习框架，这是与低查询成本和计算运行时间。显著的节省是通过利用基于现代编码理论的采样策略来实现的，具体地，稀疏图码（诸如低密度奇偶校验（LDPC）码）的设计和分析，其代表了现代分组通信的最新技术水平。更重要的是，我们展示了这种设计视角如何导致令人兴奋的，以及据我们所知，学习和编码之间的大部分未开发的智力联系。
关键是放松最坏情况的假设，使用集合平均设置，其中假设多项式是从所有多项式（具有给定大小n和稀疏性s）的集合中随机均匀抽取的。对于任何δ ∈（0，1），我们的框架在稀疏度高达s = O（2δn）的多项式系综上以高概率成功，其中f是在O（ns log s）时间内使用O（ns）查询精确学习的，即使查询受到高斯噪声的干扰。我们进一步应用所提出的框架，图素描，这是通过查询图切割推断稀疏图的问题。通过将割函数写成多项式并利用图的结构，我们提出了一种仅使用少量割查询就能学习任意n节点未知图的草图绘制算法，该算法在边的数量上几乎是线性的，在图的大小n上是次线性的.在真实的数据集上的实验表明，与竞争方案相比，该方案在运行时间和查询复杂度上都有显着降低。
Let f : {-1,1}n → ℝ be an n-variate polynomial consisting of 2n monomials, in which only s ≪ 2n coefficients are non-zero. The goal is to learn the polynomial by querying the values of f. We introduce an active learning framework that is associated with a low query cost and computational runtime. The significant savings are enabled by leveraging sampling strategies based on modern coding theory, specifically, the design and analysis of sparse-graph codes, such as Low-Density-Parity-Check (LDPC) codes, which represent the state-of-the-art of modern packet communications. More significantly, we show how this design perspective leads to exciting, and to the best of our knowledge, largely unexplored intellectual connections between learning and coding.
The key is to relax the worst-case assumption with an ensemble-average setting, where the polynomial is assumed to be drawn uniformly at random from the ensemble of all polynomials (of a given size n and sparsity s). Our framework succeeds with high probability with respect to the polynomial ensemble with sparsity up to s = O(2δn) for any δ ∈ (0,1), where f is exactly learned using O(ns) queries in time O(ns log s), even if the queries are perturbed by Gaussian noise. We further apply the proposed framework to graph sketching, which is the problem of inferring sparse graphs by querying graph cuts. By writing the cut function as a polynomial and exploiting the graph structure, we propose a sketching algorithm to learn the an arbitrary n-node unknown graph using only few cut queries, which scales almost linearly in the number of edges and sub-linearly in the graph size n. Experiments on real datasets show significant reductions in the runtime and query complexity compared with competitive schemes.