## A Family of Distributions of Random Subsets for Controlling Positive and Negative Dependence

Takahiro Kawashima

## Hideitsu Hino

ZOZO Research

## Abstract

Positive and negative dependence are fundamental concepts that characterize the attractive and repulsive behavior of random subsets. Although some probabilistic models are known to exhibit positive or negative dependence, it is challenging to seamlessly bridge them with a practicable probabilistic model. In this study, we introduce a new family of distributions, named the discrete kernel point process (DKPP), which includes determinantal point processes and parts of Boltzmann machines. We also develop some computational methods for probabilistic operations and inference with DKPPs, such as calculating marginal and conditional probabilities and learning the parameters. Our numerical experiments demonstrate the controllability of positive and negative dependence and the effectiveness of the computational methods for DKPPs.

## 1 INTRODUCTION

Random subset selection from a ground set is often encountered in problems related to statistics and machine learning. One common problem is modeling the purchasing behavior of customers; buying items from a ground set of products can be seen as the occurrence of a random subset. To go beyond the independent selection of items, we should consider a probabilistic model on the powerset of the ground set. Positive and negative dependence are fundamental concepts that characterize probabilistic models of random subsets. If the model has positive dependence, an attractive force is

Proceedings of the 28 th International Conference on Artificial Intelligence and Statistics (AISTATS) 2025, Mai Khao, Thailand. PMLR: Volume 258. Copyright 2025 by the author(s).

Institute of Statistical Mathematics RIKEN AIP

Figure 1: Two examples of subsets on the grid and their conditional probabilities log 10 P ( A | |A| = k ) with slight change in function that determines DKPPs. See Section 6 for more details.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-2e6433d0-567c-47fe-bfcd-8e402219cef3.jpg)

present and similar items tend to appear in a random subset. Conversely, if the model has negative dependence, a repulsive force occurs and random subsets are likely to contain diverse items.

Log-supermodularity and log-submodularity are representative characterizations of positive and negative dependence (Fortuin et al., 1971; Pemantle, 2000; Borcea et al., 2009). For example, ferromagnetic Ising models and determinantal point processes (DPPs) (Macchi, 1975; Borodin and Rains, 2005) are log-supermodular and log-submodular probabilistic models, respectively. Since the review article by Kulesza and Taskar (2012), DPPs have gained increasing attention in the machine learning community owing to their diversity-

promoting property.

One of the reasons that makes DPPs popular is their parameterization by a kernel matrix, which consists of pairwise similarities of items. Since kernel matrices can be constructed from any features of items, this parameterization is suitable for various machine learning and statistical problems. Indeed, DPPs are now applied to widespread problems including image search (Kulesza and Taskar, 2011), document summarization (Gillenwater et al., 2012; Dupuy and Bach, 2018), recommender systems (Wilhelm et al., 2018), randomized numerical linear algebra (Derezinski et al., 2020b; Derezi´ski and Mahoney, 2021), experimental design n (Derezinski et al., 2020a; Derezi´ski et al., 2022), and n counterfactual explanation (Mothilal et al., 2020). On the other hand, diversity is not a general prescription for such problems. Recommending similar glasses to a customer who previously bought certain glasses may not be effective, but it may be different with socks. Otherwise, we may want to adjust the strength of the repulsive force.

In this paper, we propose a new family of distributions for random subsets, discrete kernel point processes (DKPPs), by generalizing DPPs. DKPPs are determined by a kernel matrix and a scalar function on R ≥ 0 . Similarly to DPPs, the kernel matrix provides the pairwise similarity of items. Furthermore, the presence of the scalar function enables us to control positive and negative dependence. Figure 1 shows the actual behavior of DKPPs (see Section 6 for details). Attractive and repulsive forces are flexibly determined by changing a parameter λ . We also develop computational methods for evaluating marginal and conditional probabilities and learning DKPPs for practical use. Furthermore, we conduct an experiment on repulsive and attractive subset acquisition to demonstrate the applicability of the DKPPs.

## 1.1 Related Works

There are a few previous works that aim to develop a family of distributions to control positive and negative dependence. The closest ones to our study are immanantal point processes (Diaconis and Evans, 2000) and α -DPPs (Vere-Jones, 1997), in which the determinants in DPPs are generalized to the immanant and α -determinant, respectively. Although both immanantal point processes and α -DPPs include permanental point processes (i.e., behave like bosons with positive dependence (Macchi, 1975)), the computational issue is not resolved; even computing the permanent is #P-hard (Valiant, 1979). For negative dependence only, Mariet et al. (2018) considered the exponentiated strong Rayleigh distributions that can control the negative dependence and developed an approximate sam- pler for them.

Iyer and Bilmes (2015) introduced the submodular and log-submodular point processes as the family of distributions on a powerset. Although they mainly discussed how to handle these distributions, such as probabilistic operations and parameter learning, they did not focus on the control of positive and negative dependence.

## 2 PRELIMINARY

## 2.1 Supermodular and Submodular Functions

Let Y = { 1 , . . . , N } be a finite ground set with N items. A set function f : 2 Y → R is said to be submodular if f ( S ) + f ( T ) ≥ f ( S ∪ T ) + f ( S ∩ T ) holds for every S T , ⊆ Y . A set function f is said to be supermodular if -f is submodular and modular if f satisfies both submodularity and supermodularity.

For a continuous model with a probability density function p , the log-concavity of p is considered rather than concavity (An, 1996; Borzadaran and Borzadaran, 2011). In a similar spirit, we will focus on log-supermodular and log-submodular probability functions later; the set function f has logsupermodularity if log f is supermodular, and the same applies to log-submodularity. If f is logsubmodular and log-supermodular, f is said to be a log-modular function.

The multilinear extension of the set function f is one approach to extend the discrete f to a continuous function and was first introduced for submodular maximization problems (Calinescu et al., 2007; Chekuri et al., 2014).

Definition 2.1. Let f : 2 Y → R be a set function. The multilinear extension of f , denoted by ˜ : [0 f , 1] N → R , is defined by

$$\tilde { f } ( q ) \coloneqq \sum _ { \mathcal { A } \subseteq \mathcal { Y } } f ( \mathcal { A } ) \prod _ { i \in \mathcal { A } } q _ { i } \prod _ { i \notin \mathcal { A } } ( 1 - q _ { i } ), \quad ( 1 )$$

where q ∈ [0 , 1] N .

Suppose that Q q is the probability function of N independent Bernoulli trials with the parameters { q i } :

$$Q _ { q } ( \xi ) \coloneqq \prod _ { i = 1 } ^ { N } Q _ { q _ { i } } ( \xi _ { i } ) \coloneqq \prod _ { i = 1 } ^ { N } Bernoulli ( \xi _ { i } ; q _ { i } ), \ \ ( 2 )$$

for ξ ∈ { 0 1 , } N . Then, the multilinear extension (1) can also be written as

$$\tilde { f } ( q ) = \mathbb { E } _ { \xi \sim Q _ { q } } [ f ( \mathcal { A } _ { \xi } ) ],$$

where A ξ := { i ∈ Y : ξ i = 1 . }

## 2.2 Positive and Negative Dependence

Throughout this paper, we consider probability distributions on 2 Y , which assign occurrence probabilities to every subset A ⊆ Y . Such distributions are equivalent to those of N -dimensional random binary vectors and discrete point processes on Y .

Positive and negative dependence are essential concepts that characterize distributions on 2 Y . Generally, the probability function P : 2 Y → [0 , 1] exhibits positive dependence when a random subset A ∼ P tends to contain similar elements. For example, consider a ferromagnetic Ising model. In this model, closely located spins tend to align in the same direction, with similarity determined by their distance on the grid. This scenario illustrates positive dependence. Conversely, an antiferromagnetic Ising model leads to a random subset with diverse elements, as adjacent spins tend to have opposite directions. This is an example of negative dependence.

̸

Log-supermodularity and log-submodularity of the probability function P are representative characterizations of positive and negative dependence, respectively. For an intuitive understanding, we consider two singletons S = { } i and T = { } j such that i = j . If P is log-submodular, the inequality P ( { i, j } ) ≤ ZP ( { } i ) P ( { } j ) ∝ P ( { } i ) P ( { } j ) holds, where Z is the normalizing constant of P . The co-occurrence of i and j is upper bounded by a constant multiple of the probability that each appears alone, which implies the negative dependence. The same applies to the positive dependence. The log-supermodularity of the probability function P is a sufficiently strong condition. Indeed, the Fortuin-Kasteleyn-Ginibre (FKG) inequality states that log-supermodularity leads to other major characterizations (Fortuin et al., 1971). On the other hand, the log-submodularity of P is a relatively weak condition for the negative dependence induced by other characterizations but not vice versa (Pemantle, 2000; Borcea et al., 2009). However, log-submodular distributions are often used to model diverse random subsets (Iyer and Bilmes, 2015; Tschiatschek et al., 2016; Djolonga et al., 2018) because of their tractability. In Subsection 3.1, we also use log-supermodularity and log-submodularity to control positive and negative dependence.

