capbtabboxtable[][] 11institutetext: 1 Hanoi University of Science and
Technology 2 College of Engineering & Computer Science, VinUniversity3 VinUni-
Illinois Smart Health Center, VinUniversity* Corresponding author:
<EMAIL_ADDRESS>
# Image-based Contextual Pill Recognition with Medical Knowledge Graph
Assistance

Anh Duy Nguyen 11 Thuy Dung Nguyen 11 Huy Hieu Pham 2233
Thanh Hung Nguyen 11 Phi Le Nguyen 11**

###### Abstract

In many healthcare applications, identifying pills given their captured images
under various conditions and backgrounds has been becoming more and more
essential. Several efforts have been devoted to utilizing the deep learning-
based approach to tackle the pill recognition problem in the literature.
However, due to the high similarity between pills’ appearance, misrecognition
often occurs, leaving pill recognition a challenge. To this end, in this
paper, we introduce a novel approach named PIKA that leverages external
knowledge to enhance pill recognition accuracy. Specifically, we address a
practical scenario (which we call contextual pill recognition), aiming to
identify pills in a picture of a patient’s pill intake. Firstly, we propose a
novel method for modeling the implicit association between pills in the
presence of an external data source, in this case, prescriptions. Secondly, we
present a walk-based graph embedding model that transforms from the graph
space to vector space and extracts condensed relational features of the pills.
Thirdly, a final framework is provided that leverages both image-based visual
and graph-based relational features to accomplish the pill identification
task. Within this framework, the visual representation of each pill is mapped
to the graph embedding space, which is then used to execute _attention_ over
the graph representation, resulting in a semantically-rich context vector that
aids in the final classification. To our knowledge, this is the first study to
use external prescription data to establish associations between medicines and
to classify them using this aiding information. The architecture of PIKA is
lightweight and has the flexibility to incorporate into any recognition
backbones. The experimental results show that by leveraging the external
knowledge graph, PIKA can improve the recognition accuracy from $4.8\%$ to
$34.1\%$ in terms of F1-score, compared to baselines.

###### Keywords:

Pill Recognition Knowledge Graph Graph Embedding.

##  1 Introduction

Medicines are used to cure diseases and improve patients’ health. Medication
mistakes, however, may have serious consequences, including diminishing the
efficacy of the treatment, causing adverse effects, or even leading to death.
According to a WHO report, one-third of all mortality is caused by the misuse
of drugs, not by disease [2]. Moreover, according to Yaniv et al. [20],
medication errors claim the lives of about six to eight thousand people every
year. To emphasize the significance of taking medication correctly, WHO has
chosen the subject Medication Without Harm for World Patient Safety Day 2022
[1].

Medication errors may fall into many categories, one of which is incorrect
pill intake, which occurs when the drugs taken differ from the prescription.
This is due to the difficulty in manually distinguishing pills owing to the
wide variety of drugs and similarities in pill colors and shapes. In such a
context, many attempts have been made to assist users in identifying the pills
automatically. In recent years, machine learning (ML) has emerged as a viable
technique for tackling object classification problems. Many studies have
employed machine learning in the pill recognition challenge [19, 15, 3]. Some
common techniques such as convolutional neural networks (CNN) and Graph Neural
Networks (GNN) are often used. For instance, in [19], the authors exploited
Deep Convolution Network to identify pills. In [15], Enhanced Feature Pyramid
Networks (EFPNs) and Global Convolution Network (GCN) are combined to enhance
the pill localization accuracy. Besides, the authors leveraged the Xception
network [4] to solve the pill recognition problem. The authors in [3] studied
how to help visually impaired chronic patients in taking their medications
correctly. To this end, they proposed a so-called MedGlasses system, which
combines AI and IoT. MedGlasses comprises smart glasses capable of recognizing
pills, a smartphone app capable of reading medication information from a QR
code and reminding users to take the medication, and a server system to store
user information. Furthermore, numerous efforts have strived to improve pill
recognition accuracy by incorporating handcrafted features such as color,
shape, and imprint. Ling et al. [9] investigated the problem of few-shot pill
detection. The authors proposed a Multi-Stream (MS) deep learning model that
combines information from four streams: RGB, Texture, Contour, and Imprinted
Text. In addition, they offered a two-stage training technique to solve the
data scarcity constraint; the first stage is to train with all samples, while
the second concentrates only on the hard examples. In [12], the authors
integrated three handcrafted features, namely shape, color, and imprinted
text, to identify pills. Specifically, the authors first used statistical
measurements from the pill’s histogram to estimate the number of colors in the
pill. The imprinted text on the pill was then extracted using text recognition
tools. The author also used the decision tree technique to determine the pill
shape. The color, shape, and imprinted text information are then used as input
features to train the classification model.

Figure 1: Ill-predicted medicines

Despite numerous efforts, pill recognition remains problematic. Especially,
pill misidentification often occurs with tablets that look substantially
similar. Figure 1 shows some of the misclassification results made by a deep
learning model. To overcome the limitations of existing approaches, in this
study, we propose a novel method that leverages external knowledge to increase
the accuracy and, in particular, to tackle the misclassification of similar
pills. Unlike the existing works, we focus on a practical application that
recognizes pills in the patient’s pill intake picture. The external knowledge
we use is the information extracted from a given set of prescriptions. Our
main idea is that by using such external knowledge, we can learn the
relationship between the drugs, such as the co-occurrence likelihood of the
pills. This knowledge will be utilized to improve the pill recognition model’s
accuracy.

To summarize, our main contributions are as follows:

  * $\bullet$

We are the first to address a so-called _contextual pill recognition_ problem,
which recognizes pills in a picture of a patient’s pill intake.

  * $\bullet$

We build a dataset containing pill images taken in unconstraint conditions and
a corresponding prescription collection.

  * $\bullet$

We propose a novel deep learning-based approach to solve the contextual pill
recognition problem. Specifically, we design a method to construct a
prescription-based knowledge graph representing the relationship between
pills. We then present a graph embedding network to extract pills’ relational
features. Finally, we design a framework to fuse the graph-based relational
information with the image-based visual features to make the final
classification decision.

  * $\bullet$

We design loss functions and a training strategy to enhance the classification
accuracy.

  * $\bullet$

We conduct thorough experiments on a dataset of drugs taken in real-world
settings and compare the performance of the proposed solution to existing
methods. The experimental findings indicate that our proposed model
outperforms significantly the baselines.

