# Deep-QPP: A Pairwise Interaction-based Deep Learning Model for Supervised
Query Performance Prediction

Suchana Datta  University College Dublin, Ireland<EMAIL_ADDRESS>,  Debasis Ganguly  University of Glasgow, UK<EMAIL_ADDRESS>,
Derek Greene  University College Dublin, Ireland<EMAIL_ADDRESS>and
Mandar Mitra  Indian Statistical Institute, India<EMAIL_ADDRESS>
(2022)

###### Abstract.

Motivated by the recent success of end-to-end deep neural models for ranking
tasks, we present here a supervised end-to-end neural approach for query
performance prediction (QPP). In contrast to unsupervised approaches that rely
on various statistics of document score distributions, our approach is
entirely data-driven. Further, in contrast to weakly supervised approaches,
our method also does not rely on the outputs from different QPP estimators. In
particular, our model leverages information from the semantic interactions
between the terms of a query and those in the top-documents retrieved with it.
The architecture of the model comprises multiple layers of 2D convolution
filters followed by a feed-forward layer of parameters. Experiments on
standard test collections demonstrate that our proposed supervised approach
outperforms other state-of-the-art supervised and unsupervised approaches.

Supervised Query Performance Prediction, Interaction-based Models,
Convolutional Neural Networks

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
Fifteenth ACM International Conference on Web Search and Data Mining; February
21–25, 2022; Tempe, AZ, USA††booktitle: Proceedings of the Fifteenth ACM
International Conference on Web Search and Data Mining (WSDM ’22), February
21–25, 2022, Tempe, AZ, USA††price: 15.00††doi: 10.1145/3488560.3498491††isbn:
978-1-4503-9132-0/22/02††ccs: Information systems Query intent††ccs:
Information systems Information retrieval query processing

##  1\. Introduction

The evaluation of information retrieval systems is a challenging problem to
solve outside the realm of the Cranfield paradigm (Voorhees, 2001), i.e., in
situations when there are no relevance assessments available, such as those in
deployed search systems used by real-life users beyond the laboratory
environment. Query performance prediction (QPP) (Cronen-Townsend et al., 2002;
Carmel et al., 2006; Zhou and Croft, 2007; Shtok et al., 2012; Zendel et al.,
2019), therefore, remains an important and active area of research, because of
its usefulness in estimating the quality of a retrieval system on a wide range
of queries. The output of a QPP estimator function $\phi(Q)$ is a likelihood
score ($\in\mathbb{R}$), which given a query $Q$, predicts the retrieval
quality of the query. It may therefore, in a sense, be considered to represent
how _easy_ (or specific) the query is, because the higher the predicted
estimate, the higher is the likelihood that a retrieval model will perform
well for the query.

The majority of existing QPP methods relies on devising a suitable heuristic
function for predicting the likelihood of how easy a query will be for a
retrieval system. Typically, this is estimated by computing the probability of
how specific or well-formulated the query is. The specificity measures are
computed using either: i) an aggregate of collection statistics over query
terms commonly known as _pre-retrieval_ QPP estimators (Hauff, 2010; Hauff et
al., 2008); or by ii) leveraging information from the top-retrieved documents,
e.g., assessing the skewness of document similarity scores (Zhou and Croft,
2007; Shtok et al., 2012), or measuring the topical differences between the
set of top-retrieved documents and the rest of the collection (Cronen-Townsend
et al., 2002).

Supervised deep neural ranking models have recently been shown to improve
retrieval effectiveness over their unsupervised statistical counterparts (Guo
et al., 2016; Xiong et al., 2017; Dai et al., 2018; Dehghani et al., 2017;
Khattab and Zaharia, 2020). In contrast to preset similarity functions (e.g.
BM25 or LM), these supervised models rely on data-driven parametric learning
of similarity functions, usually leveraging an interaction mechanism between
the similarities of the embedded representations of constituent words of
queries and their retrieved documents (Guo et al., 2016; Xiong et al., 2017;
Dai et al., 2018).

While the benefits of using supervised approaches have predominantly been
established for ranking (Asadi et al., 2011; Cohen et al., 2018; Khattab and
Zaharia, 2020; Dehghani et al., 2017) and recommendation tasks (Dacrema et
al., 2019; Li et al., 2017; Wu et al., 2019; Smirnova and Vasile, 2017), the
exploration of supervised approaches for QPP has been limited. The only
supervised QPP approach, that we are aware of to the best of our knowledge at
the time of writing this paper, is the study (Zamani et al., 2018a) which used
a combination of features (such as retrieval scores) and word embedded vectors
to learn an optimal way of _combining_ a number of different QPP estimates
into a single one, thereby outperforming the effectiveness achieved by each
individually. A major limitation of (Zamani et al., 2018a) is that the
training procedure involves weak supervision over a number of estimators to
find an optimal combination. In contrast, our proposed method is solely data-
driven because it does not rely on other estimators. Moreover, our method is
strictly supervised as opposed to the weak supervision employed in (Zamani et
al., 2018a).

#### _Contributions_

In summary, the key contributions of this paper include –

  1. (1)

An end-to-end supervised QPP model, where instead of learning to optimize the
relative importance of different predictors (Zamani et al., 2018a), our model
learns a comparison function of relative specificity (estimated retrieval
quality) between query pairs.

  2. (2)

Early interactions between query-document pairs, where similar to the deep
relevance matching model (DRMM) (Guo et al., 2016), our model makes use of
early interactions between a query and its top-retrieved set of documents. We
argue that this way of constituting the input improves the model’s capacity to
generalize better as opposed to the late interaction between the content of
the queries and the documents (Zamani et al., 2018a).

Figure 1.  While representation-based models rely on _late interaction_
involving shared parameters (left), interaction-based models, on the other
hand, make use of _early interactions_ transforming paired instances into a
single input.

##  2\. Deep-QPP Model Description

We first describe the working principle of our approach which is based on
capturing term-semantics interaction at two levels, first, at the _intra-
query_ level of modeling, the interaction between the queries themselves and
their top-retrieved documents, and then at the _inter-query_ level, to model
their relative specificity measures.

###  2.1. Representation vs. Interaction

A fundamental difference between a representation-based model and an
interaction-based model (Guo et al., 2016) is illustrated in Figure 1. The
former first constructs a representation of each instance from a pair of
inputs, and then optimizes this representation so as to maximize the
likelihood of predicting a function involving this pair (as seen from the left
diagram of Figure 1). In contrast, an interaction-based model first
_transforms_ a paired data instance into a single instance via an interaction
operator $\oplus:\mathbb{R}^{d}\times\mathbb{R}^{d}\mapsto\mathbb{R}^{p}$,
where $d$ and $p$ are the sizes of the raw and the transformed inputs,
respectively.

We now discuss the type of interaction suitable for a supervised deep QPP
approach. For QPP, the objective function that should be learned from the
reference labels is a comparison between a pair of queries, $Q_{a}$ and
$Q_{b}$. More concretely, this comparison is an indicator of the relative
difficulty between the queries, i.e., whether $Q_{a}$ is more difficult than
$Q_{b}$ or vice versa.

While pre-retrieval QPP approaches only rely on the information from a query
itself (e.g., aggregate collection statistics for its terms (Hauff, 2010;
Hauff et al., 2008)), it has been shown that post-retrieval approaches, which
make use of additional information from the top-retrieved documents of a query
(Zhou and Croft, 2007; Shtok et al., 2012), usually perform better. Motivated
by this, we also include information from the top-retrieved documents in the
form of _early interactions_ (which we refer to as the _intra-query_
interactions). The parameters of these interactions are then optimized with
the help of a _late interaction_ between the queries, which seeks to capture
the important characteristic differences of these early interactions towards
identifying which query among the pair is easier. An overview of our model is
shown in Figure 2.

Figure 2.  Unlike an entirely representation-based or interaction-based model
(Figure 1), our model combines the benefits of both early and late
interactions, to address: a) the interaction of the terms in the top-retrieved
documents of a query with the constituent terms of the query itself; b) the
characteristic pattern of these interactions to estimate the comparison
function $y(Q_{a},Q_{b})$ between a pair of queries. Each individual query-
document interaction is shown with a different color.

###  2.2. Query-Document Interactions

In unsupervised post-retrieval QPP approaches, the interaction between the
terms in a query and those of the top-retrieved set takes the form of
statically defined functions, which aim to capture how distinct the top-
retrieved set is with respect to the collection (e.g., NQC (Shtok et al.,
2012) uses the skewness of document retrieval scores, while WIG (Zhou and
Croft, 2007) measures the information gain from the top-retrieved set with
respect to the collection). The intra-query interaction shown in Figure 2
involves computing an interaction between the terms of a query and those in
its top-retrieved set of documents. This interaction then acts as an input
source to learn an optimal specificity function automatically from the data.

##### Documents to consider for interaction

A common principle that works well as a specificity estimator for post-
retrieval QPP approaches, is to measure the distinctiveness between the set of
documents towards the top-ranks from the rest of the retrieved set. The
standard deviation of the document similarity scores in NQC (i.e., expected
difference from the average score), acts as an estimate for the topic
distinctiveness of the top set.

Motivated by this insight, in our approach, instead of using only a set of
top-$k$ documents, we use information from both the upper and the lower parts
of a ranked list. The objective is to capture the differences in the
interaction patterns of a set of highly similar (the upper part of a ranked
list) and not-so-highly similar documents (the lower part) as useful cues for
QPP.

As notations, we denote the set of documents considered for interaction with a
query $Q$ as $R(Q)$, which is comprised of a total of $M=t+b$ documents,
including the top-$t$ and the bottom-$b$ ranked ones. The index of the bottom-
most document considered for interaction computation is specified by a
parameter $N$. This means that the lower part of the ranked list, comprised of
$b$ documents are, in fact, those ranked from $N$ to $N-b+1$. For example, a
value of $t=10$ and $b=20$ means that
$R(Q)=\\{D_{1},\ldots,D_{10}\\}\cup\\{D_{81},\ldots,D_{100}\\}$.

In our experiments, we treat $t$ and $b$ as hyper-parameters (see Section
4.4), and restrict $N$ to a value of $100$ because it is unlikely that any
evidence from documents beyond the top-$100$ would be useful for the QPP task.

##### Interaction between each query term and a document

We now describe how we compute the query-document interaction matrices for
each document $D\in R(Q)$ for a query $Q$. As a first step, we calculate the
cosine similarities between the embedded representations of terms – one from
the query $Q_{a}$ and the other from the document $D^{a}_{i}$. Similar to (Guo
et al., 2016), the distribution of similarities between the
$j{{}^{\mathrm{th}}}$ query term $q_{j}$ and constituent terms of $D^{a}_{i}$
is then transformed into a vector of fixed length $p$ by the means of
computing a histogram of the similarity values over a partition of $p$ equi-
spaced intervals defined over the range of these values (i.e. the interval
$[-1,1)$). The $\beta{{}^{\mathrm{th}}}$ component ($\beta=1,\ldots,p$) of
this interaction vector is given by the count of how many terms yield
similarities that lie within the $\beta{{}^{\mathrm{th}}}$ partition of
$[-1,1)$, i.e.,

(1) $(q_{j}\oplus D^{a}_{i})_{\beta}=\sum_{w\in
D^{a}_{i}}\mathbb{I}\big{[}\frac{2(\beta-1)}{p}-1\leq\frac{\mathbf{q}_{j}\cdot\mathbf{w}}{|\mathbf{q}_{j}||\mathbf{w}|}<\frac{2\beta}{p}-1\big{]},$

where both $\mathbf{q}_{j}\in\mathbb{R}^{d}$ and
$\mathbf{w}\in\mathbb{R}^{d}$, and the interaction vector $q_{i}\oplus
D^{a}_{i}\in\mathbb{R}^{p}$, and $\mathbb{I}[X]\in\\{0,1\\}$ is an indicator
variable which takes the value of $1$, if a property $X$ is true and $0$
otherwise.

###### Example 2.0.

If $p=4$, the interval $[-1,1)$ is partitioned into the set
$\\{[-1,-0.5),[-0.5,0),[0,0.5),[0.5,1)\\}$. For a 3-term document $d$, if the
cosine similarities are $0.2$, $-0.3$ and $0.4$ with respect to a query term
$q$, then $q\oplus d=(0,1,2,0)$.

##### Collection statistics based relative weighting

The specificity (i.e., collection statistics, such as idf) of query terms
contributes to the effective estimate of QPP scores both in pre-retrieval and
post-retrieval approaches. We, therefore, incorporate the idf values of each
query term as a factor within the interaction patterns to relatively weigh the
contributions from the interaction vectors $q_{j}\oplus D^{a}_{i}$. In our
proposed approach, we use a generalized version of Equation 1, where we
incorporate the idf factor as a part of the interaction vector components,
i.e.,

