Repository: scikit-learn/scikit-learn
Pull request: ENH Add min_categories parameter for each feature to CategoricalNB
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/master/CONTRIBUTING.md#pull-request-checklist
-->

#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->
closes #16028 
closes #16045 


#### What does this implement/fix? Explain your changes.
This PR provides a way to make predictions with `CategoricalNB` with data that contains categories that were not observed in the training data. E.g., data for a problem can possibly have 2 categories, but training data only contains samples with one category observed:

```
>>> import numpy as np
>>> from sklearn.naive_bayes import CategoricalNB
>>> X_train = np.array([[0], [0], [0]])
>>> y_train = np.array([0, 1, 0])
>>> clf = CategoricalNB(min_categories=2)
>>> clf.fit(X_train, y_train)
>>> X_test = np.array([[1]])
>>> clf.predict(X_test)
array([0])
>>> clf.n_categories_
array([2])
```

This adds the additional Parameters/Attributes to `__init__` of `CategoricalNB`:
```
    Parameters
    ----------
    min_categories : int or array-like or None, (default=None)
        Minimum number of categories per feature:
        - int : Sets the minimum number of categories per feature to
          `n_categories` for each features.
        - array-like : `n_categories[i]` holds the minimum number of categories
          for the ith column of the input.
        - None : Determines the number of categories automatically from the
          training data.

    Attributes
    ----------
    n_categories_ : ndarray (n_features,)
        Number of categories for each feature. This value is provided
        inferred from the data or set by the minimum number of categories.
```

This feature has uses in instances where a given category may be rare, and then by random chance is observed in a test/application set, but not in the training set.

In the current version, such an instance will raise an error (as detailed in #16028).

#### Any other comments?
* This differs slightly from the solution I proposed in #16028 . Implementation in this way allows a minimum number of categories to be specified, but be overridden if the data has more categories, which I thought may be user-side.
* This fix will still result in the same unhelpful error message mentioned #16028 if category `i` has a greater value in a non-training set than the value of `n_categories[i] - 1`. Is #16045 considered stalled at this point?  Would it be worth wrapping a helpful error message for that case into this PR?


<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->


Problem statement:
CategoricalNB bug with categories present in test but absent in train
#### Description
Calling predict() / predict_proba() / predict_log_proba() on CategoricalNB model throws IndexError.

#### Steps/Code to Reproduce
```
import numpy as np
from sklearn.datasets import make_classification
from sklearn.naive_bayes import CategoricalNB
from sklearn.model_selection import train_test_split

X, y = make_classification(n_features=10, n_classes=3, n_samples=1000, random_state=42,
                                             n_redundant=0, n_informative=6)
X = np.abs(X.astype(np.int))
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5, random_state=42)
model = CategoricalNB().fit(X_train, y_train)

model.predict(X_test)
```

#### Expected Results
Predictions for X_test(integer labels).

#### Actual Results
```
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-3-551bb8080923> in <module>
     10 model = CategoricalNB().fit(X_train, y_train)
     11 
---> 12 model.predict(X_test)

~/Documents/MachineLearning/onnx_projects/skl_env/lib/python3.6/site-packages/sklearn/naive_bayes.py in predict(self, X)
     75         check_is_fitted(self)
     76         X = self._check_X(X)
---> 77         jll = self._joint_log_likelihood(X)
     78         return self.classes_[np.argmax(jll, axis=1)]
     79 

~/Documents/MachineLearning/onnx_projects/skl_env/lib/python3.6/site-packages/sklearn/naive_bayes.py in _joint_log_likelihood(self, X)
   1217         for i in range(self.n_features_):
   1218             indices = X[:, i]
-> 1219             jll += self.feature_log_prob_[i][:, indices].T
   1220         total_ll = jll + self.class_log_prior_
   1221         return total_ll

IndexError: index 5 is out of bounds for axis 1 with size 5
```
#### Versions
System:
    python: 3.6.8 (v3.6.8:3c6b436a57, Dec 24 2018, 02:04:31)  [GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.57)]
executable: /Users/prroy/Documents/MachineLearning/onnx_projects/skl_env/bin/python3
   machine: Darwin-19.2.0-x86_64-i386-64bit

Python dependencies:
       pip: 18.1
setuptools: 40.6.2
   sklearn: 0.22.1
     numpy: 1.18.0
     scipy: 1.4.1
    Cython: 0.29.14
    pandas: 0.25.3
