# Anna Karenina Strikes Again:
Pre-Trained LLM Embeddings May Favor High-Performing Learners

Abigail Gurin Schleifer1 Beata Beigman Klebanov2 Moriah Ariely1 Giora
Alexandron1
1 Weizmann Institute of Science, Rehovot, Israel
2 ETS, Princeton, USA
{abigail.gurin-schleifer,moriah.ariely,giora.alexandron}
@weizmann.ac.il
<EMAIL_ADDRESS>

###### Abstract

Unsupervised clustering of student responses to open-ended questions into
behavioral and cognitive profiles using pre-trained LLM embeddings is an
emerging technique, but little is known about how well this captures
pedagogically meaningful information. We investigate this in the context of
student responses to open-ended questions in biology, which were previously
analyzed and clustered by experts into theory-driven Knowledge Profiles (KPs).
Comparing these KPs to ones discovered by purely data-driven clustering
techniques, we report poor discoverability of most KPs, except for the ones
including the correct answers. We trace this ‘discoverability bias’ to the
representations of KPs in the pre-trained LLM embeddings space.

##  1 Introduction

Classifying students into behavioral or cognitive profiles using unsupervised
cluster analysis techniques is a common application of machine learning to
educational data Le Quy et al. (2023); Martin et al. (2023); Ariely et al.
(2024); Rastrollo-Guerrero et al. (2020); Bovo et al. (2013). Recently, there
has been a growing interest in applying this methodology to textual student
responses that are decoded using pre-trained large language models into
vectorized embeddings in semantic spaces Martin et al. (2023); Wulff et al.
(2022); Masala et al. (2021). The operational appeal of this approach is that
it minimizes the need for expert knowledge, which is costly to inject through
human labeling procedures Nehm and Haertig (2012); Tansomboon et al. (2017);
Li et al. (2023); Ariely et al. (2024). However, the validity of patterns
discovered this way depends on the ability of the embeddings to maintain the
pedagogically meaningful information that existed in the original, textual
representations of responses Devlin et al. (2018); Seker et al. (2022) and of
the algorithmic method to discover them. Evaluation of emergent profiles is
often done in terms of the internal quality of the clustering, as data is
usually not available to estimate the extent to which the discovered profiles
align with a pedagogically meaningful representation of the responses. Without
such an evaluation, a loss of important information can be overlooked,
potentially leading to sub-optimal educational decisions that rely on this
analysis Le Quy et al. (2023).

To investigate whether this hypothesized risk manifests in real-life
educational context, we utilize student answers to two constructed response
questions in high school biology. The data was previously analyzed by a team
of biology education researchers and experienced teachers, and graded
according to a theory-driven detailed analytic rubric that is based upon the
Causal-Mechanical Explanation framework Ariely et al. (2024); Salmon (2006).
The rubric contained 10 (item 1) or 11 (item 2) binary categories, each
checking for the occurrence of a specific key piece of information in the
response. Using these human-generated binary vectors of length 10 (11), the
responses were clustered using a KMeans algorithm into a set of 6 (7)
Knowledge Profiles (KPs) that were found by teachers to encapsulate specific
patterns of errors.

The validity of the KPs was evaluated in several ways. First, human experts
conducted a qualitative analysis to assess whether each KP captures a specific
and distinct pattern of errors. Second, we analyzed the results
computationally, showing that i) the KPs were consistent across the two items,
namely, revealing the same type of conceptual errors; and ii) the learners
tended to exhibit the same type of conceptual error (KP) in both items. Third,
we conducted an in-class formative assessment intervention study that provided
automated guidance to students based on their KP, and showed significant
improvement in their performance on a different prompt that measures the same
conceptual knowledge. These analyses provided strong evidence that the KPs
capture pedagogically meaningful information (for full details, see Ariely et
al. (2022, 2024)).

Using these data, we are in a position to answer two research questions:

RQ1

What is the correspondence between clusters that are computed from pre-trained
LLM embeddings of student responses and theory-based KPs?

To preview the result, we find that two clustering techniques that are
commonly used for such tasks Le Quy et al. (2023) – KMeans Lloyd (1982) and
HDBSCAN McInnes et al. (2017) – largely fail to discover the KPs though
retrieval is somewhat better for the profile containing the correct responses.
Following up on this finding, we go ‘upstream’, to the pre-trained embeddings,
and investigate:

RQ2

How well are the KPs represented in the pre-trained embeddings space?

Our results reveal a strong relationship between the quality of the responses
in the profile (correct or various degrees of incorrect) and the shape and
density of its embeddings-based representation. We refer to this relationship
as an ‘Anna Karenina principle’ and tie it to the profile discovery failure we
observed in RQ1.

The contribution of this work is twofold. First, it is the first to
demonstrate the Anna Karenina principle in the context of pre-trained
representation of student responses to open-ended questions. Second, our
results suggest that, in some cases, out-of-the-box pre-trained LLM embeddings
may be a pedagogically unsound basis for profile discovery.

##  2 Related Work

###  2.1 NLP-based profiling of constructed responses in science education

Open-ended items require students to develop and construct their answers,
reflect on their knowledge, and integrate it with new ideas Fellows (1994).
Reasoning and evidence-based defense of an argument is key for testing
scientific hypotheses Toulmin (2003). Therefore, constructing causal
explanations is an essential skill for students of science to learn Ariely et
al. (2024); Martin et al. (2023); practice and high-quality feedback are key
elements in helping students master the skill Hattie and Timperley (2007);
Gerard and Linn (2016); Tansomboon et al. (2017).

Analyzing open-ended items to provide feedback is a time-consuming, complex
task. Automating some of the analyses for assessment and feedback purposes is
promising for supporting teaching and learning Tansomboon et al. (2017);
Gerard and Linn (2016); Ariely et al. (2023).

Most systems for automated evaluation of scientific explanations to date had
been designed in the supervised machine learning framework Schleifer et al.
(2023); Sung et al. (2019); Riordan et al. (2020); Kumar et al. (2019);
Mizumoto et al. (2019); Li et al. (2021). Among the unsupervised approaches,
Masala et al. (2021) extracted the main takeaways from students’ feedback on
different components in academic courses, using KMeans to cluster pre-trained
BERT embeddings of students’ feedback. Martin et al. (2023) applied HDBSCAN
over pre-trained LLM embeddings and to find emergent argumentation patterns’
characteristics. Wulff et al. (2022) investigated HDBSCAN clustering over LLM
embeddings to evaluate the attention of preservice physics teachers to
classroom events elicited from open-ended text responses. A semi-supervised
coding method in which homogeneous clusters receive the same coding
automatically and heterogeneous clusters are fully labeled by humans was
proposed by Andersen et al. (2023) and applied to student responses to PISA
items.

###  2.2 Biases in pre-trained LLMs

While LLMs are powerful meaning representations that undergird the state-of-
art systems on a wide range of NLP tasks, they are also known to exhibit a
plethora of social biases that could lead to social harm when the models are
used in downstream tasks Bender et al. (2021). In a recent review of the
current state of research on LLM bias evaluation, Goldfarb-Tarrant et al.
(2023) criticize the field for focusing heavily on the upstream, pre-trained
LLMs, in most cases without considering the connection to a specific task the
LLMs is being put to (68% of the reports reviewed), citing this as a threat to
the predictive validity of bias measurements.

In fact, the literature that does consider the connection between upstream
(intrinsic) and downstream (extrinsic) behavior suggests that it is not
straightforward. Considering static embeddings (e.g., word2vec) and a commonly
used bias test, the Word Embedding Association Test (WEAT) Caliskan et al.
(2017), Goldfarb-Tarrant and colleagues Goldfarb-Tarrant et al. (2021) found
no clear relationship with performance of models using the embeddings, as
measured by differences in precision and recall of retrieval of the target
construct on data from privileged and non-privileged groups. Extension to
contextual embeddings and a wider range of tasks and measures yielded similar
results Cao et al. (2022); Kaneko et al. (2022). Our contribution extends the
discussion towards social constructs beyond the typically considered
demographic attributes such as gender, race, ethnicity, age towards a
distinction that is particularly relevant when dealing with learner data –
that of learners at the more or less advanced state of understanding of the
phenomenon under consideration. We are not aware of prior work comparing LLM
representations based on knowledge-related profiles; the closest finding in
the literature are examples of poorer performance of LLM-based systems on data
produced by English language learners with respect to native speakers of
English Baffour et al. (2023). Additionally, we explore LLMs in a relatively
low-resource language (Hebrew) in contrast to the bulk of current work that
focuses on English or other high-resource languages: In the 90 LLM bias
studies evaluated by Goldfarb-Tarrant et al. (2023), only two report results
in a language that is not highly resourced.

##  3 Data

The data consists of 669 student responses to two open-ended items in high-
school biology, collected anonymously from students in grades 10-12 from about
25 high schools of varied demographics and socioeconomic status (based on
location) across Israel. Gender distribution was 70$\%$ females (typical to
the gender distribution among high-school biology majors in Israel). The items
deal with the connection between respiration and energy in physical activity
in the context of smoking (Q1) and anemia (Q2), taught as part of the core
topic “The human body”. The items were human-scored using a similar analytic
rubric containing 10 (Q1) or 11 (Q2) categories Ariely et al. (2024). All
rubric categories are binary, each targeting specific information that needs
to be mentioned in a correct response, such as “the role of hemoglobin in
oxygen transportation” or “changes in cellular respiration rate”. The
resulting binary vectors were clustered using KMeans; the clusters were
analyzed by experienced teachers and ranked from 1 to 6 (Q1) or 7 (Q2) with
larger numbers corresponding to clusters with more severe errors. We denote
these clusters Knowledge Profiles, and index them from 1 (KP1) to 7 (KP7). See
Ariely et al. (2024) for a full description of the items and the assessment
framework. The items and examples of student responses and their mapping into
KPs can be found in Appendix 1.

For the purposes of the analysis presented in this paper, all responses were
represented using rich contextualized vectors – embeddings produced by a pre-
trained Large Language Model (LLM). The LLM being used, AlephBERT Seker et al.
(2022), is state-of-the-art for Hebrew. It was trained on a large corpus of
the Hebrew language, including: Twitter tweets, Hebrew Wikipedia, and the
Hebrew subset of the Oscar Suárez et al. (2020) dataset. AlephBERT has the
same architecture as BERT Devlin et al. (2018): 12 layers, 110M parameters,
and 12 attention heads. It was trained on a 52K-word Hebrew vocabulary on
masked token prediction task, and on the Hebrew language tasks: word
segmentation, part-of-speech tagging, and full morphological tagging. It was
further trained on the tasks of sentiment analysis and named entity
recognition.

##  4 Methods

To evaluate whether raw LLM embeddings carry useful knowledge for unsupervised
profiling of responses, we experimented with two common clustering approaches
Le Quy et al. (2023), KMeans Lloyd (1982) and HDBSCAN McInnes et al. (2017),
which implement different clustering mechanisms. The first discovers convex-
shaped clusters; its mechanism is centroid-based and applies an Euclidean
distance function. The second is density-based and can be applied with various
distance metrics, e.g., a metric induced by cosine-similarity, and the
clusters may have various shapes. Both approaches were used previously for
profile discovery in constructed response data Ariely et al. (2024); Martin et
al. (2023); Wulff et al. (2022). Experiments were conducted in Python, using
scikit-learn Pedregosa et al. (2011), SBERT Reimers and Gurevych (2019) and
Pytorch Paszke et al. (2019).

