Multi-core machines are ubiquitous.
However, most inductive logic programming (ILP) approaches use only a single core, which severely limits their scalability.
To address this limitation, we introduce parallel techniques based on constraint-driven ILP where the goal is to accumulate constraints to restrict the hypothesis space.
Our experiments on two domains (program synthesis and inductive general game playing) show that (i) parallelisation can substantially reduce learning times, and (ii) worker communication (i.e. sharing constraints) is important for good performance.

§ INTRODUCTION

Inductive logic programming (ILP) <cit.> is a form of machine learning.
Given positive and negative examples of a predicate and background knowledge (BK), the ILP problem is to find a set of logical rules (a hypothesis), which, with the BK, entails the positive examples and none of the negative examples.
Key features of ILP include its ability to (i) learn from small amounts of data, (ii) support relational data, and (iii) induce human-readable hypotheses <cit.>.

Although powerful, ILP approaches often struggle with scalability: efficiently searching a large hypothesis space (the set of all hypotheses) for a solution (a hypothesis that correctly generalises the examples).
Parallelisation is one approach to improving scalability.
However, although multi-core machines are ubiquitous, most ILP approaches are single-core learners <cit.>.

To overcome this limitation, we introduce parallel techniques based on constraint-driven ILP where the goal is to accumulate constraints to restrict the hypothesis space.
In particular, we build on the learning from failures (LFF) <cit.> approach, which supports predicate invention and learning optimal and recursive programs.
A LFF learner works by repeatedly generating and testing hypotheses on training examples.
If a hypothesis fails to correctly generalise the examples, the learner deduces constraints to explain the failure, which it then uses to rule out other hypotheses and thus restrict the hypothesis space.
The process repeats until a solution is found.

We introduce two general constraint-driven parallel ILP approaches based on parallel conflict-driven clause learning (CDCL) SAT techniques <cit.>, namely portfolio and divide-and-conquer approaches.
In our portfolio approach, parallel LFF learners compete by searching the same hypothesis space using different heuristics.
In our divide-and-conquer approach, we divide the hypothesis space into disjoint subspaces which we assign to parallel LFF learners who each search them.
Figure <ref> illustrates these strategies.
We also allow learners to exchange learned constraints, similar to how parallel SAT techniques share clauses.

Overall, our contributions are:

* We introduce parallel ILP approaches inspired by portfolio and divide-and-conquer approaches used by CDCL SAT solvers.

* We implement the techniques to parallelise the LFF implementation .

* We experimentally show on two domains (program synthesis and inductive general game playing) that (i) our parallel methods can lead to linear speedups with up to four processors in general, (ii) our parallel methods can lead to super-linear speedup in some cases, and (iii) that communication (i.e. sharing constraints) is important for good performance.

§ RELATED WORK

§.§ Sequential ILP

Many ILP systems, such as Progol <cit.> and Aleph <cit.>, often struggle with large numbers of examples because of their sequential set covering approach.
A notable exception is QuickFOIL <cit.> which builds on FOIL <cit.> by introducing (i) a new scoring function for clauses, and (ii) a highly efficient relational database implementation.
The authors show that their approach can scale to datasets with millions of background facts and hundreds of thousands of examples.
However, because it builds on FOIL, QuickFOIL inherits its limitations, including (i) difficulty learning recursive programs, (ii) no support for predicate invention, and (iii) no guarantees about the optimality of solutions.
These limitations apply to almost all classical ILP systems <cit.>.

Modern meta-level ILP approaches <cit.> can often learn recursive and optimal programs and perform predicate invention.
Although there is no standard definition for meta-level ILP most approaches encode the ILP problem as a meta-level logic program, i.e. a program that reasons about programs.
These approaches delegate the search for a hypothesis to an off-the-shelf solver, such as an answer set programming (ASP) solver <cit.>, after which the meta-level solution is translated back to a standard solution for the ILP task.
However, modern meta-level ILP approaches often struggle in terms of scalability.
For instance, ILASP <cit.> struggles to learn rules with lots of literals because it precomputes every possible rule that may appear in a program, which is often infeasible.
The same issue prevents HEXMIL <cit.> from scaling to large problems.
As far as we are aware, there is no parallel meta-level ILP system.

§.§ Parallel ILP

<cit.> survey parallel ILP techniques.
They divide approaches into three categories: search, data, and evaluation.
Search approaches parallelise the search of the hypothesis space.
Our approaches are in this category.
Data approaches divide the training examples amongst the workers which learn solutions for them in parallel.
Evaluation approaches evaluate candidates rules in parallel.

We discuss three notable parallel approaches.
<cit.> parallelise the search for a hypothesis in the ILP system Claudien.
Claudien works by maintaining a priority queue of potential clauses to add to a hypothesis.
If a clause is too general, it is removed from the queue and its specialisations are added.
In the parallel approach, parallel workers process clauses in the queue.
The authors experimentally show that the parallelisation speed-up is roughly proportional to the number of workers.

<cit.> parallelise Progol by allocating a subset of the positive examples (and all of the negative examples) to each worker.
Each worker applies the standard Progol sequential algorithm to find a good clause for its subset of the positive examples, which it then communicates to the other workers, who may then incorporate the clause into their local theory.
The authors show linear speedups with four and six processors.

<cit.> use the MapReduce paradigm to parallelise the scoring step of Aleph, where a clause is generated and its score is calculated as a function of the examples.
Their results are generally positive, especially when the number of examples is large.
However, although the authors rightly claim that their approach is not specific to Aleph, it is specific to the classic set covering approach.

These three approaches are all limited because they inherit the same limitations as their sequential counterparts.

By contrast, a key contribution of this paper is the introduction of parallel techniques that can learn optimal and recursive programs and perform predicate invention.

More recently, <cit.> introduce p-OLED, a parallel version of OLED <cit.>,  which learns event definitions in the form of even calculus theories.
In their parallel approach, a clause is evaluated in parallel on sub-streams of the input stream and its independent scores are combined.
Their evaluations show that their approach can reduce training times and, in some cases, is capable of super-linear speed-ups.
In contrast to p-OLED, our approaches learn general definite programs, including programs with recursion and predicate invention.

§.§ Parallel SAT

Our parallel ILP approaches are based on parallel conflict-driven-clause-learning SAT techniques <cit.>, of which there are two main approaches.
Divide-and-conquer approaches divide the search space into sub-spaces which are allocated to sequential workers.
Workers co-operate through the exchange of learnt conflicts.
Portfolio approaches <cit.> allow multiple sequential workers to compete on the same search space by employing different search heuristics, such as different restart policies, branching heuristics, random seeds, etc.
Workers also co-operate through the exchange of learnt conflicts.
This exchange can be done through message passing <cit.>, which is necessary for distributed approaches, or through shared memory <cit.>.
In this paper, we transfer these high-level ideas to the area of constraint-driven ILP.
In our approach, the search space is the hypothesis space and workers can co-operate through the exchange of learned constraints, i.e. clauses that describe conflicts.

§ PROBLEM SETTING

We now define the LFF problem, on which the approaches in Section <ref> are based.
We assume familiarity with logic programming <cit.>.

The key idea of LFF is to use hypothesis constraints to restrict the hypothesis space.
Let $\mathcal{L}$ be a language that defines hypotheses, i.e. a meta-language.
For instance, consider a meta-language formed of two literals, h_lit/4 and b_lit/4, which represent head and body literals respectively.
With this language, we can denote the clause last(A,B) $\leftarrow$ tail(A,C), head(C,B) as the set of literals {h_lit(0,last,2,(0,1)), b_lit(0,tail,2,(0,2)), b_lit(0,head,2,(2,1))}.
The first argument of each literal is the clause index, the second is the predicate symbol, the third is the arity, and the fourth is the literal variables, where 0 represents A, 1 represents B, etc.

A hypothesis constraint is a constraint expressed in $\mathcal{L}$.
Let $C$ be a set of hypothesis constraints written in a language $\mathcal{L}$.
A set of definite clauses $H$ is consistent with $C$ if, when written in $\mathcal{L}$, $H$ does not violate any constraint in $C$.
For instance, the constraint
$\leftarrow$ h_lit(0,last,2,(0,1)), b_lit(0,last,2,(1,0))
would be violated by the definite clause last(A,B) $\leftarrow$ last(B,A).
Let $\mathcal{H}$ be a hypothesis space.
We denote as $\mathcal{H}_{C}$ the subset of $\mathcal{H}$ which do not violate any constraint in $C$.

We define the LFF problem:

The LFF input is a tuple $(E^+, E^-, B, \mathcal{H}, C)$ where $E^+$ and $E^-$ are sets of ground atoms denoting positive and negative examples respectively; $B$ is a Horn program denoting background knowledge;
$\mathcal{H}$ is a hypothesis space, and $C$ is a set of hypothesis constraints.

We define a LFF solution:

Given an input tuple $(E^+, E^-, B, \mathcal{H}, C)$, a hypothesis $H \in \mathcal{H}_{C}$ is a solution when $H$ is complete ($\forall e \in E^+, \; B \cup H \models e$) and consistent ($\forall e \in E^-, \; B \cup H \not\models e$).

If a hypothesis is not a solution then it is a failure or a failed hypothesis.
A hypothesis is incomplete when $\exists e \in E^+, \; H \cup B \not \models e$.
A hypothesis is inconsistent when $\exists e \in E^-, \; H \cup B \models e$.
A hypothesis is totally incomplete when $\forall e \in E^+, \; H \cup B \not \models e$.

Let $cost : \mathcal{H} \mapsto R$ be an arbitrary cost function.
We define an optimal solution:

