# Weakly Supervised Recovery of Semantic Attributes

Ameen Ali
School of Computer Science
Tel Aviv University
Tel Aviv, Israel
<EMAIL_ADDRESS>
&Tomer Galanti
School of Computer Science
Tel Aviv University
Tel Aviv, Israel
<EMAIL_ADDRESS>
Evgenii Zheltonozhskii
Department of Computer Science
Technion
Haifa, Israel
<EMAIL_ADDRESS>
&Chaim Baskin
Department of Computer Science
Technion
Haifa, Israel
<EMAIL_ADDRESS>
&Lior Wolf
School of Computer Science
Tel Aviv University
Tel Aviv, Israel
<EMAIL_ADDRESS>

###### Abstract

We consider the problem of the extraction of semantic attributes, supervised
only with classification labels. For example, when learning to classify images
of birds into species, we would like to observe the emergence of features that
zoologists use to classify birds. To tackle this problem, we propose training
a neural network with discrete features in the last layer, which is followed
by two heads: a multi-layered perceptron (MLP) and a decision tree. Since
decision trees utilize simple binary decision stumps we expect those discrete
features to obtain semantic meaning. We present a theoretical analysis as well
as a practical method for learning in the intersection of two hypothesis
classes. Our results on multiple benchmarks show an improved ability to
extract a set of features that are highly correlated with the set of unseen
attributes.

##  1 Introduction

The extraction of meaningful intermediate features in classification problems
is at the heart of many scientific domains. Such features allow experts to
discuss a certain classification outcome and help understand the underlying
structure of the problem. For example, in botany, the species are often
identified based on dichotomous keys related to the shape of the leaf, the
texture of the fruit, etc. [54]. In paleography, the manuscript is dated or
attributed to a specific scribe, based, for example, on specific
characteristics of the morphology of the letters [69].

The attributes we discuss are binary and need to be both evidence-based and
distinctive. The first property means that there is a mapping $f$, such that,
every input $x$ is mapped to a vector $f(x)$ of binary values, indicating the
presence of each attribute. The second property means that there should be
simple rules that determine the class label $y(x)$ based on the obtained
attributes $f(x)$.

Currently, deep neural networks (DNNs) are the most successful methodology for
obtaining attributes from images [87, 80] and for classification. However, the
interpretation of the DNN is a very challenging problem. In contrast, decision
trees with binary decision stumps provide simple and interpretable decision
rules based on attributes [26]. We propose to merge two approaches by training
DNN to produce quantized representations which are suitable for classification
both by an MLP and by a decision tree.

To perform this hybrid learning task, we provide a theoretical analysis of the
problem of learning at the intersection of two hypothesis classes. We study
the optimization dynamics of training two hypotheses from two different
classes of functions. The first one is trained to minimize its distance from
the second one, and the second one is trained to minimize its distance from
the first one and the target function. We call this process Intersection
Regularization, as it regularizes the second hypothesis to be close to the
first hypothesis class. We theoretically discuss the conditions on the loss
surface, for which this process converges to an equilibrium point or local
minima.

The method that we develop for concurrently training a network and a tree is
based on the proposed analysis. We learn a quantized representation of the
data and two classifiers on top of this representation: a decision tree and
MLP. The two classifiers are trained using intersection regularization. Since
the human-defined attributes are usually sparse, we also apply $L_{1}$
regularization on the quantized vector of activations.

In an extensive set of experiments, we demonstrate that discrete
representations along with decision stumps learned with the proposed method
are highly correlated with a set of unseen human-defined attributes. At the
same time, the overall classification accuracy is only slightly reduced
compared to standard cross-entropy training.

The central contributions in this paper are as follows: (i) We identify a
novel learning problem that we call Weakly Unsupervised Recovery of Semantic
Attributes. In this setting, the samples are associated with abstract binary
attributes and are labeled by class membership. The algorithm is provided with
labeled samples and is judged by the ability to recover the binary attributes
without any access to them. We provide concrete measures for testing the
success of a given method for this task. (ii) We introduce a method for
recovering the semantic attributes. This method is based on a novel
regularization process for regularizing a neural network using a decision
tree. We call this regularization method, ‘Intersection Regularization’, and
(iii) We theoretically study the convergence guarantees of the new
regularization method to equilibrium points and local minima.

##  2 Related Work

We list various approaches for learning explainable models in the literature
and discuss their similarities and dissimilarities with our approach.

Interpretability  Developing tools and techniques to better interpret existing
deep learning based approaches and to that end building explainable machine
learning algorithms, is a fast-growing field of research. In computer vision,
most contributions are concerned with providing an output relevance map. These
methods include saliency-based methods [65, 85, 46, 89, 12, 90, 27],
Activation Maximization [16] and Excitation Backprop [86], perturbation-based
methods [20, 21]. Shapley-value-based methods [45] enjoy theoretical
justification and the Deep Taylor Decomposition [50] provides a derivation
that is also applicable to Layer-wise Relevance Propagation (LRP) [4] and its
variants [25, 35, 51] presented RAP. Gradient based methods are based on the
gradient with respect to the layer’s input feature map and include
Gradient*Input [63], Integrated Gradients [70], SmoothGrad [66], FullGrad [68]
and Grad-CAM [60].

Methods that provide an output relevance map suffer from several notable
disadvantages. First, many of these methods were shown to suffer from a bias
toward image edges and fail sanity checks that link their outcome to the
classifier [3]. Furthermore, even though these methods are useful for
visualization and downstream tasks, such as weakly supervised segmentation
[42], it is not obvious how to translate the image maps produced by these
methods into semantic attributes, i.e., extract meaning from a visual
depiction. An additional disadvantage of this approach is that it does not
provide a direct method for evaluating whether a given neural network is
interpretable or not and the evaluation is often done with related tasks, such
as segmentation or on measuring the classifier’s sensitivity to regions or
pixels that were deemed as being important to the classification outcome or
not. In our framework, we suggest objective measures in which one can quantify
the degree of interpretability of a given model.

Since linear models are intuitively considered interpretable, a framework in
which the learned features are monotonic and additive has been developed [1].
The explanation takes the form of presenting each attribute’s contribution
while explaining the attributes using prototype samples. Unlike our framework,
no attempt was made to validate that the obtained attributes correspond to a
predefined list of semantic attributes.

Local interpretability models, such as LIME [56], approximate the decision
surface for each specific decision by a linear model and are not aimed at
extracting meaningful attributes as in our method. Besides, such models are
known to be sensitive to small perturbations of the input [2, 83].

Fine-Grained Classification  Fine-grained classification aims at
differentiating subordinate classes of a common superior class. Those
subordinate classes are usually defined by domain experts, based on
complicated rules, which typically focus on subtle differences in particular
regions. Because of the inherent difficulty in classifying slightly different
classes, many contributions in this area often aim at detecting informative
regions in the input images that aid in classifying them [15, 82, 11, 31, 32,
93]. In our work, we would like to recover semantic attributes that are not
necessarily associated with specific image regions, e.g., mammal/reptile,
omnivore/carnivore.

Disentanglement A disentangled representation [8, 53, 59, 39, 74] is a
representation which contains multiple independent parts. Various methods,
such as [49, 19, 73, 10] have been able to effectively learn disentangled
representations from data. This setting is different than ours in two ways.
First, the attributes that we would like to recover are not independent.
Second, in disentanglement, we are typically interested in recovering any set
of features that represent the data in a disentangled manner. In our case, the
success is measured vs. a specific set of attributes.

Attributes Recovery Attributes recovery has been an active research direction
in computer vision. Attributes are typically referred as human-interpretable
features that can describe the input image or the class it belongs to. In [28]
they cast the problem of attributes recovery as a supervised learning task. In
[84, 40, 17, 58] they focus on category-level attributes, in which one would
like to learn a set of attributes that describe the classes of the different
images in the dataset. In several cases and especially in fine-grained
classification, predicting the class of an image is a more nuanced process,
where the values of attributes may vary between images in the same category.
In our paper, we focus on recovering instance-level attributes.

Explainability of Decision Trees Decision trees are known to be naturally
explainable models, as long as the decision rules are easy to interpret.
However, as far as we know, it was not shown before that learning trees, while
optimizing the features leads to the emergence of attributes of a large set of
relevant attributes.

In the context of recommendation systems interpretability, meta-trees were
used for providing per-user decision rules [64]. This method relies on a pre-
existing set of features rather than extracting them from the input. Another
line of work [22], which also employs preexisting features, distills the
information in a deep network into a soft decision tree [34]. Unlike our work,
the neural network is not optimized to produce suitable features.

More relevant to our work is the Adaptive Neural Trees method [71], which also
combines decision trees and neural networks. In this method, trees of dynamic
architectures that include network layers are grown so that the underlying
network features gradually evolve. It is shown that the learned tree divides
the classes along meaningful axes but the emergence of semantic attributes was
not shown.

Quantization  Quantization is the conversion of the floating-point data to
low-bit discrete representation. The most common approaches for training a
quantized neural network employ two sets of weights [33, 91]. The forward pass
is performed with quantized weights, and updates are performed on full
precision ones, i.e., approximating gradients with the straight-through
estimator (STE) [9]. In this work, we make use of quantizations in order to
learn discrete, interpretable representations of the data within a neural
network.

Figure 1: An illustration of our method. The model has three main components:
(a) a quantized representation function $F_{q}$, (b) a classifier neural
network $G$ and (c) a multivariate decision tree $T$. We have three losses: a
$L_{1}$ regularization over the masked quantized features, a cross entropy
loss between the network and the ground-truth labels and a soft cross entropy
loss between the outputs of the tree and the network.

##  3 Problem Setup

In this section, we formulate a new learning setting that we call Weakly
Unsupervised Recovery of Semantic Attributes. In this setting, there is an
unknown target function $y:\mathcal{X}\to\mathcal{Y}$ along with an attributes
function $f:\mathcal{X}\to\mathcal{U}^{d}$ that we would like to learn. Here,
$\mathcal{X}\subset\mathbb{R}^{n}$ is a set of instances and $\mathcal{Y}$ is
a set of labels. The function $f$ is assumed to be $d_{0}$-sparse, i.e.,
$\forall x\in\mathcal{X}:~{}\|f(x)\|_{0}\leq d_{0}$. The values of $f$ are
taken from a latent space $\mathcal{U}^{d}$, where $\mathcal{U}=\mathbb{R}$,
$[-1,1]$ or $\\{\pm 1\\}$, depending on the task.

For example, $\mathcal{X}$ can be a set of images of $k$ animal species and
$\mathcal{Y}=\\{\textnormal{e}_{i}\\}^{k}_{i=1}$ is the set of labels, where
$\textnormal{e}_{i}\in\mathbb{R}^{k}$ is the $i$’th elementary vector. In this
case, $y$ is a classifier that takes an animal image $x$ and returns the
species of the animal. The function $f$ corresponds to a set of $d$ binary
attributes $\\{f_{i}\\}^{d}_{i=1}$ (e.g., carnivore/herbivore). Each attribute
$f_{i}$ takes an image $x$ and returns whether the animal illustrated in $x$
satisfies $i^{\text{th}}$ attribute.

