# Interactive Acquisition of Fine-grained Visual Concepts by Exploiting
Semantics of Generic Characterizations in Discourse

Jonghyuk Park  Alex Lascarides  Subramanian Ramamoorthy
School of Informatics, University of Edinburgh
10 Crichton Street, Edinburgh EH8 9AB, UK
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Interactive Task Learning (ITL) concerns learning about unforeseen domain
concepts via natural interactions with human users. The learner faces a number
of significant constraints: learning should be online, incremental and few-
shot, as it is expected to perform tangible belief updates right after novel
words denoting unforeseen concepts are introduced. In this work, we explore a
challenging symbol grounding task—discriminating among object classes that
look very similar—within the constraints imposed by ITL. We demonstrate
empirically that more data-efficient grounding results from exploiting the
truth-conditions of the teacher’s generic statements (e.g., “Xs have attribute
Z.”) and their implicatures in context (e.g., as an answer to “How are Xs and
Ys different?”, one infers Y lacks attribute Z).

##  1 Introduction

Consider a general-purpose robot assistant purchased by a restaurant, which
must acquire novel domain knowledge to operate in this particular venue. For
example, the agent must learn to distinguish brandy glasses from burgundy
glasses (Fig. 1(a)), but these subcategories of glasses are entirely absent
from the agent’s domain model in its factory setting. Learning to distinguish
among fine-grained visual subcategories is a nontrivial feat Wei et al.
(2021); most current approaches require careful engineering by ML
practitioners, making them unsuitable for lay users to readily inspect and
update the robot’s domain knowledge.

(a) 3D models of fine-grained types of glasses.

(b) Example interaction between a teacher and a learner discussing generic
knowledge about types of glasses.

Figure 1: Learning via embodied dialogue in a simulated tabletop domain.

There are also challenges regarding data efficiency, which using natural
language can potentially address Laird et al. (2017). A single generic
statement—e.g., “Brandy glasses have short stems”—expresses content that would
take many visual examples to infer. Such statements, given their dialogue
context, may also carry additional meaning that is linguistically implicit.
For instance, if the statement “Brandy glasses have short stems” is given as
an answer to the contrastive question “How are brandy glasses and burgundy
glasses different?”, then it implies that burgundy glasses don’t have short
stems, and also, defeasibly, that these two types of glasses are similar in
other conceivable respects Grice (1975); Asher (2013). Vision processing
models that exploit natural language data exist He and Peng (2017); Xu et al.
(2018); Chen et al. (2018); Song et al. (2020), but they generally treat
language as supplementary signals for augmenting training examples, rather
than leveraging a range of symbolic inferences licensed by purposeful
utterances in dialogue.

In this work, we develop an interactive symbol grounding framework, in which
the teacher presents to the learner evidence for grounding during embodied
dialogues like those illustrated in Fig. 1(b). The framework is based on a
highly modular neurosymbolic architecture, in which subsymbolic perceptual
inputs and symbolic conceptual knowledge obtained during dialogues gracefully
combine. We run proof-of-concept experiments to show that agents that exploit
semantic and pragmatic inferences from generic statements in discourse
outperform baselines that don’t exploit semantics and pragmatics, or don’t
exploit symbolic inference at all.

##  2 Related Work

In fine-grained image analysis (FGIA), a model learns to distinguish (patches
of) images of subcategories that belong to the same basic category. FGIA is
challenging because images exhibit small inter-class variance and large intra-
class variance, and labeling often requires specific domain expertise, hence
high annotation costs Wei et al. (2021).

A natural approach to FGIA is to utilize information of different modalities,
including unstructured text descriptions He and Peng (2017); Song et al.
(2020), structured knowledge bases Xu et al. (2018); Chen et al. (2018) and
human-edited attention maps Duan et al. (2012); Mitsuhara et al. (2021).
However, to our knowledge, no existing FGIA models exploit NL generic
statements provided in vivo during natural dialogues. Existing interactive
FGIA methods Branson et al. (2010); Wah et al. (2011, 2014); Cui et al. (2016)
query humans to refine predictions from off-the-shelf vision models at
inference time but do not update the grounding models. In contrast, our
framework supports continuous learning, updating the grounding model as and
when the teacher says something noteworthy.

Our use case, described in §1, can be subsumed under the framework of
Interactive Task Learning (ITL; Laird et al., 2017). Motivated by scenarios
where unforeseen changes may happen to the domain after deployment, the core
goal of ITL is to acquire novel concepts that the learner is unaware of but
are critical to task success. ITL systems gather evidence from natural
embodied interactions with a teacher that take place while the learner tries
to solve its task. Thus a key desideratum in ITL is that learning should be
online and incremental: the learner should change its beliefs and behaviours
whenever the teacher provides guidance.

Natural language is a common mode of teacher-learner interaction in ITL Kirk
et al. (2016); She and Chai (2017). Accordingly, several ITL works draw
inspiration from linguistic theories to make learning more effective and
efficient. While the formal semantics of quantifiers and negation Rubavicius
and Lascarides (2022) and of discourse coherence Appelgren and Lascarides
(2020) has been explored in ITL settings, none of the works in the ITL
literature have investigated the utility of exploiting the logical inferences
licenced by the semantics and pragmatics of contrastive questions and their
generic statement answers.

##  3 Agent architecture

Figure 2: Overview of the architecture in inference mode, in which the
component modules interact to generate an answer to a user question.

Fig. 2 illustrates our neurosymbolic architecture for situated ITL agents that
can engage in extended dialogues with a teacher. Its design enables both
subsymbolic-level learning of visual concepts from perceptual inputs (“This
looks like a X”) and symbolic-level learning and exploitation of relational
knowledge between concepts (“Xs generally have attribute Z”) during task
execution. Here we stress that our proposed approach is not in direct
competition with wide-coverage neural vision-language models, but actually
complements them. As an ITL framework, we offer a coping mechanism, to be
employed when an existing pre-trained model is deployed in a domain where
concepts are frequently introduced and changed, requiring the model to quickly
adapt with only a few exemplars of unforeseen concepts.

###  3.1 Vision processing module

Figure 3: Abridged illustration of the few-shot scene graph generation process
(Full version in Appendix A)

Given a visual scene perceived by the vision sensor, the agent first
summarizes the raw input into a graph-like data structure (scene graph
hereafter). A scene graph $SG$ encodes a set of salient objects in the scene
with their distinguishing features and their pairwise relationships, serving
as the agent’s internal, abstracted representation of the scene.

Our architecture makes exemplar-based few-shot predictions to generate scene
graphs, so as to quickly learn novel visual concepts after a few training
instances in an online, incremental fashion. Specifically, our vision
processing module employs a neural model extended from Deformable DETR Zhu et
al. (2021), trained to learn distinct low-dimensional metric spaces for each
concept type (object class/attribute/relation). The module makes binary
concept predictions based on similarity distances between embedded vectors. As
illustrated in Fig. 3, the role of the vision module is to process an RGB
image input $\mathcal{I}$ into a preliminary scene graph template
$\stackrel{{\scriptstyle\sim}}{{\smash{SG}\rule{0.0pt}{4.73611pt}}}$. The
template is further processed along with the agent’s store of concept
exemplars in its long-term memory (§3.3) to yield $SG$. For further details
about the inner working of the neural vision module and the translation
process from
$\stackrel{{\scriptstyle\sim}}{{\smash{SG}\rule{0.0pt}{4.73611pt}}}$ to $SG$,
refer to Appendix A.

###  3.2 Language processing module

The language processing module parses natural language utterances into formal
semantic representations, maintains dialogue records, and generates natural
language utterances as needed. For controlled experiments, we constrain our
attention to a class of simple sentences that discuss primarily two types of
information: 1) instance-level descriptions about conceptual identities of
scene objects (e.g., “This is a brandy glass”, “This has a wide bowl”); and 2)
relational knowledge about generic properties shared across instances of the
same concepts (e.g., “Brandy glasses have short stems”).

More formally, we represent the propositions expressed by NL sentences via a
simple antecedent-consequent pair (prop hereafter). props draw on a first-
order language $\mathcal{L}$ which includes constants referring to objects in
the visual scene and predicate symbols for their classes, attributes and
pairwise relations (i.e., visual concepts from §3.1). Indicative NL sentences
are generally represented with a prop $\psi=Ante\Rightarrow Cons$, where
$Ante$ and $Cons$ are each a $\mathcal{L}$-formula (for $\psi$, we refer to
these as $Ante(\psi)$ and $Cons(\psi)$). $Ante(\psi)$ is empty (and thus
omitted) if $\psi$ represents a non-conditional, factual statement. Further,
we notate a prop that stands for a generic characterization with a ‘generic
quantifier’ $\mathbb{G}$. For example, the sentences “$o$ is a brandy glass”
and “Brandy glasses have short stems” are translated into props respectively
as $brandyGlass(o)$ and $\mathbb{G}O.brandyGlass(O)\Rightarrow
haveShortStem(O)$.111In the interest of brevity and simplicity, we have
translated “have short stems” into an ‘agglomerate’ predicate $haveShortStem$
in this text. This is contrary to the actual implementation, where we
introduced the concepts $stem$, $short$ (unary predicates) and $have$ (binary
predicate) as elementary units. See Appendix B for a more accurate exposition.

We represent questions (ques hereafter) following notation similar to
Groenendijk and Stokhof (1982). The answer to a polar question, represented as
$?\psi$, is $\psi$ (if true) or $\neg\psi$ (if false). Answers to a wh-
question $?\lambda X.\psi(X)$ provide values $a$ of $X$ that make $\psi[X/a]$
true (i.e., all occurrences of $X$ in $\psi$ are substituted with $a$). For
the question “How are $p_{1}$ and $p_{2}$ different?”, we avoid the complexity
of higher-order formal languages and simply introduce a reserved formalism
$?\text{{conceptDiff}}(p_{1},p_{2})$, which our implemented dialogue
participants can handle by invoking a dedicated proecdure. The answer to
$?\text{{conceptDiff}}(p_{1},p_{2})$ is the set of attributes that all objects
of class $p_{1}$ have and $p_{2}$ lack, and vice versa.

The language processing module is implemented as a pipeline with two
components: an off-the-shelf large-coverage parser of the English Resource
Grammar Copestake and Flickinger (2000) followed by manual heuristics that map
the parser’s outputs to the above forms, as required by the symbolic reasoner
(see §3.4). The module also keeps track of the current dialogue history as a
sequence of utterances: each one logged as a prop or ques, its NL surface form
and its speaker.

###  3.3 Long-term memory module

Our agent stores new knowledge acquired over the course of its operation in
its long-term memory. We implement four types of knowledge storage: visual
exemplar base (XB), symbolic knowledge base (KB), episodic memory and lexicon.

##### Visual XB

For each visual concept $\gamma$, the visual XB stores $\chi_{\gamma}^{+}$ and
$\chi_{\gamma}^{-}$, a set of positive/negative exemplars worth remembering.
The exemplars serve as the basis of the agent’s few-shot prediction capability
as mentioned in §3.1. The visual XB is expanded each time the agent makes an
incorrect prediction. Specifically, when the learner incorrectly states “This
is $\tilde{\gamma}$”, the teacher provides a corrective response, saying “This
is not $\tilde{\gamma}$, this is $\gamma$”, thereby augmenting
$\chi_{\gamma}^{+}$ and $\chi_{\tilde{\gamma}}^{-}$. New sets
$\chi^{+/-}_{\gamma}$ are created whenever the teacher introduces a novel
concept $\gamma$ via a neologism.

##### Symbolic KB

The symbolic KB is a collection of generic props describing relations between
symbolic concepts, such as $\mathbb{G}O.brandyGlass(O)\Rightarrow
haveShortStem(O)$. Each KB entry is annotated with the source of the
knowledge: a generic rule may be explicitly uttered by the teacher or inferred
as an implicature, given the dialogue context. We’ll discuss how the learner
can extract unstated knowledge in §4.2.2 in further detail.

##### Episodic memory

The episodic memory stores the summary of each episode of situated
interactions between the agent and the teacher.

##### Lexicon

The lexicon stores a set of content words the teacher introduces into the
discourse, along with linguistic metadata like part-of-speech.

###  3.4 Symbolic reasoning

For symbolic reasoning, we employ a probabilistic variant of a logic
programming222In contrast to first-order logic, logic programming is based on
the notion of minimal models, where any true atom must be justified (founded)
by a clause in the logic program. technique known as answer set programming
(ASP; Lifschitz, 2008). The formalism of ASP represents a reasoning problem as
a normal logic program that consists of rules of the following form:

