An Algorithm to Train Unrestricted Sequential Discrete Morphological
  Neural Networks
There have been attempts to insert mathematical morphology (MM) operators
into convolutional neural networks (CNN), and the most successful endeavor to
date has been the morphological neural networks (MNN). Although MNN have
performed better than CNN in solving some problems, they inherit their
black-box nature. Furthermore, in the case of binary images, they are
approximations that loose the Boolean lattice structure of MM operators and,
thus, it is not possible to represent a specific class of W-operators with
desired properties. In a recent work, we proposed the Discrete Morphological
Neural Networks (DMNN) for binary image transformation to represent specific
classes of W-operators and estimate them via machine learning. We also proposed
a stochastic lattice descent algorithm (SLDA) to learn the parameters of
Canonical Discrete Morphological Neural Networks (CDMNN), whose architecture is
composed only of operators that can be decomposed as the supremum, infimum, and
complement of erosions and dilations. In this paper, we propose an algorithm to
learn unrestricted sequential DMNN, whose architecture is given by the
composition of general W-operators. We illustrate the algorithm in a practical
example.
Diego Marcondes, Mariana Feldman, Junior Barrera
# An Algorithm to Train Unrestricted Sequential Discrete Morphological Neural Networks+

###### Abstract

With the advent of deep learning, there have been attempts to insert mathematical morphology (MM) operators into convolutional neural networks (CNN), and the most successful endeavor to date has been the morphological neural networks (MNN). Although MNN have performed better than CNN in solving some problems, they inherit their black-box nature. Furthermore, in the case of binary images, they are approximations, which loose the Boolean lattice structure of MM operators and, thus, it is not possible to represent a specific class of W-operators with desired properties. In a recent work, we proposed the Discrete Morphological Neural Networks (DMNN) for binary image transformation to represent specific classes of W-operators and estimate them via machine learning. We also proposed a stochastic lattice gradient descent algorithm (SLGDA) to learn the parameters of Canonical Discrete Morphological Neural Networks (CDMNN), whose architecture is composed only of operators that can be decomposed as the supremum, infimum, and complement of erosions and dilations. In this paper, we propose an algorithm to learn unrestricted sequential DMNN (USDMNN), whose architecture is given by the composition of general W-operators. We consider the representation of a W-operator by its characteristic Boolean function, and then learn it via a SLGDA in the Boolean lattice of functions. Although both the CDMNN and USDMNN have the Boolean lattice structure, USDMNN are not as dependent on prior information about the problem at hand, and may be more suitable in instances in which the practitioner does not have strong domain knowledge. We illustrate the algorithm in a practical example.

Keywords:discrete morphological neural networks image processing mathematical morphology U-curve algorithms stochastic lattice gradient descent
Introduction

Mathematical morphology is a theory of lattice mappings which can be employed to design nonlinear mappings, the morphological operators, for image processing and computer vision. It originated in the 60s, and its theoretical basis was developed in the 70s and 80s [12, 16, 17]. From the established theory followed the proposal of many families of operators, which identify or transform geometrical and topological properties of images. Their heuristic combination permits to design methods for image analysis. We refer to [5] for more details on practical methods and implementations of the design of mathematical morphology operators.

Since combining basic morphological operators to form a complex image processing pipeline is not a trivial task, a natural idea is to develop methods to automatically design morphological operators based on machine learning techniques [4], what has been extensively done in the literature with great success on solving specific problems. The problems addressed by mathematical morphology concern mainly the processing of binary and gray-scale images, and the learning methods are primarily based on discrete combinatorial algorithms. More details about mathematical morphology in the context of machine learning may be found in [2, 8].

More recently, mathematical morphology methods have been studied in connection with deep neural networks, by either combining convolutional neural networks (CNN) with a morphological operator [10], or by replacing the convolution operations of CNN with basic morphological operators, such as erosions and dilations, obtaining the so-called morphological neural networks (MNN) [7, 9, 13]. A MNN has the general framework of neural networks, and its specificity is on the fact that the layers realize morphological operations. Although it has been seen empirically that convolutional layers could be replaced by morphological layers [7], and MNN have shown a better performance than CNN in some tasks [9], they are not more interpretable than an ordinary CNN. In the context of machine learning theory, the interpretability is related to the notion of hypothesis space, which is a key component of machine learning theory.

