Othmane Marfoq

Laetitia Kameni

Richard Vidal

Giovanni Neglia

Personalized Federated Learning through Local Memorization

Federated learning allows clients to collaboratively learn statistical models while keeping their data local. Federated learning was originally used to train a unique global model to be served to all clients, but this approach might be sub-optimal when clients' local data distributions are heterogeneous. In order to tackle this limitation, recent personalized federated learning methods train a separate model for each client while still leveraging the knowledge available at other clients. In this work, we exploit the ability of deep neural networks to extract high quality vectorial representations (embeddings) from non-tabular data, e.g., images and text, to propose a personalization mechanism based on local memorization. Personalization is obtained by interpolating a collectively trained global model with a local k-nearest neighbors (kNN) model based on the shared representation provided by the global model. We provide generalization bounds for the proposed approach in the case of binary classification, and we show on a suite of federated datasets that this approach achieves significantly higher accuracy and fairness than state-of-the-art methods.

Introduction

Heterogeneity is a core and fundamental challenge in Federated Learning (FL) [START_REF] Li | Federated learning: Challenges, methods, and future directions[END_REF][START_REF] Kairouz | Advances and open problems in federated learning[END_REF]. Indeed, clients highly differ both in size and distribution of their local datasets (statistical heterogeneity), and in their storage and computational capabilities (system heterogeneity). Those two aspects challenge the assumption that clients should train a common global model, as pursued in many federated learning papers [START_REF] Mcmahan | Communicationefficient learning of deep networks from decentralized data[END_REF][START_REF] Konečny | Federated learning: Strategies for improving communication efficiency[END_REF][START_REF] Kumar Sahu | On the convergence of federated optimization in heterogeneous networks[END_REF][START_REF] Sai | Scaffold: Stochastic controlled averaging for federated learning[END_REF][START_REF] Mohri | Agnostic federated learning[END_REF]. In fact, all clients should be content Proceedings of the 39 th International Conference on Machine Learning, Baltimore, Maryland, USA, PMLR 162, 2022. Copyright 2022 by the author(s).

with a model's architecture constrained by the minimum common capabilities. Even when clients have similar hardware (e.g., they are all smartphones), in presence of statistical heterogeneity, a global model may be arbitrarily bad for some clients raising important fairness concerns [START_REF] Li | Ditto: Fair and robust federated learning through personalization[END_REF].

Motivated by the recent success of memorization techniques based on nearest neighbours for natural language processing, [START_REF] Khandelwal | Generalization through memorization: Nearest neighbor language models[END_REF]2020), computer vision (Papernot and[START_REF] Papernot | Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning[END_REF][START_REF] Orhan | A simple cache model for image recognition[END_REF], and few-shot classification [START_REF] Snell | Prototypical networks for few-shot learning[END_REF][START_REF] Wang | Simpleshot: Revisiting nearestneighbor classification for few-shot learning[END_REF], we propose kNN-Per, a personalized FL algorithm based on local memorization. kNN-Per combines a global model trained collectively (e.g., via FedAvg (McMahan et al., 2017)) with a kNN model on a client's local datastore. The global model also provides the shared representation used by the local kNN. Local memorization at each FL client can capture the client's local distribution shift with respect to the global distribution. Indeed, our experiments show that memorization is more beneficial when the distribution shift is larger. The generalization bound in Sec. 3 contributes to justify our empirical findings as well as those in [START_REF] Khandelwal | Generalization through memorization: Nearest neighbor language models[END_REF]2020;[START_REF] Orhan | A simple cache model for image recognition[END_REF].

kNN-Per offers a simple and effective way to address statistical heterogeneity even in a dynamic environment where client's data distributions change after training. It is indeed sufficient to update the local datastore with new data without the need to retrain the global model. Moreover, each client can independently tune the local kNN to its storage and computing capabilities, partially relieving the most powerful clients from the need to align their model to the weakest ones. Finally, kNN-Per has a limited leakage of private information, as personalization only occurs once communication exchanges have ended, and, if needed, it can be easily combined with differential privacy techniques.

Our contributions are threefold: 1) we propose kNN-Per, a simple personalization mechanism based on local memorization; 2) we provide generalization bounds for the proposed approach in the case of binary classification; 3) through extensive experiments on FL benchmarks, we show that kNN-Per achieves significantly higher accuracy and fairness than state-of-the-art methods.

The paper is organized as follows. After an overview of related work in Sec. 2, we present kNN-Per in Sec. 3 and provide generalization bounds in Sec. 4. Experimental setup and results are described in Sec. 5 and Sec. 6, respectively.

Related Work

We discuss personalized FL approaches to address statistical heterogeneity and system heterogeneity as well as nearest neighbours augmented neural networks.

Statistical Heterogeneity

This body of work considers that all clients have the same model architecture but potentially different parameters.

A simple approach for FL personalization is learning first a global model and then fine-tuning its parameters at each client through stochastic gradient descent for a few epochs [START_REF] Jiang | Improving federated learning personalization via model agnostic meta learning[END_REF][START_REF] Yu | Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs[END_REF]; we refer later to this approach as FedAvg+. FedAvg+ was later studied by [START_REF] Chen | On bridging generic and personalized federated learning for image classification[END_REF] and [START_REF] Cheng | Finetuning is fine in federated learning[END_REF]. The global model can then be considered as a meta-model to be used as initialization for a few-shot adaptation at each client. Later work [START_REF] Khodak | Adaptive gradient-based meta-learning methods[END_REF]Fallah et al., 2020;[START_REF] Alp | Debiasing model updates for improving personalized federated training[END_REF] has formally established the connection with Model Agnostic Meta Learning (MAML) [START_REF] Jiang | Improving federated learning personalization via model agnostic meta learning[END_REF] and proposed different algorithms to train a more suitable meta-model for local personalization.

ClusteredFL [START_REF] Sattler | Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints[END_REF]Ghosh et al., 2020;[START_REF] Mansour | Three approaches for personalization with applications to federated learning[END_REF] assumes that clients can be partitioned into several clusters, with clients in the same cluster sharing the same model, while models can be arbitrarily different across clusters. Clients jointly learn during training the cluster to which they belong as well as the cluster model. FedEM [START_REF] Marfoq | Federated multi-task learning under a mixture of distributions[END_REF] can be considered as a soft clustering algorithm as clients learn personalized models as mixtures of a limited number of component models.

Multi-Task Learning (MTL) allows for more nuanced relations among clients' models by defining federated MTL as a penalized optimization problem, where the penalization term captures clients' dissimilarity. Seminal work [START_REF] Smith | Federated multi-task learning[END_REF][START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF][START_REF] Zantedeschi | Fully decentralized joint learning of personalized models and collaboration graphs[END_REF] proposed algorithms able to deal with quite generic penalization terms, at the cost of learning only linear models or linear combinations of pre-trained models. Other MTLbased algorithms [START_REF] Hanzely | Federated learning of a mixture of global and local models[END_REF][START_REF] Hanzely | Federated learning of a mixture of global and local models[END_REF]T. Dinh et al., 2020;[START_REF] Canh T Dinh | Fedu: A unified framework for federated multi-task learning with laplacian regularization[END_REF][START_REF] Li | Ditto: Fair and robust federated learning through personalization[END_REF][START_REF] Huang | Personalized cross-silo federated learning on non-iid data[END_REF][START_REF] Li | Ditto: Fair and robust federated learning through personalization[END_REF] are able to train more general models but consider simpler penalization terms (e.g., the distance to the average model).

An alternative approach is to interpolate a global model and one local model per client [START_REF] Deng | Adaptive personalized federated learning[END_REF][START_REF] Corinzia | Variational federated multi-task learning[END_REF][START_REF] Mansour | Three approaches for personalization with applications to federated learning[END_REF]. Zhang et al. (2021) extended this idea by letting each client interpolate the local models of other clients with opportune weights learned during training. Our algorithm, kNN-Per, also interpolates a global and a local model, but the global model plays a double role as it is also used to provide a useful representation for the local kNN.

Closer to our approach, FedRep [START_REF] Collins | Exploiting shared representations for personalized federated learning[END_REF]), FedPer (Arivazhagan et al., 2019), and pFedGP (Achituve et al., 2021) jointly learn a global latent representation and local models-linear models for FedRep and FedPer, Gaussian processes for pFedGP-that operate on top of this representation. In these algorithms, the progressive refinement of local models affects the shared representation. On the contrary, in kNN-Per only the global model (and then the shared representation) is the object of federated training, and the shared representation is not influenced by local models, which are learned separately by each client in a second moment. Our experiments suggest that kNN-Per's approach is more efficient. A possible explanation is that jointly learning the shared representation and the local models lead to potentially conflicting and interfering goals. A similar argument was provided by [START_REF] Li | Ditto: Fair and robust federated learning through personalization[END_REF] to justify why Ditto replaces, as penalization term, the distance from the average of the local models-as proposed in [START_REF] Hanzely | Federated learning of a mixture of global and local models[END_REF][START_REF] Hanzely | Federated learning of a mixture of global and local models[END_REF]T. Dinh et al., 2020)-with the distance from an independently learned global model. [START_REF] Liang | Think locally, act globally: Federated learning with local and global representations[END_REF] proposed a someway opposite approach to FedRep, FedPer, and pFedGP by using local representations as input to a global model, but the representations and the global model are still jointly learned. An additional advantage of kNN-Per's clear separation between global and local model training is that, because each client does not share any information about its local model with the server, the risk of leaking private information is reduced. In particular, kNN-Per enjoys the same privacy guarantees as FedAvg, and can be easily combined with differential privacy techniques [START_REF] Wei | Federated learning with differential privacy: Algorithms and performance analysis[END_REF].

To the best of our knowledge, pFedGP and kNN-Per are the first attempts to learn semi-parametric models [START_REF] Bickel | Efficient and Adaptive Estimation for Semiparametric Models[END_REF] in a federated setting. pFedGP relies on Gaussian processes and then has higher computational cost than kNN-Per both at training and inference.

System Heterogeneity