$a\leftarrow b_{1},\ldots,b_{m},\text{{not} }c_{1},\ldots,\text{{not} }c_{n}.$
(1)

where the rule head atom $a$ and the rule body atoms
$\\{b_{i}\\}_{i=1}^{m},\\{c_{j}\\}_{i=1}^{n}$ can be propositional or
(quantifier-free) first-order logic formulas. An intuitive reading of the
rule, by itself, is that $a$ is logically justified if and only if all of the
positive body atoms $\\{b_{i}\\}_{i=1}^{m}$ hold and none of the negative body
atoms $\\{c_{j}\\}_{i=1}^{n}$ are proven to hold. For instance, the ASP rule
$fly(X)\leftarrow bird(X),\text{{not} }abnormal(X)$ would roughly correspond
to the meaning of the generic NL statement “Birds (generally) fly”. A rule
whose head is empty ($\bot$) represents an integrity constraint that its rule
body should not hold in answer models.

In probabilistic ASP Lee and Wang (2016), each rule is associated with a
weight, such that possible worlds satisfying a set of rules with higher total
weights are assigned greater probability. Thus a rule may be violated at the
expense of its weight. Formally, a probabilistic ASP program $\Pi=\\{w:R\\}$
is a finite set of weighted rules where $R$ is a rule of the form (1) and $w$
is its associated weight value. The probability of a possible world $I$
according to $\Pi$ is computed via a log-linear model on the total weight of
rules in $\Pi_{I}$, where $\Pi_{I}$ is the maximal subset of $\Pi$ satisfiable
by $I$.

$\displaystyle W_{\Pi}(I)$
$\displaystyle=exp\Biggl{(}\sum_{w:R\in\Pi_{I}}w\Biggl{)}$ (2) $\displaystyle
P_{\Pi}(I)$ $\displaystyle=\frac{W_{\Pi}(I)}{\sum_{J\in\text{possible worlds
by }\Pi}W_{\Pi}(J)}$ (3)

For more rigorous technical definition, refer to Lee and Wang (2016).

Each symbol grounding problem is cast into an appropriate program as follows.
First, serialize the learner’s visual observations contained in the scene
graph $SG$ into $\Pi_{O}=\\{\text{logit}(s):\gamma(o_{1},...).\\}$, where each
$\gamma(o_{1},...)$ is a visual observation in $SG$ with confidence score
$s\in[0,1]$. Then we export the KB into a program $\Pi_{K}$, built as follows:

  * •

For each KB entry $\kappa$, add to $\Pi_{K}$:

$\text{logit}(U_{d}):\bot\leftarrow Ante(\kappa),\text{{not} }Cons(\kappa).$

which penalizes ‘deductive violation’ of $\kappa$.

  * •

For each set of KB entries $\\{\kappa_{i}\\}$ that share identical
$Cons(\kappa_{i})$, add to $\Pi_{K}$:

$\text{logit}(U_{a}):\bot\leftarrow Cons(\kappa_{i}),\\\
\bigwedge_{\kappa_{i}}\\{\text{{not} }Ante(\kappa_{i})\\}$

which penalizes failure to explain $Cons(\kappa_{i})$.

Here, $U_{d},U_{a}\in[0,1]$ are parameters encoding the extent to which the
agent relies on its symbolic knowledge; we use $U_{d}=U_{a}=0.95$ in our
experiments. For instance, the KB consisting of a single prop parsed from
“Brandy glasses have short stems” will be translated into $\Pi_{K}$ consisting
of the two rules (7) and (8) in Example 1 below. Finally, the program
$\Pi=\Pi_{O}\cup\Pi_{K}$ is solved using a belief propagation algorithm Shenoy
(1997) modified to accommodate the semantics of logic programs.

######  Example 1.

The program $\Pi$ below encodes a scenario where the agent sees an object
$o_{1}$ and initially estimates $o_{1}$ is equally likely to be a brandy or
burgundy glass. The agent also notices with high confidence it has a short
stem, and knows brandy glasses have short stems:

$\displaystyle\text{\emph{logit}}(0.61)$ $\displaystyle:\enspace
brandyGlass(o_{1}).$ (4) $\displaystyle\text{\emph{logit}}(0.62)$
$\displaystyle:\enspace burgundyGlass(o_{1}).$ (5)
$\displaystyle\text{\emph{logit}}(0.90)$ $\displaystyle:\enspace
haveShortStem(o_{1}).$ (6) $\displaystyle\text{\emph{logit}}(0.95)$
$\displaystyle:\enspace\bot\leftarrow brandyGlass(O),$
$\displaystyle\qquad\qquad\text{{not} haveShortStem(O)}.$ (7)
$\displaystyle\text{\emph{logit}}(0.95)$ $\displaystyle:\enspace\bot\leftarrow
haveShortStem(O),$ $\displaystyle\qquad\qquad\text{{not} brandyGlass(O)}.$ (8)

This results in $P_{\Pi}(brandyGlass(o_{1}))=0.91$, whereas
$P_{\Pi}(burgundyGlass(o_{1}))=0.62$. Thus the agent forms a stronger belief
that $o_{1}$ is a brandy glass than it is a burgundy glass.

See Appendix C for more examples.

##  4 Interactive Visual Concept Acquisition

###  4.1 Task description

In our symbol grounding task, each input is a tuple
$x_{i}=(\mathcal{I}_{i},b_{i})$, where $\mathcal{I}_{i}\in[0,1]^{3\times
H\times W}$ is an RGB image and $b_{i}$ is a specification of a bounding box
encasing an object in $\mathcal{I}_{i}$. That is, $x_{i}$ is essentially
reference to an object in an image. The task output $y_{i}$ is dependent on
two possible modes of querying the agent about the identity of the object
referenced by $x_{i}$. The first ‘polar’ mode amounts to testing the agent’s
knowledge of a concept in isolation (i.e., “Is this a X?”; so $y_{i}$ is yes
or no). The second ‘multiple-choice’ mode demands the agent selects a single
object class $y_{i}$ describing the object among possible candidates (i.e.,
“What is this?”, and $y_{i}$ is a class). The teacher’s response to $y_{i}$ is
dependent on the content of $y_{i}$ and the teacher’s dialogue strategy as
described in §4.2.1. The learner updates its symbol grounding model from the
teacher’s moves using the methods described in §3 and §4.2.2.

As mentioned earlier, the agent’s domain model may entirely lack the concept
of interest for labelling $x_{i}$. The agent acquires unforeseen concepts via
teacher utterances. For example, if “This ($x_{i}$) is a brandy glass”
introduces the agent to the unforeseen concept “brandy glass”, then
$\mathit{BrandyGlass}$ is added to $\mathcal{L}$ and the visual XB is
augmented with newly generated sets
$\chi_{\mathit{BrandyGlass}}^{+}=\\{x_{i}\\}$ and
$\chi_{\mathit{BrandyGlass}}^{-}=\varnothing$.

###  4.2 Flow of dialogues

We focus on a family of dialogues illustrated in Fig. 4. As depicted, each
interaction episode is initiated by a teacher query. Dialogues will proceed
according to the learner’s responses and the teacher’s strategy. In this
research, we want to investigate how different interaction and learning
strategies affect learning efficiency.

Figure 4: Flowchart covering the range of training dialogues modeled in this
study. $\square$ signals termination of an interaction episode.

####  4.2.1 Teacher’s strategy options

The teacher starts off each interaction episode by presenting an instance $o$
of some visual concept $p$, querying the learner with a probing ques
“$?\lambda P.P(o)$”.333Note that the expression $?\lambda P.P(o)$ does not
fully capture the intended meaning of “What is this?” in its own right, since
the discourse contexts set up additional semantic/pragmatic constraints on
what counts as acceptable answers. We have approximated those constraints via
our pre-defined dialogue strategies If the learner provides the correct answer
as the prop “$p(o)$”, the teacher responds “correct” and the episode
terminates without agent belief updates. Otherwise, if the learner provides an
incorrect answer, “$\tilde{p}(o)$” or “I am not sure”, the teacher needs to
provide some corrective information so that the learner can adjust its
beliefs. We implement and compare the following variations in the teacher’s
response, in increasing order of information content:

  * •

minHelp: Provides only boolean feedback to the learner’s answer, i.e.,
“$\neg\tilde{p}(o)$”.

  * •

medHelp: In addition to minHelp, provides the correct answer label, saying
“$p(o)$”.

  * •

maxHelp: In addition to medHelp, provides a set of generic props that
characterize $p$ or $\tilde{p}$. The feedback is provided after the learner’s
ques “$?\text{{conceptDiff}}(p,\tilde{p})$”, asked once on the first confusion
between $p$ and $\tilde{p}$.

The generic props provided by maxHelp teachers originate from the teacher’s
domain knowledge, which we assume here to be correct and exhaustive. The set
of props to be delivered is computed as the symmetric difference between the
set of properties of $p$ versus that of $\tilde{p}$ (see Appendix D for an
example). minHelp and medHelp serve as vision-only baselines since only
concept exemplars with binary labels are communicated as teaching signal.

####  4.2.2 Learner’s strategy options

Another dimension of variation we model is the learner’s strategy for
interpreting generic statements within dialogue contexts. Note that the
variation in this dimension is meaningful only when the teacher deploys the
maxHelp strategy, thereby allowing exploitation of generic statements.

In human dialogues, interlocutors infer, and speakers exploit, implicatures
that are validated by linguistically explicit moves, given the context of
utterance Grice (1975). As a core contribution of this study, we model how
generic statements given as an answer to a question about similarities and
differences give rise to certain implicatures Asher (2013) that can be
exploited for more data-efficient learning.

Situation Confusion brandy glass vs. burgundy glass Teacher input “Brandy
glasses have short stems.” Current KB $\mathbb{G}O.brandyGlass(O)\Rightarrow
haveWideBowl(O)$ Strategy New KB entries added semOnly
$\mathbb{G}O.brandyGlass(O)\Rightarrow haveShortStem(O)$ semNeg
$\mathbb{G}O.brandyGlass(O)\Rightarrow haveShortStem(O)$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{G}O.burgundyGlass(O)\Rightarrow\neg
haveShortStem(O)$ semNegScal $\mathbb{G}O.brandyGlass(O)\Rightarrow
haveShortStem(O)$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{G}O.burgundyGlass(O)\Rightarrow\neg
haveShortStem(O)$
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbb{G}O.burgundyGlass(O)\Rightarrow
haveWideBowl(O)$

Table 1: An example of how different learner strategies update their KBs from
the teacher’s generic statement feedback after the learner has confused a
burgundy glass for a brandy glass. The learner has already learned that
burgundy glasses have wide bowls. props in black is obtained from the
teacher’s NL utterance; props in red from ‘negative’ implicatures
($\psi^{neg}$ from $\psi$) as demanded by coherence; and props in blue from
scalar implicatures ($\kappa^{scl}$ from $\kappa$).

Suppose a question “How are X and Y different?” is answered with a generic
statement “Xs have attribute Z”. The following implicatures can arise from
this discourse context: 1) “Ys do not have attribute Z”, and 2) “X and Y are
otherwise similar”. The former follows from the assumption that the generic is
a coherent answer to a contrastive question Asher and Lascarides (2003). The
latter, which arguably is more defeasible Grice (1975), is what’s known as a
scalar implicature: if there were other important differences that the learner
should know, then Gricean maxims of conversation predict that the teacher
would have included them in the answer as well.

For a prop $\psi$, let $\psi^{p\leftrightarrow q}$ denote a prop which is
identical to $\psi$ except that occurrences of the predicate $p$ are all
substituted with the predicate $q$ and vice versa. We consider the following
strategies the learner can take when interpreting a set of generic props
$\\{\psi_{i}\\}$ provided during an episode:

  * •

semOnly: Simply add all $\psi_{i}$’s to KB.

  * •

semNeg: In addition to semOnly, infer a generic prop
$\psi_{i}^{neg}=Ante(\psi_{i}^{p\leftrightarrow\tilde{p}})\Rightarrow\neg
Cons(\psi_{i}^{p\leftrightarrow\tilde{p}})$ for each $\psi_{i}$ given as
answer to $?\text{{conceptDiff}}(p,\tilde{p})$.

  * •

semNegScal: In addition to semNeg, infer a generic prop
$\kappa^{scl}=Ante(\kappa^{p\leftrightarrow\tilde{p}})\Rightarrow
Cons(\kappa^{p\leftrightarrow\tilde{p}})$ for each KB entry $\kappa$ that has
either $p$ or $\tilde{p}$ mentioned, only if $\kappa^{scl}$ is not
inconsistent with any of $\psi_{i}$’s or $\psi_{i}^{neg}$’s.

