# Towards Fine-tuning Pre-trained Language Models with
Integer Forward and Backward Propagation

Mohammadreza Tayaranian∗1 Alireza Ghaffari∗1 Marzieh S. Tahaei1
Mehdi Rezagholizadeh1 Masoud Asgharian2 Vahid Partovi Nia1
1 Huawei Noah’s Ark Lab, Montreal Research Center
2 Department of Mathematics and Statistics, McGill University
{mohammadreza.tayaranian, alireza.ghaffari<EMAIL_ADDRESS>
{mehdi.rezagholizadeh<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

The large number of parameters of some prominent language models, such as
BERT, makes their fine-tuning on downstream tasks computationally intensive
and energy hungry. Previously researchers were focused on lower bit-width
integer data types for the forward propagation of language models to save
memory and computation. As for the backward propagation, however, only 16-bit
floating-point data type has been used for the fine-tuning of BERT. In this
work, we use integer arithmetic for both forward and back propagation in the
fine-tuning of BERT. We study the effects of varying the integer bit-width on
the model’s metric performance. Our integer fine-tuning uses integer
arithmetic to perform forward propagation and gradient computation of linear,
layer-norm, and embedding layers of BERT. We fine-tune BERT using our integer
training method on SQuAD v1.1 and SQuAD v2., and GLUE benchmark. We
demonstrate that metric performance of fine-tuning 16-bit integer BERT matches
both 16-bit and 32-bit floating-point baselines. Furthermore, using the faster
and more memory efficient 8-bit integer data type, integer fine-tuning of BERT
loses an average of 3.1 points compared to the FP32 baseline.

##  1 Introduction

**footnotetext: Equal contribution.

Over the past few years, integration of attention mechanisms into deep
learning models led to the creation of transformer based models. BERT Devlin
et al. (2018) is a prominent transformer based language model which has shown
state-of-the-art performance in natural language processing (NLP) tasks.

BERT requires high memory and computational resources due to its large number
of parameters. Having large number of parameters incurs challenges for
inference, training, and also fine-tuning of this model. Moreover, the
training phase i.e. pre-training and fine-tuning, involves more operations
compared to the inference. More specifically, the training phase includes
gradient computation and weight update that make the training more
computationally intensive.

Figure 1: Energy consumption and latency of 1 billion operations using various
data types, measured on an Intel® Xeon® CPU E5-2698 v4.

One method of reducing the computational complexity of deep learning models is
to represent their parameters and activations in low bit-width data types.
This reduces the memory footprint of the model and enables more efficient
computations. For instance, Figure 1 shows that low-bit integer data types
have higher throughput and better energy consumption compared to floating-
point.

Previous research attempts at integer quantization of transformer based
language models were only focused on forward propagation and the gradient
computation were kept in 32-bit floating-point data type (FP32) Bhandare et
al. (2019); Kim et al. (2021); Zafrir et al. (2019).

Furthermore, earlier efforts for using low bit-width data types for gradient
computation of transformer based language models has only been limited to
16-bit floating-point (FP16). This method, known as mixed precision training
Micikevicius et al. (2017), uses FP16 data type to represent weights,
activations and gradients while using FP32 for the weight update.

Here we present an integer fine-tuning method for transformer based language
models such as BERT. Unlike previous works, we use integer data types for both
forward propagation and gradient computation during the fine-tuning of BERT.
Moreover, we use the dynamic fixed-point format to represent floating-point
numbers as integers.

Our integer mapping strategy can be used alongside floating-point numbers in
fine-tuning and inference similar to mixed precision training. In our proposed
strategy, the arithmetic of all the compute intensive layers for both forward
and back propagation are performed using integer arithmetic while other
components of the model, such as nonlinear functions and the weight updates
are kept in FP32. We use integer versions of compute intensive layers such as
linear, normalization (layer-norm), and embedding layers.

We study the effect of various bit-widths of the integer input activation and
show that increasing the bit-width of the fixed-point mapping function
improves the convergence behaviour of the model. This enables us to find the
minimum bit-width required for integer fine-tuning of BERT.

Our fine-tuning experiments show that 16-bit integer BERT is able to match the
metric performance of mixed precision FP16 and FP32 methods.

We also further reduce the bit-widths and show that integer fine-tuning of
BERT with 8-bit integer weights and 12-bit integer activations has a score
drop of $3.1$ compared to the original performance.

To summarize, this paper makes the following contributions:

  * •

Integer fine-tuning of transformer based language models that uses integer
arithmetic for both the forward and back propagation of compute intensive
layers such as linear, layer-norm, and embedding. To the best of our
knowledge, this is the first time that integer data type is used for back
propagation of pre-trained language models.

  * •

Analyzing the effect of changing the bit-width of dynamic fixed-point format
on the convergence of fine-tuning. Remark 3 discusses that the convergence
behaviour of our integer fine-tuning is directly related to the variance of
dynamic fixed-point mapping and is controlled by the bit-width.

  * •

We show that fine-tuning BERT using 16-bit integer numbers is able to
outperform the FP16 mixed precision fine-tuning method.

The rest of this paper is structured as follows. Section 2 briefly discusses
previous works in which low bit-width data types are used for inference and
training of deep learning models. Section 3 provides details of our integer
fine-tuning method, including the representation mapping functions and
integer-only layers. The convergence behaviour of the dynamic fixed-point
mapping is studied in Section 4 by providing empirical observations and
theoretical analysis. The fine-tuning experiments on various integer and
floating-point setups are presented in Section 5. Finally, Section 6 concludes
the ideas proposed in this work.

##  2 Related Works

In this section we discuss the previous works that use low bit-width data
types in transformer based language models. These works could be categorized
into two major groups. In the first group, called low-bit inference, the low
bit-width data types are used only in the forward propagation phase to improve
computational complexity and reduce memory usage during the inference. In the
second group, also known as low-bit training, lower bit-width data types are
used for both the forward and back propagation phases.

###  2.1 Low-bit Inference

Previous research on low-bit inference quantize the model parameters and
activations to speed up the forward propagation. This category is itself
divided into quantization-aware training (QAT) and post-training quantization
(PTQ) methods.

In QAT, quantization is performed during training, allowing the model
parameters to adapt to the quantization noise. QAT relies on high-precision
FP32 gradients to train the model and adapt it to the quantization noise.

For instance, Zafrir et al. (2019) proposed Q8BERT which quantizes the
inference computations of all linear and embedding layers of BERT to 8-bit
integers and updates the quantization scale with a moving average. Similarly,
Shen et al. (2020) suggested Q-BERT which requires the computation of hessian
matrix for each group of parameters to be used in a mixed precision fine-
tuning with different bit-widths. Kim et al. (2021) proposed I-BERT that uses
a uniform quantization scheme to quantize input activations and weights of
various components of BERT. In I-BERT, the quantization scaling factors are
computed based on the distribution of the training data.

Unlike QAT that performs quantization of inference operations during training,
Post-Training Quantization (PTQ) methods apply quantization to the parameters
when the training is completed. Thus, they require extra calibration or
parameter tuning to adapt the model to the quantized parameters.

For instance, Bhandare et al. (2019) quantized the matrix multiplications of
the original transformer architecture from Vaswani et al. (2017) to 8-bit
integer data type. Moreover, the quantization is done only for the forward
propagation and requires extra calibration using validation data to tune the
boundaries of the quantization function. Zadeh et al. (2020) introduced GOBO
which compresses the fine-tuned weights of BERT by grouping them into two
categories of Gaussian and outlier. The outlier weights are kept in FP32,
while the Gaussian weights are quantized to lower bits. For lower bit-width
regimes, TernaryBERT and BinaryBERT are able to push the quantization to 2 and
1 bits respectively Zhang et al. (2020a); Bai et al. (2020). They both rely on
methods such as data augmentation and knowledge distillation to adapt the
model to the low-bit weights.

###  2.2 Low-bit Training

Research on low-bit training try to perform both the forward propagation and
gradient computation in low-bit arithmetic. Using low precision number formats
for gradients reduces the model’s ability to adapt the parameters to the
quantization noise, but increases the throughput and reduces the memory
footprint.

FP16 mixed precision training Micikevicius et al. (2017) is a common method
currently for low-bit fine-tuning of transformer based language models. This
method uses FP16 data type in both forward propagation and gradient
computation, while using FP32 for the weight update. Unlike FP16 mixed
precision training, our work uses dynamic fixed-point format which allows for
multiple choices of bit-width for the data type. We show that our 16-bit
integer fine-tuning method outperforms FP16 mixed precision training in terms
of metric score.

Using integer data types in the training of deep learning models has been
previously studied for the computer vision tasks. For instance, Zhang et al.
(2020b) quantized the input activations, gradients and parameters of the
linear layers for various convolutional neural networks (CNN). Similarly, Zhao
et al. (2021) adapted the quantization parameters by detecting the
distribution of the gradients in the channel dimension. In both these works
the quantization error is measured during training and is used to adjust the
quantization scale, whereas our method does not require any information about
distribution of data or gradients. Zhu et al. (2020) applied a quantization
scheme to train CNN architectures with “direction sensitive gradient clipping”
and learning rate scaling to control the quantization error of gradients. Our
integer fine-tuning method does not require gradient clipping and can follow
the same loss trajectory as the floating-point baseline with the same hyper-
parameters. Our proposed method improves upon Ghaffari et al. (2022) which
uses dynamic fixed-point format for integer training of deep learning models.
Unlike Ghaffari et al. (2022), our work studies various bit-widths for both
weights and activations to find the minimum bit-width required for fine-tuning
BERT. Furthermore, we study integer training method on large language models
where low-bit quantization is known to be a challenging task Bondarenko et al.
(2021). To the best of our knowledge, this is the first time where integer
numbers are used for the back propagation of transformer based language
models.

Figure 2: Forward propagation operations in an integer-only linear layer.
Green boxes use integer arithmetic and red boxes use floating-point data type.
Here, the integer output is generated using an integer matrix multiplication
and the output scale is generated by a single add operation. The bottom panel
shows the linear fixed-point mapping for the input tensors, that are the input
activation and the parameter tensor in this figure.

##  3 Methodology

###  3.1 Representation Mapping

We use the dynamic fixed-point format Williamson (1991) to map the floating-
point numbers to integer data type. This format, also known as block floating-
point, maps floating-point numbers to blocks of integer numbers, with each
block having its unique scale. For more information on various number formats
refer to Appendix A.

We use a linear fixed-point mapping function to map floating-point numbers to
integer numbers. The linear fixed-point mapping converts a floating-point
tensor $\mathbf{F}$ to a tensor of integers and a single scale factor.

The integers are obtained by rounding the floating-point mantissas. The scale
is the maximum of the floating-point exponents of $\mathbf{F}$. The bottom
section of Figure 2 shows the internal operations of the linear fixed-point
mapping.

To map the fixed-point numbers to floating-point, a non-linear inverse mapping
function is used. The inverse mapping converts integer numbers into normalized
floating-point mantissas and packs each integer with its corresponding scale
into a floating-point number.

Details of the representation mapping functions are provided in Ghaffari et
al. (2022). Our methodology differs in that it includes various bit-widths for
both weights and activations for the fine-tuning of transformer based language
models. We exploit this mapping strategy to explore various bit-widths for
weights and activations in order to find the minimum bit-width for fine-tuning
the model.

###  3.2 Integer Fine-tuning

Our method uses integer arithmetic for weights, activations and gradients,
while the weight update is kept in FP32. Moreover, our proposed BERT setups
use integer-only versions for all the linear, layer-norm and embedding layers
in which internal operations are performed with integer arithmetic.

####  3.2.1 Linear Layer

Figure 2 depicts a high-level view of forward propagation operations of the
integer-only linear layer. All the parameters and activations of the layer are
first mapped to dynamic fixed-point using the linear fixed-point mapping
function. In the case of linear layer, the integer parameters and input
activations are then sent to an integer matrix multiplication function to
generate the integer output. If needed, the integer output could be mapped
back to floating-point to be used by other layers of the model using the non-
linear inverse mapping.

For back propagation, the gradients of the parameters and input activations
are also computed using integer arithmetic. Using integer matrix
multiplication, the output gradients are multiplied by input activations and
parameters to compute the gradients. Since the weight update is performed in
FP32, the integer gradients and their scales are passed to the non-linear
inverse mapping to be mapped to FP32.

####  3.2.2 Layer-norm

The layer normalization or layer-norm performs the following operation on its
input $X$ Ba et al. (2016):

${\gamma}\frac{X-\mu}{\sqrt{\sigma^{2}+\epsilon}}+{\beta}\text{.}\ $ (1)

Here $\gamma$ and $\beta$ are the weight and bias parameters, and $\sigma$ and
$\mu$ are input standard deviation and mean respectively. For the forward
propagation of integer layer-norm we map $X$ to dynamic fixed-point format and
compute $\sigma$ and $\mu$ using integer arithmetic. Note that multiplication
to $\gamma$ and addition with $\beta$ are also performed using integer
arithmetic. Moreover, the back propagation also uses integer arithmetic to
compute the gradients for the input, $\gamma$, and $\beta$.

####  3.2.3 Embedding Layer

The embedding layer is a lookup table that stores embeddings. The layer takes
a list of indices as input and returns the list of corresponding embeddings
for each index. The integer embedding layer, handles integer embeddings and
needs less memory footprint to store these values. For the back propagation,
the embedding layer applies the output integer gradients directly to each
corresponding row of the lookup table.

Figure 3: F1 score of fine-tuning BERT using $b$-bit gradients, and
activations on SQuAD v2.0 dataset. For the 8-bit and 9-bit fixed-point bit-
widths, we use 12-bit input activations. Figure 4: F1 score of fine-tuning
BERT using 8-bit weights and gradients, with varying input activation bit-
width on SQuAD v2.0 dataset. Note that Remark 3 justifies this experiment
using the variance of $b$-bit dynamic fixed-point mapping.

##  4 Convergence Behaviour of Dynamic Fixed Point Mapping

###  4.1 Empirical Observations

Figure 2 shows that the bit-width, $b$, is controlled by adjusting the number
of rounded bits in the rounding function. Here we study the effect of changing
the integer bit-width on the metric performance of the model.

The motivation of varying the bit-width of the dynamic fixed-point is to
control the variance induced by the linear fixed-point mapping. Our
experiments show that using dynamic fixed-point with a bit-width of 10
achieves the same performance as the FP32 fine-tuning method. Figure 3
demonstrates the F1 score of fine-tuning BERT on SQuAD v2.0 dataset against
the fixed-point bit-width. Note that the fixed-point arithmetic with a bit-
width higher than 10 bits is able to closely match the F1 score of the FP32
baseline, that is indicated by the red line in the figure. Also note that in
our experimental setup for the 8-bit dynamic fixed-point format, we use 12-bit
input activations to close the F1 score gap with the FP32 baseline. The reason
for using higher bit-width input activations is that we observed 8-bit
activation dramatically reduces the F1 score. Figure 4 shows the effect of
input activation bit-width on the F1 score when the weights are 8-bit
integers. Changing the bit-width of the input activation from 8 bits to 12
bits significantly increases the F1 score. Increasing the input activation
bit-width beyond 12 bits has a negligible effect on the F1 score, confirming
that 12 bits is the minimum required bit-width of the input activations for
this application with 8-bit integer weights.

###  4.2 Theoretical Analysis

Here, we study the effect of varying dynamic fixed-point mapping bit-width on
the stochastic gradient descent method. The goal is to show the relation of
weight and activation bit-widths on the convergence of integer training. Let
us consider the following simplified weight update equation

${w}_{k+1}={w}_{k}+\bar{\eta}\hat{g}(w_{k},\xi_{k}),\ $ (2)

where $\hat{g}(w_{k},\xi_{k})$ is the dynamic fixed-point gradient and
$\bar{\eta}$ is the learning rate during the fine-tuning phase. Furthermore,
we also consider the following common assumptions in sequel.

Assumption 1 (Lipschitz-continuity). The loss function $\mathcal{L}(w)$ is
continuously differentiable and its gradients satisfies the following
inequality where $L>0$ is the Lipchitz constant

$\displaystyle\mathcal{L}(w)\leqslant\mathcal{L}(\bar{w})+$
$\displaystyle\nabla\mathcal{L}(\bar{w})^{\top}(w-\bar{w})$
$\displaystyle+\frac{1}{2}L||w-\bar{w}||^{2}_{2};$
$\displaystyle~{}~{}~{}\forall~{}w,\bar{w}\in\mathbb{R}^{d}.$ (3)

Assumption 2. (i) $\mathcal{L}(w_{k})$ is bounded. (ii) $b$-bit dynamic fixed-
point gradients $\hat{g}(w_{k},\xi_{k})$ is an unbiased estimator of the true
gradients of the loss function
$\nabla\mathcal{L}(w_{k})^{\top}\mathbb{E}_{\xi_{k}}\\{\hat{g}(w_{k},\xi_{k})\\}=||\nabla\mathcal{L}(w_{k})||^{2}_{2}=||\mathbb{E}_{\xi_{k}}\\{\hat{g}(w_{k},\xi_{k})\\}||^{2}_{2},$
and (iii) with the $b$-bit dynamic fixed-point gradients i.e.
$\hat{g}(w_{k},\xi_{k})$, there exist scalars $M\geqslant 0$ , $M_{V}\geqslant
0$, $M^{q}\geqslant 0$ and $M^{q}_{V}\geqslant 0$ such that for all iterations
of SGD

$\displaystyle\mathbb{V}_{\xi_{k}}\\{\hat{g}(w_{k},\xi_{k})\\}$
$\displaystyle\hskip 14.22636pt\leqslant
M+M^{q}+(M_{V}+M^{q}_{V})||\nabla\mathcal{L}(w_{k})||^{2}_{2}.$

Where $M^{q}$ and $M^{q}_{V}$ denote the added variance of $b$-bit dynamic
fixed-point mapping on the true gradient variance. Also note that in order for
Assumption 2 (i) to hold true, we use stochastic rounding for back
propagation.

Suppose Assumption 1 and Assumption 2 are true, then inequality (4) follows
from (Ghaffari et al., 2022, Remark 2)

$\displaystyle\mathbb{E}_{\xi_{k}}\\{\mathcal{L}(w_{k+1})\\}-\mathcal{L}(w_{k})$
$\displaystyle\hskip
14.22636pt\leqslant-(1-\frac{1}{2}\bar{\eta}L(M_{G}+M^{q}_{G}))\bar{\eta}||\nabla\mathcal{L}(w_{k})||^{2}_{2}$
$\displaystyle\hskip 113.81102pt+\frac{1}{2}\bar{\eta}^{2}L(M+M^{q}),$
$\displaystyle\text{with}~{}~{}M_{G}:=1+M_{V}~{}~{}\text{and}~{}~{}M^{q}_{G}:=1+M^{q}_{V},$
(4)

which shows the effect of added variance of fixed point mapping, i.e.
$M^{q}_{V}$ and $M^{q}$, on each step of the optimizer.

Remark 1. In inequality (4), the first term,
$-(1-\frac{1}{2}\bar{\eta}L(M_{G}+M^{q}_{G}))\bar{\eta}||\nabla\mathcal{L}(w_{k})||^{2}_{2}$
contribute to decreasing the loss $\mathcal{L}$ while the second term,
$\frac{1}{2}\bar{\eta}^{2}L(M+M^{q})$, prevents it. Also note that when
$M^{q}$ and $M^{q}_{G}$ are increased, they negatively affect the descent of
the loss $\mathcal{L}$. This means for a good convergence behaviour,
representation mapping variance bounds, i.e. $M^{q}$ and $M^{q}_{G}$, must be
controlled.

Remark 2. For dynamic fixed-point mapping with $b$-bit integers, the
representation mapping variance bounds i.e. $M^{q}$ and $M^{q}_{G}$, are
closely related to the bit-width $b$. Here, we study these two constants for a
linear layer. Let us denote $\hat{\mathbf{A}}$ as the $b$-bit dynamic fixed-
point version of tensor $\mathbf{A}$ and $\hat{a}_{ij}$ as its $ij^{th}$
element. We can relate $\hat{a}_{ij}$ and $a_{ij}$ with an error term $\delta$
such as $\hat{a}_{ij}=a_{ij}+\delta^{\mathbf{A}}_{ij}$. For a linear layer
$\hat{\mathbf{Y}}=\hat{\mathbf{X}}\hat{\mathbf{W}}$, the computation of the
$b$-bit dynamic fixed-point gradients in the back propagation is

$\hat{\mathbf{C}}=\frac{\partial\hat{\mathbf{L}}}{\partial\hat{\mathbf{W}}}=\frac{\partial\hat{\mathbf{Y}}}{\partial\hat{\mathbf{W}}}\frac{\partial\hat{\mathbf{L}}}{\partial\hat{\mathbf{Y}}}=\hat{\mathbf{X}}^{\top}\frac{\partial\hat{\mathbf{L}}}{\partial\hat{\mathbf{Y}}}=\hat{\mathbf{X}}^{\top}\hat{\mathbf{G}}.$
(5)

It is of interest to find the relation between
$\hat{\mathbf{C}}=\hat{\mathbf{X}}^{\top}\hat{\mathbf{G}}$ in the integer back
propagation and the true gradients $\mathbf{C}=\mathbf{X}^{\top}\mathbf{G}$.
We can derive the variance for each element $\hat{c}_{ij}$ by expanding the
error terms $\delta$,

$\displaystyle\mathbb{V}\\{\hat{c}_{ij}\\}$
$\displaystyle=\mathbb{V}\left\\{\sum^{N}_{n=1}\hat{x}_{ni}\hat{g}_{nj}\right\\}$
$\displaystyle=\mathbb{V}\left\\{\sum^{N}_{n=1}(x_{ni}+\delta^{\mathbf{X}}_{ni})(g_{nj}+\delta^{\mathbf{G}}_{nj})\right\\}$
$\displaystyle\leqslant\mathbb{V}\left\\{\sum^{K}_{n=1}x_{ni}g_{nj}\right\\}$
$\displaystyle\hskip
28.45274pt+\sigma^{2}_{\mathbf{G}}\mathbb{E}\\{||\mathbf{X}^{\top}_{i.}||^{2}_{2}\\}+\sigma^{2}_{\mathbf{X}}\mathbb{E}\\{||\mathbf{G}_{.j}||^{2}_{2}\\}$
$\displaystyle\hskip
28.45274pt+N\sigma^{2}_{\mathbf{X}}\sigma^{2}_{\mathbf{G}}$
$\displaystyle=\mathbb{V}\\{{c}_{ij}\\}+\sigma^{2}_{\mathbf{G}}\mathbb{E}\\{||\mathbf{X}^{\top}_{i.}||^{2}_{2}\\}$
$\displaystyle\hskip
28.45274pt+\sigma^{2}_{X}\mathbb{E}\\{||\mathbf{G}_{.j}||^{2}_{2}\\}+N\sigma^{2}_{\mathbf{X}}\sigma^{2}_{\mathbf{G}}.$

In inequality (LABEL:eq:variance),
$\sigma^{2}_{\mathbf{G}}=\mathrm{max}_{i,j}(\mathbb{V}\\{\delta^{\mathbf{G}}_{i,j}\\})$
and
$\sigma^{2}_{\mathbf{X}}=\mathrm{max}_{i,j}(\mathbb{V}\\{\delta^{\mathbf{X}}_{i,j}\\})$.
Also note $||\mathbf{X}^{\top}_{i.}||^{2}_{2}=\sum^{J}_{j}x_{ji}^{2}$ denotes
the squared L-2 norm of the $i^{\text{th}}$ row of $\mathbf{X}^{\top}$ and
$||\mathbf{G}_{.j}||^{2}_{2}=\sum^{I}_{i}g_{ij}^{2}$ denotes the squared L-2
norm of the $j^{\text{th}}$ column of $\mathbf{G}$. Furthermore, by defining

$\begin{cases}M^{q}:=\sigma^{2}_{\mathbf{G}}(\mathbb{E}\\{||\mathbf{X}^{\top}_{i.}||^{2}_{2}\\}+N\sigma^{2}_{\mathbf{X}})\\\
M^{q}_{V}:=\sigma^{2}_{\mathbf{X}}\\\ \end{cases}$ (7)

Equation (7) shows that $M^{q}$ depends on variance of dynamic fixed-point
mapping for input activations and gradients while $M^{q}_{G}$ only depends on
$b$-bit dynamic fixed-point gradients variance.

| QQP | QNLI | MNLI | SST-2 | STSB | RTE | MRPC | CoLA | Average
---|---|---|---|---|---|---|---|---|---
FP32 | 91.0/88.0 | 91.1 | 84.2 | 92.5 | 88.3 | 63.8 | 82.5/87.8 | 57.2 | 82.6
FP16 AMP | 90.9/87.9 | 91.2 | 84.1 | 92.4 | 88.3 | 64 | 82.1/87.7 | 57.5 | 82.6
16-bit integer | 91.0/88.0 | 91.2 | 84.2 | 92.5 | 88.3 | 64.5 | 82.3/87.6 | 57.7 | 82.7
12-bit integer | 90.9/88.0 | 91.2 | 84.0 | 92.6 | 87.9 | 63.5 | 81.3/87.4 | 56.7 | 82.4
10-bit integer | 90.8/87.8 | 91.0 | 84.0 | 92.5 | 87.5 | 62.7 | 78.4/85.8 | 57.6 | 81.8
8-bit integer | 90.1/86.8 | 90.8 | 83.7 | 92.3 | 87 | 61.8 | 76.8/84.7 | 55.0 | 80.9
Table 1: Metric performance of integer fine-tuning of BERT on selected GLUE
tasks. The reported metric for QQP and MRPC is accuracy and F1 score, for
QNLI, MNLI, RTE, and SST-2 is accuracy, for STSB is the Pearson-Spearman
correlation, and for CoLA is the Matthews correlation.

Proposition 1. For dynamic fixed-point representation of tensor
$\hat{\mathbf{A}}$ with $b$-bit integers, the variance of error for element
$i$ satisfies the following inequality

$\mathbb{V}\\{\delta_{i}^{\mathbf{A}}\\}\leqslant
2^{2(e_{\mathrm{scale_{\mathbf{A}}}}-b+2)}.$ (8)

Proof. Using dynamic fixed-point mapping to $b$-bit integers, the error
$\delta_{i}^{\mathbf{A}}$ satisfies the following bound

$\begin{gathered}-2^{e_{\mathrm{scale_{\mathbf{A}}}}}\underbrace{(0.000001)_{2}}_{b-1}\leqslant\delta_{i}^{\mathbf{A}}\leqslant
2^{e_{\mathrm{scale_{\mathbf{A}}}}}\underbrace{(0.000001)_{2}}_{b-1}\\\
-2^{e_{\mathrm{scale_{\mathbf{A}}}}-b+2}\leqslant\delta_{i}^{\mathbf{A}}\leqslant
2^{e_{\mathrm{scale_{\mathbf{A}}}}-b+2}.\end{gathered}$ (9)

Thus, the inequality (8) is obtained by using Popoviciu’s inequality on
variances

$\displaystyle\mathbb{V}\\{\delta_{i}^{\mathbf{A}}\\}$
$\displaystyle\leqslant\frac{1}{4}(2^{e_{\mathrm{scale_{\mathbf{A}}}}-b+2}-(-2^{e_{\mathrm{scale_{\mathbf{A}}}}-b+2}))^{2}$
$\displaystyle\leqslant 2^{2(e_{\mathrm{scale_{\mathbf{A}}}}-b+2)}.$ (10)

Remark 3. Inequality (8) shows that increasing bit-width $b$ in dynamic fixed-
point mapping reduces the variance of the error. This confirms our
experimental results on SQuAD v2.0 dataset that for $b>10$, F1 score can match
FP32 baseline, see Figure 3. Also note in equation (7), both $M^{q}$ and
$M^{q}_{V}$ depend on $b$-bit dynamic fixed-point mapping variance of input
activation $\sigma^{2}_{\mathbf{X}}$. Hence, increasing $b$ for input
activations while keeping weights in 8-bit format must improve the convergence
behaviour. This phenomenon is also confirmed by our experimental results on
SQuAD v2.0 dataset demonstrated in Figure 4.

| SQuAD v1.1 | SQuAD v2
---|---|---
FP32 | 80.5/88.0 | 70.6/73.8
FP16 AMP | 79.9/87.6 | 70.6/73.9
16-bit integer | 80.7/88.0 | 70.6/73.9
12-bit integer | 79.8/87.6 | 70.5/73.8
10-bit integer | 78.4/86.6 | 69.8/73.2
8-bit integer | 75.6/84.5 | 65.5/69.2
Table 2: Metric performance of fine-tuning BERT on SQuAD v1.1 and v2.0
datasets. For both datasets the exact match metrics and F1 scores are
reported.

##  5 Experimental Results

###  5.1 Experimental Setup

We fine-tuned BERT base on a series of downstream tasks to compare the
performance of our integer fine-tuning method with FP16 and FP32 fine-tuning
methods. FP16 AMP setup uses NVIDIA’s automatic mixed
precision111https://developer.nvidia.com/automatic-mixed-precision and the
FP32 baseline is the default implementation from Pytorch.

The model is fine-tuned on selected tasks of GLUE benchmark Wang et al.
(2018), along with the Stanford Question Answering Datasets, i.e. SQuAD v1.1
and SQuAD v2.0 Rajpurkar et al. (2016).

All the fine-tuning setups use the same hyper-parameters and are fine-tuned
for the same number of epochs. Each reported metric is the average of five
runs with five different random seeds to mitigate the effects of random
variation of the results. The fine-tuning experiments are performed based on
the fine-tuning scripts of the Hugging Face library Wolf et al. (2019). For
GLUE experiments the fine-tuning is performed for 5 epochs and the learning
rate is set to $2\times 10^{-5}$. Also, the per-device fine-tuning batch-size
is set to 32. Fine-tuning BERT on SQuAD datasets is done for 2 epochs and the
learning rate is $5\times 10^{-5}$ and the per-device fine-tuning batch-size
is 12. All experiments are run on eight NVIDIA V100 GPUs with 32 gigabytes of
VRAM.

###  5.2 Results

The results of fine-tuning BERT base on GLUE benchmark and SQuAD datasets are
presented in Table 1 and Table 2 respectively. GLUE benchmark contains a
series of downstream tasks, designed to evaluate a diverse set of language
understanding abilities of NLP models. SQuAD datasets contain a series of text
passages accompanied by a question and the task is to predict the span of the
answer in the passage. Using 16-bit integer data type, BERT is able to either
match or outperform the FP32 performance for all tasks. The 16-bit integer
BERT also shows similar or better performance compared to the FP16 mixed
precision fine-tuning method. Further reducing the integer bit-width to 8,
fine-tuning BERT exhibits an average of 1.7 point drop on GLUE benchmark and
4.5 point drop for SQuAD datasets. Moreover, our experiments show that using
10-bit and 12-bit integers has average score drops of 0.8 and 0.3 points for
GLUE tasks, and 0.8 and 0.2 point for SQuAD datasets respectively.

Figure 5: Integer fine-tuning loss trajectory of BERT on SQuAD v2.0 dataset
for 2750 iterations.

###  5.3 Loss Trajectory

Figure 5 shows the loss trajectory of integer fine-tuning BERT on SQuAD v2.0
dataset using 16-bit and 8-bit integers, along with FP32 method. The fine-
tuning loss trajectory of BERT using 16-bit integer closely follows the FP32
loss trajectory. On the other hand, when fine-tuning with 8-bit integer
parameters and 12-bit integer input activations, the loss trajectory is
slightly shifted, but follows the same trend of its FP32 counterpart.

##  6 Conclusion

We proposed an integer fine-tuning method for transformer based language
models using dynamic fixed-point format. We used dynamic fixed-point data type
to represent parameters, input activations and gradients in integer values. As
a result, our fine-tuning method uses integer arithmetic for the forward and
back propagation of compute intensive layers such as linear, layer-norm and
embedding layers of BERT model. Furthermore, we studied that increasing the
bit-width of the dynamic fixed-point format reduces the variance of the
mapping function and thus, improves the convergence of our integer fine-tuning
method. We conduct fine-tuning experiments on GLUE benchmark and SQuAD
datasets to compare the metric performance of our integer BERT with FP16 mixed
precision and FP32 fine-tuning methods. Our experiments show that the 16-bit
integer fine-tuning is able to achieve the same metric performance as the FP16
mixed precision fine-tuning method. In addition, fine-tuning BERT with lower
bit-width data types, i.e. 8-bit integer, maintains an average drop of metric
score within 3.1 points of the FP16 setup.

## Limitations

Although our integer fine-tuning method uses integer numbers for compute
intensive layers of BERT, integer support for non-linear layers of BERT, e.g.
softmax and GELU activation, are left for future work.

We have shown in Figure 1 that the integer data types are faster for the
general case. However, a direct comparison of the time and memory cost of our
integer fine-tuning method with the FP16 and FP32 methods is left for future
works due to lack of access to a proper hardware with integer tensor core
support.

Despite the similarities between fine-tuning and pre-training phases, they
differ in key aspects of training such as dataset size and number of epochs.
The challenges of using integer arithmetic in the pre-training phase will be
studied in the future work.

## References

  * Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. 2016.  Layer normalization.  _arXiv preprint arXiv:1607.06450_.
  * Bai et al. (2020) Haoli Bai, Wei Zhang, Lu Hou, Lifeng Shang, Jing Jin, Xin Jiang, Qun Liu, Michael Lyu, and Irwin King. 2020.  Binarybert: Pushing the limit of bert quantization.  _arXiv preprint arXiv:2012.15701_.
  * Bhandare et al. (2019) Aishwarya Bhandare, Vamsi Sripathi, Deepthi Karkada, Vivek Menon, Sun Choi, Kushal Datta, and Vikram Saletore. 2019.  Efficient 8-bit quantization of transformer neural machine language translation model.  _arXiv preprint arXiv:1906.00532_.
  * Bondarenko et al. (2021) Yelysei Bondarenko, Markus Nagel, and Tijmen Blankevoort. 2021.  Understanding and overcoming the challenges of efficient transformer quantization.  _arXiv preprint arXiv:2109.12948_.
  * 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_.
  * Ghaffari et al. (2022) Alireza Ghaffari, Marzieh S Tahaei, Mohammadreza Tayaranian, Masoud Asgharian, and Vahid Partovi Nia. 2022.  Is integer arithmetic enough for deep learning training?  _arXiv preprint arXiv:2207.08822_.
  * Kim et al. (2021) Sehoon Kim, Amir Gholami, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. 2021\.  I-bert: Integer-only bert quantization.  In _International conference on machine learning_ , pages 5506–5518. PMLR.
  * Micikevicius et al. (2017) Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al. 2017.  Mixed precision training.  _arXiv preprint arXiv:1710.03740_.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  _arXiv preprint arXiv:1606.05250_.
  * Shen et al. (2020) Sheng Shen, Zhen Dong, Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. 2020.  Q-bert: Hessian based ultra low precision quantization of bert.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8815–8821.
  * 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.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. 2018.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  _arXiv preprint arXiv:1804.07461_.
  * Williamson (1991) Darrell Williamson. 1991.  Dynamically scaled fixed point arithmetic.  In _[1991] IEEE Pacific Rim Conference on Communications, Computers and Signal Processing Conference Proceedings_ , pages 315–318. IEEE.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Zadeh et al. (2020) Ali Hadi Zadeh, Isak Edo, Omar Mohamed Awad, and Andreas Moshovos. 2020.  Gobo: Quantizing attention-based nlp models for low latency and energy efficient inference.  In _2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_ , pages 811–824. IEEE.
  * Zafrir et al. (2019) Ofir Zafrir, Guy Boudoukh, Peter Izsak, and Moshe Wasserblat. 2019.  Q8bert: Quantized 8bit bert.  In _2019 Fifth Workshop on Energy Efficient Machine Learning and Cognitive Computing-NeurIPS Edition (EMC2-NIPS)_ , pages 36–39. IEEE.
  * Zhang et al. (2020a) Wei Zhang, Lu Hou, Yichun Yin, Lifeng Shang, Xiao Chen, Xin Jiang, and Qun Liu. 2020a.  Ternarybert: Distillation-aware ultra-low bit bert.  _arXiv preprint arXiv:2009.12812_.
  * Zhang et al. (2020b) Xishan Zhang, Shaoli Liu, Rui Zhang, Chang Liu, Di Huang, Shiyi Zhou, Jiaming Guo, Qi Guo, Zidong Du, Tian Zhi, et al. 2020b.  Fixed-point back-propagation training.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2330–2338.
  * Zhao et al. (2021) Kang Zhao, Sida Huang, Pan Pan, Yinghan Li, Yingya Zhang, Zhenyu Gu, and Yinghui Xu. 2021.  Distribution adaptive int8 quantization for training cnns.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 3483–3491.
  * Zhu et al. (2020) Feng Zhu, Ruihao Gong, Fengwei Yu, Xianglong Liu, Yanfei Wang, Zhelong Li, Xiuqi Yang, and Junjie Yan. 2020.  Towards unified int8 training for convolutional neural network.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1969–1979.

##  Appendix A Data Types

In this section we provide a brief overview of various data types mentioned in
this work.

Floating-point data type is used to represent decimal fractional numbers. A
binary floating-point number has three components of sign ($s$), mantissa
($m$), and exponent ($e$). Using these components, floating-point number $x$
is shown as:

$x=(-1)^{s}\times m\times 2^{e-t}$

where $t$ is the precision and $0\leq m\leq 2^{t}-1$. Another way of
representing floating-point numbers is as

$x=(-1)^{s}\times
2^{e}(\frac{d_{1}}{2}+\frac{d_{1}}{4}+\ldots+\frac{d_{t}}{2^{t}})$

where $d_{i}$ are binary digits of m. For FP32, exponent and mantissa are 8
and 23 bit integer numbers.

Fixed-point is another data type for representing fractional numbers. Unlike
floating-point numbers where each mantissa is scaled using its respective
exponent, fixed-point uses a single scale factor for all the numbers.

We use the dynamic fixed-point data type in our integer fine-tuning method.
Also known as block floating-point, this format uses a different scale for
each block of numbers to allow for more flexibility.


# Intersecting families with covering number $3$

Andrey Kupavskii  Moscow Institute of Physics and Technology; Email:
<EMAIL_ADDRESS>
###### Abstract.

A covering number of a family is the size of the smallest set that intersects
all sets from the family. In 1978 Frankl determined for $n\geq n_{0}(k)$ the
largest intersecting family of $k$-element subsets of $[n]$ with covering
number $3$. In this paper, we essentially settle this problem, showing that
the same family is extremal for any $k\geq 100$ and $n>2k$.

The research was supported by the Advanced Postdoc.Mobility grant no.
P300P2_177839 of the Swiss National Science Foundation.

##  1\. Introduction

For integers $a\leq b$, put $[a,b]:=\\{a,a+1,\ldots,b\\}$, and denote
$[n]:=[1,n]$ for shorthand. For a set $X$, denote by $2^{X}$ its power set
and, for integer $k\geq 0$, denote by ${X\choose k}({X\choose\leq k}$ ) the
collection of all (at most) $k$-element subsets ($k$-sets) of $X$. A family is
simply a collection of sets. We call a family intersecting, if any two of its
sets intersect. A ‘trivial’ example of an intersecting family is the full
star: the family of all sets containing a fixed element. The covering number
$\tau(\mathcal{F})$ of a family $\mathcal{F}$ is the size of the smallest $X$
such that $X\cap F\neq\emptyset$ for all $F\in\mathcal{F}$. Each such $X$ we
call a cover or a hitting set. An intersecting family is trivial or a star if
it has covering number $1$. We call an intersecting family non-trivial, if the
intersection of all sets from the family is empty. Alternatively, a family is
non-trivial if its covering number is at least $2$.

One of the oldest and most famous results in extremal combinatorics is the
Erdős–Ko–Rado theorem [6], which states that for $n\geq 2k>0$ an intersecting
family $\mathcal{F}\subset{[n]\choose k}$ satisfies
$|\mathcal{F}|\leq{n-1\choose k-1}$. Thus, the extremal example is a full
star. Answering a question of Erdős, Ko, and Rado, Hilton and Milner [21]
found the size and structure of the largest non-trivial intersecting families
of $k$-sets. It has size ${n-1\choose k-1}-{n-k-1\choose k-1}+1$ and has an
element that intersects all but one set of the family.

For a family $\mathcal{F}\subset 2^{[n]}$ and $i\in[n]$, the degree of $i$ in
$\mathcal{F}$ is the number of sets from $\mathcal{F}$ containing $i$. Let
$\Delta(\mathcal{F})$ stand for the maximal degree of an element in
$\mathcal{F}$. The diversity $\gamma(\mathcal{F})$ of $\mathcal{F}$ is the
quantity $|\mathcal{F}|-\Delta(\mathcal{F})$. One may think of diversity as of
the distance from $\mathcal{F}$ to the closest star. Frankl [10] proved a far-
reaching generalization of the Hilton–Milner theorem. We present its slightly
stronger variant due to Zakharov and the author [26].

######  Theorem 1.1 ([26]).

Let $n>2k>0$ and $\mathcal{F}\subset{[n]\choose k}$ be an intersecting family.
If $\gamma(\mathcal{F})\geq{n-u-1\choose n-k-1}$ for some real $3\leq u\leq
k$, then

(1.1) $|\mathcal{F}|\leq{n-1\choose k-1}+{n-u-1\choose n-k-1}-{n-u-1\choose
k-1}.$

We note that the Hilton–Milner theorem is included in Theorem 1.1: simply put
$u=k$. Theorem 1.1 provides essentially the strongest possible stability
result for the Erdős–Ko–Rado theorem in the regime when the intersecting
family is large (more precisely, for the families of size at least
${n-2\choose k-2}+2{n-3\choose k-2}$). There are several other stability
results for the Erdős–Ko–Rado theorem, see, e.g. [4, 5, 18]. Recently, there
were a series of results [20], [22] in which the authors found a more fine-
grained relationship between the structure of the intersecting family (again,
for large intersecting families). See the paper of the author [24] for the
most general and conclusive results.

Theorem 1.1 is stated in terms of diversity. The largest bound on diversity it
gives is for $u=3$: $\gamma(\mathcal{F})\geq{n-4\choose k-3}$. Actually, for
relatively large $n$, the diversity cannot be much bigger: I have showed [23]
that $\gamma(\mathcal{F})\leq{n-3\choose k-2}$ for $n>Ck$ with some large $C$,
and then for $n>72k$ by Frankl [12] and $n>36k$ by Frankl and Wang [17].

Another natural measure of how far the intersecting family is from the trivial
family is the covering number. Intersecting families of $k$-sets with fixed
covering number were studied in several classical works. The Erdős–Ko–Rado
theorem shows that the largest intersecting family of $k$-element sets has
covering number $1$. The result of Hilton and Milner [21] determined the
largest intersecting family with covering number $2$. It is clear that any
$k$-uniform intersecting family $\mathcal{F}$ satisfies $\tau(\mathcal{F})\leq
k$: indeed, any set of $\mathcal{F}$ is a hitting set for $\mathcal{F}$. In a
seminal paper [7], Erdős and Lovász proved that an intersecting family
$\mathcal{F}\subset{[n]\choose k}$ with $\tau(\mathcal{F})=k$ has size at most
$k^{k}$ (note that it is independent of $n$!) and provided a lower bound of
size roughly $(k/e)^{k}$. Later, both lower [15] and upper [3, 1, 11, 28]
bounds were improved.

In [8] (cf. also [16]), Frankl studied the following general question: what is
the size $c(n,k,t)$ of the largest intersecting family
$\mathcal{F}\subset{[n]\choose k}$ with $\tau(\mathcal{F})\geq t$? Let us
define the following important family.

(1.2)
$\mathcal{T}_{2}(k):=\big{\\{}[k]\big{\\}}\cup\big{\\{}\\{1\\}\cup[k+1,2k-1]\big{\\}}\cup\big{\\{}\\{2\\}\cup[k+1,2k-1]\big{\\}}.$

It is easy to see that $\mathcal{T}_{2}(k)$ is intersecting, moreover,
$\tau(\mathcal{T}_{2}(k))=2$. Define $\mathcal{C}_{3}(n,k)\subset{[n]\choose
k}$ to be the maximal intersecting family with $\mathcal{C}_{3}(n,k)(\bar{1})$
isomorphic to $\mathcal{T}_{2}(k)$. It is easy to see that
$\tau(\mathcal{C}_{3}(n,k))=3$. Frankl proved the following theorem.

######  Theorem 1.2 ([8]).

Let $k\geq 3$ and $n\geq n_{0}(k)$. Then $c(n,k,3)=|\mathcal{C}_{3}(n,k)|$.
Moreover, for $k\geq 4$ the equality holds only for families isomorphic to
$\mathcal{C}_{3}(n,k)$.

Frankl proved this theorem using the Delta-system method, which was behind
many of the breakthroughs in extremal set theory in the 1970s and 80s. If one
analyzes the method used by Frankl directly, then the bound on $n$ is doubly
exponential in $k$ if one analyzes the proof in [8]. Using a refined variant
of the $\Delta$-system method, one can get the bound down to $n$ polynomial in
$k$, but the polynomial will most likely be at least cubic. The main result of
this paper is an extension of the theorem above into an essentially full range
of parameters.

######  Theorem 1.3.

The conclusion of Theorem 1.2 holds for any $k\geq 100$, $n>2k$.

In the paper [14], the authors managed to extend the result of [8] to the case
$\tau=4$, determining the exact value of $c(n,k,4)$ and the structure of the
extremal family for $n>n_{0}(k)$. The analysis in [14] is much more
complicated than that in [8], and the problem for $\tau\geq 5$ is still wide
open. It is possible that the result of [14] may be extended to much smaller
$n$ using the techniques from this paper. In the case of $\tau\geq 5$,
however, we do not even know the answer for $n>n_{0}(k)$, and this appears to
us the most challenging problem in this direction. The main difficulty for
$t\geq 5$ lies in the following problem.

######  Problem 1.

Given an intersecting family $\mathcal{F}$ of $k$-sets with
$\tau(\mathcal{F})=t$, what is the maximum number of hitting sets of size $t$
it may have?

Remark:  A weaker version of Theorem 1.3 (the same result for $n>Ck$ with
unspecified $C$ coming from the junta method), along with many of the proof
ideas, appeared in an unpublished manuscript of the author [24]. Actually, in
[24] I posed a problem to determine $c(n,k,3)$ for all $n>2k\geq 8$. Thus,
Theorem 1.3 essentially answers this question. I decided to split the
manuscript and publish it separately because of its heterogeneous nature and,
importantly, because its first part, dedicated to the complete version of
Frankl’s degree theorem, turned out to have been obtained earlier in an
unjustly overlooked paper by Goldwasser [19].

##  2\. Proof of Theorem 1.3

###  2.1. Outline of the approach

Take an intersecting family $\mathcal{F}\subset{[n]\choose k}$ with covering
number $3$. The proof of the theorem bifurcates based on whether
$\gamma(\mathcal{F})$ is large or small. (Concretely, whether
$\gamma(\mathcal{F})>{n-5\choose k-3}$ or not.)

In the case of large diversity, we show that $\mathcal{F}$ is significantly
smaller than the family $\mathcal{C}_{3}(n,k)$ that is expected to be
extremal. For $n<2k^{2}$ the family $\mathcal{C}_{3}(n,k)$ is still quite
large, and it is sufficient to use the bound (1.1) to show that
$|\mathcal{F}|$ is small.

For $n>2k^{2}$, we use the recently developed ‘peeling’ procedure, which is an
independent and apparently useful part of the spread approximation technique
[27], which was recently upgraded to be much more efficient [25]. We say that
a (non-uniform) family is maximal intersecting if no set can be replaced by a
proper subset without violating the intersection property. Peeling is an
iterative procedure in which we replace the family by a maximal intersecting
family and then remove (peel) the layer of the largest sets. It allows for an
efficient control of the structure of the family. In a way, it is an improved
analogue of the Delta-system method as used by, say, Frankl in [8]. Back to
the proof, the fact that $\mathcal{F}$ has large diversity implies that we can
peel the family up to a constant layer without the remaining family getting
trivial (i.e., being replaced by one singleton). This at the end allows us to
efficiently control the number of different $3$-element covers of
$\mathcal{F}$, which turns out to be much smaller than that for
$\mathcal{C}_{3}(n,k)$. As a result, the size of $\mathcal{F}$ is much smaller
than that of $\mathcal{C}_{3}(n,k)$.

The second case is small diversity. The key idea in this case is an extension
of the bipartite switching idea, which was introduced in [26] (similar ideas
appeared earlier in [13]). Its application is based on Corollary 2.1 for
cross-intersecting families (essentially, the two cross-intersecting families
are restrictions of $\mathcal{F}(1)$ and $\mathcal{F}(\bar{1})$, where $1$ is
the element with the highest degree). We carefully change the family
$\mathcal{F}$ so that its size does not decrease and the covering number is
preserved, but $\mathcal{F}(\bar{1})$ gets smaller and smaller. We actually
start with a minimal subfamily $\mathcal{M}\subset\mathcal{F}(\bar{1})$ with
covering number $2$ and at the end of the procedure we get that
$\mathcal{F}(\bar{1})$ coincides with $\mathcal{M}$.

The last step is to show that the optimal minimal $\mathcal{M}$ for
$\mathcal{F}(\bar{1})$ is isomorphic to $\mathcal{T}_{2}(k)$. This is done in
Lemma 2.2. In order to show this, we found an elegant way to upper bound the
size of $\mathcal{F}$ doing a specific size count of the size of the family
$\mathcal{F}(1)$ that cross-intersects $\mathcal{M}$ and compare it term by
term with an analogous count for $\mathcal{T}_{2}(k)$.

###  2.2. Preliminaries

For a family ${\mathcal{A}}\subset 2^{X}$ and a set $Y\subset X$, we use the
following notation:

$\displaystyle{\mathcal{A}}(Y)=$ $\displaystyle\big{\\{}F\setminus Y:Y\subset
F,F\in{\mathcal{A}}\big{\\}},$ $\displaystyle{\mathcal{A}}[Y]=$
$\displaystyle\big{\\{}F:Y\subset F,F\in{\mathcal{A}}\big{\\}},$
$\displaystyle{\mathcal{A}}(\bar{Y})=$ $\displaystyle\big{\\{}F:Y\cap
F=\emptyset,F\in{\mathcal{A}}\big{\\}}.$

Note the difference between ${\mathcal{A}}(Y)$ and ${\mathcal{A}}[Y]$: we
exclude $Y$ from the sets in the former and include it in the latter. For an
element $x$ we write ${\mathcal{A}}(x)$, ${\mathcal{A}}(\bar{x})$ instead of
${\mathcal{A}}(\\{x\\}),{\mathcal{A}}(\bar{\\{x\\}})$ for shorthand. For two
families ${\mathcal{A}},\mathcal{G}$ we also use the following notation:

${\mathcal{A}}[\mathcal{G}]=\cup_{F\in\mathcal{G}}{\mathcal{A}}[F].$

The families ${\mathcal{A}},{\mathcal{B}}$ are cross-intersecting if for any
$A\in{\mathcal{A}},B\in{\mathcal{B}}$ we have $A\cap B\neq\emptyset$. The
following result was essentially (modulo uniqueness) obtained in [26], and is
a consequence of a more general and strong result from [24].

######  Corollary 2.1 ([26]).

Let $a,b>0$, $n>a+b$. Let ${\mathcal{A}}\subset{[n]\choose a},\
{\mathcal{B}}\subset{[n]\choose b}$ be a pair of cross-intersecting families.
Denote $t:=b+1-a.$ Then, if $|{\mathcal{B}}|\leq{n-t\choose a-1}$, then

(2.1) $|{\mathcal{A}}|+|{\mathcal{B}}|\leq{n\choose a}.$

Moreover, the displayed inequality is strict unless $|{\mathcal{B}}|=0$.

If ${n-j\choose b-j}\leq|{\mathcal{B}}|\leq{n-t\choose a-1}$ for integer
$j\in[t,b]$, then

(2.2) $|{\mathcal{A}}|+|{\mathcal{B}}|\leq{n\choose a}-{n-j\choose
a}+{n-j\choose b-j}.$

Moreover, if the left inequality on ${\mathcal{B}}$ is strict, then the
inequality in the displayed formula above is also strict, unless $j=t+1$ and
$|{\mathcal{B}}|={n-t\choose a-1}$.

The result in [26] did not explicitly treat the equality case. However, it is
clear that strictness of (2.1) follows from (2.2), and the equality case in
(2.2) follows from [24, Theorem 2.12, part 3].

Let us recall the definition of shifting. For a given pair of indices $1\leq
i<j\leq n$ and a set $A\subset[n]$, define its $(i,j)$-shift $S_{ij}(A)$ as
follows. If $i\in A$ or $j\notin A$, then $S_{ij}(A)=A$. If $j\in A,i\notin
A$, then $S_{ij}(A):=(A-\\{j\\})\cup\\{i\\}$. That is, $S_{ij}(A)$ is obtained
from $A$ by replacing $j$ with $i$. The $(i,j)$-shift $S_{ij}(\mathcal{A})$ of
a family $\mathcal{A}$ is as follows:

$S_{ij}(\mathcal{A}):=\\{S_{ij}(A)\ :\ A\in\mathcal{A}\\}\cup\\{A\ :\
A,S_{ij}(A)\in\mathcal{A}\\}.$

Shifting is a very useful operation in the studies of a class of extremal set
theoretic problems. We refer to [9] for a survey. Shifting preserves the sizes
of sets and the size of the family: $|S_{ij}({\mathcal{A}})|=|{\mathcal{A}}|$.
Importantly, if ${\mathcal{A}}$ is intersecting then $S_{ij}({\mathcal{A}})$
is intersecting. Unfortunately, shifting can potentially reduce the covering
number and is thus not directly applicable for our problem. However, with a
certain amount of care, it is still possible to use, which we do in this
paper.

The following lemma is one of the key ingredients in the proof of the theorem.
It allows us to compare different intersecting families with ‘minimal’
$\mathcal{F}(\bar{1})$. Let us first give some definitions. Given integers
$m>2s$, let us denote by $\mathcal{T}_{2}^{\prime}(s):=\\{[s],[s+1,2s]\\}$.
Let $\mathcal{F}_{2}^{\prime}(s)\subset{[m]\choose k-1}$ stand for the largest
family that is cross-intersecting with $\mathcal{T}_{2}^{\prime}(s)$. Let
$\mathcal{F}_{2}(s)\subset{[m]\choose k-1}$ stand for the largest family that
is cross-intersecting with $\mathcal{T}_{2}(s)$ (cf. (1.2)).

######  Lemma 2.2.

Let $k\geq s$ and $m\geq k+s$ be integers, $k\geq 4$. Given a family
$\mathcal{H}\subset{[m]\choose s}$ with $\tau(\mathcal{H})=2$ and minimal
w.r.t. this property, consider the maximal family
$\mathcal{F}\subset{[m]\choose k-1}$ that is cross-intersecting with
$\mathcal{H}$. Then the unique maximum of $|\mathcal{F}|+|\mathcal{H}|$ is
attained when $\mathcal{H}$ is isomorphic to $\mathcal{T}_{2}^{\prime}(s)$
(and $\mathcal{F}$ is thus isomorphic to $\mathcal{F}_{2}^{\prime}(s)$).

If we additionally require that $\mathcal{H}$ is intersecting111Note that this
is equivalent to requiring that $|\mathcal{H}|>2$. then the maximum of
$|\mathcal{F}|+|\mathcal{H}|$ is attained for $\mathcal{H}$ and $\mathcal{F}$
isomorphic to $\mathcal{T}_{2}(s)$ and $\mathcal{F}_{2}(s)$. The maximal
configuration is unique if $s\geq k$.

###### Proof of Lemma 2.2.

Let us first express $|\mathcal{F}^{\prime}_{2}(s)|$. It is not difficult to
see that

$\displaystyle|\mathcal{F}^{\prime}_{2}(s)|\ =\ $ $\displaystyle{m-1\choose
k-2}-{m-s-1\choose k-2}+$ $\displaystyle{m-2\choose k-2}-{m-s-2\choose k-2}+$
$\displaystyle\cdots$ (2.3) $\displaystyle{m-s\choose k-2}-{m-2s\choose k-2}.$

Indeed, in the first line we count the sets containing $1$ that intersect
$[s+1,2s]$, in the second line we count the sets not containing $1$,
containing $2$ and intersecting $[s+1,2s]$ etc.

Quite surprisingly, we can bound the size of $\mathcal{F}$ for any
$\mathcal{H}$ in a similar way. Suppose that $z:=|\mathcal{H}|$ and
$\mathcal{H}=\\{H_{1},\ldots,H_{z}\\}$. Since $\mathcal{H}$ is minimal, for
each $l\in[z]$ there exists an element $i_{l}$ such that $i_{l}\notin H_{l}$
and $i_{l}\in\bigcap_{j\in[z]\setminus\\{l\\}}H_{l}$. (All $i_{l}$ are of
course different.) Applying Bollobas’ set-pairs inequality [2] to
$\mathcal{H}$ and $\\{i_{l}\ :\ l\in[z]\\}$, we get that
$|\mathcal{H}|\leq{s+1\choose s}=s+1$.

For each $l=2,\ldots,z$, we count the sets $F\in\mathcal{F}$ such that
$F\cap\\{i_{2},\ldots,i_{l}\\}=\\{i_{l}\\}$. Such sets must additionally
intersect $H_{l}\setminus\\{i_{2},\ldots,i_{l-1}\\}$. Note that
$H_{1}\supset\\{i_{2},\ldots,i_{z}\\}$. This covers all sets from
$\mathcal{F}$ that intersect $\\{i_{2},\ldots,i_{z}\\}$ and gives the first
$z-1$ lines in the displayed inequality below. Next, we have to deal with sets
from $\mathcal{F}$ that do not intersect $\\{i_{2},\ldots,i_{z}\\}$. Firstly,
they must intersect $H_{1}$. Assuming that
$H_{1}\setminus\\{i_{2},\ldots,i_{z}\\}=\\{j_{1},\ldots,j_{s+1-z}\\}$, for
each $l=1,\ldots,s+1-z$ we further count the sets $F\in\mathcal{F}$ such that
$F\cap\\{i_{2},\ldots,i_{z},j_{1},\ldots,j_{l}\\}=\\{j_{l}\\}$. Such sets must
additionally intersect $H_{i}\setminus\\{i_{2},\ldots,i_{z}\\}$ for some
$i\in[2,z]$. (The element $j_{l}$ cannot be contained in all sets from
$\mathcal{H}$ since the intersection of $\mathcal{H}$ is empty.) Note that
$H_{i}\setminus\\{i_{2},\ldots,i_{z}\\}$ is a set of size $s-z+2$. This
explains the last $s+1-z$ lines in the displayed inequality below. Since
$F\cap H_{1}\neq\emptyset$ for any $F\in\mathcal{F}$ and given that the
classes for different $l$ are disjoint, we clearly counted each set from
$\mathcal{F}$ exactly once. (However, we may also count some sets that are not
in $\mathcal{F}$.) Doing this count, we get the following bound on
$\mathcal{F}$.

$\displaystyle|\mathcal{F}|\ \leq\ $ $\displaystyle{m-1\choose
k-2}-{m-s-1\choose k-2}+$ $\displaystyle{m-2\choose k-2}-{m-s-1\choose k-2}+$
$\displaystyle\cdots$ $\displaystyle{m-z+1\choose k-2}-{m-s-1\choose k-2}+$
$\displaystyle{m-z\choose k-2}-{m-s-2\choose k-2}+$ $\displaystyle\cdots$
(2.4) $\displaystyle{m-s\choose k-2}-{m-2s-2+z\choose k-2}\ =:\ f(z).$

Remark that (2.4) coincides with (2.3) when substituting $z=2$. We have
$f(z-1)-f(z)\geq{m-s-1\choose k-2}-{m-s-2\choose k-2}={m-s-2\choose k-3}>1$
(here we use that $m\geq s+k$ and $k\geq 4$). Therefore, for any $z\geq
z^{\prime}$,

(2.5) $|\mathcal{H}|+|\mathcal{F}|\leq f(z^{\prime})+z^{\prime},$

and the inequality is strict unless $z=|\mathcal{H}|=z^{\prime}$.

At the same time, we have
$|\mathcal{F}^{\prime}_{2}(s)|+|\mathcal{T}^{\prime}_{2}(s)|=f(2)+2$ and
$|\mathcal{F}_{2}(s)|+|\mathcal{T}_{2}(s)|=f(3)+3$! (The former we have seen
above, and the latter is easy to verify by doing exactly the same count.)
Since, up to isomorphism, there is only one family
$\mathcal{H}\subset{[m]\choose s}$ of size $2$ with $\tau(\mathcal{H})=2$, we
immediately conclude that the first part of the statement holds. To deduce the
second part, we only need to show that, among all possible choices of
$\mathcal{H}$ of size $3$, the only one (up to isomorphism) that attains
equality in (2.5) is $\mathcal{H}=\mathcal{T}_{2}(s)$.

Recall that, for uniqueness in the second part of the lemma, we have
additional condition $s\geq k$. If there are two sets
$H^{\prime},H^{\prime\prime}\in\mathcal{H}$ such that $|H^{\prime}\cap
H^{\prime\prime}|=s-1$, then $\mathcal{H}$ is isomorphic to
$\mathcal{T}_{2}(s)$. Therefore, in what follows we assume that
$|H^{\prime}\cap H^{\prime\prime}|\leq s-2$ for any
$H^{\prime},H^{\prime\prime}\in\mathcal{H}$.

Let us deal with the case when $H_{l}\cap
H_{l^{\prime}}=\\{i_{l^{\prime\prime}}\\}$ for any
$\\{l,l^{\prime},l^{\prime\prime}\\}=[3]$. Note that this implies that

$m\geq 3s-3.$

Since $s\geq k\geq 4$, there are elements $j_{l}\in
H_{l}\setminus(H_{l^{\prime}}\cup H_{l^{\prime\prime}})$,
$\\{l,l^{\prime},l^{\prime\prime}\\}=[3]$. Perform the $(j_{1},j_{2})$-shift
on $\mathcal{F}\cup\mathcal{H}$ and denote
$\mathcal{F}^{\prime}:=S_{j_{1}j_{2}}(\mathcal{F})$. Clearly, the sizes of the
families stay the same and the resulting families are cross-intersecting. The
family, $S_{j_{1}j_{2}}(\mathcal{H})$ has covering number $2$, moreover there
are two sets in $\mathcal{H}$ that intersect in $2$ elements.

Finally, we may assume that $|H_{1}\cap H_{2}|\in[2,s-2]$. Then we do the a
similar count as in (2.4). Recall that $z=3$ The first two steps (with
$i_{2},i_{3}$) are the same. The part with $j_{i}$ is, however, slightly
modified. Take $j^{\prime}\in(H_{1}\cap H_{2})\setminus\\{i_{3}\\}$ and
$j^{\prime\prime}\in H_{1}\setminus(H_{2}\cup\\{i_{2}\\})$. Such choices are
possible due to $|H_{1}\cap H_{2}|\in[2,s-2]$. Count the sets
$F\in\mathcal{F}$ such that $F\cap\\{i_{2},i_{3},j^{\prime}\\}=j^{\prime}$.
They must intersect $H_{3}\setminus\\{i_{2}\\}$. Next, crucially, count the
sets in $F\in\mathcal{F}$ such that
$F\cap\\{i_{2},i_{3},j^{\prime},j^{\prime\prime}\\}=j^{\prime\prime}$. They
must intersect $H_{2}\setminus\\{i_{3},j^{\prime}\\}$ (note the size of this
set is $s-2$ instead of $s-1$). The remaining count is the same: let
$\\{j_{1},\ldots,j_{s-4}\\}:=H_{1}\setminus\\{i_{2},i_{3},j^{\prime},j^{\prime\prime}\\}$
and, for each $l\in[s-4]$, count the sets $F\in\mathcal{F}$ such that
$F\cap\\{i_{2},i_{3},j^{\prime},j^{\prime\prime},j_{1},\ldots,j_{l}\\}=j_{l}$.
They must additionally intersect either
$H_{2}\setminus\\{i_{3},j^{\prime}\\}$, or $H_{3}\setminus\\{i_{2}\\}$. Thus,
we obtain the following bound.

$\displaystyle|\mathcal{F}|\ \leq\ $ $\displaystyle{m-1\choose
k-2}-{m-s-1\choose k-2}+$ $\displaystyle{m-2\choose k-2}-{m-s-1\choose k-2}+$
$\displaystyle{m-3\choose k-2}-{m-s-2\choose k-2}+$ $\displaystyle{m-4\choose
k-2}-{m-s-\textbf{2}\choose k-2}+$ $\displaystyle{m-5\choose
k-2}-{m-s-4\choose k-2}+$ $\displaystyle\cdots$ (2.6)
$\displaystyle{m-s\choose k-2}-{m-2s+1\choose k-2}\ =:\ f^{\prime}(3).$

We have $f(3)-f^{\prime}(3)={m-s-2\choose k-2}-{m-s-3\choose
k-2}={m-s-3\choose k-3}\geq 1$ due to $m\geq s+k$, and thus $|\mathcal{F}|\leq
f^{\prime}(3)<f(3)=|\mathcal{F}_{2}(s)|$. Thus, in the assumption $s\geq k$
and if $\mathcal{H}$, $|\mathcal{H}|\geq 3$, is not isomorphic to
$\mathcal{T}_{2}(s)$, we have strict inequality in (2.5) for $z^{\prime}=3$.
The lemma is proven. ∎

###  2.3. Proof of Theorem 1.3

Recall the expression of the size of $\mathcal{C}_{3}(n,k)$, obtained in the
proof of Lemma 2.2 (cf. (2.6)):

$\displaystyle|\mathcal{C}_{3}(n,k)|\ =\ 3\ +\ $ $\displaystyle{n-2\choose
k-2}-{n-k-2\choose k-2}+$ $\displaystyle{n-3\choose k-2}-{n-k-2\choose k-2}+$
$\displaystyle{n-4\choose k-2}-{n-k-3\choose k-2}+$ $\displaystyle\cdots$
(2.7) $\displaystyle{n-k-1\choose k-2}-{n-2k\choose k-2}.$

The proof is very different in the case when the diversity of $\mathcal{F}$ is
large and when it is small. We first consider the case of large diversity.

###  2.4. The case $\gamma(\mathcal{F})>{n-5\choose k-3}$

First, we consider the case $n\leq 2(k-1)^{2}$.

######  Lemma 2.3.

If $k\geq 100$, $n\leq 2(k-1)^{2}$ and $\mathcal{F}\subset{[n]\choose k}$ is
intersecting with $\gamma(\mathcal{F})>{n-5\choose k-3}$, then
$|\mathcal{F}|<|\mathcal{C}_{3}(n,k)|$.

###### Proof.

The proof of the lemma is rather technical and requires different estimates on
sums of binomial coefficients. We start by lower bounding the size of
$\mathcal{C}_{3}(n,k)$. For any $i\geq 0$

$\frac{{n-k-2-i\choose k-2}}{{n-3-i\choose
k-2}}=\prod_{j=1}^{k-2}\frac{n-k-1-i-j}{n-2-i-j}\leq e^{-(k-1)(k-2)/(n-2)}\leq
e^{-\frac{k-2}{2(k-1)}}<\frac{2}{3},$

provided $k\geq 100$. Thus, we can lower bound each line in (2.7) of the form
$a-b$ by $\frac{1}{3}a$ ($a,b$ are some binomial coefficients here) and get

$\displaystyle|\mathcal{C}_{3}(n,k)|\ >$ $\displaystyle\
\frac{1}{3}\Big{(}{n-2\choose k-2}+{n-3\choose k-2}+\ldots+{n-k-1\choose
k-2}\Big{)}$ $\displaystyle=$ $\displaystyle\ \frac{1}{3}\Big{(}{n-1\choose
k-1}-{n-k-1\choose k-1}\Big{)}$ $\displaystyle\geq$ $\displaystyle\
\frac{1}{9}{n-1\choose k-1},$

where the last inequality is obtained analogously. On the other hand, since
$\mathcal{F}$ is intersecting and $\gamma(\mathcal{F})\geq{n-5\choose
k-3}\geq{n-5\choose k-4},$ we can use Theorem 1.1 with $u=4$ and get

(2.8) $\displaystyle|\mathcal{F}|\ \leq$ $\displaystyle\ {n-1\choose
k-1}-{n-5\choose k-1}+{n-5\choose k-4}$ $\displaystyle\leq$ $\displaystyle\
5{n-2\choose k-2}\ \leq\ \frac{1}{10}{n-1\choose k-1}$

for $n>50(k-1)$. Thus, for $n>50(k-1)$ we have
$|\mathcal{F}|<|\mathcal{C}_{3}(n,k)|$.

Consider the case $n=C(k-1)\leq 50(k-1)$. In this case, we need another lower
bound on the size of $\mathcal{C}_{3}(n,k)$. The sum of all subtracted
binomial coefficients in (2.7) is at most ${n-k\choose k-1}$, and thus

$|\mathcal{C}_{3}(n,k)|>{n-1\choose k-1}-{n-k-1\choose k-1}-{n-k\choose
k-1}\geq{n-1\choose k-1}-2{n-k\choose k-1}.$

We have

$\frac{{n-k\choose k-1}}{{n-1\choose
k-1}}\leq\Big{(}\frac{n-k}{n-1}\Big{)}^{k-1}\leq
e^{-\frac{(k-1)^{2}}{n-1}}\leq e^{-(k-1)/C}.$

Thus,

(2.9) $|\mathcal{C}_{3}(n,k)|\geq\big{(}1-2e^{-(k-1)/C}\big{)}{n-1\choose
k-1}.$

Let us upper bound $|\mathcal{F}|$. If $2k<n\leq 7k$ then we use

$\frac{{n-5\choose k-4}}{{n-5\choose
k-1}}=\frac{(k-1)(k-2)(k-3)}{(n-k-1)(n-k-2)(n-k-3)}\geq\frac{k-2}{n-k-1}\geq
1-\frac{2}{k}$

and

$\frac{{n-1\choose k-1}}{{n-5\choose
k-1}}=\prod_{i=1}^{4}\frac{n-i}{n-k-i+1}\leq 2^{4}$

for $n\geq 2k+1$ and $k\geq 100$. Using the first inequality of (2.8) and
these calculations, we have

$|\mathcal{F}|\leq{n-1\choose k-1}-\frac{2}{k}{n-5\choose
k-1}\leq\Big{(}1-\frac{1}{8k}\Big{)}{n-1\choose k-1}.$

Comparing the bound (2.9) and the upper bound on $|\mathcal{F}|$, we see that
$\frac{1}{8k}>2e^{-(k-1)/7}$ for any $k\geq 100$, and thus
$|\mathcal{F}|<|\mathcal{C}_{3}(n,k)|$ in this case.

We are left to deal with the case $7k<n\leq 50(k-1).$ For $n>7k$ we have
${n-5\choose k-1}-{n-6\choose k-1}={n-6\choose k-2}>{n-5\choose k-4}$ and

$\frac{{n-1\choose k-1}}{{n-6\choose
k-1}}=\prod_{i=1}^{5}\frac{n-i}{n-k-i+1}\leq e^{5(k-1)/(n-k-4)}<e^{6k/n}.$

Substituting this into the inequality (2.8), we get

$|\mathcal{F}|\leq{n-1\choose k-1}-{n-6\choose
k-1}\leq\Big{(}1-e^{-6k/n}\Big{)}{n-1\choose k-1}.$

Comparing with (2.8), we see that $e^{6k/n}<e^{7/C}<e^{(k-1)/C}/2$ for any
$k\geq 100$ and $C\leq 50$, and thus $|\mathcal{F}|<|\mathcal{C}_{3}(n,k)|$
again. The proof of the lemma is complete. ∎

In the remainder of this subsection, we assume that $n>2(k-1)^{2}$. The
expression (2.7) can be rewritten as follows

$\displaystyle|\mathcal{C}_{3}(n,k)|\ =\ 3\ +\ $ $\displaystyle{n-3\choose
k-3}+\ldots+{n-k-2\choose k-3}+$ $\displaystyle{n-4\choose
k-3}+\ldots+{n-k-2\choose k-3}+$ $\displaystyle{n-5\choose
k-3}+\ldots+{n-k-3\choose k-3}+$ $\displaystyle\cdots$ (2.10)
$\displaystyle{n-k-2\choose k-3}+\ldots+{n-2k\choose k-3}$ (2.11)
$\displaystyle\geq\ 3\ +\ $ $\displaystyle(k+(k-1)^{2}){n-k-2\choose k-3},$

where in the inequality we used the convexity of ${x\choose\ell}$ as a
function of $x$ and that we sum up ${x_{i}\choose k-3}$ with the average of
$x_{i}$ being at least $n-k-2$. We also have

$\frac{{n-3\choose k-3}}{{n-k-2\choose
k-3}}=\prod_{i=1}^{k-3}\frac{n-2-i}{n-k-1-i}\leq e^{(k-1)(k-3)/(n-2k+2)}\leq
e^{0.5}$

for $n\geq 2(k-1)^{2}$. Thus, for such $n$, we have

(2.12) $|\mathcal{C}_{3}(n,k)|\geq e^{-0.5}(k^{2}-k+1){n-3\choose k-3}.$

Our next goal is to upper bound $|\mathcal{F}|$, using $\tau(\mathcal{F})\geq
3$ and $\gamma(\mathcal{F})>{n-5\choose k-3}$. To this end, we employ the
peeling procedure, developed in [27] and [25]. We need some preparations.

We say that an intersecting family $\mathcal{G}$ is maximal if whenever
$A\subsetneq B\in\mathcal{G}$ then $\mathcal{G}\setminus\\{B\\}\cup\\{A\\}$ is
not intersecting. Moreover, we require a maximal $\mathcal{G}$ to be an
antichain: we have $B_{1}\not\subset B_{2}$ for any
$B_{1},B_{2}\in\mathcal{G}$.

######  Observation.

Given an intersecting family $\mathcal{F}$, there is a maximal intersecting
family $\mathcal{G}$ such that for any $F\in\mathcal{F}$ there is
$G\in\mathcal{G}$ with $G\subset F$.

The proof is straightforward: gradually replace sets from $\mathcal{G}$ by
their proper subsets as long as the intersecting property is preserved. For a
real number $r\geq 1$ we say that a family $\mathcal{F}$ is $r$-spread if
$|\mathcal{F}(X)|\leq r^{-|X|}|\mathcal{F}|$ for any set $X$. The following
lemma is standard (see, e.g., [27], [25]).

######  Lemma 2.4.

Given $r\geq 1$ and $\mathcal{G}\subset{[n]\choose k}$, if $|\mathcal{G}|\geq
r^{k}$ then there is a set $X$ of size strictly smaller than $k$ such that
$\mathcal{G}(X)$ is $r$-spread.

To prove the lemma, take an inclusion-maximal $X$ that violates the
$r$-spreadness of $\mathcal{G}$.

######  Lemma 2.5.

If $\mathcal{G}\subset{[n]\choose\leq m}$ is intersecting and there is a set
$X$ of size strictly smaller than $m$ and a subfamily
$\mathcal{G}^{\prime}\subset\mathcal{G}$ such that $\mathcal{G}^{\prime}(X)$
is $\alpha$-spread with $\alpha>m$, then
$\mathcal{G}\setminus\mathcal{G}(X)\cup\\{X\\}$ is intersecting.

###### Proof.

Arguing indirectly, assume that a set $F\in\mathcal{G}$ is disjoint from $X$.
Then $F$ must intersect every set from $\mathcal{G}^{\prime}(X)$. However,
using $\alpha$-spreadness of $\mathcal{G}^{\prime}(X)$, we see $\sum_{y\in
F}|\mathcal{G}^{\prime}(X\cup\\{y\\})|\leq\alpha^{-1}|F||\mathcal{G}^{\prime}(X)|<|\mathcal{G}^{\prime}(X)|$,
a contradiction. ∎

The peeling procedure is as follows. We put $\mathcal{T}_{k}=\mathcal{F}$ and
then for each $i=k,k-1,\ldots,2$ do the following.

  * •

Replace $\mathcal{T}_{i}$ by a maximal intersecting family
$\mathcal{T}^{\prime}_{i}$.

  * •

Put $\mathcal{W}_{i}:=\mathcal{T}^{\prime}_{i}\cap{[n]\choose i}$ and
$\mathcal{T}_{i-1}:=\mathcal{T}^{\prime}_{i}\setminus\mathcal{W}_{i}$.

We note the following properties of this peeling. First,
$\mathcal{T}_{i}\subset{[n]\choose\leq i}$. Second, for any $i$ we have

$\mathcal{F}=\mathcal{F}[\mathcal{T}_{i}]\cup\bigcup_{j=i+1}^{k}\mathcal{F}[\mathcal{W}_{j}].$

Third, by Lemma 2.5, there is no $X$ of size $<i$, such that
$\mathcal{W}_{i}(X)$ is $r$-spread with $r>i$. Lemma 2.4 implies

$|\mathcal{W}_{i}|\leq i^{i},$

and thus

$|\mathcal{F}(\mathcal{W}_{i})|\leq i^{i}{n-i\choose k-i}=:g(i).$

Let us compare $g(i)$ and $g(i-1)$ for $i\leq k$. We have

$\frac{g(i)}{g(i-1)}\leq\frac{i^{i}}{(i-1)^{i-1}}\cdot\frac{k-i}{n-i}\leq
ei\frac{k-i}{n-i}<\frac{ek^{2}}{4(n-k)}<\frac{1}{2},$

since $k\geq 100$ and $n>2(k-1)^{2}$. Therefore, we may conclude that, for any
$i\geq 1$, we have

$\sum_{j=i}^{k}g(j)\leq 2g(i).$

Using $n>2(k-1)^{2}$, we have

$2g(5)=2\cdot 5^{5}{n-5\choose k-5}\leq 2\cdot
5^{5}\frac{(k-3)(k-4)}{(n-k-1)(n-k-2)}{n-5\choose k-3}\leq\frac{2\cdot
5^{5}}{4(k-1)^{2}}{n-5\choose k-3}<{n-5\choose k-3}.$

This implies that $|\cup_{i=5}^{k}\mathcal{F}[\mathcal{W}_{i}]|<{n-5\choose
k-3}$, and thus $\mathcal{T}_{4}$ cannot consist of a singleton. Indeed, if
this is the case, then
$\gamma(\mathcal{F})\leq|\cup_{i=5}^{k}\mathcal{F}(\mathcal{W}_{i})|<{n-5\choose
k-3}$, a contradiction with $\gamma(\mathcal{F})>{n-5\choose k-3}$.

Next, we analyze $\mathcal{T}_{4}=\mathcal{T}^{\prime}_{5}\cap{[n]\choose\leq
4}$. Since $\mathcal{T}^{\prime}_{5}$ is maximal intersecting, there is no
$>5$-spread subfamily $\mathcal{T}_{4}(X)$. Let us analyze the size of
different layers of $\mathcal{T}_{4}(X)$, using the previous observation
concerning spread subfamilies and that $\mathcal{T}_{4}$ is intersecting. It
has no singletons, otherwise the family $\mathcal{T}_{4}(X)$ consists of that
singleton only by the intersection property. The subfamily of $2$-element sets
is intersecting and thus can be either a triangle or a star with $\ell$
petals. If $\ell>6$ then each $\leq 4$-element set intersecting the star must
intersect its center, and we get that all sets in the family $\mathcal{T}_{4}$
must contain the center of the star. Therefore, $\mathcal{T}_{4}$ can contain
at most $4$ sets $B_{1},\ldots,B_{\ell}$ of size $2$ (with $\ell\leq 4$).
Since $\mathcal{T}_{4}$ has no $>5$-spread subfamily, Lemma 2.4 implies that
it contains at most $3^{5}$ sets of size $3$ and $4^{5}$ sets of size $4$.

Combining all these and using that $2f(5)<{n-5\choose k-3}<{n-3\choose k-3}$
and $n>2(k-1)^{2}\geq 198(k-1)$, we get that

$\displaystyle|\mathcal{F}|\leq$
$\displaystyle\sum_{i=1}^{\ell}|\mathcal{F}[B_{i}]|+3^{5}{n-3\choose
k-3}+4^{5}{n-4\choose k-4}+2f(5)$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\ell}|\mathcal{F}[B_{i}]|+\Big{(}3^{5}+\frac{4^{5}(k-4)}{n-4}+1\Big{)}{n-3\choose
k-3}$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\ell}|\mathcal{F}[B_{i}]|+250{n-3\choose k-3}.$

