# Background Matting

Hossein Javidnia
ADAPT Centre
School of Computer Science and Statistics
Trinity College Dublin, Ireland
<EMAIL_ADDRESS>François Pitié
Sigmedia Group
Department of Electronic & Electrical Engineering
Trinity College Dublin, Ireland
<EMAIL_ADDRESS>
###### Abstract

The current state of the art alpha matting methods mainly rely on the trimap
as the secondary and only guidance to estimate alpha. This paper investigates
the effects of utilising the background information as well as trimap in the
process of alpha calculation. To achieve this goal, a state of the art method,
AlphaGan is adopted and modified to process the background information as an
extra input channel. Extensive experiments are performed to analyse the effect
of the background information in image and video matting such as training with
mildly and heavily distorted backgrounds. Based on the quantitative
evaluations performed on Adobe Composition-1k dataset, the proposed pipeline
significantly outperforms the state of the art methods using AlphaMatting
benchmark metrics.

_K_ eywords GAN $\cdot$ Alpha Matting $\cdot$ Foreground Extraction

##  1 Introduction

Alpha estimation is a regression problem that calculates the opacity value of
each blended pixel in the foreground object. It serves as a prerequisite for a
broad range of applications such as movie post production, digital image
editing and compositing live action.

Formally, the composition image $I_{i}$ is represented as a linear combination
of the background $B_{i}$ and foreground $F_{i}$ colors [chuang2001bayesian]:

$I_{i}=\alpha_{i}F_{i}+(1-\alpha_{i})B_{i}$ (1)

where $\alpha_{i}\in[0,1]$ denotes the opacity or alpha matte of the
foreground at pixel $i$. Often, a user input is provided as a guidance in the
form of a trimap, which assigns a label for every pixel as foreground
$\alpha=1$, background $\alpha=0$ and unknown opacity. The goal of the matting
algorithms is to estimate the unknown opacities by utilising the pixel color
information of the known regions. Tackling the inverse problem of Eq. 1 is
considerably difficult as there are 7 unknowns and 3 equations to be solved
for an RGB image. The main motivation in this paper is to increase the matting
accuracy by reducing the number of unknowns in Eq. 1. To do so, we presume
that the background information $B$, is known either by capturing a clear
background or through reconstruction methods that can estimate the occluded
background regions.

In traditional methods, the matte is estimated by inferring the alpha
information in the unknown areas from those in known areas [wang2008image].
For example, the matte values could be propagated from known to unknown areas
based on the spatial and appearance affinity relation between them
[Aksoy2017matting, Chen2013matting, Chen2013mattlocal, He2010laplac,
Lee2011nonlocal, Levin2008closedf, Levin2008spectral, Jian2004poisson]. An
alternative solution is to compute the unknown mattes by sub-sampling the
color and texture distribution of the foreground and background planes
followed by an optimization such as likelihood of alpha values
[chuang2001bayesian, He2013iter, He2011global, Wang2005iter, Wang2007robust].
Despite the promising performance of these methods on public benchmarks, there
is still an unresolved issue of natural image matting and consistency in
videos between consecutive frames. One important reason causing this problem
is the fact that the performance of these methods heavily rely on the accuracy
of the given trimap. Generating the trimap for a sequence of images from a
video is indeed a challenging task as it requires tracking the object of
interest and defining an appropriate and relevant unknown areas to be solved.

To address these challenges, this paper presents a Background-Aware Generative
Adversarial Network (AlphaGan-BG) which utilises the information present in
the background plane to accurately estimate the alpha matte compensating for
the issues caused by inaccurate trimap. Unlike the state of the art which only
use RGB image and trimap as the input, AlphaGan-BG analyses the color and
texture provided as background information to achieve a better accuracy. To
our best knowledge, this paper contributes the first deep learning approach
which takes advantage of the background information to estimate alpha mattes.
Both our qualitative and quantitative experiments demonstrate that AlphaGan-BG
significantly outperforms the state of the art matting methods.

##  2 Previous Works

Alpha matting is a well established and studied field of research in computer
vision with a rich literature. A significant amount of work has been done over
the past decade to address the issues in natural image matting. More recently,
deep learning approaches have shown an impressive performance on various
computer vision tasks including image matting too.

This section briefly reviews the state of the art alpha matting methods within
two categories: conventional methods and deep learning based methods.

###  2.1 Conventional Matting Methods

The conventional alpha matting approaches could be categorised into sampling
based and affinity based methods. Sampling based methods [chuang2001bayesian,
Gastal2010SharedSF, He2011global, Xiaoxue2016cluster] initially collect a set
of known foreground and background color samples to identify the best
foreground-background color pair for a pixel.

The general rule is to use Eq. 1 to calculate the alpha value once the
corresponding background and foreground colors are determined. The issue with
the sampling based method is that they don’t make use of the texture
information present in the image and they don’t enforce spatial smoothness
thus introducing an additional spatial smoothness step. More importantly,
there is always the ambiguity on how the samples are chosen and where are they
chosen from; causing matte discontinuities. For instance, Shared Matting
[Gastal2010SharedSF] select the samples from the trimap boundaries between the
known and unknown pixels. Global Matting [He2011global] makes use of all the
pixels within the trimap boundary therefore increasing the performance time.
Sparse sampling [Karacan2015divergance] applies the sampling in a super-pixel
level by assessing their similarity using KL-Divergence based distance
measure.

Affinity-based methods work by analysing the affinities of neighboring pixels
to propagate alpha information from known to unknown regions. Levin et al.
[Levin2008closedf] proposed a closed-form matting solution where the local
color information is used to compute the affinity between two pixels. In
[Levin2008closedf] the alpha matte is calculated by solving a sparse linear
system. The advantage of the closed-form solution is the prediction of the
properties of the solution by analysing the eigenvectors of a sparse matrix.
Chen et al. [Xiaowu2012manifold] proposed a locally linear embedding system
which represents every unknown pixel as a linear combination of its neighbors.
KNN matting [Chen2013matting] utilised nonlocal principal to find the
affinities. The basis of this principal is that a pixel is a weighted sum of
the pixels with similar appearance to the given weight [Chen2013matting]. This
method enforces the the pixels and their corresponding nonlocal neighbors to
have close alpha value. Aksoy et al. [Aksoy2017matting] constructed their
method based on color-mixture flow using pixel-to-pixel connections between
the image and it’s corresponding trimap. The flow is based on local linear
embedding with gradual improvement in matting quality as more building blocks
are added to the information flow. It was shown in [Aksoy2017matting] that
combining local and non-local affinities can result in a higher quality alpha
matte. Several other state of the art approaches such as Random Walks
[grady2005random], FuzzyMatte [Zheng2008fuzzy], Spectral Matting
[Levin2008spectral] and Geodesic Matting [Bai2007geo] can also be categorised
as affinity based methods.

###  2.2 Deep Learning Based Matting Methods

Emerging field of deep learning along with the new generation of hardware,
enabled many researches to tackle the issues of natural image matting with
promising performances. Cho et al. [Donghyeon2016DCNN] proposed an end-to-end
Deep Convolutional Neural Networks (CNN) which utilises the results of the
closed form matting and KNN matting for alpha estimation. Xu et al.
[Xu2017deepmatting] proposed a two part structure to predict alpha. The first
part is an encoder-decoder module trained to predict the alpha from the input
image and trimap; the second part is a small CNN trained to perform a post-
processing step to increase the quality of the estimated alpha. Lu et al.
[Lu2019ICCV] proposed IndexNet Matting by introducing indexed pooling and
upsampling operators. They modeled the indices as a function of the feature
map to perform the upsampling. There are many other methods proposed to use
deep learning to tackle the issues of natural image matting such as VDRN
Matting [Tang2019VDRN], SampleNet Matting [Tang2019CVPR], AdaMatting
[Cai2019ICCV], Late Fusion Matting [Zhang2019CVPRlatefusion], Inductive Guided
Filter Matting [Li2019inductive], however, the analysis of these methods goes
beyond the scope of our work.

##  3 AlphaGan-BG Network

The framework in this research is built on the first proposed GAN to estimate
alpha mattes. AlphaGAN [Lutz2018alphagan] was introduced in 2018 motivated by
the encoder-decoder structure proposed in [Xu2017deepmatting]. The original
architecture of AlphaGAN consists of a generator $G$ and discriminator $D$.

In the original form of AlphaGAN, $G$ accepts the input in a form of a 4
channel volume made of a composited image (3 channels) and the corresponding
trimap (1 channel). $D$ is responsible for distinguishing the real from fake
input volume. The first 3 channels of the input volume to $D$ belongs to the
RGB values of the new composited images based on predicted alpha and the last
channel is the original trimap to help $D$ focus on salient regions.

AlphaGAN followed the same path as the rest of the state of the art methods
with the assumption that the only data available is an RGB image and the
corresponding trimap. However, in this paper, background information is also
considered as the known variable and the input to the network.

###  3.1 Generator $G$

In this research, $G$ is an encoder-decoder network that accepts the input in
a form of a 7 channel volume, where the first 3 channels contain the RGB
image, the second 3 channels contain the RGB background information and the
last channel contains the trimap. The encoder is based on ResNet50
[He2016resnet] architecture pretrained on ImageNet [Russakovsky2015imagenet]
where the convolutions in the 3rd and 4th block of the ResNet are replaced by
dilated convolutions with rate 2 and 4, respectively. To resample features at
several scales, Atrous Spatial Pyramid Pooling (ASPP) module [Chen2017ASPP,
Chen2018ASPP] is added after ResNet block 4.

Similary to AlphaGAN, the decoder is simply a set of convolutional layers and
skip connections from the encoder. The output of the encoder is bilinearly
upsampled with the factor of 2 to maintain the same spatial resolution for the
feature maps as the output of ResNet block 1. To reduce the dimensions, the
output of the ResNet block 1 is fed into $1\times 1$ convolutional layer and
concatenated with the upsampled feature maps from encoder. This is followed by
$3\times 3$ convolutions and upsampling using the saved pooling indices in the
first layer of the encoder. The results are once again concatenated with the
feature maps from the encoder with the same resolution. Before feeding the
output to the final set of convolution layers, transposed convolutions are
applied to upsample it followed by a concatenation with the RGB input image.
ReLU [Vinod2010relu] activation functions and Batch Normalization
[Sergey2015batchnorm] layers are used for all the layers except the last one
which utilises a sigmoid activation to scale the output between 0 and 1. Fig.
1 illustrates the encoder-decoder structure of $G$.

Figure 1: AlphaGan-BG: Structure of Generator ($G$).

###  3.2 Discriminator $D$

This architecture employs PatchGAN [Isola2017patchgan] as the discriminator.
$D$ attempts to distinguish fake from real input which is a 7 channel volume.
The real input is constructed by original composition using truth alpha,
background and trimap. The fake input contains the new composition using the
alpha generated by $G$, background and the trimap. By providing the background
information, $D$ will enforce $G$ to output sharper and more accurate result
as the issue of differentiating foreground and background is resolved by
default.

###  3.3 Loss Functions

The full objective of the network is a combination of three loss functions:
alpha-prediction loss $\mathcal{L}_{alpha}$, compositional loss
$\mathcal{L}_{comp}$ and adversarial loss $\mathcal{L}_{GAN}$
[Goodfellow2014loss]:

$\mathcal{L}_{total}=\mathcal{L}_{alpha}+\mathcal{L}_{comp}+\mathcal{L}_{GAN}$
(2)