For example, consider the example situation illustrated in Tab. 1. The semNeg
learner adds “Burgundy glasses do not have short stems” to its KB, and
semNegScal in addition adds “Brandy glasses have X” for every property X that,
according to its KB, burgundy glasses have (e.g., wide bowls).

While the semNeg inference stems from the demand that the teacher’s move is a
coherent answer Asher and Lascarides (2003), the scalar implicatures inferred
by semNegScal are defeasible presumptions Grice (1975). That is, semNegScal
risks misunderstanding the teacher’s intended meaning, inferring general rules
that are incorrect—yet cancellable (see Appendix E for an example failure
case). Subsequent pieces of refuting evidence may falsify the inferred
implicatures without rendering the conversation incoherent. Therefore, we
equip our agents with some risk management faculty that can assess and reject
contents of scalar implicatures. This is achieved by periodically testing KB
entries whose origin is solely from scalar implicatures, rejecting those whose
counterexamples can be found in the episodic memory.

##  5 Experiments

###  5.1 Evaluation Scheme

We run a suite of experiments that evaluate the data efficiency of the
learner’s and teacher’s strategies from §4.2. Results are averaged over
multiple sequences of interaction episodes for each of five combinations of
teacher’s and learner’s strategies: minHelp, medHelp, maxHelp+semOnly,
maxHelp+semNeg and maxHelp+semNegScal. Each episode-initial probing question
“$?\lambda P.P(o)$” is associated with a randomly selected instance $o$ of a
concept selected from a round-robin of the target concepts to be acquired. For
controlled random selections of concept instances and shuffling of the round-
robin, 40 seeds are shared across different configurations. Each sequence
continues until the learner makes $N_{t}$ mistakes in total.

As is common in ITL scenarios, training and inference are fully integrated.
Learning has to take place during use whenever the teacher imparts
information. In this work, we evaluate our learners by having them take ‘mid-
term exams’ on a separate test set after every $N_{m}$ mistakes made
($N_{m}\leq N_{t}$). The mid-term exams comprise binary prediction problems
“$?p(o)$” asked per every target concept $p$ for each test example $o$, and we
collect confidence scores between 0 and 1 as response. The primary evaluation
metric reported is mean average precision (mAP)444Mean of areas under
interpolated precision-recall curves.; we do not use an F1 score because we
are more interested in relative rankings between similar-looking concepts than
the learners’ absolute performances at some fixed confidence threshold. We
also report averaged confusion matrices collected for the sequence-final exams
(partially in Fig. 6, fully in the supplementary material).

(a) fineEasy difficulty (three glass types)

(b) fineHard difficulty (five glass types)

Figure 5: Averaged learning curves (with 95% confidence intervals): effective
training examples vs. mAP.

###  5.2 Setup

The learner agents start with relatively good, but still error-prone, priors
of what bowls and stems and their attributes (e.g., “short stem”) look like,
but completely lacks the vocabulary, concepts and related visual features for
the various glass types. The prior knowledge is injected into the learner
agents by exposing them to the full set of positive examples of stems and
bowls in our data set, and randomly sampled non-instances for negative
examples. The average binary classification accuracies on balanced test sets
were 98.11% for the part concepts and 86.12% for their attributes.

Our training and testing images are randomly generated from a simulation
framework CoppeliaSim Rohmer et al. (2013), using a toolkit for controlled
sampling of 3D environments Innes and Ramamoorthy (2021). Each image features
a scene of several objects from the restaurant domain laid on a tabletop
(e.g., the image in Fig. 2). Each type of glass in our tabletop domain can be
characterized by its parts having different attributes; see Appendix D for the
complete list. We implement simulated teachers in place of real human users
for the experiments, which perform rule-based pattern matching just sufficient
for participating as a teacher in our training dialogues. Our implementation
and datasets are publicly released in https://github.com/itl-ed/ns-arch.

The more distractor concepts we have, the more difficult the task becomes;
difficulty scales roughly quadratically with respect to the number of
concepts, since $C$ concepts enable ${C}\choose{2}$ different pairwise
confusions. Our experiments cover two levels of difficulty: fineEasy and
fineHard. For fineEasy, we set $(C,N_{t},N_{m})=(3,30,5)$, where target
concepts are {brandy glass, burgundy glass, champagne coupe}. For fineHard, we
set $(C,N_{t},N_{m})=(5,60,10)$, where target concepts as those for fineEasy
plus {bordeaux glass, martini glass}.

###  5.3 Results and Discussion

Task difficulty | fineEasy | fineHard
---|---|---
# training examples | 5 | 15 | 30 | 10 | 30 | 60
minHelp |  0.372 |  0.478 |  0.507 |  0.253 |  0.345 |  0.355
medHelp | 0.371 | 0.494 | 0.529 | 0.241 | 0.346 | 0.426
maxHelp_semOnly | 0.719 | 0.743 | 0.750 | 0.551 | 0.558 | 0.582
maxHelp_semNeg | 0.727 | 0.797 | 0.805 | 0.572 | 0.636 | 0.681
maxHelp_semNegScal | 0.744 | 0.803 | 0.811 | 0.574 | 0.649 | 0.681
Table 2: Task performances of agents by mAP scores after different numbers of
effective training examples.

Fig. 5 and Tab. 2 display the averaged learning curves for the five strategy
combinations in each task difficulty setting, along with 95% confidence
intervals. It is obvious that learners exploiting the semantics of generic
statements from maxHelp teachers are significantly faster in picking up new
concepts, compared to the vision-only baseline configurations with minHelp or
medHelp teachers. Among the maxHelp results, the learners which extract and
exploit additional, unstated information from the context (i.e., semNeg and
semNegScal) outperform the learner semOnly, which doesn’t exploit pragmatics.

Our error analysis reveals that the significant performance boosts enjoyed by
semNeg and semNegScal learners comes from the ability to infer non-properties
from property statements (i.e. $\psi^{neg}$ from $\psi$). The confusion
matrices reported in Fig. 6 allow us to study the mechanism. Specifically,
notice how the maxHelp_semOnly learner in Fig. 6(a) frequently misclassifies
brandy glasses as burgundy glasses, whereas it is considerably less likely to
make such mistakes in the opposite direction: 91% vs. 30%. We can see this is
because semOnly learners do not have access to the negative property of
burgundy glasses of not having short stems
($\mathbb{G}O.burgundyGlass(O)\Rightarrow\neg haveShortStem(O)$). Therefore,
while semOnly learners can confidently dismiss instances of burgundy glasses
as non-instances of brandy glasses, they are not able to dismiss instances of
brandy glasses as non-instances of burgundy glasses. We can observe in Fig.
6(b) that this is precisely remedied by semNeg and semNegScal learners, which
are able to reliably distinguish the two types in both directions: 24% vs.
19%.

The difference between semNeg and semNegScal learner is more subtle. Although
their performances generally tend to converge after sufficient training,
learners that exploit scalar implicatures seem to show higher data efficiency
at earlier stages, especially in the fineHard task. Nonetheless, the two
learning curves have largely overlapping confidence intervals; we cannot make
a strong scientific claim based on these results, and we will have to conduct
experiments at a larger scale to corroborate this difference.

(a) maxHelp_semOnly on fineEasy difficulty.

(b) maxHelp_semNeg on fineEasy difficulty.

Figure 6: Averaged confusion matrices taken from the sequence-final
evaluations for two configurations.

##  6 Conclusion and Future Directions

In this research, we have proposed an interactive symbol grounding framework
for ITL, along with a neurosymbolic architecture for the learner agent. We
empirically showed that learners who can comprehend and exploit valid
inferences from generic statements, including pragmatic content given their
context of use, can learn to ground novel visual concepts more data-
efficiently. Our findings confirm it pays to study human-AI natural language
interactions through the lens of discourse semantics, not only the truth
conditions of isolated sentences but also their coherent connections to their
context.

In future, we plan to relax some of many simplifying assumptions we made for
controlled experiments, possibly exploring other domains. For instance, the
ideal assumption that teachers are infallible and communication is noise-free
does not hold in most real-world scenarios Appelgren and Lascarides (2021).
Further, the set of linguistic constructions we have studied in this work is
very constrained (as intended), and a natural next step is to accommodate a
wider range of diverse and free-form NL constructions. It is also a strong
assumption that the learner agent already has relatively reliable beliefs
about object part and concept attributes. For example, if the learner does not
know what the “stem” of a wine glass means, the absence of the concept must be
resolved before communicating any generic characterizations involving stems.
Finally, our approach does not fully exploit the semantics of generic
statements, which express qualitative rules that admit exceptions Pelletier
and Asher (1997). The generic quantifier $\mathbb{G}$ did not play any
significant role in this work. One major strength of ASP is that it is well
suited for modeling non-monotonic inferences, and it would be interesting to
study how to model ITL scenarios that can robustly address exceptions to
generic rules.

## Acknowledgements

This work was supported by the UKRI Research Node on Trustworthy Autonomous
Systems Governance and Regulation (grant EP/V026607/1) and by Informatics
Global PhD Scholarships, funded by the School of Informatics at The University
of Edinburgh. We thank the anonymous reviewers for their feedback on an
earlier draft of this paper, and Mattias Appelgren, Rimvydas Rubavicius and
Gautier Dagan for continued feedback over the course of this research.

