11 ms·

Show HN: Word2Bits – Quantized Word Vectors

221 points by maxlam 9y ago

andreyk 9y ago
Very cool! I like the visualizations a lot. Did you try to get an interpretation for what each quantized vector dimension means (have just skimmed, not read)? Also, I am curious why you chose to go straight to publishing on Arxiv? I am actually also in CS224N right now and have a project me and my collaborator feel is publication worthy, but our plan is to go the normal route of submitting to a conference and only putting it on Arxiv after the review process (though our code is open source, so now that I think about it maybe that's not that useful a plan...).
- maxlam 9y ago
  Definitely tried to figure out if the dimensions mean anything -- as far as I can tell they don't really mean much :(
  - Maybestring 9y ago
    If you want them to be meaningful without changing the model... Couldn't you rotate the basis to minimize the distance between each basis vector and it's nearest neighbor?
    - maxlam 9y ago
      Haven't tried this but this is definitely a good idea for visualizing what's going on!
  - loxias 9y ago
    One of the fascinating things about neural embedding such as these is that the individual component dimensions have NO "real" semantic meaning to us humans. It's better to think of them as single points in a higher dimensional space. (of course, with a clever network design you could probably FORCE "meaning" onto some components)
wodenokoto 9y ago
Can someone explain how to read the graph?
- iampims 9y ago
  From the paper > Figure 2 shows a visualisation of 800 dimensional 1 bit word vectors trained on English Wikipedia (2017). The top 100 closest and furthest word vectors to the target word vector are plotted. Distance is measured by dot product; every 5 word vectors are labelled. A turquoise line separates the 100 closest vectors to the target word from the 100 furthest vectors (labelled “...”). We see that there are qualitative similarities between word vectors whose words are related to each other.
- maxlam 9y ago
  Yeah, I should definitely put more detail in the writeup -- thanks for the feedback! What's happening with figure 1a (epochs vs google accuracy) is that as you train for more epochs the full precision loss continues to decrease (dotted red line) but accuracy also starts decreasing (solid red line). This indicates overfitting (since you'd expect accuracy to increase if loss decreases). The blue lines (quantized training with 1 bit) do not show this which suggests that quantized training seems to act as a form of regularization. Figure 1b is pretty similar, except on the x axis we have vector dimension. As you increase vector dimension, full precision loss decreases, yet after a certain point full precision accuracy decreases as well. I took this to mean that word2vec training was overfitting with respect to vector dimension.
  - maxlam 9y ago
    Oops, thought you meant the graphs (with the dotted/solid lines) in the writeup. If you're referring to the image under "Visualizing Quantized Word Vectors" then each row is a word vector (and there are only two colors since each parameter is either -1/3 or +1/3).
    - wodenokoto 9y ago
      Thanks for the reply. Yes, I did mean the image under "Visualizing Quantized Word Vectors". I did get that the colors indicated values of dimensions, but I suppose what I really meant is, what is the take-away message? To me, it just looks like noise. Is there a pattern I should look for and go "a-ha, I see"?
Dawny33 9y ago
The data engineer in me thanks you. Great work. The paper would be a great weekend read.
newman8r 9y ago
interesting that 'artists' is a furthest neighbor of 'man' in the example
- maxlam 9y ago
  This might be because "Artist" has an uppercase "A" -- I trained all the word vectors to be case sensitive so "Artist" is not the same as "artist" (which should be closer to "man" than "Artist")
  - NKCSS 9y ago
    Why would you do that? If you look at something like LSA, they goal is to uniform those, rather than distinguish. artist and Artist should be (near)100% match; what are you trying to do here?
    - maxlam 9y ago
      Main reason I did it this way is because Facebook's DrQA (which I evaluate the vectors on for the SQuAD task) uses case sensitive vectors. Was a tough decision between choosing whether to train case sensitive vectors / case insensitive vectors and a future task would be to train case-insensitive vectors.
  - newman8r 9y ago
    Makes sense. The plural vs singular probably impacts that one too.
