Repository: scikit-learn/scikit-learn
Pull request: [MRG] Fix IncrementalPCA when final batch is smaller than dimensions required for SVD.
#### Reference Issues/PRs
This Pull Request intends to fix #12234 caused by smaller final batch during training of Incremental PCA.

#### Any other comments?
considering central limit theorem, sampling statistics (first and second central moments looking from the implementation) from batch to batch should already converge at population statistics with or without the final batch. Smaller final batch however might, I think, cause algebraic problem for SVD as there isn't enough information to infer singular values and eigenvectors.

tensorflow.train.batch uses allow_smaller_final_batch to handle this situation and might also work here.

Problem statement:
IncrementalPCA fails if data size % batch size < n_components
#### Description

`IncrementalPCA` throws`n_components=%r must be less or equal to the batch number of samples %d`

The error occurs because the last batch generated by `utils.gen_batch` may be smaller than `batch_size`.

#### Steps/Code to Reproduce

```python
from sklearn.datasets import load_iris
from sklearn.decomposition import PCA, IncrementalPCA
   
iris = load_iris()
X = iris.data[:101]
ipca = IncrementalPCA(n_components=2, batch_size=10)
X_ipca = ipca.fit_transform(X)
```

I reduced the iris data to 101 instances, so the last batch has only a single data instance, which is less than the number of components.

