# Learning Determinantal Point Processes by
Corrective Negative Sampling

Zelda Mariet∗<EMAIL_ADDRESS>
Mike Gartrell†<EMAIL_ADDRESS>
Suvrit Sra∗<EMAIL_ADDRESS>
$*$ Massachusetts Institute of Technology
$\dagger$ Criteo AI Lab

###### Abstract

Determinantal Point Processes (Dpps) have attracted significant interest from
the machine-learning community due to their ability to elegantly and tractably
model the delicate balance between quality and diversity of sets. Dpps are
commonly learned from data using maximum likelihood estimation (MLE). While
fitting observed sets well, MLE for Dpps may also assign high likelihoods to
unobserved sets that are far from the true generative distribution of the
data. To address this issue, which reduces the quality of the learned model,
we introduce a novel optimization problem, _Contrastive Estimation (CE)_ ,
which encodes information about “negative” samples into the basic learning
model. CE is grounded in the successful use of negative information in
machine-vision and language modeling. Depending on the chosen negative
distribution (which may be static or evolve during optimization), CE assumes
two different forms, which we analyze theoretically and experimentally. We
evaluate our new model on real-world datasets; on a challenging dataset, CE
learning delivers a considerable improvement in predictive performance over a
Dpp learned without using contrastive information.

##  1 Introduction

Careful selection of items from a large collection underlies many machine
learning applications. Notable examples include recommender systems,
information retrieval and automatic summarization methods, among others.
Typically, the selected set of items must fulfill a variety of application
specific requirements—e.g., when recommending items to a user, the _quality_
of each selected item is important. This quality must be, however, balanced by
the _diversity_ of the selected items to avoid redundancy within
recommendations.

But balancing quality with diversity is challenging: as the collection size
grows, the number of its subsets grows exponentially. A model that offers an
elegant, tractable way to achieve this balance is a Determinantal Point
Process (Dpp). Concretely, a Dpp models a distribution over subsets of a
ground set $\mathcal{Y}$ that is parametrized by a semi-definite matrix
${\bm{L}}\in\mathbb{R}^{|\mathcal{Y}|\times|\mathcal{Y}|}$, such that for any
$A\subseteq\mathcal{Y}$,

$\Pr(A)\propto\det({\bm{L}}_{A}),$ (1)

where ${\bm{L}}_{A}=[{\bm{L}}_{ij}]_{i,j\in A}$ is the submatrix of ${\bm{L}}$
indexed by $A$. Informally, $\det({\bm{L}}_{A})$ represents the volume
associated with subset $A$, the diagonal entry $L_{ii}$ represents the
importance of item $i$, while entry $L_{ij}=L_{ji}$ encodes similarity between
items $i$ and $j$. Since the normalization constant of (1) is simply
$\sum_{A\subseteq\mathcal{Y}}\det({\bm{L}}_{A})=\det({\bm{L}}+{\bm{I}})$, we
have $\Pr(A)=\det({\bm{L}}_{A})/\det({\bm{L}}+{\bm{I}})$, which suggests why
Dpps may be tractable despite their exponentially large sample space.

The key object defining a Dpp is its kernel matrix ${\bm{L}}$. This matrix may
be fixed _a priori_ using domain knowledge [8], or as is more common in
machine learning applications, learned from observations using maximum
likelihood estimation (MLE) [23, 36]. However, while fitting observed subsets
well, MLE for Dpps may also assign high likelihoods to unobserved subsets far
from the underlying generative distribution [14], since MLE causes the Dpp
model to maximize the determinantal volume of observed subsets without
explicitly minimizing the volume of unobserved subsets. Therefore, the volume
of unobserved subsets may be larger than expected, and MLE-based Dpp models
may thus have modes corresponding to subsets that are close in likelihood, yet
differ in how close they are to the true data distribution. Such confusable
modes reduce the quality of the learned model, hurting predictions, as shown
in Figure 1.

Such concerns when learning generative models over huge sample spaces are not
limited to the area of subset-selection: applications in image and text
generation have been the driving force in developing techniques for generating
high-quality samples. Among their innovations, a particularly successful
technique uses generated samples as “negative samples” to train a
discriminator, which in turn encourages generation of more realistic samples;
this is the key idea behind the Generative Adversarial Nets (GANs) introduced
in [24].

These observations motivate us to investigate the use of Dpp-generated samples
with added perturbations as _negatives_ , which we then incorporate into the
learning task to improve the modeling power of Dpps. Intuitively, negative
samples are those subsets that are far from the true data distribution, but to
which the Dpp erroneously assigns high probability. As there is no closed form
way to generate such idealized negatives, we approximate them via an external
“negative distribution”.

More precisely, we introduce a novel Dpp learning problem that incorporates
samples from a negative distribution into traditional MLE. Our approach
reduces the confusable mode issue associated with MLE for Dpps by augmenting
MLE with a term that explicitly minimizes the volume of unobserved subsets
that are far from the true data distribution (negative samples). While the
focus of our work is on generating the negative distribution _jointly_ with
${\bm{L}}$, we also investigate outside sources of negative information.
Ultimately, our formulation leads to an optimization problem harder than the
original Dpp learning problem; we show that even approximate solutions greatly
improve the performance of the Dpp model when evaluated on concrete tasks,
such as identifying the best item to add to a subset of chosen objects
(_basket-completion_) and discriminating between held-out test data and
randomly generated subsets.

(a) Probabilities of making the right prediction

(b) KL divergences

Figure 1: Results for experiments on a synthetic toy dataset. This toy dataset
was generated by replicating the baskets {1, 2} and {3, 4} 1000 times each. We
randomly select 80% of this dataset for training, and 20% for test. We train
each model to convergence, and then compute the next-item predictive
probabilities for each unique pair, along with the symmetric KL divergence
(over areas of shared support) between the predictive and empirical next-item
distributions. Net symmetric KL divergence is computed by adding the symmetric
KL divergences for each of the two unique baskets. Experiments were run 10
times, with $|\mathcal{A}^{+}|/|\mathcal{A}^{-}|$ set to the optimal value for
each model; $\alpha$ is set to its optimal LowRank value. See Section 3 for
details on the Dyn and Exp negative sampling models. The LR (low-rank Dpp)
model assigns relatively high probabilities to modes that represent incorrect
predictions: as Maximum Likelihood Estimation learning teaches the model to
maximize the volume of observed subsets without explicitly minimizing the
volume of unobserved subsets, volumes of unobserved subsets may be larger than
expected. The Dyn and Exp methods we introduce in Section 3 reduce this
confusable mode issue, resulting in predictive distributions that are closer
to the true distribution and much smaller variances.

#### Contributions.

To our knowledge, this work is the first theoretical or empirical
investigation of augmenting the Dpp learning problem with negative
information.

  * –

Our first main contribution is the Contrastive Estimation (CE) model, which
incorporates negative information through _inferred negatives_ into the
learning task.

  * –

We introduce static and dynamic models for CE and discuss the theoretical and
practical trade-offs of such choices. Static models leverage information that
does not evolve over time, whereas dynamic models draw samples from a negative
distribution that depends on the current model’s parameters; dynamic CE posits
an optimization problem worthy of independent study.

  * –

We show how to learn CE models efficiently, and furthermore show that the
complexity of conditioning a Dpp on a chosen sample can be brought from
$\mathcal{O}(|\mathcal{Y}|^{2})$ to essentially $\mathcal{O}(|\mathcal{Y}|)$.
This helps dynamic CE and removes a major bottleneck in computing next-item
predictions for a set.

Using findings obtained from extensive experiments conducted on small
datasets, we show on a large dataset that CE learning significantly improves
the modeling power of Dpps: CE learning improves Dpp performance for next-item
basket completion, as well as Dpp discriminative power, as evaluated by the
model’s ability to distinguish held-out test data from randomly generated
subsets.

We present a review of related work in Section 2. In Section 3, we introduce
Contrastive Estimation and its dynamic and static variants. We discuss how the
CE problem can be optimized efficiently in Section 4, as well as how Dpp
conditioning for basket-completion predictions can be performed with improved
complexity. In Section 5, we show that CE learning leads to remarkable
empirical improvements of Dpp performance metrics.

##  2 Background and related work

First introduced to model fermion behavior by Macchi [35], Dpps have gained
popularity due to their elegant balancing of quality and subset diversity.
Dpps are studied both for their theoretical properties [30, 8, 1, 29, 22, 17,
31], which include fast sampling [43, 32, 2], and for their machine learning
applications: object retrieval [1], summarization [34, 14], sensor placement
[28], recommender systems [20], neural network compression [37], and minibatch
selection [50].

Gillenwater et al. [23] study Dpp kernel learning via EM, while Mariet & Sra
[36] present a fixed-point method. Dpp kernel learning has leveraged Kronecker
[38] and low-rank [19, 21] structures. Learning guarantees using Dpp graph
properties are studied in [49]. Aside from Tschiatschek et al. [48], Djolonga
et al. [18], who learn a Facility LocatIon Diversity (FLID) distribution (as
well as more complex FLIC and FLDC models) by contrasting it with a “negative”
product distribution, little attention has been given to using negative
samples to learn richer subset-selection models.

Nonetheless, leveraging negative information is a widely used in other
applications. In object detection, negative mining corrects for the skewed
simple-to-difficult negative distribution by training the model on its false
positives [47, 13, 44]. In language modeling, Noise Contrastive Estimation
(NCE) [26], which tasks the model with distinguishing positive samples from
generated negatives, was first applied in [40] and has been instrumental in
Word2Vec [39]. Since then, variants using adaptive noise [16] have been
introduced. NCE is also the method used by Tschiatschek et al. [48] for
subset-selection.

An alternate approach to negative samples within submodular language models
was introduced as Contrastive Estimation in [45, 46]. Negative sampling is
also used in GANs [24], where a generator network competes with a
discriminative network which distinguishes between positives and generated
negatives. An adversarial approach to Contrastive Estimation has been recently
introduced in [9], where ideas from GANs for discrete data are used to
implement an adversarial negative sampler that augments a conventional
negative sampler.

##  3 Learning Dpps with negative samples

Motivated by the similarities between Dpp learning and crucial structured
prediction problems in other ML fields, we introduce an optimization problem
that leverages negative information. We refer to this problem as Contrastive
Estimation (CE) due to its ties to a notion discussed in [45].