## References

  * Appelgren and Lascarides (2020) Mattias Appelgren and Alex Lascarides. 2020.  Interactive task learning via embodied corrective feedback.  _Autonomous Agents and Multi-Agent Systems_ , 34(2):1–45.
  * Appelgren and Lascarides (2021) Mattias Appelgren and Alex Lascarides. 2021.  Symbol grounding and task learning from imperfect corrections.  In _Proceedings of Second International Combined Workshop on Spatial Language Understanding and Grounded Communication for Robotics_ , pages 1–10.
  * Asher (2013) Nicholas Asher. 2013.  Implicatures and discourse structure.  _Lingua_ , 132:13–28.
  * Asher and Lascarides (2003) Nicholas Asher and Alex Lascarides. 2003.  _Logics of conversation_.  Cambridge University Press.
  * Branson et al. (2010) Steve Branson, Catherine Wah, Florian Schroff, Boris Babenko, Peter Welinder, Pietro Perona, and Serge Belongie. 2010.  Visual recognition with humans in the loop.  In _European Conference on Computer Vision_ , pages 438–451. Springer.
  * Chen et al. (2018) Tianshui Chen, Liang Lin, Riquan Chen, Yang Wu, and Xiaonan Luo. 2018.  Knowledge-embedded representation learning for fine-grained image recognition.  _arXiv preprint arXiv:1807.00505_.
  * Copestake and Flickinger (2000) Ann A Copestake and Dan Flickinger. 2000.  An open source grammar development environment and broad-coverage english grammar using hpsg.  In _LREC_ , pages 591–600. Athens.
  * Cui et al. (2016) Yin Cui, Feng Zhou, Yuanqing Lin, and Serge Belongie. 2016.  Fine-grained categorization and dataset bootstrapping using deep metric learning with humans in the loop.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1153–1162.
  * Duan et al. (2012) Kun Duan, Devi Parikh, David Crandall, and Kristen Grauman. 2012.  Discovering localized attributes for fine-grained recognition.  In _2012 IEEE conference on computer vision and pattern recognition_ , pages 3474–3481. IEEE.
  * Goldberger et al. (2004) Jacob Goldberger, Geoffrey E Hinton, Sam Roweis, and Russ R Salakhutdinov. 2004\.  Neighbourhood components analysis.  _Advances in neural information processing systems_ , 17.
  * Grice (1975) H. P. Grice. 1975.  Logic and conversation.  In P. Cole and J. L. Morgan, editors, _Syntax and Semantics Volume 3: Speech Acts_ , pages 41–58. Academic Press.
  * Groenendijk and Stokhof (1982) J. Groenendijk and M. Stokhof. 1982.  Semantic analysis of wh-complements.  _Linguistics and Philosophy_ , 5(2):175–233.
  * He and Peng (2017) Xiangteng He and Yuxin Peng. 2017.  Fine-grained image classification via combining vision and language.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5994–6002.
  * Innes and Ramamoorthy (2021) Craig Innes and Subramanian Ramamoorthy. 2021.  Probrobscene: A probabilistic specification language for 3d robotic manipulation environments.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 9446–9452. IEEE.
  * Kirk et al. (2016) James Kirk, Aaron Mininger, and John Laird. 2016.  Learning task goals interactively with visual demonstrations.  _Biologically Inspired Cognitive Architectures_ , 18:1–8.
  * Krishna et al. (2017) Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al. 2017\.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International journal of computer vision_ , 123(1):32–73.
  * Laird et al. (2017) J. Laird, K. Gluck, J. Anderson, K. Forbus, O. Jenkins, C. Lebiere, D. Salvucci, M. Scheutz, A. Thomaz, J. Trafton, Robert. Wray, S. Mohan, and J. Kirk. 2017.  Interactive task learning.  _IEEE Intelligent Systems_ , 32:6–21.
  * Lee and Wang (2016) Joohyung Lee and Yi Wang. 2016.  Weighted rules under the stable model semantics.  In _Fifteenth International Conference on the Principles of Knowledge Representation and Reasoning_.
  * Lifschitz (2008) Vladimir Lifschitz. 2008.  What is answer set programming?  AAAI’08, page 1594–1597. AAAI Press.
  * Mitsuhara et al. (2021) Masahiro Mitsuhara, Hiroshi Fukui, Yusuke Sakashita, Takanori Ogata, Tsubasa Hirakawa, Takayoshi Yamashita, and Hironobu Fujiyoshi. 2021.  Embedding human knowledge in deep neural network via attention map.  In _VISIGRAPP_.
  * Pelletier and Asher (1997) Francis Jeffry Pelletier and Nicholas Asher. 1997.  Generics and defaults.  In _Handbook of logic and language_ , pages 1125–1177. Elsevier.
  * Platt et al. (1999) John Platt et al. 1999.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  _Advances in large margin classifiers_ , 10(3):61–74.
  * Rohmer et al. (2013) Eric Rohmer, Surya PN Singh, and Marc Freese. 2013.  V-rep: A versatile and scalable robot simulation framework.  In _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 1321–1326. IEEE.
  * Rubavicius and Lascarides (2022) Rimvydas Rubavicius and Alex Lascarides. 2022.  Interactive symbol grounding with complex referential expressions.  In _2022 Annual Conference of the North American Chapter of the Association for Computational Linguistics_.
  * She and Chai (2017) Lanbo She and Joyce Chai. 2017.  Interactive learning of grounded verb semantics towards human-robot communication.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1634–1644.
  * Shenoy (1997) Prakash P Shenoy. 1997.  Binary join trees for computing marginals in the shenoy-shafer architecture.  _International Journal of approximate reasoning_ , 17(2-3):239–263.
  * Song et al. (2020) Kaitao Song, Xiu-Shen Wei, Xiangbo Shu, Ren-Jie Song, and Jianfeng Lu. 2020.  Bi-modal progressive mask attention for fine-grained recognition.  _IEEE Transactions on Image Processing_ , 29:7006–7018.
  * Wah et al. (2011) Catherine Wah, Steve Branson, Pietro Perona, and Serge Belongie. 2011.  Multiclass recognition and part localization with humans in the loop.  In _2011 International Conference on Computer Vision_ , pages 2524–2531. IEEE.
  * Wah et al. (2014) Catherine Wah, Grant Van Horn, Steve Branson, Subhransu Maji, Pietro Perona, and Serge Belongie. 2014.  Similarity comparisons for interactive fine-grained categorization.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 859–866.
  * Wei et al. (2021) Xiu-Shen Wei, Yi-Zhe Song, Oisin Mac Aodha, Jianxin Wu, Yuxin Peng, Jinhui Tang, Jian Yang, and Serge Belongie. 2021.  Fine-grained image analysis with deep learning: A survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_.
  * Xu et al. (2018) Huapeng Xu, Guilin Qi, Jingjing Li, Meng Wang, Kang Xu, and Huan Gao. 2018.  Fine-grained image classification by visual-semantic embedding.  In _IJCAI_ , pages 1043–1049.
  * Zangwill (2011) Nick Zangwill. 2011.  Negative properties.  _Noûs_ , 45(3):528–556.
  * Zhu et al. (2021) Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai. 2021.  Deformable {detr}: Deformable transformers for end-to-end object detection.  In _International Conference on Learning Representations_.

##  Appendix A Vision processing module: implementational details

Figure 7: A schematic of the structure of the vision processing module
component in our agent architecture, and the pipeline through which raw visual
inputs are processed into the final scene graph estimate.

Our implementation of the few-shot neural vision processing module is based on
the pretrained model of two-staged Deformable DETR Zhu et al. (2021). We train
new lightweight multilayer perceptron (MLP) blocks for embedding image regions
into low-dimensional feature spaces. The MLP blocks replace the existing
pretrained prediction heads that have fixed number of output categories,
enabling metric-based few-shot predictions of incrementally learned visual
concepts.

Let $C$, $A$ and $R$ denote open sets of visual concepts of different types:
object classes555Intuitively corresponding to concepts denoted by
nouns—e.g.,‘brandy glass’, ‘stem’., attributes666intuitively corresponding to
concepts denoted by adjectives—e.g., ‘wide’, ‘short’. and pairwise
relations777intuitively corresponding to concepts denoted by transitive verbs
and adpositions—e.g., ‘have’, ‘of’. In principle, we need one metric space for
each concept type for their separate handling, hence three MLP blocks to
train. But for this work, $|R|=1$, where the only relation concept we need to
capture is ‘have’ (whole-part relationship). We can make proxy predictions for
the concept by the ratio of the area of bounding box intersection to the area
of the candidate object part’s bounding box. Therefore, in the interest of
simplicity, we prepare only two embedder blocks for $C$ and $A$ respectively;
in future extensions where we need to deal with a truly open $R$, we will have
to implement a relation-centric embedder block for $R$ as well.

Fig. 7 depicts how our vision module summarizes the raw RGB image input
$\mathcal{I}\in[0,1]^{3\times H\times W}$ into a preliminary scene graph
$\stackrel{{\scriptstyle\sim}}{{\smash{SG}\rule{0.0pt}{4.73611pt}}}$, and then
makes few-shot predictions to finally yield a scene graph $SG$. $\mathcal{I}$
is first passed through the feature extractor backbone to produce
$\\{f_{l}\\}_{l=1}^{L}$, a set of feature maps $f^{l}\in\mathbb{R}^{C\times
H^{l}\times W^{l}}$ at $L$ different scales. $\\{f_{l}\\}_{l=1}^{L}$ are
flattened into a single sequence of input tokens (thus in
$\mathbb{R}^{C\times\sum_{l}H^{l}\cdot W^{l}}$), combined with appropriate
positional encodings and fed into the encoder. We obtain from the encoder an
objectness logit score $s_{i}$ and a proposal bounding box coordinate
$\mathbf{b}_{i}\in[0,1]^{4}$ for the input tokens, out of which the top $k$
proposals with the highest $s_{i}$ scores are selected. The selected proposals
are fed into the decoder along with corresponding feature vectors to generate
$\mathbf{f}_{i}^{c},\mathbf{f}_{i}^{a}\in\mathbb{R}^{D}$, the class/attribute-
centric embeddings of each input token, in addition to the (refined) bounding
box coordinates $\mathbf{b}_{i}$. The decoder outputs are collated into the
preliminary scene graph template
$\stackrel{{\scriptstyle\sim}}{{\smash{SG}\rule{0.0pt}{4.73611pt}}}=(\tilde{N},\tilde{E})$.
$\tilde{N}$ is the node set containing
$\mathbf{b}_{i},\mathbf{f}_{i}^{c},\mathbf{f}_{i}^{a}$ for each detected
object. $\tilde{E}$ is the edge set that would contain pairwise relation-
centric embeddings $\mathbf{f}_{i,j}^{r}$ for each pair of detected objects.
However, $\tilde{E}$ is essentially empty in our current implementation since
as mentioned above, we fall back to proxy prediction by area ratio for the
only relation concept of interest ‘have’.

For each visual concept $\gamma\in C,A(,R)$, the agent’s visual XB stores
$\chi_{\gamma}^{+/-}$, a set of positive/negative exemplars, which together
naturally induce a binary classifier $BinClf_{\gamma}$. We are free to choose
any binary classification algorithm as long as it can return probability
scores for concept membership from $\chi_{\gamma}^{+}$ and
$\chi_{\gamma}^{-}$. We use Platt-scaled SVM with RBF kernel Platt et al.
(1999) in our implementation. Then, $SG=(N,E)$ is generated from
$\stackrel{{\scriptstyle\sim}}{{\smash{SG}\rule{0.0pt}{4.73611pt}}}$ and a set
of $BinClf_{\gamma}$’s, where $N$ and $E$ are each the scene graph node set
and the scene graph edge set. For each scene object, $N$ contains
$\mathbf{c}_{i}\in[0,1]^{|C|}$ and $\mathbf{a}_{i}\in[0,1]^{|A|}$, each a
vector designating the probabilistic beliefs of whether the object classifies
as an instance of concepts in $C$ and $A$, as well as the box specification
$\mathbf{b}_{i}$. $E$ contains information about binary relationships between
ordered pairs of objects, namely $\mathbf{r}_{i,j}\in[0,1]^{|R|}$, the
probabilistic beliefs of whether the pair $(i,j)$ is an instance of concepts
in $R$. As a reminder, in our setting, $N$ is computed from $\tilde{N}$ and
$BinClf_{\gamma}$ for each $\gamma\in C,A$, whereas $E$ is computed from
bounding box area ratios.

Our new embedder blocks are trained on 50% of the Visual Genome dataset
Krishna et al. (2017) with NCA loss objective Goldberger et al. (2004) for
metric learning, for 80,000 steps using SGD optimizer with the batch size of
64, the learning rate of $3\times 10^{-4}$ and the momentum factor of 0.1. The
prediction heads are then fine-tuned on our tabletop domain
dataset888Excluding the fine-grained types of drinking glasses. for 2,000
steps using Adam optimizer, with the batch size of 16, the initial learning
rate of $2\times 10^{-4}$ and PyTorch default
values999https://pytorch.org/docs/stable/generated/torch.optim.Adam.html for
the hyperparameters $\beta_{1},\beta_{2},\epsilon$.

##  Appendix B FOL representation of concept properties

In the main paper, we have represented the NL predication “have short stems”
with an agglomerate predicate haveShortStem for the sake of brevity, so that
“Brandy glasses have short stems” would be translated into the prop
$\mathbb{G}O.brandyGlass(O)\Rightarrow haveShortStem(O)$. However, this is an
oversimplification of what is actually happening under the hood in our
implementation. The predication “have short stems” ought to be broken down
into its constituent meanings delivered by the individual tokens “have”,
“short” and “stem” respectively, for primarily two reasons: 1) they are the
elementary units of concepts handled by the vision module and included in the
output scene graphs, and 2) the object parts should be explicitly acknowledged
as entities separate from the objects they belong to, and the generic props
should model relations between objects and their parts (plus their
attributes).

In light of this, we choose to read NL sentences of the form “{object}s have
{attribute} {part}s” as follows: “If $O$ is an object, there exists an entity
$P$ such that $O$ has $P$ as its part, and $P$ is a part that is attribute”.
Then, for example, the sentence “Brandy glasses have short stems” would be
represetned by the following prop:

$\displaystyle\mathbb{G}O.brandyGlass(O)\Rightarrow$
$\displaystyle\qquad(\exists P.have(O,P),short(P),stem(P))$

or alternatively,

$\displaystyle\mathbb{G}O.brandyGlass(O)\Rightarrow$ $\displaystyle\qquad
have(O,f(O)),short(f(O)),stem(f(O))$

where $f$ is a skolem function that maps from the instance of brandy glass to
its (only) short stem. We opt for the latter option because it is more
compliant with the formalism commonly used by logic programming methods, in
which existential quantifiers are not admitted and variables are all
implicitly universally quantified.

##  Appendix C More examples of grounding problems as probabilistic ASP
programs

Example 2 below illustrates how lack of high-confidence observation of a short
stem of a glass $o_{1}$ results in a weaker belief that $o_{1}$ is a brandy
glass.

######  Example 2.

The agent sees an object $o_{1}$ and initially estimates it’s equally likely
to be a brandy or burgundy glass. The agent also notices with high confidence
it does NOT have a short stem, and knows brandy glasses have short stems:

$\displaystyle\text{\emph{logit}}(0.61)$ $\displaystyle:\enspace
brandyGlass(o_{1}).$ (9) $\displaystyle\text{\emph{logit}}(0.62)$
$\displaystyle:\enspace burgundyGlass(o_{1}).$ (10)
$\displaystyle\text{\emph{logit}}(0.10)$ $\displaystyle:\enspace
haveShortStem(o_{1}).$ (11) $\displaystyle\text{\emph{logit}}(0.95)$
$\displaystyle:\enspace\bot\leftarrow brandyGlass(O),$
$\displaystyle\qquad\qquad\text{{not} haveShortStem(O)}.$ (12)
$\displaystyle\text{\emph{logit}}(0.95)$ $\displaystyle:\enspace\bot\leftarrow
haveShortStem(O),$ $\displaystyle\qquad\qquad\text{{not} brandyGlass(O)}.$
(13)

