# Beat-to-Beat Fetal Heart Rate Analysis Using Portable Medical Device and
Wavelet Transformation Technique

Maria Farahi  Sana Meditech S.L., Barcelona, Spain  Center of Research in
Biomedical Engineering. Universitat Politècnica de Catalunya, BarcelonaTech,
Barcelona, Spain  Daniel Lechuga Morente  Sana Meditech S.L., Barcelona, Spain
Universitat Pompeu Fabra, Barcelona, Spain  Omid Sarrafzadeh  Sana Meditech
S.L., Barcelona, Spain  Yasaman Zamani  Sana Meditech S.L., Barcelona, Spain
Hooran Ahmadi  Sana Meditech S.L., Barcelona, Spain  Alícia Casals Gelpí
Center of Research in Biomedical Engineering. Universitat Politècnica de
Catalunya, BarcelonaTech, Barcelona, Spain  Naeimeh Behbood  Sana Meditech
S.L., Barcelona, Spain  Hessam Habibian  Sana Meditech S.L., Barcelona, Spain

###### Abstract

A beat-to-beat Tele-fetal Monitoring and comparison with clinical data are
studied with multi wavelet transformation approach. Tele-fetal monitoring is a
big progress toward wearable medical device for a pregnant woman capable of
obtaining prenatal care at home. We propose an algorithm for fetal cardiac
monitoring using a portable fetal Doppler medical device. Choosing an
appropriate mother wavelet, 85 different mother wavelets are investigated. The
fficiency of the proposed method is evaluated using two data sets. From a
publicly available data on PhysioBank, and simultaneous clinical measurement
we prove that our beat-to-beat fetal heart rate (FHR) comparison between
obtained fetal heart rate by algorithm and the baselines yields a promising
accuracy beyond 94%. The proposed algorithm would be robust technique for any
similar Tele-fetal monitoring approach.

##  I Introduction

A gestation can end with a live birth, a spontaneous miscarriage, an induced
abortion, or a stillbirth bai2002parity ; Abman2011 . Prenatal care by the
mother and constant monitoring of the gestational period are key elements in
improving birth outcomes Reichman2010 . Clinically, various medical devices
have been introduced to monitor the Fetal Heart Rate (FHR) during pregnancy.
Approaches like cardiotocography (CTG) grivell2015antenatal , fetal
magnetocardiography (fMCG) peters2001monitoring , fetal electrocardiography
(fECG) nassit2015non , and fetal scalp electrocardiography (fsECG)
organ1968scalp  are examples of clinical techniques that can be applied for
fHR monitoring.

First of all, fetal scalp electrocardiography in which electrodes are applied
on fetal scalp. It captures signals with a high Signal to Noise Ratio (SNR).
However, it is invasive and increases the risk of infections. In addition, it
can be used only during the delivery. And, it needs a skilled specialist for
installation organ1968scalp .

Secondly, among non-invasive devices, fMCG is a method which is well known for
its high SNR in data capturing. It uses SQUID (for Superconducting QUantum
Interference Device) sensors to record the magnetic field of the fetal heart
from maternal abdomen. But it is expensive and needs a shielded room with an
expert specialist to apply it on the mother’s abdomenpeters2001monitoring .

Next non-invasive technique, known as fECG, is a cheap technology which
enables user to perform continuous monitoring. This method not only suffers
from low SNR, but also its electrodes should be placed on mother’s abdomen by
a skilled specialists nassit2015non .

Finally, CTG is a standard non-invasive clinical method. It is a well-known
technique which uses Doppler ultrasound sensors to monitor both fHR and uterus
contractions. It is highly accurate, and requires less skills to operate
nageotte2015fetal ; euliano2013monitoring , but it is highly sensitive to the
fetal movements alnuaimi2019fetal .

Tele-Fetal Monitoring (TFM) is an approach which makes a pregnant woman
capable of obtaining prenatal care. It can decrease the risk of pregnancies
with hypertensive disorders lanssens2018impact . Moreover, it has illustrated
profits in other high-risk pregnancies like those with gestational diabetes.
Also, it can be beneficial in having access to rural pregnant women whom are
far from modern hospitals van2018ehealth .

In the past decade, many efforts have been dedicated to find a suitable way
for distant fHR extraction. As an example, fHS analysis is considered as a
non-invasive method. It is simple to apply and it has a low-cost. However, fHS
signals are profoundly corrupted by noise since they are recorded at the
maternal abdominal surface. There are various sources of noise in fHS signals
including fetal movements, contractions of mother’s uterus, maternal digestive
sounds, sensor movements, ambient sounds, maternal respiratory and maternal
heart sound strazza2018pcg .

The basic principle behind the fHS processing is that the heart’s mechanical
activity is accompanied by the generation of a various characteristic sounds.
These sounds are associated with changes in the speed of blood flow, as well
as with the opening and closing of heart valves tang2016phonocardiogram . Dia
et al. estimated adult heart rate from phonocardiograph (PCG) signals
dia2019heart . They applied non-negative matrix factorization approach on the
spectrogram of the taken signals. They evaluated their work by considering
synchronous ECG and PCG signals. Samieinasab et al. samieinasab2015fetal ,
used a single-channel denoising framework to reduce the noise of fetal PCGs.
Then, similar to dia2019heart , they utilized non-negative matrix
factorization method to decompose fPCGs in time-frequency domain. In addition,
Khandoker et al. proposed a four-channel fPCG system and evaluate it using
fECG data khandoker2018validation . They used 10-minutes clinical data for
evaluation. Reported results were P<0.01 in cross correlation analysis and <5
% agreement in Bland-Altman plot.

Motivated by this fact that the most challenging step in fHR extraction from
fetal heart sound signals is denoising, this paper presents a denoising
algorithm based on wavelet transform. Also, the other aim of current paper is
to introduce an algorithm capable of performing fHR extraction from fetal
heart sound in order to facilitate tele-fetal monitoring for pregnant women.

In this paper, a pocket size fetal Doppler monitor is used for data capturing.
It is connected through a cable to a mobile to save fetal heart sounds and be
able to further analyze them and do the comparison with a clinical device.

In the following, in section 2, the procedure of data acquisition is
explained. Then, the applied method for fHR extraction is illustrated in
section 3. In section 4, obtained results are shown. Finally, the current work
is discussed and concluded in section 5.

##  II Data Acquisition

In order to collect clinical data, a portable Baby Sound A pocket fetal
Doppler device manufactured by Contec Medical Co. ContecMedicalCo  is used. It
is certified under medical CE and FDA approval. The device is utilized by Sana
Meditech company SanaMediTechCo  with a brand of Baby Heart Beat BabyHeartBeat
. Obtaining data for algorithm development, simultaneous measurement of Baby
Heart Beat together with a clinical device Bionet model FC-1400 Bionet  is
performed. The data acquisition mechanism is shown pictorially in figure 1.
Total length of 130 minutes signal has been acquired from seven pregnant women
(average age 32). The average of the records duration is almost 3 minuets with
a sampling frequency of 8KHz. Simultaneously, pregnant women are monitored
with a clinical device (Bionet FC-1400) which allows us to validate our
proposed approach.

Clinical data is recorded for rigorous analysis of the algorithm and
continuous improvement during the development process. Table 1 illustrates the
eligible criteria of our study population.

Figure 1: Clinical data acquisition setup Table 1: Study population’s eligible criteria. Age (year) | from 18 to 50
---|---
Type of pregnancy | singleton
Gestation (week) | greater than 32
Body Mass Index | from 15 to 45
Anomaly | allowed

In addition, our proposed algorithm is applied on a simulated fetal heart
sound data set provided by Cesarelli cesarelli2012simulation . It is publicly
available in physionet simulatedFetalPCGs , and contains 37 signals. Each
signal has a duration of 8 minutes, and sampling frequency is 1KHz. In this
data set, in order to simulate environment noise, signals are corrupted with
different SNR values from -26.7dB to -4.4dB. For more information about this
data set, reader can refer to simulatedFetalPCGs .

##  III Materials and Methods

In order to have a successful tele-fetal monitoring, the device should have
some capabilities. First of all, it should be user-friendly, without any need
to a specialist for its implementation. Next, it must provide continuous
monitoring, and finally, it should achieve high accuracy results in order to
omit false positive reports.

Figure 2: A comprehensive representation of the dynamics of a single heart
cycle and its related sounds. Note the temporal synchronisation between the
different signals. Taken from schmidt2007detection

Recently, the use of a pocket Doppler device is becoming common which allows
pregnant women to listen to their fetal heart sound (fHS) at home. A portable
fetal Doppler device used for this study, has an AUX port which provides a
possibility to export fHS data. The exported fHS signal can be recorded by a
dedicated mobile App, and subsequently can be used for the extraction of fetal
heart rate. Therefore, in this paper, we propose a new method consists of
adaptive band pass filtering and wavelet transform in order to extract fHR
from recorded fHS signals.

Figure 3: Proposed scheme for fHR extraction.

Fetal heart sound signals which are recorded from mother abdomen would have a
shape like figure 2. In this figure, S shows the position of systole while D
is representative of Diastole. In order to extract fHR, the distance between
two systole should be calculated. In this paper, the overall proposed signal
processing steps for fHR extraction from fHS signals is shown in figure 3. As
depicted, the algorithm starts with a pre-processing stage. In two further
steps, those peaks which are related to systole are detected. Afterwards, fHR
is extracted. Finally, a smoothing step is performed to avoid outliers in the
final reported of fHR. Following sections describe the major stages of the
shown flowchart in detail.

###  III.1 Pre-Processing

Fetal heart sound signals are heavily corrupted by noise since they are
recorded at the maternal abdominal surface. Fetal movements, contractions of
mother’s uterus, mother’s abdominal sounds, sensor movements, ambient sounds,
maternal respiratory and heart sound are the various sources of noise
strazza2018pcg . In this study, noise reduction is performed based on the use
of wavelet transform.

A. Wavelet Filtering

Wavelet Transformation (WT) is a time-frequency processing method and its
definition for an input signal $x(t)$ is as Eq. 1:

$\centering WT_{x(a,b)}=\int x(t)\Psi^{*}_{a,b}(t)dt\hskip 14.22636pt;a\neq
0\@add@centering$ (1)

where the basic function, $\Psi_{a,b}(t)$, is featured by scale and time-shift
parameters ($a$ and $b$, respectively) as Eq.2:

$\centering\Psi_{a,b}(t)=\frac{1}{\surd a}\psi(\frac{t-b}{a})\@add@centering$
(2)

Table 2: A summary of different mother wavelets’ properties

