# Why Is It Hate Speech?
Masked Rationale Prediction for Explainable Hate Speech Detection

Jiyun Kim, Byounghan Lee, Kyung-Ah Sohn∗
Ajou University
{hamjee66, qudgks96<EMAIL_ADDRESS>
∗Corresponding author

###### Abstract

In a hate speech detection model, we should consider two critical aspects in
addition to detection performance–bias and explainability. Hate speech cannot
be identified based solely on the presence of specific words: the model should
be able to reason like humans and be explainable. To improve the performance
concerning the two aspects, we propose Masked Rationale Prediction (MRP) as an
intermediate task. MRP is a task to predict the masked human
rationales–snippets of a sentence that are grounds for human judgment–by
referring to surrounding tokens combined with their unmasked rationales. As
the model learns its reasoning ability based on rationales by MRP, it performs
hate speech detection robustly in terms of bias and explainability. The
proposed method generally achieves state-of-the-art performance in various
metrics, demonstrating its effectiveness for hate speech detection. Warning:
This paper contains samples that may be upsetting.

##  1 Introduction

With the recent development of social media and online communities, hate
speech, one of the critical social problems, can spread easily. The spread of
hate strengthens discrimination and prejudice against the target social groups
and can violate their human rights. Moreover, online hatred extends offline
and causes real-world crimes. Therefore, properly regulating online hate
speech is important to address many social problems related to aversion.

In addition to the detection performance, two essential considerations are
involved in implementing a hate speech detection model–bias and
explainability. Hate speech should not be judged by any specific word but by
the context in which the word is used. Even if any word generally considered
vicious does not exist in a text, the text can be hate speech. A specific
expression does not always imply hatred either (e.g., e.g., ‘nigger’) (Del
Vigna12 et al., 2017). However, the presence of this word can cause a model to
make a biased detection of hate speech. This erroneous judgment may
inadvertently strengthen the discrimination against the target group of the
expression (Sap et al., 2019; Davidson et al., 2019). In this respect, the
model’s bias toward specific expressions should be excluded.

Figure 1: Examples for the two methods to get the final ground truths. Example
input sentences are represented with the class and human rationale labels. In
this figure, HateXplain uses the same ground truth about both normal and
hateful sentences for the loss. However, our method could determine the two
classes with the ground truths. Figure 2: Framework of the proposed method. We
finetune a pre-trained BERT through two training stages–Masked Rationale
Prediction (MRP) and then hate speech detection. In MRP, the partially masked
rationale label is inputted as the rationale embeddings by being added into
the input embeddings of BERT. The model predicts each masked rationale per
token. The model for hate speech detection is initialized by the updated
parameters during MRP.

The expressions that can cause biased judgment should be interpreted in
context. It means it is vital for the hate speech detection models to have the
ability to make judgments based on context, as humans do. Therefore, the model
should be explainable to humans so that the rationale behind a result is
explained (Liu et al., 2018). Here, the rationale is a piece of a sentence as
justification for the model’s prediction about the sentence, as defined by
related research (Hancock et al., 2018; Lei et al., 2016).

To the best of our knowledge, HateXplain (Mathew et al., 2020) is the first
hate speech detection benchmark dataset that considers both these aspects.
They proposed a method that utilizes rationales as attention ground truths to
complement the performance of the two elements. However, when most tokens are
annotated as the human rationale in a hateful sentence, the rationale’s
information could be meaningless as the ground truth attention becomes hard to
be distinguished from that of a normal sentence, as shown in Figure 1. This
can hinder the model’s learning.

In this paper, we present a method to implement a hate speech detection model
much more effectively by using the human rationale of hate for finetuning a
pre-trained language model. To achieve this, we propose Masked Rationale
Prediction (MRP) as an intermediate task before finetuning the model on hate
speech detection. MRP trains a model to predict the human rationale label of
each token by referring to the context of the input sentence. The model takes
the human rationale information of some input tokens among the sentence along
with the corresponding tokens as input. It then predicts the rationale of the
remaining tokens on which the rationale is masked. We embed the rationales to
provide the human rationales as input per token. The masking process of the
partial rationales is implemented while creating rationale embeddings; some
rationale embedding vectors are replaced with zero vectors.

MRP allows the model to make judgments per token about its masked rationale by
considering surrounding tokens with an unmasked rationale. With this, the
model learns a human-like reasoning process to get context-dependent
abusiveness of tokens. The model parameters trained on MRP become the initial
parameter values for hate speech detection in the following training stage. In
this way, based on the way of human reasoning for hate, the model can get
improved abilities in terms of bias and explainability in detecting hate
speech. We experimented with BERT Devlin et al. (2018) as the pre-trained
model. Consequently, our models finetuned in the proposed way–BERT-MRP and
BERT-RP–achieve state-of-the-art performance overall on all three types of 11
metrics of HateXplain benchmark–Performance-based, Bias-based, and
Explainability-based (Mathew et al., 2020). And the two models, especially
BERT-MRP, also show the best results in qualitative evaluation of explicit and
implicit hate speech detection.

The main contributions of this paper are:

  * •

We propose a method to utilize human rationales as input by transforming them
into rationale embeddings. Combining the embedded rationales with the
corresponding input sentence can provide information about the human
rationales per token during model training.

  * •

We propose Masked Rationale Prediction (MRP), a learning method that leads the
model to predict the masked rationale by considering the surrounding tokens.
The model is allowed to learn the reasoning process in context.

  * •

We finetune a pre-trained BERT in two stages–on MRP as an intermediate task
and then on hate speech detection. The parameters trained concerning human
reasoning for hate become a sufficient basis not only for the detection but
also in terms of the model bias and explainability.

##  2 Related works

Hate speech detection With the advance of deep learning, hate speech detection
studies have utilized neural networks (Badjatiya et al., 2017; Han and
Eisenstein, 2019), and word embedding methods (McKeown and McGregor, 2018).
More recently, Transformer-based (Vaswani et al., 2017) models have shown
remarkable results. In hate speech detection, BERT has been adopted for
various studies as hate speech detection can be considered a classification
task. Mandl et al. (2019) and Ranasinghe et al. (2019) compared a BERT-based
model with Recurrent Neural Networks (RNNs)-based models and showed the BERT-
based model outperforms other models. Furthermore, some studies have
considered the model’s bias and explainability. Vaidya et al. (2020) improved
accuracy and reduced unintended bias by adopting multi-task learning that
predicts toxicity of text and target group labels as additional information.
Mathew et al. (2020) utilized rationales of the dataset as additional
information for finetuning BERT to deal with the bias and explainability. To
improve performance in terms of the two considerations, we propose a more
effective finetuning approach based on BERT and the rationales by adopting the
pre-training framework.

Pre-finetuning on an intermediate task Recently, finetuning a pre-trained
model on a downstream task has become the norm (Howard and Ruder, 2018;
Radford et al., 2018). However, it cannot be guaranteed that the model
finetuned with a small dataset compared to its size will be sufficiently well-
adjusted for the target downstream task (Phang et al., 2018). Pre-finetuning
is a technique to train the model on a task before the target task (Aghajanyan
et al., 2021). This can help the model learn the data patterns or reduce the
tuning time so that it converges quickly to better fit the target task.
According to Pruksachatkun et al. (2020); Aghajanyan et al. (2021), the more
closely the intermediate task is related to the target task, the better the
effect of pre-finetuning. And inference tasks involving the reasoning process
show a remarkable improvement in the target task performance. We adopt this
method to train a pre-trained language model through two stages for hate
speech detection. As the intermediate task, we propose MRP, which guides the
model to infer the human rationale of each token based on surrounding tokens.
Explainable NLP and rationale Explaining the rationale of the result of an AI
model is necessary for it to be explainable to humans (Liu et al., 2018). Some
Natural Language Processing (NLP) studies define rationale as snippets of an
input text on which the model’s prediction is supported (Hancock et al., 2018;
Lei et al., 2016). Lei et al. (2016) implemented a generator that generates
words considered rationales and used them as input of an encoder for sentiment
classification. Bao et al. (2018) mapped the human rationales into the model
attention values to solve the low-resource problem by learning a domain-
invariant token representation. For hate speech detection, HateXplain employs
the human rationales as ground truth attention to concentrate on aggressive
tokens. Unlike existing approaches, we utilize the masked human rationale
label embeddings as input. They become the useful additional information of
each token.
Masked label prediction The UniMP model presented by Shi et al. (2020) aims to
solve the graph node classification problem using graph transformer networks
(Yun et al., 2019). They maximized the propagation information required to
reconstruct a partially observable label by using both feature information and
label information as inputs. However, to prevent overfitting due to excessive
information, some label information is masked, and the masked label is
predicted. We apply a similar method to text data for an intermediate task
with rationales. Through additional rationale information, the model increases
the understanding of input sentences, and the performance of the downstream
task is improved.

##  3 Method

Hate speech detection can be described as a text classification problem.
Following the problem setting of HateXplain, we define the problem as a three-
class classification involving three categories–‘hate speech,’ ‘offensive,’ or
‘normal’. We finetune a pre-trained BERT on hate speech detection. Note that
other transformer encoder-based models can be used instead. Before finetuning
the model on this task, we pre-finetune it on an intermediate task. We propose
Masked Rationale Prediction (MRP) as the intermediate task. Our method is
described in Figure 2.

###  3.1 Masked rationale prediction

For MRP, we utilize human rationales of hate provided by the HateXplain
dataset. Annotators marked some words in a sentence as rationales for judging
the sentence as abusive. A rationale label is presented in a list format,
including 1 as rationale and 0 as non-rationale per word in the corresponding
sentence. There are no such labels for a sentence whose final class is
‘normal.’ As the dataset was annotated by two or three people per sentence,
some pre-processing is required to get the final rationale labels for MRP. To
manipulate the multiple rationale labels to one per sentence, we obtain the
average value of the rationales per word, and if it is over 0.5, the value of
1; otherwise, the value of 0 is determined as the final rationale of the
corresponding word. The final rationale label is a list of these last values.
In the case of the ‘normal’ sentence, a list of zeros is used. Accordingly,
the final rationale label consists of as many 0s or 1s as the number of words
in the sentence. As a sentence is tokenized, its rationale label is also
modified in token units.

MRP is based on token classification, which predicts the rationale label $R$
per token in an input sentence $S$. In our MRP, the rationale labels, as well
as the sentences, are used as inputs. The process of embedding $S$ is the same
as that of BERT. We denote the embedded $S$ as
$X^{S}=\\{x_{0}^{S},x_{1}^{S},\cdots,x_{n-1}^{S}\\}\in\mathbb{R}^{n\times d}$
where $n$ is the sequence length and $d$ is the embedding size. And to use $R$
as input, we pass it through an embedding layer to get
$X^{R}=\\{x_{0}^{R},x_{1}^{R},\cdots,x_{n-1}^{R}\\}\in\mathbb{R}^{n\times d}$
as shown in Figure 2. The rationale embeddings reflect the attributes of each
token as a ground for the human judgment.

MRP differs from BERT’s Masked Language Modeling (MLM) in masking processing.
Specifically, we do not mask the tokens; we mask the rationales. To construct
the partially masked rationale embeddings $\tilde{X}^{R}$, some rationales are
randomly selected to be masked. Each of rationales is transformed into its
corresponding embedding vector, except the masked ones. For masking, zero
vectors replace the embedding vectors of each corresponding token. For
example, if we mask $x_{1}^{R}$ and $x_{3}^{R}$, then the rationale embedding
matrix is like
$\tilde{X}^{R}=\\{\vv{0},\vv{0},x_{2}^{R},\vv{0},\cdots,x_{n-2}^{R},\vv{0}\\}$.
The first and last rationale embeddings corresponding to CLS and SEP tokens,
respectively, are replaced with $\vv{0}$.

The MRP model predicts the rationale by taking the sum of the embedded tokens
$X^{S}$ and the partially masked rationales $\tilde{X}^{R}$ as input. We then
get:

$\begin{split}\displaystyle H_{MRP}^{(0)}&=X^{S}+\tilde{X}^{R},\\\
H_{MRP}^{(l+1)}&=\text{Transformer}(H_{MRP}^{(l)}),\\\
\hat{X}^{R}&=\text{MLP}(H_{MRP}^{(L)}).\end{split}$ (1)

The $l$-th hidden state passes through the transformer block to create the
$l+1$-th hidden state, and the last hidden state $H_{MRP}^{(L)}$ outputs a
predicted rationale $\hat{X}^{R}$ through Multi-Layer Perceptron (MLP). In
other words, the model is guided to predict the masked rationales by referring
to the representations of tokens using their corresponding observed
rationales.

The loss $\mathcal{L}_{MRP}$ is calculated with only the predictions of the
masked rationales. Therefore, our objective function is:

$\begin{split}\displaystyle\arg\max_{\theta}\hskip
2.84526pt\log\text{p}_{\theta}\left(\hat{X}^{R}|X^{S},\tilde{X}^{R}\right)=\\\
\sum_{m\in
M}\log\text{p}_{\theta}\left(x_{m}^{R}|X^{S},\tilde{X}^{R}\right),\\\
\end{split}$ (2)

where $M$ indicates a set of index numbers of rationales that have been
masked.

Model | Performance | Bias
---|---|---
| ration. | pre-fin. | Acc. | Macro F1 | AUROC | GMB-Sub. | GMB-BPSN | GMB-BNSP
BERT |  |  | 69.0 | 67.4 | 84.3 | 76.2 | 70.9 | 75.7
BERT-HateXplain | ✓ |  | 69.8 | 68.7 | 85.1 | 80.7 | 74.5 | 76.3
BERT-MLM |  | ✓ | 70.0 | 67.5 | 85.4 | 79.0 | 67.7 | 80.9
BERT-RP | ✓ | ✓ | 70.7 | 69.3 | 85.3 | 81.4 | 74.6 | 84.8
BERT-MRP | ✓ | ✓ | 70.4 | 69.9 | 86.2 | 81.5 | 74.8 | 85.4
Table 1: Results for the performance-based and the bias-based metrics. Scores in bold type are the best for each corresponding metric, while the underlined are the second best, and so are in Table 2.  Model | Explainability
---|---
| Plausibility | Faithfulness
| ration. | pre-fin. | IOU F1 | Token F1 | AUPRC | Comp. | Suff. $\downarrow$
BERT [Att] |  |  | 13.0 | 49.7 | 77.8 | 44.7 | 5.7
BERT [LIME] |  |  | 11.8 | 46.8 | 74.7 | 43.6 | 0.8
BERT-HateXplain [Att] | ✓ |  | 12.0 | 41.1 | 62.6 | 42.4 | 16.0
BERT-HateXplain [LIME] | ✓ |  | 11.2 | 45.2 | 72.2 | 50.0 | 0.4
BERT-MLM [Att] |  | ✓ | 13.5 | 43.5 | 60.8 | 40.1 | 11.9
BERT-MLM [LIME] |  | ✓ | 11.3 | 47.2 | 76.5 | 43.4 | -5.5
BERT-RP [Att] | ✓ | ✓ | 13.8 | 50.3 | 73.8 | 45.4 | 7.2
BERT-RP [LIME] | ✓ | ✓ | 11.4 | 49.3 | 77.7 | 48.6 | -2.6
BERT-MRP [Att] | ✓ | ✓ | 14.1 | 50.4 | 74.5 | 47.9 | 6.7
BERT-MRP [LIME] | ✓ | ✓ | 12.9 | 50.1 | 79.2 | 48.3 | -1.2
Table 2: Results for the explainability-based metrics. The lower the score
Sufficiency in Faithfulness, the better, and the higher the other scores, the
better.

###  3.2 Hate speech detection

Hate speech detection is implemented as three-class text classification. The
model predicts which category $Y$ the input sentence belongs to among ‘hate
speech’, ‘offensive’, and ‘normal’. The head that outputs the predicted class
$\hat{Y}$ is used on the top of BERT. Before training, the model parameters
are initialized by parameters updated on the intermediate task MRP, except for
the head. As the forms of heads are different for two stages, their parameters
are randomly initialized. Consequently, in the finetuning stage on hate speech
detection, the rationale labels are not involved functionally, considered as
$[0]_{n\times d}$. Therefore, in this stage, the input of the model is
$H_{HSD}^{(0)}=X^{S}$.

In this stage, the model does not refer to the rationale labels. The
parameters trained during MRP are utilized as a base for reasoning hatefulness
in context. The loss $\mathcal{L}_{HSD}$ is obtained through a cross-entropy
function, as the task is a multi-class classification problem.

$\begin{split}\displaystyle\arg\max_{\theta}\hskip
2.84526pt\log\text{p}_{\theta}\left(\hat{Y}|X^{S}\right).\end{split}$ (3)

##  4 Experiments

###  4.1 Dataset

For both stages of the intermediate and the target task, we use the HateXplain
dataset. It contains 20,148 items collected from Twitter and Gab. Every item
consists of one English sentence with its own ID and annotations about labels
for its category, target groups, and rationales, which are annotated by two or
three annotators. Based on the IDs, the dataset is split into 8:1:1 for
training, validation, and test phases. Following the permanent split provided
by the dataset, the models can’t reference any test data during the training
phases of all stages.

###  4.2 Metrics

The evaluation is according to the metrics of HateXplain, which are classified
into three types: performance-based, bias-based, and explainability-based. The
performance-based metrics measure the detection performance in distinguishing
among three classes (i.e., hate speech, offensive, and normal). Accuracy,
macro F1 score, and AUROC score are used as the metrics.

The bias-based metrics evaluate how biased the model is for specific
expressions or profanities easily assumed to be hateful. HateXplain follows
AUC-based metrics developed by Borkan et al. (2019). The model classifies the
data into ‘toxic’–hateful and offensive–and ‘non-toxic’–normal. For evaluating
the model’s prediction results, the data are separated into four subsets:
$D_{g}^{+},D_{g}^{-}$, $D^{+}$, and $D^{-}$. The target group labels are
considered standard for dividing data into subgroups. The notations with $g$
denote the data of a specific subgroup among the subgroups, and the notations
without g are the remaining data. $+$ and $-$ mean that the data are toxic and
non-toxic, respectively. Based on these subsets, three AUC metrics are
calculated.

Subgroup AUC is to evaluate how biased the model is to the context of each
target group: $AUC(D_{g}^{-}+D_{g}^{+})$. The higher the score, the less
biased the model is with its prediction of a certain social group.

BPSN (Background Positive, Subgroup Negative) AUC measures the model’s false-
positive rates regarding the target groups: $AUC(D^{+}+D_{g}^{-})$. The higher
the score is, the less a model is likely to confuse non-toxic sentences whose
target is the specific subgroup and toxic sentences whose target is one of the
other groups.

BNSP (Background Negative, Subgroup Positive) AUC measures the model’s false-
negative rates regarding the target groups: $AUC(D^{-}+D_{g}^{+})$. The higher
the score is, the less the model is likely to confuse non-toxic sentences
whose target is the specific group and toxic sentences whose target is one of
the other groups.

We calculate GMB (Generalized Mean of
Bias)111https://www.kaggle.com/competitions/jigsaw-unintended-bias-in-
toxicity-classification/overview/evaluation of the three metrics as the final
scores to combine those ten scores of each of the metrics into one overall
measure according to the HateXplain benchmark. The formula is:
$M_{p}(m_{s})=(\frac{1}{N}\sum_{s=1}^{N}m_{s}^{p})^{\frac{1}{p}}$, where
$M_{p}$ means the $p^{th}$ power-mean function, $m_{s}$ is one of the bias
metrics $m$ calculated for a specific subgroup $s$, and N is the number of
subgroups which is 10 in this paper.

The explainability-based metrics evaluate how much the model is explainable.
HateXplain follows ERASER (DeYoung et al., 2019), which is a benchmark for the
evaluation of explainability of an NLP model based on rationales. The metrics
are divided into Plausibility and Faithfulness. Plausibility refers to how the
model’s rationale matches the human rationale. Plausibility can be considered
both discrete selection and soft selection. For discrete selection, We convert
token scores to binary values by more than some threshold(here 0.5). Then, We
measures IOU F1 score and Token F1 score. For soft selection, We constructed
AUPRC by sweeping a threshold over token scores.

Faithfulness evaluates the influence of the model rationale on its prediction
result and consists of Comprehensiveness and Sufficiency. Comprehensiveness
assumes the model prediction is less confidence when rationales are removed.
This metric can be calculated: $m(x_{i})_{j}-m(x_{i}\backslash r_{i})_{j}$.
$m(x_{i})_{j}$ is the prediction probability of the corresponding class j with
an input sentence $x_{i}$ by the model $m$. And $x_{i}\backslash r_{i}$ is the
sentence manipulated by removing the predicted rationale tokens $r_{i}$ from
$x_{i}$.222We select the top 5 tokens to remove based on the average length of
human-annotated rationale labels in the dataset according to HateXplain
benchmark. The higher a score, the more influential the model’s rationales in
its prediction. Sufficiency captures the extent to which extracted rationales
are acceptable for a model to make a prediction: $m(x_{i})_{j}-m(r_{i})_{j}$.
A low score of this metric means that the rationales are adequate in the
prediction.

In addition, for the HateXplain benchmark, the scores are calculated based on
the attention scores of the last layer or by using the LIME method (Ribeiro et
al., 2016). The former is marked as [Att], and the latter is [LIME] in Table
2. DeYoung et al. (2019) and Mathew et al. (2020) contain more detailed
explanations.

###  4.3 Models and Experimental settings

The evaluated models in Table 1 and Table 2 are as follows. All models are
based on a BERT-base-uncased model for a pre-trained model and finetuned on
hate speech detection. BERT in the tables is simply finetuned on hate speech
detection with a fully-connected layer as a head for the three-class
classification described above.

BERT-HateXplain uses attention supervision in addition to BERT. It matches the
last attention values corresponding to the CLS token to the rationale used as
ground truth attention. With this, the CLS token takes additional rationale-
based attention information for the prediction. The loss is the summation of
this attention loss and the detection loss. The results of BERT and BERT-
HateXplain are the same as those presented in Mathew et al. (2020).

Figure 3: The Subgroup scores among bias-based metrics for each of ten target
groups. The target group labels are ‘African’, ‘Islam’, ‘Jewish’,
‘Homosexual’, ‘Women’, ‘Refugee’, ‘Arab’, ‘Caucasian’, ‘Asian’, and ‘Hispanic’
in clockwise direction respectively. The BPSN and BNSP scores are attached in
Appendix. Figure 4: Classification test scores of the proposed models
according to masking ratio in MRP. (a) is for token classification after
training on MRP in the first stage, and (b) is for hate speech detection in
the final stage. The case of masking 100% of tokens is the same as BERT-RP.

BERT-MLM is evaluated to compare the effectiveness of pre-finetuning tasks.
Training a pre-trained NLP model with MLM using data of the downstream task is
frequently used for the model to understand the downstream data and improve
its performance (Han and Eisenstein, 2019; Ben-David et al., 2020; Arefyev et
al., 2021). It is implemented by simply masking 15% tokens of each input
sentence.

BERT-MRP and BERT-RP are the proposed models in this paper. BERT-MRP is the
model trained on MRP as an intermediate task and then finetuned on hate speech
detection. The ratio of masked rationales per token is set to 50% of the
entire rationale label. BERT-RP is trained on Rationale Prediction (RP), which
is MRP when the ratio is set to 100%–masking all the rationales. It is
functionally the same as token classification with the rationale label as
ground truth.

BERT-MLM, BERT-RP, and BERT-MRP are directly trained in this study. The
experimental settings are the same for all models and each training step. The
learning rate is $5e\scalebox{0.75}[1.0]{$-$}5$ during pre-finetuning and
$2e\scalebox{0.75}[1.0]{$-$}5$ for hate speech detection, which is the same as
BERT-HateXplain. We use the RAdam optimizer and an Nvidia GeForce GTX 1050
graphics card.

###  4.4 Comparisons of results

Table 1 and Table 2 present the performances of the models. For all metrics,
the proposed models–the two from the bottom–perform much better overall.

Performance-based metrics As summarized in Table 1, the proposed method
outperforms the other methods. BERT-MRP shows the highest scores for Macro F1
and AUROC and BERT-RP for accuracy. The pre-finetuned models perform better
than those that are not. It shows that the pre-finetuning process helps
understand the data and allows enough time for tuning parameters for the
target task, thereby improving performance. On the other hand, among the pre-
finetuned models, the proposed models show better results than BERT-MLM.
Furthermore, they outperform BERT-HateXplain, which also uses the rationale
during training like ours. This shows that predicting the human rationale for
hate as an intermediate task effectively implements a hate speech detection
model.

No. | Model | Example sentence and Rationale | Label
---|---|---|---
Case 1 Explicit hate speech
1 | Human |  imagine unironically believing the high iq kike meme | HS
| BERT-MRP |  imagine un ##iro ##nical ##ly believing the high iq ki ##ke me ##me | HS
| BERT-RP |  imagine un ##iro ##nical ##ly believing the high iq ki ##ke me ##me | HS
| BERT-HX |  imagine un ##iro ##nical ##ly believing the high iq ki ##ke me ##me | HS
2 | Human |  <user> ffs these ghetto blacks are ignorant like cracker mountain hillbillies | HS
| BERT-MRP |  <user> ff ##s these ghetto blacks are ignorant like crack ##er mountain hill ##bill ##ies | HS
| BERT-RP |  <user> ff ##s these ghetto blacks are ignorant like crack ##er mountain hill ##bill ##ies | HS
| BERT-HX |  <user> ff ##s these ghetto blacks are ignorant like crack ##er mountain hill ##bill ##ies | HS
Case 2 Implicit hate speech
3 | Human |  yah christian island republic shall not have queers or witches on it if we find any death | HS
| BERT-MRP |  ya ##h christian island republic shall not have queer ##s or witches on it if we find any death | HS
| BERT-RP |  ya ##h christian island republic shall not have queer ##s or witches on it if we find any death | HS
| BERT-HX |  ya ##h christian island republic shall not have queer ##s or witches on it if we find any death | NO
4 | Human |  you can not culturally enrich a moslem | HS
| BERT-MRP |  you can not culturally en ##rich a mo ##sle ##m | HS
| BERT-RP |  you can not culturally en ##rich a mo ##sle ##m | NO
| BERT-HX |  you can not culturally en ##rich a mo ##sle ##m | NO
5 | Human |  <user> he is infected with jihadi virus he will spread it to others | HS
| BERT-MRP |  <user> he is infected with jihad ##i virus he will spread it to others | HS
| BERT-RP |  <user> he is infected with jihad ##i virus he will spread it to others | HS
| BERT-HX |  <user> he is infected with jihad ##i virus he will spread it to others | OF
Table 3: The highlighted words of the human rationale and the rationale of the
models with detection results. BERT-HX is BERT-HateXplain. In the label
column, the ground truth is of humans and the remaining labels are the
predictions of each model. HS is ’hate speech,’ OF is ’offensive,’ and NO is
’normal.’ More examples are in Appendix.

Bias-based metrics For the model bias, the proposed models show superior
results compared to other models. According to Table 1, the models trained
using the rationales achieve higher scores than others in general. Given that
the human rationales of hatred imply that hate speech is judged based on the
context, not merely specific expressions, learning the rationale can exclude
the model bias towards the particular words for the prediction. Meanwhile, the
proposed BERT-RP and BERT-MRP show better performance than BERT-HateXplain,
even though they all utilize the rationale in training. BERT-MRP shows the
best scores, and BERT-RP is the second-best for all three metrics.
Additionally, Figure 3 shows the scores of the models for each of the ten
major target groups. It can be seen that the proposed models score evenly high
for all the target groups. While other models have significant differences in
their bias depending on the groups, the proposed models have comparatively no
correlation with them.

Explainability-based metrics In terms of explainability, the proposed models
still perform better than others overall. For Plausibility, BERT-MRP achieves
the best performance for all three metrics. It scores much higher than others
because it is allowed to directly guess the human rationales during the
intermediate training stage. For Faithfulness, BERT-HateXplain[LIME] shows the
highest score for Comprehensiveness, and BERT-MLM[LIME] is the best for
Sufficiency. However, these models do not reliably score well when considering
all four scores obtained according to each of the two measurement methods:
attention values or LIME. They show worse scores than BERT for the rest of the
scores. On the other hand, BERT-MRP and BERT-RP offer stably high performance
for all five explainability-based metrics.

Based on all these results, BERT-MRP and BERT-RP demonstrate the best
performance overall for the three types of metrics. Thus, learning the human
rationale as an intermediate task before training on hate speech detection
seems effective for detection performance and model bias and its
explainability. This framework contributes to better performance than the
other–pre-finetuning on MLM as well as another way of using rationales.

BERT-MRP generally achieves better results than BERT-RP, wherein the
intermediate task is basically the same as token classification. The plots in
Figure 4 show the change in test scores according to the masking ratio in MRP.
According to Figure 4(a), when more than 20% of all rationales were masked,
there is no significant difference in the token classification performance,
although the amount of loss decreases as the ratio decreases. When each model
was re-trained for hate speech detection, as shown in Figure 4(b), the case of
50% ratio in BERT-MRP achieved the best classification performance. As MRP is
a method for inferring the rationale of a particular token based on
surrounding tokens, the model can successfully learn the human rationale
within the context. Learning parameters during this reasoning process based on
context seems to effectively prevent biased prediction while still being
explainable and consequently improves the detection performance substantially.

###  4.5 Qualitative results

Table 3 shows examples of detection results from models that use human
rationale for their training. The visualized values as the model rationales
are the LIME results used to measure the explainability-based scores. For the
human ground truth, the average value per word of human-annotated rationales
is expressed for each word. The darker the color, the higher the values.

It is relatively easy to judge explicit hate speech that includes clear
derogatory expressions. As shown in Case 1 of Table 3, all the models perform
well. The human rationale tends to focus on specific abusive words, and so
does the rationale of each model. However, the rationales of the two proposed
models match the ground truth better than BERT-HateXplain. Our method to train
a model on a token classification-based task leads well the model to focus on
human-like grounds in the sentence by directly learning the human rationale.

As in Case 2, the implicit hate speech with no aggressive expressions cannot
be grasped through context. The human rationale thus tends to appear
throughout the sentence. As this might make hate speech detection relatively
challenging, the detection results of BERT-HateXplain or BERT-RP seem
incorrect for some sentences. However, BERT-MRP works accurately based on its
rationale that is much more similar to human’s than others. Meanwhile, BERT-
HateXplain shows a low matching rate of the rationale when the human rationale
is throughout the sentence. It uses the human rationale as the ground truth
attention, and if there is no difference in the human rationale across tokens,
the ground truth could become similar to that of any normal sentence
represented by uniform values. This affects the model’s explainability and may
lead to incorrect detection results. The proposed method does not cause that
problem. It gets the distinguishable ground truth from normal ones and assigns
it as labels to tokens. On the other hand, the rationale of BERT-MRP matches
the ground truth better than that of BERT-RP. MRP requires more context-
awareness ability when predicting the masked token by allowing the model to
consider the abusiveness of surrounding words that are provided corresponding
human rationale. This offers robust detection performance, even when it is
necessary to understand the context.

##  5 Conclusion

This paper presents a method to implement a hate speech detection model
considering bias and explainability. We adopt a framework to finetune a pre-
trained language model in two stages. As the intermediate task, we propose
Masked Rationale Prediction (MRP), which predicts masked rationales for some
tokens with the additional rationale information of the remaining surrounding
tokens. With this, the model learns to identify abusiveness for each token and
the human reasoning process based on context. The trained model by MRP is
finetuned again on hate speech detection.

As a result, across quantitative and qualitative evaluations, the proposed
model shows state-of-the-art performance in bias and explainability, as well
as the detection result. And the examples demonstrate its robustness in
detecting hate speech, whether explicit or implicit, based on its superior
explainability. Meanwhile, we experimented with only BERT as the pre-trained
model to compare our method with base models. But any other Transformer
encoder-based model can be easily applied, which can be taken as future work.

## Acknowledgements

This work was supported by the Ministry of Education of the Republic of Korea
and the National Research Foundation of Korea (NRF) (NRF-2021S1A5A2A03065899),
and also by the NRF of Korea grant funded by the Korean government (MSIT)
(NRF-2022R1A2C1007434).

## References

  * Aghajanyan et al. (2021) Armen Aghajanyan, Anchit Gupta, Akshat Shrivastava, Xilun Chen, Luke Zettlemoyer, and Sonal Gupta. 2021.  Muppet: Massive multi-task representations with pre-finetuning.  _arXiv preprint arXiv:2101.11038_.
  * Arefyev et al. (2021) Nikolay Arefyev, Dmitrii Kharchev, and Artem Shelmanov. 2021.  Nb-mlm: Efficient domain adaptation of masked language models for sentiment analysis.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 9114–9124.
  * Badjatiya et al. (2017) Pinkesh Badjatiya, Shashank Gupta, Manish Gupta, and Vasudeva Varma. 2017.  Deep learning for hate speech detection in tweets.  In _Proceedings of the 26th international conference on World Wide Web companion_ , pages 759–760.
  * Bao et al. (2018) Yujia Bao, Shiyu Chang, Mo Yu, and Regina Barzilay. 2018.  Deriving machine attention from human rationales.  _arXiv preprint arXiv:1808.09367_.
  * Ben-David et al. (2020) Eyal Ben-David, Carmel Rabinovitz, and Roi Reichart. 2020.  Perl: Pivot-based domain adaptation for pre-trained deep contextualized embedding models.  _Transactions of the Association for Computational Linguistics_ , 8:504–521.
  * Borkan et al. (2019) Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. 2019\.  Nuanced metrics for measuring unintended bias with real data for text classification.  In _Companion proceedings of the 2019 world wide web conference_ , pages 491–500.
  * Davidson et al. (2019) Thomas Davidson, Debasmita Bhattacharya, and Ingmar Weber. 2019.  Racial bias in hate speech and abusive language detection datasets.  _arXiv preprint arXiv:1905.12516_.
  * Del Vigna12 et al. (2017) Fabio Del Vigna12, Andrea Cimino23, Felice Dell’Orletta, Marinella Petrocchi, and Maurizio Tesconi. 2017.  Hate me, hate me not: Hate speech detection on facebook.  In _Proceedings of the First Italian Conference on Cybersecurity (ITASEC17)_ , pages 86–95.
  * 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.  _arXiv preprint arXiv:1810.04805_.
  * DeYoung et al. (2019) Jay DeYoung, Sarthak Jain, Nazneen Fatema Rajani, Eric Lehman, Caiming Xiong, Richard Socher, and Byron C Wallace. 2019.  Eraser: A benchmark to evaluate rationalized nlp models.  _arXiv preprint arXiv:1911.03429_.
  * Han and Eisenstein (2019) Xiaochuang Han and Jacob Eisenstein. 2019.  Unsupervised domain adaptation of contextualized embeddings for sequence labeling.  _arXiv preprint arXiv:1904.02817_.
  * Hancock et al. (2018) Braden Hancock, Martin Bringmann, Paroma Varma, Percy Liang, Stephanie Wang, and Christopher Ré. 2018.  Training classifiers with natural language explanations.  In _Proceedings of the conference. Association for Computational Linguistics. Meeting_ , volume 2018, page 1884. NIH Public Access.
  * Howard and Ruder (2018) Jeremy Howard and Sebastian Ruder. 2018.  Universal language model fine-tuning for text classification.  _arXiv preprint arXiv:1801.06146_.
  * Lei et al. (2016) Tao Lei, Regina Barzilay, and Tommi Jaakkola. 2016.  Rationalizing neural predictions.  _arXiv preprint arXiv:1606.04155_.
  * Liu et al. (2018) Hui Liu, Qingyu Yin, and William Yang Wang. 2018.  Towards explainable nlp: A generative explanation framework for text classification.  _arXiv preprint arXiv:1811.00196_.
  * Mandl et al. (2019) Thomas Mandl, Sandip Modha, Prasenjit Majumder, Daksh Patel, Mohana Dave, Chintak Mandlia, and Aditya Patel. 2019.  Overview of the hasoc track at fire 2019: Hate speech and offensive content identification in indo-european languages.  In _Proceedings of the 11th forum for information retrieval evaluation_ , pages 14–17.
  * Mathew et al. (2020) Binny Mathew, Punyajoy Saha, Seid Muhie Yimam, Chris Biemann, Pawan Goyal, and Animesh Mukherjee. 2020.  Hatexplain: A benchmark dataset for explainable hate speech detection.  _arXiv preprint arXiv:2012.10289_.
  * McKeown and McGregor (2018) Rohan Kshirsagar1 Tyrus Cukuvac1 Kathleen McKeown and Susan McGregor. 2018.  Predictive embeddings for hate speech detection on twitter.  _EMNLP 2018_ , page 26.
  * Phang et al. (2018) Jason Phang, Thibault Févry, and Samuel R Bowman. 2018.  Sentence encoders on stilts: Supplementary training on intermediate labeled-data tasks.  _arXiv preprint arXiv:1811.01088_.
  * Pruksachatkun et al. (2020) Yada Pruksachatkun, Jason Phang, Haokun Liu, Phu Mon Htut, Xiaoyi Zhang, Richard Yuanzhe Pang, Clara Vania, Katharina Kann, and Samuel R Bowman. 2020.  Intermediate-task transfer learning with pretrained models for natural language understanding: When and why does it work?  _arXiv preprint arXiv:2005.00628_.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018.  Improving language understanding by generative pre-training.
  * Ranasinghe et al. (2019) Tharindu Ranasinghe, Marcos Zampieri, and Hansi Hettiarachchi. 2019.  Brums at hasoc 2019: Deep learning models for multilingual hate speech and offensive language identification.  In _FIRE (working notes)_ , pages 199–207.
  * Ribeiro et al. (2016) Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016.  " why should i trust you?" explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1135–1144.
  * Sap et al. (2019) Maarten Sap, Dallas Card, Saadia Gabriel, Yejin Choi, and A Noah Smith. 2019.  The risk of racial bias in hate speech detection.  In _ACL_.
  * Shi et al. (2020) Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. 2020\.  Masked label prediction: Unified message passing model for semi-supervised classification.  _arXiv preprint arXiv:2009.03509_.
  * Vaidya et al. (2020) Ameya Vaidya, Feng Mai, and Yue Ning. 2020.  Empirical analysis of multi-task learning for reducing identity bias in toxic comment detection.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 14, pages 683–693.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Yun et al. (2019) Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. 2019.  Graph transformer networks.  _Advances in neural information processing systems_ , 32.

Figure A1: The Bias-based scores for each 10 target groups. The target group labels are ‘African’, ‘Islam’, ‘Jewish’, ‘Homosexual’, ‘Women’, ‘Refugee’, ‘Arab’, ‘Caucasian’, ‘Asian’, and ‘Hispanic’ in clockwise direction respectively. Model | Example sentence and Rationale | Label
---|---|---
Human |  if you ’ re an army that is republican you are not welcome here we hate you | HS
BERT-MRP |  if you ’ re an army that is republican you are not welcome here we hate you | HS
BERT-RP |  if you ’ re an army that is republican you are not welcome here we hate you | NO
BERT-HX |  if you ’ re an army that is republican you are not welcome here we hate you | NO
Human |  the german regime is more scared of women like this than than are of any moslem terrorist | HS
BERT-MRP |  the german regime is more scared of women like this than than are of any mo ##sle ##m terrorist | HS
BERT-RP |  the german regime is more scared of women like this than than are of any mo ##sle ##m terrorist | HS
BERT-HX |  the german regime is more scared of women like this than than are of any mo ##sle ##m terrorist | NO
Human |  i poisoned sergei skripal he was a faggot anyway | HS
BERT-MRP |  i poisoned sergei sk ##rip ##al he was a fa ##gg ##ot anyway | HS
BERT-RP |  i poisoned sergei sk ##rip ##al he was a fa ##gg ##ot anyway | HS
BERT-HX |  i poisoned sergei sk ##rip ##al he was a fa ##gg ##ot anyway | OF
Human |  <user> would have pressed that bitch and beat the faggot out of him | HS
BERT-MRP |  <user> would have pressed that bitch and beat the fa ##gg ##ot out of him | HS
BERT-RP |  <user> would have pressed that bitch and beat the fa ##gg ##ot out of him | HS
BERT-HX |  <user> would have pressed that bitch and beat the fa ##gg ##ot out of him | OF
Human |  massive muzrat espionage | HS
BERT-MRP |  massive mu ##z ##rat espionage | HS
BERT-RP |  massive mu ##z ##rat espionage | HS
BERT-HX |  massive mu ##z ##rat espionage | HS
Human |  enjoy your kike faith | HS
BERT-MRP |  enjoy your ki ##ke faith | HS
BERT-RP |  enjoy your ki ##ke faith | HS
BERT-HX |  enjoy your ki ##ke faith | HS
Table A1: The highlighted words of the human rationale and the rationale of the models with detection results in ’hate speech’ sentences.  Model | Example sentence and Rationale | Label
---|---|---
Human |  “ i don ’ t have to respect women i ’ m gay ” kevin | OF
BERT-MRP |  “ i don ’ t have to respect women i ’ m gay ” kevin | OF
BERT-RP |  “ i don ’ t have to respect women i ’ m gay ” kevin | NO
BERT-HX |  “ i don ’ t have to respect women i ’ m gay ” kevin | NO
Human |  logan paul is a fucking bozo | OF
BERT-MRP |  logan paul is a fucking bo ##zo | OF
BERT-RP |  logan paul is a fucking bo ##zo | NO
BERT-HX |  logan paul is a fucking bo ##zo | NO
Human |  <user> <user> there are literally nazis all over all the time rigjt now throw a rock | OF
|  you hit a nazi |
BERT-MRP |  <user> <user> there are literally nazis all over all the time rig ##j ##t now throw a rock | OF
|  you hit a nazi |
BERT-RP |  <user> <user> there are literally nazis all over all the time rig ##j ##t now throw a rock | OF
|  you hit a nazi |
BERT-HX |  <user> <user> there are literally nazis all over all the time rig ##j ##t now throw a rock | NO
|  you hit a nazi |
Human |  all my friends and peers are being openly racist towards asians and this bitch is | OF
|  not having it |
BERT-MRP |  all my friends and peers are being openly racist towards asian ##s and this bitch is | OF
|  not having it |
BERT-RP |  all my friends and peers are being openly racist towards asian ##s and this bitch is | OF
|  not having it |
BERT-HX |  all my friends and peers are being openly racist towards asian ##s and this bitch is | OF
|  not having it |
Human |  hey nazi dirtbag is your black bull keeping you occupied | OF
BERT-MRP |  hey nazi dirt ##bag is your black bull keeping you occupied | OF
BERT-RP |  hey nazi dirt ##bag is your black bull keeping you occupied | OF
BERT-HX |  hey nazi dirt ##bag is your black bull keeping you occupied | OF
Human |  white bitch pink pussy | OF
BERT-MRP |  white bitch pink pussy | OF
BERT-RP |  white bitch pink pussy | OF
BERT-HX |  white bitch pink pussy | OF
Table A2: The highlighted words of the human rationale and the rationale of
the models with detection results in ’offensive’ sentences.


Stable multivariate Narayana polynomials and labeled plane trees

Harold R.L. Yanga and Philip B. Zhangb

aCollege of Science

Tianjin University of Technology and Education

Tianjin 300222, R. R. China

bCollege of Mathematical Science

Tianjin Normal University, Tianjin 300387, P. R. China

Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract. In this paper, we introduce stable multivariate generalizations of
Narayana polynomials of type A and type B. Our polynomials are multivariate
generating polynomials over labeled plane trees and can be generated by a
grammatical labeling based on a context-free grammar. Our proof of real
stability uses a characterization of stable-preserving linear operators due to
Borcea and Brändén.

AMS Classification 2020: 05A15, 26C10

Keywords: context-free grammar; Narayana polynomial; labeled plane tree

##  1 Introduction

Univariate polynomials with only real roots often occur in combinatorics and
can lead to interesting conclusions. There are several real-rooted univariate
polynomials in combinatorics, including Eulerian polynomials, Narayana
polynomials, matching polynomials of graphs, and independence polynomials of
claw-free polynomials. We refer to the following surveys [5, 9, 10, 28].

Due to the work of Borcea and Brändén [1, 2, 3], a successful multivariate
generalization of real-rooted polynomials, called _stable polynomials_ , have
been developed. Now let us recall the notion of real stability, which
generalizes the notion of real-rootedness from univariate real polynomials to
multivariate real polynomials. Given a positive integer $n$, let $\bm{x}$ be
an $n$-tuple $(x_{1},\dots,x_{n})$. Let
$\mathbb{H}_{+}=\\{z\in\mathbb{C}:\mbox{Im}(z)>0\\}$ denote the open upper
complex half-plane. A polynomial $f\in\mathbb{R}[\bm{x}]$ is said to be (real)
_stable_ if $f(\bm{x})\neq 0$ for any $\bm{x}\in\mathbb{H}_{+}^{n}$ or $f$ is
identically zero. Note that a univariate polynomial $f(x)\in\mathbb{R}[x]$ is
stable if and only if it has only real roots. Multivariate stable polynomials
have been studied in many different areas, including control theory,
statistical mechanics, partial differential equations, and functional
analysis. See the surveys [5, 24, 30] for further applications of stable
polynomials. It is remarkable that an extension of stable polynomials, namely
_Lorentzian polynomials_ , was studied by Brändén and Huh [7].

A natural question to ask is to find a stable multivariate generalization of
real-rooted univariate polynomials in combinatorics. Several multivariate
polynomials have been found in combinatorics. The multivariate Eulerian
polynomials and more general Eulerian-like polynomials were introduced by
Brändén, Haglund, Visontai, and Wagner in [6] and used to prove a conjecture
of Haglund, Ono, and Wagner [6]. Subsequently, multivariate Eulerian
polynomials over Stirling permutations [15, 21], colored permutations [8, 29],
segmented permuations [32], and related combinatorial models have been
studied.

In this paper, we focus on finding stable multivariate generalizations of two
kinds of Narayana polynomials. The Narayana polynomial of type A, defined as
$N_{n}^{A}(x)=\sum_{k=1}^{n}\frac{1}{n}{n\choose k}{n\choose k-1}x^{k},$ is a
$q$-analogue of the famous Catalan number, and the coefficent of $x^{k}$ in
$N_{n}^{A}(x)$, usually called _Narayana number_ , counts Dyck paths of
semilength $n$ with $k$ peaks, or unlabeled plane trees with $n$ edges and $k$
leaves, see [27, A001263]. Remarkablely, Narayana polynomial of type A is also
the $h$-polynomial of the simplicial complex dual to an associahedron of type
$A_{n}$, see [20]. The Narayana polynomial of type B, defined as
$N_{n}^{B}(x)=\sum_{k=0}^{n}{n\choose k}^{2}x^{k},$ is the $h$-polynomial of
the simplicial complex dual to an associahedron of type $B_{n}$ (a
cyclohedron), see [27, A008459]. It is known that both $N_{n}^{A}(x)$ and
$N_{n}^{B}(x)$ are real-rooted for any integer $n\geq 1$, see Brändén [4], and
Liu and Wang [22].

Our multivariate polynomials are based on labeled plane trees. A labeled plane
tree with $n$ nodes refers to a rooted plane tree in which each node is
assigned a unique label from the set $[n]=\\{1,2,\ldots,n\\}$. Denote by
$\mathcal{T}_{n}$ the set of labeled plane trees with $n$ nodes and by
$\mathcal{T}^{*}_{n}$ the set of labeled plane trees in which the node
$\mathbf{1}$ is the first leaf of the node $\mathbf{1}$. Now we define

$F_{n}(\mathbf{x},\mathbf{y},s,t)=\sum_{T\in\mathcal{T}_{n+1}}{wt}(T)$

and

$F^{*}_{n}(\mathbf{x},\mathbf{y},s,t)=\sum_{T\in\mathcal{T}^{*}_{n}}{wt}(T).$

Here the details of the definition of ${wt}(T)$ will be given in Section 4.
Note that labeled plane trees are in bijections with quasi-Stirling
permutations, which have been extensively studied by Elizalde [19], and Yan
and Zhu [31].

Our construction of $F_{n}(\mathbf{x},\mathbf{y},s,t)$ and
$F^{*}_{n}(\mathbf{x},\mathbf{y},s,t)$ is inspired by a context-free grammar
as well as a grammatical labeling of labeled plane trees. Chen [11] initiated
the study of applications of context-free grammars to combinatorics. Chen and
Fu [13] introduced the notations of grammatical labelings to generate
combinatorial structures, such as permutations and increasing trees, via a
recursive process. Further study on grammatical labelings related to trees can
be found in [14, 15, 16].

The main result of this paper is as follows.

######  Theorem 1.

For any positive integer $n$, we have

  * (i)

$F_{n}(\mathbf{x},\mathbf{y},s,t)$ and $F^{*}_{n}(\mathbf{x},\mathbf{y},s,t)$
are multivariable generalizations of $N_{n}^{A}(x)$ and $N_{n}^{B}(x)$,
respectively. Namely,

$\displaystyle F_{n}(x,x,\ldots,x,1,1,\ldots,1,t,t)=(n+1)!t^{n}N_{n}^{A}(x),$
(1)

and

$\displaystyle
F^{*}_{n}(x,x,\ldots,x,1,1,\ldots,1,t,t)=n!t^{n+1}N_{n}^{B}(x).$ (2)

  * (ii)

$F_{n}(\mathbf{x},\mathbf{y},s,t)$ and $F^{*}_{n}(\mathbf{x},\mathbf{y},s,t)$
are stable in variables $\mathbf{x}$ and $\mathbf{y}$ for any positive real
numbers $s$ and $t$.

The rest of the paper is organized as follows. In Section 2, we introduce an
insertion algorithm on labeled plane trees. Section 3 is devoted to a context-
free grammar as well a grammatical labeling which can be used to generate
labeled plane trees. Our grammar can be transformed to a bivariate grammar of
Ma, Ma, and Yeh [23] during their study of Narayana polynomials. As
applications of our grammar, we give grammatical proofs of convolution
identities and generating functions of $N_{n}^{A}(x)$ and $N_{n}^{B}(x)$. In
Section 4, we define a refined grammatical labeling for labeled plane trees to
prove Theorem 1 by Borcea and Brändén’s characterization of stability-
preserving linear operators.

##  2 An insertion algorithm for labeled plane trees

For each edge of the tree, we call the node closer to the root as the _parent_
node of the edge, and the node farther from the root as the _child_ node of
the edge. Nodes with the same parent are called _siblings_ and the siblings to
the left of a node $v$ are called _elder_ siblings of $v$. Following [12], a
node is called _old_ if it is the leftmost child of its parent; otherwise, it
is _young_. For our convenience, we call the node labeled $i$ as node
$\mathbf{i}$.

In this section, we provide an insertion algorithm for labeled plane trees by
adding a new node $\mathbf{n+1}$ from a tree in $\mathcal{T}_{n}$ via one of
the following manners:

  * N1:

Choose a node $\mathbf{i}$, which can be a leaf or an interior vertex, and add
$\mathbf{n+1}$ to be the old leaf of $\mathbf{i}$. In the new tree, the node
$\mathbf{n+1}$ is an old leaf.

$i$$i$$n+1$

  * N2:

Choose a node $\mathbf{i}$, relabel the node $\mathbf{i}$ by $\mathbf{n+1}$,
and add a new node $\mathbf{i}$ as the old leaf of $\mathbf{n+1}$. In the new
tree, the node $\mathbf{n+1}$ is an interior node whose old child is a leaf.

$i$$n+1$$i$

  * E1:

Choose an edge $(\mathbf{i},\mathbf{j})$, and add $\mathbf{n+1}$ to be a leaf
as the younger brother of $\mathbf{j}$. In the new tree, the node
$\mathbf{n+1}$ is a young leaf.

$i$$j$$i$$j$$n+1$

  * E2:

Choose an edge $(\mathbf{i},\mathbf{j})$. We relabel $\mathbf{i}$ by
$\mathbf{n+1}$ and make $\mathbf{i}$ be the old child of $\mathbf{n+1}$.
Meanwhile, assign the elder siblings of $\mathbf{j}$ as well as itself to be
the children of $\mathbf{i}$, and assign the remaining children of
$\mathbf{i}$ to be the younger siblings of $\mathbf{i}$. In the new tree, the
node $\mathbf{n+1}$ is an interior node whose first child is interior.

$i$$k$$j$$n+1$$k$$i$$j$

For instance, the following sequence shows the progress of generating a
labeled plane tree with seven nodes.

N1N2N2E1E2E11123123142315426354216354217

The trees obtained in the four manners are different. We claim that the
insertion algorithm can generate all trees in $\mathcal{T}_{n+1}$ from trees
in $\mathcal{T}_{n}$. To do this, we just need to construct the corresponding
deletion algorithm for a tree $T\in\mathcal{T}_{n+1}$:

  * •

If the node $\mathbf{n+1}$ is a leaf, we delete the node directly;

  * •

If the node $\mathbf{n+1}$ is an interior node with the oldest child
$\mathbf{k}$, we contract the edge $(\mathbf{n+1},\mathbf{k})$ to a node
$\mathbf{k}$, and the children of $\mathbf{k}$ and $\mathbf{n+1}$ keep the
previous order respectively and the children of $\mathbf{k}$ is elder than the
children of $\mathbf{n+1}$.

It is not difficult to verify the deletion algorithm described above is well-
defined.

As a direct application of this insertion algorithm, we can give the following
combinatorial interpretation of the recurrence relation of Narayana numbers.

######  Proposition 2 ([17, 23]).

The Narayana numbers satisfy the following identity.

$\displaystyle(n+2)N(n+1,k)=(n+2k){N}(n,k)+(3n+4-2k){N}(n,k-1).$ (3)

Therefore, the Narayana polynomials satisfy

$\displaystyle(n+2)N_{n+1}^{A}(x)=\left((3n+2)x+n\right)N_{n}^{A}(x)+2(x-x^{2})\left(N_{n}^{A}(x)\right)^{\prime}.$
(4)

###### Proof.

It is known that the number of labeled plane trees on $n+1$ nodes with $k$
leaves are given by $(n+1)!N(n,k)$. We shall show that labeled plane trees on
$n+2$ nodes with $k$ leaves can be obtained from labeled plane trees on $n+1$
nodes via the following two cases:

  * •

Given a labeled plane tree on $n+1$ nodes with $k$ leaves, we have the option
to perform insertion either in Case E2 for every edge in the tree, or in Case
N1 and Case N2 for every leaf. Thus the number in this case is $n+2k$.

  * •

Given a labeled plane tree on $n+1$ nodes with $k-1$ leaves, we have the
option to perform insertion either in Case E1 for every edge in the tree, or
in Case N1 and Case N2 for every non-leaf node. Thus the number in this case
is $n+2(n+1-k+1)=3n+4-2k$.

This completes the proof of (3). ∎

Note that the recurrence relation (3) was found by Ma, Ma, and Yeh [23, Lemma
9], and (4) was found by Chen, Yang, and Zhao [17].

##  3 A context-free Grammar for Narayana Polynomials

In this section, we first introduce the notion of _improper edges_ on labeled
plane trees and then define a context-free grammar that can be used to
generate labeled plane trees as well as extensions of Narayana polynomials of
type A and type B. Our grammar also extends the grammar given by Ma, Ma, and
Yeh [23] during their study of Narayana polynomials. Besides, as an
application of our grammar, we give a grammatical proof of a convolution
identity and a formula of the generating function of $N_{n}^{A}(x)$ and
$N_{n}^{B}(x)$. For the sake of convenience, we consider a homogeneous version
of $N_{n}^{A}(x)$ and $N_{n}^{B}(x)$ as

$N_{n}^{A}(x,y)=\sum_{k=1}^{n}\frac{1}{n}{n\choose k}{n\choose
k-1}x^{k}y^{n-k+1},$

and

$N_{n}^{B}(x,y)=\sum_{k=0}^{n}{n\choose k}^{2}x^{k}y^{n-k}.$

Here we set $N_{0}^{A}(x,y)=y.$

Inspired by Shor’s work [26] on Cayley trees, we define improper edges on
labeled plane trees as follows. Given a labeled plane tree $T$, we define the
$\beta$-value of a node $\mathbf{j}$, denoted $\beta(\mathbf{j})$, as the
smallest label on any node in the subtree rooted at $\mathbf{i}$ (it is
possible that $\beta(\mathbf{j})={j}$). Meanwhile, we define the
$\alpha$-value of a node $\mathbf{j}$, denoted $\alpha(\mathbf{j})$, to be the
minimum among the label of its father and the $\beta$-values of its elder
brothers. Precisely, let $\mathbf{i}$ be the father of $\mathbf{j}$ and
suppose that
$\mathbf{k_{1}},\mathbf{k_{2}},\cdots,\mathbf{k_{t-1}},\mathbf{j},\mathbf{k_{t+1}},\cdots,\mathbf{k_{m}}$
are the children of $\mathbf{i}$ listed from left to right. Then
$\alpha(\mathbf{j})$ is defined as

$\alpha(\mathbf{j})=\min\left({i},\beta(\mathbf{k_{1}}),\beta(\mathbf{k_{2}}),\cdots,\beta(\mathbf{k_{t-1}})\right).$

The edge $e=(\mathbf{i},\mathbf{j})$ is called _proper_ if
$\alpha(\mathbf{j})<\beta(\mathbf{j})$; otherwise, it is called _improper_.
Take the tree $T$ in Figure 1 for instance. The edge $(\mathbf{4},\mathbf{2})$
is an improper edge since $\alpha(\mathbf{2})=4$ and $\beta(\mathbf{2})=2$.
Meanwhile, the edge $(\mathbf{6},\mathbf{4})$ is a proper edge since since
$\alpha(\mathbf{4})=1$ and $\beta(\mathbf{4})=2$.

Notice that Cayley trees can be considered as labeled plane trees where the
children of each node are arranged in increasing order of their
$\beta$-values. It is worth noting that an edge $e=(\mathbf{i},\mathbf{j})$ in
a Cayley tree $T$ is improper if and only $i>\beta(j)$. Thus the definition of
improper edges can be viewed as a generalization of the definition of Cayley
trees given by Shor.

Let $\widetilde{N}(n,k,r)$ denote the number of labeled trees on $[n+1]$ with
$k$ leaves and $r$ improper edges. We define a homogeneous multivariable
polynomial:

$\widetilde{N}_{n}^{A}(x,y,s,t)=\sum_{k,r}\widetilde{N}(n,k,r)s^{n-r}t^{r}x^{k}y^{n-k+1}.$

Especially, we set $\widetilde{N}_{0}^{A}(x,y,s,t)=y$. It can be seen that
$\widetilde{N}_{n}^{A}(x,y,1,1)=(n+1)!N_{n}^{A}(x,y)$.

Following Chen [11], a context-free grammar $G$ over an alphabet set
$A=\\{x,y,z,\ldots\\}$ of variables is a collection of substitution rules that
replace a variable in $A$ with a Laurent polynomial of variables in $A$. The
formal derivative $D$ associated with a context-free grammar $G$ over $A$ is a
linear operator that acts on Laurent polynomials with variables in $A$ and
satisfies the following relations for each substitution rule:

$\displaystyle D(u+v)=D(u)+D(v),$ $\displaystyle D(uv)=D(u)v+uD(v).$

Dumont and Ramamonjisoa [18] found a grammar $\\{A\rightarrow
A^{3}S,S\rightarrow AS^{2}\\}$ to generate Cayley trees.

We next pose the following grammar on the alphabet $A=\\{s,t,x,y\\}$,

$G:=\\{s\rightarrow s(sx+ty),t\rightarrow
t(sx+ty),x\rightarrow(s+t)xy,y\rightarrow(s+t)xy\\}$ (5)

to generate labeled plane trees, as well as Narayana polynomials. Let $D$
denote the formal derivative concerning the grammar (5). The next theorem
shows the relation between the grammar (5) and labeled rooted trees.

######  Theorem 3.

For any integer $n\geq 0$, we have

$D^{n}(y)=\widetilde{N}_{n}^{A}(x,y,s,t).$ (6)

Proof. It is evident for $n=0$. For $n\geq 1$, in order to complete the proof,
we introduce a grammatical labeling of labeled rooted trees. For a tree
$T\in\mathcal{T}_{n}$, we label each leaf by $x$ and label each interior node
by $y$. Meanwhile, we label each proper edge by $t$ and label each improper
edge by $s$. Finally, we define the weight of $T$ to be the product of all the
labels on $T$, namely,

$wt(T)=s^{prop(T)}t^{imp(T)}x^{\ell(T)}y^{i(T)}.$

Here we use $prop(T)$, $imp(T)$, $\ell(T)$, and $i(T)$ to denote the number of
proper edges, improper edges, leaves, and interior nodes in $T$, respectively.
For instance, the tree $T$ has the grammatical labeling as shown in Figure 1
and $wt(T)=s^{3}t^{3}x^{4}y^{3}$.

$6(y)$$3(y)$$1(x)$$t$$7(x)$$s$$t$$5(x)$$s$$4(y)$$2(x)$$t$$s$ Figure 1: A
labeled plane tree with the grammatical labeling

This implies that (6) is equivalent to

$D^{n}(y)=\sum_{T\in\mathcal{T}_{n+1}}wt(T).$ (7)

We prove the relation (7) by induction on $n$. For $n=1$, (7) holds since the
two trees in $\mathcal{T}_{2}$ are with labels $sxy$ and $txy$. Now we assume
that (7) holds for $n-1$, that is,

$D^{n-1}(x)=\sum_{T\in\mathcal{T}_{n}}wt(T).$

To show that (7) holds for $n$, we turn to establish the relationship between
labeled rooted trees and grammar (5).

Let us recall the four cases of insertion steps of the node $\mathbf{n+1}$.
Here we view the insertion in Case N1 and Case N2 as an action on a node and
view the insertion in Case E1 and Case E2 as an action on an edge. Consider a
tree $T$ in $\mathcal{T}_{n}$.

If we add a new node $\mathbf{n+1}$ as in Case N1 and Case N2, we first choose
a node $\mathbf{i}$, labeled by $x$ or $y$.

  * •

When we add $\mathbf{n+1}$ to be the old leaf of $\mathbf{i}$ as Case N1, we
assign $x$ to the new leaf $\mathbf{n+1}$, and assign $t$ to the new edge
$(\mathbf{i},\mathbf{n+1})$. We label the node $\mathbf{i}$ by $y$, no matter
$y$ or $x$ is assigned to $\mathbf{i}$ in $T$.

  * •

When we add $\mathbf{n+1}$ to be the father node of $\mathbf{i}$ as Case N2,
we assign $y$ to the new leaf $\mathbf{n+1}$, and assign $t$ to the new edge
$(\mathbf{n+1},\mathbf{i})$. We label the node $\mathbf{i}$ by $x$, no matter
$y$ or $x$ is assigned to $\mathbf{i}$ in $T$.

Combining both two cases, whether the target node is labeled by a letter $y$
or $x$, we get $zwt+zws$, which is equivalent to the action of the
substitution rule $y\rightarrow(s+t)xy$ or $x\rightarrow(s+t)xy$.

For instance, if we apply $y\rightarrow(s+t)xy$ to the label $y$ on the node
$\mathbf{6}$, we get two new trees $T_{1}$ and $T_{2}$ in $\mathcal{T}_{8}$
with weights $wt(T_{1})=s^{4}t^{3}x^{5}y^{3}$ and
$wt(T_{2})=s^{3}t^{4}x^{5}y^{3}$. Clearly, the trees $T_{1}$ and $T_{2}$ are
labeled by consistent grammatical labels as shown in Figure 2.

$6(y)$$8(x)$$s$$3(y)$$1(x)$$t$$7(x)$$s$$t$$5(x)$$s$$4(y)$$2(x)$$t$$s$ (a)
$wt(T_{1})=s^{4}t^{3}x^{5}y^{3}$

$8(y)$$6(x)$$t$$3(y)$$1(x)$$t$$7(x)$$s$$t$$5(x)$$s$$4(y)$$2(x)$$t$$s$ (b)
$wt(T_{2})=s^{3}t^{4}x^{5}y^{3}$

Figure 2: An examples for $y\rightarrow(s+t)xy$

If we apply $x\rightarrow(s+t)xy$ to the label $x$ on the node $\mathbf{5}$,
we get two new trees $T_{3}$ and $T_{4}$ in $\mathcal{T}_{8}$ with weights
$wt(T_{3})=s^{4}t^{3}x^{4}y^{4}$ and $wt(T_{4})=s^{3}t^{4}x^{4}y^{4}$. The
trees $T_{3}$ and $T_{4}$ are labeled by consistent grammatical labels as
shown in Figure 3.

$6(y)$$3(y)$$1(x)$$t$$7(x)$$s$$t$$5(y)$$8(x)$$s$$s$$4(y)$$2(x)$$t$$s$ (a)
$wt(T_{3})=s^{4}t^{3}x^{4}y^{4}$

$6(y)$$3(y)$$1(x)$$t$$7(x)$$s$$t$$8(y)$$5(x)$$t$$s$$4(y)$$2(x)$$t$$s$ (b)
$wt(T_{4})=s^{3}t^{4}x^{4}y^{4}$

Figure 3: An examples for $x\rightarrow(s+t)xy$

If we add a new node $\mathbf{n+1}$ as in Case E1 and Case E2, we first choose
an edge $(\mathbf{i},\mathbf{j})$, which is labeled by a letter $t$ or $s$.

  * •

When we add $\mathbf{n+1}$ to be the younger brother of $\mathbf{j}$ as Case
E1, we keep all old labels on $T$, assign $x$ to the new leaf $\mathbf{n+1}$,
and assign $s$ to the new proper edge $(\mathbf{i},\mathbf{n+1})$.

  * •

When we add $\mathbf{n+1}$ to be the father of $\mathbf{i}$ as Case E2, we
keep all old labels on $T$, assign $y$ to the new interior node
$\mathbf{n+1}$, and assign $t$ to the new edge $(\mathbf{n+1},\mathbf{i})$.

Combining both two cases, whether the target edge is labeled by a letter $t$
or $s$, we obtain new labels $sx+ty$, which is equivalent to the action of the
substitution rule $s\rightarrow s(sx+ty)$ or $t\rightarrow t(sx+ty)$.

For instance, if we apply $s\rightarrow s(sx+ty)$ to the label $s$ on the edge
$(\mathbf{3},\mathbf{1})$, we get two new trees $T_{5}$ and $T_{6}$ in
$\mathcal{T}_{8}$ with weights $wt(T_{5})=s^{3}t^{4}x^{5}y^{3}$ and
$wt(T_{6})=s^{3}t^{4}x^{4}y^{4}$. Clearly, the trees $T_{5}$ and $T_{6}$ are
labeled by consistent grammatical labels as shown in Figure 4.

$6(y)$$3(y)$$1(x)$$t$$8(x)$$s$$7(x)$$t$$t$$5(x)$$s$$4(y)$$2(x)$$t$$s$ (a)
$wt(T_{5})=s^{3}t^{4}x^{5}y^{3}$

$6(y)$$8(y)$$3(y)$$1(x)$$t$$t$$7(x)$$s$$t$$5(x)$$s$$4(y)$$2(x)$$t$$s$ (b)
$wt(T_{6})=s^{3}t^{4}x^{4}y^{4}$

Figure 4: An examples for $s\rightarrow s(sx+ty)$

If we apply $t\rightarrow t(sx+ty)$ to the label $t$ on the edge
$(\mathbf{6},\mathbf{3})$, we get two new trees $T_{7}$ and $T_{8}$ in
$\mathcal{T}_{8}$ with weights $wt(T_{7})=s^{4}t^{3}x^{5}y^{3}$ and
$wt(T_{8})=s^{4}t^{3}x^{4}y^{4}$. Clearly, the trees $T_{7}$ and $T_{8}$ are
labeled by consistent grammatical labels as shown in Figure 5.

$6(y)$$3(y)$$1(x)$$t$$7(x)$$s$$t$$8(x)$$s$$5(x)$$s$$4(y)$$2(x)$$t$$s$ (a)
$wt(T_{7})=s^{4}t^{3}x^{5}y^{3}$

$8(y)$$6(y)$$3(y)$$1(x)$$t$$7(x)$$s$$t$$t$$5(x)$$s$$4(y)$$2(x)$$t$$s$ (b)
$wt(T_{8})=s^{3}t^{4}x^{4}y^{4}$

Figure 5: An examples for $t\rightarrow t(sx+ty)$

Above all, the action of the operator $D$ on $wt(T)$ is equivalent to the
insertion of $\mathbf{n+1}$ into $T$. Thus we have

$D^{n}(x)=D\left(\sum_{T\in\mathcal{T}_{n}}wt(T)\right)=\sum_{T^{*}\in\mathcal{T}_{n+1}}wt(T^{*}).$

This completes the proof.∎

Next, we give a combinatorial description of Narayana polynomials of Type B in
the notion of labeled rooted trees.

Let $\mathcal{T}^{*}_{n}$ denote the set of labeled plane trees on $[n+2]$ in
which $\mathbf{1}$ is the old child of $\mathbf{2}$. Let
$\widetilde{N}_{B}(n,k,r)$ denote the number of labeled rooted trees in
$\mathcal{T}^{*}_{n}$ with $k$ leaves and $r$ improper edges. Define
$\widetilde{N}^{B}_{n}(x,y,s,t)$ as follows:

$\widetilde{N}^{B}_{n}(x,y,s,t)=\sum_{k,r}\widetilde{N}_{B}(n,k,r)s^{n+1-r}t^{r}x^{k-1}y^{n-k+1}.$

######  Lemma 4.

For $n\geq 0$, it holds that

$\widetilde{N}^{B}_{n}(x,y,t,t)=n!t^{n+1}N_{n}^{B}(x,y).$ (8)

In order to prove (8), we need the following conclusion given by Chen,
Deutsch, and Elizalde [12].

######  Lemma 5 ([12]).

The number of unlabeled plane trees with $n+1$ nodes, $k$ leaves, and $i$ old
leaves is

$r_{n,k,i}=\frac{1}{n}{n\choose i}{n-i\choose k-i}{n-k\choose i-1}.$

###### Proof of Lemma 4.

It can be seen that

$\displaystyle\widetilde{N}^{B}_{n}(x,y,t,t)$
$\displaystyle=t^{n+1}\sum_{T\in\mathcal{T}^{*}_{n}}x^{\ell(T)-1}y^{i(T)-1}$
$\displaystyle=n!\,t^{n+1}\sum_{T\in\mathcal{U}_{n+2}}ol(T)\cdot
x^{\ell(T)-1}y^{i(T)-1},$

where $\mathcal{U}_{n}$ denotes the set of unlabeled rooted tress with $n$
nodes, and $ol(T)$ denotes the number of old leaves of $T$. The last equation
holds since a tree in $\mathcal{T}^{*}_{n}$ can be obtained from an unlabeled
tree $T$ with $n+2$ nodes by labeling freely $\\{3,4,\ldots,n+2\\}$ on all
nodes of $T$ except for an old leaf and its father.

It follows from Lemma 5 that

$\displaystyle\sum_{T\in\mathcal{U}_{n+2}}ol(T)x^{\ell(T)-1}$
$\displaystyle=\sum_{1\leq i\leq k\leq n+1}ir_{n+1,k,i}x^{k-1}y^{n-k+1}$
$\displaystyle=\sum_{1\leq i\leq k\leq n+1}i\frac{1}{n+1}{n+1\choose
i}{n+1-i\choose k-i}{n+1-k\choose i-1}x^{k-1}y^{n-k+1}$
$\displaystyle=\sum_{i\leq k\leq n+1}{n\choose k-1}{k-1\choose
k-i}{n+1-k\choose i-1}x^{k-1}y^{n-k+1}$
$\displaystyle=\sum_{k=1}^{n+1}x^{k-1}y^{n-k+1}{n\choose
k-1}\sum_{i=1}^{k}{k-1\choose k-i}{n+1-k\choose i-1}=\sum_{k=0}^{n}{n\choose
k}^{2}x^{k}y^{n-k}.$

The last equation holds from the famous Vandermonde’s identity. ∎

######  Theorem 6.

Let $D$ denote the formal derivative associated with grammar (5). For any
integer $n\geq 0$, we have

$D^{n}(t)=\widetilde{N}^{B}_{n}(x,y,s,t).$ (9)

Proof. For a tree $T$ in $\mathcal{T}^{*}_{n}$, we define the weight of $T$ as
a normal labeled rooted tree, except for the labels on the node $\mathbf{1}$
and $\mathbf{2}$. Then a tree $T$ in $\mathcal{T}^{*}_{n}$ with $k$ leaves and
$r$ improper edges has the weight $wt(T)=s^{n+1-r}t^{r}x^{k-1}y^{n-k+1}$,
which implies (9) is equivalent to

$D^{n}(t)=\sum_{T\in\mathcal{T}^{*}_{n}}wt(T).$ (10)

For $n=0$, the only tree in $\mathcal{T}^{*}_{0}$ is the tree on $[2]$ where
$\mathbf{2}$ is root, whose weight is $t$. Now consider a tree in
$\mathcal{T}^{*}_{n-1}$. Notice that there is no label in $\mathbf{1}$ and
$\mathbf{2}$. Thus we forbid the insertion of $\mathbf{n+2}$ on $\mathbf{1}$
and $\mathbf{2}$. Since we do not insert $\mathbf{n+2}$ on $\mathbf{1}$, the
node $\mathbf{1}$ is always a leaf. Since we do not insert $\mathbf{n+2}$ on
$\mathbf{2}$, the node $\mathbf{1}$ is always the first child of $\mathbf{2}$.
This completes the proof. ∎

Setting $s=t$ in grammar (5), we get a grammatical description of
$N_{n}^{A}(x,y)$ and $N_{n}^{B}(x,y)$.

######  Theorem 7.

Let $D_{H}$ denote the formal derivative associated with the grammar

$H:=\\{t\rightarrow t^{2}(x+y),x\rightarrow 2txy,y\rightarrow 2txy\\}.$ (11)

For $n\geq 0$, it holds that

$\displaystyle D_{H}^{n}(y)$ $\displaystyle=(n+1)!t^{n}N_{n}^{A}(x,y),$ (12)
$\displaystyle D_{H}^{n}(t)$ $\displaystyle=n!t^{n+1}N_{n}^{B}(x,y).$ (13)

Especially,

$\displaystyle D_{H}^{n}(y)|_{y=1}$ $\displaystyle=(n+1)!t^{n}N_{n}^{A}(x),$
(14) $\displaystyle D_{H}^{n}(t)|_{y=1}$
$\displaystyle=n!t^{n+1}N_{n}^{B}(x).$ (15)

This implies Equation (13). ∎

######  Remark 8.

Ma, Ma, and Yeh [23] provided a context-free grammar

$\\{u\rightarrow u^{2}v^{3},v\rightarrow u^{3}v^{2}\\},$ (16)

and showed that

$D^{n}(u^{2})=(n+1)!\sum_{k=0}^{n}N(n,k)u^{3n-2k+2}v^{n+2k}$

and

$D^{n}(uv)=n!\sum_{k=0}^{n}\binom{n}{k}^{2}u^{3n-2k+1}v^{n+2k+1}.$

By setting $t=uv,x=u^{2},y=v^{2}$, the grammar (11) can be changed into the
grammar (16).

As an application of the grammar $H$ given in (11), we next show a grammatical
proof of the following convolution identities of $N_{n}^{A}(x,y)$ and
$N_{n}^{B}(x,y)$. Note that our definition of $N_{n}^{A}(x)$ here is different
from that in Petersen [25] due to a shift of $x$.

######  Theorem 9.

For $n\geq 2$,

$\displaystyle N_{n}^{A}(x,y)$
$\displaystyle=(x+y)N_{n-1}^{A}(x,y)+\sum_{k=2}^{n-1}N_{k-1}^{A}(x,y)N_{n-k}^{A}(x,y)\,\,(\cite[cite]{[\@@bibref{}{Petersen2015Eulerian}{}{},
Theorem 2.2]}),$ (17) $\displaystyle N_{n}^{B}(x,y)$
$\displaystyle=(x+y)N_{n-1}^{B}(x,y)+2\sum_{k=0}^{n-2}N_{k}^{B}(x,y)N_{n-k-1}^{A}(x,y).$
(18)

Proof. Consider the following Leibnitz-type convolution

$D_{H}^{n}(t^{-2})=\sum_{k=0}^{n}{n\choose
k}D_{H}^{k}(t^{-1})D_{H}^{n-k}(t^{-1}).$ (19)

One can verify that

$D_{H}(t^{-2})=-2t^{-1}(x+y),\quad D_{H}^{2}(t^{-2})=2(y-x)^{2},\quad
D_{H}^{n}(t^{-2})=0,\mbox{ for }n\geq 3,$

and

$D_{H}(t^{-1})=-(x+y),\quad
D_{H}^{n}(t^{-1})=-2n!t^{n-1}N_{n-1}^{A}(x,y),\mbox{ for }n\geq 2.$

Thus for $n\geq 3$, the left side of (19) vanishes, while the right side of
(19) can be calculated as follows,

$R.H.S.=2t^{-1}D_{H}^{n}(t^{-1})+2nD_{H}(t^{-1})D_{H}^{n-1}(t^{-1})+\sum_{k=2}^{n-2}{n\choose
k}D_{H}^{k}(t^{-1})D_{H}^{n-k}(t^{-1}),$

which can be reduced to

$-4n!t^{n-2}N_{n-1}^{A}(x,y)+4n!(x+y)t^{n-2}N_{n-2}^{A}(x,y)+4n!t^{n-2}\sum_{k=2}^{n-2}N_{k-1}^{A}(x,y)N_{n-k-1}^{A}(x,y).$

Now we get

$N_{n-1}^{A}(x,y)=(x+y)N_{n-2}^{A}(x,y)+\sum_{k=2}^{n-2}N_{k-1}^{A}(x,y)N_{n-k-1}^{A}(x,y),$

which is equivalent to (17).

Similarly, (18) can be obtained in a similar calculation from the following
Leibnitz-type convolution

$0=D_{H}^{n}(1)=\sum_{k=0}^{n}{n\choose k}D_{H}^{k}(t)D_{H}^{n-k}(t^{-1}).$

This completes the proof. ∎

Let $C^{A}(x,y,z)$ and $C^{B}(x,y,z)$ denote the generating function of
Narayana polynomials of type A and type B, respectively. Namely,

$\displaystyle C^{A}(x,y,z)$ $\displaystyle=\sum_{n\geq
0}N_{n}^{A}(x,y)z^{n},$ (20) $\displaystyle C^{B}(x,y,z)$
$\displaystyle=\sum_{n\geq 0}N_{n}^{B}(x,y)z^{n}.$ (21)

Let $\mathop{\mathbf{Gen}}\nolimits(f,t)$ be the generating function of a
Laurent polynomial $f$ associated with the operator $D$, as defined by

$\mathop{\mathbf{Gen}}\nolimits(f,t)=\sum_{n=0}^{\infty}D^{n}(f)\frac{t^{n}}{n!}.$

The following relations of $\mathop{\mathbf{Gen}}\nolimits(f,t)$ are fisrt
given by Chen [11]:

$\displaystyle\mathop{\mathbf{Gen}}\nolimits(f+g,t)$
$\displaystyle=\mathop{\mathbf{Gen}}\nolimits(f,t)+\mathop{\mathbf{Gen}}\nolimits(g,t),$
$\displaystyle\mathop{\mathbf{Gen}}\nolimits(f\cdot g,t)$
$\displaystyle=\mathop{\mathbf{Gen}}\nolimits(f,t)\cdot\mathop{\mathbf{Gen}}\nolimits(g,t),$
$\displaystyle\frac{d}{dt}\mathop{\mathbf{Gen}}\nolimits(f,t)$
$\displaystyle=\mathop{\mathbf{Gen}}\nolimits(D(f),t).$

Based on the relation (17), Petersen [25] provided a formula for
$C^{A}(x,y,z)$. Here we give a grammatical proof in the following equivalent
form. Our approach also leads to a formula for $C^{B}(x,y,z)$.

######  Theorem 10.

We have

$\displaystyle C^{A}(x,y,z)$
$\displaystyle=\frac{1+(y-x)z-\sqrt{1-2(x+y)z+(y-x)^{2}z^{2}}}{2z}\,(\cite[cite]{[\@@bibref{}{Petersen2015Eulerian}{}{},
Equation\, (2.6)]}),$ (22) $\displaystyle C^{B}(x,y,z)$
$\displaystyle=\frac{1}{\sqrt{1-2(x+y)z+(y-x)^{2}z^{2}}}.$ (23)

Proof. Notice that

$D_{H}(t^{-2})=-2t^{-1}(y+x),\quad D_{H}^{2}(t^{-2})=2(y-x)^{2},\quad
D_{H}^{n}(t^{-2})=0,\mbox{ for }n\geq 3,$

We obtain

$\mathop{\mathbf{Gen}}\nolimits(t^{-2},u)=t^{-2}-2t^{-1}(y+x)u+(y-x)^{2}u^{2}.$

Equivalently,

$\mathop{\mathbf{Gen}}\nolimits(t^{-1},u)={\sqrt{t^{-2}-2t^{-1}(y+x)u+(y-x)^{2}u^{2}}}.$

Thus,

$\mathop{\mathbf{Gen}}\nolimits(t,u)=\frac{1}{\sqrt{t^{-2}-2t^{-1}(y+x)u+(y-x)^{2}u^{2}}}.$

It follows from (13) and (21) that

$\mathop{\mathbf{Gen}}\nolimits(t,u)=tC^{B}(x,y,tu),$

which leads to Equation (23).

According to $D_{H}(-t^{-1})=y+x$, it holds that

$\displaystyle\mathop{\mathbf{Gen}}\nolimits(-t^{-1},u)$
$\displaystyle=-t^{-1}+(x+y)u+2\sum_{n\geq 2}D_{H}^{n-1}(x)\frac{u^{n}}{n!}$
$\displaystyle=-t^{-1}+(x+y)u+2\sum_{n\geq 2}N^{A}_{n-1}(x,y)t^{n-1}u^{n}$
$\displaystyle=-t^{-1}+(x+y)u+2u\left(C^{A}(x,y,tu)-y\right).$

This implies

$C^{A}(x,y,tu)=\frac{1+(y-x)tu-\sqrt{1-2(x+y)tu+(y-x)^{2}t^{2}u^{2}}}{2tu},$

which is equivalent to Equation (22). This completes the proof. ∎

##  4 Stable multivariate Narayana polynomials

In this section, through a multivariable refinement of the Narayana grammar,
we acquire a stable multivariate generalization of Narayana polynomials.

We first define a refined grammatical labeling for a labeled plane tree
$T\in\mathcal{T}_{n}$. We assign variables to each node and edge in $T$ as
follows. Following the previous section, we assign the variable $s$ to an edge
$(\mathbf{i},\mathbf{j})$ if it is proper, and assign the variable $t$
otherwise.

  * •

For a leaf $\mathbf{i}$ in $T$, let $k=\max\\{i,\alpha(\mathbf{i})\\}$. We
assign the variable $w_{k}$ to the leaf $\mathbf{i}$.

  * •

For an interior node $\mathbf{i}$, let $k=\max\\{{i,\beta(\mathbf{j})}\\}$,
where $\mathbf{j}$ is the eldest child of $\mathbf{i}$. We assign the variable
$z_{k}$ to the interior node $\mathbf{i}$.

Finally, we define the refined weight of the tree $T$, denoted ${wt}(T)$, as
the product of the variables corresponding to all nodes and edges of $T$.

Consider the following refined context-free grammar:

$G_{n}=\\{x_{k}\rightarrow(s+t)x_{n}y_{n},\,y_{k}\rightarrow(s+t)x_{n}y_{n},\,s\rightarrow
s(sx_{n}+ty_{n}),\,t\rightarrow t(sx_{n}+ty_{n})\\}.$

Recall the insertion of the node $\mathbf{n+1}$, the following relation
between the grammar $G_{n}$ and the polynomial
$F_{n}(\mathbf{x},\mathbf{y},s,t)$ and $F_{n}^{*}(\mathbf{x},\mathbf{y},s,t)$
is obvious.

######  Corollary 11.

Let $D_{n}$ be the linear operator associated with $G_{n}$. For $n\geq 1$, it
holds that

$F_{n}(\mathbf{x},\mathbf{y},s,t)=D_{n+1}D_{n}\cdots D_{2}(y_{1})$ (24)

and

$F^{*}_{n}(\mathbf{x},\mathbf{y},s,t)=\frac{1}{t}D_{n}D_{n-1}\cdots D_{1}(t).$
(25)

We can prove the first part of Theorem 1.

###### Proof of Theorem 1 (i).

$G_{n}$ can be reduced to $G$, as given in (5), by setting $x_{k}=x$ and
$z_{k}=y$. According to Theorem 7, we know that
$F_{n}(\mathbf{x},\mathbf{y},s,t)$ (respectively
$F^{*}_{n}(\mathbf{x},\mathbf{y},s,t)$ ) is a generalization of $N_{n}^{A}(x)$
(respectively $N_{n}^{B}(x)$). ∎

To prove the stability of multivariate polynomials, we need a multi-affine
version of Borcea and Brändén’s characterization. A polynomial $f(\bm{x})$ is
said to be _multiaffine_ if the power of each indeterminate $x_{i}$ is at most
one. For a set $\mathcal{P}$ of polynomials, let $\mathcal{P}^{MA}$ be the set
of multi-affine polynomials in $\mathcal{P}$. Borcea and Brändén [1] gave a
complete characterization of the linear operators which preserve stable
multivariate polynomials.

######  Lemma 12 ([30, Theorem 3.5]).

Let $T:\mathbb{R}[\bm{x}]^{MA}\to\mathbb{R}[\bm{x}]$ be a linear operator
acting on the variables $\bm{x}=(x_{1},\dots,x_{n})$. If the polynomial

$G_{T}:=T\left(\prod_{i=1}^{n}(x_{i}+\hat{x}_{i})\right)$

is a stable polynomial of variables $\bm{x}=(x_{1},x_{2},\ldots,x_{n})$ and
$\bm{\hat{x}}=(\hat{x}_{1},\hat{x}_{2},\ldots,\hat{x}_{n})$, then $T$
preserves real stability.

Now we prove the second part of Theorem 1.

###### Proof of Theorem 1 (ii).

Let $F_{n}=F_{n}(\mathbf{x},\mathbf{y},s,t)$ and
$F^{*}_{n}=F_{n}(\mathbf{x},\mathbf{y},s,t)$. We first show the following
recursion $F_{n}=T_{n}\left(F_{n-1}\right)$, where

$T_{n}=n(s\,x_{n}+t\,y_{n})+(s+t)x_{n}y_{n}\sum_{k=1}^{n-1}\left(\frac{\partial}{\partial
x_{k}}+\frac{\partial}{\partial y_{k}}\right)$

is a linear operator.

We proceed to show the linear operator $T_{n}$ preserves real stability.
Recall that
$G_{T_{n}}=T_{n}\left(\prod_{k=1}^{n-1}(x_{k}+\hat{x}_{k})(y_{k}+\hat{y}_{k})\right).$
The linear operator $T_{n}$ actions on the $\mathbf{x}$\- and
$\mathbf{y}$-variables and treats the variables $s,t$ as positive real
constants. Now

$\displaystyle\frac{G_{T_{n}}}{x_{n}y_{n}\prod_{k=1}^{n-1}(x_{k}+\hat{x}_{k})(y_{k}+\hat{y}_{k})}$
$\displaystyle=n\left(\frac{s}{y_{n}}+\frac{t}{x_{n}}\right)+(s+t)\sum_{k=1}^{n-1}\left(\frac{1}{x_{k}+\hat{x}_{k}}+\frac{1}{y_{k}+\hat{y}_{k}}\right).$

Each term on the right side has a negative imaginary part whenever all
variables have positive imaginary parts. Hence $G_{T_{n}}$ is stable and the
theorem follows from Lemma 12. ∎

Once multivariate polynomials are shown to be stable, we can then reduce them
to real stable univariate polynomials by using the following operations.

######  Lemma 13 ([30, Lemma 2.4]).

Given $i,j\in[n]$, the following operations preserve real stability of
$f\in\mathbb{R}[\bm{x}]$:

  * •

_Differentiation:_ $f\mapsto\partial f/\partial x_{i}.$

  * •

_Diagonalization:_ $f\mapsto f|_{x_{i}=x_{j}}.$

  * •

_Specialization:_ for $a\in\mathbb{R}$, $f\mapsto f|_{x_{i}=a}.$

As an application of Theorem 1, we derive the following result from Lemma 13.

######  Theorem 14.

For any positive real numbers $s$ and $t$, the polynomials
$\sum_{k}\sum_{r}\widetilde{N}(n,k,r)s^{n-r}t^{r}x^{k}$ and
$\sum_{k}\sum_{r}\widetilde{N}_{B}(n,k,r)s^{n+1-r}t^{r}x^{k}$ have only real
roots.

Acknowledgments. Yang was supported by the National Science Foundation of
China (No. 12001404), and Zhang was supported by the National Science
Foundation of China (No. 12171362).

## References

  * [1] J. Borcea and P. Brändén, The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability, _Invent. Math._ , 177 (2009), 541–569.
  * [2] J. Borcea and P. Brändén, The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications, _Comm. Pure Appl. Math._ , 62 (2009), 1595–1631.
  * [3] J. Borcea and P. Brändén, Pólya-Schur master theorems for circular domains and their boundaries, _Ann. of Math._ , 170 (2009), 465–492.
  * [4] P. Brändén, On linear transformations preserving the Pólya frequency property, _Trans. Amer. Math. Soc._ , 358 (2006), 3697–3716.
  * [5] P. Brändén, Unimodality, log-concavity, real-rootedness and beyond, in _Handbook of Enumerative Combinatorics, Edited by Miklós Bóna_ , 437–484, CRC Press, Boca Raton, FLress, 2015.
  * [6] P. Brändén, J. Haglund, M. Visontai, and D. G. Wagner, Proof of the monotone column permanent conjecture, in _Notions of positivity and the geometry of polynomials_ , Trends Math., 63–78, Birkhäuser/Springer Basel AG, Basel, 2011.
  * [7] P. Brändén and J. Huh, Lorentzian polynomials, _Ann. of Math. (2)_ , 192 (2020), 821–891.
  * [8] P. Brändén, M. Leander, and M. Visontai, Multivariate Eulerian polynomials and exclusion processes, _Combin. Probab. Comput._ , 25 (2016), 486–499.
  * [9] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, _Mem. Amer. Math. Soc._ , 81 (1989), viii+106.
  * [10] F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, in _Jerusalem combinatorics ’93_ , vol. 178 of _Contemp. Math._ , 71–89, Amer. Math. Soc., Providence, RI, 1994.
  * [11] W. Y. C. Chen, Context-free grammars, differential operators and formal power series, vol. 117, 113–129, 1993. Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991).
  * [12] W. Y. C. Chen, E. Deutsch, and S. Elizalde, Old and young leaves on plane trees, _European J. Combin._ , 27 (2006), 414–427.
  * [13] W. Y. C. Chen and A. M. Fu, Context-free grammars for permutations and increasing trees, _Adv. in Appl. Math._ , 82 (2017), 58–82.
  * [14] W. Y. C. Chen, A. M. Fu, and S. H. F. Yan, The Gessel correspondence and the partial $\gamma$-positivity of the Eulerian polynomials on multiset Stirling permutations, _European J. Combin._ , 109 (2023), 103655.
  * [15] W. Y. C. Chen, R. X. J. Hao, and H. R. L. Yang, Context-free grammars and stable multivariate polynomials over Stirling permutations, in _Algorithmic combinatorics: enumerative combinatorics, special functions and computer algebra—in honour of Peter Paule on his 60th birthday_ , Texts Monogr. Symbol. Comput., 109–135, Springer, Cham, 2020.
  * [16] W. Y. C. Chen and H. R. L. Yang, A context-free grammar for the Ramanujan-Shor polynomials, _Adv. in Appl. Math._ , 126 (2021), 101908.
  * [17] X. Chen, A. L. B. Yang, and J. J. Y. Zhao, Recurrences for Callan’s generalization of Narayana polynomials, _J. Syst. Sci. Complex._ , 35 (2022), 1573–1585.
  * [18] D. Dumont and A. Ramamonjisoa, Grammaire de Ramanujan et arbres de Cayley, vol. 3, Research Paper 17, approx. 18, 1996. The Foata Festschrift.
  * [19] S. Elizalde, Descents on quasi-Stirling permutations, _J. Combin. Theory Ser. A_ , 180 (2021), 105429.
  * [20] S. Fomin and N. Reading, Root systems and generalized associahedra, in _Geometric combinatorics_ , vol. 13 of _IAS/Park City Math. Ser._ , 63–131, Amer. Math. Soc., Providence, RI, 2007.
  * [21] J. Haglund and M. Visontai, Stable multivariate Eulerian polynomials and generalized Stirling permutations, _European J. Combin._ , 33 (2012), 477–487.
  * [22] L. L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, _Adv. in Appl. Math._ , 38 (2007), 542–560.
  * [23] S.-M. Ma, J. Ma, and Y.-N. Yeh, $\gamma$-positivity and partial $\gamma$-positivity of descent-type polynomials, _J. Combin. Theory Ser. A_ , 167 (2019), 257–293.
  * [24] R. Pemantle, Hyperbolicity and stable polynomials in combinatorics and probability, in _Current developments in mathematics, 2011_ , 57–123, Int. Press, Somerville, MA, 2012.
  * [25] T. K. Petersen, _Eulerian numbers_ , Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser/Springer, New York, 2015.
  * [26] P. W. Shor, A new proof of Cayley’s formula for counting labeled trees, _J. Combin. Theory Ser. A_ , 71 (1995), 154–158.
  * [27] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences, _Published electronically athttp://oeis.org._
  * [28] R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, in _Graph theory and its applications: East and West (Jinan, 1986)_ , vol. 576 of _Ann. New York Acad. Sci._ , 500–535, New York Acad. Sci., New York, 1989.
  * [29] M. Visontai and N. Williams, Stable multivariate $W$-Eulerian polynomials, _J. Combin. Theory Ser. A_ , 120 (2013), 1929–1945.
  * [30] D. G. Wagner, Multivariate stable polynomials: theory and applications, _Bull. Amer. Math. Soc. (N.S.)_ , 48 (2011), 53–84.
  * [31] S. H. F. Yan and X. Zhu, Quasi-Stirling polynomials on multisets, _Adv. in Appl. Math._ , 141 (2022), Paper No. 102415, 14.
  * [32] P. B. Zhang and X. Zhang, Multivariate stable Eulerian polynomials on segmented permutations, _European J. Combin._ , 78 (2019), 155–162.