4 ms·

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 feedi

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.

opportune 9y ago
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
- creichenbach 9y ago
  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.
  - opportune 9y ago
    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 https://machinelearnings.co/deep-spelling-9ffef96a24f6 [1] http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html

opportune 9y ago

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

creichenbach 9y ago
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.
- opportune 9y ago
  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 https://machinelearnings.co/deep-spelling-9ffef96a24f6 [1] http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html