Weighted finite automata (WFAs) have been widely applied in many fields. One of the classic problems for WFAs is probability distribution estimation over sequences of discrete symbols. Although WFAs have been extended to deal with continuous input data, namely continuous WFAs (CWFAs) [Li et al., 2022], it is still unclear how to approximate density functions over sequences of continuous random variables using WFA-based models, due to the limitation on the expressiveness of the model as well as the tractability of approximating density functions via CWFAs. In this paper, we propose a nonlinear extension to the CWFA model to first improve its expressiveness, we refer to it as the nonlinear continuous WFAs (NCWFAs). Then we leverage the so-called RNADE method, which is a well-known density estimator based on neural networks, and propose the RNADE-NCWFA model. The RNADE-NCWFA model computes a density function by design. We show that this model is strictly more expressive than the Gaussian HMM model, which CWFA cannot approximate. Empirically, we conduct a synthetic experiment using Gaussian HMM generated data. We focus on evaluating the model's ability to estimate densities for sequences of varying lengths (longer length than the training data). We observe that our model performs the best among the compared baseline methods.

Weighted finite automata, sequential density estimation, neural density estimation.

§ INTRODUCTION

Many tasks in natural language processing, computational biology, reinforcement learning, and time series analysis rely on learning
with sequential data, , estimating functions defined over sequences of observations from training data.
Weighted  finite automata (WFAs) are a powerful and flexible class of models which can efficiently represent such functions.
WFAs are tractable, they encompass a wide range of machine learning models (they can for example compute any probability distribution defined by a hidden Markov
model (HMM) [Denis and Esposito, 2008] and can model the transition and observation behavior of
partially observable Markov decision processes [Thon and Jaeger, 2015]) and they offer appealing theoretical guarantees. In particular,
the so-called
methods for learning HMMs [Hsu et al., 2009], WFAs [Bailly et al., 2009, Balle et al., 2014] and related models [Glaude and Pietquin, 2016, Boots et al., 2011],
provide an alternative to Expectation-Maximization (EM) based learning algorithms that is both computationally efficient and

One of the major applications of WFA is to approximate probability distribution over sequences of discrete symbols. Although the WFA model has been extended to the continuous domain [Li et al., 2022, Rabusseau et al., 2019] as the so-called linear 2-RNN model (or continuous WFA model), approximating density functions for sequential data under continuous domain using this model is not straight-forward, as the model does not guarantee to compute a density function by construction. Moreover, due to the linearity of the model, the continuous WFA model (CWFA) is not expressive enough to estimate some of the common density functions over sequences of continuous random variables such as a Gaussian hidden Markov model.

In recent years, neural networks have been widely applied in density estimation and have been proved to be particularly successful. To estimate a density function via neural networks, the neural density estimator need to be flexible enough to represent complex densities but have tractable inference functions and learning algorithms. One particular example of such models is the class of autoregressive models [Uria et al., 2016, Uria et al., 2013], where the joint density is decomposed into a product of conditionals and each conditional is approximated by a neural network. One other type of methods are the so-called flow-based methods (normalizing flows) [Dinh et al., 2014, Dinh et al., 2016, Rezende and Mohamed, 2015]. Flow-based methods transform a base density (e.g. a standard Gaussian) into the target density by an invertible transformation with tractable Jacobian. Although these methods have been used to estimate sequential densities, the sequences often come as fixed length. It is often unclear how to generalize these methods to account for varying length of the sequences in the testing phase, which can be important for some sequential task, such as language modeling for NLP task. Weighted finite automata, on the other hand, are designed to carry out such task under the discrete setting. The question is, how to generalize WFA to approximate density functions over continuous domains.

In this paper, by extending the classic CWFA model with a (nonlinear) feature mapping and a (nonlinear) termination function, we first propose our nonlinear continuous weighted finite automata (NCWFA) model. Combining this model with the RNADE framework [Uria et al., 2013], we propose RNADE-NCWFA to approximate sequential density functions. The model is flexible as it  naturally generalizes to sequences of varying lengths. Moreover, we show that the RNADE-NCWFA model is strictly more expressive than the Gaussian HMM model. In addition, we propose a spectral learning based algorithm for efficiently learning the parameters of a RNADE-NCWFA. For the empirical study, we conduct synthetic experiments using data generated from a Gaussian HMM model. We compare our proposed spectral learning of  RNADE-NCWFA with HMM learned with the EM algorithm, RNADE with LSTM and RNADE-NCWFA learned with stochastic gradient descent. We evaluate the models' performance through  their log likelihood over sequences of unseen length, meaning the testing sequences are longer than the training sequences, to observe the models' generalization ability. We show that our model outperforms all the baseline models on this metric, especially for long testing sequences. Moreover, the advantage of our model is more significant when dealing with small training sizes and noisy data.

§ BACKGROUND

In this section, we  first introduce  basic tensor algebra. Then we  introduce the continuous weighted finite automata model as well as the RNADE model for density estimation.

§.§ Tensor algebra

We first recall basic definitions of tensor algebra; more details can be found
in [Kolda and Bader, 2009].
A tensor $\T\in \Rbb^{d_1\times\cdots \times d_p}$ can simply be seen
as a multidimensional array $(\T_{i_1,\cdots,i_p}\ : \ i_n\in [d_n], n\in [p])$. The
mode-$n$ fibers of $\T$ are the vectors obtained by fixing all
indices except  the $n$th one, $\T_{:,i_2,\cdots,i_p}\in\Rbb^{d_1}$.
The $n$th mode matricization of $\T$ is the matrix having the
mode-$n$ fibers of $\T$ for columns and is denoted by
$\tenmat{T}{n}\in \Rbb^{d_n\times d_1\cdots d_{n-1}d_{n+1}\cdots d_p}$.
The vectorization of a tensor is defined by $\vectorize{\T}=\vectorize{\tenmat{T}{1}}$.

In the following $\T$ always denotes a tensor of size $d_1\times\cdots \times d_p$.

The mode-$n$ matrix product of the tensor $\T$ and a matrix
$\X\in\Rbb^{m\times d_n}$ is a tensor  denoted by $\T\ttm{n}\X$. It is
of size $d_1\times\cdots \times d_{n-1}\times m \times d_{n+1}\times
\cdots \times d_p$ and is defined by the relation
$\Y = \T\ttm{n}\X \Leftrightarrow \tenmat{Y}{n} = \X\tenmat{T}{n}$.
The mode-$n$ vector product of the tensor $\T$ and a vector
$\vec{v}\in\Rbb^{d_n}$ is a tensor defined by $\T\ttv{n}\vec{v} = \T\ttm{n}\vec{v}^\top
\in \Rbb^{d_1\times\cdots \times d_{n-1}\times d_{n+1}\times
\cdots \times d_p}$.

It is easy to check that the $n$-mode product satisfies $(\T\ttm{n}\mat{A})\ttm{n}\mat{B} = \T\ttm{n}\mat{BA}$
where we assume compatible dimensions of the tensor $\T$ and
the matrices $\A$ and $\B$. Given strictly positive integers $n_1,\cdots, n_k$ satisfying
$\sum_i n_i = p$, we use the notation $\tenmatgen{\T}{n_1,n_2,\cdots,n_k}$ to denote the $k$th order tensor
obtained by reshaping $\T\in\R^{d_1\times \cdots\times d_p}$ into a tensor[Note that the specific ordering used to perform matricization, vectorization
and such a reshaping is not relevant as long as it is consistent across all operations.] of size
$(\prod_{i_1=1}^{n_1} d_{i_1}) \times (\prod_{i_2=1}^{n_2} d_{n_1 + i_2}) \times \cdots \times (\prod_{i_k=1}^{n_k} d_{n_1+\cdots+n_{k-1} + i_k}).$

A rank $R$ tensor train (TT) decomposition [Oseledets, 2011] of a tensor
$\T\in\R^{d_1\times \cdots\times d_p}$ factorizes $\T$ into the product of $p$ core tensors
$\G_1\in\R^{d_1\times R},\G_2\in\R^{R\times d_2\times R},
\cdots, \G_{p-1}\in\R^{R\times d_{p-1} \times R},
\G_p \in \R^{R\times d_p}$, and is defined[The classical definition of the TT-decomposition allows the rank $R$ to be different
for each mode, but this definition is sufficient for the purpose of this paper.] by
$\T_{i_1,\cdots,i_p} =
for all indices $i_1\in[d_1],\cdots,i_p\in[d_p]$ (here $(\G_1)_{i_1,:}$ is a row vector, where $[d] = \{1, 2, \cdots, d\}$, $(\G_2)_{:,i_2,:}$ is an $R\times R$ matrix, etc.).  We will use the notation $\T = \TT{\G_1,\cdots,\G_p}$
to denote this product. The name of this decomposition comes from the fact that the tensor $\Tt$ is decomposed into a train of lower-order tensors.

§.§ Continuous weighted finite automata (CWFAs)

The concept of continuous weighted finite automata (CWFAs) is a generalization of the classic weighted finite automata model to its continuous input case and is also shown to be equivalent to the linear second-order RNN model [Li et al., 2022, Rabusseau et al., 2019].

