Efficiency of Bayesian classification procedure (Q1918760)

Consider the following problem. Given is a set \(B\) of objects \(b\). Each objects \(b\in B\) is identified by a 0-1 vector \((x_1, x_2,\dots, x_n,f)\), where \(n\) is a natural number. Assume that a probability distribution \(P\) is defined on the set \(B\), but this distribution is not known to us. A sample \(V\) is drawn from the set \(B\) (the structure of the sample and the sampling procedure are described later). In addition, some object from the set \(B\) is obtained independently of the sample \(V\) according to the distribution \(P\), and only the feature values \(x_1, x_2,\dots x_n\) are known. Given these feature values and the learning (calibration) sample \(V\), it is required to determine the value of the objective criterion \(f\). In order to study the efficiency of the Bayesian approach to the solution of this problem and also the complexity of similar problems, we have to formalize certain concepts, such as class of problems, classification procedure, classification procedure error, etc. Here we apply the approach developed by \textit{A. S. Nemirovskij} and \textit{D. B. Yudin} [Complexity of problems and efficiency of optimization methods. (1979; Zbl 0501.90061); an English translation appeared 1983] for analyzing complexity of classes of problems and efficiency of optimization methods.