###  3.1 Contrastive Estimation

In conventional Dpp learning, we seek to maximize determinantal volumes of
sets drawn from the true distribution $\mu$ (that we wish to model), by
solving the following MLE problem, where samples in the training set
$\mathcal{A}^{+}$ are assumed to be drawn i.i.d.:

$\displaystyle\text{Find }{\bm{L}}\in\mathop{\rm argmax}_{{\bm{L}}\succeq
0}\phi_{\text{MLE}}({\bm{L}})\triangleq$
$\displaystyle\tfrac{1}{|\mathcal{A}^{+}|}\sum_{A\in\mathcal{A}^{+}}\log\det({\bm{L}}_{A})-\log\det({\bm{L}}+{\bm{I}}).$
(2)

We augment problem (2) to incorporate additional information from a _negative_
distribution $\nu$, which we wish to have the Dpp distribution move away from.
The ensuing optimization problem is the main focus of our paper.

######  Definition 1 (Contrastive Estimation).

Given a training set of positive samples $\mathcal{A}^{+}$ on which
$\phi_{\text{MLE}}$ is defined and a negative distribution $\nu$ over
$2^{\mathcal{Y}}$, we call _Contrastive Estimation_ the problem

$\text{Find }{\bm{L}}\in\mathop{\rm argmax}_{{\bm{L}}\succeq
0}\phi_{\text{CE}}({\bm{L}})\triangleq\
\phi_{\text{MLE}}({\bm{L}})-\mathbb{E}_{A\sim\nu}[\log\mathcal{P}_{\bm{L}}(A)],$
(3)

where we write
$\mathcal{P}_{{\bm{L}}}(A)\equiv\det({\bm{L}}_{A})/\det({\bm{L}}+{\bm{I}})$.

The expectation can be approximated by drawing a set of samples
$\mathcal{A}^{-}$ from $\nu$: $\phi_{\text{CE}}$ then becomes111With a slight
abuse of notation, we continue writing $\phi_{\text{CE}}$ despite the sample
approximation to $\mathbb{E}_{A\sim\nu}[\cdot]$.

$\displaystyle\phi_{\text{CE}}({\bm{L}})=$
$\displaystyle\tfrac{1}{|\mathcal{A}^{+}|}\sum_{A\in\mathcal{A}^{+}}\log\mathcal{P}_{\bm{L}}(A)-\tfrac{1}{|\mathcal{A}^{-}|}\sum_{A\in\mathcal{A}^{-}}\log\mathcal{P}_{\bm{L}}(A)$
(4)

If $|\mathcal{A}^{-}|=0$, the CE objective (3) reduces to $\phi_{\text{MLE}}$.
Conversely, $\phi_{\text{MLE}}$ can be viewed as a sample-based approximation
of the value $\mathbb{E}_{A\sim\mu}[\log{\bm{P}}_{\bm{L}}(A)]$, where $\mu$ is
the true distribution generating the samples in $\mathcal{A}^{+}$.
Interestingly, another reformulation of (3) suggests an even broader class of
Dpp kernel learning: indeed, let $y_{A}$ be $\frac{1}{|\mathcal{A}^{+}|}$
(resp. $-\frac{1}{|\mathcal{A}^{-}|}$) for $A\in\mathcal{A}^{+}$ (resp.
$\mathcal{A}^{-}$), and define

$\mathcal{A}=\\{(y_{A},A):A\in\mathcal{A}^{+}\\}\cup\\{(y_{A},A):A\in\mathcal{A}^{-}\\},$

where the $y_{A}$ should be viewed as belonging in $\\{-1,1\\}$ with an
additional normalization coefficient. Then, we can rewrite equation (4) in the
following form

$\phi_{\text{CE}}({\bm{L}})=\\!\\!\\!\sum_{(y_{A},A)\in\mathcal{A}}y_{A}\Big{[}\log\det{\bm{L}}_{A}-\det({\bm{L}}+{\bm{I}})\Big{]}.$
(5)

Formulation (5) suggests the use of a broader scope of continuous labels
$y_{A}$; we do not cover this variation in the present work, but note that (5)
permits the use of _weighted_ samples for learning.

######  Remark 1.

Compared to the traditional Noise Contrastive Estimation (NCE) approach, which
requires full knowledge of the negative distribution, CE does not suffer any
such limitation: we only require an estimate of
$\mathbb{E}_{\nu}[\log\mathcal{P}_{\bm{L}}(A)]$.

######  Remark 2.

Eq. (3) can be made to go to $+\infty$ with pathological negative samples
(i.e. $\mathcal{P}_{\bm{L}}(A^{-})=0$); hence, choosing the negative
distribution is a crucial concern for CE. In practice, we do not observe this
pathological behavior (cf. Section 5).

######  Remark 3.

CE is a non-convex optimization problem, and thus admits the same guarantees
as Dpp MLE learning when learned using Stochastic Gradient Ascent with
decreasing step sizes; however, the convergence rate will depend on the choice
of $\nu$.

Indeed, to fully specify the CE problem one must first choose the negative
distribution $\nu$, or equivalently, choose a procedure to generate negative
samples to obtain (4). We consider below two classes of distributions $\nu$
with considerably different ramifications: dynamic and static negatives; their
analysis is the focus of the next two sections.

###  3.2 Dynamic negatives

In most applications leveraging negative information (e.g., negative mining,
GANs), negative samples evolve over time based on the state of the learned
model. We call any $\nu$ that depends on the state of the model a _dynamic
negative distribution_ : at iteration $k$ of the learning procedure with
kernel estimate ${\bm{L}}_{k}$, we use a $\nu$ parametrized by ${\bm{L}}_{k}$.

More specifically, we focus on the setting where negative samples themselves
are generated by the current Dpp, with the goal of reducing overfitting. Given
a positive sample $A^{+}$, we generate a negative $A^{-}$ by replacing $i\in
A^{+}$ with $j$ that yields a high probability
$\mathcal{P}_{{\bm{L}}_{k}}(A^{+}\backslash\\{i\\}\cup\\{j\\})$ (Alg. 1). We
generate the samples probabilistically rather than via mode maximization so
that a sample $A^{+}$ can lead to different $A^{-}$ negatives when we generate
more negatives than positives.

Algorithm 1 Generate dynamic negative

Input: Positive sample $A^{+}$, current kernel ${\bm{L}}_{k}$

Sample $i\in A^{+}$ prop. to its empirical probability in $\mathcal{A}^{+}$

$A^{-}:=A^{+}\backslash\\{i\\}$

Sample $j$ w.p. proportional to $\mathcal{P}_{{\bm{L}}_{k}}(A^{-}\cup\\{j\\})$

$A^{-}\leftarrow A^{-}\cup\\{j\\}$

return $A^{-}$

As $\nu$ evolves along with ${\bm{L}}_{k}$, the second term of
$\phi_{\text{CE}}$ acts as a moving target that must be continuously estimated
during the learning procedure. For this reason, we choose to optimize
$\phi_{\text{CE}}$ by a two-step procedure described in Alg. 2, similarly to
an alternating maximization approach such as EM.

Algorithm 2 Optimizing dynamic CE

Input: Positive samples $\mathcal{A}^{+}$, initial kernel ${\bm{L}}_{0}$,
maxIter.

$k\leftarrow 1$

while $k++<$ maxIter and not converged do

$\mathcal{A}^{-}\leftarrow\textsc{GenerateDynamicNegatives}({\bm{L}}_{k}$,
$\mathcal{A}^{+}$)

${\bm{L}}_{k+1}\leftarrow\textsc{OptimizeCE}({\bm{L}}_{k},\mathcal{A}^{+},\mathcal{A}^{-})$

end while

return ${\bm{L}}_{k}$

Note that this approach bears strong similarities with GANs, in which both the
generator and discriminator evolve during training (dynamic negatives also
appear in a discussion by Goodfellow [25] as a theoretical tool to analyze the
difference between NCE and GANs).

Once the generated negative $A^{-}$ has been used in an iteration of the
optimization of $\phi_{\text{CE}}$, it is less likely to be sampled
again.222If $A^{-}$ happens to be a false negative (i.e. appears in
$\mathcal{A}^{+}$), $A^{-}$ will be comparatively sampled more frequently as a
positive, and so will contribute on average as a positive sample. Additional
precautions such as the ones mentioned in [9] can also be leveraged if
necessary. Crucially, such dynamic negatives also avoid the problem alluded to
in Remark 2, since by construction they have a non-zero probability under
$\mathcal{P}_{{\bm{L}}_{k}}$ at iteration $k$.

###  3.3 Static negatives

Conversely, we can simplify the optimization problem by considering a _static_
negative distribution: $\nu$ does not depend on the current kernel estimate. A
considerable theoretical advantage of static negatives lies in the simpler
optimization problem: given a static negative distribution $\nu$, the
optimization objective $\phi_{\text{CE}}$ does not evolve during training, and
is amenable to a simple invocation of stochastic gradient descent [10].

######  Theorem 1.

Let $\nu$ be a static distribution over $2^{\mathcal{Y}}$ and let $k>0$ be
such that $k\geq\max\\{|S|:S\in\mathcal{A}^{+}\cup\textup{\,supp}(\nu)\\}$.
Let $K$ be a bounded subspace of all $|\mathcal{Y}|\times|\mathcal{Y}|$
positive semi-definite matrices of rank $k$. Projected stochastic gradient
ascent applied to the CE objective with negative distribution $\nu$ and space
$K$ with step sizes $\eta_{i}$ such that $\sum\eta_{i}=\infty$,
$\sum\eta_{i}^{2}<\infty$ will converge to a critical point.

Note, however, that such distributions may suffer from the fundamental
theoretical issue in Rem. 2, and hence careful attention must be paid to
ensure that the learning algorithm does not converge to a spurious optimum
that assigns a probability ${\bm{P}}_{\bm{L}}(A)=0$ to $A\in\mathcal{A}^{-}$.
In practice, we observed that the local nature of stochastic gradient ascent
iterations was sufficient to avoid such behavior.

Let us now discuss two classical choices for fixed $\nu$.

#### Product negatives.

A common choice of negative distribution in other machine learning areas is
the _product distribution_ , which is the standard “noise” distribution used
in NCE. It is defined by

$\nu(A)=\prod\nolimits_{i\in A}\hat{p}(i)\prod\nolimits_{i\not\in
A}(1-\hat{p}(i))$ (6)