In this context, in [11] we proposed the Discrete Morphological Neural Networks (DMNN) for binary image transformation to represent translation invariant and locally defined operators, i.e., W-operators, and estimate them via machine learning. A DMNN architecture is represented by a Morphological Computational Graph that combines operators via composition, infimum, and supremum to build more complex operators. In [11] we proposed a stochastic lattice gradient descent algorithm (SLGDA) to train the parameters of Canonical Discrete Morphological Neural Networks (CDMNN) based on a sample of input and output images under the usual machine learning approach. The architecture of a CDMNN is composed only of canonical operations (supremum, infimum, or complement) and operators that can be decomposed as the supremum, infimum, and complement of erosions and dilations with the same structural element. The DMNN is a true mathematical morphology method since it retains the control over the design
and the interpretability of results of classical mathematical morphology methods, which is a relevant advantage over CNN.

In this paper, we propose an algorithm to train unrestricted sequential DMNN (USDMNN), whose architecture is given by the composition of general W-operators. The algorithm considers the representation of a W-operator by its characteristic Boolean function, which is learned via a SLGDA in the Boolean lattice of functions. This SLGDA differs from that of [11] which minimizes an empirical error in a lattice of sets and intervals that are the structural elements and intervals representing operators such as erosions, dilations, openings, closings and sup-generating.

As opposed to CDMNN, which can be designed from prior information to represent a constrained class of operators, USDMNN are subject to overfitting the data, since it can represent a great class of operators, that may fit the data, but not generalize to new examples. In order to address this issue, we control the complexity of the architecture by selecting from data the window of each W-operator in the sequence (layer). By restricting the window, we create equivalence classes on the characteristic function domain that constrain the class of operators that each layer can represent, decreasing the overall complexity of the operators represented by the architecture and mitigating the risk of overfitting. We propose a SLGDA to select the windows by minimizing a validation error in a lattice of sets within the usual model selection framework in machine learning.

We note that both the CDMNN and the USDMNN are fully transparent, the properties of the operators represented by the trained architectures are fully known, and their results can be interpreted. The advantage of USDMNN is that they are not as dependent on prior information as the CDMNN, which require a careful design of the architecture to represent a _simple_ class of operators with properties necessary to solve the practical problem, as was illustrated in the empirical application in [11]. When there is no prior information about the problem at hand, an USDMNN may be preferable.

In Section 2, we present some notations and definitions, and in Section 3 we formally define the USDMNN that is a particular example of the DMNN proposed by [11]. In Section 4, we present the SLGDAs to learn the windows and the characteristic functions of the W-operators in a USDMNN, and in Section 5 we apply the USDMNN to the same dataset used in [11] in order to compare the results. In Section 6, we present our conclusions.

## 2 W-operators

Let \(E=\mathbb{Z}^{2}\) and denote by \(\mathcal{P}(E)\) the collection of all subsets of \(E\). Denote by \(+\) the vector addition operation. We denote the zero element of \(E\) by \(o\). A _set operator_ is any mapping defined from \(\mathcal{P}(E)\) into itself. We denote by \(\Psi\) the collection of all the operators from \(\mathcal{P}(E)\) to \(\mathcal{P}(E)\). Denote by \(\iota\) the identity set operator: \(\iota(X)=X,X\in\mathcal{P}(E)\).

For any \(h\in E\) and \(X\in\mathcal{P}(E)\), the set \(X+h\coloneqq\{x\in E:x-h\in X\}\) is called the translation of \(X\) by \(h\). We may also denote this set by \(X_{h}\). A set operator
is called _translation invariant_ (t.i) if, and only if, \(\forall h\in E\), \(\psi(X+h)=\psi(X)+h\) for \(X\in\mathcal{P}(E)\).

Let \(W\) be a finite subset of \(E\). A set operator \(\psi\) is called _locally defined within a window \(W\)_ if, and only if, \(\forall h\in E\), \(h\in\psi(X)\iff h\in\psi(X\cap W_{h})\) for \(X\in\mathcal{P}(E)\). The collection \(\Psi_{W}\) of t.i. operators locally defined within a window \(W\in\mathcal{P}(E)\) inherits the complete lattice structure of \((\mathcal{P}(E),\subseteq)\) by setting, \(\forall\psi_{1},\psi_{2}\in\Psi\),

\[\psi_{1}\leq\psi_{2}\iff\psi_{1}(X)\subseteq\psi_{2}(X),\forall X\in\mathcal{ P}(E). \tag{1}\]