## 2.3 Operator Monotonicity and Convexity

↦

Let ϕ : R → R be a function. Given the N × N Hermitian matrix X that can be diagonalized as X = U diag( λ , . . . , λ 1 N ) U ∗ , we also regard ϕ as a matrix operator such that ϕ : X → U diag( ϕ λ ( 1 ) , . . . , ϕ ( λ N )) U ∗ . Note that a matrix logarithm and a matrix exponential are special cases of

ϕ . Now, we can define the monotonicity of ϕ as an operator.

Definition 2.2. The function ϕ is said to be operator monotone if A ⪰ B implies ϕ ( A ) ⪰ ϕ ( B ) for all n ∈ N and for all the n × n Hermitian matrices A B , . The function ϕ is operator antitone if -ϕ is operator monotone.

Here, we use ⪰ for positive semidefinite ordering. Since ordinary monotonicity is the special case of n = 1 in Definition 2.2, operator monotonicity is much stronger than ordinary monotonicity. Indeed, ϕ x ( ) = x p is operator monotone on [0 , ∞ ) for p ∈ [0 , 1], but not for p = 2 (see Bhatia, 1997, Chapter 5).

We can also define operator convexity and concavity.

Definition 2.3. The function ϕ is said to be operator convex if

$$t \phi ( A ) + ( 1 - t ) \phi ( B ) \succeq \phi ( t A + ( 1 - t ) B ), \ t \in [ 0, 1 ]$$

holds for all n ∈ N and for all the Hermitian matrices A B , . A function ϕ is operator concave if -ϕ is operator convex.

Let ϕ ′ be a function and ϕ be a primitive of ϕ ′ . As with ordinary monotone functions, ϕ is operator convex if ϕ ′ is operator monotone. We denote X [ A ] := ( X ij ) i,j ∈A for A ⊆ Y . Friedland and Gaubert (2013) obtained an interesting result that bridges operator monotonicity/antitonicity and supermodularity/submodularity.

Theorem 2.4. (Friedland and Gaubert, 2013) Suppose that ϕ is a real continuous function on the interval E ⊂ R and that ϕ is a primitive of the operator monotone function ϕ ′ on E . Then, for every N × N Hermitian matrix X whose eigenvalues are all in E , the set function

$$f \colon 2 ^ { \mathcal { Y } } \rightarrow \mathbb { R } \colon \mathcal { A } \mapsto \text{tr} \phi ( X [ \mathcal { A } ] ) \text{ \quad \ \ } ( 3 )$$

is supermodular. If ϕ is a primitive of the operator antitone ϕ ′ , the set function f is submodular.

↦

Conceptually, Theorem 2.4 says that the operator convexity/concavity of ϕ corresponds to the supermodularity/submodularity of f : A → X [ A ] 1 . Note that the submodularity of the set function A ↦→ log det( X [ A ]) is well known (Bach, 2013), and it is a special case of (3) with ϕ = log. Another example from Theorem 2.4 is ϕ : x → x p ; it leads to a submodular f when p ∈ [0 , 1] and a supermodular f when p ∈ [1 , 2].

1 This is not always true because there are operator convex functions that cannot be obtained as primitives of operator motonone functions, as stated by Friedland and Gaubert (2013).

## 3 DISCRETE KERNEL POINT PROCESSES

Definition 3.1. Let ϕ : R ≥ 0 → R be a continuous function and L be an N × N positive semidefinite Hermitian matrix. The probability function P ϕ ( ; · L ) : 2 Y → [0 , 1] is called a discrete kernel point process (DKPP) if it is given by

$$P _ { \phi } ( \mathcal { A } ; L ) = \frac { 1 } { Z _ { \phi } ( L ) } \exp \left ( \text{tr} \phi ( L [ \mathcal { A } ] ) \right ) = \colon \frac { \tilde { P } _ { \phi } ( \mathcal { A } ; L ) } { Z _ { \phi } ( L ) }, \\ \text{where} \quad Z _ { \phi } ( L ) \coloneqq \sum _ { \mathcal { A } \subseteq \mathcal { V } } \exp \left ( \text{tr} \phi ( L [ \mathcal { A } ] ) \right ) \quad \begin{array} { c } \text{sif} \\ \text{th} \\ B \text{.} \end{array} \quad \text{$\text{$\text{$th}$} }$$

for every A ⊆ Y .

Let C ( R ≥ 0 , R ) denote the set of all functions from R ≥ 0 to R . The set

$$\mathcal { F } _ { \text{DKPP} } \coloneqq \{ P _ { \phi } ( \cdot ; \mathbf L ) \, \colon \, \phi \in \mathcal { C } ( \mathbb { R } _ { \geq 0 }, \mathbb { R } ), \mathbf L \in \mathbb { H } _ { \geq 0 } ^ { N } \}$$

is a family of specific distributions on 2 Y . We readily see that DPPs belong to F DKPP .

Proposition 3.2. If ϕ = log , a DKPP P ϕ ( ; · L ) is a DPP.

Proof. In general, we have the identity tr log X = log det X for every positive semidefinite X . This leads to P ϕ ( A ; L ) ∝ exp(tr log L [ A ]) = exp(log det L [ A ]) = det L [ A ] .

One of the representative probabilistic models for a random binary vector ξ ∈ { 0 1 , } N (equivalently random subsets) is the Boltzmann machine (Ackley et al., 1985). A fully visible Boltzmann machine with bias vectors h ∈ R N and symmetric connections W (diag( W ) = 0 , W ij = W ji ) is modeled as

$$P _ { \text{BM} } ( \xi ; h, W ) \infty \exp \left ( \sum _ { i = 1 } ^ { N } h _ { i } \xi _ { i } + \sum _ { i, j = 1 } ^ { N } W _ { i j } \xi _ { i } \xi _ { j } \right ). \, ( 4 ) \quad \text{An } \colon _ { \text{smoo} }.$$

In the Boltzmann machine (4), two-body interactions of ξ are captured by the quadratic term. We can see that a DKPP becomes a Boltzmann machine if ϕ is a quadratic function.

Proposition 3.3. Suppose that ϕ x ( ) = ax 2 + bx + c . Then, the DKPP P ϕ ( ; · L ) is equivalent to the Boltzmann machine (4) with the parameters

̸

$$W _ { i j } & = \begin{cases} 0 & ( i = j ), & \text{ with } \\ a | L _ { i j } | ^ { 2 } & ( i \neq j ), & \text{or} \\ h _ { i } & = a L _ { i i } ^ { 2 } + b L _ { i i } + c, & \text{ for } \\ & \text{bol} \end{cases}$$

for i, j = 1 , . . . , N .

The proof of Proposition 3.3 is in Appendix A. Note that although any values are allowed for W ij in Boltzmann machines, the relation (5) implies that a DKPP with quadratic ϕ can only represent either all nonnegative or all non-positive { W ij } i,j .

When a = 0, the connections W ij vanish in (5), meaning all elements of ξ become independent. Formally, the following corollary holds as a special case of Proposition 3.2.

Corollary 3.4. Suppose that ϕ x ( ) = bx + c . Then, the DKPP P ϕ ( ; · L ) is equivalent to N independent Bernoulli trials where the probability of success of the i -th trial is given by p i = σ bL ( ii + ) c , with σ : R → (0 , 1) being the logistic sigmoid function.

Additionally, the following proposition also holds for affine ϕ .

Proposition 3.5. A DKPP P ϕ ( ; · L ) is log-modular if and only if ϕ is affine for all x ∈ R ≥ 0 .

The proof of Proposition 3.5 is shown in Appendix A.

## 3.1 Positive and Negative Dependence of DKPPs

The behavior of a DKPP P ϕ is fundamentally determined by ϕ , allowing control over positive and negative dependence by appropriately choosing ϕ . The following corollary follows directly from Theorem 2.4.

Corollary 3.6. Let ϕ be a primitive of a function ϕ ′ . A DKPP P ϕ ( ; · L ) is log-supermodular if ϕ ′ is operator monotone and log-submodular if ϕ ′ is operator antitone.

An appropriate parameterization of ϕ enables a smooth transition between positive and negative dependence. For example, we consider the scaled BoxCox transformation for ϕ :

$$\phi _ { \beta, \lambda } ( x ) \coloneqq \begin{cases} \beta \log x & ( \lambda = 0 ), \\ \frac { \beta ( x ^ { \lambda } - 1 ) } { \lambda } & ( \text{otherwise} ), \end{cases}$$

with the hyperparameters λ ∈ R and β ∈ R &gt; 0 . According to Corollary 3.6, a DKPP P ϕ β,λ exhibits negative dependence for λ ∈ [0 , 1] and positive dependence for λ ∈ [1 , 2]. It reduces to a DPP for λ = 0 and a Boltzmann machine for λ = 2. Hereafter, we denote ϕ λ := ϕ 1 ,λ for simplicity.

## 4 OPERATIONS AND INFERENCE OF DKPPs

## 4.1 Mode Exploration

