lmcinnes / lmcinnes/pynndescent

Problems with sparse

Open
#65 7 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
970
Forks
107
PR merge metrics
No merged PRs in 30d

Description

I've been trying to get this to work with sparse matrices.

The setup:
```python
>>> import pynndescent
>>> import scipy.sparse as sp
>>> x = sp.random(1000, 1000, density=0.01)
```

Next, I try to construct the index; this raises an error:
```python
>>> nn = pynndescent.NNDescent(x)
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
in
----> 1 pynndescent.NNDescent(x)

~/miniconda3/envs/tsne/lib/python3.7/site-packages/pynndescent/pynndescent_.py in __init__(self, data, metric, metric_kwds, n_neighbors, n_trees, leaf_size, pruning_level, tree_init, random_state, algorithm, max_candidates, n_iters, delta, rho, n_jobs, seed_per_row, verbose)
565 )
566 metric_nn_descent = sparse.make_sparse_nn_descent(
--> 567 distance_func, tuple(metric_kwds.values())
568 )
569 if verbose:

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

Okay, so `metric_kwds` must be specified. Very unexpected, but ok, I can fix that.

```python
>>> nn = pynndescent.NNDescent(x, metric_kwds={}) # works!
```

Great, so I've got the index. Now I want to query it:
```python
>>> nn.query(x)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
in
----> 1 nn.query(x)

~/miniconda3/envs/tsne/lib/python3.7/site-packages/pynndescent/pynndescent_.py in query(self, query_data, k, queue_size)
697 """
698 # query_data = check_array(query_data, dtype=np.float64, order='C')
--> 699 query_data = np.asarray(query_data).astype(np.float32)
700 self._init_search_graph()
701 init = initialise_search(

TypeError: float() argument must be a string or a number, not 'coo_matrix'
```

Again, weird that I can build an index for a sparse matrix, but not query with it. Ok, I convert it to a dense matrix:

```python
>>> nn.query(x.toarray())
---------------------------------------------------------------------------
TypingError Traceback (most recent call last)
in
----> 1 nn.query(x.toarray())

~/miniconda3/envs/tsne/lib/python3.7/site-packages/pynndescent/pynndescent_.py in query(self, query_data, k, queue_size)
706 self._random_init,
707 self._tree_init,
--> 708 self.rng_state,
709 )
710 result = self._search(

~/miniconda3/envs/tsne/lib/python3.7/site-packages/pynndescent/pynndescent_.py in initialise_search(forest, data, query_points, n_neighbors, init_from_random, init_from_tree, rng_state)
73 ):
74 results = make_heap(query_points.shape[0], n_neighbors)
---> 75 init_from_random(n_neighbors, data, query_points, results, rng_state)
76 if forest is not None:
77 for tree in forest:

~/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/dispatcher.py in _compile_for_args(self, *args, **kws)
348 e.patch_message(msg)
349
--> 350 error_rewrite(e, 'typing')
351 except errors.UnsupportedError as e:
352 # Something unsupported is present in the user code, add help info

~/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/dispatcher.py in error_rewrite(e, issue_type)
315 raise e
316 else:
--> 317 reraise(type(e), e, None)
318
319 argtypes = []

~/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/six.py in reraise(tp, value, tb)
656 value = tp()
657 if value.__traceback__ is not tb:
--> 658 raise value.with_traceback(tb)
659 raise value
660

TypingError: Failed in nopython mode pipeline (step: nopython frontend)
Internal error at :
--%<----------------------------------------------------------------------------
Traceback (most recent call last):
File "/home/pavlin/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/errors.py", line 627, in new_error_context
yield
File "/home/pavlin/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/typeinfer.py", line 201, in __call__
assert ty.is_precise()
AssertionError

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
File "/home/pavlin/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/typeinfer.py", line 144, in propagate
constraint(typeinfer)
File "/home/pavlin/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/typeinfer.py", line 202, in __call__
typeinfer.add_type(self.dst, ty, loc=self.loc)
File "/home/pavlin/miniconda3/envs/tsne/lib/python3.7/contextlib.py", line 130, in __exit__
self.gen.throw(type, value, traceback)
File "/home/pavlin/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/errors.py", line 635, in new_error_context
six.reraise(type(newerr), newerr, tb)
File "/home/pavlin/miniconda3/envs/tsne/lib/python3.7/site-packages/numba-0.43.1-py3.7-linux-x86_64.egg/numba/six.py", line 659, in reraise
raise value
numba.errors.InternalError:
[1] During: typing of argument at /home/pavlin/miniconda3/envs/tsne/lib/python3.7/site-packages/pynndescent/pynndescent_.py (39)
--%<----------------------------------------------------------------------------

File "../../miniconda3/envs/tsne/lib/python3.7/site-packages/pynndescent/pynndescent_.py", line 39:
def init_from_random(n_neighbors, data, query_points, heap, rng_state):
for i in range(query_points.shape[0]):
^

This error may have been caused by the following argument(s):
- argument 1: cannot determine Numba type of

This is not usually a problem with Numba itself but instead often caused by
the use of unsupported features or an issue in resolving types.
```

I noticed something to do with csr_matrices in that error, so maybe COO format is not supported?

```python
>>> nn.query(x.tocsr())
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
in
----> 1 nn.query(x.tocsr())

~/miniconda3/envs/tsne/lib/python3.7/site-packages/pynndescent/pynndescent_.py in query(self, query_data, k, queue_size)
697 """
698 # query_data = check_array(query_data, dtype=np.float64, order='C')
--> 699 query_data = np.asarray(query_data).astype(np.float32)
700 self._init_search_graph()
701 init = initialise_search(

ValueError: setting an array element with a sequence.
```

Same error as with the COO matrix.

A little bit of environment info:
```
Python 3.7.3
---------------------------
numba==0.43.1
scipy==1.2.0
pynndescent==0.3.0
```

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

Reproduce the sparse-matrix cases with the Python 3.7, SciPy 1.2.0, Numba 0.43.1, and pynndescent 0.3.0 versions shown. Read pynndescent_.py around NNDescent.__init__, query, and initialise_search, then compare the construction and query paths for COO, CSR, and dense inputs. Done means the intended sparse workflow behaves consistently and has regression coverage for the reported failures.

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
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.