Similar to the standard learning setting, the set $\mathcal{X}$ is endowed
with a distribution $D$, from which samples $x$ are being taken. The learning
algorithm is provided with a set
$\mathcal{S}=\\{(x_{i},y(x_{i}))\\}^{m}_{i=1}$ of $m$ i.i.d. samples. In the
empirical risk minimization setting [76], the learning algorithm is supposed
to fit a hypothesis $H:\mathcal{X}\to\mathcal{Y}$ from a given hypothesis
class $\mathcal{H}$ that would minimize the expected risk:

$\mathcal{L}_{D}[H,y]:=\mathbb{E}_{x\sim D}[\ell(H(x),y(x))],$ (1)

where $\ell:\mathcal{Y}^{2}\to[0,\infty)$ is some loss function, for example,
the $\ell_{2}$ loss function $\ell_{2}(a,b)=\|a-b\|^{2}_{2}$ for regression or
the cross-entropy loss for classification. Since the algorithm is not provided
with a full access to $D$, the algorithm minimizes the empirical version of
it:

$\mathcal{L}_{\mathcal{S}}[H,y]:=\frac{1}{m}\sum_{(x,y(x))\in\mathcal{S}}\ell(H(x),y(x)),$
(2)

or by minimizing $\mathcal{L}_{\mathcal{S}}[H,y]$ along with additional
regularization terms.

In contrast to the standard learning setting, in our framework we would like
to learn a model $H=G\circ q\circ F$ that minimizes the expected risk, but
also recovers the semantic attributes $f(x)$ (without any access to these
attributes). Here, $F$ and $G$ are a trainable representation function and
classifier and $q$ is a pre-defined discretization operator.

Put differently, the labels are given as proxy labels, while the actual goal
is to learn a discrete-valued representation $q(F(x))$ of the data that
maximizes some measure of feature fidelity $d_{D}(F)=d_{D}(f;b\circ q\circ F)$
that depends on the distribution $D$ and a binarization function $b$ that
translates a vector into a binary vector (see Sec. 5 for details).

###  3.1 Measures of Feature Fidelity

The goal of training in the proposed setting is to learn a representation of
the data $q(F(x))$ that maximizes the fidelity of the extracted features with
respect to an unseen set of ground-truth binary attributes $f(x)$.

In this section, we define a generic family of functions $d_{D}(f;g)$ for
measuring the fidelity of a multi-variate function
$g:\mathcal{X}\to\mathcal{U}^{d}$ with respect to a multi-variate function
$f:\mathcal{X}\to\mathcal{U}^{n}$ over a distribution $D$ of samples.

Let $r(q_{1},q_{2};D)$ be a measure of accuracy between two univariate
functions $q_{1},q_{2}:\mathcal{X}\to\mathcal{U}$ over a distribution $D$. In
this paper, since we consider imbalanced attributes, $r$ is the F1 score.
Finally, we extend $r$ to be annotation invariant by using
$\hat{r}(q_{1},q_{2};D):=\max\\{r(q_{1},q_{2};D),r(q_{1},1-q_{2};D)\\}$ as a
measure of accuracy which is invariant to whether positive samples are denoted
by $1$ or $0$.

Let $g:\mathcal{X}\to\\{0,1\\}^{d}$ and $f:\mathcal{X}\to\\{0,1\\}^{n}$ be two
multivariate binary functions. We denote:

$\displaystyle
d_{D}(f\|g):=\max_{\pi:[n]\to[d]}\frac{1}{n}\sum^{n}_{i=1}\hat{r}(f_{i},g_{\pi(i)};D)=\frac{1}{n}\sum^{n}_{i=1}\max_{j\in[d]}\hat{r}(f_{i},g_{j};D)$
(3)

This quantity measures the average similarity between each feature $f_{i}$ in
$f$ to some feature $g_{j}$ in $g$.

The fidelity of $g$ with respect to $f$ is the harmonic mean
$d_{D}(f;g):=2\frac{d_{D}(f\|g)\cdot d_{D}(g\|f)}{d_{D}(f\|g)+d_{D}(g\|f)}$,
which is a symmetric measure of similarity. Informally, $d_{D}(f\|g)$ measures
the extent at which the set of attributes in $f$ can be treated as a subset of
the set of attributes in $g$ and $d_{D}(f;g)$ as the extent at which the sets
of attributes in $f$ and $g$ are equivalent. We use the harmonic mean since it
penalizes low values in contrast to the arithmetic mean.

When measuring the fidelity over a finite set of test samples
$\mathcal{S}_{T}$, the proposed $d_{D}(f;g)$ considers the discrete uniform
distribution $D=U[\mathcal{S}_{T}]$.

Finally, in some cases, it is more relevant to measure the distance between
$f$ and $g$, instead of their similarity. We note that our method can be
readily extended to this case by taking $r$ to be a distance function and
replacing the maximization in Eq. (3) and the definition of $\hat{r}$ by
minimization. For example, for real-valued functions (i.e.,
$\mathcal{U}\subset\mathbb{R}$), it is reasonable to use the distance between
the two functions, $r(q_{1},q_{2};D)=\mathbb{E}_{x\sim
D}[|q_{1}(x)-q_{2}(x)|]$.

##  4 Intersection Regularization

A key component of our method in Sec. 5 is the proposed notion of Intersection
Regularization. In this section, we introduce and theoretically study the
optimization dynamics of the intersection regularization.

Suppose we have two hypothesis classes
$\mathcal{G}=\\{G_{\theta}\mid\theta\in\Theta\\}$ and
$\mathcal{T}=\\{T_{\omega}\mid\omega\in\Omega\\}$, where $\Theta$ and $\Omega$
are two sets of parameters. Intersection regularization involves solving the
following problem:

$\displaystyle\min_{\theta\in\Theta}\min_{\omega\in\Omega}\mathcal{Q}(\theta,\omega)$
(4) where:
$\displaystyle\mathcal{Q}(\theta,\omega):=\mathcal{L}_{\mathcal{S}}[G_{\theta},y]+\mathcal{L}_{\mathcal{S}}[G_{\theta},T_{\omega}]$

In this problem, we are interested in learning a hypothesis
$G_{\theta}\in\mathcal{G}$ that is closest to the target function $y$ among
all members of $\mathcal{G}$ that can be approximated by a hypothesis
$T_{\omega}\in\mathcal{T}$. We can think of $\mathcal{T}$ as a prior knowledge
we have on the target function $y$. Therefore, in some sense, the term
$\mathcal{L}_{\mathcal{S}}[G_{\theta},T_{\omega}]$ acts as a regularization
term that restricts $G_{\theta}$ to be close to the class $\mathcal{T}$.

In Sec. 5, we use intersection regularization to train a neural network $G$
over a quantized representation that mimics a decision tree $T$ and minimizes
the classification error. In this case, the class $\mathcal{T}$ consists of
decision trees of a limited depth ($\omega$ is a vector that allocates an
encoding of the tree, including its structure and decision rules) and
$\mathcal{G}$ is a class of neural networks of a fixed architecture ($\theta$
is a vector of the weights and biases of a given network). The underlying
quantized representation thus obtained is suitable for classification by both
a decision tree and a neural network.

The following analysis focuses on two main properties: finding a local minima
of $\mathcal{Q}$ and arriving at an equilibrium point of $\mathcal{Q}$. An
equilibrium point of $\mathcal{Q}$ is a pair $(\theta,\omega)$, such that,
$\mathcal{Q}(\hat{\theta},\hat{\omega})=\min_{\theta}\mathcal{Q}(\theta,\hat{\omega})=\min_{\omega}\mathcal{Q}(\hat{\theta},\omega)$.
The proofs are given in the supplementary material and are based on Thm.
2.1.14 by Nesterov [52] and the analysis by Song et al. [67].

The following proposition shows that under certain conditions, it is possible
to converge to an equilibrium of $\mathcal{Q}(\theta,\omega)$ when iteratively
optimizing $\theta$ and $\omega$. To show that, we assume that $\mathcal{Q}$
is a convex function with respect to $\theta$ for any fixed value of $\omega$.
This is true, for example, when $G_{\theta}$ is the linearization of a wide
neural network [41], which also serve as universal approximators [36]. It has
also been proven that the optimization dynamics of wide neural networks match
the dynamics of their linearized version [41]. In addition, we assume that one
is able to compute a global minimizer $\omega$ of
$\mathcal{L}_{\mathcal{S}}[G_{\theta},T_{\omega}]$ for any $\theta$. This is
typically impossible, however, it is reasonable to assume that one is able to
approximately minimize $\mathcal{L}_{\mathcal{S}}[G_{\theta},T_{\omega}]$ with
respect to $\omega$ if it is being optimized by a descent optimizer.
Throughout the analysis, we assume that
$\cup_{\omega\in\Omega}\arg\min_{\theta}\mathcal{Q}(\theta,\omega)$ is well-
defined and bounded and that
$\lim_{\theta:~{}\|\theta\|\to\infty}\mathcal{L}_{\mathcal{S}}[G_{\theta},y]=\infty$.

######  Proposition 1.

Assume that $\mathcal{Q}(\theta,\omega)$ is convex and $\beta$-smooth w.r.t
$\theta$ for any fixed value of $\omega$. Let $\theta_{1}$ be some
initialization and
$\omega_{1}\in\arg\min_{\omega}\mathcal{Q}(\theta_{1},\omega)$. We define
$\theta_{t}$ to be the weights produced after $t$ iterations of applying
Gradient Descent on $\mathcal{Q}(\theta,\omega_{t-1})$ over $\theta$ with
learning rate $\mu<\beta^{-1}$ and
$\omega_{t}=\arg\min_{\omega}\mathcal{Q}(\theta_{t-1},\omega)$. Then, we have:

$\displaystyle\lim_{t\to\infty}\mathcal{Q}(\theta_{t},\omega_{t})=\lim_{t\to\infty}\min_{\theta}\mathcal{Q}(\theta,\omega_{t})=\lim_{t\to\infty}\min_{\omega}\mathcal{Q}(\theta_{t},\omega)$

The following proposition shows that if we apply Block Coordinate Gradient
Descent (BCGD) to optimize $\theta$ and $\omega$ for minimizing
$\mathcal{Q}(\theta,\omega)$ (starting at $(\theta_{1},\omega_{1})$), then,
they converge to a local minima that is also an equilibrium point. The BCGD
iteratively updates:
$\theta_{t+1}=\theta_{t}-\mu\nabla\mathcal{Q}(\theta_{t},\omega_{t})$ and
$\omega_{t+1}=\omega_{t}-\mu\nabla\mathcal{Q}(\theta_{t+1},\omega_{t})$.
Throughout the analysis we assume that the sets
$\cup_{\omega\in\Omega}\arg\min_{\theta}\mathcal{Q}(\theta,\omega)$ and
$\cup_{\theta\in\Theta}\arg\min_{\omega}\mathcal{Q}(\theta,\omega)$ are well-
defined and bounded.

