# Approximation by Lexicographically Maximal Solutions
in Matching and Matroid Intersection Problems

Kristóf Bérczi MTA-ELTE Momentum Matroid Optimization Research Group and MTA-
ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd
University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>Tamás Király11footnotemark: 1 Yutaro
Yamaguchi Department of Information and Physical Sciences, Graduate School of
Information Science and Technology, Osaka University, Osaka, Japan. Email:
<EMAIL_ADDRESS>Yu Yokoi Principles of Informatics Research
Division, National Institute of Informatics, Tokyo, Japan. Email:
<EMAIL_ADDRESS>
###### Abstract

We study how good a lexicographically maximal solution is in the weighted
matching and matroid intersection problems. A solution is lexicographically
maximal if it takes as many heaviest elements as possible, and subject to
this, it takes as many second heaviest elements as possible, and so on. If the
distinct weight values are sufficiently dispersed, e.g., the minimum ratio of
two distinct weight values is at least the ground set size, then the
lexicographical maximality and the usual weighted optimality are equivalent.
We show that the threshold of the ratio for this equivalence to hold is
exactly $2$. Furthermore, we prove that if the ratio is less than $2$, say
$\alpha$, then a lexicographically maximal solution achieves
$(\alpha/2)$-approximation, and this bound is tight.

Keywords: Matching, Matroid intersection, Lexicographical maximality,
Approximation ratio

##  1 Introduction

Matching in bipartite graphs is one of the fundamental topics in combinatorics
and optimization. Due to its diverse applications, various optimality criteria
of matchings have been proposed based on the number of edges, the total weight
of edges, etc. The concept of _rank maximality_ is one of them, which is
especially studied in the context of matching problems under preferences [2,
7]. In this setting, we are given a partition $\\{E_{1},E_{2},\dots,E_{k}\\}$
of the edge set $E$ that represents a priority order, and a matching
$M\subseteq E$ is _rank-maximal_ if $|M\cap E_{1}|$ is maximized, and subject
to this, $|M\cap E_{2}|$ is maximized, and so on. As pointed out in several
papers [2, 7, 4, 1] (on generalized problems), the problem of finding a rank-
maximal solution can be reduced to the usual weight-maximization setting by
using sufficiently dispersed weights, e.g., by assigning $|E|^{k-i}$ for each
element in $E_{i}$.

In this paper, we explore the relation between rank-maximality and optimality
in the weighted setting for two generalizations of bipartite matching:
matching in general graphs and matroid intersection. To avoid confusion, we
hereafter replace the term “rank” with “lex(icographical)” because we also
deal with ranks in matroids. The main results of the paper (Theorems 2.1 and
2.2) state that, in both problems, the equivalence between lex-maximality and
weighted optimality holds if the minimum ratio of two distinct weight values
is larger than $2$. This implies that we can choose the base of exponential
weights as any constant larger than $2$ (instead of $|E|$) in the
aforementioned reduction. Furthermore, we show that if the minimum ratio is at
most $2$, say $\alpha$, then a lex-maximal solution achieves
$(\alpha/2)$-approximation of the maximum weight, and this bound is tight.

##  2 Results

We assume the basic notation and terminology on graphs and matroids (see,
e.g., [8]).

Throughout the paper, let $E$ be a finite ground set and $w\colon
E\to{\mathbb{R}}_{>0}$ be a positive weight function on $E$. For a subset
$X\subseteq E$, the weight $w(X)$ is defined as the sum of its elements. Let
$w_{1},w_{2},\dots,w_{k}$ be the distinct values of $w$ in descending order.
We assume $k\geq 2$ (otherwise, the results are trivial), and define

$\alpha_{w}\coloneqq\min_{1\leq i\leq k-1}\frac{w_{i}}{w_{i+1}}.$

For a subset $X\subseteq E$ and $1\leq i\leq k$, we denote by $X_{i}=\\{\,e\in
X\mid w(e)=w_{i}\,\\}$ the restriction of $X$ to the elements of weight
$w_{i}$, and define $X_{\leq i}\coloneqq\bigcup_{j\leq i}X_{j}$ and
accordingly $X_{\geq i}$, $X_{<i}$, and $X_{>i}$. For two subsets
$X,Y\subseteq E$, we say that $X$ is _lex-larger_ than $Y$ (or $Y$ is _lex-
smaller_ than $X$) if there exists an index $i$ such that $|X_{j}|=|Y_{j}|$
for any $j<i$ and $|X_{i}|>|Y_{i}|$. For a family ${\mathcal{F}}\subseteq
2^{E}$ of subsets of $E$, we say that $X\in{\mathcal{F}}$ is _lex-maximal_ if
no $Y\in{\mathcal{F}}$ is lex-larger than $X$. Note that a lex-maximal subset
$X\in{\mathcal{F}}$ may not be unique but the sequence
$|X_{1}|,|X_{2}|,\dots,|X_{k}|$ is unique.

A _weighted matching instance_ consists of an undirected graph $G=(V,E)$ and a
weight function $w$ on the edge set. We denote by ${\mathrm{opt}}(G,w)$ the
optimal value, i.e., the maximum weight of a matching in $G$. In addition, we
denote by ${\mathrm{lexopt}}(G,w)$ the weight of a lex-maximal matching in $G$
(where ${\mathcal{F}}$ is the family of matchings in $G$), which takes as many
edges of weight $w_{1}$ as possible, and subject to this, takes as many edges
of weight $w_{2}$ as possible, and so on.

