PNAS Nexus (preprint) https://doi.org/10.1093/pnasnexus/pgac039 Preprint

Glielmo et al.

[$\ast$]To whom correspondence should be addressed<EMAIL_ADDRESS>
[†]The views and opinions expressed in this paper are those of the authors and
do not necessarily reflect the official policy or position of Banca d’Italia.

Associate Editor: Name

# Ranking the information content of distance measures

Aldo Glielmo  Claudio Zeni  Bingqing Cheng  Gábor Csányi  Alessandro Laio
Physics Department, International School for Advanced Studies (SISSA), Via
Bonomea 265, 34136, Trieste, Italy  Banca d’Italia, Italy† The Institute of
Science and Technology Austria, Am Campus 1, 3400, Klosterneuburg, Austria
Engineering Laboratory, University of Cambridge, Trumpington St, CB21PZ,
Cambridge, United Kingdom

(2022; 2022)

###### Abstract

Real-world data typically contain a large number of features that are often
heterogeneous in nature, relevance, and also units of measure. When assessing
the similarity between data points, one can build various distance measures
using subsets of these features. Finding a small set of features that still
retains sufficient information about the dataset is important for the
successful application of many statistical learning approaches. We introduce a
statistical test that can assess the relative information retained when using
two different distance measures, and determine if they are equivalent,
independent, or if one is more informative than the other. This ranking can in
turn be used to identify the most informative distance measure and, therefore,
the most informative set of features, out of a pool of candidates. To
illustrate the general applicability of our approach, we show that it
reproduces the known importance ranking of policy variables for Covid-19
control, and also identifies compact yet informative descriptors for atomic
structures. We further provide initial evidence that the information asymmetry
measured by the proposed test can be used to infer relationships of causality
between the features of a dataset. The method is general and should be
applicable to many branches of science.

###### keywords:

information theory, feature selection, causality detection

In real-world data sets many characteristics are often associated with each
data point, and one can imagine different ways to define the similarity
between two samples. For example, in a clinical database two patients might be
compared based on their age, sex, or height, or on the results of specific
clinical exams. In this work we introduce a method which allows studying the
relationship between different distances (or similarity) measures defined on
the same dataset. One can find that two distances are unrelated, that they
bring equal information, or that one of the two distances allows predicting
the other, while the reverse is not true. This allows finding distances which
are maximally informative for a prediction, and detecting causality
relationships.

##  1 Introduction

An open challenge in machine learning is to extract useful information from a
database with relatively few data points, but with a large number of features
available for each point Wang et al. (2020); Lopes et al. (2017); Nazábal et
al. (2020). For example, clinical databases typically include data for a few
hundreds patients with a similar clinical history, but an enormous amount of
information for each patient: the results of clinical exams, imaging data, and
a record of part of their genome Sudlow et al. (2015). In cheminformatics and
materials science, molecules and materials can be described by a large number
of features, but databases are limited in size by the great cost of the
calculations or the experiments required to predict quantum properties Altae-
Tran et al. (2017); Yamada et al. (2019). In short, real-world data are often
“big data”, but in the wrong direction: instead of millions of data points,
there are often too many features for a few samples. As such, training
accurate learning models is challenging, and even more so when using deep
neural networks, which typically require a large amount of independent samples
Shorten and Khoshgoftaar (2019).

One way to circumvent this problem is to perform preliminary feature
selection, and discard features that appear irrelevant or redundant Cai et al.
(2018); Lopes et al. (2017); Jović et al. (2015); Deng et al. (2019).
Alternatively, one can perform a dimensional reduction aimed at finding a
representation of the data with few variables built as functions of the
original features van der Maaten and Hinton (2008); McInnes et al. (2018);
Bengio et al. (2013).

Figure 1:  Distance ranks can be used to measure the relative informations
contained in two distance measures. a): Illustration of the distance rank of
two points in different feature spaces $A$ and $B$. The rank $r_{ij}$ of point
$j$ relative to $i$ is equal to 1 in space $A$, meaning that $j$ is the first
neighbor of $i$. This is not the case in space $B$, where point $j$ is the
third neighbor of point $i$. b): Illustration of how ranks can be used to
verify that space $x$ is less informative than space $y$. The figure shows how
a distance bound in $y$ automatically implies a distance bound in $x$. The
opposite is not necessarily true: the first neighbor of a point in the $x$
space can be very far in $y$.

In some cases, explicit features are not available, as in the case of raw text
documents or genome sequences. What one can always define, even in these
cases, are _distances_ between data points whose definition, however, can be
rather arbitrary Kaya and Bilge (2019); Kulis (2013). How can one select,
among an enormous amount of possible choices, the most appropriate distance
measure for a given task? Finding the correct distance is of course as
difficult as performing feature selection or dimensionality reduction. In
fact, these tasks can be considered equivalent if explicit features are
available, since in this case a particular choice of features naturally gives
rise to a different distance function computed through the Euclidean norm.

In this work, we approach feature/distance learning through a novel
statistical and information theoretic concept. We pose the question: given two
distance measures $A$ and $B$, can we identify whether one is more
_informative_ than the other? If distance $A$ is more informative than
distance $B$, even partial information on the distance $A$ can be predictive
about $B$, while the reverse will not necessarily be true. If this happens,
and if the two distances have the same complexity e.g, they are built using
the same number of features, $A$ should be generally preferred with respect to
$B$ in any learning model.

We introduce the concept of “information imbalance”, a measure able to
quantify the relative information content of one distance measure with respect
to another. We show how this tool can be used for feature learning in
different branches of science. For example, by optimizing the information
content of a distance measure we are able to select from a set of more than
300 material descriptors, a subset of around 10 which is sufficient to define
the state of a material system, and predict its energy. Moreover, we use the
information imbalance to verify that the national policy measures implemented
to contain the Covid-19 epidemic are informative about the future state of the
epidemic. In this case, we also show that the method can be used to detect
_causality_ relationship between variables.

##  2 The information imbalance

Inspired by the widespread idea of using local neighborhoods to perform
dimensional reduction Hastie et al. (2001) and classification Gashler et al.
(2008) we quantify the relative quality of two distance measures by analyzing
the _ranks_ of the first neighbors of each point. For each pair of points $i$
and $j$, the rank $r_{ij}$ of point $j$ relative to point $i$, is obtained by
sorting the pairwise distances between $i$ and rest of the points from
smallest to largest. For example, $r_{ij}^{A}=1$ if point $j$ is the first
neighbor of point $i$ according to the distance $d_{A}$. The rank of two
points will be, in general, different when computed using a different distance
measures $B$, as illustrated in Figure 1a.

The key idea of our approach is that distance ranks can be used to identify
whether one metric is more informative than the other. Take the example given
in Figure 1b, depicting a schematic representation of a noisy curved dataset.
In this dataset the distance along the $y$-axis is clearly more informative
than the one along the $x$-axis since one could construct a function able to
predict $x$ from the knowledge of $y$, but not the opposite. This asymmetry is
well captured by the ranks between points. Take for example point $i$ (red
circle in the figure). Its first neighbour according to the $y$-distance is
$j$ (blue circle), while according to the $x$-distance (green lines) $j$ is
the 7th neighbour of $i$ . Conversely, the nearest neighbour of $i$ according
to the $x$-distance is $k$ (green circle), which is the 35th neighbour of $i$
according to the $y$-distance (blue lines). We hence find that $r_{ij}^{x}\ll
r_{ik}^{y}$ i.e., the rank in space $x$ of the first neighbor measured in
space $y$ is much smaller than the rank in space $y$ of first neighbor
measured in space $x$.

To give a more quantitative example, let’s consider a dataset of points
harvested from a 3-dimensional Gaussian whose standard deviation along the $z$
direction is a tenth of those along $x$ and $y$. In this case, one can define
a Euclidean distance between data points either using all the three features,
$d_{xyz}^{2}=(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}+(z_{i}-z_{j})^{2}$, or using
a subset of these features ( $d_{xy}$, $d_{yz}$ and so on).

Intuitively, $d_{xyz}$ and $d_{xy}$ are almost equivalent since the standard
deviation along $z$ is small, while there are information imbalances, say,
between $d_{x}$ and $d_{xy}$, which would allow saying that $d_{xy}$ is more
informative than $d_{x}$.

Figure 2:  Classifying and visualizing the relationship between any two
distance measures using the information imbalance. a), c), e): Scatter plots
of the ranks between ordered pairs of points for different distance measures
evaluated on a 3D Gaussian dataset with a small variance along $z$. The red
and blue bands indicate, respectively, the points for which the rank on the
$x$ and $y$ axis is equal to one (proportions were exaggerated for clarity).
The histogram of the points inside each band is plotted in the bottom plots
using the same color. b), d), f): Probability of that two nearest neighbor
points ($r=1$) for one distance have rank $r$ for the other distance. The
three columns represent different pairs of representations. g): The four
different types of relationships that can characterize the relative
information content of two spaces $A$ and $B$. h): Information imbalance plane
for the discussed 3D Gaussian dataset with small $z$-axis variance (gray
markers), and for a 4D isotropic Gaussian dataset (black star). The different
colors (light blue, red, green and orange) roughly mark the regions
corresponding to the four types of relationships listed in panel g.

