Order of nominal feature levels change the results

[aswer-svg]

Hi,

I am building an EBM regressor with some nominal and continuous features with only main effects. I have tried ordering the nominal features by the mean of the response for better visualization. For example, if a feature has levels named ["cat", "dog", "fish"], the transformed levels would be ["2-cat", "0-dog", "1-fish"], where the number at the start indicate the order with respect to the mean of the response.

With this transformation, the scores of transformed feature levels change a lot. I had a categorical feature whose importance was quite low before the transformation, and it is the most important feature after this transformation.

I didn't specify the feature_types parameter, and the categorical features has type "nominal" when inspecting feature_types_in_.

As far as I know, EBM uses Fischer method for nominal categoricals, so the order shouldn't matter.

Can you please clarify the underlying cause of this discrepancy in the model results?

Take care,

[paulbkoch]

Thanks @aswer-svg -- This is very interesting and sounds like it might be a bug. Can you tell us what version of interpret you are using? Categorical handling is fairly new.

[aswer-svg]

I experienced this issue on 0.7.0, and I'm able to recreate this on 0.7.2.

[paulbkoch]

@aswer-svg -- The smoothing rounds seem to be causing this effect. Fischer is only applied to categoricals during the greedy boosting phase. At the start of fitting an EBM, the current default EBM algorithm executes a fixed number of smoothing rounds where the splitting points in the trees are randomly chosen. This initial smoothing prevents larger jumps in the graphs that would otherwise occur during the initial boosting steps when the shape functions are far away from their final shapes. During that phase the categories in the categorical features are placed in alphanumeric sorted order. I remember deciding to do it this way because we also use the equivalent of smoothing rounds for differentially private EBMs, and sorting the categories by the target would leak private information in those models. There are better things we could do for normal EBMs where privacy leakage isn't an issue, like for example dropping fitting the nominal features during the initial smoothing rounds, or possibly using Fischer on the categoricals while still randomizing the cut points. I'd want to benchmark those choices, so I'm not going to make this change immediately. I wouldn't call the current situation a bug since Fisher is an optimization, but I understand why this is unexpected behavior, so I'll plan to make some kind of change to rectify that. I'll leave this issue open until that is done.

If you'd like to verify that this is the same issue you are observing on your dataset, try setting smoothing_rounds=0 and retry your experiment. I tried this on a synthetic dataset, and the results were invariant to changes in the category order.

[aswer-svg]

Huge thank you for the detailed reply. Indeed, setting smoothing_rounds=0 makes the alphanumeric order irrelevant. I'm looking forward to any changes in this regard. Take care.

[invalidarg]

Hi, I was experimenting with high-cardinality nominal categoricals and noticed that the learned effects appeared “smooth” when plotted along the alphabetically sorted levels. After some digging I found this issue, which seems related.

I’m trying to build a clearer intuition for what “smoothness” means for categorical features in this context.

From what I understand, during smoothing_rounds > 0, categorical features are temporarily treated as ordered according to their input (alphabetical) order, and random splits are applied along this axis. This introduces a notion of neighbourhood between categories that is unrelated to the target (i.e. induced by label names rather than data signal).

In practice, this seems to lead to neighbouring category levels (in alphabetical order) having more similar effects — hence the “smoothness” on that axis — even though the variable is nominal.

One consequence I observed is that categories near the ends of the ordering (e.g. “A” or “Z”) behave differently from those in the middle. My intuition is that this creates a positional bias where levels in the “middle” are averaged over more groupings during smoothing, since they participate in more random interval splits, while edge levels participate in fewer groupings.

I’m trying to understand if this interpretation is correct.

If so, it suggests that the smoothing phase introduces a dependence on the alphabetical ordering of categories, before Fisher-style ordering is applied later during boosting.

I was thinking about possible alternatives that could reduce this positional bias, for example:
• assigning categories randomly to bins instead of relying on a fixed ordering,
• enforcing more balanced splits (e.g. roughly equal numbers of categories on each side),
• or treating the categories as circular rather than linear (so that edge categories are not special cases).

Another possible direction could be something closer to permutation-based approaches (e.g. CatBoost-style ordered target statistics), where categorical structure is learned without relying on a fixed ordering.

Also, setting smoothing_rounds=0 seems to remove most of this behaviour, which suggests that it originates from the smoothing phase rather than the core boosting procedure.

Additionally, if I read it correctly, even when Fisher-style ordering is used (e.g. when smoothing_rounds=0), there can still be a weak dependence on the original (alphabetical) ordering due to how ties or near-ties between categories are handled. In particular, if multiple categories have similar or identical target statistics at a given boosting step, their relative order must still be determined in some way. If this falls back to the original input/alphabetical order, it can introduce a subtle but systematic bias. This effect is likely most visible when categories have limited data or weak signal, where ties are more common, and could help explain cases where renaming categories slightly changes the learned function even without smoothing.

[paulbkoch]

Hi @invalidarg -- Unless there is a bug, I think there shouldn't be an alphabetical dependency in more recent version of Interpret (anything newer than about 2 years ago).

The section that handles Fischer and nominals during smoothing rounds is here:

interpret/shared/libebm/PartitionOneDimensionalBoosting.cpp

