# EHRKit: A Python Natural Language Processing Toolkit for
Electronic Health Record Texts

Irene Li, Keen You, Xiangru Tang, Yujie Qiao, Lucas Huang,
Chia-Chun Hsieh, Benjamin Rosand, Dragomir Radev
Yale University

###### Abstract

The Electronic Health Record (EHR) is an essential part of the modern medical
system and impacts healthcare delivery, operations, and research. Unstructured
text is attracting much attention despite structured information in the EHRs
and has become an exciting research field. The success of the recent neural
Natural Language Processing (NLP) method has led to a new direction for
processing unstructured clinical notes. In this work, we create a python
library for clinical texts, EHRKit. This library contains two main parts:
MIMIC-III-specific functions and tasks specific functions. The first part
introduces a list of interfaces for accessing MIMIC-III NOTEEVENTS data,
including basic search, information retrieval, and information extraction. The
second part integrates many third-party libraries for up to 12 off-shelf NLP
tasks such as named entity recognition, summarization, machine translation,
etc.

##  1 Introduction

With the rising trend of Electronic Health Records (EHRs), massive
unstructured texts (i.e., clinical and admission notes) are being created in
the healthcare system. It is very important to process such data for secondary
usage Xiao et al. (2018). The main obstacle is the processing and
understanding of the unstructured text. Natural Language Processing (NLP)
techniques have been applied to deal with such texts Li et al. (2021b);
Shickel et al. (2018); Al-Aiad et al. (2018). Especially, deep learning-based
methods achieved great success in some existing NLP tasks in the biomedical
and clinical literature, such as text classification Zhou et al. (2021); Li
and Yu (2020); Li et al. (2019); Hughes et al. (2017), named entity
recognition Song et al. (2021), text segmentation Badjatiya et al. (2018),
medical language translation and generation Weng et al. (2019); Abacha and
Demner-Fushman (2019) and many others.

Following the success of BERT Devlin et al. (2019), researchers developed
BERT-based models trained on the clinical literature. BioBERT Lee et al.
(2020) is a representative model that was pretrained on large-scale biomedical
corpora. The evaluation shows that it outperforms the previous state-of-the-
art by a large margin on many domain-specific tasks, including biomedical
named entity recognition, biomedical relation extraction, and biomedical
question answering. Similarly, there are other similar pretrained models like
ClinicalBERTHuang et al. (2019), which is trained on MIMIC-III Johnson et al.
(2016). With such advanced neural models, there is a need for a user-friendly
programming interface that can support a variety of downstream tasks.

There are some existing libraries and toolkits designed for bioinformatical
and clinical needs, including the biomedical and clinical model packages of
Stanza Zhang et al. (2021), SciFive Phan et al. (2021), UmlsBERT Michalopoulos
et al. (2021), MIMIC-Extract Wang et al. (2020) and so on. However, we noticed
that there is a need to integrate more existing libraries with much broader
coverage of clinical and biomedical NLP tasks in our toolkit. Besides, based
on the analysis from Li et al. (2021b), there are limited research on
generation tasks for EHR unstructured text, especially on machine translation.
Thus, in our toolkit, we provide a pretrained model for clinical text machine
translation which supports of 3 languages.

Figure 1: EHRKit Architecture.

Our contributions are: 1) First, we propose EHRKit, a Python NLP toolkit for
EHR unstructured texts. This toolkit contains two main components: general API
functions and MIMIC-specific functions. The toolkit is user-friendly, with
easy installation and quick start tutorials. We also provide detailed use
cases and readme files to help users understand. 2) Second, to fill the gap in
machine translation for clinical texts, we release pretrained models in three
languages, and evaluation shows steady improvement. Besides, we evaluate
existing pretrained models for summarization in a biomedical and clinical
scenario. We release this toolkit and pretrained models publicly available at
https://github.com/Yale-LILY/EHRKit-2022.

##  2 System Design and Architecture

We show our EHRKit architecture in Fig. 1. It consists of two modules, namely
MIMIC-III Tasks and Wrapper Functions.

###  2.1 MIMIC-III Tasks

We include some basic NLP functions for MIMIC-III NOTEEVENTS text data Johnson
et al. (2016), including basic statistical functions, Information Extraction,
Keyword Search, Document Retrieval, Extractive and Abstractive Summarization.
A big advantage of this module is to load the original NOTEEVENTS data (this
is in free text) as a more structured data source.

  * •

Basic statistical functions support counting for number of patients and number
of documents, number of sentences and so on.

  * •

Information Extraction provides helpful interfaces for investigating the data,
i.e., phrases extraction, and abbreviation term extraction from a given record
ID. We applied Phrase-At-Scale111https://github.com/kavgan/phrase-at-scale for
this function.

  * •

Keyword Search allows users to search a record by a keyword.

  * •

Document Retrieval allows users to search a record by ID.

  * •

Extractive and Abstractive Summarization provides two methods for document
summarization: Naïve Bayes Ramanujam and Kaliappan (2016) and DistilBART
Shleifer and Rush (2020).

###  2.2 Wrapper Functions

This module integrates many third-party libraries and supports up to 12
functionalities for any free-text inputs.

  * •

Abbreviation Detection and Expansion: finds abbreviation and its expansions.
Function imported from scispaCy222https://allenai.github.io/scispacy/.

  * •

Sentencizer: Detect sentence boundaries. We support four approaches:
PyRuSH333https://github.com/jianlins/PyRuSH., Stanza, ScispaCy and Stnza
Biomed.

  * •

Hyponym Detection: finds the hyponyms of the recognized entities in the input
text. Function imported from scispaCy.

  * •

Negation Detection: detects negation in a sentence, imported from medspaCy
Eyre et al. (2021a)

  * •

Word Tokenization: tokenizes a sentence into a list of words. Function
imported from medspaCy.

  * •

Named Entity Recognition: finds named entities, part-of-speech and universal
morphological features, and dependencies of an input record. Function imported
from Stanza Zhang et al. (2021).

  * •

Document Clustering: given the query record, selects $k$ documents from
supporting records that are most similar to the main record (K-Means
clustering), measured by embedded document using pretrained BERT model Devlin
et al. (2019).

  * •

UMLS Concept Extraction: matches the UMLS concept for the input text. Function
imported from medspaCy Eyre et al. (2021a).

  * •

Entity Linking: finds named entities, negation entities, and linked entities
in the input text. Function imported from
scispaCy444https://allenai.github.io/scispacy/.

  * •

Section Detection: rule-based method for detecting section (i.e., allergies,
history). Function imported from medspaCy Eyre et al. (2021a).

  * •

Machine Translation: translates English texts into 17 target languages. We
applied the existing MarianMT
model555https://huggingface.co/docs/transformers/model_doc/marian.

  * •

Summarization: we support both extractive and abstractive summarization
methods. We integrated TextRank Mihalcea and Tarau (2004), pretrained BART, T5
and SciFive summarization libraries. We also allow single and multiple
documents as the input.

###  2.3 Other similar libraries

MIMIC-Extract666https://github.com/MLforHealth/MIMIC_ExtractA pipeline for
preprocessing and presenting data from MIMIC-III dataset. It provides several
features for data analysis, including extraction of clinical events like
mortality from free text.

ScispaCy777https://allenai.github.io/scispacy/ Neumann et al. (2019) A tool
that adapts SpaCy’s models to process scientific, biomedical, and clinical
text. It supports multiple models for tokenization, part of speech tagging,
dependency parsing, and named entity recognition.

medspaCy Based on the spaCy framework, medspaCy Eyre et al. (2021b) is a
clinical NLP python library that provides both rule-based and machine
learning-based methods for processing clinical text. It supports methods for
various clinical applications such as UMLS Mapping (rule-based), Section
Detection, Sentence Detection, Contextual Analysis and Visualization on
entities.

| MIMIC Related | Neural Methods | Machine Translation | Summarization |
---|---|---|---|---|---
MIMIC-Extract | ✓ |  |  |  |
ScispaCy |  | ✓ |  |  |
medspaCy |  | ✓ |  |  |
Stanza Biomed |  | ✓ |  |  |
medspaCy |  | ✓ |  |  |
SciFive |  | ✓ |  | ✓ |
EHRKit (ours) | ✓ | ✓ | ✓ | ✓ |
Table 1: A comparison with other similar python toolkit.

Stanza Biomed Zhang et al. (2021) A set of tools developed by Stanford NLP
Group for statistical, neural, and rule-based problems in computational
linguistics. Its software provides a simple, useful interface for NLP tasks
like NER and part-of-speech (POS) tagging. It is a widely used Python library
for processing clinical texts. It provides nearly state-of-the art performance
using neural networks on tasks including tokenization, sentence segmentation,
part of speech (POS) tagging, lemmatization, and dependency parsing.

SciFive Phan et al. (2021) A pretrained T5 language model for biomedical
domain. Fine-tuned on PubMed Abstract 888https://pubmed.ncbi.nlm.nih.gov/ and
PubMed Central (PMC) 999https://www.ncbi.nlm.nih.gov/pmc, it outperformed
similar models including BioBERT and the Base T5 model on multiple NLP tasks:
named entity relation, relation extraction, natural language inference, and
question answering.

Tab. 1 lists our EHRKit and other similar tool-kits. We compare from different
perspectives by focusing on the functionalities. MIMIC Related: if supports
MIMIC-related functions. We consider MIMIC as an essential data source and it
plays an important role in the research field. We can find that only MIMIC-
Extract supports these related functions which users can apply directly on the
MIMIC data. Neural Methods: if this toolkit supports neural methods and
embedding methods. As we can see, the majority contain such feature. Machine
Translation and Summarization: if this toolkit supports generation tasks like
machine translation and summarization. In this case, only SciFive and EHRKit
support such feature. Based on these perspectives, our toolkit provides
diverse functionalities and easy to use.

##  3 Performance Evaluation

###  3.1 Machine Translation

In this section, we report the performance of Machine Translation function
within our EHRKit, and compare this to evaluation results based on a
pretrained model. Our training sets and test sets are obtained from the UFAL
Medical Corpus101010https://ufal.mff.cuni.cz/ufal_medical_corpus, which is a
collection of multilingual parallel corpora. The collected corpora are from
various medical text sources, such as titles of medical Wikipedia articles,
medical term-pairs, patents, documents from the European Medicines Agency
Braune et al. (2018). We evaluate language pairs including English (en) to
Spanish (es), English to French (fr), and English to Romanian (ro), as those
are the three language pairs that are mutually supported by EHRKit and UFAL
corpus.

For data pre-processing, we first exclude general domain data from UFAL, such
as parliament proceedings, news commentaries and web crawls. Next, we random
shuffle the medical-domain corpora and split it into two parts by 85% and 15%,
as our training set and test set, respectively. For each language pair, we use
all of the available parallel data. Tab. 2 summarizes the number of sentences
that we extract from the UFAL corpus.

Lang. Pair | Total | Train | Test
---|---|---|---
en $\rightarrow$ es | 790,915 | 672,276 | 111,779
en$\rightarrow$fr | 2,812,305 | 2,390,458 | 407,388
en$\rightarrow$ ro | 1,165,092 | 990,327 | 161,936
Table 2: Data statistics for machine translation: we apply UFAL and select the
overlapped target language pairs for our experiments.