Mother Wavelet |  Compact Support |  Vanishing Moment |  Regularity |  Orthogonal |  Bio Orthogonal |  Symmetric |  Energy |  Discrete Wavelet |  Continues Wavelet |  References
---|---|---|---|---|---|---|---|---|---|---
HAAR |  ✓ |  1 |  × |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  Daubechies1992
Daubechies |  ✓ |  N |  0.2N |  ✓ |  ✓ |  × |  ✓ |  ✓ |  ✓ |  Daubechies1992
Symlets |  ✓ |  N |  - |  ✓ |  ✓ |  near |  ✓ |  ✓ |  ✓ |  Daubechies1992
Coiflets |  ✓ |  2N |  - |  ✓ |  ✓ |  near |  ✓ |  ✓ |  ✓ |  Daubechies1992
Biorthogonal |  ✓ |  Nr |  Nr-1 |  × |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  Daubechies1992
Fejer-Korovkin |  ✓ |  N |  - |  ✓ |  × |  × |  ✓ |  ✓ |  ✓ |  nielsen2001construction ; chen2020comparing
Meyers |  × |  N |  inf |  ✓ |  ✓ |  ✓ |  ✓ |  * |  ✓ |  Daubechies1992
Gaussian |  × |  - |  - |  × |  × |  ** |  × |  × |  ✓ |  mallat1999wavelet
Mexican hat |  × |  2 |  - |  × |  × |  ✓ |  × |  × |  ✓ |  Daubechies1992 ; Leigh2013
Morlet |  × |  - |  - |  × |  × |  ✓ |  × |  × |  ✓ |  Daubechies1992
Complex Gaussian |  × |  - |  - |  × |  × |  ** |  × |  × |  ✓ |  mallat1999wavelet
Shannon |  × |  N |  - |  × |  × |  ✓ |  × |  × |  ✓ |  teolis1998computational
Freq. B-Spline |  × |  - |  - |  × |  × |  ✓ |  × |  × |  ✓ |  teolis1998computational
Complex Morlet |  × |  - |  - |  × |  × |  ✓ |  × |  × |  ✓ |  teolis1998computational

* It is possible but without fast WT.
** They are symmetric if their order is even.

$\Psi_{a,b}(t)$ can be also used for signal decomposition. The main challenge
in using WT for denoising is to choose the optimum mother wavelet for the
given tasks. In order to conclude which mother wavelet is suitable for a
specific purpose, main properties such as vanishing moments rhif2019wavelet ,
size of support kozachenko2014uniform , regularity Daubechies1992  ,
orthogonality anoh2013comparison  , bio-orthogonality anoh2013comparison ,
energy yang2019parameterised , symmetry, and the ability of implementing on
discrete signals should be investigated. Table 2 presents 14 different
families of mother wavelets that we have investigated in this paper. They
include HAAR, Daubechies, Symlets, Coiflets, Biorthogonal, Fejer-Krovokin,
Meyers, Gaussian, Mexican hat, Morlet, Complex Gaussian, Shannon, Freq.
B-Spline, and Complex Morlet. Next section describes the procedure of choosing
the best mother wavelet related to our goal (fHS denoising).

B. Mother wavelet Selection

Figure 4: Distribution plot of RWEER for different 85 mother wavelets
including $db$ 1, $db$ 2, …, $db$ 45 ,$sym$ 1, $sym$ 2, …, $sym$ 20, $coif$ 1,
$coif$ 2, …, $coif$ 5, $bior$ 1.1, $bior$ 1.3, …, and $bior$ 6.8. First row:
The effect of wavelet decomposition in different levels on the abundance of
maximum RWEER. It shows that level $j=4$ works better than others. Second row:
The investigation of RWEER for 215 sections with different mother wavelets on
level $j=4$, red dash-dot graph interprets the proposed algorithm’s execution
time for each mother wavelet, the black dash-dot graph represents the value of
$\frac{mean}{std}$ for shown box-plot. Outliers are drawn in red plus.

In this paper, the selection of most suitable mother wavelet is performed by
looking at each mother wavelet’s properties (see table 2). It means that we
firstly considered our needs to discard some mother wavelets which are far
from our goals. For isntance, we need a mother wavelet that preserves the
energy of the signal after decomposition (like orthogonal and bio-orthogonal).
As a result, we crossed out non-orthogonal mother wavelets including Gaussian,
Mexican hat, Morlet, Complex Gaussian, Shannon, Freq B-Spline and Complex
Morlet.

Similarly, the chosen wavelet family must be able to offer the possibility of
performing the discrete wavelet transform. Since Meyer family can not do fast
WT for discrete data, we crossed it out from further investigation.

Finally, relatively complex mother wavelets, with a minimum number of
vanishing moments are needed. This will allow to represent more complex
functions with fewer wavelet coefficients Omari2014 . Considering mentioned
specifications, mother wavelets of Daubechies, Symlets, Coiflets and
Biorthogonal are chosen. In this paper, all mother wavelets of $db1$, $db2$,
$\dots$, $db45$, $sym1$, $sym2$ ,$\dots$, $sym20$, $coif1$, $coif2$, $\dots$,
$coif5$, and $bior1.1$, $bior1.2$, $\dots$, $bior6.8$ are investigated.

(a)

(b)

(c)

Figure 5: A sample of an original fHS signal before and after filtering: (a)
Original signal, (b) Denoised signal using proposed method, and (c) Extracted
S-peaks. Red graph shows obtained envelop and red bullets represent all local
maxima. Green bullets illustrate the position of selected S.

In order to find the most proper mother wavelet among others, two factors are
important to be taken into account: energy and entropy. Energy clarifies how
much a signal and a mother wavelet are similar to each other. The energy of a
detail signal at each resolution level, $j$ is:

$\centering E_{j}=\sum_{j=1}^{J}|C_{j}(k)|^{2}\@add@centering$ (3)

where $C_{j}(k)$ is wavelet coefficients in level $j$. In consequence, the
total energy can be obtained by:

$\centering
E_{tot}=\sum_{j}\sum_{k}|C_{j}(k)|^{2}|=\sum_{j=1}E_{j}\@add@centering$ (4)

Relative wavelet energy will assist to choose an effective mother wavelet
salwani2005relative . It can detect the degree of similarities between
different segments of a signal rosso2001wavelet  and is defined as Eq.5.

$\centering p_{j}=\frac{E_{j}}{E_{tot}}\@add@centering$ (5)

Entropy shows the effect of mother wavelet on the accuracy of reconstruction.
It illustrates how much of data will be missed by a chosen mother wavelet. The
definition of entropy is presented in equation 6.

$H(j)=-\sum_{j=1}^{J}p_{j}^{2}log(p_{j}^{2})$ (6)

where $p_{j}$ is the energy probability distribution of the wavelet
coefficients defined in Eq5.

Dividing relative wavelet energy by entropy (see Eq. 7) , what we get is a
ratio that clearly indicates which mother wavelet mostly resembles the
original signal. The mother wavelet we are most interested in, will be the one
that obtains a higher value of this ratio, meaning that the similarities
between the wavelet and the original signal are greater than the non-conserved
information between them.

$RWEER(j)=\frac{E(j)}{H(j)}$ (7)

where RWEER is a representative of Relative Wavelet Energy to Entropy Ratio.

In this study, RWEER is calculated until level $j=12$ on 215 abdominal fetal
heart sound sections. 85 mother wavelets are investigated to select the most
proper one. These mother wavelets are $db1,db2,...,db45$,
$sym1,sym2,...,sym20$, $coif1,...,coif5$, and $bior1.1,...,bior6.8$. Maximum
RWEER for each level is obtained. First row of figure 4 shows that the highest
RWEER happens in level 4. Therefore, level $j=4$ is chosen. In the next step,
RWEER is calculated for $level=4$ to find the best mother wavelet. In figure 4
bottom, the shown boxplot depicts the RWEER distribution for each mother
wavelet applied on 215 fHS sections. Also, red-dashed graph illustrates the
execution time for each mother wavelet, and black-dash line displays the ratio
of mean to standard deviation for RWEER of all 215 sections. Based on this
figure, mother wavelet number 74, bior2.2, is chosen to denoise fHS signals.
It has the highest mean/std ratio and it also is more repeatable than others
while its time execution is low.

To sum up, in this work, decomposition, denoising and reconstruction of fHS
signals were performed by the use of $Bior2.2$ with 4 levels of decomposition.
An example of a noisy fHS versus denoised fHS is shown in figure 5 top. In
this figure, top graph shows 1-second of original fHS signal and bottom graph
depicts denoised fHS signal using proposed denoising approach.

Table 3: The effect of various methods for outliers replacement on final MSE
error.

replace with |  WS=1 |  WS=2 |  WS=3 |  WS=4 |  WS=5 |  WS=6 |  WS=7 |  WS=8 |  WS=9 |  WS=10 |  WS=11
---|---|---|---|---|---|---|---|---|---|---|---
Moving Mean
previous |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  18.19
next |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  18.19
nearest |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  18.19
linear |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  18.19
spline |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  18.19
pchip |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  18.19
makima |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  20.54 |  18.19
Moving Median
previous |  20.54 |  20.54 |  15.92 |  16.09 |  7.16 |  6.57 |  6.25 |  4.58 |  5.45 |  3.12 |  5.45
next |  20.54 |  20.54 |  15.91 |  16.09 |  7.16 |  6.67 |  6.12 |  3.50 |  9.44 |  2.58 |  9.46
nearest |  20.54 |  20.54 |  15.91 |  16.07 |  7.14 |  6.67 |  6.13 |  3.51 |  7.56 |  2.69 |  7.57
linear |  20.54 |  20.54 |  15.91 |  16.07 |  7.24 |  6.55 |  6.14 |  3.77 |  6.82 |  2.62 |  6.83
spline |  20.54 |  20.54 |  15.95 |  16.20 |  7.50 |  6.64 |  6.16 |  3.79 |  10.6 |  3.16 |  10.62
pchip |  20.54 |  20.54 |  15.91 |  16.07 |  7.26 |  6.57 |  6.14 |  3.82 |  7.40 |  2.67 |  7.40
makima |  20.54 |  20.54 |  15.91 |  16.08 |  7.25 |  6.55 |  6.13 |  3.76 |  7.26 |  2.65 |  7.27

* All the numbers are in (bpm).

###  III.2 Systole Extraction

Figure 2 shows that the detection of systole is essential for fHR extraction.
In fHS signals, the distance between systole (S) and diastole (D) is much
shorter than that in adult’s heart sound. Considering the fact that diastolic
duration is longer than systolic duration, D falls at least 100ms after
preceding S and at most 200ms before successive S koutsiana2017WD-FD . As a
result, a reasonable approach for S extraction, is to firstly find all the
candidates (including S and D) and secondly select S among them.

In the first stage, two steps including enveloping and finding local maxima
are applied to extract all peaks (S and D). Considering figure 5, local maxima
can be taken into account as potential candidates for S peaks. The procedure
of S selection is based on this fact that the normal duration of a fetal
beating heart cycle is $430ms$ while the minimum is $375ms$ and the maximum is
$545ms$ koutsiana2017WD-FD . Therefore, in this study, a thresholding method
is chosen to extract S peaks. Selected S-peaks are passed through the next
step, which is fHR calculation. An example of the results of S-selection is
shown in the last row of figure 5 . In this figure, red graph shows obtained
envelope. All candidates are illustrated in red bullets while selected S-peaks
are depicted in green bullets.

(a)

(b)

Figure 6: The results of beat to beat cross correlation analysis and Bland-
Altman plot for obtained fHR by proposed algorithm and the reference for
simulated data. (a) Beat to beat cross correlation analysis, and (b) Bland-
Altman plot. We use a test statistic known as the p-value to determine
statistical significance: if the p-value falls below the significance level,
then the result is statistically significant. Figure 7: The use of image
processing techniques for validation of the proposed algorithm. A) Saved image
from clinical device. B,C) fHR graph extraction, D) Confidence interval
definition, and E) Adding fHR results obtained from proposed algorithm in red.

###  III.3 fHR calculation

Knowing that the time elapsed between two successive S in a fHS signal, is a
combination of systolic time and diastolic timekovacs2011fetal , fHR can be
calculated using Eq.8.

$\centering fHR(bpm)=\frac{60}{T_{{s}{s}}(sec)}\@add@centering$ (8)

where, $T_{{s}{s}}$ is the time duration between two S.