where $\hat{p}(i)$ is the empirical probability of $\\{i\\}$ in
$\mathcal{A}^{+}$. Although [39] reports better results by raising the
$\hat{p}$ to the power $\tfrac{3}{4}$, we did not observe any improvements
when using exponentiated power distributions; for this reason, by _product
negatives_ , we always indicate the baseline distribution (6).

The product distribution is in practice a mismatch for Dpps, as it lacks the
negative association property of Dpps which enables them to model the
repulsive interactions between similar items333Dpps belong to the family of
_Strongly Rayleigh_ measures, which have been shown to verify a broad range of
negatively associated properties; we refer the interested reader to the
fascinating work [42, 6, 7, 3, 4, 5]..

#### Explicit negatives.

Alternatively, we may have prior knowledge of a class of subsets that our
model should _not_ generate. For example, we might know that items $i$ and $j$
are negatively correlated and hence unlikely to co-occur. We may also learn
via user feedback that some generated subsets are inaccurate. We refer to
negatives obtained using such outside information as _explicit negatives_.

A fundamental advantage of explicit negatives is that they allow us to
incorporate prior knowledge and user feedback as part of the learning
algorithm. The ability to incorporate such information, to our knowledge, is
in itself a novel contribution to Dpp learning.

Although such knowledge may be costly and/or only available at rare intervals,
a form of continuous learning that would regularly update the state of our
prior knowledge (and hence $\nu$) would bring the explicit negative
distribution into the realm of dynamic distributions, as described by Alg. 2.

##  4 Efficient learning and prediction

We now describe how the Contrastive Estimation problem for Dpps can be
optimized efficiently. In order to efficiently generate dynamic negatives,
which rely on Dpp conditioning, we additionally generalize the dual
transformation leveraged in [41] to speed up basket-completion tasks with
Dpps. This speed-up impacts the broader use of Dpps, outside of CE learning.

###  4.1 Optimizing $\phi_{\text{CE}}$

We propose to optimize the CE problem by exploiting a low-rank factorization
of the kernel, writing ${\bm{L}}={\bm{V}}{\bm{V}}^{\top}$, where
${\bm{V}}\in\mathbb{R}^{M\times K}$ and $K\leq M$ is the rank of the kernel,
which is fixed a priori.

This factorization ensures that the estimated kernel remains positive semi-
definite, and enables us to leverage the low-rank computations derived in [21]
and refined in [41]. Given the similar forms of the MLE and CE objectives, we
use the traditional stochastic gradient ascent algorithm introduced by [21] to
optimize (3). In the case of dynamic negatives, we re-generate
$\mathcal{A}^{-}$ after each gradient step; less frequent updates are also
possible if the negative generation algorithm is very costly.

We furthermore augment $\phi_{\text{CE}}$ with a regularization term
$R({\bm{V}})$, defined as

$R({\bm{V}})=\alpha\sum\nolimits_{i=1}^{M}\frac{1}{\mu_{i}}\|{\bm{v}}_{i}\|_{2}^{2},$

where $\mu_{i}$ counts the occurrences of $i$ in the training set,
${\bm{v}}_{i}$ is the corresponding row vector of ${\bm{V}}$ and $\alpha>0$ is
a tunable hyperparameter. Note that this is the same regularization as
introduced in [21]. This regularization tempers the strength of
$\|{\bm{v}}_{i}\|_{2}$, a term interpretable as to the popularity of item $i$
[30, 22], based on its _empirical_ popularity $\mu_{i}$. Experimentally, we
observe that adding $R({\bm{V}})$ has a strong impact on the predictive
quality of our model.

The reader may wonder if other approaches to Dpp learning are also applicable
to the CE problem.

######  Remark 4.

Gradient ascent algorithms require that the estimate ${\bm{L}}$ be projected
onto the space of positive semi-definite matrices; however, doing so can lead
to almost-diagonal kernels [23] that cannot model negative interactions.
Riemannian gradient ascent methods were considered, but deemed too
computationally demanding by [36]. Furthermore, the update rule for the fixed-
point approach in [36] does not admit a closed form solution for CE, rendering
it impractical (App. A).

The low-rank formulation allows us to apply CE (as well as NCE, as discussed
in Section 5) to learn large datasets such as the Belgian retail supermarket
dataset (described in Section 5) without prohibitive learning runtimes. We
show below that by leveraging the idea described in [41], the low-rank
formulation can also lead to additional speed ups during prediction.

###  4.2 Efficient conditioning for predictions

Dynamic negatives rely upon conditioning a Dpp on a chosen sample $A$ (see
Alg. 1: $\mathcal{P}_{{\bm{L}}_{k}}(A^{-}\cup\\{j\\})$ can be efficiently
computed for all $j$ by a preprocessing step that conditions ${\bm{L}}_{k}$ on
set $A^{-}$). For this reason, we now describe how low-rank Dpp conditioning
can be significantly sped up.

In [21], conditioning has a cost of $\mathcal{O}(K|\bar{A}|^{2}+|A|^{3})$,
where $\bar{A}=\mathcal{Y}-A$. Since $|\mathcal{Y}|\,\gg\\!|A|$ for many
datasets, this represents a significant bottleneck for conditioning and
computing next-item predictions for a set. We show here that this complexity
can be brought down significantly.

######  Proposition 1.

Given $A\subseteq\\{1,\ldots,M\\}$ and a Dpp of rank $K$ parametrized by
${\bm{V}}$, where ${\bm{L}}={\bm{V}}{\bm{V}}^{\top}$, we can derive the
conditional marginal probabilities in the Dpp parametrization ${\bm{L}}^{A}$
in only $\mathcal{O}(K^{3}+|A|^{3}+K^{2}|A|^{2}+|\bar{A}|K^{2})$ time.

###### Proof.

Let ${\bm{V}}$ be the low-rank parametrization of the Dpp kernel
(${\bm{L}}={\bm{V}}{\bm{V}}^{\top}$) and $A\subseteq\mathcal{Y}$. As in [22],
we first compute the dual kernel ${\bm{C}}={\bm{B}}^{\top}{\bm{B}}$, where
${\bm{B}}={\bm{V}}^{\top}$. We then compute

${\bm{C}}^{A}=({\bm{B}}^{A})^{\top}{\bm{B}}^{A}={\bm{Z}}^{A}{\bm{C}}{\bm{Z}}^{A},$

with
${\bm{Z}}^{A}={\bm{I}}-{\bm{B}}_{A}({\bm{B}}_{A}^{\top}{\bm{B}}_{A})^{-1}{\bm{B}}_{A}^{\top}$,
and where ${\bm{C}}^{A}$ is the Dpp kernel conditioned on the event that all
items in $A$ are observed, and ${\bm{B}}_{A}$ is the restriction of ${\bm{B}}$
to the rows and columns indexed by $A$.

Computing ${\bm{C}}^{A}$ costs $\mathcal{O}(K^{3}+|A|^{3}+K^{2}|A|^{2})$.
Next, following [30], we eigendecompose ${\bm{C}}^{A}$ to compute the
conditional (marginal) probability $P_{i}$ of every possible item $i$ in
$\bar{A}$:

$P_{i}=\sum\nolimits_{n=1}^{K}\tfrac{\lambda_{n}}{\lambda_{n}+1}\left(\tfrac{1}{\sqrt{\lambda_{n}}}{\bm{b}}_{i}^{A}\hat{{\bm{v}}}_{n}\right)^{2}$

where ${\bm{b}}_{i}^{A}$ is column vector for item $i$ in ${\bm{B}}^{A}$ and
$(\lambda_{n}$, $\hat{\bm{v}}_{n})$ are an eigenvalue/vector of
${\bm{C}}^{A}$.

The computational complexity for computing the eigendecomposition is
$\mathcal{O}(K^{3})$, and computing $P_{i}$ for all items in $\bar{A}$ costs
$\mathcal{O}(|\bar{A}|K^{2})$. Therefore, we have an overall computational
complexity of $\mathcal{O}(K^{3}+|A|^{3}+K^{2}|A|^{2}+|\bar{A}|K^{2})$ for
computing next-item conditionals/predictions for the low-rank Dpp using the
dual kernel, which is significantly superior to the typical cost of
$\mathcal{O}(K|\bar{A}|^{2}+|A|^{3})$. ∎

As in most cases $K\ll|\bar{A}|$, this represents a substantial improvement,
allowing us condition in time essentially linear in the size of the item
catalog.

##  5 Experiments

(a) UK dataset
---
|  | Improvement over LowRank
Metric | LowRank | Exp | Dyn
MPR | 80.07 | 3.75 $\pm$ 0.16 | 3.74 $\pm$ 0.16
AUC | 0.57297 | 0.41465 $\pm$ 0.01334 | 0.41467 $\pm$ 0.01339

(b) Belgian dataset
---
| Improvement over LowRank
LowRank | Exp | Dyn
79.42 | 9.58 $\pm$ 0.15 | 9.64 $\pm$ 0.13
0.6162 | 0.3705 $\pm$ 8.569e-5 | 0.3702 $\pm$ 4.447e-5

Table 1: Results over the UK and Belgian datasets. Both explicit and dynamic
CE obtain statistically significant improvements in MPR and AUC metrics,
confirming that CE learning enhances recommender value of the model and its
ability to distinguish data drawn from the target distribution from fake
samples. The impact on precisions@$k$ metrics is not reported as we did not
observe statistically significant deviations from LowRank performance.

We run next-item prediction and AUC-based classification experiments444All
code is implemented in Julia and will be made publicly available upon
publication. on two recommendation datasets for Dpp evaluation: the UK retail
dataset [15], which after clipping all subsets to a maximum size555This allows
us to use a low-rank matrix factorization for the Dpp that scales well in
terms of train and prediction time. of 100, contains 4070 items and 20059
subsets, and the Belgian Retail Supermarket
dataset666http://fimi.ua.ac.be/data/retail.pdf, which contains 88,163 subsets,
of a total of 16,470 unique items [12, 11]. We compare the following
Contrastive Estimation approaches:

  * –

Exp: explicit negatives learned with CE. As to our knowledge there are no
datasets with explicit negative information, we generate approximations of
explicit negatives by removing one item from a positive sample and replacing
it with the least likely item (Algorithm 3).

  * –

