5 ms·

Show HN: Word2vec Algorithm in ~100sloc with NumPy

72 points by extasia 3y ago

Here's a small demonstration of the fundamental aspects of the word-to-vec algorithm. It's implemented in a single python script and depends only on a single text file for training. It's not meant to be blazingly fast or anything, just a toy example to aid my understanding of how word vectors might be learnt from a corpus.

eesmith 3y ago
I have a suggestion for improving clarity: word_bag: dict[str, int] = dict() # Multiset for line in raw_corpus: words = line.split() for word in words: if word in word_bag: word_bag[word] += 1 else: word_bag[word] = 1 Try: word_bag = collections.Counter() for line in raw_corpus: word_bag.update(line.split()) then, to filter: word_bag = {word: count for (word, count) in word_bag.items() if count >= min_frequency} or, if you can avoid printing the filtered word bag: return set(word for (word, count) in word_bag.items() if count >= min_frequency) Also, that: raw_corpus : list[list[str]], should be list[str]. It's your corpus which is a list[list[str]]. (And you might want to use "line_words" instead of "line" Could you explain why lines are processed independently? for i, line in enumerate(corpus): for j, target_word in enumerate(line): Does it make a difference that some lines have fewer words than others? I would think that for positive_words in sliding_window(flatten(corpus), window_size): using the sliding_window and flatting recipes at https://docs.python.org/3/library/itertools.html#itertools-recipes https://docs.python.org/3/library/itertools.html#itertools-r... would be more appropriate. Though using it directly would not handle the leading/trailing partial windows. I liked seeing the 'η' - I haven't yet used non-ASCII in my code!
- extasia 3y ago
  Hi eesmith, thanks for your insight! I've applied a lot of the improvements you mentioned, the collections.Counter one didn't even cross my mind- very neat:) The lines are processed independently as they are separate sentences. One line may be from one source, and the next from a completely different source. The problem with simply concatenating them is that the target words on the boundaries between sentences can end up with context words from unrelated sentences. >I liked seeing the 'η' - I haven't yet used non-ASCII in my code! Then you may enjoy this april fool's python issue I made https://github.com/python/cpython/issues/103172 https://github.com/python/cpython/issues/103172 Yeah, I like using utf-8 chars for mathematical symbols, it makes my brain hurt a little less when mapping between the two! I also like using ŷ for predictions in ML contexts as that's the canonical symbol used in the literature.
  - eesmith 3y ago
    > The lines are processed independently as they are separate sentences. Ahh! I didn't understand that about the corpus. Thanks!