matplotlib: None
    joblib: 0.14.1

Built with OpenMP: True

Hints from issue discussion:
Some categories are present during testing but never seen during training.
We should probably have a strategy to handle unknown categories or at least raise a proper error message.
Any ideas/suggestions on a strategy to handle unknown categories? Otherwise, I'd like to submit a PR raising a proper error for such instances. 
For now I think an improved error can be raised. They are hard to handle
due to smoothing, unless I'm much mistaken.

Thanks, @jnothman. PR at https://github.com/scikit-learn/scikit-learn/pull/16045
Agree that an improved error message would be great (I spent a while getting to the same conclusion as @glemaitre ). Thanks @madhuracj !!

I have an application where it is not unheard of to have a value for a categorical feature that has not been observed in the training set (application is Naive Bayes on characters in a string of DNA). So it would be really great to have an option to handle unknown categories.

Motivated by this, my proposed solution would be to take an additional argument, e.g. `n_categories`, in `CategoricalNB.__init__()` such that
```
"""
n_categories : int or array-like or 'auto', (default='auto')
    Number of categories (unique values) per feature:

    - int : Sets the number of categories per feature to `n_categories` for each features.
    - array-like : `n_categories[i]` holds the number of categories expected in the ith
       column.
    - 'auto' : Determines the categories automatically from the training data.
"""
```

I'd be happy to submit a PR that does this.
I would be happy with that solution.

Commit message: DOC: from suggestion, remove extra word

Co-Authored-By: Joel Nothman <joel.nothman@gmail.com>

Patch to review:
diff --git a/sklearn/naive_bayes.py b/sklearn/naive_bayes.py
index dd1d9586db6e1..b1016a4c7f0b0 100644
--- a/sklearn/naive_bayes.py
+++ b/sklearn/naive_bayes.py
@@ -1031,6 +1031,16 @@ class CategoricalNB(_BaseDiscreteNB):
         Prior probabilities of the classes. If specified the priors are not
         adjusted according to the data.
 
+    min_categories : int or array-like or None, default=None
+        Minimum number of categories per feature.
+
+        - int : Sets the minimum number of categories per feature to
+          `n_categories` for each features.
+        - array-like : shape (n_features,) where `n_categories[i]` holds the
+          minimum number of categories for the ith column of the input.
+        - None : Determines the number of categories automatically from the
+          training data.
+
     Attributes
     ----------
     category_count_ : list of arrays of shape (n_features,)
@@ -1056,6 +1066,10 @@ class CategoricalNB(_BaseDiscreteNB):
     n_features_ : int
         Number of features of each sample.
 
+    n_categories_ : ndarray (n_features,)
+        Number of categories for each feature. This value is
+        inferred from the data or set by the minimum number of categories.
+
     Examples
     --------
     >>> import numpy as np
@@ -1070,10 +1084,12 @@ class CategoricalNB(_BaseDiscreteNB):
     [3]
     """
 
-    def __init__(self, alpha=1.0, fit_prior=True, class_prior=None):
+    def __init__(self, alpha=1.0, fit_prior=True, class_prior=None,
+                 min_categories=None):
         self.alpha = alpha
         self.fit_prior = fit_prior
         self.class_prior = class_prior
+        self.min_categories = min_categories
 
     def fit(self, X, y, sample_weight=None):
         """Fit Naive Bayes classifier according to X, y
@@ -1164,6 +1180,21 @@ def _init_counters(self, n_effective_classes, n_features):
         self.category_count_ = [np.zeros((n_effective_classes, 0))
                                 for _ in range(n_features)]
 
+    def _init_n_categories(self, X):
+        feature_n_categories = X.max(axis=0) + 1
+        if self.min_categories is not None:
+            # unsafe casting allows float to be coerced to int
+            n_categories_ = np.maximum(feature_n_categories,
+                                       self.min_categories,
+                                       dtype=np.int,
+                                       casting='unsafe')
+            if np.shape(n_categories_) != feature_n_categories.shape:
+                raise ValueError('min_categories must be scalar, array-like '
+                                 'of shape (n_features,), or None.')
+            self.n_categories_ = n_categories_
+        else:
+            self.n_categories_ = feature_n_categories
+
     def _count(self, X, Y):
         def _update_cat_count_dims(cat_count, highest_feature):
             diff = highest_feature + 1 - cat_count.shape[1]