Lines 1170 to 1212 in 7fbb088

	EBM_ASSERT(bShuffle || bSort);
	EBM_ASSERT(2 <= cKeep);
	if(bShuffle) {
	auto** ppBinShuffle = apBins;
	auto** const ppBinShuffleEnd = apBins + cKeep;
	do {
	EBM_ASSERT(1 <= cRemaining);
	if(1 != cRemaining) {
	const size_t iSwap = pRng->NextFast(cRemaining);
	auto* const pTemp = ppBinShuffle[iSwap];
	--cRemaining;
	ppBinShuffle[iSwap] = *ppBinShuffle;
	*ppBinShuffle = pTemp;
	} else {
	EBM_ASSERT(ppBinShuffleEnd == ppBinShuffle + 1);
	}
	++ppBinShuffle;
	} while(ppBinShuffleEnd != ppBinShuffle);
	// anything left goes into the dregs
	if(ppBin != ppBinShuffle) {
	if(!pDregSumBin) {
	pDregSumBin = *ppBinShuffle;
	pDregsTreeNode = pRootTreeNode;
	++ppBinShuffle;
	}
	while(ppBin != ppBinShuffle) {
	const auto* const pBinDrop = *ppBinShuffle;
	pDregSumBin->Add(cScores, *pBinDrop, pBinDrop->GetGradientPairs());
	++ppBinShuffle;
	}
	EBM_ASSERT(ppBinShuffleEnd == apBins + cKeep);
	ppBin = ppBinShuffleEnd;
	}
	}
	if(bSort) {
	std::sort(apBins,
	ppBin,
	CompareBin<bHessian, cCompilerScores>(
	!(TermBoostFlags_DisableNewtonUpdate & flags), categoricalSmoothing));
	}

You can see from the assert that when boosting a nominal, we either sort the feature (Fischer), or we randomly shuffle the categories each time we boost on each feature.

The original issue is still an issue in that the model outputted will be different if you rename the categories. The shuffling occurs from the point of the initial alphabetical ordering, so although the models will be different there shouldn't be any correlation to the alphabetical position.

But like I said, this is all assuming there isn't a bug, so if possible, could you post some of your graphs and we can take a closer look.

To answer your other question about smoothing for nominals -- we do smoothing entirely for the benefit of continuous features. If your dataset consisted entirely of nominals, turning off smoothing rounds would make sense, although I suspect the benefit of doing this is small. We only include nominal features during the smoothing phase because we don't want the model to become overly reliant on the continuous features during that phase.

The underlying problem we have is that nominals are not specified in the feature_types init parameter, but are instead found in the dataset itself. If we wanted the nominals to be invariant to their given names, we could do that by ordering them by the order they appear in the dataset, but then EBMs would no longer invariant to re-ordering the dataset, which is arguably worse. Alternatively, as you suggest, we could order them by statistics like frequency, which improves things, but doesn't fundamentally solve the issue since we'd still need tiebreakers.

Side note: I really like CatBoost-style ordered target statistics, but I think it would significantly slow future GPU EBMs down because it introduces more serial dependency in the boosting process. CatBoost doesn't have this issue as much since they can parallelize the gain calculations across features, but EBMs spend more time boosting (a serial process) than computing gains.

[aswer-svg]

Hi, I was fairly confident in my initial testing that ordering the nominal features with respect to the mean of the response clearly changed the smoothing in favor of that feature being more important.

I have done some testing, limiting the number of rounds so that the model only consists of smooth rounds.

Here are the results with and without sorting by response:

Not sorted by response:

Sorted by response:

As we can see, the importances increase a lot. Also, the plots look smooth along the sorting order.
The tests are done on interpret 0.7.8

[paulbkoch]

Thanks @aswer-svg! That illustrates the issue perfectly. I have found the problem and will correct it soon. The section of code I linked to above isn't the section that handles the random cut algorithm used during smoothing. That is in PartitionRandomBoosting.cpp, and it doesn't (currently) do shuffling.

Here's my repro:

import interpret
from interpret.utils import make_synthetic
from interpret import show
from interpret.glassbox import ExplainableBoostingRegressor

X, y, names, types = make_synthetic(classes=None, n_samples=10000, missing=False)
ebm = ExplainableBoostingRegressor(names, types, interactions=0, max_rounds=100, smoothing_rounds=100)
ebm.fit(X, y)

show(ebm.explain_global(), 9)

[aswer-svg]

Thank you for your time. I have some more questions about how this can be fixed.

Does your proposed fix mean just an initial shuffling, or shuffling at each round?

If it's the former, that wouldn't eliminate the bias induced by smoothing along the initial order, it would just make it random.

The latter would eliminate that bias but make the model biased for the numerical features instead. Because the relationship between the numericals and the response are usually monotonic, they would get the benefit of being sorted, but the nominals wouldn't. This could make the model prefer numericals over nominals.

Your previously suggested solution of sorting the nominals at each round with Fischer's method while randomizing the cut points feels like a better way to handle this, but I understand why this needs some benchmarking. Do you still have any plans on this?

Edit: Will the fix also apply to interaction smoothing rounds?

Take care,

[paulbkoch]

@aswer-svg -- I think for the next release I will just do randomized shuffling of the categories during each smoothing round. That's close enough to the original algorithm that I don't feel the need to benchmark that change, and I would like to remove the bias towards category label positions that you've brought up. There seem to be a lot of ways we could do nominals during the smoothing phase. I'd like to implement a number of them under the hood before benchmarking them together at once. I don't think there's fundamentally a best theoretical choice here -- as Cynthia Rudin's group has pointed out there's a kind of Rashmon set for GAMs when features are correlated, so this choice is biasing the model towards one of them. Also, from previous benchmarking I can say that the smoothing phase has a fairly minimal effect on the final model performance. The greedy phase is able to rebalance the importances the model puts on each feature during the smoothing phase.

[aswer-svg]

Thanks a lot. Glad to see improvements on the already great EBM :)
Take care