###  4.1 KMeans

The KMeans is a widely used algorithm Lloyd (1982). The algorithm is initiated
with a specified number of clusters and a random initialization of their
centroids. The clustering approach minimizes the within-cluster sum of squared
distances, i.e., Euclidean distance. KMeans clusters are convex and all
samples are assigned to a cluster, i.e., there are no outliers. Convexity
means that for every two points in the cluster, a straight line between them
also lies within the cluster.

###  4.2 Hierarchical Density-Based Spatial Clustering of Applications with
Noise (HDBSCAN)

Another clustering approach, which is more promising in the context of LLMs’
embeddings Martin et al. (2023) is the HDBSCAN McInnes et al. (2017)
algorithm. The approach here is creating a mutual reachability graph where
core samples are points in areas of high density. A cluster is a set of core
samples and a set of non-core samples that are neighbors of core samples but
are not core themselves. Non-core samples are at the fringes of clusters. A
core sample is such that there are ’min_samples’ other samples with a distance
less than $\epsilon$ from it, for some $\epsilon>0$ Pedregosa et al. (2011).
The HDBSCAN mechanism performs clustering for various $\epsilon$ values and
the most stable clustering is chosen.

The default metric for HDBSCAN is Euclidean distance. To use cosine
similarity, we turn it into a distance function McInnes et al. (2017):

$\|x-y\|=\sqrt{2\times(1-CosSim(x,y))}\ ,$ (1)

where $x,y$ are unit vectors, i.e., $\|x\|=\|y\|=1$ Manning (1999). Since
cosine similarity does not depend on vectors’ magnitude, only on the angle
between the two vectors, we first turned every embedding $e_{i}$ to a unit
vector $\frac{e_{i}}{\|e_{i}\|}$ and then applied the HDBSCAN on a pre-
computed metric matrix consisting of all pairwise distances between all
embeddings in the dataset using formula (1).

In contrast to the KMeans, HDBSCAN can find clusters with varied densities and
clusters may have non-convex shapes.

###  4.3 Metrics for Comparing Clusters

To compare the similarity between the KPs and the cluster assignments of the
KMeans/HDBSCAN, we used Adjusted Rand Index (ARI) Vinh et al. (2009). In ARI,
similarity is interpreted as the number of pairs of items on which the
clusterings agree, adjusted for the amount of chance agreement. Let $D$ be a
dataset containing $n$ items that are classified into $m$ clusters by
clustering C and, independently, into $k$ clusters by clustering E. For a pair
of items $(i_{1},i_{2})\in D$, C and E agree on it iff $i_{1}$ and $i_{2}$ are
either (1) assigned to the same cluster in both C and E (let’s say there are
$a$ such pairs), or (2) assigned to different clusters in both C and E (let’s
say there are $b$ such pairs). Now, $a+b$ is the number of agreements between
C and E. The ARI index is given by:

$RI=\frac{a+b}{\binom{n}{2}}\quad~{};~{}\quad
ARI=\frac{RI-E[RI]}{\max(RI)-E[RI]}\quad,$

where $E[RI]$ is the expected RI for some random label assignment Vinh et al.
(2009), and $max(RI)$ equals to $1$. The ARI values range from $-1$ to $1$,
where $1$ indicates perfect agreement, and $-1$ indicates complete
disagreement Hubert and Arabie (1985). Since each student response in our
dataset is labeled with its KP, we evaluated the ARI for each clustering
assignment, i.e., KMeans and HDBSCAN, compared to the KPs. This yields a
global comparison between the KPs and each clustering assignment.

To evaluate the ‘discoverability’ of each KP, we also conducted by-KP
analysis, applying a retrieval paradigm and considering each cluster as an
attempt to retrieve each of the KPs. We calculate recall, precision, and F1
score using a contingency matrix $A=(a_{mn})_{1\leq m\leq k,\ 1\leq n\leq f}$
where rows are the KPs $k=6,7$, and columns are the unsupervised clusters
$C_{n}$ found by KMeans or HDBSCAN, $f=\\#fitted\\_clusters$;

$a_{mn}=\big{|}\\{x:\ x\in KP_{m}\cap C_{n}\\}\big{|}$

the cell $a_{mn}$ in the matrix $A$ counts the number of members of KPm that
fell in cluster Cn. The precision of retrieval of KPm using cluster Cn is
$P_{mn}=\frac{a_{mn}}{|C(n)|}$; the recall is $R_{mn}=\frac{a_{mn}}{|KP(m)|}$.
F1 score is $F_{mn}=\frac{2\cdot P_{mn}\cdot R_{mn}}{P_{mn}+R_{mn}}$,
indicating the extent to which we were able to retrieve KPm using the emergent
cluster Cn.

##  5 Results

###  5.1 RQ1: Correspondence between embedding-based clusters and theory-based
Knowledge Profiles

####  5.1.1 Global alignment between the clusterings

As described in Section 4, we evaluated the agreement between clusterings that
were computed from the embeddings using two cluster analysis methods: KMeans
and HDBSCAN. As we were interested in upper-bounding the discoverability of
the KPs by both algorithms, we “helped" them with additional information (the
number of clusters to the KMeans algorithm, and allowing the HDBSCAN to grid
search for ‘good’ hyperparameters). With $k$ equals the number of KPs per item
(six for Q1 and seven for Q2), the resulting ARIs for the KMeans were 0.122
and 0.191, for Q1 and Q2, respectively. For the HDBSCAN algorithm, we
conducted a grid search for two parameters: $min\\_cluster\\_size$, i.e., the
minimum number of samples in a cluster (values:$\\{3,4,5,10,15,20,30,40\\}$),
and $min\\_samples$, i.e., the number of samples in a neighborhood for a point
to be considered as a core point (values: $\\{1,2,3,4,5\\}$). We report the
best-performing combination in terms of ARI: 0.037 for Q1 (with
$min\\_cluster=5$, $min\\_samples=2$), and 0.038 for Q2 (with
$min\\_cluster=3$, $min\\_samples=3$). Based on these results, we conclude
that the clusters discovered by the KMeans had low agreement with the KPs, and
the clusters discovered by the HDBSCAN had negligible agreement with the KPs.

####  5.1.2 Discoverability of specific KPs

We further investigated the clusters’ matching quality by calculating the F1
score per KP for each of Q1 and Q2. For KMeans, the results show good
retrieval of KP1, the cluster with the highest-quality responses – $F1=0.60,\
0.67$ for items Q1 and Q2 respectively – but much worse retrieval of the other
KPs, with maximal $F1=0.40$ for KP6 in Q1 and $F1=0.47$ for KP2 in Q2. The
clustering results in terms of contingency tables and F1 Scores are presented
in Tables 2 to 4, with KPs as rows and columns as fitted clusters.The maximum
F1 scores per profile are shaded in gray.

|  A |  B |  C |  D |  E |  F
---|---|---|---|---|---|---
KP1 |  0 |  102 |  0 |  0 |  5 |  24
KP2 |  3 |  39 |  0 |  0 |  12 |  37
KP3 |  3 |  22 |  0 |  0 |  13 |  65
KP4 |  13 |  28 |  0 |  0 |  26 |  39
KP5 |  12 |  14 |  0 |  0 |  36 |  50
KP6 |  31 |  5 |  3 |  16 |  55 |  16
Table 1: Q1 KMeans contingency matrix.

|  A |  B |  C |  D |  E |  F
---|---|---|---|---|---|---
KP1 |  .00 |  .60 |  .00 |  .00 |  .04 |  .13
KP2 |  .04 |  .26 |  .00 |  .00 |  .10 |  .23
KP3 |  .04 |  .14 |  .00 |  .00 |  .10 |  .39
KP4 |  .15 |  .18 |  .00 |  .00 |  .21 |  .23
KP5 |  .14 |  .09 |  .00 |  .00 |  .28 |  .29
KP6 |  .33 |  .03 |  .05 |  .23 |  .40 |  .09
Table 2: Q1 KMeans F1 Scores.

|  A |  B |  C |  D |  E |  F |  G
---|---|---|---|---|---|---|---
KP1 |  10 |  0 |  2 |  13 |  13 |  127 |  0
KP2 |  51 |  0 |  22 |  13 |  4 |  30 |  0
KP3 |  11 |  0 |  10 |  21 |  14 |  28 |  0
KP4 |  12 |  0 |  18 |  25 |  16 |  13 |  5
KP5 |  5 |  0 |  16 |  23 |  29 |  6 |  1
KP6 |  3 |  0 |  29 |  8 |  8 |  6 |  10
KP7 |  4 |  9 |  20 |  11 |  8 |  3 |  12
Table 3: Q2 KMeans contingency matrix.

|  A |  B |  C |  D |  E |  F |  G
---|---|---|---|---|---|---|---
KP1 |  .08 |  0 |  .01 |  .09 |  .10 |  .67 |  0
KP2 |  .47 |  0 |  .19 |  .11 |  .04 |  .18 |  0
KP3 |  .12 |  0 |  .10 |  .21 |  .16 |  .19 |  0
KP4 |  .13 |  0 |  .17 |  .25 |  .18 |  .09 |  .09
KP5 |  .06 |  0 |  .16 |  .24 |  .34 |  .04 |  .02
KP6 |  .04 |  0 |  .32 |  .09 |  .10 |  .04 |  .22
KP7 |  .05 |  .24 |  .22 |  .12 |  .10 |  .02 |  .25
Table 4: Q2 KMeans F1 Scores.

The evaluation of HDBSCAN clusters mirrored that of KMeans, showing better
retrieval of KP1 – $0.43,0.46$ F1 scores for Q1 and Q2 – than of any other
profile, with maximal $F1=0.36$ for KP6 in Q1 and $F1=0.29$ for KP2 in Q2. We
observe that, overall, results are worse for HDBSCAN than for KMeans. The
clustering results in terms of contingency tables and F1 Scores are presented
in Tables 6 to 8, with KPs as rows and columns as fitted clusters. The maximum
F1 scores are shaded in gray.

|  A |  B |  C |  D
---|---|---|---|---
KP1 |  19 |  0 |  112 |  0
KP2 |  29 |  0 |  62 |  0
KP3 |  36 |  0 |  67 |  0
KP4 |  49 |  0 |  57 |  0
KP5 |  61 |  0 |  51 |  0
KP6 |  71 |  7 |  43 |  5
Table 5: Q1 HDBSCAN contingency matrix.

|  A |  B |  C |  D
---|---|---|---|---
KP1 |  .10 |  0 |  .43 |  0
KP2 |  .16 |  0 |  .26 |  0
KP3 |  .20 |  0 |  .27 |  0
KP4 |  .26 |  0 |  .23 |  0
KP5 |  .32 |  0 |  .20 |  0
KP6 |  .36 |  .11 |  .17 |  .08
Table 6: Q1 HDBSCAN F1 Scores.

|  A |  B |  C |  D
---|---|---|---|---
KP1 |  23 |  0 |  142 |  0
KP2 |  39 |  0 |  81 |  0
KP3 |  27 |  0 |  57 |  0
KP4 |  30 |  0 |  56 |  3
KP5 |  32 |  0 |  48 |  0
KP6 |  33 |  0 |  31 |  0
KP7 |  32 |  3 |  32 |  0
Table 7: Q2 HDBSCAN contingency matrix.

