![](https://csdnimg.cn/release/download_crawler_static/88590772/bg5.jpg)
∀j τ
0
j
= 1 ⇐⇒ (∃c ∈ U
j
. ∀I
i
∈ I. c
I
i
= T (I
i
)) (10)
5
0
从训练数据中提取概念,并生成逻辑公式作为输出(Mendelson,2009)。通过构造,从概念C到输
出O学习的概念解码器¯gA≈gA是一个布尔映射。作为任何布尔函数,它可以通过其真值表(Mendel
son,2009)转换为逻辑公式的析取范式。概念解码器gA的权重用于选择每个输出任务的最相关概念
。为了得到简明的逻辑解释(在我们的实验中,仅在图着色任务中需要许多概念作为输入),我们在
损失函数中添加了一个正则化项,最小化概念解码器权重W的L1范数,从而导致W的稀疏配置。稍后
,在训练时期tprune,首层权重按概念逐个进行修剪,即删除从最不相关的概念出发的所有权重:
0
˜W1j=W1jI||W1j||1≥maxi||W1i||1/2,其中i=
0
其中I是指示函数,W1是第一层的权重。有关逻辑提取的更多细节,请参见附录B。
0
提取算法终止规则在决定是否继续执行时,我们利用了一些图算法在迭代过程中会一直迭代,直到存
在具有特定概念组合的节点的事实。由于不清楚我们应该朝着哪种概念组合进行监督,我们在提取终
止规则时采用了完全枚举的方法。首先,我们从给定图的每个步骤的训练集中生成一个样本j,形式为
(Uj,τ'j)。τ'j是关于我们是否应该继续迭代的真值,Uj=
{c'1,...,c'k}是所有唯一概念组合的集合,2表示在执行算法更新状态之后(因此为c')。给定一组
概念索引3IP({1..|C|})和真值分配T:{1..|C|}→
{0,1},告诉我们哪些概念必须为真/假,我们检查以下条件是否满足:
0
即如果存在特殊的概念组合,我们应该继续迭代,如果不存在特殊的概念组合,我们应该停止迭代。
我们采用暴力方法来寻找I和T,通过优先选择较小的I来打破平局。这种方法的复杂度是指数级的,但
是如果概念瓶颈被精心设计,所需的概念数量和/或特殊组合中的概念数量将很小,使计算可行。
0
更重要的是,如果相同的枚举方法应用于原始节点输入数据,可能不存在I/
T组合。例如,BFS任务的每个步骤的节点级输入并不能告诉我们哪些节点访问了邻居(决定终止的关
键)。此外,如果我们有更多的输入特征,暴力方法可能无法计算-
组合随着节点特征和概念数量的增加呈指数级增长,而概念是减少这个数量的一种方法。
0
4实验设置
0
我们实验的代码可以在https://github.com/HekpoMaH/algorithmic-concepts-reasoning找到。
0
我们将我们的GNN应用于以下算法:广度优先搜索(BFS),并行着色(Jones和Plassmann,1993
),图着色启发式算法和Kruskal的最小生成树(MST)算法(Kruskal,1956)。BFS被建模为一个
二分类问题,我们预测一个节点是否被访问,而并行着色则被建模为一个分类任务,任务是确定可能
的节点颜色的类别,再加上一个类别表示未着色的节点。Kruskal的算法被建模为两个并行训练的任
务,一个是分类任务,选择下一个要考虑的MST边,另一个是帮助我们确定哪些节点属于同一集合的
任务。由于原始的Kruskal算法执行|E|步,我们不学习MST任务的终止条件,并坚持固定的步数。我
们在附录C中展示了我们如何为所有算法建模输入/输出。
0
2k可能因样本而异3{a..b}表示从a到b的整数集合4
在我们的情况下,这打破了所有的平局,但是,如果有必要,可以通过在真值分配上添加平局破坏,例如选择具
有更多真/假值的分配
0
+v:mala2255获取更多论文