标题： 通过机器学习的网络信息聚合 显示英文标题

标题： Networked Information Aggregation via Machine Learning

摘要： 我们研究了一个分布式学习问题，其中学习代理嵌入在一个有向无环图（DAG）中。 在特征/标签对上存在一个固定且任意的分布，图中的每个代理或顶点只能直接观察到特征的一个子集——每个代理可能有不同的子集。 代理按照与DAG的拓扑排序一致的顺序依次学习，承诺一个将观察结果映射到实数值标签预测的模型。 每个代理观察DAG中其父节点的预测，并使用他们直接观察到的实例的特征以及父节点的预测作为额外特征来训练他们的模型。 我们询问在这种情况下，什么时候这个过程足以实现\emph{信息聚合}，即DAG中某个代理能够学习一个模型，其误差与在某些假设类中可以直接访问\emph{全部}特征的情况下所能学习的最佳模型的误差具有竞争力，尽管网络中没有任何单个代理具有这种访问权限。 我们给出了线性和一般假设类的该问题的上下界。 我们的结果确定了DAG的\emph{深度}作为关键参数：在假设路径上的相关特征都被良好表示的情况下，信息聚合可以在足够长的路径上发生，而且存在一些分布，在线性情况下甚至在任意大的DAG中信息聚合也无法发生（例如，辐条-中心拓扑结构中，辐条顶点共同看到所有特征）。 我们通过一组全面的实验来补充我们的理论结果。 显示英文摘要

摘要： We study a distributed learning problem in which learning agents are embedded in a directed acyclic graph (DAG). There is a fixed and arbitrary distribution over feature/label pairs, and each agent or vertex in the graph is able to directly observe only a subset of the features -- potentially a different subset for every agent. The agents learn sequentially in some order consistent with a topological sort of the DAG, committing to a model mapping observations to predictions of the real-valued label. Each agent observes the predictions of their parents in the DAG, and trains their model using both the features of the instance that they directly observe, and the predictions of their parents as additional features. We ask when this process is sufficient to achieve \emph{information aggregation}, in the sense that some agent in the DAG is able to learn a model whose error is competitive with the best model that could have been learned (in some hypothesis class) with direct access to \emph{all} features, despite the fact that no single agent in the network has such access. We give upper and lower bounds for this problem for both linear and general hypothesis classes. Our results identify the \emph{depth} of the DAG as the key parameter: information aggregation can occur over sufficiently long paths in the DAG, assuming that all of the relevant features are well represented along the path, and there are distributions over which information aggregation cannot occur even in the linear case, and even in arbitrarily large DAGs that do not have sufficient depth (such as a hub-and-spokes topology in which the spoke vertices collectively see all the features). We complement our theoretical results with a comprehensive set of experiments.