Learning Stochastic Perceptrons Under k-Blocking Distributions

Mario Marchand, Saeed HadjifaradjiNeurIPS 1994 · OpenReview

Introduction

In Computational Learning Theory, the "Probably Approximately Correct" (PAC) framework serves as the gold standard for proving that an algorithm can learn a concept efficiently. Historically, however, most early successes in PAC learning for neural concepts relied on a massive oversimplification: the assumption that every input feature is statistically independent (product distributions).

Real-world data—such as adjacent pixels in an image or sequential words in a sentence—is rarely independent; features are often highly correlated. Previous attempts to handle these correlations typically fell into two traps: they were either too specific (only handling linear cases) or too broad (rendering the math "unlearnable" due to malicious distributions). This paper bridges the gap by introducing a statistical method to PAC-learn "stochastic perceptrons"—probabilistic neurons with monotonic activation functions—under a realistic, structured form of correlation known as $k$-blocking distributions.

Methodology

The authors introduce two primary innovations to solve the correlation problem: a novel distribution class and a specialized learning algorithm.

1. $k$-Blocking Distributions

A distribution is defined as "$k$-blocking" if, for every variable $x_i$, there exists a small set of other variables (a "blocking set" of size $\le k$) that, when fixed, statistically shields $x_i$ from the rest of the network. Essentially, it formalizes the concept of "local influence." For example, if you know the state of a pixel's immediate neighbors, the state of a pixel on the far side of the image provides no additional information. Crucially, the $k$-blocking family naturally encompasses all $k$-th order Markov distributions, making it applicable to a wide variety of time-series and spatial data structures.

2. The LearnSP Algorithm

To learn a stochastic perceptron—where the output is a probability $f(\sum w_i x_i)$—the authors propose the LearnSP algorithm, which operates in a two-step process:

  • Weight Discovery: The algorithm estimates the "blocked influence" of each variable. By fixing the variables in the blocking set, the algorithm breaks the chain reaction of correlated variables, isolating whether a specific input $x_i$ has a positive, negative, or zero effect on the output. This allows it to assign discrete weights $w_i \in \{-1, 0, +1\}$.
  • Activation Function Estimation: Once the weights are determined, the algorithm does not attempt to guess the exact shape of the activation function (e.g., a sigmoid or radial basis function). Instead, it uses a robust "table look-up" method, estimating the probability of a positive output for every possible sum of weights. Because of this, the algorithm works for any monotonic activation function.

Key Theoretical Results

As a theoretical paper focused on formal proofs of learnability, the study does not rely on empirical datasets or benchmarks like MNIST. Instead, its core contributions are mathematical guarantees:

  • Polynomial Time Complexity: The authors prove that the LearnSP algorithm can learn the target concept to within $\epsilon$ error with $1-\delta$ confidence using a number of samples and computation time that is polynomial relative to the number of inputs ($n$) and the inverse of the error parameters.
  • Sample Complexity: The paper provides a specific bound for the number of examples ($m$) required, which scales with $(2n)^{2k+4}$. While this grows quickly with $k$, it remains highly efficient for small, fixed neighborhood sizes.
  • Breaking the Chain Reaction: The theoretical "aha moment" is the realization that correlations act like a chain reaction. By "hard-wiring" a small blocking set, the learner successfully isolates the specific contribution of a single variable, enabling efficient learning despite complex dependencies.

Limitations and Future Work

While a significant step forward, the framework has a few notable constraints:

  • The "Known Neighborhood" Problem: The algorithm assumes the learner already knows which variables belong in the blocking set for each $x_i$. Finding these sets from scratch is likely NP-complete. However, in fields like computer vision, these sets are often naturally provided by spatial proximity.
  • Weight Restrictions: The current proof holds specifically for discrete weights $\{-1, 0, +1\}$. While this covers feature selection (0) and basic excitatory/inhibitory connections, extending the proofs to arbitrary real-valued weights remains a challenge for future research.
  • Computational Scaling: Although technically polynomial, the exponent depends heavily on $k$. For distributions with very large dependencies (a large $k$), the sample requirements would become practically prohibitive.

Summary updated

Abstract

We present a statistical method that PAC learns the class of stochastic perceptrons with arbitrary monotonic activation func(cid:173) tion and weights Wi E {-I, 0, + I} when the probability distribution that generates the input examples is member of a family that we call k-blocking distributions. Such distributions represent an impor(cid:173) tant step beyond the case where each input variable is statistically independent since the 2k-blocking family contains all the Markov distributions of order k. By stochastic percept ron we mean a per(cid:173) ceptron which, upon presentation of input vector x, outputs 1 with probability fCLJi WiXi - B). Because the same algorithm works for any monotonic (nondecreasing or nonincreasing) activation func(cid:173) tion f on Boolean domain, it handles the well studied cases of sigmolds and the "usual" radial basis functions.
BibTeX
@inproceedings{marchand1994learning,
  author = {Mario Marchand and Saeed Hadjifaradji},
  title = {{Learning Stochastic Perceptrons Under k-Blocking Distributions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1994},
  url = {https://openreview.net/forum?id=SJbcJYbOWB},
}
Figure