The remainder of the paper is organized as follows. We introduce the related
works in Section 2. Section 3 describes our proposed solution. We evaluate the
effectiveness of the proposed approach in Section 4 and conclude the paper in
Section 5. Our code and pre-trained deep learning models will be made publicly
available on our project webpage (http://vaipe.io/) upon the publication of
this paper.

##  2 Related work

The contextual pill recognition can be treated as a traditional object
identification problem. The conventional approach is to divide it into two
stages. The first stage is responsible for segmenting each pill image, and the
second one treats each pill box as a separate object and identifies it using
an object recognition model. In [19], the authors employed Deep Convolution
Network, Feature Pyramid Networks (EFPNs), combined with GCN for pill
detection. They then used the Xception network to identify the pill. Ling et
al. [9] studied the issue of pill identification with a limited number of
samples. To improve identification accuracy, the author incorporated data from
numerous sources, including RGB, Texture, Contour, and Imprinted Text. Hand-
crafted features such as shape, color, and imprinted text were also used in
the [12]. The shortcoming of these approaches is that they handle each pill in
the picture separately, without taking use of the pill’s interaction.

Contextual pill identification is analogous to the multi-label classification
problem, which has drawn a lot of attention in recent years. Many research has
employed external information to improve recognition accuracy in this problem.
The most common strategy is to obtain the label co-occurrence relationship and
use it in the recognition task. Label co-occurrence may be retrieved using a
variety of approaches, including probabilistic models, neural networks, and
graph networks. Li et al. employed conditional graphical Lasso model in [8] to
statistically calculate the co-occurrence probability of the labels. Several
works have adopted neural networks such as LSTM to simulate the interaction of
labels to decrease the computation costs [16]. The author of [5] used the
autoencoder Graph Isomorphism Network (GIN) to represent the label
association. They also presented a collaborative training framework
incorporating label semantic encoding and label-specific feature extraction.
There are also several techniques to utilize relational information.
Relational information, in particular, may be combined with visual
characteristics in the final layers, as shown in [18]. It may also be injected
into the middle CNN layers through lateral connections, as described in [17].

Contextual pill identification, on the other hand, differs from traditional
multi-label classification in that the multi-label classification task tries
to recognize the global information offered by the picture rather than finding
and recognizing each item featured in the image. The second problem lies in
modeling the label’s relation. Indeed, traditional multi-label classification
systems mainly construct label relationships based on the semantic meaning of
the label’s name. This strategy, however, does not work with medicine names
since they often have no meaning. Furthermore, extracting correlations between
medicine names from public data sources is difficult.

##  3 Proposed Approach

In this section we propose a novel pill recognition framework named PIKA
(which stands for Pill Identification with medical Knowledge grAph). We first
present the main components of the PIKA framework (Section 3.1). We then
describe how the prescription-based medical knowledge graph is built (Section
3.2) and explain how pill visual features are extracted (Section 3.3). Next,
we combine the built medical knowledge graph and extracted visual features to
enhance pill identification performance (Section 3.4). Finally, we introduce
an auxiliary loss and a training strategy to improve the effectiveness of the
proposed learning model (Section 3.5).

###  3.1 Overview

Figure 2: Overview of the proposed framework. Firstly, the Input Processing
Procedure is used to generate a non-directed Medical Knowledge Graph (MKG)
$\mathcal{G=<V,E,W>}$ from given prescriptions, and crop the input images into
pill boxes. Secondly, the MKG is fed into a Graph embedding network to extract
pills’ relational features, while the cropped pill images are passed via a
backbone network to retrieve its visual representations. At this stage, the
graph-based relational features are combined with the pseudo-class scores
produced by the visual backbone to make up its condensed version. Thirdly, the
visual embedding get projected to the same hyper-plane as their counterparts
in the graph space, with the aid of the Projection Module. Following, the
projected visual features, coupled with graph-based relational information,
are the input for the Context Attention Module to provide the context vector.
Finally, the enriched visual features, which combine the context vector and
the visual features, are fed into the final classifier to identify the pill.

As illustrated in Figure 2, the proposed model comprises four major
components: input processing, visual processing, graph processing, and
information fusion. The first block, i.e., input processing, is in charge of
locating and retrieving pill images and creating a graph modeling drug
interactions. The visual processing block is used to extract visual features
of the pills, while the graph processing module attempts to depict the
relationship between the pills. The fusion layer then combines the visual
characteristics of the pills with their graph-based relational features to
generate the final classification decision. The overall flow is as follows.

  * $\bullet$

Step 1. The original image containing multiple pills is passed through an
object localization model to identify and cut out bounding-box images of every
pill. Note that we do not focus on the object detection problem in this work;
thus, we can use any object detection model for this step.

  * $\bullet$

Step 2. We construct a graph from a given set of prescriptions, with nodes
representing pills and edges reflecting drug linkages. We name this graph the
Prescription-based Medical Knowledge Graph or PMKG for short. The PMKG is then
passed through a Graph Neural Network (GNN) to yield embedding vectors. Each
embedding vector conveys information about a node and its relationship to the
neighbors. The detailed algorithm is presented in Section 3.2.

  * $\bullet$

Step 3. The pills’ images will then be put into the Visual processing module
to extract the visual characteristic. On the one hand, these features will be
fed into the data fusion block to make the classification decision. On the
other hand, these features are put in a projection module. The objective of
the projection module is to generate a representation similar to that of the
graph processing block. The projected features are then utilized to learn the
relationship between the pill images and the PMKG’s nodes. The detail of the
visual processing module will be described in Section 3.3.

  * $\bullet$

Step 4. The Graph embedding vector retrieved in Step 2 and the projected
features acquired in Step 3 will be passed through an attention layer to
generate a context vector. Finally, the context vector will be concatenated
with the Visual feature before being fed into the final classifier, which will
produce prediction results. The details of our losses functions are presented
in Section 3.5.

###  3.2 Prescription-based Medical Knowledge Graph

The key idea behind the proposed approach is to utilize the information on the
relationship between pills via their corresponding prescriptions to enhance
image-based pill recognition. To this end, a prescription-based medical
knowledge graph is constructed. Our intuition is that all the medicines are
prescribed to cure or alleviate some diseases or symptoms in actual pill
captures. Hence, we can formulate that implicit relation through the direct
relations between pills and diagnoses. This information contains in the
prescriptions provided by pharmacists to their patients. This section covers
our detailed methodology for knowledge graph modeling and our framework for
embedding this graph.

####  3.2.1 Knowledge Graph Modelling

The Medical Knowledge Graph (MKG) is a weighted graph, denoted as
$\mathcal{G=<V,E,W>}$, whose vertices $\mathcal{V}$ represent pill classes,
and the weights $\mathcal{W}$ indicate the relationship between the pills.
With prescriptions as the initial data, two factors can be used to formulate
graph edges $\mathcal{E}$, which are diagnoses and medications. As the
relationship between pills is not explicitly presented in prescriptions, we
model the relation representing the edge between two nodes (i.e., pill
classes) $C_{i}$ and $C_{j}$ based on the following criteria.

  * $\bullet$

There is an edge between two pill classes $C_{i}$ and $C_{j}$ if and only if
they have been prescribed for at least one shared diagnosis.

  * $\bullet$

The weight of an edge $E_{ij}$ connecting pill classes $C_{i}$ and $C_{j}$
reflects the likelihood that these two medications will be given at the same
time.

Instead of directly weighting the Pill-Pill edges, we determine the weights
via Diagnose-Pill relation. In particular, we first define a so-called
Diagnose-Pill impact factor, which reflects how important a pill is to a
diagnosis or, in other words, how often a pill is prescribed to cure a
diagnosis. Inspired by the Term Frequency (tf) — Inverse Dense Frequency (idf)
often used in NLP domain, we define the impact factor of a pill $P_{j}$ to a
diagnose $D_{i}$ (denoted as $I(P_{j},D_{i})$) as follows.

$\mathcal{I}(P_{j},D_{i})=\texttt{tf}(D_{j},P_{i})\times\texttt{idf}(P_{i})=\frac{|\mathbb{S}(D_{j},P_{i})|}{|\mathbb{S}(D_{j})|}\times\log\frac{|\mathbb{S}|}{|\mathbb{S}(P_{i})|},$
(1)

where $\mathbb{S}$ represents the set of all prescriptions,
$\mathbb{S}(D_{j},P_{i})$ depicts the collection of prescriptions containing
both $D_{j}$ and $P_{i}$, and $\mathbb{S}(D_{j})$ illustrates the set of
prescriptions containing $D_{j}$. After calculating the impact factors of the
pills and diagnoses, we derive the weights between two pills by averaging
their impact factors against all diagnoses, as shown below

$\mathcal{W}(P_{i},P_{j})=\sum_{D\in\mathbb{D}}\mathcal{I}(P_{i},D)+\mathcal{I}(P_{j},D),$
(2)

where $\mathcal{W}(P_{i},P_{j})$ depicts the weight between pills
$P_{i},P_{j}$, and $\mathbb{D}$ denotes the set of all diagnoses.

####  3.2.2 Knowledge Graph Embedding

As the MKG is sparse, we will not utilize it directly but pass it through a
graph embedding module to extract the condensed meaningful information.
Specifically, the graph embedding module helps project from the graph space
into a vector space. Each vector corresponds to a node (i.e., a pill class)
and conveys information about that node and its relationships with the
neighbors. With the graph embedding module, we want to preserve the co-
occurrence property of the pills, i.e., if two nodes $V_{i},V_{j}$ are
neighbors in the original MKG, their corresponding presentations $u_{i}$ and
$u_{j}$ should also have small distance in the vector space. To this end, we
leverage the walk-based approach, which will train a graph embedding network
using the skip-gram model with the following loss function

$\mathcal{L}_{g}=-\sum_{i=1}^{n}\left[\sum_{u_{j}\in\mathbb{N}(u_{i})}\sigma\left(u_{i}\cdot
u_{j}\right)-\sum_{u_{k}\notin\mathbb{N}(u_{i})}\log\left(e^{u_{k}\cdot
u_{i}}\right)\right],$ (3)

where $n$ denotes the total number of nodes in the graph, $u_{i}$ represents
the embedding vector of node ${V}_{i}$, and $\mathbb{N}(u_{i})$ depicts the
set of ${V}_{i}$’s 1-hop neighbors. By minimizing $\mathcal{L}_{g}$, we can
reduce the distance between representations of neighboring nodes while
increasing that of non-neighboring nodes.

###  3.3 Visual Processing Procedure

The Visual Processing block is responsible for retrieving two types of
information. The former refers to the visual characteristics of individual
pill images; meanwhile, the latter relates to the relational feature that
represents the interaction between pills. We employ a conventional
Convolutional neural networks such as VGG [14] or ResNet [6] to extract the
visual features. Concerning the relational features, our idea is to distill
knowledge from MKG into the representation of each pill using a projection
layer. Besides, the Visual Processing block also contains a pseudo classifier
module that helps to provide rough classification results. These results are
then used to filter out condensed information from MKG (the details will be
presented in Section 3.4).

####  3.3.1 V2G Projection Layer

The V2G projection layer obtains a pill’s visual feature vector as the input.
It passes through several layers to generate a representation with the same
dimension as the MKG’s node embedding vector. This layer can be mathematically
represented as $v^{V2G}_{i}=\theta(v_{i})$, where $v_{i}$ and $v^{V2G}_{i}$
are the representations in the visual and graph spaces, respectively; and
$\theta(\cdot):V\xrightarrow{}U$ is a non-linear mapping. In the
implementation, we formulate this mapping as a stack of Fully Connected (FC)
layers, with $tanh$ as the middle activation function. Through the training
processing, the $\theta(\cdot)$ will be optimized so that the probability
distribution of the projected vectors is similar to that of the MKG’s
embedding vectors. This is accomplished by introducing the Linkage loss as
described in Section 3.5.

####  3.3.2 Pseudo Classification Layer

The pseudo classifier produces temporary identification results. This rough
classification result will be used as a filter layer responsible for
extracting from the MKG only information related to the pills in the image
(and omitting information from the nodes that are not associated with the
pills in the picture). In our implementation, pseudo classification is
currently implemented as a fully connected layer.

###  3.4 Data Fusion

In the Data Fusion block, we first extract the condensed information from the
MKG and integrate it with the visual features using an attention mechanism to
create the context feature. The context feature are then concatenated with the
visual features before being fed into the final classification layer to make
the final decision.

####  3.4.1 Condensed Relational Feature Extraction

The idea of the Condensed Feature Extraction module is to extract from the MKG
only information related to the pills in the input image. Let $N$ be the
number of pill classes and $M$ be the number of pills in the input image.
Suppose $P={[p_{ij}]}_{M\times N}$ is the matrix whose row vectors represent
the logits produced by the pseudo classifier, and $U={[u_{kl}]}_{N\times H}$
denotes the embedding matrix, whose each row represents a pill class’
embedding vector. The condensed relational features, denoted as $\mathcal{R}$
is a set of $M$ vectors, each depicts the condensed relational information of
a pill (in the input image), extracted from the MKG. $\mathcal{R}$ is
calculated by multiplying the softmax of $P$ to $U$ as follows.

$\mathcal{R}=\sigma(P)\cdot U.$ (4)

Here the symbol $\sigma$ denotes the Softmax activation function. Intuitively,
$\mathcal{R}$ is a matrix consisting of $M$ rows. The $i$-th row of
$\mathcal{R}$ is a weighted sum of all the MKG’s node embeddings, whose
weights are the classification probabilities corresponding to the $i$-th pill
in the input image.

####  3.4.2 Attention Module

Figure 3: Illustration of the Context Attention Module

To avoid misclassification and improve the model’s accuracy, besides the pure
visual information extracted by the visual extractor described in Section 3.3,
we leverage the attention mechanism to create a context vector that integrates
both visual and relational features. The details of the attention module are
illustrated in Fig. 3. Specifically, we use the projected features (i.e.,
produced by the Visual Projection module) as the key and value, and the graph
embedding vectors as the query. The attention module first calculates the
attention weights as the similarity of each projected feature to all the graph
embedding vectors. The final context vector is then generated by taking the
weighted sum of the projected features. The context vector is then fused with
the visual features and passed to the final classifier.

###  3.5 Loss Functions

With additional modules for different purposes mentioned above, we also
provide auxiliary losses for aiding the optimization process of the modules.
This section is dedicated for presenting those losses.

####  3.5.1 Classification loss

Our first objective function is the classification loss, which is composed of
two terms. The first term’s functionality is to bring the final output of
PIKA’s Classifier close to the actual result. The following one deal with the
output of the Pseudo Classification layer. It is expected to produce the
result that is best closed to ground truth also. Since we are dealing with
multi-label problems, cross-entropy is used.

$\mathcal{L}_{c}=-\frac{1}{N}\sum_{i=1}^{N}y_{i}\cdot\log\left(\tilde{y}_{i}\right)-\beta_{\text{loose
}}*\frac{1}{N}\sum_{i=1}^{N}y_{i}\cdot\log\left(p_{i}\right),$ (5)

where $y_{i}$ denotes the one-hot vector - the ground truth of the $i$\- pill,
$\tilde{y}_{i}$ and $p_{i}$ represent the Classifier’s and the Pseudo
Classifier’s outputs, respectively. In the formula, there is an additional
parameter $\beta_{\text{loose }}$ ($0\leq\beta_{\text{loose }}\leq 1$), which
helps loosing the constraints for the Pseudo Classifier. The closer
$\beta_{\text{loose }}$ approaches 1, the more we expect that the output of
Pseudo Classifier is similar to the main one. In our case, it is set as $0.1$
for additional flexibility.

####  3.5.2 Linkage Loss

For the V2G projection layer, we propose an auxiliary loss called linkage
loss, helping this module achieve its aim, i.e., mapping from the visual space
$\mathcal{V}$ to the graph space $\mathcal{U}$. Let $\mathcal{V}^{V2G}$ be the
vector spaces produced by the Projection layer; then, our objective is to
bring $\mathcal{V}^{V2G}$ close to the graph space $\mathcal{U}$. To this end,
we design the linkage loss as a type of probabilistic distance instead of a
point-wise one. We believe it would loosen the constraint while also being
robust enough to help the module converge. Let the distributions of
$\mathcal{V}^{V2G}$ and $\mathcal{U}$ be modeled by two continuous random
variables $X$, and $G$ respectively. Firstly, we have to model the geometry of
the distributions. A common way to accomplish this purpose is to investigate
the pairwise interactions between sample points (with an ample number of data
samples) [7, 11] via the joint probability density of every two data samples.
Let $u_{ij}$ and $v_{ij}$ be the joint density probability functions of the
$i$-th and $j$-th data points of variable $X$ and $G$, respectively; then
$u_{ij}$ and $v_{ij}$ can be modeled using Kernel Density Estimation (KDE)
[13] as follows.

$u_{ij}=u_{i\mid
j}u_{j}=\frac{1}{N}K\left(\mathbf{g}_{i},\mathbf{g}_{j};2\sigma_{\mathcal{U}}^{2}\right);~{}~{}v^{V2G}_{ij}=v^{V2G}_{i\mid
j}v^{V2G}_{j}=\frac{1}{N}K\left(\mathbf{x}_{i},\mathbf{x}_{j};2\sigma_{\mathcal{V}^{V2G}}^{2}\right),$
(6)

in which $K\left(\cdot,\cdot;2\sigma^{2}\right)$ denotes a symmetric kernel
function with the width $\sigma$; $\mathbf{g}_{i},\mathbf{g}_{j}$ are two data
points sampled from the distribution of $G$, and
$\mathbf{x}_{i},\mathbf{x}_{j}$ are two data points sampled from the
distribution of $X$; $N$ is the number of samples. Ideally, we want to
minimize the divergence of the joint density probability functions of $U$ and
$V^{V2G}$. However, learning a projection module that can accomplish this
purpose is impossible. To alleviate this issue, we choose to replace the joint
probability density function with the conditional probability distribution of
the samples. Though the divergence of both two functions has the same
convergence point (in case the kernel similarities are the same for both
distributions), the use of conditional probability can better describe the
local regions between data points [11] (expresses the probability of each
sample to select each of its neighbors). The conditional probability
distributions for the graph and projected visual spaces are defined as
follows.

$u_{i\mid
j}=\frac{K\left(\mathbf{g}_{i},\mathbf{g}_{j};2\sigma_{\mathcal{U}}^{2}\right)}{\sum_{k=1,k\neq
j}^{N}K\left(\mathbf{g}_{k},\mathbf{g}_{j};2\sigma_{\mathcal{U}}^{2}\right)};~{}~{}v^{V2G}_{i\mid
j}=\frac{K\left(\mathbf{x}_{i},\mathbf{x}_{j};2\sigma_{V^{V2G}}^{2}\right)}{\sum_{k=1,k\neq
j}^{N}K\left(\mathbf{x}_{k},\mathbf{x}_{j};2\sigma_{V^{V2G}}^{2}\right)}.$ (7)

We use the Cosine Similarity as the kernel. Finally, the divergence metric we
chose as our linkage loss function is the Jensen-Shannon (JS) Divergence:

$\mathcal{L}_{l}=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1,i\neq j}^{N}\left[u_{j\mid
i}\log\left(\frac{u_{j\mid i}}{v^{V2G}_{j\mid i}}\right)+v^{V2G}_{j\mid
i}\log\left(\frac{v^{V2G}_{j\mid i}}{u_{j\mid i}}\right)\right].$ (8)

