denoted $Y=\\{y_{1},y_{2},\ldots,y_{M}\\}$, where $M>0$, and the observation
probabilities $P(y|x)$ are fixed for all time. The POMDP class they consider
is one where the observations are labels for disjoint partitions of $X$. Next,
some facts are presented using pictorial and simple counter arguments:

  1. 1.

Just confounding two states of an MDP can lead to an arbitrarily high absolute
loss in the return or cumulative infinite-horizon discounted payoff.

  2. 2.

In a POMDP the best stationary stochastic policy can be arbitrarily better
than the best stationary deterministic policy.

  3. 3.

The best stationary stochastic policy in a POMDP can be arbitrarily worse than
the optimal policy in the underlying MDP.

  4. 4.

In POMDPs the optimal policies can be non-stationary.

  5. 5.

In the class of POMDPs defined in Section 3, there need not be a stationary
policy that maximizes the value of each observation simultaneously.

  6. 6.

In the class of POMDPs defined in Section 3, there need not be a stationary
policy that maximizes the value of each state in the underlying MDP
simultaneously.

Under a stochastic policy $\bar{\mu}$, The value of a state $x$, can be
written as:

$V_{\bar{\mu}}(x)=\sum\limits_{u\in
U}Pr(u|\bar{\mu},x)[R(x,u)+\gamma\sum\limits_{x^{\prime}\in
X}P_{xx^{\prime}}(u)V_{\bar{\mu}}(x^{\prime})].$

Next, he defines the value of an observation:

$V_{\bar{\mu}}(y)=\sum\limits_{x\in X}P_{\bar{\mu}}(x|y)V_{\bar{\mu}}(x),$

where $P_{\bar{\mu}}(x|y)$ is called the asymptotic occupancy probability
distribution, which can be computed from $P(y|x),\leavevmode\nobreak\
P_{\bar{\mu}}(x)$ using Bayes’ rule, where $P_{\bar{\mu}}$ is the steady state
distribution. The authors take the standard TD($0$) algorithm, which is used
to evaluate a given policy, to now evaluate the value of an observation via a
TD($0$) like algorithm:

$V_{k+1}(Y_{k})=(1-\alpha(Y_{k}))V_{k}(Y_{k})+\alpha(Y_{k})(R_{k}+\gamma
V_{k}(Y_{k+1})).$

To make analysis possible, they consider, a fixed stationary persistent
excitation learning policy, i.e., a policy that assigns a non-zero probability
to every action in every state. They define a $Q$-value like quantity for
POMDPs with stochastic control $\bar{\mu}^{\prime}(y)$ as:

$Q_{\bar{\mu}}(y,\bar{\mu}^{\prime})=\sum\limits_{x\in
X}P_{\bar{\mu}}(x|y)Q_{\bar{\mu}}(x,\bar{\mu}^{\prime}),$

where,

$Q_{\bar{\mu}}(x,\bar{\mu}^{\prime})=R_{\bar{\mu}^{\prime}}(x)+\gamma\sum\limits_{x^{\prime}\in
X}P_{\bar{\mu}^{\prime}}(x,x^{\prime})V_{\bar{\mu}}(x^{\prime}).$

This paper demonstrated how to solve a POMDP without state estimation, by
defining a suitable stochastic policy, and showed that it can lead to
arbitrarily greater performance than a deterministic policy. Note also, that
now the policy space is infinite instead of finite. Nevertheless, we now have
a method to create value functions based on observations rather than states.
This approach may lead to a computationally fast partially observed multi-
agent control algorithm.

Next, consider the paper [35], which develops a number of heuristic MDP based
control strategies as well as a few others for a mobile robot navigation
problem in an office environment. For the review of this paper I am less
interested in the robot architecture and instead focus on the control
strategies that were developed as well as the reported results for the agent’s
effectiveness on the office environments under the different experimental
conditions. In these experiments a navigating robot must use the belief
framework discussed extensively before to reason about its state.

Briefly, I discuss constructing optimal policies before surveying the
heuristics developed. Once a belief state $\pi$ and control $u$ is obtained,
there are only $|\mathcal{Y}|$ possible next-stage beliefs, also known as
successor beliefs, denoted as $\pi^{\prime}$. We can define a state transition
function for the POMDP, where the state transitions are between belief-states
as
$\tau(\pi,u,\pi^{\prime})=\sum\limits_{\\{y\in\mathcal{Y}:T(\pi|y,u)=\pi^{\prime}\\}}\sigma(y|u,\pi),$
where $\sigma$ is the normalizing constant in the belief-state update formula.
And we can use the notation for belief cost as
$\rho(\pi,u)=\sum\limits_{x\in\mathcal{X}}\pi(x)c(x,u)$. Even though we have
converted this POMDP into an MDP, the known methods for MDPs only work for
finite state and action space, not continuous spaces. The methods that do
exist for solving the belief MDP can only solve small scale MDPs with 10
states and 10 observations.

Now, we are in a position to discuss heuristic strategies, which the
intractability of the complete POMDP problem motivates. He develops a Maximum
Likelihood state estimator approach
$\mu_{ML}(\pi)=\mu^{*}(\arg\max_{i}\pi(i))$. This paper is worthwhile to
review because one could in future research investigations compare the
effectiveness of other reduction to MDP methods I have thought of, e.g., the
floored mean-state estimator. Also, all of these types of approximations can
be applied and studied in a multi-agent control setting, to significantly
speed up learning. Many other kinds of reduction to MDP approximations could
be compared in an empirical study too that I may have missed in a multi-agent
control setting.

Another idea for future experiments would be to compare these methods with
some constraints on periodically updating the belief, and then running VIA
from the MDP context. This would be a kind of optimistic value iteration or
policy iteration from the POMDP point of view. In the current paper, however
the most likely state(MLS) approach selects the control which optimizes the
cost-to-go from the state which has the maximum probability in the current
belief-state. This takes advantage of the stored optimal policy for the
completely known MDP optimal policy $\mu^{*}$.

The next heuristic is a voting type method. With a belief-state in hand,
denote the optimal action probability by
$w_{u}(\pi)=\sum\limits_{x\in\mathcal{X}}\pi(x)\mathbf{1}(\mu^{*}(x)=u)$,
where an indicator function has been used. Then, the most likely optimal
control is selected by:

$\mu_{\textbf{vote}}(\pi)=\arg\max\limits_{u}w_{u}(\pi).$

The $Q$-MDP method is reviewed more fully in the next paper [36], but the form
of the equation is noted here for completeness of the current paper.

$\mu_{Q_{\textbf{MDP}}}(\pi)=\arg\max\limits_{u}(\sum_{x}\pi(x)Q(x,u)).$

This method is more refined than the voting method, as it utilizes the Q
function information and the belief-state information. But as discussed
before, it is not the best when there is a lot of uncertainties involved in
future situations.

Next, and I think this could be useful in RL exploration contexts,
particularly for multi-agent control settings, is formulating an entropy
definition using the belief-state, and using that to drive the policy
construction. That is this method more accurately accounts for different
uncertainties in the navigating robot’s actions, for example. This method
allows agents to explore different controls to obtain more information. Define
the entropy of the belief-state $\pi$ as
$H(\pi)=-\sum\limits_{x}\pi(x)\log(\pi(x))$, where $\pi(x)\log(\pi(x))=0$ if
$\pi(x)=0$. The higher this value the more uncertainty, and conversely the
lower, the more certain the robot is about it’s actions for meeting its
objectives. Next, the author defines the expected entropy as

$EE(u,\pi)=\sum\limits_{\pi^{\prime}}\tau(\pi,u,\pi^{\prime})H(\pi^{\prime}).$

An interesting extension of this idea would be to consider sequences of
actions and entropy sequences of some kind to utilize more stochastic methods.
This is an open research direction. Also, perhaps an interesting application
of this methodology for multi-agent control would be to come up with some time
optimization criterion of using expected entropy for some time horizon, and
then using $Q$-MDP for the agents in the remaining time of the optimal control
problem.

