Implementation:Interpretml Interpret SPOTgreedy

Knowledge Sources	Interpretml Interpret
Domains	Machine_Learning, Interpretability
Last Updated	2026-02-07 12:00 GMT

Overview

SPOT_GreedySubsetSelection implements the SPOTgreedy algorithm for selecting a set of prototypes from a dataset using optimal transport, as described in the SPOT framework paper.

Description

This module implements the greedy prototype selection algorithm from the SPOT (Selection of Prototypes using Optimal Transport) framework:

• SPOT_GreedySubsetSelection: A greedy algorithm that selects m prototype points from a set of candidate source points such that the selected prototypes best represent a target distribution in the optimal transport sense. The algorithm works by iteratively selecting the source point that maximally reduces the transport cost between the selected prototypes and the target distribution.

The algorithm proceeds as follows:

1. Initialize with empty prototype set
2. At each iteration, evaluate remaining candidates by computing the incremental reduction in transport cost each would provide
3. Select the candidate with the maximum incremental improvement
4. Update the current minimum cost values and source assignments
5. After selecting all m prototypes, compute the optimal transport plan as a sparse matrix and derive the prototype weights

The implementation uses scipy sparse matrices (csr_matrix) for the optimal transport plan computation.

This algorithm is referenced in: SPOT: A framework for selection of prototypes using optimal transport

Usage

Use SPOT_GreedySubsetSelection when you need to select a representative subset of prototypes from a larger dataset, where the selected prototypes should optimally represent the target data distribution in terms of transport cost. This is useful for dataset summarization, exemplar-based explanations, or creating representative training subsets.

Code Reference

Source Location

• Repository: Interpretml_Interpret
• File: python/interpret-core/interpret/utils/_SPOTgreedy.py

Signature

def SPOT_GreedySubsetSelection(C, targetMarginal, m):

Import

from interpret.utils._SPOTgreedy import SPOT_GreedySubsetSelection

I/O Contract

Inputs

Name	Type	Required	Description
C	numpy array (numY x numX)	Yes	Cost matrix of optimal transport: rows are source (candidate) points, columns are target points
targetMarginal	numpy array (1 x numX)	Yes	Histogram of the target distribution; non-negative entries that will be normalized to sum to 1
m	int	Yes	Number of prototypes to select

Outputs

Name	Type	Description
S	numpy array (m,)	Indices of the selected prototype points (indices into the rows of C)
currOptw	numpy array (m,)	Optimal weights for each selected prototype in the transport plan

Algorithm Details

The greedy selection works as follows:

1. Initialization: Set up tracking arrays for current minimum costs, source assignments, and remaining candidates
2. Iterative Selection (repeat m times):
   1. For each remaining candidate, compute how much it would reduce the transport cost: max(currentMinCost - candidateCost, 0) * targetMarginal
   2. Select the candidate with the largest total cost reduction
   3. Update the running minimum cost vector and source assignments
3. Transport Plan: After all prototypes are selected, construct the sparse optimal transport matrix and compute per-prototype weights by summing their transport allocations

The time complexity is approximately O(m * numY * numX) since each of the m iterations evaluates all remaining candidates against all target points.

Usage Examples

Basic Example

from interpret.utils._SPOTgreedy import SPOT_GreedySubsetSelection
import numpy as np

# Create a cost matrix (e.g., pairwise distances)
numY = 100  # candidate points
numX = 50   # target points
C = np.random.rand(numY, numX)

# Uniform target distribution
targetMarginal = np.ones(numX) / numX

# Select 10 prototypes
m = 10
selected_indices, weights = SPOT_GreedySubsetSelection(C, targetMarginal, m)

print(f"Selected prototype indices: {selected_indices}")
print(f"Prototype weights: {weights}")

Related Pages

• Principle:Interpretml_Interpret_Optimal_Transport_Selection