The total loss comprises of the Classification loss and Linkage loss as
follows:

$\mathcal{L}=\alpha\mathcal{L}_{c}+(1-\alpha)\mathcal{L}_{l},\text{with
}\alpha\in\left(0,1\right).$ (9)

##  4 Performance evaluation

In this section we evaluate the performance of our proposed model, PIKA. We
perform several experiments on our custom pill images captured with mobile
phones under unconstraint environments. Details about the dataset, together
with our evaluation metrics and implementation details, would be covered in
subsection 4.1.1. The numerical results are then presented in Section 4.2 and
4.3.

Figure 4: The visualization of several representative examples from our
customized pill dataset.

###  4.1 Experimental Setup

####  4.1.1 Dataset

To the best of our knowledge, the dataset of pill images and corresponding
prescription set are not publicly available. That is our motivation to build
our own dataset for this work. Table 1 describes some important statistics
about it. In addition, the collecting and processing procedure is combined by
the following steps.

Images |  Classes |  Prescriptions |  Train Set |  Test Set
---|---|---|---|---
3,087 |  76 |  168 |  | 116 prescriptions
---
2,058 images
| 52 prescriptions
---
1,029 images
Table 1: Dataset statistics

  * $\bullet$

We collect anonymous prescriptions of $168$ patients from 4 hospitals in
Vietnam. After processing the raw data, we converted them into JSON format for
each prescriptions record; the pills are also indexed to form a dictionary,
including $76$ kinds of drugs.

  * $\bullet$