rococode 9y ago
Very cool that this beats Word2Vec on SQuAD! I wonder if the current state of the art models are using the standard GloVe word vecs and might see improvement from this. Tbh I don't know too much about how those have been implemented though, haha. I'm curious, how many values did you try for the quantization functions? Without thinking too much about it, that seems like one of the hyperparams that could have a pretty big impact on performance.
- maxlam 9y ago
  You're definitely right, the quantization function and its values definitely have an impact on performance. For 1 bit I think I tried something like -1/+1, -.5/+.5, -.25/+.25, -.333/+.333. and something like -10/+10 -- (and I think a few more). It seemed -.333/+.333 worked the best while +10/-10 did the worst on the google analogy task (getting like 0% right). All this was tuned on 100MB of Wikipedia data.
  - yorwba 9y ago
    Have you considered doing gradient descent on the quantization steps? It looks to me like the model should be differentiable with respect to those values, so I'm not sure why you'd have to fix them to a constant.
    - maxlam 9y ago
      Hm what do you mean? I'm not quite seeing how to differentiate with respect to the quantization steps.
      - yorwba 9y ago
        Say you have a function f(q(x)) where q quantizes x into one of s_1, ..., s_n. Then if q(x) = s_i for a certain x, df/ds_i = df/dq and df/ds_j = 0 for all j != i. That breaks down for values of x precisely at the boundary between steps, so I should have qualified "differentiable" with "almost everywhere". It also occurs to me that this might interact strangely with the approximation dq/dx = 1, but since the quantization steps are globally shared, I think it should be stable anyway. If the evaluation suite for your code doesn't require too much manual interaction, I might try and see for myself.
