8000 MDS: fall back to SVD when the full similarity matrix is known · Issue #1453 · scikit-learn/scikit-learn · GitHub
[go: up one dir, main page]
Skip to content

MDS: fall back to SVD when the full similarity matrix is known #1453

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
NelleV opened this issue Dec 8, 2012 · 13 comments
Closed

MDS: fall back to SVD when the full similarity matrix is known #1453

NelleV opened this issue Dec 8, 2012 · 13 comments
Assignees
@NelleV
Labels
Enhancement module:manifold

Comments

@NelleV
Copy link
Member
NelleV commented Dec 8, 2012

Right now, the MDS uses a slow majorization optimization method instead of falling back to the SVD when the full matrix is known.
@ghost ghost assigned NelleV Dec 8, 2012
@NelleV NelleV mentioned this issue Dec 9, 2012
Closed
@amueller
Copy link
Member
amueller commented Jan 7, 2013

#1452 is merged now :)

@NelleV
Copy link
Member Author
NelleV commented Jan 7, 2013

Yes... I'm just having trouble with this part. I thought it was obvious, but I don't get the same results with an SVD so far. I'll need more time on that PR.

@amueller
Copy link
Member
amueller commented Jan 7, 2013

No worries. Take your time. I just wanted to let you know that you don't have to wait for me any more ;)

@FlorianWilhelm
Copy link
Contributor

Is someone still working on this issue? Otherwise, I'd like to take a closer look on it.

@GaelVaroquaux
Copy link
Member

Is someone still working on this issue?

Not that I know. Let's wait a bit to see if someone answers.

Otherwise, I'd like to take a closer look on it.

That would be great!

@FlorianWilhelm FlorianWilhelm mentioned this issue May 10, 2014
Closed
@FlorianWilhelm
Copy link
Contributor

@GaelVaroquaux @amueller This issue was harder than I expected. Would you be so kind to take a look at it to see if this goes into the right direction? Thanks

@FlorianWilhelm
Copy link
Contributor

Are there any comments on my PR? I am pretty conviced that my PR resolves this issue but I would love to get at least some feedback.

@jeffrey-hokanson
Copy link

My understanding is the SVD can be used to solve the "Classical MDS Problem" ([1] Section 13.6) but solving the "Metric MDS Problem" ([1] Section 13.8) requires a nonlinear least squares-type algorithm, such as SMACOF. Metric MDS is the current default for MDS and as such, I don't think it would be appropriate to switch which problem is solve based on the input.

[1] Modern Multivariate Statistical Techniques, Alan Julian Izenman, 2013.

@NelleV
Copy link
Member Au 8000 thor
NelleV commented Jul 29, 2014

My understanding is the SVD can be used to solve the "Classical MDS
Problem" ([1] Section 13.6) but solving the "Metric MDS Problem" ([1]
Section 13.8) requires a nonlinear least squares-type algorithm, such as
SMACOF. Metric MDS is the current default for MDS and as such, I don't
think it would be appropriate to switch which problem is solve based on the
input.

That is my understanding too.

[1] Modern Multivariate Statistical Techniques, Alan Julian Izenman, 2013.

—
Reply to this email directly or view it on GitHub
#1453 (comment)
.

@FlorianWilhelm
Copy link
Contributor

From Wikipedia:

Classical multidimensional scaling
Also known as Principal Coordinates Analysis, Torgerson Scaling or Torgerson–Gower scaling. Takes an input matrix giving dissimilarities between pairs of items and outputs a coordinate matrix whose configuration minimizes a loss function called strain.[1]

Metric multidimensional scaling
A superset of classical MDS that generalizes the optimization procedure to a variety of loss functions and input matrices of known distances with weights and so on. A useful loss function in this context is called stress, which is often minimized using a procedure called stress majorization.

My understanding is that the only difference is that with metric MDS you have the choice do define your own loss function. The loss function as implemented in _smacof (if metric=True) is

stress = ((dis.ravel() - disparities.ravel()) ** 2).sum() / 2

To my understanding this is the strain as defined in classical MDS. In the more general metric MDS the usual way of defining the normalized stress is

stress = ((dis.ravel() - disparities.ravel()) ** 2).sum() / dis.ravel()**2.sum()

as far as I know but it could be any arbitrary other metric. In this case you really need SMACOF but not in the former.

So, as long as this MDS implementation does not allow for non-classical loss functions it can be solved with SVD. But anyway, I am no MDS expert and I was just looking for an issue with the "easy" label to contribute to Scikit-Learn and I thought that at least the goal of the issue "falling back to SVD..." was agreed on.

@FlorianWilhelm
Copy link
Contributor

@NelleV You opened and also worked on this issue, right? What do you think? Should this issue be just closed then since SVD makes no sense for the general case of a metric MDS?

@NelleV
Copy link
Member Author
NelleV commented Jul 30, 2014

I opened the issue, hearing that metric MDS could be formulated as PCA, but now that I've tried formulating it, I'm not managing to, so I think I was confused between metric MDS and classic MDS and that this is not possible. @GaelVaroquaux , were you also thinking about classical MDS when we talked about it, and not metric MDS, or am I missing something obvious?

NelleV pushed a commit to NelleV/scikit-learn that referenced this issue Apr 2, 2015
@FlorianWilhelm @NelleV
FIX scikit-learn#1453: SVD method as option for MDS
a720390
@yxtay yxtay mentioned this issue Jun 18, 2016
Closed
@jsoutherland jsoutherland mentioned this issue Sep 26, 2017
Closed
@cmarmo cmarmo added module:manifold and removed Easy Well-defined and straightforward way to resolve labels Dec 3, 2021
@adrinjalali
Copy link
Member

I think we can close this one.

@adrinjalali adrinjalali closed this as not planned Won't fix, can't repro, duplicate, stale Apr 17, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@NelleV NelleV

Labels
Enhancement module:manifold
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
7 participants
@NelleV @GaelVaroquaux @amueller @jeffrey-hokanson @cmarmo @adrinjalali @FlorianWilhelm
0