# Henderson-like interval maps

Jernej Činč

###### Abstract.

In this paper we study interval maps $f$ with zero topological entropy that
are crooked; i.e. whose inverse limit with $f$ as the single bonding map is
the pseudo-arc. We show that there are uncountably many pairwise non-conjugate
zero entropy crooked interval maps with different sets of fixed points. We
also show that there are uncountably many crooked maps that are pairwise non-
conjugate and have exactly two fixed points. Furthermore, we provide a
characterization of crooked interval maps that are under or above the
diagonal.

###### Key words and phrases:

pseudo-arc, inverse limit

###### 2010 Mathematics Subject Classification:

37E05, 37B45

##  1\. Introduction

The aim of this paper is to address the question about variety of maps with
entropy $0$ that give pseudo-arc in the inverse limit. Henderson in [14]
provided a construction to obtain such a map, we call it here the Henderson
map $f_{H}$, see Section 3.1 for more information on the construction of such
a map. However, it is a priori unclear if the construction given in [14] can
be modified in order to obtain interval maps non-conjugate to $f_{H}$ whose
inverse limit is the pseudo-arc and have topological entropy $0$. This
question has been recently circulating in the community working in the
interaction between Continuum Theory and Topological Dynamical Systems; it was
also mentioned in the introduction of the paper of Drwięga and Oprocha [12].
We answer this question in the affirmative and in particular show that there
are uncountably many such pairwise non-conjugate interval maps with different
sets of fixed points as well as with exactly two fixed points. Moreover, we
provide a characterization of crooked interval maps that are under the
diagonal. Our characterization of crooked under diagonal maps says it is
enough to require crookedness in an arbitrary small neighbourhood $U$ of point
$1$ and in addition to find a point $x\in U$ that is attracted to $0$ by this
map. Analogous results also hold for maps that are under the diagonal.

In a sense, this paper also initiates the study that is complementary to the
study in [10]. There, Oprocha and the author prove that generic maps in the
closure of the set of all maps with dense set of periodic points as well as in
the set of all Lebesgue measure-preserving are giving pseudo-arc in the
inverse limit. In that context, the topological entropy of maps is known to be
$\infty$ (see e.g. Proposition 26 in [7] and Remark in [8]). Mouron [17] has
proved that crooked maps can have topological entropy $\infty$ or $0$.
Combining these perspectives and putting them in the context of [10] our
results also show that there are uncountably many non-conjugate embeddings of
the pseudo-arc in the plane with planar homeomorphisms having topological
entropy $0$. This follows from application of BBM technique developed by Barge
and Martin [3] (see [10] for details).

Furthermore, our study can be seen as the continuation of the study towards
understanding the interaction between the dynamics of interval maps and
topological complexity of their inverse limits. One direction of this line of
study culminated in a very nice paper of Darji and Kato [11] where the
authors, using recent developments in local entropy theory, show that inverse
limit of a graph map with positive topological entropy contains an
indecomposable subcontinuum. The other direction of this line of research has,
however, not been explored to a great extent and our research can be thought
as the first step in that direction. Our paper can also be treated as a
continuation of the work of Greenwood and Štimac [13] where the authors
characterized interval maps that give arcs in the inverse limit.

Let us give a brief outline of the paper. In Section 2 we provide preliminary
definitions used throughout the paper. In Section 3 we define the collection
of maps that we will work with in the rest of the paper, provide initial
examples that motivate our study and explain our approach. In Section 3.1 we
give a brief outline of the Henderson’s example $f_{H}$ [14] that will be used
implicitly in the rest of the paper. Finally, in Section 4 we prove the main
results about non-conjugate under and upper diagonal interval maps with zero
topological entropy that give pseudo-arc in the inverse limit as well as
provide their characterization.

##  2\. General preliminaries

We denote the set of natural numbers by $\mathbb{N}:=\\{1,2,3,\ldots\\}$, and
let $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$. By $I$ let us denote the unit
interval $[0,1]\subset\mathbb{R}$. A map $f\colon I\to I$ is a continuous
surjective function. Denote the set of interval maps by $C(I)$. We equip
$C(I)$ with the metric of uniform convergence. Let $f^{n}=f\circ\ldots\circ f$
denote the $n$-th iterate of $f$. We call a point $c\in(0,1)$ a critical point
of $f\colon I\to I$ if for every open $J\ni c$, $f|_{J}$ is not one-to-one. In
particular, we say that $c$ is a strict critical point if in addition there
exists an interval $c\in(t_{1},t_{2})\subset J$ such that $f|_{(t_{1},c)}$ and
$f|_{(c,t_{2})}$ are one-to-one. Interval map is called piecewise monotone, if
it has finitely many critical points. Given $f\colon I\to I$, an orbit of a
point $x\in I$ is the set

$\operatorname{Orb}(x,f):=\\{f^{n}(x):n\geq 0\\}.$

We say that a point $x\in I$ is $f$-attracted to $y\in I$ if $f^{n}(x)\to y$
as $n\to\infty$. The set of fixed points of $f$ will be denoted by

$\mathrm{Fix}(f):=\\{y\in I:f(y)=y\\}.$

We say that maps $f,g\in C(I)$ are conjugate, if there exists a homeomorphism
$h:I\to I$ such that $g=h\circ f\circ h^{-1}$.

A continuum is a non-empty, compact, connected, metric space. In the
definition of inverse limit space we can assume without loss of generality
that the bonding functions are surjective. Let $\\{I_{i}\\}_{i\in\mathbb{N}}$
be a collection of closed intervals from $I$. An inverse sequence of
$\\{I_{i}\\}_{i\in\mathbb{N}}$ is a pair of sequences
$(I_{i},f_{i})_{i\in\mathbb{N}}$ where $f_{i}\colon I_{i}\to I_{i+1}$,
$i\in\mathbb{N}$. The inverse limit is defined by:

$\underleftarrow{\lim}(I_{i},f_{i})=\\{(x_{1},x_{2},\ldots):f_{i}(x_{i+1})=x_{i},i\in\mathbb{N}\\}\subset
I_{1}\times I_{2}\times\ldots.$

Equipped with the product topology, $\underleftarrow{\lim}\\{I_{i},f_{i}\\}$
is a continuum, and it is arc-like, i.e. for every $\varepsilon>0$ there
exists an $\varepsilon$-mapping onto an interval. The coordinate projections
are defined by $\pi_{i}\colon\underleftarrow{\lim}(I_{i},f_{i})\to I$,
$\pi_{i}((x_{1},x_{2},\ldots))=x_{i}$, for $i\in\mathbb{N}$ and they are all
continuous.

If $f_{i}=f$ and $I_{i}=I$ for all $i\in\mathbb{N}$, we denote the inverse
limit by $\hat{I}:=\underleftarrow{\lim}(I,f)$. Then there exists a
homeomorphism $\hat{f}\colon\hat{I}\to\hat{I}$, given by

$\hat{f}((x_{0},x_{1},\ldots)):=(f(x_{0}),f(x_{1}),f(x_{2}),\ldots)=(f(x_{0}),x_{0},x_{1},\ldots).$

It is called the natural extension of $f$ (or sometimes shift homeomorphism).

##  3\. Under diagonal, above diagonal maps and preliminary examples

######  Definition 3.1.

A map $f:I\to I$ is called _under diagonal_ if $f(x)\leq x$ for every
$x\in[0,1]$. A map $f:I\to I$ is called _$0$ -attracted_ if $f(0)=0$, $f(1)=1$
and $f(x)<x$ for every $x\in(0,1)$. Denote the set of $0$-attracted interval
maps by $C_{ud}(I)$ and the set of $0$-attracted interval maps by
$C_{0}(I)\subset C_{ud}(I)$. We also define _above diagonal_ interval maps $f$
by $f(x)\geq x$ for every $x\in[0,1]$. A map is called $1$-attracted if
additionally $f(x)>x$ for every $x\in(0,1)$). We denote the set of above
diagonal interval maps by $C_{ad}(I)$ and the set of $1$-attracted maps by
$C_{1}(I)$.