In order to bound $\mathcal{F}[B_{i}]$, we use $\tau(\mathcal{F})\geq 3$.
Namely, for each $i\in[\ell]$ there is a set $F_{i}$ such that $F_{i}\cap
B_{i}=\emptyset$, and thus $\mathcal{F}[B_{i}]=\cup_{x\in
F_{i}}\mathcal{F}[B_{i}\cup\\{x\\}]$. We have
$|\mathcal{F}[B_{i}\cup\\{x\\}]|\leq{n-3\choose k-3}$, and thus
$\sum_{i=1}^{\ell}|\mathcal{F}[B_{i}]|\leq 4k{n-3\choose k-3}$. Overall, we
get that

$|\mathcal{F}|\leq(4k+250){n-3\choose k-3}.$

Comparing this with (2.12), we see that, for $k\geq 100$,
$e^{-0.5}(k^{2}-k+1)>50k>4k+250$, and thus
$|\mathcal{F}|<|\mathcal{C}_{3}(n,k)|$. This completes the proof in the case
$\gamma(\mathcal{F})>{n-5\choose k-3}$.

###  2.5. The case $\gamma(\mathcal{F})\leq{n-5\choose k-3}$

We note that this part of the argument works for any $n>2k\geq 8$. W.l.o.g.
assume that $1$ has the largest degree in $\mathcal{F}$. The proof is based on
the bipartite switching idea (see the sketch of the proof for more details).
We shall transform our family $\mathcal{F}$ into another family (denoted by
$\mathcal{F}^{\prime\prime}$), which will satisfy
$\tau(\mathcal{F}^{\prime\prime})=3$,
$|\mathcal{F}^{\prime\prime}|\geq|\mathcal{F}|$ (with strict equality in case
$\mathcal{F}^{\prime\prime}$ is not isomorphic to $\mathcal{F}$). Moreover,
$\mathcal{F}^{\prime\prime}(\bar{1})$ will have covering number $2$ and will
be minimal with respect to that property.

