Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Learning in decentralized systems: A nonparametric approach

Xuanlong Nguyen

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-111
August 30, 2007

http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-111.pdf

Rapid advances in information technology result in increased deployment of decentralized decision-making systems embedded within large-scale infrastructures consisting of data collection and processing devices. In such a system, each statistical decision is performed on the basis of limited amount of data due to constraints given by the decentralized system. For instance, the constraints may be imposed by limits in energy source, communication bandwidth, computation and time budget. A fundamental research problem arised in decentralized systems involves the development of methods that take into account not only the statistical accuracy of decision-making procedures, but also the constraints imposed by the system limits. It is this general problem that drives the focus of this thesis. In particular, we focus on the development and analysis of statistical learning methods for decentralized decision-making by employing a nonparametric approach. The nonparametric approach imposes very little a priori assumption on the data; such flexibility allows it to be applicable to a wide range of applications. Coupled with tools from convex analysis and empirical process theory we develop computationally efficient algorithms and analyze their statistical behavior both theoretically and empirically. Our specific contributions include the following. We develop a novel kernel-based algorithm for centralized detection and estimation in the ad hoc sensor networks through the challenging task of sensor mote localization. Next, we develop and analyze a nonparametric decentralized detection algorithm using the methodology of convex surrogate loss functions and marginalized kernels. The analysis of this algorithm leads to an in-depth study of the correspondence between the class of surrogate loss functions widely used in statistical machine learning and the class of divergence functionals widely used in information theory. This correspondence allows us to provide an interesting decision-theoretic justification to a given choice of divergence functionals, which often arise from asymptotic analysis. In addition, this correspondence also motivates the development and the analysis of a novel M-estimation procedure for estimating divergence functionals and the likelihood ratio. Finally, we also investigate a sequential setting of the decentralized detection algorithm, and settle an open question regarding the characterization of optimal decision rules in such a setting.

Advisor: Michael Jordan


BibTeX citation:

@phdthesis{Nguyen:EECS-2007-111,
    Author = {Nguyen, Xuanlong},
    Title = {Learning in decentralized systems: A nonparametric approach},
    School = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Aug},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-111.html},
    Number = {UCB/EECS-2007-111},
    Abstract = {Rapid advances in information technology result in increased deployment of decentralized decision-making systems embedded within large-scale infrastructures consisting of data collection and processing devices. In such a system, each statistical decision is performed on the basis of limited amount of data due to constraints given by the decentralized system. For instance, the constraints may be imposed by limits in energy source, communication bandwidth, computation and time budget. A fundamental research problem arised in decentralized systems involves the development of methods that take into account not only the statistical accuracy of decision-making procedures, but also the constraints imposed by the system limits. It is this general problem that drives the focus of this thesis. In particular, we focus on the development and analysis of statistical learning methods for decentralized decision-making by employing a nonparametric approach.  The nonparametric approach imposes very little a priori assumption on the data; such flexibility allows it to be applicable to a wide range of applications.  Coupled with tools from convex analysis and empirical process theory we develop computationally efficient algorithms and analyze their statistical behavior both theoretically and empirically. 

Our specific contributions include the following. We develop a novel kernel-based algorithm for centralized detection and estimation in the ad hoc sensor networks through the challenging task of sensor mote localization. Next, we develop and analyze a nonparametric decentralized detection algorithm using the methodology of convex surrogate loss functions and marginalized kernels. The analysis of this algorithm leads to an in-depth study of the correspondence between the class of surrogate loss functions widely used in statistical machine learning and the class of divergence functionals widely used in information theory. This correspondence allows us to provide an interesting decision-theoretic justification to a given choice of divergence functionals, which often arise from asymptotic analysis. In addition, this correspondence also motivates the development and the analysis of a novel M-estimation procedure for estimating divergence functionals and the likelihood ratio. Finally, we also investigate a sequential setting of the decentralized detection algorithm, and settle an open question regarding the characterization of optimal decision rules in such a setting.}
}

EndNote citation:

%0 Thesis
%A Nguyen, Xuanlong
%T Learning in decentralized systems: A nonparametric approach
%I EECS Department, University of California, Berkeley
%D 2007
%8 August 30
%@ UCB/EECS-2007-111
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-111.html
%F Nguyen:EECS-2007-111