# Radon partitions in convexity spaces222The paper is in public domain, and is
not protected by copyright.

Boris<EMAIL_ADDRESS>Centre for Mathematical Sciences,
Cambridge CB3 0WB, England and Churchill College, Cambridge CB3 0DS, England.

###### Abstract

Tverberg’s theorem asserts that every $(k-1)(d+1)+1$ points in
$\mathbb{R}^{d}$ can be partitioned into $k$ parts, so that the convex hulls
of the parts have a common intersection. Calder and Eckhoff asked whether
there is a purely combinatorial deduction of Tverberg’s theorem from the
special case $k=2$. We dash the hopes of a purely combinatorial deduction, but
show that the case $k=2$ does imply that every set of $O(k^{2}\log^{2}k)$
points admits a Tverberg partition into $k$ parts.

## Introduction

Radon’s lemma [Rad21] states that every set $P$ of $d+2$ points in
$\mathbb{R}^{d}$ can be partitioned into two classes $P=P_{1}\cup P_{2}$ so
that the convex hulls of $P_{1}$ and $P_{2}$ intersect. Birch [Bir59] (for
$d=2$) and Tverberg [Tve66] (for general $d$) extended Radon’s theorem to the
analogous statement for partitions of a set into more than two parts: For a
set $P\subset\mathbb{R}^{d}$ of $\lvert P\rvert\geq(k-1)(d+1)+1$ points there
is a partition $P=P_{1}\cup\dotsb\cup P_{k}$ into $k$ parts, such that the
intersection of the convex hulls
$\operatorname{conv}P_{1}\cap\dotsb\cap\operatorname{conv}P_{k}$ is non-empty.
The bound of $(k-1)(d+1)+1$ is sharp, as witnessed by any set of points in
sufficiently general position.

Calder [Cal71] conjectured and Eckhoff [Eck79] speculated that Tverberg’s
theorem is a consequence of Radon’s theorem in the context of abstract
convexity spaces. The conjecture, which we now present, is commonly referred
as “Eckhoff’s conjecture”, and we will maintain this tradition to avoid
additional confusion. If true, the conjecture would have provided a purely
combinatorial proof of Tverberg’s theorem. However, we will show that the
conjecture is false.

A _convexity space_ on the ground set $X$ is a family $\mathcal{F}\subset
2^{X}$ of subsets of $X$, called _convex sets_ , such as both $\emptyset$ and
$X$ are convex, and intersection of any collection of convex sets is convex.
For example, the familiar convex sets in $\mathbb{R}^{d}$ form a convexity
space on $\mathbb{R}^{d}$. Among the other examples are axis-parallel boxes in
$\mathbb{R}^{d}$, finite subsets on any ground set, closed sets in any
topological space (see the book [vdV93] for a through overview of convexity
spaces). If the ground set $X$ in the convexity space $(X,\mathcal{F})$ is
clear from the context, we will speak simply of a convexity space
$\mathcal{F}$. The _convex hull_ of a set $P\subset X$, denoted
$\operatorname{conv}P$, is the intersection of all the convex sets containing
$P$. We write $\operatorname{conv}_{\mathcal{F}}P$ if the convexity space is
not clear from the context. The $k$-th _Radon number_ of $(X,\mathcal{F})$ is
the minimum natural number $r_{k}$, if it exists, so that every set $P\subset
X$ of at least $r_{k}$ points admits a partition $P=P_{1}\cup\dotsb\cup P_{k}$
into $k$ parts whose convex hulls have an element in common. It is not hard to
show333According to [Eck00] it was first shown by R.E.Jamison (1976). The
first published proofs appear to be in [DRS81] and [JW81]. that if $r_{2}$ is
finite, then so is $r_{k}$. Eckhoff’s conjecture states that
$r_{k}\leq(k-1)(r_{2}-1)+1$ in every convexity space. The conjecture has been
proved for $r_{2}=3$ by Jamison [JW81], and for convexity space with at most
$2r_{2}$ points by Sierksma and Boland [SB83]. In section 4 we reproduce a
version of Jamison’s proof.

The best bounds on $r_{k}$ are

$\displaystyle r_{k_{1}k_{2}}$ $\displaystyle\leq r_{k_{1}}r_{k_{2}}\qquad$
$\displaystyle\text{(due to Jamison
\cite[cite]{[\@@bibref{}{jamison_r3}{}{}]})},$ $\displaystyle r_{2k+1}$
$\displaystyle\leq(r_{2}-1)(r_{k+1}-1)+r_{k}+1\qquad$ $\displaystyle\text{(due
to Eckhoff \cite[cite]{[\@@bibref{}{eckhoff_survey}{}{}]})}.$

In particular,

$r_{k}\leq k^{\lceil\log_{2}r_{2}\rceil}.$ (1)

The following result improves on (1).

######  Theorem 1.

Let $(X,\mathcal{F})$ be a convexity space, and assume that $r_{2}$ is finite.
Then

$r_{k}\leq c(r_{2})k^{2}\log^{2}k,$

where $c(r_{2})$ is a constant that depends only on $r_{2}$.

Though this bound is not far from Eckhoff’s conjecture, the conjecture itself
is false.

######  Theorem 2.

For each $k\geq 3$ there is a convexity space $(X,\mathcal{F})$ such that
$r_{2}=4$, but $r_{k}\geq 3(k-1)+2$.

Despite the failure of Eckhoff’s conjecture, we have been unable to rule out
that the convexity spaces with finite $r_{2}$ might behave similarly to
Euclidean spaces. It is conceivable that $r_{k}$ is bounded by a linear
function of $k$ for each $r_{2}$. Moreover, it is possible that other results
from combinatorial convexity extend to such spaces. For instance, Radon proved
the lemma now bearing his name to give an alternative proof of Helly’s theorem
that if in some family of convex sets in $\mathbb{R}^{d}$ every $d+1$ sets
intersect, then all of them do. One of the easy but startling consequences of
Helly’s theorem is the centrepoint theorem. The centrepoint theorem asserts
that for every finite set $P\subset\mathbb{R}^{d}$ there is a point
$p\in\mathbb{R}^{d}$ (the “centrepoint”) such that every convex set containing
more than $\frac{d}{d+1}\lvert P\rvert$ points of $P$ also contains $p$. Both
the deduction of Helly’s theorem from Radon’s theorem, and the deduction of
centrepoint theorem from Helly’s theorem remain valid in the context of the
convexity spaces with finite $r_{2}$. This prompts the following question:

######  Question 3 (Weak epsilon-nets).

Suppose $(X,\mathcal{F})$ is a convexity space with finite $r_{2}$. Let
$\varepsilon>0$ be given. Let $P\subset X$ be a set of points in the space. Is
there a set $N$ of $\lvert N\rvert\leq f(\epsilon,r_{2})$ points such that
every convex set $S$ containing more than $\varepsilon\lvert P\rvert$ points
of $P$ also contains at least one point of $N$?

The set $N$ as in the question above is called a _weak $\varepsilon$-net_
(with respect to convex sets) for $P$. In $\mathbb{R}^{d}$ it is known that
there are weak $\varepsilon$-nets of size only
$(1/\varepsilon)^{d}\log^{c_{d}}(1/\varepsilon)$. The discussion above shows
that the answer to the question is positive if $\epsilon>1-1/(r_{2}-1)$. It is
unclear whether the weak $\varepsilon$-nets of size $f(\varepsilon,r_{2})$
exist for any $\epsilon<1-1/(r_{2}-1)$.

Bárány [Bár82] showed that if $P$ is an $n$-point set in $\mathbb{R}^{d}$,
then there is a point $p$ in $c_{d}\binom{n}{d+1}$ of all the $\binom{n}{d+1}$
simplices spanned by $P$, where $c_{d}$ is a positive constant that depends
only on $d$. In $\mathbb{R}^{1}$, it is immediate that $c_{1}=1/2$ is
admissible, and is best possible. The situation for convexity spaces with
bounded $r_{2}$ is again unclear, except if $r_{2}=3$:

######  Proposition 4 (Selection theorem).

Let $(X,\mathcal{F})$ be a space with $r_{2}=3$. Let $P\subset X$ be point
set. Then there is a point $p\in X$ that is contained in at least
$\frac{1}{3}\binom{n}{2}+O(n)$ of all the sets $\operatorname{conv}\\{x,y\\}$.

######  Question 5.

Does the preceding proposition hold with $1/2$ in place of $1/3$?

The standard greedy argument of Alon, Bárány, Füredi, Kleitman [ABFK92,
Section 8] shows that the selection theorem implies an affirmative answer to
Question 3. In particular, it gives $f(\epsilon,3)\leq
O\bigl{(}(1/\epsilon)^{2}\bigr{)}$, which is probably not sharp.

The rest of the paper is organized as follows. In section 1 we introduce our
only technical tool, the nerves of convex sets. In lemma 7 we will show that
the nerves encode all the information about the convexity space that we need.
In section 2 we present a counterexample to Eckhoff’s conjecture. It is then
followed in section 3 by the proof of Theorem 1. We conclude the paper with a
short discussion of convexity spaces with $r_{2}=3$.

##  1 Nerves

Let $P$ be a set of points in a some convexity space. We associate to $P$ a
collection $\boldsymbol{\mathcal{N}}(P)$ of subsets of $2^{P}$. A family
$\mathcal{F}\subset 2^{P}$ belongs to $\boldsymbol{\mathcal{N}}(P)$ if and
only if the intersection $\bigcap_{S\in\mathcal{F}}\operatorname{conv}S$ is
non-empty. In the conventional terminology one would say that the collection
$\boldsymbol{\mathcal{N}}(P)$ is the nerve of the family of convex sets
$\\{\operatorname{conv}S:S\subset P\\}$. Since we will not use the nerves of
any other families of sets, in this paper we abuse the language and say that
$\boldsymbol{\mathcal{N}}(P)$ is the nerve of $P$.

######  Proposition 6.

If $\boldsymbol{\mathcal{N}}=\boldsymbol{\mathcal{N}}(P)$, then
$\boldsymbol{\mathcal{N}}$ satisfies the following properties:

  1. (N1)