To that end, take any
$\mathcal{M}=\\{M_{1},\ldots,M_{z}\\}\subset\mathcal{F}^{\prime}(\bar{1})$
such that $\tau(\mathcal{M})=2$ and $\mathcal{M}$ is minimal w.r.t. this
property. Remark that $z\geq 3$ due to the fact that $\tau(\mathcal{M})=2$ and
$\mathcal{M}$ is intersecting. Since $\mathcal{M}$ is minimal, for each
$M^{\prime}\in\mathcal{M}$, there is

(2.13)
$i_{\ell}\in\Big{(}\bigcap_{M\in\mathcal{M}\setminus\\{M_{\ell}\\}}M\Big{)}\setminus\Big{(}\bigcap_{M\in\mathcal{M}}M\Big{)}.$

Fix an arbitrary choice of $i_{\ell}$ and put $I=\\{i_{\ell}:\ell\in[z]\\}$.
W.l.o.g. assume that $I=[2,z+1]$. For each $i\geq 2$, consider the following
bipartite graph $G_{i}$ (with the convention that $[2,1]=\emptyset$). The
parts of $G_{i}$ are

$\displaystyle\mathcal{P}_{a}^{i}:=\ $ $\displaystyle\Big{\\{}P\ :\
P\in{[2,n]\choose k-1},\ P\cap[2,i]=\\{i\\}\Big{\\}},$
$\displaystyle\mathcal{P}_{b}^{i}:=\ $ $\displaystyle\Big{\\{}P\ :\
P\in{[2,n]\choose k},\ P\cap[2,i]=[2,i-1]\Big{\\}},$

