# Natural Deduction for Assertibility and Deniability††thanks: This paper is
an outcome of the project Logical Structure of Information Channels, no.
21-23610M, supported by the Czech Science Foundation and realized at the
Institute of Philosophy of the Czech Academy of Sciences.

Vít Punčochář Institute of Philosophy,
Czech Academy of Sciences,
Czech Republic<EMAIL_ADDRESS>Institute of Philosophy,
Czech Academy of Sciences,
Czech Republic Berta Grimau Institute of Philosophy,
Czech Academy of Sciences,
Czech Republic<EMAIL_ADDRESS>
###### Abstract

In this paper we split every basic propositional connective into two versions,
one is called extensional and the other one intensional. The extensional
connectives are semantically characterized by standard truth conditions that
are relative to possible worlds. Assertibility and deniability of sentences
built out of atomic sentences by extensional connectives are defined in terms
of the notion of truth. The intensional connectives are characterized directly
by assertibility and deniability conditions without the notion of truth. We
pay special attention to the deniability condition for intensional
implication. We characterize the logic of this mixed language by a system of
natural deduction that sheds some light on the inferential behaviour of these
two kinds of connectives and on the way they can interact.

##  1 Introduction

Christopher Gauker, in his book [5], put forward an interesting theory of
conditionals based on the notions of assertibility and deniability in a
context. A simplification of Gauker’s theory was proposed in [9] where it was
shown that the characteristic features of the logic determined by Gauker’s
semantics are preserved even if we replace Gauker’s rather complex notion of
context with a much simpler one, according to which contexts are represented
by sets of possible worlds. Besides simplicity the proposed modification has
some further nice properties that the original Gauker’s theory lacks,
concerning a simple form of compositionality, validity of some plausible
argument forms, or simple treatment of conditionals embedded in antecedents of
other conditionals (for more details, see [9]).

A peculiar feature of Gauker’s theory is that it reflects one rather
surprising phenomenon: Logical operators are sensitive to the types of
sentences they are applied to. For example, disjunction of two conditional
sentences seems to behave differently than disjunction of two elementary
sentences. The original semantics from [5] incorporates this ambiguity
directly into the formal language. This approach was further elaborated,
especially from the philosophical point of view, in [10]. The semantics from
[9] is designed in a different way. It disambiguates the behaviour of logical
connectives at the level of the formal language by replacing each connective
with two operators, one “extensional” and one “intensional”. It is argued in
[9] that while the original Gauker’s approach allows us to model some
phenomena in a straightforward way, it is technically less elegant than the
disambiguation strategy.

In this paper, we will focus on the semantics of extensional and intensional
connectives proposed in [9] and we will study the logic determined by this
framework. Let us call it the Logic of Assertibility and Deniability, or LAD,
for short. [9] provided a syntactic characterization of LAD, but only an
indirect one, via a translation into a modal logic. The main contribution of
this paper is a direct syntactic characterization of LAD. We will show that
this logic can be characterized by an elegant system of natural deduction that
clarifies the inferential behaviour of both extensional and intensional
operators.

##  2 Extensional and intensional connectives

Consider the following scenario. A murder has been committed and we have four
suspects. The murderer is not known but it is settled that it must be someone
among these suspects. It is also clear that only one person has committed the
crime. We have the following description of the suspects:

tall man with dark hair and moustache | tall man with blond hair and without moustache
---|---
short man with blond hair and moustache | short man with dark hair and without moustache

Now it seems that in this context one is entitled to assert the premises but
not the conclusion of the following argument that has a seemingly valid form:

Premise 1 | The murderer is either tall or short.
---|---
Premise 2 | If the murderer is tall then he has a moustache if he has dark hair.
Premise 3 | If the murderer is short then he has a moustache if he has blond hair.
Conclusion | It either holds that the murderer has a moustache if he has dark hair
| or that the murderer has a moustache if he has blond hair.

The assertibility of the premisses is clear from the description of the
context. But the conclusion does not seem to be assertible. As a reason for
this intuition one might say that none of the two disjuncts in the conclusion
is assertible in the context. But the same holds for the first premise, none
of the disjuncts is assertible in the context and yet the whole disjunction
clearly is. This puzzling phenomenon illustrates what we vaguely described in
the introduction as the sensitivity of logical operators. The first premise
says that in each possibility (“possible world”), one of the disjuncts is
true. The disjunction connecting two conditionals in the conclusion says
something different, namely that at least one of the two conditionals holds
with respect to the whole context. We can describe these two cases as
involving two different logical operators, one operating on the level of
possible worlds and the other operating on the level of the whole context. One
can easily formulate similar examples that involve negation of conditionals
(see [9]). For a discussion of similar phenomena, see, e.g. [12] or [2].

Such examples motivate splitting each of the basic logical connectives
(implication, conjunction, disjunction, and negation) into two versions, one
will be called “extensional” and the other one “intensional”:

Extensional connectives: | $\supset$ | $\cap$ | $\cup$ | $\sim$
---|---|---|---|---
Intensional connectives: | $\rightarrow$ | $\and$ | $\vee$ | $\neg$

Let $L$ be the language containing all atomic formulas and all formulas which
can be constructed out of the atomic formulas using the extensional
connectives. The language $L^{*}$ is the smallest set of formulas containing
all $L$-formulas and closed under the application of the intensional
connectives. The two languages can be concisely introduced as follows:

$L$: | $\alpha=p\mid\alpha\supset\alpha\mid\alpha\cap\alpha\mid\alpha\cup\alpha\mid{\sim}\alpha$
---|---
$L^{*}$: | $\varphi=\alpha\mid\varphi\rightarrow\varphi\mid\varphi\and\varphi\mid\varphi\vee\varphi\mid\neg\varphi$

The argument above would be formalized in the language $L^{*}$ in the
following way (note that the language forbids us from connecting two
intensional implications by the extensional disjunction):

$p\cup q,p\rightarrow(r\rightarrow t),q\rightarrow(s\rightarrow
t)/(r\rightarrow t)\vee(s\rightarrow t)$
---

The Greek letters $\alpha,\beta,\gamma$ will range over $L$-formulas and the
letters $\varphi,\psi,\chi,\vartheta$ over $L^{*}$-formulas. Let $A$ be a set
of atomic formulas. A possible $A$-world is any function that assigns a truth
value ($1$ representing truth or $0$ representing falsity) to every atomic
formula from $A$. An $A$-context is a nonempty set of possible $A$-worlds. The
specification of the set $A$ will be omitted if no confusion arises. Note
that, by definition, there cannot be two different possible $A$-worlds in
which exactly the same atomic formulas are true.

For the complex formulas of the language $L$, the truth and falsity conditions
with respect to individual possible worlds are those of classical
propositional logic. $\Vdash^{+}$ and $\Vdash^{-}$ will now respectively stand
for the relations of assertibility and deniability between contexts and
formulas of the language $L^{*}$. The assertibility and deniability conditions
taken from [9] (and motivated by [5]) are defined in the following way:

$C\Vdash^{+}\alpha$ iff for all $w\in C$, $\alpha$ is true in $w$.
---
$C\Vdash^{-}\alpha$ iff for all $w\in C$, $\alpha$ is false in $w$.
$C\Vdash^{+}\neg\varphi$ iff $C\Vdash^{-}\varphi$.
$C\Vdash^{-}\neg\varphi$ iff $C\Vdash^{+}\varphi$.
$C\Vdash^{+}\varphi\vee\psi$ iff $C\Vdash^{+}\varphi$ or $C\Vdash^{+}\psi$.
$C\Vdash^{-}\varphi\vee\psi$ iff $C\Vdash^{-}\varphi$ and $C\Vdash^{-}\psi$.
$C\Vdash^{+}\varphi\and\psi$ iff $C\Vdash^{+}\varphi$ and $C\Vdash^{+}\psi$.
$C\Vdash^{-}\varphi\and\psi$ iff $C\Vdash^{-}\varphi$ or $C\Vdash^{-}\psi$.
$C\Vdash^{+}\varphi\rightarrow\psi$ iff $D\Vdash^{+}\psi$ for all nonempty
$D\subseteq C$, such that $D\Vdash^{+}\varphi$.
$C\Vdash^{-}\varphi\rightarrow\psi$ iff $D\Vdash^{-}\psi$ for some nonempty
$D\subseteq C$, such that $D\Vdash^{+}\varphi$.

The consequence relation is defined as assertibility preservation. That is, a
set of $L^{*}$-formulas $\Delta$ entails an $L^{*}$-formula $\psi$
(symbolically $\Delta\vDash\psi$) if $\psi$ is assertible in every context in
which all formulas from $\Delta$ are assertible. This consequence relation
represents what we here call the Logic of Assertibility and Deniability (LAD).
We say that two $L^{*}$-formulas, $\varphi$ and $\psi$, are (logically)
equivalent in this logic (symbolically $\varphi\equiv\psi$) if they are
assertible in the same contexts, that is, if $\varphi\vDash\psi$ and
$\psi\vDash\varphi$. They are strongly equivalent (symbolically
$\varphi\rightleftharpoons\psi$) if they are not only assertible but also
deniable in the same contexts, that is, if $\varphi\equiv\psi$ and
$\neg\varphi\equiv\neg\psi$. It can be shown by induction that strongly
equivalent formulas are universally interchangeable (this does not hold for
mere equivalence). Note that the Gauker’s original semantics from [5] does not
have this property.

######  Proposition 1.

Assume that $\varphi\rightleftharpoons\psi$, and $\varphi$ occurs as a
subformula in $\chi$. If $\chi^{\prime}$ is the result of replacing an
occurrence of the subformula $\varphi$ in $\chi$ with $\psi$ then
$\chi\rightleftharpoons\chi^{\prime}$.

Note that the assertibility clause for disjunction formally corresponds to the
support condition for inquisitive disjunction used in inquisitive semantics
(see [4]). However, in contrast to inquisitive semantics we do not treat
intensional disjunction as a question generating operator but as a statement
generating operator (e.g., the formula $(r\rightarrow t)\vee(s\rightarrow t)$
in the conclusion of our example does not represent a question but a
statement). The assertibility clauses for conjunction and implication also
correspond to the support clauses for these connectives in inquisitive
semantics. Technically speaking, if negation is omitted, LAD just corresponds
to inquisitive logic (which is axiomatized for example in [4]). What is
different from the standard inquisitive logic is our treatment of negation via
the deniability conditions. The deniability conditions for (intensional)
negation, disjunction and conjunction are the standard ones, typically used in
a bilateralist setting (see, e.g., [6]). The most tricky case is the
deniability condition for implication. There are two natural candidates for an
alternative deniability clause:

(A) |  $C\Vdash^{-}\varphi\rightarrow\psi$ iff $C\Vdash^{+}\varphi$ and $C\Vdash^{-}\psi$.
---|---
(B) |  $C\Vdash^{-}\varphi\rightarrow\psi$ iff $D\Vdash^{-}\psi$ for all nonempty $D\subseteq C$, such that $D\Vdash^{+}\varphi$.

The option (A) is known from Nelson logic (see [6]). However, this option
licenses the inference from $\neg(\varphi\rightarrow\psi)$ to $\varphi$ (and
also to $\neg\psi$), which we found highly problematic from the natural
language point of view (consider the following argument: It is not the case
that if I die today, I will be living tomorrow. Therefore I will die today.).
The option (B) looks much more plausible. This option is known from connexive
logic (see [11]). It makes $\neg(\varphi\rightarrow\psi)$ strongly equivalent
to $\varphi\rightarrow\neg\psi$. This is indeed a reasonable way to read
negations of conditionals. This clause was explored in more detail within the
semantics of assertibility and deniability in [7].

In our current setting the clause (B) would allow us to completely eliminate
intensional negations from any $L^{*}$-formula. Since we also have double
negation and DeMorgan laws guaranteed by the other semantic clauses, we could
push all the intensional negations occurring in a formula to the subformulas
that are already in the language $L$. For example, in the formula
$\neg(\neg(p\and{\sim}s)\rightarrow(p\cup{\sim}q))$ we could push the
negations inside the formula in the following way: $(\neg
p\vee\neg{\sim}s)\rightarrow\neg(p\cup{\sim}q)$. Moreover, observe that for
any $L$-formula $\alpha$ we have $\neg\alpha\rightleftharpoons{\sim}\alpha$,
so when pushed so that it applies to an $L$-formula, intensional negation can
be replaced with extensional negation (we would obtain
$({\sim}p\vee{\sim}{\sim}s)\rightarrow{\sim}(p\cup{\sim}q)$, in our example).
Hence, if the deniability clause (B) for implication is employed, every
occurrence of intensional negation in any $L^{*}$-formula can be dissolved and
thus intensional negation does not add any extra expressive power.