Sukotto 9y ago
I thought I knew what a vector was, but I have no idea what any of this project means. Would someone please explain in simple language what this is, and why it's cool?
- maxlam 9y ago
  The idea is that you can kind of capture the "meaning" of a word with a sequence of numbers (a vector) -- and then you use these vectors for machine learning tasks to do cool stuff like answer questions! Word2Vec is one of the algorithms to do this. Given a bunch of text (like Wikipedia) it turns words into vectors. These vectors have interesting properties like: vector("man") - vector("woman") + vector("queen") = vector("king") and distance(vector("man"), vector("woman)) < distance(vector("man"), vector("cat")) What Word2Bits does is make sure that the numbers that represent a word is limited to just 2 values (-.333 and +.333). This reduces the amount of storage the vectors take and surprisingly improves accuracy in some scenarios. If you're interested in learning more, check out http://colah.github.io/posts/2014-07-NLP-RNNs-Representations/ http://colah.github.io/posts/2014-07-NLP-RNNs-Representation... which has a lot more details about representations in deep learning!
  - Sukotto 9y ago
    Thank you. That really helped.
- knolan 9y ago
  From the Arxiv paper, multidimensional word vectors are used in natural language processing. However they can be many gigabytes in size making then cumbersome. This approach aims to solve that issue. The wiki page on Word2vec seems helpful. https://en.m.wikipedia.org/wiki/Word2vec https://en.m.wikipedia.org/wiki/Word2vec
- opportune 9y ago
  Quick run down on word2vec and what happened here: A big problem with NLP is understanding the semantic associations between words (or even lemmas. Lemmas in this context refer to different meanings of the same word, like a baseball bat vs. a vampire bat). For example "run" and "sprint" are similar in meaning but convey different connotations; kings and queens are both high-level monarchs but we need to encode the difference in gender between them for a true semantic understanding. The problem is that the information in words themselves don't accurately convey all of this information through their string (or spoken) representations. Even dictionary definitions lack explanations of connotations or subtle differences in context, and furthermore aren't easily explained to a computer Word2vec is an algorithm that maps words to vectors, which can be compared to one another to analyze semantic meaning. These are typically high-dimensional (e.g. several hundred dimensions). When words are used often together, or in similar contexts, they are embedded within the vector space closer to each other. The idea is that words like "computer" and "digital" are placed closer together than "inference" and "paddling". Usually these vector mappings are represented as something like a python dictionary with each key in the dictionary corresponding to some token or word appearing at least one (maybe more) times in some set of training data. As you can imagine these can be quite large if the vocabulary of the training data is diverse, and due to being in such a high-dimensional space, the precision of a vector entry may not need to be as high as doubles or floats encode. Floats are 32 bits. The authors of this paper/repo figured out a way to quantize vector entries into representations with smaller numbers of bits, which can be used in storage to make saved word2vec models even smaller. This is really useful because a big problem with running word2vec instances is that they can take up space on the order of gigabytes. I haven't read it all yet but it seems the big innovation might have been figuring out a way to work with these quantized word vectors in-memory without losing much performance Edit: seems it may not work in-memory
creichenbach 9y ago
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
a_bonobo 9y ago
This could be useful with DNA/protein sequences - there's dna2vec and similar approaches to mine sequences for regulatory elements and more, the problem when compared with word2vec is that you have an order of magnitude more words. You don't really have words so you split the continuous DNA sequence into overlapping mers and treat that as words (afaik). That means that dna2vec takes forever (>24h with one chromosome) and builds a huge vector. I wonder whether this will speed up things...
rspeer 9y ago
It's interesting and slightly uncomfortable that the illustration for similar words uses the word "man" as an example, given the gender biases that result from learning word vectors solely from word distributions. To explain, although I’m sure the author himself is familiar with the issue: For any word that is disproportionately associated with one gender in the corpus, the model will learn that gender difference as part of the representation of the word, pretty much baking it into all applications. [1] It's all fun and games when this helps you find the difference between "king" and "queen", but it becomes a problem when the same difference appears between "genius" and "beautiful". I haven't evaluated these vectors for built-in biases, but I assume they would have similar problems to the pre-computed word2vec and GloVe embeddings. (If they don't -- if quantization is a natural way to counteract bias -- then that's an awesome result! But an unlikely one.) To the author: I don’t mean this to sound like an accusation that you haven’t done this yet; I know that short papers can’t tell two stories at the same time. But the next step is pretty clear, right? How do these vectors measure on the Word Embedding Association Test for implicit bias? Does Bolukbasi’s de-biasing method, or an analogue of it, work on quantized embeddings? [1] Bolukbasi et al., "Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings." https://arxiv.org/abs/1607.06520 https://arxiv.org/abs/1607.06520
- maxlam 9y ago
  Interesting, definitely need to think about debiasing. Seems like it won't really work straight out of the box since it'd destroy the 1 bit-ness of the vectors. Though if only a few of the vectors are de-biased then you can still save a lot of space since all the other vectors are still represented using 2 numbers (while the de-biased vectors are represented using the full range of 32 bit numbers).
  - rspeer 9y ago
    There may be a way to build it into the loss function so that it happens before the quantization, right? (and holy crap, look how fast the HN conservatives are getting to my comment)
    - 9y ago
dougb5 9y ago
This is great and echoes a recent fascination for me. One application of compact word embeddings is that if they're small enough you can ship a whole model to the user in a web app so that semantic computations can be done entirely client-side, which is useful for privacy. I did a naive 1-bit quantization a few months ago in order to fit a large-vocabulary word embedding into a smallish (< 3 MB) JSON file so that synonyms could be generated by the user without hitting a server. (See https://docs.google.com/presentation/d/1SfbfnuNSlDRtUOpN1KNc2RMtw030defCDME6p_268fQ/edit#slide=id.g28366446a3_0_110 https://docs.google.com/presentation/d/1SfbfnuNSlDRtUOpN1KNc... for a description and https://prototypes.cortico.ai/search-history/ https://prototypes.cortico.ai/search-history/ for the application -- happy to send you more details/code if you want) I never got as far as formally evaluating the quality of these vectors, though.
- visarga 9y ago
  You can also replace rare words with a linear combination of 1..3 of their closest neighbours, especially for topic classification tasks. This would allow higher precision for more frequent words and still handle the rare words, reducing the number of vectors you need to send to the thin client.
- narrator 9y ago
  Finally a use for 5g bandwidth: sending big ML models to the client.
- rpedela 9y ago
  Can you expand on the privacy use case? I don't understand how applying a word vector model on the client improves privacy.
  - darawk 9y ago
    You presumably do not have to ship the content of the user's query up to the server.
    - rpedela 9y ago
Jack000 9y ago
can this be done with fasttext as well? Word2bits is definitely great for memory-constrained applications but for server use memory isn't as much a constraint (there's a direct word -> vector relationship so you can just put it in a database) it would be amazing to combine this with fasttext's ability to generate vectors for out-of-vocab words.
- manojlds 9y ago
  Yeah you can - https://github.com/facebookresearch/fastText/blob/master/quantization-example.sh https://github.com/facebookresearch/fastText/blob/master/qua...
Radim 9y ago
Optimizations are always great :-) This sounds similar to Maciej Kula's experiments in "Binary Latent Representations for Efficient Ranking: Empirical Assessment", https://arxiv.org/abs/1706.07479 https://arxiv.org/abs/1706.07479. Maciej shared this [1]: "FWIW I ran similar experiments on recommendation tasks. My initial results were very encouraging (and similar to those reported here), but the effect disappeared entirely after adding regularization to the baseline. I would have more confidence in the results reported here if the authors ran a more principled hyperparameter search, and added regularization to their baseline." [1] https://twitter.com/Maciej_Kula/status/976028573487239168 https://twitter.com/Maciej_Kula/status/976028573487239168
mark_l_watson 9y ago
Very nice, thanks for creating this! In addition to (possibly new) hardware that supports much larger memory, compression techniques like this might allow us to start operations with “phrase embedding” or eventually even whole “sentence embedding.”
tmalsburg2 9y ago
Interesting to see that "science" and "fiction" are so similar according to this metric. Not surprising, though, given how often they co-occur in text, but this clearly shows the limitations of the method. The unit of interest is not really character strings but lexical entries and there can be multiple lexical entries associated with one character string. For instance, the word "bank" can mean "financial institution" or "edge of a river" but both meanings would contribute to a common word vector. You could say that this only affects ambiguous words, but first ambiguous words are very common and second these words probably distort the whole vector space (by introducing "short circuits") and therefore also affect the vectors for non-ambiguous words. A long way left to go for these methods I suppose. Edit: Have people tried to detect ambiguous words by measuring local conflict in word2vec space? E.g. "laboratory" is similar to "science" and "science" is similar to "fiction" but there is no evidence to suggest that "laboratory" should be similar to "fiction".
- popinman322 9y ago
  This is a known problem and work is being done on it. I'm not sure whether there's work in the specific direction that you specified in your edit, but I did manage to find this paper from 2012 via a quick search: http://www.aclweb.org/anthology/P12-1092 http://www.aclweb.org/anthology/P12-1092 This paper in particular has ~700 citations right now; I didn't go through them to see the latest work but this likely doesn't represent the cutting edge. I imagine that marginal computational cost would be the deciding factor in choosing a more advanced model here. Granted, these embeddings are often generated infrequently so I don't see the harm in extra one-off training time. It's possible that choosing between definitions adds overhead elsewhere in the system.
