that assumption is unnecessary and the same proof works in the case with
boundary. ∎

The definition of the Fukaya category $\mathcal{F}(S,M,\nu)$ is based on
counting immersed polygons in $\widehat{S}$. Instead, we could also count
immersed polygons in $S$, or equivalently immersed polygons “with holes” in
$\widehat{S}$, where each hole corresponds to a point in the polygon in $S$
which maps to a point in $M$. Algebraically, this turns out to give a
deformation of $\mathcal{F}(S,M,\nu)$ over $\mathbf{k}[[t]]$, where the degree
of $t$ has to be a positive multiple of an integer which depends on the
behaviour of $\nu$ near $M$. In the following we discuss all this in more
detail.

######  Definition 4.8.

Let $(S,M,\nu)$ be a graded marked surface, $M^{\prime}\subset
M\cap\mathrm{int}(S)$, and $n\in\mathbb{Z}$. The pair $(M^{\prime},n)$ is
_compatible_ if for every $p\in M^{\prime}$ there is a positive integer $m$
with $n=\mathrm{ind}_{\nu}(p)m$. (The index $\mathrm{ind}_{\nu}(p)$ is the
winding number of $\nu$ around $p$.)

Note that in the situation of the definition above, $n/\mathrm{ind}(p)$ is a
well-defined positive integer unless $\mathrm{ind}(p)=0$ in which case $n=0$
also. In that case we define $n/\mathrm{ind}(p)\coloneqq 1$.

Fix a graded marked surface $(S,M,\nu)$ and a compatible pair $(M^{\prime},n)$
in the above sense. The next step is to construct a curved,
$\mathbb{Z}\times\mathbb{Z}/2$-graded $A_{\infty}$-category over
$\mathbf{k}[[t]]$, $|t|=2-n$, $\pi(t)=n\mod 2$, whose base change to
$\mathbf{k}$ is $\mathcal{F}_{\mathbb{X}}$. Here, curved means that besides
the $A_{\infty}$-operations $\mathfrak{m}_{d}$, $d\geq 1$, there are also
elements $\mathfrak{m}_{0}\in\mathrm{Hom}^{2}(X,X)$ for every object $X$,
satisfying a generalization of the usual $A_{\infty}$-category equations.
Morphism spaces are required to be topologically free
$\mathbf{k}[[t]]$-modules. We emphasize also that $\mathbf{k}[[t]]$ is
complete and commutative in the $\mathbb{Z}\times\mathbb{Z}/2$-graded sense,
and thus has underlying ungraded algebra: the algebra of polynomials if
$|t|\neq 0$, or the algebra of formal power series if $|t|=0$. We refer the
reader to [Hai24] for the details on the definition of such
$A_{\infty}$-categories.

The following definition generalizes the kinds of immersed polygons in the
definition of $\mathcal{F}_{\mathbb{X}}$ — the special case $k=0$.

######  Definition 4.9.

Let $D$ be a $2d$-gon with $k\geq 0$ open disks removed from its interior.
Denote by $e_{1},f_{1},e_{2},f_{2},\ldots,e_{d},f_{d}$ the edges of $D$ in
clockwise order, and by $c_{1},\ldots,c_{k}$ the boundaries of the removed
disks. An _immersed $2d$-gon with $k$ holes_ is an immersion $\psi\colon
D\to\widehat{S}$ so that each $e_{i}$ is mapped to an arc in $\mathbb{X}$,
each $f_{i}$ is mapped to a boundary path, $a_{i}$, in $\widehat{S}$, and each
$c_{i}$ is mapped to a component $\pi^{-1}(p)$ of $\partial\widehat{S}$ for
some $p\in M^{\prime}$ in a $d/\mathrm{ind}(p)$-to-1 covering. The _associated
cyclic sequence_ of boundary paths is $a_{d},a_{d-1},\ldots,a_{1}$.

######  Lemma 4.10.

If $a_{d},a_{d-1},\ldots,a_{1}$ is the associate cyclic sequence of some
immersed $2d$-gon with $k$ holes $\psi\colon D\to\widehat{S}$, then

$|a_{1}|+\ldots+|a_{d}|=d-2+(2-n)k,\qquad\pi(a_{1})+\ldots+\pi(a_{d})=nk\mod
2.$ (4.3)

###### Proof.

This is a slight generalization of [Hai24, Lemma 3.14]. The key point is that
the foliation $\psi^{*}\nu$ on $D$ satisfies $\mathrm{ind}(c)=n$ if $c$ is the
boundary of one of the $k$ removed disks. In the case $n=2$ we get no
correction from the holes, since $\psi^{*}\nu$ extends to a smooth foliation
on the entire $2d$-gon (i.e. without the holes) in that case. In general, we
get $\mathrm{ind}(c)=2+(n-2)k$ for a simple loop $c$ which goes around all the
$k$ holes in $D$ in counterclockwise direction. ∎

######  Lemma 4.11.

Fix a cyclic sequence $a_{d},a_{d-1},\ldots,a_{1}$ of boundary paths and
$k\geq 0$, then there are finitely many $2d$-gons with $k$ holes, up to
reparametrization, with associated cyclic sequence the given one.

Note that in the case $n\neq 2$, $k$ is already determined by the $a_{i}$’s by
the previous lemma, so does not need to be fixed.

###### Proof.

The proof is essentially the same as in [Hai24, Lemma 3.15], with the only
difference that the factor “3” appearing there needs to be replaced by $n$ if
$n\neq 0$ and 1 if $n=0$. The basic idea is as follows: Let $D$ be some
$2d$-gon with $k$ holes and associated cyclic sequence the given one. Our
assumptions fix the number of edges of $\mathbb{X}$-polygons, counted with
multiplicity, which appear on the boundary of $D$. But this implies a bound on
the number of $\mathbb{X}$-polygons tessellating $D$. ∎

######  Definition 4.12.

Let $(S,M,\nu)$ be a graded marked surface, $\mathbb{X}$ an arc system,
$M^{\prime}\subset M$, and $n\in\mathbb{Z}$ such that $(M^{\prime},n)$ is
compatible. Define a curved, $\mathbb{Z}\times\mathbb{Z}/2$-graded
$A_{\infty}$-category $\mathcal{A}_{\mathbb{X}}$ over $\mathbf{k}[[t]]$,
$|t|=2-n$, $\pi(t)=n\mod 2$, as follows.

  * •

$\mathrm{Ob}(\mathcal{A}_{\mathbb{X}})\coloneqq\mathrm{Ob}(\mathcal{F}_{\mathbb{X}})=\mathbb{X}$

  * •

$\mathrm{Hom}_{\mathcal{A}_{\mathbb{X}}}(X,Y)\coloneqq\mathrm{Hom}_{\mathcal{F}_{\mathbb{X}}}(X,Y)[[t]]$

  * •

Structure maps: Modulo $t$, these are just the structure maps for
$\mathcal{F}_{\mathbb{X}}$. There are the following additional terms in higher
powers of $t$:

    1. 1∘.

For each $X\in\mathbb{X}$ and endpoint $p$ of $X$ with $p\in M^{\prime}$ there
is a term $\pm c_{p,X}t$ of $\mathfrak{m}_{0}\in\mathrm{Hom}^{2}(X,X)$, where
$c_{p,X}$ is the closed boundary path which starts and ends at $X$ and winds
$n/\mathrm{ind}(p)$ times around the component of $\partial\widehat{S}$
corresponding to $p\in M^{\prime}$. The sign is $+1$ (resp. $(-1)^{n}$) if $X$
points towards (resp. away from) $p$ with respect to the natural orientation
coming from the grading of $X$ and lift to $\Sigma$.

    2. 2∘.

Each immersed $2d$-gon with $k$ holes and associated cyclic sequence $a_{d}$,
$a_{d-1}$, …, $a_{1}$ contributes: a) a term
$(-1)^{nk\varepsilon_{-}(a_{1})}1_{X}t^{k}$ to
$\mathfrak{m}_{d}(a_{d},\ldots,a_{1})$, where $X$ is the arc where $a_{1}$
starts, b) a term $(-1)^{nk\varepsilon_{-}(a_{1})}bt^{k}$ to
$\mathfrak{m}_{d}(ba_{d},\ldots,a_{1})$, where $b$ is a boundary path which
stars where $a_{d}$ ends, and c) a term
$(-1)^{|b|+nk\varepsilon_{-}(b)}bt^{k}$ to
$\mathfrak{m}_{d}(a_{d},\ldots,a_{1}b)$, where $b$ is a boundary path which
ends where $a_{1}$ starts.

######  Proposition 4.13.

$\mathcal{A}_{\mathbb{X}}=\mathcal{A}_{\mathbb{X}}(S,M,\nu,M^{\prime},n)$ is a
curved $A_{\infty}$-category over $\mathbf{k}[[t]]$.

###### Proof.

The proof is the same as in [Hai24] except for the signs. More precisely, the
signs are the same if $n$ is odd and simplify in the case where $n$ is even,
so we will omit the (straightforward) checking of signs. ∎

We briefly recall some algebraic constructions from [Hai24]. Given any curved
$A_{\infty}$-category $\mathcal{A}$ over $\mathbf{k}[[t]]$ we obtain an
uncurved one ($\mathfrak{m}_{0}=0$) by passing to the $A_{\infty}$-category of
(not necessarily one-sided) twisted complexes $\mathrm{Tw}(\mathcal{A})$. An
object of $\mathrm{Tw}(\mathcal{A})$ is a pair $(X,\delta)$, where $X$ is an
object in the closure of $\mathcal{A}$ under finite direct sums and shift, and
$\delta\in\mathrm{Hom}^{1}(X,X)$ has $t^{0}$ term which is strictly upper-
triangular and $\delta$ satisfies the $A_{\infty}$ Maurer–Cartan equation.
Base change from $\mathbf{k}[[t]]$ to $\mathbf{k}$ gives a functor

$F\colon\mathrm{Tw}(\mathcal{A})\to\mathrm{Tw}^{+}\left(\mathcal{A}\otimes_{\mathbf{k}[[t]]}\mathbf{k}\right)$

which has a right adjoint, $G$, see [Hai24, Prop. 2.13]. Moreover, the counit
of the adjunction, $FG\to 1$, fits into an exact triangle of functors and
natural transformations

$[n-1,n]\longrightarrow FG\longrightarrow 1\longrightarrow[n,n]$ (4.4)

where $[n,k]$ is the shift in bi-degree
$(n,k)\in\mathbb{Z}\times\mathbb{Z}/2$. We denote by
$\mathrm{Tors}(\mathcal{A})$ the full triangulated subcategory of
$\mathrm{Tw}(\mathcal{A})$ which is generated by the image of $G$. By
restricting $F$ to $\mathrm{Tors}(\mathcal{A})$, we obtain an adjunction
between
$\mathrm{Tw}^{+}\left(\mathcal{A}\otimes_{\mathbf{k}[[t]]}\mathbf{k}\right)$
and $\mathrm{Tors}(\mathcal{A})$.

######  Remark 4.14.

Using more geometric language, $\mathcal{A}$ is a family of
$A_{\infty}$-categories over a formal disk (with coordinate in degree $2-n$).
Moreover,
$\mathcal{A}_{0}\coloneqq\mathcal{A}\otimes_{\mathbf{k}[[t]]}\mathbf{k}$ is
the central fiber of this family, $\mathrm{Tw}^{+}(\mathcal{A}_{0})$ are
objects living on the central fiber, and $\mathrm{Tors}(\mathcal{A})$ are
objects supported on the central fiber.