Finally, to plot obtained fHR, it would be appropriate if outliers
yang2020graduated  are replaced with a proper value. In this study, in order
to increase the accuracy of the obtained fHR, two methods of outliers
detection including moving median and moving mean are investigated with
various Window Sizes (WS). In addition, different fillers including
’previous’, ’next’, ’nearest’, ’linear’, ’spline’, ’pchip’, and ’makima’ are
considered to find an alternative value for detected outliers. As it is shown
in table 3, moving median acts better that moving mean. The lowest Mean Square
Error (MSE) firstly happens when WS=10, and secondly when WS=8. In this study,
because the analysis is real time, having a smaller WS will cause less delay.
Therefore, moving median outlier detector with a ’nearest’ filler of WS=8 is
chosen.

##  IV Results and discussions

The analysis and validation of this study is applied on a personal computer
using Matlab R2020a on two datasets. Firstly, the public standard simulated
fHS database cesarelli2012simulation  is used for algorithm implementation.
This dataset contains 37 simulated fPCG signals. Each signal has a duration of
8 minutes, and the sampling frequency is 1KHz. In order to obtain the
functionality of proposed algorithm, the analysis of beat-to-beat correlation
and Bland-Altman plot giavarina2015understanding  is performed between
obtained fHR and manually extracted fHR from reference (see figure 6 )

Secondly, the algorithm is clinically validated using a real fHS dataset. For
this purpose, a portable fetal Doppler device ContecMedicalCo  is used to save
fHS signals. Simultaneously, a clinical device, Bionet model FC-1400 Bionet
is used for fetal monitoring. Final fHR reported by the clinical device is
saved in image format. Using image processing techniques in MATLAB, clinical
fHR graph is extracted from each image and a confidence interval of $\pm 7bpm$
hayes2012accuracy  is shown on the same image. Finally, obtained fHR is
depicted on the image to find the number of outliers (see figure 7). Figure 8
shows another example in which outliers are depicted by red arrows.

In this paper, each clinical signal has a different length. Therefore, in
order to validate the proposed algorithm, normalized accuracy is calculated
(eq.9).

Figure 8: A comparison sample between algorithm’s final graph (in red) and the
result of clinical device (in black). Confidence interval is shown in green.
Ouliers are shown by red arrows. Figure 9: The percentage of error obtained
for each data. Orange graph shows the percentage of obtained error. Blue bars
illustrate the length of each data in second.

$\begin{split}NormalizedAccuracy=\sum_{t=1}^{K}(1-\frac{N_{o}}{N_{t}})\times(\frac{N_{o}}{N_{T}})\end{split}$
(9)

in where, $N_{o}$ is the number of outliers in signal number $t$. $N_{t}$ is
the length of signal, and $N_{T}$ shows the total length of the used dataset.
In this paper, 130 minutes data are investigated which means
$N_{T}$=60*130=7800. The number of reported outliers is only 509 that shows an
accuracy of 94.21 % and, consequently, an error of 5.79 %. Distribution of
data length and obtained error is shown in figure 9. Just to mention that high
error rate in some cases were due to missing datapoint with the clinical
device, where our algorithm could perform much better for those corner cases.
We believe that further tuning our algorithm with more clinical data, we would
be able to build a groundbreaking approach for the fetal monitoring.

###  IV.1 Conclusions and Future Works

Fetal heart sound signals, generally, have low amplitude and are hidden by
high-amplitude noises that may come from the sounds of mother breathes, fetal
movements and other ambient sounds. In the present paper, an algorithm has
been developed for the estimation of fHR from fHS signals. Firstly, a pre-
processing task has been done for denoising based on wavelet transformation.
Then, a combination of enveloping and finding local maximum is applied for the
extraction of systole and diastole peaks. Further, systole peaks have been
selected using distance information between S-peaks and D-peaks. Finally, fHR
was calculated through a computation of interval times between the S-peaks.

On the basis of the obtained results and the comparison between those and the
ones obtained from simulated/clinical signals, we can conclude that our
proposed method is a promising tool for the identification of reliable fHR. In
future, by collecting more hours of annotated data with abnormalities, we
would like to address fetal anomaly classification analysis with sophisticated
machine learning techniques.

###  IV.2 Acknowledgements

The authors are grateful to the team of Mehr-e-Madar hospital and dedicated
gynecology clinic, for the clinical data acquisition.

## References

  * (1) J. Bai, F. W. Wong, A. Bauman, and M. Mohsin, “Parity and pregnancy outcomes,” _American journal of obstetrics and gynecology_ , vol. 186, no. 2, pp. 274–278, 2002.
  * (2) S. M. Abman, _Fetal and neonatal physiology_. Elsevier Publisher, 2011.
  * (3) N. E. Reichman, H. Corman, K. Noonan, and O. Schwartz-Soicher, “Parity and pregnancy outcomes,” _Review of economics of the household_ , vol. 8, no. 2, pp. 171–297, 2010.
  * (4) R. M. Grivell, Z. Alfirevic, G. M. Gyte, and D. Devane, “Antenatal cardiotocography for fetal assessment,” _Cochrane Database of Systematic Reviews_ , no. 9, 2015.
  * (5) M. Peters, J. Crowe, J.-F. Piéri, H. Quartero, B. Hayes-Gill, D. James, J. Stinstra, and S. Shakespeare, “Monitoring the fetal heart non-invasively: a review of methods,” 2001.
  * (6) M. Nassit and H. Berbia, “Non-invasive technologies of fetal heart rate diagnosis,” in _2015 Third World Conference on Complex Systems (WCCS)_. IEEE, 2015, pp. 1–5.
  * (7) L. W. Organ, “Scalp lead fetal electrocardiography.” _Canadian Medical Association Journal_ , vol. 98, no. 4, p. 199, 1968.
  * (8) M. P. Nageotte, “Fetal heart rate monitoring,” in _Seminars in Fetal and Neonatal Medicine_ , vol. 20, no. 3. Elsevier, 2015, pp. 144–148.
  * (9) T. Y. Euliano, M. T. Nguyen, S. Darmanjian, S. P. McGorray, N. Euliano, A. Onkala, and A. R. Gregg, “Monitoring uterine activity during labor: a comparison of 3 methods,” _American journal of obstetrics and gynecology_ , vol. 208, no. 1, pp. 66–e1, 2013.
  * (10) S. Alnuaimi, S. Jimaa, Y. Kimura, L. J. Hadjileontiadis, and A. H. Khandoker, “Fetal cardiac timing events estimation from doppler ultrasound signal cepstrum analysis,” in _2019 41st Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC)_. IEEE, 2019, pp. 4677–4681.
  * (11) D. Lanssens, S. Vonck, V. Storms, I. M. Thijs, L. Grieten, and W. Gyselaers, “The impact of a remote monitoring program on the prenatal follow-up of women with gestational hypertensive disorders,” _European Journal of Obstetrics & Gynecology and Reproductive Biology_, vol. 223, pp. 72–78, 2018\.
  * (12) J. F. Van Den Heuvel, T. K. Groenhof, J. H. Veerbeek, W. W. Van Solinge, A. T. Lely, A. Franx, and M. N. Bekker, “ehealth as the next-generation perinatal care: an overview of the literature,” _Journal of medical Internet research_ , vol. 20, no. 6, p. e9262, 2018.
  * (13) A. Strazza, A. Sbrollini, V. Di Battista, R. Ricci, L. Trillini, I. Marcantoni, M. Morettini, S. Fioretti, and L. Burattini, “Pcg-delineator: an efficient algorithm for automatic heart sounds detection in fetal phonocardiography,” in _2018 Computing in Cardiology Conference (CinC)_ , vol. 45. IEEE, 2018, pp. 1–4.
  * (14) H. Tang, J. Zhang, J. Sun, T. Qiu, and Y. Park, “Phonocardiogram signal compression using sound repetition and vector quantization,” _Computers in biology and medicine_ , vol. 71, pp. 24–34, 2016.
  * (15) N. Dia, J. Fontecave-Jallon, P.-Y. Guméry, and B. Rivet, “Heart rate estimation from phonocardiogram signals using non-negative matrix factorization,” in _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2019, pp. 1293–1297.
  * (16) M. Samieinasab and R. Sameni, “Fetal phonocardiogram extraction using single channel blind source separation,” in _2015 23rd Iranian Conference on Electrical Engineering_. IEEE, 2015, pp. 78–83.
  * (17) A. Khandoker, E. Ibrahim, S. Oshio, and Y. Kimura, “Validation of beat by beat fetal heart signals acquired from four-channel fetal phonocardiogram with fetal electrocardiogram in healthy late pregnancy,” _Scientific reports_ , vol. 8, no. 1, pp. 1–11, 2018.
  * (18) C. M. Company. Baby sound a pocket fetal doppler device. [Online]. Available: https://www.contecmed.com/index.php?page=shop.product_details&flypage=flypage.tpl&product_id=66&category_id=14&option=com_virtuemart&Itemid=606
  * (19) Sana meditech company. [Online]. Available: https://www.sanameditech.com/
  * (20) Baby heart beat device. [Online]. Available: http://www.oepm.es/es/signos_distintivos/detalle.html?mod=N&exp=0402889&bis=
  * (21) Bionet fc1400 fetal monitor. [Online]. Available: https://www.bionetus.com/fc1400-touch-screen-fetal-monitor/
  * (22) 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.
  * (23) Simulated fetal phonocardiograms data set. [Online]. Available: https://physionet.org/content/simfpcgdb/1.0.0/
  * (24) S. Schmidt, C. Holst-Hansen, C. Graff, E. Toft, and J. Struijk, “Detection of coronary artery disease with an electronic stethoscope,” in _2007 Computers in Cardiology_. IEEE, 2007, pp. 757–760.
  * (25) I. Daubechies, _Ten lectures on wavelets_. Society for industrial and applied mathematics, 1992.
  * (26) M. Nielsen, “On the construction and frequency localization of finite orthogonal quadrature filters,” _Journal of Approximation Theory_ , vol. 108, no. 1, pp. 36–52, 2001.
  * (27) C.-C. Chen and F. R. Tsui, “Comparing different wavelet transforms on removing electrocardiogram baseline wanders and special trends,” _BMC medical informatics and decision making_ , vol. 20, no. 11, pp. 1–10, 2020.
  * (28) S. Mallat, _A wavelet tour of signal processing_. Elsevier, 1999.
  * (29) G. Leigh, “Fast fir algorithms for the continuous wavelet transform from constrained least squares,” _Signal Processing, IEEE Transactions on_ , vol. 61, pp. 28–37, 2013.
  * (30) A. Teolis and J. J. Benedetto, _Computational signal processing with wavelets_. Springer, 1998, vol. 182.
  * (31) M. Rhif, A. Ben Abbes, I. R. Farah, B. Martínez, and Y. Sang, “Wavelet transform application for/in non-stationary time-series analysis: a review,” _Applied Sciences_ , vol. 9, no. 7, p. 1345, 2019.
  * (32) Y. Kozachenko, A. Olenko, and O. Polosmak, “Uniform convergence of compactly supported wavelet expansions of gaussian random processes,” _Communications in Statistics-Theory and Methods_ , vol. 43, no. 10-12, pp. 2549–2562, 2014.
  * (33) O. O. Anoh, R. A. Abd-Alhameed, S. Jones, J. M. Noras, Y. A. Dama, A. Altimimi, N. T. Ali, and M. Alkhambashi, “Comparison of orthogonal and biorthogonal wavelets for multicarrier systems,” in _2013 8th IEEE Design and Test Symposium_. IEEE, 2013, pp. 1–4.
  * (34) Y. Yang, Z. Peng, W. Zhang, and G. Meng, “Parameterised time-frequency analysis methods and their engineering applications: A review of recent advances,” _Mechanical Systems and Signal Processing_ , vol. 119, pp. 182–221, 2019.
  * (35) T. Omari and F. Bereksi-Reguig, “An automatic wavelet selection scheme for heart sounds denoising,” in _2014 International Work-Conference on Bioinformatics and Biomedical Engineering_ , 2014, pp. 1450–1462.
  * (36) M. Salwani and Y. Jasmy, “Relative wavelet energy as a tool to select suitable wavelet for artifact removal in eeg,” in _2005 1st International Conference on Computers, Communications, & Signal Processing with Special Track on Biomedical Engineering_. IEEE, 2005, pp. 282–287.
  * (37) O. A. Rosso, S. Blanco, J. Yordanova, V. Kolev, A. Figliola, M. Schürmann, and E. Başar, “Wavelet entropy: a new tool for analysis of short duration brain electrical signals,” _Journal of neuroscience methods_ , vol. 105, no. 1, pp. 65–75, 2001.
  * (38) E. Koutsiana, L. Hadjileontiadis, I. Chouvarda, and A. Khandoker, “Fetal heart sounds detection using wavelet transform and fractal dimension,” _Frontiers Bioengineering and Biotechnology_ , vol. 5, pp. 1–8, 2017.
  * (39) F. Kovács, C. Horváth, Á. T. Balogh, and G. Hosszú, “Fetal phonocardiography—past and future possibilities,” _Computer methods and programs in biomedicine_ , vol. 104, no. 1, pp. 19–25, 2011.
  * (40) H. Yang, P. Antonante, V. Tzoumas, and L. Carlone, “Graduated non-convexity for robust spatial perception: From non-minimal solvers to global outlier rejection,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 1127–1134, 2020.
  * (41) D. Giavarina, “Understanding bland altman analysis,” _Biochemia medica_ , vol. 25, no. 2, pp. 141–151, 2015.
  * (42) B. Hayes-Gill, S. Hassan, F. G. Mirza, S. Ommani, J. Himsworth, M. Solomon, R. Brown, B. S. Schifrin, and W. R. Cohen, “Accuracy and reliability of uterine contraction identification using abdominal surface electrodes,” _Clinical Medicine Insights: Women’s Health_ , vol. 5, pp. CMWH–S10 444, 2012.