Define by \(\Omega=\cup_{W\in\mathcal{P}(E),|W|<\infty}\Psi_{W}\) the subset of \(\Psi\) of all operators from \(\mathcal{P}(E)\) to \(\mathcal{P}(E)\) that are t.i. and locally defined within some finite window \(W\in\mathcal{P}(E)\). The elements of \(\Omega\) are called _\(W\)-operators_.

Any W-operator can be uniquely determined by its kernel, its basis or its characteristic function (see [3] for more details). In special, denote by \(\mathfrak{B}_{W}\coloneqq\{0,1\}^{\mathcal{P}(W)}\) the set of all Boolean functions on \(\mathcal{P}(W)\) and consider the mapping \(T\) between \(\Psi_{W}\) and \(\mathfrak{B}_{W}\) defined by

\[T(\psi)(X)=\begin{cases}1,&\text{ if }o\in\psi(X)\\ 0,&\text{ otherwise.}\end{cases}\qquad\qquad\psi\in\Psi_{W},X\in\mathcal{P}(W).\]

The mapping \(T\) constitutes a lattice isomorphism between the complete lattices \((\Psi_{W},\leq)\) and \((\mathfrak{B}_{W},\leq)\), and its inverse \(T^{-1}\) is defined by \(T^{-1}(f)(X)=\{x\in E:f(X_{-x}\cap W)=1\}\) for \(f\in\mathfrak{B}_{W}\) and \(X\in\mathcal{P}(E)\). We denote by \(f_{\psi}\coloneqq T(\psi)\) the characteristic function of \(\psi\).

## 3 Unrestricted Sequential Discrete Morphological Neural Networks

### Sequential Morphological Computational graph

Let \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{C})\) be a _computational graph_, in which \(\mathcal{V}\) is a general set of vertices, \(\mathcal{E}\subset\{(\mathfrak{v}_{1},\mathfrak{v}_{2})\in\mathcal{V}\times \mathcal{V}:\mathfrak{v}_{1}\neq\mathfrak{v}_{2}\}\) is a set of directed edges, and \(\mathcal{C}:\mathcal{V}\to\Omega\cup\{\vee,\wedge\}\) is a mapping that associates each vertex \(\mathfrak{v}\in\mathcal{V}\) to a _computation_ given by either applying a t.i. and locally defined operator \(\psi\in\Omega\) or one of the two basic operations \(\{\vee,\wedge\}\).

Denoting \(\mathcal{V}=\{\mathfrak{v}_{i},\mathfrak{v}_{1},\ldots,\mathfrak{v}_{n}, \mathfrak{v}_{o}\}\) for a \(n\geq 1\), \(\mathcal{G}\) is a sequential morphological computational graph (MCG) if

\[\mathcal{E}=\{(\mathfrak{v}_{i},\mathfrak{v}_{1}),(\mathfrak{v}_{n},\mathfrak{ v}_{o})\}\bigcup\left\{(\mathfrak{v}_{j},\mathfrak{v}_{j+1}):j=1,\ldots,n-1 \right\},\]

\(\mathcal{C}(\mathfrak{v}_{i})=\mathcal{C}(\mathfrak{v}_{o})=\iota\) and \(\mathcal{C}(\mathfrak{v}_{j})\in\Omega,\ j=1,\ldots,n\). This computational graph satisfies the axioms of MCG (see [11] for more details).

In a sequential MCG, the computation of a vertex \(\mathfrak{v}_{j}\) in \(\mathcal{G}\) receives as input the output of the computation of the previous vertex \(\mathfrak{v}_{j-1}\), and the output of its computation will be used as the input of the computation of the vertex \(\mathfrak{v}_{j+1}\). We assume there is an input vertex \(\mathfrak{v}_{i}\), and an output vertex \(\mathfrak{v}_{o}\), that store
the input, which is an element \(X\in\mathcal{P}(E)\), and output of the computational graph, respectively, by applying the identity operator. Furthermore, each vertex computes an operator in \(\Omega\) and there are no vertices computing supremum or infimum operations.

Denote by \(\psi_{\mathcal{G}}(X)\) the output of vertex \(\mathfrak{v}_{o}\) when the input of vertex \(\mathfrak{v}_{i}\) is \(X\in\mathcal{P}(E)\) as the set operator \(\psi_{\mathcal{G}}:\mathcal{P}(E)\rightarrow\mathcal{P}(E)\) generated by MCG \(\mathcal{G}\). The operator \(\psi_{\mathcal{G}}\) is actually t.i. and locally defined within a window \(W_{\mathcal{G}}\) (cf. Proposition 5.1 in [11]). We define the sequential Discrete Morphological Neural Network represented by \(\mathcal{G}\) as the translation invariant and locally defined set operator \(\psi_{\mathcal{G}}\).