This results in $P_{\Pi}(brandyGlass(o_{1}))=0.20$, whereas
$P_{\Pi}(burgundyGlass(o_{1}))=0.62$.

Example 3 shows how knowledge of negative properties of an object class can
affect symbolic reasoning. The example supposes the agent’s KB only consists
of the knowledge “Burgundy glasses do not have short stems”, namely the prop
$\mathbb{G}O.burgundyGlass(O)\Rightarrow\neg haveShortStem(O)$. Note how we
translate a generic prop whose $Cons$ is a negation of some
$\mathcal{L}$-formula into probabilistic ASP rules. Only rules penalizing
deductive violations are generated, in which the negation ($\neg$) that wraps
around $Cons$ ‘cancels out’ the default negation not. We do not generate rules
for penalizing failures to explain $Cons$ from negative props, as abductive
inferences of object classes from lack of properties would give rise to far-
fetched conclusions: e.g., inferring something might be a banana because it
does not have wheels.

######  Example 3.

The agent sees an object $o_{1}$ and initially estimates it’s equally likely
to be a brandy or burgundy glass. The agent also notices with high confidence
it has a short stem, and knows burgundy glasses do NOT have short stems:

$\displaystyle\text{\emph{logit}}(0.61)$ $\displaystyle:\enspace
brandyGlass(o_{1}).$ (14) $\displaystyle\text{\emph{logit}}(0.62)$
$\displaystyle:\enspace burgundyGlass(o_{1}).$ (15)
$\displaystyle\text{\emph{logit}}(0.90)$ $\displaystyle:\enspace
haveShortStem(o_{1}).$ (16) $\displaystyle\text{\emph{logit}}(0.95)$
$\displaystyle:\enspace\bot\leftarrow burgundyGlass(O),$
$\displaystyle\qquad\qquad\enspace haveShortStem(O).$ (17)

This results in $P_{\Pi}(brandyGlass(o_{1}))=0.61$, whereas
$P_{\Pi}(burgundyGlass(o_{1}))=0.19$.

Note that knowledge about brandy glasses do not affect the likelihood of
$o_{1}$ being a burgundy glass, and vice versa: i.e., for an object, the
events of being a brandy glass vs. a burgundy glass are independent. This is
because the KBs in the examples do not introduce any type of dependency
between the two glass types. For instance, if we inject mutual exclusivity
relation between the two types in the KB, both probability values
$P_{\Pi}(brandyGlass(o_{1}))$ and $P_{\Pi}(burgundyGlass(o_{1}))$ would be
affected by knowledge about either.

##  Appendix D Task domain: Fine-grained types of drinking glasses to
distinguish

Type Properties Sample image bordeaux glass Bowl: elliptical, tapered. brandy
glass Bowl: wide, tapered, round.
Stem: short. burgundy glass Bowl: wide, tapered, round. champagne coupe Bowl:
broad, round. martini glass Bowl: broad, conic.

Table 3: Fine-grained types of drinking glasses modeled in our tabletop
domain. (Note only brandy glasses have characteristic stems, whereas bowls of
all glass types can be characterized by some set of attributes.)

Confusion champagne coupe - burgundy glass burgundy glass - bordeaux glass KB
state $\mathbb{G}O.champagneCoupe(O)\Rightarrow haveBroadBowl(O)$
$\mathbb{G}O.burgundyGlass(O)\Rightarrow$
$\mathbb{G}O.burgundyGlass(O)\Rightarrow$ $haveWideBowl(O),haveRoundBowl(O)$
$haveWideBowl(O),haveTaperedBowl(O)$ $\mathbb{G}O.bordeauxGlass(O)\Rightarrow
haveEllipticalBowl(O)$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{G}O.burgundyGlass(O)\Rightarrow\neg
haveBroadBowl(O)$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{G}O.bordeauxGlass(O)\Rightarrow$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{G}O.champagneCoupe(O)\Rightarrow$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\neg(haveWideBowl(O),haveRoundBowl(O))$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\neg(haveWideBowl(O),haveTaperedBowl(O))$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{G}O.burgundyGlass(O)\Rightarrow\neg
haveEllipticalBowl(O)$
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\underline{\mathbb{G}O.bordeauxGlass(O)\Rightarrow}$
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\underline{haveWideBowl(O),haveTaperedBowl(O)}$
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbb{G}O.bordeauxGlass(O)\Rightarrow\neg
haveBroadBowl(O)$

Table 4: An example illustration of how semNegScal learners can infer
incorrect and unintended knowledge. The underlined prop denotes a generic rule
which is neither correct nor intended by the teacher.

Tab. 3 lists the set of fine-grained types of drinking glasses that are
modeled in our simulated tabletop domain, along with their properties and
sample images. 3D meshes of the glasses are obtained from a website that lists
stock models made by third-party
providers,101010https://www.turbosquid.com/3d-models/wine-glasses-3d-1385831
then imported into the simulation environment.

As illustrated, properties of each fine-grained type comprise its part
attributes. For instance, the full set of properties of a brandy glass could
be expressed as a set {(wide, bowl), (tapered, bowl), (round, bowl), (short,
stem)}. When asked, our simulated teacher computes the answer to ?conceptDiff
ques as pairwise symmetric differences between property sets: e.g., for
?conceptDiff(brandyGlass,burgundyGlass), we obtain {(short, stem)} for brandy
glasses and $\varnothing$ for burgundy glasses.

These properties of glasses did not ship with the 3D models; instead, we hand-
coded them based on information available on the internet. We have put effort
to prepare an annotation scheme that is faithful to properties of the glasses
in the reality, yet the domain knowledge may still have inconsistency against
the ‘ground-truth’—any error in that regard remains our own.

##  Appendix E Rule acquisition by inference of implicatures and failure case
analysis

In this work, we assume that all generic NL statements given by the teacher
are characterizations of object classes by their positive properties (those
described in Appendix D), and statements of negative properties are never
explicitly provided. This reflects the fact that we usually characterize
things by their positive properties rather than by their negative properties
because the former generally have more determining power Zangwill (2011).
Therefore, in our experiments, negative properties can be obtained only by
virtue of inference of implicatures. That is, for example, only semNeg or
semNegScal learners have access to the negative prop
$\mathbb{G}O.burgundyGlass(O)\Rightarrow\neg haveShortStem(O)$.

Nevertheless, semNegScal learners risk acquisition of incorrect and unintended
knowledge when they make inferences of scalar implicatures. To see this, study
the example illustrated in Tab. 4, where two successive confusions take place
in the order of brandy glass vs. burgundy glass and then burgundy glass vs.
champagne coupe. In the example, the underlined prop successfully infiltrates
into the learner’s KB without being suppressed by explicitly stated props or
their negative implicature counterparts. This is why inference of the scalar
implicatures should be cancellable, so that they can be retracted in the face
of contradictory evidence. In our implementation, this is achieved by
periodically inspecting the KB entries against the episodic memory, removing
any rules whose counterexamples are found.


# Forking and invariant measures in NIP theories

Anand Pillay,111Partially supported by NSF grants DMS-1760212 and DMS-2054271.
Atticus Stonestrom
Department of Mathematics, University of Notre Dame

Abstract: We give an example of an NIP theory $T$ in which there is a formula
that does not fork over $\varnothing$ but has measure $0$ under any global
$\varnothing$-invariant Keisler measure, and we show that this cannot occur if
$T$ is also first-order amenable.

Notation: Throughout $T$ will denote a complete theory in a first-order
language $L$, with a monster model $\mathfrak{C}$. We will always be working
over $\varnothing$. So: (i) if we say a formula or type forks (respectively
divides), we mean that it forks (respectively divides) over $\varnothing$,
(ii) by ‘definable’ (respectively ‘type-definable’) we mean definable
(respectively type-definable) without parameters, and (iii) if we say two
tuples $a,b$ are conjugate, we mean they have the same type over
$\varnothing$, which we denote by $a\equiv b$.

##  1 Introduction

This paper continues investigation of one of the themes of [2], namely the
relationship between two natural ideals of $L(\mathfrak{C})$-formulas in a
theory $T$: the ideal of formulas which fork, and the ideal of formulas which
are given measure $0$ under any automorphism-invariant Keisler measure on
$\mathfrak{C}$. The former is always contained in the latter (see for example
Fact 1.2 in [2]), and the other inclusion holds if $T$ is stable (see for
example Corollary 1.4 in [2]). But the other inclusion need not hold in
general, and [2] gives such an example where $T$ is simple. In this paper we
will discuss the case when $T$ is NIP; for much more general context, we refer
to the introduction of [2].

From here on, let $\phi(x,b)$ be an $L(\mathfrak{C})$-formula that does not
fork, and let $(\ast)$ denote the statement that $\mu(\phi(x,b))>0$ for some
global automorphism-invariant Keisler measure $\mu$. It is an early fact from
[1], that, if $T$ is NIP, then $\phi(x,b)$ is contained in a global type which
is Lascar-invariant over $\varnothing$; in particular, if
$\operatorname{dcl}(\varnothing)$ is a model, then $\phi(x,b)$ is contained in
some automorphism-invariant type, and so $(\ast)$ holds. In [8], Hrushovski
and the first author showed further that, if $T$ is NIP, then $\phi(x,b)$ is
contained in a global type which is KP-invariant over $\varnothing$; by
lifting the Haar measure on the KP-Galois group of $T$, they used this to show
that, if $T$ is NIP, then $(\ast)$ holds provided
$b\in\operatorname{dcl}(\varnothing)$ (see Section 2.1 below for more
details). Nevertheless, we show here that $(\ast)$ need not hold in general
when $T$ is NIP; this is the content of Section 4.

A notion related to the above theme is that of first-order amenability,
introduced by Hrushovski, Krupiński, and the first author in [7] and [6]. $T$
is said to be ‘amenable’ if every type over $\varnothing$ extends to a global
automorphism-invariant Keisler measure. Using the construction from [8]
mentioned above, [7] shows that, if $T$ is NIP, then $T$ is amenable if and
only if $\varnothing$ is an extension base – ie no formula without parameters
forks. In Section 3 we observe that $(\ast)$ holds when $T$ is NIP and
amenable; in fact, we give two proofs, both adapting arguments of Chernikov
and Simon. In contrast, as shown in [2], $(\ast)$ need not hold even if $T$ is
simple and amenable, as the example found there is amenable.

##  2 Preliminaries

###  2.1 KP-Strong Types

Recall that, for a small tuple of variables $x$, two $x$-tuples
$b,c\in\mathfrak{C}^{x}$ are said to be Kim-Pillay equivalent (over
$\varnothing$), written $E_{\mathrm{KP}}(b,c)$, if they lie in the same
equivalence class of every bounded type-definable equivalence relation on
$\mathfrak{C}^{x}$. For small tuples of variables $x,y$ of the same arities
and respective sorts, the relation $E_{\mathrm{KP}}(x,y)$ is bounded and type-
definable, and the KP-strong type of $b$ is the equivalence class of $b$ under
$E_{\mathrm{KP}}$. The KP-Galois group, denoted
$\mathrm{Gal}_{\mathrm{KP}}(T)$, is the quotient of
$\operatorname{Aut}(\mathfrak{C})$ by the (normal) subgroup of automorphisms
$\sigma$ such that $E_{\mathrm{KP}}(b,\sigma(b))$ holds for every small tuple
$b$. Given an automorphism $\sigma$ of $\mathfrak{C}$, we will denote by
$\bar{\sigma}$ its image in $\mathrm{Gal}_{\mathrm{KP}}(T)$.

The type of a tuple over any small model determines its KP-strong type. Thus,
for any small $M,N\prec\mathfrak{C}$, if we let $\bar{n}$ be an enumeration of
$N$ and let $S_{\bar{n}}(M)$ denote the space of complete types over $M$
extending $\operatorname{tp}(\bar{n}/\varnothing)$, then the map taking
$\operatorname{tp}(\sigma(\bar{n})/M)$ to $\bar{\sigma}$ gives a well-defined
surjection from $S_{\bar{n}}(M)$ to $\mathrm{Gal}_{\mathrm{KP}}(T)$. The
quotient topology on $\mathrm{Gal}_{\mathrm{KP}}(T)$ induced by this map is
independent of the choice of $M,N$, and makes $\mathrm{Gal}_{\mathrm{KP}}(T)$
into a compact Hausdorff topological group; see for example [11].

