lmcinnes / lmcinnes/umap

Error when fitting UMAP with a target vector and target_metric != "categorical"

Open
#110 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
8.3k
Forks
871
Avg merge
1d 13h
Merged PRs (30d)
5

Description

Hi,

I tried to fit UMAP with a target vector `y` and several metrics and I got an error.

The following code will result in an error.
```python
import numpy as np
from umap import UMAP

rng = np.random.RandomState(123)
n_samples = 10
n_features = 48
n_classes = 2

X = rng.randn(n_samples, n_features)
y = rng.randint(n_classes, size=n_samples)

umap = UMAP(n_neighbors=3, random_state=123,
target_metric="euclidean", angular_rp_forest=False)
res = umap.fit_transform(X, y)
```

```python
AttributeError Traceback (most recent call last)
in ()
1 umap = UMAP(n_neighbors=3, random_state=123, target_metric="euclidean", angular_rp_forest=False)
----> 2 res = umap.fit_transform(X, y)

~/anaconda3/lib/python3.5/site-packages/umap/umap_.py in fit_transform(self, X, y)
1521 Embedding of the training data in low-dimensional space.
1522 """
-> 1523 self.fit(X, y)
1524 return self.embedding_
1525

~/anaconda3/lib/python3.5/site-packages/umap/umap_.py in fit(self, X, y)
1459 1.0,
1460 1.0,
-> 1461 False,
1462 )
1463 # product = self.graph_.multiply(target_graph)

~/anaconda3/lib/python3.5/site-packages/umap/umap_.py in nearest_neighbors(X, n_neighbors, metric, metric_kwds, angular, random_state, verbose)
246 n_iters = max(5, int(round(np.log2(X.shape[0]))))
247
--> 248 rp_forest = make_forest(X, n_neighbors, n_trees, rng_state, angular)
249 leaf_array = rptree_leaf_array(rp_forest)
250 knn_indices, knn_dists = metric_nn_descent(

~/anaconda3/lib/python3.5/site-packages/umap/rp_tree.py in make_forest(data, n_neighbors, n_trees, rng_state, angular)
706 result = [
707 flatten_tree(make_tree(data, rng_state, leaf_size, angular), leaf_size)
--> 708 for i in range(n_trees)
709 ]
710 except (RuntimeError, RecursionError):

~/anaconda3/lib/python3.5/site-packages/umap/rp_tree.py in (.0)
706 result = [
707 flatten_tree(make_tree(data, rng_state, leaf_size, angular), leaf_size)
--> 708 for i in range(n_trees)
709 ]
710 except (RuntimeError, RecursionError):

~/anaconda3/lib/python3.5/site-packages/umap/rp_tree.py in flatten_tree(tree, leaf_size)
638 n_leaves = num_leaves(tree)
639
--> 640 if len(tree.hyperplane.shape) > 1:
641 # sparse case
642 max_hyperplane_nnz = max_sparse_hyperplane_size(tree)

AttributeError: 'NoneType' object has no attribute 'shape'
```

It looks like tree.hyperplane is `None`. Looking at the called functions, `make_tree` calls either `make_angular_tree `, `make_euclidean_tree` or their sparse versions. They all have the same structure, so let's take `make_euclidean_tree`:

https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L439-L455

The `hyperplane` attribute is set to `None` if the condition is not satisfied. Looking at [euclidean_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L131-L217), I don't think this function can return `None` for `hyperplane_vector` because it is defined and modified there only:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L170-L173
I would guess that this error occurs when there is only one node in the graph.

I did a little more testing and it looks like that the error only occurs if one of the following criteria is satisfied:
* `n_samples (i.e. X.shape[0]) <= 10`
* `n_samples > 10` and `n_neighbors >= n_samples `

### Edit 1
It seems like the error occurs in those scenarios because of the definition of `leaf_size` in `make_forest`:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L704
and since `indices.shape[0]` is equal to `n_samples`:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L546
the condition in the `if else` loop of `make_euclidean_tree` is never satisfied.

### Edit 2
`n_neighbors` is defined at the beginning of the `fit` method of UMAP:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1336-L1347
but afterwards, `n_neighbors` and `self.n_neighbors` are both used in the method:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1361-L1366
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1390-L1392
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1445-L1447
Using only `n_neighbors` is probably what is intended and I think that it would fix the issue for the second setting. The first setting would still raise an error because `leaf_size` would be equal to 10 and it would be greater than or equal to the number of samples.

### NB

[angular_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L29-L53), [euclidean_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L132-L156), [sparse_angular_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L221-L250) and [sparse_euclidean_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L331-L360) all have the same docstring issue (the Returns section doesn't match what is returned by the function).

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the supplied fit_transform reproduction, then inspect umap/umap_.py around n_neighbors handling and umap/rp_tree.py around make_forest, make_euclidean_tree, and the random projection split functions. Verify behavior for the reported small-sample and large-n_neighbors cases, and confirm that the documented return values match the split functions.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
machine-learning
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.