- morelandjs 9y ago
  One method to partially rectify the problem you mention is to add additional preprocessing to the text to identify ngrams and add part of speech tags to words. For example [The, river, bank] might be restructed as [The, river bank (bigram)] where "river bank" is embedded as its own word vector. This can also be used to disambiguate words like "hit" which can be used as a verb and a noun. You just replace "hit" with "hit|noun" and "hit|verb".
loxias 9y ago
Interesting. So, this approach computes a "traditional" neural embedding, in say, R^50, and then "brutally" replaces each of the reals with an integer in Z_2,4,8... I can't quite put my finger on it, but my hunch is that this naive method, while already delivering interesting results, can be drastically improved upon. * don't use a fixed bit depth for all vector components I guess it depends on what you're trying to optimize for -- what algebraic properties you wish to preserve for the end application: If the end goal is: "linearity be damned, I want a stupidly fast but inaccurate way of doing approximate nearest neighbor search", then turning words into bitvectors, and using hamming distance, not(xor(a,b)), &c" works. Either way, thanks for the ideas, OP. (was going to go on with some mathematical stuff which I suspect would improve upon it, but decided to either shutup, or put-up-and-credit-you.)
- _mhr_ 9y ago
  I would appreciate if you elaborated on your supposed improvements.
malcook 9y ago
Is there an explanation for why almost all the words most distant from "man" are either uppercase or otherwise lexically anomalous? Is it largely driven by their being low frequency in the corpus?