# Local Propagation for Few-Shot Learning

Yann Lifchitz  Inria, Univ Rennes, CNRS, IRISA
Safran  Yannis Avrithis  Inria, Univ Rennes, CNRS, IRISA  Sylvaine Picard
Safran

###### Abstract

The challenge in few-shot learning is that available data is not enough to
capture the underlying distribution. To mitigate this, two emerging directions
are (a) using local image representations, essentially multiplying the amount
of data by a constant factor, and (b) using more unlabeled data, for instance
by transductive inference, jointly on a number of queries. In this work, we
bring these two ideas together, introducing _local propagation_. We treat
local image features as independent examples, we build a graph on them and we
use it to propagate both the features themselves and the labels, known and
unknown. Interestingly, since there is a number of features per image, even a
single query gives rise to transductive inference. As a result, we provide a
universally safe choice for few-shot inference under both non-transductive and
transductive settings, improving accuracy over corresponding methods. This is
in contrast to existing solutions, where one needs to choose the method
depending on the quantity of available data.

##  I Introduction

_Few-shot learning_ [1, 2, 3] is the problem of learning new tasks from few
examples, possibly transferring knowledge from previous tasks. Against the
mainstream paradigm of having lots of labeled data in deep learning, it limits
not only the amount of supervision but also the amount of data. Given the
variability of appearance in few-shot image classification benchmarks,
learning from few examples without knowledge of the underlying distribution is
truly challenging.

Few-shot learning has been little studied before deep learning [4]. Research
on few-shot learning is recently becoming very popular, but is not very
mature. On one hand, it is often connected to _meta-learning_ [5] in the sense
of learning to compare [1] or to optimize [6], giving rise to complex ideas
involving second-order derivatives. On the other hand, it boils down to
_representation learning_ , using _e.g_. metric learning [7] or parametric
classifiers [8], followed by nearest neighbor classifiers at inference [9].

While there are several approaches on _generating_ more data [3, 10], global
spatial pooling into compact image representations ignores the rich data that
is hidden in each given example. Each image is inherently a collection of
data, which has been exploited by _dense classification_ (DC) at
representation learning [11] and _naïve Bayes nearest neighbor_ (NBNN) [12] at
inference.

Using _unlabeled data_ is another popular direction of research, leveraging
existing results from transductive inference [13], semi-supervised learning
[14] and self-supervised representation learning [15]. _Graph-based methods_
are at the core of this effort, using for instance label propagation [13],
feature propagation [16] and graph neural networks [14].

This work is an attempt to bridge these two ideas, _i.e_., local
representations [12] and propagation [16], into a common framework.
Essentially, NBNN [12] measures the _average similarity_ of local
representations of a given image to local representations of all images in a
class; while feature or label propagation [16] replaces raw (Euclidean)
similarities with similarities taking into account the manifold structure of
the data distribution, and measures a single _manifold similarity_ of a given
image to a class. Our _local propagation_ combines both by measuring the
_average manifold similarity_ of local representations of a given image to
local representations of all images in a class.

Figure 1: CUB 5-way 5-shot classification accuracy _vs_. number of queries per
novel class. Our local label propagation (LP) outperforms transductive and
non-transductive baselines in all settings. By contrast, global LP only
competes with non-trasductive methods when at least 10 unlabelled queries are
available. Spatial attention (Att) is also our contribution. We use feature
propagation [16] for all methods. We use feature pooling for local
propagation. Please see section VI for more details.

Concretely, we learn a representation using DC [11] and we apply local
propagation at inference, without meta-learning: We break down the
convolutional activations of support and query images into pieces
corresponding to different spatial positions, consider all these pieces as
different examples, and then apply feature or label propagation [16] to these
examples. Pieces originating in support examples inherit their labels as in DC
[11] and NBNN [12], while pieces originating in queries are unlabeled. Since
there are a number of unlabeled pieces per image, this gives rise to
_transductive inference_ even in the case of a single query image. As shown in
Figure 1, this means that our method is a _universally safe choice_ regardless
of the amount of available unlabeled data.

In summary, we make the following contributions:

  * •

We study graph-based propagation on _local_ (pixel) and _semi-local_
(clusters) representations across of images for _feature and label
propagation_ for the first time.

  * •

We apply this idea to few-shot learning, effectively _generating_ more data
and _propagating_ through it, bringing even the case of single queries into
_transductive inference_.

  * •

We show that an extremely simple _spatial attention_ mechanism is not only
essential in our local propagation, but also brings significant gains in all
baselines.

  * •

We show consistent gains in most datasets and settings, including transductive
and non-transductive.

##  II Related work

Few shot learning. While studies before deep learning have been scarce [17,
18, 4], few-shot learning has become a very popular problem beginning mainly
from _matching networks_ [1] and _prototypical networks_ [2]. Seen as a _meta-
learning_ problem of learning to compare in episodes, these solutions amount
essentially to _metric learning_ , and indeed such methods have been revisited
in the context of few-shot learning [19, 7]. Simpler methods have highlighted
the importance of _representation learning_. These include for instance
nearest-neighbor classifiers without meta-learning [9] and simple variants of
supervised classifiers like a _cosine classifier_ [20, 21, 8].

More data. Since the main challenge in few-shot learning is the lack of data,
several approaches focus on finding more. These include _augmentation_ in the
feature space [22] or by combining spatial elements of images [23, 24],
_generation_ in the feature space [3] or images [25, 26], _image-to-image
translation_ [27, 10], using _base-class data_ [28, 29], or even _true
additional data_ , unlabeled [30] or weakly labeled [31]. By contrast, we
generate more data “for free” by just looking more carefully within the
existing data.

Transductive inference. Another possibility is to consider multiple queries
jointly and exploit their distribution, even though they are unlabeled. This
gives rise to transductive inference [32, 33, 13]. Most well-known are
_transductive propagation networks_ (TPN) [13], which use _label propagation_
[34] in a meta-learning setting. Recently, this direction is becoming very
popular [35, 36, 37, 38, 16, 39, 40]. Most related to our work is the very
recent _embedding propagation_ [16], which propagates the features as well as
the labels. We do the same without meta-learning and most importantly, all
propagation is _local_.

Semi/self-supervised learning. Using unlabeled data in an _inductive setting_
gives rise to _semi-supervised learning_ by using pseudo-labels [41], graph-
based methods [14], or feature-space augmentation [42, 22]. It is also common
to use auxiliary unsupervised objectives like _rotation_ [15, 22]. While we do
not address an inductive setting, our work is a direct extension of graph-
based methods, hence it can be applied to an inductive setting too, much like
label propagation itself [43], or combined with any other objective.

Attention. It is common to use attention and adaptation mechanisms in the
feature space [1, 44, 45, 21, 46, 47]. However, despite being the subject of a
pioneering work in 2005 [4], looking at local information in images has not
been studied more recently in few-shot learning, until _dense classification_
(DC) [11] and _naïve Bayes nearest neighbor_ (NBNN) [12]. We use the former
for representation learning. The latter is similar to our work in using local
representations at inference, the difference being that we apply propagation.
These works have been followed by studies on _spatial attention_ [48, 49, 50,
51] and _alignment_ [52, 53, 54, 55]. We experiment with an extremely simple
spatial attention mechanism in this work, which requires no learning and
boosts significantly all baselines.

Local propagation. Whatever is propagated (similarities, features, or labels),
there are two extremes in graph-based propagation. At one extreme, vertices
are _global_ representations of images, and the graph represents a dataset.
This can be used _e.g_. for similarity search [56] or semi-supervised
classification [57, 34]. At the other extreme, vertices are _local_
representations of pixels in an image, which can be used _e.g_. for
interactive [58, 59] or semantic [60] segmentation, or both [61]. _Regional
representations_ across images have been used for similarity search [62], but
we believe we are the first to use _local_ (pixel) or _semi-local_ (clusters)
representations across images for feature or label propagation.

##  III Preliminaries

Problem. A few-shot classification task comprises a dataset
$D\mathrel{:=}\\{(\mathbf{x}_{i},\mathbf{y}_{i})\\}_{i=1}^{n}$ of _support
examples_ $\mathbf{x}_{i}\in\mathcal{X}$ and _labels_ $\mathbf{y}_{i}$, where
$\mathcal{X}$ is an input space. Each label is represented by a _one-hot_
vector $\mathbf{y}_{i}\mathrel{:=}\mathbf{e}_{\ell_{i}}$, where
$\\{\mathbf{e}_{j}\\}_{j=1}^{c}$ is the standard basis of $\mathbb{R}^{c}$,
$\ell_{i}\in C$ is a _label index_ and
$C\mathrel{:=}[c]\mathrel{:=}\\{1,\dots,c\\}$ is a set of _novel (unseen)
classes_. The number $n$ of support examples is assumed to be small. The most
common setting is $s$ examples per novel class, with _e.g_.
$s\in\\{1,5,10\\}$, so that $n=cs$, referred to as _$c$ -way_, _$s$ -shot_
classification. The objective of the task is to learn a classifier
$f:\mathcal{X}\mapsto\mathbb{R}_{+}^{c}$ on the support data $D$. This
classifier maps a new _query example_ $\mathbf{x}$ from $\mathcal{X}$ to a
probability distribution $\mathbf{p}=f(\mathbf{x})$. A discrete _prediction_
$\pi(\mathbf{p})$ in $C$ follows, where

$\pi(\mathbf{p})\mathrel{:=}\arg\max_{j\in[c]}p_{j}$ (1)