Since the process of collecting pills in accordance with prescriptions takes a
great effort, time, and funding, in this current work, we have to collect
images of $76$ type of drugs which is not exactly the types in our collected
prescriptions.

  * $\bullet$

Following, the collected pills are relabeled by our pill dictionary described
above and grouped by prescriptions, with the number of images per prescription
being 5. Figure 4 illustrates the appearances of collected pills with their
mapped labels.

  * $\bullet$

Finally, we combine the retrieved sets of prescription photos into two sets,
one for the training process and one for evaluation.

####  4.1.2 Evaluation Metrics

For assessing PIKA performance across all used backbones, as well as other
testing scenarios, $Recall$, $Precision$ and $F1$-score metrics are adopted
altogether. The figures claimed in Section 4.2 and Section 4.3 are the
averaged numbers achieved over all classes.

####  4.1.3 Implementation Details

In our PIKA implementation, the dimensions of the graph embeddings are set as
$64$. The Projection Module consists of $3$ Fully Connected (FC) Layers, with
middle $tanh$ activation, and the output dimensions are $512$, $256$, $64$
respectively. The optimizer used is AdamW [10], and the initial learning rate
is $0.001$. $\beta_{loose}$ (Eq. 5) and $\alpha$ (Eq. 9) are set as $0.1$ and
$0.9$ respectively. During the training process, the input images is resized
to $224\times 224$, with random rotation of $10\degree$ and horizontal flip
for augmentation. The batch size is set as $32$. For the backbones we fuse our
framework with, all are kept the same as in the original papers ([6], [14]),
except the last classifier is adopted to output $76$ scores in compliant with
our $76$ classes. All the implementation is performed with the help of
_Pytorch_ framework, and the training, as well as evaluation processes, are
conducted with $2$ NVIDIA GeForce RTX 3090 GPUs.

We use a two-step training approach for PIKA. We first train the graph module
to convergence with its specified loss (Equation 3). The converged model
output is then utilized to train the rest of the PIKA framework. By doing so,
we ensure that the graph embeddings are reliable enough and truly reflect our
design intention of making them as references for projected visual vectors.

###  4.2 Comparison with baselines

In this section, we will demonstrate the flexibility of PIKA by incorporating
it with different backbones, including VGG and RESNET. We also investigate how
significantly our proposed approach can improve the recognition accuracy
compared to the baselines.

