8000 Make return_std 20x faster in Gaussian Processes (includes solution) · Issue #9234 · scikit-learn/scikit-learn · GitHub
[go: up one dir, main page]
Skip to content

Make return_std 20x faster in Gaussian Processes (includes solution) #9234

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
AndreusUltimus opened this issue Jun 27, 2017 · 10 comments
Closed

Make return_std 20x faster in Gaussian Processes (includes solution) #9234

AndreusUltimus opened this issue Jun 27, 2017 · 10 comments
Labels
Easy Well-defined and straightforward way to resolve Enhancement

Comments

@AndreusUltimus
Copy link
AndreusUltimus commented Jun 27, 2017 •
edited by TomDLT
Loading

Two requests:

(1) Please replace this line:
https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/gaussian_process/gpr.py#L329

from this

    yvar -= np.einsum("ki,kj,ij->k", K_trans, K_trans, K_inv)

to this

    sum1 = np.dot(K_trans,K_inv).T
    yvar -= np.einsum("ki,ik->k", K_trans, sum1)

For an input data set of size 800x1, the time difference is 12.7 seconds to 0.2 seconds. I have validated that the result is the same up to 1e-12 or smaller.

(2) Please cache the result of the K_inv computation. It depends only on the result of training, and can be very costly for repeated calls to the class.
@AndreusUltimus
Copy link
Author
AndreusUltimus commented Jun 27, 2017 •
edited by TomDLT
Loading

Complete solution, starting here https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/gaussian_process/gpr.py#L322

    if not hasattr(self,'K_inv_'):
        L_inv = solve_triangular(self.L_.T, np.eye(self.L_.shape[0]))
        self.K_inv_ = L_inv.dot(L_inv.T)
        
    # Compute variance of predictive distribution
    y_var = self.kernel_.diag(X)
    sum1 = np.dot(K_trans,self.K_inv_).T
    y_var1 = y_var - np.einsum("ki,ik->k", K_trans, sum1)
    # y_var2 = y_var - np.einsum("ki,kj,ij->k", K_trans, K_trans, self.K_inv_)
    # assert np.all(np.abs(y_var1-y_var2)<1e-12)
    y_var = y_var1

@TomDLT
Copy link
Member
TomDLT commented Jun 27, 2017 •
edited
Loading

Thanks for the suggestion. Can you open a pull-request with this change?

Note that the first part was already solved in #8591, but not the second

@AndreusUltimus
Copy link
Author

I'm sorry, I can't. I'm posting this from an environment where I can access the website, but none of the other GitHub tools.

@jnothman
Copy link
Member
jnothman commented Jun 27, 2017 via email

@jnothman jnothman added Easy Well-defined and straightforward way to resolve Enhancement Need Contributor labels Jun 27, 2017
@minghui-liu
Copy link
Contributor

I would like to help and make the changes if that's ok.

@jmschrei
Copy link
Member
jmschrei commented Jun 27, 2017 via email

@minghui-liu minghui-liu mentioned this issue Jun 28, 2017
Closed
@ogrisel
Copy link
Member
ogrisel commented Sep 1, 2017

Fixed in 6e01fef from #9236. Thanks @minghui-liu and @Andrewww.

@ogrisel ogrisel closed this as completed Sep 1, 2017
@ogrisel
Copy link
Member
ogrisel commented Sep 1, 2017

BTW I did not observe a 20x speed up a in my tests. The speed stayed approximately the same on a 1000x5 dataset generated with sklearn.datasets.make_regression.

Note: the second call to predict is significantly faster because of the cached K_inv.

@Andrewww I would be curious to know more about the kind of data where you observed the initially reported speedup.

@AndreusUltimus
Copy link
Author
AndreusUltimus commented Sep 1, 2017 •
edited
Loading

Hmmm.... This was literally a make-or-break change to the code for me, i.e., the code was so slow I could not actually use it without this change (the change to the .einsum() call).

Only thing I can think of is: I'm on Windows 7 x64 / Anaconda 3.1.4. Doesn't numpy sometimes behave differently on different platforms? Maybe the Windows einsum() call is a lot slower than on Linux?

Also, apparently it was already fixed in an earlier issue #8591

@refrigerator
Copy link

Is anyone still having problems with this?

I have a model trained on 15,000 data points, and predictions with return_std=True take about 2 minutes for a single prediction, whereas with return_std=False it's basically instant.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Easy Well-defined and straightforward way to resolve Enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
7 participants
@jnothman @ogrisel @refrigerator @AndreusUltimus @jmschrei @minghui-liu @TomDLT
2A3A
0