提出线性复杂度方法，高效估算互信息并检测依赖关系。
Linear cost mutual information estimation and independence test of similar performance as HSIC
- 用混合矩描述依赖，计算仅需O(n)时间
- 在相同精度下比HSIC快，支持高维依赖检测
- 适合大数据与高维分析场景
数据科学与机器学习中评估两组数据样本间的统计依赖是基础问题，当前最优方法为希尔伯特-施密特信息准则（HSIC），但其对大小为n的数据需进行n×n矩阵乘法，计算复杂度约为O(n².³)，难以处理大规模数据。本文提出一种线性成本的实用替代方案HCR（层次相关重构），在依赖检测上灵敏度更高，并可给出指定显著性水平下的联合分布模型。通过特征表示依赖关系，从相关性和同方差性开始，逐步扩展至更复杂的混合矩。互信息可近似为这些非平凡混合矩平方和。单个依赖特征计算耗时仅为O(n)，所需特征数量随维度d变化：成对依赖需O(d²)，三元依赖则需O(d³)。
原文摘要 · Abstract (English)
Evaluation of statistical dependencies between two data samples is a basic problem of data science/machine learning, and HSIC (Hilbert-Schmidt Information Criterion)~\cite{HSIC} is considered the state-of-art method. However, for size $n$ data sample it requires multiplication of $n\times n$ matrices, what currently needs $\sim O(n^{2.37})$ computational complexity~\cite{mult}, making it impractical for large data samples. We discuss HCR (Hierarchical Correlation Reconstruction) as its linear cost practical alternative, in tests of even higher sensitivity to dependencies, and additionally providing actual joint distribution model for chosen significance level, by description of dependencies through features being mixed moments, starting with correlation and homoscedasticity. Also allowing to approximate mutual information as just sum of squares of such nontrivial mixed moments between two data samples. Such single dependence describing feature is calculated in $O(n)$ linear time. Their number to test varies with dimension $d$ - requiring $O(d^2)$ for pairwise dependencies, $O(d^3)$ if wanting to also consider more subtle triplewise, and so on.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。