In the first row of Figure 2, we plot the ranks computed using one distance
against the ranks computed using a second distance (for example the ranks in
$d_{xy}$ as a function of those in $d_{xyz}$ for panel a). In the second row
of the figure we show the probability distribution $p(r^{A}\mid r^{B}=1)$ of
the ranks $r_{ij}^{A}$ in space $A$ restricted to those pairs $(i,j)$ for
which $r_{ij}^{B}=1$, namely to the nearest neighbors according to distance
$B$. In panels a and b, we compare the most informative distance containing
all three coordinates to the one containing only the $x$ and $y$ coordinates.
Given the small variance along the $z$ direction, these two distance measures
are practically equivalent, and this results in rank distributions strongly
peaked around one. In panels c and d, we compare the two metrics $d_{xy}$ and
$d_{x}$. In this case, the former is clearly more informative than the latter,
and we find that the distribution of ranks when passing from $d_{xy}$ to
$d_{x}$ is more peaked around small values than when going in the opposite
direction. Finally, for two metrics built using independent coordinates ($x$
and $y$, in panels c and f) the rank distributions are completely uniform.

We hence propose to assess the relationship between any two distance measures
$d_{A}$ and $d_{B}$ by using the properties of the conditional rank
distribution $p(r^{B}\mid r^{A}=1)$. The closer this distribution is to a
delta function peaked at one, the more information about space $B$ is
contained within space $A$.

This intuition can be made more rigorous through the statistical theory of
copula variables. We can define a copula variable $c_{A}$ as the cumulative
distribution $c_{A}=\int_{0}^{d_{A}}p_{A}(w\mid x)dw$, where $p_{A}(w\mid x)$
is the of probability of sampling a data point within distance $w$ from $x$ in
the $A$ space. The value of $c_{A}$ can be estimated from a finite dataset by
counting the fraction of points that fall within distance $d_{A}$ of point
$x$, $c_{A}\approx r_{A}/N$. Copula variables and distance ranks can be
considered continuous-discrete analogues of each other. As a consequence, the
distributions $p(r^{B}\mid r^{A}=1)$ shown in Figure 2 are nothing else but
estimates of the copula distributions $p(c_{B}\mid c_{A})$ with $c_{A}$
conditioned to be very small. This is important, since Sklar’s theorem
guarantees that the copula distribution $p(c_{A},c_{B})$ contains the entire
correlation structure of the metric spaces $A$ and $B$, independently of any
details of the marginal distributions $p(d_{A}\mid x)$ and $p(d_{B}\mid x)$
Nelsen (2006); Calsaverini and Vicente (2009); Safaai et al. (2018).

Using the copula variables, we define the “information imbalance” from space
$A$ to space $B$ as

$\Delta(A\rightarrow B)=2\lim_{\epsilon\rightarrow 0}\,\langle c_{B}\mid
c_{A}=\epsilon\rangle,$ (1)

where we used the conditional expectation $\langle c_{B}\mid
c_{A}=\epsilon\rangle=\int c_{B}\,p(c_{B}\mid c_{A}=\epsilon)dc_{B}$ to
characterize the deviation of $p(c_{B}\mid c_{A}=\epsilon)$ from a delta
function. In the limit cases where the two spaces are equivalent or completely
independent we have that $\langle c_{B}\mid c_{A}=\epsilon\rangle=\epsilon$
and $\langle c_{B}\mid c_{A}=\epsilon\rangle=1/2$ respectively, so that the
definition provided in Eq. (1) statistically confines $\Delta$ in the range
$(0,1)$. The information imbalance defined in Eq. (1) is estimated on a
dataset with $N$ data points as

$\Delta(A\rightarrow B)\approx 2\langle r^{B}\mid r^{A}=1\rangle/N$ (2)

We remark that the conditional expectation used in Eq. (1) is only one of the
possible quantities that can be used to characterize the deviation of the
conditional copula distribution from a delta function. Another attractive
option is the entropy of the distribution. In the Supplementary Material (SM)
(S1.C), we show how these two quantities are related and we demonstrate that
the specific choice does not substantially affect the results. In the SM (see
S1.B and Figure S1), we also show how copula variables can be used to connect
the information imbalance to the standard information theoretic concept of
mutual information.

By measuring the information imbalances $\Delta(A\rightarrow B)$ and
$\Delta(B\rightarrow A)$, we can identify four classes of relationships
between the two spaces $A$ and $B$. We can find whether $A$ and $B$ are
equivalent or independent, whether they symmetrically share both independent
and equivalent information, or whether one space contains the information of
the other. These relationships are presented in Figure 2g. These relationships
can be identified visually by plotting the two imbalances $\Delta(A\rightarrow
B)$ and $\Delta(B\rightarrow A)$ against each other in a graph as done in
Figure 2h. We will refer to this kind of graphs as _information imbalance
planes_. In Figure 2h we present the information imbalance plane of the
3-dimensional Gaussian dataset discussed so far, and used for Figure 2a-f.
Looking at this figure, one can immediately verify that the small variance
along the $z$ axis makes the two spaces $xyz$ and $xy$ practically equivalent
(gray circle). Similarly, one can verify that space $x$ is correctly
identified to be contained in $xyz$ (gray square) and that the two spaces $x$
and $y$ are classified as orthogonal (gray triangle). The figure also includes
a point corresponding to a different dataset sampled from a 4-dimensional
isotropic Gaussian with dimensions $\tilde{x}$, $\tilde{y}$, $\tilde{z}$ and
$\tilde{w}$. This point (black star) shows that the spaces
$\tilde{x}\tilde{y}\tilde{z}$ and $\tilde{y}\tilde{z}\tilde{q}$ are correctly
identified as sharing symmetric information. Importantly, the information
imbalance only depends on the local neighborhood of each point and, for this
reason, it is naturally suited to analyze data manifolds which are arbitrarily
nonlinear. In the SM (see S2.A and Figure S2), we show that our approach is
able to correctly identify the best feature for describing a spiral of points
wrapping around one axis, and a sinusoidal function. More numerical tests are
available online at DAD (2022) along with the corresponding code Glielmo et
al. (2022). In the examples discussed so far we have chosen the Euclidean
metric as distance measure for any subset of coordinates considered. We will
make the same choice throughout the rest of this work.

Figure 3:  The information imbalance allows for a straightforward verification
of the impact of national policy measures on the Covid-19 epidemic. a)
Information imbalance between the space $[T_{t},C_{t}]$ of the number of tests
and number of confirmed cases $C_{t}$ in a given week $t$, and the number of
deaths $D_{t+\delta t}$ occurred in week $t+\delta t$. The time shift $\delta
t$ ranges from $-5$ (5 weeks before) to $+5$ (5 weeks after). b): Minimum
information imbalances from growing sets of policy variables $P_{t}$ to the
state of the epidemic after two weeks $E_{t+2}$. c): The corresponding
information imbalance plane with the number of policy variables going from 1
to 10 reported in the gray circles. Point 10 is not visible as it lies below
point 9. The figure shows that the policy measures space $P_{t}$ can predict
the state of the epidemic $E_{t+2}$, while $E_{t+2}$ cannot predict $P_{t}$.

##  3 Influence of national policy measures on the Covid-19 epidemic

We now use the information imbalance to analyze the “Covid-19 Data Hub”, a
dataset which provides comprehensive and up to date information on the
Covid-19 epidemic Guidotti and Ardia (2020), including epidemiological
indicators such as the number of confirmed infections and the number of
Covid-19 related deaths for nations where this is available, as well as the
policy indicators that quantify the severity of the governmental measures such
as school and workplace closing, restrictions on gatherings and movements of
people, testing and contact tracing Hale et al. (2020). More details on the
dataset are available in the SM (S2.B.1).

We first illustrate how the information imbalance can be used to recover the
arrow of time from time series data. In Figure 3a we show the information
imbalance between the space $[T_{t},C_{t}]$, containing the number of tests
$T_{t}$ and the number of confirmed cases $C_{t}$ in a given week $t$, and the
space of the number of deaths occurring in week $t+\delta t$ ($D_{t+\delta
t}$). The imbalance is shown as a function of $\delta t$. All the points lay
above the diagonal, indicating that, in the language of Figure 2h, the number
of deaths is marginally _contained_ in the two variables $[T_{t},C_{t}]$ if
$\delta_{t}$ is small; and the optimal information imbalance occurs at $\delta
t=1$. Importantly, for each pair of opposite time lags ($\delta t,-\delta t$)
we find that the two variables $[T_{t},C_{t}]$ always contain more information
on future deaths than on past deaths. In this scenario this result represents
an obvious verification of the known arrow of time of the dataset, but it
suggests that further dedicated investigations could bring to the development
of accurate tests to detect nontrivial causality relationships Runge et al.
(2019).