$\mathcal{L}_{alpha}$ is the absolute difference of the ground truth and
predicted alpha values for all the pixels. $\mathcal{L}_{comp}$ is the
absolute difference of the composited image using ground truth alpha and the
composited image using predicted alpha. The composition in both cases are
based on the ground truth foreground and background images
[Xu2017deepmatting]. $\mathcal{L}_{GAN}$ is defined based on the fundamentals
of adversarial networks, where in this research, $G$ aims at generating alpha
mattes close to the ground truth while $D$ aims at distinguishing real from
fake input; resulting in $G$ minimizing the $\mathcal{L}_{GAN}$.

##  4 Experiments and Discussion

###  4.1 Dataset

The network in this paper is trained on Adobe Matting dataset
[Xu2017deepmatting] consists of 431 foreground images for training and 50
images for testing with corresponding ground truth. To augment the data,
Pascal VOC 2008 [everingham2010pascal] and MSCOCO images [lin2014microsoft]
are used as the background for image composition resulting in a training set
containing 43100 images.

###  4.2 Data Preparation

As described in Section 3, this network takes advantage of the background
information to predict alpha matte. This requires the background information
to be available during the test phase as well as training. However, acquiring
the background image during the test phase is a challenging task. To achieve
this, several inpainting and background reconstruction methods
[Kim2019deepinpainting, Xu2019flowinpainting, Huang2016tempinpainting,
LAUGRAUD201712, Laugraud2015medianbasedinpainting, Herling2014pixmix] are
studied to analyse their accuracy and performance on static images and videos.
The findings indicate that currently there is no background reconstruction
method that can generate a clear background without artifacts. The ultimate
goal is to obtain a reconstructed image which is equivalent of the original
input used for the composition. The common artifacts present in the output of
the reconstruction methods are the blur (degraded quality) and shift
(translation), meaning that the region containing the object of interest is
slightly translated in the reconstructed image.

To simulate these artifacts, two sets of backgrounds are augmented. In the
first set, a random selection of images are manipulated by applying a
hexagonal shape Gaussian blur with a random filter size. The location of the
hexagonal blur is randomly chosen along the dimensions of the input image. The
diameter of the shape is randomly selected between 120 and 345 pixels with
rotation angle chosen by generating a linearly spaced vector. The blurred
region is also translated using a 2D linear translation. In the second set,
all the images are initially blurred followed by applying the hexagonal shape
Gaussian blur at a random location. Comparatively, the first scenario
represents a more realistic case as it contains both clean and partially
distorted backgrounds. However, the second set represents severely distorted
cases where all the images are blurred with an additional distorted patch
introducing a more challenging set for training.

###  4.3 Training

In this paper, two models are trained for evaluation purposes. The first model
utilises the first set of background images as described in Section 4.2 and
the second model uses the second set of backgrounds with severe distortion. In
order to make the remaining sections easier to follow, we refer to the first
model as AlphaGan-BG_M (Mildly distorted) and second model as AlphaGan-BG_H
(Heavily distorted).

AlphaGan-BG_M and AlphaGan-BG_H are trained for 376 and 650 epochs
respectively with the initial learning rate set to 0.0002. Adam optimizer
[kingma2014adam] with $\beta$ = 0.999 is also employed for optimization
purposes.

###  4.4 Results and Evaluation

###  4.5 Still Image Matting

The evaluation for still images is performed on a set of 50 images from Adobe
Matting [Xu2017deepmatting] test set. Note that, none of the test images are
considered as part of the training. Four metrics based on AlphaMatting
benchmark [Rhemann2009matting, alphamattingweb] are used for evaluation
purposes including Sum of Absolute Difference (SAD), Mean Square Error (MSE),
Connectivity (CONN) and Gradient Errors (GRAD). The test images from
AlphaMatting benchmark are not considered as part of this evaluation as there
is no available background information for the test set. The background images
used for evaluation are also manipulated using the pipeline describes in
Section 4.2 to simulate the reconstruction artifacts. The performance of the
trained models are compared against 8 state of the art methods ranked in
AlphaMatting benchmark with publicly available code including Closed-Form
Matting [Levin2008closedf], DCNN Matting [Donghyeon2016DCNN], Deep Matting
[Xu2017deepmatting], IndexNet Matting [Lu2019ICCV], Information-flow Matting
[Aksoy2017matting], KNN Matting [Chen2013matting], Late Fusion
[Zhang2019CVPRlatefusion] and AlphaGAN [Lutz2018alphagan].

Methods | SAD | MSE | GRAD | CONN
---|---|---|---|---
Closed-Form Matting [Levin2008closedf] | 78.768 | 0.065 | 57.047 | 56.856
DCNN Matting [Donghyeon2016DCNN] | 85.842 | 0.070 | 57.622 | 65.196
Deep Matting [Xu2017deepmatting] | 33.075 | 0.017 | 23.316 | 34.204
IndexNet Matting [Lu2019ICCV] | 28.984 | 0.013 | 19.127 | 28.872
Information-flow Matting [Aksoy2017matting] | 84.766 | 0.067 | 52.789 | 63.827
KNN Matting [Chen2013matting] | 95.122 | 0.082 | 66.188 | 74.940
Late Fusion [Zhang2019CVPRlatefusion] | 88.109 | 0.097 | 59.382 | 91.743
AlphaGAN [Lutz2018alphagan] | 35.057 | 0.019 | 33.598 | 35.963
AlphaGan-BG_M | 11.312 | 0.002 | 4.850 | 8.696
AlphaGan-BG_H | 14.692 | 0.003 | 8.410 | 12.328

Table 1: The quantitative comparison of the AlphaGan-BG models against state
of the art. The best average value/metric is emboldened.

Figure 2: Comparison with State of the Art Methods - Example 1.

Table 1 presents the numerical evaluation of the AlphaGan-BG models against
the state of the art methods and clearly notes that AlphaGan-BG outperforms
the other methods based on the commonly used AlphaMatting benchmark metrics.
This experiment also validates the idea of using background information for
alpha estimation. As discussed in Section 4.2, based on the current state of
the art in background reconstruction, it is very challenging to obtain a clear
reconstructed background; However, this experiment demonstrates that even
having a partial information about the background plane (with distortion) can
significantly increase the accuracy of the alpha prediction.

Fig. 2 and Fig. 3 illustrate the qualitative comparison of the proposed models
against the state of the art methods. A part of the predicted alpha mattes by
the state of the art is marked in Fig. 2 to closely expose the difference in
the performance of the methods.

Figure 3: Comparison with State of the Art Methods - Example 2.

The performance of the AlphaGan-BG_M and AlphaGan-BG_H in Fig. 2 is a clear
example and proof of an earlier statement that including the partial
background information of the image during the matting pipeline, can
significantly increase its accuracy and preserve fine details.

Fig. 3 is another example of the visual comparison against the state of the
art where the superior performance of the AlphaGan-BG_M and AlphaGan-BG_H is
clearly visible through the marked areas. For more and detailed visual results
refer to Appendix 1.

###  4.6 Video Matting

To evaluate the performance of the AlphaGan-BG_M and AlphaGan-BG_H on video
sequences, we used four state of the art background reconstruction and
inpainting methods including Deep Video Inpainting (DVI)
[Kim2019deepinpainting], Deep Flow Inpainting (DFGI) [Xu2019flowinpainting],
FVC [Afifi2014fastvideocomp] and Gated Video Inpainting (GVI) [chang2019free]
to separate the foreground and background layers. We also considered
backgrounds with simulated artifacts as part of this evaluation. The
background layers are further used as the input to the proposed matting
framework. Three video sequences including Alex, Castle and Dmitriy from
VideoMatting benchmark [Erofeev2015videomatting] are used for evaluation
purposes. Tables 2-5 present the numerical evaluation of the AlphaGan-BG
models on video sequences. The aforementioned reconstruction methods are
applied to each sequence to extract the background layer as one of the input
channels to AlphaGan-BG models. One important and obvious take from this
experiment is the fact that a successful background aware matting method
significantly relies on the quality of the reconstructed background. Although,
the point of this experiment is not to compare the performance of the
reconstruction methods, a few state of the art techniques such as FCV
[Afifi2014fastvideocomp] generate background layers with less artifacts and
similar to the simulated ones resulting in more accurate alpha estimation
using AlphaGan-BG_M. On the other hand, AlphaGan-BG_H performs better in
scenarios where the reconstructed background layers are heavily distorted such
as DVI [Kim2019deepinpainting] and DFGI [Xu2019flowinpainting]. A detailed set
of visual results for this section is provided in Appendix 2.

W\Artifact DVI [Kim2019deepinpainting] DFGI [Xu2019flowinpainting] GVI
[chang2019free] FVC [Afifi2014fastvideocomp] A C D A C D A C D A C D A C D
AlphaGan-BG_M 1.004 10.145 1.66 9.95 95.712 11.856 1.787 32.808 2.28 16.814
89.4 15.046 1.165 11.385 1.781 AlphaGan-BG_H 1.28 28.062 1.758 1.658 53.513
2.115 1.292 37.207 1.775 2.409 56.7 2.91 1.3 28.352 1.77

Table 2: SAD Metric - Performance of the AlphaGan-BG models using different
background reconstruction methods. A: Alex, C: Castle and D: Dimitriy. The
best average value per model for each animation across all reconstruction
method is emboldened.

W\Artifact DVI [Kim2019deepinpainting] DFGI [Xu2019flowinpainting] GVI
[chang2019free] FVC [Afifi2014fastvideocomp] A C D A C D A C D A C D A C D
AlphaGan-BG_M 0.0001 0.001 0.0006 0.014 0.059 0.014 0.0008 0.014 0.001 0.027
0.053 0.019 0.0002 0.001 0.0007 AlphaGan-BG_H 0.0002 0.010 0.0008 0.0006 0.028
0.001 0.0003 0.017 0.0008 0.001 0.031 0.002 0.0003 0.011 0.0008

Table 3: MSE Metric - Performance of the AlphaGan-BG models using different
background reconstruction methods. A: Alex, C: Castle and D: Dimitriy. The
best average value per model for each animation across all reconstruction
method is emboldened.

W\Artifact DVI [Kim2019deepinpainting] DFGI [Xu2019flowinpainting] GVI
[chang2019free] FVC [Afifi2014fastvideocomp] A C D A C D A C D A C D A C D
AlphaGan-BG_M 0.365 5.779 2.51 12.52 123.945 21.397 1.376 33.184 3.931 17.57
110.25 25.134 0.582 7.826 2.835 AlphaGan-BG_H 0.744 67.829 3.059 1.075 95.806
4.061 0.766 75.408 3.099 2.111 97.737 6.213 0.762 68.364 3.098

Table 4: GRAD Metric - Performance of the AlphaGan-BG models using different
background reconstruction methods. A: Alex, C: Castle and D: Dimitriy. The
best average value per model for each animation across all reconstruction
method is emboldened.

W\Artifact DVI [Kim2019deepinpainting] DFGI [Xu2019flowinpainting] GVI
[chang2019free] FVC [Afifi2014fastvideocomp] A C D A C D A C D A C D A C D
AlphaGan-BG_M 0.457 7.77 1.562 9.78 100.104 11.932 1.21 33.173 2.131 17.066
93.838 15.254 0.624 9.208 1.68 AlphaGan-BG_H 0.801 27.864 1.707 1.252 55.5
2.085 0.818 37.95 1.725 2.162 58.965 2.948 0.825 28.191 1.719