Given an input tuple $(E^+, E^-, B, \mathcal{H}, C)$, a hypothesis $H \in \mathcal{H}_{C}$ is optimal when (i) $H$ is a solution, and (ii) $\forall H' \in \mathcal{H}_{C}$, where $H'$ is a solution, $cost(H) \leq cost(H')$.

In this paper, we define the cost(H) to be the total number of literals in the logic program $H$.

§.§.§ Hypothesis Constraints

<cit.> introduce hypothesis constraints based on subsumption <cit.>.
A clause $C_1$ subsumes a clause $C_2$ ($C_1 \preceq C_2$) if and only if there exists a substitution $\theta$ such that $C_1\theta \subseteq C_2$.
A clausal theory $T_1$ subsumes a clausal theory $T_2$ ($T_1 \preceq T_2$) if and only if $\forall C_2 \in T_2, \exists C_1 \in T_1$ such that $C_1$ subsumes $C_2$.
A clausal theory $T_1$ is a specialisation of a clausal theory $T_2$ if and only if $T_2 \preceq T_1$.
A clausal theory $T_1$ is a generalisation of a clausal theory $T_2$ if and only if $T_1 \preceq T_2$.
If a hypothesis $H$ is incomplete, a specialisation constraint prunes specialisations of $H$, as they are guaranteed to also be incomplete.
If a hypothesis $H$ is inconsistent, a generalisation constraint prunes generalisations of $H$, as they are guaranteed to be inconsistent as well.
If a hypothesis $H$ is totally incomplete, a redundancy constraint prunes hypotheses that contain a specialisation of $H$ as a subset.

§ PARALLEL ALGORITHMS

We now describe our parallel ILP approaches.
We first describe the sequential ILP system , which we parallelise.

Algorithm <ref> shows the high-level  algorithm, which solves the LFF problem (Definition <ref>).
takes as input positive (pos) and negative (neg) examples, background knowledge (bk), and a maximum hypothesis size (max_size).
uses  a generate, test, and constrain loop.
starts with a base generator ASP program whose models correspond to hypotheses (definite programs).

The idea is to augment this generator program with constraints to eliminate models and thus restrict the hypothesis space.
The constraints are initially empty (line 3).

In the generate stage (line 5),  uses Clingo <cit.>, an ASP system, to search for a model of the generator program with exactly m literals which  then converts to a hypothesis (a definite program).

In the test stage (line 9),  tests a hypothesis on the given training examples.
If a hypothesis fails, i.e. is incomplete or inconsistent, then, in the constrain stage (line 12),  learns hypothesis constraints (described as ASP constraints) from the failure.
adds the constraints to the generator program to prune models and constrain subsequent hypothesis generation.
For instance, if a hypothesis is incomplete, i.e. does not entail all the positive examples,  builds a specialisation constraint to prune hypotheses that are logically more specific.

To find an optimal solution,  progressively increases the number of literals allowed in a hypothesis when the hypothesis space is empty at a certain size (e.g. when the generator program together with the learned constraints has no more models) (line 6).

This loop repeats until either (i)  finds an optimal solution, or (ii) there are no more hypotheses to test.
is guaranteed to find the optimal solution when every hypothesis is guaranteed to terminate, such as when the hypothesis space only contains Datalog programs.

def $\text{popper}$(pos, neg, bk, max_size):
m = 1
cons =
while m $\leq$ max_size:
h = generate(cons, m)
if h == UNSAT:
m += 1
outcome = test(pos, neg, bk, h)
if outcome == (COMPLETE, CONSISTENT)
return h
cons += constrain(h, outcome)
return UNSAT

§.§ Parallel Solving

The simplest way to parallelise  is to parallelise the search for a model in the generate stage using the parallel capabilities of Clingo <cit.>.

Clingo incorporates a SAT solver which supports parallel search using shared memory multi-threading (cf. Section <ref>).
Learned conflict clauses (known as nogoods) are exchanged among worker threads according to various heuristics.
To implement this approach, we simply enable Clingo's parallel mode (using the flag `–parallel-mode $k$') which runs $k$ workers in a portfolio configuration.
In our experiments, we call this approach .

Similar to parallel portfolio SAT approaches, our parallel portfolio ILP approach involves multiple workers searching the same hypothesis space using different strategies.
Algorithm <ref> shows the main portfolio worker algorithm, which we call  and which is almost identical to  (Algorithm <ref>).
A master controls the workers.
The master first creates an empty message queue to allow workers to communicate.
This queue is a many-to-many queue that allows each worker to receive a copy of any message put on it.
The master then spawns $k$ workers who each search the same hypothesis space.

In addition to the standard  inputs, a  worker receives as input a message queue for communicating constraints (q_cons) and a flag to denote whether to send constraints to other workers.
Each worker calls the generate step (i.e. Clingo) with different search heuristics so that they find models (and thus hypotheses) in a different order to the other workers.
In this paper, we use the simple approach of calling Clingo with the arguments --rand-freq=p and --seed=s.
The --rand-freq flag tells Clingo to perform random (rather than heuristic) decisions with probability $p$.
The value $s$ is a seed.
We set $p=0.01$ and $s$ to be the workerid.
A direction for future work is to determine how to choose a suitable Clingo heuristic.
To be clear, each  worker has its own single-threaded ASP solver.
As with ,  is guaranteed to find the optimal solution when every hypothesis is guaranteed to terminate.

The  approach, by default, does not permit communication between workers (i.e. the communication flag is false by default).
If the communication option (com) is true, then workers exchange constraints with other workers.
We call this communication-enabled version of the algorithm .
When one  worker finds an incomplete or inconsistent hypothesis, it builds the constraints and sends them to the other workers (line 15) and also receives them (line 16).
As  is essentially learning nogoods by testing hypotheses, our sharing of learned constraints can be seen as exchanging externally learnt nogoods between multiple solvers.

def $\text{port}$(pos, neg, bk, max_size, q_cons, com):
m = 1
cons =
while m $\leq$ max_size:
h = generate(cons, m)
if h == UNSAT:
m += 1
outcome = test(pos, neg, bk, h)
if outcome == (COMPLETE, CONSISTENT)
return h
cons' = constrain(h, outcome)
cons += cons'
if com:
cons += q_cons.get()
return UNSAT

§.§ Divide and Conquer

Similar to parallel D&C SAT approaches, our parallel D&C ILP approach involves multiple workers searching disjoint hypothesises spaces.
In this paper, we take the simple approach of splitting the hypothesis space by the hypothesis size.
A direction for future work is to study alternative methods to divide the hypothesis space.

Algorithm <ref> shows the D&C worker algorithm, which we call .
As with , a master controls the workers.
In addition to creating an empty message queue to share constraints between workers (q_cons), the master creates a second message queue (q_size) to maintain hypothesis sizes to be searched.
The master populates the size queue with all possible hypothesis sizes in increasing order.
The master then spawns $k$ workers.

In addition to the standard  inputs, a  worker receives as input a message queue for communicating constraints (q_cons), a message queue for receiving hypothesis sizes to explore (q_sizes), and a flag to denote whether to send constraints to other workers.
A worker pops the smallest size m off the  size queue and then searches for a solution with exactly m literals.
If there is no solution, the worker loops again and pops another size off the queue.
Since each worker only considers solutions with exactly m literals, they all consider disjoint regions of the hypothesis space.
If a worker finds a solution, they inform the master.
If a solution of size $m$ is found, the master waits until all workers searching for hypotheses of size $k < m$ have finished before returning the solution to guarantee that  returns an optimal solution.

The  approach, by default, does not permit communication between workers (i.e. the communication is defaulted to false).
If the communication option (com) is true, then workers exchange constraints with other workers.
We call this communication-enabled version of the algorithm .
Figure <ref> illustrates the difference between  and .

def $\text{dac}$(pos, neg, bk, q_size, q_cons, com):
cons =
while |q_size| > 1:
m = q_size.get()
while true:
h = generate(cons, m)
if h == UNSAT:
outcome = test(pos, neg, bk, h)
if outcome == (COMPLETE, CONSISTENT)
return h
cons' = constrain(h, outcome)
cons += cons'
if com:
cons += q_cons.get()
return UNSAT

§.§ Implementation

We implemented the systems in Python 3 using the multiprocessing module.
Each process is an instance of Popper which maintains its own ASP solver.
Rather than use shared memory, we use a message queue to allow workers to communicate.

§ EXPERIMENTS

We claim that our parallelisation approaches can reduce learning times and thus improve scalability.
Our experiments[
All the implementation code and experimental data will be made open-source and freely available after the paper has gone through review.
] therefore aim to answer the question:

Q1 Can our parallel approaches reduce learning times?

To answer this question, we compare the performance of our approaches when given progressively more workers (CPUs).

Our parallel approaches allow workers to exchange learned constraints.
To evaluate the impact of communication, our experiments aim to answer the question:

Q2 Can communication (sharing constraints) reduce learning times?

We use Clingo version 5.5.0, SWI-Prolog 7.6.3 and Python 3.9.6.

All experiments were performed on a server with an AMD OpteronTM Processor with 32 cores, 64 threads, and 256GB of RAM.

We give all the approaches identical inputs in all the experiments.

We enforce a timeout of five minutes per task.
We repeat each experiment five times and measure mean learning time and standard deviation.

§.§ Domains

We consider two domains: program synthesis and inductive general game playing.

§.§.§ Program synthesis

Program synthesis has long been considered a difficult problem in ILP <cit.>.
Indeed, most ILP systems cannot learn recursive programs.
<cit.> showed that  can learn recursive programs with higher accuracies and in less time than other ILP systems.
In this experiment, we try to answer the experimental questions using a similar program synthesis dataset.

We use four challenging synthesis tasks: (find dupl) find a duplicate element in a list,  (sorted) determine whether a list is sorted, (dropk) drop the first k elements in a list, and (filter) remove all odd elements from a list.
Figure <ref> shows an example solution for the filter task.
We provide as background knowledge the dyadic relations head, tail, element, increment, decrement, geq and the monadic relations empty, zero, one, even, and odd.
We also include the triadic relation prepend in the filter experiment.

f(A,B):- empty(A),empty(B).

f(A,B):- head(A,D),odd(D),tail(A,C),f(C,B).

f(A,B):- tail(A,C),head(A,E),even(E),

An example solution described as Prolog program for the filter task.

For each task, we generate 10 positive and 10 negative training examples.
Each list is randomly generated and has a maximum length of 50.
We sample the list elements uniformly at random from the set $\{1,2,\dots,100\}$.

§.§.§ IGGP

The general game playing (GGP) framework <cit.> is a system for evaluating an agent's general intelligence across a wide range of tasks.
In the GGP competition, agents are tested on games they have never seen before.
In each round, the agents are given the rules of a new game. The rules are described symbolically as a logic program.
The agents are given a few seconds to process the rules of the game, then they start playing, thus producing game traces.
The winner of the competition is the agent who gets the best total score over all the games.
In this experiment, we use the IGGP dataset <cit.> which inverts the GGP task: an ILP system is given game traces and the task is to learn a set of rules (a logic program) that could have produced these traces.

We focus on two IGGP games: minimal decay and rock, paper, scissors (rps) and on learning the next relations, which is the most challenging one to learn <cit.>.
Figure <ref> shows an example solution for the rps task.

nextscore(A,B,C):- score(A,B,C),does(A,D,F),

