《Applied Sciences》:Concept Tree Learner (CTL): An Incremental and Interpretable Symbolic Framework for Binary String Rule Induction
编辑推荐:
符号化与基于规则的学习为当代由统计范式主导的机器学习提供了一种透明且样本高效的替代方案。大语言模型与深度网络从大规模语料中近似目标函数而不暴露其所依赖的规则,而许多实际问题反而需要从极少数样本中学习紧凑、人类可读的概念定义。研究人员提出概念树学习器(Conce
符号化与基于规则的学习为当代由统计范式主导的机器学习提供了一种透明且样本高效的替代方案。大语言模型与深度网络从大规模语料中近似目标函数而不暴露其所依赖的规则,而许多实际问题反而需要从极少数样本中学习紧凑、人类可读的概念定义。研究人员提出概念树学习器(Concept Tree Learner, CTL),一种增量式可解释符号框架,从最少标记数据中在二进制字符串上归纳逻辑概念。CTL将知识表示为逻辑谓词的有根树;每处理一个标记样本即增量扩展该树,并在观测数据后通过集合覆盖(set-cover)过滤步骤依据奥卡姆剃刀(Occam’s Razor)提炼与所有样本一致的最简规则集。研究人员给出树结构、构造与剪枝操作及规则选择目标的正式定义,并分析过程的最坏情况时间与空间复杂度。原型实现在一组原子二进制字符串谓词上运行,其数值参数随输入长度动态缩放,在29个不同复杂度的概念学习任务上评估。CTL为每个任务恢复一致概念——26个数据集上为目标概念,3个训练集未唯一确定目标的任务上为等价一致替代——通常在训练样本耗尽前收敛,并产生完全可解释规则集。在相同原子词汇下,其对未见字符串的泛化显著优于经典基于熵的决策树与RIPPER(Repeated Incremental Pruning to Produce Error Reduction)规则学习器(全任务均值准确率——26个训练集唯一确定目标任务上——分别为——与——,而基线分别为——与——),且使用更少更短规则。研究人员将CTL置于符号机器学习、归纳逻辑编程(Inductive Logic Programming, ILP)与决策树归纳文献中,讨论原型当前局限——限于无噪声二进制输入、批处理(排序)训练机制及固定谓词词汇——并给出向自扩展分层概念学习系统扩展的具体方向。
研究背景方面,当代人工智能以统计学习为主导,大语言模型(LLM)如GPT-4、DeepSeek、Gemini虽展现强文本能力,但因其概率性质难以识别二进制字符串等简单语义模式,且无法暴露内部规则,与迈向人工通用智能(AGI)所需的概念组合式增量获取存在差距。认知科学与发育心理学指出人类概念获取得益于由简至繁的组合式构造,而非从海量数据一次性推断。现有决策树(ID3、C4.5、CART)与归纳逻辑编程(FOIL)等符号方法或需批量特征矩阵、或产生扁平子句、或依赖统计分裂准则,难以在极少样本下直接表达原始字符串上的结构谓词并兼顾可解释与增量性。为此,研究人员开展Concept Tree Learner(CTL)研究,以二进制字符串为基底,构建有根谓词树,通过construct与destruct操作增量维护与正负样本一致的候选路径群体,最终以集合覆盖过滤得最简析取规则集。论文发表于《Applied Sciences》,其意义在于为少样本、可解释、符号化概念学习提供形式化算法与复杂度证明,并实证超越经典符号基线。
关键技术方法上,研究人员采用八类原子谓词节点(Root、Any、Not、Starts-with、Ends-with、Has、Length、Equals)及其trim变体,将字符串匹配与消费建模为带占位符X的变换;以正例先于负例的批排序预处理保障destruct安全删枝;数值参数(如len、has计数)动态绑定当前到达节点残串长度以抑搜索爆炸;树深设MAX_LEVEL常数,叶端以Any闭合;候选路径经加权集合覆盖(最小基数优先、路径深度次之)贪心近似筛选;基线对照在同源原子特征向量化下调用scikit-learn熵决策树与wittgenstein包RIPPER,测试全集为长度1至6共126个二进制串。
研究结果各节要点如下。引言节阐明自下而上组合式概念习得动机,界定CTL不声称AGI或自动谓词发明。相关工节将CTL定位:异于决策树之批量轴对齐分裂,异于FOIL之单子句贪心,其并行存假说说与全局覆盖过滤为特色。方法节3.1至3.3.4给出形式化:概念树T=(V,E)中每非根节点载谓词p与active/deleted状态,路径规则为渐进trim下谓词合取,分类器为活跃叶路径覆盖析取;construct枚举类型、字符、数值、trim四重循环生长,destruct沿接受负例路径递归删叶并向上收敛删内部节点,命题1证排序批处理下不删一致所需路径;节点类型节详述八节点语义与trim消字符机制;过滤节将规则选取化为NP-hard最小基数集合覆盖,采Lund-Yannakakis贪心边际覆盖近似,深度作平局破缺,并证启发式不影响训练正确性只影响精简度。例案节以“首尾同字符”14行数据演示:前8正例得Any,第9负例激变双路径,第12负例收敛为s[1]%→e[1]% ∨ s[0]%→e[0]%。
结果讨论节4.1在29任务上CTL全训一致,26任务命中目标概念,3任务(数据集1、5、20)因训练未唯一确定返等价最简规则;泛化准确率均值为——(26任务——),胜熵决策树——与RIPPER——,规则数均值——少于决策树叶——;树规模因动态数值界较旧固定界缩3至20倍(838–10331节点);单行处理时随输入长度平滑上升而非随树累积增大,M4单线程纯Python下长度6串约—至—秒。复杂度节(4.2)指每新增行仅触及受输入长、常数原子数、常数树深约束的局部邻域,分支因子P随词汇增而胀。局限节(4.3)承认无噪声二进制、批排序、固定词汇三限制,在线化需destruct改停用可重扩。
讨论与结论翻译浓缩:研究人员将CTL嵌入符号机器学习、ILP与决策树谱系,指明其通过并行假设树与全局set-cover蒸馏兼顾少样本泛化与规则精简,弥补LLM不可解释与决策树难捕原始串结构谓词之短;原型价值在基学习器形式化与评测,非层级扩展本身;未来工作含在线删枝、谓词自扩展、跨长度抽象与噪声容忍。结论确认CTL在29任务恢复一致概念且多数命中意图,泛化优于同词汇下熵树与RIPPER且规则更短,局限属设计边界而非算法缺陷,向自扩展分层符号概念系统演进需放宽批排序与固定原子集前提。