Khaled Belahcene
email: khaled.belahcene@hds.utc.fr

Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Explications de recommandations fondées sur des principes d'équité à l'aide de transferts Hénoïk Willot

Nous explorons la génération d'explication pour des préférences basées sur un modèle de somme pondérée ordonnée (OWA) favorisant une répartition équilibrée des performances relatives à différents points de vue. Nous proposons des explications, correctes vis-à-vis du modèle, fondées sur la composition par transitivité d'arguments élémentaires fondés sur la dominance de Pareto, des transferts de Pigou-Dalton, et l'information préférentielle fournie par le décideur. Nous proposons plusieurs approches heuristiques permettant de calculer ces explications, validées par une campagne expérimentale montrant que les explications obtenues sont souvent de longueur optimale.

Introduction

Our aim is to propose explanation tools for recommendations based on preference aggregation. The need for decision-theoretic recommender systems-tools helping decision makers to formalize and support their judgment in a principled manner-has in turn given rise to a need for tools allowing people-be they actors of the decision process, or third parties impacted by it-to understand, scrutinize, validate or contradict the functioning of such recommender systems.

Preference aggregation is the process of merging comparative judgments expressed from various points of view into a single ranking. Points of view can represent various aspects of a situation (such as in multiple criteria decision aiding-MCDA), be expressed by various agents, or several possible worlds when modelling uncertainty. In turn, the aggregated judgment can be used as a basis for decision, supporting tasks such as choosing the best alternative, comparing them, or sorting them into ordered categories [START_REF] Bouyssou | Evaluation and decision models with multiple criteria : Stepping stones for the analyst[END_REF].

The MCDA literature usually distinguishes three approaches to aggregation : "aggregate then compare", where judgments are normatively described as complete preorders and described numerically with a score-the higher, the better-and the aggregator is a multi-attribute utility function [START_REF] Keeney | Decisions with multiple consequences : preferences and value tradeoffs[END_REF] ; "compare then aggregate", where the aggregated judgment is represented by an outranking relation constructed from the preference profiles [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF] ; and models based on logic. Following the numeric approach, it is customary to decide on several high-level features of the aggregator-either technical, such as possessing an additive form [START_REF] Krantz | Foundations of measurement, tome 1 : Additive and polynomial representations[END_REF] , or decision-theoretic, such as being compatible to Pareto-dominance, satisfying anonymity or idempotence, etc. Usually, these requirements are chosen so as to define, either directly or indirectly via a representation theorem, a parametric family of aggregators. When the decision task requires to be able to compare any two alternatives, the usual approach, called preference elicitation, is to select a specific, precise value of the preference parameter. It is common to use indirect elicitation techniques, where the aggregator is fitted to preference information (PI) given by the decision maker in the form of comparative statements about alternatives, as opposed to statements concerning the parameters [START_REF] Jacquet-Lagreze | Assessing a set of additive utility functions for multicriteria decisionmaking, the UTA method[END_REF]. Full elicitation is not mandatory, though : skeptical recommendations can be derived considering the whole set of aggregators of the family that are compatible to the PI.

In the context of MCDA, Belahcene et al. have recently shown that, for the class of additive aggregators, it is possible to provide structured explanations where elementary arguments are organized according to a specific scheme. In [START_REF] Belahcene | Explaining robust additive utility models by sequences of preference swaps[END_REF], an explanation of a comparative statement is a decomposition into elementary swaps linked together by transitivity. In [START_REF] Belahcène | Comparing Options with Argument Schemes Powered by Cancellation[END_REF], an explanation is a decomposition into preference statements committed by the decision maker, assembled together by a high-order cancellation property.

When points of view are assessed on the same scale, the Choquet integral is a convenient class of aggregators, offering a good mixture of expressiveness, interpretabilty and computational tractability [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF]. We focus on the subclass of anonymous aggregators, where the respective identities of the points of view play no role into their aggregation. Evaluations can be permuted, and the importance of a given score is related to its rank in the ordering of scores. These aggregators are thus named ordered weighted average (OWAs). Introduced in MCDA by Yager [START_REF] Yager | On Ordered Weighted Averaging Aggregation Operators in Multicriteria Decisionmaking[END_REF], they form a family of function parameterized by a tuple of weights, one per criteria, similarly to the weighted sum, and encompass the minimum, maximum, median and mean operators as particular cases. Moreover, by imposing the weights to be non-increasing w.r.t. the rank, it is possible to favour balanced scores over imbalanced ones, thus representing a sense of fairness. The explanatory engine described in [START_REF] Belahcene | Explaining robust additive utility models by sequences of preference swaps[END_REF] relies on swaps between criteria and is inspired by the notion of even swaps [START_REF] Hammond | The Even-Swap Method for Multiple Objective Decisions[END_REF]. In the field of welfare economy, many methods and criteria are used to rank sets of incomes depending on the distribution of wealth among agents. The Pigou-Dalton principle [START_REF] Shorrocks | Ranking Income Distributions[END_REF] provides a similar notion of acceptable transfers in this context : the inequality between agents is reduced when a rich agent gives a small portion ϵ of its wealth to a poorer agent.

Our contribution is the definition of structured explanations for recommendations based on fairness-oriented OWAs. We propose to arrange comparative statements based on Pareto dominance, Pigou-Dalton transfers, and PI into a transitive structure. We begin by introducing the OWA operator, the Pigou-Dalton Principle and other definitions we will use in Section 2. In Section 3, we deal with the case where preference and explanations can be constructed without relying on preference information, and propose a heuristic to compute short explanations. In section 4, we address the case where preference is inferred from PI, and propose to find an additive decomposition of a comparative statement as an intermediate step towards finding a transitive explanation. Finally we will run an example combining both in Section 5 and give some insight about the performances of the method in Section 6.

Preliminaries

Ordered Weighted Averages

In this section we will introduce the decision problems and the formulation of the OWA operator. The MCDA problem we consider is ranking alternatives over a set of n criteria, defined on the same domain X, which can be [0, 1] or R. The model of preference should then create an order over the candidates represented by their vectors x ∈ X n . Definition 1 (Reordering function). We define the reordering function ↑ as the permutation function over

X n s.t. x → x ↑ with x ↑ 1 ≤ x ↑ 2 ≤ • • • ≤ x ↑ n .
We denote by X n↑ the domain of such vectors x ↑ . Definition 2 (Ordered Weighted Average [START_REF] Yager | On Ordered Weighted Averaging Aggregation Operators in Multicriteria Decisionmaking[END_REF]). The OWA operator is a function X n → R + defined by a vector of weights w ∈ W s.t. ∀ i w i ∈ [0, 1] and n i=1 w i = 1 :

OWA w (x) = n i=1 w i x ↑ i
Even if it is presented as a weighted sum, thanks to the reordering function ↑ the weights are assigned to the rank of the criteria, allowing to represent non linear preference operators, such as the min operator w min = (1, 0, . . . , 0), the max operator w max = (0, . . . , 0, 1), and in general any quantile as well as the arithmetic mean operator w mean = ( 1 n , . . . , 1 n ). Definition 3 (Fairness-oriented OWA (FOWA)). An OWA operator is fairness-oriented if its weight vector w also satisfy w 1 ≥ w 2 ≥ • • • ≥ w n . We note by W ↘ ⊂ W the domain of such weights.