The following theorem shows that the inverse limits with piecewise monotone
under diagonal maps are topologically unique. This follows from Theorem B8
from [2] since by the definition of under diagonal maps, for every $x\in I$
there exists $p\in\mathrm{Fix}(f)$ such that $f^{n}(x)\mapsto p$ as
$n\to\infty$ (in the terminology of [2] every $x\in I$ is $f$-attracted to
some $p\in\mathrm{Fix}(f)$).

######  Theorem 3.1.

If $f:I\to I$ is under diagonal and piecewise monotone then $\hat{I}_{f}$ is
homeomorphic to an arc.

######  Definition 3.2.

Let $f\in C(I)$ and let $a,b\in I$ and let $\delta>0$. We say that $f$ is
$\delta$-crooked between $a$ and $b$ if for every two points $c,d\in I$ such
that $f(c)=a$ and $f(d)=b$, there is a point $c^{\prime}$ between $c$ and $d$
and there is a point $d^{\prime}$ between $c^{\prime}$ and $d$ such that
$|b-f(c^{\prime})|<\delta$ and $|a-f(d^{\prime})|<\delta$. We will say that
$f$ is $\delta$-crooked if it is $\delta$-crooked between every pair of points
from $I$. We will say that $f$ is $(n,\delta)$-crooked if $f^{n}$ is
$\delta$-crooked.
We will simply say that $f$ is crooked, if for every $\delta>0$ there exists
$n\in\mathbb{N}$ such that $f^{n}$ is $\delta$-crooked.

In particular, Theorem 3.1 says that crooked interval maps cannot be piecewise
monotone.

From [15, Theorem 3.5] it follows that crookedness is equivalent to inverse
limit being hereditary indecomposable which in the arc-like case means the
inverse limit is the pseudo-arc.

######  Proposition 3.3.

Space $\hat{I}_{f}$ is the pseudo-arc if and only if $f$ is crooked.

Next examples show that even for $0$-attracted maps there is no connection
between interval maps with infinitely many strict critical points and
crookedness. With them we want to emphasize the topological variety of
$\hat{I}_{f}$ despite simple dynamics of $f$.

######  Example 3.4.

There exists a $0$-attracted map $f\in C(I)$ with infinitely many strict
critical points so that $\hat{I}_{f}$ is homeomorphic to an arc, see Figure 3.
Indeed, this follows from an extension of Lemma B.5 in [2] since every
$x\in[0,1)$ is $f$-attracted to $0$, see Remark B.7 in [2].

Figure 1. Graph of a $0$-attracted interval map $f$ with infinitely many
critical points for which the inverse limit is an arc.

The following example shows that $0$-attracted ($1$-attracted) maps can have
inverse limits that are neither pseudo-arc nor arc.

A double $\sin(1/x)$ continuum is a continuum which consisting of two rays
(homeomorphic image of $[0,1)$) that both accumulate on a unique arc, see the
right picture on Figure 2.

######  Example 3.5.

There exists a $1$-attracted interval map $f$ with infinitely many critical
points so that $\hat{I}_{f}$ is not homeomorphic to an arc and there are
countably infinitely many double $\sin(1/x)$ continua, see Figure 2. An
important feature of map $f$ is that the absolute value of the slope of map
restricted to intervals $[a_{1},b_{1}]$ is $1$ and for every $i\in\mathbb{N}$
there is a subinterval of $[a_{i+1},b_{i+1}]$ that maps onto $[a_{i},b_{i}]$
and that
$\operatorname{diam}(f^{i-1}([a_{i},b_{i}]))=\operatorname{diam}([f(a_{1}),f(b_{1})])$
(compare this with Example 4.12 in [2]). The subcontinuum
$H:=\underleftarrow{\lim}([a_{i},b_{i}],f|_{[a_{i},b_{i}]})$ is homeomorphic
to a double $\sin(1/x)$ continuum (see the right picture on Figure 2). Also
${\hat{f}}^{n}(H)$ will be double $\sin(1/x)$ continuum for every
$n\in\mathbb{N}$.

However, similar construction as in the Example 3.5 but requiring for every
$i\in\mathbb{N}$ that $\operatorname{diam}(f^{i-1}([a_{i},b_{i}]))=0$ would
yield $\hat{I}_{f}$ is an arc (compare to Example 4.12 in [2]).

$1$$0$$a^{\prime}_{5}$$b^{\prime}_{5}$$a^{\prime}_{4}$$b^{\prime}_{4}$$a^{\prime}_{3}$$b^{\prime}_{3}$$a^{\prime}_{2}$$a_{2}$$b_{2}$$b^{\prime}_{2}$$a^{\prime}_{1}$$a_{1}$$b_{1}$$b^{\prime}_{1}$$a^{\prime}_{0}$$b_{0}$$a_{0}$$b^{\prime}_{0}$

Figure 2. Left: graph of an example of a $1$-attracted interval map $f$ for
which the inverse limit has (double) $\sin(1/x)$-continua. Right: double
$\sin(1/x)$-continuum.

###  3.1. Henderson’s map $f_{H}$

In comparison with the examples above we recall the construction of a crooked
$0$-attracted interval map from [14]. We state it here rather detailed
because, in a sense, it gives minimal (eventual) requirements for an under
diagonal map to be crooked as we shall see later in the paper.

######  Definition 3.6.

With $\langle a,b,c,d\rangle$ we denote a quadruple of real numbers such that
$0\leq a<b<c<d\leq 1$. Denote by $W:=\\{\alpha_{i}:=\langle
a_{i},b_{i},c_{i},d_{i}\rangle|i\in\mathbb{N}\\}$ a quadruple of all
increasing rational points on $(0,1)$. Denote $J_{i}:=[a_{i},d_{i}]$.

######  Definition 3.7.

Let $[u,v],\langle a,b,c,d\rangle\subset I$. We say that $f$ maps $[u,v]$
crookedly onto $\langle a,b,c,d\rangle$, if

  1. (1)

$[a,d]\subset f([u,v])$ and

  2. (2)

     * •

either there either exists $b^{\prime}\in f^{-1}(b)$ and
$c^{\prime},c^{\prime\prime}\in f^{-1}(c)$ with $c^{\prime}<c^{\prime\prime}$
such that $c^{\prime}<b^{\prime}<c^{\prime\prime}$

     * •

or there either exists $c^{\prime}\in f^{-1}(c)$ and
$b^{\prime},b^{\prime\prime}\in f^{-1}(b)$ with $b^{\prime}<b^{\prime\prime}$
such that $b^{\prime}<c^{\prime}<b^{\prime\prime}$.

We say that an interval $[u,v]\subset I$ is larger than $t\in I$, if $u>t$.
Let $J_{1},J_{2}\subset I$ be intervals. We say that $f$ maps $J_{1}$
minimally on interval $U$ if $f$ maps $J_{1}$ onto $U$, however for every
proper subinterval $J$ of $J_{1}$ it holds that $f(J)\subsetneq U$.

The following technical lemma from [14] is crucial in the construction of the
map $f_{H}$.

######  Lemma 3.8.

There exists a sequence of interval maps $(f_{i}:I\to I)_{i\in\mathbb{N}}$ and
sequences $(\ell_{i})_{i\in\mathbb{N}},(L_{i})_{i\in\mathbb{N}}\subset(0,1)$
so that for all $i\in\mathbb{N}$ and all $j\in\mathbb{N}$ it holds:

  1. (1)

$f_{i}(x)\leq x^{2}$ for all $x\in I$,

  2. (2)

$f_{i}(x)=f_{i+j}(x)$ for all $x\in[0,l_{i+1})$ and $f_{i}(x)=x^{2}$ for all
$x\in(\ell_{i+1},1]$,

  3. (3)

if $\ell_{i+1}<x<1$ then $f_{i}(x)>\ell_{i}$,

  4. (4)