The mode exploration arg max A⊆Y log P ϕ ( A ; L ) is one of the most fundamental problems regarding probability model over sets, but it is NP-hard for a general ϕ for DKPPs. If P ϕ ( ; · L ) is log-supermodular, it becomes a submodular minimization problem. Although there are (strongly) polynomial-time combinatorial algorithms (Schrijver, 2000; Iwata et al., 2001; Orlin, 2009) for submodular minimization problems, their computational complexity is expensive (typically O ( N 6 ) for function calls). The minimum-norm point algorithm (Fujishige et al., 2006; Fujishige and Isotani, 2011; Chakrabarty et al., 2014) is an alternative to such combinatorial algorithms. Although the minimum-point algorithm has weaker theoretical complexity, it usually performs better in practice.

When P ϕ ( ; · L ) is log-submodular, the problem becomes a submodular maximization problem. Although submodular maximization problems are NPhard, many approximation algorithms have been proposed. If log P ϕ ( ; · L ) is not only submodular but also monotone (i.e., log P ϕ ( S ; L ) ≤ log P ϕ ( T ; L ) holds for every S ⊆ T ), the simple greedy algorithm provides a 1 -1 /e approximation (Nemhauser et al., 1978). However, we have no guarantee of monotonicity in general. For example, a DPP is a special case of DKPPs and has a submodular but non-monotone log-probability function. For general non-monotone submodular maximization problems, a deterministic 1/3-approximate algorithm and a randomized 1/2-approximate algorithm (in expectation) are proposed in (Buchbinder et al., 2012).

In constrained settings, submodular minimization problems are generally NP-hard (Garey and Johnson, 1979; Feige et al., 2001), and there are no algorithms with a polynomial approximation factor even for constraints with a cardinality lower bound (Svitkina and Fleischer, 2011). Nevertheless, some practical approximation techniques can be applied (Svitkina and Fleischer, 2011; Iyer et al., 2013). Conversely, there are approximate algorithms yielding constant factor approximations for submodular maximization problems under cardinality-constrained settings. Buchbinder et al. (2014) proposed efficient algorithms achieving the approximation factors in the range [1 /e + 0 004 1 . , / 2 -o (1)] for the constraint |A| ≤ k and [0 356 1 . , / 2 -o (1)] for |A| = k , in expectation.

## 4.2 Sampling

Although direct sampling from a DKPP P ϕ ( ; · L ) is difficult for a general ϕ , Markov chain Monte Carlo (MCMC) samplers are effective. Although many advanced MCMC samplers are not suitable for DKPPs owing to their discreteness, the recently proposed Langevin-like sampler (Zhang et al., 2022) may be a viable option. Classical MCMC samplers are also applicable. For the probability function P on the powerset 2 V , mixing times of the Metropolis-Hastings sampler (including the Gibb sampler) are studied both in the log-supermodular or log-submodular cases (Gotovos et al., 2015) and for general cases (Rebeschini and Karbasi, 2015).

## 4.3 Normalizing Constant and Expectation

The evaluation of the normalizing constant Z ϕ ( L ) is also crucial, as it is required for calculating marginal probabilities. Several methods are developed for approximating or bounding Z ϕ ( L ), including the meanfield approximation for set distributions (Djolonga et al., 2018) and the perturb-and-MAP method (Papandreou and Yuille, 2011; Hazan and Jaakkola, 2012; Balog et al., 2017). The L-field developed in (Djolonga and Krause, 2014; Djolonga et al., 2018) is also applicable to obtain the lower and upper bound of log Z ϕ ( L ) if the DKPP is log-submodular or log-supermodular.

The mean-field approximation is a basic method in statistical mechanics and Bayesian statistics to approximate target distributions. For the DKPP P ϕ ( ; · L ), we can employ Q q defined in (2) for the variational distribution and aim to minimize the Kullback-Leibler divergence (KLD) between the variational distribution and the DKPP. Then, we obtain the following iterative update rule for i = 1 , . . . , N from the coordinate ascent:

̸