is the class of of maximum probability and $p_{j}$ is the $j$-th element of
$\mathbf{p}$.

Before we are presented with few-shot classification tasks, we are given a
dataset
$\dot{D}\mathrel{:=}\\{(\dot{\mathbf{x}}_{i},\dot{\mathbf{y}}_{i})\\}_{i=1}^{\dot{n}}$
of _training examples_ $\dot{\mathbf{x}}_{i}\in\mathcal{X}$ and _labels_
$\dot{\mathbf{y}}_{i}\mathrel{:=}\mathbf{e}_{\dot{\ell}_{i}}$, where
$\dot{\ell}_{i}\in\dot{C}$ and $\dot{C}\mathrel{:=}[\dot{c}]$ is a set of
_base classes_ , disjoint from $C$. The number $\dot{n}$ of training examples
is assumed to be large enough to learn a _representation_ of data in
$\mathcal{X}$, or otherwise accumulate knowledge that facilitates solving new
tasks. We call this process _base training_. The problem of few-shot
classification amounts to designing both the base training process given
$\dot{D}$ and how to solve new tasks given $D$.

Transductive setting. It is possible that in each few-shot classification task
we are given a _set_ $Q\mathrel{:=}\\{\mathbf{q}_{i}\\}_{i=1}^{q}$ of query
examples and a prediction is required for all queries in $Q$. In this case,
although query examples are unlabeled, we can take advantage of this
additional data and learn a classifier $f$ that is a function of both the
labeled support data $D$ and the unlabeled queries $Q$. This transductive
setting implies _semi-supervised learning_.

Representation. The classifier is built on top of an _embedding function_
$\phi_{\theta}:\mathcal{X}\to\mathbb{R}^{r\times d}$, with parameters $\theta$
that are learned at base training. Given an example
$\mathbf{x}\in\mathcal{X}$, this function yields a $r\times d$ _feature
tensor_ $\phi_{\theta}(\mathbf{x})$, where $r$ represents the dimensions of a
spatial domain $\Omega$ and $d$ the feature dimensions. For $\mathcal{X}$
comprising 2D images, the feature is a $w\times h\times d$ tensor that is the
activation of the last convolutional layer, $r\mathrel{:=}w\times h$ is the
spatial resolution and $\Omega\mathrel{:=}[w]\times[h]$ is the spatial domain.
The feature can still be a vector in $\mathbb{R}^{d}$ in the special case
$r=1$, _e.g_. using _global spatial pooling_. The feature tensor
$F\mathrel{:=}\phi_{\theta}(\mathbf{x})$ contains a feature vector
$F(\mathbf{r})=\phi_{\theta}(\mathbf{x})(\mathbf{r})\in\mathbb{R}^{d}$ for
each spatial position $\mathbf{r}\in\Omega$.

##  IV Background

Cosine classifier. Initially used in face verification [63, 64], a simple form
of base training that was introduced to few-shot learning independently by Qi
_et al_. [20] and Gidaris and Komodakis [21], is to learn a parametric linear
classifier that consists of a fully-connected layer without bias on top of the
embedding function $\phi_{\theta}$, followed by softmax and cross-entropy. If
$W\mathrel{:=}(\dot{\mathbf{w}}_{j})_{j=1}^{\dot{c}}$ is the collection of
class weights with $\dot{\mathbf{w}}_{j}\in\mathbb{R}^{r\times d}$, the
classifier is defined by

$\displaystyle
f_{\theta,W}(\mathbf{x})\mathrel{:=}{\boldsymbol{\sigma}}\left(\rho[\cos(\phi_{\theta}(\mathbf{x}),\dot{\mathbf{w}}_{j})]_{j=1}^{\dot{c}}\right),$
(2)

for $\mathbf{x}\in\mathcal{X}$, where $\cos$ is _cosine similarity_ ,
$\rho\in\mathbb{R}^{+}$ is a trainable _scale parameter_ and
${\boldsymbol{\sigma}}:\mathbb{R}^{m}\to\mathbb{R}_{+}^{m}$ is the _softmax
function_
${\boldsymbol{\sigma}}(\mathbf{a})\mathrel{:=}(e^{a_{1}},\dots,e^{a_{\dot{c}}})/\sum_{j}e^{a_{j}}$
for $\mathbf{a}\in\mathbb{R}^{\dot{c}}$. The representations (features and
class weights) either retain resolution $r>1$ and are _flattened_ to vectors
of length $rd$, or are _pooled_ to vectors of length $d$ ($r=1$), by global
spatial pooling. Base training amounts to minimizing the _cost function_

$\displaystyle
J(\dot{D};\theta,W)\mathrel{:=}\sum_{i=1}^{n}\ell(f_{\theta,W}(\dot{\mathbf{x}}_{i}),\dot{\mathbf{y}}_{i})$
(3)

over $\theta,W$, where
$\ell(\mathbf{p},\mathbf{y})\mathrel{:=}-\log\left\langle{\mathbf{y},\mathbf{p}}\right\rangle$
for $\mathbf{y}\in\\{0,1\\}^{\dot{c}}$ and
$\mathbf{p}\in\mathbb{R}_{+}^{\dot{c}}$, is the _cross-entropy_ loss.

Prototypes. A popular classifier for few-shot classification tasks is the
_prototype classifier_ , introduced by Snell _et al_. [2]. If
$\mathcal{I}_{j}\mathrel{:=}\\{i\in[n]:\mathbf{y}_{i}=\mathbf{e}_{j}\\}$
denotes the indices of support examples labeled in class $j$, then the
_prototype_ of this class $j$ is given by the average features

$\displaystyle{\boldsymbol{\mu}}_{j}\mathrel{:=}\frac{1}{|\mathcal{I}_{j}|}\sum_{i\in\mathcal{I}_{j}}\phi_{\theta}(\mathbf{x}_{i})$
(4)

of those examples for $j\in C$. Again, features are either flattened or pooled
to vectors first. Then, denoting by
$M\mathrel{:=}({\boldsymbol{\mu}}_{j})_{j=1}^{c}$ the collection of
prototypes, a query $\mathbf{x}\in\mathcal{X}$ is mapped to
$f_{\theta,M}(\mathbf{x})$, as defined by (2).

Naïve Bayes nearest neighbor (NBNN). In the revival [12] of the classic image-
to-class approach [65], one collects, for each class $j\in[c]$, the features
$V_{j}\mathrel{:=}\\{\phi_{\theta}(\mathbf{x}_{i})(\mathbf{r})\\}_{i\in\mathcal{I}_{j},\mathbf{r}\in\Omega}$
of all spatial positions of all support examples labeled in class $j$. Then,
given a query $\mathbf{x}\in\mathcal{X}$ with feature tensor
$F\mathrel{:=}\phi_{\theta}(\mathbf{x})$, for each class $j$, a score

$\displaystyle
s_{j}(F)\mathrel{:=}\sum_{\mathbf{r}\in\Omega}\sum_{\mathbf{v}\in\text{NN}_{V_{j}}(F(\mathbf{r}))}\cos(F(\mathbf{r}),\mathbf{v})$
(5)

is defined as the average cosine similarity over the features $F(\mathbf{r})$
at all spatial positions $\mathbf{r}\in\Omega$ and their $k$-nearest neighbors
$\text{NN}_{V_{j}}(F(\mathbf{r}))$ in $V_{j}$. Then, the prediction for
$\mathbf{x}$ is the class of maximum score.

##  V Local propagation

###  V-A Base training

Dense classifier. We use a _dense classifier_ for base training, introduced by
Lifchitz _et al_. [11]. Rather than flattening or pooling, the classifier
$f_{\theta,W}:\mathcal{X}\to\mathbb{R}_{+}^{r\times\dot{c}}$ maps an example
$\mathbf{x}$ to a tensor of probabilities over spatial positions, by applying
a cosine classifier (2) densely at each position

$\displaystyle
f_{\theta,W}(\mathbf{x})\mathrel{:=}\left[{\boldsymbol{\sigma}}\left(\rho[\cos(\phi_{\theta}(\mathbf{x})(\mathbf{r}),\dot{\mathbf{w}}_{j})]_{j=1}^{\dot{c}}\right)\right]_{\mathbf{r}\in\Omega},$
(6)

where the class weights $W$ are shared over locations with
$\dot{\mathbf{w}}_{j}\in\mathbb{R}^{d}$. Cross-entropy applies to all spatial
positions using the same class label, and cost function (3) becomes

$\displaystyle
J(\dot{D};\theta,W)\mathrel{:=}\sum_{i=1}^{n}\sum_{\mathbf{r}\in\Omega}\ell(f_{\theta,W}(\dot{\mathbf{x}}_{i})(\mathbf{r}),\dot{\mathbf{y}}_{i}).$
(7)

Local spatial pooling. Dense classification avoids global spatial pooling by
going to the other extreme of applying the loss to every position. This
happens regardless of whether the effective receptive field is large enough to
represent the class at hand, so it assumes an appropriate resolution of the
feature tensor. However, it has been observed that it helps to use input
images of higher resolution than the standard benchmarks [66], which we
follow. This results in features of accordingly higher resolution, where each
position corresponds to small details. We solve this by applying _local
spatial pooling_ on the feature tensor, both before dense classification at
base training as well as at new classification tasks.

|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
Figure 2: Examples of images, each with the corresponding spatial attention
heatmap and clusters used in feature pooling (black indicates regions below
threshold in the heatmap). The first two lines correspond to CUB, the last two
to _mini_ ImageNet. We use $\tau=0.3$ for spatial attention and $m=10$ for
feature pooling.

###  V-B Few-shot classification

Spatial attention. Before we can use features of all spatial positions as
data, it is important to suppress the background, which appears frequently
across positions and images, without being discriminative for the
classification task. There are different approaches, such as learning a class-
agnostic _spatial attention_ mechanism [48, 49] or simply by a form of pooling
over feature channels [67]. We follow the latter approach. In particular,
given an example $\mathbf{x}\in\mathcal{X}$ with feature tensor
$F\mathrel{:=}\phi_{\theta}(\mathbf{x})$, we select a subset of feature
vectors $a(F)\subset\mathbb{R}^{d}$ at spatial positions $\mathbf{r}\in\Omega$
where the $\ell_{2}$-norm is at least $\tau>0$ relative to the maximum over
the domain:

$\displaystyle
a(F)\mathrel{:=}\\{F(\mathbf{r}):\|F(\mathbf{r})\|\geq\tau\max_{\mathbf{t}\in\Omega}\|F(\mathbf{t})\|,\mathbf{r}\in\Omega\\}.$
(8)

Examples are shown in Figure 2. We find this mechanism particularly effective
for its simplicity, not only for our method, but also for all baselines. No
spatial attention is a special case where $\tau=0$.

Feature pooling. Propagation tends to amplify elements that appear frequently
in a dataset. Local propagation does the same for elements originating from
different spatial positions, which in turn depends on the scale of objects
relative to the spatial resolution. This can be particularly harmful with
elements originating from background clutter and bypass condition (8), exactly
because they appear frequently.

To obtain a fixed-size representation that only depends on the content, we
perform pooling in the feature space into a fixed number of vectors per
example. We do so by _clustering_ : given an example
$\mathbf{x}\in\mathcal{X}$ with selected feature vectors
$a(\phi_{\theta}(\mathbf{x}))$ (8), we obtain $m$ clusters by $k$-means. We
represent the corresponding $m$ _feature centroids_ as columns in the $d\times
m$ matrix $g_{\theta}(\mathbf{x})$. Examples are shown in Figure 2. We use
this representation only for local propagation. Global propagation and no
feature pooling are special cases where $m=1$ and $m=w\times h$ respectively.