The next method that is developed uses this entropy definition to define a
split policy that takes actions to minimize entropy if the entropy in the
belief-state is too high, and conversely take the action that maximizes the
voting likelihood if the entropy is below a certain level. The action entropy
policy is $\arg\max\limits_{u}w_{u}(\pi)$ if $H(w_{u}(\pi))<\phi$, where
$\phi$ is the threshold. Otherwise, $\arg\min\limits_{u}EE(u,\pi)$. Lastly, we
can use an entropy-weighting (EW) approach that balances the two goals just
discussed, rather than pursuing either exclusively, weighting each of these
aims with a normalized form of entropy. The normalized entropy of a belief-
state is defined as $\tilde{H}(\pi)=(\frac{H(\pi)}{H(unif)})^{k}$, where unif
is the uniform pmf, and $k$ is a power that controls the relative weighting of
the entropy, thus yielding a useful measure in the compact interval $[0,1]$.
The entropy definitions discussed are used to derive new Q-values and a new
policy called $\mu_{EW}(\pi)=\arg\max\limits_{u}E[Q(\pi,u)]$. See the paper
for more on these definitions. Note the issue for exploration for multi-agent
control has not been fully addressed in the literature.

Now, I present the lessons learned from these methods on the mobile robot
navigation problem. These methods were tested in simulation on four different
configurations of an office environment with different initial conditions. For
these environments, a reward of 1 is given once the agent uses the control
declare-goal in the goal state, and a reward of 0 is assigned for every other
state-control pair. All episodes were 300 steps long or terminated once the
point was earned. All results were averaged over 250 trials. It was found that
the MLS method was the most robust across the different settings, illustrating
how essential and effective the belief-state info is by itself for determining
the optimal policy. The $Q$-MDP method did not do well when it was uncertain
in it’s starting state. In the final tested scenario, the initial distribution
was uniform, so the entropy was maximized. For this scenario, the voting and
$Q$-MDP methods did not fare well. In these domains, a reward of 1 is given
for performing the action declare-goal in the desired goal state, and 0 for
every other state-action pair.

The next paper’s [36] main idea is to learn a POMDP policy based on the
Q-function.

$\mu_{Q_{MDP}}=\arg\min_{u}\sum_{i}\pi(i)Q^{*}(i,u),$

where here the Q function is used for cost minimization. In connection with
the paper [34] on POMDPs and $Q$-learning , here the belief-state is used in
coming up with a policy for the POMDP, while before no costly state estimation
was required.

This paper explores approximate methods for finding near optimal POMDP
policies, but with the added goal of working within larger state-spaces. The
paper reviews several approximation methods for various POMDP problem sizes
and shows the different capabilities of each method. The paper explores the
theme of promise and practice, in that the optimality of the policy may not
have to be sacrificed much in order to solve more challenging problems. RL
techniques are developed using insights from the POMDP community. Their
algorithm is successfully scaled up to have a hundred states and dozens of
observations. Other assumptions made include knowledge of the transition
dynamics, and the goal is to find a policy capable of achieving the optimal
return. Some concessions are made. The first is that it is fine to have a sub-
optimal policy as long as it is close to optimal. Secondly, the problems are
all solved and compared from one initial distribution over the states in
simulation.

Now, I describe the various solution methods used in this paper and overview
their strengths and weaknesses before discussing the successes and failures
from the experiments. All methods perform reasonably well in the small
domains, but the one dubbed $Q$-MDP performs most consistently. None of the
approaches perform well on the two larger problems that are tested. This
prompts development of hybrid approaches. The motivation for their algorithms
comes from approximating the $Q$-function over the belief-space, and using
this to find rewarding controls in the environment. The first method is a
truncated form of approximation to the exact VIA methods already discussed by
using the finite set of vectors built from learning. The main issue that
motivates this and others is that the cardinality of the set of alpha vectors
used to approximate the $Q$-function can be exponentially complex from
iteration to iteration.

The $Q$-MDP value method is really the core algorithm of this paper, but there
are a few other interesting successful algorithms developed. This method uses
the $Q$-function computed from the underlying MDP based on the known problem
parameters. This approach has been discussed in other papers already surveyed
so it is a widely accepted approximation method; this would be a good
approximation scheme candidate for the multi-agent control setting. Once we
have the $Q$-function from the MDP denoted $Q_{MDP}$, we compute the
$Q$-function with belief-state as argument as
$Q_{\pi}(u)=\sum\limits_{x}\pi(x)Q_{MDP}(x,u)$. This method has the drawback
that it will not take exploratory controls because it considers all
uncertainty to exist for the current stage. Despite this aspect of the
approximation, this method has been effective in practice on moderate to large
state-control spaces.

The final algorithm in this section is called Replicated Q-Learning, explored
in [29]. In that paper, they also had to learn the model because they are
explicitly RL model-free. The replicated Q-learning algorithm uses one vector
$q_{u}$ to approximate the $Q$-function for every control $u$ as
$Q_{\pi}(u)=q_{u}\cdot\pi$. The $q_{u}$ vector’s elements are updated using
the formula:

$q_{u}(x)=q_{u}(x)+\alpha\pi(x)[r+\gamma\max\limits_{u^{\prime}}Q_{\pi^{\prime}}(u^{\prime})-q_{u}(x)].$

The update is applied to every $x\in\mathcal{X}$. The learning rate is
$\alpha$. The reward is denoted as $r$, the belief-state is denoted by $\pi$,
the control is denoted by $u$, and the successor belief-state is denoted by
$\pi^{\prime}$.

The $Q$-learning rule is applied element wise to every component of $q_{u}$,
multiplied with corresponding weight from the belief-state. Once a sequence of
belief-states is obtained the learning rule could be applied, for every pair
of belief-states. The update becomes the MDP $Q$-learning rule whenever
$\pi(x)=1$ for some $x$. This learning rule applies the $Q$-learning algorithm
to each component of $q_{u}$, weighted by the corresponding component of the
belief-state.

The next algorithm developed in the paper is Linear $Q$-learning, which has
slightly different learning dynamics from Replicated Q-learning. Instead of
adjusting the q-vector evaluated at a state, it adjusts the linear predictor
$q_{u}\cdot\pi$ as follows:

$q_{u}(x)=q_{u}(x)+\alpha\pi(x)[r+\gamma\max\limits_{u^{\prime}}Q_{\pi^{\prime}}(u^{\prime})-q_{u}\cdot\pi].$

Similar to the previous algorithm, this algorithm will collapse to the
$Q$-learning rule when the belief-state has probability one for only one
state. The main limitation of Linear $Q$-learning and the previous algorithm
is that they can only learn linear approximations to the true $Q$-function.
For the small environments tested, it did not appear to be the case that the
policies were poor.

Comparing these algorithms on a range of environments reveals different
strengths and weaknesses. In every simulation the agent had the same initial
belief-state, and the time horizon was 101 stages long. For the small
environments it was the case that the truncated exact VIA had almost identical
performance to the exact VIA, and appeared to perform slightly better than the
$Q$-MDP algorithm. The $Q$-MDP performed consistently well and was the most
time efficient of the group of algorithms. The last two learning algorithms
were the slowest at learning.

The next set of experiments looked at environments with 57 states, 21
observations, 4 controls and 89 states, 17 observations, and 5 controls,
respectively. To handle these larger POMDPs a hybrid approach to the design of
algorithms was considered. Note that none of the algorithms fared well in the
larger POMDP setting. This suggested to the authors the possibility of
attempting a hybrid solution. One that was tried was computing the $Q$-MDP
function and seeding the q-vectors for the learning algorithm. The Linear
$Q$-learning algorithm almost doubled its chance of reaching the goal state,
and eliminated half the steps required to reach the goal state. Because the
navigation environments where so complex, that excluded direct comparison with
exact methods.

Nevertheless, this hybrid strategy improved the performance of the algorithms.
The authors have called for further improved algorithm design. The main
discovery of poor performance of the $Q$-MDP algorithm was that, the agent can
end up choosing a stay in place action that forced it in a cycle at a specific
belief-state. To conclude this section of the paper I quote, Seeding linear
Q-learning using the $Q$-MDP values leads to a promising method of solving
larger POMDP’s than have been addressed to date. More study is needed to
understand the strengths and limitations of this approach.. More variants of
these POMDP approximation methods could be tried on some of the different
test-beds mentioned. Particularly, development of POMDP approximation methods
for continuous state and control spaces would be interesting, and could be
studied under the game theory testbed discussed previously.