### Sequential Discrete Morphological Neural Networks Architectures

A triple \(\mathcal{A}=(\mathcal{V},\mathcal{E},\mathcal{F})\), in which \(\mathcal{F}\subseteq\Omega^{\mathcal{V}}\), is a sequential Discrete Morphological Neural Network (SDMNN) architecture if \((\mathcal{V},\mathcal{E},\mathcal{C})\) is a sequential MCG for all \(\mathcal{C}\in\mathcal{F}\). A SDMNN architecture is a collection of sequential MCG with the same graph \((\mathcal{V},\mathcal{E})\) and computation map \(\mathcal{C}\) in \(\mathcal{F}\). Since a SDMNN architecture represents a collection of MCG, it actually represents a collection of t.i. and locally defined set operators that can be represented as the composition of W-operators.

For an architecture \(\mathcal{A}=(\mathcal{V},\mathcal{E},\mathcal{F})\), let \(\mathbb{G}(\mathcal{A})=\{\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{C}): \mathcal{C}\in\mathcal{F}\}\) be the collection of MCG generated by \(\mathcal{A}\). We say that \(\mathcal{G}\in\mathbb{G}(\mathcal{A})\) is a realization of architecture \(\mathcal{A}\) and we define \(\mathcal{H}(\mathcal{A})=\{\psi\in\Omega:\psi=\psi_{\mathcal{G}},\mathcal{G}\in \mathbb{G}(\mathcal{A})\}\) as the collection of t.i. and locally defined set operators that can be realized by \(\mathcal{A}\).

A SDMNN is said unrestricted if its interior vertices \(\mathfrak{v}_{j}\) can compute any W-operator locally defined within a \(W_{j}\), so it holds \(\mathcal{F}=\{\iota\}\times\Psi_{W_{1}}\times\cdots\times\Psi_{W_{n}}\times\{\iota\}\). We denote by \(n=|\mathcal{V}|-2\) the depth of an unrestricted sequential DMNN (USDMNN) and by \(|W_{j}|\) the width of the layer represented by vertex \(\mathfrak{v}_{j},j=1,\ldots,n\).

As an example, consider an USDMNN with three hidden layers. For fixed windows \(W_{1},W_{2},W_{3}\in\mathcal{P}(E)\), this sequential architecture realizes the operators in \(\Psi_{W}\), with \(W=W_{1}\oplus W_{2}\oplus W_{3}\), in which \(\oplus\) stands for the _Minkowski addition_, that can be written as the composition of operators in \(\Psi_{W_{1}},\Psi_{W_{2}}\) and \(\Psi_{W_{3}}\), that is, \(\mathcal{H}(\mathcal{A})=\{\psi\in\Psi_{W}:\psi=\psi^{W_{3}}\psi^{W_{2}}\psi^{W_ {1}};\psi^{W_{i}}\in\Psi_{W_{i}},i=1,2,3\}\). For a proof of this fact, see [3].

### Representation of USDMNN

The USDMNN realized by MCG \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{C})\) can be represented by a sequence \(\{\psi_{1},\ldots,\psi_{n}\}\), \(n\geq 2\), of \(W\)-operators with windows \(W_{1},\ldots,W_{n}\) as the composition

\[\psi_{\mathcal{G}}=\psi_{n}\circ\cdots\circ\psi_{1} \tag{2}\]

in which \(\psi_{j}=\mathcal{C}(\mathfrak{v}_{j}),j=1,\ldots,n\). Based on (2), we propose a representation for the class of operators realized by an USDMNN.
For each \(i=1,\ldots,n\), we fix a \(d_{i}\geq 3\) odd and assume that each window \(W_{i},i=1,\ldots,n\), is a connected subset of \(F_{d_{i}}=\{-(d_{i}-1)/2,\ldots,(d_{i}-1)/2\}^{2}\), the square of side \(d_{i}\) centered at the origin of \(E\). This means that, for every \(w,w^{\prime}\in W_{i}\), there exists a sequence \(w_{0},\ldots,w_{r}\in W_{i},r\geq 1\), such that \(w_{0}=w,w_{r}=w^{\prime}\) and \(\|w_{i}-w_{i+1}\|_{\infty}=1\), for all \(i=0,\ldots,r-1\). Denoting \(\mathcal{C}_{d}=\{W\subseteq F_{d}:W\text{ is connected}\}\), we assume that \(W_{i}\in\mathcal{C}_{d_{i}}\) for all \(i=1,\ldots,n\).