######  Proposition 2.

Assume that $\mathcal{Q}(\theta,\omega)$ is a twice-continuously
differentiable, element-wise convex (i.e., convex w.r.t $\theta$ for any fixed
value of $\omega$ and vice versa), Lipschitz continuous and $\beta$-smooth
function, whose saddle points are strict. Let $\theta_{t}$, $\omega_{t}$ be
the weights produced after $t$ iterations of applying BCGD on
$\mathcal{Q}(\theta,\omega)$ with learning rate $\mu<\beta^{-1}$.
$(\theta_{t},\omega_{t})$ then converges to a local minima
$(\hat{\theta},\hat{\omega})$ of $\mathcal{Q}$ that is also an equilibrium
point.

##  5 Method

In this section, we discuss propose our method for dealing with the problem
introduced in Sec. 3.

Model  Informally, our algorithm aims at learning a sparse discrete
representation $F_{q}(x):=q(F(x))$ of the data, that is suitable for
classification by a decision tree $T$ of small depth. Intuitively, this leads
to a representation that supports classification by relatively simple decision
rules. For this purpose, we consider a model of the following form:
$H_{tree}=T\circ F_{q}$, where $F:\mathcal{X}\to\mathbb{R}^{d}$ is a trainable
neural network and $T:\mathbb{R}^{d}\to\mathbb{R}^{k}$ is a decision tree from
a class $\mathcal{T}$ of multivariate regression decision trees of maximal
depth $d_{\max}$. The function $G$ (and $T$) is translated into a classifier
by taking $\arg\max_{i\in[k]}G(F_{q}(x))$ (and
$\arg\max_{i\in[k]}T(F_{q}(x))$).

Algorithm 1 Intersection Regularization based Sparse Attributes Recovery

0: $\mathcal{S}=\\{(x_{i},y(x_{i}))\\}^{m}_{i=1}$ \- dataset;
$\lambda_{1},\lambda_{2},\lambda_{3}$ \- non-negative coefficients; $I$ \-
number of epochs; $s$ \- batch size; $A$ \- Tree training algorithm (and
splitting criteria);

1: Initialize $F,G$ and $T=\textnormal{None}$;

2: Partition $\mathcal{S}$ into batches $Batches(\mathcal{S})$ of size $s$;

3: for $i=1,\dots,I$ do

4: $\bar{\lambda}_{2}=\mathds{1}[i>1]\cdot\lambda_{2}$;

5: $\mathcal{S}^{\prime}=\emptyset$;

6: for $B\in Batches(\mathcal{S})$ do

7: Update $G$ using GD to minimize $\lambda_{1}\mathcal{L}_{B}[G\circ
F_{q},y]+\bar{\lambda}_{2}\mathcal{L}_{B}[G\circ F_{q},T\circ F_{q}]$;

8: Update $F$ using GD to minimize $\lambda_{1}\mathcal{L}_{B}[G\circ
F_{q},y]+\bar{\lambda}_{2}\mathcal{L}_{B}[G\circ F_{q},T\circ
F_{q}]+\lambda_{3}\mathcal{R}_{B}[F]$;

9: Extend
$\mathcal{S}^{\prime}=\mathcal{S}^{\prime}\cup\\{(F_{q}(x),G(F_{q}(x)))\mid
x\in B\\}$;

10: end for

11: Initialize decision tree $T$;

12: Train $T$ over $\mathcal{S}^{\prime}$ using $A$;

13: end for

14: return $F,G,T$;

In order to learn a neural network $G$ that minimizes the classification error
and also approximates a decision tree, we apply intersection regularization
between a class of neural networks $\mathcal{G}$ and the class of decision
trees $\mathcal{T}$. Our objective function is decomposed into several loss
functions. For each loss, we specify in brackets
$``[~{}\cdot~{}]^{\prime\prime}$ the components that are responsible for
minimizing the specified loss functions. For a full description of our method,
see Alg. 1.

For each epoch (line 3), we iteratively update the network to minimize its
objective function using GD and train the decision tree from scratch. To
optimize the neural network, we use two loss functions (lines 7-8). The first
one is the cross-entropy loss of $H_{net}$ with respect to the ground-truth
labels, and the second one is the soft cross-entropy loss of $H_{net}$ with
respect to the probabilities of $H_{tree}$,

$\displaystyle\mathcal{L}_{B}[G\circ F_{q},y]\textnormal{ and
}\mathcal{L}_{B}[G\circ F_{q},T\circ F_{q}],$ (5)

where the loss function $\ell:\Delta_{k}\times\Delta_{k}\to[0,\infty)$ is the
cross-entropy loss that is defined as follows:
$\ell(u,v):=-\sum^{k}_{i=1}v_{i}\cdot\log(u_{i})$, $k$ is the number of
classes and $\Delta_{k}$ is the standard simplex. The second loss is applied
only from the second epoch onward (line 4).

To encourage sparse representations [72, 38], we also apply $L_{1}$
regularization over the quantized representation of the data.

$\mathcal{R}_{B}[F]:=\frac{1}{m}\sum^{s}_{i=1}\|F_{q}(x_{i})\|_{1}$ (6)

Tree Optimization  During each epoch, we accumulate a dataset
$\mathcal{S}^{\prime}$ of pairs $(F_{q}(x),G(F_{q}(x)))$ for all of the
samples $x$ that have been incurred until the current iteration (line 9 in
Alg. 1). By the end of the epoch, we train a multivariate regression decision
tree $T$ from scratch over the dataset $\mathcal{S}^{\prime}$ (see line 12 in
Alg. 1). To train the decision tree, we used the CART algorithm [44] with the
information gain splitting criteria.

Quantization and Binarization  The function $F:\mathcal{X}\to\mathbb{R}^{n}$
is a real-valued multivariate function. To obtain a discrete representation of
the data, we discretize the outputs of $F$ using the uniform quantizer [62,
75] $q$, see supplementary for a step-by-step listing of the algorithm. This
quantization employs a finite number of equally-sized bins. Their size is
calculated by dividing the input range into $2^{r}$ bins, where $r$ specifies
the number of bits for encoding each bin.

Since the round function is non-differentiable, the gradients of the uniform
quantization are usually approximated [9, 55, 81]. In this paper, we utilize
the straight-through estimator (STE) [9], which assumes that the Jacobian of
rounding is just identity, to estimate gradients of the discretization.

For applying the feature fidelity measure proposed in Sec. 3.1, we first cast
the discrete vector $q(F(x))$ into a vector of binary features $b(q(F(x)))$
and compute $d_{D}(F):=d_{D}(f;b\circ q\circ F)$, where $b$ is a binarization
function. In this paper, we use the following binarization scheme. For a given
vector $v=q(F(x))$ we compute $u=b(v):=(u^{1}\|u^{2})$ as follows: for all
$i\in[n]$ and $j\in[2^{r}]$, we have: $u^{1}_{i,j}=\mathds{1}[v_{i}=j]$ and
$u^{2}_{i,j}=\mathds{1}[v_{i}\neq j]$, where $\mathds{1}$ is the indicator
function. The dimension of $u$ is $2^{r+1}\cdot n$.

##  6 Experiments

In this section, we evaluate our method on several datasets with attributes in
comparison with various baselines. To evaluate the attributes recovery
quality, we use the evaluation metric explained in Sec. 3.1 based on the F1
score.

Implementation Details  The architecture of the feature extractor $F$ is taken
from [14] with the published hyperparameters and is based on ResNet-50. The
classifier $G$ is a two-layered fully connected neural network. We initialize
the ResNet with pre-trained weights trained on ILSVRC2012 [57]. When training
our method and the baselines we employed the following early stopping
criteria: we train the model until the second epoch for which the accuracy
rate drops over a validation set, and report the results on the last epoch
before the drop.

Our method was run on 4 GeForce RTX 2080 Ti GPUs. On the aPscal and aYahoo
datasets, each epoch takes about 2-3 minutes, on the AwA dataset each epoch
takes 17-25 minutes, on CUB-200-2011 dataset each epoch takes 8-15 minutes.
The range of time depends on the representation capacity (e.g., no. bits,
dimension).

Throughout the experiments, we used the following default hyperparameters,
except in our ablation studies, where we varied the hyperparameters to
evaluate their effect. The coefficients for the loss functions
$\lambda_{1}=2$, $\lambda_{2}=1$, $\lambda_{3}=0.001$. Optimization was
carried out using SGD.

Datasets  Throughout our experiments, we used the following datasets. (i) The
aYahoo dataset [18], consisting of images from $12$ classes (e.g., bag, goat,
mug). Each image is labeled with $64$ binary attributes. The images are
collected from Yahoo. (ii) aPascal dataset [18] consisting of $20$ classes of
images. The images are labeled with the same $64$ binary attributes as in the
aYahoo dataset. (iii) Animals with attributes dataset (AwA2) [79] consisting
of images from $50$ animal classes, each class is labeled with $85$ numeric
attribute values, (iv) CUB-200-2011 [77] consisting of $200$ bird species
classes, each image is labeled with $312$ binary attribute values. We used the
standard train/evaluation splits of the datasets.

Baseline methods  We compare our method with various methods that capture a
wide variety of approaches: (i) SDT [22] and ANT [71], train a neural network
of a tree architecture with the intention of learning high-level concepts.
(ii) WS-DAN [31] is a method that generates attention maps to represent the
object’s discriminative parts in order to improve the classification. (iii)
DFL-CNN and Nts [78, 82] use a network that captures class-specific
discriminative regions. Region Grouping [32] is a similar method that also
uses a regularization term enforcing the empirical distribution of part
occurrence to align a U-shaped prior distribution. (iv) ProtoPNet [11]
computes similarity scores of informative patches in the image with learned
prototype images. These similarity scores are then aggregated by an MLP
classifier. All of the baselines, except ProtoPNet, are provided with labeled
samples, without access to ground-truth semantic segmentation of any kind. In
ProtoPNet they make use of cropping-based preprocessing that makes use of the
bounding boxes provided with the CUB-200-2011 dataset.

To measure the baselines’ and our method’s performance on our task, we apply
quantization on the penultimate layer of each model. For each method, we apply
configurations with penultimate layer dimension $128,256$ or $512$ and apply
uniform quantization with a $1,2,3$ or $4$ bits representation. We report, for
each method, the results of the configuration that provides the highest
accuracy rate on the validation set. Note that this selection is based on
accuracy and not on the feature fidelity score. The fidelity score is computed
as follows: $d_{D}(F):=d_{D}(f;b\circ q\circ F)$, where $F$ is the penultimate
layer of the model and $q$, $b$ are the uniform quantization and binarization
operators.