In particular, $\mathrm{Gal}_{\mathrm{KP}}(T)$ is equipped with a bi-invariant
Haar measure of weight $1$, ie a regular Borel measure $\eta$ such that
$\eta(\mathrm{Gal}_{\mathrm{KP}}(T))=1$ and such that
$\eta(\bar{\sigma}S\bar{\tau})=\eta(S)$ for any Borel subset
$S\subseteq\mathrm{Gal}_{\mathrm{KP}}(T)$ and any
$\bar{\sigma},\bar{\tau}\in\mathrm{Gal}_{\mathrm{KP}}(T)$.

###  2.2 Forking in NIP Theories

In this section assume that $T$ is NIP. Recall that a global type $p(x)\in
S_{x}(\mathfrak{C})$ is ‘KP-invariant’ if, for any $L(\mathfrak{C})$-formula
$\phi(x,b)$ and any $b^{\prime}$ with the same KP-strong type as $b$, we have
$p(x)\vdash\phi(x,b)\leftrightarrow\phi(x,b^{\prime})$. From [8] we have the
following:

######  Fact 2.1.

A global type does not fork if and only if it is KP-invariant.

In particular, given a global non-forking type $p(x)\in S_{x}(\mathfrak{C})$
and an $L(\mathfrak{C})$-formula $\phi(x,b)$, the subset
$S_{p,\phi(x,b)}\subseteq\mathrm{Gal}_{\mathrm{KP}}(T)$ given by
$\\{\bar{\sigma}:\sigma p(x)\vdash\phi(x,b)\\}$ is well-defined. Again from
[8], we have:

######  Fact 2.2.

If $p(x)\in S_{x}(\mathfrak{C})$ does not fork, then $S_{p,\phi(x,b)}$ is
Borel for every $L(\mathfrak{C})$-formula $\phi(x,b)$. In particular, taking
$\mu_{p}(\phi(x,b)):=\eta(S_{p,\phi(x,b)})$ for each $L(\mathfrak{C})$-formula
$\phi(x,b)$ gives a well-defined Keisler measure on $\mathfrak{C}^{x}$, which
is automorphism-invariant by the left-invariance of $\eta$.

Now, recall that a small subset $B\subset\mathfrak{C}$ is called an ‘extension
base’ if no type over $B$ forks over $B$. We have the following from [3]:

######  Fact 2.3.

Suppose $B$ is an extension base. Then an $L(\mathfrak{C})$-formula forks over
$B$ if and only if it divides over $B$. Moreover, given an $L$-formula
$\psi(x,y)$, the set of all $c\in\mathfrak{C}^{y}$ such that $\psi(x,c)$ forks
over $B$ is type-definable over $B$.

We will also need the following, which is Proposition 25 of [5]; it is stated
and proved there for the case when $\operatorname{dcl}(\varnothing)$ is a
model, but precisely the same proof works over any extension base, so we
repeat the proof here for clarity without the assumption that
$\operatorname{dcl}(\varnothing)$ is a model. For the statement of the
$(p,q)$-property and the $(p,q)$-theorem see Section 0.4 in [5].

######  Fact 2.4.

Suppose $\varnothing$ is an extension base, that $\phi(x,y)$ is an
$L$-formula, and that $\pi(y)$ is a partial type over $\varnothing$ such that
$\phi(x,b)$ does not fork for all $b\models\pi$. Then there are finitely many
non-forking global types $p_{1},\dots,p_{n}\in S_{x}(\mathfrak{C})$ such that,
for every $b\models\pi$, there is some $p_{i}$ concentrated on $\phi(x,b)$.

###### Proof.

Let $X$ denote the closed subset of $S_{x}(\mathfrak{C})$ consisting of those
types which do not fork. Give $b\models\pi$, let $F_{b}=\\{p\in
X:p\vdash\phi(x,b)\\}$, and let $\mathcal{F}$ be the family
$\\{F_{p}:b\models\pi\\}$. Since $T$ is NIP, $\mathcal{F}$ has finite VC-
dimension, and hence finite VC-codimension – say strictly smaller than
$q\in\omega$. We claim that $\mathcal{F}$ has the $(p,q)$-property for some
$p\in\omega$. Otherwise, for each $p\in\omega$, there is a sequence
$b_{1},\dots,b_{p}$ of realizations of $\pi$ such that, for any
$s\subseteq[p]$ of size $q$, we have $\bigcap_{i\in s}F_{b_{i}}=\varnothing$,
so that the formula $\bigwedge_{i\in s}\phi(x,b_{i})$ forks.

Now, since $\varnothing$ is an extension base, the set of
$(c_{1},\dots,c_{q})$ such that $\bigwedge_{i\in[q]}\phi(x,c_{i})$ forks is
type-definable. Thus, by compactness, we may find an infinite sequence
$(b_{i})_{i\in\omega}$ of realizations of $\pi(y)$ such that $\bigwedge_{i\in
s}\phi(x,b_{i})$ forks for every $s\subset\omega$ of size $q$, and then again
by compactness and by Ramsey’s theorem we may assume $(b_{i})_{i\in\omega}$ is
indiscernible. But this is a contradiction; letting $q(x)$ be any global non-
forking type concentrated on $\phi(x,b_{0})$, then by Lascar-invariance $q$ is
concentrated on $\phi(x,b_{i})$ for each $i\in\omega$, so that
$\bigwedge_{i\in[q]}\phi(x,b_{i})$ does not fork.

So indeed $\mathcal{F}$ has the $(p,q)$-property for some $p\in\omega$. By the
$(p,q)$-theorem, there is thus some $n\in\omega$ such that, for every finite
subset $\mathcal{F}_{0}\subseteq\mathcal{F}$, there is an $n$-element subset
of $X$ which meets every element of $\mathcal{F}_{0}$. Hence, by compactness,
the partial type in variables $x_{1},\dots,x_{n}$ containing the following
formulas is consistent: (i) $\bigvee_{i\in[n]}\phi(x_{i},b)$ for every
$b\models\pi$, and (ii) $\neg\psi(x_{i},c)$ for every $i\in[n]$ and every
$\psi(x_{i},c)\in L(\mathfrak{C})$ which forks. Taking any global completion
and letting $p_{i}$ be its restriction to the variable $x_{i}$, the desired
result follows. ∎

###  2.3 Dynamics

Let $G$ be a (discrete) group. Recall that a ‘$G$-flow’ is a non-empty compact
Hausdorff space $X$ together with a left action of $G$ on $X$ by
homeomorphisms. A ‘subflow’ of $X$ is a closed $G$-invariant subset of $X$, ie
a non-empty closed subset $Y\subseteq X$ with $gY=Y$ for all $g\in G$. The
flow $X$ is ‘point-transitive’ if, for some $p\in X$, the orbit $Gp$ is a
dense subset of $X$. An open subset $U\subseteq X$ is called ‘generic’ if
$X=g_{1}U\cup\dots\cup g_{n}U$ for some $g_{1},\dots,g_{n}\in G$, and is
called ‘weakly generic’ if there is a non-generic open set $V$ such that
$U\cup V$ is generic. A point $p\in X$ is called (weakly) generic if every one
of its open neighborhoods is (weakly) generic. Finally, a point $p\in X$ is
said to be ‘almost periodic’ if it lies in a minimal subflow of $X$. The
following is proved in [9]:

######  Fact 2.5.

Let $X$ be a point-transitive $G$-flow. Then every almost periodic point of
$X$ is weakly generic.

##  3 Amenable Case

Recall from [7] that a theory $T$ is said to be ‘first-order amenable’, or
just ‘amenable’, if every type over $\varnothing$ extends to a global
automorphism-invariant Keisler measure. In any theory $T$, amenability implies
that $\varnothing$ is an extension base, and, using Fact 2.2, it is observed
in [7] that the converse holds when $T$ is NIP. We now observe that, if $T$ is
NIP and first-order amenable, then having measure $0$ under any automorphism-
invariant Keisler measure implies forking. This is the ‘automorphism group
analogue’ of Corollary 3.34 in [4] and is proved in an analogous way, with the
proof a quick corollary of Fact 2.2 and Fact 2.4.

######  Theorem 3.1.

Suppose that $T$ is NIP, that $\varnothing$ is an extension base, and that
$\phi(x,b)$ is a non-forking $L(\mathfrak{C})$-formula. Then there is a global
automorphism-invariant Keisler measure giving $\phi(x,b)$ positive measure.

###### Proof.

By Fact 2.4 applied to the type $\pi(x):=\operatorname{tp}(b/\varnothing)$,
there are non-forking types $p_{1},\dots,p_{n}\in S_{x}(\mathfrak{C})$ such
that, for every $b^{\prime}\equiv b$, the formula $\phi(x,b^{\prime})$ is
contained in some $p_{i}$. In particular, the sets
$S_{p_{1},\phi(x,b)},\dots,S_{p_{n},\phi(x,b)}$ defined in Section 2.2 cover
$\mathrm{Gal}_{\mathrm{KP}}(T)$. Hence, for some $i\in[n]$,
$S_{p_{i},\phi(x,b)}$ has Haar measure at least $1/n$, and then the measure
$\mu_{p_{i}}$ from Fact 2.2 is automorphism-invariant and gives $\phi(x,b)$
measure at least $1/n$. ∎

###  3.1 Connection with Dynamics

Corollary 3.34 in [4] is deduced using a ‘definable group analogue’ of Fact
2.4,111The analogue in this case is that, in a definably amenable NIP group,
for any f-generic formula $\phi(x,b)$ there are finitely many global f-generic
types $p_{1},\dots,p_{n}$ such that every translate of $\phi(x,b)$ is
contained in some $p_{i}$. which is proved using topological dynamics in
Section 3.3 of [4]. We observe in this section that an analogous argument also
gives a topological dynamics proof of Fact 2.4.

Let $x$ be a tuple of variables. Then $S_{x}(\mathfrak{C})$ is naturally a
flow for the automorphism group $G=\mathrm{Aut}(\mathfrak{C})$, and a subset
$Y\subseteq S_{x}(\mathfrak{C})$ is a subflow if and only if it is of form
$S_{\pi(x)}(\mathfrak{C})$, where $\pi(x)$ is an automorphism-invariant
partial type over $\mathfrak{C}$ and $S_{\pi(x)}(\mathfrak{C})$ is the set of
complete $x$-types over $\mathfrak{C}$ extending $\pi(x)$. Fix such a
$\varnothing$-invariant partial type $\pi(x)$.

Let us say that an $L(\mathfrak{C})$-formula $\phi(x,b)$ is (weakly) generic
for $\pi(x)$ if the clopen subset of $S_{\pi(x)}(\mathfrak{C})$ corresponding
to $\phi(x,b)$ is (weakly) generic; then $\phi(x,b)$ is generic for $\pi(x)$
if and only if $\pi(x)\vdash\bigvee_{i\in[n]}\phi(x,b_{i})$ for some finitely
many $b_{1},\dots,b_{n}$ with $b_{i}\equiv b$ for each $i\in[n]$, and, by
compactness in $S_{\pi(x)}(\mathfrak{C})$, $\phi(x,b)$ is weakly generic for
$\pi(x)$ if and only if there is an $L(\mathfrak{C})$-formula $\psi(x,c)$ not
generic for $\pi(x)$ such that $\phi(x,b)\vee\psi(x,c)$ is generic for
$\pi(x)$.

Now the following lemmas correspond respectively to Proposition 3.33 and
Proposition 3.30 in [4]:

######  Lemma 3.2.

Suppose that $T$ is NIP and that $\phi(x,b)$ is a non-dividing
$L(\mathfrak{C})$-formula. Then there are finitely many almost periodic types
$p_{1},\dots,p_{n}\in X=S_{x}(\mathfrak{C})$ such that, for any
$b^{\prime}\equiv b$, there is $i\in[n]$ with $p_{i}\vdash\phi(x,b^{\prime})$.

###### Proof.