$d_{i}<\ell_{i+1}$ and $\ell_{i}<L_{i}<\ell_{i+1}<1$,

  5. (5)

if $V$ is larger than $L_{i}$ and for some $n\in\mathbb{N}$ we have
$I_{i}\subset f^{n}_{i}(V)$, then $f^{n}_{i}$ maps $V$ crookedly on
$\alpha_{i}$.

  6. (6)

if $W$ is larger than $\ell_{i+1}$ and there exists $m\in\mathbb{N}$ so that
$f^{m}_{i+j}$ maps $W$ minimally on $I_{i}$, then there exists $k<m$ so that
$f^{k}_{i+j}$ maps $W$ into $L_{i},\ell_{i+1}$.

Using the previous lemma one gets the following.

######  Lemma 3.9.

There exists a $0$-attracted interval map $f_{H}:=\lim_{i\to\infty}f_{i}$ so
that for any $\langle a,b,c,d\rangle\subset(0,1)$ there exists
$m\in\mathbb{N}$ such that for every $n>m$ if $f_{H}^{n}([u,v])=[a,d]$ for
$[u,v]\subset I$, then $f_{H}^{n}$ maps $[u,t]$ crookedly onto $\langle
a,b,c,d\rangle$.

######  Theorem 3.2.

Map $f_{H}$ is crooked.

$a$$b$$c$$d$$d_{-2}$$c_{-2}$$b_{-2}$$a_{-2}$$\ell_{1}$$L_{1}$$\ell_{2}$ Figure
3. Graph of $f_{1}$ from the construction of $f_{H}$; $x_{-2}$ denotes $y\in
f^{-2}(x)$ for some $x\in I$.

##  4\. Pairwise non-conjugate crooked maps derived from $f_{H}$

Note that crookedness is preserved under topological conjugacies, i.e.,
provided $f\in C(I)$ is crooked and $g\in C(I)$ is conjugate to $f$, then $g$
is also crooked. This indeed follows immediately from Proposition 3.3 and the
fact that if $f$ is conjugate to $g$, then $\hat{I}_{f}$ is homeomorphic to
$\hat{I}_{g}$. First let us state a standard observation, see e.g. Proposition
5 from [6].

######  Observation 4.1.

Let $H$ be a subcontinuum of $\hat{I}_{f}$. Then there exists an inverse
sequence $(J_{i},f_{i})_{i\in\mathbb{N}}$ where $J_{i}\subset I$ are closed
intervals or points and $f_{i}=f|_{J_{i}}$ continuous surjections so that
$H=\underleftarrow{\lim}(J_{i},f_{i})$. In particular, if $H$ is non-
degenerate then $J_{i}$ are non-degenerate for all but finitely many
$i\in\mathbb{N}$.

The following proposition was proven in [4, 5]. We will use it when studying
the subcontinua of $\hat{I}_{f}$.

For $i>j\geq 1$ let $f_{i,j}:=f_{j-1}\circ\ldots\circ f_{i}$. For completeness
let $f_{i,i}:=\mathrm{id}$.

######  Proposition 4.2.

[16, Proposition 3.2] Let $f:I\to I$ and let a nondegenerate continuum
$H\subset\hat{I}_{f}$ be the inverse limit of an inverse sequence
$\left(I_{k},f_{k}\right)_{k=1}^{\infty}$, where $I_{k}\subset I$ for
$k=1,2,\ldots$ are closed intervals. Then, $H$ is a pseudo-arc if and only if
for every $\delta>0$ and every positive integer $k$ there is an integer
$k^{\prime}>k$ such that $f_{k^{\prime},k}$ is $\delta$-crooked (where
$f_{k^{\prime},k}$ is a continuous surjection from $I_{k}^{\prime}$ to
$I_{k}$).

######  Definition 4.3.

Let $f:I\to I$ be an under diagonal map and let $\eta\in(0,1)$. For every
$i\geq 2$ denote by $I_{i}(\eta)$ a connected component of
$f^{-i+1}([\eta,1])$ such that the inverse limit
$\hat{I}(\eta)\subset\hat{I}_{f}$

$I_{1}(\eta)\xleftarrow{f|_{I_{2}(\eta)}}I_{2}(\eta)\xleftarrow{f|_{I_{3}(\eta)}}I_{3}(\eta)\xleftarrow{f|_{I_{4}(\eta)}}\ldots$

is a subcontinuum of $\hat{I}_{f}$.

######  Remark 4.4.

Since in the rest of the paper it does not matter which inverse limit sequence
$\hat{I}(\eta)$ we choose, by abuse of notation, we speak about general
$\hat{I}(\eta)$ but have in mind that this $\hat{I}(\eta)$ is just one chosen
inverse limit sequence from possibly several choices.

######  Observation 4.5.

By Observation 4.1 $\hat{I}(\eta)$ is a non-degenerate continuum. Since $f$ is
under diagonal it follows $f^{-1}(1)=\\{1\\}$. Thus every interval
$I_{i}(\eta)$ from Definition 4.3 contains point $1$; therefore, we can
compare the intervals $I_{i}(\eta)$ using the inclusion relation.

For an under diagonal map $f$ denote the fixed point of $\hat{f}$ by
$\mathbf{1}:=(1,1,1,\ldots)\in\hat{I}_{f}$. The composant of a point
$x\in\hat{I}_{f}$ is a union of all proper subcontinua of $\hat{I}_{f}$ that
contain point $x$. Denote the composant of $\mathbf{1}$ by
$\mathcal{C}_{\mathbf{1}}$. Next observation follows from Observation 4.1 and
Observation 4.5.

######  Observation 4.6.

The composant $\mathcal{C}_{\mathbf{1}}$ is the union of subcontinua
$\hat{I}(\eta)$ for $\eta\in(0,1)$.

The following two lemmas will be crucial ingredients in the proof of the main
theorems.

######  Lemma 4.7.

Let $f$ be a $0$-attracted interval map. Space $\hat{I}_{f}$ is homeomorphic
to the pseudo-arc if and only if there exists $\eta\in(0,1)$ such that
$\hat{I}(\eta)$ is the pseudo-arc.

###### Proof.

$(\Rightarrow)$ The only if direction is obvious due to Observation 4.1 since
every proper subcontinuum of the pseudo-arc is the pseudo-arc.
$(\Leftarrow)$ For the if direction let us fix $\eta>0$ and $\hat{I}(\eta)$.
First let us assume that for every $x\in(0,1)$, $f(x)\neq 0$. Since $f$ is
$0$-attracted

(1) $x\text{ is }f\text{-attracted to }0$

for every $x\in[0,1)$ and since $\hat{I}(\eta)$ is the pseudo-arc it follows
that for every $m\geq 1$ the inverse limit

$f^{m}(I_{1}(\eta))\xleftarrow{f|_{f^{m-1}(I_{1}(\eta))}}f^{m-1}(I_{1}(\eta))\xleftarrow{f|_{f^{m-2}(I_{1}(\eta))}}\ldots\xleftarrow{f|_{I_{1}(\eta)}}I_{1}(\eta)\xleftarrow{f|_{I_{2}(\eta)}}\ldots$

is the pseudo-arc as well since we can apply homeomorphism
$\hat{f}^{m}|_{\hat{I}(\eta)}$ to $\hat{I}(\eta)$. But then using (1) and the
fact that $f$ is $0$-attracted it follows

(2) $\exists\text{ a sequence }(\eta_{i})^{\infty}_{i=1}\subset[0,1)\text{ so
that }\hat{I}(\eta_{i})\text{ is the pseudo-arc and
}\eta_{i}\xrightarrow{i\to\infty}0.$

By $\Gamma(f)$ we denote the graph of an interval map $f$ and by $d_{H}$ the
Hausdorff distance between sets.

Now fix $\delta>0$. By (2) there exist integers $N,m(N)\geq 1$ such that the
following three properties hold:

  1. (a)

$\eta_{N}<\frac{\delta}{12}$

  2. (b)