Table 5: CONN Metric - Performance of the AlphaGan-BG models using different
background reconstruction methods. A: Alex, C: Castle and D: Dimitriy. The
best average value per model for each animation across all reconstruction
method is emboldened.

##  5 Conclusion

In this paper we proposed an approach inspired by a state of the art GAN model
to validate the idea of using background information as part of the alpha
matting process. The proposed approach utilises an encoder-decoder structure
as generator and PacthGAN as discriminator. The input to the network consists
of 7 channels, including RGB image, RGB background information and the trimap.
The preliminary results of the experiments and evaluations against the
benchmarked methods indicate the validity of the core idea in this research.
Using the full or partial background information, AlphaGan-BG demonstrated a
superior performance against the studied methods. In the future work, we would
like to train and analyse the performance of AlphaGan-BG on synthetic data.
The background reconstruction process is another exciting aspect of this
research that requires more investigation. The current performance of the
models is achieved by simulating the reconstruction artifacts. However, we
believe that AlphaGan-BG can obtain a higher accuracy if trained on a specific
background reconstruction method with consistent noise and artifact pattern.

## Appendix 1: Visual Results on Adobe Matting dataset

## Appendix 2: Visual Results on Video Matting dataset - A Frame from Alex
Video Sequence

## Appendix 2: Visual Results on Video Matting dataset - A Frame from Castle
Video Sequence

## Appendix 2: Visual Results on Video Matting dataset - A Frame from Dmitriy
Video Sequence


# In-storage Processing of I/O Intensive Applications on Computational Storage
Drives

Ali HeydariGorji University of California Irvine
Mahdi Torabzadehkashi Vladimir Alves  NGD Systems Inc.
NGD Systems Inc.
Siavash Rezaei NGD Systems Inc.
Pai H. Chou  University of California Irvine
Hossein Bobarshad  NGD Systems Inc.

###### Abstract

Computational storage drives (CSD) are solid-state drives (SSD) empowered by
general-purpose processors that can perform in-storage processing. They have
the potential to improve both performance and energy significantly for big-
data analytics by bringing compute to data, thereby eliminating costly data
transfer while offering better privacy. In this work, we introduce Solana, the
first-ever high-capacity(12-TB) CSD in E1.S form factor, and present an actual
prototype for evaluation. To demonstrate the benefits of in-storage processing
on CSD, we deploy several natural language processing (NLP) applications on
datacenter-grade storage servers comprised of clusters of the Solana.
Experimental results show up to 3.1x speedup in processing while reducing the
energy consumption and data transfer by 67% and 68%, respectively, compared to
regular enterprise SSDs.

###### Index Terms:

Computational Storage Drives, In-Storage Processing, Near-data processing,
Natural Language Processing, distributed NLP

##  I Introduction

In-storage processing (ISP) is the computing paradigm of moving computation to
data storage as opposed to moving data to compute engines. ISP may be the
ultimate form of the near-data processing in the age of data centers, which
fuel the demand for virtually unlimited storage. It has been estimated that
2.5 exabytes of data is being created every day [1], from text to images,
music, and videos. The deep learning revolution has given rise to running
computationally intensive algorithms on these huge amounts of data. Different
technologies have been developed to support this trend towards high storage
and computation demands, and they shift the bottleneck as a result.

On the storage side, hard disk drives (HDDs) have been increasing in capacity
exponentially with high reliability and very competitive cost. However, HDDs
have plateaued in performance, and their power consumption is ultimately
lower-bounded by the mechanical motion. Solid state drives (SSD), which are
based on NAND-flash memory and thus have no moving parts, offer better
performance at lower power consumption,

Figure 1: Handling queries on (a) a server with generic storage systems vs.
(b) a server with CSDs.

On the computing side, general-purpose graphic processing units (GPGPU) have
brought massive parallel processing to conventional PCs for running
computationally intensive applications such as deep learning and crypto
mining. However, GPUs are power-hungry and are not suitable for storage
systems. Data centers are now most concerned about power for not only the
electric bill but also cooling, which can become another source of
unreliability. As a result, GPGPUs are not so suitable for in-storage
processing, but they often assume data to reside on the local computer. If the
data resides on data storage, the communication network to bring it to memory
will incur 5000x more energy consumption and 2500x more latency compared to
loading it from volatile memory [2].

One class of application that fits the characteristics above is natural
language processing (NLP). It is a branch of artificial intelligence (AI) that
enables machines to communicate with humans directly by speech or written
language. Many NLP applications use large components such as embeddings that
can exceed GBs in size, or rather large input data such as audio or video
input that is much much larger in size than text input [3]. Subsequently, the
cost of data transfer between storage and host can quickly dominate in long
latency and energy consumption.

In-storage processing can minimize data transfer between the host and storage
by moving computation into the storage units and sending only the output back
to the host. To support ISP, the storage system requires an emerging class of
devices called computational storage drives (CSD), which augment the storage
with processing capabilities. CSDs are being used to build new servers such as
that shown in Fig. 1, where the storage drive can serve parts of the requests.

This paper introduces a novel high-capacity CSD and demonstrates its
effectiveness for ISP using some NLP applications. Our CSD prototype, code-
named Solana, is a 12-TB, NAND flash SSD, equipped with a dedicated embedded
processing engine along with the main SSD controller, all in _E1.S form
factor_. Solana’s dedicated processor runs a version of embedded Linux
operating system that allows users to run any Linux-based application such as
Docker or distributed processes. With this CSD as the compute/storage building
blocks for ISP, we show that it can effectively eliminate transfer of data out
of storage unit when running our developed scheduler to distribute NLP
applications onto the cluster of CSDs. We evaluate our proposed
hardware/software solution for common NLP applications and also compare our
design with previous state-of-the-art works on storage solutions.

##  II Background and related work

Near-data processing (or in this case In-Storage Processing) is a new way to
break the artificial lower bound on data transmission between storage and
computation by re-partitioning so that data transmission can be eliminated
partially or entirely. Researchers have proposed ways of augmenting the
storage with more computing power for near-data processing.[4, 5, 6, 7, 8, 9,
10, 11, 12, 13] Traditionally, there are two approaches to implement CSD.

The first approach uses the same processing engine that runs the SSD
controller tasks i.e. low-capability ARM M-series or R-series that yields a
low performance for in-storage processing. Such design can address light
computational tasks [4], but cannot be used for heavier computation tasks.

The second approach uses an external engine coupled with the main SSD
controller, to run the task computations. This method is easier to design as
the storage module is separated from the ISP module. But it comes at the price
of another bottleneck, that is the communication bandwidth between the storage
module and the computation module. The external ISP engine can be a mixture of
low-power processors such as ARM A-series or reconfigurable logic such as
FPGA. FPGA-based ISP provides flexibility for implementing custom-designed
accelerators. But deploying an FPGA-based unit requires RTL-level design which
significantly complicates the deployment of new tasks[12, 11].

Researchers in [13] investigate a computational storage platform for big data
analytics. The computation part is based on the Xilinx’s Zynq, an SoC
containing both ARM cores and FPGA arrays. It can directly communicate with
the storage part by transferring data in P2P mode. With their software stack,
it can run user binaries without modification, making it easy to port
applications. Experimental results show that this system can achieve 6x
improvement in query times and an average of 60% lower CPU usage. However, no
power and energy results were reported, even though the FPGAs and the off-chip
accelerator are likely to be power hungry. Also, the communication between the
SSD engine and the computation engine can emerge as a new bottleneck and the
entire design falls behind of an integrated solution such as Solana.

A close work to ours, RecSSD [14] proposes a near-data processing solution
that improves the performance of the underlying SSD storage for embedding
table operations for recommendation applications. It utilizes the internal SSD
bandwidth and reduces data communication overhead between the host processor
and the SSDs by offloading the entire embedding table operation, including
gather and aggregation computations, to the SSDs. The hardware is a commercial
OpenSSD evaluation platform[15]. This research’s main contribution is a
software solution that is implemented on the flash translation layer (FTL).
Experimental results show that their proposed system enhances the overall
latency by up to 2x compared to off-the-shelf SSDs. Even though the results of
RecSSD looks promising, the design is application specific and cannot be
adapted to different applications. It also requires changes deep down to the
flash translation layer (FTL) which is not an viable option for end users.

We take in-storage processing a step further by designing an ASIC that
includes both the SSD controller and a dedicated ARM processor subsystem for
running general applications on a single chip. The 64 bit quad-core ARM
processor supports running a Linux operating system which in turn enables
running executables without source-code modification or recompiling. We have
also implemented a TCP/IP-based tunneling system that allows the in-storage
processing engine to connect to a network, including the Internet and other
processing nodes. The next section details the hardware and software that
enable our system to function both as a regular storage system and as a
standalone processing node.

##  III Computational Storage Platform

This section provides a high level description of the hardware prototype and
software stack of the proposed Solana CSD. We explain our system with a
highlight of key features for supporting efficient in-storage processing.

###  III-A CSD Hardware

Solana is a NAND-based 12-TB storage system that uses an NVMe protocol over a
4-lane PCIe to connect to the host. The proposed architecture consists of two
subsystems: flash controller unit (FCU) and in-storage processing(ISP) engine,
both sharing a 6-GB Direct Random Access Memory (DRAM) through a high-speed
intra-chip data bus. This section describes the architectures of FCU and ISP
as well as the communication link between them.

####  III-A1 FCU Subsystem

The proposed CSD solution should be able to act as a standard SSD with an NVMe
interface, so the FCU subsystem has many parts similar to those in
conventional SSDs. This subsystem includes two main modules: front-end (FE)
and back-end(BE).

The FE is responsible for receiving the IO commands from the host, checking
their integrity and correctness, and interpreting them. Then, it transfers the
commands to BE for execution. One of the main modules of the FE subsystem is
the NVMe/PCIe interface. This interface is an ASIC module that is designed for
high-performance communication with the host using NVMe over PCIe protocol.

Figure 2: Solana: CSD prototype in E1.S form factor.

The BE is considerably more complex than FE. It needs to communicate with the
flash memory chips to complete the IO commands, and it is equipped with an
error-correction unit (ECC) to remove data errors that occur in the flash
memory cells. The communication between BE and the flash memory chips is
handled by a 16-channel data bus. The bus is capable of doing multiple IO
operations concurrently. BE is also responsible for implementing flash
management routines, such as wear-leveling, address translation, and garbage
collection.

Both ISP and FE are directly connected to BE. When an IO command comes from
the host, FE submits it to BE. Similarly, the ISP engine can submit IO
commands to BE. In other words, the ISP subsystem bypasses the FE module and
the NVMe over PCIe link altogether. This provides ISP with an efficient, high-
performance link to the data in the flash storage.

####  III-A2 In-Storage Processing Subsystem

The in-storage processing (ISP) subsystem consists of a quad-core ARM Cortex
A-53 processor together with the NEON single instruction multiple data (SIMD)
engines. ISP is implemented inside the same chip as the controller, and an
efficient high-speed intra-chip data link connects it to the BE. Although ISP
is equipped with only a quad-core processing engine, this intra-chip data link
makes the ISP engine a unique processing unit. The processor also provides an
environment for running different types of applications. More details of the
hardware architecture are available on our previous works[16, 17].

###  III-B System Software on the CSD