Some FL application scenarios envision clients with highly heterogeneous hardware, like smartphones, IoT devices, edge computing servers, and the cloud. Ideally, each client could learn a potentially different model architecture, suited to its capabilities. Such system heterogeneity has been studied much less than statistical heterogeneity. Some work (Lin et al., 2020;[START_REF] Li | Fedmd: Heterogenous federated learning via model distillation[END_REF][START_REF] Zhu | Data-free knowledge distillation for heterogeneous federated learning[END_REF][START_REF] Zhang | Fedzkt: Zero-shot knowledge transfer towards heterogeneous on-device models in federated learning[END_REF] proposed to address system heterogeneity by distilling the knowledge from a global teacher to clients' student models with different architectures. While early methods [START_REF] Li | Fedmd: Heterogenous federated learning via model distillation[END_REF]Lin et al., 2020) required the access to an extra (unlabeled) public dataset, more recent ones [START_REF] Zhu | Data-free knowledge distillation for heterogeneous federated learning[END_REF][START_REF] Zhang | Fedzkt: Zero-shot knowledge transfer towards heterogeneous on-device models in federated learning[END_REF]) eliminated this requirement. Some papers [START_REF] Diao | Heterofl: Computation and communication efficient federated learning for heterogeneous clients[END_REF][START_REF] Horváth | FjORD: Fair and accurate federated learning under heterogeneous targets with ordered dropout[END_REF][START_REF] Bouchra | Simple, efficient and convenient decentralized multi-task learning for neural networks[END_REF] propose that each client only trains a sub-model of a global model. The sub-model size is determined by the client's computational capabilities. The approach appears particularly advantageous for convolutional neural networks with clients selecting only a limited subset of channels. [START_REF] Tan | FedProto: Federated Prototype Learning across Heterogeneous Clients[END_REF] followed another approach where devices and server communicate prototypes, i.e., average representations for all samples in a given class, instead of communicating model's gradients or parameters, allowing each client to have a different model architecture and input space.

While in this paper we assume that kNN-Per relies on a shared global model, it is possible to replace it with heterogeneous models adapted to the clients' capabilities and jointly trained following one of the methods listed above. Then, kNN-Per's interpolation with a kNN model extends these methods to address not only system heterogeneity, but also statistical heterogeneity.

To the best of our knowledge, the only existing method that takes into account both system and statistical heterogeneity is pFedHN [START_REF] Shamsian | Personalized federated learning using hypernetworks[END_REF]. pFedHN feeds local clients representations to a global (across clients) hypernetwork, which can output personalized heterogeneous models. Unfortunately, the hypernetwork has a large memory footprint already for small clients' models (e.g., the hypernetwork in the experiments in [START_REF] Shamsian | Personalized federated learning using hypernetworks[END_REF] has 100 more parameters than the output model): it is not clear if pFedHN can scale to complex models.

We observe that kNN-Per's kNN model can itself be adapted to client's capabilities by tuning the size of the datastore and/or selecting an appropriate approximate kNN algorithm, like FAISS [START_REF] Johnson | Billionscale similarity search with gpus[END_REF], HNSW (Malkov and Yashunin, 2020), or ProtoNN [START_REF] Gupta | ProtoNN: Compressed and accurate kNN for resource-scarce devices[END_REF] for IoT resource-scarce devices, e.g., based on Arduino.

Nearest Neighbours Augmented Neural Networks

Recent work proposed to augment neural networks with nearest neighbours classifiers for applications to language modelling [START_REF] Khandelwal | Generalization through memorization: Nearest neighbor language models[END_REF], neural machine translation [START_REF] Khandelwal | Nearest neighbor machine translation[END_REF], computer vision [START_REF] Papernot | Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning[END_REF][START_REF] Orhan | A simple cache model for image recognition[END_REF], and few-shot learning [START_REF] Snell | Prototypical networks for few-shot learning[END_REF][START_REF] Wang | Simpleshot: Revisiting nearestneighbor classification for few-shot learning[END_REF].

In [START_REF] Khandelwal | Generalization through memorization: Nearest neighbor language models[END_REF]2020) kNN improves model per-formance by memorizing explicitly (rather than implicitly in model parameters) rare patterns. [START_REF] Papernot | Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning[END_REF] and [START_REF] Orhan | A simple cache model for image recognition[END_REF] showed that memorization can also increase the robustness of models against adversarial attacks. Differently from these lines of work, our paper shows that local memorization at each FL client can capture the client's local distribution shift with respect to the global distribution. In this sense, our use of kNN is more similar to what is proposed for few shot learning in [START_REF] Snell | Prototypical networks for few-shot learning[END_REF][START_REF] Wang | Simpleshot: Revisiting nearestneighbor classification for few-shot learning[END_REF], where an embedding function is learned for future application to new small datasets. Beside the different learning problem, the algorithms proposed in [START_REF] Snell | Prototypical networks for few-shot learning[END_REF][START_REF] Wang | Simpleshot: Revisiting nearestneighbor classification for few-shot learning[END_REF] do not rely on models' interpolation and do not enjoy generalization guarantees as kNN-Per does. Moreover, their natural extension to the FL setting would lead to jointly learn the shared representation and the local kNN models, a potentially less efficient approach than ours as we discussed above when presenting FedRep, and pFedGP.

kNN-Per Algorithm

In this work we consider M classification or regression tasks also called clients.

Each client m ∈ [M ] has a local dataset S m = s (i) m = x (i) m , y (i) m , 1 ≤ i ≤ n m with n m sam- ples drawn i.i.d. from a distribution D m over the domain X × Y. Local data distributions {D m } m∈[M ]
are in general different, thus it is natural to fit a separate model (hypothesis) h m ∈ H to each data distribution D m . We consider that each hypothesis h ∈ H is a discriminative model mapping each input x ∈ X to a probability distribution over the set Y, i.e., h : X → ∆ |Y| , where ∆ C denotes the unitary simplex of dimension C. A hypothesis then can be interpreted as (an estimation of) a conditional probability distribution D(y|x).

Personalized FL aims to solve (in parallel) the following optimization problems

∀m ∈ [M ], h * m ∈ arg min h∈H L Dm (h), (1)
where

[M ] denotes the set of positive integers up to M , l : ∆ |Y| × Y → R + is the loss function, 1 and L Dm (h m ) = E (x,y)∼Dm [l(h m (x), y)] is the true risk of a model h m under data distribution D m .
We suppose that all tasks have access to a global discriminative model h S minimizing the empirical risk on the aggre-

gated dataset S ≜ M m=1 S m , i.e., h S ∈ arg min h∈H L S (h) , (2)
where

L S (h) ≜ M m=1 nm n • 1 nm nm i=1 l h x (i) m , y (i)
m , 1 In the case of (multi-output) regression, we have hm :

X → R d for some d ≥ 1 and l : R d × R d → R + .
and n = M m=1 n m . Typically h S is a feed-forward neural network, jointly trained by the clients using a standard FL algorithm like FedAvg.

We also suppose that the global model can be used to compute a fixed-length representation for any input x ∈ X , and we use ϕ h S : X → R p to denote the function that maps the input x ∈ X to its representation. The intermediate representation can be, for example, the output of the last convolutional layer in the case of CNNs, or the last hidden state in the case of recurrent networks or the output of an arbitrary self-attention layer in the case of transformers. Note that an alternative possible approach would be to separately learn an independent shared representation, e.g., using metric learning techniques [START_REF] Bellet | Metric Learning, volume 9 of Synthesis Lectures on Artificial Intelligence and Machine Learning[END_REF].

Our method (see Algorithm 1) involves augmenting the global model with a local nearest neighbors' retrieval mechanism at each client. The proposed method does not need any additional training; it only requires a single forward pass over the local dataset S m , m ∈ [M ]: client m computes the intermediate representation ϕ h S (x) for each sample (x, y) ∈ S m . The corresponding representation-label pairs are stored in a local key-value datastore (K m , V m ) that is queried during inference. Formally,

(K m , V m ) = ϕ h S x (i) m , y (i) m , ∀ x (i) m , y (i) m ∈ S m . (3)
At inference time, given input data x ∈ X , client m ∈ [M ] computes h S (x) and the intermediate representation

ϕ h S (x). Then, it queries its local datastore (K m , V m ) with ϕ h S (x) to retrieve its k-nearest neighbors N (k) m (x) accord- ing to a distance d (•, •): N (k) m (x) = ϕ h S x π (i) m (x) , y π (i) m (x) 1≤i≤k , (4)
where π

(1)

m (x) , . . . , π (nm) m (x) is a permutation of [n m ] cor- responding to the distance of the samples in S m from x, i.e., for i ∈ [n m -1], d ϕ h S x ,ϕ h S x π (i) m (x) ≤ d ϕ h S x , ϕ h S x π (i+1) m (x)
.

(5)

Then, the client computes a local hypothesis h

(k)
Sm which estimates the conditional probability D m (y|x) using a kNN method, e.g., with a Gaussian kernel:

h (k) Sm (x) y ∝ k i=1 1 y=y π (i) m (x) × exp -d ϕ h S (x) , ϕ h S x π (i) m (x)
. ( 6)

Algorithm 1 kNN-Per (Typical usage)

Learn global model using available clients with FedAvg.

for each client m ∈ [M ] (in parallel) do Build datastore using S m . At inference on x ∈ X , return h m,λm (x) given by ( 7) end for

The final decision rule (hypothesis

) at client m ∈ [M ] (h m,λm ) is obtained interpolating the nearest neighbour dis- tribution h (k)
Sm with the distribution obtained from the global model h S using a hyper-parameter λ m ∈ (0, 1) to produce the final prediction, i.e.,

h m,λm (x) ≜ λ m • h (k) Sm (x) + (1 -λ m ) • h S (x) . (7)
As h m,λm may not belong to H, we are considering an improper learning setting. The parameter λ m is tuned at client m through a local validation dataset or crossvalidation as in [START_REF] Corinzia | Variational federated multi-task learning[END_REF][START_REF] Mansour | Three approaches for personalization with applications to federated learning[END_REF]Zhang et al., 2021;[START_REF] Li | Ditto: Fair and robust federated learning through personalization[END_REF]

Generalization Bounds

In this section we provide a generalization bound associated with the proposed approach in the case of binary classification, namely Y = {0, 1}, when only one neighbour is used for kNN estimation, i.e., k = 1, and d (•, •) is the Euclidean distance. For client m ∈ [M ], we denote by η m : X → R the true conditional probability of label 1, that is

η m (x) = D m (y = 1|x) . (8)
Our result holds under the following assumptions:

Assumption 1 (Bounded representation). ϕ h S : X → [0, 1] p . Assumption 2 (Bounded loss). l : ∆ |Y| × Y → [0, 1].
Moreover, for y, y ′ ∈ {0, 1}, l(e y , y ′ ) = 1 y̸ =y ′ , where e y ∈ ∆ |Y| is the vector having all entries equal to 0 except the entry on the y-th coordinate.

Remark 1. Loss boundedness is a common assumption, e.g., [START_REF] Mansour | Three approaches for personalization with applications to federated learning[END_REF], (Shalev-Shwartz and Ben-David, 2014, Ch. 4). The second requirement is that the maximum loss is achieved when the model is fully confident about a prediction, but this is wrong. A simple transformation of common loss functions-e.g., exponentiating the logistic function-make them satisfy Assumption 2.