For each \(W\in\mathcal{C}_{d_{i}}\), let \(\mathcal{B}_{W}=\{f:\mathcal{P}(W)\mapsto\{0,1\}\}\) be the set of all binary functions on \(\mathcal{P}(W)\), and define \(\mathcal{F}_{i}=\{(W,f):W\in\mathcal{C}_{d_{i}},f\in\mathcal{B}_{W}\}\) as the collection of \(W\)-operators with window \(W\) in \(\mathcal{C}_{d_{i}}\) and characteristic function \(f\) in \(\mathcal{B}_{W}\), which are completely defined by a pair \((W,f)\). Finally, let \(\Theta=\prod_{i=1}^{n}\mathcal{F}_{i}\) be the Cartesian product of \(\mathcal{F}_{i}\). Observe that an element \(\theta\) in \(\Theta\) is actually a sequence of \(n\)\(W\)-operators with windows in \(\mathcal{C}_{d_{i}},i=1,\ldots,n\), which we denote by \(\theta=\{(W_{1},f_{1}),\ldots,(W_{n},f_{n})\}\). Denoting the \(W\)-operator represented by \((W_{i},f_{i})\) as \(\psi_{i}\), a \(\theta\in\Theta\) generates a USDMNN \(\psi_{\theta}\) via expression (2).

The USDMNN architecture \(\mathcal{A}=(\mathcal{V},\mathcal{E},\mathcal{F})\) with \(n\) hidden layers and \(\mathcal{F}=\{\iota\}\times\Psi_{F_{d_{1}}}\times\cdots\times\Psi_{F_{d_{n}}} \times\{\iota\}\) is such that \(\mathcal{H}(\mathcal{A})=\{\psi_{\theta}:\theta\in\Theta\}\), so \(\Theta\) is a representation for the class of operators generated by the architecture \(\mathcal{A}\).

Since an operator locally defined in \(W\) is also locally defined in any \(W^{\prime}\supset W\) (cf. Proposition 5.1 in [3]) it follows that \(\Theta\) is actually an overparametrization of \(\mathcal{H}(\mathcal{A})\) since there are many representations \((W^{\prime},f_{\psi})\) for a same W-operator locally defined in \(W\subsetneq F_{d_{i}}\). This overparametrization also happens in the representation of CDMNN proposed in [11] and we take advantage of it to propose a SLGDA to train USDMNN and mitigate the risk of overfitting.

## 4 Training USDMNN via the stochastic lattice gradient descent algorithm

The training of a USDMNN is performed by obtaining a sequence \(\hat{\theta}\in\Theta\) of \(W\)-operators via the minimization of an empirical error on a sample \(\{(X_{1},Y_{1}),\ldots,\)\((X_{N},Y_{N})\}\), of \(N\) input images \(X\) and output target transformed images \(Y\). In order to mitigate overfitting the sample, the training of a USDMNN will be performed by a two-step algorithm that, for a fixed sequence of windows, learns a sequence of characteristic functions by minimizing the empirical error \(L_{t}\) in a training sample, and then learns a sequence of windows by minimizing an empirical error \(L_{v}\) in a validation sample over the sequences of windows. More details about the empirical errors \(L_{t}\) and \(L_{v}\) will be given in Section 5.

These two steps are instances of an algorithm for the minimization of a function in a subset of a Boolean lattice. On the one hand, the set \(\mathcal{C}\coloneqq\prod_{i=1}^{n}\mathcal{C}_{d_{i}}\) of all sequences of \(n\) connected windows is a subset of a Boolean lattice isomorphic to \(\prod_{i=1}^{n}\{0,1\}^{F_{d_{i}}}\), so minimizing the validation error over the windows means minimizing a function in a subset of a Boolean lattice. On the other hand, for a fixed sequence of windows \((W_{1},\ldots,W_{n})\in\mathcal{C}\), the set \(\mathcal{B}_{W_{1}}\times\cdots\times\mathcal{B}_{W_{n}}\) of all sequences of characteristic functions with these windows is a Boolean lattice isomorphic to \(\{0,1\}^{\mathcal{P}(W_{1})}\times\cdots\times\{0,1\}^{\mathcal{P}(W_{n})}\), so minimizing the training error in this space means minimizing a function in a Boolean lattice.
The U-curve algorithms [1, 6, 14, 15] were proposed to minimize a U-curve function on a Boolean lattice. In summary, these algorithms perform a greedy search of a Boolean lattice, at each step jumping to the point at distance one with the least value of the function, and stopping when all neighbor points have a function value greater or equal to that of the current point. This greedy search of a lattice, that at each step goes to the direction that minimizes the function, is analogous to the dynamic of the gradient descent algorithm to minimize a function with domain in \(\mathbb{R}^{p}\). Inspired by the U-curve algorithms and by the success of stochastic gradient descent algorithms for minimizing overparametrized functions in \(\mathbb{R}^{p}\), and following the ideas of [11], we propose a stochastic lattice gradient descent algorithm (SLGDA) to train USDMNN. In Figure 1, we present the main ideas of the algorithm, and in Sections 4.1 and 4.2 we formally define it.

