Autogluon: k nearest neighbors model ignores categorical features

[razmikmelikbekyan]

https://github.com/awslabs/autogluon/blob/2b11a59a0e9af6c71f23ecb9607d61f954ba1a10/autogluon/utils/tabular/ml/models/knn/knn_model.py#L26

[jwmueller]

Categoricals eventually shouldn't be dropped like they are currently, but simply converting them to int is also inappropriate for kNN since the distance between different pairs of categories should remain equal. One-hot encoding satisfies this property, but has the downside that different features with different # of categories will end up with totally different distances.

I see a couple preprocessing options here:

1) Pass in a custom distance metric to the kNN model: https://stackoverflow.com/questions/21052509/sklearn-knn-usage-with-a-user-defined-metric

where the distance for each categorical feature is = 1 if two rows have different values for this feature and otherwise = 0 (and vector distances are still used for the numerical features).
The key challenge with this approach will be to ensure that the kNN model is not slowed down by the user-defined metric, which must be implemented very efficiently (and must account for missing values / unknown categories that only appear at inference time).

2) Use target mean encoding for each categorical feature to represent it as a vector of fixed dimensionality d (where d is the same across all categorical features):
https://medium.com/@pouryaayria/k-fold-target-encoding-dfe9a594874b

Once all categoricals are vectors, one can just apply the current kNN model. However, the d in target mean encoding will depend on the number of possible labels in multi-class problems which is also undesirable. Thus, for multiclass problems, I would actually first apply target mean encoding, followed by further dimension reduction to reduce d to something like 2-5 (eg. PCA, multi-dimensional-scaling). After each categorical feature has been represented as a vector, I'd also make sure to rescale these vectors so their distances are distributed similarly as the distances between different rows along a single numerical feature. The key challenge with this approach will be: ensuring the target mean encoding code is robust across many datasets and can handle missing-values / unknown categories that only appear at inference time.

[razmikmelikbekyan]

Thanks for detailed explanation and possible solutions. Do you think if this kind of solution can be applied also in general for all models? At least mean target encoding.

[Innixma]

Target mean encoding is something that is greatly desired in future. For now, the built-in categorical support we have in LightGBM, CatBoost, and the neural network model mitigate some of the losses we have for not doing target mean encoding (CatBoost actually does TME internally), but there is definitely significant improvements that can be had from it.

A great breakdown of TME strategies is available here: https://towardsdatascience.com/benchmarking-categorical-encoders-9c322bd77ee8

For our implementation, we would ideally want to implement Single/Double Validation CatBoost Encoder and possibly None Validation Frequency Encoder. We would avoid encoders such as None Validation Helmert Encoder and any other one-hot-encoding method due to the explosion of memory usage and subsequent training times (although some models may be able to support sparse matrix input where the downsides of OHE could be mitigated). There is also the difficulty of multi-class problems as Jonas mentioned, where memory usage and training times continue to be a major issue.

A core challenge is that TME Double Validation is complex to do in a bagged ensemble setting while maintaining reasonable training speeds, as the best TME techniques are expensive, and would require us to cache the TME results in temporary files that are then loaded on-demand to the appropriate fold of bagged models, and this process would have to be repeated for each stack layer and each repeated bagged fold.

Achieving this is do-able, but the implementation is complex and requires models to have the ability to load files from disk on-demand, which is not currently supported (models are fully unaware of any data outside of the dataframes passed in to .fit())

[jwmueller]

Thanks for detailed explanation and possible solutions. Do you think if this kind of solution can be applied also in general for all models? At least mean target encoding.

Most definitely! If you're interested in helping with this, I'd implement the TME as a general preprocessing function that just happens to be used by the kNN model. A good next step after that would be to also create a second Neural Net that also operates on TME-preprocessed categorical data as a more efficient alternative to our current network's embedding layers. The kNN will almost certainly benefit from TME and the second TME Neural Net is likely to provide additional benefits as well.

[razmikmelikbekyan]

Yep, I would try to help.

[gradientsky]

FYI, if the whole dataset is made of only categorical variables, the model produces the error:

Fitting model: KNeighborsClassifierUnif_STACKER_l0 ...
Saving data/models/autogluon/models/KNeighborsClassifierUnif_STACKER_l0/utils/model_template.pkl
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/trainer/abstract_trainer.py", line 263, in train_and_save
    model = self.train_single(X_train, y_train, X_test, y_test, model, kfolds=kfolds, k_fold_start=k_fold_start, k_fold_end=k_fold_end, n_repeats=n_repeats, n_repeat_start=n_repeat_start, level=level, time_limit=time_limit)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/trainer/abstract_trainer.py", line 246, in train_single
    model.fit(X=X_train, y=y_train, k_fold=kfolds, k_fold_start=k_fold_start, k_fold_end=k_fold_end, n_repeats=n_repeats, n_repeat_start=n_repeat_start, compute_base_preds=False, time_limit=time_limit, **model_fit_kwargs)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/models/ensemble/stacker_ensemble_model.py", line 128, in fit
    super().fit(X=X, y=y, k_fold=k_fold, k_fold_start=k_fold_start, k_fold_end=k_fold_end, n_repeats=n_repeats, n_repeat_start=n_repeat_start, time_limit=time_limit, **kwargs)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/models/ensemble/bagged_ensemble_model.py", line 183, in fit
    fold_model.fit(X_train=X_train, Y_train=y_train, X_test=X_test, Y_test=y_test, time_limit=time_limit_fold, **kwargs)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/models/knn/knn_model.py", line 59, in fit
    self.model = model.fit(X_train, Y_train)
  File "/home/user/anaconda3/envs/py36mkl/lib/python3.6/site-packages/sklearn/neighbors/_base.py", line 1130, in fit
    X, y = check_X_y(X, y, "csr", multi_output=True)
  File "/home/user/anaconda3/envs/py36mkl/lib/python3.6/site-packages/sklearn/utils/validation.py", line 755, in check_X_y
    estimator=estimator)
  File "/home/user/anaconda3/envs/py36mkl/lib/python3.6/site-packages/sklearn/utils/validation.py", line 475, in check_array
    dtype_orig = np.result_type(*dtypes_orig)
  File "<__array_function__ internals>", line 6, in result_type
Warning: Exception caused KNeighborsClassifierUnif_STACKER_l0 to fail during training... Skipping this model.
Traceback (most recent call last):
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/trainer/abstract_trainer.py", line 263, in train_and_save
    model = self.train_single(X_train, y_train, X_test, y_test, model, kfolds=kfolds, k_fold_start=k_fold_start, k_fold_end=k_fold_end, n_repeats=n_repeats, n_repeat_start=n_repeat_start, level=level, time_limit=time_limit)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/trainer/abstract_trainer.py", line 246, in train_single
    model.fit(X=X_train, y=y_train, k_fold=kfolds, k_fold_start=k_fold_start, k_fold_end=k_fold_end, n_repeats=n_repeats, n_repeat_start=n_repeat_start, compute_base_preds=False, time_limit=time_limit, **model_fit_kwargs)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/models/ensemble/stacker_ensemble_model.py", line 128, in fit
    super().fit(X=X, y=y, k_fold=k_fold, k_fold_start=k_fold_start, k_fold_end=k_fold_end, n_repeats=n_repeats, n_repeat_start=n_repeat_start, time_limit=time_limit, **kwargs)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/models/ensemble/bagged_ensemble_model.py", line 183, in fit
    fold_model.fit(X_train=X_train, Y_train=y_train, X_test=X_test, Y_test=y_test, time_limit=time_limit_fold, **kwargs)
  File "/home/user/Projects/autogluon/autogluon/utils/tabular/ml/models/knn/knn_model.py", line 59, in fit
    self.model = model.fit(X_train, Y_train)
  File "/home/user/anaconda3/envs/py36mkl/lib/python3.6/site-packages/sklearn/neighbors/_base.py", line 1130, in fit
    X, y = check_X_y(X, y, "csr", multi_output=True)
  File "/home/user/anaconda3/envs/py36mkl/lib/python3.6/site-packages/sklearn/utils/validation.py", line 755, in check_X_y
    estimator=estimator)
  File "/home/user/anaconda3/envs/py36mkl/lib/python3.6/site-packages/sklearn/utils/validation.py", line 475, in check_array
    dtype_orig = np.result_type(*dtypes_orig)
  File "<__array_function__ internals>", line 6, in result_type
ValueError: at least one array or dtype is required
at least one array or dtype is required

[Innixma]

Yes, I am aware of this issue. We can probably improve the error message to be cleaner.