The Kushilevitz–Mansour algorithm #
The Kushilevitz–Mansour algorithm [KM93]
O'Donnell, Section 3.5 learns, with membership queries, every Boolean function of
small spectral norm ∑_S |f̂(S)| (UniformLearning.spectralNormClass); for instance every function
computed by a small decision tree (UniformLearning.decisionTreeClass). It finds the large Fourier
coefficients by the bucket search of Goldreich and Levin [GL89]: the bucket of a set
S ⊆ J is the family of the sets U with U ∩ J = S, and its weight is the bucket weight
(BitString.bucketWeight, O'Donnell's W^{S | J̄} with J̄ the complement of J). Starting from
the bucket of all sets, the search adds the coordinates one at a time, splitting each surviving
bucket S of J into the buckets S and insert i S of insert i J, and keeps the buckets whose
estimated weight is at least θ² / 2 (UniformLearning.bucketSearch). A set U with |f̂(U)| ≥ θ
contributes θ² to each of its buckets and is never discarded
(UniformLearning.inter_mem_bucketSearch), while every surviving bucket weighs at least θ² / 4,
so at most 4 / θ² buckets survive at each level (UniformLearning.mul_card_bucketSearch_le_one).
The weights are estimated from samples (x, y, z) of three independent uniform points, as the
average of f (x, z) χ_S(x) f (y, z) χ_S(y) (UniformLearning.bucketEstimate,
BitString.bucketWeight_eq_expect_sample), where (x, z) takes the coordinates in J from x and
the others from z. Here the same m samples serve every bucket of every level, so the queries are
non-adaptive: the learner queries f at x and at the points (x, z), (y, z) of every sample
and every level, m (2 n + 3) queries for n coordinates
(UniformLearning.kmLearner_queriesAtMost), and then runs the search on the answers. The analysis
takes a union bound over all 2 ^ n buckets of each level, which costs a factor n in the number
of samples compared with fresh samples for each weighing. The hypothesis is the sign of the
expansion on the found sets with coefficients estimated from the points x
(UniformLearning.kmHypothesis, UniformLearning.kmLearner).
If all estimates are within θ² / 4 of their values, the hypothesis has error at most
θ² / 4 + θ L for a function of spectral norm at most L
(UniformLearning.uniformError_kmHypothesis_le): the found sets carry all coefficients of absolute
value at least θ, and the others weigh at most θ L. Hoeffding's inequality and the union bound
make the estimates accurate except with probability at most 2 (n + 2) 2 ^ n exp (-m θ⁴ / 32)
(UniformLearning.uniform_not_accurate_le). With θ = ε / (2 L) this gives the
Kushilevitz–Mansour theorem: the functions of spectral norm at most L are learned with error
ε and confidence 1 - δ from m ≥ (512 L⁴ / ε⁴) log (2 (n + 2) 2 ^ n / δ) samples, hence
m (2 n + 3) membership queries, polynomial in n, L, 1 / ε and log (1 / δ)
(UniformLearning.kmLearner_learns) O'Donnell, Theorem 3.38. By the spectral
norm bound for decision trees (DecisionTree.sum_abs_fourierCoeff_signVal_le_leafCount), this
applies to the functions computed by decision trees with at most L leaves
(UniformLearning.kmLearner_learns_decisionTree).
Cost. Only the number of queries is certified. On accurate samples the search computes at most
8 / θ² bucket estimates at each level, each from the m samples, and estimates at most 4 / θ²
coefficients; this count of arithmetic operations is informal, and the running time is not
certified by a machine model.
Main definitions #
Cslib.MachineLearning.UniformLearning.spectralNormClass,Cslib.MachineLearning.UniformLearning.decisionTreeClass: the functions of bounded spectral norm, and those computed by decision trees with few leaves.Cslib.MachineLearning.UniformLearning.bucketSearch: the bucket search of Goldreich–Levin and Kushilevitz–Mansour.Cslib.MachineLearning.UniformLearning.bucketEstimate,Cslib.MachineLearning.UniformLearning.sampleCoeff: the empirical bucket weights and Fourier coefficients of the samples.Cslib.MachineLearning.UniformLearning.kmHypothesis,Cslib.MachineLearning.UniformLearning.kmLearner: the Kushilevitz–Mansour algorithm.Cslib.MachineLearning.UniformLearning.KMAccurate: accurate samples.
Main results #
Cslib.MachineLearning.UniformLearning.inter_mem_bucketSearch,Cslib.MachineLearning.UniformLearning.mul_card_bucketSearch_le_one: the bucket search finds the heavy sets and keeps few buckets.Cslib.MachineLearning.UniformLearning.uniformError_kmHypothesis_le: the error on accurate samples.Cslib.MachineLearning.UniformLearning.uniform_not_accurate_le: the samples are accurate with high probability.Cslib.MachineLearning.UniformLearning.kmLearner_learns,Cslib.MachineLearning.UniformLearning.kmLearner_learns_and_queriesAtMost: the Kushilevitz–Mansour theorem.Cslib.MachineLearning.UniformLearning.kmLearner_learns_decisionTree,Cslib.MachineLearning.UniformLearning.kmLearner_learns_decisionTree_and_queriesAtMost: learning decision trees with membership queries.
References #
The bucket search #
The sets of coordinates weighed by the bucket search over the list l: the sets of
coordinates of the suffixes of l, from l itself down to the empty list.
Instances For
The coordinates of l are its first level.
The bucket search of Goldreich–Levin and Kushilevitz–Mansour over the list l of
coordinates, given estimates est J S of the bucket weights W^{S | J} and a threshold τ.
Starting from the bucket of all sets, it adds the coordinates of l from the last to the first,
splits each surviving bucket S of J into the buckets S and insert i S of insert i J, and
keeps the buckets whose estimated weight is at least τ.
Instances For
The bucket search reads the estimates only at its levels.
Every bucket kept by the search over l has estimated weight at least τ at the level of
the coordinates of l.
Completeness of the bucket search: if at every level J the bucket of U ∩ J has
estimated weight at least τ, then the search over l keeps the bucket U ∩ l.
Few buckets survive: if the estimates at the level of the coordinates of l are within
θ² / 4 of the bucket weights of a Boolean function, then the search over l with threshold
θ² / 2 keeps at most 4 / θ² buckets.
The algorithm #
The Boolean functions whose spectral norm ∑_S |f̂(S)|, read as signs, is at most L.
Instances For
The functions computed by decision trees with at most L leaves.
Instances For
The empirical estimate of the bucket weight W^{S | J} of g, read as signs, from the
samples ω j = (x, y, z): the average of g (x, z) χ_S(x) g (y, z) χ_S(y), where (x, z) takes
the coordinates in J from x and the others from z.
Instances For
The sets found by the Kushilevitz–Mansour algorithm with threshold θ: the bucket search over
all coordinates, keeping the buckets with estimated weight at least θ² / 2.
Instances For
The hypothesis of the Kushilevitz–Mansour algorithm: the sign of the expansion on the found sets, with the empirical coefficients of the samples.
Instances For
The points queried by the Kushilevitz–Mansour algorithm: the first point x of each sample,
and the points (x, z) and (y, z) of each sample (x, y, z) at every level J of the
search.
Instances For
The hypothesis depends only on the answers at the queried points.
The Kushilevitz–Mansour algorithm with threshold θ from m samples: draw m
independent samples of three uniform points, query the target at the points kmQueries, run the
bucket search with threshold θ² / 2 on the estimated bucket weights, and output the sign of the
expansion on the found sets with estimated coefficients. Its queries are non-adaptive.
Instances For
Run on the target f, the algorithm outputs kmHypothesis f θ ω.
The Kushilevitz–Mansour algorithm makes m (2 n + 3) membership queries for n
coordinates.
The analysis #
The samples ω are accurate for f at precision γ: every bucket estimate at every level
of the search over all coordinates, and every sample coefficient, is within γ of its value.
Instances For
The Kushilevitz–Mansour algorithm on accurate samples. Let the spectral norm of f, read
as signs, be at most L, and let θ > 0. If the samples are accurate at precision θ² / 4, then
the hypothesis has error at most θ² / 4 + θ L.
The samples are accurate with high probability: m samples fail to be accurate at
precision θ² / 4 with probability at most 2 (n + 2) 2 ^ n exp (-m θ⁴ / 32) for n
coordinates.
The Kushilevitz–Mansour theorem [KM93]
O'Donnell, Theorem 3.38: for n coordinates, the Kushilevitz–Mansour algorithm
with threshold ε / (2 L) from m ≥ (512 L⁴ / ε⁴) log (2 (n + 2) 2 ^ n / δ) samples, hence
m (2 n + 3) membership queries (kmLearner_queriesAtMost), learns the Boolean functions whose
spectral norm, read as signs, is at most L, with error ε and confidence 1 - δ.
Learning decision trees with membership queries [KM93]
O'Donnell, Theorem 3.38: for n coordinates, the Kushilevitz–Mansour algorithm
with threshold ε / (2 L) from m ≥ (512 L⁴ / ε⁴) log (2 (n + 2) 2 ^ n / δ) samples, hence
m (2 n + 3) membership queries, learns the functions computed by decision trees with at most
L leaves, with error ε and confidence 1 - δ.
The Kushilevitz–Mansour theorem with its query count: under the hypotheses of
kmLearner_learns, the algorithm learns the functions of spectral norm at most L with
m (2 n + 3) membership queries for n coordinates.
Learning decision trees with membership queries, with the query count: under the
hypotheses of kmLearner_learns_decisionTree, the algorithm learns the functions computed by
decision trees with at most L leaves with m (2 n + 3) membership queries for n
coordinates.