$\boldsymbol{\mathcal{N}}$ is a downset: if
$\mathcal{F}\in\boldsymbol{\mathcal{N}}$ and
$\mathcal{F}^{\prime}\subset\mathcal{F}$, then
$\mathcal{F}^{\prime}\in\boldsymbol{\mathcal{N}}$.

  2. (N2)

If $\mathcal{F}$ is in $\boldsymbol{\mathcal{N}}$, then so is
$\hat{\mathcal{F}}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\\{S^{\prime}:S^{\prime}\supset S\in\mathcal{F}\\}$.

  3. (N3)

For every $p\in P$ the family
$\mathcal{F}(p)\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\\{S:p\in S\\}$
is in $\boldsymbol{\mathcal{N}}$.

  4. (N4)

The set $P$ can be partitioned into $k$ parts $P=P_{1}\cup\dotsb\cup P_{k}$ so
that
$(\operatorname{conv}P_{1})\cap\dotsb\cap(\operatorname{conv}P_{k})\neq\emptyset$
if and only if there is a family
$\\{P_{1},\dotsc,P_{k}\\}\in\boldsymbol{\mathcal{N}}$ consisting of $k$
disjoint sets.

  5. (N5)

If $r_{t}$ exists, then for every set of $r_{t}$ families
$\boldsymbol{\mathcal{F}}=\\{\mathcal{F}_{1},\dotsc,\mathcal{F}_{r_{t}}\\}\subset\boldsymbol{\mathcal{N}}$
there is a partition
$\boldsymbol{\mathcal{F}}=\boldsymbol{\mathcal{F}}_{1}\cup\dotsb\cup\boldsymbol{\mathcal{F}}_{t}$
of $\boldsymbol{\mathcal{F}}$ into $t$ parts so that
$(\bigcap\boldsymbol{\mathcal{F}}_{1})\cup\dotsb\cup(\bigcap\boldsymbol{\mathcal{F}}_{t})\in\boldsymbol{\mathcal{N}}$.

###### Proof.

The first properties four properties are immediate from the definition of
$\boldsymbol{\mathcal{N}}(P)$.

The final property is easy too: Suppose
$\boldsymbol{\mathcal{F}}=\\{\mathcal{F}_{1},\dotsc,\mathcal{F}_{r_{t}}\\}$ is
given. Let $q_{i}$ be any point in
$\bigcap_{S\in\mathcal{F}_{i}}\operatorname{conv}S$. The set
$Q=\\{q_{1},\dotsc,q_{r_{t}}\\}$ of $r_{t}$ points can be partition into $t$
parts $Q=Q_{1}\cup\dotsb\cup Q_{t}$ so that
$(\operatorname{conv}Q_{1})\cap\dotsb\cap(\operatorname{conv}Q_{t})$ is non-
empty, thus containing some point $p$. The partition $Q=Q_{1}\cup\dotsb\cup
Q_{t}$ naturally induces the partition
$\boldsymbol{\mathcal{F}}=\boldsymbol{\mathcal{F}}_{1}\cup\dotsb\cup\boldsymbol{\mathcal{F}}_{t}$.
It is easy to see that the point $q$ belongs to
$\bigcap_{S\in\cap\boldsymbol{\mathcal{F}}_{i}}\operatorname{conv}S$ for each
$i=1,\dotsc,t$. ∎

Thanks to the following lemma we can avoid the convexity spaces in the rest of
the paper, and work exclusively with nerves.

######  Lemma 7.

Let $P$ be a set, and let $\boldsymbol{\mathcal{N}}$ be a collection of
subsets of $2^{P}$ that satisfies the first three properties in the
Proposition 6. Then there are a ground set $X\supset P$ and a convexity space
on $X$ so that $\boldsymbol{\mathcal{N}}(P)=\boldsymbol{\mathcal{N}}$.

###### Proof.

For an arbitrary family $\mathcal{F}$ let
$C(\mathcal{F})=\\{\mathcal{F}^{\prime}\in\boldsymbol{\mathcal{N}}:\mathcal{F}\subset\mathcal{F}^{\prime}\\}$,
and denote by $\mathcal{C}$ the family of all the sets of the form
$C(\mathcal{F})$. Put $X=\boldsymbol{\mathcal{N}}$. We claim that
$\mathcal{C}$ forms a desired convexity space on $X$. It is clear that
$\emptyset,X\in\mathcal{C}$. Since $C(\mathcal{F}_{1})\cap
C(\mathcal{F}_{2})=C(\mathcal{F}_{1}\cup\mathcal{F}_{2})$, and similarly for
intersections of more than two sets, the collection $\mathcal{C}$ indeed forms
a convexity space on $X$. Define $\phi\colon P\to X$ by
$\phi(p)=\mathcal{F}(p)$. The map $\phi$ is well-defined by property (N3), and
provides the embedding of $P$ into $X$. We need to check that
$\boldsymbol{\mathcal{N}}(\phi(P))=\phi(\boldsymbol{\mathcal{N}})$

Since $\mathcal{F}(p)\in C(\mathcal{F})$ if and only if
$\mathcal{F}\subset\mathcal{F}(p)$, it follows that
$\\{\mathcal{F}(p_{1}),\dots,\mathcal{F}(p_{t})\\}\subset C(\mathcal{F})$
precisely when $\mathcal{F}\subset\bigcap\mathcal{F}(p_{i})$. Hence, if
$P^{\prime}\subset P$, then

$\displaystyle\operatorname{conv}_{\mathcal{C}}(\phi(P^{\prime}))=\bigcap_{\phi(P^{\prime})\subset
C(\mathcal{F})}C(\mathcal{F})=\bigcap_{\mathcal{F}\subset\bigcap_{p\in
P^{\prime}}\mathcal{F}(p)}C(\mathcal{F})=C\left(\bigcap_{p\in
P^{\prime}}\mathcal{F}(p)\right).$

Hence, $\mathcal{F}\in\operatorname{conv}_{\mathcal{C}}(\phi(P^{\prime}))$ if
and only if $\\{P:P^{\prime}\subset P\\}\subset\mathcal{F}$. The intersection
$\bigcap_{P\in\mathcal{F}^{\prime}}\operatorname{conv}_{\mathcal{C}}(\phi(P))$
is non-empty if and only if there is an
$\mathcal{F}\in\boldsymbol{\mathcal{N}}$ so that
$\hat{\mathcal{F}}^{\prime}\subset\mathcal{F}$. Thus by the properties (N1)
and (N2)

$\bigcap_{P\in\mathcal{F}^{\prime}}\operatorname{conv}_{\mathcal{C}}(\phi(P))\neq\emptyset\iff
F^{\prime}\in\boldsymbol{\mathcal{N}}.$

Therefore
$\boldsymbol{\mathcal{N}}_{\mathcal{C}}(\phi(P))=\phi(\boldsymbol{\mathcal{N}})$
as claimed. ∎

##  2 Counterexample to Eckhoff’s conjecture

###### Proof of Theorem 2.

We shall use the Lemma 7 to construct the requisite convexity space. Let
$P=[3(k-1)+1]$. Consider the three kinds of families:

$\displaystyle A[x]$
$\displaystyle=\bigl{\\{}\\{x\\}\bigr{\\}}\cup\binom{P}{4},$ $\displaystyle
B[xy:zw]$
$\displaystyle=\bigl{\\{}\\{x,y\\},\\{z,w\\}\bigr{\\}}\cup\bigl{\\{}S\\!\in\\!\binom{P}{3}:\\{x,y,z,w\\}\cap
S\neq\emptyset\bigr{\\}}\cup\binom{P}{4},\text{ distinct }x,y,z,w$
$\displaystyle C[xy]$
$\displaystyle=\bigl{\\{}\\{x,y\\}\bigr{\\}}\cup\binom{P}{3},\qquad x,y\text{
are distinct}.$

Here $x,y,z,w$ are elements of $P=[3(k-1)+1]$. Let $\hat{A[x]},\hat{B}[xy:zw]$
and $\hat{C}[xy]$ be as in Proposition 6 property (N2). Let
$\boldsymbol{\mathcal{N}}$ consist of all the families,
$\hat{A[x]},\hat{B}[xy:zw]$ and $\hat{C}[xy]$ and all their subfamilies. Let
$\boldsymbol{\mathcal{N}}_{0}$ consist only of families $\hat{A}[x]$,
$\hat{B}[xy:zw]$ and $\hat{C}[xy]$. As $\boldsymbol{\mathcal{N}}$
automatically satisfies properties (N1) and (N2) in Proposition 6 and
$\mathcal{F}(p)\subset\hat{A}[p]$, by Lemma 7 it is a nerve of some convexity
space. As $k\geq 3$, no family of the form $A[x],B[xy:zw]$ or $C[xy]$ contains
$t$ disjoint sets. From that it follows that none of
$\hat{A}[x],\hat{B}[xy:zw]$ or $\hat{C}[xy]$ contain $k$ disjoint sets either,
and same holds for every family in $\boldsymbol{\mathcal{N}}$. Therefore, to
establish the theorem it remains to verify the property (N5) with $r_{2}=4$.

As $\hat{A}$-, $\hat{B}$\- and $\hat{C}$-families are the maximal families in
$\boldsymbol{\mathcal{N}}$, it suffices to show that whenever
$\boldsymbol{\mathcal{F}}=\\{\mathcal{F}_{1},\dotsc,\mathcal{F}_{4}\\}$ is a
collections of four families in $\boldsymbol{\mathcal{N}}_{0}$, then there is
a partition
$\boldsymbol{\mathcal{F}}=\boldsymbol{\mathcal{F}}_{1}\cup\boldsymbol{\mathcal{F}}_{2}$
so that
$(\bigcap\boldsymbol{\mathcal{F}}_{1})\cup(\bigcap\boldsymbol{\mathcal{F}}_{2})$
is contained in some $\mathcal{F}\in\boldsymbol{\mathcal{N}}_{0}$.

To every family $\mathcal{F}$ we associate a subset