Local propagation. We develop this idea under the transductive setting because
it is more general: The non-transductive is the special case where $q=1$, the
set of queries $Q=\\{\mathbf{q}_{1}\\}$ is singleton and we are making a
prediction for $\mathbf{q}_{1}$. Given the support examples in $D$ and queries
$Q$, we represent the feature centroids of both as columns in the $d\times t$
matrix

$\displaystyle
V\mathrel{:=}\left(\begin{array}[]{cccccc}g_{\theta}(\mathbf{x}_{1})&\dots&g_{\theta}(\mathbf{x}_{n})&g_{\theta}(\mathbf{q}_{1})&\dots&g_{\theta}(\mathbf{q}_{q})\end{array}\right)$
(10)

where $t\mathrel{:=}(n+q)m$. Following [62], we use the pairwise similarity
function
$s(\mathbf{v}_{1},\mathbf{v}_{2})\mathrel{:=}[\cos(\mathbf{v}_{1},\mathbf{v}_{2})]_{+}^{\gamma}$
where $\gamma>1$, and construct the reciprocal _$k$ -nearest neighbor graph_
of the columns of $V$, represented by the $t\times t$ symmetric nonnegative
_adjacency matrix_ $W_{V}$ with zero diagonal. Following [34], this matrix is
symmetrically normalized as
$\mathcal{W}_{V}\mathrel{:=}D_{V}^{-1/2}W_{V}D_{V}^{-1/2}$, where
$D_{V}\mathrel{:=}W_{V}\mathbf{1}_{t}$ is the _degree matrix_ of the graph and
$\mathbf{1}_{t}$ is the $t\times 1$ all-ones vector.

Extending [34], given any matrix $A\in\mathbb{R}^{u\times t}$ (or row vector
for $u=1$), its _propagation_ on $V$ is defined as

$\displaystyle p_{V}(A)\mathrel{:=}A(1-\alpha)(I-\alpha\mathcal{W}_{V})^{-1}.$
(11)

This is a smoothing operation on the graph of $V$, where parameter
$\alpha\in[0,1)$ controls the amount of smoothing: Columns of $A$
corresponding to similar columns of $V$ are averaged together. It is
infinitely-recursive, as revealed by the series expansion of the matrix
inverse [34].

The operation (11) is called _local propagation_ because the graph is defined
on local representations originating from different spatial positions of the
given images. _Global propagation_ is the special case of having $m=1$ cluster
per image. This is the same as _global average pooling_ (GAP), with or without
spatial attention.

Local feature propagation. Using $A=V$, $u=d$ in (11), _local feature
propagation_ amounts to propagating $V$ on itself:

$\displaystyle\widetilde{V}\mathrel{:=}p_{V}(V),$ (12)

in the sense that similar feature vectors in columns of $V$ are averaged
together, becoming even more similar. No feature propagation is a special case
where $\alpha=0$, $\widetilde{V}=V$.

|  |  |  |  |
---|---|---|---|---|---
| (a) |  |  | (b) |
|  |  |  |  |
| (c) |  |  | (d) |
Figure 3: Examples of CUB query images in 5-way 5-shot non-transductive tasks,
each followed by the heatmap of predicted probability for the correct class
using a prototype classifier, then using local label propagation. (a), (b)
Local label propagation helps classifying to the correct class. (c) Both give
a correct prediction. (d) Local label propagation fails.

Local label propagation. Given the propagated features $\widetilde{V}$ (12),
we form a new graph with normalized adjacency matrix
$\mathcal{W}_{\widetilde{V}}$. Extending [34], we form the $c\times t$ zero-
one _label matrix_ $Y$ with one row per class and one column per spatial
position over support examples and queries. A column corresponding to a
spatial position of a support example $\mathbf{x}_{i}$ is defined as the one-
hot label vector $\mathbf{y}_{i}$; a column corresponding to a position of a
query $\mathbf{q}_{i}$ is zero:

$\displaystyle
Y\mathrel{:=}\left(\begin{array}[]{cccccc}\mathbf{y}_{1}\mathbf{1}_{m}^{\top}&\dots&\mathbf{y}_{n}\mathbf{1}_{m}^{\top}&\mathbf{0}_{c\times
m}&\dots&\mathbf{0}_{c\times m}\end{array}\right)$ (14)

where $\mathbf{0}_{c\times m}$ is the $c\times m$ zero matrix and there are
$q$ such matrices. Using $A=Y$, $u=c$ in (11), _local label propagation_ then
amounts to propagating $Y$ on $\widetilde{V}$:

$\displaystyle\widetilde{Y}\mathrel{:=}p_{\widetilde{V}}(Y),$ (15)

such that spatial positions with similar feature vectors obtain similar class
scores. This may make little difference on labeled (support) examples, but is
a mechanism for spatial positions of _unlabeled_ (query) examples to obtain
label information as propagated from spatial positions of labeled examples
with similar features.

Inference. In $c\times t$ matrix $\widetilde{Y}$ (15), there is one row per
class and one column per spatial position over support examples and queries.
$\widetilde{Y}$ is nonnegative; by column-wise $\ell_{1}$-normalizing it into
$c\times t$ matrix $\hat{Y}$, we can interpret columns as probability
distributions over classes per position. For each query example
$\mathbf{q}_{i}$, if $\hat{Y}_{i}$ is the corresponding $c\times m$ submatrix
of $\hat{Y}$, we average these distributions over positions, obtaining a
distribution $\mathbf{p}_{i}\mathrel{:=}\hat{Y}_{i}\mathbf{1}_{m}/m$. Finally,
as in (1), we make a discrete prediction
$\pi(\mathbf{p}_{i})=\arg\max_{j\in[c]}p_{ij}$ as the class of maximum
probability. This operation is similar to NBNN (5), but the quantities being
averaged have undergone propagation rather than being direct similarities.
Figure 3 shows examples of predicted probability for the correct class per
spatial location. Local label propagation results in spatially smooth
predictions that covers a large portion of the object.

##  VI Experiments

###  VI-A Experimental setup

Datasets. We evaluate our method on two datasets that are common in few-shot
learning. The first, _Mini_ ImageNet, is a subset of ImageNet ILSVRC-12 [68].
It contains 600 images for each of its 100 classes. Following the work of Ravi
and Larochelle [69], we use 64 classes for base training, 16 classes for
validation and 20 classes for test. We resample all images to 224$\times$224,
similarily to [8, 66]. The second dataset, CUB-200-2011 [70], referred to as
CUB below, was introduced to few-shot learning by Hilliard _et al_. [71]. It
contains 11,788 images from 200 distinct bird species. Following the splits of
Ye _et al_. [72], we use 100 classes for base training, 50 for validation and
50 for testing. We crop images using bounding box annotations and resample
them to 224$\times$224.

Network. We test our method on a ResNet-12 embedding network. Introduced in
[46], this network is now commonly used in the few-shot learning community.
With input images of size 224$\times$224, the embedding features are tensors
of resolution 14$\times$14\. To adapt the the larger images before applying a
dense classifier [11], we apply average pooling on these feature tensors, with
kernel size 3$\times$3 and stride 1 without padding. The resulting tensors are
of resolution 12$\times$12.

Base Training. We train the network from scratch using stochastic gradient
descent with Nesterov momentum on mini-batches of size 32. The learning rate
schedule is set according to the 5-way 5-shot validation accuracy.

Evaluation protocol. For each dataset, we obtain a unique embedding network
resulting from base training. All methods are then applied to the same
features. For all experiments, we sample 2000 5-way few-shot tasks from the
test set, each with 15 queries per class. We report average accuracy as well
as 95% confidence interval. We evaluate two different settings: In the _non-
transductive_ setting, queries are treated as 75 distinct sets $Q$ with only
one query each, whereas in the _transductive_ setting, there is a single set
$Q$ with all 75 queries.

Baselines. In the _non-transductive_ setting, we compare our method with
variants of four existing few-shot inference methods. The first, referred to
as GAP+Proto, applies _global average pooling_ (GAP) on feature tensors and
then uses a prototype classifier [2] on the support set (4). The second is the
inference mechanism of the matching network [1], while the third, referred to
as Local Match, is a modified version as follows. For each support example
$\mathbf{x}$ with feature tensor $F\mathrel{:=}\phi_{\theta}(\mathbf{x})$, we
use local feature vectors $F(\mathbf{r})$ at all positions
$\mathbf{r}\in\Omega$ as independent support examples, with the same label as
$\mathbf{x}$. We do the same on queries and average the class score vectors
over positions. The fourth is the inference mechanism of NBNN [12] (5). For
each method, we experiment with and without our spatial attention mechanism
(8). For Local Match and NBNN, we select a subset of local features per image.
For GAP+Proto and Matching Net, we apply GAP to the selected subset only.

In the _transductive_ setting, we compare with the inference mechanism of
global label propagation [13, 16], with and without global embedding
propagation [16]. These baselines are again evaluated with and without spatial
attention. We always include spatial attention in our local propagation, but
we experiment with and without feature pooling, with and without feature
propagation.

Figure 4: _Spatial attention_ on GAP+Proto [2]: 5-way few-shot classification
accuracy _vs_. threshold $\tau$, relative to $\tau=0$ (no attention). Figure
5: _Spatial attention_ on our local label propagation, including feature
pooling and feature propagation: 5-way few-shot classification accuracy _vs_.
threshold $\tau$, relative to $\tau=0$ (no attention). All other parameters
fixed to optimal.

###  VI-B Ablation studies

Overall, our method has five parameters. Two refer to optional components
related to local information: the threshold $\tau$ for spatial attention and
the number of clusters $m$ for feature pooling. The other three refer to
propagation, like all related methods dating back to [34]: the number of
neighbors $k$ in the graph, the exponent $\gamma$ in the feature similarity
function and $\alpha$, controlling the amount of the smoothing. For all
experiments, we perform a fairly exhaustive parameter search over a small set
of possible values per parameter and we make choices according to validation
accuracy. We present a summary of parameter search independently for $\tau$
and $m$, keeping other parameters fixed to the optimal.

Spatial Attention. As shown in Figure 4, referring to GAP+Proto baseline,
there is an optimal range of $\tau$ in $[0.3,0.5]$, such that we filter out
the uniformative local feature without removing too much information. The same
behavior appears in Figure 5, referring to our best method for each setting.
For the remaining of the experiments, we fix $\tau$ to 0.3.

Feature pooling. This is a compromise between global pooling and a full set of
local features per image, which brings a consistent small improvement compared
to both, while making local propagation more efficient by limiting the graph
size. According to Figure 6, referring again to our best method for each
setting, there is an optimal number $m$ of clusters that depends on the
dataset and setting (transductive or not, 1/5-shot). On CUB, we use $m=40$ for
1-shot and $m=60$ for 5-shot. On _mini_ ImageNet, we use $m=60$ in both cases.

Propagation parameters. Propagation has been extensively researched in the
past, so we do not report the study of its parameters. It is known for
instance that $\alpha$ should be close to $1$ and there is a local maximum
with respect to $k$, which depends on the quantity of the data [62]. After
parameter search, for most experiments we set $\alpha=0.9$, $\gamma=4$, and
$k=5$, $k=50$ respectively for global and local propagation.

Figure 6: _Feature pooling_ on our local propagation: 5-way few-shot
classification accuracy _vs_. number of clusters $m$, relative to $m=10$ for
better visualization. TR: transductive. We use spatial attention in all
settings and feature propagation only in transductive. All other parameters
fixed to optimal.

###  VI-C Results