A _weighted matroid intersection instance_ consists of two matroids
${\mathbf{M}}_{1}=(E,{\mathcal{I}}_{1})$ and
${\mathbf{M}}_{2}=(E,{\mathcal{I}}_{2})$ and a weight function $w$ on the
common ground set. We denote by
${\mathrm{opt}}({\mathbf{M}}_{1},{\mathbf{M}}_{2},w)$ the optimal value, i.e.,
the maximum weight of a common independent set in
${\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$. In addition, we denote by
${\mathrm{lexopt}}({\mathbf{M}}_{1},{\mathbf{M}}_{2},w)$ the weight of a lex-
maximal common independent set (where
${\mathcal{F}}={\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$), which takes as many
elements of weight $w_{1}$ as possible, and subject to this, takes as many
elements of weight $w_{2}$ as possible, and so on.

The main theorems are stated as follows.

######  Theorem 2.1.

Let $(G,w)$ be a weighted matching instance. If $\alpha_{w}\leq 2$, then

${\mathrm{lexopt}}(G,w)\geq\frac{\alpha_{w}}{2}\cdot{\mathrm{opt}}(G,w).$

If $\alpha_{w}>2$, then a lex-maximal matching is a maximum-weight matching,
and vice versa.

######  Theorem 2.2.

Let $({\mathbf{M}}_{1},{\mathbf{M}}_{2},w)$ be a weighted matroid intersection
instance. If $\alpha_{w}\leq 2$, then

${\mathrm{lexopt}}({\mathbf{M}}_{1},{\mathbf{M}}_{2},w)\geq\frac{\alpha_{w}}{2}\cdot{\mathrm{opt}}({\mathbf{M}}_{1},{\mathbf{M}}_{2},w).$

If $\alpha_{w}>2$, then a lex-maximal common independent set is a maximum-
weight common independent set, and vice versa.

We remark that the approximation ratio is tight as the weighted bipartite
matching problem is included as a common special case. Let $G=(V,E)$ be a
bipartite graph with $V=\\{1,2,3,4\\}$ and
$E=\\{\,e_{1}=\\{1,3\\},\,e_{2}=\\{2,3\\},\,e_{3}=\\{2,4\\}\,\\}$. Define
$w(e_{1})=1$, $w(e_{2})=x\in(1,2]$, and $w(e_{3})=1$. We then have
$\alpha_{w}=x$ (as $w_{1}=x$ and $w_{2}=1$), ${\mathrm{opt}}(G,w)=2$, and
${\mathrm{lexopt}}(G,w)=x$. We also remark that, when $x=2$, there are two
maximum-weight matchings $\\{e_{2}\\}$ and $\\{e_{1},e_{3}\\}$; the former is
lex-maximal whereas the latter is not. This means that “and vice versa” is not
true when $\alpha_{w}=2$ in both theorems.

##  3 Proofs

We prove both theorems using the same strategy. The key definition and lemmas
are as follows.

######  Definition 3.1.

Let $X\subseteq E$ be a feasible solution that is not lex-maximal in a
weighted matching or matroid intersection instance, and $i$ be the smallest
index such that $X_{\leq i}$ is not lex-maximal in the restricted instance
whose ground set is $E_{\leq i}$. We say that a feasible solution $Y\subseteq
E$ in the original instance is _eligible_ if the following three conditions
are satisfied:

  * •

$|Y_{j}|=|X_{j}|$ for any $j<i$,

  * •

$|Y_{i}|=|X_{i}|+1$, and

  * •

$|X_{>i}\setminus Y_{>i}|\leq 2$.

Intuitively, an eligible solution lexicographically improves the original
solution at the most significant improvable class by sacrificing at most two
lighter elements.

######  Lemma 3.2.

For any weighted matching instance $(G,w)$ and any matching $X$ that is not
lex-maximal, there exists an eligible matching $Y$.

######  Lemma 3.3.

For any weighted matroid intersection instance
$({\mathbf{M}}_{1},{\mathbf{M}}_{2},w)$ and any common independent set $X$
that is not lex-maximal, there exists an eligible common independent set $Y$.

We here prove Theorems 2.1 and 2.2 using Lemmas 3.2 and 3.3, whose proofs are
provided later.

###### Proof of Theorems 2.1 and 2.2.

Let $X^{*}$ be an optimal solution. Starting with $X=X^{*}$, we repeatedly
update $X$ to an eligible $Y$ until it becomes lex-maximal. Let $Y^{*}$ be the
lex-maximal solution that is finally obtained.

In any update from $X$ to $Y$, we have

$w(Y)=w(Y_{\leq i})+w(Y_{>i})\geq w(X_{\leq i})+w_{i}+w(X_{>i})-2w_{i+1}\geq
w(X)-\frac{2-\alpha_{w}}{\alpha_{w}}\cdot w_{i}.$

If $\alpha_{w}>2$, then we have $w(Y)>w(X)$, which cannot happen at the
beginning when $X=X^{*}$. Thus, $X^{*}$ is lex-maximal. As any lex-maximal
solution has the same weight, we also see that any lex-maximal solution is
optimal, and we are done with the second statements.

Suppose that $\alpha_{w}\leq 2$. Since we always have
$|Y_{j}|=|X_{j}|=|Y_{j}^{*}|$ $(j<i)$ and $|Y_{i}|=|X_{i}|+1\leq|Y_{i}^{*}|$,
we see that $i$ is nondecreasing during the process and each $w_{i}$ appears
on the right-hand side at most $|Y_{i}^{*}|$ times in total. Thus, by
repeating the above inequalities, we obtain

$w(Y^{*})\geq
w(X^{*})-\frac{2-\alpha_{w}}{\alpha_{w}}\sum_{i=1}^{k}(w_{i}\cdot|Y_{i}^{*}|)=w(X^{*})-\frac{2-\alpha_{w}}{\alpha_{w}}\cdot
w(Y^{*}),$

which implies the first statements. ∎

###  3.1 Matching: Proof of Lemma 3.2

We prove Lemma 3.2 by contradiction. Suppose to the contrary that there exists
a counterexample, and take a minimal one in the following sense. First, the
ground set $E$ is minimized as the first priority, and subject to this, a
counterexample matching $X$ (that is not lex-maximal but admits no eligible
matching $Y$) and a lex-maximal matching $Z$ are taken so that the symmetric
difference $X\triangle Z=(X\setminus Z)\cup(Z\setminus X)$ is minimized.

By the minimality, we have $E=X\cup Z=X\triangle Z$. Indeed, if there exists
an edge $e\in E\setminus(X\cup Z)$, then we obtain a smaller counterexample by
removing $e$ (no eligible matching can newly appear), a contradiction.
Similarly, if there exists $e\in X\cap Z$, then we obtain a smaller
counterexample again by removing $e$ (note that no edge is adjacent to $e$ as
$X$ and $Z$ are matchings), a contradiction.

######  Claim 3.4.

There are no adjacent edges of the heaviest weight.

###### Proof.

Suppose to the contrary that $e_{1}=\\{v,u_{1}\\}\in X$ and
$e_{2}=\\{v,u_{2}\\}\in Z$ are adjacent (at $v$) and
$w(e_{1})=w(e_{2})=w_{1}$. If $u_{1}=u_{2}$ (i.e., $e_{1}$ and $e_{2}$ are
parallel), then $X^{\prime}=(X\setminus\\{e_{1}\\})\cup\\{e_{2}\\}$ is a
smaller counterexample, a contradiction. Otherwise, consider the instance
obtained by contracting the two edges $e_{1}$ and $e_{2}$, i.e., by merging
$u_{1}$ and $u_{2}$ into a single vertex, removing the vertex $v$ together
with the incident edges, and restricting the weight function to the remaining
set of edges.

As $X$ is a matching that is not lex-maximal, this is true for
$X^{\prime}=X\setminus\\{e_{1}\\}$ after the contraction. By the minimality of
the counterexample, there exists an eligible matching $Y^{\prime}\subseteq
E\setminus\\{e_{1},e_{2}\\}$. Since at most one of $u_{1}$ and $u_{2}$ is
matched by $Y^{\prime}$ in the original graph, we can add $e_{1}$ or $e_{2}$
to $Y^{\prime}$ to obtain a matching $Y$ in the original instance. Moreover,
the $Y$ thus obtained is eligible by definition even if $e_{2}$ is added since
$e_{1}\in X_{\leq i}$ for any $i\geq 1$, contradicting our indirect
assumption. ∎

######  Claim 3.5.

$X_{1}=\emptyset$.

###### Proof.

Suppose to the contrary that there exists an edge $e\in X_{1}$. Then, by Claim
3.4, we have $w(f)<w(e)=w_{1}$ for each adjacent edge $f\in Z$. Thus, we can
obtain a lex-larger matching $Z^{\prime}$ from $Z$ by adding $e$ and by
removing all the (at most two) adjacent edges, a contradiction. ∎

By Claim 3.5, we have $|X_{1}|=0<|Z_{1}|$. Let $f\in Z$ be an edge with
$w(f)=w_{1}$. Then, we can obtain an eligible matching $Y$ from $X$ by adding
$f$ and by removing all the (at most two) adjacent edges, a contradiction.
This concludes the proof of the lemma.

######  Remark 1.

We could give algorithmic proofs, e.g., what is similar to the matroid
intersection case given in the next section, or what is based on the property
of lex-maximal matchings that any lex-maximal matching in $E_{<i}$ can be
augmented to some lex-maximal matching in $E_{\leq i}$ along alternating paths
(which is implicitly observed and utilized in the algorithm in [2]) as
follows.

Let $X$ be a matching that is not lex-maximal, $Y$ be a lex-maximal matching,
and $i$ be the smallest index in Definition 3.1. Since both $X_{<i}$ and
$Y_{<i}$ are lex-maximal in $E_{<i}$, each connected component of
$X_{<i}\triangle Y_{<i}$ is an alternating path/cycle which contains the same
number of edges in $X_{j}$ and in $Y_{j}$ for every $j<i$ (otherwise, by
flipping edges along it, one is made a lex-larger matching in $E_{<i}$, a
contradiction). In particular, all of such paths are of even length.

Let us consider $X_{\leq i}\triangle Y_{\leq i}$. Since $Y_{\leq i}$ is lex-
maximal in $E_{\leq i}$ but $X_{\leq i}$ is not, there exists an alternating
path/cycle which contains strictly more edges in $Y_{i}$ than edges in
$X_{i}$. Such an alternating path/cycle must be obtained by connecting edges
in $X_{i}$ and in $Y_{i}$ alternately with even-length (possibly zero-length)
alternating paths in $X_{<i}\triangle Y_{<i}$ between them; hence, the number
of edges in $Y_{i}$ is larger than that of edges in $X_{i}$ by exactly one and
it cannot be a cycle. Thus, there exists an alternating path $P$ in $X_{\leq
i}\triangle Y_{\leq i}$ such that $|P\cap Y_{i}|=|P\cap X_{i}|+1$ and $|P\cap
Y_{j}|=|P\cap X_{j}|$ for every $j<i$. By flipping the edges of $X_{\leq i}$
along $P$ and removing at most two edges in $X_{>i}$ incident to the end
vertices of $P$, we obtain an eligible matching.

###  3.2 Matroid Intersection: Proof of Lemma 3.3

The proof relies on (the correctness of) an augmenting path algorithm for the
weighted matroid intersection problem, which was first described in [6]. We
first review the basic facts based on [8, Sections 41.2 and 41.3].

Let $({\mathbf{M}}_{1},{\mathbf{M}}_{2},w)$ be a weighted matroid intersection
instance. For each matroid ${\mathbf{M}}_{i}$ $(i\in\\{1,2\\})$, we denote the
independent set family, the rank function, and the span function111This is
also called the closure function; we follow the terminology of [8] for
simplicity. by ${\mathcal{I}}_{i}\subseteq 2^{E}$, $r_{i}\colon
2^{E}\to{\mathbb{Z}}_{\geq 0}$, and ${\mathrm{span}}_{i}\colon 2^{E}\to
2^{E}$, respectively. For a set $X$ and elements $x\in X$ and $y\not\in X$, we
write $X\setminus\\{x\\}$ and $X\cup\\{y\\}$ as $X-x$ and $X+y$, respectively.

Let $I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ be a common independent set.
The _exchangeability graph_ with respect to $I$ is a directed bipartite graph
$D=(E\setminus I,I;A)$ defined as follows. Let $A\coloneqq A_{1}\cup A_{2}$,
where

$\displaystyle A_{1}\coloneqq$ $\displaystyle\ \\{\,(y,x)\mid x\in E\setminus
I,~{}y\in I,~{}I+x-y\in{\mathcal{I}}_{1}\,\\},$ $\displaystyle A_{2}\coloneqq$
$\displaystyle\ \\{\,(x,y)\mid x\in E\setminus I,~{}y\in
I,~{}I+x-y\in{\mathcal{I}}_{2}\,\\}.$

We also define

$\displaystyle S$ $\displaystyle\coloneqq\\{\,s\in E\setminus I\mid
I+s\in{\mathcal{I}}_{1}\,\\},$ $\displaystyle T$
$\displaystyle\coloneqq\\{\,t\in E\setminus I\mid
I+t\in{\mathcal{I}}_{2}\,\\},$

where the elements in $S$ and in $T$ are called _sources_ and _sinks_ ,
respectively. Note that $A_{1}$ and $S$ depend only on ${\mathbf{M}}_{1}$, and
$A_{2}$ and $T$ depend only on ${\mathbf{M}}_{2}$. Let $c\colon
E\to{\mathbb{R}}$ be a cost function on the vertex set defined as follows:

$\displaystyle c(e)$ $\displaystyle\coloneqq\begin{cases}w(e)&(e\in I),\\\
-w(e)&(e\in E\setminus I).\end{cases}$ (3.1)

An $S$–$T$ path $P$ in $D$ is _cheapest_ if the total cost of its vertices is
minimized. Subject to this, $P$ is _shortest_ if the number of its vertices is
minimized.

For a nonnegative integer $\ell$, a common independent set
$I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ is said to be _$\ell$ -extreme_
if $w(I)$ is maximized subject to $I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$
and $|I|=\ell$. The following lemma leads to a simple augmenting path
algorithm for the weighted matroid intersection problem. The key is that one
can augment any $\ell$-extreme solution to some $(\ell+1)$-extreme solution
(if exists) by simply exchanging elements along a path.

######  Lemma 3.6 (cf. [8, Theorems 41.3, 41.5, and 41.6]).

Let $I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ be an $\ell$-extreme common
independent set, and suppose that there exists a common independent set
$J\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ with $|J|>|I|$. Then, $D$
contains an $S$–$T$ path, which may consist of a single vertex in $S\cap T$.
Let $P$ be a shortest cheapest $S$–$T$ path222Actually, $P$ does not need to
be shortest but it suffices that $P$ does not admit any shortcut. in $D$ with
respect to the cost function $c$ defined as (3.1). Then, no inner vertex of
$P$ is a source or a sink, and $I\triangle P$ is an $(\ell+1)$-extreme common
independent set.

Now we start the proof of Lemma 3.3. Let
$X\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ be a common independent set that
is not lex-maximal, and let $i$ be the smallest index such that $X_{\leq i}$
is not lex-maximal in the restricted instance whose ground set is $E_{\leq
i}$.

######  Claim 3.7.

There exists a common independent set $Y^{\prime}\subseteq E_{\leq i}$ such
that $|Y^{\prime}_{j}|=|X_{j}|$ for any $j<i$, $|Y^{\prime}_{i}|=|X_{i}|+1$,
${\mathrm{span}}_{1}(X_{\leq i})\subseteq{\mathrm{span}}_{1}(Y^{\prime})$, and
${\mathrm{span}}_{2}(X_{\leq i})\subseteq{\mathrm{span}}_{2}(Y^{\prime})$.

###### Proof.

Define an auxiliary weight function $w^{\prime}\colon E_{\leq
i}\to{\mathbb{R}}_{>0}$ by $w^{\prime}(e)\coloneqq n^{i-j}$ for each $e\in
E_{j}$ $(j=1,2,\dots,i)$, where $n=|E_{\leq i}|$. As remarked in the
introduction, the lexicographical order coincides with the weighted order,
i.e., for any two subsets $Z,Z^{\prime}\subseteq E_{\leq i}$, $Z$ is lex-
larger than $Z^{\prime}$ if and only if
$w^{\prime}(Z)>w^{\prime}(Z^{\prime})$.

Let $\ell\coloneqq|X_{\leq i}|$. Then, $X_{\leq i}$ is $\ell$-extreme in the
restricted instance $({\mathbf{M}}_{1}|E_{\leq i},{\mathbf{M}}_{2}|E_{\leq
i},w^{\prime})$, which has a larger common independent set. By Lemma 3.6, one
can obtain an $(\ell+1)$-extreme common independent set $Y^{\prime}\subseteq
E_{\leq i}$ by flipping $X_{\leq i}$ along a source-sink path $P$ in the
exchangeability graph. Note that $|Y^{\prime}_{j}|=|X_{j}|$ for any $j<i$ and
$|Y^{\prime}_{i}|=|X_{i}|+1$ by the choice of $i$ and the definition of
$w^{\prime}$.

If $P$ consists of a single vertex (which is a source and a sink), then the
claim immediately follows since $Y^{\prime}=X_{\leq i}+y$ for some element
$y\in E_{i}$. Otherwise, let $s$ and $t$ be the first and last vertices of
$P$, respectively. By the definitions of the exchangeability graph and the
sources and sinks, $y\in{\mathrm{span}}_{1}(X_{\leq
i})\subseteq{\mathrm{span}}_{1}(X_{\leq i}+s)$ for every $y\in P-s$ and
$y\in{\mathrm{span}}_{2}(X_{\leq i})\subseteq{\mathrm{span}}_{2}(X_{\leq
i}+t)$ for every $y\in P-t$ (recall that any $y\in P-s$ is not a source and
any $y\in P-t$ is not a sink). Hence, we have ${\mathrm{span}}_{1}(X_{\leq
i}\cup P)={\mathrm{span}}_{1}(X_{\leq i}+s)$ and ${\mathrm{span}}_{2}(X_{\leq
i}\cup P)={\mathrm{span}}_{2}(X_{\leq i}+t)$, and then

$\displaystyle\ell+1$ $\displaystyle=|Y^{\prime}|=r_{1}(Y^{\prime})\leq
r_{1}(X_{\leq i}\cup P)=r_{1}(X_{\leq i}+s)\leq r_{1}(X_{\leq
i})+r_{1}(s)=|X_{\leq i}|+1=\ell+1,$ $\displaystyle\ell+1$
$\displaystyle=|Y^{\prime}|=r_{2}(Y^{\prime})\leq r_{2}(X_{\leq i}\cup
P)=r_{2}(X_{\leq i}+t)\leq r_{2}(X_{\leq i})+r_{2}(t)=|X_{\leq i}|+1=\ell+1,$

which implies that the equality holds everywhere. Thus we have
${\mathrm{span}}_{1}(Y^{\prime})={\mathrm{span}}_{1}(X_{\leq
i}+s)\supseteq{\mathrm{span}}_{1}(X_{\leq i})$ and
${\mathrm{span}}_{2}(Y^{\prime})={\mathrm{span}}_{2}(X_{\leq
i}+t)\supseteq{\mathrm{span}}_{2}(X_{\leq i})$, which completes the proof. ∎

Take a subset $Y^{\prime}\subseteq E_{\leq i}$ satisfying the conditions in
Claim 3.7. We then obtain an eligible common independent set $Y\subseteq E$
from $Y^{\prime}\cup X_{>i}$ by removing at most two elements in $X_{>i}$ as
follows. If $r_{1}(Y^{\prime}\cup X_{>i})=r_{2}(Y^{\prime}\cup X_{>i})=|X|+1$,
then $Y^{\prime}\cup X_{>i}\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and we
do not need to remove any element. Suppose that $r_{1}(Y^{\prime}\cup
X_{>i})<|X|+1$. As ${\mathrm{span}}_{1}(X_{\leq
i})\subseteq{\mathrm{span}}_{1}(Y^{\prime})$, we have $r_{1}(Y^{\prime}\cup
X_{>i})\geq r_{1}(X)=|X|$, and hence $r_{1}(Y^{\prime}\cup X_{>i})=|X|$. This
implies that $Y^{\prime}\cup X_{>i}$ contains exactly one circuit of
${\mathbf{M}}_{1}$, which must intersect $X_{>i}$ since
$Y^{\prime}\in{\mathcal{I}}_{1}$. Hence, there exists an element $x\in X_{>i}$
such that $Y^{\prime}\cup(X_{>i}-x)\in{\mathcal{I}}_{1}$. The same holds for
${\mathbf{M}}_{2}$. Thus we obtain a common independent set $Y\subseteq
Y^{\prime}\cup X_{>i}$ with $|X_{>i}\setminus Y_{>i}|\leq 2$, which is
eligible.

##  4 Concluding Remarks

In this paper, we have analyzed how good a lex-maximal solution is in the
weighted matching and matroid intersection problems based on how dispersed the
distinct weight values are. It is well-known that, subject to a single
matroid, a lex-maximal solution is always optimal, which can be found by a
greedy algorithm. For more general independence systems, Jenkyns [3] and Korte
and Hausmann [5] independently analyzed the worst-case approximation ratio of
a greedy algorithm. In particular, the worst ratio is $2$ in the weighted
matching and matroid intersection problems, while a lex-maximal solution
(which is a possible output of a greedy algorithm) always achieves the maximum
weight if the distinct weight values are sufficiently dispersed. From this
perspective, we have filled the gap between these two situations.

A natural question is as follows: what about a further (common)
generalization, e.g., the weighted matroid parity problem? We just remark that
it seems difficult to extend our algorithmic proof straightforwardly bacause
no counterpart of augmentation from any $\ell$-extreme solution to some
$(\ell+1)$-extreme solution along a path (Lemma 3.6) is known. A minimal
counterexample proof (like the matching case) also seems nontrivial; in
particular, we have found no counterpart of Claim 3.4.

## Acknowledgments

We are grateful to Naoyuki Kamiyama for providing comments on a literature on
rank-maximal matchings. We appreciate the anonymous reviewer’s careful reading
and helpful comments. In particular, the alternative proof of Lemma 3.2 based
on the augmentation property of rank-maximal matchings came from their
comment.

Kristóf Bérczi was supported by the Lendület Programme of the Hungarian
Academy of Sciences – grant number LP2021-1/2021 and by the Hungarian National
Research, Development and Innovation Office – NKFIH, grant number FK128673.
Tamás Király was supported by the Hungarian National Research, Development and
Innovation Office – NKFIH, grant number K120254. Yutaro Yamaguchi was
supported by JSPS KAKENHI Grant Numbers JP20K19743 and JP20H00605 and by
Overseas Research Program in Graduate School of Information Science and
Technology, Osaka University. Yu Yokoi was supported by JSPS KAKENHI Grant
Number JP18K18004 and JST, PRESTO Grant Number JPMJPR212B.

“Application Domain Specific Highly Reliable IT Solutions” project has been
implemented with the support provided from the National Research, Development
and Innovation Fund of Hungary, financed under the Thematic Excellence
Programme TKP2020-NKA-06 (National Challenges Subprogramme) funding scheme.

## References

  * [1] C.-C. Huang, N. Kakimura, and N. Kamiyama.  Exact and approximation algorithms for weighted matroid intersection.  Mathematical Programming, 177(1-2):85–112, 2019.
  * [2] R. W. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. E. Paluch.  Rank-maximal matchings.  ACM Transactions on Algorithms (TALG), 2(4):602–610, 2006.
  * [3] T. A. Jenkyns.  The efficacy of the “greedy” algorithm.  In Proceedings of the 7th Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 341–350, 1976.
  * [4] N. Kamiyama.  Matroid intersection with priority constraints.  Journal of the Operations Research Society of Japan, 56(1):15–25, 2013.
  * [5] B. Korte and D. Hausmann.  An analysis of the greedy heuristic for independence systems.  In Annals of Discrete Mathematics, volume 2, pages 65–74. Elsevier, 1978.
  * [6] E. L. Lawler.  Matroid intersection algorithms.  Mathematical Programming, 9(1):31–56, 1975.
  * [7] D. Michail.  Reducing rank-maximal to maximum weight matching.  Theoretical Computer Science, 389(1-2):125–132, 2007.
  * [8] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, 2003.


# SDOH-NLI: a Dataset for Inferring Social Determinants
of Health from Clinical Notes

Adam D. Lelkes1, Eric Loreaux2, Tal Schuster1, Ming-Jun Chen1, Alvin
Rajkomar1‡

1Google Research, 2Curai Health  Corresponding author<EMAIL_ADDRESS>Work
completed at Google. Equal leadership.

###### Abstract

Social and behavioral determinants of health (SDOH) play a significant role in
shaping health outcomes, and extracting these determinants from clinical notes
is a first step to help healthcare providers systematically identify
opportunities to provide appropriate care and address disparities. Progress on
using NLP methods for this task has been hindered by the lack of high-quality
publicly available labeled data, largely due to the privacy and regulatory
constraints on the use of real patients’ information. This paper introduces a
new dataset, SDOH-NLI, that is based on publicly available notes and which we
release publicly.111https://github.com/google-research-datasets/SDOH-NLIWe
formulate SDOH extraction as a natural language inference (NLI) task, and
provide binary textual entailment labels obtained from human raters for a
cross product of a set of social history snippets as premises and SDOH factors
as hypotheses. Our dataset differs from standard NLI benchmarks in that our
premises and hypotheses are obtained independently. We evaluate both "off-the-
shelf" entailment models as well as models fine-tuned on our data, and
highlight the ways in which our dataset appears more challenging than commonly
used NLI datasets.

##  1 Introduction

There has been growing recognition that social and behavioral determinants of
health (SDOH) play a significant role in shaping health outcomes for
individuals and populations. The ability to accurately identify and extract
social and behavioral determinants of health from clinical notes can provide
valuable insights that can enable healthcare providers to better understand
and address the underlying determinants of health that contribute to poor
health outcomes and health disparities.

Social determinants of health are frequently recorded in clinical notes as
unstructured text, so natural language processing (NLP) can be a valuable tool
for extracting actionable insights for care teams. However, research in this
area often uses patient records from private health systems’ electronic health
records (EHRs), which makes it difficult to compare results from other health
systems or even replicate the studies. The development and release of high-
quality publicly available datasets could enable more reproducible research in
this area.

In this work, we introduce a new, public SDOH dataset based on MTSamples.com,
an online collection of transcribed medical reports. Our setup is motivated by
the use cases of slicing patient populations along social determinant
dimensions for population analytics, and retrieving patients with certain
social determinants of health to allow for more targeted outreach and
intervention. Given a large set of social determinant factors, our goal is to
make binary determinations for each patient about whether that patient’s notes
imply a particular SDOH factor. In other words, for example, we want to be
able to find all patients who lack access to transportation, as opposed to
just tagging transportation-related spans in their notes, as done in some
previous work.

To achieve this goal, we formulate the task as a textual entailment problem,
with patient note snippets as the premises, SDOH factors as the hypotheses,
and binary entailment labels. We use human annotators to label 1,398 social
history snippets according to a curated list of 60 SDOH statements, resulting
in a dataset of 29,635 labeled premise-hypothesis examples after some
filtering (see Section 3 for details). We release this dataset publicly. We
also evaluate state-of-the-art publicly available large language models on our
data in a range of different settings (see Section 4).

A notable feature of our entailment dataset is that unlike other entailment
datasets, our premises and hypotheses were obtained independently, and we
label the full cross product of premises and hypotheses. In traditional
entailment datasets, the hypotheses are constructed to be tied to a particular
premise; however, in our formulation, the hypotheses are drawn from a large
set of SDOH factors that may or may not be discussed in a particular premise
(drawn from a clinical note). Since all our text comes from the same domain,
we still have a non-negligible fraction of positive entailment labels (albeit
with a much larger label imbalance than in standard NLI benchmark datasets).

This requires NLI methods to understand both the premise and the hypothesis,
and defeats typical shortcuts that have been observed to work for other
entailment datasets, such as guessing the label based on the hypothesis alone,
or relying on simple syntactic clues such as the presence of negations (see
Section 2.2). Indeed, even though our task does not require domain-specific
knowledge, we observe that state-of-the-art models struggle to generalize from
common NLI benchmarks to our dataset, and highlight typical failure cases (see
Section 4).

We evaluate both off-the-shelf and fine-tuned models in different setups: dual
encoders, zero/few-shot prompting, and binary classification. We show that
state-of-the-art off-the-shelf models, even if they were fine-tuned on various
NLI datasets, do not reliably solve our problem; on the other hand, models
fine-tuned on our training set robustly generalize both to unseen notes and to
unseen factors, providing evidence for the usefulness of our dataset for model
fine-tuning and evaluation.

##  2 Related Work

###  2.1 Social and Behavorial Determinants of Health

There has been a lot of interest in using NLP techniques for SDOH extraction;
see Patra et al. (2021) for a recent survey. The range and granularity of SDOH
factors vary considerably across different papers. There has also been a range
of methods used, from rule-based heuristics, to n-grams, to fine-tuning
pretrained Transformer models.

Many previous research studies on SDOH extraction were performed on EHR data
from particular health systems and are not released publicly. Exceptions
include the i2b2 NLP Smoking Challenge (Uzuner et al., 2008), which classified
502 deidentified medical discharge records for smoking status only, and small
number of datasets based on MIMIC-III (Johnson et al., 2016), a large publicly
available database of deidentified health records of patients who stayed in
critical care units of Beth Israel Deaconess Medical Center between 2001 and
2012. For example, Gehrmann et al. (2018) annotated MIMIC-III with binary
labels for certain "phenotypes" including alcohol and substance abuse, and
Lybarger et al. (2021) annotated note spans with SDOH information.

We are aware of four other previous SDOH-related papers which used MTSamples
data (Wang et al., 2015; Winden et al., 2017; Yetisgen et al., 2016; Yetisgen
and Vanderwende, 2017), all of which focused on extracting and tagging SDOH-
related spans from social history sections.

Among previous papers, the one methodologically closest to ours is Lituiev et
al. (2023) which also formulated SDOH extraction as an entailment problem and
evaluated RoBERTa (Liu et al., 2019) fine-tuned on ANLI (Nie et al., 2020) on
clinical notes from UCSF, without any in-domain fine-tuning experiments.

###  2.2 Natural Language Inference

Natural language inference (NLI), also called recognizing textual entailment
(RTE), has been a very well-studied NLP task; see e.g. Storks et al. (2019);
Poliak (2020) for recent surveys. Many standard NLI datasets, such as SNLI
(Bowman et al., 2015) or MultiNLI (Williams et al., 2018), are obtained by
automatically collecting premises and, for each premise and target entailment
label, having human annotators write a hypothesis with the specified
entailment relation to the premise. (Even some of the datasets specifically
designed to address these datasets’ shortcomings, such as ANLI (Nie et al.,
2020), follow a similar setup.) It has been observed that this leads to
annotation artifacts that lets models do well on these tasks without requiring
true understanding of entailment, including by using simple syntactic
heuristics (McCoy et al., 2019) or by completely ignoring the premise, and
considering only the hypothesis (Gururangan et al., 2018; Poliak et al.,
2018). ContractNLI (Koreeda and Manning, 2021) is an example of a previous
dataset which used the same fixed set of hypotheses for all the premises.

##  3 Dataset Construction

We scraped all 5,003 medical reports from MTSamples. Within these reports, we
obtained 1,030 note sections related to social history by searching for a
collection of note section titles identified as synonyms of social history. We
then split each note section into sentences, resulting in 3,281 sentences.
Many sentences (such as "He is married") appear in multiple notes; after
deduplication, we have 1,398 unique sentences.

We manually curated a collection of SDOH factors primarily from two sources,
the AHRQ Social Determinants of Health Database (for Healthcare Research and
Quality, 2020) and UCSF SIREN’s Compendium of medical terminology codes for
social risk factors (Arons et al., 2018). We rephrased each factor as a full
English sentence stating a fact about a person; e.g. "The person is employed."
For binary factors, we included a statement and its negation; e.g. "The person
currently drinks alcohol" and "The person currently does not drink alcohol."
For factors with multiple potential values (such as housing status), we aimed
to list all the common options. We grouped these 60 statements into 10
categories: smoking, alcohol use, drug use, employment, housing, food,
transportation, health insurance, social support, and financial situation. See
the full list in Appendix A.

For each social history sentence, we asked human raters to select all the
relevant categories and, within each category, all the statements that are
supported by the social history snippet. Each snippet was rated by at least
three raters. For each (snippet, statement) pair, we took the majority vote of
raters to get binary entailment labels. Rater agreement was high, with a
Krippendorff’s alpha of 0.97 (computed over the binary entailment labels
provided by different raters for (premise, hypothesis) pairs).

We removed all SDOH statements which were not entailed by any of the social
history snippets as well as all note sentences that were not relevant to any
SDOH categories. Finally, after inspecting the dataset, we removed three SDOH
factors ("The person is stably housed.", "The person has social support.",
"The person does not have social support.") because raters weren’t able to
consistently give correct ratings. That left us with 787 unique sentences and
38 SDOH factors. Since each snippet would typically only entail one factor or
a small number of factors, the resulting dataset is heavily imbalanced: only
$4.6\%$ of the labels are positive.

We split the dataset along the snippets into training, validation, and test
sets with a 70:15:15 ratio, with the following modification: we remove a
single pair of factors, "The person lives alone" and "The person does not live
alone," from the training and validation sets, in order to evaluate fine-tuned
models’ ability to generalize to unseen factors. In other words, the training,
validation, and test sets have disjoint note snippets but the same SDOH
factors, except for the test set which also contains an additional two factors
that are not present in the training or validation sets.

##  4 Model Evaluation

Since the typical use case is retrieving patients with a particular SDOH
factor, and because of the heavy label imbalance in our dataset, we use
precision, recall, and F1 score as our evaluation metrics.

We evaluate state-of-the-art public models in four different setups:

  * •

Treating the problem as a retrieval task with SDOH factors as queries and note
snippets as documents. We evaluate Sentence-T5 (Ni et al., 2022a) and GTR (Ni
et al., 2022b), two state-of-the-art dual encoder models. We select the cosine
similarity threshold which maximizes F1 score on the training set.

  * •

A general-purpose NLI model. We evaluate the seNtLI model (Schuster et al.,
2022), a state-of-the-art NLI model (T5 large fine-tuned on the SNLI (Bowman
et al., 2015), MNLI (Williams et al., 2018), ANLI (Nie et al., 2020), Fever
(Thorne et al., 2018), and VitaminC (Schuster et al., 2021) datasets). To help
the model adapt to the label imbalance in our dataset, we also evaluate it
with re-tuning the threshold for positive prediction to maximize F1 score on
our training set.

  * •

Zero/few-shot prompting. We evaluate Flan-T5 XXL (Chung et al., 2022) and
Flan-UL2 (Tay et al., 2023) in both a zero- and a few-shot setting. These
models instruction tuned for a large set of tasks, including NLI tasks. (See
Appendix B for details.)

  * •

Fine-tuning experiments. We fine-tune T5 and Flan-T5 on our dataset (SDOH-
NLI), on ANLI, and on a mixture of both at various model sizes. (See Appendix
C for details.)

###  4.1 Results

Model | Precision | Recall | F1
---|---|---|---
Sentence-T5 11B | $.2826$ | $.523$ | $.3669$
GTR XXL | $.3148$ | $.4885$ | $.3829$
seNtLI | $.4438$ | $.8161$ | $.5749$
seNtLI, threshold tuned | $.5721$ | $.7299$ | $.6414$
Flan-T5 XXL 0-shot | $.6867$ | $.6552$ | $.6706$
Flan-T5 XXL 5-shot | $.6297$ | $.6839$ | $.6556$
Flan-UL2 0-shot | $.5922$ | $.7011$ | $.6421$
Flan-UL2 5-shot | $.5536$ | $.7126$ | $.6231$
Flan-T5 XXL finetuned on ANLI | $.356$ | $.\textbf{8736}$ | $.5058$
Flan-T5 XXL finetuned on SDOH-NLI | $.\textbf{9295}$ | $.8333$ | $.\textbf{8788}$
Flan-T5 XXL finetuned on ANLI + SDOH-NLI | $.8765$ | $.8563$ | $.8663$
Table 1: Scores of retrieval-based, general-purpose NLI, in-context, and fine-
tuned models on the SDOH test set. See Appendix C for additional fine-tuning
experiments.

Table 1 shows selected results (see Appendix D for more model fine-tuning
metrics). First, we observe that while our problem can naturally be framed as
an information retrieval problem, even state-of-the-art retrieval models
perform poorly on it; formulating the problem as natural language inference
yields dramatically better results.

However, even powerful models fine-tuned for NLI, either on NLI datasets alone
or as part of the much larger Flan collection, do not reliably solve our
problem, with an F1 score of at most $.67$ on the test set. Even T5 small
fine-tuned on our dataset outperforms the largest off-the-shelf models,
highlighting the added value of our dataset.

When prompting instruction-tuned models, including few-shot examples does not
appear to add any value compared to a zero-shot setup. We conjecture that this
is because the models are already familiar with the NLI task and the prompt
format from instruction tuning, and presenting them with a small number of
additional examples is not sufficient for teaching them the difference between
this task and the NLI benchmark datasets they have seen during fine-tuning.

For fine-tuned models below XXL size, when fine-tuning on the SDOH-NLI
training set only, we observed poor generalization to the held-out SDOH
factors in the test set (see Appendix D for detailed metrics). Because of
this, why we experimented with fine-tuning on a combination of our data and
ANLI R1, a challenging general-purpose NLI dataset of a similar size. For
smaller models, fine-tuning on this mixture enabled robust generalization to
unseen factors without sacrificing overall test performance.

###  4.2 Discussion

What makes our dataset challenging for models fine-tuned on standard NLI
datasets? We emphasize that it is not that it requires any specialized (e.g.,
medical) knowledge: most of our examples describe everyday situations in plain
English (e.g., "The patient is retired on disability due to her knee
replacements"); human raters without any domain-specific training had no
difficulty understanding them. We conjecture that the main difference is that
the hypotheses of typical NLI datasets are written to satisfy a given
entailment label for a given premise, whereas ours are obtained independently
from the premises, and therefore their entailment status can be more subtle
and ambiguous. These models also struggled with distinguishing between
statements about the present and the past; e.g., Flan-UL2 erroneously
predicting that "He is not a smoker" entails "The person wasn’t a smoker in
the past." Also, our dataset contains a lot of irrelevant hypotheses and
requires the model to correctly classify all of those; we see off-the-shelf
models occasionally giving them positive labels (e.g. predicting that "She was
living alone and is now living in assisted living." implies "The person drank
alcohol in the past."), hurting precision. As an example, Flan-T5 fine-tuned
on ANLI had comparable recall to our best models, but much worse precision.

##  5 Conclusion

In this work, we introduced SDOH-NLI, a new entailment dataset containing
social history snippets as premises and social and behavioral determinants of
health as hypotheses. Our dataset was designed both to reflect realistic use
cases of SDOH extraction in clinical settings as well as to provide a high
quality entailment dataset to support broader NLI research. We evaluated
baseline methods using state-of-the-art public models in a variety of setups,
and highlighted novel and challenging features of our dataset.

## Acknowledgments

The authors would like to thank Jonas B. Kemp, Donald Metzler, Von Nguyen,
Birju Patel, Martin G. Seneviratne, Andy Strunk, and Vinh Q. Tran for their
valuable feedback and discussions.

## Limitations

Our dataset is English-only, and reflects the American healthcare system.
While a lot of the social and behavioral determinants of health mentioned in
the data could apply elsewhere, too, their distribution and the language used
to describe them could reflect U.S. norms. Also, since the dataset is based on
transcription samples, the text can be cleaner than in some other settings
(such as notes in EHRs), where the task could be more challenging due to typos
and abbreviations that do not appear in our dataset. In such settings,
performance could be improved by first using the methods of Rajkomar et al.
(2022) to decode abbreviations, but we have not included this in our
evaluations. Finally, our dataset only contains short note snippets, and we
have not evaluated the models’ ability to reconcile contradictory statements
or reason about the chronology of information in longer patient records. For
longer contexts, especially if the social history sections don’t fit in the
Transformer model’s context window, we recommend evaluating the methods of
Schuster et al. (2022).

## Ethics Statement

Machine learning research in the clinical domain has many ethical
considerations. Given the nature of this work is to identify opportunities for
care teams to improve the health outcomes of patients due to factors commonly
not addressed, we think it contributes to human well-being and avoids harms.
The use of public, non-identifiable data that is released for the NLP
community helps balance the need to have reproducible (i.e., honest and
trustworthy) data to enable technical advances while limiting the need for
sensitive, private medical records for research. We acknowledge that the
purpose of the work is to identify SDOH to provide additional help and
services to patients, and we warn against any use to deny patients care or
services based on any factor that can be identified. Although we picked a
large number of SDOH factors to test our method, we acknowledge that there may
be additional factors that are important for specific patients and
populations, so we encourage researchers to reflect on those possible factors
and create datasets to help others study them, as well.

## References

  * Arons et al. (2018) Abigail Arons, Sarah DeSilvey, Caroline Fichtenberg, and Laura Gottlieb. 2018.  Compendium of medical terminology codes for social risk factors.
  * Bowman et al. (2015) Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. 2015\.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 632–642.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. 2022.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_.
  * for Healthcare Research and Quality (2020) Agency for Healthcare Research and MD. Quality, Rockville. 2020.  Social determinants of health database.
  * Gehrmann et al. (2018) Sebastian Gehrmann, Franck Dernoncourt, Yeran Li, Eric T Carlson, Joy T Wu, Jonathan Welt, John Foote Jr, Edward T Moseley, David W Grant, Patrick D Tyler, et al. 2018.  Comparing deep learning and concept extraction based methods for patient phenotyping from clinical narratives.  _PloS one_ , 13(2):e0192360.
  * Gururangan et al. (2018) Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A Smith. 2018.  Annotation artifacts in natural language inference data.  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 107–112.
  * Johnson et al. (2016) Alistair EW Johnson, Tom J Pollard, Lu Shen, Li-wei H Lehman, 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.
  * Koreeda and Manning (2021) Yuta Koreeda and Christopher D Manning. 2021.  Contractnli: A dataset for document-level natural language inference for contracts.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 1907–1919.
  * Lituiev et al. (2023) Dmytro S Lituiev, Benjamin Lacar, Sang Pak, Peter L Abramowitsch, Emilia H De Marchis, and Thomas A Peterson. 2023.  Automatic extraction of social determinants of health from medical notes of chronic lower back pain patients.  _J. Am. Med. Inform. Assoc._
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Longpre et al. (2023) Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoc V Le, Barret Zoph, Jason Wei, et al. 2023.  The flan collection: Designing data and methods for effective instruction tuning.  _arXiv preprint arXiv:2301.13688_.
  * Lybarger et al. (2021) Kevin Lybarger, Mari Ostendorf, and Meliha Yetisgen. 2021.  Annotating social determinants of health using active learning, and characterizing determinants using neural event extraction.  _Journal of Biomedical Informatics_ , 113:103631.
  * McCoy et al. (2019) Tom McCoy, Ellie Pavlick, and Tal Linzen. 2019.  Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3428–3448.
  * Ni et al. (2022a) Jianmo Ni, Gustavo Hernandez Abrego, Noah Constant, Ji Ma, Keith Hall, Daniel Cer, and Yinfei Yang. 2022a.  Sentence-t5: Scalable sentence encoders from pre-trained text-to-text models.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 1864–1874.
  * Ni et al. (2022b) Jianmo Ni, Chen Qu, Jing Lu, Zhuyun Dai, Gustavo Hernandez Abrego, Ji Ma, Vincent Zhao, Yi Luan, Keith Hall, Ming-Wei Chang, and Yinfei Yang. 2022b.  Large dual encoders are generalizable retrievers.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 9844–9855, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Nie et al. (2020) Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. 2020.  Adversarial nli: A new benchmark for natural language understanding.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4885–4901.
  * Patra et al. (2021) Braja G Patra, Mohit M Sharma, Veer Vekaria, Prakash Adekkanattu, Olga V Patterson, Benjamin Glicksberg, Lauren A Lepow, Euijung Ryu, Joanna M Biernacka, Al’ona Furmanchuk, et al. 2021.  Extracting social determinants of health from electronic health records using natural language processing: a systematic review.  _Journal of the American Medical Informatics Association_ , 28(12):2716–2727.
  * Poliak (2020) Adam Poliak. 2020.  A survey on recognizing textual entailment as an nlp evaluation.  In _Proceedings of the First Workshop on Evaluation and Comparison of NLP Systems_ , pages 92–109.
  * Poliak et al. (2018) Adam Poliak, Jason Naradowsky, Aparajita Haldar, Rachel Rudinger, and Benjamin Van Durme. 2018.  Hypothesis only baselines in natural language inference.  In _Proceedings of the Seventh Joint Conference on Lexical and Computational Semantics_ , pages 180–191.
  * Rajkomar et al. (2022) Alvin Rajkomar, Eric Loreaux, Yuchen Liu, Jonas Kemp, Benny Li, Ming-Jun Chen, Yi Zhang, Afroz Mohiuddin, and Juraj Gottweis. 2022.  Deciphering clinical abbreviations with a privacy protecting machine learning system.  _Nature Communications_ , 13(1):7456.
  * Roberts et al. (2022) Adam Roberts, Hyung Won Chung, Anselm Levskaya, Gaurav Mishra, James Bradbury, Daniel Andor, Sharan Narang, Brian Lester, Colin Gaffney, Afroz Mohiuddin, et al. 2022.  Scaling up models and data with t5x and seqio.  _arXiv preprint arXiv:2203.17189_.
  * Schuster et al. (2022) Tal Schuster, Sihao Chen, Senaka Buthpitiya, Alex Fabrikant, and Donald Metzler. 2022.  Stretching sentence-pair NLI models to reason over long documents and clusters.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 394–412, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Schuster et al. (2021) Tal Schuster, Adam Fisch, and Regina Barzilay. 2021.  Get your vitamin c! robust fact verification with contrastive evidence.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 624–643.
  * Storks et al. (2019) Shane Storks, Qiaozi Gao, and Joyce Y Chai. 2019.  Recent advances in natural language inference: A survey of benchmarks, resources, and approaches.  _arXiv preprint arXiv:1904.01172_.
  * Tay et al. (2023) Yi Tay, Mostafa Dehghani, Vinh Q Tran, Xavier Garcia, Jason Wei, Xuezhi Wang, Hyung Won Chung, Dara Bahri, Tal Schuster, Steven Zheng, et al. 2023.  Ul2: Unifying language learning paradigms.  In _The Eleventh International Conference on Learning Representations_.
  * Thorne et al. (2018) James Thorne, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal. 2018\.  FEVER: a large-scale dataset for fact extraction and VERification.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 809–819, New Orleans, Louisiana. Association for Computational Linguistics.
  * Uzuner et al. (2008) Özlem Uzuner, Ira Goldstein, Yuan Luo, and Isaac Kohane. 2008.  Identifying patient smoking status from medical discharge records.  _Journal of the American Medical Informatics Association_ , 15(1):14–24.
  * Wang et al. (2015) Yan Wang, Elizabeth S Chen, Serguei Pakhomov, Elliot Arsoniadis, Elizabeth W Carter, Elizabeth Lindemann, Indra Neil Sarkar, and Genevieve B Melton. 2015.  Automated extraction of substance use information from clinical texts.  In _AMIA Annual Symposium Proceedings_ , volume 2015, page 2121. American Medical Informatics Association.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1112–1122.
  * Winden et al. (2017) Tamara J Winden, Elizabeth S Chen, Yan Wang, Elizabeth Lindemann, and Genevieve B Melton. 2017.  Residence, living situation, and living conditions information documentation in clinical practice.  In _AMIA Annual Symposium Proceedings_ , volume 2017, page 1783. American Medical Informatics Association.
  * Yetisgen et al. (2016) Meliha Yetisgen, Elena Pellicer, David R Crosslin, and Lucy Vanderwende. 2016.  Automatic identification of lifestyle and environmental factors from social history in clinical text.  In _Proceedings of AMIA 2016 Joint Summits on Translational Science_.
  * Yetisgen and Vanderwende (2017) Meliha Yetisgen and Lucy Vanderwende. 2017.  Automatic identification of substance abuse from social history in clinical text.  In _Artificial Intelligence in Medicine: 16th Conference on Artificial Intelligence in Medicine, AIME 2017, Vienna, Austria, June 21-24, 2017, Proceedings 16_ , pages 171–181. Springer.

##  Appendix A Labeling Setup

Raters were given the following instructions:

"In this task, you will be given a list of snippets from transcribed medical
records, describing a person’s social history. Your job is to select the
categories that are relevant to the snippet and, in each category, select
statements about the person that are supported by the snippet.

Only select categories and statements relevant to the subject of the sentence,
NOT if they apply to someone else (such as the subject’s relatives).

The source of the medical transcript samples is a public dataset
(MTSamples.com), and not your, other raters’ or users health transcript data."

For each snippet, they were required select one or more of the following
categories (including "None of the above" if none of the categories were
relevant). If they selected a category, the statements within the category
would be displayed, and they were required to select one of statements within
that category, or "None of the above":

  * •

Smoking

    * –

The person is currently a smoker.

    * –

The person is currently not a smoker.

    * –

The person was a smoker in the past.

    * –

The person wasn’t a smoker in the past.

    * –

None of the above

  * •

Alcohol use

    * –

The person currently drinks alcohol.

    * –

The person currently does not drink alcohol.

    * –

The person drank alcohol in the past.

    * –

The person did not drink alcohol in the past.

    * –

None of the above

  * •

Drug use

    * –

The person is a drug user.

    * –

The person is not a drug user.

    * –

The person was a drug user in the past.

    * –

The person wasn’t a drug user in the past.

    * –

The person uses cocaine.

    * –

The person does not use cocaine.

    * –

The person used cocaine in the past.

    * –

The person did not use cocaine in the past.

    * –

The person uses marijuana.

    * –

The person does not use marijuana.

    * –

The person used marijuana in the past.

    * –

The person did not use marijuana in the past.

    * –

The person uses opioids (e.g., heroin, fentanyl, oxycodone).

    * –

The person does not opioids (e.g., heroin, fentanyl, oxycodone).

    * –

The person used opioids in the past (e.g., heroin, fentanyl, oxycodone).

    * –

The person did not use opioids in the past (e.g., heroin, fentanyl,
oxycodone).

    * –

None of the above

  * •

Employment

    * –

The person is employed.

    * –

The person is not employed.

    * –

The person is employed part time.

    * –

The person is a student.

    * –

The person is a homemaker.

    * –

The person is retired due to age or preference.

    * –

The person is retired due to disability.

    * –

The person is retired due to an unknown reason.

    * –

None of the above

  * •

Housing

    * –

The person lives in their own or their family’s home.

    * –

The person lives in a housing facility.

    * –

The person is homeless.

    * –

The person is stably housed.

    * –

The person’s housing is unsuited to their needs.

    * –

None of the above

  * •

Food

    * –

The person is able to obtain food on a consistent basis.

    * –

The person is not able to obtain food on a consistent basis.

    * –

The person has consistent fruit and vegetable intake.

    * –

The person does not have consistent fruit and vegetable intake.

    * –

None of the above

  * •

Transportation

    * –

The person has access to transportation.

    * –

The person does not have access to transportation.

    * –

The person has access to a car.

    * –

The person does not have access to a car.

    * –

The person has access to public transit.

    * –

The person does not have access to public transit.

    * –

The person has issues with finding transportation.

    * –

None of the above

  * •

Health insurance

    * –

The person has private health insurance.

    * –

The person is on Medicare.

    * –

The person is on Medicaid.

    * –

The person does not have health insurance.

    * –

None of the above

  * •

Social support

    * –

The person has social support.

    * –

The person does not have social support.

    * –

The person lives alone.

    * –

The person does not live alone.

    * –

None of the above

  * •

Financial situation

    * –

The person is below the poverty line.

    * –

The person is above the poverty line.

    * –

The person is able to afford medications.

    * –

The person is not able to afford medications.

    * –

None of the above

  * •

None of the above

##  Appendix B Prompting Setup

Our goal with the design of our zero/few-shot experiments was to stay close to
how the models were trained and evaluated on similar NLI tasks. Since the
models we used were fine-tuned on the Flan collection (Longpre et al., 2023),
which includes several NLI datasets, we reused some of the Flan collections’s
prompt templates.

In particular, we used the templates for the SNLI and MNLI dataset which were
the most relevant to our data. (We excluded templates for other datasets such
as RTE, ANLI, or WNLI because the wording of some of the prompts could be
slightly misleading; e.g. by referring to the premise as a "paragraph.") For
each example, we chose a prompt template uniformly at random from the 19
templates. For few-shot experiments, we first picked a random positive example
from the training set, then picked the other few-shot examples uniformly at
random from the training examples. (Without explicitly forcing at least one
example to be positive, it would be very likely that all the few-shot examples
would be negative, given the label imbalance in the dataset. We tried dropping
that requirement and sampling all examples at random, which resulted in a
slight drop in model performance, as we expected.)

Since SNLI and MNLI have three answer options ("yes," "it is not possible to
tell," "no"), we kept all three of these options in the prompt template, even
though our dataset is binary. We experimented with dropping either the "no" or
the "it is not possible to tell" option; both of these deviations from the
original prompts resulted in slight decreases in model performance.

We use rank classification to obtain binary labels (as is customary): i.e.,
instead of decoding a model prediction, we score the three answer options (for
three copies of each input example) and consider the prediction positive if
"yes" has the highest score. Similarly to our experiment with seNtLI, we also
tried taking softmax over the three options and using a fixed threshold for
"yes" which maximizes F1 score on the training set; this resulted in a small
drop in test F1 score (e.g., $.6501$ to $.6222$ for Flan-UL2).

##  Appendix C Fine-tuning Setup

All models were fine-tuned using the T5X framework (Roberts et al., 2022) on
TPUv3 chips for 10k steps with batch size 32 and learning rate 1e-4, with the
exception of the T5 small size models which were finetuned for 50k steps. For
each model, we picked the checkpoint with the highest F1 score on the
validation set.

##  Appendix D Additional Model Fine-tuning Results

See Table 2 for the full set of results from our finetuning experiments. Here
we also include metrics on the subset of the test set consisiting on the new
SDOH factors not included in the training and validation sets to highlight the
differences in models’ ability to generalize to unseen factors.

Note that since Flan-T5 models between sizes large and XL fine-tuned on either
ANLI or our SDOH dataset alone underperformed the same models fine-tuned on
the combined dataset, we did not perform these dataset ablations on smaller
Flan-T5 models or on T5 below the XXL size.

Model | Size | Dataset | Test P | Test R | Test F1 | New factors P | New factors R | New factors F1
---|---|---|---|---|---|---|---|---
T5 | small | ANLI + SDOH-NLI | $.7987$ | $.7069$ | $.7500$ | $.6667$ | $.0833$ | $.1481$
T5 | base | ANLI + SDOH-NLI | $.7396$ | $.8161$ | $.7760$ | $.75$ | $.375$ | $.5$
T5 | large | ANLI + SDOH-NLI | $.8247$ | $.7299$ | $.7744$ | $.75$ | $.125$ | $.2143$
T5 | XL | ANLI + SDOH-NLI | $.8391$ | $.8391$ | $.8391$ | $.9231$ | $.5$ | $.6486$
T5 | XXL | ANLI | $.8391$ | $.8391$ | $.8391$ | $.75$ | $.1$ | $.8571$
T5 | XXL | SDOH-NLI | $.8859$ | $.7586$ | $.8173$ | $.8571$ | $.25$ | $.3871$
T5 | XXL | ANLI + SDOH-NLI | $.9024$ | $.8506$ | $.8757$ | $.8889$ | $1.$ | $.9412$
Flan-T5 | small | ANLI + SDOH-NLI | $.8075$ | $.7471$ | $.7761$ | $.6667$ | $.0833$ | $.1481$
Flan-T5 | base | ANLI + SDOH-NLI | $.7956$ | $.8276$ | $.8113$ | $.6216$ | $.9583$ | $.7541$
Flan-T5 | large | ANLI | $.1777$ | $.8506$ | $.2939$ | $.2421$ | $.9583$ | $.3866$
Flan-T5 | large | SDOH-NLI | $.8041$ | $.6839$ | $.7391$ | $.2308$ | $.125$ | $.1622$
Flan-T5 | large | ANLI + SDOH-NLI | $.8212$ | $.8448$ | $.8329$ | $.8846$ | $.9583$ | $.92$
Flan-T5 | XL | ANLI | $.2868$ | $.8851$ | $.4332$ | $.7667$ | $.9583$ | $.8519$
Flan-T5 | XL | SDOH | $.9071$ | $.7299$ | $.8089$ | $1.$ | $.125$ | $.2222$
Flan-T5 | XL | ANLI + SDOH-NLI | $.8647$ | $.8448$ | $.8547$ | $.8846$ | $.9583$ | $.92$
Flan-T5 | XXL | ANLI | $.3560$ | $.8736$ | $.5058$ | $.7931$ | $.9583$ | $.8679$
Flan-T5 | XXL | SDOH-NLI | $.9295$ | $.8333$ | $.8788$ | $1.$ | $.875$ | $.9333$
Flan-T5 | XXL | ANLI + SDOH-NLI | $.8765$ | $.8563$ | $.8663$ | $.8846$ | $.9583$ | $.92$

Table 2: Precision, recall, and F1 scores of various models on the full test
set and on the subset of the test set consisting of the two held-out factors.


11institutetext: Department of Ophthalmology and Optometry,
Medical University of Vienna, Austria 22institutetext: Christian Doppler
Laboratory for Artificial Intelligence in Retina,
Department of Ophthalmology and Optometry, Medical University of Vienna,
Austria

# Projective Skip-Connections for Segmentation Along a Subset of Dimensions in
Retinal OCT

Dmitrii Lachinov 1122 Philipp Seeböck 11 Julia Mai 1122 Felix Goldbach 11
Ursula Schmidt-Erfurth 11 Hrvoje Bogunovic 1122

###### Abstract

In medical imaging, there are clinically relevant segmentation tasks where the
output mask is a projection to a subset of input image dimensions. In this
work, we propose a novel convolutional neural network architecture that can
effectively learn to produce a lower-dimensional segmentation mask than the
input image. The network restores encoded representation only in a subset of
input spatial dimensions and keeps the representation unchanged in the others.
The newly proposed projective skip-connections allow linking the encoder and
decoder in a UNet-like structure. We evaluated the proposed method on two
clinically relevant tasks in retinal Optical Coherence Tomography (OCT):
geographic atrophy and retinal blood vessel segmentation. The proposed method
outperformed the current state-of-the-art approaches on all the OCT datasets
used, consisting of 3D volumes and corresponding 2D en-face masks. The
proposed architecture fills the methodological gap between image
classification and $N$D image segmentation.

##  1 Introduction

The field of medical image segmentation is dominated by neural network based
solutions. The convolution neural networks (CNNs), notably U-Net [24] and its
variants, demonstrate state-of-the-art performance on a variety of medical
benchmarks like BraTS [1], LiTS [3], REFUGE [23], CHAOS [13] and ISIC [6].
Most of these benchmarks focus on the problem of segmentation, either 2D or
3D, where the input image and the output segmentation mask are of the same
dimension. However, a few medical protocols like OCT for retina [16, 17], OCT
and Ultrasound for skin [21, 25], Intravascular ultrasound (IVUS) pullback
images for vasculature [26], CT for diaphragm analysis [29] and online tumor
tracking [22] require the segmentation to be performed on the image
projection, resulting in the output segmentation of lower spatial dimension
than the input image. It introduces the problem of dimensionality reduction
into the segmentation, for example, segmenting a flat 2D en-face structures on
the projection of a 3D volumetric image.

This scenario has so far not been sufficiently explored in the literature and
it is currently not clear what CNN architectures are the most suitable for
this task. Here, we propose a new approach for $N\text{D}\rightarrow
M\text{D}$ segmentation, where $M<N$ , and evaluate it on two clinically
relevant tasks of 2D Geographic Atrophy (GA) and Blood Vessels segmentation in
3D optical coherence tomography (OCT) retinal images.

###  1.1 Clinical background

##### Geographic atrophy (GA)

is an advanced form of age-related macular degeneration (AMD). It corresponds
to localized irreversible and progressive loss of retinal photoreceptors and
leads to a devastating visual impairment. 3D optical coherence tomography
(OCT) is a gold standard modality for retinal examination in ophthalmology. In
OCT, GA is characterized by hypertransmission of OCT signal below the retina.
As GA essentially denotes a loss of tissue, it does not have “thickness”, and
it is hence delineated as a 2D en-face area (Fig. 1).

##### Retinal blood vessels

provide oxygen and nutrition to the retinal tissues. Retinal vessels are
typically examined using 2D fundus photographs where they can be seen as dark
lines. In OCT volumes, retinal blood vessels can be detected in individual
slices (B-scans) as interconnected morphological regions, dropping shadows on
the underlying retinal layer structures (Fig. 1).

(a)

(b)

(c)

(d)

(e)

Figure 1: (a) 3D retinal OCT volume. Ground truth annotations are shown in 2D
cross-sectional slices for (b) GA and (c) blood vessels in yellow. Predictions
of the proposed method are visualized in en-face projection images for (d) GA
and (e) blood vessels. Green region - true positives, orange - false
positives, dark red - false negatives.

###  1.2 Related work

Recently, several methods dealing with dimensionality reduction in
segmentation tasks have been proposed [17, 16, 11]. Liefers et al. [17]
introduced a fully convolutional neural network to address the problem of
$N\text{D}\rightarrow M\text{D}$ segmentation. The authors evaluated their
method on $2D\rightarrow 1D$ tasks of Geographic Atrophy (GA) and Retinal
Layer segmentation. In contrast to our method, their approach is limited by
the fixed size of the input image and shortcut networks that are prone to
overfitting. This is caused by the full compression of the image in 2nd
dimension, leading to a large receptive field but completely removing the
local context.

Recently, Li et al. [16] proposed an image projection network IPN designed for
3D-to-2D image segmentation, without any explicit shortcuts or skip-
connections. Pooling is only performed for a subset of dimensions, resulting
in a highly anisotropic receptive field. This limits the amount of context the
network can use for segmentation.

Ji et al. [11] proposed a deep voting model for GA segmentation. First,
multiple fully-connected classifiers are trained on axial depth scans
(A-scans), producing a single probability value for each A-scan (1D-to-0D
reduction). During the inference phase, the predictions of the trained
classifiers are concatenated to form the final output. This approach doesn’t
account for neighboring AScans, thus lacks spatial context, and requires
additional postprocessing.

Existing approaches suffer from two main limitations: On the one hand, they
are designed to handle images of a fixed size, making patch based training
difficult. This is of particular relevance as it has been shown that patch
based training improves overall generalization as it serves as additional data
augmentation [15]. On the other hand, existing $N\text{D}\rightarrow
M\text{D}$ methods have a large receptive field due to a high number of
pooling operations or large pooling kernel sizes, that fail to capture local
context. To illustrate this issue, we conducted a compared receptive fields of
state-of-the-art segmentation [12, 30, 19, 7, 28, 2] and classification
methods [18, 5, 20] for medical imaging across different benchmarks [1, 3, 6]
with popular architectures designed for natural images classification [8,
9](Fig 1-2 in the supplement). We observed that current state-of-the art
methods for segmentation in a subset of input dimensions [17, 16] fall out of
the cluster with methods designed for medical tasks, and have a receptive
field comparable to the networks designed for natural images classification.
However, the amount of training data available for medical tasks differs by
the orders of magnitude from the natural images data. Alternatively, the
$N\text{D}\rightarrow M\text{D}$ segmentation task can be solved using
$N\text{D}\rightarrow N\text{D}$ methods. It can be attempted by either first
projecting the input image to the output $M\text{D}$ space, which looses
context, or by running $N\text{D}$ segmentation first, which is memory
demanding, requires additional postprocessing and is not effective.

Our approach is explicitly designed to overcome these limitations. We propose
a segmentation network that can handle arbitrary sized input and is on par
with state-of-the-art $N\text{D}\rightarrow N\text{D}$ medical segmentation
methods in terms of receptive field size.

###  1.3 Contribution

In this paper we introduce a novel CNN architecture for $N\text{D}\rightarrow
M\text{D}$ segmentation. The proposed approach has a decoder that operates in
the same dimensionality space as the encoder, and restores the compressed
representation of the bottleneck layer only in a subset of the input
dimensions. The contribution of this work is threefold: (1) We propose
projective skip-connections addressing the general problem of segmentation in
a subset of dimensions; (2) We provide clear definitions and instructions on
how to reuse the method for arbitrary input and output dimensions; (3) We
perform an extensive evaluation with three different datasets on the task of
Geographic Atrophy and Retinal Blood Vessel $3D\rightarrow 2D$ segmentation in
retinal OCTs. The results demonstrate that the proposed method clearly
outperforms the state-of-the-art.

##  2 Method

Let the image $I\in\mathbb{R}^{\prod_{d=1}^{N}{n_{d}}}$, where $N$ is the
number of dimensions, and $n_{d}$ is the size of the image in the
corresponding dimension $d$. We want to find such function $f$ that
$f:I\longrightarrow O$, where $O\in\mathbb{R}^{\prod_{d=1}^{M}{n_{d}}}$ is
output segmentation and $M$ is its dimensionality. We focus on the case where
$M\leq N$ with dimensions $d\leq M$ being target dimensions, where we perform
segmentation; and $M<d\leq N$ being reducible dimensions.

We parameterize $f$ by a convolutional neural network. The CNN architecture we
propose to use for the segmentation along dimensions $M$ follows a U-Net [24,
32] architecture. The encoder consists of multiple blocks that sequentially
process and downsample the input volume. Unlike the other methods, we don’t
perform the global pooling in the network bottleneck in the dimensions outside
of $M$. Instead, we freeze the size of these dimensions and propagate the
features through the decoder into the final classification layer. The decoder
restores the input resolution only across those target dimensions $M$ where we
perform the segmentation. The decoder keeps feature maps in the remaining
reducible dimensions $M<d\leq N$ compressed. Since the sizes of encoder and
decoder feature maps do not match, we propose projective skip-connections to
link them.

At the last stage of the network, each location of the output $M$D image has a
corresponding feature tensor of compressed representation in $(N-M)$D (refer
to Fig. 2). We perform Global Average Pooling (GAP) and a regular convolution
to obtain $M$D logits.

###  2.1 Projective skip-connections

The purpose of projective skip-connections is to compress the reducible
dimensions $M<d\leq N$ to the size of bottleneck and leave the target
dimensions $d\leq M$ unchanged. In contrast to GAP, we don’t completely reduce
the target dimensions to size of 1 (Section 3.2). Instead, we use average
pooling with varying kernel size (Fig. 2). Keeping in mind that the feature
map size along dimension $d$ generated by our proposed network $f$ of depth
$l$ with input image $I$ at the level $j$ of the encoder will be
$\frac{n_{d}}{2^{j-1}}$, the feature map size at the level $j$ of the decoder
will be $n_{d}^{j}$ (1).
$n_{d}^{j}=\begin{cases}\frac{n_{d}}{2^{j-1}},&\mbox{if }d\leq M\\\
\frac{n_{d}}{2^{l-1}},&\mbox{otherwise.}\end{cases}$ (1)
$k_{d}^{j}=\begin{cases}1,&\mbox{if }d\leq M\\\
2^{l-j},&\mbox{otherwise,}\end{cases}$ (2) We propose to perform the average
pooling of the encoder feature maps with kernel size and stride $k_{d}^{j}$
(2), where $d$ is the corresponding dimension, and $j$ is the corresponding
layer of the network. After the average pooling is performed, we concatenate
the encoder and decoder feature maps.

Figure 2: The proposed CNN architecture solving $ND\rightarrow MD$
segmentation problem, where $N=3$ and $M=2$. _Transformation_ can be any sort
of operation, residual blocks in our case. The input is a 3D crop from the SD-
OCT image. The final feature map is averaged (GAP) in dimensions that are not
in $M$, only last dimension in our case. Then the feature map is processed
with final convolution, that reduces the number of channels from 32 to 1. The
output is a 2D en-face segmentation mask. The network in this figure has a
configuration of $l=3$, $C=\\{2,4,8\\}$, and $B=\\{1,1,1\\}.$

The proposed CNN can be explicitly described with the depth or the number of
total network levels $l$, the number of channels per convolution for each
level $C=\\{{c_{0}}\times 2^{i-1}:1\leq i\leq l\\}$, and the number of
residual blocks at each level $B=\\{b_{i}:i\leq l\\}$. The schematic
representation of the proposed approach is shown in Fig. 2. The network has a
configuration of $l=3$, $C=\\{2,4,8\\}$ and $B=\\{1,1,1\\}$. The input is a 3D
volume patch $I\in\mathbb{R}^{64\times 128\times 256}$, so $N=3$. We are
interested in the en-face segmentation, so $M=2$. In the extreme case where
$M=N$, the proposed CNN is equivalent to a U-Net architecture with residual
blocks. If $M=0$, the proposed CNN is equivalent to N-D ResNet with skip-
connections in the last residual blocks.

##  3 Experiments

###  3.1 Data sets

We use a rich collection of three medical datasets with annotated retinal OCT
volumes for our experiments (Table 1). All our datasets consist of volumetric
3D OCT images and corresponding en-face 2D annotations (Fig 1), meaning that
the used datasets represent $3D\rightarrow 2D$ segmentation problems.

Table 1: Datasets description

Dataset | Device | Volumes | Eyes | Patients |  Depth, mm |  En-face area,$\text{mm}^{2}$ |  Depth spacing, $\mu\text{m}$ |  En-face Spacing,$\mu\text{m}^{2}$ |  Depth resolution, px |  En-face resolution, $\text{px}^{2}$
---|---|---|---|---|---|---|---|---|---|---
GA 1 | Spectralis | 192 | 70 | 37 | 1.92 | $6.68\times 6.86$ | $3.87$ | $156.46\times 7.91$ | 496 | $43\times 867$
GA 2 | Spectralis | 260 | 147 | 147 | 1.92 | $6.02\times 6.03$ | $3.87$ | $122.95\times 11.16$ | 496 | $49\times 540$
Vessel 1 | TopconDR | 1 | 1 | 1 | 2.3 | $6\times 6$ | $2.6$ | $46.87\times 11.72$ | 885 | $128\times 512$
| Cirrus | 40 | 40 | 40 | 2 | $6.05\times 6.01$ | $1.96$ | $47.24\times 11.74$ | 1024 | $128\times 512$
| Spectralis | 43 | 43 | 43 | 1.92 | $5.88\times 5.82$ | $3.87$ | $60.57\times 5.68$ | 496 | $97\times 1024$
| Topcon2000 | 9 | 9 | 9 | 2.3 | $6\times 6$ | $2.6$ | $46.88\times 11.72$ | 885 | $128\times 512$
| Topcon-Triton | 32 | 32 | 32 | 2.57 | $7\times 7$ | $2.59$ | $27.34\times 13.67$ | 992 | $256\times 512$

The following are the three datasets. Dataset ‘GA1’: The scans were taken at
multiple time points from an observational longitudinal study of natural GA
progression. Annotations of GA were performed by retinal experts on 2D Fundus
Auto Fluorescence (FAF) images and transferred by image registration to the
OCT, resulting in 2D en-face OCT annotations. Dataset ‘GA2’: With the OCT
scans originating from a clinical trial that has en-face annotations of GA
that were annotated directly on the OCT BScans by a retinal expert. Dataset
‘Vessel 1’: A diverse set of OCT scans across device manufacturers of patients
with AMD where the retinal blood vessels were directly annotated on OCT en-
face projections by retinal experts.

###  3.2 Baseline methods

We exhaustively compared our approach against multiple $N\text{D}\rightarrow
N\text{D}$ baselines: _UNet 3D_ [32] operating on OCT volume; _UNet 2D_ [24]
operating on OCT volume projections; _UNet++_ [31] operating on OCT volume
projections. And $N\text{D}~{}\rightarrow~{}M\text{D}$ methods: _SD_ or
Selected Dimensions [17]; _FCN_ or Fully Convolutional Network, used as a
baseline in [17]; _IPN_ or Image Projection Network [16];

Ablation experiment: _3D2D_ is a variation of the proposed method with 3D
encoder and 2D decoder networks. The bottleneck and skip-connections perform
global pooling in the dimensions $d\geq M$. This ablation experiment was
included to study the effect of propagating deep features to the last stages
of the network.

###  3.3 Training Details

As a part of preprocessing, we flattened the volume along the Bruch’s
Membrane, and cropped a 3D retina region with the size of 128 pixels along
AScan (vertical direction) and keep the full size in the rest of dimensions.
We resampled the images to have $119.105\times 5.671\mu\text{m}^{2}$ en-face
spacing. Before processing the data, we performed z-score normalization in
cross-sectional plane. For generating OCT projections, we employed the
algorithm introduced by Chen et al. [4].

For the task of Geographic Atrophy segmentation, the _proposed_ method has the
following configuration: $l=4$, $B=\\{1,1,1,1\\}$, $C=\\{32,64,128,256\\}$. We
use residual blocks [8] with 3D convolutions with kernel size of 3. Instead of
Batch Normalization [10], we employ Instance Normalization [27], due to small
batch size. The _3D2D_ network has the same configuration as the proposed
method. _SD_ and _FCN_ are reproduced as in the paper [17], but with the AScan
size equals to 128 and 32 channels in the first convolution. _IPN_ network is
implemented as in the paper [16] for $3D\rightarrow 2D$ case with 32 channels
in the first convolution. _UNet 2D_ is reproduced as in the paper [24], but
with residual blocks. _UNet 3D_[32] and _UNet++_[31] were reproduced by
following the corresponding papers. _UNet 3D_ output masks were converted to
2D by pooling the reducible dimensions and thresholding. For Retinal Vessel
segmentation, we used the networks of the same configuration, but we set the
number of channels in the first layer equal to 4.

The models were trained with Adam [14] optimizer for $3\cdot 10^{4}$ and
$10^{4}$ iterations with weight decay of $10^{-5}$, learning rate of $10^{-3}$
and decaying with a factor of 10 at iteration $2\cdot 10^{4}$ and $6\cdot
10^{3}$ for GA and blood vessels segmentation respectively. For GA
segmentation, the batch size was set to 8 and patch size to $64\times
256\times 64$. For the _SD_ and _FCN_ models we used patch size of $64\times
512\times 512$ due to architecture features described in the paper [17]. For
blood vessels segmentation, the batch size was set to 8 and patch size was
$32\times 128\times 256$. The optimizer was chosen empirically for each model.
We used Dice score as a loss function for both tasks.

###  3.4 Evaluation Details

For all three datasets (GA1, GA2, Vessel 1) we conducted a 5-fold cross-
validation for evaluation. The splits were made on patient level with
stratification by baseline GA size for GA datasets and by device manufacturer
for Vessel 1 dataset. The results marked as validation are average of all
samples from all the validation splits. The Dice score and 95th percentile of
Hausdorff distance averaged across scans (Dice and HD95) were used. To test
for significant differences between the proposed method and baselines, we
conducted two-sided Wilcoxon signed-rank tests, using $\alpha=0.05$. In
addition to cross-validation results, we report performances on hold out
(external) datasets: models trained on GA1 were evaluated on GA2 serving as an
external test set and vice versa.

##  4 Results and Discussion

Cross-validation results are reported in the Table 2. The qualitative examples
of segmentations can be found in Supplementary materials. For all the tasks,
the proposed methods achieved a significant improvement in both the mean
_Dice_ and _Hausdorff_ distance. This improvement is also reflected in the
boxplots, showing higher mean _Dice_ scores and lower variance consistently
across all datasets (Figure 3(a)). Of note, _SD_ approach outperformed _FCN_ ,
successfully reproducing their results reported in [17]. In Table 2 we can see
a significant margin in the performance between $N$D methods like _2D UNet_
,_3D UNet_ ,_UNet++_ and $3D\rightarrow 2D$ methods. This indicates that the
problem of $3D\rightarrow 2D$ segmentation cannot be solved efficiently with
existing $2D$ or $3D$ methods.

External test set results are provided in Table 2. The proposed method
outperforms all other approaches, with significant improvements in GA2. The
improvement over _SD_[17] on GA 1 dataset is slightly below the significance
threshold, $\text{p-value}=0.063$, but the boxplots (Figure 3(b)) highlight
the lower variance and higher median _Dice_ of the proposed architecture.

Table 2: Experiments results. Left: cross-validation, right: external test
set. (*: p-value$\leq 0.05$; **: p-value$\leq 10^{-5}$; ***: p-value$\leq
10^{-10}$).

Dataset | GA 1 | GA 2 | Vessel 1
---|---|---|---
Model | Dice | HD95 | Dice | HD95 | Dice | HD95
UNet 3D [24] | $0.71^{***}$ | $0.71^{***}$ | $0.85^{***}$ | $0.58^{***}$ | - | -
UNet 2D [24] | $0.73^{***}$ | $1.43^{***}$ | $0.82^{***}$ | $1.18^{***}$ | $0.51^{***}$ | $0.63^{***}$
UNet++ [24] | $0.75^{***}$ | $1.22^{***}$ | $0.83^{***}$ | $1^{***}$ | $0.50^{***}$ | $0.65^{***}$
FCN [17] | $0.769^{***}$ | $0.533^{***}$ | $0.890^{***}$ | $0.114^{***}$ | $0.358^{***}$ | $0.934^{***}$
IPN [16] | $0.793^{***}$ | $0.523^{**}$ | $0.910^{***}$ | $0.116^{***}$ | $0.630^{***}$ | $0.482^{*}$
SD [17] | $0.788^{***}$ | $0.591^{***}$ | $0.919^{***}$ | $0.092^{***}$ | $0.654^{***}$ | $0.447^{**}$
3D2D | $0.791^{**}$ | $0.563^{**}$ | $0.927^{***}$ | $0.070^{**}$ | $0.650^{***}$ | $0.451^{*}$
Proposed | 0.820 | 0.336 | 0.935 | 0.052 | 0.684 | 0.367

Dataset | GA 1 | GA 2
---|---|---
Model | Dice | HD95 | Dice | HD95
FCN [17] | $0.761^{***}$ | $0.426^{***}$ | $0.878^{***}$ | $0.141^{***}$
IPN [16] | $0.796^{***}$ | $0.549^{**}$ | $0.903^{***}$ | $0.094^{**}$
SD [17] | $0.817$ | $0.404$ | $0.905^{***}$ | $0.113^{***}$
3D2D | $0.819^{*}$ | $0.382$ | $0.906^{***}$ | $0.113^{**}$
Proposed | 0.824 | 0.310 | 0.915 | 0.079

(a)

(b)

Figure 3: Segmentation performance evaluated with (a) cross-validation and (b)
external test set.

##  5 Conclusion

The problem of image segmentation in a subset of dimensions is a
characteristic of a few relevant clinical applications. It can not be
efficiently solved with well-studied 2D-to-2D or 3D-to-3D segmentation
methods. In this paper, we first analyzed and discussed the existing
approaches designed for $N\text{D}\rightarrow M\text{D}$ segmentation. For
instance, existing methods share the same features, like large receptive field
and encoder performing dimensionality reduction. The skip-connections,
however, are implemented as subnetworks or not used at all.

Based on this analysis we proposed a novel convolutional neural network
architecture for image segmentation in a subset of input dimensions. It
consists of encoder that doesn’t completely reduce any of the dimensions; the
decoder that restores only the dimensions where the segmentation is needed;
and projective skip-connections that help to link the encoder and the decoder
of the network. The proposed method was tested on three medical datasets and
it clearly outperformed the state of the art in two $3D\rightarrow 2D$ retinal
OCT segmentation tasks.

#### Acknowledgements:

The financial support by the Austrian Federal Ministry for Digital and
Economic Affairs, the National Foundation for Research, Technology and
Development and the Christian Doppler Research Association is gratefully
acknowledged.

## References

  * [1] Bakas, S., et al.: Identifying the Best Machine Learning Algorithms for Brain Tumor Segmentation, Progression Assessment, and Overall Survival Prediction in the BRATS Challenge. ArXiv abs/1811.02629 (2018)
  * [2] Bi, L., Kim, J., Kumar, A., Feng, D.: Automatic liver lesion detection using cascaded deep residual networks. ArXiv abs/1704.02703 (2017)
  * [3] Bilic, P., et al.: The Liver Tumor Segmentation Benchmark (LiTS). ArXiv abs/1901.04056 (2019)
  * [4] Chen, Q., Niu, S., Shen, H., Leng, T., de Sisternes, L., Rubin, D.L.: Restricted Summed-Area Projection for Geographic Atrophy Visualization in SD-OCT Images. Translational Vision Science & Technology 4(5), 2 (2015). https://doi.org/10.1167/tvst.4.5.2
  * [5] Díaz, I.G.: Incorporating the knowledge of dermatologists to convolutional neural networks for the diagnosis of skin lesions. arXiv: Computer Vision and Pattern Recognition (2017)
  * [6] Gutman, D., Codella, N.C.F., Celebi, M.E., Helba, B., Marchetti, M., Mishra, N., Halpern, A.: Skin lesion analysis toward melanoma detection: A challenge at the 2017 International symposium on biomedical imaging (ISBI), hosted by the international skin imaging collaboration (ISIC). 2018 IEEE 15th International Symposium on Biomedical Imaging (ISBI 2018) pp. 168–172 (2018)
  * [7] Han, X.: Automatic liver lesion segmentation using a deep convolutional neural network method. ArXiv abs/1704.07239 (2017)
  * [8] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 770–778 (June 2016)
  * [9] Huang, G., Liu, Z., Weinberger, K.Q.: Densely connected convolutional networks. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) pp. 2261–2269 (2017)
  * [10] Ioffe, S., Szegedy, C.: Batch normalization: Accelerating deep network training by reducing internal covariate shift. ArXiv abs/1502.03167 (2015)
  * [11] Ji, Z., Chen, Q., Niu, S., Leng, T., Rubin, D.L.: Beyond Retinal Layers: A Deep Voting Model for Automated Geographic Atrophy Segmentation in SD-OCT Images. Translational Vision Science & Technology 7(1), 1–1 (01 2018)
  * [12] Jiang, Z., Ding, C., Liu, M., Tao, D.: Two-Stage Cascaded U-Net: 1st Place Solution to BraTS Challenge 2019 Segmentation Task. In: BrainLes@MICCAI (2019)
  * [13] Kavur, A.E., et al.: CHAOS Challenge - Combined (CT-MR) Healthy Abdominal Organ Segmentation. ArXiv abs/2001.06535 (2020)
  * [14] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. CoRR abs/1412.6980 (2015)
  * [15] Krizhevsky, A., Sutskever, I., Hinton, G.E.: ImageNet classification with deep convolutional neural networks. In: CACM (2017)
  * [16] Li, M., Chen, Y., Ji, Z., Xie, K., Yuan, S., Chen, Q., Li, S.: Image Projection Network: 3D to 2D Image Segmentation in OCTA Images. IEEE Transactions on Medical Imaging 39(11), 3343–3354 (2020)
  * [17] Liefers, B., González-Gonzalo, C., Klaver, C., van Ginneken, B., Sánchez, C.: Dense segmentation in selected dimensions: Application to retinal optical coherence tomography. Proceedings of Machine Learning Research, vol. 102, pp. 337–346. PMLR, London, United Kingdom (08–10 Jul 2019)
  * [18] Matsunaga, K., Hamada, A., Minagawa, A., Koga, H.: Image classification of melanoma, nevus and seborrheic keratosis by deep neural network ensemble. ArXiv abs/1703.03108 (2017)
  * [19] McKinley, R., Rebsamen, M., Meier, R., Wiest, R.: Triplanar Ensemble of 3D-to-2D CNNs with Label-Uncertainty for Brain Tumor Segmentation. In: BrainLes@MICCAI (2019)
  * [20] Menegola, A., Tavares, J., Fornaciali, M., Li, L., Avila, S., Valle, E.: RECOD Titans at ISIC Challenge 2017. ArXiv abs/1703.04819 (2017)
  * [21] Mlosek, R.K., Malinowska, S.: Ultrasound image of the skin, apparatus and imaging basics. Journal of ultrasonography 13(53), 212–221 (jun 2013). https://doi.org/10.15557/JoU.2013.0021
  * [22] Murphy, M.J.: Tracking moving organs in real time. Seminars in Radiation Oncology 14(1), 91–100 (2004)
  * [23] Orlando, J.I., et al.: REFUGE Challenge: A unified framework for evaluating automated methods for glaucoma assessment from fundus photographs. Medical Image Analysis 59, 101570 (2020)
  * [24] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: Navab, N., Hornegger, J., Wells, W.M., Frangi, A.F. (eds.) Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015. pp. 234–241. Springer International Publishing, Cham (2015)
  * [25] Srivastava, R., Yow, A.P., Cheng, J., Wong, D.W.K., Tey, H.L.: Three-dimensional graph-based skin layer segmentation in optical coherence tomography images for roughness estimation. Biomed. Opt. Express 9(8), 3590–3606 (Aug 2018)
  * [26] Sun, S., Sonka, M., Beichel, R.R.: Graph-based IVUS segmentation with efficient computer-aided refinement. IEEE transactions on medical imaging 32(8), 1536–1549 (aug 2013). https://doi.org/10.1109/TMI.2013.2260763
  * [27] Ulyanov, D., Vedaldi, A., Lempitsky, V.: Instance normalization: The missing ingredient for fast stylization. ArXiv abs/1607.08022 (2016)
  * [28] Vorontsov, E., Chartrand, G., Tang, A., Pal, C., Kadoury, S.: Liver lesion segmentation informed by joint liver segmentation. 2018 IEEE 15th International Symposium on Biomedical Imaging (ISBI 2018) pp. 1332–1335 (2018)
  * [29] Yalamanchili, R., Chittajallu, D., Balanca, P., Tamarappoo, B., Berman, D., Dey, D., Kakadiaris, I.: Automatic segmentation of the diaphragm in non-contrast ct images. In: 2010 IEEE International Symposium on Biomedical Imaging: From Nano to Macro. pp. 900–903 (2010)
  * [30] Zhao, Y.X., Zhang, Y.M., Liu, C.L.: Bag of tricks for 3d mri brain tumor segmentation. In: Crimi, A., Bakas, S. (eds.) Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries. pp. 210–220. Springer International Publishing, Cham (2020)
  * [31] Zhou, Z., Siddiquee, M.M.R., Tajbakhsh, N., Liang, J.: UNet++: A Nested U-Net Architecture for Medical Image Segmentation. Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support : 4th International Workshop, DLMIA 2018, and 8th International Workshop, ML-CDS 2018, held in conjunction with MICCAI 2018, Granada, Spain, S… 11045, 3–11 (2018)
  * [32] Çiçek, Ö., Abdulkadir, A., Lienkamp, S.S., Brox, T., Ronneberger, O.: 3D U-Net: Learning Dense Volumetric Segmentation from Sparse Annotation. In: MICCAI (2016)

Supplementary Materials

Figure 4: Ratio of the receptive field size and the input image size for the
main CNN architectures designed for either medical or natural images. Figure
5: The scatter plot of different networks where x-axis corresponds to
receptive field size, and y-axis corresponds to input image size, during
training.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 6: Qualitative example of the results. Geographic Atrophy and retinal
blood vessels segmentation (a),(e) FCN. (b),(f) IPN (c),(g) SD. (d),(h)
Proposed method. Green region - true positives, orange - false positives, dark
red - false negatives.