and edges connect disjoint sets. We identify $\mathcal{P}_{a}^{i}$ with
${[i+1,n]\choose k-2}$ and $\mathcal{P}_{b}^{i}$ with ${[i+1,n]\choose
k-i+2}$.

We have
$|\mathcal{P}_{b}^{i}\cap\mathcal{F}(\bar{1})|\leq|\mathcal{F}(\bar{1})|\leq{n-5\choose
k-3}$. Thus, for each $i=2,\ldots,z+1$ we can apply (2.2) to

$\displaystyle{\mathcal{A}}:=\mathcal{F}(1)\cap\mathcal{P}_{a}^{i}\ \ \ \
\text{and}\ \ \ \ \
{\mathcal{B}}:=\mathcal{F}(\bar{1})\cap\mathcal{P}_{b}^{i}$

with $a=k-1$ and $b=t=k$. Note that ${\mathcal{B}}$ already contains one set
$M\in\mathcal{M}$, and thus we get

$|{\mathcal{A}}|+|{\mathcal{B}}|\leq{n-i\choose k-2}-{n-k-2\choose k-2}+1,$

with a strict inequality unless $|{\mathcal{B}}|=1$. We replace
${\mathcal{A}},{\mathcal{B}}$ with $\big{\\{}F\cup\\{i\\}:F\in{[i+1,n]\choose
k-2},F\cap M\neq\emptyset\big{\\}}$ and $\\{M\\}$, respectively, getting a new
family $\mathcal{F}_{i}$. Note that
$|\mathcal{F}_{i}|\geq|\mathcal{F}_{i-1}|$, where
$\mathcal{F}_{1}:=\mathcal{F}$. Moreover, note that $\mathcal{F}_{i}$ stays
intersecting, since $\mathcal{F}_{i}(\bar{1})$ consists of $\mathcal{M}$ and
sets that contain $[2,i]$ entirely. All these sets intersect all the sets
newly added to $\mathcal{F}_{i}(1)$. We repeat the same exchange procedure for
any choice of set of representatives $I$. At the end of the procedure we get a
family $\mathcal{F}^{\prime}$ with $\mathcal{F}^{\prime}(\bar{1})$ consisting
of $\mathcal{M}$ and some family $\mathcal{U}\subset\mathcal{F}(\bar{1})$ of
sets that all contain the set $I^{\prime}$ of all elements that belong to all
but $1$ set in $\mathcal{M}$. Let us w.l.o.g. assume that $I^{\prime}=[2,t]$.
We also get $|\mathcal{F}^{\prime}|>|\mathcal{F}|$ unless
$\mathcal{F}^{\prime}$ is isomorphic to $\mathcal{F}$.

