\section{Introduction}
 While modern deep neural language models achieve impressive performance on various benchmarking datasets, the question of {\em how} this is achieved is gaining increased attention. This line of inquiry includes a new avenue of research: probing.

There are many methods to probe a neural network. Among these, diagnostic classification is by far the most common. To probe a neural network in a classification configuration, we specify a classification task that examines an ability (e.g., detecting verb tense). We encode the texts with a deep neural network and apply a post-hoc classifier to the encoded representations. If the classifier can easily predict an attribute, we consider this deep neural network capable of encoding the specified ability.
Researchers have expanded the targets of probing classifications to a wide range of abilities including syntax and semantics \citep{jawahar-etal-2019-bert,tenney-etal-2019-bert,kulmizev-etal-2020-neural,vulic-etal-2020-probing}, discourse \citep{koto-etal-2021-discourse,zhu-etal-2020-examining,chen-etal-2019-evaluation} and commonsense reasoning \citep{petroni-etal-2019-language,lin-etal-2020-birds}. These probing papers are associated with datasets of varying sizes, as shown in Figure \ref{fig:probing_dataset_sizes}.
\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/probing_datasets_sizes.png}
    \caption{Sizes of the datasets in some common probing suites. Depending on the tasks, they vary from hundreds to larger than $10^5$.}
    \label{fig:probing_dataset_sizes}
\end{figure}

What is a suitable size for probing datasets? Larger training datasets lead to tighter generalization bounds. With other conditions fixed, larger testing datasets allow for higher statistical power in comparing probing models and classifiers. That said, it is neither realistic nor desirable to increase the probing dataset sizes arbitrarily. It is therefore essential to find a balanced size for probing classifications.

We propose a framework to formally estimate the data requirements of probing configurations (\S \ref{sec:methodology}). Our framework considers the scenario of comparing probing configurations given some data. How many additional data samples may be necessary to reliably reproduce this comparison effect? We propose a novel method to estimate the required data samples by adapting a generalization bound.

We evaluate our framework on various probing tasks. First, we verify that the choice of generalization bound agrees with the probing results (\S \ref{subsec:experiment_theoretical_bounds_conservative}). On a case study recognizing synthetic Gaussian noise, we verify that larger datasets provide higher statistical power (\S \ref{subsec:experiment_add_gaussian_noise}). We evaluate the utility of our framework on a collection of comparison problems (\S \ref{subsec:experiment_corrupted_encoders} - \S \ref{subsec:experiment:compare_encoders}), where the probing data sizes recommended by the theoretical framework always supports power larger than $0.8$.
This paper helps to formalize probing experiments. Our framework can be used by the research community in collecting probing datasets.

\section{Related Work}
\paragraph{Understanding the datasets} There is increased research attention paid to the datasets used for deep learning models.
One way to study the dataset is to visualize each of the dataset samples in a map. \citet{swayamdipta-etal-2020-dataset} mapped the data samples in NLP datasets to regions such as ``hard-to-learn'' and ``easy-to-learn'' using signals observed during the training process. \citet{yauney2021comparing} mapped the difficulty of data samples by the data-dependent complexity \citep{arora2019fine}. \citet{vania-etal-2021-comparing} used Item Response Theory \citep{baker2004item}, a statistical framework from psychometrics to describe various attributes related to the difficulty of test set items.
Similarly, researchers also describe the effects of datasets as a whole. Several papers attempted through information theory \citep{pimentel2021bayesian,zhu_quantifying_2021}. \citet{le-scao-rush-2021-many} compared the effectiveness of prompts to those of classification samples.
When collecting datasets for probing, showing the effect of data is an important goal. Our framework considers the classification data samples, but we do not impose restrictions on the signal to probe in the classification tasks.

\paragraph{Probing methods}
The probing literature has proposed numerous diagnostic methods. This paper focuses on diagnostic classifiers, where post-hoc classifiers predict labels from representation vectors. These vectors can be a unified representation of a sequence \citep{conneau_senteval_2018,tenney2019you}, a collection of vectors from different tokens in a sequence \citep{hewitt_structural_2019}, or a pair of carefully set-up vectors that contrast between the ``control'' and the ``treatment'' \citep{hewitt_designing_2019,elazar_amnesic_2021}. We defer to \citet{belinkov_probing_2021} for a systematic overview.

Note that there are also many probing papers without post-hoc classifiers \citep{zhou-srikumar-2021-directprobe,torroba-hennigen-etal-2020-intrinsic,li-etal-2021-bert}. While many of these do not mention the term ``probing'', they nevertheless probe the intrinsics of deep neural models. In this paper, we consider only classification-based probing methods. Our framework can generalize to unsupervised probing methods in future work.