|  A |  B |  C |  D
---|---|---|---|---
KP1 |  .12 |  0 |  .46 |  0
KP2 |  .23 |  0 |  .29 |  0
KP3 |  .18 |  0 |  .21 |  0
KP4 |  .20 |  0 |  .21 |  .07
KP5 |  .22 |  0 |  .18 |  0
KP6 |  .24 |  0 |  .12 |  0
KP7 |  .23 |  .09 |  .12 |  0
Table 8: Q2 HDBSCAN F1 Scores.

We then considered the possibility that more coarse-grained profiles might
emerge from the clustering than the detailed KPs. To this end, we tried
different options for grouping KPs and calculated the F1 scores between fitted
clusters and the grouped KPs. The best results show an emergent pattern
consistent in both items Q1 and Q2, where one cluster consists of the higher-
quality responses (KP1-KP4) an is retrievable with $F1=0.72,0.74$, and the
other cluster consists of lower-quality responses (KP5-KP7), retrievable with
$F1=0.52,0.45$.

We tried this approach with the KMeans as well, but the samples scattering
across fitted clusters there did not exhibit meaningful patterns.

###  5.2 RQ2: How well are the KPs represented in the embeddings?

To answer this question, we first analyzed, descriptively, the level of
similarity between the embeddings within each KP, and between KPs. We then
conducted statistical tests to verify that the observed patterns are
statistically robust.

Within KP similarity. To analyze the level of similarity within each KP, we
computed the pairwise cosine-similarity between all pairs in that KP. Tables 9
and 10 show the results, with KPs as rows and fitted clusters as columns.
Within-KP similarities are in the diagonals. Since the pairwise cosine
similarity values are not normally distributed111The two-sided Kolmogorov-
Smirnov test: test statistic = 0.5, $p<0.001$, we report medians. The results
show that KP1’s embeddings (highest quality responses) have the highest
density; as the quality of a response goes down, so does its similarity to
other responses with the same pattern of error.
Between-KP similarity. As can be further seen in Tables 9 and 10, for both
items, for every $i>1$ the embeddings of KPi responses tend to be more similar
to the embeddings of KP1 than to embeddings of their own KP (the bolded values
in the first row are the largest in each column). This means that erroneous
responses of various types are more similar to the correct responses than to
those with the same pattern of error.

KP |  1 |  2 |  3 |  4 |  5 |  6
---|---|---|---|---|---|---
1 |  .920 |  .910 |  .900 |  .899 |  .883 |  .852
2 |  |  .903 |  .896 |  .889 |  .880 |  .849
3 |  |  |  .897 |  .890 |  .883 |  .852
4 |  |  |  |  .877 |  .871 |  .837
5 |  |  |  |  |  .874 |  .845
6 |  |  |  |  |  |  .755
Table 9: Q1 pairwise cosine similarity median per KP. KP |  1 |  2 |  3 |  4 |  5 |  6 |  7
---|---|---|---|---|---|---|---
1 |  .916 |  .891 |  .896 |  .886 |  .873 |  .857 |  .837
2 |  |  .876 |  .870 |  .860 |  .854 |  .840 |  .820
3 |  |  |  .881 |  .870 |  .862 |  .844 |  .828
4 |  |  |  |  .866 |  .860 |  .843 |  .822
5 |  |  |  |  |  .861 |  .843 |  .823
6 |  |  |  |  |  |  .824 |  .796
7 |  |  |  |  |  |  |  .764
Table 10: Q2 pairwise cosine similarity median per KP.

Hypothesis testing. Next, we conducted statistical tests to confirm that i)
the distribution of the embeddings in each KP are indeed different and that
ii) the cosine similarity within each KP is correlated with the responses
quality.

i) A Kruskal-Wallis H-test confirmed that at least one of the medians for the
different KPs is significantly different from the others, for both Q1 and Q2
(Q1: $statistic=338.435,p<0.001$; Q2: $statistic=295.019,p<0.001$). A follow-
up Dunn’s post-hoc analysis indicated that the within-KPs similarities differ
significantly across all KP pairs, for both Q1 and Q2, with $p<0.001$. This
indicates that embeddings of responses from different KPs have different
distributions. Moreover, the embeddings of high-quality responses are highly
dense, while embeddings of low-quality responses are more scattered in the
vector space.

ii) To show that the cosine similarities within KPs are significantly
correlated with the responses’ quality, we calculated for every sample $x\in
KP(i)$ its cosine similarity to $KP(i)$ centroid $c(i)$, where $c(i)$ is the
average embedding component-wise of the embeddings in $KP(i)$, i.e.,

$CosSim(x,c(i))\quad\forall x\in KP(i).$

We then calculated the Spearman correlation between all the similarities
values $\cup_{i=1}^{k}\\{CosSim(x,c(i)):x\in KP(i)\\}$ where $k=6,7$ for Q1,
Q2 respectively, and the ordinal variable of the KPs’ index, where lower index
represents higher-quality responses. The Spearman correlation coefficient and
its p-values are:

$r_{Q1}=-0.686,~{}p<0.001$ $r_{Q2}=-0.633,p<0.001$

indicating a strong correlation Xiao et al. (2016) between the quality of a
‘family of responses’ (KP) and the within-family similarity.

##  6 Discussion and Conclusion

Our data consists of $669$ high-school student responses to two typical
constructed response items in high-school biology. The responses were human
graded according to an analytic rubric that is based on the Causal-Mechanical
explanation framework Ariely et al. (2023), transforming each response to a
binary vector that encodes the grading according to the rubric categories.
Previous work demonstrated that applying cluster analysis (KMeans) to these
vectors, which result from a process that applies a theoretical assessment
framework to concrete context by human experts, yields stable clusters that
reveal pedagogically meaningful knowledge profiles, which were validated in
several ways Ariely et al. (2024). (For more details, see Section 3.) We
reasoned that given the successful performance of pre-trained LLMs on a
variety of education-related meaning-intensive tasks Schleifer et al. (2023);
Wambsganss et al. (2023); Riordan et al. (2020); Sung et al. (2019), and
previous work that applied this specifically to profile discovery Martin et
al. (2023); Wulff et al. (2022), we want to evaluate whether unsupervised
profile discovery that is not aided by human knowledge works sufficiently well
to be applied out-of-the-box.

The results of RQ1 reveal that two distinct common unsupervised clustering
techniques largely failed to discover the ‘gold’ KPs from the pre-trained LLM
embeddings. Inasmuch as a weak relationship with the knowledge profiles was
exhibited by KMeans clusters (ARI of 0.12-0.19), our retrieval-based analysis
per profile showed that KP1, the profile that captures the correct responses,
was the most discoverable profile, with F1-scores of 0.60/0.67 (on Q1/Q2) for
retrieving members of KP1 using the best-aligned emergent cluster. Thus, had
the emergent clusters been used as a basis for feedback, only the correct
responses would have received pedagogically cogent feedback, since responses
belonging to low-knowledge KPs are all intermixed in the emergent clusters.
This phenomenon was consistent across two items – Q1 and Q2 – that were
analyzed separately.

In an attempt to account for both the failure of overall profile discovery
based on pre-trained LLM embeddings and for the bias towards the correct
responses exhibited by the emergent clusters, we turned ‘upstream’ to inspect
how the KPs are represented by the embeddings.

We found that the lower the knowledge level of the profile, the less similar
to each other its members are in the embeddings space. It is this property
that we refer to as the Anna Karenina principle: Analogously to Tolstoy’s
observation that happy families are similar to each other whereas each unhappy
family is unhappy in its own way, we see that the correct responses are
similar to each other, whereas incorrect responses differ more from each other
the more incorrect (’unhappy’) they are (strong correlation of
$r_{1}=-0.686,r_{2}=-0.633$ for Q1/Q2). One could say that Tolstoy considered
all unhappy families as an undifferentiated mass; presumably, if classified by
their specific source of unhappiness (by family therapists, say), profiles
would have probably emerged. In our case, the incorrect responses are grouped
by teachers according to the type of problem they exhibit; however, within-
profile similarities are still lower than those of correct responses and drift
further apart the bigger the problems. The lower density of the poor-knowledge
profiles may be one reason that inhibits their downstream discovery.

Further analysis suggests that the privileged status of ‘happy families’
(correct responses) extends beyond their higher density. We also found that
while an average correct response is most similar to another correct response,
an average incorrect response is closer in the embeddings space to a correct
response than to a member of its own profile (Tables 9 and 10). That is, in
some sense, the correct responses are the center of the universe, whereas the
incorrect responses drift around them in non-convex formations. The non-
convexity of the lower-knowledge profiles may be another inhibitor of their
downstream discoverability. Taken together, the ‘classic’ Anna Karenina
property and the strong version that puts the correct responses in the center
suggest an explanation for both the overall discovery failure observed
downstream and for the bias in favor of correct responses exhibited by the
emergent clusters.

Based on our results, pre-trained representations may not lend themselves to
making the necessary distinctions to support pedagogical decisions such as
providing formative feedback that targets specific errors in student
reasoning. In particular, our results show a case where the representations
are not sufficiently nuanced to allow commonly used clustering methods to
identify any error-based profiles, only the profile of the correct responses.
Since it is the students who gave the incorrect responses who are in most need
of targeted formative feedback, the bias in favor of correct responses is
especially counter-productive. Thus, our results tell a cautionary tale about
using emergent properties of student response data built over pre-trained
embeddings without domain- and task-specific tuning, and without human
supervision.

###  6.1 Limitations

It is possible that other clustering approaches could have revealed clusters
that are more similar to the ‘gold’ ones. However, given that despite the
large difference between KMeans and HDB SCAN’s algorithmic approach, they were
quite consistent in both demonstrating poor overall agreement and being biased
towards discovering the best KP, we believe that reaching results that are
qualitatively different from another clustering method is unlikely. It is also
possible that emergent clusters do correspond to an alternative meaningful
partition of the responses into groups, but that partition is not what
educators see when they analyze student responses.

The AlephBERT model used in this paper is state-of-the-art for Hebrew, but it
has a smaller number of parameters compared to the most recent LLMs for
English. It is possible that with more advanced LLM technology, the LLM
representations of student responses will be more nuanced; we will revisit our
analyses with larger Hebrew LLMs when available.

Due to the monolingual nature of our current data, we have experimented with
one language only. Work is underway to collect comparable student response
data in Arabic.

## Ethics statement

We acknowledge that the work is conformant with the ACL Code of Ethics. The
research and its data collection procedures were approved by the Institutional
Review Board and the Ministry of Education. The instrument was administered to
the students as part of the regular instruction of the topic, based on the
teachers’ decision to use it as part of the teaching routine (the instrument
was published in teachers’ forums), with teacher and school principal approval
that response data will be used for research.

The goal of this research is to better understand the relations between pre-
trained LLM-based representations of student responses to open-ended questions
in science, and representations of these responses according to theory-driven
rubrics applied by human experts. We study to what extent
conceptually/pedagogically similar responses tend to maintain their proximity
in the embedding space as well, and the impact of deviations from this
property on downstream analysis. What makes this especially relevant to Ethics
is our finding that the weaker students are the ones whose responses suffer
the most from representation mismatches between the two representation spaces.
This limits the ability to automatically cater to these students – the ones
who are in the highest need for personalized guidance – with formative
feedback that matches the gaps in their reasoning. By identifying and naming
this phenomenon (‘the Anna Karenina principle’ in automated short answer
evaluation), we hope to start a discussion on the means to both estimate its
prevalence and to address it.