If $\mathcal{M}$ is isomorphic to $\mathcal{T}_{2}(k)$ (cf. (1.2)), then the
number of the elements contained in exactly two sets (all but one sets) is
$k+1$, and thus we may immediately conclude that $\mathcal{U}=\emptyset$: no
$k$-set can contain a subset of size $k+1$. Otherwise, $\mathcal{M}$ is not
isomorphic to $\mathcal{T}_{2}(k)$.222This is only needed for the uniqueness
of the extremal family $\mathcal{C}_{3}(n,k)$, since some of the exchanges we
shall perform below may not necessarily strictly increase the size. But this
does not pose problems since we will eventually arrive at a family
$\mathcal{F}^{\prime\prime}$ with
$\mathcal{F}^{\prime\prime}(\bar{1})=\mathcal{M}$, which we will show to have
size strictly smaller than that of $\mathcal{C}_{3}(n,k)$.

Let us show that we may continue the transformations and assure that
$\mathcal{U}$ is empty. It is clear if $t\geq k+2$: no $k$-element set can
contain a $(k+1)$-element set as a subset. Otherwise, consider the family
$\mathcal{M}^{\prime}:=\\{M\setminus[2,t]\ :\ M\in\mathcal{M}\\}$ and note
that sets in $\mathcal{M}^{\prime}$ have size at least $1$. If there is no
element $i^{\prime}\in[t+1,n]$ that is contained in at least $2$ sets of
$\mathcal{M}^{\prime}$, then take two elements $i\in M^{\prime}$ and $j\in
M^{\prime\prime}$, where $t+1\leq i<j\leq n$ and $M^{\prime},M^{\prime\prime}$
are distinct sets in $\mathcal{M}^{\prime}$, and perform the $(i,j)$-shift on
$\mathcal{F}^{\prime}$. Only two sets in $S_{ij}(\mathcal{M})$ will contain
$i$, and thus $\tau(S_{ij}(\mathcal{M}))=2$. Moreover,
$S_{ij}(\mathcal{F}^{\prime})$ is intersecting due to the properties of
shifting. Thus, we may replace $\mathcal{F}^{\prime}$ with
$S_{ij}(\mathcal{F}^{\prime})$ and $\mathcal{M}$ with $S_{ij}(\mathcal{M})$.

