Show HN: Word2vec Algorithm in ~100sloc with NumPy | Hacker News Reader

Show HN: Word2vec Algorithm in ~100sloc with NumPy

github.com

72 pointsextasia30 comments

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.

Open articleView on HN

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)

Sometimes Python's conciseness works against its value as a didactic language.

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.

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,...

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 :)

I politely disagree. Both pieces of code have a teaching value, but different.

The iterative code is busy and long, but allows to track exactly how the pretty trivial calculation is happening, down to elementary(-ish) operations.

The comprehension-based code is more declarative; it succinctly shows what is happening, in almost plain English, without the minute details cluttering out the purpose of the code.

For anyone who is not a Python beginner, but is an ML beginner, the shorter version is much more approachable, as it puts the subject matter more front-and-center.

(Imagine that every matrix multiplication would be written using explicit loops, instead of one "multiply" operation. Would it clarify linear algebra for you, or the other way around?)

> For anyone who is not a Python beginner, but is an ML beginner, the shorter version is much more approachable, as it puts the subject matter more front-and-center.

It certainly depends on the audience. Interestingly, I had the opposite conclusion about Python beginners in my head before reaching this line!

I think it's more about the learner's prior background. Lately, I've mostly been helping friends who do a lot of scientific computing get started in ML. For that audience, the "nested loops" presentation is typically much easier to grok.

> (Imagine that every matrix multiplication would be written using explicit loops, instead of one "multiply" operation. Would it clarify linear algebra for you, or the other way around?)

Obviously "every" would be terrible. But there's a real question here if we flip "every" to "first". For a work-a-day mathematician who doesn't write code often, certainly not! For a work-a-day programmer who didn't take or doesn't remember linear algebra, the loopy version is probably worth showing once before moving on.

On a related note: I sometimes find folds easier to understand than loops. Other times find loops easier to understand than folds. I'm not particularly sure why. Probably having both versions stashed away and either exercising judgement based on the learner at hand -- or just showing both -- is the best option.

I sympathize with your position, but in this case the two liner is significantly more readable. I had no problem digesting it. I then looked at the longer version and it was a much higher cognitive load to digest that. I have to look at multiple for loops to realize they're merely counting the words in a corpus. The shorter version lets me see it immediately.

It's probably a matter of audience. For the folks I've been teaching lately, who mostly know some combination of Java/C++/MATLAB, the Pythonic version is probably harder to follow.

Anyways, now I have two ways of saying the same thing, which is always nice to have when teaching.

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-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!

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

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.

> The lines are processed independently as they are separate sentences.

Ahh! I didn't understand that about the corpus. Thanks!

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.

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 (search for 'static embeddings')

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.

Do you mean html tags? I'm not sure I follow!

No, a tag like a hashtag.

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.

Think Instagram or Twitter tags.

That mainly depends on the number of dimensions on the model, and if the training picked up split meaning.

With a high dimension vector (>50d, more usually 300d or 500d) one or two dimensions together will pick up a concept.

This is why word algebra like

Paris - France + Russia ~ Moscow

works with original Word2Vec vectors.

Language models are better at picking up context-dependent meaning, but word vectors still have good enough performance for many tasks.

No, that’s why you need attention. Some might say that’s all you need…

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…)

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)

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.

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)

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!

> Hope that helps!

Yes, very much

Thank you for such a great explanation, super clear :)

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.'

The golden standard for word2vec and topic modeling in general is gensim: 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?

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.

Reply on news.ycombinator.com