### Training a USDMNN with fixed windows

For each \(\mathbf{W}\coloneqq\{W_{1},\ldots,W_{n}\}\in\mathcal{C}\) let \(\varTheta_{\mathbf{W}}\coloneqq\{\{(W_{1},f_{1}),\ldots,(W_{n},f_{n})\}:f_{i}\in \mathcal{F}_{W_{i}},i=1,\ldots,n\}\) be all sequences of \(W\)-operators with windows \(\mathbf{W}\). Observe

Figure 1: Illustration of the deterministic version of the SLGDA to (a) learn the USDMNN windows and (b) train a USDMNN with fixed windows. To simplify the illustration, we considered only the possibility of adding a point to a window, and flipping a bit from \(0\) to \(1\) of a characteristic function, at each step, even though a point can be erased from a window, and a flipping from \(1\) to \(0\) may happen, if they have the least respective error. The training error \(L_{t}\) or validation error \(L_{v}\) of each point is on top of it.
there is a bijection between \(\Theta_{\mathbf{W}}\) and the Boolean lattice \(\prod_{i=1}^{n}\{0,1\}^{\mathcal{P}(W_{i})}\), and consider the Boolean lattice \((\Theta_{\mathbf{W}},\leq)\).

Denoting by \(d\) the distance in the acyclic directed graph \((\Theta_{\mathbf{W}},\leq)\), we define the neighborhood of a \(\theta\in\Theta_{\mathbf{W}}\) as \(N(\theta)=\{\theta^{\prime}\in\Theta_{\mathbf{W}}:d(\theta,\theta^{\prime})=1\}\). Observe that \(\theta,\theta^{\prime}\in\Theta_{\mathbf{W}}\) are such that \(d(\theta,\theta^{\prime})=1\) if, and only if, all their characteristic functions but one are equal, and in the one in which they differ, the difference is in only one point of their domain. In other words, \(\theta^{\prime}\) is obtained from \(\theta\) by flipping the image of one point of one characteristic function from \(0\) to \(1\) or from \(1\) to \(0\).

The SLGDA for learning the characteristic functions of a USDMNN with fixed windows is formalized in Algorithm 1. The initial point \(\theta\in\Theta_{\mathbf{W}}\), a batch size \(b\), the number \(n\) of neighbors to be sampled at each step, and the number of training epochs are fixed. The initial point is stored as the point with minimum training error visited so far. For each epoch, the training sample is randomly partitioned in \(N/b\) batches, and we denote the training error on batch \(j\) by \(L_{t}^{(j)}\). For each batch, \(n\) neighbors of \(\theta\) are sampled and \(\theta\) is updated to the sampled neighbor with the least training error \(L_{t}^{(j)}\), that is calculated on the sample batch \(j\). Observe that \(\theta\) is updated at each batch, so during an epoch, it is updated \(N/b\) times. At the end of each epoch, the training error \(L_{t}(\theta)\) of \(\theta\) on the whole training sample is compared with the error of the point with the least training error visited so far at the end of an epoch, and it is stored as this point if its training error is lesser. After the predetermined number of epochs, the algorithm returns the point with the least training error on the whole sample visited at the end of an epoch.

Observe that Algorithm 1 has two sources of stochasticity: the sample of neighbors and the sample batches. If \(n=n(\theta)\coloneqq|N(\theta)|\) and \(b=N\), then this algorithm reduces to the deterministic one illustrated in Figure 1. Furthermore, the complexity of the algorithm is controlled by the number \(n\) of sampled neighbors, the batch size \(b\) and the number of epochs. See [11] for a further discussion about a SLGDA.

### Learning the USDMNN windows

