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

[NelleV]

Right now, the MDS uses a slow majorization optimization method instead of falling back to the SVD when the full matrix is known.

[amueller]

#1452 is merged now :)

[NelleV]

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]

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

[FlorianWilhelm]

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

[GaelVaroquaux]

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]

@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]

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]

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]

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]

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]

@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]

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?

[adrinjalali]

I think we can close this one.