221 points by maxlam 9y ago

Very cool! I like the visualizations a lot. Did you try to get an interpretation for what each quantized vector dimension means (have just skimmed, not read)? Also, I am curious why you chose to go straight to publishing on Arxiv? I am actually also in CS224N right now and have a project me and my collaborator feel is publication worthy, but our plan is to go the normal route of submitting to a conference and only putting it on Arxiv after the review process (though our code is open source, so now that I think about it maybe that's not that useful a plan...).

maxlam 9y ago
Definitely tried to figure out if the dimensions mean anything -- as far as I can tell they don't really mean much :(
- Maybestring 9y ago
  If you want them to be meaningful without changing the model... Couldn't you rotate the basis to minimize the distance between each basis vector and it's nearest neighbor?
  - maxlam 9y ago
    Haven't tried this but this is definitely a good idea for visualizing what's going on!
- loxias 9y ago
  One of the fascinating things about neural embedding such as these is that the individual component dimensions have NO "real" semantic meaning to us humans. It's better to think of them as single points in a higher dimensional space. (of course, with a clever network design you could probably FORCE "meaning" onto some components)

wodenokoto 9y ago

Can someone explain how to read the graph?

iampims 9y ago
From the paper > Figure 2 shows a visualisation of 800 dimensional 1 bit word vectors trained on English Wikipedia (2017). The top 100 closest and furthest word vectors to the target word vector are plotted. Distance is measured by dot product; every 5 word vectors are labelled. A turquoise line separates the 100 closest vectors to the target word from the 100 furthest vectors (labelled “...”). We see that there are qualitative similarities between word vectors whose words are related to each other.
maxlam 9y ago
Yeah, I should definitely put more detail in the writeup -- thanks for the feedback! What's happening with figure 1a (epochs vs google accuracy) is that as you train for more epochs the full precision loss continues to decrease (dotted red line) but accuracy also starts decreasing (solid red line). This indicates overfitting (since you'd expect accuracy to increase if loss decreases). The blue lines (quantized training with 1 bit) do not show this which suggests that quantized training seems to act as a form of regularization. Figure 1b is pretty similar, except on the x axis we have vector dimension. As you increase vector dimension, full precision loss decreases, yet after a certain point full precision accuracy decreases as well. I took this to mean that word2vec training was overfitting with respect to vector dimension.
- maxlam 9y ago
  Oops, thought you meant the graphs (with the dotted/solid lines) in the writeup. If you're referring to the image under "Visualizing Quantized Word Vectors" then each row is a word vector (and there are only two colors since each parameter is either -1/3 or +1/3).
  - wodenokoto 9y ago
    Thanks for the reply. Yes, I did mean the image under "Visualizing Quantized Word Vectors". I did get that the colors indicated values of dimensions, but I suppose what I really meant is, what is the take-away message? To me, it just looks like noise. Is there a pattern I should look for and go "a-ha, I see"?

Dawny33 9y ago

The data engineer in me thanks you. Great work. The paper would be a great weekend read.

newman8r 9y ago

interesting that 'artists' is a furthest neighbor of 'man' in the example

maxlam 9y ago
This might be because "Artist" has an uppercase "A" -- I trained all the word vectors to be case sensitive so "Artist" is not the same as "artist" (which should be closer to "man" than "Artist")
- NKCSS 9y ago
  Why would you do that? If you look at something like LSA, they goal is to uniform those, rather than distinguish. artist and Artist should be (near)100% match; what are you trying to do here?
  - maxlam 9y ago
    Main reason I did it this way is because Facebook's DrQA (which I evaluate the vectors on for the SQuAD task) uses case sensitive vectors. Was a tough decision between choosing whether to train case sensitive vectors / case insensitive vectors and a future task would be to train case-insensitive vectors.
- newman8r 9y ago
  Makes sense. The plural vs singular probably impacts that one too.

rococode 9y ago

Very cool that this beats Word2Vec on SQuAD! I wonder if the current state of the art models are using the standard GloVe word vecs and might see improvement from this. Tbh I don't know too much about how those have been implemented though, haha. I'm curious, how many values did you try for the quantization functions? Without thinking too much about it, that seems like one of the hyperparams that could have a pretty big impact on performance.

