\section{Introduction}
``The story had held us, round the fire, sufficiently breathless, but except the obvious remark that it was gruesome...I remember no comment uttered till somebody happened to say that it was the only case he had met in which such a visitation had fallen on a child.'' This is the opening line to Henry James's ``The Turning Of The Screw'' \citep{James2008} and summarizes a key and counter-intuitive aspect of scary stories: they can be both revolting and captivating; they capture a fundamental emotion, fear \citep{Adolphs2013}, but in doing so, provide entertainment. The closest analogy might be how spicy foods cause pain yet are tasty. We understand what makes food spicy, and can tailor a meal's spice to fit one's palate, yet it is less clear how to generate fear in a story because we do not know the ingredients that make a story scary. This is a special case of a more general issue, in which we do not yet fully understand how stories elicit particular emotions, i.e., what emotion the reader should feel, in contrast to detecting the emotion a writer expresses \citep{Alhuzali2021,Strapparava2008}

In this paper, begin to understand how stories make readers scared by quantifying patterns in scary stories. First, we analyze the topics associated with scary stories, and find writers are making fewer stories about houses and more stories about human bodies, school, and diseases, potentially to stay topical. We then develop a method to quantify more universal patterns in scary stories by measuring the percentage of times a word appears in scary and non-scary stories, a metric which we call Scary Story Token Prevalence (SSToP). Words with high SSToPs, such as \emph{creature} or \emph{silhouette}, are more likely to be human-like words, suggesting scary story writers intentionally use words that are semi-human. Finally, we analyze where writers use high SSToP words or words expressing fear within a story. We find that stories can be decomposed into modes where the high SSToP or fearful words appear in regular intervals, and combinations of these modes are used to develop scary story patterns. Overall, these results lend insight into how stories express fear, and patterns writers exploit to make scary stories.

Our contributions can be summarized as follows:
\begin{itemize}
    \item we analyze dynamic patterns of scary stories to understand what themes have become popular or fell out of favor.
    \item we analyze static patterns, such as the relationship between scary story nouns like ``human'' to capture what words writers use and why they might use those words
    \item we capture how scary stories are written by quantifying the common scary story modes. We find some modes are particularly common, which offers clues about how writers make a scary story.
\end{itemize}

\section{Related Work}

\subsection{Uncanny Valley}
What makes something scary is most similar to previous work on the uncanny valley effect. Research on the uncanny valley began with Jentsch and Freud who coined the term \emph{unheimlich} (literally, ``unhomely'') when referencing human uncanniness and eeriness \citep{Freud1909,Jentsch1906}. The uncanny valley also came into prominence among human-computer interaction (HCI) and human-robot interaction (HRI) researchers with a paper by Mori (\citeyear{MoriUncannValley}). Researchers were inspired by Mori to learn what can make a robot unsettling \citep{Broadbent2017} because willingness to work with robots can depend on their likability \citep{Destephe2015}. An objective definition of uncanny (what makes something human-like) or valley (what is and is not unsettling) is still, however, a fiercely debated topic \citep{Mathur2016,Langer2018,Mathur2020,Palomaki2018,MacDorman2006,Ho2017}. Moreover, the qualitative shape of the uncanny valley varies significantly between studies \citep{Mathur2016,Langer2018,Mathur2020,Palomaki2018,MacDorman2006,Ho2017}. Finally, these works (with rare exception \citep{McAndrew2016}) do not explore non-image media, such as text. Open questions, such as how to make less-scary text, or how make scarier ghost stories, have also been under-explored.

\subsection{Emotion Detection}
The fear detection model we create is related to previous work on emotion detection. Emotions are fundamental to humans across cultures \citep{Plutchik1982}, and are typically split into eight components: terror (fear), admiration, ecstacy, vigilance, rage, loathing, grief, and amazement. Research on detecting these emotions in text has a long history \citep{Acheampong2020,Chen2022}, but this research recently came to prominence with text embedding-based methods that can accurately detect emotion in sentences. Detection methods have recently exploited advances in Bi-LSTMs and attention for higher accuracy (c.f., \citep{Cai2018,Alhuzali2021}) and have proven useful for chatbots, for example, which are used in a range of applications \citep{Chen2022}. Emotion detection is closely related to sentiment analysis, such as VADER \citep{Gilbert2014}, or the hedonometer, studied by Dodds et al., \citep{Dodds2011,Dodds2016}. Both methods aim to detect the positivity or negativity of words or sentences, and has been used to understand story arcs \citep{Dodds2016} or tweet sentiment \cite{Dodds2011,Gilbert2014}.

\section{Data}

\subsection{Fear Training Data}
We use multiple datasets to train a fear-detection model, where each dataset has sentences labeled as expressing fear or not. The datasets were gathered and converted into a binary classification problem with a label 1 or 0 representing if the sentence does or does not express fear, respectively. The datasets used for modeling are described in Table~\ref{tab:tab1}. This is one of the most complete collections of data to analyze fear in text. Alike to previous research \citep{Bostan2018}, we collect a range of emotion data, but in contrast to that work, some of our data are unique and only available upon request from the authors \citep{Szpakowicz2007}. This diverse dataset is trained with a model we describe in the Metrics section. In total, there are 70K labeled sentences, with roughly 7K of these sentences labeled ``fear.''

\begin{table*}[]
    \centering
    \begin{tabular}{|p{0.4\textwidth}|p{0.5\textwidth}|}\hline
    Dataset	& Description  \\\hline
ISEARs \citep{ISEARS}	& Obtained from cross‐cultural studies in 37 countries and contains sentences annotated for joy, sadness, fear, anger, guilt, disgust and shame emotions \\\hlin
WASSA 2017 \citep{WASSA2017}& 	Constructed from tweets and annotated for joy, sadness, fear, and anger emotions\\\hline
Affect Data \citep{Alm2008}& 	Constructed from Tales and classified into angry, fearful, happy, sad, disgusted and surprised emotions\\\hlin
Emotion Stimulus No Cause Dataset \citep{Ghazi2015}& 	Data developed from FrameNets' annotated data for emotion lexical unit, each sentence is marked with an emotion tag.	\\\hlin
CrowdFlower Twitter Sentiment Analysis Emotion Data \citep{Crowdflower}& 	Constructed from tweets and classified into 13 emotions (sadness, relief, anger, worry, enthusiasm etc.)\\
\hlin
Emotion-Annotated Dataset \citep{Szpakowicz2007}& 	Constructed from blog data sentences classified into happiness, sadness, fear, anger, surprise and disgust. 	\\\hlin
DailyDialog Dataset \citep{Li2017}	& Human-written text sentences tagged with emotions and communication intention\\\hlin
Emotion Hashtag Corpus \citep{Mohammad2015}&	Tweets annotated with emotions based on the emotion-word hashtag in the tweet text \\\hlin
    \end{tabular}
    \caption{Datasets used to construct fear model.}
    \label{tab:tab1}
\end{table*}

\begin{figure*}[tbh!]
    \centering
    \includegraphics[width=\linewidth]{figures/Fig1.pdf}
    \caption{The fear model framework. (a) The neural network used to predict fear in sentences (5,840,850 parameters total). (b) The receiver operative characteristic for the neural network model.}
    \label{fig:fig1}
