4 ms·

SVD scales with the number of items cubed, w2v scales linearly. Typical real world vocabularies are 1-10M, not 10-100k. This article is FUD and best, and IMO, j

by fnl 9y ago

SVD scales with the number of items cubed, w2v scales linearly. Typical real world vocabularies are 1-10M, not 10-100k. This article is FUD and best, and IMO, just plain BS.

ctchocula 9y ago
My understanding was that you can get some savings from keeping the sparse matrix and running sparse SVD via scipy.sparse.linalg.svds(PMI, k=256). I am not certain about the exact time complexity however.
- fnl 9y ago
  Some minor space savings, maybe. But SVD runtime still scales with the cube of your vocabulary size. Good luck with SVD on a vocabulary from Wikipedia or Common Crawl. If anything, using traditional count-based approaches is good when you only can use a small corpus with tiny vocabularies (<100k) to develop your word embeddings. But that's not what this article is proclaiming. Oh, and yeah, do use fasttext, not the good old word2vec.
  - ctchocula 9y ago
    I don't think you are correct here. The advantage of using sparse storage and sparse matrix multiplication is that you can get savings in both storage and runtime. There would be no point in using sparse storage if runtime still scaled with the cube of vocab size. It would be that way if the best way of getting sparse SVD is by materializing a dense matrix product, but people have discovered smarter ways using sparse matvec. The time complexity for obtaining k eigenvalues seems to be O(dkn) where d is the average number of nonzeroes per row, and n is the vocab size [1]. Therefore, one can assert that sparse SVD too is linear in vocab size just like word2vec. This is corroborated by the link elsewhere in this thread that shows SVD enjoying lower wall clock time on the 1.9B word Wikipedia dataset [2]. [1] https://en.wikipedia.org/wiki/Lanczos_algorithm#Application_to_the_eigenproblem https://en.wikipedia.org/wiki/Lanczos_algorithm#Application_... [2] https://rare-technologies.com/making-sense-of-word2vec/ https://rare-technologies.com/making-sense-of-word2vec/
    - fnl 9y ago
      As to [1]: Yes, I was not honest in the sense that non-standard SVD implementations for generating your PMIs will scale with the square of |V|, not the cube. But as I will go on to show, that is not good enough to make count-based approaches competitive to predictive ones. Re. [2], these measurements by Radim have several issues; First, word2vec is a poor implementation, CPU-usage wise, as can be seen by profiling word2vec (fastText is much better at using your CPUs). Second, even Radim states there that his SVD-based results are significantly poorer than the w2v embeddings ("the quality of both SPPMI and SPPMI-SVD models is atrocious"). Third, Radim's conclusion there is: "TL;DR: the word2vec implementation is still fine and state-of-the-art, you can continue using it :-)". So I don't really get your points. Instead of referencing websites and blogs, lets take a deeper look at a "proponent" for count-based methods, in a peer-reviewed setting. In Goldberg et al.'s SPPMI model [1,2] they use truncated SVD. (FYI, that proposed model, SPPMI, is what got used in Radim's blog above.) So even if you wanted use SPPMI instead of the sub-optimal SVD (alone), you would first have to find a really good implementation of that, i.e., something that is competitive to fastTest. Also note that Goldberg only used 2 word-windows for SGNS in most comparisons, which makes the results for neural embeddings a bit dubious. You would typically use 5-10, and as shown in Table 5 of [2], SGNS is pretty much the winner on all cases as it "approaches" 10-word window. Next, I would only trust Hill's SimLex as proper evaluation targets for word similarity - simply look at the raw data of the various evaluation datasets yourself and read Hill's explanations why he created SimLex, and I am sure you will agree. "Coincidentally", it also is - by a huge margin - the most difficult dataset to get right (i.e., all approaches perform worst on SimLex). However, SGNS nearly always outperforms SVD/SSPMI on precisely that set. Finally, even Omar et al. had to conclude: "Applying the traditional count-based methods to this setting [=large-scale corpora] proved technically challenging, as they consumed too much memory to be efficiently manipulated." So even if they "wanted" to conclude that SVD is just as good as neural embeddings, their own results (Table 5) and this statment lead us to a clearly different conclusion: If you use enough window size, you are better off with neural embeddings, particularly for large corpora. And this work only compares W2V & GloVe to SVD & SPPMI, while fastText in turn works a lot better than "vanilla" SGNS and GloVe. What I do agree with is that properly tuning neural embeddings is a bit of a black art, much like anything with the "neural" tag on it... QED; This article is horseradish. Neural embeddings work significantly better than SVD, and SVD is significantly harder to scale to large corpora. Even if you use SPPMI or other tricks. [1] https://papers.nips.cc/paper/5477-neural-word-embedding-as-implicit-matrix-factorization https://papers.nips.cc/paper/5477-neural-word-embedding-as-i... [2] https://www.transacl.org/ojs/index.php/tacl/article/view/570 https://www.transacl.org/ojs/index.php/tacl/article/view/570
fnl 9y ago
In fact, if the author had actually read Mikolov's w2v NIPS paper (nb, not the arXiv blog posts!) he would have found interesting, insightfull, and, particularly, sound arguments when neutral embeddings work better than count-based PMI - and, when not! As with everything in the world, it's not black-and-white...