\paragraph{Reliability of tests}
When all data samples follow i.i.d assumptions, larger datasets allow higher reliability. The reliability of testing is essential in quantitative studies, including medical, societal, and educational contexts \citep{Kraemer1992reliability, Drost2011reliability,golafshani2003understanding}. \textit{Reliability} describes how possible the test results can be reproduced. Depending on the forms of these tests, there are many ways to measure reliability. The test-retest reliability (usually quantified by Pearson correlations between the test and the retest results) measures the consistency of the results across time. The internal consistency reliability (usually quantified by Cronbach's $\alpha$ \citep{cronbach1951coefficient}) measures the consistency of participants responding to a set of items. The inter-rater reliability (quantified by Cohen's $\kappa$ \citep{cohen1960coefficient} or Krippendorff's $\alpha$ \citep{krippendorff2018content}) measures the extent of agreements between the annotators.

To our knowledge, existing works reflecting on the reliability of model diagnostics rely on repeating the tests on a variety of controlled conditions \citep{aribandi-etal-2021-reliable,novikova2021robustness}. A larger variance in results indicates lower test reliability. The reliability is related to two other attributes -- validity and robustness. \textit{Validity} measures how well the test measures what it intends to measure. In a valid test, the result is right for the right reasons \citep{mccoy-etal-2019-right,ravichander-etal-2021-probing}. \textit{Robustness} measures how well the results of a test can generalize from the experimental setting to real-world settings \citep{xing-etal-2020-tasty,niu-etal-2020-evaluating}.

\section{Methodology}
\label{sec:methodology}

\subsection{Problem statement}
\label{subsec:comparison_problem}
Much of probing research considers some form of comparison problem. For example:
\begin{itemize}[nosep]
    \item Which deep neural language model encodes certain linguistic signal in an easier-to-extract manner?
    \item For a neural model, does pretraining with setting $A$ support higher probing classification performances than models pretrained on setting $B$?
    \item Is the accuracy of a simple probing classifier (e.g., logistic regressor) higher than a more complicated one (e.g., MLP with hidden layers)?
\end{itemize}
These problems are instances of comparison problems, where we compare two probing configurations. We formalize them as follows.

\begin{definition}[Probing configuration]
A \textit{probing configuration} $\mathcal{C}$ consists of $\{T, E, f\}$, where $T$ specifies the probing task (e.g., past-vs-present from the SentEval suite), $E$ is the encoder that encodes the text specified by $T$ into representation vectors (e.g., the output from the 11$^{\text{th}}$ layer of BERT\_{base}), and $f$ is the probing classifier.
\label{def:probing_configuration}
\end{definition}
\begin{remark}
Task $T$ can be a text-based classification dataset, with either word inputs or sequential inputs. Here we only consider the classification problems with fixed number of classes. For more complex problems (e.g., generalization problems), the generalization bounds need to be adapted.
\end{remark}

\begin{definition}[Comparison problem]
A \textit{comparison problem} consists of a pair of probing configurations, $\mathcal{C}_A=\{T, E_A, f_A\}$ and $\mathcal{C}_B=\{T, E_B, f_B\}$.
\label{def:comparison_problem}
\end{definition}

\begin{remark}
Usually, the two configurations of a comparison problem, $\mathcal{C}_A$ and $\mathcal{C}_B$ differ by only one of $\{E, f\}$ to avoid confounds. A comparison problem can \textit{collapse} if the two configurations are identical. Recommending the required number of data samples for a collapsed comparison problem is not meaningful.
\end{remark}

\subsection{An overview of the framework}
\label{subsec:method_framework}
For researchers collecting a probing dataset, we recommend the following procedure to estimate the probing dataset sizes:
\begin{enumerate}[nosep]
    \item Identify a comparison problem by specifying two probing configurations, and collect a small set of data in a pilot study. Using the existing data, run the two probing classifications. Let $R_1$ and $R_2$ denote the probing performances, respectively.
    \item When $|R_1 - R_2|$ is small, it is likely that the comparison problem collapses -- \S \ref{subsec:method_collapsed_comparison_problems} describes some heuristics to verify.
    \item When the comparison problem has a difference in the performances $|R_1 - R_2|$, our framework can recommend the data requirements: Plug in $\frac{|R_1 - R_2|}{2}$ to the generalization bounds to retrospectively solve for a recommendation of train data size $N_{\text{train}}$. \S \ref{subsec:method_generalization_bounds} elaborates the generalization bounds in probing classifiers. \S \ref{subsec:method_train_data_requirements} presents numerical examples.
    \item Without loss of generality, we assume that the train, validation, and test data have relative sizes of $\eta:1:1$. Then $(1+\frac{2}{\eta})N_{\text{train}}$ is the total data requirement.
\end{enumerate}

\subsection{Generalization bounds}
\label{subsec:method_generalization_bounds}
Machine learning theory literature provides many generalization bounds.
These bounds usually occur in the following form:
\begin{equation}
\label{eq:generalization_bounds_form}
    \mathbb{P}\left(|R(\hat{f}) - R(f_*)| > B(n,\delta)\right) < \delta,
\end{equation}
where $f$ is the classifier, $R(\cdot)$ is the risk, $n$ is the number of training data points, and $\delta$ is a hyper-parameter. Given $n$, a generalization bound states that, with a probability of at least $1-\delta$, the risk of the empirically optimal classifier $R(\hat{f})$ differs from the risk of the globally optimal classifier $R(f_*)$ by at most $B(n;\delta)$.
The risk is usually assumed to refer to the cross entropy loss. We show that several metrics used in probing have bounds with the form as well.

\paragraph{Accuracy} The most widely used scores to measure the probing performance include accuracy, precision, recall, and F1 score. If we substitute the risk with accuracy, the bounds can apply without loss of generality, modulo two differences: accuracy (etc.) is bounded by $B=1$ (whereas the upper bounds for loss could be larger), and is the highest with $f_*$ (whereas the loss is the lowest with $f_*$).

Note that most behavioural probes\footnote{as described in \citet{belinkov-etal-2020-interpretability}} use evaluation metrics in this category. Many structural probes use additional evaluation metrics. We discuss them below.

\paragraph{Control tasks}
It is possible that the probes, as diagnostic classifiers, rely on some irrelevant dataset statistics to boost the performance. To factor out this effect, \citet{hewitt_structural_2019} proposed to use control tasks.
In a control task setting, we need to set up an auxiliary diagnostic classification task, and take the difference of the two classifications. Note that the difference is related to information theoretic terms \citep{pimentel_information-theoretic_2020,zhu_information_2020}. Regardless, their formulations involve some intractable terms that have to be empirically ignored.

Dependent on the goal of the tasks, there are different ways to set up the auxiliary task. In the part-of-speech (PoS) probing task, for example, \citet{hewitt_structural_2019} associated each word type to a fixed PoS label. Another example is amnesic probing \citep{elazar_amnesic_2021}, which uses iterative null-space projection \citep{ravfogel_null_2020} to remove the probing task information from the representations.

\begin{restatable}[]{theorem}{ThmControlTask}
The probing results for control tasks are subject to the generalization bounds in the following form:
\begin{equation}
\label{eq:generalization_bounds_form_control_task}
    \mathbb{P}\left(|R(\hat{f}) - R(f_*)| > 2B(n,\delta)\right) < \delta
\end{equation}
\end{restatable}

\begin{Proof}
The proofs of all theorems are listed in Appendix \ref{sec:proofs_of_theorems}.
\end{Proof}

\paragraph{Minimum description length}
Recently, \citet{voita_information-theoretic_2020} presented an alternative viewpoint of structural probing based on the minimum description length (MDL). The MDL of a probe or classifier is defined by the sum of (a) the code length required to transmit the data, and (b) the code length required to transmit the model for compressing the data. \citet{voita_information-theoretic_2020} gives two ways to approximate the MDL values: variational and prequential.

The \textit{variational MDL} consists of two terms: the cross entropy loss $L(\hat{f})$, and the KL divergence between the posterior ($\beta$) and prior distribution ($\alpha$) of the model parameters $\theta$.
$$MDL_{\text{var}} = L(\hat{f}) + KL(\beta_\theta\ \|\ \alpha_\theta)$$

\begin{restatable}[]{theorem}{ThmVariationalMDL}
The probing results of variational MDLs subject to the identical bounds as Eq. \ref{eq:generalization_bounds_form}.
\end{restatable}

The \textit{prequential MDL} computes the code length required in this ``transmission protocol''. First, transmit the first $t_1$ data points using random coding. Then, optimize the model with the transmitted data, and transmit the next portion with the new model. The first portion $t_1$ constitutes of as few as $0.1\%$ of the dataset.
\begin{align*}
MDL_{\text{pre}}&=t_1\text{log}K - \\
&\sum_{i=1}^{S-1}\text{log} p_{f_i} (y_{t_i+1..t_{i+1}}|x_{t_i+1..t_{i+1}}) \\
&=t_1\text{log}K + \sum_{i=1}^{S-1} R(f_i;n_i)
\end{align*}

\begin{restatable}[]{theorem}{ThmPrequentialMDL}
The generalization bound for prequential MDL takes the following form:
\begin{equation}
    \mathbb{P}\left( |R(\hat{f}) - R(f_*)| > \frac{Cn}{t_1}B(n, \delta) \right) < \delta,
\end{equation}
where $C$ is a constant.
\end{restatable}

\subsection{From generalization bounds to training data requirement}
\label{subsec:method_train_data_requirements}
To estimate the required number of training data samples $n$, we can fix $\delta$ and enforce an upper bound on the excess risk $|R(\hat{f}) - R(f_*))|$. Then the corresponding $n$ would be the required number of training data samples. Following is a numerical example where we consider the textbook finite function space bound\footnote{This bound assumes that classifiers $f$ come from a finite space $\mathcal{F}$. We defer to Theorem 7 of \citet{liang2016cs229t} for details. In the rest of this paper, we use this finite function class bound.}:
$$\mathbb{P}\left(|R(\hat{f}) - R(f_*)| > B\sqrt{\frac{2\text{log}\frac{2|\mathcal{F}|}{\delta}}{n}}\right) < \delta.$$