We demonstrate the Anna Karenina principle on two tasks with one pre-trained
model. It is possible that results will look different with other tasks and
other large language models. There is a potential danger of over-
generalization based on our results, whereby large language models, as a
species, so to speak, would be thought to suffer from the Anna Karenina
principle and their off-the-shelf use would be avoided in learner-focused
applications. This, in turn, could hamper development of useful LLM-based
applications to support learners. We believe that the best course of action is
to continue the study of the principle in order to improve our understanding
of what kind of models are likely to exhibit the problem and for what kind of
task, as well as how to diagnose and correct it, ideally without recourse to a
large human-tagged dataset. In parallel, future ethics-focused research could
investigate whether weaker learners should be a protected category in
educational applications, akin to demographic categories like race or gender,
by investigating evidence of harm differentially wrought on such learners
through technology that does not cater sufficiently precisely to their needs.

Data from this research cannot be shared publicly due to privacy regulations,
but may be provided for research purposes, along with its analysis code,
subject to the necessary approvals.

## Acknowledgments

This study was partially supported by the Israeli Science Foundation (ISF)
grant number 851/22.

## References

  * Andersen et al. (2023) Nico Andersen, Fabian Zehner, and Frank Goldhammer. 2023.  Semi-automatic coding of open-ended text responses in large-scale assessments.  _Journal of Computer Assisted Learning_ , 39(3):841–854.
  * Ariely et al. (2022) Moriah Ariely, Tanya Nazaretsky, and Giora Alexandron. 2022.  Personalized automated formative feedback can support students in generating causal explanations in biology.  In _Proceedings of the 16th International Conference of the Learning Sciences-ICLS 2022, pp. 953-956_. International Society of the Learning Sciences.
  * Ariely et al. (2023) Moriah Ariely, Tanya Nazaretsky, and Giora Alexandron. 2023.  Machine learning and Hebrew NLP for automated assessment of open-ended questions in biology.  _International Journal of Artificial Intelligence in Education_ , 33(1):1–34.
  * Ariely et al. (2024) Moriah Ariely, Tanya Nazaretsky, and Giora Alexandron. 2024.  Causal-mechanical explanations in biology: Applying automated assessment for personalized learning in the science classroom.  _Journal of Research in Science Teaching_.
  * Baffour et al. (2023) Perpetual Baffour, Tor Saxberg, and Scott Crossley. 2023.  Analyzing bias in large language model solutions for assisted writing feedback tools: Lessons from the feedback prize competition series.  In _Proceedings of the 18th Workshop on Innovative Use of NLP for Building Educational Applications (BEA 2023)_ , pages 242–246.
  * Bender et al. (2021) Emily M Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell. 2021.  On the dangers of stochastic parrots: Can language models be too big?  In _Proceedings of the 2021 ACM conference on Fairness, Accountability, and Transparency_ , pages 610–623.
  * Bovo et al. (2013) Angela Bovo, Stéphane Sanchez, Olivier Héguy, and Yves Duthen. 2013.  Clustering moodle data as a tool for profiling students.  In _2013 Second international conference on E-Learning and E-Technologies in education (ICEEE)_ , pages 121–126. IEEE.
  * Caliskan et al. (2017) Aylin Caliskan, Joanna J Bryson, and Arvind Narayanan. 2017.  Semantics derived automatically from language corpora contain human-like biases.  _Science_ , 356(6334):183–186.
  * Cao et al. (2022) Yang Trista Cao, Yada Pruksachatkun, Kai-Wei Chang, Rahul Gupta, Varun Kumar, Jwala Dhamala, and Aram Galstyan. 2022.  On the intrinsic and extrinsic fairness evaluation metrics for contextualized language representations.  In _Proceedings of the ACL_ , pages 561–570.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv:1810.04805_.
  * Fellows (1994) Nancy J Fellows. 1994.  A window into thinking: Using student writing to understand conceptual change in science learning.  _Journal of Research in Science Teaching_ , 31(9):985–1001.
  * Gerard and Linn (2016) Libby F Gerard and Marcia C Linn. 2016.  Using automated scores of student essays to support teacher guidance in classroom inquiry.  _Journal of Science Teacher Education_ , 27(1):111–129.
  * Goldfarb-Tarrant et al. (2021) Seraphina Goldfarb-Tarrant, Rebecca Marchant, Ricardo Muñoz Sánchez, Mugdha Pandya, and Adam Lopez. 2021.  Intrinsic bias metrics do not correlate with application bias.  In _Proceedings of the ACL_ , pages 1926–1940.
  * Goldfarb-Tarrant et al. (2023) Seraphina Goldfarb-Tarrant, Eddie Ungless, Esma Balkir, and Su Lin Blodgett. 2023.  This prompt is measuring <mask>: evaluating bias evaluation in language models.  In _Findings of the ACL_ , pages 2209–2225.
  * Hattie and Timperley (2007) John Hattie and Helen Timperley. 2007.  The power of feedback.  _Review of Educational Research_ , 77(1):81–112.
  * Hubert and Arabie (1985) Lawrence Hubert and Phipps Arabie. 1985.  Comparing partitions.  _Journal of Classification_ , pages 193–218.
  * Kaneko et al. (2022) Masahiro Kaneko, Danushka Bollegala, and Naoaki Okazaki. 2022.  Debiasing isn’t enough! – on the effectiveness of debiasing MLMs and their social biases in downstream tasks.  In _Proceedings of COLING_ , pages 1299–1310.
  * Kumar et al. (2019) Yaman Kumar, Swati Aggarwal, Debanjan Mahata, Rajiv Ratn Shah, Ponnurangam Kumaraguru, and Roger Zimmermann. 2019.  Get IT scored using AutoSAS — an automated system for scoring short answers.  In _Proceedings of AAAI_ , pages 9662–9669.
  * Le Quy et al. (2023) Tai Le Quy, Gunnar Friege, and Eirini Ntoutsi. 2023.  A review of clustering models in educational data science toward fairness-aware learning.  In Alejandro Peña-Ayala, editor, _Educational Data Science: Essentials, Approaches, and Tendencies: Proactive Education based on Empirical Big Data Evidence_ , pages 43–94. Springer Nature Singapore, Singapore.
  * Li et al. (2023) Tingting Li, Emily Reigh, Peng He, and Emily Adah Miller. 2023.  Can we and should we use artificial intelligence for formative assessment in science?  _Journal of Research in Science Teaching_ , 60(6):1385–1389.
  * Li et al. (2021) Zhaohui Li, Yajur Tomar, and Rebecca J. Passonneau. 2021.  A semantic feature-wise transformation relation network for automatic short answer grading.  In _Proceedings of EMNLP_ , pages 6030–6040.
  * Lloyd (1982) Stuart Lloyd. 1982.  Least squares quantization in PCM.  _IEEE Transactions on Information Theory_ , 28(2):129–137.
  * Manning (1999) H. Manning, C. D. Schutze. 1999.  _Foundations of statistical natural language processing_.  MIT Press.
  * Martin et al. (2023) Paul P Martin, David Kranz, Peter Wulff, and Nicole Graulich. 2023.  Exploring new depths: Applying machine learning for the analysis of student argumentation in chemistry.  _Journal of Research in Science Teaching_.
  * Masala et al. (2021) Mihai Masala, Stefan Ruseti, Mihai Dascalu, and Ciprian Dobre. 2021.  Extracting and clustering main ideas from student feedback using language models.  In _Proceedings of AIED_ , pages 282–292. Springer.
  * McInnes et al. (2017) Leland McInnes, John Healy, and Steve Astels. 2017.  hdbscan: Hierarchical density based clustering.  _The Journal of Open Source Software_ , 2(11).
  * Mizumoto et al. (2019) Tomoya Mizumoto, Hiroki Ouchi, Yoriko Isobe, Paul Reisert, Ryo Nagata, Satoshi Sekine, and Kentaro Inui. 2019.  Analytic score prediction and justification identification in automated short answer scoring.  In _Proceedings of the 14th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 316–325.
  * Nehm and Haertig (2012) Ross H Nehm and Hendrik Haertig. 2012.  Human vs. computer diagnosis of students’ natural selection knowledge: testing the efficacy of text analytic software.  _Journal of Science Education and Technology_ , 21:56–73.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830.
  * Rastrollo-Guerrero et al. (2020) Juan L Rastrollo-Guerrero, Juan A Gómez-Pulido, and Arturo Durán-Domínguez. 2020.  Analyzing and predicting students’ performance by means of machine learning: A review.  _Applied Sciences_ , 10(3):1042.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings Using Siamese BERT-Networks.  In _Proceedings of EMNLP_ , pages 3982–3992.
  * Riordan et al. (2020) Brian Riordan, Sarah Bichler, Allison Bradford, Jennifer King Chen, Korah Wiley, Libby Gerard, and Marcia C. Linn. 2020.  An empirical investigation of neural methods for content scoring of science explanations.  In _Proceedings of the 15th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 135–144.
  * Salmon (2006) Wesley C Salmon. 2006.  _Four decades of scientific explanation_.  University of Pittsburgh press.
  * Schleifer et al. (2023) Abigail Gurin Schleifer, Beata Beigman Klebanov, Moriah Ariely, and Giora Alexandron. 2023.  Transformer-based Hebrew NLP models for short answer scoring in biology.  In _Proceedings of the 18th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 550–555.
  * Seker et al. (2022) Amit Seker, Elron Bandel, Dan Bareket, Idan Brusilovsky, Refael Greenfeld, and Reut Tsarfaty. 2022.  Alephbert: Language model pre-training and evaluation from sub-word to sentence level.  In _Proceedings of the ACL_ , pages 46–56.
  * Suárez et al. (2020) Pedro Javier Ortiz Suárez, Laurent Romary, and Benoît Sagot. 2020.  A monolingual approach to contextualized word embeddings for mid-resource languages.  In _Proceedings of the ACL_ , pages 1703–1714.
  * Sung et al. (2019) Chul Sung, Tejas Indulal Dhamecha, and Nirmal Mukhi. 2019.  Improving short answer grading using transformer-based pre-training.  In _Proceedings of AIED_ , pages 469–481.
  * Tansomboon et al. (2017) Charissa Tansomboon, Libby F Gerard, Jonathan M Vitale, and Marcia C Linn. 2017.  Designing automated guidance to promote productive revision of science explanations.  _International Journal of Artificial Intelligence in Education_ , 27:729–757.
  * Toulmin (2003) Stephen E Toulmin. 2003.  _The uses of argument_.  Cambridge University Press.
  * Vinh et al. (2009) Nguyen Xuan Vinh, Julien Epps, and James Bailey. 2009.  Information theoretic measures for clusterings comparison: Is a correction for chance necessary?  In _Proceedings of ICML_ , pages 1073–1080.
  * Wambsganss et al. (2023) Thiemo Wambsganss, Xiaotian Su, Vinitra Swamy, Seyed Neshaei, Roman Rietsche, and Tanja Käser. 2023.  Unraveling Downstream Gender Bias from Large Language Models: A Study on AI Educational Writing Assistance.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 10275–10288.
  * Wulff et al. (2022) Peter Wulff, David Buschhüter, Andrea Westphal, Lukas Mientus, Anna Nowak, and Andreas Borowski. 2022.  Bridging the gap between qualitative and quantitative assessment in science education research with machine learning—a case for pretrained language models-based clustering.  _Journal of Science Education and Technology_ , 31(4):490–513.
  * Xiao et al. (2016) Chengwei Xiao, Jiaqi Ye, Rui Máximo Esteves, and Chunming Rong. 2016.  Using spearman’s correlation coefficients for exploratory data analysis on big dataset.  _Concurrency and Computation: Practice and Experience_ , 28(14):3866–3878.