We apply these algebraic constructions to the curved $A_{\infty}$-category
$\mathcal{A}_{\mathbb{X}}$. It turns out that
$\mathrm{Tors}(\mathcal{A}_{\mathbb{X}})$ does not depend, up to coherent
quasi-equivalence, on the choice of arc system $\mathbb{X}$. This can be
proven in the same way as in [HKK17, Hai24]. Thus, we omit $\mathbb{X}$ from
the notation in the following definition.

######  Definition 4.15.

$\mathcal{C}(S,n)=\mathcal{C}(S,M,\nu,M^{\prime},n)\coloneqq\mathrm{Tors}(\mathcal{A}_{\mathbb{X}}(S,M,\nu,M^{\prime},n))$
is the triangulated $A_{\infty}$-category associated with the quintuple
$(S,M,\nu,M^{\prime},n)$.

By definition,
$\mathcal{A}_{\mathbb{X}}\otimes_{\mathbf{k}[[t]]}\mathbf{k}=\mathcal{F}_{\mathbb{X}}$,
so the right adjoint of the base change functor is a functor

$G\colon\mathcal{F}(S,M,\nu)=\mathrm{Tw}^{+}(\mathcal{F}_{\mathbb{X}})\to\mathrm{Tors}(\mathcal{A}_{\mathbb{X}})=\mathcal{C}(S,n).$
(4.5)

The following proposition gives an explicit description of
$\mathrm{Ext}^{i}$’s between those objects in $\mathcal{C}(S,n)$ which
correspond to arcs.

######  Proposition 4.16.

Let $\mathbb{X}$ be an arc system for $(S,M)$ which does not cut out any
1-gons, and $X,Y\in\mathbb{X}$. Then
$\mathrm{Ext}^{\bullet}_{\mathrm{Tw}(\mathcal{A}_{\mathbb{X}})}(X,Y)$ is the
cohomology of the complex

$\mathrm{Hom}_{\mathcal{F}_{\mathbb{X}}}(X,Y)\otimes\operatorname{H}^{\bullet}(S^{n-1};\mathbf{k}),\qquad
d(a+b\tau)=(-1)^{n}\mathfrak{m}_{2}(b,\mathfrak{m}_{0}t^{-1})$

where $\tau\in\operatorname{H}^{n-1}(S^{n-1};\mathbf{k})$ is the fundamental
class.

###### Proof.

By the formula for the cone over the counit (4.4), and adjunction, there is an
exact triangle of complexes

$\mathrm{Hom}_{\mathcal{F}_{\mathbb{X}}}(X,Y)\to\mathrm{Hom}_{\mathrm{Tw}(\mathcal{A}_{\mathbb{X}})}(GX,GY)\to\mathrm{Hom}_{\mathcal{F}_{\mathbb{X}}}(X[n-1],Y).$
(4.6)

The differential on $\mathrm{Hom}_{\mathcal{F}_{\mathbb{X}}}(X,Y)$ is trivial
by the assumption on $\mathbb{X}$. The formula for the differential can be
read off from

$F(G(X))=\left(X\oplus X[n-1,n],\begin{pmatrix}0&0\\\
(-1)^{n}\mathfrak{m}_{0}t^{-1}&0\end{pmatrix}\right)$

which can be found in [Hai24, Subsection 2.3]. ∎

######  Remark 4.17.

If $\partial S=\varnothing$, $M^{\prime}=M$, and either $n$ is odd or $\nu$
orientable, then one can show that $\mathcal{C}(S,n)$ is proper and
$n$-Calabi–Yau in the sense of proper $A_{\infty}$-categories over
$\mathbf{k}$. The proof is similar to the one in the special case $n=3$ found
in [Hai24].

###  4.2. Transfer of stability conditions

In this subsection we recall the main result about stability conditions from
[HKK17] and a theorem from [Hai24] which, put together, allow us to show that
certain components of the space of stability conditions of a full subcategory
of $\mathcal{C}(S,n)$ are identified with moduli spaces of quadratic
differentials.

Let us first recall the main result of [HKK17]. Let $C$ be a compact Riemann
surface and $\varphi$ a quadratic differential which is holomorphic and non-
vanishing away from a finite set $D\subset C$ where $\varphi$ is allowed to
have zeros, poles and exponential singularities. Let us discuss how to obtain
a triple $(S,M,\nu)$ from $(C,\varphi)$. In the case where $\varphi$ has no
exponential singularities, we can simply take $S=C$, $M=D$, and $\nu$ to be
the horizontal foliation of $\varphi$. In general, $S$ will be a compact
surface with boundary embedded in $C$, which is the complement of a small open
disk around each exponential singularity. Moreover, for each exponential
singularity $z\in C$ with corresponding component $B\subset\partial S$, which
is the boundary of the open disk around $z$, and set
$E\subset\overline{C\smallsetminus D}$ of infinite-angle conical points
($\overline{C\smallsetminus D}$ is the completion with respect to the metric
$|\varphi|$), we have a set of non-intersecting paths in
$\overline{C\smallsetminus D}$, one from each point in $E$ to a point in
$M\cap B$.

If $\varphi$ has no higher order ($\geq 2$) poles, then it is shown in [HKK17]
that there is a stability condition on $\mathcal{F}(S,M,\nu)$ so that, roughly
speaking, $Z$ is given by integrating $\sqrt{\varphi}$ and semistable objects
correspond to geodesics on the flat surface $\overline{C\smallsetminus D}$. In
the presence of higher order poles this still works, but one first needs to
pass to a full subcategory
$\mathcal{F}_{\mathrm{len}}(S,M,\nu)\subset\mathcal{F}(S,M,\nu)$ of those
objects which are supported away from the higher order poles (otherwise
$Z(E)=\infty$). Here we use the correspondence of objects in
$\mathcal{F}(S,M,\nu)$ and curves on $S$ with extra data.

Instead of fixing $(C,\varphi)$ we can consider the moduli space of such pairs
which give rise to equivalent marked surfaces $(S,M,\nu)$. Thus, as in
[HKK17], we let $\mathcal{M}(S,M,\nu)$ be the space of pairs $(C,\varphi)$
corresponding to a marked surface $(S^{\prime},M^{\prime},\nu^{\prime})$ as
above, together with a diffeomorphism $f\colon S^{\prime}\to S$ with
$f(M^{\prime})=M$ and a homotopy class of paths between $f_{*}\nu^{\prime}$
and $\nu$ as sections of $\mathbb{P}(TS)|_{S\smallsetminus M}$. Passing from
$\varphi$ to the cohomology class of $\sqrt{\varphi}$ gives a local
homeomorphism

$\mathcal{M}(S,M,\nu)\longrightarrow\mathrm{Hom}(\Gamma_{S,M,\nu},\mathbb{C})$
(4.7)

where

$\Gamma_{S,M,\nu}\coloneqq H_{1}(S,M;\mathbb{Z}\otimes_{\mathbb{Z}/2}\Sigma)$
(4.8)

and $\Sigma\to S\smallsetminus M$ is the double cover of orientations of
$\nu=\mathrm{hor}(\varphi)$ as before.

The main result of [HKK17] is the following.

######  Theorem 4.18.

Fix a triple $(S,M,\nu)$. Then there is a canonical map

$\mathcal{M}(S,M,\nu)\longrightarrow\mathrm{Stab}\left(\mathcal{F}_{\mathrm{len}}(S,M,\nu)\right)$
(4.9)

which is biholomorphic onto a union of connected components.

We will combine the above theorem with the following result from [Hai24].

######  Theorem 4.19.

Let $G\colon\mathcal{C}\to\mathcal{D}$ be an exact functor between
triangulated categories such that:

  1. 1∘.

$G$ has a left adjoint $F\colon\mathcal{D}\to\mathcal{C}$ and there exists an
$n\geq 3$, such that

$\mathrm{Cone}\left(\varepsilon_{X}\colon FGX\to X\right)\cong X[n]\,,$ (4.10)

for any $X\in\mathcal{C}$, where $\varepsilon$ denotes the counit of the
adjunction.

  2. 2∘.

The image of $G$ generates $\mathcal{D}$ under direct sums, shifts, and cones.

  3. 3∘.

$\mathcal{C}$ admits a bounded t-structure.

Then $K_{0}(G)$ induces an isomorphism $K_{0}(\mathcal{C})\to
K_{0}(\mathcal{D})$ and there is a pushforward map

$G_{*}\colon\mathrm{Stab}(\mathcal{C},\Gamma,\mathrm{cl})\longrightarrow\mathrm{Stab}\left(\mathcal{D},\Gamma,\mathrm{cl}\circ\left(K_{0}(G)\right)^{-1}\right)$
(4.11)

which is a biholomorphism onto its image which is a union of connected
components. Given a stability condition on $\mathcal{C}$ its image under
$G_{*}$ has the same central charge and
$\mathcal{D}_{\phi}=G(\mathcal{C}_{\phi})$.

We apply the above theorem to the case where
$\mathcal{C}=\mathcal{F}_{\mathrm{len}}(S,M,\nu)$ and $\mathcal{D}$ is the
full triangulated subcategory, denoted $\mathcal{C}_{\mathrm{len}}(S,n)$, of
$\mathcal{C}(S,n)$ generated by the image of $\mathcal{C}$ under the functor
$G$ from (4.5). If there exist no $p\in M\cap\mathrm{int}(S)$ with
$\mathrm{ind}(p)\leq 0$, then
$\mathcal{C}_{\mathrm{len}}(S,n)=\mathcal{C}(S,n)$.

######  Theorem 4.20.

Fix a quintuple $(S,M,\nu,M^{\prime},n)$ with $n\geq 3$, then there is a
canonical map

$\mathcal{M}(S,M,\nu)\longrightarrow\mathrm{Stab}\left(\mathcal{C}_{\mathrm{len}}(S,n)\right)$

which defines a biholomorphism with a union of connected components.

###### Proof.

Follows from Theorem 4.18 and Theorem 4.19. The assumptions of the latter
theorem are satisfied by (4.4). ∎

###  4.3. Relation to RGB algebras

In this subsection we restrict to the case of quadratic differentials of
infinite area and show that a full subcategory of
$\mathcal{C}_{\mathrm{len}}(S,n)$ (often equal to the whole category) has a
generator whose Yoneda algebra is an RGB algebra in the sense of Section 2.

In [CHQ23, Subsection 2.3] we described the mixed-angulation and dual S-graph
of a generic quadratic differential of infinite area, generalizing the “WKB
triangulation” in the case of simple zeros. We can consider each edge, $e$, of
the S-graph as an object, $X_{e}\in\mathcal{F}_{\mathrm{len}}(S,M,\nu)$ in the
Fukaya category. There is a canonical choice of grading (branch of
$\mathrm{Arg}$) such that $\mathrm{Arg}(\sqrt{\varphi})|_{e}\in(0,\pi)$.

######  Definition 4.21.

Let
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)\subset\mathcal{F}_{\mathrm{len}}(S,M,\nu)$
be the full triangulated subcategory generated by the edges of an S-graph.

