logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

An efficient Bayes error rate estimation method

delete2025-04-11
delete0
PRE
AI
Q
Qingqiang Chen
F
Fuyuan Cao *
Y
Ying Xing
J
Jiye Liang
DOI：10.1007/s10994-025-06761-wdelete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
The Bayes error rate is the lowest error rate that any classifier can achieve, and estimating the Bayes error rate is a generally acknowledged difficult problem in machine learning. Recently, a consistent estimator of the Bayes error rate has been proposed, and the method to calculate this estimator is called BN-BER. Although the consistency of the estimator has been proven, whether the estimator is unbiased remains to be analyzed, because consistency and unbiasedness are two important properties to measure the effectiveness of an estimator. Besides, the time and space complexity of BN-BER are high, resulting in high runnning costs for large-scale data. To address the above issues, we first prove the unbiasedness of the estimator. Subsequently, addressing the high time and space complexity of BN-BER, we propose an approach for estimating Bayes error rates based on hierarchical k-means clustering and approximate k-nearest neighbor algorithm. Through analysis, we found that the time and space complexity of the proposed method is O(n(log2n)2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n(\log _{2}n)<^>2)$$\end{document}, whereas the time and space complexity of the BN-BER method is O(n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>2)$$\end{document}. The effectiveness and efficiency of the proposed method are verified on a large number of synthetic datasets and benchmark datasets.
Keywords:
Classification
Big data
Bayes error rate
Model evaluation

Journal

Machine Learning cover
Machine Learning
IF:
2.9
Papers:
2.6K
Citations:
3.4W

Organization

No organization information available