nico 3y ago
Ignorant question about the algorithm: There is a min_frequency threshold for including words Wouldn’t you want a max_frequency instead? A lot of times infrequent words are more important than the frequent ones (eg titles vs articles)
- spott 3y ago
  The algorithm learns by looking at contextual words around a given word. If a word is infrequent, there isn't enough context to span the space of possible contexts for the word, making it difficult for the algorithm to get a good idea about what the word means. It is also worth discussing the difference between the training corpus (the data that the word vectors are found from) and the inference corpus (the data that the word vectors are used on). If a word is uncommon in the inference corpus, but is common enough to be trained on the training corpus, then a vector is still generated and useful for the inference task.
  - nico 3y ago
    Thank you for the thoughtful explanation. Follow up: Is the context considered “all appearances of the word”, or “text around the word”? Also, are all positions/“areas” of the corpus considered evenly important except for their frequency? In other words, ie position within the corpus considered at all? (eg. Usually titles are more relevant to a document then a random sentence or word in the middle of it)
    - extasia 3y ago
      The context for one training step is the target word, plus a window of the `n` words that precede and follow that word. For example in the sentence: > Usually titles are more relevant to a document then a random sentence or word in the middle of it If 'document' is the current target word, we select ["relevant", "to", "a"] and ["then, "a", "random"] as our left and right contexts. These context words and our target word, ["document"] form our 'positive' examples that we want to move closer together in the embedding space. Position in the text is not used in this algorithm. You're right about titles being more relevant to the meaning of a document but the document isn't important: it's just a resource that we're using to learn which words occur together (and thus are semantically related). The algorithm steps through every single word as a target and thus will inevitably utilize words that were titles just as much as words in any other part of the text:) Hope that helps!
sandos 3y ago
What Ive wondered about word-vectors is, are different meanings split or not? A word having many meanings would otherwise means its vectors are more "smeared" out and less accurate I guess. Although, I guess that might be good for these algorithms.
- extasia 3y ago
  In the skip-gram algorithm (aka word-2-vec), words vectors are global; i.e one word maps to one vector. In practice, as you intuit, contextual embeddings are in fact useful for obtaining more precise word vectors. The example given in[0] is BERT's embeddings, though I would imagine that most NLP applications nowadays all use contextual embeddings since they're a strict improvement over static embeddings. [0]. https://web.stanford.edu/~jurafsky/slp3/6.pdf https://web.stanford.edu/~jurafsky/slp3/6.pdf (search for 'static embeddings')
  - rolisz 3y ago
    Contextual embeddings are not a strict improvement over static embeddings: if you don't have context, they tend to be worse. For example, if you have tags for example, which usually are just single words, word2vec style embeddings are better usually.
    - extasia 3y ago
      Do you mean html tags? I'm not sure I follow!
      - sp332 3y ago
        No, a tag like a hashtag.
      - chaxor 3y ago
        I think they're trying to say there is a good use case for everything. For instance, if you have a set of keyword-like IDs (normalized items like EntityID:47283 for example) for a container of these things, like documents, you can make a quick GLoVe or W2V representation for each entityID, and then the cosine similarity between an entity vector and itself is exactly 1, not 0.98 or something. So in the scenario that these are products which have IDs, and the container is a document that mentions these products together, you can reduce it to a key-value map of documentID-[list of product IDs], and then by selecting the vectors that have cosine similarity of .95-0.9999, you can get the object similar to that product but not that product. Using contextualized vectors, in the best case would give you things similar as well as the query product, but for every single instance, not just the single abstract entity.
sdenton4 3y ago
Neat! It /should/ be pretty easy to convert this to Jax, as a big party of the Jax API is just reimplementing the Numpy API. The two changes I can imagine are: a) handling randomness requires more explicit rng estate handling, and b) wrapping the inner loop in a function so that it can be JIT-compiled. The advantage to doing this is that you can then run your code on a GPU, getting you most of the way to 'blazingly fast.'
SethTro 3y ago
Right out of the bag lots of wasted lines word_bag: dict[str, int] = dict() # Multiset for line in raw_corpus: words = line.split() for word in words: if word in word_bag: word_bag[word] += 1 else: word_bag[word] = 1 keys_to_drop = [] for k, v in word_bag.items(): if v < min_frequency: keys_to_drop.append(k) for k in keys_to_drop: del word_bag[k] pprint(word_bag) print(len(word_bag)) vocabulary = word_bag.keys() return set(vocabulary) Can be a python one/two liner # word_bag = Counter() # defaultdict(int) word_bag = Counter(word for line in raw_corpus for word in line.split()) return set(word for word, count in word_bag.items() if count >= min_frequency)
- CamperBob2 3y ago
  Sometimes Python's conciseness works against its value as a didactic language.
  - Y_Y 3y ago
    The original code looked like someone had learned old-school C++ and just shoehorned that into python. This phenomenon is all over physics. The fixed code isn't just short, it's idiomatic and clear (YMMV) and hence much easier to understand.
    - nine_k 3y ago
      Reasonably modern C++ would allow you to define a Counter class, and to define maps and filters, if the stdlib versions don't work for you for whatever reason. Fortran, on the other hand,...
- NathanFulton 3y ago
  I collect mini implementations of ML things for teaching purposes. In this case, the longer-form version is a better artifact. Pithy readable implementations of core ideas have a lot of value. I don't see much value in code golfing besides having fun :)
sireat 3y ago
The golden standard for word2vec and topic modeling in general is gensim: https://radimrehurek.com/gensim/models/word2vec.html https://radimrehurek.com/gensim/models/word2vec.html I've been using gensim for a few years for topic modeling. It works great with pyLDAvis for visualizations. How does your implementation differ from the one by Radim?
- extasia 3y ago
  It's not a serious implementation but one for didactic purposes:) I've used gensim's one and it seems great for practical use but I wanted to build an understanding of the underlying algorithm, so built my own from scratch. I was hoping others might learn from it, but it's not really a practical approach to constructing w2v embeddings.
quickthrower2 3y ago
Beginner here. Having done most of the Karpathy YT course I have seen embeddings trained as part of a larger net that is predicting the next token. After the embedding is run on several tokens the output goes though several layers of linear;batchnorm;nonlinear. I haven’t done the wavenet or transformer stuff yet. How can you train the embedding without that? And if you can, is it a good or bad idea to prepare your embedding using this script first then chuck those weights into a bigger model (I think I know what the answer will be…)