Subsequently, we perform a baseline analysis of Machine Translation function
within our EHRKit by the industry standard BLEU score Papineni et al. (2002).
Next, we pretrain our model with the training sets and re-calculate the BLEU
scores. As shown in Fig. 2, our translation function improved significantly
after pretraining, with an average 16.80% increase in BLEU score. Among the
three selected language pairs, we can observe that English to French has the
best improvement - it achieves 32.40% performance gain. We conjecture that
this occurs because we have significantly more training data in English to
French.

en-esen-fren-ro$0.2$$0.3$$0.4$$0.5$Average BLEU ScoreBeforeAfter Figure 2: BLEU score: before and after pretraining. | PubMed | MIMIC-CXR
---|---|---
| R-1 | R-2 | R-L | R-1 | R-2 | R-L
Pegasus Zhang et al. (2020) | 45.97 | 20.15 | 28.25 | 65.11 | 52.90 | 61.88
BigBird Zaheer et al. (2020) | 46.32 | 20.65 | 42.33 | 63.85 | 51.09 | 60.55
BART Lewis et al. (2019) | 44.16 | 20.28 | 36.80 | 62.09 | 49.02 | 58.65
SciFive Phan et al. (2021) | 48.83 | 15.81 | 37.06 | 65.17 | 52.45 | 61.80
Table 3: Summarization evaluation: we evaluate selected models and report ROUGE-1, ROUGE-2 and ROUGE-L.  Dataset | Train | Valid | Test
---|---|---|---
PubMed | 112K | 6.6K | 6.7K
MIMIC-CXR | 91,544 | 2000 | 600
Table 4: Data statistics for PubMed and MIMIC-CXR summarization datasets.
Words are counted before tokenization.

###  3.2 Summarization

Since there are many existing pretrained models for summarization in the
general NLP field, we investigate how they perform in the biomedical
literature and clinical data. Summarization corpora from the clinical scenario
are very challenging to be obtained, we chose the existing PubMed Cohan et al.
(2018) and MIMIC-CXR Johnson et al. (2019) as our principal datasets.

PubMed dataset consists of 133k biomedical scientific publications from the
PubMed database. Each input document is a scientific article, and the
reference summary is the associated abstract. MIMIC-CXR is a de-identified,
Protected Health Information removed dataset of chest radiographs, with a
DICOM format and free-text radiology reports. We use a subset from the MIMIC-
CXR Dataset for the MEDIQA 2021 Radiology report summarization shared
task111111https://sites.google.com/view/mediqa2021. Each example contains
three fields: (a) findings field contains the original human-written radiology
findings text, (b) impression field contains the human-written radiology
impression text, and (c) background field contains background information of
the study in text format. We show the statistics in Tab. 4.

We evaluate selected pretrained abstractive methods using ROUGE Lin (2004).
Among the four models, we can observe that SciFive has a high R-1 score, but
BigBird Zaheer et al. (2020) and Pegasus Zhang et al. (2020) achieve a better
score on R-2 and R-L, respectively, on the two datasets. This evaluation shows
that it is challenging to determine which model is the best in our specific
scenario, though SciFive was pretrained for this purpose. In the future, more
work can be done to improve automatic summarization for biomedical and
clinical texts.

##  4 Conclusion

In this work, we propose a python library for clinical texts, EHRKit. This
toolkit contains two main components: general API functions and MIMIC-specific
functions. In the future, we will investigate more EHR-NLP tasks including
machine translation for more languages, multi-document summarization and
question answering Li et al. (2021b). Besides, we plan to investigate better-
performed NLP models for these tasks, for example, BERT-based models Lee et
al. (2020); Li et al. (2021c) and graph-based models Li et al. (2020, 2021d,
2021a).

## References

  * Abacha and Demner-Fushman (2019) Asma Ben Abacha and Dina Demner-Fushman. 2019.  On the summarization of consumer health questions.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers_ , pages 2228–2234. Association for Computational Linguistics.
  * Al-Aiad et al. (2018) Ahmad Al-Aiad, Rehab Duwairi, and Manar Fraihat. 2018.  Survey: Deep learning concepts and techniques for electronic health record.  In _15th IEEE/ACS International Conference on Computer Systems and Applications, AICCSA 2018, Aqaba, Jordan, October 28 - Nov. 1, 2018_ , pages 1–5. IEEE Computer Society.
  * Badjatiya et al. (2018) Pinkesh Badjatiya, Litton J. Kurisinkel, Manish Gupta, and Vasudeva Varma. 2018\.  Attention-based neural text segmentation.  In _Advances in Information Retrieval - 40th European Conference on IR Research, ECIR 2018, Grenoble, France, March 26-29, 2018, Proceedings_ , volume 10772 of _Lecture Notes in Computer Science_ , pages 180–193. Springer.
  * Braune et al. (2018) Fabienne Braune, Alex. Fraser, and Barry Haddow. 2018.  D1.2: Report on improving translation with monolingual data.
  * Cohan et al. (2018) Arman Cohan, Franck Dernoncourt, Doo Soon Kim, Trung Bui, Seokhwan Kim, Walter Chang, and Nazli Goharian. 2018.  A discourse-aware attention model for abstractive summarization of long documents.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 615–621, New Orleans, Louisiana. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Eyre et al. (2021a) Hannah Eyre, Alec B Chapman, Kelly S Peterson, Jianlin Shi, Patrick R Alba, Makoto M Jones, Tamara L Box, Scott L DuVall, and Olga V Patterson. 2021a.  Launching into clinical space with medspacy: a new clinical text processing toolkit in python.  In _AMIA Annual Symposium Proceedings 2021_.
  * Eyre et al. (2021b) Hannah Eyre, Alec B Chapman, Kelly S Peterson, Jianlin Shi, Patrick R Alba, Makoto M Jones, Tamara L Box, Scott L DuVall, and Olga V Patterson. 2021b.  Launching into clinical space with medspacy: a new clinical text processing toolkit in python.  _arXiv preprint arXiv:2106.07799_.
  * Huang et al. (2019) Kexin Huang, Jaan Altosaar, and Rajesh Ranganath. 2019.  Clinicalbert: Modeling clinical notes and predicting hospital readmission.  _arXiv:1904.05342_.
  * Hughes et al. (2017) Mark Hughes, Irene Li, Spyros Kotoulas, and Toyotaro Suzumura. 2017.  Medical text classification using convolutional neural networks.  _CoRR_ , abs/1704.06841.
  * Johnson et al. (2019) AEWP Johnson, Tom Pollard, Roger Mark, Seth Berkowitz, and Steven Horng. 2019.  Mimic-cxr database.  _PhysioNet10_ , 13026:C2JT1Q.
  * Johnson et al. (2016) Alistair EW Johnson, Tom J Pollard, Lu Shen, H Lehman Li-Wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. 2016.  Mimic-iii, a freely accessible critical care database.  _Scientific data_ , 3(1):1–9.
  * Lee et al. (2020) Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang. 2020.  Biobert: a pre-trained biomedical language representation model for biomedical text mining.  _Bioinform._ , 36(4):1234–1240.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Li and Yu (2020) Fei Li and Hong Yu. 2020.  ICD coding from clinical text using multi-filter residual convolutional neural network.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 8180–8187. AAAI Press.
  * Li et al. (2020) Irene Li, Alexander Fabbri, Swapnil Hingmire, and Dragomir Radev. 2020.  R-vgae: Relational-variational graph autoencoder for unsupervised prerequisite chain learning.  _arXiv preprint arXiv:2004.10610_.
  * Li et al. (2021a) Irene Li, Tianxiao Li, Yixin Li, Ruihai Dong, and Toyotaro Suzumura. 2021a.  Heterogeneous graph neural networks for multi-label text classification.  _arXiv preprint arXiv:2103.14620_.
  * Li et al. (2021b) Irene Li, Jessica Pan, Jeremy Goldwasser, Neha Verma, Wai Pan Wong, Muhammed Yavuz Nuzumlali, Benjamin Rosand, Yixin Li, Matthew Zhang, David Chang, Richard Andrew Taylor, Harlan M. Krumholz, and Dragomir R. Radev. 2021b.  Neural natural language processing for unstructured data in electronic health records: a review.  _CoRR_ , abs/2107.02975.
  * Li et al. (2021c) Irene Li, Prithviraj Sen, Huaiyu Zhu, Yunyao Li, and Dragomir Radev. 2021c.  Improving cross-lingual text classification with zero-shot instance-weighting.  In _Proceedings of the 6th Workshop on Representation Learning for NLP (RepL4NLP-2021)_ , pages 1–7.
  * Li et al. (2021d) Irene Li, Vanessa Yan, and Dragomir Radev. 2021d.  Efficient variational graph autoencoders for unsupervised cross-domain prerequisite chains.  _arXiv preprint arXiv:2109.08722_.
  * Li et al. (2019) Irene Li, Michihiro Yasunaga, Muhammed Yavuz Nuzumlali, Cesar Caraballo, Shiwani Mahajan, Harlan M. Krumholz, and Dragomir R. Radev. 2019.  A neural topic-attention model for medical term abbreviation disambiguation.  _CoRR_ , abs/1910.14076.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81.
  * Michalopoulos et al. (2021) George Michalopoulos, Yuanxin Wang, Hussam Kaka, Helen H. Chen, and Alexander Wong. 2021.  Umlsbert: Clinical domain knowledge augmentation of contextual embeddings using the unified medical language system metathesaurus.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021_ , pages 1744–1753. Association for Computational Linguistics.
  * Mihalcea and Tarau (2004) Rada Mihalcea and Paul Tarau. 2004.  Textrank: Bringing order into text.  In _Proceedings of the 2004 conference on empirical methods in natural language processing_ , pages 404–411.
  * Neumann et al. (2019) Mark Neumann, Daniel King, Iz Beltagy, and Waleed Ammar. 2019.  ScispaCy: Fast and Robust Models for Biomedical Natural Language Processing.  In _Proceedings of the 18th BioNLP Workshop and Shared Task_ , pages 319–327, Florence, Italy. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  BLEU: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL)_ , pages 311–318, Philadelphia. Association for Computational Linguistics.
  * Phan et al. (2021) Long N Phan, James T Anibal, Hieu Tran, Shaurya Chanana, Erol Bahadroglu, Alec Peltekian, and Grégoire Altan-Bonnet. 2021.  Scifive: a text-to-text transformer model for biomedical literature.  _arXiv preprint arXiv:2106.03598_.
  * Ramanujam and Kaliappan (2016) Nedunchelian Ramanujam and Manivannan Kaliappan. 2016.  An automatic multidocument text summarization approach based on naive bayesian classifier using timestamp strategy.  _The Scientific World Journal_ , 2016.
  * Shickel et al. (2018) Benjamin Shickel, Patrick J. Tighe, Azra Bihorac, and Parisa Rashidi. 2018.  Deep EHR: A survey of recent advances in deep learning techniques for electronic health record (EHR) analysis.  _IEEE J. Biomed. Health Informatics_ , 22(5):1589–1604.
  * Shleifer and Rush (2020) Sam Shleifer and Alexander M. Rush. 2020.  Pre-trained summarization distillation.  _CoRR_ , abs/2010.13002.
  * Song et al. (2021) Bosheng Song, Fen Li, Yuansheng Liu, and Xiangxiang Zeng. 2021.  Deep learning methods for biomedical named entity recognition: a survey and qualitative comparison.  _Briefings Bioinform._ , 22(6).
  * Wang et al. (2020) Shirly Wang, Matthew BA McDermott, Geeticka Chauhan, Marzyeh Ghassemi, Michael C Hughes, and Tristan Naumann. 2020.  Mimic-extract: A data extraction, preprocessing, and representation pipeline for mimic-iii.  In _Proceedings of the ACM conference on health, inference, and learning_ , pages 222–235.
  * Weng et al. (2019) Wei-Hung Weng, Yu-An Chung, and Peter Szolovits. 2019.  Unsupervised clinical language translation.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019_, pages 3121–3131. ACM.
  * Xiao et al. (2018) Cao Xiao, Edward Choi, and Jimeng Sun. 2018.  Opportunities and challenges in developing deep learning models using electronic health records data: a systematic review.  _J. Am. Medical Informatics Assoc._ , 25(10):1419–1428.
  * Zaheer et al. (2020) Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. 2020.  Big bird: Transformers for longer sequences.  _Advances in Neural Information Processing Systems_ , 33:17283–17297.
  * Zhang et al. (2020) Jingqing Zhang, Yao Zhao, Mohammad Saleh, and Peter Liu. 2020.  Pegasus: Pre-training with extracted gap-sentences for abstractive summarization.  In _International Conference on Machine Learning_ , pages 11328–11339. PMLR.
  * Zhang et al. (2021) Yuhao Zhang, Yuhui Zhang, Peng Qi, Christopher D Manning, and Curtis P Langlotz. 2021.  Biomedical and clinical english model packages for the stanza python nlp library.  _Journal of the American Medical Informatics Association_ , 28(9):1892–1899.
  * Zhou et al. (2021) Tong Zhou, Pengfei Cao, Yubo Chen, Kang Liu, Jun Zhao, Kun Niu, Weifeng Chong, and Shengping Liu. 2021.  Automatic ICD coding via interactive shared representation networks with self-distillation mechanism.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , pages 5948–5957. Association for Computational Linguistics.


