در مورد ویژگی های کلاس های مفهوم ناشی از شبکه های بیزی چند ارز

The concept class CNCN induced by a Bayesian network NN can be embedded into some Euclidean inner product space. The Vapnik –Chervonenkis (VC)-dimension of the concept class and the minimum dimension of the inner product space are very important indicators for evaluating the classification capability of the Bayesian network. In this paper, we investigate the properties of the concept class CNkCNk induced by a multivalued Bayesian network NkNk, where each node X i of NkNk is a k -valued variable. We focus on the values of two dimensions: (i) the VC -dimension of the concept class CNkCNk, denoted as VCdim(Nk)VCdim(Nk), and (ii) the minimum dimension of the inner product space into which CNkCNk can be embedded. We show that the values of these two dimensions are k n − 1 for fully connected k -valued Bayesian networks View the MathML sourceNFk with n variables. For non-fully connected k -valued Bayesian networks NkNk without V -structure, we prove that the two dimensional values are View the MathML source(k-1)∑i=1nkmi+1, where mi denotes the number of parents for the ith variable. We also derive the upper and lower bounds on the minimum dimension of the inner product space induced by non-fully connected Bayesian networks.

Bayesian networks (BNs), also referred to as Belief Networks or Causal Networks, are directed graphical models for representing the probabilistic relationships between variables. The network structure is a directed acyclic graph (DAG) where each node represents a random variable [18], [8], [16] and [10]. BNs are a powerful tool for modeling the decision-making process under uncertainty. They have been successfully applied to various fields including machine learning and bioinformatics, and found particularly useful in knowledge representation, reasoning and learning under uncertainty [12], [9] and [5]. Kitakoshi et al. [14] presented a reinforcement learning system that adapts to environmental changes using a mixture of BNs. Yang et al. [27] proposed a driver fatigue recognition model based on the information fusion technique and a dynamic BN. BNs are also widely used for classification due to their simplicity and accuracy [4], [7], [11] and [17]. Some approaches combine kernel methods and probabilistic models, such as Ben et al. [3], Taskar et al. [21], Gurwicz and Lerner [13], Chechik et al. [6], Aritz et al. [2] and Theodoros and Mark [22]. Altun et al. [1] proposed a kernel for the Hidden Markov Model, which is a special case of a BN. These methods study not only the domain-specific design of some probabilistic models, but also the information extracted from the data during the training of the probabilistic models. For a data mining algorithm, the generalization capability is a very important feature that is often used to evaluate the performance of the algorithm. To improve the generalization of data mining algorithms, Wang and Dong [23] and Wang et al. [24] proposed a new refinement method based on a fuzzy decision tree, the rough set technique, and the fuzzy entropy. Based on the analysis for multi-valued attribute and multi-labeled data, Yi et al. [28] presented a new decision tree classification algorithm. In fact, decision tree is a special type of graphical model. To improve the power of the nearest neighbor-based algorithms to high dimensional data, a local learning method was proposed in the paper Tang et al. [20] for image processing. As machine learning techniques become more widely adopted regarding the classification and the structure prediction, it becomes increasingly important how to balance the computational consumption and the classification capability [19]. For the evaluation of the classification capability induced by a BN without considering the training data and the classification algorithm, two important indexes are often considered, i.e. VC-dimension and the smallest dimension of the inner product space (see Fig. 1). For example, to classify toys, a general procedure is to build a BN using the attributes of the toys or an expert system, and then train the data and design an appropriate algorithm. In this paper, we focus on the classification capability induced by a BN without considering the training data, the algorithm and the construction of the network graph. We will discuss the two dimensional-values by multivalued BNs. Full-size image (24 K) Fig. 1. The relationship is depicted among a BN NN, the concept class CNCN, Euclidean inner product space and related parameters. By the probability distribution on the BN, the data can be classified. That two dimension-values (VCdim(N)VCdim(N) and Edim(N)Edim(N)) reflect the classification ability of BN. Figure options For a BN NN, one can get a concept class CNCN induced by it. The concept class can be embedded into some Euclidean inner product space. Therefore, there are two dimensional-values: the VC -dimension, denoted as VCdim(N)VCdim(N) of the concept class CNCN, and the minimum dimension of the inner product space, denoted as Edim(N)Edim(N), into which CNCN can be embedded, as shown in Fig. 1. These are very important indexes to assess the classification capability of the BN. An interesting question has been raised as to whether these two dimensional-values are equal for BNs. A network graph is fully connected if there is a directed edge between any two nodes, as illustrated in Fig. 2. Let X , Z , Y be three nodes of a network graph G=(V,E)G=(V,E). We call (X , Z , Y ) a V -structure if (1) GG contains the edges X → Z and Z ← Y , and (2) X and Y are not adjacent in GG [8]. For example, (X3, X5, X4) in Fig. 3(a), (X1, X3, X2) in Fig. 3(b) and (X1, X5, X4) in Fig. 3(c) are three V-structures. The BNs shown in Fig. 4 do not have any V-structure. Full-size image (11 K) Fig. 2. Two FBNs with 4 and 5 nodes, respectively. Figure options Full-size image (18 K) Fig. 3. Three BNs with V-structures: (X3, X5, X4), (X1, X3, X2) and (X1, X5, X4), respectively. Figure options Full-size image (16 K) Fig. 4. BNs without any V-structure. Figure options Nakamura et al. [15] established the upper and lower bounds on the dimension Edim(N)Edim(N) of the inner product space for two-valued BNs, where each node is a boolean variable. Our earlier work in Yang and Wu [25] and Yang and Wu [26] was also focused on these two-valued BNs. For two-valued fully connected Bayesian networks (FBNs) and almost-full Bayesian networks (AFBNs) with n variables, Yang and Wu [25] showed that the VC dimension and the minimum dimension of the inner product space induced by them are 2n − 1, and the two dimensional-values induced by a class of two-valued BNs without V -structures is View the MathML source∑i=1n2mi+1. In this paper, we investigate the properties of the inner product space and concept classes induced by multivalued BNs NkNk, where each node is a k -valued variable (X i ∈ {0, 1, 2, … , k − 1}). Our work makes two major contributions to the field: (i) for a k -valued FBN with n variables, we show that View the MathML sourceVCdim(NFk)=Edim(NFk)=k-1n, and (ii) for k -valued BNs NkNk without V -structure, we prove that View the MathML sourceVCdim(Nk)=Edim(Nk)=(k-1)∑i=1nkmi+1, where mi denotes the number of parents for the ith variable. We further derive the upper and lower bounds on the minimum dimension of the inner product space for k-valued non-FBNs. The results presented in this paper are partially based on our earlier work Yang and Wu [25] and Yang and Wu [26]. For example, some results in Yang and Wu [25] are the special cases of the work in this paper. The rest of the paper is organized as follows. In Section 2, we discuss related work and introduce our notations. In Section 3, we provide the VC dimension and inner product space induced by FBNs. In Section 4, we provide a detailed proof of the upper and lower bounds on the dimension of the inner product space for k-valued BNs. The VC-dimension and inner product space induced by BNs without V-structure are given in Section 4. We conclude our work in Section 5.