Aside from making intensional negation redundant, the clause (B) has one other
questionable consequence. If this clause is employed, there are formulas that
are assertible as well as deniable in some contexts. There are even formulas
that are assertible as well as deniable in every context and thus there are
formulas of the form $\varphi\and\neg\varphi$ regarded as logically valid. A
concrete example is obtained when we substitute $(p\and\neg
p)\rightarrow(p\vee\neg p)$ for $\varphi$. Hence, the resulting logic is not
only paraconsistent but it is in this sense inconsistent (see [11] for a more
detailed discussion of this phenomenon). From a certain point of view, this
may not be conceived as a substantial problem. However, in this paper, we want
to maintain consistency and thus we reject clause (B) in favour of the clause
stated above according to which a conditional is deniable in a context $C$ if
and only if there is some subcontext of $C$ in which the antecedent is
assertible and the consequent is deniable. This deniability clause corresponds
to the one proposed in Gauker’s book [5]. It can be viewed as a weakening of
the strong clause (A) in the sense that $\neg(\varphi\rightarrow\psi)$ is not
equivalent to $\varphi\and\neg\psi$ but rather to a mere possibility of
$\varphi\and\neg\psi$. This way of denying conditionals seems to have strong
support from natural language. For example, with respect to the context above,
one can deny the claim if the murderer is tall, he has dark hair because it is
possible (from the perspective of the context) that the murderer is tall and
does not have dark hair. In comparison to (B) we can observe that the clause
(C) allows us to prove by induction the following fact.

######  Proposition 2.

There is no context $C$ and no $L^{*}$-formula $\varphi$ such that
$C\Vdash^{+}\varphi$ and $C\Vdash^{-}\varphi$.

Another feature that distinguishes our deniability clause for implication from
(B) is that it leads to the classical behaviour of intensional connectives in
the special case where the context contains only one world. Thus in singleton
contexts the assertibility and deniability clauses for intensional connectives
coincide with truth and falsity clauses for the extensional connectives. To
express this fact more formally, we will use the following notation. For any
$L^{*}$-formula $\varphi$, $\varphi^{e}$ denotes the $L$-formula which is the
result of replacing all intensional connectives in $\varphi$ with their
extensional counterparts. Then the following fact can be easily established by
induction.

######  Proposition 3.

$\left\\{w\right\\}\Vdash^{+}\varphi$ iff $\varphi^{e}$ is true in $w$, and
$\left\\{w\right\\}\Vdash^{-}\varphi$ iff $\varphi^{e}$ is false in $w$.

Since the truth conditions for the extensional connectives are the standard
ones, the consequence relation restricted to the language $L$ is classical.

######  Proposition 4.

For the formulas of the language $L$ the consequence relation coincides with
the consequence relation of classical logic.

Of course, in general intensional and extensional connectives behave
differently. Let us illustrate this with the murder scenario described above.
Let $A$ be the set of atomic formulas $\\{p,q,r,s,t\\}$. Consider the
following formalization and an $A$-context consisting of four possible
$A$-worlds that differ from each other on who among the suspects committed the
murder.

|  | $w_{\\_}1$ | $w_{\\_}2$ | $w_{\\_}3$ | $w_{\\_}4$
---|---|---|---|---|---
The murderer is tall. | $p$ | 1 | 1 | 0 | 0
The murderer is short. | $q$ | 0 | 0 | 1 | 1
The murderer has dark hair. | $r$ | 1 | 0 | 0 | 1
The murderer has blond hair. | $s$ | 0 | 1 | 1 | 0
The murderer has a moustache. | $t$ | 1 | 0 | 1 | 0

Now one can check that in this context all the premises of the argument,
namely the formulas $p\cup q$, $p\rightarrow(r\rightarrow t)$, and
$q\rightarrow(s\rightarrow t)$, are assertible but the conclusion
$(r\rightarrow t)\vee(s\rightarrow t)$ is not.

Our deniability condition for conditionals is an important ingredient of the
semantics because it increases the expressive power of the language and
introduces a specific kind of non-persistent formulas. We say that a formula
is persistent if it holds that whenever it is assertible in a context, it is
assertible in every subcontext (i.e. in every nonempty subset) of the context.
It can be proved by induction that every $L^{*}$-formula that does not contain
any intensional implication in the scope of an intensional negation is
persistent.

This claim does not hold generally. For example, for the above context
$C=\\{w_{\\_}1,w_{\\_}2,w_{\\_}3,w_{\\_}4\\}$ we have
$C\Vdash^{+}\neg(p\rightarrow q)$ because there is a subcontext
$D=\\{w_{\\_}1,w_{\\_}2\\}$ such that $D\Vdash^{+}p$ and $D\Vdash^{-}q$.
However, there is a subcontext $E\subseteq C$, e.g.
$E=\\{w_{\\_}3,w_{\\_}4\\}$, such that $E\nVdash^{+}\neg(p\rightarrow q)$.

Note that every formula of the form $\varphi\rightarrow\psi$ is also
persistent, even if it contains an occurrence of intensional implication in
the scope of intensional negation. We would like to say that persistent
formulas play in inferences a substantially different role than non-persistent
formulas. However, the notion of a persistent formula was defined semantically
and thus we cannot use it directly in the formulation of a syntactic deductive
system. Nevertheless, we just specified syntactically a large class of
formulas that have this semantic property. We will call them safe. We say that
a formula is safe, if either it does not contain any $\rightarrow$ in the
scope of $\neg$, or it is of the form $\varphi\rightarrow\psi$.

######  Proposition 5.

Every safe formula is persistent.

Safe formulas will play an important role in the formulation of our system of
natural deduction. The subsequent completeness proof will indicate that this
syntactic notion sufficiently approximates the notion of a persistent formula.

Now we will show that by the extra expressive power gained from the
deniability clause for implication we obtain functional completeness. To
describe this fact more precisely, we will use the following defined symbols
that will also be used later in the system of natural deduction.

(a) |  $\bot=_{\\_}{def}p\cap{\sim}p$, for some selected fixed atomic formula $p$,
---|---
(b) |  $\lozenge\varphi=_{\\_}{def}\neg(\varphi\rightarrow\bot)$,
(c) |  $\alpha_{\\_}1\oplus\ldots\oplus\alpha_{\\_}n=_{\\_}{def}(\alpha_{\\_}1\cup\ldots\cup\alpha_{\\_}n)\and(\lozenge\alpha_{\\_}1\and\ldots\and\lozenge\alpha_{\\_}n)$.

The symbol $\bot$ represents a contradiction. It can be easily observed that
$C\Vdash^{-}\bot$, for every context $C$. The symbol $\lozenge$ expresses a
contextual possibility. It holds that $C\Vdash^{+}\lozenge\varphi$ iff there
is a nonempty $D\subseteq C$ such that $D\Vdash^{+}\varphi$. Finally, $\oplus$
represents a “pragmatic disjunction”, i.e. an extensional disjunction but such
that all its disjuncts are possible (which is usually regarded to be a
pragmatic feature of disjunction).

If a finite set of atomic formulas is fixed, any $A$-world $w$ can be
described by an $L$-formula $\sigma_{\\_}w$ in the usual way. For example, in
the above example the formula $\sigma_{\\_}{w_{\\_}1}$ would be
$p\cap{\sim}q\cap r\cap{\sim}s\cap t$. Now any $A$-context
$C=\\{w_{\\_}1,\ldots,w_{\\_}n\\}$ can be described by the formula
$\mu_{\\_}C=\sigma_{\\_}{w_{\\_}1}\oplus\ldots\oplus\sigma_{\\_}{w_{\\_}n}$.
Moreover, any set of $A$-contexts $X=\\{C_{\\_}1,\ldots,C_{\\_}k\\}$ can be
described by the formula
$\xi_{\\_}X=\mu_{\\_}{C_{\\_}1}\vee\ldots\vee\mu_{\\_}{C_{\\_}k}$. Now we can
state the functional completeness result.

######  Proposition 6.

Let $A$ be a finite set of atomic formulas. Then it holds for any $A$-contexts
$C,D$ that $C\Vdash^{+}\mu_{\\_}D$ iff $D=C$. Moreover, it holds for any set
of $A$-contexts $X$, and any $A$-context $C$ that $C\Vdash^{+}\xi_{\\_}X$ iff
$C\in X$.

A similar result was observed in [8] for inquisitive logic with an operation
called “weak negation”. In fact, the crucial part of the proof of our main
result will be a syntactic reconstruction of weak negation within our system
of natural deduction.

##  3 Deductive calculus

In this section we define a Fitch style system of natural deduction for the
semantics of assertibility and deniability. We will use the following economic
notation. We use brackets and the colon to refer to subproofs. For example,
$[\varphi:\psi]$ stands for a subproof in which $\varphi$ is the hypothetical
assumption and $\psi$ is the last line of the subproof. We use two kinds of
brackets, square and round. The difference is in the formulas from the outer
proof that can be used in the subproof. By using square brackets in
$[\varphi:\psi]$ we indicate that all formulas that are available in the step
before the hypothetical assumption $\varphi$ is made are also available under
this assumption in the derivation of $\psi$ from $\varphi$. This is just as in
the standard natural deduction systems for classical and intuitionistic logic.
The round brackets indicate that there is a restriction concerning the
formulas from the outer proof that can be used under the assumption. By
writing $(\varphi:\psi)$, we indicate that only safe formulas from the outer
proof can be used in the derivation of $\psi$ from $\varphi$. (Safe formulas
are defined in the previous section.)

The distinction between square and round brackets reflects the semantic
distinction between two kinds of hypothetical assumption. Square brackets,
i.e. $[\varphi:\psi]$, indicate that by making the hypothetical assumption
$\varphi$ in a context $C$ we do not change the given context, we only assume
that the assumption $\varphi$ is assertible in $C$. In contrast, round
brackets, i.e. $(\varphi:\psi)$, indicate that by making the hypothetical
assumption $\varphi$ in a context $C$ we move from $C$ to an arbitrary
subcontext $D$ of $C$ in which $\varphi$ is assertible. If we have already
proved that a formula is assertible in $C$, we can use it under the assumption
$\varphi$ (in $D$) only if it is guaranteed that it is persistent. Proposition
5 guarantees that all safe formulas are persistent.

We split the rules of the calculus into three groups. The first group contains
the “classical” introduction and elimination rules for the extensional
connectives.

(i$\cap$) | $\alpha,\beta/\alpha\cap\beta$ | (e$\cap_{\\_}1$) | $\alpha\cap\beta/\alpha$
---|---|---|---
|  | (e$\cap_{\\_}2$) | $\alpha\cap\beta/\beta$
(i$\cup_{\\_}1$) | $\alpha/\alpha\cup\beta$ | (e$\cup$) | $\alpha\cup\beta,(\alpha:\gamma),(\beta:\gamma)/\gamma$
(i$\cup_{\\_}2$) | $\beta/\alpha\cup\beta$ |  |
(i$\supset$) | $(\alpha:\beta)/\alpha\supset\beta$ | (e$\supset$) | $\alpha,\alpha\supset\beta/\beta$
(i$\sim$) | $(\alpha:\bot)/{\sim}\alpha$ | (e$\sim_{\\_}1$) | $\alpha,{\sim}\alpha/\bot$
|  | (e$\sim_{\\_}2$) | ${\sim}{\sim}\alpha/\alpha$

The second group contains the following “intuitionistic” rules concerning the
intensional connectives (but notice the restrictions indicated by round
brackets and the fact that (i$\neg$) is restricted to $L$-formulas):

(i$\and$) | $\varphi,\psi/\varphi\and\psi$ | (e$\and_{\\_}1$) | $\varphi\and\psi/\varphi$
---|---|---|---
|  | (e$\and_{\\_}2$) | $\varphi\and\psi/\psi$
(i$\vee_{\\_}1$) | $\varphi/\varphi\vee\psi$ | (e$\vee$) | $\varphi\vee\psi,[\varphi:\chi],[\psi:\chi]/\chi$
(i$\vee_{\\_}2$) | $\psi/\varphi\vee\psi$ |  |
(i$\rightarrow$) | $(\varphi:\psi)/\varphi\rightarrow\psi$ | (e$\rightarrow$) | $\varphi,\varphi\rightarrow\psi/\psi$
(i$\neg$) | $(\alpha:\bot)/\neg\alpha$ | (e$\neg$) | $\varphi,\neg\varphi/\bot$
|  | (EFQ) | $\bot/\varphi$