We ported a full-fledged version of embedded Linux OS to our CSD to run as our
ISP engine. Running a conventional Linux-based compute system makes it
compatible with a wide spectrum of applications, programming languages, and
command lines without modification. Linux is also extensible with our own
custom features, including device drivers and file systems.

We developed a Customized Block Device Driver (CBDD) to enable accessing
storage units optimized to the specific on-chip communication links/protocols,
which are different from common protocols between processing units and storage
devices (e.g., PCIe and SATA). CBDD uses a command-based mechanism to
communicate with the SSD controller to initiate data transfers. Using the
scatter-gather mechanism, the SSD controller directly handles data transfers
through the DDR addresses exposed by Linux.

Figure 3: Hardware architecture of Solana CSD.

Figure 4: Solana’s software stack provides three different communication
paths: (a) The conventional data path through the NVMe driver to the host, (b)
The path through on-chip connection to the ISP subsystem with file-system
abstraction, and (c) The TCP/IP tunneling over the PCIe/NVMe.

One unique feature with our CSD is that the CBDD supports file-system access
by the ISP applications and the host. By allowing the embedded Linux to mount
partitions on the storage and present a file API, this makes it not only
easier to port applications but also more efficient to access the data[18,
19]. The host CPU and ISP units can also communicate via the same partition,
which is mounted by both the host and the ISP. While conventional file systems
do not allow multiple mount points, there are efficient shared file systems
designed to support multiple mount points. We use the Oracle Cluster File
System (OCFS2) to enable sharing file systems and mounting the same partitions
from both the host and the ISP. OCFS2 requires a TCP/IP communication link to
orchestrate and update file systems of the two mounting points. Our TCP/IP
tunnel provides such possibility.

###  III-C Multi-Path Software Stack

Fig. 4 depicts the different layers of the Solana’s software stack. It
supports three communication paths over the different interfaces on our CSD:
flash-to-host, flash-to-ISP, and TCP/IP tunneling.

####  III-C1 Flash-to-Host Interface

The conventional data path (shown as path “a” in Fig. 4) is through NVMe
protocol over PCIe to allow the host to access the data stored in the NAND
flash memory. To do so, our NVMe controller is capable of handling NVMe
commands and responds to them appropriately and manages data movement through
communicating with our flash media controller.

####  III-C2 Flash-to-ISP Interface

Path “b” in Fig. 4 shows the data path through on-chip connection to provide
file-system-based data access to the ISP engine. CBDD implements the file-
system-based data access interface through communication with our flash media
controller. In fact, the flash media controller is responsible for handling
requests from both the ISP engine and the host.

####  III-C3 TCP/IP tunnelling over the PCIe/NVMe

Path “c” in Fig. 4 shows TCP/IP communication mechanism tunneled through
PCIe/NVMe to enable communication between host (and the world-wide network)
and the ISP system. Such tunneling feature eliminates the need for unwieldy
network setup, including cables and switches, to connect the many tightly
assembled storage units, which would be impractical to maintain and scale. The
proposed TCP/IP tunnel uses two shared buffers on the on-board DDR to provide
the data communication. Two user-level applications, one on the host and one
on the ISP running in the background, are responsible for managing NVMe-based
data movement and encapsulating/decapsulating the TCP/IP data through NVMe
packets.

##  IV Methods and Experimental results

We evaluate the proposed ISP system by running three NLP application on a
commercial storage server. We choose the AIC FB128-LX equipped with an 8-core,
16-thread Intel® Xeon® Silver 4108 CPU running at 2.1 GHz and 64 GB of DRAM.
It can support up to 36 E1.S drives in the front bay, 12 TB each, for a total
capacity of 432 TB on a 1U class server. This section first describes our
method of distributing processing loads onto the CSDs using our scheduler,
followed by the results of running each benchmark.

###  IV-A Methods

To efficiently divide the processing over the host system and the CSDs with
minimum overhead, we developed a scheduler that distributes applications onto
multiple nodes. This scheduler is MPI-based and developed in Python. It can
redirect requests or queries based on the availability of the nodes. Each node
sends an ack signal to the scheduler when the current processing batch is
done, which acts as a request for the next one. The scheduler runs on a
separate thread on the host and wakes up every 0.2 seconds to check if there
is a new message from the nodes. By putting the scheduler to sleep, the thread
releases the processor and thus increases the available processing power on
the host. Our setup uses the OCFS2 as the shared disk file system, which
enables both the host and the ISP to access the same shared data stored on the
flash[20]. As a result, the scheduler sends only the data indexes or addresses
to the ISP engine. This method significantly reduces the communication
overhead by eliminating one of the most important bottlenecks in a parallel
systems. It also increases the read/write speed, as all nodes access the data
at a much higher speed (GBps of PCIe/NVMe for the host and DMA/hardware for
the in-situ vs. MBps of TCP/IP) by communicating with the flash directly.

Figure 5: Experimental results for three NLP benchmarks and different
batchsizes.

Two important parameters for the scheduler are the _batch size_ , or the size
of the chunk of data that is assigned to each node at a time, and the _batch
ratio_ , which is the ratio between the batch size for the host and the ones
for the CSDs. The _batch ratio_ is determined based on the difference in the
processing power in a heterogeneous system. Since the host has a more powerful
CPU (Xeon) than the CSD does (ARM A53), the _batch ratio_ is considerably
large, ranging from 20 to 30 based on the experimental results. Any ratio
other than the optimal _batch ratio_ results in under-utilization of the
system. Using the _batch ratio_ decreases the workload of the scheduler and
also increases the host’s performance due to lower scheduling overhead and
larger chunks of data to process at a time. The batch size for each
application can be determined by running a small test to obtain the best range
for the batch size. In the following subsection, we will investigate the
performance of different configurations on our prototype. Note that due to
unavailability, we cannot compare our prototype with other CSD projects and
hence, we can just compare it with a baseline system that uses the CSD only as
an storage drive.

###  IV-B Results

####  IV-B1 Speech to text benchmark

This benchmark is developed based on Vosk, an offline speech recognition
toolkit [21]. Our dataset is LJ Dataset speech [22], a public-domain speech
dataset consisting of 13,100 short audio clips. The dataset is about 24 hours
long and consists of 225,715 words. By running a small benchmark on single
nodes, we get 102 words/sec and 5.3 words/sec processing speed for the host
and the CSDs, respectively. That yields an approximate batch size ratio of 20,
which we will use in the scheduler. This ratio is almost the same for all
three applications.

Fig. 5(a) shows the overall output of this benchmark in terms of the number of
transcribed words per second, based on the batch size and the number of
engaged CSDs. By augmenting the host with the processing power of all 36 CSDs,
the output rate increases from 96 words/sec to 296 words/sec for batch size of
6. That is 3.1x better performance compared to the host alone. Fig. 5(a) also
shows that the processing speed does not change much (less than 7%) when
varying the batch size. In terms of IO transfers, CSD engines processed 68% of
the input data ($(296-96)\div 296\simeq 0.68$), which means that 2.58 GB out
of the 3.8 GB of the dataset never left the storage unit, and the only output
of about 1.2 MB that was transferred to the host was the output text. This
reduction in number of IO’s and in data transfer size drastically reduces the
power consumption, network congestion, and use of the host’s CPU memory
bandwidth. It also enhances the security and the privacy aspects of the data
as it never leaves the storage device.

####  IV-B2 Movie Recommender Benchmark

Our second benchmark is a movie recommendation system based on [23]. The
recommender creates a new metadata entry for each movie, including the title,
genres, director, main actors, and the story line keywords. It then uses the
cosine similarity function to generate a similarity matrix that will be used
later to suggest contents. As an extra step, the ratings and the popularity
indexes will be used to filter the top results. For each query, the target
movie title is sent to the recommender function that returns the top-10
similar movies. We used the MovieLens Dataset [24], which consists of 27
million ratings and 1.1 million tag applications applied to 58,000 movie
titles by 280,000 users. We ran the training process once and stored the
matrix on flash for further uses. To simulate the queries, we made a list of
all movie titles and randomly shuffled them into a new list. Fig. 5(b) shows
the results for movie recommendation queries with different configurations.
With 36 drives, the system can address 1506 queries/second compared to the 579
queries/second of the standalone host, which is 2.6x improvement. Just like
the speech-to-text benchmark, changing the batch size does not significantly
affect the outcome by more than 3%.

####  IV-B3 Sentiment Analysis Benchmark

The last benchmark is a Twitter sentiment analysis app based on Python’s
Natural Language Toolkit (NLTK), depicted from [25] and modified to fit to our
parallelization goals. It uses labeled data to train a model to detect the
positivity or negativity of the tweet’s content and then uses the model to
predict the sentiment of the incoming tweets. Our test dataset consists of 1.6
million tweets [26] and are duplicated in cases where we need a larger number
of queries. We ran a single node test to evaluate the host and the CSDs
performance for different batch sizes. Unlike the other two benchmarks,
performance changes considerably based on the batch size. Fig. 6 shows the
performance in terms of queries per second for different batch sizes on a
logarithmic scale. It shows that as batch sizes increase, both Solana and the
host get better performance but also increased latency in processing some of
the queries. Because the input are sequentially fed to the nodes, once a batch
of queries is assigned to one processing node, each query has to wait for
prior queries in the same batch to finish but cannot be migrated to some other
idle nodes; in smaller batch sizes, different batches of queries could be
assigned to other available nodes and therefore the total wait time is less.
Based on these numbers, we set the batch size ratio to $9496\div 364\simeq 26$
and ran the benchmark with 8 million tweets. Fig. 5(c) shows the performance
for different batch sizes and on different numbers of CSDs. The best result is
for the batch size of 40k, where the number of queries per second increases
from 9496 to 20994, or 2.2x the performance.

###  IV-C Power and Energy Analysis

We measured the power and energy consumption of the server using an HPM-100A
power meter. The overall power consumption includes the host processor, the
storage systems, and peripherals including the cooling system. Since there is
no comparable E1.S drive on the market with 12 TB capacity, we choose the
baseline test system to be the same server but with the ISP engines disabled.
In idle mode, the server consumes 167 W without storage drives, or 405 W with
36 CSDs. Thus, each CSD consumes an average of 6.6 W, compared to 10-15 W for
commercial E1.S units with lower storage capacity in normal operation mode.
When we ran the benchmarks, the power consumption of the entire system was up
to 482 W without enabling ISP (i.e., CSD acting as storage only), compared to
492 W with all 36 ISP engines running. That is, each ISP engine consumes 0.28
W on top of the storage-only feature. Fig. 7 shows the normalized energy
consumption per query, or per word in the case of the text-to-speech
benchmark. We used a normalized diagram to better show the energy saving
trend. Table I summarizes the measured energy results along with a summary of
the experiments.

Figure 6: 1-node performance for sentiment analysis benchmark.

Figure 7: Energy per query, normalized to host-only setup. TABLE I: Summary of
the experimental results.

application |  speech to text |  recom- mender |  sentiment analysis
---|---|---|---
dataset size | 226K | 58K | 1.6M
output accuracy | same | same | same
max speedup | 3.1x | 2.8x | 2.2x
energy per query (host) (mJ) | 5021 | 832 | 51
energy per query (w/CSD) (mJ) | 1662 | 327 | 23
energy saving per query (%) | 67% | 61% | 54%
data processed on host (%) | 32% | 36% | 44%
data processed in CSDs (%) | 68% | 64% | 56%

##  V Conclusions