If $\varphi$ has no second order pole, then
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)=\mathcal{F}_{\mathrm{len}}(S,M,\nu)$,
i.e. edges generate the entire category, see [HKK17, Proposition 6.2]. If
$\varphi$ has at least one second order pole, then
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)$ is an orthogonal summand of
$\mathcal{F}_{\mathrm{len}}(S,M,\nu)$ whose orthogonal complement is a direct
sum of copies of the category $D^{b}(\mathrm{Rep}(\mathbf{k}\mathbb{Z}))$, the
bounded derived category of finite-dimensional representations of the group
$\mathbb{Z}$ over $\mathbf{k}$, with one such copy for each second order pole.
This follows from the classification of objects in $\mathcal{F}(S,M,\nu)$, see
[HKK17, Theorem 4.3], where an orthogonal summand of the form
$D^{b}(\mathrm{Rep}(\mathbf{k}\mathbb{Z}))$ corresponds to objects supported
on a simple loop around the second order pole. We note that
$\mathcal{F}_{\mathrm{len}}(S,M,\nu)$ and
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)$ have the same spaces of stability
conditions, provided we choose $\Gamma$ as a first homology group as in
[HKK17], since the objects in the any orthogonal summand corresponding to a
double pole are necessarily semistable.

The point of the previous paragraph is that we might as well restrict to
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)$, which is compactly generated. The
endomorphism algebra of the generator $E\coloneqq\bigoplus_{e}X_{e}$ turns out
to have a very simple structure: It is formal and determined by a graded
quiver with quadratic relations, see the proposition below. This is shown in
[HKK17, Section 6.1].

######  Proposition 4.22.

Let $E\coloneqq\bigoplus_{e}X_{e}$ be the generator of
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)$ given by the direct sum of all edges of
a fixed S-graph $\mathbb{S}$. Then the $A_{\infty}$-structure maps
$\mathfrak{m}_{d}$ of $\mathrm{End}(E)$ vanish for $d\neq 2$, i.e.
$\mathrm{End}(E)$ is essentially a graded algebra. Moreover, this algebra has
the following description in terms of a graded quiver $Q$ with relations:

  1. 1∘.

Vertices are the edges of $\mathbb{S}$.

  2. 2∘.

Arrows $a_{i}$ correspond to pairs $(i,i+1)$ of consecutive halfedges
(“corners”) of $\mathbb{S}$ with degree given by $d(i,i+1)\in\mathbb{Z}$.

  3. 3∘.

Relations are quadratic of the form $a_{j}a_{i}=0$ if $i+1\neq j$ are
halfedges belonging to the same edge.

We assume from now on that $n\geq 1$ and that $M^{\prime}$ includes all the
zeros and simple poles of $\varphi$, i.e. $M^{\prime}\subset M$ is maximal.
This is to ensure that we get a proper dg-algebra.

The following theorem describes the endomorphism algebra of the corresponding
generator of
$\mathcal{C}_{\mathrm{core}}(S,n)=\mathcal{C}_{\mathrm{core}}(S,M,\nu,M^{\prime},n)$
which is by definition the triangulated closure of the image of
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)$ in $\mathcal{C}(S,M,\nu,M^{\prime},n)$.
Recall that if there are no second order poles, then
$\mathcal{F}_{\mathrm{core}}(S,M,\nu)=\mathcal{F}_{\mathrm{len}}(S,M,\nu)$ and
thus we also get
$\mathcal{C}_{\mathrm{core}}(S,n)=\mathcal{C}_{\mathrm{len}}(S,n)$.

######  Theorem 4.23.

Let $E\coloneqq\bigoplus_{e}X_{e}$ be the generator of
$\mathcal{C}_{\mathrm{core}}(S,n)$ given by the direct sum of all edges of a
fixed S-graph $\mathbb{S}$. Then $\mathrm{End}(E)$ is quasi-isomorphic to the
finite-dimensional dg-algebra $A(\mathbb{S},n)$ defined in Section 2.

###### Proof.

Let $\mathbb{G}$ be the collection of arcs which are edges of the S-graph and
extend this to an arc system $\mathbb{X}$ of $(S,M)$. The curved
$A_{\infty}$-category $\mathcal{A}_{\mathbb{X}}$, whose objects are the arcs
in $\mathbb{X}$, has a full subcategory, denoted $\mathcal{A}_{\mathbb{G}}$,
whose objects are the arcs in $\mathbb{G}$, i.e. edges of the S-graph. Since
the S-graph is a deformation retract of the surface, the arcs in $\mathbb{G}$
do not cut out any polygons, and thus there are no contributions to the
structure constants of $\mathcal{A}_{\mathbb{G}}$ from immersed $2d$-gons. In
particular, $\mathfrak{m}_{d}=0$ for $d\neq 0,2$, so
$\mathcal{A}_{\mathbb{G}}$ is essentially a curved algebra. By construction,
$E\in\mathrm{Tw}(\mathcal{A}_{\mathbb{G}})=\mathcal{C}_{\mathrm{core}}(S,M,\nu)$
is the twisted complex

$G(E^{\prime})=\left(\mathcal{A}_{\mathbb{G}}\oplus\mathcal{A}_{\mathbb{G}}[1-n,n],\begin{pmatrix}0&t\\\
(-1)^{n}\mathfrak{m}_{0}t^{-1}&0\end{pmatrix}\right)$ (4.12)

where $E^{\prime}\in\mathcal{F}_{\mathbb{X}}$ is the object given by the
direct sum of edges in $\mathbb{G}$. Thus $\mathrm{End}(E)$ is the dg-algebra
of 2-by-2 matrices in $\mathcal{A}_{\mathbb{G}}$ with differential given by
the commutator with the matrix appearing in (4.12).

We already know from Proposition 4.16 that the chain complex underlying
$\mathrm{End}(E)$ is quasi-isomorphic to the chain complex

$\mathcal{F}_{\mathbb{G}}[\tau]/\tau^{2},\qquad
d(a+b\tau)=(-1)^{n}\mathfrak{m}_{2}(b,\mathfrak{m}_{0}t^{-1}).$

This chain complex has a natural dg-algebra structure, where $\tau$ is given
bi-degree $(|\tau|,\pi(\tau))=(n-1,n)\in\mathbb{Z}\times\mathbb{Z}/2$ and
required to be central in the $\mathbb{Z}\times\mathbb{Z}/2$-graded sense,
i.e.

$\tau a=(-1)^{(n-1)|a|+n\pi(a)}a\tau$

which forces $\tau^{2}=0$. Moreover, it is naturally a sub-dg-algebra of
$\mathrm{End}(E)$ via the inclusion map

$a+b\tau\mapsto\begin{pmatrix}a&0\\\ b&a\end{pmatrix}$

which is a quasi-isomorphism of dg-algebras.

Given a halfedge $i$ belonging to an edge $e$ of the S-graph, let
$\tau_{i}\coloneqq(-1)^{n\varepsilon(i)}1_{e}\tau$, where $1_{e}$ is the
idempotent corresponding to $e$ and $\varepsilon(i)$ is $0$ (resp. $1$) if $e$
points away from (resp. towards) $i$. Because of
$|a|+\pi(a)=\varepsilon_{-}(a)+\varepsilon_{+}(a)\mod 2$ we then get
$a_{i}\tau_{i}=(-1)^{|a_{i}|}\tau_{i+1}a_{i}$. Also,
$\tau_{i}=(-1)^{n}\tau_{j}$ if $i\neq j$ belong to the same edge.

For any halfedge $i$ define $c_{i}$ as in Definition 2.8, then $c_{i}$ is
equal, up to sign, to $c_{p,X}$ from Definition 4.12 where $i$ belongs to the
edge $X$ and ends at $p$. Consider the ideal
$I\subset\mathcal{F}_{\mathbb{G}}[\tau]/\tau^{2}$ generated by

  * •

$\tau_{i}$ and $d(\tau_{i})=c_{i}+(-1)^{n}c_{j}$ for those halfedges $i$
belonging to an edge $\\{i,j\\}$ of the S-graph attached to internal vertices
only,

  * •

$a_{i}\tau_{i}$ and $d(a_{i}\tau_{i})=\pm a_{i}c_{i}$ if $i$ is a halfedge
attached to an internal vertex.

Since $I$ consists of pairs of basis elements and their images under $d$, it
is acyclic and therefore $\mathcal{F}_{\mathbb{G}}[\tau]/\tau^{2}$ is quasi-
isomorphic to the quotient dg-algebra
$\left(\mathcal{F}_{\mathbb{G}}[\tau]/\tau^{2}\right)/I$, which is precisely
$A(\mathbb{S},n)$. ∎

######  Remark 4.24.

As a consequence of the above theorem and the independence of the
$A_{\infty}$-category $\mathcal{C}_{\mathrm{core}}(S,n)$ on the choice of arc
system, we find that the derived Morita equivalence class of $A(\mathbb{S},n)$
only depends on $S$, $M$, $\nu$, and $n$ ($M^{\prime}$ was assumed to be
maximal). In the case of usual (ungraded) Brauer graph algebras, an analogous
result was established in [OZ22] likewise using $A_{\infty}$-structures and
arc systems.