$e(\mathcal{F})=\mathcal{F}\cap\binom{P}{2}.$

That is

$\displaystyle e(\hat{A}[x])$ $\displaystyle=\bigl{\\{}\\{x,y\\}:y\in
P\setminus\\{x\\}\bigr{\\}}$ $\displaystyle e(\hat{B}[xy:zw])$
$\displaystyle=\bigl{\\{}\\{x,y\\},\\{z,w\\}\bigr{\\}},$ $\displaystyle
e(\hat{C}[xy])$ $\displaystyle=\bigl{\\{}\\{x,y\\}\bigr{\\}}.$

Note that $e(\mathcal{F}_{1}\cap\mathcal{F}_{2})=e(\mathcal{F}_{1})\cap
e(\mathcal{F}_{2})$. It is convenient think of $e(\mathcal{F})$ as an edge of
a hypergraph on the ground set $\binom{P}{2}$.

Note that if $\mathcal{F}_{1},\mathcal{F}_{2}\in\boldsymbol{\mathcal{N}}_{0}$
are two distinct families, then $\mathcal{F}_{1}\cap\mathcal{F}_{2}$ is
contained in a $\hat{C}$-set. Moreover, if $e(\mathcal{F}_{1})\cap
e(\mathcal{F}_{2})=\emptyset$, then $\mathcal{F}_{1}\cap\mathcal{F}_{2}$ in
contained in $\binom{P}{3}$.

Suppose $\mathcal{F}_{1},\dotsc,\mathcal{F}_{4}$ are four families in
$\boldsymbol{\mathcal{N}}_{0}$. If $e(\mathcal{F}_{1})\cap
e(\mathcal{F}_{2})=\emptyset$, then
$\mathcal{F}_{1}\cap\mathcal{F}_{2}\subset\binom{P}{3}$ and
$\mathcal{F}_{3}\cap\mathcal{F}_{4}\subset\hat{C}[xy]$ for some $x,y$. Hence
$(\mathcal{F}_{1}\cap\mathcal{F}_{2})\cup(\mathcal{F}_{3}\cap\mathcal{F}_{4})\subset\binom{P}{3}\cup\hat{C}[xy]=\hat{C}[xy]$.
We may thus assume that $e(F_{1})\cap e(F_{2})$ is non-empty, and similarly
for other pairs of sets $\mathcal{F}_{1},\dotsc,\mathcal{F}_{4}$.

There are five cases according to the number of $\hat{A}$-families among the
four families $\mathcal{F}_{1},\dotsc\mathcal{F}_{4}$.

There no $\hat{A}$-families: Since every two families meet, and
$e(\mathcal{F}_{1}),\dotsc,e(\mathcal{F}_{4})$ contain $1$ or $2$ vertices
each, it follows that $e(\mathcal{F}_{1}),\dotsc,e(\mathcal{F}_{4})$ must have
a common vertex, say $\\{1,2\\}\in\binom{P}{2}$. Then
$(\mathcal{F}_{1}\cap\mathcal{F}_{2})\cup(\mathcal{F}_{3}\cap\mathcal{F}_{4})\subset\hat{C}[12]$.

There is a single $\hat{A}$-family $\mathcal{F}_{1}$: As $e(\mathcal{F}_{2})$,
$e(\mathcal{F}_{3})$ and $e(\mathcal{F}_{4})$ pairwise meet, they either have
a vertex in common, or $\mathcal{F}_{2},\mathcal{F}_{3},\mathcal{F}_{4}$ are
$\hat{B}$-families, and
$e(\mathcal{F}_{2}),e(\mathcal{F}_{3}),e(\mathcal{F}_{4})$ form a triangle.
However, they cannot form the triangle because $e(\mathcal{F}_{1})$ would not
meet each of $e(\mathcal{F}_{2})$, $e(\mathcal{F}_{3})$ and
$e(\mathcal{F}_{4})$. Thus, $e(\mathcal{F}_{1})\cap\dotsb\cap
e(\mathcal{F}_{4})$ is non-empty, and equals to say
$\\{1,2\\}\in\binom{P}{2}$. Then
$(\mathcal{F}_{1}\cap\mathcal{F}_{2})\cup(\mathcal{F}_{3}\cap\mathcal{F}_{4})\subset\hat{C}[12]$.

There are two $\hat{A}$-families $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$: The
intersection $e(\mathcal{F}_{3})\cap e(\mathcal{F}_{4})$ contains just one
element, say $\\{x,y\\}$. If $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ are just
$\hat{A}[x]$ and $\hat{A}[y]$, then
$(\mathcal{F}_{1}\cap\mathcal{F}_{2})\cup(\mathcal{F}_{3}\cap\mathcal{F}_{4})\subset\hat{C}[xy]$.
If $\mathcal{F}_{1}=\hat{A}[z]$ and $z\not\in\\{x,y\\}$, then it necessarily
follows that $e(\mathcal{F}_{3})=\bigl{\\{}\\{x,y\\},\\{z,w_{3}\\}\bigr{\\}}$
and $e(\mathcal{F}_{4})=\bigl{\\{}\\{x,y\\},\\{z,w_{4}\\}\bigr{\\}}$ for some
$w_{3}$ and $w_{4}$. Thus $\mathcal{F}_{2}$ is either $\hat{A}[x]$ or
$\hat{A}[y]$. In either case $(\mathcal{F}_{1}\cap
F_{3})\cup(\mathcal{F}_{2}\cap\mathcal{F}_{4})\subset\hat{B}[xy:zw_{3}]$.

There are three $\hat{A}$-families $\mathcal{F}_{1}$, $\mathcal{F}_{2}$ and
$\mathcal{F}_{3}$: As $e(\mathcal{F}_{4})$ has to meet all of
$e(\mathcal{F}_{1})$, $e(F_{2})$, $e(F_{3})$, it must be that
$\mathcal{F}_{4}$ is a $\hat{B}$-family, implying that
$(\mathcal{F}_{1}\cap\mathcal{F}_{2}\cap\mathcal{F}_{3})\cup\mathcal{F}_{4}=\mathcal{F}_{4}$.

All four families are $\hat{A}$-families: Say, $\mathcal{F}_{1}=\hat{A}[x]$,
$\mathcal{F}_{2}=\hat{A}[y]$, $\mathcal{F}_{3}=\hat{A}[z]$ and
$\mathcal{F}_{4}=\hat{A}[w]$. In that case
$(\mathcal{F}_{1}\cap\mathcal{F}_{2})\cup(F_{3}\cap\mathcal{F}_{4})\subset\hat{B}[xy:zw]$.
∎

##  3 Upper bound on Radon numbers

The main ingredient in the proof of theorem 1 is a version of Kruskal–Katona
theorem from [Buk10]. A _$d$ -dimensional $r$-uniform family_ is a $d$-tuple
of $r$-element sets. In other words, if we denote by $\binom{X}{r}$ the family
of all $r$-element subsets of $X$, then $d$-dimensional $r$-uniform family is
a subset of $\binom{X}{r}^{d}$. A _shadow_ of such a family
$\mathcal{F}\subset\binom{X}{r}^{d}$ is defined to be

$\partial\mathcal{F}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\bigl{\\{}(S_{1}\setminus\\{x_{i}\\},\dotsc,S_{d}\setminus\\{x_{d}\\}):(S_{1},\dotsc,S_{d})\in\mathcal{F},\text{and
}x_{i}\in S_{i}\text{ for }i=1,\dotsc,d\bigr{\\}}.$

######  Lemma 8 (Theorem 1 of [Buk10]).

Suppose $\mathcal{F}\subset\binom{X}{r}^{d}$ is a $d$-dimensional $r$-uniform
family of size

$\lvert\mathcal{F}\rvert=\binom{x}{r}^{d},$

where $x\geq r$ is a real number. Then

$\lvert\partial\mathcal{F}\rvert\geq\binom{x}{r-1}^{d}.$

In addition to multidimensional Kruskal–Katona theorem, we shall need four
lemmas. The first two lemmas are a bound on Turán numbers of hypergraphs and a
bound on the independence numbers of graphs in which every subgraph have a
large independence number.

######  Lemma 9 ([dC83]).

If $H$ is an $s$-uniform hypergraph on $n$ vertices with fewer than
$\binom{l-1}{s-1}^{-1}\frac{n-l+1}{n-s+1}\binom{\lvert H\rvert}{s}$ edges,
then $H$ contains an independent set on $l$ vertices.

######  Lemma 10 (Special case of Theorem 2.1 from [AS07]).

Let $t<s\leq 2s-3$, and let $G$ be a graph on $n$ vertices. Suppose that every
set of size $s$ contains an independent set of size $t$. Then $G$ contains an
independent set of size $n-s+1$.

Our third lemma is purely computational. We say that a tuple
$(S_{1},\dotsc,S_{d})\in\binom{P}{a}^{d}$ is _$r$ -good_ if there are $r$
pairwise disjoint sets $S_{i_{1}},\dotsc,S_{i_{r}}$ among $S$’s.

######  Lemma 11.

Let $P$ be a finite set. There are at most

$C(d)(a^{2}/\lvert P\rvert)^{d-r+1}\binom{\lvert P\rvert}{a}^{d}$

$r$-bad tuples in $\binom{P}{a}^{d}$, where $C(d)$ is a constant that depends
only on $d$.

###### Proof.

For $S=(S_{1},\dots,S_{d})\in\binom{P}{a}^{d}$ let $G[S]$ be a graph on
$\\{1,\dotsc,d\\}$ with $ij$ forming an edge if $S_{i}\cap
S_{j}\neq\emptyset$. A tuple $S$ is $r$-bad if and only if the independence
number of $G[S]$ is less than $r$. Suppose that the largest forest in $G[S]$
has $m$ edges, then by contracting these edges we obtain an independent set of
size $d-m$. Thus if a tuple $S$ is $r$-bad, then $G[S]$ contains a forest $F$
with $d-r+1$ edges. We say that the forest $F$ _witnesses_ that $S$ is
$r$-bad.