Finally, a call for more advanced representations was proposed by the authors.
While piece-wise linear convex functions can approximate any optimal
$Q$-function, the linear representation has no such guarantee. Hence different
ideas are welcome for solving this problem of good representation of the
optimal Q-function that is easy to compute and time-efficient. To me, this is
a big open area of research, and the first experiment would be to try a new
algorithm called Quadratic $Q$-learning, that uses a quadratic basis, possibly
with linear and bias terms as well; other sets of basis functions could be
compared on the performance of various sized POMDP learning tasks. In closing,
the authors proposed a PWLC Q-learning algorithm that maintains a set of
vectors for every possible control and uses an update rule based on
competition between the vectors. It goes as follows. Essentially, the belief-
state dotted with the $q$-vector that produces the largest value is used for
updating. The updating rule used is the linear Q-learning rule. The hope is
that this approximation allows a better coverage of the state-space then is
possible with a single vector representation for the linear function. They
tested this algorithm with three q-vectors per action. When a new belief-
state, value pair arrives, the $q$ -vector with the largest dot product is
used for updating.

##  6 Conclusion

In conclusion we have studied POMDPs and the main ways of developing
approximate control strategies for them; however, there are many more possible
modelling variations that need to be researched for the POMDP and its
approximation. Now I list a few of the possible research directions from here
for approximate methods for POMDPs: exploration strategies in POMDPs, applying
these approximate POMDP strategies in multi-agent control settings and
developing guarantees for such multi-agent systems. Information theory should
help out or be a starting point for developing useful exploration strategies
and may lead to even better approximate control strategies. For the
approximate methods for POMDPs covered in this survey, those methods could be
extended to multi-agent Markov decision processes (MMDPs), stochastic games
(SGs), or Decentralized POMDPs (Dec-POMDPs).

## References

  * [1] D. P. Bertsekas, _Dynamic Programming and Optimal Control: $4$th and earlier editions_. Scientific, Athena, vol. 1.
  * [2] ——, _Dynamic Programming and Optimal Control: $4$th and earlier editions_. Scientific, Athena, vol. 2.
  * [3] V. Krishnamurthy, _Partially Observed Markov Decision Processes_. Cambridge University Press, 2016.
  * [4] A. R. Cassandra, “A Survey of POMDP Applications,” in _Working notes of AAAI 1998 fall symposium on planning with partially observable Markov decision processes_ , vol. 1724, 1998.
  * [5] C. M. Bowyer, J. M. Shea, and T. F. Wong, “Optimizing Timing Synchronization Times for Distributed Tracking of a Mobile Asset in GPS-denied Environments,” 2021, unpublished.
  * [6] A. W. Drake, “Observation of a Markov Process Through a Noisy Channel,” Ph.D. dissertation, Massachusetts Institute of Technology, 1962.
  * [7] C. Bowyer, D. Greene, T. Ward, M. Menendez, J. Shea, and T. Wong, “Reinforcement learning for mixed cooperative/competitive dynamic spectrum access,” in _2019 IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN)_. IEEE, 2019, pp. 1–6.
  * [8] T. F. Wong, T. Ward, J. M. Shea, M. Menendez, D. Green, and C. Bowyer, “A Dynamic Spectrum Sharing Design in the DARPA Spectrum Collaboration Challenge,” in _Proceedings of the Government Microcircuit Applications and Critical Technology Conference (GOMACTech)_ , 2020.
  * [9] R. D. Smallwood and E. J. Sondik, “Optimal Control of Partially Observable Markov Processes over a Finite Horizon,” _Operations Research_ , vol. 21, no. 5, pp. 1071–1088, 1973.
  * [10] E. V. Denardo, “Contraction Mappings in the Theory Underlying Dynamic Programming,” _Siam Review_ , vol. 9, no. 2, pp. 165–177, 1967.
  * [11] E. J. Sondik, “The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs,” _Operations Research_ , vol. 26, no. 2, pp. 282–304, 1978.
  * [12] G. E. Monahan, “State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms,” _Management Science_ , vol. 28, no. 1, pp. 1–16, 1982.
  * [13] R. L. Stratonovich, “Conditional Markov Processes,” in _Non-linear transformations of stochastic processes_. Elsevier, 1965, pp. 427–453.
  * [14] E. Dynkin, “Controlled Random Sequences,” _Theory of Probability & Its Applications_, vol. 10, no. 1, pp. 1–14, 1965.
  * [15] K. J. Åström, “Optimal Control of Markov Processes with Incomplete State Information,” _Journal of Mathematical Analysis and Applications_ , vol. 10, no. 1, pp. 174–205, 1965.
  * [16] S. M. Pollock, “A Simple Model of Search for a Moving Target,” _Operations Research_ , vol. 18, no. 5, pp. 883–903, 1970.
  * [17] J. N. Eagle, “The Optimal Search for a Moving Target when the Search Path is Constrained,” _Operations research_ , vol. 32, no. 5, pp. 1107–1115, 1984\.
  * [18] S. Singh and V. Krishnamurthy, “The Optimal Search for a Markovian Target when the Search Path is Constrained: the Infinite-Horizon Case,” _IEEE Transactions on automatic control_ , vol. 48, no. 3, pp. 493–497, 2003.
  * [19] R. A. Howard, “Dynamic Probabilistic Systems: Markov Processes, Vol. I John Wiley & Sons,” _Inc., New York_ , 1971.
  * [20] D. Blackwell, “Discounted Dynamic Programming,” _The Annals of Mathematical Statistics_ , vol. 36, no. 1, pp. 226–235, 1965.
  * [21] R. Bellman, “Dynamic Programming,” _Press Princeton, New Jersey_ , 1957\.
  * [22] E. V. Denardo, _Sequential Decision Processes_. Northwestern University, 1965.
  * [23] A. Maitra, “Discounted Dynamic Programming on Compact Metric Spaces,” _Sankhyā: The Indian Journal of Statistics, Series A_ , pp. 211–216, 1968\.
  * [24] J. S. Kakalik, “Optimum Policies for Partially Observable Markov Systems,” MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER, Tech. Rep., 1965\.
  * [25] J. K. Satia, “Markovian Decision Processes with Uncertain Transition Matrices or/and Probabilistic Observation of States.” 1969.
  * [26] E. J. Sondik, _The Optimal Control of Partially Observable Markov Processes_. Stanford University, 1971\.
  * [27] J. E. Eckles, “Optimum Maintenance with Incomplete Information,” _Operations Research_ , vol. 16, no. 5, pp. 1058–1067, 1968.
  * [28] A. R. Cassandra, L. P. Kaelbling, and M. L. Littman, “Acting Optimally in Partially Observable Stochastic Domains,” in _AAAI_ , vol. 94, 1994, pp. 1023–1028.
  * [29] L. Chrisman, “Reinforcement Learning with Perceptual Aliasing: The Perceptual Distinctions Approach,” in _AAAI_ , vol. 1992. Citeseer, 1992, pp. 183–188.
  * [30] W. S. Lovejoy, “A Survey of Algorithmic Methods for Partially Observed Markov Decision Processes,” _Annals of Operations Research_ , vol. 28, no. 1, pp. 47–65, 1991.
  * [31] A. R. Cassandra, M. L. Littman, and N. L. Zhang, “Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes,” _arXiv preprint arXiv:1302.1525_ , 2013.
  * [32] C. M. Bowyer, “Improving Generalization in Mountain Car Through the Partitioned Parameterized Policy Approach via Quasi-Stochastic Gradient Descent,” _arXiv preprint arXiv:2105.13986_ , 2021.
  * [33] R. Parr and S. Russell, “Approximating Optimal Policies for Partially Observable Stochastic Domains,” in _IJCAI_ , vol. 95, 1995, pp. 1088–1094.
  * [34] S. P. Singh, T. Jaakkola, and M. I. Jordan, “Learning Without State-Estimation in Partially Observable Markovian Decision Processes,” in _Machine Learning Proceedings 1994_. Elsevier, 1994, pp. 284–292.
  * [35] A. R. Cassandra, L. P. Kaelbling, and J. A. Kurien, “Acting Under Uncertainty: Discrete Bayesian Models for Mobile-Robot Navigation,” in _Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. IROS’96_ , vol. 2. IEEE, 1996, pp. 963–972.
  * [36] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling, “Learning Policies for Partially Observable Environments: Scaling up,” in _Machine Learning Proceedings 1995_. Elsevier, 1995, pp. 362–370.