(2) $(q_{j}\oplus D^{a}_{i})_{\beta}=\log(\frac{N_{0}}{n(q_{j})})\sum_{w\in
D^{a}_{i}}\mathbb{I}\big{[}\frac{2(\beta-1)}{p}-1\leq\frac{\mathbf{q}_{j}\cdot\mathbf{w}}{|\mathbf{q}_{j}||\mathbf{w}|}<\frac{2\beta}{p}-1\big{]},$

where $n(q_{j})$ denotes the number of documents in the collection where the
$j{{}^{\mathrm{th}}}$ query term $q_{j}$ occurs, and $N_{0}$ denotes the total
number of documents in the collection.

##### Overall interaction between a query and a document

Each $p$-dimensional interaction vector computed for the $j{{}^{\mathrm{th}}}$
query term forms the $j{{}^{\mathrm{th}}}$ row of the overall interaction
matrix between the query $Q_{a}$ and the $i{{}^{\mathrm{th}}}$ document
$D^{a}_{i}$. The overall interaction matrix, $Q_{a}\oplus
D^{a}_{i}\in\mathbb{R}^{k\times b}$ is thus given by

(3) $Q_{a}\oplus D^{a}_{i}=[(q_{1}\oplus D^{a}_{i})^{T},\ldots,(q_{k}\oplus
D^{a}_{i})^{T}]^{T},$

where $k$ is a preset upper limit of the number of terms in a query. A zero-
padding is used for the row indices exceeding the number of query terms, i.e.,
$(q_{j}\oplus D^{a}_{i})=\\{0\\}^{b},\,\forall j>|Q_{a}|$. Referring back to
Figure 2, each $k\times p$ interaction matrix between a query $Q_{a}$ and a
document $D^{a}_{i}$ corresponds to a colored rectangle (shown in the planes
above the queries and documents).

Figure 3.  Our proposed end-to-end QPP model comprising a Siamese network of
shared parameters of layered convolutional feature extraction, followed by
either i) merge (concatenation) and a fully connected (FC) layer with a
$\operatorname{Sigmoid}$ loss for pairwise testing (Equation 7) yielding a
binary comparison indicator between a pair, or ii) a linear activation layer
with pairwise hinge loss for pointwise testing yielding a score for a given
query (Equation 8). Since the interaction for MDMQ and SDSQ are matrices with
a single row only, the two layers of convolution filter sizes for these
approaches are $1\times 5$ and $1\times 3$ (see Section 2.4).

##### Interaction between a query and its top-retrieved set

Finally, each individual document-query interaction matrix, when stacked up
one above the other in the order of the document ranks, yields an interaction
tensor of order $M\times k\times p$. Formally,

(4) $Q_{a}\oplus R(Q_{a})=\begin{bmatrix}Q_{a}\oplus D^{a}_{1}\\\ \ldots\\\
\ldots\\\ Q_{a}\oplus D^{a}_{M}\end{bmatrix}$

###  2.3. Layered Convolutions for QPP

After constructing the local interactions of a query with its top-retrieved
set of documents, i.e. the intra-query interactions, the next step is to
extract convolutional features from the $3^{rd}$ order interaction tensor,
$Q_{a}\oplus R(Q_{a})\in\mathbb{R}^{M\times k\times b}$ between a query
$Q_{a}$ and its top-retrieved set $R(Q_{a})$. To this end, we first need to
slice the $3^{rd}$ order tensor into separate matrices ($2^{nd}$ order
tensors), on each of which, 2D convolution can be applied to extract
distinguishing features from the raw data of query-document interactions.
Before describing the ways to slicing the tensor into matrices in Section 2.4,
we first briefly describe the architecture that we employ to extract useful
features from the lower-dimensional slices of the interaction tensor.

##### Brief background on 2D convolution

We do not explain the background of 2D convolution operation (Rodríguez-
Sánchez et al., 2015) in detail. Formally speaking, if
$\mathbf{X}\in\mathbb{R}^{M\times P}$ represents an input data matrix, and if
$\mathbf{W^{(\mathit{l})}}\in\mathbb{R}^{k_{l}\times k_{l}}$ ($k_{l}\mod 2=1$,
i.e., $k_{l}$ an odd number) denotes the kernel weight matrix of the
$l{{}^{\mathrm{th}}}$ layer, conveniently represented as $(W^{(l)}_{-\lfloor
k/2\rfloor},\ldots,0,\ldots,W^{(l)}_{\lfloor k/2\rfloor})$, then the outputs
of layer-wise convolution, generally speaking, are given by

(5) $\mathbf{h}^{(l)}_{r,c}=f^{(l)}(\sum_{i=-\lfloor k/2\rfloor}^{\lfloor
k/2\rfloor}\sum_{j=-\lfloor k/2\rfloor}^{\lfloor
k/2\rfloor}\mathbf{W}^{(l)}_{i,j}\mathbf{h}^{(l-1)}_{r+i,c+j}),$

for each $l=1,\ldots,L$ ($L$ being the total number of layers), where
$\mathbf{h}^{(l-1)}\\!\in\\!\mathbb{R}^{M^{(k-1)}\times P^{(k-1)}}$ is the
output obtained from the previous layer of the convolution filter, with
$h^{(1)}\\!=\\!X$, $M^{(1)}\\!=\\!M$ and $P^{(1)}=P$. The function $f^{(l)}$
is an aggregation function that, generally speaking, progressively reduces the
size of the convolutional representations, $\mathbf{h}^{(l)}$, across layers.
Aggregation methods commonly applied in computer vision include the
$\operatorname{MaxPooling}$ (Christlein et al., 2019; Wu and Gu, 2015) and
$\operatorname{AvgPooling}$ (Shen et al., 2014) functions.

##### Late interactions with convolutional features

A more detailed view of the late interaction across a query pair is shown in
Figure 3. Referring to the notation from Equation 5, we employ $L=2$ (i.e. use
a total of 2 convolution layers), and use $k_{1}=5$ and $k_{2}=3$ (i.e. a 5x5
filter for the first layer and a 3x3 for the second one). The aggregate
function, $f^{(l)}$, of each layer $l$ is set to the
$\operatorname{MaxPooling}$ operation.

After extracting the convolutional features for each query vs. top-documents
interaction tensor (shown as the two cuboids towards the extreme left of
Figure 3), we employ the standard practice of merging the convolutional filter
outputs of each query into a single vector (shown as the ‘merge’ operation)
(Wang et al., 2020; Byerly et al., 2020). Following the merge operation, which
now combines abstract features extracted from the local interactions of the
two queries into a single vector, we apply a fully connected dense layer.
Depending on whether we test the network in a pointwise or pairwise manner,
the loss function is set to either the $\operatorname{Sigmoid}$ function or a
function that seeks to maximize the accuracy of the comparison function
between pairs. Section 3 provides more details on the network training
process.

###  2.4. Reshaping the Interaction Tensor

There exists a number of different choices for slicing up the interaction
tensor of Equation 4 into a set of matrices for the purpose of separately
applying 2D convolution on each and then combining the features, shown as the
_reshaping_ function $\pi:\mathbb{R}^{3}\mapsto\mathbb{R}^{2}$ in Figure 3. We
now discuss each alternative and examine their pros and cons in the context of
the QPP problem.

As our nomenclature, we characterize reshaping functions by whether the
information across i) top-retrieved documents are merged together, or across
ii) query-terms are merged together. A part of the name thus uses the
characters D to denote the top-retrieved set, and Q to denote query terms. To
indicate ‘merging’, we use the letter ‘M’ and to denote its counterpart, we
use the letter ‘S’ (separate). For instance, the name MDMQ means that the
information from both top-documents and query terms are merged together.

##### MDMQ (Merged Documents Merged Query-terms)

This is the most coarse-grained way to reduce the dimensionality of the
interaction tensor of order $3$ (Equation 4) by reducing the $M\times k\times
p$ tensor to a flattened vector of dimensionality $Mkp$, which can still be
imagined to be a matrix of dimension $1\times Mkp$ allowing 1D convolutions to
be applied. This method extracts abstract features at an aggregate level
rather than for individual documents separately. This may not be desirable
because, in standard QPP methods such as WIG and NQC, an individual
contribution from each document score is responsible for the predicted
specificity measure.

##### SDMQ (Separate Documents Merged Query-terms)

This corresponds to the most natural way of grouping an interaction tensor,
$Q\oplus R(Q)$, by considering the $i{{}^{\mathrm{th}}}$ row for each
$i=1,\ldots,M$, $Q\oplus D_{i}$, as a matrix of dimension $k\times p$. This
method allows the extraction of abstract features from each document
separately in relation to the whole query. Thus, it takes into account the
compositionality of the query terms, and at the same time avoids mixing
information across documents. This conforms to how most unsupervised post-
retrieval QPP methods actually work.

##### MDSQ (Merged Documents Separate Query-terms)

Contrary to grouping the interaction tensor row-wise, for this method we slice
out the constituent matrices column-wise. Each matrix is thus of dimension
$M\times p$, and there are a total $k$ of them, on each of which we apply 2D
convolution for feature extraction. This QPP method thus does not take into
account the compositionality of the constituent query terms while considering
the semantic interactions. Rather it treats the whole set of top-retrieved
documents in an aggregated manner, which is also somewhat counter-intuitive
because a document at the very top rank should be treated in a different
manner from the very bottom one, i.e. the one at $M{{}^{\mathrm{th}}}$ rank.

##### SDSQ (Separate Documents Separate Query-terms)

This is the most fine-grained approach, which considers every interaction
vector between the $j{{}^{\mathrm{th}}}$ query term and $i{{}^{\mathrm{th}}}$
document (see Equation 2 as a separate candidate for convolutional feature
extraction. Each such interaction vector between a query-term and a document
is of dimension $p$ and there are a total of $Mk$ such vectors. As with the
MDMQ approach, we apply 1D convolution on these vectors.

A point to note is that, although Figure 3 shows the convolution filters as
$5\times 5$ and $3\times 3$, for MDMQ and SDSQ approaches, these filters are
of size $1\times 5$ and $1\times 3$ respectively.

##  3\. Deep-QPP Training

The network in Figure 3 is trained with instances of query pairs with two
different objectives – pointwise and pairwise. In the pairwise case, the
network directly learns the comparison function, i.e. a binary indicator of
the anti-symmetric relation between a query pair. On the other hand, the
pointwise objective aims to predict a QPP score, instead of the relative order
of specificity between a pair. Before describing the objectives, we first
provide details on obtaining the data instances and the reference labels.

###  3.1. Instances and Ground-truth Labels

Given a training set of queries $\mathcal{Q}=\\{Q_{1},\ldots,Q_{m}\\}$, we
construct the set of all unordered pairs of the form $(Q_{a},Q_{b})$, where
$\forall a,b\leq m$ and $b>a$. The reference label, $y(Q_{i},Q_{j})$, of a
paired instance is determined by a relative comparison of the retrieval
effectiveness obtained by a system with a target metric. The retrieval
effectiveness, in turn, is computed with the help of available relevance
assessments. Formally speaking, if $\mathcal{M}$ denotes an IR evaluation
measure (e.g., average precision or AP), which is a function of i) the known
set of relevant documents - $\mathcal{R}(Q)$ for a query $Q\in\mathcal{Q}$,
and ii) the set of documents retrieved with a model $\mathcal{A}$ (e.g., LM-
Dir (Zhai and Lafferty, 2001)), then

(6)
$y(Q_{a},Q_{b})=\operatorname{sgn}(\mathcal{M}(Q_{a};\mathcal{R}(Q_{a}))-\mathcal{M}(Q_{b};\mathcal{R}(Q_{b}))),$

where $\operatorname{sgn}(x)=0$ if $x\leq 0$ or $1$ otherwise.

For all our experiments, we used AP@100 and nDCG@20 as the target metric
$\mathcal{M}$. As the IR model, $\mathcal{A}$, we employ LM-Dir with the
smoothing parameter $\mu=1000$ following QPP literature (Shtok et al., 2012).
We emphasize that the results of our experiments are mostly insensitive to the
choice of either the target metric used or the IR model employed.

###  3.2. Pairwise Objective

For the pairwise objective, the Deep-QPP model is trained to maximize the
likelihood of correctly predicting the indicator value of the comparison
between a given pair of queries. The purpose here is to learn a data-driven
generalization of the comparison function. During the testing phase, the model
outputs a predicted value of the comparison between a pair of queries unseen
during the training phase. The output layer for the pairwise objective thus
constitutes a $\operatorname{Sigmoid}$ layer, predicting values of
$y(Q_{a},Q_{b})$ (see Equation 6) as a function of the network parameters
denoted as $\hat{y}(Q_{a},Q_{b};\Theta)$. During the training phase, the
parameter updates seek to minimize the standard square loss

(7)
$\mathcal{L}(Q_{a},Q_{b})=(y(Q_{a},Q_{b})-\hat{y}(Q_{a},Q_{b};\Theta))^{2}$

between the ground-truth and the predicted labels.

###  3.3. Pointwise Objective

