概率 Tsetlin 机：一种新的不确定性量化方法

The Probabilistic Tsetlin Machine: A Novel Approach to Uncertainty Quantification

概率 Tsetlin 机：一种新的不确定性量化方法

https://arxiv.org/abs/2410.17851

摘要

图灵机（TMs）已成为传统深度学习方法的有力替代方案，具有内存占用小、推理速度快、容错性强和可解释性高等显著优势。尽管TMs的多种改进已拓展其在各领域的应用，但对其预测中不确定性量化的理解仍存在根本性空白。为此，本文提出概率图灵机（PTM）框架，旨在提供一种稳健、可靠且可解释的不确定性量化方法。与原始TM不同，PTM学习每个子句中各个图灵自动机（TA）在各状态停留的概率，并利用TM框架中的I型和II型反馈表更新这些概率。在推理过程中，TA基于所学习的概率分布进行状态采样以决定动作，类似于贝叶斯神经网络（BNN）生成权重值的方式。在实验分析中，我们首先展示了PTM在噪声XOR数据集上TA状态概率的分布情况；随后在模拟和真实世界数据集上将PTM与基准模型进行比较。模拟数据集的实验结果表明，PTM在不确定性量化方面表现优异，尤其在划分决策边界和识别高不确定性区域方面效果显著。此外，在使用Iris数据集进行多分类任务时，PTM在预测熵和期望校准误差方面表现出具有竞争力的性能，展现出其作为可靠不确定性估计工具的潜力。我们的研究结果强调了在预测任务中选择合适模型以实现准确不确定性量化的重要性，而PTM提供了一种尤为可解释且有效的解决方案。

关键词：概率图灵机 · 图灵机 · 不确定性量化

1 引言

图灵机（TMs）是当前深度学习方法的一种有前景的替代方案（Granmo, 2018）。最初，TMs能够在二值特征条件下以与最先进机器学习方法相竞争的性能完成分类任务。随后，为应对不同领域中的广泛挑战，提出了多种TMs的变体。这些变体适用于连续输入输出场景（Darshana Abeyrathna 等, 2020）、确定性学习过程（Abeyrathna 等, 2020）、自然语言处理（NLP）应用（Saha 等, 2021；Bhattarai 等, 2022）、图像分析任务（Granmo 等, 2019），以及紧凑模式表示任务（Abeyrathna 等, 2021b）。

此外，由于TMs相较于最先进的机器学习方法具备多项优势，如更小的内存占用（Granmo 等, 2019；Abeyrathna 等, 2020）、更快的推理速度（Wheeldon 等, 2020b）、容错性（Shafik 等, 2020）以及可解释性（Wang 等, 2017；Abeyrathna 等, 2021b），基于TM的硬件已得到实现并经过严格测试，证明了其在实际应用中的可行性和有效性（Mao 等, 2022）。这些硬件实现充分利用了TM固有的并行性和结构简单性，使其非常适合实时和资源受限环境（Wheeldon 等, 2020a）。

尽管TMs在多个领域具有广泛适用性并具备实际优势，但对其预测中如何量化不确定性仍缺乏深入理解。尽管已有部分研究探讨了图灵机的不确定性量化问题（Abeyrathna 等, 2023a,b），但这些工作仅限于连续值预测应用。在本研究中，我们提出概率图灵机（PTM）作为一种新颖的不确定性量化框架——一种更稳健、可靠且可解释的方法，可适配上述多种TMs变体。我们首先在第3节讨论基本的TM理论，并正式引入PTM，涵盖为获得概率输出所需对TM进行的修改，这也是本研究的主要贡献。第2节讨论不确定性量化的重要性。第5节中，我们使用人工和真实世界数据进行了实验。最后在第6节总结研究发现。

2 不确定性量化

概述：在科学领域中对不确定性进行建模并非人工智能（AI）所独有，也不是当代才出现的问题。早在17世纪，惠更斯（Huyghens）、帕斯卡（Pascal）、梅雷骑士（Chevalier de Meré）和雅各布·伯努利（Jacques Bernoulli）等学者就在其著作中提及了这一概念。随着计算机科学的发展，知识表示与推理中因不精确性、不确定性和信息冲突所带来的挑战逐渐显现。然而，直到20世纪80年代之前，这些问题的讨论仍独立于概率论和决策理论之外（Denœux 等, 2020）。

在过去几十年中，人工智能在应用科学领域的潜力日益凸显（Abdar 等, 2022）。然而，在错误代价较高的领域（如医疗、自动驾驶等），AI系统必须能够估计自身的不确定性，以做出安全的决策。因此，对于基于AI的预测模型而言，不确定性量化是衡量模型在领域知识有限、数据不完整或含噪声、或系统本身存在内在随机性等情况下，其预测的置信度或可靠性的重要指标，并有助于增强人们对预测结果的信任（Seoni 等, 2023）。