# EFFGAN: Ensembles of fine-tuned federated GANs

1st Ebba Ekblom  RISE Research Institutes of Sweden
<EMAIL_ADDRESS>2nd Edvin Listo Zec  RISE Research Institutes of Sweden
<EMAIL_ADDRESS>3rd Olof Mogren  RISE Research Institutes of Sweden
<EMAIL_ADDRESS>
###### Abstract

Decentralized machine learning tackles the problem of learning useful models
when data is distributed among several clients. The most prevalent
decentralized setting today is federated learning (FL), where a central server
orchestrates the learning among clients. In this work, we contribute to the
relatively understudied sub-field of generative modelling in the FL framework.

We study the task of how to train generative adversarial networks (GANs) when
training data is heterogeneously distributed (non-iid) over clients and cannot
be shared. Our objective is to train a generator that is able to sample from
the collective data distribution centrally, while the client data never leaves
the clients and user privacy is respected. We show using standard benchmark
image datasets that existing approaches fail in this setting, experiencing so-
called client drift when the local number of epochs becomes to large and local
parameters drift too far away in parameter space. To tackle this challenge, we
propose a novel approach named EFFGAN: Ensembles of fine-tuned federated GANs.
Being an ensemble of local expert generators, EFFGAN is able to learn the data
distribution over all clients and mitigate client drift. It is able to train
with a large number of local epochs, making it more communication efficient
than previous works.

###### Index Terms:

generative adversarial networks, federated learning

Figure 1: Schematic of the EFFGAN training protocol. The solution leverages
the combination of federated learning with local fine-tuning and ensembling to
produce a generative model trained on decentralized private data.

##  I Introduction

Phones and tablets have increasingly been getting more powerful in the last
decades. Today, they carry strong sensors such as cameras, microphones and
GPS. People around the world frequently carry these devices wherever they go,
and as such, these devices contain a lot of data. This data, due to the nature
of how it is collected, is very private and cannot be shared or collected
centrally. Meanwhile, it still could be leveraged and greatly improve user
applications. It is in this setting that federated learning [1] has become a
paradigm shift for distributed machine learning. Federated learning is a
framework for machine learning using decentralized data, allowing the training
data to remain at the clients. Yet the data from many clients can be used in
training the resulting machine learning model. Since federated averaging
(FedAvg) was introduced in [1], the amount of research on it has increased at
a fast pace. Problems such as heterogeneous client data, heterogeneous
systems, privacy, fairness and many more are active research areas. At the
same time, most of the current work focuses on mainly on supervised tasks,
such as classification. Much less has been done in the realm of self-
supervised and unsupervised learning [2].

In this work, we study unsupervised learning in the form of generative
adversarial networks (GANs) [3] in a distributed setting. We investigate the
application of federated learning to GANs, and conclude that while existing
federated learning strategies for them work well when training data is
identically and independently distributed (iid), they fail to produce robust
models when training data is heterogeneous (non-iid).

GANs are unsupervised generative models where two neural networks, a generator
and a discriminator, compete in a two-player minimax game. They were proposed
as a powerful approach to modelling complex and high-dimensional data
distributions. Since the inception of GANs, a number of issues have been
identified and addressed leading to more recent versions which suffer less
from problems such as mode collapse, convergence failure, and instability
during training. However, the decentralized setting of GANs, where data is
distributed among a number of clients, has received much less attention in the
literature. A decentralized GAN would allow for more powerful generative
models trained on data from devices such as smartphones and tablets while at
the same time respecting the privacy of users’ data, as it does not need to be
collected centrally. Meanwhile, training these models decentralized brings
forth a lot of challenges. GANs are usually data-hungry, requiring a lot of
data to perform well. Even when data is sufficient, instability issues are
frequent even in central training. Further, data collected in the real world
using devices such as phones and tablets is naturally non-iid. Label
distribution skew and covariate shift are common distributional shifts that
need to be addressed.

Therefore, in this paper, we investigate the question of how to learn a data
distribution over decentralized data in a non-iid setting. We provide an
experimental evaluation where data from standard benchmark datasets (MNIST and
FashionMNIST) are heterogeneously distributed over a set of clients, where
certain classes of objects occur only on subsets of the clients. Finally, we
propose a novel solution for distributed training of generative adversarial
networks in the setting of heterogeneous data. In this setting, training local
models on each client results in models that overfit to the local datasets,
and a model trained using vanilla federated learning (FedGAN [4]) on the same
data results in an aggregate model which fails to produce convincing samples
due to a too large number of local epochs, i.e. client drift. Our proposed
solution, EFFGAN: Ensembles of fine-tuned federated GANs mitigates both
issues. By building an ensemble of fine-tuned generators it provides results
that outperform previous works. We find that EFFGAN robustly handles
heterogeneous data settings and requires substantially less communication
compared to the baseline.

In summary, our main contributions are

  1. 1.

We scale up previous work, and increase the number of clients from 5 to 100.

  2. 2.

We show that distributed GAN training in non-iid data settings suffers from
client drift, i.e. the parameters of the locally trained models drift apart,
resulting in a bad aggregated global model.

  3. 3.

We show that FedAvg possesses good transfer learning capabilities in the GAN
setting, even though it suffers from client drift.

  4. 4.

Using these insights, we propose EFFGAN, an ensemble that consists of fine-
tuned generators trained from FedAvg which mitigates client drift and achieves
better FID score as compared to previous works in non-iid data settings.

Our goal is to learn a model that can be used centrally to generate as real
data as possible. Thus, the final model will be used at the server and not at
the clients (which is typically the goal in FL). This is useful for
organizations such as hospitals and financial institutions, where acquiring
data can be time-consuming and expensive, and where sharing data is hard or
prohibited. A generative model which can be sampled from can thus facilitate
many such problems.

##  II Related work

The work in this paper is related to federated learning, generative
adversarial networks and ensemble models. Federated learning was proposed for
communication efficient distributed learning [1]. The algorithm, called
federated averaging, runs parallel stochastic gradient descent for a number of
communication rounds on a subset of all the clients. After each round, the
updated client models are sent to a central server where they are averaged and
communicated back. Most work on federated learning has been focused on the
supervised setting where clients have labeled data [2].

Federated GANs. Up until recently, semi-supervised and unsupervised methods
have been lacking in the federated learning literature. We contribute to this
area of research in this work by studying GANs [3] in a distributed setup,
which are trained unsupervised without any need of labels.

For iid data settings, MD-GAN [5] is a solution based on a single generator at
the server with distributed discriminators. The generator communicates
generated data to all participating clients, which is a communication-
intensive operation and not scalable to many clients.

Non-iid data is tackled in [6], where the discriminators are distributed and
the server keeps a central generator, just as for MD-GAN. Here, the generator
is updated using the most forgiving discriminator (i.e. the largest loss).
Augenstein et al. [7] propose a similar federated GAN, with only one central
generator and several distributed discriminators. The difference is that the
discriminator update is based on selecting a subset of clients. Both these
works suffer from large communication overhead, as the central generator needs
to send data to each participating client each communication round.

FedGAN [4] is a GAN trained across distributed clients with non-iid data. The
generator in FedGAN does not provide the same bottleneck effect, as each
client has its own local generator and discriminator which are updated with
federated averaging through the central server. FeGAN [8] is a similar
solution, which also uses federated averaging on the generator and the
discriminator. Here, the authors however aggregate models using Kullback-
Leibler weighting, which uses a softmax on the KL divergence score of each
client. Each model $w_{k}$ from client $k$ is assigned a weight

$\alpha_{k}=\frac{e^{-s_{k}}}{\sum_{i}e^{-s_{i}}},$ (1)

where $s_{k}$ is the pre-computed KL score of client $k$. FeGAN further
utilizes balanced sampling every communication round, i.e. sampling clients
with balanced datasets and more samples. However, this breaks some privacy
concerns as clients need to disclose information about their data
distributions to the central server.

Gossip GAN [9] is a completely decentralized approach, where there is no
central server available and where the clients communicate in a peer-to-peer
network.

Ensembles of deep nets. Ensembles of deep neural networks have been studied in
a non-federated setup. Deep ensembles were introduced by [10], where an
ensemble of deep neural networks is trained by randomly initializing a number
of different models. In [11], the authors demonstrate the stability and
diversity of randomly initialized models. In [12], the authors propose an
(non-distributed) ensemble of GANs with different initializations to learn a
distribution over images. MAD-GAN [13] is another solution that tackles mode-
collapse, where several generators are trained together with a multi-class
discriminator.

Inspired by these previous works, in this paper we propose to build an
ensemble of fine-tuned federated generators, illustrated in figure 1. We
emphasize that our goal is to learn to generate realistic data at the central
server, and not at the clients. Thus, our method is communication efficient
and does not require more computational power from the clients, as the full
ensemble is never sent out to the clients. Our proposed solution is robust
with respect to mode collapse, client drift and heterogeneous data. In the
work of FedGAN [4], the authors only considered $5$ clients in their
experiments. In this work, we scale this up and show that our solution works
for 100 participating clients.

##  III Method

In GAN training, two neural networks compete in a two-player minimax game. The
goal of the generator $G(z;\theta_{g})$ is to learn a distribution $p_{g}(x)$
over data $x$, by mapping input noise $z\sim p_{z}(z)$ to real samples $x$.
Meanwhile, the discriminator $D(x;\theta_{D})$ is trained to discriminate
between real samples $x$ and generated samples $G(z)$. The optimization
problem can thus be formulated as

$\min_{G}\max_{D}\mathbb{E}_{x\sim p_{\text{data}}(x)}[\log
D(x)]+\mathbb{E}_{z\sim p_{z}(z)}[\log(1-D(G(z)))].$ (2)