Now, we assume that there is an element in $i^{\prime}\in[t+1,n]$ that is
contained in at least $2$ sets of $\mathcal{M}^{\prime}$. W.l.o.g., assume
that $i^{\prime}=t+1$. For each $l\in[z]$, select one element $i_{l}\in
M_{l}\cap[t+1,n]$, with the condition that we select $i^{\prime}$ for each set
that contains it. (That is, $i_{l}$ may coincide.) Put $I:=\\{i_{l}\ :\
l\in[z]\\}$ and note $|I|\leq z-1.$ Consider the bipartite graph $G(t,I)$ with
parts

$\displaystyle\mathcal{P}_{a}(t,I):=\ $ $\displaystyle\Big{\\{}P\ :\
P\in{[2,n]\choose k-1},\ I\subset P,\ [2,t]\cap P=\emptyset\Big{\\}},$
$\displaystyle\mathcal{P}_{b}(t,I):=\ $ $\displaystyle\Big{\\{}P\ :\
P\in{[2,n]\choose k},\ [2,t]\subset P,\ I\cap P=\emptyset\Big{\\}},$

and edges connecting disjoint sets. Put $Y=[t+1,n]\setminus I$. We identify
$\mathcal{P}_{a}(t,I)$ with ${Y\choose k-|I|-1}$ and $\mathcal{P}_{b}(t,I)$
with ${Y\choose k-t+1}$. We have $t-1\geq z\geq|I|+1$, and, therefore, we may
apply (2.1) with $a:=k-|I|-1,\ b:=k-t+1$ and conclude that
$|{\mathcal{A}}|+|{\mathcal{B}}|\leq{|Y|\choose k-|I|-1}$. Replacing
${\mathcal{A}}$ with $\mathcal{P}_{a}(t,I)$ and ${\mathcal{B}}$ with
$\emptyset$ does not decrease the sum of sizes of the families and preserves
the intersecting property of the family. (Here we also note that, by the
choice of $I$, we have $|\mathcal{M}\cap\mathcal{P}_{b}(t,I)|=\emptyset$.)

