News for hackers. Stuff that matters.
Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Tuesday March 20, 2018 @03:50AM (#16626654)
Only tangentially related, but we've recently tried to find an encoding of text that's "stable" with regards to it's characters (as opposed to stable wrt semantic meaning as here). That is, similar words (or fragments) such as "carg" and "cargo" should yield a simliar encoding.

To our surprise, we couldn't find any example or description of someone doing this before. Is this such an uncommon problem or did we just not search in the right places?

FWIW, our use case is a search tool with live result listing, so we're dealing with word fragments and would like the outcome to be somewhat stable as the user types along. We ended up rolling our own, but it has certain shortcomings, such as a hard character limit.

Re:Show HN: Word2Bits – Quantized Word Vectors by wodenokoto on Tuesday March 20, 2018 @04:07AM (#16626728)
> To our surprise, we couldn't find any example or description of someone doing this before. Is this such an uncommon problem or did we just not search in the right places?

This is one of the defining differences between Word2Vec and Fasttext. But fasttext incorporates these character vectors as part of calculating the semantic vector, so you can't expect carg and cargo to end up being similar, but people have thought of it.

I don't think partial search is that uncommon, but I don't think it is usually solved by using vector representations similarly to word vectors. It seems like what you are looking for is usually accomplished by edit-distance / Levenshtein distance [1]

[1] https://en.wikipedia.org/wiki/Levenshtein_distance

Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Tuesday March 20, 2018 @05:04AM (#16626948)
Yeah, Levenstein distance is pretty close to our goal metric of "similarity". The thing is that we're feeding the search query into a neural network, hence we need some kind of vector represenation.
Re:Show HN: Word2Bits – Quantized Word Vectors by igravious on Tuesday March 20, 2018 @05:43AM (#16627087)
Need?

Or don't feed the search query directly into a neural network?

Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Tuesday March 20, 2018 @08:36AM (#16627954)
I don't understand; what do you mean?
Re:Show HN: Word2Bits – Quantized Word Vectors by rjurney on Tuesday March 20, 2018 @11:30AM (#16629396)
Do what a search engine does: detect a more common form via edit distance and substitute that word.
Re:Show HN: Word2Bits – Quantized Word Vectors by opportune on Tuesday March 20, 2018 @04:25AM (#16626780)
You might be interested in phonetic algorithms for similarly sounding words:

https://en.wikipedia.org/wiki/New_York_State_Identification_...

https://en.wikipedia.org/wiki/Soundex

Your specific example would be relevant to word-stemming and lemmatization. Stemming is the process of removing suffixes from words for standardization (e.g. swim, swims, swimming, swimmer could all be stemmed to just "swim") across inflections/conjugations. Lemmatization is similar but uses contexts. Actually, some stemmers wouldn't stem cargo to carg by default, but they definitely could be modified to exhibit that kind of behavior, or used as one step in a multistep standardization process

https://en.wikipedia.org/wiki/Stemming

https://en.wikipedia.org/wiki/Lemmatisation

Levenshtein distance is a good metric for individual comparisons but if you're doing a lot of pairwise comparisons/want to index it's not a great option sometimes.

https://en.wikipedia.org/wiki/Levenshtein_distance

You definitely want to also look into tries/prefix trees. These take each character in the word and use it for an O(1) index for the next level of the tree. For example, "brea" queries the top node "b", pointing the next node "r", then "e", then "a". If you next read "d", the trie would indicate that this represents a completed word-fragment at the b->r->e->a->d node of the trie. If you combine this data structure with a statistical model, you can use it for things like spell-checking and autocompletion

https://en.wikipedia.org/wiki/Trie

(I've edited this comment twice now to make it more clear, hopefully this is sufficient). Let me know if you'd like me to point you to any other resources. I've worked with NLP a decent amount and could even work with you guys, if interested my email is in my profile and we can arrange further conversations

Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Tuesday March 20, 2018 @05:08AM (#16626963)
Stemming is similar, but probably wouldn't help solving our problem because we're potentially dealing with word fragments shorter than a stem. Also, we're feeding the search query into a neural network, so we need to create a vector representation of it.
Re:Show HN: Word2Bits – Quantized Word Vectors by opportune on Tuesday March 20, 2018 @05:13AM (#16626985)
You could modify word2vec to embed word fragments as part of the training process. You could also use stemming before training, or if you have a decent amount of computational resources you could embed trie entries with word2vec representations of word fragments and probabilistic models of the likely next character/syllable/word, which would allow you to use something like a markov process

For word completion, I would create a trie and encode naive char-to-char and absolute (word prefix vs. all recorded) frequencies for each edge during its creation, noting that the "end word" value is also possible and deserves a frequency. Then when a user is entering a single word without prior context, you simulate a markov process from the last character to the end of the word. If the user has input a short but unlikely combination you can observe the frequencies of untraversed edges from the nodes of the current path and start a markov process from there if it is much more likely. That gets you to the end of your current word in terms of its string representation. From there you can use n-grams if desired, or go straight into sanitization preceding vectorizaton, to construct a likely query

If I were you I would decouple processes in your pipeline. I mentioned the best way I know of combining word vectors and word fragments (embedding word fragments of a corpus into word2vec, then indexing them with a trie) and I don't think it would be feasible for size reasons - although perhaps the topic of this thread could make it more computationally amenable. It sounds like what you want to do is 1 first infer a word/phrase, 2 stem/sanitize it, 3 map it to its word2vec representation, then 4 do some search query using the vector. 2 and 3 could be combined if desired (would decrease corpus vocab substantially and be good space-wise, improve embeddings of stems of rare words by reducing overfitting, but lose some semantic complexity), perhaps even aggressively, but not with 1 unless you further modify the training process / augment the corpus with fragments.

TL;DR: There's not a good way I know of to use a word2vec mapping trained on a vanilla corpus to directly account for short spelling errors since individual spelling error fragments will be rare or not present within the vanilla data. You seem to think Levenshtein will help but keep in mind this is an expensive pairwise string comparison algorithm. Unless you implement a good way to check which strings to compare the input fragment to, you will likely perform too many comparisons because you won't know where to start

Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Tuesday March 20, 2018 @08:43AM (#16628002)
Our problem is not about auto-completion (we're not dealing with that much data to need sophisticated algorithms for that). What we're doing with our NN is ordering the set of results (matches) we already have. In other words, we're assigning a relevance number in [0, 1] to each result, based on the query string and training based on past user choices (clicking a result). In order to maintain some consistency and robustness, we need our NN to yield similar results for similar word fragments.

So if the NN has previously learned meaningful result priorities for "cargo", they should ideally also work out for "carg" (and vice versa) because of the live listing nature of our tool.

Re:Show HN: Word2Bits – Quantized Word Vectors by opportune on Tuesday March 20, 2018 @09:56AM (#16628556)
Ah ok I think I get it. So herein lies the problem (let me know if any of this is incorrect): you want to encode fragments of a word similarly to completed versions of the word, without doing inference. The easiest way of augmenting your training data into a word2vec embedding with artificially misspelled inputs doesn't seem like it would work considering how many misspellings there are per word.

I think the best way to do this is to create a second neural network which smooths out fragments into word2vec vectors corresponding to the derived word (or the derived word itself). In both approaches you start by making a dataset where each word in the vocabulary is the output for multiple incorrectly spelled, artificially generated inputs. For example you want to have the inputs "crg", "carg", "argo", "crgo", "cago", "cargo", "cargop" "cartgo" all have outputs to "cargo" in this data, whether it's the string "cargo" itself or the w2vec embedding of it. The approach where w2vec embeddings are the output allows for words like "carg" to be interpreted as something like a median between "car" and "cargo" both as input to your main NN and for training purposes, which might be want you want. There's some info on this here [0] but they use it to regenerate words themselves, which you probably don't want. Note that including the identity/low training error is very important unless you do a preliminary vocabulary check.

The second approach of generating correct spellings instead of approximate vectors fails if it doesn't get a close enough approximation, although it seems if levenstein distance <=2, the approximation can be corrected cheaply [1]. Sorry I couldn't be more of help, I haven't really encountered this type of problem before. Good luck, you have an interesting problem to solve!

[0] https://machinelearnings.co/deep-spelling-9ffef96a24f6 [1] http://norvig.com/spell-correct.html

Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Wednesday March 21, 2018 @08:44AM (#16637525)
Ah, so your first suggestion would be basically building an auto-encoder based on training data with correct and incorrect words (fragments). This might work, but it would require a lot of computation: Each word of the vocabulary multiplied by all its similar counterparts. And this wouldn't cover new/unknown terms yet.

What we ended up doing for now is a two-dimensional input layer with per-column one-hot encoding of characters (i.e. one character is one column, 128 rows for the ascii alphabet). Then, apply a convolution with kernel dimensions 3x128, which flattens data to one dimesion and combines three neighboring characters. The second part builds an "assiciation" between neighbors, which helps yielding similar outputs for similar word fragments.

This works quite well, except for some nasty limitations:

- Search queries have a hard limit in length, caused by our input layer dimensions

- Due to varying search query length, input nodes on the right side are often unused/zero, leading an weighting bias on the left side when training. That is, the start of search queries receives more attention that the end. But that's not necessarily a bad thing.

Re:Show HN: Word2Bits – Quantized Word Vectors by loxias on Tuesday March 20, 2018 @12:11PM (#16629845)
creichenbach: I believe I have an algorithm with working code, for you, but don't want to spam this thread. send me an email if you want to. (on my profile).

[Also. I hate having to spam discussion threads with personal user-to-user comments.. but there's no message user feature. This message will self destruct once it's goal has been achieved.]

Re:Show HN: Word2Bits – Quantized Word Vectors by sushirain on Tuesday March 20, 2018 @04:51PM (#16632515)
You can use a character RNN that reads the fragmented input char by char, and feed its output to your NN.
Re:Show HN: Word2Bits – Quantized Word Vectors by patelajay285 on Tuesday March 20, 2018 @11:35AM (#16629461)
We recently open sourced a library that does exactly this:

https://github.com/plasticityai/magnitude

For word2vec, GloVE, and fastText. It is able to generate vectors for out-of-vocabulary words through "fragments" of words or subword character n-grams rather.

Re:Show HN: Word2Bits – Quantized Word Vectors by isoprophlex on Tuesday March 20, 2018 @03:58AM (#16626693)
You can try encoding your input in shingles maybe, and feeding vectorized shingles (instead of a one hot encoded dictionary) into the usual CBOW or skipgram thing to train the embedding.

You'd need to invest plenty of effort into shingling and vectorizing properly to get useful results, though.

Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Tuesday March 20, 2018 @05:00AM (#16626930)
Ah, so we'd divide our word (fragment) into parts and treat the parts like words for usage with CBOW or skipgram?
Re:Show HN: Word2Bits – Quantized Word Vectors by isoprophlex on Tuesday March 20, 2018 @11:23AM (#16629333)
Uh yeah I have no idea if it'd perform well, but instead of having a sparse vector with the one-hot encoding of 'cargo', you enter a sparse vector with the 'car', 'arg' and 'rgo' dimensions set high.

Top of my head speculation, I never tried this...

Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Wednesday March 21, 2018 @08:54AM (#16637577)
Ah, that's actually not too far idea-wise from what we ended up doing: https://news.ycombinator.com/item?id=16637525
Re:Show HN: Word2Bits – Quantized Word Vectors by nl on Tuesday March 20, 2018 @06:05AM (#16627187)
FastText can generate word vectors for partial and/or unknown words based on similar chargram patterns.
Re:Show HN: Word2Bits – Quantized Word Vectors by creichenbach on Tuesday March 20, 2018 @08:49AM (#16628049)
That sounds interesting, do you happen to have a documentation link or similar? I can't seem to find any info about it.
Re:Show HN: Word2Bits – Quantized Word Vectors by nl on Tuesday March 20, 2018 @03:42PM (#16631856)
There are some somewhat reasonable docs at the bottom of https://fasttext.cc/docs/en/unsupervised-tutorial.html

I really should do a blog post about it or something.

Re:Show HN: Word2Bits – Quantized Word Vectors by physicsyogi on Tuesday March 20, 2018 @10:00AM (#16628582)
Enriching Word Vectors with Subword Information: https://arxiv.org/abs/1607.04606