[MRG+1] Reduce runtime of graph_lasso #9858
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
LGTM
|
|
Hi @TomDLT, I think the PEP8 error is now resolved; the tests looked OK on my screen. I've added said comment. It took me a little while to convince myself that this was true, but this short script can also verify it for anyone who is interested: import numpy as np
t = np.random.randint(1, 100, size=(100,100))
indices = np.arange(t.shape[0])
subt = np.ascontiguousarray(t[1:, 1:])
for idx in indices:
if idx > 0:
subt[idx-1] = t[idx-1][indices != idx]
subt[:, idx-1] = t[:, idx-1][indices != idx]
else:
subt[:] = t[1:, 1:]
assert np.all(subt == t[indices != idx].T[indices != idx].T) |
TomDLT
reviewed
Oct 2, 2017
sklearn/covariance/graph_lasso_.py
Outdated
| for i in range(max_iter): | ||
| for idx in range(n_features): | ||
| sub_covariance = np.ascontiguousarray( | ||
| covariance_[indices != idx].T[indices != idx]) | ||
| # for each idx, the sub_covariance matrix is the covariance_ |
There was a problem hiding this comment.
I think this comment is good but a bit too long.
I would have gone with something less verbose, such as:
# To keep the contiguous matrix `sub_covariance` equal to
# covariance_[indices != idx].T[indices != idx]
# we only need to update 1 column and 1 line when idx changes
Indeed, for some weird reason I don't see the commit 070fdcf in this page... Anyway, thanks for the script, this is indeed non trivial. |
|
@TomDLT I've replaced my version of the comment with yours. Thanks. |
|
All right, I approved this change, let's just wait for a second reviewer |
|
thx @stevendbrown |
maskani-moh
pushed a commit
to maskani-moh/scikit-learn
that referenced
this pull request
Nov 15, 2017
* reduce runtime of graph_lasso * fixed line length overrun * added comment explaining the change * changed explanation comment
jwjohnson314
pushed a commit
to jwjohnson314/scikit-learn
that referenced
this pull request
Dec 18, 2017
* reduce runtime of graph_lasso * fixed line length overrun * added comment explaining the change * changed explanation comment
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Reference Issue
None.
What does this implement/fix? Explain your changes.
For a 1288x1288 empirical covariance matrix,
sklearn.covariance.graph_lassocurrently spends 70-80% of it's runtime creatingsub_covarianceon my computer. This change reduces that to ~3.5% of the function's runtime, andnp.allclose(...)comparing both of the arrays in the result tuple returnTruefor each. Iterations have the same losses & dual gaps, and calls tograph_lassoend after the same number of iterations, so I don't see a functional change with my data.Any other comments?
Just noticed that this may interact with #4787. My dataset is quite dense, so the runtime of
graph_lassobased on that PR is almost double that of the original function.