Memory-Aware Social Learning under Partial Information Sharing

Michele Cirillo, Virgı́nia Bordignon, Vincenzo Matta, Ali H. SayedIEEE TSP 2023

TL;DR

This paper introduces a novel "memory-aware" strategy for social learning in networks where agents can only share information about a single hypothesis. They demonstrate that this approach, unlike standard methods, allows agents to correctly classify hypotheses even with limited information, and importantly, that a simple maximum-belief rule is insufficient.

What Problem Does This Paper Address?

Imagine a group of agents (like sensors, robots, or even people) trying to collectively figure out the true state of the world (e.g., is it going to rain, or is product A better than product B?). They do this by observing data and sharing their "beliefs" (how confident they are about each possibility) with their neighbors in a network.

The challenge this paper tackles is a common real-world constraint: agents can't share everything they know. Instead, they can only share information about one specific hypothesis they are interested in. This is like a group trying to decide if it will rain, but each person can only tell their neighbor "I think it will rain" or "I don't think it will rain," without giving details about other weather possibilities like "snow" or "hail." This "partial information sharing" makes it much harder for agents to reach a consensus or correctly identify the true state. Traditional social learning methods often assume full belief sharing, which doesn't work here.

Methods

The core of this paper is a new learning strategy called "memory-aware social learning." Here's how it works and what's new:

  • Partial Information Sharing: Agents only transmit their belief about a single, designated hypothesis (let's call it $\theta_{tx}$).
  • Belief Completion (The Novelty): When an agent receives this partial information from a neighbor, it needs to "fill in the gaps" for the other hypotheses. Instead of just assuming a uniform distribution (like saying "I have no idea about the rest"), the proposed "memory-aware" strategy uses the agent's own past beliefs to make an informed guess about the missing information. This is inspired by a Bayesian criterion and is the key innovation.
  • Bayesian Update & Averaging: Like standard social learning, agents still perform local Bayesian updates with new observations and then combine information from neighbors through a weighted average. The difference lies in how they reconstruct the full belief vectors before averaging.
  • Memoryless vs. Memory-Aware: The paper contrasts their approach with a "memoryless" strategy that fills in missing beliefs uniformly. They show that the memory-aware approach is superior.
  • Decision Rule: Crucially, they demonstrate that the standard approach of simply picking the hypothesis with the highest belief is not optimal under partial information sharing. Instead, they propose a threshold-based decision rule that allows agents to correctly classify the transmitted hypothesis with high probability.

Datasets

Not discussed in the paper. The experiments are based on simulated networks and synthetic data generated according to specified likelihood models.

Key Insights and Ideas

  • Memory is Crucial: The paper strongly emphasizes that incorporating an agent's own past beliefs (memory) into the process of filling in missing information is critical for overcoming the limitations of partial information sharing.
  • Maximizing Belief Isn't Always Best: A surprising finding is that the intuitive strategy of always choosing the hypothesis with the highest belief can fail when information is partial. This is because the highest belief might be allocated to indistinguishable hypotheses.
  • A Smarter Decision Rule: A simple threshold-based rule, which checks if the belief in the transmitted hypothesis exceeds a certain level (related to initial confusion), proves to be more robust and effective for classification.
  • Cooperation Can Be Tricky: While cooperation is generally beneficial, the paper shows that in some scenarios (when an agent is already less confused than the network average), cooperation might not lead to the true hypothesis having the absolute maximum belief, even though correct classification is still achieved.
  • Global Identifiability is Key: The ability of the network as a whole to distinguish the true hypothesis from others (global identifiability) is essential for successful learning, even if individual agents struggle.

Key Results

  • Correct Classification: Under the memory-aware strategy, agents can correctly classify the transmitted hypothesis with probability approaching 1 as time goes on, provided the network has global identifiability.
  • Discarding False Hypotheses: When the transmitted hypothesis is not the true one ($\theta_{tx} \neq \theta_0$), agents effectively discard it, assigning it near-zero belief. They also discard other distinguishable hypotheses.
  • Handling Indistinguishable Hypotheses: When the transmitted hypothesis is the true one ($\theta_{tx} = \theta_0$), agents assign a belief that converges to a value strictly less than 1, but this value is greater than the belief assigned to any distinguishable hypothesis. The remaining belief mass is distributed among indistinguishable hypotheses.
  • Performance Improvement: The proposed memory-aware strategy outperforms previously considered schemes for partial information sharing.

Limitations and Future Work

  • Computational Complexity: While the paper focuses on communication efficiency, the Bayesian updates themselves can still be computationally intensive.
  • Knowledge of Network Structure/Parameters: The proposed decision rule requires some knowledge of the network's initial confusion ratios (e.g., the network confusion ratio $\rho$ or minimum initial belief $\mu_{min,0}$). While they show how to set a threshold with coarser information, full knowledge of initial beliefs and network structure is ideal.
  • Future Work: The authors suggest exploring scenarios with more complex information sharing patterns, different network structures, and investigating the practical implementation of such algorithms in real-world systems. They also hint at further analysis of the dichotomy between the $\theta_{tx} \neq \theta_0$ and $\theta_{tx} = \theta_0$ cases.

Summary updated

Abstract

This work examines a social learning problem, where dispersed agents connected through a network topology interact locally to form their opinions (beliefs) as regards certain hypotheses of interest. These opinions evolve over time, since the agents collect observations from the environment, and update their current beliefs by accounting for: their past beliefs, the innovation contained in the new data, and the beliefs received from the neighbors. The distinguishing feature of the present work is that agents are constrained to share opinions regarding only a single hypothesis. We devise a novel learning strategy where each agent forms a valid belief by completing the partial beliefs received from its neighbors. This completion is performed by exploiting the knowledge accumulated in the past beliefs, thanks to a principled memory-aware rule inspired by a Bayesian criterion. The analysis allows us to characterize the role of memory in social learning under partial information sharing, revealing novel and nontrivial learning dynamics. Surprisingly, we establish that the standard classification rule based on selecting the maximum belief is not optimal under partial information sharing, while there exists a consistent threshold-based decision rule that allows each agent to classify correctly the hypothesis of interest. We also show that the proposed strategy outperforms previously considered schemes, highlighting that the introduction of memory in the social learning algorithm is critical to overcome the limitations arising from sharing partial information.
BibTeX
@article{cirillo2023memory,
  author = {Michele Cirillo and Virgı́nia Bordignon and Vincenzo Matta and Ali H. Sayed},
  title = {{Memory-Aware Social Learning under Partial Information Sharing}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
}
Figure