@@ -1184,10 +1215,11 @@ def _update_cat_count(X_feature, Y, cat_count, n_classes):
                 cat_count[j, indices] += counts[indices]
 
         self.class_count_ += Y.sum(axis=0)
+        self._init_n_categories(X)
         for i in range(self.n_features_):
             X_feature = X[:, i]
             self.category_count_[i] = _update_cat_count_dims(
-                self.category_count_[i], X_feature.max())
+                self.category_count_[i], self.n_categories_[i] - 1)
             _update_cat_count(X_feature, Y,
                               self.category_count_[i],
                               self.class_count_.shape[0])
diff --git a/sklearn/tests/test_naive_bayes.py b/sklearn/tests/test_naive_bayes.py
index b4470a7ed49e5..e2c940a54a422 100644
--- a/sklearn/tests/test_naive_bayes.py
+++ b/sklearn/tests/test_naive_bayes.py
@@ -659,6 +659,7 @@ def test_categoricalnb():
     clf = CategoricalNB(alpha=1, fit_prior=False)
 
     clf.fit(X3, y3)
+    assert_array_equal(clf.n_categories_, np.array([3, 6]))
 
     # Check error is raised for X with negative entries
     X = np.array([[0, -1]])
@@ -690,6 +691,7 @@ def test_categoricalnb():
     clf = CategoricalNB(alpha=1, fit_prior=False)
     clf.fit(X, y)
     assert_array_equal(clf.predict(np.array([[0, 0]])), np.array([1]))
+    assert_array_equal(clf.n_categories_, np.array([2, 2]))
 
     for factor in [1., 0.3, 5, 0.0001]:
         X = np.array([[0, 0], [0, 1], [0, 0], [1, 1]])
@@ -698,6 +700,51 @@ def test_categoricalnb():
         clf = CategoricalNB(alpha=1, fit_prior=False)
         clf.fit(X, y, sample_weight=sample_weight)
         assert_array_equal(clf.predict(np.array([[0, 0]])), np.array([2]))
+        assert_array_equal(clf.n_categories_, np.array([2, 2]))
+
+
+def test_categoricalnb_with_min_categories():
+    # None as n_categories is checked by default in test_categoricalnb
+
+    X_n_categories = np.array([[0, 0], [0, 1], [0, 0], [1, 1]])
+    y_n_categories = np.array([1, 1, 2, 2])
+
+    # Check min_categories with int
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories=3)
+    clf.fit(X_n_categories, y_n_categories)
+    X1_count, X2_count = clf.category_count_
+    assert_array_equal(X1_count, np.array([[2, 0, 0], [1, 1, 0]]))
+    assert_array_equal(X2_count, np.array([[1, 1, 0], [1, 1, 0]]))
+    data_with_unseen_feature_2 = np.array([[0, 2]])
+    predictions = clf.predict(data_with_unseen_feature_2)
+    assert_array_equal(predictions, np.array([1]))
+    assert_array_equal(clf.n_categories_, np.array([3, 3]))
+
+    # Check min_categories with list
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories=[3, 4])
+    clf.fit(X_n_categories, y_n_categories)
+    X1_count, X2_count = clf.category_count_
+    assert_array_equal(X1_count, np.array([[2, 0, 0], [1, 1, 0]]))
+    assert_array_equal(X2_count, np.array([[1, 1, 0, 0], [1, 1, 0, 0]]))
+    data_with_unseen_feature_3 = np.array([[0, 3]])
+    predictions = clf.predict(data_with_unseen_feature_3)
+    assert_array_equal(predictions, np.array([1]))
+    assert_array_equal(clf.n_categories_, np.array([3, 4]))
+
+    # check min_categories with min less than actual
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories=1)
+    clf.fit(X_n_categories, y_n_categories)
+    assert_array_equal(clf.n_categories_, np.array([2, 2]))
+
+    # does not accept string
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories='bad_arg')
+    assert_raises(ValueError, clf.fit, X_n_categories, y_n_categories)
+
+    # gives error for min_categories with wrong shape
+    clf = CategoricalNB(alpha=1, fit_prior=False,
+                        min_categories=[[3, 2], [2, 4]])
+    assert_raise_message(ValueError, 'min_categories must be', clf.fit,
+                         X_n_categories, y_n_categories)
 
 
 def test_alpha():


Code review comments:
diff_hunk: @@ -1031,6 +1031,16 @@ class CategoricalNB(_BaseDiscreteNB):
         Prior probabilities of the classes. If specified the priors are not
         adjusted according to the data.
 