A continuous weighted finite automaton with $k$ states (CWFA) is defined by a tuple $A = \langle \vec{\alpha}, \Aten, \mat{\Omega}\rangle$, where $\vec{\alpha} \in \mathbb{R}^k$ is the initial weight, $\Aten\in \mathbb{R}^{k\times d\times k}$ is the transition tensor, and $\mat{\Omega} \in \mathbb{R}^{k\times p}$ is the termination matrix. Let $(\mathbb{R}^d)^*$ denote the set of sequences of size $d$ real-valued vectors. A CWFA computes the following function $f: (\mathbb{R}^d)^* \rightarrow \mathbb{R}^p$:

\begin{equation}
\label{eq:def_cwfa}
f(\x_1,\x_2,\cdots, \x_n)= (\At\ttv{1}\szero \ttv{2}\x_1)^\top(\At\ttv{2}\x_2)\cdots(\At\ttv{2}\x_n)\mat{\Omega}.
\end{equation}

To learn the CWFA model, [Li et al., 2022] extend the spectral learning algorithm for the classic WFA model [Mohri et al., 2012, Balle et al., 2014] to its continuous case. The algorithm relies on the Hankel tensor, which is a generalization of the Hankel matrix.

For a function  $f:(\R^d)^*\to\R^p$, its Hankel tensor of length $l$, $\Hten_f^l\in \R^{[d]^l \times p}$ is defined by
$(\Hten_f)^{l}_{i_1, \cdots, i_l,:} = f(\e_{i_1},\cdots,\e_{i_l}),$
where $\e_1,\cdots,\e_d$ denotes the  canonical basis  of $\mathbb{R}^d$.

In practice, to learn the Hankel tensor, one can use gradient descent to minimize the loss function $\mathcal{L}(\x_1,\cdots,\x_l, \vec{y}, \mathbfcal{H}) = \norm{(\x^{\otimes})^\top \tenmatgen{\mathbfcal{H}}{l,1} - \vec{y}}_F^2,$ over a training dataset. Here $\x_1, \cdots, \x_l$ is an input sequence and $\vec{y}$ the corresponding output, and  $\x^{\otimes} = \x_1\otimes \x_2\otimes\cdots\otimes\x_l$. It is is shown in
[Li et al., 2022] that the Hankel tensor of a CWFA with finite states can be parameterized by its tensor train form, i.e. $\mathbfcal{H}^{(l)} = \TT{\G_1,\cdots,\G_{l+1}}$. The spectral learning algorithm for CWFA relies on the following theorem [Li et al., 2022] showing how to recover the parameters of CWFA from Hankel tensors of the function it computes.

Let $f:(\R^d)^*\to \R^p$ be a function computed by a minimal linear CWFA  with $n$ hidden units and let
$L$ be an integer such that[It is worth mentioning that such an integer does not always exist. See [Li et al., 2022] for more details.] $\rank(\tenmatgen{\Hten^{(2L)}_f}{L,L+1}) = n$. Then, for any $\P\in\R^{d^L\times n}$ and $\S\in\R^{n\times d^Lp}$ such that $\tenmatgen{\Hten^{(2L)}_f}{L,L+1} = \P\S,$ the  minimal CWFA computing $f$ is defined by:

$$\szero = (\S\pinv)^\top\tenmatgen{\Hten^{(L)}_f}{L+1}, \ \vvsinf^\top = \P\pinv\tenmatgen{\Hten^{(L)}_f}{L,1},\ \Aten = (\tenmatgen{\Hten^{(2L+1)}_f}{L,1,L+1})\ttm{1}\P\pinv\ttm{3}(\S\pinv)^\top$$

§.§ Real-valued neural autoregressive density estimator (RNADE)

The real-valued neural autoregressive density estimator (RNADE) [Uria et al., 2013] is a generalization of the original neural autoregressive density estimator (NADE) [Uria et al., 2016] to  continuous variables.
The core idea of RNADE is to estimate the joint density using the chain rule and approximate each conditional density via neural networks, i.e.

\begin{align}
\label{RNADE}
p(x_1, \cdots, x_n) &= \prod_{i=1}^n p(x_i|x_{<i})~~\mathrm{with}~~ p(x_i|x_{<i})=p_M(x_i|\theta_i),
\end{align}

where $x_{<i}$ denotes all attributes preceding $x_i\in \mathbb{R}$ in a fixed ordering, $p_M$ is a mixture of $m$ Gaussians with parameters $\theta_i = \{\vec{\beta}_i \in \R^{m}, \vec{\mu}_i\in\R^m, \vec{\sigma}_i\in\R^m\}$. Moreover, we have: $p_M(x_i|\theta_i)=\sum_{j=1}^m\vec{\beta}^{j}_i  \mathcal{N}(x_i| \vec{\mu}^{j}_i, \vec{\sigma}^{j}_i)$, where $\vec{\beta}_{i}^{j}$ denotes the $j$th element of $\vec{\beta}_i$, same for $\vec{\mu}_i^j$ and $\vec{\sigma}_i^j$ and $\mathcal{N}(x_i|\vec{\mu}_i^j, \vec{\sigma}_i^j)$ denotes the Gaussian density with mean $\vec{\mu}_i^j$ and standard deviation $\vec{\sigma}_i^j$ evaluated at $x_i$. Note that $\vec{\beta}_i, \vec{\mu}_i, \vec{\sigma}_i$  are functions of $x_{<i}$. These functions are often chosen to be various forms of neural networks. In the classic setting, RNADE with $m$ mixing components and $k$ hidden states has the following update rules:

\begin{align}
\vec{h}_i &= g_i(\vec{h}_{i-1}) ,~~~\vec{\beta}_i = \mathrm{softmax}(\mat{V}^{\beta}_i\vec{h}_{i-1} + \vec{b}_i^\beta) \label{eq:state}\\
\vec{\mu}_i &= \mat{V}^{\mu}_i\vec{h}_{i-1} + \vec{b}_i^\mu \label{eq:mu},~~~~\vec{\sigma}_i = \mathrm{exp}(\mat{V}^{\sigma}_i\vec{h}_{i-1} + \vec{b}_i^\sigma),
\end{align}

where $\mat{V}^{\beta}_i, \mat{V}^{\mu}_i$ and $\mat{V}^{\sigma}_i$ are $m\times k$ matrices, $\vec{b}_i^\beta, \vec{b}_i^\mu$ and $\vec{b}_i^\sigma$ are vectors of size $m$, and $g_i$ is an update function for the hidden state which is time step dependent (see [Uria et al., 2013] for more details on the specific update functions used in the original RNADE formulation). The softmax function [Bridle, 1990] ensures the mixing weights $\vec{\beta}$ are positive and sum to one and the exponential ensures the variances are positive.
RNADE is trained to minimize the negative log likelihood: $\mathcal{L}(x_1\cdots x_n, \theta_i) = -\sum_{i=1}^n  \mathrm{log}(p_M(x_i|\theta_i))$ via gradient descent.

§ METHODOLOGY

To approximate density functions with CWFA, we need to improve the expressivity of the model and  constrain it to compute a valid density function. In this section, we first introduce nonlinear continuous weighted finite automata. Then, we  present RNADE-NCWFA for sequential density approximation, which combines CWFA with the RNADE framework. In the end, we show that RNADE-NCWFA is strictly more expressive than Gaussian HMM and present our spectral learning based algorithm for learning RNADE-NCWFA.

§.§ Nonlinear Continuous Weighted Finite Automata (NCWFAs)

To leverage CWFAs to estimate density functions, we first need to improve the expressivity of the model. We will do so by introducing a nonlinear feature map as well as a nonlinear termination function. We hence propose the nonlinear continuous weighted finite automata (NCWFA) model as the following:

A nonlinear continuous weighted finite automaton (NCWFA) is defined by a tuple $\Tilde{A} = \langle \vec{\alpha}, \xi, \phi, \cA\rangle$, where $\vec{\alpha} \in \mathbb{R}^k$ is the initial weight, $\phi: \mathbb{R}^d \rightarrow \mathbb{R}^{d^\prime}$ is the feature map, $\xi: \mathbb{R}^k \rightarrow \mathbb{R}^p$ is the termination function and $\cA\in \mathbb{R}^{k\times d\times k}$ is the transition tensor. Given a sequence $\x_1, \cdots, \x_l$, the function that the NCWFA $\Tilde{A}$ computes is:

\begin{align}
\vec{h_0} &= \vec{\alpha},~~~~\vec{h_t} = \cA\bullet_1\vec{h}_{t-1}\bullet_2\phi(\x_{t}),~~~~f_{\Tilde{A}}(\x_1, \cdots, \x_l) = \xi(\vec{h}_{l}).
\end{align}

One immediate observation is that we can exactly recover the definition of a CWFA  by letting $\phi(\x_i) =\x_i$ and $\xi(\vec{h}) = \vec{h}^\top \mat{\Omega}$.

§.§ Density Estimation with NCWFAs

The second problem to tackle is that we need to constrain the NCWFA so that it can tractably compute a density function. In this section, we will leverage the  RNADE method to propose the RNADE-NCWFAs model. The proposed model is flexible and can compute sequential densities of arbitrary sequence length. Moreover, we will show that this model is strictly more expressive than the classic Gaussian HMM model.