SSDs not only brought fast, power-efficient data storage but also new
opportunities for a new class of devices in the form of computational storage
drives (CSD) that can support near-data (or in-storage) processing. Moving
computation to storage not only eliminates most of the data transfers needed
and saves the time and energy, but also has the added benefit of better
privacy. All these benefits come at negligible cost, as the cost of the
storage system is dominated by the NAND chip.

In this work, we introduced Solana, the first 12TB Computational Storage Drive
in _E1.S_ form factor. Unlike other CSDs, Solana has an integrated In-Storage
Processing engine with the SSD controller on one chip, makes it a true ISP
capable drive. We demonstrated the effectiveness of deploying our proposed
design on storage servers which can achieve up to 3.1x speedup for a number of
common NLP applications, while reducing the energy consumption and data
transfer by 67% and 68%, respectively, compared to regular enterprise SSDs.
For future work, we plan to develop a data-aware distributed system that can
benefit not only from temporal locality but also from spacial locality of
data, by classifying queries into categorical groups and redirecting them to
associated nodes.

## References

  * [1] “How data is stored and what we do with it,” Nov 2017. [Online]. Available: https://insidebigdata.com/2017/11/12/how-data-is-stored-and-what-we-do-with-it/
  * [2] H. Bahn and K. Cho, “Implications of NVM based storage on memory subsystem management,” _Applied Sciences_ , vol. 10, p. 999, 2020.
  * [3] M. Naumov, D. Mudigere, H.-J. M. Shi, J. Huang, N. Sundaraman, J. Park, X. Wang, U. Gupta, C.-J. Wu, A. G. Azzolini, D. Dzhulgakov, A. Mallevich, I. Cherniavskii, Y. Lu, R. Krishnamoorthi, A. Yu, V. Kondratenko, S. Pereira, X. Chen, W. Chen, V. Rao, B. Jia, L. Xiong, and M. Smelyanskiy, “Deep learning recommendation model for personalization and recommendation systems,” 2019.
  * [4] S. Kim, H. Oh, C. Park, S. Cho, S.-W. Lee, and B. Moon, “In-storage processing of database scans and joins,” _Inf. Sci._ , vol. 327, no. C, p. 183–200, Jan. 2016. [Online]. Available: https://doi.org/10.1016/j.ins.2015.07.056
  * [5] S. Salamat, A. Haj Aboutalebi, B. Khaleghi, J. H. Lee, Y. S. Ki, and T. Rosing, “Nascent: Near-storage acceleration of database sort on smartssd,” in _The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , ser. FPGA ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 262–272. [Online]. Available: https://doi.org/10.1145/3431920.3439298
  * [6] M. Torabzadehkashi, S. Rezaei, V. Alves, and N. Bagherzadeh, “Compstor: An in-storage computation platform for scalable distributed processing,” in _2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)_. IEEE, 2018, pp. 1260–1267.
  * [7] M. Torabzadehkashi, S. Rezaei, A. Heydarigorji, H. Bobarshad, V. Alves, and N. Bagherzadeh, “Catalina: In-storage processing acceleration for scalable big data analytics,” in _2019 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)_ , 2019, pp. 430–437.
  * [8] M. Torabzadehkashi, _SoC-Based In-Storage Processing: Bringing Flexibility and Efficiency to Near-Data Processing_. University of California, Irvine, 2019.
  * [9] B. Gu, A. S. Yoon, D.-H. Bae, I. Jo, J. Lee, J. Yoon, J.-U. Kang, M. Kwon, C. Yoon, S. Cho, J. Jeong, and D. Chang, “Biscuit: A framework for near-data processing of big data workloads,” in _2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA)_ , 2016, pp. 153–165.
  * [10] J. H. Lee, H. Zhang, V. Lagrange, P. Krishnamoorthy, X. Zhao, and Y. S. Ki, “Smartssd: Fpga accelerated near-storage data analytics on ssd,” _IEEE Computer Architecture Letters_ , vol. 19, no. 2, pp. 110–113, 2020.
  * [11] M. Soltaniyeh, V. L. Moutinho Dos Reis, M. Bryson, R. Martin, and S. Nagarakatte, “Near-storage acceleration of database query processing with smartssds,” in _2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , 2021, pp. 265–265.
  * [12] S.-W. Jun, M. Liu, S. Lee, J. Hicks, J. Ankcorn, M. King, S. Xu, and Arvind, “BlueDBM: An appliance for big data analytics,” _SIGARCH Comput. Archit. News_ , vol. 43, no. 3S, p. 1–13, Jun. 2015. [Online]. Available: https://doi.org/10.1145/2872887.2750412
  * [13] K. Chapman, M. Nik, B. Robatmili, S. Mirkhani, and M. Lavasani, “Computational storage for big data analytics,” in _Proceedings of 10th International Workshop on Accelerating Analytics and Data Management Systems (ADMS’19)_ , 2019\.
  * [14] M. Wilkening, U. Gupta, S. Hsia, C. Trippel, C.-J. Wu, D. Brooks, and G.-Y. Wei, _RecSSD: Near Data Processing for Solid State Drive Based Recommendation Inference_. New York, NY, USA: Association for Computing Machinery, 2021, p. 717–729. [Online]. Available: https://doi.org/10.1145/3445814.3446763
  * [15] [Online]. Available: http://www.openssd.io/
  * [16] J. Do, V. C. Ferreira, H. Bobarshad, M. Torabzadehkashi, S. Rezaei, A. Heydarigorji, D. Souza, B. F. Goldstein, L. Santiago, M. S. Kim, P. M. V. Lima, F. M. G. França, and V. Alves, “Cost-effective, energy-efficient, and scalable storage computing for large-scale ai applications,” _ACM Trans. Storage_ , vol. 16, no. 4, oct 2020. [Online]. Available: https://doi.org/10.1145/3415580
  * [17] A. HeydariGorji, S. Rezaei, M. Torabzadehkashi, H. Bobarshad, V. Alves, and P. H. Chou, “Hypertune: Dynamic hyperparameter tuning for efficient distribution of dnn training over heterogeneous systems,” in _2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD)_ , 2020, pp. 1–8.
  * [18] M. Torabzadehkashi, A. Heydarigorji, S. Rezaei, H. Bobarshad, V. Alves, and N. Bagherzadeh, “Accelerating hpc applications using computational storage devices,” in _2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)_. IEEE, 2019, pp. 1878–1885.
  * [19] M. Torabzadehkashi, S. Rezaei, A. HeydariGorji, H. Bobarshad, V. Alves, and N. Bagherzadeh, “Computational storage: an efficient and scalable platform for big data and hpc applications,” _Journal of Big Data_ , vol. 6, no. 1, pp. 1–29, 2019.
  * [20] A. HeydariGorji, M. Torabzadehkashi, S. Rezaei, H. Bobarshad, V. Alves, and P. H. Chou, “Stannis: Low-power acceleration of dnn training using computational storage devices,” in _2020 57th ACM/IEEE Design Automation Conference (DAC)_ , 2020, pp. 1–6.
  * [21] [Online]. Available: https://alphacephei.com/vosk/
  * [22] K. Ito and L. Johnson, “The LJ speech dataset,” https://keithito.com/LJ-Speech-Dataset/, 2017.
  * [23] J. Ng, “Content-based recommender using natural language processing (NLP),” Apr 2020. [Online]. Available: https://towardsdatascience.com/content-based-recommender-using-natural-language-processing-nlp-159d0925a649
  * [24] “Movielens,” Mar 2021. [Online]. Available: https://grouplens.org/datasets/movielens/
  * [25] DigitalOcean, “How to perform sentiment analysis in Python 3 using the natural language toolkit (NLTK),” Jan 2021. [Online]. Available: https://www.digitalocean.com/community/tutorials/how-to-perform-sentiment-analysis-in-python-3-using-the-natural-language-toolkit-nltk
  * [26] A. Go, R. Bhayani, and L. Huang, “Twitter sentiment classification using distant supervision,” _Processing_ , vol. 150, 01 2009.


# Recovering Dropped Pronouns in Chinese Conversations via
Modeling Their Referents

Jingxuan Yang, Jianzhuo Tong, Si Li ∗, Sheng Gao, Jun Guo, Nianwen Xue †
Beijing University of Posts and Telecommunications
†Brandeis University
{yjx, tongjianzhuo, lisi, gaosheng<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Pronouns are often dropped in Chinese sentences, and this happens more
frequently in conversational genres as their referents can be easily
understood from context. Recovering dropped pronouns is essential to
applications such as Information Extraction where the referents of these
dropped pronouns need to be resolved, or Machine Translation when Chinese is
the source language. In this work, we present a novel end-to-end neural
network model to recover dropped pronouns in conversational data. Our model is
based on a structured attention mechanism that models the referents of dropped
pronouns utilizing both sentence-level and word-level information. Results on
three different conversational genres show that our approach achieves a
significant improvement over the current state of the art. ††footnotetext: ∗
Corresponding author

##  1 Introduction

Chinese is a pro-drop language, meaning that it is not always necessary to
have an overt pronoun when the referent is clear from the context. This is in
contrast with a non-pro-drop language like English, where an overt pronoun is
always needed. For example, Kim Kim (2000) shows that an overt subject is used
only in 64% of the cases in Chinese while that percentage is over 96% in
English.

Even in pro-drop languages like Chinese, pronouns are omitted to different
degrees in different genres. Pronouns are dropped more often in informal
conversational genres than in formal genres like newswire. Recovering these
dropped pronouns (DPs) is important to applications such as Machine
Translation where dropped pronouns need to be made explicit when Chinese is
translated into a target language Wang et al. (2016a, b, 2018) or Information
Extraction where relations might involve entities referred to by these DPs.

Figure 1: An example conversation between two people. The first dropped
pronoun refers to “this computer” in the first sentence and is translated into
“it” in English. It needs to be recovered from the wider context.

More concretely, recovering DPs involves i) first locating the position in a
sentence where a pronoun is dropped, and ii) determining the type of the
pronoun that is dropped. This is illustrated in Figure 1, where the recovered
dropped pronouns are in parenthesis. Both instances of dropped pronouns can be
replaced with the overt pronoun 它 (“it”), but they refer to different things
in the conversation. Dropped pronoun recovery is different from zero pronoun
(ZP) resolution Chen and Ng (2015); Yin et al. (2017, 2018) where the focus is
on resolving an anaphoric pronoun to its antecedent, assuming the position of
the zero pronoun is already determined. Here we do not attempt to resolve the
dropped pronoun to its referent. Dropped pronoun recovery can thus be viewed
as the first step of zero pronoun resolution, but this task is also important
in its own right. In applications like machine translation, dropped pronouns
only need to be identified and translated correctly but they do not need to be
resolved.

Traditionally dropped pronoun recovery has been formulated as a sequence
labeling problem where each word in the sentence receives a tag that indicates
whether the word has a dropped pronoun before it and which pronoun is dropped.
Yang et al. Yang et al. (2015) leverages lexical, contextual and syntactic
features to detect DPs before each word from a predefined list of pronouns.
Giannella et al. Giannella et al. (2017) utilizes a linear-chain conditional
random field (CRF) classifier to simultaneously predict the position as well
as the person number of a dropped pronoun based on lexical and syntactic
information. These featured-based methods require labor-intensive feature
engineering.

