The structured output framework provides a helpful tool for learning to rank problems. In this paper, we propose a structured output approach which regards rankings as latent variables. Our approach addresses the complex optimization of Mean Average Precision (MAP) ranking metric. We provide an inference procedure to find the max-violating ranking based on the decomposition of the corresponding loss. The results of our experiments on WikiQA and TREC13 datasets show that our reranking based on structured prediction is a promising research direction. The current state-of-the-art learning approaches for answer sentence reranking in question answering (QA) are mostly based on learning pairwise ranking signals or simple binary classification (rel-evant versus irrelevant labels). Intuitively, global information over a rank should improve the ranker accuracy. Thus, there have been promising attempts to learn global ranking functions which encompass the signals of all the candidates for a given query (Chapelle et al., 2007; Weston and Blitzer, 2012; Le et al., 2018). These works employ the structured output learning framework to represent a ranking as a structured object, with respect to which it is possible to directly optimize a ranking measure. Direct optimization of the target ranking measures is affordable when they are factorizable, e.g., the structural SVM of Chapelle et al. (2007) makes use of the factorization properties of the Normalized Discounted Cumulative Gain (NDCG) ranking score. In contrast, MAP is rather complex making its treatment harder. Yue et al. (2007)  Most of this work was carried out before joining Amazon. could still find an exact solution to the hinge-loss relaxation of Average Precision (AP) for the structural SVM approach. It is found for the particular case of a combined feature mapping of inputs and structured outputs. Such a mapping accounts for respective orderings of the pairs of candidate items, where one item is relevant and the other is not, without explicitly encoding the order of all the items in the rank. Encoding such order (Chapelle et al., 2007; Weston and Blitzer, 2012), i.e., adding yet more complexity to the structural feature space, might lead to intractability of the previous exact max-violating inference with respect to MAP. Furthermore, the feature representation of the gold standard rankings, which could be many for a given candidate list of items, is not unique anymore. In this work, we study the effect of using structured ranking representations (Chapelle et al., 2007) within the large-margin structured prediction framework versus direct MAP optimization on the most representative task of QA, i.e., passage reranking. To make two ends meet, we have to tackle the above two issues, i.e., i) intractability of the max-violating inference with respect to MAP, and ii) multiplicity of the ground truths. Regarding the latter, it should be noted that different rankings can correspond to optimal performance, thus, Chapelle et al. (2007) select one among all possible correct rankings at random to build the ground truth for training. Weston and Blitzer (2012) bypass the necessity of comparison to a complete ranking during training and sample the candidate pairs. In this work, we show how this issue can be seamlessly circumvent using the latent structured prediction formulation. For optimizing MAP, we derive a strict decomposition of the loss corresponding to AP and propose an approximate method for inference of the max-violating constraint with respect to it. More specifically, we provide two structured output approaches optimizing the MAP metric based on Latent Structured Perceptron (LSP) (Sun et al., 2009; Fernandes et al., 2014) and Latent Structural SVM (LSSVM) (Yu and Joachims, 2009) algorithms. We compare LSP and LSSVM using our MAP optimization strategy on WikiQA (Yang et al., 2015) and TREC13 (Wang et al., 2007) datasets against an SVM classifier and SVM map  the structural approach of Yue et al. (2007). All the models use state-of-the-art traditional feature vectors for the task. Our experiments on WikiQA dataset show a large improvement of our structural approaches over the SVM baseline, i.e., more than 7 absolute points in MAP, MRR and Precision@1. However, we acknowledge the fact that neural models can produce better representations, which can lead to a superior performance. Thus, to collocate our results in a more general setting, we also carried out experiments using the embeddings of questions and passages, produced by an accurate Convolutional Neural Network (CNN) for passage reranking. In this setting, the structured output models approach the state of the art, confirming the positive impact of our models, which may also be used to train neural networks. The work related to our approach can be divided in two research areas: (i) structured prediction for reranking problems and (ii) passage reranking in question answering systems. Structured prediction Seminal work on large-margin structured prediction is by Tsochantaridis et al. (2004), which enables the optimization of multivariate loss functions, exploiting structural dependencies within complex output variables. Chapelle et al. (2007) devise an approach based on the structural SVM, which enables direct optimization of the NDCG ranking measure. Le et al. (2018) facilitate the optimization of a range of ranking measures, within a unified structured output formulation. However, they do not provide any solution for MAP. Weston and Blitzer (2012) optimize a retrieval AUC loss, which decomposes into pairwise decision variables. The approach most similar to ours is SVM map by Yue et al. (2007), who provide a structural solution for optimizing MAP. They find exactly the max-violating ranking structure with respect to AP within the structural hinge loss formulation. This is done for the case when a ranking is represented by aggregating pairwise outputs between all the relevant and all the irrelevant items in the rank. Our approach is an alternative to this technique, providing an approximate max-violating inference with respect to AP for a more general case of the ranking represenation. Passage Reranking Most representative pre-neural networks work for answer selec-tion/passage reranking is from Wang et al. (2007), who used quasi-synchronous grammar to model relations between a question and a candidate answer with syntactic transformations. Heilman and Smith (2010) and Wang and Manning (2010) applied Tree Edit Distance (TED) to learn the match between question and passage. Yao et al. (2013) applied linear chain CRFs with features derived from TED. Yih et al. (2013) used lexical semantics to build a word-alignment model. Most recently, Deep Neural Networks (DNNs) have shown to be more competitive. DNN can learn relational patterns between a question (Q) and its passage (P) in a variety of ways, e.g., (i) by using a Q-to-P transformation matrix and simple Q-to-P similarity features (Yu et al., 2014; Severyn and Moschitti, 2015), (ii) by relying on RNN and LSTM architectures (Wang and Nyberg, 2015; Shen et al., 2017), (iii) by employing attention components (Yin et al., 2016; Shen et al., 2017; Wang et al., 2016a), (iv) by decomposing input into similarity and dissimilarity matches (Wang et al., 2016b) or (v) by comparing-aggregating matching results (Wang and Jiang, 2017; Bian et al., 2017). Since our baselines, SVM and SVM map , as well as our proposed models, LSP and LSSVM, do not apply such transformations, they may perform lower than the state of the art. Thus, we will use the embedding vectors generated by a CNN to show that they can achieve the state-of-the-art accuracy. In this section, we provide the task formulation with an introduction of structured prediction algorithms. We have training examples of the form { ( x i , y i ) } where x i = ( q i , D i ) , q i is a query, D i = { d ji } N i j =1 is a list of candidate items corresponding to q i and N i is the number of candidates. y i = { y ji : y ji  { 0 , 1 }} N i j =1 is a vector of gold item labels, label y ji corresponding to item d ji , taking value of 1 for relevant (good or positive) items and 0  for irrelevant (bad or negative). The task is to learn to predict, for each example x i , a ranking of its items r ( x i ) = r ( q i , D i ) , such that the relevant items, d ji with gold labels y ji = 1 , are always at top positions in r ( q i , D i ) . Finally, r ( x i ) = { r j } N i j =1 is a permutation of D i . In the following, we omit the example index i for simplification of the notation. Generally, structured output approaches aim at linking structured input and output patterns. More formally, in a linear case, such algorithms learn a scoring function f : X  Y  R , f ( x , y ) = w  ( x , y ) , where ( x , y ) is a combined feature mapping of input variables X and output variables Y . The predicted structure is derived as  y = argmax y  Y f ( x , y ) . Online structured prediction approaches, e.g., the structured perceptron by Collins (2002), are based on gradient descent updates of the model on the current predicted structure y against the correct structure y  : w  w + ( x , y  )  ( x , y ) . The large-margin perceptron variants augment the inference with the structural loss (Fernandes and Brefeld, 2011):  y = argmax y  Y f ( x , y ) + ( y  , y ) . When exhaustive search over Y is impossible, the problem can still be solved if the loss  and the scoring function f ( x , y ) are decomposable over the subparts of the structure y and there exists an efficient procedure for finding the argmax using such a decomposition. The structured prediction framework for ranking (Chapelle et al., 2007; Le et al., 2018) considers a joint feature representation of an input example x together with an output ranking r : ( x , r ) = ( q, D, r ) , which factorizes over the individual feature representations of items with respect to the query, weighted relatively to the item positions j in the rank: The typically used weighting schema, v , implies non-increasing weights associated with the positions j : v 1  v 2  ...  v N  0 , where the importance decreases gradually from the top to the bottom of the ranking. Inferring a ranking corresponding to a linear model w , i.e., finding argmax r  R ( x ) w  ( x , r ) (2) among all possible rankings, R ( x ) = R ( q, D ) , simply reduces to ordering the items by scores w   ( q, d ) , since v j are fixed. As the correct ranking r  for an example x is often not unique, Chapelle et al. (2007) select one of the correct rankings at random as a gold label during training. This evidently biases the training towards such ground truths. The above problem can be alleviated using a latent structured prediction framework. We describe now the general idea of latent variables, and after that we introduce our approach, in which, we implement this idea for ranking tasks. Latent variables h are auxiliary structures which are not fully observed in the training data (Yu and Joachims, 2009). The training examples are extended with h  ( x , y , h ) , and the learning is shifted to the space H of latent output structures h . Normally, each h corresponds to one y , while the opposite is not the case. The problem of multiplicity of the ground truths h is overcome by finding the best h explaining the gold y  : h  = argmax h  H ( x , y  ) w  ( x , h ) , (3) using the current model weights w at each iteration of the training, and h  used as gold labels. In the following, we describe the two classical steps in structured prediction, i.e., learning and inference. Regarding inference, we show our new approximation of MAP. We deal with a non fully observed case as the ground truth ranking labels r we intend to learn are not given in the input data. The case suits perfectly the latent structural formulation (Sec. 3.4), where r can be regarded as latent variables h . Consider the following latent structural large-margin objective (Yu and Joachims, 2009), in terms of the structured ranking variables: min w (cid:2) 1 2 || w || 2 + C n (cid:88) i =1 max r  R ( x i ) [( y i , r )+ + w  ( x i , r )]  C n (cid:88) i =1 max r  R ( x i ,y i ) w  ( x i , r ) (cid:3) , (4) in which the upper bound on the training loss  involves (i) finding the max-violating ranking structure,  r i , over the set R ( x i ) of all possible rankings for the example x i , under the first max , and (ii) the current ground truth ranking structure, r  i , over the set R ( x i , y i ) of all rankings that comply with the gold label y i , under the second max . We adapt the loss-augmented LSP algorithm (Fernandes and Brefeld, 2011) for ranking. LSP is essentially a gradient descent operated on the objective in Eq. 4 with a gradient taken with respect to the example variable. The pseudocode of our adaptation of the algorithm is shown in Alg. 1. Iterating over the training examples ( x i , y i ) , the algorithm, for each example, first finds the max-violating  r i with respect to a ranking loss ( y i , r ) , over the set R ( x i ) for the example x i (Line 5). can represent any arbitrary ranking loss. In this work, we instantiate  with the loss corresponding to the MAP ranking metric. Sec. 4.2 describes the procedure we use here for the max-violating inference with respect to it. If the max-violating ranking  r i is erroneous (Line 6), the algorithm updates the model w . In Line 7, the current ground truth ranking structure  the best correct r  i corresponding to the current model weights w t  is found. The search here is restricted to the set R ( x i , y i ) of all correct rankings of the example x i , i.e., those at which good items take top positions and bad  bottom positions. Thus, the operation is reduced to simple ordering of the good and bad items (separately) by weights, and putting the former to the top, and the latter  to the bottom of the resulting ranking. This step corresponds exactly to imputing latent variables, described by Eq. 3, in the general latent formulation. In Line 8, we update the weights w using the structural feature representations (defined by Eq. 1) of the two ranking outputs, the current ground truth r  i and the max-violating  r i . Likewise, we adapt the Latent Structural SVM (LSSVM) algorithm (Yu and Joachims, 2009) for ranking. We employ also LSSVM in our experiments for its generalization guarantees. The only minor difference from the LSP adaptation is that, in the LSSVM adaptation, we consider only the top items in the joint feature representation in Eq. 1, i.e., ( x , r ) = P (cid:88) j =1 v j  ( q, r j ) , where P is the number of good/positive items in the candidate list D of the example x . This is relevant only at the training phase and only for the updates of the model; for the max-violating inference, still all the items at all N positions participate. By doing so, we help LSSVM to keep the balance between positive and negative items. The test phase inference (respective to Eq. 2), for both LSP and LSSVM, consists only in ordering of all the items by their weight with respect to the model. Weston and Blitzer (2012) adopt the same structural feature representation of Eq. 1 for ranking, however, in the latent embedding space. They do online SGD updates in correspondence to the positive-negative item pairs, and not on the whole rank, which relates to the way we proceed with LSSVM. In their case, this is due to the impossibility of the global inference (their model is also augmented with the structural component describing item-item interactions) and the scale of the task (they do ranking for recommendation domain). However, they perform a cascade-like inference of the rank which is scattered over the iterations. Our target is to optimize the MAP ranking metric. Thus, in training, we intend to minimize the following loss on structural examples which is the inverse of the average precision (AP):  ap ( y, r ) = 1  AP ( y, r ) . AP is a global measure, non-decomposable in a strict sense over the position variables, so that to enable iterative exact inference. Here, we propose a method for approximate inference with respect to  ap , which is efficient and enables exact local search. Let us denote by P = |{ d | y ( d ) = 1 }| the number of good/positive items in the candidate list D , and by I + j = I [ y ( r j )=1] and I  j = I [ y ( r j ) (cid:54) =1] the indicator functions that the item at position j in r is good and not good (positive and negative), respectively. Then, AP ( y, r ) = 1 PN (cid:88) j =1 1 j I + j j (cid:88) k =1 I + k . We rewrite the AP formula as follows: AP ( y, r ) = 1 PN (cid:88) j =1 1 j I + j ( j  1 (cid:88) k =1 I + k + I + j ) = 1 PN (cid:88) j =1 1 j I + j ( j  1 (cid:88) k =1 I + k + 1) . Here, I + j inside the parentheses becomes 1 in the right-hand side because I + j  I + j = I + j . Then,  ap ( y, r ) = 1  1 PN (cid:88) j =1 1 j I + j ( j  1 (cid:88) k =1 I + k + 1) = 1 P ( P  N (cid:88) j =1 1 j I + j ( j  1 (cid:88) k =1 I + k + 1)) = 1 PN (cid:88) j =1 1 j I + j ( j  1  j  1 (cid:88) k =1 I + k ) = 1 PN (cid:88) j =1 1 j I + j j  1 (cid:88) k =1 (1  I + k ) = 1 PN (cid:88) j =1 I + j j j  1 (cid:88) k =1 I  k = 1 PN  1 (cid:88) j =1 I  j N (cid:88) k = j +1 I + k k . (5) According to the last line of Eq. We can have a strict decomposition of  ap over the negative items. PN (cid:88) k = j +1 k k over all positions j with negative items (those activating I  j ) except for the last position N . Note that I  j l j ( y, r ) gives the loss at position j considering the correct items below position j in the ranking. Therefore, we can use it for a bottom-up (max-violating) inference procedure, which first finds the best candidate item to be put at the lowest position of the rank and proceeds fill-ing the positions in the ascending order. Specifically, we start with the last N th position of the rank and put there the minimum weighted item:  r N = argmin d  D v N w   ( q, d ) . According to the decomposition in Eq. 5, loss is always 0 at position N . At each of the following steps j ,  r N  j = = argmin d  D \{  r N  k } j  1 k =0 v N  j w   ( q, d )+ I  N  j l N  j ( y,  r ) . (7) Note that the loss part, I  N  j l N  j ( y,  r ) , in the above formula will be invariant for all the negative items remained in the candidate list, as well as it is for all the positive ones (equal to 0). Thus,  r N  j is essentially the argmin taken over only two candidate items from D \{  r N  k } j  1 k =0 : one is the positive item with the minimal weight w   ( q, d ) , and the other, respectively, is the minimal weighted negative one. It is sufficient then to sort independently the positive and the negative items, in the beginning of the whole procedure, in the increasing order of their weights w   ( q, d ) . Argmin's in equations 6 and 7 are then to be taken over the first items of the two sorted lists, which have not been selected at previous steps. This goes in line with the observation of Yue et al. (2007), that the max-violating ranking output  r is an interleaving of such two sorted lists, which turns true also for our choice of the structural joint feature representation ( x , r ) in Eq. 1. However, the exact algorithm for max-violating inference of Yue et al. (2007) cannot be applied in our case, since our  , due to distinctive contributions of items at different rank positions scaled with v j weights, does not satisfy its conditions for an arbitrary choice of v j . Since, in our loss decomposition, the position-wise components are not independent of the decisions for the other positions, using a greedy procedure does not find a global optimum, but finds a local optimum with respect to the loss exactly. Namely, an item chosen at each step is optimal with respect to the partial rank constructed at the previous steps of the inference procedure. Regarding the running time complexity of our greedy inference procedure, it is bounded by the complexity of the sort operation, O ( N log N ) , for the candidate lists of size N . In comparison, the worst case complexity of the exact inference in SVM map by Yue et al. (2007) is O ( N 2 ) . In several cases, as shown by our experiments, doing inexact inference produces also higher MAP values compared to SVM map . In our experiments, we compare the proposed structural ranking approach with the classification and structural baselines. WikiQA We use only examples with at least one correct and at least one incorrect answer candidate (Yang et al., 2015) both for training and evaluation. This corresponds to 857 examples for training from train set, 237  for testing from test, and 122  for validation from development (dev.) set. TREC13 We apply the same evaluation strategy as above on TREC13 dataset (Wang et al., 2007), however, for training, we limit to 10 the number of answer candidates for each question. This gives us 970 training examples, 65 examples for validation, and 68 test examples. We implement our structural ranking approach described in Sec. 3.3 using both LSP and LSSVM 2 algorithms, denoting the resulting models LSP-AP and LSSVM-AP, respectively. We compare the models to an SVM baseline using the same feature set for the pairs, ( q, d i ) , and a polynomial kernel. We consider also a couple of structural baselines: (i) the standard LSP model (Sun et al., 2009), without loss-augmented inference, which we use in order to explore the impact of optimizing the target evaluation measure. This model still follows Alg. 1, however, the difference is that instead of finding the max-violating  r i in 2 www.cs.cornell.edu/cnyu/latentssvm/ Line 5, it finds the following max-scoring:  r i  argmax r  R ( x i ) w t  ( x i , r ) . And another structural baseline is (ii) SVM map 3 (Yue et al., 2007)  a structural SVM approach affording exact max-violating inference with respect to AP. Features In our study, we use two feature settings: (i) simple textual similarity features  the setting by Barron-Cedeno et al. (2016), i.e., co-sine similarity over the text pair, the similarity based on the PTK score , longest common sub-string/subsequence measure , Jaccard similarity , word containment measure , greedy string tiling , ESA similarity based on Explicit Semantic Analysis (ESA), and (ii) powerful features coming from the embeddings trained with the state-of-the-art neural networks (Tymoshenko et al., 2017). Parametrization We use the following weighting schema for the ranking structures: v j = 1 j , in LSP, LSP-AP, and LSSVM-AP. LSP-AP requires specifying a loss scaling parameter C . In LSSVM and SVM map , C is the standard trade-off between regularization and training error. In all the three models, we select C on dev. set from the values { 1 , 10 , 100 , 1000 , 2000 , 5000 } . The max number of epochs, T , is set to 100 , for both LSP and LSP-AP. We apply weight averaging in the LSP models. We derive the best number, T best , with respect to the MAP score on dev. set. The baseline SVM is trained with polynomial kernels of degree 3 . Cross-validation On TREC13, which has a very small test set we apply cross-validation. On WikiQA, we obtain results on the official test set as well as applying cross-validation. We employ disjoint cross-validation as in Tymoshenko et al. (2017). For each approach, we train 5 models on the training set following the traditional 5-fold cross-validation strategy. We split dev. and test sets in 5 subsets each, and use i th dev. subset to tune the parameters of the models trained on the i th fold, and i th test subset  to test them. We report the results averaged over 5 test subsets. We borrowed the CNN embeddings of questions and answer passages produced by the neural model for passage reranking of Tymoshenko et al. (2017); Severyn and Moschitti (2015) 4 . The neural model by Tymoshenko et al. (2017) includes (i) two sentence encoders that map input questions q i and answer passages d ji into fixed size m -dimensional vectors  ( q i ) and  ( d ji ) using a convolutional operation followed by a max pooling layer, and (ii) a feed forward neural network that computes the similarity between the two sentences in the input. The sentence vectors of a question and a passage,  ( q i ) and  ( d ji ) , are concatenated together and given in input, at stage (ii), to a standard NN architechture, constituted by a nonlinear hidden layer and a sigmoid output layer, which optimizes binary cross-entropy loss. Note that we use exactly the concatenated question-passage sentence vectors (CNN embeddings) from stage (i) of the above model as features in SVM and the structured output models:  ( q, d ) = [  ( q ) ,  ( d )] . Evaluation metrics We report Mean Average Precision (MAP), Mean Reciprocal Rank (MRR) and Prec@1 (P@1). We first report the results using standard similarity features in all of our models. Then, we show the outcome of our models when fed with embeddings produced by the CNN. to SVM, LSP, and SVM map models on WikiQA dataset. LSSVM-AP and LSP-AP are better than the SVM classifier baseline by roughly 8 and 10 points, respectively, in terms of MAP metric on the test set. It should be noted that SVM uses kernels, while LSSVM and LSP are simple linear models. Moreover, for SVM, we also had to limit the number of candidates to 10 for each query to make the positive/negative example rate more balanced. The baseline LSP model (without augmented loss optimization) performs surprisingly well in this setting. It lacks only 0 . 15 of a MAP point on test set as compared to the highest scoring LSP-AP model. However, as LSP does not optimize the ranking measure directly, it may result unstable. We verified this hypothesis by exploring the performance of the two LSP models (with our loss and without) on dev. set, plotting the learning curves over the training epochs, T . Fig. 1 shows that the LSP-AP curve is distinctly superior to that of LSP only in the beginning of training, before epoch 17 . We further verify this issue in cross-validation experiments in Sec. 5.2.3. LSSVM-AP outperforms the structural baseline SVM map . The latter targets direct optimization of MAP, and it clearly outperforms the SVM classifier. However, it is worse than the standard perceptron model, LSP, which does not optimize MAP. This suggests a higher appropriateness of the structural feature representation for rankings in Eq. 1. Indeed, it encodes the real positioning of items within a ranking (using positional weights v i ), compared to that used by SVM map , agnostic to it and considering only pairwise relevant/irrelevant relative placements among the items. Finally, in the last lines of Dev. and Test subparts of Tab. 1, we report the results of the models denoted with  . In these model variants, we perform exact search for the max-violating ranking  r with respect to  AP over the structural hypothesis space R ( x ) , e.g., in Line 5 of Alg. 1, instead of our approximate inference procedure in Sec. 4.2. In the current setting, exhaustive search over all possible rankings is reduced to an inference procedure, which inspects all interleavings of the two sorted lists, of positive and negative items, as pointed out in Sec. 4.2. In addition to the sorting complexity, this operation needs to traverse through a subset R (cid:48) of ranking structures r , R (cid:48)  R ( x ) , where | R (cid:48) | is estimated by the binomial co-efficient (cid:0) NN  P (cid:1) , which, for fixed P , grows poly-nomially as O ( NP ) . Recall that N is a total number of items in the candidate list D , among which P items are positive. In the context of WikiQA dataset, this is affordable, since the candidate lists D i of the training examples are relatively short. This way, LSSVM-AP  adds around 1.3 of a MAP point to its result using our approximate inference. LSP-AP  's best number of epochs on dev., T best , gives a nearly identical result on the test set in terms of MAP. However, its scores are lower compared to those of LSP-AP. Fig. 1 illustrates a clear advantage of the direct optimization of AP using exact inference, which results in the best curve on dev. for LSP-AP  , stabilizing to its highest values on the interval between epochs 55 and 85 . Still such a level of accuracy is nearly reachable by LSP-AP, although actually achieved at a very narrow interval (see the spike around epoch 5 ), while LSP's curve lies almost always lower. In future, we would like to study the impact of the loss approximation onto the convergence speed of the structural algorithms. The LSP models in the current setting do not reveal a clear correlation between dev. and test results in Tab. 1, which might (i) signal of insuffi-cient generalization power of LSP, and (ii) suggest that the effect of direct loss optimization can be reached by carefully selecting the epoch's number parameter, T , in the considered feature space. The test set results of LSSVM in terms of MAP instead conform appropriately to the optimized loss function (using approximate versus exact inference) in the large-margin objective in Eq. 4. This should be due to a better generalization capability of the DEV . In these experiments, we used the CNN embeddings, described in Sec. 5.1.2, as features in all of the models. This setting allows us to examine the performance of the models in a more complex and richer feature space, at the level of the state-of-the-art performance. It can also be seen as a coarse way to neuralize the structural ranking approaches. The results of all the models are shown in Tab. 2. As before, we note the relative inconsistency of the performance of the LSP models between dev. and test sets. The non-loss-augmented structured perceptron, LSP, is the weakest of the models on dev. set, while on test it is better than LSP-AP by around 1 point in terms of MAP. It only slightly outperforms now the baseline SVM, which benefited greatly from using the embeddings. Recall, however, that the baseline SVM is trained with kernels. LSP-AP  , reaching considerably higher scores than the rest of the models, including CNN, on dev., is better than LSP by no more than 0.5 of a MAP point. LSSVM is in general more robust and consistent as with similarity features. Although SVM map outperforms it on dev., LSSVM-AP is better on test in each of the three metrics. LSSVM-AP  with exact inference further improves the results of LSSVM-AP. It outperforms SVM map by more than 1 point in terms of MAP. It should be noted that the embeddings that we use were trained in a classification setting, thus, giving an additional advantage to the classification models, e.g., the relative improvement of the baseline SVM when passing to embeddings is the highest among the models. Nonetheless, LSSVM approaches closest of all to CNN, with the variant of the model with exact search showing P@1 superior to that of CNN. This suggests that the structural ranking approaches are of decent capacity, and that the optimal solution lies in regions feasible to the structural linear model, considering also the high results of LSP-AP* on dev. set. This is despite the fact that, in contrast to CNN, which trains on the whole training set, we omit examples with only negative and only positive candidates (Sec. 5.1). Exploiting the information from such examples (subject to additional enhancement of our approach, as it would currently perform a zero update on them in Line 8 of Alg. 1 due to equal max-violated and ground truth rankings) might advance the performance. Thus, good features make our models competitive with the state of the art. 5.2.3 Cross-validation experiments In Tab. 3, we repeat the main experiments in the cross-validation setting, using the similarity features. On average, LSSVM-AP outperforms SVM map in terms of MAP and MRR, as in the standard setting, however, having relatively higher variance across the folds. The LSP models sustain their superiority using the similarity features also in cross-validation, with LSP-AP scoring the best across the models and with the least variance. The results of our cross-validation experiments on TREC13 are depicted in Tab. 4. LSP-AP slightly improves over the baseline models in terms of MAP. The baseline LSP this time deviates the least over the folds and reaches better P@1 among all the models. LSSVM-AP instead underperforms in this experiment, which might be for the reason of shortage of the data for validation. It is also true that in this work, by fixing the weighting schema v , we limited our study to one particular case of a structural ranking representation. However, finding an appropriate structural feature space, e.g., to the extent enabled by tuning the positional weights v j for the particular application, can be potentially beneficial. In this paper, we proposed new structured prediction algorithms for ranking problems. In particular, we designed (i) a new loss function that leads to the direct optimization of MAP; and (ii) two new algorithms, based on LSP and LSSVM solvers, to optimize it. The comparative results on the benchmarks for passage reranking, WikiQA and TREC13, demonstrate an improvement of LSP-AP over the standard SVM classifier, which is particularly large in the case of WikiQA. LSP without any loss augmentation can achieve good performance, as well, subject to accurate tuning of the epoch number parameter. In the same setting, LSSVM-AP is comparable to SVM map baseline. Finally, we used CNN embeddings as more expressive features in our models. We found that (i) linear models can benefit from them; (ii) LSSVM-AP is more robust than the LSP models to the use of a complex representation; and (iii) traditional max margin methods may not be on par with neural networks on tasks, such as WikiQA, however providing them with right features (embeddings) can make them approach the performance of neural models. This suggests an interesting research line on using our structural models and loss function optimizing MAP in neural models. We would like to thank the anonymous reviewers for their competent and useful suggestions. Many thanks to Kateryna Tymoshenko and Daniele Bonadiman for kindly providing us with the CNN embeddings for our experiments.
abstain objective abstain result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain result objective method method abstain result method result method method other other other other other other other other other other method other other other other other other other other other other other objective abstain method method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method method method abstain other abstain abstain method abstain abstain method abstain abstain abstain method method abstain abstain abstain abstain abstain abstain method method method method abstain abstain method abstain abstain abstain method abstain abstain method method abstain method method abstain method abstain other abstain method abstain abstain method method abstain abstain abstain abstain abstain abstain abstain method abstain method method abstain method abstain method abstain method abstain method method result method method method abstain abstain abstain abstain method abstain abstain method abstain abstain method abstain abstain method method abstain abstain method result method method method abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method abstain method abstain abstain result abstain abstain abstain abstain abstain abstain objective method abstain abstain abstain abstain abstain method result abstain abstain abstain method other other