\end{figure*}
\subsection{Reddit Data}
We extract stories from subreddits using the Python wrapper for the Pushshift API (\url{https://psaw.readthedocs.io}). Stories are collected within two broad genres: scary stories and non-scary stories. For the scary stories, our data comes from the subreddits r/CreepyPasta, r/ShortScaryStories, and r/NoSleep, and for non-scary stories we selected the subreddits r/TIFU, r/Self, r/StoriesAboutKevin, r/Confession, and r/Confessions, which are common story-writing subreddits. All stories are collected from the start of the subreddit until June, 2020. These data are used to train FastText embeddings \citep{joulin2016fasttext}, and to find SSToP scores. After cleaning, described below, there are in total 123K stories.

\subsection{Data cleaning}
To clean data for fear detection, we remove all characters except English alphabets and spaces. This ensures that the fear model’s vocabulary is only English words, and any numbers/HTML markup is removed. Next, we split phrases written in the camel case (a frequent occurrence in the Reddit and Tweet datasets due to hashtags) into its constituent words. (e.g. \#EndThisTyranny split to 'end this tyranny'). Finally, we convert all strings to lowercase and remove all English stopwords (collected from NLTK corpus), to ensure that the model doesn’t falsely learn fear from universally occurring stopwords.

\subsection{Metrics}

\subsubsection{Fear Confidence}
To determine the confidence that a word or sentence expresses fear we train a model whose architecture is described in Fig.~\ref{fig:fig1}a. A Bidirectional GRU (Bi-GRU) is used because it is capable of incorporating contextual information in the forward and reverse direction in contrast to a standard GRU or LSTM. A Global Average Pooling layer was used after the Bi-GRU layer and a dropout layer of 50\% was used to regularize the dense layer just before the two-node prediction layer. A batch size of 64 was used with categorical cross-entropy loss and an Adam optimizer.

To train this model, we split the meta-dataset into 3 parts (where each datapoint is assigned at random): 75\% for training, 10\% for validation and 10\% for testing. The original training dataset contained 55.8K sentences, of which 5.5K were sentences expressing fear. To reduce imbalance, we up-sample the fear sentences to create 100.5K sentences for training. Validation and test sets are separate sets of 7.0K sentences without up-sampling or down-sampling (roughly 700 sentences in each set were labeled \emph{fear}). Tensorflow Keras is used for the tasks of tokenization, sequencing and padding of the three datasets. The tokenizer is only fit on the training data. The vocabulary size was 56.5K. Each sentence is then converted into a sequence and zero-padded to a length of 100. The model ROC curve is shown in Fig.~\ref{fig:fig1}b, which shows high micro- and macro-averaged AUC (0.96 and 0.85, respectively).

We compare this model to logistic regression models  with L1 or L2 regularization. Text is tokenized and fed through FastText \citep{joulin2016fasttext} embeddings trained on the scary and non-scary story corpora. All embedded words in a story are then averaged to create a document embedding. When training the logistic regression models, the training data is down-sampled so that each class is of equal size. The comparisons against the baselines are shown in Table~\ref{tab:baselines}. We see significant improvements over the baseline models.

\begin{table*}[]
    \centering
    \begin{tabular}{|l|c|c|c|}
    \hline
         Model & Accuracy & F1 & ROC-AUC\\
         &                & (Macro Avg) &\\\hline
         {\bf Neural Net} &\textbf{0.92} &\textbf{0.76}&\textbf{0.85}\\
         Logistic (L1) & 0.71&0.60&0.84\\
         Logistic (L2) & 0.74&0.61&0.84\\\hline
         Majority & 0.90 & 0.57&0.5\\\hline
    \end{tabular}
    \caption{Model performance for neural network-based fear model and logistic regression baselines. Bottom row are metrics for majority class null model, in which we guess all test data is not scary (the majority class).}
    \label{tab:baselines}
\end{table*}

\subsubsection{Scary Story Token Prevalence}

SSToP is defined as the odds ratio between a word's frequency in scary and non-scary stories
\begin{equation}\label{eq:eq1}
    c(word) = \frac{f_{scary}(word)}{f_{normal}(word)}
\end{equation}
Where $f_X(word)$ is the word frequency across all posts and subreddits within the genre $X$. To check the robustness of this method, we re-calculate $c(word)$ such that non-scary word frequencies were calculated from each of the non-scary subreddits (creating five separate metrics) and results are qualitatively the same.
\begin{table*}[tbh!]
    \centering
    \begin{tabular}{|l|c||l|c|}
    \hline
\textbf{High SSToP Words} & \textbf{SSToP} &\textbf{Low SSToP Words} & \textbf{SSToP}\\
\textbf{(Common in Scary Stories)} &&\textbf{(Uncommon in Scary Stories)}&\\\hline
    eyeless	& 100&rself&	0.0018\\
scarecrows	& 108&fwb	&0.0021\\
cryptids&	110&superjail&	0.0022\\
skinwalkers&	130&19f	&0.0023\\
headstones&	137&tldr&0.0025\\
    \hline
    \end{tabular}
    \caption{Examples of words with high and low SSToP scores. Skin-walkers, which have a high SSToP score, are a harmful witch in Navajo culture.}
    \label{tab:tab3}
\end{table*}
To calculate this metric for each word, we first select all stories which contain at least 500 words. This helps ensure that the lengths of the stories are approximately uniform and allows us to calculate story modes described later. The stories are preprocessed by tokenizing and removing punctuation. We utilize a dictionary to keep track of the number of times each word occurs. This is calculated for both scary and non-scary stories and Eq.~\ref{eq:eq1} is applied to determine a SSToP value for each word. Since Reddit stories are not checked for correct grammar or spelling, there are several unique names or words which may be misspelt. Because the occurrence of each of these words does not span broadly throughout the entire subreddit, SSToP cannot accurately assign a value to these unique terms. Therefore, we only consider words which have occurred at least 100 times in the entire corpora of scary and non-scary stories.

\subsection{Generating Story Modes}
The main motivation behind creating story modes is to identify patterns writers exploit to make scarier stories. Some stories may, for example, get scary towards the end while other stories may start out scary and end scary, but have a less-scary segment in the middle. Therefore, while we generate a model to detect whether fear is expressed in sentences, it is the pattern of fear, the modes, that we study to better understand how readers might be provoked to experience fear.

To construct these story modes, we first segment each story into ten points based on the percentage of story covered (0\%, 10\%,...,90\%). We then calculate the fear confidence of a sentence located at that point in the story or average the SSToP score for 50 words after that point in the story. After the metrics are sampled, we construct a matrix, $\mathbf{M}$, such that columns represent the 10 sampled points, and rows represent each story.  We then apply singular value decomposition to calculate the story modes \citep{Dodds2016}, such that $\mathbf{M} = \mathbf{V\Sigma U} = \mathbf{WU}$. The matrix $\mathbf{U}$ represents the modes while $\mathbf{W}$ represents the coefficients of each mode used to reconstruct each story, alike to the coefficients of a Fourier transform. The largest element in each row of $\mathbf{W}$ represents the mode that best aligns with each story, but in general several modes are needed to reconstruct a story.

\subsection{Word similarity to human}
To determine how similar a noun is to \emph{human}, we first embed nouns using FastText. Human synonyms, namely human, mortal, person, soul, Homo Sapien, earthling, higher animal, and living person (common synonyms of human that are gender neutral) are averaged together into one \emph{human} vector to avoid noise associated with the embedding of a single word. This follows similar work on gender bias in word embeddings, where the first principle component of a collection of words are used to construct a he-she vector, in order to reduce noise associated with each individual pair of words \citep{Bolukbasi2016}. Next we determine what words in the word embeddings are nouns using Python's TextBlob library (\url{https://textblob.readthedocs.io}). If NN, PN, or NP are in the TextBlog tags for a word, the word is categorized as a noun. This method helps us avoid finding the unrealistic similarity between, e.g., a verb and a noun. Finally, we determine distance between words using Euclidean distance. Other distance metrics, such as Manhattan distance \citep{Aggarwal2001}, show similar results.

\section{Results}

\begin{figure*}[tbh!]
    \centering
    \includegraphics[width=\linewidth]{figures/Fig2.pdf}
    \caption{Scary story statistics. (a) The number of stories each year (inset: the number of stories written each hour in GMT time). (b) LDA topics over time, which shows a significant drop in the house-like topic but an increase in body-related and school-related topics in recent years. (c) The proportion of disease-related stories over time.}
    \label{fig:fig2}
\end{figure*}

We show data statistics in Fig.~\ref{fig:fig2}. This figure demonstrates when writers post their stories and what they discuss. First, Fig.~\ref{fig:fig2}a shows the frequency of stories over time, which rapidly increases to over 20,000 stories a year before dropping slightly. In the inset, we see that users are least likely to post their stories at 12 p.m. GMT, or around 5 a.m. EST, perhaps because most writers might be from America and do not post when they just wake up. Next, we use Latent Derichlet Allocation (with lemmatized words and all stop words removed) to find ten story topics, the largest of which are shown in Fig.~\ref{fig:fig2}b. We notice that the house topic (with words like ``door" or ``window'') drops off in frequency while topics related to bodies (with words like ``bodies" or ``blood'') and school (with words like ``phone'' or ``school'') become increasingly popular. These results suggest long-term trends in what writers consider topical for their stories, possibly because writers focus on different topics as they age or they believe readers find school or body horror more interesting. Finally, we show the frequency of disease-like stories, in which ``lockdown,'' ``infect,'' ``viru,'' or ``diseas'' lemmas are within the story, increase dramatically in 2020 (likely due to COVID-19 being in the news), but this follows a long-term trend, in which disease-like stories have become increasingly popular. We also notice a small peak in their prevalence in mid-2014, when the disease Ebola became topical.

Next, we show in Fig.~\ref{fig:fig3} that a word's SSToP score varies with its similarity to human. Words seen in scary stories tend to be more similar to human, which is reminiscent of the uncanny valley, in which people find semi-human objects more unsettling. A number of plausible reasons for these patterns exist. For example, scary story authors use semi-human words (such as ``devil'' or ``clown'') in an attempt to unsettle readers, or they are discussing human-related topics, or they avoid words that are static and boring, such as cars, which are far from ``human'' in latent embedding space. Whatever the reason, this pattern gives new insights into how writers make scary stories.

\begin{figure}
    \centering
    \includegraphics[width=0.75\linewidth]{figures/Fig3.pdf}
    \caption{Scary story writers use more human-like words. Mean SSToP score (fraction of words in scary stories) in red versus noun similarity to ``human.'' Error bars are standard errors.}
    \label{fig:fig3}
\end{figure}

\begin{figure*}[tbh!]
    \centering
    \includegraphics[width=0.95\linewidth]{figures/Fig4.pdf
    \caption{Story modes in r/NoSleep. (a) 3 lowest story modes for fear (modes are blue lines), (b) 3 lowest story modes for SSToP scores (modes are red lines), and (c) histograms of each story mode for the respective metrics. Gray lines in (a-b) are example stories that best match those respective modes (they have the largest W coefficients for those modes).
    }
    \label{fig:fig4}
\end{figure*}
Finally, we analyze how scary story authors develop story modes. In Fig.~\ref{fig:fig4}, we show story modes of fear confidence and SSToP score in the r/NoSleep subreddit (14K stories in total). Blue lines in Fig.~\ref{fig:fig4}a correspond to the three lowest modes for fear confidences, red lines in Fig.~\ref{fig:fig4}b are the three lowest modes for SSToP scores. Gray lines correspond to 20 stories which have the highest coefficients in the corresponding $\mathbf{W}$ matrix for a given mode. We normalize the story modes by dividing by the largest $\mathbf{W}$ coefficient in each row. These figures show that stories use high SSToP words, such as ``shadow'' or ``creature'' at very particular points in the story, presumably at story climaxes or key scenes. Stories also express fear at particular points in the story as well, presumably to keep the audience thrilled or afraid until the end of the story.

In Fig.~\ref{fig:fig4}c, we show the frequency of the largest mode associated with each story. We see that many stories are in the lowest SSToP mode. Scary story authors therefore tend to use scary words in the center of the story, perhaps to set up scenes. Surprisingly, however, there are a variety of modes used for fear, and a combination of these modes often appear in stories. Furthermore, the fear and SSToP modes rarely align. Namely, the largest SSToP modes for a given story have a low correlation with the top fear modes (Spearman correlation $=0.06$, p-value $<10^{-10}$). Finally mode 9 is rarely the largest mode because it corresponds to a story without any change (the mode is a flat line).

\section{Conclusions}

In conclusion, we analyze text patterns to better understand how writers make scary stories. The results suggest that writers tend to be topical or change the story topic to fit the mood of readers. Moreover, scary story authors tend to use human-like words, which is reminiscent of the uncanny valley in which people find human-like images more unsettling. In addition, authors create stories whose modes may help scare readers. Overall, our work uncovers patterns associated with text that elicits fear, but we believe more work will be needed to understand how these patterns may cause fear to be elicited.

\section{Limitations}
There are a number of limitations in our work. While we uncover patterns associated with scary stories, more work is needed to understand whether or how these patterns create fear in readers. This task will require analyzing reader reactions in a controlled study. In addition, the relationship between nouns and words like ``human'' have not been tested on alternative text embedding models, such as GLoVe \citep{pennington2014glove}, or attention-based embeddings, such as BERT \citep{Devlin2019}. Finally story motifs we uncover should be compared against alternative methods \citep{Dodds2016}.

\section{Ethical Considerations}
All results come from publicly available and anonymized data, therefore the study poses minimal ethical risk.

\section{Acknowledgements}
This project was developed at the USC Center for Knowledge-Powered Interdisciplinary Data Science (CKIDS) DataFest 2020.  We also thank the USC Graduates Rising in Information and Data Science (GRIDS) for their help.  Code to reproduce some of our major results are shown here: https://github.com/KeithBurghardt/Creepypasta.

\section{Introduction}
``The story had held us, round the fire, sufficiently breathless, but except the obvious remark that it was gruesome...I remember no comment uttered till somebody happened to say that it was the only case he had met in which such a visitation had fallen on a child.'' This is the opening line to Henry James's ``The Turning Of The Screw'' \citep{James2008} and summarizes a key and counter-intuitive aspect of scary stories: they can be both revolting and captivating; they capture a fundamental emotion, fear \citep{Adolphs2013}, but in doing so, provide entertainment. The closest analogy might be how spicy foods cause pain yet are tasty. We understand what makes food spicy, and can tailor a meal's spice to fit one's palate, yet it is less clear how to generate fear in a story because we do not know the ingredients that make a story scary. This is a special case of a more general issue, in which we do not yet fully understand how stories elicit particular emotions, i.e., what emotion the reader should feel, in contrast to detecting the emotion a writer expresses \citep{Alhuzali2021,Strapparava2008}

In this paper, begin to understand how stories make readers scared by quantifying patterns in scary stories. First, we analyze the topics associated with scary stories, and find writers are making fewer stories about houses and more stories about human bodies, school, and diseases, potentially to stay topical. We then develop a method to quantify more universal patterns in scary stories by measuring the percentage of times a word appears in scary and non-scary stories, a metric which we call Scary Story Token Prevalence (SSToP). Words with high SSToPs, such as \emph{creature} or \emph{silhouette}, are more likely to be human-like words, suggesting scary story writers intentionally use words that are semi-human. Finally, we analyze where writers use high SSToP words or words expressing fear within a story. We find that stories can be decomposed into modes where the high SSToP or fearful words appear in regular intervals, and combinations of these modes are used to develop scary story patterns. Overall, these results lend insight into how stories express fear, and patterns writers exploit to make scary stories.

Our contributions can be summarized as follows:
\begin{itemize}
    \item we analyze dynamic patterns of scary stories to understand what themes have become popular or fell out of favor.
    \item we analyze static patterns, such as the relationship between scary story nouns like ``human'' to capture what words writers use and why they might use those words
    \item we capture how scary stories are written by quantifying the common scary story modes. We find some modes are particularly common, which offers clues about how writers make a scary story.
\end{itemize}

\section{Related Work}

\subsection{Uncanny Valley}
What makes something scary is most similar to previous work on the uncanny valley effect. Research on the uncanny valley began with Jentsch and Freud who coined the term \emph{unheimlich} (literally, ``unhomely'') when referencing human uncanniness and eeriness \citep{Freud1909,Jentsch1906}. The uncanny valley also came into prominence among human-computer interaction (HCI) and human-robot interaction (HRI) researchers with a paper by Mori (\citeyear{MoriUncannValley}). Researchers were inspired by Mori to learn what can make a robot unsettling \citep{Broadbent2017} because willingness to work with robots can depend on their likability \citep{Destephe2015}. An objective definition of uncanny (what makes something human-like) or valley (what is and is not unsettling) is still, however, a fiercely debated topic \citep{Mathur2016,Langer2018,Mathur2020,Palomaki2018,MacDorman2006,Ho2017}. Moreover, the qualitative shape of the uncanny valley varies significantly between studies \citep{Mathur2016,Langer2018,Mathur2020,Palomaki2018,MacDorman2006,Ho2017}. Finally, these works (with rare exception \citep{McAndrew2016}) do not explore non-image media, such as text. Open questions, such as how to make less-scary text, or how make scarier ghost stories, have also been under-explored.

\subsection{Emotion Detection}
The fear detection model we create is related to previous work on emotion detection. Emotions are fundamental to humans across cultures \citep{Plutchik1982}, and are typically split into eight components: terror (fear), admiration, ecstacy, vigilance, rage, loathing, grief, and amazement. Research on detecting these emotions in text has a long history \citep{Acheampong2020,Chen2022}, but this research recently came to prominence with text embedding-based methods that can accurately detect emotion in sentences. Detection methods have recently exploited advances in Bi-LSTMs and attention for higher accuracy (c.f., \citep{Cai2018,Alhuzali2021}) and have proven useful for chatbots, for example, which are used in a range of applications \citep{Chen2022}. Emotion detection is closely related to sentiment analysis, such as VADER \citep{Gilbert2014}, or the hedonometer, studied by Dodds et al., \citep{Dodds2011,Dodds2016}. Both methods aim to detect the positivity or negativity of words or sentences, and has been used to understand story arcs \citep{Dodds2016} or tweet sentiment \cite{Dodds2011,Gilbert2014}.

\section{Data}

\subsection{Fear Training Data}
We use multiple datasets to train a fear-detection model, where each dataset has sentences labeled as expressing fear or not. The datasets were gathered and converted into a binary classification problem with a label 1 or 0 representing if the sentence does or does not express fear, respectively. The datasets used for modeling are described in Table~\ref{tab:tab1}. This is one of the most complete collections of data to analyze fear in text. Alike to previous research \citep{Bostan2018}, we collect a range of emotion data, but in contrast to that work, some of our data are unique and only available upon request from the authors \citep{Szpakowicz2007}. This diverse dataset is trained with a model we describe in the Metrics section. In total, there are 70K labeled sentences, with roughly 7K of these sentences labeled ``fear.''

\begin{table*}[]
    \centering
    \begin{tabular}{|p{0.4\textwidth}|p{0.5\textwidth}|}\hline
    Dataset	& Description  \\\hline
ISEARs \citep{ISEARS}	& Obtained from cross‐cultural studies in 37 countries and contains sentences annotated for joy, sadness, fear, anger, guilt, disgust and shame emotions \\\hlin
WASSA 2017 \citep{WASSA2017}& 	Constructed from tweets and annotated for joy, sadness, fear, and anger emotions\\\hline
Affect Data \citep{Alm2008}& 	Constructed from Tales and classified into angry, fearful, happy, sad, disgusted and surprised emotions\\\hlin
Emotion Stimulus No Cause Dataset \citep{Ghazi2015}& 	Data developed from FrameNets' annotated data for emotion lexical unit, each sentence is marked with an emotion tag.	\\\hlin
CrowdFlower Twitter Sentiment Analysis Emotion Data \citep{Crowdflower}& 	Constructed from tweets and classified into 13 emotions (sadness, relief, anger, worry, enthusiasm etc.)\\
\hlin
Emotion-Annotated Dataset \citep{Szpakowicz2007}& 	Constructed from blog data sentences classified into happiness, sadness, fear, anger, surprise and disgust. 	\\\hlin
DailyDialog Dataset \citep{Li2017}	& Human-written text sentences tagged with emotions and communication intention\\\hlin
Emotion Hashtag Corpus \citep{Mohammad2015}&	Tweets annotated with emotions based on the emotion-word hashtag in the tweet text \\\hlin
    \end{tabular}
    \caption{Datasets used to construct fear model.}
    \label{tab:tab1}
\end{table*}

\begin{figure*}[tbh!]
    \centering
    \includegraphics[width=\linewidth]{figures/Fig1.pdf}
    \caption{The fear model framework. (a) The neural network used to predict fear in sentences (5,840,850 parameters total). (b) The receiver operative characteristic for the neural network model.}
    \label{fig:fig1}
\end{figure*}
\subsection{Reddit Data}
We extract stories from subreddits using the Python wrapper for the Pushshift API (\url{https://psaw.readthedocs.io}). Stories are collected within two broad genres: scary stories and non-scary stories. For the scary stories, our data comes from the subreddits r/CreepyPasta, r/ShortScaryStories, and r/NoSleep, and for non-scary stories we selected the subreddits r/TIFU, r/Self, r/StoriesAboutKevin, r/Confession, and r/Confessions, which are common story-writing subreddits. All stories are collected from the start of the subreddit until June, 2020. These data are used to train FastText embeddings \citep{joulin2016fasttext}, and to find SSToP scores. After cleaning, described below, there are in total 123K stories.

\subsection{Data cleaning}
To clean data for fear detection, we remove all characters except English alphabets and spaces. This ensures that the fear model’s vocabulary is only English words, and any numbers/HTML markup is removed. Next, we split phrases written in the camel case (a frequent occurrence in the Reddit and Tweet datasets due to hashtags) into its constituent words. (e.g. \#EndThisTyranny split to 'end this tyranny'). Finally, we convert all strings to lowercase and remove all English stopwords (collected from NLTK corpus), to ensure that the model doesn’t falsely learn fear from universally occurring stopwords.

\subsection{Metrics}

\subsubsection{Fear Confidence}
To determine the confidence that a word or sentence expresses fear we train a model whose architecture is described in Fig.~\ref{fig:fig1}a. A Bidirectional GRU (Bi-GRU) is used because it is capable of incorporating contextual information in the forward and reverse direction in contrast to a standard GRU or LSTM. A Global Average Pooling layer was used after the Bi-GRU layer and a dropout layer of 50\% was used to regularize the dense layer just before the two-node prediction layer. A batch size of 64 was used with categorical cross-entropy loss and an Adam optimizer.

To train this model, we split the meta-dataset into 3 parts (where each datapoint is assigned at random): 75\% for training, 10\% for validation and 10\% for testing. The original training dataset contained 55.8K sentences, of which 5.5K were sentences expressing fear. To reduce imbalance, we up-sample the fear sentences to create 100.5K sentences for training. Validation and test sets are separate sets of 7.0K sentences without up-sampling or down-sampling (roughly 700 sentences in each set were labeled \emph{fear}). Tensorflow Keras is used for the tasks of tokenization, sequencing and padding of the three datasets. The tokenizer is only fit on the training data. The vocabulary size was 56.5K. Each sentence is then converted into a sequence and zero-padded to a length of 100. The model ROC curve is shown in Fig.~\ref{fig:fig1}b, which shows high micro- and macro-averaged AUC (0.96 and 0.85, respectively).

We compare this model to logistic regression models  with L1 or L2 regularization. Text is tokenized and fed through FastText \citep{joulin2016fasttext} embeddings trained on the scary and non-scary story corpora. All embedded words in a story are then averaged to create a document embedding. When training the logistic regression models, the training data is down-sampled so that each class is of equal size. The comparisons against the baselines are shown in Table~\ref{tab:baselines}. We see significant improvements over the baseline models.

\begin{table*}[]
    \centering
    \begin{tabular}{|l|c|c|c|}
    \hline
         Model & Accuracy & F1 & ROC-AUC\\
         &                & (Macro Avg) &\\\hline
         {\bf Neural Net} &\textbf{0.92} &\textbf{0.76}&\textbf{0.85}\\
         Logistic (L1) & 0.71&0.60&0.84\\
         Logistic (L2) & 0.74&0.61&0.84\\\hline
         Majority & 0.90 & 0.57&0.5\\\hline
    \end{tabular}
    \caption{Model performance for neural network-based fear model and logistic regression baselines. Bottom row are metrics for majority class null model, in which we guess all test data is not scary (the majority class).}
    \label{tab:baselines}
\end{table*}

\subsubsection{Scary Story Token Prevalence}

SSToP is defined as the odds ratio between a word's frequency in scary and non-scary stories
\begin{equation}\label{eq:eq1}
    c(word) = \frac{f_{scary}(word)}{f_{normal}(word)}
\end{equation}
Where $f_X(word)$ is the word frequency across all posts and subreddits within the genre $X$. To check the robustness of this method, we re-calculate $c(word)$ such that non-scary word frequencies were calculated from each of the non-scary subreddits (creating five separate metrics) and results are qualitatively the same.
\begin{table*}[tbh!]
    \centering
    \begin{tabular}{|l|c||l|c|}
    \hline
\textbf{High SSToP Words} & \textbf{SSToP} &\textbf{Low SSToP Words} & \textbf{SSToP}\\
\textbf{(Common in Scary Stories)} &&\textbf{(Uncommon in Scary Stories)}&\\\hline
    eyeless	& 100&rself&	0.0018\\
scarecrows	& 108&fwb	&0.0021\\
cryptids&	110&superjail&	0.0022\\
skinwalkers&	130&19f	&0.0023\\
headstones&	137&tldr&0.0025\\
    \hline
    \end{tabular}
    \caption{Examples of words with high and low SSToP scores. Skin-walkers, which have a high SSToP score, are a harmful witch in Navajo culture.}
    \label{tab:tab3}
\end{table*}
To calculate this metric for each word, we first select all stories which contain at least 500 words. This helps ensure that the lengths of the stories are approximately uniform and allows us to calculate story modes described later. The stories are preprocessed by tokenizing and removing punctuation. We utilize a dictionary to keep track of the number of times each word occurs. This is calculated for both scary and non-scary stories and Eq.~\ref{eq:eq1} is applied to determine a SSToP value for each word. Since Reddit stories are not checked for correct grammar or spelling, there are several unique names or words which may be misspelt. Because the occurrence of each of these words does not span broadly throughout the entire subreddit, SSToP cannot accurately assign a value to these unique terms. Therefore, we only consider words which have occurred at least 100 times in the entire corpora of scary and non-scary stories.

\subsection{Generating Story Modes}
The main motivation behind creating story modes is to identify patterns writers exploit to make scarier stories. Some stories may, for example, get scary towards the end while other stories may start out scary and end scary, but have a less-scary segment in the middle. Therefore, while we generate a model to detect whether fear is expressed in sentences, it is the pattern of fear, the modes, that we study to better understand how readers might be provoked to experience fear.

To construct these story modes, we first segment each story into ten points based on the percentage of story covered (0\%, 10\%,...,90\%). We then calculate the fear confidence of a sentence located at that point in the story or average the SSToP score for 50 words after that point in the story. After the metrics are sampled, we construct a matrix, $\mathbf{M}$, such that columns represent the 10 sampled points, and rows represent each story.  We then apply singular value decomposition to calculate the story modes \citep{Dodds2016}, such that $\mathbf{M} = \mathbf{V\Sigma U} = \mathbf{WU}$. The matrix $\mathbf{U}$ represents the modes while $\mathbf{W}$ represents the coefficients of each mode used to reconstruct each story, alike to the coefficients of a Fourier transform. The largest element in each row of $\mathbf{W}$ represents the mode that best aligns with each story, but in general several modes are needed to reconstruct a story.

\subsection{Word similarity to human}
To determine how similar a noun is to \emph{human}, we first embed nouns using FastText. Human synonyms, namely human, mortal, person, soul, Homo Sapien, earthling, higher animal, and living person (common synonyms of human that are gender neutral) are averaged together into one \emph{human} vector to avoid noise associated with the embedding of a single word. This follows similar work on gender bias in word embeddings, where the first principle component of a collection of words are used to construct a he-she vector, in order to reduce noise associated with each individual pair of words \citep{Bolukbasi2016}. Next we determine what words in the word embeddings are nouns using Python's TextBlob library (\url{https://textblob.readthedocs.io}). If NN, PN, or NP are in the TextBlog tags for a word, the word is categorized as a noun. This method helps us avoid finding the unrealistic similarity between, e.g., a verb and a noun. Finally, we determine distance between words using Euclidean distance. Other distance metrics, such as Manhattan distance \citep{Aggarwal2001}, show similar results.

\section{Results}

\begin{figure*}[tbh!]
    \centering
    \includegraphics[width=\linewidth]{figures/Fig2.pdf}
    \caption{Scary story statistics. (a) The number of stories each year (inset: the number of stories written each hour in GMT time). (b) LDA topics over time, which shows a significant drop in the house-like topic but an increase in body-related and school-related topics in recent years. (c) The proportion of disease-related stories over time.}
    \label{fig:fig2}
\end{figure*}

We show data statistics in Fig.~\ref{fig:fig2}. This figure demonstrates when writers post their stories and what they discuss. First, Fig.~\ref{fig:fig2}a shows the frequency of stories over time, which rapidly increases to over 20,000 stories a year before dropping slightly. In the inset, we see that users are least likely to post their stories at 12 p.m. GMT, or around 5 a.m. EST, perhaps because most writers might be from America and do not post when they just wake up. Next, we use Latent Derichlet Allocation (with lemmatized words and all stop words removed) to find ten story topics, the largest of which are shown in Fig.~\ref{fig:fig2}b. We notice that the house topic (with words like ``door" or ``window'') drops off in frequency while topics related to bodies (with words like ``bodies" or ``blood'') and school (with words like ``phone'' or ``school'') become increasingly popular. These results suggest long-term trends in what writers consider topical for their stories, possibly because writers focus on different topics as they age or they believe readers find school or body horror more interesting. Finally, we show the frequency of disease-like stories, in which ``lockdown,'' ``infect,'' ``viru,'' or ``diseas'' lemmas are within the story, increase dramatically in 2020 (likely due to COVID-19 being in the news), but this follows a long-term trend, in which disease-like stories have become increasingly popular. We also notice a small peak in their prevalence in mid-2014, when the disease Ebola became topical.

Next, we show in Fig.~\ref{fig:fig3} that a word's SSToP score varies with its similarity to human. Words seen in scary stories tend to be more similar to human, which is reminiscent of the uncanny valley, in which people find semi-human objects more unsettling. A number of plausible reasons for these patterns exist. For example, scary story authors use semi-human words (such as ``devil'' or ``clown'') in an attempt to unsettle readers, or they are discussing human-related topics, or they avoid words that are static and boring, such as cars, which are far from ``human'' in latent embedding space. Whatever the reason, this pattern gives new insights into how writers make scary stories.

\begin{figure}
    \centering
    \includegraphics[width=0.75\linewidth]{figures/Fig3.pdf}
    \caption{Scary story writers use more human-like words. Mean SSToP score (fraction of words in scary stories) in red versus noun similarity to ``human.'' Error bars are standard errors.}
    \label{fig:fig3}
\end{figure}

\begin{figure*}[tbh!]
    \centering
    \includegraphics[width=0.95\linewidth]{figures/Fig4.pdf
    \caption{Story modes in r/NoSleep. (a) 3 lowest story modes for fear (modes are blue lines), (b) 3 lowest story modes for SSToP scores (modes are red lines), and (c) histograms of each story mode for the respective metrics. Gray lines in (a-b) are example stories that best match those respective modes (they have the largest W coefficients for those modes).
    }
    \label{fig:fig4}
\end{figure*}
Finally, we analyze how scary story authors develop story modes. In Fig.~\ref{fig:fig4}, we show story modes of fear confidence and SSToP score in the r/NoSleep subreddit (14K stories in total). Blue lines in Fig.~\ref{fig:fig4}a correspond to the three lowest modes for fear confidences, red lines in Fig.~\ref{fig:fig4}b are the three lowest modes for SSToP scores. Gray lines correspond to 20 stories which have the highest coefficients in the corresponding $\mathbf{W}$ matrix for a given mode. We normalize the story modes by dividing by the largest $\mathbf{W}$ coefficient in each row. These figures show that stories use high SSToP words, such as ``shadow'' or ``creature'' at very particular points in the story, presumably at story climaxes or key scenes. Stories also express fear at particular points in the story as well, presumably to keep the audience thrilled or afraid until the end of the story.

In Fig.~\ref{fig:fig4}c, we show the frequency of the largest mode associated with each story. We see that many stories are in the lowest SSToP mode. Scary story authors therefore tend to use scary words in the center of the story, perhaps to set up scenes. Surprisingly, however, there are a variety of modes used for fear, and a combination of these modes often appear in stories. Furthermore, the fear and SSToP modes rarely align. Namely, the largest SSToP modes for a given story have a low correlation with the top fear modes (Spearman correlation $=0.06$, p-value $<10^{-10}$). Finally mode 9 is rarely the largest mode because it corresponds to a story without any change (the mode is a flat line).

\section{Conclusions}

In conclusion, we analyze text patterns to better understand how writers make scary stories. The results suggest that writers tend to be topical or change the story topic to fit the mood of readers. Moreover, scary story authors tend to use human-like words, which is reminiscent of the uncanny valley in which people find human-like images more unsettling. In addition, authors create stories whose modes may help scare readers. Overall, our work uncovers patterns associated with text that elicits fear, but we believe more work will be needed to understand how these patterns may cause fear to be elicited.

\section{Limitations}
There are a number of limitations in our work. While we uncover patterns associated with scary stories, more work is needed to understand whether or how these patterns create fear in readers. This task will require analyzing reader reactions in a controlled study. In addition, the relationship between nouns and words like ``human'' have not been tested on alternative text embedding models, such as GLoVe \citep{pennington2014glove}, or attention-based embeddings, such as BERT \citep{Devlin2019}. Finally story motifs we uncover should be compared against alternative methods \citep{Dodds2016}.

\section{Ethical Considerations}
All results come from publicly available and anonymized data, therefore the study poses minimal ethical risk.

\section{Acknowledgements}
This project was developed at the USC Center for Knowledge-Powered Interdisciplinary Data Science (CKIDS) DataFest 2020.  We also thank the USC Graduates Rising in Information and Data Science (GRIDS) for their help.  Code to reproduce some of our major results are shown here: https://github.com/KeithBurghardt/Creepypasta.


\section{Introduction}

The recent success of neural networks in a range of tasks connected with logical inference in natural language is remarkable. Foremost among such systems are those employing transformer-based language models \cite{Vaswani2017}  optimised on large corpora in an unsupervised manner \cite{Devlin2018} and then further fine-tuned on task-specific datasets \cite{Bowman2015,rajpurkar2016squad}.
\ignore{Superficially, the performance of these systems is remarkable.}
However, concerns  persist regarding so-called ``data-set artefacts''~\cite{gururangan2018annotation,Schlegel2020a,Schlegel2020}. Have netural networks really acquired the principles of reasoning with natural language, or are they merely responding to superficial patterns in the data?

\ignore{Applications of neural networks to inference in formal languages typically employ different architectures---for example graph neural networks encoding logical syntax such as NeuroSAT~\cite{nnFrag:slblmd18} or collections of sampled possible worlds as in PossibleWorldNet~\cite{ nnFrag:esakg18}---or alternatively proceed more obliquely, using neural networks to select inference rules or proof strategies~\cite{nnFrag:kcs17,nnFragrlbs20,nnFrag:ps20,nnFrag:hrwap21}.}

\begin{figure}[!t]
    \centering
    \resizebox{1.02\columnwidth}{!} {
    \input{figure}
    }
    \resizebox{1\columnwidth}{!}{
    \input{figure2}
    }

    \caption{Depiction of our approach to evaluate reasoning capabilities in neural networks.}
    \label{fig:summary}
\end{figure}

\ignore{
There are reasons to be cautious. One recent line of research in natural language inference reveals that
crowd-sourced datasets are prone to so-called ``data-set artefacts''~\cite{gururangan2018annotation,Schlegel2020a}.
For instance, {\em shorter} hypotheses are more likely to be entailed by their respective premises than are longer ones. The fact that models learn to rely on combinations of such clues casts further doubt on whether their seemingly impressive performance is really  evidence of their ability to reason with language.
Indeed, data sets used to train systems for performing inference in formal languages may be prone to broadly similar difficulties.
Notwithstanding the success of the NeuroSAT system in solving the satisfiability problem for propositional clause sets,
even its authors suggest the detection of \textit{unsatisfiability} by neural networks appears to depend on the existence of
small, \textit{unsatisfiable cores} in the training and test sets ({\em op.~cit.~p.~8}). Put bluntly,
the problems the network is given, though large, may nevertheless be, in a well-defined sense, \textit{easy}. (Similar remarks  apply to
other applications of neural networks to hard combinatorially problems such as, for instance, graph-colourability~\cite{nnFrag:lpal19}.)
Such considerations suggest that the performance of neural networks on inference problems, both in natural and formal languages, may be based on capacities orthogonal to the grasp of any logical principle or generally applicable rule. }

\ignore{
There are reasons to be cautious. One recent line of research in natural language inference reveals that
crowd-sourced datasets are prone to so-called ``data-set artefacts''~\cite{gururangan2018annotation,Schlegel2020a}.}

In fact, two strands of research may be discerned in recent work on natural language inference (NLI). The first formulates the central task as follows: given a pair of sentences in some natural language, a {\em premise}, $P$ and a {\em hypothesis}, $H$, determine whether
$P$ (i)  \textit{entails} or (ii) \textit{contradicts} (i.e.~entails the negation of) $H$; or (iii) $P$ is {\em neutral} with respect to $H$.
For example, the premise
\textit{A person rides his bicycle in the sand beside the ocean} is taken to entail the hypothesis \textit{A person is on a beach}. The primary issue is the possibility of learning such a mapping on the basis of some data set consisting of many such sentence pairs, each  tagged with the a `correct' (i.e.~gold standard) label as determined by human judgement, typically obtained by crowd-sourcing.
Examples include the RTE dataset~\cite{nnFrag:BDDGM09} and the (much larger) SNLI and MNLI datasets~\cite{Bowman2015,Williams2018}.
Neural-network models achieve impressive accuracy on this task \cite{Chen2017EnhancedInference,Devlin2018}.
The nature of the challenge here is (deliberately)  mixed:
on the one hand, solving the NLI problem requires a grasp of the meaning
of various closed-class words  ({\em a}, {\em not}, \dots)
together with an appreciation of the semantics of the grammatical constructions involved. On the other hand, almost all the entailments or contradictions encountered rely on common sense knowledge (for example, that racing a bicycle involves riding it), which it is the job of the system to acquire. The supposition is that these pieces of commonsense knowledge mediate the entailment of the hypothesis (or its negation)
from the premise. The logical basis of the inferences, so reconstructed, is typically straightforward,
amounting to simple syllogism-like inferences; but the mediating commonsense knowledge is coded in `soft' form, matching the approximate, probabilistic nature of natural language inference.  The operative notion of inference
thus eludes a formal
definition~\cite{Sugawara2018}
ultimately resulting in debatable labels \cite{Schlegel2020}

Th
second strand of research investigates the ability of neural networks to recognize formally valid entailments {\em in sensu stricto}, but nevertheless couched in fragments of natural language. Examples include~\newcite{Salvatore2019,Richardson2019a, nnFrag:rs21} and \newcite{Talmor2020}. Here the focus is on  learning the (potentially complex) inferential patterns inherent in the logical syntax of the closed-class words and grammatical constructions defining the fragment of language under investigation.
For example, the premises
\textit{Every doctor who is not a philosopher is a baker}, {\em John is a doctor} and {\em John is not a baker}
entail the hypothesis \textit{John is a philosopher}.
No commonsense knowledge is required here: the given premises either entail the given hypothesis formally, or they do not. Since entailment in a formally defined fragment of language is a matter of mathematical fact,
not human judgement, inferential problems may be constructed artificially, using random sampling over a grammar, with the correct answers determined by an automated theorem prover (ATP). The question is not whether neural networks can be trained to mimic human annotators' judgements, but rather, whether they can learn the logical principles governing language in question. Note that, because it is formal validity rather than commonsense plausibility that is at issue here, inference tasks of interest typically involve not a \textit{single} premise $P$,
but rather, a \textit{collection} of premises.
Individual sentences seldom yield any non-trivial formal entailments.

\ignore{Closer analysis of some widely-used NLI datasets reveals three striking
features of the challenge posed.
Thus, to perform well on this NLI task, a system has to solve two quite different sorts of problem: (i) understanding basic logical syntax, and (ii) inducing meaning postulates.

The reliance on implicit meaning postulates explains the second striking feature of the NLI

Yet, from a logical point of view,  when sentences are short
the problem of recognising entailments becomes interesting only when those entailments depend on multiple, interacting premises. Here, of course,
the induced meaning postulates supply the additional (implicit) premises that render the entailments informative. Yet,
many of the entailments encountered appear to involve little more than syllogism-like inferences.
}

These two strands of research reflect a difference in motivation. The former aims to understand inferences apparently performed by humans in everyday linguistic settings---inferences which are necessarily messy and approximate in character.
From a formal point of view, many of the alleged entailments or contradictions
are in fact judgements of \textit{probability}. Thus, for example the premise {\em Alice is holding a dog} does not, logically speaking, contradict the hypothesis {\em Alice is holding a cat}, even assuming that no dog is a cat; yet such labellings abound in NLI datasets, reflecting the judgements made by (and instructions given to) the human annotators who generate them.
\ignore{Human annotators have a notoriously weak grasp of the concept of logico-syntactic entailment familiar---for better or for worse---to most logicians, as evidenced by inherent disagreements between different annotators of gold labels \cite{Pavlick2019}, ultimately resulting in data that can be factually wrong \cite{Schlegel2020}.
Whatever the practical value of teaching a neural network to mimic these judgements, its scientific value must be open to question.}
By contrast, the second (strictly logical) strand of research is motivated principally by a desire to understand the rule-based character of natural language syntax and semantics, and in particular, by the question of whether a neural network can learn the rules in question.

In this paper, we report on
a large-scale empirical study to investigate whether transformer-based language models can learn the logical syntax of natural language. Specifically, we consider performance on
the problem of determining the satisfiability (logical consistency)
of sets of English sentences featuring
the
determiners
{\em every}, {\em some}, {\em no}, the negative adverb {\em not},
and relative clauses,
in the context of a vocabulary of
count nouns and
 transitive verbs.
 Importantly, the sentences in question are drawn from various different \textit{fragments} of English, each characterized by a particular range of the grammatical constructions investigated.
In each case,
data sets---both for training and evaluation---are artificially generated
in order to test the system's grasp of the underlying logic. Figure~\ref{fig:summary} illustrates the approach, giving an example problem instance for the very simplest of the fragments considered.
We find that
state-of-the-art deep learning-based approaches achieve impressive performance on this task. However, in-depth analysis of their generalisation capabilities reveals a more nuanced pattern, suggesting a tendency to overfit to the parameters that control the data generation, rather than learning the underlying logical principles.

\section{Fragments of Language}

By a {\em fragment} of a natural language, we understand a collection of sentences forming a naturally delineated subset of that language, and equipped with a truth-conditional semantics commanding the assent of its native speakers.
For example, consider the fragment of natural language corresponding to the {\em classical syllogistic} given to us by~\citet[Book A]{nnFrag:aristotlePA}.
In its English-language version, it  consists of the sentence forms
\begin{center}
	\begin{minipage}{10cm}
		\begin{tabbing}
			\small Every $p$ is a $q$ \hspace{2cm} \=
			\small No $p$ is a $q$ \\
			\small Some $p$ is a $q$               \>
			\small Some $p$ is not a $q$,
		\end{tabbing}
	\end{minipage}
\end{center}
with schematic variables $p$ and $q$ substituted by common (count) nouns.
This fragment, which we here denote \sS, can be used to formulate examples such as the one shown in Figure~\ref{fig:summary}.

For present purposes, we may consider the truth conditions of an English sentence to be given by translation to a formal language such as first-order logic, in a way which uncontroversially reconstructs the operative notion of logical entailment. Thus, for example, the sentence forms \sS{}  correspond to the respective logical forms
$\forall x(p(x) \rightarrow \pm q(x))$ and $\exists x(p(x) \wedge \pm q(x))$, where $\pm$ indicates either the presence or absence of negation ($\neg$). An argument in \sS{} is regarded as valid precisely when the first-order translations of its premises entail---in the familiar logical sense---the first-order translation of its conclusion.

Consider now the argument:
\begin{equation}
\text{\begin{minipage}{6cm} \small
\textit{Some artist hates no beekeeper};  \textit{every beekeeper hates some artist}; \textit{therefore some artist is not a beekeeper}.
\end{minipage}}
\label{eq:arg1}
\end{equation}
This argument is again intuitively valid
(though this takes a little thought to see). On the other hand,
it cannot be sensibly cast in the
syllogistic, because it
so obviously
hinges on intrinsically relational information.
(Observe the alternation of subject and object of the verb {\em hates} in the two premises.) Is there, then, a larger fragment of English in which it might be expressed? Take
the {\em relational syllogistic}, denoted \sR, to be the fragment of English obtained by adding to \sS{} the sentence-forms:
\begin{center}
	\begin{minipage}{10cm}
		\begin{tabbing}
			\small Every $p$ $r$s every/some $q$ \hspace{0.25cm} \=
			\small Some $p$ $r$s every/some $q$\\
			\small No $p$ $r$s every/any $q$ \>
			\small Some $p$ does not $r$ every/any $q$,
		\end{tabbing}
	\end{minipage}
\end{center}
where $p$ and $q$ are common count nouns and $r$ a transitive verb.
As with \sS{}, so too with \sR{}: the truth-conditions of sentences
can be captured by translation to first-order logic in a way which faithfully reconstructs the intuitive notion of validity.
For example, ``Some artist hates no beekeeper'' may be rendered as $\exists x(\mbox{artist}(x) \wedge \forall y (\mbox{beekeeper}(y)
\rightarrow \neg \mbox{hate}(x,y)))$, and so on.
Under these semantics, argument \eqref{eq:arg1} is confirmed as a valid argument in the fragment \sR.

There are other ways to extend the fragment \sS, of course.
One (very modest) such extension is actually
featured in the works of~\citet[Ch.~10]{nnFrag:aristotleCdI}. Let us say that the {\em extended classical syllogistic}, denoted \sSd, is the fragment of English which adds to \sS{} the sentence-forms
\begin{center}
	\begin{minipage}{10cm}
		\begin{tabbing}
			\small Every non-$p$ is a $q$ \hspace{1cm} \=
			\small Some non-$p$ is a $q$\\
			\small No non-$p$ is a $q$                 \>
			\small Some non-$p$ is not a $q$,
		\end{tabbing}
	\end{minipage}
\end{center}
corresponding to the first-order formulas
$\forall x(\neg p(x) \rightarrow \pm q(x))$ and $\exists x(\neg p(x) \wedge \pm q(x))$. As we might say, \sSd{} adds `noun-level negation' to \sS.
Following in the same vein, we can extend \sR{} with noun-level negation, yielding sentences such as
\emph{``No non-carpenter admires any non-artist''}
and so on. We call this fourth fragment the {\em extended relational syllogistic}, denoted \sRd. Again, translation into first-order logic is completely standard.

Let $\cL$ be a fragment of some natural language. A set of \cL-sentences is said to be \textit{satisfiable} if there is a structure making the logical translations of these sentences true. The \textit{satisfiability problem} for $\cL$, denoted $\ensuremath{\mbox{\rm Sat}}(\cL)$, is the problem of determining whether a given finite set of sentences of $\cL$ is satisfiable. Provided $\cL$ is equipped with a mechanism for sentence negation (as are all the fragments considered here), any procedure for solving $\ensuremath{\mbox{\rm Sat}}(\cL)$ immediately yields a procedure for recognizing logical entailments in $\cL$, since an argument is valid just in case its premises together with the negation of its conclusion is not satisfiable.
Therefore, we have no use for the familiar classification of
natural language inference problems as {\em entailment}, {\em contradiction} and {\em neutral} (and still less the four-way classification of~\citet{nnFrag:tlcxhj21}): the satisfiability problem is as general as we need. As the fragment $\cL$ becomes more expressive, the
corresponding satisfiability problem $\ensuremath{\mbox{\rm Sat}}(\cL)$ will, in general, become
more increasingly difficult. However, as we shall see, the details of the resulting trade-off between expressiveness and ease of inference are rather intricate. The focus of the present paper is whether neural networks can learn to solve problems such as $\ensuremath{\mbox{\rm Sat}}(\cL)$ for various fragments $\cL$
such as \sS{}, \sSd{}, \sR{} and \sRd{}.

We remark that the approach taken here is parallel to that taken with respect to the fragments GRL and RCL in~\cite{nnFrag:rs21}.
There are two notable differences, however, Firstly, the fragments considered here are, from a grammatical point of view, more basic, and less clearly a natural language version of propositional logic clauses.
In particular, GRL includes the `sentence' \textit{If carrot and not steak then apples}; and even the more natural RCL is limited to the constructions \textit{Every $X$ who is (not) a $Y$ is (not) a $Z$}.
To allow comparison between this work and the present study
we consider the minimal extension of \sS{} by means of \textit{relative clauses}, thus allowing the additional sentence-forms
\begin{center}
	\begin{minipage}{10cm}
		\begin{tabbing}
		\small
			Every $o$ who is a $p$ is a $q$ \hspace{.5cm} \= \small No $o$ who is a $p$ is a $q$  \\
		\small	Some $o$ who is a $p$ is a $q$               \> \small Some $o$ who is a $p$ is not a $q$
		\end{tabbing}
	\end{minipage}
\end{center}
Denote this fragment by \sSrel. Similarly, denote by \sSrelN{} the same fragment additionally allowing negative relative clauses, such as ``Every $o$ who is not a $p$ is a $q$'' and so on. The fragment
\sSrelN{} is actually an extension of RCL.

An important motivation for the rather more general approach taken here is that
the satisfiability problem $\ensuremath{\mbox{\rm Sat}}(\cL)$ for various fragments $\cL$ of English may be studied from a purely complexity-theoretic point of view. Thus, for example, it is known that the problems $\ensuremath{\mbox{\rm Sat}}(\sS)$, $\ensuremath{\mbox{\rm Sat}}(\sSd)$ and $\ensuremath{\mbox{\rm Sat}}(\sR)$ are \textsc{NLogSpace}-complete, while $\ensuremath{\mbox{\rm Sat}}(\sRd)$ is \textsc{ExpTime}-complete \cite{nnFrag:p-hm09}.
Similarly, the satisfiability
problems for GRL and RCL are easily seen to be \textsc{NPTime}-complete, as is the problem
$\ensuremath{\mbox{\rm Sat}}(\sSrelN)$; by contrast, the problem
$\ensuremath{\mbox{\rm Sat}}(\sSrel)$
is \textsc{PTime}-complete~\cite[Theorem 7]{nnFrag:ph14}.
The question naturally arises as to whether the ability of neural networks to learn to solve these various satisfiability problems correlates with these complexity-theoretic differences.

\begin{table*}[t]
    \centering
    \begin{tabularx}{1\textwidth}{p{.05\textwidth}XX}
         \textbf{Frag.} & \textbf{Templates} & \textbf{Example sentence} \\
         \hline
         \multirow{2}{*}{\sSd} & Every/No (non-)$p$ is a $q$. & Every artist is a beekeeper. \\
          & Some (non-)$p$ is (not) a $q$. & Some carpenter is not a dentist. \\
         \hdashline
         \multirow{4}{*}{\sR} & \emph{all of \sS{} and:} & \\
          & Every/Some $p$ $r$s every/some $q$. & Every artist chases some beekeeper. \\
          & Some $p$ does not $r$ every/any $q$. & Some beekeeper does not chase any artist. \\
          & No $p$ $r$s every/any $q$. & No beekeeper bewitches any artist. \\
         \hdashline
         \multirow{4}{*}{\sRd} & \emph{all of \sSd{} and:} & \\
          & Every/Some (non-)$p$ $r$s every/some (non-)$q$. & Every non-artist chases some beekeeper. \\
          & Some (non-)$p$ does not $r$ every/any (non-)$q$. & Some beekeeper does not chase any non-artist. \\
          & No (non-)$p$ $r$s every/any (non-) $q$. & No non-beekeeper bewitches any non-artist. \\
          \hdashline
         \multirow{2}{*}{\sSrel}
          & Every/Some/No $o$ who is a $p$ is a $q$. & Every artist who is a dentist is a carpenter. \\
          & Some $o$ who is a $p$ is not a $q$. & Some dentist who is a hunter is not a spy. \\
          \hdashline
          \multirow{2}{*}{\sSrelN} & \emph{all of \sSrel{} and:} & \\
          & Every/Some/No $o$ who is not a $p$ is a $q$. & Every artist who is a not dentist is a carpenter. \\
          & Some $o$ who is a not $p$ is not a $q$. & Some dentist who is a not hunter is not a spy. \\
          \hline
    \end{tabularx}
    \caption{Templates used to generate the problem instances for all five fragments. Round brackets () denote optionals, forward slashes / denote alternatives.}
    \label{tab:examples}
\end{table*}

Table~\ref{tab:examples
shows all templates used to generate the datasets for each of the fragments. Code to generate the datasets, allowing control of the parameters discussed above, is included in the supplementary material available on github\footnote{\url{https://github.com/schlevik/nlr}}.

\section{Random problems}
\label{sec:generation}
In this section  we outline the construction of collections of sets of formulas in the fragments \sSd, \sR, \sRd, \sSrel{} and \sSrelN, in which each generated set is labelled as \textit{satisfiable} or \textit{unsatisfiable}. (The fragment \sS{} is not interestingly different
from \sSd{}, and will not be considered in the experiments reported here.
These collections are partitioned into training and evaluation sets, enabling us to test the ability of neural networks to learn to recognise satisfiability under a range of conditions.

Any sentence in $\sSd$ translates to a formula having either of the forms $\forall x(\pm p(x) \rightarrow \pm q(x))$ or $\exists x(\pm p(x) \wedge \pm q(x))$. We may thus generate a sentence of $\sSd$ pseudo-randomly by selecting a universal sentence with probability $p_u$, a negated subject with probability $p_{\bar s}$ and a negated object with probability $p_{\bar o}$, and then choosing $p$ and $q$ at random from some collection of $n$ nouns. By
carrying out this process $s$ times, we obtain a random set $\Phi$ of \sSd-sentences ($|\Phi| = s$).  For definiteness, we set $p_{\bar s}=p_{\bar o}=0.5$ and $p_u = 0.8$. In addition, we remove any inconsistent sentences, such as ``Some $p$ is not a $p$.''  In
choosing the various parameters, we fix $n/s=0.8$, which, as we have empirically established,
keeps the proportion of satisfiable instances at roughly 50\%. Collections
of such problem instances are created for various values of $s$.  The ratio $n/s=0.8$ corresponds (for \sSd) roughly to the critical region of SAT problems studied in~\cite{nnFrag:rs21},
where it was shown that learning on data from this region is more effective than learning from uniformly sampled data. However, we need to be wary of assuming that such instances are difficult---an issue addressed in Section 4.

For \sRd, we proceed similarly, generating $s$ sentences at random over a fixed collection of $n$ nouns and $v$ transitive verbs. Every sentence in \sRd{} is either a sentence in \sSd{} or translates to a formula having one of the forms $\forall x (\pm p(x) \rightarrow \gamma)$ or
$\exists x (\pm p(x) \wedge \gamma)$, where $\gamma$ is either $\forall y(\pm q(y) \rightarrow \pm r(x,y))$ or
$\exists y(\pm q(y) \wedge \pm r(x,y))$. Call sentences in $\sRd{} \setminus  \sSd{}$ {\em relational sentences}. We
may thus generate a sentence of \sRd{}  pseudo-randomly by choosing to produce a relational sentence with probability
$p_r$. If we choose to produce a non-relational sentence (i.e.~a sentence in \sSd), we proceed as above; otherwise a negated verb is chosen with probability $p_{\bar v}$, a universally quantified $\gamma$ with probability
$p_{uu}$; the other parameters, $n$, $v$, $p_u$, $p_s$ and $p_o$ are interpreted as before. By setting
$p_{\bar s}=p_{\bar o}=0$, we guarantee that every generated relational sentence has a non-negated subject and a non-negated object, and hence is
a sentence of $\sR$.  By repeating this process $s$ times, we obtain an set $\Phi$ of sentences in \sRd{} (or \sR).
When generating instances of $\ensuremath{\mbox{\rm Sat}}(\sR)$, we thus set
$p_r=0.2$, $p_{\bar s}=p_{\bar o}=0$,
$p_{\bar v}=0.5$ and $p_u = p_{uu} = 0.8$; in addition, we fix  $n/s=0.6$ and $v/s = 0.15$, which, as we have empirically established,
keeps the ratio of satisfiable to non-satisfiable instances at roughly 50\%.
Likewise, when generating instances of $\ensuremath{\mbox{\rm Sat}}(\sRd)$, we set $p_{\bar s}=p_{\bar v}=0.5$, with the other parameters as for $\sR$; however, we adjust $n/s$ to $0.64$ in order to maintain the ratio of satisfiable to non-satisfiable instances.

Finally, for fragments with
relative clauses, \sSrel{} and \sSrelN, in addition to the parameters introduced for \sSd, we control the probability of negated relative clauses by the parameter $p_{\bar r}$. By setting
$p_{\bar r}=0$ we guarantee that every generated sentence has an un-negated relative clause, and hence is
a sentence of \sSrel{}. We additionally set $p_{\bar o}=0.5$ and $p_u=0.8$, and for \sSrelN{}, we set $p_{\bar r}=0.5$.
We empirically establish that setting $(n-0.225)/s~=~0.59$ yields a probability of satisfiability of approximately 0.5
for both fragments.

The satisfiability of a generated problem instance is determined using the Vampire automated theorem prover (ATP) \cite{Kovacs2013First-OrderVampire}, which (assuming termination) either reports that the input set is satisfiable or outputs a proof of a contradiction.
We record, for each generated problem instance, whether it  is satisfiable, and, if not, the number $l$ of lines in the
discovered proof of a contradiction (\emph{proof length}) as well as the number of input sentences, $d$, used in that proof. The ATP terminated on all generated problem instances; there is, however, no general guarantee that the proofs found are the shortest possible.

Generated sentences are created in the relevant fragments of English with templates depicted in Table~\ref{tab:examples}
and realised with dictionaries of nouns that describe categories for unary predicates (e.g. ``artist'', ``beekeeper'') and transitive verbs for binary predicates (e.g. ``admires'', ``bewitches''). We use distinct vocabularies for training and evaluation data and use words with non-overlapping semantic fields.
Unless stated otherwise, to maintain comparability between the different datasets, we generate $60000$ examples for training and $8000$ for evaluating model accuracy. This is achieved by generating $3750$ and $500$ (for training and evaluation sets, respectively) examples for each number of sentences $s$ between $15$ and $30$.

\section{Constructed problems}
One attractive feature of the fragments \sS, \sSd{} and \sR{} is that their satisfiable sets of formulas admit of a simple graph-theoretic characterization. This gives us an additional means of creating data sets comprising challenging problem instances.

We
illustrate with \sS{}. Let a set $\Phi$ of \sS{}-sentences be given, and let $p_1, \dots, p_n$ be the common nouns (predicates)
occurring in $\Phi$. Now let $V$ be the set of expressions $p_i(x)$ or $\neg p_i(x)$ ($1 \leq i \leq n$). We call the elments of $V$ {\em literals} and let the variables $\ell$ and $m$ range over $V$. If $\ell \in V$, denote by $\bar{\ell}$ the opposite literal obtained by adding or removing the negation sign as appropriate. Now let $E$ be the set of ordered pairs of literals $(\ell, m)$ such that
$\Phi$ contains a sentence formalized as
either $\forall x(\ell \rightarrow m)$ or as
$\forall x(\bar{m} \rightarrow \bar{\ell})$.
Thus, $G_\Phi= (V,E)$ is a directed graph. Write
$\ell \Rightarrow_\Phi m$ if there is a path in $G_\Phi$ from $\ell$ to $m$.
It can be shown
\citep[Sec.~3]{nnFrag:p-hm09} that a set of \sS-formulas $\Phi$ is satisfiable if and only if $\Phi$ contains no sentence $\exists x (\ell \wedge  m)$ such that either: \textup{(i)} $\ell \Rightarrow_\Phi \bar{\ell}$; \textup{(ii)} $m \Rightarrow_\Phi \bar{m}$ or \textup{(iii)} $\ell \Rightarrow_\Phi \bar{m}$.
Thus, determining (un)satisfiability in \sS{} amounts to detecting certain
{\em forbidden configurations} (in this case: paths) in the directed graph $G_\Phi$. We regard the length of the
path  (if it exists) as the {\em size}
of the forbidden configuration. Satisfiability in \sSd{} is characterized similarly: we simply have to check that, in addition,
$V$ contains no pair of opposite literals
$o$ and $\bar{o}$ such that $o \Rightarrow \bar{o}$ and $\bar{o} \Rightarrow o$. Again, if a set of sentences of \sSd{} is inconsistent, then it contains a forbidden configuration having a well-defined {\em size}.

This gives us controlled way to generate hard problem instances. Consider the fragment \sSd.
We begin by simply constructing a forbidden configuration having a given size, $d$. To obtain an \textit{unsatisfiable} problem instance $\Phi$ of size $s$, we then add $s - d$ random sentences, checking (using a simple algorithm) that doing so does not create any smaller forbidden configurations. To obtain a \textit{satisfiable} problem instance of size $s$, we reverse one of the implications in the forbidden configuration, and check that the added $s - d$ random sentences do not cause an unsatisfiability. In effect, $d$ is a guaranteed difficulty level; it yields a lower bound on the proof length required to establish unsatisfiability.
At the same time, the satisfiable and unsatisfiable instances thus generated are not easily distinguished by any superficial characteristics. We denote the problem $\ensuremath{\mbox{\rm Sat}}(\sSd)$ constructed as just described with $d$ in a specified range as $\ensuremath{\mbox{\rm Sat}}(\sSd_{[\cdot,\cdot]})$. Thus, for example, in $\sSd_{[2,6]}$, unsatisfiable problem instances have $2 \leq d \leq 6$.

For $\sR$,  the corresponding characterization of unsatisfiability in terms of forbidden configurations involves several cases~\citep[Sec.~4]{nnFrag:p-hm09}.
For simplicity, we generate difficult instances by focusing on just one of these types of forbidden configuration, which we call an $\forall\forall$-configuration.
We begin by constructing an
$\forall\forall$-configuration of specific size $6d$ (for $d \geq 1$).
(Such a collection of sentences is always unsatisfiable.)
To obtain an \textit{unsatisfiable} problem instance of size $s$,
we add $s - 6d$ randomly generated sentences, again checking that
the resulting unsatisfiability is due entirely to the forbidden configuration.
\textit{Satisfiable} instances are then obtained by reversing one of the implications in the $\forall\forall$-configuration, and checking that this does not lead to unsatisfiability. Denote the problem $\ensuremath{\mbox{\rm Sat}}(\sR)$ constructed as just described with $d$ in a specified range as $\ensuremath{\mbox{\rm Sat}}(\sR_{\langle\cdot,\cdot\rangle})$. For example, in $\sR_{\langle 1,2\rangle}$, inconsistent problem instances are inconsistent because of $\forall\forall$-configurations of size 6 or 12

It is not possible to characterize $\ensuremath{\mbox{\rm Sat}}(\sRd)$ in terms of forbidden configurations in this simple way. As a substitute, we use the proof-lengths of the proofs found by the ATP as a rough guide to difficulty.
To generate difficult instances of \sRd, therefore, we first generate random instances as in
Sec.~\ref{sec:generation};  we then  filter out those unsatisfiable instances with short proof-lengths (as reported by the ATP), and then remove satisfiable instances at random to preserve the proportion of satisfiable instances overall.

\section{Experimental Setup}
In the following study, we investigate whether neural networks, and in particular state-of-the-art transformer-based language models \cite{Devlin2018} can learn to perform satisfiability checks on examples representing the selected fragments. First, we investigate whether they can do so in principle, by optimising and evaluating classifiers on training and evaluation data drawn from the same distribution. Second, in an attempt to understand whether they reliably learn the underlying logical principles that govern (un-)satisfiability, we evaluate their \emph{generalisation capabilities} on out-of-distribution evaluation data.  We do so by altering various parameters of the training and evaluation data generation to control the structure
of the generated problem instances.

More specifically, we cast the problem of determining satisfiability as binary text classification and conduct experiments with three transformer based language models, RoBERTa, XLnet and Electra \cite{Liu2019c,Yang2019a,Clark2020ELECTRA:Generators}.which are further described in the Appendix. We employ pre-trained language models because initial experiments showed that these tend to converge faster compared to training from scratch, despite the fact that their pre-training objectives bears little similarity to the task at hand. Following \newcite{Devlin2018}, we represent each problem in plain English text prepended by the special \texttt{[CLS]} token as input to the language model. The text is embedded using the language model, and the embedding of the \texttt{[CLS]} token, as output by the final layer of the language model, is projected into a two-dimensional space, representing the odds of the problem being satisfiable. During inference, we pick the highest logit as the model's prediction and during training we minimise the cross-entropy loss between the logits and the expected class, thus optimising the parameters of the language model to produce the expected prediction conditioned on the input. We keep the choice of hyper-parameters (detailed in Appendix) consistent across experiments.

\section{Results and Analysis}

We report and analyse the results of the conducted empirical study.
For all results we measure the error as a confidence interval at $\alpha = 0.05$,  using asymptotic normal approximation and omit reportage for brevity, as all measures are in the range of at most
two percent points. We average results obtained for all three language models.

\begin{table}[!tb]
    \centering
    \begin{tabular}{c|ccccc}

    \multirow{1}{*}{\textbf{Problem size}} & \sSd & \sR & \sSrel & \sSrelN & \sRd \\

    \hline
        $15\leq s \leq 30$ &  76 & 93 & 94 & 80 & 74\\
    \hdashline

        $30\leq s \leq 40$\footnotemark[1] & 64 & 89 & 94 & 82 & 72 \\
        $40\leq s \leq 45$ & 63 & 86 & - &  -  & 71 \\
        \hline
    \end{tabular}
    \caption{Accuracy of optimised models trained on random examples consisting of $15$ to $30$ sentences ($s$) and evaluated on longer random problem instances.}
    \label{tab:res-longer}
\end{table}

\footnotetext[1]{$37$ for \sSrel{} and \sSrelN{} to fit transformers' $512$-token limit}
\textbf{\emph{Transformers perform well on random examples in all fragments.}}
To seek evidence for the first question we train and evaluate separate models on randomly generated problems instances of each of the five fragments. The results are reported the first row of Table~\ref{tab:res-longer} and suggest that the models perform well on randomly generated problems in all fragments, even on the \textsc{ExpTime}-complete $\sRd{}$ fragment. Surprisingly, the obtained accuracies do not seem to correspond to the complexity classes of the elicited fragments. Note that the results reported in this table are not necessarily that of the best-performing model; for example, by training the RoBERTa model longer and on a larger dataset representing the \sRd{} fragment, we obtain accuracy scores of up to $81\%$ (from original $79\%$, see Table~\ref{tab:res-longer-roberta} in the Appendix). However, to maintain comparability and as the difference is marginal, we use the same training budget for all models optimised on different fragments. The task appears non-trivial, as a simple LSTM-based classifier was not able to outperform the majority class baseline even on the simplest \sSd{} fragment and after explicit hyper-parameter optimisation.

To investigate whether this performance generalises with the size of the problem instances, we generate evaluation sets with $30 \leq s \leq45$ sentences for longer problems. Note that we are constrained to problems of the size of up to $512$ tokens, as a technical constraint of the pre-trained language model, hence we do not investigate generalisation capabilities to problems beyond 45 (37 for \sSrel{}, \sSrelN{}) sentences.
The remainder of Table~\ref{tab:res-longer} shows that models generalise consistently to problems larger than seen during training, with the notable exception of the model optimised on \sSd{}, which exhibits the most significant drop of over $10$ percent points.

Superficially, Table~\ref{tab:res-longer} appears to indicate good generalisation performance. However, it is important to realise that simply increasing the number of sentences does not make the reasoning problems harder, as witnessed by the fact that the number of sentences, $d$, required to prove contradiction does not increase: on average, $d=3.50$ for examples with  $15$ to $30$ sentences, and  $d=3.58$  for problems with $30$ to $45$ sentences.
Thus, the forbidden configurations the network is identifying are, for the most part, small, even for large numbers of sentences. A complimentary analysis in the Appendix reveals further, that these forbidden configurations are likely to be common between different fragments.

\textbf{\emph{Transformers are not robust to distribution shifts.}}
Moving on to the second question, we investigate whether the optimised models truly pick up the reasoning patterns as intended or rather overfit to their training data as an artefact of the configuration of parameters controlling the stochastic generation. Approximating the ``hardness'' of a problem instance by its proof length $l$, we find that for all fragments, the overwhelming majority (ranging from 29\% in \sS{} to 86\% in \sSrelN{}) of contradictory examples have short proof lengths of $12$ or less, indicating that random problems are, in fact, unsatisfiable for trivial reasons which are easy to show (See also histogram in Appendix). Thus, we collect ``hard'' examples by \mbox{(over-) generating} a large body of examples and then filtering by proof length and refer to them as \emph{random hard} problem instances. Naturally, in this way we can only capture the hardness of \emph{inconsistent} examples, therefore the evaluation focuses on those.

When comparing the (out-of-distribution) performance of models on ``easy'' and ``hard'' non-satisfiable problem instances with proof length of at least $42$ (Table~\ref{tab:res-harder}, second and third rows), on average, there is a gap of $25$ percent points,
This suggests that models in fact overfit to simple problems that tend to dominate the
randomly generated datasets without picking up the general principles governing reasoning in the corresponding fragments. Models optimised on ``hard'' training examples  (proof length $\geq 22$, complemented with an equal number of random consistent problems), generalise well to even harder problems (proof length $\geq 42$, Table~\ref{tab:res-harder}, last row).  This suggests that the
models can learn to classify hard problem instances when presented explicitly by supplying appropriate training data.
This performance does not carry over to simpler problems, however, as models optimised on harder problems exhibit a drop in accuracy when evaluated on simpler problems, as the penultimate row of Table~\ref{tab:res-harder} shows. In conjunction, these observations suggest that the models tend to overfit to patterns in the generated data arising from the parameterisation of the generation algorithm, rather than learning to perform satisfiability checking in a more general sense. In other words,  just like a bad student of logic, they appear to ``learn the proofs'' rather than the logical principles behind the proofs required for successful systematic generalisation.

\begin{table}[!tb]
    \centering
    \resizebox{\columnwidth}{!}{
    \begin{tabular}{cc|ccccc}

    \textbf{Train} $l$ & \textbf{Eval} $l$ & \sSd & \sR & \sSrel & \sSrelN & \sRd \\

    \hline

         \multirow{3}{*}{\begin{tabular}{@{}c@{}}$l \geq 6$ \\ \emph{(easy)}\end{tabular}} & satisfiable & 61 & 87 & 90 & 53 & 58 \\
          & $l \leq 12$ & 98 & 99 & 99 & 70 & 98\\
         & $l \geq 42$ & 84 & 74 & 70 &  42 & 70 \\
         \hdashline
         \multirow{3}{*}{\begin{tabular}{@{}c@{}}$l \geq 22$ \\ \emph{(hard)}\end{tabular}} &satisfiable & 57 & 89 & 86 & 50 & 52 \\
          & $l \leq 12$ & 68 & 61 &33 & 61& 72\\
         & $l \geq 42$ &100 & 94 & 99 &  96 & 73 \\
        \hline
    \end{tabular}
    }
    \caption{Accuracy of models trained on random satisfiable and easy/hard insatisfiable examples, and evaluated on random satisfiable and easy/hard insatisfiable examples with proof length $l\leq12$ and $l \geq 42$.}
    \label{tab:res-harder}
\end{table}

\textbf{\emph{Transformers seem unable to reliably learn the distinct reasoning patterns.}}
Finally, as determining non-satisfiability for the fragments \sSd{} and \sR{} involves detection of one of a handful of forbidden configurations, we generate data that exposes precisely these forbidden configurations.

The four top rows of Table~\ref{tab:res-constructed} show that models optimised on \emph{random} and \emph{random hard} datasets in \sSd{} and \sR{} pick these patterns up to a varying degree: while all models perform better than chance, the evaluation performance drops considerably, when comparing to in-distribution performance.
In the case of \sSd{}, breaking down the performance by chain depth, as shown in Figure~\ref{fig:breakdown}, reveals that models optimised on \emph{random} data perform best on examples with chain length two (essentially detecting inconsistencies of the form ``All $p$ are $q$'', ``All $q$ are $s$'', ``Some $p$ are not $s$'') and fail to generalise beyond that, while models trained on \emph{random hard} data perform best on examples with chain length five, with their performance deteriorating for examples with longer and shorter chains. This reinforces the previous point that these models appear to have learned to identify problems that have proofs with similar structure to those in their training data rather than learning to solve the problem in a more general sense.

When we both optimise and evaluate models on the constructed datasets, we find that they are capable of learning these inconsistency patterns well, and generalise to harder problems unseen during training: the RoBERTa model optimised on \sSd{} with chain lengths between two and six performs just as well on evaluation data with chain lengths of up to 10 (Table~\ref{tab:res-constructed}, row five). However, other models fail to learn these patterns from constructed \sSd{} data, suggesting that it is a challenging task. Similarly, all models optimised on \sR{} generalise to unseen lengths of the $\forall\forall$-configurations (Table~\ref{tab:res-constructed}, row six).
However, even when seemingly learning these patterns, models fail to reliably transfer these capabilities beyond the constructed cases, as evidenced by the poor generalisation performance when trained on the constructed datasets and evaluated on randomly generated data  (Table~\ref{tab:res-constructed}, bottom). For \sR{}, the bad generalisation capability is expected, as  the constructed dataset does not contain inconsistency patterns other than the $\forall\forall$-configurations (e.g. examples where only the non-relational statements are inconsistent). However, this is inconsistent with the case of \sSd{}, as all possible inconsistency patterns are covered in the constructed dataset, yet the optimised RoBERTa models fail to transfer to random \sSd{} data.

\begin{table}[!tb]
    \centering
    \begin{tabular}{l l c}
    \textbf{Train On} & \textbf{Evaluate On} & \textbf{Accuracy} \\
    \hline

    \tikzmarkin{d}(1.01,-0.15)(-0.2,0.3)$\sSd$ & \setbordercolor{rred!35}\tikzmarkin{f}(1.2,-0.15)(-0.2,0.3)$\sSd_{[2,6]}$ & $65$ \\
    $\sSd_{l\geq22}$ & $\sSd_{[2,6]}$ & $57$ \\
    $\sR$ & $\sR_{\langle1,2\rangle}$ & $53$ \\
    $\sR_{l\geq22}$ \tikzmarkend{d} & $\sR_{\langle1,2\rangle}$ & $58$ \\

    \setbordercolor{rred!35}\tikzmarkin{g}(0.1,-0.19)(-0.2,0.3)$\sSd_{[2,6]}$ & $\sSd_{[2,10]}$ &  $96$\footnotemark[2] \\

    $\sR_{\langle1,2\rangle}$ & $\sR_{\langle1,3\rangle}$ \tikzmarkend{f} & $100$ \\

    $\sSd_{[2,6]}$ &\tikzmarkin{e}(1.93,-0.19)(-0.2,0.3)$\sSd$ & $54$\footnotemark[2] \\
    $\sR_{\langle1,2\rangle}$ & $\sR$ & $48$ \\

    $\sSd_{[2,6]}$+$\sR_{\langle1,2\rangle}$\tikzmarkend{g}&$\sR$\tikzmarkend{e}& $88$\footnotemark[2] \\

    \hline
    \end{tabular}
    \caption{Accuracy  of model optimised and evaluated on {\color{bblue} randomly} generated and {\color{rred}constructed} datasets in \sSd and \sR{}. The datasets $\sSd_{l\geq22}$ and $\sR_{l\geq22}$ have unsatisfiable examples with at least proof length $22$, while $\sSd_{[\cdot,\cdot]}$, $\sR_{\langle\cdot,\cdot\rangle}$ have constructed chains in the bracketed range.}
    \label{tab:res-constructed}
\end{table}
\footnotetext[2]{Results for RoBERTa only, as other models failed to converge on constructed \sSd{} data.}

\pgfplotsset{
/pgfplots/my legend/.style={
legend image code/.code={
\draw[thick,ggreen,dotted](-0.05cm,0cm) -- (0.3cm,0cm);%
   }
  }
}

\begin{figure}[tb]
    \centering
    \begin{tikzpicture}
\begin{axis}[
    height=15em,
    width = 1\columnwidth,
    ybar=5pt,
    ymin=40,
    ymax=100,
    scaled y ticks = false,
    extra y ticks = 50,
    extra y tick labels={},

    extra y tick style={grid=major,major grid style={thick,draw=ggreen,dotted}},
    bar width=4.25pt,
    x tick label style={},
    major x tick style = transparent,
    ylabel={Accuracy},
    xlabel={Chain Length},
    x tick label as interval,
    xmajorgrids=true,
    ymajorgrids=true,

    legend columns=1,
        xticklabels={$2$,$3$,$4$,$5$, $6$},
    xtick={0,1,2,3,4,5},
    xmin=0, xmax=5,
    ]

    \addplot+[legend entry=\sSd, bar shift=-2.5pt, color=bblue, fill=bblue]
    coordinates {
        (0.5,91.69) (1.5,65.31) (2.5,59.69) (3.5,59.13) (4.5,60.37)
        };
    \addplot+[legend entry=\sSd$_{l\leq 22}$, bar shift=+2.5pt, color=rred, fill=rred]
    coordinates {
        (0.5,51.8) (1.5,54.25) (2.5,58.38) (3.5,63.94) (4.5,62.31)
        };
    \addlegendimage{my legend}
    \addlegendentry{Random Guess}

\end{axis}
\end{tikzpicture}
    \caption{Accuracy by chain length for RoBERTa models optimised on \sSd{} and \sSd$_{l\leq 22}$, evaluated on \sSd$_{[2,6]}$.
    }
    \label{fig:breakdown}
\end{figure}

\section{Related Work and Conclusion}

The work reported in this paper represents a continuation of various studies carried out on ``challenge sets'', proposed to investigate the ability of (optimised) neural networks to perform different kinds of reasoning. Such studies range from monotonicity entailments \cite{nnFrag:GRP20,Yanaka2020} to probing lexical knowledge \cite{Glockner2018} to logical connectives \cite{Salvatore2019,Richardson2019a} or verb symmetry \cite{Mitra2019}. These studies are related to ours, in that they seek to isolate capabilities of interest and perform controlled experiments using synthetic datasets. They have in common that models optimised on crowd-sourced datasets, such as MNLI, \cite{Williams2018}, perform poorly on the challenge set data exhibiting the elicited phenomenon, but fine-tuning the optimised model on portions of these data improves the performance.

However, as \newcite{Rozen2019} show, good scores after the fine-tuning probably stem from the fact that the investigated model has learned to adapt to the regularities of the challenge set rather than learning a general notion of the investigated phenomenon. Our analysis is similar: transformer-based neural networks perform well on randomly generated data, but this performance is brittle, and the models overfit to the problem space as set out by the dataset generation method. They do not generalise well to examples outside of that space, suggesting that they do not generalise \emph{systematically} \cite{Fodor1988ConnectionismAnalysis}, i.e. they struggle to identify a finite set of rules and to apply them repeatedly. Similar to our findings, research on systematic generalisation suggests that neural networks tend to generalise without systematicity in supervised learning scenarios \cite{Johnson2017CLEVR:Reasoning,Lake2017GeneralizationNetworks,Goodwin2020}, although these studies, unlike ours, did not concern pre-trained models.

One might argue that it is unfair to expect a statistical model that relies on correlations to learn patterns that are not obviously present in the data. However, it seems that such claims are being made in the literature \cite{Clark2020a}.
While we observe that models optimised on constructed examples generalise well to  harder problems unseen during training, we also show that this capability appears not to transfer to examples that are only superficially different. Thus, in our experiments, similar to \newcite{nnFrag:rs21}, we find that the optimised models are not able to reliably disentangle and acquire the different reasoning patterns required to successfully complete the task of determining satisfiability.

Our study highlights one of the issues with empirically postulating neural networks various capabilities by means of good performance on challenge sets. They have only negative predictive power \cite{Gardner2020}: while low performance indicates the lack of a capability, the converse does not necessarily hold. This can be taken as a motivation to develop formal verification methods for neural networks \cite{Shi2020RobustnessTransformers}, or investigate worst-case bounds for different phenomena \cite{Raghunathan2018,Jia2019}.

Our formulated task naturally allows us to expand the scope of the controlled experiments: for example, by increasing the closed-class vocabulary.
Another possible avenue is to focus on improving the systematic generalisation of neural approaches, for example by providing the formulas required to prove that a set of sentences is unsatisfiable as additional supervision signal, or by relying on modular or model-based approaches \cite{Andreas2016NeuralNetworks,Lake2013One-shotProcess}.

\section*{Limitations}

The design of the study limits our findings by design - by removing the need of inducing
meaning postulates (i.e. commonsense reasoning and world knowledge) we explicitly focus
on logico-syntactic capabilities, analogous to how “reasoning” is defined for symbolic
approaches to AI. Arguably, In “real world” application scenarios, commonsense reasoning
and world knowledge cannot be fully disconnected from the requirement to perform
reasoning, which allows our inquiry to draw fundamental conclusions about the capabilities
of transformer-based language models rather than to make recommendations which are of
immediate relevance to practitioners.

Our study also suffers from the inductive dilemma. We find that multiple transformer-based
language models follow the trends reported in this paper, specifically that they fail to robustly
identify the reasoning patterns necessary for reliably determining satisfiability in the elicited
fragments. However, due to the empirical nature of this research, this finding is of course not
a guarantee that some neural architecture (transformer-based or otherwise) could still
perform well, when tested in our out-of-distribution evaluation settings.

\section*{Acknowledgements}
The authors would like to acknowledge the use of the Computational Shared Facility at The University of Manchester and thank the anonymous reviewers from the ARR December 2021 cycle for their valuable feedback.