$d_{H}(\Gamma(f^{m(N)}),\Gamma(f^{m(N)}|_{I_{1}(\eta_{N})})))<\frac{\delta}{24}$

  3. (c)

$f^{m(N)}(I_{1}(\eta_{N}))$ is $\frac{\delta}{3}$-crooked.

Only (b) from the above properties needs additional explanation. Interval
$I_{1}(\eta_{N})$ is connected and contains point $1$ by the definition. Since
$f$ is continuous and $0$-attracted $f^{m(N)}(I_{1}(\eta_{N}))=[t,1]$ for some
$t\in(0,1)$ and thus the distance between the graphs of maps
$f^{m(N)}|_{I_{1}(\eta_{N})}$ and $f^{m(N)}$ can be chosen to be arbitrary
small. Note also that in (c) we use Proposition 4.2.

Now let us see that $f^{m(N)}$ is $\delta$-crooked. Let us fix $a,b\in I$ and
$c<d\in I$ such that $f^{m(N)}(c)=a$ and $f^{m(N)}(d)=b$. The idea is that
because of (a) and (b) it follows that $f^{m(N)}$ and
$f^{m(N)}|_{I_{1}(\eta_{N})}$ are close enough so that we can use (c) and
applying the $\frac{\delta}{3}$-crookedness of $f^{m(N)}|_{I_{1}(\eta_{N})}$
conclude $\delta$-crookedness of $f$. Let us make this more precise. There
exist $\tilde{a},\tilde{b}\in f^{m(N)}(I_{1}(\eta_{N}))$ and
$\tilde{c},\tilde{d}\in I_{1}(\eta_{N})$ such that by (b)

$|\tilde{a}-a|<\frac{\delta}{24}\text{ and }|\tilde{b}-b|<\frac{\delta}{24},$

and by (a)

$|c-\tilde{c}|<\frac{\delta}{12}\text{ where }c<\tilde{c}\text{ and
}|d-\tilde{d}|<\frac{\delta}{12}\text{ where }\tilde{d}<d$

are such that

$f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c})=\tilde{b}\text{ and
}f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{d})=\tilde{a}.$

By (c) and (b) there exist
$\tilde{c}<\tilde{c}^{\prime}<\tilde{d}^{\prime}<\tilde{d}$ such that

$|f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c}^{\prime})-f^{m(N)}(\tilde{c}^{\prime})|<\frac{\delta}{24}\text{
and
}|f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{d}^{\prime})-f^{m(N)}(\tilde{d^{\prime}})|<\frac{\delta}{24}$

and

$|f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c})-f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{d}^{\prime})|<\frac{\delta}{3}\text{
and
}|f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{d})-f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c}^{\prime})|<\frac{\delta}{3}.$

Since $c<\tilde{c}$ and $\tilde{d}<d$ it follows
$c<\tilde{c^{\prime}}<\tilde{d^{\prime}}<d$. But then applying the above
inequalities

(3)
$\begin{split}|f^{m(N)}(\tilde{c^{\prime}})-f^{m(N)}(d)|=|f^{m(N)}(\tilde{c^{\prime}})-f^{m(N)}(d)+f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{d})\\\
-f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c}^{\prime})-f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{d})+f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c}^{\prime})|\leq|f^{m(N)}(\tilde{c^{\prime}})-\\\
f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c}^{\prime})|+|a-\tilde{a}|+|f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{d})-f^{m(N)}|_{I_{1}(\eta_{N})}(\tilde{c}^{\prime})|<\frac{\delta}{6}+\frac{\delta}{12}+\frac{\delta}{3}<\delta\end{split}$

and similarly

$|f^{m(N)}(\tilde{d^{\prime}})-f^{m(N)}(c)|<\delta.$

This shows that $f$ is crooked.
Note that the above argument also takes into account points $a,b$ that are
possibly in $[0,\eta_{N}]$. Indeed, since $f$ is under diagonal also all
images of $x\in[0,\eta_{N}]$ will be smaller than $\eta_{N}$ and thus this
does not have effect on the crookedness of $f$.

Now assume that there exist $z\in(0,1)$ such that $f(z)=0$ and let $z$ be the
largest in $(0,1)$ for which this holds. Following the preceding proof we
obtain that for any sequence $(\eta_{i})$ in (2) there exists $M>0$ such that
$\eta_{M}<z$. If $N(m)>M$ it is thus enough to require that
$f^{M}(I_{1}(\eta_{M}))$ is $\delta$-crooked (compare with (a)-(c) from the
proof above) which directly implies that $f$ is $\delta$-crooked as well. ∎

######  Lemma 4.8.

Let $f$ be an under diagonal map and $\mathrm{Fix}(f)$ nowhere dense in $I$.
The space $\hat{I}_{f}$ is the pseudo-arc if and only if there exists
$\eta\in(0,1)$ so that $\eta$ is $f$-attracted to $0$ and $\hat{I}(\eta)$ is
the pseudo-arc.

###### Proof.

$(\Leftarrow)$ This direction follows analogously as in the proof of Lemma
4.7. The only difference from Lemma 4.7 is that we take in (2) $f^{i}(\eta)$
for the sequence $(\eta_{i})^{\infty}_{i=1}$.
$(\Rightarrow)$ Assume that for every $\eta\in(0,1)$

  1. (1)

$f^{i}(\eta)\not\to 0$ as $i\to\infty$ or

  2. (2)

$\hat{I}(\eta)$ is not the pseudo-arc.

If (2) holds we get by Observation 4.5 $\hat{I}(\eta)$ is non-degenerate and
thus $\hat{I}_{f}$ is not the pseudo-arc.
Thus we can assume that (1) holds and (2) does not hold. Since $f$ is under
diagonal and for every $x\in I\setminus\mathrm{Fix}(f)$, $f^{i}(x)\downarrow
y\in\mathrm{Fix}(f)$ (actually every sequence $f^{i}(x)$ is decreasing because
map $f$ is under diagonal (even strictly decreasing if
$\operatorname{Orb}(x,f)\cap\mathrm{Fix}(f)=\emptyset$)) there exists
$p(\eta)\in\mathrm{Fix}(f)$ such that $0\neq
p(\eta)=\lim_{i\to\infty}f^{i}(x)$. Indeed, $p(\eta)\in\mathrm{Fix}(f)$ since
otherwise $p(\eta)\neq\lim_{i\to\infty}f^{i}(x)$. Now take

(4) $\begin{split}\xi:=\inf_{\eta\in(0,1)}\\{p(\eta)\in I;\text{
}\hat{I}(\eta)\text{ is the pseudo-arc}\\}\newline =\\\
=\min_{\eta\in(0,1)}\\{p(\eta)\in I;\text{ }\hat{I}(\eta)\text{ is the pseudo-
arc}\\}.\end{split}$

The last equality holds since $\mathrm{Fix}(f)$ is closed. Since (1) holds we
obtain $\xi>0$. Also $f(\xi)=\xi$ since otherwise $\xi$ would not be the
minimum as $f$ is under diagonal. Thus, summing up the above and since $f$ is
an under diagonal map we obtain

$\hat{I}_{f}=\underleftarrow{\lim}([0,\xi],f|_{[0,\xi]})\cup\underleftarrow{\lim}([\xi,1],f|_{[\xi,1]}).$

Therefore, $\hat{I}_{f}$ is decomposable and thus not the pseudo-arc. ∎

######  Theorem 4.1.

Let $S$ be a non-degenerate closed nowhere dense set in $I$. There exists a
crooked under diagonal interval map $f$ with $\mathrm{Fix}(f)=S\cup\\{0,1\\}$
such that $0,1\notin S$.

###### Proof.

