{'fraction_non_alphanumeric': 0.04250061774153694, 'fraction_numerical': 0.009191994069681245, 'mean_word_length': 4.238415739062905, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Boosting Learning Algorithm for Pattern Recognition and Beyond

This paper discusses recent developments for pattern recognition focusing on boosting approach in machine learning. The statistical properties such as Bayes risk consistency for several loss functions are discussed in a probabilistic framework. There are a number of loss functions proposed for different purposes and targets. A unified derivation is given by a generator function U which naturally defines entropy, divergence and loss function. The class of U-loss functions associates with the boosting learning algorithms for the loss minimization, which includes AdaBoost and LogitBoost as a twin generated from Kullback-Leibler divergence, and the (partial) area under the ROC curve. We expand boosting to unsupervised learning, typically density estimation employing U-loss function. Finally, a future perspective in machine learning is discussed. key words: AUC; boosting; entropy; divergence; ROC; U-loss function; density estimation


Introduction
The methodology for pattern recognition has been actively proposed and discussed in a field related with neural computation and machine learning rather than statistics in recent decades, and hence there are a vast number of new developments beyond standard discriminant analyses such as Fisher linear discriminant analysis and logistic regression, cf. [1]. In particular, boosting and support vector machine (SVM) both have got large popularity to break through conventional methods, see [2], [3]. Statistical considerations give reasonable understandings for the performance of these methods in the community of statistics. Presently boosting has been well established as in [4] where boosting is discussed as the approximation to additive modeling on the logistic scale using maximum Bernoulli likelihood.
In this paper we put stress on the characteristic such that the boosting is not simply a single method to directly construct a discriminant function, but a hyper-method to combine selected weak classifiers. In each iteration step the learning algorithm selects the best candidate in a given dictionary of weak classifiers to linearly combine the candidate and the discriminant function. Such an idea is creative and progressive in the research of pattern recognition which incorporates a rule of majority vote with effective weights. It is noted that the performance of boosting depends on the choice of dictionary in the sense that larger dictionary gives higher approximation for the Bayes rule associated with the underlying density function, but is apt to be over-learning. Thus we have to carefully investigate the trade-off in the choice of the dictionary. Boosting satisfies a great applicability for minimization of various loss functions. A class of U-loss functions is discussed with a close association with U-entropy and Udivergence [5], [6], where U is a generator function on the real line such as an exponential function. Any U-loss function can employ the idea of boosting with a simple change from AdaBoost. If U is monotone increasing and convex, then the classifier derived by the minimization of U-loss function is shown to satisfy Bayes risk consistency in a general probabilistic framework. It is discussed that a specific choice of U leads to the robustness for outlying in both the spaces of feature vectors and class labels [7]. Although it is not a convex function, the Heaviside function leads to an important objective function called the area under the ROC curve (AUC).
At the end, we discuss an extension of boosting for pattern recognition to other statistical analyses such as density estimation. In principle, we can define U-loss function in a situation where the probabilistic framework and the discriminant function are given, so that any statistical analyses are applicable for the boosting method. In this sense the kernel method is also applicable. There remain a lot of undeveloped areas for data analysis in machine learning. We will discuss such perspectives from the point of loss functions.

Boosting for Pattern Recognition
Statistical pattern recognition aims to conduct good prediction for a category of an observed variable based on a given empirical examples. This can be said to be a mathematical expression in which a human brain makes prediction for a future event based on his own experiences. In fact, the brain acquires prediction capability in a process of learning from several experiences accompanying the achievements of motor ability and language function. We need to take a careful attention to this characteristic in the discussion of the statistical pattern recognition, in particular to over-learning for the training data. The framework is given in a simple form composed of a feature vector x and a class label y, in which a mapping h of x into y is called a classifier, or classification machine. The objective is to build up the classifier h with good performance for the pattern recognition in the statistical sense.
A boosting method does not directly give any specific Copyright c 2011 The Institute of Electronics, Information and Communication Engineers proposal for a classifier, but gives a procedure combining several weak classifiers in a given set, say D = {h ω : ω ∈ Ω}, where Ω is a parameter space. The learning algorithm implements in a reasonable way a convex combination based on a training data of n tuple examples, say D = {(x 1 , y 1 ), · · · , (x n , y n )}, so that a strong classifier is integrated to outperform all the weak classifiers in the set. In this combination process we employ the training data many times to select weak classifiers, in which we can see the number of examples (x i , y i ) that a weak classifier h wrongly predicts, that is h(x i ) y i for all the iteration steps. A simple way of reweighting to the training data efficiently works to take a weighted majority vote of the sequence of weak classifiers. On the other hand, SVM is a batch-type learning algorithm to maximize the margin associated with D by the use of mathematical programming, which can sophisticatedly employ kernel functions to produce a linear decision boundary in the reproducing kernel Hilbert space. Thus SVM leads to an effective classifier associated with a higher-dimension space other than the original feature space.
There are various applications in pattern recognition since the first application to Fisher's iris data, in which a decision maker wants to predict a categorical variable, or phenotype from a given input variable, or feature variable. For example, the class label represents an endpoint in a context of risk analysis.

U-Boosting
For a training data set D = {(x 1 , y 1 ), · · · , (x n , y n )}, we discuss a leaning algorithm as follows. Consider a discriminant function F : X → R to construct a classifier h : x → y with the relation that h(x) = sgn F(x), where X is a feature space, sgn denotes the sign function. We prepare a dictionary of weak classifiers D = {h(x, ω) : ω ∈ Ω} which is assumed to be the negation-closed, that is, if h ∈ D, then −h ∈ D. For example, the class of all linear classifier D = {sgn l(x) : l ∈ L} with the class L of linear functions of x can be considered.
Let U : R → R be a convex and monotone increasing function. Then we define U-loss function for the discriminant function F by in which the expected loss is given by L U (F) = EU(−YF(X)), where E denotes the statistical expectation of the underlying distribution for D. Our proposal is to find where con(D) is the cone of D, that is, A variational argument leads to which implies the Bayes risk consistency such that On the other hand, the U-loss function has a normalized form defined by In this way we have two forms of loss functions as in (1) and (2). If U(t) = exp(t), then (1) is exp-loss, and (2) is log-loss In general U(t) = exp(t) generates the Kullback-Leibler divergence in which AdaBoost and LogitBoost are viewed as twin in this context. In a subsequent discussion we will consider the Uloss function for supervised learning.

U-Boost Algorithm
The learning algorithm for a sequential minimization of Uloss function in the convex hull of the dictionary D is as follows.
1. In the initial step we set 3. In the final, output a discriminant function as The main step 2 is sometimes changed to a gradient-type algorithm In particular, this change is recommended when the cost of joint optimization in step 2 is considerable. A overlearning of this algorithm to the data set D is reported when the dictionary D is unbalanced with D. In fact, after only a few step, the error rate becomes 0, and any further steps do not improve the performance. In such a situation it is better to fix a predetermined sequence of step lengths independent of D, see the early stopping rule in [8]. Hence if we write the sequence by α, then the algorithm selects only the best candidate as

Boosting AUC
The expected U-loss function L U (F) = EU(−YF(X)) is expressed using joint probability in the same way as error rate. It is very common and useful for measuring the accuracy of classification performance. However, in medical and biological sciences, the type I error and type II error must be treated differently. Suppose a classification problem for disease screening in which the prevalence rate is very low. In that case, classifying all subjects to be negative (non-diseased) leads to almost perfect classification based on U-loss or error rate, though it is not practical. In this context, the false positive rate (FPR) and true positive rate (TPR) are used in practical situations, and the classification performance is often measured by the area under the ROC curve (AUC). See the relationship between U-loss function and the AUC in the logistic-type context [9].

Area under the ROC Curve
For probability density function g − (x) and g + (x) for y ∈ {−1, +1}, the FPR and TPR are defined as where the subject is classified to be positive when F(x) > c, and to be negative when otherwise. Hence we have Then, the area under the ROC curve (AUC) is given as It is rewritten as where H(z) is the Heaviside function: H(z) = 1 if z ≥ 0 and 0 otherwise. Hence, the empirical AUC is given by where {x −1 , . . . , x −n − } and {x +1 , . . . , x +n + } are samples with sample size n − and n + for y = −1 and y = +1, respectively. Its probabilistic interpretation is given in [10] as In order to facilitate the maximization process, the standard normal distribution function is used in place of H(z) [9], or a sigmoid approximation for this purpose is also proposed in [11] and [12]. Here, we consider the former approximation: where H σ (z) = Φ (z/σ), with Φ being the standard normal distribution function.
Similarly to Eq. (3), the approximate AUC is given as The next theorem in [13] justifies the use of the approximate AUC in place of the AUC as follows.

Theorem 1:
Let where Λ(x) = g + (x)/g − (x) and m is a strictly increasing function. Then, Ψ(γ) is a strictly increasing function of γ ∈ R, and Theorem 1 can be extended into the justification of the use of the approximate pAUC [14]. See Theorem 2 for more details.

Objective Function
At first, we prepare a set of weak classifiers, D k , for each k-th component of x ∈ R p and combine the sets into among which we choose weak classifiers to construct F(x).
In this setting, F(x) can be decomposed componentially: Then, the objective function is given as where λ is a smoothing parameter and F (2) k (x k ) denotes the second-order difference of F k (x k ). The second-order difference is considered for B k , which is a set of quantiles for x k .
By a simple calculation, we have if λσ 2 = λ σ 2 . This implies that the maximization of AUC σ,λ (F) is equivalent to that of AUC 1,λσ 2 F σ . Therefore, we have From this consideration, we can fix σ = 1 without loss of generality, and redefine AUC λ (F) ≡ AUC 1,λ (F).
2. For t = 1, . . . , T a. Find the best weak classifier h t and calculate the coefficient α t as b. Update the discriminant function as 3. Finally, output the final discriminant function: If we have no prior information about the data, we set F 0 (x) = 0. In step 2.a, we search D for a h t which maximizes the first derivative of AUC λ (F) at the point F t−1 (x) + αh(x). This argument is similar to that of [3] and [7]. Next, we calculate the coefficient of h t (x) using the Newton-Raphson method, and add α t h t (x) to the previous discriminant function. We repeat this process T times and output the final discriminant function. Thus, the resultant discriminant function is an aggregation of h t (x)'s with weights α t 's.

Boosting pAUC
In medical practice, a part of the range of FPR or TPR is essential. For example, in disease screening, the targeted population consists mainly of healthy subjects. In that case, a very low FPR is required to avoid a large amount of unnecessary treatments. On the other hand, in the case where severe medical treatments such as biopsies or surgeries follow the diagnosis of subjects when being judged to be positive, TPR needs to be kept as high as possible. In this context, the partial area under the ROC curve is getting more useful than the AUC itself. The classification problems relating to the pAUC are discussed in several papers such as [14]- [16].

Partial Area under the ROC Curve
We consider a part of the AUC by limiting the value of FPR between α 1 and α 2 , which are determined by thresholds c 1 and c 2 , respectively: where 0 ≤ α 1 < α 2 ≤ 1 (c 2 < c 1 ). Usually, the values are set to be 0 and 0.1, respectively. However, it is also worth considering to take α 1 > 0 and choose α 2 − α 1 to be small enough, so that we essentially maximize TPR for fixed FPR. Then, the pAUC can be divided into a fan-shaped part and a rectangular part: Its probabilistic interpretation is offered by [17] as The empirical form is expressed as where α 1 and α 2 are empirical values that are the closest to α 1 and α 2 , respectively; where c 1 and c 2 are thresholds determined by α 1 and α 2 .
In the same way as Eq. (4), the approximate pAUC is given as where α 1 and α 2 are defined in (5). Similarly, the corresponding empirical pAUC is defined as Before discussing a boosting method for the pAUC, we give a theoretical justification of the use of the approximate pAUC in the following theorem [14].
Theorem 2: For a pair of fixed α 1 and α 2 , let where γ is a scalar, Λ(x) = g + (x)/g − (x) and m is a strictly increasing function. Then, Ψ(γ) is a strictly increasing function of γ, and As proved by [9] and [18], the likelihood ratio Λ(x) is the optimal discriminant function that maximizes the AUC as well as the pAUC. Theorem 2 suggests a weak version of the Bayes risk consistency in the limiting sense.

pAUCBoost Algorithm
The difference from AUCBoost algorithm is that the thresholds c 1 and c 2 should be calculated, and that they depend on a discriminant function F(x). Hence, the coefficient should be individually calculated for each weak classifier h, which is explicitly denoted by β(h) in the following algorithm.
1. Start with a discriminant function F 0 (x) = 0 and set each coefficient β 0 (h) of weak classifiers to be 1 or −1.
2. For t = 1, . . . , T a. Calculate the values of thresholds c 1 and c 2 for

Finally, output a final discriminant function
The dependency of the pAUC λ (F t−1 + β t (h)h, α 1 , α 2 ) on thresholds c 1 and c 2 makes it necessary to pick up the best pair of (β t (h t ), h t ) at the same time in step 2.c. Because of the dependency and the difficulty of getting the exact solution of β t (h t ), the one-step Newton-Raphson calculation is conducted in the boosting process. In this algorithm, the components x 1 , . . . , x p of x are combined componentially for maximizing the pAUC using natural cubic splines or decision stumps (single-level decision trees) in a dictionary D, according to the values of variables (continuous or discrete). See [14] for more details.

Boosting for Density Estimation
A lot of boosting methods for prediction or classification have been proposed so far. The first and typical one in machine learning community is AdaBoost [19] for the minimization of the exponential loss. Other boosting methods for various objective function such as likelihood, L 2loss, mixture of the exponential loss and naive loss, U-loss, AUC and pAUC [4], [5], [7], [13], [14], [20] have been considered and applied to real data analysis. However, the boosting methods for other purpose than prediction seem to have been paid little attention, see [21]- [23]. Recently, [24] has proposed a stagewise methods for density estimation based on L 2 loss and derived a non-asymptotic error bound. See [25] for further details. Then [26] extended the estimation method based on U-divergence and [27] modified it so that it can be applied in more general setting and with less computational cost.

U-Divergence
We employ the same generator function U to define the loss function for a density estimator. Here we redefine U as follows. Let U be a convex and monotone increasing function, and u be the first derivative. Then the conjugate convex function is given as By differentiating it with respect to t, we have where ξ is the inverse function of u. Then, for x ∈ R p , f (x) > 0 and g(x) > 0, the U-divergence is defined as It is rewritten as where Here, C U ( f, g) and H U ( f ) are U-cross entropy and Uentropy, respectively. From the relation that H U ( f ) = − Ξ( f (x))dx, we have D U ( f, g) ≥ 0. In the case that U(t) = exp(t), we have u(t) = exp(t) and ξ(t) = log(t), which leads to This is the Kullback-Leibler divergence. In the same way, if we consider Then u and ξ are given as This is the β-divergence [28], [29]. It becomes the Kullback-Leibler divergence when β → 0; it becomes L 2 norm when β = 1.

Loss Function for β-Divergence
For observations {x 1 , . . . , x n }, the loss function for Udivergence is given as From Eq. (6), the loss function for β-divergence is given as This loss function is known to be robust to outliers. See [30] for the application to ICA, and [31] for that to PCA mixture.

Boosting Algorithm
For a dictionary of density function D, the dictionary used in the boosting algorithm is defined as where ξ(t) = (t β − 1)/β. Then, we consider the following mixture model: based on which we construct the density estimatorf . For a positive numerical sequence π 1 , . . . , π T , the stagewise algorithm forf is proposed by [26] as follows.
1. Choose f 0 ∈ D so that where > 0 is an approximation bound. 2. For t = 1, . . . , T , f t is given as where, φ t is chosen such that 3. Finally, we havef = f T ∈ M.
The numerical performance of this method is illustrated and the non-asymptotic error bound is derived in [26].

Discussion and Future Problems
We overview a unified perspective associated with U-loss function. In fact, any generator function U leads to a cross/diagonal entropy and divergence, in which U-cross entropy easily yields U-loss function by plugging the empirical distribution because this is a linear functional with respect to the data distribution. In this framework U model and U estimator are connected with a dualistic structure in the sense of information geometry, see [32].
Hence U-loss function naturally utilizes boosting learning by the use of prescribed set of weak classifiers, called dictionary, while U-loss function utilizes kernel methods for linear learning in the reproducing kernel Hilbert space. This tells us that such boosting and kernel methods are applicable for any loss functions such as the AUC, which is not convex but still applicable for boosting method as discussed here. In some applications we can build boosting learning algorithms for mixture model and principal/independent component analysis. AdaBoost and SVM have been established as the most popular methods in pattern recognition, however, we remark that what they have done by specific choice of the loss function is not so essential. We have not explored yet the performance of integrating local learning by specific choice of the loss function here. In the near future, it may be possible that the surprising performance is implemented for data learning in machine learning.