Fix a forest $F$. We shall bound the number of $r$-bad tuples $S$ for which
$F$ is a witness that $S$ is $r$-bad. Let $v_{1},\dotsc,v_{d}$ be a
relabelling of $\\{1,\dotsc,d\\}$ so that in $F$ the vertex $v_{i}$ is
adjacent to at most one vertex $v_{j}$ with $j<i$. Pick $S_{1},\dotsc,S_{d}$
uniformly at random from $\binom{P}{a}$. If $v_{i}$ is adjacent to some
$v_{j}$ with $j<i$ let $E_{i}$ be the event that $S_{i}\cap
S_{j}\neq\emptyset$. If $v_{j}$ is adjacent to none $v_{j}$ with $j<i$ let
$E_{i}$ be the event that holds with probability $1$. Then

$\displaystyle\Pr[F\text{ is a witness that }S\text{ is
$r$-bad}]=\prod_{i=1}^{d}\Pr[E_{i}|E_{1},\dotsc,E_{i-1}]=\prod_{i=1}^{d}\Pr[E_{i}]\leq(a^{2}/\lvert
P\rvert)^{d-r+1}.$

As the number of forests on $d$ vertices depends only on $d$, the lemma
follows by the union bound. ∎

Finally, the third lemma that we need is a restatement of Jamison’s upper
bound $r_{2^{t}}\leq r_{2}^{t}$ in terms of nerves. We include the proof for
completeness.

######  Lemma 12.

Suppose $P$ a set in a convexity space, and
$\boldsymbol{\mathcal{N}}=\boldsymbol{\mathcal{N}}(P)$ is its nerve. Then for
every set $P^{\prime}\subset P$ of size $\lvert P^{\prime}\rvert=r_{2}^{t}$
there is a family $\mathcal{F}\in\boldsymbol{\mathcal{N}}$ containing $2^{t}$
disjoint subsets of $P^{\prime}$.

###### Proof.

The proof is by induction on $t$. The base case $t=0$ is trivial. Suppose
$t\geq 1$. Let $P^{\prime}=P_{1}^{\prime}\cup\dotsb\cup P_{r_{2}}^{\prime}$ be
a partition of $P^{\prime}$ into sets of size $r_{2}^{t-1}$. By the induction
hypothesis, there are families $\mathcal{F}_{1},\dotsc,\mathcal{F}_{r_{2}}$
such that each $\mathcal{F}_{i}$ contains $2^{t-1}$ disjoint subsets of
$P_{i}^{\prime}$. Let these subsets be $R_{i,1},\dotsc,R_{i,2^{t-1}}$. By
property (N5) of the proposition 6, there is a a set $I\subset[r_{k}]$ so that

$\bigcap_{i\in I}\mathcal{F}_{i}\cup\bigcap_{i\not\in
I}\mathcal{F}_{i}\in\boldsymbol{\mathcal{N}}.$

By property (N2) the intersection $R_{j}=\bigcap_{i\in I}R_{i,j}$ is in
$\bigcap_{i\in I}\hat{\mathcal{F}}_{i}$ for each $j=1,\dotsc,2^{t-1}$. The
sets $R_{j}$ are $2^{t-1}$ disjoint subsets of $\bigcup_{i\in
I}P^{\prime}_{i}$. Similarly one obtains $2^{t-1}$ disjoint subsets of
$\bigcup_{i\not\in I}P^{\prime}_{i}$, for the total of $2^{t}$ disjoint
subsets of $P^{\prime}$. ∎

###### Proof of theorem 1.

It suffices to show that for every nerve $\boldsymbol{\mathcal{N}}$ on $\lvert
P\rvert=k^{2}\log^{2}k$ points there are $k$ disjoint sets
$S_{1},\dotsc,S_{k}\subset P$ and a family $\mathcal{F}$ that contains all of
these sets.

For brevity we shall write $r=r_{2}$ and $t=1+\lceil\log_{2}r\rceil$. Define a
$(2r-3)$-dimensional family $\mathcal{T}\subset\binom{P}{r^{t}}^{2r-3}$ as
follows: A tuple $(S_{1},\dotsc,S_{2r-3})\in\binom{P}{r^{t}}^{2r-3}$ is in
$\mathcal{T}$ if there is a family $\mathcal{F}\in\boldsymbol{\mathcal{N}}$
such that $\\{S_{1},\dotsc,S_{2r-3}\\}\subset\mathcal{F}$. Let $P_{0}\subset
P$ be any $(2r-3)r^{t}$-element subset of $P$. Let $P^{\prime}\subset P_{0}$
be an arbitrary $r^{t}$-element subset of $P_{0}$. By the preceding lemma
there is a family $\mathcal{F}$ that contains $2^{t}$ disjoint subsets of
$P^{\prime}$. Since $2r-3\leq 2^{t}$, by property (N2) it follows that
$\mathcal{F}$ contains $2r-3$ disjoint subsets of size $r^{t}$ each that
partition $P_{0}$. In other words, $P_{0}$ gives rise to at least one tuple in
$\mathcal{T}$. Since $P_{0}$ is an arbitrary $(2r-3)r^{t}$-element subset of
$P$, we conclude that

$\lvert\mathcal{T}\rvert\geq\binom{\lvert P\rvert}{(2r-3)r^{t}}\geq
c_{1}(r)\lvert P\rvert^{(2r-3)r^{t}}\geq\binom{\lvert
P\rvert}{r^{t}}^{2r-3}-\binom{(1-c_{2}(r))\lvert P\rvert}{r^{t}}^{2r-3}$

for some positive constants $c_{1}(r),c_{2}(r)$ that depend only on $r$.

Let $m=\lceil\log k/c_{2}(r)\rceil$. Define a $(2r-3)$-dimensional family
$\mathcal{T}^{\prime}\subset\binom{P}{mr^{t}}^{2r-3}$ in the same way as
$\mathcal{T}$ was defined: namely, $S\in\mathcal{T}^{\prime}$ if there is an
$\mathcal{F}\in\boldsymbol{\mathcal{N}}$ such that $S\subset\mathcal{F}$. Note
that the property (N2) implies that if $S\in\binom{P}{mr^{t}}^{2r-3}$ is not
in $\mathcal{T}^{\prime}$, then neither is any family obtained from $S$ by
removing some elements from each set in $S$. Lemma 8 applied to the complement
of $\mathcal{T}^{\prime}$ yields

$\lvert\mathcal{T}^{\prime}\rvert\geq\binom{\lvert
P\rvert}{mr^{t+1}}^{2r-3}-\binom{(1-c_{2}(r))\lvert P\rvert}{mr^{t}}^{2r-3}.$

Let $H\subset\binom{\binom{P}{mr^{t}}}{2r-3}$ be a $(2r-3)$-uniform hypergraph
on $\binom{P}{mr^{t}}$ with edges

$\\{S_{1},\dotsc,S_{2r-3}\\}\in
H\iff(S_{1},\dotsc,S_{2r-3})\in\mathcal{T}^{\prime}\text{ and
}(S_{1},\dotsc,S_{2r-3})\text{ is $r$-good}.$

By Lemma 11, it follows that

$\displaystyle\lvert H\rvert$
$\displaystyle\geq\frac{1}{(2r-3)!}\left(\lvert\mathcal{T}^{\prime}\rvert-
c_{3}(r)(m^{2}r^{2t}/\lvert P\rvert)^{r-2}\binom{\lvert
P\rvert}{mr^{t}}^{2r-3}\right)$ $\displaystyle\geq\binom{\binom{\lvert
P\rvert}{mr^{t}}}{2r-3}\left(1-(1-c_{2}(r))^{(2r-3)mr^{t}}-c_{4}(r)(m^{2}/\lvert
P\rvert)^{r-2}\right)$

Since $m>\log k/c_{2}(r)$, and $\lvert
P\rvert\geq(9c_{4}(r))^{1/(r-2)}m^{2}k^{2}$ it follows that the density of $H$
is

$\lvert H\rvert/\binom{\binom{\lvert P\rvert}{mr^{t}}}{2r-3}\geq
1-k^{(2r-3)r^{t}}-(3k)^{-(2r-4)}\geq 1-(2k)^{-(2r-4)}$

for $k$ large enough.

By Lemma 9 the hypergraph $H$ contains a clique on $2k$ vertices. Let
$S_{1},\dotsc,S_{2k}\in\binom{P}{mr^{t}}$ be the vertices of this clique.
Since edges of $H$ are $r$-good among every $2r-3$ of these $2k$ sets there
are $r$ that are pairwise disjoint. Thus, by Lemma 10 there are $k$ of them,
say $S_{1},\dotsc,S_{k}$, that are pairwise disjoint.

We claim that for every $I\subset[k]$ there is a family
$\mathcal{F}_{I}\in\boldsymbol{\mathcal{N}}$ that contains $S_{i}$ for every
$i\in I$. The proof is by induction on $\lvert I\rvert$ starting with $\lvert
I\rvert=2r-3$. If $\lvert I\rvert=2r-3$, then the claim holds because
$\\{S_{i}:i\in I\\}$ is an edge in $H$. Suppose $\lvert I\rvert>2r-3$. Pick
any $r$ distinct $\lvert I\rvert-1$-element subsets $I_{1},\dotsc,I_{r}$ of
$I$. Then by by property (N5) applied to families
$\mathcal{F}_{I_{1}},\dotsc,\mathcal{F}_{I_{r}}$ it follows that there is a
$J\subset[r]$ so that $\mathcal{F}=(\bigcap_{j\in
J}\mathcal{F}_{I_{j}})\cup(\bigcap_{j\not\in
J}\mathcal{F}_{I_{j}})\in\boldsymbol{\mathcal{N}}$. Since the family
$\mathcal{F}$ contain $\mathcal{F}_{i}$ for every $i\in I$, we may put
$\mathcal{F}_{I}=\mathcal{F}$.

Finally, the family $\mathcal{F}_{[k]}$ contains $k$ disjoint sets
$S_{1},\dotsc,S_{k}$, as required. ∎

##  4 Convexity spaces with $r_{2}=3$