We define $f$ in the following way. First let $f|_{[1/2,1]}=f_{H}|_{[1/2,1]}$,
thus $f(1/2)=1/4$ and let $f(3/8)=0$, $f(1/4)=1/4$ and $f|_{[1/4,1/2]}$ be a
piecewise linear map with two pieces of monotonicity on the interval
$[3/8,1/2]$. Let $f|_{[0,1/4]}$ be chosen so that
$\mathrm{Fix}(f|_{(0,1/4]})=S$ and for $x\in(0,1/4]\setminus S$ let $f(x)<x$.
Now we apply Lemma 4.8 by taking $\eta=\frac{\sqrt{3}}{2\sqrt{2}}$ which
finishes the proof. ∎

Since we have uncountably many non-homeomorphic closed nowhere dense sets in
$I$ we obtain the following.

######  Corollary 4.9.

There exist uncountably many topologically non-conjugated under diagonal
crooked maps with pairwise different sets of fixed points.

We will only implicitly use the well known (standard) definition of
topological entropy for compact metric spaces from [1, 9] and thus we will not
define it here.

######  Observation 4.10.

Under diagonal and above diagonal interval maps have topological entropy $0$.

Therefore, Corollary 4.9 and Theorem 4.2 imply the following two statements.

######  Corollary 4.11.

There exists an uncountable set of crooked interval maps $\mathcal{T}\subset
C(I)$ with topological entropy $0$ such that any two different
$f,g\in\mathcal{T}$ are not topologically conjugate.

A question that remains to be answered is whether there are uncountably many
pairwise non-conjugated maps that have the same structure of fixed points as
the Henderson’s map $f_{H}$, i.e. $0$-attracted maps.

We call $f\in C(I)$ a countably strictly monotone map if it has countably
infinitely many strict critical points.

######  Definition 4.12.

Let $f\in C(I)$ be a countably piecewise strictly monotone map and let
$\mathcal{D}_{f}=\left\\{\left[r_{k},s_{k}\right]\mid
k\in\mathbb{N}\right\\},$ i.e., for all positive integers $k$ and $\ell$, if
$k\neq\ell$ then
$\left[r_{k},s_{k}\right]\cap\left[r_{\ell},s_{\ell}\right]=\emptyset$. We
define $\mathcal{A}(f)$ to be the set of all points $t\in[0,1]$ for which
there is a convergent subsequence
$\left(\left[r_{i_{k}},s_{i_{k}}\right]\right)$ of the sequence
$\left(\left[r_{k},s_{k}\right]\right)$ in the Hausdorff metric, such that

$\lim_{k\rightarrow\infty}\left[r_{i_{k}},s_{i_{k}}\right]=\\{t\\}.$

We call points in $\mathcal{A}(f)$ the accumulation points of $f$.

######  Observation 4.13.

Let $f,g\in C(I)$ be two countably piecewise strictly monotone functions. If
$f$ and $g$ are topologically conjugate and $\varphi$ : $I\rightarrow I$ is a
homeomorphism such that $f=\varphi^{-1}\circ g\circ\varphi$, then

$\mathcal{A}(g)=\\{\varphi(t)\mid t\in\mathcal{A}(f)\\}.$

In particular, $|\mathcal{A}(g)|=|\mathcal{A}(f)|$.

######  Theorem 4.2.

There exists an uncountable set of crooked $0$-attracted interval maps
$\mathcal{T}\subset C(I)$ such that any two different $f,g\in\mathcal{T}$ are
not topologically conjugate.

###### Proof.

We will show that there are uncountably many non-conjugate maps such that
$f|_{[0,1/2]}$ with $f(0)=0$, $f(1/2)=1/4$ and $f(x)<x$ for $x\in(0,1/2)$ and
$f|_{[1/2,1]}=f_{H}|_{[1/2,1]}$. By Lemma 4.7 such $f$ is crooked so we have
complete freedom to choose $f|_{[0,1/2]}$ as long as $f(x)<x$ for all
$x\in(0,1/2]$. Let $f|_{[0,1/2]}$ have $n$ critical points. We have a choice
to make each strict critical point an accumulation point or not and since
conjugacy of a $0$-attracted map needs to preserve $0$ it also needs to
preserve ordering of accumulation points. Accumulation points are preserved
under the conjugacy by Observation 4.13. In such a way we get countably
(varying the number of strict critical points) over countably (by adding
accumulation points) many pairwise non-conjugate $0$-attracted choices to
construct map $f$. ∎

######  Corollary 4.14.

There exists uncountably many pairwise non-conjugated crooked maps with
topological entropy $0$ and exactly two fixed points.

We could perform a construction similar to the one in Theorem 4.2 for any
under diagonal map with a nowhere dense set of fixed points and obtain the
following theorem.

######  Theorem 4.3.

Let $S$ be a non-degenerate closed nowhere dense set in $I$. There exist
uncoutably many pairwise non-conjugate under diagonal crooked maps $f$ with
$\mathrm{Fix}(f)=S\cup\\{0,1\\}$ such that $0,1\notin S$.

######  Definition 4.15.

Let $f:I\to I$ be an above diagonal map and let $\eta\in(0,1)$. Define by
$I^{\prime}_{i}(\eta)$ a connected component of $f^{-i}([0,\eta])$. Denote a
fixed point of $\hat{f}$ by $\mathbf{0}:=(0,0,0,\ldots)\in\hat{I}_{f}$ and the
composant of $\mathbf{0}$ by $\mathcal{C}_{\mathbf{0}}$.

######  Remark 4.16.

Let $f$ be an above diagonal interval map. Note that $\varphi:I\to I$ defined
by $\varphi(x)=1-x$ for every $x\in I$ conjugates $f$ to a map $g\in
C_{ud}(I)$, i.e., $\varphi^{-1}\circ f\circ\varphi\in C_{ud}(I)$. Thus,
$\varphi$ is actually a homeomorphism of $C_{ud}(I)$ to $C_{ad}(I)$.
Therefore, the results from the previous section follow analogously for the
set $C_{ad}(I)$ if we replace $\hat{I}(\eta)$ with similarly defined
$\hat{I}^{\prime}(\eta)$ and the role of ${\bf 1}$ and $\mathcal{C}_{\bf 1}$
by ${\bf 0}$ and $\mathcal{C}_{\bf 0}$ respectively.

Thus we have the following theorem.

######  Theorem 4.4.

Map $f$ is crooked and under diagonal or above diagonal interval map if and
only if $\mathrm{Fix}(f)$ is nowhere dense in $I$ and

  1. (1)

either there exists $\eta\in(0,1)$ such that $\hat{I}(\eta)$ is the pseudo-arc
and $\eta$ is $f$-attracted to $0$ or

  2. (2)

there exists $\eta\in(0,1)$ such that $\hat{I}^{\prime}(\eta)$ is the pseudo-
arc and $\eta$ is $f$-attracted to $1$.

###### Proof.

The proof of this theorem follows from Lemma 4.8 and Remark 4.16 if we prove
that provided $\mathrm{Fix}(f)$ is dense somewhere in $I$, then $\hat{I}_{f}$
is not the pseudo-arc. Say $\mathrm{Fix}(f)$ is dense somewhere in $I$, denote
that set by $A\subset I$. Since $f$ is continuous, the closure
$\overline{A}\subset\mathrm{Fix}(f)$. Thus there exists an open interval
$U\subset A$. Fix a non-degenerate closed interval $J\subset U$. Inverse limit
$\underleftarrow{\lim}(J,f|_{J})\subset\hat{I}_{f}$ is an arc which finishes
the proof. ∎

##  5\. Acknowledgments

I would like to thank Ana Anušić, Iztok Banič and Piotr Oprocha for remarks
that helped improve the exposition of the paper. J. Činč was partially
supported by the Slovenian research agency ARRS grant J1-4632 and by European
Union’s Horizon Europe Marie Skłodowska-Curie grant HE-MSCA-PF- PFSAIL -
101063512.

|  This research is part of a project that has received funding from the
European Union’s Horizon Europe research and innovation programme under the
Marie Skłodowska-Curie grant agreement No 101063512.
---|---