For pointwise testing, as a test input, the network takes a single query $Q$,
as opposed to the pair of queries in the pairwise situation from Section 3.2.
Instead of predicting a binary indicator comparison, the network predicts a
score $\hat{y}(Q;\Theta)$ that can be used as an estimated measure of
specificity of $Q$. To allow for pointwise testing, the output from the shared
layer of parameters goes into a linear activation unit predicting a real-
valued score $\hat{y}(Q;\Theta)$, which is a function of one query (rather
than a pair), as can be seen from the bottom-right part of the Figure 3.
Rather than training the network on a merged representation of a query pair,
the loss function includes separate contributions from the two parts of the
network corresponding to each query, the objective being to update the
parameters for maximizing the comparison agreements between the reference and
the predicted scores. Specifically, we minimize the following hinge loss:

(8)
$\mathcal{L}(Q_{a},Q_{b})=\max(0,1-\operatorname{sgn}(y(Q_{a},Q_{b})\cdot(\hat{y}(Q_{a};\Theta)-\hat{y}(Q_{b};\Theta)))).$

##  4\. Experiments

###  4.1. Datasets and Hyper-parameters

Coll | #Docs | Topic Set | $|\mathcal{Q}|$ | Avg. Q_len | Avg. #Rel
---|---|---|---|---|---
Disks 4 & 5 | 528,155 | TREC-Rb | 249 | 2.68 | 71.21
CWeb09B-S70 | 29,038,220 | TREC-Web | 200 | 2.42 | 16.03
Table 1.  Dataset Characteristics (the suffix ‘S70’ indicates that documents
detected as spams with confidence scores higher than $70\%$ were removed from
the collection).

##### Collections

We experiment with two standard ad-hoc IR test collections, namely the TREC
Robust (comprised of news articles) and the ClueWeb09B (Clarke et al., 2010)
(comprised of crawled web pages). For the ClueWeb experiments, we used the
Waterloo spam scores (wat, 2021) to remove documents which were detected to be
spam with confidence $>70\%$. We denote this subset as CWeb09B-S70 in Table 1.

##### Train and test splits

Since our proposed Deep-QPP method is a supervised one, the method first
requires a training set of queries to learn the model parameters and then a
test set for evaluating the effectiveness of the model. Following the standard
convention in the literature, e.g. (Zamani et al., 2018a; Shtok et al., 2012;
Zendel et al., 2019), we employ repeated partitioning (specifically, 30 times)
of the set of queries into 50:50 splits and report the average values of the
correlation metrics (see Section 4.3) computed over the 30 splits.

A major difference of our setup compared to existing QPP approaches is the use
of the training set. While the training set for unsupervised approaches serve
the purpose of _tuning the hyper-parameters_ of a model by grid search, in our
case, it involves _updating the learnable parameters_ of the neural model by
methods such as stochastic gradient descent.

##### Hyper-parameter tuning

The most common hyper-parameter for existing unsupervised QPP approaches is
the number of top-$M$ documents considered for computing the statistics on the
document retrieval scores, as in NQC and WIG, or to estimate a relevance
feedback model, as in Clarity and UEF (see Section 4.2 for more details). We
tune this parameter via grid search on the training partition. As prescribed
in (Zamani et al., 2018a), the values used in grid search were $\\{$5, 10, 15,
20, 25, 50, 100, 300, 500, 1000$\\}$.

###  4.2. Baselines

We compare our supervised Deep-QPP approach with a number of standard
unsupervised QPP approaches, and also a more recent weak supervision-based
neural approach (Zamani et al., 2018a). In our investigation, we do not
include QPP methods that leverage external information, such as query variants
(Butman et al., 2013). Using query variants has been shown to improve the
effectiveness of unsupervised QPP estimators and it is also likely that
including them in our supervised end-to-end approach will may also lead to
further improvement in its performance. However, since the main objective of
our experiments is to investigate if a deep QPP model can outperform existing
ones, we leave the use of external data for future exploration. Moreover, we
also do not include the pre-retrieval QPP approaches, such as avg. idf etc.,
because they have been reported to be outperformed by post-retrieval
approaches in a number of existing studies (Cronen-Townsend et al., 2002; Zhou
and Croft, 2007; Shtok et al., 2012; Zamani et al., 2018a).

####  4.2.1. Unsupervised Approaches

This refers to existing methods that make use of term weight heuristics to
measure the specificity estimates of queries. The underlying common principle
on which all these methods rely is the assumption that, if the set of top-
documents retrieved for a query is substantially different from the rest of
the collection, then the query is likely to be indicative of unambiguous
information need. This makes it a potentially good candidate for achieving
effective retrieval results. These methods mainly differ in the way in which
they calculate the similarity of the top-retrieved set of documents from the
rest of the collection.

##### Clarity (Cronen-Townsend et al., 2002)

This method estimates a relevance model (RLM) (Lavrenko and Croft, 2001)
distribution of term weights from a set of top-ranked documents, and then
computes its KL divergence with the collection model - the higher the KL
divergence (a distance measure) the higher is the query specificity.

##### WIG (Zhou and Croft, 2007)

As its specificity measure, weighted information gain (WIG) uses the
aggregated value of the information gain with each document (with respect to
the collection) in the top-retrieved set. The more topically distinct a
document is from the collection, the higher its gain will be. Hence, the
average of these gains characterizes how topically distinct is the overall set
of top-documents.

##### NQC (Shtok et al., 2012)

Normalized query commitment (NQC) estimates the specificity of a query as the
standard deviation of the RSV’s of the top-retrieved documents with the
assumption that a lower deviation from the average (indicative of a flat
distribution of scores) is likely to represent a situation where the documents
at the very top ranks are significantly different from the rest. NQC thus
makes use of not only the relative gain of a document score from the
collection (similar to WIG) but also the gain in a document’s score with
respect to the average score.

##### UEF (Shtok et al., 2010)

The UEF method assumes that information from some top-retrieved set of
documents are more reliable than others. As a first step, the UEF method
estimates how robust is a set of top-retrieved documents by checking the
relative stability in the rank order before and after relevance feedback (by
RLM). The higher the perturbation of a ranked list post-feedback for a query,
the greater is the likelihood that the retrieval effectiveness of the initial
list was poor, which in turn suggests that a smaller confidence should be
associated with the QPP estimate of such a query.

####  4.2.2. Supervised Approaches

Our choice of supervised baselines is guided by two objectives - _first_ , to
show that (strong) supervision using the ground-truth of relative query
performance is better than the existing approach of weak supervision on QPP
estimation functions (Zamani et al., 2018a), and _second_ , to demonstrate
that a mixture of both early and late interactions (i.e., a hybrid of both
content and interaction-focused approaches) is better than purely content-
based ones (see Figures 1 and 2).

##### Weakly Supervised Neural QPP (WS-NeurQPP) (Zamani et al., 2018a)

The main difference between WS-NeurQPP and Deep-QPP lies in the source of
information used and also the objective of the neural end-to-end models. WS-
NeurQPP uses weak supervision to approximate the scores of individual QPP
estimators so as to learn an optimal combination. As inputs, it uses the
retrieval scores, along with the word embedded vectors. However, in contrast
to our approach, it does not use interactions between terms and is hence a
purely representation-based approach.

##### Siamese Network (SN)

This approach is an ablation of the Deep-QPP model (Figure 3). Here instead of
feeding in the interaction tensors between a query and its top-retrieved
documents, we simply input the dense vector representations of queries in
pairs. We experiment with two different types of dense vector inputs - one
where we used pre-trained RoBERTa vectors (Liu et al., 2019) obtained using
the HuggingFace library (web, 2021), and the other, where we used the sum of
the Skipgram (Mikolov et al., 2013) word embedded vectors (trained on the
respective target collections) of constituent terms as the dense
representation of a query for input. We name these two ablations as SN-BERT
and SN-SG, respectively.

##### No Intra-Query Interaction

As another ablation of Deep-QPP, we only use the interaction between the terms
of the query pairs themselves. The interaction tensor between a pair of
queries is a $2^{nd}$ order tensor, i.e., a $k\times p$ matrix. This is a
purely interaction-based method, and in principle, is similar to DRMM (Guo et
al., 2016), with the added layer of 2D convolutions. We denote this baseline
as DRMM.

###  4.3. Experiment Settings

|  Metric : AP$@100$ |  Metric : nDCG$@20$
---|---|---
| TREC-Robust | ClueWeb09B | TREC-Robust | ClueWeb09B
Methods | Pairwise | Pointwise | Pairwise | Pointwise | Pairwise | Pointwise | Pairwise | Pointwise
| Accuracy |  P-$\rho$ |  K-$\tau$ | Accuracy |  P-$\rho$ |  K-$\tau$ | Accuracy |  P-$\rho$ |  K-$\tau$ | Accuracy |  P-$\rho$ |  K-$\tau$
Clarity (Cronen-Townsend et al., 2002) | 0.6251 | 0.4863 | 0.3140 | 0.6120 | 0.1911 | 0.0641 | 0.6118 | 0.3529 | 0.2462 | 0.6101 | 0.0923 | 0.0714
NQC (Shtok et al., 2012) | 0.6720 | 0.5269 | 0.4041 | 0.7030 | 0.2654 | 0.1518 | 0.6689 | 0.4261 | 0.3017 | 0.6916 | 0.3105 | 0.1987
WIG (Zhou and Croft, 2007) | 0.6613 | 0.5440 | 0.4279 | 0.6829 | 0.2492 | 0.1920 | 0.6629 | 0.3915 | 0.2407 | 0.6710 | 0.2780 | 0.1823
UEF (Shtok et al., 2010) | 0.6941 | 0.5523 | 0.4154 | 0.7217 | 0.3162 | 0.1959 | 0.6792 | 0.5029 | 0.3510 | 0.6925 | 0.3320 | 0.1854
SN-BERT | 0.6613 | 0.5208 | 0.4169 | 0.6902 | 0.2317 | 0.1441 | 0.6529 | 0.5023 | 0.3624 | 0.6724 | 0.2241 | 0.1334
SN-SG | 0.6349 | 0.5112 | 0.3987 | 0.6273 | 0.2110 | 0.1154 | 0.6147 | 0.4736 | 0.3561 | 0.6231 | 0.2049 | 0.1283
DRMM | 0.5871 | 0.4730 | 0.3710 | 0.6023 | 0.2014 | 0.1141 | 0.5629 | 0.4038 | 0.3119 | 0.6004 | 0.1927 | 0.1201
WS-NeurQPP(Zamani et al., 2018a) | 0.8123 | 0.7215 | 0.5090 | 0.7727 | 0.5192 | 0.2828 | 0.7973 | 0.5913 | 0.4126 | 0.7614 | 0.3928 | 0.2337
Deep-QPP (MDMQ) | 0.7857 | 0.6988 | 0.4981 | 0.7414 | 0.4636 | 0.2495 | 0.7632 | 0.5649 | 0.3619 | 0.7189 | 0.3509 | 0.2185
Deep-QPP (SDSQ) | 0.7210 | 0.6303 | 0.4018 | 0.6844 | 0.4208 | 0.2401 | 0.7284 | 0.5112 | 0.3065 | 0.6753 | 0.3124 | 0.2014
Deep-QPP (MDSQ) | 0.8006 | 0.7203 | 0.4989 | 0.7426 | 0.4840 | 0.2575 | 0.7824 | 0.5601 | 0.3245 | 0.7037 | 0.3518 | 0.2100
Deep-QPP (SDMQ) | 0.8420 | 0.7404 | 0.5434 | 0.8045 | 0.5532 | 0.3130 | 0.8371 | 0.6315 | 0.4614 | 0.7903 | 0.4431 | 0.2554
Table 2.  A comparison of the QPP effectiveness between Deep-QPP, and a set of
unsupervised and supervised baselines (shown in the 1st and the 2nd groups,
respectively). The average accuracy and the correlation values (see Section
4.3) of Deep-QPP over the best performing baseline - WS-NeurQPP, are
statistically significant (t-test with over 97% confidence).

##### Implementation

We used the Java API of Lucene 8.8 (luc, 2021) for indexing and retrieval;
also to implement the existing unsupervised QPP baselines (e.g., for
calculating the document and collection statistics). The supervised baseline -
WS-NeurQPP, and our proposed method - Deep-QPP, were both implemented in Keras
(ker, 2021). The code for our proposed method is available for research
purposes111https://github.com/suchanadatta/DeepQPP.git.

##### Metrics

Recall from Section 3 that the Deep-QPP model can be trained using either the
pairwise and the pointwise objectives. The pointwise test use-case is the
standard practice in existing QPP studies, where given a query, a QPP model
predicts a score indicative of the retrieval effectiveness. For this use-case,
we evaluate the effectiveness of the QPP methods with standard metrics used in
the literature: a) Pearson’s-$\rho$ correlation between the AP values of the
queries in the test-set and the predicted QPP scores; b) a ranking correlation
measure, specifically Kendall’s $\tau$ between the ground-truth ordering
(increasing AP values) of the test-set queries and the ordering induced by the
predicted QPP scores.