不确定性估计的一种常见分类方式是将其分为两类：一类是由AI模型自身引起的不确定性，例如训练数据表示不佳或知识不足所导致的；另一类则是由数据本身引起的不确定性，例如数据信息不足、不完整、相互冲突或含有噪声。前者称为认知不确定性（epistemic uncertainty），后者称为偶然不确定性（aleatoric uncertainty）（Der Kiureghian 和 Ditlevsen, 2009）。认知不确定性可以通过增加训练数据或改进模型结构来减少，而由数据本身引起的偶然不确定性则是不可消除的（Gawlikowski 等, 2021）。

不确定性可通过两种常用方法进行量化：集成学习（ensemble learning）和概率机器学习（probabilistic machine learning）。后者也称为贝叶斯机器学习，它应用概率论从数据中提取信息（Ghahramani, 2015）。然而，概率方法在处理大规模或复杂数据及模型（如深度学习模型）时面临计算上的挑战。可通过使用近似方法（如变分推断和马尔可夫链蒙特卡洛方法）来估计后验分布，以缓解这一问题（Murphy, 2023）。但使用这些方法时，必须在计算成本与准确性之间进行权衡（Seoh, 2020）。集成学习方法则通过训练多个独立模型，最终预测结果由所有模型共同决定。为估计预测的不确定性，利用各模型之间的差异（发散程度）进行评估。集成学习方法也存在局限性，包括训练时间长、缺乏可解释性，以及对噪声数据和异常值敏感。

为了在输出空间为离散（记为 Y）的场景下定量评估模型的预测准确性和不确定性量化能力，我们采用以下几种指标：熵（entropy）、互信息（mutual information）和方差（variance）。这些指标专门用于衡量模型的不确定性。对于每个测试样本 xi，这些量的计算方式如下：

评估指标：

预测均值（Predictive Mean）：对每个测试样本，我们使用每个模型生成 K 个预测样本。预测均值表示这 K 个样本中预测概率的平均值，作为目标值的点估计。其计算公式如下：

预测熵与互信息 ：它们可用于分别估计总不确定性与认知不确定性（Depeweg 等, 2018）。总不确定性可通过预测熵进行量化，如下所示：

3 图灵机（Tsetlin Machines）

结构：根据具体任务的不同，需要采用合适的图灵机（TM）配置。例如，若目标是将样本分为两类，则可使用专为二分类设计的基础TM。该基础TM也是大多数其他TM变体的基础，例如多分类图灵机（MTM）（Granmo, 2018）、回归图灵机（RTM）（Darshana Abeyrathna 等, 2020）和卷积图灵机（CTM）（Granmo 等, 2019）。在本文中，我们使用用于二分类任务的基础TM（以下简称TM）来解释概率图灵机（PTM），而其核心概念同样适用于所有其他TM变体。

TM解决模式分类问题的方式是：通过一组学习得到的子模式来表示各个类别。在TM中，这些子模式由“子句”（clauses）表示，每个子句是若干“文字”（literals）的逻辑与（合取）。TM接收二值形式的特征输入，因此，每个文字指的是某个命题变量本身或其否定形式。TM使用 m 个子句来学习模式，其中一半子句用于识别属于类别1的模式，另一半则学习类别0的模式。

数学上，一个子句可表示为：

4 概率图灵机（Probabilistic Tsetlin Machines）

5 实验与结果

本节介绍我们开展的实验及其所得结果。首先，我们介绍用于与所提出的概率图灵机（PTM）进行比较的基准方法。接着，我们展示在噪声XOR数据集上，不同图灵自动机（TAs）的概率向量的表现形式。最后，我们利用合成数据和真实世界数据，展示PTM相较于基准方法在不确定性量化方面的准确程度。

5.1 基准方法

我们将所提出的PTM与不同的机器学习技术进行比较，这些技术用于不确定性量化：

• 高斯过程（GP）：高斯过程（Williams 和 Rasmussen, 2006）是一种贝叶斯非参数学习方法，适用于回归和分类问题。它基于观测数据对可能函数的概率分布进行建模。高斯过程由一个均值函数和一个协方差或核函数定义，这两个函数决定了数据点之间的相似性。

• 带蒙特卡洛丢弃的多层感知机（MLP-MCd）：MLP-MCd 是一种神经网络技术，它不仅在训练过程中使用丢弃层以实现正则化，而且在推理过程中也使用丢弃层以估计不确定性（Gal 和 Ghahramani, 2016）。通过多次前向传播并随机失活神经元，MLP 生成输出的分布，从而揭示模型的不确定性。

• 随机森林（RF）：随机森林（Breiman, 2001）是一种集成机器学习技术，涉及构建多个决策树并将它们的预测结果组合起来，以获得带有置信度度量的输出。随机森林通过一种称为“装袋法”（bagging）的技术来运行，该技术有助于减少方差而不增加偏差。此外，随机森林在构建树的过程中，在每个分裂点处使用特征的随机子集。

5.2 噪声XOR数据集的稳态概率（SSPs）