In order to learn the windows of a USDMNN, we apply the SLGDA on \(\mathcal{C}\), that is a subset of the Boolean lattice \(\prod_{i=1}^{n}\{0,1\}^{F_{d_{i}}}\). For each \(\mathbf{W}\in\mathcal{C}\), let \(L_{v}(\mathbf{W})\coloneqq L_{v}(\theta_{\mathbf{W}}^{\mathbb{A}})\) be the validation error of the USDMNN realized by \(\theta_{\mathbf{W}}^{\mathbb{A}}\), which was learned by Algorithm 1.

We define the neighborhood of \(\mathbf{W}\) in \(\mathcal{C}\) as \(N(\mathbf{W})=\big{\{}\mathbf{W}^{\prime}\in\mathcal{C},d(\mathbf{W},\mathbf{W}^{\prime})=1 \big{\}}\) in which \(d\) means the distance in the acyclic directed graph \((\mathcal{C},\leq)\). Observe that \(\mathbf{W},\mathbf{W}^{\prime}\in\mathcal{C}\) are such that \(d(\mathbf{W},\mathbf{W}^{\prime})=1\) if, and only if, all their windows but one are equal, and in the one in which they differ, the difference is of one point. In other words, \(\mathbf{W}^{\prime}\) is obtained from \(\mathbf{W}\) by adding or removing one point from one of its windows.

The SLGDA for learning the windows of a USDMNN is formalized in Algorithm 2. The initial point \(\mathbf{W}\in\mathcal{C}\), a batch size \(b\), the number \(n\) of neighbors to
be sampled at each step, and the number of training epochs are fixed. The initial point is stored as the point with minimum validation error visited so far. For each epoch, the validation sample is randomly partitioned in \(N/b\) batches, and we denote the validation error of any \(\mathbf{W}\) on batch \(j\) by \(L_{v}^{(j)}(\mathbf{W})\coloneqq L_{v}^{(j)}(\theta_{\mathbf{W}}^{h})\) which is the empirical error on the \(j\)-th batch of the validation sample of the USDMNN realized by \(\theta_{\mathbf{W}}^{h}\), learned by Algorithm 1.

For each batch, \(n\) neighbors of \(\mathbf{W}\) are sampled and \(\mathbf{W}\) is updated to the sampled neighbor with the least validation error \(L_{v}^{(j)}\). At the end of each epoch, the validation error \(L_{v}(\mathbf{W})\) of \(\mathbf{W}\) on the whole validation sample is compared with the error of the point with the least validation error visited so far at the end of an epoch, and it is stored as this point if its validation error is lesser. After the predetermined number of epochs, the algorithm returns the point with the least validation error on the whole sample visited at the end of an epoch.

Algorithms 1 and 2 are analogous and differ only on the lattice (\(\Theta_{\mathbf{W}}\) and \(\mathcal{C}\)) they search and the function they seek to minimize (the training and the validation error).

```
1:\(\theta\in\Theta_{\mathbf{W}},n,b,Epochs\)
2:\(L_{min}\gets L_{t}(\theta)\)
3:\(\theta_{\mathbf{W}}^{h}\leftarrow\theta\)
4:for run \(\in\{1,\ldots,\text{Epochs}\}\)do
5: ShuffleBatches(\(b\))
6:for\(j\in\{1,\ldots,N/b\}\)do
7:\(\tilde{N}(\theta)\leftarrow\text{SampleNeighbors}(\theta,n)\)
8:\(\theta\leftarrow\theta^{\prime}\) s.t. \(\theta^{\prime}\in\tilde{N}(\theta)\) and \(L_{t}^{(j)}(\theta^{\prime})=\min\{L_{t}^{(j)}(\theta^{\prime\prime}):\theta^ {\prime\prime}\in\tilde{N}(\theta)\}\)
9:if\(L_{t}(\theta)<L_{min}\)then
10:\(L_{min}\gets L_{t}(\theta)\)
11:\(\theta_{\mathbf{W}}^{h}\leftarrow\theta\)
12:return\(\theta_{\mathbf{W}}^{h}\)
```

**Algorithm 1** Stochastic lattice gradient descent algorithm for learning the characteristic functions of a USDMNN with fixed windows \(\mathbf{W}=\{W_{1},\ldots,W_{n}\}\).

## 5 Application: Boundary recognition of digits with noise