+    min_categories : int or array-like or None, default=None
path: sklearn/naive_bayes.py
text: @user1:
```suggestion
    min_categories : int or array-like of shape (n_features,), default=None
```

diff_hunk: @@ -1184,10 +1215,11 @@ def _update_cat_count(X_feature, Y, cat_count, n_classes):
                 cat_count[j, indices] += counts[indices]
 
         self.class_count_ += Y.sum(axis=0)
+        self._init_n_categories(X)
path: sklearn/naive_bayes.py
text: @user1:
I would call this `_validate_n_categories`

@user1:
and I would prefer the following signature:

```python
self.n_categories_ = self._validate_n_categories(X)
```

`_validate_n_categories` could be decorated as a `@user2`. It will be more explicit when reading the code that we set a fitting attribute if it returns something in fit than setting it in a private method.

diff_hunk: @@ -1164,6 +1180,21 @@ def _init_counters(self, n_effective_classes, n_features):
         self.category_count_ = [np.zeros((n_effective_classes, 0))
                                 for _ in range(n_features)]
 
+    def _init_n_categories(self, X):
+        feature_n_categories = X.max(axis=0) + 1
+        if self.min_categories is not None:
+            # unsafe casting allows float to be coerced to int
+            n_categories_ = np.maximum(feature_n_categories,
+                                       self.min_categories,
+                                       dtype=np.int,
+                                       casting='unsafe')
+            if np.shape(n_categories_) != feature_n_categories.shape:
path: sklearn/naive_bayes.py
text: @user1:
```suggestion
            if n_categories_.shape != feature_n_categories.shape:
```

diff_hunk: @@ -1164,6 +1180,21 @@ def _init_counters(self, n_effective_classes, n_features):
         self.category_count_ = [np.zeros((n_effective_classes, 0))
                                 for _ in range(n_features)]
 
+    def _init_n_categories(self, X):
+        feature_n_categories = X.max(axis=0) + 1
path: sklearn/naive_bayes.py
text: @user1:
I would rather call this `n_categories_X` since you cannot have categories on axis=1 (samples).
Put a small comment why we can rely on using `max` (we expect categories encoded between 0...n-1)

diff_hunk: @@ -1031,6 +1031,16 @@ class CategoricalNB(_BaseDiscreteNB):
         Prior probabilities of the classes. If specified the priors are not
         adjusted according to the data.
 
+    min_categories : int or array-like or None, default=None
+        Minimum number of categories per feature.
+
+        - int : Sets the minimum number of categories per feature to
+          `n_categories` for each features.
+        - array-like : shape (n_features,) where `n_categories[i]` holds the
path: sklearn/naive_bayes.py
text: @user1:
```suggestion
        - array-like: shape (n_features,) where `n_categories[i]` holds the
```

diff_hunk: @@ -1031,6 +1031,16 @@ class CategoricalNB(_BaseDiscreteNB):
         Prior probabilities of the classes. If specified the priors are not
         adjusted according to the data.
 
+    min_categories : int or array-like or None, default=None
+        Minimum number of categories per feature.
+
+        - int : Sets the minimum number of categories per feature to
path: sklearn/naive_bayes.py
text: @user1:
```suggestion
        - integer: Sets the minimum number of categories per feature to
```

diff_hunk: @@ -1056,6 +1066,10 @@ class CategoricalNB(_BaseDiscreteNB):
     n_features_ : int
         Number of features of each sample.
 
+    n_categories_ : ndarray (n_features,)
path: sklearn/naive_bayes.py
text: @user1:
```suggestion
    n_categories_ : ndarray of shape (n_features,), dtype=int
```

diff_hunk: @@ -1164,6 +1180,21 @@ def _init_counters(self, n_effective_classes, n_features):
         self.category_count_ = [np.zeros((n_effective_classes, 0))
                                 for _ in range(n_features)]
 
