datasheet2_Algorithmic Probability-Guided Machine Learning on Non-Differentiable Spaces.zip

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.

本研究阐明了将复杂性理论（complexity theory）引入机器学习（machine learning）的方法，可有效整合当前研究中看似互不相关的多个领域。研究表明，该模型驱动（model-driven）的方法所需训练数据量更少，且具备更强的泛化能力，同时对随机攻击展现出更高的鲁棒性。在算法空间（algorithmic space）中，元素的排序由其算法概率（algorithmic probability）决定，而算法概率自然产生于可计算过程（computable processes）。本研究针对以算法复杂性（algorithmic complexity）为参数的损失函数（loss function）在回归（regression）与分类（classification）任务中的应用场景，探究了离散算法空间的形态特征，证明了无需依赖可微性（differentiation），即可获得与深度学习（deep learning）等可微编程（differentiable programming）方法相近的实验效果。为此，本研究采用了可对两种方法进行对比的示例（由于算法复杂性估计需耗费大量计算资源，示例规模均较小）。本研究发现并报告了以下结论：1）借助算法复杂性，可在非光滑曲面（non-smooth surface）上成功开展机器学习任务；2）通过算法概率分类器（algorithmic-probability classifier）即可寻得最优解，由此在本质上离散的可计算性理论（computability theory）与本质上连续的优化数学理论之间搭建了桥梁；3）可定义并实现一种在非光滑流形（non-smooth manifolds）上开展的算法引导搜索方法；4）可借助针对算法搜索的利用策略与数值方法，对这类离散非可微空间（discrete non-differentiable spaces）进行遍历探索。具体应用场景包括：(a) 从数据观测中识别生成规则（generative rules）；(b) 解决图像分类（image classification）任务，相较于神经网络（neural networks），该方法对像素攻击（pixel attacks）具备更强的鲁棒性；(c) 在含噪声的连续常微分方程（Ordinary Differential Equation, ODE）系统问题中，从少量数据集里识别方程参数；(d) 基于(1)网络拓扑结构、(2)底层布尔函数、(3)入边数量这三个维度，对布尔NK网络（Boolean NK networks）进行分类。