Backbone |  Precision |  Recall |  F1-score
---|---|---|---
VGG-16 [14] |  Baseline |  0.58967 |  0.47236 |  0.50121
PIKA (ours) |  0.6213 |  0.5264 |  0.5488
ResNet-18 [6] |  Baseline |  0.61020 |  0.49880 |  0.51570
PIKA (ours) |  0.9056 |  0.8389 |  0.8571
ResNet-34 [6] |  Baseline |  0.58200 |  0.49520 |  0.50870
PIKA (ours) |  0.8832 |  0.8173 |  0.8315
ResNet-50 [6] |  Baseline |  0.59612 |  0.51142 |  0.52146
PIKA (ours) |  0.8664 |  0.7909 |  0.8101
ResNet-101 [6] |  Baseline |  0.59120 |  0.50960 |  0.51620
PIKA (ours) |  0.8148 |  0.7482 |  0.7609
Table 2: PIKA performace over different backbones. The best results are
highlighted in bold.

The numerical results are presented in Table 2. As shown, PIKA, with all the
backbones, enhances the performance by a large gap. Quantitatively, PIKA
outperforms all compared SOTA significantly in terms of all metrics. Compared
to VGG-16, PIKA improves the Precision, Recall, and F1-score by $5.36\%$,
$11.44\%$, $9.49\%$, respectively. The performance gaps of PIKA to ResNet(s)
are even more significant. Concerning all the settings of ResNet(s), PIKA
improves the precision, recall, and F1-score by $45.83\%$, $58.67\%$,
$58.11\%$ on average, respectively. The most significant improvement can be
found at ResNet-18, where PIKA improves the Precision, Recall, and F1-score by
$48.41\%$, $68.18\%$, $66.20\%$, respectively.

###  4.3 Ablation Study

In this section, we first study the impacts of the Medical Knowledge Graph in
Section 4.3.1. We then examine the impact of removing modules from the PIKA
architecture on overall performance in Section 4.3.2 and 4.3.3.

####  4.3.1 Impacts of the Medical Knowledge Graph

Figure 5: F1-score of PIKA, given the Medical Knowledge Graph with different
levels of edge cutting

When working with a graph, we should ensure that all the information from it
is really beneficial for the model performance (containing no noise element).
Since we built the Knowledge Graph by information from the set of
prescriptions (Section 3.2), there are cases in which adding edges between
some pills cause potential conflicts. We observe that while most edges have
small weights, there are some with very large values. Those with small weights
suggest they are potential noise that might hurt overall performance. With
that in mind, we carry out an additional experiment for cutting edges and
employ the F1-score for evaluation, which is plotted in 5. We first exclude
$5\%$ of edges with the lowest weights and increase the exclusion ratios up to
$75\%$. The experiment results are shown in Figure 5. As can be observed, some
edges actually cause a negative impact on the overall result. The performance
reaches its peak when excluding around $20\%$ of edges with low weights and
starts degrading afterward.

####  4.3.2 Impacts of the Pseudo Classification Layer

Model |  Precision |  Recall |  F1-score
---|---|---|---
ResNet-50 [6] |  0.59612 |  0.51142 |  0.52146
PIKA |  0.86640 |  0.79090 |  0.81010
PIKA Without Pseudo Classifier |  0.67608 |  0.79778 |  0.69887
Table 3: PIKA performace with the Pseudo Classifier Removal

As declared in 3.3.2, The Pseudo Classifier layer assists in removing
redundant information from the MGK while retrieving condensed information
about the pills in the input images. For this experiment, we use ResNet-50 as
the backbone, and do training PIKA without Pseudo Classification Layer. The
result is compared with the full version as well as our backbone.
Specifically, employing the Pseudo Classifier improves the overall precision
and F1-score by roughly 28% and 16%. The details of the result is presented in
3.

####  4.3.3 Impacts of the Projection Module, and Context Attention Module

Following, we study the performance of PIKA’s when both Projection Moudule as
well as Context Attention Module are removed.

Model |  Precision |  Recall |  F1-score
---|---|---|---
ResNet-50 [6] |  0.59612 |  0.51142 |  0.52146
PIKA |  0.86640 |  0.79090 |  0.81010
PIKA w/o the Project and Attention Modules |  0.82750 |  0.74700 |  0.76630
Table 4: PIKA performace without Projection and Context Attention Modules.

Instead of generating context vector $c_{i}$ as the weighted sum of all
condensed graph embeddings $q_{i},i\in(0,\dots,n)$, we directly take the mean
over all $q_{i}$. For compliant with previous experiment, we also use
ResNet-50 as our backbone as well as our baseline. As shown in Table 4,
removing of the two modules leads to a degradation of 6% in the performance of
PIKA.

##  5 Conclusion and future work

In this study, we presented a novel approach to addressing challenges in
image-based pill recognition. Specifically, we investigated a practical
scenario aiming to identify pills from a patient’s intake picture. The
proposed method leverages additional information from prescriptions to improve
pill recognition from photos. We first presented a method to construct a
knowledge graph from prescriptions. We then designed a model to extract pills’
relational information from the graph, and a framework to combine both the
image-based visual and graph-based relational features for identifying pills.
Extensive experiments on our real-world pill image dataset showed that the
proposed framework outperforms the baselines by a significant margin, ranging
from $4.8\%$ to $34.1\%$ in terms of _F1_ -score. We also analyzed the effects
of the prescription-based medical knowledge graph on pill recognition
performance and discovered that the graph’s accuracy is critical in boosting
the overall system’s performance. We are actively developing this study by
gathering more pill and prescription datasets required to verify the suggested
technique and prove its usefulness in different clinical settings. We believe
that leveraging the external knowledge will improve the accuracy of pill
identification significantly.

## Acknowledgement

This work was funded by Vingroup Joint Stock Company (Vingroup JSC), Vingroup,
and supported by Vingroup Innovation Foundation (VINIF) under project code
VINIF.2021.DA00128.