Here, we set $\delta=10^{-8}$. In a probing classification configuration $\mathcal{C}=\{T, E, f\}$, the encoder $E$ produces vectors with $D=768$ dimensions and $f$ is a logistic regressor. Additionally, we assume that the $D+1$ weight parameters in $f$ are stored in 32-bit floating point numbers\footnote{Following PyTorch's default for \texttt{FloatTensor}.}, so each weight parameter takes $2^{32}$ possible values. Then the probing classifier constitutes a finite space with cardinality $|\mathcal{F}| = 2^{32} \times (D+1)$.

When there are $n=65,536$ training data points, with probability of at least $1-10^{-8}$, the empirically optimal accuracy is different from the global minimum by at most $0.039$ for $D=4,096$ (InferSent) classifications.

More importantly, we can also plug in an expectation on the generalization bound to retrospectively solve for the training data requirement. For example, a bound of $0.05$ requires $N=40\textrm{k}$ i.i.d data samples at $D=4,096$.

If the datasets for both probing configurations in a probing classification are sufficiently large, the generalization bounds would be sufficiently small, so that the result of the comparison problem is reliable. As a heuristic, we let the bound be $\frac{|R_1 - R_2|}{2}$, where $R_1$ and $R_2$ are the probing performances from the existing datasets.

A tighter bound (e.g., $\frac{|R_1 - R_2|}{10}$) requires more data samples (hence larger statistical power) as well as higher expectation for budgets. We consider $\frac{|R_1 - R_2|}{2}$ to be a balanced choice. Following are some justifications.

In the most ideal case, both $R_1$ and $R_2$ are the true global minima $R(f_*)_1$ and $R(f_*)_2$, then the comparison results will remain consistent regardless of the number of data samples.

In the less ideal case, both $R_1$ and $R_2$ are the empirical minima $R(\hat{f})_1$ and $R(\hat{f})_2$, then a generalization bound of $\frac{|R_1 - R_2|}{2}$ guarantees that the relative preference in the comparison will remain consistent (yet the scale of the comparison may fluctuate). We expect that most probing classifiers resemble this scenario, since they reach almost perfect training accuracies.

In the most unfortunate case, $R_1$ and $R_2$ deviate from the empirical minima. The extent they differ contributes to the randomness. While the scales of the empirical imperfectness remain unknown, one can consider some heuristics reduce this imperfectness. First, a probing classifier with higher accuracy tend to have smaller empirical imperfectness, hence smaller unknown instability. Second, identifying the collapsed comparisons helps reduce the uncertainties introduced by the classifier imperfectness.

\subsection{Power analysis}
\label{subsec:method_power_analysis}
We use power analysis to evaluate the reliability of our data recommendations. For a statistical test, the power is the probability of correctly rejecting the null hypothesis. In the context of this paper, we compare the reliability of the prediction results provided by two probing configurations, $\mathcal{C}_A$ and $\mathcal{C}_B$. The hypothesis is stated as follows.

$H_0$: On a test set $\{x_i\}_{i=1}^{M}$, the results $f_A$ and $f_B$ are not significantly different.

To accept or reject $H_0$ on the two probing classifiers, one can apply the McNemar's test \citep{mcnemar1947note}, which checks if the $\chi^2$ statistic is significant. The $\chi^2$ can be computed as $\chi^2 = \frac{(p_{01} - p_{10})^2}{p_{01} + p_{10}}$, where $p_{00}, p_{01}, p_{10}, p_{11}$ are the probabilities specified by the contingency table (Table \ref{tab:contingency_table}).

\begin{table}[h]
    \centering
    \begin{tabular}{c |c c}
        \toprule
        & $f_B$ incorrect & $f_B$ correct \\ \midrule
        $f_A$ incorrect & $p_{00}$ & $p_{01}$ \\
        $f_A$ correct & $p_{10}$ & $p_{11}$ \\ \midrule \bottomrule
    \end{tabular}
    \caption{Contingency table between two probing results, $f_A$ and $f_B$.}
    \label{tab:contingency_table}
\end{table}

\citet{card-etal-2020-little} described a framework that estimates the power by simulation. One repetitively samples a portion of test data and computes $\chi^2$. The portion of simulations with significant $\chi^2$ is taken as the estimated power.
Empirically, one runs multiple classifications with distinct random seeds to increase robustness. To account for multiple classifications, we run the simulations of \citet{card-etal-2020-little} for each random seed, and then count the total number of significant simulations to compute the power.
Usually, we expect that a reliable decision to reject the null hypothesis should have a statistical power of at least $0.8$.

\subsection{Detecting collapsed comparison problems}
\label{subsec:method_collapsed_comparison_problems}
When we have data for a comparison problem from a ``pilot study'' and observe very small classification performance differences (e.g., of $0.5\%$), we might fall back to the null hypothesis -- that the comparison problem collapses -- in this case, increasing the data size does not ``uncollapse'' this comparison problem. Here we describe some heuristics to increase the confidence of detecting a collapse.

In our experiments, our data are subsampled from a larger dataset, so we can test if a probing configuration collapses by repeatedly subsampling the data, and run statistical tests. In the real-world, this is similar to running multiple ``pilot studies'' and collecting small-scale probing data, repeatedly. If the probing configurations output almost indistinguishable results, one can infer that the probing configuration collapses.

Alternatively, one can consider this augmentation method based on cross validation folds. For each dataset in a comparison problem, we divide it into, e.g., 6 folds. For each of $i=1..6$ runs, take Fold $i$ as the validation split, Fold $(i+1)\textrm{ mod }6$ as the test split, and the rest as the train split. Considering the probing classification results of all 6 runs can lead to higher confidence.

\section{Experiments}
\label{sec:experiments}

\subsection{Data and Models}
\label{subsec:data_models}
\paragraph{Probing task}
We run probing classifiers on several classification tasks in one of the largest existing probing suites, SentEval \citep{conneau_senteval_2018}: Past\_present (tense prediction), bigram\_shift (whether two words are flipped in a sentence), and coordination\_inversion (whether two sentences are flipped) are binary classification tasks with 120k samples per class. Sentence\_length contains 6 classes with 12k samples per class. To test the data requirements, we stratify sample subsets with $\{2^7, 2^9, 2^{11}, 2^{13}, 2^{15}\}$ training data samples per class, where applicable\footnote{When there are $2^7$ train sample per class, the subset consists of 256 train samples, 64 dev and 64 test samples, all with evenly distributed labels. i.e., $\eta=4$. In this paper, we keep this ratio consistent.}.

\paragraph{Encoders}
\begin{itemize}[nosep]
    \item BERT \citep{devlin-etal-2019-bert} is a contextualized language model. We take the multilingual $\text{BERT}_{\text{base}}$ model
    \item SBERT \citep{reimers-2019-sentence-bert} encouraged semantically similar sentences to be mapped to nearby vectors in the representation space.
    \item GloVe \citep{pennington-etal-2014-glove} is a static word embedding model. It maps each token to a fixed, 300-dimensional vector. We average all embedding vectors of a SentEval sequence as the input representation.
    \item InferSent \citep{infersent} is a contextualized language model. It processes the GloVe embeddings with a bidirectional LSTM \citep{hochreiter1997long} with 2,048 hidden dimensions.
\end{itemize}

\paragraph{Probing classifiers} We use a logistic regressor and a multilayer perceptron (MLP) with 20 hidden units (\S \ref{subsec:experiment_compare_classifiers}) as probing classifiers. In addition, we run several MDL probes, whose results are described in Appendix \ref{subsec:experiment_other_probing_methods}.

\subsection{Verifying the theoretical bounds}
\label{subsec:experiment_theoretical_bounds_conservative}
We run probing classifications using a collection of subsets. Each subset is subsampled in a stratified manner from the dataset. We run 5 probing classifications with different random seeds on each subset.

To qualitatively examine the extent that the generalization bounds agree with the probing classifications, we plot both the empirical and the theoretical margins. Figure \ref{fig:theoretical_vs_empirical} shows an example. Appendix \ref{subsec:experiment_more_theory_vs_experiment_plots} contains additional plots. The empirical classification results reside within the theoretical margins, except for an outlier classification trial -- this is the classification suboptimality, and we extend the discussion in Appendix \ref{subsec:classifier_suboptimality}.
\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/past_present_bert_test_acc.svg}

    \caption{Theoretical bounds vs. empirical results on $T=\text{past\_present}$, $E=\text{BERT}$, and $f=\text{LogReg}$. The purple regions represent the empirical margin (mean $\pm$ stdev), while the green lines are the empirical mean $\pm$ margins computed by the learning theory bound.}
    \label{fig:theoretical_vs_empirical}
\end{figure}

\subsection{Larger datasets support higher power}
\label{subsec:experiment_add_gaussian_noise}
Intuitively, adding noise into the representation vectors makes it harder to decode the referential attribute. In this case study, we add Gaussian noise drawn from $\mathcal{N}(0, \sigma^2)$, where $\sigma^2 \in \{.01, .03, .1, .3, 1, 3\}$, and compare against the probing classification with the original representations. Figure \ref{fig:power_plot_gaussian} shows the effect of noise on a configuration. Appendix \ref{subsec:experiment_more_power_vs_noise_plots} contains additional figures. Adding noise with a larger scale results in a configuration that is easier to distinguish. In addition, a larger training dataset usually leads to a higher power to distinguish the configurations.

\begin{figure}[h]
    \centering

    \includesvg[width=\linewidth]{figures/power_plot_bert.svg}
    \caption{The powers to distinguish the representations with Gaussian noise from the original representations, for $T=\text{past\_present}$, $f=\text{LogReg}$, and $E=\text{BERT}$.}
    \label{fig:power_plot_gaussian}
\end{figure}

This case study shows that we can verify the data requirement by incrementally collecting larger datasets for comparisons until we have sufficient power. For example, on the tense prediction task, distinguishing GloVe embeddings from its counterpart with $\mathcal{N}(0, 0.1)$ noise, $1,024$ testing data samples is sufficient to lead to $0.8$ power. However, the same comparison with $\mathcal{N}(0, 0.03)$ noise requires up to $16,384$ testing data points.

The scale of Gaussian noise constitutes a spectrum. When we keep reducing the Gaussian scale, the comparison problem becomes more data-hungry. This leads to a question: where, on the ``min-max'' spectrum, do some other comparison settings (e.g., comparing between encoders) reside? In subsequent case studies, we verify that the numbers predicted by learning theory bounds have sufficient power.

\subsection{Comparing to corrupted encoders}
\label{subsec:experiment_corrupted_encoders}
In this case study, we finetune the BERT models on WikiText\footnote{\texttt{wikitext-2-v1} from huggingface datasets \citep{quentin_lhoest_2021_5510481}.} sentences with scrambled tokens for 200 steps.

