# Constructing and Evaluating an Explainable Model for COVID-19 Diagnosis from
Chest X-rays

Rishab Khincha<EMAIL_ADDRESS>
BITS Pilani  Goa  India  Soundarya Krishnan<EMAIL_ADDRESS>
BITS Pilani  Goa  India  Tirtharaj Dash<EMAIL_ADDRESS>
BITS Pilani  Goa  India  Lovekesh Vig<EMAIL_ADDRESS>
TCS Research  New Delhi  India  Ashwin Srinivasan<EMAIL_ADDRESS>
BITS Pilani  Goa  India

###### Abstract

In this paper, our focus is on constructing models to assist a clinician in
the diagnosis of COVID-19 patients in situations where it is easier and
cheaper to obtain X-ray data than to obtain high-quality images like those
from CT scans. Deep neural networks have repeatedly been shown to be capable
of constructing highly predictive models for disease detection directly from
image data. However, their use in assisting clinicians has repeatedly hit a
stumbling block, because of their black-box nature. Some of this difficulty
can be alleviated if predictions were accompanied by explanations expressed in
clinically-relevant terms. In this paper, deep neural networks are used to
extract domain-specific features(morphological features like ground glass
opacity and disease indications like pneumonia) directly from the image data.
Predictions about these features are then used to construct a symbolic model
(a decision tree) for the diagnosis of COVID-19 from chest X-rays. We
accompany these predictions with two kinds of explanations: visual (saliency
maps, derived from the neural stage), and textual (logical descriptions,
derived from the symbolic stage). A radiologist rates the usefulness of the
visual and textual explanations. Our results suggest that: (a) There is no
significant loss in predictive accuracies when using the neural-symbolic model
over using a single end-to-end model; and (b) The radiologist usually finds at
least one of visual or textual explanations relevant; In addition, the textual
explanations are better than a “textual baseline” more often than the
corresponding visual case. This suggests either: the textual representation is
is more relevant to the diagnosistic task, or that the visual representation
is not very relevant for the diagnostic task, or both. Taken together, these
results demonstrate that neural models can be employed usefully in identifying
domain-specific features from low-level image data; that textual explanations
in terms of clinically-relevant features may be useful; and that visual
explanations will need to be clinically meaningful to be useful.

###### keywords:

Hybrid models, Neural-Symbolic models, Human-in-the-loop, Explainable ML,
COVID-19

(a) Single End-to-End Model

(b) Hierarchical Model

Figure 1: Two approaches to building explainable models

##  1 Introduction

The use of explainable symbolic models for diagnosis of disease is not new
(MYCIN and Internist-I, for example, were developed from the early 1970s, with
just this purpose Shortliffe and Buchanan (1975); Miller et al. (1982)).
Neither is the use of hierarchical approaches to Computer Vision, in which
high-level symbolic models use the results of low-level feature-extraction
from raw images (see for example, Ballard and Brown (1982)). For most of
these, the symbolic component has fulfilled purpose of generating limited
answers to “Why” type questions. Recent developments in hardware, storage, and
algorithmic optimisation has however made possible the construction of very
large end-to-end neural network models that are capable of predicting the
probability of disease, directly from raw image data (see Fig. 1)

Although end-to-end models can produce accurate diagnosis of COVID-19 (Asnaoui
and Chawki, 2020; Toğaçar et al., 2020; Mangal et al., 2020; Wang and Wong,
2020; Gozes et al., 2020), they are often considered as black-box models, with
little or no explanatory power (Lipton, 2016). This has proved to be a
stumbling block in their clinical acceptability.

However, interpretability and explainability of these models has not been a
focus for these works. Work in these areas is crucial for acceptance by
physicians, as well as for sanity checks during model development.

