Iterative maximum likelihood on networks

作者：Mossel Elchanan; Tamuz Omer^*

来源：Advances in Applied Mathematics, 2010, 45(1): 36-49.

DOI：10.1016/j.aam.2009.11.004

• Maximum likelihood
• Sparse sensing
• Learning on networks
• Algebraic recursion relation
• Bayesian Economics

We consider n agents located on the vertices of a connected graph. Each agent v receives a signal X(v)(0) similar to N(mu, 1) where mu is an unknown quantity. A natural iterative way of estimating mu is to perform the following procedure. At iteration t + 1 let X(v)(t + 1) be the average of X(v)(t) and of X(w)(t) among all the neighbors w of v. It is well known that this procedure converges to X(infinity) = 1/2 vertical bar E vertical bar(-1) Sigma d(v)X(v) where d(v) is the degree of v.
In this paper we consider a variant of simple iterative averaging, which models "greedy" behavior of the agents. At iteration t, each agent v declares the value of its estimator X(v)(t) to all of its neighbors. Then, it updates X(v)(t + 1) by taking the maximum likelihood (or minimum variance) estimator of mu, given X(v)(t) and X(w)(t) for all neighbors w of v, and the structure of the graph. We give an explicit efficient procedure for calculating X(v)(t), study the convergence of the process as t -> infinity and show that if the limit exists then X(v)(infinity) = X(w)(infinity) for all v and w. For graphs that are symmetric under actions of transitive groups, we show that the process is efficient. Finally, we show that the greedy process is in some cases more efficient than simple averaging, while in other cases the converse is true, so that, in this model, "greed" of the individual agents may or may not have an adverse affect on the outcome.
The model discussed here may be viewed as the maximum likelihood version of models studied in Bayesian Economics. The ML variant is more accessible and allows in particular to show the significance of symmetry in the efficiency of estimators using networks of agents.

• 出版日期2010-7