We perform the same exchange operations for all possible choices of $I$ that
contain $i^{\prime}$, concluding that either all sets in $\mathcal{U}$ must
contain $i^{\prime}$, or they must contain some fixed set
$M^{\prime}\in\mathcal{M}^{\prime}$. The latter is, however, impossible, since
it would again imply that a $k$-element set from $\mathcal{U}$ contains a
$(\geq k+1)$-element set $M^{\prime}\cup[2,t]$.

Therefore, we may assume that all sets in $\mathcal{U}$ contain
$i^{\prime}=t+1$, and thus all contain $[2,t+1]$. We may next perform similar
exchange operations. Let us prepare the setup first. Slightly abusing
notation, consider the family $\mathcal{M}^{\prime}:=\\{M\setminus[2,t+1]\ :\
M\in\mathcal{M}\\}$ and consider all possible transversals $I$ for
$\mathcal{M}^{\prime}$: select one element $i_{l}\in M_{l}\cap[t+2,n]$.
(Again, $i_{l}$ may coincide.) Put $I:=\\{i_{l}\ :\ l\in[z]\\}$ and note
$|I|\leq z.$ Consider the same bipartite graph with parts
$\mathcal{P}_{a}(t+1,I)$ and $\mathcal{P}_{b}(t+1,I)$ and do the same exchange
operations. The only condition we needed to obey is that on uniformity, which
is $t\geq z+1\geq|I|+1$ in this case. (The reason it works now is the extra
fixed element in $\mathcal{P}_{b}^{\prime}(t+1,I)$, which makes the number of
fixed elements in $\mathcal{P}_{b}(t+1,I)$ at least as big as that in
$\mathcal{P}_{a}(t+1,I)$.)

Repeating this for all possible choices of $I$, we arrive at the family
$\mathcal{F}^{\prime\prime}$ and a situation when any set from
$\mathcal{F}^{\prime\prime}(\bar{1})\setminus\mathcal{M}$ must intersect any
such set $I$. Clearly, this is only possible for a set $F$ if $F\supset
M_{l}\cap[t+1,n]$. But this implies that $|F|>|M_{l}|$, which is impossible.
Thus $\mathcal{F}^{\prime\prime}(\bar{1})=\mathcal{M}$, and so $\mathcal{U}$
is empty. Moreover, $|\mathcal{F}^{\prime\prime}|\geq|\mathcal{F}|$ and it is
not difficult to check $\tau(\mathcal{F}^{\prime\prime})=3$.

Finally, we need to show that, among all minimal families $\mathcal{M}$, the
choice of $\mathcal{T}_{2}(k)$ is the unique optimal. But this is a direct
application of the second part of Lemma 2.2 with $s=k$ and $[2,n]$ playing the
role of $[m]$. Note that $n>2k$, and $m\geq 2k$. The proof of Theorem 1.3 in
case $\gamma(\mathcal{F})\leq{n-5\choose k-3}$ is complete.

Acknowledgements: I would like to thank Peter Frankl for introducing me to the
area and for numerous interesting discussions we had on the topic.