## References

  * [AL17] R. Anno and T. Logvinenko.  Spherical DG-functors.  J. Eur. Math. Soc., 19:2577–2656, 2017.
  * [Ami11] C. Amiot.  On generalized cluster categories.  arXiv:1101.3675, 2011.
  * [BD19] C. Brav and T. Dyckerhoff.  Relative Calabi-Yau structures.  Compos. Math., 155(2):372–412, 2019.
  * [BMQS24] Anna Barbieri, Martin Möller, Yu Qiu, and Jeonghoon So.  Quadratic differentials as stability conditions: collapsing subsurfaces.  J. Reine Angew. Math., 810:49–95, 2024.  arxiv:2212.08433.
  * [CHQ23] M. Christ, F. Haiden, and Y. Qiu.  Perverse schobers, stability conditions and quadratic differentials I.  arXiv:2303.18249, 2023.
  * [Chr21] M. Christ.  Geometric models for derived categories of Ginzburg algebras of $n$-angulated surfaces via local-to-global principles.  arXiv:2107.10091, 2021.
  * [Chr22a] M. Christ.  Cluster theory of topological Fukaya categories.  arXiv:2209.06595, 2022.
  * [Chr22b] M. Christ.  Ginzburg algebras of triangulated surfaces and perverse schobers.  Forum Math. Sigma, 10:e8, 2022.
  * [Chr23] M. Christ.  Relative Calabi-Yau structures and perverse schobers on surfaces.  arXiv:2311.16597, 2023.
  * [Cis19] D. Cisinski.  Higher categories and homotopical algebra.  Cambridge Studies in Advanced Mathematics 180, Cambridge University Press, 2019.
  * [DF78] P. W. Donovan and M.-R. Freislich.  The indecomposable modular representations of certain groups with dihedral Sylow subgroup.  Math. Ann., 238:207–216, 1978.
  * [DK15] T. Dyckerhoff and M. Kapranov.  Crossed simplicial groups and structured surfaces.  Stacks and categories in geometry, topology, and algebra, Contemp. Math., 643, Amer. Math. Soc., Providence, RI, pages 37–110, 2015.
  * [DK18] T. Dyckerhoff and M. Kapranov.  Triangulated surfaces in triangulated categories.  J. Eur. Math. Soc. (JEMS), 20(6):1473–1524, 2018.
  * [DKSS21] T. Dyckerhoff, M. Kapranov, V. Schechtman, and Y. Soibelman.  Spherical adjunctions of stable $\infty$-categories and the relative S-construction.  arXiv:2106.02873, 2021.
  * [Gne19] Wassilij Gnedin.  Calabi-Yau properties of ribbon graph orders, 2019.  arXiv:1908.08895.
  * [GS20] J. P. C Greenlees and G. Stevenson.  Morita theory and singularity categories.  Adv. Math., 365:51, 2020.  Id/No 107055.
  * [GSS14] Edward L. Green, Sibylle Schroll, and Nicole Snashall.  Group actions and coverings of Brauer graph algebras.  Glasg. Math. J., 56(2):439–464, 2014.
  * [Hai24] F. Haiden.  3-d Calabi–Yau categories for Teichmüller theory.  Duke Math. J., 173(2):277–346, 2024.  arxiv:2104.06018.
  * [HKK17] F. Haiden, L. Katzarkov, and M. Kontsevich.  Flat surfaces and stability structures.  Publ. Math. Inst. Hautes Études Sci,, 126(1):247–318, 2017.
  * [Kel] B. Keller.  Koszul duality and coderived categories (after K. Lefèvre).  available on the author’s webpage: https://webusers.imj-prg.fr/$\sim$bernhard.keller/publ/kdc.pdf.
  * [KQ20] Alastair King and Y. Qiu.  Cluster exchange groupoids and framed quadratic differentials.  Invent. Math., 220(2):479–523, 2020.
  * [KS14] M. Kapranov and V. Schechtman.  Perverse Schobers.  arXiv:1411.2772, 2014\.
  * [KW24] O. Kidwai and N. Williams.  Donaldson-Thomas invariants for the Bridgeland-Smith correspondence.  arXiv:2401.10093, 2024.
  * [LFM24] Daniel Labardini-Fragoso and Lang Mou.  Gentle algebras arising from surfaces with orbifold points of order 3\. I: Scattering diagrams.  Algebr. Represent. Theory, 27(1):679–722, 2024.  arXiv:2203.11563.
  * [LH03] K. Lefèvre-Hasegawa.  Sur les A-infinity catégories.  PhD thesis, Paris Diderot University, 2003.
  * [LM20] Patrick Le Meur.  Crossed products of Calabi-Yau algebras by finite groups.  J. Pure Appl. Algebra, 224(10):43, 2020.  Id/No 106394.
  * [Lur17] J. Lurie.  Higher Algebra.  preprint, available on the author’s webpage, 2017.
  * [OZ22] Sebastian Opper and Alexandra Zvonareva.  Derived equivalence classification of Brauer graph algebras.  Adv. Math., 402:59, 2022.  Id/No 108341.
  * [Qiu16] Y. Qiu.  Decorated marked surfaces: spherical twists versus braid twists.  Math. Ann. 365, 595-633, 2016.
  * [Sch18] S. Schroll.  Brauer graph algebras. A survey on Brauer graph algebras, associated gentle algebras and their connections to cluster theory.  In Homological methods, representation theory, and cluster algebras. Based on six mini-courses, CIMPA, Mar del Plata, Argentina, March 7–18, 2016, pages 177–223. Cham: Springer; Montreal: Centre de Recherches Mathématiques (CRM), 2018.
  * [VdB15] M. Van den Bergh.  Calabi-Yau algebras and superpotentials.  Sel. Math., New Ser., 21(2):555–603, 2015.


# Estimating HIV Epidemics for Sub-National Areas

