JCSE, vol. 9, no. 4, pp.204-213, 2015

DOI: http://dx.doi.org/10.5626/JCSE.2015.9.4.204

Relation Based Bayesian Network for NBNN

Mingyang Sun, YoonSeok Lee, and Sung-eui Yoon
School of Computing, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea

Abstract: Under the conditional independence assumption among local features, the Naive Bayes Nearest Neighbor (NBNN) classifier has been recently proposed and performs classification without any training or quantization phases. While the original NBNN shows high classification accuracy without adopting an explicit training phase, the conditional independence among local features is against the compositionality of objects indicating that different, but related parts of an object appear together. As a result, the assumption of the conditional independence weakens the accuracy of classification techniques based on NBNN. In this work, we look into this issue, and propose a novel Bayesian network for an NBNN based classification to consider the conditional dependence among features. To achieve our goal, we extract a high-level feature and its corresponding, multiple low-level features for each image patch. We then represent them based on a simple, twolevel layered Bayesian network, and design its classification function considering our Bayesian network. To achieve low memory requirement and fast query-time performance, we further optimize our representation and classification function, named relation-based Bayesian network, by considering and representing the relationship between a high-level feature and its low-level features into a compact relation vector, whose dimensionality is the same as the number of lowlevel features, e.g., four elements in our tests. We have demonstrated the benefits of our method over the original NBNN and its recent improvement, and local NBNN in two different benchmarks. Our method shows improved accuracy, up to 27% against the tested methods. This high accuracy is mainly due to consideration of the conditional dependences between high-level and its corresponding low-level features.

Keyword: Naive Bayes nearest neighbor; Classifications; Conditional dependency; Bayesian network

Full Paper:   365 Downloads, 1822 View