要旨: 高次の U-統計は、統計学、機械学習、計算機科学などの分野に数多く存在しますが、実際に計算しようとすると非常に計算時間がかかることが知られています。広く見かけるにもかかわらず、その計算複雑性についての包括的な研究は驚くほど欠けています。本論文は、このギャップを埋めることを目的として、U-統計に関する計算面でのいくつかの結果を提示します。まず、m 次の U-統計から、次数が m を超えない V-統計の線形結合への、有用な分解を導出し、これらは一般に計算しやすいものです。次に、V-統計を厳密に計算することと、テンソル計算を高速化するために計算数学や量子計算でしばしば用いられる手法であるアインシュタイン総和規約（Einstein summation）との関連を探ります。第三に、U-統計カーネルに関連するあるグラフの木幅（treewidth）に基づいて、U-統計を厳密に計算する時間計算量に関する楽観的な見積もりを与えます。以上の要素により、(1) 一般の高次 U-統計を厳密に計算するための、はるかに実行時間効率の高い新しいアルゴリズム、そして (2) U-統計を計算する際の計算時間複雑性に関する、より簡潔な特徴付けが導かれます。本論文では、付随するオープンソース・パッケージとして exttt{u-stats} を、Python（https://github.com/zrq1706/U-Statistics-Python）および R（https://github.com/cxy0714/U-Statistics-R）の両方で開発しています。統計学における 3 つの例を通じて、 exttt{u-stats} が既存のベンチマークに比べて印象的な実行時間性能を達成することを示します。本論文はまた、2 つの目標を達成することも目指します: (1) 統計学および関連する他分野の研究者の関心を喚起し、U-統計のアルゴリズム開発をさらに発展させること、そして (2) 実務者にとって高次 U-統計を実装する負担を軽減することです。
高階U統計の計算と計算複雑性について、ちょうど（exactly）
arXiv stat.ML / 2026/4/1
💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisTools & Practical UsageModels & Research
要点
- 本論文は、高階U統計の計算複雑性に関する理解のギャップを埋めることを目的として、より効率的に計算できる方法に関する結果を導出し、その計算の難しさを明らかにする。
- m次のU統計を、一般に計算しやすい「低次以下のV統計」の線形結合として書き換える分解手法を提示する。
- V統計の厳密計算をEinstein summation（アインシュタインの総和規約）に結び付け、計算数学や量子計算で用いられるテンソル計算の加速技術との関連を示す。
- グラフ／ツリー幅（treewidth）の議論を用いることで、U統計を厳密に計算するための楽観的な時間複雑性の見積もりを与え、計算時間の振る舞いをより体系的に特徴付ける。
- 著者らはオープンソース実装（u-stats）をPythonおよびRで公開し、既存のベンチマークと比較して、統計的な例において実行時間が改善したことを報告する。