## References

  * [1] A. Arman and T. Retter, An upper bound for the size of a k-uniform intersecting family with covering number k, J. Comb. Theory Ser. A 147 (2017), 18–26.
  * [2] B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar 16 (1965), 447–452.
  * [3] D. D. Cherkashin, On hypergraph cliques with chromatic number 3, Moscow J. Comb. Numb. Th. 1 (2011), N3.
  * [4] S. Das and T. Tran, Removal and Stability for Erdős–Ko–Rado, SIAM J. Disc. Math. 30 (2016), 1102–-1114.
  * [5] D. Ellis, N. Keller and N. Lifshitz, Stability versions of Erdős–Ko–Rado type theorems via isoperimetry, Journal of the European Mathematical Society 21 (2019), N12, 3857–3902.
  * [6] P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics, 12 (1961), N1, 313–320.
  * [7] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infnite and Finite Sets, Proc. Colloq. Math. Soc. János Bolyai, Keszthely, Hungary (1973), North-Holland, Amsterdam (1974), 609–627.
  * [8] P. Frankl, On intersecting families of finite sets, J. Comb. Theory Ser. A 24 (1978), N2, 146–161.
  * [9] P. Frankl, The shifting technique in extremal set theory, Surveys in combinatorics, Lond. Math. Soc. Lecture Note Ser. 123 (1987), 81–110, Cambridge University Press, Cambridge.
  * [10] P. Frankl, Erdős–Ko–Rado theorem with conditions on the maximal degree, J. Comb. Theory Ser. A 46 (1987), N2, 252–263.
  * [11] P. Frankl, A near exponential improvement on a bound of Erdős and Lovász, preprint, https://users.renyi.hu/~pfrankl/2017-4.pdf
  * [12] P. Frankl, Maximum degree and diversity in intersecting hypergraphs, Journal of Combinatorial Theory, Series B 144 (2020), 81–94.
  * [13] P. Frankl, A. Kupavskii, Erdős–Ko–Rado theorem for $\\{0,\pm 1\\}$-vectors, J. Comb. Theory Ser. A 155 (2018), 157–179.
  * [14] P. Frankl, K. Ota and N. Tokushige, Uniform intersecting families with covering number four, J. Comb. Theory Ser. A 71 (1995), 127–145.
  * [15] P. Frankl, K. Ota and N. Tokushige, Covers in uniform intersecting families and a counterexample to a conjecture of Lovász, J. Comb. Theory Ser. A 74 (1996), 33–42.
  * [16] P. Frankl and N. Tokushige, Invitation to intersection problems for finite sets, J. Comb. Theory Ser. A 144 (2016), 157–211.
  * [17] P. Frankl, J. Wang, Improved bounds on the maximum diversity of intersecting families, European Journal of Combinatorics 118 (2024).
  * [18] E. Friedgut, On the measure of intersecting families, uniqueness and stability, Combinatorica, 28 (2008), 503–528.
  * [19] J.L. Goldwasser, Erdős–Ko–Rado with conditions on the minimum complementary degree, J. Comb. Theory Ser. A 109 (2005), 45–62.
  * [20] J. Han, Y. Kohayakawa, The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family, Proc. Amer. Math. Soc. 145 (2017) N1, 73–87.
  * [21] A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford 18 (1967), 369–384.
  * [22] A. Kostochka, Dhruv Mubayi, The structure of large intersecting families Proc. Amer. Math. Soc. 145 (2017), N6, 2311–2321.
  * [23] A. Kupavskii, Diversity of intersecting families, European Journal of Combinatorics 74 (2018), 39–47.
  * [24] A. Kupavskii, Structure and properties of large intersecting families, unpublished, arXiv:1810.00920
  * [25] A. Kupavskii, An almost complete $t$-intersection theorem for permutations, preprint
  * [26] A. Kupavskii, D. Zakharov, Regular bipartite graphs and intersecting families, J. Comb. Theory Ser. A 155 (2018), 180–189.
  * [27] A. Kupavskii and D. Zakharov, Spread approximations for forbidden intersections problems, to appear in Advances in Mathematics, available at arxiv:2203.13379
  * [28] D. Zakharov, On the size of maximal intersecting families, Combinatorics, Probability and Computing 33 (2024), N1, 32–49.


# Where exactly does contextualization in a PLM happen?

Soniya Vijayakumar, Simon Ostermann, Tanja Bäumel  Josef van Genabith
German Research Instutite for Artificial Intelligence (DFKI), Saarland
Informatics Campus, Germany
soniya.vijayakumar, simon.ostermann, tanja.baeumel, josef.van_genabith
@dfki.de

##  1 Introduction

Pre-trained Language Models (PLMs) have shown to be consistently successful in
a plethora of NLP tasks due to their ability to learn contextualized
representations of words Ethayarajh (2019). BERT Devlin et al. (2018), ELMo
Peters et al. (2018) and other PLMs encode word meaning via textual context,
as opposed to static word embeddings, which encode all meanings of a word in a
single vector representation. Much recent work has explored understanding the
syntactic, semantic or contextualization information present in the hidden-
states or attention-heads of the various PLMs by extracting contextualized
representations either from the last output layer or concatenating the mean of
representations across all layers Khattab and Zaharia (2020); Ravfogel et al.
(2020); Zhao et al. (2020); Khattab and Zaharia (2020); Wiedemann et al.
(2019); Ethayarajh (2019); Mareček and Rosa (2019); Clark et al. (2019). In
this work, we present a study that aims to localize where exactly in a PLM
word contextualization happens. In order to find the location of this word
meaning transformation, we investigate representations of polysemous words in
the basic $BERT_{uncased}$ 12 layer architecture Devlin et al. (2018), a
masked language model trained on an additional sentence adjacency objective,
using qualitative and quantitative measures.

Our main contribution is that unlike previous work, we do not restrict
ourselves to the output layer(s) of such networks, but also investigate
different sub-layers within each BERT encoder layer. We also apply
Dimensionality Reduction (DR) techniques on these latent sub-layers to better
visualize our qualitative findings.

First, we confirm findings of Ethayarajh (2019) and other works, indicating
that higher layers of BERT exhibit higher degrees of contextualization.
Second, by investigating contextualization also in encoder sub-layers, we find
for the first time that representations in the self-attention sub-layers
exhibit stronger and earlier signs of contextualization as compared to the
activation and output sub-layers.

##  2 Methodology

### Experimental Setup:

We use the Contextualised Polysemy Word Sense v2 Dataset Haber and Poesio
(2020) which contains custom samples of polysemous words in sentential
contexts. We feed two sentences for each polysemous word to BERT and extract
sub-layer vector representations for each encoder layer. For each word, we
arrive at a set of vectors: Self-Attention (SA) sub-layer, Activation (Acts)
sub-layer, and Output sub-layer. We also extract the BERT static word
embeddings (layer-0) for understanding semantic divergence of the sub-layers.

### Measures of Contextuality:

Sub-Layer Similarity. Let w be the polysemous word that appears in a pair of
sentences $\\{\textit{s1, s}2\\}$ at index i,j in its respective sentences,
$\\{x_{s1}$, $x_{s2}\\}$ the sub-layer vector representations of the model m.
The sub-layer similarity of word w in layer l is:

$SubLayerSim_{x}(w^{l}_{i,j})=\frac{cos(x^{l}_{i_{s1}},x^{l}_{j_{s2}})}{||x^{l}_{i_{s1}}||||x^{l}_{j_{s2}}||}$
(1)

where x is Self-Attention sub-layer, Activation sub-layer and Output sub-layer
or $l=\\{0,1,...,11\\}$.

Static Word Embedding Similarity. For each word, we determine the cosine
similarity between each sub-layer and its respective static word embedding
from layer 0 (denoted as WESim).

Principal Components Analysis (PCA). For better visualization, we reduce the
High-Dimensional (HD) sub-layers (12 x 768, 12 x 3072) into two principal
components using the PCA technique. PCA preserves the actual relative distance
in the Euclidean data space and Principal Components (PCs) capture the
direction of maximum variance. We determine squared L2 distances of the PCs
between reduced sub-layer vector representations in the pair of sentences. We
use these distance measures to quantitatively conform the observations made
using SubLayerSim similarities.

Intuitively, the higher the SubLayerSim between the polysemous words, the
closer the respective vector representations are to each other, hence they are
less contextualized. The lower the WESim, the further the vector is away from
the (uncontextualized) static word embedding. On the other hand, the higher
the L2 Distance, the further the respective words (PCs) are from each other.
This implies the actual relative distance in the higher dimension is high,
indicating more contextualization.

Figure 1: Layer-wise average Self-Attention (SA), Activations (Acts) and Output SubLayerSim for all words. Figure 2: Layer-wise average Self-Attention (SA) and Outputs WESim for all words. the Acts sub-layer similarity is not reported due to the dimensionality mismatch. | Avg Sa | Avg Acts | Avg Outs
---|---|---|---
SLSim | 0.6329 | 0.7309 | 0.8614
WESim | 0.008 | - | 0.521
L2 Dists | 3.217 | 3.413 | 1.195
Table 1: SLSim: SubLayerSim, WESim Word Embeddings and L2 distances for each
sub-layer and all words.

##  3 Results & Discussion

Examining the average SubLayerSim of all polysemous words, we observe that the
Output sub-layer similarity is closer to one, indicating a lower degree of
contextualization as compared to Acts and SA sub-layers (Figure 1). The Acts
and SA sub-layers SubLayerSim are closer to each other, with higher
contextualization in the SA sub-layer. The all-words average SubLayerSim for
the sub-layers indicate similar observations (Table 1).

BERT’s layer-wise average SubLayerSim of all sub-layers decreases towards
higher layers (lowest at layer 9), indicating the existence of higher
contextualization layers between layers 5 and 9 (Figure 1). This observation
is similar to Ethayarajh (2019)’s experiments: The upper hidden layers of
contextualizing models produce more context-specific representations. An
interesting observation is that the sub-layer similarities become higher and
closer to each other in the penultimate layer of BERT (layer 12), which could
be an indication of the model’s sensitivity to output form and training
objective. A notable finding in WESim is that, SA sub-layer WESim remains
relatively consistent across BERT Layers where as the Output sub-layer WESim
consistently decreases (Figure 2). This indicates the influence of residual
connections in the BERT encoder Output sub-layer.

### PCA:

We observe that the PCA bi-plots for SA, Acts and Output sub-layers are
structurally different, indicating different structural alignment in their
respective HD spaces. Examining the per-word average L2 distances, we observe
that the Output sub-layer L2 distances are much lower than the respective SA
and Acts sub-layers, indicating a stronger contextualization in the SA and
Acts sub-layers (Table 1).

##  4 Conclusion & Future (on-going) research

In our research, we dive deeper into sub-layers of each BERT encoder layer to
localize the contextualization of polysemous words. Using contextuality
measures and PCA, we observe that the contexts of these words are strongly
captured in the Self-Attention sub-layer compared to the respective Activation
and Output sub-layers and in higher layers of BERT. In other words, we find
word meaning transformation to occur strongly in SA and Acts sub-layer as
compared to the Output sub-layers. We are currently working on exploring these
methods on benchmark WSD corpora Raganato et al. (2017) on other
contextualized models. Our future research involves applying Representational
Similarity Analysis (RSA) across the sub-layers Abnar et al. (2019) to
understand if contextualization redundancies exist in these sub-layers.

## Limitations

In this work, we are faced with a few limitations. First, the available WSD
benchmark datasets are not in the format we require and hence, we conducted
our experiments with a relatively smaller dataset, as presented above. Second,
with the limited dataset, all the sentences have a standard structure for each
polysemous word, i.e, each polysemous word is in the second position after the
stopword ’The’. We are yet to experiment with sentences that have different
indices for polysemous words. Third, we use two different metrics, cosine
similarity and euclidean distance on a PCA for understanding the extent of
contextualization. These two metrics have different properties making them not
directly comparable. SubLayerSim measure helped us in quantifying the
contextualization whereas we used PCA as a visualization technique, to
qualitatively confirm our observations.

## References

  * Abnar et al. (2019) Samira Abnar, Lisa Beinborn, Rochelle Choenni, and Willem Zuidema. 2019.  Blackbox meets blackbox: Representational similarity & stability analysis of neural language models and brains.  In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 191–203, Florence, Italy. Association for Computational Linguistics.
  * Clark et al. (2019) Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. 2019.  What does BERT look at? an analysis of BERT’s attention.  In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 276–286, Florence, Italy. Association for Computational Linguistics.
  * 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.
  * Ethayarajh (2019) Kawin Ethayarajh. 2019.  How contextual are contextualized word representations? comparing the geometry of bert, elmo, and GPT-2 embeddings.  _CoRR_ , abs/1909.00512.
  * Haber and Poesio (2020) Janosch Haber and Massimo Poesio. 2020.  Word sense distance in human similarity judgements and contextualised word embeddings.  In _Proceedings of the Probability and Meaning Conference (PaM 2020)_ , pages 128–145, Gothenburg. Association for Computational Linguistics.
  * Khattab and Zaharia (2020) Omar Khattab and Matei Zaharia. 2020.  Colbert: Efficient and effective passage search via contextualized late interaction over bert.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’20, page 39–48, New York, NY, USA. Association for Computing Machinery.
  * Mareček and Rosa (2019) David Mareček and Rudolf Rosa. 2019.  From balustrades to pierre vinken: Looking for syntax in transformer self-attentions.  In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 263–275, Florence, Italy. Association for Computational Linguistics.
  * Peters et al. (2018) Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 2227–2237, New Orleans, Louisiana. Association for Computational Linguistics.
  * Raganato et al. (2017) Alessandro Raganato, Jose Camacho-Collados, and Roberto Navigli. 2017.  Word sense disambiguation: A unified evaluation framework and empirical comparison.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 99–110, Valencia, Spain. Association for Computational Linguistics.
  * Ravfogel et al. (2020) Shauli Ravfogel, Yanai Elazar, Jacob Goldberger, and Yoav Goldberg. 2020.  Unsupervised distillation of syntactic information from contextualized word representations.  In _Proceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pages 91–106, Online. Association for Computational Linguistics.
  * Wiedemann et al. (2019) Gregor Wiedemann, Steffen Remus, Avi Chawla, and Chris Biemann. 2019.  Does bert make any sense? interpretable word sense disambiguation with contextualized embeddings.
  * Zhao et al. (2020) Mengjie Zhao, Philipp Dufter, Yadollah Yaghoobzadeh, and Hinrich Schütze. 2020\.  Quantifying the contextualization of word representations with semantic class probing.