## Appendix 1

Item |  Text
---|---
Smoking item |  The smoke from cigarettes contains several harmful substances, including the gas carbon-monoxide (CO). CO is released from cigarettes while smoking, and has a stronger tendency than oxygen to bind to Hemoglobin. Explain how high levels of CO make it difficult for smokers to exercise.
Anemia item |  A person was found to have low levels of red blood cells in his blood test (anemia). This person complained to his doctor about weakness and difficulty to exercise. Explain how low levels of red blood cells make it difficult for people with anemia to exercise.
Table 11: The constructed response items (reproduced from Ariely et al. (2024); original responses are in Hebrew).  Cluster description |  Exemplifying response
---|---
Full explanations: All/most of the conceptual components and the underlying causal relations are present. |  “Red blood cells bind oxygen and transfer it in the bloodstream, from the lungs where it is absorbed, to all the cells of the body. A low amount of red blood cells in the body leads to the transfer of less oxygen to the body’s cells. Since oxygen is one of the reactants in the process of cellular respiration - the energy production process, less oxygen reaching the cells leads to damage to this process. Thus, less available energy is produced in the body’s cells and this impairs their function, which leads to fatigue and difficulty in performing physical activity.” (Anemia item)
Gaps in causal connections: All/most of the conceptual components are present, but all/most of the causal relations are missing. |  “The CO binds to the red blood cell instead of the oxygen and thus oxygen does not reach the cells of the body and then cellular respiration does not occur and the body cannot produce energy and thus it stops physical activity due to lack of energy.” (Smoking item)
Specific sequential stages are missing and causal relations are often missing. |  “CO gas is known to bind to Hemoglobin with a stronger tendency than oxygen. When CO binds to Hemoglobin, it takes the oxygen’s place, so much less oxygen is transported from place to place and enters the cells. Lack of oxygen in the cells leads to less production of ATP molecules. Since energy is required for physical exercise, the result is that the person gets tired quickly and has difficulty exercising.” (Smoking item)
Many sequential stages are missing and causal relations are often missing as well. |  “Red blood cells carry the oxygen (because of Hemoglobin). When there is anemia, then there is a low amount of red blood cells and thus a low amount of oxygen reaches the muscles.” (Anemia item)
No explanation: All/most of the sequential stages and the underlying causal relations are missing/irrelevant responses. |  “I don’t know”
“Anemic people are tired because they have few red blood cells.” (Anemia item)
Table 12: Examples of student responses and their classification into the KPs
that were derived from the expert scoring according to the theory-driven
rubric (reproduced from Ariely et al. (2024); original responses are in
Hebrew).


2n}e^{-i\sum_{ij}J_{ij}\sigma^{(i)}_{z}\tau^{(j)}_{z}t/n}\sum_{\mathbf{w}^{\sigma}\in\\{0,1\\}^{n}}\ket{\mathbf{w}^{\sigma}}\otimes\sum_{\mathbf{w}^{\tau}\in\\{0,1\\}^{n}}(-1)^{\operatorname{wt}(\mathbf{w}^{\tau})}\ket{\mathbf{w}^{\tau}}$
$\displaystyle=\frac{1}{\sqrt{2}^{2n}}\sum_{\begin{subarray}{c}\mathbf{w}^{\sigma}\in\\{0,1\\}^{n}\\\
\mathbf{w}^{\tau}\in\\{0,1\\}^{n}\end{subarray}}(-1)^{\operatorname{wt}(\mathbf{w}^{\tau})}e^{-i\sum_{ij}J_{ij}/n(1-2w^{\sigma}_{i})(1-2w^{\tau}_{j})t}\langle\mathbf{x}^{\sigma}\mathbf{x}^{\tau}|H^{\otimes
2n}\ket{\mathbf{w}^{\sigma}\mathbf{w}^{\tau}}.$ (109)

From

$\displaystyle\langle\mathbf{x}^{\sigma}\mathbf{x}^{\tau}|H^{\otimes
2n}\ket{\mathbf{w}^{\sigma}\mathbf{w}^{\tau}}$
$\displaystyle=\frac{1}{\sqrt{2}^{2n}}\sum_{\mathbf{y}^{\sigma}\in\\{0,1\\}^{n}}\sum_{\mathbf{y}^{\tau}\in\\{0,1\\}^{n}}(-1)^{\mathbf{x}^{\sigma}\cdot\mathbf{y}^{\sigma}+\mathbf{x}^{\tau}\cdot\mathbf{y}^{\tau}}\delta_{\mathbf{y}^{\sigma},\mathbf{w}^{\sigma}}\delta_{\mathbf{y}^{\tau},\mathbf{w}^{\tau}}$
$\displaystyle=\frac{1}{\sqrt{2}^{2n}}(-1)^{\mathbf{w}^{\sigma}\cdot\mathbf{x}^{\sigma}+\mathbf{w}^{\tau}\cdot\mathbf{x}^{\tau}},$
(110)

we obtain

$\displaystyle f(\mathbf{x};J;t)$
$\displaystyle=\frac{1}{2^{2n}}\sum_{\begin{subarray}{c}\mathbf{w}^{\sigma}\in\\{0,1\\}^{n}\\\
\mathbf{w}^{\tau}\in\\{0,1\\}^{n}\end{subarray}}(-1)^{\operatorname{wt}(\mathbf{w}^{\tau})+\mathbf{w}^{\sigma}\cdot\mathbf{x}^{\sigma}+\mathbf{w}^{\tau}\cdot\mathbf{x}^{\tau}}e^{-i\sum_{ij}J_{ij}/n(1-2y^{\sigma}_{i})(1-2y^{\tau}_{j})t}.$
(111)

Then, the output probability is given by

$\displaystyle p(\mathbf{x};J;t)$
$\displaystyle=f(\mathbf{x};J;t)f(\mathbf{x};J;t)^{*}$
$\displaystyle=\frac{1}{2^{4n}}\sum_{\begin{subarray}{c}\mathbf{w}^{\sigma}\in\\{0,1\\}^{n}\\\
\mathbf{w}^{\tau}\in\\{0,1\\}^{n}\end{subarray}}\sum_{\begin{subarray}{c}\mathbf{z}^{\sigma}\in\\{0,1\\}^{n}\\\
\mathbf{z}^{\tau}\in\\{0,1\\}^{n}\end{subarray}}(-1)^{\operatorname{wt}(\mathbf{w}^{\tau})+\mathbf{w}^{\sigma}\cdot\mathbf{x}^{\sigma}+\mathbf{w}^{\tau}\cdot\mathbf{x}^{\tau}+\operatorname{wt}(\mathbf{z}^{\tau})+\mathbf{z}^{\sigma}\cdot\mathbf{x}^{\sigma}+\mathbf{z}^{\tau}\cdot\mathbf{x}^{\tau}}$
$\displaystyle\qquad\qquad\times
e^{-i\sum_{ij}J_{ij}/n[(1-2w^{\sigma}_{i})(1-2w^{\tau}_{j})-(1-2z^{\sigma}_{i})(1-2z^{\tau}_{j})]t}.$
(112)

We now assume that $\\{J_{ij}\\}$ is rationally independent, i.e.,

$\displaystyle\sum_{ij}J_{ij}a_{ij}=0\text{ for }a_{ij}\in\mathbb{Z},\text{
iff }a_{ij}=0\text{ for all }i,j.$ (113)

This condition is satisfied for a randomly chosen $J_{ij}$.

Then, it follows that

$\displaystyle\lim_{T\rightarrow\infty}\frac{1}{T}\int_{0}^{T}dte^{-i\sum_{ij}J_{ij}/n[(1-2w^{\sigma}_{i})(1-2w^{\tau}_{j})-(1-2z^{\sigma}_{i})(1-2z^{\tau}_{j})]t}=\begin{cases}1\text{
if }\mathbf{w}=\mathbf{z}\text{ or }\mathbf{w}=\overline{\mathbf{z}}\\\
0\text{ otherwise}\end{cases},$ (114)

where $\overline{\mathbf{z}}=\\{1-z_{i}\\}$ is a vector after taking binary
complement for each component of $\mathbf{z}$.

We now take the time average of $p(\mathbf{x};J;t)$, which yields

$\displaystyle\overline{p}(\mathbf{x};J)$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{1}{T}\int_{0}^{T}dtp(\mathbf{x};J;t)$
$\displaystyle=\frac{1}{2^{4n}}\Biggl{[}\sum_{\begin{subarray}{c}\mathbf{w}^{\sigma}\in\\{0,1\\}^{n}\\\
\mathbf{w}^{\tau}\in\\{0,1\\}^{n}\end{subarray}}(-1)^{2\operatorname{wt}(\mathbf{w}^{\tau})+2\mathbf{w}^{\sigma}\cdot\mathbf{x}^{\sigma}+2\mathbf{w}^{\tau}\cdot\mathbf{x}^{\tau}}+\sum_{\begin{subarray}{c}\mathbf{w}^{\sigma}\in\\{0,1\\}^{n}\\\
\mathbf{w}^{\tau}\in\\{0,1\\}^{n}\end{subarray}}(-1)^{\operatorname{wt}(\mathbf{w}^{\tau})+\mathbf{w}^{\sigma}\cdot\mathbf{x}^{\sigma}+\mathbf{w}^{\tau}\cdot\mathbf{x}^{\tau}+\operatorname{wt}(\overline{\mathbf{w}}^{\tau})+\overline{\mathbf{w}}^{\sigma}\cdot\mathbf{x}^{\sigma}+\overline{\mathbf{w}}^{\tau}\cdot\mathbf{x}^{\tau}}\Biggr{]}$
$\displaystyle=\frac{1}{2^{2n}}\Biggl{[}1+(-1)^{n+\operatorname{wt}(\mathbf{x}^{\sigma})+\operatorname{wt}(\mathbf{x}^{\tau})}\Biggr{]}=\frac{1}{2^{2n}}\Biggl{[}1+(-1)^{n+\operatorname{wt}(\mathbf{x})}\Biggr{]},$
(115)

where we have used
$\operatorname{wt}(\mathbf{w}^{\tau})+\operatorname{wt}(\overline{\mathbf{w}}^{\tau})=|\mathbf{w}^{\tau}|=n$
(and the same for $\mathbf{w}^{\sigma}$) and
$\mathbf{w}^{\tau}\cdot\mathbf{x}^{\tau}+\overline{\mathbf{w}}^{\tau}\cdot\mathbf{x}^{\tau}=\mathbf{1}^{\tau}\cdot\mathbf{x}^{\tau}=\operatorname{wt}(\mathbf{x}^{\tau})$
(and the same for $\mathbf{x}^{\sigma}$).

The final expression implies that $p(\mathbf{x};J;t)$ converges to $2\times
2^{-2n}$ or $0$ as $t$ goes to infinity, depending on the Hamming weight of
$\mathbf{x}$. In addition, the converged values do not depend on $J_{ij}$.
Given that $\mathbf{x}\in X$ has the Hamming weight of $n$, we know that
$p(\mathbf{x};J;t)$ converges to $2\times 2^{-2n}$, which is consistent with
the numerical observation from the previous subsection.

We finally note that this convergence behavior also supports anticoncentration
as it implies that the probability distribution, $p(\mathbf{x};J;t)$, after an
equilibration time, $t_{\rm eq}$, only fluctuates near $2\times 2^{-2n}$
regardless of $J$ and $\mathbf{x}$.