Assumption 3 (Loss convexity). The loss function is convex on the first variable

∀y 1 , y 2 ∈ ∆ |Y| , ∀y ∈ Y, ∀λ m ∈ [0, 1], l(λ m • y 1 + (1 -λ m ) • y 2 , y) ≤ λ m • l(y 1 , y) + (1 -λ m ) • l(y 2 , y). ( 9
)
Remark 2. Assumption 3 holds for most loss functions used in supervised machine learning, including the mean squared error loss, the cross-entropy loss, and the hinge loss.

Assumption 4. There exist constants γ 1 , γ 2 > 0, such that for any dataset S drawn from X × Y and any data points x, x ′ ∈ X , we have

η m (x) -η m (x ′ ) ≤ d (ϕ h S (x) , ϕ h S (x ′ )) × (γ 1 + γ 2 (L Dm (h S ) -L Dm (h * m ))) , ( 10
)
where h * m ∈ arg min h∈H L Dm (h).
This assumption means that if two samples x and x ′ have close representations ϕ h S (x) and ϕ h S (x ′ ), then their labels are likely to be the same (|η m (x) -η m (x ′ )| is small). This is all the more so, the better h S predictions are for distribution

D m , m ∈ [M ] (the smaller L Dm (h S ) -L Dm (h * m ) is).
Experimental results support Assumption 4 (see Figure 3). 2)). The distance between two distributions D and D ′ associated to a hypothesis class H can be quantified by the label discrepancy [START_REF] Mansour | Three approaches for personalization with applications to federated learning[END_REF]:

disc H (D, D ′ ) = max h∈H |L D (h) -L D ′ (h)| . ( 11
)
Theorem 4.1. Suppose that Assumptions 1-4 hold, and consider m ∈ [M ] and λ m ∈ (0, 1), then there exist constants c 1 , c 2 , c 3 , c 4 , and c 5 ∈ R, such that

E S∼⊗ M m=1 D nm m [L Dm (h m,λm )] ≤ (1 + λ m ) • L Dm (h * m ) + c 1 (1 -λ m ) • disc H D, D m + c 2 λ m • √ p p+1 √ n m • disc H D, D m + 1 + c 3 (1 -λ m ) • d H n • c 4 + log n d H + c 5 λ m • d H n • c 4 + log n d H • √ p p+1 √ n m , (12)
where d H is the the VC dimension of the hypothesis class

H, n = M m=1 n m , D = M m=1
nm n • D m , p is the dimension of representations, and disc H is the label discrepancy associated to the hypothesis class H.

The proof of Theorem 4.1 is in Appendix A. Let us consider, for simplicity, the non-agnostic case, i.e, L Dm (h * m ) = 0. We observe that, when clients only use the global model (λ m = 0), our generalization bound is analogous to the probabilistic bound in (Mansour et al., 2020, Eq. ( 2)). In particular, if data is i.i.d. distributed across the clients (disc H D, D m = 0), the difference between the expected losses of the learned model and the optimal one decreases with rate Õ The bound (12) leads to predict that client m should give a larger weight (λ m > 1/2) to its kNN model, when n m exceeds a given threshold, even when local distributions are identical. The bound contributes then to explain why adding a memorization mechanism on top of a pretrained model can improve performance, as observed in [START_REF] Khandelwal | Generalization through memorization: Nearest neighbor language models[END_REF] and [START_REF] Khandelwal | Nearest neighbor machine translation[END_REF]. While it is difficult to quantify the threshold analytically (also because the constants involved depend on γ 1 and γ 2 in Assumption 4), our experiments in Sec. 6 show that even clients with a few tens of samples weigh more the kNN model than the global one.

Experimental Setup

We evaluate kNN-Per on four federated datasets spanning a wide range of machine learning tasks: language modeling (Shakespeare [START_REF] Caldas | Leaf: A benchmark for federated settings[END_REF][START_REF] Mcmahan | Communicationefficient learning of deep networks from decentralized data[END_REF]), image classification (CIFAR-10 and CIFAR-100 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF]), handwritten character recognition (FEMNIST [START_REF] Caldas | Leaf: A benchmark for federated settings[END_REF]). Unless otherwise said, kNN-Per's global model h S is trained by all clients through FedAvg. Code is available at https: //github.com/omarfoq/knn-per.

Datasets. For Shakespeare and FEMNIST datasets there is a natural way to partition data through clients (by character and by writer, respectively). We relied on common approaches in the literature to sample heterogenous local datasets from CIFAR-10 and CIFAR-100. We created a federated version of CIFAR-10 by randomly partitioning the dataset among clients using a symmetric Dirichlet distribution, as done in [START_REF] Wang | Federated learning with matched averaging[END_REF]. In particular, for each label y we sampled a vector p y from a Dirichlet distribution of order M = 200 and parameter α = 0.3 (unless otherwise et al., 2021). 4 For each method, and each dataset, we tuned the learning rate via grid search on the values 10 -0.5 , 10 -1 , 10 -1.5 , 10 -2 , 10 -2.5 . FedPer's learning rate for network heads' training was separately tuned on the same grid. Ditto's penalization parameter λ m was selected among the values 10 1 , 10 0 , 10 -1 , 10 -2 on a per-client basis. For ClusteredFL, we used the same values of tolerance specified in its official implementation [START_REF] Sattler | Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints[END_REF]. We found tuning tol1 and tol2 particularly hard: no empirical rule is provided in [START_REF] Sattler | Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints[END_REF], and the few random settings we tried did not show any improvement in comparison to the default ones. For APFL, the mixing parameter α was tuned via grid search on the grid {0.1, 0.3, 0.5, 0.7, 0.9}. For pFedGP, we used the same hyperparameters as in [START_REF] Achituve | Personalized federated learning with gaussian processes[END_REF]. The parameter λ m of kNN-Per was tuned for each client via grid search on the grid {0.0, 0.1, 0.3, 0.5, 0.7, 0.9, 1.0}, and the number of neighbours was set to k = 10. Once the optimal hyperparameters' values were selected, models were retrained on the concatenation of training and validation sets.

Training details. In all experiments with CIFAR-10 and CIFAR-100, training spanned 200 rounds with full clients' participation at each round for all methods. The learning rate was reduced by a factor 10 at round 100 and then again at round 150. For Shakespeare, 10% of clients were sampled uniformly at random without replacement at each round, and we trained for 300 rounds with a constant learning rate.

For FEMNIST, 5% of the clients participated at each round for a total 1000 rounds, with the learning rate dropping by a factor 10 at round 500 and 750. In all our experiments we employed the following aggregation scheme

w t+1 = m / ∈St n m n w t + m∈St n m n w m t , (13)
where w t , w m t , and S t denote, respectively, the global model, the updated model at client m, and the set of clients participating to training at round t.

In all our experiments, local hypotheses follow Eq. ( 6) with d(•) being the Euclidean distance. kNN retrieval relied on FAISS library [START_REF] Johnson | Billionscale similarity search with gpus[END_REF]. 1). This occurs because each client only receives samples for a few classes, and then its local task is much easier than the global one. Effect of local dataset's size. Beside its relevance for some practical scenarios, the distinction between old and new clients also helps us to evaluate how different factors contribute to the final performance of kNN-Per. For example, to understand how the size of the local dataset affects performance, we reduced proportionally the size of new clients' local datasets, while maintaining unchanged the global model, which was trained on old clients. Figure 1 shows that new clients still reap most of kNN-Per's benefits even if their local datastore is reduced by a factor 3. Note that if we had changed the local dataset sizes also for old clients, the global model (and then the representation) would have changed too, making it difficult to isolate the effect of the local datastore size. We show the results for this experiment in Figure 6 (Appendix B).

Fairness across clients.

Effect of data heterogeneity. Figure 1 also shows that, as expected by Theorem 4.1, the benefit of the memorization mechanism is larger when data distributions are more heterogeneous (smaller α). While other methods also benefit from higher heterogeneity, kNN-Per appears to address statistical heterogeneity more effectively (Figure 10). Note that if local distributions were identical (α → ∞), no personalization method would provide any advantage.

Hyperparameters. kNN-Per's performance is not highly sensitive to the value k which can be selected between 7 and 14 for CIFAR-10 and between 5 and 12 for CIFAR-100 with less than 0.2 percentage points of accuracy variation (see Figure 5 in Appendix B). Similarly, scaling the Euclidean distance by a factor σ has almost no effect for values of σ between 0.1 and 100 and between 1 and 100, respectively for CIFAR-10 and CIFAR-100 (see Figure 7 in Appendix B). The interpolation parameter λ m plays a more important role. Experiments in Appendix B (Figure 8)

show that, as expected, the larger the local dataset, the more clients rely on the local kNN model. Interestingly, clients give a larger weight to the kNN model than to the global one (λ > 1/2) for datasets with just one hundred samples (Figure 2).

Effect of global model's quality. Assumption 4 stipulates that the smaller the expected loss of the global model, the better representations' distances capture the variability of x → D m (•|x) and then the more accurate the kNN model. This effect is quantified by Lemma A.2, where the loss of the local memorization mechanism is upper bounded by a term that depends linearly on the loss of the global model. In order to validate this assumption, we study the relation between the test accuracies of the global model and kNN-Per.

In particular, we trained a global model for CIFAR-10, in a centralized way, and we save the weights at different stages of the training, leading to global models with different accuracy. Figure 3 shows the test accuracy of kNN-Per with λ = 1 (i.e., when only the kNN predictor is used) as a func-Global model's test accuracy tion of the global model's test accuracy for different levels of heterogeneity. We observe that, quite unexpectedly, the relation between the two accuracies is almost linear. Additional experiments (also including CIFAR-100) in Appendix B confirm these findings.

Robustness to distribution shift. kNN-Per offers a simple and effective way to address statistical heterogeneity in a dynamic environment where client's data distributions change after training. We simulate such a dynamic environment as follows. Client m initially has a datastore with instances sampled from data distribution D m . At each time step t < t 0 , client m receives a batch of instances drawn from D m . At time step t 0 , a data distribution shift takes place, i.e., for t 0 ≤ t ≤ T , client m receives instances drawn from a data distribution D ′ m ̸ = D m . Upon receiving new instances, client m may use those instances to update its datastore. We consider 3 different strategies: (1) first-infirst-out (FIFO) where, at time step t, new instances replace the oldest ones; (2) concatenate, where the new samples are simply added to the datastore; (3) fixed datastore, where the datastore is not updated at all. Figure 4 shows the evaluation of the test accuracy across time. If clients do not update their datastores, there is a significant drop in accuracy as soon as the distribution changes at t 0 = 50. Under FIFO, we observe some random fluctuations for the accuracy for t < t 0 , as repository changes affect the kNN predictions. While accuracy inevitably drops for t = t 0 , it then increases as datastores are progressively populated by instances from the new distributions. Under the "concatenate" strategy, results are similar, but 1) accuracy increases for t < t 0 as the quality of kNN predictors improves for larger datastores, 2) accuracy increases also for t > t 0 , but at a slower pace than what observed under FIFO, as samples from the old distribution are never evicted. Experiments' details and results for CIFAR-100 are in Appendix B. fect of system heterogeneity and the possibility to use aggressive nearest neighbours compression techniques like ProtoNN [START_REF] Gupta | ProtoNN: Compressed and accurate kNN for resource-scarce devices[END_REF].