Table 1: Comparing the performance of various baselines with our method. We
report the classification accuracy rate (Acc) and the feature fidelity score
($d_{D}(F)$) for each method on each one of the datasets. For ProtoPNet on
CUB-200-2011, we report the results with (right) and without (left) using
cropping-based augmentations. As can be seen, our method outperforms the other
methods in terms of recovering the semantic attributes across datasets.

| CUB-200-2011 | aYahoo | AwA2 | aPascal
---|---|---|---|---
Method | Bits | Dim | Acc | $d_{D}(F)$ | Bits | Dim | Acc | $d_{D}(F)$ | Bits | Dim | Acc | $d_{D}(F)$ | Bits | Dim | Acc | $d_{D}(F)$
SDT [22] | 4 | 512 | 9.80% | 33.01 | 3 | 512 | 17.58% | 31.90 | 2 | 256 | 7.21% | 66.17 | 2 | 128 | 30.48% | 31.53
ANT [71] | 2 | 512 | 11.13% | 33.69 | 4 | 512 | 35.66% | 39.35 | 3 | 256 | 14.17% | 69.27 | 3 | 256 | 31.70% | 39.24
PMG [88] | 4 | 512 | 86.41% | 39.06 | 3 | 512 | 96.14% | 43.68 | 1 | 256 | 96.14% | 71.70 | 2 | 128 | 79.22% | 45.82
WS-DAN [31] | 4 | 256 | 87.54% | 37.90 | 2 | 256 | 96.82% | 56.90 | 4 | 512 | 96.22% | 78.08 | 3 | 512 | 79.03% | 57.44
DFL-CNN [78] | 3 | 512 | 85.88% | 37.56 | 3 | 512 | 88.16% | 30.06 | 4 | 256 | 89.20% | 65.01 | 4 | 256 | 72.82% | 43.13
Nts [82] | 2 | 128 | 85.42% | 40.66 | 3 | 128 | 98.11% | 55.27 | 4 | 256 | 96.12% | 79.40 | 3 | 128 | 76.10% | 53.42
API-Net [93] | 3 | 512 | 88.21% | 36.77 | 3 | 512 | 98.72% | 57.26 | 4 | 256 | 96.25% | 79.85 | 3 | 256 | 79.15% | 57.58
ProtoPNet [11] | 3 | 512 | 78.82% | 35.31 | 4 | 256 | 85.62% | 49.67 | 2 | 512 | 89.11% | 76.42 | 2 | 512 | 73.52% | 49.66
Region Group [32] | 3 | 512 | 86.10% | 40.45 | 2 | 512 | 97.70% | 58.90 | 3 | 512 | 96.11% | 80.27 | 3 | 256 | 77.27% | 56.80
Quantized network | 4 | 512 | 80.08% | 40.22 | 1 | 512 | 98.08% | 55.75 | 2 | 512 | 95.30% | 80.32 | 2 | 256 | 74.80% | 56.30
Quantized net + DT | 4 | 512 | 39.04% | 32.11 | 1 | 512 | 58.24% | 35.77 | 2 | 512 | 52.09% | 68.77 | 2 | 256 | 47.65% | 33.82
Quantized net + L1 | 4 | 512 | 80.61% | 41.82 | 1 | 512 | 97.57% | 59.20 | 2 | 512 | 94.81% | 83.31 | 2 | 256 | 75.06% | 59.80
Our method | 4 | 512 | 79.82% | 42.58 | 1 | 512 | 96.86% | 61.46 | 2 | 512 | 94.48% | 84.67 | 2 | 256 | 75.09% | 61.72

#### Quantitative Analysis

In Tab. 1 we report the results of our method and the various baselines on
each one of the datasets. As can be seen, our method has a significantly
higher feature fidelity score, compared to the baselines across all datasets.
We note that ProtoPNet [11] makes use of cropping-based preprocessing. In
order to fairly compare its results with the rest of the methods, we omitted
using the preprocessing on all datasets except for CUB-200-2011. As can be
seen, our method achieves a fidelity score that is higher than ProtoPNet’s on
CUB-200-2011, even though this kind of supervision helps ProtoPNet achieve the
most competitive feature fidelity score among the baselines. On the other
datasets, where no such crops were available, and ProtoPNet is trained on the
entire frame, the feature fidelity score of ProtoPNet is significantly worse
than that of our method.

#### Ablation Study

We conducted several ablation studies to validate the soundness of our method.
Throughout the ablations, we compared our method with three of its variations:
(i) a quantized network trained to minimize the cross-entropy loss, (ii) a
quantized network trained to minimize the cross-entropy loss and the $L_{1}$
regularization loss and (iii) a quantized network with a differentiable soft
decision tree (SDT) on top of it, trained to minimize the cross-entropy loss.
In all three cases, the neural network is initialized with weights pre-trained
on ILSVRC2012 [57]. We used the online learning decision trees of Domingos and
Hulten [13]. The quantized network uses the same architecture as our model and
is trained with the same hyperparameters. As can be seen in Tab. 1, our method
significantly improves the recovery of the semantic attributes, at the small
expense of a slight decrease in the classification accuracy, which is of
second priority for our task.

To validate that the obtain performance gap in the fidelity score $d_{D}(F)$
is consistent across multiple configurations, we report in Fig 2 the results
of the baseline method (i) and our complete method. As can be seen, our method
does not harm the models’ accuracy, while it generally improves the feature
fidelity score across the various configurations of feature dimensions and the
number of bits used in the binarization process.

A qualitative analysis studying which attributes emerge within the learned
representations by applying our full method is presented in the supplementary
material.

|  |  |
---|---|---|---
|  |  |
(a) CUB-200-201 | (b) aYahoo | (c) AwA2 | (d) aPascal

Figure 2: Comparing the performance of our method (blue) and a standard
quantized neural network (orange). We compare the feature fidelity score
($d_{D}(F)$) (top) and the classification accuracy rate (bottom). We plot the
results for different configurations of feature dimensions $n$ and number of
bits $k$ for binarization. Each configuration is labeled with $(n,k)$.

##  7 Limitations

There are a few limitations to both our problem setting and algorithmic
approach. First, the problem of ‘Weakly Supervised Recovery of Semantic
Attributes’ discussed in Sec. 3 is ill-posed in the general case. That is
because we do not have an access to the ground-truth binary attributes, and
potentially the function $f(x)$ could be replaced with a different function,
even when assuming that $y(x)$ is a function of $f(x)$. For example, in
general, if $y(x)=\textnormal{sign}(\sum_{i}f(x)_{i})$, then, there are
typically multiple functions $f(x)$ that could implement $y(x)$. In
particular, it is typically unknown what the dimension of $F$ is ought to be.
This is no different to other unsupervised learning settings, such as,
clustering [61, 5], cross-domain mapping [92, 29, 37, 23], domain adaptation
[7, 6, 47, 48], causality and disentanglement [53, 43] and sparse dictionary
learning [30, 24], where ambiguity is an inherent aspect of the learning
problem.

This issue makes this problem challenging, especially when the number of
ground-truth attributes is large as in the case of CUB-200-2011, or there are
multiple redundant attributes in the dataset.

To cope with this issue in unsupervised learning, we typically make
assumptions on the structure of the target function, which narrows the space
of functions captured by the algorithm. In our case, we assume that $y(x)$ can
be represented as $t(f(x))$, where $t$ is a decision tree of a small depth.

##  8 Conclusions

In this paper, we introduced the problem of weakly supervised recovery of
semantic attributes. This problem explores the emergence of interpretable
features quantitatively, based on a set of semantic features that is unseen
during training. We present evidence that methods that are tailored to extract
semantic attributes do not necessarily perform well in this metric and suggest
a new approach to solving this problem. Our method is based on learning,
concurrently, in the soft-intersection of two hypothesis classes: a neural
network for obtaining its classification power, and a decision tree to learn
features that lend themselves to classification by short logical expressions.
We demonstrate that learning this way is more effective than other methods for
the new task and that learning with the new regularization scheme improves the
fidelity of the obtained feature map.

## Acknowledgment

This project has received funding from the European Research Council (ERC)
under the European Unions Horizon 2020 research and innovation programme
(grant ERC CoG 725974).