##  Appendix H Estimating the number of required gates for the XY model

In the main text, we presented the number of gates required to simulate the XY
model. For $n=100$ and $t_{0}=5\log(n)\approx 23.03$, we estimated that the
number of required gates is between around $10^{8}$ to $10^{9}$ depending on
the target Trotter error. This appendix provides detailed steps on how these
estimations are obtained.

Our main tool is the following inequality:

$\displaystyle\Biggl{\|}\exp\biggl{[}-it_{0}\sum_{ij}\frac{J_{ij}}{2n}\Bigl{(}\sigma^{(i)}_{x}\tau^{(j)}_{x}+\sigma^{(i)}_{y}\tau^{(j)}_{y}\Bigr{)}\biggr{]}-\mathcal{T}_{2}^{M}\biggr{]}\Biggr{\|}\leq\mathcal{O}\left[M\Bigl{(}\sum_{ij}\frac{|J_{ij}|}{n}\frac{t_{0}}{M}\Bigr{)}^{3}\right],$

where $\mathcal{T}_{2}$ is the expression obtained by applying the second-
order Suzuki–Trotter formula for each Trotter step (for a timestep of
$t_{0}/M$). Thus, $\mathcal{T}_{2}$ can be implemented using a quantum circuit
with $2n^{2}$ gates.

When $n$ is sufficiently large, we can change $\sum_{ij}|J_{ij}|$ to its
average value given by $n^{2}\sqrt{2/\pi}$. The total Trotter error is then
approximated by $\epsilon_{t}\approx P\frac{n^{3}t_{0}^{3}}{M^{2}}$ where $P$
is a pre-factor. The prefactor $P$ is estimated to $\approx 2.97\times
10^{-4}$ by computing the distance (measured w.r.t. the operator norm) between
the unitary operator, $e^{-iHt}$, and the Trotterized expression,
$\mathcal{T}_{2}^{M}$, for $n=5$.

Using this value of $P$, results for $n=100$ are extrapolated. For the target
Trotter error $\epsilon_{t}$, the number of gates is estimated as

$\displaystyle\\#(\text{gates})=2n^{2}M=2n^{2}\sqrt{\frac{Pn^{3}t_{0}^{3}}{\epsilon_{t}}}.$
(116)

By entering $P\approx 2.97\times 10^{-4}$, $n=10^{2}$, and $t_{0}\approx
23.03$, we obtained the number of gates $1.2\times 10^{8}$, $3.8\times
10^{8}$, and $1.2\times 10^{9}$ for $\epsilon_{t}=10^{-1}$, $10^{-2}$, and
$10^{-3}$, respectively.


P 3020 11institutetext:  1Pattern Recognition Lab, Department of Computer
Science, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany
2R & D Projects, EUROIMMUN Medizinische Labordiagnostika AG
3Institute of Veterinary Pathology, Freie Universität Berlin, Germany
4Equine Clinic, Freie Universität Berlin, Berlin, Germany
5Technische Hochschule Ingolstadt, Ingolstadt, Germany

# Learning to be EXACT

Cell Detection for Asthma on Partially Annotated Whole Slide Images

Christian Marzahl1,2 Christof A. Bertram3 Frauke Wilm1 Jörn Voigt2 Ann K.
Barton4 Robert Klopfleisch3 Katharina Breininger1 Andreas Maier1 Marc
Aubreville5<EMAIL_ADDRESS>
###### Abstract

Asthma is a chronic inflammatory disorder of the lower respiratory tract and
naturally occurs in humans and animals including horses. The annotation of an
asthma microscopy whole slide image (WSI) is an extremely labour-intensive
task due to the hundreds of thousands of cells per WSI. To overcome the
limitation of annotating WSI incompletely, we developed a training pipeline
which can train a deep learning-based object detection model with partially
annotated WSIs and compensate class imbalances on the fly. With this approach
we can freely sample from annotated WSIs areas and are not restricted to fully
annotated extracted sub-images of the WSI as with classical approaches. We
evaluated our pipeline in a cross-validation setup with a fixed training set
using a dataset of six equine WSIs of which four are partially annotated and
used for training, and two fully annotated WSI are used for validation and
testing. Our WSI-based training approach outperformed classical sub-image-
based training methods by up to 15% $mAP$ and yielded human-like performance
when compared to the annotations of ten trained pathologists.

##  1 Introduction

Asthma is a chronic inflammatory disorder of the lower respiratory tract and
can occur in multiple species. While asthma can affect humans, horses can also
suffer from asthma and are often used as models for human disease [1] due to
their similar symptoms and pathogenesis. The gold standard for diagnosis of
equine and human asthma is to collect bronchoalveolar lavage fluid (BALF) and
to examine the sample under a microscope or on digitised whole slide images
(WSIs). Asthma and other pulmonary disorders are diagnosed based on the
relative proportion of different cell types including eosinophils, mast cells,
neutrophils, macrophages and lymphocytes. This typically requires manual
counting of 300-500 cells and is therefore time-consuming and strenuous for
the pathologist [2]. Therefore, automatic solutions that support this task are
of high interest. Although asthma is a common disease in horses and humans, to
the author’s knowledge there is no trained model or method published analysing
asthma on WSI automatically. For the development of machine learning
algorithms, huge annotated datasets are generally required. A particular
challenge for the annotation process of asthma is the large number of cells
per WSI, which can easily reach hundreds of thousands. This makes the
annotation process very labour-intensive and time-consuming. In order to
increase the efficiency of the annotation process, expert-algorithm
collaboration can be used where experts enhance pre-computed annotations of a
trained model. Marzahl et al.[2] showed this for mitotic figures or pulmonary
haemorrhage. An alternative option is to annotate multiple WSIs only partially
to capture the domain variability between WSIs, and train a network to
complete the annotation. On the one hand, training deep learning-based methods
on partially annotated WSIs faces some additional challenges regarding
tracking annotated WSI areas and leads to higher demands on the coordination
and synchronisation between the participating institutes. On the other hand,
training on partially annotated data simplifies training pipelines in terms of
data augmentation and live patch sampling in contrast to extracted sub-image-
based approaches. Nevertheless, sub-image-based approaches, where patches from
the WSI have to be extracted before the training, are the only supported
method for the most prominent object detection frameworks [3] and are used in
multiple WSI-based detection applications [4, 5].

As the main contribution to the field of deep learning-based cytological WSI
analysis, we propose a training pipeline to train object detection models with
live sampling on partially annotated WSIs. Additionally, we create a baseline
with a state-of-the-art deep learning-based object detection model for
detecting five types of cells on WSIs. All code to train, evaluate, test our
models and to reproduce our results for public is accessible at GitHub
111https://github.com/ChristianMarzahl/Asthma_WSI. Furthermore, the WSIs can
be accessed at reasonable request from the corresponding author.

##  2 Material and methods

The dataset consists of six cytological samples (Table 1) of equine BALF which
were cytocentrifugated and stained using May-Grunwald Giemsa stain.
Afterwards, the glass slides were digitized using a linear scanner (Aperio
ScanScope CS2, Leica Biosystems, Germany) at a magnification of 400$\times$
with a resolution of $0.25\leavevmode\nobreak\ \frac{\mu m}{px}$. Finally, two
slides were completely annotated and the remaining four partially annotated by
a veterinary pathologist. Twenty patches from the same six WSI have been used
in a recent study [2] to investigate the annotation accuracy from ten trained
pathologist. We exclude these twenty patches from training to compare the
accuracy of human experts with our algorithmic approach.

Figure 1: Left: visualisation of the annotated regions/cells of the included slides. Center: visualisation of the 16 traditional fully annotated sub-images for sampling in green and 624 cell-based sampling positions for our live sampling approach within the red area. To prevent sampling from unannotated WSI areas, the red area is restricted to half of the patch size to the annotation border. Right: The ground truth (GT) and the deep learning based predictions; neutrophils (red), eosinophils (green), lymphocytes(̃blue), macrophages (yellow), mast cells (purple). Table 1: Overview of the dataset including the file id, the number of cells per type and the screened sample area. The top two rows represent the completely annotated validation and test slides for the cross validation with a fixed train set. id | eosinophils | mast cells | neutrophils | macrophages | lymphocytes | total | screened image
---|---|---|---|---|---|---|---
1 | 21 | 511 | 3301 | 3934 | 14846 | 22613 | 100%
2 | 47 | 762 | 951 | 16748 | 10342 | 28850 | 100%
3 | 10 | 69 | 1321 | 3081 | 15666 | 20147 | 8%
4 | 20 | 37 | 2467 | 729 | 2144 | 5397 | 28%
5 | 8 | 116 | 4491 | 1639 | 3077 | 9331 | 43%
6 | 2 | 40 | 26 | 370 | 323 | 761 | 1%
| 108 | 1535 | 12557 | 26501 | 46398 | 87099 | 46%

###  2.1 Label generation and training pipeline

The dataset containing only six WSIs appears to be comparably small. However,
the cells in the WSIs are annotated by experts and subdivided into five
classes using SlideRunner [6], rendering it one of the largest manually
annotated cytology datasets to date. The dataset displays an extreme class
imbalance, with the rarest class of eosinophils representing only 0.12% of all
annotations. A particular challenge for training neuronal networks emerges
from the sparse annotation of four WSIs, as shown in the column "screened" in
table 1. To meet this challenge of partially annotated WSIs, we apply an
online training approach using the open-source online annotation platform
EXACT [7]. EXACT supports a persistent screening mode that allows experts to
screen WSIs in a self-determined resolution. By reusing the information this
screening mode provides, we are able to track exactly which areas of the slide
have already been annotated by the expert and can download them into the
training process via the provided REST-API.

We propose the following online training pipeline for equine asthma. As a
first step, screened areas of the slides and associated annotations are
downloaded from the EXACT server via the REST-API. The training pipeline is
then initialised with the downloaded information, the network architecture and
the loss function. During training, new patches are sampled live from the WSI
according to the patch selection and sampling strategy described in the
following sections and are restricted by information about the screened area
provided by EXACT. The trained models can be applied to new data and the
results can be synchronised with the server for expert review.

###  2.2 Live patch selection and sampling strategy

To counteract the described class imbalance and partial annotations, we
propose the following sampling strategy which uses annotated cells as seeds
for training patches: Each training patch has a cell that was manually
annotated by an expert in its center. Consequently, only cells that have at
least a distance of half of the patch size to the border of the annotated
region can be used as patch centers (red area in Figure 1). Each training
batch contains at least five patches with each of the five cell types
represented as patch center cell. The center cells within each class are
randomly chosen from the annotations. If the training batch size is chosen
larger than the number of cell types, a new cell type is randomly selected
with a probability proportional to $1-p_{k}$ where $p_{k}$ is the relative
class frequency of each cell type until the required batch size is reached.
This results in a sampling strategy which can freely choose the sampled
patches and reduces the possibility of sampling a given region repeatedly.
This is highly desirable to counter overfitting and works as an advanced
augmentation technique.

For comparison we extract all available fully annotated areas as sub-images of
the WSIs to simulate a traditional training pipeline. This results in a total
of 1862 sub-images of which 851 belong to the two fully annotated test WSIs.
Example sub-images are visualised in Figure 1 on the right with green
rectangles. For training the same cell type-based sampling strategy to
counteract the described class imbalance is applied.

###  2.3 Object detection methods