Table \ref{tab:comparison_between_encoders_corrupted_bert} shows the recommended $N_{\text{train}}$ values in the probing comparisons with corresponding ``pilot data'' (subsampled) sizes. As shown in Figure \ref{fig:comparison_between_encoders_corrupted_bert}, the probing datasets with sizes no fewer than $N_{\text{test}}=256$ (i.e., $N_{\text{train}}=1024$) have sufficient power, and all recommended values fall within the ``sufficient-power'' range.

\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/bigram_shift_bert_bert_corr200.svg}
    \caption{Left: the probing accuracies of BERT (orange) and BERT ``corrupted'' by 200 steps (blue). $T=\text{bigram\_shift}$, $f=\text{LogReg}$. Right: the power to compare between them.}
    \label{fig:comparison_between_encoders_corrupted_bert}
\end{figure}

\begin{table}[h]
    \resizebox{\linewidth}{!}{
    \centering
    \begin{tabular}{r r r}
    \toprule
        Subsampled $N_{\text{test}}$ & Mean $|R_1 - R_2|$ & Recommended $N_{\text{train}}$ \\ \midrule
        64 & .1313 & 22,263\\
        256 & .1281 & 23,362 \\
        1,024 & .0879 & 49,647 \\
        4,096 & .1331 & 21,662 \\
        16,384 & .1488 & 17,331\\ \midrule \bottomrule
    \end{tabular}}
    \caption{The recommended $N_{\text{train}}$ values in the comparison problem in Figure \ref{fig:comparison_between_encoders_corrupted_bert} given different subsample sizes.}
    \label{tab:comparison_between_encoders_corrupted_bert}
\end{table}

\subsection{Comparing between encoders}
\label{subsec:experiment:compare_encoders}
In this case study, we compare pairs of configurations containing the same task, data, and probing classifier but different encoders. Figure \ref{fig:comparison_between_encoders} shows an example. A test set of size $N_{\text{test}}=1,024$ does not have sufficient power to compare the probing accuracy of BERT vs. GloVe, but $N_{\text{test}}=4,096$ does. This corresponds to $N_{\text{train}=16,384}$, indicating that the recommendations in Table \ref{tab:comparison_between_encoders} are sufficient. Appendix \ref{subsec:experiment_additional_tasks} contains two other examples supporting the same finding.

\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/comparison_bert_glove.svg}
    \caption{Left: the comparison of accuracies between BERT (orange) and GloVe (blue). $T=\text{past\_present}$, $f=\text{LogReg}$. Right: the power of this comparison. The probing classification accuracy of BERT is higher than that of GloVe, but we do not have enough power to identify that until the testing dataset size is increased to $N_{\text{test}}=4,096$.}
    \label{fig:comparison_between_encoders}
\end{figure}

\begin{table}[h]
    \resizebox{\linewidth}{!}{
    \centering
    \begin{tabular}{r r r}
    \toprule
        Subsampled $N_{\text{test}}$ & Mean $|R_1 - R_2|$ & Recommended $N_{\text{train}}$ \\ \midrule
        64 & .0344 & 324,563 \\
        256 & .0492 & 158,315 \\
        1,024 & .0355 & 303,516 \\
        4,096 & .0091 & 4,600,037 \\
        16,384 & .0320 & 373,513 \\ \midrule \bottomrule
    \end{tabular}}
    \caption{The recommended $N_{\text{train}}$ values in the comparison problem in Figure \ref{fig:comparison_between_encoders} given different subsample sizes.}
    \label{tab:comparison_between_encoders}
\end{table}

\subsection{Comparing between classifiers}
\label{subsec:experiment_compare_classifiers}
Here, we compare two probing configurations with different classifiers: LogReg vs. MLP with one hidden layer of $H=20$ neurons. Although the two configurations involve the same task, they have different training data requirements\footnote{The LogReg has $D+1=799$ parameters, while the MLP has $(D+1)H+H+1=15,401$, leading to a larger data requirement.}. We take the larger one as the recommendation.
Table \ref{tab:comparison_probing_classifiers} recommends $N_{\text{train}}$ that are larger than the SentEval dataset sizes. These numbers are actually not necessary --
Figure \ref{fig:comparison_probing_classifiers} shows that $N_{\text{test}}=16.4\textrm{k}$ (corresponding to $N_{\text{train}}=65.6\textrm{k}$) is still insufficient to distinguish the results of the two probing classifier configurations on the bigram\_shift task. There is insufficient evidence to reject the null hypothesis. In other words, the comparison problem between LogReg vs. MLP on $T=\text{bigram\_shift}$ collapses\footnote{Note that LogReg vs. MLP on other tasks e.g., $T=\text{sentence\_length}$ do not collapse. We include the results in Appendix \ref{subsec:experiment_additional_tasks}.}. The exceedingly large data recommendations are meaningless.

\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/bigram_shift_nohid_vs_hid20_bert.svg}
    \caption{A comparison between probing classifiers. $T=\text{bigram\_shift}$, $E=\text{BERT}$, $f=\{\text{LogReg (blue) vs. MLP (orange)}\}$.}
    \label{fig:comparison_probing_classifiers}
\end{figure}

\begin{table}[h]
    \resizebox{\linewidth}{!}{
    \centering
    \begin{tabular}{r r r}
    \toprule
        Subsampled $N_{\text{test}}$ & Mean $|R_1 - R_2|$ & Recommended $N_{\text{train}}$ \\ \midrule
        64 & .022 & 801,472 \\
        256 & .018 & 1,187,812 \\
        1,024 & .007 & 7,757,460 \\
        4,096 & .012 & 2,912,787 \\
        16,384 & .013 & 2,444,949 \\ \midrule \bottomrule
    \end{tabular}}
    \caption{The recommended $N_{\text{train}}$ values in the comparison problem in Figure \ref{fig:comparison_probing_classifiers} given different subsample sizes.}
    \label{tab:comparison_probing_classifiers}
\end{table}

\section{Discussion}
\paragraph{What does a high accuracy entail?}
Our framework implicitly considers the probing classification performances, but the causal relationship between, e.g., the accuracy, the data requirements, and the reliability can be explored further in future frameworks. A high probing accuracy indicates a small empirical risk $R(f)$. This could result from a small $|R(f)-R(\hat{f})|$ (the probe ``learns the task''), or a small $R(\hat{f}) - R(f_*)$ (the distribution of the data samples represent the ``true distribution'' well). The two possibilities resemble the dichotomy raised by \citet{hewitt_designing_2019}, but do they describe the same phenomenon? We leave this as an open question to future researchers.

\paragraph{On the stability of theoretical recommendations}
How stable are our theoretical recommendations? For those comparisons with sufficient evidence to reject the null hypotheses, the recommended $N_{\text{train}}$ sometimes varies (e.g., at $N_{\text{test}}=4096$ in Table \ref{tab:comparison_between_encoders}). This is brought in by the suboptimality of several probing classifications. We extend the discussions about how to interpret and reduce classifier suboptimality in Appendix \ref{subsec:classifier_suboptimality}. Future methods to estimate data requirement may improve the stability.

\paragraph{Cross-task comparison problems} Our framework does not consider cross-task comparison, i.e., when comparing $\mathcal{C}_A=\{T_A, E_A, f_A\}$ vs. $\mathcal{C}_B=\{T_B, E_B, f_B\}$ where $T_A\neq T_B$, because McNemar's test requires pairwise data. Alternative power tests would be necessary to consider cross-task comparison problems. We leave this to an open problem for future research.

\paragraph{Why not just collect as much data as possible?} We argue in favor of knowing how many data samples we need, instead of directly collecting as many samples that budgets allow. The two views resemble the ``top-down'' vs. ``bottom-up'' research approaches mentioned in \citet{bender-koller-2020-climbing}. Practically, our experiments show that many comparison problems do not need as many data samples as the sizes of some existing large probing datasets.

