Active Learning of Multiple Source Multiple Destination Topologies

DOI10.1109/TSP.2014.2304431zbMATH Open1394.94500arXiv1212.2310OpenAlexW2762632680MaRDI QIDQ4579124FDOQ4579124

Authors: Pegah Sattari, MacIej Kurant, Animashree Anandkumar, Athina Markopoulou, Michael G. Rabbat 

Publication date: 22 August 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: We consider the problem of inferring the topology of a network with $M$ sources and $N$ receivers (hereafter referred to as an $M$-by-$N$ network), by sending probes between the sources and receivers. Prior work has shown that this problem can be decomposed into two parts: first, infer smaller subnetwork components (i.e., $1$-by-$N$'s or $2$-by-$2$'s) and then merge these components to identify the $M$-by-$N$ topology. In this paper, we focus on the second part, which had previously received less attention in the literature. In particular, we assume that a $1$-by-$N$ topology is given and that all $2$-by-$2$ components can be queried and learned using end-to-end probes. The problem is which $2$-by-$2$'s to query and how to merge them with the given $1$-by-$N$, so as to exactly identify the $2$-by-$N$ topology, and optimize a number of performance metrics, including the number of queries (which directly translates into measurement bandwidth), time complexity, and memory usage. We provide a lower bound, $lceilfracN2ceil$, on the number of $2$-by-$2$'s required by any active learning algorithm and propose two greedy algorithms. The first algorithm follows the framework of multiple hypothesis testing, in particular Generalized Binary Search (GBS), since our problem is one of active learning, from $2$-by-$2$ queries. The second algorithm is called the Receiver Elimination Algorithm (REA) and follows a bottom-up approach: at every step, it selects two receivers, queries the corresponding $2$-by-$2$, and merges it with the given $1$-by-$N$; it requires exactly $N-1$ steps, which is much less than all $$ possible $2$-by-$2$'s. Simulation results over synthetic and realistic topologies demonstrate that both algorithms correctly identify the $2$-by-$N$ topology and are near-optimal, but REA is more efficient in practice.

Full work available at URL: https://arxiv.org/abs/1212.2310

Recommendations

• Publication:4939096
• Active learning via collective inference in network regression problems
• Active Learning in Multi-armed Bandits
• Active learning in neural networks
• Multiple-view multiple-learner active learning
• Active learning with multiple views
• A Scalable Algorithm for Graph-Based Active Learning

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

This page was built for publication: Active Learning of Multiple Source Multiple Destination Topologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579124)