Dyn: dynamic negatives learned with CE.

As our work revolves around improving Dpp performance, we focus on the two
following baselines, which are targeted to learning Dpp parametrizations from
data:

  * –

NCE: Noise Contrastive Estimation using product negatives.

  * –

LowRank: the standard low-rank Dpp stochastic gradient ascent algorithm from
[21].

NCE learns a model by contrasting $\mathcal{A}^{+}$ with negatives drawn from
a “noisy” distribution $p_{n}$, training the model to distinguish between sets
drawn from $\mu$ and sets drawn from $p_{n}$. NCE has gained popularity due to
its ability to model distributions $\mu$ with untractable normalization
coefficients, and has been shown to be a powerful technique to improve
submodular recommendation models [48]. NCE learns by maximizing the following
conditional log-likelihood:

$\displaystyle\phi_{\text{NCE}}({\bm{L}})=$
$\displaystyle{\sum_{A\in\mathcal{A}^{+}}\log P(A\in\mathcal{A}^{+}\mid
A)}+{\sum_{A\in\mathcal{A}^{-}}\log P(A\in\mathcal{A}^{-}\mid A)}.$ (7)

The key difference between NCE and CE lies in how negative information is
used: whereas CE learns to assign a low probability to negative subsets, NCE’s
task is more indirect, learning to distinguish positive from negative
examples. As a consequence of NCE’s objective function (Eq. 7), NCE requires
knowledge of the distribution of negative samples, making it difficult to
apply when explicit negative samples are available, but not the form of their
distribution.

In our experiments, we learn the NCE objective with stochastic gradient ascent
for our low-rank model, since
$\nabla\log\Pr(A\in\mathcal{A}^{*}|A,{{\bm{V}}{\bm{V}}^{\top}})$ is given by

$\Big{(}\epsilon^{*}-\Big{(}{1+\frac{|\mathcal{A}^{-}|}{|\mathcal{A}^{+}|}\frac{p_{n}(A)}{\mathcal{P}_{{\bm{V}}{\bm{V}}^{\top}}(A)}}\Big{)}^{-1}\Big{)}\nabla_{\bm{V}}\log\mathcal{P}_{{\bm{V}}{\bm{V}}^{\top}}(A).$
(8)

where $\epsilon^{*}=1$ if $\mathcal{A}^{*}=\mathcal{A}^{+}$ and 0 otherwise.

Algorithm 3 Approximate explicit negative generation

input: Positive sample $A^{+}$

Sample $i\neq j\in A^{+}$ w.p. $p_{i}\propto\widehat{P}(\\{i\\})$

Sample $k\not\in A^{+}$ w.p. $p_{k}\propto 1-\widehat{P}(\\{i,k\\})$.

return $(A^{+}\backslash\\{j\\})\cup\\{k\\}$

This allows us to approximate true explicit negatives, as we use the empirical
data to derive “implausible” sets. Note, however, that when using such
negatives we have no guarantee that objective function will be well behaved,
as opposed to the theoretically grounded dynamic negatives.

###  5.1 Experimental setup

The performance of all methods are compared using standard recommender system
metrics: Mean Percentile Rank (MPR). MPR is a recall-based metric which
evaluates the model’s predictive power by measuring how well it predicts the
next item in a basket, and is a standard choice for recommender systems [27,
33].

Specifically, given a set $A$, let $p_{i,A}=\Pr(A\cup\\{i\\}\mid A)$. The
percentile rank of an item $i$ given a set $A$ is defined as

$\text{PR}_{i,A}=\frac{\sum_{i^{\prime}\not\in A}\mathds{1}(p_{i,A}\geq
p_{i^{\prime},A})}{|\mathcal{Y}\backslash A|}\times 100\%$

The MPR is then computed as

$\text{MPR}=\frac{1}{|\mathcal{T}|}\sum_{A\in\mathcal{T}}\text{PR}_{i,A\backslash\\{i\\}}$

where $\mathcal{T}$ is the set of test instances and $i$ is a randomly
selected element in each set $A$. An MPR of 50 is equivalent to random
selection; a MPR of 100 indicates that the model perfectly predicts the held
out item.

We also evaluate the discriminative power of each model using the AUC metric.
For this task, we generate a set of negative subsets uniformly at random. For
each positive subset $A^{+}$ in the test set, we generate a negative subset
$A^{-}$ of the same length by drawing $|A^{+}|$ samples uniformly at random,
while ensuring that the same item is not drawn more than once for a subset. We
then compute the AUC for the model on these positive and negative subsets,
where the score for each subset is the log-likelihood that the model assigns
to the subset. This task measures the ability of the model to discriminate
between positive subsets (ground-truth subsets) and randomly generated
subsets.

In all experiments, 80% of subsets are used for training; the remaining 20%
served as test; convergence is reached when the relative change in the
validation log-likelihood is below a pre-determined threshold $\epsilon$, set
identically for all methods. All results are averaged over 5 learning trials.

###  5.2 Amazon registries

We conducted an experimental analysis on the largest 7 sub-datasets included
in the Amazon Registry dataset, which has become a standard dataset for Dpp
modeling [23, 36, 21]. Given the small size of these datasets (the largest has
100 items), these experiments serve only to provide insight into the general
behavior of the baselines and CE methods as well as the influence of the
hyperparameters on convergence.

Table 2 reports the average time to convergence for each method. As generating
the dynamic negatives has a high complexity due to Dpp conditioning, Dyn is
2.7x slower than Exp. LowRank is the fastest method, as it does not need to
process any negatives. NCE is by far the most time-consuming.

Table 2: Runtime to convergence (s) on the feeding Amazon registry ($\alpha=1$, $|\mathcal{A}^{-}|/|\mathcal{A}^{+}|=0.5$, $K=30$). Method | LowRank | Exp | Dyn | NCE
---|---|---|---|---
Runtime |  0.83 $\pm$ 0.54 |  2.69 $\pm$ 0.02 |  7.13 $\pm$ 0.28 |  27.59 $\pm$ 2.20

We found that explicit and dynamic CE are not very sensitive to the $\alpha$
and $|\mathcal{A}^{-}|/|\mathcal{A}^{+}|$ hyperparameters. For this reason, in
all further results, we set $\alpha=1$ and
$|\mathcal{A}^{-}|/|\mathcal{A}^{+}|=.5$ in all further experiments. In
previous work on low-rank Dpp learning [21], $\alpha=1$ was found to be a
reasonably optimal value, ensuring a fair comparison between all methods.

Further experiments reporting the MPR, AUC and various precisions for the
Amazon registries are described in App. B.

###  5.3 UK and Belgian Retail Datasets

Following [20], for both the UK and the Belgian dataset, we set the rank $K$
of the kernel to be the size of the largest subset in the dataset (K=100 for
the UK dataset, K=76 for the Belgian dataset): this optimizes memory costs
while still modeling all ground-truth subsets. Based on our results on the
smaller Amazon dataset, we fix $|\mathcal{A}^{-}|/|\mathcal{A}^{+}|=0.5$ and
$\alpha=1$.

Finally, corroborating our timing results on the Amazon registry, we saw that
one iteration of NCE required nearly 11 hours on the Belgian dataset (compared
to 5 minutes for one iteration of CE). For this reason, we remove NCE as a
baseline from all remaining experiments, as it is not feasible in the general
case.

Tables 4 (a) and (b) summarize our results; the negative methods show
significant MPR improvement over LowRank, with both Dyn and Exp performing
almost 10 points higher on the Belgian dataset, and 3 points higher on the UK
dataset. This is a striking improvement, compounded by small standard
deviations confirming that these results are robust to matrix initialization.

We also see a dramatic improvement over LowRank in AUC, with an improvement of
approximately 0.41 for the UK dataset and 0.37 for the Belgian dataset, across
both Dyn and Exp methods. Both Dyn and Exp perform quite well, with an AUC
score of approximately 0.9864 or higher for both models. These results suggest
that for larger datasets, CE can be effective at improving the discriminative
power of the Dpp.

##  6 Conclusion and future work

We introduce the Contrastive Estimation (CE) optimization problem, which
optimizes the difference of the traditional Dpp log-likelihood and the
expectation of the Dpp model’s log-likelihood under a _negative_ distribution
$\nu$. This increases the Dpp’s fit to the data while simultaneously
incorporating inferred or explicit domain knowledge into the learning
procedure.

CE lends itself to intuitively similar but theoretically different variants,
depending on the choice of $\nu$: a static $\nu$ leads to significantly faster
learning but allows spurious optima; conversely, allowing $\nu$ to evolve
along with model parameters limits overfitting at the cost of a more complex
optimization problem. Optimizing dynamic CE is in of itself a theoretical
problem worthy of independent study.

Additionally, we show that low-rank Dpp conditioning complexity can be
improved by a factor of $M$ by leveraging the dual representation of the low-
rank kernel. This not only improves prediction speed on a trained model, but
allows for more efficient dynamic negative generation.

Experimentally, we show that CE with dynamic and explicit negatives provide
comparable, significant improvements in the predictive performance of Dpps, as
well as on the learned Dpp’s ability to discriminate between real and randomly
generated subsets.

Our analysis also raises both theoretical and practical questions: in
particular, a key component of future work lies in better understanding how
explicit domain knowledge can be incorporated into the generating logic for
both dynamic and static negatives. Furthermore, the CE formulation in Eq. (5)
suggests the possibility of using continuous labels for weighted samples
within CE.

#### Acknowledgements.

This work was partially supported by a Criteo Faculty Research Award, and NSF-
IIS-1409802.