为了说明概率向量的形态，我们使用了噪声XOR数据集的一个变体，该数据集最初由Granmo (2018)提出。在此改编版本中，我们去除了冗余特征，并在XOR输出中引入了30%的随机反转。随后，我们要求PTM仅使用4个子句（m = 4），每个子句专注于一个特定模式，来学习类别1和类别0的独特模式。

作为参考，无噪声情况下的分布如图1所示。在这里，TA-1、TA-2、TA-3和TA-4分别就字面量x₁、¬x₁、x₂和¬x₂的包含与排除做出决策。正如预期的那样，c₁和c₃识别出类别1的模式，而c₂和c₄学习类别0的模式。例如，c₁通过在子句中包含¬x₁和x₂来捕捉模式(0, 1)，因此当样本中x₁为0且x₂为1时，输出为1。

与数据无噪声时观察到的清晰直接的字面量包含和排除不同，TA会调整其表示形式以适应噪声数据中固有的不确定性，这一点在图2中显而易见。尽管根据先前关于子句分配给类别的知识，人们可能会假设c₁已学会模式(0, 1)，而c₃学会了模式(1, 0)，但这些模式的确切构成可能会变化。换句话说，即使明显看出c₁的子句中包含了¬x₁和x₂，c₃的子句中包含了x₁和¬x₂，但由于其他TA的状态之间共享概率，导致这些模式可能因其他TA的决策而受到干扰。

5.3 使用合成数据集的说明

我们的实验分析使用了一个简单的模拟数据集来评估模型，该数据集包含1000个带标签的示例。该数据集中的每个数据点包含两个特征，记作X₁和X₂，并被赋予两个标签之一：0或1。为了评估模型并深入了解其性能，我们生成了2000个额外的未标记测试示例。这些测试示例在比训练数据点更广泛的范围内随机分布。该数据集如图4所示。

在图3中，展示了PTM的预测结果与不确定性量化与其他基准模型的对比。如前所述，针对每个测试点，使用100个预测样本计算预测均值、熵和标准差。每个子图表示所获得数值的插值曲面。预测均值表明所有模型都能有效区分两个类别。值得注意的是，PTM和GP模型准确地捕捉了两个类别的分布情况。特别是，PTM根据输入值对某些决策边界进行了明确划分。MLP-MCd模型实现了一个线性分类器，而随机森林（RF）模型则将输入空间划分为四个不同的区域。

由熵表示的总不确定性显示，PTM和GP模型在训练数据覆盖范围之外的区域表现出较高的不确定性。相比之下，MLP-MCd模型仅在决策边界附近表现出高不确定性，而在其他区域的不确定性非常低。RF模型将输入空间划分为四个区域，在没有训练数据的区域表现出高不确定性，在有训练数据的区域则表现出低不确定性。然而，与PTM和GP不同，RF模型在超出训练数据实际覆盖范围的区域也表现出较高的置信度。

我们得出结论：MLP-MCd模型所提供的不确定性量化可能会产生误导，因为它在无数据区域表现出高度自信。此外，尽管随机森林（RF）模型能够有效地区分两个类别，但它有时在本应具有较高不确定性的区域表现出较低的不确定性。高斯过程（GP）和PTM模型提供了良好的不确定性量化，其中PTM的不确定性尤其具有可解释性。该分析强调了在预测任务中选择合适模型以实现准确不确定性估计的重要性。

5.4 使用鸢尾花数据集进行多分类

在本节中，我们评估多分类PTM在鸢尾花（Iris）数据集上的性能，并将其与高斯过程（GP）、带蒙特卡洛丢弃的多层感知机（MLP-MCd）以及随机森林（RF）进行比较。我们将数据集的80%用于模型训练，其余20%用于测试。评估指标包括预测熵、互信息和期望校准误差（ECE）。

图5展示了实验结果，表明对于错误预测，预测熵和互信息均显著更高，这符合良好概率模型的预期行为。表6列出了各模型的ECE值，其中数值越低表示模型校准效果越好。表中的ECE值表明所有模型均具有良好的校准性能。

6 结论

总之，本文提出的概率型Tset林机（Probabilistic Tsetlin Machine, PTM）框架为解决Tsetlin机在预测任务中不确定性量化这一挑战提供了一种有前景的解决方案。通过实验分析，我们证明了PTM在准确量化不确定性方面的有效性。在模拟数据集和真实世界数据集上的实验表明，PTM在预测熵和期望校准误差方面表现出具有竞争力的性能。未来，进一步探索PTM的能力，并将其应用于多样化的数据集和领域，可能会为应对复杂预测挑战并提供透明的不确定性估计带来有价值的见解。当充分发挥其潜力时，PTM不仅能够计算不确定性估计，还能够解释不确定性高低的原因，使其在那些错误预测代价高昂的各类应用领域中成为一项宝贵的工具。

原文链接：https://arxiv.org/pdf/2410.17851