\paragraph{A ``recipe'' for probing datasets} To systematically probe the linguistic abilities of neural networks, many more datasets need to be collected. To make the probing dataset collection procedure systematic, a complete ``recipe'' would be beneficial. Several recent papers called for this goal \citep{ethayarajh-jurafsky-2020-utility,rodriguez-etal-2021-evaluation}. Our framework is one component of such a recipe, by quantifying questions of dataset sizes. Additional components for future work include quantifying the label distributions and the inherent `difficulties' of samples.

\section{Conclusion}
This paper presents a novel framework to estimate the data requirements for probing experiments. This framework uses generalization bounds from formal learning theory to determine minimum training set sizes. In a series of comparison problems, we verify that our recommendations provide sufficient power. Our framework describes an actionable procedure to double check if an experiment needs additional data samples to be scientifically meaningful. Additionally, this paper calls for further attention to complete a systematic methodology in evaluating probing datasets and methods.

\section{Introduction}
 While modern deep neural language models achieve impressive performance on various benchmarking datasets, the question of {\em how} this is achieved is gaining increased attention. This line of inquiry includes a new avenue of research: probing.

There are many methods to probe a neural network. Among these, diagnostic classification is by far the most common. To probe a neural network in a classification configuration, we specify a classification task that examines an ability (e.g., detecting verb tense). We encode the texts with a deep neural network and apply a post-hoc classifier to the encoded representations. If the classifier can easily predict an attribute, we consider this deep neural network capable of encoding the specified ability.
Researchers have expanded the targets of probing classifications to a wide range of abilities including syntax and semantics \citep{jawahar-etal-2019-bert,tenney-etal-2019-bert,kulmizev-etal-2020-neural,vulic-etal-2020-probing}, discourse \citep{koto-etal-2021-discourse,zhu-etal-2020-examining,chen-etal-2019-evaluation} and commonsense reasoning \citep{petroni-etal-2019-language,lin-etal-2020-birds}. These probing papers are associated with datasets of varying sizes, as shown in Figure \ref{fig:probing_dataset_sizes}.
\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/probing_datasets_sizes.png}
    \caption{Sizes of the datasets in some common probing suites. Depending on the tasks, they vary from hundreds to larger than $10^5$.}
    \label{fig:probing_dataset_sizes}
\end{figure}

What is a suitable size for probing datasets? Larger training datasets lead to tighter generalization bounds. With other conditions fixed, larger testing datasets allow for higher statistical power in comparing probing models and classifiers. That said, it is neither realistic nor desirable to increase the probing dataset sizes arbitrarily. It is therefore essential to find a balanced size for probing classifications.

We propose a framework to formally estimate the data requirements of probing configurations (\S \ref{sec:methodology}). Our framework considers the scenario of comparing probing configurations given some data. How many additional data samples may be necessary to reliably reproduce this comparison effect? We propose a novel method to estimate the required data samples by adapting a generalization bound.

We evaluate our framework on various probing tasks. First, we verify that the choice of generalization bound agrees with the probing results (\S \ref{subsec:experiment_theoretical_bounds_conservative}). On a case study recognizing synthetic Gaussian noise, we verify that larger datasets provide higher statistical power (\S \ref{subsec:experiment_add_gaussian_noise}). We evaluate the utility of our framework on a collection of comparison problems (\S \ref{subsec:experiment_corrupted_encoders} - \S \ref{subsec:experiment:compare_encoders}), where the probing data sizes recommended by the theoretical framework always supports power larger than $0.8$.
This paper helps to formalize probing experiments. Our framework can be used by the research community in collecting probing datasets.

\section{Related Work}
\paragraph{Understanding the datasets} There is increased research attention paid to the datasets used for deep learning models.
One way to study the dataset is to visualize each of the dataset samples in a map. \citet{swayamdipta-etal-2020-dataset} mapped the data samples in NLP datasets to regions such as ``hard-to-learn'' and ``easy-to-learn'' using signals observed during the training process. \citet{yauney2021comparing} mapped the difficulty of data samples by the data-dependent complexity \citep{arora2019fine}. \citet{vania-etal-2021-comparing} used Item Response Theory \citep{baker2004item}, a statistical framework from psychometrics to describe various attributes related to the difficulty of test set items.
Similarly, researchers also describe the effects of datasets as a whole. Several papers attempted through information theory \citep{pimentel2021bayesian,zhu_quantifying_2021}. \citet{le-scao-rush-2021-many} compared the effectiveness of prompts to those of classification samples.
When collecting datasets for probing, showing the effect of data is an important goal. Our framework considers the classification data samples, but we do not impose restrictions on the signal to probe in the classification tasks.

\paragraph{Probing methods}
The probing literature has proposed numerous diagnostic methods. This paper focuses on diagnostic classifiers, where post-hoc classifiers predict labels from representation vectors. These vectors can be a unified representation of a sequence \citep{conneau_senteval_2018,tenney2019you}, a collection of vectors from different tokens in a sequence \citep{hewitt_structural_2019}, or a pair of carefully set-up vectors that contrast between the ``control'' and the ``treatment'' \citep{hewitt_designing_2019,elazar_amnesic_2021}. We defer to \citet{belinkov_probing_2021} for a systematic overview.

Note that there are also many probing papers without post-hoc classifiers \citep{zhou-srikumar-2021-directprobe,torroba-hennigen-etal-2020-intrinsic,li-etal-2021-bert}. While many of these do not mention the term ``probing'', they nevertheless probe the intrinsics of deep neural models. In this paper, we consider only classification-based probing methods. Our framework can generalize to unsupervised probing methods in future work.

\paragraph{Reliability of tests}
When all data samples follow i.i.d assumptions, larger datasets allow higher reliability. The reliability of testing is essential in quantitative studies, including medical, societal, and educational contexts \citep{Kraemer1992reliability, Drost2011reliability,golafshani2003understanding}. \textit{Reliability} describes how possible the test results can be reproduced. Depending on the forms of these tests, there are many ways to measure reliability. The test-retest reliability (usually quantified by Pearson correlations between the test and the retest results) measures the consistency of the results across time. The internal consistency reliability (usually quantified by Cronbach's $\alpha$ \citep{cronbach1951coefficient}) measures the consistency of participants responding to a set of items. The inter-rater reliability (quantified by Cohen's $\kappa$ \citep{cohen1960coefficient} or Krippendorff's $\alpha$ \citep{krippendorff2018content}) measures the extent of agreements between the annotators.

To our knowledge, existing works reflecting on the reliability of model diagnostics rely on repeating the tests on a variety of controlled conditions \citep{aribandi-etal-2021-reliable,novikova2021robustness}. A larger variance in results indicates lower test reliability. The reliability is related to two other attributes -- validity and robustness. \textit{Validity} measures how well the test measures what it intends to measure. In a valid test, the result is right for the right reasons \citep{mccoy-etal-2019-right,ravichander-etal-2021-probing}. \textit{Robustness} measures how well the results of a test can generalize from the experimental setting to real-world settings \citep{xing-etal-2020-tasty,niu-etal-2020-evaluating}.

\section{Methodology}
\label{sec:methodology}

\subsection{Problem statement}
\label{subsec:comparison_problem}
Much of probing research considers some form of comparison problem. For example:
\begin{itemize}[nosep]
    \item Which deep neural language model encodes certain linguistic signal in an easier-to-extract manner?
    \item For a neural model, does pretraining with setting $A$ support higher probing classification performances than models pretrained on setting $B$?
    \item Is the accuracy of a simple probing classifier (e.g., logistic regressor) higher than a more complicated one (e.g., MLP with hidden layers)?
\end{itemize}
These problems are instances of comparison problems, where we compare two probing configurations. We formalize them as follows.

\begin{definition}[Probing configuration]
A \textit{probing configuration} $\mathcal{C}$ consists of $\{T, E, f\}$, where $T$ specifies the probing task (e.g., past-vs-present from the SentEval suite), $E$ is the encoder that encodes the text specified by $T$ into representation vectors (e.g., the output from the 11$^{\text{th}}$ layer of BERT\_{base}), and $f$ is the probing classifier.
\label{def:probing_configuration}
\end{definition}
\begin{remark}
Task $T$ can be a text-based classification dataset, with either word inputs or sequential inputs. Here we only consider the classification problems with fixed number of classes. For more complex problems (e.g., generalization problems), the generalization bounds need to be adapted.
\end{remark}

\begin{definition}[Comparison problem]
A \textit{comparison problem} consists of a pair of probing configurations, $\mathcal{C}_A=\{T, E_A, f_A\}$ and $\mathcal{C}_B=\{T, E_B, f_B\}$.
\label{def:comparison_problem}
\end{definition}

\begin{remark}
Usually, the two configurations of a comparison problem, $\mathcal{C}_A$ and $\mathcal{C}_B$ differ by only one of $\{E, f\}$ to avoid confounds. A comparison problem can \textit{collapse} if the two configurations are identical. Recommending the required number of data samples for a collapsed comparison problem is not meaningful.
\end{remark}

\subsection{An overview of the framework}
\label{subsec:method_framework}
For researchers collecting a probing dataset, we recommend the following procedure to estimate the probing dataset sizes:
\begin{enumerate}[nosep]
    \item Identify a comparison problem by specifying two probing configurations, and collect a small set of data in a pilot study. Using the existing data, run the two probing classifications. Let $R_1$ and $R_2$ denote the probing performances, respectively.
    \item When $|R_1 - R_2|$ is small, it is likely that the comparison problem collapses -- \S \ref{subsec:method_collapsed_comparison_problems} describes some heuristics to verify.
    \item When the comparison problem has a difference in the performances $|R_1 - R_2|$, our framework can recommend the data requirements: Plug in $\frac{|R_1 - R_2|}{2}$ to the generalization bounds to retrospectively solve for a recommendation of train data size $N_{\text{train}}$. \S \ref{subsec:method_generalization_bounds} elaborates the generalization bounds in probing classifiers. \S \ref{subsec:method_train_data_requirements} presents numerical examples.
    \item Without loss of generality, we assume that the train, validation, and test data have relative sizes of $\eta:1:1$. Then $(1+\frac{2}{\eta})N_{\text{train}}$ is the total data requirement.
\end{enumerate}

\subsection{Generalization bounds}
\label{subsec:method_generalization_bounds}
Machine learning theory literature provides many generalization bounds.
These bounds usually occur in the following form:
\begin{equation}
\label{eq:generalization_bounds_form}
    \mathbb{P}\left(|R(\hat{f}) - R(f_*)| > B(n,\delta)\right) < \delta,
\end{equation}
where $f$ is the classifier, $R(\cdot)$ is the risk, $n$ is the number of training data points, and $\delta$ is a hyper-parameter. Given $n$, a generalization bound states that, with a probability of at least $1-\delta$, the risk of the empirically optimal classifier $R(\hat{f})$ differs from the risk of the globally optimal classifier $R(f_*)$ by at most $B(n;\delta)$.
The risk is usually assumed to refer to the cross entropy loss. We show that several metrics used in probing have bounds with the form as well.

\paragraph{Accuracy} The most widely used scores to measure the probing performance include accuracy, precision, recall, and F1 score. If we substitute the risk with accuracy, the bounds can apply without loss of generality, modulo two differences: accuracy (etc.) is bounded by $B=1$ (whereas the upper bounds for loss could be larger), and is the highest with $f_*$ (whereas the loss is the lowest with $f_*$).

Note that most behavioural probes\footnote{as described in \citet{belinkov-etal-2020-interpretability}} use evaluation metrics in this category. Many structural probes use additional evaluation metrics. We discuss them below.

\paragraph{Control tasks}
It is possible that the probes, as diagnostic classifiers, rely on some irrelevant dataset statistics to boost the performance. To factor out this effect, \citet{hewitt_structural_2019} proposed to use control tasks.
In a control task setting, we need to set up an auxiliary diagnostic classification task, and take the difference of the two classifications. Note that the difference is related to information theoretic terms \citep{pimentel_information-theoretic_2020,zhu_information_2020}. Regardless, their formulations involve some intractable terms that have to be empirically ignored.

Dependent on the goal of the tasks, there are different ways to set up the auxiliary task. In the part-of-speech (PoS) probing task, for example, \citet{hewitt_structural_2019} associated each word type to a fixed PoS label. Another example is amnesic probing \citep{elazar_amnesic_2021}, which uses iterative null-space projection \citep{ravfogel_null_2020} to remove the probing task information from the representations.

\begin{restatable}[]{theorem}{ThmControlTask}
The probing results for control tasks are subject to the generalization bounds in the following form:
\begin{equation}
\label{eq:generalization_bounds_form_control_task}
    \mathbb{P}\left(|R(\hat{f}) - R(f_*)| > 2B(n,\delta)\right) < \delta
\end{equation}
\end{restatable}

\begin{Proof}
The proofs of all theorems are listed in Appendix \ref{sec:proofs_of_theorems}.
\end{Proof}

\paragraph{Minimum description length}
Recently, \citet{voita_information-theoretic_2020} presented an alternative viewpoint of structural probing based on the minimum description length (MDL). The MDL of a probe or classifier is defined by the sum of (a) the code length required to transmit the data, and (b) the code length required to transmit the model for compressing the data. \citet{voita_information-theoretic_2020} gives two ways to approximate the MDL values: variational and prequential.

The \textit{variational MDL} consists of two terms: the cross entropy loss $L(\hat{f})$, and the KL divergence between the posterior ($\beta$) and prior distribution ($\alpha$) of the model parameters $\theta$.
$$MDL_{\text{var}} = L(\hat{f}) + KL(\beta_\theta\ \|\ \alpha_\theta)$$

\begin{restatable}[]{theorem}{ThmVariationalMDL}
The probing results of variational MDLs subject to the identical bounds as Eq. \ref{eq:generalization_bounds_form}.
\end{restatable}

The \textit{prequential MDL} computes the code length required in this ``transmission protocol''. First, transmit the first $t_1$ data points using random coding. Then, optimize the model with the transmitted data, and transmit the next portion with the new model. The first portion $t_1$ constitutes of as few as $0.1\%$ of the dataset.
\begin{align*}
MDL_{\text{pre}}&=t_1\text{log}K - \\
&\sum_{i=1}^{S-1}\text{log} p_{f_i} (y_{t_i+1..t_{i+1}}|x_{t_i+1..t_{i+1}}) \\
&=t_1\text{log}K + \sum_{i=1}^{S-1} R(f_i;n_i)
\end{align*}

\begin{restatable}[]{theorem}{ThmPrequentialMDL}
The generalization bound for prequential MDL takes the following form:
\begin{equation}
    \mathbb{P}\left( |R(\hat{f}) - R(f_*)| > \frac{Cn}{t_1}B(n, \delta) \right) < \delta,
\end{equation}
where $C$ is a constant.
\end{restatable}

\subsection{From generalization bounds to training data requirement}
\label{subsec:method_train_data_requirements}
To estimate the required number of training data samples $n$, we can fix $\delta$ and enforce an upper bound on the excess risk $|R(\hat{f}) - R(f_*))|$. Then the corresponding $n$ would be the required number of training data samples. Following is a numerical example where we consider the textbook finite function space bound\footnote{This bound assumes that classifiers $f$ come from a finite space $\mathcal{F}$. We defer to Theorem 7 of \citet{liang2016cs229t} for details. In the rest of this paper, we use this finite function class bound.}:
$$\mathbb{P}\left(|R(\hat{f}) - R(f_*)| > B\sqrt{\frac{2\text{log}\frac{2|\mathcal{F}|}{\delta}}{n}}\right) < \delta.$$

Here, we set $\delta=10^{-8}$. In a probing classification configuration $\mathcal{C}=\{T, E, f\}$, the encoder $E$ produces vectors with $D=768$ dimensions and $f$ is a logistic regressor. Additionally, we assume that the $D+1$ weight parameters in $f$ are stored in 32-bit floating point numbers\footnote{Following PyTorch's default for \texttt{FloatTensor}.}, so each weight parameter takes $2^{32}$ possible values. Then the probing classifier constitutes a finite space with cardinality $|\mathcal{F}| = 2^{32} \times (D+1)$.

When there are $n=65,536$ training data points, with probability of at least $1-10^{-8}$, the empirically optimal accuracy is different from the global minimum by at most $0.039$ for $D=4,096$ (InferSent) classifications.

More importantly, we can also plug in an expectation on the generalization bound to retrospectively solve for the training data requirement. For example, a bound of $0.05$ requires $N=40\textrm{k}$ i.i.d data samples at $D=4,096$.

If the datasets for both probing configurations in a probing classification are sufficiently large, the generalization bounds would be sufficiently small, so that the result of the comparison problem is reliable. As a heuristic, we let the bound be $\frac{|R_1 - R_2|}{2}$, where $R_1$ and $R_2$ are the probing performances from the existing datasets.

A tighter bound (e.g., $\frac{|R_1 - R_2|}{10}$) requires more data samples (hence larger statistical power) as well as higher expectation for budgets. We consider $\frac{|R_1 - R_2|}{2}$ to be a balanced choice. Following are some justifications.

In the most ideal case, both $R_1$ and $R_2$ are the true global minima $R(f_*)_1$ and $R(f_*)_2$, then the comparison results will remain consistent regardless of the number of data samples.

In the less ideal case, both $R_1$ and $R_2$ are the empirical minima $R(\hat{f})_1$ and $R(\hat{f})_2$, then a generalization bound of $\frac{|R_1 - R_2|}{2}$ guarantees that the relative preference in the comparison will remain consistent (yet the scale of the comparison may fluctuate). We expect that most probing classifiers resemble this scenario, since they reach almost perfect training accuracies.

In the most unfortunate case, $R_1$ and $R_2$ deviate from the empirical minima. The extent they differ contributes to the randomness. While the scales of the empirical imperfectness remain unknown, one can consider some heuristics reduce this imperfectness. First, a probing classifier with higher accuracy tend to have smaller empirical imperfectness, hence smaller unknown instability. Second, identifying the collapsed comparisons helps reduce the uncertainties introduced by the classifier imperfectness.

\subsection{Power analysis}
\label{subsec:method_power_analysis}
We use power analysis to evaluate the reliability of our data recommendations. For a statistical test, the power is the probability of correctly rejecting the null hypothesis. In the context of this paper, we compare the reliability of the prediction results provided by two probing configurations, $\mathcal{C}_A$ and $\mathcal{C}_B$. The hypothesis is stated as follows.

$H_0$: On a test set $\{x_i\}_{i=1}^{M}$, the results $f_A$ and $f_B$ are not significantly different.

To accept or reject $H_0$ on the two probing classifiers, one can apply the McNemar's test \citep{mcnemar1947note}, which checks if the $\chi^2$ statistic is significant. The $\chi^2$ can be computed as $\chi^2 = \frac{(p_{01} - p_{10})^2}{p_{01} + p_{10}}$, where $p_{00}, p_{01}, p_{10}, p_{11}$ are the probabilities specified by the contingency table (Table \ref{tab:contingency_table}).

\begin{table}[h]
    \centering
    \begin{tabular}{c |c c}
        \toprule
        & $f_B$ incorrect & $f_B$ correct \\ \midrule
        $f_A$ incorrect & $p_{00}$ & $p_{01}$ \\
        $f_A$ correct & $p_{10}$ & $p_{11}$ \\ \midrule \bottomrule
    \end{tabular}
    \caption{Contingency table between two probing results, $f_A$ and $f_B$.}
    \label{tab:contingency_table}
\end{table}

\citet{card-etal-2020-little} described a framework that estimates the power by simulation. One repetitively samples a portion of test data and computes $\chi^2$. The portion of simulations with significant $\chi^2$ is taken as the estimated power.
Empirically, one runs multiple classifications with distinct random seeds to increase robustness. To account for multiple classifications, we run the simulations of \citet{card-etal-2020-little} for each random seed, and then count the total number of significant simulations to compute the power.
Usually, we expect that a reliable decision to reject the null hypothesis should have a statistical power of at least $0.8$.

\subsection{Detecting collapsed comparison problems}
\label{subsec:method_collapsed_comparison_problems}
When we have data for a comparison problem from a ``pilot study'' and observe very small classification performance differences (e.g., of $0.5\%$), we might fall back to the null hypothesis -- that the comparison problem collapses -- in this case, increasing the data size does not ``uncollapse'' this comparison problem. Here we describe some heuristics to increase the confidence of detecting a collapse.

In our experiments, our data are subsampled from a larger dataset, so we can test if a probing configuration collapses by repeatedly subsampling the data, and run statistical tests. In the real-world, this is similar to running multiple ``pilot studies'' and collecting small-scale probing data, repeatedly. If the probing configurations output almost indistinguishable results, one can infer that the probing configuration collapses.

Alternatively, one can consider this augmentation method based on cross validation folds. For each dataset in a comparison problem, we divide it into, e.g., 6 folds. For each of $i=1..6$ runs, take Fold $i$ as the validation split, Fold $(i+1)\textrm{ mod }6$ as the test split, and the rest as the train split. Considering the probing classification results of all 6 runs can lead to higher confidence.

\section{Experiments}
\label{sec:experiments}

\subsection{Data and Models}
\label{subsec:data_models}
\paragraph{Probing task}
We run probing classifiers on several classification tasks in one of the largest existing probing suites, SentEval \citep{conneau_senteval_2018}: Past\_present (tense prediction), bigram\_shift (whether two words are flipped in a sentence), and coordination\_inversion (whether two sentences are flipped) are binary classification tasks with 120k samples per class. Sentence\_length contains 6 classes with 12k samples per class. To test the data requirements, we stratify sample subsets with $\{2^7, 2^9, 2^{11}, 2^{13}, 2^{15}\}$ training data samples per class, where applicable\footnote{When there are $2^7$ train sample per class, the subset consists of 256 train samples, 64 dev and 64 test samples, all with evenly distributed labels. i.e., $\eta=4$. In this paper, we keep this ratio consistent.}.

\paragraph{Encoders}
\begin{itemize}[nosep]
    \item BERT \citep{devlin-etal-2019-bert} is a contextualized language model. We take the multilingual $\text{BERT}_{\text{base}}$ model
    \item SBERT \citep{reimers-2019-sentence-bert} encouraged semantically similar sentences to be mapped to nearby vectors in the representation space.
    \item GloVe \citep{pennington-etal-2014-glove} is a static word embedding model. It maps each token to a fixed, 300-dimensional vector. We average all embedding vectors of a SentEval sequence as the input representation.
    \item InferSent \citep{infersent} is a contextualized language model. It processes the GloVe embeddings with a bidirectional LSTM \citep{hochreiter1997long} with 2,048 hidden dimensions.
\end{itemize}

\paragraph{Probing classifiers} We use a logistic regressor and a multilayer perceptron (MLP) with 20 hidden units (\S \ref{subsec:experiment_compare_classifiers}) as probing classifiers. In addition, we run several MDL probes, whose results are described in Appendix \ref{subsec:experiment_other_probing_methods}.

\subsection{Verifying the theoretical bounds}
\label{subsec:experiment_theoretical_bounds_conservative}
We run probing classifications using a collection of subsets. Each subset is subsampled in a stratified manner from the dataset. We run 5 probing classifications with different random seeds on each subset.

To qualitatively examine the extent that the generalization bounds agree with the probing classifications, we plot both the empirical and the theoretical margins. Figure \ref{fig:theoretical_vs_empirical} shows an example. Appendix \ref{subsec:experiment_more_theory_vs_experiment_plots} contains additional plots. The empirical classification results reside within the theoretical margins, except for an outlier classification trial -- this is the classification suboptimality, and we extend the discussion in Appendix \ref{subsec:classifier_suboptimality}.
\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/past_present_bert_test_acc.svg}

    \caption{Theoretical bounds vs. empirical results on $T=\text{past\_present}$, $E=\text{BERT}$, and $f=\text{LogReg}$. The purple regions represent the empirical margin (mean $\pm$ stdev), while the green lines are the empirical mean $\pm$ margins computed by the learning theory bound.}
    \label{fig:theoretical_vs_empirical}
\end{figure}

\subsection{Larger datasets support higher power}
\label{subsec:experiment_add_gaussian_noise}
Intuitively, adding noise into the representation vectors makes it harder to decode the referential attribute. In this case study, we add Gaussian noise drawn from $\mathcal{N}(0, \sigma^2)$, where $\sigma^2 \in \{.01, .03, .1, .3, 1, 3\}$, and compare against the probing classification with the original representations. Figure \ref{fig:power_plot_gaussian} shows the effect of noise on a configuration. Appendix \ref{subsec:experiment_more_power_vs_noise_plots} contains additional figures. Adding noise with a larger scale results in a configuration that is easier to distinguish. In addition, a larger training dataset usually leads to a higher power to distinguish the configurations.

\begin{figure}[h]
    \centering

    \includesvg[width=\linewidth]{figures/power_plot_bert.svg}
    \caption{The powers to distinguish the representations with Gaussian noise from the original representations, for $T=\text{past\_present}$, $f=\text{LogReg}$, and $E=\text{BERT}$.}
    \label{fig:power_plot_gaussian}
\end{figure}

This case study shows that we can verify the data requirement by incrementally collecting larger datasets for comparisons until we have sufficient power. For example, on the tense prediction task, distinguishing GloVe embeddings from its counterpart with $\mathcal{N}(0, 0.1)$ noise, $1,024$ testing data samples is sufficient to lead to $0.8$ power. However, the same comparison with $\mathcal{N}(0, 0.03)$ noise requires up to $16,384$ testing data points.

The scale of Gaussian noise constitutes a spectrum. When we keep reducing the Gaussian scale, the comparison problem becomes more data-hungry. This leads to a question: where, on the ``min-max'' spectrum, do some other comparison settings (e.g., comparing between encoders) reside? In subsequent case studies, we verify that the numbers predicted by learning theory bounds have sufficient power.

\subsection{Comparing to corrupted encoders}
\label{subsec:experiment_corrupted_encoders}
In this case study, we finetune the BERT models on WikiText\footnote{\texttt{wikitext-2-v1} from huggingface datasets \citep{quentin_lhoest_2021_5510481}.} sentences with scrambled tokens for 200 steps.

Table \ref{tab:comparison_between_encoders_corrupted_bert} shows the recommended $N_{\text{train}}$ values in the probing comparisons with corresponding ``pilot data'' (subsampled) sizes. As shown in Figure \ref{fig:comparison_between_encoders_corrupted_bert}, the probing datasets with sizes no fewer than $N_{\text{test}}=256$ (i.e., $N_{\text{train}}=1024$) have sufficient power, and all recommended values fall within the ``sufficient-power'' range.

\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/bigram_shift_bert_bert_corr200.svg}
    \caption{Left: the probing accuracies of BERT (orange) and BERT ``corrupted'' by 200 steps (blue). $T=\text{bigram\_shift}$, $f=\text{LogReg}$. Right: the power to compare between them.}
    \label{fig:comparison_between_encoders_corrupted_bert}
\end{figure}

\begin{table}[h]
    \resizebox{\linewidth}{!}{
    \centering
    \begin{tabular}{r r r}
    \toprule
        Subsampled $N_{\text{test}}$ & Mean $|R_1 - R_2|$ & Recommended $N_{\text{train}}$ \\ \midrule
        64 & .1313 & 22,263\\
        256 & .1281 & 23,362 \\
        1,024 & .0879 & 49,647 \\
        4,096 & .1331 & 21,662 \\
        16,384 & .1488 & 17,331\\ \midrule \bottomrule
    \end{tabular}}
    \caption{The recommended $N_{\text{train}}$ values in the comparison problem in Figure \ref{fig:comparison_between_encoders_corrupted_bert} given different subsample sizes.}
    \label{tab:comparison_between_encoders_corrupted_bert}
\end{table}

\subsection{Comparing between encoders}
\label{subsec:experiment:compare_encoders}
In this case study, we compare pairs of configurations containing the same task, data, and probing classifier but different encoders. Figure \ref{fig:comparison_between_encoders} shows an example. A test set of size $N_{\text{test}}=1,024$ does not have sufficient power to compare the probing accuracy of BERT vs. GloVe, but $N_{\text{test}}=4,096$ does. This corresponds to $N_{\text{train}=16,384}$, indicating that the recommendations in Table \ref{tab:comparison_between_encoders} are sufficient. Appendix \ref{subsec:experiment_additional_tasks} contains two other examples supporting the same finding.

\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/comparison_bert_glove.svg}
    \caption{Left: the comparison of accuracies between BERT (orange) and GloVe (blue). $T=\text{past\_present}$, $f=\text{LogReg}$. Right: the power of this comparison. The probing classification accuracy of BERT is higher than that of GloVe, but we do not have enough power to identify that until the testing dataset size is increased to $N_{\text{test}}=4,096$.}
    \label{fig:comparison_between_encoders}
\end{figure}

\begin{table}[h]
    \resizebox{\linewidth}{!}{
    \centering
    \begin{tabular}{r r r}
    \toprule
        Subsampled $N_{\text{test}}$ & Mean $|R_1 - R_2|$ & Recommended $N_{\text{train}}$ \\ \midrule
        64 & .0344 & 324,563 \\
        256 & .0492 & 158,315 \\
        1,024 & .0355 & 303,516 \\
        4,096 & .0091 & 4,600,037 \\
        16,384 & .0320 & 373,513 \\ \midrule \bottomrule
    \end{tabular}}
    \caption{The recommended $N_{\text{train}}$ values in the comparison problem in Figure \ref{fig:comparison_between_encoders} given different subsample sizes.}
    \label{tab:comparison_between_encoders}
\end{table}

\subsection{Comparing between classifiers}
\label{subsec:experiment_compare_classifiers}
Here, we compare two probing configurations with different classifiers: LogReg vs. MLP with one hidden layer of $H=20$ neurons. Although the two configurations involve the same task, they have different training data requirements\footnote{The LogReg has $D+1=799$ parameters, while the MLP has $(D+1)H+H+1=15,401$, leading to a larger data requirement.}. We take the larger one as the recommendation.
Table \ref{tab:comparison_probing_classifiers} recommends $N_{\text{train}}$ that are larger than the SentEval dataset sizes. These numbers are actually not necessary --
Figure \ref{fig:comparison_probing_classifiers} shows that $N_{\text{test}}=16.4\textrm{k}$ (corresponding to $N_{\text{train}}=65.6\textrm{k}$) is still insufficient to distinguish the results of the two probing classifier configurations on the bigram\_shift task. There is insufficient evidence to reject the null hypothesis. In other words, the comparison problem between LogReg vs. MLP on $T=\text{bigram\_shift}$ collapses\footnote{Note that LogReg vs. MLP on other tasks e.g., $T=\text{sentence\_length}$ do not collapse. We include the results in Appendix \ref{subsec:experiment_additional_tasks}.}. The exceedingly large data recommendations are meaningless.

\begin{figure}[h]
    \centering
    \includesvg[width=\linewidth]{figures/bigram_shift_nohid_vs_hid20_bert.svg}
    \caption{A comparison between probing classifiers. $T=\text{bigram\_shift}$, $E=\text{BERT}$, $f=\{\text{LogReg (blue) vs. MLP (orange)}\}$.}
    \label{fig:comparison_probing_classifiers}
\end{figure}

\begin{table}[h]
    \resizebox{\linewidth}{!}{
    \centering
    \begin{tabular}{r r r}
    \toprule
        Subsampled $N_{\text{test}}$ & Mean $|R_1 - R_2|$ & Recommended $N_{\text{train}}$ \\ \midrule
        64 & .022 & 801,472 \\
        256 & .018 & 1,187,812 \\
        1,024 & .007 & 7,757,460 \\
        4,096 & .012 & 2,912,787 \\
        16,384 & .013 & 2,444,949 \\ \midrule \bottomrule
    \end{tabular}}
    \caption{The recommended $N_{\text{train}}$ values in the comparison problem in Figure \ref{fig:comparison_probing_classifiers} given different subsample sizes.}
    \label{tab:comparison_probing_classifiers}
\end{table}

\section{Discussion}
\paragraph{What does a high accuracy entail?}
Our framework implicitly considers the probing classification performances, but the causal relationship between, e.g., the accuracy, the data requirements, and the reliability can be explored further in future frameworks. A high probing accuracy indicates a small empirical risk $R(f)$. This could result from a small $|R(f)-R(\hat{f})|$ (the probe ``learns the task''), or a small $R(\hat{f}) - R(f_*)$ (the distribution of the data samples represent the ``true distribution'' well). The two possibilities resemble the dichotomy raised by \citet{hewitt_designing_2019}, but do they describe the same phenomenon? We leave this as an open question to future researchers.

\paragraph{On the stability of theoretical recommendations}
How stable are our theoretical recommendations? For those comparisons with sufficient evidence to reject the null hypotheses, the recommended $N_{\text{train}}$ sometimes varies (e.g., at $N_{\text{test}}=4096$ in Table \ref{tab:comparison_between_encoders}). This is brought in by the suboptimality of several probing classifications. We extend the discussions about how to interpret and reduce classifier suboptimality in Appendix \ref{subsec:classifier_suboptimality}. Future methods to estimate data requirement may improve the stability.

\paragraph{Cross-task comparison problems} Our framework does not consider cross-task comparison, i.e., when comparing $\mathcal{C}_A=\{T_A, E_A, f_A\}$ vs. $\mathcal{C}_B=\{T_B, E_B, f_B\}$ where $T_A\neq T_B$, because McNemar's test requires pairwise data. Alternative power tests would be necessary to consider cross-task comparison problems. We leave this to an open problem for future research.

\paragraph{Why not just collect as much data as possible?} We argue in favor of knowing how many data samples we need, instead of directly collecting as many samples that budgets allow. The two views resemble the ``top-down'' vs. ``bottom-up'' research approaches mentioned in \citet{bender-koller-2020-climbing}. Practically, our experiments show that many comparison problems do not need as many data samples as the sizes of some existing large probing datasets.

\paragraph{A ``recipe'' for probing datasets} To systematically probe the linguistic abilities of neural networks, many more datasets need to be collected. To make the probing dataset collection procedure systematic, a complete ``recipe'' would be beneficial. Several recent papers called for this goal \citep{ethayarajh-jurafsky-2020-utility,rodriguez-etal-2021-evaluation}. Our framework is one component of such a recipe, by quantifying questions of dataset sizes. Additional components for future work include quantifying the label distributions and the inherent `difficulties' of samples.

\section{Conclusion}
This paper presents a novel framework to estimate the data requirements for probing experiments. This framework uses generalization bounds from formal learning theory to determine minimum training set sizes. In a series of comparison problems, we verify that our recommendations provide sufficient power. Our framework describes an actionable procedure to double check if an experiment needs additional data samples to be scientifically meaningful. Additionally, this paper calls for further attention to complete a systematic methodology in evaluating probing datasets and methods.