## References

  * Affandi et al. [2014] Affandi, R., Fox, E., Adams, R., and Taskar, B.  Learning the parameters of Determinantal Point Process kernels.  In _ICML_ , 2014.
  * Anari et al. [2016] Anari, Nima, Gharan, Shayan Oveis, and Rezaei, Alireza.  Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes.  In _29th Annual Conference on Learning Theory_ , volume 49 of _Proceedings of Machine Learning Research_ , pp. 103–115, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.
  * Borcea & Brändén [2009a] Borcea, Julius and Brändén, Petter.  The Lee-Yang and Pólya-Schur programs I Linear operators preserving stability.  _Inventiones mathematicae_ , 177(3), 2009a.
  * Borcea & Brändén [2009b] Borcea, Julius and Brändén, Petter.  The Lee-Yang and Pólya-Schur programs II Theory of stable polynomials and applications.  _Communications on Pure and Applied Mathematics_ , 62(12), 2009b.
  * Borcea & Brändén [2010] Borcea, Julius and Brändén, Petter.  Multivariate Pólya–Schur classification problems in the Weyl algebra.  _Proceedings of the London Mathematical Society_ , 101(1), 2010.
  * Borcea et al. [2009a] Borcea, Julius, Brändén, Petter, and Liggett, Thomas.  Negative dependence and the geometry of polynomials.  _Journal of the American Mathematical Society_ , 22(2), 2009a.
  * Borcea et al. [2009b] Borcea, Julius, Brändén, Petter, and Shapiro, Boris.  Classification of hyperbolicity and stability preservers: the multivariate Weyl algebra case.  _arXiv preprint math.CA/0606360_ , 2009b.
  * Borodin [2009] Borodin, Alexei.  Determinantal Point Processes.  _arXiv:0911.1153_ , 2009.
  * Bose et al. [2018] Bose, Avishek, Ling, Huan, and Cao, Yanshuai.  Adversarial contrastive estimation.  _arXiv preprint arXiv:1805.03642_ , 2018.
  * Bottou [1998] Bottou, Léon.  On-line learning in neural networks.  Cambridge University Press, 1998.
  * Brijs [2003] Brijs, Tom.  Retail market basket data set.  In _Workshop on Frequent Itemset Mining Implementations (FIMI’03)_ , 2003.
  * Brijs et al. [1999] Brijs, Tom, Swinnen, Gilbert, Vanhoof, Koen, and Wets, Geert.  Using association rules for product assortment decisions: A case study.  In _SIGKDD_. ACM, 1999.
  * Canévet & Fleuret [2014] Canévet, Olivier and Fleuret, Francois.  Efficient Sample Mining for Object Detection.  In _ACML_ , JMLR: Workshop and Conference Proceedings, 2014.
  * Chao et al. [2015] Chao, Wei-Lun, Gong, Boqing, Grauman, Kristen, and Sha, Fei.  Large-margin Determinantal Point Processes.  In _Uncertainty in Artificial Intelligence (UAI)_ , 2015.
  * Chen [2012] Chen, D.  Data mining for the online retail industry: A case study of rfm model-based customer segmentation using data mining.  _Journal of Database Marketing and Customer Strategy Management_ , 19(3), August 2012.
  * Chen et al. [2017] Chen, Long, Yuan, Fajie, Jose, Joemon M., and Zhang, Weinan.  Improving negative sampling for word representation using self-embedded features.  _CoRR_ , abs/1710.09805, 2017.
  * Decreusefond et al. [2015] Decreusefond, Laurent, Flint, Ian, Privault, Nicolas, and Torrisi, Giovanni Luca.  Determinantal Point Processes, 2015.
  * Djolonga et al. [2016] Djolonga, Josip, Tschiatschek, Sebastian, and Krause, Andreas.  Variational inference in mixed probabilistic submodular models.  In _NIPS_ , 2016.
  * Dupuy & Bach [2016] Dupuy, Christophe and Bach, Francis.  Learning Determinantal Point Processes in sublinear time, 2016.
  * Gartrell et al. [2016] Gartrell, Mike, Paquet, Ulrich, and Koenigstein, Noam.  Bayesian low-rank Determinantal Point Processes.  In _RecSys_ , 2016.
  * Gartrell et al. [2017] Gartrell, Mike, Paquet, Ulrich, and Koenigstein, Noam.  Low-rank factorization of Determinantal Point Processes.  In _AAAI_ , 2017.
  * Gillenwater [2014] Gillenwater, J.  _Approximate Inference for Determinantal Point Processes_.  PhD thesis, University of Pennsylvania, 2014.
  * Gillenwater et al. [2014] Gillenwater, J., Kulesza, A., Fox, E., and Taskar, B.  Expectation-maximization for learning Determinantal Point Processes.  In _NIPS_ , 2014.
  * Goodfellow et al. [2014] Goodfellow, Ian, Pouget-Abadie, Jean, Mirza, Mehdi, Xu, Bing, Warde-Farley, David, Ozair, Sherjil, Courville, Aaron, and Bengio, Yoshua.  Generative adversarial nets.  In _NIPS_ , 2014.
  * Goodfellow [2014] Goodfellow, Ian J.  On distinguishability criteria for estimating generative models, 2014\.
  * Gutmann & Hyvärinen [2012] Gutmann, Michael U. and Hyvärinen, Aapo.  Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics.  _J. Mach. Learn. Res._ , 13, February 2012.  ISSN 1532-4435.
  * Hu et al. [2008] Hu, Yifan, Koren, Yehuda, and Volinsky, Chris.  Collaborative filtering for implicit feedback datasets.  In _ICDM_ , 2008.
  * Krause et al. [2008] Krause, Andreas, Singh, Ajit, and Guestrin, Carlos.  Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies.  _JMLR_ , 9, 2008.
  * Kulesza [2013] Kulesza, A.  _Learning with Determinantal Point Processes_.  PhD thesis, University of Pennsylvania, 2013.
  * Kulesza & Taskar [2012] Kulesza, A. and Taskar, B.  _Determinantal Point Processes for machine learning_ , volume 5.  Foundations and Trends in Machine Learning, 2012.
  * Lavancier et al. [2015] Lavancier, Frédéric, Møller, Jesper, and Rubak, Ege.  Determinantal Point Process models and statistical inference.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 77(4), 2015.
  * Li et al. [2016] Li, Chengtao, Jegelka, Stefanie, and Sra, Suvrit.  Fast dpp sampling for nystrom with application to kernel methods.  In _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pp. 2061–2070, New York, New York, USA, 20–22 Jun 2016. PMLR.
  * Li et al. [2010] Li, Yanen, Hu, Jia, Zhai, ChengXiang, and Chen, Ye.  Improving one-class collaborative filtering by incorporating rich user information.  In _CIKM_ , 2010.
  * Lin & Bilmes [2012] Lin, H. and Bilmes, J.  Learning mixtures of submodular shells with application to document summarization.  In _UAI_ , 2012.
  * Macchi [1975] Macchi, O.  The coincidence approach to stochastic point processes.  _Adv. Appl. Prob._ , 7(1), 1975.
  * Mariet & Sra [2015] Mariet, Zelda and Sra, Suvrit.  Fixed-point algorithms for learning Determinantal Point Processes.  In _ICML_ , 2015.
  * Mariet & Sra [2016a] Mariet, Zelda and Sra, Suvrit.  Diversity networks.  _Int. Conf. on Learning Representations (ICLR)_ , 2016a.
  * Mariet & Sra [2016b] Mariet, Zelda and Sra, Suvrit.  Kronecker Determinantal Point Processes.  In _NIPS_ , 2016b.
  * Mikolov et al. [2013] Mikolov, Tomas, Sutskever, Ilya, Chen, Kai, Corrado, Greg S, and Dean, Jeff.  Distributed representations of words and phrases and their compositionality.  In _NIPS_. 2013.
  * Mnih & Teh [2012] Mnih, Andriy and Teh, Yee Whye.  A fast and simple algorithm for training neural probabilistic language models.  In _ICML_ , 2012.
  * Osogami et al. [2018] Osogami, Takayuki, Raymond, Rudy, Goel, Akshay, Shirai, Tomoyuki, and Maehara, Takanori.  Dynamic Determinantal Point Processes.  In _AAAI_ , 2018.
  * Pemantle [2000] Pemantle, Robin.  Towards a theory of negative dependence.  _Journal of Mathematical Physics_ , 41(3), 2000.
  * Rebeschini & Karbasi [2015] Rebeschini, Patrick and Karbasi, Amin.  Fast mixing for discrete point processes.  In _Proceedings of The 28th Conference on Learning Theory_ , volume 40 of _Proceedings of Machine Learning Research_ , pp. 1480–1500, Paris, France, 03–06 Jul 2015. PMLR.
  * Shrivastava et al. [2016] Shrivastava, Abhinav, Gupta, Abhinav, and Girshick, Ross.  Training region-based object detectors with online hard example mining.  In _CVPR_ , 2016.
  * Smith & Eisner [2005a] Smith, Noah A. and Eisner, Jason.  Guiding unsupervised grammar induction using contrastive estimation.  In _In Proc. of IJCAI Workshop on Grammatical Inference Applications_ , 2005a.
  * Smith & Eisner [2005b] Smith, Noah A. and Eisner, Jason.  Contrastive estimation: Training log-linear models on unlabeled data.  In _ACL_ , ACL ’05, 2005b.
  * Sung [1996] Sung, Kah Kay.  _Learning and Example Selection for Object and Pattern Detection_.  PhD thesis, Massachusetts Institute of Technology, 1996.
  * Tschiatschek et al. [2016] Tschiatschek, Sebastian, Djolonga, Josip, and Krause, Andreas.  Learning probabilistic submodular diversity models via noise contrastive estimation.  In _AISTATS_ , 2016.
  * Urschel et al. [2017] Urschel, John, Brunel, Victor-Emmanuel, Moitra, Ankur, and Rigollet, Philippe.  Learning Determinantal Point Processes with moments and cycles.  In _ICML_ , 2017.
  * Zhang et al. [2017] Zhang, Cheng, Kjellström, Hedvig, and Mandt, Stephan.  Stochastic learning on imbalanced data: Determinantal Point Processes for mini-batch diversification.  _CoRR_ , abs/1705.00607, 2017.

##  Appendix A Contrastive Estimation with the Picard iteration

Letting $\beta=|\mathcal{A}^{+}|-|\mathcal{A}^{-}|\geq 0$ and writing
${\bm{U}}_{A}$ as the $M\times|A|$ indicator matrix such that
${\bm{L}}_{A}={\bm{U}}_{A}^{\top}{\bm{L}}{\bm{U}}_{A}$, we have

$\displaystyle\phi({\bm{L}})\propto$
$\displaystyle\underbrace{-\beta\log\det({\bm{I}}+{\bm{X}})+\sum_{A\in\mathcal{A}^{+}}\log\det({\bm{U}}_{A}^{\top}{\bm{X}}^{-1}{\bm{U}}_{A})}_{f\text{
convex}}$
$\displaystyle+\underbrace{\beta\log\det({\bm{X}})-\sum_{A\in\mathcal{A}^{-}}\log\det({\bm{U}}_{A}^{\top}{\bm{X}}^{-1}{\bm{U}}_{A})}_{g\text{
concave}}$

