Real-world relationships are rarely one-sided. In a recommendation system, items can be complementary (attraction: buying a camera makes you highly likely to buy a lens) or substitutes (repulsion: buying a Pepsi makes you highly unlikely to buy a Coke). Ideally, a machine learning model should capture both dynamics simultaneously to accurately reflect the underlying data distribution.
However, many traditional probabilistic, geometric, and kernel-based frameworks suffer from a fundamental sign constraint: they are mathematically locked into modeling only positive correlations or only negative correlations. A major thrust of recent research focuses on breaking these rigid constraints to allow full-range dependency modeling.
The Negative-Only Trap of Symmetric DPPs
Determinantal Point Processes (DPPs) are widely celebrated for their ability to model diversity and repulsion. As explained by Kulesza et al. in Determinantal Point Processes for Machine Learning, traditional structured models like Markov Random Fields struggle with negative correlations, making DPPs an elegant alternative for subset selection tasks like document summarization or search diversification.
Yet, standard DPPs suffer from their own mathematical straightjacket. They rely on a symmetric kernel matrix $L$, where the probability of selecting a subset of items $Y$ is proportional to the determinant of the corresponding submatrix:
$$P(Y) \propto \det(L_Y)$$
To build intuition for why this limits the model to negative correlations, consider the geometric interpretation of a determinant. The determinant $\det(L_Y)$ represents the squared volume of a parallelotope spanned by the feature vectors of the items in $Y$.
If two items are highly similar, their feature vectors point in nearly the same direction. Geometrically, this causes the parallelotope to flatten, shrinking its volume toward zero. This correctly assigns a low probability to selecting both items together, capturing repulsion.
But what happens if two items are highly attractive and should co-occur? To maximize their joint probability, their vectors would need to align perfectly. However, aligning the vectors collapses the volume to zero, making their co-occurrence impossible under the model. As noted by Gartrell et al. in Learning Nonsymmetric Determinantal Point Processes, this symmetry constraint strictly prevents standard DPPs from capturing positive associations or synergies.
The Positive-Only Constraint in Geometric and Kernel Models
While DPPs are trapped in a negative-only world, many other foundational machine learning frameworks suffer from the exact opposite problem: they can only represent positive or non-negative correlations.
For instance, standard Gaussian Process (GP) kernels typically measure similarity using distance metrics or inner products that decay to zero but never drop below it. As argued by Wilson et al. in Gaussian Process Kernels for Pattern Discovery and Extrapolation, this positive-only restriction prevents GPs from capturing oscillatory patterns or physical processes where variables move in opposite directions over specific intervals.
A similar limitation appears across clustering, representation learning, and Bayesian nonparametrics:
- Hypergraph and Hierarchical Clustering: Many formulations for group discovery require strictly positive affinity values. Leordeanu et al. point out in Efficient Hypergraph Clustering that this prevents modeling mutual exclusion in tasks like image segmentation. Similarly, Gray et al. demonstrate in Hierarchical clustering with dot products recovers hidden tree structure that assuming non-negative correlations fails in domains like finance where strong inhibitory relationships exist.
- Knowledge Graph Embeddings: Geometric models often use cones or regions to represent hierarchies, which naturally capture containment but struggle with disjointness. In Probabilistic Embedding of Knowledge Graphs with Box Lattice Measures, Vilnis et al. show that failing to model negative correlations makes it impossible to represent mutually exclusive concepts (e.g., knowing that an entity cannot be both a "dog" and a "plant").
- Bayesian Nonparametrics: Traditional mixed-membership models and dependent random probabilities often assume independent or positively correlated features. As discussed by Wood et al. in their Discussion of "The Discrete Infinite Logistic Normal Distribution for Mixed-Membership Modeling", these frameworks lack the mathematical flexibility to model features that rarely or never co-occur. To address this, Ascolani et al. in Nonparametric priors with full-range borrowing of information and Lee et al. in Logistic-Beta Processes for Dependent Random Probabilities with Beta Marginals have designed new classes of priors that allow full-range borrowing of information across both positive and negative signs.
Breaking the Sign Barrier
To build models capable of reflecting real-world complexity, researchers have focused on relaxing these rigid sign constraints.
The most prominent breakthrough comes from Nonsymmetric Determinantal Point Processes (NDPPs). By decomposing the kernel matrix $L$ into a symmetric part (which captures item similarities and repulsion) and an anti-symmetric part (which captures directed co-occurrences and attraction), NDPPs break the volume-collapse trap. As shown by Gartrell et al. in Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes, this mathematical relaxation allows the model to capture both diversity and item synergies simultaneously.
Alternatively, Brunel proposed Signed DPPs in Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem to solve the principal minor assignment problem for nonsymmetric matrices, unlocking polynomial-time learning for both attractive and repulsive interactions.
Overcoming Computational Bottlenecks
While removing sign constraints makes models vastly more expressive, it introduces severe computational challenges. For instance, evaluating or sampling from an NDPP traditionally scales cubically ($O(M^3)$) with the number of items. To make these flexible models practical for massive real-world datasets, a suite of algorithmic innovations has emerged:
- Efficient Inference: Gartrell et al. introduced a kernel decomposition that slashes the complexity of Maximum A Posteriori (MAP) inference from cubic to linear time ($O(M)$). For streaming data, Reddy et al. developed one-pass streaming algorithms in One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes using local search and candidate stashes.
- Scalable Sampling: Exact sampling has been accelerated by orders of magnitude. In Scalable Sampling for Nonsymmetric Determinantal Point Processes, Han et al. leveraged low-rank kernel structures and rejection sampling to achieve massive speedups. For larger ground sets, Han et al. developed a tree-based Markov chain Monte Carlo (MCMC) sampler in Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes that drops transition complexity to logarithmic time. Finally, Song et al. in Fast Dynamic Sampling for Determinantal Point Processes utilized batching and fast matrix multiplication to optimize dynamic sampling scenarios.
Key Foundational Work
Determinantal Point Processes for Machine Learning (2012) — contributed 3 concept elements to this direction.
Discussion of "The Discrete Infinite Logistic Normal Distribution for Mixed-Membership Modeling" (2011) — contributed 1 concept elements to this direction.
Efficient Hypergraph Clustering (2012) — contributed 1 concept elements to this direction.