## References

  * [1] R.L. Adler, A.G. Konheim, and M.H. McAndrew, Topological entropy, Transactions of the American Mathematical Society 114 (1965) 309–319.
  * [2] A. Anušić, J. Činč, Inhomogeneities in chainable continua, Fundamenta Mathematicae 254, (2021). (Appendix A written by Henk Bruin.)
  * [3] M. Barge, J. Martin, Construction of global attractors, Proc. Am. Math. Soc. 110 (1990), 523–525.
  * [4] R. H. Bing, A homogeneous indecomposable plane continuum, Duke Math. J. 15 (1948), 729–742.
  * [5] R. H. Bing, Concerning hereditarily indecomposable continua, Pacific J . Math. 1 (1951), 43–51.
  * [6] L. Block, J. Keesling, J., V. V. Uspenskij, Inverse limits which are the pseudoarc. Houston J. Math. 26 (2000), no. 4, 629–638.
  * [7] J. Bobok,; J., S. Troubetzkoy, Typical properties of interval maps preserving the Lebesgue measure. Nonlinearity 33 (2020), no. 12, 6461–6479.
  * [8] J. Bobok,; J. Činč, P. Oprocha, S. Troubetzkoy, Periodic points and shadowing for generic Lebesgue measure-preserving interval maps. Nonlinearity 35 (2022), no. 5, 2534–2557.
  * [9] R. Bowen, Entropy for group endomorphisms and homogeneous spaces, Trans. Amer. Math. Soc. 153 (1971), 401–414.
  * [10] J. Činč, P. Oprocha, Parametrized family of pseudo-arc attractors: physical measures and prime end rotations, Proc. Lond. Math. Soc. (3) 125 (2022), 318–357.
  * [11] U. B. Darji, Udayan, H. Kato Chaos and indecomposability, Adv. Math. 304 (2017), 793–808.
  * [12] Drwięga, T., Oprocha, P., Topologically mixing maps and the pseudoarc, Ukraïn. Mat. Zh. 66 (2014), no. 2, 176–186.
  * [13] S. Greenwood, S. Štimac A characterization of a map whose inverse limit is an arc. Ergodic Theory Dynam. Systems 42 (2022), no. 8, 2533–2549.
  * [14] G. W. Henderson, The pseudo-arc as an inverse limit with one binding map. Duke Math. J. 31(1964), 421–425.
  * [15] J. Krasinkiewicz, P. Minc, Mappings onto indecomposable continua Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.25 (1977), no.7, 675–680.
  * [16] W. Lewis, P. Minc, Drawing the pseudo-arc Houston J. Math.36 (2010), no.3, 905–934.
  * [17] C. Mouron, Entropy of shift maps of the pseudo-arcs, Top. Appl. 159 (2012) 34–39.


# Can Language Models perform Abductive Commonsense Reasoning?

Seungone Kim
Yonsei University, Department of Computer Science
<EMAIL_ADDRESS>

###### Abstract

Abductive Reasoning is a task of inferring the most plausible hypothesis given
a set of observations. In literature, the community has approached to solve
this challenge by classifying/generating a likely hypothesis that does not
contradict with a past observation and future observation. Some of the most
well known benchmarks that tackle this problem are aNLI and aNLG (pronounced
as alpha-NLI and alpha-NLG). In this report, I review over some of the
methodologies that were attempted to solve this challenge, re-implement the
baseline models, and analyze some of the weaknesses that current approaches
have. The code and the re-implemented results are available at this
link111https://github.com/SeungoneKim/abductive-commonsense-reasoning.

##  1 Introduction

Reasoning can be divided into three different categories; (1) Abduction is a
process of both generating hypotheses and selecting some for further pursuit;
(2) Deduction draws out their testable consequences; (3) Induction evaluates
them (Kapitan, 1992). People unconsciously and constantly perform these three
different types of reasoning within daily lives. Reasoning allows us to be
intelligent coupled with abstraction capabilities (Chollet, 2019). In order to
accomplish the grand goal of building Artificial General Intelligence(AGI),
reasoning is one of the biggest obstacles that must be fully understood, but
there is less progress made.

Within the research community, there has been various attempts to build
systems that could mimic the reasoning capabilities a human might have. More
specifically, researchers have paid a lot of attention to Commonsense
Reasoning, a field that deals with knowledge and inferences that we encounter
in everyday situations. Different line of works tried to build benchmarks that
test whether a system posses a particular commonsense reasoning type (Qin et
al., 2019; Zhang et al., 2020; Bisk et al., 2020; Sap et al., 2019; Zellers et
al., 2019; Zhou et al., 2019; Talmor et al., 2019). Others tried to build
methodologies that are efficient in solving these tasks (Klein and Nabi, 2019;
Wang et al., 2020; Rajani et al., 2019; Majumder et al., 2020).

ARI is a large-scale benchmark dataset that specifically tackles abductive
commonsense reasoning (Bhagavatula et al., 2019). In this setting, two text
inputs are given; (1) a observation that is made in the past; (2) a
observation that is made in the future. Given the input, the goal of aNLI task
is to classify a more plausible hypothesis that might have occurred between
the past - future observations given two candidate hypotheses, while the goal
of aNLG is to generate this hypothesis. For example, when a person locked up
all the windows and doors before leaving the house and observed that the house
was set open with all the furniture broken, it is more likely that a thief
might have stole from his/her house instead of a bird flying through the house
and making a mess.

Generating a good hypothesis is considered more challenging than selecting a
better hypothesis since it tests the model has to generate a plausible text
output based on the commonsense knowledge it has and map with with the given
observations. It could be viewed of a more general form of abductive
reasoning. Among the two tasks, I focus on the generative task (aNLG), in this
report.

##  2 Related Works and Methods

###  2.1 Baseline Model

As a baseline model, Bhagavatula et al. (2019) proposed a model that
conditionally generates by simply concatenating the past observation and
future observation back and forth, and divide it with special tokens <o1>,
</o1>, <o2>, </o2>. The loss is formalized as a negative log-likelihood as in
a typical text generation setting.

$\mbox{${\cal L}$}=-\sum_{i=1}^{N}\log
P(w_{i}^{h}|w_{<i}^{h},w_{1}^{o1}...w_{m}^{o1},w_{1}^{o2}...w_{n}^{o2})$ (1)

In this report, I re-implemented the inference procedure using this model and
compare with the reported scores of Bhagavatula et al. (2019).

###  2.2 Using a Commonsense Inference Model for assistance

Bhagavatula et al. (2019) proposed another model that conditions on an
additional background knowledge ${\cal K}$. Specifically, the authors used a
commonsense knowledge inference model COMET (Bosselut et al., 2019). COMET is
a transformer-based model that generates a commonsense inference when a
narrative text and its corresponding relation (e.g., xWant, xNeed, xIntent) is
given. With an additional background knowledge ${\cal K}$, the loss can be
formalized as follows.

$\begin{split}\mbox{${\cal L}$}=-\sum_{i=1}^{N}\log
P(w_{i}^{h}|w_{<i}^{h},w_{1}^{o1}...w_{m}^{o1},\\\
w_{1}^{o2}...w_{n}^{o2},{\cal K})\end{split}$ (2)

The additional commonsense knowledge can be provided in 2 different methods.
First, the text output of the commonsense knowledge can explicitly be provided
as additional input where the text generation model can potentially use it to
generate a plausible hypothesis. Second, the COMET embedding output of the
commonsense inferences can be given as additional input by concatenating with
the token embedding of the observations. Bhagavatula et al. (2019) use a
setting of appending eighteen additional embeddings (corresponding to nine
relations for each observation) and explains that this allows the model to
learn each token’s representation while attending to the COMET embeddings to
effectively integrate background commonsense knowledge into a language model.

In this report, I re-implemented the inference procedure using this model and
compare with the reported scores of Bhagavatula et al. (2019).

###  2.3 Enhanced Decoding Methods