As an example, we treat the problem of boundary recognition in digits with noise. We consider the USDMNN with two layers, and windows contained in the \(3\times 3\) square trained with a training sample of 10, and a validation sample of 10, \(56\times 56\) binary images. The training and validation samples are the same used in [11], the initial windows were considered as the five point cross centered at the origin, and the initial characteristic functions of a fixed window were those that minimized the training loss of its neighbor window visited before, except to the window on which they differ, where the characteristic function is initiated randomly. The algorithms were implemented in **python** and are available at
[https://github.com/MarianaFeldman/USDMM](https://github.com/MarianaFeldman/USDMM). The training was performed on a personal computer with processor 13th Gen Intel Core i7-1355U x 12 and 16 GB of ram.

We consider the intersection of union (IoU) error that is more suitable for form or object detection tasks. The IoU error of \(\psi_{\theta}\) in the training and validation sample is, respectively,

\[L_{t}(\theta)=1-\frac{1}{10}\sum_{k=1}^{10}\frac{|Y_{k}\cap\psi_{\theta}(X_{k}) |}{|Y_{k}\cup\psi_{\theta}(X_{k})|}\quad\ L_{v}(\theta)=1-\frac{1}{10}\sum_{k=1 }^{10}\frac{|Y_{k}^{(v)}\cap\psi_{\theta}(X_{k}^{(v)})|}{|Y_{k}^{(v)}\cup\psi_{ \theta}(X_{k}^{(v)})|}\]

that is, the mean proportion of pixels in \(Y\cup\psi_{\theta}(X)\) that are not in \(Y\cap\psi_{\theta}(X)\) among the sample points in the training and validation sample.

The results are presented in Table 1 and Figure 2. We trained the two layer USDMNN with batch sizes 1 and 10, sampling 10 neighbors in the SLGDA for the characteristic functions and considering all neighbors in the SLGDA for the windows. For the batch size 1, we considered 50 epochs to train the windows and 100 epochs to train the characteristic functions, while for the batch size 10 we considered 19 and 50 epochs, respectively. These batch sizes refer to the characteristic function SLGDA and in both cases we considered a batch size of 10 for the window SLGDA. The best result was obtained with batch size 10, although it took around ten times more to train. The SLGDA for the characteristic functions took an average of 17 epochs to reach the minimum with batch size 1, and an average of 35 epochs with batch size 10, what is expected since with batch size 1 the characteristic function is actually updated 10 times at each epoch.

The time to train these USDMNN was significantly greater than that it took to train CDMNN in [11], where the best architecture had a total training time of less than one hour. Moreover, as opposed to what was observed with CDMNN, the best validation error was obtained with a batch size of 10 and was actually
lesser than the minimum validation error obtained in [11] before fine training (0.066). Furthermore, the minimum training loss attained via USDMNN (0.037) was lesser than the minimum training loss obtained in [11] (0.049). Therefore, the USDMNN have obtained similar empirical results as the CDMNN in [11] without any prior information, but at a greater computational cost.

## 6 Conclusion

In this paper, we proposed a hierarchical SLGDA to train USDMNN and illustrated it in a simple example. We obtained empirical results as good as that of [11], but much more computational resources were necessary, so high algorithmic complexity was the price to pay to obtain good results without considering prior information to design a specific CDMNN architecture.

The example in this paper is only an illustration of the method, and it is necessary to improve the algorithm implementation. We are currently working on an efficient implementation of the hierarchical SLGDA that, we believe, will significantly decrease the training time, so methods based on USDMNN may also be competitive with CDMNN from a computational complexity perspective. With a more efficient algorithm, it will be possible to fine train the USDMNN and

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline b & Min. Train & Learned Train & Min Val & Total time (h) & Time to min. (h) & Epochs to min. (W) & Mean Epochs to min (f) & W visited \\ \hline
1 & 0.050 & 0.090 & 0.1571 & **5.84** & **4.81** & **42** & **17** & 589 \\
10 & **0.037** & **0.044** & **0.060** & 62.39 & 37.95 & 12 & 35 & **252** \\ \hline \end{tabular}
\end{table}
Table 1: Results of the two layer USDMNN trained with batch sizes \(b=1\) and \(b=10\) for the characteristic function SLGDA. We present the minimum training loss observed during training; the training and validation loss of the trained USDMNN; the algorithm total time and time until the minimum validation error; the number of epochs to the minimum validation error and the average number of epochs until the minimum training error with fixed windows; and the number of visited windows.

Figure 2: Result obtained after applying to the validation sample each layer of the USDMNN trained with a batch size of 10.
better study the effect of settings such as the number of layers and the window size on the model performance. An efficient method to train DMNN without the need of strong prior information may help popularize methods based on them among practitioners which do not have strong knowledge in mathematical morphology to design specific CDMNN architectures.