where the convexity/concavity results follow immediately from [36, Lemma 2.3].
Then, the update rule $\nabla f({\bm{L}}_{k+1})=-\nabla g({\bm{L}}_{k})$
requires

$\displaystyle\beta$
$\displaystyle{\bm{L}}_{k+1}+\sum_{A\in\mathcal{A}^{-}}{\bm{L}}_{k+1}{\bm{U}}_{A}({\bm{U}}_{A}^{\top}{\bm{L}}_{k+1}{\bm{U}}_{A})^{-1}{\bm{U}}_{A}^{\top}{\bm{L}}_{k+1}$
$\displaystyle\leftarrow\beta({\bm{I}}+{\bm{L}}_{k}^{-1})^{-1}+\sum_{A\in\mathcal{A}^{+}}{\bm{L}}_{k}{\bm{U}}_{A}({\bm{U}}_{A}^{\top}{\bm{L}}_{k}{\bm{U}}_{A})^{-1}{\bm{U}}_{A}^{\top}{\bm{L}}_{k}$

which cannot be evaluated due to the $\sum_{A\in\mathcal{A}^{-}}$ term.

##  Appendix B Amazon Baby registries experiments

###  B.1 Amazon Baby Registries description

Table 3: Description of the Amazon Baby registries dataset.
Registry | $M$ | train size | test size
---|---|---|---
health | 62 | 5278 | 1320
bath | 100 | 5510 | 1377
apparel | 100 | 6482 | 1620
bedding | 100 | 7119 | 1780
diaper | 100 | 8403 | 2101
gear | 100 | 7089 | 1772
feeding | 100 | 10,090 | 2522

###  B.2 Experimental results

In Tab. 4(a), we compare the performance of the various algorithms with rank
$K=30$. The regularization strength $\alpha$ is set to its optimal value for
the LowRank algorithm, and $|\mathcal{A}^{-}|/|\mathcal{A}^{+}|=1/2$. This
allows us to compare the LR algorithm to its “augmented” negative versions
without hyper-parameter tuning. As Prod performs much worse than LowRank, it
is not included in further experiments.

We evaluate the precision at $k$ as

$p@k=\frac{1}{|\mathcal{T}|}\sum_{A\in\mathcal{T}}\frac{1}{|A|}\sum_{i\in
A}\mathds{1}\big{[}\text{rank}(i\mid A\backslash\\{i\\})\leq k\big{]}.$

Table 4: MPR, p@$k$, and AUC values for LowRank, and baseline improvement over
LowRank for other methods. Positive values indicate the algorithm performs
better than LowRank, and bold values indicate improvement over LowRank that
lies outside the standard deviation. Experiments were run 5 times, with
$|\mathcal{A}^{+}|/|\mathcal{A}^{-}|=\frac{1}{2}$; $\alpha$ is set to its
optimal LowRank value.

|  | Improvement over LowRank
---|---|---
Metric | LowRank | Dyn | Exp | NCE
MPR | 70.50 | 0.92 $\pm$ 0.56 | 0.68 $\pm$ 0.62 | 0.86 $\pm$ 0.55
p@1 | 9.96 | 0.67 $\pm$ 0.75 | 0.58 $\pm$ 0.76 | 0.20 $\pm$ 1.75
p@5 | 25.36 | 1.04 $\pm$ 0.82 | 0.78 $\pm$ 0.67 | 0.67 $\pm$ 1.09
p@10 | 36.50 | 1.39 $\pm$ 0.85 | 1.13 $\pm$ 0.79 | 0.97 $\pm$ 1.18
p@20 | 51.22 | 1.38 $\pm$ 0.97 | 1.28 $\pm$ 1.11 | 1.35 $\pm$ 1.20
AUC | 0.630 | 0.027 $\pm$ 0.017 | 0.026 $\pm$ 0.016 | 0.009 $\pm$ 0.017

Compared to traditional SGA methods, algorithms that use inferred negatives
perform (Prod excepted) better across all metrics and datasets. Dyn and Exp
provide consistent improvements compared to the other methods, whereas NCE
shows a higher variance and slightly worse performance. Improvements observed
using Dyn and Exp are larger than the loss in performance due to going from
full-rank to low-rank kernels reported in [21].

Finally, we also compared all methods when tuning both the regularization
$\alpha$ and the negative to positive ratio
${|\mathcal{A}^{-}|}/{|\mathcal{A}^{+}|}$, but did not see any significant
improvements. As this suggests there is no need to do additional hyper-
parameter tuning when using CE, we fix
$\frac{|\mathcal{A}^{-}|}{|\mathcal{A}^{+}|}=\frac{1}{2}$ for all experiments.


# The Human Factor in AI Red Teaming: Perspectives from Social and
Collaborative Computing

Alice Qian Zhang  0009-0005-6407-6981<EMAIL_ADDRESS>Carnegie Mellon
UniversityPittsburghPennsylvaniaUnited States ,  Ryland Shaw
0009-0008-6123-1781<EMAIL_ADDRESS>Microsoft ResearchNew York
CityNew YorkUnited States ,  Jacy Reese Anthis  0000-0002-4684-348X
<EMAIL_ADDRESS>University of ChicagoChicagoIllinoisUnited States ,
Ashlee Milton  0000-0002-0320-6122<EMAIL_ADDRESS>University of
MinnesotaMinneapolisMinnesotaUnited States ,  Emily Tseng  0000-0003-1087-1101
<EMAIL_ADDRESS>Microsoft ResearchUnited States ,  Jina Suh
0000-0002-7646-5563<EMAIL_ADDRESS>Microsoft
ResearchRedmondWashingtonUnited States ,  Lama Ahmad<EMAIL_ADDRESS>OpenAISan FranciscoCaliforniaUnited States ,  Ram Shankar Siva Kumar
<EMAIL_ADDRESS>MicrosoftRedmondWashingtonUnited States ,  Julian
Posada  0000-0002-3285-6503<EMAIL_ADDRESS>Yale UniversityNew
HavenConnecticutUnited States ,  Benjamin Shestakofsky  0000-0002-6733-1942
<EMAIL_ADDRESS>University of PennsylvaniaPhiladelphiaPennsylvaniaUnited
States ,  Sarah T. Roberts  0000-0001-8953-1470<EMAIL_ADDRESS>University of California Los AngelesLos AngelesCaliforniaUnited States and
Mary L. Gray<EMAIL_ADDRESS>Microsoft ResearchCambridgeMassachusettsUnited
States

(2024)

###### Abstract.

Rapid progress in general-purpose AI has sparked significant interest in “red
teaming,” a practice of adversarial testing originating in military and
cybersecurity applications. AI red teaming raises many questions about the
human factor, such as how red teamers are selected, biases and blindspots in
how tests are conducted, and harmful content’s psychological effects on red
teamers. A growing body of HCI and CSCW literature examines related
practices—including data labeling, content moderation, and algorithmic
auditing. However, few, if any, have investigated red teaming itself. This
workshop seeks to consider the conceptual and empirical challenges associated
with this practice, often rendered opaque by non-disclosure agreements. Future
studies may explore topics ranging from fairness to mental health and other
areas of potential harm. We aim to facilitate a community of researchers and
practitioners who can begin to meet these challenges with creativity,
innovation, and thoughtful reflection.

artificial intelligence, red teaming, AI red teaming, labor, fairness, well-
being, security, AI safety, AI ethics

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXXXXXX††ccs: Human-
centered computing Collaborative and social computing††ccs: Social and
professional topics Computing industry††ccs: Social and professional topics
Computing / technology policy

##  1\. Introduction

As machine learning applications—particularly those driven by large language
models—have become increasingly widespread, researchers have examined how
these technologies may be integrated into our lives while also adhering to
responsible artificial intelligence (AI) standards formulated by governments,
large technology organizations, and researchers (House, 2023). Given AI
systems’ broad application and relatively unpredictable nature, it is
challenging for designers and developers to anticipate all possible use cases
and consequences. For example, generative AI tools have been shown to
reproduce implicit stereotypes about gender and ethnicity (Gillespie, 2024;
Bolukbasi et al., 2016). This follows other AI blunders, such as Google’s
image recognition system tagging photographs of Black people as “gorillas”
(Barr, 2015) and Microsoft’s Tay chatbot engaging in Holocaust denial
(Schwartz, 2019). These incidents echo a long history of tech companies
unintentionally reifying material and representational harms that researchers
and policymakers have worked to counteract (Barocas et al., 2017).

The harms caused by these AI systems have inspired numerous efforts at “red
teaming,” with leading AI companies such as OpenAI, Google, Microsoft, and
Anthropic adopting red teams into their responsible AI initiatives. Red
teaming has been defined as “a structured process for probing AI systems and
products for the identification of harmful capabilities, outputs, or
infrastructural threats” (Forum, 2024). However, what constitutes red teaming
changes as the practice evolves, with its definition and methods being shaped
by advancements and insights from various fields. For example, Anthropic is
using crowd workers to test AI systems by trying to make them generate harmful
content (Ganguli et al., 2022). In red teams, users – from domain experts in
cybersecurity and algorithmic fairness to international crowd workers – take
on a pseudo-adversarial role in deliberately producing harmful outputs.

While most red teaming initiatives in AI began recently, there is substantial
precedent in other domains. The term was first used to describe military
scenario testing, formally established as a practice by the US government
during the Cold War (Zenko and Haass, 2015). More recently, it has appeared in
computer security (Zenko, 2015; Abbass et al., 2011; Wood and Duggan, 2000).
Today, red teamers use AI systems to generate outputs that are then subject to
review–an activity that CSCW scholars have previously examined through the
lenses of social computing, content moderation, and data labeling (Roberts,
2019; Gillespie, 2018; Gray and Suri, 2019). In this workshop, we hope to draw
on scholarship on the history of red teaming to understand and inform the use
of red teaming for AI.