The approach of finetuning a Pre-trained Language Model on a particular task
has gained success in different subfields within Natural Language Processing.
However, supervised approaches still perform considerably worse than humans
and are subject to developing superficial strategies such as repeatedly
generating the same phrase or memorizing prevalent surface patterns specific
in the dataset. A number of research tackles this problem and come up with
some advanced form of text decoding methods to alleviate this problem.

Qin et al. (2020) proposed a decoding method, DELOREAN that is suitable for
abductive reasoning and counter-factual reasoning. Instead of simply
concatenating the past and future observations when they are given as input
like Equation 1, 2, DELOREAN generates the hypothesis based only on the past
observation. Then, by conditioning on the past observation and the hypothesis
candidate, the model generates a plausible future observation. Note that while
there is a ground truth future observation, a new future observation is
additionally generated. The cross entropy loss between the existing future
observation and the newly generated future observation is used to compute the
gradients of the hypothesis using backpropagtion algorithm. Lastly, the model
samples possible tokens step-by-step using both the logits of the forward pass
and the backward pass. Therefore, DELOREAN isa backprop-based decoding
algorithm.

More recently, Qin et al. (2022) proposed a different decoding algorithm, COLD
which is designed for abductive reasoning, counter-factual reasoning, and
constrained reasoning. COLD treats text generation as sampling from an energy-
based distribution (Hinton, 2002; LeCun et al., 2006), which allows flexibly
composing constraints based on the task at hand. It uses Langevin dynamics
which is capable of mapping continuous sample into discrete, fluent text. It
uses the gradient of the energy function which can specifically be designed
based on the constraints that exist in the underlying task on-the-fly without
the need of fine-tuning.

In this report, I did not re-implemented this methods, but compare with the
reported scores of Qin et al. (2020, 2022).

| aNLG
---|---
Model | Bleu-4 | METEOR | ROUGE-L | Cider | Bert-score
GPT2 (unsupervised) (Bhagavatula et al., 2019) | 0.00 | 9.29 | 9.99 | 3.34 | 36.69
GPT2 + DELOREAN (unsupervised) (Qin et al., 2020) | 1.60 | / | 19.06 | 7.88 | 41.74
GPT2 + COLD (unsupervised) (Qin et al., 2022) | 1.79 | / | 19.50 | 10.68 | 42.67
GPT2 (supervised) (Bhagavatula et al., 2019) | 2.23 | 16.71 | 22.83 | 33.54 | 48.74
GPT2 (supervised; re-implemented) | 3.06 | 18.61 | 24.49 | 33.42 | 48.70
GPT2 + COMET-txt (Bhagavatula et al., 2019) | 2.29 | 16.73 | 22.51 | 31.99 | 48.46
GPT2 + COMET-txt (re-implemented) | 3.13 | 18.63 | 24.50 | 32.66 | 48.50
GPT2 + COMET-emb (Bhagavatula et al., 2019) | 3.03 | 17.66 | 22.93 | 32.00 | 48.52
GPT2 + COMET-emb (re-implemented) | 4.13 | 19.87 | 23.81 | 30.86 | 48.32
Table 1: Automatic evaluation on aNLG benchmark in terms of different metrics

##  3 Details of re-Implementation

I have used the implementation222https://github.com/allenai/abductive-
commonsense-reasoning provided by AllenAI to reproduce the results and test
the fine-tuned models.

I have used GPT-2 XL, a 1.5B parameter model as a baseline model for the re-
implementation. The inference procedure uses beam-search based decoding with
temperature of 1.0, top_p value of 0.9. For COMET-text and COMET-emb based
models, the COMET relation oEffect, oReact, oWant, xAttr, xEffect, xIntent,
xNeed, xReact, xWant were used. More details of the fine-tuning procedure is
presented in Bhagavatula et al. (2019).

##  4 Evaluation of re-Implementation

The results of the re-implemented versions and the scores reported in each
corresponding papers are shown in Table 1. Since it is not fair to directly
compare supervised approaches and unsupervised approaches, we should compare
independently.

Using Enhanced decoding approaches show a significant amount of better
performance in ROUGE-L and Cider metric, gaining more than twice better
performance. However, its performance is still not comparable with fine-tuning
methods implying that improving decoding strategies itself could not be a
substitute fine-tuning yet. This result addresses open-questions to whether a
prominent strategy could be used in abductive reasoning instead of the current
fine-tuning approaches in future works.

Comparing the re-implemented version and the reported scores of the supervised
methods, the re-implemented versions achieved better scores in 11 out of 15.
This proves that my re-implementation of inferencing on fine-tuned methods was
successful. Also, comparing the scores between different approaches, the
methods that reached the highest scores among different metrics differs
implying that using COMET text or embedding isn’t very effective compared to
the baseline model. This also opens room of future research of how we could
inject additional knowledge for abductive reasoning.

##  5 Analysis on Failure Cases

In this section, we look at the failure cases each unsupervised and supervised
methods made in solving the aNLG task. Some of the failure cases are presented
in Table 2.

Past Observation |  Future Observation
---|---
I really love to play video games. |  |  I couldn’t play video games until I bought a new one.
Answer Hypothesis |
Sadly my playstation broke after a flood. |
GPT2 (supervised) |
I had to quit playing my favorite video games after a week. |
GPT2 + COMET-txt |
I had to order new games from my local game store. |
GPT2 + COMET-emb |
I had a cracked computer. |
Amy had a roommate named Sue. |  |  They didn’t speak to each other for weeks.
Answer Hypothesis |
Sue was very messy. |
GPT2 (supervised) |
Amy asked Sue to come to class on time. |
GPT2 + COMET-txt |
Amy asked Sue to come to work on time, but she arrived late. |
GPT2 + COMET-emb |
Sue had to go to work on time. |
Sam always wanted to save up and buy a computer. |  |  Sam was devastated when he came home to an empty box.
Answer Hypothesis |
The computer was delivered on the front porch. |
GPT2 (supervised) |
Sam didn’t save enough money for the computer. |
GPT2 + COMET-txt |
Sam didn’t save enough money. |
GPT2 + COMET-emb |
Sam didn’t save up enough money to but one. |
In Fort Worth, we have an event call hit the bricks. |  |  However, thanks to my training the run was easy.
Answer Hypothesis |
We had to run several miles. |
GPT2 (supervised) |
I trained myself for the run. |
GPT2 + COMET-txt |
I trained myself to run very fast. |
GPT2 + COMET-emb |
I took a deep learning class to teach myself how to run. |
Nikki wanted candy. |  |  Nikki was very mad at her mother.
Answer Hypothesis |
Her mother wouldn’t buy candy because it’s bad for Nikki’s teeth. |
GPT2 (supervised) |
Nikki got candy from her mom. |
GPT2 + COMET-txt |
Nikki got out of the deli. |
GPT2 + COMET-emb |
She went to the store for some candy. |
The cat sunned itself where the light passed through the window. |  |  The cat slept there fore the next two hours.
Answer Hypothesis |
The cat made it self comfortable in the sunlight. |
GPT2 (supervised) |
The cat was sleeping in a shady spot. |
GPT2 + COMET-txt |
The cat was sleeping in a hard pile. |
GPT2 + COMET-emb |
The cat always woke up in the dark. |
Table 2: Failure examples of generated hypotheses from GPT2 and its variants

###  5.1 Language Models do not capture the Causal Relationship between events

Majority cases of Language Models failing to capture the Causal Relationship
between events were found. For example, given a past observation such that
’Sam always wanted to save up and buy a computer’ and a future observation
such that ’Sam was devastated when he came home to an empty box’, we could
easily suspect that Sam saved money, bought a computer, but he was scammed and
got an empty box. The reasoning chain requires 4 hops in total which is very
challenging for a Language Model to learn. Therefore, GPT2, GPT2 + COMET-txt,
GPT2 + COMET-emb all generated a hypothesis that ’Sam didn’t save enough
money’.