## References

  * Alvarez-Melis and Jaakkola [2018a] David Alvarez-Melis and Tommi S. Jaakkola.  Towards robust interpretability with self-explaining neural networks.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31, pages 7775–7784. Curran Associates, Inc., 2018a.
  * Alvarez-Melis and Jaakkola [2018b] David Alvarez-Melis and Tommi S. Jaakkola.  On the robustness of interpretability methods.  _arXiv preprint arXiv:1806.08049_ , 2018b.
  * Asano et al. [2019] Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi.  A critical analysis of self-supervision, or what we can learn from a single image.  _arXiv preprint arXiv:1904.13132_ , 2019.
  * Bach et al. [2015] Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojciech Samek.  On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation.  _PloS one_ , 10(7):e0130140, 2015.
  * Ben-David [2018] Shai Ben-David.  Clustering - what both theoreticians and practitioners are doing wrong.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 32(1), Apr. 2018.
  * Ben-david et al. [2006] Shai Ben-david, John Blitzer, Koby Crammer, and Fernando Pereira.  Analysis of representations for domain adaptation.  In _NIPS_ , pages 137–144, 2006.
  * Ben-David et al. [2010] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  _Machine Learning_ , 79(1-2):151–175, 2010.
  * Bengio et al. [2013a] Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Representation learning: A review and new perspectives.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 35(8):1798–1828, August 2013a.  ISSN 0162-8828.  doi: 10.1109/TPAMI.2013.50.
  * Bengio et al. [2013b] Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  _CoRR_ , abs/1308.3432, 2013b.
  * Brakel and Bengio [2017] Philemon Brakel and Yoshua Bengio.  Learning independent features with adversarial nets for non-linear ica, 2017.
  * Chen et al. [2019] Chaofan Chen, Oscar Li, Daniel Tao, Alina Barnett, Cynthia Rudin, and Jonathan K Su.  This looks like that: Deep learning for interpretable image recognition.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Dabkowski and Gal [2017] Piotr Dabkowski and Yarin Gal.  Real time image saliency for black box classifiers.  In _Advances in Neural Information Processing Systems_ , pages 6970–6979, 2017.
  * Domingos and Hulten [2000] Pedro Domingos and Geoff Hulten.  Mining high-speed data streams.  In _Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’00, page 71–80, New York, NY, USA, 2000. Association for Computing Machinery.  ISBN 1581132336.
  * Du et al. [2020] Ruoyi Du, Dongliang Chang, Ayan Kumar Bhunia, Jiyang Xie, Zhanyu Ma, Yi-Zhe Song, and Jun Guo.  Fine-grained visual classification via progressive multi-granularity training of jigsaw patches.  In _European Conference on Computer Vision_ , pages 153–168. Springer, 2020.
  * Duan et al. [2012] Kun Duan, Devi Parikh, David J. Crandall, and Kristen Grauman.  Discovering localized attributes for fine-grained recognition.  In _2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, June 16-21, 2012_ , pages 3474–3481. IEEE Computer Society, 2012.  doi: 10.1109/CVPR.2012.6248089.  URL https://doi.org/10.1109/CVPR.2012.6248089.
  * Erhan et al. [2009] Dumitru Erhan, Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Visualizing higher-layer features of a deep network.  _University of Montreal_ , 1341(3):1, 2009.
  * Farhadi et al. [2009a] Ali Farhadi, Ian Endres, Derek Hoiem, and David Forsyth.  Describing objects by their attributes.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1778–1785, 2009a.  doi: 10.1109/CVPR.2009.5206772.
  * Farhadi et al. [2009b] Ali Farhadi, Ian Endres, Derek Hoiem, and David Forsyth.  Describing objects by their attributes.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1778–1785. IEEE, 2009b.
  * Feng et al. [2018] Zunlei Feng, Xinchao Wang, Chenglong Ke, Anxiang Zeng, Dacheng Tao, and Mingli Song.  Dual swap disentangling.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 5898–5908, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Fong and Vedaldi [2017] Ruth C. Fong and Andrea Vedaldi.  Interpretable explanations of black boxes by meaningful perturbation.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 3429–3437, 2017.
  * Fong et al. [2019] Ruth C. Fong, Mandela Patrick, and Andrea Vedaldi.  Understanding deep networks via extremal perturbations and smooth masks.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 2950–2958, 2019.
  * Frosst and Hinton [2017] Nicholas Frosst and Geoffrey Hinton.  Distilling a neural network into a soft decision tree.  _arXiv preprint arXiv:1711.09784_ , 2017.
  * Galanti et al. [2018] Tomer Galanti, Lior Wolf, and Sagie Benaim.  The role of minimal complexity functions in unsupervised learning of semantic mappings.  In _International Conference on Learning Representations_ , 2018.
  * Garfinkle and Hillar [2019] Charles J. Garfinkle and Christopher J. Hillar.  On the uniqueness and stability of dictionaries for sparse representation of noisy signals.  _IEEE Transactions on Signal Processing_ , 67(23):5884–5892, 2019.  doi: 10.1109/TSP.2019.2935914.
  * Gu et al. [2018] Jindong Gu, Yinchong Yang, and Volker Tresp.  Understanding individual decisions of cnns via contrastive backpropagation.  In _Asian Conference on Computer Vision_ , pages 119–134. Springer, 2018.
  * Guidotti et al. [2018] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi.  A survey of methods for explaining black box models.  _ACM computing surveys (CSUR)_ , 51(5):1–42, 2018\.
  * Gur et al. [2020] Shir Gur, Ameen Ali, and Lior Wolf.  Visualization of supervised and self-supervised neural networks via attribution guided factorization.  _arXiv preprint arXiv:2012.02166_ , 2020.
  * Gutierrez et al. [2019] Patricia Gutierrez, Pierre-Antoine Sondag, Petar Butkovic, Mauro Lacy, Jordi Berges, Felipe Bertrand, and Arne Knudson.  Deep learning for automated tagging of fashion images.  In Laura Leal-Taixé and Stefan Roth, editors, _Computer Vision – ECCV 2018 Workshops_ , pages 3–11, Cham, 2019. Springer International Publishing.  ISBN 978-3-030-11015-4.
  * He et al. [2016] Di He, Yingce Xia, Tao Qin, Liwei Wang, Nenghai Yu, Tie-Yan Liu, and Wei-Ying Ma.  Dual learning for machine translation.  In _Advances in Neural Information Processing Systems_. Curran Associates, Inc., 2016.
  * Hillar and Sommer [2015] Christopher J. Hillar and Friedrich T. Sommer.  When can dictionary learning uniquely recover sparse data from subsamples?  _IEEE Transactions on Information Theory_ , 61(11):6290–6297, 2015.  doi: 10.1109/TIT.2015.2460238.
  * Hu et al. [2019] Tao Hu, Honggang Qi, Qingming Huang, and Yan Lu.  See better before looking closer: Weakly supervised data augmentation network for fine-grained visual classification, 2019.
  * Huang and Li [2020] Zixuan Huang and Yin Li.  Interpretable and accurate fine-grained recognition via region grouping.  In _CVPR_ , pages 8662–8672, 2020.
  * Hubara et al. [2018] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Quantized neural networks: Training neural networks with low precision weights and activations.  _Journal of Machine Learning Research_ , 18(187):1–30, 2018.
  * Irsoy et al. [2012] Ozan Irsoy, Olcay Taner Yildiz, and Ethem Alpaydin.  Soft decision trees.  In _International Conference on Pattern Recognition_ , 2012.
  * Iwana et al. [2019] Brian Kenji Iwana, Ryohei Kuroki, and Seiichi Uchida.  Explaining convolutional neural networks using softmax gradient layer-wise relevance propagation.  _arXiv preprint arXiv:1908.04351_ , 2019.
  * Ji et al. [2020] Ziwei Ji, Matus Telgarsky, and Ruicheng Xian.  Neural tangent kernels, transportation mappings, and universal approximation.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HklQYxBKwS.
  * Kim et al. [2017] Taeksoo Kim, Moonsu Cha, Hyunsoo Kim, Jung Kwon Lee, and Jiwon Kim.  Learning to discover cross-domain relations with generative adversarial networks.  In _International Conference on Machine Learning (ICML)_ , Proceedings of Machine Learning Research. PMLR, 2017.
  * Koh et al. [2007] Kwangmoo Koh, Seung-Jean Kim, and Stephen Boyd.  An interior-point method for large-scale $\ell_{1}$-regularized logistic regression.  _Journal of Machine Learning Research_ , 8(54):1519–1555, 2007.
  * Lake et al. [2017] Brenden M. Lake, Tomer D. Ullman, Joshua B. Tenenbaum, and Samuel J. Gershman.  Building machines that learn and think like people.  _Behavioral and Brain Sciences_ , 40:e253, 2017.  doi: 10.1017/S0140525X16001837.
  * Lampert et al. [2009] Christoph H. Lampert, Hannes Nickisch, and Stefan Harmeling.  Learning to detect unseen object classes by between-class attribute transfer.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 951–958, 2009.  doi: 10.1109/CVPR.2009.5206594.
  * Lee et al. [2019] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/0d1a9651497a38d8b1c3871c84528bd4-Paper.pdf.
  * Li et al. [2018] Kunpeng Li, Ziyan Wu, Kuan-Chuan Peng, Jan Ernst, and Yun Fu.  Tell me where to look: Guided attention inference network.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 9215–9223, 2018.
  * Locatello et al. [2019] Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem.  Challenging common assumptions in the unsupervised learning of disentangled representations.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 4114–4124. PMLR, 09–15 Jun 2019.
  * Loh [2011] Wei-Yin Loh.  Classification and regression trees.  _Wiley interdisciplinary reviews: data mining and knowledge discovery_ , 1(1):14–23, 2011.
  * Lundberg and Lee [2017] Scott M. Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In _Advances in Neural Information Processing Systems_ , pages 4765–4774, 2017.
  * Mahendran and Vedaldi [2016] Aravindh Mahendran and Andrea Vedaldi.  Visualizing deep convolutional neural networks using natural pre-images.  _International Journal of Computer Vision_ , 120(3):233–255, 2016.
  * Mansour [2009] Yishay Mansour.  Learning and domain adaptation.  In _Algorithmic Learning Theory, 20th International Conference, ALT_ , pages 4–6, 2009.
  * Mansour et al. [2009] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  In _COLT - The 22nd Conference on Learning Theory_ , 2009.
  * Marx et al. [2019] Charles Marx, Richard Phillips, Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian.  Disentangling influence: Using disentangled representations to audit model predictions.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/55a988dfb00a914717b3000a3374694c-Paper.pdf.
  * Montavon et al. [2017] Grégoire Montavon, Sebastian Lapuschkin, Alexander Binder, Wojciech Samek, and Klaus-Robert Müller.  Explaining nonlinear classification decisions with deep taylor decomposition.  _Pattern Recognition_ , 65:211–222, 2017.
  * Nam et al. [2019] Woo-Jeoung Nam, Shir Gur, Jaesik Choi, Lior Wolf, and Seong-Whan Lee.  Relative attributing propagation: Interpreting the comparative contributions of individual units in deep neural networks.  _arXiv preprint arXiv:1904.00605_ , 2019.
  * Nesterov [2014] Yurii Nesterov.  _Introductory Lectures on Convex Optimization: A Basic Course_.  Springer Publishing Company, Incorporated, 1 edition, 2014.  ISBN 1461346916.
  * Peters et al. [2017] J. Peters, D. Janzing, and B. Schölkopf.  _Elements of Causal Inference: Foundations and Learning Algorithms_.  MIT Press, Cambridge, MA, USA, 2017.
  * Project [2021] Jepson Flora Project.  Jepson eFlora, 2021.  URL https://ucjeps.berkeley.edu/eflora/.
  * Ramapuram and Webb [2019] Jason Ramapuram and Russ Webb.  Improving discrete latent representations with differentiable approximation bridges, 2019.
  * Ribeiro et al. [2016] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  “Why should I trust you?”: Explaining the predictions of any classifier.  In _Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, pages 1135–1144, New York, NY, USA, 2016. ACM.  ISBN 978-1-4503-4232-2.
  * Russakovsky et al. [2015] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  Imagenet large scale visual recognition challenge.  _Int. J. Comput. Vision_ , 115(3):211–252, December 2015.
  * Sattar et al. [2017] Hosnieh Sattar, Andreas Bulling, and Mario Fritz.  Predicting the category and attributes of visual search targets using deep gaze pooling.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV) Workshops_ , Oct 2017.
  * Schmidhuber [1992] Jürgen Schmidhuber.  Learning factorial codes by predictability minimization.  _Neural Comput._ , 4(6):863–879, November 1992\.  ISSN 0899-7667.  doi: 10.1162/neco.1992.4.6.863.  URL https://doi.org/10.1162/neco.1992.4.6.863.
  * Selvaraju et al. [2017] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _Proceedings of the IEEE international conference on computer vision_ , pages 618–626, 2017.
  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, New York, NY, USA, 2014.  ISBN 1107057132, 9781107057135.
  * Sheppard [1897] William Fleetwood Sheppard.  On the calculation of the most probable values of frequency-constants, for data arranged according to equidistant division of a scale.  _Proceedings of the London Mathematical Society_ , 1(1):353–380, 1897.
  * Shrikumar et al. [2016] Avanti Shrikumar, Peyton Greenside, Anna Shcherbina, and Anshul Kundaje.  Not just a black box: Learning important features through propagating activation differences.  _arXiv preprint arXiv:1605.01713_ , 2016.
  * Shulman and Wolf [2020] Eyal Shulman and Lior Wolf.  Meta decision trees for explainable recommendation systems.  In _Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society_ , AIES ’20, page 365–371, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450371100.
  * Simonyan et al. [2013] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  _arXiv preprint arXiv:1312.6034_ , 2013.
  * Smilkov et al. [2017] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg.  Smoothgrad: removing noise by adding noise.  _arXiv preprint arXiv:1706.03825_ , 2017.
  * Song et al. [2017] Enbin Song, Zhubin Shen, and Qingjiang Shi.  Block coordinate descent only converge to minimizers, 2017.
  * Srinivas and Fleuret [2019] Suraj Srinivas and François Fleuret.  Full-gradient representation for neural network visualization.  In _Advances in Neural Information Processing Systems_ , pages 4126–4135, 2019.
  * Stokes [2009] Peter Stokes.  Computer-aided palaeography, present and future.  In Malte Rehbein, Torsten Schaßan, and Patrick Sahle, editors, _Kodikologie und Paläographie im digitalen Zeitalter - Codicology and Palaeography in the Digital Age_ , volume 2, pages 309–338. BoD, Norderstedt, 2009.
  * Sundararajan et al. [2017] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 3319–3328. JMLR. org, 2017.
  * Tanno et al. [2019] Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori.  Adaptive neural trees.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6166–6175. PMLR, 09–15 Jun 2019.
  * Tibshirani [1996] Robert Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , 58(1):267–288, 1996.
  * Tsai et al. [2020] Yao-Hung Hubert Tsai, Han Zhao, Makoto Yamada, Louis-Philippe Morency, and Russ R Salakhutdinov.  Neural methods for point-wise dependency estimation.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 62–72. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/00a03ec6533ca7f5c644d198d815329c-Paper.pdf.
  * Tschannen et al. [2018] Michael Tschannen, Olivier Frederic Bachem, and Mario Lučić.  Recent advances in autoencoder-based representation learning.  In _Bayesian Deep Learning Workshop, NeurIPS_ , 2018.
  * Vanhoucke et al. [2011] Vincent Vanhoucke, Andrew Senior, and Mark Z. Mao.  Improving the speed of neural networks on cpus.  In _Deep Learning and Unsupervised Feature Learning Workshop, NIPS 2011_ , 2011.
  * Vapnik [1992] Vladimir Vapnik.  Principles of risk minimization for learning theory.  In J. Moody, S. Hanson, and R. P. Lippmann, editors, _Advances in Neural Information Processing Systems_ , volume 4. Morgan-Kaufmann, 1992.  URL https://proceedings.neurips.cc/paper/1991/hash/ff4d5fbbafdf976cfdc032e3bde78de5-Abstract.html.
  * Wah et al. [2011] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie.  The Caltech-UCSD Birds-200-2011 Dataset.  Technical Report CNS-TR-2011-001, Caltech, 2011.
  * Wang et al. [2018] Yaming Wang, Vlad I. Morariu, and Larry S. Davis.  Learning a discriminative filter bank within a CNN for fine-grained recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * Xian et al. [2018] Yongqin Xian, Christoph H. Lampert, Bernt Schiele, and Zeynep Akata.  Zero-shot learning—a comprehensive evaluation of the good, the bad and the ugly.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 41(9):2251–2265, 2018.
  * Xu et al. [2020] Wenjia Xu, Jiuniu Wang, Yang Wang, Yirong Wu, and Zeynep Akata.  Generating visual and semantic explanations with multi-task network.  In _European Conference on Computer Vision_ , pages 620–635. Springer, 2020.
  * Yang et al. [2019] Jiwei Yang, Xu Shen, Jun Xing, Xinmei Tian, Houqiang Li, Bing Deng, Jianqiang Huang, and Xian-sheng Hua.  Quantization networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Yang et al. [2018] Ze Yang, Tiange Luo, Dong Wang, Zhiqiang Hu, Jun Gao, and Liwei Wang.  Learning to navigate for fine-grained classification.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , September 2018.
  * Yeh et al. [2019] Chih-Kuan Yeh, Cheng-Yu Hsieh, Arun Sai Suggala, David Inouye, and Pradeep Ravikumar.  How sensitive are sensitivity-based explanations?  _arXiv preprint arXiv:1901.09392_ , 2019.
  * Yu et al. [2013] Felix X. Yu, Liangliang Cao, Rogerio S. Feris, John R. Smith, and Shih-Fu Chang.  Designing category-level attributes for discriminative visual recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2013.
  * Zeiler and Fergus [2014] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In _European conference on computer vision_ , pages 818–833. Springer, Cham, 2014.
  * Zhang et al. [2018] Jianming Zhang, Sarah Adel Bargal, Zhe Lin, Jonathan Brandt, Xiaohui Shen, and Stan Sclaroff.  Top-down neural attention by excitation backprop.  _International Journal of Computer Vision_ , 126(10):1084–1102, 2018.
  * Zhang et al. [2014] Ning Zhang, Manohar Paluri, Marc’Aurelio Ranzato, Trevor Darrell, and Lubomir Bourdev.  Panda: Pose aligned networks for deep attribute modeling.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1637–1644, 2014.
  * Zhang et al. [2021] Tian Zhang, Dongliang Chang, Zhanyu Ma, and Jun Guo.  Progressive co-attention network for fine-grained visual classification, 2021.
  * Zhou et al. [2016a] Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba.  Learning deep features for discriminative localization.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2921–2929, 2016a.
  * Zhou et al. [2018] Bolei Zhou, David Bau, Aude Oliva, and Antonio Torralba.  Interpreting deep visual representations via network dissection.  _IEEE transactions on pattern analysis and machine intelligence_ , 2018.
  * Zhou et al. [2016b] Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  _arXiv preprint arXiv:1606.06160_ , 2016b.
  * Zhu et al. [2017] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A. Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In _International Conference on Computer Vision (ICCV)_. IEEE Computer Society, 2017.
  * Zhuang et al. [2020] Peiqin Zhuang, Yali Wang, and Yu Qiao.  Learning attentive pairwise interaction for fine-grained classification.  In _AAAI_ , pages 13130–13137, 2020.