In pairwise testing, the network is presented with pairs of queries from the
test set, for which it then predicts binary indications of the relative order
of queries within the pairs. As a QPP effectiveness measure, we report the
average accuracy of these predictions, i.e. whether a predicted relation as
given by the $\operatorname{Sigmoid}$ output from Deep-QPP,
$\hat{y}(Q_{a},Q_{b};\Theta)$, matches the ground-truth that
$AP(Q_{a})<AP(Q_{b})$. Since $\hat{y}(Q_{a},Q_{b};\Theta)\in[0,1]$, we
_binarize_ this value to $\\{0,1\\}$ with the threshold of $0.5$, thus
indicating a prediction of whether $Q_{a}$ is a more difficult query than
$Q_{b}$ or vice versa.

##### Deep-QPP hyper-parameters

For the Deep-QPP method (and also for the semantic analyzer component of the
weakly supervised baseline WS-NeurQPP), we use skip-gram word vectors of
dimension $300$ trained on the respective document collections with a window
size of $10$ and $25$ negative samples. Another hyper-parameter in Deep-QPP is
the number of intervals (bins) $p$ used to compute the interactions in
Equation 2. In Table 2, we report results with $p=30$ (as per the settings of
the DRMM paper (Guo et al., 2016)), and later investigate the effect of
varying this parameter on the effectiveness of Deep-QPP (results in Figure 6).

We observed that, after a number of initial experiments, excluding the idf of
terms in the interaction tensors always produced worse results than when
including them. Therefore, in all our experiments with Deep-QPP, we use the
idf-weighted interactions (Equation 2), and do not report the results obtained
with Equation 1 for brevity. Another hyper-parameter that we use in the Deep-
QPP model to avoid over-fitting is the dropout probability, which we set to
$0.2$ as per the initial trends in our experimental findings.

###  4.4. Results

Table 2 presents the QPP results for all the methods investigated. _Firstly_ ,
we observe that the existing supervised approach for QPP, WS-NeurQPP,
outperforms the unsupervised approaches (NQC, WIG and UEF), which conforms to
the observations reported in (Zamani et al., 2018a). _Secondly_ , we observe
that the ablation baselines of Deep-QPP involving a purely representation-
based approach (SN-BERT and SN-SG), or a purely interaction-based one (DRMM),
perform worse than Deep-QPP. This is mainly because these baselines lack the
additional source of information – interactions of queries with the top-
retrieved set of documents, which Deep-QPP is able to leverage from. This
observation also reflects the fact that post-retrieval QPP approaches, with
the additional information from top-documents, typically outperform pre-
retrieval ones (Shtok et al., 2012).

_Third and most importantly_ , we observe that Deep-QPP outperforms WS-
NeurQPP, which confirms the hypothesis that explicitly learning the relative
specificity of query pairs with an end-to-end (strongly) supervised model is
better able to generalize than a weakly supervised approach which learns an
optimal combination of statistical predictors.

Another observation is that the SDMQ version of the reshaping function
$\pi:\mathbb{R}^{3}\mapsto\mathbb{R}^{2}$ (see Section 2.4 and Figure 3) turns
out to be the most effective, as we might expect. This also conforms to the
way in which unsupervised QPP approaches generally work, i.e., by first making
use of the information from each top-retrieved document (e.g. its score in NQC
and WIG) and then computing an aggregate function over them (e.g. their
variance in NQC, and relative gains in WIG).

To further compare Deep-QPP to WS-NeurQPP, we report the training-time
efficiency of both approaches in Figure 4. Due to a much larger number of
trainable parameters and larger input dimensionality (dense word vectors
instead of interactions between the dense vectors), WS-NeurQPP turns out to be
taking a much larger time to execute than Deep-QPP. The total number of
trainable parameters of WS-NeurQPP is $4.7$M which is about $2.5$X the number
of parameters in Deep-QPP ($1.9$M).

##### Hyper-parameter Sensitivity of Deep-QPP

Figure 5 shows that using the top-$10$ and the bottom-$10$ documents for the
interaction computation (Section 2.2) yields the best results, which shows
that neither a too small nor too large a number of documents should be used as
inputs for learning the QPP comparison function.

Figure 6 shows the effects of different bin-sizes, $p$ (of Equation 2), used
to compute the interactions between queries and the documents retrieved at top
and bottom ranks. A value of $30$ turned out to be optimal, which is similar
to the reported optimal value of the bin-size for interaction computation in
the LTR task (Guo et al., 2016).

Figure 4.  Deep-QPP, in addition to being more effective than WS-NeurQPP, also
outperforms WS-NeurQPP in terms of training time because of a much smaller
number of parameters (1.9M vs. 4.7M). Figure 5.  Sensitivity of Deep-QPP on
the number of top ($t$) and bottom ($b$) documents to include for interaction
computation (see Section 2.2) on QPP effectiveness. The limiting case of
$(t,b)=(0,0)$ corresponds to the situation when we simply use the interaction
between query terms themselves (i.e. the DRMM baseline). Figure 6.
Sensitivity of Deep-QPP w.r.t. the bin-size, $p$.

##  5\. Related Work

We have already discussed a number of existing QPP methods as a part of the
description of the baselines in Section 4.2. We now outline additional QPP
work, and also cover some recent work on applications of end-to-end learning
in IR. Kurland et. al. (Kurland et al., 2012) showed that the QPP task is
equivalent to ranking clusters of similar documents by their relevance with
respect to a query. Zendel et. al. (Zendel et al., 2019) made use of
alternative expressions of information needs, such as variants of a given
query, to improve QPP effectiveness. The study (Diaz, 2007) reported that a
spatial analysis of vector representations of top-retrieved documents provide
useful cues for improving QPP effectiveness – a hypothesis that our data-
driven model also includes, through the convolutions over the interaction
matrices. Other standard deviation-based approaches, somewhat similar to NQC,
have also been reported to work well for the QPP task (Cummins et al., 2011;
Cummins, 2014). Apart from the weakly supervised neural approach of WS-NeurQPP
(Zamani et al., 2018a), a QPP unsupervised approach that uses cluster
hypothesis of word vectors in an embedded space was proposed in (Roy et al.,
2019).

Recent studies have reported a close association between the findings of
learning to rank (LTR) and QPP studies. It was reported that the set of
features that are useful for LTR also proves beneficial for QPP (Chifu et al.,
2018; Déjean et al., 2020). Moreover, the mechanism of two levels of
interaction (both between queries and documents, and across queries) has also
been reported to be useful for LTR (Mitra et al., 2017).

In addition to DRMM (Guo et al., 2016), other work proposing end-to-end LTR
approaches include (Xiong et al., 2017; Zamani et al., 2018b). The ColBERT
model was recently proposed in (Khattab and Zaharia, 2020), which is a fine-
tuned BERT model (Devlin et al., 2018) using pairwise ranking loss. As a
precursor to end-to-end supervised approaches, unsupervised approaches have
addressed term semantics by using dense word vectors, including (Ganguly et
al., 2015; Roy et al., 2016, 2018) which used skip-gram vectors and the work
of (Yilmaz et al., 2019) which employed BERT.

##  6\. Conclusions and Future work

In this paper, we have proposed Deep-QPP, a data-driven end-to-end neural
framework for the task of query performance prediction in ad-hoc retrieval.
Rather than relying on statistical term weighting heuristics or employing a
weakly-supervised model on those heuristics, our method directly learns from
the data, where the input consists of a set of queries, along with their top-
retrieved sets of documents. The ground-truth for training is comprised of the
true query performance indicators (e.g., measured with AP). Our experiments,
conducted on standard news and Web collections, demonstrated that a data-
driven approach trained on query pairs with known QPP indications (e.g., AP
values) is able to effectively generalize this comparison function for unseen
query pairs. The improvement percentages obtained for Web queries are in fact
higher which suggest that, in future we could potentially use pseudo-relevance
information in the context of query logs, such as clicks and dwell times, to
train QPP models at a large scale.

#### Acknowledgement

The first and the third authors were partially supported by the Science
Foundation Ireland (SFI) grant number SFI/12/RC/2289_P2.