In order to overcome this issue, it is likely that more advanced learning
methods that could incorporate causal reasoning should be developed. Simply
showing the answer hypothesis is not enough to enforce the model to learn the
mapping patterns because it is well known that Deep Learning methods are
likely to learn the shortcuts (Geirhos et al., 2020). Although increasing the
model size and data size is the top-trend within the community of Natural
Language Processing (Brown et al., 2020), there is room of improvement that
could be accomplished by establishing reasoning based learning methods (Luo et
al., 2020). Simply adding the text outputs or embeddings of commonsense
inference models did not resolve the issue of enforcing the model to capture
the causal relationships.

###  5.2 Language Models are weak in Negation Logic

Negation is an important property in many language understanding tasks, such
as sentiment analysis, question answering, knowledge base completion and
natural language inference (Hosseini et al., 2021). However, a number of
examples generated by GPT2 did not seem to capture the crucial negation logic
between the past and future observations. For example, given a past
observation such that ’Nikki wanted candy’ and a future observation such that
’Nikki was very mad at her mother’, we could conjecture that Nikki did not get
candy from her mother. However, all of the generated results included the
information that Nikki got candy from her mother.

I conjecture there are two possible reasons why GPT2 did not successfully
generate an plausible hypothesis. First, it did not understand that in order
for Nikki to be angry at her mother, she wouldn’t have got what she wanted.
This means that the model was unable to capture the negation logic in a social
situation. Second, the model might not have the commonsense knowledge to
inference the hypothesis. If the model possessed commonsense knowledge that
mothers typically do not give candy to their children, it is more likely to
have generated a more acceptable result.

###  5.3 Language Models generate open-bounded results in Open-Domain Tasks

The ability to control the generation results is crucial in open-domain
settings. There were various methods developed to control the desired output
in response generation (Yang et al., ) and text-generation (Keskar et al.,
2019; Dathathri et al., 2019). In abductive commonsense reasoning, the scope
of possible outputs is very large, and I observed a lot of cases where the
model generates a awkward output. For example, given a past observation such
that ’Amy had a roommate named Sue’ and a future observation such that ’They
didn’t speak to each other for weeks’ it is likely that some part of Sue upset
Amy or vice versa. However, the result in which GPT2 generated is that Amy or
Sue did not come to work in time. Although it is possible that Amy and Sue
might also be coworkers, a more appropriate answer should be constrained into
an event that might have happened inside their room. The models did not
generate a similar output to the answer which is ’Sue was very messy’.

##  6 Conclusion

In this report, I have summarized a novel commonsense reasoning task of
abductive reasoning. I explained some of the state-of-the-art methodologies in
solving the task and re-implemented the supervised methods and measured their
scores in terms of automatic evaluation metrics. I have analyzed some of the
weaknesses by introducing some failure cases and suggested how the community
could develop more advanced learning methods to make models that could perform
abductive reasoning. I have included the code I have used for re-
implementation in the report.

## Acknowledgements

This report is submitted to the final project of BigData course(CSI4121.01) of
Yonsei University. All the experiment code and report was written by the
author.

## References

  * Bhagavatula et al. (2019) Chandra Bhagavatula, Ronan Le Bras, Chaitanya Malaviya, Keisuke Sakaguchi, Ari Holtzman, Hannah Rashkin, Doug Downey, Scott Wen-tau Yih, and Yejin Choi. 2019\.  Abductive commonsense reasoning.  _arXiv preprint arXiv:1908.05739_.
  * Bisk et al. (2020) Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. 2020.  Piqa: Reasoning about physical commonsense in natural language.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 7432–7439.
  * Bosselut et al. (2019) Antoine Bosselut, Hannah Rashkin, Maarten Sap, Chaitanya Malaviya, Asli Celikyilmaz, and Yejin Choi. 2019.  Comet: Commonsense transformers for automatic knowledge graph construction.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4762–4779.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Chollet (2019) François Chollet. 2019.  On the measure of intelligence.  _arXiv preprint arXiv:1911.01547_.
  * Dathathri et al. (2019) Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. 2019.  Plug and play language models: A simple approach to controlled text generation.  _arXiv preprint arXiv:1912.02164_.
  * Geirhos et al. (2020) Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. 2020.  Shortcut learning in deep neural networks.  _Nature Machine Intelligence_ , 2(11):665–673.
  * Hinton (2002) Geoffrey E Hinton. 2002.  Training products of experts by minimizing contrastive divergence.  _Neural computation_ , 14(8):1771–1800.
  * Hosseini et al. (2021) Arian Hosseini, Siva Reddy, Dzmitry Bahdanau, R Devon Hjelm, Alessandro Sordoni, and Aaron Courville. 2021.  Understanding by understanding not: Modeling negation in language models.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1301–1312.
  * Kapitan (1992) Tomis Kapitan. 1992.  Peirce and the autonomy of abductive reasoning.  _Erkenntnis_ , 37(1):1–26.
  * Keskar et al. (2019) Nitish Shirish Keskar, Bryan McCann, Lav R Varshney, Caiming Xiong, and Richard Socher. 2019.  Ctrl: A conditional transformer language model for controllable generation.  _arXiv preprint arXiv:1909.05858_.
  * Klein and Nabi (2019) Tassilo Klein and Moin Nabi. 2019.  Attention is (not) all you need for commonsense reasoning.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4831–4836.
  * LeCun et al. (2006) Yann LeCun, S Chopra, R Hadsell, M Ranzato, and F Huang. 2006.  Predicting structured data.  _A tutorial on energy-based learning. MIT Press, Cambridge_.
  * Luo et al. (2020) Yunan Luo, Jian Peng, and Jianzhu Ma. 2020.  When causal inference meets deep learning.  _Nature Machine Intelligence_ , 2(8):426–427.
  * Majumder et al. (2020) Bodhisattwa Prasad Majumder, Harsh Jhamtani, Taylor Berg-Kirkpatrick, and Julian McAuley. 2020.  Like hiking? you probably enjoy nature: Persona-grounded dialog with commonsense expansions.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9194–9206.
  * Qin et al. (2019) Lianhui Qin, Antoine Bosselut, Ari Holtzman, Chandra Bhagavatula, Elizabeth Clark, and Yejin Choi. 2019.  Counterfactual story reasoning and generation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5043–5053.
  * Qin et al. (2020) Lianhui Qin, Vered Shwartz, Peter West, Chandra Bhagavatula, Jena D Hwang, Ronan Le Bras, Antoine Bosselut, and Yejin Choi. 2020.  Back to the future: Unsupervised backprop-based decoding for counterfactual and abductive commonsense reasoning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 794–805.
  * Qin et al. (2022) Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. 2022.  Cold decoding: Energy-based constrained text generation with langevin dynamics.  _arXiv preprint arXiv:2202.11705_.
  * Rajani et al. (2019) Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher. 2019.  Explain yourself! leveraging language models for commonsense reasoning.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4932–4942.
  * Sap et al. (2019) Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi. 2019.  Social iqa: Commonsense reasoning about social interactions.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4463–4473.
  * Talmor et al. (2019) Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019.  Commonsenseqa: A question answering challenge targeting commonsense knowledge.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4149–4158.
  * Wang et al. (2020) Peifeng Wang, Nanyun Peng, Filip Ilievski, Pedro Szekely, and Xiang Ren. 2020.  Connecting the dots: A knowledgeable path generator for commonsense question answering.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 4129–4140.
  * (23) Haiqin Yang, Xiaoyuan Yao, Yiqun Duan, Jianping Shen, Jie Zhong, and Kun Zhang.  Progressive open-domain response generation with multiple controllable attributes.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019.  Hellaswag: Can a machine really finish your sentence?  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4791–4800.
  * Zhang et al. (2020) Hongming Zhang, Xinran Zhao, and Yangqiu Song. 2020.  Winowhy: A deep diagnosis of essential commonsense knowledge for answering winograd schema challenge.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5736–5745.
  * Zhou et al. (2019) Ben Zhou, Daniel Khashabi, Qiang Ning, and Dan Roth. 2019.  “going on a vacation” takes longer than “going for a walk”: A study of temporal commonsense understanding.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3363–3369.