##  Appendix A Uniform Quantization

The uniform quantization method is fully described in Alg. 2. For a given
function $p$, we denote by $\partial p$ the estimated gradients of $p$ w.r.t
$x$. In Alg. 2, the estimated gradient of $\tilde{z}$ is computed as the
gradient of $\min(\max(z_{init},q_{\min}),q_{\max})$ (since
$\partial\mathrm{round}(x)=1$ when applying STE [9]), which is simply
$\mathds{1}[z_{init}\in(q_{\min},q_{\max})]\cdot\frac{\partial
z_{init}}{\partial x}$, where $\frac{\partial z_{init}}{\partial x}$ is the
gradient of $z_{init}$ w.r.t $x$. $\partial\tilde{q}_{i}$ and $\partial{q}$
are defined similarly, see lines 10-11 in Alg. 2.

Algorithm 2 The uniform quantization method (forward and backward passes)

0: $x$ is tensor to be quantized; $r$ number of bits.

1: $q_{\min},q_{\max}=0,2^{r}-1$;

2: $x_{\min},x_{\max}=\min_{j}\\{x_{j}\\},\max_{j}\\{x_{j}\\}$;

3: $s=\frac{x_{\max}-x_{\min}}{q_{\max}-q_{\min}}$;

4: $z_{\text{init}}=\frac{q_{\min}-x_{\min}}{s}$;

5: $z=\min(\max(z_{\text{init}},q_{\min}),q_{\max})$;

6: $\tilde{z}=\mathrm{round}(z)$;

7: $\forall i:~{}\tilde{q}_{i}=\tilde{z}+\frac{x_{i}}{s}$;

8: $\forall
i:~{}q_{i}=\mathrm{round}(\min(\max(\tilde{q}_{i},q_{\min}),q_{\max}))$;

9:
$\partial\tilde{z}=\mathds{1}[z_{init}\in(q_{\min},q_{\max})]\cdot\frac{\partial
z_{init}}{\partial x}$;

10: $\forall
i:~{}\partial\tilde{q}_{i}=\partial\tilde{z}+\frac{\partial(x_{i}/s)}{\partial
x}$;

11: $\forall i:~{}\partial
q_{i}=\mathds{1}[\tilde{q_{i}}\in(q_{\min},q_{\max})]\cdot\partial\tilde{q}_{i}$;

12: return $q$, $\partial q$;

##  Appendix B Additional Experimental Details

Datasets  (i) The aYahoo dataset [18] consists of 1850 training images and 794
test images, (ii) the aPascal dataset [18] has 2869 training images and 2227
test images, (iii) in the AwA2 dataset [79] we used 26125 training images and
11197 test images, and (iv) the CUB-200-2011 dataset [77] contains 5994
training images and 5794 test images. We used the standard train/test splits
for each one of the datasets, except for AwA2, where we follow a 0.7/0.3
random split because there is no standard partition for this dataset.

Runtime and Infrastructure  The experiments were run on three GeForce RTX 3090
GPUs. Our method completes an epoch every 7 minutes on aYahoo, 10 minutes on
aPascal, 1 hour on AwA2, and 1 hour on CUB-200-2011. On average our method
runs for approximately 12 epochs on both aYahoo and aPascal, 2-4 epochs on
AwA2, and 35-40 on CUB-200-2011.

##  Appendix C Qualitative Analysis

We provide a qualitative analysis of the advantage of our method over a simple
neural network with a quantized representation layer. In this experiment, for
each ground-truth attribute $q_{i}(x)$ in the dataset, we compute the degree
it appears in the learned binarized representation layer $b\circ q\circ F$ for
each method: $d_{D}(q_{i};b\circ q\circ F)$. In Figs. 3-5 we plot the values
of $d_{D}(q_{i};b\circ q\circ F)$ for each attribute in the dataset as a
heatmap. We also report the number of attributes for which our method achieves
a higher score (by at least $\epsilon=0.05$) and vice versa.

Figure 3: Heatmaps of $d_{D}(q_{i};b\circ q\circ F)$ on the aYahoo dataset
[18]. In (top) we report the results of our method and (bottom) reports the
results of a standard neural network with a quantized representation layer.
Our method has a higher score on 23 attributes and a lower score on 4
attributes. Figure 4: Heatmaps of $d_{D}(q_{i};b\circ q\circ F)$ on the
aPascal dataset [18]. In (top) we report the results of our method and
(bottom) reports the results of a standard neural network with a quantized
representation layer. Our method has a higher score on 38 attributes and a
lower score on 3 attributes.  Figure 5: Heatmaps of $d_{D}(q_{i};b\circ q\circ
F)$ on the AwA2 dataset [79]. In (top) we report the results of our method and
(bottom) reports the results of a standard neural network with a quantized
representation layer. Our method has a higher score on 48 attributes and a
lower score on 3 attributes.