# Heart Murmur and Abnormal PCG Detection via Wavelet Scattering Transform & a
1D-CNN

Ahmed Patwa, M. Mahboob Ur Rahman, and Tareq Al-Naffouri Authors are with the
Department of Electrical Engineering, KAUST, KSA.

###### Abstract

This work leverages deep learning (DL) techniques in order to do automatic and
accurate heart murmur detection from phonocardiogram (PCG) recordings. Two
public PCG datasets (CirCor Digiscope 2022 dataset and PCG 2016 dataset) from
Physionet online database are utilized to train and test three custom neural
networks (NN): a 1D convolutional neural network (CNN), a long short-term
memory (LSTM) recurrent neural network (RNN), and a convolutional RNN (C-RNN).
Under our proposed method, we first do pre-processing on both datasets in
order to prepare the data for the NNs. Key pre-processing steps include the
following: denoising, segmentation, re-labeling of noise-only segments, data
normalization, and time-frequency analysis of the PCG segments using wavelet
scattering transform. We note that the segmentation step results in a number
of noise-only segments; thus, we re-label the noise-only segments. Further, we
do exhaustive search to find optimal segment length (which turns out to be 4
sec).

To evaluate the performance of the three NNs we have implemented, we conduct
four experiments, first three using PCG 2022 dataset, and fourth using PCG
2016 dataset. It turns out that our custom 1D-CNN outperforms other two NNs
(LSTM-RNN and C-RNN) as well as the state-of-the-art. Specifically, for
experiment E1 (murmur detection using original PCG 2022 dataset), our 1D-CNN
model achieves an accuracy of 82.28%, weighted accuracy of 83.81%, F1-score of
65.79%, and and area under receive operating charactertic (AUROC) curve of
90.79%. For experiment E2 (mumur detection using PCG 2022 dataset with unknown
class removed), our 1D-CNN model achieves an accuracy of 87.05%, F1-score of
87.72%, and AUROC of 94.4%. For experiment E3 (murmur detection using PCG 2022
dataset with re-labeling of segments), our 1D-CNN model achieves an accuracy
of 82.86%, weighted accuracy of 86.30%, F1-score of 81.87%, and AUROC of
93.45%. For experiment E4 (abnormal PCG detection using PCG 2016 dataset), our
1D-CNN model achieves an accuracy of 96.30%, F1-score of 96.29% and AUROC of
98.17%.

###### Index Terms:

phonocardiogram, heart murmur, valvular heart disease, physionet,
convolutional neural network, recurrent neural network, wavelet scattering.

##  I Introduction

Cardiac auscultation provides valuable insights into the mechanical activity
of heart, and remains the gold standard for diagnosis of a wide range of
cardiovascular diseases. Phonocardiogram (PCG)—the systematic recording of
heart sounds by means of a digital stethoscope, is a clinically significant
method to study the pathology of the four heart valves (i.e., the mitral
valve, tricuspid valve, aortic valve, and pulmonary valve). This is because
the PCG could record abnormal sounds, known as heart murmurs, made by heart
valves as they open and close during cardiac cycle. Heart murmurs, when
present, often indicate the presence of a heart valve disease, e.g., mitral
regurgitation, mitral stenosis, congenital heart disease, septal defects,
patent ductus arteriosus in newborns, defective cardiac valves, rheumatic
heart disease, etc [1]. Thus, early murmur detection, classification, and
grading analysis in an automated fashion to help diagnose a valvular heart
disease at an early stage is the need of the hour [2].

PCG signal acquisition is done from following four chest locations where the
valves can be best heard: Aortic area, Pulmonic area, Tricuspid area, and
Mitral area [3]. For a normal sinus cardiac cycle, the PCG signal captures two
fundamental heart sounds, first is called S1 sound while second is called S2
sounds. S1 signifies the start of isovolumetric ventricular contraction with
the closing of the mitral and tricuspid valves amid rapid increase in pressure
within the ventricles. S2, on the other hand, implies the start of diastole
with the closing of the aortic and pulmonic valves. In addition to S1 and S2
sounds, the mechanical activity of the heart may occasionally give rise other
sounds which include: third heart sound (S3), the fourth heart sound (S4),
systolic ejection click (EC), mid-systolic click (MC), diastolic sound or
opening snap (OS), and heart murmurs (due to turbulent flow of blood due to
malfunctioning of heart valves) [4].

PCG signal analysis for abnormal heart beat detection and for murmur detection
has traditionally been done using classical signal processing techniques [5].
More recently, there has been enormous interest in utilizing tools from
machine learning [6], deep learning [7], and transfer learning [8] in order to
do heart sounds classification (see the review articles [1],[2], and
references therein for more in-depth discussion of the related work).

Contributions. Inline with the recent surge of interest in utilizing deep
learning methods for PCG signal analysis, this work utilizes two public PCG
datasets (PCG 2022 dataset and PCG 2016 dataset) from Physionet database [9]
to train and test three custom neural networks (NN), i.e., 1D-CNN, LSTM-RNN,
C-RNN for heart murmur and abnormal PCG detection. We first pre-process the
data in order to split each PCG signal into smaller segments using a custom-
designed GUI framework. We systematically identify the noise-only segments and
re-label them, and do exhaustive search to determine optimal segment size. We
conduct four experiments to evaluate the performance of our NN models on
following four datasets: 1) PCG 2022 dataset as is, 2) PCG 2022 dataset with
unknown class removed, 3) PCG 2022 dataset with re-labeled segments, and 4)
PCG 2016 dataset. We note that our 1D-CNN model outperforms the other two NN
models (i.e., LSTM-RNN and C-RNN), as well as the state-of-the-art methods for
murmur detection.

Outline. The rest of this paper is organized as follows. Section II describes
selected related work on murmur detection and heart valve disease
classification. Section III outlines essential details of the two public
datasets used, pre-processing done, and time-frequency domain methods for
feature extraction. Section IV presents three deep learning classifiers for
murmur detection and abnormal PCG detection. Section V discusses performance
results for all three classifiers for both datasets. Section VI concludes the
paper.

##  II Related Work

Broadly speaking, the relevant literature on PCG signal analysis has attempted
to solve following major problems, to date: i) identification of fundamental
heart sounds (S1 and S2) [10], ii) abnormal PCG detection (by identifying
sounds other than the normal lub-dub sound) [11], iii) heart sound
classification (normal sounds, murmurs, extra clicks, artifacts) [12], iv)
heart murmur detection [13], v) heart valve disease classification (by means
of heart murmur classification) [14], and vi) PCG signal denoising methods
[15]. Lately, there is a work which attempts to do automatic murmur grading
analysis [16] at the patient-level, and has the potential to do disease
staging and progression analysis.

In terms of public datasets, apart from PCG 2022 dataset [3] and PCG 2016
dataset [4] that are available on Physionet database, there are a few other
public datasets too. These include: EPHNOGRAM [17], PASCAL, Michigan heart
sound and murmur database (MHSDB) provided by the University of Michigan
health system, and cardiac auscultation of heart murmurs database provided by
eGeneral Medical Inc. [4]. On a side note, fetal PCG dataset provides 26
recordings of fetal PCG collected from expecting mothers with singleton
pregnancy during their last trimester [18].

