Tsetlin 自动机算法的广义收敛性分析：概念学习的概率方法

Generalized Convergence Analysis of Tsetlin Automaton Based Algorithms: A Probabilistic Approach to Concept Learning

Tsetlin 自动机算法的广义收敛性分析：概念学习的概率方法

https://ojs.aaai.org/index.php/AAAI/article/download/33704/35859

摘要
Tsetlin机（TMs）因其能够通过命题公式学习概念，并在多个应用领域中展现出卓越的效率，而受到越来越多的关注。然而，关于TMs的收敛性证明，尤其是在广义情况下（输入超过两位）对AND操作符（文字的合取）的收敛性分析，仍然是一个未解决的问题。本文旨在填补这一空白，提出对基于Tsetlin自动机的机器学习算法进行全面的收敛性分析。我们引入了一种新颖的框架，称为概率概念学习（Probabilistic Concept Learning, PCL），该框架在简化Tsetlin机结构的同时，引入了专用的反馈机制以及文字特有的包含/排除概率。给定n个特征，PCL旨在学习一组合取子句Ci，每个子句均关联一个独立的包含概率pi。最重要的是，我们建立了理论证明，确认对于任意子句Ck，当0.5 < pk < 1时，PCL将收敛至一个文字的合取表达式。该结果为未来研究基于Tsetlin自动机的学习算法的收敛性质提供了重要基础。我们的研究不仅增进了对这类算法的理论理解，也对其实际应用具有重要意义，有望推动构建更鲁棒且可解释的机器学习模型。

引言
概念学习是一种从实例中推断布尔函数的机制，其理论基础源于经典机器学习（Valiant 1984；Angluin 1988；Mitchell 1997）。现代的一种实现形式是Tsetlin机（TM）（Granmo 2018），它利用Tsetlin自动机（TAs）（Tsetlin 1961）生成作为合取子句的布尔表达式。与深度神经网络的“黑箱”特性不同，TMs因其基于析取范式（DNF）的内在可解释性而备受关注（Valiant 1984）。近年来，基础TM的多种扩展形式相继提出，包括用于卷积的架构（Granmo等，2019）、回归模型（Abeyrathna等，2020）以及其他多种变体（Seraj、Sharma和Granmo 2022；Sharma等，2023；Abeyrathna等，2021，2023）。这些进展已在情感分析（Yadav等，2021）和新颖性检测（Bhattarai、Granmo和Jiao 2022）等领域展现出重要应用价值。

证明机器学习模型的收敛性至关重要，因为它保证了模型的可靠性和稳定性，确保模型能够达到一个一致的解（Shalev-Shwartz 等，2010；Berkenkamp 等，2017）。它还有助于算法的开发与评估，为性能提供理论上的基准，并帮助理解模型的局限性。对Tsetlin机（TMs）的收敛性分析揭示了其在1位（Zhang 等，2022）和2位情况（Jiao、Zhang 和 Granmo 2021；Jiao 等，2023）下的已验证行为，涵盖了AND、OR和XOR操作符。然而，对于更一般的情况，尤其是当输入位数更多时，实现收敛面临显著挑战。问题的核心在于TMs学习机制中基于子句的文字之间的相互依赖性。本质上，一个文字所接收到的反馈会受到同一子句中其他文字的影响。这种相互依赖性，加上文字组合数量的巨大可能性，使得对TMs建立一般性证明变得更加困难。

我们的工作引入了一种创新的Tsetlin机变体——用于概念学习的文字概率性包含方法（Probabilistic inclusion of literals for Concept Learning, PCL）。PCL的设计允许文字被独立地更新和分析，这与标准Tsetlin机的行为形成鲜明对比。这一目标通过调整反馈表来实现：在训练过程中排除子句的取值，并省略“不作为”状态转移。此外，PCL为各个子句采用专用的包含概率，以使所学习的模式更加多样化。最重要的是，我们提供了证据，表明在特定前提条件下，PCL的子句能够收敛到任意期望的文字合取表达式。我们的论断得到了实验结果的支持，以验证理论发现，并展示PCL在选定实际问题（二分类IRIS数据集）上的行为表现。最后，需要强调的是，我们关于PCL收敛性的证明并不意味着原始Tsetlin机也具有收敛性，但它为基于Tsetlin自动机的学习算法的潜在证明奠定了坚实的基础，并勾画出一条清晰的研究路径。

PCL：用于概念学习的文字概率性包含

对正样本的反馈

对负样本的反馈

PCL训练算法

PCL 与 TM 的对比

在将 PCL 与标准 Tsetlin 机（TM）进行对比时，一个主要区别在于：在 PCL 中，子句内所有文字对应的 Tsetlin 自动机（TA）均独立更新。这种对文字的个体化处理方式，简化了理论收敛性分析的复杂度，相较于传统的 TM 更为清晰。即使采用更精细的学习方法，PCL 的收敛性证明也深入揭示了学习概念的本质，从而增强了对 TM 家族算法的理论理解。

PCL 收敛性证明

实验评估

在本节中，我们首先对PCL进行评估以验证其理论结果，然后测试其在选定实际问题上的表现。

收敛性测试

在已建立定理1中PCL理论收敛性的基础上，本节旨在通过实证测试来证实这些理论发现。我们的实验目标可以简洁地表述为：“给定所有可能的组合作为训练样本（即共2ⁿ个样本），如果我们运行PCL 100次（每次使用一个子句Ck和包含概率pk），每次运行采用不同随机生成的目标合取式CT，并设置不同的训练轮数（epochs），那么PCL成功学习到目标合取式CT的频率是多少？” 为简便起见，我们将pk记为p。

