Identifying a Probabilistic Boolean Threshold Network From Samples
Identifying a Probabilistic Boolean Threshold Network From Samples
复制标题
DOI：
10.1109/tnnls.2017.2648039
复制
发表时间：
2018-04
影响因子：
10.4
通讯作者：
A. Melkman;Xiaoqing Cheng;W. Ching;T. Akutsu
中科院分区：
文献类型：
--
作者：
A. Melkman;Xiaoqing Cheng;W. Ching;T. Akutsu
本文研究了从给定的一组样本中准确识别概率布尔网络（PBN）结构的问题，其中PBN是布尔网络的概率扩展。程等人。研究了这个问题，同时关注由 AND/OR 函数对组成的 PBN。本文考虑由布尔阈值函数组成的PBN，同时重点关注具有单位系数的阈值函数。布尔阈值函数以及此类函数的三元组和 ${n}$ 元组的处理需要深化理论分析。结果表明，在合理的约束下，可以从样本中准确识别具有此类阈值函数的广泛类别的PBN，其中包括：1）可以分配任意数量的阈值函数的PBN，前提是所有阈值函数都具有相同数量的输入变量；2）由具有不同数量的输入变量的阈值函数对组成的PBN。它还表明，确定两个布尔阈值函数的等价性的问题可以在伪多项式时间内解决，但仍然是 co-NP 完全的。
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 ${n}$ -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.