Since this work focuses mainly on automatic heart murmur and abnormal PCG
detection, selected work on these two problems is discussed as follows. [19]
utilizes PCG 2016 dataset, applies multiple time-frequency analysis methods,
e.g., discrete wavelet transform, mel-frequency cepstral coefficients etc.,
along with a feedforward neural network in order to do abnormal PCG detection,
achieving 97.1% accuracy. [20] computes short time Fourier transform of the
PCG signals without doing any segmentation, implements a custom CNN, and
achieves an accuracy of 95.4%, and 96.8%, on PCG 2016 dataset and PASCAL
dataset, respectively. [21] utilizes two PCG datasets to evaluate their custom
CNN model, as well as two pre-trained models (i.e., VGGNet-16, ResNet-50) in
order to do heart valve disease (HVD) classification. They claim to achieve an
overall accuracy of 99% to classify the following HVD: aortic stenosis, mitral
stenosis, aortic regurgitation, mitral regurgitation, and mitral valve
prolapse. [22] utilized a private dataset (with data collected at PKU
Muhammadiyah Yogyakarta Hospital, Indonesia), and implemented a custom CNN
model in order to HVD classification for the following diseases: angina
pectoris, congestive heart failure, and hypertensive heart disease. They
reported an accuracy of 85% for their HVD classification problem. [23] aimed
at intelligent diagnosis of murmurs in pediatric patients with congenital
heart disease. They applied segmentation method to extract the first and
second heart sounds from the PCG signals, and used them as input to their
feedforward neural network classifier, resulting in HVD detection accuracy of
93%. [24] utilizes the PASCAL dataset and aims to classify PCG signals into
three classes (normal, systolic murmur, diastolic murmur). To this end, they
extract various time-domain features, frequency-domain features, and
statistical features, and pass them to three classifiers: k-NN, fuzzy k-NN and
a feedforward neural network. They report a classification accuracy of 99.6%,
that is achieved by the fuzzy k-NN. [25] utilizes the PCG 2016 dataset,
extracts time-domain, frequency-domain, and time-frequency domain features
from the PCG signals, and implements an ensemble of 20 feedforward neural
networks in order to do abnormal PCG detection, achieving an overall accuracy
of 91.5%. Finally, [26] utilizes the PCG 2016 dataset, extracts time-domain,
frequency-domain and time-frequency domain features, does feature selection
and implements a two-layer feedforward neural network for abnormal PCG
detection, resulting in an accuracy of 85.2%.

##  III Datasets, Pre-processing & Feature Extraction

This work utilized two PCG datasets: 1) CirCor Digiscope PCG dataset from
PhysioNet 2022 challenge (called PCG 2022 dataset, in this work) [27], 2) PCG
dataset from PhysioNet 2016 challenge (called PCG 2016 dataset, in this work).
Below, we describe the key details of the two datasets, followed by the key
pre-processing steps performed on each dataset, followed by feature extraction
by means of various time-frequency analysis methods.

###  III-A Datasets

1) CirCor Digiscope PCG dataset from PhysioNet 2022 challenge:

This dataset is a collection of PCG signals collected from pediatric subjects
during the two mass screening campaigns in Brazil. The dataset consists of
3,163 audio files, collected from 942 patients, sampled at 4,000 Hz. The
length of these recordings vary between 5 seconds to 65 seconds. These PCG
recordings have been taken from one or more of 4 possible locations on the
chest, namely: AV, MV, PV, TV (see Fig. 1). Additionally, some samples have
been taken at another location, labeled as Phc. Moreover, some subjects had
multiple recordings for the same chest location. Murmur labels are given both
patient-wise, or chest-location-wise. This implies that we could get to know
whether a patient has murmur or not, as well as if the dataset annotator
detected murmur in each recording separately. In this work, we go by chest-
location-wise murmur detection.

Figure 1: Cardiac auscultation locations: AO = aortic area; LV = left
ventricle; PA = pulmonary area; RV = right ventricle; 1 = right second
intercostal space; 2 = left second intercostal space; 3 = midleft sternal
border (tricuspid); 4 = fifth intercostal space, midclavicular line. [3]

In addition to the audio PCG data, following meta-data is also available: age,
weight, and gender of the pediatric subject. Furthermore, additional
information about heart murmurs such as the location of a murmur, strength of
a murmur is also given. Having said that, this work utilizes the CirCor
Digiscope 2022 dataset for murmur detection, i.e., we solve a classification
problem with following three classes: 1) murmur present, 2) murmur absent, and
3) unknown (noisy, unknown to the annotator).

2) PCG dataset from PhysioNet/CinC 2016 challenge:

The PhysioNet/CinC challenge 2016 dataset consists of a total of 3,240 heart
sound recordings, sampled at 2,000 Hz. The length of these recordings vary
between 5 seconds to 120 seconds. All the data was recorded from a single
precordial location on the chest. As for the labels, each recording has been
annotated as normal (taken from a healthy subject) or abnormal (taken from
subjects with confirmed cardiac diagnosis). Furthermore, each recording has
been labeled as either high-quality or low quality. Moreover, some of the data
belonging to abnormal class has been further annotated with the exact
diagnosis that the subject suffers from. There are a total of 2,575 recordings
for the normal class, while there are a total of 665 recordings for the
abnormal class. Thus, the data is highly imbalanced given the number of
examples for the normal and abnormal class, and this effect is more pronounced
when it comes to disease labels (within the abnormal class).

We utilize PCG 2016 dataset to solve the classification problem with two
classes: 1) PCG normal, 2) PCG abnormal. One important difference between this
dataset and the CirCor Digiscope dataset is that this dataset assigns normal
labels even to the low-quality recordings. Thus, these recordings could still
be used for the classification problem (PCG normal vs. PCG abnormal), without
adding a third class for low-quality recordings.

Table I summarizes the key statistics of the two datasets.

TABLE I: Key statistics of the two datasets |  CirCor Digiscope dataset 2022 |  PhysioNet/CinC challenge dataset 2016
---|---|---
Total recordings |  3,163 |  3,240
Recordings per class |  Absent: 2,391, Present: 616, Unknown: 156 |  Normal: 2,575, Abnormal: 665
Total subjects |  942 |  -
Sampling rate |  4,000 Hz |  2,000 Hz
Recordings lengths |  (5-65) seconds |  (5-120) seconds
Auscultation locations |  AV, TV, MV, PV, Phc |  Single chest location

###  III-B Data Pre-Processing

Denoising: Both datasets have noise overlapping with heartbeats. Some
prominent examples of noise in the two datasets include: noise due to
stethoscope movement, baby crying, intense breathing, and people talking.
Since the spectrums of voice and PCG overlap, complete elimination of noise is
not possible. However, out-of-band (OOB) noise rejection is still possible. To
this end, a low-pass filter with a cut-off frequency of 300 Hz (chosen by
experimentation) has been applied to each PCG signal to remove the OOB noise.

Segmentation: Since recordings are not of the same length, each recording has
been divided into $N$-second long segments111The optimal segment length turns
out to be $N=4$, as will be discussed in Section V in more detail., to
increase the number of training examples for the deep learning model. Thus,
for PCG 2016 dataset, we end up with 12,827 PCG segments for the normal class
and 3,922 PCG segments for the abnormal class. To deal with the problem of
highly imbalanced dataset, a balanced subset is constructed by including all
the PCG segments from the abnormal class, while randomly selecting PCG
segments from the normal class. This way, each of the two classes contain a
total of 7,844 audio files (segments). The same process is repeated for the
CirCor Digiscope 2022 dataset, where a total of 16,522 segments were
extracted. We then utilized 6,571 files to construct as a more-balanced
dataset as follows: 3,579 files from murmur absent class, 2,593 files from
murmur present class, and 399 samples from the unknown class.

Re-labeling of noise-only segments:  The splitting of a PCG time-series into
multiple smaller segments results in a new problem (i.e., how to assign labels
to each segment). Note that a label (murmur present, murmur absent, unknown)
was assigned to each recording as a whole by the annotator in the original
dataset. However, when dividing a PCG signal into smaller segments, a
situation arises where some segments are bad segments (i.e., they contain only
noise, with no heartbeat at all!). If left untreated, feeding such noise-only
segments to the deep learning model could have a negative impact on its
performance. That is, the model will consider one such segment as representing
a murmur. But in reality, the segment contains pure noise, and thus, should
ideally be labeled as an unknown sample. Thus, to deal with this problem, a
systematic method for assessment and re-labeling of each segment of the CirCor
2022 dataset is needed.

Graphical user interface for segment assessment and potential re-labeling: To
this end, we developed a simple graphical user interface (GUI) in Python, in
order to assess the quality of the default label for each segment in order to
re-label all the noise-only segments, in a semi-automated fashion (see Fig.
2). Specifically, the GUI of Fig. 2 shows the 2D time-frequency domain
representation of each segment, as well as plays the audio. This allows us to
systematically determine the presence or absence of heart beat in each
segment, for all PCG files. Note that the re-labeling process made sure not to
alter the integrity of the dataset. Specifically, the only allowed change was
to re-label (murmur present) to (unknown), or (murmur absent) to (unknown)
indicating that a certain segment of a whole recording doesn’t actually
represent a heartbeat signal, but rather contains only noise. In other words,
no (murmur present) was changed to (murmur absent) or the other way around.
Similarly, no (unknown) was changed to (murmur present) or (murmur absent).
This exercise helped us identify the bad segments, which in turn helped us
improve the training accuracy of our proposed DL classifiers. The resulting
new distribution of the three classes (murmur present, murmur absent, and
unknown) is summarized in Table II.

