boofun.analysis.pac_learning

PAC (Probably Approximately Correct) Learning for Boolean functions.

This module implements PAC learning algorithms for various classes of Boolean functions as covered in O’Donnell Chapter 3 and Lecture 6.

Key algorithms: - Low-degree learning: Learn functions with spectral concentration - Junta learning: Learn k-juntas with query complexity O(2^k) - LMN algorithm: Learn decision trees from uniform samples - Sparse Fourier learning: Learn functions with few Fourier coefficients

PAC Learning Framework: - Given: Sample access to f (can draw (x, f(x)) for random x) - Goal: Output hypothesis h such that Pr[h(x) ≠ f(x)] ≤ ε - With probability at least 1 - δ

References: - Linial, Mansour, Nisan (1993): “Constant depth circuits, Fourier transform” - O’Donnell Chapter 3: Learning - Mossel, O’Donnell, Servedio (2004): “Learning juntas”

Functions

lmn_algorithm(f[, epsilon, delta, rng])	Learn a function using the Linial-Mansour-Nisan algorithm.
pac_learn_decision_tree(f, max_depth[, ...])	PAC learn a function computed by a depth-d decision tree.
pac_learn_junta(f, k[, epsilon, delta, rng])	PAC learn a k-junta (function depending on at most k variables).
pac_learn_low_degree(f, max_degree[, ...])	PAC learn a function assuming it has degree at most max_degree.
pac_learn_monotone(f[, epsilon, delta, rng])	PAC learn a monotone Boolean function.
pac_learn_sparse_fourier(f, sparsity[, ...])	Learn a function assuming it has at most 'sparsity' non-zero Fourier coefficients.
sample_function(f, num_samples[, rng])	Draw random labeled samples from a Boolean function.

Classes

PACLearner(f[, epsilon, delta, rng])

PAC learning framework for Boolean functions.

boofun.analysis.pac_learning.pac_learn_low_degree(f: BooleanFunction, max_degree: int, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None) → Dict[int, float]

PAC learn a function assuming it has degree at most max_degree.

Uses the “Low-Degree Algorithm” from O’Donnell Chapter 3: 1. Estimate all Fourier coefficients of degree ≤ max_degree 2. Threshold small coefficients 3. Return the truncated polynomial

Sample complexity: O(n^d / ε²) where d = max_degree

Parameters:

• f – Target function (used for sampling)

• max_degree – Maximum degree to learn

• epsilon – Target error rate

• delta – Failure probability

• rng – Random number generator

Returns:

Dictionary mapping subset masks to estimated Fourier coefficients

boofun.analysis.pac_learning.pac_learn_junta(f: BooleanFunction, k: int, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None) → Tuple[List[int], Dict[int, float]]

PAC learn a k-junta (function depending on at most k variables).

Uses influence-based junta finding followed by exhaustive learning on the relevant variables.

Parameters:

• f – Target function

• k – Maximum number of relevant variables

• epsilon – Target error rate

• delta – Failure probability

• rng – Random number generator

Returns:

Tuple of (relevant_variables, learned_function_on_those_vars)

boofun.analysis.pac_learning.pac_learn_sparse_fourier(f: BooleanFunction, sparsity: int, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None) → Dict[int, float]

Learn a function assuming it has at most ‘sparsity’ non-zero Fourier coefficients.

Uses heavy coefficient detection followed by precise estimation.

Parameters:

• f – Target function

• sparsity – Maximum number of non-zero coefficients

• epsilon – Target error rate

• delta – Failure probability

• rng – Random number generator

Returns:

Dictionary of learned Fourier coefficients

boofun.analysis.pac_learning.pac_learn_decision_tree(f: BooleanFunction, max_depth: int, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None) → Dict[int, float]

PAC learn a function computed by a depth-d decision tree.

Decision trees of depth d have Fourier concentration on degrees 0 to d. Uses this fact to apply low-degree learning.

Parameters:

• f – Target function

• max_depth – Maximum tree depth

• epsilon – Target error rate

• delta – Failure probability

• rng – Random number generator

Returns:

Dictionary of learned Fourier coefficients

boofun.analysis.pac_learning.pac_learn_monotone(f: BooleanFunction, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None) → Dict[int, float]

PAC learn a monotone Boolean function.

Monotone functions have special structure: all non-zero Fourier coefficients f̂(S) ≥ 0 for non-empty S.

Parameters:

• f – Target function (assumed monotone)

• epsilon – Target error rate

• delta – Failure probability

• rng – Random number generator

Returns:

Dictionary of learned Fourier coefficients

boofun.analysis.pac_learning.lmn_algorithm(f: BooleanFunction, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None) → Dict[int, float]

Learn a function using the Linial-Mansour-Nisan algorithm.

The LMN algorithm learns any function that is well-approximated by a polynomial of degree O(log(1/ε)).

Particularly effective for: - Functions computed by small depth circuits (AC⁰) - Decision trees - DNFs with few terms

Parameters:

• f – Target function

• epsilon – Target error rate

• delta – Failure probability

• rng – Random number generator

Returns:

Dictionary of learned Fourier coefficients

class boofun.analysis.pac_learning.PACLearner(f: BooleanFunction, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None)

PAC learning framework for Boolean functions.

Provides a unified interface for various PAC learning algorithms with sample complexity tracking.

__init__(f: BooleanFunction, epsilon: float = 0.1, delta: float = 0.05, rng: np.random.Generator | None = None)

Initialize PAC learner.

Parameters:

• f – Target function

• epsilon – Target error rate

• delta – Failure probability

• rng – Random number generator

sample(num_samples: int) → List[Tuple[int, int]]

Draw samples and track count.

learn_low_degree(max_degree: int) → Dict[int, float]

Learn assuming low degree.

learn_junta(k: int) → Tuple[List[int], Dict[int, float]]

Learn assuming k-junta.

learn_sparse(sparsity: int) → Dict[int, float]

Learn assuming sparse Fourier spectrum.

learn_decision_tree(max_depth: int) → Dict[int, float]

Learn assuming decision tree structure.

learn_monotone() → Dict[int, float]

Learn assuming monotone function.

learn_adaptive() → Dict[str, Any]

Adaptively choose learning algorithm based on function properties.

Returns:

Dict with learned coefficients and algorithm used

evaluate_hypothesis(coefficients: Dict[int, float], x: int) → int

Evaluate learned hypothesis on input x.

h(x) = sign(Σ f̂(S) χ_S(x))

test_accuracy(coefficients: Dict[int, float], num_tests: int = 1000) → float

Test accuracy of learned hypothesis.

summary() → str

Get summary of learning progress.

boofun.analysis.pac_learning.sample_function(f: BooleanFunction, num_samples: int, rng: np.random.Generator | None = None) → List[Tuple[int, int]]

Draw random labeled samples from a Boolean function.

Parameters:

• f – Boolean function to sample

• num_samples – Number of samples to draw

• rng – Random number generator

Returns:

List of (input, output) pairs