maxlam 9y ago
You're definitely right, the quantization function and its values definitely have an impact on performance. For 1 bit I think I tried something like -1/+1, -.5/+.5, -.25/+.25, -.333/+.333. and something like -10/+10 -- (and I think a few more). It seemed -.333/+.333 worked the best while +10/-10 did the worst on the google analogy task (getting like 0% right). All this was tuned on 100MB of Wikipedia data.
- yorwba 9y ago
  Have you considered doing gradient descent on the quantization steps? It looks to me like the model should be differentiable with respect to those values, so I'm not sure why you'd have to fix them to a constant.
  - maxlam 9y ago
    Hm what do you mean? I'm not quite seeing how to differentiate with respect to the quantization steps.
    - yorwba 9y ago
      Say you have a function f(q(x)) where q quantizes x into one of s_1, ..., s_n. Then if q(x) = s_i for a certain x, df/ds_i = df/dq and df/ds_j = 0 for all j != i. That breaks down for values of x precisely at the boundary between steps, so I should have qualified "differentiable" with "almost everywhere". It also occurs to me that this might interact strangely with the approximation dq/dx = 1, but since the quantization steps are globally shared, I think it should be stable anyway. If the evaluation suite for your code doesn't require too much manual interaction, I might try and see for myself.

Sukotto 9y ago

I thought I knew what a vector was, but I have no idea what any of this project means. Would someone please explain in simple language what this is, and why it's cool?

