IEEE Trans Neural Netw Learn Syst. 2018 Apr;29(4):869-881. doi: 10.1109/TNNLS.2017.2648039. Epub 2017 Jan 25.
This paper studies the problem of exactly identifying the structure of a probabilistic Boolean network (PBN) from a given set of samples, where PBNs are probabilistic extensions of Boolean networks. Cheng et al. studied the problem while focusing on PBNs consisting of pairs of AND/OR functions. This paper considers PBNs consisting of Boolean threshold functions while focusing on those threshold functions that have unit coefficients. The treatment of Boolean threshold functions, and triplets and -tuplets of such functions, necessitates a deepening of the theoretical analyses. It is shown that wide classes of PBNs with such threshold functions can be exactly identified from samples under reasonable constraints, which include: 1) PBNs in which any number of threshold functions can be assigned provided that all have the same number of input variables and 2) PBNs consisting of pairs of threshold functions with different numbers of input variables. It is also shown that the problem of deciding the equivalence of two Boolean threshold functions is solvable in pseudopolynomial time but remains co-NP complete.
本文研究了从给定样本集中准确识别概率布尔网络（PBN）结构的问题，其中 PBN 是布尔网络的概率扩展。Cheng 等人在研究该问题时，重点关注由 AND/OR 函数对组成的 PBN。本文考虑了由布尔门限函数组成的 PBN，重点关注那些系数为 1 的门限函数。布尔门限函数以及此类函数的三元组和四元组的处理需要深化理论分析。结果表明，在合理的约束下，可以从样本中准确识别具有此类门限函数的广泛类别的 PBN，其中包括：1）可以分配任意数量的门限函数，只要它们具有相同数量的输入变量，以及 2）由具有不同数量输入变量的门限函数对组成的 PBN。此外，还表明判断两个布尔门限函数是否等价的问题可以在伪多项式时间内解决，但仍然属于 co-NP 完全问题。
