Naive Bayes is efficient, has clear theoretical foundations and strong classification performance. Our powerful and computationally efficient Bayesian Network Classifiers improve naive Bayes by addressing limitations of its attribute independence assumption.
The AnDE algorithms achieve this without resorting to model selection or search, by averaging over all of a class of models that directly map lower-dimensional probabilities to the desired high-dimensional probability. Averaged One Dependence Estimators (AODE) is the best known of the AnDE algorithms. It provides particularly high prediction accuracy with relatively modest computational overheads. The AnDE algorithms learn in a single pass through the data, thus supporting both incremental learning and learning from data that is too large to fit in memory. They have complexity that is linear with respect to data quantity. These properties, together with their capacity to accurately model high-dimensional probability distributions, make them an extremely attractive option for large data.
An alternative approach is provided by Lazy Bayesian Rules (LBR), which does perform model selection. It provides very high prediction accuracy for large training sets, and is computationally efficient when few objects are to be classified for each training set.
Selective AnDE refines AnDE models, requiring only a single additional pass through the data.
Selective KDB learns highly accurate models from large quantities of data in just three passes through the data.
AnDE, Selective AnDE and Selective KDB can all operate out-of-core, and thus support learning from very large data.
WANBIA and its variants WANBIA-C and ALR add discriminately learned weights to generatively learned linear models, greatly improving accuracy relative to pure generative learning and learning time relative to pure disciminative learning.
There have been many scientific applications of AODE.
Software
An AnDE package for Weka is available here.
An AnDE package for R is available here.
The following are standard components in Weka:
- AODE, which is AnDE with n=1.
- AODEsr, which is AODE with subsumption resolution.
- LBR, Lazy Bayesian Rules.
An open source C++ implementation of Selective KDB can be downloaded here. A refinement that uses Hierarchical Dirichlet Processes to obtain exceptional predictive accuracy can be downloaded here.
An open source C++ implementation of Sample-base Selective Attribute ANDE can be downloaded here.
Publications
Zhang, Huan; Jiang, Liangxiao; Webb, Geoffrey I.
Rigorous non-disjoint discretization for naive Bayes
Pattern Recognition, vol. 140, 2023, ISSN: 0031-3203.
@article{Zhang2023,
title = {Rigorous non-disjoint discretization for naive Bayes},
author = {Huan Zhang and Liangxiao Jiang and Geoffrey I. Webb},
doi = {10.1016/j.patcog.2023.109554},
issn = {0031-3203},
year = {2023},
date = {2023-01-01},
journal = {Pattern Recognition},
volume = {140},
abstract = {Naive Bayes is a classical machine learning algorithm for which discretization is commonly used to transform quantitative attributes into qualitative attributes. Of numerous discretization methods, Non-Disjoint Discretization (NDD) proposes a novel perspective by forming overlapping intervals and always locating a value toward the middle of an interval. However, existing approaches to NDD fail to adequately consider the effect of multiple occurrences of a single value - a commonly occurring circumstance in practice. By necessity, all occurrences of a single value fall within the same interval. As a result, it is often not possible to discretize an attribute into intervals containing equal numbers of training instances. Current methods address this issue in an ad hoc manner, reducing the specificity of the resulting atomic intervals. In this study, we propose a non-disjoint discretization method for NB, called Rigorous Non-Disjoint Discretization (RNDD), that handles multiple occurrences of a single value in a systematic manner. Our extensive experimental results suggest that RNDD significantly outperforms NDD along with all other existing state-of-the-art competitors.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Naive Bayes is a classical machine learning algorithm for which discretization is commonly used to transform quantitative attributes into qualitative attributes. Of numerous discretization methods, Non-Disjoint Discretization (NDD) proposes a novel perspective by forming overlapping intervals and always locating a value toward the middle of an interval. However, existing approaches to NDD fail to adequately consider the effect of multiple occurrences of a single value - a commonly occurring circumstance in practice. By necessity, all occurrences of a single value fall within the same interval. As a result, it is often not possible to discretize an attribute into intervals containing equal numbers of training instances. Current methods address this issue in an ad hoc manner, reducing the specificity of the resulting atomic intervals. In this study, we propose a non-disjoint discretization method for NB, called Rigorous Non-Disjoint Discretization (RNDD), that handles multiple occurrences of a single value in a systematic manner. Our extensive experimental results suggest that RNDD significantly outperforms NDD along with all other existing state-of-the-art competitors.
Chen, Shenglei; Webb, Geoffrey I.; Liu, Linyuan; Ma, Xin
A novel selective naive Bayes algorithm
Knowledge-Based Systems, vol. 192, 2020.
@article{CHEN2019105361,
title = {A novel selective naive Bayes algorithm},
author = {Shenglei Chen and Geoffrey I. Webb and Linyuan Liu and Xin Ma},
doi = {10.1016/j.knosys.2019.105361},
year = {2020},
date = {2020-01-01},
journal = {Knowledge-Based Systems},
volume = {192},
abstract = {Naive Bayes is one of the most popular data mining algorithms. Its efficiency comes from the assumption of attribute independence, although this might be violated in many real-world data sets. Many efforts have been done to mitigate the assumption, among which attribute selection is an important approach. However, conventional efforts to perform attribute selection in naive Bayes suffer from heavy computational overhead. This paper proposes an efficient selective naive Bayes algorithm, which adopts only some of the attributes to construct selective naive Bayes models. These models are built in such a way that each one is a trivial extension of another. The most predictive selective naive Bayes model can be selected by the measures of incremental leave-one-out cross validation. As a result, attributes can be selected by efficient model selection. Empirical results demonstrate that the selective naive Bayes shows superior classification accuracy, yet at the same time maintains the simplicity and efficiency.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Naive Bayes is one of the most popular data mining algorithms. Its efficiency comes from the assumption of attribute independence, although this might be violated in many real-world data sets. Many efforts have been done to mitigate the assumption, among which attribute selection is an important approach. However, conventional efforts to perform attribute selection in naive Bayes suffer from heavy computational overhead. This paper proposes an efficient selective naive Bayes algorithm, which adopts only some of the attributes to construct selective naive Bayes models. These models are built in such a way that each one is a trivial extension of another. The most predictive selective naive Bayes model can be selected by the measures of incremental leave-one-out cross validation. As a result, attributes can be selected by efficient model selection. Empirical results demonstrate that the selective naive Bayes shows superior classification accuracy, yet at the same time maintains the simplicity and efficiency.
Petitjean, Francois; Buntine, Wray; Webb, Geoffrey I.; Zaidi, Nayyar
Machine Learning, vol. 107, no. 8-10, pp. 1303-1331, 2018, ISSN: 1573-0565.
@article{Petitjean2018,
title = {Accurate parameter estimation for Bayesian network classifiers using hierarchical Dirichlet processes},
author = {Francois Petitjean and Wray Buntine and Geoffrey I. Webb and Nayyar Zaidi},
url = {https://rdcu.be/OX3g},
doi = {10.1007/s10994-018-5718-0},
issn = {1573-0565},
year = {2018},
date = {2018-01-01},
journal = {Machine Learning},
volume = {107},
number = {8-10},
pages = {1303-1331},
abstract = {This paper introduces a novel parameter estimation method for the probability tables of Bayesian network classifiers (BNCs), using hierarchical Dirichlet processes (HDPs). The main result of this paper is to show that improved parameter estimation allows BNCs to outperform leading learning methods such as random forest for both 0\textendash1 loss and RMSE, albeit just on categorical datasets. As data assets become larger, entering the hyped world of ``big'', efficient accurate classification requires three main elements: (1) classifiers with low-bias that can capture the fine-detail of large datasets (2) out-of-core learners that can learn from data without having to hold it all in main memory and (3) models that can classify new data very efficiently. The latest BNCs satisfy these requirements. Their bias can be controlled easily by increasing the number of parents of the nodes in the graph. Their structure can be learned out of core with a limited number of passes over the data. However, as the bias is made lower to accurately model classification tasks, so is the accuracy of their parameters' estimates, as each parameter is estimated from ever decreasing quantities of data. In this paper, we introduce the use of HDPs for accurate BNC parameter estimation even with lower bias. We conduct an extensive set of experiments on 68 standard datasets and demonstrate that our resulting classifiers perform very competitively with random forest in terms of prediction, while keeping the out-of-core capability and superior classification time.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This paper introduces a novel parameter estimation method for the probability tables of Bayesian network classifiers (BNCs), using hierarchical Dirichlet processes (HDPs). The main result of this paper is to show that improved parameter estimation allows BNCs to outperform leading learning methods such as random forest for both 0–1 loss and RMSE, albeit just on categorical datasets. As data assets become larger, entering the hyped world of ``big'', efficient accurate classification requires three main elements: (1) classifiers with low-bias that can capture the fine-detail of large datasets (2) out-of-core learners that can learn from data without having to hold it all in main memory and (3) models that can classify new data very efficiently. The latest BNCs satisfy these requirements. Their bias can be controlled easily by increasing the number of parents of the nodes in the graph. Their structure can be learned out of core with a limited number of passes over the data. However, as the bias is made lower to accurately model classification tasks, so is the accuracy of their parameters' estimates, as each parameter is estimated from ever decreasing quantities of data. In this paper, we introduce the use of HDPs for accurate BNC parameter estimation even with lower bias. We conduct an extensive set of experiments on 68 standard datasets and demonstrate that our resulting classifiers perform very competitively with random forest in terms of prediction, while keeping the out-of-core capability and superior classification time.
Zaidi, Nayyar A.; Petitjean, Francois; Webb, Geoffrey I.
Proceedings of the 2018 SIAM International Conference on Data Mining, pp. 459-467, 2018.
@inproceedings{Zaidi2018,
title = {Efficient and Effective Accelerated Hierarchical Higher-Order Logistic Regression for Large Data Quantities},
author = {Nayyar A. Zaidi and Francois Petitjean and Geoffrey I. Webb},
doi = {10.1137/1.9781611975321.52},
year = {2018},
date = {2018-01-01},
booktitle = {Proceedings of the 2018 SIAM International Conference on Data Mining},
pages = {459-467},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Chen, S.; Martinez, A.; Webb, G.; Wang, L.
Sample-based Attribute Selective AnDE for Large Data
IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 1, pp. 172-185, 2017, ISSN: 1041-4347.
@article{ChenEtAl16b,
title = {Sample-based Attribute Selective AnDE for Large Data},
author = {S. Chen and A. Martinez and G. Webb and L. Wang},
doi = {10.1109/TKDE.2016.2608881},
issn = {1041-4347},
year = {2017},
date = {2017-01-01},
journal = {IEEE Transactions on Knowledge and Data Engineering},
volume = {29},
number = {1},
pages = {172-185},
abstract = {More and more applications come with large data sets in the past decade. However, existing algorithms cannot guarantee to scale well on large data. Averaged n-Dependence Estimators (AnDE) allows for flexible learning from out-of-core data, by varying the value of n (number of super parents). Hence AnDE is especially appropriate for large data learning. In this paper, we propose a sample-based attribute selection technique for AnDE. It needs one more pass through the training data, in which a multitude of approximate AnDE models are built and efficiently assessed by leave-one-out cross validation. The use of a sample reduces the training time. Experiments on 15 large data sets demonstrate that the proposed technique significantly reduces AnDE's error at the cost of a modest increase in training time. This efficient and scalable out-of-core approach delivers superior or comparable performance to typical in-core Bayesian network classifiers.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
More and more applications come with large data sets in the past decade. However, existing algorithms cannot guarantee to scale well on large data. Averaged n-Dependence Estimators (AnDE) allows for flexible learning from out-of-core data, by varying the value of n (number of super parents). Hence AnDE is especially appropriate for large data learning. In this paper, we propose a sample-based attribute selection technique for AnDE. It needs one more pass through the training data, in which a multitude of approximate AnDE models are built and efficiently assessed by leave-one-out cross validation. The use of a sample reduces the training time. Experiments on 15 large data sets demonstrate that the proposed technique significantly reduces AnDE's error at the cost of a modest increase in training time. This efficient and scalable out-of-core approach delivers superior or comparable performance to typical in-core Bayesian network classifiers.
Chen, Shenglei; Martinez, Ana M.; Webb, Geoffrey I.; Wang, Limin
Selective AnDE for large data learning: a low-bias memory constrained approach
Knowledge and Information Systems, vol. 50, no. 2, pp. 475-503, 2017, ISSN: 0219-3116.
@article{ChenEtAl16,
title = {Selective AnDE for large data learning: a low-bias memory constrained approach},
author = {Shenglei Chen and Ana M. Martinez and Geoffrey I. Webb and Limin Wang},
doi = {10.1007/s10115-016-0937-9},
issn = {0219-3116},
year = {2017},
date = {2017-01-01},
journal = {Knowledge and Information Systems},
volume = {50},
number = {2},
pages = {475-503},
abstract = {Learning from data that are too big to fit into memory poses great challenges to currently available learning approaches. Averaged n-Dependence Estimators (AnDE) allows for a flexible learning from out-of-core data, by varying the value of n (number of super parents). Hence, AnDE is especially appropriate for learning from large quantities of data. Memory requirement in AnDE, however, increases combinatorially with the number of attributes and the parameter n. In large data learning, number of attributes is often large and we also expect high n to achieve low-bias classification. In order to achieve the lower bias of AnDE with higher n but with less memory requirement, we propose a memory constrained selective AnDE algorithm, in which two passes of learning through training examples are involved. The first pass performs attribute selection on super parents according to available memory, whereas the second one learns an AnDE model with parents only on the selected attributes. Extensive experiments show that the new selective AnDE has considerably lower bias and prediction error relative to A $$n'$$ n ´x DE, where $$n' = n-1$$ n ´x = n - 1 , while maintaining the same space complexity and similar time complexity. The proposed algorithm works well on categorical data. Numerical data sets need to be discretized first.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Learning from data that are too big to fit into memory poses great challenges to currently available learning approaches. Averaged n-Dependence Estimators (AnDE) allows for a flexible learning from out-of-core data, by varying the value of n (number of super parents). Hence, AnDE is especially appropriate for learning from large quantities of data. Memory requirement in AnDE, however, increases combinatorially with the number of attributes and the parameter n. In large data learning, number of attributes is often large and we also expect high n to achieve low-bias classification. In order to achieve the lower bias of AnDE with higher n but with less memory requirement, we propose a memory constrained selective AnDE algorithm, in which two passes of learning through training examples are involved. The first pass performs attribute selection on super parents according to available memory, whereas the second one learns an AnDE model with parents only on the selected attributes. Extensive experiments show that the new selective AnDE has considerably lower bias and prediction error relative to A $$n'$$ n ´x DE, where $$n' = n-1$$ n ´x = n - 1 , while maintaining the same space complexity and similar time complexity. The proposed algorithm works well on categorical data. Numerical data sets need to be discretized first.
Zaidi, Nayyar A.; Webb, Geoffrey I.
A Fast Trust-Region Newton Method for Softmax Logistic Regression
Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 705-713, SIAM 2017.
@inproceedings{ZaidiWebb17,
title = {A Fast Trust-Region Newton Method for Softmax Logistic Regression},
author = {Nayyar A. Zaidi and Geoffrey I. Webb},
doi = {10.1137/1.9781611974973.79},
year = {2017},
date = {2017-01-01},
booktitle = {Proceedings of the 2017 SIAM International Conference on Data Mining},
pages = {705-713},
organization = {SIAM},
abstract = {With the emergence of big data, there has been a growing
interest in optimization routines that lead to faster convergence of Logistic Regression (LR). Among many optimization methods such as Gradient Descent, Quasi-Newton, Conjugate Gradient, etc., the Trust-region based truncated Newton method (TRON) algorithm has been shown to converge
the fastest. The TRON algorithm also forms an important
component of the highly efficient and widely used liblinear
package. It has been shown that the WANBIA-C trick of
scaling with the log of the naive Bayes conditional probabilities can greatly accelerate the convergence of LR trained using (first-order) Gradient Descent and (approximate second-order) Quasi-Newton optimization. In this work we study
the applicability of the WANBIA-C trick to TRON. We first
devise a TRON algorithm optimizing the softmax objective
function and then demonstrate that WANBIA-C style preconditioning can be beneficial for TRON, leading to an ex-
tremely fast (batch) LR algorithm. Second, we present a
comparative analysis of one-vs-all LR and softmax LR in
terms of the 0-1 Loss, Bias, Variance, RMSE, Log-Loss,
Training and Classification time, and show that softmax LR
leads to significantly better RMSE and Log-Loss. We evaluate our proposed approach on 51 benchmark datasets.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
With the emergence of big data, there has been a growing
interest in optimization routines that lead to faster convergence of Logistic Regression (LR). Among many optimization methods such as Gradient Descent, Quasi-Newton, Conjugate Gradient, etc., the Trust-region based truncated Newton method (TRON) algorithm has been shown to converge
the fastest. The TRON algorithm also forms an important
component of the highly efficient and widely used liblinear
package. It has been shown that the WANBIA-C trick of
scaling with the log of the naive Bayes conditional probabilities can greatly accelerate the convergence of LR trained using (first-order) Gradient Descent and (approximate second-order) Quasi-Newton optimization. In this work we study
the applicability of the WANBIA-C trick to TRON. We first
devise a TRON algorithm optimizing the softmax objective
function and then demonstrate that WANBIA-C style preconditioning can be beneficial for TRON, leading to an ex-
tremely fast (batch) LR algorithm. Second, we present a
comparative analysis of one-vs-all LR and softmax LR in
terms of the 0-1 Loss, Bias, Variance, RMSE, Log-Loss,
Training and Classification time, and show that softmax LR
leads to significantly better RMSE and Log-Loss. We evaluate our proposed approach on 51 benchmark datasets.
interest in optimization routines that lead to faster convergence of Logistic Regression (LR). Among many optimization methods such as Gradient Descent, Quasi-Newton, Conjugate Gradient, etc., the Trust-region based truncated Newton method (TRON) algorithm has been shown to converge
the fastest. The TRON algorithm also forms an important
component of the highly efficient and widely used liblinear
package. It has been shown that the WANBIA-C trick of
scaling with the log of the naive Bayes conditional probabilities can greatly accelerate the convergence of LR trained using (first-order) Gradient Descent and (approximate second-order) Quasi-Newton optimization. In this work we study
the applicability of the WANBIA-C trick to TRON. We first
devise a TRON algorithm optimizing the softmax objective
function and then demonstrate that WANBIA-C style preconditioning can be beneficial for TRON, leading to an ex-
tremely fast (batch) LR algorithm. Second, we present a
comparative analysis of one-vs-all LR and softmax LR in
terms of the 0-1 Loss, Bias, Variance, RMSE, Log-Loss,
Training and Classification time, and show that softmax LR
leads to significantly better RMSE and Log-Loss. We evaluate our proposed approach on 51 benchmark datasets.
Zaidi, N.; Webb, Geoffrey I.; Carman, M.; Petitjean, F.; Buntine, W.; Hynes, H.; Sterck, H. De
Efficient Parameter Learning of Bayesian Network Classifiers
Machine Learning, vol. 106, no. 9-10, pp. 1289-1329, 2017.
@article{ZaidiEtAl17,
title = {Efficient Parameter Learning of Bayesian Network Classifiers},
author = {N. Zaidi and Geoffrey I. Webb and M. Carman and F. Petitjean and W. Buntine and H. Hynes and H. De Sterck},
url = {http://rdcu.be/oP1t},
doi = {10.1007/s10994-016-5619-z},
year = {2017},
date = {2017-01-01},
journal = {Machine Learning},
volume = {106},
number = {9-10},
pages = {1289-1329},
abstract = {Recent advances have demonstrated substantial benefits from learning with both generative and discriminative parameters. On the one hand, generative approaches address the estimation of the parameters of the joint distribution P(y,x), which for most network types is very computationally efficient (a notable exception to this are Markov networks) and on the other hand, discriminative approaches address the estimation of the parameters of the posterior distribution and, are more effective for classification, since they fit P(y|x) directly. However, discriminative approaches are less computationally efficient as the normalization factor in the conditional log-likelihood precludes the derivation of closed-form estimation of parameters. This paper introduces a new discriminative parameter learning method for Bayesian network classifiers that combines in an elegant fashion parameters learned using both generative and discriminative methods. The proposed method is discriminative in nature, but uses estimates of generative probabilities to speed-up the optimization process. A second contribution is to propose a simple framework to characterize the parameter learning task for Bayesian network classifiers. We conduct an extensive set of experiments on 72 standard datasets and demonstrate that our proposed discriminative parameterization provides an efficient alternative to other state-of-the-art parameterizations.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Recent advances have demonstrated substantial benefits from learning with both generative and discriminative parameters. On the one hand, generative approaches address the estimation of the parameters of the joint distribution P(y,x), which for most network types is very computationally efficient (a notable exception to this are Markov networks) and on the other hand, discriminative approaches address the estimation of the parameters of the posterior distribution and, are more effective for classification, since they fit P(y|x) directly. However, discriminative approaches are less computationally efficient as the normalization factor in the conditional log-likelihood precludes the derivation of closed-form estimation of parameters. This paper introduces a new discriminative parameter learning method for Bayesian network classifiers that combines in an elegant fashion parameters learned using both generative and discriminative methods. The proposed method is discriminative in nature, but uses estimates of generative probabilities to speed-up the optimization process. A second contribution is to propose a simple framework to characterize the parameter learning task for Bayesian network classifiers. We conduct an extensive set of experiments on 72 standard datasets and demonstrate that our proposed discriminative parameterization provides an efficient alternative to other state-of-the-art parameterizations.
Martinez, Ana M.; Webb, Geoffrey I.; Chen, Shenglei; Zaidi, Nayyar A.
Scalable Learning of Bayesian Network Classifiers
Journal of Machine Learning Research, vol. 17, no. 44, pp. 1-35, 2016.
@article{MartinezEtAl16,
title = {Scalable Learning of Bayesian Network Classifiers},
author = {Ana M. Martinez and Geoffrey I. Webb and Shenglei Chen and Nayyar A. Zaidi},
url = {http://jmlr.org/papers/v17/martinez16a.html},
year = {2016},
date = {2016-01-01},
journal = {Journal of Machine Learning Research},
volume = {17},
number = {44},
pages = {1-35},
abstract = {Ever increasing data quantity makes ever more urgent the need for highly scalable learners that have good classification performance. Therefore, an out-of-core learner with excellent time and space complexity, along with high expressivity (that is, capacity to learn very complex multivariate probability distributions) is extremely desirable. This paper presents such a learner. We propose an extension to the k-dependence Bayesian classifier (KDB) that discriminatively selects a sub- model of a full KDB classifier. It requires only one additional pass through the training data, making it a three-pass learner. Our extensive experimental evaluation on 16 large data sets reveals that this out-of-core algorithm achieves competitive classification performance, and substantially better training and classification time than state-of-the-art in-core learners such as random forest and linear and non-linear logistic regression.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Ever increasing data quantity makes ever more urgent the need for highly scalable learners that have good classification performance. Therefore, an out-of-core learner with excellent time and space complexity, along with high expressivity (that is, capacity to learn very complex multivariate probability distributions) is extremely desirable. This paper presents such a learner. We propose an extension to the k-dependence Bayesian classifier (KDB) that discriminatively selects a sub- model of a full KDB classifier. It requires only one additional pass through the training data, making it a three-pass learner. Our extensive experimental evaluation on 16 large data sets reveals that this out-of-core algorithm achieves competitive classification performance, and substantially better training and classification time than state-of-the-art in-core learners such as random forest and linear and non-linear logistic regression.
Zaidi, Nayyar A.; Petitjean, Francois; Webb, Geoffrey I.
Preconditioning an Artificial Neural Network Using Naive Bayes
Bailey, James; Khan, Latifur; Washio, Takashi; Dobbie, Gill; Huang, Zhexue Joshua; Wang, Ruili (Ed.): Proceedings of the 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016, pp. 341-353, Springer International Publishing, 2016, ISBN: 978-3-319-31753-3.
@inproceedings{ZaidiEtAl16,
title = {Preconditioning an Artificial Neural Network Using Naive Bayes},
author = {Nayyar A. Zaidi and Francois Petitjean and Geoffrey I. Webb},
editor = {James Bailey and Latifur Khan and Takashi Washio and Gill Dobbie and Zhexue Joshua Huang and Ruili Wang},
url = {http://dx.doi.org/10.1007/978-3-319-31753-3_28},
doi = {10.1007/978-3-319-31753-3_28},
isbn = {978-3-319-31753-3},
year = {2016},
date = {2016-01-01},
booktitle = {Proceedings of the 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016},
pages = {341-353},
publisher = {Springer International Publishing},
abstract = {Logistic Regression (LR) is a workhorse of the statistics community and a state-of-the-art machine learning classifier. It learns a linear model from inputs to outputs trained by optimizing the Conditional Log-Likelihood (CLL) of the data. Recently, it has been shown that preconditioning LR using a Naive Bayes (NB) model speeds up LR learning many-fold. One can, however, train a linear model by optimizing the mean-square-error (MSE) instead of CLL. This leads to an Artificial Neural Network (ANN) with no hidden layer. In this work, we study the effect of NB preconditioning on such an ANN classifier. Optimizing MSE instead of CLL may lead to a lower bias classifier and hence result in better performance on big datasets. We show that this NB preconditioning can speed-up convergence significantly. We also show that optimizing a linear model with MSE leads to a lower bias classifier than optimizing with CLL. We also compare the performance to state-of-the-art classifier Random Forest.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Logistic Regression (LR) is a workhorse of the statistics community and a state-of-the-art machine learning classifier. It learns a linear model from inputs to outputs trained by optimizing the Conditional Log-Likelihood (CLL) of the data. Recently, it has been shown that preconditioning LR using a Naive Bayes (NB) model speeds up LR learning many-fold. One can, however, train a linear model by optimizing the mean-square-error (MSE) instead of CLL. This leads to an Artificial Neural Network (ANN) with no hidden layer. In this work, we study the effect of NB preconditioning on such an ANN classifier. Optimizing MSE instead of CLL may lead to a lower bias classifier and hence result in better performance on big datasets. We show that this NB preconditioning can speed-up convergence significantly. We also show that optimizing a linear model with MSE leads to a lower bias classifier than optimizing with CLL. We also compare the performance to state-of-the-art classifier Random Forest.
Zaidi, Nayyar A.; Webb, Geoffrey I.; Carman, Mark J.; Petitjean, Francois; Cerquides, Jesus
ALRn: Accelerated higher-order logistic regression
Machine Learning, vol. 104, no. 2, pp. 151-194, 2016, ISSN: 1573-0565.
@article{ZaidiEtAl16b,
title = {ALRn: Accelerated higher-order logistic regression},
author = {Nayyar A. Zaidi and Geoffrey I. Webb and Mark J. Carman and Francois Petitjean and Jesus Cerquides},
doi = {10.1007/s10994-016-5574-8},
issn = {1573-0565},
year = {2016},
date = {2016-01-01},
journal = {Machine Learning},
volume = {104},
number = {2},
pages = {151-194},
abstract = {This paper introduces Accelerated Logistic Regression: a hybrid generative-discriminative approach to training Logistic Regression with high-order features. We present two main results: (1) that our combined generative-discriminative approach significantly improves the efficiency of Logistic Regression and (2) that incorporating higher order features (i.e. features that are the Cartesian products of the original features) reduces the bias of Logistic Regression, which in turn significantly reduces its error on large datasets. We assess the efficacy of Accelerated Logistic Regression by conducting an extensive set of experiments on 75 standard datasets. We demonstrate its competitiveness, particularly on large datasets, by comparing against state-of-the-art classifiers including Random Forest and Averaged n-Dependence Estimators.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This paper introduces Accelerated Logistic Regression: a hybrid generative-discriminative approach to training Logistic Regression with high-order features. We present two main results: (1) that our combined generative-discriminative approach significantly improves the efficiency of Logistic Regression and (2) that incorporating higher order features (i.e. features that are the Cartesian products of the original features) reduces the bias of Logistic Regression, which in turn significantly reduces its error on large datasets. We assess the efficacy of Accelerated Logistic Regression by conducting an extensive set of experiments on 75 standard datasets. We demonstrate its competitiveness, particularly on large datasets, by comparing against state-of-the-art classifiers including Random Forest and Averaged n-Dependence Estimators.
Chen, S.; Martinez, A.; Webb, G. I.
Highly Scalable Attribute Selection for AODE
Proceedings of the 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 86-97, 2014.
@inproceedings{ChenEtAl14,
title = {Highly Scalable Attribute Selection for AODE},
author = {S. Chen and A. Martinez and G. I. Webb},
doi = {10.1007/978-3-319-06605-9_8},
year = {2014},
date = {2014-01-01},
booktitle = {Proceedings of the 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining},
pages = {86-97},
abstract = {Averaged One-Dependence Estimators (AODE) is a popular
and effective approach to Bayesian learning. In this paper, a new
attribute selection approach is proposed for AODE. It can search in a
large model space, while it requires only a single extra pass through the
training data, resulting in a computationally efficient two-pass learning
algorithm. The experimental results indicate that the new technique significantly
reduces AODE.s bias at the cost of a modest increase in training
time. Its low bias and computational efficiency make it an attractive
algorithm for learning from big data.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Averaged One-Dependence Estimators (AODE) is a popular
and effective approach to Bayesian learning. In this paper, a new
attribute selection approach is proposed for AODE. It can search in a
large model space, while it requires only a single extra pass through the
training data, resulting in a computationally efficient two-pass learning
algorithm. The experimental results indicate that the new technique significantly
reduces AODE.s bias at the cost of a modest increase in training
time. Its low bias and computational efficiency make it an attractive
algorithm for learning from big data.
and effective approach to Bayesian learning. In this paper, a new
attribute selection approach is proposed for AODE. It can search in a
large model space, while it requires only a single extra pass through the
training data, resulting in a computationally efficient two-pass learning
algorithm. The experimental results indicate that the new technique significantly
reduces AODE.s bias at the cost of a modest increase in training
time. Its low bias and computational efficiency make it an attractive
algorithm for learning from big data.
Zaidi, N.; Carman, M.; Cerquides, J.; Webb, G. I.
Naive-Bayes Inspired Effective Pre-Conditioner for Speeding-up Logistic Regression
Proceedings of the 14th IEEE International Conference on Data Mining, pp. 1097-1102, 2014.
@inproceedings{ZaidiEtAl14,
title = {Naive-Bayes Inspired Effective Pre-Conditioner for Speeding-up Logistic Regression},
author = {N. Zaidi and M. Carman and J. Cerquides and G. I. Webb},
doi = {10.1109/ICDM.2014.53},
year = {2014},
date = {2014-01-01},
booktitle = {Proceedings of the 14th IEEE International Conference on Data Mining},
pages = {1097-1102},
abstract = {We propose an alternative parameterization of
Logistic Regression (LR) for the categorical data, multi-class
setting. LR optimizes the conditional log-likelihood over the
training data and is based on an iterative optimization procedure
to tune this objective function. The optimization procedure
employed may be sensitive to scale and hence an effective
pre-conditioning method is recommended. Many problems in
machine learning involve arbitrary scales or categorical data
(where simple standardization of features is not applicable).
The problem can be alleviated by using optimization routines
that are invariant to scale such as (second-order) Newton
methods. However, computing and inverting the Hessian is a
costly procedure and not feasible for big data. Thus one must
often rely on first-order methods such as gradient descent (GD),
stochastic gradient descent (SGD) or approximate secondorder
such as quasi-Newton (QN) routines, which are not
invariant to scale. This paper proposes a simple yet effective
pre-conditioner for speeding-up LR based on naive Bayes
conditional probability estimates. The idea is to scale each
attribute by the log of the conditional probability of that
attribute given the class. This formulation substantially speeds up
LR's convergence. It also provides a weighted naive Bayes
formulation which yields an effective framework for hybrid
generative-discriminative classification.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We propose an alternative parameterization of
Logistic Regression (LR) for the categorical data, multi-class
setting. LR optimizes the conditional log-likelihood over the
training data and is based on an iterative optimization procedure
to tune this objective function. The optimization procedure
employed may be sensitive to scale and hence an effective
pre-conditioning method is recommended. Many problems in
machine learning involve arbitrary scales or categorical data
(where simple standardization of features is not applicable).
The problem can be alleviated by using optimization routines
that are invariant to scale such as (second-order) Newton
methods. However, computing and inverting the Hessian is a
costly procedure and not feasible for big data. Thus one must
often rely on first-order methods such as gradient descent (GD),
stochastic gradient descent (SGD) or approximate secondorder
such as quasi-Newton (QN) routines, which are not
invariant to scale. This paper proposes a simple yet effective
pre-conditioner for speeding-up LR based on naive Bayes
conditional probability estimates. The idea is to scale each
attribute by the log of the conditional probability of that
attribute given the class. This formulation substantially speeds up
LR's convergence. It also provides a weighted naive Bayes
formulation which yields an effective framework for hybrid
generative-discriminative classification.
Logistic Regression (LR) for the categorical data, multi-class
setting. LR optimizes the conditional log-likelihood over the
training data and is based on an iterative optimization procedure
to tune this objective function. The optimization procedure
employed may be sensitive to scale and hence an effective
pre-conditioning method is recommended. Many problems in
machine learning involve arbitrary scales or categorical data
(where simple standardization of features is not applicable).
The problem can be alleviated by using optimization routines
that are invariant to scale such as (second-order) Newton
methods. However, computing and inverting the Hessian is a
costly procedure and not feasible for big data. Thus one must
often rely on first-order methods such as gradient descent (GD),
stochastic gradient descent (SGD) or approximate secondorder
such as quasi-Newton (QN) routines, which are not
invariant to scale. This paper proposes a simple yet effective
pre-conditioner for speeding-up LR based on naive Bayes
conditional probability estimates. The idea is to scale each
attribute by the log of the conditional probability of that
attribute given the class. This formulation substantially speeds up
LR's convergence. It also provides a weighted naive Bayes
formulation which yields an effective framework for hybrid
generative-discriminative classification.
Zaidi, Nayyar A.; Cerquides, Jesus; Carman, Mark J.; Webb, Geoffrey I.
Alleviating Naive Bayes Attribute Independence Assumption by Attribute Weighting
Journal of Machine Learning Research, vol. 14, pp. 1947-1988, 2013.
@article{Zaidi2013,
title = {Alleviating Naive Bayes Attribute Independence Assumption by Attribute Weighting},
author = {Nayyar A. Zaidi and Jesus Cerquides and Mark J. Carman and Geoffrey I. Webb},
url = {http://jmlr.org/papers/volume14/zaidi13a/zaidi13a.pdf},
year = {2013},
date = {2013-01-01},
journal = {Journal of Machine Learning Research},
volume = {14},
pages = {1947-1988},
abstract = {Despite the simplicity of the Naive Bayes classifier, it has continued to perform well against more sophisticated newcomers and has remained, therefore, of great interest to the machine learning community. Of numerous approaches to refining the naive Bayes classifier, attribute weighting has received less attention than it warrants. Most approaches, perhaps influenced by attribute weighting in other machine learning algorithms, use weighting to place more emphasis on highly predictive attributes than those that are less predictive. In this paper, we argue that for naive Bayes attribute weighting should instead be used to alleviate the conditional independence assumption. Based on this premise, we propose a weighted naive Bayes algorithm, called WANBIA, that selects weights to minimize either the negative conditional log likelihood or the mean squared error objective functions. We perform extensive evaluations and find that WANBIA is a competitive alternative to state of the art classifiers like Random Forest, Logistic Regression and A1DE.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Despite the simplicity of the Naive Bayes classifier, it has continued to perform well against more sophisticated newcomers and has remained, therefore, of great interest to the machine learning community. Of numerous approaches to refining the naive Bayes classifier, attribute weighting has received less attention than it warrants. Most approaches, perhaps influenced by attribute weighting in other machine learning algorithms, use weighting to place more emphasis on highly predictive attributes than those that are less predictive. In this paper, we argue that for naive Bayes attribute weighting should instead be used to alleviate the conditional independence assumption. Based on this premise, we propose a weighted naive Bayes algorithm, called WANBIA, that selects weights to minimize either the negative conditional log likelihood or the mean squared error objective functions. We perform extensive evaluations and find that WANBIA is a competitive alternative to state of the art classifiers like Random Forest, Logistic Regression and A1DE.
Zaidi, N.; Webb, G. I.
Fast and Effective Single Pass Bayesian Learning
Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 149-160, 2013.
@inproceedings{ZaidiWebb13,
title = {Fast and Effective Single Pass Bayesian Learning},
author = {N. Zaidi and G. I. Webb},
doi = {10.1007/978-3-642-37453-1_13},
year = {2013},
date = {2013-01-01},
booktitle = {Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining},
pages = {149-160},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Martinez, A.; Webb, G. I.; Flores, M.; Gamez, J.
Non-Disjoint Discretization for Aggregating One-Dependence Estimator Classifiers
Proceedings of the 7th International Conference on Hybrid Artificial Intelligent Systems, pp. 151-162, Springer, Berlin / Heidelberg, 2012, ISBN: 978-3-642-28930-9.
@inproceedings{MartinezEtAl12,
title = {Non-Disjoint Discretization for Aggregating One-Dependence Estimator Classifiers},
author = {A. Martinez and G. I. Webb and M. Flores and J. Gamez},
isbn = {978-3-642-28930-9},
year = {2012},
date = {2012-01-01},
booktitle = {Proceedings of the 7th International Conference on Hybrid Artificial Intelligent Systems},
pages = {151-162},
publisher = {Springer},
address = {Berlin / Heidelberg},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Salem, H.; Suraweera, P.; Webb, G. I.; Boughton, J. R.
Techniques for Efficient Learning without Search
Proceedings of the 16th Pacific-Asia Conference, PAKDD 2012, pp. 50-61, Springer, Kuala Lumpur, Malaysia, 2012.
@inproceedings{SalemEtAl12,
title = {Techniques for Efficient Learning without Search},
author = {H. Salem and P. Suraweera and G. I. Webb and J. R. Boughton},
url = {http://link.springer.com/chapter/10.1007%2F978-3-642-30217-6_5},
year = {2012},
date = {2012-01-01},
booktitle = {Proceedings of the 16th Pacific-Asia Conference, PAKDD 2012},
pages = {50-61},
publisher = {Springer},
address = {Kuala Lumpur, Malaysia},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Webb, G. I.; Boughton, J.; Zheng, F.; Ting, K. M.; Salem, H.
Machine Learning, vol. 86, no. 2, pp. 233-272, 2012, ISSN: 0885-6125.
@article{WebbEtAl12,
title = {Learning by extrapolation from marginal to full-multivariate probability distributions: Decreasingly naive Bayesian classification},
author = {G. I. Webb and J. Boughton and F. Zheng and K. M. Ting and H. Salem},
url = {http://dx.doi.org/10.1007/s10994-011-5263-6},
issn = {0885-6125},
year = {2012},
date = {2012-01-01},
journal = {Machine Learning},
volume = {86},
number = {2},
pages = {233-272},
publisher = {Springer},
address = {Netherlands},
abstract = {Averaged n-Dependence Estimators (AnDE) is an approach to probabilistic classification learning that learns by extrapolation from marginal
to full-multivariate probability distributions. It utilizes a single parameter that transforms the approach between a low-variance high-bias learner
(Naive Bayes) and a high-variance low-bias learner with Bayes optimal
asymptotic error. It extends the underlying strategy of Averaged One-Dependence Estimators (AODE), which relaxes the Naive Bayes independence assumption while retaining many of Naive Bayes' desirable computational and theoretical properties. AnDE further relaxes the independence assumption by generalizing AODE to higher-levels of dependence.
Extensive experimental evaluation shows that the bias-variance trade-off
for Averaged 2-Dependence Estimators results in strong predictive accuracy over a wide range of data sets. It has training time linear with
respect to the number of examples, supports incremental learning, handles directly missing values, and is robust in the face of noise. Beyond
the practical utility of its lower-dimensional variants, AnDE is of interest
in that it demonstrates that it is possible to create low-bias high-variance
generative learners and suggests strategies for developing even more powerful classifiers.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Averaged n-Dependence Estimators (AnDE) is an approach to probabilistic classification learning that learns by extrapolation from marginal
to full-multivariate probability distributions. It utilizes a single parameter that transforms the approach between a low-variance high-bias learner
(Naive Bayes) and a high-variance low-bias learner with Bayes optimal
asymptotic error. It extends the underlying strategy of Averaged One-Dependence Estimators (AODE), which relaxes the Naive Bayes independence assumption while retaining many of Naive Bayes' desirable computational and theoretical properties. AnDE further relaxes the independence assumption by generalizing AODE to higher-levels of dependence.
Extensive experimental evaluation shows that the bias-variance trade-off
for Averaged 2-Dependence Estimators results in strong predictive accuracy over a wide range of data sets. It has training time linear with
respect to the number of examples, supports incremental learning, handles directly missing values, and is robust in the face of noise. Beyond
the practical utility of its lower-dimensional variants, AnDE is of interest
in that it demonstrates that it is possible to create low-bias high-variance
generative learners and suggests strategies for developing even more powerful classifiers.
to full-multivariate probability distributions. It utilizes a single parameter that transforms the approach between a low-variance high-bias learner
(Naive Bayes) and a high-variance low-bias learner with Bayes optimal
asymptotic error. It extends the underlying strategy of Averaged One-Dependence Estimators (AODE), which relaxes the Naive Bayes independence assumption while retaining many of Naive Bayes' desirable computational and theoretical properties. AnDE further relaxes the independence assumption by generalizing AODE to higher-levels of dependence.
Extensive experimental evaluation shows that the bias-variance trade-off
for Averaged 2-Dependence Estimators results in strong predictive accuracy over a wide range of data sets. It has training time linear with
respect to the number of examples, supports incremental learning, handles directly missing values, and is robust in the face of noise. Beyond
the practical utility of its lower-dimensional variants, AnDE is of interest
in that it demonstrates that it is possible to create low-bias high-variance
generative learners and suggests strategies for developing even more powerful classifiers.
Zheng, F.; Webb, G. I.; Suraweera, P.; Zhu, L.
Subsumption Resolution: An Efficient and Effective Technique for Semi-Naive Bayesian Learning
Machine Learning, vol. 87, no. 1, pp. 93-125, 2012, ISSN: 0885-6125.
@article{ZhengEtAl12,
title = {Subsumption Resolution: An Efficient and Effective Technique for Semi-Naive Bayesian Learning},
author = {F. Zheng and G. I. Webb and P. Suraweera and L. Zhu},
doi = {10.1007/s10994-011-5275-2},
issn = {0885-6125},
year = {2012},
date = {2012-01-01},
journal = {Machine Learning},
volume = {87},
number = {1},
pages = {93-125},
publisher = {Springer},
address = {Netherlands},
abstract = {Semi-naive Bayesian techniques seek to improve the accuracy of naive
Bayes (NB) by relaxing the attribute independence assumption. We present a new
type of semi-naive Bayesian operation, Subsumption Resolution (SR), which efficiently identifies occurrences of the specialization-generalization relationship and
eliminates generalizations at classification time.We extend SR to Near-Subsumption
Resolution (NSR) to delete near.generalizations in addition to generalizations. We
develop two versions of SR: one that performs SR during training, called eager SR
(ESR), and another that performs SR during testing, called lazy SR (LSR).We inves-
tigate the effect of ESR, LSR, NSR and conventional attribute elimination (BSE) on
NB and Averaged One-Dependence Estimators (AODE), a powerful alternative to
NB. BSE imposes very high training time overheads on NB and AODE accompanied
by varying decreases in classification time overheads. ESR, LSR and NSR impose
high training time and test time overheads on NB. However, LSR imposes no extra
training time overheads and only modest test time overheads on AODE, while ESR
and NSR impose modest training and test time overheads on AODE. Our extensive
experimental comparison on sixty UCI data sets shows that applying BSE, LSR or
NSR to NB significantly improves both zero-one loss and RMSE, while applying
BSE, ESR or NSR to AODE significantly improves zero-one loss and RMSE and
applying LSR to AODE significantly improves zero-one loss. The Friedman test and
Nemenyi test show that AODE with ESR or NSR have a significant zero-one loss and
RMSE advantage over Logistic Regression and a zero-one loss advantage overWeka.s
LibSVM implementation with a grid parameter search on categorical data. AODE
with LSR has a zero-one loss advantage over Logistic Regression and comparable
zero-one loss with LibSVM. Finally, we examine the circumstances under which the
elimination of near-generalizations proves beneficial.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Semi-naive Bayesian techniques seek to improve the accuracy of naive
Bayes (NB) by relaxing the attribute independence assumption. We present a new
type of semi-naive Bayesian operation, Subsumption Resolution (SR), which efficiently identifies occurrences of the specialization-generalization relationship and
eliminates generalizations at classification time.We extend SR to Near-Subsumption
Resolution (NSR) to delete near.generalizations in addition to generalizations. We
develop two versions of SR: one that performs SR during training, called eager SR
(ESR), and another that performs SR during testing, called lazy SR (LSR).We inves-
tigate the effect of ESR, LSR, NSR and conventional attribute elimination (BSE) on
NB and Averaged One-Dependence Estimators (AODE), a powerful alternative to
NB. BSE imposes very high training time overheads on NB and AODE accompanied
by varying decreases in classification time overheads. ESR, LSR and NSR impose
high training time and test time overheads on NB. However, LSR imposes no extra
training time overheads and only modest test time overheads on AODE, while ESR
and NSR impose modest training and test time overheads on AODE. Our extensive
experimental comparison on sixty UCI data sets shows that applying BSE, LSR or
NSR to NB significantly improves both zero-one loss and RMSE, while applying
BSE, ESR or NSR to AODE significantly improves zero-one loss and RMSE and
applying LSR to AODE significantly improves zero-one loss. The Friedman test and
Nemenyi test show that AODE with ESR or NSR have a significant zero-one loss and
RMSE advantage over Logistic Regression and a zero-one loss advantage overWeka.s
LibSVM implementation with a grid parameter search on categorical data. AODE
with LSR has a zero-one loss advantage over Logistic Regression and comparable
zero-one loss with LibSVM. Finally, we examine the circumstances under which the
elimination of near-generalizations proves beneficial.
Bayes (NB) by relaxing the attribute independence assumption. We present a new
type of semi-naive Bayesian operation, Subsumption Resolution (SR), which efficiently identifies occurrences of the specialization-generalization relationship and
eliminates generalizations at classification time.We extend SR to Near-Subsumption
Resolution (NSR) to delete near.generalizations in addition to generalizations. We
develop two versions of SR: one that performs SR during training, called eager SR
(ESR), and another that performs SR during testing, called lazy SR (LSR).We inves-
tigate the effect of ESR, LSR, NSR and conventional attribute elimination (BSE) on
NB and Averaged One-Dependence Estimators (AODE), a powerful alternative to
NB. BSE imposes very high training time overheads on NB and AODE accompanied
by varying decreases in classification time overheads. ESR, LSR and NSR impose
high training time and test time overheads on NB. However, LSR imposes no extra
training time overheads and only modest test time overheads on AODE, while ESR
and NSR impose modest training and test time overheads on AODE. Our extensive
experimental comparison on sixty UCI data sets shows that applying BSE, LSR or
NSR to NB significantly improves both zero-one loss and RMSE, while applying
BSE, ESR or NSR to AODE significantly improves zero-one loss and RMSE and
applying LSR to AODE significantly improves zero-one loss. The Friedman test and
Nemenyi test show that AODE with ESR or NSR have a significant zero-one loss and
RMSE advantage over Logistic Regression and a zero-one loss advantage overWeka.s
LibSVM implementation with a grid parameter search on categorical data. AODE
with LSR has a zero-one loss advantage over Logistic Regression and comparable
zero-one loss with LibSVM. Finally, we examine the circumstances under which the
elimination of near-generalizations proves beneficial.
Hui, B.; Yang, Y.; Webb, G. I.
Anytime Classification for a Pool of Instances
Machine Learning, vol. 77, no. 1, pp. 61-102, 2009.
@article{HuiYangWebb09,
title = {Anytime Classification for a Pool of Instances},
author = {B. Hui and Y. Yang and G. I. Webb},
doi = {10.1007/s10994-009-5118-6},
year = {2009},
date = {2009-01-01},
journal = {Machine Learning},
volume = {77},
number = {1},
pages = {61-102},
publisher = {Springer},
address = {Netherlands},
abstract = {In many real-world applications of classification learning, such as
credit card transaction vetting or classification embedded in sensor
nodes, multiple instances simultaneously require classification under
computational resource constraints such as limited time or limited
battery capacity. In such a situation, available computational
resources should be allocated across the instances in order to
optimize the overall classification efficacy and efficiency. We
propose a novel anytime classification framework, Scheduling Anytime
Averaged Probabilistic Estimators (SAAPE), which is capable of
classifying a pool of instances, delivering accurate results whenever
interrupted and optimizing the collective classification
performance. Following the practice of our previous anytime
classification system AAPE, SAAPE runs a sequence of very efficient
Bayesian probabilistic classifiers to classify each single
instance. Furthermore, SAAPE implements seven alternative scheduling
schemes to decide which instance gets available computational
resources next such that a new classifier can be applied to refine its
classification. We formally present each scheduling scheme's
definition, rationale and time complexity. We conduct large-scale
experiments using 60 benchmark data sets and diversified statistical
tests to evaluate SAAPE's performance on zero-one loss classification
as well as on probability estimation. We analyze each scheduling
scheme's advantage and disadvantage according to both theoretical
understandings and empirical observations. Consequently we identify
effective scheduling schemes that enable SAAPE to accomplish accurate
anytime classification for a pool of instances.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In many real-world applications of classification learning, such as
credit card transaction vetting or classification embedded in sensor
nodes, multiple instances simultaneously require classification under
computational resource constraints such as limited time or limited
battery capacity. In such a situation, available computational
resources should be allocated across the instances in order to
optimize the overall classification efficacy and efficiency. We
propose a novel anytime classification framework, Scheduling Anytime
Averaged Probabilistic Estimators (SAAPE), which is capable of
classifying a pool of instances, delivering accurate results whenever
interrupted and optimizing the collective classification
performance. Following the practice of our previous anytime
classification system AAPE, SAAPE runs a sequence of very efficient
Bayesian probabilistic classifiers to classify each single
instance. Furthermore, SAAPE implements seven alternative scheduling
schemes to decide which instance gets available computational
resources next such that a new classifier can be applied to refine its
classification. We formally present each scheduling scheme's
definition, rationale and time complexity. We conduct large-scale
experiments using 60 benchmark data sets and diversified statistical
tests to evaluate SAAPE's performance on zero-one loss classification
as well as on probability estimation. We analyze each scheduling
scheme's advantage and disadvantage according to both theoretical
understandings and empirical observations. Consequently we identify
effective scheduling schemes that enable SAAPE to accomplish accurate
anytime classification for a pool of instances.
credit card transaction vetting or classification embedded in sensor
nodes, multiple instances simultaneously require classification under
computational resource constraints such as limited time or limited
battery capacity. In such a situation, available computational
resources should be allocated across the instances in order to
optimize the overall classification efficacy and efficiency. We
propose a novel anytime classification framework, Scheduling Anytime
Averaged Probabilistic Estimators (SAAPE), which is capable of
classifying a pool of instances, delivering accurate results whenever
interrupted and optimizing the collective classification
performance. Following the practice of our previous anytime
classification system AAPE, SAAPE runs a sequence of very efficient
Bayesian probabilistic classifiers to classify each single
instance. Furthermore, SAAPE implements seven alternative scheduling
schemes to decide which instance gets available computational
resources next such that a new classifier can be applied to refine its
classification. We formally present each scheduling scheme's
definition, rationale and time complexity. We conduct large-scale
experiments using 60 benchmark data sets and diversified statistical
tests to evaluate SAAPE's performance on zero-one loss classification
as well as on probability estimation. We analyze each scheduling
scheme's advantage and disadvantage according to both theoretical
understandings and empirical observations. Consequently we identify
effective scheduling schemes that enable SAAPE to accomplish accurate
anytime classification for a pool of instances.
Liu, B.; Yang, Y.; Webb, G. I.; Boughton, J.
Proceedings of the 13th Pacific-Asia Conference, PAKDD 2009, pp. 302-313, Springer, Bangkok, Thailand, 2009.
@inproceedings{LiuYangWebbBoughton09,
title = {A Comparative Study of Bandwidth Choice in Kernel Density Estimation for Naive Bayesian Classification},
author = {B. Liu and Y. Yang and G. I. Webb and J. Boughton},
doi = {10.1007/2F978-3-642-01307-2_29},
year = {2009},
date = {2009-01-01},
booktitle = {Proceedings of the 13th Pacific-Asia Conference, PAKDD 2009},
pages = {302-313},
publisher = {Springer},
address = {Bangkok, Thailand},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Yang, Y.; Webb, G. I.
Discretization for Naive-Bayes Learning: Managing Discretization Bias and Variance
Machine Learning, vol. 74, no. 1, pp. 39-74, 2009.
@article{YangWebb09,
title = {Discretization for Naive-Bayes Learning: Managing Discretization Bias and Variance},
author = {Y. Yang and G. I. Webb},
doi = {10.1007/s10994-008-5083-5},
year = {2009},
date = {2009-01-01},
journal = {Machine Learning},
volume = {74},
number = {1},
pages = {39-74},
publisher = {Springer},
address = {Netherlands},
abstract = {Quantitative attributes are usually discretized in Naive-Bayes learning. We establish simple conditions under which discretization is equivalent to use of the true probability density function during naive-Bayes learning. The use of different discretization techniques can be expected to affect the classification bias and variance of generated naive-Bayes classifiers, effects we name discretization bias and variance. We argue that by properly managing discretization bias and variance, we can effectively reduce naive-Bayes classification error. In particular, we supply insights into managing discretization bias and variance by adjusting the number of intervals and the number of training instances contained in each interval. We accordingly propose proportional discretization and fixed frequency discretization, two efficient unsupervised discretization methods that are able to effectively manage discretization bias and variance. We evaluate our new techniques against four key discretization methods for naive-Bayes classifiers. The experimental results support our theoretical analyses by showing that with statistically significant frequency, naive-Bayes classifiers trained on data discretized by our new methods are able to achieve lower classification error than those trained on data discretized by current established discretization methods.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Quantitative attributes are usually discretized in Naive-Bayes learning. We establish simple conditions under which discretization is equivalent to use of the true probability density function during naive-Bayes learning. The use of different discretization techniques can be expected to affect the classification bias and variance of generated naive-Bayes classifiers, effects we name discretization bias and variance. We argue that by properly managing discretization bias and variance, we can effectively reduce naive-Bayes classification error. In particular, we supply insights into managing discretization bias and variance by adjusting the number of intervals and the number of training instances contained in each interval. We accordingly propose proportional discretization and fixed frequency discretization, two efficient unsupervised discretization methods that are able to effectively manage discretization bias and variance. We evaluate our new techniques against four key discretization methods for naive-Bayes classifiers. The experimental results support our theoretical analyses by showing that with statistically significant frequency, naive-Bayes classifiers trained on data discretized by our new methods are able to achieve lower classification error than those trained on data discretized by current established discretization methods.
Yang, Y.; Webb, G. I.; Cerquides, J.; Korb, K.; Boughton, J.; Ting, K-M.
IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 12, pp. 1652-1665, 2007.
@article{YangWebbCerquideszKorbBoughtonTing07,
title = {To Select or To Weigh: A Comparative Study of Linear Combination Schemes for SuperParent-One-Dependence Estimators},
author = {Y. Yang and G. I. Webb and J. Cerquides and K. Korb and J. Boughton and K-M. Ting},
doi = {10.1109/TKDE.2007.190650},
year = {2007},
date = {2007-01-01},
journal = {IEEE Transactions on Knowledge and Data Engineering},
volume = {19},
number = {12},
pages = {1652-1665},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA},
abstract = {We conduct a large-scale comparative study on linearly combining superparent-one-dependence estimators (SPODEs), a popular family of semi-naive Bayesian classifiers. Altogether 16 model selection and weighing schemes, 58 benchmark data sets, as well as various statistical tests are employed. This paper's main contributions are three-fold. First, it formally presents each scheme's definition, rationale and time complexity; and hence can serve as a comprehensive reference for researchers interested in ensemble learning. Second, it offers bias-variance analysis for each scheme's classification error performance. Third, it identifies effective schemes that meet various needs in practice. This leads to accurate and fast classification algorithms with immediate and significant impact on real-world applications. Another important feature of our study is using a variety of statistical tests to evaluate multiple learning methods across multiple data sets.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
We conduct a large-scale comparative study on linearly combining superparent-one-dependence estimators (SPODEs), a popular family of semi-naive Bayesian classifiers. Altogether 16 model selection and weighing schemes, 58 benchmark data sets, as well as various statistical tests are employed. This paper's main contributions are three-fold. First, it formally presents each scheme's definition, rationale and time complexity; and hence can serve as a comprehensive reference for researchers interested in ensemble learning. Second, it offers bias-variance analysis for each scheme's classification error performance. Third, it identifies effective schemes that meet various needs in practice. This leads to accurate and fast classification algorithms with immediate and significant impact on real-world applications. Another important feature of our study is using a variety of statistical tests to evaluate multiple learning methods across multiple data sets.
Yang, Y.; Webb, G. I.; Korb, K.; Ting, K-M.
Machine Learning, vol. 69, no. 1, pp. 35-53, 2007.
@article{YangWebbKorbTing07,
title = {Classifying under Computational Resource Constraints: Anytime Classification Using Probabilistic Estimators},
author = {Y. Yang and G. I. Webb and K. Korb and K-M. Ting},
doi = {10.1007/s10994-007-5020-z},
year = {2007},
date = {2007-01-01},
journal = {Machine Learning},
volume = {69},
number = {1},
pages = {35-53},
publisher = {Springer},
address = {Netherlands},
abstract = {In many online applications of machine learning, the computational resources available for classification will vary from time to time. Most techniques are designed to operate within the constraints of the minimum expected resources and fail to utilize further resources when they are available. We propose a novel anytime classification algorithm, anytime averaged probabilistic estimators (AAPE), which is capable of delivering strong prediction accuracy with little CPU time and utilizing additional CPU time to increase classification accuracy. The idea is to run an ordered sequence of very efficient Bayesian probabilistic estimators (single improvement steps) until classification time runs out. Theoretical studies and empirical validations reveal that by properly identifying, ordering, invoking and ensembling single improvement steps, AAPE is able to accomplish accurate classification whenever it is interrupted. It is also able to output class probability estimates beyond simple 0/1-loss classifications, as well as adeptly handle incremental learning.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In many online applications of machine learning, the computational resources available for classification will vary from time to time. Most techniques are designed to operate within the constraints of the minimum expected resources and fail to utilize further resources when they are available. We propose a novel anytime classification algorithm, anytime averaged probabilistic estimators (AAPE), which is capable of delivering strong prediction accuracy with little CPU time and utilizing additional CPU time to increase classification accuracy. The idea is to run an ordered sequence of very efficient Bayesian probabilistic estimators (single improvement steps) until classification time runs out. Theoretical studies and empirical validations reveal that by properly identifying, ordering, invoking and ensembling single improvement steps, AAPE is able to accomplish accurate classification whenever it is interrupted. It is also able to output class probability estimates beyond simple 0/1-loss classifications, as well as adeptly handle incremental learning.
Zheng, F.; Webb, G. I.
Finding the Right Family: Parent and Child Selection for Averaged One-Dependence Estimators
Lecture Notes in Artificial Intelligence 4710: Proceedings of the 18th European Conference on Machine Learning (ECML'07), pp. 490-501, Springer-Verlag, Warsaw, Poland, 2007.
@inproceedings{ZhengWebb07,
title = {Finding the Right Family: Parent and Child Selection for Averaged One-Dependence Estimators},
author = {F. Zheng and G. I. Webb},
year = {2007},
date = {2007-01-01},
booktitle = {Lecture Notes in Artificial Intelligence 4710: Proceedings of the 18th European Conference on Machine Learning (ECML'07)},
pages = {490-501},
publisher = {Springer-Verlag},
address = {Warsaw, Poland},
abstract = {Averaged One-Dependence Estimators (AODE) classifies by uniformly aggregating all qualified one-dependence estimators (ODEs). Its capacity to significantly improve naive Bayes' accuracy without undue time complexity has attracted substantial interest. Forward Sequential Selection and Backwards Sequential Elimination are effective wrapper techniques to identify and repair harmful interdependencies which have been profitably applied to naive Bayes. However, their straightforward application to AODE has previously proved ineffective. We investigate novel variants of these strategies. Our extensive experiments show that elimination of child attributes from within the constituent ODEs results in a significant improvement in probability estimate and reductions in bias and error relative to unmodified AODE. In contrast, elimination of complete constituent ODEs and the four types of attribute addition are found to be less effective and do not demonstrate any strong advantage over AODE. These surprising results lead to effective techniques for improving AODE's prediction accuracy.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Averaged One-Dependence Estimators (AODE) classifies by uniformly aggregating all qualified one-dependence estimators (ODEs). Its capacity to significantly improve naive Bayes' accuracy without undue time complexity has attracted substantial interest. Forward Sequential Selection and Backwards Sequential Elimination are effective wrapper techniques to identify and repair harmful interdependencies which have been profitably applied to naive Bayes. However, their straightforward application to AODE has previously proved ineffective. We investigate novel variants of these strategies. Our extensive experiments show that elimination of child attributes from within the constituent ODEs results in a significant improvement in probability estimate and reductions in bias and error relative to unmodified AODE. In contrast, elimination of complete constituent ODEs and the four types of attribute addition are found to be less effective and do not demonstrate any strong advantage over AODE. These surprising results lead to effective techniques for improving AODE's prediction accuracy.
Lu, J.; Yang, Y.; Webb, G. I.
Incremental Discretization for Naive-Bayes Classifier
Li, Xue; Zaiane, Osmar R.; Li, Zhanhuai (Ed.): Lecture Notes in Computer Science 4093: Proceedings of the Second International Conference on Advanced Data Mining and Applications (ADMA 2006), pp. 223-238, Springer, Xian, China, 2006.
@inproceedings{LuYangWebb06,
title = {Incremental Discretization for Naive-Bayes Classifier},
author = {J. Lu and Y. Yang and G. I. Webb},
editor = {Xue Li and Osmar R. Zaiane and Zhanhuai Li},
year = {2006},
date = {2006-01-01},
booktitle = {Lecture Notes in Computer Science 4093: Proceedings of the Second International Conference on Advanced Data Mining and Applications (ADMA 2006)},
pages = {223-238},
publisher = {Springer},
address = {Xian, China},
abstract = {Naive-Bayes classifiers (NB) support incremental learning. However, the lack of effective incremental discretization methods has been hindering NB's incremental learning in face of quantitative data. This problem is further compounded by the fact that quantitative data are everywhere, from temperature readings to share prices. In this paper, we present a novel incremental discretization method for NB, incremental flexible frequency discretization (IFFD). IFFD discretizes values of a quantitative attribute into a sequence of intervals of flexible sizes. It allows online insertion and splitting operation on intervals. Theoretical analysis and experimental test are conducted to compare IFFD with alternative methods. Empirical evidence suggests that IFFD is efficient and effective. NB coupled with IFFD achieves a rapport between high learning efficiency and high classification accuracy in the context of incremental learning.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Naive-Bayes classifiers (NB) support incremental learning. However, the lack of effective incremental discretization methods has been hindering NB's incremental learning in face of quantitative data. This problem is further compounded by the fact that quantitative data are everywhere, from temperature readings to share prices. In this paper, we present a novel incremental discretization method for NB, incremental flexible frequency discretization (IFFD). IFFD discretizes values of a quantitative attribute into a sequence of intervals of flexible sizes. It allows online insertion and splitting operation on intervals. Theoretical analysis and experimental test are conducted to compare IFFD with alternative methods. Empirical evidence suggests that IFFD is efficient and effective. NB coupled with IFFD achieves a rapport between high learning efficiency and high classification accuracy in the context of incremental learning.
Yang, Y.; Webb, G. I.; Cerquides, J.; Korb, K.; Boughton, J.; Ting, K-M.
To Select or To Weigh: A Comparative Study of Model Selection and Model Weighing for SPODE Ensembles
Furkranz, J.; Scheffer, T.; Spiliopoulou, M. (Ed.): Lecture Notes in Computer Science 4212: Proceedings of the 17th European Conference on Machine Learning (ECML'06), pp. 533-544, Springer-Verlag, Berlin, Germany, 2006.
@inproceedings{YangWebbCerquideKorbBoughtonTing06,
title = {To Select or To Weigh: A Comparative Study of Model Selection and Model Weighing for SPODE Ensembles},
author = {Y. Yang and G. I. Webb and J. Cerquides and K. Korb and J. Boughton and K-M. Ting},
editor = {J. Furkranz and T. Scheffer and M. Spiliopoulou},
year = {2006},
date = {2006-01-01},
booktitle = {Lecture Notes in Computer Science 4212: Proceedings of the 17th European Conference on Machine Learning (ECML'06)},
pages = {533-544},
publisher = {Springer-Verlag},
address = {Berlin, Germany},
abstract = {An ensemble of Super-Parent-One-Dependence Estimators (SPODEs) offers a powerful yet simple alternative to naive Bayes classifiers, achieving significantly higher classification accuracy at a moderate cost in classification efficiency. Currently there exist two families of methodologies that ensemble candidate SPODEs for classification. One is to select only helpful SPODEs and uniformly average their probability estimates, a type of model selection. Another is to assign a weight to each SPODE and linearly combine their probability estimates, a methodology named model weighing. This paper presents a theoretical and empirical study comparing model selection and model weighing for ensembling SPODEs. The focus is on maximizing the ensemble's classification accuracy while minimizing its computational time. A number of representative selection and weighing schemes are studied, providing a comprehensive research on this topic and identifying effective schemes that provide alternative trades-offs between speed and expected error},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
An ensemble of Super-Parent-One-Dependence Estimators (SPODEs) offers a powerful yet simple alternative to naive Bayes classifiers, achieving significantly higher classification accuracy at a moderate cost in classification efficiency. Currently there exist two families of methodologies that ensemble candidate SPODEs for classification. One is to select only helpful SPODEs and uniformly average their probability estimates, a type of model selection. Another is to assign a weight to each SPODE and linearly combine their probability estimates, a methodology named model weighing. This paper presents a theoretical and empirical study comparing model selection and model weighing for ensembling SPODEs. The focus is on maximizing the ensemble's classification accuracy while minimizing its computational time. A number of representative selection and weighing schemes are studied, providing a comprehensive research on this topic and identifying effective schemes that provide alternative trades-offs between speed and expected error
Zheng, F.; Webb, G. I.
Efficient Lazy Elimination for Averaged One-Dependence Estimators
Cohen, W.; Moore, A. (Ed.): ACM International Conference Proceeding Series, Vol. 148: The Proceedings of the Twenty-third International Conference on Machine Learning (ICML'06), pp. 1113-1120, ACM Press, Pittsburgh, Pennsylvania, 2006.
@inproceedings{ZhengWebb06,
title = {Efficient Lazy Elimination for Averaged One-Dependence Estimators},
author = {F. Zheng and G. I. Webb},
editor = {W. Cohen and A. Moore},
url = {http://dl.acm.org/authorize?N00547},
year = {2006},
date = {2006-01-01},
booktitle = {ACM International Conference Proceeding Series, Vol. 148: The Proceedings of the Twenty-third International Conference on Machine Learning (ICML'06)},
pages = {1113-1120},
publisher = {ACM Press},
address = {Pittsburgh, Pennsylvania},
abstract = {Semi-naive Bayesian classifiers seek to retain the numerous strengths of naive Bayes while reducing error by weakening the attribute independence assumption. Backwards Sequential Elimination (BSE) is a wrapper technique for attribute elimination that has proved effective at this task. We explore a new efficient technique, Lazy Elimination (LE), which eliminates highly related attribute-values at classification time without the computational overheads inherent in wrapper techniques. We analyze the effect of LE and BSE on Averaged One-Dependence Estimators (AODE), a state-of-the-art semi-naive Bayesian algorithm. Our extensive experiments show that LE significantly reduces bias and error without undue additional computation, while BSE significantly reduces bias but not error, with high training time complexity. In the context of AODE, LE has a significant advantage over BSE in both computational efficiency and error.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Semi-naive Bayesian classifiers seek to retain the numerous strengths of naive Bayes while reducing error by weakening the attribute independence assumption. Backwards Sequential Elimination (BSE) is a wrapper technique for attribute elimination that has proved effective at this task. We explore a new efficient technique, Lazy Elimination (LE), which eliminates highly related attribute-values at classification time without the computational overheads inherent in wrapper techniques. We analyze the effect of LE and BSE on Averaged One-Dependence Estimators (AODE), a state-of-the-art semi-naive Bayesian algorithm. Our extensive experiments show that LE significantly reduces bias and error without undue additional computation, while BSE significantly reduces bias but not error, with high training time complexity. In the context of AODE, LE has a significant advantage over BSE in both computational efficiency and error.
Webb, G. I.; Boughton, J.; Wang, Z.
Not So Naive Bayes: Aggregating One-Dependence Estimators
Machine Learning, vol. 58, no. 1, pp. 5-24, 2005.
@article{WebbBoughtonWang05,
title = {Not So Naive Bayes: Aggregating One-Dependence Estimators},
author = {G. I. Webb and J. Boughton and Z. Wang},
doi = {10.1007/s10994-005-4258-6},
year = {2005},
date = {2005-01-01},
journal = {Machine Learning},
volume = {58},
number = {1},
pages = {5-24},
publisher = {Springer},
address = {Netherlands},
abstract = {Of numerous proposals to improve the accuracy of naive Bayes by weakening its attribute independence assumption, both LBR and TAN have demonstrated remarkable error performance. However, both techniques obtain this outcome at a considerable computational cost. We present a new approach to weakening the attribute independence assumption by averaging all of a constrained class of classifiers. In extensive experiments this technique delivers comparable prediction accuracy to LBR and TAN with substantially improved computational efficiency.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Of numerous proposals to improve the accuracy of naive Bayes by weakening its attribute independence assumption, both LBR and TAN have demonstrated remarkable error performance. However, both techniques obtain this outcome at a considerable computational cost. We present a new approach to weakening the attribute independence assumption by averaging all of a constrained class of classifiers. In extensive experiments this technique delivers comparable prediction accuracy to LBR and TAN with substantially improved computational efficiency.
Zheng, F.; I., Webb. G.
A Comparative Study of Semi-naive Bayes Methods in Classification Learning
Simoff, S. J.; Williams, G. J.; Galloway, J.; Kolyshkina, I. (Ed.): Proceedings of the Fourth Australasian Data Mining Conference (AusDM05), pp. 141-156, University of Technology, Sydney, Australia, 2005.
@inproceedings{ZhengWebb05,
title = {A Comparative Study of Semi-naive Bayes Methods in Classification Learning},
author = {F. Zheng and Webb. G. I.},
editor = {S. J. Simoff and G. J. Williams and J. Galloway and I. Kolyshkina},
year = {2005},
date = {2005-01-01},
booktitle = {Proceedings of the Fourth Australasian Data Mining Conference (AusDM05)},
pages = {141-156},
publisher = {University of Technology},
address = {Sydney, Australia},
abstract = {Numerous techniques have sought to improve the accuracy of Naive Bayes (NB) by alleviating the attribute interdependence problem. This paper summarizes these semi-naive Bayesian methods into two groups: those that apply conventional NB with a new attribute set, and those that alter NB by allowing inter-dependencies between attributes. We review eight typical semi-naive Bayesian learning algorithms and perform error analysis using the bias-variance decomposition on thirty-six natural domains from the UCI Machine Learning Repository. In analysing the results of these experiments we provide general recommendations for selection between methods.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Numerous techniques have sought to improve the accuracy of Naive Bayes (NB) by alleviating the attribute interdependence problem. This paper summarizes these semi-naive Bayesian methods into two groups: those that apply conventional NB with a new attribute set, and those that alter NB by allowing inter-dependencies between attributes. We review eight typical semi-naive Bayesian learning algorithms and perform error analysis using the bias-variance decomposition on thirty-six natural domains from the UCI Machine Learning Repository. In analysing the results of these experiments we provide general recommendations for selection between methods.
Yang, Y.; Korb, K.; Ting, K-M.; Webb, G. I.
Ensemble Selection for SuperParent-One-Dependence Estimators
Zhang, S.; Jarvis, R. (Ed.): Lecture Notes in Computer Science 3809: Advances in Artificial Intelligence, Proceedings of the 18th Australian Joint Conference on Artificial Intelligence (AI 2005), pp. 102-111, Springer, Sydney, Australia, 2005.
@inproceedings{YangKorbTingWebb05,
title = {Ensemble Selection for SuperParent-One-Dependence Estimators},
author = {Y. Yang and K. Korb and K-M. Ting and G. I. Webb},
editor = {S. Zhang and R. Jarvis},
doi = {10.1007/11589990_13},
year = {2005},
date = {2005-01-01},
urldate = {2005-01-01},
booktitle = {Lecture Notes in Computer Science 3809: Advances in Artificial Intelligence, Proceedings of the 18th Australian Joint Conference on Artificial Intelligence (AI 2005)},
pages = {102-111},
publisher = {Springer},
address = {Sydney, Australia},
abstract = {SuperParent-One-Dependence Estimators (SPODEs) loosen Naive-Bayes\' attribute independence assumption by allowing each attribute to depend on a common single attribute (superparent) in addition to the class. An ensemble of SPODEs is able to achieve high classification accuracy with modest computational cost. This paper investigates how to select SPODEs for ensembling. Various popular model selection strategies are presented. Their learning efficacy and efficiency are theoretically analyzed and empirically verified. Accordingly, guidelines are investigated for choosing between selection criteria in differing contexts.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
SuperParent-One-Dependence Estimators (SPODEs) loosen Naive-Bayes' attribute independence assumption by allowing each attribute to depend on a common single attribute (superparent) in addition to the class. An ensemble of SPODEs is able to achieve high classification accuracy with modest computational cost. This paper investigates how to select SPODEs for ensembling. Various popular model selection strategies are presented. Their learning efficacy and efficiency are theoretically analyzed and empirically verified. Accordingly, guidelines are investigated for choosing between selection criteria in differing contexts.
Wang, Z.; Webb, G. I.; Zheng, F.
Selective Augmented Bayesian Network Classifiers Based on Rough Set Theory
Dai, H.; Srikant, R.; Zhang, C. (Ed.): Lecture Notes in Computer Science Vol. 3056: Proceedings of the Eighth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 04), pp. 319-328, Springer, Sydney, Australia, 2004.
@inproceedings{WangWebbZheng04,
title = {Selective Augmented Bayesian Network Classifiers Based on Rough Set Theory},
author = {Z. Wang and G. I. Webb and F. Zheng},
editor = {H. Dai and R. Srikant and C. Zhang},
year = {2004},
date = {2004-01-01},
booktitle = {Lecture Notes in Computer Science Vol. 3056: Proceedings of the Eighth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 04)},
pages = {319-328},
publisher = {Springer},
address = {Sydney, Australia},
abstract = {The naive Bayes classifier is widely used in interactive applications due to its computational efficiency, direct theoretical base, and competitive accuracy. However, its attribute independence assumption can result in sub-optimal accuracy. A number of techniques have explored simple relaxations of the attribute independence assumption in order to increase accuracy. TAN, Tree-Augmented Naive Bayes, is a state-of-the-art extension of naive Bayes, that can express limited forms of inter-dependence among attributes. Rough sets theory provides tools for expressing inexact or partial dependencies within dataset. In this paper, we present a variant of TAN and compare their tree classifier structures, which can be thought of as a selective restricted trees Bayesian classifier. It delivers lower error than both pre-existing state-of-the-art TAN-based classifiers, with substantially less computation than is required by the SuperParent approach.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The naive Bayes classifier is widely used in interactive applications due to its computational efficiency, direct theoretical base, and competitive accuracy. However, its attribute independence assumption can result in sub-optimal accuracy. A number of techniques have explored simple relaxations of the attribute independence assumption in order to increase accuracy. TAN, Tree-Augmented Naive Bayes, is a state-of-the-art extension of naive Bayes, that can express limited forms of inter-dependence among attributes. Rough sets theory provides tools for expressing inexact or partial dependencies within dataset. In this paper, we present a variant of TAN and compare their tree classifier structures, which can be thought of as a selective restricted trees Bayesian classifier. It delivers lower error than both pre-existing state-of-the-art TAN-based classifiers, with substantially less computation than is required by the SuperParent approach.
Shi, H.; Wang, Z.; Webb, G. I.; Huang, H.
A New Restricted Bayesian Network Classifier
Whang, K-Y.; Jeon, J.; Shim, K.; Srivastava, J. (Ed.): Lecture Notes in Artificial Intelligence Vol. 2637: Proceedings of the Seventh Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'03), pp. 265-270, Springer-Verlag, Seoul, Korea, 2003.
@inproceedings{ShiWangWebbHuang03,
title = {A New Restricted Bayesian Network Classifier},
author = {H. Shi and Z. Wang and G. I. Webb and H. Huang},
editor = {K-Y. Whang and J. Jeon and K. Shim and J. Srivastava},
year = {2003},
date = {2003-01-01},
booktitle = {Lecture Notes in Artificial Intelligence Vol. 2637: Proceedings of the Seventh Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'03)},
pages = {265-270},
publisher = {Springer-Verlag},
address = {Seoul, Korea},
abstract = {On the basis of examining the existing restricted Bayesian network classifiers, a new Bayes-theorem-based and more strictly restricted Bayesian-network-based classification model DLBAN is proposed, which can be viewed as a double-level Bayesian network augmented naive Bayes classification. The experimental results show that the DLBAN classifier is better than the TAN classifier in the most cases.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
On the basis of examining the existing restricted Bayesian network classifiers, a new Bayes-theorem-based and more strictly restricted Bayesian-network-based classification model DLBAN is proposed, which can be viewed as a double-level Bayesian network augmented naive Bayes classification. The experimental results show that the DLBAN classifier is better than the TAN classifier in the most cases.
Wang, Z.; Webb, G. I.; Zheng, F.
Adjusting Dependence Relations for Semi-Lazy TAN Classifiers
Gedeon, T. D.; Fung, L. C. C. (Ed.): Lecture Notes in Artificial Intelligence Vol. 2903: Proceedings of the 16th Australian Conference on Artificial Intelligence (AI 03), pp. 453-465, Springer, Perth, Australia, 2003.
@inproceedings{WangWebbZheng03,
title = {Adjusting Dependence Relations for Semi-Lazy TAN Classifiers},
author = {Z. Wang and G. I. Webb and F. Zheng},
editor = {T. D. Gedeon and L. C. C. Fung},
year = {2003},
date = {2003-01-01},
booktitle = {Lecture Notes in Artificial Intelligence Vol. 2903: Proceedings of the 16th Australian Conference on Artificial Intelligence (AI 03)},
pages = {453-465},
publisher = {Springer},
address = {Perth, Australia},
abstract = {The naive Bayesian classifier is a simple and effective classification method, which assumes a Bayesian network in which each attribute has the class label as its only one parent. But this assumption is not obviously hold in many real world domains. Tree-Augmented Na?ve Bayes (TAN) is a state-of-the-art extension of the naive Bayes, which can express partial dependence relations among attributes. In this paper, we analyze the implementations of two different TAN classifiers and their tree structures. Experiments show how different dependence relations impact on accuracy of TAN classifiers. We present a kind of semi-lazy TAN classifier, which builds a TAN identical to the original TAN at training time, but adjusts the dependence relations for a new test instance at classification time. Our extensive experimental results show that this kind of semi-lazy classifier delivers lower error than the original TAN and is more efficient than SuperParent TAN.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The naive Bayesian classifier is a simple and effective classification method, which assumes a Bayesian network in which each attribute has the class label as its only one parent. But this assumption is not obviously hold in many real world domains. Tree-Augmented Na?ve Bayes (TAN) is a state-of-the-art extension of the naive Bayes, which can express partial dependence relations among attributes. In this paper, we analyze the implementations of two different TAN classifiers and their tree structures. Experiments show how different dependence relations impact on accuracy of TAN classifiers. We present a kind of semi-lazy TAN classifier, which builds a TAN identical to the original TAN at training time, but adjusts the dependence relations for a new test instance at classification time. Our extensive experimental results show that this kind of semi-lazy classifier delivers lower error than the original TAN and is more efficient than SuperParent TAN.
Wang, Z.; Webb, G. I.
A Heuristic Lazy Bayesian Rules Algorithm
Simoff, S. J; Williams, G. J; Hegland, M. (Ed.): Proceedings of the First Australasian Data Mining Workshop (AusDM02), pp. 57-63, University of Technology, Canberra, Australia, 2002.
@inproceedings{WangWebb02b,
title = {A Heuristic Lazy Bayesian Rules Algorithm},
author = {Z. Wang and G. I. Webb},
editor = {S. J Simoff and G. J Williams and M. Hegland},
year = {2002},
date = {2002-01-01},
booktitle = {Proceedings of the First Australasian Data Mining Workshop (AusDM02)},
pages = {57-63},
publisher = {University of Technology},
address = {Canberra, Australia},
abstract = {Lazy Bayesian rule has demonstrated outstanding classification accuracy. However, it has high computational overheads when large numbers of instances are classified from a single training set. We compare lazy Bayesian rule and the tree-augmented Bayesian classifier, and present a new heuristic lazy Bayesian rule classifier that combines elements of the two. It requires less computation than lazy Bayesian rule, but demonstrates similar prediction accuracy.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Lazy Bayesian rule has demonstrated outstanding classification accuracy. However, it has high computational overheads when large numbers of instances are classified from a single training set. We compare lazy Bayesian rule and the tree-augmented Bayesian classifier, and present a new heuristic lazy Bayesian rule classifier that combines elements of the two. It requires less computation than lazy Bayesian rule, but demonstrates similar prediction accuracy.
Wang, Z.; Webb, G. I.
Comparison of Lazy Bayesian Rule Learning and Tree-Augmented Bayesian Learning
Proceedings of the IEEE International Conference on Data Mining (ICDM-2002), pp. 775-778, IEEE Computer Society, Maebashi City, Japan, 2002.
@inproceedings{WangWebb02,
title = {Comparison of Lazy Bayesian Rule Learning and Tree-Augmented Bayesian Learning},
author = {Z. Wang and G. I. Webb},
year = {2002},
date = {2002-01-01},
booktitle = {Proceedings of the IEEE International Conference on Data Mining (ICDM-2002)},
pages = {775-778},
publisher = {IEEE Computer Society},
address = {Maebashi City, Japan},
abstract = {The naive Bayes classifier is widely used in interactive applications due to its computational efficiency, direct theoretical base, and competitive accuracy. However, its attribute independence assumption can result in sub-optimal accuracy. A number of techniques have explored simple relaxations of the attribute independence assumption in order to increase accuracy. Among these, Lazy Bayesian Rules (LBR) and Tree-Augmented Na?ve-Bayes (TAN) have demonstrated strong prediction accuracy. However, their relative performance has never been evaluated. This paper compares and contrasts these two techniques, finding that they have comparable accuracy and hence should be selected according to computational profile. LBR is desirable when small numbers of objects are to be classified while TAN is desirable when large numbers of objects are to be classified},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The naive Bayes classifier is widely used in interactive applications due to its computational efficiency, direct theoretical base, and competitive accuracy. However, its attribute independence assumption can result in sub-optimal accuracy. A number of techniques have explored simple relaxations of the attribute independence assumption in order to increase accuracy. Among these, Lazy Bayesian Rules (LBR) and Tree-Augmented Na?ve-Bayes (TAN) have demonstrated strong prediction accuracy. However, their relative performance has never been evaluated. This paper compares and contrasts these two techniques, finding that they have comparable accuracy and hence should be selected according to computational profile. LBR is desirable when small numbers of objects are to be classified while TAN is desirable when large numbers of objects are to be classified
Webb, G. I.; Boughton, J.; Wang, Z.
Averaged One-Dependence Estimators: Preliminary Results
Simoff, S. J.; Williams, G. J.; Hegland, M. (Ed.): Proceedings of the First Australasian Data Mining Workshop (AusDM02), pp. 65-73, University of Technology, Canberra, Australia, 2002.
@inproceedings{WebbBoughtonWang02,
title = {Averaged One-Dependence Estimators: Preliminary Results},
author = {G. I. Webb and J. Boughton and Z. Wang},
editor = {S. J. Simoff and G. J. Williams and M. Hegland},
year = {2002},
date = {2002-01-01},
booktitle = {Proceedings of the First Australasian Data Mining Workshop (AusDM02)},
pages = {65-73},
publisher = {University of Technology},
address = {Canberra, Australia},
abstract = {Naive Bayes is a simple, computationally efficient and remarkably accurate approach to classification learning. These properties have led to its wide deployment in many online applications. However, it is based on an assumption that all attributes are conditionally independent given the class. This assumption leads to decreased accuracy in some applications. AODE overcomes the attribute independence assumption of naive Bayes by averaging over all models in which all attributes depend upon the class and a single other attribute. The resulting classification learning algorithm for nominal data is computationally efficient and achieves very low error rates.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Naive Bayes is a simple, computationally efficient and remarkably accurate approach to classification learning. These properties have led to its wide deployment in many online applications. However, it is based on an assumption that all attributes are conditionally independent given the class. This assumption leads to decreased accuracy in some applications. AODE overcomes the attribute independence assumption of naive Bayes by averaging over all models in which all attributes depend upon the class and a single other attribute. The resulting classification learning algorithm for nominal data is computationally efficient and achieves very low error rates.
Wang, Z.; Webb, G. I.; Dai, H.
Implementation of Lazy Bayesian Rules in the Weka System
Software Technology Catering for 21st Century: Proceedings of the International Symposium on Future Software Technology (ISFST2001), pp. 204-208, Software Engineers Association, Zheng Zhou, China, 2001.
@inproceedings{WangWebbDai01,
title = {Implementation of Lazy Bayesian Rules in the Weka System},
author = {Z. Wang and G. I. Webb and H. Dai},
year = {2001},
date = {2001-01-01},
booktitle = {Software Technology Catering for 21st Century: Proceedings of the International Symposium on Future Software Technology (ISFST2001)},
pages = {204-208},
publisher = {Software Engineers Association},
address = {Zheng Zhou, China},
abstract = {The na?ve Bayesian classification algorithms were shown to be computationally efficient and surprisingly accurate when the conditional independence assumption on which they are based is violated. The lazy Bayesian rule is the application of lazy learning techniques to Bayesian tree induction, which supports a weaker conditional attribute independence assumption. The Weka system is a full, industrial-strength implementation of essentially almost the state-of-the-art machine learning techniques, and it contains a framework, in the form of a Java class library, which supports applications that use embedded machine learning and even the implementation of new learning schemes. In this paper, we mainly discuss the implementation of the algorithm of lazy Bayesian rule in Weka System, and introduce all the methods to be used in the Java class. This is the first lazy learning scheme implemented in Weka System.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The na?ve Bayesian classification algorithms were shown to be computationally efficient and surprisingly accurate when the conditional independence assumption on which they are based is violated. The lazy Bayesian rule is the application of lazy learning techniques to Bayesian tree induction, which supports a weaker conditional attribute independence assumption. The Weka system is a full, industrial-strength implementation of essentially almost the state-of-the-art machine learning techniques, and it contains a framework, in the form of a Java class library, which supports applications that use embedded machine learning and even the implementation of new learning schemes. In this paper, we mainly discuss the implementation of the algorithm of lazy Bayesian rule in Weka System, and introduce all the methods to be used in the Java class. This is the first lazy learning scheme implemented in Weka System.
Webb, G. I.
Candidate Elimination Criteria for Lazy Bayesian Rules
Stumptner, M.; Corbett, D.; Brooks, M. J. (Ed.): Lecture Notes in Computer Science Vol. 2256: Proceedings of the 14th Australian Joint Conference on Artificial Intelligence (AI'01), pp. 545-556, Springer, Adelaide, Australia, 2001.
@inproceedings{Webb01b,
title = {Candidate Elimination Criteria for Lazy Bayesian Rules},
author = {G. I. Webb},
editor = {M. Stumptner and D. Corbett and M. J. Brooks},
doi = {10.1007%2F3-540-45656-2_47},
year = {2001},
date = {2001-01-01},
booktitle = {Lecture Notes in Computer Science Vol. 2256: Proceedings of the 14th Australian Joint Conference on Artificial Intelligence (AI'01)},
pages = {545-556},
publisher = {Springer},
address = {Adelaide, Australia},
abstract = {Lazy Bayesian Rules modify naive Bayesian classification to undo elements of the harmful attribute independence assumption. It has been shown to provide classification error comparable to boosting decision trees. This paper explores alternatives to the candidate elimination criterion employed within Lazy Bayesian Rules. Improvements over naive Bayes are consistent so long as the candidate elimination criteria ensures there is sufficient data for accurate probability estimation. However, the original candidate elimination criterion is demonstrated to provide better overall error reduction than the use of a minimum data subset size criterion.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Lazy Bayesian Rules modify naive Bayesian classification to undo elements of the harmful attribute independence assumption. It has been shown to provide classification error comparable to boosting decision trees. This paper explores alternatives to the candidate elimination criterion employed within Lazy Bayesian Rules. Improvements over naive Bayes are consistent so long as the candidate elimination criteria ensures there is sufficient data for accurate probability estimation. However, the original candidate elimination criterion is demonstrated to provide better overall error reduction than the use of a minimum data subset size criterion.
Zheng, Z.; Webb, G. I.
Lazy Learning of Bayesian Rules
Machine Learning, vol. 41, no. 1, pp. 53-84, 2000.
@article{ZhengWebb00,
title = {Lazy Learning of Bayesian Rules},
author = {Z. Zheng and G. I. Webb},
doi = {10.1023/A:1007613203719},
year = {2000},
date = {2000-01-01},
journal = {Machine Learning},
volume = {41},
number = {1},
pages = {53-84},
publisher = {Springer},
address = {Netherlands},
abstract = {The naive Bayesian classifier provides a simple and effective approach to classifier learning, but its attribute independence assumption is often violated in the real world. A number of approaches have sought to alleviate this problem. A Bayesian tree learning algorithm builds a decision tree, and generates a local naive Bayesian classifier at each leaf. The tests leading to a leaf can alleviate attribute interdependencies for the local naive Bayesian classifier. However, Bayesian tree learning still suffers from the small disjunct problem of tree learning. While inferred Bayesian trees demonstrate low average prediction error rates, there is reason to believe that error rates will be higher for those leaves with few training examples. This paper proposes the application of lazy learning techniques to Bayesian tree induction and presents the resulting lazy Bayesian rule learning algorithm, called LBR. For each test example, it builds a most appropriate rule with a local naive Bayesian classifier as its consequent. It is demonstrated that the computational requirements of LBR are reasonable in a wide cross selection of natural domains. Experiments with these domains show that, on average, this new algorithm obtains lower error rates significantly more often than the reverse in comparison to a naive Bayesian classifier, C4.5, a Bayesian tree learning algorithm, a constructive Bayesian classifier that eliminates attributes and constructs new attributes using Cartesian products of existing nominal attributes, and a lazy decision tree learning algorithm. It also outperforms, although the result is not statistically significant, a selective naive Bayesian classifier.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
The naive Bayesian classifier provides a simple and effective approach to classifier learning, but its attribute independence assumption is often violated in the real world. A number of approaches have sought to alleviate this problem. A Bayesian tree learning algorithm builds a decision tree, and generates a local naive Bayesian classifier at each leaf. The tests leading to a leaf can alleviate attribute interdependencies for the local naive Bayesian classifier. However, Bayesian tree learning still suffers from the small disjunct problem of tree learning. While inferred Bayesian trees demonstrate low average prediction error rates, there is reason to believe that error rates will be higher for those leaves with few training examples. This paper proposes the application of lazy learning techniques to Bayesian tree induction and presents the resulting lazy Bayesian rule learning algorithm, called LBR. For each test example, it builds a most appropriate rule with a local naive Bayesian classifier as its consequent. It is demonstrated that the computational requirements of LBR are reasonable in a wide cross selection of natural domains. Experiments with these domains show that, on average, this new algorithm obtains lower error rates significantly more often than the reverse in comparison to a naive Bayesian classifier, C4.5, a Bayesian tree learning algorithm, a constructive Bayesian classifier that eliminates attributes and constructs new attributes using Cartesian products of existing nominal attributes, and a lazy decision tree learning algorithm. It also outperforms, although the result is not statistically significant, a selective naive Bayesian classifier.
Ting, K. M.; Zheng, Z.; Webb, G. I.
Learning Lazy Rules to Improve the Performance of Classifiers
Coenen, F.; Macintosh, A. (Ed.): Proceedings of the Nineteenth SGES International Conference on Knowledge Based Systems and Applied Artificial Intelligence (ES'99), pp. 122-131, Springer, Peterhouse College, Cambridge, UK, 1999.
@inproceedings{TingZhengWebb99,
title = {Learning Lazy Rules to Improve the Performance of Classifiers},
author = {K. M. Ting and Z. Zheng and G. I. Webb},
editor = {F. Coenen and A. Macintosh},
year = {1999},
date = {1999-01-01},
booktitle = {Proceedings of the Nineteenth SGES International Conference on Knowledge Based Systems and Applied Artificial Intelligence (ES'99)},
pages = {122-131},
publisher = {Springer},
address = {Peterhouse College, Cambridge, UK},
abstract = {Based on an earlier study on lazy Bayesian rule learning, this paper introduces a general lazy learning framework, called LAZYRULE, that begins to learn a rule only when classifying a test case. The objective of the framework is to improve the performance of a base learning algorithm. It has the potential to be used for different types of base learning algorithms. LAZYRULE performs attribute elimination and training case selection using cross-validation to generate the most appropriate rule for each test case. At the consequent of the rule, it applies the base learning algorithm on the selected training subset and the remaining attributes to construct a classifier to make a prediction. This combined action seeks to build a better performing classifier for each test case than the classifier trained using all attributes and all training cases. We show empirically that LAZYRULE improves the performances of naive Bayesian classifiers and majority vote.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Based on an earlier study on lazy Bayesian rule learning, this paper introduces a general lazy learning framework, called LAZYRULE, that begins to learn a rule only when classifying a test case. The objective of the framework is to improve the performance of a base learning algorithm. It has the potential to be used for different types of base learning algorithms. LAZYRULE performs attribute elimination and training case selection using cross-validation to generate the most appropriate rule for each test case. At the consequent of the rule, it applies the base learning algorithm on the selected training subset and the remaining attributes to construct a classifier to make a prediction. This combined action seeks to build a better performing classifier for each test case than the classifier trained using all attributes and all training cases. We show empirically that LAZYRULE improves the performances of naive Bayesian classifiers and majority vote.
Zheng, Z.; Webb, G. I.; Ting, K. M.
Lazy Bayesian Rules: A Lazy Semi-Naive Bayesian Learning Technique Competitive to Boosting Decision Trees
Bratko, I.; Dzeroski, S. (Ed.): Proceedings of the Sixteenth International Conference on Machine Learning (ICML-99), pp. 493-502, Morgan Kaufmann, Bled, Slovenia, 1999.
@inproceedings{ZhengWebbTing99,
title = {Lazy Bayesian Rules: A Lazy Semi-Naive Bayesian Learning Technique Competitive to Boosting Decision Trees},
author = {Z. Zheng and G. I. Webb and K. M. Ting},
editor = {I. Bratko and S. Dzeroski},
year = {1999},
date = {1999-01-01},
booktitle = {Proceedings of the Sixteenth International Conference on Machine Learning (ICML-99)},
pages = {493-502},
publisher = {Morgan Kaufmann},
address = {Bled, Slovenia},
abstract = {LBR is a lazy semi-naive Bayesian classifier learning technique, designed to alleviate the attribute interdependence problem of naive Bayesian classification. To classify a test example, it creates a conjunctive rule that selects a most appropriate subset of training examples and induces a local naive Bayesian classifier using this subset. LBR can significantly improve the performance of the naive Bayesian classifier. A bias and variance analysis of LBR reveals that it significantly reduces the bias of naive Bayesian classification at a cost of a slight increase in variance. It is interesting to compare this lazy technique with boosting and bagging, two well-known state-of-the-art non-lazy learning techniques. Empirical comparison of LBR with boosting decision trees on discrete valued data shows that LBR has, on average, significantly lower variance and higher bias. As a result of the interaction of these effects, the average prediction error of LBR over a range of learning tasks is at a level directly comparable to boosting. LBR provides a very competitive discrete valued learning technique where error minimization is the primary concern. It is very efficient when a single classifier is to be applied to classify few cases, such as in a typical incremental learning scenario.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
LBR is a lazy semi-naive Bayesian classifier learning technique, designed to alleviate the attribute interdependence problem of naive Bayesian classification. To classify a test example, it creates a conjunctive rule that selects a most appropriate subset of training examples and induces a local naive Bayesian classifier using this subset. LBR can significantly improve the performance of the naive Bayesian classifier. A bias and variance analysis of LBR reveals that it significantly reduces the bias of naive Bayesian classification at a cost of a slight increase in variance. It is interesting to compare this lazy technique with boosting and bagging, two well-known state-of-the-art non-lazy learning techniques. Empirical comparison of LBR with boosting decision trees on discrete valued data shows that LBR has, on average, significantly lower variance and higher bias. As a result of the interaction of these effects, the average prediction error of LBR over a range of learning tasks is at a level directly comparable to boosting. LBR provides a very competitive discrete valued learning technique where error minimization is the primary concern. It is very efficient when a single classifier is to be applied to classify few cases, such as in a typical incremental learning scenario.
Webb, G. I.; Pazzani, M.
Adjusted Probability Naive Bayesian Induction
Antoniou, G.; Slaney, J. K. (Ed.): Lecture Notes in Computer Science Vol. 1502: Advanced Topics in Artificial Intelligence, Selected Papers from the Eleventh Australian Joint Conference on Artificial Intelligence (AI '98), pp. 285-295, Springer-Verlag, Brisbane, Australia, 1998.
@inproceedings{WebbPazzani98,
title = {Adjusted Probability Naive Bayesian Induction},
author = {G. I. Webb and M. Pazzani},
editor = {G. Antoniou and J. K. Slaney},
year = {1998},
date = {1998-01-01},
booktitle = {Lecture Notes in Computer Science Vol. 1502: Advanced Topics in Artificial Intelligence, Selected Papers from the Eleventh Australian Joint Conference on Artificial Intelligence (AI '98)},
pages = {285-295},
publisher = {Springer-Verlag},
address = {Brisbane, Australia},
abstract = {Naive Bayesian classifiers utilise a simple mathematical model for induction. While it is known that the assumptions on which this model is based are frequently violated, the predictive accuracy obtained in discriminate classification tasks is surprisingly competitive in comparison to more complex induction techniques. Adjusted probability naive Bayesian induction adds a simple extension to the naive Bayesian classifier. A numeric weight is inferred for each class. During discriminate classification, the naive Bayesian probability of a class is multiplied by its weight to obtain an adjusted value. The use of this adjusted value in place of the naive Bayesian probability is shown to significantly improve predictive accuracy.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Naive Bayesian classifiers utilise a simple mathematical model for induction. While it is known that the assumptions on which this model is based are frequently violated, the predictive accuracy obtained in discriminate classification tasks is surprisingly competitive in comparison to more complex induction techniques. Adjusted probability naive Bayesian induction adds a simple extension to the naive Bayesian classifier. A numeric weight is inferred for each class. During discriminate classification, the naive Bayesian probability of a class is multiplied by its weight to obtain an adjusted value. The use of this adjusted value in place of the naive Bayesian probability is shown to significantly improve predictive accuracy.