Recall the core idea of RNADE is to estimate the joint density using the chain rule as in Equation <ref>. Instead of approximating the conditionals via the classic RNADE treatment as in Equations <ref>, we use an NCWFA $\Tilde{A} = \langle \vec{\alpha}, \xi, \phi, \mathbfcal{A}\rangle$, i.e., $p(\x_i|\x_{<i}) = f_{\Tilde{A}}(\x_1, \cdots, \x_i)$. One key difference with the classic RNADE model is that the state update function is independent of the time step, allowing the model to generalize to sequences of arbitrary lengths.
However, an NCWFA does not readily compute a density function, as the function does not necessarily integrates to one and the output is non-negative.
To overcome this issue, we adopt the approach used in RNADE  by constraining the output of the NCWFA to be a mixture of Gaussians with diagonal covariance matrices:

\begin{align}
\phi(\x_i) &= \mathrm{\tanh}(\x_i^\top \mat{W}),~~\vec{h}_i = \mathbfcal{A}\ttv{1}\vec{h}_{i-1}\bullet_2 \phi(\x_{i}),~~\vec{\beta}_i = \mathrm{softmax}(\mat{V}^{\beta}_i\vec{h}_{i-1} + \vec{b}_i^\beta)  \label{eq:phi_RNADE-NCWFA}\\
\mat{M}_i &= \mathbfcal{V}^{\mu} \ttv{1}\vec{h}_{i-1} + \mat{B}^\mu,~~\mat{\Sigma}_i = \mathrm{exp}(\mathbfcal{V}^{\sigma}\ttv{1}\vec{h}_{i-1} + \mathbfcal{B}^\sigma)\label{eq: mu, sigma}\\
\xi(\x_i, \vec{h}_{i-1}) &= \sum_{j=1}^m \vec{\beta}_i^{j} \mathcal{N}(\x_i|\mat{M}_i^{j}, \mathrm{diag}(\mat{\Sigma}_i^j)),~~~~f_{\Tilde{A}}(\x_1, \cdots, \x_l) = \xi(\x_l, \vec{h}_{l-1}) \label{eq:xi_RNADE-NCWFA}
\end{align}

where $\vec{h}_0 = \vec{\alpha}, \mathbfcal{V}^{\mu} \in\mathbb{R}^{k\times m\times d}, \mathbfcal{V}^{\sigma} \in\mathbb{R}^{k\times m\times d}, \mat{B}^\mu\in\mathbb{R}^{m\times d}, \mathbfcal{B}^\sigma\in\mathbb{R}^{m\times d}$, $\vec{\mu}_i^j = (\mat{M}_i)_{:, j}\in \R^{d}, \mat{\Sigma}_i^{j} = (\mat{\Sigma}_i)_{:, j} \in\R^{d}$. $\mathrm{diag}$ is defined to be $\mathrm{diag}(\mat{\Sigma}^j_i) = (\mat{\Sigma}^{j}_i \otimes \vec{1})\circ \mat{I}$, where $\circ$ denotes the Hadamard product, $\vec{1}\in \mathbb{R}^d$ is an all one vector and $\mat{I}\in\mathbb{R}^{d\times d}$ is an identity matrix. For simplicity, we let $d^\prime = d$ and approximate each conditional via a mixture of Gaussian with diagonal covariance matrix. This can be changed to a full covariance matrix, should the corresponding assumption (positive semi-definite) of the matrix is satisfied. Note this simplification does not affect the expressiveness of the model, as a GMM with a diagonal covariance matrix is also an universal approximator for densities and can approximate a GMM with a full covariance matrix [Benesty et al., 2008], given enough states. Under this definition, it is easy to show that $\prod_{i=1}^l f_{\Tilde{A}}(\x_{\leq i})$ computes the density of the sequence $\x_{\leq l}$, where $\x_{\leq l}$ denotes $\x_1, \cdots, \x_l$. We will refer to this NCWFA model with RNADE structure as RNADE-NCWFA of $k$ states and $m$ mixtures. Note although the definitions of $\vec{\beta}_i$, $\mat{M}_i$ and $\mat{\Sigma}_i$ takes specific forms, in practice, one can use any differentiable function of $\vec{h}_i$ to compute $\vec{\beta}_i$, $\mat{M}_i$ and $\mat{\Sigma}_i$, so long as $\vec{\beta}_i$ sums to one and $\mat{\Sigma}_i$ is positive.

One natural question to ask is how expressive this model is. We  show in the following theorem (proof in Appendix <ref>) that RNADE-NCWFA is strictly more expressive than Gaussian HMMs, which is well known for sequential modeling [Bilmes et al., 1998].
Given a Gaussian HMM with $k$ states $\eta = \langle \vec{\mu}, \mat{T}, O\rangle$, where $O: \mathbb{R}^k\times\mathbb{R}^d \rightarrow \mathbb{R}^+$ is the Gaussian emission function, $\mu \in \mathbb{R}^k$ is the initial state distribution and $\mat{T}\in [0,1]^k$ is the transition matrix, there exists a $k$ states $k$ mixtures RNADE-NCWFA $\Tilde{A} = \langle \vec{\alpha}, \xi, \phi, \mathbfcal{A}\rangle$ with full covariance matrices such that the density function over all possible trajectories generated by $\eta$ can be computed by $\Tilde{A}$: $p^{\eta}(\vec{o}_1 \cdots \vec{o}_n) = \prod_{i=1}^{n} f_{\Tilde{A}}(\vec{o}_{\leq n})$
for any trajectory $\vec{o}_1 \cdots \vec{o}_n$. Moreover, there exists a RNADE-NCWFA $\Tilde{A}$ such that no Gaussian HMM model can compute its density.

Note that a CWFA cannot compute the density function of a Gaussian mixture. Indeed, the function computed by a CWFA on a sequence of length $1$ is linear in its input, whereas a RNADE-NCWFA associate such an input to a Gaussian density.

To learn RNADE-NCWFA, we want to maximize the likelihood given some training set   $D_l=\{\x^1_{\leq l}, \cdots , \x^N_{\leq l}\}$ of length-$l$ sequences of $d$ dimensional vectors, i.e., $\x^n_{\leq l} = \x^n_1,\cdots, \x^n_l$, where each $\x^n_i\in\R^d$. More specifically, we want to minimize the negative log likelihood function:
$\mathcal{L}(\Tilde{A}, D) = -\sum_{i=1}^N \sum_{j=1}^l \mathrm{log}(f_{\Tilde{A}}(\x^i_{\leq j})).$
One straight-forward solution is to use gradient descent to optimize this loss function. However, as pointed out in [Bengio et al., 1994], due to repeated multiplication by the same transition tensor, gradient descent is prone to suffer from the vanishing gradient problem and to fail in capturing long term dependencies. One alternative is the classic spectral learning algorithm for WFAs. Recall that the spectral learning method for CWFA requires to first learn Hankel tensors of length $L$, $2L$ and $2L+1$ and then perform a rank factorization on the learnt Hankel tensor to recover the CWFA parameters (see [Li et al., 2022]). However, due to the nonlinearity added to the model, namely the feature map $\phi$ and the termination function $\xi$, spectral learning alone will not be enough. To circumvent this issue, we present an algorithm jointly leveraging gradient descent and spectral learning. The idea is to first learn the Hankel tensors of various length and the function $\phi$ and $\xi$ using gradient descent. Then we use the spectral learning algorithm to recover the transition tensor and the initial weights.

Let $\delta$ and $\omega$ denote the parameters of the mappings $\phi$ and $\xi$, respectively (see Eq. <ref>-<ref>), and let $\Hten^{(l)}_{\Tilde{A}} = \TT{\Gten^{(l)}_1,\cdots,\Gten^{(l)}_{l}}$ be the TT form of the Hankel tensor,  where $\Gten^{(l)}_1\in\R^{d\times k}$ and $\Gten^{(l)}_i\in\R^{k\times d\times k}$ for $i = 2, \cdots, l$. The spectral learning method for RNADE-NCWFAs first involves an approximation of the Hankel tensor via minimizing the following loss function:

\begin{equation}
\label{loss: density loss}
\mathcal{L}(\delta, \omega,\Gten^{(l)}_1,\cdots,\Gten^{(l)}_{l}, D_l) = -\sum_{i=1}^N\sum_{j=1}^l \mathrm{log}\left[\xi\left(\psi(\x^i_{\leq j})^\top \tenmatgen{\TT{\Gten^{(l)}_1,\cdots,\Gten^{(l)}_{j}}}{j,1}\right)\right]
\end{equation}

where $\psi(\x_{\leq j}) = \phi(\x_1)\otimes\cdots\otimes\phi(\x_j)$.
In this process, we have obtained the Hankel tensors and the parameters of the termination function and the feature map. Then, one can perform a rank factorization on the learned Hankel tensor and recover the rest of the parameters for the RNADE-NCWFA, namely $\vec{\alpha}, \cA$. The detailed algorithm is presented in Algorithm <ref>.

: Spectral Learning of RNADE-NCWFA

[1]
Three training datasets $D_L,D_{2L},D_{2L+1}$ with input sequences of length $L$, $2L$ and $2L+1$ respectively, an encoder $\phi_{\delta}$, a termination function $\xi_{\omega}$ and TT-parameterized Hankel tensors $\Hten^{(L)}_{\Tilde{A}}$, $\Hten^{(2L)}_{\Tilde{A}}$ and $\Hten^{(2L+1)}_{\Tilde{A}}$, learning rate $\gamma$, desired rank $R$