## References

  * (1)
  * luc (2021) 2021\.  Apache Lucene.  https://lucene.apache.org/.  Accessed: 2021-08-13.
  * web (2021) 2021\.  Huggingface Transformers.  https://huggingface.co/transformers/.  Accessed: 2021-08-13.
  * ker (2021) 2021\.  Keras.  https://keras.io/.  Accessed: 2021-08-13.
  * wat (2021) 2021\.  Waterloo Spam Rankings for the ClueWeb09 Dataset.  https://plg.uwaterloo.ca/~gvcormac/clueweb09spam/.  Accessed: 2021-08-13.
  * Asadi et al. (2011) Nima Asadi, Donald Metzler, Tamer Elsayed, and Jimmy Lin. 2011.  Pseudo Test Collections for Learning Web Search Ranking Functions. In _Proc. of the ACM SIGIR ’11_. 1073–1082.
  * Butman et al. (2013) Olga Butman, Anna Shtok, Oren Kurland, and David Carmel. 2013\.  Query-Performance Prediction Using Minimal Relevance Feedback. In _Proc. of ICTIR ’13_. 14–21.
  * Byerly et al. (2020) Adam Byerly, Tatiana Kalganova, and Ian Dear. 2020\.  A Branching and Merging Convolutional Network with Homogeneous Filter Capsules.  _CoRR_ abs/2001.09136 (2020).
  * Carmel et al. (2006) David Carmel, Elad Yom-Tov, Adam Darlow, and Dan Pelleg. 2006\.  What Makes a Query Difficult?. In _Proc. of the 29th ACM SIGIR ’06_. 390–397.
  * Chifu et al. (2018) Adrian-Gabriel Chifu, Léa Laporte, Josiane Mothe, and Md Zia Ullah. 2018.  Query Performance Prediction Focused on Summarized Letor Features. In _Proc. of the 41st ACM SIGIR_. 1177–1180.
  * Christlein et al. (2019) Vincent Christlein, Lukas Spranger, Mathias Seuret, Anguelos Nicolaou, Pavel Král, and Andreas Maier. 2019.  Deep Generalized Max Pooling.  _2019 International Conference on Document Analysis and Recognition (ICDAR)_ (2019), 1090–1096.
  * Clarke et al. (2010) C. Clarke, Nick Craswell, I. Soboroff, and G. Cormack. 2010\.  Overview of the TREC 2010 Web Track. In _TREC_.
  * Cohen et al. (2018) Daniel Cohen, John Foley, Hamed Zamani, James Allan, and W. Bruce Croft. 2018.  Universal Approximation Functions for Fast Learning to Rank: Replacing Expensive Regression Forests with Simple Feed-Forward Networks. In _Proc. of the 41st ACM SIGIR ’18_. 1017–1020.
  * Cronen-Townsend et al. (2002) Steve Cronen-Townsend, Yun Zhou, and W. Bruce Croft. 2002\.  Predicting Query Performance. In _Proc. of the 25th ACM SIGIR ’02_. 299–306.
  * Cummins (2014) Ronan Cummins. 2014\.  Document Score Distribution Models for Query Performance Inference and Prediction.  _ACM Trans. Inf. Syst._ 32, 1, Article 2 (2014).
  * Cummins et al. (2011) Ronan Cummins, Joemon Jose, and Colm O’Riordan. 2011\.  Improved Query Performance Prediction Using Standard Deviation. In _Proc. the 34th ACM SIGIR ’11_. 1089–1090.
  * Dacrema et al. (2019) Maurizio Ferrari Dacrema, Paolo Cremonesi, and Dietmar Jannach. 2019\.  Are We Really Making Much Progress? A Worrying Analysis of Recent Neural Recommendation Approaches.  _CoRR_ abs/1907.06902.
  * Dai et al. (2018) Zhuyun Dai, Chenyan Xiong, Jamie Callan, and Zhiyuan Liu. 2018\.  Convolutional Neural Networks for Soft-Matching N-Grams in Ad-Hoc Search. In _Proc. of the Eleventh ACM WSDM ’18_. 126–134.
  * Dehghani et al. (2017) Mostafa Dehghani, Hamed Zamani, Aliaksei Severyn, Jaap Kamps, and W. Bruce Croft. 2017.  Neural Ranking Models with Weak Supervision. In _Proc. of the 40th ACM SIGIR ’17_. 65–74.
  * Déjean et al. (2020) Sébastien Déjean, Radu Tudor Ionescu, Josiane Mothe, and Md Zia Ullah. 2020.  Forward and backward feature selection for query performance prediction.  _Proceedings of the 35th Annual ACM Symposium on Applied Computing_ (2020).
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  _CoRR_ abs/1810.04805.
  * Diaz (2007) Fernando Diaz. 2007\.  Performance Prediction Using Spatial Autocorrelation. In _Proc. of the 30th ACM SIGIR ’07_. 583–590.
  * Ganguly et al. (2015) Debasis Ganguly, Dwaipayan Roy, Mandar Mitra, and Gareth J.F. Jones. 2015.  Word Embedding Based Generalized Language Model for Information Retrieval. In _Proc. of the 38th ACM SIGIR ’15_. 795–798.
  * Guo et al. (2016) Jiafeng Guo, Yixing Fan, Qingyao Ai, and W. Bruce Croft. 2016\.  A Deep Relevance Matching Model for Ad-Hoc Retrieval. In _Proc. of the 25th ACM CIKM ’16_. 55–64.
  * Hauff (2010) Claudia Hauff. 2010\.  Predicting the Effectiveness of Queries and Retrieval Systems.  _SIGIR Forum_ 44, 1 (Aug. 2010), 88\.
  * Hauff et al. (2008) Claudia Hauff, Djoerd Hiemstra, and Franciska de Jong. 2008\.  A Survey of Pre-Retrieval Query Performance Predictors. In _Proc. of the 17th ACM CIKM ’08_. 1419–1420.
  * Khattab and Zaharia (2020) Omar Khattab and Matei Zaharia. 2020.  _ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT_.  39–48.
  * Kurland et al. (2012) Oren Kurland, Fiana Raiber, and Anna Shtok. 2012\.  Query-Performance Prediction and Cluster Ranking: Two Sides of the Same Coin. In _Proc. of the 21st ACM CIKM ’12_. 2459–2462.
  * Lavrenko and Croft (2001) Victor Lavrenko and W. Bruce Croft. 2001.  Relevance Based Language Models. In _Proc. of SIGIR ’01_. 120–127.
  * Li et al. (2017) Jing Li, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Tao Lian, and Jun Ma. 2017\.  Neural Attentive Session-Based Recommendation. In _Proc. of the ACM CIKM ’17_. 1419–1428.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Distributed Representations of Words and Phrases and Their Compositionality. In _Proc. of the 26th NIPS ’13 - Volume 2_. 3111–3119.
  * Mitra et al. (2017) Bhaskar Mitra, Fernando Diaz, and Nick Craswell. 2017\.  Learning to Match Using Local and Distributed Representations of Text for Web Search. In _Proc. of the 26th WWW ’17_. 1291–1299.
  * Rodríguez-Sánchez et al. (2015) A. Rodríguez-Sánchez, M. Fallah, and A. Leonardis. 2015\.  Editorial: Hierarchical Object Representations in the Visual Cortex and Computer Vision.  _Frontiers in Computational Neuroscience_ 9 (2015).
  * Roy et al. (2018) Dwaipayan Roy, Debasis Ganguly, Sumit Bhatia, Srikanta Bedathur, and Mandar Mitra. 2018\.  Using Word Embeddings for Information Retrieval: How Collection and Term Normalization Choices Affect Performance. In _Proc. of the 27th ACM CIKM’18_. 1835–1838.
  * Roy et al. (2019) Dwaipayan Roy, Debasis Ganguly, Mandar Mitra, and G. Jones. 2019\.  Estimating Gaussian mixture models in the local neighbourhood of embedded word vectors for query performance prediction.  _Information Processing Management_ 56 (2019), 1026–1045.
  * Roy et al. (2016) Dwaipayan Roy, Debasis Ganguly, Mandar Mitra, and Gareth J.F. Jones. 2016.  Word Vector Compositionality Based Relevance Feedback Using Kernel Density Estimation. In _Proc. of CIKM’16_. 1281–1290.
  * Shen et al. (2014) Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. 2014.  A Latent Semantic Model with Convolutional-Pooling Structure for Information Retrieval. In _Proc. of CIKM’14_. 101–110.
  * Shtok et al. (2010) Anna Shtok, Oren Kurland, and David Carmel. 2010.  Using Statistical Decision Theory and Relevance Models for Query-Performance Prediction. In _Proc. of SIGIR’10_. 259–266.
  * Shtok et al. (2012) Anna Shtok, Oren Kurland, David Carmel, Fiana Raiber, and Gad Markovits. 2012.  Predicting Query Performance by Query-Drift Estimation.  _ACM Transactions on Information System_ 30, 2, Article 11 (2012), 35 pages.
  * Smirnova and Vasile (2017) Elena Smirnova and Flavian Vasile. 2017.  Contextual Sequence Modeling for Recommendation with Recurrent Neural Networks. In _Proc. of the 2nd Workshop on DLRS’17_. 2–9.
  * Voorhees (2001) Ellen M. Voorhees. 2001\.  The Philosophy of Information Retrieval Evaluation. In _Proc. of CLEF’01_. 355–370.
  * Wang et al. (2020) Kunfu Wang, Pengyi Zhang, and Jian Su. 2020\.  A Text Classification Method Based on the Merge-LSTM-CNN Model.  1646 (2020), 012110\.
  * Wu and Gu (2015) Haibing Wu and Xiaodong Gu. 2015.  Max-Pooling Dropout for Regularization of Convolutional Neural Networks. In _Proc. of NIPS’15_ , Sabri Arik, Tingwen Huang, Weng Kin Lai, and Qingshan Liu (Eds.). 46–54.
  * Wu et al. (2019) Le Wu, Peijie Sun, Yanjie Fu, Richang Hong, Xiting Wang, and Meng Wang. 2019\.  A Neural Influence Diffusion Model for Social Recommendation. In _Proc. of the 42nd ACM SIGIR’19_. 235–244.
  * Xiong et al. (2017) Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power. 2017.  End-to-End Neural Ad-Hoc Ranking with Kernel Pooling. In _Proc. of the 40th ACM SIGIR’17_. 55–64.
  * Yilmaz et al. (2019) Zeynep Akkalyoncu Yilmaz, S. Wang, W. Yang, Haotian Zhang, and Jimmy J. Lin. 2019\.  Applying BERT to Document Retrieval with Birch. In _Proc. of EMNLP and the 9th International Joint Conference on NLP_. 19–24.
  * Zamani et al. (2018a) Hamed Zamani, W Bruce Croft, and J Shane Culpepper. 2018a.  Neural Query Performance Prediction Using Weak Supervision from Multiple Signals. In _Proc. of the 41st ACM SIGIR’18_. Association for Computing Machinery, New York, NY, USA, 105–114.
  * Zamani et al. (2018b) Hamed Zamani, Bhaskar Mitra, Xia Song, Nick Craswell, and Saurabh Tiwary. 2018b.  Neural Ranking Models with Multiple Document Fields. In _Proc. of the Eleventh ACM WSDM’18_. 700–708.
  * Zendel et al. (2019) Oleg Zendel, Anna Shtok, Fiana Raiber, Oren Kurland, and J. Shane Culpepper. 2019.  Information Needs, Queries, and Query Performance Prediction. In _Proc. of the 42nd ACM SIGIR’19_. 395–404.
  * Zhai and Lafferty (2001) Chengxiang Zhai and John Lafferty. 2001.  A Study of Smoothing Methods for Language Models Applied to Ad Hoc Information Retrieval. In _Proc. of the 24th ACM SIGIR’01_. Association for Computing Machinery, New York, NY, USA, 334–342.
  * Zhou and Croft (2007) Yun Zhou and W. Bruce Croft. 2007.  Query Performance Prediction in Web Search Environments. In _Proc. of the 30th ACM SIGIR’07_. 543–550.


Quasi-Stirling Permutations on Multisets

Sherry H.F. Yan, Lihong Yang, Yunwei Huang, Xue Zhu

Department of Mathematics

Zhejiang Normal University

Jinhua 321004, P.R. China

<EMAIL_ADDRESS>
Abstract. A permutation $\pi$ of a multiset is said to be a quasi-Stirling
permutation if there does not exist four indices $i<j<k<\ell$ such that
$\pi_{i}=\pi_{k}$ and $\pi_{j}=\pi_{\ell}$. Define

$\overline{Q}_{\mathcal{M}}(t,u,v)=\sum_{\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}}t^{des(\pi)}u^{asc(\pi)}v^{plat(\pi)},$

where $\overline{\mathcal{Q}}_{\mathcal{M}}$ denotes the set of quasi-Stirling
permutations on the multiset $\mathcal{M}$, and $asc(\pi)$ (resp. $des(\pi)$,
$plat(\pi)$) denotes the number of ascents (resp. descents, plateaux) of
$\pi$. Denote by $\mathcal{M}^{\sigma}$ the multiset
$\\{1^{\sigma_{1}},2^{\sigma_{2}},\ldots,n^{\sigma_{n}}\\}$, where
$\sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{n})$ is an $n$-composition of
$K$ for positive integers $K$ and $n$. In this paper, we show that
$\overline{Q}_{\mathcal{M}^{\sigma}}(t,u,v)=\overline{Q}_{\mathcal{M}^{\tau}}(t,u,v)$
for any two $n$-compositions $\sigma$ and $\tau$ of $K$. This is accomplished
by establishing an $(asc,des,plat)$-preserving bijection between
$\overline{\mathcal{Q}}_{\mathcal{M}^{\sigma}}$ and
$\overline{\mathcal{Q}}_{\mathcal{M}^{\tau}}$. As applications, we obtain
generalizations of several results for quasi-Stirling permutations on
$\mathcal{M}=\\{1^{k},2^{k},\ldots,n^{k}\\}$ obtained by Elizalde and solve an
open problem posed by Elizalde.

Keywords: quasi-Stirling permutation, bijection.

AMS Subject Classifications: 05A05, 05C30

##  1 Introduction

Let $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$ be a multiset
where $k_{i}$ is the number of occurrences of $i$ in $\mathcal{M}$ and
$k_{i}\geq 1$. A permutation $\pi$ of a multiset $\mathcal{M}$ is said to be a
Stirling  permutation if $i<j<k$ and $\pi_{i}=\pi_{k}$, then
$\pi_{j}>\pi_{i}$. Stirling permutations were originally introduced by Gessel
and Stanley [7] in the case of the multiset
$\mathcal{M}=\\{1^{2},2^{2},\ldots,n^{2}\\}$. Park [9, 10] and Liu [8] studied
the distribution of various statistics over Stirling permutations on
$\mathcal{M}=\\{1^{k},2^{k},\ldots,n^{k}\\}$. Brenti [2, 3] and Dzhumadil’daev
and Yeliussizov [5] investigated the descent polynomials of Stirling
permutations on an arbitrary multiset. In analogy to Stirling permutations,
Archer, Gregory, Pennington and Slayden [1] introduced quasi-Stirling
permutations. A permutation $\pi$ of a multiset is said to be a quasi-Stirling
permutation if there does not exist four indices $i<j<k<\ell$ such that
$\pi_{i}=\pi_{k}$ and $\pi_{j}=\pi_{\ell}$. For a multiset $\mathcal{M}$,
denote by $\overline{\mathcal{Q}}_{\mathcal{M}}$ the set of quasi-Stirling
permutations of $\mathcal{M}$. For example, if
$\mathcal{M}=\\{1^{2},2^{2}\\}$, we have
$\overline{\mathcal{Q}}_{\mathcal{M}}=\\{1221,2112,1122,2211\\}.$

For a permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$, an index $i$, $0\leq
i\leq n$, is called an ascent (resp. a descent, a plateau) of $\pi$ if
$\pi_{i}<\pi_{i+1}$ (resp. $\pi_{i}>\pi_{i+1}$, $\pi_{i}=\pi_{i+1}$) with the
convention $\pi_{0}=\pi_{n+1}=0$. Let $asc(\pi)$ (resp. $des(\pi)$,
$plat(\pi)$) denote the number of ascents (resp. descents, plateaux) of $\pi$.
In [4], Bona proved that the three statistics $asc$, $plat$ and $des$ are
equidistributed over Stirling permutations on
$\mathcal{M}=\\{1^{2},2^{2},\ldots,n^{2}\\}$. Define

$\overline{Q}_{\mathcal{M}}(t,u,v)=\sum_{\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}}t^{des(\pi)}u^{asc(\pi)}v^{plat(\pi)}.$

The polynomial $\overline{Q}_{\mathcal{M}}(t,1,1)$ is called the quasi-
Stirling polynomial  on the multiset $\mathcal{M}$. By employing generating
function arguments, Elizalde [6] derived that

$\sum_{m=0}^{\infty}{m^{n}\over n+1}{n+m\choose
m}t^{m}={\overline{Q}_{\mathcal{M}}(t,1,1)\over(1-t)^{2n+1}},$ (1.1)

when $\mathcal{M}=\\{1^{2},2^{2},\ldots,n^{2}\\}$ and asked for a
combinatorial proof. Recently, Yan and Zhu [11] provided such a combinatorial
proof and further derived that

$\sum_{m=0}^{\infty}{m^{n}\over K-n+1}{K-n+m\choose
m}t^{m}={\overline{Q}_{\mathcal{M}}(t,1,1)\over(1-t)^{K+1}},$ (1.2)