In federated learning, the data on the clients is considered sensitive and
cannot be shared. Instead, a central server orchestrates the learning among
clients by sending out a copy of a global model that is trained on each
client’s data. The new, updated models are then sent back to the central
server where they are aggregated into a new global model. This procedure is
repeated for a number of communication rounds until some stopping criteria is
met. Let $K$ be the number of clients, $w$ the global model parameters, $x$ a
data sample, $p_{k}$ the local data distribution for client $k$ and $\ell_{k}$
the loss function for client $k$. The optimization problem can then be
described as

$\min_{w\in\mathbb{R}^{d}}\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}_{x\sim
p_{k}}\left[\ell_{k}(w;\;x)\right].$ (3)

As a baseline, we compare our method to FedGAN [4]. For FedGAN, the generator
and discriminator are locally trained for a number of local epochs, optimizing
equation (2). Then, equation (3) is optimized using FedAvg, both for $G$ and
$D$. That is, every local discriminator and generator is trained using SGD on
the local datasets, and then every communication round the parameters are
averaged to produce global models.

###  III-A EFFGAN: Ensembles of fine-tuned federated GANs

In this work, we instead propose to build an ensemble of client generators
$G_{m}$ for $m=1,2,\dots,M$ in order to learn the data distribution over all
clients, where $M\leq K$. The ensemble thus consists of $M$ locally fine-tuned
local models of the last achieved global generator using FedAvg. More
specifically, after FedAvg has finished, fine-tuning on the local clients is
done. Then, the $M$ number of fine-tuned generators are sent to the central
server, and the data generation process is performed using all $M$ generators.
Since the generation of the data happens at the central server, no extra
computation is needed at the clients. An illustration of EFFGAN is shown in
figure 1. In summary our proposed method works as follows.

  1. 1.

Train a global generator using FedAvg (as in FedGAN).

  2. 2.

Fine-tune the global model achieved from 1) on $M$ randomly selected clients
for $E$ number of epochs and send them back to the central server.

  3. 3.

At the server, sample a fine-tuned generator $G_{m}$: $m\sim\mathcal{U}(0,M)$.

  4. 4.

Sample a data point $x$ from generator $G_{m}$: $x\sim p^{m}_{g}(x)$.

  5. 5.

Repeat 3-4 until sufficient data has been generated.

In our experimental setup, we will investigate how the number of fine-tuned
generators $M$ affect the performance of EFFGAN, see figure 9.

###  III-B Note on privacy

As for most federated learning methods, our proposed EFFGAN requires model
information to be sent from clients to the central server during training.
This is a potential privacy risk, as recent work has shown that it is possible
to reconstruct training data using gradients [14]. Meanwhile, EFFGAN can be
combined with existing works such as differential privacy [15], in order to
achieve stronger privacy for the clients. This is an interesting field of
research but out of scope of this paper, and we leave further studies of this
topic for future work.

##  IV Experimental setup

All experiments were carried out using the DCGAN architecture [16] trained on
the FashionMNIST dataset [17] and the MNIST dataset [18]. Meanwhile, we
believe our framework is compatible with any type of GAN. DCGAN is a GAN
architecture that consists of convolutional layers in the generator and
convolutional-transpose layers in the discriminator. The input to the
generator is a latent vector that is sampled from the standard normal
distribution $z\sim\mathcal{N}(0,1)$. The DCGAN architecture was chosen for
its simplicity and because it is used widely in the literature. While there
today exist GANs that perform better for more complex datasets, DCGAN has
sufficient capacity for the purposes of this work.

FashionMNIST contains 70,000 28x28 gray-scale images of Zalando clothing in 10
classes. It is split into 60,000 training images and 10 000 test images. MNIST
contains 70,000 28x28 gray-scale images of handwritten digits, and it is also
split into 60,000 training samples and 10,000 test samples.

In experimental setup of this paper, we study three main problems:
heterogeneous data, client drift, and how the number of fine-tuned generators
affect the ensemble performance. In order to study non-iid data, each client
is assigned the same number of data points from $n$ distinct classes out of
ten existing ones in the dataset. We perform experiments for varying $n$,
comparing our method to the baseline. We also perform experiments varying the
local number of epochs $E$ to study the effect of client drift in the non-iid
setting of $n=2$. Lastly, we run experiments to investigate how sensitive
EFFGAN is to the number of fine-tuned client generators $M$ that make up the
ensemble.

In the beginning of each communication round, each client receives a copy of
the generator ($G$) and the discriminator ($D$). Both $G$ and $D$ are then
trained locally for $E$ local epochs, after which all local networks are
aggregated using FedAvg. The models are trained using the Adam optimizer [19],
with a learning rate of $\eta=0.001$ and $\beta_{1}=0.0$, $\beta_{2}=0.9$. For
the previous work of FedGAN [4], the authors considered $K=5$ clients in their
experiments. We scale up the experiments to $K=100$ clients and distribute
$600$ samples for each client. A common way to increase efficiency in
federated learning is to randomly sample a fraction $c$ of all clients in each
communication round. However, using too few clients poses the risk of loss of
performance. We thus perform experiments investigating how this fraction
affects the performance of our method and compare it with the baseline.

Evaluation. We use the Fréchet Inception Distance (FID) [20, 21] as our
measure of performance, which compares the distribution of generated samples
with the distribution of real ones that were used to train $G$. For FedGAN,
the FID is computed after aggregation of the local models each communication
round. The performance of EFFGAN is measured after the local fine-tuning, and
the FID is based on data generated from the $M$ number of client generators.

Baselines. In our experiments, we compare EFFGAN to two main baselines. The
first baseline is the aforementioned FedGAN [4]. Since EFFGAN consists of
locally fine-tuned generators, the second baseline we compare with is an
ensemble of locally trained generators, which did not participate in federated
learning. We can thus study to what extent FedAvg facilitates the training of
the fine-tuned generators.

(a) FedGAN

(b) EFFGAN

Figure 2: Images generated by (a) FedGAN [4] and (b) our EFFGAN trained on the
MNIST dataset. The rows correspond to models trained with local epochs
$E=1,5,10$ (top to bottom).

(a) FedGAN

(b) EFFGAN

Figure 3: Images generated by (a) FedGAN [4] and (b) our EFFGAN trained on the
FashionMNIST dataset. The rows corresponds to models trained with local epochs
$E=1,5,10,20,50$ (top to bottom).

##  V Results

In this section we present the results of our work according to the
experimental setup.

###  V-A Qualitative results

Figure 2 shows images generated by FedGAN and EFFGAN side by side, both
approaches trained on MNIST for a varying number of local epochs. For both
models, we save the best performing model with respect to FID over all
communication rounds, and use that as our final model to generate data. We can
see that both solutions manage to solve the task well, and generate plausible
handwritten digits up to $E=5$ local epochs. For FedGAN, the generated images
for $E=10$ are somewhat unclear and smudged, indicating problems of client
drift.

Figure 3 similarly shows images generated by FedGAN and EFFGAN side by side,
using FashionMNIST for training. Here, the difference between the two methods
becomes more clear. While FedGAN generates images that are blurred and grey
with limited variability as the number of local epochs increases, EFFGAN
consistently outputs images that are clear and with good variability. We note
that EFFGAN is more robust to a larger number of local epochs, generating more
realistic images up to $E=50$. This makes EFFGAN more communication efficient
than FedGAN, as it can generate the same (or better) images with less
communication.

###  V-B Non-iid data

Figure 5 shows a comparison of FID scores on FashionMNIST for the FedGAN
baseline (blue), our proposed ensemble of fine-tuned client models: EFFGAN
(red), and an ensemble of client models trained locally without any federated
learning (orange). All clients only have $n=2$ distinct classes in their
datasets, making the problem non-iid. These are also benchmarked against the
lowest FID reached by a centrally trained model, i.e. a model with access to
the entire dataset. In this experiment, EFFGAN is an ensemble of 20 randomly
chosen client generators. The results demonstrate that by using an ensemble of
fine-tuned generators to generate data we reach a better FID as compared to
both FedGAN and an ensemble of locally trained generators, almost reaching the
performance of a centrally trained GAN. Note that a centrally trained GAN has
access to all data and does not solve the distributed learning problem. These
results suggest that using a generator trained with FedAvg serves as a good
initialization for learning the local client data distributions since EFFGAN
outperforms an ensemble of local models trained without communication.

Figure 4: FID for EFFGAN (solid) and FedGAN (dashed) for different number of
local epochs ($E$), trained on the FashionMNIST dataset. Here it is clearly
shown that FedGAN experiences client drift as $E$ increases, whereas EFFGAN is
mitigates this problem. Figure 5: FID scores of different federated GAN
architectures during training. Figure 6: FID for varying heterogeneity, by
varying the number of classes $n$ present in the local client datasets (higher
$n\rightarrow$ more iid). Dataset: MNIST. Figure 7: FID for EFFGAN (solid) and
FedGAN (dashed line) for different number of local epochs ($E$), trained on
the MNIST dataset.

Figure 6 shows the advantage of using the ensemble with a varying degree of
data heterogeneity, and especially so when the data distribution is highly
non-iid. For this experiment, each client has at most $n$ data classes present
in its local dataset, for $n=1,2,\dots,10$. For lower values of $n$, there is
a major difference between the aggregated FedGAN and our proposed ensemble
EFFGAN. As expected, this gap closes as the data distribution goes towards an
iid data distribution. Most notably, EFFGAN is not affected by the data
heterogeneity at all, and even performs on par with a centrally trained model
when each client dataset only has samples from $n=1$ label. This behaviour
ought to be affected by the number of clients in the ensemble. As there are 10
classes in total in the dataset, and this experiment is performed with 20
clients in the ensemble, then we expect all classes to be represented by the
ensemble even when there is only one class of data in the local datasets. That
is, assuming that the local generators diverge to generate data based on the
local datasets, despite the occasional aggregation during training.

TABLE I: The best FID score achieved by EFFGAN and FedGAN for different number of local epochs. | FID
---|---
# local epochs $E$ | EFFGAN | FedGAN
1 | 19.8 | 20.4
5 | 18.7 | 42.1
10 | 19.9 | 53.3
20 | 21.7 | 64.7
50 | 22.0 | 72.1

###  V-C Client drift

FedAvg is known to become detrimental when client data is distributed non-iid
due to local models drifting far away from each other in parameter space when
training is performed with too man local epochs. This phenomenon is known as
client drift [1, 22].

To study the stability of our method, we investigate the performance with
respect to the number of local epochs $E$ each client performs every
communication round. In figure 7 we observe results from this experiment for
the non-iid data setting for the MNIST dataset, where each client dataset only
contains $n=2$ classes. The performance of the FedGAN baseline is represented
by the dashed lines, and the ensemble of fine-tuned models (EFFGAN) is
represented by solid lines. Even though both FedGAN and EFFGAN seem to reach
similar scores for low values of $E$, we see that an increase in $E$ leads to
faster convergence for EFFGAN. Furthermore, when the number of local epochs
increases to $E=10$ FedGAN starts to diverge, while EFFGAN remains stable.