Red teaming’s scope differs across applications, and the working practices and
occupational hazards related to red teaming are likely to vary widely
depending on the labor arrangements in which it is embedded. Red team
initiatives rely on contracted experts, permanent employees, volunteers, crowd
workers, and end-users (humane intelligence et al., 2024; Ganguli et al.,
2022). Red teamers’ identities and organizational contexts may influence AI
systems in subtle and unexpected ways. Thus, it is imperative to map the
sociotechnical ecology of red teaming–the people doing the work, their methods
and means, and their organizational settings. The varying skills users bring
to red teaming (e.g., resilience) can also affect their ability to cope with
challenges related to productive model assessment and psychological pressures.

Some AI red teamers search for bugs and security risks, but others provoke AI
systems to generate content that may be racist, sexist, queerphobic, or have
other prejudicial implications. Throughout this process, they expose
themselves to the harmful content they help create, with the goal of reducing
its availability and effects on end-users of the technology. Repeated exposure
to such content has been shown to cause psychological harm to crowd workers
and content moderators (Steiger et al., 2022; Michel, 2018; Ruckenstein and
Turunen, 2020; Dwoskin, 2019; Arsht and Etcovitch, 2018). We recognize the
importance of centering red teamers’ well-being in future research (Miceli et
al., 2022).

In this workshop, we will explore the evolving landscape of AI red teaming,
drawing from both contemporary and historical perspectives. We will explore
stakeholder roles in AI red teaming, identifying practitioner needs and
addressing worker safety and well-being concerns. Through our discussions and
collaborative activities, we aim to achieve two primary outcomes: 1) establish
an AI red teaming research network, fostering interdisciplinary collaboration
among researchers and practitioners, and 2) collate key insights into an
informal post-workshop report for practitioners and researchers.

##  2\. Workshop Goals and Themes

This workshop aims to outline the practice of AI red teaming, drawing on
historical insights to understand its trajectory and structure. We prioritize
understanding the humans involved in AI red teaming and how their roles
influence the development of AI systems. Additionally, we seek to leverage
past research to address safety concerns and identify academic disciplines and
methodologies pertinent to analyzing red teaming practices. We will focus on
the following themes:

  1. (1)

Conceptualization of Red Teaming Inspired by Robert Soden and colleagues’
(Soden et al., 2021) argument to ground CSCW in history, we aim to understand
the trajectory of red teaming as a socio-technical, collaborative practice.
This theme invites participants to engage in deeper discussions about red
teaming complexities and consider the impact of conducting research in this
space (Olteanu et al., 2023). What constitutes red teaming, and how has its
conceptualization evolved over time? What role does red teaming play within
broader frameworks of Responsible AI, and how can decentralized or external
approaches contribute to its effectiveness?

  2. (2)

Labor of Red Teaming This theme explores the human aspects of AI red teaming,
investigating stakeholders involved in the practice and their impact on
shaping AI systems to inform future practices and policies. By examining the
labor arrangements and power dynamics involved in red teaming practices (e.g.,
inequities in organizational practices of tech labor (Shestakofsky, 2017)), we
seek to uncover historical parallels and contemporary methodologies that
illuminate red teamers’ roles and operational frameworks. What can historical
precedents teach us about red teaming as a labor practice? How can we employ
diverse methodologies to investigate red teamers’ labor structures, including
recruitment procedures and institutional commitments?

  3. (3)

Well-being of and Harms Against Red Teamers Building on the theme of labor,
this theme focuses on the safety and well-being of red teamers. We will
identify strategies and interventions to mitigate potential harms from
exposure to harmful content during red teaming activities. By addressing these
critical concerns and integrating recommendations to prioritize worker well-
being (e.g., (Pendse et al., 2024)), we aim to foster a culture of well-being
within the AI red teaming community. How can organizations build safeguards
and design interventions to protect red teamers from potential harm? How can
these strategies be implemented to ensure the safety and well-being of red
teamers in their roles?

##  3\. Workshop Activities

We propose a one-day hybrid workshop that participants can attend in person at
CSCW 2024 or virtually to include as many perspectives as possible. We will
account for conference and meal breaks in the final schedule. We aim to
include the following activities in the workshop:

  * •

Introduction (15 minutes): Workshop organizers will welcome participants,
introduce themselves, and provide an overview of the workshop, including the
details of the objectives and planned activities.

  * •

Red Teaming Exercise (45 minutes): We will have two red teaming exercises led
by workshop organizers. First, participants will be grouped by areas of
expertise (e.g., fairness (Anthis et al., 2024), mental health (Pendse et al.,
2024)) accompanied by a workshop organizer per group. Participants will be
given a brief walkthrough of prompt injection via the Gandalf platform in
which the goal is to force the system to share a secret password. Then, each
group will be instructed to formulate and input prompts into a popular LLM
(e.g., ChatGPT, Claude) that produces harmful system behavior while being
mindful of usage policies. Participants will produce a one-page “report” of
their findings, emulating an open-ended task assigned to expert red teamers.

  * •

Panel Discussion (1 hour): To provide further background for this new area of
CSCW inquiry, our organizing team includes senior scholars and practitioners
from diverse sectors who will speak on challenges in red teaming. These senior
workshop organizers will briefly discuss their perspectives on red teaming
guided by prepared and live questions.

  * •

Artifact Development (2 hours): In this activity, participants will work in
small groups to develop preliminary artifacts for later publication. Groups of
participants will be no larger than five people, and each will be assigned a
predefined workshop theme or theme that surfaced during the workshop.
Participants can choose to develop artifacts in one of two ways:

    * –

Research Agenda: The first option is to ideate toward a research agenda
linking relevant prior research to workshop themes (e.g., organizational
practices of tech labor (Shestakofsky, 2017), prioritizing worker well-being
(Pendse et al., 2024), and critically reflecting on research impacts (Olteanu
et al., 2023)).

    * –

ToolKit: The second option is to ideate towards a toolkit that may be
leveraged by red teaming practitioners relevant to the assigned theme (e.g.,
for harms, a toolkit might include activities to consider well-being).

After 90 minutes, groups working on the same theme will discuss and organize
their findings in a shared online space (e.g., Miro board).

  * •

Shareouts (1 hour): To synthesize key findings and common themes across the
artifact development activity, each group will have 10-15 minutes to present
their findings, while others can provide feedback.

  * •

Closing Remarks (15 minutes): An organizer will convene to recap key insights
gleaned from the workshop activities. Those interested in refining the
artifacts created will have their information collected through a co-
authorship interest form. We will emphasize that all contributions made during
the workshop will be duly recognized in any resulting publications through
acknowledgment if not co-authorship. Following this, there will be an
opportunity for additional discussions and to formally conclude the workshop.

##  4\. Hybrid Workshop Logistics

In line with our workshop’s goal of incorporating diverse perspectives, we are
fully dedicated to offering a hybrid experience to enhance accessibility.
Before the workshop, participants will be asked to bring a device capable of
accessing online platforms listed below as these tools will be essential for
facilitating the hybrid experience.

  * •

Website: The organizers will create a website for the workshop, including
information about the workshop, a call for participation, an expression of
interest form, the workshop schedule, and any other relevant information.

  * •

Discord: We will create a Discord server for the workshop to facilitate
participants’ interactions before, during, and after the workshop. We will ask
participants to introduce themselves and share why they are attending the
workshop on the server. The organizers will monitor the server to foster
discussions and keep participants engaged.

  * •

Zoom Video Conferencing: All activities will be broadcast through Zoom to
allow virtual participants to engage in the activities and discussions. The
organizers will be on Zoom and will monitor the chat to help facilitate
interactions between in-person and virtual participants. We will utilize
breakout rooms to pair in-person and virtual participants to promote
discussion between modalities.

  * •

Online Platforms: To support the sharing and recording of ideas during the
discussion activities, we will use Google Documents and Miro to allow workshop
participants to take notes. Both of these software are available online,
allowing virtual participants to access the materials.

##  5\. Call for Participants

We welcome 20-30 academics and practitioners who are working, researching, or
interested in red teaming from fields including but not limited to CSCW, AI,
HCI, sociology, communications, philosophy, psychology, and labor studies. To
express interest in attending, individuals must submit a statement of interest
that will include a summary of their motivation for attending the workshop,
themes they are interested in exploring, and a short biography via a Google
form. The submissions will be reviewed by the workshop organizers and accepted
based on the diversity of perspectives, given the focus on bringing together
academic and practitioner viewpoints and approaches from diverse domains. We
will advertise our workshop through social media and academic mailing lists
and reach out to organizations or special interest groups that may be
interested in the topic of our workshop.

##  6\. Workshop Outcomes

In addition to providing a venue for those already engaged with red teaming,
we envision this workshop as an opportunity to highlight red teaming and its
relevance to others in CSCW. Thus, the expected outcomes of this workshop
include the following:

  * •

AI Red Teaming Research Network: We will bring together interdisciplinary
researchers and practitioners to critically examine the current state of red
teaming and how practitioners can support the humans who perform it. Through
the exchange of experiences and ideas, we expect that collaborations will be
formed, creating a network of researchers who will continue to work together
on the topic.

  * •

Synthesis of Workshop Findings: Building on the collaborative efforts during
the workshop activities, we aim to synthesize and publish key findings from
the discussions and artifacts developed. We will gather insights and
perspectives on AI red teaming practices by discussing developed artifacts.
The resulting synthesis will offer valuable insights for practitioners and
highlight avenues for further exploration by researchers.

##  7\. Organizing Team

Our workshop proposal includes a team of researchers experienced in critically
examining labor, moderation, mental health and well-being, and RAI red-
teaming.

Alice Qian Zhang is a PhD student in the Human-Computer Interaction Institute
at Carnegie Mellon University. Her research explores avenues to support
individuals engaging with social computing technologies and AI systems, with a
particular emphasis on underrepresented populations and the implications for
mental health and well-being.

Ryland Shaw is a pre-doctoral research assistant at Microsoft Research’s
Social Media Collective, where he works on questions of AI ethics,
technological norms, and sociotechnical systems. He has an MA in Communication
from Simon Fraser University and comes from a background in documentary
filmmaking.

Jacy Reese Anthis is the director of the Sentience Institute, a visiting
scholar at the Stanford Institute for Human-Centered Artificial Intelligence
(HAI), and a PhD candidate in the sociology and statistics departments at the
University of Chicago. Jacy researches machine learning and human-AI
interaction, particularly the rise of digital minds and how humanity can work
together with highly capable AI systems.

Ashlee Milton is a PhD candidate in computer science at the University of
Minnesota, focusing on human-computer interaction. Their research investigates
how information retrieval systems are used by and affect users from
marginalized populations from a user perspective to better design these
systems to support users’ needs and mental well-being.