where $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$ and
$K=k_{1}+k_{2}+\ldots+k_{n}$ with $k_{i}\geq 1$.

For positive integers $K$ and $n$, let
$\sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{n})$ be an $n$-composition of
$K$. Denote by $\mathcal{M}^{\sigma}$ the multiset
$\\{1^{\sigma_{1}},2^{\sigma_{2}},\ldots,n^{\sigma_{n}}\\}$. By (1.2), for any
two $n$-compositions $\sigma$ and $\tau$ of $K$, we have
$\overline{Q}_{\mathcal{M}^{\sigma}}(t,1,1)=\overline{Q}_{\mathcal{M}^{\tau}}(t,1,1)$.
In this paper, we get the following generalizations.

###### Theorem 1.1

Let $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$,
$\mathcal{M^{\prime}}=\\{1^{K-n+1},2,3,\ldots,n\\}$ and
$K=k_{1}+k_{2}+\ldots+k_{n}$ with $k_{i}\geq 1$. There is a bijection $\Phi$
between $\overline{\mathcal{Q}}_{\mathcal{M}}$ and
$\overline{\mathcal{Q}}_{\mathcal{M^{\prime}}}$ such that for any
$\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$, we have

$(asc,des,plat)\pi=(asc,des,plat)\Phi(\pi).$

Consequently, we have
$\overline{Q}_{\mathcal{M}}(t,u,v)=\overline{Q}_{\mathcal{M^{\prime}}}(t,u,v)$.

The following result follows immediately from Theorem 1.1.

###### Theorem 1.2

Let $K$ and $n$ be positive integers. For any two $n$-compositions $\sigma$
and $\tau$ of $K$, there exists a bijection between
$\overline{\mathcal{Q}}_{\mathcal{M}^{\sigma}}$ and
$\overline{\mathcal{Q}}_{\mathcal{M}^{\tau}}$ which preserves the number of
ascents, descents and plateaux. Consequently, we have
$\overline{Q}_{\mathcal{M}^{\sigma}}(t,u,v)=\overline{Q}_{\mathcal{M}^{\tau}}(t,u,v)$.

Let $\mathcal{J}_{n,r}$ be the set of permutations
$\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n-r}$ where each $\sigma_{i}\in[n]$
and $\sigma_{i}\neq\sigma_{j}$ for all $1\leq i,j\leq n-r$. Recall that for a
permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$, an index $i$ is said to be an
excedance of $\pi$ if $\pi_{i}>i$. Let $exc(\pi)$ denote the number of
excedances of $\pi$. By employing generating function arguments, Elizalde [6]
derived that for $\mathcal{M}=\\{1^{2},2^{2},\ldots,n^{2}\\}$, quasi-Stirling
permutations $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with $des(\pi)=d+1$
are equinumerous with permutations $\sigma\in\mathcal{J}_{2n,n+1}$ with
$exc(\sigma)=d$, and asked for a combinatorial proof. Relying on Theorem 1.1,
we present such a combinatorial proof and further extend Elizalde’s result to
an arbitrary multiset.

###### Theorem 1.3

Let $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$ and
$K=k_{1}+k_{2}+\ldots+k_{n}$ with $k_{i}\geq 1$. There is a bijection between
quasi-Stirling permutations $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with
$des(\pi)=d+1$ and permutations $\sigma\in\mathcal{J}_{K,K-n+1}$ with
$exc(\sigma)=d$.

By establishing a bijection between quasi-Stirling permutations and edge-
labeled plane (ordered) rooted trees, Elizalde [6] confirmed a conjecture
posed by Archer et al. [1] which asserts that the number of
$\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with $des(\pi)=n$ is equal to
$(n+1)^{n-1}$ for $\mathcal{M}=\\{1^{2},2^{2},\ldots,n^{2}\\}$. He further
proved that the number of $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with
$des(\pi)=n$ is equal to $((k-1)n+1)^{n-1}$ for
$\mathcal{M}=\\{1^{k},2^{k},\ldots,n^{k}\\}$ and $k\geq 2$. As an application
of Theorem 1.1, we obtain the following generalization of Elizalde’s result.

###### Corollary 1.4

Let $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$ and
$K=k_{1}+k_{2}+\ldots+k_{n}$ with $k_{i}\geq 1$. Then the number of
permutations $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with $des(\pi)=n$ is
equal to $(K-n+1)^{n-1}$.

Denote by $\mathcal{S}_{n}$ the set of all permutations of $[n]$. The
polynomial

$A_{n}(t,u)=\sum_{\pi\in\mathcal{S}_{n}}t^{des(\pi)}u^{asc(\pi)}$

is called the bivariate Eulerian polynomial. Define

$\widetilde{A}(t,u;z)=1+\sum_{n\geq 1}A_{n}(t,u){z^{n}\over n!}.$

In [6], Elizalde derived that

$\overline{Q}_{\mathcal{M}}(t,u,v)={n!\over(k-1)n+1}[z^{n}](\widetilde{A}(t,u;z)-1+v)^{(k-1)n+1}.$
(1.3)

for $\mathcal{M}=\\{1^{k},2^{k},\ldots,n^{k}\\}$. Based on Theorem 1.1, we
extend (1.3) to an arbitrary multiset.

###### Corollary 1.5

Let $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$ and
$K=k_{1}+k_{2}+\ldots+k_{n}$ with $k_{i}\geq 1$. Then

$\overline{Q}_{\mathcal{M}}(t,u,v)={n!\over
K-n+1}[z^{n}](\widetilde{A}(t,u;z)-1+v)^{K-n+1}.$

The rest of this paper is organized as follows. In Section 2, we shall
establish the bijection $\Phi$, thereby proving Theorem 1.1. As an application
of Theorem 1.1, we get the enumeration of quasi-Stirling permutations with $n$
descents. Section 3 is devoted to the proof of Theorem 1.3. In Section 4,
relying on Theorem 1.1, we express the polynomial
$\overline{Q}_{\mathcal{M}}(t,u,v)$ in terms of the generating function
$\widetilde{A}(t,u;z)$, thereby proving Corollary 1.5.

##  2  Proof of Theorem 1.1

The objective of this section is to establish the bijection $\Phi$ stated in
Theorem 1.1. Recall that an ordered tree is a tree with one designated vertex,
which is called the root, and the subtrees of each vertex are linearly
ordered. In an ordered tree $T$, the level of a vertex $v$ in $T$ is defined
to be the length of the unique path from the root to $v$. A vertex $v$ is said
to be at odd level (resp. at even level) if the level of $v$ is odd (resp.
even). In a rooted tree, the vertex $v$ is a descendant of the vertex $u$ if
$u$ lies on the path from $v$ to the root. In order to prove (1.2), Yan and
Zhu [11] introduced a new class of ordered labeled trees $T$ verifying the
following properties:

  * (i)

the vertices are labeled by the elements of the multiset
$\\{0\\}\cup\mathcal{M}$, where
$\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$ with $k_{i}\geq 1$;

  * (ii)

the root is labeled by $0$;

  * (iii)

for a vertex $v$ at odd level, if $v$ is labeled by $i$, then $v$ has exactly
$k_{i}-1$ children and the children of $v$ have the same label as that of $v$
in $T$.

Let $\mathcal{T}_{\mathcal{M}}$ denote the set of such ordered labeled trees.
For example, a tree $T\in\mathcal{T}_{\mathcal{M}}$ with
$\mathcal{M}=\\{1,2,3^{2},4,5^{3},6,7^{2}\\}$ is illustrated in Figure 1.

Figure 1:  A tree $T\in\mathcal{T}_{\mathcal{M}}$ with
$\mathcal{M}=\\{1,2,3^{2},4,5^{3},6,7^{2}\\}$.

The number of cyclic descents of a sequence $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$
is defined to be

$cdes(\pi)=|\\{i\mid\pi_{i}>\pi_{i+1}\\}|$

with the convention $\pi_{n+1}=\pi_{1}$. Similarly, the number of cyclic
ascents of a sequence $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$ is defined to be

$casc(\pi)=|\\{i\mid\pi_{i}<\pi_{i+1}\\}|$

with the convention $\pi_{n+1}=\pi_{1}$.

In an ordered labeled tree $T$, let $u$ be a vertex of $T$. Suppose that $u$
has $\ell$ children $v_{1},v_{2},\ldots,v_{\ell}$ listed from left to right.
The number of cyclic descents (resp. cyclic ascents) of $u$, denoted by
$cdes(u)$ (resp. $casc(u)$), is defined to be the number
$cdes(uv_{1}v_{2}\ldots v_{\ell})$ (resp. $casc(uv_{1}v_{2}\ldots v_{\ell})$).
The number of cyclic descents and cyclic ascents of $T$ are defined to be

$cdes(T)=\sum_{u\in V(T)}cdes(u),$

and

$casc(T)=\sum_{u\in V(T)}casc(u),$

where $V(T)$ denotes the vertex set of $T$. Denote by $eleaf(T)$ the number of
leaves at even level. For example, if we let $T$ be a tree as shown in Figure
1, we have $casc(T)=6$, $cdes(T)=5$ and $eleaf(T)=1$. Let $\pi$ be a
permutation, the leftmost (resp. rightmost) entry of $\pi$ is denoted by
$first(\pi)$ (resp. $last(\pi)$). Similarly, for an ordered labeled tree $T$,
we denote by $first(T)$ (resp. $last(T)$) the leftmost (resp. rightmost) child
of the root.

In order to prove (1.2), Yan and Zhu [11] established a bijection $\phi$
between $\mathcal{T}_{\mathcal{M}}$ and
$\overline{\mathcal{Q}}_{\mathcal{M}}$. First we give an overview of the
bijection $\phi$. If $T$ has only one vertex, let $\phi(T)=\epsilon$, where
$\epsilon$ denotes the empty permutation. Otherwise, suppose that
$first(T)=r$.

Case 1. The leftmost child of the root is a leaf. Let $T_{0}$ be the tree
obtained from $T$ by removing the leftmost child of the root together with the
edge incident to it. Define $\phi(T)=r\phi(T_{0})$.

Case 2. The leftmost child of the root has $k$ children. For $1\leq i\leq k$,
let $T_{i}$ be the subtree rooted at the $i$-th child of the leftmost child of
the root. Denote by $T^{\prime}_{i}$ the tree obtained from $T_{i}$ by
relabeling its root by $0$. Let $T_{0}$ be the tree obtained from $T$ by
removing all the subtrees $T_{1}$, $T_{2}$, $\ldots,$ $T_{k}$ and all the
vertices labeled by $r$ together with the edges incident to them. Define
$\phi(T)=r\phi(T^{\prime}_{1})r\phi(T^{\prime}_{2})\ldots
r\phi(T^{\prime}_{k})r\ \phi(T_{0})$.

For instance, let $T$ be a tree illustrated in Figure 1. By applying the map
$\phi$, we have $\phi(T)=27475633515$.

In [11], Yan and Zhu proved that the bijection $\phi$ has the following
property.

###### Theorem 2.1

( [11])  For any nonempty multiset $\mathcal{M}$,the map $\phi$ is a bijection
between $\mathcal{T}_{\mathcal{M}}$ and $\overline{\mathcal{Q}}_{\mathcal{M}}$
such that

$(cdes,first,last)T=(des,first,last)\phi(T)$

for any $T\in\mathcal{T}_{\mathcal{M}}$.

###### Theorem 2.2

For any nonempty multiset $\mathcal{M}$, the map $\phi$ induces a bijection
between $\mathcal{T}_{\mathcal{M}}$ and $\overline{\mathcal{Q}}_{\mathcal{M}}$
such that

$(cdes,casc,eleaf,first,last)T=(des,asc,plat,first,last)\phi(T)$

for any $T\in\mathcal{T}_{\mathcal{M}}$.

Proof. By theorem 2.1, it remains to show that
$(casc,eleaf)T=(asc,plat)\phi(T)$. We shall prove the statement by induction
on the cardinality of the multiset $\mathcal{M}$. Suppose that $first(T)=r$.
If $|\mathcal{M}|=1$, then $T$ consists of the root $0$ and its child $r$.
According to the construction of $\phi$, we have $\phi(T)=r$. Then it is easy
to check that $casc(T)=asc(\phi(T))=1$ and $eleaf(T)=plat(\phi(T))=0$. Assume
that $(casc,eleaf)T=(asc,plat)\phi(T)$ for any
$T\in\mathcal{T}_{\mathcal{M}^{\prime}}$ with
$|\mathcal{M}^{\prime}|<|\mathcal{M}|$. We proceed to show that
$(casc,eleaf)T=(asc,plat)\phi(T)$ for any $T\in\mathcal{T}_{\mathcal{M}}$. We
have two cases.

Case 1. The leftmost child of the root is a leaf. In this case, we have
$\phi(T)=r\phi(T_{0})$. It is routine to check that

$casc(T)=casc(T_{0})+\chi(r<first(T_{0})).$