by fnl 9y ago

SVD scales with the number of items cubed, w2v scales linearly. Typical real world vocabularies are 1-10M, not 10-100k. This article is FUD and best, and IMO, just plain BS.

ctchocula 9y ago

My understanding was that you can get some savings from keeping the sparse matrix and running sparse SVD via scipy.sparse.linalg.svds(PMI, k=256). I am not certain about the exact time complexity however.

fnl 9y ago
Some minor space savings, maybe. But SVD runtime still scales with the cube of your vocabulary size. Good luck with SVD on a vocabulary from Wikipedia or Common Crawl. If anything, using traditional count-based approaches is good when you only can use a small corpus with tiny vocabularies (<100k) to develop your word embeddings. But that's not what this article is proclaiming. Oh, and yeah, do use fasttext, not the good old word2vec.
- ctchocula 9y ago
  I don't think you are correct here. The advantage of using sparse storage and sparse matrix multiplication is that you can get savings in both storage and runtime. There would be no point in using sparse storage if runtime still scaled with the cube of vocab size. It would be that way if the best way of getting sparse SVD is by materializing a dense matrix product, but people have discovered smarter ways using sparse matvec. The time complexity for obtaining k eigenvalues seems to be O(dkn) where d is the average number of nonzeroes per row, and n is the vocab size [1]. Therefore, one can assert that sparse SVD too is linear in vocab size just like word2vec. This is corroborated by the link elsewhere in this thread that shows SVD enjoying lower wall clock time on the 1.9B word Wikipedia dataset [2]. [1] https://en.wikipedia.org/wiki/Lanczos_algorithm#Application_to_the_eigenproblem https://en.wikipedia.org/wiki/Lanczos_algorithm#Application_... [2] https://rare-technologies.com/making-sense-of-word2vec/ https://rare-technologies.com/making-sense-of-word2vec/
  - fnl 9y ago
    As to [1]: Yes, I was not honest in the sense that non-standard SVD implementations for generating your PMIs will scale with the square of |V|, not the cube. But as I will go on to show, that is not good enough to make count-based approaches competitive to predictive ones. Re. [2], these measurements by Radim have several issues; First, word2vec is a poor implementation, CPU-usage wise, as can be seen by profiling word2vec (fastText is much better at using your CPUs). Second, even Radim states there that his SVD-based results are significantly poorer than the w2v embeddings ("the quality of both SPPMI and SPPMI-SVD models is atrocious"). Third, Radim's conclusion there is: "TL;DR: the word2vec implementation is still fine and state-of-the-art, you can continue using it :-)". So I don't really get your points. Instead of referencing websites and blogs, lets take a deeper look at a "proponent" for count-based methods, in a peer-reviewed setting. In Goldberg et al.'s SPPMI model [1,2] they use truncated SVD. (FYI, that proposed model, SPPMI, is what got used in Radim's blog above.) So even if you wanted use SPPMI instead of the sub-optimal SVD (alone), you would first have to find a really good implementation of that, i.e., something that is competitive to fastTest. Also note that Goldberg only used 2 word-windows for SGNS in most comparisons, which makes the results for neural embeddings a bit dubious. You would typically use 5-10, and as shown in Table 5 of [2], SGNS is pretty much the winner on all cases as it "approaches" 10-word window. Next, I would only trust Hill's SimLex as proper evaluation targets for word similarity - simply look at the raw data of the various evaluation datasets yourself and read Hill's explanations why he created SimLex, and I am sure you will agree. "Coincidentally", it also is - by a huge margin - the most difficult dataset to get right (i.e., all approaches perform worst on SimLex). However, SGNS nearly always outperforms SVD/SSPMI on precisely that set. Finally, even Omar et al. had to conclude: "Applying the traditional count-based methods to this setting [=large-scale corpora] proved technically challenging, as they consumed too much memory to be efficiently manipulated." So even if they "wanted" to conclude that SVD is just as good as neural embeddings, their own results (Table 5) and this statment lead us to a clearly different conclusion: If you use enough window size, you are better off with neural embeddings, particularly for large corpora. And this work only compares W2V & GloVe to SVD & SPPMI, while fastText in turn works a lot better than "vanilla" SGNS and GloVe. What I do agree with is that properly tuning neural embeddings is a bit of a black art, much like anything with the "neural" tag on it... QED; This article is horseradish. Neural embeddings work significantly better than SVD, and SVD is significantly harder to scale to large corpora. Even if you use SPPMI or other tricks. [1] https://papers.nips.cc/paper/5477-neural-word-embedding-as-implicit-matrix-factorization https://papers.nips.cc/paper/5477-neural-word-embedding-as-i... [2] https://www.transacl.org/ojs/index.php/tacl/article/view/570 https://www.transacl.org/ojs/index.php/tacl/article/view/570

fnl 9y ago

In fact, if the author had actually read Mikolov's w2v NIPS paper (nb, not the arXiv blog posts!) he would have found interesting, insightfull, and, particularly, sound arguments when neutral embeddings work better than count-based PMI - and, when not! As with everything in the world, it's not black-and-white...