バナッハ・バタフライ不変量:三項多項式閾値関数に対する影響適応型ワルシュ幾何

arXiv cs.LG / 2026/5/5

📰 ニュースDeveloper Stack & InfrastructureSignals & Early TrendsIdeas & Deep AnalysisModels & Research

要点

  • この論文では、ワルシュ・ハダマールのバタフライ因数分解に基づく、影響に適応するバナッハ幾何の尺度「Banach-Butterfly Invariant(BBT)」を提案し、各座標の影響に応じて層ごとの指数を割り当てます。
  • 影響の総量 I(f) によるJensen型の下界を導き、μ(f) が影響ベクトルに関して(順列を除いて)厳密にシュール凸であることを証明しています。
  • parity(パリティ)・majority(多数)・dictators(独裁者)といった代表的なブール関数に対して μ のスケーリング則を特徴付け、例えば parity では μ ~ 2^{-n/2}、majority では μ = 2^{-Theta(√n)}、dictators では μ = 2^{-1/2} となることを示します。
  • n ≤ 4 の認定済み三項ワルシュ閾値のテストベッドと、n = 5 の NPN-正準代表のサンプルを用いて、MILP による最小サポート証明書を計算し、μ が総影響が同じ関数どうしを識別できる一方で、最小サポートを n をまたいで常に単調に予測するわけではないことを示しています。
  • 併せて提出された適用論文では、この理論に触発された実数値 WHT(Walsh-Hadamard 変換)の「activation-energy」代理指標を LLM の圧縮/量子化に用い、wikitext-2 の perplexity を baseline の auto-round に比べ 15–58% 減らしました。ただし、この転移は定式化されたものではなく定性的です。

Abstract

本稿では、Walsh-Hadamard のバタフライ因数分解に対する、影響(influence)適応型の Banach 幾何学である Banach-Butterfly Invariant(BBT)を導入する。座標ごとの影響 mathrm{Inf}_l(f) をもつブール関数 f:\{-1,+1\}^n\to\{-1,+1\} に対して、BBT はバタフライ層 l に指数 p_l = 1+mathrm{Inf}_l(f) を割り当て、収縮不変量(contraction invariant) mu(f)=\prod_l 2^{-mathrm{Inf}_l/(1+mathrm{Inf}_l)} を与える。我々は Jensen による下界 log_2mu(f) \ge -I(f)/(1+I(f)/n) を証明し、さらに mu が影響ベクトル(ただし置換による同一視)に関して厳密に Schur-凸(Schur-convex)であることを示し、スケーリング類 mu\sim 2^{-n/2}(パリティ)、2^{-\Theta(\sqrt{n})}(多数決)、2^{-1/2}(ダミー変数)を得る。log_2mu は有理数だがフーリエ係数に対して多項式ではない一方、mu は代数的である。また、mu は総影響が同一の関数を分離でき(n=3 で 122 組)、同一総影響をもつ関数間を区別することができる。 付随する合成(synthesis)原稿から得られた、検証済みの n \le 4 の三値 Walsh-threshold ユニバースを有限のテストベッドとして用い、n=4 における全 65,536 個のブール関数について、厳密な MILP 最小支持証明(minimum-support certificates)を計算する(平均 6.42、最大 9、パリティの議論により全て奇数)。さらに n=5 では、我々が列挙した 616,126 個の NPN-正準代表(NPN-canonical representatives)のうち 10,000 個について計算する(OEIS A000370 と一致)。固定した総影響のもとでの条件付き Spearman の rho(mu,|\mathrm{supp}|) は、n=4 の最大ストラタでは +0.571 だが、関数一様サンプリングおよび NPN-正準サンプリングの両方で n=5 では -0.38 へと反転する。mu は妥当な Schur-凸な濃度不変量(concentration invariant)であるが、n をまたいだ最小支持に対する普遍的な単調予測子(universal monotone predictor)ではない。 付随する応用論文では、この理論に触発された実数値の WHT 活性化エネルギー代理(activation-energy proxy)について、W2A16 における 5 つの事前学習済み LLM で妥当性を検証し、バニラの auto-round に比べ wikitext-2 の perplexity を 15-58% 減少させることを示す。ブール理論から実数値代理への移転は定性的であり、形式的(formal)ではない。