In contrast, Zhang et al. Zhang et al. (2016) uses a multi-layer perceptron
based neural network model to recover dropped pronouns, which eliminates the
need for feature engineering. The input to their model is a context embedding
constructed by concatenating the embeddings of word tokens in a fixed-length
window. However, the referent of a dropped pronoun that provides crucial
information to determine the identity of a pronoun is typically found outside
the local context of the dropped pronoun, and thus cannot be effectively
modeled with a window-based multi-layer perceptron model. For example, in
Figure 1 the referent of the first dropped pronoun, the third person singular
pronoun 它 (“it”) is 电脑 (“computer”), which appears in the very first
utterance, several utterances before the pro-drop sentence. Therefore, long-
distance contextual information needs to be captured in order to determine the
type of the dropped pronoun.

In this paper, we describe a novel Neural Dropped Pronoun Recovery framework,
named NDPR that can model the referent information in a much larger context.
The model makes use of contextual information at two levels of granularity:
the sentence level and the word level. An illustration of the NDPR framework
is given in Figure 2. The referent modeling process is implemented with a
structured attention mechanism. For each word token in the pro-drop sentence,
the model attends to the utterance in which the referent of the dropped
pronoun is mentioned by sentence attention and then zeros in to the referent
by word attention. The resulting referent representation is combined with the
representation of the dropped pronoun to make the final prediction on the
location and type of the dropped pronoun. We demonstrate the effectiveness of
our proposed model on three Chinese conversational datasets and results show
that our approach outperforms the current state of the art by a fairly large
margin.

Figure 2:  Neural Dropped Pronoun Recovery Framework.

We also perform ablation studies to explore the contribution of the different
components of our model. We show that word-level attention is more effective
in recovering concrete pronouns because it serves as a matching mechanism that
matches the representation of the dropped pronoun against that of the DP
referent. In contrast, sentence-level attention can be considered as an
auxiliary tool for word-level attention to improve model accuracy by filtering
out irrelevant referents. All code is available at
https://github.com/ningningyang/NDPR.

Our contributions are summarized as follows:

  * •

We propose a novel attention-based neural network to recover dropped pronouns
in Chinese conversational data by modeling their referent.

  * •

We evaluate our system on three conversational genres and show that our model
consistently outperforms the state of the art by a large margin on all three
datasets.

  * •

We also present experimental results that demonstrate the effectiveness of
various components in our framework and analyze some mistakes made by our
model on each dataset.

##  2 Related Work

###  2.1 Dropped pronoun recovery.

Dropped pronoun detection originates from Empty Category (EC) detection and
resolution, a task aimed to recover certain dropped elements in syntactic
treebanks Chung and Gildea (2010); Cai et al. (2011); Xue and Yang (2013).
Dropped pronoun recovery was first proposed as an independent task in Yang et
al. (2015), which leveraged a set of specially designed features to recover
DPs in Chinese text messages. Giannella et al. Giannella et al. (2017)
employed a linear-chain CRF classifier to jointly determine the position and
person number of dropped pronouns in Chinese SMS messages using hand-crafted
features. These traditional feature-based methods require heavy feature
engineering. Zhang et al. Zhang et al. (2016) for the first time utilized a
multi-layer perceptron model to recover dropped pronouns. Each word is
expressed as a concatenation of embeddings of word tokens in a fixed-length
window. This method can not resolve the cases when referents are outside the
local context, which is a common occurrence in conversational data. There has
also been some work that attempts to recover dropped pronoun in pro-drop
languages to help Machine Translation Wang et al. (2016a, b, 2018). There are
some inherent differences between their work and ours. In their work, they
attempt to create training data by projecting pronouns from another language
to Chinese, and the specific location of a dropped pronoun may not matter as
much as long as it is translated correctly when Chinese is the source
language. In contrast, we focus on recovering DPs from conversational context,
and determining the correct position of a dropped pronoun is critical part of
the task.

###  2.2 Zero pronoun resolution.

A line of research that is closely related to our task is zero pronoun (ZP)
resolution, which aims to resolve Chinese pronouns to their antecedents.
Converse and Palmer Converse and Palmer (2006) presented a rule-based method
to resolve ZP by utilizing the Hobbs algorithm Hobbs (1978). Learning-based
anaphoric resolution approaches have also been extensively explored. Zhao and
Ng Zhao and Ng (2007) and Kong and Zhou Kong and Zhou (2010) proposed systems
that perform ZP resolution by integrating syntactic features and position
information in a system based on decision trees and context-sensitive
convolution tree kernels. With the powerful learning capacity of neural
networks, recent work focuses on learning representations to resolve zero
pronouns or common noun phrases Ng (2007); Yin et al. (2017, 2018). The DP
recovery task explored in our work focuses on determining the position and
type of dropped pronoun without attempting to resolve it to an antecedent.

###  2.3 Attention and memory network.

The attention mechanism is first proposed for neural machine translation
Bahdanau et al. (2014) and has been attempted in a variety of natural language
processing tasks Bahdanau et al. (2014); Hermann et al. (2015). Kim Kim et al.
(2017) extended the basic attention mechanism to incorporate structural biases
by combining graphical models with neural networks. Yang et al. Yang et al.
(2016) proposed a word and sentence-level hierarchical attention network for
document classification. Xing et al. Xing et al. (2018) also presented a
hierarchical recurrent attention network (HRAN) to model the hierarchy of
conversation context in order to generate multi-turn responses in chatbots. In
contrast with these bottom-up mechanisms, our model adopts a top-down
structured attention mechanism to construct the representation for a DP. Our
model attempts to identify utterances which contain the referent of a DP, and
then focus in on the representation of the referent itself. Our model draws
inspiration from the memory network and its variants Weston et al. (2015);
Sukhbaatar et al. (2015); Henaff et al. (2017); Miller et al. (2016), where an
external memory component is used to store and update knowledge.

##  3 Approach

Following Yang et al. (2015), we formulate DP recovery as a sequential tagging
problem. Given an input sentence $X=(x_{1},x_{2},...,x_{s})$ and its
contextual utterances $\bm{C}=(X_{1},...,X_{m})$, our task is to model
$P(Y|X,\bm{C})$ and predict a set of labels $Y=(y_{1},y_{2},...,y_{s})$. Each
element of $Y$ indicates whether a pronoun is dropped and which type it should
be before each word in the sentence $X$. The NDPR model consists of three
components: (1) Input Layer; (2) Referent Modeling Layer; (3) Output Layer. We
describe them in detail below.

###  3.1 Input Layer

This layer converts the raw inputs $X$ and $\bm{C}$ into distributed
representations.

####  3.1.1 Sentence $X$

During the encoding process, the input sentence of length $s$, is transformed
into a sequence of $d$-dimensional word embeddings at first, and then fed into
two different kinds of bidirectional recurrent neural networks (RNN) Elman
(1991):

  * •

BiGRU Bahdanau et al. (2014): Each word $x_{n},n\in\\{1,...,s\\}$ of the
sentence is represented as a concatenation of forward and backward hidden
states as:
$\bm{h_{n}}=[\bm{\overleftarrow{h}_{n}},\bm{\overrightarrow{h}_{n}}]$. We aim
to express DP by the hidden state of the first word after DP.

  * •

PC-BiGRU Yin et al. (2017): Pronoun-centered BiGRU (PC-BiGRU) also contains
two independent GRU networks. For each word $x_{n},n\in\\{1,...,s\\}$, the
forward GRUf encodes the preceding context of DP from left to right as
$\bm{\overrightarrow{h}_{n-1}}$, and the backward GRUb models the succeeding
context as $\bm{\overleftarrow{h}_{n}}$ in the reverse direction. Final hidden
state of DP is also concatenated as
$\bm{h_{n}}=[\bm{\overleftarrow{h}_{n}},\bm{\overrightarrow{h}_{n-1}}]$. The
intuition of this structure is to express DP by the last word before DP and
the first word after DP.

####  3.1.2 Context $\bm{C}$

The context provides the necessary background information to recover DPs. In
our work, we utilize five utterances preceding the one the DP is in and two
utterances following current input sentence $X$ as context C. The size of C is
determined empirically since our statistics show that $97\%$ of the dropped
pronouns can be inferred based on information in the 7 sentences surrounding
the sentence in which the dropped pronoun occurs. The context C passes through
the same encoder as $X$, yielding two kinds of memories: (1) sentence-level
memory: concatenated final states of the forward and backward GRU for each
contextual utterance $i=\\{1,...,m\\}$ as
$\bm{cs_{i}}=[\bm{\overleftarrow{cs}_{i}},\bm{\overrightarrow{cs}_{i}}]$,
holding sentence level background knowledge. (2) word-level memory: a set of
concatenated hidden states at each time step $j=\\{1,...,k\\}$ as
$\bm{cw_{i,j}}=[\bm{\overleftarrow{cw}_{i,j}},\bm{\overrightarrow{cw}_{i,j}}]$,
expressing the contextual information of words in memory.

Figure 3: Counts of each type of dropped pronouns in different conversational
data sets. Pronouns have a more balanced distribution in Chinese SMS and
telephone conversation(TC). For BaiduZhidao, only concrete pronouns are
annotated and the distribution of these pronouns is extremely uneven.

###  3.2 Referent Modeling layer

The referent modeling layer models the interaction between the input sentence
$X$ and its context $\bm{C}$ and outputs representation of DP referents. The
relevant information for predicting the dropped pronoun is retrieved by a two-
step attention-based inference mechanism in which the intermediate results of
sentence-level attention is utilized to support subsequent word-level
inference.

####  3.2.1 Identify utterances mentioning DP

This operation aims to figure out which utterances mention the intended
referent of DP. We compute the relevance between the hidden states
$\bm{h_{n}}$ representing the DP and its sentence level contextual
representation $\bm{cs_{i}}$, resulting in $rs_{n,i}$. After passing it
through softmax, we obtain a sentence-level attention distribution $as_{n,i}$
as:

$rs_{n,i}=\bm{h_{n}}^{T}\bm{cs_{i}}$ (1)
$as_{n,i}=\frac{e^{rs_{n,i}}}{\sum\nolimits_{i=1}^{m}e^{rs_{n,i}}}$ (2)

We then conclude sentence-level background information $\bm{s_{n}}$ of DP as a
weighted sum of contextual utterance representations:

$\bm{s_{n}}=\sum_{i=1}^{m}as_{n,i}\cdot\bm{cs_{i}}$ (3)

####  3.2.2 Update DP representation

This operation updates representation of the DP by combining the original DP
information $\bm{h_{n}}$ with sentence-level background knowledge $\bm{s_{n}}$
through a linear transformation as:

$\bm{hs_{n}}=\bm{W^{2d\times 4d}}[\bm{h_{n}},\bm{s_{n}}]+\bm{b^{2d}},$ (4)

The updated DP state $\bm{hs_{n}}$ will be used in subsequent word level
inference.

####  3.2.3 Identify DP referents

This operation aims to capture the word sequence that represents the intended
referent of the DP. We cast the updated DP state $\bm{hs_{n}}$ onto the space
of contextual words $\bm{cw_{i,j}}$ by measuring the similarity $rw_{n,i,j}$
between them. The casting operation also serves as a regularization measure to
restrict the inference space. The similarities are fed into the softmax
function to give a word-level attention distribution $aw_{n,i,j}$ for each
contextual word as:

$rw_{n,i,j}=\bm{W^{1\times 2d}}(\bm{hs_{n}}\odot\bm{cw_{i,j}})+b^{1}$ (5)
$aw_{n,i,j}=\frac{e^{rw_{n,i,j}}}{\sum\nolimits_{j=1}^{k}e^{rw_{n,i,j}}},$ (6)

