# Understanding Query Combination Behavior in Exploratory Searches
## 5 Automatic QCB Classification
### Classification for QCB Types  
After identifying the features, we first described an automatic QCB classification model, and then we described our experimental setup and the results for the classification experiments. We conducted experiments using the QCB sessions described, which had approximately 6000 QCB sessions and 23,871 queries. These QCB sessions were manually classified and labeled. To ensure the validity of features in each QCB session, we began by performing standard text normalization where we removed leading spaces, trailing spaces, and stop words. We used 10-fold cross-validation for all experiments and we trained our classifier to classify QCB based on the gradient boosting tree (GBT) model [54, 55]. We adopted the GBT model because it can handle heterogeneous features and has a good prediction power [48]. We trained each QCB pattern as one class, and the GBT algorithm is summarized in Algorithm 1. ```
1: Initialize \(F_{0}(x)=arg\min\sum_{a=1}^{N}L(y_{i},a)\)
2:for\(m=1,2,\ldots,M\)do
3:for\(i=1,2,\ldots,M\)do
4:\(\tilde{y}_{im}=-\left[\frac{\Delta(y_{i}F(x_{i}))}{\Delta(y_{i})}\right]_{F(x )=F_{m-1}(x)}\)
5:endfor
6:\(a_{m}=arg\min_{a}\sum_{i=1}^{N}(\tilde{y}_{im}-T(x_{i},a))^{2}\)
7:\(\mu_{m}=arg\min_{y}\sum_{i=1}^{N}L(y_{i},F_{m-1}(x_{i})+\mu T(x_{i},a))\)
8:\(F_{m}(x)=F_{m-1}(x)+\sum_{m=1}^{M}\mu_{m}T(S,a_{m})\)
9:endfor
10:\(F(x)=\sum_{m=1}^{M}\mu_{m}T(S,a_{m})\)
```  
**Algorithm 1** Gradient boosting tree (GBT)  
The input of Algorithm 1 is the training data set \(S=\{(x_{1},y_{1}),\ (x_{2},y_{1}),\ldots,(x_{N},y_{N})\}\), and the sample size is N. \(x_{i}\in x\subset R^{n}\), where \(x\) is the feature set we proposed in Table 3. \(y_{i}\in y\subset R\), where y is the QCB pattern set. The output is the optimal mapping function \(F\) (\(x\)), which minimizes the loss function \(L(y,F(x))\) by ensemble weak learners (CATR decision tree). The GBT model combines M individual CATR decision trees \(T(S,a_{1}),\ T(S,a_{2}),\ldots,\)\(T(S,a_{M})\), where \(T(S,a_{i})\) is the ith CATR decision tree. Therefore, the function F(x) can be expressed as Equation (2), as follows:  
\[F(x)=\sum_{m=1}^{M}\mu_{m}T(S,a_{m}) \tag{2}\]  
For the mth CATR decision tree \(T(S,a_{m})\), \(\mu_{m}\) is the weight for this classifier, and \(a_{m}\) determines the structure of the tree. The parameters \(\mu_{m}\) and \(a_{m}\) are determined iteratively, which can ensure that the loss function \(L(y,F(x))\) is minimized. \(\mu_{m}\) and \(a_{m}\) can be determined as Equation (3), as follows:  
\[(\mu_{m},\ a_{m})=arg\min_{\mu,\ a}\sum_{i=1}^{N}L(y_{i},F_{m-1}(x_{i})+\mu T( x_{i},a)) \tag{3}\]  
The GBT algorithm initialized \(F_{0}(x)=arg\min_{a}\sum_{i=1}^{N}L(y_{i},a)\) at the beginning of Algorithm 1; however, it is difficult to directly solve \(\mu_{m}\) and \(a_{m}\). Therefore, we estimate \(\mu_{m}\) and \(a_{m}\) with a simple two-step procedure [56, 57]. The GBT algorithm first estimates \(a_{m}\) as Equation (4), as follows:  
\[a_{m}=arg\min_{a}\sum_{i=1}^{N}(\tilde{y}_{im}-T(x_{i},a))^{2} \tag{4}\]  
After the \(a_{m}\) estimated, the output of the CATR decision tree is constant, so that the weight \(\mu_{m}\) can be straightforwardly estimated using a line search on the loss function [58, 59]. To study the performances of our approach, we also experimented with other classifiers, such as multiple additive regression trees (MART) [50], SVM, and C4.5 [60]. For every classifier, we use the area under the curve (AUC) of ROC, accuracy, and the F1 score to evaluate these models' performance. Table 4 presents the results of the QCB pattern classification experiment. Experimental results show that the GBT model yielded better performances than the other baseline classifiers. From the results, we can see that, using the features, the gradient boosting tree can effectively classify QCB sessions. The AUC reaches 79.23 in the QCB classification. Table 5 shows the classification power of GBT for each QCB pattern.