找函数依赖的变量和判断是否只依赖少数变量，本质是同一问题。
Feature Selection and Junta Testing are Statistically Equivalent
- 用暴力枚举所有可能的k个变量组合来同时解决两个问题。
- 样本量下界为 Θ(1/ε (√(2^k log C(n,k)) + log C(n,k)))，最优。
- 适合研究布尔函数性质或数据特征筛选的学者参考。
对于一个函数 $f oken {0,1}^n \to {0,1}$， junta 测试问题要求判断该函数是否仅依赖于 $k$ 个变量；若如此，特征选择问题则要求找出这 $k$ 个变量。本文证明这两个任务在统计上等价：暴力算法——即对任意 $k$ 个变量的组合检查其是否与样本一致——在两者中均达到最优样本复杂度。最优样本数量为 Θ(1/ε (√(2^k log C(n,k)) + log C(n,k)))，其中 $\varepsilon$ 为误差容忍度，$C(n,k)$ 表示从 $n$ 个变量中选 $k$ 个的组合数。
原文摘要 · Abstract (English)
For a function $f \colon \{0,1\}^n \to \{0,1\}$, the junta testing problem asks whether $f$ depends on only $k$ variables. If $f$ depends on only $k$ variables, the feature selection problem asks to find those variables. We prove that these two tasks are statistically equivalent. Specifically, we show that the ``brute-force'' algorithm, which checks for any set of $k$ variables consistent with the sample, is simultaneously sample-optimal for both problems, and the optimal sample size is \[ Θ\left(\frac 1 \varepsilon \left( \sqrt{2^k \log {n \choose k}} + \log {n \choose k}\right)\right). \]
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。