The attention distribution $aw_{n,i,j}$ also provides an interpretation for DP
recovery results based on the words it attends to.

Finally, we derive the word-level representation $\bm{w_{n}}$ from word states
$\bm{cw_{i,j}}$. Word-level attention $aw_{n,i,j}$ is used to compute a
weighted sum of contextual word states $\bm{cw_{i,j}}$ of each utterance,
yielding the referent representation $\bm{tw_{n,i}}$. Then, sentence-level
attention $as_{i}$ further filters out irrelevant referents, yielding the
final referent representation $\bm{w_{n}}$ as:

$\bm{tw_{n,i}}=\sum_{j=1}^{k}aw_{n,i,j}\cdot\bm{cw_{i,j}}$ (7)
$\bm{w_{n}}=\sum_{i=1}^{m}as_{n,i}\cdot\bm{tw_{n,i}}$ (8)

###  3.3 Output Layer and Training Objective

The output layer predicts the recovery result based on DP state $\bm{h_{n}}$
and referent representation $\bm{w_{n}}$. We feed the concatenation of these
two parts into a 2-layer fully connected softmax classifier to give a
categorical probability distribution over 17 candidate pronouns as:

$\bm{\alpha_{n}}=tanh(\bm{W_{1}}\cdot[\bm{h_{n};w_{n}}]+\bm{b})$ (9)
$P(y_{n}|x_{n},\\!\bm{C})\\!=softmax(\bm{W_{2}}\cdot\bm{\alpha_{n}}+\bm{b})$
(10)

We train our model by minimizing cross-entropy between the predicted label
distributions and the annotated labels for all sentences. The training
objective is defined as:

$\\!loss\\!=\\!-\\!\sum_{l\in
N}\\!\sum_{n=1}^{s}\\!\delta(y_{n}|x_{n},\\!\bm{C})\\!\log(P(y_{n}|x_{n},\\!\bm{C})),$

(11)

where $N$ represents all training instances, $s$ represents the number of
words in each sentence; $\delta(y_{n}|x_{n},c)$ represents the annotated label
of $x_{n}$.

##  4 Datasets and Experimental Setup

###  4.1 Datasets

We perform experiments on three Chinese conversational datasets.

  * •

Chinese text message (SMS) data, which consists of 684 SMS/Chat files. We use
the same dataset split as Yang et al. (2015), which reserves $16.7\%$ of the
training set as a held-out development set to tune the hyper-parameters and
evaluate the model on a separate test set.

  * •

OntoNotes Release 5.0, which is used in the CoNLL 2012 Shared Task. We use a
portion of OntoNotes 5.0 that consists of transcripts of Chinese telephone
conversation (TC) speech. The 9,507-sentence subset of OntoNotes only has
coreference annotations for anaphoric zero pronouns. In order to formulate the
task as an end-to-end sequence labeling task, we annotate all the dropped
pronouns following annotation guidelines described in Yang et al. (2015).

  * •

BaiduZhidao, which is a question answering dialogue dataset used in Zhang et
al. (2016). It contains 11,160 sentences that are annotated with 10 types of
concrete dropped pronouns.

Figure 3 shows the statistics of each type of pronouns in the three data sets.
According to Yang et al. (2015), 5 out of 15 types of dropped pronouns in the
SMS data set are abstract pronouns that do not correspond to any actual
pronoun in Chinese. These can refer to an event (Event), the previous
utterance (Previous Utterance), or an generic or unspecific entity (Generic).
The other two abstract pronouns are used to indicate the subject of an
existential construction (Existential) or a pleonastic subject (Pleonastic).
The other ten types of Chinese pronouns are classified as concrete pronouns.
The same 15 types of pronouns are used to annotate the TC data. We can see
that the BaiDuZhidao data set only has concrete pronouns.

###  4.2 Evaluation metrics

We use the same evaluation metrics as Yang et al. (2015): precision (P),
recall (R) and F-score (F).

Model | Chinese SMS | TC of OntoNotes | BaiduZhidao
---|---|---|---
P(%) |  R(%) |  F |  P(%) |  R(%) |  F |  P(%) |  R(%) |  F
MEPR Yang et al. (2015) |  37.27 |  45.57 |  38.76 |  - |  - |  - |  - |  - |  -
NRM∗ Zhang et al. (2016) |  37.11 |  44.07 |  39.03 |  23.12 |  26.09 |  22.80 |  26.87 |  49.44 |  34.54
BiGRU |  40.18 |  45.32 |  42.67 |  25.64 |  36.82 |  30.93 |  29.35 |  42.38 |  35.83
NDPR-rand |  46.47 |  43.23 |  43.58 |  28.98 |  41.50 |  33.38 |  35.44 |  43.82 |  37.79
NDPR-PC-BiGRU |  46.34 |  46.21 |  46.27 |  36.69 |  40.12 |  38.33 |  38.42 |  48.01 |  41.68
NDPR-W |  46.78 |  46.61 |  45.76 |  38.67 |  41.56 |  39.64 |  38.60 |  50.12 |  43.36
NDPR-S |  46.99 |  46.32 |  44.89 |  37.40 |  40.32 |  38.81 |  39.32 |  46.40 |  41.53
NDPR |  49.39 |  44.89 |  46.39 |  39.63 |  43.09 |  39.77 |  41.04 |  46.55 |  42.94
Table 1:  Results in terms of precision, recall and F-score on 16 types of
pronouns produced by the baseline systems and variants of our proposed NDPR
model. For NRM∗ Zhang et al. (2016), we implement the proposed model as
described in the paper.

###  4.3 Training details

Our model is implemented with Tensorflow. The vocabulary is generated from the
training set, which contains 17,199 word types. Out-of-vocabulary (OOV) words
are represented as UNK. The BiGRU encoder uses a hidden layer of 150 units. To
train the model, we use the Adam optimizer Kingma and Ba (2015) with a
learning rate of 0.0003. We train the model for 8 epochs and select the model
with the highest F-score on the development set for testing. Dropout rate is
set at 0.2 on the fully connected layers. We use uniform initialization for
the weight matrices and zero initialization for biases.

###  4.4 Baseline Methods and Model Variations

We compare our proposed NDPR framework with three baselines and implement two
parallel experiments:

  * •

MEPR: This model is provided by Yang Yang et al. (2015), which uses a maximum
entropy (ME) classifier with hand-crafted features to recover dropped
pronouns.

  * •

NRM: This model is proposed by Zhang Zhang et al. (2016), which uses two
independent multi-layer perceptrons to locate the position of dropped pronouns
and determine the type of dropped pronouns.

  * •

BiGRU: This model encodes each word in the target sentence with a
bidirectional GRU. The output representation of the BiGRU encoder is used to
predict the type of the dropped pronoun. This method can be seen as a
degenerate variant of our NDPR model without the attention mechanism.

  * •

NDPR: This model uses the BiGRU encoder with both sentence-level and word-
level attention. The word embeddings are initialized with pre-trained 300-D
Zhihu QA vectors Li et al. (2018) and fine-tuned when training the DP recovery
model.

  * •

NDPR-rand: Same as NDPR except that the word embeddings are randomly
initialized.

  * •

NDPR-PC-BiGRU: Same as NDPR but the encoder of utterance $X$ is replaced with
PC-BiGRU.

We also perform two ablation experiments to explore the effectiveness of
sentence-level attention and word-level attention:

  * •

NDPR-S: Same as NDPR but the referent modeling layer only utilizes sentence-
level attention. The output layer makes prediction with only DP state
$\bm{h_{n}}$ and sentence level information $\bm{s_{n}}$.

  * •

NDPR-W: Same as NDPR but the referent modeling layer only utilizes word-level
attention. The output layer makes prediction with only DP state $\bm{h_{n}}$
and word-level information $\bm{w_{n}}$.

##  5 Results and Discussion

Tag |  NDPR-S |  NDPR-W |  NDPR
---|---|---|---
他们(masculine they) |  17.05 |  23.28 |  24.44
她(she) |  32.35 |  33.72 |  35.14
previous utterance |  84.90 |  86.08 |  87.55
他(he) |  29.05 |  31.20 |  34.92
它(it) |  25.00 |  26.67 |  26.95
她们(feminine they) |  0 |  0 |  40.00
我(I) |  50.66 |  50.90 |  52.98
我们(we) |  31.49 |  33.57 |  34.81
你(singular you) |  42.88 |  44.15 |  44.31
pleonastic |  25.89 |  22.29 |  28.46
generic |  11.61 |  11.08 |  16.83
event |  6.15 |  0 |  16.27
existential |  34.17 |  30.84 |  38.71
你们(plural you) |  0 |  0 |  5.41
它们(inanimate they) |  16.00 |  19.15 |  13.89
|  |  |
Table 2:  F-scores of our proposed model NDPR and its two variants (NDPR-S,
NDPR-W) for concrete and abstract pronouns on the Chinese SMS test set.

###  5.1 Main Results

Table 1 shows experimental results of three baseline systems and variants of
our proposed NDPR model on Chinese SMS, TC section of OntoNotes, and
BaiduZhidao. We can see that our proposed model and its variants outperform
the baseline methods on all these datasets by different margins. Our best
model, NDPR, outperforms MEPR by 7.63% in terms of F-score on the Chinese SMS
dataset, and outperforms NRM by 16.97% and 8.40% on the OntoNotes and
BaiduZhidao datasets respectively. Compared with the degenerate variant model
BiGRU, our NDPR model also performs better on all three datasets, which
demonstrate the effectiveness of referent modeling mechanism composed of
sentence-level and word-level attention.

The experimental results also show that all components of our model have made
a positive contribution, which is evidenced by the fact that the full model
NDPR outperforms the other variants by a small margin. The results also show
that pre-trained word embeddings have had a positive impact on the model, as
shown by the higher accuracy of the NDPR model over the NDPR-rand model, where
the word embeddings are randomly initialized.

PC-BiGRU encoder seems to perform worse than vanilla BiGRU encoder, as shown
by the slightly lower F-score of the NDPR-PC-BiGRU model. But it alleviates
what we call the local pronoun repetition problem, the situation where a DP is
recovered redundantly in a sentence before a verb and its adverbial modifier.
We attribute this to that PC-BiGRU uses the context state $\bm{h_{n-1}}$ of
the last word before DP instead of $\bm{h_{n}}$, which makes the model pay
more attention to the preceding modifier.

For the BaiduZhidao dataset, the NDPR-W model actually performs better than
NDPR model, as indicated by the higher F-score for NDPR-W in the last column
of Table 1. We attribute this to the fact that there are only concrete
pronouns in this dataset. The combination of “我(I)”, “你(singular you)” and
“它(it)” accounts for $94.47\%$ of the overall dropped pronoun population, for
which the referent can be easily determined by word-level attention. Moreover,
the fewer conversation turns in this data set mean there are few irrelevant
referents that need to be filtered out by sentence-level attention.

###  5.2 Ablation Study

In this section, we dive a bit deeper and look at the impact of the attention
mechanism on concrete and abstract pronouns, respectively. Table 2 shows the
F-scores of three variants of our proposed model for each type of pronouns on
the entire Chinese SMS test set. The best results among these three variants
are in boldface, and the better results between NDPR-S and NDPR-W are
underlined.

Figure 4:  Visualization of attention in the NDPR model. The red pattern on
the left shows the distribution of sentence-level attention and the blue
pattern on the right shows the distribution of word-level attention. Darker
color indicates higher attention weight.