Here $\chi(S)=1$ if the statement $S$ is true, and $\chi(S)=0$ otherwise. Then
by induction hypothesis, we have

$\begin{array}[]{lll}casc(T)&=&casc(T_{0})+\chi(r<first(T_{0}))\\\
&=&asc(\phi(T_{0}))+\chi(r<first(\phi(T_{0})))\\\ &=&asc(\phi(T)).\end{array}$

Similarly, we have $eleaf(T)=eleaf(T_{0}).$ and
$plat(\phi(T_{0}))=plat(\phi(T))$. Again by induction hypothesis, we have
$eleaf(T)=eleaf(T_{0})=plat(\phi(T_{0}))=plat(\phi(T))$.

Case 2. The leftmost child of the root has $k$ children. Then we have
$\phi(T)=r\phi(T^{\prime}_{1})r\phi(T^{\prime}_{2})\ldots
r\phi(T^{\prime}_{k})r\ \phi(T_{0})$. Define

$\mathcal{I}=\\{i\mid|T_{i}|>1,1\leq i\leq k\\},$

where $|T_{i}|$ denotes the number of vertices of $T_{i}$.

Subcase 2.1. $|T_{0}|>1$. It is easily seen that

$casc(T)=casc(T_{0})+\chi(r<first(T_{0}))+\sum_{i\in\mathcal{I}}\big{(}casc(T^{\prime}_{i})-1+\chi(r<first(T^{\prime}_{i})\big{)}+\chi(r>last(T^{\prime}_{i})),$

and $asc(\phi(T))$ is given by

$asc(\phi(T_{0}))+\chi(r<first(\phi(T_{0})))+\sum_{i\in\mathcal{I}}\big{(}asc(\phi(T^{\prime}_{i}))-1+\chi(r<first(\phi(T^{\prime}_{i}))\big{)}+\chi(r>last(\phi(T^{\prime}_{i}))).$

By induction hypothesis, it is easy to verify that $casc(T)=asc(\phi(T))$.
Similarly, we have

$eleaf(T)=eleaf(T_{0})+|[k]\setminus\mathcal{I}|+\sum_{i\in\mathcal{I}}eleaf(T^{\prime}_{i})$

and

$plat(\phi(T))=plat(\phi(T_{0}))+|[k]\setminus\mathcal{I}|+\sum_{i\in\mathcal{I}}plat(\phi(T^{\prime}_{i})).$

Again by induction hypothesis, we have $eleaf(T)=plat(\phi(T))$.

Subcase 2.2. $|T_{0}|=1$. It is easily seen that

$casc(T)=1+\sum_{i\in\mathcal{I}}\big{(}casc(T^{\prime}_{i})-1+\chi(r<first(T^{\prime}_{i})\big{)}+\chi(r>last(T^{\prime}_{i})),$

and $asc(\phi(T))$ is given by

$1+\sum_{i\in\mathcal{I}}\big{(}asc(\phi(T^{\prime}_{i}))-1+\chi(r<first(\phi(T^{\prime}_{i}))\big{)}+\chi(r>last(\phi(T^{\prime}_{i}))).$

By induction hypothesis, it is easy to verify that $casc(T)=asc(\phi(T))$.
Similarly, we have

$eleaf(T)=|[k]\setminus\mathcal{I}|+\sum_{i\in\mathcal{I}}eleaf(T^{\prime}_{i})$

and

$plat(\phi(T))=|[k]\setminus\mathcal{I}|+\sum_{i\in\mathcal{I}}plat(\phi(T^{\prime}_{i})).$

Again by induction hypothesis, we have $eleaf(T)=plat(\phi(T))$, completing
the proof.

Let $T\in\mathcal{T}_{\mathcal{M}}$. A vertex $i$ of $T$ is said be be even
(resp. odd) if it is at even (resp. odd) level of $T$.

###### Theorem 2.3

Let $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$ with $k_{i}\geq
1$ for all $1\leq i\leq n$. Suppose that $k_{j}>1$ for some $j\geq 2$. Let
$M_{j}$ be the multiset obtained from $\mathcal{M}$ by changing one element
$j$ to $j-1$, that is,
$\mathcal{M}_{j}=\\{1^{k_{1}},2^{k_{2}},\ldots,(j-1)^{k_{j-1}+1},j^{k_{j}-1},\ldots,n^{k_{n}}\\}$.
Then there is a bijection $\psi_{j}$ between $\mathcal{T}_{\mathcal{M}}$ and
$\mathcal{T}_{\mathcal{M}_{j}}$ such that

$(cdes,casc,eleaf)T=(cdes,casc,eleaf)\psi_{j}(T)$

for any $T\in\mathcal{T}_{\mathcal{M}}$.

Proof. First we give a description of the map $\psi_{j}$ from
$\mathcal{T}_{\mathcal{M}}$ to $\mathcal{T}_{\mathcal{M}_{j}}$. Let
$T\in\mathcal{T}_{\mathcal{M}}$. In the following, we demonstrate how to
construct $\psi_{j}(T)$.

Case 1. The odd vertex $j-1$ is a descendant of the rightmost even vertex $j$.
Suppose that rightmost even vertex $j$ has exactly $k$ children, say
$x_{1},x_{2},\ldots,x_{k}$, listed from left to right. Let $T_{p}$, $1\leq
p\leq k_{j-1}-1$, be the subtree rooted at the $p$-th even vertex $j-1$
(counting from left to right). Similarly, let $T^{\prime}_{q}$, $1\leq q\leq
k_{j}-2$, be the subtree rooted at the $q$-th even vertex $j$ (counting from
left to right) . First we remove the subtree $T_{p}$ for all $1\leq p\leq
k_{j-1}-1$ and the subtree $T^{\prime}_{q}$ for all $1\leq q\leq k_{j}-2$ from
$T$. Then, relabel the rightmost even vertex $j$ by $j-1$, and relabel the odd
vertex $j$ (resp. $j-1$) by $j-1$ (resp. $j$). Then we attach $T_{p}$ to the
odd vertex $j-1$ as its $p$-th subtree (counting from left to right) for all
$1\leq p\leq k_{j-1}-1$, and attach $T^{\prime}_{q}$ to the odd vertex $j$ as
its $q$-th subtree (counting from left to right) for all $1\leq q\leq
k_{j}-2$. Let $T^{*}$ be the resulting tree. In the following, we demonstrate
how to get a tree $\psi_{j}(T)$ from $T^{*}$.

Subcase 1.1. If $x_{\ell}=j-1$ for some $1\leq\ell\leq k$, then from the
construction of $T^{*}$, the odd vertex $j$ is the $\ell$-th child of the
rightmost even vertex $j-1$ in $T^{*}$. Let $\psi_{j}(T)$ be the tree obtained
from $T^{*}$ by rearranging the subtrees of the rightmost even vertex $j-1$
such that the odd vertices
$x_{\ell+1},\ldots,x_{k},j,x_{1},x_{2},\ldots,x_{\ell-1}$ are its children
listed from left to right. See Figure 2 for an example.

Figure 2: An example of Subcase 1.1.

Subcase 1.2. If $x_{\ell}\neq j-1$ for all $1\leq\ell\leq k$, set
$\psi_{j}(T)=T^{*}$. See Figure 3 for an example.

Figure 3: An example of Subcase 1.2.

Case 2. Otherwise, let $T^{\prime}$ be the subtree rooted at rightmost even
vertex $j$. Remove the subtree $T^{\prime}$ from $T$, relabel the root of
$T^{\prime}$ by $j-1$ and attach it to the odd vertex $j-1$ as its rightmost
subtree. Let $\psi_{j}(T)$ be the resulting tree. See Figure 4 for an example.

It is routine to check that $\psi_{j}(T)\in\mathcal{T}_{\mathcal{M}_{j}}$ and
we have

$(cdes,casc,eleaf)T=(cdes,casc,eleaf)\psi_{j}(T)$

as desired.

Conversely, given a tree $T\in\mathcal{T}_{\mathcal{M}_{j}}$, we can recover a
tree $T^{\prime}\in\mathcal{T}_{\mathcal{M}}$ by the following procedure. If
the odd vertex $j$ is a descendant of rightmost even vertex $j-1$, one can
generate a tree $T^{\prime}\in\mathcal{T}_{\mathcal{M}}$ by reversing the
procedure in Case 1. Otherwise, we can recover a tree
$T^{\prime}\in\mathcal{T}_{\mathcal{M}}$ by reversing the procedure in Case 2.
So the construction of the map $\psi_{j}$ is reversible and hence the map
$\psi_{j}$ is a bijection. This completes the proof.

Figure 4:  An example of Case 2.

###### Theorem 2.4

Let $\mathcal{M}=\\{1^{k_{1}},2^{k_{2}},\ldots,n^{k_{n}}\\}$,
$\mathcal{M^{\prime}}=\\{1^{K-n+1},2,3,\ldots,n\\}$ and
$K=k_{1}+k_{2}+\ldots+k_{n}$ with $k_{i}\geq 1$. There is a bijection $\Psi$
between $\mathcal{T}_{\mathcal{M}}$ and $\mathcal{T}_{\mathcal{M}^{\prime}}$
such that

$(cdes,casc,eleaf)T=(cdes,casc,eleaf)\Psi(T)$

for any $T\in\mathcal{T}_{\mathcal{M}}$.

Proof. Let $T\in\mathcal{T}_{\mathcal{M}}$. If $k_{i}=1$ for all $2\leq i\leq
n$, then we set $\Psi(T)=T$. Otherwise, find the largest integer $j$ with
$j\geq 2$ such that $k_{j}>2$. By applying the map $\psi_{j}$ to $T$, we
generate a tree $T^{(1)}=\psi_{j}(T)\in\mathcal{T}_{\mathcal{M}_{j}}$, where
$M_{j}$ is the multiset obtained from $\mathcal{M}$ by changing one element
$j$ to $j-1$. For $i=1,2,\ldots,n$, denote by $k^{\prime}_{i}$ the number of
occurrences of $i$ in $\mathcal{M}_{j}$. If $k^{\prime}_{i}=1$ for all $2\leq
i\leq n$, we stop and set $\Psi(T)=\psi_{j}(T)$. Otherwise, find the largest
integer $\ell$ with $\ell\geq 2$ such that $k^{\prime}_{\ell}>2$. By applying
the map $\psi_{\ell}$ to $T^{(1)}$, we generate a tree
$T^{(2)}=\psi_{\ell}(T^{(1)})$. We continue this process until we reach a tree
$T^{\prime}\in T_{\mathcal{M^{\prime}}}$ and set $\Psi(T)=T^{\prime}$. By
Theorem 2.3, the map $\Psi$ is a bijection between between
$\mathcal{T}_{\mathcal{M}}$ and $\mathcal{T}_{\mathcal{M}^{\prime}}$
satisfying that

$(cdes,casc,eleaf)T=(cdes,casc,eleaf)\Psi(T)$

for any $T\in\mathcal{T}_{\mathcal{M}}$ as desired. This completes the proof.

Proof of Theorem 1.1. By Theorems 2.2 and 2.4, the map
$\Phi=\phi\circ\Psi\circ\phi^{-1}$ serves as a bijection between
$\overline{\mathcal{Q}}_{\mathcal{M}}$ and
$\overline{\mathcal{Q}}_{\mathcal{M^{\prime}}}$. Moreover, we have

$(asc,des,plat)\pi=(asc,des,plat)\Phi(\pi)$

for any $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$, completing the proof.

In the following, we aim to prove Corollary 1.4. The following observation
will play an essential role in the proof of Corollary 1.4.

###### Observation 2.5

For positive integers $m$ and $n$, let $\mathcal{M}=\\{1^{m},2,3,\ldots,n\\}$.
For any permutation $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with
$des(\pi)=n$, $\pi$ can be uniquely decomposed as

$\pi=\pi^{(1)}1\pi^{(2)}1\ldots\pi^{(m)}1$

where each $\pi^{(i)}$ is a (possibly empty) decreasing sequence.

Proof of Corollary 1.4. By Theorem 1.1, it suffices to get the enumeration of
permutations $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}^{\prime}}$ with
$des(\pi)=n$, where $M^{\prime}=\\{1^{K-n+1},2,3,\ldots,n\\}$. By Observation
2.5, one can easily verify that the number of permutations
$\pi\in\overline{\mathcal{Q}}_{\mathcal{M}^{\prime}}$ with $des(\pi)=n$ is
given by $(K-n+1)^{n-1}$, completing the proof.

##  3 Proof of Theorem 1.3

In this section, we shall establish a bijection between quasi-Stirling
permutations $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with $des(\pi)=d+1$
and permutations $\sigma\in\mathcal{J}_{K,K-n+1}$ with $exc(\sigma)=d$. To
this end, we introduce the disjoint path and cycle notation of a permutation
$\sigma\in\mathcal{J}_{n+m-1,m}$. Let
$\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n-1}\in\mathcal{J}_{n+m-1,m}$. A
sequence $(a_{1},a_{2},\ldots,a_{k})$ is called a cycle  of $\sigma$ if
$\sigma_{a_{i}}=a_{i+1}$ for all $1\leq i\leq k$ with the convention
$a_{k+1}=a_{1}$. A sequence $<a_{1},a_{2},\ldots a_{k}>$ is called a path  of
$\sigma$ if $\sigma_{a_{i}}=a_{i+1}$ for all $1\leq i\leq k-1$ and $a_{k}\geq
n$. Then $\sigma$ can be decomposed into a disjoint union of distinct paths
$P_{1},P_{2},\ldots,P_{s}$ and distinct cycles $C_{1},C_{2},\ldots,C_{t}$,
written $\sigma=P_{1}P_{2}\ldots P_{s}C_{1}C_{2}\ldots C_{t}$. Such a
decomposition is called the disjoint path and cycle notation of a permutation
$\sigma$. For example, let $\sigma=7816293(11)\in\mathcal{J}_{11,3}$, the
disjoint path and cycle notation of $\sigma$ is given by
$<4,6,9><10><5,2,8,11>(1,7,3)$. Of course this representation of $\sigma$ in
disjoint path and cycle notation is not unique. We also have for instance
$\sigma=<10><4,6,9><5,2,8,11>(7,3,1)$. We can define a standard representation
by requiring that (a) the paths are written in increasing order of their
largest element, (b) each cycle is written with its smallest element first,
and (c) the cycles are written in decreasing order of their smallest element.
One can easily check that if $\sigma=P_{1}P_{2}\ldots P_{s}C_{1}C_{2}\ldots
C_{t}$ written in standard disjoint path and cycle notation, then we have

$exc(\sigma)=\sum_{i=1}^{s}(asc(P_{i})-1)+\sum_{j=1}^{t}(asc(C_{j})-1).$ (3.1)

For instance, if $\sigma=<4,6,9><10><5,2,8,11>(1,7,3)$, then
$exc(\sigma)=2+0+2+1=5$.

###### Lemma 3.1

For positive integers $n$ and $m$, let
$\mathcal{M}=\\{1,2,\ldots,n-1,n^{m}\\}$. There exists a bijection $\chi$
between quasi-Stirling permutations
$\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ and permutations $\sigma\in
J_{n+m-1,m}$ such that for any $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$,
we have $asc(\pi)=exc(\sigma)+1$.

Proof. First we describe a map $\chi$ from
$\overline{\mathcal{Q}}_{\mathcal{M}}$ to $J_{n+m-1,m}$. Let
$\pi=\pi_{1}\pi_{2}\ldots\pi_{n+m-1}\in\overline{\mathcal{Q}}_{\mathcal{M}}$.
Then $\pi$ can be uniquely decomposed as $\pi=\pi^{\prime}\pi^{\prime\prime}$
where there is no $n$ in $\pi^{\prime\prime}$. Now we can generate a
permutation $\chi(\pi)$ in standard disjoint path and cycle notation by the
following procedure.

  * •

Insert a “$>$” after each $n$ and insert a “$<$” where appropriate in
$\pi^{\prime}$;

  * •

Insert a “$($” before each left-to-right minimum of $\pi^{\prime\prime}$ and
insert a “$)$” where appropriate;

  * •

Replace $m$’s occurrences of $n$ by $n,n+1,\ldots,n+m-1$ from left to right.

It is easily seen that the resulting permutation
$\chi(\pi)\in\mathcal{J}_{n+m-1,m}$. By (3.1), we have
$asc(\pi)=exc(\chi(\pi))+1$. For example, let $\pi=46995289173$, we have
$\chi(\pi)=<4,6,9><10><5,2,8,11>(1,7,3)$ and $asc(\pi)=exc(\chi(\pi))+1=6$.

In order to show that the map $\chi$ is a bijection, we describe a map
$\chi^{\prime}$ from $J_{n+m-1,m}$ to $\overline{\mathcal{Q}}_{\mathcal{M}}$.
Let $\sigma\in J_{n+m-1,m}$ written in standard path and cycle notation. We
can generate a permutation $\chi^{\prime}(\sigma)$ by replacing each element
larger than $n$ by $n$ and erasing the parentheses and angle brackets. It is
easily seen that
$\chi^{\prime}(\sigma)\in\overline{\mathcal{Q}}_{\mathcal{M}}$. Moreover, the
standard path and cycle notation ensures that the maps $\chi$ and
$\chi^{\prime}$ are inverses of each other, and hence the map $\chi$ is a
bijection as desired. This completes the proof.

###### Lemma 3.2

For positive integers $n$ and $m$, let $\mathcal{M}=\\{1^{m},2,\ldots,n\\}$.
There exists a bijection $\delta$ between quasi-Stirling permutations
$\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ and permutations $\sigma\in
J_{n+m-1,m}$ such that for any $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$,
we have $des(\pi)=exc(\sigma)+1$.

Proof. Let $\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ and
$M^{\prime}=\\{1,2,\ldots,n^{m}\\}$. First, we generate a permutation
$\pi^{\prime}\in\overline{\mathcal{Q}}_{\mathcal{M}^{\prime}}$ from $\pi$ by
replacing each element $i$ with $n+1-i$. It is apparent that we have
$des(\pi)=asc(\pi^{\prime})$. Then, by applying the map $\chi$ to
$\pi^{\prime}$, we obtain a permutation $\chi(\pi^{\prime})\in J_{n+m-1,m}$.
Set $\delta(\pi)=\chi(\pi^{\prime})$. By Lemma 3.1, one can easily verify that

$des(\pi)=asc(\pi^{\prime})=exc(\chi(\pi^{\prime}))+1=exc(\delta(\pi))+1.$

Since $\chi$ is a bijection, the map $\delta$ is a bijection as desired,
completing the proof.

Proof of Theorem 1.3. By Theorem 1.1 and Lemma 3.2, the map $\delta\circ\Phi$
serves as a bijection between quasi-Stirling permutations
$\pi\in\overline{\mathcal{Q}}_{\mathcal{M}}$ with $des(\pi)=d+1$ and
permutations $\sigma\in\mathcal{J}_{K,K-n+1}$ with $exc(\sigma)=d$. This
completes the proof.

##  4 Proof of Corollary 1.5

For positive integers $m$ and $n$, let $\mathcal{P}_{m,n}$ denote the set of
$m$-tuples $(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(m)})$ where each $\pi^{(i)}$ is
a (possibly empty) permutation, $\pi^{(i)}\cap\pi^{(j)}=\emptyset$ for all
$1\leq i<j\leq m$ and $\cup_{i=1}^{m}\pi^{(i)}=[n]$. For
$\alpha=(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(m)})\in\mathcal{P}_{m,n}$, let
$\mathcal{E}(\alpha)=\\{i\mid\pi^{(i)}=\epsilon\\}$. Define