Appendix B also includes experiments to evaluate the ef-

Conclusion

In this paper, we showed that local memorization at each client is a simple and effective way to address statistical heterogeneity in federated learning. In particular, while a global model trained with classic FL techniques, like FedAvg, may not deliver accurate predictions at each client, it may still provide a good representation of the input, which can be advantageously used by a local kNN model. This finding suggests that combining memorization techniques with neural networks has additional benefits other than those highlighted in the seminal papers [START_REF] Grefenstette | Learning to transduce with unbounded memory[END_REF][START_REF] Joulin | Inferring algorithmic patterns with stack-augmented recurrent nets[END_REF] and the recent applications to natural language processing [START_REF] Khandelwal | Generalization through memorization: Nearest neighbor language models[END_REF]2020).

The better performance of kNN-Per in comparison to

FedRep and pFedGP show that jointly learning the shared representation and the local models (as FedRep and pFedGP do) may lead to potentially conflicting and interfering goals, but further study is required to understand this interaction. Semi-parametric learning [START_REF] Peter | Efficient and adaptive estimation for semiparametric models[END_REF] could be the right framework to formalize this problem, but its extension to a federated setting is still unexplored.

A. Proofs

In the general description of kNN-Per, and in our experiments, we considered that each client m ∈ [M ] uses its whole dataset S m both to train the base shared model h S -and the corresponding representation function ϕ h S -and to populate the local datastore.

In the analysis, for simplicity, we deviate by this operation and consider that each local dataset S m is split in two disjoint parts (S m = S ′ m ˙ S ′′ m ), with S ′ m used to train the base model and S ′′ m used to populate the local datastore. Moreover, we assume that the two parts have the same size, i.e., n ′ m = n ′′ m = n m /2 for all m ∈ [M ], where n ′ m and n ′′ m denote the size of S ′ m and S ′′ m , respectively. In general, the result holds if the two parts have a fixed relative size across clients (i.e., n ′ m1 /n m1 = n ′ m2 /n m2 for all m 1 and m 2 in [m]). Let S ′ denote the whole data used to train the base model, i.e., S ′ = m∈[M ] S ′ m . We observe that the base model h S is only function of S ′ , and then we can write h S ′ . Instead, the local model h

(1)
Sm is both a function of S ′ (used to learn the shared representation ϕ ′ S ) and of S ′′ m (used to populate the datastore). In order to stress such dependence, we then write h

E S∼⊗ M m=1 D nm m [L Dm (h m,λm )] ≤ (1 + λ m ) • L Dm (h * m ) + c 1 (1 -λ m ) • disc H D, D m + 1 + c 2 λ m • √ p p+1 √ n m • disc H D, D m + c 3 (1 -λ m ) • d H n • c 4 + log n d H + c 5 λ m • d H n • c 4 + log n d H • √ p p+1 √ n m , ( 14
)
where

h m,λm = λ m • h (1) S ′′ m ,S ′ + (1 -λ m ) • h S ′ . ( 15
)
From Assumption 3 and the linearity of the expectation, it follows

L Dm (h m,λm ) ≤ λ m • L Dm h (1) S ′′ m ,S ′ + (1 -λ m ) • L Dm (h S ′ ) . (16)
Using Lemma A.2 and Lemma A.1, and applying expectation over samples S ∼ ⊗ M m=1 D nm m , we have

E S∼⊗ M m=1 D nm m [L Dm (h m,λm )] ≤ λ m • E S ′ ∼⊗ M m=1 D nm /2 m E S ′′ ∼⊗ M m=1 D nm/2 m L Dm h (1) S ′′ m ,S ′ + (1 -λ m ) • E S ′ ∼⊗ M m=1 D nm /2 m E S ′′ ∼⊗ M m=1 D nm/2 m L Dm (h S ′ ) (17) ≤ 2λ m L Dm (h * m ) + 6λ m γ 1 √ p p+1 √ n m + 6λ m γ 2 √ p p+1 √ n m • E S ′ ∼⊗ M m=1 D nm/2 m [L Dm (h S ′ )] -L Dm (h * m ) + (1 -λ m ) • E S ′ ∼⊗ M m=1 D nm/2 m [L Dm (h S ′ )] (18)
≤ 2λ m L Dm (h * m ) + 6λ m γ 1 √ p p+1 √ n m + 6λ m γ 2 √ p p+1 √ n m • δ 1 • d H n • δ 2 + log n d H + 2 • disc H D, D m + (1 -λ m ) • L Dm (h * m ) + δ 1 • d H n • δ 2 + log n d H + 2 • disc H D, D m (19) = (1 + λ m )L Dm (h * m ) + 6λ m γ 1 √ p p+1 √ n m + 6λ m γ 2 √ p p+1 √ n m δ 1 • d H n • δ 2 + log n d H + 12λ m γ 2 √ p p+1 √ n m • disc H D, D m + δ 1 (1 -λ m ) • d H n • δ 2 + log n d H + 2 • (1 -λ m ) disc H D, D m . ( 20
)
Rearranging the terms and taking c 1 ≜ 2, c 2 ≜ max{12γ 2 , 6γ 1 }, c 3 ≜ δ 1 , c 4 ≜ δ 2 and c 5 ≜ 6γ 2 δ 1 , the final result follows.

A.2. Intermediate Lemmas

Lemma A.1. Consider m ∈ [M ], then there exists constants δ 1 , δ 2 ∈ R such that

E S ′ ∼⊗ M m=1 D nm /2 m [L Dm (h S ′ )] ≤ L Dm (h * m ) + δ 1 • d H n • δ 2 + log n d H + 2 • disc H D, D m , ( 21
)
where d is the VC dimension of the hypothesis class H, D = M m=1 nm n • D m and disc H is the label discrepancy associated to the hypothesis class H.

Proof. We remind that the label discrepancy associated to the hypothesis class H for two distributions D 1 and D 2 over features and labels is defined as [START_REF] Mansour | Three approaches for personalization with applications to federated learning[END_REF]:

disc H (D 1 , D 2 ) = max h∈H |L D1 (h) -L D2 (h)| . ( 22
) Consider m ∈ [M ] and h * ∈ arg min h∈H L D (h). For S ′ ∼ ⊗ M m=1 D nm/2 m
, we have

L Dm (h S ′ ) -L Dm (h * m ) = L Dm (h S ′ ) -L D (h S ′ ) + L D (h S ′ ) -L D (h * m ) + L D (h * m ) -L D (h * ) + L D (h * ) -L Dm (h * m ) (23) = L Dm (h S ′ ) -L D (h S ′ ) ≤disc H( Dm, D) + L D (h * m ) -L Dm (h * m ) ≤disc H( Dm, D) + L D (h * ) -L D (h * m ) ≤0 +L D (h S ′ ) -L D (h * ) (24) ≤ 2 • disc H D m , D + L D (h S ′ ) -L D (h * ) (25) = 2 • disc H D m , D + L D (h S ′ ) -L S ′ (h S ′ ) + L S ′ (h S ′ ) -L S ′ (h * ) ≤0 +L S ′ (h * ) -L D (h * ) (26) ≤ 2 • disc H D m , D + 2 • sup h∈H |L D (h) -L S ′ (h)| . (27)
We now bound

E S ′ ∼⊗ M m=1 D nm/2 m sup h∈H |L D (h) -L S ′ (h)|.
We first observe that for every h ∈ H, we can write

L D (h) = E S ′ ∼⊗ M m=1 D nm/2 m L S ′ (h).
Therefore, despite the fact that the samples in S ′ are not i.i.d., we can follow the same steps as in the proof of Shalev-Shwartz and Ben-David (2014, Theorem 6.11), and conclude

E S ′ ∼⊗ M m=1 D nm/2 m sup h∈H |L D (h) -L S ′ (h)| ≤ 4 + log (τ H (n)) √ n , (28)
where τ H is the growth function of class H.

Let d denote the VC dimension of H. From Sauer's lemma (Shalev-Shwartz and Ben-David, 2014, Lemma 6.10), we have that for

n > d + 1, τ H (n) ≤ (en/d) d H . Therefore, there exist constants δ 1 , δ 2 ∈ R (e.g., δ 1 = 4, δ 2 = max{4/ √ d H , 1}), such that E S ′ ∼⊗ M m=1 D nm/2 m sup h∈H |L D (h) -L S ′ (h)| ≤ δ 1 2 • d H n • δ 2 + log n d H . (29)
Taking the expectation in Eq. ( 27) and using this inequality, we have

E S ′ ∼⊗ M m=1 D nm /2 m [L Dm (h S ′ )] ≤ L Dm (h * m ) + δ 1 • d H n • δ 2 + log n d H + 2 • disc H D, D m . (30)
The following Lemma proves an upper bound on the expected error of the 1-NN learning rule.

Lemma A.2 (Adapted from (Shalev-Shwartz and Ben-David, 2014, Thm 19.3)). Under Assumptions 1, 2, and 4 for all m ∈ [M ], it holds

E S ′′ m ∼D nm /2 m L Dm h (1) S ′′ m ,S ′ ≤ 2L Dm (h * m ) + 6 γ 1 + γ 2 • L Dm (h S ′ ) -L Dm (h * m ) • √ p p+1 √ n m . (31)
Proof. Recall that for m ∈ [M ], the Bayes optimal rule, i.e., the hypothesis that minimizes L Dm (h) over all functions, is

h * m (x) = 1 {ηm(x)>1/2} . (32)
We note that the 1-NN rule can be expressed as follows:

h (1) S ′′ m ,S ′ (x) y = 1 y=π (1) S ′′ m (x) , (33)
where we are putting in evidence that the permutation π m depends on the dataset S ′′ m . Then, under Assumption 2, the loss function l(•) reduces to the 0-1 loss.

Consider samples S ∼ ⊗ M m=1 D nm m . Using Assumptions 1, 2 and 4, and following the same steps as in (Shalev-Shwartz and Ben-David, 2014, Lemma 19.1), we have