Le<EMAIL_ADDRESS>[ Xiaoyue Niu1 Mary Mahy2 Peter D. Ghys2
Department of Statistics, Penn State University, University Park, PA, USA1
UNAIDS, Strategic Information and Evaluation Department, Geneva, Switzerland2

###### Abstract

As the global HIV pandemic enters its fourth decade, increasing numbers of
surveillance sites have been established which allows countries to look into
the epidemics at a finer scale, e.g. at sub-national levels. Currently, the
epidemic models have been applied independently to the sub-national areas
within countries. However, the availability and quality of the data vary
widely, which leads to biased and unreliable estimates for areas with very few
data. We propose to overcome this issue by introducing the dependence of the
parameters across areas in a mixture model. The joint distribution of the
parameters in multiple areas can be approximated directly from the results of
independent fits without needing to refit the data or unpack the software. As
a result, the mixture model has better predictive ability than the independent
model as shown in examples of multiple countries in Sub-Saharan Africa.

HIV epidemics,

Hierarchical model,

Mixture model,

Importance sampling,

###### keywords:

and and and

##  1 Introduction

Since the first case reported in 1981 [Centers for Disease Control (1981)],
the global HIV epidemic has become one of the greatest threats to human health
and development. The number of people living with HIV worldwide continued to
grow, reaching 35 million in 2013, about three times more than in 1990. There
have been 78 million infected with HIV and over 29 million AIDS-related deaths
so far. The response to the HIV epidemic has been mixed, with progress being
made to reduce new infection and rapid improvements in survival rates among
AIDS patients as antiretroviral therapy has become available in recent years
[UNAIDS (2014)].

Countries need to ground their HIV strategies in an understanding of their own
epidemics and their national responses. Reliable estimation and prediction of
the HIV epidemic can help policy makers and program planners efficiently
allocate their resources, plan and manage the intervention, treatment and care
programs, evaluate their effort, and raise funds. Therefore, accurate
estimation and projection of the epidemic is the foundation of all HIV-related
studies [UNAIDS/WHO Working Group on Global HIV and STI Surveillance (2013)].
In addition, countries – especially large countries and countries with
geographically heterogeneous epidemics – need to understand the variation of
the impact within the country by geographic area and population Mahy2014.
Having surveillance data and HIV estimates available by sub-national entities
helps allocating limited resources [UNAIDS (2013)].

Most countries (158 countries submitted files in 2014) use Spectrum software
to estimate the impact of HIV on their population at the national level
Case2014. Spectrum relies on data from HIV surveillance systems and the
Estimation and Projection Package (EPP) to estimate trends in HIV incidence
over time Spectrum2014,Brown2014,Stover2014. The UNAIDS Reference Group on
Estimates, Modelling and Projections has developed, and continues to refine
Spectrum/EPP for estimation and short-term prediction of HIV trends
Ghys2004,Brown2006,Brown2010,Brown2014. Due to the paucity of reliable
information on the incidence of HIV in most countries, sentinel surveillance
systems for HIV were designed to monitor the HIV prevalence trends. Using
these surveillance data from 1970 through the current year, EPP reconstructs
trends in HIV prevalence, incidence and mortality and makes short term
projections.

As the global HIV pandemic enters its fourth decade, increasing numbers of
surveillance sites have been established which allows countries to look into
the epidemics at a finer scale, e.g. at sub-national level. Most countries
with generalized epidemics (epidemics in which HIV transmission is primarily
in the general population through heterosexual sex) have historical HIV
surveillance data from women attending antenatal clinics from year 2000 to
present. In addition, all but four generalized epidemic countries have
household surveys that measure the HIV prevalence in the national population
as well as sub-national estimates to the first sub-national administrative
level Marsh2014. Currently, the estimation and projection process has been
implemented independently for areas in those countries. However, the
availability and quality of HIV surveillance data used for these models is
variable Calleja2010. Some key components of data availability and quality
include the number of years of data to show trends over time, the
representativeness of the data across the country, and the accuracy of those
data Lyerla2008. When the sub-national areas do not have sufficient high
quality data the models produce inaccurate results with large uncertainty
bounds.

One way to improve accuracy of the estimates is to borrow information from
neighboring areas in the case of sub-national estimates. For example many
areas have few data points early in the HIV epidemic (between 1980 and 2000).
In such situation, if the data from neighboring areas are assumed to have
similar trends, the trends from those areas can be used to inform the one in
the lack-of-data area. In this paper we introduce an informative prior
distribution derived from the mixture model to allow sharing information
across datasets. In the mixture model, the epidemiologically implausible
trajectories fit in the area with few data would be down-weighted by the area
with rich data. The difficulty of utilizing the proposed model is that the
underlying epidemic model is described by differential equations, and the
computational cost of fitting such a model is high because the model
parameters do not have analytic solutions. In this article, we propose an
importance sampling method that draws posterior samples of parameters in the
new model without needing to refit the data.

In Section 2 we describe the EPP model used by UNAIDS, the mixture model, the
parameter estimation, and the evaluation procedure in detail. In Section 3, we
give results for 20 countries in Sub-Saharan Africa, and in Section 4 we offer
conclusions and discussion for future work.

##  2 Approach

In this section, we first describe a dynamic model used by EPP for estimating
and projecting the HIV epidemic from prevalence data. We then introduce the
mixture model that allows information to be shared across areas with similar
epidemiological patterns. After that we propose a novel parameter estimation
method for the mixture model that avoids additional runs of the dynamic model.
Finally we discuss the model evaluation procedure.

###  2.1 The EPP Model

The Estimation and Projection Package (EPP) is based on a simple susceptible-
infected (SI) epidemiological model. The dynamic model is as follows :

$\left\\{\begin{array}[]{ccc}\frac{dZ(t)}{dt}&=&E(t)-r(t)\rho(t)Z(t)-\mu(t)Z(t)-a_{50}(t)Z(t)+M(t)Z(t),\\\
\frac{dY(t)}{dt}&=&r(t)\rho(t)Z(t)-\textup{HIVdeath}(t)-a_{50}(t)Y(t)+M(t)Y(t),\\\
\end{array}\right.$ (1)

The population being modeled is aged between 15 and 49, and the population at
time $t$ is divided into two groups: $Z(t)$ is the number of uninfected
individuals, $Y(t)$ is the number of infected individuals, $N(t)=Z(t)+Y(t)$ is
the total adult population size, $E(t)$ is the number of new adults entering
the population, $\rho(t)=Y(t)/N(t)$ is the prevalence rate, and
$\textup{HIVdeath}(t)$ is the number of deaths among infected individuals.
There is a set of parameters defined by external life-tables such as $\mu(t)$,
the non-AIDS mortality rate; $a_{50}(t)$, the rate at which adults exit the
model after attaining age 50, and $M(t)$, the rate of net migration into the
population.

The infection rate, $r(t)$, is the expected number of persons infected by one
HIV positive person in year $t$ in a wholly susceptible population $Z(t)$, and
is assumed to have the following form:

$\log r(t+1)-\log
r(t)=\beta_{1}\times(\beta_{0}-r(t))-\beta_{2}\rho(t)+\beta_{3}\gamma(t),$ (2)

where $\gamma_{t}=\frac{(\rho(t+1)-\rho(t))(t-t_{1})^{+}}{\rho(t)}$ implies
the tendency of stabilization after year $t_{1}$. Therefore, Equation (2)
imposes some common structure on the changes of $r(t)$ across countries:
$r(t)$ declines if $r(t)>\beta_{0}$, or $\rho(t)$ is too high, or the relative
increase of prevalence is too large. Furthermore, we define $t_{0}$ as the
start year of the epidemic at which the prevalence is 0.0025%, and let $r_{0}$
be the infection rate at $t_{0}$.

The data for EPP model estimation mainly come from ANC data which consist of
the number of infected women $Y_{it}$ and the number of women tested $N_{it}$,
for a given year $t$ and a given clinic $i$. Let
$W_{it}=\Phi^{-1}(\frac{Y_{it}+0.5}{N_{it}+1})$, where $\Phi^{-1}(.)$ is the
inverse cumulative distribution function of the standard normal distribution.
The data and the population prevalence – $\rho(t)$ – derived from the dynamic
system (1) are linked through a random effect model:

$\displaystyle W_{it}$ $\displaystyle=$
$\displaystyle\Phi^{-1}(\rho_{t})+\beta_{4}+b_{i}+\epsilon_{it},$
$\displaystyle b_{i}$ $\displaystyle\sim$ $\displaystyle N(0,\sigma^{2}),$ (3)
$\displaystyle\epsilon_{it}$ $\displaystyle\sim$ $\displaystyle N(0,\nu_{it})$

where $\beta_{4}$ is the bias of ANC data with respect to prevalence data from
national population-based household surveys (NPBS) [Bao (2012)], and $b_{i}$
is the clinic random effect. $\sigma^{2}$ is assumed to have an inverse-Gamma
prior which gets integrated out in the likelihood evaluation. $\nu_{it}$ is a
fixed quantity that depends on the clinic data and approximates the binomial
variation [Alkema et al. (2007)].

With each input set,
$\boldsymbol{\theta}=(t_{0},t_{1},r_{0},\beta_{0},\beta_{1},\beta_{2},\beta_{3},\beta_{4})$,
from Equation (1) and (2), there is a series of output $\rho(t)$, which get
evaluated in the likelihood based on Equation (3). With a set of informative
priors incorporating empirical evidence and expert opinions as in Equations
(4), Bayesian inference of the population prevalence, incidence and mortality
(all derived from the dynamic system) can be performed for the EPP model [Bao
(2012)]. To be specific, the following informative prior distributions are
used:

$\begin{array}[]{ccl}t_{0}&\sim&\textup{Uniform}[1970,1990],\\\
t_{1}&\sim&T_{(2)}(20,0.458),\\\ \log r_{0}&\sim&T_{(2)}(0.42,0.081),\\\
\beta_{0}&\sim&T_{(2)}(0.46,0.192),\\\ \beta_{1}&\sim&T_{(2)}(0.17,0.091),\\\
\beta_{2}&\sim&T_{(2)}(-0.68,0.264),\\\
\beta_{3}&\sim&T_{(2)}(-0.038,0.009),\\\
\beta_{4}&\sim&T_{(2)}(0.14,0.068).\end{array}$ (4)

where $T_{(2)}(\mu_{0},\sigma_{0}^{2})$ is a t-distribution with location
parameter $\mu_{0}$, scale parameter $\sigma_{0}$, and 2 degrees of freedom.
The $T_{(2)}$ distribution has infinity variance which ensures a good coverage
of all possible parameter values. For simplicity,
$(t_{0},t_{1},r_{0},\beta_{0},\beta_{1},\beta_{2},\beta_{3},\beta_{4})$ are
assumed to be independent in the prior distribution. The dynamic model runs at
a 0.1-year time step, so $t_{0}$ and $t_{1}$ will be rounded into one decimal
place when calculating the likelihood.

###  2.2 The Mixture Model

In the current EPP implementation, all areas apply the same prior in Equation
(4) independently. We refer to the current model using prior (4) as the
independent model. The availability and quality of the data vary from area to
area. In areas with sufficient data, the independent model can work reasonably
well, while in data scarce areas it would result in unreliable estimates. One
way to overcome this issue in the data scarce areas is to borrow information
from other areas with similar epidemic trends, such as areas within the same
country. A hierarchical structure can be useful in associating parameters
among areas, as illustrated in Figure 1. We see that the sub-national
parameter estimates affect each other through the national parameter
estimates.

$\boldsymbol{\mu}_{\textrm{country}}$$\boldsymbol{\theta}_{\textrm{urban}}$$\boldsymbol{\theta}_{\textrm{rural}}$Urban
DataRural Data Figure 1: A hierarchical structure for input parameters of EPP.

For each country, let
$\boldsymbol{\theta}_{i}=(t_{i0},t_{i1},r_{i0},\beta_{i0},\beta_{i1},\beta_{i2},\beta_{i3},\beta_{i4})$
be the parameters of area $i$, so $\theta_{ij}$ is the $j$th parameter in the
$i$th area, with $j=1,2,...,8$ and $i=1,2,...,K$. To implement a structure as
in Figure 1, we can assume the following model:

$\displaystyle\theta_{ij}|\mu_{j},\sigma_{j}^{2}$ $\displaystyle\sim$
$\displaystyle N[\mu_{j},(1-\rho_{0j})\sigma_{j}^{2}],$
$\displaystyle\mu_{j}|\sigma_{j}^{2}$ $\displaystyle\sim$ $\displaystyle
N[\mu_{0j},\rho_{0j}\sigma_{j}^{2}],$ (5) $\displaystyle\sigma_{j}^{2}$
$\displaystyle\sim$ $\displaystyle\textup{InverseGamma}[a_{0j},b_{0j}],$

where $\mu_{0j}$, $\rho_{0j}$, $a_{0j}$ and $b_{0j}$ are hyperparameters.
Integrating out $\mu_{j}$ and $\sigma_{j}^{2}$, we get the joint distribution
of $(\theta_{1j},\theta_{2j},\ldots,\theta_{Kj})$,

$\begin{bmatrix}\theta_{1j}\\\ \theta_{2j}\\\ \vdots\\\
\theta_{Kj}\end{bmatrix}\sim\textup{MVT}_{(2a_{0j})}\left(\begin{bmatrix}\mu_{0j}\\\
\mu_{0j}\\\ \vdots\\\
\mu_{0j}\end{bmatrix},\sigma_{0j}^{2}\times\begin{bmatrix}1&\rho_{0j}&\ldots&\rho_{0j}\\\
\rho_{0j}&1&\ldots&\rho_{0j}\\\ \ldots&\ldots&\ldots&\ldots\\\
\rho_{0j}&\rho_{0j}&\ldots&1\end{bmatrix}\right),$ (6)

which is a multivariate $t$-distribution with $\sigma_{0j}^{2}=b_{0j}/a_{0j}$.
Setting $a_{0j}=1$, $\mu_{0j}$ and $\sigma_{0j}$ to be the means and standard
deviations in Equation (4), we have the same marginal distributions between
the hierarchical model (5) and the independent model (4) except for $t_{0}$.
$t_{0}$ follows a uniform distribution ranging from 1970 to 1990 in the
independent model, and a truncated t-distribution also ranging from 1970 and
1990 in the hierarchical model, and those two distributions have the same mean
and variance. As a result, the hierarchical model and the independent model
mainly differ in whether allowing correlations between parameters from
different areas.

As mentioned above, the independent prior (4) works reasonably well in areas
with sufficient data. Moreover, even within the same country, different areas
could have heterogeneous epidemics so that the parameters are not obviously
correlated. While on the other hand, for some other areas with fewer data, the
correlated structure (6) is critical in achieving a reliable estimate. In
order for the priors to be flexible enough to accommodate both situations, we
propose the following mixture model: let $f_{0j}$ be the prior density of the
independent model (4) and $f_{1j}$ be the prior density of the hierarchical
model (6) when $\rho_{0j}\neq 0$, and define the mixture model $g_{j}$ as the
following:

$g_{j}(\boldsymbol{\theta}_{j})=\pi_{0j}f_{0j}(\boldsymbol{\theta}_{j})+(1-\pi_{0j})f_{1}(\boldsymbol{\theta}_{j}|\mu_{0j},\sigma_{0j}^{2},\rho_{0j}),$
(7)

where $\pi_{0j}$ is the mixing probability or the weight of the independent
model that we will determine together with $\rho_{0j}$. The resulting mixture
model (7) accounts for the model uncertainty.

###  2.3 Hyperparameters

We first need to determine a reasonable set of the hyperparameters
$\boldsymbol{\rho_{0}}$ and $\boldsymbol{\pi_{0}}$. Here we adopt the
empirical Bayes framework by using the point estimates from countries with
multiple datasets. Let $\hat{\theta}_{icj}$ be the posterior mean of the $j$th
parameter obtained from fitting the independent model to the $i$th area of a
high-data-quality country $c$. $\pi_{0j}$ and $\rho_{0j}$ could be estimated
by maximizing the likelihood with known $\mu_{0j}$ and $\sigma_{0j}^{2}$:

$\prod_{c}g_{j}(\boldsymbol{\hat{\theta}}_{cj})=\prod_{c}\left[\pi_{0j}f_{0}(\boldsymbol{\hat{\theta}}_{cj})+(1-\pi_{0j})f_{1}(\boldsymbol{\hat{\theta}}_{cj}|\mu_{0j},\sigma_{0j}^{2},\rho_{0j})\right]$
(8)

Currently, there are not many countries with high-quality datasets at sub-
national level. Fosdick2012 compared approaches of estimating the correlation
in bivariate normal data with known variances and small sample sizes, and
found that the Bayesian approach consistently outperformed several exact and
approximate maximum likelihood estimators for small samples. Therefore, we
assume a prior for $\rho_{0j}$ and $\pi_{0j}$ and set the posterior mode as
the hyperparameter value in Equation (7). Specifically, we assume that
$\frac{\rho_{0j}+1}{2}\sim\textup{Beta}(1.5,1.5)$ which is slightly
concentrated towards $\rho_{0j}=0$ with density 1.273 at
$\frac{\rho_{0j}+1}{2}=0.5$, while the uniform distribution has density 1 over
the domain of $[0,1]$. We also assume that $\pi_{0j}\sim\textup{Beta}(1,1.5)$
which has mean 0.6 and density 1.5 at 1 so that it is slightly in favor of
larger values of $\pi_{0j}$. Finally, we denote $g=\prod_{j}g_{j}$ as the
joint prior distribution of the mixture model and $f_{0}=\prod_{j}f_{0j}$ as
the joint prior distribution of the independent model.

###  2.4 Parameter Estimation via Importance Sampling

Estimating parameters in dynamic models is often time consuming due to the
lack of an analytic solution, the multi-modality and the nonlinearity. Fitting
the datasets from multiple areas simultaneously in the mixture model (7) will
further increase the computing cost. It is desirable to develop a procedure
that produces the mixture model results without additional computational cost.
Since running the dynamic model is the most time consuming part of the
estimation, we propose applying the independent model to fit each individual
dataset as currently being implemented in EPP/Spectrum 2013 Brown2014 and
using importance sampling to approximate the joint posterior distribution of
parameters in the mixture model for multiple datasets.

Applying the independent model to each individual dataset, the posterior
samples are drawn by the incremental mixture importance sampling (IMIS)
algorithm which has been proved to be efficient for estimating parameters in
dynamic systems with a moderate number of parameters Raftery2010,Brown2010. It
works as follows:

  1. 1.

Draw initial samples from a sampling distribution, e.g. the prior
distribution, $f_{0}$;

  2. 2.

Update the importance weight for each sample, which is the ratio between
posterior density, $P(\boldsymbol{\theta_{i}}|\textrm{Data}_{i})$, and density
of the sampling distribution;

  3. 3.

Find the sample with the highest weights, and draw new ones from a
multivariate Gaussian distribution centered around it;

  4. 4.

Combine new samples with all existing samples, update the sampling
distribution by a mixture of initial sampling distribution and multiple
Gaussian components, and recalculate the importance weight;

  5. 5.

Iterate between step 2 and 4 until there is no large importance weight;

  6. 6.

Resample all samples from the multinomial distribution with weights.

The initial sampling distribution is often flat so that it ensures a good
coverage of the entire parameter space. As a new Gaussian sampler is placed in
the region that is under-represented by the sampling distribution at each
iteration, the sampling distribution gets closer and closer to the posterior
distribution.

To avoid a separate run of the proposed model, the step 6 of the IMIS
algorithm can be revised as follows:

  1. 6.a.

Repeat steps $1\sim 5$ for areas $i=1,\ldots,K$. All samples with non-ignoble
importance weight will be stored, e.g. greater than $10^{-6}$,;

  2. 6.b.

Create a joint sample of parameters across all areas by randomly taking one
sample from each area, and repeat until we have a large number of candidate
joint samples, e.g. 1,000,000;

  3. 6.c.

The importance weight of a joint sample
$(\boldsymbol{\theta_{1}},\ldots,\boldsymbol{\theta_{K}})$ is calculated as
the product of the importance weights for $\boldsymbol{\theta_{i}}$’s times
$\frac{g(\boldsymbol{\theta_{1}},\ldots,\boldsymbol{\theta_{K}})}{f_{0}(\boldsymbol{\theta_{1}},\ldots,\boldsymbol{\theta_{K}})}$,
the ratio between the mixture model prior density and the independent model
prior density;

  4. 6.d.

Resample all samples from the multinomial distribution with weights.

The resulting posterior samples will have replicates because they are drawn
from multinomial distribution with replacement, and a large number of
replicates suggests a low sampling efficiency – a large discrepancy between
the sampling distribution and the target distribution Raftery2010. The ratio
between two prior densities is

$\frac{g(\boldsymbol{\theta_{1}},\ldots,\boldsymbol{\theta_{K}})}{f_{0}(\boldsymbol{\theta_{1}},\ldots,\boldsymbol{\theta_{K}})}=\prod_{j}\left[\pi_{0j}+(1-\pi_{0j})\times\frac{f_{1j}(\theta_{1j},\ldots,\theta_{Kj})}{f_{0j}(\theta_{1j},\ldots,\theta_{Kj})}\right],$

which has the lower bound $\prod_{j}\pi_{0j}$, so that all combinations have
non-ignoble reweighing factor. Therefore, limiting the importance weights
helps obtain desired sampling efficiency. In the result section we will show
that the revised IMIS algorithm still provides a large number of unique
samples.

###  2.5 Assessing Model Fit

We compare performance of the original EPP model (independent model) and the
proposed mixture model based on datasets collected from the following 20
countries in Sub-Saharan Africa: Benin, Botswana, Burkina Faso, Burundi,
Cameroun, Chad, Ethiopia, Ghana, Kenya, Lesotho, Malawi, Mali, Nigeria,
Republic of Cote d’Ivoire (RCI), Democratic Republic of the Congo (RDC),
Rwanda, SierraLeone, Tanzania, Uganda, and Zambia. We construct two scenarios
to assess the model fit by splitting the data into training and test in two
different ways. In the first scenario we assess the prediction into the future
by withholding the last 3 years of data as the test set. In the second
scenario we assess both the future prediction and recovery of the past by
using only the mid-period data as the training set and predict both the
earlier and later data.

##  3 Results

To determine the values of $\boldsymbol{\pi_{0}}$ and $\boldsymbol{\rho_{0}}$,
we obtain a set of posterior means by applying the independent model to 14
countries with multiple high-quality datasets, where high-quality is defined
as having prevalence data at multiple clinics for at least 7 years and at
least one national population based survey. Here we focus on high-quality
datasets because their point estimates are mainly driven by the data instead
of the informative prior distribution in Equation (4). Table 1 presents the
estimated $\boldsymbol{\pi_{0}}$ and $\boldsymbol{\rho_{0}}$ following the
procedure in Section 2.3. It suggests that the correlations of $\beta_{2}$’s
between areas are negligible with probability $\pi_{06}=1$ of using the
independent model prior distribution.

Table 1: $\boldsymbol{\pi_{0}}$ and $\boldsymbol{\rho_{0}}$ determined by point estimates of high-quality datasets. | $\theta_{1}$ | $\theta_{2}$ | $\theta_{3}$ | $\theta_{4}$ | $\theta_{5}$ | $\theta_{6}$ | $\theta_{7}$ | $\theta_{8}$
---|---|---|---|---|---|---|---|---
$t_{0}$ | $t_{1}$ | $\log r_{0}$ | $\beta_{0}$ | $\beta_{1}$ | $\beta_{2}$ | $\beta_{3}$ | $\beta_{4}$
$\pi_{0j}$ | 0.278 | 0.249 | 0.315 | 0.154 | 0.490 | 1.000 | 0.196 | 0.125
$\rho_{0j}$ | 0.822 | 0.925 | 0.996 | 0.708 | 0.783 | 0.000 | 0.529 | 0.608

We then apply both the independent model and the mixture model to datasets in
20 countries that have sufficient data to evaluate the prediction performance
by with holding the last 3 years as test datasets. Table 3 summarizes
prediction performance in term of the mean absolute errors (MAE) of antenatal
clinic prevalence, and the sampling efficiency in term of the number of unique
posterior samples.

Despite the success of the independent model with the informative prior
distribution in many high-quality-data countries [Bao (2012)], the mixture
model further improves 3-year prediction MAE by 0.05 on average, with (5th,
95th) percentiles being (-0.03, 0.22). Among 41 datasets, the improvement is
greater than 0.05 for 13 datasets, and less than -0.05 for one dataset. We
also note that the mixture model provides better prediction accuracy
especially for areas that have fewer data. Table 3 highlights eight areas with
less than 5 years of training data – four of them gain substantial
improvements by using the mixture model, and the remaining four areas have
little difference.

The top four panels in Figure 2 present examples that the mixture model
results differ systematically from the independent model results during the
3-year period of test data. In the Sierra Leone example, the mixture model
(blue) improves the prediction accuracy as its posterior mean is closer to the
average of observed HIV prevalence (red) than the posterior mean of
independent model (black). Moreover, Sierra Leone surveillance data starts
from 2003 in urban areas and 2006 in rural areas. Two models provided
significant different estimates for the early period of Sierra Leone rural
epidemic. It was because Sierra Leone urban data suggested the epidemic
started after 1980 and the rural area estimation borrowed that information in
the mixture model. In the Burundi example, the mixture model (blue) fails to
make a better prediction. It was because the prevalence had an unexpected
decline in the test data period (after the red vertical line), and neither
urban training data nor rural training data could predict that decline. It
revealed a limitation of the mixture model: if there is a sudden change of the
epidemic pattern that could not predicted by any individual dataset, borrowing
information from each other could not help in capturing the change.

IMIS method [Raftery and Bao (2010)] is used to draw the posterior samples for
the independent model. Among all datasets, it provides 801 unique samples out
of 1,000 resamples on average, with (5th, 95th) percentiles being (767, 828).
Adjusting the importance weights following procedures 6.a.$\sim$6.c. in
section 2.4., the average number of unique samples for the mixture model is
537, and (5th, 95th) percentiles are (235, 762). It is less efficient than
applying IMIS from the scratch in term of the number of unique samples.
However, we avoid re-running the time-consuming EPP models and get new results
within 10 seconds for each country. The gray curves in Figure 2 show the
posterior samples of mixture model. It seems that simply adjusting the
importance weights provides enough unique samples to cover the high posterior
density region.

Table 2: A summary table for the number of data-years in training dataset, the 3-year prediction mean absolute error of antenatal clinic prevalence in %, the number of unique posterior samples. Bold highlights the areas with less than 5 years of training data. Country | Area | Training Data | Mean Absolute Error (%) | Number of Unique Samples
---|---|---|---|---
$\\#$ of Years | Independent | Mixture | Improvement | Independent | Mixture
Benin | Urban | 18 | 1.56 | 1.57 | -0.01 | 808 | 152
Benin | Rural | 6 | 0.88 | 0.88 | -0.01 | 824 | 186
Botswana | Urban | 15 | 3.07 | 3.07 | 0.01 | 657 | 460
Botswana | Rural | 15 | 4.31 | 4.14 | 0.17 | 793 | 467
BurkinaFaso | Urban | 17 | 0.71 | 0.7 | 0.02 | 797 | 513
BurkinaFaso | Rural | 5 | 0.47 | 0.48 | 0.00 | 821 | 360
Burundi | Urban | 17 | 6.66 | 6.69 | -0.03 | 814 | 730
Burundi | Rural | 17 | 1.52 | 1.74 | -0.22 | 818 | 571
Cameroun | Urban | 13 | 3.88 | 3.88 | 0.00 | 817 | 677
Cameroun | Rural | 2 | 3.3 | 3.03 | 0.26 | 803 | 613
Chad | Urban | 6 | 2.42 | 2.37 | 0.05 | 811 | 283
Chad | Rural | 2 | 1.23 | 1.01 | 0.22 | 809 | 244
Ethiopia | Urban | 11 | 2.5 | 2.43 | 0.08 | 785 | 283
Ethiopia | Rural | 7 | 1.22 | 1.22 | -0.01 | 808 | 374
Ghana | Urban | 14 | 0.74 | 0.72 | 0.02 | 803 | 450
Ghana | Rural | 13 | 0.71 | 0.75 | -0.04 | 822 | 430
Kenya | Urban | 15 | 3.11 | 3.04 | 0.07 | 759 | 624
Kenya | Rural | 12 | 2.72 | 2.5 | 0.22 | 819 | 617
Lesotho | Urban | 8 | 5.93 | 5.9 | 0.03 | 815 | 755
Lesotho | Rural | 8 | 4.17 | 4.01 | 0.16 | 817 | 772
Malawi | Central | 9 | 2.55 | 2.58 | -0.01 | 806 | 719
Malawi | Northern | 9 | 2.04 | 2.05 | -0.02 | 817 | 817
Malawi | Southern | 9 | 5.35 | 5.27 | 0.08 | 797 | 729
Mali | Urban | 3 | 1.03 | 1 | 0.03 | 803 | 665
Mali | Rural | 3 | 0.99 | 0.97 | 0.02 | 828 | 663
Nigeria | Urban | 7 | 2.58 | 2.59 | -0.01 | 782 | 725
Nigeria | Rural | 2 | 2.21 | 2.22 | -0.01 | 821 | 645
RCI | Urban | 14 | 1.97 | 1.92 | 0.05 | 795 | 528
RCI | Rural | 3 | 2.54 | 2.52 | 0.02 | 824 | 544
RDC | Urban | 20 | 1.23 | 1.22 | 0.02 | 770 | 670
RDC | Rural | 11 | 1.33 | 1.34 | -0.01 | 817 | 525
Rwanda | Urban | 6 | 1.88 | 1.8 | 0.09 | 807 | 529
Rwanda | Rural | 6 | 0.87 | 0.87 | 0.01 | 807 | 355
SierraLeone | Urban | 3 | 2.7 | 2.49 | 0.20 | 794 | 591
SierraLeone | Rural | 2 | 1.78 | 1.6 | 0.18 | 834 | 509
Tanzania | Urban | 18 | 1.61 | 1.61 | 0.00 | 796 | 685
Tanzania | Rural | 18 | 1.37 | 1.36 | 0.00 | 796 | 645
Uganda | Urban | 20 | 2.34 | 2.33 | 0.01 | 767 | 763
Uganda | Rural | 17 | 1.59 | 1.59 | 0.00 | 807 | 797
Zambia | Urban | 5 | 2.55 | 2.5 | 0.05 | 797 | 484
Zambia | Rural | 5 | 3.08 | 3.1 | -0.02 | 818 | 541
Mean | 2.23 | 2.18 | 0.05 | 801 | 537
5th quantile | 0.71 | 0.72 | -0.03 | 767 | 235
95th quantile | 4.55 | 4.40 | 0.22 | 828 | 762
|
---|---
|
|
Figure 2: HIV prevalence estimation and prediction for 6 datasets that present
large differences between the independent model and the mixture model. Within
each figure, the black solid line is the posterior mean trajectory of the
original model; the blue solid line is the posterior mean trajectory of the
mixture model; the dashed black/blue lines show the 95% credible intervals;
colored dots are observed prevalence from different ANC sites; the red solid
line is the raw average trajectory of ANC prevalence. The red dashed vertical
lines separate the training data and test data.

In the next few years, many countries are going to produce estimates at finer
sub-national scales, e.g. at province or district levels. The data imbalance
across sub-national areas is a major concern – some areas have historical
surveillance sites with many years of observations, and some other area only
have newly established surveillance sites with observations in recent years.
One motivation of our model is to improve the estimation and prediction for
low-data-quality areas by borrowing information from high-data-quality areas.
Trying to mimic this situation, for each country, we create one “low-data-
quality” area by keeping only the middle 6 years data as the training set and
using both the early years data (however many years available) and last 3
years data as the test set in that area, and the other areas in that country
act as “high-data-quality” areas such that only the last 3 years data are
withheld as the test set. We also rotate the areas of “low” and “high” so each
area gets evaluated as the “low-data-quality” area. We summarize the MAE’s for
both future predictions and past recoveries in Table 4. The “Area” column
indicates which area is the “low-data-quality” area. The results show that the
mixture model improves 3-year prediction MAE by 0.05 on average with
improvement greater than 0.10 in 8 cases and no less than -0.10 in all other
cases. The mixture model also improves the early epidemic estimation MAE by
0.55 on average with improvement greater than 1.00 in 8 cases but less than
-1.00 in one case. The bottom two panels in Figure 2 present two cases with
large difference between two models in the early period of the epidemic, and
the mixture model mean trajectory is a better approximation to the raw data
average than the independent model.

Table 3: A summary table for the early data period estimation mean absolute errors and the 3-year prediction mean absolute errors in %. Country | Area | Early Data Period MAE | Prediction MAE
---|---|---|---
Independent | Mixture | Improvement | Independent | Mixture | Improvement
Botswana | Urban | 9.44 | 3.60 | 5.84 | 3.17 | 2.98 | 0.18
Botswana | Rural | 4.6 | 6.16 | -1.57 | 4.39 | 4.33 | 0.06
Burundi | Urban | 7.79 | 7.84 | -0.05 | 16.57 | 16.65 | -0.08
Burundi | Rural | 3.83 | 3.94 | -0.11 | 2.15 | 2.25 | -0.10
Ethiopia | Urban | 3.40 | 3.20 | 0.20 | 2.29 | 2.16 | 0.14
Ethiopia | Rural | 1.44 | 1.45 | -0.01 | 1.16 | 1.16 | 0.00
Ghana | Urban | 1.89 | 1.24 | 0.65 | 0.84 | 0.81 | 0.03
Ghana | Rural | 1.50 | 0.91 | 0.59 | 0.71 | 0.76 | -0.05
Kenya | Urban | 5.74 | 5.69 | 0.05 | 1.87 | 1.84 | 0.03
Kenya | Rural | 4.41 | 4.31 | 0.10 | 2.52 | 2.54 | -0.02
Lesotho | Urban | 7.74 | 6.57 | 1.17 | 1.18 | 1.18 | 0.01
Lesotho | Rural | 10.03 | 8.23 | 1.80 | 2.97 | 2.77 | 0.20
Malawi | Central | 3.82 | 4.77 | -0.85 | 2.20 | 2.25 | -0.05
Malawi | Northern | 7.63 | 7.18 | 0.45 | 1.72 | 1.71 | 0.01
Malawi | Southern | 5.67 | 3.64 | 2.03 | 4.65 | 4.74 | -0.09
RDC | Urban | 2.18 | 2.09 | 0.09 | 1.20 | 1.20 | 0.00
RDC | Rural | 3.27 | 2.46 | 1.19 | 0.85 | 0.85 | 0.00
Rwanda | Urban | 9.88 | 10.14 | -0.26 | 1.91 | 1.70 | 0.21
Rwanda | Rural | 1.51 | 1.84 | -0.33 | 1.13 | 0.93 | 0.20
Tanzania | Urban | 4.85 | 4.95 | -0.10 | 1.55 | 1.54 | 0.00
Tanzania | Rural | 7.88 | 6.53 | 1.35 | 1.61 | 1.35 | 0.27
Uganda | Urban | 8.47 | 6.04 | 2.42 | 2.60 | 2.45 | 0.15
Uganda | Rural | 4.04 | 2.56 | 1.47 | 2.18 | 2.07 | 0.11
Zambia | Urban | 7.12 | 4.78 | 2.34 | 2.34 | 2.41 | -0.07
Zambia | Rural | 2.99 | 2.74 | 0.25 | 2.75 | 2.85 | -0.10
Mean | 5.01 | 4.46 | 0.55 | 2.71 | 2.66 | 0.05
5th quantile | 1.45 | 1.27 | -1.43 | 0.84 | 0.82 | -0.09
95th quantile | 9.81 | 8.17 | 2.41 | 4.33 | 4.27 | 0.21

In addition to the examination of the marginal distribution of prevalence
within each area, we also examine the joint distributions of the quantity of
interest across areas, e.g. HIV prevalence and HIV incidence. We apply the
mixture model to the full datasets of 20 countries. For every country and
every year, we calculate the prevalence correlation and incidence correlation
among areas. Figure 3 shows those correlations by years and by countries.
Those correlations are mostly positive due to the positive correlation of EPP
input parameters. Since the mixture model involves a hierarchical structure
for the EPP input parameters which summarize the characteristics of the HIV
epidemic, the correlations of the EPP output prevalence and incidence vary
across time.

|
---|---
Figure 3: The prevalence correlations (left) and incidece correlations (right)
between subnaitonal areas produced by the mixture model. Each gray line
corresponds to one country. The black solid line and dashed lines provide the
median and (5th, 95th) quantiles. The red dashed line indicates a zero
correlation which corresponds to the expected correlation in the independent
model.

##  4 Discussion

Planning an effective response to the HIV epidemic and assessing the impact of
the past response requires quantitative analysis. Sub-national estimates can
be used for better program planning and management, such as assessing and
meeting the needs for commodities, human resources and other program elements,
measuring population coverage of treatments, and monitoring and evaluating
interventions. In this article, we describe a hierarchical epidemiological
structure that assumes the patterns of the sub-national epidemic are similar,
and suggest a mixture between the independent model and newly proposed
hierarchical model to account for the uncertainty between two model choices.
For the estimation and projection of HIV epidemics, this will be the first
attempt of developing a joint model for multiple areas within a country. It
will be potentially implemented in the next round of EPP/Spectrum software
(available from http://www.futuresinstitute.org). The proposed model can be
easily generalized to the study of other epidemics.

We find that the predictive ability of EPP model can be improved by using the
mixture model, especially for the areas that are lack of long historical data.
The mixture model also provides more accurate assessment of the early period
of the epidemics in many examples, but there are a couple of exceptions. If
the mixture model and the independent model estimate the early trend of the
epidemic very differently, we suggest choosing the model with the help of
other available information such as the year of the first case report in that
area. The prediction accuracy might be further improved by redefining the
default prior distribution of independent model, such as allowing dependence
among $(t_{0},t_{1},r_{0},\beta_{0},\beta_{1},\beta_{2},\beta_{3},\beta_{4})$.
However, it is beyond the focus of this article.

The computing cost of estimating parameters in a dynamic model is often high
due to the lack of an analytic solution, the multi-modality and nonlinearity.
We propose an importance sampling method that draws posterior samples of
parameters in the mixture model without needing to refit the data or unpack
the existing software for implementing an independent model. We first obtain
posterior samples of parameters for each datasets independently. Since the
mixture model and the independent model only differ at their prior
distributions, we can randomly combine posterior samples of the independent
model from multiple areas, reweight the joint samples by the ratio between the
mixture model prior and the default independent prior, and draw a set of joint
posterior samples from the multinomial distribution with weights. The mixture
between the original model prior and the new model prior provided a lower
bound on the ratio, and thus provided satisfactory sampling efficiency as
measured by the number of unique posterior samples in our examples. If the
number of unique posterior samples is too small, we suggest either increasing
the number of random combinations, or using a less informative prior
distribution in the independent model. A more efficient sampling strategy
should be developed in the future.

Note that, in this specific application, the incremental mixture importance
sampling method is used to draw posterior samples for each individual data,
but our proposed reweighting approach is generic and does not depend on how
the posterior samples are drawn for individual datasets. For instance, if
Markov chain Monte Carlo (MCMC) is used to draw posterior samples for
individual datasets with reasonable burn-in and thinning, we can assume that
those posterior samples have equal weights in the independent model. This
suggests an alternative way of estimating parameters in dependent data, e.g.
data with hierarchical/spatial/temporal structure: fitting each piece of data
independently, and merge the results with adjustments for the difference
between the independent model and the joint model.

When a country has a large geographical territory or diverse regions of public
health conditions, it is worthy to further develop a spatial model or
multilevel hierarchical model based on the knowledge of the national
officials. In those cases, the similarity of epidemic patterns may depend on
the distance or adjacency status between areas, or the regions to which the
areas belong. In countries with low-level and concentrated epidemics, HIV has
spread rapidly in several high risk groups, but is not well established in the
general population. Fewer data are available for those high risk populations
due to the stigmatized nature of these populations in many countries. In such
cases, a hierarchical model can allow sharing information across areas and
high risk groups.

The results presented in this paper are based on illustrative HIV prevalence
data for these countries, which may not be complete. These results should
therefore not be seen as replacing or competing with official estimates
regularly published by countries and UNAIDS.

## References

  * Alkema et al. (2007) Alkema, L., A. E. Raftery, and S. J. Clark (2007).  Probabilistic projections of HIV prevalence using Bayesian melding.  Annals of Applied Statistics 1, 229–248.
  * Bao (2012) Bao, L. (2012).  A new infectious disease model for estimating and projecting HIV/AIDS epidemics.  Sexually Transmitted Infections 88, i58–i64.
  * Brown et al. (2014) Brown, T., L. Bao, J. W. Eaton, D. R. Hogan, M. Mahy, K. Marsh, B. M. Mathers, and R. Puckett (2014).  Improvements in prevalence trend fitting and incidence estimation in epp 2013.  AIDS 28(Suppl 4), S415–S426.
  * Brown et al. (2010) Brown, T., L. Bao, A. Raftery, J. Salomon, R. Baggaley, J. Stover, and P. Gerland (2010).  EPP 2009: bringing the UNAIDS Estimation and Projection Package into the ART era.  Sexually Transmitted Infections 86, ii3–ii10.
  * Brown et al. (2008) Brown, T., N. Grassly, and G. Garnett (2008).  Improving projections at the country level: the UNAIDS Estimation and Projection Package 2005.  Sexually Transmitted Infections 82, iii34–iii40.
  * Calleja et al. (2010) Calleja, J. M. G., J. Jacobson, R. Garg, N. Thuy, A. Stengaard, M. Alonso, H. Ziady, L. Mukenge, S. Ntabangana, D. Chamla, et al. (2010).  Has the quality of serosurveillance in low-and middle-income countries improved since the last hiv estimates round in 2007? status and trends through 2009.  Sexually transmitted infections 86(Suppl 2), ii35–ii42.
  * Case et al. (2014) Case, K. K., T. B. Hallett, S. Gregson, K. Porter, and P. D. Ghys (2014).  Development and future directions for the joint united nations programme on hiv/aids estimates.  AIDS 28(Suppl 4), S411–S414.
  * Centers for Disease Control (1981) Centers for Disease Control (1981).  Pneumocystis pneumonia: Los angeles.  Morbidity and Mortality Weekly Report 30, 250–252.
  * Fosdick and Raftery (2012) Fosdick, B. and A. Raftery (2012).  Estimating the correlation in bivariate normal data with known variances and small sample sizes.  The American Statistician 66, 34–41.
  * Futures Institute (2014) Futures Institute (2014).  Spectrum Manual.  Glastonbury, Connecticut: Futures Institute.
  * Ghys et al. (2004) Ghys, P. D., T. Brown, N. C. Grassly, G. Garnett, K. A. Stanecki, J. Stover, and N. Walker (2004).  The UNAIDS estimation and projection package: A software package to estimate and project national HIV epidemics.  Sexual Transmitted Infections 80, i5–i9.
  * Lyerla et al. (2008) Lyerla, R., E. Gouws, and J. Garcia-Calleja (2008).  The quality of sero-surveillance in low-and middle-income countries: status and trends through 2007.  Sexually Transmitted Infections 84(Suppl 1), i85–i91.
  * Mahy et al. (2014) Mahy, M., M. Nzima, M. K. Ogungbemi, D. A. Ogbang, M. C. Morka, and J. Stover (2014).  Redefining the hiv epidemic in nigeria: from national to state level.  AIDS 28(Suppl 4), S461–S468.
  * Marsh et al. (2014) Marsh, K., M. Mahy, J. A. Salomon, and D. R. Hogan (2014).  Assessing and adjusting for differences between hiv prevalence estimates derived from national population-based surveys and antenatal care surveillance, with applications for spectrum 2013.  AIDS 28(Suppl 4), S497–S506.
  * Raftery and Bao (2010) Raftery, A. and L. Bao (2010).  Estimating and projecting trends in HIV/AIDS generalized epidemics using incremental mixture importance sampling (supported by NICHD grant HD054511).  Journal of the American Statistical Association 66, 1162–1173.
  * Stover et al. (2014) Stover, J., K. Andreev, E. Slaymaker, C. Gopalappa, K. Sabin, C. Velasquez, J. Nakiyingi-Miiro, A. Crampin, T. Lutalo, K. Herbst, S. Gregson, and M. Urassa (2014).  Updates to the spectrum model to estimate key hiv indicators for adults and children.  AIDS 28(Suppl 4), S427–S434.
  * UNAIDS (2013) UNAIDS (2013).  Location, Location: Connecting people faster to HIV services.  Geneva, Switzerland: UNAIDS.
  * UNAIDS (2014) UNAIDS (2014).  The GAP Report.  Geneva, Switzerland: UNAIDS.
  * UNAIDS/WHO Working Group on Global HIV and STI Surveillance (2013) UNAIDS/WHO Working Group on Global HIV and STI Surveillance (2013).  Guidelines for second generation HIV surveillance: an update: Know your epidemic.  Geneva, Switzerland: World Health Organization.


# Generation of complex database queries and API calls from natural language
utterances

Amol Kelkar, Nachiketa Rajpurohit, Utkarsh Mittal, Peter Relan
Got It AI R&D
<EMAIL_ADDRESS>
###### Abstract

Generating queries corresponding to natural language questions is a long
standing problem. Traditional methods lack language flexibility, while newer
sequence-to-sequence models require large amount of data. Schema-agnostic
sequence-to-sequence models can be fine-tuned for a specific schema using a
small dataset but these models have relatively low accuracy. We present a
method that transforms the query generation problem into an intent
classification and slot filling problem. This method can work using small
datasets. For questions similar to the ones in the training dataset, it
produces complex queries with high accuracy. For other questions, it can use a
template-based approach or predict query pieces to construct the queries,
still at a higher accuracy than sequence-to-sequence models. On a real-world
dataset, a schema fine-tuned state-of-the-art generative model had 60% exact
match accuracy for the query generation task, while our method resulted in 92%
exact match accuracy.

##  1 Introduction

Natural language interfaces to databases (NLIDB) Grosz et al. (1987) systems
allow a user to communicate with the database directly by entering the query
in the form of a natural language question. Pattern matching based Weizenbaum
(1966), syntax based Woods (1972), semantic grammar based systems have been
investigated Owda et al. (2007).

In recent years, neural networks based generative text-2-SQL semantic parsers
have gained prominence as a core component in NLIDB systems. They use neural
language models that can handle natural language variations and ambiguities
better than the traditional approaches. Some of these approaches work with a
specific schema, such as Seq2SQL Zhong et al. (2017). They require large
datasets of question-query pairs for the specific schema, which is typically
not available for practical applications. Also, the generated queries are
typically simplistic compared to queries used in real world applications.
Other approaches such as IRNet Guo et al. (2019) and GNN Bogin et al. (2019)
are schema agnostic and accept schema description along with natural language
question at inference time. These are trained on a large corpus of question-
query pairs across many schemas and are typically fine-tuned on a small
dataset for the specific application schema. Unfortunately, their accuracy is
not high enough to use in practical applications without human oversight of
generated queries.

In this paper, we present an approach that produces complex queries from
natural language questions on a specific schema with high accuracy, while
requiring only a small dataset of question-query pairs. This approach can be
used to produce SQL queries, API calls or other commands.

##  2 Our approach

We use intent discovery, intent classification, entity extraction, slot
filling, and template based generation to generate query for a given natural
language question.

###  2.1 Intent discovery

All queries… FROM table1 …… FROM table2 JOIN table3 …… FROM table1 …… FROM
table1 … GROUP BY col1 …… FROM table1 … GROUP BY col2, col1SELECT col1,
SUM(col3)FROM table1 … GROUP BY col1 …SELECT col1, max(col4) FROM table1 …
GROUP BY col1 …SELECT col1, max(col4) FROM table1 WHERE col6 BETWEEN [slot1]
AND [slot2] GROUP BY col1 …SELECT col1, max(col4) FROM table1 WHERE col5 =
[slot3] ANDcol6 = [slot1]GROUP BY col1 …RootLevel 1Level 2Level 3Level 4

Figure 1: A set of question-query examples are mapped to a tree of intents by
analyzing the queries.

We first analyze queries in examples from the question-query dataset and build
a tree of intents. See figure 1. Root of the the tree represents all example
queries. Each level 1 node represents a subset of queries that uses a specific
table and JOIN set. Each level 2 node represents a further subset that share
GROUP BY columns. Each level 3 node represents a specific set of SELECT
clauses. Each level 4 node represents queries that differ only in the values
used.

###  2.2 Intent classification and slot filling

We train a BERT Devlin et al. (2019) fine-tuned joint intent classification
and slot filling (IDSF) model. It predicts the intent corresponding to a user
question. Each node in the intent tree represents an intent. The model is
trained to predict one intent from a specific intent level, or a set of
intents along a path from root to a level 4 intent. Figure 2 shows
configuration where a single intent is predicted. The model is also jointly
trained to predict which tokens from the input question represent slot values
and which slots should be filled with those values.

###  2.3 Query generation

The slot values predicted by the IDSF model may need to be transformed before
use in queries. We build translation dictionaries using annotations from the
question-query dataset to map slot values into query values. We also detect
slot data types using a heuristic algorithm. Then, for slots with known data
types such as date, we detect formatting rules to transform the value into
appropriately formatted query value. For example, a date could be specified as
"next Thursday" in the question that gets extracted as a date object, and
needs to be used in the query as "2020-10-20". In this case, we would detect
formatting rule as "%y-%m-%d". If the lists of allowed values for certain
database columns is available, that information is used to map corresponding
slot values to select one of the allowed values.

Sequence Classifier: Dropout,Intent 1Intent n$H_{[CLS]}$BERT[CLS] how many
redQuestionToken Classifier: Dropout,Slot 1Slot n$H_{token}$for each token
Slot 5 ”color” 1.0 Intent 3 ”product count” 1.0Linear Layer, Cross Entropy
LossLinear Layer, Cross Entropy Loss

Figure 2: Joint intent detection and slot filling

If the IDSF model predicts a level 4 intent, query can be generated by simply
replacing placeholders in the intent’s template. If a level 3 intent is
predicted, WHERE and HAVING conditions in the SQL query are generated based on
which slot values are available and rest of the query is generated by simple
slot value substitution like level 4 intents. Queries for level 2 and level 1
intents are generated using more complex algorithms and models that predict
non-value slots such as aggregation operators and columns to use in SELECT
clause of the query, similar to the approach used in Hwang et al. (2019). If
no intent is predicted with high confidence, a generative text-to-SQL model
such as Kelkar et al. (2020) is used, with a human-in-the-loop to validate
generated query before use.

The approach can be used to generate commands in an arbitrary non-SQL syntax
by pre-processing into an isomorphic SQL command. We use this approach to
predict API calls from natural language questions. Consider a question What’s
the current temperature in Seattle? and corresponding API call such as
temperature(city=’Seattle’). We pre-process the API call as SELECT t FROM
temperature WHERE city=’Seattle’ during training and back into API call after
inference.

##  3 Results and conclusion

We applied this approach to build an NLIDB system for a particular e-commerce
application. We used a dataset of 230 question-query pairs and schema
description as table-column hierarchy with column types and allowed values for
enumerated type columns. 200 examples were used for training and 30 were
reserved for testing. We tested GNN Bogin et al. (2019) trained on the Spider
dataset Yu et al. (2018) and saw 8% accuracy on the test dataset. When we fine
tuned the GNN model on this schema using the training dataset, the accuracy
improved to 60%. In comparison, our system resulted in 92% accuracy on the
test dataset.

## References

  * Bogin et al. (2019) Ben Bogin, Jonathan Berant, and Matt Gardner. 2019.  Representing Schema Structure with Graph Neural Networks for Text-to-SQL Parsing.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4560–4565, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North_ , Mlm, pages 4171–4186, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Grosz et al. (1987) Barbara J Grosz, Douglas E Appelt, Paul A Martin, and Fernando CN Pereira. 1987\.  Team: an experiment in the design of transportable natural-language interfaces.  _Artificial Intelligence_ , 32(2):173–243.
  * Guo et al. (2019) Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. 2019.  Towards Complex Text-to-SQL in Cross-Domain Database with Intermediate Representation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4524–4535, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Hwang et al. (2019) Wonseok Hwang, Jinyeong Yim, Seunghyun Park, and Minjoon Seo. 2019.  A Comprehensive Exploration on WikiSQL with Table-Aware Word Contextualization.  (2017).
  * Kelkar et al. (2020) Amol Kelkar, Rohan Relan, Vaishali Bhardwaj, Saurabh Vaichal, and Peter Relan. 2020\.  Bertrand-dr: Improving text-to-sql using a discriminative re-ranker.
  * Owda et al. (2007) M. Owda, Z. Bandar, and K. Crockett. 2007.  Conversation-based natural language interface to relational databases.  In _2007 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology - Workshops_ , pages 363–367.
  * Weizenbaum (1966) Joseph Weizenbaum. 1966.  Eliza—a computer program for the study of natural language communication between man and machine.  _Commun. ACM_ , 9(1):36–45.
  * Woods (1972) William Woods. 1972.  The lunar sciences natural language information system.  _BBN report_.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018\.  Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3911–3921, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Zhong et al. (2017) Victor Zhong, Caiming Xiong, and Richard Socher. 2017.  Seq2sql: Generating structured queries from natural language using reinforcement learning.