In figure 4 we see the same experiment performed for FashionMNIST. We note
that for increasing $E$ here, FedGAN (dashed) performs much worse,
experiencing client drift where the clients converge to different solutions in
parameter space due to the heterogeneous data. This breaks FedAvg, resulting
in performance degeneration. On the contrary, EFFGAN converges faster in terms
of communication rounds towards the performance of a central GAN with an
increase of $E$. More notably, it does not suffer from client drift, which is
presented as solid lines in figure 4.

Figure 8: Varying number of clients sampled in each communication round, for
the non-iid setting of $n=2$ classes in each client dataset. Figure 9: FID
score vs the number of fine-tuned client generators that make up the ensemble
in EFFGAN, in the non-iid data setting of $n=2$ classes in each client
dataset.

This is further presented in table I, where we report the best FID score
reached by each algorithm, for a different number of local epochs. We observe
here that EFFGAN reaches a better FID score as compared to FedGAN in all
experiments.

In figure 8 the lowest FID is recorded for a varying number of clients used in
communication. Here, FedGAN tends to be lower for a larger amount of clients
in communication. Meanwhile, the FID of the ensemble is stable and works well
even when a small number of clients participate in each communication round.
This means that less communication is needed for training EFFGAN as compared
to FedGAN.

###  V-D Effect of the number of models in ensemble

Despite having a fixed fraction of clients taking part in each communication
round, we can still fine-tune all clients in the last round without reducing
the efficiency of the algorithm much. However, an ensemble consisting of quite
a few models may be unpractical and computationally unnecessary. Figure 9
shows how the FID score on FashionMNIST is affected by the number of client
generators that make up the ensemble. We see that the FID score decreases fast
in the beginning, and there is a lot to gain from adding more generators to
the ensemble. However, after the ensemble consists of $10$ generators,
diminishing returns is experienced. EFFGAN can thus efficiently learn the data
distribution without using a large number of client models.

##  VI Discussion

Client drift. A main finding in our paper is that FedGAN is sensitive to the
number of local epochs used to train the generator and discriminator. This is
presented in figure 4, where we see that FedGAN (dashed) diverges as $E$
increases, i.e. suffering from client drift. This is especially observed for
the FashionMNIST dataset, which is a harder dataset distribution to learn as
compared to MNIST. Meanwhile, our proposed method EFFGAN outperforms FedGAN in
this regard and is especially able to perform well even when the number of
local epochs is large. Whereas FedGAN suffers from client drift for large $E$,
EFFGAN does not, and in our experiments, it can handle up to $50$ local epochs
during training. The reason for this is that all fine-tuned members of the
ensemble have learnt their own respective data distribution well, so as long
as a sufficient number of clients participate in the ensemble, EFFGAN learns
to model the whole data distribution. This also makes EFFGAN more
communication efficient, as it does not need to communicate with the central
server as often. Figure 9 also shows that we do not need a high percentage of
clients to build the ensemble.

For MNIST, both FedGAN and EFFGAN can successfully solve the problem and
generate convincing synthetic samples. However, when increasing the number of
local epochs, EFFGAN converges faster as seen in figure 7, and we conclude
that EFFGAN requires substantially less communication. FedGAN does start to
drift for $E=10$, which is avoided for EFFGAN.

Qualitative evaluation. In figure 2 and figure 3, we can see by visual
inspection that both FedGAN and EFFGAN manage to generate good samples on the
simple MNIST dataset, and generate plausible handwritten digits for up to 5
local epochs. For a larger number of local epochs, the output starts to
produce images that are less clear. In these figures it becomes evident that
FedGAN does not handle the more complex FashionMNIST dataset well, producing
increasingly grey and blurred images with low variability as the number of
local epochs grows. EFFGAN on the other hand, produces convincing images for
all explored numbers of local epochs, for both datasets. This indicates that
the client drift that occurs in FedGAN, and which hinders the aggregation from
producing a meaningful and expressive resulting model, does not occur in
EFFGAN. We observe that MNIST is a simpler problem, and that FedGAN is capable
of solving it with a sufficient amount of communication (local epochs at most
5). Meanwhile, EFFGAN handles both datasets quite well, regardless of the
number of local epochs; thus EFFGAN requires substantially less communication
overhead in comparison. Analogously, in figure 7 we can see that both
approaches reach a similar FID score for MNIST after training for $E=1$ and
$E=5$, although as the number of local epochs increases, EFFGAN increasingly
starts to converge at fewer communication rounds. For $E=10$ local epochs we
start to observe client drift for FedGAN, whereas EFFGAN mitigates this.
Similar patterns can be seen in figure 4 for FashionMNIST. Here it becomes
clear that FedGAN suffers from client drift when the number of local epochs is
greater than 1. This further strengthens the conclusion that EFFGAN is less
sensitive to the number of local epochs, and that it can perform well with
less communication.

Heterogeneous data. In figure 6, EFFGAN is compared to FedGAN in the highly
non-iid setting where each client only has $n$ classes present in its dataset,
for varying $n$. We see that FedGAN performs quite well for $n>2$, where data
is not that heterogeneous, even beating a central GAN. This can seem counter-
intuitive, but is consistent with numbers from previous work, as reported from
[8]. This stems from the fact that the aggregate global generator is based on
more data samples (the clients) as compared to the central model. This is a
great advantage of distributed training, enhancing the learning procedure by
using more diverse updates as compared to central training.

Meanwhile, EFFGAN is robust with respect to $n$, and outperforms FedGAN in the
non-iid setting where $n<3$. Even in the case of $n=1$, i.e. when there is
only one class out of ten in each client data set, EFFGAN manages to perform
on par with a centrally trained GAN. EFFGAN is also less prone to mode
collapse, i.e. only generating samples from certain modes in the data. This is
due to the ensemble consisting of several fine-tuned models, each expert on
their own local data distribution.

Number of generators in ensemble. In figure 9, we show how FID score changes
as a function of the number of generators in the ensemble for the non-iid
setting of $n=2$. Using very few fine-tuned generators will not be enough to
capture the whole data distribution, as each generator is fine-tuned on its
own local data. However, by only randomly sampling $10$ out of $100$ clients,
FID is improved a lot. The ensemble is robust to increasing the number of
generators, however diminishing returns of FID is experienced when adding many
more.

Transfer learning. In figure 5 we note that EFFGAN outperforms both FedGAN and
an ensemble of locally trained generators (with no communication). This result
indicates that the generator in FedGAN achieved from FedAvg serves as a good
initialization for transfer learning, as this is what is fine-tuned for every
ensemble member in EFFGAN. This even holds true if FedGAN starts to degenerate
due to client drift.

##  VII Conclusions

In this work, we have proposed a novel method for learning a data distribution
over decentralized client data using an ensemble of fine-tuned federated GANs
which we name EFFGAN. Our main results show that using standard FedAvg for
training GANs works when data is iid, but suffers from client drift when data
is non-iid. Our EFFGAN mitigates this problem by generating data from an
ensemble of locally fine-tuned generators. First, we show in our experiments
that client drift can be avoided in this way, which enables training for a
large number of local epochs. This makes the proposed method communication-
efficient, as we do not need to communicate with a central server often.
Secondly, as long as we have a sufficient number of client generators as a
part of the ensemble we are able to learn the full data distribution and
achieve a FID score close to a centrally trained model even in a pathological
non-iid data setting. Lastly, although FedGAN diverges in the non-iid setting
when trained for several local epochs, we conclude that FedAvg has good
transfer learning capabilities as this enables the local generators to fine-
tune and learn the local data distributions better as compared to random
initialization and no communication.

In this work, we experimented with non-iid data in the form of label
distribution skew. For future work, it would be interesting to research other
types of heterogeneity as well, such as covariate shift and concept shift.
Studies investigating how the number of data samples per client dataset effect
the generated images also serve as interesting future experiments.

## Acknowledgment

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [2] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _arXiv preprint arXiv:1912.04977_ , 2019.
  * [3] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” _Advances in neural information processing systems_ , vol. 27, 2014.
  * [4] M. Rasouli, T. Sun, and R. Rajagopal, “Fedgan: Federated generative adversarial networks for distributed data,” _arXiv preprint arXiv:2006.07228_ , 2020.
  * [5] C. Hardy, E. Le Merrer, and B. Sericola, “Md-gan: Multi-discriminator generative adversarial networks for distributed datasets,” in _2019 IEEE international parallel and distributed processing symposium (IPDPS)_. IEEE, 2019, pp. 866–877.
  * [6] R. Yonetani, T. Takahashi, A. Hashimoto, and Y. Ushiku, “Decentralized learning of generative adversarial networks from non-iid data,” _arXiv preprint arXiv:1905.09684_ , 2019.
  * [7] S. Augenstein, H. B. McMahan, D. Ramage, S. Ramaswamy, P. Kairouz, M. Chen, R. Mathews _et al._ , “Generative models for effective ml on private, decentralized datasets,” _arXiv preprint arXiv:1911.06679_ , 2019.
  * [8] R. Guerraoui, A. Guirguis, A.-M. Kermarrec, and E. L. Merrer, “Fegan: Scaling distributed gans,” in _Proceedings of the 21st International Middleware Conference_ , 2020, pp. 193–206.
  * [9] C. Hardy, E. Le Merrer, and B. Sericola, “Gossiping gans: Position paper,” in _Proceedings of the Second Workshop on Distributed Infrastructures for Deep Learning_ , 2018, pp. 25–28.
  * [10] B. Lakshminarayanan, A. Pritzel, and C. Blundell, “Simple and scalable predictive uncertainty estimation using deep ensembles,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [11] S. Fort, H. Hu, and B. Lakshminarayanan, “Deep ensembles: A loss landscape perspective,” _arXiv preprint arXiv:1912.02757_ , 2019.
  * [12] Y. Wang, L. Zhang, and J. Van De Weijer, “Ensembles of generative adversarial networks,” _arXiv preprint arXiv:1612.00991_ , 2016.
  * [13] A. Ghosh, V. Kulharia, V. P. Namboodiri, P. H. Torr, and P. K. Dokania, “Multi-agent diverse generative adversarial networks,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 8513–8521.
  * [14] J. Geiping, H. Bauermeister, H. Dröge, and M. Moeller, “Inverting gradients-how easy is it to break privacy in federated learning?” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 16 937–16 947, 2020.
  * [15] R. C. Geyer, T. Klein, and M. Nabi, “Differentially private federated learning: A client level perspective,” _arXiv preprint arXiv:1712.07557_ , 2017.
  * [16] A. Radford, L. Metz, and S. Chintala, “Unsupervised representation learning with deep convolutional generative adversarial networks,” _arXiv preprint arXiv:1511.06434_ , 2015.
  * [17] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” _arXiv preprint arXiv:1708.07747_ , 2017.
  * [18] L. Deng, “The mnist database of handwritten digit images for machine learning research,” _IEEE Signal Processing Magazine_ , vol. 29, no. 6, pp. 141–142, 2012.
  * [19] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [20] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter, “Gans trained by a two time-scale update rule converge to a local nash equilibrium,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [21] M. Seitzer, “pytorch-fid: FID Score for PyTorch,” https://github.com/mseitzer/pytorch-fid, August 2020, version 0.2.1.
  * [22] S. P. Karimireddy, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh, “Scaffold: Stochastic controlled averaging for on-device federated learning.” 2019.


# One-sorted Program Algebras

Igor Sedlár  Czech Academy of Sciences, Institute of Computer Science  Johann
J. Wannenburg  Czech Academy of Sciences, Institute of Computer Science

(April 27, 2022)

###### Abstract