The third group consists of the rules that characterize the interaction of
intensional negation with all intensional operators, plus two extra rules,
(CEM), i.e. “contextual excluded middle”, and ($\lozenge\oplus$):

($\neg\neg_{\\_}1$) | $\neg\neg\varphi/\varphi$ | ($\neg\neg_{\\_}2$) | $\varphi/\neg\neg\varphi$
---|---|---|---
($\neg\and_{\\_}1$) | $\neg(\varphi\and\psi)/\neg\varphi\vee\neg\psi$ | ($\neg\and_{\\_}2$) | $\neg\varphi\vee\neg\psi/\neg(\varphi\and\psi)$
($\neg\vee_{\\_}1$) | $\neg(\varphi\vee\psi)/\neg\varphi\and\neg\psi$ | ($\neg\vee_{\\_}2$) | $\neg\varphi\and\neg\psi/\neg(\varphi\vee\psi)$
($\neg{\rightarrow}_{\\_}1$) | $\neg(\varphi\rightarrow\psi)/\lozenge(\varphi\and\neg\psi)$ | ($\neg{\rightarrow}_{\\_}2$) | $\lozenge(\varphi\and\neg\psi)/\neg(\varphi\rightarrow\psi)$
(CEM) | $/(\varphi\rightarrow\bot)\vee\lozenge\varphi$ | ($\lozenge\oplus$) | $\lozenge\alpha_{\\_}{1}\and\ldots\and\lozenge\alpha_{\\_}{n}/\lozenge(\alpha_{\\_}{1}\oplus\ldots\oplus\alpha_{\\_}{n})$

We will write $\varphi_{\\_}1,\ldots,\varphi_{\\_}n\vdash\psi$ if $\psi$ is
derivable in this system from the assumptions
$\varphi_{\\_}1,\ldots,\varphi_{\\_}n$.

As we already mentioned, our semantics has some connection to inquisitive
semantics. Note, however, that our deductive system is very different from the
standard system of natural deduction for inquisitive logic (see, e.g., [3]),
though it has some similarities with the system for inquisitive logic with
weak negation developed in [8].

We can illustrate the role of restrictions related to round brackets with the
following example. If the restriction given by the round brackets were not
present we could derive, for example, the contradiction $\bot$ from the
premise $\lozenge p\and\lozenge{\sim}p$ in the following way:

  * ◆p and ◆∼ p = ¬(p →⊥) and ¬(∼ p →⊥) | premise
---|---
p ∪∼ p | the standard derivation of excluded middle
p | hypothetical assumption
∼ p | hypothetical assumption
⊥ |  3,4, (e${\sim}_{\\_}1$)
∼ p →⊥ |  4-5, (i$\rightarrow$)
¬(∼ p →⊥) |  1, (e$\and_{\\_}2$)
⊥ |  6,7, (e$\neg$)
∼ p | hypothetical assumption
p | hypothetical assumption
⊥ |  9,10, (e${\sim}_{\\_}1$)
p →⊥ |  10-11, (i$\rightarrow$)
¬(p →⊥) |  1, (e$\and_{\\_}1$)
⊥ |  12,13, (e$\neg$)
⊥ |  2,3-8,9-14, (e$\cup$)

This would be an undesirable result. In our semantics, $\lozenge
p\and\lozenge{\sim}p$ does not entail $\bot$ which accords with the intuition
that $p$ and ${\sim} p$ can consistently be both possible. As it stands, the
derivation is incorrect in the system, because in the steps 7 and 13 the
restriction on the rule (e$\cup$) was not respected and the unsafe formula
$\lozenge p\and\lozenge{\sim}p$ occurring in the outer proof was used under
the hypothetical assumptions.

We can observe that all rules of the system are sound with respect to the
semantics. To illustrate how the soundness proof goes let us consider the
rules (e$\cup$) and (e$\vee$). Let $\Delta^{s}$ denote the set of safe
formulas from $\Delta$. Soundness of the two rules corresponds respectively to
the following two semantic facts:

  * (a)

If $\Delta^{s},\alpha\vDash\gamma$ and $\Delta^{s},\beta\vDash\gamma$ then
$\Delta,\alpha\cup\beta\vDash\gamma$.

  * (b)

If $\Delta,\varphi\vDash\chi$ and $\Delta,\psi\vDash\chi$ then
$\Delta,\varphi\vee\psi\vDash\chi$.

In order to prove (a), assume that $\Delta^{s},\alpha\vDash\gamma$ and
$\Delta^{s},\beta\vDash\gamma$. Let $C$ be a context in which all formulas
from $\Delta$ and the formula $\alpha\cup\beta$ are assertible. Take an
arbitrary possible world $w\in C$. All formulas of $\Delta^{s}$ are assertible
in $\\{w\\}$ (due to persistence of safe formulas). Moreover, $\alpha$ or
$\beta$ is assertible in $\\{w\\}$. It follows from our assumption that
$\gamma$ is assertible in $\\{w\\}$. Since this holds for every $w\in C$, and
$\gamma$ is an $L$-formula, we obtain $C\Vdash^{+}\gamma$, as required.

In order to prove (b), assume that $\Delta,\varphi\vDash\chi$ and
$\Delta,\psi\vDash\chi$. Let $C$ be a context in which all formulas from
$\Delta$ and the formula $\varphi\vee\psi$ are assertible. Then $\varphi$ or
$\psi$ is assertible in $C$. It follows from our assumption that $\chi$ is
assertible in $C$, as required.

##  4 Completeness

The proof of completeness proceeds in the following steps. First a contextual
weak negation $-\varphi$ is defined recursively. This negation is a denial of
assertibility, that is, $-\varphi$ is assertible in a given context iff
$\varphi$ is not assertible in that context. It has to be shown that this
negation behaves properly also on the syntactic side. That means that the
following holds: $\Delta\nvdash\varphi$ if and only if
$\Delta\cup\\{-\varphi\\}$ is consistent, i.e. $\Delta,-\varphi\nvdash\bot$.
The proof of this fact will be the main task of this section. The
reconstruction of weak negation allows us to reduce completeness to the claim
that every consistent set has a model. We will only sketch the proof of this
claim because the technique is basically the same as the one used in the
completeness proof for inquisitive logic with weak negation from [8]. The
“contextual weak negation” is defined by the following five recursive clauses.
The first clause states the definition for $L$-formulas and their intensional
negations:

1. |  $-\alpha=\lozenge\neg\alpha$, |  $-\neg\alpha=\lozenge\alpha$.
---|---|---

In the clauses 2.-5. we assume that $\varphi,\psi$ are arbitrary
$L^{*}$-formulas for which $-\varphi,-\neg\varphi,-\psi,-\neg\psi$ are already
defined, and we further define:

2. |  $-\neg\neg\varphi=-\varphi$. |
---|---|---
3. | (a) $-(\varphi\rightarrow\psi)=\lozenge(\varphi\and-\psi)$, | (b) $-\neg(\varphi\rightarrow\psi)=\varphi\rightarrow-\neg\psi$.
4. | (a) $-(\varphi\and\psi)=-\varphi\vee-\psi$, | (b) $-\neg(\varphi\and\psi)=-\neg\varphi\and-\neg\psi$.
5. | (a) $-(\varphi\vee\psi)=-\varphi\and-\psi$, | (b) $-\neg(\varphi\vee\psi)=-\neg\varphi\vee-\neg\psi$.

Note that by these clauses $-\varphi$ is indeed defined for every
$L^{*}$-formula $\varphi$. By induction on $\varphi$, we obtain the following
observation.

######  Lemma 1.

For any $L^{*}$-formula $\varphi$ and any context $C$, it holds that

  * $C\Vdash^{+}-\varphi$ iff $C\nVdash^{+}\varphi$.

We say that a context $C$ is a model of a set of formulas $\Delta$ if and only
if every formula from $\Delta$ is assertible in $C$. The following lemma
follows directly from Lemma 1.

######  Lemma 2.

$\Delta\nvDash\varphi$ iff $\Delta\cup\\{-\varphi\\}$ has a model.

The next lemma is a cornerstone of the completeness proof and the main
technical issue of this paper.

######  Lemma 3.

For any formula $\varphi$, the following holds:

  * (a)

$\vdash\varphi\vee-\varphi$,

  * (b)

$\varphi,-\varphi\vdash\bot$.

###### Proof.

(a) We will proceed by simultaneous induction on $\varphi$ and $\neg\varphi$.
In the derivations below, whenever we use a safe formula in a context in which
it is required to use only safe formulas, we indicate this in the
corresponding annotation.

1\. Assume that $\alpha$ is from $L$. We will derive $\alpha\vee-\alpha$, i.e.
$\alpha\vee\neg(\neg\alpha\rightarrow\bot)$. The derivation of
$\neg\alpha\vee-\neg\alpha$ is similar.

  * (¬α→⊥) ∨¬(¬α→⊥) | (CEM)
---|---
¬α→⊥ | hypothetical assumption
∼α | hypothetical assumption
α | hypothetical assumption
⊥ |  3,4, (e$\sim_{\\_}1$)
¬α |  4-5, (i$\neg$)
⊥ |  2-safe,6, (e$\rightarrow$)
∼∼α |  3-7, (i$\sim$)
α |  8, (e$\sim_{\\_}2$)
α∨¬(¬α→⊥) |  9, (i$\vee_{\\_}1$)
¬(¬α→⊥) | hypothetical assumption
α∨¬(¬α→⊥) |  11, (i$\vee_{\\_}2$)
α∨¬(¬α→⊥) |  1,2-10,11-12, (e$\vee$)

In the cases 2.-5. we assume as an inductive hypothesis that our claim holds
for $\varphi,\neg\varphi,\psi,\neg\psi$.

2\. It is easy to derive $\neg\neg\varphi\vee-\neg\neg\varphi$ from
$\varphi\vee-\varphi$, by (e$\vee$), (i$\vee_{\\_}1$), (i$\vee_{\\_}2$), and
($\neg\neg_{\\_}2$).

3\. We show that our claim holds for $\varphi\rightarrow\psi$ and
$\neg(\varphi\rightarrow\psi)$. First, we prove
$\vdash(\varphi\rightarrow\psi)\vee-(\varphi\rightarrow\psi)$, i.e.
$\vdash(\varphi\rightarrow\psi)\vee\lozenge(\varphi\and-\psi)$, which can be
done in the following way:

  * ((φ and -ψ) →⊥) ∨◆(φ and -ψ) | (CEM)
---|---
(φ and -ψ) →⊥ | hypothetical assumption
φ | hypothetical assumption
ψ∨- ψ | induction hypothesis
ψ | hypothetical assumption
– ψ | hypothetical assumption
φ and - ψ |  3,6, (i$\and$)
⊥ |  2-safe,7, (e$\rightarrow$)
ψ | 8, (EFQ)
ψ |  4,5,6-9, (e$\vee$)
φ→ψ |  3-10, (i$\rightarrow$)
(φ→ψ) ∨◆(φ and -ψ) |  11, (i$\vee_{\\_}1$)
◆(φ and -ψ) | hypothetical assumption
(φ→ψ) ∨◆(φ and -ψ) |  13, (i$\vee_{\\_}2$)
(φ→ψ) ∨◆(φ and -ψ) |  1,2-12,13-14, (e$\vee$)

Now we prove
$\vdash\neg(\varphi\rightarrow\psi)\vee-\neg(\varphi\rightarrow\psi)$, i.e.
$\neg(\varphi\rightarrow\psi)\vee(\varphi\rightarrow-\neg\psi)$:

  * ((φ and ¬ψ) →⊥) ∨◆(φ and ¬ψ) | (CEM)
---|---
(φ and ¬ψ) →⊥ | hypothetical assumption
φ | hypothetical assumption
¬ψ∨-¬ψ | induction hypothesis
¬ψ | hypothetical assumption
φ and ¬ψ |  3,5, (i$\and$)
⊥ |  2-safe,6, (e$\rightarrow$)
– ¬ψ | 7, (EFQ)
– ¬ψ | hypothetical assumption
– ¬ψ |  4,5-8,9, (e$\vee$)
φ→-¬ψ |  3-10, (i$\rightarrow$)
¬(φ→ψ) ∨(φ→- ¬ψ) |  11, (i$\vee_{\\_}2$)
◆(φ and ¬ψ) | hypothetical assumption
¬(φ→ψ) |  13, ($\neg{\rightarrow}_{\\_}2$)
¬(φ→ψ) ∨(φ→- ¬ψ) |  14, (i$\vee_{\\_}1$)
¬(φ→ψ) ∨(φ→- ¬ψ) |  1,2-12,13-15, (e$\vee$)