##  Appendix D Proofs of Props. 1 and 2

See 1

###### Proof.

First, we would like to prove that $\mathcal{Q}(\theta_{t},\omega_{t})$ is
monotonically decreasing. We notice that for each $t\in\mathbb{N}$, we have:

$\mathcal{Q}(\theta_{t},\omega_{t})\leq\mathcal{Q}(\theta_{t},\omega_{t-1})$
(7)

since $\omega_{t}$ is the global minimizer of
$\mathcal{Q}(\theta_{t},\omega)$. In addition, by the proof of (cf. Nesterov
[52], Thm. 2.1.14), we have:

$\displaystyle\mathcal{Q}(\theta_{t},\omega_{t-1})\leq\mathcal{Q}(\theta_{t-1},\omega_{t-1})-\eta\|\nabla_{\theta}\mathcal{Q}(\theta_{t},\omega_{t-1})\|^{2}_{2}\leq\mathcal{Q}(\theta_{t-1},\omega_{t-1}),$
(8)

where $\eta:=\mu(1-0.5\beta\mu)>0$. Therefore, we conclude that
$\mathcal{Q}(\theta_{t},\omega_{t})$ is indeed monotonically decreasing. Since
$\mathcal{Q}$ is non-negative, we conclude that
$\mathcal{Q}(\theta_{t},\omega_{t})$ is a convergent sequence. In particular,
$\theta_{t}$ is bounded. Otherwise,
$\mathcal{Q}(\theta_{t},\omega_{t})\geq\mathcal{L}_{\mathcal{S}}[h_{\theta_{t}},y]\to\infty$
in contradiction to the fact that $\mathcal{Q}(\theta_{t},\omega_{t})$ is a
convergent sequence.

Next, by applying the convexity of $\mathcal{Q}(\theta,\omega_{t-1})$ (as a
function of $\theta$), we have:

$\displaystyle\mathcal{Q}(\theta_{t},\omega_{t-1})-\mathcal{Q}(\theta^{*}_{t},\omega_{t-1})\leq\langle\nabla_{\theta}\mathcal{Q}(\theta,\omega_{t-1}),\theta_{t}-\theta^{*}_{t}\rangle\leq\|\nabla_{\theta}\mathcal{Q}(\theta_{t},\omega_{t-1})\|_{2}\cdot\|\theta_{t}-\theta^{*}_{t}\|_{2},$
(9)

where $\theta^{*}_{t}=\arg\min_{\theta}\mathcal{Q}(\theta,\omega_{t})$. By
combining Eqs. (8) and (9), we have:

$\displaystyle\mathcal{Q}(\theta_{t},\omega_{t})\leq\mathcal{Q}(\theta_{t},\omega_{t-1})\leq\mathcal{Q}(\theta_{t-1},\omega_{t-1})-\frac{\eta}{\|\theta_{t}-\theta^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t-1},\omega_{t-1})-\min_{\theta}\mathcal{Q}(\theta,\omega_{t-1})\right)^{2}$
(10)

In particular,

$\displaystyle\mathcal{Q}(\theta_{t-1},\omega_{t-1})-\mathcal{Q}(\theta_{t},\omega_{t})\geq\frac{\eta}{\|\theta_{t}-\theta^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t-1},\omega_{t-1})-\min_{\theta}\mathcal{Q}(\theta,\omega_{t-1})\right)^{2}$
(11)

Since the left hand side tends to zero and the right hand side is lower
bounded by zero, by the sandwich theorem, the right hand side tends to zero as
well. Since both $\theta_{t}$ and $\theta^{*}_{t}$ are bounded sequences
($\\{\arg\min_{\theta}\mathcal{Q}(\theta,\omega)\mid\omega\in\Omega\\}$ is
well-defined and bounded), we conclude that
$\lim_{t\to\infty}\mathcal{Q}(\theta_{t},\omega_{t})=\lim_{t\to\infty}\min_{\theta}\mathcal{Q}(\theta,\omega_{t})$.
We also have:
$\mathcal{Q}(\theta_{t},\omega_{t})=\min_{\omega}\mathcal{Q}(\theta_{t},\omega)$
by definition, and therefore,
$\lim_{t\to\infty}\mathcal{Q}(\theta_{t},\omega_{t})=\lim_{t\to\infty}\min_{\omega}\mathcal{Q}(\theta_{t},\omega)$
as well. ∎

See 2

###### Proof.

Firstly, since $\mathcal{Q}(\theta,\omega)$ is a twice-continuously
differentiable, Lipschitz continuous and $\beta$-smooth function, by Prop. 3.4
and Cor. 3.1 in [67], $(\theta_{t},\omega_{t})$ converge to a local minima
$(\hat{\theta},\hat{\omega})$ of $\mathcal{Q}$. Therefore, it is left to show
that $(\hat{\theta},\hat{\omega})$ is also an equilibrium point. We note that
$\mathcal{Q}(\theta,\omega)$ is element-wise convex and $\beta$-smooth. By the
proof of (cf. Nesterov [52], Thm. 2.1.14), we have:

$\displaystyle\mathcal{Q}(\theta_{t+1},\omega_{t})\leq$
$\displaystyle\mathcal{Q}(\theta_{t},\omega_{t})-\eta\|\nabla_{\theta}\mathcal{Q}(\theta_{t},\omega_{t})\|^{2}_{2},$
(12)

where $\eta:=\mu(1-0.5\beta\mu)>0$. By applying the convexity of
$\mathcal{Q}(\theta,\omega_{t})$ (as a function of $\theta$), we have:

$\displaystyle\mathcal{Q}(\theta_{t},\omega_{t})-\mathcal{Q}(\theta^{*}_{t},\omega_{t})\leq$
$\displaystyle\langle\nabla_{\theta}\mathcal{Q}(\theta,\omega_{t}),\theta_{t}-\theta^{*}_{t}\rangle$
(13) $\displaystyle\leq$
$\displaystyle\|\nabla_{\theta}\mathcal{Q}(\theta_{t},\omega_{t})\|_{2}\cdot\|\theta_{t}-\theta^{*}_{t}\|_{2},$

where $\theta^{*}_{t}=\arg\min_{\theta}\mathcal{Q}(\theta,\omega_{t})$ and
$\omega^{*}_{t}=\arg\min_{\omega}\mathcal{Q}(\theta_{t+1},\omega)$. By
combining Eqs. (12) and (13), we have:

$\displaystyle\mathcal{Q}(\theta_{t+1},\omega_{t})\leq\mathcal{Q}(\theta_{t},\omega_{t})-\frac{\eta}{\|\theta_{t}-\theta^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t},\omega_{t})-\min_{\theta}\mathcal{Q}(\theta,\omega_{t})\right)^{2}$
(14)

and similarly, we have:

$\displaystyle\mathcal{Q}(\theta_{t+1},\omega_{t+1})\leq\mathcal{Q}(\theta_{t+1},\omega_{t})-\frac{\eta}{\|\omega_{t}-\omega^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t+1},\omega_{t})-\min_{\omega}\mathcal{Q}(\theta_{t+1},\omega)\right)^{2}$
(15)

In particular, we have:

$\displaystyle\mathcal{Q}(\theta_{t+1},\omega_{t+1})\leq$
$\displaystyle\mathcal{Q}(\theta_{t},\omega_{t})-\frac{\eta}{\|\theta_{t}-\theta^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t},\omega_{t})-\min_{\theta}\mathcal{Q}(\theta,\omega_{t})\right)^{2}$
(16)
$\displaystyle-\frac{\eta}{\|\omega_{t}-\omega^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t+1},\omega_{t})-\min_{\omega}\mathcal{Q}(\theta_{t+1},\omega)\right)^{2}$

Therefore, the sequence $\mathcal{Q}(\theta_{t},\omega_{t})$ is monotonically
decreasing. Since $\mathcal{Q}(\theta_{t},\omega_{t})$ is non-negative, it
converges to some non-negative constant. By Eq. (16), we have:

$\displaystyle\mathcal{Q}(\theta_{t+1},\omega_{t+1})-\mathcal{Q}(\theta_{t},\omega_{t})$
(17) $\displaystyle\geq$
$\displaystyle\frac{\eta}{\|\theta_{t}-\theta^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t},\omega_{t})-\min_{\theta}\mathcal{Q}(\theta,\omega_{t})\right)^{2}+\frac{\eta}{\|\omega_{t}-\omega^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t+1},\omega_{t})-\min_{\omega}\mathcal{Q}(\theta_{t+1},\omega)\right)^{2}$

Since the left hand side tends to zero and the right hand side is lower
bounded by zero, by the sandwich theorem, the sequences
$\frac{\eta}{\|\theta_{t}-\theta^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t},\omega_{t})-\min_{\theta}\mathcal{Q}(\theta,\omega_{t})\right)^{2}$
and
$\frac{\eta}{\|\omega_{t}-\omega^{*}_{t}\|^{2}_{2}}\left(\mathcal{Q}(\theta_{t+1},\omega_{t})-\min_{\omega}\mathcal{Q}(\theta_{t+1},\omega)\right)^{2}$
tend to zero. We note that $\theta_{t}$ and $\omega_{t}$ are convergent
sequences, and therefore, are bounded as well. In addition, we recall that the
sets $\\{\arg\min_{\theta}\mathcal{Q}(\theta,\omega)\mid\omega\in\Omega\\}$
and $\\{\arg\min_{\omega}\mathcal{Q}(\theta,\omega)\mid\theta\in\Theta\\}$ are
well-defined and bounded. Hence, the terms
$\|\theta_{t}-\theta^{*}_{t}\|^{2}_{2}$ and
$\|\omega_{t}-\omega^{*}_{t}\|^{2}_{2}$ are bounded. Thus, we conclude that
the sequences
$\left(\mathcal{Q}(\theta_{t},\omega_{t})-\min_{\theta}\mathcal{Q}(\theta,\omega_{t})\right)^{2}$
and
$\left(\mathcal{Q}(\theta_{t+1},\omega_{t})-\min_{\omega}\mathcal{Q}(\theta_{t+1},\omega)\right)^{2}$
tend to zero. In particular,

$\displaystyle\lim_{t\to\infty}\mathcal{Q}(\theta_{t},\omega_{t})$
$\displaystyle=\lim_{t\to\infty}\min_{\theta}\mathcal{Q}(\theta,\omega_{t})$
(18) $\displaystyle\lim_{t\to\infty}\mathcal{Q}(\theta_{t+1},\omega_{t})$
$\displaystyle=\lim_{t\to\infty}\min_{\omega}\mathcal{Q}(\theta_{t},\omega)$