Kleene algebra with tests, KAT, provides a simple two-sorted algebraic
framework for verifying properties of propositional while programs. Kleene
algebra with domain, KAD, is a one-sorted alternative to KAT. The equational
theory of KAT embeds into KAD, but KAD lacks some natural properties of KAT.
For instance, not each Kleene algebra expands to a KAD, and the subalgebra of
tests in each KAD is forced to be the maximal Boolean subalgebra of the
negative cone. In this paper we propose a generalization of KAD that avoids
these features while still embedding the equational theory of KAT. We show
that several natural properties of the domain operator of KAD can be added to
the generalized framework without affecting the results. We consider a variant
of the framework where test complementation is defined using a residual of the
Kleene algebra multiplication.

##  1 Introduction

Kleene algebra with tests [9], KAT, is a simple algebraic framework for
verifying properties of propositional while programs. KAT subsumes
propositional Hoare logic [10] and it has been applied in a number of
verification tasks. KAT has computationally attractive fragments [14] and its
extensions have been applied beyond while programs, for instance in network
programming languages [1].

KAT is two-sorted, featuring a Boolean algebra of tests embedded into a Kleene
algebra of programs. For various reasons, a one-sorted alternative to KAT may
be desirable. One such alternative is Kleene algebra with domain, KAD, in its
“internal” formulation [4]. The idea of KAD is to expand Kleene algebra with a
domain operator $d$ such that the set of images of elements of the algebra
under $d$ forms a Boolean algebra. Hence, one obtains a Boolean algebra of
tests in a one-sorted setting. Consequently, the equational theory of KAT
embeds into the equational theory of KAD.

However, the properties of the domain operator in KAD lead to some curious
features of the framework. For instance, the algebra of tests is always the
maximal Boolean subalgebra of the negative cone in the underlying Kleene
algebra. In a sense, then, every “proposition” is considered a test, contrary
to some of the intuitions expressed in [9]. Moreover, not each Kleene algebra
can be expanded with a domain operator, not even every finite one. This is in
contrast with the fact that each KA is expands to a KAT.

In this paper we generalize KAD to a framework we call _one-sorted Kleene
algebra with tests_ , KAt. Our framework has the desired features of KAD:
every KAt contains a Boolean subalgebra of tests and the equational theory of
KAT embeds into the equational theory of KAt. In addition, every Kleene
algebra expands into a KAt, and the subalgebra of tests in KAt is not
necessarily the maximal Boolean subalgebra of the negative cone. We also
consider various extensions of KAt with axioms known from KAD to show which
properties of the domain operator are still consistent with the desired
features of KAt. In addition, we consider a variant of the KAt framework where
test complementation is defined using a residual of Kleene algebra
multiplication. It can be shown that algebras in this framework form a
variety.

The paper is organized as follows. In Sections 2 and 3 we recall Kleene
algebra with tests and Kleene algebra with domain, respectively. In Section 4
we introduce one-sorted Kleene algebra with domain. We show that every Kleene
algebra with domain is a one-sorted Kleene algebra with tests, that the test
algebra in every one-sorted KAT is a Boolean algebra, and that every Kleene
algebra expands into a one-sorted Kleene algebra with tests. In Section 5 we
consider some extensions of one-sorted KAT that retain the good properties. In
Section 6 we show that the equational theory of KAT embeds into the equational
theory of one-sorted KAT and a number of its extensions. Section 7 briefly
considers a residuated variant of one-sorted KAT that forms a variety.

##  2 Kleene algebra with tests

We assume that the reader is familiar with the notion of an _idempotent
semiring_. The definition of Kleene algebra is taken from [7]. The reader is
referred to [9] for more details on Kleene algebra with tests.

######  Definition 1.

A _Kleene algebra_ is an idempotent semiring $(K,\cdot,+,1,0)$ expanded with
an operation ${}^{*}:K\to K$ such that

$\displaystyle 1+xx^{*}\leq x^{*}$ $\displaystyle 1+x^{*}x\leq x^{*}$
$\displaystyle y+xz\leq z\implies x^{*}y\leq z$ $\displaystyle y+zx\leq
z\implies yx^{*}\leq z$

A _Kleene algebra with tests_ is $(K,B,\cdot,+,^{*},1,0,\,\bar{}\,)$ such that

  * •

$(K,\cdot,+,^{*},1,0)$ is a Kleene algebra,

  * •

$B\subseteq K$, and

  * •

$(B,\cdot,+,\,\bar{}\,,1,0)$ is a Boolean algebra.

A standard example of a Kleene algebra is a relational Kleene algebra where
$K$ is a set of binary relations over some set $S$, $\cdot$ is relational
composition, $+$ is set union, ∗ is reflexive transitive closure, $1$ is
identity on $S$ and $0$ is the empty set; another standard example is the
Kleene algebra of regular languages over some finite alphabet.

Every KA is a KAT; take $B=\\{0,1\\}$ and define $\bar{0}=1$, $\bar{1}=0$ and
$\bar{x}=x$ for $x\notin\\{1,0\\}$. The class of Kleene algebra with tests is
denoted as $\mathbf{KAT}$. A standard example of a KAT is a relational KA
expanded with a Boolean subalgebra of the _negative cone_ , i.e. the elements
$x\leq 1$, which in the relational case are subsets of the identity relation.
The class of relational Kleene algebras with tests will be denoted as
$\mathbf{rKAT}$.

The equational theory of $\mathbf{KAT}$ is defined in terms of a two-sorted
language. Let $\mathsf{B}=\\{\mathsf{b}_{n}\mid n\in\omega\\}$ and
$\mathsf{P}=\\{\mathsf{p}_{n}\mid n\in\omega\\}$ be two disjoint sets of _test
variables_ and _program variables_ , respectively. The set of _KAT terms_ is
two sorted:

  * •

tests: $b,c:=\mathsf{b}_{n}\mid\mathsf{0}\mid\mathsf{1}\mid\bar{b}\mid b\cdot
c\mid b+c$

  * •

programs: $p,q:=\mathsf{p}_{n}\mid b\mid p+q\mid p\cdot q\mid p^{*}$

Note that each test is a program, and so we may use program variables to range
over arbitrary KAT terms. The set of KAT terms is denoted as
$\mathscr{T}_{\text{KAT}}$. If $\mathscr{B}$ is a KAT, then a _$\mathscr{B}$
-valuation_ is any function $h$ from $\mathscr{T}_{\text{KAT}}$ to
$\mathscr{B}$ such that

  * •

$h(\mathsf{b}_{n})\in B$

  * •

$h(\mathsf{0})=0$ and $h(\mathsf{1})=1$, and

  * •

$h$ commutes with $\star\in\\{\cdot,+,^{*},\,\bar{}\,\\}$.

A _KAT equation_ is an ordered pair of KAT terms, denoted in general as
$p\approx q$. An equation $p\approx q$ _holds_ is a $\mathscr{B}$-valuation
$h$ iff $h(p)=h(q)$. The _equational theory of $\mathbf{KAT}$_ is the set of
KAT equations that holds in all $\mathscr{B}$-valuations where
$\mathscr{B}\in\mathbf{KAT}$. The equational theory of $\mathbf{KAT}$
($\mathbf{rKAT}$) is denoted as $\mathsf{KAT}$ ($\mathsf{rKAT}$).

Propositional Hoare logic embeds into $\mathsf{KAT}$ [10], $\mathsf{KAT}$ is
PSPACE-complete [2], and $\mathsf{KAT}=\mathsf{rKAT}$ [11].

##  3 Kleene algebra with domain

KAT is a two-sorted framework, and for various reasons it may be desirable to
look for a one-sorted alternative. For instance, “one-sorted domain semirings
are easier to formalise in interactive proof assistants and apply in program
verification and correctness.” [5, p. 576]. A one-sorted alternative called
Kleene algebra with domain was introduced in [4], following earlier work on a
related two-sorted framework [3]. The idea is to expand a Kleene algebra with
an operation $d$ that transforms elements $x\in K$ into _test-like_ elements
$d(x)$, and to show that the set of images of $x\in K$ under $d$, $d(K)$,
forms a Boolean algebra. In other words, instead of assuming the existence of
a Boolean subalgebra, such a subalgebra arises from images under a new
operation $d$.

The desired properties of $d$ are inspired by relational KAT, where tests are
subsets of the identity relation. One obvious choice of a $d$ such that $d(R)$
is a subset of the identity relation is the _relational domain_ operation

$d(R):=\\{(s,s)\mid\exists u.(s,u)\in R\\}$

Informally, $d(R)$ represents the set of states in which the program
associated with $R$ has a terminating computation. The main question shaping
the definition of KAD is the following: _which properties of relational domain
should be adopted on the abstract algebraic level in order to yield a Boolean
subalgebra?_

######  Definition 2.

A _predomain_ operation on a Kleene algebra is any $d:K\to K$ such that

$\displaystyle x\leq d(x)x$ (1) $\displaystyle d(xy)\leq d(xd(y))$ (2)
$\displaystyle d(x)\leq 1$ (3) $\displaystyle d(0)=0$ (4) $\displaystyle
d(x+y)=d(x)+d(y)$ (5)

A _domain_ operation on a Kleene algebra is any predomain operation that
satisfies

$d(xy)=d(xd(y))$ (6)

It is easily checked that the relational domain operation is a domain
operation on relational Kleene algebras.

######  Proposition 1 ([4]).

Let $\mathscr{K}$ be a Kleene algebra and let $d$ be a domain operation on
$\mathscr{K}$. Let $d(K):=\\{y\mid\exists x.y=d(x)\\}$. Then:

  1. 1.

$d(K)$ contains $1$ and $0$, and it is closed under $\cdot$ and $+$;

  2. 2.

$d(\mathscr{K})=(d(K),\cdot,+,1,0)$ is a bounded distributive lattice.

In order to obtain a Boolean algebra from the distributive lattice
$d(\mathscr{K})$, one has to make sure that each test $d(x)$ is complemented
in $d(K)$, that is, for each $d(x)$ there is $y\in d(K)$ such that $d(x)y=0$
and $d(x)+y=1$. An elegant solution to this problem presented in [4] consists
in expanding Kleene algebras with a single unary operation $a$ (_antidomain_)
that allows to define a domain operation $d$ and has properties entailing that
$a(x)$ is a complement of $d(x)$.

######  Definition 3.

A _Kleene algebra with domain_ is a Kleene algebra expanded with an operation
$a:K\to K$ such that