## References

  * [1] World patient safety day 2022. https://www.who.int/news-room/events/detail/2022/09/17/default-calendar/world-patient-safety-day-2022, accessed: 2022-04-14
  * [2] Chang, et al.: A deep learning-based intelligent medicine recognition system for chronic patients. IEEE Access 7, 44441–44458 (2019). https://doi.org/10.1109/ACCESS.2019.2908843
  * [3] Chang, et al.: Medglasses: A wearable smart-glasses-based drug pill recognition system using deep learning for visually impaired chronic patients. IEEE Access 8, 17013–17024 (2020). https://doi.org/10.1109/ACCESS.2020.2967400
  * [4] Chollet, et al.: Xception: Deep learning with depthwise separable convolutions. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 1251–1258 (2017)
  * [5] Hang, J.Y., Zhang, M.L.: Collaborative learning of label semantics and deep label-specific features for multi-label classification. IEEE Transactions on Pattern Analysis and Machine Intelligence pp. 1–1 (2021). https://doi.org/10.1109/TPAMI.2021.3136592
  * [6] He, et al.: Deep residual learning for image recognition. In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 770–778 (2016). https://doi.org/10.1109/CVPR.2016.90
  * [7] Hinton, et al.: Stochastic neighbor embedding. In: Becker, S., Thrun, S., Obermayer, K. (eds.) Advances in Neural Information Processing Systems. vol. 15. MIT Press (2002), https://proceedings.neurips.cc/paper/2002/file/6150ccc6069bea6b5716254057a194ef-Paper.pdf
  * [8] Li, Q., Qiao, M., Bian, W., Tao, D.: Conditional graphical lasso for multi-label image classification. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2016)
  * [9] Ling, et al.: Few-shot pill recognition. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2020)
  * [10] Loshchilov, I., et al.: Decoupled weight decay regularization. In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net (2019), https://openreview.net/forum?id=Bkg6RiCqY7
  * [11] van der Maaten, L., et al.: Visualizing data using t-sne. Journal of Machine Learning Research 9(86), 2579–2605 (2008), http://jmlr.org/papers/v9/vandermaaten08a.html
  * [12] Proma, et al.: Medicine recognition from colors and text. In: Proceedings of the 2019 3rd International Conference on Graphics and Signal Processing. p. 39–43. ICGSP ’19, Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3338472.3338484, https://doi.org/10.1145/3338472.3338484
  * [13] Scott, et al.: Multivariate density estimation: Theory, practice, and visualization: Second edition (03 2015). https://doi.org/10.1002/9781118575574
  * [14] Simonyan, K., et al.: Very deep convolutional networks for large-scale image recognition. In: Bengio, Y., LeCun, Y. (eds.) 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings (2015), http://arxiv.org/abs/1409.1556
  * [15] Ting, H.W., et al.: A drug identification model developed using deep learning technologies: experience of a medical center in taiwan. BMC Health Services Research 20 (2020). https://doi.org/10.1186/s12913-020-05166-w, https://bmchealthservres.biomedcentral.com/articles/10.1186/s12913-020-05166-w#citeas
  * [16] Wang, J., Yang, Y., Mao, J., Huang, Z., Huang, C., Xu, W.: Cnn-rnn: A unified framework for multi-label image classification. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2016)
  * [17] Wang, Y., He, D., Li, F., Long, X., Zhou, Z., Ma, J., Wen, S.: Multi-label classification with label graph superimposing. Proceedings of the AAAI Conference on Artificial Intelligence 34(07), 12265–12272 (Apr 2020). https://doi.org/10.1609/aaai.v34i07.6909, https://ojs.aaai.org/index.php/AAAI/article/view/6909
  * [18] Wang, Y., Xie, Y., Liu, Y., Zhou, K., Li, X.: Fast graph convolution network based multi-label image recognition via cross-modal fusion. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management. p. 1575–1584. CIKM ’20, Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3340531.3411880, https://doi.org/10.1145/3340531.3411880
  * [19] Wong, Y.F., et al.: Development of fine-grained pill identification algorithm using deep convolutional network. Journal of Biomedical Informatics 74, 130–136 (2017). https://doi.org/https://doi.org/10.1016/j.jbi.2017.09.005, https://www.sciencedirect.com/science/article/pii/S1532046417302022
  * [20] Yaniv, et al.: The national library of medicine pill image recognition challenge: An initial report. In: 2016 IEEE Applied Imagery Pattern Recognition Workshop (AIPR). pp. 1–9 (2016). https://doi.org/10.1109/AIPR.2016.8010584


# Gradient Descent over Metagrammars for Syntax-Guided Synthesis

Nicolas Chan<EMAIL_ADDRESS>UC Berkeley ,  Elizabeth Polgreen
<EMAIL_ADDRESS>UC Berkeley and  Sanjit A. Seshia<EMAIL_ADDRESS>UC Berkeley

(2020)

###### Abstract.

Syntax-guided synthesis restricts the search space for program synthesis
through the use of a grammar imposing a syntactic restriction. In practice,
provision of such a grammar is often left to the user to do manually, though
in the absence of such a grammar, state-of-the-art solvers will provide their
own default grammar, which is dependent on the signature of the target program
to be sythesized. In this work, we speculate this default grammar could be
improved upon substantially. We build sets of rules, or metagrammars, for
constructing grammars, and perform a gradient descent over these metagrammars
aiming to find a metagrammar which solves more benchmarks and on average
faster. We show the resulting metagrammar enables CVC4 to solve $26$% more
benchmarks than the default grammar within a $300$s time-out, and that
metagrammars learnt from tens of benchmarks generalize to performance on 100s
of benchmarks.

††copyright: rightsretained††journalyear: 2020††journal:
PACMPL††journalvolume: 1††journalnumber: SYNT††article: 2††publicationmonth:
7††conference: SYNT ’20: 9th Workshop on Synthesis; July 19, 2020; Los
Angeles, CA, USA

##  1\. Introduction

A major theme in the advances in program synthesis over the past 15 years has
been the use of syntactic restrictions on the space of programs being
searched. One prominent approach is that of Syntax-Guided Synthesis
(DBLP:series/natosec/AlurBDF0JKMMRSSSSTU15, ), which augments the program
synthesis problem with a syntactic template or grammar from which the program
is to be constructed. This template can be used to guide the synthesis
algorithm and to reduce the search space of possible solutions.

Provision of this grammar, however, typically requires a skilled domain
expert. If the grammar is too small, it may not be expressive enough to
contain a solution to the synthesis task, or any solution might be intractably
large. For instance, constant literals may need to be constructed as the sum
of smaller constant literals e.g., $1^{\prime}s$. If the grammar is large, the
space of potential solutions is large and so the run-time of the synthesis
algorithm will be longer. Furthermore, a grammar may contain some operators
that are more expensive for a synthesis algorithm to reason about than others.
Consequently, choosing a good grammar is a key part in the success of SyGuS.

The best particular grammar for a synthesis problem will depend on the
function to be synthesized, for example, it will depend on the number and type
of arguments of the function, the return type of the function, or any number
of other particularities about the synthesis problem. So to construct a good
grammar in general, we need a set of rules that output a good particular
grammar for a particular synthesis problem.

In this work, we call this set of rules a metagrammar. The metagrammar may
include rules such as adding the function arguments to the grammar, adding
various functions (such as bvadd, bvor, etc. for bitvector problems), or
adding helper functions and constants present in the constraints or other
parts of the problem statement.

We design a scoring system to reward metagrammars solving benchmarks quickly
and penalize those failing to solve benchmarks, and use a simple gradient
descent over these metagrammars. We evaluate the resulting metagrammar on a
set of bitvector benchmarks from the SyGuS competition, using CVC4
(DBLP:journals/corr/abs-1806-08775, ) as the SyGuS solver, and find
metagrammars learnt from a randomly selected training set of tens of
benchmarks, are able to solve $26$% more benchmarks than the default grammar
on the remaining benchmarks within a 300$s$ time-out.

###  1.1. Related work

The balance between expressivity of a grammar and the speed of synthesis is
discussed by Gulwani in the context of data-wrangling
(DBLP:series/natosec/Gulwani16, ), and further by Padhi et al, who hypothesise
that the performance of SyGuS tools degrades as the expressivity of the
grammar increases, and propose a solution based on interleaving multiple
grammars (DBLP:conf/cav/PadhiMN019, ). Morton et al.
(DBLP:journals/corr/abs-2002-02884, ) use machine learning to filter the
grammars used by SyGuS. This work assumes a grammar is given, and optimizes
that grammar, whereas we assume no grammar is provided and improve upon the
default grammar. A key difference is that Morton et al. use a neural network
to perform the filtering and so need a large amount of training data. The
authors test their techniques on programming-by-example benchmarks (benchmarks
where the specification is a set of input-output examples which the desired
program satisfies), where automatically generating new benchmarks is
straightforward. A key benefit of our approach is that it requires very small
amounts of training data, which is difficult to obtain for program synthesis
for logical specifications (where the desired program must satisfy a set of
logical constraints). It is not straight forward to convert a logical
specification into a programming-by-example specification
(DBLP:journals/corr/abs-2001-09245, ; DBLP:journals/corr/abs-1710-01291, ).
Machine learning based program synthesis techniques
(DBLP:journals/corr/abs-1805-04276, ; DBLP:conf/icml/DevlinUBSMK17, ), which
often do look at identifying important pieces of a grammar
(DBLP:conf/iclr/BalogGBNT17, ; DBLP:conf/iclr/KalyanMPBJG18, ), are usually
applied to PBE problems, in part due to this challenge. A key advantage of our
simple gradient descent based technique is that we do not need large amounts
of training data in order to achieve performance gains.