The space with $r_{2}=3$ are especially nice because of the following lemma,
which is implicit in [JW81].

######  Lemma 13.

Let $P$ be a set in a convexity space with $r_{2}=3$, and let
$\boldsymbol{\mathcal{N}}=\boldsymbol{\mathcal{N}}(P)$ be its nerve. Then
there is a family $\mathcal{F}_{p}\in\boldsymbol{\mathcal{N}}$ for each $p\in
P$, and these families satisfy

  1. (J1)

$\\{p\\}\in\mathcal{F}_{p}$.

  2. (J2)

If $p,q,r$ are any three points of $P$, then either
$\\{p,q\\}\in\mathcal{F}_{r}$ or $\\{p,r\\}\in F_{q}$ or
$\\{q,r\\}\in\mathcal{F}_{p}$.

  3. (J3)

If $\\{q,r\\}\in\mathcal{F}_{p}$ and $\\{r,s\\}\in\mathcal{F}_{q}$, then
$\\{r,s\\}\in\mathcal{F}_{p}$.

###### Proof.

Let $\mathcal{F}_{p}$ be a maximal family containing $\\{p\\}$. Then the other
conditions follow from the property (N5) applied to the triple of families
$\mathcal{F}_{p},\mathcal{F}_{q},\mathcal{F}_{r}$. ∎

###### Proof of Proposition 4.

Let $I=\\{(p,q,r):p\in\operatorname{conv}\\{q,r\\}\\}$. Since there are
$\binom{n}{3}$ triples $\\{p,q,r\\}$, each of which contributes at least at
least one element $I$, the proposition follows by the pigeonhole principle. ∎

Since Jamison’s proof of Eckhoff’s conjecture is especially short in the
language of nerves, we include it:

######  Theorem 14.

If $r_{2}=3$, then $r_{k}\leq 2(k-1)+1$.

###### Proof.

Suppose $\lvert P\rvert=2(k-1)+1$. We shall show that one of $\mathcal{F}_{p}$
contains $k$ pairwise disjoint sets. We claim that there is a pair of elements
$p,q\in P$ so that $\\{p,q\\}\in\mathcal{F}_{r}$ for every $r\neq p,q$.
Indeed, it is true if $\lvert P\rvert\leq 3$. If $\lvert P\rvert\geq 4$, and
$s$ is any element of $\mathcal{F}_{p}$, then by induction there is a $p,q\in
P\setminus\\{s\\}$ so that $\\{p,q\\}\in\mathcal{F}_{r}$ for every $r\neq
p,q,s$. If in addition $\\{p,q\\}\in\mathcal{F}_{s}$, then we are done.
Otherwise by property (J2) either $\\{p,s\\}\in\mathcal{F}_{q}$ or
$\\{q,s\\}\in\mathcal{F}_{p}$. Say $\\{p,s\\}\in\mathcal{F}_{q}$. Then by
property (J3) applied to $\\{p,q\\}\in\mathcal{F}_{r}$ and either
$\\{p,s\\}\in\mathcal{F}_{q}$ we conclude that $\\{p,s\\}$ is in every
$\mathcal{F}_{r}$, $r\neq p,s$. The claim is proved.

Let $p,q$ be a pair of element so that $\\{p,q\\}\in\mathcal{F}_{r}$ for
$r\neq p,q$. By the induction hypothesis applied to $P\setminus\\{p,q\\}$
there is $r\in\\{p,q\\}$ so that $\mathcal{F}_{r}$ contains $k-1$ disjoint
sets that are also disjoint from $\\{p,q\\}$. Together with $\\{p,q\\}$ these
form a desired family of disjoint sets. ∎

## References

  * [ABFK92] Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman.  Point selections and weak $\epsilon$-nets for convex hulls.  Combin. Probab. Comput., 1(3):189–200, 1992.  http://www.tau.ac.il/~nogaa/PDFS/abfk3.pdf.
  * [AS07] Noga Alon and Benny Sudakov.  On graphs with subgraphs having large independence numbers.  J. Graph Theory, 56(2):149–157, 2007.  http://www.math.ucla.edu/~bsudakov/erdos-hajnal.pdf.
  * [Bár82] Imre Bárány.  A generalization of Carathéodory’s theorem.  Discrete Math., 40(2-3):141–152, 1982.
  * [Bir59] B. J. Birch.  On $3N$ points in a plane.  Proc. Cambridge Philos. Soc., 55:289–293, 1959.
  * [Buk10] Boris Bukh.  Multidimensional Kruskal–Katona theorem.  arXiv, Sep 2010.
  * [Cal71] J. R. Calder.  Some elementary properties of interval convexities.  J. London Math. Soc. (2), 3:422–428, 1971.
  * [dC83] D. de Caen.  Extension of a theorem of Moon and Moser on complete subgraphs.  Ars Combin., 16:5–10, 1983.
  * [DRS81] Jean-Paul Doignon, John R. Reay, and Gerard Sierksma.  A Tverberg-type generalization of the Helly number of a convexity space.  J. Geom., 16(2):117–125, 1981.
  * [Eck79] Jürgen Eckhoff.  Radon’s theorem revisited.  In Contributions to geometry (Proc. Geom. Sympos., Siegen, 1978), pages 164–185. Birkhäuser, Basel, 1979.
  * [Eck00] Jürgen Eckhoff.  The partition conjecture.  Discrete Math., 221(1-3):61–78, 2000.  Selected papers in honor of Ludwig Danzer.
  * [JW81] Robert E. Jamison-Waldner.  Partition numbers for trees and ordered sets.  Pacific J. Math., 96(1):115–140, 1981.  http://projecteuclid.org/getRecord?id=euclid.pjm/1102734951.
  * [Rad21] Johann Radon.  Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten.  Math. Ann., 83(1-2):113–115, 1921.
  * [SB83] Gerard Sierksma and Jan Ch. Boland.  On Eckhoff’s conjecture for Radon numbers; or how far the proof is still away.  J. Geom., 20(2):116–121, 1983.
  * [Tve66] H. Tverberg.  A generalization of Radon’s theorem.  J. London Math. Soc., 41:123–128, 1966.
  * [vdV93] M. L. J. van de Vel.  Theory of convex structures, volume 50 of North-Holland Mathematical Library.  North-Holland Publishing Co., Amsterdam, 1993.


11institutetext: Suraj Pandey 22institutetext: The Open University, Walton
Hall, Kents Hill, Milton Keynes MK7 6AA, 22email<EMAIL_ADDRESS>33institutetext: Svetlana Stoyanchev, Rama Doddipatla 44institutetext: Toshiba
Europe Ltd., Cambridge Research Laboratory, 208 Cambridge Science Park Milton
Rd, Cambridge CB4 0GZ 44email:
<EMAIL_ADDRESS>
# Towards Handling Unconstrained User Preferences in Dialogue

Suraj Pandey  Svetlana Stoyanchev and Rama Doddipatla

###### Abstract

A user input to a schema-driven dialogue information navigation system, such
as venue search, is typically constrained by the underlying database which
restricts the user to specify a predefined set of preferences, or slots,
corresponding to the database fields. We envision a more natural information
navigation dialogue interface where a user has flexibility to specify
unconstrained preferences that may not match a predefined schema. We propose
to use information retrieval from unstructured knowledge to identify entities
relevant to a user request. We update the Cambridge restaurants database with
unstructured knowledge snippets (reviews and information from the web) for
each of the restaurants and annotate a set of query-snippet pairs with a
relevance label. We use the annotated dataset to train and evaluate snippet
relevance classifiers, as a proxy to evaluating recommendation accuracy. We
show that with a pretrained transformer model as an encoder, an
unsupervised/supervised classifier achieves a weighted F1 of .661/.856.

##  1 Introduction

Figure 1: Process for building a supervised relevance scoring model.

A conversation is a natural user interface for accessing information. In
information navigation dialogue, such as search (for restaurants, hotels, or
tourist attractions), a user specifies search constraints and navigates over
search results using text-based, spoken, or multi-modal interface. Information
navigation tasks are typically handled with a schema-driven approach
budzianowski-etal-2018-multiwoz ; schema-guided ; stoyanchev-asu-2021 . While
a schema-driven system may be effectively bootstrapped for a new application
using the structure and content of the corresponding database, a user is
limited in the range of constraints they may specify. For example, in a
restaurant search domain with the schema fields area, price range and food
type, a user may specify any combination of these fields but not others
henderson-thomson-williams:2014:W14-43 . To evaluate a schema-driven
information navigation system, the recruited experiment participants are
typically given a conversation ‘goal’ based on the database schema, e.g. “you
are looking for a cheap Italian place in the center”, and are instructed to
retrieve matching venues using spoken or text chat interaction. These
instructions guide the user to specify in-domain preferences that can be
handled by the dialogue system. An initial user request based on the above
‘goal’ may be:

> User: ‘A cheap Italian restaurant in the centre’
> User: ‘I am looking for a cheap place’
> User: ‘A restaurant in the center’
> User: ‘An Italian restaurant in cheap price range’111A system may ask to
> narrow down the search criteria and a user may specify additional
> preferences in consecutive turns.
> User: …

While there is variability in the natural language utterances of a recruited
user for a predefined ‘goal’, the preference type specified in the goal is
limited to the schema.

Unlike the recruited subjects, real users come up with personalised search
preferences and formulate their requests to the system without a bias of the
instructions. The challenge is that a user request with preferences outside of
the domain schema, e.g. ‘Find me a cosy family friendly pub that serves
pizza.’ can not be handled by a purely schema-driven system. The majority of
user queries (75 out of 105) that we collected without priming the user by a
predefined ‘goal’ do not mention any of the domain-specific schema fields,
indicating that a purely schema-driven system is not sufficient to handle
naturally constructed user requests. In contrast to a schema-driven dialogue
system, a search interface handles such unconstrained user queries using
information retrieval methods from unstructured (text) data. Search
interfaces, however, are not interactive and do not handle query changes or
follow-up questions. In this work, we aim to improve the naturalness of
interaction  with an information navigation dialogue system. We propose to
extend the schema-driven dialogue system to handle out-of-schema user queries
by incorporating an entity retrieval module in the dialogue system pipeline.