4\. We prove that our claim holds for $\varphi\and\psi$ and
$\neg(\varphi\and\psi)$. First, we prove the former, i.e.
$\vdash(\varphi\and\psi)\vee(-\varphi\vee-\psi)$, which can be done by the
following derivation:

  * φ∨- φ | induction hypothesis
---|---
φ | hypothetical assumption
ψ∨- ψ | induction hypothesis
ψ | hypothetical assumption
φ and ψ |  2,4, (i$\and$)
(φ and ψ) ∨(-φ∨-ψ) |  5, (i$\vee_{\\_}1$)
-ψ | hypothetical assumption
(φ and ψ) ∨(-φ∨-ψ) |  7, (i$\vee_{\\_}2$) (twice)
(φ and ψ) ∨(-φ∨-ψ) |  3, 4-6,7-8, (e$\vee$)
\- φ | hypothetical assumption
(φ and ψ) ∨(-φ∨-ψ) |  10, (i$\vee_{\\_}1$), (i$\vee_{\\_}2$)
(φ and ψ) ∨(-φ∨-ψ) |  1,2-9,10-11, (e$\vee$)

Now we prove that
$\vdash\neg(\varphi\and\psi)\vee(-\neg\varphi\and-\neg\psi)$, which can be
done by the following derivation:

  * ¬φ∨- ¬φ | induction hypothesis
---|---
¬φ | hypothetical assumption
¬φ∨¬ψ |  2, (i$\vee_{\\_}1$)
¬(φ and ψ) |  3, ($\neg\and_{\\_}2$)
¬(φ and ψ) ∨(-¬φ and -¬ψ) |  4, (i$\vee_{\\_}1$)
-¬φ | hypothetical assumption
¬ψ∨- ¬ψ | induction hypothesis
¬ψ | hypothetical assumption
¬φ∨¬ψ |  8, (i$\vee_{\\_}2$)
¬(φ and ψ) |  9, ($\neg\and_{\\_}2$)
¬(φ and ψ) ∨(-¬φ and -¬ψ) |  10, (i$\vee_{\\_}1$)
\- ¬ψ | hypothetical assumption
(-¬φ and -¬ψ) |  6,12, (i$\and$)
¬(φ and ψ) ∨(-¬φ and -¬ψ) |  13, (i$\vee_{\\_}2$)
¬(φ and ψ) ∨(-¬φ and -¬ψ) |  7,8-11,12-14, (e$\vee$)
¬(φ and ψ) ∨(-¬φ and -¬ψ) |  1,2-5,6-15, (e$\vee$)

5\. The case of $\vee$ is analogous to the case of $\and$. This finishes the
proof of (a).

(b) We will proceed again by simultaneous induction on $\varphi$ and
$\neg\varphi$. 1. Assume that $\alpha$ is any $L$-formula. First, we will
derive $\bot$ from $\alpha$ and $-\alpha=\neg(\neg\alpha\rightarrow\bot)$. The
derivation of $\bot$ from $\neg\alpha$ and $-\neg\alpha$ is similar.

  * α | premise
---|---
¬(¬α→⊥) | premise
¬α | hypothetical assumption
⊥ |  1-safe,3, (e$\neg$)
¬α→⊥ |  2-3, (i$\rightarrow$)
⊥ |  2,5, (e$\neg$)

For the steps 3.-5., assume as an induction hypothesis that our claim holds
for some arbitrary $\varphi,\neg\varphi,\psi,\neg\psi$. 2. It is easy to see
that if we assume $\varphi,-\varphi\vdash\bot$, then also
$\neg\neg\varphi,-\neg\neg\varphi\vdash\bot$, by ($\neg\neg_{\\_}1$).

3\. We prove that the claim holds for $\varphi\rightarrow\psi$, i.e.
$\varphi\rightarrow\psi,-(\varphi\rightarrow\psi)\vdash\bot$.

  * φ→ψ | premise
---|---
–(φ→ψ)=¬((φ and - ψ) →⊥) | premise
φ and - ψ | hypothetical assumption
φ |  3, (e$\and_{\\_}1$)
ψ |  1-safe,4, (e$\rightarrow$)
– ψ |  3, (e$\and_{\\_}2$)
⊥ | 5,6, induction hypothesis
(φ and - ψ) →⊥ |  3-7, (i$\rightarrow$)
⊥ |  2,8, (e$\neg$)

Now we prove that
$\neg(\varphi\rightarrow\psi),-\neg(\varphi\rightarrow\psi)\vdash\bot$.

  * ¬(φ→ψ) | premise
---|---
– ¬(φ→ψ)= φ→- ¬ψ | premise
φ and ¬ψ | hypothetical assumption
φ |  3, (e$\and_{\\_}1$)
– ¬ψ |  2-safe,4, (e$\rightarrow$)
¬ψ |  3, (e$\and_{\\_}2$)
⊥ | 5,6, induction hypothesis
(φ and ¬ψ) →⊥ |  3-7, (i$\rightarrow$)
¬((φ and ¬ψ) →⊥) |  1, ($\neg{\rightarrow}_{\\_}1$)
⊥ |  8,9, (e$\neg$)

4\. We prove that our claim holds for $\varphi\and\psi$ and
$\neg(\varphi\and\psi)$. First, we prove that
$\varphi\and\psi,-(\varphi\and\psi)\vdash\bot$, which can be done by the
following derivation:

  * φ and ψ | premise
---|---
-φ∨-ψ | premise
-φ | hypothetical assumption
φ |  1, (e$\and_{\\_}1$)
⊥ | 3,4, induction hypothesis
-ψ | hypothetical assumption
ψ |  1, (e$\and_{\\_}1$)
⊥ | 6,7, induction hypothesis
⊥ |  2,3-5,6-8, (e$\vee$)

Now we prove that $\neg(\varphi\and\psi),-\neg(\varphi\and\psi)\vdash\bot$,
which can be done by the following derivation:

  * ¬(φ and ψ) | premise
---|---
-¬φ and -¬ψ | premise
¬φ∨¬ψ |  1, ($\neg\and_{\\_}1$)
¬φ | hypothetical assumption
-¬φ |  2, (e$\and_{\\_}1$)
⊥ | 4,5, induction hypothesis
¬ψ | hyp
-¬ψ |  2, (e$\and_{\\_}2$)
⊥ | 7,8, induction hypothesis
⊥ |  3,4-6,7-9, (e$\vee$)

5\. The case of $\vee$ is analogous to the case of $\and$. This finishes the
proof of (b). ∎

######  Lemma 4.

$\Delta\nvdash\varphi$ iff $\Delta\cup\\{-\varphi\\}$ is consistent.

###### Proof.

The left-to-right implication is obtained from Lemma 3-a, using the rules
(e$\vee$) and (EFQ), and the right-to-left implication follows from Lemma 3-b.
∎

######  Lemma 5.

Every consistent finite set of $L^{*}$-formulas has a model.

###### Proof.

We can give only a sketch of the proof here. The strategy is the same as in
the analogous proofs in [8] and [10]. Let $A$ be a finite set of atomic
formulas. Recall that for every $A$-context $C$ there is an $L^{*}$-formula
$\mu_{\\_}C$ characterizing $C$ in the following sense: For every $A$-context
$D$, $D\Vdash^{+}\mu_{\\_}{C}$ iff $D=C$. We can further prove that if
$\Delta$ is a consistent set of $L^{*}$-formulas built out of the atomic
formulas from $A$, then there is an $A$-context $C$ such that
$\Delta\cup\left\\{\mu_{\\_}{C}\right\\}$ is consistent. Moreover, we can
prove by induction, crucially using the rule ($\lozenge\oplus$), that for
every $L^{*}$-formula $\varphi$ built out of the atomic formulas from $A$,
either $\mu_{\\_}{C}\vdash\varphi$, or $\mu_{\\_}{C}\vdash-\varphi$.

We can further reason as follows. Let $\Delta$ be a consistent finite set of
$L^{*}$-formulas and let $A$ be the set of atomic formulas occurring in
$\Delta$. Then there is an $A$-context $C$ such that
$\Delta\cup\left\\{\mu_{\\_}{C}\right\\}$ is consistent. It follows that
$\mu_{\\_}{C}\vdash\psi$, for every $\psi\in\Delta$. Since
$C\Vdash^{+}\mu_{\\_}{C}$ it follows from soundness of the deductive rules
that $C\Vdash^{+}\psi$, for every $\psi\in\Delta$. Hence, $\Delta$ has a
model. ∎

######  Theorem 1.

$\varphi_{\\_}1,\ldots,\varphi_{\\_}n\vdash\psi$ iff
$\varphi_{\\_}1,\ldots,\varphi_{\\_}n\vDash\psi$.

###### Proof.

Soundness was already discussed and completeness is obtained from Lemmas 2, 4,
and 5. ∎

## References

  * [1]
  * [2] Justin Bledin (2014): _Logic informed_.  Mind 123, pp. 277–316, 10.1093/mind/fzu073.
  * [3] Ivano Ciardelli (2016): _Questions in Logic_.  Ph.D. thesis, University of Amsterdam.
  * [4] Ivano Ciardelli & Floris Roelofsen (2011): _Inquisitive logic_.  Journal of Philosophical Logic 40, pp. 55–94, 10.1007/s10992-010-9142-6.
  * [5] Christopher Gauker (2005): _Conditionals in Context_.  MIT Press, Cambridge MA.
  * [6] Sergei Odintsov (2008): _Constructive Negations and Paraconsistency_.  Springer, Dordrecht, 10.1007/978-1-4020-6867-6.
  * [7] Vít Punčochář (2014): _Intensionalisation of logical operators_.  In Michal Dančák & Vít Punčochář, editors: The Logica Yearbook 2013, College Publications, London, pp. 173–186.
  * [8] Vít Punčochář (2015): _Weak negation in inquisitive semantics_.  Journal of Logic, Language, and Information 24(3), pp. 323–355, 10.1007/s10849-015-9219-2.
  * [9] Vít Punčochář (2016): _Semantics of assertibility and deniability_.  In Juan Redmond, Olga Pombo Martins & Ángel Nepomuceno Fernández, editors: Epistemology, Knowledge and the Impact of Interaction, Logic, Epistemology, and the Unity of Science 38, Springer, Cham, pp. 343–362, 10.1007/978-3-319-26506-315.
  * [10] Vít Punčochář & Christopher Gauker (2020): _Indicative conditionals in objective contexts_.  Theoria 86(5), pp. 651–687, 10.1111/theo.12277.
  * [11] Heinrich Wansing (2021): _Connexive logic_.  Available at https://plato.stanford.edu/archives/spr2021/entries/logic-connexive/.
  * [12] Seth Yalcin (2012): _A counterexample to modus tollens_.  Journal of Philosophical Logic 41, pp. 1001–1024, 10.1007/s10992-012-9228-4.


# ReAD: A Regional Anomaly Detection Framework Based on Dynamic Partition

Huaishao Luo1, Chuishi Meng2, Bowen Wu2, Junbo Zhang2, Tianrui Li1, Yu Zheng2
1Southwest Jiaotong University, Chengdu, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
2Urban Computing Business Unit, JD Digits, Beijing, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The detection of the abnormal area from urban data is a significant research
problem. However, to the best of our knowledge, previous methods designed on
spatio-temporal anomalies are road-based or grid-based, which usually causes
the data sparsity problem and affects the detection results. In this paper, we
proposed a dynamic region partition method to address the above issues.
Besides, we proposed an unsupervised REgional Anomaly Detection framework
(ReAD) to detect abnormal regions with arbitrary shapes by jointly considering
spatial and temporal properties. Specifically, the proposed framework first
generate regions via a dynamic region partition method. It keeps that
observations in the same region have adjacent locations and similar non-
spatial attribute readings, and could alleviate data sparsity and
heterogeneity compared with the grid-based approach. Then, an anomaly metric
will be calculated for each region by a regional divergence calculation
method. The abnormal regions could be finally detected by a weighted approach
or a wavy approach according to the different scenario. Experiments on both
the simulated dataset and real-world applications demonstrate the
effectiveness and practicability of the proposed framework.

_K_ eywords Dynamic region partition $\cdot$ Regional anomaly detection
$\cdot$ Spatio-temporal anomaly detection $\cdot$ Urban computing

##  1 Introduction