A FOWA represents preferences oriented toward equity because, with a higher emphasis put on the smaller values, it gives higher scores to vectors with balanced values than to vectors where modalities are concentrated on a small subset of criteria. We can note that an increase in a small variable has a bigger impact on the aggregated value than the same increase in a big variable, i.e.

∀ i < j OWA w (x ↑ + k × e i ) ≥ OWA w (x ↑ + k × e j )
, with e l the vector that is one for its l th element and zero everywhere else.

Definition 4 (Ranking relation). We define the ranking relation ⪰ w induced by the operator OWA w by : a ⪰ w b ⇐⇒ OWA w (a) ≥ OWA w (b) Example 1. The Decision Maker is asked to rank students over their results (scaled between 0 and 1) in 3 main courses {"Science", "Literature", "Language"}. She prefers students who are balanced between the 3 courses, and with an analyst the OWA with the following vector of weights has been designed : w = (0.6, 0.3, 0.1).

If we consider three students a, b and c such that a = (0.7, 1, 0.5), b = (0.7, 0.7, 0.7) and c = (1, 0.7, 0.8). Their scores defined by the OWA w will be computed on their reordered vectors a ↑ = (0.5, 0.7, 1), b ↑ = (0.7, 0.7, 0.7) and c ↑ = (0.7, 0.8, 1), and are :

OWA w (a) = 0.5 × 0.6 + 0.7 × 0.3 + 1 × 0.1 = 0.61 OWA w (b) = 0.7 × 0.6 + 0.7 × 0.3 + 0.7 × 0.1 = 0.7 OWA w (c) = 0.7 × 0.6 + 0.8 × 0.3 + 1 × 0.1 = 0.76
Therefore we obtain the preferences c ⪰ w b ⪰ w a.

In this example, we do not exactly know why the weight vector was w = (0.6, 0.3, 0.1). The issue with determining a specific set of weights is that it produces a total preorder (with possible ties) and may produce knowledge that the DM is not aware of and could potentially disagree with. Furthermore, obtaining precise values is cognitively demanding and require strong efforts. To circumvent this problem of finding the right set of weights, we can robustify our model using a set of models [START_REF] Mitchell | Generalization as search[END_REF]. The set of OWA is defined as the set which respects the information obtained from the DM, her preferential information (PI), through an interactive process. In our case of study, the information collected is of the shape of m preference statements a j ⪰ PI b j , j ∈ {1, . . . , m}, with a j , b j alternatives.

Definition 5 (Robust OWA). We define a robust OWA operator the set W PI ⊆ W of OWA weights :

W PI = {w ∈ W : ∀ j ∈ {1, . . . , m} a j ⪰ w b j }
And we note W ↘ PI = W ↘ ∩ W PI As we now have a set of models instead of a single vector of weights, we have to adapt our process for producing preferences. We can define two relations of preferences from the set W PI , a necessary and a possible preference relations [START_REF] Giarlotta | Necessary and possible preference structures[END_REF]. In this paper we only focus on the necessary preference.

Definition 6 (Necessary preference). We define the necessary preference N OWA ↘ PI of a robust FOWA with respect to preference information PI as :

aN OWA ↘ PI b ⇔ ∀w ∈ W ↘ PI , a ⪰ w b
In order to compute the set W PI and to reason with the necessary preference relation N OWA ↘ PI , we can adapt the GRIP method [START_REF] Figueira | Building a set of additive value functions representing a reference preorder and intensities of preference : GRIP method[END_REF] that allows to decide whether a pair of alternatives belongs to the necessary preference relation, given some PI, for the additive value model, by solving a linear program 1 . In fact, to represent OWA operators, we only need to feed the method with vectors already reordered by ↑ , and for the representation of FOWA operators we need to add n -1 linear constraints w i ≥ w i+1 2 , i ∈ {1, . . . , n -1} to constraint the weights of the additive value function in the linear program to be decreasing.

Pigou-Dalton Principle and Dominance relations

In this section we will first connect the OWA aggregators to the Pigou-Dalton principle. To do so, we will introduce the dominance relations and the Pigou-Dalton principle that we will use in our explanation engine and its potential use cases.

1. Such a LP formulation could already be found in [START_REF] Greco | Ordinal regression revisited : Multiple criteria ranking using a set of additive value functions[END_REF], but we opt to use the more streamlined formalism of GRIP.

2. to follow the GRIP methods notations, the constraints are

u i (β i ) - u i+1 (β i+1 ) ≥ 0
The Pigou-Dalton Principle was first introduced in welfare economic problem, where the components of the vector to compare are the incomes of economical agents, ranked from bottom to top [START_REF] Shorrocks | Ranking Income Distributions[END_REF]. In this context, the Pigou-Dalton Principle defines a relation ⪰ PDP between two distributions over n agents.

Definition 7 (Pigou-Dalton Principle). Let x be the income vector of n agents such that x = (x 1 , . . . , x n ),

x 1 ≤ x 2 ≤ • • • ≤ x n .
The vector x ′ is favoured to x by the Pigou-Dalton Principle, noted x ⪯ PDP x ′ if there exists points of view i, j ∈ {1, . . . , n}, i < j and quantity ϵ > 0 s.t. :

         ∀k ∈ {1, . . . , n}, k i, k j, x ′ k = x k ; x ′ i = x i + ϵ ≤ x i+1 ; and x ′ j = x j -ϵ ≥ x j-1 .
When these conditions are met, we also use the notation

x j→i ⪯ PDP
x ′ to account for the witnesses i and j.

The Pigou-Dalton Principle therefore favours vectors of incomes where a "rich" agent j gives a positive portion ϵ of its wealth to a "poorer" agent i in order to reduce the inequality. We also add explicitly another constraint on ϵ which is not always clear in the literature : the order in the distribution is preserved, x j -ϵ ≥ x j-1 and x i + ϵ ≤ x i+1 . This principle of equity is respected by FOWA operators as we discussed earlier after definition 3.

We will now introduce two preorders relations, compatible with FOWA operators, which will be used by our explanation engine : the Pareto and Lorenz dominance, denoted respectively as ⪰ P and ⪰ L .

Definition 8 (Pareto-dominance). ∀a, b ∈ X n , a ⪰ P b ⇐⇒ ∀i ∈ {1, . . . , n} a i ≥ b i
Pareto dominance embodies the desirable property of monotonicity of a preference aggregator : if an alternative is better on every aspect than another, then it should be preferred. Definition 9 (Lorenz vector). We call the Lorenz vector of a candidate a the cumulative vector L(a) of R n whose components are defined by : L(a) i = We can note that the Lorenz-dominance is a partial preorder, as neither a or b Lorenz-dominates the other.

FOWA operators are highly linked to Lorenz Dominance as shown by Golden and Perny [START_REF] Golden | Infinite order Lorenz dominance for fair multiagent optimization[END_REF].