Given $b^{\prime}\equiv b$, let $F_{b^{\prime}}=\\{p\in
X:p\vdash\phi(x,b^{\prime})\\}$. Since $T$ is NIP, the family of subsets
$\mathcal{F}=\\{F_{b^{\prime}}:b^{\prime}\equiv b\\}$ has finite VC-
codimension, say strictly smaller than $q\in\omega$. Now $\mathcal{F}$ has the
$(p,q)$-property for some $p\in\omega$; otherwise we can find arbitrary long
sequences $b_{1},\dots,b_{p}$ of conjugates of $b$ such that, for any
$s\subseteq[p]$ of size $q$, we have $\bigcap_{i\in s}F_{b_{i}}=\varnothing$,
so that $\bigwedge_{i\in s}\phi(x,b_{i})$ is inconsistent. But then by Ramsey
and compactness we may find an indiscernible sequence $(b_{i})_{i\in\omega}$
of conjugates of $b$ such that $\bigwedge_{i\in s}\phi(x,b_{i})$ is
inconsistent for every $s\subset\omega$ of size $q$, contradicting that
$\phi(x,b)$ does not divide. So indeed $\mathcal{F}$ has the $(p,q)$-property
for some $p\in\omega$, and so by compactness and the $(p,q)$-theorem we may
find finitely many $p_{1},\dots,p_{n}\in X$ such that, for every
$b^{\prime}\equiv b$, there is some $i\in[n]$ with
$p_{i}\vdash\phi(x,b^{\prime})$.

Now consider the flow $X^{n}$, equipped with the product topology and on which
$G$ acts diagonally. Let $Y$ be the closure in $X^{n}$ of the orbit of
$(p_{1},\dots,p_{n})$. We claim that, for any $(q_{1},\dots,q_{n})\in Y$, and
any $b^{\prime}\equiv b$, there is some $i\in[n]$ with
$q_{i}\vdash\phi(x,b^{\prime})$. To see this, suppose otherwise. Let $O$ be
the clopen subset of $X$ corresponding to the formula
$\neg\phi(x,b^{\prime})$; then $O^{n}$ is an open subset of $Y$ containing
$(q_{1},\dots,q_{n})$. But $O^{n}$ is also disjoint from the orbit of
$(p_{1},\dots,p_{n})$; indeed, if $\sigma$ is an automorphism, then some
$p_{i}$ contains $\phi(x,\sigma^{-1}(b^{\prime}))$, and so some $\sigma p_{i}$
contains $\phi(x,b^{\prime})$. So $(q_{1},\dots,q_{n})$ lying in $O^{n}$
contradicts the definition of $Y$.

By Zorn’s lemma, let $Z$ be a minimal subflow of $Y$. Then the image of $Z$
under any of the projection maps $X^{n}\to X$ is a minimal subflow of $X$. In
particular, picking any $(q_{1},\dots,q_{n})\in Z$, then the types
$q_{1},\dots,q_{n}$ have the desired properties. ∎

######  Lemma 3.3.

Suppose that forking and dividing coincide, and that $\pi(x)$ is an
automorphism-invariant partial type over $\mathfrak{C}$. Then a weakly generic
formula for $\pi(x)$ does not fork.

###### Proof.

Suppose that $\phi(x,b)$ forks and that $\phi(x,b)\vee\psi(x,c)$ is generic
for $\pi(x)$; we will show that $\psi(x,c)$ is generic for $\pi(x)$, which
will give the desired result. Since $\phi(x,b)\vee\psi(x,c)$ is generic for
$\pi(x)$, there are $(b_{1},c_{1}),\dots,(b_{n},c_{n})$ with
$(b_{i},c_{i})\equiv(b,c)$ for each $i\in[n]$ and
$\pi(x)\vdash\bigvee_{i\in[n]}(\phi(x,b_{i})\vee\psi(x,c_{i}))$. In other
words, we have $\pi(x)\vdash\zeta(x,\bar{b})\vee\xi(x,\bar{c})$, where

$\displaystyle\zeta(x,y_{1},\dots,y_{n})$
$\displaystyle\equiv\bigvee_{i\in[n]}\phi(x,y_{i})$
$\displaystyle\xi(x,z_{1},\dots,z_{n})$
$\displaystyle\equiv\bigvee_{i\in[n]}\psi(x,z_{i})$

and $\bar{b}=(b_{1},\dots,b_{n}),\bar{c}=(c_{1},\dots,c_{n})$. Now, the
formulas which fork form an ideal, and $\phi(x,b_{i})$ forks for each $i$, so
$\zeta(x,\bar{b})$ forks as well. Since forking and dividing coincide, there
is thus an indiscernible sequence
$(\bar{b}_{k}=(b_{k1},\dots,b_{kn}))_{k\in\omega}$ such that
$\bar{b}_{0}=\bar{b}$ and such that the family of formulas
$(\zeta(x,\bar{b}_{k}):k\in\omega)$ is inconsistent.

Since $\bar{b}\equiv\bar{b}_{k}$ for each $k$, we may find
$(\bar{c}_{k}:k\in\omega)$ such that
$(\bar{b}_{k},\bar{c}_{k})\equiv(\bar{b},\bar{c})$ for each $k$. In
particular, $\pi(x)\vdash\zeta(x,\bar{b}_{k})\vee\xi(x,\bar{c}_{k})$ for each
$k$. On the other hand, for some $q\in\omega$, we have
$\bigwedge_{k\in[q]}\zeta(x,\bar{b}_{k})$ inconsistent, whence
$\pi(x)\vdash\bigvee_{k\in[q]}\xi(x,\bar{c}_{k})$, ie
$\pi(x)\vdash\bigvee_{k\in[q]}\bigvee_{i\in[n]}\psi(x,c_{ki}).$ Since
$\bar{c}\equiv\bar{c}_{k}$ for each $k\in\omega$, it follows that
$c_{ki}\equiv c$ for each $k,i\in\omega$, and hence indeed $\psi(x,c)$ is
generic for $\pi(x)$. ∎

Now Fact 2.4 follows from Lemma 3.2 and Lemma 3.3; indeed, suppose $T$ is NIP
and that $\varnothing$ is an extension base, and let $\phi(x,b)$ be any non-
forking formula. By Lemma 3.2, there are almost periodic types
$p_{1},\dots,p_{n}\in S_{x}(\mathfrak{C})$ such that any conjugate of
$\phi(x,b)$ lies in some $p_{i}$, so it suffices to show that $p_{i}$ is non-
forking for each $i\in[n]$.

To see this, let $Y_{i}$ be the (unique) minimal subflow of
$S_{x}(\mathfrak{C})$ containing $p_{i}$, and let $\pi_{i}(x)$ be an
automorphism-invariant partial type over $\mathfrak{C}$ such that
$Y_{i}=S_{\pi_{i}(x)}(\mathfrak{C})$. $Y_{i}$ is a minimal flow, so by Fact
2.5 any point of $Y_{i}$ is weakly generic in $Y_{i}$, and in particular
$p_{i}$ is. But $\varnothing$ is an extension base, so forking and dividing
coincide by Fact 2.3, and now the result follows from Lemma 3.3.

##  4 Counterexample

In this section we show that Theorem 3.1 can fail if the amenability
hypothesis is dropped. First, in Section 4.1, we give a general construction,
which obtains from a structure $M$ a new structure $M_{\mathrm{cyc}}$ in which
algebraic formulas from $M$ give rise to forking formulas. Then in Section 4.2
we make some basic observations about the model theory of the binary tree
$M=(2^{<\omega},\leqslant)$, and then in Section 4.3 we show that the
structure $M_{\mathrm{cyc}}$ associated to it has the desired behavior.

###  4.1 General Construction

Let $L$ be a first-order language, and assume for notational convenience that
it is one-sorted. We define a new language $L_{\mathrm{cyc}}$, which has two
sorts $E$ and $B$, a function symbol $\pi:E\to B$, a ternary relation symbol
$\mathrm{cyc}$ on the sort $E$, and all the symbols of $L$, taken as symbols
on the sort $B$. Now, given an $L$-structure $M$, we define a corresponding
$L_{\mathrm{cyc}}$-structure $M_{\mathrm{cyc}}$ by taking
$E(M_{\mathrm{cyc}})=S^{1}\times M$ and $B(M_{\mathrm{cyc}})=M$, taking
$\pi:S^{1}\times M\to M$ to be the projection map, and taking $\mathrm{cyc}$
to be the circular order on each fiber of $\pi$ and to induce no other
relations. (So that $\mathrm{cyc}(x,y,z)\to\pi(x)=\pi(y)=\pi(z)$.)

Note that $M_{\mathrm{cyc}}$ is interpretable in the two-sorted structure
$(S^{1},M)$; in particular, if $M$ is NIP, then $M_{\mathrm{cyc}}$ will be
too. Now, let $\mathfrak{C}$ be a saturated model of
$\mathrm{Th}(M_{\mathrm{cyc}})$. By uniqueness of saturated models,
$\mathfrak{C}$ can be identified with the projection
$\bar{S}^{1}\times\bar{M}\to\bar{M}$, where $\bar{S}^{1},\bar{M}$ are
saturated models of the circular order and of $\mathrm{Th}(M)$, respectively.
Note that the automorphisms of $\mathfrak{C}$ are in bijection with pairs
$(\alpha,(f_{e})_{e\in\bar{M}})$, where $\alpha$ is an automorphism of
$\bar{M}$ and $f_{e}$ is an automorphism of $\bar{S}^{1}$ for each
$e\in\bar{M}$; the associated automorphism of $\mathfrak{C}$ acts on the
$E$-sort by taking $(u,e)$ to $(f_{e}(u),\alpha(e))$.

In the section we will focus on $L_{\mathrm{cyc}}(\bar{M})$-formulas of the
form $\phi(\pi(x),b)$, where $\phi(z,b)$ is an $L(\bar{M})$-formula. We will
show that $\phi(\pi(x),b)$ forks in $\mathfrak{C}$ if and only if $\phi(z,b)$
implies a disjunction of an algebraic $L$-formula and a forking
$L(\bar{M})$-formula; first we give the backwards direction:

######  Lemma 4.1.

Let $\theta(z)$ be an algebraic $L$-formula and $\psi(z,d)$ an
$L(\bar{M})$-formula that forks in $\bar{M}$; then the formula
$\theta(\pi(x))\vee\psi(\pi(x),d)$ forks in $\mathfrak{C}$.

###### Proof.

It suffices to show that $\theta(\pi(x))$ and $\psi(\pi(x),d)$ each fork in
$\mathfrak{C}$. To see that $\theta(\pi(x))$ forks in $\mathfrak{C}$, let
$b_{1},\dots,b_{n}$ be the realizations of $\theta(z)$; now $\theta(\pi(x))$
implies the disjunction $\bigvee_{i\in[n]}(\pi(x)=b_{i})$. But each formula
$\pi(x)=b_{i}$ forks in $\mathfrak{C}$, since the induced structure on the
fiber $\bar{S}^{1}\times\\{b_{i}\\}$ is just the circular order, and any
formula in the circular order forks. So we need only show that
$\psi(\pi(x),d)$ forks in $\mathfrak{C}$.

By hypothesis, $\psi(z,d)$ implies a finite disjunction
$\bigvee_{i\in[n]}\xi_{i}(z,e)$, where each $\xi_{i}(z,e)$ is an
$L(\bar{M})$-formula that divides in $\bar{M}$, and so it suffices to show
that each $\xi_{i}(\pi(x),e)$ divides in $\mathfrak{C}$. But if
$(e_{j})_{j\in\omega}$ is an indiscernible sequence from $\bar{M}$ with
$e_{0}=e$ and $(\xi_{i}(z,e_{j}):j\in\omega)$ inconsistent, then
$(\xi_{i}(\pi(x),e_{j}):j\in\omega)$ is also inconsistent, and
$(e_{j})_{j\in\omega}$ is still an indiscernible sequence in $\mathfrak{C}$,
so that indeed $\xi_{i}(\pi(x),e)$ divides in $\mathfrak{C}$. ∎

In the rest of the section we will show the forwards direction of the claim
above; first we need some auxiliary observations about types in
$\mathfrak{C}$.

######  Lemma 4.2.

Let $(c_{1},\dots,c_{n})$ and $(c^{\prime}_{1},\dots,c^{\prime}_{n})$ be
tuples from $E(\mathfrak{C})=\bar{S}^{1}\times\bar{M}$ and $a,a^{\prime}$
elements of $E(\mathfrak{C})$ such that (i) $\pi(a)\neq\pi(c_{i})$ and
$\pi(a^{\prime})\neq\pi(c^{\prime}_{i})$ for each $i$, (ii)
$(\pi(a),\pi(\bar{c}))$ and $(\pi(a^{\prime}),\pi(\bar{c}^{\prime}))$ have the
same type in $\bar{M}$, and (iii) $\bar{c}$ and $\bar{c}^{\prime}$ have the
same type in $\mathfrak{C}$. Then $(a,\bar{c})$ and
$(a^{\prime},\bar{c}^{\prime})$ have the same type in $\mathfrak{C}$.

###### Proof.