Anomaly detection is widely used in many scenarios, e.g., credit card fraud
and industrial damage detection [1]. Most of them are usually associated with
scalar datasets or time series. As a branch of anomaly detection, urban
anomaly detection, which also belongs to urban computing [2], mainly focuses
the anomalies in the urban. In urban computing, observations generally contain
two kinds of descriptive information: spatial attribute, namely geographic
coordinates, and temporal attribute, which shows as the dynamic readings with
time. Formatively, each observation is a triplet $\langle$geographic
locations, timestamp, readings$\rangle$. Thus, urban anomaly detection should
consider spatial and temporal attributes synthetically. It is important to
public safety and urban policy-making. For instance, if a crowd gathering can
be detected timely, the risks to public safety may be decreased beforehand.
One negative example mentioned in [3] is that a tragic stampede resulting in
36 people killed and 49 injured took place in Shanghai. There are more than
300,000 people flocked for a popular light show on New Year’s Eve (Dec. 31th,
2014). The declaration from the authority reflects that the correct estimation
of crowd size and well-preparation can avoid this event.

Existing urban anomaly detection methods can be divided into the point-based
method, line-based method, and region-based method by their detection
objective. The point-based method is usually used to detect abnormal points.
As an instance, spatial outliers detection is a typical scenario [4, 5].
Likewise, the trajectory anomalies detection can regard as a type of line-
based method [6, 7, 8, 9]. The target of the region-based method is to find
group anomalies or collective anomalies [10, 3]. Our goal is to detect
regional anomalies, which relates to the region-based method.

However, the previous region-based detection method usually involves fixed-
based regional partition. Both [10] and [3] partition a city into some regions
by major roads, e.g., highways and arterial roads. Such a partition approach
we refer to as a road-based method shown in Figure 1a. Another fixed-based
regional partition is grid-based partition shown as Figure 1b, which usually
used in some applications in the urban data mining, e.g., the crowd flows
prediction [11]. The grid-based method partitions a city into a grid map based
on the longitude and latitude where a grid denotes a region. The big problem
caused by the fixed-based regional partition is data sparsity because the
distribution of observations is unbalanced in the whole area, which will
influence the detection results. Another issue is that the heterogeneity of
data will also affect detection [12].

To alleviate the influence of data sparsity and heterogeneity, we propose a
novel method to partition the area dynamically. Figure 1c illustrates the
process of the dynamic partition, in which the area number and shape are
changed with the time flow. The dynamic partition operates on locations and
readings directly. Thus, the data sparsity issue is negligible compared with
that caused by fixed-based partition method. The generated regions need to
satisfy two principles: locations are adjacent, and readings are similar.
Thus, data heterogeneity is not a highlighted problem anymore.

(a) Road based partition

(b) Grid based partition

(c) Dynamic partition

Figure 1: Different type of spatial partition.

The target of regional anomalies detection is to detect whether a region is
significantly different from others. Besides exploring the regional partition
approach, another critical question is to exploring a metric to measure the
abnormality. In urban data, this metric is supposed to have a relationship
with the temporal attributes or both spatial and temporal attributes. On the
one hand, we can not assume an observation is abnormal by only judging its
value is lower or higher than others in spatial distribution. E.g., the bike
drivers in the center of a city are always much more than the ambient areas.
Thus it is unreasonable to regard an area with a lower or higher driver number
as an abnormal area. On the other hand, using only the fluctuation of the time
series to judge whether a timestamp is abnormal is also not enough. The reason
is there are too many factors like workday or raining weather that will
influence the readings. Inspired by the study of [13], we adopt the divergence
as the metric. It is calculated considering the readings belonging to both a
target region and its surrounding regions. The difference with [13] is the
divergence plays two roles in the paper. Besides the direct anomaly metric,
the divergence is also used as a weight. So, we also call the divergence as
relative divergence.

The choice that using the relative divergence to describe the fundamental
change caused by an unusual event is adaptive. As an instance, although the
number of bike drivers in a city is different on the raining day and sunny
day, each station should have a stable relative divergence under these weather
conditions. A constant relative divergence means each station has the same
trend: riders are less on a raining day and more on a sunny day as common
sense. If the drivers of a station have no such tendency, we believe there is
an anomaly. E.g., a concert that causes a big riders’ number. In other words,
when the relative divergence changes massively, there may be an anomaly we
want to track.

Combining dynamic regions and the relative divergence, we propose an
unsupervised REgional Anomaly Detection framework, entitled ReAD, to detect
regional anomalies in this paper. Explicitly, we first partition the
observations using its geographic locations and readings. Each of the
generated regions should always hold the following two principles: locations
are adjacent, and readings are similar. Then, we calculate the relative
divergence of each region. Finally, finding the anomalies by the calculated
divergence. These processes keep the final anomalies are regional and deviate
from the normal regionals with comparable values.

Our proposed framework involves dynamic region partition instead of the fixed-
based partition for the following advantages:

  * 1)

Dynamic region partition gathers similar readings within the nearby location
together directly. It is capable of overcoming the data-sparse in the fixed-
based partition method and addressing the heterogeneity of the given data.

  * 2)

Dynamic region partition has no grid size choice to affect the results of
detection. However, the grid size is essential in the grid-based partition. It
also no need to combine the final nearby detected regions, which should be
operated in the road-based approach.

Temporal attributes play two roles in the proposed framework for different
applications. One is to assist the detection considering some scenarios
emphasize spatial anomalies, e.g., credit anomaly detection. Another is to
investigate the fluctuation of the divergence. The reason is most situations
can not generate anomalies without temporal information, e.g., bike drivers
anomaly detection. Thus, we design two approaches to generate the final
regional anomalies. Correspondingly, one is called weighted approach, and
another is called wavy approach.

Our contributions are three-fold:

  * •

A partition method is proposed to partition regions dynamically. Each
generated region satisfies two principles: locations are adjacent, and
readings are similar.

  * •

An unsupervised framework ReAD is proposed to address regional anomaly
detection. It heuristically involves dynamic region partition, regional
divergence calculation, and anomalous region generation.

  * •

We evaluate the proposed framework by a synthetic spatio-temporal dataset and
two real-world applications. The results demonstrate the effectiveness and
practicability of the framework.

In the following, we first present the preliminary notations and definitions,
and the overview of the proposed framework ReAD in Section 2. Then, we
elaborate on the proposed framework in Section 3. The experiments and analysis
are discussed in Section 4, followed by an introduction to the related work in
Section 5. Finally, we conclude the paper in Section 6.

##  2 Overview

In this section, we introduce some preliminary notations, definitions, and the
main structure of the proposed framework.

###  2.1 Preliminary

######  Definition 2.1 (Region).

In this study, all observations $s_{t}$ at the time slot $t$ are partitioned
into some regions $r_{t}=\left\\{r_{t,1},r_{t,2},\cdots,r_{t,n_{t}}\right\\}$,
where $n_{t}$ is the number of regions at time slot $t$. Each region needs to
satisfy the following two criteria:

  * 1)

Adjacent locations,

  * 2)

Similar readings: $\forall v_{i},v_{j}\in r_{t,k}$,
$dist(v_{i},v_{j})\leq\delta_{d}$.

######  Definition 2.2 (Regional Anomaly).

A regional anomaly is a region that deviates significantly from the nearby
regions or whole regions. In other words, the distribution of each point in a
region deviates significantly from other points outside it.

Problem Definition. Given a data stream $s$, each element of it is a triplet
$\langle$ $l$, $t$, $v$ $\rangle$ representing that a value $v$ is observed in
geographic coordinate (i.e., longitude, latitude) $l$ at time slot $t$. We aim
to detect $\varrho$ anomalous regions
$\mathcal{A}_{t}=\left\\{r_{t,1},r_{t,2},\cdots,r_{t,\varrho}\right\\}$ at
time epoch $t$.

(a)

(b)

Figure 2: An instance of the problem definition, the numbers colored with
purple are the mean value of each region (Best seen in color).

Figure 2 is an instance to illustrate the problem definition. There are two
regional anomalies ($a_{i},i=1,2$) detected from three consecutive time
interval [$t_{1},t_{3}$] in Figure 2a. Figure 2b elaborates the locations and
readings of each timestamp. The numbers colored with purple are the mean value
of each region. As it shows, the regions are partitioned dynamically by the
geo-coordinates and readings of observations at each time slot. E.g., all
observations are partitioned into three regions at time slot $t_{1}$. However,
there are four regions at time slot $t_{2}$, because the readings in $r_{4}$
have changed. The proposed method detects abnormal regions combining spatial
and temporal attributes. For example, $r_{4}$ at time slot $t_{2}$ is an
unusual region since their readings entirely different from the readings of
region $r_{1}$. Besides, $r_{2}$ at $t_{3}$ is an abnormal region because the
readings go up sharply compared with the other two regions.

As a conclusion, we can not identify the anomalies just by spatial attribute
and also can not identify the anomalies only by temporal attribute. The task
of regional anomaly detection involves both of them.

Figure 3: The overall structure of our proposed framework.

###  2.2 Framework

The main structure of our proposed framework is illustrated in Figure 3. The
two main parts are dynamic region partition and regional anomaly detection.
For the dynamic region partition, the key idea is to partition locations and
cluster readings at each time slot, respectively. Then, an intersection
operation is carried out to obtain final regions. These two steps keep
locations adjacent and readings similar in each generated region. To the best
of our knowledge, it is the first time to use intersection operation in the
regional partition. It is a concise and efficient approach to get the target
regions. For regional anomaly detection, we first calculate a divergence for
each region. Then, two approaches are proposed to address different scenarios.
A weighted method is used in spatial anomaly regions detection, in which the
weights are calculated considering temporal information. A wavy approach is
proposed to spatio-temporal anomaly detection. All these steps will be
described in detail in Section 3.

##  3 Methodology

In this section, we elaborate regional partition, regional divergence
calculation, and anomalous region generation of the proposed framework shown
as Figure 3.

###  3.1 Regional Partition

Regional partition is an essential part of the framework. Its output is
regions, in which observations have adjacent locations and similar readings.
It is challenging to consider locations and readings simultaneously. The
reason is the location of an observation is always fixed, but its reading will
change with time. The location and reading have different features. From a
clustering perspective, the task of regional partition essentially is a
cluster problem, which can be addressed by unsupervised cluster algorithms.
Putting above two knots together, we develop an effective method to solve the
problem of regional partition. The technique first cluster them individually,
then intersect these clusters. Thus, each of the final regions satisfies the
principles of adjacent locations and similar readings.

Before introducing the partition approach, it needs to explain the reason why
we need a novel partition method. The critical point is that the partition
regions we need are arbitrarily shaped and should form a full coverage for all
observations. It makes most of the cluster methods are infeasible. As an
instance, the density-based clusters (e.g., DBSCAN [14]) can cluster
arbitrarily shaped regions but can not ensure them cover all observations. It
is also a challenge to choose proper parameters (e.g., the $MinPts$ in
DBSCAN). The expectation of arbitrary shape and full coverage makes a
customized cluster approach necessary.

Partition locations. Inspired by CFDP (Clustering by Fast Search and Find of
Density Peaks) [15], we propose a partition algorithm (or cluster algorithm)
based on Delaunay triangulation [16] to address above challenges.

A Delaunay triangulation is also known as a Delone triangulation. Its
objective is to maximize the minimum angle of all the angles of the triangles
in the triangulation. We use Delaunay triangulation mainly because it is
parameters free.

(a) Delaunay triangulation

(b) Density calculation

(c) Partition process

(d) Region partition results

Figure 4: Partition algorithm on locations.

Figure 4 with four subfigures is an illustration of the proposed partition
algorithm. Given some geographic coordinates $s_{t}$, the generated Delaunay
triangulation $\mathcal{T}_{s_{t}}$ is a connected graph, in which a vertex
represents a location, and an edge connects two adjacent locations. Figure 4a
is a diagram of Delaunay triangulation. If we cut the longest edge in
sequence, there will be two clusters shown as Figure 4d. It also follows the
rule that the edge length between clusters is longer than the edge length
inside. Through analyzing the two clusters, there is a truth that the points
in the boundary of a cluster usually have longer edges to connect with other
clusters. One step closer, these boundary points typically have a higher
variance on the length of edge around themselves than that of other points.
Thus, we define the density of each location $l_{i}$ by:

$\displaystyle\rho_{l_{i}}=\log\left(\frac{1}{\sigma_{l_{i}}}\right),$ (1)

