# Finiteness conditions for the $n$-fold tensor product of groups

Raimundo Bastos  and  Guilherme Ortega  Departamento de Matemática,
Universidade de Brasília, Brasilia-DF, 70910-900 Brazil  (Bastos)
<EMAIL_ADDRESS>(Ortega<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a finitely generated group. We prove that the $n$-fold tensor
product $G^{\otimes n}$ is finite (resp. polycyclic) if and only $G$ is finite
(resp. polycyclic). Further, assuming that $G$ is finitely presented, we show
that $G^{\otimes n}$ is finitely presented if and only if $\gamma_{n}(G)$ is
finitely presented. We also examine some finiteness conditions for the non-
abelian tensor product of groups.

###### Key words and phrases:

finitely presented groups; finiteness conditions; non-abelian tensor product
of groups; $n$-fold tensor product

###### 2010 Mathematics Subject Classification:

20E06, 20E22, 20E34, 20F18, 20F24, 20J99

##  1\. Introduction

Let $G$ and $H$ be groups each of which acts upon the other (on the right),

$G\times H\rightarrow G,\;(g,h)\mapsto g^{h};\;\;H\times G\rightarrow
H,\;(h,g)\mapsto h^{g}$

and on itself by conjugation, in such a way that for all $g,g_{1}\in G$ and
$h,h_{1}\in H$,

(1)
$g^{\left(h^{g_{1}}\right)}=\left(\left(g^{g^{-1}_{1}}\right)^{h}\right)^{g_{1}}\;\;\mbox{and}\;\;h^{\left(g^{h_{1}}\right)}=\left(\left(h^{h_{1}^{-1}}\right)^{g}\right)^{h_{1}}.$

In this situation we say that $G$ and $H$ act compatibly on each other.

Let $G$ and $H$ be groups that act compatibly on each other. The non-abelian
tensor product $G\otimes H$ was introduced by Brown and Loday [5] following
works of Miller [17], Dennis [7] and Lue [16]. It is defined to be the group
generated by all symbols $\;\,g\otimes h,\;g\in G,\;h\in H$, subject to the
relations

$gg_{1}\otimes h=(g^{g_{1}}\otimes h^{g_{1}})(g_{1}\otimes
h)\quad\mbox{and}\quad g\otimes hh_{1}=(g\otimes h_{1})(g^{h_{1}}\otimes
h^{h_{1}})$

for all $g,g_{1}\in G$, $h,h_{1}\in H$. When $G=H$ and all actions are
conjugations, $G\otimes G$ is the non-abelian tensor square. Now, there is a
well defined action of $G$ on $G\otimes G$ by

$(g_{1}\otimes g_{2})^{g_{3}}=g_{1}^{g_{3}}\otimes g_{2}^{g_{3}},$

where $g_{i}\in G$. Moreover, there is a natural action of $G\otimes G$ on $G$
given by

$g_{1}^{g_{2}\otimes g_{3}}=g_{1}^{[g_{2},g_{3}]}.$

With these (compatible) actions we write $G^{\otimes 3}$ to denote the non-
abelian tensor product $(G\otimes G)\otimes G$. Furthermore, for any
$n\geqslant 3$, we can inductively define the $n$-fold tensor product, denoted
by $G^{\otimes n}$, by considering the actions of $G$ and $G^{\otimes n-1}$ on
each other defined by

$(((g_{1}\otimes g_{2})\otimes\ldots\otimes g_{n-2})\otimes
g_{n-1})^{g_{n}}=((g_{1}^{g_{n}}\otimes g_{2}^{g_{n}})\otimes\ldots\otimes
g_{n-2}^{g_{n}})\otimes g_{n-1}^{g_{n}}$

and

$g_{1}^{((g_{2}\otimes g_{3})\otimes\ldots\otimes g_{n-1})\otimes
g_{n}}=g_{1}^{[g_{2},g_{3},\ldots,g_{n}]}.$

Note that all involved actions are compatible. Furthermore, there is a well-
defined homomorphism $\lambda^{G}_{n}\colon G^{\otimes n}\to\gamma_{n}(G)$
defined on generators by

$((g_{1}\otimes g_{2})\otimes\ldots\otimes g_{n-1})\otimes
g_{n}\mapsto[g_{1},g_{2},\ldots,g_{n}].$

Here $\lambda_{2}^{G}$ corresponds to the derived map $\kappa$ of [5] and
$\ker(\lambda_{2}^{G})$ is isomorphic to $\pi_{3}(SK(G,1))$, where $SK(G,1)$
is the suspension of an Eilenberg-MacLane space $K(G,1)$. According to [23,
Proposition 2.8], the sequence

$1\to\Delta(G)\to\ker(\lambda_{2}^{G})\to H_{2}(G)\to 1$

is exact, where $\Delta(G)=\langle g\otimes g\mid g\in G\rangle$ and
$H_{2}(G)$ is the second homology group of the group $G$.

In the present article we consider some finiteness conditions for the non-
abelian tensor product of groups and related constructions. Finiteness
conditions for the non-abelian tensor product and related constructions were
considered in a number of papers (see [1, 2, 8, 9, 10, 11, 15, 18, 24] and
references therein for further results).

In [10], Donadze and Garcia-Martinez proved that if $G$ is a finitely
generated group, then the $n$-fold tensor product $G^{\otimes n}$ is finitely
generated if and only if the subgroup $\gamma_{n}(G)$ is finitely generated.
Here, we prove an analogue of this theorem for finitely presented groups.

######  Theorem 1.1.

Let $G$ be a finitely presented group. Then, the $n$-fold tensor product
$G^{\otimes n}$ is finitely presented if and only if $\gamma_{n}(G)$ is
finitely presented.

It is straightforward to see that the finiteness of $G^{\otimes n}$ does not
imply the finiteness of $G$. For instance, if $G=C_{p^{\infty}}$ is the Prüfer
group, then $G^{\otimes n}$ is trivial, for any $n\geqslant 2$ (see [20] for
more details). The same phenomenon occurs with polycyclic groups. We describe
the following finiteness conditions:

######  Theorem 1.2.

Let $G$ be a finitely generated group.

  1. (1)

The $n$-fold tensor product $G^{\otimes n}$ is finite if and only if $G$ is
finite.

  2. (2)

The $n$-fold tensor product $G^{\otimes n}$ is polycyclic if and only if $G$
is polycyclic.

Let $G$ and $H$ be groups that act compatibly on each other. As usual, the
derivative of $G$ under the action of $H$, denoted by $[G,H]$, is defined to
be the subgroup $\langle g^{-1}g^{h}\,\mid\,g\in G,h\in H\rangle$ of $G$.
Similarly, the subgroup $[H,G]=\langle h^{-1}h^{g}\,\mid\,h\in H,g\in
G\rangle$ of $H$ is called the derivative of $H$ under $G$. By [5, Proposition
2.3 (b)], there are epimorphisms: $\lambda\colon G\otimes H\to[G,H]$ and
$\lambda^{\prime}\colon G\otimes H\to[H,G]$ given by $\lambda(g\otimes
h)=g^{-1}g^{h}$ and $\lambda^{\prime}(g\otimes h)=h^{-g}h$, for each $g\in G$
and $h\in H$. In particular, in the context of the $n$-fold tensor product, it
is customary to write $\lambda_{n}^{G}$ rather than $\lambda^{\prime}$.

The authors of [9] show that if $G$ and $H$ are finitely generated groups
acting on each other compatibly, then the non-abelian tensor product $G\otimes
H$ is finitely generated if and only if the derivatives $[G,H]$ and $[H,G]$
are finitely generated. It is natural to ask whether the analogue of the
previous result is true for finitely presented groups. We obtain the following
related result.

######  Theorem 1.3.

Let $G$ and $H$ be finitely generated groups acting compatibly on each other.
If the derivative $[G,H]$ is finitely presented, then the non-abelian tensor
product $G\otimes H$ is finitely presented.

The paper is organized as follows. In the next section we present the proofs
of Theorems 1.1 and 1.2. Moreover, we show that if $G$ is finitely presented,
then $\ker(\lambda_{n}^{G})$ and $n$-th nilpotent multiplier $M_{n}(G)$ are
finitely generated, for each $n\geq 2$ (see Lemma 2.2 and Corollary 2.3,
below). In the third section we prove Theorem 1.3. In the final section we
present some Schur-Baer type theorems for finitely presented groups.

##  2\. $n$-fold tensor product of groups

Convention. Let $H$ be a normal subgroup of $G$. Then, the following
homomorphisms $G\otimes H\to[G,H]$ and $G\wedge H\to[G,H]$, $g\otimes
h\mapsto[g,h]$, $g\wedge h\mapsto[g,h]$, for each $g\in G$, $h\in H$, will be
denoted by $[\;,\;]$.

Let $M,N,P$ be groups such that we can define crossed modules $\mu:M\to P$ and
$\nu:N\to P$. Observe that with those maps, we can define compatible actions
between $M$ and $N$. Define the fibre product as

$M\times_{P}N=\\{(m,n)\in M\times N\,|\,\mu(m)=\nu(n)\\}.$

The (non-abelian) exterior product $M\wedge^{P}N$ is obtained as follows:

$M\wedge^{P}N=\frac{M\otimes N}{\langle m\otimes n|(m,n)\in
M\times_{P}N\rangle^{M\otimes N}}.$

######  Proposition 2.1.

Let $M,N,P$ groups such that we can define crossed modules $\mu:M\to P$ and
$\nu:N\to P$.

  1. (1)

(Brown and Loday, [5, Theorem 2.12]) There is a sequence:

$\Gamma\big{(}M\times_{P}N/\langle M,N\rangle\big{)}\to M\otimes N\to
M\wedge^{P}N\to 1,$

where $\Gamma$ is Whitehead’s universal quadratic functor defined in [26] and
$\langle M,N\rangle$ is the image of $\lambda\times\lambda^{\prime}$.

  2. (2)

Let $G$ be a group and $n$ a positive integer. Then

$\Gamma\big{(}\gamma_{n}(G)/\gamma_{n+1}(G)\big{)}\to\ker\Big{(}[\;,\;]:G\otimes\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}\to$
$\to\ker\Big{(}[\;,\;]:G\wedge\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}\to 1.$

###### Proof.

(2) Adjusting the first item to our case, let $inc:\gamma_{n}(G)\to G$ and
$Id:G\to G$, then we have that,

$\gamma_{n}(G)\times_{G}G=\\{(g,h)\in\gamma_{n}(G)\times G|\
g=h\\}=\gamma_{n}(G),$

and for any $g\in\gamma_{n}(G)$, $h\in G$,

$\lambda\times\lambda^{\prime}(g\otimes h)=([g,h],[g,h]).$

Hence, $\langle\gamma_{n}(G),G\rangle\cong\gamma_{n+1}(G)$. Finally,

$\gamma_{n}(G)\wedge^{G}G=\frac{\gamma_{n}(G)\otimes G}{\langle g\otimes
h|g=h\rangle^{\gamma_{n}(G)\otimes G}}=\gamma_{n}(G)\wedge G.$

By the previous item, we obtain the following sequence:

$\Gamma\big{(}\gamma_{n}(G)/\gamma_{n+1}(G)\big{)}\to\gamma_{n}(G)\otimes
G\to\gamma_{n}(G)\wedge G\to 1$

Therefore, it follows that,

$\Gamma\big{(}\gamma_{n}(G)/\gamma_{n+1}(G)\big{)}\to\ker\Big{(}[\;,\;]:G\otimes\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}\to$
$\to\ker\Big{(}[\;,\;]:G\wedge\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}\to 1.$

∎

First we will establish that if $G$ is finitely presented, then so is the
kernel $\ker(\lambda^{G}_{n})$. Recall that $G^{\otimes n}$ is a central
extension of $\ker(\lambda^{G}_{n})$ by $\gamma_{n}(G)$.

######  Lemma 2.2.

Let $G$ be a finitely presented group. Then the kernel $\ker(\lambda^{G}_{n})$
is finitely generated, for each $n\geq 2$.

###### Proof.

The proof is by induction on $n$. Assume that $n=2$. It is well known that
$\ker\Big{(}[\;,\;]:G\wedge G\to[G,G]\Big{)}$ is isomorphic to $H_{2}(G)$
which is finitely generated because $G$ is finitely presented [21, 14.1.5]. On
the other hand, by [23, Proposition 2.8] we have a short exact sequence:

$1\to\Delta(G)\to\ker\Big{(}\lambda^{G}_{2}:G\otimes G\to[G,G]\Big{)}\to
H_{2}(G)\to 1,$

where $\Delta(G)=\langle g\otimes g\ \mid\ g\in G\rangle$. Since $G^{ab}$ is
finitely generated, $\Delta(G^{ab})$ is also finitely generated [23, Section
3], which implies that $\ker\Big{(}\lambda^{G}_{2}:G\otimes G\to[G,G]\Big{)}$
is finitely generated.

Now, assuming that the lemma holds for $\lambda^{G}_{n}$, we will prove the
same for $\lambda^{G}_{n+1}$. Consider the central extension of groups

$1\to\ker\Big{(}\lambda^{G}_{n}\Big{)}\to G^{\otimes n}\to\gamma_{n}(G)\to 1.$

By [4, Proposition 9],

$\Big{(}\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes G\Big{)}\to G^{\otimes
n}\otimes G\to\gamma_{n}(G)\otimes G\to 1$

is an exact sequence. Denote the homomorphism
$\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes G\to G^{\otimes n}\otimes G$ by
$\sigma$, and its image by
$\sigma\Big{(}\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes G\Big{)}$. Then we have
the following commutative diagram with exact rows:

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\sigma\Big{(}\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes
G\Big{)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{G^{\otimes
n+1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda^{G}_{n+1}}$$\textstyle{\gamma_{n}(G)\otimes
G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[\;,\;]}$$\textstyle{1}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\gamma_{n+1}(G)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{Id}$$\textstyle{\gamma_{n+1}(G)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1,}$

which yields the following exact sequence:

$\sigma\Big{(}\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes
G\Big{)}\hookrightarrow\ker\Big{(}\lambda^{G}_{n+1}\Big{)}\twoheadrightarrow\ker\Big{(}[\;,\;]:\gamma_{n}(G)\otimes
G\to\gamma_{n+1}(G)\Big{)}.$

We will show that the first and the last terms in this exact sequence are
finitely generated. Since $\ker\Big{(}\lambda^{G}_{n}\Big{)}$ is an abelian
group and acts trivially on $G$, by [14, Proposition 3.2] we have:

$\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes
G=\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes_{G}I(G),$

where $I(G)$ denotes the augmentation ideal of $G$. Since $G$ is finitely
generated, $I(G)$ is a finitely generated $G$-module. By the induction
hypothesis we get that $\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes_{G}G$ is a
finitely generated group. Hence,
$\sigma\Big{(}\ker\Big{(}\lambda^{G}_{n}\Big{)}\otimes G\Big{)}$ is finitely
generated. Moreover, by Proposition 2.1, there is an exact sequence:

$\Gamma\big{(}\gamma_{n}(G)/\gamma_{n+1}(G)\big{)}\to\ker\Big{(}[\;,\;]:G\otimes\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}\to$
$\to\ker\Big{(}[\;,\;]:G\wedge\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}\to 1.$

Since $\Gamma\big{(}\gamma_{n}(G)/\gamma_{n+1}(G)\big{)}$ is finitely
generated, it suffices to show that
$\ker\Big{(}[\;,\;]:G\wedge\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}$ is finitely
generated. For the latter, we will use the following exact sequence (see [12,
Remark 3]):

$H_{3}\big{(}G/\gamma_{n}(G)\big{)}\to\ker\Big{(}[\;,\;]:G\wedge\gamma_{n}(G)\to\gamma_{n+1}(G)\Big{)}\to
H_{2}(G).$

We have already pointed out that $H_{2}(G)$ is finitely generated. Moreover,
since $G/\gamma_{n}(G)$ is polycyclic, by [3, Corollary 5.5]
$H_{3}\big{(}G/\gamma_{n}(G)\big{)}$ is finitely generated, which completes
the proof. ∎

We are now in a position to prove Theorem 1.1.

###### Proof of Theorem 1.1.

Recall that $G$ is finitely presented. We need to show that the $n$-th term of
the lower central series $\gamma_{n}(G)$ is finitely presented if and only if
$G^{\otimes n}$ is finitely presented.

The subgroup $\ker\Big{(}\lambda^{G}_{n}:G^{\otimes n}\to\gamma_{n}(G)\Big{)}$
is a central subgroup of $G^{\otimes n}$ and, by Lemma 2.2, it is finitely
presented. Consequently, the following extension

$1\to\ker\Big{(}\lambda^{G}_{n}:G^{\otimes n}\to\gamma_{n}(G)\Big{)}\to
G^{\otimes n}\to\gamma_{n}(G)\to 1,$

implies that the $n$-fold tensor product $G^{\otimes n}$ is finitely presented
if and only if $\gamma_{n}(G)$ is finitely presented. ∎

Let $G$ be a group and let $F$ be a free group such that $G=F/R$ for some
normal subgroup $R$ of $F$. The $n$-th nilpotent multiplier $M_{n}(G)$ is
defined by

$M_{n}(G)=\dfrac{R\cap\gamma_{n}(F)}{\gamma_{n}(R,F)},$

where $\gamma_{1}(R,F)=R$ and $\gamma_{k+1}(R,F)=[\gamma_{k}(R,F),F]$. In
particular, $M_{1}(G)\cong H_{2}(G)$ is the Schur multiplier of $G$.

According to Hall [21, 14.1.5] the Schur multiplier of a finitely presented
group $G$, $M_{1}(G)$, is finitely generated. We obtain the following related
result.

######  Corollary 2.3.

Let $G$ be a finitely presented group. Then the $n$-th nilpotent multiplier
$M_{n}(G)$ is finitely generated for all $n\geq 1$.

###### Proof.

If $n=1$, then $M_{1}(G)$ is finitely generated [21, 14.1.5]. Now, we can
assume $n\geq 2$. By [6], $M_{n}(G)$ is an epimorphic image of
$\ker\Big{(}\lambda^{G}_{n+1}:G^{\otimes n+1}\to\gamma_{n+1}(G)\Big{)}$. By
Lemma 2.2, $M_{n}(G)$ is (abelian) finitely generated. ∎

Let $\nu(G)$ be the group defined in [22] as

$\nu(G):=\langle G\cup G^{\varphi}\ |\
[g_{1},{g_{2}}^{\varphi}]^{g_{3}}=[{g_{1}}^{g_{3}},({g_{2}}^{g_{3}})^{\varphi}]=[g_{1},{g_{2}}^{\varphi}]^{{g_{3}}^{\varphi}},\;\
g_{i}\in G\rangle.$

The motivation for studying $\nu(G)$ is the commutator connection: indeed, the
map $\Phi:G\otimes G\rightarrow[G,G^{\varphi}]$, defined by $g\otimes
h\mapsto[g,h^{\varphi}]$, for all $g,h\in G$, is an isomorphism [22,
Proposition 2.6] (see also Ellis and Leonard [13])).

The following result is an immediate consequence of Lemma 2.2.

######  Corollary 2.4.

Let $G$ be a finitely presented group. Assume that the derived subgroup
$G^{\prime}$ is finitely presented. Then $\nu(G)$ and $\nu(G)^{\prime}$ are
finitely presented.

###### Proof.

By [23], there are short exact sequences:

$1\to\ker(\lambda_{2}^{G})\to\nu(G)^{\prime}\to G^{\prime}\times
G^{\prime}\times G^{\prime}\to 1$

and

$1\to G\otimes G\to\nu(G)\to G\times G\to 1.$

Applying Lemma 2.2 and Theorem 1.1 with $n=2$, we obtain that
$\ker(\lambda_{2}^{G})$ and $G\otimes G$ are finitely presented. Consequently,
$\nu(G)^{\prime}$ and $\nu(G)$ are finitely presented. ∎

######  Remark 2.5.

It is worthy to mention that part of the previous result is already known.
More precisely, Kochloukova and Sidki proved that $G$ is finitely presented if
and only if $\nu(G)$ is finitely presented [15, Theorem E].

Now we will deal with Theorem 1.2: Let $G$ be a finitely generated.

  1. (1)

The $n$-fold tensor product $G^{\otimes n}$ is finite if and only if $G$ is
finite.

  2. (2)

The $n$-fold tensor product $G^{\otimes n}$ is polycyclic if and only if $G$
is polycyclic.

###### Proof of Theorem 1.2.

First we consider the item (1). Assume that $G$ is finite. Combining [11] and
[4, Proposition 5], we deduce that $G^{\otimes n}$ is finite.

Conversely, assume that $G^{\otimes n}$ is finite. First we prove that
$G^{ab}$ is finite. As $G$ is finitely generated, we deduce that $G^{ab}$ is
finitely generated and $G^{ab}\cong T\times F,$ where $T$ is the torsion part
and $F$ the free part of $G^{ab}$. In particular, $T$ is finite. There exists
an epimorphism $G^{\otimes n}\to(G^{ab})^{\otimes n}$. Moreover, by [5],
$(G^{ab})^{\otimes n}\cong(G^{ab})^{\otimes_{\mathbb{Z}}n}$, where
“$\otimes_{\mathbb{Z}}$” denotes the usual tensor product of
$\mathbb{Z}$-modules. Now, if $F$ is infinite, then so is
$(G^{ab})^{\otimes_{\mathbb{Z}}n}$, which implies that $G^{\otimes n}$ is
infinite too, a contradiction.

Now, we need to show that the derived subgroup $G^{\prime}$ is finite. Since
$\lambda_{n}^{G}\colon G^{\otimes n}\to\gamma_{n}(G)$ is an epimorphism, we
deduce that $\gamma_{n}(G)$ is finite. Consequently, it suffices to prove that
if $\gamma_{k}(G)$ is finite, then so is $\gamma_{k-1}(G)$, where $k$ is a
positive integer with $n\leq k<2$. To prove that $\gamma_{k}(G)$ is finite is
enough to show that $\gamma_{k-1}(G)/\gamma_{k}(G)$ is finite. Since
$\gamma_{k}(G)/\gamma_{k+1}(G)$ is a finitely generated abelian group, is
sufficient to show that

$\displaystyle[g_{1},g_{2},\ldots,g_{k-1}^{m}]\gamma_{k}(G)$ $\displaystyle=$
$\displaystyle[g_{1},g_{2},\ldots,g_{k-1}]^{m}\gamma_{k}(G),$

where $m$ is a positive integer and $g_{1},g_{2},\ldots g_{k-1}\in G$. To this
end, we proceed by induction on $m$. The formula is obvious if $m=1$. Assume
the formula is valid up to $m-1$; we will prove it for $m$.

$\displaystyle[g_{1},\ldots,g_{k-1}^{m}]$ $\displaystyle=$
$\displaystyle[g_{1},\ldots,g_{k-1}][g_{1},\ldots,g_{k-1}^{m-1}]^{g_{k-1}}$
$\displaystyle=$
$\displaystyle[g_{1},\ldots,g_{k-1}][g_{1},\ldots,g_{k-1}^{m-1}][g_{1},\ldots,g_{k-1}^{m-1},g_{k-1}]$
$\displaystyle\equiv$
$\displaystyle[g_{1},\ldots,g_{k-1}]^{m}\mod\gamma_{k}(G)$

Let $|G^{ab}|=m$, then any $m$ power of an element of $G$ is an element of
$G^{\prime}$, so we have that the commutator
$[g_{1},\ldots,g_{k-1}]\gamma_{k}(G)$ has order dividing $m$. We conclude that
$G^{\prime}$ is finite, which completes the proof.

Now we deal with item (2). Assume that $G$ is polycyclic. According to
Moravec’s theorem [18], we deduce that the $n$-fold tensor product $G^{\otimes
n}$ is polycyclic.

Conversely, assume that $G^{\otimes n}$ is polycyclic. Therefore,
$\gamma_{n}(G)$ is polycyclic. Since polycyclic is a class closed to
extension, it suffices to prove that $G/\gamma_{n}(G)$ is polycyclic. Note
that $G/\gamma_{n}(G)$ is nilpotent finitely generated, in particular,
polycyclic. ∎

######  Remark 2.6.

It is worthy to mention that the case $n=2$ in Theorem 1.2 (1) was considered
in [20, Theorem 3.1].

##  3\. On the non-abelian tensor product of finitely presented group

In this section, we consider the influence of specific derivative subgroup in
the structure of the non-abelian tensor product. This approach is mainly
motivated by the following works: Brown, Johnson and Robertson [4, Section 8],
Nakaoka [19], Visscher [25] and Donadze, Ladra and Thomas [9, Section 3].

###### Proof of Theorem 1.3.

Recall that $G$ and $H$ are finitely generated groups acting compatibly on
each other, and the derivative $[G,H]$ is finitely presented. We need to prove
that the non-abelian tensor product $G\otimes H$ is finitely presented.

By [5, Propostion 2.3 (b) and (d)], the non-abelian tensor product $G\otimes
H$ is a central extension of $\ker(\lambda)$ by $[G,H]$, where $\lambda\colon
G\otimes H\to[G,H]$, $g\otimes h\mapsto g^{-1}g^{h}$, is an epimorphism.
According to [9, Proposition 5.1], we deduce that $G\otimes H$ is finitely
generated. Thus, it suffices to prove that $\ker(\lambda)$ is finitely
generated.

As $G\otimes H$ is finitely generated, we have an epimorphism $p\colon F\to
G\otimes H$, where $F$ is a free group of finite ranking. Define
$\lambda^{\prime}\colon F\to[G,H]$ as the composition $\lambda\circ p$. Then,
from the following commutative diagram:

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\ker(\lambda^{\prime})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p}$$\scriptstyle{\lambda^{\prime}}$$\textstyle{[G,H]\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{Id}_{[G,H]}}$$\textstyle{1}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\ker(\lambda)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{G\otimes
H\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda}$$\textstyle{[G,H]\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1,}$

we get an epimorphism $\ker(\lambda^{\prime})\to\ker(\lambda)$ induced by
$p\colon F\to G\otimes H$. Moreover, as $\ker(\lambda)\leq Z(G\otimes H)$, we
have an epimorphism

$\dfrac{ker(\lambda^{\prime})}{[ker(\lambda^{\prime}),F]}\to\dfrac{\ker(\lambda)}{[ker(\lambda),G\otimes
H]}=\ker(\lambda).$

Set $K=\ker(\lambda^{\prime})$. Now, it remains to show that $K/(K\cap
F^{\prime})$ and $(K\cap F^{\prime})/([K,F])$ are finitely generated. Consider
the following lattice of subgroups:

$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{KF^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{K\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{F^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{K\cap
F^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{[K,F]}$

Note that $K/(K\cap F^{\prime})$ is isomorphic to a subgroup of the
abelianization $F^{ab}$ and so, finitely generated. Moreover, by [21,
11.4.15], $(K\cap F^{\prime})/([K,F])$ is isomorphic to the Schur multiplier
$M(F/K)=M([G,H])$. According to Hall’s theorem, the Schur multiplier
$M([G,H])$ is finitely generated [21, 14.1.5]. Consequently, $\ker(\lambda)$
is finitely presented, the proof is complete. ∎

######  Remark 3.1.

It is well-known that the finite presentability of the groups $G$ and $H$ does
not imply the finite presentability of the non-abelian tensor product
$G\otimes H$. For instance, by [4, Proposition 6], if $F$ is a free group of
rank $n\geq 2$, then the non-abelian tensor square $F\otimes F\cong
F^{\prime}\times\mathbb{Z}^{\frac{n(n+1)}{2}},$ where $F^{\prime}$ is a free
group of countably infinite rank.

######  Theorem 3.2.

Let $G$ and $H$ be groups acting compatibly on each other. Assume that $G$ is
finite and $H$ finitely generated. Then the non-abelian tensor product
$G\otimes H$ is finitely presented. Moreover, every subgroup of $G\otimes H$
is finitely presented.

###### Proof.

By Theorem 1.3, the non-abelian tensor product $G\otimes H$ is finitely
presented. Now, we will show that every subgroup of $G\otimes H$ is finitely
presented. Indeed, consider the following exact sequence:

$1\to\ker(\lambda)\to G\otimes H\to[G,H]\to 1,$

where $[G,H]\leq G$ is the derivative of $G$ under the action of $H$. As
$G\otimes H$ is finitely generated, $\ker(\lambda)\leq Z(G\otimes H)$ and the
index $[G\otimes H:\ker(\lambda)]\leq|[G,H]|<\infty$, we have the kernel
$\ker(\lambda)$ is finitely generated. Therefore $G\otimes H$ is polycyclic-
by-finite and the result follows. ∎

##  4\. Schur-Baer type theorem for finitely presented groups

In this section, we will use the approach of [8] and [10] to prove a Schur-
Baer type theorem for finitely presented groups.

Recall that the group class $\mathfrak{X}$ is called a Schur class if for any
group $G$ such that the factor $G/Z(G)$ belongs to $\mathfrak{X}$, also the
derived subgroup $G^{\prime}$ of $G$ belongs to $\mathfrak{X}$. Thus the
famous Schur’s theorem just states that finite groups form a Schur class [21,
10.1.4]. Schur’s theorem admits a generalization to higher terms of the lower
central series. More precisely, if $G/Z_{i}(G)$ is finite, then
$\gamma_{i+1}(G)$ is finite (Baer, [21, 14.5.1]). In particular, the case
$i=1$ is, exactly, Schur’s theorem. For more details see [21] and the
references given there.

Recall that an exact sequence of groups

$1\to N\to H\to G\to 1$

is called $n$-central if $N\leq Z_{n}(H)$. The next lemma is taken from [10].

######  Lemma 4.1.

Let $1\to N\to H\to G\to 1$ be a $n$-central extension for a fixed positive
integer $n$. Then, there exists an epimorphism $\tau\colon G^{\otimes
n+1}\to\gamma_{n+1}(H)$ making the following diagram commutative

---
$\textstyle{G^{\otimes
n+1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{Id}$$\scriptstyle{\tau}$$\textstyle{G^{\otimes
n+1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda^{G}_{n+1}}$$\textstyle{\gamma_{n+1}(H)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\gamma_{n+1}(G)}$

######  Theorem 4.2.

Let $G$ be a finitely presented group and $n\geq 1$. Then, the following are
equivalent:

(i) $\gamma_{n+1}(G)$ is finitely presented,

(ii) for arbitrary $n$-central extension of groups $1\to N\to H\to G\to 1$,
$\gamma_{n+1}(H)$ is finitely presented.

###### Proof.

Let $H$ be as in the theorem. By Lemma 4.1 there exists an epimorphism
$\tau:G^{\otimes n+1}\to\gamma_{n+1}(H)$ such that the following diagram
commutes:

---
$\textstyle{G^{\otimes
n+1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{Id}$$\scriptstyle{\tau}$$\textstyle{G^{\otimes
n+1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda^{G}_{n+1}}$$\textstyle{\gamma_{n+1}(H)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\gamma_{n+1}(G)}$

From this diagram we get an epimorphism:

$\ker\Big{(}\lambda^{G}_{n+1}:G^{\otimes
n+1}\to\gamma_{n+1}(G)\Big{)}\to\ker\Big{(}\gamma_{n+1}(H)\to\gamma_{n+1}(G)\Big{)}.$

Since $\ker\Big{(}\lambda^{G}_{n+1}\Big{)}$ is an abelian group, we get that
$\ker\Big{(}\gamma_{n+1}(H)\to\gamma_{n+1}(G)\Big{)}$ is finitely presented by
Lemma 2.2. Consequently, the extension of groups

$1\to\ker\Big{(}\gamma_{n+1}(H)\to\gamma_{n+1}(G)\Big{)}\to\gamma_{n+1}(H)\to\gamma_{n+1}(G)\to
1$

implies that $\gamma_{n+1}(H)$ is finitely presented if and only if
$\gamma_{n+1}(G)$ is finitely presented. ∎

######  Proposition 4.3.

Let $\mathfrak{X}$ be one of the following classes of groups:

  1. (i)

the class of perfect finitely presented groups;

  2. (ii)

the class of nilpotent finitely presented groups;

  3. (iii)

the class of finitely presented groups in which every subgroup is finitely
presented.

Let $G\in\mathfrak{X}$. Then, for each $n$-central extension of groups $1\to
N\to H\to G\to 1$, $n\geq 1$, we have $\gamma_{n+1}(H)\in\mathfrak{X}$.

###### Proof.

We denote by $\tau:G^{\otimes n+1}\to\gamma_{n+1}(H)$ the first vertical
homomorphism in the diagram given in Lemma 4.1.

(i): Since $\gamma_{n+1}(G)=G$, by Theorem 4.2 $\gamma_{n+1}(H)$ is finitely
presented. On the other hand, given two groups $M$ and $N$ acting on each
other compatibly, we have the following relation (see [5, Proposition 2.3]):

$[m\otimes n,m^{\prime}\otimes
n^{\prime}]=(m^{n}m^{-1})\otimes(^{m^{\prime}}n^{\prime}n^{\prime-1}),$

for each $m,m^{\prime}\in M$ and $n,n^{\prime}\in N$. This implies that
$G^{\otimes n+1}$ is a perfect group, because $G$ is perfect. Since
$\gamma_{n+1}(H)=Im(\tau)$, we get that $\gamma_{n+1}(H)\in\mathfrak{X}$.

(ii): By [25, Theorem 3.4 (i)], the $n$-fold tensor product $G^{\otimes n+1}$
is nilpotent. Hence, $\gamma_{n+1}(H)$ is nilpotent. Moreover, since $G$ is
finitely presented and nilpotent, $\gamma_{k}(G)$ will be finitely presented
for all $k\geq 1$. Thus, by Theorem 4.2 $\gamma_{n+1}(H)$ is a finitely
presented group.

(iii): Let $H_{1}$ be a subgroup of $\gamma_{n+1}(H)$. We have to show that
$H_{1}$ is finitely presented. Let $\delta:H\to G$ denote the epimorphism
given in the proposition. Since $\delta(H_{1})$ is a subgroup of $G$, it is a
finitely presented group. Therefore, it suffices to show that
$\ker\Big{(}\delta|_{H_{1}}:H_{1}\to\delta(H_{1})\Big{)}$ is finitely
presented. We have the following commutative diagram:

---
$\textstyle{\tau^{-1}(H_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda^{G}_{n+1}|_{\tau^{-1}(H_{1})}}$$\scriptstyle{\tau|_{\tau^{-1}(H_{1})}}$$\textstyle{\delta(H_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{Id}$$\textstyle{H_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta|_{H_{1}}}$$\textstyle{\delta(H_{1})}$

This implies an epimorphism
$\ker\Big{(}\lambda^{G}_{n+1}|_{\tau^{-1}(H_{1})}\Big{)}\to\ker\Big{(}\delta|_{H_{1}}\Big{)}$.
Since
$\ker\Big{(}\lambda^{G}_{n+1}|_{\tau^{-1}(H_{1})}\Big{)}\subseteq\ker\Big{(}\lambda^{G}_{n+1}\Big{)}$,
by Lemma 2.2 $\ker\Big{(}\lambda^{G}_{n+1}|_{\tau^{-1}(H_{1})}\Big{)}$ is a
finitely generated abelian group. Hence, $\ker\Big{(}\delta|_{H_{1}}\Big{)}$
is finitely presented. We are done with the proof. ∎

######  Remark 4.4.

Let $\mathfrak{X}$ be as in Proposition 4.3. Then $\mathfrak{X}$ is a Schur
class.

######  Corollary 4.5.

Let $\mathfrak{X}$ be a class of groups defined by

$\mathfrak{X}=\\{G\>|\>G\>\text{is nilpotent-by-finite and finitely
presented}\\}.$

  1. (1)

For arbitrary two groups $G,H\in\mathfrak{X}$ acting on each other compatibly,
we have $G\otimes H\in\mathfrak{X}$.

  2. (2)

Then $\mathfrak{X}$ is a Schur class.

###### Proof.

(1) By [9, Corollary 3.6 (ii)], the non-abelian tensor product of two
nilpotent-by-finite groups is nilpotent-by-finite. Now, it suffices to show
that $G\otimes H$ is finitely presented for each $G,H\in\mathfrak{X}$. Since
$G$ is finitely generated nilpotent-by-finite, it follows that $G$ and $[G,H]$
are polycyclic-by-finite and so, finitely presented. By Theorem 1.3, the non-
abelian tensor product $G\otimes H$ is finitely presented.

(2) This follows from Lemma 4.1, Theorem 4.2. ∎

## Acknowledgements

The authors are very grateful to Guram Donadze and Noraí Rocco for the
interesting discussions and suggestions on the best approach to these results.
The work of the first was supported by FAPDF and CNPq–Brazil. The second
author was supported by CAPES–Brazil.

## Data availability

NA

## References

  * [1] R. Bastos, I. N. Nakaoka and N. R. Rocco, Finiteness conditions for the non-abelian tensor product of groups, Monatsh. Math. 187 (2018) pp. 603–615.
  * [2] R. Bastos, I. N. Nakaoka and N. R. Rocco, Finiteness conditions for the box-tensor product of groups and related constructions, J. Algebra 587 (2021) pp. 594–612.
  * [3] G. Baumslag, F. B. Cannonito, and C. F. Miller III, Computable algebra and group embeddings, J. Algebra, 69 (1981) pp. 186–212.
  * [4] R. Brown, D. L. Johnson and E. F. Robertson, Some computations of non-abelian tensor products of groups, J. Algebra, 111 (1987) pp. 177–202.
  * [5] R. Brown, and J.-L. Loday, Van Kampen theorems for diagrams of spaces, Topology, 26 (1987) pp. 311–335, with an appendix by M. Zisman.
  * [6] J. Burns and G. Ellis, Inequalities for Baer invariants of finite groups, Canad. Math. Bull., 41 (4) (1998) pp. 385–391.
  * [7] R. K. Dennis, In search of new “homology” functors having a close relationship to $K$-theory, Preprint, Cornell University, Ithaca, NY, 1976.
  * [8] G. Donadze, M. Ladra and P. Paez-Guillan, Schur’s theorem and its relation to the closure properties of the non-abelian tensor product, Proc. R. Soc. Edinb. A: Math, 150 (2020) pp. 993–1002.
  * [9] G. Donadze, M. Ladra and V. Thomas, On some closure properties of the non-abelian tensor product, J. Algebra 472 (2017) pp. 399–413.
  * [10] G. Donadze and X. Garcia-Martinez, Some generalisations of Schur’ and Baer’s theorem and their connection with homological algebra, Math. Nachr., 294 (11) (2021) pp. 2029–2039.
  * [11] G. Ellis, The non-abelian tensor product of finite groups is finite, J. Algebra, 111 (1987), pp. 203–205.
  * [12] G. J. Ellis. Non-Abelian exterior products of groups and exact sequences in the homology of groups, Glasgow Math. J. 29 (1987) pp. 13–19.
  * [13] G. Ellis and F. Leonard, Computing Schur multipliers and tensor products of finite groups, Proc. Royal Irish Acad., 95A (1995) pp. 137–147.
  * [14] D. Guin, Cohomologie et homologie non abeliennes des groupes, J. Pure Appl. Algebra 50 (2) (1988) pp. 109–137.
  * [15] D. Kochloukova and S. Sidki, On weak commutativity in groups, J. Algebra, 471 (2017) pp. 319–347.
  * [16] A. S.-T. Lue, The Ganea Map for Nilpotent Groups, J. London Math. Soc., s2-14 (1976) pp. 309–312.
  * [17] C. Miller, The second homology group of a group: relations among commutators, Proc. Am. Math. Soc., 3 (1952) pp. 588–595.
  * [18] P. Moravec, The non-abelian tensor product of polycylclic groups is polycyclic, J. Group Theory 10 (2007) pp. 795–798.
  * [19] I. N. Nakaoka, Non-abelian tensor products of solvable groups, J. Group Theory 3 (2000) pp. 157–167.
  * [20] M. Parvizi and P. Niroomand, On the structure of groups whose exterior or tensor square is a $p$-group, J. Algebra, 352 (2012) pp. 347–353.
  * [21] D. J. S. Robinson, A course in the theory of groups, 2nd edition, Springer-Verlag, New York, 1996.
  * [22] N. R. Rocco, On a construction related to the non-abelian tensor square of a group, Bol. Soc. Brasil Mat., 22 (1991) pp. 63–79.
  * [23] N. R. Rocco, A presentation for a crossed embedding of finite solvable groups, Comm. Algebra, 22 (1994) pp. 1975–1998.
  * [24] V. Z. Thomas, The non-abelian tensor product of finite groups is finite: a Homology-free proof, Glasgow Math. J. 52 (2010) pp. 473–477.
  * [25] M. P. Visscher, On the nilpotency class and solvability length of non-abelian tensor products of groups, Arch. Math. (Basel) 73 (3) (1999) pp. 161–171.
  * [26] J. H. C. Whitehead, A certain exact sequence, Ann. of Math., 52 (1950) pp. 51–110.


# Generating Bayesian Network Models from Data Using Tsetlin Machines

Christian Blakely Author’s status: Any statements, ideas, and/or opinions
expressed in this paper are strictly those of the author and do not
necessarily reflect those of PwC Switzerland Machine Learning and AI
PwC Switzerland
Zurich, Switzerland
<EMAIL_ADDRESS>
###### Abstract

Bayesian networks (BNs) are directed acyclic graphical (DAG) models that have
been adopted into many fields for their strengths in transparency,
interpretability, probabilistic reasoning, and causal modeling. Given a set of
data, one hurdle towards using BNs is in building the network graph from the
data that properly handles dependencies, whether correlated or causal. In this
paper, we propose an initial methodology for discovering network structures
using Tsetlin Machines (TMs).

###### Index Terms:

Tsetlin Machines, Bayesian Networks, Interpretability

##  I Introduction

A Bayesian network (BN) is a directed acyclic graph (DAG) where nodes of the
graph are random variables while the directed edges represent dependent
relationships in the form of probability dependencies among the variables. The
entire graph thus represents a compact representation of a joint probability
distribution over the set of random variables, where each node and its parents
are associated with a conditional probability distribution (CPD). Reasons for
adopting Bayesian network models over other machine learning models such as
random forests, gradient-boost models, or neural networks usually aim towards
1) Interpretability 2) Uncertainty Quantification 3) Small Data Requirements,
and 4) efficient computational complexity. Furthermore, since the entire joint
probability distribution is described completely by the network, generating
new data from the network is also a common application.

One challenge of modeling with BNs is in constructing this DAG that accurately
and robustly characterizes the underlying relationships in data Scutari
(2010). Learning a BN is typically conducted in two phases, whereby the first
phase constructs the topology (network structure) of the network and the
second phase estimates the parameters of the CPDs given the fixed structure.
As parameter estimation is considered a well-studied problem, especially with
the availability of data, learning the structure is more challenging. A long
literature study of BN structure learning includes usually two different types
of algorithms: 1) constraint-based which look for conditional independencies
(CIs)in the data and build the DAG consistent to these CIs and 2) score-based
which convert the problem to an optimization problem, where a score is used to
measure the fitness of a DAG to the observed data with a search strategy
employed to maximize the score over the space of possible DAGs (see e.g.
Scutari (2015) for more on constraint-based algorithms, and Kasza and Solomon
(2011) for more on score-based approaches). No matter the methodology or
combination of methodologies employed, finding an optimal structure has been
shown to be NP-hard. In light of this, we will focus on the problem of
generating network structures for the data, as defining CPDs with the use of
data is a much easier problem once conditional dependencies have been defined.

###  I-A Motivation and contributions

In the past few years, there has been a new genre of building supervised
machine learning models called Tsetlin machines. First introduced by O.C.
Granmo in Granmo (2018), Tsetlin machines have been gaining attraction in some
machine learning communities for their many computational and modeling
benefits. Mostly notably, TMs capture patterns in data using conjunctive
clauses in propositional logic and are thus intrinsically interpretable
learning systems, and they are also typically fast to train, benefiting from
parallelization and many recent regularization advancements in training
algorithms such as in Abeyrathna et al. (2021), Sharma et al. (2021), even
without the use of GPUs.

But the most useful benefit of Tsetlin machines for this study presented in
this paper is the ease in which global importance features can be extracted
from the propositional logic of an underlying learned Tsetlin machine on data.
In Blakely and Granmo (2021) a simple method for extracting global importance
features was introduced and compared with popular approaches such as SHAP for
gradient boost models showing comparable results without the need of a post-
hoc approach. We take advantage of this powerful approach to derive a fairly
straightforward method for constructing Bayesian network topologies of data.

The motivations of learning Bayesian Network structures from data using TMs is
multifold:

  * •

Bayesian Networks can offer a compact visual overview of data dependencies

  * •

Through a very powerful reinforcement learning mechanism, TMs can often learn
literal structure already with small data

  * •

Contributes to the validation and verification of TMs in building predictive
models

  * •

Provides a way of building hybrid predictive models

We will touch on all these points throughout this paper, with an exposition of
the approach using both algorithms and examples. The main contribution of this
paper is to demonstrate that TM models can provide an alternative approach to
building and investigating Bayesian network structures, or at minimum provide
additional computational medium for a hybrid-type approach using other
classical resources.

###  I-B Paper structure

The paper will be organized as follows. We first review Tsetlin Machines with
a focus on constructing interpretable features of the data from the resulting
propositional logic expressions that are learned in training. We then provide
a simple algorithm for constructing a Bayesian Network given (unlabeled) data
using a modified version of the standard TM learning algorithm. To explore
validation of the method, we will propose an approach where we first sample
from a known Bayesian network and then apply the algorithm to the sampled data
to build a network and verify how similar the networks are. We then proceed to
a larger statistical approach to understand how well our approach does in
generating networks that are close to the ground truth. To understand the
proximity to the ground truth network, we apply a kernel graph based approach
to compare a TM generated network with the proposed network from which the
underlying data was simulated. We do this on varying number of node size
networks, and also on varying the models used in generating the networks.

Finally, in the last sections, we apply our approach to two real-world data
sets, namely a Supply Chain data set and a Bank Customer Churn data set from
an anonymous bank. The motivation here is to understand how well our method
does in building partial dependencies on certain features in the data which
are well known in other models for such types of industrial data sets.
Furthermore, in the Supply Chain dataset, only 100 samples are available, with
over 20 features, making it very challenging for traditional machine learning
predictive models such as neural networks and gradient boost approach which
typically require lots of data.

##  II Tsetlin Machine Architecture

In this paper we employ a recently developed architecture for TM learning
originally proposed in Glimsdal and Granmo (2021). The architecture shares an
entire pool of clauses between all output classes, while introducing a system
of weights for each class type. The learning of weights is based on increasing
the weight of clauses that receive a Type Ia feedback (due to true positive
output) and decreasing the weight of clauses that receive a Type II feedback
(due to false positive output). This architectural design allows to determine
which clauses are inaccurate and thus must team up to obtain high accuracy as
a team (low weight clauses), and which clauses are sufficiently accurate to
operate more independently (high weight clauses). The weight updating
procedure is given in more detail in Appendix References. Here we illustrate
the overall scheme in Figure 1. Notice that each clause in the shared pool is
related to each output by using a weight dependant on the output class and the
clause. The weights that are learned during the TM learning steps and are
multiplied by the output of the clause for a given input. Thus clause outputs
are related to a set of weights for each output class (in this case three
classes). One of the clauses also contains four literals, the pattern learned
for that clause.

Figure 1: Showing a collection of clauses and their relationship with weights
that are learned during TM training. Each clause contains a set of literals
that are also learned during feedback.

In our methodology for building candidate networks, both the frequency of
literals across the various clauses and the weights will play an important
role in determining the global feature strength in learning data outputs,
which we give a brief overview of next.

##  III Global Interpretability

In this section we give a brief overview of the expressions for global
interpretability in TMs that have been modified from Blakely and Granmo
(2021). In this paper, global strength indicators for each feature were
derived based on output class prediction. This required constructing the
strength based on the polarity of the clause as we wanted to understand
strength of a feature dependent on an output of a class.

We represent a set of $d_{f}$ literals for the $i$-th feature $f_{i}$ as
$S_{f_{i}}=(l_{1},l_{2},\ldots,l_{d_{f}})$. and map all the literals from all
the features of the data into one macro set of literals which we will denote
as $F_{L}=\cup_{i}S_{f_{i}}$. Thus the set of literals $I^{n}_{c}$ learned
from any TM learning process for class output $n$ and clause $c$ is a subset
of $F_{L}$. To formulate our global feature importance expressions, associated
with each clause $c$ is an integer weight $w_{n}[c]$. These weights will be
used to express the most salient features in predicting an output for a
feature $f_{i}$.

$y^{i}\in\\{y^{1},y^{2},\ldots,y^{n}\\}$, $y^{i}=\\{0,1\\}$ and the upper
index $i$, which refers to a particular output variable. For simplicity in
exposition, we assume that the corresponding literal index sets
$I^{i}_{j},\bar{I}^{i}_{j}$, for each output variable, $i=1,\ldots,n$, and
clause, $j=1,\ldots,m$, have been found under some performance criteria of the
learning procedure, described in Section References. With these sets fixed, we
can now assemble the closed form expressions.

We denote by $I^{n}_{c}$ the set of literals (combined with negated literals)
learned from the TM for class output $n$ and clause $c$. Associated with each
clause $c$ is an integer weight $w_{n}[c]$, for all clauses $c=1,\ldots,C$.
Specifically, we compute feature strength for a given output variable and
$k$th bit of feature $f_{u}$ as follows:

$g[f_{i}]\leftarrow\sum_{n}\sum_{c}|w^{n}[c]|_{l_{k}\in S_{f_{i}}|l_{k}\in
I^{n}_{c}}$ (1)

For any feature $f_{i}$, this expression sums up the absolute value of the
weights $w^{n}[c]$ over all class outputs $1\leq n\leq N$ and all clauses
$c\in C$ such that the literals belong to both the feature’s set of literals
$S_{f_{i}}$ and the clause $c\in C$. Once computed for all features $f_{i}$ of
the data, trained on an output variable $y$, we can assess the most important
features in any prediction of a collection of input variables by ranking the
values of each $g[f_{i}]$. In other words, for any given feature, the
frequency of its set of literals inclusion across all clauses multiplied by
the weight of that clause for the output class polarity governed by the
governs its global importance score. This score thus reflects how often the
feature is part of a pattern that is important to making a certain class
prediction. Notice that we are interested in indices pertaining any polarity
(and thus weight) of the clauses $C^{n}_{c}(X)$ since these are the clauses
that contain references to features that are beneficial for predicting
$R_{n}$.

Figure 2 shows a graphical representation of how the feature strengths are
compiled after a TM training round. We look in each clause and count how many
literals from the different features exist and place them in a map,
incrementing by the absolute value of the weight for that clause. This way,
the highest valued strengths feature the most amount of literals spread out
over as many clauses. The weights matter because they are summed across the
frequencies of literals. A very small weight compared to the others will
contribute very little (as that clause made little contribution to a
prediction). More relevant clauses (and thus literals), will be more
represented with the larger weights.

Figure 2: Assembling global feature strengths from contributing features in
clauses

This gives us quick access to feature strength in absolute terms without
regard to any output prediction class, which, as we’ll see is relevant for
when finding possible parent or child nodes in the Bayesian network candidate
structures.

With the feature strength indicator defined, our next step is to introduce an
approach to building a candidate Bayesian network structure from data.

##  IV Method

Formally, a Bayesian network is a pair $B=(G,P)$, where $G$ is a DAG that
encodes a joint probability distribution $P$ over a vector of random variables
$\mathbf{F}=(f_{1},\ldots,f_{M})$ with each node $n_{i}$ of the graph
representing a variable in $\mathbf{F}$. The DAG can be represented as a
vector $G=(P_{n_{1}},\ldots,P_{n_{M}})$ where each $P_{n_{i}}$ is a subset of
the index set $V=\\{1,\ldots,M\\}$ and specifies the parents of node $n_{i}$
in the graph.

There are typically three types of nodes (features) $n_{i}$ in a Bayesian
network which we will need to identify a priori in our network generating
algorithm

  * •

Parameters: These are the predictors for which we’d like to build the model.
They have no dependencies, thus no children, and are often parameters such as
age, gender/sex, Location/Geography, time/day, etc.

  * •

Observed features: These are features which are observed and could have
conditional dependencies, or be dependencies for other nodes.

  * •

Unobserved features: These are features which are not directly observed and
are being inferred from evidence or predicted. They could have conditional
dependencies, or be dependencies for other nodes. These are typically labels
or also could be latent variables.

We now turn to the application of constructing Bayesian Network
representations of data from the global features derived from weighted TMs.
The approach is essentially a search problem that consists of two parts:
scoring the top features for each targeted feature in the data using TM
learning, and then a search algorithm that creates parent to child
relationships based on most salient features found from the TMs.

We assume a data set $\mathbf{X}$ comprised of a set of $M$ features
$\mathbf{F}={f_{1},\ldots,f_{M}}$. Each feature $f_{i}$ we also assume can be
represented by $d_{f_{i}}$ literals. For example, a feature with values low,
medium, high would be represented by three literals $(l_{1},l_{2},l_{3})$ with
each $l_{k}\in(0,1)$. Low would be $(1,0,0)$, medium $(1,1,0)$, and high
$(1,1,1)$. Starting with $f_{1}$, the goal is to traverse all variables of the
data, where each variable is independently treated as an output variable of an
independent TM model. For each variable, we learn which top $K$ features
$f_{j},f_{j+1},\ldots,f_{j+K}\in\mathbf{F}$ have the most impact in predicting
the variable as an output for a model. These top $K$ features are then
proposed as candidate parent or child nodes of the targeted output variable.

To do this we apply $R$ rounds of learning for each variable $f_{i}$ as an
output target, and apply the global feature strength indicator 1 to all other
features of the data set $X$. After each round, we aggregate all the feature
strengths together and propose the top $K$ features as parent nodes of
$f_{i}$.

It is important to note that in learning a variable $f_{i}$, a balanced set of
training data $X_{I}\subset X$ with regard to the output values of $f_{i}$ is
helpful to ensure a fair assessment and reinforcement of literals for each
feature.

The construction of the Bayesian network candidate is done in three simple
steps. The first step is to compute the most relevant features for all the the
parameters, observed, and unobserved features in the the data. Algorithm 1
demonstrates the first step in achieving a straightforward approach to compute
a list of most relevant features for each type of variable $f_{i}$. Algorithm
2 will then apply the second step of the approach to each feature and relevant
feature mapping.

Algorithm 1 Learning the most salient global features for each variable

1:Input $X$, $N$, $\epsilon$

2:Initialize an empty map $S_{i}:f\rightarrow\mathbb{Z}^{+}$ for each
$f_{i}\in\mathbf{F}$

3:for each variable $f_{i}\in\mathbf{F}$ do

4: Sample training set w.r.t outputs values of $f_{i}$

5: Learn $N$ rounds of $\epsilon>0$ epochs

6: for each round in $N$ do

7: Extract the top $K$ features and add to the map $S_{i}$

8: end for

9:end for

10:return $S_{i}$

Algorithm 1 begins by initializing a map for each variable $f_{i}$ that will
be used to store the aggregation of the feature strengths $g[f_{\cdot}]$ when
applying a learning round of a TM model. Next, we traverse all the variables
of the data set $X$, in no particular order, whereby fixing each variable
$f_{i}$ as an output variable when applying the TM learning rounds. Each
possible value of the the variable $f_{i}$ is thus treated as an output class
$y=(y_{1},y_{2},\ldots,y_{d_{f}})$ where $d_{f}$ we recall is the dimension of
the literal set $S_{f_{i}}$. In learning the output class given an in-sample
training set of $X$, we essentially learn which features were most salient
when making a prediction for all output classes combined. The top $K$ features
strengths $g[f_{i}]$ are added to the map as $S_{i}:=S_{i}+g[f_{i}]$. After
$M$ rounds of learning, we sort the aggregate feature strengths by rank of
highest to lowest. These ranked features are candidates for parent nodes of
$f_{j}$. To this end, we add the top $P$ features to a node list for feature
$f_{j}$. This is represented in Figure 3, where we see that for a feature node
(output) $A$, there are three features that provide high relevance $f_{x}$,
$f_{y}$, $f_{z}$, and after three independent rounds of training, $f_{x}$ has
the largest aggregate strength. We the propose the feature $f_{x}$ as a parent
node for $A$.

Figure 3: Assembling the feature strengths for node (output) $A$. Most
relevant feature $f_{x}$ from the strength map then proposed as parent node
for $A$

The output of Algorithm 1 is a map from each features $f_{i}$ to a list of the
top $K$ features. For each feature, sorted by strength, the map will look like
the table in I, with $K=3$.

TABLE I: Top three features derived from each node Node | TopFeature 1 | TopFeature 2 | TopFeature 3
---|---|---|---
$f_{1}$ | $f_{x}$ | $f_{y}$ | $f_{z}$
$f_{2}$ | $f_{x_{2}}$ | $f_{y_{2}}$ | $f_{z_{2}}$
$\dotsc$ | $\dotsc$ | $\dotsc$ | $\dotsc$
$f_{M}$ | $f_{x_{M}}$ | $f_{y_{M}}$ | $f_{z_{M}}$

Before we introduce Algorithm 2, we define the notion of lower strength
direction. For an edge between two nodes $n_{i}$ and $n_{j}$ respective of
features $f_{i}$ and $f_{j}$, the lower strength direction is the direction
from the lower total feature strength to the higher. Namely, we sum up the
feature strengths computed for each feature in regards to all the features,
and the one with the lowest strength pointing in direction to the highest
strength is the lowest strength direction. We will utilize this to remove
competing edges between two nodes.

Algorithm 2 Search Algorithm for Network Structure

1:procedure NetworkStructure( $S_{i}:f\rightarrow\mathbb{Z}^{+}$)

2: Empty set of nodes $\Phi_{X}=\\{\\}$

3: for each ”Parameter” node $n_{i}$ do

4: for each TopFeature in list $S_{i}$ do

5: Compute most frequent feature $f_{i,k}$

6: Define $f_{i,k}$ as parent node $n_{j}\leftarrow P_{n_{i}}$

7: Add $n_{i}$ and $n_{j}$ to $\Phi_{X}$

8: if edge $n_{i}\rightarrow n_{j}$ exists then

9: remove edge

10: end if

11: end for

12: end for

13: for each ”Observed/Unobserved” node $n_{i}$ do

14: for each TopFeature in list $S_{i}$ do

15: Compute most frequent feature $f_{i,k}$

16: Define $f_{i,k}$ as child node $n_{j}\leftarrow P_{n_{i}}$

17: Add $n_{i}$ and $n_{j}$ to $\Phi_{X}$

18: if edge $n_{j}\rightarrow n_{i}$ exists then

19: remove edge with lower strength direction

20: end if

21: end for

22: end for

23:end procedure

Once the map table for each node is constructed, this algorithm is applied to
build the first candidate network structure. It first passes over each
parameter in the data $X$ independently of all the observed and any unobserved
features. We find the features with the most impact in predicting that
parameter and construct a parent node from the parameter to the global
feature. After all the parameter features have been processed, we then proceed
with finding any child nodes of the observable features. We then end with
doing the same process with any unobserved features or labels/latent
variables.

In choosing each parent (for parameter nodes) or child node, beginning with
the top feature, the algorithm begins by proposing the most frequently
assigned top feature as the first node in the network. This feature being the
most explanatory power for much of the data and thus a node and an edge is
drawn between each of these pairings between the top feature node. We then
choose the second most frequented feature in the map of top features and
propose it as a parent/child node, introducing edges between it and the nodes
proposing that feature as a parent node. Each time we present a new edge, we
must first verify that no cycle is introduced and that edge doesn’t already
exist. To ensure this, we measure the strengths of each feature relative to
the node child node, and choose the edge which has a higher feature strength.

Continuing this until all top feature nodes are exhausted reveals the first
candidate for the network. The final step in generating the network is to
validate the network in that no cycles have been introduced. We again apply
the lowest strength direction to ensure that maximal strengths on all edges
remain. After Algorithm 2 has been applied, we apply a depth-first search
algorithm to locate any cycles between 3 or more nodes. If a cycle is
detected, we loop through all the edges in the cycle and remove the edge that
has the lowest strength direction in the cycle that was introduced. Formally,
this is given in Algorithm 3

Algorithm 3 Cycle detection

1: $\Phi_{X}$, $e\in E$

2:for each node $n_{i}\in\Phi$ do

3: if cycle of length $K$ exists then

4: $\phi\rightarrow\\{n_{i},n_{i,1},\ldots,n_{i,K}\\}$

5: for each possible edge in cycle $e\in\phi$ do

6: if if $e$ has minimum strength then

7: remove $e$ from $E$

8: end if

9: end for

10: end if

11:end for

After removing any cycles from the network, a first generated DAG of the data
has been produced. We can deduce from the three algorithmic steps that the
following properties are ensured.

  * •

All designated parameters of the model have no dependencies (i.e. no child
nodes) introduced. This is due to two properties designed in Algorithm 2,
namely 1) that parameter nodes only propose parent nodes from their feature
strength list, and 2) that all other nodes will only propose all their feature
nodes as child nodes (dependencies)

  * •

All edges in the network are designated to find and connect conditional
dependencies. This is due to the global interpretability property of TMs, that
when learning on any labeled feature, the clauses will assemble literals from
features that design patterns which are beneficial towards predicting that
particular label value.

  * •

No cycles are introduced in the network. This is ensured by the last step 3

Before we begin our numerical examples and validation of the network
generation, we first comment on some practical tips when applying the above
algorithms. In practice, step 5 in Algorithm 1 is quite crucial as it allows
as to control the ”information” that is distributed throughout the network. We
will give strategies on this step in the following sections, but overall, we
have found the best results when $N$, the number of iterations of the TM
learning procedure, is quite large (say $N>20$). Secondly, we also recommend
using multiple TM models to boost robustness when building the map of
important features. This will help ensure that the most crucial global
features for each node are chosen.

Now we move to the empirical section where we first validate our approach, and
then offer two numerical examples on data where no known networks have been
built before and the data comes from real-world industry scenarios.

##  V Car Insurance

To clearly demonstrate how the Algorithm 1 and Algorithm 2 builds a candidate
Bayesian network model, in this section we will go over a full example where
we have sampled data directly from a well-known Bayesian network. The network
is used for car insurance risk estimation of the expected claim costs for a
car insurance policy holder (see Scutari (2010) for more info on the model).
Figure 4 shows the network which contains 27 nodes, of which 15 are
observable, and over 1400 parameters. The hidden nodes (unobserved) are shaded
and output nodes are shown with bold ovals.

Figure 4: Car insurance network to model expected claims costs

We begin by simulating 5000 independent samples from the full joint
probability definition of the network. For each variable, we select a balanced
training set with nearly identical samples of all outputs of that variable to
ensure the most robust literal pattern design in the clauses as possible. In
our first variable, GoodStudent, a two-level factor with levels False and
True, following Algorithm 1 with 20 rounds of training, we’ve collected the
top features and them in a list of candidate. Figure 5 showing the top
features when predicting GoodStudent variable using the balance training set.
Clearly, Age is shown to be the most prominent in this sample and is proposed
as a parent node to GoodStudent. Next, we choose Age as the next node to
model. After applying 5 rounds of learning, we find that RiskAversion is the
feature with the most impact,

Figure 5: Top features collected for predicting GoodStudent variable. Figure
6: Top features collected for predicting Age variable.

Continuing along, very every node, the top 5 features are computed using 20
rounds of learning for the next several nodes. RiskAversion having PropCost,
Age, and CarValue as top parent candidates. The table in II shows in order of
computation, the top 3 features for every node which completes the first stage
in building a candidate Bayesian network structure.

Figure 7: Showing the global feature strengths for RiskAversion

In the Top Feature columns, we use bold font to highlight that the top feature
node is a child of the targeted node, namely that the targeted node has
dependencies in the TopFeatures and italic font to denote that they are an
ancestor.

Comparing the table of the top features chosen for each node with the original
Bayesian network, we see further details in the accuracy of choosing potential
parent node candidate. Especially for nodes with two or more parent nodes, we
notice high accuracy in choosing those nodes as top features after several
rounds of TM learning. For example, SeniorTrain has RiskAversion and Age as
two parent nodes, and were computed as the top two features. OtherCar has
SocioEcon as a parent node and is also a top feature. In the case a node has
no parents, namely, it’s a prior probability that is used for connected nodes,
the feature strength selection process yields similar results, but not as
robust as with nodes predicting their parent nodes.

For example, Age is the parent node providing observable prior information for
two of its top features. ThisCarCost is the only node which had top features
of which none were either true parent nodes of grandparent nodes in the
underlying network, nor were child nodes for any feature. SocioEcon, with
MakeModel and RiskAversion as its top two features, were not parent nodes in
the underlying network, but were child nodes, thus having immediate
dependencies for those nodes.

TABLE II: Top three features derived from each node Node | TopFeature 1 | TopFeature 2 | TopFeature 3
---|---|---|---
SeniorTrain | RiskAversion | Age | RuggedAuto
OtherCar | SocioEcon | RiskAversion | Mileage
Antilock | CarValue | MakeModel | SocioEcon
ILiCost | Accident | MakeModel | DrivQuality
Cushioning | RuggedAuto | RiskAversion | SocioEcon
CarValue | MakeModel | Mileage | RiskAversion
PropCost | RiskAversion | Age | DrivQuality
Airbag | MakeModel | RuggedAuto | Accident
Theft | RiskAversion | SocioEcon | Mileage
ThisCarDam | Accident | DrivQuality | RiskAversion
DrivHist | RiskAversion | DrivQuality | DrivingSkill
ThisCarCost | DrivQuality | Age | RiskAversion
RuggedAuto | MakeModel | SocioEcon | RiskAversion
VehicleYear | CarValue | ThisCarCost | SocioEcon
DrivingSkill | DrivQuality | MakeModel | SocioEcon
GoodStudent | Age | MakeModel | RiskAversion
DrivQuality | RiskAversion | MakeModel | Mileage
Age | RiskAversion | Theft | Mileage
HomeBase | SocioEcon | RiskAversion | Age
Accident | DrivQuality | Mileage | RiskAversion
SocioEcon | MakeModel | RiskAversion | Theft
MedCost | RuggedAuto | RiskAversion | SocioEcon
Mileage | Age | MakeModel | RiskAversion
MakeModel | RiskAversion | Mileage | RuggedAuto
AntiTheft | RiskAversion | SocioEcon | Mileage
RiskAversion | Age | MakeModel | Mileage
OtherCarCost | RuggedAuto | MakeModel | RiskAversion

With the table of nodes their top features estimated, we can now apply
algorithm 2 that essentially proposes the child or parent node candidates and
then prunes the network. The second pass of the algorithm builds the structure
while also respecting both parameter and observed node types. We begin by
choosing the two parameters Age, and Mileage and find the parent nodes by
taking the TopFeature, in this case RiskAversion for Age which suggests that
RiskAversion was typically the most prominent feature in predicting the age of
the driver given all other 26 variables.

Next we consider our observed variables, in this case GoodStudent, followed by
choosing the first top feature which in this case is Age. With the next
candidate node chosen as Age, the algorithm then selects the top feature
extracted RiskAversion. Now selecting RiskAversion as the next candidate node,
we see that Age is selected as the top feature. which creates a scenario in
which a root node is also a child node. In the case of an edge introduced in
the opposite direction, the higher feature is chosen, and in this case
RickAversion is directed towards Age as it has the higher feature direction.
Thus Age becomes the parent node for RiskAversion. This is shown in Figure 8.
With the first three nodes being introduced, GoodStudent, Age, and
RiskAversion with Age determined as the parent for both GoodStudent and
RiskAversion, the next step is to introduce a new node candidate randomly,
SocioEcon. Computing the most prominent feature yields MakeModel with a second
being RiskAversion.

Figure 8 depicts the candidate network after a first round of the 1. Notice
that Age is the dependency on many nodes at the bottom of the network
structure. This corresponds to ground truth network, except for the missing of
several parameter nodes which we introduce next.

Figure 8: First round of the algorithm yields a network close to ground truth

Completing the Algorithm 2 over all observed nodes, we arrive to a network
close to ground truth, with the only additional edges on the graph being
AntiLock being partially dependent on CarValue and Mileage being partially
dependent on Age. Both of these edges could be argued to be included in the
final network, but as we are wanting to see how close we are to the original
network from which we simulated the data, we will need an approach to compare
”distance” between graphs. The best method for this is in so called ”graph
kernels” which are functions that compute an inner product on graphs.

###  V-A Comparison

To compare the proximity to the ground truth network, we apply a kernel graph
based approach to compare a TM generated network with the proposed network
from which the underlying data was simulated. We would like to understand how
similar two nodes are in the graph, comparing both outgoing edges and incoming
edges, as well as how similar the node’s neighbors are.

Graph kernels are used widely in many disciplines and typically follow three
steps, which we will use in our comparison study. For more on graph kernels,
Vishwanathan et al. (2008) contains an in-depth study with various
applications.

  * •

Compute Node Similarity: This step computes the pairwise similarity between
nodes in two graphs, iterating over all nodes in both graphs and calculating
the similarity between corresponding nodes.

  * •

Compute Edge Similarity: Computes the pairwise similarity between edges in the
two graphs similar to node similarity, it involves iterating over all edges in
both graphs and calculating the similarity between corresponding edges and
their direction.

  * •

Combine Similarity: Lastly, we combine the node similarity matrix and edge
similarity matrix into an overall graph similarity score by averaging the
similarities.

Since the graph kernel computation depends on the number of nodes and edges of
a graph, we normalize the values of the averaging of similarities to get a
value between 0 and 1, with 0 being the value comparing a null graph with any
non-empty graph, and 1 being all the nodes and edges with their directions are
identical.

We apply our network structure generating algorithm to four different popular
networks. In order to create a robust framework for the comparison, we run our
algorithm using 5 different randomly chosen Tsetlin Machine parameterizations.
We do this to remove any chance that we could be ”overfitting” our models for
generating the networks. We use a simple strategy of randomly choosing the
number of clauses to be a random integer between 1 and 3 times the total
number of literals for the data simulated by the network. The threshold
parameter is then chosen as a random number between 10 and the number of
clauses, coupled with the specificity between 5 and 15. Finally, the maximum
number of literals per clause is chosen to be a random value between 3 and the
total number literals for the data. Table III shows the randomly chosen
parameterizations, with $L$ being the total number of literals for the data.

TABLE III: Five models used to combine into ensemble model | Clauses | Threshold | Specificity | Max Number Literals
---|---|---|---|---
Model I | L + 12 | 25 | 9.4 | 25
Model II | L + 34 | 21 | 11.2 | 33
Model III | L + 23 | 30 | 6.7 | 7
Model IV | L + 58 | 10 | 9.8 | 55
Model V | L + 92 | 42 | 12.6 | 5

The four networks we simulate data from are as follows:

  * •

Asia: A small simplified version of a network that may be used to diagnose a
doctor’s new patients. Each node represents a facet relating to a patient’s
condition, and each directional edge roughly corresponds to causality.

  * •

Child: A larger network modeling uncertainty of birth asphyxia given lung
metrics, CO2, x-rays, and other variables (see 9)

  * •

Insurance: The network from section V

  * •

Diabetes: A large network used for the detection of early signs and symptoms
of diabetes. Such models are important to control the side effects of diabetes
and Bayesian network models have been used extensively in the literature.

The strategy for our study is to generate 10 networks from each model, and
compute the similarity score using the kernel graph similarity computation.
The average of these scores is then recorded for each model. Table IV shows
the results for the four different networks.

Figure 9: Child network, adapted from Scutari (2010) TABLE IV: Four networks and average similarity score across fives models Network | Model I | Model II | Model III | Model IV | Model V
---|---|---|---|---|---
Asia | 0.834 | 0.855 | 0.791 | 0.846 | 0.821
Child | 0.875 | 0.891 | 0.908 | 0.940 | 0.805
Insurance | 0.831 | 0.874 | 0.924 | 0.981 | 0.819
Diabetes | 0.754 | 0.790 | 0.781 | 0.877 | 0.825

We see that typically, the medium (20 - 50) node networks tend to do best in
performance on average. The smallest network had the worse performers in terms
of models, with the Child and the Insurance networks the best performers
across two of the parameterizations. The very large network (¿ 100 nodes)
performs well on high specificity with high amount of literals allowed per
clause. It seems that on average, high specificity parameter coupled with
allowing more literals per clause seems to work better than being more
restrictive on the number of literals per clause (models III and V). This is
mostly likely because for very challenging target nodes, allowing more
information via literals in the clauses allows for more complex patterns.

While generating networks based on a ground-truth model plays an important
role in this study, we would also like to see the performance of the network
generating algorithm using data that is unlabeled and has no ground-truth for
reference. Here we rely on intuition and logic along with ensuring the
networks generated satisfy the properties of a DAG to derive how well the
algorithm does.

##  VI Supply Chain Analysis

In our final example, we consider a supply chain data set collected from a
Fashion and Beauty startup that is based on the supply chain of makeup
products Singh (2023). Supply chain analytics is the process of collecting,
modeling, and interpreting data related to the movement of products and
services from suppliers to customers.

The challenge with this particular data set is that is it quite small: only
100 observations from the supply chain exist, namely one data point for each
product. With 23 different variables accounting for the supply chain for each
of the products, creating a predictive model for effectively understanding the
sensitivities of revenue generated, the impact of how stock and MC attribute
to profits, and many of the other variables could be challenging for
traditional models such as gradient boost, neural network, or random forests
where larger data sets are typically required. Using our TM formulation for
building network structures of the data, we will see that even though we only
have one observation for each product, achieving a coherent network structure
is still quite readily obtainable.

Figure 10 shows some of the major continuous variables featured in the supply
chain data set along with their value frequency. The easiest way to transform
the continuous variables into observations easily handled by both TMs and
Bayesian networks is to simply attribute the values to `low, medium, high,
very high`. For the categorical variables, such as the ones shown in figure
11, we simply find the frequency each variable and rank them from least
frequency to most frequent. The least frequent value will be a 1, second most
frequent a 2, and so on.

Figure 10: Continuous features of the supply chain data set Figure 11: Some
categorical features of the supply chain data set

With so few observations, obtaining near optimal hyper parameters for our TM
model will be challenging. We propose a simple way around this by building an
ensemble model, which is a collection of smaller models each with different
number of clauses, thresholds, and specificity values. Our global feature
impact model will then be an aggregation of all the literals in each clause in
each model.

We begin by applying our ensemble learning approach on each of the discretized
continuous variables. For this, we set the variable as the target label, thus
giving four different values to learn on `low, medium, high, very high`.

TABLE V: Five models used to combine into ensemble model | Clauses | Threshold | Specificity | Max Number Literals
---|---|---|---|---
Model I | 42 | 14 | 7.2 | 18
Model II | 80 | 37 | 7.4 | 32
Model III | 66 | 35 | 8.7 | 27
Model IV | 85 | 10 | 9.4 | 85
Model V | 42 | 35 | 11.3 | 42

Being the first variable we target, is a variable that is most likely
determined at the origin of the supply chain. Applying our 5 independent TM
models to learn the high impact features, we discover that `Availability`, and
`Production volumes` are the two features which score very high in prediction
impact. Namely, to most accurately predict price, these two variables have the
most impact. A third is `Stock levels` which we will note in our node to
feature table VI.

With the highest impact being `Availability`, we now target this variable to
learn its most salient features. After one round of training with each of the
5 models, we see that `Order quantities` and `Defect rates` play the largest
roles, with `Manufacturing costs` a close third. We then consider `Order
quantities`, and see that `Stock levels` and `Price` are the highest
predictors with `Revenue generated` very strong as well.

Continuing through the rest of the variables, we finalize our node to feature
table VI and can start building an initial directed network where each node is
a variable from the supply chain.

TABLE VI: Top three features derived from each node Node | TopFeature 1 | TopFeature 2
---|---|---
Price | Availability | ProdVolumes
Availability | Order quantities | Defect rates
Order quantities | Stock levels | Price
Lead times | Lead time | Stock levels
Shipping times | MLT | Lead time
Stock levels | Lead times | Availability
Shipping carriers | Order quantities | Shipping times
Customer demographics | RevGenerated | Location
RevGenerated | MC | Stock levels
NumProdSold | MC | Defect rates
Product type | Lead temp | Availability
Supplier name | Availability | Location
Shipping costs | Lead time | Order quantities
Location | Price | ProdVolumes
Lead time | Availability | ProdVolumes
ProdVolumes | NumProdSold | Stock levels
MLT | NumProdSold | Lead time
MC | Order quantities | MLT
Inspection results | Defect rates | RevGenerated
Defect rates | RevGenerated | Order quantities
Transportation modes | Shipping times | Stock levels
Routes | Shipping times | Price
Costs | Order quantities | Defect rates

In our first iteration of the Algorithm 1, a collection of vertices and edges
are produced. The second iteration, Algorithm 2 runs over the network and
looks for competing edges and eliminates any edges with a lower strength
direction. This gives the final network as shown in Figure 12. To ensure there
are no cycles in the graph, we do a depth first search on all the nodes. In
any case there is a cycle, we simply eliminate the edge with the lowest
strength direction in the cycle.

Figure 12: First iteration of the network using top two features for each node

In analyzing the final network, we see that the TM to BN algorithm has
discovered that Product type, Shipping costs, Shipping carriers, Routes,
Customer Demographics, and Location are some of the main input parameters into
the supply chain. This seems to be consistent with the logistics of supply
chains and how they operate in the sense that they are degrees of freedom that
can be used to optimize costs in the supply chain. Namely, they will have an
impact on costs, maintenance, stock, and lead times.

The direct conditionals on Revenue generated has been discovered to be
`Price`, `Costs`, `Number of Products sold`, `Stock levels` and `Inspection
Results`, which from a quick sanity check registers well with typical revenue
models. A failed `Inspection Results` could lead to higher costs, or
manufacturing costs which would impact the revenue generated.

Lastly we see that another important observable node in the supply chain
`Number of products sold` is dependent on `location`, `Production Volumes` and
`Lead times`. In return, it is computed that `Number of products sold`
influences the `defect rate` as perhaps defect rates scale with the number of
customers using the product.

We have also shown two competing directions between the `Availability`
variable and `defect rate`. Here, the feature strength in the direction from
`defect rate` to `Availability` is significantly higher than the other
direction, making the availability of the product conditionally dependent on
the defect rate.

On a final note, we mention that although we now seem to have a candidate for
a network structure, a fully constructed Bayesian network still requires
conditional probability tables across all the parent nodes and their children.
If we do not have expert knowledge into these probability distributions, the
easiest way is to estimate them empirically. With the network proposal built,
generating conditional probability tables for a particular variable node $v$
can be done simply by computing the frequency of each child node’s literals of
$v$, and ensuring they are normalized across all combinations of literals for
that child.

##  VII Bank Customer Churn

In this last example we will build a candidate network for Bank Customer Churn
data. The data in this example is the customer data of account holders from an
Anonymous Multinational Bank and the aim of the data is to not only predict
the customer churn, but understand when predicted, why does it occur. Every
bank wants to hold there customers for sustaining their business for a long
period of time. But as customers might leave their banking institution for a
variety of reasons, generating a Bayesian network for gaining better insights
into customer retention could be useful, e.g. when a customer has a high
probability of leaving given their current conditions. Reasons why a banking
institution might want to minimize customer turnover is because it is
typically much more expensive to sign in a new client than keeping an existing
one. It is advantageous for banks to know what leads a client towards the
decision to leave the company. Churn prevention allows companies to develop
loyalty programs and retention campaigns to keep as many customers as
possible.

The data contains 15 features, of which 4 are parameters, 10 observable, and 1
label (namely whether the customer has left bank). The features are as
follows:

  * •

CreditScore: can have an effect on customer churn, since a customer with a
higher credit score is less likely to leave the bank.

  * •

Geography: a customer’s location can affect their decision to leave the bank.

  * •

Gender: it’s interesting to explore whether gender plays a role in a customer
leaving the bank.

  * •

Age: this is certainly relevant, since older customers are less likely to
leave their bank than younger ones.

  * •

Tenure: refers to the number of years that the customer has been a client of
the bank. Normally, older clients are more loyal and less likely to leave a
bank.

  * •

Balance: also a very good indicator of customer churn, as people with a higher
balance in their accounts are less likely to leave the bank compared to those
with lower balances.

  * •

NumOfProducts: refers to the number of products that a customer has purchased
through the bank.

  * •

HasCrCard: denotes whether or not a customer has a credit card. This column is
also relevant, since people with a credit card are less likely to leave the
bank.

  * •

IsActiveMember: active customers are less likely to leave the bank.

  * •

EstimatedSalary: as with balance, people with lower salaries are more likely
to leave the bank compared to those with higher salaries.

  * •

Exited: whether or not the customer left the bank.

  * •

Complain: customer has complaint or not.

  * •

Satisfaction Score: Score provided by the customer for their complaint
resolution.

  * •

Card Type: type of card hold by the customer.

  * •

Points Earned: the points earned by the customer for using credit card.

We can identify already the three parameters (predictors) being Geography,
Gender, and Age as they have no dependencies. All other features clearly have
some kind of partial dependencies, or might also supply conditions for other
features. For the observed variables, we look first at CreditScore,
EstimatedSalary, and SatisfactionScore which have a few very strong partial
dependencies in predicting churn as we’ll see. Table VII shows the top
features of each observed feature.

TABLE VII: Top three features derived from each node CreditScore | EstimatedSalary | SatisfactionScore
---|---|---
Age | Geography | NumOfProducts
Tenure | Gender | PointEarned
EstimatedSalary | Tenure | EstimatedSalary

We see that CreditScore has dependencies on Age and Tenure, which is typically
in line whith how credit models work for many retail banking institutions.
EstimatedSalary is geographically dependent as some countries have higher
economic power. For the Satisfaction Score, it seems that it is most dependent
on NumOfProducts a customer has purchased through the bank, and how often they
use their credit card.

Figure 13: First candidate network for Bank Customer Churn data

Our first candidate network for the Bank customer churn data is shown in
Figure 13. We see that the label (unobserved) node Exited, namely whether the
customer will leave the banking institution is mostly dependent on their
CreditScore and EstimatedSalary. In turn, these features are highly dependent
on Balance in the account, Age, and Tenure at the institution. This makes
sense in most models for customer churn as normally, older clients are more
loyal and less likely to leave a bank.

##  VIII Conclusion

We proposed an algorithm for constructing a Bayesian network using feature
strength indicators derived from the clause weights and literals of a Tsetlin
machine. We showed through both empirical evidence in comparing with ground-
truth networks as well as through examples where dependencies on certain
features in the data are widely know that TMs generating initial networks
through data is a very promising area of research. The strengths are numerous,
which one being that the method is entirely interpretable which how parent and
child nodes are generated, and also in the shear speed of the approach -
candidate networks can be generated in milliseconds to seconds, even for large
data sets with many features ( 100).

While this first proposal is not without drawbacks or challenges, it has shown
to be an attractive basis for further research and methodical development. One
area that seems like a reasonable direction would be in a hybrid-based
structure learning. Consider for example a score based approach such as in the
Chow-Liu algorithm Scutari (2010) where instead of mutual information is used
to construct a spanning tree, feature strengths derived from TMs are used
instead to construct the first sequence of trees.

Another drawback is the fact that a good foundation for generating a network
should start with knowing the parameters of the model being generated, namely
which features of the data do not have any dependencies. This can be
challenging for many large data sets without expert witnesses. Furthermore,
this approach cannot introduce non-labeled latent variables as all the
features that are candidate nodes need to be present in the data.

We demonstrated that building a Bayesian network with TMs can also reveal
deeper interpretable insights into the data. In our Supply Chain example, even
with only 100 data observations from a supply chain, we were able to build a
network with a good understanding of the inter dependencies in the network.
For the Bank Customer Churn, our network generating algorithms were able to
create a network that fit quite well the narrative to how customer exit models
behave in general.

Our future work will be in several areas in improving the approach. First, we
would like to improve on algorithms 1 and 2 in both filtering for Top Features
in a more constructive way by perhaps working with a newly developed Type-III
feedback system (paper to appear). This method seeks to remove in a more
direct way literals from features which do not add any value to clause
feedback and thus predictions overall. The idea here would be that more
literals would be penalized and thus the final Top Features would have truly
more impact. The second area is to better design how competing directions in
the network are resolved. Here we simply take the higher feature strength
between two competing connections.

Lastly, our next applications of interest will be in designing
temporal/dynamic networks on time-dependent data, where nodes can be connected
via lags in the data.

## References

  * Abeyrathna et al. [2021] Kuruge Darshana Abeyrathna, Ole-Christoffer Granmo, and Morten Goodwin.  Extending the Tsetlin Machine With Integer-Weighted Clauses for Increased Interpretability.  IEEE Access, 9, 2021.
  * Blakely and Granmo [2021] Christian D. Blakely and Ole-Christoffer Granmo.  Closed-Form Expressions for Global and Local Interpretation of Tsetlin Machines.  In 34th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2021). Springer, 2021\.
  * Glimsdal and Granmo [2021] Sondre Glimsdal and Ole-Christoffer Granmo.  Coalesced multi-output tsetlin machines with clause sharing, 2021.
  * Granmo [2018] Ole-Christoffer Granmo.  The Tsetlin Machine - A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic.  arXiv preprint arXiv:1804.01508, 2018.
  * Kasza and Solomon [2011] Jessica Kasza and Patty Solomon.  A comparison of score-based methods for estimating bayesian networks using the kullback-leibler divergence, 2011.
  * Oommen [1997] B.J. Oommen.  Stochastic searching on the line and its applications to parameter learning in nonlinear optimization.  IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 27(4):733–739, 1997.
  * Scutari [2010] Marco Scutari.  Learning bayesian networks with the bnlearn r package, 2010.
  * Scutari [2015] Marco Scutari.  Bayesian network constraint-based structure learning algorithms: Parallel and optimised implementations in the bnlearn r package, 2015.
  * Sharma et al. [2021] Jivitesh Sharma, Rohan Yadav, Ole-Christoffer Granmo, and Lei Jiao.  Drop Clause: Enhancing Performance, Interpretability and Robustness of the Tsetlin Machine.  arXiv e-prints, page arXiv:2105.14506, May 2021.
  * Singh [2023] Harsh Singh.  Supply chain analysis - kaggle, 2023.
  * Vishwanathan et al. [2008] S. V. N. Vishwanathan, Karsten M. Borgwardt, Imre Risi Kondor, and Nicol N. Schraudolph.  Graph kernels, 2008.

In this subsection, we give some more details of the TM with weights model.
The learning of weights is based on increasing the weight of clauses that
receive true positive output (Type Ia feedback) and decreasing the weight of a
clause that receive false positive outputs (penalizing Type II feedback). The
motivation is to determine which clauses are inaccurate and thus must team up
to obtain high accuracy as a team (low weight clauses), and which clauses are
sufficiently accurate to operate more independently (high weight clauses). The
weight updating procedure is summarized in Algorithm 4. Here, $w_{i}$ is the
weight of clause $C_{i}$ at the $n^{th}$ training round (ignoring polarity to
simplify notation). The first step of a training round is to calculate the
clause output. The weight of a clause is only updated if the clause output
$C_{i}$ is 1 and the clause has been selected for feedback ($P_{i}$ = 1). Then
the polarity of the clause and the class label $y$ decide the type of feedback
given. That is, like a regular TM, positive polarity clauses receive Type Ia
feedback if the clause output is a true positive, and similarly, they receive
Type II feedback if the clause output is a false positive. For clauses with
negative polarity, the feedback types switch roles. When clauses receive Type
Ia or Type II feedback, their weights are updated accordingly. We use the
stochastic searching on the line (SSL) automaton to learn appropriate weights.
SSL is an optimization scheme for unknown stochastic environments Oommen
[1997]. The goal is to find an unknown location $\lambda^{*}$ within a search
interval $[0,1]$. In order to find $\lambda^{*}$, the only available
information for the Learning Mechanism (LM) is the possibly faulty feedback
from its attached environment $E$.
In SSL, the search space $\lambda$ is discretized into $N$ points,
$\\{0,1/N,2/N,...,(N-1)/N,1\\}$ with N being the discretization resolution.
During the search, the LM has a location
$\lambda\in\\{0,1/N,2/N,...,(N-1)/N,1\\}$, and can freely move to the left or
to the right from its current location. The environment $E$ provides two types
of feedback: $E=1$ is the environment suggestion to increase the value of
$\lambda$ by one step, and $E=0$ is the environment suggestion to decrease the
value of $\lambda$ by one step. The next location of $\lambda$, i.e.
$\lambda_{n+1}$, can thus be expressed as follows:

$\lambda_{n+1}=\begin{cases}\lambda_{n}+1/N,&\text{if $E_{n}=1$,}\\\
\lambda_{n}-1/N,&\text{if $E_{n}=0$.}\\\ \end{cases}$ (2)
$\lambda_{n+1}=\begin{cases}\lambda_{n},&\text{if $\lambda_{n}=1$ and
$E_{n}=1$,}\\\ \lambda_{n},&\text{if $\lambda_{n}=0$ and $E_{n}=0$.}\\\
\end{cases}$ (3)

Asymptotically, the learning mechanics is able to find a value arbitrarily
close to $\lambda^{*}$ when $N\rightarrow\infty$ and $n\rightarrow\infty$. In
our case, the search space of clause weights is $[0,\infty]$, so we use
resolution $N=1$, with no upper bound for $\lambda$. Accordingly, we operate
with integer weights. As in Algorithm 4, if the clause output is a true
positive, we simply increase the weight by $1$. Conversely, if the clause
output is a false positive, we decrease the weight by $1$.
By following the above procedure, the goal is to make low precision clauses
team up by giving them low weights, so that they together can reach the
summation target $T$. By teaming up, precision increases due to the resulting
ensemble effect. Clauses with high precision, however, obtain a higher weight,
allowing them to operate more independently.
The above weighting scheme has several advantages. First of all, increment and
decrement operations on integers are computationally less costly than
multiplication based updates of real-valued weights. Additionally, a clause
with an integer weight can be seen as multiple copies of the same clause,
making it more interpretable than real-valued weighting, as shown in the next
section. Additionally, clauses can be turned completely off by setting their
weights to $0$ if they do not contribute positively to the classification
task. For a more detailed explanation of the weighted TM, please refer to
Abeyrathna et al. [2021].

Algorithm 4 Complete WTM learning process

1:Input: Training data batch $(B,x,y)\quad\rhd B\geq 1$

2:Initialize: Random initialization of TAs

3:Begin: $n^{th}$ training round

4:for $i=1,...,m$ do if $P_{i}=1$

5: if ($y=1$ and $i$ is odd) or ($y=0$ and $i$ is even) then

6: if $c_{i}=1$ then

7: $w_{i}\leftarrow w_{i}+1$

8: for feature $k=1,...,2o$ do

9: if $l_{k}=1$ then

10: Type Ia Feedback

11: else:

12: Type Ib Feedback

13: end if

14: end for

15: else:

16: $w_{i}\leftarrow w_{i}\quad\rhd$ [No Change]

17: Type Ib Feedback

18: end if

19: else: ($y=1$ and $i$ is even) or ($y=0$ and $i$ is odd)

20: if $c_{i}=1$ then

21: if $w_{i}>0$ then

22: $w_{i}\leftarrow w_{i}-1$

23: end if

24: for feature $k=1,...,2o$ do

25: if $l_{k}=0$ then

26: Type II Feedback

27: else:

28: Inaction

29: end if

30: end for

31: else:

32: $w_{i}\leftarrow w_{i}\quad\rhd$ [No Change]

33: Inaction

34: end if

35: end if

36:end for