Categorical data support.

[trivialfis]

We started initial experimental support for categorical in xgboost 1.3. The initial target is to make the one-hot encoding based tree split available for all xgboost components. Here is a list of to-do items:

One Hot

• Recognize categorical data in DMatrix.

  • Accept feature types.
  • DMatrix binary.
  • Revert data handler. (Simplify the data backends. #5893)
  • Support for non-dataframe types (Support more input types for categorical data. #7220)

• Remove min values.

  • Clarify trivial split (Clarification on Trivial Splits #2914).
  • Replace trivial split with infinity.

• Device DMatrix.

  • Normal data. (Categorical data support for cuDF. #7042)
  • Iterator. (Support categorical data for dask functional interface and DQM. #7043)

• GPU Sketching for categorical data.

  • Count categories automatically.
  • Weighted sketching. (Support categorical data in GPU weighted sketching. #6508)
  • Handle merging by removing duplicated entries after merge. (Support categorical data for dask functional interface and DQM. #7043)
  • Ignore num bins in GPU pruning. (Support categorical data in GPU sketching. #6137)
  • Handle compress index. (Support categorical data in ellpack. #6140)

• GPU Evaluate splits based on feature types.

  • Unify split candidate structs. (Unify evaluation functions. #6037)
  • Working implementation.
  • Handle monotone constraint.

• Tree model (RegTree).

  • Define expand categorical.
  • Tree model dump. (Support categorical split in tree model dump. #7036)
  • Feature scores. (Implement feature score in GBTree. #7041)
  • Model as dataframe. (Handle categorical split in model histogram and dataframe. #7065)
  • Split value histogram. (Handle categorical split in model histogram and dataframe. #7065)

• GPU Hist Updater.

  • Evaluate split
  • Apply split

• Prediction.

  • Use predictor in dart (Use Predictor for dart. #6693).
  • CPU Predictor. (Implement categorical prediction for CPU and GPU predict leaf. #7001)
  • GPU Predictor. (Add categorical data support to GPU predictor. #6165)
  • CPU leaf prediction. (Implement categorical prediction for CPU and GPU predict leaf. #7001)
  • GPU leaf prediction. (Implement categorical prediction for CPU and GPU predict leaf. #7001)
  • Missing value handling.
  • Shap. (Categorical split support for SHAP #7053)
  • In-place prediction. (Support categorical data with pandas Dataframe in inplace prediction #7322)

• Model IO.

  • Design JSON model schema.
  • Implement it.
  • Update schema.
  • Set JSON to be the default format for pickle serialization.

• CPU Sketching.

  • Merge sparse cut builder and dense cut builder. (Unify CPU hist sketching #5880)
  • Count categories. (Categorical data support in CPU sketching. #7221)
  • Merge operation. (Support distributed CPU env for categorical data. #7575)
  • Check for invalid categorical values. (Validate out of range categorical value. #7576)

• CPU Hist.

  • Evaluate split (CPU evaluation for cat data. #7393)
  • Update partition (Support categorical data for hist. #7695)

• Migrate the implementation of global approx to hist's codebase.

  • Implement external memory support with GHistIndexMatrix used by hist. (Move GHistIndex into DMatrix. #7064, Initial support for external memory in gradient index. #7183) .
  • Make evaluation function from hist reusable. (Extract evaluate splits from CPU hist. #7079) .
  • Make histogram builder reusble. (Extract histogram builder from CPU Hist. #7152)
  • Make part of the partitioner reusble.
  • Modify sketching function to support hessian as weights. (Support hessian in host sketch container. #7081)

• Global approx (Rewrite approx #7214)

  • Gradient Index (Support building gradient index with cat data. #7371)
  • Evaluator (CPU evaluation for cat data. #7393)
  • Partitioner

• Local approx.
  Unsupported.

• Sketch maker.

  • Deprecate it.

• Exact
  Unsupported.

• Sklearn interfaces (Add enable_categorical to sklearn. #7011).

• Dask

  • functional (Support categorical data for dask functional interface and DQM. #7043)
  • sklearn (Tests for dask skl categorical data support. #7054)
  • In-place prediction. ([dask] prediction with categorical data. #7708)
  • Dask dafaframe cat codes.

• Documents

  • Brief introduction to native model support. (Add document for categorical data. #7307)
  • Simple demo. (Demo for experimental categorical data support. #7213)

Partitioning Based (LGB)

• General

  • Let tree method be aware of whether it can be used (Pass infomation about objective to tree methods. #7385)

• GPU Hist

  • Rewrite GPU evaluation into 2 passes evaluation style. (Refactor split evaluator using device-wide Scan primitive #7197)
  • Evaluator (Support optimal partitioning for GPU hist. #7652)
  • Explore tunning parameters.

• Approx

  • Evaluate split (CPU evaluation for cat data. #7393)
  • Distributed (Support distributed CPU env for categorical data. #7575)
  • Tests (Cover approx tree method for categorical data tests. #7569)

• CPU Hist

  • Evaluate split (CPU evaluation for cat data. #7393)

• Documents

  • Demo (Support optimal partitioning for GPU hist. #7652)
  • Tutorial (Support optimal partitioning for GPU hist. #7652)

Feature items can only be marked as completed if there's a corresponding (unit)test. Please let me know if there are missing items or if you want to help to accelerate the progress. ;-)

[trivialfis]

As of posting, I have prototypes on new GPU evaluation function and refactored CPU hist/approx/local tree methods. Dart support is on the way.

[mayer79]

Great idea! Will this be compatible with

• interaction constraints?
• monotonic constraints (probably not)?
• SHAP contribution calculations?

[hcho3]

interaction constraints?

Yes, since we only care whether two features appear together or not.

monotonic constraints

No, since categorical values cannot be sorted in increasing order.

SHAP contribution calculations

Probably, given that LightGBM also supports computing SHAP with categorical features. But we need to test it.

[trivialfis]

Status update:

Here are the few big items remaining for feature completeness:

• GPU evaluation function rewrite to have better performance.
• Add partition-based cat split for the rewritten evaluation function.
• Extract the partitioner from hist and implement categorical data support in it.
• Add categorical feature specific regularization parameters.

[trivialfis]

Closing, initial support is completed. We will continue to add optimization and new features in the future.