Hernández-Orozco Santiago, Zenil Hector, Riedel Jürgen, Uccello Adam, Kiani Narsis A, Tegnér Jesper
Facultad de Ciencias, Universidad Nacional Autónoma de México, Mexico City, Mexico.
Oxford Immune Algorithmics, Oxford, United Kingdom.
Front Artif Intell. 2021 Jan 25;3:567356. doi: 10.3389/frai.2020.567356. eCollection 2020.
We show how complexity theory can be introduced in machine learning to help bring together apparently disparate areas of current research. We show that this model-driven approach may require less training data and can potentially be more generalizable as it shows greater resilience to random attacks. In an algorithmic space the order of its element is given by its algorithmic probability, which arises naturally from computable processes. We investigate the shape of a discrete algorithmic space when performing regression or classification using a loss function parametrized by algorithmic complexity, demonstrating that the property of differentiation is not required to achieve results similar to those obtained using differentiable programming approaches such as deep learning. In doing so we use examples which enable the two approaches to be compared (small, given the computational power required for estimations of algorithmic complexity). We find and report that 1) machine learning can successfully be performed on a non-smooth surface using algorithmic complexity; 2) that solutions can be found using an algorithmic-probability classifier, establishing a bridge between a fundamentally discrete theory of computability and a fundamentally continuous mathematical theory of optimization methods; 3) a formulation of an algorithmically directed search technique in non-smooth manifolds can be defined and conducted; 4) exploitation techniques and numerical methods for algorithmic search to navigate these discrete non-differentiable spaces can be performed; in application of the (a) identification of generative rules from data observations; (b) solutions to image classification problems more resilient against pixel attacks compared to neural networks; (c) identification of equation parameters from a small data-set in the presence of noise in continuous ODE system problem, (d) classification of Boolean NK networks by (1) network topology, (2) underlying Boolean function, and (3) number of incoming edges.
我们展示了如何将复杂性理论引入机器学习，以帮助整合当前研究中明显不同的领域。我们表明，这种模型驱动的方法可能需要更少的训练数据，并且由于对随机攻击具有更强的恢复能力，可能具有更强的通用性。在算法空间中，其元素的顺序由其算法概率给出，该概率自然地源于可计算过程。我们研究了在使用由算法复杂性参数化的损失函数进行回归或分类时离散算法空间的形状，证明了实现与使用深度学习等可微编程方法获得的结果相似的结果并不需要可微性。在此过程中，我们使用了一些示例，以便能够比较这两种方法（由于估计算法复杂性所需的计算能力，示例规模较小）。我们发现并报告：1）使用算法复杂性可以在非光滑表面上成功进行机器学习；2）可以使用算法概率分类器找到解决方案，从而在根本上离散的可计算性理论与根本上连续的优化方法数学理论之间架起一座桥梁；3）可以定义并进行非光滑流形中的算法导向搜索技术的公式化；4）可以执行用于算法搜索以导航这些离散不可微空间的利用技术和数值方法；在应用中，（a）从数据观测中识别生成规则；（b）与神经网络相比，对像素攻击更具恢复能力的图像分类问题的解决方案；（c）在连续常微分方程系统问题存在噪声的情况下，从小数据集中识别方程参数；（d）通过（1）网络拓扑、（2）底层布尔函数和（3）入边数量对布尔NK网络进行分类。