Model not converging
Update $\delta, \omega, \Gten^{(l)}_1, \cdots, \Gten^{(l)}_l$ via gradient descent by minimize the loss function <ref>:
$\theta \in \{\delta, \omega, \Gten^{(l)}_1, \cdots, \Gten^{(l)}_l\}$

$$\theta \leftarrow \theta - \gamma \nabla_{\theta} \mathcal{L}(\delta, \omega,\Gten^{(l)}_1,\cdots,\Gten^{(l)}_{l}, D_l)$$

Let $\tenmatgen{\Hten^{(2L)}_{\Tilde{A}}}{L,L+1} = \P\S$ be a rank $R$ factorization.
Return the RNADE-NCWFA $\Tilde{A} = \langle \vec{\alpha}, \xi_\omega, \phi_\delta, \mathbfcal{A}\rangle$ where

\begin{align*}
\vec{\alpha} &= (\S\pinv)^\top\tenmatgen{\Hten^{(L)}_{\Tilde{A}}}{L+1},~~~~~~~~\Aten= (\tenmatgen{\Hten^{(2L+1)}_{\Tilde{A}}}{L,1,L+1})\ttm{1}\P\pinv\ttm{3}(\S\pinv)^\top
\end{align*}

§ EXPERIMENTS

For the experiments, we conduct a synthetic experiment based on data generated from a random 10-states Gaussian HMM. We sample sequences of length 3, 6 and 7 from the HMM. To evaluate the model's performance on its generalization ability to unseen length of sequence, we sample 1,000 sequences from length 8 to length 400 from the same HMM for the test data. To test the model's resistance to noise, we inject the training samples with Gaussian noise of different standard deviations  (0.1 and 1.0) with 0 mean.

For the baseline models, we have HMM learned with expectation maximization (EM) method, as it can computes density of sequences of any length by design.  We also modified the RNADE model by replacing the hidden states update rule <ref> with an LSTM structure to give the RNADE model the ability to generalize to sequences of arbitrary length, regardless of the length of the training sequences. We refer to this model as RNADE-LSTM. For our model, by following Algorithm <ref>, we have the method RNADE-NCWFA (spec). Alternatively, although we have mentioned that training the (RNADE-)NCWFA model through pure gradient descent method can have many issues, we also list this approach of training RNADE-NCWFA as one of the baselines, referred to as RNADE-NCWFA (sgd).
For all the training processes, if gradient descent is involved, we always use Adam optimizer [Kingma and Ba, 2014] with 0.001 learning rate with early stopping. For HMM as well as RNADE-NCWFA models, we set the size of the model to be 10 (ground truth of the randomly HMM). For RNADE-LSTM, we set the size of the hidden states to be 10. We present the trend of the averaged log likelihood ratio with the ground truth likelihood, i.e. $\mathrm{log}(\frac{\mathrm{predicted~likelihood}}{\mathrm{ground~truth}})$ w.r.t. length of the sequences over 10 seeds in Figure <ref> and a snapshot of the log likelihood for each model of 400 length testing sequences in Appendix <ref>.

From the experiment results, we can see that RNADE-CWFA (spec) consistently has the best performance across all training sizes and levels of noise injected. More precisely, this advantage is more significant when given small training sizes and (or) the data is injected with high noise. Moreover, the spectral learning algorithm shows stable training results as the standard deviation of the log likelihood (ratio) is the lowest among all methods. This is especially the case when not enough training samples are provided. In addition, one can see that this advantage is consistent with all test sequence lengths we have experimented.

Log likelihood ratios between the tested models and the ground truth likelihood. We show the trend w.r.t. the length of the testing sequences under different sample sizes (columns) and standard deviations of the injected noise (rows).

§ CONCLUSION AND FUTURE WORK

In this paper, we propose the RNADE-NCWFA model, an expressive and tractable WFA-based density estimator over sequences of continuous vectors. We extend the notion of continuous WFA to its nonlinear case by introducing a nonlinear feature mapping function as well as a nonlinear termination function. We then combine the idea from RNADE to propose our density estimation model RNADE-NCWFA and its spectral learning based learning algorithm. In addition, we show that theoretically, RNADE-NCWFA is strictly more expressive than the Gaussian HMM model. We show that, empirically, our method has great capability of generalize to sequences of varying length, which is potentially not the same as the training sequences. For future work, we are looking into more experiments on real dataset and compare with more baselines. Moreover, we did not add nonlinear transition for the NCWFA model as it would imply that the Hankel tensor will be of infinite tensor train rank, hence making the spectral learning algorithm intractable. We will be looking into possibilities of adding this nonlinearity into the NCWFA model and have a working algorithm for it. In addition, we would like to examine more closely in terms of the expressivity of the RNADE-NCWFA.

[Bailly et al., 2009]
Raphaël Bailly, François Denis, and Liva Ralaivola.
Grammatical inference as a principal component analysis problem.
In Proceedings of the 26th Annual International Conference on
Machine Learning, pages 33–40. ACM, 2009.

[Balle et al., 2014]
Borja Balle, Xavier Carreras, Franco M Luque, and Ariadna Quattoni.
Spectral learning of weighted automata.
Machine learning, 960 (1-2):0 33–63,

[Balle et al., 2014]
Borja Balle, William L. Hamilton, and Joelle Pineau.
Methods of moments for learning stochastic languages: Unified
presentation and empirical comparison.
In Proceedings of ICML, pages 1386–1394,

[Benesty et al., 2008]
Jacob Benesty, M Mohan Sondhi, Yiteng Huang, et al.
Springer handbook of speech processing, volume 1.
Springer, 2008.

[Bengio et al., 1994]
Yoshua Bengio, Patrice Simard, and Paolo Frasconi.
Learning long-term dependencies with gradient descent is difficult.
IEEE transactions on neural networks, 50 (2):0
157–166, 1994.

[Bilmes et al., 1998]
Jeff A Bilmes et al.
A gentle tutorial of the em algorithm and its application to
parameter estimation for gaussian mixture and hidden markov models.
International Computer Science Institute, 40
(510):0 126, 1998.

[Boots et al., 2011]
Byron Boots, Sajid M Siddiqi, and Geoffrey J Gordon.
Closing the learning-planning loop with predictive state
The International Journal of Robotics Research, 300
(7):0 954–966, 2011.

[Bridle, 1990]
John S Bridle.
Probabilistic interpretation of feedforward classification network
outputs, with relationships to statistical pattern recognition.
In Neurocomputing, pages 227–236. Springer, 1990.

[Denis and Esposito, 2008]
François Denis and Yann Esposito.
On rational stochastic languages.
Fundamenta Informaticae, 860 (1, 2):0 41–77,

[Dinh et al., 2014]
Laurent Dinh, David Krueger, and Yoshua Bengio.
Nice: Non-linear independent components estimation.
arXiv preprint arXiv:1410.8516, 2014.

[Dinh et al., 2016]
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio.
Density estimation using real nvp.
arXiv preprint arXiv:1605.08803, 2016.

[Glaude and Pietquin, 2016]
Hadrien Glaude and Olivier Pietquin.
PAC learning of probabilistic automaton based on the method of
In Proceedings of ICML, pages 820–829, 2016.

[Hsu et al., 2009]
Daniel J. Hsu, Sham M. Kakade, and Tong Zhang.
A spectral algorithm for learning hidden markov models.
In Proceedings of COLT, 2009.

[Kingma and Ba, 2014]
Diederik Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980, 2014.

[Kolda and Bader, 2009]
Tamara G Kolda and Brett W Bader.
Tensor decompositions and applications.
SIAM review, 510 (3):0 455–500, 2009.

[Li et al., 2022]
Tianyu Li, Doina Precup, and Guillaume Rabusseau.
Connecting weighted automata, tensor networks and recurrent neural
networks through spectral learning.
Machine Learning, 2022.

[Mohri et al., 2012]
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.
Foundations of machine learning.
MIT press, 2012.

[Oseledets, 2011]
Ivan V Oseledets.
Tensor-train decomposition.
SIAM Journal on Scientific Computing, 330
(5):0 2295–2317, 2011.

[Rabusseau et al., 2019]
Guillaume Rabusseau, Tianyu Li, and Doina Precup.
Connecting weighted automata and recurrent neural networks through
spectral learning.
In The 22nd International Conference on Artificial Intelligence
and Statistics, pages 1630–1639. PMLR, 2019.

[Rezende and Mohamed, 2015]
Danilo Rezende and Shakir Mohamed.
Variational inference with normalizing flows.
In International conference on machine learning, pages
1530–1538. PMLR, 2015.

[Thon and Jaeger, 2015]
Michael Thon and Herbert Jaeger.
Links between multiplicity automata, observable operator models and
predictive state representations: a unified learning framework.
The Journal of Machine Learning Research, 160
(1):0 103–147, 2015.

[Uria et al., 2013]
Benigno Uria, Iain Murray, and Hugo Larochelle.
Rnade: The real-valued neural autoregressive density-estimator.
Advances in Neural Information Processing Systems, 26, 2013.