E S ′′ m ∼D nm/2 m L Dm h (1) S ′′ m ,S ′ -2L Dm (h * m ) ≤ γ 1 + γ 2 • L Dm (h S ′ ) -L Dm (h * m ) × E S ′′ m,X ∼D nm /2 m,X , x∼D m,X d ϕ h S ′ (x) , ϕ h S ′ π (1) S ′′ m (x) ≜T S ′ , (34)
where S ′′ m,X denotes the set of input features in the dataset S ′′ m and D m,X the marginal distribution of D m over X . Note that S ′′ m is independent from S ′ . As in the proof of (Shalev-Shwartz and Ben-David, 2014, Theorem 19.3), let T be an integer to be precised later on. We consider r = T p and C 1 , . . . , C r to be the cover of the set [0, 1] p using boxes with side 1/T . We bound the term T S ′ independently from S ′ as follows

E S ′′ m ∼D nm/2 m,X , x∼D m,X d ϕ h S ′ (x) , ϕ h S ′ π (1) S ′′ m (x) ≤ √ p 2T p n m e + 1 T . (35)
If we set ϵ = 2 2 nm 1 p+1 and T = ⌈1/ϵ⌉, it follows 1/ϵ ≤ T < 2/ϵ and then

E S ′′ m ∼D nm/2 m,X , x∼D m,X d ϕ h ′ (x) , ϕ h S ′ π (1) S ′′ m (x) ≤ √ p 2(2/ϵ) p n m e + ϵ (36) = √ p 1 e + 2 2 n m 1 p+1 (37) ≤ 6 √ p p+1 √ n m . (38)
Thus,

E S ′ m ∼D nm m L Dm h (1) S ′′ m ,S ′ ≤ 2L Dm (h * m ) + 6 √ p p+1 √ n m γ 1 + γ 2 • L Dm (h S ) -L Dm (h * m ) . ( 39

B. Additional Experiments

Effect of kernel scale parameter σ. We consider distance metrics of the form

∀z, z ′ ∈ R p ; d σ (z, z ′ ) = ∥z -z ′ ∥ 2 σ , (40)
where σ ∈ R + is a scale parameter. Figure 7 shows that kNN-Per's performance is not highly sensitive to the selection of the length scale parameter, as scaling the Euclidean distance by a constant factor σ has almost no effect for values of σ between 0.1 and 1000. Effect of datastore's size on the optimal λ. Figure 8 shows the effect of the local number of samples n m on the optimal mixing parameter λ opt (evaluated on the client's test dataset). The number of samples changes across clients and, for the same client, with different values of the capacity. The figure shows a positive correlation between the local number of samples and the optimal mixing parameter and then validates the intuition that clients with more samples tend to rely more on the memorization mechanism than on the base model, as captured by the generalization bound from Theorem 4.1.

Effect of hardware heterogeneity. In our experiments above, clients' local datasets had different size, which can also be due to different memory capabilities. In order to investigate more in depth the effect of system heterogeneity, we split the new clients in two groups: "weak" clients with normalized capacity 1/2 -∆C and "strong" clients with normalized capacity 1/2 + ∆C, where ∆C ∈ (0, 1/2) is a parameter controlling the hardware heterogeneity of the system. Note that the total amount of memory in the system is constant, but varying ∆C changes its distribution across clients from a homogeneous scenario (∆C = 0) to an extremely heterogeneous one (∆C = 0.5). Figure 9 shows the effect of the hardware heterogeneity, as captured by ∆C. As the marginal improvement from additional memory is decreasing (see, e.g., Fig. 1) the gain for strong clients does not compensate the loss for weak ones. The overall effect is then that the average test accuracy decreases as system heterogeneity increases.

Adding compression techniques. kNN-Per can be combined with nearest neighbours compression techniques as ProtoNN [START_REF] Gupta | ProtoNN: Compressed and accurate kNN for resource-scarce devices[END_REF]. ProtoNN reduces the amount of memory required by jointly learning 1) a small number of prototypes to represent the entire training set and 2) a data projection into a low dimensional space. We combined kNN-Per and ProtoNN and explored both the effect of the number of prototypes and the projection dimension used in ProtoNN.

For each client, the number of prototypes is set to a given fraction of the total number of available samples. We refer to this quantity also as capacity. We varied the capacity in the grid {i × 10 -1 , i ∈ [10]}, and the projection dimension in the grid {i × 100, i ∈ [12]} ∪ {1280}. Note that smaller projection dimension and less prototypes correspond to a smaller memory footprint, suited for more restricted hardware. Our implementation is based on ProtoNN's official. 5 Figure 11a shows that, on CIFAR-10, ProtoNN allows to reduce the kNN-Per's memory footprint by a factor four (using n m /3 prototypes and projection dimension 1000) at the cost of a limited reduction in test accuracy (82.3% versus 83.0% in Table 2). Note that kNN-Per with ProtoNN still outperforms all other methods. On CIFAR-100, ProtoNN's compression techniques appear less advantageous: the approach loses about 3 percentage points (52.1% versus 55.0% in Table 2) while only reducing memory requirement by 20%.