Saliency-like visual explanations (GSInquire in Wang and Wong (2020) and
GradCAMs in Mangal et al. (2020); Karim et al. (2020) have been used to
highlight the relevant regions for the diagnosis made by the model. However,
these maps may have less utility in a medical setting, consistent to previous
findings like in Arun et al. (2020). None of these works explore any other
means of explanations. Most crucially, most works do not consult clinicians to
find out which types of explanations are actually meaningful to them and
assist them in diagnosis.

In this paper, we investigate the use of a hierarchical neural-symbolic
approach for COVID-19 diagnosis, accompanied by a description of why the
diagnosis was reached. We consider two kinds of explanations: (a) Visual, in
the form of saliency maps from the neural-stage that construct the domain-
specific features used for diagnosis; and (b) Textual, in the form of a
description obtained from the symbolic model when making a diagnosis. We
compare these against the following baselines that are agnostic to any
decision being made: (c) A simple segmentation map of the lungs; and (d) A
simple tabulation of the input to the symbolic model for the data instance
being diagnosed. The thinking here is that for (a) to be a relevant visual
explanation, it should be judged (by a radiologist) to be at least better than
(c); and for (b) to be relevant, it should be judged (again, by a radiologist)
to be at least better than (d).

Recently, a categorisation of model explainability has been proposed by
Arrieta et al. (2019). In this categorisation, explanations in (a) constitute
local, visual explanations; and (b) constitute global, textual explanations.
To promote reproducibility of our findings, and for any future extensions, we
provide the datasets collected from an experienced radiologist on request.

Figure 2: Neural-Symbolic Pipeline for COVID-19 diagnosis. The $S$-model is a
deep network for predicting symptoms; the $R$-model is a deep network for
predicting radiological features; and the $T$-model is a decision-tree. $E$
refers to a set of procedures for extracting visual and symbolic explanations.

##  2 Neural-Symbolic Modelling for Diagnosis and Explanation

In this section, we describe a hierarchical approach for obtaining diagnoses
and explanations. The first stage of the hierarchical approach performs a form
of domain-specific representation-learning. Two deep neural networks are used
to obtain clinically relevant features directly from images. The $S$-model is
a deep network that predicts symptomatic features like consolidations, pleural
effusions and so on. The $R$-model is a deep network that predicts
morphological features like ground-glass opacity and air-space opacifications
(see Fig. 2). The principal datasets used in each of the models are shown in
Table 1.

Figure 3: Explanations for COVID-19 diagnosis

###  2.1 Stage 1: Neural Models for Clinical Features

The $S$-model is a CheXNet (Rajpurkar et al., 2017) model, obtained by
minimising the binary crossentropy loss using an Adam optimizer.

The $R$-model is a deep model that identifies radiologically-relevant
morphological symptoms. The model in this paper focuses on predicting the
occurrence of various forms of opacification in chest X-rays. To train the
$R$-model, we use a dataset assembled from: (a) Morphological annotations for
COVID-19 X-rays from the COVIDx dataset - we call this the COVIDr dataset; (b)
Images for pneumonia patients taken from the NIH dataset; (c) Images for
healthy and tuberculosis patients taken from the Pulmonary Chest X-ray
dataset. The COVIDr dataset contains annotatations made by a practising
radiologist from the NHS, UK. We describe the annotation process first.

Chest X-rays from COVID-19 positive patients are annotated with one of 7
morphological labels. Here, we are interested in simply two broad categories
of these labels, namely the presence (or absence) of Ground Glass Opacity
($GGO$) and Air Space Opacification ($ASO$). In COVID-19 images, $GGO$ is
$present$ if the Ground Glass Opacity annotation is marked as present; and
$ASO$ is $present$ if any of: Bilateral or Unilateral Air Space Opacification
annotations are marked as _present_ (See Appendix A for more details on the
COVIDr dataset). For healthy samples, we assume both $GGO$ and $ASO$ are
absent. For tuberculosis and pneumonia patients, both $GGO$ and $ASO$ are not
known (these images were not seen during annotation).

The $R$-model is constructed to predict a $1$-hot encoding of of one of 5
values: only $GGO$ is $present$; only $ASO$ is $present$; both $GGO$ and $ASO$
are $present$; both $GGO$ and $ASO$ are $absent$; and both $GGO$ and $ASO$ are
unknown. The model is constructed using a training, validation, and the
independent held-out test data as described Section 3.3. Input data for
constructing the model consist of chest X-ray images, and the predictions of
the $S$-model. The final model is obtained by minimising the categorical
cross-entropy loss using an Adam optimizer.

Table 1: Datasets Table Dataset | Model | Details
---|---|---
NIH Chest X-ray Wang et al. (2017) |  $S$-model |  | 112,120 X-ray images with 14 disease
---
labels from 30,805 unique patients
Default train-val-test split used.
$R$-model |  | Pneumonia images used.
---
Train(234) and test(88).
Pulmonary Chest X-ray Jaeger et al. (2014) |  $Seg$-model |  | Chest X-rays and their masks used.
---
Train (566) and Test (134)
$R$-model |  | Tuberculosis and healthy Chest X-rays used.
---
Tuberculosis - Train (295) and Test (88);
Healthy - Train(294) and Test(110)
COVIDx Cohen et al. (2020) |  $Seg$-model |  | Chest X-rays and their manually
---
annotated masks used.
$R$-model |  | COVID-19 positive Chest X-rays used.
---
Train (196) and Test (30)
COVIDr |  $R$-model |  | Relevant radiological annotations from a
---
practicing radiologist for COVID-19 positive
Chest X-rays from COVIDx.
See Appendix A for details.

###  2.2 Stage 2: Symbolic Model for Diagnosis

In this stage, outputs of the $S$ and $R$-models along with labels for images
are used to construct a decision-tree for COVID-19 diagnosis (the class-labels
for the decision-tree are _COV+_ or _COV–_ , where the latter refers to images
of healthy, pneumonia and tuberculosis patients).111 The input to for tree-
construction are probability vectors for symptoms and boolean-values for the
morphological features. Recall the $R$-models essentially predict whether
$GGO$ and $ASO$ are present, absent, or missing. Details of tree-construction
are in Section 3.3.

###  2.3 Explanations

We examine two kinds of model-based explanations visual and textual, each with
the corresponding baselines. We use the term “inductive” to qualify the
explanation based on a machine-constructed model. The baselines are simple
summarisations of the relevant features of the data, and are qualified by the
term “descriptive”. We require the inductive explanations to be at least as
useful to the clinicians as the descriptive summaries. Details of these
categories are:

Visual, Inductive.

This consists of class activation maps (GradCAMs, proposed by Selvaraju et al.
(2016)), showing gradations of saliency in the $R$-model.

Visual, Descriptive.

This acts of a baseline for the corresponding inductive explanation. It
consists of masks showing a segmentation of the lungs obtained using a deep
network.

Symbolic, Inductive.

This is a translation of the sequence of decisions made by the symbolic model
in reaching a diagnosis.222 For simplicity, we leave out statements about
missing values when generating explanations. It is unclear whether statements
of the form “X is missing” are of value to the radiologist, but such an
expression can nevertheless have predictive value.

Symbolic, Descriptive.

This acts as a baseline for assessing the utility of the corresponding
inductive explanation. It is a tabulation of discretised values of
probabilities of the outputs of the $S$ and $R$-models. The discretisation is
into 3 simple categories ($high$, $medium$, and $low$).

Examples of each of these kinds of these categories are shown in Fig. 3.

##  3 Empirical Evaluation

###  3.1 Aims

Our aim is to test the neural-symbolic system proposed in Section 2 along the
following dimensions:

  * •

Predictive We investigate if there is any significant loss in predictive
accuracy over using a single end-to-end deep network model with access to the
same image data.

  * •

Explanatory We investigate the clinical usefulness of the visual and symbolic
explanations described earlier.

###  3.2 Materials

####  3.2.1 Data

The datasets used in this paper are shown in Table 1. The COVIDr dataset has
been annotated a practising radiologist. It captures important ground glass
opacities and air space opacifications from the Chest X-rays relevant to the
diagnosis of COVID-19 (See Appendix A for more details).

####  3.2.2 Algorithms and Machines

All the experiments are conducted in Python environment (Tensorflow/Keras) in
a machine with 64GB main memory, 16-core Intel processor and 8GB NVIDIA P4000
graphics processor.

###  3.3 Methods

We adopt the following method for evaluation of predictive accuracy:

  1. 1.

Split the COVIDx dataset into _COVIDxTrain_ and _COVIDxTest_

  2. 2.

Construct an end-to-end deep model on the _COVIDxTrain_ data and use it to
obtain predictions on the _COVIDxTest_ data.

  3. 3.

Construct an $S$-model using the $NIH$ dataset and use it to obtain
predictions for the _COVIDxTrain_ data.

  4. 4.

Construct an $R$-model using pre-trained weights (see details below), and the
_COVIDxTrain_ data and use it to construct predictions for morphological
features for the _COVIDxTrain_ data.

  5. 5.

Construct a $T$-model (decision tree) using the outputs of the $S$-model (Step
3) and the $R$-model (Step 4) and use it to obtain predictions on the
_COVIDxTest_ data

  6. 6.

Compare the estimated accuracies on _COVIDxTest_ of the $T$-model (Step 5) and
the end-to-end deep model (Step 2)

The following details are relevant:

  * •

We use the default split provided by Cohen et al. (2020) for splitting the
COVIDx data in _COVIDxTrain_ and the completely held out test-set,
_COVIDxTest_

  * •

Pre-trained weights for the end-to-end model are from ImageNet. The learning
rate used was $10^{-4}$ and the model was trained for 500 epochs.

  * •

The train, validation and test set for the $S$-model uses the default split
from Wang et al. (2017) with 62428, 6336, and 1518 images respectively.

  * •

There are two choices for pre-trained weights for the $R$-model. We have a
choice of either using a generic pre-training (using ImageNet) or the domain-
specific pre-training (using the end-to-end model in Step 2). We use a subset
of _COVIDxTrain_ as a validation set to decide between these alternatives,
which resulted in the use of domain-specific pre-trained weights.

  * •

We split the _COVIDxTrain_ set into a 85-15 train-val set to construct the
$R$-model. We perform a sweep across 3 learning rate settings ($10^{-3}$,
$10^{-4}$ and $10^{-5}$) and epochs (100, 250, 500) and the train split to
build 9 $R$-models. The one performing best on the val split is selected as
our final $R$-model.

  * •

Assessments of comparative difference in accuracies are made using a Gaussian
approximation to the Binomial distribution. Given an accuracy of $p$ on
_COVIDxTest_ , the standard deviation (s.d) is given by $\sqrt{p(1-p)/n}$,
where $n$ is the number of instances in _COVIDxTest_. Then a difference in
accuracy is taken to be significant if it is 2 or more s.d’s away.

We adopt the following method for evaluation of explanations. For a subset of
images in _COVIDxTest_ :

  1. 1.

Obtain inductive visual and textual explanations along with their
corresponding baselines. explanations (inductive and descriptive)

  2. 2.

Obtain a radiological assessment of (a) Utility of visual and textual
explanations; (b) Comparative utility of visual and textual explanations with
the baselines.

The following details are relevant:

  * •

Visual inductive explanations are class activation maps obtained using
GradCAM. Visual descriptive baselines are obtained using the lung segmentation
model trained in Section 2.3.

  * •

Textual descriptive baselines are obtained from the predictions of the $R$ and
the $S$-models by binning the probabilities into _Low_ ($\leq 0.33$), _Medium_
($\leq 0.67$) or _High_.

  * •

The radiological assessments of the utility for each of the individual
explanations as well as the comparative utilities are obtained by asking the
radiologist a series of questions described in Appendix C.

###  3.4 Results

Table 2: Confusion Matrices for COVID-19 Prediction. (COV$+$ is COVID-19
positive; COV$-$ is not COVID-19 positive)

(a) End to End model Act Pred | COV$+$ | COV$-$
---|---|---
COV$+$ | 26 | 4
COV$-$ | 1 | 297

(b) Neural-Symbolic Model Act Pred | COV$+$ | COV$-$
---|---|---
COV$+$ | 23 | 7
COV$-$ | 2 | 296

Table 3: Usefulness of explanations and baselines as rated by the radiologist (Vis-Visual; Text-Textual; Ind-Inductive; Des-Descriptive) | Vis-Ind | Vis-Des | Text-Ind | Text-Des
---|---|---|---|---
Useful | 14 | 21 | 17 | 6
Somewhat Useful | 7 | 5 | 1 | 4
Not Useful | 9 | 1 | 12 | 20

The main observations to note are these:333Here, we term an explanation as
“relevant” if it is _useful_ or _somewhat useful_. (1) The estimated
predictive accuracy of the end-to-end approach is $0.985\pm 0.007$ and that of
the Neural-Symbolic approach is $0.973\pm 0.009$ (Table 2); (2) Visual
explanations are marked as relevant on 21/30 instances. Of these, in 5/21
instances the inductive explanation is marked as being more useful than the
corresponding descriptive baseline (see Table 4); (3) Textual explanations are
marked as relevant on 18/30 instances. Of these, in 13/18 instances the
inductive explanation is marked as being more useful than that the
corresponding descriptive baseline (see Table 4); (4) Either one of visual or
textual explanation is marked as relevant in 29/30 instances. (See Table 3 for
details about the utility of each of the representations we provide.

Table 4: Conditional comparison of inductive explanations ($I$) and
descriptive baseline ($D$). ($X>Y$ means that $X$ is more useful than $Y$)

(a) Comparison given Visual Explanations (V) are relevant. | Count
---|---
$I>D$ | 5
$I<D$ | 8
$I=D$ | 8

(b) Comparison given Textual Explanations (T) are relevant. | Count
---|---
$I>D$ | 13
$I<D$ | 0
$I=D$ | 5

Table 5: Agreements between the model (M) and the radiologist (R) when the latter is sure R M | Agree | Disagree
---|---|---
Sure | 19 | 6

Table 6: Correct and Incorrect predictions of the model (M) when the radiologist (R) is unsure R M | Correct | Incorrect
---|---|---
Unsure | 4 | 1

[Explanations are Useful.] Either visual or textual explanations were
considered radiologically relevant in 29/30 instances. This suggests that it
could be useful to augment clinical diagnoses with such additional
information.

[Domain-Specific Representations are Important.] There seems to be a reversal
in preference from the descriptive baseline to the inductive explanation when
going from visual to textual explanations. This is against a backdrop of a
high frequency of preference for visual representations (21/30 instances). We
believe several factors to be involved here. First, radiological diagnosis is
largely image-based. This results in a natural preference for visual
representations. However, the fact that the baseline of a simple lung
segmentation is preferred over the saliency maps suggests that the latter do
not correspond in any meaningful way. This is not the case with textual
explanations that use radiologically meaningful features: hence the greater
preference for the inductive explanation over the tabulation of descriptive
statistics. Taken together, the results highlight the need to construct
explanations in clinically meaningful terms. This supports a finding by Arun
et al. (2020) that direct presentation of GradCAM visualisation may not be
‘trustworthy’, or relevant in a medical context.

[“Simpler” Explanations are Preferable.] We think the apparent preference for
visual baseline and textual inductive explanations over the visual inductive
explanation also indicate an underlying preference for simpler explanations.
The visual baseline is simply a delineation of the lungs; and the preferred
inductive textual explanation is a small set of conditions leading to the
diagnosis. In contrast, the saliency maps and tabulations of probabilities
contains significantly more detail, most of which is probably not thought to
be clinically relevant. While the lung-segmentation image does not constitute
any kind of explanation for the diagnosis of the model, it is not entirely
irrelevant, since radiologists do look at lung-appearance during diagnosis.

[Models Can Assist.] Our results in Tables 6 and 6 suggest that the model is
not simply a clone of the radiologist, and could be helpful in cases where the
diagnosis is not clear-cut. This opens up the possibility of using such
systems as a second opinion when making diagnoses.

##  4 Concluding Remarks

In this paper, we have examined the use of a hierarchical neural-symbolic
approach for diagnosis of COVID-19 from chest X-rays. Our findings suggest
that it is possible to construct hierarchical models with accuracies
comparable to end-to-end models, with additional benefits arising the ability
to construct visual and textual explanations using the neural and symbolic
stages of the approach. We have also presented some evidence of an assessment
of these explanations. Specifically, we find that while explanations are
relevant, they are better than a simple “baseline explanation” only for the
symbolic explanation that is a simple logical description using domain-
specific concepts. This does not mean visual explanations are not meaningful:
rather that the specific use of saliency maps is not useful.

A focus on explanations and keeping the clinician-in-the-loop is crucial for
deployment of models as clinical assistants, so that clinicians gain trust in
the decision of these machines, and possibly make better judgements. The
deployment of quick and reliable model-based tools is becoming increasingly
important in the context of COVID-19, as it threatens to overwhelm medical
practitioners in countries with limited medical expertise.

It has been repeatedly shown in machine learning, that accuracy of models
depends crucially on the representation used, and that the acceptance of
machine-learnt models depends crucially on whether the models are able to
capture meaningful mechanisms. Future work in this area needs to focus
therefore on the domain-specific features to identify automatically from
image-data, and how to develop convey the concepts identified to the
radiologists in a manner in which they can assess clinical significance. We
think this can only be achieved by a continuous dialogue between clinicians
and developers of machine-learning models.

### Acknowledgements

The authors would like to thank the radiologist from NHS, UK for helping us
carry out this project.

## References

  * Arrieta et al. (2019) Alejandro Barredo Arrieta, Natalia Díaz-Rodríguez, Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador García, Sergio Gil-López, Daniel Molina, Richard Benjamins, Raja Chatila, and Francisco Herrera.  Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai, 2019.
  * Arun et al. (2020) Nishanth Arun, Nathan Gaw, Praveer Singh, Ken Chang, Mehak Aggarwal, Bryan Chen, Katharina Hoebel, Sharut Gupta, Jay Patel, Mishka Gidwani, Julius Adebayo, Matthew D. Li, and Jayashree Kalpathy-Cramer.  Assessing the (un)trustworthiness of saliency maps for localizing abnormalities in medical imaging, 2020.
  * Asnaoui and Chawki (2020) Khalid El Asnaoui and Youness Chawki.  Using x-ray images and deep learning for automated detection of coronavirus disease.  _Journal of Biomolecular Structure and Dynamics_ , 0(0):1–12, 2020.  URL https://doi.org/10.1080/07391102.2020.1767212.
  * Ballard and Brown (1982) Dana Harry Ballard and Christopher M. Brown.  _Computer Vision_.  Prentice Hall Professional Technical Reference, 1st edition, 1982.  ISBN 0131653164.
  * Cohen et al. (2020) Joseph Paul Cohen, Paul Morrison, Lan Dao, Karsten Roth, Tim Q Duong, and Marzyeh Ghassemi.  Covid-19 image data collection: Prospective predictions are the future, 2020.
  * Gozes et al. (2020) Ophir Gozes, Maayan Frid-Adar, Hayit Greenspan, Patrick D. Browning, Huangqi Zhang, Wenbin Ji, Adam Bernheim, and Eliot Siegel.  Rapid ai development cycle for the coronavirus (covid-19) pandemic: Initial results for automated detection & patient monitoring using deep learning ct image analysis, 2020.
  * Jaeger et al. (2014) Stefan Jaeger, Sema Candemir, Sameer Antani, Yì-Xiáng Wáng, Pu-Xuan Lu, and George Thoma.  Two public chest x-ray datasets for computer-aided screening of pulmonary diseases.  _Quantitative imaging in medicine and surgery_ , 4:475–7, 12 2014.  10.3978/j.issn.2223-4292.2014.11.20.
  * Karim et al. (2020) Md. Rezaul Karim, Till Döhmen, Dietrich Rebholz-Schuhmann, Stefan Decker, Michael Cochez, and Oya Beyan.  Deepcovidexplainer: Explainable covid-19 diagnosis based on chest x-ray images, 2020.
  * Lipton (2016) Zachary Chase Lipton.  The mythos of model interpretability.  _CoRR_ , abs/1606.03490, 2016.  URL http://arxiv.org/abs/1606.03490.
  * Mangal et al. (2020) Arpan Mangal, Surya Kalia, Harish Rajgopal, Krithika Rangarajan, Vinay Namboodiri, Subhashis Banerjee, and Chetan Arora.  Covidaid: Covid-19 detection using chest x-ray, 2020.
  * Miller et al. (1982) Randolph A. Miller, Harry E. Pople, and Jack D. Myers.  Internist-i, an experimental computer-based diagnostic consultant for general internal medicine.  _New England Journal of Medicine_ , 307(8):468–476, 1982.  10.1056/NEJM198208193070803.  URL https://doi.org/10.1056/NEJM198208193070803.  PMID: 7048091.
  * Rajpurkar et al. (2017) Pranav Rajpurkar, Jeremy Irvin, Kaylie Zhu, Brandon Yang, Hershel Mehta, Tony Duan, Daisy Ding, Aarti Bagul, Curtis Langlotz, Katie Shpanskaya, Matthew P. Lungren, and Andrew Y. Ng.  Chexnet: Radiologist-level pneumonia detection on chest x-rays with deep learning, 2017.
  * Selvaraju et al. (2016) Ramprasaath R. Selvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra.  Grad-cam: Why did you say that? visual explanations from deep networks via gradient-based localization.  _CoRR_ , abs/1610.02391, 2016.  URL http://arxiv.org/abs/1610.02391.
  * Shortliffe and Buchanan (1975) Edward H. Shortliffe and Bruce G. Buchanan.  A model of inexact reasoning in medicine.  _Mathematical Biosciences_ , 23(3):351 – 379, 1975.  ISSN 0025-5564.  https://doi.org/10.1016/0025-5564(75)90047-4.  URL http://www.sciencedirect.com/science/article/pii/0025556475900474.
  * Toğaçar et al. (2020) Mesut Toğaçar, Burhan Ergen, and Zafer Cömert.  Covid-19 detection using deep learning models to exploit social mimic optimization and structured chest x-ray images using fuzzy color and stacking approaches.  _Computers in Biology and Medicine_ , 121:103805, 2020.  ISSN 0010-4825.  URL http://www.sciencedirect.com/science/article/pii/S0010482520301736.
  * Wang and Wong (2020) Linda Wang and Alexander Wong.  Covid-net: A tailored deep convolutional neural network design for detection of covid-19 cases from chest x-ray images, 2020.
  * Wang et al. (2017) Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald Summers.  Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.  _arXiv:1705.02315_ , 05 2017.

##  Appendix A COVIDr Dataset

The details of the COVIDr dataset are seen in Table 7. An example of the way
we parse the dataset is shown in Fig. 4.

Figure 4: Parsing the COVIDr dataset Table 7: The COVIDr dataset consists of 7 CXR finding labels for COVID-19 positive images. The number of positive instances of these labels are shown in the accompanying table.  CXR-Finding | Positive Instances
---|---
None | 44/245 (17.95%)
Ground glass opacity | 145/245 (59.18%)
Bilateral patchy air-space opacification | 30/245 (12.24%)
Bilateral symmetrical air-space opacification | 18/245 (7.34%)
Bilateral peripheral air-space opacification | 54/245 (22.04%)
Predominantly unilateral air-space opacification Rt | 36/245 (14.69%)
Predominantly unilateral air-space opacification Lt | 28/245 (11.4%)

##  Appendix B Model Details

(a) R-Model

(b) S-Model

Figure 5: Neural model architectures Table 8: Conversion of Neural Radiology Model output to Symbolic Tree input Max Prob. | ASO | GGO
---|---|---
ASO | 1 | 0
GGO | 0 | 1
ASO_GGO | 1 | 1
No_ASO_GGO | 0 | 0
Missing_ASO_GGO | ? | ?

The _R-_ and _S-Model_ architectures are shown in Fig. 5. Details of
conversion of the Neural Radiology Model ($R$-model) output to Symbolic Tree
($T$-model) input are shown in Table 8.

To check for the optimal maximum leaf nodes, we plot (Fig. 6) the test
accuracy against the number of leaf nodes. We also try to find the optimal
maximum depth of the tree, as shown in Fig. 6.

(a) Accuracy vs. Max. Leaf Nodes

(b) Accuracy vs. Max. Depth

Figure 6: Optimal Leaf Nodes and Depth Figure 7: Tree used to generate textual
inductive explanations

The tree obtained from the Symbolic model that is described in Section 1 is
shown in Fig. 7. The extracted rules are shown below.

Rules for COVID-Positive

  1. 1.

P(ASO) > 0.5

  2. 2.

P(ASO) <= 0.5
&& P(Missing GGO/ASO) <= 0.5
&& P(Infiltration) > 0.406
&& P(Emphysema) <= 0.122

  3. 3.

P(ASO) <= 0.5
&& P(Missing GGO/ASO) <= 0.5
&& P(Infiltration) <= 0.406
&& P(Emphysema) > 0.127
&& P(Edema) > 0.085

Rules for COVID-Negative

  1. 1.

P(ASO) <= 0.5
&& P(Missing GGO/ASO) <= 0.5

  2. 2.

P(ASO) <= 0.5
&& P(Missing GGO/ASO) <= 0.5
&& P(Infiltration) > 0.406
&& P(Emphysema)>0.122
&& P(Emphysema) <= 0.122

  3. 3.

P(ASO) <= 0.5
&& P(Missing GGO/ASO) <= 0.5
&& P(Infiltration) <= 0.406
&& P(Emphysema)>0.127
&& P(Edema) <= 0.085

  4. 4.

P(ASO) <= 0.5
&& P(Missing GGO/ASO) <= 0.5
&& P(Infiltration) <= 0.406
&& P(Emphysema) <= 0.127

Figure 8: Snippet of Interface that the Radiologist uses to evaluate
explanations and baselines

##  Appendix C Web-Based interface for collecting feedback

A practising radiologist from the NHS, UK provides utility assessments for 30
Chest X-ray images sampled from the held-out test set (COVID-19 positive - 5,
healthy - 5, tuberculosis - 5 and pneumonia - 5) , along with the COVID-19
diagnosis made by our model and all the explanations as stated in Section 2.3.
We provide a web-based interface and ask the following questions in the given
order :

  1. 1.

Prior to revealing the diagnosis of a given Chest X-ray image made by the
model (true label is never revealed) or the corresponding explanations, we ask
for the radiologist’s diagnosis. We then reveal the diagnosis made by the
model.

  2. 2.

We ask the radiologist to rate the visual quality of the image as Low, Medium
or High.

  3. 3.

The visual explanations(_VisInd_ , _VisDed_) provided by our model are then
displayed side by side along with the Chest X-ray. We then ask if each of
these explanations individually are _Useful_ , _Somewhat Useful_ or _Not
Useful_. We also ask whether the _VisInd_ explanations was more useful,
_VisDed_ explanations was more useful or if both are the same.

  4. 4.

The symbolic explanations(_SymInd_ , _SymDed_) provided by our model are
displayed side by side along with the Chest X-ray. We then ask if each of
these explanations individually are _Useful_ , _Somewhat Useful_ or _Not
Useful_. We also ask whether the _SymInd_ explanations was more useful,
_SymDed_ explanations was more useful or if both are the same.

  5. 5.

Finally, we ask which explanations were more useful - Visual, Symbolic or both
were the same.

Snippets of the web interface are shown in Fig. 8

##  Appendix D Additional Results

###  D.1 COVIDr Baselines

We benchmark the COVIDr dataset by training different variation to predict the
morphological symptoms. The results are shown in Table 9.

Table 9: Results on the Radiology Model. (Sym– Model using embeddings from the $S$-model. PT– VGG16 uses pre-trained weights from the end-to-end model) Model | Accuracy | AUC
---|---|---
VGG-16 | 0.83 | 0.96
VGG-16 + Sym | 0.86 | 0.97
VGG-16 + Sym (PT) | 0.88 | 0.99

###  D.2 Symbolic Model Baselines

The results of our symbolic model are shown in Table 10. We compare these
results with a single end-to-end, as well as other tree-based models. We find
that the loss in accuracy in our symbolic model is not significant in
comparison with the black box model, and the tree model additionally provides
interpretable explanations. We also see that our decision tree has very
similar predictive power as with other tree ensembling methods like _Random
Forest_ and _XGBOOST_.

Table 10: Results on the COVID-19 prediction Model | Accuracy | F1
---|---|---
End-to-End | $\textbf{0.985}\pm\textbf{0.007}$ | 0.95
NS-RF | $0.973\pm 0.009$ | 0.915
NS-XGB | $0.973\pm 0.009$ | 0.930
NS-DTree | $0.973\pm 0.009$ | 0.915


# The weakness of finding descending sequences in ill-founded linear orders

Jun Le Goh & Arno Pauly & Manlio Valenti

###### Abstract

We prove that the Weihrauch degree of the problem of finding a bad sequence in
a non-well quasi order ($\mathsf{BS}$) is strictly above that of finding a
descending sequence in an ill-founded linear order ($\mathsf{DS}$). This
corrects our mistaken claim in [2], which stated that they are Weihrauch
equivalent. We prove that König’s lemma $\mathsf{KL}$ is not Weihrauch
reducible to $\mathsf{DS}$ either, resolving the main open question raised in
[2].

00footnotetext: We are grateful to Takayuki Kihara for pointing out the
mistake in our previous article. We thank also Cécilia Pradic for comments
which greatly improved the presentation of this note.

For background and notation on Weihrauch reducibility, $\mathsf{DS}$,
$\mathsf{BS}$, etc., please refer to our previous article [2].

##  1 Separating $\mathsf{BS}$ and $\mathsf{DS}$

A key tool used in [2] is the notion of the first-order part of a problem. In
this section, we shall separate $\mathsf{BS}$ and $\mathsf{DS}$ by separating
their first-order parts.

######  Theorem 1.

${}^{1}(\mathsf{BS})\nleq_{\textrm{W}}{}^{1}(\mathsf{DS})$ and so
$\mathsf{DS}<_{\textrm{W}}\mathsf{BS}$.

This corrects our mistaken claim [2, Proposition 4.5] that $\mathsf{BS}$ and
$\mathsf{DS}$ are Weihrauch equivalent. Further results on the Weihrauch
degree of $\mathsf{BS}$ (and variants thereof) are in preparation.

Recall from [2, Theorem 4.10] that the first-order part ${}^{1}(\mathsf{DS})$
is Weihrauch equivalent to $\boldsymbol{\Pi}^{1}_{1}\mathrm{-Bound}$, which is
the problem of producing an upper bound for a finite subset of $\mathbb{N}$
(given via a $\Pi^{1}_{1}$ code). Observe that
$\boldsymbol{\Pi}^{1}_{1}\mathrm{-Bound}$ is upwards closed (i.e. if $n\in
g(x)$, then $m\in g(x)$ for all $m>n$).

######  Lemma 2.

Let $f$ be a problem with codomain $\mathbb{N}$. The following are equivalent:

  1. 1.

there exists an upwards closed problem $g$ with codomain $\mathbb{N}$ such
that $f\leq_{\textrm{W}}g$;

  2. 2.

there is a computable procedure which takes as input any
$x\in\operatorname{dom}(f)$ and produces a sequence
$p_{x}\in\mathbb{N}^{\mathbb{N}}$ of guesses for $f$-solutions to $x$ which is
correct cofinitely often.

###### Proof.

For $1.\Rightarrow 2.$, let $g$ be upwards closed and assume
$f\leq_{\textrm{W}}g$ via $\Phi$ and $\Psi$. Given
$x\in\operatorname{dom}(f)$, dovetail the computations
$(\Psi(x,m))_{m\in\mathbb{N}}$. Once some $\Psi(x,m)$ halts, we output its
result and cancel $\Psi(x,n)$ for all $n<m$.

For the converse direction, for every $x\in\operatorname{dom}(f)$, let
$p_{x}\in\mathbb{N}^{\mathbb{N}}$ be as in the hypothesis. Define
$M:=\max\\{m\mid p_{x}(m)\notin f(x)\\}$ and let $g(x):=\\{n\mid n>M\\}$.
Clearly $g$ is upwards closed. The fact that $f\leq_{\textrm{W}}g$ follows
from the fact that $x\mapsto p_{x}$ is computable. ∎

In light of Lemma 2, to prove Theorem 1 it suffices to show that one cannot
computably “guess” solutions for $\mathsf{BS}$. In other words, given a
computable procedure which tries to guess extendible elements in a non-wqo, we
want to construct a non-wqo $P$ on which the procedure outputs a non-
extendible element infinitely often. The non-wqos $P$ we construct will be
“tree-like” in the following sense:

######  Definition 3.

A _tree decomposition_ of a partial order $(P,<_{P})$ consists of a tree
$T\subseteq 2^{<\mathbb{N}}$ and a function $\iota:T\to P$ such that:

  1. 1.

$P$ is partitioned into finite $P$-intervals, where each interval has the form

$(wb]=\\{v\in P\mid\iota(w)<_{P}v\leq_{P}\iota(wb)\\}$

for some vertex $wb\in T$ (with final entry $b$), or
$(\varepsilon]=\\{\iota(\varepsilon)\\}$ (where $\varepsilon$ denotes the root
of $2^{<\mathbb{N}}$). For $v\in P$ let $\lceil v\rceil\in T$ be uniquely
defined by $v\in(\lceil v\rceil]$.

  2. 2.

If $w_{1},w_{2}\in T$ and $w_{1}$ is a proper prefix of $w_{2}$ (written
$w_{1}\sqsubset w_{2}$), then $\iota(w_{1})<_{P}\iota(w_{2})$.

  3. 3.

If $w_{1},w_{2}\in T$ are incompatible, so are $\iota(w_{1})$ and
$\iota(w_{2})$ (i.e. they have no common upper bound in $P$).

The following lemma is straightforward.

######  Lemma 4.

If $\iota:T\to P$ is a tree decomposition, then $P$ has no infinite descending
sequences. Moreover, $T$ is wqo (i.e. it has finite width) if and only if $P$
is wqo. In other words, $T$ has an infinite antichain iff so does $P$.

###### Proof.

The fact that every partial order that admits a tree decomposition does not
have an infinite descending sequence follows from the fact that if
($v_{n})_{n\in\mathbb{N}}$ is an infinite descending sequence in $P$, then
since every interval $(\lceil v_{n}\rceil]$ is finite, up to removing
duplicates, the sequence $(\lceil v_{n}\rceil)_{(}n\in\mathbb{N})$ would be an
infinite descending sequence in $T$.

If $(w_{n})_{n\in\mathbb{N}}$ is an infinite antichain in $T$ then, by
definition of tree decomposition, $(\iota(w_{n}))_{n\in\mathbb{N}}$ is an
infinite antichain in $P$. Conversely, if $(v_{n})_{n\in\mathbb{N}}$ is an
infinite antichain in $P$, then for every $n$, for all but finitely $m$,
$\lceil v_{n}\rceil$ is -incomparable with $\lceil v_{m}\rceil$. In
particular, we can obtain an infinite antichain in $T$ by choosing a
subsequence $(v_{n_{i}})_{i\in\mathbb{N}}$ such that, for every $i\neq j$,
$\lceil v_{n_{i}}\rceil$ and $\lceil v_{n_{j}}\rceil$ are -incomparable. ∎

######  Lemma 5.

There is no computable procedure that, given in input a partial order which
admits a tree decomposition, outputs a sequence of elements of that partial
order such that if the input is not wqo, then cofinitely many elements in the
output are extendible to a bad sequence.

We point out a subtle yet important aspect regarding Lemma 5: The procedure
only has access to the partial order, not to a tree decomposition of it.

###### Proof.

Fix a computable “guessing” procedure $g$ that receives as input a partial
order (admitting a tree decomposition) and outputs a sequence of elements in
that partial order. We shall build a partial order $P$ together with a tree
decomposition $\iota:T\to P$ in stages such that, infinitely often, $g$
outputs an element of $P$ that does not extend to an infinite bad sequence.

Start with $T_{0}=\\{\varepsilon\\}$ and $P_{0}$ having a single element
$v_{\varepsilon}$, with $\iota_{0}(\varepsilon)=v_{\varepsilon}$. In stage
$s$, we have built a finite tree decomposition $\iota_{s}:T_{s}\to P_{s}$ and
wish to extend it to some $\iota_{s+1}:T_{s+1}\to P_{s+1}$. The tree $T_{s+1}$
will always be obtained by giving each leaf in $T_{s}$ a single successor, and
then adding two successors to exactly one of the new leaves. To decide which
leaf gets two successors, say a finite extension $Q$ of $P_{s}$ is _suitable_
for $\iota_{s}:T_{s}\to P_{s}$ if for every $v\in Q\setminus P_{s}$, there is
exactly one leaf $w\in T_{s}$ such that $\iota_{s}(w)<_{Q}v$. Pick the left-
most leaf $\sigma$ of $T_{s}$ with the following property:

> There is some suitable extension $Q$ of $P_{s}$ such that, when given $Q$,
> the guessing procedure $g$ would guess an element of $Q$ which is comparable
> with $\iota_{s}(\sigma)$.

To see that such $\sigma$ must exist, consider extending $P_{s}$ by adding an
“infinite comb” (i.e. a copy of $\\{0^{n}1^{i}\mid
n\in\mathbb{N},i\in\\{0,1\\}\\}$) above the $\iota_{s}$-image of a single leaf
in $T_{s}$. The resulting partial order is non-wqo, admits a tree
decomposition (obtained by extending $T_{s}$ and $\iota_{s}$ in the obvious
way), and its finite approximations (extending $P_{s}$) are suitable for
$\iota_{s}$. Hence, by hypothesis, $g$ eventually guesses some element which
must be comparable with $\iota_{s}(\sigma)$, for some leaf $\sigma\in T_{s}$.

Having identified $\sigma$, we fix any corresponding suitable extension $Q$ of
$P_{s}$. In order to extend $\iota_{s}$, we further extend $Q$ to $Q^{\prime}$
by adding a new maximal element $v_{w}$ to $Q$ for each leaf $w\in T_{s}$ as
follows: $v_{w}$ lies above all $v\in Q\setminus P_{s}$ such that
$\iota_{s}(w)<_{P}v$, and is incomparable with all other elements (including
the other new maximal elements $v_{w^{\prime}}$). To extend $T_{s}$, we add a
new leaf $\tau\smash{\raisebox{3.87495pt}{$\smallfrown$}}0$ to $T_{s}$ for
each leaf $\tau$, obtaining a tree $T^{\prime}$. We extend $\iota_{s}$ to
yield a tree decomposition $\iota^{\prime}:T^{\prime}\to Q^{\prime}$ in the
obvious way.

Finally, we add two successors to
$\sigma\smash{\raisebox{3.87495pt}{$\smallfrown$}}0$ in $T^{\prime}$, i.e.,
define
$T_{s+1}=T^{\prime}\cup\\{\sigma\smash{\raisebox{3.87495pt}{$\smallfrown$}}00,\sigma\smash{\raisebox{3.87495pt}{$\smallfrown$}}01\\}$.
We also add two successors $v_{1}$, $v_{2}$ to
$\iota^{\prime}(\sigma\smash{\raisebox{3.87495pt}{$\smallfrown$}}0)$ in
$Q^{\prime}$ to obtain $P_{s+1}$, and extend $\iota^{\prime}$ to $\iota_{s+1}$
by setting
$\iota_{s+1}(\sigma\smash{\raisebox{3.87495pt}{$\smallfrown$}}0i)=v_{i}$. This
concludes stage $s$.

It is clear from the construction that $\iota:T\to P$ is a tree decomposition.
Let us discuss the shape of the tree $T$. In stage $s$, we introduced a
bifurcation above a leaf $\sigma_{s}$ of $T_{s}$. These are the only
bifurcations in $T$. Observe that, whenever $s^{\prime}<s$, $\sigma_{s}$ is
either above or to the right of $\sigma_{s^{\prime}}$, because every suitable
extension of $P_{s}$ is also a suitable extension of $P_{s^{\prime}}$ and, at
stage $s^{\prime}$, the chosen leaf was the left-most. Therefore $T$ has a
unique non-isolated infinite path $p=\lim_{s}\sigma_{s}$, and a vertex $w$ in
$T$ is extendible to an infinite antichain in $T$ if and only if it does not
belong to $p$.

We may now apply Lemma 4 to analyze $P$. First, since $T$ is not wqo, neither
is $P$. Second, we claim that if $v<_{P}\iota(\sigma)$ for some vertex
$\sigma$ on $p$, then $v$ is not extendible to an infinite bad sequence. To
prove this, suppose $v$ is extendible. Then so is $\iota(\sigma)$. The proof
of Lemma 4 implies that $\lceil\iota(\sigma)\rceil=\sigma$ is extendible to an
infinite antichain in $T$. So $\sigma$ cannot lie on $p$, proving our claim.

To complete the proof, observe that our construction of $\iota$ ensures that
for each $s$, $g(P)$ eventually outputs a guess which is below
$\iota(\sigma_{s}\smash{\raisebox{3.87495pt}{$\smallfrown$}}0)$. Whenever
$\sigma_{s}\smash{\raisebox{3.87495pt}{$\smallfrown$}}0$ lies along $p$ (which
holds for infinitely many $s$), this guess is wrong by the above claim. ∎

We may now complete the proof of Theorem 1.

###### Proof of Theorem 1.

Suppose towards a contradiction that
${}^{1}(\mathsf{BS})\leq_{\textrm{W}}\boldsymbol{\Pi}^{1}_{1}\mathrm{-Bound}$.
Since the problem of finding an element in a non-wqo which extends to an
infinite bad sequence is first-order, it is Weihrauch reducible to
$\boldsymbol{\Pi}^{1}_{1}\mathrm{-Bound}$ as well. Now
$\boldsymbol{\Pi}^{1}_{1}\mathrm{-Bound}$ is upwards closed, so there is a
computable guessing procedure for this problem (Lemma 2). However such a
procedure cannot exist, even for partial orders which admit a tree
decomposition (Lemma 5). ∎

##  2 Separating $\mathsf{KL}$ and $\mathsf{DS}$

In this section we shall prove $\mathsf{KL}\not\leq_{\textrm{W}}\mathsf{DS}$
(Corollary 7), providing a negative answer to [2, Question 6.1].

######  Theorem 6.

Let $f$ be a problem. The following are equivalent:

  1. 1.

$\widehat{\mathrm{ACC}_{\mathbb{N}}}\times f\leq_{\textrm{W}}\mathsf{DS}$

  2. 2.

$f\leq_{\textrm{W}}\mathsf{lim}$.

###### Proof.

The implication from (2) to (1) follows from
$\mathsf{lim}\leq_{\textrm{W}}\mathsf{DS}$ (as shown in [2, Theorem 4.16]).
For the other direction, we consider a name $x$ for an input to $f$ together
with witnesses $\Phi,\Psi$ for the reduction. We show that, from them, we can
uniformly compute an input $q$ to $\widehat{\mathrm{ACC}_{\mathbb{N}}}$
together with an enumeration of a set $W$ such that $W$ is the well-founded
part of the (ill-founded) linear order $L$ built by the forward functional
$\Phi$ on $(q,x)$. We can then use $\mathsf{lim}$ to obtain the characteristic
function of $W$. Having access to this lets us find an infinite descending
sequence in $L$ greedily by avoiding ever choosing an element of $W$. From
such a descending sequence the backward functional $\Psi$ then computes a
solution to $f$ for $x$.

It remains to construct $q=\langle q_{0},q_{1},\ldots\rangle$ and $W$ to
achieve the above. At the beginning, $W$ is empty, and we extend each $q_{i}$
in a way that removes no solution from its
$\mathsf{ACC}_{\mathbb{N}}$-instance. As we do so, for each $i\notin W$ (in
parallel), we monitor whether the following condition has occurred:

> $L$ (as computed by the finite prefix of $(q,x)$ built/observed thus far)
> contains $i$ and some (finite) descending sequence $\ell$ such that
>
>   1. 1.
>
> $\ell$ is $L$-above $i$ (i.e. $i<_{L}\min_{L}\ell$);
>
>   2. 2.
>
> the functional $\Psi$, upon reading the current prefix of $(q,x)$ and
> $\ell$, produces some output $m$ for the $i$-th
> $\mathsf{ACC}_{\mathbb{N}}$-instance.
>
>

Once the above occurs for $i$ (if ever), we remove $m$ as a valid solution to
$q_{i}$. This means that $\ell$ cannot be extendible to an infinite descending
sequence in $L$, so $i$ must be in the well-founded part of $L$. Hence we
shall enumerate $i$ into $W$. This completes our action for $i$, after which
we return to monitoring the above condition for numbers not in $W$. This
completes the construction.

It is clear that each $q_{i}$ is an $\mathsf{ACC}_{\mathbb{N}}$-instance (with
solution set $\mathbb{N}$ if the condition is never triggered, otherwise with
solution set $\mathbb{N}\setminus\\{m\\}$). Hence $L=\Phi(q,x)$ is an ill-
founded linear order. As argued above, $W$ is contained in the well-founded
part of $L$. Conversely, suppose $i$ lies in the well-founded part of $L$. Fix
an infinite descending sequence $r$ which lies above $i$. The backward
functional $\Psi$ will have to produce all $\mathsf{ACC}_{\mathbb{N}}$ answers
upon receiving $(q,x)$ and $r$, including an answer to $q_{i}$. This answer is
determined by finite prefixes only, and after having constructed a
sufficiently long prefix of $q$, some finite prefix $\ell$ of $r$ will trigger
the condition for $i$ (unless something else triggered it previously), which
ensures that $i$ gets placed into $W$. This shows that $W$ is exactly the
well-founded part of $L$, thereby concluding the proof. ∎

######  Corollary 7.

If $f$ is a parallelizable problem with
$\mathsf{ACC}_{\mathbb{N}}\leq_{\textrm{W}}f\leq_{\textrm{W}}\mathsf{DS}$,
then $f\leq_{\textrm{W}}\mathsf{lim}$. In particular,
$\mathsf{KL}\nleq_{\textrm{W}}\mathsf{DS}$.

###### Proof.

Since
$\mathsf{ACC}_{\mathbb{N}}\leq_{\textrm{W}}f\leq_{\textrm{W}}\mathsf{DS}$ and
$f$ is parallelizable, we have $\widehat{\mathsf{ACC}_{\mathbb{N}}}\times
f\leq_{\textrm{W}}f\leq_{\textrm{W}}\mathsf{DS}$. By the previous theorem,
$f\leq_{\textrm{W}}\mathsf{lim}$. We conclude that
$\mathsf{KL}\nleq_{\textrm{W}}\mathsf{DS}$ because
$\mathsf{ACC}_{\mathbb{N}}\leq_{\textrm{W}}\mathsf{KL}$ and $\mathsf{KL}$ is
parallelizable, yet $\mathsf{KL}\nleq_{\textrm{W}}\mathsf{lim}$. ∎

## References

  * [1]
  * [2] Jun Le Goh, Arno Pauly & Manlio Valenti (2021): _Finding descending sequences through ill-founded linear orders_.  Journal of Symbolic Logic 86(2), 10.1017/jsl.2021.15.