LightGBM error when using UseCat with count Feature selection

[rauhs]

Issue

version: 0.11

• What did you do?

1. I trained a LightGBM multi-class classifier with UseCat to true.
2. I added a SelectFeaturesBasedOnCount on the final Features.

If it matters: I also use early stopping (does this prune some trees?).

• What happened?

I got an exception after training was done (successfully) and ML.NET tries to construct the InternalRegressionTree:

System.InvalidOperationException: 'Categorical split features is zero length'

Stack

>	Microsoft.ML.Core.dll!Microsoft.ML.Contracts.Check(bool f, string msg) Line 491	C#
 	Microsoft.ML.FastTree.dll!Microsoft.ML.Trainers.FastTree.InternalRegressionTree.CheckValid(System.Action<bool, string> checker) Line 471	C#
 	Microsoft.ML.FastTree.dll!Microsoft.ML.Trainers.FastTree.InternalRegressionTree.InternalRegressionTree(int[] splitFeatures, double[] splitGain, double[] gainPValue, float[] rawThresholds, float[] defaultValueForMissing, int[] lteChild, int[] gtChild, double[] leafValues, int[][] categoricalSplitFeatures, bool[] categoricalSplit) Line 224	C#
 	Microsoft.ML.FastTree.dll!Microsoft.ML.Trainers.FastTree.InternalRegressionTree.Create(int numLeaves, int[] splitFeatures, double[] splitGain, float[] rawThresholds, float[] defaultValueForMissing, int[] lteChild, int[] gtChild, double[] leafValues, int[][] categoricalSplitFeatures, bool[] categoricalSplit) Line 188	C#
 	Microsoft.ML.LightGBM.dll!Microsoft.ML.LightGBM.Booster.GetModel(int[] categoricalFeatureBoudaries) Line 257	C#
 	Microsoft.ML.LightGBM.dll!Microsoft.ML.LightGBM.LightGbmTrainerBase<Microsoft.ML.Data.VBuffer<float>, Microsoft.ML.Data.MulticlassPredictionTransformer<Microsoft.ML.Trainers.OvaModelParameters>, Microsoft.ML.Trainers.OvaModelParameters>.TrainCore(Microsoft.ML.IChannel ch, Microsoft.ML.IProgressChannel pch, Microsoft.ML.LightGBM.Dataset dtrain, Microsoft.ML.LightGBM.LightGbmTrainerBase<Microsoft.ML.Data.VBuffer<float>, Microsoft.ML.Data.MulticlassPredictionTransformer<Microsoft.ML.Trainers.OvaModelParameters>, Microsoft.ML.Trainers.OvaModelParameters>.CategoricalMetaData catMetaData, Microsoft.ML.LightGBM.Dataset dvalid) Line 375	C#
 	Microsoft.ML.LightGBM.dll!Microsoft.ML.LightGBM.LightGbmTrainerBase<Microsoft.ML.Data.VBuffer<float>, Microsoft.ML.Data.MulticlassPredictionTransformer<Microsoft.ML.Trainers.OvaModelParameters>, Microsoft.ML.Trainers.OvaModelParameters>.TrainModelCore(Microsoft.ML.TrainContext context) Line 117	C#
 	Microsoft.ML.Data.dll!Microsoft.ML.Trainers.TrainerEstimatorBase<Microsoft.ML.Data.MulticlassPredictionTransformer<Microsoft.ML.Trainers.OvaModelParameters>, Microsoft.ML.Trainers.OvaModelParameters>.TrainTransformer(Microsoft.Data.DataView.IDataView trainSet, Microsoft.Data.DataView.IDataView validationSet, Microsoft.ML.IPredictor initPredictor) Line 148	C#
 	MlnEval.exe!ConsoleApp1.MlNetSpecific.MlNetLightGbmMultiClassTrainer.TrainAndEval(ConsoleApp1.Dev.AppState app) Line 107	C#
 	MlnEval.exe!ConsoleApp1.Program.Main(string[] args) Line 116	C#

Unfortunately I failed to come up with a minimal reproducible example. Seems this requires a certain data setup.

Partial analysis

It looks like here:

machinelearning/src/Microsoft.ML.LightGbm/WrappedLightGbmBooster.cs

Lines 236 to 251 in c5aab77

	if (GetIsCategoricalSplit(decisionType[node]))
	{
	int catIdx = (int)threshold[node];
	var cats = GetCatThresholds(catThreshold, catBoundaries[catIdx], catBoundaries[catIdx + 1]);
	categoricalSplitFeatures[node] = new int[cats.Length];
	// Convert Cat thresholds to feature indices.
	for (int j = 0; j < cats.Length; ++j)
	categoricalSplitFeatures[node][j] = splitFeature[node] + cats[j] - 1;
	splitFeature[node] = -1;
	categoricalSplit[node] = true;
	// Swap left and right child.
	int t = leftChild[node];
	leftChild[node] = rightChild[node];
	rightChild[node] = t;
	}

cats array is actually 0 length but categoricalSplit[node] is still set to true.

which then later on will throw here:

machinelearning/src/Microsoft.ML.FastTree/TreeEnsemble/InternalRegressionTree.cs

Lines 465 to 469 in c5aab77

	if (CategoricalSplit[index])
	{
	checker(CategoricalSplitFeatures[index] != null, "Categorical split features is null");
	checker(CategoricalSplitFeatures[index].Length > 0,
	"Categorical split features is zero length");

[rauhs]

FWIW, same problem with using HandleMissingValue and assigning some nulls to some features.

[justinormont]

Duplicate of #1625, though additional details are provided in this new bug report.

[rauhs]

Any chance this can be looked at?

[najeeb-kazmi]

@rauhs can you give me a sample of the dataset on which this can be reproduced?

[rauhs]

I'm sure there is a smaller example but this reproduces it with version 1.5.0-preview:

   public static string[] FeatureVector(int card, int total)
    {
      var inner  = Enumerable.Range(1, card).Select(x => x.ToString());
      var repeatCount = (int)Math.Ceiling((double)total / card) + 1;
      return Enumerable.Repeat(inner, repeatCount).SelectMany(x => x).ToArray();
    }

    public static void ReproduceLightGbmFeatureSelByCountUseCatBug()
    {
      var numInstances = 10_000;
      var axs = FeatureVector(1000, numInstances);
      var bxs = FeatureVector(200, numInstances);
      var labels = FeatureVector(100, numInstances);
      var data = Enumerable.Range(1, numInstances).Select(x => new GenericSample { A = axs[x], B = bxs[x], Label = labels[x] });
      var ctx = new MLContext();
      ctx.Log += (sender, e) =>
      {
        if (e.Message.Contains("Kind=Trace]"))
        {
          return;
        }
        Console.WriteLine(e.Message);
      };

      var options = new LightGbmMulticlassTrainer.Options
      {
        UseCategoricalSplit = true,
        MinimumExampleCountPerLeaf = 1,
        MinimumExampleCountPerGroup = 1,
        EarlyStoppingRound = 10,
      };
      options.Booster = new GradientBooster.Options();

      var pipe = ctx.Transforms.Conversion.MapValueToKey("A")
        .Append(ctx.Transforms.Conversion.MapValueToKey("B"))
        .Append(ctx.Transforms.Conversion.MapKeyToVector("A"))
        .Append(ctx.Transforms.Conversion.MapKeyToVector("B"))
        .Append(ctx.Transforms.Concatenate("Features", "A", "B"))
        .Append(ctx.Transforms.FeatureSelection.SelectFeaturesBasedOnCount("Features", "Features", 10))
        .Append(ctx.Transforms.Conversion.MapValueToKey("Label"));
      var dataView = ctx.Data.LoadFromEnumerable(data);
      var trainer = ctx.MulticlassClassification.Trainers.LightGbm(options);
      var dataSplit = ctx.Data.TrainTestSplit(dataView);
      var encoder = pipe.Fit(dataSplit.TestSet);
      var trainEncoded = encoder.Transform(dataSplit.TrainSet);
      var testEncoded = encoder.Transform(dataSplit.TestSet);
      var model = trainer.Fit(trainEncoded, testEncoded);
      var scores = model.Transform(trainEncoded).GetColumn<float[]>("Score").ToArray();

      Console.WriteLine($"Min: {scores.Select(x => x.Min()).Min()}");
      Console.WriteLine($"Max: {scores.Select(x => x.Max()).Max()}");
    }

[najeeb-kazmi]

Upon further investigation, I have found that this is not because of CountFeatureSelection, but because of how categorical splits are handled when there is only one categorical column, specifically how CategoricalSlotRanges is determined in the schema annotation and how catBoundaries and catThresholds are used

machinelearning/src/Microsoft.ML.LightGbm/WrappedLightGbmBooster.cs

Lines 189 to 190 in f94f359

	public InternalTreeEnsemble GetModel(int[] categoricalFeatureBoudaries)
	{

machinelearning/src/Microsoft.ML.LightGbm/WrappedLightGbmBooster.cs

Lines 231 to 232 in f94f359

	var catBoundaries = Str2IntArray(kvPairs["cat_boundaries"], ' ');
	var catThreshold = Str2UIntArray(kvPairs["cat_threshold"], ' ');

which affects the calculation of cats

machinelearning/src/Microsoft.ML.LightGbm/WrappedLightGbmBooster.cs

Lines 235 to 245 in f94f359

	if (GetIsCategoricalSplit(decisionType[node]))
	{
	int catIdx = (int)threshold[node];
	var cats = GetCatThresholds(catThreshold, catBoundaries[catIdx], catBoundaries[catIdx + 1]);
	categoricalSplitFeatures[node] = new int[cats.Length];
	// Convert Cat thresholds to feature indices.
	for (int j = 0; j < cats.Length; ++j)
	categoricalSplitFeatures[node][j] = splitFeature[node] + cats[j] - 1;
	splitFeature[node] = -1;
	categoricalSplit[node] = true;

Here's what happens under various situations:

Situation	CategoricalSlotRanges	categoricalFeatureBoundaries	catBoundaries	catThresholds	cats
Concatenate A into Features	[0, 665]	[0, 666]	[0, 1]	[1]	empty []
Concatenate A and B into Features	[0, 665, 666, 864]	[0, 666, 865]	[0, 2]	[2, 4096]	[1, 44]
Concatenate A and B into Features and apply SelectFeaturesBasedOnCount	9 slots are selected [0, 8]	[0, 9]	[0, 1]	[1]	empty []

1 and 3 fail, but 2 succeeds. 1 and 3 lead to cats being an empty array but categoricalSplit being set to true, as pointed out by @rauhs, which leads to the error in

machinelearning/src/Microsoft.ML.FastTree/TreeEnsemble/InternalRegressionTree.cs

Lines 474 to 475 in f94f359

	checker(CategoricalSplitFeatureRanges[index].Length == 2,
	"Categorical split feature range length is not two.");

The error arises not specifically due to the presence of SelectFeaturesBasedOnCount, but because there is only one implied categorical feature produced by SelectFeaturesBasedOnCount.

I will look deeper into it and propose a fix.

cc: @guolinke @harishsk

[najeeb-kazmi]

More on this, re: values of variables in (relevant diffs in bold)

machinelearning/src/Microsoft.ML.LightGbm/WrappedLightGbmBooster.cs

Lines 208 to 247 in f94f359

	int numberOfLeaves = int.Parse(kvPairs["num_leaves"], CultureInfo.InvariantCulture);
	int numCat = int.Parse(kvPairs["num_cat"], CultureInfo.InvariantCulture);
	if (numberOfLeaves > 1)
	{
	var leftChild = Str2IntArray(kvPairs["left_child"], ' ');
	var rightChild = Str2IntArray(kvPairs["right_child"], ' ');
	var splitFeature = Str2IntArray(kvPairs["split_feature"], ' ');
	var threshold = Str2DoubleArray(kvPairs["threshold"], ' ');
	var splitGain = Str2DoubleArray(kvPairs["split_gain"], ' ');
	var leafOutput = Str2DoubleArray(kvPairs["leaf_value"], ' ');
	var decisionType = Str2UIntArray(kvPairs["decision_type"], ' ');
	var defaultValue = GetDefalutValue(threshold, decisionType);
	var categoricalSplitFeatures = new int[numberOfLeaves - 1][];
	var categoricalSplit = new bool[numberOfLeaves - 1];
	if (categoricalFeatureBoudaries != null)
	{
	// Add offsets to split features.
	for (int node = 0; node < numberOfLeaves - 1; ++node)
	splitFeature[node] = categoricalFeatureBoudaries[splitFeature[node]];
	}
	if (numCat > 0)
	{
	var catBoundaries = Str2IntArray(kvPairs["cat_boundaries"], ' ');
	var catThreshold = Str2UIntArray(kvPairs["cat_threshold"], ' ');
	for (int node = 0; node < numberOfLeaves - 1; ++node)
	{
	if (GetIsCategoricalSplit(decisionType[node]))
	{
	int catIdx = (int)threshold[node];
	var cats = GetCatThresholds(catThreshold, catBoundaries[catIdx], catBoundaries[catIdx + 1]);
	categoricalSplitFeatures[node] = new int[cats.Length];
	// Convert Cat thresholds to feature indices.
	for (int j = 0; j < cats.Length; ++j)
	categoricalSplitFeatures[node][j] = splitFeature[node] + cats[j] - 1;
	splitFeature[node] = -1;
	categoricalSplit[node] = true;
	// Swap left and right child.
	int t = leftChild[node];

	A only	A and B
numberOfLeaves	2	2
numCat	1	1
leftChild	int[] {-1}	int[] {-1}
rightChild	int[] {-2}	int[] {-2}
splitFeature at line 215	int[] {0}	int[] {1}
splitFeature after update in line 227	int[] {0}	int[] {666}
threshold	double[] {0}	double[] {0}
splitGain	double[] {1.13603}	double[] {250.777}
leafOutput	double[] {-9.1865…, -9.2197...}	double[] {-8.7746..., -9.3438...}
decisionType	uint[] {5}	uint[] {1}
defaultValue	double[] {0}	double[] {0}
categoricalSplitFeatures at line 221	int[][] {null}	int[][] {null}
categoricalSplitFeatures after update at line 243	int[][] { {} }	int[][] { {666, 709} }
categoricalSplit at line 222	bool[] {false}	bool[] {false}
categoricalSplit after update in line 246	bool[] {true}	bool[] {true}
categoricalFeatureBoundaries	int[] {0, 666}	int[] {0, 666, 865}
numCat	1	1
catBoundaries	int[] (0, 1}	int[] (0, 2}
catThreshold	uint[] {1}	uint[] {2, 4096}
cats	int[] {} (empty)	int[] {1, 44}

cc: @guolinke @harishsk

[guolinke]

@najeeb-kazmi from the log, it seems the bug is caused by wrong mapping from feature index to cat index