[Uria et al., 2016]
Benigno Uria, Marc-Alexandre Côté, Karol Gregor, Iain Murray, and Hugo
Neural autoregressive distribution estimation.
The Journal of Machine Learning Research, 170
(1):0 7184–7220, 2016.

§ PROOF OF THEOREM

Given a Gaussian HMM with $k$ states $\eta = \langle \vec{\mu}, \mat{T}, O\rangle$, where $O: \mathbb{R}^k\times\mathbb{R}^d \rightarrow \mathbb{R}^+$ is the Gaussian emission function, $\mu \in \mathbb{R}^k$ is the initial state distribution and $\mat{T}\in [0,1]^k$ is the transition matrix, there exists a $k$ states $k$ mixtures RNADE-NCWFA $\Tilde{A} = \langle \vec{\alpha}, \xi, \phi, \mathbfcal{A}\rangle$ with full covariance matrices such that the density function over all possible trajectories generated by $\eta$ can be computed by $\Tilde{A}$:

$$p^{\eta}(\vec{o}_1 \cdots \vec{o}_n) = \prod_{i=1}^{n} f_{\Tilde{A}}(\vec{o}_{\leq n})$$

for any trajectory $\vec{o}_1 \cdots \vec{o}_n$. Moreover, there exists a RNADE-NCWFA $\Tilde{A}$ such that no Gaussian HMM model can compute its density.

For the Gaussian HMM $\eta$, given an observation sequences $\vec{o}_1 \cdots \vec{o}_n$, its density under $\eta$ is:

$$p^{\eta}(\vec{o}_1 \cdots \vec{o}_n) = O(\vec{m}^\top, \vec{o}_1)O(\vec{m}^\top \mat{T}, \vec{o}_2)\cdots O(\vec{m}^\top\mat{T}^{n-1}, \vec{o}_n),$$

where $O(\vec{h}, \vec{o}) = \sum_{i=1}^k \vec{h}_i \mathcal{N}(\vec{o}|\vec{\mu}, \mat{\Sigma})$ for some mean vector $\vec{\mu}$ and covariance matrix $\mat{\Sigma}$.
Let $\vec{\alpha} = \vec{m} $, $\cA_{:, i, :} = \mat{T}$ for $i\in [k]$, $\phi(\x) = [\frac{1}{k}, \frac{1}{k}, \cdots, \frac{1}{k}]^\top$ and $\xi = O$. Note it reasonable to let $\xi = O$, since as long as we let $\vec{\beta}_i = \vec{\alpha}^\top \mat{T}^{i-1}$, $\vec{\beta}_0 = \vec{\alpha}^\top$, $\vec{\mu}_i = \vec{\mu}$ and $\vec{\Sigma}_i = \vec{\Sigma}$, following equations <ref>, then for any $\vec{h}\in\R^k, \vec{o} \in \R^d$, we have $\xi(\vec{h}, \vec{o}) = O(\vec{h}, \vec{o})$. Then under this parameterization, we have $\cA\ttv{2}\phi(\vec{o}_j) = \mat{T}$. Then the RNADE-NCWFA computes the following function:

\begin{align*}
f_{\Tilde{A}}(\vec{o}_1, \cdots, \vec{o}_i) &= \xi( (\cA \ttv{1} \vec{\alpha}^\top\ttv{2}\phi(\vec{o}_1))^\top (\cA \ttv{2}\phi(\vec{o}_2))\cdots (\cA \ttv{2}\phi(\vec{o}_{i-1})), \vec{o}_i)\\
&= \xi(\vec{\alpha}^\top \mat{T}^{i-1}, \vec{o}_i) = O(\vec{m}^\top \mat{T}^{i-1}, \vec{o}_i)
\end{align*}

Therefore, we have:

\begin{align*}
p^{\eta}(\vec{o}_1 \cdots \vec{o}_n) &= O(\vec{m}^\top, \vec{o}_1)O(\vec{m}^\top \mat{T}, \vec{o}_2)\cdots O(\vec{m}^\top\mat{T}^{n-1}, \vec{o}_n)\\
&= f_{\Tilde{A}}(\vec{o}_1)f_{\Tilde{A}}(\vec{o}_1, \vec{o}_2)\cdots f_{\Tilde{A}}(\vec{o}_1, \cdots, \vec{o}_n) = \prod_{i=1}^{n} f_{\Tilde{A}}(\vec{o}_{\leq n})
\end{align*}

For the proof of the second half of the theorem, consider a shifting Gaussian HMM, where the mean vector of the Gaussian emission is a function of the time steps, i.e., $\vec{\mu} = q(i)$, where $i = 1, 2, \cdots$. For simplicity, assume the shifting Gaussian HMM is for one dimensional sequences and has one mixture. In addition, let $q(i) = i$ and assume the variance is 1. Then the emission function can be written as $O^t(o) = \mathcal{N}(o|t, 1)$. Then the density of a sequence $o_1, \cdots, o_n$ under this shifting Gaussian HMM $\eta_s$ is:

$$p^{\eta_s}(o_1, \cdots, o_n) = O^1({o}_1)O^2({o}_2)\cdots O^n({o}_n).$$

We show that this density cannot be computed by a Gaussian HMM of finite states. If $p^{\eta_s}$ can be computed by a Gaussian HMM, then for the mean vector $\vec{\mu}$ there exists an initial weight vector $\vec{m}$, a transition matrix $\mat{T}$ satisfying the following linear system:

\begin{equation*}
\begin{cases}
\vec{m}^\top\vec{\mu} &= 1\\
\vec{m}^\top \mat{T}\vec{\mu} &= 2\\
\vec{m}^\top \mat{T}^{n-1}\vec{\mu} &= n\\
\end{cases}
\end{equation*}

This linear system is, however, overdetermined, as $\vec{\mu}$ is a vector of finite size, while there are infinite linearly independent equations to satisfy. Therefore, a Gaussian HMM of finite states cannot compute the density function of a shifting Gaussian HMM.

We now show such density can be computed by a RNADE-NCWFA. Let $\vec{\alpha}^\top = [1, 1]$, and $\cA_{:, i, :} =  \begin{bmatrix}
1 & 1 \\
0 & 1
\end{bmatrix}$, $\vec{\mu}_i = \langle \vec{h}_{i-1}, [0, 1] \rangle$, $\phi(o)^\top = [0.5, 0.5]$, $\mat{\Sigma}_i = 1$. Then we have:

\begin{align*}
f_{\Tilde{A}}({o}_1, \cdots, {o}_i) &= \xi( (\cA \ttv{1} \vec{\alpha}^\top\ttv{2}\phi({o}_1))^\top (\cA \ttv{2}\phi({o}_2))\cdots (\cA \ttv{2}\phi({o}_{i-1})), {o}_i)\\
&= \xi(\vec{\alpha}^\top \mat{T}^{i-1}, {o}_i) = \xi([1, i], o_i) = \mathcal{N}(o_i|i, 1)
\end{align*}

\begin{align*}
p^{\eta_s}(o_1, \cdots, o_n) &= \mathcal{N}(o|1, 1)\mathcal{N}(o|1, 2)\cdots\mathcal{N}(o|1, n)\\
&= f_{\Tilde{A}}({o}_1)f_{\Tilde{A}}({o}_1, {o}_2)\cdots f_{\Tilde{A}}({o}_1, \cdots, {o}_n) = \prod_{i=1}^{n} f_{\Tilde{A}}(\vec{o}_{\leq n})
\end{align*}

Therefore, for the given shifting Gaussian HMM density, it can be computed by a RNADE-NCWFA, but cannot be computed by a Gaussian HMM with finite states.

§ EXPERIMENT RESULTS IN TABLE

In this section, we show a snapshot of the results we show in the previous experiment results in Figure <ref>. The result is listed in Table <ref>. The reported likelihood is evaluated on test sequence of length 400. From this table, we can see more clearly the advantage of our RNADE-NCWFA model when trained with spectral learning algorithm.

Comparison of model performance in term of average log likelihood (in NAT). Different models are compared under different training sizes and level of noise injected. The reported likelihood (mean (standard deviation)) is evaluated on test sequence of length 400.

Training Size     3c|100                                                                                3c|500                                                                                3c1000
Noise Std         1c|0                           1c|0.1                         1c|1      1c|0                           1c|0.1                          1c|1      1c|0                           1c|0.1                         1c1
HMM (EM)          1l|-615.26 (2.57)              1l|-616.88 (3.40)              -638.44 (7.50)              1l|-601.15 (0.20)              1l|-601.18 (0.17)               -628.75 (1.51)              1l|-600.70 (0.12)              1l|-600.69 (0.12)              -628.91 (1.13)

RNADE-LSTM        1l|-604.71 (3.36)              1l|-604.10 (2.29)              -641.72 (7.17)              1l|-600.86 (0.15)              1l|-600.85 (0.23)               -628.28 (3.56)              1l|-601.01 (1.34)              1l|-600.67 (0.24)              -628.45 (1.56)

RNADE-NCWFA (spec)               1l|-600.96 (0.42)     1l|-601.06 (0.24)     -621.75 (2.71)     1l|-600.73 (0.18)     1l|-600.67 (0.067)     -622.10 (1.44)     1l|-600.50 (0.49)     1l|-600.53 (0.07)              -621.91 (1.13)