实验1：固定包含概率（图3(a)）

在本实验中，包含概率p被固定为0.75，该值位于0.5与1.0之间。我们观察在不同特征数量n的情况下，随着训练轮数的增加，PCL成功学习的平均次数（基于10次独立运行的平均值）。我们观察到以下现象：

• 随着训练轮数的增加，PCL始终能够收敛到目标合取式，在训练轮数较大时成功率达到100%。

• 当n = 8时，PCL在第1000轮训练时几乎能识别全部100个目标；甚至在600轮时，成功率已超过90%。

该性能结果支持了定理1中的论断，表明PCL在无限时间范围内具备收敛能力。

实验2：变化包含概率（图3(b)）

在本实验中，我们将特征数量固定为n = 4，而改变包含概率pk（记为p），并绘制不同训练轮数下成功学习的平均次数（基于10次独立运行的平均值）。我们观察到以下现象：

• 当p < 0.5时，PCL难以学习目标，各训练轮次的成功率均接近于零。

• 当0.5 < p < 1时，PCL表现出显著改善，尤其随着训练轮数的增加，成功率持续上升。

• 有趣的是，当p = 1时，成功率反而下降，表明此时无法实现收敛。

总体而言，我们的实验结果强有力地支持了定理1，强调PCL在区间0.5 < pk < 1内表现出收敛性。

PCL 与 TM 在学习文字合取式上的对比

在本分析中，我们使用无噪声的样本数据，比较 PCL 与 TM 在学习文字合取式方面的能力。PCL 和 TM 均被限制为仅使用一个子句，并训练 100 个轮次（epochs）。对于每种方法，我们训练了两个不同的模型：TM-a（s = 1.0）和 PCL-a（p = 0.95），这两个模型在所有训练轮次中使用完整的真值表进行训练；以及 TM-b（s = 1.1）和 PCL-b（p = 0.7），这两个模型在每一轮中随机选择两个样本进行训练，其中一个为正样本，一个为负样本。各模型参数的选择过程详见附录。表7展示了在不同输入位数 n 的情况下，各模型的收敛得分（如前一节所定义），结果为10次独立运行的平均值。显然，TM-b 由于使用了平衡的训练集，在大多数情况下成功学习了合取式；而 PCL-b 也取得了可比的结果，成功率保持在90%至98%之间。当使用完整真值表进行训练时，TM-a 在学习合取式方面优于 PCL-a。然而，随着 n 的增加，两者之间的性能差距逐渐缩小（例如，当 n = 11 和 n = 12 时，PCL-a 平均学习到的合取式数量超过了 TM-a）。

PCL 在二分类 IRIS 数据集上的应用

在本实验中，我们使用 PCL 作为分类工具，利用其析取范式（DNF）输出来展示其在真实世界问题——二分类 IRIS 上的表现。原始 IRIS 数据集包含150朵鸢尾花，分为三个物种。在二分类设置中，我们将其中一个类别 C 设为“真”，其余两个类别视为“假”（非C）。我们使用 sklearn 的二值化工具将4个原始特征转换为16个二进制特征。数据集按70%用于训练、30%用于测试进行划分。状态转移概率（即 pi 值）在区间 [0.6, 0.8] 内均匀随机选取。我们运行 PCL 10,000 次，每次训练100个轮次，并尝试不同数量的子句。图4(b) 显示了每个子句数量下的平均准确率及其标准差。值得注意的是，从6个子句开始，PCL 的准确率稳定收敛至92%以上，标准差约为0.04。此外，图4(a) 展示了使用10个子句时在10,000次运行中的准确率分布。显然，大多数运行的准确率超过80%（约5,000次运行的准确率超过94%），突显了我们方法行为的一致性和非随机性。在执行时间方面，单次运行耗时不到20毫秒，这得益于 PCL 简单的状态更新机制，体现了其高效性。

此外，我们将 PCL 的性能与标准 Tsetlin 机（TM）以及其他几种成熟的机器学习算法在二分类 IRIS 上的表现进行了比较，结果详见表8。值得注意的是，PCL 仅使用10个子句和100个训练轮次就取得了具有竞争力的结果。需要说明的是，PCL 报告的准确率是10,000次运行的平均值。其他方法均采用其默认实现参数，而 TM 使用了300个子句，并设置了特定参数（s = 2, T = 10），训练100个轮次。考虑到 PCL 分类器仅使用简单的 DNF 结构，这一结果是令人鼓舞的。

局限性

PCL的主要局限性与Tsetlin机（TM）类似，包括在每个分类问题中都需要对输入进行二值化处理。此外，目前PCL尚不支持多分类问题，除非为每个类别单独构建二分类器。另外，PCL当前的局限性也使其难以与最先进的分类器相竞争。

结论

在本研究中，我们提出了PCL，一种基于Tsetlin自动机的创新方法，用于生成布尔表达式。PCL的独特之处在于，通过为每个子句引入专用的包含概率，简化了Tsetlin机（TM）的训练过程，从而增强了所识别模式的多样性。PCL的一个显著特点是，其在满足特定条件的情况下，能够在无限时间范围内收敛到任意文字的合取式——这一结论得到了我们实验结果的支持。这一关键性证明为更广泛的Tsetlin机家族的收敛性分析奠定了坚实的基础。我们的理论洞察预示着PCL在应对现实世界挑战方面的潜在适应性。展望未来，我们的目标是增强PCL的能力，以支持多分类任务，并在更多实际应用场景中严格检验其有效性。

原文链接： https://ojs.aaai.org/index.php/AAAI/article/download/33704/35859