Complexity of classification problems (Q1369621)

Consider a finite set \(B\) of objects \(b\). Each object \(b \in B\) is identified with an integer vector \((x_1, x_2,\dots, x_n,f)\); here \(n\) is a natural number \((1\leq n<\infty)\); \(x_j\in \{0,1,\dots, g-1\}\), \(j=1,2,\dots, n\); \(f\in \{0,1,\dots, h-1\}\) and \(g,h\) are natural numbers, \(g\geq 2\), \(h\geq 2\). Assume that a probability distribution \(P\) is defined on the set \(B\), but this distribution is unknown to us. A calibration sample \(V\) is drawn from the set \(B\). Assume that some object has been drawn from the set \(B\) independently of the sample \(V\) according to the distribution \(P\), and only the values of the features \(x_1, x_2,\dots, x_n\) are known for this object. Given these values and the calibration sample \(V\), it is required to determine the criterion value \(f\). To analyze the complexity of such problems, we need to formalize certain basic concepts, such as class of problems, classification procedure, classification 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 problems and efficiency of optimization methods. The present article generalizes our results in Cybern. Syst. Anal. 31, No. 4, 543-554 (1995); translation from Kibern. Sist. Anal. 1995, No. 4, 76-89 (1995; see the preceding entry, Zbl 0902.62070), in two directions: 0-1 classification problems are replaced with integer problems, and classes of objects are assigned to certain weights that characterize their relative importance.