$P_{m,n}(t,u,v)=\sum_{\alpha=(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(m)})\in\mathcal{P}_{m,n}}v^{|\mathcal{E}(\alpha)|}\prod_{i\in[m]\setminus\mathcal{E}(\alpha)}t^{des(\pi^{(i)})}u^{asc(\pi^{(i)})}.$

From the definition of $\widetilde{A}(t,u;z)$, it follows that

$P_{m,n}(t,u,v)=n![z^{n}](\widetilde{A}(t,u;z)-1+v)^{m}.$ (4.1)

For $1\leq j\leq m$, denote by $\mathcal{P}^{j}_{n,m}$ the set of $m$-tuples
$(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(m)})\in\mathcal{P}_{n,m}$ such that
$\pi^{(j)}$ contains the element $1$. Define

$P^{j}_{m,n}(t,u,v)=\sum_{\alpha=(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(m)})\in\mathcal{P}^{j}_{m,n}}v^{|\mathcal{E}(\alpha)|}\prod_{i\in[m]\setminus\mathcal{E}(\alpha)}t^{des(\pi^{(i)})}u^{asc(\pi^{(i)})}.$

It is apparent that

$P^{i}_{m,n}(t,u,v)=P^{j}_{m,n}(t,u,v)$ (4.2)

for all $1\leq i<j\leq m$. Combining (4.1) and (4.2), we have

$P^{1}_{m,n}(t,u,v)={n!\over m}[z^{n}](\widetilde{A}(t,u;z)-1+v)^{m}.$ (4.3)

###### Lemma 4.1

For positive integers $m$ and $n$, let $\mathcal{M}=\\{1^{m},2,\ldots,n\\}$.
There exists a bijection $\zeta$ between $\mathcal{P}^{1}_{m,n}$ and
$\overline{\mathcal{Q}}_{\mathcal{M}}$ such that for any
$\alpha=(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(m)})\in\mathcal{P}^{1}_{m,n}$, we
have $plat(\zeta(\alpha))=|\mathcal{E}(\alpha)|$ and
$asc(\zeta(\alpha))=\sum_{i\in[m]\setminus\mathcal{E}(\alpha)}asc(\pi^{(i)})$,
and
$des(\zeta(\alpha))=\sum_{i\in[m]\setminus\mathcal{E}(\alpha)}des(\pi^{(i)})$.

Proof. Let
$\alpha=(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(m)})\in\mathcal{P}^{1}_{m,n}$.
Suppose that $\pi^{(1)}=\sigma 1\tau$. Set

$\zeta(\alpha)=\sigma 1\pi^{(2)}1\pi^{(3)}1\ldots\pi^{(m)}1\tau.$

It is easily seen that $\zeta(\alpha)\in\overline{\mathcal{Q}}_{\mathcal{M}}$
verifying the properties

  * •

$plat(\zeta(\alpha))=|\mathcal{E}(\alpha)|$;

  * •

$asc(\zeta(\alpha))=\sum_{i\in[m]\setminus\mathcal{E}(\alpha)}asc(\pi^{(i)})$;

  * •

$des(\zeta(\alpha))=\sum_{i\in[m]\setminus\mathcal{E}(\alpha)}des(\pi^{(i)})$.

Clearly, the map $\zeta$ is reversible and hence the map $\zeta$ is a
bijection, completing the proof.

Proof of Corollary 1.5. Let $\mathcal{M^{\prime}}=\\{1^{K-n+1},2,\ldots,n\\}$.
By Lemma 4.1, we have

$\begin{array}[]{lll}\overline{Q}_{\mathcal{M^{\prime}}}(t,u,v)&=&\sum_{\pi\in\overline{\mathcal{Q}}_{\mathcal{M}^{\prime}}}t^{des(\pi)}u^{asc(\pi)}v^{plat(\pi)}\\\
&=&\sum_{\alpha=(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(K-n+1)})\in\mathcal{P}^{1}_{K-n+1,n}}v^{|\mathcal{E}(\alpha)|}\prod_{i\in[K-n+1]\setminus\mathcal{E}(\alpha)}t^{des(\pi^{(i)})}u^{asc(\pi^{(i)})}\\\
&=&P^{1}_{K-n+1,n}(t,u,v)\\\ &=&{n!\over
K-n+1}[z^{n}](\widetilde{A}(t,u;z)-1+v)^{K-n+1}\,\,\,\,\,\,\mbox{(By
(\ref{eq4.2}))}.\end{array}$

By Theorem 1.1, we have

$\overline{Q}_{\mathcal{M}}(t,u,v)=\overline{Q}_{\mathcal{M^{\prime}}}(t,u,v)={n!\over
K-n+1}[z^{n}](\widetilde{A}(t,u;z)-1+v)^{K-n+1}$

as desired. This completes the proof.

Acknowledgments. This work was supported by the National Natural Science
Foundation of China (12071440).

## References

  * [1] K. Archer, A. Gregory, B. Pennington, S. Slayden, Pattern restricted quasi-Stirling permutations, Australas. J. Comb., 74 (2019), 389–407.
  * [2] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc., 81(413) (1989).
  * [3] F. Brenti, Hilbert polynomials in combinatorics, J. Algebraic Combin., 7 (1998), 127–156.
  * [4] M. Bóna, Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley, SIAM J. Discrete Math., 23 (2008), 401–406.
  * [5] A. Dzhumadil’daev, D. Yeliussizov, Stirling permutations on multisets, European J. Combin., 36 (2014), 377–392.
  * [6] S. Elizalde, Descents on quasi-Stirling permutations, J. Combin. Theory Ser. A, 180 (2021), 105429.
  * [7] I.M. Gessel, R.P. Stanley, Stirling polynomials, J. Combin. Theory Ser. A, 24(1978), 24–33.
  * [8] S. Liu, MacMahon’s equidistribution theorem for $k$-Stirling permutations, Adv. Appl. Math., 128(2021), 102193.
  * [9] S. Park, Inverse descents of $r$-multipermutations, Discrete Math., 132(1994), 215–229.
  * [10] S. Park, The r-multipermutations, J. Combin. Theory Ser. A, 67(1994), 44–71.
  * [11] S.H.F. Yan, X. Zhu, Quasi-Stirling Polynomials on Multisets, submitted.