As far as I see, none of the current unit tests run into this. (`test_incremental_pca_batch_signs` could, if the code that raises the exception would compare `self.n_components_` with `n_samples` - which it should, but doesn't).

Skipping the last batch if it is to small, that is, changing

```
        for batch in gen_batches(n_samples, self.batch_size_):
                self.partial_fit(X[batch], check_input=False)
```

to

```
        for batch in gen_batches(n_samples, self.batch_size_):
            if self.n_components is None \
                    or X[batch].shape[0] >= self.n_components:
                self.partial_fit(X[batch], check_input=False)
```

fixes the problem. @kastnerkyle, please confirm that this solution seems OK before I go preparing the PR and tests.

#### Expected Results

No error is thrown.

#### Actual Results

`ValueError: n_components=2 must be less or equal to the batch number of samples 1.`

#### Versions

```
Darwin-18.0.0-x86_64-i386-64bit
Python 3.6.2 |Continuum Analytics, Inc.| (default, Jul 20 2017, 13:14:59)
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.57)]
NumPy 1.15.2
SciPy 1.1.0
Scikit-Learn 0.20.0
```

Hints from issue discussion:
Looks like this was introduced in #9303 so @wallygauze should probably take a look too.
I haven't checked in-depth how incremental pca does partial fits, but does it really need `n_components` to be <= to the `batch_size` (`n_samples` in partial_fit) - especially does it need this to hold for _every_ batch? Or should the actual requirement be in `fit` that `n_components <= n_samples` (all of them, not a single batch) and possibly also `n_components <= batch_size` (so that at least one batch is big enough)?

In any case, I don't think dropping the last batch if it is too small is a good solution - it might be an important part of the data.
Looked like a bug and a regression to me
anyone looking into this for 0.20.1?
I don't know of anyone working on it, but I would consider it a blocker for
0.20.1 as it's an important regression that should not be hard to fix

Hi, if this issue is still open for a fix, will try to look at this issue and produce a PR. 👍

Commit message: update test

Patch to review:
diff --git a/doc/whats_new/v0.20.rst b/doc/whats_new/v0.20.rst
index ca6589bd895d3..5af66b9629bd5 100644
--- a/doc/whats_new/v0.20.rst
+++ b/doc/whats_new/v0.20.rst
@@ -51,6 +51,12 @@ Changelog
   for values of ``n_informative`` parameter larger than 64.
   :issue:`10811` by :user:`Roman Feldbauer <VarIr>`.
 
+:mod:`sklearn.decomposition`
+............................
+- |Fix| :class:`decomposition.IncrementalPCA` to use larger final batch
+  combining last two batches and prevent insufficient sample size for SVD.
+  :issue:`12234` by :user:`Ming Li <minggli>`.
+
 :mod:`sklearn.ensemble`
 .......................
 
@@ -150,7 +156,7 @@ occurs due to changes in the modelling logic (bug fixes or enhancements), or in
 random sampling procedures.
 
 - :class:`cluster.MeanShift` (bug fix)
-- :class:`decomposition.IncrementalPCA` in Python 2 (bug fix)
+- :class:`decomposition.IncrementalPCA` in Python 2 and larger final batch (bug fix)
 - :class:`decomposition.SparsePCA` (bug fix)
 - :class:`ensemble.GradientBoostingClassifier` (bug fix affecting feature importances)
 - :class:`isotonic.IsotonicRegression` (bug fix)
diff --git a/sklearn/decomposition/incremental_pca.py b/sklearn/decomposition/incremental_pca.py
index 779ebf42b20f1..a4cfd7810ece0 100644
--- a/sklearn/decomposition/incremental_pca.py
+++ b/sklearn/decomposition/incremental_pca.py
@@ -196,7 +196,8 @@ def fit(self, X, y=None):
         else:
             self.batch_size_ = self.batch_size
 
-        for batch in gen_batches(n_samples, self.batch_size_):
+        for batch in gen_batches(n_samples, self.batch_size_,
+                                 larger_final_batch=True):
             self.partial_fit(X[batch], check_input=False)
 
         return self
diff --git a/sklearn/decomposition/tests/test_incremental_pca.py b/sklearn/decomposition/tests/test_incremental_pca.py
index f6f39db22c944..9665df56b4857 100644
--- a/sklearn/decomposition/tests/test_incremental_pca.py
+++ b/sklearn/decomposition/tests/test_incremental_pca.py
@@ -175,6 +175,22 @@ def test_incremental_pca_batch_values():
         assert_almost_equal(i, j, decimal=1)
 
 
+def test_incremental_pca_batch_rank():
+    # Test that sample size in each batch is always larger or equal to dim of X
+    rng = np.random.RandomState(1999)
+    n_samples = 100
+    n_features = 20
+    X = rng.randn(n_samples, n_features)
+    all_components = []
+    batch_sizes = np.arange(20, 40, 3)
+    for batch_size in batch_sizes:
+        ipca = IncrementalPCA(n_components=20, batch_size=batch_size).fit(X)
+        all_components.append(ipca.components_)
+
+    for i, j in zip(all_components[:-1], all_components[1:]):
+        assert_almost_equal(i, j, decimal=1)
+
+
 def test_incremental_pca_partial_fit():
     # Test that fit and partial_fit get equivalent results.
     rng = np.random.RandomState(1999)
diff --git a/sklearn/utils/__init__.py b/sklearn/utils/__init__.py
index 4c22752030703..ab2fce932e676 100644
--- a/sklearn/utils/__init__.py
+++ b/sklearn/utils/__init__.py
@@ -400,7 +400,7 @@ def safe_sqr(X, copy=True):
     return X
 
 
-def gen_batches(n, batch_size):
+def gen_batches(n, batch_size, larger_final_batch=False):
     """Generator to create slices containing batch_size elements, from 0 to n.
 
     The last slice may contain less than batch_size elements, when batch_size
@@ -411,6 +411,8 @@ def gen_batches(n, batch_size):
     n : int
     batch_size : int
         Number of element in each batch
+    larger_final_batch : bool
+        Whether to combine two last batches to avoid a small final batch.
 
     Yields
     ------
@@ -429,6 +431,8 @@ def gen_batches(n, batch_size):
     start = 0
     for _ in range(int(n // batch_size)):
         end = start + batch_size
+        if larger_final_batch and end + batch_size > n:
+            continue
         yield slice(start, end)
         start = end
     if start < n:


Code review comments:
diff_hunk: @@ -150,7 +156,7 @@ occurs due to changes in the modelling logic (bug fixes or enhancements), or in
 random sampling procedures.
 
 - :class:`cluster.MeanShift` (bug fix)
-- :class:`decomposition.IncrementalPCA` in Python 2 (bug fix)
+- :class:`decomposition.IncrementalPCA` in Python 2 and larger final batch (bug fix)
path: doc/whats_new/v0.20.rst
text: @user1:
"and larger final batch" is a strange way to express it for a user unfamiliar with the issue

Anyway, this isn't relevant to 0.20.0 and shouldn't be here. We can make a similar section above.

@author:
good point. moved to a new section in 0.20.1 notes

diff_hunk: @@ -175,6 +175,22 @@ def test_incremental_pca_batch_values():
         assert_almost_equal(i, j, decimal=1)
 
 
+def test_incremental_pca_batch_rank():
+    # Test that sample size in each batch is always larger or equal to dim of X
path: sklearn/decomposition/tests/test_incremental_pca.py
text: @user1:
We don't care about dim of X, we care about n_components

@author:
sure! 😃