Since the training strategy itself is the main contribution of this work, we
use a publicly available and for cytology optimised implementation [8] of the
successful RetinaNet [9] architecture. Different ResNet-variants [10]
(ResNet-18, -34, -50) pretrained on ImageNetare applied as backbone networks
with appropriate mini-batch sizes. The networks are trained using the sub-
images-based and the proposed live sampling-based approach with a patch size
of 1024$\times$1024 px. Each of the two fully annotated WSIs (Table 1) are
used once as the validation set and once as the test set while keeping the
training set static to allow for a form of cross-validation given the limited
amount of cases. During training, data augmentation (rotation between zero and
90 degrees, horizontal and vertical flips, random increase or decrease of
intensity in the range of -20 to +20%) is applied and the networks are trained
until convergence on the validation set. The initial learning rate is set to
1e-3 and reduced to 1e-4 and 1e-5 if the validation loss doesn’t decrease for
three epochs. One epoch consists of 500 training patches regardless of the
WSI-based sampling mode or the extracted sub-images. The object detection
accuracy is measured as mean Average Precision (mAP) according to the 2007
PASCAL VOC challenge.

##  3 Results

Table 2: The mean average precision for the five types of cells in respect to the number of layers used for the ResNet backbone network (BB) and batch size (BS). The modes represent our method working on partially annotated WSIs and a classical approach with extracted sub-images. mode | BB | BS | eosinophils | mast cell | neutrophils | macrophages | lymphocytes | $\varnothing$
---|---|---|---|---|---|---|---|---
ours | 18 | 16 | 0.93 | 0.85 | 0.88 | 0.89 | 0.81 | 0.87
sub-image | 18 | 16 | 0.69 | 0.72 | 0.68 | 0.80 | 0.71 | 0.72
ours | 34 | 16 | 0.91 | 0.86 | 0.90 | 0.89 | 0.78 | 0.87
sub-image | 34 | 16 | 0.70 | 0.71 | 0.68 | 0.80 | 0.72 | 0.72
ours | 50 | 6 | 0.92 | 0.80 | 0.90 | 0.89 | 0.81 | 0.86
sub-image | 50 | 6 | 0.72 | 0.69 | 0.68 | 0.81 | 0.75 | 0.73

Independent of the backbone model or batch size, the accuracy of our WSI-based
sampling approach converge at an mAP of 0.87 (min=0.86, max=0.87, IoU=0.5,
epochs=73), outperforming the model trained on sub-images (mAP=0.72, min =
0.72, max=0.73, IoU=0.5, epochs=23) as shown in Table 2. After 23 epochs the
sub-images-based training is terminated due to overfitting. The backbone
network of the model has no effect on the accuracy. The live sampling
approaches show the lowest performance for the lymphocytes, which are the
smallest and most clustered type of cells. The sub-images-based approach
scores lowest on the rare classes of eosinophils and mast cells due to
overfitting.

When applying the trained solution with a ResNet-18 as a backbone on the image
patches and ground-truth published in [blinded for peer review], we reach a
mean mAP across images of 0.76 with the proposed method and 0.63 with the sub-
images-based approach compared to the experts reaching a published mean
concordance of $\mu$=0.73 mAP (min=0.56, max=0.82,$\sigma$=0.08).

##  4 Discussion and outlook

We demonstrated the creation of an object detection training pipeline which is
able to use partially annotated WSIs efficiently and is superior to a simple
sub-image-based approach. Our proposed approach allows for better sampling
strategies and data augmentation for rare classes which massively reduces the
chance to sample the same patch repeatedly and therefore mitigate overfitting,
as apparent in the considerable difference in performance for eosinophils in
the evaluation. This resulted in a object detection model with human like
performance on a small set of example patches. However, this work has the
limitation that only six images have been partially annotated by one expert,
which needs to be addressed in further research. This work can be used as a
baseline for further enhancements, like increasing the detection performance
of small cells, optimising the non-maximum suppression algorithm for high
quantities of cells but also to create new annotations in an expert-algorithm
based manner on the remaining WSIs.

CAB gratefully acknowledges financial support received from the Dres. Jutta &
Georg Bruns-Stiftung für innovative Veterinärmedizin.

## References

  * [1] Bullone M, Lavoie JP.  Asthma “of horses and men”—how can equine heaves help us better understand human asthma immunopathology and its functional consequences?  Mol Immunol. 2015;66(1):97–105.
  * [2] Marzahl C, Bertram CA, Aubreville M, et al.  Are Fast Labeling Methods Reliable? A Case Study of Computer-Aided Expert Annotations on Microscopy Slides.  In: MICCAI. Cham: Springer International Publishing; 2020. p. 24–32.
  * [3] Huang J, Rathod V, Sun C, et al.  Speed/accuracy trade-offs for modern convolutional object detectors.  In: CVPR; 2017. p. 7310–7311.
  * [4] Kawazoe Y, Shimamoto K, Yamaguchi R, et al.  Faster r-cnn-based glomerular detection in multistained human whole slide images.  Imaging. 2018;4(7):91.
  * [5] Yang F, Yu H, Silamut K, et al.  Parasite Detection in Thick Blood Smears Based on Customized Faster-RCNN on Smartphones.  In: AIPR; 2019. p. 1–4.
  * [6] Aubreville M, Bertram C, Klopfleisch R, et al.  SlideRunner.  In: Bildverarbeitung für die Medizin 2018. Springer; 2018. p. 309–314.
  * [7] Marzahl C, Aubreville M, Bertram CA, et al.  EXACT: A collaboration toolset for algorithm-aided annotation of almost everything.  arXiv preprint arXiv:200414595. 2020;.
  * [8] Marzahl C, Aubreville M, Bertram CA, et al.  Deep Learning-Based Quantification of Pulmonary Hemosiderophages in Cytology Slides.  Sci Rep. 2020;10(1):1–10.
  * [9] Lin TY, Goyal P, Girshick R, et al.  Focal loss for dense object detection.  In: Proceedings of the IEEE international conference on computer vision; 2017. p. 2980–2988.
  * [10] He K, Zhang X, Ren S, et al.  Deep residual learning for image recognition.  In: CVPR; 2016. p. 770–778.

††margin:  E


$\sum_{x\in\mathsf{v}}a_{x}\delta_{x}\in U^{2}_{0}$ is $\langle
v,\sum_{x\in\mathsf{V}}a_{x}\delta_{x}\rangle=\sum_{x\in\mathsf{V}}a_{x}v(x)$,
and the inner products are
$(v,v^{\prime})_{V^{0}}=\sum_{x\in\mathsf{V}}v(x)v^{\prime}(x)$, and
$(\sum_{x\in\mathsf{V}}a_{x}\delta_{x},\sum_{x\in\mathsf{V}}a_{x}^{\prime}\delta_{x})=\sum_{x\in\mathsf{V}}a_{x}a_{x}^{\prime}.$
Moreover, we introduce $\pi_{V^{0}\to
U^{2}_{0}}(v):=\sum_{x\in\mathsf{V}}v(x)\delta_{x}$ and vice versa.

Similarly, we define other linear maps. It can be shown that $\pi_{V^{k}\to
U^{2-k}_{0}}$ induces isomorphisms
$\mathcal{H}^{k}(U^{{\scriptscriptstyle\bullet}}_{0})\cong\mathcal{H}^{2-k}(V^{{\scriptscriptstyle\bullet}})$,
which concludes the result. ∎

###### Proof of Theorem 5.2.

By the following diagram:

(A.7)
${0}$${V^{0}_{-,0}}$${\bm{V}^{1}_{-,0}}$${\bm{V}^{2}_{-,0}}$${\bm{V}^{3}_{-,0}}$${0}$${0}$${C_{3}(\Delta,\mathcal{P}_{1})}$${C_{2}(\Delta,\mathcal{P}_{1})}$${C_{1}(\Delta,\mathcal{P}_{1})}$${C_{0}(\Delta,\mathcal{P}_{1})}$${0.}$$\scriptstyle{\operatorname{hess}}$$\scriptstyle{\kappa^{0}_{-}}$$\scriptstyle{\operatorname{curl}}$$\scriptstyle{\kappa^{1}_{-}}$$\scriptstyle{\operatorname{div}}$$\scriptstyle{\kappa^{2}_{-}}$$\scriptstyle{\kappa^{3}_{-}}$$\scriptstyle{\partial_{0}}$$\scriptstyle{\partial_{0}}$$\scriptstyle{\partial_{0}}$

∎

###### Proof of Theorem 3.2.

The following diagram

(A.8)
${0}$${0}$${\bm{V}^{1}_{0}}$${\bm{V}^{2}_{0}}$${\bm{V}^{3}_{0}}$${0}$${0}$${V^{0}_{-,0}}$${\bm{V}^{1}_{-,0}}$${\bm{V}^{2}_{-,0}}$${\bm{V}^{3}}$${0}$${0}$${\bigoplus\limits_{K\in\mathsf{K}}\mathcal{P}_{1}}$${\bigoplus\limits_{f\in\mathsf{F}}\mathcal{P}_{1}(f)}$${\bigoplus\limits_{e\in\mathsf{E}}\mathcal{P}_{1}(e)}$${\bigoplus\limits_{x\in\mathsf{V}}\mathcal{P}_{1}(x)}$${0,}$$\scriptstyle{\operatorname{hess}_{0}}$$\scriptstyle{\operatorname{curl}_{0}}$$\scriptstyle{\operatorname{div}_{0}}$$\scriptstyle{\operatorname{hess}_{0}}$$\scriptstyle{g^{0}}$$\scriptstyle{\operatorname{curl}_{0}}$$\scriptstyle{g^{1}}$$\scriptstyle{\operatorname{div}_{0}}$$\scriptstyle{g^{2}}$$\scriptstyle{g^{3}}$$\scriptstyle{\widetilde{\partial}_{0}}$$\scriptstyle{\widetilde{\partial}_{0}}$$\scriptstyle{\widetilde{\partial}_{0}}$

induces the long exact sequence below:

(A.9)
${0}$${0}$${\mathcal{N}(\operatorname{curl}_{0}:\bm{V}^{1}_{0}\to\bm{V}^{2}_{0})}$${\mathcal{H}^{2}(V^{{\scriptscriptstyle\bullet}}_{0})}$${\mathcal{H}^{3}(V^{{\scriptscriptstyle\bullet}}_{0})}$${0}$${0}$${\mathcal{H}^{0}_{dR,c}(\Omega)\otimes\mathcal{P}_{1}}$${\mathcal{H}^{1}_{dR,c}(\Omega)\otimes\mathcal{P}_{1}}$${\mathcal{H}^{2}_{dR,c}(\Omega)\otimes\mathcal{P}_{1}}$${\mathcal{H}^{3}_{dR,c}(\Omega)\otimes\mathcal{P}_{1}}$${0}$${0}$${V^{0}_{0}}$${0}$${0}$${0}$${0.}$

The result follows from a diagram chase. ∎

###### Proof of Theorem 5.3.

The proof is based on the following dual pairs:

(A.10)
${0}$${V^{0}_{0}}$${\bm{V}^{1}_{0}}$${\bm{V}^{2}_{0}}$${\bm{V}^{3}_{0}}$${0}$${0}$${U^{3}}$${\widehat{\bm{U}}^{2}}$${\widehat{\bm{U}}^{1}}$${\bm{U}^{0}}$${0.}$$\scriptstyle{\operatorname{hess}_{0}}$${\ast}$$\scriptstyle{\operatorname{curl}_{0}}$${\ast}$$\scriptstyle{\operatorname{div}_{0}}$${\ast}$${\ast}$$\scriptstyle{\widetilde{\operatorname{div}\operatorname{div}}}$$\scriptstyle{\widetilde{\operatorname{sym}\operatorname{curl}}}$$\scriptstyle{\widetilde{\operatorname{dev}\operatorname{grad}}}$