Let $\eta_{i}=\left\\{l_{j},l_{j+1},\cdots,l_{j+k-1}\right\\}$ denote $k$
neighbors of $l_{i}$ (e.g., the T location in Figure 4b owns $k=7$ neighbors),
the $\sigma_{l_{i}}$ is calculated with the following equations:

$\displaystyle\sigma_{l_{i}}$
$\displaystyle=\sqrt{\frac{1}{k}\sum_{{l_{j}}\in\eta_{l_{i}}}{\left(e_{l_{i},l_{j}}-\mu_{l_{i}}\right)^{2}}},$
(2) $\displaystyle\mu_{l_{i}}$
$\displaystyle=\frac{1}{k}\sum_{{l_{j}}\in\eta_{l_{i}}}{e_{l_{i},l_{j}}},$ (3)
$\displaystyle e_{l_{i},l_{j}}$ $\displaystyle=\lVert l_{i}-l_{j}\rVert_{2},$
(4)

where, $\lVert\cdot\rVert_{2}$ is the Euclidean norm. The numbers (round to
two decimal places) in Figure 4b are calculated densities for each location.
As we expect, the density of the points in the boundary is usually smaller
than that in the central position. It is note that here using the variance
$\sigma_{l_{i}}$ instead of the average $\mu_{l_{i}}$ to calculate density
$\rho_{l_{i}}$. The reason is the variance $\sigma_{l_{i}}$ is stable no
matter for sparse or dense points. This feature is useful to alleviate the
influence of the data heterogeneity.

After obtaining the density, the task is to allocate each of the locations to
a latent cluster. As the previous conclusion, the density in the central
position is usually higher than that in the boundary. So there are three steps
to get clusters. Firstly, let each point go with the direction of the density
higher than itself. Then, choose the locations with the top density as the
center of each cluster. Finally, gather the points to each cluster using the
opposite direction with the first step recursively. Following the CFDP,
$\delta_{l_{i}}$ is defined as the minimum distance between the location
$l_{i}$ and any other locations with higher density:

$\delta_{l_{(i)}}=\left\\{\begin{array}[]{lr}\min\limits_{j<i}\left(e_{l_{(i)},l_{(j)}}\right),&i\geq
2;\\\ \max\limits_{j\geq
2}\left(\delta_{l_{(j)}}\right),&i=1.\end{array}\right.$ (5)

where, the $l_{(i)}$ is the reordering of $l_{i}$:
$\rho_{l_{(1)}}\geq\rho_{l_{(2)}}\geq\cdots\geq\rho_{l_{(i)}}\geq\cdots$.
According to $\delta_{l_{i}}$, each location owns a parent that has the
minimum distance with itself, except the one with the biggest minimum
distance.

Figure 4c illustrates the process of clustering using the density
$\rho_{l_{i}}$ and the minimum distance $\delta_{l_{i}}$ of each location. The
locations with the biggest $c=2$ readings
$\gamma_{l_{i}}=\rho_{l_{i}}\times\delta_{l_{i}}$ are first chosen as the
centers of clusters, and then other locations recursion to one of the centers
following their parent locations. For example, $A$ and $B$ are the chosen two
centers. $l_{2}$ belongs to $A$ by the path $l_{2}\rightarrow l_{1}\rightarrow
A$. Likewise, $l_{3}$ belongs to $B$. Figure 4d illustrates the final
clustering results. Benefit from the elaborate density function, the proposed
algorithm has fewer parameters than CFDP.

Cluster readings. Compared with partition locations, cluster readings is a
relatively straightforward process. Any cluster method can finish this step
because the condition of similar readings is always satisfied in the same
cluster. As an alternative approach, we use the CFDP with the default setting
to cluster the readings at time slot $t$. Nevertheless, KNN or other cluster
methods are also feasible.

Intersect clusters. We denote the location clusters at time slot $t$ by
$\mathcal{L}=s_{t}/l=\left\\{c_{t,1}^{(l)},c_{t,2}^{(l)},\cdots,c_{t,n_{t}(l)}^{(l)}\right\\}$
and the reading clusters at time slot $t$ by
$\mathcal{V}=s_{t}/v=\left\\{c_{t,1}^{(v)},c_{t,2}^{(v)},\cdots,c_{t,n_{t}(v)}^{(v)}\right\\}$
where $n_{t}(l)$ is the location cluster number and $n_{t}(v)$ is the reading
cluster number. Thus, the final partition regions $r_{t}$ are their
intersection:

$\displaystyle
r_{t}=\mathcal{L}\cap\mathcal{V}=\left\\{r_{t,1},r_{t,2},\cdots,r_{t,n_{t}}\right\\},$
(6)

The intersection operation keeps each of the final regions satisfies the
principles of adjacent locations and similar readings. Figure 5 illustrates
the whole partition process. There are 5 location clusters, 2 value clusters,
and the 6 final regions in this example.

Figure 5: The process of partition regions.

The final partition regions are dynamic with different locations or readings.
Actually, the location partition almost changeless until the points change
their positions (such as increasing the bike stations). At this moment, this
partition can be regarded as repartition the points inside some fixed regions
according to their readings at each time slot.

###  3.2 Regional Divergence Calculation

We calculate the metric of abnormality by the relative divergence of each
region. According to our analysis mentioned in Section 1, the relative
divergence is essential when considering the regional anomaly detection. The
reason is the external factors (e.g., sunny or raining) except for the unusual
event (e.g., a concert) is changing with time. We assume that the relative
divergence is stable under the condition of external factors, but drastic
fluctuation under the abnormal events. Motivated by the works on collective
anomaly detection [13, 17, 18], we use the Kullback-Leiber (KL) divergence to
calculate the relative divergence:

$\displaystyle\mathfrak{D}_{KL}(p,q)=\mathbb{E}_{p}\left[-\log\frac{p}{q}\right],$
(7)

Specifically, we measure each region $r_{t,i}$ with the relative divergence
from two aspects, one is local divergence, and another is global divergence.
The local divergence involves the probability density $p_{r_{t,i}}$ and the
distribution $p_{c_{t,i}^{(l)}}$, where $c_{t,i}^{(l)}$ is the location
cluster containing the region $r_{t,i}$. The global divergence involves the
probability density $p_{r_{t,i}}$ and the distribution $p_{\lnot r_{t,i}}$ of
the rest regions except $r_{t,i}$ at time slot $t$. We investigate Kernel
Density Estimation (KDE) for calculating these distributions:

$\displaystyle
p_{\Re}\left(v_{\iota}\right)=\frac{1}{\left|\Re\right|}\sum\limits_{j\in\Re}{\kappa\left(v_{\iota},v_{j}\right)},\quad\Re\in\left\\{r_{t,i},c_{t,i}^{(l)},\lnot
r_{t,i}\right\\},$ (8)

where, the kernel is Gaussian kernel:

$\displaystyle\kappa\left(v_{\iota},v_{j}\right)=(2\pi\sigma)^{-\frac{1}{2}}\exp(-\frac{\lVert
v_{\iota}-v_{j}\rVert^{2}}{2\sigma^{2}}),$ (9)

Thus, we can generate the regional divergence $\mathfrak{D}_{r_{t,i}}$ with:

$\displaystyle\mathfrak{D}_{r_{t,i}}=\lambda\cdot\mathfrak{D}_{KL}^{local}(p_{r_{t,i}},p_{c_{t,i}^{(l)}})+(1-\lambda)\cdot\mathfrak{D}_{KL}^{global}(p_{r_{t,i}},p_{\lnot
r_{t,i}}),$ (10)

where, $\mathfrak{D}_{KL}^{local}(p_{r_{t,i}},p_{c_{t,i}^{(l)}})$ is the local
divergence (e.g, $\mathfrak{D}_{KL}(p_{r_{1}},p_{r_{2}})$ in Figure 5), and
$\mathfrak{D}_{KL}^{global}(p_{r_{t,i}},p_{\lnot r_{t,i}})$ is the global
divergence (e.g., $\mathfrak{D}_{KL}(p_{r_{1}},p_{\cup r_{i},i=2,3,4,5,6})$ in
Figure 5). $\lambda\in[0,1]$ is a trade off between the local and the global
divergence.

###  3.3 Regional Anomalies Detection

The temporal dimension plays a vital role in our framework. We explore two
approaches to cover two types of situations. The first one is to use temporal
information to help the detection of spatial anomalies where spatial anomalies
are conspicuous, e.g., credit anomaly detection. We call this approach as a
weighted approach. The second one is to use the fluctuation of the divergence
series to decide whether a region is abnormal or not, e.g., NYC bike anomaly
detection. In this situation, spatial attributes are not enough to make a
decision. We call this approach a wavy approach.

Figure 6: An example of weighted approach.

Weighted approach uses temporal information to weight the regional divergence.
Before adopting temporal information, each point at time slot $t$ should be
allocated a divergence instead of using the regional divergence because the
locations belong to a different region with the time flow. An approach is to
assign the divergence of the region to each location contained by this region.

$\displaystyle\alpha_{j}^{t}=\mathfrak{D}_{r_{t,i}},\quad j\in r_{t,i},$ (11)

When each point at time slot $t$ owns a divergence, we consider the sequence
of each point during a period $\left[t-\tau+1,t\right]$. Figure 6 illustrates
the weighted approach. The fact of the divergence of a location goes up with
time means the deviation of the point changes bigger and bigger. So we need to
pay more attention to such a location. Consequently, such location should have
a big weight, e.g., the point marked 1, which has weight 1.56. On the
contrary, the decreasing trend of the divergence means the deviation changes
smaller and smaller, e.g., the point marked 2, which has weight 0.80. It is
reasonable to assign a small weight. Assuming the sequence of a point is
$\alpha_{i}^{\left[t-\tau+1,t\right]}$, we calculate the weight at time slot
$t$ by:

$\displaystyle w_{i}^{t}$
$\displaystyle=\frac{2}{1+\exp(-\hat{\alpha}_{i}^{t})},$ (12)
$\displaystyle\hat{\alpha}_{i}^{t}$
$\displaystyle=\frac{1}{\tau}\sum\limits_{j=1}^{\tau-1}\vartheta^{j}\cdot(\alpha_{i}^{t}-\alpha_{i}^{t-j})$
(13)

where, $\vartheta\in(0,1]$ is a decay factor. The value of $w_{i}^{t}$ has the
following implication: $w_{i}^{t}>1$ means the deviation of the value is
increscent, $w_{i}^{t}<1$ denotes the deviation of value is decrescent, and
$w_{i}^{t}=1$ means the value is identical.

After generating the weight of each point, we update the divergence of each
region with:

$\displaystyle\mathfrak{D}_{r_{t,i}}=\frac{1}{\left|r_{t,i}\right|}\sum\limits_{j\in
r_{t,i}}w_{j}^{t}\cdot\alpha_{j},$ (14)

For more robust detection results, an adaptively momentum-based method is used
to generate the final abnormal regions:

$\displaystyle mean^{t}=\jmath\cdot mean^{t-1}+(1-\jmath)\cdot
mean\left(\mathfrak{D}_{r_{t}}\right),$ (15) $\displaystyle
std^{t}=\jmath\cdot std^{t-1}+(1-\jmath)\cdot
std\left(\mathfrak{D}_{r_{t}}\right),$ (16)
$\displaystyle\mathcal{A}_{t}=\left\\{r_{t,i}\left.\Big{|}\right.\mathfrak{D}_{r_{t,i}}\geq
mean^{t}+\frac{mean^{t}}{r_{t,i}}\cdot std^{t}\right\\},$ (17)

where, $\jmath$ is a trade off between historical value and current value.
$\mathfrak{D}_{r_{t}}$ means the divergence of all regions at time slot $t$.
$mean(\cdot)$ and $std(\cdot)$ are the mean value function and the standard
deviation function, respectively. Eq. (17) is also used in [12].

Wavy approach considers the fluctuation of the divergence series directly.
Because the generated regions are dynamic at different time slot, we copy the
regional divergence to each point similar to the weighted approach by Eq.
(11). The difference between the wavy approach and the weighted approach is
the role of the temporal information. In the wavy approach, we directly detect
anomalies on the divergence series instead of weighting.

Figure 7: Divergence series in wavy approach.

Figure 7 is an example of divergence series. Usually, the divergence of each
point is stable. If there is a substantial fluctuation, we believe it is
abnormal, e.g., the positions 1 and 2 of the top line. Though some existing
methods can finish such a task, e.g., OC-SVM [19] and skyline detection
algorithm [20], we investigate a more simple and effective way to detect such
fluctuation:

$\displaystyle std_{i}^{t}=std\left(\alpha_{i}^{[t-\tau+1,t]}\right),$ (18)
$\displaystyle std^{t}=\jmath\cdot std^{t-1}+(1-\jmath)\cdot
mean\left(STD^{t}\right),$ (19) $\displaystyle mean_{i}^{t}=\jmath\cdot
mean_{i}^{t-1}+(1-\jmath)\cdot mean\left(\alpha_{i}^{[t-\tau+1,t]}\right),$
(20)
$\displaystyle\mathcal{A}_{\alpha}^{t}=\left\\{\alpha_{i}^{t}\left.\Big{|}\right.\alpha_{i}^{t}\geq
mean_{i}^{t}+\frac{mean_{i}^{t}}{\alpha_{i}^{t}}\cdot std^{t}\right\\},$ (21)

where,
$STD^{t}=\left\\{std_{1}^{t},std_{2}^{t},\cdots,std_{i}^{t},\cdots\right\\}$
means the collection of current standard deviation from each point. $std^{t}$
is a global standard deviation. The $\jmath$, $mean(\cdot)$, and $std(\cdot)$
have the same meaning with Eq. (15) and Eq. (16). After generating the point
anomalies, we can aggregate the anomalous points to generate the anomalies
$\mathcal{A}_{t}$ by the edges of Delaunay triangulation at time slot $t$.

Algorithm 1 summarizes the ReAD.

Input: Dataset $s$, current time slot $t$, $d_{c}$ and $n_{t}(v)$ in CFDP, the
number of location cluster $n_{t}(l)$, $\sigma$ in Gaussian kernel, detection
approach $ap$, other paramenters $\lambda$, $\tau$, $\vartheta$, and $\jmath$

Output: Anomalous regions $\mathcal{A}_{t}$

1 Construct the Delaunay triangulation $\mathcal{T}_{s_{t}}$ on $s_{t}$;

2 Clustering locations to $\mathcal{L}$ by (1-5);

3 Clustering readings to $\mathcal{V}$ by CFDP;

4 Partition $s_{t}$ to $r_{t}$ though $\mathcal{L}\cap\mathcal{V}$;

5 Calculate the divergence $\mathfrak{D}_{r_{t,i}}$ of each region using (10);

6 if  _$ap$ is weighted approach_ then

7 Generate the weights by (11-14);

8 Generate anomalous regions $\mathcal{A}_{t}$ by (15-17);

9

10else

11 Generate point anomalies $\mathcal{A}_{\alpha}^{t}$ by (18-21);

12 Aggregate $\mathcal{A}_{\alpha}^{t}$ to $\mathcal{A}_{t}$ using the edges
of $\mathcal{T}_{s_{t}}$;

13

14 end if

return _$\mathcal{A}_{t}$_

Algorithm 1 ReAD

##  4 Experiments

In this section, we first evaluate the proposed ReAD on a synthetic dataset
and compare it with state-of-the-art anomaly detection algorithms. Then, we
perform two case studies on real-world datasets to demonstrate the feasibility
of our approach in real-world applications.

###  4.1 Experiments Based on Synthetic Dataset

Due to there is no widely used standard benchmark for evaluating regional
anomaly detection algorithms, we construct a synthetic dataset for
quantitative analysis.

(a) Synthetic spatial coordinates.

(b) Base time-series.

Figure 8: Synthetic data generation.

Dataset Generation. There are five steps to generate data source. 1) Generate
four regions. To mimic real spatial locations, we manually generate the
latitude and longitude of each point by a GeoJSON
generator111http://geojson.io. As shown in Figure 8a, the generated spatial
distribution is designed to present different densities, e.g., $R_{1}$ is
sparser than other regions. Besides, each region has a different size and
shape. 2) Generate time-series readings for each location. The time-series is
sampled from a base curve: $y_{t}=y_{0}\cdot\left|\sin(x_{t})\right|+b+g$,
where $y_{0}$ is an amplitude, $b$ is a bias, and $g$ means a Gaussian noise.
Figure 8b depicts two groups of base time-series we set for the synthetic
coordinates. The upper group with $y_{0}=3$, $b=1$ is assigned to $R_{1}$ and
$R_{4}$, and the lower group with $y_{0}=1$, $b=0.5$ belongs to $R_{2}$ and
$R_{3}$. 3) Inject external influences. We randomly inject some external
influences to the base time-series, e.g., $e_{1}$, $e_{2}$, and $e_{3}$ in
Figure 8b, by changing the base readings in the same trend (increase or
decrease simultaneously). The external influences are set to mimic the
influences caused by external factors, e.g., weather and holiday. 4) Generate
readings by sampling. We generate the time-series of each location from the
base time-series of its belonging region by adding another Gaussian noise for
each time. The Gaussian noise is set to mean 0 and standard deviation 0.5, and
the sampling step is set to 0.1 in our experiments. Such generation type on
time-series is a simplification from the actual scenario: typical periodicity
and changing trend influenced by external factors, which also can be regarded
as a microform of NYC bike dataset. 5) Inject anomalies. After generating the
time-series for each location, we randomly choice adjacent locations in the
same region and a period to inject a defined anomaly. Specifically, we add to
or subtract from the chosen series with a random, but constant value
$\nu\in\left[1.5,2.0\right]$. An example of injecting anomaly is shown as
Figure 9. Summarily, the generated four regions contain 223 coordinates, and
each of them involves a time-series with 6402 time-slots. Besides, the number
of external influences is 82, and the number of injected anomalies is 200.