Research into techniques used for selecting grammars for SyGuS and research
into techniques used for enumerating through the grammars
(DBLP:conf/cav/ReynoldsBNBT19, ; DBLP:conf/tacas/AlurRU17, ) tackle similar
problems, and good enumeration strategy should mitigate the effects of a
grammar specifying a large search space. An interesting example is EUPHONY
(DBLP:conf/pldi/LeeHAN18, ), which uses learns a probabilistic model at run
time that biases the enumeration. However, there are advantages to having an
algorithm for selecting grammars as well as an effective enumeration
algorithm. It provides flexibility as the algorithm can be treated as a bolt-
on for any SyGuS solver. It is also likely that the best metagrammar will be
be dependent on the set of benchmarks you wish to solve. We can evision a
scenario where a user has bodies of synthesis problems from different specific
applications and uses our technique to generate a metagrammar for use with
each specific benchmark set. Our framework could also allow a user to specify
rules as part of the metagrammar which extract features the user knows to be
important from the benchmark.

##  2\. Background

###  2.1. Syntax-Guided Synthesis

A Syntax-Guided Synthesis (DBLP:series/natosec/AlurBDF0JKMMRSSSSTU15, )
(SyGuS) problem consists of two constraints, a semantic constraint given as a
formula $\phi$, and a context-free grammar, often referred to as the syntactic
template. The computational problem is then to find a function $f$, built from
the context-free grammar, such that

$\forall x\,\,\phi(f,x)$

is valid, where $x$ is the set of all possible inputs to $f$.

###  2.2. Metagrammars

A metagrammar is a set of rules which determine what to add to the grammar for
a particular synthesis problem. A rule is a mapping from a particular
synthesis specification $\phi$ to a set of terminal symbols $S$, where the
specification includes the signature for the function $f$ to be synthesized.
For example, a rule specifying that the arguments of the function are included
in the grammar would inspect $\phi$, extract the function arguments, and then
output $S$ consisting of the arguments as terminals. Then each terminal in $S$
can be included in the definition of the appropriate non-terminal to construct
the final grammar for the particular synthesis problem (in union with the
other rules).

##  3\. Methodology

###  3.1. Building Metagrammars

We begin by identifyinga default grammar which includes a non-terminal for
each data type in the function signature plus booleans and the following rules
for populating these non-terminals:

  * •

Add argument variables of the same data type

  * •

Add constants $1$ and $0$ for each data type

  * •

Add functions (operators) for each data type

  * •

Add predicates for each relevant data type to the Bool type (for use in the
condition of if-then-else)

We identify a set of rules for producing the default grammar, where each rule
adds a set of constants and/or operators to the grammar. This set of rules
forms the default metagrammar which we can use to generate a grammar for a
given synthesis problem. We use this basic set of rules to evaluate our
framework but more complex rules could be explored in future work. We could,
for instance, introduce rules which extend the grammar, for example rules
which add constants and helper functions found in the synthesis specification
file.

|  | Default metagrammar | Reduced metagrammar | Enhanced metagrammar
---|---|---|---|---
Set | total | solved | avg. time | solved | unique | avg. time | solved | unique | avg. time
Non-SI bitvector | 421 | 276 | 18.1$s$ | 271 | 12 | 13.3$s$ | 282 | 21 | 12.5$s$
Non-SI (orig LIA) | 429 | 165 | 14.9$s$ | 181 | 19 | 13.6$s$ | 165 | 0 | 15.8$s$
PBE bitvector | 705 | 244 | 33.3$s$ | 379 | 146 | 40.8$s$ | 556 | 331 | 1.0$s$
Total | 1555 | 685 | 22.7$s$ | 831 | 177 | 25.9$s$ | 1003 | 352 | 6.6$s$
Table 1. The number of benchmarks solved and average solving time in seconds
for the default, reduced and enhanced metagrammars. The unique columns show
the number of benchmarks solved, that were not solved by the default grammar.
We discount the performance of the enhanced metagrammar on the PBE benchmarks
because adding in constant literals to a grammar allows the solver to produce
large look-up tables as solution.

###  3.2. Metagrammar Search

We score each metagrammar according to its performance on a set of training
benchmarks. Where the benchmarks are easily divisible into representative
categories, for instance invariant generation, we stratify the training data
across these sets in order to attempt to obtain representative training data.
Based on these scores we perform a search by expanding the neighbors of the
best performing metagrammar.

As described, a metagrammar $M$ is a set of rules
$M=\\{r_{1},r_{2},\dots,r_{n}\\}$. A smaller neighbor of $M$ is a metagrammar
$N_{i}$ which is missing one of the rules. That is, the set of smaller
neighbors of $M$ is $\\{N_{i}=M\setminus\\{r_{i}\\}:i=1,2,\dots,n\\}$.

The search begins with the neighbors of the default metagrammar. Then the
neighbors of the best neighbor are expanded, and so on, until we have
exhausted all of the rules.

####  3.2.1. Scoring

We designed a scoring function that aims to reward metagrammars solving a
benchmark significantly faster than neighbor metagrammars, and heavily
penalize metagrammars failing to solve a benchmark. We base this on the
normalized runtime against the neighbors. The score $S_{B}$ for a particular
metagrammar $M$ on a benchmark $B$, in the context of the results of the $n$
neighboring metagrammars, for a single benchmark is determined by the
difference of $M$’s runtime against the average of its neighbors normalized by
the standard deviation:

$S_{B}=\begin{cases}10&\text{benchmark unsolved,}\\\
\frac{r_{M}-\frac{1}{n}\sum_{0\leq j\leq n}r_{N_{j}}}{\sigma}&\text{benchmark
solved}\end{cases}$

where $r$ is the runtime of the metagrammar in seconds and $\sigma$ is the
standard deviation of the runtime of all the metagrammars on that benchmark. A
lower score is better. The specific scoring system is a heuristic and may be
improved upon or tailored for specific use cases, for instance one could
incorporate a metric that rewards finding shorter solutions, or finding
solutions that contain certain operators.

##  4\. Evaluation

We use CVC4 1.7 (84da9c0b) with the \--cegqi-si=none option, and remove single
invocation benchmarks from our benchmark set since these do not benefit from a
grammar being provided. We use a 300 second timeout, with 20 benchmarks
running in parallel on each Intel Xeon E5-2670 v2 CPU. We use a set of $1699$
bitvector benchmarks taken from the SyGuS competition (sygus-comp, ), grouped
into $3$ sets, shown in Table 1: non single-invocation (non-SI) bitvector
benchmarks; programming-by-example (PBE) bitvector benchmarks; and non-SI
Linear Integer Arithmetic benchmarks that we translate into bitvectors (this
includes invariant generation benchmarks).