Proposition 1 (Reformulation from Lemma 2 in [6] ). a ⪰ L b ⇔ ∀w ∈ W ↘ a ⪰ w b ⇔ aN OWA ↘ ∅ b
Therefore, with proposition 1 we have that the Lorenzdominance is compatible to any FOWA operator, meaning that these results will also appear in robust FOWA but are not depending on the DM preferential information. This first set of results makes up the core of our explanatory engine described in Section 3.

Transitive explanations for Lorenz dominance

In this section we will present an algorithm which computes efficiently an explanation for a Lorenz dominance in the form of a transitive chain of transfers using the Pigou-Dalton Principle. The former is only a small part of the results a robust FOWA can produce and the rest will be addressed in section 4.

We saw from proposition 1 that some results, those corresponding to the Lorenz dominance ⪰ L , are compatible with every FOWA operator. It naturally follows that these results, will appear in the necessary preferences of any robust FOWA operator. It has also be known since the 1960s that the Lorenz dominance and the Pigou-Dalton Principle are closely related. [START_REF] Moyes | Gini or Lorenz : Does it make a difference for inequality measurement[END_REF], reformulation from Proposition 3.1 ). a ⪰ L b iff there exists a transitive explanation (x 0 , . . . , x k+1 ) ∈ X n↑ using Y = {⪰ PDP , ⪰ P } In [START_REF] Moyes | Gini or Lorenz : Does it make a difference for inequality measurement[END_REF], Lorenz dominance is only considered over alternatives which have the same last value in their Lorenz vectors, i.e. for which the sum of all values is the same. As we want the scope of our explanation engine to be as broad as possible, we imbue it with the capability of inserting Pareto dominance statements in the explanation sequence to overcome this limitation and deal with the potential surplus.

Definition 11 (Transitive explanation (TE)). Given a set of binary relations over alternatives Y, we call transitive explanation of a