An entity retrieval model requires domain-specific data to extract the
requested information. For this study, we create an annotated dataset for the
Cambridge Restaurants domain following the process outlined in Figure 1. We
first collect a database from the Web, including text snippets composed from
restaurant reviews and descriptions along with a set of unconstrained
restaurant search queries. Next, unsupervised and transfer learning methods
are used to obtain a set of query-snippet pairs which are then annotated using
Amazon Mechanical Turk. The resulting annotated dataset is then used to build
supervised relevance scoring models and compared with the performance of
unsupervised and transfer learning approaches. We show that using a pretrained
transformer model as an encoder, an unsupervised/supervised classifier of the
snippet relevance to the query achieves a weighted F1 of .661/.856.

The contributions of this paper are:

  * •

A methodology for extending a schema-driven dialogue system to support natural
user preferences.

  * •

A manually annotated dataset with 1.7K query and text snippet pairs.

  * •

Evaluation of supervised, unsupervised, and transfer learning approaches for
snippet relevance classification.

The rest of the paper is organized as follows. In Section 2, we outline
related research. In Section 3, we present an extended Cambridge Restaurants
2021 dataset and annotated REStaurant Query Snippet dataset (ResQS). In
Section 4, we describe the approaches used to detect text snippets relevant to
a query and present experimental results in Section 5. Finally, the
conclusions are presented in Section 6.

##  2 Related Work

Conversational search aims at providing users with an interactive natural
language interface for access to unstructured open-domain information
trippas2018informing . Similarly, task-oriented information navigation
dialogue systems often involve search, e.g. for venues or catalogue items
budzianowski-etal-2018-multiwoz ; 10.5555/3298023.3298238 . While open-domain
conversational search has a wider scope than closed-domain search in task-
oriented dialogue, empirical analysis shows that both tasks result in a
similar conversational structure 10.1007/978-3-030-15712-8_35 .

Open-domain search interfaces and task-oriented information navigation
dialogue systems both take unconstrained natural language as input. However,
dialogue system users are typically limited in expressing their preferences by
the domain schema. In response to an out-of-schema user request, a task-
oriented dialogue system may produce an informative help message guiding the
user to adapt to its limitations DBLP:journals/umuai/KomataniUKO05 ; tomko-
rosenfeld-2004-speech . Alternatively, system capabilities may be extended
beyond a domain API. For example, Kim et al. kim-etal-2020-beyond  proposes a
method for handling users’ follow-up questions in task-oriented dialogue
systems. To support pragmatic interpretation, Louis at al. louis-etal-2020-id
explores users’ indirect responses to questions. To extend a task-oriented
system to handle natural preferences, a corpus of natural requests for movie
preferences was collected using a novel approach to preference elicitation
Radlinski2019 .

Task-oriented dialogue systems require accurate models to extract information
from unstructured text. Pretrained transformer models, such as BERT
devlin2019bert , have shown to be effective in extracting information from
text, leading to significant improvements on many NLP tasks, including open-
domain question answering, FAQ retrieval, and dialogue generation
wang2019multi ; sakata2019faq ; kim-etal-2020-beyond . Following previous
work, we use BERT both in a supervised and an unsupervised setting
izacard2021leveraging ; 10.1145/3397271.3401325 . We also explore transfer
learning from a general natural language entailment task using publicly
available corpora conf/emnlp/BowmanAPM15 .

##  3 Data

To develop and evaluate an entity retrieval component for a dialogue system
that handles unconstrained user queries, it is necessary to construct a
dataset that includes text snippets associated with the entities, collect
unconstrained user queries, and identify a set of matching entities for the
queries. We collect a new extended dataset of Cambridge restaurants (Section
3.1), a set of unconstrained search queries (Section 3.2), and annotate query-
snippet pairs with relevance labels (Section 3.3).

###  3.1 Cambridge Restaurants 2021

In previous work henderson-thomson-williams:2014:W14-43 , the authors used a
now outdated dataset of 102 Cambridge restaurants, which did not have review
information. In this work, we created an up-to-date database with 422
restaurants in Cambridge, UK.222The dataset is compiled by crawling the Web in
January 2021. Following the schema used in previous work, each restaurant is
associated with cuisine, price range, location, and description. As in the
past systems, the price range is mapped to cheap, moderate, expensive and
location to east, west, centre, south. However, cuisine in our database is
associated with a list of values rather than a single value for each entity.
In addition, the new dataset includes information on meals (breakfast, lunch,
dinner), special diets (e.g., vegan, gluten free) and reviews.

A standard restaurant database may not always contain information relating to
the unconstrained user’s search preferences (example, cosy family friendly
pub). In such regards, we theorise that personalised messages, such as
reviews, are an acceptable source to handle such requests. We collect 62.3K
reviews with an average and standard deviation of 145(256) per restaurant. The
reviews together with text in each data fields are used as text snippets to
retrieve items relevant to the query in the experiments. Only positive reviews
(rating 4 or 5 stars) are used, as we expect user queries to mention desirable
properties of the restaurant.

###  3.2 Unconstrained Queries

To simulate natural unbiased user requests in a restaurant search domain, we
created an online form with one question: Please type a sentence describing
your restaurant preference to your smart virtual assistant.’ The form was
distributed to several university and company mailing lists. Each participant
was asked to enter one query.333As the task was very short, the participants
were not paid.

We found that only 30 out of 105 collected queries specified a constraint
corresponding to one of the pre-defined fields of the database schema (area,
cuisine, or price range) that may be used to search for a restaurant in a
purely schema-driven system. Although only 14 of these queries contained an
entity exactly matching a value in the database and only 7 had no other
preferences besides the slot value. For example, ‘I would like to eat in a
fine dining establishment, preferably french cuisine.’ contains a mention of
cuisine as well as a vague preference for a ‘fine dining establishment’. The
unbiased queries are highly diverse and most frequently contain a menu item
(46), a subjective (31) or an objective preference (25) about a restaurant
(see Table 1). We removed 5 queries that mention proximity, e.g. ‘near me’.
Such queries would not be handled with the proposed method as it would require
additional geographical location information. We use the remaining 100 queries
in our experiments.

Table 1: Preferences (number of queries) mentioned by the users in 105 unbiased queries.  preference |  examples
---|---
menu item (46) |  burger, veggie burger, pizza, curry, steak, fried rice, meat, sushi, seafood, noodle bar, dim-sum, shark, eel, alcohol, wine, mulled wine, beer, whisky, milkshake, dessert
objective (25) |  live music, music, quiet, dogs, kids, fireplace, free delivery, local food, new place, biggest pizza, spicy food, large groups, Burn’s night, big pizza,sweet tooth, traditional, portion size, restaurant name, parking, quick, outdoor seating, spaced out tables, byob
subjective (31) |  ambience, friendly, gourmet, authentic, romantic, cozy, small, local, safe, different, inventive, stylish, exotic, interesting, hygienic, fine dining, best value, fancy, nothing too fancy

###  3.3 Query-Snippets Annotation

For extracting relevant entities using unstructured data, we need to develop
supervised models, which require preferably a balanced training dataset. We
create a REStaurant Query Snippet (ResQS) dataset of query-snippet pairs,
where the snippets include text from reviews and each of the database fields,
labelled with ‘1’ if the snippet is relevant  to the query and ‘0’, otherwise.
For each query, most of the snippets from our set of 62.3K candidates will be
irrelevant. Thus, a random selection of snippets for each query would result
in an unbalanced dataset of mostly irrelevant snippets. Instead, unsupervised
and transfer learning methods are used to select a set of relevant snippets
for each query. We then use manual annotation on the selected set to create
query-snippet pairs with annotated relevance information.

For each of the 100 queries, we first score all snippets using two
unsupervised and one transfer learning method (see the first three methods
shown in Figure 2). Next, we compute a relevance score for each of the 422
restaurants in the dataset and use it to rank them (see Section 4). Finally,
we randomly sample one of the five top-ranked restaurants for the query444The
number of top results (5) was chosen empirically since a user of a dialogue
system may navigate over multiple search results. and manually label the top
five snippets that were used to compute the relevance score of this
restaurant. Manual labels are used for the evaluation of the unsupervised
methods as well as for training the supervised models. Using three methods to
select five snippets per query we generate $1500$ query-snippet pairs.
Additionally, to simulate the hybrid system where both relevance ranking and
database match are used to extract a relevant item, we use the 14 queries that
specify a value for one of the system slots (_area_ , _cuisine_ , or _price
range_). This subset is then used to select a recommended restaurant for the
query. Thus by using three methods to select five snippets for the 14 queries
we extend the dataset by $210$ query-snippet pairs resulting in $1710$
examples.

For annotation, we use crowd workers from Amazon Mechanical Turk. Each Human
Intelligence Tasks (HIT) consists of 23 randomized query-snippet pairs and is
annotated by three crowd workers.5553 query-snippet pairs with a known label
are used to monitor work quality. The workers that did not pass the quality
test were rejected. The workers were compensated according to government pay
guidance.666https://www.gov.uk/national-minimum-wage-rates We use the majority
vote amongst the three crowd workers to select the final label. The pairwise
agreement between each annotator and the majority vote is very good with
Fleiss Kappa $k>.7$ fleiss1973equivalence .

Algorithm 1 Relevance ranking

1:procedure RankAndSelect($Query$,$~{}Dataset$, $J$, $N$)

2: Input: $Query$ is a String of user’s request

3: Input: $Dataset$ is a collection of items with associated snippets
${Item:[S1,S2,...]}$

4: Input: $J$ is the number of top snippets used to compute the score

5: Input: $N$ is the number of items to return

6: Output: List of top $N$ items for the $Query$

7: for each $Item\in Dataset$ do

8: for each $Snippet\in Item$ do

9: $Snippets[score]=RelevanceScore(Query,Snippet)$

10: $Sorted\\_Snippets=Sort(Snippets.score,order=descending)$

