thanks gael,
let me start with practical points regarding code changes and then i'll
turn to the discussion.
1. do we want the implementation in scikits to be general? there is no loss
in efficiency at this point to compute it in all ways possible. it's what
you do with the laplacian (solvers etc.,.) that might determine which you
one you use. (and as we know, in the long run this is going to be available
in scipy itself).
2. regarding the default option, i'm planning on running things on a bunch
of interpoint comparison matrices, whose properties i yet don't know. from
my reading of uvl, proposition 4 and section 7 (perturbation theory), it
seemed quite clear that for graphs with very low degrees spectral
clustering with Lsym can be problematic. in my case of typically small
world graphs, this is like to be true of at least a handful of nodes
(especially after thresholding).
3. the return_diag option: i still don't understand intuitively what this
is supposed to represent in the Lsym case (current normed option in code).
(i'm reading the published doc in stat. comput. so the pages are off -
hence i'm referring to sections)
> that's helpful. the difference was in the adjacency matrix. i was assuming
> > a system with a self loop on the nodes with arbitrary weights (i.e., a
> > general form of a undirected graph).
>
> AFAIK, spectral clustering and spectral embedding do not work with
> weights on the diagonal. In the UvL tutorial that you point to, she says
> on page 4, one paragraph above prop 2 that the graph laplacian does not
> depend on the weights of the diagonal.
>
this is true only in the case of the L = D-W (the unnormalized graph
Laplacian). the diagonal contributes to D and W equally. not so for the
normalized cases.
> > The reason is that the eigenvectors of Lrw are cluster indicator vectors
> 1Ai
> > , while the eigenvectors of Lsym are additionally multiplied with D1/2,
> which
> > might lead to undesired arti- facts. As using Lsym also does not have any
> > computational advantages, we thus advocate for using Lrw.
>
> I disagree with this statement. Using Lsym enables to use an SPD solver
> to diagonalize the matrix. SPD solvers are not only faster, they are in
> addition much more stable if the spectrum of the matrix has almost
> degenerate eigenvalues, because they can enforce orthogonality between
> the corresponding eigenvectors. Back when I implemented this, my
> experience was that using non SPD solvers was too prone to numerical
> errors to be useful in many cases.
>
i wasn't thinking in terms of the solvers yet. one step at a time! here i
was only trying to make the code work generally, which i think we can do.
> I am a bit surprised that UvL advocates Lrw. I find her arguments a bit
> weak. Most importantly, there is exact mathematical correspondance
> between the two approaches. Indeed, the generalized eigenvalue problem of
> the non-symmetric approach is:
>
i think that's exactly what she states in proposition 4
The only reason for which one approach might be prefered to another is
> better speed or stability properties of the solvers on one of the
> problems or the other.
>
possibly. i'll get to solvers soon.
> all sklearners: I'd like to propose allowing the different normalizations
> > and if necessary switching to Lrw as the default and allowing for any
> > adjacency matrix. any objections?
>
> I have an objection. The type of solvers down the line are fairly
> different. It is not just a matter of changing the normalization. In
> addition, I'd like to be convinced that there is an actual benefit,
> because my experience was the opposite. That said, when I did it, I used
> a fairly naive approach to solving the generalized eigenvalue problem.
>
i'm assuming you have no objections with implementing the general laplacian
code, just with changing the default to Lrw.
> Is there a reason in particular that you are looking at this
> normalization? Looking at this reason might help us understand the stakes
> here.
>
my general reasons are due to the fact that a lot of the data i deal with
invariably end up having low degrees and the perturbation theory arguments
proposed against Lsym seemed rational (i'm not a mathematician).
cheers,
satra
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Scikit-learn-general mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