Figure 2:  Graphical user interface for guided re-labeling of dataset segments.  TABLE II: CirCor Digiscope 2022 dataset: new distribution of the three classes after segment re-labeling | Class
---|---
|  Absent |  Present |  Unknown
Before re-labeling |  3,579 |  2,593 |  399
After re-labeling |  2,501 |  2,438 |  1,587
Figure 3:  PCG time-series and the corresponding WST for the two situations
(murmur present, murmur absent) across the four heart valves, i.e., AV, PV,
TV, MV. Note that WST is quite effective in differentiating between the two
classes (murmur present, murmur absent).

Data normalization: For each data vector (segment), its mean $\mu$ and
standard deviation $\sigma$ is computed. Then, i-th element $x_{i}$ of each
data vector is normalized by means of following operation:
$x_{i,n}=\frac{x_{i}-\mu}{\sigma}$. The normalized data vector has zero mean
and unit variance.

###  III-C Time-Frequency Analysis for Feature Extraction

In order to study the feasibility of the two classification problems at hand,
and in order to help our neural networks do automatic feature extraction, we
transform the 1D audio PCG signals into their equivalent 2D representation
using various time-frequency domain methods, e.g., short-time Fourier
transform, mel-spectrograms, discrete and continuous wavelet transforms, and
wavelet scattering transform (WST). We note that all but WST are not effective
in differentiating between the three classes for the CirCor Digiscope 2022
dataset (the same holds for the PCG 2016 dataset). This is because WST is
known to be effective for feature extraction, even for very small datasets.
Therefore, we stick to WST for the rest of this work222Wavelet scattering is a
technique that applies mathematical operations similar to those applied in
convolutional layers. Specifically, WST utilizes wavelets as fixed
convolutional filter, followed by a non-linearity (modulus operator), followed
by averaging in order to find a low-variance representation of the data. .

Fig. 3 provides a visual summary of two possible situations (murmur present,
murmur absent) at each of the four heart valves. Specifically, Fig. 3 provides
the audio PCG time-series as well as the wavelet scattering function for all
possible scenarios. We conclude from Fig. 3 that wavelet scattering function
indeed is effective in discriminating between the three classes for the CirCor
Digiscope 2022 dataset.

##  IV Heart Murmur & Abnormal PCG Detection

###  IV-A Neural Network Architectures

For heart murmur detection and abnormal PCG detection, we implemented and
tested the following neural network (NN) architectures: convolutional neural
network (CNN)–both 1D and 2D, recurrent neural network (RNN)333The motivation
behind using the RNN (LSTM and GRU) is to exploit its capability to learn
temporal dependencies between the samples of a time-series (audio PCG signals,
in this work)., combination of CNN and RNN, and residual network (ResNet).
Eventually, it was the 1D-CNN model that resulted in maximum classification
accuracy. Therefore, Fig. 4 provides a detailed block diagram of the custom
1D-CNN model, with important parameters for each layer specified. One could
see that the best-performer 1D-CNN model is relatively shallow, with 4
convolution layers (each followed by a pooling layer, followed by a batch
normalization layer), a flattening layer, and 4 dense (fully connected)
layers. Each (convolutional and dense) layer utilized RELU activation
function, except the last layer which utilized softmax activation function.

For the sake of completeness, Figs. 5, 6 present the block diagrams of the two
other neural network models implemented in this work: a C-RNN model, and a
single-layer LSTM-RNN model (with tanh activation function). Finally, Fig. 7
provides the overall pictorial summary of our approach for heart murmur and
abnormal PCG detection.

Note that we re-train our 1D-CNN model from scratch in order to do abnormal
PCG detection on the PCG 2016 dataset later444We investigated transfer
learning technique by reusing the 1D-CNN model trained on PCG 2022 dataset by
testing it on PCG 2022 dataset, but without much success. This points to the
fundamental different nature (distribution) of the two datasets..

Figure 4: 1D-CNN Model architecture: KS (kernel size), SS(stride size), Pad
(padding).  Figure 5: CRNN Model architecture: KS (kernel size), SS(stride
size), Pad (padding).  Figure 6: LSTM-RNN Model Architecture. Figure 7:
Proposed method for heart murmur and abnormal PCG detection.

###  IV-B Training and Testing of NNs & Hyper-parameters

We implemented the custom 1D-CNN and LSTM-RNN models in Python using the
PyTorch framework (in Microsoft visual studio environment), on a desktop PC
with I5 7600 intel CPU and 1060ti Nvidia graphics card. The total available
data for both datasets was divided into training data and test data using an
80-20 split, while making sure that test data is totally unique (i.e., the
test data is not seen by the models during the training stage). For
backpropagation purpose, the cross-entropy loss function was used. Table III
summarizes the important hyper-parameters for the 1D-CNN model and the LSTM-
RNN model when trained on both datasets.

TABLE III: Hyper-parameters of the 1D-CNN and LSTM-RNN models when trained on both datasets: Q and J are wavelet scattering related parameters as described in the Python library Kymatio [28]. (*A dropout of 0.15 drops 15% of the output of each dense layer, except last one.)  Dataset |  PCG 2022/ 1D-CNN |  PCG 2022/ LSTM-RNN |  PCG 2016/ 1D-CNN
---|---|---|---
Batch Size |  132 |  132 |  126
Learning rate |  3e-5 |  1e-3 |  1e-4
Dropout |  0.15* |  None |  0.15*
Optimizer |  Adam |  Adam |  Adam
Backprop algorithm |  SGD |  SGD |  SGD
Initializer |  Xaviar |  Xaviar |  Xaviar
Q |  2 |  2 |  2
J |  4 |  4 |  4

We conducted a total of four experiments by training the custom 1D-CNN and
LSTM-RNN on the two datasets, in order to do:

  * •

E1) murmur detection using the original PCG 2022 dataset with 3 classes
(murmur present, murmur absent, unknown).

  * •

E2) murmur detection using a subset of the PCG 2022 dataset with 2 classes
(murmur present, murmur absent) with unknown class excluded.

  * •

E3) murmur detection with 3 classes using the cleaned PCG 2022 dataset after
re-labeling of noise-only segments, as discussed in previous section.

  * •

E4) abnormal PCG detection using the PCG 2016 dataset.

Fig. 8 shows that the loss as well as the accuracy settles in about 150 epochs
during both the training and the validation phase, for experiment E1. Fig. 9
shows that the loss and accuracy settle much quickly (in about 10 epochs), for
experiment E2 (due to the removal of the unknown class with noisy samples).
The loss and accuracy plots for experiments E3 and E4 show a similar trend,
and thus, are omitted for the sake of brevity.

(a)

(b)

Figure 8:  Loss and accuracy vs. epochs for experiment E1.

(a)

(b)

Figure 9:  Loss and accuracy vs. epochs for experiment E2.

##  V Experimental Results

We first describe the performance metrics used to evaluate the 1D-CNN and
other classifiers, followed by a discussion of the key results for the three
experiments E1, E2, E3 on murmur detection using the three variants of the PCG
2022 dataset, followed by a discussion of selected results for the fourth
experiment E4 on abnormal PCG detection using PCG 2016 dataset.

###  V-A Performance Metrics

We use accuracy and F1-score as the main performance evaluation metrics. Since
accuracy is most meaningful for a balanced dataset, we minimized the class
imbalance by reducing the size of the murmur present class in both datasets.
Additionally, weighted accuracy is also used as a performance metric for
comparison with other contestants of the Physionet challenge 2022.

####  V-A1 Accuracy

The accuracy of a dataset is the ratio of number of correct predictions
$S_{c}$ by the model and total number of samples $S_{t}$:
$A=\frac{S_{c}}{S_{t}}\times 100$.

####  V-A2 Weighted Accuracy

The weighted accuracy is a metric that gives more weight to the patients with
murmur, and is defined as:

$A_{w}=\frac{5m_{pp}+3m_{uu}+m_{aa}}{5(m_{pp}+m_{up}+m_{ap})+3(m_{pu}+m_{uu}+m_{au})+(m_{pa}+m_{ua}+m_{aa})}$
where $m_{xx}$ is defined as in Table IV.

TABLE IV: Weighted accuracy confusion matrix | Murmur Classifier
---|---
| Present | Unknown | Absent
Murmur Expert | Present | $m_{pp}$ | $m_{pu}$ | $m_{pa}$
Unknown | $m_{up}$ | $m_{uu}$ | $m_{ua}$
Absent | $m_{ap}$ | $m_{au}$ | $m_{aa}$

####  V-A3 F1-Score

F1-score is a statistical measure that depends upon two factors, precision and
recall. Precision is obtained by dividing total number of correctly classified
elements, i.e. True Positives by total positively classified elements, i.e.
True Positives (TP) + False Positives (FP). Thus, $P=\frac{TP}{TP+FP}$. Recall
is obtained by dividing total number of positively classified samples by the
total number of samples that should had been marked as positive, i.e., True
Positives and True Positives + False Negatives (FN) respectively. Thus,
$R=\frac{TP}{TP+FN}$. With precision and recall in hand, F1-score is
calculated as: $F1=2*\frac{P*R}{P+R}$, where $P$ is precision and $R$ is
recall.

(a)

(b)

(c)

Figure 10:  confusion matrices:
(a) experiment E1: murmur detection with three classes,
(b) experiment E2: murmur detection with two classes,
(c) experiment E3: murmur detection with three classes (after re-labeling).

###  V-B Results: Murmur detection using PCG 2022 dataset

Performance of 1D-CNN: First, we report the results obtained by the best-
performing 1D-CNN model. For experiment E1 that does murmur detection using
PCG 2022 dataset with three classes, we obtained a maximum accuracy of 82.28%,
83.81% weighted accuracy, and 90% area under the receiver operating
characteristic curve (AUROC) (see the confusion matrix in Fig. 10 (a)). On the
other hand, the experiment E2 that does murmur detection using PCG 2022
dataset with two classes (with unknown class with low-quality audios removed),
resulted in an improved accuracy of 87.66%, elevated F1-score of 0.87, and
higher AUROC of 92.28% (see the confusion matrix in Fig. 10 (b)). Finally, for
experiment E3 that does murmur detection using PCG 2022 dataset with three
classes (after re-labeling), the weighted accuracy improved to 86% and AUROC
rose to 93% (see Fig. 10 (c)). This resulted in a more balanced confusion
matrix for experiment E3 as before the re-labeling process, only 17% of the
unknown class samples were correctly detected in experiment E1, but now it
increases to 80% after the re-labeling process in experiment E3. This could
also be verified by comparing the F1-scores for experiments E1 and E3.

Selection of optimal segment size: We repeated our experiment E1 (where we
utilize the original PCG 2022 dataset as is) with different segment sizes
(i.e., 1 sec, 3 sec, 4 sec, and 5s), and assessed the performance of our
1D-CNN model with the aim to find an optimal segment size (see Table V). We
utilize F1-score as the core performance metric to select the optimal segment
size (this is because the accuracy is not a reliable performance metric for
the imbalanced datasets). Furthermore, we observed that overlapping segments
cause extreme over-fitting; therefore, we ended up selecting non-overlapping
segments of duration 4 seconds.

TABLE V: Impact of different segment sizes on performance of our 1D-CNN model (for experiment E1).  Window size |  Accuracy |  Precision |  Recall |  F1-score
---|---|---|---|---
1 sec |  72.15% |  55.40% |  54.91% |  54%
3 sec |  86 % |  55.60% |  55.30% |  55.30%
4 sec |  82.28% |  65.67% |  65.92% |  65.79%
5 sec |  73.7% |  63.56% |  63.38% |  62.98%
TABLE VI:  Heart murmur detection using PCG 2022 dataset: performance comparison of our work with the state-of-the-art (basically, the top performing submissions to the PhysioNet-2022 challenge).  Works |  Accuracy |  Weighted Accuracy |  Precision |  Recall |  F1-Score |  AUROC
---|---|---|---|---|---|---
Rank #1 contestant |  80.1% |  78% |  —– |  —– |  61.9% |  88.4%
Rank #2 contestant |  76.3% |  77.6% |  —– |  —– |  62.3% |  75.7%
Rank #3 contestant |  82.2% |  77.6% |  —– |  —– |  64.7% |  77.1%
Our work: 1D-CNN (experiment E1) |  82.28% |  83.81% |  65.67% |  65.92% |  65.79% |  90.79%
Our work: 1D-CNN (experiment E2) |  87.05% |  - |  87.05% |  88.02% |  87.72% |  94.4%
Our work: 1D-CNN (experiment E3) |  82.86% |  86.30% |  81.75% |  82.19% |  81.87% |  93.45%
Our work: LSTM-RNN (experiment E3) |  77.18% |  82.28% |  76.83% |  76.20% |  75.92% |  90.72%
Our work: CRNN (experiment E3) |  73.99% |  79.88% |  74.02% |  74.38% |  73.64% |  89.25%

Performance comparison with LSTM-RNN and CRNN: Table VI lists the performance
obtained by the other two NN models (i.e., LSTM-RNN and CRNN) that we
implemented and tested. We note that our 1D-CNN model outperforms both LSTM-
RNN and CRNN models in terms of accuracy, weighted accuracy, precision,
recall, F1-score and AUROC, for experiment E3 (which does murmur detection on
the cleaned dataset).

Performance comparison with the state-of-the-art: Table VI provides a thorough
comparison of the performance achieved by the top three contestants in the
Physionet 2022 challenge, with the performance achieved by our NN models:
1D-CNN, LSTM-RNN, and CRNN. Table VI demonstrates that our 1D-CNN model
outperforms all the three top contestants in terms of accuracy, weighted
accuracy, F1-score and AUROC, for both experiments E1 (which does murmur
detection on the original dataset) and E3 (which does murmur detection on the
cleaned dataset).

###  V-C Results: Abnormal PCG detection using PCG 2016 dataset

As mentioned in the previous section, we re-train our 1D-CNN model from
scratch on PCG 2016 dataset in order to differentiate between a normal PCG
signal and an abnormal PCG signal. The hyper-parameters of the 1D-CNN that was
fine-tuned for PCG 2016 dataset could be found in Table III. Specifically, for
the abnormal PCG detection problem, the model achieved 96.30% accuracy, and
98.17% AUROC (see Fig. 11 and Table VII).

TABLE VII: Experiment E4 (Abnormal PCG signal detection): performance of our 1D-CNN model on PCG 2016 dataset.  Accuracy |  Precision |  Recall |  F1-Score |  AUROC
---|---|---|---|---
96.30% |  96.24% |  96.40% |  96.29% |  98.17%
(a)
Figure 11:  Confusion matrix for experiment E4: abnormal PCG detection (using
PCG 2016 dataset).

##  VI Conclusion

This work utilized two public datasets, i.e., CirCor Digiscope 2022 dataset
and PCG 2016 datasets (from Physionet online database) in order to train three
deep learning classifiers, i.e., 1D-CNN, LSTM-RNN, and C-RNN to do heart
murmur detection as well as abnormal PCG detection. We observed that our
1D-CNN outperformed the other two NNs as well as the state-of-the-art, with an
accuracy of 82.86%, weighted accuracy of 86.30%, and F1-score of 81.87% (for
experiment E3 which does murmur detection after re-labeling of noise-only
segments).

We note that the CirCor Digiscope 2022 dataset also contains other valuable
information about the murmurs, e.g., murmur grading, timing, quality, pitch,
shape etc. Thus, design of novel machine/deep learning algorithms which could
do automatic and accurate murmur grading analysis with little data is an open
problem of great interest. Furthermore, study of generative methods which
could reliably generate synthetic PCG data in order to help train the data
hungry deep learning methods is another interesting but challenging open
problem (due to non-stationary nature of PCG signals with murmurs).