72 points by extasia 3y ago

eesmith 3y ago

I have a suggestion for improving clarity: word_bag: dict[str, int] = dict() # Multiset for line in raw_corpus: words = line.split() for word in words: if word in word_bag: word_bag[word] += 1 else: word_bag[word] = 1 Try: word_bag = collections.Counter() for line in raw_corpus: word_bag.update(line.split()) then, to filter: word_bag = {word: count for (word, count) in word_bag.items() if count >= min_frequency} or, if you can avoid printing the filtered word bag: return set(word for (word, count) in word_bag.items() if count >= min_frequency) Also, that: raw_corpus : list[list[str]], should be list[str]. It's your corpus which is a list[list[str]]. (And you might want to use "line_words" instead of "line" Could you explain why lines are processed independently? for i, line in enumerate(corpus): for j, target_word in enumerate(line): Does it make a difference that some lines have fewer words than others? I would think that for positive_words in sliding_window(flatten(corpus), window_size): using the sliding_window and flatting recipes at https://docs.python.org/3/library/itertools.html#itertools-recipes https://docs.python.org/3/library/itertools.html#itertools-r... would be more appropriate. Though using it directly would not handle the leading/trailing partial windows. I liked seeing the 'η' - I haven't yet used non-ASCII in my code!

extasia 3y ago
Hi eesmith, thanks for your insight! I've applied a lot of the improvements you mentioned, the collections.Counter one didn't even cross my mind- very neat:) The lines are processed independently as they are separate sentences. One line may be from one source, and the next from a completely different source. The problem with simply concatenating them is that the target words on the boundaries between sentences can end up with context words from unrelated sentences. >I liked seeing the 'η' - I haven't yet used non-ASCII in my code! Then you may enjoy this april fool's python issue I made https://github.com/python/cpython/issues/103172 https://github.com/python/cpython/issues/103172 Yeah, I like using utf-8 chars for mathematical symbols, it makes my brain hurt a little less when mapping between the two! I also like using ŷ for predictions in ML contexts as that's the canonical symbol used in the literature.
- eesmith 3y ago
  > The lines are processed independently as they are separate sentences. Ahh! I didn't understand that about the corpus. Thanks!

nico 3y ago

Ignorant question about the algorithm: There is a min_frequency threshold for including words Wouldn’t you want a max_frequency instead? A lot of times infrequent words are more important than the frequent ones (eg titles vs articles)