We extract the default grammar used by CVC4111 Obtained from CVC4 version 1.7
using the \--trace=sygus-grammar-def option. and identify a default
metagrammar capable of producing this grammar. We run the gradient descent
process starting with the default metagrammar. We train on a stratified sample
of benchmarks, taking 48 from each of the 3 sets shown in Table 1. We stratify
the training data across these 3 sets in order to attempt to obtain
representative training data. These categories are very broad though and
better results may be obtained by categorising the benchmarks into more
precise categories, or by training a metagrammar for each set, We obtain a
metagrammar which we call the reduced metagrammar, and which produces the
following grammar for a function with bitvector arguments A1 and A2:

⬇

BV ::= A1|A2|1|(ite Bool BV BV)|(bvnot BV BV)|

(bvor BV BV)|(+ BV BV)|(bvlshr BV BV)|

(bvshl BV BV)

predicate ::= (= BV BV)|(bvult BV BV)

Bool ::= true|(not Bool)|(and Bool Bool)|

(or Bool Bool)|predicate

We also take the default metagrammar and manually add a rule adding constant
literals found in the benchmark, and we call the resulting metagrammar the
enhanced metagrammar.

We evaluate all metagrammars over the remaining set of $1555$ benchmarks. The
reduced metagrammar solved $177$ benchmarks that the default did not solve,
while failing to solve 31 benchmarks the default metagrammar did solve. It is
$22$% faster on the first two categories of benchmarks, but slower on the PBE
category. The enhanced metagrammar solves $21$ benchmarks that the default did
not solve, taken from the bitvector category, but does is on average slower
and solves no new benchmarks in the category of benchmarks translated from LIA
(which includes all benchmarks from the invariant synthesis category). We
hypothesize that this is because, whilst adding constant literals to a grammar
is helpful, it is not sufficient to do so without also reducing the size of
the grammar when the benchmarks are more complex. This suggests it would be
beneficial to explore using gradient descent over the space of metagrammars
that include rules that extend beyond the default metagrammar, with the aim of
combining the success of the reduced and enhanced metagrammars. We discount
the results for the enhanced metagrammar on the PBE category since adding in
constants makes it possible for the solver to effectively produce lookup table
solutions to these benchmarks. The differences in results across the
categories suggest it would be worth further exploring stratified sampling for
training sets, learning metagrammars based on training sets taken solely from
the category that the metagrammar is going to be tested on, or metagrammars
containing rules that attempt to classify benchmarks into such categories.

It is worth noting that in some cases the learnt metagrammar results in faster
solving but potentially longer solutions. This would not necessarily be a
desirable outcome, but it this behaviour is expected given that our scoring
function only rewards speed of solving and number of benchmarks solved. A
scoring function that places some weighting on “quality” of solutions would be
interesting to explore in future work. It is also worth noting that a
different training set will result in a different metagrammar; we report
results from a randomly selected training set. A fuller evaluation is in order
to determine the optimum size of the training set in order to consistently
produce these improvements, but we note that we trained two further
metagrammars which both improved over the default (solving 744 benchmarks in
an average of $22.0$s, and solving 814 benchmarks in an average of $27.7$s,
with significant improvements in the Non-SI bitvector and Non-SI LIA
translated categories respectively).

##  5\. Conclusions

We have presented a framework that uses a gradient descent based search to
find a metagrammar that improves solver performance over a set of SyGuS
benchmarks. We have evaluated one specific instance of this framework, using
bitvector benchmarks and the specific set of metagrammar rules and the scoring
function described in this paper. Despite its simplicity, and the minimal
amount of training data benchmarks required, we found this instantiation of
our method solved $25\%$ more benchmarks than the default metagrammar within
the timeout. In future work we plan to explore more advanced gradient descent
algorithms, as well as incorporating more advanced rules in the metagrammars
and exploring the relationships between metagrammars and different enumerative
synthesis algorithms. We believe that techniques like this could have
significant impact in application domains for synthesis such as synthesising
invariants for a specific type of software, where benchmarks are available but
not in the abundance required for neural network based techniques.

##### Acknowledgements

This work was supported in part by NSF grants 1739816 and 1837132, a gift from
Intel under the SCAP program, and the iCyPhy center.

## References

  * (1) Rajeev Alur, Rastislav Bodík, Eric Dallal, Dana Fisman, Pranav Garg, Garvit Juniwal, Hadas Kress-Gazit, P. Madhusudan, Milo M. K. Martin, Mukund Raghothaman, Shambwaditya Saha, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa.  Syntax-guided synthesis.  In Dependable Software Systems Engineering, volume 40 of NATO Science for Peace and Security Series, D: Information and Communication Security, pages 1–25. IOS Press, 2015.
  * (2) Rajeev Alur, Dana Fisman, Rishabh Singh, and Abhishek Udupa.  Syntax guided synthesis competition.  http://sygus.seas.upenn.edu/SyGuS-COMP2017.html, 2017.
  * (3) Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa.  Scaling enumerative program synthesis via divide and conquer.  In TACAS (1), volume 10205 of Lecture Notes in Computer Science, pages 319–336, 2017.
  * (4) Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow.  Deepcoder: Learning to write programs.  In ICLR (Poster). OpenReview.net, 2017.
  * (5) Clark W. Barrett, Haniel Barbosa, Martin Brain, Duligur Ibeling, Tim King, Paul Meng, Aina Niemetz, Andres Nötzli, Mathias Preiner, Andrew Reynolds, and Cesare Tinelli.  CVC4 at the SMT competition 2018.  CoRR, abs/1806.08775, 2018.
  * (6) Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli.  Leveraging grammar and reinforcement learning for neural program synthesis.  2018\.
  * (7) Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli.  Robustfill: Neural program learning under noisy I/O.  In ICML, volume 70 of Proceedings of Machine Learning Research, pages 990–998. PMLR, 2017.
  * (8) Sumit Gulwani.  Programming by examples - and its applications in data wrangling.  In Dependable Software Systems Engineering, volume 45 of NATO Science for Peace and Security Series - D: Information and Communication Security, pages 137–158. IOS Press, 2016.
  * (9) Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani.  Neural-guided deductive search for real-time program synthesis from examples.  In ICLR (Poster). OpenReview.net, 2018.
  * (10) Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik.  Accelerating search-based program synthesis using learned probabilistic models.  In PLDI, pages 436–449. ACM, 2018.
  * (11) Kairo Morton, William T. Hallahan, Elven Shum, Ruzica Piskac, and Mark Santolucito.  Grammar filtering for syntax-guided synthesis.  pages 1611–1618, 2020.
  * (12) Saswat Padhi, Todd D. Millstein, Aditya V. Nori, and Rahul Sharma.  Overfitting in synthesis: Theory and practice.  In CAV (1), volume 11561 of Lecture Notes in Computer Science, pages 315–334. Springer, 2019.
  * (13) Hila Peleg, Sharon Shoham, and Eran Yahav.  Programming not only by example.  pages 1114–1124, 2018.
  * (14) Elizabeth Polgreen, Ralph Abboud, and Daniel Kroening.  Counterexample guided neural synthesis.  CoRR, abs/2001.09245, 2020.
  * (15) Andrew Reynolds, Haniel Barbosa, Andres Nötzli, Clark W. Barrett, and Cesare Tinelli.  cvc4sy: Smart and fast term enumeration for syntax-guided synthesis.  In CAV (2), volume 11562 of Lecture Notes in Computer Science, pages 74–83. Springer, 2019.