We now analyze the relationship between the space of policy measures $P_{t}$
at week $t$, and the state of the epidemic $E_{t+\delta t}$, with $\delta t=2$
(namely after two weeks). In SM (S2.B.2, Figure S3) we show that the analysis
with time lags of one or three weeks bring to similar results. While we
consider several different choices for the policy space, the epidemic state is
defined by the number of weekly deaths $D_{t}$ and the ratio
$R_{t}=C_{t}/T_{t}$ of confirmed cases $C_{t}$ over total number of tests
performed $T_{t}$ per week. We estimate the information imbalance
$\Delta(P_{t}\rightarrow E_{t+\delta t})$ between the spaces defined by all
the possible combination of policy measures $P_{t}$ and the space of
epidemiological variables $E_{t+\delta t}$. A low value of
$\Delta(P_{t}\rightarrow E_{t+\delta t})$ means that $P_{t}$ can predict
$E_{t+\delta t}$. In Figure 3b we present the minimum information imbalance
$\Delta(P_{t}\rightarrow E_{t+\delta t})$ achievable with any set of $d$
policy measures.

For $d\leq 2$, $\Delta(P_{t}\rightarrow E_{t+\delta t})$ is close to one,
indicating that no single or couple of policy measure is significantly
predictive about the state of the epidemic, consistently with Haug et al.
(2020). When three or more policy measures are considered, the information
imbalance decreases rapidly reaching a value of about $0.28$ when almost all
policy measures are considered. This sharp decrease and the low value of the
information imbalance clearly indicate that policy measures _do contain_
information on the future state of the epidemic, and the more policy measures
are considered, the more the future state of the epidemic can be considered as
_contained_ in the space of the policies. As a sanity check, a dummy policy
variable was introduced for this test (blue hexagon). This variable is never
selected by the algorithm, and its addition deteriorates the information
content of the policy space.

The described analysis verifies that policy interventions have been effective
in containing the spreading of the Covid-19 epidemic, a result which has been
shown in a number of studies Brauner et al. (2021); Haug et al. (2020); Hsiang
et al. (2020); Flaxman et al. (2020). In accordance with these studies, we
also find that multiple measures are necessary to effectively contain the
epidemic, with no single policy being sufficient on its own Soltesz et al.
(2020), and that the impact of policy measures increases monotonically with
the number of measures put in place. We find that a small yet effective set of
policy measures has been the combination of testing, stay home restrictions
and restrictions on international movement and gatherings. While our results
are computed as averages over all nations considered, further analysis carried
out in the SM (S2.B.3, Figure S5) on disjointed subsets of nations give
results which are consistent with our main findings.

We finally note that the information imbalance $\Delta(E_{t+2}\rightarrow
P_{t})$ (shown in Figure 3c) remains considerably high for any number of
policy variables. This indicates that the state of the epidemic is not
informative about past policy measures. Surprisingly, the state of the
epidemic is not informative even on _future_ policy measures (see S2.B.2 and
Figure S4 of the SM), a result which seems to indicate that that different
nations have reacted to the epidemic through widely different strategies.

The information imbalance can also be used to optimally choose the relative
scale of heterogeneous variables. For instance, in the SM (S2.B.4, Figure S6),
we use the information imbalance to select the relative scale of heterogeneous
epidemiological variables such as the total number of tests and the ratio of
confirmed cases over total number of tests. This is important in real-world
applications, where features are often characterized by different units of
measure and different scales of variations.

Figure 4:  The information imbalance can be used to perform an effective
information-driven feature selection in materials systems. a): Information
imbalances between ground truth “rmsd” distance metric and standard atomistic
descriptors. b): Information imbalances between a full description and the
most informative $d$-plet of components ($d=1,\dots,4$). c): Convergence of
the “symmetric” information imbalance with the number of components for three
different compression strategies. The symmetric information imbalance is
defined as $\bar{\Delta}(A,B)=[\Delta(A\rightarrow B)+\Delta(B\rightarrow
A)]/\sqrt{2}$; more details can be found in the SM (S2.C.3). d): Force error
on a validation set of a machine learning potential energy model built on the
compressed descriptors.

##  4 Selection and compression of descriptors in materials physics

We now show that the information imbalance criterion can be used to assess the
information content of commonly used numerical descriptors of the geometric
arrangement of atoms in materials and molecules, as well as to compress the
dimension (number of features) of a given descriptor with minimal loss of
information. Such atomistic descriptors are needed for applying any
statistical learning algorithm to problems in physics and chemistry Zdeborová
(2017); Schütt et al. (2020); Carleo et al. (2019); Schmidt et al. (2019);
Butler et al. (2018), and the problem of choosing optimally informative atomic
descriptors has recently attracted attention Goscinski et al. (2021). We first
consider a database consisting of an atomic trajectory of amorphous silicon
generated from a molecular dynamics simulation at 500$\rm{K}$ (see S2.C.1 of
the SM for details). At each time step of this trajectory we select a single
local environment by including all the neighboring atoms within the cutoff
radius of $4.5\text{\AA}$ from a given central atom. In this simple system,
which does not undergo any significant atomic rearrangement, one can define a
fully informative distance measure as the minimum over all rigid rotations of
the root mean square deviation (rmsd) of two local environments (details in
S2.C.2 of the SM).

In Figure 4a, this ground truth distance measure is compared with some of the
descriptors most commonly used for materials modeling: the “Atom-centered
Symmetry Functions” (ACSF) Behler and Parrinello (2007); Behler (2011), the
“Smooth Overlap of Atomic Positions” (SOAP) Bartók et al. (2013); Caro (2019)
and the 2 and 3-body kernels Glielmo et al. (2018); Zeni et al. (2019).
Unsurprisingly, all descriptors are contained in the ground truth distance
measure. For ACSF and SOAP representations, one can increase the resolution by
increasing the size of the descriptor in a systematic way, and we found that
doing this allows both representations to converge to the ground truth.

A materials descriptor typically involves a few hundred components. Following
a procedure similar to the one used in the last section to select policy
measures, we use the information imbalance to efficiently compress these high-
dimensional vectors with minimal loss of information (more details are given
in S2.C.3 of the SM). We perform this compression for a database consisting of
complex geometric arrangements of carbon atoms Deringer and Csányi (2017). As
illustrated in Figure 4b and c, the selection leads to a rapid decrease of the
information imbalance, and converge much more quickly than other strategies
such as random selection (blue squares) and standard sequential selection
(green triangles). Figure 4d depicts the test error of a potential energy
model constructed using a state-of-the-art Gaussian process regression model
Bartók et al. (2010) (see S2.C.5 of the SM) on the compressed descriptors, as
a function of the size of the descriptors and for the different compression
strategies considered. Remarkably, the graph shows that a very accurate model
can be obtained using only 16 out of the 324 original components of the
descriptor considered Caro (2019). Figures 4c and 4d show that when the
information imbalance has converged, the validation error does not diminish
further. This suggests that one can select the optimal descriptor dimension as
the one for which no improvement in the information imbalance is observed. In
the SM (S2.C.6, Figure S8) we show how a similar criterion can be also used to
select the hyper-parameters of materials descriptors, and we demonstrate how
the order of the components selected by our procedure can be understood
considering the fundamental structure of the descriptor. In the SM (S2.C.7,
Figure S7) we show that, for this prediction task, the feature selection
scheme based on the information imbalance is marginally more efficient than
other well known compression schemes for materials descriptors.

##  5 Conclusions

In this work we introduce the information imbalance, a new method to assess
the relative information content between two distance measures. The key
property which makes the information imbalance useful is its asymmetry: it is
different when computed using a distance $A$ as a reference and a distance $B$
as a target, and when the two distances are swapped. This allows
distinguishing three classes of similarity between two distance measures: a
full equivalence, a partial but symmetric equivalence, and an asymmetric
equivalence, in which one of the two distances is observed to contain the
information of the other.

The potential applications of the information imbalance criterion are
multifaceted. The most important one is probably the long-standing and crucial
problem of feature selection van der Maaten and Hinton (2008); McInnes et al.
(2018); Bengio et al. (2013). Low-dimensional models typically allow for more
robust predictions in supervised learning tasks Lopes et al. (2017); Cai et
al. (2018). Moreover, they are generally easier to interpret and can be used
for direct data visualization if sufficiently low dimensional. We design
feature selection algorithm by selecting the subset of features which
minimizes the information imbalance with respect to a target property, or to
the original feature space.