(a) An abnormal region.

(b) An abnormal time-series.

Figure 9: An example of injected anomaly.

Baselines. We compare ReAD with the following baselines, which are classical
and widely used anomaly detection methods.

  * •

Hotelling’s $T^{2}$. It is a generalization of Student’s t-statistic that is
used in multivariate hypothesis testing [21].

  * •

RKDE. It is the Robust Kernel Density Estimation [22]. A Gaussian kernel with
a standard deviation of 1.0 and the Hampel loss function are used.

  * •

LRT. It fits a Poisson distribution on the historical data and uses likelihood
ratio test as the anomaly score.

  * •

SAPRD It designs multi-constrained graphs and local density to detect spatial
anomaly regions [12].

  * •

MDI-KDE. MDI is a Maximally Divergent Intervals algorithm [13].

Besides the baselines, we also show the effectiveness of both weighted
approach and wavy approach of the ReAD. We use F1-Score with an Intersection
over Union (IoU) as the metric to quantify the performance. It is a hit if the
IoU has an overlap over 50%.

For Hotelling’s $T^{2}$, RKDE, and LRT, we obtain regional detections from
those point-wise baselines by gathering contiguous detections at each time
slot based on the edges of the Delaunay triangulation constructed on spatial
coordinates. For RKDE, we adopt a Gaussian kernel with a standard deviation of
1.0 and the Hampel loss function as the setting in [13]. The LRT is set as
[10]. The SAPRD and MDI-KDE keep the same parameters as they are used in [12]
and [13], respectively. The weighted approach and wavy approach are set with
the same parameters to compare with other baselines. The numbers of location
cluster $n_{t}(t)$ and value cluster $n_{t}(v)$ are set as 4 and 2,
respectively. Besides, $\lambda$, $\vartheta$, and $\jmath$ are set to 1, and
$\tau$ is set to 10. $\sigma$ is set by Scott’s rule. Finally, the average of
10 runs with the same hyperparameters is reported.

Table 1:  Performance comparison between baselines and our method on synthetic data. Methods | Precision | Recall | F1 Score
---|---|---|---
Hotelling’s $T^{2}$ | 0.16 | 0.96 | 0.27
RKDE | 0.06 | 0.72 | 0.10
LRT | 0.09 | 0.56 | 0.16
SAPRD | 0.10 | 0.60 | 0.17
MDI-KDE | 0.36 | 0.56 | 0.44
ReAD (weighted) | 0.50 | 0.60 | 0.55
ReAD (wavy) | 0.71 | 0.68 | 0.69

Performance Analysis. Table 1 summarizes the detection results of different
baselines and the proposed approaches. ReAD (weighted) denotes the weighted
approach, and ReAD (wavy) denotes the wavy approach of the ReAD. They achieve
F1-score gains over the baselines as the table shows. These improvements
demonstrate the superior performance of the proposed ReAD methods.
Specifically, the first three baselines perform poorly. The reason is they are
point anomaly detection methods, which only utilize the temporal information
and can not make good use of the spatial information. Likewise, SAPRD does not
obtain a good score for the reason of losing temporal information. Although
MDI-KDE considers spatial and temporal information simultaneously, it is still
worse than ReAD because its spatial partition is always rectangular. On the
contrary, the proposed ReAD partition the regions with arbitrary shapes.
Compared with the ReAD (weighted), ReAD (wavy) has a better performance. It
proves spatio-temporal anomaly detection is more effective than spatial
anomaly detection in this synthetic task. We also notice that Hotelling’s
$T^{2}$ and RKDE have very high recall values but low precision values. The
reason is they radically regard most of the candidates as anomalies.
Otherwise, they will get close 0 precision values. However, our methods have a
relative balance on precision and recall, thus achieve better F1 scores.

Figure 10: Robustness comparison between baselines and our method on synthetic
data. The value means the ratio of the detected anomalies which overlap with
the external influence in whole detected anomalies.

Robustness Analysis. We further design an experiment to compare the robustness
of our framework. The ratio of detected anomalies overlapping with the
external influence is compared — the lower of the ratio, the better of the
robustness. As can be seen in Figure 10, ReAD is capable of finding anomalies
even with external influences. ReAD (weighted) and SAPRD have a lower ratio
than others because they do not care about the continuity of time but detect
spatial anomalies. However, others focus on temporal information, so they are
deeper influenced by external changes. Nevertheless, ReAD (weighted) and ReAD
(wavy) have better performance than others, which benefits from the dynamic
region partition and relative divergence.

Discussion. Although we have generated data source manually and designed a
quantitative experiment to evidence the effectiveness of the proposed ReAD, it
is not very convincing that the ReAD can always outperform other anomaly
detection methods. One reason is the data synthesis process may implicitly
adopt the same assumption of the proposed method. Another reason is we can not
perform a real quantitative evaluation on a real-life dataset due to a lack of
labels. This situation can happen in almost any unsupervised detection
framework [10, 3]. It also reflects the fact that the definition and solution
of anomaly detection vary from scenario to scenario. Nevertheless, we can
argue that the proposed ReAD is still a solution for the regional anomaly
detection and work well under a certain situation. Beside, building a real-
life quantitative evaluation will be as our future work. Instead of
quantitative evaluations on real-life datasets, the following content shows
two case studies to demonstrate the feasibility of our approach.

###  4.2 Case Study I: Credit Detection of Companies

In the case, the weighted approach of ReAD is applied to detect the credit
anomaly of companies. The dataset collected from a city of China contains
company names and their credit scores. Typically, the credit score of a
company does not change or change with a small value within a long period.
Thus, there is nothing wrong with a company when checking the fluctuation of
the score-series if it always keeps a lower score. On the contrary,
considering the credit score of other companies around it is more useful. That
is what the weighted approach wants to address. The dataset contains 3434
companies. The parameters are set to $n_{t}(l)=6$, $n_{t}(v)=3$,
$\lambda=\tau=1$, $\vartheta=\jmath=0$ because just one time slot is involved,
and $\sigma$ is set by the Scott’s rule.

Figure 11: The potential anomaly pattern about a city of China.

Figure 11 presents the detection results. Figure 11b is the detection results
with top 20 anomalous regions marked with red triangles. As expected, regions
with quite low credit scores are recognized by the proposed ReAD method, e.g.,
A and B in Figure 11c and Figure 11d, respectively. A word cloud is generated
with the names of the detected companies. The visualization is shown as Figure
11e, in which the “trade” indicates the trade industry has a potential poor
credit. The case proves the capability of our method to do decision making and
supervision.

Our framework is designed based on the regional partition, which is meaningful
in the above scenario. Because each region has different economic conditions,
the companies in different regions have different credit scores. Thus, the
collected score is heterogeneous on spatial distribution. The regional
detection could find the clusters of low-credit companies, and further use to
diagnosis industry credit and manage regional economic.

###  4.3 Case Study II: Events Detection in New York City

To demonstrate the feasibility of the wavy approach for real problem, we also
perform events detection in New York City using its bike rental data, which is
generated by the bike-sharing system222https://www.citibikenyc.com/system-
data. We count the hourly check-out of each station from 6/1/2018 to
8/31/2018, which has 808 bike stations and 2208 time slots. Figure 12 is an
exmaple of distribution of the bike stations (the left part) and a check-out
series of a staion from 6/1/2018 to 6/30/2018(the right part). We evaluate our
method by the corresponding events reported by
nycinsiderguide333https://www.nycinsiderguide.com/ refering to the study of
[10, 3]. The details of the 15 primarily reported events are listed in Table
3. The information in this table is collected manually.

