Neighborhood Generation

For natural language, the neighborhood is generated by randomly removing or replacing tokens from the original instance.

• Mechanism: A binary vector represents the presence or absence of words in a bag-of-words or TF-IDF representation.
• Perturbation: Tokens are randomly set to zero (masked) to create distorted versions of the document.
• Distance Metric: Cosine distance is typically used to measure similarity between the original and perturbed documents.
• Interpretable Representation: The surrogate model operates on individual word presence, making explanations like 'the word terrible decreased the positive sentiment score' directly human-readable.

Images are segmented into superpixels—contiguous groups of perceptually similar pixels—which become the interpretable features.

• Segmentation: Algorithms like QuickShift or SLIC partition the image into atomic regions that respect object boundaries.
• Perturbation: Random superpixels are turned 'off' by replacing them with a neutral color (e.g., gray or the dataset mean).
• Fidelity: The surrogate model learns which superpixels are most predictive of the classification.
• Output: A saliency mask highlights the image regions that most strongly influenced the model's decision, answering 'where did the model look?'

For structured numerical and categorical data, neighborhoods are created by sampling around the instance of interest.

• Numerical Features: Values are perturbed by drawing from a normal distribution centered on the original value with a specified standard deviation.
• Categorical Features: Categories are randomly switched according to the empirical distribution observed in the training data.
• Discretization: Continuous features may be binned into quantiles to create a more human-friendly interpretable domain for the surrogate model.
• Weighting: An exponential kernel assigns higher importance to perturbed samples that are closer to the original instance in Euclidean space.

Regardless of modality, all perturbation strategies rely on a kernel function to enforce the locality constraint.

• Exponential Kernel: The default weighting function in LIME, defined as exp(-D(x, z)^2 / sigma^2), where D is a distance function and sigma is the kernel width.
• Kernel Width: This critical hyperparameter controls the effective size of the local neighborhood. A small width enforces strict locality but may produce unstable explanations.
• OptiLIME: An optimization framework that automatically selects the optimal kernel width by balancing local fidelity against explanation stability across multiple runs.
• Locally Weighted Regression: The statistical backbone of the algorithm, fitting a simple model to a localized subset of data weighted by proximity.

Once the perturbed neighborhood is generated and weighted, an interpretable model is trained to mimic the black-box predictions.

• Sparse Linear Model: Lasso regression (L1-regularized) is the standard choice, forcing the coefficients of less important features to exactly zero.
• Feature Selection: The non-zero coefficients become the explanation, typically limited to a small number (e.g., top 5-10 features) for human consumption.
• Bayesian LIME: An extension using Bayesian ridge regression that provides uncertainty estimates alongside feature importance scores, indicating the confidence of the explanation itself.
• Fidelity-Interpretability Trade-off: The surrogate must balance accurately approximating the local decision boundary against remaining simple enough for a human to understand.

A critical quality metric for neighborhood generation is the consistency of explanations across different random seeds.

• Stability Definition: The property that identified important features remain consistent across multiple runs, indicating they are robust rather than artifacts of the sampling process.
• Explanation Regularization: Adding penalty terms to the surrogate's training objective to enforce smoothness and sparsity, directly controlling explanation complexity.
• Submodular Pick: An algorithm for selecting a diverse, non-redundant set of individual instance explanations to provide a global overview of model behavior for human review.
• Anchor Explanations: A successor to LIME providing high-precision if-then rules that guarantee a prediction remains unchanged regardless of changes to other feature values not in the rule.