## References

  * [1] T. Chakrabarti, S. Saha, S. Roy, and I. Chel, “Phonocardiogram signal analysis-practices, trends and challenges: A critical review,” in _2015 international conference and workshop on computing and communication (IEMCON)_. IEEE, 2015, pp. 1–4.
  * [2] S. Ismail, I. Siddiqi, and U. Akram, “Localization and classification of heart beats in phonocardiography signals—a comprehensive review,” _EURASIP Journal on Advances in Signal Processing_ , vol. 2018, no. 1, pp. 1–27, 2018.
  * [3] J. Oliveira, F. Renna, P. D. Costa, M. Nogueira, C. Oliveira, C. Ferreira, A. Jorge, S. Mattos, T. Hatem, T. Tavares, A. Elola, A. B. Rad, R. Sameni, G. D. Clifford, and M. T. Coimbra, “The circor digiscope dataset: From murmur detection to murmur classification,” _IEEE Journal of Biomedical and Health Informatics_ , vol. 26, no. 6, pp. 2524–2535, 2022.
  * [4] C. Liu, D. Springer, Q. Li, B. Moody, R. A. Juan, F. J. Chorro, F. Castells, J. M. Roig, I. Silva, A. E. Johnson _et al._ , “An open access database for the evaluation of heart sound algorithms,” _Physiological measurement_ , vol. 37, no. 12, p. 2181, 2016.
  * [5] A. Djebbari and F. B. Reguig, “Short-time fourier transform analysis of the phonocardiogram signal,” in _ICECS 2000. 7th IEEE International Conference on Electronics, Circuits and Systems (Cat. No. 00EX445)_ , vol. 2. IEEE, 2000, pp. 844–847.
  * [6] C. Potes, S. Parvaneh, A. Rahman, and B. Conroy, “Ensemble of feature-based and deep learning-based classifiers for detection of abnormal heart sounds,” in _2016 computing in cardiology conference (CinC)_. IEEE, 2016, pp. 621–624.
  * [7] P. T. Krishnan, P. Balasubramanian, and S. Umapathy, “Automated heart sound classification system from unsegmented phonocardiogram (pcg) using deep neural network,” _Physical and Engineering Sciences in Medicine_ , vol. 43, pp. 505–515, 2020.
  * [8] O. R. A. Almanifi, A. F. Ab Nasir, M. A. M. Razman, R. M. Musa, and A. P. A. Majeed, “Heartbeat murmurs detection in phonocardiogram recordings via transfer learning,” _Alexandria Engineering Journal_ , vol. 61, no. 12, pp. 10 995–11 002, 2022.
  * [9] A. L. Goldberger, L. A. Amaral, L. Glass, J. M. Hausdorff, P. C. Ivanov, R. G. Mark, J. E. Mietus, G. B. Moody, C.-K. Peng, and H. E. Stanley, “Physiobank, physiotoolkit, and physionet: components of a new research resource for complex physiologic signals,” _circulation_ , vol. 101, no. 23, pp. e215–e220, 2000.
  * [10] K. A. Babu, B. Ramkumar, and M. S. Manikandan, “Automatic identification of s1 and s2 heart sounds using simultaneous pcg and ppg recordings,” _IEEE Sensors Journal_ , vol. 18, no. 22, pp. 9430–9440, 2018.
  * [11] P. Vikhe, N. Nehe, and V. Thool, “Heart sound abnormality detection using short time fourier transform and continuous wavelet transform,” in _2009 Second International Conference on Emerging Trends in Engineering & Technology_. IEEE, 2009, pp. 50–54.
  * [12] P. Langley and A. Murray, “Heart sound classification from unsegmented phonocardiograms,” _Physiological measurement_ , vol. 38, no. 8, p. 1658, 2017.
  * [13] M. A. Reyna, Y. Kiarashi, A. Elola, J. Oliveira, F. Renna, A. Gu, E. A. Perez-Alday, N. Sadr, A. Sharma, S. Mattos _et al._ , “Heart murmur detection from phonocardiogram recordings: The george b. moody physionet challenge 2022,” _medRxiv_ , pp. 2022–08, 2022.
  * [14] M. Alkhodari and L. Fraiwan, “Convolutional and recurrent neural networks for the detection of valvular heart diseases in phonocardiogram recordings,” _Computer Methods and Programs in Biomedicine_ , vol. 200, p. 105940, 2021\.
  * [15] S. R. Messer, J. Agzarian, and D. Abbott, “Optimal wavelet denoising for phonocardiograms,” _Microelectronics journal_ , vol. 32, no. 12, pp. 931–941, 2001.
  * [16] A. Elola, E. Aramendi, J. Oliveira, F. Renna, M. T. Coimbra, M. A. Reyna, R. Sameni, G. D. Clifford, and A. B. Rad, “Beyond heart murmur detection: Automatic murmur grading from phonocardiogram,” _arXiv.org_ , Sep 2022. [Online]. Available: https://arxiv.org/abs/2209.13385v1
  * [17] A. Kazemnejad, P. Gordany, and R. Sameni, “Ephnogram: A simultaneous electrocardiogram and phonocardiogram database,” _PhysioNet_ , 2021.
  * [18] M. Cesarelli, M. Ruffo, M. Romano, and P. Bifulco, “Simulation of foetal phonocardiographic recordings for testing of fhr extraction algorithms,” _Computer methods and programs in biomedicine_ , vol. 107, no. 3, pp. 513–523, 2012.
  * [19] T. H. Chowdhury, K. N. Poudel, and Y. Hu, “Time-frequency analysis, denoising, compression, segmentation, and classification of pcg signals,” _IEEE Access_ , vol. 8, pp. 160 882–160 890, 2020.
  * [20] K. N. Khan, F. A. Khan, A. Abid, T. Ölmez, Z. Dokur, A. Khandakar, M. E. H. Chowdhury, and M. S. Khan, “Deep learning based classification of unsegmented phonocardiogram spectrograms leveraging transfer learning,” _CoRR_ , vol. abs/2012.08406, 2020. [Online]. Available: https://arxiv.org/abs/2012.08406
  * [21] J. Karhade, S. Dash, S. K. Ghosh, D. K. Dash, and R. K. Tripathy, “Time–frequency-domain deep learning framework for the automated detection of heart valve disorders using pcg signals,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 71, pp. 1–11, 2022.
  * [22] A. Sugiyarto, A. Abadi, and Sumarna, “Classification of heart disease based on pcg signal using cnn,” _TELKOMNIKA (Telecommunication Computing Electronics and Control)_ , vol. 15, pp. 1697–1706, 10 2021.
  * [23] J. Wang, T. You, Y. Kang, Y. Gong, Q. Xie, F. Qu, B. Wang, and Z. He, “Intelligent diagnosis of heart murmurs in children with congenital heart disease,” _Journal of Healthcare Engineering_ , vol. 2020, pp. 1–9, 05 2020\.
  * [24] S. K. Randhawa and M. Singh, “Classification of heart sound signals using multi-modal features,” _Procedia Computer Science_ , vol. 58, pp. 165–171, 2015, second International Symposium on Computer Vision and the Internet (VisionNet’15). [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1877050915021560
  * [25] M. Zabihi, A. Bahrami Rad, S. Kiranyaz, M. Gabbouj, and A. Katsaggelos, “Heart sound anomaly and quality detection using ensemble of neural networks without segmentation,” 09 2016.
  * [26] E. Kay and A. Agarwal, “Dropconnected neural networks trained on time-frequency and inter-beat features for classifying heart sounds,” _Physiological Measurement_ , vol. 38, pp. 1645–1657, 07 2017.
  * [27] M. A. Reyna, Y. Kiarashi, A. Elola, J. Oliveira, F. Renna, A. Gu, E. A. Perez Alday, N. Sadr, A. Sharma, S. Mattos, M. T. Coimbra, R. Sameni, A. B. Rad, and G. D. Clifford, “Heart murmur detection from phonocardiogram recordings: The george b. moody physionet challenge 2022,” _medRxiv_ , 2022\. [Online]. Available: https://www.medrxiv.org/content/early/2022/08/16/2022.08.11.22278688
  * [28] M. Andreux, T. Angles, G. Exarchakisgeo, R. Leonardu, G. Rochette, L. Thiry, J. Zarka, S. Mallat, J. Andén, E. Belilovsky _et al._ , “Kymatio: Scattering transforms in python,” _The Journal of Machine Learning Research_ , vol. 21, no. 1, pp. 2256–2261, 2020.