RNADE-NCWFA (sgd)           1l|-604.11 (2.13)              1l|-603.29 (1.69)              -633.96 (14.6)              1l|-600.81 (0.20)              1l|-600.91 (0.46)               -631.80 (5.53)              1l|-600.51 (0.06)              1l|-600.52 (0.08)     -629.11 (1.65)

Ground Truth      1l|-600.40                     1l|-600.40                     -600.40                     1l|-600.40                     1l|-600.40                      -600.40                     1l|-600.40                     1l|-600.40                     -600.40


# Communication On the Use of Impedance Detuning for Gastrointestinal Segment
Tracking of Ingestible Capsules

Erdem Cil, , Icaro V. Soares, , David Renaudeau, Ronan Lucas, Sema Dumanli, ,
Ronan Sauleau, , and Denys Nikolayev (Corresponding author: Denys Nikolayev,
denys.nikolayev@deniq.com)E. Cil is with the Univ Rennes, CNRS, IETR – UMR
6164, FR-35000 Rennes, France and with BodyCAP, FR-14200 Hérouville St Clair,
France.I. V. Soares, R. Sauleau, and D. Nikolayev are with the Univ Rennes,
CNRS, IETR – UMR 6164, FR-35000 Rennes, France.D. Renaudeau is with the
PEGASE, INRAE, Agrocampus-Ouest, 16 le clos, FR-35590 Saint-Gilles, France.R.
Lucas is with BodyCAP, FR-14200 Hérouville St Clair, France.S. Dumanli is with
the Department of Electrical and Electronics Engineering, Bogazici University,
34343 Istanbul, Turkey.

###### Abstract

During their travel through the gastrointestinal tract, ingestible antennas
encounter detuning in their impedance response due to varying electromagnetic
properties of the surrounding tissues. This paper investigates the possibility
of using this impedance detuning to detect in which segment of the
gastrointestinal tract – stomach, small intestine, or large intestine – the
capsule is located. Meandered dipole antennas operating in the 433 MHz
Industrial, Scientific, and Medical Band are designed for this purpose. The
antennas conform to the inner surface of 3D-printed polylactic-acid capsules
with a shell thickness of 0.6 or 0.4 mm. The impedance response is first
optimized numerically in a homogeneous cylindrical phantom with time-averaged
electromagnetic properties. The magnitude and the phase of the reflection
coefficient are then obtained in different tissues and compared with
simulations and measurements. The experimental demonstration is carried out
first using tissue-mimicking liquids and then in a recently deceased ex vivo
porcine model. The minimum change in the phase between different
gastrointestinal tissues was determined to be around $10^{\circ}$ in the
porcine model, indicating that the changes in the impedance response,
particularly the changes in the phase, provide sufficient information to
follow the position of the capsule in the gastrointestinal tract.

###### Index Terms:

Conformal antennas, dipole antennas, impedance detuning, in-body, ingestible
devices, in vivo applications.

##  I Introduction

In recent years, ingestible devices have been widely used in diverse medical
applications, such as monitoring of physiological data and wireless endoscopy
[1, 2, 3]. Due to the variety of possible applications and compact structure
of these devices, the ingestible bioelectronics have the potential to
substantially improve the diagnostics and therapies of the gastrointestinal
(GI) tract [4].

Ingestible devices consist of several components integrated into the same
capsule [5]. The antenna is one of the key components as the quality of the
communication link with external devices strongly depends on its performance
[6, 7]. Therefore, different types of antennas, such as patch [8, 9, 10],
spiral [11], helical [12, 13], and differentially-fed antennas [14, 15] have
been implemented in ingestible capsules. Note that the ingestible antenna
design is a challenging task due to the variety of loss mechanisms encountered
in their operation. These losses can be classified as near-field, propagation,
reflection, and detuning losses [16, 17, 18, 19]. The latest corresponds to
the possible changes in the impedance response of the antenna caused by the
physical and electromagnetic (EM) variations in the surrounding biological
environment as the capsule travels through the GI tract. Several studies in
the literature examined these changes at different frequencies, such as 403.5
MHz [20], 433 MHz [21, 22], and 2.45 GHz [23, 24]. Moreover, various robust
ingestible antenna designs were proposed to mitigate this loss component [25,
26, 27, 28, 29, 30, 31, 32].

Recent technological breakthroughs in terms of miniaturization, artificial
intelligence, and power saving have enabled innovative companies to develop
ingestible systems for monitoring physiological data [33, 34]. The next
generation of ingestible bioelectronic systems aims to provide information
beyond this intent by performing accurate measurements all along the GI tract.
For instance, the real-time localization of a capsule inside the GI tract can
be a useful and innovative measurement to (i) optimize a device to investigate
the middle of the track which is not accessible with probes (feeding tube,
rectal probe), (ii) correlate a measurement and a position to determine the
segment duration in order to identify specific pathologies such as
gastroparesis, (iii) deliver efficiently an active substance at the right
position. The smart capsules designed within this context can offer an
ergonomic and accurate medical system.

In this context, this paper investigates the possibility of using the
impedance detuning caused by the varying EM properties of the GI tract to
distinguish the GI tissues (i.e. stomach, small intestine, or large intestine)
for localization purposes. For this investigation, impedance responses (both
magnitude and phase of the reflection coefficient) of capsule-integrated
meandered dipole antennas in different GI tissues are compared with
simulations in numerical phantoms representing different GI tissues and with
measurements in tissue-mimicking liquids as well as in an ex vivo porcine
model. To the authors’ best knowledge, it is the first time in the literature
where impedance responses of ingestible antennas are investigated for the
purpose of GI segment tracking.

This communication is organized as follows: First, Section II describes the
antenna and simulation models, and presents the simulation results. Then,
Section III explains the prototyping process, and discusses the measurement
results. Finally, the paper concludes in Section IV.

##  II Numerical Study

###  II-A Antenna Design and Modeling

A capsule-integrated ingestible antenna is designed for the intended purpose.
A meandered dipole antenna is preferred for the design since its radiation
mechanisms and the near field behavior have been widely studied and better
understood than the complex structures [16, 35]. The designed antenna, as
visualized in Fig. 1a, is a meandered dipole antenna operating in the 433 MHz
Industrial, Scientific, and Medical (ISM) band. It is designed on a 100-µm-
thick Rogers CLTE-MW substrate ($\varepsilon_{r}$ = 2.97) [36], which conforms
to the inner surface of the polylactic-acid (PLA, $\varepsilon_{r}$ = 2.7,
$\delta$ = 0.003) capsule as shown in Fig. 1b. The capsule is also filled with
a PLA cylinder to fix the antenna in its cylindrical shape and has two
thicknesses: $t=0.6$ mm or $t=0.4$ mm. It is placed in the middle of a
cylindrical homogeneous phantom, as seen in Fig. 1c. The trace length is
numerically optimized for the two shell thicknesses in the phantom having
time-averaged EM properties of the GI tract ($\varepsilon_{r}=63$,
$\sigma=1.02$ S/m). The detailed description of the time-averaged phantom can
be found in [24, 37]. The optimized values for the trace length are 16.4 mm
for $t=0.6$ mm and 14 mm for $t=0.4$ mm. The values of the other parameters
are the same for two shell thicknesses and are shown in Fig. 1a. The parameter
$N$ indicates the number of turns as explained in [38] and is equal to 7 for
both models. Note that an offset feed is required to better match the antennas
to 50 $\Omega$ due to long antenna meandering [39].

(a)

(b)

(c)

Figure 1: Model of the antenna, the capsule and the numerical setup (units:
mm). (a) Meandered dipole antenna model. (b) Antenna conforming to the inner
surface of the PLA capsule. (c) Capsule placed inside the cylindrical
numerical phantom for simulations.

###  II-B Numerical Results

After optimizing the antennas, the possibility of using the impedance detuning
is examined by simulating the antennas in numerical phantoms representing 3
tissues in the GI tract: stomach, small intestine, and large intestine. The EM
properties of these tissues at 434 MHz are tabulated in Table I [40]. The
simulated magnitude and phase of the reflection coefficient are shown in Fig
2. From the results, it can be seen that the minimum difference in the
magnitude observed between 3 GI tissues at 434 MHz is 0.9 dB for $t=0.6$ mm
and 1.1 dB for $t=0.4$ mm. As for the phase, it is $16.9^{\circ}$ for $t=0.6$
mm and $19.7^{\circ}$ for $t=0.4$ mm. As these values are sufficiently large
to distinguish the tissues, it can be stated that the change in the impedance
response of the antenna in different GI tissues can be utilized to determine
the segment in which the capsule is located. Note that it is more convenient
to track the change in the phase for the intended purpose, as it is more
dominant than the change in the magnitude.

TABLE I: EM Properties of the GI Tissues at 434 MHz and the Amount of Each Ingredient (in grams) Used per 100 g Mixture for the Fabrication of the Tissue-Mimicking Liquids | Average | Stomach | Small Intestine | Large Intestine
---|---|---|---|---
$\varepsilon_{r}$ | $63$ | $67.2$ | $65.3$ | $62$
$\sigma$ (S/m) | $1.02$ | $1.01$ | $1.92$ | $0.87$
Water | $53.96$ | $59.13$ | $54.59$ | $52.97$
Sugar | $44.6$ | $39.7$ | $42.6$ | $45.8$
Salt | $1.44$ | $1.17$ | $2.81$ | $1.23$
Figure 2: Simulation results for the magnitude and the phase of the reflection
coefficient obtained in numerical phantoms representing different GI tissues
for two shell thicknesses.