Since $\mathcal{Q}$ is a Lipschitz continuous function, we have: (i)
$\lim_{t\to\infty}\mathcal{Q}(\theta_{t+1},\omega_{t})=\lim_{t\to\infty}\mathcal{Q}(\theta_{t},\omega_{t})=\mathcal{Q}(\hat{\theta},\hat{\omega})$,
(ii)
$\lim_{t\to\infty}\min_{\theta}\mathcal{Q}(\theta,\omega_{t})=\min_{\theta}\mathcal{Q}(\theta,\hat{\omega})$
and (iii)
$\lim_{t\to\infty}\min_{\omega}\mathcal{Q}(\theta_{t},\omega)=\min_{\omega}\mathcal{Q}(\hat{\theta},\omega)$.
Therefore, we finally conclude that $(\hat{\theta},\hat{\omega})$ is an
equilibrium point of $\mathcal{Q}$. ∎


# Keyphrase Generation for Scientific Articles using GANs

Avinash Swaminathan 1, Raj Kuwar Gupta1, Haimin Zhang2,
Debanjan Mahata 2, Rakesh Gosangi2, Rajiv Ratn Shah1
1MIDAS, IIIT-Delhi, India
2Bloomberg
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

> In this paper, we present a keyphrase generation approach using conditional
> Generative Adversarial Networks (GAN). In our GAN model, the generator
> outputs a sequence of keyphrases based on the title and abstract of a
> scientific article. The discriminator learns to distinguish between machine-
> generated and human-curated keyphrases. We evaluate this approach on
> standard benchmark datasets. Our model achieves state-of-the-art performance
> in generation of abstractive keyphrases and is also comparable to the best
> performing extractive techniques. We also demonstrate that our method
> generates more diverse keyphrases and make our implementation publicly
> available111Code is available at https://github.com/avinsit123/keyphrase-
> gan.

## Introduction

Keyphrases are employed to capture the most salient topics of a long document
and are indexed in databases for convenient retrieval. Researchers annotate
their scientific publications with high quality keyphrases to ensure
discoverability in large scientific repositories. Keyphrases could either be
extractive (part of the document) or abstractive. Keyphrase generation is the
process of predicting both extractive and abstractive keyphrases from a given
document. This process is similar to abstractive summarization but instead of
a summary the models generate keyphrases.

Researchers have achieved considerable success in the field of abstractive
summarization using conditional-GANs (?). There has also been growing interest
in deep learning models for keyphrase generation (?; ?). Inspired by these
advances, we propose a new GAN architecture for keyphrase generation where the
generator produces a sequence of keyphrases from a given document and the
discriminator distinguishes between human-curated and machine-generated
keyphrases.

##  Proposed Adversarial Model

As with most GAN architectures, our model also consists of a generator (G) and
discriminator (D), which are trained in an alternating fashion (?).

Generator \- Given a document $d=\\{x_{1},x_{2},...,x_{n}\\}$, where $x_{i}$
is the $i\textsuperscript{th}$ token, the generator produces a sequence of
keyphrases: $y=\\{y_{1},y_{2},...,y_{m}\\}$, where each keyphrase $y_{i}$ is
composed of tokens ${y_{i}^{1},y_{i}^{2},...,y_{i}^{l_{i}}}$. We employ catSeq
model (?) for the generation process, which uses an encoder-decoder framework:
the encoder being a bidirectional Gated Recurrent Unit (bi-GRU) and the
decoder a forward GRU. To incorporate the out-of-vocabulary words, we use a
copying mechanism (?). We also make use of attention mechanism to help the
generator identify the relevant components of the source text.

Discriminator \- We propose a new hierarchical-attention model as the
discriminator, which is trained to distinguish between human-curated and
machine-generated keyphrases. The first layer of this model consists of $m+1$
bi-GRUs. The first bi-GRU encodes the input document $d$ as a sequence of
vectors: $h=\\{h_{1},h_{2},...,h_{n}\\}$. The other $m$ bi-GRUs, which have
the same weight parameters, encode each keyphrase as a vector:
$\\{k_{1},k_{2},...,k_{m}\\}$. We then use an attention-based approach (?) to
build context vectors $c_{j}$ for each keyphrase, where $c_{j}$ is a weighted
average over $h$. By concatenating $c_{j}$ and $k_{j}$, we get a
contextualized representation $e_{j}=[c_{j};k_{j}]$ of keyphrase $y_{j}$.

The second layer of the discriminator is another bi-GRU which consumes the
document representation $h$ and the keyphrase representations $e$. The final
state of this layer is passed through one fully connected layer ($W_{f}$) and
sigmoid transformation to get the probability that a given keyphrase sequence
is human-curated.

$s_{t}=\begin{cases}GRU(h_{t},s_{t-1}),\textbf{for }1\leq t\leq n\\\
GRU(e_{t-n},s_{t-1}),\textbf{ for }n+1\leq t\leq n+m\\\ \end{cases}$

$R(y_{i})=D(y_{i})=\sigma(W_{f}s_{i+n})$

Figure 1: Schematic of Proposed Discriminator(D)

GAN training \- For a given dataset (S), which contain the documents and
corresponding keyphrases, we first pre-train the generator (G) using Maximum
Likelihood Estimation. We then use this generator to produce machine-generated
keyphrases for all documents in S. These generated keyphrases along with the
curated keyphrases are used to train the first version of the discriminator
(D).

We then employ policy gradient reinforcement learning to train the subsequent
versions of G. We freeze the weight parameters of D and use it for reward
calculation to train a new version of G. The reward for each keyphrase is
obtained from the last $m$ states of the second bi-GRU layer in D (see Figure
1). The gradient update is given as:

$\bigtriangledown R_{G}=\sum_{i=1}^{m}[D(y_{i})-B]\bigtriangledown
log\prod_{j=1}^{l_{i}}G(y_{i}^{j}$ — $y_{i}^{1:j-1},y_{1:i-1},x)$

where B is a baseline obtained by greedy decoding of keyphrase sequence. The
resulting generator is then used to create new training samples for D. This
process is continued till G converges.

## Experiments and Results

We trained the proposed GAN model on KP20k dataset (?) which consists of
567,830 samples for training, 20,000 each for testing and validation. Each
sample consists of an abstract, title, and the corresponding keyphrases of a
scientific article. We evaluated the model on four datasets: Inspec, NUS,
KP20k, and Krapivin, which contain 600, 211, 20,000, and 800 test samples
respectively. For training G, we used Adagrad optimizer with learning rate
$\approx$ 0.0005. We compare our proposed approach against 2 baseline models -
catSeq (?), RL-based catSeq Model (?) in terms of F1 scores as explained in
(?). The results, summarized in Table 1, are broken down in terms of
performance on extractive and abstractive keyphrases.

For extractive keyphrases, our proposed model performs better than the pre-
trained catSeq model on all datasets but is slightly worse than catSeq-RL
except for on Krapivin where it obtains the best F1@M of 0.37. On the other
hand, for abstractive keyphrases, our model performs better than the other two
baselines on three of four datasets suggesting that GAN models are more
effective in generation of keyphrases.

We also evaluated the models in terms of $\alpha$-nDCG@5 (?). The results are
summarized in Table 2. Our model obtains the best performance on three out of
the four datasets. The difference is most prevalent in KP20k, the largest of
the four datasets, where our GAN model (at 0.85) is nearly 5% better than both
the other baseline models.

## Conclusion

In this paper, we propose new GAN architecture for keyphrase generation. The
proposed model obtains state-of-the-art performance in generating abstractive
keyphrases. To our knowledge, this is the first work that applies GANs to
keyphrase generation problem.

Model | Score | Inspec | Krapivin | NUS | KP20k
---|---|---|---|---|---
Catseq(Ex) | F1@5 | 0.2350 | 0.2680 | 0.3330 | 0.2840
| F1@M | 0.2864 | 0.3610 | 0.3982 | 0.3661
catSeq-RL(Ex.) | F1@5 | 0.2501 | 0.2870 | 0.3750 | 0.3100
| F1@M | 0.3000 | 0.3630 | 0.4330 | 0.3830
GAN(Ex.) | F1@5 | 0.2481 | 0.2862 | 0.3681 | 0.3002
| F1@M | 0.2970 | 0.3700 | 0.4300 | 0.3810
catSeq(Abs.) | F1@5 | 0.0045 | 0.0168 | 0.0126 | 0.0200
| F1@M | 0.0085 | 0.0320 | 0.0170 | 0.0360
catSeq-RL(Abs.) | F1@5 | 0.0090 | 0.0262 | 0.0190 | 0.0240
| F1@M | 0.0017 | 0.0460 | 0.0310 | 0.0440
GAN(Abs.) | F1@5 | 0.0100 | 0.0240 | 0.0193 | 0.0250
| F1@M | 0.0190 | 0.0440 | 0.0340 | 0.0450

Table 1: Extractive and Abstractive Keyphrase Metrics

Model | Inspec | Krapivin | NUS | KP20k
---|---|---|---|---
Catseq | 0.87803 | 0.781 | 0.82118 | 0.804
Catseq-RL | 0.8602 | 0.786 | 0.83 | 0.809
GAN | 0.891 | 0.771 | 0.853 | 0.85

Table 2: $\alpha$-nDCG@5 metrics

## References

  * [Chan et al. 2019] Chan, H. P.; Chen, W.; Wang, L.; and King, I.  2019\.  Neural keyphrase generation via reinforcement learning with adaptive rewards.  In ACL.
  * [Clarke et al. 2008] Clarke, C.; Kolla, M.; V. Cormack, G.; Vechtomova, O.; Ashkan, A.; Büttcher, S.; and MacKinnon, I.  2008\.  Novelty and diversity in information retrieval evaluation.  Proc. of the 31st ACM SIGIR 659–666.
  * [Goodfellow et al. 2014] Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; and Bengio, Y.  2014\.  Generative adversarial nets.  In Advances in neural information processing systems, 2672–2680.
  * [Gu et al. 2016] Gu, J.; Lu, Z.; Li, H.; and Li, V. O.  2016\.  Incorporating copying mechanism in sequence-to-sequence learning.  arXiv preprint arXiv:1603.06393.
  * [Luong, Pham, and Manning 2015] Luong, T.; Pham, H.; and Manning, C. D.  2015\.  Effective approaches to attention-based neural machine translation.  In EMNLP.
  * [Meng et al. 2017] Meng, R.; Zhao, S.; Han, S.; He, D.; Brusilovsky, P.; and Chi, Y.  2017\.  Deep keyphrase generation.  arXiv preprint arXiv:1704.06879.
  * [Wang and Lee 2018] Wang, Y., and Lee, H.  2018\.  Learning to encode text as human-readable summaries using generative adversarial networks.  CoRR abs/1810.02851.
  * [Yuan et al. 2018] Yuan, X.; Wang, T.; Meng, R.; Thaker, K.; He, D.; and Trischler, A.  2018\.  Generating diverse numbers of diverse keyphrases.  ArXiv abs/1810.05241.