$\displaystyle a(x)x=0$ (7) $\displaystyle a(xy)\leq a(x\,a(a(y))$ (8)
$\displaystyle a(x)+a(a(x))=1$ (9)

We define $d(x):=a(a(x))$.

######  Lemma 1 ([4]).

In each KAD, $d$ is a domain operation and $a(x)$ is a complement of $d(x)$.

######  Theorem 1 ([4]).

In each KAD, $d(\mathscr{K})=(d(K),\cdot,+,1,0)$ is a Boolean algebra.

It has been shown that, at least in the semiring signature extended with $d$,
the domain axioms capture the essential properties of relational domain [12].
However, $d$ has some peculiar features when it comes to general Kleene
algebra and KAT. First, $d(\mathscr{K})$ is necessarily the maximal Boolean
subalgebra of the negative cone of $\mathscr{K}$; see Thm. 8.5 in [4]. In a
sense, then, every “proposition” is considered a test, contrary to some of the
intuitions expressed in [9]. These intuitions also collide with the approach
of taking KAT as KA with a Boolean negative cone [5, 6]. Second, not every
Kleene algebra expands to a KAD, not even every finite one; see Prop. 5.3 in
[4]; see the first counterexample in the appendix. This is in contrast to the
fact that every Kleene algebra expands to a KAT. This feature is caused by (6)
and the authors of [4] express interest in variants of $d$ not satisfying
(6).111The immediate candidate is predomain, but it can be shown that if $d$
is a predomain operation then $d(K)$ is not necessarily closed under $\cdot$,
and that $d(x)=d(x)d(x)$ may fail (see $\mathbf{A}_{4}$ in the appendix).

Hence, it is interesting to ask if there is a suitable one-sorted alternative
to KAT, in the sense of satisfying the following properties:

  * •

(P0) The algebras in the given class $\mathbf{ALT}$ expand Kleene algebras by
additional operations $t$ and $t^{\prime}$.

  * •

(P1) The test algebra $t(\mathscr{A})$ for each $\mathscr{A}\in\mathbf{ALT}$
is a Boolean algebra.

  * •

(P2) Every Kleene algebra expands to an $\mathscr{A}\in\mathbf{ALT}$.

  * •

(P3) The test algebra $t(\mathscr{A})$ is not necessarily the maximal Boolean
subalgebra of the negative cone of $\mathscr{A}$.

  * •

(P4) The equational theory of $\mathbf{KAT}$ embeds into the equational theory
of $\mathbf{ALT}$.

Condition (P2) would ensure that $\mathbf{ALT}$ is a _conservative expansion_
of Kleene algebras, i.e., $\mathbf{ALT}$ satisfies exactly the same
$(\cdot,+,^{*},1,0)$-equations as Kleene algebras.

##  4 One-sorted KAT

In the present section, we define a class of algebras satisfying (P0–3). The
algebras in the class will be called simply _one-sorted Kleene algebras with
tests_ , KAt. Property (P4) is established in Section 6.

######  Definition 4.

A _one-sorted Kleene algebra with tests_ is a Kleene algebra expanded by two
unary operations $t$ and $t^{\prime}$ such that

$\displaystyle t(0)=0$ (10) $\displaystyle t(1)=1$ (11) $\displaystyle
t(t(x)+t(y))=t(x)+t(y)$ (12) $\displaystyle t(t(x)t(y))=t(x)\,t(y)$ (13)
$\displaystyle t(x)t(x)=t(x)$ (14) $\displaystyle t(x)\leq 1$ (15)
$\displaystyle 1\leq t^{\prime}(t(x))+t(x)$ (16) $\displaystyle
t^{\prime}(t(x))\,t(x)\leq 0$ (17) $\displaystyle
t^{\prime}(t(x))=t(t^{\prime}(t(x)))$ (18)

######  Example 1.

Relational KA with $t(R)=\\{(w,w)\mid\exists v.\,(w,v)\in R)\\}$ and
$t^{\prime}(R)=\\{(w,w)\mid\neg\exists v.\,(w,v)\in R)\\}$.

Every KAD $\mathscr{D}=(K,\cdot,+,\,^{*},1,0,a)$ can be seen as an algebra of
the type of KAt, namely, by adding $d$ explicitly to the signature. It can
then be shown that KAt generalizes KAD.

######  Proposition 2.

Every KAD is a KAt.

###### Proof.

It needs to be checked that the KAt axioms are satisfied by any KAD where $d$
is seen as $t$ and $a$ is seen as $t^{\prime}$. This is mostly a matter of
easy calculation using known KAD properties. ∎

Let $\mathscr{K}=(K,\cdot,+,^{*},1,0,t,t^{\prime})$ be a KAt. Let
$t(K)=\\{x\mid\exists y.x=t(y)\\}$.

######  Lemma 2.

For all KAt, $d(K)$ is closed under the semiring operations and $t^{\prime}$.

###### Proof.

The set $d(K)$ contains constants $1,0$ by (10–11), and it is closed under $+$
and $\cdot$ by (12–13). $d(K)$ is closed under $t^{\prime}$ by (18). ∎

For each KAt $\mathscr{K}$, let
$t(\mathscr{K})=(t(K),\cdot,+,1,0,t^{\prime})$. This is a well defined
subalgebra of $\mathscr{K}$ by Lemma 2.

######  Theorem 2.

Each $t(\mathscr{K})$ is a Boolean algebra.

###### Proof.

Each $t(\mathscr{K})$ is a bounded distributive lattice by (14–15) and
properties of semirings. By (16–17), $t^{\prime}(x)$ is a complement of $x$
for all $x\in t(K)$. Since $t(\mathscr{K})$ is a bounded distributive lattice,
it is uniquely complemented, and so it is a Boolean algebra. ∎

######  Theorem 3.

Each Kleene algebra expands to a KAt.

###### Proof.

The proof is similar as in the case of KAT. For any Kleene algebra
$(K,\cdot,+,^{*},1,0)$, define:

$t(x)=\begin{cases}0&\text{if }x=0\\\ 1&\text{otherwise.}\end{cases}$
$t^{\prime}(x)=\begin{cases}0&\text{if }x=1\\\ 1&\text{if }x=0\\\
x&\text{otherwise.}\end{cases}$

The rest is checked by easy calculation. ∎

Theorem 3 shows that, unlike KAD and like KAT, KAt is a proper generalization
of Kleene algebra. The proof of the theorem also shows that $t(\mathscr{K})$
need not be the maximal Boolean subalgebra of the negative cone.

On the other hand, one may say that $t(x)$ lacks any intuitive relation to
$x$, unlike the domain operator in KAD. For instance, it holds in KAD that
$d(x)$ is a left preserver of $x$, that is, $x\leq d(x)x$. This lack of
connection between $x$ and $t(x)$ can be seen as the reason why (P0–3) are
satisfied. However, the following section shows that this is only partially
so.

##  5 An extension of KAt

In this section we consider a particular extension of KAt with a number of
axioms known from KAD. We show that the extension still has properties (P0–3).

######  Definition 5.

A _strong KAt_ , sKAt, is a KAt satisfying the following axioms:

$\displaystyle t(x+y)=t(x)+t(y)$ (19) $\displaystyle x\leq t(x)x$ (20)
$\displaystyle t(t(x)y)\leq t(x)$ (21) $\displaystyle t(xy)\leq t(xt(y))$ (22)

(19) entails that $t$ is monotonic; (20) says that $t(x)$ is a left preserver
of $x$; (21) entails

$x\leq t(y)x\implies t(x)\leq t(y)\,,$ (23)

saying that $t(x)$ is the _least_ left preserver among tests; and (22) is the
sublocality property of predomain operators. In fact, $t$ is a predomain
operator in each sKAt. The algebra from Prop. 5.3 in [4] shows that $t$ need
not be a domain operation; see the first example in the appendix.

It is clear that sKAt satisfies (P0) and (P1). It can also be shown, by
revisiting the construction in the proof of Theorem 3 that (P2) and (P3) are
satisfied as well. However, as shown already in [4], adding locality
$t(xt(y))\leq t(xy)$ destroys (P2) and (P3).

##  6 Embedding KAT

In this section we show that KAt has property (P4) as well. The result
actually applies to a larger class of cases.

We say that a KAT $\mathscr{K}=(K,B,\cdot,+,^{*},1,0,\,\bar{}\,)$ _expands_
into a KAt $\mathscr{A}=(K,\cdot,+,\,^{*},1,0,t,t^{\prime})$ iff

  * •

$B=t(K)$.

Note that if $\mathscr{K}$ expands to $\mathscr{A}$, then
$\bar{b}=t^{\prime}(b)$, since
$\bar{b}=\overline{t(y)}=t^{\prime}t(x)=t^{\prime}(b)$. The second to last
equation holds since $t^{\prime}t(x)$ is the complement of $t(x)$ in $t(K)=B$.

######  Definition 6.

A class of KAt $\mathbf{A}$ is _KAT-like_ iff it satisfies properties (P0),
(P1) and

  * •

(P2a) Every KAT expands to a $\mathscr{A}\in\mathbf{A}$.

######  Theorem 4.

If $\mathbf{A}$ is KAT-like, then $\mathbf{A}$ satisfies (P4).

In the proof of the theorem, we will use the following translation from
$\mathscr{T}_{\text{KAT}}$ to $\mathscr{T}_{\text{KAt}}$:

  * •

$Tr(\mathsf{p}_{n})=\mathsf{x}_{2n}$

  * •

$Tr(\mathsf{b}_{n})=t(\mathsf{x}_{2n+1})$

  * •

$Tr(\mathsf{0})=t(\mathsf{0})$

  * •

$Tr(\mathsf{1})=t(\mathsf{1})$

  * •

$Tr(p+q)=Tr(p)+Tr(q)$

  * •

$Tr(p\cdot q)=Tr(p)\cdot Tr(q)$

  * •

$Tr(p^{*})=Tr(p)^{*}$

  * •

$Tr(\bar{b})=t^{\prime}(Tr(b))$

###### Proof.

We show that, for all KAT equations $p\approx q$, there is KAT
$\mathscr{K}\not\models p\approx q$ iff there is $\mathscr{A}\not\models
Tr(p)\approx Tr(q)$ such that $\mathscr{A}\in\mathbf{A}$.

First, if $\mathscr{K}\not\models p\approx q$, then there is a
$\mathscr{K}$-valuation [ ] such that
${\texttt{[}p\texttt{]}}\neq{\texttt{[}q\texttt{]}}$. By (P2a), $\mathscr{K}$
expands to $\mathscr{A}\in\mathbf{A}$. We define an $\mathscr{A}$-valuation
[[ ]] as the unique homomorphism such that

  * •

$\\!\text{{[\\!\\![}}\mathsf{x}_{2n}\text{{]\\!\\!]}}={\texttt{[}\mathsf{p}_{n}\texttt{]}}$,

  * •

$\\!\text{{[\\!\\![}}\mathsf{x}_{2n+1}\text{{]\\!\\!]}}={\texttt{[}\mathsf{b}_{n}\texttt{]}}$.

We prove by induction on KAT terms $r$ that

${\texttt{[}r\texttt{]}}=\\!\text{{[\\!\\![}}Tr(r)\text{{]\\!\\!]}}$ (24)

Before the main inductive proof, we prove that (24) holds for all tests $b$;
the proof is by induction on tests. The base case is established as follows:
$\\!\text{{[\\!\\![}}Tr(\mathsf{b}_{n})\text{{]\\!\\!]}}=\\!\text{{[\\!\\![}}t(\mathsf{x}_{2n+1})\text{{]\\!\\!]}}=t\\!\text{{[\\!\\![}}\mathsf{x}_{2n+1}\text{{]\\!\\!]}}=t{\texttt{[}\mathsf{b}_{n}\texttt{]}}={\texttt{[}\mathsf{b}_{n}\texttt{]}}$.
The last equation holds by definition of expansion (we know that
${\texttt{[}\mathsf{b}_{n}\texttt{]}}\in B=t(K)$ and that $tt(x)=t(x)$). The
cases of the induction step for $+$ and $\cdot$ are trivial. The case for
$\,\bar{}\,$ is established as follows:
$\\!\text{{[\\!\\![}}Tr(bar{b})\text{{]\\!\\!]}}=\\!\text{{[\\!\\![}}t^{\prime}Tr(b)\text{{]\\!\\!]}}=t^{\prime}\\!\text{{[\\!\\![}}Tr(b)\text{{]\\!\\!]}}=t^{\prime}{\texttt{[}b\texttt{]}}={\texttt{[}t^{\prime}(b)\texttt{]}}={\texttt{[}\bar{b}\texttt{]}}$
by the definition of expansion (see the note after the definition). This
concludes the proof for tests. The main inductive proof for KAT terms is now
trivial.