##  III Prototyping and Measurements

The measurements were carried out using two different measurement setups. In
the first setup, tissue-mimicking liquids were used. In the second setup, ex
vivo measurements were performed using a porcine model.

###  III-A Prototyping

The antennas and 3D-printed capsules were fabricated for the measurements, as
shown in Fig. 3a and Fig. 3b, respectively. The antennas were soldered to the
coaxial cable and placed inside the capsules. The side of the capsules was
covered with Araldite 2012 epoxy resin to make a watertight seal. As mentioned
previously, the main purpose of this study is to compare the impedance
responses of the antennas in different GI tissues. However, with the
introduction of the coaxial cable, the EM changes in the environment around
the cable also affect the impedance responses, decreasing the accuracy of the
comparison. Therefore, ferrite rings, which help eliminate this undesired
effect by attenuating the magnetic fields created between the cable and the
antenna, were placed at the antenna end of the cable. Note that the cable
affects the operation of the antennas even with the use of ferrite rings.
However, the ferrite rings stabilize this effect in different tissues by
making it independent of the surrounding environment, which is sufficient for
the aim of this work. The complete prototype with the ferrite rings can be
seen in Fig. 3c.

Figure 3: Different parts of the prototype and the porcine model. (a) Printed
antenna. (b) 3D-printed PLA capsule. (c) Final antenna under test (AuT) with
the ferrite rings. (d) General view of porcine model used in the ex vivo
measurements. (e) AuT placed inside the porcine model.

###  III-B Measurements in Tissue-Mimicking Liquids

For the first measurement setup, tissue-mimicking liquids were fabricated with
deionized water, sugar, and salt using the method proposed in [27]. The amount
of each ingredient used for 100 g tissues is tabulated in Table I. The EM
properties of the fabricated liquids were validated at 434 MHz with a SPEAG
DAK-12 probe [41]. Fig. 4 shows the measurement results in the prepared
liquids. It can be observed that the operating frequency in the liquid with
time-averaged EM properties is shifted to 408.6 MHz for $t=0.6$ mm and 398.3
MHz for $t=0.4$ mm due to the effect of the cable. At these resonant
frequencies, the minimum difference in the phase observed between 3 GI tissues
is $5.3^{\circ}$ for $t=0.6$ mm and $16.3^{\circ}$ for $t=0.4$ mm. Similar to
the simulation results, these values are sufficiently large to identify the
tissue in which the capsule is located, supporting the idea presented in this
work.

Figure 4: Measurement results for the magnitude and the phase of the
reflection coefficient obtained in tissue-mimicking liquids for two shell
thicknesses.

###  III-C Ex vivo Measurements

In the second measurement setup, ex vivo measurements were performed using the
porcine model shown in Fig. 3d. Experimental validation of the proposed EM-
sensing with ingestible capsules requires measurements using recently deceased
tissues as the EM properties might quickly evolve post-mortem [42]. Thus, Ex
vivo measurements on a 50-kg live body-weight Yucatan miniature pig were
performed at the experimental facilities of the Unité Expérimentale
Physiologie et Phénotypage des Porcs in Saint-Gilles, France [43].

After premedication with ketamine (15 mg/kg IM), a 50-kg live body-weight
Yucatan miniature pig was euthanized by intravenous injection of 5 ml of T61 –
a nonbarbiturate, non-narcotic combination consisting of 3 compounds:
embutramide (anesthetic), mebenzonium iodide (paralytic), and tetracaine
hydrochloride (potent local anesthetic). Once euthanized, the animal was
placed in dorsal recumbency. An incision (about 30 cm) was made in the lower
abdominal wall ventral median following the linea alba starting 100 mm behind
the breastbone, opening the abdominal cavity. The stomach (M1), the apical
part of the duodenum (M2), the terminal part of the ileum (at the beginning:
M3 and at the end: M4), and the terminal part of the colon (M5) were located
and exteriorized. At each location, 1 cm incisions were made to insert the
prototypes and the prototypes were inserted in 10 cm depth as shown in Fig.
3e.

Fig. 5 shows the measurement results obtained using the porcine model. As can
be seen, the change in the magnitude and phase values in different tissues is
greater compared to the simulations and measurements in the liquids. The
responses in different tissues become more distinguishable with a more
realistic setup, as the real tissues have a heterogeneous form and contain air
gaps. The EM properties of the real tissues vary depending on the spatial
coordinates, contrary to the homogeneous tissue models, which contributes to
the differences observed in the responses.

Figure 5: Measurement results for the magnitude and the phase of the
reflection coefficient obtained with the porcine model for two shell
thicknesses. Figure 6: The values of the magnitude and the phase of the
reflection coefficient at 434 MHz measured using the porcine model. The
straight lines show the magnitude and the dashed lines show the phase.

Furthermore, Fig. 6 illustrates the magnitude and phase values measured at 434
MHz with the porcine model. It can be observed that the values change
significantly depending on the tissue. This indicates that it is possible to
distinguish the tissues by tracking the impedance response. Moreover, the
graphs obtained with two different antennas have similar tendencies, showing
the consistency of the measurements. Hence, the results obtained with the
porcine model support the idea presented in this paper.

##  IV Conclusion

This paper examined the possibility of using the impedance detuning of
ingestible antennas to track the segment of the GI tract in which a capsule is
located. For this examination, meandered dipole antennas that are conformal to
a PLA capsule are designed to operate in the 433 MHz ISM band. The examination
is performed by comparing the impedance responses of the optimized antennas in
different GI tissues with simulations and measurements (tissue-mimicking
liquids and porcine model). The results show that the location of the capsule
can be followed by tracking the changes in the impedance response, in phase in
particular. Our future work aims at developing biodegradable resonators (for
instance, Mg) on the outside part of the capsule as an additional indicator.
Such a resonator will rapidly degrade in the stomach due to its acidic nature
and hence can be used to distinguish the stomach from the other segments. The
real-time localization of capsules inside the GI tract can be useful to
improve diagnostics as well as to deliver drugs and therapies more
efficiently.

## Acknowledgement

The authors would like to thank Sébastien Moussay and Estelle Blond from
BodyCAP, without whom this research would have been impossible, Christophe
Guitton for the manufacturing of prototypes, Frédéric Boutet and Laurent Le
Coq for helping with the antenna measurements, and Céline Gantier for the
assistance with the ex vivo demonstration.