BNs have become one of the major models used for statistical inference. In this paper, we focused on the two-label classification over the domain {0, 1, 2, … , k − 1}n. We showed that for fully connected k -valued BNs View the MathML sourceNFk with n variables, the VC-dimension of the concept class and the minimum dimension of the inner product space induced by them are kn − 1. Therefore, for BNs depicted in Fig. 6, one has the two dimensional-values induced by them. Furthermore, for those k -valued BNs NkNk without any V -structure, we proved that the VC -dimension of the concept class and the lower bound of the dimension of the inner product space induced by them are View the MathML source(k-1)∑i=1nkmi+1. For instance, one has the two dimensional-values induced by BNs depicted in Fig. 7. Our work does not show a common way to compute the VC dimension and linear arrangement dimensionality for any BN with V -structure. However the upper and lower bounds on the minimum dimension of the inner product space induced by a BN NkNk with V -structure are given, i.e. View the MathML source(k-1)∑i=1nkmi+1⩽Edim(Nk)⩽|⋃i=1nkPAi∪{Xi}|. For BNs without V-structure, we concluded that their VC dimension and the smallest linear arrangement dimension are equal. It is still an open question as to whether these two dimensional-values are equal for any BN. Acknowledgments The authors thank Mitsunori Ogihara, Bin Wei and Chengliang Zhang for valuable discussions and constructive suggestions during the visit of the lead author to the University of Rochester. We especially want to acknowledge Qishi Wu for invaluable writing support and improving the English expression. We would also like to thank the anonymous reviewers for their helpful comments. This work was supported by National Natural Science Foundation of China.