11: ${\displaystyle
Item[score]={\frac{1}{J}}\sum_{i=1}^{J}Sorted\\_Snippets\\_i[score]}$

12: $Sorted\\_Items=Sort(Items.score,order=descending)$

13: return $[Sorted\\_Items_{1}..Sorted\\_Items_{N}]$

##  4 Method

In this work, we extend a schema-driven dialogue system to support users’
unconstrained search requests. Our goal is to extract the items most relevant
to the users’ query. A dialogue system then presents these items as
recommendations to the user and responds to follow-up questions. This work
only addresses the extraction of the relevant items, leaving the evaluation of
information presentation and handling of interaction to future work. We apply
and evaluate our approach using the Cambridge Restaurants search domain.

Algorithm 1 is used to extract an item most relevant to the user’s query.
First the snippets are scored (line 9) then the top recommended restaurants
are obtained by ranking the list of restaurants based on the average score of
the top 5 snippets.777We use empirically chosen J=5 and N=5 in this work.

For snippets scoring, we explore two unsupervised approaches: Cos-TF-IDF and
Cos-BERT, and two supervised approaches: transfer learning from another domain
(Trans-BERT), and in-domain training approach (Dom-BERT) illustrated on Figure
2. The input to each of the models are two strings (query and text snippet)
and the output is a score where the scores closer to 1 indicate a higher
relevance.

Figure 2: Relevance scoring methods.

###  4.1 Unsupervised Approach

We expect relevant text snippets to have a higher word overlap and semantic
similarity with the corresponding query. For example, for a user query:

> Query: I am looking for a place that serves vegan food and also allows dogs
> inside.

the two relevant snippets have overlapping vocabulary:

>   1. 1.
>
> Special diets: vegan friendly
>
>   2. 2.
>
> Review: It was such a happy surprise that they allowed dogs inside their
> premises. Fanta was woofing with delight.
>
>

We map the user query ($Q_{i}$) and each snippet ($S_{j}$) for all of the
restaurants into a fixed-sized vector using a mapping function $M$. We then
compute the cosine similarity score between the user request and each snippet:

$Score(Q_{i},S_{j})=cos(M(Q_{i}),M(S_{j}))$

The cosine score estimates the distance between the query $Q_{i}$ and snippet
$S_{j}$.

Cos-TF-IDF: Cosine similarity with TF-IDF Encoding
As a baseline, we use Term Frequency-Inverse Document Frequency(TF-IDF), an
efficient and simple algorithm for matching words in a query to documents that
are relevant to that query, to encode the query and the knowledge snippets
salton1988term . Text snippet for each restaurant is taken as a separate
document to calculate TF-IDF for each word in the snippet. TF-IDF score for
each word in the query is also calculated. Then, the words in the query and
the words in the text snippet are replaced by their TF-IDF score to form
vocabulary-sized vectors.888The vocabulary size in our domain is 30124. The
cosine score corresponds to the vocabulary overlap between $Q_{i}$ and
$S_{j}$.

Cos-BERT: Cosine similarity using BERT encoding
We use pretrained Sentence-BERT (SBERT) model to encode the query and the
snippets reimers2019sentence . SBERT uses a pooling operation to obtain the
mean of all output vectors of BERT, fine-tuned on the SNLI corpus, to derive a
fixed-sized sentence embedding devlin2019bert . The cosine score corresponds
to the semantic distance between $Q_{i}$ and $S_{j}$.

###  4.2 Supervised Approach

We build a classifier using a DNN with a single fully-connected linear layer
that takes as input encoded representation of a query and a snippet. The input
($<CLS>query<SEP>snippet$) is encoded with the pretrained BERT model and the
encoding of the special symbol ($CLS$) is passed into a linear layer that
outputs a 2- or 3-way classification. The model is trained to minimize cross-
entropy on the training set.

Trans-BERT: Transfer Learning Approach
For transfer learning we use Stanford Natural Language Inference (SNLI) and
DSTC9 datasets 10.5555/3298023.3298238 ; kim-etal-2020-beyond . SNLI corpus is
a collection of 570,000 sets of premises and hypotheses sentences annotated
with the labels contradiction, entailment, and neutral as in the following
example:

> Premise: A boy is jumping on skateboard in the middle of a red bridge.
> Entailment: The boy does a skateboarding trick.
> Contradiction: The boy skates down the sidewalk.
> Neutral: The boy is wearing safety equipment.
>

The intuition behind using a model trained on the SNLI dataset is that the
relevant snippet for the user’s query would be classified as entailment while
the irrelevant snippets would be classified as neutral or contradiction.
Hence, we train a 3-way classification and use the score of entailment class
to estimate relevance.

DSTC9 dataset was constructed for the purpose of extracting answers to follow-
up questions in a dialogue system. It contains 938 question and answer pairs
for the train, hotel, and restaurant domains as shown in following examples.

> Request: Are children welcomed at this location?
> Reply: Yes, you can stay with children at A and B Guest House.
>
> Request: Can my small dog stay with me?
> Reply: Pets are not allowed at the A and B Guest House.
>

We use the question-answer pairs as the positive examples (relevant) for
training the model. The negative examples for training a binary classifier are
extracted by randomly sampling answers from different questions following the
approaches used by the authors.

Dom-BERT: In-domain Training Approach
The models that are trained on in-domain data usually achieve better
performance. To compare the models trained with the in-domain data with the
transfer/unsupervised approaches, we train a supervised binary classifier on
ResQS and the combination of ResQS and DSTC9 datasets. A pre-trained BERT
encoder was fine-tuned on the in-domain classification task using the pruning
method that removes the task-irrelevant neural connections from the BERT model
to better reflect the data for the task DBLP:journals/corr/abs-2105-03343 .

##  5 Experiments and Results

Evaluating the overall relevance of a recommended restaurant is challenging,
as the information presented to the user would bias their judgement. We assume
that the restaurants preferred by the user are associated with the snippets
that are relevant to the query. The models are evaluated based on the scores
they assign to the snippets.

We use the two unsupervised and the transfer learning from SNLI models for
information retrieval to extract a recommended restaurant for each query by
ranking restaurants based on the relevance score of the snippets (see Section
5.1). The dataset produced with the information retrieval is then manually
annotated and used to train supervised snippet relevance classification
models. To compare snippet relevance classification methods, we use a
threshold to classify each snippet’s relevance to the query and compute the
classifier’s precision, recall, and F1 (see Section 5.2).

###  5.1 Information Retrieval

Table 2: Snippet Relevance and the overall recommendation of information
retrieval.

Model | Snippet Relevance | Overall Recommendation
---|---|---
|  All
---
(500)
| Menu Item
---
(230)
| Objective
---
(125)
| Subjective
---
(155)
| % with at least one
---
relevant snippet
| avg number of
---
relevant snippets
Cos-TF-IDF | 65 % | 59% | 53% | 67% | 83% | 3.25
Cos-BERT | 57 % | 61% | 55% | 60% | 86% | 2.86
Transfer-BERT (SNLI) | 16 % | 10% | 13% | 20% | 41% | 0.79

For each of the queries we apply unsupervised and transfer learning methods to
score each snippet and use these scores to rank the restaurants. As a dialogue
system can present multiple options in response to a query, we randomly select
one of the top five recommended restaurants and manually annotate the top five
matching snippets with a binary label relevant/not-relevant (see Section 3.3).
For the two unsupervised cosine-similarity (Cos-TF-IDF and Cos-BERT) and
transfer (Trans-BERT-SNLI) methods we report the snippet relevance (the
percent of snippets extracted by the model labelled as relevant) and the
overall recommendation quality (see Table 2). We further analyze the relevance
scoring performance across three query types that mention a menu item,
objective, or subjective information.

Cosine similarity approach using TF-IDF encoding (Cos-TF-IDF), which relies on
exact keyword match, achieves the highest overall snippet relevance of 65%,
followed by Cos-BERT with 57%. Transfer learning did not work well, yielding
only 16% snippet relevance. We observe that Cos-TF-IDF performance is the
highest (67%) on the queries with subjective information that contain
adjectives (‘excellent’, ‘great’). However, its performance is below Cos-BERT
model on the queries with objective and menu item information (‘fireplace’,
‘dogs’, ’desserts’). For a user query ‘Find me a restaurant with great
desserts’, Cos-TF-IDF model extracts a restaurant with generic positive
reviews which are not relevant to the query:

>   1. 1.
>
> Review: Great service, great food, had a great night! Good value for money
> and great atmosphere, definitely coming back.
>
>   2. 2.
>
> Review: Great find in cambridge
>
>

However, Cos-BERT model extracts a restaurant with the snippets relevant to
this query that focus on the quality of deserts:

>   1. 1.
>
> Review: The food in this restaurant is very good. However, it is the
> desserts that steal the show. I have sometimes been there just for dessert.
>
>   2. 2.
>
> Review: Fabulous french style food and cocktails. we plan to return for
> dessert only as the selection looked amazing and we were quite full from our
> meal.
>
>

Using BERT for embedding the query and the snippets appears to capture the
semantics which is especially important for the queries with objective
information.

The overall recommendation accuracy is the proportion of recommended
restaurants that would satisfy the user. We approximate the subjective user
satisfaction with 1) the percentage of the queries for which at least one of
the top five snippets was labelled as relevant and 2) the average number of
the top five snippets labeled as relevant. Cos-BERT model outperforms the Cos-
TF-IDF on the first metric (86% vs 83%) and Cos-TF-IDF outperforms Cos-BERT on
the second one (3.25 vs 2.86).

Our dataset contains 62.3K snippets. Exact word match (TF-IDF) may have
outperformed the semantic method (Cos-BERT) because it was likely to find
exact word match for each query. However, for smaller datasets, where
vocabulary in a query may not match any of the text snippet, semantic methods
may be more beneficial.

The overall relevance scoring accuracy is 48%, resulting in a balanced dataset
of 1710 query-snippet (ResQS) pairs which we use to train and evaluate
supervised relevance labeling models described in the next section.

###  5.2 Snippet Relevance Classification