nextscore(A,B,C):- different(B,E),does(A,E,G),

nextscore(A,B,C):- score(A,B,F),beats(E,G),

An example solution described as Prolog program for the rps task.

§.§ Results

Figure <ref> shows the experimental results.
is the single-core baseline.

The results show no major benefit from , i.e. running  with parallel Clingo enabled.
For instance, in the filter experiment, the difference in running time between  and  is less than 5%.
This result may surprise the reader, especially as parallel Clingo has been shown to outperform sequential Clingo <cit.>.
The reason is that the bottleneck in  is rarely generating a hypothesis, i.e. searching for a syntactically valid program.
Instead, the bottleneck is mostly the sheer number of hypotheses to consider.
There is, therefore, little benefit from parallelising only the generate part.

The results are mixed for the  approach without communication.
In two tasks it performs worse than  (dropk and sorted), in one better (minimal decay), and about the same in the rest.
This result is expected.
The only way that  can outperform  is when a worker happens to find a solution quicker than  because of its different search heuristics.
However, since  performs iterative deepening search on the hypothesis sizes, whereby it proves that there is no solution at a certain size before going to the next size, both  and  should roughly take the same amount of time to search the space of programs smaller than the solution.
It is only when searching the part of the space at the size of the solution that  has the opportunity to outperform , hence the modest improvements.

The results are very strong for the  approach.
In all cases,  outperforms  and a paired t-test confirms the significance at the $p < 0.01$ level.
For instance, in the minimal decay experiment, given one worker,  takes about the same time (around 250s) as , which is to be expected as there is no parallelisation with only one worker.
Given more workers,  starts to outperform .
With two workers, the learning time of  is almost halved to 136s.
With four workers, the learning time of  is halved again to 60s.
With eight workers, the learning time of  is almost halved again to around 35s.
Similar reductions are demonstrated in all the tasks.
This result strongly suggests that the answer to Q1 is yes: our parallelisation approaches can significantly reduce learning times and that the speed-up is roughly proportional to the number of workers.
In all cases,  outperforms  and a paired t-test confirms the significance at the $p < 0.01$ level.
This result clearly demonstrates that communication between workers is important for good learning performance (Q2).

Figure <ref> excludes the results of  ( without communication) results.
We have excluded the results for  because it struggles to find solutions for any tasks in the given time limit.
This result may surprise the reader, as they may think that  would in the worst-case simulate .
However, the key omission of  is the inability to learn constraints from failed hypotheses from multiple hypothesis sizes.
A key reason why  can efficiently find solutions is that it first considers smaller hypotheses before larger ones.
By learning constraints from small failed hypotheses,  can prune large parts of the hypothesis space.

So when  increases the hypothesis size bound, the space for the next size is greatly reduced from constraints learnt when learning for smaller sizes.
However, in the  approach, there is no transfer of knowledge between the hypothesis sizes.
By contrast,  performs reasonably well, outperforming  on four of the six tasks.
The most impressive results are in the minimal decay task.
With one worker,  takes around 250s.
With two workers, the running time of  is reduced to one fifth (45s).
Given eight workers,  takes around 1s to find a solution.

This result again clearly demonstrates that communication between workers is important for good learning performance (Q2).

[legend columns=5,legend style=nodes=scale=.6, transform shape,align=left,column sep=0ex,
legend entries=Popper, , , , Communication]

scaled x ticks=false
every tick label/.append style=font=
xlabel=Num. workers,
ylabel=Learning time (seconds),

ylabel style=yshift=-1mm,
label style=font=,
legend style=legend pos=south west,font=,style=nodes=right