As we have showcased, such algorithms can be “exact” if the distances to be
compared are relatively few (as done for the Covid-19 database) or
approximate, if one has to compare a very large number of distances (as done
for the atomistic database). Such algorithms work well even when in the
presence of strong nonlinearities and correlations within the feature space.
This is exemplified by the analysis of the Covid-19 dataset, where 4 policy
measures which appear similarly irrelevant when taken singularly, were instead
identified as maximally informative when taken together with regards to the
future state of the epidemic.
Other applications include dimensionality reduction schemes that directly use
the information imbalance as an objective function. Admittedly such function
will in general be non differentiable and highly non-linear, but efficient
optimization algorithms could still be developed by exploiting recent results
on the computation of approximate derivatives for sorting and ranking
operations Blondel et al. (2020).
Another potentially fruitful line of research would be exploiting the
information imbalance to optimize the performance of deep neural networks. For
example, in SM (S2.C.8, Figure S9), we show that one can reduce the size of
the input layer of a neural network that predicts the energy of a material,
yielding more computationally efficient and robust predictions. However, one
can imagine to go much further, and compare distance measures built using the
representations in different hidden layers, or in different architectures.
This could allow for designing maximally informative and maximally compact
neural network architectures. We finally envision potential applications of
the proposed method in the study of causal relationships: we have seen that in
the Covid-19 database the use of information imbalance makes it possible to
distinguish the future from the past, as the former contains information about
the latter, but not vice-versa. We believe that this empirical observation can
be made robust by dedicated theoretical investigations, and used in practical
applications in other branches of science.

##  6 Acknowledgments

AG, CZ, and AL gratefully acknowledge support from the European Union’s
Horizon 2020 research and innovation program (Grant No. 824143, MaX ’Materials
design at the eXascale’ Centre of Excellence). The authors would like to thank
M. Carli, D. Doimo and I. Macocco (SISSA) for discussions, M. Caro (Aalto
University) for precious help in using the TurboGap code and D. Frenkel
(University of Cambridge) and N. Bernstein (U.S. Naval Research Laboratory)
for useful feedback on the manuscript.

##  7 Supplementary Material

Supplementary material is available at PNAS Nexus online.

##  8 Funding

This work is supported in part by funds from the European Union’s Horizon 2020
research and innovation program (Grant No. 824143, MaX ’Materials design at
the eXascale’ Centre of Excellence).

##  9 Author contributions statement

A.L., A.G., G.C. and B.C. designed research; A.G performed research; A.L. and
C.Z. contributed to perform research; A.G., C.Z., B.C., G.C. and A.L. wrote
the paper.

##  10 Data availability

Details on the datasets used are available in the supplementary material.