Table I presents a complete set of results our method and baselines in
different settings, using different options. We discuss the effect of our
contributions below.

Spatial attention. We use spatial attention with our method but we also
combine it with baselines for fair comparison. It is an extremely simple
mechanism that consistently improves few-shot classification accuracy in most
cases, including global or local, with propagation or not, transductive or
not. The only exception is Local Match on _mini_ ImageNet. The gain is more
pronounced on 1-shot tasks, which is expected as information selection is more
important when information is scarce. It reaches 3% for the baselines and 2%
for propagation on CUB, as well as 1% on _mini_ ImageNet.

Feature pooling. Clustering the set of local features into a given number of
clusters for each image is bringing small accuracy improvements when combined
with propagation, local or global. In particular, spatial attention and
feature pooling brings a 0.30% to 0.75% increase of accuracy compared to
spatial attention alone on CUB (transductive and non-transductive). An
exception is _mini_ ImageNet non-transductive where feature pooling gives
slightly worse accuracy by an insignificant margin.

Label propagation. In the _non-transductive_ setting, global label propagation
fails. Its performance is similar or inferior to GAP+Protonet. This is to be
expected, as this is method a transductive method, so it is not a natural
choice given only one query. By contrast, our local label propagation succeeds
even in this setting, with up to 2.7% improvement on CUB 5-way 1-shot compared
to GAP+Proto. One exception is _mini_ ImageNet 5-way 1-shot, where GAP+Proto
is better by a small margin; in this case however, the other local baselines
(Local Match and NBNN) are worse than both GAP+Proto and our local label
propagation, by a larger margin.

In the _transductive_ setting, label propagation, global or local, always
helps by using unlabeled data. Our local label propagation with spatial
attention and feature pooling improves 5-way 1-shot accuracy over the non-
transductive setting by 6% and 5.5%, on CUB and _mini_ ImageNet respectively.
This improvement is lower for 5-shot tasks as more labeled data are used.
Compared with global label propagation, it improves by up to 1.5% on 5-shot,
CUB and _mini_ ImageNet.

Feature propagation. In the _non-transductive_ setting, feature propagation is
mostly harmful, especially when used with our local label propagation, which
remains the best option, together with feature pooling. In the _transductive_
setting however, it helps both global and local label propagation, the only
exception being 5-shot, _mini_ ImageNet. In the case of local label
propagation with feature pooling, the gain is up to 2% and 1.5% on 1-shot, CUB
and _mini_ ImageNet respectively. Therefore this combination is the most
effective, improving over our best non transductive result by 8% and 6.5% on
1-shot, CUB and _mini_ ImageNet respectively.

Universality. As shown in Figure 1, our local label propagation is a
_universally safe choice_ for few-shot inference under both transductive and
non-transductive settings. This is in contrast to existing methods such as
global label propagation, where the user needs to make decisions depending on
the amount of unlabeled data that is available.

Comparison to existing methods. Table I also includes a number of recent few-
shot learning methods. For fair comparison, all reported results are using the
same ResNet12 as embedding network. We observe that our baseline GAP+Proto is
better than these models on non-transductive 5-shot classification on _mini_
ImageNet. Our method is then outperforming those models as well. In the
transductive setting, global propagation is weaker than existing methods, but
our best setting of local propagation (including spatial attention, feature
pooling, feature propagation and label propagation) is stronger in general.
The only exception is 1-shot classification on CUB, where LR+ICI [13] is
stronger by a small margin.

In parallel with this work, two methods appeared very recently, which are
stronger than our solution on _mini_ ImageNet but weaker on CUB: (1) DGPN
[40], which is yet another graph-based method and could be easily integrated
with our local propagation. (2) DeepEMD [55], which is based on pairwise image
alignment. This is more challenging to integrate, for instance one would need
to use alignment in the definition of the graph itself. This can be
interesting future work.

Method | A | P | F | CUB |  _mini_ ImageNet
---|---|---|---|---|---
1-shot | 5-shot | 1-shot | 5-shot
GAP+Proto [2] |  |  |  |  74.85$\pm$0.48 |  90.38$\pm$0.27 |  63.39$\pm$0.46 |  81.21$\pm$0.32
GAP+Proto [2] | ✓ |  |  |  77.10$\pm$0.47 |  91.24$\pm$0.26 |  64.22$\pm$0.45 |  81.71$\pm$0.31
Matching Net [1] |  |  |  |  74.85$\pm$0.48 |  89.23$\pm$0.29 |  63.39$\pm$0.46 |  78.14$\pm$0.33
Matching Net [1] | ✓ |  |  |  77.10$\pm$0.47 |  89.95$\pm$0.28 |  64.22$\pm$0.45 |  78.70$\pm$0.33
Local Match [1] |  |  |  |  75.92$\pm$0.46 |  89.16$\pm$0.28 |  64.05$\pm$0.46 |  78.45$\pm$0.34
Local Match [1] | ✓ |  |  |  78.29$\pm$0.45 |  90.60$\pm$0.26 |  63.58$\pm$0.46 |  78.01$\pm$0.35
NBNN [12] |  |  |  |  76.21$\pm$0.45 |  89.59$\pm$0.27 |  64.90$\pm$0.45 |  79.74$\pm$0.32
NBNN [12] | ✓ |  |  |  79.14$\pm$0.44 |  91.40$\pm$0.25 |  65.18$\pm$0.45 |  80.00$\pm$0.31
Global Label Propagation, Non-Transductive
Propagation |  |  |  |  74.69$\pm$0.48 |  87.96$\pm$0.30 |  63.39$\pm$0.46 |  75.89$\pm$0.36
✓ |  |  |  76.94$\pm$0.47 |  89.14$\pm$0.30 |  64.22$\pm$0.45 |  76.40$\pm$0.36
✓ |  | ✓ |  77.23$\pm$0.46 |  88.78$\pm$0.31 |  63.41$\pm$0.45 |  77.04$\pm$0.37
Local Label Propagation (this work), Non-Transductive
Propagation |  |  |  |  78.24$\pm$0.44 |  91.07$\pm$0.26 |  65.52$\pm$0.45 |  80.49$\pm$0.31
✓ |  |  |  79.02$\pm$0.44 |  91.81$\pm$0.25 | 65.74$\pm$0.45 | 81.13$\pm$0.31
✓ | ✓ |  | 79.77$\pm$0.44 | 92.07$\pm$0.25 |  65.59$\pm$0.45 |  80.73$\pm$0.31
✓ | ✓ | ✓ |  79.32$\pm$0.44 |  91.52$\pm$0.25 |  64.43$\pm$0.45 |  80.26$\pm$0.32
Global Label Propagation, Transductive
Propagation |  |  |  |  83.64$\pm$0.48 |  90.63$\pm$0.27 |  70.07$\pm$0.51 |  80.96$\pm$0.34
✓ |  |  |  85.52$\pm$0.46 |  91.67$\pm$0.27 |  70.67$\pm$0.51 |  81.44$\pm$0.33
✓ |  | ✓ |  87.18$\pm$0.46 |  91.88$\pm$0.27 |  72.54$\pm$0.54 |  81.38$\pm$0.35
Local Label Propagation (this work), Transductive
Propagation |  |  |  |  83.04$\pm$0.43 |  91.89$\pm$0.25 |  69.95$\pm$0.48 |  82.13$\pm$0.31
✓ |  |  |  85.33$\pm$0.42 |  92.50$\pm$0.25 |  71.00$\pm$0.48 | 82.87$\pm$0.30
✓ | ✓ |  |  85.80$\pm$0.41 |  92.92$\pm$0.24 |  71.12$\pm$0.48 |  82.83$\pm$0.31
✓ | ✓ | ✓ | 87.77$\pm$0.41 | 93.35$\pm$0.23 | 72.57$\pm$0.51 |  82.76$\pm$0.33
Other models, Non-Transductive
SNAIL [44] |  |  |  | - | - |  55.71$\pm$0.99 |  68.88$\pm$0.92
TADAM [46] |  |  |  | - | - |  58.50$\pm$0.30 |  76.70$\pm$0.30
DC+IMP [11] |  |  |  | - | - |  62.53$\pm$0.19 |  79.77$\pm$0.19
Neg-Cosine [73] |  |  |  | - | - |  62.33$\pm$0.82 |  80.94$\pm$0.59
Other models, Transductive
TPN [13] |  |  |  | - | - |  59.46$\pm$0.00 |  75.65$\pm$0.00
LR+ICI [39] |  |  |  |  88.06$\pm$0.00 |  92.53$\pm$0.00 |  66.80$\pm$0.00 |  79.26$\pm$0.00
EPNet [16] |  |  |  |  82.85$\pm$0.81 |  91.32$\pm$0.41 |  66.50$\pm$0.89 |  81.06$\pm$0.60
TABLE I: 5-way few-shot classification accuracy, comparing our local (feature
and label) propagation to baselines and existing work. A: spatial attention
(our work, also applied to baselines). P: feature pooling (clustering) (our
work). F: feature propagation [16].

##  VII Conclusion

Our _local propagation_ framework takes the best of both worlds: more data
from local representations and better use of this data from propagation. It
provides a unified solution that works well given few labeled data and an
arbitrary number of unlabeled data. As a result, it works better that
solutions meant for the standard few-shot inference and at the same time
better than solutions meant for transductive few-shot inference. Two secondary
contributions are extremely simple and effective: (a) our _feature pooling_
helps control the additional cost related to local features, while improving
performance in most cases; (b) our _spatial attention_ helps not only our
method but all baselines too, by a significant margin on 1-shot
classification. Our solution only affects inference, so it can easily be
plugged into any alternative representation learning method. It is general
enough to integrate other state-of-the-art solutions, like pairwise image
alignment, other forms of propagation and propagation on several layers.