+    def _init_n_categories(self, X):
+        feature_n_categories = X.max(axis=0) + 1
+        if self.min_categories is not None:
+            # unsafe casting allows float to be coerced to int
+            n_categories_ = np.maximum(feature_n_categories,
+                                       self.min_categories,
+                                       dtype=np.int,
+                                       casting='unsafe')
+            if np.shape(n_categories_) != feature_n_categories.shape:
+                raise ValueError('min_categories must be scalar, array-like '
path: sklearn/naive_bayes.py
text: @user1:
If I am not wrong, this error can only be trigger with `n_categories` being an array with an unexpected size. We would need an error message more specific then:

```python
raise ValueError(
    f"'min_categories' should have a shape ({X.shape[1]},) when an array-like is "
    f"provided. Got {self.min_categories.shape} instead.
)
```

diff_hunk: @@ -698,6 +700,51 @@ def test_categoricalnb():
         clf = CategoricalNB(alpha=1, fit_prior=False)
         clf.fit(X, y, sample_weight=sample_weight)
         assert_array_equal(clf.predict(np.array([[0, 0]])), np.array([2]))
+        assert_array_equal(clf.n_categories_, np.array([2, 2]))
+
+
+def test_categoricalnb_with_min_categories():
+    # None as n_categories is checked by default in test_categoricalnb
path: sklearn/tests/test_naive_bayes.py
text: @user1:
You can remove this comment

diff_hunk: @@ -1031,6 +1031,16 @@ class CategoricalNB(_BaseDiscreteNB):
         Prior probabilities of the classes. If specified the priors are not
         adjusted according to the data.
 
+    min_categories : int or array-like or None, default=None
+        Minimum number of categories per feature.
+
+        - int : Sets the minimum number of categories per feature to
+          `n_categories` for each features.
+        - array-like : shape (n_features,) where `n_categories[i]` holds the
+          minimum number of categories for the ith column of the input.
+        - None : Determines the number of categories automatically from the
path: sklearn/naive_bayes.py
text: @user1:
```suggestion
        - None (default): Determines the number of categories automatically from the
```

diff_hunk: @@ -698,6 +700,51 @@ def test_categoricalnb():
         clf = CategoricalNB(alpha=1, fit_prior=False)
         clf.fit(X, y, sample_weight=sample_weight)
         assert_array_equal(clf.predict(np.array([[0, 0]])), np.array([2]))
+        assert_array_equal(clf.n_categories_, np.array([2, 2]))
+
+
+def test_categoricalnb_with_min_categories():
+    # None as n_categories is checked by default in test_categoricalnb
+
+    X_n_categories = np.array([[0, 0], [0, 1], [0, 0], [1, 1]])
+    y_n_categories = np.array([1, 1, 2, 2])
+
+    # Check min_categories with int
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories=3)
+    clf.fit(X_n_categories, y_n_categories)
+    X1_count, X2_count = clf.category_count_
+    assert_array_equal(X1_count, np.array([[2, 0, 0], [1, 1, 0]]))
+    assert_array_equal(X2_count, np.array([[1, 1, 0], [1, 1, 0]]))
+    data_with_unseen_feature_2 = np.array([[0, 2]])
+    predictions = clf.predict(data_with_unseen_feature_2)
+    assert_array_equal(predictions, np.array([1]))
+    assert_array_equal(clf.n_categories_, np.array([3, 3]))
+
+    # Check min_categories with list
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories=[3, 4])
+    clf.fit(X_n_categories, y_n_categories)
+    X1_count, X2_count = clf.category_count_
+    assert_array_equal(X1_count, np.array([[2, 0, 0], [1, 1, 0]]))
+    assert_array_equal(X2_count, np.array([[1, 1, 0, 0], [1, 1, 0, 0]]))
+    data_with_unseen_feature_3 = np.array([[0, 3]])
+    predictions = clf.predict(data_with_unseen_feature_3)
+    assert_array_equal(predictions, np.array([1]))
+    assert_array_equal(clf.n_categories_, np.array([3, 4]))
+
+    # check min_categories with min less than actual
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories=1)
+    clf.fit(X_n_categories, y_n_categories)
+    assert_array_equal(clf.n_categories_, np.array([2, 2]))
+
+    # does not accept string
+    clf = CategoricalNB(alpha=1, fit_prior=False, min_categories='bad_arg')
+    assert_raises(ValueError, clf.fit, X_n_categories, y_n_categories)
path: sklearn/tests/test_naive_bayes.py
text: @user1:
You should use pytest instead of `assert_raises` (we are removing those):

```python
with pytest.raises(ValueError, match=err_msg):
    CategoricalNB(....).fit(X, y)
```

`err_msg` will be a partial string which will correspond to the error (partially) message.
Ensure that we match the error message each time to be sure that we are raising the error that we expect.

@author:
Sounds good, done!