## References

  * [1] E. Katz, _Implantable bioelectronics_. Weinheim, Germany, Wiley, 2014.
  * [2] A. Kiourti and K. S. Nikita, “A review of in-body biotelemetry devices: Implantables, ingestibles, and injectables,” _IEEE Trans. Biomed. Eng._ , vol. 64, no. 7, pp. 1422–1430, 2017.
  * [3] H. Rajagopalan and Y. Rahmat-Samii, “Wireless medical telemetry characterization for ingestible capsule antenna designs,” _IEEE Antenn. Wireless Propag. Lett._ , vol. 11, pp. 1679–1682, 2012.
  * [4] Y. Rahmat-Samii and L. Song, “Advances in communication and biomedical antenna developments at the UCLA antenna lab: Handheld, wearable, ingestible, and implantable [bioelectromagnetics],” _IEEE Antennas Propag. Mag._ , vol. 63, no. 5, pp. 102–115, 2021.
  * [5] M. R. Yuce and T. Dissanayake, “Easy-to-swallow wireless telemetry,” _IEEE Microw. Mag._ , vol. 13, no. 6, pp. 90–101, 2012.
  * [6] D. Nikolayev, W. Joseph, M. Zhadobov, R. Sauleau, and L. Martens, “Optimal radiation of body-implanted capsules,” _Phys. Rev. Lett._ , vol. 122, no. 10, p. 108101, Mar. 2019.
  * [7] Z. Sipus, A. Šušnjara, A. K. Skrivervik, D. Poljak, and M. Bosiljevac, “Influence of uncertainty of body permittivity on achievable radiation efficiency of implantable antennas—Stochastic analysis,” _IEEE Trans. Antennas Propag._ , vol. 69, no. 10, pp. 6894–6905, Oct. 2021.
  * [8] R. Das and H. Yoo, “A wideband circularly polarized conformal endoscopic antenna system for high-speed data transfer,” _IEEE Trans. Antennas Propag._ , vol. 65, no. 6, pp. 2816–2826, 2017.
  * [9] R. R. Hasan, R. Saraff, P. Dutta, S. Roy, A. Mosabbir, and S. Nath, “Ingestible antenna at inner-wall of capsule for capsule endoscopy,” in _Proc. 10th Int. Conf. Electr. Comput. Eng. (ICECE 2018)_ , Dhaka, Bangladesh, 2018, pp. 201–204.
  * [10] A. Iqbal, M. Al-Hasan, I. B. Mabrouk, and M. Nedil, “Scalp-Implantable MIMO antenna for high-data-rate head implants,” _IEEE Antenn. Wireless Propag. Lett._ , vol. 20, no. 12, pp. 2529–2533, Dec. 2021.
  * [11] S. H. Lee, J. Lee, Y. J. Yoon, S. Park, C. Cheon, K. Kim, and S. Nam, “A wideband spiral antenna for ingestible capsule endoscope systems: Experimental results in a human phantom and a pig,” _IEEE Trans. Biomed. Eng._ , vol. 58, no. 6, pp. 1734–1741, 2011.
  * [12] C. Liu, Y.-X. Guo, and S. Xiao, “Circularly polarized helical antenna for ism-band ingestible capsule endoscope systems,” _IEEE Trans. Antennas Propag._ , vol. 62, no. 12, pp. 6027–6039, 2014.
  * [13] J. Faerber, G. Cummins, S. K. Pavuluri, P. Record, A. R. A. Rodriguez, H. S. Lay, R. McPhillips, B. F. Cox, C. Connor, R. Gregson, R. E. Clutton, S. R. Khan, S. Cochran, and M. P. Y. Desmulliez, “In vivo characterization of a wireless telemetry module for a capsule endoscopy system utilizing a conformal antenna,” _IEEE Trans. Biomed. Circuits Syst._ , vol. 12, no. 1, pp. 95–105, 2018.
  * [14] K. Zhang, C. Liu, X. Liu, H. Cao, Y. Zhang, X. Yang, and H. Guo, “A conformal differentially fed antenna for ingestible capsule system,” _IEEE Trans. Antennas Propag._ , vol. 66, no. 4, pp. 1695–1703, 2018.
  * [15] H. Wang, Y. Feng, and Y. Guo, “A differentially fed antenna with complex impedance for ingestible wireless capsules,” _IEEE Antenn. Wireless Propag. Lett._ , vol. 21, no. 1, pp. 139–143, 2022.
  * [16] A. K. Skrivervik, M. Bosiljevac, and Z. Sipus, “Fundamental limits for implanted antennas: Maximum power density reaching free space,” _IEEE Trans. Antennas Propag._ , vol. 67, no. 8, pp. 4978–4988, 2019.
  * [17] X. Fang, M. Ramzan, Q. Wang, N. Neumann, X. Du, and D. Plettemeier, “Path loss models for wireless cardiac RF communication,” _IEEE Antenn. Wireless Propag. Lett._ , vol. 20, no. 6, pp. 893–897, Jun. 2021.
  * [18] D. Nikolayev, M. Zhadobov, P. Karban, and R. Sauleau, “Electromagnetic radiation efficiency of body-implanted devices,” _Phys. Rev. Applied_ , vol. 9, no. 2, p. 024033, Feb. 2018.
  * [19] S. Benaissa, L. Verloock, D. Nikolayev, M. Deruyck, G. Vermeeren, L. Martens, J. Govaere, F. Tuyttens, B. Sonck, D. Plets, and W. Joseph, “Propagation-loss characterization for livestock implantables at 433, 868, and 1400 MHz,” _IEEE Trans. Antennas Propag._ , vol. 69, no. 8, pp. 5166–5170, Aug. 2021.
  * [20] K. A. Psathas, A. P. Keliris, A. Kiourti, and K. S. Nikita, “Operation of ingestible antennas along the gastrointestinal tract: Detuning and performance,” in _Proc. 13th Int. Conf. Bioinform. Biomed. Eng._ , Chania, Greece, 2013, pp. 1–4.
  * [21] M. M. Suzan, K. Haneda, C. Icheln, A. Khatun, and K.-i. Takizawa, “An ultrawideband conformal loop antenna for ingestible capsule endoscope system,” in _Proc. 10th Eur. Conf. Antennas Propag. (EuCAP 2016)_ , Davos, Switzerland, 2016, pp. 1–5.
  * [22] D. Nikolayev, M. Zhadobov, and R. Sauleau, “Impact of tissue electromagnetic properties on radiation performance of in-body antennas,” _IEEE Antenn. Wireless Propag. Lett._ , vol. 17, no. 8, pp. 1440–1444, 2018.
  * [23] K. N. Bocan, M. H. Mickle, and E. Sejdić, “Simulating, modeling, and sensing variable tissues for wireless implantable medical devices,” _IEEE Trans. Microw. Theory Techn._ , vol. 66, no. 7, pp. 3547–3556, Jul. 2018.
  * [24] E. Cil, S. Dumanli, and D. Nikolayev, “Examination of impedance response of capsule-integrated antennas through gastrointestinal tract,” in _Proc. 16th Eur. Conf. Antennas Propag. (EuCAP 2022)_ , Madrid, Spain, 2022, pp. 1–5.
  * [25] D. Nikolayev, A. K. Skrivervik, J. S. Ho, M. Zhadobov, and R. Sauleau, “Reconfigurable dual-band capsule-conformal antenna array for in-body bioelectronics,” _IEEE Trans. Antennas Propag._ , vol. 70, no. 5, pp. 3749–3761, 2022.
  * [26] H. Chu, P.-J. Wang, X.-H. Zhu, and H. Hong, “Antenna-in-package design and robust test for the link between wireless ingestible capsule and smart phone,” _IEEE Access_ , vol. 7, pp. 35 231–35 241, 2019.
  * [27] D. Nikolayev, M. Zhadobov, L. Le Coq, P. Karban, and R. Sauleau, “Robust ultraminiature capsule antenna for ingestible and implantable applications,” _IEEE Trans. Antennas Propag._ , vol. 65, no. 11, pp. 6107–6119, 2017.
  * [28] F. El Hatmi, M. Grzeskowiak, D. Delcroix, T. Alves, S. Protat, S. Mostarshedi, and O. Picon, “A multilayered coil antenna for ingestible capsule: Near-field magnetic induction link,” _IEEE Antenn. Wireless Propag. Lett._ , vol. 12, pp. 1118–1121, 2013.
  * [29] M. Yousaf, I. B. Mabrouk, F. Faisal, M. Zada, Z. Bashir, A. Akram, M. Nedil, and H. Yoo, “Compacted conformal implantable antenna with multitasking capabilities for ingestible capsule endoscope,” _IEEE Access_ , vol. 8, pp. 157 617–157 627, 2020.
  * [30] M. K. Magill, G. A. Conway, and W. G. Scanlon, “Tissue-independent implantable antenna for in-body communications at 2.36–2.5 ghz,” _IEEE Trans. Antennas Propag._ , vol. 65, no. 9, pp. 4406–4417, 2017.
  * [31] Z. Bao, Y.-X. Guo, and R. Mittra, “Conformal capsule antenna with reconfigurable radiation pattern for robust communications,” _IEEE Trans. Antennas Propag._ , vol. 66, no. 7, pp. 3354–3365, 2018.
  * [32] D. Nikolayev, M. Zhadobov, and R. Sauleau, “Immune-to-detuning wireless in-body platform for versatile biotelemetry applications,” _IEEE Trans. Biomed. Circuits Syst._ , vol. 13, no. 2, pp. 403–412, Apr. 2019.
  * [33] A. Khaleghi, A. Hasanvand, and I. Balasingham, “Radio frequency backscatter communication for high data rate deep implants,” _IEEE Trans. Microwave Theory Techn._ , vol. 67, no. 3, pp. 1093–1106, Mar. 2019.
  * [34] _BodyCAP_ , July 2022. [Online]. Available: https://www.bodycap.fr/
  * [35] S. M. Mikki and Y. M. M. Antar, “A theory of antenna electromagnetic near field—part i,” _IEEE Trans. Antennas Propag._ , vol. 59, no. 12, pp. 4691–4705, 2011.
  * [36] _Rogers Corporation_ , July 2022. [Online]. Available: https://www.rogerscorp.com/advanced-electronics-solutions/clte-series-laminates/clte-mw-laminates
  * [37] D. Nikolayev, M. Zhadobov, R. Sauleau, and P. Karban, “Antennas for ingestible capsule telemetry,” in _Advances in Body-Centric Wireless Communication: Applications and State-of-the-Art_. London, UK: IET, 2016, pp. 143–186.
  * [38] O. O. Olaode, W. D. Palmer, and W. T. Joines, “Effects of meandering on dipole antenna resonant frequency,” _IEEE Antenn. Wireless Propag. Lett._ , vol. 11, pp. 122–125, 2012.
  * [39] P. M. Izdebski, H. Rajagopalan, and Y. Rahmat-Samii, “Conformal ingestible capsule antenna: A novel chandelier meandered design,” _IEEE Trans. Antennas Propag._ , vol. 57, no. 4, pp. 900–909, 2009.
  * [40] S. Gabriel, R. W. Lau, and C. Gabriel, “The dielectric properties of biological tissues: II. Measurements in the frequency range 10 Hz to 20 GHz,” _Phys. Med. Biol._ , vol. 41, pp. 2251–2269, 1996.
  * [41] _SPEAG Dielectric Assesment Kit_ , May 2022. [Online]. Available: https://speag.swiss/products/dak/overview/
  * [42] C. Gabriel, S. Gabriel, and E. Corthout, “The dielectric properties of biological tissues: I. Literature survey,” _Phys. Med. Biol._ , vol. 41, pp. 2231–2249, 1996.
  * [43] _Unité Expérimentale Physiologie et Phénotypage des Porcs_ , June 2022. [Online]. Available: https://www6.rennes.inrae.fr/ue3p/