Effect of global model's quality. Assumption 4 stipulates that the smaller the expected loss of the global model, the more accurate the corresponding representation. As representation quality improves, we can expect that kNN accuracy

  Our generalization bound depends, as usual, on the complexity of the hypothesis class H (expressed by its VCdimension, d H ) and on the size of the local and global datasets (n m and n, respectively), but also on the distance between the local distribution D m and the average distribution D = M m=1 nm n • D m , which is the one the global model h S is targeting (see (

  d H n. Instead, when each client only uses the kNN model (λ m = 1), 2 we recover the kNN generalization bound in(Shalev-Shwartz and Ben-David, 2014, Thm 19.3).

Figure 1 .Figure 2 .

 12 Figure 1. Test accuracy vs capacity (local datastore size). The capacity is normalized with respect to the initial size of the client's dataset partition. Smaller values of α correspond to more heterogeneous data distributions across clients.

Figure 3 .

 3 Figure 3. Effect of the global model's quality on the test accuracy of kNN-Per with λ = 1. CIFAR-10.

Figure 4 .

 4 Figure 4. Effect of the global model's quality on the test accuracy of kNN-Per with λ = 1. CIFAR-10.

  ′ . A.1. Proof of Theorem 4.1 Theorem 4.1. Suppose that Assumptions 1-4 hold, and consider m ∈ [M ] and λ m ∈ (0, 1), then there exist constants c 1 , c 2 , c 3 , c 4 , and c 5 ∈ R, such that

  d H is the the VC dimension of the hypothesis class H, n = M m=1 n m , D = M m=1 nm n • D m , p is the dimension of representations, and disc H is the label discrepancy associated to the hypothesis class H. Proof. The idea of the proof is to bound both the expected error of the shared base model (Lemma A.1) and the error of the local kNN retrieval mechanism (Lemma A.2) before using the convexity of the loss function to bound the error of h m,λm . Consider S ∼ ⊗ M m=1 D nm m or, equivalently, S = S ′ ∪ S ′′ , where S ′ ∼ ⊗ M m=1 D nm/2 m , and S ′′ = ∪ m∈[M ] S ′′ m and S ′′ m ∼ D nm/2 m . For m ∈ [M ], and λ m ∈ (0, 1), we have

Figure 5 .

 5 Figure 5. Test accuracy vs number of neighbors k.

Figure 6 .

 6 Figure6. Test accuracy vs capacity (local datastore size) when the global model is retrained for each value of α. The capacity is normalized with respect to the initial size of the client's dataset partition. Smaller values of α correspond to more heterogeneous data distributions across clients. The curves start from different accuracy values for zero capacity, but are qualitatively similar to those in Figure1for large capacities. As expected, the global model performs worse the more heterogeneous the local distributions are, but the local model is able to compensate such effect (at least partially) as far as the datastore is large enough.

Figure 7 .

 7 Figure 7. Test accuracy vs the interpolation parameter λ for different values of the kernel scale parameter σ.

  . Clients could also use different values k m and different distance metrics d m (•), but, in what follows, we consider them equal across clients. Also our experiments in Sec. 6 show that k and d(•) do not require careful tuning.

Table 1 .

 1 Datasets and models. ) and allocated to client m a p y,m fraction of all training instances of class y. The approach ensures that the number of data points and label distributions are unbalanced across clients. For CIFAR-100, we exploit the availability of "coarse" and "fine" label structure, to partition the dataset using pachinko allocation method[START_REF] Li | Pachinko allocation: Dag-structured mixture models of topic correlations[END_REF] as in[START_REF] Sashank | Adaptive federated optimization[END_REF]. The method generates local datasets with heterogeneous distributions by combining a per-client Dirichlet distribution with parameter α = 0.3 (unless otherwise specified) over the coarse labels and a per-coarse-label Dirichlet distribution with parameter β = 10 over the corresponding fine labels. We also partitioned CIFAR-10 and CIFAR-100 in a different way following (Achituve et al.We compared kNN-Per with locally trained models (with no collaboration across clients) and FedAvg[START_REF] Mcmahan | Communicationefficient learning of deep networks from decentralized data[END_REF], as well as with one method for each of the personalization approaches described in Sec. 2, namely, FedAvg+(Jiang et al., 2019), 3 ClusteredFL[START_REF] Sattler | Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints[END_REF], Ditto[START_REF] Li | Ditto: Fair and robust federated learning through personalization[END_REF], FedRep[START_REF] Collins | Exploiting shared representations for personalized federated learning[END_REF], APFL[START_REF] Deng | Adaptive personalized federated learning[END_REF], and pFedGP (Achituve

	DATASET	TASK	CLIENTS TOTAL SAMPLES MODEL
	FEMNIST	HANDWRITTEN CHARACTER RECOGNITION	3, 550	805, 263 MOBILENET-V2
	CIFAR-10	IMAGE CLASSIFICATION	200	60, 000 MOBILENET-V2
	CIFAR-100	IMAGE CLASSIFICATION	200	60, 000 MOBILENET-V2
	SHAKESPEARE NEXT-CHARACTER PREDICTION	778	4, 226, 158 STACKED-LSTM

specified, 2021): each client has only samples from two and ten classes for CIFAR-10 and CIFAR-100, respectively. We refer to the resulting datasets as CIFAR-10 (v2) and CIFAR-100 (v2). For FEMNIST and Shakespeare, we randomly split each local dataset into training (60%), validation (20%), and test (20%) sets. For CIFAR-10 and CIFAR-100, we maintained the original training/test data split and used 20% of the training dataset as validation dataset. Table

1

summarizes datasets, models and number of clients.

Models and representations.

For CIFAR-100, CIFAR-10, and FEMNIST, we used MobileNet-v2

[START_REF] Sandler | Mobilenetv2: Inverted residuals and linear bottlenecks[END_REF]

as a base model with the output of the last hidden layer-a 1280-dimensional vector-as representation. For Shakespeare, the base model was a stacked LSTM model with two layers, each of them with 256 units; a 1024-dimensional representation was obtained by concatenating the hidden states and the cell states.

Benchmarks.

Table 2 .

 2 Test accuracy: average across clients / bottom decile.

	DATASET	LOCAL	FE DAV G	FE DAV G +	CL U S T E R E DFL	DI T T O	FE DRE P	APFL	PFE DGP	KNN-PE R (OURS)
	FEMNIST	71.0 / 57.5 83.4 / 68.9 84.3 / 69.4	83.7 / 69.4	84.3 / 71.3 85.3 / 72.7 84.1 / 69.4	-/ -	88.2 / 78.8
	CIFAR-10	57.6 / 41.1 72.8 / 59.6 75.2 / 62.3	73.3 / 61.5	80.0 / 66.5 77.7 / 65.2 78.9 / 68.1	-/ -	83.0 / 71.4
	CIFAR-10 (V2)	82.4 / 71.3 67.9 / 60.1 85.0 / 79.6	79.9 / 72.3	86.3 / 80.6 89.1 / 85.3 82.6 / 76.4 88.9 / 84.1 93.8 / 88.2
	CIFAR-100	31.5 / 19.8 47.4 / 36.0 51.4 / 41.1	47.2 / 36.2	52.0 / 41.4 53.2 / 41.7 51.7 / 41.1	-/ -	55.0 / 43.6
	CIFAR-100 (V2) 45.7 / 38.2 42.3 / 34.8 48.1 / 41.9	43.5 / 37.2	48.7 / 40.3 70.1 / 65.2 48.3 / 42.1 61.1 / 50.0 74.6 / 67.3
	SHAKESPEARE	32.0 / 16.0 48.1 / 43.1 47.0 / 42.2	46.7 / 41.4	47.9 / 42.6 47.2 / 42.3 45.9 / 42.4	-/ -	51.4 / 45.4

Table 3 .

 3 Average test accuracy across clients unseen at training (train accuracy between parentheses).

	Dataset	FedAvg	FedAvg+ ClusteredFL	Ditto	FedRep	APFL	pFedGP	kNN-Per (Ours)
	FEMNIST	83.1 (83.3) 84.2 (88.5)	83.2 (86.0)	83.9 (86.9) 85.4 (88.9) 84.2 (85.5)	-	88.1 (90.5)
	CIFAR-10	72.9 (72.8) 75.3 (78.2)	73.9 (76.2)	79.7 (84.3) 76.4 (79.5) 79.2 (80.6)	-	82.4 (87.1)
	CIFAR-10 (v2)	67.5 (68.1) 85.1 (85.0)	79.6 (79.9)	85.9 (86.0) 89.0 (89.1) 82.3 (82.5) 89.0 (88.8) 93.0 (93.1)
	CIFAR-100	47.1 (47.5) 50.8 (53.4)	47.1 (48.2)	52.1 (57.3) 53.5 (58.2) 49.1 (52.7)	-	56.1 (59.3)
	CIFAR-100 (v2) 42.1 (42.2) 47.9 (48.1)	43.2 (43.4)	48.8 (48.5) 69.8 (70.0) 48.2 (48.4) 61.3 (61.0) 74.3 (74.5)
	Shakespeare	49.0 (48.3) 49.3 (48.1)	49.4 (46.7)	48.1 (49.2) 48.7 (47.8) 46.1 (52.7)	-	50.7 (64.2)
	6. Experiments

Average performance of personalized models. The performance of each personalized model (which coincides with the global one in the case of FedAvg) is evaluated on the local test dataset (unseen at training). Table

2

shows the average weighted accuracy with weights proportional to local dataset sizes. kNN-Per consistently achieves the highest accuracy across all datasets. We observe that Local performs much worse than any other FL method as expected (e.g., 25 pp w.r.t. kNN-Per or 22 pp w.r.t. to Ditto on CIFAR-10). Local outperforms some other FL methods on CIFAR-10/100 (v2). This splitting was proposed in pFedGP's paper-where the same result is observed

(Achituve et al., 2021, Table

Table 2

 2

	also shows the bottom
	decile of the accuracy of personalized models, i.e., the
	(M/10)-th worst accuracy (the minimum accuracy is par-
	ticularly noisy, notably because some local test datasets are
	very small). We observe that even clients with the worst
	personalized models are still better off when kNN-Per is
	used for training.
	Generalization to unseen clients. An advantage of
	kNN-Per is that a "new" client arriving after training may
	easily learn a personalized model: it may simply retrieve

the global model (whose training it did not participate to) from the orchestrator and use it to build the local datastore for kNN. Even if this scenario was not explicitly considered in their original papers, other personalized FL methods can also be adapted to new clients as follows. FedAvg+ personalizes the global model through stochastic gradient updates on the new client's local dataset. Ditto operates similarly, but maintains a penalization term proportional to the distance between the personalized model and the global model. FedRep trains the network head using the local dataset, while freezing the body as in the global model. For pFedGP new clients inherit the previously trained shared network and compute their local kernel. ClusteredFL assigns the new client to one learned cluster model using a held-out validation set. In the case of FedAvg, there is no personalization and the new client uses directly the global model. We performed an experiment where only 80% of the clients participated to the training and the remaining 20% joined later. Results in Table

3

show that, despite its simplicity in dealing with new clients, kNN-Per still outperforms all other methods.

Inria, Université Côte d'Azur, Sophia Antipolis, France

Accenture Labs, Sophia Antipolis, France. Correspondence to: Othmane Marfoq <othmane.marfoq@inria.fr>.

Note that the kNN model still relies on the representation provided by the global model.

We also implemented the more sophisticated first-order MAML approach from(Fallah et al., 2020), but had worse performance than FedAvg+.

 4 We were able to run the official pFedGP's code (https: //github.com/IdanAchituve/pFedGP) only on datasets partitioned as in[START_REF] Achituve | Personalized federated learning with gaussian processes[END_REF].

https://github.com/Microsoft/EdgeML.

We always make sure that |Sm| ≤ |S ′ m |.

Acknowledgments

This work has been supported by the French government, through the 3IA Côte d'Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002. The authors are grateful to the OPAL infrastructure from Université Côte d'Azur for providing computational resources and technical support.

improves too. This effect is quantified by Lemma A.2, where the loss of the local memorization mechanism is upper bounded by a term that depends linearly on the loss of the global model. In order to validate this assumption, we study the relation between the test accuracies of the global model and kNN-Per. In particular, we train two global models, one for CIFAR-10 and the other for CIFAR-100, in a centralized way, and we save the weights at different stages of the training, leading to global models with different qualities. Figure 12 shows the test accuracy of kNN-Per with λ = 1 (i.e., when only the knn predictor is used) as a function of the global model's test accuracy for different levels of heterogeneity on CIFAR-10 and CIFAR-100 datasets. We observe that, quite unexpectedly, the relation between the two accuracies is almost linear. The experiments also confirm what observed in Fig. 1: kNN-Perperforms better when local distributions are more heterogeneous (smaller α). Similar plots with λ optimized locally at every client are shown in Fig. 13.

Robustness to distribution shift. As previously mentioned, kNN-Per offers a simple and effective way to address statistical heterogeneity in a dynamic environment where client's data distributions change after training. We simulate such a dynamic environment as follows. Client m initially has a datastore built using instances sampled from a data distribution D m . For time step t < t 0 , client m receives a batch of n

m instances drawn from D m . At time step t 0 , we suppose that a data distribution shift takes place, i.e., for t 0 ≤ t ≤ T , client m receives n . These batches are the new samples arriving at client m. Similarly, S ′ m is partitioned into T -t 0 equally sized batches. Figure 14 shows the evaluation of the test accuracy across time. If clients do not update their datastores, there is a significant drop in accuracy as soon as the distribution changes at t 0 = 50. If datastore are updated using FIFO, we observe some random fluctuations for the accuracy for t < t 0 , as repository changes affect the kNN predictions. While accuracy inevitably drops for t = t 0 , it then increases as datastores are progressively populated by instances from the new distributions. Once all samples from the previous distributions are evicted, the accuracy settles around a new value (higher or lower than the one for t < t 0 depending on the difference between the new and the old distributions). If clients keep adding new samples to their datastores (the "concatenate" strategy), results are similar, but 1) accuracy increases for t < t 0 as the quality of kNN predictors improves for larger datastores, 2) accuracy increases also for t > t 0 , but at a slower pace than what observed under FIFO, as samples from the old distribution are never evicted.


Nicolas Belloir
email: nicolas.belloir@irisa.fr

Wassila Ouerdane

Oscar Pastor

Characterizing Fake News: A Conceptual Modeling-based Approach

Keywords: Conceptual Modeling, Characterization, Fake News, Explainable Artificial Intelligence

For some time, and even more so now, Fake News has increasingly occupied the media and social space. How identify Fake News and conspiracy theories have become an extremely attractive research area. However, the lack of a solid and well-founded conceptual characterization of what exactly Fake News is and what are its main characteristics, makes it difficult to manage their understanding, identification, and detection. This research work advocates that conceptual modeling must plays a crucial role in characterizing Fake News content accurately. Only by delimiting what Fake News is will it be possible to understand and manage their different perspectives and dimensions, with the ultimate goal of developing a reliable framework for online Fake News detection, as much automated as possible. To contribute in that direction from a pure and practical conceptual modeling perspective, this paper proposes a precise conceptual model of Fake Newss, an essential element for any explainable Artificial Intelligence (XAI)-based approach that must be based on the shared understanding of the domain that only such an accurate conceptualization dimension can facilitate.

Introduction

Conceptual modeling is a discipline that contributes rich and diverse results when applied to well-understand the conceptual support of a particular domain of interest. One domain especially interesting nowadays is the Fake News one. Although Fake News is not a new phenomenon [START_REF] Tandoc | Defining "Fake News": A typology of scholarly definitions[END_REF], questions such as why it has emerged as a global topic of interest and why it is attracting increasingly more public attention are particularly relevant in our times. The leading cause is that fake news can be created and published online faster and cheaper when compared to traditional news media such as newspapers and television [START_REF] Shu | Fake news detection on social media: A data mining perspective[END_REF]. In addition, recent discussions of higher education's failure to teach students how to identify Fake Newshave appeared in leading newspapers [START_REF]Op-ed: Why can't a generation that grew up online spot the misinformation in front of them? Los Angeles Times[END_REF].

Conceptual Modeling should play an essential role to understand and communicate what Fake News is. In a sound Information Conceptual Modeling context, a correct data management of Fake News must be supported by a precise conceptual characterization of "what" a Fake News is. This is where Conceptual Modeling becomes a crucial actor. If an information structure must represent a conceptualization, the entities that represent that conceptualization must be explicitly determined. Any information system intended to register information about Fake News must identify in detail what are the relevant entities that conceptually characterize the different dimensions that must be considered to treat Fake News data correctly. Ontologically speaking, a precise ontological commitment that involves a precise identification of the relevant entities that constitute the conceptualization must be stated. Our previous work has focused on exploring what are the concepts that should be considered for achiving that purpose. In this paper we introduce the result of such an ontological analysis, presenting a conceptual model of Fake News. This is the main contribution here addressed, by facing a fundamental question regarding the terminology and the ontology of Fake News: what constitutes and qualifies as Fake News?.

To achieve that goal, in Section 2 we discuss the literature and show that the views on the concept of Fake News are not unified. On the way to propose the conceptual model of Fake News, Section 3 explores the key notions that must be taken into account when the goal is to provide a sound conceptual characterization of the Fake News notion. As a consequence, a precise definition of Fake News is proposed, and a Fake News Conceptual Model is presented in Section 4. A discussion of the application of this conceptual model as an initial building block for an XAI approach is provided in Section 5. Concluding remarks and the list of used references complete the work.

Related Work

In recent years, different works were interested in studying and understanding the nature of information encompassed in Fake News. Indeed, to help online users identify valuable information, there has been extensive research on establishing practical and automatic frameworks for online Fake News detection [START_REF] Ansar | Combating the menace: A survey on characterization and detection of fake news from a data science perspective[END_REF][START_REF] Zhou | A survey of fake news: Fundamental theories, detection methods, and opportunities[END_REF][START_REF] Zhang | An overview of online fake news: Characterization, detection, and discussion[END_REF].

An important element is to be able to identify very clearly what is a Fake News or what are the principal features characterizing it. However, what we can notice first in the literature is that the concept of Fake News is still ambiguous, and the frontier between the definition of Fake News and other related concepts, such as mis-information, des-information, hoax news, propaganda news, etc., is blurred. Indeed, as it is illustrated by some categorization examples [START_REF] Tandoc | Defining "Fake News": A typology of scholarly definitions[END_REF][START_REF] Wang | Fake news and related concepts: Definitions and recent research development[END_REF][START_REF] Kumar | False information on web and social media: A survey[END_REF], it is not always clear or precise how these different concepts are related, or how we can distinguish between theme. On the other hand, as we can see in Table 1, several definitions of Fake News have been proposed in the literature, most of which include falsehood and the news form as common factors. Even if it can be argued that there is some common intuition on what a Fake News is, what we can note is that it is difficult to have a consensus and a unified vision on what "exactly" -conceptually-speaking-a Fake News is.

Definitions

Reference Fake News is a news article that is intentionally and verifiably false.

[18] Fake News are intentionally false news published by a news outlet [START_REF] Zhou | A survey of fake news: Fundamental theories, detection methods, and opportunities[END_REF] Fabricated news articles that could be potentially or intentionally misleading for the readers [START_REF] Pierri | False news on social media: A data-driven survey[END_REF] News articles that are intentionally and verifiably false, and could mislead readers [START_REF] Allcott | Social media and fake news in the 2016 election[END_REF] Fabricated information that mimics news media content in form but not in organisational process or intent [START_REF] Lazer | The science of fake news[END_REF] Fake News are fabricated stories presented as if they were originating from legitimate sources with an intention to deceive [START_REF] Katsaros | Which machine learning paradigm for fake news detection?[END_REF] Table 1. A Sample of Fake News Definitions A recent work has proposed a first step towards a characterization of Fake News [START_REF] Molina | fake news" is not simply false information: A concept explication and taxonomy of online content[END_REF]. It introduces a taxonomy of operational indicators in four domain (message, source, structure, and network) to distinguish seven types of online content under the label of "Fake News" (false news, polarized content, satire, etc.). The proposed characterization is of interest, but it is not based on a precise conceptual model, which is our contribution in this paper. As a representation that captures the conceptualization of a person's understanding of a domain, a conceptual model is the natural strategy for obtaining a reliable representation of the domain that is used by human users to support communication, discussion, negotiation, etc. In our context, it allows us to define a domain with specific and precise semantics. Moreover, the conceptual model will expose the relationships between the concepts composing the Fake News in a more informative and robust way, which will offer a reliable and practical means for the detection or even automatic generation of Fake News. In this line, [START_REF] Weiss | Toward a comprehensive model of fake news: A new approach to examine the creation and sharing of false information[END_REF] have proposed a conceptual model to examine the phenomenon of Fake News. Their model focuses on the relationship between the creator and the consumer of the information, and proposes a mechanism to determine the likelihood that users will share their Fake News with others. In contrast, in this paper, we are particularly interested in the conceptualization of the content of Fake News.

A further advantage of relying upon a conceptual model is its ability to facilitate building well-justified and explainable models for Fake News detection and generation, which, to date, have rarely been available. Works as [START_REF] Bani-Hani | Fandet Semantic Model: An OWL Ontology for Context-Based Fake News Detection on Social Media[END_REF] explores and integrates the use of ontologies (OWL-based) trying to detect fake news on social media by identifying contextual features for news articles. However, as it was emphasized by [START_REF] Zhou | A survey of fake news: Fundamental theories, detection methods, and opportunities[END_REF][START_REF] Zafarani | Fake news research: Theories, detection strategies, and open problems[END_REF], despite the surge of works around the concept of Fake News, how one can automatically assess news authenticity in an effective and explainable manner is still an open issue, especially due to the lack of the precise conceptual characterization of the Fake News concept that this paper advocates.

Facilitating explainability and interpretability has been of great interest in artificial intelligence and machine learning research (see for instance [START_REF] Gilpin | Explaining explanations: An overview of interpretability of machine learning[END_REF][START_REF] Guidotti | A survey of methods for explaining black box models[END_REF]). Indeed, eXplainable Artificial Intelligence (XAI) is recognized as a major need for future applications. It aims to produce intelligent systems that enhance the confidence of users to understand the underlying reasoning and automations [START_REF] Gunning | Xai: Explainable artificial intelligence[END_REF][START_REF] Arrieta | Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai[END_REF]. For Fake News context, to our knowledge, works involving explainability feature within Fake News detection methods are still at their beginning [START_REF] Shu | Defend: Explainable fake news detection[END_REF].

In this paper, we propose an original approach to contribute to understanding what is a Fake News. Our proposal is novel at different levels. First, we offer to characterize Fake News content by relying on a Conceptual Model. A conceptual understanding of Fake News will help us distinguish them better and rule them from real news. A well-grounded conceptual characterization would make feasible to go beyond what the classical approaches normally do, by opening the door to design a Fake News generation process fully guided by the Conceptual Model. More precisely, we follow the XAI-based process proposed by [START_REF] Spreeuwenberg | AIX: Artificial Intelligence needs eXplanation: Why and how transparency increases the success of AI solutions[END_REF] to facilitate building well-justified and explainable models for Fake News generation. Our aim is to propose an approach that is understandable, trustable and manageable to humans, as suggested in [START_REF] Gunning | Explainable artificial intelligence (xai)[END_REF]. More specifically, the different steps suggested by [START_REF] Spreeuwenberg | AIX: Artificial Intelligence needs eXplanation: Why and how transparency increases the success of AI solutions[END_REF] are: (i) Get a shared understanding of the domain, (ii) Understand the task and select the right scope, (iii) Collect the right data and improve its quality, (iv) Select AI techniques that deliver results, (v) Generate good explanations, and (vi) Evolve the solution over time. Our contribution establishes the foundation of such a process by solving the first, essential step of getting a shared understanding of what a Fake News is by introducing a precise conceptual model of Fake News. From that sound conceptual basis, the rest of the proposed XAI process can be applied in a reliable way. The explainability with our approach is conceptually guided by the conceptual model which conforms the core of the contribution: to have an ontologically well-grounded definition of what a Fake News is, which is directly derived from the conceptual model.

Characterization of Fake News

We briefly present our definition of the concept of Fake News and a summary of the essential semantic elements to be considered in the characterization of the concept of fake news. Both have been proposed and discussed in a previous publication [START_REF] Belloir | A conceptual characterization of fake news: A positioning paper[END_REF] and we invite the reader who wants more details to consult it. Definition 1 (Fake News). A Fake News is false but verifiable news composed of false facts based on real ones. Drafted in a way to trigger an emotional load, it aims to deceive its readers and influence their opinion through an implicit conclusion.

Among the highlights that have been identified, one concerns the origin of fake news. Indeed, in the same way that a cyber-attack is rarely the work of a single person but rather that of an organized group or even a state service, fake news is rarely created by an isolated person. However, identifying the chain of creation of a fake news allows us to understand what objective it serves, and therefore to better understand and counter it. Thus, a conceptual model of fake news must be able to take into account the entities that were involved in the creation of a fake news and the different levels of decision-making involved. For example, at the moment fake news targets pro-Ukrainian political figures. This is part of an operational context aimed at manipulating pro-Ukrainian opinion and part of a strategic vision that seeks to justify the Ukrainian-Russian war.

Fake News is usually built on a distortion of reality. Representing this distortion is a second point of interest for the characterization of a fake news. Indeed, even if we can find fake news totally false, most of the time they are built by mixing true facts and false facts. This increases its credibility. The thinner the border between the two, the harder the fake news is possible. The real facts can take different forms. For instance, real facts can come from a political statement, an event that occurred, or real data such as a photo or video. In the same way, there are different forms of false facts. Indeed, as mentioned earlier, false facts may not be based on any real element. This makes it less credible. Other times, the false fact may be constituted by distortion of real elements. Photos or videos can be altered, articles can be falsified. Finally, one can take them out of their context of real facts for example, or associate several real facts but independent of each other.

In order to reinforce the credibility of a fake news, their authors often use an authority. The latter can be of different nature but its objective is always to reinforce the realistic side of the Fake News by relying on a reassuring element. This authority can be of three types: internal, external or false. In the first two cases, the authority is real. For the first one, the authority can be a person or an entity in direct link with the subject carried by the Fake News. In the second case, it may be a reference to a historical authority whose word or deed is considered true and safe. Finally, in the last case, the authority may be totally invented or its field of competence may have nothing to do with the information carried by the Fake News.

Fake news is constructed to influence the opinion of its target by generating an emotional charge. The reaction of the target leads him to draw certain conclusions and to change his opinion on a subject. That is the objective. Identifying the latter and knowing who the fake news is aimed at is therefore a challenge in order to try to counter it. Thus, in a conceptual model, three aspects need to be addressed: the target, its opinion on a topic and the way in which the fake news will change it. It can seek to strengthen or weaken it. We talk about the goal of fake news. The human mind can be seen as a two-tiered system. The first is instinctive, almost automatic. It reacts to perception, to emotion. The second is slower, more analytical. Fake news takes advantage of these two systems. It generates an emotion which makes the first system react. Then, in a second step, the second system analyzes the reaction to the emotion and to what generated it and draws conclusions. A fake news must therefore be able to trigger an emotion. It does this by a catalyst mechanism. Then, the target of the fake news reacts to this emotion and goes where the fake news wants to take him. A conceptual model must therefore be able to capture this mechanism.

The conceptual model that we present is articulated using the three main dimensions of: (i) identification of the origin of the fake news (the 'attacker' dimension), (ii) the relationship between true and false fact (the 'fact' dimension), and (iii) the target including opinion and reactive emotion (the 'target' dimension). They all together vertebrate the conceptual model of Fake News that we present in the next section.

Conceptual Model

In this section, we present a Fake News conceptual model. It captures the main points of view identified through Section 3. The Attacker sub-model describes the context in which the Fake News is created. The Target sub-model allows designing the target population of the Fake News and the psychological effects generated by it. The Fact sub-model allows specifying the real fact on which a Fake News is based and the way it will be altered to produce the desired psychological effect.

To illustrate this section, we draw on an identified Fake News that was disseminated during the 2016 U.S. presidential campaign : it was published by a Donald Trump's supporter named Sean Hannity and stated that Trump helped 200 marines to come home after Iraq war as illustrated by the Figure 1.

Attacker sub-model

The Figure 2 is a part of the complete conceptual model describing the actors directly or indirectly involved in Fake News creation process. As mentioned above, it is common that the creation of a Fake News is the result of a structured disinformation campaign, in which we find a classic division into three levels of responsibility: strategic, operational and tactical. At the head of the organization is the Strategic Attacker managing the Information Warfare and commanding Campaign Leaders. These Campaign Leaders manage the Disinformation Campaigns and have the Fake News Creator under their command to feed these campaigns with Fake News. The latter are created to be conform within a Disinformation Campaign. This is represented by the Is a part of relationship. Moreover, a Disinformation Campaign can also re-use a Fake News for its own purposes. Indeed, some of them can become viral and some campaigns could grasp the opportunity to re-use them to fulfill their own goals. It is represented by the Re-uses relationship. Both Information Warfare and Disinformation Campaign can be characterized by the context in which they are conducted. The Figure 3

Fact sub-model

This part of the model illustrated in Figure 4 details the facts on which a Fake News relies. Figure 5 shows how data populate it.

Fake News is the key notion. The entire diagram is created around it. title of a Fake News consists of its headline and is described by a string. subject corresponds to the category of knowledge it refers to. description is a textual summary of the key ideas contained in. tacticalImpact is an integer evaluating the number of potential readers, expressing the size of the targeted population.

A Fake News relies on at least one Real Fact. Since the context is important to understand the Real Fact itself, it is modeled through the context attribute. The description attribute provides a textual description of the Real Fact. It is characterized by a value stored in an enumeration : DATA, STATEMENT, or EVENT. A Real Fact can also be illustrated by a Document, which can either be a PICTURE, a FIGURE or a VIDEO.

False Facts contains its own description. It can be specified in three categories: made-up event, deformation of the truth or combination of true events. An Authority has a name and an expertise field. The three types of references to an authority discussed above make it possible to divide the concept into two simpler categories : true and false authorities. While the true authority did say or publish what is claimed to have been said or published, the false authority didn't. Thus, a Fake News can call upon an Authority, which can be either a True Authority, linked to a Real Fact, or a False Authority, linked to a False Fact. In both cases, the Authority is characterized by a Credibility regarding the fact at hand. A False Authority also includes a Boolean attribute which models whether the Authority is a real entity or not.

Target sub-model

Fake News target specific communities and aim at affecting as many people as possible. To do that, they use cognitive mechanisms. The part of the model illustrated in Figure 6 deals with the target of the Fake News and the process through which it is influenced by the content, while Figure 7 shows a data example instantiation.

A Target corresponds to the group of people that the Fake News intends to reach and influence. targetCharacteristics are their descriptions. They determine what makes them the Target. targetValues are ideas about which the readers will be especially sensitive about. An effective Fake News will twist these values to elaborate the Trigger Idea and maximize the Emotional Load. Fake News are spread through a media which can be either conventional, state-affiliated, alternative, or social. It is represented by Vector in the model. It also defines the Trust that the Target has in it. The latter is measured with an intensity : low, medium or high. A Target expresses an Opinion about an opinionSubject. It is described with the opinionDescription and the type classifies the position: pro, anti, or neutral. This opinion depicts the target's original thinking before being influenced by the Fake News, i.e., changed or strengthened. Note that the manipulation of the Opinion starts with the Disinformation Campaign. The Goal of the Fake News can either be to WEAKEN or STRENGTHEN the opinion expressed by the target. Its action is determined by the Processed Information. Fake News contains Trigger Ideas which represent arguments in favor of the Processed Information. The latter is the mixing effect of an emotion and an information. It represents how the information is assimilated and understood by the target. It is directly responsible for influencing or changing the opinion of the target. Processed Information conveys an implicitConclusion through its Trigger Ideas. Fake News aims to influence opinions and lead the target to come to the desired conclusion. The emotional load enhances the phenomena. The trigger ignites an Emotional Load. Emotional load has a type which can be chosen among the eight standard emotions: JOY, TRUST, FEAR, SURPRISE, SADNESS, ANTICIPATION, ANGER and DISGUST. The intensity of the load is evaluated based on the Plutchik wheel [START_REF] Plutchik | Theories of emotion[END_REF].

Discussion

The focus of our proposal is a Conceptual Model for Fake News. Our next further work includes a n intensive validation process, that we have started to accomplish For lack of space, we will not detail the study, but we refer the reader to this website: https://people.irisa.fr/Nicolas.Belloir/public/ER2022. Some relevant conclusions have been obtained. Concerning the attacker part of the model, it is sometimes tricky to formally identify the operational and strategic levels in which a Fake News operates. This is not surprising since one of the pillars of disinformation is to hide the initiators to make it more credible. However, they can often be guessed. Concerning the Facts part of the model, we note that the different types of False Facts appear equitably. We also note that the studied Fake News often play on the difference between correlation and causality, especially when a Fake News is built around several True Facts, which is not surprising. We also find an equal distribution of true and false authorities. Finally, if we look at the Target part, the emotional mechanisms are pretty easily identifiable, as well as the objective of the Fake News. However, if this study shows us that we manage to characterize existing Fake News with our model, the number of studied examples remains limited, and the conclusions we draw We also used the conceptual model to create a Fake News. The advantage of relying on a conceptual model is that it allows associating a process that will enable to control the Fake News generation. Such a formalized process is still a challenge, but our conceptual model is the first step to make it possible because it increases the interpretability of the resulting Fake News.

Indeed, explainability and interpretatbility is recognized as a major feature for future intelligent systems in AI and Machine Learning research. Known under the name eXplainable Artificial Intelligence (XAI), the aim is to produce intelligent systems that enhance the confidence of users to understand the underlying reasoning and automations [START_REF] Gunning | Xai: Explainable artificial intelligence[END_REF]. For Fake News context, to our knowledge, works involving explainability feature within Fake News detection methods are still at their beginning [START_REF] Shu | Defend: Explainable fake news detection[END_REF]. A promising line of work is to follow the XAI-based process proposed by [START_REF] Spreeuwenberg | AIX: Artificial Intelligence needs eXplanation: Why and how transparency increases the success of AI solutions[END_REF] to facilitate building well-justified and explainable models for Fake News generation. The idea is to offer an approach that is understandable, trustable and manageable to humans, as suggested in [START_REF] Gunning | Xai: Explainable artificial intelligence[END_REF]. The contribution of this paper establishes the foundation of such a process by solving the first, essential step of getting a shared understanding of what a Fake News is by introducing a precise conceptual model of Fake News. From that sound conceptual basis, the rest of the proposed XAI process can be applied in a reliable way. The explainability with our approach will be conceptually guided by the conceptual model which conforms the core of the contribution: to have an ontologically wellgrounded definition of what a Fake News is, which is directly derived from the conceptual model.

Conclusion

This paper presents a conceptual model of Fake News allowing to identify and specify the relevant entities that conceptually characterize the different dimensions that must be considered in Fake News. We believe that this model will contribute significantly to improving tools for generating/detecting fake news. Under a sound conceptual modeling perspective, we argue that a correct Fake News management process will only be feasible if it is based on a precise conceptual modeling approach, as the one proposed in this paper. We have chosen to focus on the following main aspects: the production chain, the articulation around true and false facts, and the manipulation mechanism used by Fake News and based on emotions. We have confronted this conceptual model to up to ten different fake news in order to evaluate its conformity. The first results are encouraging. A larger study will be conducted in the near future in order to evaluate its scaling up. Moreover, the proposition addresses the first step of the XAI process proposed by [START_REF] Spreeuwenberg | AIX: Artificial Intelligence needs eXplanation: Why and how transparency increases the success of AI solutions[END_REF], that it is crucial to make possible the full XAI-based process. The explainability with our approach is conceptually guided by the conceptual model which conforms the core of the contribution: to have an ontologically well-grounded definition of what a Fake News is, which is directly derived from the conceptual model. The next steps of the process are naturally our future work.

Fig. 1 .

 1 Fig. 1. Fake News stating that Donald Trump helped 200 Marines return to the US

  illustrate how data are integrated into the different classes of the conceptual model.

Fig. 2 .

 2 Fig. 2. Fake News Attacker Conceptual Model

Fig. 3 .

 3 Fig. 3. Illustration of the use of the conceptual model Attacker part

Fig. 4 .

 4 Fig. 4. Fake News Fact Conceptual Model

Fig. 5 .

 5 Fig. 5. Illustration of the use of the conceptual model Fact part

  ). Results have been very positive: with the support of the conceptual model, we have been able to characterize all of them in detail, what reinforces Fake News communication and management, our main purpose.

Fig. 6 .

 6 Fig. 6. Fake News Target Conceptual Model

Fig. 7 .

 7 Fig. 7. Illustration of the use of the conceptual model Target part

Table 2 .

 2 Fake News used for conceptual model evaluation