用神经网络学习布尔函数非线性度，4-5变量准确率超95%。
Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks
- 用编码器结构的深度网络从真值表预测非线性度
- 4~5变量函数预测准确率高于95%
- 适合对布尔函数性质建模感兴趣的读者
本文研究了使用神经网络学习布尔函数非线性性质的可行性。我们训练编码器风格的深度神经网络，从真值表及其对应非线性值中学习预测非线性度。实验结果表明，深度神经网络在4变量和5变量布尔函数上预测准确率超过95%。尽管结果积极，并首次系统分析了该问题，但需指出：将方法推广到更多变量仍具挑战性，且在时间和空间复杂度上是否优于现有组合算法尚不明确。
原文摘要 · Abstract (English)
This paper investigates the learnability of the nonlinearity property of Boolean functions using neural networks. We train encoder style deep neural networks to learn to predict the nonlinearity of Boolean functions from examples of functions in the form of a truth table and their corresponding nonlinearity values. We report empirical results to show that deep neural networks are able to learn to predict the property for functions in 4 and 5 variables with an accuracy above 95%. While these results are positive and a disciplined analysis is being presented for the first time in this regard, we should also underline the statutory warning that it seems quite challenging to extend the idea to higher number of variables, and it is also not clear whether one can get advantage in terms of time and space complexity over the existing combinatorial algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。