By (iii), let $(\alpha,(f_{e})_{e\in\bar{M}})$ be the data associated to an
automorphism of $\mathfrak{C}$ taking $\bar{c}$ to $\bar{c}^{\prime}$. Also,
by (ii), let $\beta$ be an automorphism of $\bar{M}$ taking
$(\pi(a),\pi(\bar{c}))$ to $(\pi(a^{\prime}),\pi(\bar{c}^{\prime}))$. Finally,
using that any two elements of $\bar{S}^{1}$ have the same type, let $f$ be an
automorphism of $\bar{S}^{1}$ taking the first coordinate of $a$ to the first
coordinate of $a^{\prime}$. Now, for $e\in\bar{M}$, define an automorphism
$g_{e}$ of $\bar{S}^{1}$ by cases:

$g_{e}=\begin{cases}f&\text{if }e=\pi(a)\\\ f_{e}&\text{if }e=\pi(c_{i})\text{
for some }i\\\ \mathrm{id}_{\bar{S}^{1}}&\text{otherwise}.\end{cases}$

By condition (i), this is well-defined, and the automorphism of $\mathfrak{C}$
associated to $(\beta,(g_{e})_{e\in\bar{M}})$ then takes $(a,\bar{c})$ to
$(a^{\prime},\bar{c}^{\prime})$, as needed. ∎

######  Corollary 4.3.

Suppose $C\subseteq E(\mathfrak{C})=\bar{S}^{1}\times\bar{M}$ and $a\in
E(\mathfrak{C})$ are such that (i) $\pi(a)\notin\pi(C)$, and (ii)
$\operatorname{tp}(\pi(a)/\pi(C))$ does not divide in $\bar{M}$. Then
$\operatorname{tp}(a/C)$ does not divide in $\mathfrak{C}$.

###### Proof.

Let $(\bar{c}_{i})_{i\in\omega}$ be an indiscernible sequence, where
$\bar{c}_{0}$ is a finite tuple from $C$. We wish to find $a^{\prime}$ such
that $(a^{\prime},\bar{c}_{i})$ and $(a,\bar{c}_{0})$ have the same type in
$\mathfrak{C}$ for every $i\in\omega$. Since
$\operatorname{tp}(\pi(a)/\pi(C))$ does not divide, we may (picking a first
coordinate arbitrarily) find some $a^{\prime}\in E(\mathfrak{C})$ such that
$(\pi(a^{\prime}),\pi(\bar{c}_{i}))$ and $(\pi(a),\pi(\bar{c}_{0}))$ have the
same type in $\bar{M}$ for every $i\in\omega$. But, since
$\pi(a)\notin\pi(C)$, this gives the desired result by Lemma 4.2. ∎

Now we can give the desired characterization.

######  Lemma 4.4.

Let $\phi(z,b)$ be an $L({\bar{M}})$-formula. Then $\phi(\pi(x),b)$ forks in
$\mathfrak{C}$ if and only if there is an $L$-formula $\theta(z)$ and an
$L(\bar{M})$-formula $\psi(z,d)$ such that $\theta(z)$ is algebraic,
$\psi(z,d)$ forks in $\bar{M}$, and $\phi(z,b)\vdash\theta(z)\vee\psi(z,d)$.

###### Proof.

The backwards direction is Lemma 4.1, so we show the forwards direction.
Suppose for contradiction that $\phi(\pi(x),b)$ forks in $\mathfrak{C}$ but
that the desired conclusion does not hold. Then there are some finite
$C\subset E(\mathfrak{C})$ and $D\subset B(\mathfrak{C})=\bar{M}$ such that,
for any $a\in\bar{S}^{1}\times\bar{M}$ realizing $\phi(\pi(x),b)$,
$\operatorname{tp}(a/C,D)$ divides. Expanding $C$ if necessary, we may assume
without loss of generality that $\pi(C)\supseteq D$, so that
$\operatorname{tp}(a/C)$ divides for any $a\models\phi(\pi(x),b))$.

Now, by hypothesis, $\phi(z,b)$ is consistent with
$\neg\theta(z)\wedge\neg\psi(z,d)$ for every algebraic $L$-formula $\theta(z)$
and every $L(\pi(C))$-formula $\psi(z,d)$ that forks in $\bar{M}$. Formulas of
these latter two kinds form an ideal, so by compactness (and picking an
arbitrary first coordinate) we may find some $a\in E(\mathfrak{C})$ such that:

  1. 1.

$\pi(a)\models\phi(z,b)$.

  2. 2.

$\operatorname{tp}(\pi(a)/\varnothing)$ is non-algebraic.

  3. 3.

$\operatorname{tp}(\pi(a)/\pi(C))$ does not fork in $\bar{M}$.

(2) and (3) together imply that $\pi(a)\notin\pi(C)$. By (3) and Corollary
4.3, this implies that $\operatorname{tp}(a/C)$ does not divide in
$\mathfrak{C}$. By (1), this contradicts the choice of $C$. ∎

###  4.2 Binary Tree

Let $L=\\{\leqslant\\}$ be the language of trees and let $M$ be the tree
$(2^{<\omega},\leqslant)$. Note that $M$ is NIP, and indeed dp-minimal, since
any tree is; see [10]. Let $\bar{M}$ be a saturated model of $\mathrm{Th}(M)$.
Note that $M$ is a meet-tree, and so $\bar{M}$ is as well. We have
$\operatorname{acl}(\varnothing)=M$, so that $M$ is the unique minimal
elementary substructure of $\bar{M}$. By a back-and-forth argument, any two
elements $b,b^{\prime}\in\bar{M}\setminus M$ have the same type over
$\varnothing$, and the non-algebraic $1$-types over $M$ correspond to paths
through $2^{<\omega}$: given $f\in 2^{\omega}$, there is a unique $1$-type
over $M$ determined by $\\{x>f|_{n}:n\in\omega\\}$, and conversely any
unrealized $1$-type over $M$ is of that form.

Now, suppose $I=(b_{i})_{i\in\omega}$ is any non-constant indiscernible
sequence of elements of $\bar{M}$; then, since
$M=\operatorname{acl}(\varnothing)$, $I$ is indiscernible over $M$, and so all
the elements of $I$ determine the same path through $M$. In particular, for
every $n\in\omega$, we have $b_{1}\wedge\dots\wedge b_{n}\notin M$.

######  Lemma 4.5.

Let $b\in\bar{M}\setminus M$. Then the formula $\phi(z,b)\equiv z\leqslant b$
does not imply a disjunction of an algebraic formula without parameters and an
$L(\bar{M})$-formula that forks.

###### Proof.

It suffices to show that $\phi(z,b)\wedge\neg\theta(z)$ does not fork over
$\varnothing$ for every algebraic $\theta(z)$ without parameters. So suppose
otherwise; then $\phi(z,b)\wedge\neg\theta(z)$ implies a finite disjunction of
formulas that each divide over $\varnothing$. Since
$M=\operatorname{acl}(\varnothing)$, a formula divides over $\varnothing$ if
and only if it divides over $M$, and hence $\phi(z,b)\wedge\neg\theta(z)$
implies a finite disjunction of formulas that each divide over $M$; in other
words $\phi(z,b)\wedge\neg\theta(z)$ forks over $M$. But $\mathrm{Th}(M)$ is
NIP, so forking and dividing coincide over models, and hence
$\phi(z,b)\wedge\neg\theta(z)$ divides over $M$. Let $(b_{i})_{i\in\omega}$ be
an indiscernible sequence witnessing this; then for some $n\in\omega$ we have
$\phi(z,b_{1})\wedge\dots\wedge\phi(z,b_{n})\vdash\theta(z)$. In particular,
we have $b_{1}\wedge\dots\wedge b_{n}\models\theta(z)$. But $\theta$ is
algebraic, so this forces $b_{1}\wedge\dots\wedge b_{n}\in M$, contradicting
the remark above this lemma. ∎

###  4.3 Main example

Now we can give the main example. Let $M$ be the tree from Section 2. Let
$\mathfrak{C}$ be a saturated model of $\mathrm{Th}(M_{\mathrm{cyc}})$, with
$E$-sort $\bar{S}^{1}\times\bar{M}$. Pick any $b\in\bar{M}\setminus M$, and
let $\phi(z,b)\equiv z\leqslant b$.

######  Lemma 4.6.

The formula $\phi(\pi(x),b)$ does not fork.

###### Proof.

This follows from Lemma 4.4 and Lemma 4.5. ∎

######  Lemma 4.7.

Let $\mu$ be a automorphism-invariant Keisler measure on the $E$-sort of
$\bar{M}$. Then $\mu(\phi(\pi(x),b))=0$.

###### Proof.

Suppose otherwise that $\mu(\phi(\pi(x),b))=\varepsilon>0$. Recalling that any
two elements of $\bar{M}\setminus M$ have the same type over $\varnothing$, we
thus have $\mu(\phi(\pi(x),b^{\prime}))=\varepsilon$ for every
$b^{\prime}\in\bar{M}\setminus M$. Let $n$ be such that $n\varepsilon>1$, and
let $m$ be any natural number with $2^{m}>n$; I claim that
$\mu\left(P_{m}(\pi(x))\right)>0$, where $P_{m}(z)\equiv\exists^{\leqslant
m}u(u\leqslant z)$ is the formula of $\bar{M}$ expressing that $z$ is of
height at most $m$.

To see this, suppose $\mu\left(P_{m}(\pi(x))\right)=0$. Since $2^{m}>n$, we
may find distinct elements $c_{1},\dots,c_{n}\in M$ of height precisely $m$.
Pick any $b_{i}\in\bar{M}\setminus M$ with $b_{i}\geqslant c_{i}$; then
$b_{i}\wedge b_{j}\models P_{m}(z)$ for each $i\neq j$. Hence
$\phi(z,b_{i})\wedge\phi(z,b_{j})\vdash P_{m}(z)$ for each $i\neq j$; since
$P_{m}(\pi(x))$ has measure $0$ under $\mu$, also

$\mu\big{(}\phi(\pi(x),b_{i})\wedge\phi(\pi(x),b_{j})\big{)}=0$

for each $i\neq j$. But then

$\mu\left(\bigvee_{i\in[n]}\phi(\pi(x),b_{i})\right)=\sum_{i\in[n]}\mu(\phi(\pi(x),b_{i}))=n\varepsilon>1,$

a contradiction.

So indeed $\mu(P_{m}(\pi(x)))>0$. But $P_{m}(z)$ is algebraic, so the formula
$P_{m}(\pi(x))$ forks over $\varnothing$ by Lemma 4.1, contradicting that
$\mu$ is $\varnothing$-invariant. ∎

Thus $\mathrm{Th}(M_{\mathrm{cyc}})$ is an NIP theory for which, in a
saturated model, there are non-forking formulas given measure $0$ by any
automorphism-invariant Keisler measure; this gives the desired example.

## References

  * [1] Hans Adler. Introduction to theories without the independence property. Preprint (2008).
  * [2] A. Chernikov, E. Hrushovski, A. Kruckman, K. Krupiński, S. Moconja, A. Pillay, N. Ramsey. Invariant measures in simple and in small theories. Journal of Mathematical Logic, Vol. 23 Iss. 2 (2023).
  * [3] Artem Chernikov, Itay Kaplan. Forking and dividing in NTP2 theories. The Journal of Symbolic Logic, Vol. 77 No. 1 (2012). pp. 1-20.
  * [4] Artem Chernikov, Pierre Simon. Definably amenable NIP groups. Journal of the AMS, Vol. 31 Iss. 3 (2018). pp. 609-641.
  * [5] Artem Chernikov, Pierre Simon. Externally definable sets and dependent pairs II. Transactions of the AMS, Vol. 367 No. 7 (2015). pp. 5217-5235.
  * [6] Ehud Hrushovski, Krzysztof Krupiński, Anand Pillay. Amenability, connected components, and definable actions. Selecta Mathematica 28, Article 16 (2022).
  * [7] Ehud Hrushovski, Krzysztof Krupiński, Anand Pillay. On first-order amenability. Preprint (2020) arXiv:2004.08306.
  * [8] Ehud Hrushovski, Anand Pillay. On NIP and invariant measures. Journal of the EMS, Vol. 13 No. 4 (2011). pp. 1005-1061.
  * [9] Ludomir Newelski. Topological dynamics of definable group actions. The Journal of Symbolic Logic, Vol. 74 No. 1 (2009). pp. 50-72.
  * [10] Pierre Simon. On dp-minimal ordered structures. The Journal of Symbolic Logic, Vol. 76 No. 2 (2011). pp. 448-460.
  * [11] Martin Ziegler. Introduction to the Lascar Group, in Tits Buildings and the Model Theory of Groups. Cambridge University Press (2010).