maxlam 9y ago
The idea is that you can kind of capture the "meaning" of a word with a sequence of numbers (a vector) -- and then you use these vectors for machine learning tasks to do cool stuff like answer questions! Word2Vec is one of the algorithms to do this. Given a bunch of text (like Wikipedia) it turns words into vectors. These vectors have interesting properties like: vector("man") - vector("woman") + vector("queen") = vector("king") and distance(vector("man"), vector("woman)) < distance(vector("man"), vector("cat")) What Word2Bits does is make sure that the numbers that represent a word is limited to just 2 values (-.333 and +.333). This reduces the amount of storage the vectors take and surprisingly improves accuracy in some scenarios. If you're interested in learning more, check out http://colah.github.io/posts/2014-07-NLP-RNNs-Representations/ http://colah.github.io/posts/2014-07-NLP-RNNs-Representation... which has a lot more details about representations in deep learning!
- Sukotto 9y ago
  Thank you. That really helped.
knolan 9y ago
From the Arxiv paper, multidimensional word vectors are used in natural language processing. However they can be many gigabytes in size making then cumbersome. This approach aims to solve that issue. The wiki page on Word2vec seems helpful. https://en.m.wikipedia.org/wiki/Word2vec https://en.m.wikipedia.org/wiki/Word2vec
opportune 9y ago
Quick run down on word2vec and what happened here: A big problem with NLP is understanding the semantic associations between words (or even lemmas. Lemmas in this context refer to different meanings of the same word, like a baseball bat vs. a vampire bat). For example "run" and "sprint" are similar in meaning but convey different connotations; kings and queens are both high-level monarchs but we need to encode the difference in gender between them for a true semantic understanding. The problem is that the information in words themselves don't accurately convey all of this information through their string (or spoken) representations. Even dictionary definitions lack explanations of connotations or subtle differences in context, and furthermore aren't easily explained to a computer Word2vec is an algorithm that maps words to vectors, which can be compared to one another to analyze semantic meaning. These are typically high-dimensional (e.g. several hundred dimensions). When words are used often together, or in similar contexts, they are embedded within the vector space closer to each other. The idea is that words like "computer" and "digital" are placed closer together than "inference" and "paddling". Usually these vector mappings are represented as something like a python dictionary with each key in the dictionary corresponding to some token or word appearing at least one (maybe more) times in some set of training data. As you can imagine these can be quite large if the vocabulary of the training data is diverse, and due to being in such a high-dimensional space, the precision of a vector entry may not need to be as high as doubles or floats encode. Floats are 32 bits. The authors of this paper/repo figured out a way to quantize vector entries into representations with smaller numbers of bits, which can be used in storage to make saved word2vec models even smaller. This is really useful because a big problem with running word2vec instances is that they can take up space on the order of gigabytes. I haven't read it all yet but it seems the big innovation might have been figuring out a way to work with these quantized word vectors in-memory without losing much performance Edit: seems it may not work in-memory

creichenbach 9y ago

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

a_bonobo 9y ago

This could be useful with DNA/protein sequences - there's dna2vec and similar approaches to mine sequences for regulatory elements and more, the problem when compared with word2vec is that you have an order of magnitude more words. You don't really have words so you split the continuous DNA sequence into overlapping mers and treat that as words (afaik). That means that dna2vec takes forever (>24h with one chromosome) and builds a huge vector. I wonder whether this will speed up things...

rspeer 9y ago

It's interesting and slightly uncomfortable that the illustration for similar words uses the word "man" as an example, given the gender biases that result from learning word vectors solely from word distributions. To explain, although I’m sure the author himself is familiar with the issue: For any word that is disproportionately associated with one gender in the corpus, the model will learn that gender difference as part of the representation of the word, pretty much baking it into all applications. [1] It's all fun and games when this helps you find the difference between "king" and "queen", but it becomes a problem when the same difference appears between "genius" and "beautiful". I haven't evaluated these vectors for built-in biases, but I assume they would have similar problems to the pre-computed word2vec and GloVe embeddings. (If they don't -- if quantization is a natural way to counteract bias -- then that's an awesome result! But an unlikely one.) To the author: I don’t mean this to sound like an accusation that you haven’t done this yet; I know that short papers can’t tell two stories at the same time. But the next step is pretty clear, right? How do these vectors measure on the Word Embedding Association Test for implicit bias? Does Bolukbasi’s de-biasing method, or an analogue of it, work on quantized embeddings? [1] Bolukbasi et al., "Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings." https://arxiv.org/abs/1607.06520 https://arxiv.org/abs/1607.06520

maxlam 9y ago
Interesting, definitely need to think about debiasing. Seems like it won't really work straight out of the box since it'd destroy the 1 bit-ness of the vectors. Though if only a few of the vectors are de-biased then you can still save a lot of space since all the other vectors are still represented using 2 numbers (while the de-biased vectors are represented using the full range of 32 bit numbers).
- rspeer 9y ago
  There may be a way to build it into the loss function so that it happens before the quantization, right? (and holy crap, look how fast the HN conservatives are getting to my comment)
  - 9y ago

dougb5 9y ago

This is great and echoes a recent fascination for me. One application of compact word embeddings is that if they're small enough you can ship a whole model to the user in a web app so that semantic computations can be done entirely client-side, which is useful for privacy. I did a naive 1-bit quantization a few months ago in order to fit a large-vocabulary word embedding into a smallish (< 3 MB) JSON file so that synonyms could be generated by the user without hitting a server. (See https://docs.google.com/presentation/d/1SfbfnuNSlDRtUOpN1KNc2RMtw030defCDME6p_268fQ/edit#slide=id.g28366446a3_0_110 https://docs.google.com/presentation/d/1SfbfnuNSlDRtUOpN1KNc... for a description and https://prototypes.cortico.ai/search-history/ https://prototypes.cortico.ai/search-history/ for the application -- happy to send you more details/code if you want) I never got as far as formally evaluating the quality of these vectors, though.

visarga 9y ago
You can also replace rare words with a linear combination of 1..3 of their closest neighbours, especially for topic classification tasks. This would allow higher precision for more frequent words and still handle the rare words, reducing the number of vectors you need to send to the thin client.
narrator 9y ago
Finally a use for 5g bandwidth: sending big ML models to the client.
rpedela 9y ago
Can you expand on the privacy use case? I don't understand how applying a word vector model on the client improves privacy.
- darawk 9y ago
  You presumably do not have to ship the content of the user's query up to the server.
  - rpedela 9y ago

Jack000 9y ago

can this be done with fasttext as well? Word2bits is definitely great for memory-constrained applications but for server use memory isn't as much a constraint (there's a direct word -> vector relationship so you can just put it in a database) it would be amazing to combine this with fasttext's ability to generate vectors for out-of-vocab words.

manojlds 9y ago
Yeah you can - https://github.com/facebookresearch/fastText/blob/master/quantization-example.sh https://github.com/facebookresearch/fastText/blob/master/qua...

Radim 9y ago

Optimizations are always great :-) This sounds similar to Maciej Kula's experiments in "Binary Latent Representations for Efficient Ranking: Empirical Assessment", https://arxiv.org/abs/1706.07479 https://arxiv.org/abs/1706.07479. Maciej shared this [1]: "FWIW I ran similar experiments on recommendation tasks. My initial results were very encouraging (and similar to those reported here), but the effect disappeared entirely after adding regularization to the baseline. I would have more confidence in the results reported here if the authors ran a more principled hyperparameter search, and added regularization to their baseline." [1] https://twitter.com/Maciej_Kula/status/976028573487239168 https://twitter.com/Maciej_Kula/status/976028573487239168