+[gray,mark=none,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/filter-default_popper.csv;

+[black,mark=x,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/filter-parallel_clingo.csv;

+[red,mark=square*,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/filter-portfolio.csv;

+[red,mark=square*,dashed,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/filter-portfolio_comm.csv;

+[blue,mark=triangle*,dashed,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/filter-dac_comm.csv;

scaled x ticks=false
every tick label/.append style=font=
xlabel=Num. workers,

ylabel style=yshift=-1mm,
label style=font=,
legend style=legend pos=south west,font=,style=nodes=right

+[gray,mark=none,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/dropk-default_popper.csv;

+[black,mark=x,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/dropk-parallel_clingo.csv;

+[red,mark=square*,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/dropk-portfolio.csv;

+[red,mark=square*,dashed,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/dropk-portfolio_comm.csv;

+[blue,mark=triangle*,dashed,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/dropk-dac_comm.csv;

scaled x ticks=false
every tick label/.append style=font=
xlabel=Num. workers,
ylabel=Learning time (seconds),

ylabel style=yshift=-1mm,
label style=font=,
legend style=legend pos=south west,font=,style=nodes=right

+[gray,mark=none,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/sorted-default_popper.csv;

+[black,mark=x,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/sorted-parallel_clingo.csv;

+[red,mark=square*,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/sorted-portfolio.csv;

+[red,mark=square*,dashed,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/sorted-portfolio_comm.csv;

+[blue,mark=triangle*,dashed,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/sorted-dac_comm.csv;

scaled x ticks=false
every tick label/.append style=font=
xlabel=Num. workers,

ylabel style=yshift=-1mm,
label style=font=,
legend style=legend pos=south west,font=,style=nodes=right

+[gray,mark=none,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/find-dupl-default_popper.csv;

+[black,mark=x,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/find-dupl-parallel_clingo.csv;

+[red,mark=square*,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/find-dupl-portfolio.csv;

+[red,mark=square*,dashed,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/find-dupl-portfolio_comm.csv;

+[blue,mark=triangle*,dashed,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/find-dupl-dac_comm.csv;

*Find dupl

scaled x ticks=false
every tick label/.append style=font=
xlabel=Num. workers,
ylabel=Learning time (seconds),

ylabel style=yshift=-1mm,
label style=font=,
legend style=legend pos=south west,font=,style=nodes=right

+[gray,mark=none,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-minimal-decay-default_popper.csv;

+[black,mark=x,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-minimal-decay-parallel_clingo.csv;

+[red,mark=square*,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-minimal-decay-portfolio.csv;

+[red,mark=square*,dashed,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-minimal-decay-portfolio_comm.csv;

+[blue,mark=triangle*,dashed,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-minimal-decay-dac_comm.csv;

*Minimal decay

scaled x ticks=false
every tick label/.append style=font=
xlabel=Num. workers,

ylabel style=yshift=-1mm,
label style=font=,
legend style=legend pos=south west,font=,style=nodes=right

+[gray,mark=none,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-rps-default_popper.csv;

+[black,mark=x,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-rps-parallel_clingo.csv;

+[red,mark=square*,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-rps-portfolio.csv;

+[red,mark=square*,dashed,mark options=fill=red,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-rps-portfolio_comm.csv;

+[blue,mark=triangle*,dashed,mark options=fill=blue,error bars/.cd,y dir=both,y explicit]
table [
col sep=comma,
y error plus expr=error,
y error minus expr=error,
] data/iggp-rps-dac_comm.csv;

*Rock, paper, scissors

Experimental results.

§ CONCLUSIONS AND LIMITATIONS

To improve the ILP scalability problem, we have introduced parallel ILP approaches inspired by parallel SAT approaches, namely portfolio and divide-and-conquer approaches.
Our implementations parallelise , a state-of-the-art constraint-driven ILP system.
Our experiments on two domains (program synthesis and inductive general game playing) show that (i) our parallel methods can lead to linear speedups with up to four processors in general, (ii) our parallel methods can lead to super-linear speedup in some cases, and (iii) that communication (i.e. sharing constraints) is important for good performance.
As far as we are aware, this work is the first to clearly demonstrate the ability to parallelise state-of-the-art ILP systems that support predicate invention and learning recursive programs.

§.§ Limitations and Future Work

There are many limitations of this work, which open much scope for future work.

Better implementation.
Our implementations are based on message passing via inter-process communication.
As our workers learn many, and at times large, constraints, message passing involves non-trivial overhead, not least due to copying.
On a single machine, we could exploit shared memory for improved performance, e.g. due to less copying.

Better constraints.
Parallel SAT solver workers tend to perform checks on the clauses that they receive.
One such check ensures that a new propositional constraint is not subsumed by any known constraint <cit.>.
We could also check subsumption of our learned first-order constraints, though this does have non-trivial cost.
SAT solvers also employ heuristics for deciding which constraints to share.
For example, typically only small learned constraints are sent to other workers, based on some cut-off value <cit.>.
Another heuristic is to only send (long) constraints to workers searching a similar part of the solution space (ibid.).
We could empirically test if parallel SAT techniques like these are beneficial to parallel constraint-driven ILP.

Distributed approaches.
Our implementations support local parallelisation, i.e. on one machine.
Our choice for message passaging is an advantage here, as it should generalise to distributed parallelisation, where we could potentially harness hundreds of CPUs.

Combination of  and
The D&C approach sometimes has one worker working on size $k$ and other workers doing nothing, as they have finished working on other sizes.
Instead of them waiting, they could start work on the same size $k$, each with a new search heuristic.
In line with a distributed approach having many workers, we could follow the parallel SAT strategy of first splitting the search space and then applying a portfolio of workers to each subspace.


# Unravel Anomalies: An End-to-end Seasonal-Trend Decomposition Approach for
Time Series Anomaly Detection

###### Abstract

Traditional Time-series Anomaly Detection (TAD) methods often struggle with
the composite nature of complex time-series data and a diverse array of
anomalies. We introduce TADNet, an end-to-end TAD model that leverages
Seasonal-Trend Decomposition to link various types of anomalies to specific
decomposition components, thereby simplifying the analysis of complex time-
series and enhancing detection performance. Our training methodology, which
includes pre-training on a synthetic dataset followed by fine-tuning, strikes
a balance between effective decomposition and precise anomaly detection.
Experimental validation on real-world datasets confirms TADNet’s state-of-the-
art performance across a diverse range of anomalies.

Index Terms—  time-series anomaly detection, seasonal-trend decomposition,
time-series analysis, end-to-end

##  1 Introduction

In the realm of signal processing, time-series analysis has emerged as a
pivotal area of focus across diverse application domains [1]. The ability to
understand underlying temporal patterns and identify anomalies in these
signals is paramount. Time-series Anomaly Detection (TAD) takes on the
intricate task of pinpointing such deviations from expected behavior in time-
series. Despite extensive efforts to accurately label data, real-world
datasets are still prone to errors [2, 3]. Recognizing these challenges, our
work aligns with a growing trend toward semi-supervised anomaly detection for
time-series data [4, 5], which operates on the assumption of a purely normal
training dataset.

Challenges. TAD presents two primary challenges. First, real-world data, with
its diverse origins, displays a composition of complex patterns. This
necessitates models to effectively learn representations from such intricate
temporal dynamics without labeled data. Second, temporal anomalies span
various categories, including point- (global and contextual) and pattern-wise
(shapelet, seasonal, and trend) anomalies [3, 4]. Specifically, pattern-wise
anomalies can arise from varied causes, such as unusual shapes, reduced
seasonality, or a declining trend. Such diversity introduces ambiguity, making
accurate anomaly detection more challenging for models.

Existing solutions. In recent years, deep learning models [6, 4] have
surpassed classical techniques [7] in TAD tasks. These models generally fall
into two categories: autoregression-based and reconstruction-based approaches.
Autoregression-based methods identify anomalies through prediction errors [8],
while reconstruction-based methods, including Autoencoder-based techniques [9,
10] and generative adversarial networks [11], use reconstruction errors.
Despite their overall accuracy, many of these models fail to account for the
complex compositional nature of patterns in time-series data or distinguish
between different types of anomalies. Consequently, these approaches often
overlook nuanced deviations and lack interpretability.

Fig. 1: Schematic of the STD and TAD workflow, which begins by applying STD to
the anomalous time-series, yielding its decomposed components. Subsequently,
the original series is compared with the reconstructed series to compute the
reconstruction error. Finally, the error is transformed into anomaly scores
and labels. Fig. 2: Overview of TADNet. The workflow initiates with data
augmentation, wherein trend, seasonal, anomalies, and reaminder are integrated
to formulate the synthetic dataset. The training of TADnet unfolds in two
phases: first, it masters STD on the synthetic data guided by
$L_{\text{dec}}$, followed by fine-tuning on real-world data, leveraging
$L_{\text{rec}}$ to capture typical patterns. The backbone of TADnet consists
of an Encoder-Decoder pair, facilitating mapping between the time-domain and
latent space, and a separator tasked with generating masks tailored for STD
targets. The parameters are shared between the three decoders.

New insights. Time series are inherently composed of multiple overlapping
patterns: seasonality, trend, and remainder. This overlapping nature can
obscure different types of anomalies. The advantage of using Seasonal-Trend
Decomposition (STD) [12] is vividly demonstrated in Fig.1, which shows how
anomalies can be effectively unraveled by separating them into their
respective components. By leveraging the power of STD, our approach can
uniquely break down these complex composite patterns. Furthermore, following
the taxonomy proposed in [3], we find that different types of anomalies can be
systematically associated with their respective components: seasonal anomalies
with the seasonal component, trend anomalies with the trend component, and
point anomalies with the remainder component.

Although existing research has incorporated time-series decomposition into TAD
task [13, 14, 15], these approaches do not follow an end-to-end training
manner. Specifically, they either depend on pre-defined decomposition
algorithms, necessitating elaborate parameter tuning [14, 15], or employ
decomposition only for data preprocessing [13]. To overcome the lack of
supervised signals for end-to-end training, we introduce a novel two-step
training approach. Initially, we generate a synthetic dataset that mimics the
decomposed components of real-world data. First, we pre-train our model on
this synthetic dataset for decomposition tasks. The model is subsequently
fine-tuned on real-world anomalous data, yielding enhanced time-series
decomposition and anomaly detection.

Contributions. Our contributions are threefold. First, we present TADNet, a
novel end-to-end TAD model that leverages STD, as illustrated in Fig.2.
Inspired by TasNet [16], TADNet is designed to handle time-series data
similarly to audio signals, and offers detailed decomposition components,
enhancing both interpretability and accuracy. Second, we adopt a targeted
training strategy with pre-training and fine-tuning to enable end-to-end
decomposition and detection. Third, our model achieves state-of-the-art
performance and validates its efficacy through decomposition visualizations.

##  2 Preliminaries

Time-series Anomaly Detection. Consider a time-series
$\mathcal{T}\in\mathbb{R}^{T\times D}$ of length $T$. The series is designated
as univariate when $D=1$ and multivariate when $D>1$. The primary objective of
TAD task is to identify anomalies within $\mathcal{T}$, consequently
generating an output series $\mathcal{Y}$. Each element in $\mathcal{Y}$
corresponds to the anomalous status of the respective data points in
$\mathcal{T}$, with $1$ indicating an anomaly. To facilitate this, point-wise
scoring methods [6, 17] are employed to produce an anomaly score series
$\mathcal{S}=\\{s_{1},s_{2},...,s_{m}\\}$, each $s_{i}\in\mathbb{R}$. These
scores are then converted into binary anomaly labels $\mathcal{Y}$ through an
independent thresholding process.

Seasonal-Trend Decomposition. For a univariate time-series
$x\in\mathbb{R}^{T}$, its structural composition capturing trend and
seasonality is represented as $x_{t}=\tau_{t}+s_{t}+r_{t}$, where
$\tau_{t},s_{t}$, and $r_{t}$ denote the trend, seasonal, and remainder
components at the $t$-th timestamp, respectively.

The primary focus of our method for TAD task lies in the seasonal-trend
decomposition of univariate time-series. The current literature underscores
the benefits of evaluating each variable individually for increased predictive
accuracy [18, 19]. Thus, each variable in a multivariate series undergoes
independent decomposition, while the overall anomaly detection strategy
accounts for its multivariate nature.

Time-domain Audio Separation. The task is formulated in terms of estimating
$C$ sources $s^{(1)}_{t},\ldots,s^{(C)}_{t}\in\mathbb{R}^{T}$, given the
discrete waveform of the mixture $x_{t}\in\mathbb{R}^{T}$. Mathematically,
this is expressed as $x_{t}=\sum\nolimits_{i=1}^{C}s^{(i)}_{t}$.

The field of monaural audio source separation has seen advancements through
various deep learning models. TasNet [16] introduced the concept of end-to-end
learning in this area. Conv-TasNet [20] further developed this approach by
incorporating convolutional layers. DPRNN [21] focused on improving long-term
modeling through recurrent neural networks. More recently, architectures like
SepFormer [22] have integrated attention mechanisms.

The theoretical framework of Time-domain Audio Separation exhibits striking
resemblances to the Seasonal-Trend Decomposition tasks, thus leading us to
contemplate the possible transference of methodologies between these domains
for improved time-series decomposition and anomaly detection.

##  3 Methodology

###  3.1 Overall Framework

The overall flowchart of TADNet is shown in Fig.2. The preprocessing contains
data normalization and segmentation. The input is first normalized to the
range $[0,1)$. Segmentation involves a sliding window approach of length $P$,
converting the normalized $\mathcal{T}$ into non-overlap blocks of length $P$
denoted as
$\mathcal{D}=\left\\{\mathcal{X}_{1},\mathcal{X}_{2},\ldots,\mathcal{X}_{N}\right\\}$.
Notably, while segmentation offers a more flexible approach to managing longer
sequences, it does not influence results.

Within the TADNet backbone, we leverage the TasNet architecture and its
variants [16, 20, 21] from speech separation. Viewing the seasonal and trend
components as distinct audio signals, TasNet facilitates effective STD (see
Fig.2).

Since the training utilizes only normal samples, anomalies typically disrupt
the reconstruction process. To detect these anomalies, we compute the
reconstruction error, denoted by
$Score(t)=\lVert\mathcal{T}_{t,:}-\hat{\mathcal{T}}_{t,:}\rVert_{2}$, where
$\lVert\cdot\rVert_{2}$ represents the L2 norm.

###  3.2 TADNet Backbone

Table 1: Quantitative results for TADNet across five real-world datasets use
metrics _P_ , _R_ , and _F1_ for precision, recall, and F1-score (%). Higher
values indicate better performance. Best and second-best results are in bold
and underlined, respectively. Dataset are followed by brackets, where _u_
indicates univariate and _m_ multivariate.

Dataset |  UCR (_u_) |  SMD (_m_) |  SWaT (_m_) |  PSM (_m_) |  WADI (_m_)
---|---|---|---|---|---
Metric | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1
OCSVM | 41.14 | 94.00 | 57.23 | 44.34 | 76.72 | 56.19 | 45.39 | 49.22 | 47.23 | 62.75 | 80.89 | 70.67 | 61.89 | 62.31 | 62.10
BeatGAN | 45.20 | 88.42 | 59.82 | 72.90 | 84.09 | 78.10 | 64.01 | 87.46 | 73.92 | 90.30 | 93.84 | 92.04 | 65.13 | 38.32 | 48.25
OmniAnomaly | 64.21 | 86.93 | 73.86 | 83.34 | 94.49 | 88.57 | 86.33 | 76.94 | 81.36 | 91.61 | 71.36 | 80.23 | 31.58 | 65.41 | 42.60
InterFusion | 60.74 | 95.20 | 74.16 | 87.02 | 85.43 | 86.22 | 80.59 | 85.58 | 83.01 | 83.61 | 83.45 | 83.52 | 80.26 | 30.38 | 44.08
AnomalyTran | 72.80 | 99.60 | 84.12 | 89.40 | 95.45 | 92.33 | 91.55 | 96.73 | 94.07 | 96.91 | 98.90 | 97.89 | 80.30 | 79.23 | 79.76
TranAD | 94.07 | 100.00 | 96.94 | 88.03 | 89.42 | 88.72 | 97.60 | 69.97 | 81.51 | 96.44 | 87.37 | 91.68 | 35.29 | 82.96 | 49.51
DecompTran | 71.58 | 96.83 | 82.31 | 89.32 | 93.94 | 91.57 | 95.17 | 80.30 | 87.10 | 97.65 | 87.21 | 92.14 | 79.40 | 81.01 | 80.20
TADNet(Ours) | 97.51 | 100.00 | 98.74 | 94.81 | 91.93 | 93.35 | 92.15 | 88.35 | 90.21 | 98.12 | 99.21 | 98.66 | 94.03 | 82.96 | 88.15

The encoder accepts a univariate time series $x_{d}\in\mathbb{R}^{P}$, where
$d=1,2,\ldots,D$, sourced from multivariate $\mathcal{X}_{i}$. It segments
this series into multiple overlapping frames. Each frame possesses a length of
$L$ and overlaps with adjacent frames by a stride of $S$. Sequentially, these
frames are collated to constitute $\mathbf{X}_{d}\in\mathbb{R}^{L\times K}$.
Through a subsequent linear transformation, the encoder projects
$\mathbf{X}_{d}$ into a latent space, given by:
$\mathbf{E}=\mathbf{U}\mathbf{X}_{d}.$ The matrix
$\mathbf{U}\in\mathbb{R}^{N\times L}$ contains trainable transformation bases
in its rows, while $\mathbf{E}\in\mathbb{R}^{N\times K}$ represents the
feature representation of the input time series in the latent space.

The separator receives the encoded representation and is tasked with
generating masks for each of the decomposed components. Formally,
$\\{\mathbf{M}_{\tau},\mathbf{M}_{s},\mathbf{M}_{r}\\}=\mathcal{F}_{\text{sep}}(\mathbf{E};\theta)$,
where $\mathbf{M}_{\tau}$, $\mathbf{M}_{s}$, and $\mathbf{M}_{r}$ represent
the masks for the trend, seasonal, and remainder components, respectively.
Here, $\mathcal{F}_{\text{sep}}$ denotes the separator subnetwork, which can
be implemented using various architectures such as CNN [20], RNN [21], or
Transformer [22]. Utilizing these masks, the embeddings for each target from
the global feature $\mathbf{E}$ are:

$\mathbf{E}_{\tau}=\mathbf{M}_{\tau}\odot\mathbf{E},\quad\mathbf{E}_{s}=\mathbf{M}_{s}\odot\mathbf{E},\quad\mathbf{E}_{r}=\mathbf{M}_{r}\odot\mathbf{E},$
(1)

achieved via point-wise products of the corresponding masks.

The decoder architecture mirrors the encoder, taking in the masked embeddings
generated by the separator. These embeddings are mapped back to the time
domain via a linear transformation $V$:

$\hat{\mathbf{S}}_{\tau}=\mathbf{E}_{\tau}^{T}\mathbf{V},\quad\hat{\mathbf{S}}_{s}=\mathbf{E}_{s}^{T}\mathbf{V},\quad\hat{\mathbf{S}}_{r}=\mathbf{E}_{r}^{T}\mathbf{V}.$
(2)

Here, $V\in\mathbb{R}^{N\times L}$ has $N$ decoder bases. The reconstructed
trend, seasonal, and remainder, denoted as $\hat{\mathbf{S}}_{\tau}$,
$\hat{\mathbf{S}}_{s}$, and $\hat{\mathbf{S}}_{r}$, are derived from their
respective embeddings. The output time-domain signals, $\hat{\tau}_{d}$,
$\hat{s}_{d}$, and $\hat{r}_{d}$, are obtained through an overlap-and-add
operation.

###  3.3 Synthetic Dataset

In anomaly detection, real-world data often lack the nuanced trend and
seasonal patterns essential for STD. To equip TADnet with robust STD
capabilities, we constructed a composite dataset. This dataset is meticulously
designed with intricate seasonal and trend shifts, anomalies, and noise to
emulate real-world contexts, as illustrated in Fig.1. Both deterministic and
stochastic trends are leveraged to craft the trend and seasonal components,
which are subsequently normalized to maintain a zero mean and unit variance.

Trend. The deterministic trend is generated using a linear trend function with
fixed coefficients: $\tau_{t}^{(d)}=\beta_{0}+\beta_{1}\cdot t$, where
$\beta_{0}$ and $\beta_{1}$ are tunable parameters. The stochastic trend
component is modeled using an ARIMA(0,2,0) process, integrated into the trend
model as follows: $\tau_{t}^{(s)}=\sum_{n=1}^{t}nX_{n}$, where $X_{t}$ is a
normally-distributed white noise term, satisfying
$\Delta^{2}\tau^{(s)}_{t}=X_{t}$.

Seasonal. The deterministic seasonal component combines various types of
periodic signals. It includes sinusoidal waves with varying amplitudes,
frequencies, and phases, as well as square waves with different amplitudes,
periods, and phases.

For the slow-changing stochastic sequence, the seasonal component is composed
of repeating cycles of a slow-changing trend series $\tau^{(s)}_{t}$. This
series is generated using the trend generation algorithm to ensure a smooth
transition between cycles. Each cycle is uniquely characterized by a period
$T_{0}$ and a phase $\phi$. The stochastic seasonal component is thus
formulated as $s_{t}=\tau^{(s)}_{\text{mod}(t+\phi,T_{0})}$.

To enrich the dataset, minor adjustments are made to both the cycle’s length
and amplitude, including resampling individual cycles and scaling values
within a cycle, aiming for more diverse and generalizable signal
decomposition.

Remainder. The remainder component is conceived using a white noise process
with adjustable variances.

To enhance the robustness of the decomposition model against anomalies and
ensure stable decomposition performance, we injected a portion of anomalous
data into the synthetic dataset, following the method outlined in [3].

###  3.4 Two-Phase Training Strategy

We propose a two-phase training strategy for TADnet to ensure its efficacy in
both time-series decomposition and anomaly detection tasks.

In the first phase, TADnet is pre-trained on a synthetic dataset, with a focus
on time-series decomposition. The corresponding loss function, which
aggregates the Mean Squared Errors for each decomposed component, is
formulated by:

$L_{\text{dec}}=\sum\nolimits_{d=1}^{D}\left(\lVert\tau_{d}-\hat{\tau}_{d}\rVert_{2}^{2}+\lVert
s_{d}-\hat{s}_{d}\rVert_{2}^{2}+\lVert r_{d}-\hat{r}_{d}\rVert_{2}^{2}\right)$
(3)

Here, $\tau_{d}$, $s_{d}$, and $r_{d}$ denote the actual seasonal, trend, and
residual components for the $d$-th dimension, respectively, while
$\hat{\tau}_{d}$, $\hat{s}_{d}$, and $\hat{r}_{d}$ represent their predicted
counterparts.

In the second phase, TADnet is fine-tuned using a real-world TAD dataset. This
stage emphasizes the accurate reconstruction of the original time series
following its decomposition, a key requirement for effective anomaly
detection. The loss function for this stage, which focuses on overall
reconstruction accuracy, is given by:

$L_{\text{rec}}=\sum\nolimits_{d=1}^{D}\lVert
x_{d}-(\hat{\tau}_{d}+\hat{s}_{d})\rVert_{2}^{2}$ (4)

Here, $x_{d}$ represents the original time series in the $d$-th dimension, and
$\hat{\tau}_{d}+\hat{s}_{d}$ is its predicted reconstruction.

Table 2: Details of the dataset.

Dataset | #Entities | #Dim | #Train | #Test(labeled) | Anomaly%
---|---|---|---|---|---
UCR | 4 | 1 | 1,200-3,000 | 4,500-6,301 | 1.9
SMD | 28 | 38 | 23.6K-28.7K | 23.6K-28.7K | 4.2
WADI | 1 | 127 | 789,371 | 172,801 | 5.9
SWaT | 1 | 51 | 496,800 | 449,919 | 12.1
PSM | 1 | 25 | 132,481 | 87,841 | 27.8

##  4 Experiments

Fig. 3: Visualization of decomposition and detection results in UCR and SMD.
The first row shows the raw time series with anomalies, the second and third
rows display the seasonal and trend components, respectively, and the final
row depicts the reconstruction error. Anomalies are marked with a red
background.

In our experiments, we employ five real-world datasets encompassing both
univariate and multivariate time-series, as outlined in Table 2. These include
multi-univariate dataset UCR [23], featured in the KDD 2021 Cup; SMD [9],
which provides five weeks of data from a leading Internet company; and SWaT
[24], offering sensor data from water treatment plant. WADI extends SWaT but
contains over twice as many sensors and actuators. Additionally, PSM [25]
originates from eBay’s application server nodes. NASA’s MSL and SMAP [8]
datasets were excluded due to their abundance of binary sequences, which are
incompatible with our decomposition methods.

We benchmark TADNet against: one classic method, OCSVM [7], and six deep
models including BeatGAN [11], OmniAnomaly [9], InterFusion [10], AnomalyTran
[4], TranAD [6], and DecompTran [13]. Other traditional methods are excluded,
as deep learning models have been proven superior [4]. Evaluation is based on
standard TAD metrics such as precision, recall, and F1 score. We adopt a
widely-used adjustment strategy [9, 4, 6, 13]: if any time point in an
abnormal segment is detected, the entire segment is considered correctly
identified, aligning with real-world applications.

We partition the dataset into blocks of $P=8,000$ time points to optimize
memory. The backbone utilizes TasNet with DPRNN [21], featuring kernel size
$W=2$, encoding dimension $E=256$, feature dimension $F=64$, hidden dimension
$H=128$, and six layers. Training employs ADAM with an initial learning rate
of $1\times 10^{-3}$ for 200 epochs, followed by fine-tuning at $5\times
10^{-4}$ for 10-20 epochs. Experiments run on an NVIDIA GeForce RTX 3090. To
ensure fair comparisons with previous work, the Peak Over Threshold method
[26] is employed to determine the anomaly threshold. A timestamp is labeled as
anomalous if its score exceeds this threshold.

###  4.1 Results and Analysis

The results of our quantitative evaluation are presented in Table 1. We
rigorously assess TADNet against seven competitive baselines across five real-
world datasets. TADNet manifests superior performance across all metrics,
notably achieving the highest F1-score in four out of the five datasets. This
consistently elevated performance attests to the efficacy of our approach,
which leverages seasonal trend decomposition to disentangle intricate and
overlapping temporal patterns. Such decomposition unravels a broader spectrum
of anomalies, thereby elevating the detection capabilities of our model.
Importantly, the results provide empirical support for the benefit of
incorporating decomposition techniques into time-series anomaly detection
tasks.

Visualization. To demonstrate the effectiveness of STD in unraveling complex
anomalies, we showcase decomposition and reconstruction error results on
multiple real-world datasets in Fig.1 (NeurIPS-TS) and Fig.3 (UCR and SMD).
It’s noteworthy that anomalies become more clearly evident when comparing
their respective decomposed components to the original series. As the
reconstruction error and anomaly scores are positively correlated, our
reconstruction error closely aligns with the anomalous regions, as seen in the
last row. This validates that our method adeptly identifies anomalies, thereby
improving detection accuracy while reducing false positives.

Table 3: Ablation results, evaluated using F1-score (%). ’w/o Sep’ excludes
the separator from the backbone architecture; ’w/o Decomp’ replaces
$L_{\text{dec}}$ with $L_{\text{rec}}$; ’w/o Augment’ omits pretraining on a
synthetic dataset; and ’Iterative’ involves iterative training between the
decomposition and anomaly detection tasks.

Ablation | UCR | SMD | SWaT | PSM | WADI
---|---|---|---|---|---
TADNet | 98.74 | 93.35 | 90.21 | 98.66 | 88.15
w/o Sep | 32.68 | 66.24 | 76.89 | 83.28 | 47.66
w/o Decomp | 48.69 | 84.12 | 88.41 | 95.57 | 65.72
w/o Augment | 40.12 | 74.17 | 83.26 | 98.01 | 62.15
Iterative | 99.12 | 92.14 | 86.55 | 96.58 | 92.06

Ablation Study. As shown in Table 3, we further investigate the effect of each
part in TADNet. The removal of key components such as the Separator (w/o Sep),
Decomposition (w/o Decomp), or Augmentation (w/o Augment) leads to substantial
drops in F1-scores, highlighting their essential roles in TADNet’s
performance. While the iterative training approach (Iterative) shows some
improvement in specific datasets (notably WADI, increased to 92.06%), its
computational overhead makes it less practical for broader applications. We
therefore opt for the pretrain-finetune paradigm and leave the study of
iterative training for future work.

##  5 Conclusion

In summary, we introduced TADNet, an end-to-end TAD model that employs STD to
tackle the challenges of complex patterns and diverse anomalies. Our model
distinguishes itself by providing interpretable and accurate decomposition
components. Through a two-phase training strategy involving pre-training on
synthetic data and fine-tuning on real-world data, TADNet not only achieves
state-of-the-art performance but also validates its effectiveness via
decomposition visualizations. This work represents a substantial advance in
time-series anomaly detection, effectively bridging the gap between accuracy
and interpretability.

## References

  * [1] Yuantao Gu, Yuchen Jiao, Xingyu Xu, and Quan Yu,  “Request–response and censoring-based energy-efficient decentralized change-point detection with iot applications,”  IEEE Internet of Things Journal, vol. 8, no. 8, pp. 6771–6788, 2020\.

  * [2] Renjie Wu and Eamonn Keogh,  “Current time series anomaly detection benchmarks are flawed and are creating the illusion of progress,”  IEEE Transactions on Knowledge and Data Engineering, 2021.
  * [3] Kwei-Herng Lai, Daochen Zha, Junjie Xu, Yue Zhao, Guanchu Wang, and Xia Hu,  “Revisiting time series outlier detection: Definitions and benchmarks,”  in Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
  * [4] Jiehui Xu, Haixu Wu, Jianmin Wang, and Mingsheng Long,  “Anomaly transformer: Time series anomaly detection with association discrepancy,”  in International Conference on Learning Representations, 2021.
  * [5] Guansong Pang, Chunhua Shen, Longbing Cao, and Anton Van Den Hengel,  “Deep learning for anomaly detection: A review,”  ACM computing surveys (CSUR), vol. 54, no. 2, pp. 1–38, 2021.
  * [6] Shreshth Tuli, Giuliano Casale, and Nicholas R. Jennings,  “Tranad: Deep transformer networks for anomaly detection in multivariate time series data,”  Proc. VLDB Endow., vol. 15, no. 6, pp. 1201–1214, feb 2022.
  * [7] Bernhard Schölkopf, John C. Platt, John Shawe-Taylor, Alex J. Smola, and Robert C. Williamson,  “Estimating the Support of a High-Dimensional Distribution,”  Neural Computation, vol. 13, no. 7, pp. 1443–1471, 07 2001.
  * [8] Kyle Hundman, Valentino Constantinou, Christopher Laporte, Ian Colwell, and Tom Soderstrom,  “Detecting spacecraft anomalies using lstms and nonparametric dynamic thresholding,”  in Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, 2018, pp. 387–395.
  * [9] Ya Su, Youjian Zhao, Chenhao Niu, Rong Liu, Wei Sun, and Dan Pei,  “Robust anomaly detection for multivariate time series through stochastic recurrent neural network,”  in Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2019, pp. 2828–2837.
  * [10] Zhihan Li, Youjian Zhao, Jiaqi Han, Ya Su, Rui Jiao, Xidao Wen, and Dan Pei,  “Multivariate time series anomaly detection and interpretation using hierarchical inter-metric and temporal embedding,”  in Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, 2021, pp. 3220–3230.
  * [11] Bin Zhou, Shenghua Liu, Bryan Hooi, Xueqi Cheng, and Jing Ye,  “Beatgan: Anomalous rhythm detection using adversarially generated time series.,”  in IJCAI, 2019, vol. 2019, pp. 4433–4439.
  * [12] Robert B Cleveland, William S Cleveland, Jean E McRae, and Irma Terpenning,  “Stl: A seasonal-trend decomposition procedure based on loess,”  Journal of Official Statistics, vol. 6, no. 1, pp. 3–73, 1990.
  * [13] Shuxin Qin, Jing Zhu, Dan Wang, Liang Ou, Hongxin Gui, and Gaofeng Tao,  “Decomposed transformer with frequency attention for multivariate time series anomaly detection,”  in 2022 IEEE International Conference on Big Data (Big Data). IEEE, 2022, pp. 1090–1098.
  * [14] Jingkun Gao, Xiaomin Song, Qingsong Wen, Pichao Wang, Liang Sun, and Huan Xu,  “Robusttad: Robust time series anomaly detection via decomposition and convolutional neural networks,”  arXiv preprint arXiv:2002.09545, 2020.
  * [15] Sourav Chatterjee, Rohan Bopardikar, Marius Guerard, Uttam Thakore, and Xiaodong Jiang,  “Mospat: Automl based model selection and parameter tuning for time series anomaly detection,”  arXiv preprint arXiv:2205.11755, 2022.
  * [16] Yi Luo and Nima Mesgarani,  “Tasnet: Time-domain audio separation network for real-time, single-channel speech separation,”  in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 696–700.
  * [17] Sebastian Schmidl, Phillip Wenig, and Thorsten Papenbrock,  “Anomaly detection in time series: A comprehensive evaluation,”  Proc. VLDB Endow., vol. 15, no. 9, pp. 1779–1797, may 2022.
  * [18] Zhenwei Zhang, Xin Wang, and Yuantao Gu,  “Sageformer: Series-aware graph-enhanced transformers for multivariate time series forecasting,”  arXiv preprint arXiv:2307.01616, 2023.
  * [19] Yuqi Nie, Nam H. Nguyen, Phanwadee Sinthong, and Jayant Kalagnanam,  “A time series is worth 64 words: Long-term forecasting with transformers,”  in International Conference on Learning Representations, 2023.
  * [20] Yi Luo and Nima Mesgarani,  “Conv-tasnet: Surpassing ideal time–frequency magnitude masking for speech separation,”  IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 27, no. 8, pp. 1256–1266, 2019.
  * [21] Yi Luo, Zhuo Chen, and Takuya Yoshioka,  “Dual-path rnn: Efficient long sequence modeling for time-domain single-channel speech separation,”  in ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 46–50.
  * [22] Cem Subakan, Mirco Ravanelli, Samuele Cornell, Mirko Bronzi, and Jianyuan Zhong,  “Attention is all you need in speech separation,”  in ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021, pp. 21–25.
  * [23] Eamonn Keogh, Dutta Roy Taposh, U Naik, and A Agrawal,  “Multi-dataset time-series anomaly detection competition,”  in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. https://compete. hexagonml. com/practice/competition/39, 2021\.
  * [24] Aditya P Mathur and Nils Ole Tippenhauer,  “Swat: A water treatment testbed for research and training on ics security,”  in CySWater. IEEE, 2016, pp. 31–36.
  * [25] Ahmed Abdulaal, Zhuanghua Liu, and Tomer Lancewicki,  “Practical approach to asynchronous multivariate time series anomaly detection and localization,”  in Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, 2021, pp. 2485–2494.
  * [26] Alban Siffer, Pierre-Alain Fouque, Alexandre Termier, and Christine Largouet,  “Anomaly detection in streams with extreme value theory,”  in Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, 2017, pp. 1067–1075.


# On the dimension of cofinite modules

Majid Rahro Zargar and Ghader Ghasemi  Majid Rahro Zargar, Department of
Engineering Sciences, Faculty of Advanced Technologies, University of
Mohaghegh Ardabili, Namin, Ardabil, Iran<EMAIL_ADDRESS><EMAIL_ADDRESS>Ghader Ghasemi, Faculty of Mathematical Sciences,
Department of Mathematics, University of Mohaghegh Ardabili, Ardabil, Iran,
<EMAIL_ADDRESS>
###### Abstract.

Let $I$ be an ideal of a commutative Noetherian complete local ring $R$. In
the present paper, we establish the equality
$\operatorname{\mathsf{dim}}R/(I+\mbox{Ann}\,_{R}M)=\operatorname{\mathsf{dim}}M$
for all $I$-cofinite $R$-modules $M$.

###### Key words and phrases:

Cofinite module, Noetherian complete local ring, Local cohomology module,
Krull dimension.

###### 2020 Mathematics Subject Classification:

13D45, 13C15, 13J10, 18E10

##  1\. Introduction

Throughout this paper, let $R$ denote a commutative Noetherian ring (with
identity) and $I$ be an ideal of $R$. Also, we denote by $\mathscr{C}(R)$ the
category of all $R$-modules. For an $R$-module $M$, the $i$th local cohomology
module of $M$ with respect to $I$ is defined as:

$H^{i}_{I}(M)=\underset{n\geq
1}{\varinjlim}\,\,\text{Ext}^{i}_{R}(R/I^{n},M).$

We refer the reader to [8] or [6] for more details about local cohomology.
Hartshorne, in [9], defined an $R$-module $M$ to be $I$-cofinite, if
$\operatorname{Supp}M\subseteq V(I)$ and ${\rm Ext}^{i}_{R}(R/I,M)$ is a
finitely generated $R$-module for all $i\geq 0$.

In the sequel, for any ideal $I$ of $R$, we denote by $\mathscr{C}(R,I)_{cof}$
the category of all $I$-cofinite $R$-modules. Also, we denote by
$\mathscr{A}(R)$ the class of all ideals $I$ of $R$ such that
$\mathscr{C}(R,I)_{cof}$ is an Abelian subcategory of $\mathscr{C}(R)$; that
is, if $f:M\longrightarrow N$ is an $R$-homomorphism of $I$-cofinite modules,
then the $R$-modules ${\rm ker}\,f$ and ${\rm coker}\,f$ are $I$-cofinite,
too.

One of the more elementary results concerning the finitely generated
$R$-module $M$ is the relation
$\operatorname{\mathsf{dim}}R/\mbox{Ann}\,_{R}M=\operatorname{\mathsf{dim}}M$.
This relation easily follows from the fact that
$\operatorname{Supp}M=V(\mbox{Ann}\,_{R}M)$. But, this result does not hold
for cofinite $R$-modules with respect to an ideal of $R$. For example, if
$(R,\operatorname{\mathfrak{m}},k)$ is a Noetherian local ring of dimension
$d>0$, then the $\operatorname{\mathfrak{m}}$-cofinite $R$-module
$\mbox{E}_{R}(k)$ (the injective envelope of the residue field
$k=R/\operatorname{\mathfrak{m}}$ of $R$) is faithful, that is
$\mbox{Ann}\,_{R}\mbox{E}_{R}(k)=0$, and
$\operatorname{\mathsf{dim}}\mbox{E}_{R}(k)=0$. So,
$\operatorname{\mathsf{dim}}R/\mbox{Ann}\,_{R}\mbox{E}_{R}(k)=d>\operatorname{\mathsf{dim}}\mbox{E}_{R}(k)$.
But, we know that every finitely generated $R$-module $M$ is
$(0_{R})$-cofinite, where $(0_{R})$ denotes the zero ideal of $R$. So, one has
the equality
$\operatorname{\mathsf{dim}}R/((0_{R})+\mbox{Ann}\,_{R}M)=\operatorname{\mathsf{dim}}M$.
Furthermore, in [12], Melkersson proved that if
$(R,\operatorname{\mathfrak{m}})$ is a Noetherian complete local ring and $I$
is an ideal of $R$, then each zero-dimensional $I$-cofinite module $M$ is
Artinian and for each $\mathfrak{p}\in\mbox{Att}\,_{R}M$ we have
$\operatorname{\mathsf{dim}}R/(I+\mathfrak{p})=0$. So,
$\operatorname{\mathsf{dim}}R/(I+\mbox{Ann}\,_{R}M)=0=\operatorname{\mathsf{dim}}M$.
Therefore, according to the above, it is natural to raise the following
question:

######  Question 1.1.

Let $I$ be an ideal of a Notherian complete local ring $R$ and $M$ an
$I$-cofinite $R$-module. Then, does the equality
$\operatorname{\mathsf{dim}}R/(I+\mbox{Ann}\,_{R}M)=\operatorname{\mathsf{dim}}M$
hold?

More recently, in [13], Pirmohammadi provided a partial answer to the above
question. Indeed. he proved that for any ideal $I$ of a Noetherian complete
local ring with $I\in\mathscr{A}(R)$ and any non-zero $I$-cofinite $R$-module
$M$, the equality
$\operatorname{\mathsf{dim}}R/(I+\mbox{Ann}\,_{R}M)=\operatorname{\mathsf{dim}}M$
holds.

In the present paper, we provide an affirmative answer to the above question
without any additional assumption. Indeed, we prove the following result:

######  Theorem 1.2.

Let $I$ be and ideal of a complete local ring $R$ and $M$ a non-zero
$I$-cofinite $R$-module. Then __

$\operatorname{\mathsf{dim}}R/(I+\mbox{Ann}\,_{R}M)=\operatorname{\mathsf{dim}}M.$

Here, we should notice that the category of $I$-cofinite $R$-modules with
dimension less than one is Abelian (see [5, Theorem 2.7] ). But, the category
of $I$-cofinite $R$-modules with a dimension greater than two is not
necessarily Abelian. For example, consider the following counterexample of
Hartshorne: Let $R=k[[x,y,z,w]]$, $I=(x,z)$ and $M=R/(xy-zw)$. Now, set
$t:=xy-zw$ and by the exact sequence $0\longrightarrow
R\stackrel{{\scriptstyle t}}{{\longrightarrow}}R\longrightarrow
M\longrightarrow 0$, one can get the following induced exact sequence:

$\cdots\longrightarrow\mbox{H}_{I}^{2}(R)\stackrel{{\scriptstyle
t^{*}}}{{\longrightarrow}}\mbox{H}_{I}^{2}(R)\longrightarrow\mbox{H}_{I}^{2}(M)\longrightarrow
0.$

Since $\mbox{H}_{I}^{i}(R)=0$ for all $i\neq 2$, one can use [14, Proposition
2.1] to see that the $R$-module $\mbox{H}_{I}^{2}(R)$ is $I$-cofinite.
However, $\mbox{coker}\,(t^{*})=\mbox{H}_{I}^{2}(M)$ is not $I$-cofinite (see
[9]). Furthermore, using the fact that
$\operatorname{Supp}_{R}(\mbox{H}_{I}^{2}(R))=\operatorname{Supp}_{R}(\underset{i\in\mathbb{N}_{0}}{\bigoplus}\mbox{H}_{I}^{i}(R))=\operatorname{Supp}_{R}(R/I)$,
implies that $\operatorname{\mathsf{dim}}_{R}(\mbox{H}_{I}^{2}(R))=2$.

##  2\. results

The starting point of this section is the following main result.

######  Theorem 2.1.

Let $I$ be and ideal of a complete local ring
$(R,\operatorname{\mathfrak{m}})$ and $M$ a non-zero $I$-cofinite $R$-module.
Then __

$\operatorname{\mathsf{dim}}R/(I+\mbox{Ann}\,_{R}M)=\operatorname{\mathsf{dim}}M.$

###### Proof.

We use induction on $\operatorname{\mathsf{dim}}_{R}M$ to prove the result.
First set $\mathfrak{b}:=\mbox{Ann}\,_{R}M$, and then assume that
$\operatorname{\mathsf{dim}}M=0$. Then, using [11, Lemma 2.1] implies that $M$
is Artinian; and thus
$\operatorname{\mathsf{dim}}R/(I+\mathfrak{b})=0=\operatorname{\mathsf{dim}}M$,
by [2, Lemma 2.1]. Now, let $\operatorname{\mathsf{dim}}M\geq 1$ and suppose
that the result has been proved for all cofinite $R$-modules of dimension
$\operatorname{\mathsf{dim}}_{R}M-1.$ Note that since
$\operatorname{Supp}M\subseteq V(I+\mathfrak{b})$, then
$\operatorname{\mathsf{dim}}R/(I+\mathfrak{b})\geq\operatorname{\mathsf{dim}}M.$
Therefore, we may and do assume that
$n:=\operatorname{\mathsf{dim}}R/(I+\mathfrak{b})\geq 0.$ Hence, there are
elements $x_{1},\dots,x_{n}$ in $R-(I+\mathfrak{b})$ such that

$\operatorname{Rad}((x_{1}+(I+\mathfrak{b}),\dots,x_{n}+(I+\mathfrak{b})))=\mathfrak{m}/(I+\mathfrak{b}),$

and so
$\operatorname{Rad}((x_{1},\dots,x_{n})+(I+\mathfrak{b}))=\mathfrak{m}$. By
[2, Lemma 2.4], $\Gamma_{\operatorname{\mathfrak{m}}}(M)$ is an Artinian
$I$-cofinite $R$-module. Therefore, by a similar argument in the first step of
induction, we have
$\operatorname{Rad}(I+\mbox{Ann}\,_{R}\Gamma_{\operatorname{\mathfrak{m}}}(M))\supseteq\operatorname{\mathfrak{m}}$.
Now, set $\overline{M}:=M/\Gamma_{\operatorname{\mathfrak{m}}}(M)$ and
consider the following short exact sequence:

$0\longrightarrow\Gamma_{\operatorname{\mathfrak{m}}}(M)\longrightarrow
M\longrightarrow\overline{M}\longrightarrow 0,$

which shows that the $R$-module $\overline{M}$ is $I$-cofinite and
$\operatorname{\mathsf{dim}}\overline{M}=\operatorname{\mathsf{dim}}_{R}M$.
Furthermore, since
$\operatorname{Rad}(\mathfrak{b})=\operatorname{Rad}(\mbox{Ann}\,_{R}\Gamma_{\mathfrak{m}}(M)\cap\mbox{Ann}\,_{R}\overline{M})$
and
$\operatorname{Rad}(I+\mbox{Ann}\,_{R}\Gamma_{\operatorname{\mathfrak{m}}}(M))\supseteq\operatorname{\mathfrak{m}}$,
then by considering the following equalities:

$\begin{array}[]{rl}\operatorname{Rad}(I+\mathfrak{b})&=\operatorname{Rad}(I+\operatorname{Rad}(\mathfrak{b}))\\\
&=\operatorname{Rad}(I+\operatorname{Rad}(\mbox{Ann}\,_{R}\Gamma_{\mathfrak{m}}(M)\cap\mbox{Ann}\,_{R}\overline{M}))\\\
&=\operatorname{Rad}(I+\mbox{Ann}\,_{R}\Gamma_{\mathfrak{m}}(M)\cap\mbox{Ann}\,_{R}\overline{M})\\\
&=\operatorname{Rad}(I+\mbox{Ann}\,_{R}\Gamma_{\mathfrak{m}}(M))\cap\operatorname{Rad}(I+\mbox{Ann}\,_{R}\overline{M})\\\
&=\mathfrak{m}\cap\operatorname{Rad}(I+\mbox{Ann}\,_{R}\overline{M})\\\
&=\operatorname{Rad}(I+\mbox{Ann}\,_{R}\overline{M}),\end{array}$

one has
$\operatorname{\mathsf{dim}}R/(I+\mathfrak{b})=\operatorname{\mathsf{dim}}R/(I+\mbox{Ann}\,_{R}\overline{M})$.
Therefore, by replacing $M$ with $\overline{M}$, we may and do assume that
$\Gamma_{\mathfrak{m}}(M)=0$, and so
$\mathfrak{m}\not\in\operatorname{Ass}_{R}M$. Therefore, one can deduce that

$(x_{1},\dots,x_{n})\nsubseteq\bigcup_{\mathfrak{p}\in\operatorname{Ass}_{R}M}\mathfrak{p}.$

So, there exists an element $b\in(x_{2},\dots,x_{n})$ such that
$z:=x_{1}+b\notin\bigcup_{\mathfrak{p}\in\operatorname{Ass}_{R}M}\mathfrak{p},$
and also $(x_{1},x_{2},\dots,x_{n})=(z,x_{2},\dots,x_{n})$. Hence, by the
following equalities:

$\begin{array}[]{rl}\mathfrak{m}/(I+\mathfrak{b})&=\operatorname{Rad}(\frac{(x_{1},\dots,x_{n})+(I+\mathfrak{b})}{(I+\mathfrak{b})})\\\
&=\operatorname{Rad}(\frac{(z,x_{2},\dots,x_{n})+(I+\mathfrak{b})}{I+\mathfrak{b}})\\\
&=\operatorname{Rad}((z+(I+\mathfrak{b}),x_{2}+(I+\mathfrak{b}),\dots,x_{n}+(I+\mathfrak{b}))),\end{array}$

one can deduce that the element $z+(I+\mathfrak{b})$ is a subset of a system
of parameters for $R/(I+\mathfrak{b})$. Here, we should notice that
$z\not\in(I+\mathfrak{b})$. It therefore follows from [15, Proposition 15.22]
that

(2.1)
$\displaystyle\operatorname{\mathsf{dim}}R/(I+\mathfrak{b})=\operatorname{\mathsf{dim}}R/(Rz+I+\mathfrak{b})+1.$

Next, in view of [3, Lemma 4.2] we have that the $R$-module $H^{1}_{Rz}(M)$ is
a non-zero $(I+Rz)$-cofinite module and
$\operatorname{\mathsf{dim}}_{R}\mbox{H}^{1}_{Rz}(M)=\operatorname{\mathsf{dim}}_{R}M-1$.
Therefore, by the inductive hypothesis one has the following equality:

(2.2)
$\operatorname{\mathsf{dim}}R/(I+Rz+\mbox{Ann}\,_{R}\mbox{H}^{1}_{Rz}(M))=\operatorname{\mathsf{dim}}_{R}\mbox{H}^{1}_{Rz}(M)=\operatorname{\mathsf{dim}}_{R}M-1.$

Now, we claim that
$z\not\in\bigcup_{\mathfrak{p}\in\operatorname{Ass}_{R}M/(0:_{M}I^{n})}\mathfrak{p}$
for each $n\in\mathbb{N}$. To do this, contrary assume that
$z\in\bigcup_{\mathfrak{p}\in\operatorname{Ass}_{R}M/(0:_{M}I^{n})}\mathfrak{p}$
for some $t\in\mathbb{N}$. Hence, there is
$\mathfrak{p}\in\operatorname{Ass}_{R}M/(0:_{M}I^{t})$ such that
$z\in\mathfrak{p}$ and also there is an element $\beta\in M$ with
$\beta\not\in(0:_{M}I^{t})$ such that
$\mathfrak{p}=(0:_{R}\beta+(0:_{M}I^{t}))$. Therefore $z\beta I^{t}=0$; and
thus $I^{t}\beta\subseteq(0:_{M}Rz)=0$. So, $\beta\in(0:_{M}I^{t})$ which is a
contradiction. Now, for each $n\in\mathbb{N}$, by the exact sequence

$0\longrightarrow(0:_{M}I^{n})\longrightarrow M\longrightarrow
M/(0:_{M}I^{n})\longrightarrow 0,$

one get the exact sequence $0\longrightarrow
H^{1}_{Rz}((0:_{M}I^{n}))\longrightarrow H^{1}_{Rz}(M),$ which shows that
$\mbox{Ann}\,_{R}H^{1}_{Rz}(M)\subseteq\mbox{Ann}\,_{R}H^{1}_{Rz}((0:_{M}I^{n})).$
Since $z$ is a regular element on the finitely generated $R$-module
$(0:_{M}I^{n})$, then by [1, Theorem 3.4] one has the equality
$\mbox{Ann}\,_{R}H^{1}_{Rz}((0:_{M}I^{n}))=\mbox{Ann}\,_{R}(0:_{M}I^{n}).$
Hence, by considering the following

$\begin{array}[]{rl}\mbox{Ann}\,_{R}M&\subseteq\mbox{Ann}\,_{R}H^{1}_{Rz}(M)\\\
&\subseteq\bigcap_{n=1}^{\infty}\mbox{Ann}\,_{R}(0:_{M}I^{n})\\\
&=\mbox{Ann}\,_{R}M,\end{array}$

we can get the equality
$\mbox{Ann}\,_{R}H^{1}_{Rz}(M)\overset{{\dagger}}{=}\mbox{Ann}\,_{R}M$.
Therefore, given the (2.1), (2.2) and † we have the following equalities:

$\begin{array}[]{rl}\operatorname{\mathsf{dim}}R/(I+\mathfrak{b})&=\operatorname{\mathsf{dim}}R/(Rz+I+\mathfrak{b})+1\\\
&=\operatorname{\mathsf{dim}}R/(Rz+I+\mbox{Ann}\,_{R}H^{1}_{Rz}(M))+1\\\
&=\operatorname{\mathsf{dim}}_{R}M-1+1\\\
&=\operatorname{\mathsf{dim}}_{R}M,\end{array}$

as required. ∎

######  Remark 2.2.

_There exists a two-dimensional Noetherian local domain $(R,\mathfrak{m})$
which does not have a maximal Cohen-Macaulay $R$-module (see [10, §1] and
[7]). Therefore, by [4, Corollay 3.6], over such a ring the $R$-module
$\mbox{H}_{\mathfrak{m}}^{1}(R)$ can not be finitely generated. Now, let $x$
be a nonzero element of $R$ and consider the following exact sequence:_

$0\longrightarrow\Gamma_{\mathfrak{m}}(R/xR)\longrightarrow\mbox{H}_{\mathfrak{m}}^{1}(R)\stackrel{{\scriptstyle
x}}{{\longrightarrow}}\mbox{H}_{\mathfrak{m}}^{1}(R),$

_which is induced from the exact sequence $0\longrightarrow
R\stackrel{{\scriptstyle x}}{{\longrightarrow}}R\longrightarrow
R/xR\longrightarrow 0.$ Therefore, one has the following isomorphism:_

(2.3)
$\displaystyle\Gamma_{\mathfrak{m}}(R/xR)\cong\operatorname{\mathsf{Hom}}_{R}(R/Rx,\mbox{H}^{1}_{\mathfrak{m}}(R)).$

_If $x\in\mbox{Ann}\,_{R}(\mbox{H}_{\mathfrak{m}}^{1}(R))$, then by the above
isomorphism $\Gamma_{\mathfrak{m}}(R/xR)\cong\mbox{H}_{\mathfrak{m}}^{1}(R)$
which is a contradiction by the fact that $\mbox{H}_{\mathfrak{m}}^{1}(R)$ is
not finitely generated, and so we have
$\mbox{Ann}\,_{R}(\mbox{H}_{\mathfrak{m}}^{1}(R))=0$.
Furthermore, by the isomorphism (2.3),
$\operatorname{\mathsf{Hom}}_{R}(R/Rx,\mbox{H}^{1}_{\mathfrak{m}}(R))$ is
finitely generated and also
$\operatorname{Supp}_{R}\mbox{H}^{1}_{\mathfrak{m}}(R)\subseteq\mbox{Max}\,R\cap\mbox{V}(Rx).$
Hence, by [12, Lemma 2.1] one has $\mbox{H}^{1}_{\mathfrak{m}}(R)$ is
$Rx$-cofinite. Therefore, there is the following equality:_

$1=\operatorname{\mathsf{dim}}_{R}(R/Rx)=\operatorname{\mathsf{dim}}_{R}R/(Rx+\mbox{Ann}\,_{R}(\mbox{H}_{\mathfrak{m}}^{1}(R)).$

_But, $\operatorname{\mathsf{dim}}_{R}\mbox{H}_{\mathfrak{m}}^{1}(R)=0$, and
so
$\operatorname{\mathsf{dim}}_{R}R/(Rx+\mbox{Ann}\,_{R}(\mbox{H}_{\mathfrak{m}}^{1}(R))\neq\operatorname{\mathsf{dim}}_{R}\mbox{H}_{\mathfrak{m}}^{1}(R)$.
It therefore follows from Theorem 2.1 that the desired ring $R$ cannot be
complete. So, in our main result, the completeness assumption on $R$ is quite
necessary. _

$\mathbf{Acknowledgments}$. The authors would like to thank Prof. Kamal
Bahmanpour for his valuable and profound comments during the preparation of
the manuscript.

## References

  * [1] K. Bahmanpour, A complex of modules and its applications to local cohomology and extension functors, Math. Scand. 117, (2015), 150-160.
  * [2] K. Bahmanpour, Artinian local cohomology modules of cofinie modules, J. Alg. Appl. 21, (2022), 2250029 (19 pages).
  * [3] K. Bahmanpour, A study of cofiniteness through minimal associated primes, Commun. Algebra, 47, (2019), 1327-1347.
  * [4] K. Bahmanpour, Cohen-Macaulay modules over Noetherian local rings, Bull. Korean Math. Soc. 51 (2014), 373–386.
  * [5] K. Bahmanpour, R. Naghipour and M. Sedghi, _On the category of cofinite modules which is Abelian,_ Proc. Amer. Math. Soc., 142 (2014), 1101–1107.
  * [6] M.P. Brodmann and R.Y. Sharp, Local cohomology; an algebraic introduction with geometric applications, Cambridge University Press, Cambridge, 1998.
  * [7] D. Ferrand and M. Rayanaud, Fibres formelles $\acute{d}$un anneau local Noeth$\acute{e}$rien, Ann. Sci. $\acute{E}$cole Norm. Sup. 3 (1970), 295–311.
  * [8] A. Grothendieck, Local cohomology, Notes by R. Hartshorne, Lecture Notes in Math., 862 (Springer, New York, 1966).
  * [9] R. Hartshorne, Affine duality and cofiniteness, Invent. Math. 9, (1970), 145-164.
  * [10] M. Hochster, Cohen-Macaulay modules, Proc. Kansas Commutative Algebra Conference, Lecture Notes Math. 311, Springer-Verlag, Berlin, 1973, pp. 120–152.
  * [11] L. Melkersson, Cofiniteness with respect to ideals of dimension one, J. Algebra, 372, (2012), 459-462.
  * [12] L. Melkersson, Properties of cofinite modules and application to local cohomology, Math. Proc. Camb. Philos. Soc., 125, (1999), 417-423.
  * [13] G. Pirmohammadi, A note on cofinite modules over Noetherian complete local rings, Bull. Belg. Math. Soc. Simon Stevin, 29, (2022), 435-441.
  * [14] M. Rahro Zargar and H. Zakeri, _On injective and Gorenstein injective dimensions of local cohomology modules_ , Algebra Colloq. 22, (2015), 935–946.
  * [15] R. Y. Sharp, Steps in Commutative Algebra, Second edition, Cambridge University Press, Cambridge, 2000.