自组织神经图：决策树与图结合的高效训练方法

38480SONGs: 自组织神经图0Łukasz Struski 1 Tomasz Danel 1 Marek  ´ Smieja 1 Jacek Tabor 10Bartosz Zieli´nski 1 , 201  数学与计算机科学学院，克拉科夫雅各隆大学，波兰 2  IDEAS NCBR，华沙，波兰0{lukasz.struski;marek.smieja;jacek.tabor;bartosz.zielinski}@uj.edu.pl0{tomasz.danel}@doctoral.uj.edu.pl0摘要0近年来，研究人员在深度神经网络与其他方法（包括决策树和图）的结合方面取得了突破。将决策树和图结合起来至少有三个优点：它们易于解释，因为它们基于顺序决策；它们可以更快地做出决策；它们提供了一个类别的层次结构。然而，与决策图相比，决策树的一个众所周知的缺点是决策树不能重复使用决策节点。然而，由于缺乏高效的基于梯度的训练技术，决策图在深度学习中并不常用。在本文中，我们填补了这一空白，并提供了一个基于马尔可夫过程的通用范例，允许高效训练一种特殊类型的决策图，我们称之为自组织神经图（SONG）。我们在Letter、Connect4、MNIST、CIFAR和TinyIm-ageNet数据集上进行了理论研究，并进行了实验证明我们的方法在性能上与现有的决策模型相当或更好。01. 引言0神经网络（NNs）和决策树（DTs）是两种具有丰富而成功的机器学习历史的强大模型。然而，它们通常具有互斥的优势和限制。NNs通过共同学习表示和分类数据来优于传统流程[15]。然而，它们普遍不透明，并且缺乏透明度和可解释性[30]。另一方面，DTs的预测很容易解释，因为它们依赖于相对较短的决策序列[38]。然而，它们通常不像深度神经网络那样具有很好的泛化能力[8]。因此，最近的研究重点放在结合两者的优点上0两种模型都使用了[2, 8, 13, 23, 24, 34, 36,38]。有一些方法将神经网络和软决策树结合起来，每个节点都有部分成员资格[8, 13, 24,34]。其他方法使用树来解释神经网络[5,39]或获取其最佳分层结构[2, 23,36]。最后，一些模型将神经网络的最后一个softmax层替换为分层二叉决策树[20, 21,38]。虽然决策树可以提高神经网络的性能和可解释性，但它们通常在深度方面遇到指数级增长[32]、重复节点[8]和次优结构的问题，通常在训练之前手动选择[38]。因此，越来越多的注意力放在将神经网络与决策图结合起来，而不是树[4, 9,11, 22,37]。决策图与决策树相比具有一些优势。它们具有灵活的结构，允许从根到每个叶子的多条路径。因此，节点被重复使用，从而产生更简单、更小的模型，解决了复制问题[27]。此外，决策图需要更少的内存，同时显著提高了泛化能力[33]。然而，由于缺乏高效的基于梯度的训练技术，决策图在深度学习中并不常用。在本文中，我们介绍了自组织神经图（SONGs），这是一种特殊类型的决策图，可以推广像软决策树（SDT）[8]和神经支持决策树（NBDT）[38]这样的方法，并且作为可微分的解决方案适用于任何深度学习流程。此外，与现有方法的固定结构相比[8,38]，SONGs可以在训练过程中加强或减弱任意一对节点之间的边，以优化它们的结构。我们在图1中说明了这个过程。开始时，边的权重是随机的。然而，在训练的连续步骤中，通过反向传播来纠正结构，并且它变得稀疏并收敛到二进制有向无环图[28]。我们的贡献可以总结如下：•我们介绍了自组织神经图（SONGs）38490r0v 1 v 20l 1 l 20x0NN0y 1 y 20反向传播0(a) 随机初始化0r0v 1 v 20l 1 l 20x0NN0y 1 y 20(b) 中间阶段0r0v 1 v 20l 1 l 20x0NN0y 1 y 20(c) 训练后的SONG0图1：SONG的训练阶段，使用梯度下降来修改图结构和转移概率。基于输入x，骨干神经网络（NN）提取一个向量表示，传递给SONG以获得每个类别的预测（y 1和y 2）。在训练开始时，图具有根节点r，节点v 1和v 2，叶节点l 1和l2，并且具有随机初始化的边（a）。在连续的训练迭代中，边权重的熵增加（b），最终得到一个稀疏的二进制图，每个节点有两条强边出去（c）。请注意，SONG包含两组节点之间的两组备选边（虚线蓝箭头和实线红箭头），根据输入进行组合（详见图2）。0一种基于马尔可夫过程的端到端训练新范式，可以同时学习最优图结构和转移概率。0• 我们的模型完全可微分，因此适合与其他深度学习模型进行联合训练。0•我们通过实证和理论证明，SONG在训练过程中收敛到稀疏的二进制有向无环图0•我们的方法在类似设置中表现出色，超过或与训练的决策树相当，并且不需要在训练之前预定义图/树结构。02. 相关工作02.1. 决策树0多年来，已经开发了许多决策树（DT）算法[18，19，29，31]，在深度学习取得成功之后，许多研究与将DT与神经网络相结合有关。因此，引入了软决策树（SDT），允许样本在构成树结构的节点中具有部分成员资格[34]，也在蒸馏设置中进行了训练[8]。这个想法也被用于[13]，该论文以端到端的方式训练一组分类树和一个骨干网络。此外，最近在[24]中使用了这个想法，使用具有原型节点[6]而不是分类器的节点来忠实地可视化模型。树还被用来解释先前训练的黑盒模型[5，39]。更先进的方法会以多步或端到端的方式自动生成具有树结构的深度网络[1，2，23，38]。许多先前的工作都被ANT框架[36]所泛化，该框架还使用变压器丰富了树结构，这是一个非线性函数0将样本从前一个模块映射到下一个模块的函数，允许训练树的拓扑结构。与这些方法相比，我们设计了一种简单而有效的模型，以端到端的方式训练决策图以及基础神经网络的参数。02.2. 决策图0决策图是一种经过深入研究的分类器，已经被用于解决许多现实世界的问题[35]。当实现为有向无环图（DAG）时，它能够提供准确的预测，同时具有较低的模型复杂性、子树复制和训练数据碎片化，相比决策树[33]。然而，大多数现有的学习DAG的算法涉及训练一个传统的树，然后将其转换为DAG[7，12，25，26]，因此很难直接应用于神经网络。因此，提出了替代方法，例如[4]，它保持标准卷积神经网络（CNN）的结构，但在每一层使用额外的路由损失来最大化类别纯度（类似于增长决策树），根据类别标签分布使用数据激活。另一种方法[37]引入了类似于ResNets[9]的身份跳连接，根据输入的门响应执行或跳过。类似的门机制在[22]中用于选择针对不同输入专门化的分支，其输出被组合以进行最终预测。最后，[11]将无限多个滤波器嵌入到由紧凑B样条参数化的低维流形中，并最大化样条位置和类别标签之间的互信息，以实现最佳的分类任务专业化。这样的38500与现有方法相比，SONG是一个有向图，可以适应任何深度架构，并以高效的基于梯度的方式进行训练，从而显著降低了运行时复杂性。03. 自组织神经图0为了充分描述自组织神经图（SONG），我们首先定义了一个更抽象的结构，称为软二进制有向图（SBDG）。SBDG被认为是二进制的，因为有两组备选边，而且是软的，因为这些组合成一个目标边集，取决于输入。然后，基于SBDG，我们定义SONG并描述如何将其用作决策模型。最后，我们介绍了方法的局限性，并展示了如何通过额外的正则化器来克服这些局限性。下面的定义对应于单标签分类，以便更清楚地描述。然而，它们可以很容易地扩展到其他任务，如多标签分类或回归。03.1. 方法03.1.1 软二进制有向图0软二进制有向图（SBDG）是一个有向图，可以看作是一个概率模型。它被定义为图 G = ( V, E 0 , E 1 ) ，其中 V对应于一组节点，E 0 ， E 1 对应于两组备选边，其中：0• 集合 V 包含两种类型的节点：0- 内部节点 v 0 ，...，v n ，其中 v 0 指定为根节点r ，0- 叶子节点 l 1 ，...，l c ，每个叶子节点都与集合 {1 ，...，c } 中的一个类别独占关联。0• 对于 d ∈ { 0 , 1 } ，集合 E d包含所有可能的边，其权重为 m d ji ，对应于从节点 u i移动到 u j ∈ V的概率，如图2a所示。接下来，将从节点 u i移动到其他节点的聚合概率称为转换向量，并表示为 m0• 如果 u i 是叶子节点，则 m d ji = δ ji （Kroneckerdelta），这意味着无法从叶子节点移出。0• 每个内部节点 u i 进行二进制决策 d ∈ { 0 , 1 }，使用来自集合 E d 的边的概率为 σ d i 。0• σ 0 i + σ 1 i = 1 ，并且通过将 m 0 ∙ i 和 m 1 ∙ i组合使用以下公式对每个节点 u i 进行转换，可以将 G转换为标准有向图：σ 0 i m 0 ∙ i + σ 1 i m 1 ∙ i。该过程如图2b所示。请注意，如果所有转换向量都是二进制的，则在去除概率为零的边之后，SBDG将变为二进制有向图[28]。03.1.2 自组织神经图0自组织神经图（SONG）是SBDG的全可微适应版本，可以与各种深度架构结合使用。SONG定义为 G = ( V , E 0 , E 1) ，其中 V ， E 0 ， E 1 实现了SBDG的 V ， E 0 和 E 1，并且通过以下方式获得输入点 x 的 V ， E 0 和 E 1 ：0• 节点 u i 中决策 d = 1 的概率由以下公式得到：σ 1 i (x ) = σ ( xw i + b i ) ，其中 σ 是sigmoid逻辑函数，w i是一个滤波函数，b i 是偏置项1。0• 决策 d = 0 的概率等于 σ 0 i ( x ) = 1 − σ 1 i ( x ) 。0• 从内部节点移动的概率由两个矩阵 M d = [ m d ji ] ∈ R (n + c ) × n 定义，其中 d = { 0 , 1 }，其具有正值并且列之和为1。在我们的实现中，我们通过对每列应用softmax来获得这样的矩阵。请注意，{ w i } i=1 ,...,n ，{ b i } i =1 ,...,n ，M 0 和 M 1是模型的可训练参数。最后，我们定义了一个针对输入 x生成的有向图 G x = ( V , E ) ，其中 E 对应于矩阵 M 0 和M 1 的组合：0M x = 1 σ T x ⊙ M 1 + 1 ( 1 − σ x ) T ⊙ M 0 ,0其中σx = [σ10(x), ..., σ1n(x)]T，符号⊙表示Hadamard乘积，1是维度为n的全1向量。03.1.3 决策模型0矩阵Mx包含从内部节点到图的所有节点的移动概率。然而，为了应用马尔可夫过程的理论，它需要通过对应于叶节点的列进行扩展（如图3左侧所示）：0Px = � M x 0 I0� ∈ R (n + c) × (n + c)，(2)0其中0∈Rn×c是零矩阵，I∈Rc×c是单位矩阵。因此，我们得到一个用于描述马尔可夫链转移的方阵。虽然Px包含从ui到uj在一个时间步长内移动的概率，但可以通过计算Px的N次幂来轻松获得N步的类似概率。最后，将得到的矩阵乘以向量v= [1, 0, ..., 0]T，以获得从根节点移动到图的任何节点的概率，包括叶节点，其概率是模型的输出。我们在图3的右侧提供了一个简单的示例来说明这个过程。更多示例请参见补充材料。01实际上，这个概率也可以用以sigmoid函数结尾的任何神经网络获得。0100000000000100100000100.70.2 0.50000.30.70.800.200000.50.500000100010σv =Pxv =P0.80.20.50.50.30.70.80.20.50.50.30.70.80.20.50.50.30.7rv1v2l1l2rrv1v1v2v2l1l2rrv1 v2l1l2rv1v2l1l2rv1 v2 l1l2M0, M1100%0%1 0 0 0 00 0.8 0.2 0 00 0 0.4 0.46 0.14TTT38510m 0 i0l 10l c0v 10v n0v i0r0r0v 10v i0v nl 10l c0m 1 i0m ni0m n +1, i0m n + c , i0m 0 i0m 1 i0m ni0m n +1, i0m n + c , i0m 01 r0v 10v i0v nl 10l c0m 1 i0m ni0m n +1, i0m n + c , i0m 0 i0m 1 i0m ni0m n +1, i0m n + c , i0（a）过渡向量0( x )0l 10l c0v 10v n0v i0r00 r0v 10v nl 10l c0m 0 i0m 1 i0m ni0m n +1, i0m n + c , i01 σ i01 σ i01 σ i01 σ i01 σ i0决0σ 0∙0（b）过渡向量的组合0图2：SONG包含两个备选的过渡向量m0∙i和m1∙i，它们汇总了从特定节点vi到所有其他节点的移动概率。在（a）中，它们分别表示为虚线蓝色箭头和实线红色箭头。每个节点获取输入数据x，并以使用一种过渡或另一种过渡的概率σ0i和σ1i做出二进制决策。由于σ0i + σ1i =1，SONG可以通过组合m0∙i和m1∙i转化为标准有向图，如（b）所示。在训练过程中，同时训练σ∙i和m∙∙i以获得最佳决策图，如论文中的图1所示。0M 0 = M 1 = 空格0步骤0 步骤1 步骤20决策0节点中的概率0图3：转移矩阵的构建和我们的马尔可夫过程的连续步骤。左边是一个带有矩阵M0和M1的图形，接下来是一个示例决策向量σx和结果矩阵Px。右边是图中的流程，连续进行3个步骤。首先，概率完全放置在根节点中。然而，在接下来的步骤中，根据转移概率，分布在节点之间分裂，第3步到达叶子节点。所有步骤后叶子节点中的概率是模型推断的类概率（步骤数被视为方法的超参数）。03.1.4 算法复杂度0由于需要存储转移矩阵M0和M1，内存与节点数n的平方成正比。对于单个图像x，计算复杂度受到用于生成矩阵Mx（以及因此Px）的Hadamard乘积的限制，即O(n^2)。考虑到步骤数N，向量v乘以矩阵PxN次。因此，复杂度为O(n^2 + N * (n +c)^2)，其中c是叶子节点的数量。03.2. 正则化0与软决策树（SDT）[8]类似，我们观察到我们的图形需要额外的训练正则化器。0原因有三个。首先，SONG可能会陷入平台，其中一个或多个输入样本x的σdi(x)为0，而该决策的sigmoid逻辑函数的梯度始终非常接近于零。其次，如果SONG对其预测不确定，它可以安全地将概率保留在内部节点中，而不是将其移动到叶子节点，这导致后者中的累积概率很小。第三，SONG倾向于将一般情况下的正面二值化，但如果这种二值化出现得太早，模型可能会陷入局部最小值。因此，为了防止模型退化，我们引入了三种正则化方法。Lnodes = −λ2log(αi,s) + log(βi,s),x∈sxr)i · (σ1i (x))γx∈B(P sxr)i,x∈B(P sxr)i · (σ0i (x))γ(P sr)i,n+ci=n(P Nx r)i,(3)38520(a) 对应于初始M0，M1的图形。0(b) 对应于训练后的 M 0 ,  M 1 的图形。0(c) 具有初始值的M0，M1。0(d) 训练后的 M 0 ,  M 1 .0图4：在MNIST数据集上训练后，具有9个内部节点的SONG的转移矩阵M0（蓝色边）和M1（红色边）的图形可视化。可以观察到SONG模型在梯度训练过程中对连接进行二值化。03.2.1 节点正则化0节点正则化是对[8]提出的方法的直接改编。它用于避免陷入糟糕的解决方案，鼓励每个内部节点平等地使用左右子树。在我们的方法中，该正则化鼓励每个内部节点平等地使用边集E0和E1。即，将一半的训练样本发送到一个方向（使用M0），将另一半的训练样本发送到另一个方向（使用M1）。为此，我们计算所需的平均分布0.5,0.5与节点vi在步骤s中的实际平均分布αi,s,βi,s之间的交叉熵。0n空格0其中0α i,s  =空格0空格0βi,s = �0B是迭代中使用的样本批次，γ∈[1，2]，(Psxr)i对应于(Psxr)向量的第i个坐标。可以观察到我们的节点正则化器是按节点和步骤计算的，与[8]不同，其中为每个节点计算了额外的损失。此外，我们使用参数γ惩罚模型做出不确定决策(σi,s(x)≈0.5)。03.2.2 叶子正则化0叶子正则化，强制叶子中的摘要概率接近1，定义为0L leaves = -log0其中n是节点数(不包括以0为索引的根)，c是叶子数(类别数)，N是数量3.2.3Gumbel-softmax38530方法 Ex SO EE MNIST C10 C100 TIN0DDN (NiN) � � � - 90.32 68.35 - DCDJ (NiN) � � � - - 69.00 -ANT-A* (n/a) � � � 99.36 93.28 - -0ResNet18 � � � 98.91 94.93 75.82 63.05 DNDF � � � 97.2094.32 67.18 44.56 DT � � � - 93.97 64.45 52.09 NBDT � � � -94.82 77.09 64.23 NBDT无层次结构 � � � - 94.52 74.97 -RDT � � � - 93.12 - - SONG (我们的) � � � 98.81 95.62 76.2661.990表1：在MNIST、CI-FAR10 (C10)、CIFAR100(C100)和TinyImageNet(TIN)上，深度架构模型的特征和准确性比较。ResNet18用于提取输入图像的向量表示，用于DNDF [13]、DT、NBDT(带和不带层次结构) [38]、RDT [2]和SONG。对于DDN[23]、DCDJ [4]和ANT-A[36]，在括号中提供了骨干模型。“Ex”表示方法是否保留了纯叶子、顺序决策和非集成等特性。“SO”表示模型是否是自组织的(不需要预定义的结构)。“EE”表示模型的结构和权重是否以端到端连续的方式进行训练。0步骤数。0我们使用Gumbel-softmax[10]代替softmax对矩阵M0和M1的每一列进行探索图的轨迹。换句话说，Gumbel-softmax引入了随机性，从而在优化过程中对图结构进行更广泛的探索。04. 理论分析0在补充材料中，我们提供了理论结果，显示SONG在训练过程中生成的图结构是二值化的，如图4所示。05. 实验0在本节中，我们分析了在Letter [3]，Connect4 [3]，MNIST[17]，CI-FAR10 [14]，CIFAR100 [14]和TinyImageNet[16]数据集上训练的SONG的准确性，并将其与现有的方法[2，4，13，23，36，38]进行比较。我们研究了节点数和步数如何影响图的结构，模型使用的内部节点数，反向边的数量以及从根到叶子的距离。此外，我们解释了背向边和交叉边的概率如何。0方法 Letter Connect4 MNIST0SDT无蒸馏[8] 78.00 (511) 78.63 (255) 94.45 (255) SDT [8]81.00 (511) 80.60 (255) 96.76 (255) SONG-S-large (我们的)86.25 (511) 82.82 (255) 95.74 (255) SONG-S-small (我们的)82.95 (64) 80.27 (8) 94.66 (64)0表2：在三个数据集上比较SDT [8]和浅层SONG(SONG-S)，其中浅层对应于直接展开的输入(不使用骨干网络)。报告了每个模型的准确性以及括号中指定的内部节点数。SONG-S-small包含与SDT匹配准确性所需的最小节点数。SONG-S-large使用与SDT相同数量的内部节点。请注意，SONG模型在没有蒸馏机制的情况下进行训练，它们总是比没有蒸馏的SDT获得更好的结果。0在连续的训练步骤中观察到的变化。最后，我们与SDT[8]进行了详细比较，并展示了在MNIST数据集上获得的样本图。在所有实验中，我们使用叶节点归一化和Gumbel-softmax，并将节点正则化视为模型的超参数。尽管本节只呈现了最重要的发现以保持清晰度，但实验设置和详细结果可以在补充材料中找到。05.1. SONG 在深度学习设置中0在第一个实验中，我们在主干卷积神经网络（CNN）的顶部应用 SONG2，而不包括最后的线性层。CNN接收输入图像并生成表示，然后将表示传递给SONG。SONG处理表示并返回每个类别的预测结果，然后与目标标签一起计算二元交叉熵（BCE）损失。作为主干网络，我们在所有数据集上使用ResNet18，除了MNIST数据集，我们使用了一个较小的网络（详见补充材料）。如表1所示，我们的方法与大多数最新的最先进方法相匹配或超过。在CIFAR10上，SONG的准确率超过了所有基线方法近1个百分点。在MNIST上，它比ANT[36]差了约0.5％，在CIFAR100和Tiny-ImagNet上，NBDT[38]取得了更好的结果。然而，ANT和NBDT都不是以端到端连续的方式进行训练的。此外，NBDT在训练之前需要提供一个层次结构，如果没有这样的层次结构，它在CIFAR100上的准确率比SONG低1％以上。05.2. SONG 作为浅层模型0尽管 SONG可以在深度学习设置中成功使用，但它也可以被视为一个浅层模型。在02 我们已经将代码公开在：https://github.com/gmum/SONGs012345789012345678946810 2024646810 2046810 2046810 2046810 20012346810 2046810 2046810 2046810 200.02.55.07.50.046810 2046810 2046810 2046810 20510152046810 2046810 2046810 2038540(a) 16 个内部节点和 8 个步骤。0(b) 32 个内部节点和 8 个步骤。0图 5：在 MNIST 数据集上训练 SONG获得的图结构示例。根节点是每个图中最上面的节点，双重节点边界表示 MNIST 类别的叶节点。对于每个节点 v i，我们展示了两条边，分别对应于两个转移向量 m 0 ∙ i 和m 1 ∙ i的最高概率（分别用虚线蓝色箭头和实线红色箭头表示）。0在这种情况下，SONG直接处理输入样本并将预测结果传递给BCE损失的目标标签。这个设置类似于在SDTs[8]上进行的实验中所呈现的设置。因此，我们在[8]考虑的所有数据集上与SDT进行比较。表2显示，SONG在所有数据集上都比没有蒸馏的SDT获得更好的结果。此外，在Letter和Connect4上，SONG甚至优于具有蒸馏的SDT。我们还观察到，SONG所需的节点数量比SDT少，并且在Connect4数据集上获得了与SDT相当的结果，但节点数量只有SDT的30倍。对于Letter和MNIST，可以使用30倍少的节点获得类似好的结果。这一发现与[33]一致，该研究表明决策图在显著提高泛化能力的同时需要的内存大大减少。05.3. SONG 结构0作为一个完全可微的模型，SONG在训练过程中加强或减弱任意一对节点之间的边，以不断优化图的结构（见图4）。因此，它可以生成使用所有可用节点或仅使用其中一些节点的任何结构。特别地，最终的结构可以是二叉树或包含反向边。此外，从根节点到叶节点的距离可以变化。这种变化在图5中可视化，我们展示了使用不同数量的内部节点和步骤获得的两个MNIST图。在图6中，我们提供了多个SONG的统计数据。0节点数量 = 9 节点数量 = 16 节点数量 = 32 节点数量 = 640步骤数量 步骤数量 步骤数量 步骤数量0反向边数量交叉边数量到叶子的距离使用的内部节点数量0图6：在CIFAR10数据集上训练的SONGs的节点和边统计。对于每个内部节点和步骤数量的组合，训练了20个图并用于绘制四个统计量的分布。0针对CIFAR10数据集进行的SONG结构分析。我们观察到SONG的结构差异取决于内部节点和步骤的数量。首先，我们注意到模型使用的内部节点数量随着步骤数量的增加而增加，并且不依赖于总内部节点数n。作为自然结果，根到叶子的距离也呈类似趋势。当涉及到反向边时，它们的数量相对较少，只在较大的步骤数下出现。与此同时，交叉边更常见，并且随着内部节点数量的增加而增加。我们还分析了节点和步骤数量与SONG预测准确性之间的关系。如表3所示，对于MNIST数据集（a），随着节点和步骤数量的增加，性能不断提高。而对于CIFAR-10（b），在所有参数组合下性能相对类似。这可能是由于MNIST中表示向量的维度（50）小于CIFAR10中的维度（512）所致。05.4. 训练过程中的SONG结构0我们分析了BCE损失与训练的连续时期中反向边和交叉边的概率之间的关系。我们对多个模型和所有测试样本进行了平均（因为每个测试样本x的图由矩阵Px表示）。我们观察到反向边的概率随着BCE损失的减少而减少，无论是简单的MNIST还是更复杂的CIFAR100数据集（参见图7）。此外，在图8中，我们呈现了对于CIFAR10数据集生成的样本获得的转移矩阵（Px）之间的平均距离。995.6697.2997.2597.9597.561697.3197.8398.2398.4398.563296.8297.7498.3598.6598.626496.2998.1298.1298.4798.68994.4894.8694.9294.9494.931694.8894.9594.8694.8794.893294.9994.9594.9594.9094.986494.9094.8794.8894.9494.930.0150.0200.0250.030BCE loss60120180240Number of back edgeswith p > 104020406080100Epoch150300450Number of cross edgeswith p > 1040.0150.0200.0250.030BCE loss040080012001600Number of back edgeswith p > 104020406080100Epoch0250500750Number of cross edgeswith p > 10438550步骤0节点4 6 8 10 200（a）MNIST。0步骤0节点4 6 8 10 200（b）CIFAR10。0表3：SONG在深度学习设置中的结果。可以观察到对于MNIST数据集（a），性能随着节点和步骤数量的增加而增加。相反，对于CIFAR10（b），在所有参数组合下性能相对类似。0（a）CIFAR100训练的具有256个内部节点和10个步骤的SONG。0（b）CIFAR10训练的具有64个内部节点和10个步骤的SONG。0图7：SONG在连续训练时的BCE损失以及反向边和交叉边的数量。可以观察到反向边的数量随着BCE损失的减少而减少。0（a）16个内部节点。0（b）64个内部节点。0图8：对于由距离矩阵表示的一对MNIST输入样本，转移矩阵Px的平均距离（距离越大，颜色越亮）。行和列对应于0-9的数字。0相同和不同类别。可以观察到，对角线明显比矩阵的其他部分更暗，这意味着相同类别的输入具有更相似的转移矩阵。这证实了我们对相似输入获得相似转移矩阵的观察。06. 结论0在这项工作中，我们介绍了自组织神经图（SONGs），这是一种适用于任何深度学习流程的新型决策图。它们通过使用梯度下降来加强或减弱图的边缘，在训练过程中优化其结构。由于图的结构，SONG可以重用决策节点，并且与现有方法相比，使用显著较少的节点获得最先进的结果。此外，基于马尔可夫过程的引入的通用范例可以实现高效的训练，并且SONG收敛到二进制无环有向图。因此，我们相信我们的工作为在深度学习设置中更有效地应用决策图开辟了大量的研究途径。0致谢0J. Tabor和B.Zieli´nski的工作得到波兰国家科学中心（Poland）资助，资助号为2021/41/B/ST6/01370；Ł.Struski的工作得到波兰国家科学中心（Poland）资助，资助号为2020/39/D/ST6/01332；T.Danel的工作得到波兰国家科学中心（Poland）资助，资助号为2020/37/N/ST6/02728；M. ´Smieja的研究项目“Bio-inspired artificial neuralnetwork”（资助号POIR.04.04.00-00-14DE/18-00）在波兰科学基金会的Team-Net计划下进行，该计划由欧洲区域发展基金（European Regional DevelopmentFund）共同资助。[19] Manish Mehta, Rakesh Agrawal, and Jorma Rissanen. Sliq:A fast scalable classifier for data mining. In International38560参考文献0[1]  Karim Ahmed，Mohammad Haris Baig和LorenzoTorresani.用于大规模图像分类的专家网络。在欧洲计算机视觉会议上，页码516-532。Springer，2016年。0[2]  Stephan Alaniz，Diego Marcos，Bernt Schiele和ZeynepAkata.通过通信递归学习决策树。第34届IEEE计算机视觉和模式识别会议。IEEE，2021年。0[3]  Arthur Asuncion和David Newman.UCI机器学习库，2007年。0[4]  Seungryul Baek，Kwang In Kim和Tae-Kyun Kim.用于图像分类的深度卷积决策森林。arXiv预印本arXiv:1706.02003，2017年。0[5]  Osbert Bastani，Carolyn Kim和Hamsa Bastani.通过模型提取解释黑盒模型。arXiv预印本arXiv:1705.08504，2017年。0[6]  Chaofan Chen，Oscar Li，Chaofan Tao，Alina JadeBarnett，Jonathan Su和Cynthia Rudin.这看起来像那个：用于可解释的图像识别的深度学习。arXiv预印本arXiv:1806.10574，2018年。0[7]  Philip A. Chou.用于分类和回归树的最优分区。IEEE计算机架构通讯，13(04):340-354，1991年。0[8]  Nicholas Frosst和Geoffrey Hinton.将神经网络提炼为软决策树。arXiv预印本arXiv:1711.09784，2017年。0[9]  Kaiming He, Xiangyu Zhang, Shaoqing Ren和Jian Sun.深度残差学习用于图像识别。在IEEE计算机视觉和模式识别会议上的论文集，页码770-778，2016年。0[10]  Eric Jang，Shixiang Gu和Ben Poole.使用Gumbel-Softmax进行分类重参数化。arXiv预印本arXiv:1611.01144，2016年。0[11]  Cem Keskin和Shahram Izadi. Splinenets:连续神经决策图。arXiv预印本arXiv:1810.13118，2018年。0[12]  Ron Kohavi和Chia-Hsin Li.无视决策树、图和自顶向下修剪。在IJCAI上，页码1071-1079。Citeseer，1995年。0[13]  Peter Kontschieder, Madalina Fiterau, AntonioCriminisi和Samuel Rota Bulo.深度神经决策森林。在IEEE国际计算机视觉会议上的论文集，页码1467-1475，2015年。0[14]  Alex Krizhevsky，GeoffreyHinton等人。从小图像中学习多层特征。2009年。0[15]  Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.使用深度卷积神经网络的Imagenet分类。神经信息处理系统的进展，25:1097-1105，2012年。0[16]  Ya Le和Xuan Yang. Tiny Imagenet视觉识别挑战。CS231N，7:7，2015年。0[17]  Yann LeCun, Corinna Cortes, and CJ Burges.Mnist手写数字数据库，2010年。0[18]  Wei-Yin Loh.分类和回归树。Wiley跨学科综述：数据挖掘和知识发现，1(1):14-23，2011年。0扩展数据库技术会议，第18-32页。Springer，1996年。0[20]  Tom ´ a ˇ s Mikolov，Stefan Kombrink，Luk ´ a ˇ sBurget，Jan ˇ Cernock ` y和SanjeevKhudanpur。递归神经网络语言模型的扩展。在2011年IEEE国际会议上，声音和信号处理（ICASSP）的论文集中，第5528-5531页。0[21]  Frederic Morin和YoshuaBengio。分层概率神经网络语言模型。在Aistats中，第5卷，第246-252页。Citeseer，2005年。0[22]  Ravi Teja Mullapudi，William R Mark，NoamShazeer和KayvonFatahalian。Hydranets：用于高效推理的专用动态架构。在IEEE计算机视觉和模式识别会议的论文集中，第8080-8089页，2018年。0[23]  Venkatesh N Murthy，Vivek Singh，Terrence Chen，RMan- matha和DorinComaniciu。用于多类图像分类的深度决策网络。在IEEE计算机视觉和模式识别会议的论文集中，第2240-2248页，2016年。0[24]  Meike Nauta，Ron van Bree和ChristinSeifert。用于可解释细粒度图像识别的神经原型树。arXiv预印本arXiv:2012.02046，2020年。0[25]  Arlindo L Oliveira和AlbertoSangiovanni-Vincentelli。使用最小描述长度原理推断简化有序决策图。机器学习，25（1）：23-50，1996年。0[26]  JonathanOliver。决策图：决策树的扩展。Citeseer，1992年。0[27]  JJOliver。决策图-决策树的扩展。在第4届人工智能和统计国际会议上，迈阿密，佛罗里达州，1993年，1993年。0[28]  John C Platt，Nello Cristianini，JohnShawe-Taylor等。用于多类分类的大边缘有向无环图。在nips中，卷- ume 12，第547-553页，1999年。0[29]  J RossQuinlan。C4.5：用于机器学习的程序。Elsevier，2014年。0[30]  CynthiaRudin。停止解释高风险决策的黑盒机器学习模型，改用可解释模型。自然机器智能，1（5）：20