mark_l_watson 9y ago

Very nice, thanks for creating this! In addition to (possibly new) hardware that supports much larger memory, compression techniques like this might allow us to start operations with “phrase embedding” or eventually even whole “sentence embedding.”

tmalsburg2 9y ago

Interesting to see that "science" and "fiction" are so similar according to this metric. Not surprising, though, given how often they co-occur in text, but this clearly shows the limitations of the method. The unit of interest is not really character strings but lexical entries and there can be multiple lexical entries associated with one character string. For instance, the word "bank" can mean "financial institution" or "edge of a river" but both meanings would contribute to a common word vector. You could say that this only affects ambiguous words, but first ambiguous words are very common and second these words probably distort the whole vector space (by introducing "short circuits") and therefore also affect the vectors for non-ambiguous words. A long way left to go for these methods I suppose. Edit: Have people tried to detect ambiguous words by measuring local conflict in word2vec space? E.g. "laboratory" is similar to "science" and "science" is similar to "fiction" but there is no evidence to suggest that "laboratory" should be similar to "fiction".

popinman322 9y ago
This is a known problem and work is being done on it. I'm not sure whether there's work in the specific direction that you specified in your edit, but I did manage to find this paper from 2012 via a quick search: http://www.aclweb.org/anthology/P12-1092 http://www.aclweb.org/anthology/P12-1092 This paper in particular has ~700 citations right now; I didn't go through them to see the latest work but this likely doesn't represent the cutting edge. I imagine that marginal computational cost would be the deciding factor in choosing a more advanced model here. Granted, these embeddings are often generated infrequently so I don't see the harm in extra one-off training time. It's possible that choosing between definitions adds overhead elsewhere in the system.
morelandjs 9y ago
One method to partially rectify the problem you mention is to add additional preprocessing to the text to identify ngrams and add part of speech tags to words. For example [The, river, bank] might be restructed as [The, river bank (bigram)] where "river bank" is embedded as its own word vector. This can also be used to disambiguate words like "hit" which can be used as a verb and a noun. You just replace "hit" with "hit|noun" and "hit|verb".

loxias 9y ago

Interesting. So, this approach computes a "traditional" neural embedding, in say, R^50, and then "brutally" replaces each of the reals with an integer in Z_2,4,8... I can't quite put my finger on it, but my hunch is that this naive method, while already delivering interesting results, can be drastically improved upon. * don't use a fixed bit depth for all vector components I guess it depends on what you're trying to optimize for -- what algebraic properties you wish to preserve for the end application: If the end goal is: "linearity be damned, I want a stupidly fast but inaccurate way of doing approximate nearest neighbor search", then turning words into bitvectors, and using hamming distance, not(xor(a,b)), &c" works. Either way, thanks for the ideas, OP. (was going to go on with some mathematical stuff which I suspect would improve upon it, but decided to either shutup, or put-up-and-credit-you.)

_mhr_ 9y ago
I would appreciate if you elaborated on your supposed improvements.

malcook 9y ago

Is there an explanation for why almost all the words most distant from "man" are either uppercase or otherwise lexically anomalous? Is it largely driven by their being low frequency in the corpus?