返回学习路线

U20：频谱、噪声与查询学习 ​

题目 ​

1. 在均匀 $\{-1,1{\}}^3$ 上，完整列出 ${\mathrm{Maj}}_3$ 与奇偶 $x_1{x}_2{x}_3$ 的八个 Fourier 系数，求各坐标影响、总影响与 $\rho =0.8$ 的稳定性。
2. 解释 KKL、Friedgut junta 和多数最稳定中的量词与分布条件。为什么三位多数在 $\rho =1/2$ 下超过 $1/3$ 不违反多数最稳定？
3. 用 KM 的前缀质量公式求三位多数第一层两节点的质量。取 $\theta =0.4$，写估计误差、剪枝门槛和保留数量保证。说明 BLR 为什么不等于这个学习算法。

解答 ​

多数展开为

$${\mathrm{Maj}}_3=\frac{1}{2}(x_1+x_2+x_3-x_1{x}_2{x}_3).$$

空集和三个二元集合的系数都为零，三个单元集合各为 $1/2$，三元集合为 $-1/2$。奇偶只有三元集合系数为 $1$，其余七项为零。多数每位影响 $1/4+1/4=1/2$、总影响 $3/2$；奇偶每位影响 $1$、总影响 $3$。

多数稳定性为 $3\rho /4+{\rho }^3/4$，在 $0.8$ 时是 $0.728$；奇偶为 ${\rho }^3=0.512$。逐位翻转概率为 $(1-0.8)/2=0.1$，所以两者输出改变概率分别为 $0.136$ 与 $0.244$。

KKL 在均匀输入下保证存在一个坐标，其影响至少为绝对常数乘 $\mathrm{Var}(f)\log n/n$。junta 定理在给定误差 $\epsilon$ 后保证存在一个固定坐标集，大小至多指数于 $I(f)/\epsilon$，使只依赖该集的函数在均匀分布下近似 $f$。它不声称原函数精确只依赖这些坐标，也不直接给高效搜索算法。

多数最稳定先固定 $\rho ,\eta$ 与均值，再要求所有坐标影响至多相应阈值 $\tau$。平衡极限在 $\rho =1/2$ 时为 $1/3$，但三位多数最大影响为 $1/2$，并非趋于零。它的稳定性 $13/32$ 因而没有违背该渐近定理。

KM 的前缀 0 包含系数位置 001、010，各平方为 $1/4$，质量为 $1/2$；前缀 1 包含 100、111，质量也为 $1/2$。${\theta }^2=0.16$，每次估计误差控制到 $0.04$，保留估计至少 $0.12$ 的节点。含 $0.4$-显著系数的前缀真实质量至少 $0.16$，不会被剪掉；保留节点真实质量至少 $0.08$，每层至多 $12.5$ 个，整数意义下至多 $12$ 个，此小例实际只有两至四个。

前缀估计需要查询 $f(u,v)$ 与 $f(u^{\prime },v)$，共享后缀 $v$ 由算法主动指定。BLR 则查询一组加法三元组并检验线性等式，输出性质判定。二者都用 Fourier 分析，但目标、采样结构与输出信息不同。

验收标准 ​

• 使用 $\pm 1$ 输出和归一化 Fourier 系数，平方和恰为一
• 区分翻转概率 $\eta$ 与相关参数 $\rho =1-2\eta$
• 低影响、固定均值、固定噪声和规模极限的量词不遗漏
• KM 估计平方质量，不把系数正负抵消；访问模型确实允许共享后缀查询