## References

  * Wang et al. [2020] Yaqing Wang, Quanming Yao, James T. Kwok, and Lionel M. Ni.  Generalizing from a few examples: A survey on few-shot learning.  _ACM Comput. Surv._ , 53(3), June 2020.  ISSN 0360-0300.  10.1145/3386252.  URL https://doi.org/10.1145/3386252.
  * Lopes et al. [2017] André Teixeira Lopes, Edilson de Aguiar, Alberto F. De Souza, and Thiago Oliveira-Santos.  Facial expression recognition with convolutional neural networks: Coping with few data and the training sample order.  _Pattern Recognition_ , 61:610–628, 2017.  ISSN 0031-3203.  https://doi.org/10.1016/j.patcog.2016.07.026.  URL https://www.sciencedirect.com/science/article/pii/S0031320316301753.
  * Nazábal et al. [2020] Alfredo Nazábal, Pablo M. Olmos, Zoubin Ghahramani, and Isabel Valera.  Handling incomplete heterogeneous data using vaes.  _Pattern Recognition_ , 107:107501, 2020.  ISSN 0031-3203.  https://doi.org/10.1016/j.patcog.2020.107501.  URL https://www.sciencedirect.com/science/article/pii/S0031320320303046.
  * Sudlow et al. [2015] Cathie Sudlow, John Gallacher, Naomi Allen, Valerie Beral, Paul Burton, John Danesh, Paul Downey, Paul Elliott, Jane Green, Martin Landray, et al.  Uk biobank: an open access resource for identifying the causes of a wide range of complex diseases of middle and old age.  _Plos med_ , 12(3):e1001779, 2015.
  * Altae-Tran et al. [2017] Han Altae-Tran, Bharath Ramsundar, Aneesh S. Pappu, and Vijay Pande.  Low data drug discovery with one-shot learning.  _ACS Central Science_ , 3(4):283–293, 2017.  10.1021/acscentsci.6b00367.  URL https://doi.org/10.1021/acscentsci.6b00367.  PMID: 28470045.
  * Yamada et al. [2019] Hironao Yamada, Chang Liu, Stephen Wu, Yukinori Koyama, Shenghong Ju, Junichiro Shiomi, Junko Morikawa, and Ryo Yoshida.  Predicting materials properties with little data using shotgun transfer learning.  _ACS Central Science_ , 5(10):1717–1730, 2019\.  10.1021/acscentsci.9b00804.  URL https://doi.org/10.1021/acscentsci.9b00804.
  * Shorten and Khoshgoftaar [2019] Connor Shorten and Taghi M. Khoshgoftaar.  A survey on image data augmentation for deep learning.  _Journal of Big Data_ , 6(1):60, Jul 2019.  ISSN 2196-1115.  10.1186/s40537-019-0197-0.  URL https://doi.org/10.1186/s40537-019-0197-0.
  * Cai et al. [2018] Jie Cai, Jiawei Luo, Shulin Wang, and Sheng Yang.  Feature selection in machine learning: A new perspective.  _Neurocomputing_ , 300:70–79, 2018.  ISSN 0925-2312.  https://doi.org/10.1016/j.neucom.2017.11.077.  URL https://www.sciencedirect.com/science/article/pii/S0925231218302911.
  * Jović et al. [2015] A. Jović, K. Brkić, and N. Bogunović.  A review of feature selection methods with applications.  In _2015 38th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)_ , pages 1200–1205, 2015.  10.1109/MIPRO.2015.7160458.
  * Deng et al. [2019] Xuelian Deng, Yuqing Li, Jian Weng, and Jilian Zhang.  Feature selection for text classification: A review.  _Multimedia Tools and Applications_ , 78(3):3797–3816, Feb 2019.  ISSN 1573-7721.  10.1007/s11042-018-6083-5.  URL https://doi.org/10.1007/s11042-018-6083-5.
  * van der Maaten and Hinton [2008] Laurens van der Maaten and Geoffrey Hinton.  Visualizing Data using t-SNE.  _Journal of Machine Learning Research_ , 9:2579–2605, November 2008.
  * McInnes et al. [2018] Leland McInnes, John Healy, and James Melville.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ , 2018.
  * Bengio et al. [2013] Y Bengio, A Courville, and P Vincent.  Representation Learning: A Review and New Perspectives.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 35(8):1798–1828, June 2013.
  * Kaya and Bilge [2019] Kaya and Bilge.  Deep Metric Learning: A Survey.  _Symmetry_ , 11(9):1066–26, September 2019.
  * Kulis [2013] Brian Kulis.  Metric Learning: A Survey.  _Foundations and Trends in Machine Learning_ , 5(4):287–364, 2013.
  * Hastie et al. [2001] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  _The Elements of Statistical Learning_.  Springer Series in Statistics. Springer New York Inc., New York, NY, USA, 2001.
  * Gashler et al. [2008] Michael Gashler, Dan Ventura, and Tony Martinez.  Iterative non-linear dimensionality reduction with manifold sculpting.  In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2008.  URL https://proceedings.neurips.cc/paper/2007/file/c06d06da9666a219db15cf575aff2824-Paper.pdf.
  * Nelsen [2006] Roger B. Nelsen.  _An introduction to copulas._ Springer, New York, 2006.  ISBN 0387286594 9780387286594.  URL http://www.worldcat.org/search?qt=worldcat_org_all&q=0387286594.
  * Calsaverini and Vicente [2009] R. S. Calsaverini and R. Vicente.  An information-theoretic approach to statistical dependence: Copula information.  _EPL (Europhysics Letters)_ , 88(6):68003, dec 2009.  10.1209/0295-5075/88/68003.  URL https://doi.org/10.1209/0295-5075/88/68003.
  * Safaai et al. [2018] Houman Safaai, Arno Onken, Christopher D. Harvey, and Stefano Panzeri.  Information estimation using nonparametric copulas.  _Phys. Rev. E_ , 98:053302, Nov 2018.  10.1103/PhysRevE.98.053302.  URL https://link.aps.org/doi/10.1103/PhysRevE.98.053302.
  * DAD [2022] Dadapy: Distance-based analysis of data-manifolds in python.  Code: https://github.com/sissa-data-science/DADApy, Documentation: https://dadapy.readthedocs.io, 2022.  Accessed: 2022-02-10.
  * Glielmo et al. [2022] Aldo Glielmo, Iuri Macocco, Diego Doimo, Matteo Carli, Claudio Zeni, Romina Wild, Maria d’Errico, Alex Rodriguez, and Laio Alessandro.  DADApy: Distance-based Analysis of DAta-manifolds in Python.  _arXiv preprint arXiv:2205.03373_ , 2022.  https://doi.org/10.48550/arXiv.2205.03373.  URL https://arxiv.org/abs/2205.03373.
  * Guidotti and Ardia [2020] Emanuele Guidotti and David Ardia.  COVID-19 Data Hub.  _Journal of Open Source Software_ , 5(51):2376, July 2020.
  * Hale et al. [2020] Thomas Hale, Anna Petherick, Toby Phillips, and Samuel Webster.  Variation in government responses to covid-19.  _Blavatnik school of government working paper_ , 31:2020–11, 2020.
  * Runge et al. [2019] Jakob Runge, Sebastian Bathiany, Erik Bollt, Gustau Camps-Valls, Dim Coumou, Ethan Deyle, Clark Glymour, Marlene Kretschmer, Miguel D Mahecha, Jordi Muñoz-Marí, et al.  Inferring causation from time series in earth system sciences.  _Nature communications_ , 10(1):1–13, 2019.
  * Haug et al. [2020] Nils Haug, Lukas Geyrhofer, Alessandro Londei, Elma Dervic, Amélie Desvars-Larrive, Vittorio Loreto, Beate Pinior, Stefan Thurner, and Peter Klimek.  Ranking the effectiveness of worldwide covid-19 government interventions.  _Nature Human Behaviour_ , 4(12):1303–1312, Dec 2020.  ISSN 2397-3374.  10.1038/s41562-020-01009-0.  URL https://doi.org/10.1038/s41562-020-01009-0.
  * Brauner et al. [2021] Jan M. Brauner, Sören Mindermann, Mrinank Sharma, David Johnston, John Salvatier, Tomáš Gavenčiak, Anna B. Stephenson, Gavin Leech, George Altman, Vladimir Mikulik, Alexander John Norman, Joshua Teperowski Monrad, Tamay Besiroglu, Hong Ge, Meghan A. Hartwick, Yee Whye Teh, Leonid Chindelevitch, Yarin Gal, and Jan Kulveit.  Inferring the effectiveness of government interventions against covid-19.  _Science_ , 371(6531), 2021.  ISSN 0036-8075.  10.1126/science.abd9338.  URL https://science.sciencemag.org/content/371/6531/eabd9338.
  * Hsiang et al. [2020] Solomon Hsiang, Daniel Allen, Sébastien Annan-Phan, Kendon Bell, Ian Bolliger, Trinetta Chong, Hannah Druckenmiller, Luna Yue Huang, Andrew Hultgren, Emma Krasovich, Peiley Lau, Jaecheol Lee, Esther Rolf, Jeanette Tseng, and Tiffany Wu.  The effect of large-scale anti-contagion policies on the covid-19 pandemic.  _Nature_ , 584(7820):262–267, Aug 2020.  ISSN 1476-4687.  10.1038/s41586-020-2404-8.  URL https://doi.org/10.1038/s41586-020-2404-8.
  * Flaxman et al. [2020] Seth Flaxman, Swapnil Mishra, Axel Gandy, H. Juliette T. Unwin, Thomas A. Mellan, Helen Coupland, Charles Whittaker, Harrison Zhu, Tresnia Berah, Jeffrey W. Eaton, Mélodie Monod, Pablo N. Perez-Guzman, Nora Schmit, Lucia Cilloni, Kylie E. C. Ainslie, Marc Baguelin, Adhiratha Boonyasiri, Olivia Boyd, Lorenzo Cattarino, Laura V. Cooper, Zulma Cucunubá, Gina Cuomo-Dannenburg, Amy Dighe, Bimandra Djaafara, Ilaria Dorigatti, Sabine L. van Elsland, Richard G. FitzJohn, Katy A. M. Gaythorpe, Lily Geidelberg, Nicholas C. Grassly, William D. Green, Timothy Hallett, Arran Hamlet, Wes Hinsley, Ben Jeffrey, Edward Knock, Daniel J. Laydon, Gemma Nedjati-Gilani, Pierre Nouvellet, Kris V. Parag, Igor Siveroni, Hayley A. Thompson, Robert Verity, Erik Volz, Caroline E. Walters, Haowei Wang, Yuanrong Wang, Oliver J. Watson, Peter Winskill, Xiaoyue Xi, Patrick G. T. Walker, Azra C. Ghani, Christl A. Donnelly, Steven Riley, Michaela A. C. Vollmer, Neil M. Ferguson, Lucy C. Okell, Samir Bhatt, and Imperial College COVID-19 Response Team.  Estimating the effects of non-pharmaceutical interventions on covid-19 in europe.  _Nature_ , 584(7820):257–261, Aug 2020.  ISSN 1476-4687.  10.1038/s41586-020-2405-7.  URL https://doi.org/10.1038/s41586-020-2405-7.
  * Soltesz et al. [2020] Kristian Soltesz, Fredrik Gustafsson, Toomas Timpka, Joakim Jaldén, Carl Jidling, Albin Heimerson, Thomas B Schön, Armin Spreco, Joakim Ekberg, Örjan Dahlström, Fredrik Bagge Carlson, Anna Jöud, and Bo Bernhardsson.  The effect of interventions on COVID-19.  _Nature_ , pages 1–9, December 2020.
  * Zdeborová [2017] Lenka Zdeborová.  Machine learning: New tool in the box.  _Nature Physics_ , 13(5):420–421, May 2017.
  * Schütt et al. [2020] Kristof T Schütt, Stefan Chmiela, O A von Lilienfeld, Alexandre Tkatchenko, Koji Tsuda, and K R Müller.  _Machine Learning Meets Quantum Physics_.  Springer Nature, June 2020.
  * Carleo et al. [2019] Giuseppe Carleo, Ignacio Cirac, Kyle Cranmer, Laurent Daudet, Maria Schuld, Naftali Tishby, Leslie Vogt-Maranto, and Lenka Zdeborová.  Machine learning and the physical sciences.  _Rev. Mod. Phys._ , 91:045002, Dec 2019.  10.1103/RevModPhys.91.045002.  URL https://link.aps.org/doi/10.1103/RevModPhys.91.045002.
  * Schmidt et al. [2019] Jonathan Schmidt, Mário R G Marques, Silvana Botti, and Miguel A L Marques.  Recent advances and applications of machine learning in solid- state materials science.  _npj Computational Materials_ , pages 1–36, August 2019.
  * Butler et al. [2018] Keith T Butler, Daniel W Davies, Hugh Cartwright, Olexandr Isayev, and Aron Walsh.  Machine learning for molecular and materials science.  _Nature_ , pages 1–9, July 2018.
  * Goscinski et al. [2021] Alexander Goscinski, Guillaume Fraux, Giulio Imbalzano, and Michele Ceriotti.  The role of feature space in atomistic learning.  _Machine Learning: Science and Technology_ , 2(2):025028, 2021.
  * Behler and Parrinello [2007] Jörg Behler and Michele Parrinello.  Generalized neural-network representation of high-dimensional potential-energy surfaces.  _Physical review letters_ , 98(14):146401, 2007\.
  * Behler [2011] J Behler.  Atom-centered symmetry functions for constructing high-dimensional neural network potentials.  _The Journal of Chemical Physics_ , 134(7):074106–14, February 2011.
  * Bartók et al. [2013] A P Bartók, Risi Kondor, and Gábor Csányi.  On representing chemical environments.  _Physical Review B_ , 87(18):184115–16, May 2013\.
  * Caro [2019] Miguel A. Caro.  Optimizing many-body atomic descriptors for enhanced computational performance of machine learning based interatomic potentials.  _Physical Review B_ , 100:024112, Jul 2019.  10.1103/PhysRevB.100.024112.  URL https://link.aps.org/doi/10.1103/PhysRevB.100.024112.
  * Glielmo et al. [2018] A Glielmo, Claudio Zeni, and A De Vita.  Efficient nonparametric $n$-body force fields from machine learning.  _Physical Review B_ , 97(18):1–12, May 2018.
  * Zeni et al. [2019] Claudio Zeni, Kevin Rossi, A Glielmo, and Francesca Baletto.  On machine learning force fields for metallic nanoparticles.  _Advances in Physics: X_ , 4(1):1–33, December 2019.
  * Deringer and Csányi [2017] Volker L Deringer and Gábor Csányi.  Machine learning based interatomic potential for amorphous carbon.  _Physical Review B_ , 95(9):094203, March 2017\.
  * Bartók et al. [2010] Albert P Bartók, Mike C Payne, Risi Kondor, and Gábor Csányi.  Gaussian approximation potentials: The accuracy of quantum mechanics, without the electrons.  _Physical review letters_ , 104(13):136403, 2010\.
  * Blondel et al. [2020] Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga.  Fast differentiable sorting and ranking.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 950–959. PMLR, 13–18 Jul 2020.  URL http://proceedings.mlr.press/v119/blondel20a.html.