⪰ b using Y, a tuple (x 0 , . . . , x k+1 ) ∈ (X n ) k+2 such that a = x 0 , b = x k+1 , ∀i ∈ {1, . . . , k}x i R i x i+1 , with R i ∈ Y Proposition 2 ([
From proposition 2, we can build a transitive sequence of preferences, a transitive explanation, combining only progressive Pigou-Dalton transfers and Pareto dominance to explain every pair (a, b) such that a ⪰ L b. Note that, because of the equivalence in proposition 1, the Lorenz-dominated alternatives are exactly the ones for which explanations can solely be based on Pareto and Pigou-Dalton transfers and we will need other explanation mechanisms to explain necessary preferences of a robust FOWA operator when alternatives are not Lorenzdominated. As Pigou-Dalton transfers only redistribute a portion ϵ among candidates without breaking the order of criteria, and as Pareto dominance is only here to remove the surplus that can remain between the last intermediate candidate and b, every intermediate candidate from (x 0 , . . . , x k+1 ) is within X n↑ .

Hence this sequence can be presented to the DM as an explanation because :

-it is of finite length ; -the mechanisms are plausible, given the explainee adheres to the principles of monotonicity and fairness they embody ; -the mechanisms used are of small cognitive load (Pareto dominance does not require any trade-off, while a Pigou-Dalton transfer can be described as occurring between two points of view, ignoring the rest) ; and -the intermediate candidates used are plausible, even though they are not present in the set of candidates to rank.

The question of finding an algorithm to build a (not necessarily unique) sequence of Pigou-Dalton transfers has been answered in a close but not identical domain, on a problem called Majorization [START_REF] Marshall | Inequalities : Theory of Majorization and Its Applications[END_REF]. It is defined as a preorder over vectors using their values reordered in a decreasing way, so if we take similar notations as in definition 1 we would be dealing with vectors x ↓ . Majorization a ⪰ M b occurs when, for each criterion k, we have

k i=1 a ↓ i ≥ k i=1 b ↓ i . The link with our problem is therefore clear as a ⪰ M b ⇔ b ⪰ L a.
In this context, the majorization is explained using a sequence of "Robin Hood transfers", which are Pigou-Dalton transfers, produced with a polynomial time algorithm. Without going into the mathematical details, we can give simply the idea of their (Lorenz-revisited) algorithm. We have a ⪰ L b, which means that a is more balanced than b. Especially, we can find some index j where b ↑ j > a ↑ j , and some index k < j where a ↑ k > b ↑ k . The idea is to perform an exchange between these two points of view of a quantity wich is as large as possible, i.e. ϵ = min(a

↑ j -b ↑ j , b ↑ k -a ↑ k ).
Their idea for choosing suitable values for j and k is left vague ; it is usually the smallest j possible and for this j the biggest k possible.

We can pinpoint three possible drawbacks :

1. the value of ϵ does not guarantee the candidate built by the transfer to be ordered ;

2. it is limited to the case where n i=1 a i = n i=1 b i ; and 3. the algorithm will find a sequence but does not aim at making it short.

Point #2 can easily be solved by allowing the explainer to use arguments based on Pareto dominance. However, this increase in flexibility makes point #3 even more prominent. Indeed, we have more flexibility in finding the criteria k so that k i=1 a ↓ i ≥ k i=1 b ↓ i as we have "surplus" (non zero Pareto-dominance implies n i=1 a i > n i=1 b i ). We now present our (heuristic) Algorithm 1, which is similar to the idea given above but tries to solve the three points mentioned. A natural idea consists in minimizing the length of the explanation, but this problem seems computationally hard, even though we were not able to assess its theoretical difficulty. Consequently, we propose a heuristic method to compute short transitive explanations for a Lorenz dominance statement. In Section 6, we compare this heuristic to a A* algorithm computing an explanation of proven minimal length. Experiments tend to show we achieve nearly minimal length in a fraction of the time required to perform the exact search.

By focusing on Pigou-Dalton transfers occurring between variables which can receive (Step 1) or give (Step 3 (I)) the complete difference with the loser we ensure that the candidate obtained after the transfer is ordered. It also allows us to have a maximum length of explanation of n. Indeed at each step we remove at least one criteria from the set of criteria on which there is a non zero difference with the looser, bounding the explanation by the cardinal of this set, itself bounded by the number n of criteria.

Once we cannot find a rank j for which the attribute value x j is bigger than b j , we remove every surplus that could exists with a single Pareto dominance statement. Unfortunately, our heuristic algorithm does not always leads to the smallest explanation length as shown in example 3.

Example 3. In the same context as example 1, we want to rank students, this time over their grades in 5 courses. The two students at hand are d = (0.6 0.7 0.5 0.7 0.8) and e = (0.8 1 0.6 0.4 0.4). It is easy to compute that d ⪰ L e, therefore we can apply our algorithm 1 and a A* search to have two explanations.

ϵ k = x k -b k (II) Find the index k ′ ∈ K allowing to perform the biggest trade ϵ = max k ′ ∈K min(ϵ j , ϵ k ′ ) (if draws take the largest index) (III) X = (x 1 , . . . , x k ′ -ϵ, . . . , x j + ϵ, . . . , x n ) (IV) If we don't have X ⪰ L b, go back to (II) to find another index in K \ {k ′ } (V) x = X ; C = C j→k ′ ⪰ PDP x 4 Go back to Step 2 5 Compute K, the set of indices k s.t. x k > b k 6 If K ∅ : C = C ⪰ P b
We reverse the explanation returned by the algorithm as it is easier to read and understand when the Pigou-Dalton transfers are performed in the reading direction. We note with i the criterion receiving and i the criterion giving. We obtain for our algorithm the explanation : In conclusion, our algorithm 1 computes in polynomial time a chain of Pigou-Dalton transfers and Pareto dominance statement to explain any Lorenz dominance statement with a bounded length of n statements. The length of the explanation is unfortunately not minimal, but the true minimal length can be computed for example with a A* algorithm over a graph exponential in size in the number of criteria.

As we saw previously, Lorenz dominance statements form a subset of the preference yielded by a robust FOWA aggregator, missing the part entailed by the specific PI obtained from the decision maker. Thus the idea we will deve-lop in Section 4 is to complete Pigou-Dalton transfers and Pareto dominance with a combination of statements deduced from the PI to produce a sequence of preferences, or at least a decomposition of preferences, to explain every necessary preference statements obtained by a robust FOWA operator.

Additive and transitive decompositions of necessary preference statements

In this section we introduce and justify a linear programming model producing decompositions for every necessary preference statement compatible with the robust FOWA W ↘ PI ⊆ W ↘ constrained by the PI. We start by introducing the notion of decomposition, which is weaker than the one of transitive explanation, we then try to assemble them into a transitive sequence of preferences. We will first introduce notations for the problem, then we present the model and finally we explain every variable and constraint and discuss it.

The problem we want to solve is finding an explanation for the necessary preference statement c N OWA ↘ PI d, c, d ∈ X n . We have 3 mechanisms at our disposal : PI statements provided by the DM, Pigou-Dalton transfers and Pareto dominance. Trying to find directly a valid transitive explanation (x 0 , . . . , x k+1 ) ∈ X n↑ using {⪯ P , ⪯ PDP , ⪯ PI } is a difficult planning problem, so we begin by building an additive decomposition of this statement.

Definition 12 (Decomposition). We call decomposition of a ⪰ b by Y, Y a set of explanation mechanisms, the "protoexplanation" defined by : ∀i ∈ {1, . . . , n} a ib i = y∈Y γ yi γ y is the contribution vector of explanation mechanism y to the preference a ⪰ b Remark 1. If we take a transitive explanation {x 0 , . . . , x k+1 } of a ⪰ b using Y, we have a = x 0 , b = x k+1 and ∀ j ∈ {0, . . . , k} x j R j x j+1 , R k ∈ Y. We can rewrite the latter as x jx j+1 = γ R j . By summation we obtain ab = k j=0 x jx j+1 = k j=0 γ R j . Therefore an only decomposition based "proto-explanation" is weaker than a transitive explanation in the sense that any transitive explanation can be rewritten as a decomposition.

As we have seen, invoking the anonymity of the model, we rewrite the statement a j ⪰ PI b j by a j↑b j↑ . We can then build a m × n matrix PI containing these m statements. Abusing notations, we will use interchangeably the set of statement PI and the matrix PI. Previously, when we wanted to compute necessary and possible preference statements (with the GRIP method), we used the PI as a constraint to find the necessary relation, so we used (a j↑b j↑ ) × w ≥ ⃗ 0 as a constraint of the model. Here however we will interpret the statement a j↑b j↑ = PI j as a trade-off between ranks of attributes, for which the DM agreed it increases the quality of a candidate. This positive trade-off could be interpreted ceteris paribus as an argument in support of having x ↑ + PI j preferred to x ↑ , for any alternative x ∈ X n , provided x ↑ + PI j also defines an alternative belonging to X n↑ . Moreover, we augment this argument by allowing it to invoke the positive homogeneity of the model.

Definition 13 (PI dominance). b ↑ λ j ×PI j ⪯ PI a ↑ ⇔ a ↑ = b ↑ + λ j × PI j
We note that this dominance is a refinement of a N OWA ↘ PI j \∅ b We can then compute the contribution of the PI as

γ PI = PI T × λ with λ ∈ R + m .
Small reminder, a Pigou-Dalton transfer occurs between two variables i, j with i < j and we remove a quantity ϵ from criterion j to give it to criterion i. We obtain a contribution γ PDP = (e ke j ) × ϵ. As several Pigou-Dalton transfer can occur in the decomposition, the total contribution of the transfers can be written for each criterion i as γ PDP,i = τ with τ ∈ R n . To be able to write linear constraints over this type of transfers, we will divide this vector τ in two vectors τ + and τ -, with τ + i ∈ R -(resp. τ - i ∈ R + ) the quantity criterion i have to give (resp. receive).

Pareto-dominance between a and b can be simply written as a vector µ ∈ R + n , so the contribution of Paretodominance is γ P = µ.

We now have the contribution of our 3 explanation mechanisms and we can sum them up for every criteria i ∈ {1, . . . , n} and obtain :

c ↑ i -d ↑ i = τ + i + τ - i + µ i + m j=1 λ j × (a j↑ i -b j↑ i ) (1)
The set of equation we build from (1) and the domains form a linear program, but unfortunately we have to introduce some binary variables to constrain the Pigou-Dalton variables τ + and τ -left unconstrained. We will have to go back to the definition of Pigou-Dalton transfers to build the constraints.

First a Pigou-Dalton transfer is balanced, we only redistribute ϵ between criteria. This can be written as a linear constraint :

τ + 1 -τ - 1 = 0 (2)
Then, we know that the transfers take from a criterion j a positive quantity to give to a criterion i such that i < j.

We can then write ∀k ∈ {1, . . . , n} n i=k τ + i + τ - i <= 0 which can be synthesized with the matrix constraint :

U × (τ -+ τ + ) ≤ ⃗ 0 (3)
with U the upper triangular matrix of size n × n with ones in the upper triangle.

Finally we need to introduce some auxiliary binary variables t + and t -used to avoid useless Pigou-Dalton transfers. Their goal is to ensure that a criterion k is used only as a receiver or a giver in the transfers (otherwise we will perform useless trades using k as an unnecessary intermediate). We obtain the mixed integer linear equations using M a big constant we will discuss after :

M × t + + τ + ≥ ⃗ 0 (4) M × t --τ -≥ ⃗ 0 (5) t + + t -≤ ⃗ 1 (6)
Our big M has to be scaled as an upper bound of the maximum width that can be used in a Pigou-Dalton transfer (as receiver or giver). Its computation is fairly easy, in the normalised and general case. In the normalized case we can use M = 1 as the maximum value we can add or retrieve to a criteria is 1. In the general case, we can only redistribute values through criteria, so if we take M = ∥c∥ 1 + ∥d∥ 1 , we are sure to cover every case.

Example 4. We take a small illustrative example. We suppose that the DM has expressed her preferences over two candidates a 1 and b 1 , resulting into the statement PI = (-0.05 0.1 -0.05 0). The problem is then of ranking two candidates a ↑ = (0.5 0.5 0.7 0.9) and b ↑ = (0.3 0.7 0.8 0.8). As L(a) = (0.5 1 1.7 2.6) and L(b) = (0.3 1 1.8 2.6) there is no Lorenz dominance between them but the GRIP method finds that a N OWA ↘ PI b. For the statement a ↑b ↑ = (-0.05 0.1 0 -0.05) a decomposition can be :

-PI = 1 × (-0.05 0.1 -0.05 0)

-τ + = (0 0 0 -0.05) -τ -= (0 0 0.05 0) -µ = ⃗ 0
Theorem 1 (Characterization of the necessary preference with decomposition).

aN OWA ↘ PI b ⇔ ∃ µ, τ + , τ -, λ s.t. (a ↑ -b ↑ ) = PI T ×λ+µ+τ + +τ - Démonstration.
Proving that if we have such a decomposition for (a ↑b ↑ ) then we have a N OWA ↘ PI b is obvious. Proving the converse will require the use of Farkas' lemma. First, we suppose that the polytope obtained in W ↘ by the intersection of PI statements, i.e. the intersection of the hyperplanes (a j↑b j↑ ) × w = 0, is consistent, meaning that the robust FOWA W ↘ PI is non-empty. Then, we have aN OWA ↘ PI b, meaning that it is not possible to find a set of weights w ∈ W ↘ PI such that b ≻ w a, i.e. (a ↑b ↑ ) × w < 0. Therefore by using Farkas' lemma, we can write (a ↑ -b ↑ )× w as a linear combination of our constraints, i.e. PI statements, Pigou-Dalton transfers and Pareto dominance. □ To complete our linear program we have to define our objective. We want to provide an explanation, as easy and as short as possible. Our goal is then first to minimize the contribution of our explanation mechanisms in the decomposition. But our explanation mechanisms are not on the same scale of complexity for the user. Pareto dominance is natural and easy to understand. Pigou-Dalton transfers are a little harder to interpret but as it is the reason we use fairness-oriented OWA and are binary exchanges, it is still easy to understand, with a small cognitive cost. However, using a positive linear combination of PI statements is hard to understand, as it is performed with the anonymized variables and not the base variables, especially if the computed coefficients are complicated and the statements include multiple variables, so it should be limited as much as possible.

We represent this complex situation with multiple objectives :

-minimize the number of PI statements involved -reduce the part of Pigou-Dalton in the decomposition, i.e. maximize Pareto dominance -find the nicest coefficients values for the PI statements The idea of finding the nicest coefficients is that when we use the PI dominance λ j ×PI j ⪯ PI , we want the λ j displayed to be at least rational 3 , and preferably integer. To do so we will introduce in equation 1 an integer coefficient α, corresponding to the denominator of our λ j which becomes also an integer. We obtain :

α × (c ↑ i -d ↑ i ) = PI T × λ + µ + τ + + τ - (7)
with λ ∈ N m and α ∈ N * .

Subsequently, we used the (single-)objective function

F = ∥λ∥ 1 + α + 1
M ∥t -∥ 1 to minimize, but other approaches can be considered, such as minimising a norm L 0 or canceling balancing effects between λ and α.

To summarize our mixed integer program is represented in figure 1.

F.ob j : Min F subject to α × (c ↑ i -d ↑ i ) = PI T × λ + µ + τ + + τ - M × t + + τ + ≥ ⃗ 0 M × t --τ -≥ ⃗ 0 t + + t -≤ ⃗ 1 τ + 1 -τ - 1 = 0 U × (τ -+ τ + ) ≤ ⃗ 0 λ ∈ N m µ ∈ R n + , τ + ∈ R n -, τ -∈ R n + α ∈ N * , t + ∈ {0, 1} n , t -∈ {0, 1} n .
FIGURE 1 -A linear program allowing to find an additive decomposition of a comparative statement.

An illustrative example

In this section we will run an example, close to a real-case study, to use our algorithm and linear program to explain inferred preferences. The decision maker is the person in charge of the recruitment of students in a large french University. Her University has a large variety of formations but the policy is to form students toward general knowledge with specialisation in the last year. Therefore her preferences are oriented toward students with balanced overall good results instead of students specialised in some field only.

She is asked by the University her preferences over a set of 7 students, represented by their grades (on a scale from 0 to 20) in 4 important subjects : {"Mathematics", "Philosophy", "Biology", "English" }. This small subset of students corresponds to students from "classes préparatoires" and is fundamentally smaller that the set of students she will receive later in the year from students which just obtained their baccalaureate exam. Therefore she wants to automatize the process of building her preferences, even if it returns incomplete rankings, as long as she can have non technical explanations of the results, both for her personal use and for answering questions coming e.g. from rejected students or from a supervising regulatory institution. For all these reasons we presented her (without explicitly tell her the name) our robust FOWA operator.

To avoid any biases based on the names of candidates, we randomized them and assigned them a capital letter in {a, b, c, d, e, f, g}. The results of the candidates (reordered) to rank are : To start our model with preferences, we asked the decision maker to rank two pairs of candidates and she replied that b ⪰ PI c and d ⪰ PI e.

Student #1 #2 #3 #4 a ↑ 5
We then compute the robust FOWA operator W ↘ PI with a linear program inspired from the GRIP method [START_REF] Figueira | Building a set of additive value functions representing a reference preorder and intensities of preference : GRIP method[END_REF] and obtain the necessary preference order which is : b With algorithm 1, we obtain as explanation for g ⪰ L a :

N OWA ↘ PI c, b N OWA ↘ PI g, b N OWA ↘ PI d, g N OWA ↘
a ↑ = (5 13 14
b ↑ -e ↑ = (-3 6 -1 -4) = PI 1 + 2 × PI 2 + ν + + ν - with ν -= (0 2 0 0) and ν + = (0 0 -2 0) -c ↑ -g ↑ = (-2 4 -1 -1) = PI 1 + ν + + ν -
with ν -= (0 1 0 0) and ν + = (0 0 0 -1)

We were also able to find through a brute force algorithm (testing all permutation) a sequence of preferences using the decomposition to produce a transitive explanation sequence, but it is not a general result. We can note that if we tried to apply the decomposition in another order, it would build intermediate candidates which are not ordered.

Experimental results

In this section we will present some results obtained from experiments. We have generated randomly 1000 samples of 50 candidates (non Pareto-dominated) over 8 criteria with 5 PI statements. To compute these PI statements we draw from a Dirichlet distribution a set of ground-truth FOOWA weigth w ↘ , and drew randomly 5 pairs (a i , b i ) of non Lorenz-dominated candidates and added to the robust FOOWA the preference induced by w ↘ . For the rest of the experiment the ground-truth will be hidden. From these sample we studied two aspects of our method. In the first place, we computed for Lorenz-dominated pairs of candidates the results of our algorithm 1 against A* algorithm and we compared the obtained length to the true minimal length and the computation times. In the second place, we tried through several means to compute a transitive explanation from the decompositions obtained by our MILP formulation detailed in figure 1.

Algorithm 1 against A* algorithm

Our goal is to compare the explanation length and the computation time our polynomial heuristic algorithm 1 with a method guaranteeing to find the "true" minimum length. As introduced in Section 3 we do so by the means of a A* search. Indeed, the idea underlying the A* algorithm is to find the shortest path between the winning candidate to the loosing candidate using Pigou-Dalton transfers and Pareto-dominance. The heuristic we use to estimate the distance to the loosing candidate is the number of positions which need to receive from a Pigou-Dalton transfer, plus 1 if there are more variables in a position to give than to receive. This estimate is indeed a lower bound of the number of remaining trades.

We represent in table 1 the difference between the length found by the A* algorithm and our algorithm 1. Each row i of the table corresponds to a true length of i Pigou-Dalton transfers and Pareto-dominance. We can see that overall the results obtained by our algorithm 1 do not differ from the A* algorithm, except in some We have represented in table 2 the percentage of reduction in the computation time by using algorithm 1 instead of the A* algorithm. We can see that only very little data (in line 3) are corresponding to the A* algorithm performing better, and with high number of criteria we see a strict dominance of algorithm 1. Therefore, for the rest of the study combining the resolution of finding a concise explanation for Lorenz-dominance and PI dominance, we will be using algorithm 1 for its benefits in computational cost.

Feasibility of transitive explanation for decomposition computed by the MILP formulation

Our goal is to study the availability of an explanation from the decomposition found by our MILP formulation in figure 1 for a necessary preference statement. We recall that a valid explanation is a sequence of progressive transfers from the winner to the looser, using our 3 explanation mechanisms {⪯ P , ⪯ PDP , ⪯ PI }, while verifying that each intermediate candidate used in the explanation is valid, i.e. with values of criteria ordered and belonging to the domain.

To compute such a sequence from a set of values ( 1 α × λ, µ, ν + , ν -), we search for a permutation verifying our validity constraint. We allow to permute each individual PI statement with the Pareto dominance and the total Pigou-Dalton transfers. This algorithm does not try to divide any of this statements. We obtain some encouraging results on the length of explanation, displayed in table 3, unfortunately too many preferences fail to have a valid permutation : we found 192 436 cases where we cannot build the transitive explanation, meaning that 73% of our explanations cannot be interpreted into valid sequences. A first hypothesis to explain these results outside our valid domain could be that, because the PI itself is not linear and does not guarantee to stay inside the domain (where Pigou-Dalton transfers and Pareto dominance do), maybe some statements are required to be performed but cannot be taken separately. They should be performed in sequence but without looking into the intermediary result. Therefore we build a unique "whole PI" statement to recompute permutation with. New sequences are found but their number, 914, is not sufficient to conclude for the significance of the hypothesis.

PI involved #Explanations

Another cause for the unfeasibility of scheduling the decomposition into a valid transitive explanation could be the proximity of candidates to the boundaries of the domain X n , making the use of the PI statements hard without fragmentation. We therefore performed the experience again with candidates sampled over X n = [0.1; 0.9] n instead of [0; 1] n , leaving this space for the explanations. We obtain the results in table 4 We obtain better results, even adding 1 229 more with the "one PI statement" augmentation, but we still have a humongous quantity (161 797 so around 63%) of non valid sequences. Finally, it could be worthwhile to consider a finer-grained scheduling of PI statements, where a statement λ k ×PI k could be split into δ k λ k ×PI k and (1-δ k )×λ k × PI k . We could use these statements in different locations in the explanation to build a sequence which could seem like

c ↑ ⪰ PI c ↑ -δ × λ × PI ⪰ L d ↑ + ( ⃗ 1 -δ) × λ × PI ⪰ PI d ↑ .

Conclusion and future works

In this paper we looked into the problem of producing explanations for the robust fairness-oriented OWA. The explanations are designed to be the least technical possible to be shared with external users which are possibly not involved in the conception of the system and have very little knowledge about it. To understand our explanations, it is only required to know why the model is used, preferring candidates with a balanced profile and therefore agrees with the Pigou-Dalton principle of transfers on the ordered profile of the candidate.

We presented an algorithm which builds a transitive chain for Lorenz-dominance as an explication. The existence of the chain is known from a long time [START_REF] Moyes | Gini or Lorenz : Does it make a difference for inequality measurement[END_REF] as a result in welfare economy and also the link with the OWA operator [START_REF] Golden | Infinite order Lorenz dominance for fair multiagent optimization[END_REF]. This algorithm works in a polynomial time in the number n of criteria, with a length of maximum n transfers. It can be used to explain Lorenz dominance in general and not only in the fairness-oriented OWA setting, where it corresponds to the results obtained by the necessary preference relation N OWA ↘ ∅ .

We then presented a mixed integer linear program to compute an additive decomposition of a preference in N OWA ↘ PI , composed by a positive linear combination of the preference statements given by the DM, Pigou-Dalton transfers and Pareto-Dominance. This decomposition however is not a transitive explanation, and the existence of the latter for a given decomposition is still unknown yet, even though we can always build a decomposition (Theorem 1). We plan to adopt planning tools to further investigate the problem of computing transitive explanations, and the question whether guiding this search by the pre-computation of an additive decomposition is efficient or not.

j

  Definition 10 (Lorenz-dominance). We define the Lorenzdominance ⪰ L by :a ⪰ L b ⇐⇒ ∀i ∈ {1, . . . , n} L(a) i ≥ L(b) iExample 2. (Example 1 continued) The Lorenz vector of the three candidates {a, b, c} are L(a) = (0.5, 1.2, 2.2), L(b) = (0.7, 1.4, 2.1) and L(c) = (0.7, 1.4, 2.1). By comparing the Lorenz vectors we obtain the following Lorenz-dominance relation statements : c ⪰ L a and c ⪰ L b.

Algorithm 1 :

 1 Algorithm explaining Lorenzdominance with Pareto dominance and Pigou-Dalton transfers Input: a, b ∈ X n↑ s.t. a ⪰ L b Output: C x = a ; C = a 1 Compute J, the set of indices j s.t. x j < b j and s.t. we can perform a trade ϵ j = b jx j 2 If J == ∅ go to Steps 5 3 For each j ∈ J : (I) Compute K, the set of indices k < j s.t. x k > b k and s.t. we can perform a trade

  5 0.6 0.7 0.7 0.8) = d ↑ of length 4. With the A* search we obtain a different explanation : e ↑ = (0.4 0.4 0.6 0.8 1) ⪯ P (0.4 0.4 0.7 0.

  PI a, d N OWA ↘ PI e and d N OWA ↘ PI f , and all preferences deduced by transitivity. We can also compute the Lorenz dominance for every pair of candidates, obtaining preference statements b ⪰ L a, g ⪰ L a, c ⪰ L a, c ⪰ L f , d ⪰ L f . By comparing the two preference sets, we can see that adding the preferential information c preferences among candidates such as c N OWA ↘ PI g and c N OWA ↘ PI d and transitive ones such as b N OWA ↘ PI g, b N OWA ↘ PI d, b N OWA ↘ PI e and b N OWA ↘ PI f . To sum up, our robust FOWA produces 14 preference relations, including 2 PI from the user and 12 statements to explain, 5 with Lorenz-dominance explanations and 7 with our decomposition program. We will not detail all of these 12 statements, only one based on Lorenz-dominance such as g ⪰ L a and two from our linear program such as b N OWA ↘ PI e and c N OWA ↘ PI g. To present thing shortly we will refer as PI 1 = (-1 2 -1 0) and PI 2 = (-1 1 1 -1) the vectors corresponding respectively to the PI statements b ⪰ PI c and d ⪰ PI e.

16 )

 16 = g ↑ . With linear program (1) we find two decompositions for b N OWA ↘ PI e and c N OWA ↘ PI g : -

For

  b N OWA ↘ PI e we found : e ↑ = (8 16) = b ↑ For c N OWA ↘ PI g we found : g ↑ = (7

TABLE 3 -

 3 Distribution of explanation length by quantity of PI involved.

  .

	PI involved #Explanations Q1 Median Q3
	1	84 347	4	6	8
	2	8 315	7	8	9
	3	596	8	9	10
	4	22	10	11	11
	Not found	161 797	-	-	-

TABLE 4 -

 4 Distribution of explanation length by quantity of PI involved for candidates sampled over [0.1; 0.9] n .

This is always possible, because the constraints are expressed using integers.


Both types of methods can be considered as data driven

Machine learning methods

• Linear, statistical machine learning methods (e.g., 3DVA in CryoSPARC, Punjani and Fleet 2021)

• Assume that each conformation can be represented with a sum of a reference conformation and a linear combination of principal conformations, as those that can be obtained by PCA of the covariance matrix Harmonic approximation of the potential energy and Diagonalization of the Hessian matrix ( )

3 0 7 N i ij j i j x a q x = = + ∑ q Hessian: 2 nd derivative of the potential o r r j i p r r E =         ∂ ∂ ∂ = 2 H Eigenvalue problem L HA A t =           =  0 0 2 2 2 1 ω ω L Eigenvector = normal mode Eigenvalue = frequency 2 ( )  2 1 a a A = Size of the system: 3N x 3N N : Number of atoms or pseudoatoms ∑ ∑ →  - - ∂ ∂ ∂ ≅ = n n n j j ij i i r r j i p p q r r r r r r E r E o 2 2 0 0 2 2 1 ) ( ) ( 2 1 ) ( ω

Coordinate change

Amplitudes (no physical units) can be obtained by correlating models with EM data

DeepHEMNMA tests with synthetic data

Hamitouche & Jonic, Front Mol Biosci 2022

•

  Continuous conformational heterogeneity SPA with MDSPACE 98% of the particles 2% of the particles anuscript in preparation (PhD thesis of Rémi Vuillemot 2023, Collab. Rouiller team, The University of Melbourne) 17 MDSPACE analysis of p97 dataset of 274,640 particles • Initial model: Cα Gō model of PDB:5FTN (N domains up) • 2 iterations of MDSPACE • Iter 1: 5,000 particles, 5 NMs • Iter 2: 274,640 particles, 10 PCs • 50 ps NMMD simulations (time step : 1 fs) Conformational heterogeneity subtomogram analysis with MDTOMO Closed RBD One-open RBD Intermediate open RBD NTD lift Vuillemot et al. Sci Rep 2023, data provided by B. Turonova, Max Planck Inst. Biophys, Germany MDTOMO analysis of SARS-CoV2 spike dataset of 20,080 subtomograms • Initial model: Cα Gō model of PDB:6VXX (closed RBDs) • 1 iter of MDTOMO • 100 ps NMMD simulations • Force constant: 7000 kcal/mol Relationship between Point Density and Free-Energy Difference Δ𝐺𝐺/𝑘𝑘 𝐵𝐵 𝑇𝑇 = -ln(𝑛𝑛 𝑖𝑖 /𝑛𝑛 0 ) ∆G: Free-energy difference with respect to a reference state with population 𝑛𝑛 0 𝑛𝑛 0 : Number of particles in the most populated region 𝑛𝑛 𝑖𝑖 : Number of particles in region i 𝑘𝑘 𝐵𝐵 : Boltzmann constant 𝑇𝑇 : Temperature of the system Vuillemot et al. Sci Rep 2023 et al. Structure 2014 SPA, DNA Pol α -B complex Methods based on machine learning (statistical or deep learning) • Methods based on molecular conformational dynamics simulation (hybrid methods)

••…

  Non-linear, statistical machine learning methods (e.g., Manifold Embedding, Dashti et al. 2014) • Non-linear, deep learning methods (e.g., CryoDRGN, Zhong et al. 2021; 3DFlex, Punjani & Fleet 2023) Often use pre-estimated angles and shifts • Produce density-map representations of the conformational spaces • Deep learning methods produce models of density maps • Prediction can be correct or incorrect Hybrid methods: Use a prior structural knowledge (e.g., atomic model) Integrate dynamics simulation using this model into data analysis • Obtain a conformational model from each individual particle image or subtomogram • By flexible fitting of a given model into each image or subtomogram • Project the obtained models onto a low-Hybrid methods: Use a prior structural knowledge (e.g., atomic model) Integrate simulation of dynamics using this model into data analysis • Obtain a conformational model from each individual particle image or subtomogram • By flexible fitting of a given model into each image or subtomogram • Project the obtained models onto a low-Estimation of angles and shifts from scratch … Hybrid methods

PART 2 :

 2 GOING FURTHER INTO DETAILS OF HYBRID METHODS • Standard approaches to simulate conformational dynamics • Molecular Dynamics (MD) simulation • Normal Mode Analysis (NMA) • Earlier hybrid approaches • 3D-to-3D flexible fitting of an initial atomic model into a single EM map • Using MD simulation or Normal Modes • How to efficiently combine NMA and MD simulations ? • Normal Mode Molecular Dynamics (NMMD) approach • Use of NMMD in 3D-to-3D flexible fitting • Molecular Dynamics (MD) simulation • Normal Mode Analysis (NMA) Molecular Dynamics (MD) simulation 𝐹𝐹 = 𝑚𝑚𝑚𝑚 • Mimics the behavior of the atoms in the real world • Integrates Newton's equations of motion 𝐹𝐹 = -∇𝑈𝑈 𝑥𝑥 𝑚𝑚 = team, The University of Melbourne Limitations of MD simulation • High computational cost : • Small time step • Large number of degrees of freedom • Could be reduced with coarse-graining All-atom vs. coarse-grained representation its two coarse-grained models (spheres: 3D Gaussian functions called pseudoatoms) Jonic & Sorzano, IEEE J STSP 2016 Tirion's Elastic Network Model (ENM) Tirion, Phys Rev Lett 1996• Allows obtaining normal modes of atomic structures or EM maps • Before NMA, EM maps must be converted into "pseudoatoms" (3D Gaussians)• Initial conformation is assumed to be at the energy minimum • Atoms or "pseudoatoms" are connected with elastic springs (within a given radius) Radius of interaction (within which atoms are connected)

NMA••

  Linear combination of harmonic oscillator motions obtained by harmonic approximation of potential energy ⇒Fast ⇒Large amplitudes of normal modes may induce model distortions Earlier hybrid approaches 3D-to-3D flexible fitting of an initial atomic model into a single EM map 42 Fitting the EM map) Use of MD simulation for 3D-to-3D flexible fitting of an EM map with an atomic model Normal Mode Molecular Dynamics (NMMD) approach (Vuillemot et al. J Mol. Biol. 2022) • Incorporates displacements along normal modes (NMs) into MD simulation (into the computation of the potential energy function for MD simulation) • Simultaneously determines both NM and MD parameters • Speeds up MD simulations using NMs while preserving high quality of the fitted models Normal Mode Molecular Dynamics (NMMD) approach NM-based displacement Atomic displacement 𝑟𝑟 𝑑𝑑 = 𝑞𝑞 𝑑𝑑 � 𝐴𝐴 + 𝑥𝑥 𝑑𝑑 + 𝑟𝑟 0 𝐹𝐹 𝑥𝑥 = 𝑚𝑚 𝑥𝑥 ẍ𝑥 𝐹𝐹 𝑥𝑥 = -𝜕𝜕𝑈𝑈 𝜕𝜕𝑥𝑥 𝐹𝐹 𝑞𝑞 = -𝜕𝜕𝑈𝑈 𝜕𝜕𝑞𝑞 Incorporates NM-displacements in the computation of the potential energy function 𝑈𝑈 𝑟𝑟 during MD simulation 𝐹𝐹 𝑞𝑞 = 𝑚𝑚 𝑥𝑥 q𝑞 𝐹𝐹 𝑞𝑞 = 𝐴𝐴𝐹𝐹 𝑥𝑥 conformational space: Image mapping in a low-dimensional space of normal-mode displacement amplitudes Each point: 3 angles, 2 shifts, and M normal-mode amplitudes (conformation) For each single particle image: Iterative 3D-to-2D elastic and rigid-body alignment to find conformation, orientation, and translation quasi-simultaneously Image Reference DNA polymerase Pol α -B ., Structure 2014 DeepHEMNMA: Recent approach for HEMNMA speed-up Based on Deep Learning of rigid-body and elastic parameters 56 Ilyes Hamitouche PhD, March 2023 (now Pdoc Curie, Paris) Resnet 34 (34-layer residual net) followed by a 4-layer MLP Regression learning: -small number of conformational parameters (normal-mode amplitudes) -rotations and translations Reconstruction of 7 maps showing variable degree of inter-subunit rotation and presence/absence of the second tRNA Hamitouche & Jonic, Front Mol Biosci 2022

DeepHEMNMA analysis of EMPIAR-10016 data Yeast 80S ribosome-tRNA complexes Errors Normal-mode amplitudes Angles [°]

  Mean SD Mean SD Mean SD Mean SD Mean SD Mean SD

											Shifts X	Shifts Y
		Mean	Mode 7	Mode 8	Mode 9			[Å]		[Å]
		over
		modes
		7-9
	Predicted vs. Ground-truth	7.5	5.4	6.5 8.2 9.2	8.9 10.5 2.5	3.3	0.2	0.1 0.2	0.1
	Predicted vs. HEMNMA	6.9	5.4	6.7 7.3 9.0	7.9	9.6	1.9	3.4	0.2	0.1 0.2	0.1
	HEMNMA vs. Ground-truth	6.6	5.7	8.4 6.2 7.2	7.8	7.2	1.0	0.9	0.2	0.2 0.2	0.2
			Normal-mode
		RMSDs	[Å] amplitudes	of images Small subset Angles [Å] Shifts [Å]
			Mean	SD Mean SD Mean SD
	Predicted vs. Ground-truth	0.4	0.2	0.9	Large subset of images 1.0	0.3	1,018 1,148 0.2		1,461	1,816	1,771	975	949

3D-to-2D flexible fitting of large sets of cryo-EM images

synthetic datasets of 3,000 subtomograms of ABC transporter PDB-6RAK (Hoffman et al. Nature 2019) SNR 0.05 SNR 0.03 SNR 0.01 Vuillemot, et al. Sci Rep 2023

74 Vuillemot, et al. Sci Rep 2023 MDTOMO analysis of EMPIAR-10453 data

Conformational landscapes and

Use of Normal Modes for 3D-to-3D flexible fitting of an EM map with an atomic model

Fast, but … Challenges and Limitations:

• How to select normal modes?

• Usual use of low-frequency collective normal modes (fitting of global, large-scale motions)

• Validity of NMA for larger motion amplitudes around the initial conformation Target conformation (given by the EM map)

Initial conformation

Brief conclusions on earlier hybrid approaches • Use of 46,095 images (mixture of 2 classes, with 1 tRNA and 2 tRNAs)

• Downscaling from 360 × 360 pixels (pixel: 1.05 Å) to 128 × 128 pixels (pixel: 2.95 Å)

• Splitting images into 3 subsets: training (32,000), validation (2,000), and test (12,095)

• PCA space split quasi-uniformly to get at least 900 images per group • NMMD is faster than MD alone, thanks to normal modes

• MDSPACE produces high-quality models (better than those obtained with normal modes only)

• Selection of normal modes is less critical in MDSPACE than in HEMNMA Iterative MDSPACE procedure for refining conformational space 64

The initial rigid-body alignment parameters are refined during the fitting in each MDSPACE iteration and updated before each new iteration Vuillemot et al., J Mol Biol 2023 MDSPACE validation with synthetic data of an ABC transporter Summary: 3D-to-2D flexible fitting of each particle image with a given model 77 HEMNMA (Jin et al., Structure 2014) • First approach for analyzing continuous conformational heterogeneity in large sets of particle images, which integrates simulated motion directions of a given model into image analysis • Simulations performed using NMA DeepHEMNMA (Hamitouche & Jonic, Front Mol Biosci 2022) • First approach integrating motion simulation into deep learning (training data obtained with HEMNMA)

• Accelerates HEMNMA MDSPACE (Vuillemot et al., J Mol Biol 2023) • First approach integrating MD simulation into SPA for continuous conformational heterogeneity analysis, where each image is analyzed independently of others • Uses NMMD (MD simulation empowered with normal modes to speed up the analysis while preserving high quality resulting models) Summary: 3D-to-3D flexible fitting of each subtomogram with a given model 78 HEMNMA-3D (Harastani et al., Front Mol Biosc 2021) • First approach for analyzing continuous conformational heterogeneity in a set of cryo-ET subtomograms, which integrates simulated motion directions of a given model into subtomogram analysis

• Extension of HEMNMA (simulations performed using NMA) MDTOMO (Vuillemot et al., Sci Rep 2023) • First approach integrating MD simulation into subtomogram analysis for continuous conformational heterogeneity studies

• Uses NMMD (MD simulation empowered with normal modes to speed up the analysis while preserving high quality resulting models)

Thank You

Thank You