$$\text{go- ascim.} \\ \text{ler} \quad & q _ { i } \leftarrow \sigma \left ( \mathbb { E } _ { \xi _ { \vee ^ { i } } \sim Q _ { \mu _ { i } } } [ f ( i | \mathcal { A } _ { \xi _ { \vee ^ {$$

Here, A ξ \ i is defined as A ξ \ i := { i ∈ { 1 , . . . , i -1 , i + 1 , . . . , N } : ξ i = 1 . The derivation of (7) is presented } in Appendix B. The expectation in (7) can easily be approximated using Monte Carlo methods. Once the optimal q is found, the tightened evidence lower bound (ELBO) L ( q ) := H [ Q q ] + E ξ ∼ Q q [tr ϕ ( L [ A ξ ])], which ensures log Z ϕ ≥ L ( q ), can be computed ( H [ ] · means the entropy).

Our proposed method for evaluating the normalizing constant Z ϕ ( L ) of a DKPP is the combination of mean-field approximation and importance sampling.

For any set function g and a proposal distribution Q on 2 Y , the expectation E A∼ P ϕ [ g ( A )] can be evaluated as the weighted mean over Q since

$$\mathbb { E } _ { \mathcal { A } \sim P _ { \phi } } [ g ( \mathcal { A } ) ] = \mathbb { E } _ { \mathcal { A } \sim Q } [ w ( \mathcal { A } ) g ( \mathcal { A } ) ], \quad ( 8 ) \quad \quad \quad$$

where w ( A ) := P ϕ ( A ; L ) /Q ( A ). For unnormalized ˜ P ϕ ,

$$1 & = \mathbb { E } _ { \mathcal { A } \sim P _ { \phi } } [ 1 ] = \frac { 1 } { Z _ { \phi } ( L ) } \mathbb { E } _ { \mathcal { A } \sim Q } \left [ \frac { \tilde { P } _ { \phi } ( \mathcal { A$$

yields the sampling-based method for evaluating the normalizing constant. If our goal is to obtain (8), the approximated Z ϕ ( L ) can be plugged into the weight w ( A ) = P ϕ ( A ; L ) /Q ( A ) = ˜ P ϕ ( A ; L ) / Z ( ϕ ( L ) Q ( A )).

When evaluating (9), i.e., g ( A ) ≡ 1, we employ the variational distribution Q q obtained by iterating (7) as the proposal distribution. In general, Q ∗ ( A ) ∝ | g ( A | ) P ϕ ( A ; L ) minimizes Var A∼ Q [ w ( A ) g ( A )] (Rubinstein and Kroese, 2008). Because this choice of the proposal distribution is the solution of arg min Q q KL( Q q ∥ Q ∗ ) = arg min Q q KL( Q q ∥ P ϕ ( ; · L )), it is the reasonable choice for evaluating (9).

## 4.4 Marginal and Conditional Probabilities

Consider recommending k items as a subset of size k . The customer may already have items in the basket; then conditional probabilities naturally arise. Marginal probabilities are also important because they define conditional probabilities. We introduce some computational techniques to evaluate marginal and conditional probabilities of random subset models.

## Marginal Probability

Let A sub and A sup be given subsets Y such that A sub ⊆ A sup . We consider approximating the marginal probability P ( A sub ⊆ A ⊆ A sup ) when A is a random subset following a probabilistic function on 2 Y . A straightforward way to evaluate this marginal probability is to use the importance sampling as in (8):

$$\mathbb { P } ( \mathcal { A } _ { s u b } \subseteq \mathcal { A } \subseteq \mathcal { A } _ { s u p } ) & = \mathbb { E } _ { P _ { \phi } } [ 1 ( \mathcal { A } _ { s u b } \subseteq \mathcal { A$$

The Monte Carlo method for (10) is unbiased for P ( A sub ⊆ A ⊆ A sup ), but the critical issue remains: most Monte Carlo samples yield zero when |A sup \A sub | is small owing to the indicator function. If we use Monte Carlo samples on 2 A sup \A sub instead of 2 Y , the number of wasted samples could be reduced. The following proposition realizes this.

Proposition 4.1. Let P be a probability function on 2 Y and ξ be a random vector following the independent Bernoulli trials Q q defined in (2) . Then,

$$\tilde { P } _ { \phi }, \quad \mathbb { E } _ { \xi } & \left [ \frac { P ( \mathcal { A } _ { \xi } ) } { \prod _ { i \in \mathcal { A } _ { \sup } \mathcal { A } _ { \substack { \mathcal { A } _ {$$

and

$$( 9 ) \quad \text{Var} _ { \xi } \left [ \frac { P ( \mathcal { A } _ { \xi } ) } { \prod _ { i \in \mathcal { A } _ { \sup } \mathcal { \mathcal { A } _ { \text{sub} } } } Q _ { q _ { i } } ( \xi _ { i } ) } \begin{vmatrix} \xi _ { i } = 1 & ( i \in \mathcal { A } _ { \text{sub} } ) \\ \xi _ { j } = 0 & ( j \in \mathcal { Y } \mathcal { A } _ { \sup } ) \end{vmatrix}$$

$$\leq \text{Var} _ { \xi } [ w ( \mathcal { A } _ { \xi } ) 1 ( \mathcal { A } _ { \text{sub} } \subseteq \mathcal { A } _ { \xi } \subseteq \mathcal { A } _ { \text{sup} } ) ]$$

$$\cdot \cdot \cdot \quad h o l d, \, w h e r e \ w ( \mathcal { A } _ { \xi } ) = P ( \mathcal { A } _ { \xi } ) / Q _ { q } ( \xi ).$$

The proof of Proposition 4.1 mainly depends on the tower properties of expectation and variance (the detailed proof is in Appendix A). Such variance reduction techniques are called Rao-Blackwellization and are commonly used in computational statistics (Casella and Robert, 1996; Doucet et al., 2000). Since only { ξ i } i ∈A sup \A sub are required as Monte Carlo samples owing to the independence of the proposal distribution Q q , and the indicator function no longer appears in (11), we can expect a significant reduction in variance when evaluating the marginal probability. RaoBlackwellization is effective in estimating marginal probabilities other than P ( A sub ⊆ A ⊆ A sup ).

Proposition 4.2. Let A be a random subset following the probability function P : 2 Y → [0 , 1] . Then, we have

$$\mathbb { P } ( | \mathcal { A } | = k ) = \binom { N } { k } \mathbb { E } _ { \mathcal { A } ^ { k } \sim Q ^ { k } } [ P ( \mathcal { A } ^ { k } ) ], \quad ( 1 2 )$$

where Q k is the uniform distribution on {A ⊆ Y : |A| = k } .

The proof of 4.2 is also shown in Appendix A. Proposition 4.2 provides an accurate Monte Carlo method to evaluate the marginal probability P ( |A| = k ) for a given k ∈ { 1 , . . . , N } . Simply take Monte Carlo samples consisting of uniformly randomly chosen k items in Y and evaluate (12).

## Conditional Probability

The conditional probability

$$\stackrel { - } { e } \ r e ^ { - } _ { \text{when} } \quad P _ { \phi } ( \mathcal { A } | \mathcal { A } _ { \text{sub} } \subseteq \mathcal { A } \subseteq \mathcal { A } _ { \text{sup} } ; \mathcal { L } ) = \frac { P _ { \phi } ( \mathcal { A } ; \mathcal { L } ) } { \mathbb { P } ( \mathcal { A } _ { \text{sub} } \subseteq \mathcal { A } \subseteq \mathcal { A } _ { \text{sup} } ) } \\ \stackrel { - } { e } d \text{of}$$

can be accurately estimated by approximating the marginal probability P ( A sub ⊆ A ⊆ A sup ) using

Proposition 4.1. Note that the approximation of the normalizing constants within (11) is not required if we are only interested in the conditional probability because they cancel out in the numerator and denominator in (13). The same applies to P ϕ ( A||A| = k ; L ).

## 5 LEARNING DKPPs

Since the kernel matrix L of DKPPs indicates the pairwise similarity for each ( i, j ) ∈ Y × Y , we can build it directly when the items have feature vectors. Otherwise, we may need to learn the kernel matrix L from observations.

Let A 1 , . . . , A M ∈ Y be the observed data series with M samples. The simplest way to learn L is through the maximum likelihood estimation (MLE). For ϕ = log, say for DPPs, several algorithms have been developed to learn L through MLE (Gillenwater et al., 2014; Mariet and Sra, 2015, 2016; Gartrell et al., 2017; Dupuy and Bach, 2018; Kawashima and Hino, 2023). However, the term log Z ϕ ( L ) makes it difficult to learn L directly for general ϕ .

As an alternative to MLE, we propose using ratio matching, which was developed by (Hyv¨rinen, 2007) a as a discrete extension of score matching (Hyv¨rinen, a 2005). According to the prescription of the ratio matching, the objective function to minimize is

$$J ( L ) \coloneqq \frac { 1 } { M } \sum _ { m, n } g \left ( \exp ( \text{tr} \phi ( L [ \mathcal { A } _ { m } ] ) - \text{tr} \phi ( L [ \mathcal { A } _ { m } ^ { \bar { n } } ] ) ) \right ) ^ { 2 }, \quad \text{thed by } \text{Me} \\ ( 1 4 ) \quad \text{samp}.$$

$$\text{where } \ g ( x ) \coloneqq \frac { 1 } { 1 + x }, \, \mathcal { A } ^ { \bar { n } } \coloneqq \begin{cases} \mathcal { A } \{ n \} & ( n \in \mathcal { A } ), & \text{The} \\ \mathcal { A } \cup \{ n \} & ( n \notin \mathcal { A } ), & \text{pres} \end{cases}.$$

for DKPPs. Although we cannot evaluate the exponent term in (14) more efficiently than by direct computation for general ϕ , we can employ stochastic gradient descent (SGD) because J has a summation form. Let Ω ⊆ { ( m,n ) : m = 1 , . . . , M, n = 1 , . . . , N } be the minibatch and κ := max {|A | 1 , . . . , |A M |} . The time complexity of computing the gradient ∂J/∂ L is O | ( Ω | κ 3 + Ω | | N 2 ), which no longer depends on the sample size M and the number of items N , except for the term | Ω | N 2 owing to | Ω additions of | N × N matrices (see Appendix C for derivation). This ensures the good scalability of the algorithm. Optionally, the variance reduction technique for SGD of the ratio matching can be applied (Liu et al., 2022).

## 6 EXPERIMENTS

All experiments were performed on a MacBook Pro (2023, macOS 14.3) with an Apple M3 Pro chip and

Algorithm 1: Subset Acquiring Algorithm Input: DKPP P ϕ ( ; · L ) and the subset size k Output: A Initialize A ← {} , B ← { 1 , . . . , N } ; for t = 1 to k do Sample j ∈ B with probability proportional to weights w i = ˜ ( P ϕ A∪{ }| i L ) , i ∈ B ; Update A ← A ∪ { } i , B ← B\{ } j ; end

36GB RAM.

## 6.1 Controllability of Positive and Negative Dependence

To verify that DKPPs can flexibly control positive and negative dependence, we experiment on the behavior of the conditional probability P ϕ ( A | |A| = k ; L ). We prepare a 20 × 20 grid of points in R 2 as the ground set Y , so that N = 20 2 = 400. The kernel matrix L is constructed from the Gaussian kernel with unit bandwidth. Then, we create two types of realization on 2 Y : SCATTERED and GATHERED , both containing k = |A| = 25 items. SCATTERED is obtained by applying an approximate algorithm for submodular maximization (Buchbinder et al., 2014) to a DPP, whereas GATHERED is created manually. We evaluate the conditional probabilities P ϕ λ ( A | |A| = k ; L ) where ϕ λ is the Box-Cox transformation (6). We execute 30 trials of Monte Carlo approximations using (12) with 1 000 , samples to estimate the conditional probabilities.

The results are shown in Figure 1. The error bars are present but nearly invisible owing to the remarkably small approximation variance. As expected, the probability of SCATTERED decreases monotonically and the probability of GATHERED increases monotonically with λ . Interestingly, the probabilities of SCATTERED and GATHERED reverse at λ = 1. This result aligns exactly with the theory; the switch between positive and negative dependence occurs at λ = 1, as explained in Subsection 3.1.

## 6.2 Subset Acquisition

Attractive and repulsive subset acquisition may be the most direct application of the DKPPs. We randomly pick N = 2 000 images of the MNIST dataset (Le-, cun et al., 1998) with containing 200 instances from each digit class. Then, the Gaussian kernel with the median heuristic is applied to make the kernel matrix L ∈ R 2 000 , × 2 000 , . Algorithm 1 is the heuristic algorithm to acquire subsets from a DKPP. Given the kernel matrix, we run the algorithm to acquire subsets of size 5 from P ϕ β,λ and measure the number of dis-

Figure 2: Number of distinct classes within the acquired subsets.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-c7e79c90-09a3-4269-84dd-a65f5cee725f.jpg)

tinct digit classes within each subset. A larger value of this metric indicates more repulsive subset acquisition, while a smaller value suggests more attractive.

Figure 2 shows the metric values for β ∈ { 1 10 50 , , } , λ ∈ [0 , 2] with the mean and standard deviations of 100 trials. Although the values are not significantly different in β = 1, it smoothly decreases as λ increases for β = 10; the dependency control is realized. We can find the dependency is more intensified for β = 50. Additionally, we visually show the acquired instances in Appendix D.

Notably this procedure involves no learning process at all. The entire process is forward-only, demonstrating the advantage of the DKPP's clear and practicable parameterization via the kernel matrix and the dependency controlling function ϕ .

## 6.3 Approximating the Normalizing Constant

We assess some approximating or bounding methods for log Z ϕ ( L ). We use the Box-Cox transformation (6) for ϕ and the hyperparameter λ ∈ [0 , 2]. We calculate the mean-field ELBOs and demonstrate the importance sampling described in Subsection 4.3. Additionally, we apply the L-field (Djolonga and Krause, 2014; Djolonga et al., 2018) to obtain both the upper and lower bounds of log Z ϕ ( L ) since the DKPP is logsubmodular or log-supermodular for such λ . For all experiments reported in this subsection, we ran 30 trials and showed the means and standard deviations in the figures.

First, we set N = 16 and obtain the kernel parameters from L ∼ Wishart( L ; N, I ) /N for each hyperparameter λ ∈ [0 , 2]. Then, we evaluate the gaps from the ground truth log Z approx ϕ λ ( L ) -log Z ϕ λ ( L ) for each pair of ( λ, L ). Figure 3 shows the results. Although the ELBO and importance sampling seem to yield good estimates of the normalizing constant, the gaps of the L-fields become larger as λ moves away from 1. Fig-

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-f2d6bd41-3549-4690-8424-afb351460962.jpg)

Figure 3: Evaluated gaps log Z approx ϕ ( L ) -log Z ϕ ( L ). approximation qualities of Z - Ratio

Figure 4: Evaluated ratios Z approx ϕ ( L ) /Z ϕ ( L ). Variance of approximated logZ

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-797f0a04-eb59-4bf0-97af-6957db703daf.jpg)

Figure 5: Evaluated variances of importance sampling with and without mean-field approximation.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-ac4ec2e1-8879-4016-aa83-06fdc2f1e644.jpg)

ure 4 shows the more detailed behavior of the ELBO and proposed importance sampling through the ratio Z approx ϕ λ ( L ) /Z ϕ λ ( L ). Although the ELBO constructs a theoretical lower bound of the normalizing constant, it can take larger values than the ground truth owing to the evaluation error of the Monte Carlo approximation for the multilinear extension. We can see that the importance sampling achieves a better estimator than the ELBO, and the variance of the importance sampling also increases as λ moves away from 1, since the mean-field approximation for the proposal distribution becomes less accurate.

As an ablation study, we compare the importance sampling with and without the mean-field approximation for the proposal distribution. We set N = 64 and evaluate Var(log Z approx ϕ λ ( L )) for each λ . We use q 1 = · · · = q N = 0 5 for the without-mean-field pro-.

Figure 6: Learning curves with media . The LPSD takes 7 925 . × 10 -2 s per iteration and ratio matching takes 2 174 . × 10 -3 s per iteration.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-e975a8a7-a638-461b-888e-2895286a50e8.jpg)

Figure 7: Learning curves with apparel . The LPSD takes 6 091 . × 10 -1 s per iteration and ratio matching takes 4 155 . × 10 -3 s per iteration.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-e028accc-83d2-4e7f-950a-9a891dfcca19.jpg)

posal. As shown in Figure 5, the proposal distributions with the mean-field approximation significantly reduce the variance of the importance sampling.

## 6.4 Learning the Kernel Parameter

We demonstrate kernel learning methods on the Amazon Baby Registry dataset (Gillenwater et al., 2014). The dataset contains 13 categories of childcare products, and we use media ( N = 58 , M = 5 904) and , apparel ( N = 100 , M = 14 970) , categories. We compare the ratio matching introduced in Section 5 with the localized pseudo-spherical divergence (LPSD) (Takenouchi and Kanamori, 2015, 2017), which can measure the discrepancy between an empirical distribution and a probability function with finite support while avoiding the calculation of the normalizing constant. We set the Box-Cox transformation hyperparameter λ = 0 5 1 5 and the minibatch size for ratio . , . matching | Ω = 100. | Figures 6 and 7 show the learning curves. The normalizing constants are evaluated approximately by importance sampling. Overall, ratio matching performs better in both convergence and computational time.

## 7 CONCLUSION

In this study, we introduced DKPPs, a new family of distributions for random subsets that can seamlessly control positive and negative dependence. We developed methods for the probabilistic operations and inference in DKPPs for practical use, including the evaluation of expectations, the normalizing constant, and marginal and conditional probabilities. We also proposed an efficient learning method based on ratio matching. Empirically, we demonstrated the controllability of positive and negative dependence in DKPPs and conducted a subset acquisition experiment as the representative application. The effectiveness of the proposed computational algorithms was also shown numerically.

Although in this paper, we mainly focused on conceptual and practical motivation, many theoretical questions remain open. How do DKPPs connect to point processes on continuous spaces like the marginal kernel representation of DPPs? When do stronger conditions than log-submodularity hold as negative dependence in a DKPP? Furthermore, we will seek an understanding of how broad the DKPP family is as a set of distributions.

## Acknowledgements

We thank Satoshi Kuriki, Keisuke Yano, Yuki Saito, Yuki Hirakawa, Takuya Furusawa, and anonymous reviewers for helpful comments. This work was supported by JST CREST Grant Number JPMJCR2015, JSPS KAKENHI Grant Numbers JP22H03653 and 23H04483, and JST the establishment of university fellowships towards the creation of science technology innovation Grant Number JPMJFS2136.

## References

Ackley, D. H., Hinton, G. E., and Sejnowski, T. J. (1985). A learning algorithm for boltzmann machines. Cognitive Science , 9(1):147-169.

An, M. (1996). Log-concave Probability Distributions: Theory and Statistical Testing. Game Theory and Information, University Library of Munich, Germany.

Bach, F. (2013). Learning with Submodular Functions: A Convex Optimization Perspective .

Balog, M., Tripuraneni, N., Ghahramani, Z., and Weller, A. (2017). Lost Relatives of the Gumbel Trick. In Proceedings of the 34th International Conference on Machine Learning , pages 371-379.

Bhatia, R. (1997). Matrix Analysis , volume 169 of Graduate Texts in Mathematics .

Borcea, J., Br¨ and´n, e P., and Liggett, T. M. (2009). Negative Dependence and the Geometry of Polynomials. Journal of the American Mathematical Society , 22(2):521-567.

Borodin, A. and Rains, E. M. (2005). EynardMehta Theorem, Schur Process, and Their Pfaffian Analogs. Journal of Statistical Physics , 121(3):291317.

Borzadaran, G. M. and Borzadaran, H. M. (2011). Log-concavity property for some well-known distributions. Surveys in Mathematics and its Applications , 6:203-219.

Buchbinder, N., Feldman, M., Naor, J., and Schwartz, R. (2012). A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 649-658.

Buchbinder, N., Feldman, M., Naor, J. S., and Schwartz, R. (2014). Submodular Maximization with Cardinality Constraints. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1433-1452.

Calinescu, G., Chekuri, C., P´ al, M., and Vondr´ ak, J. (2007). Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract). In Integer Programming and Combinatorial Optimization , pages 182-196.

Casella, G. and Robert, C. P. (1996). RaoBlackwellisation of Sampling Schemes. Biometrika , 83(1):81-94.

Chakrabarty, D., Jain, P., and Kothari, P. (2014). Provable Submodular Minimization using Wolfe' s Algorithm. In Advances in Neural Information Processing Systems , volume 27.

Chekuri, C., Vondr´k, J., and Zenklusen, R. (2014). a Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. SIAM Journal on Computing , 43(6):18311879.

Derezinski, M., Liang, F., and Mahoney, M. (2020a). Bayesian Experimental Design Using Regularized Determinantal Point Processes. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics , pages 3197-3207.

Derezinski, M., Liang, F. T., Liao, Z., and Mahoney, M. W. (2020b). Precise expressions for random projections: Low-rank approximation and randomized Newton. In Advances in Neural Information Processing Systems , volume 33, pages 18272-18283.

Derezi´ski, n M. and Mahoney, M. W. (2021). Determinantal Point Processes in Randomized Numerical Linear Algebra. Notices of the American Mathematical Society , 68(01):1.

Derezi´ski, n M., Warmuth, M. K., and Hsu, D. (2022). Unbiased Estimators for Random Design Regression. Journal of Machine Learning Research , 23(167):1-46.

Diaconis, P. and Evans, S. N. (2000). Immanants and Finite Point Processes. Journal of Combinatorial Theory, Series A , 91(1):305-321.

Djolonga, J., Jegelka, S., and Krause, A. (2018). Provable Variational Inference for Constrained LogSubmodular Models. In Advances in Neural Information Processing Systems , volume 31.

Djolonga, J. and Krause, A. (2014). From MAP to Marginals: Variational Inference in Bayesian Submodular Models. In Advances in Neural Information Processing Systems , volume 27.

Doucet, A., de Freitas, N., Murphy, K. P., and Russell, S. J. (2000). Rao-blackwellised particle filtering for dynamic bayesian networks. In Conference on Uncertainty in Artificial Intelligence .

Dupuy, C. and Bach, F. (2018). Learning Determinantal Point Processes in Sublinear Time. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics , pages 244257.

Feige, U., Peleg, D., and Kortsarz, G. (2001). The Dense k -Subgraph Problem. Algorithmica , 29(3):410-421.

Fortuin, C. M., Ginibre, J., and Kasteleyn, P. W. (1971). Correlation inequalities on some partially ordered sets. Communications in Mathematical Physics , 22(2):89-103.

Friedland, S. and Gaubert, S. (2013). Submodular spectral functions of principal submatrices of a hermitian matrix, extensions and applications. Linear Algebra and its Applications , 438(10):3872-3884.

Fujishige, S., Hayashi, T., and Isotani, S. (2006). The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and Linear Programming.

Fujishige, S. and Isotani, S. (2011). A submodular function minimization algorithm based on the minimum-norm base. Pacific Journal of Optimization , 7(1):3-17.

Garey, M. R. and Johnson, D. S. (1979). Computers and intractability : a guide to the theory of NPcompleteness .

Gartrell, M., Paquet, U., and Koenigstein, N. (2017). Low-Rank Factorization of Determinantal Point

Processes. Proceedings of the AAAI Conference on Artificial Intelligence , 31(1).

Gillenwater, J., Kulesza, A., and Taskar, B. (2012). Near-Optimal MAP Inference for Determinantal Point Processes. In Advances in Neural Information Processing Systems , volume 25.

Gillenwater, J. A., Kulesza, A., Fox, E., and Taskar, B. (2014). Expectation-Maximization for Learning Determinantal Point Processes. In Advances in Neural Information Processing Systems , volume 27.

Gotovos, A., Hassani, H., and Krause, A. (2015). Sampling from Probabilistic Submodular Models. In Advances in Neural Information Processing Systems , volume 28.

Hazan, T. and Jaakkola, T. S. (2012). On the partition function and random maximum a-posteriori perturbations. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012 .

Hyv¨ arinen, A. (2005). Estimation of Non-Normalized Statistical Models by Score Matching. Journal of Machine Learning Research , 6(24):695-709.

Hyv¨ arinen, A. (2007). Some extensions of score matching. Computational Statistics &amp; Data Analysis , 51(5):2499-2512.

Iwata, S., Fleischer, L., and Fujishige, S. (2001). A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM , 48(4):761-777.

Iyer, R. and Bilmes, J. (2015). Submodular Point Processes with Applications to Machine learning. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics , pages 388-397.

Iyer, R., Jegelka, S., and Bilmes, J. (2013). Fast semidifferential-based submodular function optimization. In Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28 , ICML'13, pages III-855-III863.

Kawashima, T. and Hino, H. (2023). MinorizationMaximization for Learning Determinantal Point Processes. Transactions on Machine Learning Research .

Kulesza, A. and Taskar, B. (2011). K-Dpps: FixedSize Determinantal Point Processes. In International Conference on Machine Learning .

Kulesza, A. and Taskar, B. (2012). Determinantal Point Processes for Machine Learning. Foundations and Trends ® in Machine Learning , 5(2-3):123-286.

Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE , 86(11):2278-2324.

Liu, M., Liu, H., and Ji, S. (2022). Gradient-Guided Importance Sampling for Learning Binary EnergyBased Models. In The Eleventh International Conference on Learning Representations .

Macchi, O. (1975). The Coincidence Approach to Stochastic Point Processes. Advances in Applied Probability , 7(1):83-122.

Mariet, Z. and Sra, S. (2015). Fixed-Point Algorithms for Learning Determinantal Point Processes. In Proceedings of the 32nd International Conference on Machine Learning , pages 2389-2397.

Mariet, Z. E. and Sra, S. (2016). Kronecker Determinantal Point Processes. In Advances in Neural Information Processing Systems , volume 29.

Mariet, Z. E., Sra, S., and Jegelka, S. (2018). Exponentiated Strongly Rayleigh Distributions. In Advances in Neural Information Processing Systems , volume 31.

Mothilal, R. K., Sharma, A., and Tan, C. (2020). Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency , FAT* '20, pages 607-617.

Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming , 14(1):265-294.

Orlin, J. B. (2009). A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming , 118(2):237-251.

Papandreou, G. and Yuille, A. L. (2011). Perturb-andMAP random fields: Using discrete optimization to learn and sample from energy models. In 2011 International Conference on Computer Vision , pages 193-200.

Pemantle, R. (2000). Towards a theory of negative dependence. Journal of Mathematical Physics , 41(3):1371-1390.

Rebeschini, P. and Karbasi, A. (2015). Fast Mixing for Discrete Point Processes. In Proceedings of The 28th Conference on Learning Theory , pages 1480-1500.

Rubinstein, R. Y. and Kroese, D. P. (2008). Simulation and the Monte Carlo Method . Wiley Series in Probability and Statistics. 2nd ed edition.

Sch¨ olkopf, B., Smola, A., and M¨ uller, K.-R. (1997). Kernel principal component analysis. In Artificial Neural Networks - ICANN'97 , volume 1327, pages 583-588.

- Schrijver, A. (2000). A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. Journal of Combinatorial Theory, Series B , 80(2):346-355.
- Svitkina, Z. and Fleischer, L. (2011). Submodular Approximation: Sampling-based Algorithms and Lower Bounds. SIAM Journal on Computing , 40(6):1715-1737.
- Takenouchi, T. and Kanamori, T. (2015). Empirical Localization of Homogeneous Divergences on Discrete Sample Spaces. In Advances in Neural Information Processing Systems , volume 28.
- Takenouchi, T. and Kanamori, T. (2017). Statistical Inference with Unnormalized Discrete Models and Localized Homogeneous Divergences. Journal of Machine Learning Research , 18(56):1-26.
- Tschiatschek, S., Djolonga, J., and Krause, A. (2016). Learning Probabilistic Submodular Diversity Models Via Noise Contrastive Estimation. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics , pages 770-779.
- Valiant, L. G. (1979). The complexity of computing the permanent. Theoretical Computer Science , 8(2):189-201.
- Vere-Jones, D. (1997). Alpha-permanents and their applications to multivariate gamma, negative binomial and ordinary binomial distributions. New Zealand J. Math , 26(1):125-149.
- Wilhelm, M., Ramanathan, A., Bonomo, A., Jain, S., Chi, E. H., and Gillenwater, J. (2018). Practical Diversified Recommendations on YouTube with Determinantal Point Processes. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management , pages 2165-2173.
- Zhang, R., Liu, X., and Liu, Q. (2022). A Langevinlike Sampler for Discrete Distributions. In Proceedings of the 39th International Conference on Machine Learning , pages 26375-26396.

## Checklist

- 1. For all models and algorithms presented, check if you include:
- (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes]
- (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [No]
- (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Yes]
- 2. For any theoretical claim, check if you include:
- (a) Statements of the full set of assumptions of all theoretical results. [Yes]
- (b) Complete proofs of all theoretical results. [Yes]
- (c) Clear explanations of any assumptions. [Yes]
- 3. For all figures and tables that present empirical results, check if you include:
- (a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes]
- (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes]
- (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes]
- (d) Adescription of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes]
- 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include:
- (a) Citations of the creator If your work uses existing assets. [Yes]
- (b) The license information of the assets, if applicable. [Not Applicable]
- (c) New assets either in the supplemental material or as a URL, if applicable. [Not Applicable]
- (d) Information about consent from data providers/curators. [Yes]
- (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable]
- 5. If you used crowdsourcing or conducted research with human subjects, check if you include:
- (a) The full text of instructions given to participants and screenshots. [Not Applicable]
- (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable]
- (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

## A PROOFS

## A.1 Proof of Proposition 3.3

Proof. Let A ⊆ Y be a random subset following the DKPP P ϕ ( A ; L ), and let z = ( z , . . . , z 1 N ) ⊤ denote the indicator vector of A :

$$z _ { i } = \begin{cases} \ 0 & \text{if $i\notin \mathcal{A}$}, \\ 1 & \text{if $i\in \mathcal{A}$}, \end{cases}$$

for i = 1 , . . . , N . Then, we obtain

̸

$$z _ { i } & = \Big \{ 1 \quad \text{if $i\in\mathcal{A}$}, \\ 1, \dots, N. \text{ Then, we obtain} \\ P _ { \phi } ( \mathcal { A } ; L ) & \circ \exp \text{tr} \phi ( L [ \mathcal { A } ] ) \\ & = \exp \text{tr} \left ( a L [ \mathcal { A } ] L [ \mathcal { A } ] + b L [ \mathcal { A } ] + c I \right ) \\ & = \exp \left ( a \| L [ \mathcal { A } ] \| _ { F } ^ { F } + b \text{tr} L [ \mathcal { A } ] + c | \mathcal { A } | \right ) \\ & = \exp \left ( a \sum _ { i, j \in \mathcal { A } } | L _ { i j } | ^ { 2 } + \sum _ { i \in \mathcal { A } } ( b L _ { i i } + c ) \right ) \\ & = \exp \left ( a \sum _ { i, j = 1 } ^ { N } | L _ { i j } | ^ { 2 } z _ { i } z _ { j } + \sum _ { i = 1 } ^ { N } ( b L _ { i i } + c ) z _ { i } \right ) \\ & = \exp \left ( a \sum _ { i \neq j } | L _ { i j } | ^ { 2 } z _ { i } z _ { j } + a \sum _ { i = 1 } ^ { N } L _ { i } ^ { 2 } z _ { i } ^ { 2 } + \sum _ { i = 1 } ^ { N } ( b L _ { i i } + c ) z _ { i } \right ) \\ & = \exp \left ( a \sum _ { i \neq j } | L _ { i j } | ^ { 2 } z _ { i } z _ { j } + a \sum _ { i = 1 } ^ { N } L _ { i } ^ { 2 } z _ { i } + \sum _ { i = 1 } ^ { N } ( b L _ { i i } + c ) z _ { i } \right ). \\ \text{parg} \left ( A. 1 \right ) \text{ and } ( 4 ), \text{we prove the proposition}. \quad \quad \ \Box \Big \} \\ \text{roof of Proposition } 3. 5$$

̸

̸

By comparing (A.1) and (4), we prove the proposition.

## A.2 Proof of Proposition 3.5

Proof. [ ϕ is affine = ⇒ DKPP is log-modular]

We denote the diagonal matrix with the eigenvalues of L [ A ] by Λ A . By letting ϕ x ( ) = bx + from the assumption, c we find that the log-likelihood of the DKPP is

$$\Lambda _ { \Lambda } \log P _ { \phi } ( \mathcal { A } ; L ) = \text{tr} \phi ( L [ \mathcal { A } ] ) - \log Z _ { \phi } ( L ) & = \text{tr} ( b \Lambda _ { \mathcal { A } } + c I ) - \log Z _ { \phi } ( L ) \\ & = b \text{tr} \Lambda _ { \mathcal { A } } + c | \mathcal { A } | - \log Z _ { \phi } ( L ) \\ & = b \text{tr} L _ { \mathcal { A } } + c | \mathcal { A } | - \log Z _ { \phi } ( L ) \\ & = \sum _ { i \in \mathcal { A } } ( b L _ { i i } + c ) - \log Z _ { \phi } ( L ). \\ \Lambda _ { \Lambda } \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \sigma \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \ dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots.$$

This is a modular function for A ⊆ Y .

[DKPP is log-modular = ⇒ ϕ is affine]

The goal of this proof is show the affinity of the single-variable function ϕ : R ≥ 0 → R . From the log-modularity of the DKPP, we have

$$\text{tr} \phi ( L [ \mathcal { S } ] ) + \text{tr} \phi ( L [ \mathcal { T } ] ) = \text{tr} \phi ( L [ \mathcal { S } \cup \mathcal { T } ] ) + \text{tr} \phi ( L [ \mathcal { S } \cap \mathcal { T } ] )$$

̸

for every S T , ⊆ Y . By defining g x ( ) := ϕ x ( ) -ϕ (0), we can represent ϕ as ϕ x ( ) = g x ( ) + ϕ (0). Note that g is continuous because of the continuity of ϕ , assumed in Definition 3.1. Now, we take S = { } T i , = { } j ( i = ) and j the kernel matrix L arbitrarily to satisfy L ij = √ L L ii jj ∈ R . Since L and ϕ are independent, this choice of L does not impose any restriction on ϕ .

The two eigenvalues of L [ S ∪ T ] ∈ R 2 × 2 are given by λ 1 = L ii + L jj and λ 2 = 0. The l.h.s. of (A.2) is

$$\text{tr} \phi ( \mathcal { L } [ \mathcal { S } ] ) + \text{tr} \phi ( \mathcal { L } [ \mathcal { T } ] ) = \phi ( L _ { i i } ) + \phi ( L _ { j j } ),$$

and the r.h.s. is

$$\ t r \phi ( \mathcal { L } [ \mathcal { S } \cup \mathcal { T } ] ) + \ t r \phi ( \mathcal { L } [ \mathcal { S } \cap \mathcal { T } ] ) = \ t r \phi ( \mathcal { L } [ \mathcal { S } \cup \mathcal { T } ] ) = \phi ( \lambda _ { 1 } ) + \phi ( \lambda _ { 2 } ).$$

Therefore, we have the identity

$$\phi ( L _ { i i } ) + \phi ( L _ { j j } ) = \phi ( \lambda _ { 1 } ) + \phi ( \lambda _ { 2 } ).$$

By substituting ϕ x ( ) = g x ( ) + ϕ (0) into (A.3), it becomes

$$& \{ g ( L _ { i i } ) + \phi ( 0 ) \} + \{ g ( L _ { j j } ) + \phi ( 0 ) \} = \{ g ( \lambda _ { 1 } ) + \phi ( 0 ) \} + \{ g ( \lambda _ { 2 } ) + \phi ( 0 ) \} \\ & \quad \Longleftrightarrow \ g ( L _ { i i } ) + g ( L _ { j j } ) = g ( \lambda _ { 1 } ) + g ( \lambda _ { 2 } ) = g ( L _ { i i } + L _ { j j } ) + g ( 0 ) = g ( L _ { i i } + L _ { j j } ).$$

Because L ii and L jj are arbitrary on R ≥ 0 , we have g x ( ) + g y ( ) = g x ( + ) for all y x, y ∈ R ≥ 0 . From the continuity of g , this means that g must be linear and ϕ must be affine.

## A.3 Proof of Proposition 4.1

Proof. We consider the partition of Y given by A sub , Y\A sup , A sup \A sub and separate the random vector ξ = ( ξ 1 , . . . , ξ N ) ⊤ by ξ + := ( ξ i ) i ∈A sub , ξ -:= ( ξ i ) i ∈Y\A sup , and ξ ◦ := ( ξ i ) i ∈A sup \A sub . For example, when Y = { 1 2 3 4 5 , , , , } A , sub = { 1 2 , } , and A sup = { 1 2 4 5 , , , } ⊇ ( A sub ), the separation of ξ becomes ξ + = ( ξ 1 , ξ 2 ) ⊤ , ξ -= ( ξ 3 ), and ξ ◦ = ( ξ 4 , ξ 5 ) ⊤ . We also denote N + := |A sub | , N -:= |Y\A sup | , and N ◦ := |A sup \A sub | and ξ + ∼ Q q + , ξ -∼ Q q -, and ξ ◦ ∼ Q q ◦ , where Q q + := ∏ i ∈A sub Q q i ( ξ i ) , Q q -:= ∏ i ∈Y\A sup Q q i ( ξ i ), and Q q ◦ := ∏ i ∈A sup \A sub Q q i ( ξ i ). We denote the probability measure that induces Q q + by Q q + and the same for Q q -and Q q ◦ .

As shown in (10), E ξ ∼ Q q [ w ( A ξ ) 1 ( A sub ⊆ A ξ ⊆ A sup )] is equal to P ( A sub ⊆ A ⊆ A sup ). The tower property of expectation states that E X [ f ( X )] = E Y [ E X [ f ( X Y ) | ]] generally holds for an arbitrary pair of random variables

( X,Y ) and an arbitrary function f . By choosing X ← ξ and Y ← ξ + (and Y ← ξ -), we have

$$\begin{array} {$$

which is the first half of Proposition 4.1.

On the other hand, the tower property of variance states that Var X [ f ( X )] = E Y [Var X [ f ( X Y ) | ]] + Var Y [ E X [ f ( X Y ) | ]] ≤ Var Y [ E X [ f ( X Y ) | ]] . This ensures the latter half of Proposition 4.1.

## A.4 Proof of Proposition 4.2

Proof. First, we define independent Bernoulli trials Q q as in (2) with q 1 = · · · = q N =: q . By importance sampling, we have

$$\mathbb { P } ( | \mathcal { A } | = k ) = \sum _$$

in the similar way to (10), where w ( A ξ ) = P ( A ξ ) /Q q ( ξ ) is the weight function. Then, we introduce a new random variable, ζ := ∑ N i =1 ξ i , that follows the binomial distribution: ξ ∼ Bin( N,q ). Now, we consider the

Rao-Blackwellization of (A.4) by the auxiliary random variable ζ :

̸

$$\text{my or previous or random sources for confusing resolve and negative performance} \\ \text{ck$$

Because ξ 1 , . . . , ξ N are i.i.d. such that ξ i ∼ Bernoulli( q ), the conditional expectation in the r.h.s. of (A.5) equals to the expectation over the uniform distribution on {A ⊆ Y : |A| = k } .

## B MEAN-FIELD APPROXIMATION

↦

We derive the update rule of the mean-field approximation (7) for completeness. It is recommended to also refer to the thesis by Djolonga et al. (2018, Section 3) since the derivation is equivalent. Let ξ ∈ { 0 1 , } N denote a binary random vector, f : 2 Y → R be a set function, and P : ξ → Z -1 exp( f ( A ξ )) be a probabilistic function on { 0 1 , } N , or equivalently 2 Y . Now, we consider minimizing KL( Q q ∥ P ), where Q q is defined in (2). Given

$$\text{KL} ( Q _ { q } \| P ) = \mathbb { E$$

the minimization of KL( Q q ∥ P ) is equivalent to maximizing the ELBO, defined as

$$L ( q ) \coloneqq - \mathbb { E } _ { \xi \sim Q$$

We solve the problem max q L ( q ) by using the coordinate ascent. The derivative ∂L ( q ) ∂q i is

̸

$$\text{We solve the problem max} _ { q } L ( q ) & = \frac { \partial L ( q ) } { \partial q _ { i } } \left \{ \sum _ { j = 1 } ^ { N } ( - q _ { j } \log q _ { j } - ( 1 - q _ { j } ) \log ( 1 - q _ { j } ) ) + \sum _ { \mathcal { A } \subset \mathcal { Y } } f ( \mathcal { A } ) \prod _ { j \in \mathcal { A } } q _ { j } \prod _ { j \not \in \mathcal { A } } ( 1 - q _ { j } ) \right \} \\ & = \log \frac { 1 - q _ { i } } { q _ { i } } + \sum _ { \mathcal { A } i \in \mathcal { A } } \ f ( \mathcal { A } ) \prod _ { j \in \mathcal { A } } q _ { j } \prod _ { j \not \in \mathcal { A } } ( 1 - q _ { j } ) - \sum _ { \mathcal { A } i \not \in \mathcal { A } } f ( \mathcal { A } ) \prod _ { j \in \mathcal { A } } q _ { j } \prod _ { j \not \in \mathcal { A } } ( 1 - q _ { j } ) \\ & = \log \frac { 1 - q _ { i } } { q _ { i } } + \sum _ { \mathcal { A } \subset \mathcal { Y } \vee \{ i \} } \left [ f ( \mathcal { A } \cup \{ i \} ) - f ( \mathcal { A } ) \right ] \prod _ { j \in \mathcal { A } } q _ { j } \prod _ { j \not \in \mathcal { A } } ( 1 - q _ { j } ) \\ & = \log \frac { 1 - q _ { i } } { q _ { i } } + \mathbb { E } _ { \xi \downarrow \sim Q _ { \tau, \tau } } [ f ( i | \mathcal { A } _ { \xi \downarrow } ) ].$$

̸

By solving the equation

$$\log \frac { 1 - q _ { i } } { q _ { i } } + \mathbb { E } _ { \xi _ { \vee i } \sim Q _ { q _ { \vee i } } } [ f ( i | \mathcal { A } _ { \xi _ { \vee i } } ) ] = 0,$$

we obtain the update rule (7). We know KL( Q q ∥ P ) ≥ 0, leading to the inequality log Z ≥ L ( q ). Therefore, we can evaluate the tightened lower bound of log Z using the optimized q .

## C GRADIENT OF RATIO MATCHING

In this section, we derive the gradient of the loss function from ratio matching (14) in analytical form. By defining u m,n := exp(tr ϕ ( L [ A m ]) -tr ϕ ( L [ A ¯ n m ])), we obtain

$$\frac { \partial J ( L ) } { \partial L } = \sum _ { m, n } \frac { d g ( u _ { m, n } ) ^ { 2 } } { d u _ { m, n } } \frac { \partial u _ { m, n } } { \partial L } = - 2 \sum _ { m, n } \frac { g ( u _ { m, n } ) } { ( 1 + u _ { m, n } ) ^ { 2 } } \frac { \partial u _ { m, n } } { \partial L }.$$

Here, U A denotes the N ×|A| binary matrix such that L [ A ] = U LU ⊤ A A . Then,

$$\frac { \partial } { \partial L } \text{tr} \phi ( \mathcal { L } [ \mathcal { A } ] ) = U _ { \mathcal { A } } ^ { \top } \phi ^ { \prime } ( \mathcal { L } [ \mathcal { A } ] ) U _ { \mathcal { A } },$$

where ϕ ′ is the derivative of the univariate scalar function ϕ . Therefore, the remaining term in (C.6) becomes

$$\frac { \partial u _ { m, n } } { \partial L } = u _ { m, n } ( U _ { \mathcal { A } _ { m } } ^ { \top } \phi ^ { \prime } ( L [ \mathcal { A } _ { m } ] ) U _ { \mathcal { A } _ { m } } - U _ { \mathcal { A } _ { m } ^ { n } } ^ { \top } \phi ^ { \prime } ( L [ \mathcal { A } _ { m } ^ { \bar { n } } ] ) U _ { \mathcal { A } _ { m } ^ { n } } ).$$

Consequently, the derivative we seek is

$$\frac { \partial J ( \mathcal { L } ) } { \partial L } = - 2 \sum _ { m, n } \frac { u _ { m, n } g ( u _ { m, n } ) } { ( 1 + u _ { m, n } ) ^ { 2 } } ( U _ { \mathcal { A } _ { m } } ^ { \top } \phi ^ { \prime } ( \mathcal { L } [ \mathcal { A } _ { m } ] ) U _ { \mathcal { A } _ { m } } - U _ { \mathcal { A } _ { m } ^ { \bar { n } } } ^ { \top } \phi ^ { \prime } ( \mathcal { L } [ \mathcal { A } _ { m } ^ { \bar { n } } ] ) U _ { \mathcal { A } _ { m } ^ { \bar { n } } } ).$$

For evaluating the gradient (C.7), computing u m,n requires O |A ( m | 3 ) time complexity, and U ⊤ A m ϕ ′ ( L [ A m ]) U A m also takes O |A ( m | 3 ) because U A m has only |A m | non-zero elements. Computing U ⊤ A ¯ n m ϕ ′ ( L [ A ¯ n m ]) U A ¯ n m takes O (( |A m | +1) ) = 3 O |A ( m | 3 ). By taking the complexity from the sum of N × N matrices into account, we obtain the whole complexity O ( ∑ ( m,n ) ∈ Ω |A m | 3 + Ω | | N 2 ) = O | ( Ω ( | κ 3 + N 2 )) with the minibatch Ω.

In practical scenarios, V ∈ R N × D such that L = V V ⊤ is often learned to keep L positive (semi-)definite in learning steps. If D &lt; N , the low-rank kernel matrix is obtained. Then, the gradient with respect to V becomes

$$\frac { \partial J ( \mathcal { L } ) } { \partial V } & = 2 \frac { \partial J ( \mathcal { L } ) } { \partial L } V \\ & = - 4 \sum _ { m, n } \frac { u _ { m, n } g ( u _ { m, n } ) } { ( 1 + u _ { m, n } ) ^ { 2 } } ( U _ { \mathcal { A } _ { m } } ^ { \top } \phi ^ { \prime } ( L [ \mathcal { A } _ { m } ] ) U _ { \mathcal { A } _ { m } } V - U _ { \mathcal { A } _ { m } ^ { n } } ^ { \top } \phi ^ { \prime } ( L [ \mathcal { A } _ { m } ^ { \bar { n } } ] ) U _ { \mathcal { A } _ { m } ^ { n } } V ).$$

Since U A m V is the |A m | × D dense matrix, the time complexity of (C.8) is O ( ∑ ( m,n ) ∈ Ω ( |A m | 3 + D |A m | 2 ) + | Ω | ND ) = O | ( Ω ( | κ 2 max { κ, D } + ND )). The term O | ( Ω | ND ) arises from matrix additions, which still ensures scalability as M and/or N increases even if D = N .

## D FURTHER EXPERIMENTS

## D.1 Subset Acquiring Experiment

Here, we show additional results of the subset acquiring experiment in Section 6. As stated in Section 6, the kernel matrix L is constructed from the Gaussian kernel with the bandwidth parameter determined by the median heuristic. We can make the centered kernel matrix ˜ := ( L I -11 ⊤ /N ) L I ( -11 ⊤ /N ) and apply kernel principal component analysis (PCA) to ˜ (Sch¨lkopf et al., 1997). L o Figure 8 shows the first and second principal components of the MNIST obtained by the kernel. We can see that the kernel has a certain capability for class separation.

In Figures 9, 10, and 11, we show 10 randomly chosen acquired subsets for each ( β, λ ) ∈ { 1 10 50 , , } × { 0 1 2 , , } . It is visually evident that the attractive power increases as λ and β become larger.

Figure 8: Kernel PCA for MNIST.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-50de7a60-22e3-42eb-9011-6937fdcf7213.jpg)

Figure 9: Examples of the acquired subsets of MNIST for β = 1.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-b9800af4-31b7-49e2-a832-83d3e4512c0e.jpg)

Figure 10: Examples of the acquired subsets of MNIST for β = 10.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-ceb6773a-73c8-440c-9440-528bf95659f4.jpg)

Figure 11: Examples of the acquired subsets of MNIST for β = 50.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-1b2a505d-07bf-4bae-999b-39e857229ac8.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-b026ca5e-8a39-4f7a-b87d-d127915a6edd.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01022v2-figure-6b1dc3d6-3e08-4642-bd51-b1e15235c861.jpg)
Takahiro Kawashima Hideitsu Hino
A Family of Distributions of Random Subsets for Controlling Positive and Negative Dependence
Positive and negative dependence are fundamental concepts that characterize
the attractive and repulsive behavior of random subsets. Although some
probabilistic models are known to exhibit positive or negative dependence, it
is challenging to seamlessly bridge them with a practicable probabilistic
model. In this study, we introduce a new family of distributions, named the
discrete kernel point process (DKPP), which includes determinantal point
processes and parts of Boltzmann machines. We also develop some computational
methods for probabilistic operations and inference with DKPPs, such as
calculating marginal and conditional probabilities and learning the parameters.
Our numerical experiments demonstrate the controllability of positive and
negative dependence and the effectiveness of the computational methods for
DKPPs.