Intro

Occasionally, you may want to get the next/prev lexicographical permutation of a sequence. How would you do that? If you are a C++ programmer, you are probably familiar with the next_permutation¹ and prev_permutation² APIs. However, Python does not provide the counterparts. So the topic today is how to do this in Python. Since the solutions of prev lexicographical permutation and the next lexicographical permutation are very similar, let us focus on the next lexicographical permutation problem.

A taxonomy of tokenization methods

In NLP, one crux of problems is - how to tokenize the text. There are three methods available:

• Char-level
• Word-level
• Subword-level

Let’s talk about the Char-level tokenizer. That is, we tokenize the text into a char stream. For instance, highest -> h, i, g, h, e, s, t. One advantage of the Char-level tokenizer is that the size of Vocab won’t be that large. The size of Vocab is equal to the size of the alphabet. So you probably won’t meet the infamous Out-of-vocabulary(OOV) problem. However, the downside is that the char itself does not convey too much information, and we will get too many tokens after tokenizing. Try to imagine that a simple word highest will give us 7 tokens😨

What is the bag-of-word model?

In NLP, we need to represent each document as a vector because machine learning can only accept input as numbers. That is, we want to find a magic function that: $$ f(\text{document}) = vector $$

Today’s topic is bag-of-word(BoW) model, which can transform a document into a vector representation.

💡 Although the BoW model is outdated in 2023, I still encourage you to learn from the history and think about some essential problems:

Intro

You may have difficulties when trying to calculate the partial derivatives in machine learning like me. Even though I found a good reference cookbook that could be used to derive the gradients, I still got confused. Today, I want to share a practical technique I recently learned from this video: when calculating partial derivatives in machine learning, you can treat everything as if it were a scalar and then make the shapes match

Intro

Even though I have been using Numpy and Pytorch for a long time, I never really knew how they implemented the underlying tensors and why they are so efficient. Recently, while studying the course Deep Learning Systems, I finally got the opportunity to try implementing tensors on my own. After going through the process, my understanding of tensors is much better 🧐

As a Pytorch user, is it necessary to understand the underlying tensor storage mechanism? I believe it is essential. In most cases, understanding the underlying principles helps you grasp higher-level concepts better. For example, understanding the tensor storage mechanism can help you answer the following questions:

Intro

If you are attracted by the title of this blog, I believe you may agree with me: The process of memorizing the insertion and deletion operations of the Red-black tree can be incredibly arduous. It entails keeping track of complex tree rotations and the necessity to recolor nodes as required. I once read the renowned Introducing to Algorithms written by the CLRS. However, there are so many cases to remember and I quickly get overwhelmed.

What is the git bundle command

git bundle is a relatively less commonly used git command. Its purpose is to package a git repo into a single file, which can then be used by others to recreate the original git repo. Additionally, git bundle supports incremental update. Before I learned about the git bundle command, I would usually directly use tar czf some_git_repo to create a package for a git repo. Recently, I accidentally discovered the git bundle and found it quite useful🍻.

What’s MPNN

Justin Gilmer proposed the MPNN (Message Passing Neural Network) framework ¹ for describing graph neural network models used in supervised learning on graphs. I found this to be a useful framework that provides a clear understanding of how different GNN models work and facilitates a quick grasp of the differences between them. Considering a node $v$ on the graph $G$, the update procedure for its vector representation $h_v$ is as follows:

Question

Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as an argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well.

Question

Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.

Question

Suppose we define the procedure f. What happens if we (perversely) ask the interpreter to evaluate the combination (f f)?