* Liu and Molinari (2024) Liu, Yiqi and Francesca Molinari, “Inference for an Algorithmic Fairness-Accuracy Frontier,” arXiv preprint arXiv:2402.08879, 2024.
  * Mammen (1992) Mammen, Enno, When does bootstrap work?: asymptotic results and simulations, Vol. 77, Springer Science & Business Media, 1992.
  * Mbakop and Tabord-Meehan (2021) Mbakop, Eric and Max Tabord-Meehan, “Model selection for treatment choice: Penalized welfare maximization,” Econometrica, 2021, 89 (2), 825–848.
  * Mitchell et al. (2021) Mitchell, Shira, Eric Potash, Solon Barocas, Alexander D’Amour, and Kristian Lum, “Algorithmic Fairness: Choices, Assumptions, and Definitions,” Annual Review of Statistics and Its Application, 2021, 8, 141–163.
  * Obermeyer et al. (2019) Obermeyer, Ziad, Brian Powers, Christine Vogeli, and Sendhil Mullainathan, “Dissecting racial bias in an algorithm used to manage the health of populations,” Science, October 2019, 366 (6464), 447–453.
  * Romano and Shaikh (2012) Romano, Joseph P and Azeem M Shaikh, “On the uniform asymptotic validity of subsampling and the bootstrap,” 2012.
  * Shoben (1978) Shoben, Elaine W, “Differential pass-fail rates in employment testing: Statistical proof under Title VII,” Harvard Law Review, 1978, pp. 793–813.
  * Viviano and Bradic (2023) Viviano, Davide and Jelena Bradic, “Fair policy targeting,” Journal of the American Statistical Association, 2023, pp. 1–14.
  * Wang and Gupta (2020) Wang, Serena and Maya Gupta, “Deontological Ethics By Monotonicity Shape Constraints,” in Silvia Chiappa and Roberto Calandra, eds., Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Vol. 108 of Proceedings of Machine Learning Research PMLR 26–28 Aug 2020, pp. 2043–2054.


# LC-Score: Reference-less estimation of Text Comprehension Difficulty

Paul Tardy
U31
https://u31.io
<EMAIL_ADDRESS>
&Charlotte Roze
U31
https://u31.io
<EMAIL_ADDRESS>
&Paul Poupet
U31
https://u31.io
<EMAIL_ADDRESS>

###### Abstract

Being able to read and understand written text is critical in a digital era.
However, studies shows that a large fraction of the population experiences
comprehension issues. In this context, further initiatives in accessibility
are required to improve the audience text comprehension. However, writers are
hardly assisted nor encouraged to produce easy-to-understand content.
Moreover, Automatic Text Simplification (ATS) model development suffers from
the lack of metric to accurately estimate comprehension difficulty We present
LC-Score, a simple approach for training text comprehension metric for any
French text without reference i.e. predicting how easy to understand a given
text is on a $[0,100]$ scale. Our objective with this scale is to
quantitatively capture the extend to which a text suits to the Langage Clair
(LC, Clear Language) guidelines, a French initiative closely related to
English Plain Language. We explore two approaches: (i) using linguistically
motivated indicators used to train statistical models, and (ii) neural
learning directly from text leveraging pre-trained language models. We
introduce a simple proxy task for comprehension difficulty training as a
classification task. To evaluate our models, we run two distinct human
annotation experiments, and find that both approaches (indicator based and
neural) outperforms commonly used readability and comprehension metrics such
as FKGL.

##  1 Introduction

The ability to understand text is essential for a wide range of daily tasks.
It enables individuals to stay informed, understand administrative forms, and
have a full, unimpeded access to social and medical care.

Studies shows that a large fraction of the population experiences
comprehension issues in their daily life. Almost half of the OECD population
shows reading and written information comprehension difficulties OECD (2013);
Štajner (2021).

Such difficulties have a major impact in people’s life. In France for example,
the National Statistic Institute INSEE (2012) reports that one person out of
four has already abandoned an administrative procedure deemed too complicated
to follow-along.

In order to improve written text accessibility, initiatives such as Plain
Language111https://plainlanguagenetwork.org/plain-language/what-is-plain-
language or Language Clair (LC, translates to Clear Language) defines writing
guidelines to produce clearer texts. Moreover, comprehension makes its way
into international standards and norms ISO (24495); WCAG (2018) but still
lacks of concrete solution and measurable objectives.

With the rise of deep-learning approaches in natural language processing, as
well as its recent successes in a wide variety of tasks (transcription,
translation, summarization, question answering), Automatic Text Simplification
is an interesting candidate for accessibility improvements at scale. However,
system performances are difficult to measure due to the limitations of current
automatic metrics Alva-Manchego et al. (2021).

We hypothesize that the development of better text comprehension metrics could
provide Automatic Text Simplification researchers with a way of validating
their models while also to giving measurable objectives for the content
editors to write clearer texts.

In this context, we focus our work in developing models for reference-less
text comprehension evaluation as a scoring function for French texts i.e.
$s:\text{text}\mapsto\left[0,100\right]$ reflecting how clearly written a text
is.

In this paper, we present the following contributions:

  * •

We introduce a simple approach to address comprehension evaluation as a
classification task

  * •

We introduce a set of linguistically motivated lexical, syntactic and
structural indicators

  * •

We train both indicator based models and text-based Neural Models

  * •

We evaluate our experiments thanks to two human annotation experiments using
crowd sourced human judgement for one and expert rating for the second.

##  2 Related Work

Defining what makes a text difficult to understand is a complex task by
itself. Multiple approaches are explored, like studying the age at which
children acquires complex syntactic constructions in French Canut (2014); or
relying on standardized foreign language levels such as the Common European
Framework of Reference (CEFR), ranging from A1 to C2. Wilkens et al. (2022)
uses this scale to study French as a Foreign Language difficulty.

In order to improve texts clarity, some organizations produced redaction
guidelines i.e. suggestions of good practices to write clear texts, such as
Plain Language PLAIN  and, in French, Leys (2011). Gala et al. (2020) also
published guidelines for adapting French texts to increase readability and
comprehension. More closely related to our work, Francois and Fairon (2012)
introduced a readability formula for French as a foreign language.

Automatic Text Simplification aims at generating simpler versions of a source
texts. In literature, such models are usually evaluated using automatic
metrics. Therefore, standard language level and redaction guidelines are
hardly suitable to evaluate simplification models since it would require an
expert judgement. Automatic evaluation instead mostly rely on readability
metrics such as FKGL Kincaid et al. (1975), SMOG McLaughlin (1969) and Gunning
fog Index Gunning (1952). Such metrics were designed with English in mind but
can be used on French in practice. On the other hand, SAMSA Sulem et al.
(2018), a semantic metric, is currently not implemented for French, as
discussed in section 3.1.

Other approach include learning regression and classification models Martin et
al. (2018) or pre-trained language models Zhang et al. (2020). However, Alva-
Manchego et al. (2021) found that automatic metrics remains unsuitable to
evaluate progress in Automatic Text Simplification.

##  3 Methods

###  3.1 Baseline metrics

In order to evaluate our work with respect to the literature we take the
following existing readability metrics as baselines: FKGL Kincaid et al.
(1975), SMOG McLaughlin (1969), Gunning Fog Gunning (1952).

The SAMSA metric Sulem et al. (2018) takes semantic into consideration. Even
though it would be theoretically possible to adapt this metric for french, it
is not yet implemented. We tried adapting existing implementation from EASSE
Alva-Manchego et al. (2019) based on CoreNLP Manning et al. (2014) but it
turned out to fail due to the lack of French lemmatization model.

###  3.2 Evaluate text comprehension difficulty as a classification task

Training a model to predict comprehension difficulty would require a text
corpus annotated with comprehension scores. However, to the best of our
knowledge, their is no such corpus for the general audience and of sufficient
size to envision model training. In this context, we suggest to rely on a
simpler proxy task consisting of a classification between simple and complex
texts. Defining what makes a text simple or complex here is difficult. In
order to bypass this question, we uses pairs of content sources such as one is
roughly a simplified version of the other:

#### Encyclopedia articles

based on French Wikipedia (complex) and its simpler alternative, Vikidia
(simple), designed for 8-13 years old readers. We only took into consideration
the introduction paragraph as it is a concise and synthetic presentation of
the article. Articles are aligned i.e. the corpus consists in
$(simple,complex)$ pairs.

#### International Radio Journal Transcriptions

with France Culture international press review (complex) 222
https://www.radiofrance.fr/franceculture/podcasts/revue-de-presse-
internationale and RFI Journal En Français Facile (simple), 333
https://francaisfacile.rfi.fr/fr/podcasts/journal-en-fran%C3%A7ais-facile/
aimed at french speakers that do not speak the language on a daily basis.
Articles have similar subjects (international news) but are not aligned
strictly speaking i.e. there is no $(complex,simple)$ pairs for a given
article. We report statistics about this new corpus in table 1.

