7 ms·

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 semant

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.

isoprophlex 9y ago
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.
- creichenbach 9y ago
  Ah, so we'd divide our word (fragment) into parts and treat the parts like words for usage with CBOW or skipgram?
  - isoprophlex 9y ago
    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...
    - creichenbach 9y ago
      Ah, that's actually not too far idea-wise from what we ended up doing: https://news.ycombinator.com/item?id=16637525 https://news.ycombinator.com/item?id=16637525
wodenokoto 9y ago
> 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 https://en.wikipedia.org/wiki/Levenshtein_distance
- creichenbach 9y ago
  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.
  - igravious 9y ago
    Need? Or don't feed the search query directly into a neural network?
    - creichenbach 9y ago
      I don't understand; what do you mean?
      - rjurney 9y ago
        Do what a search engine does: detect a more common form via edit distance and substitute that word.
  - deleted 9y ago
    [deleted]
opportune 9y ago
You might be interested in phonetic algorithms for similarly sounding words: https://en.wikipedia.org/wiki/New_York_State_Identification_and_Intelligence_System https://en.wikipedia.org/wiki/New_York_State_Identification_... https://en.wikipedia.org/wiki/Soundex 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/Stemming https://en.wikipedia.org/wiki/Lemmatisation 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 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 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
- creichenbach 9y ago
  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
nl 9y ago
FastText can generate word vectors for partial and/or unknown words based on similar chargram patterns.
- creichenbach 9y ago
  That sounds interesting, do you happen to have a documentation link or similar? I can't seem to find any info about it.
  - physicsyogi 9y ago
    Enriching Word Vectors with Subword Information: https://arxiv.org/abs/1607.04606 https://arxiv.org/abs/1607.04606
  - nl 9y ago
    There are some somewhat reasonable docs at the bottom of https://fasttext.cc/docs/en/unsupervised-tutorial.html https://fasttext.cc/docs/en/unsupervised-tutorial.html I really should do a blog post about it or something.
patelajay285 9y ago
We recently open sourced a library that does exactly this: https://github.com/plasticityai/magnitude 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.

isoprophlex 9y ago

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.

creichenbach 9y ago
Ah, so we'd divide our word (fragment) into parts and treat the parts like words for usage with CBOW or skipgram?
- isoprophlex 9y ago
  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...
  - creichenbach 9y ago
    Ah, that's actually not too far idea-wise from what we ended up doing: https://news.ycombinator.com/item?id=16637525 https://news.ycombinator.com/item?id=16637525

wodenokoto 9y ago

> 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 https://en.wikipedia.org/wiki/Levenshtein_distance

creichenbach 9y ago
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.
- igravious 9y ago
  Need? Or don't feed the search query directly into a neural network?
  - creichenbach 9y ago
    I don't understand; what do you mean?
    - rjurney 9y ago
      Do what a search engine does: detect a more common form via edit distance and substitute that word.
- deleted 9y ago
  [deleted]

opportune 9y ago

You might be interested in phonetic algorithms for similarly sounding words: https://en.wikipedia.org/wiki/New_York_State_Identification_and_Intelligence_System https://en.wikipedia.org/wiki/New_York_State_Identification_... https://en.wikipedia.org/wiki/Soundex 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/Stemming https://en.wikipedia.org/wiki/Lemmatisation 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 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 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

creichenbach 9y ago
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

nl 9y ago

FastText can generate word vectors for partial and/or unknown words based on similar chargram patterns.

creichenbach 9y ago
That sounds interesting, do you happen to have a documentation link or similar? I can't seem to find any info about it.
- physicsyogi 9y ago
  Enriching Word Vectors with Subword Information: https://arxiv.org/abs/1607.04606 https://arxiv.org/abs/1607.04606
- nl 9y ago
  There are some somewhat reasonable docs at the bottom of https://fasttext.cc/docs/en/unsupervised-tutorial.html https://fasttext.cc/docs/en/unsupervised-tutorial.html I really should do a blog post about it or something.

patelajay285 9y ago

We recently open sourced a library that does exactly this: https://github.com/plasticityai/magnitude 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.