4 ms·

> Build your own by computing the pairwise distance matrix of your entries, then reducing this matrix through PCA to an appropriate number of components (the le

by srean 12y ago

> Build your own by computing the pairwise distance matrix of your entries, then reducing this matrix through PCA to an appropriate number of components (the length of your hash). You are kidding right ? I cant imagine anyone seriously suggesting PCA on a half a million by half a million matrix, or evaluating this matrix in the first place. This actually a fairly actively researched topic: whether edit distance can be embedded, even if approximately in a vector space. It has been surprisingly resistant to such efforts. Yes there are some results but nothing very satisfactory. Edit distance is a metric, so it was believed it would easy to map individual strings to vectors, such that the distance between two vectors was same as, or close to the edit distance between the corresponding strings. What we want, then, is an (approximate) isomorphism between these two metric spaces. In addition, in the interest of size we would like these vectors to be of small dimension. If the required dimension is high it would defeat the purpose if the string to vector map needs to be stored. Unfortunately it seems edit distance is resistant to isomorphism to a low-dimensional vector space. There is also this question which metric do we use in the vector space, Euclidean, Manhattan...? there are some results on the L1, i.e. embedding on a vector space with Manhattan distances. Fun story: was an intern in Google's spelling correction team once upon a time long ago. So I was explaining what I was doing, the person I was explaining it to was thoroughly unimpressed: "So whats the big deal, you know/hear the word and write down the spelling". It made me realize how difficult spelling in English is compared to some of the other languages. The variability in the map from phonemes to spelling is quite high in English. This person was Italian, he told me Italian has a lot less variability in this regard.

danieltillett 12y ago
Pity nobody here seem to be interested in doing anything about English spelling. Propose a practicable solution [1] and it is ignored :( [1] https://news.ycombinator.com/item?id=8158579 https://news.ycombinator.com/item?id=8158579
- beagle3 12y ago
  The scope of this project is beyond huge. And similar things are being proposed for the last 250 years (some in jest, some seriously [1]). But the benefits do not seem sufficient given the costs. [1] http://grammar.ccc.commnet.edu/grammar/twain.htm http://grammar.ccc.commnet.edu/grammar/twain.htm
  - danieltillett 12y ago
    Of course it is huge, but as something I have thought about for a long time it actually has a chance of working. Not that I can convince anyone here, but it is worth taking the time to consider in depth.
StefanKarpinski 12y ago
PCA is basically just SVD and computing an SVD of that size is not unreasonable, even of it's dense: 0.5e6^2 = 0.25e12 = 1TB of 32-bit floats. That's a lot of memory but there are reasonably priced machines ($50k or so) with that much RAM these days. If it's sparse, this can be done on a laptop, and it might not even be necessarily to materialize the matrix at all if you use Lancosz iteration.
- srean 12y ago
  Lets put it this way then, we disagree on what's a reasonable expenditure. 1TB Ram ? $50k ? Could you fund me please :) ok adding pretty please. Note its not just memory, its computation also. Every entry of that matrix is a solution to a dynamic program, if you dont store it you have to recompute it. The DP scales as product of the lengths of the string, those things have a fat tail. You could still get away with it if this matrix was close to a low rank matrix and with large gaps between adjacent singular values. Its not and thats a problem. Note you have to store the SVD factors too. EDIT: Interesting ! my comments seems to have annoyed someone. Did not expect downvotes on my comments here, thought they were pretty uncontroversial. If you dear reader can leave some clues it would be helpful and appreciated. I upvote those who explain what they found unpalatable about my comments, regardless of agreement.
  - StefanKarpinski 12y ago
    It's a lot of computation, granted, but I just wanted to point out that it wasn't completely ludicrous. The proposed algorithm doesn't work anyway since there are no non-degenerate hash functions that map all words within D edits of each other to the same hash value (as I pointed out here: https://news.ycombinator.com/item?id=8158942 https://news.ycombinator.com/item?id=8158942).
fchollet 12y ago
I'm definitely not kidding. I'll point out that this is very much tractable (for instance Spotify runs a matrix factorization job every few days on a users x songs matrix, maybe 50 million by 30 million, which is several orders of magnitude more). But anyway if you want to do that on your laptop, you don't have to use the entire space to build a good function, just a statistically representative sample of your dictionary will suffice.
- beagle3 12y ago
  Sparse matrix SVD (or, more likely, truncated/approximate SVD) like Spotify and Netflix contestants used to do is easy. But anything dense is not quite as easy (StefanKarpinski gave a $50K estimate for a machine with enough memory to do that -- I don't consider that "easy") Also, do you actually have any kind of experience with PCAing/SVDing an edit distance matrix? It's not easy to embed in a eucleadean geometry. If you have that experience, can you point to more reference material? If you don't, it would be prudent to say "I believe this might work though I have never tried anything similar".

by srean 12y ago

danieltillett 12y ago

Pity nobody here seem to be interested in doing anything about English spelling. Propose a practicable solution [1] and it is ignored :( [1] https://news.ycombinator.com/item?id=8158579 https://news.ycombinator.com/item?id=8158579

beagle3 12y ago
The scope of this project is beyond huge. And similar things are being proposed for the last 250 years (some in jest, some seriously [1]). But the benefits do not seem sufficient given the costs. [1] http://grammar.ccc.commnet.edu/grammar/twain.htm http://grammar.ccc.commnet.edu/grammar/twain.htm
- danieltillett 12y ago
  Of course it is huge, but as something I have thought about for a long time it actually has a chance of working. Not that I can convince anyone here, but it is worth taking the time to consider in depth.

StefanKarpinski 12y ago

PCA is basically just SVD and computing an SVD of that size is not unreasonable, even of it's dense: 0.5e6^2 = 0.25e12 = 1TB of 32-bit floats. That's a lot of memory but there are reasonably priced machines ($50k or so) with that much RAM these days. If it's sparse, this can be done on a laptop, and it might not even be necessarily to materialize the matrix at all if you use Lancosz iteration.

srean 12y ago
Lets put it this way then, we disagree on what's a reasonable expenditure. 1TB Ram ? $50k ? Could you fund me please :) ok adding pretty please. Note its not just memory, its computation also. Every entry of that matrix is a solution to a dynamic program, if you dont store it you have to recompute it. The DP scales as product of the lengths of the string, those things have a fat tail. You could still get away with it if this matrix was close to a low rank matrix and with large gaps between adjacent singular values. Its not and thats a problem. Note you have to store the SVD factors too. EDIT: Interesting ! my comments seems to have annoyed someone. Did not expect downvotes on my comments here, thought they were pretty uncontroversial. If you dear reader can leave some clues it would be helpful and appreciated. I upvote those who explain what they found unpalatable about my comments, regardless of agreement.
- StefanKarpinski 12y ago
  It's a lot of computation, granted, but I just wanted to point out that it wasn't completely ludicrous. The proposed algorithm doesn't work anyway since there are no non-degenerate hash functions that map all words within D edits of each other to the same hash value (as I pointed out here: https://news.ycombinator.com/item?id=8158942 https://news.ycombinator.com/item?id=8158942).

fchollet 12y ago

I'm definitely not kidding. I'll point out that this is very much tractable (for instance Spotify runs a matrix factorization job every few days on a users x songs matrix, maybe 50 million by 30 million, which is several orders of magnitude more). But anyway if you want to do that on your laptop, you don't have to use the entire space to build a good function, just a statistically representative sample of your dictionary will suffice.

beagle3 12y ago
Sparse matrix SVD (or, more likely, truncated/approximate SVD) like Spotify and Netflix contestants used to do is easy. But anything dense is not quite as easy (StefanKarpinski gave a $50K estimate for a machine with enough memory to do that -- I don't consider that "easy") Also, do you actually have any kind of experience with PCAing/SVDing an edit distance matrix? It's not easy to embed in a eucleadean geometry. If you have that experience, can you point to more reference material? If you don't, it would be prudent to say "I believe this might work though I have never tried anything similar".