We can see that for all types of concrete pronouns, the NDPR-W model
outperforms the NDPR-S model by a significant margin. In general, the referent
of concrete dropped pronoun is usually realized in the form of a phrase that
consists of one or more word, and they can be accurately captured by word-
level attention. The NDPR model that incorporates both word-level and
sentence-level attention further improves upon NDPR-W, with the lone exception
of 它们 (“they”). We believe the reason is that the sentence-level encoder
cannot adequately represent the interaction between the multiple referents for
plural pronouns like 它们 and only add noise to the representation.

However, this observation does not hold for abstract dropped pronouns. The
NDPR-W performs comparably or slightly worse on four out of the five types of
abstract pronouns. This is consistent with the fact that the referent of
abstract pronouns like “Event” is often an entire sentence. The full NDPR
model still outperforms both NDPR-W and NDPR-S for all abstract pronouns.

Figure 5:  Example errors made by NDPR on different conversational datasets.

###  5.3 Attention Visualization

Intuitively, sentence-level attention models the interaction between the
dropped pronoun and each context utterance. The utterance containing the
referent of the dropped pronoun should receive more attention. Similarly,
word-level attention models the interaction between each word in the context
and the dropped pronoun. Thus words that describe the referent of the pronoun
should receive more attention if the model works as intended. Figure 4 shows a
instance of attention distribution produced by our model.

In this example, the model correctly gives higher attention weights to three
utterances that contain words that indicate the referent of the pronoun. At
word level, the model also gives higher attention weights to the specific
words that indicate the referent of the dropped pronoun. For example, words
such as 她 (“she”) and 女儿 (“daughter”) have received higher weights, as
indicated by the darker color. This suggests that in this case the model
attends to the right utterances and words and works as we have expected.

###  5.4 Error Analysis

Figure 5 shows some typical mistakes made by our model on each genre. For the
Chinese SMS dataset, the distribution of different types of pronouns is
relatively balanced (See Table 3), and our model does a better job on concrete
pronouns but stumbles on abstract pronouns like “event” and “generic” as shown
in Table 2 as it is harder to attend to the correct parts of the context in
these cases.

The TC data of OntoNotes is a transcription of telephone conversations where
there are often repetitions, and our model struggles when people repeat what
they said. If the same pronoun is mentioned repeatedly, our model can not
capture this interaction, since each pronoun is recover independently. This
suggests that one future improvement might involve using a sequence-based
decoder.

In the BaiduZhidao dataset, only concrete pronouns are annotated as shown in
Figure 3. Pronouns like 它 (“it”) and 它们 (“they”) account for a large
proportion of all dropped pronouns. For these two categories, the performance
of our proposed method is hit-and-miss, which can be attributed to the absence
of pronoun resolution common sense.

##  6 Conclusions

We have proposed an end-to-end neural network architecture that attempts to
model the interaction between the dropped pronoun and its referent in order to
recover dropped pronouns in Chinese conversational data. Our model is based on
sentence-level and word-level attention and results show that our model
consistently outperforms baseline methods when evaluated on three separate
datasets. We further investigate the effectiveness of different components of
our model by performing ablation experiments and demonstrate the
interpretability of our model using attention visualization.

## Acknowledgments

This work was supported by the National Natural Science Foundation of China
(No.61702047, No.61300080) and Beijing Natural Science Foundation
(No.4174098).

## References

  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Y Bengio. 2014.  Neural machine translation by jointly learning to align and translate.  _Computer Science._ , 1409.
  * Cai et al. (2011) Shu Cai, David Chiang, and Yoav Goldberg. 2011.  Language-independent parsing with empty elements.  pages 212–216. Proceedings of the Meeting of the Association for Computational Linguistics.
  * Chen and Ng (2015) Chen Chen and Vincent Ng. 2015.  Chinese zero pronoun resolution: A joint unsupervised discourse-aware model rivaling state-of-the-art resolvers.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing._ , volume 2, pages 320–326.
  * Chung and Gildea (2010) Tagyoung Chung and Daniel Gildea. 2010.  Effects of empty categories on machine translation.  pages 636–645.
  * Converse and Palmer (2006) Susan P Converse and Martha Stone Palmer. 2006.  _Pronominal anaphora resolution in Chinese_.  Citeseer.
  * Elman (1991) Jeffrey L. Elman. 1991.  _Distributed Representations, Simple Recurrent Networks, And Grammatical Structure_.  Springer US.
  * Giannella et al. (2017) Chris Giannella, Ransom K Winder, and Stacy Petersen. 2017.  Dropped personal pronoun recovery in chinese sms.  _Natural Language Engineering_ , 23(06):905–927.
  * Henaff et al. (2017) Mikael Henaff, Jason Weston, Arthur Szlam, Antoine Bordes, and Yann Lecun. 2017\.  Tracking the world state with recurrent entity networks.  _International Conference on Learning Representations._
  * Hermann et al. (2015) Karl Moritz Hermann, Tomas Kociský, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015.  Teaching machines to read and comprehend.  _Advances in Neural Information Processing Systems._ , pages 1693–1701.
  * Hobbs (1978) Jerry R Hobbs. 1978.  Resolving pronoun references.  _Lingua_ , 44(4):311–338.
  * Kim et al. (2017) Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. 2017.  Structured attention networks.  _International Conference on Learning Representations_.
  * Kim (2000) Young Joo Kim. 2000.  Subject/object drop in the acquisition of korean: A cross-linguistic comparison.  _Journal of East Asian Linguistics._ , 9(4):325–351.
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  _International Conference on Learning Representations._
  * Kong and Zhou (2010) Fang Kong and Guodong Zhou. 2010.  A tree kernel-based unified framework for chinese zero anaphora resolution.  In _Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing._ , pages 882–891. Association for Computational Linguistics.
  * Li et al. (2018) Shen Li, Zhe Zhao, Renfen Hu, Wensi Li, Tao Liu, and Xiaoyong Du. 2018.  Analogical reasoning on chinese morphological and semantic relations.  _Proceedings of the Meeting of the Association for Computational Linguistics._
  * Miller et al. (2016) Alexander H Miller, Adam Fisch, Jesse Dodge, Amirhossein Karimi, Antoine Bordes, and Jason Weston. 2016.  Key-value memory networks for directly reading documents.  _Conference on Empirical Methods in Natural Language Processing._ , pages 1400–1409.
  * Ng (2007) Vincent Ng. 2007.  Semantic class induction and coreference resolution.  In _Proceedings of the Meeting of the Association for Computational Linguistics, June 23-30, 2007, Prague, Czech Republic_ , pages 536–543.
  * Sukhbaatar et al. (2015) Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, et al. 2015.  End-to-end memory networks.  In _Advances in Neural Information Processing Systems._ , pages 2440–2448.
  * Wang et al. (2018) Longyue Wang, Zhaopeng Tu, Shuming Shi, Tong Zhang, Yvette Graham, and Qun Liu. 2018\.  Translating pro-drop languages with reconstruction models.  _arXiv preprint arXiv:1801.03257_.
  * Wang et al. (2016a) Longyue Wang, Zhaopeng Tu, Xiaojun Zhang, Hang Li, Andy Way, and Qun Liu. 2016a.  A novel approach to dropped pronoun translation.  _arXiv preprint arXiv:1604.06285_.
  * Wang et al. (2016b) Longyue Wang, Xiaojun Zhang, Zhaopeng Tu, Hang Li, and Qun Liu. 2016b.  Dropped pronoun generation for dialogue machine translation.  In _Acoustics, Speech and Signal Processing (ICASSP), 2016 IEEE International Conference on_ , pages 6110–6114. IEEE.
  * Weston et al. (2015) Jason Weston, Sumit Chopra, and Antoine Bordes. 2015.  Memory networks.  _International Conference on Learning Representations (ICLR)_.
  * Xing et al. (2018) Chen Xing, Yu Wu, Wei Wu, Yalou Huang, and Ming Zhou. 2018.  Hierarchical recurrent attention network for response generation.  _National Conference on Artificial Intelligence._
  * Xue and Yang (2013) Nianwen Xue and Yaqin Yang. 2013.  Dependency-based empty category detection via phrase structure trees.  pages 1051–1060.
  * Yang et al. (2015) Yaqin Yang, Yalin Liu, and Nianwen Xue. 2015.  Recovering dropped pronouns from chinese text messages.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing._ , volume 2, pages 309–313.
  * Yang et al. (2016) Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. 2016\.  Hierarchical attention networks for document classification.  In _Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies._ , pages 1480–1489.
  * Yin et al. (2017) Qingyu Yin, Yu Zhang, Weinan Zhang, and Ting Liu. 2017.  Chinese zero pronoun resolution with deep memory network.  In _Conference on Empirical Methods in Natural Language Processing._ , pages 1309–1318.
  * Yin et al. (2018) Qingyu Yin, Yu Zhang, Weinan Zhang, Ting Liu, and William Yang Wang. 2018.  Deep reinforcement learning for chinese zero pronoun resolution.  _meeting of the association for computational linguistics_ , pages 569–578.
  * Zhang et al. (2016) Weinan Zhang, Ting Liu, Qingyu Yin, and Yu Zhang. 2016.  Neural recovery machine for chinese dropped pronoun.  _arXiv: Computation and Language_.
  * Zhao and Ng (2007) Shanheng Zhao and Hwee Tou Ng. 2007.  Identification and resolution of chinese zero pronouns: A machine learning approach.  In _Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning._


Dataset Obfuscation: Its Applications to and Impacts on Edge Machine Learning

Guangsheng Yu

Data61, CSIRO

Xu Wang

FEIT, UTS

Ping Yu

Faculty of Computing, Harbin Institute of Technology

Caijun Sun
Caijun Sun acts as the corresponding author.

Zhejiang Lab

Wei Ni

Data61, CSIRO

Ren Ping Liu

FEIT, UTS

Obfuscating a dataset by adding random noises to protect the privacy of sensitive samples in the training dataset is crucial to prevent data leakage to untrusted parties for edge applications.
We conduct comprehensive experiments to investigate how the dataset obfuscation can affect the resultant model weights - in terms of the model accuracy, Frobenius-norm (F-norm)-based model distance, and level of data privacy - and discuss the potential applications with the proposed Privacy, Utility, and Distinguishability (PUD)-triangle diagram to visualize the requirement preferences. Our experiments are based on the popular MNIST and CIFAR-10 datasets under both independent and identically distributed (IID) and non-IID settings. Significant results include a trade-off between the model accuracy and privacy level and a trade-off between the model difference and privacy level. The results indicate broad application prospects for training outsourcing in edge computing and guarding against attacks in Federated Learning among edge devices.

<concept_desc>Computing methodologies Machine learning</concept_desc>
<concept_desc>Computing methodologies Artificial intelligence</concept_desc>
<concept_desc>Security and privacy Privacy-preserving protocols</concept_desc>

[500]Computing methodologies Machine learning
[500]Computing methodologies Artificial intelligence
[500]Security and privacy Privacy-preserving protocols

§ CONCLUSION

We conducted comprehensive experiments to investigate

how obfuscating a training dataset by adding random noises would affect the resultant model in terms of model prediction accuracy, model distance, data utility, data privacy, etc. Experimental results over both the MNIST and CIFAR-10 datasets revealed that, if a balanced point among all the considered metrics is satisfied, broad application prospects on real-world applications will become realistic, including training outsourcing on edge computing and guarding against attacks in FL among edge devices.