Emily Tseng is a postdoctoral researcher at Microsoft Research. Her work
explores how computing technologies mediate individual, interpersonal, and
structural harms, and how to create more equitable tech. Emily publishes at
top-tier venues in HCI and design (CHI, CSCW), computer security and privacy
(USENIX Security), and medicine (JAMA). She earned a Ph.D. in Information
Science at Cornell University and a B.A. at Princeton University.

Jina Suh is a Principal Researcher in the Human Understanding and Empathy
group at Microsoft Research. Her work lies at the intersection of technology
and human well-being, where she examines the role of technologies, design
choices, development practices, and values embedded in them in shifting power
dynamics and affecting individual and organizational mental health and well-
being. She received her Ph.D. in Computer Science at the University of
Washington.

Lama Ahmad is a Policy Researcher at OpenAI, leading red teaming and
researcher access efforts. Her work focuses on evaluating the socio-technical
impact of AI systems on society. Prior to OpenAI, Lama was at Facebook,
assessing the impact of social media on elections and democracy.

Ram Shankar Siva Kumar founded and leads the AI Red Team at Microsoft and co-
authored Not with a Bug, But with a Sticker: Attacks on Machine Learning
Systems and What To Do About Them (Kumar and Anderson, 2023). He is also a
Tech Policy Fellow at UC Berkeley, wherein his work on adversarial machine
learning appeared notably in the National Security Commission on Artificial
Intelligence (NSCAI) Final report presented to the United States Congress and
the President.

Julian Posada is an Assistant Professor of American Studies at Yale University
and a member of the Yale Law School’s Information Society Project and the Yale
Institute for Foundations of Data Science. Their research integrates theories
and methods from information science, sociology, and human-computer
interaction to examine how technology is developed and used within various
historical, cultural, and social contexts.

Benjamin Shestakofsky is an Assistant Professor of Sociology at the University
of Pennsylvania. His research centers on the relationship between work,
technology, organizations, and political economy. He is the author of Behind
the Startup: How Venture Capital Shapes Work, Innovation, and Inequality
(Shestakofsky, 2017).

Sarah T. Roberts is an associate professor at UCLA specializing in Internet
and social media policy, infrastructure, politics and culture, and the
intersection of media, technology, and society. She is the faculty director of
the UCLA Center for Critical Internet Inquiry (C2i2). Informed by feminist
Science and Technology Studies perspectives, Roberts is keenly interested in
the way power, geopolitics, and economics play out on/via the internet,
reproducing, reifying, and exacerbating global inequities and social
injustice.

Mary L. Gray is a Senior Principal Researcher at Microsoft Research, a Faculty
Associate at Harvard University’s Berkman Klein Center for Internet and
Society, and a MacArthur Fellow. An anthropologist and media scholar by
training, she focuses on how people’s everyday uses of technologies transform
labor, identity, and human rights. She maintains a faculty position in the
Luddy School of Informatics, Computing, and Engineering with affiliations in
Anthropology and Gender Studies at Indiana University.

## References

  * (1)
  * Abbass et al. (2011) Hussein Abbass, Axel Bender, Svetoslav Gaidow, and Paul Whitbread. 2011.  Computational red teaming: Past, present and future.  _IEEE Computational Intelligence Magazine_ 6, 1 (2011), 30–42.
  * Anthis et al. (2024) Jacy Reese Anthis, Kristian Lum, Michael Ekstrand, Avi Feller, Alexander D’Amour, and Chenhao Tan. 2024.  The Impossibility of Fair LLMs.  _arXiv preprint arXiv:2406.03198_ (2024).
  * Arsht and Etcovitch (2018) Andrew Arsht and Daniel Etcovitch. 2018.  The human cost of online content moderation.  _Harvard Journal of Law and Technology_ 2 (2018).
  * Barocas et al. (2017) Solon Barocas, Kate Crawford, Aaron Shapiro, and Hanna Wallach. 2017.  The Problem With Bias: Allocative Versus Representational Harms in Machine Learning. Philadelphia, PA.
  * Barr (2015) Alistair Barr. 2015.  Google Mistakenly Tags Black People as ‘Gorillas,’ Showing Limits of Algorithms.  _Wall Street Journal_ (July 2015).  http://blogs.wsj.com/digits/2015/07/01/google-mistakenly-tags-black-people-as-gorillas-showing-limits-of-algorithms/
  * Bolukbasi et al. (2016) Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. 2016.  Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings. In _30th Conference on Neural Information Processing Systems_. Barcelona.
  * Dwoskin (2019) Elizabeth Dwoskin. 2019.  Inside facebook, the second-class workers who do the hardest job are waging a quiet battle.  https://www.washingtonpost.com/technology/2019/05/08/inside-facebook-second-class-workers-who-do-hardest-job-are-waging-quiet-battle/
  * Forum (2024) Frontier Model Forum. 2024.  Issue brief: What is red teaming?  https://www.frontiermodelforum.org/updates/red-teaming/
  * Ganguli et al. (2022) Deep Ganguli, Liane Lovitt, Jackson Kernion, Amanda Askell, Yuntao Bai, Saurav Kadavath, Ben Mann, Ethan Perez, Nicholas Schiefer, Kamal Ndousse, et al. 2022\.  Red teaming language models to reduce harms: Methods, scaling behaviors, and lessons learned.  _arXiv preprint arXiv:2209.07858_ (2022).
  * Gillespie (2018) Tarleton Gillespie. 2018.  _Custodians of the Internet: Platforms, Content Moderation, and the Hidden Decisions That Shape Social Media_.  Yale University Press, New Haven Connecticut.
  * Gillespie (2024) Tarleton Gillespie. 2024.  Generative AI and the Politics of Visibility.  _Big Data & Society_ (2024).
  * Gray and Suri (2019) Mary L. Gray and Siddharth Suri. 2019.  _Ghost Work: How to Stop Silicon Valley from Building a New Global Underclass_ (illustrated edition ed.).  Harper Business, Boston.
  * House (2023) The White House. 2023.  FACT SHEET: Biden-Harris Administration Secures Voluntary Commitments from Leading Artificial Intelligence Companies to Manage the Risks Posed by AI.  https://www.whitehouse.gov/briefing-room/statements-releases/2023/07/21/fact-sheet-biden-harris-administration-secures-voluntary-commitments-from-leading-artificial-intelligence-companies-to-manage-the-risks-posed-by-ai/
  * humane intelligence et al. (2024) humane intelligence, SeeAI, and DEFCON AI Village. 2024.
  * Kumar and Anderson (2023) Ram Shankar Siva Kumar and Hyrum Anderson. 2023.  _Not with a Bug, But with a Sticker: Attacks on Machine Learning Systems and what to Do about Them_.  John Wiley & Sons, Incorporated.
  * Miceli et al. (2022) Milagros Miceli, Julian Posada, and Tianling Yang. 2022.  Studying Up Machine Learning Data: Why Talk About Bias When We Mean Power?  _Proceedings of the ACM on Human-Computer Interaction_ 6, GROUP (Jan. 2022), 34:1–34:14.  https://doi.org/10.1145/3492853
  * Michel (2018) Michel. 2018.  Ex-Content Moderator Sues Facebook, Saying Violent Images Caused Her PTSD - e-traces.  https://api.semanticscholar.org/CorpusID:150309904
  * Olteanu et al. (2023) Alexandra Olteanu, Michael Ekstrand, Carlos Castillo, and Jina Suh. 2023.  Responsible AI Research Needs Impact Statements Too.  _arXiv preprint arXiv:2311.11776_ (2023).
  * Pendse et al. (2024) Sachin R Pendse, Talie Massachi, Jalehsadat Mahdavimoghaddam, Jenna Butler, Jina Suh, and Mary Czerwinski. 2024.  Towards Inclusive Futures for Worker Wellbeing.  _Proceedings of the ACM on Human-Computer Interaction_ 8, CSCW1 (2024), 1–32.
  * Roberts (2019) Sarah T. Roberts. 2019.  _Behind the Screen: Content Moderation in the Shadows of Social Media_.  Yale University Press.  Google-Books-ID: uiCbDwAAQBAJ.
  * Ruckenstein and Turunen (2020) Minna Ruckenstein and Linda Lisa Maria Turunen. 2020.  Re-humanizing the platform: Content moderators and the logic of care.  22, 6 (2020), 1026–1042.  Publisher: Sage Publications Sage UK: London, England.
  * Schwartz (2019) Oscar Schwartz. 2019.  In 2016, Microsoft’s Racist Chatbot Revealed the Dangers of Online Conversation - IEEE Spectrum.  https://spectrum.ieee.org/in-2016-microsofts-racist-chatbot-revealed-the-dangers-of-online-conversation
  * Shestakofsky (2017) Benjamin Shestakofsky. 2017.  Working algorithms: Software automation and the future of work.  _Work and Occupations_ 44, 4 (2017), 376–423.
  * Soden et al. (2021) Robert Soden, David Ribes, Seyram Avle, and Will Sutherland. 2021.  Time for Historicism in CSCW: An Invitation.  _Proceedings of the ACM on Human-Computer Interaction_ 5, CSCW2 (Oct. 2021), 1–18.  https://doi.org/10.1145/3479603
  * Steiger et al. (2022) Miriah Steiger, Timir J Bharucha, Wilfredo Torralba, Marlyn Savio, Priyanka Manchanda, and Rachel Lutz-Guevara. 2022.  Effects of a Novel Resiliency Training Program for Social Media Content Moderators. In _Proceedings of Seventh International Congress on Information and Communication Technology: ICICT 2022, London, Volume 4_. Springer, 283–298.
  * Wood and Duggan (2000) Bradley J Wood and Ruth A Duggan. 2000.  Red teaming of advanced information assurance concepts. In _Proceedings DARPA Information Survivability Conference and Exposition. DISCEX’00_ , Vol. 2. IEEE, 112–118.
  * Zenko (2015) Micah Zenko. 2015.  _Red Team: How to succeed by thinking like the enemy_.  Basic Books.
  * Zenko and Haass (2015) Micah Zenko and Richard Haass. 2015.  “red team: How to succeed by thinking like the enemy”.  https://www.cfr.org/event/red-team-how-succeed-thinking-enemy