Corpus | #T | #W/#T | #W/#S
---|---|---|---
Wikipedia | 25812 | 144 | 26.0
Vikidia | 25812 | 80 | 18.9
France Culture | 1402 | 1106 | 28.8
| Journal en
---
Français Facile
1555 | 1494 | 19.0
Table 1: Comprehension Classification Datasets: number of texts per corpus
($\\#T$), average word per text ($\\#W/\\#T$) and average word per sentence
$\\#W/\\#S).$

###  3.3 Linguistic Indicators

Deriving from works on Langage Clair we introduce a set of complexity
indicators. Indicators varies from lexical difficulties (i.e. a word
difficulty score) to syntactic difficulties or sentences parse tree height.
Indicators are detailed below.

Indicators are detected based on our own rules implementation using SpaCy
pipeline based on both dependency and constituency parsing respectively using
fr-dep-news-trf444https://spacy.io/models/fr#fr_dep_news_trf and
benepar555https://github.com/nikitakit/self-attentive-parser.

#### Lexical Indicators (5)

These are indicators of difficulties at word level. We use a word difficulty
score based on word frequencies in corpora of different difficulty levels:
elementary school textbooks of various grades from Manulex Lété et al. (2004)
and French as a Foreign Language textbooks of various CEFR (Common European
Framework of Reference for Languages) levels from FLELex François et al.
(2014). Lexical indicators also include abbreviations, acronyms, named
entities and numerical expressions.

#### Sentence Length Indicators (3)

We measure sentences lengths with averages of words per sentence; dependency
and constituency tree heights.

#### Syntactic Indicators (17)

Several difficulties on the syntactic level in sentences are identified, which
are related to sentence structure: coordinate clauses, relative clauses,
adverbial clauses, participle clauses, cleft structures, interpolated clauses,
appositive phrases, enumerations, etc.). Information about verb forms are also
detected: non-finite clauses, passive voice, complex verbal tenses,
conditional mood. Negations marks, complex noun phrases and text spans between
brackets are also included in syntactic indicators.

#### Structure Indicators (3)

Two indicators are related to the presence of connectives and their potential
complexity, estimated by syntactic information (e.g. clause position for
conjunction connectives, sentence initial position for adverbial connectives)
and information from a French connectives lexicon Roze et al. (2010). A third
indicator counts temporal breaks (i.e. a tense change) within text paragraphs.

We train models using sklearn: two linear models (Linear SVC and Ridge) for
fairer comparison to linear readability metrics, and 2 non-linear (Random
Forest and Multi Layer Perceptron)

###  3.4 Neural Methods based on Text

Even though indicator-based approaches rely on linguistic motivations, they
lack the possibility to learn from deeper relationships throughout the text
such as the subject, the context and the semantic that might carry essential
information to infer comprehension difficulty. This is the reason why we chose
to compare indicator-based methods with deep learning approaches directly
relying on text.

We use two French pre-trained language models such as BARThez Eddine et al.
(2020) and CamemBERT Martin et al. (2020) fine-tuned with a classification (C)
or a regression objective (R).

##  4 Comprehension Difficulty Annotation

We ran two human annotation experiments in two different contexts: the first
one using Mechanical Turk, a crowd-sourcing platform to receive annotations of
French speakers from general audience (4.1); the second based on the feedback
of Langage Clair experts in our team (4.2).

###  4.1 Crowd-sourced Human Annotation

In order to get the most reliable annotations we follow Kiritchenko and
Mohammad (2017) and use a Best-Worst Scaling (BWS) technique. They recommend
to use comparison task instead of direct assessment i.e. directly giving a
note to a given text. More specifically, BWS compares $k$ (typically $k=4$)
simultaneous examples and asks the annotator to select the best one and the
worst one with respect to the dimension of interest (text comprehension
difficulty in our context).

When annotating texts of up to $200$ words, preliminary experiments showed us
that comparing $k=4$ simultaneous texts was too long and fastidious. In this
light, we reduce to $k=3$.

The annotation counts $T=48$ news articles (up to 200 words). Each text is
present in $e=12$ different examples of $k=3$ texts. Examples are annotated by
$a=3$ separate annotators in a total of $26$. We end up with a total of
$E=(T\times e)/k=192$ examples, and $E\times a$ annotation i.e. for any three
texts $\left\\{T_{a};T_{b};T_{c}\right\\}$ the annotation task consist in
submitting an ordered set e.g. $T_{c}>T_{a}>T_{b}$.

Each text $T_{i}$ is associated with an annotation score by
$score(i)=\\#best\%(i)-\\#worst\%(i)$ with $\\#best\%(i)$ (resp.
$\\#worst\%(i)$) representing the frequency at which $T_{i}$ was evaluated the
best (resp. worst) text out of the 3.

In order to measure the reliability of an annotation experiment, a common
practice is to measure inter-annotation agreement. However, in a BWS process,
each annotators is presented with a different set of examples which makes the
concept of annotator agreement less relevant. Moreover, disagreement is even
beneficial to produce accurate annotation: for two items $A$ and $B$ of
similar difficulty, we can expect half of the annotator to rate $A>B$ and the
other half $B>A$. From this apparent disagreement emerges diversity that
actually reinforce score accuracy. For this reason, BWS is instead evaluated
in terms of reproductibility metrics like Split Half Reliability (SHR). SHR is
the correlation between two randomly sampled half of the annotation. In
practice, we average SHR over $1000$ iterations to rule out randomness.

###  4.2 Expert Annotation

In addition to crowd-sourced corpus, our team built a small corpus of $74$
texts annotated with difficulty scores. We selected $37$ texts originating
from news articles, literature, and customer support mails. In addition, we
provide $37$ manually simplified versions following Langage Clair methodology.
Each of the $74$ resulting texts were then scored on a $\left[0,100\right]$
scale by $4$ LC experts from our team.

To make sure we obtained good quality annotation, we measure annotator
agreement with Intra-class Correlation Coefficient (ICC2, Shrout and Fleiss,
1979). ICC2 ranges from $0$ (no agreement) to $1$ (perfect agreeement).

##  5 Results

###  5.1 Annotation results

Annotations experiments text length metrics and reliability measure are
reported in table 2.

#### Good reliability from MTurk and Expert

even though our annotation experiments are very different in terms of
annotators and process, both shows high reliability measures achieving
respectively an SHR correlation of $64.7$ (MTurk) and an Intraclass
Correlation Coefficient of $74.6$ (Experts).

#### Filtering MTurk workers does not increase reliability

A common practice when involving crowd-sourced annotation is to filter-out
users that shows the lowest agreement. Even though we discussed in 4.2 that
agreement is not considered to be the most relevant metric for BWS annotation,
we challenge this hypothesis by calculating worker agreement rate based on how
often a given user submits the same result than another worker. Then, we
suppose that workers with the lowest agreement rate might add noise to the
experiment so we might want to exclude them. However, results showed the
opposite: filtering out workers does not increase reliability in terms of SHR,
no matter the agreement rate of each. This observation is in line with the
hypothesis that annotator disagreement is expected and beneficial in a BWS
annotation experiment.