The converse claim is established as follows. Assume that there is
$\mathscr{A}\in\mathbf{A}$ such that $\mathscr{A}\not\models Tr(p)\approx
Tr(q)$. Hence, there is an $\mathscr{A}$-valuation [[ ]] such that
$\\!\text{{[\\!\\![}}Tr(p)\text{{]\\!\\!]}}\neq\\!\text{{[\\!\\![}}Tr(q)\text{{]\\!\\!]}}$.
It follows from (P1) that $t(\mathscr{A})$ is a Boolean algebra, and so
$\mathscr{K}=(K,t(\mathscr{A}),\cdot,+,\,^{*},1,0,t^{\prime})$ is a KAT. We
define a $\mathscr{K}$-valuation [ ] as the unique KAT-homomorphism such that

  * •

${\texttt{[}\mathsf{p}_{n}\texttt{]}}=\\!\text{{[\\!\\![}}\mathsf{x}_{2n}\text{{]\\!\\!]}}$

  * •

${\texttt{[}\mathsf{b}_{n}\texttt{]}}=\\!\text{{[\\!\\![}}t(\mathsf{x}_{2n+1})\text{{]\\!\\!]}}$

As before, it is sufficient to prove that (24) holds in this setting for all
KAT terms $r$. The proof is again by induction and the only interesting case
is $\bar{b}$ (the case for $\mathsf{b}_{n}$ holds by definition). We reason as
follows:
$\\!\text{{[\\!\\![}}Tr(\bar{b})\text{{]\\!\\!]}}=\\!\text{{[\\!\\![}}t^{\prime}Tr(b)\text{{]\\!\\!]}}=t^{\prime}{\texttt{[}b\texttt{]}}={\texttt{[}t^{\prime}(b)\texttt{]}}={\texttt{[}\bar{b}\texttt{]}}$.
∎

######  Theorem 5.

$\mathbf{KAt}$ is KAT-like.

###### Proof.

Take an arbitrary KAT $\mathscr{K}=(K,B,\cdot,+,\,^{*},1,0,\,\bar{}\,)$ and
define $\mathscr{A}=(K,\cdot,+,\,^{*},1,0,t,t^{\prime})$ where:

$t(x)=\begin{cases}x&\text{if }x\in B\\\ 1&\text{otherwise.}\end{cases}$
$t^{\prime}(x)=\begin{cases}\bar{x}&\text{if }x\in B\\\
x&\text{otherwise.}\end{cases}$

It can be easily checked that $\mathscr{A}$ is a KAt. ∎

It is a matter of easy calculation that $\mathscr{A}$ in the proof of the
above theorem satisfies (20) and (21). For (19) and (22), a different approach
is needed.

It is known that the equational theory of KAT is identical to the equational
theory of relational KAT [11]. Hence, one could work with a modification of
the notion of a KAT-like class of algebras.

######  Definition 7.

A class of KAt $\mathbf{A}$ is _rKAT-like_ iff it satisfies properties (P0),
(P1) and

  * •

(P2b) Every relational KAT expands to a $\mathscr{A}\in\mathbf{A}$.

######  Theorem 6.

If $\mathbf{A}$ is rKAT-like, then $\mathbf{A}$ satisfies (P4).

###### Proof.

The fact that (24) holds in both directions of the proof is established as
before. ∎

######  Theorem 7.

$\mathbf{sKAt}$ and $\mathbf{KAD}$ are rKAT-like.

###### Proof.

Take any relational KAT, and define

  * •

$t(R)=\\{(s,s)\mid\exists u.(s,u)\in R\\}$;

  * •

$t^{\prime}(R)=\\{(s,s)\mid\neg\exists u.(s,u)\in R\\}$.

It is easily checked that we obtain a sKAt. ∎

Since it is known that Propositional Hoare Logic embeds into KAT [10], we
obtain the result that KAt, sKAt and KAD subsume PHL as well (the latter case
is known).

##  7 Residual

In this section we focus on a particular version of KAt where $t^{\prime}$ is
not a primitive operator, but it is defined using the residual of Kleene
algebra multiplication. It is known Kleene algebras with residuals form a
variety [13]. Consequently, one-sorted residuated Kleene algebras and their
equational extensions form varieties as well.

######  Definition 8.

A _residuated Kleene algebra_ is a Kleene algebra expanded with a binary
operation $\to$ such that

$xy\leq z\iff x\leq y\to z$ (25)

######  Definition 9.

A _residuated one-sorted Kleene algebra with tests_ is a residuated Kleene
algebra expanded with a unary operation $t$ satisfying (10–15) and

$\displaystyle 1\leq t(t(x)\to 0)+t(x)$ (26) $\displaystyle t(t(x)\to
0)\,t(x)\leq 0$ (27)

We define $t^{\prime}(x)=t(t(x)\to 0)$.

It is an easy consequence of the definition that the class of residuated KAt
forms a (finitely based) variety. We denote it as
$\mathbf{KA}\vec{\mathbf{t}}$.

######  Proposition 3.

Each residuated KAt is a KAt.

###### Proof.

It is easy to check that $t^{\prime}$ as defined in terms of $t$ and $\to$
satisfies (16–17). It follows from (11) and (13) that $t(t(x))=t(x)$. Hence,
(18) holds as well. ∎

######  Theorem 8.

Each join-complete Kleene algebra expands to a residuated KAt.

###### Proof.

Each join-complete KA is residuated since we can define

$x\to y:=\sum\\{z\mid zx\leq y\\}\,.$

Define $t(x)$ as in the proof of Theorem 3. We prove by cases that (26–27)
hold.

  * •

If $x=0$: $t(t(x)\to 0)+t(x)=t(0\to 0)+0=t(1)+0=1$ and $t(t(x)\to
0)\,t(x)=10=0$;

  * •

If $x\neq 0$: $t(t(x)\to 0)+t(x)=t(1\to 0)+1=t(0)+1=1$ and $t(t(x)\to
0)\,t(x)=01=0$.∎

Not every KA expands to a residuated KA [8], so not every KA expands to a
residuated KAt.

##  8 Conclusion

In this paper we studied a one-sorted variant of Kleene algebra with tests,
KAt. We have shown that KAt generalizes Kleene algebra with domain, KAD, and
that it retains the good properties of KAD, namely (P1) the test algebra of
any KAt is a Boolean algebra and (P4) the equational theory of KAT embeds into
the equational theory of KAt. Moreover, KAt avoids the bad properties of KAD:
unlike KAD, every Kleene algebra expands to a KAt (P2), and the test algebra
in KAt is not necessarily the maximal Boolean subalgebra of the negative cone
(P3). We have shown that adding several axioms familiar from KAD to KAt does
in fact not injure (P2) and (P3). We believe that this leads to a better
general view of the landscape of one-sorted program algebras.

## References

  * [1] Carolyn Jane Anderson, Nate Foster, Arjun Guha, Jean-Baptiste Jeannin, Dexter Kozen, Cole Schlesinger, and David Walker.  NetKAT: Semantic foundations for networks.  In Proc. 41st ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages (POPL’14), pages 113–126, San Diego, California, USA, January 2014\. ACM.
  * [2] Ernie Cohen, Dexter Kozen, and Frederick Smith.  The complexity of Kleene algebra with tests.  Technical Report TR96-1598, Computer Science Department, Cornell University, July 1996.
  * [3] Jules Desharnais, Bernhard Möller, and Georg Struth.  Kleene algebra with domain.  ACM Trans. Comput. Logic, 7(4):798–833, oct 2006.
  * [4] Jules Desharnais and Georg Struth.  Internal axioms for domain semirings.  Science of Computer Programming, 76(3):181–203, 2011.
  * [5] Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański.  Domain semirings united.  Acta Cybernetica, pages 575–583, 2022.
  * [6] Peter Jipsen.  From semirings to residuated Kleene lattices.  Studia Logica, 76(2):291–303, Mar 2004.
  * [7] Dexter Kozen.  A completeness theorem for Kleene algebras and the algebra of regular events.  Information and Computation, 110(2):366 – 390, 1994.
  * [8] D. Kozen.  On action algebras.  In Logic and Information Flow, pages 78 – 88. MIT Press, 1994\.
  * [9] Dexter Kozen.  Kleene algebra with tests.  ACM Trans. Program. Lang. Syst., 19(3):427–443, May 1997.
  * [10] Dexter Kozen.  On Hoare logic and Kleene algebra with tests.  ACM Trans. Comput. Logic, 1(1):60–76, July 2000.
  * [11] Dexter Kozen and Frederick Smith.  Kleene algebra with tests: Completeness and decidability.  In Dirk van Dalen and Marc Bezem, editors, Computer Science Logic, pages 244–259, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
  * [12] Brett McLean.  Free kleene algebras with domain.  Journal of Logical and Algebraic Methods in Programming, 117:100606, 2020.
  * [13] Vaughan Pratt.  Action logic and pure induction.  In Logics in AI. European workshop JELIA ’90, Amsterdam, the Netherlands, September 10-14, 1990. Proceedings, pages 97–120. Berlin etc.: Springer-Verlag, 1991.
  * [14] Steffen Smolka, Nate Foster, Justin Hsu, Tobias Kappé, Dexter Kozen, and Alexandra Silva.  Guarded Kleene algebra with tests: Verification of uninterpreted programs in nearly linear time.  In Proc. 47th ACM SIGPLAN Symp. Principles of Programming Languages (POPL’20), pages 61:1–28, New Orleans, January 2020. ACM.

##  Appendix A Counter-examples

The following algebra $\mathscr{A}_{3}$ exhibits a Kleene algebra with
predomain operation $d$, which does not satisfy the locality axiom $d(2\cdot
2)=0\neq 1=d(2\cdot d(2))$. This example is closely related to the example in
Prop. 5.3 in [4].

$1$$2$$0$$\mathscr{A}_{3}$ |  | $\cdot$ | 0 | 1 | 2
---|---|---|---
0 | 0 | 0 | 0
1 | 0 | 1 | 2
2 | 0 | 2 | 0
| ∗ | 0 | 1 | 2
---|---|---|---
| 1 | 1 | 1
| $d$ | 0 | 1 | 2
---|---|---|---
| 0 | 1 | 1

The following algebra $\mathscr{A}_{4}$ exhibits a Kleene algebra with
predomain operation $d$, such that $d(A_{4})$ is not closed under $\cdot$,
since $d(2)=3\neq 2=d(2)d(2)\notin d(A_{4})$.

$1$$3$$2$$0$$\mathscr{A}_{4}$ |  | $\cdot$ | 0 | 1 | 2 | 3
---|---|---|---|---
0 | 0 | 0 | 0 | 0
1 | 0 | 1 | 2 | 3
2 | 0 | 2 | 0 | 0
3 | 0 | 3 | 2 | 3
| ∗ | 0 | 1 | 2 | 3
---|---|---|---|---
| 1 | 1 | 1 | 1
| $d$ | 0 | 1 | 2 | 3
---|---|---|---|---
| 0 | 1 | 3 | 1