A set of variables is the Markov blanket of a random variable if it contains
all the information needed for predicting the variable. If the blanket cannot
be reduced without losing useful information, it is called a Markov boundary.
Identifying the Markov boundary of a random variable is advantageous because
all variables outside the boundary are superfluous. Hence, the Markov boundary
provides an optimal feature set. However, learning the Markov boundary from
data is challenging for two reasons. If one or more variables are removed from
the Markov boundary, variables outside the boundary may start providing
information. Conversely, variables within the boundary may stop providing
information. The true role of each candidate variable is only manifesting when
the Markov boundary has been identified. In this paper, we propose a new
Tsetlin Machine (TM) feedback scheme that supplements Type I and Type II
feedback. The scheme introduces a novel Finite State Automaton - a
Context-Specific Independence Automaton. The automaton learns which features
are outside the Markov boundary of the target, allowing them to be pruned from
the TM during learning. We investigate the new scheme empirically, showing how
it is capable of exploiting context-specific independence to find Markov
boundaries. Further, we provide a theoretical analysis of convergence. Our
approach thus connects the field of Bayesian networks (BN) with TMs,
potentially opening up for synergies when it comes to inference and learning,
including TM-produced Bayesian knowledge bases and TM-based Bayesian inference.

本文提出了一种新的 Tsetlin Machine (TM) 反馈机制，引入了一个上下文特定独立自动机，该自动机学习目标变量 Markov 边界之外的特征，从而在学习过程中将它们从 TM 中剪枝，通过实证研究展示了该机制如何利用上下文特定独立来找到 Markov 边界，并为其收敛性提供了理论分析，从而将贝叶斯网络领域与 TMs 相关联，为推理和学习提供协同作用的可能性，包括由 TM 生成的贝叶斯知识库和基于 TM 的贝叶斯推断。

使用马尔科夫边界引导剪枝学习极简特斯林机器子句

Learning Minimalistic Tsetlin Machine Clauses with Markov  Boundary-Guided Pruning

Ridge regularized linear models (RRLMs), such as ridge regression and the
SVM, are a popular group of methods that are used in conjunction with
coefficient hypothesis testing to discover explanatory variables with a
significant multivariate association to a response. However, many investigators
are reluctant to draw causal interpretations of the selected variables due to
the incomplete knowledge of the capabilities of RRLMs in causal inference.
Under reasonable assumptions, we show that a modified form of RRLMs can get
very close to identifying a subset of the Markov boundary by providing a
worst-case bound on the space of possible solutions. The results hold for any
convex loss, even when the underlying functional relationship is nonlinear, and
the solution is not unique. Our approach combines ideas in Markov boundary and
sufficient dimension reduction theory. Experimental results show that the
modified RRLMs are competitive against state-of-the-art algorithms in
discovering part of the Markov boundary from gene expression data.

本研究提出了一种修改后的岭回归方法，可以在减小空间的基础上识别潜在的 Markov 边界。实验结果表明，这种方法在基因表达数据的 Markov 边界发现方面具有很强的实用性。