spott 3y ago
The algorithm learns by looking at contextual words around a given word. If a word is infrequent, there isn't enough context to span the space of possible contexts for the word, making it difficult for the algorithm to get a good idea about what the word means. It is also worth discussing the difference between the training corpus (the data that the word vectors are found from) and the inference corpus (the data that the word vectors are used on). If a word is uncommon in the inference corpus, but is common enough to be trained on the training corpus, then a vector is still generated and useful for the inference task.
- nico 3y ago
  Thank you for the thoughtful explanation. Follow up: Is the context considered “all appearances of the word”, or “text around the word”? Also, are all positions/“areas” of the corpus considered evenly important except for their frequency? In other words, ie position within the corpus considered at all? (eg. Usually titles are more relevant to a document then a random sentence or word in the middle of it)
  - extasia 3y ago
    The context for one training step is the target word, plus a window of the `n` words that precede and follow that word. For example in the sentence: > Usually titles are more relevant to a document then a random sentence or word in the middle of it If 'document' is the current target word, we select ["relevant", "to", "a"] and ["then, "a", "random"] as our left and right contexts. These context words and our target word, ["document"] form our 'positive' examples that we want to move closer together in the embedding space. Position in the text is not used in this algorithm. You're right about titles being more relevant to the meaning of a document but the document isn't important: it's just a resource that we're using to learn which words occur together (and thus are semantically related). The algorithm steps through every single word as a target and thus will inevitably utilize words that were titles just as much as words in any other part of the text:) Hope that helps!

sandos 3y ago

What Ive wondered about word-vectors is, are different meanings split or not? A word having many meanings would otherwise means its vectors are more "smeared" out and less accurate I guess. Although, I guess that might be good for these algorithms.

extasia 3y ago
In the skip-gram algorithm (aka word-2-vec), words vectors are global; i.e one word maps to one vector. In practice, as you intuit, contextual embeddings are in fact useful for obtaining more precise word vectors. The example given in[0] is BERT's embeddings, though I would imagine that most NLP applications nowadays all use contextual embeddings since they're a strict improvement over static embeddings. [0]. https://web.stanford.edu/~jurafsky/slp3/6.pdf https://web.stanford.edu/~jurafsky/slp3/6.pdf (search for 'static embeddings')
- rolisz 3y ago
  Contextual embeddings are not a strict improvement over static embeddings: if you don't have context, they tend to be worse. For example, if you have tags for example, which usually are just single words, word2vec style embeddings are better usually.
  - extasia 3y ago
    Do you mean html tags? I'm not sure I follow!
    - sp332 3y ago
      No, a tag like a hashtag.
    - chaxor 3y ago
      I think they're trying to say there is a good use case for everything. For instance, if you have a set of keyword-like IDs (normalized items like EntityID:47283 for example) for a container of these things, like documents, you can make a quick GLoVe or W2V representation for each entityID, and then the cosine similarity between an entity vector and itself is exactly 1, not 0.98 or something. So in the scenario that these are products which have IDs, and the container is a document that mentions these products together, you can reduce it to a key-value map of documentID-[list of product IDs], and then by selecting the vectors that have cosine similarity of .95-0.9999, you can get the object similar to that product but not that product. Using contextualized vectors, in the best case would give you things similar as well as the query product, but for every single instance, not just the single abstract entity.

sdenton4 3y ago

Neat! It /should/ be pretty easy to convert this to Jax, as a big party of the Jax API is just reimplementing the Numpy API. The two changes I can imagine are: a) handling randomness requires more explicit rng estate handling, and b) wrapping the inner loop in a function so that it can be JIT-compiled. The advantage to doing this is that you can then run your code on a GPU, getting you most of the way to 'blazingly fast.'

SethTro 3y ago

Right out of the bag lots of wasted lines word_bag: dict[str, int] = dict() # Multiset for line in raw_corpus: words = line.split() for word in words: if word in word_bag: word_bag[word] += 1 else: word_bag[word] = 1 keys_to_drop = [] for k, v in word_bag.items(): if v < min_frequency: keys_to_drop.append(k) for k in keys_to_drop: del word_bag[k] pprint(word_bag) print(len(word_bag)) vocabulary = word_bag.keys() return set(vocabulary) Can be a python one/two liner # word_bag = Counter() # defaultdict(int) word_bag = Counter(word for line in raw_corpus for word in line.split()) return set(word for word, count in word_bag.items() if count >= min_frequency)

CamperBob2 3y ago
Sometimes Python's conciseness works against its value as a didactic language.
- Y_Y 3y ago
  The original code looked like someone had learned old-school C++ and just shoehorned that into python. This phenomenon is all over physics. The fixed code isn't just short, it's idiomatic and clear (YMMV) and hence much easier to understand.
  - nine_k 3y ago
    Reasonably modern C++ would allow you to define a Counter class, and to define maps and filters, if the stdlib versions don't work for you for whatever reason. Fortran, on the other hand,...
NathanFulton 3y ago
I collect mini implementations of ML things for teaching purposes. In this case, the longer-form version is a better artifact. Pithy readable implementations of core ideas have a lot of value. I don't see much value in code golfing besides having fun :)

sireat 3y ago

The golden standard for word2vec and topic modeling in general is gensim: https://radimrehurek.com/gensim/models/word2vec.html https://radimrehurek.com/gensim/models/word2vec.html I've been using gensim for a few years for topic modeling. It works great with pyLDAvis for visualizations. How does your implementation differ from the one by Radim?

extasia 3y ago
It's not a serious implementation but one for didactic purposes:) I've used gensim's one and it seems great for practical use but I wanted to build an understanding of the underlying algorithm, so built my own from scratch. I was hoping others might learn from it, but it's not really a practical approach to constructing w2v embeddings.

quickthrower2 3y ago

Beginner here. Having done most of the Karpathy YT course I have seen embeddings trained as part of a larger net that is predicting the next token. After the embedding is run on several tokens the output goes though several layers of linear;batchnorm;nonlinear. I haven’t done the wavenet or transformer stuff yet. How can you train the embedding without that? And if you can, is it a good or bad idea to prepare your embedding using this script first then chuck those weights into a bigger model (I think I know what the answer will be…)