Table 3: Relevance classification performance on ResQS dataset. Model Type | Training data | Avg Precision | Avg Recall | Weighted F1
---|---|---|---|---
| Always-relevant
---
baseline
- | 0.240 | 0.490 | 0.322
Unsupervised methods
Cos-TF-IDF | - | 0.752 | 0.519 | 0.365
Cos-BERT | - | 0.703 | 0.672 | 0.661
Transfer learning methods
Trans-BERT | SNLI | 0.429 | 0.493 | 0.368
Trans-BERT | DSTC9 | 0.771 | 0.768 | 0.769
Supervised in-domain training methods
Dom-BERT | ResQS | 0.829 | 0.825 | 0.824
Dom-BERT |  ResQS + DSTC9 | 0.859 | 0.857 | 0.856

We compare the snippet relevance classification performance of the
unsupervised (Cos-TF-IDF, Cos-BERT), transfer (Trans-BERT) and supervised
(Dom-BERT) methods. The unsupervised cosine similarity methods use a threshold
of 0.5 to determine relevance of a snippet to a query. The Trans-BERT models
are trained on the publicly available SNLI and DSTC9 datasets. The model
trained on SNLI dataset outputs a 3-way classification with the classes
contradiction, entailment, and neutral. To apply it on our binary query
relevance detection task, we combine contradiction and neutral into the not
relevant class and use entailment as the relevant class. The unsupervised and
transfer methods are evaluated on the full ResQS corpus as they do not use any
of its data for training and the supervised methods are evaluated with 10-fold
cross-validation.

Table 3 shows the average precision, recall, and weighed F1 scores on the
ResQS dataset. Cos-TF-IDF method achieves F1 of 0.365, slightly higher than
the baseline that predicts all snippets as relevant (F1=0.322) while Cos-BERT
achieves F1 of 0.661. We observe that Cos-TF-IDF which relies on word match
has a lower recall than Cos-BERT which captures semantic meaning (0.519 vs
0.672).

The Transfer-BERT trained on SNLI achieves F1 of 0.368, slightly higher than
the always-relevant baseline but lower than the unsupervised Cos-BERT model.
The Trans-BERT model trained on DSTC9, a dataset more closely resembling to
the target data, achieves F1 of 0.769 outperforming both of the unsupervised
methods. The model trained on in-domain ResQS dataset achieves F1 of 0.824 and
outperforms all unsupervised and transfer learning models. The best result
(F1=0.856) is obtained by training on the combined in-domain ResQS and DSTC9
dataset.

###  5.3 Discussion

Our aim was to collect data that covers most of the aspects of the individual
restaurants. In addition to the standard aspects (cuisine, location) provided
by the restaurants, we also used reviews which augmented the restaurant
information with further non-standard (fireplace, dogs, exotic) aspects thus
providing a comprehensive unstructured dataset for handling unconstrained
queries.

We then test how accurately an unsupervised method can extract relevant items
using unstructured data. Cosine similarity with the BERT encoder method
resulted in 57% relevant snippets on the information retrieval task and
achieved F1 score of .661 on the snippet relevance classification task. With
this approach 86% of top-5 recommended restaurants had at least one relevant
snippet (the estimated recommendation accuracy). Assuming that an item with
more relevant snippets is a better match for a user query, we expect to
achieve even higher restaurant recommendation accuracy using a more accurate
supervised snippet relevance scoring model. The supervised model achieves F1
score of 0.856 on the snippet relevance classification task.

Although we achieve improvements with the supervised models, it should be
noted that they are slower compared to unsupervised methods999Experiments were
conducted with i7-6 cores CPU and single GTX 1080 GPU.. If using a supervised
model to extract relevant information from unstructured data is not real-time,
it becomes unfeasible for use in a dialogue system. To reduce latency while
maintaining accuracy, we could use a combination of models by first filtering
snippets with an unsupervised method and then applying a supervised model on a
smaller dataset.

##  6 Conclusions

In this work, we aim to improve naturalness of interaction with an information
navigation dialogue system. When a user is not primed by instructions, most
user queries in the restaurant search domain include out-of-schema search
preferences. Such queries cannot be handled by a purely schema-driven dialogue
system, resulting in ineffective and unnatural conversations. To address this
problem, we propose an entity retrieval method by incorporating a snippet
relevance classifier into the pipeline of a schema-driven dialogue system.

We present an effective methodology for extending schema-driven dialogue
systems to use unstructured knowledge and handle out-of-schema user
preferences.101010The project was completed during during a four month
internship and the annotation costs were under $300. We update the Cambridge
restaurants database, and extend it with text knowledge snippets. To simulate
a naive user, we collect restaurant queries from users without biasing them
with specific instructions In our experimental restaurant search domain, the
snippets were obtained from publicly available restaurant reviews and
descriptions and annotated by Amazon Mechanical Turk workers. We build a
supervised text relevance classification model on the annotated data and
compare its performance with an unsupervised method. We show that on the
annotated dataset an unsupervised/supervised classifier achieves a weighted F1
of .661/.856. In future work, we will incorporate the proposed approach into
the Cambridge restaurant search dialogue system and evaluate it with users.

## References

  * (1) Bowman, S.R., Angeli, G., Potts, C., Manning, C.D.: A large annotated corpus for learning natural language inference.  In: L. Màrquez, C. Callison-Burch, J. Su, D. Pighin, Y. Marton (eds.) EMNLP, pp. 632–642. The Association for Computational Linguistics (2015)
  * (2) Budzianowski, P., Wen, T.H., Tseng, B.H., Casanueva, I., Ultes, S., Ramadan, O., Gašić, M.: MultiWOZ - a large-scale multi-domain Wizard-of-Oz dataset for task-oriented dialogue modelling.  In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 5016–5026. Brussels, Belgium (2018)
  * (3) Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding.  In NAACL-HLT (2019)
  * (4) Fleiss, J.L., Cohen, J.: The equivalence of weighted kappa and the intraclass correlation coefficient as measures of reliability.  Educational and psychological measurement 33(3), 613–619 (1973)
  * (5) Gao, Y., Colombo, N., Wang, W.: Adapting by pruning: A case study on BERT.  CoRR abs/2105.03343 (2021)
  * (6) Henderson, M., Thomson, B., Williams, J.D.: The second dialog state tracking challenge.  In: Proceedings of the 15th Annual SIGdial Meeting on Discourse and Dialogue, pp. 263–272 (2014)
  * (7) Izacard, G., Grave, É.: Leveraging passage retrieval with generative models for open domain question answering.  In: Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp. 874–880 (2021)
  * (8) Kim, S., Eric, M., Gopalakrishnan, K., Hedayatnia, B., Liu, Y., Hakkani-Tur, D.: Beyond domain APIs: Task-oriented conversational modeling with unstructured knowledge access.  In: Proceedings of the 21th Annual Meeting of the Special Interest Group on Discourse and Dialogue, pp. 278–289. Association for Computational Linguistics, 1st virtual meeting (2020)
  * (9) Komatani, K., Ueno, S., Kawahara, T., Okuno, H.G.: User modeling in spoken dialogue systems to generate flexible guidance.  User Model. User Adapt. Interact. 15(1-2), 169–183 (2005)
  * (10) Louis, A., Roth, D., Radlinski, F.: “I’d rather just go to bed”: Understanding indirect answers.  In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7411–7425. Association for Computational Linguistics, Online (2020)
  * (11) Radlinski, F., Balog, K., Byrne, B., Krishnamoorthi, K.: Coached conversational preference elicitation: A case study in understanding movie preferences.  In: Proceedings of the Annual SIGdial Meeting on Discourse and Dialogue (2019)
  * (12) Rastogi, A., Zang, X., Sunkara, S., Gupta, R., Khaitan, P.: Schema-guided dialogue state tracking task at DSTC8.  In: Proceedings of the AAAI Dialog System Technology Challenges Workshop (2020)
  * (13) Reimers, N., Gurevych, I.: Sentence-bert: Sentence embeddings using siamese bert-networks.  In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 3982–3992 (2019)
  * (14) Sakata, W., Shibata, T., Tanaka, R., Kurohashi, S.: Faq retrieval using query-question similarity and bert-based query-answer relevance.  In: Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1113–1116 (2019)
  * (15) Salton, G., Buckley, C.: Term-weighting approaches in automatic text retrieval.  Information processing & management 24(5), 513–523 (1988)
  * (16) Stoyanchev, S., Keizer, S., Doddipatla, R.: Action state update approach to dialogue management.  In: ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7398–7402 (2021)
  * (17) Tomko, S., Rosenfeld, R.: Speech graffiti vs. natural language: Assessing the user experience.  In: Proceedings of HLT-NAACL 2004: Short Papers, pp. 73–76. Association for Computational Linguistics, Boston, Massachusetts, USA (2004)
  * (18) Trippas, J.R., Spina, D., Cavedon, L., Joho, H., Sanderson, M.: Informing the design of spoken conversational search: Perspective paper.  In: Proceedings of the 2018 Conference on Human Information Interaction & Retrieval, CHIIR ’18, pp. 32–41. ACM, New York, NY, USA (2018)
  * (19) Vakulenko, S., Revoredo, K., Di Ciccio, C., de Rijke, M.: Qrfa: a data-driven model of information-seeking dialogues.  In: L. Azzopardi, B. Stein, N. Fuhr, P. Mayr, C. Hauff, D. Hiemstra (eds.) Advances in Information Retrieval, pp. 541–557. Springer International Publishing, Cham (2019)
  * (20) Wang, Z., Ng, P., Ma, X., Nallapati, R., Xiang, B.: Multi-passage bert: A globally normalized bert model for open-domain question answering.  In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 5881–5885 (2019)
  * (21) Yan, Z., Duan, N., Chen, P., Zhou, M., Zhou, J., Li, Z.: Building task-oriented dialogue systems for online shopping.  In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI’17, p. 4618–4625. AAAI Press (2017)
  * (22) Zhan, J., Mao, J., Liu, Y., Zhang, M., Ma, S.: An Analysis of BERT in Document Ranking, p. 1941–1944.  Association for Computing Machinery, New York, NY, USA (2020)