Figure 12: NYC bike dataset.

Table 2 presents the hit events of our method and different baselines. The top
15 anomalies detected by these models are checked. The ‘hit’ means the
detected results have an overlap with any address and corresponding start or
end time in Table 3. The parameters are set with the same as the experiments
designed on the synthetic dataset. ReAD (wavy) hits 6 events and other methods
hit less than or equal with 4 events. It shows that our method has an
advantage of detecting real-world events without knowing any other external
influences, e.g., weather. It indicates that using regional partition and the
divergence in ReAD (wavy) works well on spatio-temporal anomaly detection.

Table 2:  Events hit on NYC bike dataset. Methods |  Hit Event IDs
---|---
Hotelling’s $T^{2}$ |  8
RKDE |  None
LRT |  12
SAPRD |  3, 12
MDI-KDE |  3, 6, 12, 15
ReAD (weighted) |  4, 6, 12, 13
ReAD (wavy) |  3, 4, 6, 8, 12, 13
Table 3:  Events reported by nycinsiderguide.com |  Event Name |  Address |  Start Time |  End Time
---|---|---|---|---
1 |  Governors Ball Music Festival |  Randall’s Island |  06/01 11:45AM |  06/01
2 |  Taste of Times Square |  46th Street |  06/04 5:00PM |  06/04 9:00PM
3 |  Central Park Taste of Summer |  Central Park |  06/06 7:00PM |  06/06 11:00PM
4 |  AVP(Volleyball) New York City Open |  Tribeca Courts |  06/07 8:00AM |  06/10 6:00PM
5 |  National Puerto Rican Day Parade |  Fifth Avenue, 44th to 79th Street |  06/10 11:00AM |  06/10 5:00PM
6 |  Museum Mile Festival |  Fifth Ave, 82nd to 105th Street |  06/12 6:00PM |  06/12 9:00PM
7 |  NY Philharmonic Concerts in the Parks |  Central Park |  06/13 8:00PM |  06/13 9:30PM
8 |  American Crafts Festival at Lincoln Center |  Lincoln Center |  06/14 10:00PM |  06/14 7:00PM
9 |  Bryant Park Film Festival |  Bryant Park |  06/18 8:00PM |  06/18 9:00PM
10 |  Macy’s July 4th Fireworks |  East River |  07/04 9:25PM |  07/04
11 |  FREE Broadway in Bryant Park |  Lawn 42nd St and 6th Ave |  07/06 12:30PM |  08/10 1:30PM
12 |  Riverflicks FREE Movies in Hudson River Park |  Adults: Pier 63 at W. 23rd Street |  07/11 8:30PM |  07/11
13 |  Riverflicks FREE Movies in Hudson River Park |  Kids: Pier 46 at Charles Street |  07/13 8:30PM |  07/13
14 |  Jay Z & Beyoncé OTR II |  MetLife Stadium |  08/05 7:30PM |  08/05
15 |  Battery Dance Festival NYC |  Battery Park City |  08/11 7:00PM |  08/17 9:00PM

##  5 Related Work

###  5.1 Anomaly Detection

As a critical problem in practical applications, anomaly detection has been
studied extensively in the past decades [1, 23]. In urban computing, the form
of data is usually spatio-temporal data, in which the readings are influenced
by many factors, e.g., location, time, and weather, etc. Thus, these anomaly
detection methods for univariate time series [24, 25], multivariate time
series [26], and spatial outliers [4, 5] are unsuitable to the urban scenario.
The main reason is they ignore the joint representation of spatial and
temporal attributes. In this paper, we focus on urban anomaly detection.

A direction to explore the urban anomaly detection is to use the movement of
the observations (e.g., bike, taxi, and crowd). Because these movements
generate a lot of trajectories every day, trajectory anomalies detection is a
direct way in urban anomaly detection. [6] computed the average direction of
each spatial grid and identified an anomalous trajectory if its covered grids
exist some unexpected behaviors. In addition to the above two approaches. [7]
proposed a graph-based method to glean the problematic design in urban
planning. Besides, some supervised methods are also explored to detect
anomalous trajectory shapes [8, 9].

Considering the information of the observations from the statistical
perspective, another direction to investigate the urban anomaly detection is
to exploit the collected readings of spatial locations on time interval.
Different from the trajectory anomalies detection addressed by line-based
methods, group anomalies (or collective anomalies, regional anomalies) are
what point-based or region-based approach focuses. [10] first partition a city
into some regions by major roads, such as highways and arterial roads. The
generated regions are the minimal unit to extract statistic features, like
taxi amount or bike amount at each time interval. Then, detected the anomalies
on a probabilistic model. [3] used the same partition strategy as [10] and
identified anomalies by the changes of similarity measurement (Pearson
Correlation Coefficient) between the target region and other historically
similar regions. We focus on regional anomalies detection in this paper.
Different from previous approaches built on the fixed partition, the proposed
framework is designed based on the dynamic region partition, which alleviates
the sparse and heterogeneity of data distribution from the beginning.

###  5.2 Regional Partition

The dynamic region partition involves dynamic clusters. Despite many
clustering algorithms including K-means [27] and DBSCAN [14] can group similar
points to several clusters, they do not address the fundamental necessities of
our regional partition: arbitrarily shape and full-coverage, and do not take
into account spatial information exactly. [28] first identified the set of
core locations across all timestamps and then grew around the core locations
at every time stamps to capture the dynamic behavior occurring at the
boundaries. However, the clusters are also not full-coverage clusters. [4]
used a multilevel and constrained Delaunay triangulation to detect spatial
point event outliers. Different from their cutting approach between nodes, we
cluster locations through the definition of node density. Such density
definition can avoid the error caused by the adaptive coefficient and reduce
the cost of computation.

##  6 Conclusion

In this paper, we propose a novel framework ReAD to detect regional anomalies.
The framework partitions regions according to coordinates proximity and
readings similarity on spatial locations and non-spatial attributes at each
time slot. To cluster the geographical locations, we propose a clustering
algorithm based on Delaunay triangulation. Then, the abnormal metric of each
region is calculated by the relative divergence. Based on the divergence, two
types of regional anomaly detection approach are proposed to address different
scenarios which use temporal information differently. We finally evaluate the
proposed framework on the elaborate synthetic dataset and other two real-world
applications. They all demonstrate the effectiveness and feasibility of the
proposed framework.

## References

  * [1] Varun Chandola, Arindam Banerjee, and Vipin Kumar.  Anomaly detection: A survey.  ACM Comput. Surv., 41(3):15:1–15:58, 2009.
  * [2] Yu Zheng, Licia Capra, Ouri Wolfson, and Hai Yang.  Urban computing: concepts, methodologies, and applications.  ACM Transactions on Intelligent Systems and Technology (TIST), 5(3):38, 2014.
  * [3] Huichu Zhang, Yu Zheng, and Yong Yu.  Detecting urban anomalies using multiple spatio-temporal data sources.  Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 2(1):54, 2018.
  * [4] Yan Shi, Min Deng, Xuexi Yang, and Qiliang Liu.  Adaptive detection of spatial point event outliers using multilevel constrained delaunay triangulation.  Computers, Environment and Urban Systems, 59:164–183, 2016.
  * [5] Guanjie Zheng, Susan L. Brantley, Thomas Lauvaux, and Zhenhui Li.  Contextual spatial outlier detection with metric learning.  In KDD, pages 2161–2170. ACM, 2017.
  * [6] Yong Ge, Hui Xiong, Zhi-Hua Zhou, Hasan Timucin Ozdemir, Jannite Yu, and Kuo Chu Lee.  Top-eye: top-k evolving trajectory outlier detection.  In CIKM, pages 1733–1736. ACM, 2010.
  * [7] Wei Liu, Yu Zheng, Sanjay Chawla, Jing Yuan, and Xing Xie.  Discovering spatio-temporal causal interactions in traffic data streams.  In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1010–1018. ACM, 2011\.
  * [8] Xiaolei Li, Jiawei Han, and Sangkyum Kim.  Motion-alert: Automatic anomaly detection in massive moving objects.  In International Conference on Intelligence and Security Informatics, volume 3975 of Lecture Notes in Computer Science, pages 166–177. Springer, 2006.
  * [9] Xiaolei Li, Jiawei Han, Sangkyum Kim, and Hector Gonzalez.  ROAM: rule- and motif-based anomaly detection in massive moving object data sets.  In Proceedings of the Seventh SIAM International Conference on Data Mining, pages 273–284. SIAM, 2007.
  * [10] Yu Zheng, Huichu Zhang, and Yong Yu.  Detecting collective anomalies from multiple spatio-temporal datasets across different domains.  In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 2:1–2:10. ACM, 2015.
  * [11] Junbo Zhang, Yu Zheng, and Dekang Qi.  Deep spatio-temporal residual networks for citywide crowd flows prediction.  In AAAI, pages 1655–1661, 2017.
  * [12] Yan Shi, Min Deng, Xuexi Yang, and Qiliang Liu.  A spatial anomaly points and regions detection method using multi-constrained graphs and local density.  Transactions in GIS, 21(2):376–405, 2017.
  * [13] Bjorn Barz, Erik Rodner, Yanira Guanche Garcia, and Joachim Denzler.  Detecting regions of maximal divergence for spatio-temporal anomaly detection.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018\.
  * [14] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu.  A density-based algorithm for discovering clusters in large spatial databases with noise.  In KDD, volume 96, pages 226–231, 1996.
  * [15] Alex Rodriguez and Alessandro Laio.  Clustering by fast search and find of density peaks.  Science, 344(6191):1492–1496, 2014.
  * [16] Victor JD Tsai.  Delaunay triangulations in tin creation: an overview and a linear-time algorithm.  International Journal of Geographical Information Science, 7(6):501–524, 1993.
  * [17] Song Liu, Makoto Yamada, Nigel Collier, and Masashi Sugiyama.  Change-point detection in time-series data by relative density-ratio estimation.  Neural Networks, 43:72–83, 2013.
  * [18] Meng Jiang, Alex Beutel, Peng Cui, Bryan Hooi, Shiqiang Yang, and Christos Faloutsos.  A general suspiciousness metric for dense blocks in multimodal data.  In 2015 IEEE International Conference on Data Mining, pages 781–786. IEEE Computer Society, 2015.
  * [19] Bernhard Schölkopf, Robert C. Williamson, Alexander J. Smola, John Shawe-Taylor, and John C. Platt.  Support vector method for novelty detection.  In NIPS, pages 582–588. The MIT Press, 1999.
  * [20] Stephan Börzsönyi, Donald Kossmann, and Konrad Stocker.  The skyline operator.  In ICDE, pages 421–430. IEEE Computer Society, 2001.
  * [21] John F MacGregor and Theodora Kourti.  Statistical process control of multivariate processes.  Control Engineering Practice, 3(3):403–414, 1995.
  * [22] JooSeuk Kim and Clayton D Scott.  Robust kernel density estimation.  Journal of Machine Learning Research, 13(Sep):2529–2565, 2012.
  * [23] Gowtham Atluri, Anuj Karpatne, and Vipin Kumar.  Spatio-temporal data mining: A survey of problems and methods.  ACM Comput. Surv., 51(4):83:1–83:41, 2018.
  * [24] Li Wei, Nitin Kumar, Venkata Nishanth Lolla, Eamonn J. Keogh, Stefano Lonardi, and Chotirat (Ann) Ratanamahatana.  Assumption-free anomaly detection in time series.  In SSDBM, pages 237–240, 2005.
  * [25] Alban Siffer, Pierre-Alain Fouque, Alexandre Termier, and Christine Largouët.  Anomaly detection in streams with extreme value theory.  In KDD, pages 1067–1075. ACM, 2017.
  * [26] Naoya Takeishi and Takehisa Yairi.  Anomaly detection from multivariate time-series with sparse representation.  In IEEE International Conference on Systems, Man, and Cybernetics, pages 2651–2656. IEEE, 2014.
  * [27] James MacQueen et al.  Some methods for classification and analysis of multivariate observations.  In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281–297. Oakland, CA, USA, 1967\.
  * [28] Xi C Chen, James H Faghmous, Ankush Khandelwal, and Vipin Kumar.  Clustering dynamic spatio-temporal patterns in the presence of noise and missing data.  In IJCAI, pages 2575–2581, 2015.