## References

  * [1] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra _et al._ , “Matching networks for one shot learning,” in _NIPS_ , 2016.
  * [2] J. Snell, K. Swersky, and R. Zemel, “Prototypical networks for few-shot learning,” in _NIPS_ , 2017.
  * [3] Y.-X. Wang, R. Girshick, M. Hebert, and B. Hariharan, “Low-shot learning from imaginary data,” in _CVPR_ , 2018.
  * [4] E. Bart and S. Ullman, “Cross-generalization: Learning novel classes from a single example by feature replacement,” in _CVPR_ , 2005.
  * [5] R. Vilalta and Y. Drissi, “A perspective view and survey of meta-learning,” _Artificial Intelligence Review_ , vol. 18, no. 2, pp. 77–95, 2002.
  * [6] C. Finn, P. Abbeel, and S. Levine, “Model-agnostic meta-learning for fast adaptation of deep networks,” in _ICML_ , 2017.
  * [7] X. Li, L. Yu, C.-W. Fu, M. Fang, and P.-A. Heng, “Revisiting metric learning for few-shot image classification,” _arXiv preprint arXiv:1907.03123_ , 2019\.
  * [8] W. Chen, Y. Liu, Z. Kira, Y. F. Wang, and J. Huang, “A closer look at few-shot classification,” _ICLR_ , 2019.
  * [9] Y. Wang, W.-L. Chao, K. Q. Weinberger, and L. van der Maaten, “SimpleShot: Revisiting nearest-neighbor classification for few-shot learning,” _arXiv preprint arXiv:1911.04623_ , 2019.
  * [10] Y. Wang, S. Khan, A. Gonzalez-Garcia, J. v. d. Weijer, and F. S. Khan, “Semi-supervised learning for few-shot image-to-image translation,” in _CVPR_ , 2020.
  * [11] Y. Lifchitz, Y. Avrithis, S. Picard, and A. Bursuc, “Dense classification and implanting for few-shot learning,” _CVPR_ , 2019.
  * [12] W. Li, L. Wang, J. Xu, J. Huo, Y. Gao, and J. Luo, “Revisiting local descriptor based image-to-class measure for few-shot learning,” in _CVPR_ , 2019.
  * [13] Y. Liu, J. Lee, M. Park, S. Kim, E. Yang, S. Hwang, and Y. Yang, “Learning to propagate labels: Transductive propagation network for few-shot learning,” in _ICLR_ , 2019.
  * [14] V. Garcia and J. Bruna, “Few-shot learning with graph neural networks,” in _ICLR_ , 2018.
  * [15] S. Gidaris, A. Bursuc, N. Komodakis, P. Pérez, and M. Cord, “Boosting few-shot visual learning with self-supervision,” in _ICCV_ , 2019.
  * [16] P. Rodríguez, I. Laradji, A. Drouin, and A. Lacoste, “Embedding propagation: Smoother manifold for few-shot classification,” _arXiv preprint arXiv:2003.04151_ , 2020.
  * [17] E. G. Miller, N. E. Matsakis, and P. A. Viola, “Learning from one example through shared densities on transforms,” in _CVPR_ , 2000.
  * [18] L. Fei-Fei, R. Fergus, and P. Perona, “A Bayesian approach to unsupervised one-shot learning of object categories,” in _ICCV_ , 2003.
  * [19] Z. Wu, A. A. Efros, and S. X. Yu, “Improving generalization via scalable neighborhood component analysis,” in _ECCV_ , 2018.
  * [20] H. Qi, M. Brown, and D. G. Lowe, “Low-shot learning with imprinted weights,” in _CVPR_ , 2018.
  * [21] S. Gidaris and N. Komodakis, “Dynamic few-shot visual learning without forgetting,” in _CVPR_ , 2018.
  * [22] P. Mangla, N. Kumari, A. Sinha, M. Singh, B. Krishnamurthy, and V. N. Balasubramanian, “Charting the right manifold: Manifold mixup for few-shot learning,” in _WACV_ , 2020.
  * [23] J.-W. Seo, H.-G. Jung, and S.-W. Lee, “Self-augmentation: Generalizing deep networks to unseen classes for few-shot learning,” _arXiv preprint arXiv:2004.00251_ , 2020.
  * [24] C. Le, Z. Chen, X. Wei, B. Wang, and L. Zhang, “Continual local replacement for few-shot learning,” _arXiv preprint arXiv:2001.08366_ , 2020.
  * [25] Z. Chen, Y. Fu, Y. Zhang, Y.-G. Jiang, X. Xue, and L. Sigal, “Semantic feature augmentation in few-shot learning,” _arXiv preprint arXiv:1804.05298_ , 2018\.
  * [26] R. Zhang, T. Che, Z. Ghahramani, Y. Bengio, and Y. Song, “(metagan): an adversarial approach to few-shot learning,” in _NeurIPS_ , 2018.
  * [27] M.-Y. Liu, X. Huang, A. Mallya, T. Karras, T. Aila, J. Lehtinen, and J. Kautz, “Few-shot unsupervised image-to-image translation,” in _ICCV_ , 2019.
  * [28] A. Li, T. Luo, T. Xiang, W. Huang, and L. Wang, “Few-shot learning with global class representations,” in _ICCV_ , 2019.
  * [29] A. Afrasiyabi, J.-F. Lalonde, and C. Gagné, “Associative alignment for few-shot image classification,” _arXiv preprint arXiv:1912.05094_ , 2019\.
  * [30] M. Douze, A. Szlam, B. Hariharan, and H. Jégou, “Low-shot learning with large-scale diffusion,” in _CVPR_ , 2018.
  * [31] A. Iscen, G. Tolias, Y. Avrithis, O. Chum, and C. Schmid, “Graph convolutional networks for learning with few clean and many noisy labels,” _arXiv preprint arXiv:1910.00324_ , 2019.
  * [32] M. Rohrbach, S. Ebert, and B. Schiele, “Transfer learning in a transductive setting,” in _NIPS_ , 2013.
  * [33] A. Nichol, J. Achiam, and J. Schulman, “On first-order meta-learning algorithms,” _CoRR, abs/1803.02999_ , 2018.
  * [34] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf, “Learning with local and global consistency,” in _NIPS_ , 2003.
  * [35] J. Kim, T. Kim, S. Kim, and C. D. Yoo, “Edge-labeling graph neural network for few-shot learning,” in _CVPR_ , 2019.
  * [36] L. Qiao, Y. Shi, J. Li, Y. Wang, T. Huang, and Y. Tian, “Transductive episodic-wise adaptive metric for few-shot learning,” in _ICCV_ , 2019.
  * [37] Y. Hu, V. Gripon, and S. Pateux, “Exploiting unsupervised inputs for accurate few-shot classification,” _arXiv preprint arXiv:2001.09849_ , 2020.
  * [38] S. M. Kye, H. B. Lee, H. Kim, and S. J. Hwang, “Transductive few-shot learning with meta-learned confidence,” _arXiv preprint arXiv:2002.12017_ , 2020.
  * [39] Y. Wang, C. Xu, C. Liu, L. Zhang, and Y. Fu, “Instance credibility inference for few-shot learning,” _arXiv preprint arXiv:2003.11853_ , 2020.
  * [40] L. Yang, L. Li, Z. Zhang, E. Zhou, Y. Liu _et al._ , “DPGN: Distribution propagation graph network for few-shot learning,” _arXiv preprint arXiv:2003.14247_ , 2020.
  * [41] M. Ren, S. Ravi, E. Triantafillou, J. Snell, K. Swersky, J. B. Tenenbaum, H. Larochelle, and R. S. Zemel, “Meta-learning for semi-supervised few-shot classification,” in _ICLR_ , 2018.
  * [42] Z. Yu, L. Chen, Z. Cheng, and J. Luo, “TransMatch: A transfer-learning scheme for semi-supervised few-shot learning,” _arXiv preprint arXiv:1912.09033_ , 2019.
  * [43] A. Iscen, G. Tolias, Y. Avrithis, and O. Chum, “Label propagation for deep semi-supervised learning,” in _CVPR_ , 2019.
  * [44] N. Mishra, M. Rohaninejad, X. Chen, and P. Abbeel, “A simple neural attentive meta-learner,” _ICLR_ , 2018.
  * [45] M. Ren, R. Liao, E. Fetaya, and R. S. Zemel, “Incremental few-shot learning with attention attractor networks,” _arXiv preprint arXiv:1810.07218_ , 2018\.
  * [46] B. N. Oreshkin, A. Lacoste, and P. Rodriguez, “TADAM: Task dependent adaptive metric for improved few-shot learning,” _arXiv preprint arXiv:1805.10123_ , 2018.
  * [47] H. Li, D. Eigen, S. Dodge, M. Zeiler, and X. Wang, “Finding task-relevant features for few-shot learning by category traversal,” in _CVPR_ , 2019.
  * [48] D. Wertheimer and B. Hariharan, “Few-shot learning with localization in realistic settings,” in _CVPR_ , 2019.
  * [49] H. Zhang, J. Zhang, and P. Koniusz, “Few-shot learning via saliency-guided hallucination of samples,” in _CVPR_ , 2019.
  * [50] H. Xv, X. Sun, J. Dong, S. Zhang, and Q. Li, “Multi-level similarity learning for low-shot recognition,” _arXiv preprint arXiv:1912.06418_ , 2019.
  * [51] Y. Lifchitz, Y. Avrithis, and S. Picard, “Few-shot few-shot learning and the role of spatial attention,” _arXiv preprint arXiv:2002.07522_ , 2020.
  * [52] R. Hou, H. Chang, M. Bingpeng, S. Shan, and X. Chen, “Cross attention network for few-shot classification,” in _NeurIPS_ , 2019.
  * [53] F. Hao, F. He, J. Cheng, L. Wang, J. Cao, and D. Tao, “Collect and select: Semantic alignment metric learning for few-shot learning,” in _ICCV_ , 2019\.
  * [54] Z. Wu, Y. Li, L. Guo, and K. Jia, “PARN: Position-aware relation networks for few-shot learning,” in _ICCV_ , 2019.
  * [55] C. Zhang, Y. Cai, G. Lin, and C. Shen, “DeepEMD: Few-shot image classification with differentiable earth mover’s distance and structured classifiers,” _arXiv preprint arXiv:2003.06777_ , 2020.
  * [56] D. Zhou, J. Weston, A. Gretton, O. Bousquet, and B. Schölkopf, “Ranking on data manifolds,” in _NIPS_ , 2003.
  * [57] X. Zhu and Z. Ghahramani, “Learning from labeled and unlabeled data with label propagation,” Carnegie Mellon University, Tech. Rep., 2002.
  * [58] L. Grady, “Random walks for image segmentation,” _IEEE Trans. PAMI_ , vol. 28, no. 11, pp. 1768–1783, 2006.
  * [59] T. H. Kim, K. M. Lee, and S. U. Lee, “Generative image segmentation using random walks with restart,” in _ECCV_. Springer, 2008, pp. 264–275.
  * [60] G. Bertasius, L. Torresani, S. X. Yu, and J. Shi, “Convolutional random walk networks for semantic image segmentation,” in _CVPR_ , 2017.
  * [61] P. Vernaza and M. Chandraker, “Learning random-walk label propagation for weakly-supervised semantic segmentation,” in _CVPR_ , 2017.
  * [62] A. Iscen, G. Tolias, Y. Avrithis, T. Furon, and O. Chum, “Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations,” in _CVPR_ , 2017.
  * [63] R. Ranjan, C. D. Castillo, and R. Chellappa, “L2-constrained softmax loss for discriminative face verification,” _arXiv preprint arXiv:1703.09507_ , 2017\.
  * [64] F. Wang, X. Xiang, J. Cheng, and A. L. Yuille, “Normface: L2 hypersphere embedding for face verification,” in _ACM Multimedia_ , 2017.
  * [65] O. Boiman, E. Shechtman, and M. Irani, “In defense of nearest-neighbor based image classification,” in _CVPR_ , 2008.
  * [66] N. Dvornik, C. Schmid, and J. Mairal, “Diversity with cooperation: Ensemble methods for few-shot classification,” _ICCV_ , 2019.
  * [67] Y. Kalantidis, C. Mellina, and S. Osindero, “Cross-dimensional weighting for aggregated deep convolutional features,” in _ECCVW_ , 2016.
  * [68] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein _et al._ , “Imagenet large scale visual recognition challenge,” _arXiv_ , 2014.
  * [69] S. Ravi and H. Larochelle, “Optimization as a model for few-shot learning,” _ICLR_ , 2017.
  * [70] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie, “The Caltech-UCSD Birds-200-2011 Dataset,” California Institute of Technology, Tech. Rep. CNS-TR-2011-001, 2011.
  * [71] N. Hilliard, L. Phillips, S. Howland, A. Yankov, C. D. Corley, and N. O. Hodas, “Few-shot learning with metric-agnostic conditional embeddings,” _CoRR_ , vol. abs/1802.04376, 2018.
  * [72] H. Ye, H. Hu, D. Zhan, and F. Sha, “Learning embedding adaptation for few-shot learning,” _CoRR_ , vol. abs/1812.03664, 2018.
  * [73] B. Liu, Y. Cao, Y. Lin, Q. Li, Z. Zhang, M. Long, and H. Hu, “Negative margin matters: Understanding margin in few-shot classification,” _arXiv preprint arXiv:2003.12060_ , 2020.