We can define $\pi_{U^{k}\to V^{3-k}_{0}}$ and the inner products of each
space. It can be shown that these $\pi$’s induce an isomorphism between
$\mathcal{H}^{k}(U^{{\scriptscriptstyle\bullet}})$ and
$\mathcal{H}^{3-k}(V^{{\scriptscriptstyle\bullet}}_{0})$, which concludes with
the result. ∎

###### Proof of Theorem 3.5 .

Combining the dual pairing method

(A.11)
${0}$${V^{0}}$${\bm{V}^{1}}$${\bm{V}^{2}}$${\bm{V}^{3}}$${0}$${0}$${U^{3}_{0}}$${\widehat{\bm{U}}^{2}_{0}}$${\widehat{\bm{U}}^{1}_{0}}$${\bm{U}^{0}_{0}}$${0,}$$\scriptstyle{\operatorname{hess}}$${\ast}$$\scriptstyle{\operatorname{curl}}$${\ast}$$\scriptstyle{\operatorname{div}}$${\ast}$${\ast}$$\scriptstyle{\widehat{\operatorname{div}\operatorname{div}}_{0}}$$\scriptstyle{{\operatorname{sym}\operatorname{curl}}_{h}}$$\scriptstyle{{\operatorname{dev}\operatorname{grad}}}$

and the exactness of

(A.12)
${0}$${0}$${\mathbb{B}_{K}^{*}}$${\mathbb{B}_{K}}$${0}$${0}$$\scriptstyle{\operatorname{sym}\operatorname{curl}_{h}}$

yields the result. ∎

## Acknowledgement

The work of KH was supported by a Royal Society University Research Fellowship
(URF$\backslash$ R1$\backslash$221398).

## References

  * [1] Douglas N Arnold.  Finite element exterior calculus.  SIAM, 2018.
  * [2] Douglas N Arnold, Richard S Falk, and Ragnar Winther.  Finite element exterior calculus, homological techniques, and applications.  Acta numerica, 15:1–155, 2006.
  * [3] Douglas N Arnold, Richard S Falk, and Ragnar Winther.  Finite element exterior calculus: from Hodge theory to numerical stability.  Bulletin of the American Mathematical Society, 47(2):281–354, 2010\.
  * [4] Douglas N Arnold and Kaibo Hu.  Complexes from complexes.  Foundations of Computational Mathematics, 21(6):1739–1774, 2021\.
  * [5] Yakov Berchenko-Kogan and Evan S Gawlik.  Finite element approximation of the Levi-Civita connection and its curvature in two dimensions.  Foundations of Computational Mathematics, pages 1–51, 2022.
  * [6] Francesca Bonizzoni, Kaibo Hu, Guido Kanschat, and Duygu Sap.  Discrete tensor product BGG sequences: splines and finite elements.  arXiv preprint arXiv:2302.02434, 2023.
  * [7] Alain Bossavit.  Whitney forms: A class of finite elements for three-dimensional computations in electromagnetism.  IEE Proceedings A (Physical Science, Measurement and Instrumentation, Management and Education, Reviews), 135(8):493–500, 1988.
  * [8] Dietrich Braess and Joachim Schöberl.  Equilibrated residual error estimator for edge elements.  Mathematics of Computation, 77(262):651–672, 2008.
  * [9] Annalisa Buffa, Judith Rivas, Giancarlo Sangalli, and Rafael Vázquez.  Isogeometric discrete differential forms in three dimensions.  SIAM Journal on Numerical Analysis, 49(2):818–844, 2011.
  * [10] Andreas Čap and Kaibo Hu.  BGG sequences with weak regularity and applications.  Foundations of Computational Mathematics, pages 1–40, 2023.
  * [11] Andreas Čap and Kaibo Hu.  Bounded Poincaré operators for twisted and BGG complexes.  accepted, Journal de Mathématiques Pures et Appliquées (arXiv preprint arXiv:2304.07185), 2023.
  * [12] Andreas Čap, Jan Slovák, and Vladimír Souček.  Bernstein-Gelfand-Gelfand sequences.  Annals of Mathematics, pages 97–113, 2001.
  * [13] Long Chen and Xuehai Huang.  Complexes from complexes: Finite element complexes in three dimensions.  arXiv preprint arXiv:2211.08656, 2022.
  * [14] Long Chen and Xuehai Huang.  Finite element complexes in two dimensions.  arXiv preprint arXiv:2206.00851, 2022.
  * [15] Long Chen and Xuehai Huang.  A finite element elasticity complex in three dimensions.  Mathematics of Computation, 91(337):2095–2127, 2022.
  * [16] Long Chen and Xuehai Huang.  Finite elements for div-and divdiv-conforming symmetric tensors in arbitrary dimension.  SIAM Journal on Numerical Analysis, 60(4):1932–1961, 2022.
  * [17] Long Chen and Xuehai Huang.  Finite elements for divdiv conforming symmetric tensors in three dimensions.  Mathematics of Computation, 91(335):1107–1142, 2022.
  * [18] LONG CHEN and XUEHAI HUANG.  A new div-div-conforming symmetric tensor finite element space with applications to the biharmonic equation.  arXiv preprint arXiv:2305.11356, 2023.
  * [19] Snorre H Christiansen.  Foundations of finite element methods for wave equations of Maxwell type.  In Applied Wave Mathematics: Selected Topics in Solids, Fluids, and Mathematical Methods, pages 335–393. Springer, 2009.
  * [20] Snorre H Christiansen.  On the linearization of Regge calculus.  Numerische Mathematik, 119:613–640, 2011.
  * [21] Snorre H Christiansen and Kaibo Hu.  Finite element systems for vector bundles: elasticity and curvature.  Foundations of Computational Mathematics, 23(2):545–596, 2023.
  * [22] Philippe G Ciarlet.  Linear and nonlinear functional analysis with applications, volume 130.  SIAM, 2013.
  * [23] Martin Costabel and Alan McIntosh.  On Bogovskiĭ and regularized Poincaré integral operators for de Rham complexes on Lipschitz domains.  Mathematische Zeitschrift, 265(2):297–320, 2010.
  * [24] Mathieu Desbrun, Anil N Hirani, Melvin Leok, and Jerrold E Marsden.  Discrete exterior calculus.  arXiv preprint math/0508341, 2005.
  * [25] Evan S Gawlik and Michael Neunteufel.  Finite element approximation of scalar curvature in arbitrary dimension.  arXiv preprint arXiv:2301.02159, 2023.
  * [26] Sining Gong, Jay Gopalakrishnan, Johnny Guzmán, and Michael Neilan.  Discrete Elasticity Exact Sequences on Worsey-Farin splits.  arXiv preprint arXiv:2302.08598, 2023.
  * [27] Jay Gopalakrishnan, Philip L Lederer, and Joachim Schöberl.  A mass conserving mixed stress formulation for the Stokes equations.  IMA Journal of Numerical Analysis, 40(3):1838–1874, 2020.
  * [28] Jay Gopalakrishnan, Michael Neunteufel, Joachim Schöberl, and Max Wardetzky.  Analysis of curvature approximations via covariant curl and incompatibility for Regge metrics.  arXiv preprint arXiv:2206.09343, 2022.
  * [29] Jay Gopalakrishnan, Michael Neunteufel, Joachim Schöberl, and Max Wardetzky.  Analysis of distributional riemann curvature tensor in any dimension.  arXiv preprint arXiv:2311.01603, 2023.
  * [30] Allen Hatcher.  Algebraic Topology.  Cambridge University Press, 2002.
  * [31] Ralf Hiptmair.  Canonical construction of finite elements.  Mathematics of computation, 68(228):1325–1346, 1999.
  * [32] Ralf Hiptmair.  Higher order Whitney forms.  Progress in Electromagnetics Research, 32:271–299, 2001.
  * [33] Anil Nirmal Hirani.  Discrete exterior calculus.  California Institute of Technology, 2003.
  * [34] Jun Hu and Yizhou Liang.  Conforming discrete Gradgrad-complexes in three dimensions.  Mathematics of Computation, 90(330):1637–1662, 2021.
  * [35] Jun Hu, Yizhou Liang, and Ting Lin.  Local bounded commuting projection operator for discrete de Rham complexes.  arXiv preprint arXiv:2303.09359, 2023.
  * [36] Jun Hu, Yizhou Liang, and Ting Lin.  Local bounded commuting projection operators for discrete gradgrad complexes.  arXiv preprint arXiv:2304.11566, 2023.
  * [37] Jun Hu, Rui Ma, and Min Zhang.  A family of mixed finite elements for the biharmonic equations on triangular and tetrahedral grids.  Science China Mathematics, 64(12):2793–2816, 2021.
  * [38] Jun Hu and ShangYou Zhang.  A family of symmetric mixed finite elements for linear elasticity on tetrahedral grids.  Science China Mathematics, 58(2):297–307, 2015.
  * [39] Kaibo Hu.  Nonlinear elasticity complex and a finite element diagram chase.  arXiv preprint arXiv:2302.02442, 2023.
  * [40] Kaibo Hu, Ting Lin, and Bowen Shi.  Finite elements for symmetric and traceless tensors in three dimensions.  in preparation, 2023.
  * [41] Ming-Jun Lai and Larry L Schumaker.  Spline functions on triangulations.  Number 110. Cambridge University Press, 2007.
  * [42] Lizao Li.  Regge finite elements with applications in solid mechanics and relativity.  PhD thesis, University of Minnesota, 2018.
  * [43] Martin Werner Licht.  Complexes of discrete distributional differential forms and their homology theory.  Foundations of Computational Mathematics, 17(4):1085–1122, 2017\.
  * [44] Lek-Heng Lim.  Hodge Laplacians on graphs.  SIAM Review, 62(3):685–715, 2020.
  * [45] Jacques Louis Lions and Enrico Magenes.  Non-homogeneous boundary value problems and applications: Vol. 1, volume 181.  Springer Science & Business Media, 2012.
  * [46] Jean-Claude Nédélec.  Mixed finite elements in $\mathbb{R}^{3}$.  Numerische Mathematik, 35:315–341, 1980.
  * [47] Michael Neunteufel and Joachim Schöberl.  Avoiding membrane locking with regge interpolation.  Computer Methods in Applied Mechanics and Engineering, 373:113524, 2021.
  * [48] Michael Neunteufel and Joachim Schöberl.  The Hellan-Herrmann-Johnson and TDNNS method for linear and nonlinear shells.  arXiv preprint arXiv:2304.13806, 2023.
  * [49] Astrid Pechstein and Joachim Schöberl.  Tangential-displacement and normal-normal-stress continuous mixed finite elements for elasticity.  Mathematical Models and Methods in Applied Sciences, 21(08):1761–1782, 2011.
  * [50] Pierre-Arnaud Raviart and Jean-Marie Thomas.  A mixed finite element method for 2-nd order elliptic problems.  In Mathematical Aspects of Finite Element Methods: Proceedings of the Conference Held in Rome, December 10–12, 1975, pages 292–315. Springer, 2006.
  * [51] Stephanie Wang, Mohammad Sina Nabizadeh, and Albert Chern.  Exterior Calculus in Graphics.  SIGGRAPH ’23. ACM, New York, NY, USA, 2023.