| MTurk | Expert
---|---|---
#T | 48 | 37 / 37
#W/#T | 183 | 190 / 209
#W/#S | 25 | 28 / 13
#Annotators | 26 | 4
Type | BWS | RS
Reliability Measure | SHR | ICC2
Reliability | 64.7 | 74.6
Table 2: Human Annotation Experiments. Corpus are reported with number of
texts per corpus ($\\#T$), average word per text ($\\#W/\\#T$) and average
word per sentence $\\#W/\\#S)$. Since Expert is aligned, metrics are reported
for both sides. Experiments uses two different annotation processes (i) Best
Worst Scaling (BWS) evaluated in term of Split Half Reliability (SHR) and (ii)
Rating Scale in $[0,100]$ (RS, 100 is best) evaluated with Intraclass
Correlation Coefficient (ICC2).

###  5.2 Scoring results

First, we evaluate model performances with respect to their own training by
measure accuracy on their validation set: a $10\%$ held-out subset from the
training set. Validation accuracy is used to select the best hyper-parameters
and training iterations for each models.

Models are then evaluated against human annotations from MTurk and Experts
using Spearman Rank Correlations ($\rho$).

Results are reported in Table 3. Our approaches show better correlations with
the human judgement than readability metrics. Models trained from indicators
achieves the highest correlations, with Random Forest being the best on both
evaluation sets, MTurk and Expert.

It is also interesting that even simple linear statistical models based on our
indicators outperforms readability metrics therefore arguing in favor of this
indicator set. In particular, the Ridge Regression model outperform FKGL by
$14.76$ and $10.55$ correlation point respectively on MTurk and Expert.

Readability metrics seems complementary in that FKGL achieve better
correlation on MTurk evaluation while Gunning Fog does on Expert.

Similarly, we observe sensible differences between Camembert training
objectives, with the regression (R) being better on MTurk and classification
(C) on Expert.

Model |  Valid $acc\%$ |  MTurk $\rho$ |  Expert $\rho$
---|---|---|---
SMOG | - | -18.68 | -73.09
Gunning Fog | - | -12.59 | -82.14
FKGL | - | -19.66 | -77.54
Linear SVC | 73.07 | 20.94 | 69.37
Ridge | - | 27.58 | 86.44
MLP | 75.31 | 32.56 | 85.73
Random Forest | 77.20 | 34.42 | 88.09
BARThez | 79.64 | 23.16 | 58.41
Camembert(R) | 91.01 | 28.35 | 75.85
Camembert(C) | 90.15 | 18.44 | 84.73
Table 3: Scoring models Spearman correlations ($\rho$) with human judgement.
(C) and (R) respectively indicates classification and regression training
objective.

##  6 Discussions

Results shows a large improvement of human judgement correlation in favor to
our approaches over existing readability metrics. Moreover, indicator based
method outperform neural models fine-tuned from pre-trained model. Neural
models’ results are promising and could be extended with longer training time
and adapting their training objective to produce equally distributed scores.

In addition to outperforming neural models, indicator based model are far
cheaper to train and predict with since they does not require GPU. Being
indicator-based makes it easier to interpret and more predictable than neural
models, and thus might deliver a better user experience. We observed Neural
models we trained tend to produce very polarized output probabilities i.e.
either very close to $0$ or to $1$. That’s not a problem to quantitatively
evaluate the resulting score, but it should probably be adapted to output
equally distributed scores in order to be more intuitive.

##  7 Conclusion

Developing methods to accurately measure written text comprehension difficulty
is a key challenge that would help better assessing the quality of Automatic
Text Simplification models, and provide with a tool for editors to produce
texts that are simpler to understand.

We explore multiple approaches for training a reference-less metric based on a
simple classification task. Our systems rely either on linguistic indicators
or directly from text.

To evaluate our models, we two human annotation experiments. The first
involves crowd-sourced workers, asked to compare text based on their
comprehension difficulties using Best Worst Scaling with $k=3$. In the second
experiment, texts are simplified then rated on a $[0,100]$ scale by experts
from our team.

Both neural and indicator based methods shows promising results and largely
outperform other broadly used readability metrics, on both crowd-sourced and
expert human annotations. Even simple linear models largely outperform
readability metrics which adds an evidence against using it to estimate text
comprehension complexity.

As further researches, we suggest exploring multi-lingual neural training.
This would have the obvious benefit of overcoming the language restriction of
our work while also mutualizing learning from each language and unifying
comprehension difficulties estimation accross languages.

##  8 Lay Summary

Nowadays, most services use the Internet as their primary way of
communicating. Therefore, being able to read and understand texts is really
important. But a lot of people have difficulties reading and understanding so
it is not simple for them to access information or complete administrative
procedures.

We introduce a method to calculate a difficulty score for French texts. A
score of 0 means that the text is really difficult to understand, whereas a
score of 100 means it is really clear. We suggest that developing such a score
is a first step toward helping people write easier texts. We gathered two
categories of texts: some that we consider easy to understand and others that
we consider difficult to understand. Then, we trained models to predict
whether a text is categorized as “easy” or not. After training, we use the
predictions as our scoring method: the score corresponds to the probability
(multiplied by 100) that a text is categorized as easy by the model.

We explored two kinds of models. For the first one, we count different kinds
of linguistic difficulties and give them to the model to predict the
difficulty. The second kind of model is deep neural networks that have already
been trained to learn French. We specialize it in predicting the difficulty
based on the text by providing examples of texts and their difficulties.

To measure how relevant our models are, we asked people on the Internet as
well as experts to give their opinions on texts. In particular, they were
given texts and should determine how difficult they are. We found that people
agreed more with our method’s scores than with other existing scoring methods.

## References

  * Alva-Manchego et al. (2019) Fernando Alva-Manchego, Louis Martin, Carolina Scarton, and Lucia Specia. 2019.  EASSE: Easier Automatic Sentence Simplification Evaluation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP): System Demonstrations_ , pages 49–54, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Alva-Manchego et al. (2021) Fernando Alva-Manchego, Carolina Scarton, and Lucia Specia. 2021.  The (Un)Suitability of Automatic Evaluation Metrics for Text Simplification.  _Computational Linguistics_ , 47(4):861–889.
  * Canut (2014) Emmanuelle Canut. 2014.  Acquisition des constructions syntaxiques complexes chez l’enfant français entre 2 et 6 ans.  _SHS Web of Conferences_ , 8:1437–1452.
  * Eddine et al. (2020) Moussa Kamal Eddine, Antoine J. P. Tixier, and Michalis Vazirgiannis. 2020.  BARThez: a Skilled Pretrained French Sequence-to-Sequence Model.
  * Francois and Fairon (2012) Thomas Francois and Cedrick Fairon. 2012.  An “AI readability” formula for French as a foreign language.  In _EMNLP-CoNLL 2012 - 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, Proceedings of the Conference_ , pages 466–477.
  * François et al. (2014) Thomas François, Nùria Gala, Patrick Watrin, and Cédrick Fairon. 2014\.  FLELex: a graded lexical resource for French foreign learners.  In _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , pages 3766–3773, Reykjavik, Iceland. European Language Resources Association (ELRA).
  * Gala et al. (2020) Núria Gala, Amalia Todirascu, Ludivine Javourey-Drevet, Delphine Bernhard, Rodrigo Wilkens, Jean-Paul Meyer, and Al Recommandations. 2020.  Recommandations pour des transformations de textes français afin d’améliorer leur lisibilité et leur compréhension.
  * Gunning (1952) Robert Gunning. 1952.  The technique of clear writing.  _1952_ , page 289.
  * INSEE (2012) INSEE 2012. 2012.  Pour les générations les plus récentes, les difficultés des adultes diminuent à l’écrit, mais augmentent en calcul.  Standard, INSEE.
  * ISO (24495) ISO 24495. 2023.  Plain language – Part 1: Governing principles and guidelines.  Standard, International Organization for Standardization.
  * Kincaid et al. (1975) J. P. Kincaid, R. P Fishburne, R. L Rogers, and B. S Chissom. 1975.  Derivation of new readability formulas for navy enlisted personnel.  _Naval Technical Training Command Millington TN Research Branch_.
  * Kiritchenko and Mohammad (2017) Svetlana Kiritchenko and Saif Mohammad. 2017.  Best-Worst Scaling More Reliable than Rating Scales: A Case Study on Sentiment Intensity Annotation.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , volume 2, pages 465–470, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Lété et al. (2004) Bernard Lété, Liliane Sprenger-Charolles, and Pascale Colé. 2004.  MANULEX: a grade-level lexical database from French elementary school readers. _Behavior Research Methods Instruments and Computers_ , 36(1):156–66.
  * Leys (2011) Michel Leys. 2011.  Écrire pour être lu : comment rédiger des textes administratifs faciles à comprendre?  Technical report, Fédération Wallonie-Bruxelles.
  * Manning et al. (2014) Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014.  The stanford CoreNLP natural language processing toolkit.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , volume 2014-June, pages 55–60. Association for Computational Linguistics (ACL).
  * Martin et al. (2018) Louis Martin, Samuel Humeau, Pierre Emmanuel Mazare, Antoine Bordes, Eric De La Clergerie, Sagot Benoit, Pierre-Emmanuel Mazaré, and Antoine Bordes. 2018\.  Reference-less Quality Estimation of Text Simplification Systems.  In _ATA 2018 - 1st Workshop on Automatic Text Adaptation, Proceedings of the Workshop_ , pages 29–38. Association for Computational Linguistics (ACL).
  * Martin et al. (2020) Louis Martin, Benjamin Muller, Pedro Javier Ortiz Suárez, Yoann Dupont, Laurent Romary, Éric Villemonte de la Clergerie, Djamé Seddah, and Benoît Sagot. 2020.  CamemBERT: A tasty French language model.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , pages 7203–7219. Association for Computational Linguistics (ACL).
  * McLaughlin (1969) G.H. McLaughlin. 1969.  SMOG grading: A new readability formula.  _Journal of reading_ , 12(8):639–646.
  * OECD (2013) OECD 2013. 2013.  OECD Skills Outlook 2013 – First Results from the Survey of Adult Skills.  Standard, OECD.
  * (20) PLAIN. 2023.  Federal Plain Language Guidelines.  Standard, Plain Language Action and Information Network (PLAIN).
  * Roze et al. (2010) Charlotte Roze, Danlos Laurence, and Philippe Muller. 2010.  LEXCONN: a French Lexicon of Discourse Connectives.  In _MAD 2010 - 8th Workshop Multidisciplinary Approaches to Discourse_ , Proceedings of the 8th Workshop Multidisciplinary Approaches to Discourse (MAD 2010), pages 114–125, Moissac, France.
  * Shrout and Fleiss (1979) Patrick E. Shrout and Joseph L. Fleiss. 1979.  Intraclass correlations: Uses in assessing rater reliability.  _Psychological Bulletin_ , 86(2):420–428.
  * Štajner (2021) Sanja Štajner. 2021.  Automatic Text Simplification for Social Good: Progress and Challenges.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 2637–2652.
  * Sulem et al. (2018) Elior Sulem, Omri Abend, and Ari Rappoport. 2018.  Semantic structural evaluation for text simplification.  In _NAACL HLT 2018 - 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Proceedings of the Conference_ , volume 1, pages 685–696.
  * WCAG (2018) WCAG 2018. 2018.  Web Content Accessibility Guidelines (WCAG) 2.1 – 3.1 Understanding.  Standard, W3C.
  * Wilkens et al. (2022) Rodrigo Wilkens, David Alfter, Xiaoou Wang, Alice Pintard, Anaïs Tack, Kevin Yancey, and Thomas François. 2022.  FABRA: French Aggregator-Based Readability Assessment toolkit.
  * Zhang et al. (2020) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020\.  Bertscore: Evaluating Text Generation With Bert.  _8th International Conference on Learning Representations, ICLR 2020_.