While Language Models (LMs) have demonstrated an ever-wider range of reasoning capabilities, from mathematical problems to symbolic manipulation, their underlying mechanism remains a simple, left-to-right, token-level decision process. In So You Think You Can Prompt(explores Chain of Thought) and Beyond Chain of Thought, we explored two such left-to-right, token-level processing techniques. In this article we explore the problems with such techniques and Tree of Thought, a paradigm that explores the problem space as a tree instead of exploring just a single branch.

Table of Content

1. The Problem: LLMs as “System 1” Thinkers
2. Tree of Thoughts (ToT) Paradigm
3. Core Components of ToT
4. Experiments Results
5. Pros & Cons
6. References And Acronyms Used

The Problem: LLMs as “System 1” Thinkers

The literature on human cognition suggests that people have two modes in which they engage with decisions — a fast, automatic, unconscious mode (“System 1”) and a slow, deliberate, conscious mode (“System 2”).

These two modes have previously been connected to a variety of mathematical models used in machine learning. The simple associative token-level choices of LLMs are also reminiscent of “System 1”, and thus might benefit from augmentation by a more deliberate “System 2” planning process that (1) maintains and explores diverse alternatives for current choices instead of just picking one, and (2) evaluates its current status and actively looks ahead or backtracks to make more global decisions, or in simple words — searching a tree of possible paths to the solution of a problem.

Tree of Thoughts (ToT) Paradigm

This led to the proposition of the Tree of Thoughts (ToT) paradigm, which enables LLMs to navigate and explore multiple reasoning paths. ToT fundamentally frames any complex task as a search through a combinatorial problem space, maintaining a tree where each ‘thought’ serves as a coherent intermediate step toward a solution. This structure allows the model to self-evaluate its progress and systematically explore the search space with lookahead and backtracking.

ToT frames any problem as a search over a tree, where each node is a state s = [x, z1…i ] representing a partial solution with the input and the sequence of thoughts so far. A specific instantiation of ToT involves answering four questions:

1. How to decompose the intermediate process into thought steps?
2. How to generate potential thoughts from each state?
3. How to heuristically evaluate states?
4. What search algorithm to use?

Core Components of ToT

A specific ToT implementation is defined by four operational components:

1. Thought decomposition:

Defining how the process is broken down into discrete intermediate thought steps.

2. Thought generator:

Strategies for producing k candidate thoughts from a current state. Two strategies used in the paper are:

1. Sample: independent and identically distributed (i.i.d.) thoughts from a CoT prompt. This works better when the thought space is rich (e.g. each thought is a paragraph), and i.i.d. samples lead to diversity.
2. Propose: Generate thoughts sequentially using a “propose prompt” (Game of 24, Figure 2; Crosswords, Figure 6). This works better when the thought space is more constrained (e.g. each thought is just a word or a line), so proposing different thoughts in the same context avoids duplication.

3. State Evaluator:

Heuristically assessing the progress of states to determine which states to keep exploring and in which order. We consider two strategies to evaluate states either independently or together:

1. Value: A value prompt reasons about the state to generate a scalar value (e.g. 1–10) or a classification (e.g. sure/likely/impossible) that could be heuristically turned into a value. Such valuations do not need to be perfect, and only need to be approximately helpful for decision making.
2. Vote: A “good” state is voted out based on deliberately comparing different states in a vote prompt. When problem success is harder to directly value (e.g. passage coherency), it is easier to compare different partial solutions and vote for the most promising one.

4.Search Algorithm:

The chosen method for systematically navigating the tree.

1. Breadth-first search (BFS) maintains a set of the b most promising states per step.
2. Depth-first search (DFS) explores the most promising state first, until the final output is reached, or the state evaluator deems it impossible to solve the problem from the current state. In the latter case, the subtree from s is pruned to trade exploration for exploitation.

In both cases, DFS backtracks to the parent state of s to continue exploration.

Experiments Results

The following experiments were done by the authors to compare the performance of Tree of Thought against other prompt techniques.

Game of 24

Game of 24 is a mathematical reasoning challenge, where the goal is to use 4 numbers and basic arithmetic operations (+-*/) to obtain 24.

Baseline Setup: For the standard input-output (IO) prompt, 5 in-context examples were added. For chain-of-thought (CoT) prompting, each input-output pair was augmented with 3 intermediate equations, each operating on two remaining numbers.

In the ToT setup,

• Thought Decomposition + Generator: at each tree node, the remaining numbers are extracted and the LM is prompted to propose possible next steps. The same “propose prompt” is utilized for all three thought steps, despite having only one example with four input numbers.
• Search Algorithm: A breadth-first search (BFS) is performed, where at each step, the best 5 candidates are retained.
• State evaluator: The LM is prompted to evaluate each thought candidate as “sure/maybe/impossible” with respect to reaching 24. Values are sampled 3 times for each thought.

Result: On the Game of 24 mathematical challenge, ToT’s impact was dramatic. The baseline I/O, CoT and CoT-SC[Chain of Thought + Self Consistency] methods yielded meager success rates of 7.3%, 4.0% and 9.0% respectively. In sharp contrast, ToT achieved a 45% success rate with a narrow breadth (b=1) and a compelling 74% with b=5. This demonstrates a decisive superiority over direct left-to-right decoding as around 60% of CoT samples already failed the task after generating the first step, or equivalently, the first three words (e.g. “4 + 9”).

Creative Writing

The input is 4 random sentences and the output should be a coherent passage with 4 paragraphs that end in the 4 input sentences respectively.

Evaluation Process: Evaluating passage coherency in two ways: using a GPT-4 zero-shot prompt to provide a 1–10 scalar score, or using human judgments to compare pairs of outputs from different methods. We employ a subset of the authors in a blind study to compare the coherency of CoT vs. ToT generated passage pairs, where the order of passages is randomly flipped over 100 inputs.

Setup: Both IO and CoT prompts are zero-shot. IO prompts the LM to directly generate a coherent passage given input constraints, CoT prompts the LM to first make a brief plan then write the passage, i.e. the plan serves as the intermediate thought step.
ToT with depth 2 (and only 1 intermediate thought step) — the LM first generates k = 5 plans and votes for the best one (Figure 4), then similarly generate k = 5 passages based on the best plan then vote for the best one. Here the breadth limit b = 1, as only one choice is kept per step. A simple zero-shot vote prompt (“analyze choices below, then conclude which is most promising for the instruction”) is used to sample 5 votes at both steps.

A third approach for thought generation: iterative refinement was also used for thought generation in IO and ToT where new thoughts were refined from old thoughts instead of i.i.d. or sequentially generation.

Results: Figure below shows average GPT-4 scores across 100 tasks, where ToT (7.56) is deemed to generate more coherent passages than IO (6.19) and CoT (6.93) on average. The authors do acknowledge that such an evaluation might be noisy. The findings, however, are also confirmed by the human evaluations. In 41 cases ToT was superior to CoT. If you look at the second part of the results on the left, where iterative refine was used, it was more effective and improved coherency scores for both IO and ToT.

Mini Crosswords

We provide 5 example input-output pairs in the IO prompt, and in the CoT prompt additionally include intermediate words in the order. We run each prompt for 10 samples and average the results.

ToT: We leverage a depth-first search that keeps exploring the most promising subsequent word clue until the state is no longer promising, then backtrack to the parent state to explore alternative thoughts. . For thought generation, at each state we translate all existing thoughts into letter constraints for remaining clues and prompt a proposal prompt 5 times to come up with candidates for where and what to fill in the next word. We also prompt the LM to give a confidence level for different thoughts, and aggregate these across proposals to obtain a sorted list of next thoughts to explore. For state evaluations, we similarly translate each state into letter constraints for remaining clues, then evaluate for each clue if it is possible to fill given the constraints. If any remaining clue is deemed “impossible” to fill in, then the exploration of the state’s subtree is pruned and DFS backtracks to its parent to explore the next promising thought.

Result: Both I/O and CoT failed to exceed 16% word-level success, ToT tripled performance, achieving a 60% word-level success rate and solving 4 out of 20 games.

Pros

1. Generality: ToT encompasses existing methods (I/O, CoT) as special cases. (i.e. trees of limited depth and breadth).
2. Modularity & Adaptability: Allows for independent variation of the base LM, thought procedures, and search algorithms to fit diverse constraints.
3. Convenience: Requires no extra training, functioning purely on top of a pre-trained model.
4. Interpretability: Significantly enhances the transparency of model decision-making.

Cons

1. Computational Cost: Deliberate search necessitates substantially more resources than standard decoding.
2. Necessity: May be an unnecessary complexity for tasks that current LLMs already solve effectively.
3. Scope: Initial studies have been restricted to a limited set of relatively simple tasks.

References And Acronyms Used

• Tree of Thoughts: Deliberate Problem Solving with Large Language Models by Shunyu Yao, Dian Yu and co.
• Github repo: https://github.com/princeton-nlp/tree-of-thought-llm
• CoT = Chain of Thought
• Cot-SC = Chain of Thought with Self Consistency

Tree of Thought was originally published in Data Science Collective on Medium, where people are continuing the conversation by highlighting and responding to this story.

After learning about Chain of Thought, the prompts got better but it still doesn’t work for everything. So where do we go from here?

If you remember in my previous article, we discussed one flaw of LLMs — they are inconsistent. Just because we solved a problem with one prompt, it doesn’t guarantee that a slightly different variant of the prompt will also return the same result. This makes them difficult to rely on and one must verify the answers they give to some degree. But can this inconsistency be used to improve our confidence (and in general the robustness) in LLMs’ responses?

Self Consistency

Self-consistency leverages the intuition that complex reasoning tasks typically admit multiple reasoning paths that reach a correct answer. The more that deliberate thinking and analysis is required for a problem, the greater the diversity of reasoning paths that can recover the answer.

What the authors of this paper are trying to say here is that if you arrive at the same answer by following multiple reasoning paths, the odds of that answer being correct is higher than the answers which it arrived at only once. Such an approach is analogous to the human experience that if multiple different ways of thinking lead to the same answer, one has greater confidence that the final answer is correct.

Think of a class of 10 students, 7 of the students arrive at the same answer while the 3 have 3 different answers. The odds of the common answer being correct is statistically higher than any of the 3 other answers. Is it guaranteed that the common answer is the correct answer? NO. In a similar way, if LLMs arrive at the same answer by multiple reasoning paths, the odds of that being the correct answer is higher, but correctness is still not guaranteed.

Since language models are not perfect reasoners (like the students in our hypothetical class), the model might also produce an incorrect reasoning path or make a mistake in one of the reasoning steps, but such solutions are less likely to arrive at the same answer. That is, the paper hypothesizes that correct reasoning processes, even if they are diverse, tend to have greater agreement in their final answer than incorrect processes.

Steps for Self Consistency

Instead of greedily decoding the optimal reasoning path as traditional LLMs do, the paper proposes a “sample-and-marginalize” decoding procedure. They first sample from the language model’s decoder to generate a diverse set of reasoning paths.

Then they generate an answer for each reasoning path, hoping some reasoning path might lead to a different final answer. (Getting the same answer from all paths might only happen for simple problems — for which you might not need self consistency in the first place to achieve good performance.)

Lastly, they determine the optimal answer by “marginalising” out the sampled reasoning paths to find the most consistent answer in the final answer set.

In layman terms, prompt the LLM a few times so that it generates different reasoning paths for the same prompt. Collect all the answers. Return the most frequently returned answer.

One should note that self-consistency can be applied only to problems where the final answer is from a fixed answer set, but in principle this approach can be extended to open-text generation problems if a good metric of consistency can be defined between multiple generations, e.g., whether two answers agree or contradict each other.

How to Generate Multiple Reasoning Paths?

So it sounds convincing, how do I try this out for my problem? In the paper the authors performed all experiments in the few-shot setting, without training or fine-tuning the language models. They generated various reasoning paths by applying temperature (aka creativity parameter) sampling and truncated the top k tokens. The truncation step is optional and wasn’t used in all cases.

Some particulars they mentioned, in case you want to recreate the results. Though things get outdated in a blink of an eye, so it might be worthwhile to experiment a bit.

For UL2–20B and LaMDA-137B we applied temperature sampling with T = 0.5 and truncated at the top-k (k = 40) tokens with the highest probability, for PaLM-540B we applied T = 0.7, k = 40, and for GPT-3 we use T = 0.7 without top-k truncation.

Experiments Results

Arithmetic Reasoning

The results are shown in Table 2. 7. Self-consistency improves the arithmetic reasoning performance over all four language models significantly over chain-of-thought prompting. More surprisingly, the gains become more significant when the language model’s scale increases, e.g., we see +3%-6% absolute accuracy improvement over UL2–20B but +9%-23% for LaMDA137B and GPT-3.

Commonsense and Symbolic Reasoning

Self-consistency yielded large gains across all four language models, and obtained SoTA results on 5 out of 6 tasks. For symbolic reasoning, they tested the out-of-distribution (OOD) setting where the input prompt contains examples 4-letters and 4-flips (this setting is more challenging as PaLM-540B or GPT-3 can already achieve perfect in-distribution accuracy). In this challenging OOD setting, the gain of self-consistency is still quite significant compared to CoT-prompting with sufficient model sizes. The results show that sampling a higher number (e.g., 40) of reasoning paths leads to a consistently better performance.

Comparison to Other Existing Approaches

Sample-and-Rank

One commonly used approach to improve generation quality is sample-and-rank, where multiple sequences are sampled from the decoder and then ranked according to each sequence’s log probability. While sample-and-rank does improve the accuracy with additionally sampled sequences and ranking, the gain is much smaller compared to self-consistency.

Beam Search

For a fair comparison we report the accuracy under the same number of beams and reasoning paths. On both tasks self-consistency outperforms beam search significantly. Note self-consistency can also adopt beam search to decode each reasoning path, but its performance is worse compared to self-consistency with sampling.

Ensemble-based Approaches

Compared to self-consistency, existing ensemble-based approaches achieve a much smaller gain. In addition, note that self-consistency is different from a typical model-ensemble approach, where multiple models are trained and their outputs are aggregated. Self-consistency acts more like a “self-ensemble” on top of a single language model.

Pros of Self-consistency

• Self-consistency is entirely unsupervised.
• It works off-the-shelf with pre-trained language models.
• It requires no additional human annotation.
• It avoids any additional training, auxiliary models or fine-tuning.
• Self-consistency also differs from a typical ensemble approach where multiple models are trained and the outputs from each model are aggregated, it acts more like a “self-ensemble” that works on top of a single language model.

Cons of Self-consistency

• It incurs more computation cost.
• Still doesn’t guarantee a correct answer.

References

• https://arxiv.org/pdf/2203.11171-- The paper
• https://learnprompting.org/docs/intermediate/self_consistency?srsltid=AfmBOooGcy5rxs0a7Yea4mDiPTvLquCCiQ9IWHK8XkwPLCzEi0KTiH4L
• https://www.promptingguide.ai/techniques/consistency

Beyond Chain of Thought was originally published in Data Science Collective on Medium, where people are continuing the conversation by highlighting and responding to this story.

The rise of Generative AI (Gen-AI) and its chatbots has undeniably taken the world by storm. It’s almost Luddite-like to not be aware of their impact. I certainly feel a bit like one writing this article because are still people trying to solve problems themselves and looking for answers on the web? Hopefully I am not in the minority. Luddite or not, the advances are truly fascinating and here in my humble attempt to keep up with things, I am sharing my notes on my deep dives in the world of prompting.

Prompts: Origin

Historically, ML models required inputs in a fixed format and therefore were inaccessible to a vast majority of people and were unable to infiltrate our day to day chores. However, with the increasing capabilities of large language models (LLMs), in-context learning (ICL) has emerged as a new paradigm for natural language processing (NLP). ICL allows LLMs to make predictions based on contexts — usually provided through a prompt — that enable users to interact with them using natural language and apply them to everyday problems.

A “prompting-only” approach became viral because

• It doesn’t require a large training dataset to perform a task successfully.
• A single model checkpoint can perform many tasks without loss of generality, making it easier to provide it as a service (think of all the bots) to end-users.
• It eliminates fixed input formats, making it very easy to use without a steep learning curve (unlike previous non-NLP-based models).

Now that natural language, prompt-based models are ubiquitous in user product journeys and our lives, it is imperative to learn more about them. Understanding their full potential, limitations and biases allows us to use them responsibly and benefit from them without falling prey to the misinformation (worst case) or looking like an idiot saying the wrong things confidently (umm least worst case).

How much difference can the quality of a prompt make?

First things first: not all prompts are created equal. The “garbage in, garbage out” rule still applies. The quality of your prompt directly determines the quality of the answer you get and in mathematical cases whether you solved the problem or not.

In short, a prompt makes a HUGE difference! See this research paper for in-depth analysis. This dependency on prompt quality leads to a robustness problem. See Table 1 (in the paper) for a quick overview.

There is a significant gap between the worst performance (lower bound) and best performance (upper bound) for all models. For instance, the worst and best performance of Llama-2–70B-chat are 0.094 and 0.549, respectively, indicating a difference of 0.455. This suggests that the current LLMs’ ability to follow instructions is not robust enough. Even instructions with identical semantics and fluent expressions could lead models like Llama2–70B-chat to plummet from a level comparable to GPT4 (0.5 indicates equivalence to the reference model) to far below the average level (0.292).

^ Quote from the above mentioned paper.

Shot-Based Prompting

This is a quick review of shot prompting, where you provide the context along with some examples of similar solved problems. The number of examples provided are shots (I am not sure how this term came about to be).

Zero-Shot Prompting

Only the problem statement is provided; no examples are given in the prompt.

Example Prompt: How many ‘r’ are there in the word “strawberry”?

Single-Shot Prompting

A single example is given along with the problem statement.

Example Prompt:
Question: How many ‘e’ are there in the word “blueberry”?
Answer: There are 2 ‘e’s in “blueberry”.
How many ‘r’ are there in the word “strawberry”?

Few-Shot Prompting

An LLM receives in-context exemplars of input–output pairs before outputting a prediction for a test-time example.

Example Prompt:
Question: How many ‘e’ are there in the word “blueberry”?
Answer: There are 2 ‘e’s in “blueberry”.
Question: How many ‘p’ are there in the word “pineapple”?
Answer: There are 3 ‘p’s in “pineapple”.
How many ‘r’ are there in the word “strawberry”?

Chain of Thought Prompting

A chain of thought is a series of intermediate natural language reasoning steps that lead to the final output. In chain-of-thought (CoT) prompting, we use few-shot prompting and augment each exemplar with a chain of thought for an associated answer. The prompt consists of triples: <input, chain of thought, output>.

Example Prompt:
Question: How many ‘e’ are there in the word “blueberry”?
Chain of Thought: To find the number of ‘e’s in “blueberry”, I need to examine each letter of the word. Going through the word, I see an ‘e’ at the beginning and another ‘e’ near the end. That makes a total of two ‘e’s.
Answer: There are 2 ‘e’s in “blueberry”.

Question: How many ‘p’ are there in the word “pineapple”?
Chain of Thought: Let’s look at each letter in “pineapple”. I see a ‘p’ at the beginning, another two ‘p’s in the middle. So, there are three ‘p’s.
Answer: There are 3 ‘p’s in “pineapple”.

Question: How many ‘r’ are there in the word “strawberry”?

CoT works better than few-shot prompting alone because traditional few-shot prompting methods (used in Brown et al. (2020)) struggle on tasks that require reasoning abilities and often do not improve significantly with increasing language model scale.

Pros of Chain-of-Thought Prompting:

CoT prompting has several attractive properties as an approach for facilitating reasoning in language models.

1. Decomposition: CoT, in principle, allows models to decompose multi-step problems into intermediate steps, allocating more computation to complex problems.
2. Interpretability: A CoT provides an interpretable window into the model’s behaviour, suggesting how it arrived at a particular answer and providing opportunities to debug incorrect reasoning paths (although fully characterising a model’s computations that support an answer remains an open question).
3. Versatility: CoT reasoning can be used for tasks such as math word problems, common sense reasoning, and symbolic manipulation. It is potentially applicable (at least in principle) to any task that humans can solve via language.
4. Ease of Implementation: CoT reasoning can be easily elicited in sufficiently large off-the-shelf language models simply by including examples of CoT sequences into the exemplars of few-shot prompting.

Results of CoT Prompting

This paper qualitatively explores CoT prompting across various baseline datasets and found the following results:

1. CoT prompting doesn’t positively impact performance for small models, and it only yields performance gains when used with models of ∼100B parameters. Smaller scale models produced fluent but illogical chains of thought, leading to lower performance than standard prompting. (Note: the paper this was based on was published before Deep-seek so this may no lobger be the case)
2. It has larger performance gains for more-complicated problems. For instance, for GSM8K (the dataset with the lowest baseline performance), performance more than doubled for the largest GPT and PaLM models. On the other hand, for SingleOp, the easiest subset of MAWPS which only requires a single step to solve, performance improvements were either negative or very small.
3. Chain-of-thought prompting via GPT-3 175B and PaLM 540B compares favourably to prior state of the art, which typically fine tunes a task-specific model on a labeled training dataset.

Robustness of Chain of Thought

CoT is more robust than few-shot prompts. While there is variance among different chain of thought annotations, all sets of chain of thought prompts outperform the standard baseline by a large margin. This implies that successful use of chain of thought does not depend on a particular linguistic style. CoT prompting for arithmetic reasoning is robust to different exemplar orders and varying numbers of exemplars.

Different number of exemplars

Gains from chain-of-thought prompting generally still held when there was a varying number of few-shot exemplars. Increasing the number of exemplars in standard prompting did not lead to significant gains (e.g., increasing from 8 to 16 exemplars did not improve the performance of standard prompting enough to catch up with chain-of-thought prompting). This shows that CoT is more robust than standard few shot prompting.

Does CoT work on other types of problems?

Common sense Reasoning

So far, most of the results are based on mathematical problem datasets. The language-based nature of chain of thought actually makes it applicable to a broad class of common sense reasoning problems.

Similar to the mathematical problems, for all tasks, scaling up model size improved the performance of standard prompting; CoT prompting led to further gains even when the tasks required a range of common-sense abilities (though the improvement was minimal).

Symbolic Reasoning

To measure improvements at symbolic tasks, the paper tests various models with CoT prompts at two toy tasks:

1. Last-letter concatenation: This task asks the model to concatenate the last letters of words in a name (e.g., “Amy Brown” → “yn”).
2. Coin flip: This task asks the model to answer whether a coin is still heads up after people either flip or don’t flip the coin (e.g., “A coin is heads up. Phoebe flips the coin. Osvaldo does not flip the coin. Is the coin still heads up?” → “no”).

These in-domain evaluations are “toy tasks” in the sense that perfect solution structures are already provided by the chains of thought in the few-shot exemplars; all the model has to do is repeat the same steps with the new symbols in the test-time example.

However, small models still fail — the ability to perform abstract manipulations on unseen symbols for these tasks only arises at the scale of 100B model parameters.

Limitations of CoT

CoT is not a universal solution and comes with a set of limitations.

• Annotation Cost: While the cost of manually augmenting exemplars with chains of thought is minimal in the few-shot setting, such annotation costs could be prohibitive for fine tuning (though this could potentially be surmounted with synthetic data generation, or zero-shot generalisation).
• Computational Cost: The emergence of chain-of-thought reasoning only at large model scales makes it costly to serve in real-world applications.
• Reasoning Errors: There is no guarantee of correct reasoning paths, which can lead to both correct and incorrect answers.
• “Reasoning” Question: Although chain of thought emulates the thought processes of human reasoners, this does not answer whether the neural network is actually “reasoning”.
• Model Dependence: If the same prompt is used for 3 different models, we don’t get the same improvement across all 3 models. The fact that gains don’t transfer perfectly among models is a limitation.
• Model Specificity: Further work is needed to investigate how different pre-training datasets and model architectures affect the performance gain from chain-of-thought prompting.

Why does the Chain of Thought work?

The observed benefits of using CoT prompting raises the natural question of whether the same performance improvements can be conferred via other types of prompting.

The paper tests three variations to see if CoT is the cause of improved performance.

Equation-Only Prompting

Instead of the final answer, the model was asked to output only the final equation. Equation-only prompting doesn’t help much for questions that are too challenging to directly translate into an equation without the natural language reasoning steps in the chain of thought. However, for datasets of one-step or two-step problems, we find that equation only prompting does improve performance, since the equation can be easily derived from the question.

Variable Compute Only

Another intuition is that chain of thought allows the model to spend more computation (i.e., intermediate tokens) on harder problems. To isolate the effect of variable computation from chain-of-thought reasoning, the paper tests a configuration where the model is prompted to output only a sequence of dots (. . .) equal to the number of characters in the equation needed to solve the problem. This variant performs about the same as the baseline, suggesting that variable computation by itself is not the reason for the success of CoT prompting and that there appears to be utility from expressing intermediate steps via natural language.

Chain of thought after answer

Another potential benefit of chain-of-thought prompting (as compared to. vanilla few-shot prompting) could simply be that such prompts allow the model to better access relevant knowledge acquired during pre-training. Therefore, the paper tests an alternative configuration where the CoT prompt is only given after the answer, isolating whether the model actually depends on the produced chain of thought to give the final answer. This variant performs about the same as the baseline, suggesting that the sequential reasoning embodied in the chain of thought is useful for reasons beyond just activating knowledge.

Conclusion

Prompt engineering is a rapidly evolving field and its power is undeniable. While techniques like chain-of-thought prompting offer significant improvements in LLM performance, they are not a panacea. Understanding both the strengths and limitations of these methods is crucial for responsible and effective application of Gen-AI. As models continue to evolve, so too must our understanding of how to best leverage their capabilities. As we increasingly rely on LLMs in various aspects of our lives, it’s essential to be aware of their potential biases and limitations. The journey of prompt optimisation is just beginning, and continuous learning and experimentation are key to unlocking the full potential of LLMs.

References/Future reads

• The CoT paper, also linked above.
• How much difference a prompt makes, read this.
• Learn more about transformers — that give LLMs its superpowers, read here.

So you think you can prompt? was originally published in Data Science Collective on Medium, where people are continuing the conversation by highlighting and responding to this story.

Understanding the most widely used security protocol

What is OAuth?

OAuth (Open Authorisation) is an open standard (basically guidelines) for authorisation (not authentication). To know the difference between the two, read more here.

It is commonly used as a way for access delegation — internet users grant websites or applications access to their information but without giving them the passwords.

What do OAuth guidelines say?

OAuth recommends a safe and secure way to allow access to a certain resource/information without actually sharing it. Think of your resource as a painting in a museum, anyone with a ticket can look at it, they can look at it as many times as they want in a single visit, they can even take a picture of it. But they can’t take the painting home, they can’t enter again without a new ticket, and while anyone can get a ticket it is you who decides to whom you want to sell tickets and which sections of the museum are accessible.

The ticket is just an example of how access can be controlled. The actions that are allowed can vary. Maybe phones aren’t allowed, so no pictures can be taken of the paintings.

OAuth does the same by the means of tokens in the online world.

Auth is one tricky pony and usually SWEs don’t try to play around much with it because 99% of the time it can’t be tested locally and if it breaks ALL traffic to your service is affected. It has a notorious reputation in the tech world. So no team will change their auth policies just for fun. And it is not often you get to work on it unless you are in a dedicated team.

Basic Components in OAuth

An Example

You [Client] are at a hotel reception and trying to check-in to your beautiful room [Resource Server]. The receptionist [Authorization Server] asks for some valid documents for verifying your identity. (Note: This part is Authentication, not Authorisation) Then the receptionist checks the hotel system [ ~ Resource Owner] to see if you have a booking with them [Authorisation!!]. If you do, they give you the room keys [Token that give you access to the resource for a fixed amount of time]. Then you use the keys to access your room. Once your stay is over [token is expired], you need to do the whole dance again to get access to the resource. The access was scoped because you could access only your room. But it could be different for hotel employees, who can access multiple rooms with the master key. Another example could be those all inclusive hotels where the colour code of the band determines what privileges you get. Maybe only the bar and no spa access or something like that.

Tl;dr - The resource owner (hotel) was able to delegate access for a certain resource (room) to the client (you). The access was scoped because there were limits to what you can do based on your token.

Informal definitions

• Client: Wants access to a certain resource.
• Resource Owner: Indirectly/directly owns and controls access to the resource.
• Authorisation Server: Checks if the request has valid scopes to access the resources in the request. So scopes can change based on the type of request. Get request will require only read access while an Update request might require read/write access. Usually(almost always) applications have a separate service that performs these checks and aren’t coupled with the application service that contains the business logic.
• Scope: Constraints what access a user is privileged to have for a certain resource.
• Token: Contains scope and identity information that a client has/wants to use. Obtained through various OAuth grant types.

There are different types of tokens and grants (steps to fetch tokens/how tokens are granted) to support different kinds of authorisation flows. These are the most popular ones in a complex flow:

• Access tokens: Allows access to a resource for a fixed(short) time. A popular sub type is a bearer token that allows access to whoever has the token (with some extra check for security obviously).
• Refresh tokens: If application needs to perform an action in the future, getting an access token is of no use as it will simply expire. You can’t ask for a fresh token from the user right before performing the action, but you can get a refresh token from the user instead during the interaction. Later when you need to perform the action, you can exchange the refresh token for an access one.

The token choice and how it is obtained depends a lot on the kind of flow we have — is it user initiated, after how long does the service need to perform the action etc.

In future posts I will break down some popular auth flows we use frequently such as log in, log in with <some third party email account>, machine to machine calls and more.

More Resources

• API Keys
• OAuth

Note

This article contains my notes from my initial reading about privacy preserving ML for a hackathon project some 2y ago (so doesn’t cover the latest state) and some added context why the topic is relevant and its impact.

Introduction

Remember in the 90s (or was it 00s?), when the Internet was the latest buzz. Everyone was super excited about building the next big thing on the Internet, and for the longest time nobody paid attention to security. It was a good invention , but once they nailed the security aspect or at least began their attempts, the Internet truly flourished and became the magical, addictive, ubiquitous and larger than life entity we all know, love and sometimes hate! The Internet is now leveraged for services ranging from online banking, stock trading to retailing among many others that would have been unimaginable without security.

I believe we are in a similar phase with ML. Yes, I’m envious too when an AI draws/writes better content than I do, but there is plenty more possible when we can ensure security and privacy in its development process.

Security Vs Privacy — They are NOT the same!

Security is about ensuring only authorised people have access to something, while privacy has more to do with who is authorised. You cannot have privacy without security, but the other way around is possible.

Think of it this way, a hotel room is secure — only people with the key can enter it. But it is not private — any hotel staff with the master key can also enter it, without your knowledge/consent.

Meanwhile, your house is secure and private because you own the keys and control its distribution as well.

Let’s try to see what the current ML scenario looks like, are we secure but lack privacy, are we both, or are we neither?

ML 2020 — An Analysis

Most ML models are trained on a publicly available, unencrypted, and large datasets. The publicly available unencrypted data is accessible to almost anybody, hence it is neither secure nor private.

The training is followed by fine-tuning on a downstream task, the dataset used here can be public or private, depending on the nature of downstream applications and trainer’s discretion, but it has to be unencrypted. Again, due to the lack of encryption, this is potentially un-secure. At the very least, people who are training the model will have eyes on access to the data.

How privacy will benefit ML?

An ML model’s performance is majorly driven by the data it is trained on. The availability of different kinds of datasets varies substantially depending on the quality and domain of data one has access to. Most commonly available datasets contain trivial information. These can be very useful to comprehend the basics of ML but can seldom be used directly to solve real problems afflicting real people. Cute dogs and cats can only save the world to an extent.

If you were to set out to solve a novel and impactful problem, the first hurdle you’ll most likely face is collecting relevant data. Not only you will need to find people/organisations in possession of such data, but also need access to it in an unencrypted state. *legal stuff, better lawyer up!*

ML is, at its core, a way of pattern matching. In many domains, that can benefit from ML, privacy is of utmost importance. Example: Matching early/rare symptoms with correct diagnosis, improving the quality of lifestyle and health research or improved personalised recommendations not as a marketing strategy but as a way to tackle over-consumerism etc. Getting access to such data is a tedious job and rightfully so, it is indeed very personal and critical information and can easily be misused and abused. This results in a major bottleneck and deters development of many real-life applications from reaping the benefits of the advances in ML. There is little use of those State-Of-The-Art results if we can’t use them to solve real problems.

Doing it like the Internet <Ctrl + C && Ctrl +V>

It is evident that this is not the first time in history where concern for privacy is restricting development. Not so long ago, many naysayers believed, the Internet, will never take off and now it is IMPOSSIBLE to imagine a world without it. But it clearly did, you are reading this right now. So can we do the same for ML?

There are plenty of exchanges happening all over the Internet that deal with sensitive information — passwords, bank details, medical information, photographs, official documents you name it and it is on the internet i.e. potentially available to the prying eyes. But it is not a concern one might expect it to be, things can be available online and still be secure and private, only you and the people you authorise are able to access it. Why can’t we do the same for ML? Less eyes on data would mean exposure of private information only to trusted individuals. One can work with that, or can they?

Only a few chosen individuals/groups get “eyes-on” access. This could work but this will, intentionally or unintentionally, hamper progress in a totally different way by creating an uneven playing field. Who gets access to data? How to ensure an unbiased distribution? What does the screening process to make such a discussion looks like? It is too much power for a single authority because the last thing we need are more prejudices and barriers to entry to this industry (as if the existing educational/experience/financial/legal requirements aren’t discouraging enough).

Privacy Preserving ML

Privacy in ML is not completely unheard of, it is not the most lucrative area of research at the moment, but it is starting to grow. It is not in a place to compete with the “State of the Arts” yet, but some great progress have been made. It allows model trainers to develop model while keeping privacy of the data owners in mind. Here are a few ways on how this is done:

Remote Execution/Federated Learning

There are two parties in an exchange, the model owner and the data owner. Currently, data owner has to trust before sharing the data with the model owner. Once the data is with the model owner you HAVE to, you really can’t do much about it, trust them to do the right thing. What if there is a way to train a model without explicitly handing them the data?

This is what remote execution allows. Instead of you sharing your data, the model owner shares the model with various data owners. The model trains on the data, possibly in the data owner’s machine and the updated model (think of updated weights after an epoch) is returned to the model owner. This in some way distributes the trust between both data and model owner.

The data never leaves participants’ device and the ML models of the world can still train on, sounds like a win-win. The data didn’t leave, but some information it held did. This is alright and expected because that is the point of ML model — to extract information from data. The real question is your privacy preserved in this exchange?

The answer is no. Even if the data is securely with you and the eyes of model owners never really saw it, they can in some rare cases deduce some aspects of the data, even if we make the data owner anonymous. If it sounds far-fetched, read about how people de-anonymized data by correlating information from two different datasets.
The main concern (ignoring the combining of datasets for now) is that if the model learns a new behaviour after training on data of user X, then model owners can conclude that user X’s data must have given that information. Simplified example: Model learns how to identify a new species of dog after User X, then model owners can conclude that User X must own a dog of that species. This may not seem like that big of a con in this example, but the whole point of doing this exercise is to make access, to sensitive and personal data, accessible. Also the user still need to trust the model owner to do the right thing, including not just copying the data in the name of training. And the model owner needs to trust the data owner that they simply won’t copy the model or tamper with it.

Federated learning is similar to remote execution. In federated learning, the computations are done on remote devices of the data owners and the results are uploaded to the cloud where multiple such results are combined to update the global model. The minor difference I have noticed based on what I have read is that in federated learning, the results will be uploaded whenever available to the cloud, it is similar to pub-sub model in some ways, but in case of remote execution, it is more driven by the model owners, they will reach out to data owners when they need it, and not listen for updates all the time. It kind of makes sense because the data owner is interested in niche data eg: data about cancer and everything and anything medical.

Differential Privacy*

The above mentioned con can be overcome by using differential privacy in conjunction of remote execution. In differential privacy, in intellectual terms, we create an upper bound on the statistical uniqueness of the dataset aka privacy budget. In layman terms, we add some good old noise. So the model owner can never be 100% sure, in cases such as the one mentioned above, that User X has a dog of the newly learnt species, because it could have been due to noise.

From what I understand, this budget not only limited to per query but to the overall dataset as well. So you cannot query it multiple times in hopes of recreating the OG set. Example: If you query the same user 10 times and notice that 8/10 times you saw similar results, and hence you can deduce the responses that are noise aren’t. Well this won’t work because of the limit on overall dataset as well. How it ensures that is a topic for a different blog.

If you are feeling a little sour about the noise being added, as it will reduce the quality of your results, don’t. A little noise in datasets is encouraged because it prevents the ML model from over-fitting. Better generalisation is more likely to give better results on test data, or when we actually use the model in real life applications.

It is not always practical to be the owner of your own data. For both the data owner and model owner, reaching out to/being reached out by large numbers of users is impractical and honestly annoying. Both parties need to check if they can trust each other and blah blah. Plus how does one de-annonymise it if you are reaching out to individuals?

Secure Multi-Party Computation

As the name suggests (that’s why you name things) it allows you to securely (using encryption) distribute the data across multiple parties (better anonymisation) and still allows the training computation to occur.

You basically take data and divide it into smaller chunks and encrypt it. Each chunk is “owned” by a different individual who, for obvious reasons cannot decrypt it. When a model owner needs to train their model, it asks all chunk holders to send data to a remote machine, the model is sent to that remote machine and it trains of the data. Or maybe the owner sends the model to train on all share-holders of the chunks. No decryption is required for any step in the process. (This is a rough overview of what happens, actual details of various implementation may vary)

The individual parties cannot decrypt data on their own. For additional security, the model owners can also encrypt their models. So both, the data owners and model owners can feel lot more comfortable during collaborations. You cannot do all kinds of computations in an encrypted state but most one the basic ones. So the fancy transformers and all that can’t simply adapt to a privacy preserving ML way of training.

Conclusion

Privacy preserving ML is an exciting area of research and is in its early phase. The solutions we have might not give the results we want to/or expect from ML models at this point, but the area has lot more to offer and will improve tremendously in the years to come. (I’m sure it already has in the 2y I wrote this)

Resources

• Privacy Preserving AI (Andrew Trask) | MIT Deep Learning Series
• OpenMined Blog

Obviously there are more caveats and intricacies involved here and this is merely a simplified overview of all the sub-topics mention. If you want a follow up on any of them or explore any other concept in this space, please feel free to reach out to me. :D

*Differential Privacy is a very interesting topic on its own and here I have only covered of what is does on a high level and not how. Most of its claims have a mathematical proof, if you want me to explore it in depth, please reach out.

Intro to Privacy Preserving ML was originally published in Analytics Vidhya on Medium, where people are continuing the conversation by highlighting and responding to this story.

Disclaimer: I’m not dull enough to suppose that the entirety of software engineering wisdom can be distilled down to five or even ten points. But one needs to start somewhere, right? These action items will help you stay afloat while you figure out your master plan.

So if you are a college graduate starting out soon, or someone making a career switch, this would be a good place to start. If you have been in this industry for a while, this might not be for you. But don’t leave the page just yet, why don’t you share some of your wisdom in the comments? ;)

Action Item #1: Be curious. 🧐

• Ask questions about the code, system architecture, team culture, team practices, the deployment pipeline, testing support, etc.
• Don’t know whom to ask? I suggest your buddy or mentor. If you don’t have one of those, ask your manager for one of those.

Action Item #2: Let the code talk. 👩‍💻

• Write thoroughly tested code. Everyone prefers a reliable change over a quick one.
• Take time to understand the code and try to reuse code whenever possible and keep it clean. As exciting/challenging writing code from scratch sounds it is not what you should do. If re-usability is possible — even if it requires some refactoring — REUSE it. You want to treat your code base like planet earth and we all know where single use objects (pun intended.) lead to.

Friendly Tip: Do not use this as an excuse and take a week to do something that requires a few hours. Not all tasks assigned to you will be grand enough to pull off this as an excuse.

Action Item #3: Do PR Reviews. 📋

• It is impossible to be involved in everything that is happening, it’s not a single person team for a reason. Coding isn’t the only way to contribute to a products’ development. One of the most valuable way is to review your peers’ PRs. Now this is quite overwhelming for a few of us, *heyyy imposter syndrome, I see you* and you’d be thinking I just got here, how can I tell someone how to something better, but chill out. Start small, it is ok to ask why they did something in a particular way.
• When it comes to your own PR, be as descriptive as possible. Set out the entire context in that description box.

Action Item #4: Use 1:1 to learn and grow. 📈

• Many people believe 1:1s are there for your manager’s benefit and they should run the meeting. But that is the opposite of how it should be. They are there for YOU! Think of them as a default mentoring sessions.
• Use them to make sure to set the expectations right. How do you do that? Well learn what they expect of you in the first place!
• Ask about gaps in your current skill set. Learn how you can increase your impact.

Action Item #5: Take ownership. 🏛️

• As mentioned numerous times before, joining a new team is overwhelming in its own ways and it is only natural to try to learn everything at once. Alas, it is not humanly possible for most of us to do so. A better way to strategize would be to pick a small area and building your expertise around that.
• Next time there is a discussion around any of those areas, make sure to participate and contribute in whatever way possible. Lo and behold, you are an owner of an area.

Bonus Tip: Know Git.

I have previously written about it, so I will keep it short and link it here.

Learning Git in Under 8 minutes!

Now What? 🤔

Okay, you have been around for a while and already doing all the aforementioned things, what else can you do? What’s next?

One would think the internet is the go-to place for people like us to share their knowledge but surprisingly so much of it is buried in good old fashioned books.

Here are a few I recommend:

1. You Had Me at “Hello, World”: Mentoring Sessions with Industry Leaders at Microsoft, Facebook, Google, Amazon, Zynga and more! by Dona Sarkar
2. Refactoring: Improving the Design of Existing Code by Martin Fowler — if not the whole thing, read chapter 3. I might make a post about it, so watch out!
3. Head First Design Patterns by Eric Freeman — I have read partially and it has been good so far. By partially I meant one chapter.

Few that are on my reading list:

1. The Pragmatic Programmer: From Journeyman to Master by Andy Hunt
2. Clean Code: A Handbook of Agile Software Craftsmanship by Robert C. Martin

If you even slightly follow the NLP world, or even the ML news you have most likely come across Google’s BERT model or one of its relatives. If you haven’t and still somehow have stumbled across this article, let me have the honor of introducing you to BERT — the powerful NLP beast.

What is BERT?

BERT stands for Bidirectional Encoder Representations from Transformers and is a language representation model by Google. It uses two steps, pre-training and fine-tuning, to create state-of-the-art models for a wide range of tasks.

Its distinctive feature is the unified architecture across different downstream tasks — what these are, we will discuss soon. That means that the same pre-trained model can be fine-tuned for a variety of final tasks that might not be similar to the task model was trained on and give close to state-of-the-art results.

As you can see, we first train the model on the pre-training tasks simultaneously. Once the pre-training is complete, the same model can be fine-tuned for a variety of downstream tasks. Note that a separate model is fine-tuned for a specific downstream task. So single pre-trained models can generate multiple downstream task specific models post fine tuning.

BERT Architecture

Simply put, it is a stack of Transformer’s Encoder. You can read about Transformers in details in my previous article. Or if you have some faint idea about it already, check out this absolutely bomb 3D diagram of the Encoder block used in BERT. Seriously you can’t miss this!

Transformers

Now let’s look at some numbers that none of us will ever remember, but our understanding will feel incomplete without them, so here goes nothing:

L = Number of layers (i.e., #Transformer encoder blocks in the stack).
H = Hidden size (i.e. the size of q, k and v vectors).
A = Number of attention heads.

• BERT Base: L=12, H=768, A=12.
  Total Parameters=110M!
• BERT Large: L=24, H=1024, A=16.
  Total Parameters=340M!!

What makes it Bidirectional?

We usually create a language model by training it on some unrelated task but tasks that help develop a contextual understanding of words in a model. More often than not such tasks involve predicting the next word or words in close vicinity of each other. Such training methods can’t be extended and used for bidirectional models because it would allow each word to indirectly “see itself” — when you would approach the same sentence again but from opposite direction, you kind of already know what to expect. A case of data leakage.

In such a situation, model could trivially predict the target word. Additionally, we can’t guarantee that the model, if completely trained, has learnt the contextual meaning of the words to some extent and not just focused on optimizing the trivial predictions.

So how does BERT manage to pre-train bidirectionally? It does so by using a procedure called Masked LM. More details on it later, so read on, my friend.

Pre-training BERT

The BERT model is trained on the following two unsupervised tasks.

1. Masked Language Model (MLM)

This task enables the deep bidirectional learning aspect of the model. In this task, some percentage of the input tokens are masked (Replaced with [MASK] token) at random and the model tries to predict these masked tokens — not the entire input sequence. The predicted tokens from the model are then fed into an output softmax over the vocabulary to get the final output words.

This, however creates a mismatch between the pre-training and fine-tuning tasks because the latter does not involve predicting masked words in most of the downstream tasks. This is mitigated by a subtle twist in how we mask the input tokens.

Approximately 15% of the words are masked while training, but all of the masked words are not replaced by the [MASK] token.

• 80% of the time with [MASK] tokens.
• 10% of the time with a random tokens.
• 10% of the time with the unchanged input tokens that were being masked.

2. Next Sentence Prediction (NSP)

The LM doesn’t directly capture the relationship between two sentences which is relevant in many downstream tasks such as Question Answering (QA) and Natural Language Inference (NLI). The model is taught sentence relationships by training on binarized NSP task.

In this task, two sentences — A and B — are chosen for pre-training.

• 50% of the time B is the actual next sentence that follows A.
• 50% of the time B is a random sentence from the corpus.

Training — Inputs and Outputs.

The model is trained on both above mentioned tasks simultaneously. This is made possible by clever usage of inputs and outputs.

Inputs

The model needs to take input for both a single sentence or two sentences packed together unambiguously in one token sequence. Authors note that a “sentence” can be an arbitrary span of contiguous text, rather than an actual linguistic sentence. A [SEP] token is used to separate two sentences as well as a using a learnt segment embedding indicating a token as a part of segment A or B.

Problem #1: All the inputs are fed in one step — as opposed to RNNs in which inputs are fed sequentially, the model is not able to preserve the ordering of the input tokens. The order of words in every language is significant, both semantically and syntactically.

Problem #2: In order to perform Next Sentence Prediction task properly we need to be able to distinguish between sentences A and B. Fixing the lengths of sentences can be too restrictive and a potential bottleneck for various downstream tasks.

Both of these problems are solved by adding embeddings containing the required information to our original tokens and using the result as the input to our BERT model. The following embeddings are added to token embeddings:

• Segment Embedding: They provide information about the sentence a particular token is a part of.
• Position Embedding: They provide information about the order of words in the input.

Outputs

How does one predict output for two different tasks simultaneously? The answer is by using different FFNN + Softmax layer built on top of output(s) from the last encoder, corresponding to desired input tokens. We will refer to the outputs from last encoder as final states.

The first input token is always a special classification [CLS] token. The final state corresponding to this token is used as the aggregate sequence representation for classification tasks and used for the Next Sentence Prediction where it is fed into a FFNN + Softmax layer that predicts probabilities for the labels “IsNext” or “NotNext”.

The final states corresponding to [MASK] tokens is fed into FFNN+Softmax to predict the next word from our vocabulary.

Fine-tuning BERT

Fine-tuning on various downstream tasks is done by swapping out the appropriate inputs or outputs. In the general run of things, to train task-specific models, we add an extra output layer to existing BERT and fine-tune the resultant model — all parameters, end to end. A positive consequence of adding layers — input/output and not changing the BERT model is that only a minimal number of parameters need to be learned from scratch making the procedure fast, cost and resource efficient.

Just to give you an idea of how fast and efficient it is, the authors claim that all the results in the paper can be replicated in at most 1 hour on a single Cloud TPU, or a few hours on a GPU, starting from the exact same pre-trained model.

In Sentence Pair Classification and Single Sentence Classification, the final state corresponding to [CLS] token is used as input for the additional layers that makes the prediction.

In QA tasks, a start (S) and an end (E) vector are introduced during fine tuning. The question is fed as sentence A and the answer as sentence B. The probability of word i being the start of the answer span is computed as a dot product between Ti (final state corresponding to ith input token) and S (start vector) followed by a softmax over all of the words in the paragraph. A similar method is used for end span.
The score of a candidate span from position i to position j is defined as S·Ti + E·Tj, and the maximum scoring span where j ≥ i is used as a prediction

GPT — The distant cousin

Is BERT the only model that is producing these ground breaking results? No. Another model by OpenAI, called GPT has been making quite the buzz on internet.

But what many people don’t realize that these two models have something in common, that is both these model reuse a Transformer component. As stated earlier BERT stacks the encoder part of the Transformer as its building block. Meanwhile, GPT uses the decoder part of the Transformer as its building block.

Note that the bidirectional connections in BERT due to encoder’s bidirectional self-attention. Meanwhile, the connections in GPT are only in a single direction, from left-to-right, due to decoder design to prevent looking at future predictions — refer Transformers for more info.

The BERT Family

It wouldn’t be 21st century if we didn’t take something that works well and try to recreate or modify it. BERT architecture is no different. These are some of the most popular variants of it:

• ALBERT by Google and more — This paper describes parameter reduction techniques to lower memory reduction and increase the training speed of BERT models.
• RoBERTa by Facebook — This paper for FAIR believes the original BERT models were under-trained and shows with more training/tuning it can outperform the initial results.
• ERNIE: Enhanced Representation through Knowledge Integration by Baidu — It is inspired by the masking strategy of BERT and learns language representation enhanced by knowledge masking strategies, which includes entity-level masking and phrase-level masking.
• DistilBERT — Smaller BERT using model distillation from Huggingface.

You can check out more BERT inspired models at the GLUE Leaderboard.

Conclusion

1. BERT is a stacked Transformer’s Encoder model.
2. It has two phases — pre-training and fine-tuning.
3. Pre-training is computationally and time intensive.
4. It is, however, independent of the task it finally does, so same pre-trained model can be used for a lot of tasks.
5. GPT is not that different from BERT and is a stacked Transformer’s decoder model.
6. There are many variants of BERT out there.

References + Recommended Reads

• Transformers — if you want more in-depth knowledge on aforementioned encoder/decoder architecture.
• The paper — it is easy to read, and they also elaborate on the practical details a bit. Worth a read.
• Jay Alammar’s Blog.
• Official GitHub repo.
• More BERT Models.

I’m glad you made it till the end of this article. 🎉
I hope your reading experience was as enriching as the one I had writing this. 💖

Do check out my other articles here.

If you want to reach out to me, my medium of choice would be Twitter.

Keeping up with the BERTs was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

In times dim and distant, I asked followers on my Instagram account to share “Books that they couldn’t forget!”, and they didn’t disappoint. The past me was lazy and compiled them in a Google Doc, but here goes nothing!

Disclaimers:

1. I haven’t read most of these books.
2. I also haven’t dared to sort them into genres owing to my unawareness of their content.
3. It is an eternal WIP and I would be more than happy to add your unforgettable books to this list. I would also like to mention your name along with the recommendation for tracking purposes — only if you are ok with that.
4. The post is hastily put together and would improve considerably — both in terms of visuals and formatting — in future.

The Book Recommendations — in no particular order:

• Shoe Dog by Phil Knight <- read it and it is good and kinda motivates you, if you are struggling to “Just Do It” this might be the push you need.
• Factfulness: Ten Reasons We’re Wrong About the World — and Why Things Are Better Than You Think by Hans Rosling, Ola Rosling, Anna Rosling Rönnlund <- could have used a shorter title, haven’t read it to have an opinion beyond this.
• 21 Lessons for the 21st Century by Yuval Noah Harari
• Sapiens: A Brief History of Humankind by Yuval Noah Harari

• 1984 by George Orwell <- Makes you think a lot and is not just about totalitarian governments. I rather thought that was just a small bit of it.
• The Subtle Art of Not Giving a F*#K by Mark Manson
• A Thousand Splendid Suns by Khaled Hosseini <- Really emotional and moving. It is about a women in Afghanistan and her courage and sacrifice. Don’t want to spoil it much but emotions were felt.
• The Kite Runner by Khaled Hosseni <- Similar scene (Afghanistan under Taliban) as the above but a very different story. Reading both makes you realise how a situation impacts everyone differently.
• Into Thin Air by Jon Krakauer
• “Surely You’re Joking, Mr. Feynman!” by Richard P. Feynman
• How to Get Rich and Retire Early by Raja Sekharan
• Nudge (couldn’t resolve the exact book)
• The Leader Who Had No Title by Robin S. Sharma
• The Checklist Manifesto by Atul Gawande
• A Stranger in the Mirror by Sidney Sheldon
• Flowers for Algernon by Daniel Keyes
• Deep Work by Cal Newport <- Started it and I think it is crucial in the current times, but due to some other priorities couldn’t finish and had to return my copy to the library. But it is quite high in my non fiction TBR list.
• If Tomorrow Comes by Sidney Sheldon
• The Book Thief by Markus Zusak
• Kafka on the Shore by Haruki Murakami
• To Kill A Mockingbird by Harper Lee <- An American classic, views racism from a white kids POV. Though you can find much better reviews online.
• Becoming by Michelle Obama <- Loved it. A strong, ambitious and smart women. Really enjoyed reading it and how she navigates life. Honestly could re-read it!
• When Breath Becomes Air by Paul Kalanithi
• Tuesdays with Morrie by Mitch Albom
• Gone With The Wind by Margaret Mitchell
• The Innocent Man: Murder and Injustice in a Small Town by John Grisham
• Outliers by Adam Grant
• The Perks of Being a Wallflower by Stephen Chbosky
• Blonde Bombshell by Tom Holt

Series

• Harry Potter by JK Rowling <- It is a childhood crush that I read at the cusp of adulthood. It might not be the best/most immersive fantasy but it made me love reading and you can’t deny it feels nice to be a part of the Potter-verse, with the memes and references.
• Warbreaker by Brandon Sanderson <- I have read Mistborn trilogy and really enjoyed it, from the reviews I have found it is supposedly even better.
• The Belgariad series by David Eddings
• The Clifton Chronicles by Jeffrey Archer <- I have read a few of his books and they are good and but there are usually too many in a series for me to commit to.
• Millennium by Steig larsson <- You might know its first book, the girl with the dragon tattoo.

Thank you everyone!

Some bonus recommendations from my side — because ain’t no thing as too many recommendations:

“Becoming is better than being”

• Mindset: The New Psychology of Success by Carol C. Dweck
  The idea might get a little repetitive for people by the end but basic premise is sound.

“It was when he tried to talk about ‘the boat’ that his words began to falter and tears welled up in his eyes…Finally, watching Joe struggle for composure over and over, I realised that ‘the boat’ was something more than just the shell or its crew. To Joe, it encompassed but transcended both — it was something mysterious and almost beyond definition. It was a shared experience — a singular thing that had unfolded in a golden sliver of time long gone, when nine good-hearted young men strove together, pulled together as one, gave everything they had for one another, bound together forever by pride and respect and love. Joe was crying, at least in part, for the loss of that vanished moment but much more, I think, for the sheer beauty of it.”

• The Boys in the Boat by Daniel James Brown <- never thought I would care much about rowing but here we are, that’s the power of good story telling.

“Happiness comes from moving toward something. When you run away, ofttimes you bring your misery with you.”

• The Riyria Revelations by Michael J. Sullivan <- the richer fantasy I was talking about earlier. This is a good example.

Want to add your books to this list?

Just reach out to me anywhere or leave a note on this post, and I will add your book recommendations to this list. :)

I‘m glad you made it till the end of this article. 🎉
If you liked this article, do share it with your friends/family or leave a few claps. 💖

Do check out my other articles here.

If you want to reach out to me, my medium of choice would be Twitter.

No, this article is not about the American sci-fi action movie series — no Optimus Prime here. It is also not about the electrical device that is used to transfer energy from one electrical circuit to another. What is this about then, you ask?

It is about the one in the most sci-fi fields of all time, Artificial Intelligence — Natural Language Processing in particular and it is pretty optimal at transferring information and primely used. (See what I did there. :P)

This post is based on the paper: Attention is All You Need. P.S. the authors were not kidding when they chose that title because you will need all the attention at your disposal for this one. But don’t let that scare you, it is SO SO worth it!!

What is a Transformer?

The Transformer in NLP is a novel architecture that aims to solve sequence-to-sequence tasks while handling long-range dependencies with ease. It relies entirely on self-attention to compute representations of its input and output WITHOUT using sequence-aligned RNNs or convolution. 🤯

If you recall my previous post, Understanding Attention In Deep Learning, we discussed how and why many models fell short when it came to handling long-range dependencies. The concept of attention somewhat allowed us to overcome that problem and now in Transformers we will build on top of attention and unleash its full potential.

Understanding Attention In Deep Learning

Few things to know before diving into Transformers

Self-Attention

Let us start with revisiting what attention is in the NLP universe? Understanding Attention In Deep Learning. (I apologize for these blatant self-advertisements, but seriously give it a read. It will help you under Transformers much better. I promise.)

Attention allowed us to focus on parts of our input sequence while we predicted our output sequence. If our model predicted the word “rouge” [French translation for the color red], we are very likely to find a high weight-age for the word “red” in our input sequence. So attention, in a way, allowed us to map some connection/correlation between the input word “rouge” and the output word “red”.

Self attention, sometimes called intra-attention is an attention mechanism relating different positions of a single sequence in order to compute a representation of the sequence.

In simpler terms, self attention helps us create similar connections but within the same sentence. Look at the following example:

“I poured water from the bottle into the cup until it was full.”
it => cup

“I poured water from the bottle into the cup until it was empty.”
it=> bottle

By changing one word “full” — > “empty” the reference object for “it” changed. If we are translating such a sentence, we will want to know the word “it” refers to.

The three kinds of Attention possible in a model:

1. Encoder-Decoder Attention: Attention between the input sequence and the output sequence.
2. Self attention in the input sequence: Attends to all the words in the input sequence.
3. Self attention in the output sequence: One thing we should be wary of here is that the scope of self attention is limited to the words that occur before a given word. This prevents any information leaks during the training of the model. This is done by masking the words that occur after it for each step. So for step 1, only the first word of the output sequence is NOT masked, for step 2, the first two words are NOT masked and so on.

Keys, Values, and Queries:

The three random words I just threw at you in this heading are vectors created as abstractions are useful for calculating self attention, more details on each below. These are calculated by multiplying your input vector(X) with weight matrices that are learnt while training.

• Query Vector: q= X * Wq. Think of this as the current word.
• Key Vector: k= X * Wk. Think of this as an indexing mechanism for Value vector. Similar to how we have key-value pairs in hash maps, where keys are used to uniquely index the values.
• Value Vector: v= X * Wv. Think of this as the information in the input word.

What we want to do is take query q and find the most similar key k, by doing a dot product for q and k. The closest query-key product will have the highest value, followed by a softmax that will drive the q.k with smaller values close to 0 and q.k with larger values towards 1. This softmax distribution is multiplied with v. The value vectors multiplied with ~1 will get more attention while the ones ~0 will get less. The sizes of these q, k and v vectors are referred to as “hidden size” by various implementations.

All these matrices Wq, Wk and Wv are learnt while being jointly trained during the model training.

Calculating Self attention from q, k and v:

If we are calculating self attention for #i input word,

• Step 1: Multiply qᵢ by the kⱼ key vector of word.
• Step 2: Then divide this product by the square root of the dimension of key vector.
  This step is done for better gradient flow which is specially important in cases when the value of the dot product in previous step is too big. As using them directly might push the softmax into regions with very little gradient flow.
• Step 3: Once we have scores for all js, we pass these through a softmax. We get normalized value for each j.
• Step 4: Multiply softmax scores for each j with vᵢ vector.
  The idea/purpose here is, very similar attention, to keep preserve only the values v of the input word(s) we want to focus on by multiplying them with high probability scores from softmax ~1, and remove the rest by driving them towards 0, i.e. making them very small by multiplying them with the low probability scores ~0 from softmax.

The Transformer

⚠️ A word of caution: the contents of this image may appear exponentially more complicated than they are. We will break this scary beast down into small baby beasts and it will all make sense. (I promise #2)

Beast #1: Encoder-Decoder stacks

Encoder: The encoder maps an input sequence of symbol representations (x₁, …, xₙ) to a sequence of representations z = (z₁, …, zₙ). Think of them as the outputs from self attention with some post-processing.

Each encoder has two sub-layers.

1. A multi-head self attention mechanism on the input vectors (Think parallelized and efficient sibling of self attention).
2. A simple, position-wise fully connected feed-forward network (Think post-processing).

Check out this absolute bomb 3D diagram of the Encoder block used in BERT. Seriously you can’t miss this!!! It is like a whole new level of understanding.

Decoder: Given z, the decoder then generates an output sequence (y₁, …, yₘ) of symbols one element at a time.

Each decoder has three sub-layers.

1. A masked multi-head self attention mechanism on the output vectors of the previous iteration.
2. A multi-head attention mechanism on the output from encoder and masked multi-headed attention in decoder.
3. A simple, position-wise fully connected feed-forward network (think post-processing).

A few additional points:

• In the original paper, 6 layers were present in the encoder stack (2 sub-layer version) and 6 in the decoder stack (3 sub-layer version).
• All sub-layers in the model, as well as the embedding layers, produce outputs of the same dimension. This is done to facilitate the residual connections.

Beast #2 Inside Encoder-Decoder stacks — Multi-Head Attention:

We just noted that the output of each sub-layer needs to be of the same dimension which is 512 in our paper.
=> zᵢ needs to be of 512 dimensions.
=> vᵢ needs to be of 512 dimensions as zᵢ are just sort of weighted sums of vᵢs.

Additionally, we want to allow the model to focus on different positions is by calculating self attention multiple times with different sets of q, k and v vectors, then take an average of all those outputs to get our final z.

So instead of dealing with these humongous vectors and averaging multiple outputs, we reduce the size of our k,q and v vectors to some smaller dimension — reduces size of Wq, Wk, and Wv matrices as well. We keep the multiple sets (h) of k,q and v and refer to each set as an “attention head”, hence the name multi-headed attention. And lastly, instead of averaging to get final z, we concatenate them.

The size of the concatenated vector will be too large to be fed to the next sub-layer, so we scale it down by multiplying it with another learnt matrix Wo.

Multiple attention heads allowed the model to jointly attend to information from different representation sub-spaces at different positions which was inhibited by averaging in a single attention head.

Beast #3— Input and Output Pre-processing:

The input words are represented using some form of embedding. This is done for both encoder and decoder.

Word embedding on their own lack any positional information which is achieved in RNNs by virtue of their sequential nature. Meanwhile in self-attention, due to softmax, any such positional information is lost.

To preserve the positional information, the transformer injects a vector to individual input embeddings (could be using word embeddings for corresponding to the input words). These vectors follow a specific periodic function (Example: combination of various sines/cosines having different frequency, in short not in sync with each other) that the model learns and is able to determine the position of individual word wrt each other based on the values .

This injected vector is called “positional encoding” and are added to the input embeddings at the bottoms of both encoder and decoder stacks.

Beast #4 — Decoder stack: Revisited

The output of the decoder stack at each step is fed back to the decoder in the next time step — pretty similar to how outputs from previous steps in RNNs were used as next hidden states. And just as we did with the encoder inputs, we embed and add positional encoding to those decoder inputs to preserve the position of each word. This positional encoding + word embedding combo is then fed into a masked multi-headed self attention.

This self-attention sub-layer in the decoder stack is modified to prevent positions from attending to subsequent positions — you can’t look at future words. This masking ensures that the predictions for position i can depend only on the known outputs at positions less than i.

The outputs from the encoder stack are then used as multiple sets of key vectors k and value vectors v, for the “encoder decoder attention” — shown in green in the diagram — layer. It helps the decoder focus on the contextually relevant parts in the input sequence for that step. (The part similar to global attention vectors.) The q vector comes from the “output self attention” layer.

Once we get the output from the decoder, we do a softmax again to select the final probabilities of words.

Conclusion

Let’s finish with a quick wrap-up revision.

• We started with understanding what self attention is and how to calculate self-attention from these v, k ,q vectors.
• Multi-headed attention is an efficient modification of self attention that uses multiple smaller sets of v, k ,q and concatenates the outputs from each set to get the final z.
• Then we saw how and where the three kinds of self attention are used in the model.
• Followed by the pre-processing done on the inputs for the encoder and decoder stacks.

References + Recommended Reads

• Understanding Deep Attention in Deep Learning if you faced issues around attention.
• The Illustrated Transformer — Has great visualizations along with the explanations.
• https://www.analyticsvidhya.com/blog/2019/06/understanding-transformers-nlp-state-of-the-art-models/

• YouTube video #1: A great resource to get the model intuition. Specially if you want to learn more about positional encoding.

• YouTube video#2: Talk by Lukasz Kaiser on this paper explaining self attention — . P.S. He is one of the authors for this paper.

I’m glad you made it till the end of this article. 🎉
I hope your reading experience was as enriching as the one I had writing this. 💖

If you liked this article, do check out my other ones here.

If you want to reach out to me, my medium of choice would be Twitter.

Transformers was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

In one of my previous articles, I talk about how attention is one of the most important assets — we as humans — have. How we choose to spend our time and on what we choose to focus on during that time determines the outcome for almost all our endeavors.

In this article, we will discuss how we gave an ML model the ability to focus and the impact it had on its performance.

Why models need to have attention

Let’s go over a task — popularly solved in many NLP models — translation. A word to word translation doesn’t work in most cases as most languages don’t share a common sentence structure. A simple example:

English => French
red => rouge
dress => robe
“red dress” => “robe rouge”
Notice how red is before dress in English but rouge is after robe.

The way NLP models usually go about such tasks is by capturing all the information in the input sentence —the details of objects, how objects are related to each other — in an intermediate state and then using this intermediary information and expressing it in the output language. The size of the vector used for this intermediary state i.e. the state capturing all the information from input sequence — before we start decoding the output sequence— is fixed.

The intermediate state plays a paramount role in this entire process. Its ability to remember all the information passed in the input sentence is critical to the quality of decoded output. Whether it is a translation or a QnA task, in which the input is a question and a paragraph and the model needs to predict the answer to that question based on the paragraph or, any other sequence to sequence modeling operation, the intermediary state continues to be the most crucial piece of the puzzle.

It was the best of times, it was the worst of times, it was the age of wisdom, it was the age of foolishness, it was the epoch of belief, it was the epoch of incredulity, it was the season of Light, it was the season of Darkness, it was the spring of hope, it was the winter of despair, we had everything before us, we had nothing before us, we were all going direct to Heaven, we were all going direct the other way — in short, the period was so far like the present period, that some of its noisiest authorities insisted on its being received, for good or for evil, in the superlative degree of comparison only.

- A Tale of Two Cities, Charles Dickens.

Now I ask you to just memorize, not even translate, this sentence after going over it once, from left to right, and I limit the number of words that you can write in your notes. Not so easy, is it?

How about memorizing this sentence about cars brimming with facts that I totally made up? Disclaimer: The numbers and use cases appearing in the following statement are fictitious, any sense they make is purely coincidental.

This car is 2m in height — so lean on my friend, 12m in width — not very hug-able unfortunately, with a 8m wheelbase — whatever use that information is for, a turning radius of just 0.1m — making it easier to turn away from all your problems, a boot-space of 200 litres — for all the luggage you’ll carry for a trip and never use, a ground clearance of 0.25m — in case you ever seek refuge under the car, a 6 cylinder engine with 5 valves — a spec you’ll only ever use while showing off and lastly has a dual overhead camshaft because big cars comes with big words.
-Yours truly :)

Jokes aside, in this case not only you have to remember all the numbers I randomly threw in there, but also the features —shown in bold — it corresponds to. Mess it up at one place and you have got it all wrong.

As evident by now, in cases with very long sentences as input, the intermediate state fails and is not sufficient to capture all the information. Often it will forget the first part by the time it completes processing the whole input. To improve the model’s performance and relieve the intermediate state from being solely responsible for encoding all the information available to the decoder in a fixed length vector and from being a potential bottleneck, we use the concept of attention. With this new approach, the information can be spread throughout the sequence of annotations — encoder hidden states, which can be selectively retrieved by the decoder accordingly.

Attention mechanism in a model

Attention mechanism tries to overcome the information bottleneck of the intermediary state by allowing the decoder model to access all the hidden states, rather than a single vector — aka intermediary state — build out of the encoder’s last hidden state, while predicting each output.

The input to a cell in decoder now gets the following values:

1. The previous hidden state of the decoder model Hₖ-₁.
2. The previous output of decoder model Yₖ-₁.
3. A context vector Cₖ— a weighted sum of all encoder hidden states(hⱼ’s) aka annotations. (New addition)

A few features of Context Vector and Global Alignment Weights

The global alignment weights are important because they tell us which annotations(s) to focus on for the next output. The weights will and should vary in each time steps of the decoder model. They are calculated by using a feed forward neural network.

A few observations worth noting:

• While predicting the next step, weights are high — shown in white — only for a few words at a time. No more than 3–4 words have high attention for a given output word.
• The attention doesn’t linger for very long on a particular input word across time steps. That is, just because the weight was high in the previous step, doesn’t imply it would be in the subsequent steps.
• Sometimes attention returns to an input word — look at the word “que” in output and how a part of its attention is on the first word “It”.

The flow while predicting — during testing/validation of the model

The sequence of steps is as follows:

ENCODER MODEL:

• Step 1: Run the input sequence to get all the hidden states and calculate the intermediary state.

DECODER MODEL:

• Step 2: Get the global alignment weights ⍺ₖ ⱼ from the attention layer neural network for kᵗʰ step.
• Step 3: Calculate the context vector by multiplying the ⍺ₖ ⱼ with hⱼ for j in range 0 to t, where t=steps in encoder model.

• Step 4: Take the previous hidden state of the decoder, Hₖ-₁,the context vector Cₖ, and the previous output Yₖ-₁ to get the next hidden state of the decoder Hₖ. Predict Yₖ from Hₖ.
• Step 5: Repeat 2, 3 and 4 till model predicts end token.

How to get the Global Alignment Weights

We know we use a feed forward neural network that outputs these global alignment weights ⍺ₖ ⱼ. The purpose of these weights is to reflect the importance of each annotation hⱼ w.r.t. the previous hidden state in deciding the next state Hₖ. This, in a way, allows the model to decide which parts of the input to attend to. The bigger the weight, the more attention it gets. So the next question is, what are its inputs, and how do we train it?

The Inputs

We input both decoder hidden state and the annotations in our neural network to predict a single value — eₖ ⱼ as the authors of the paper liked to call it, the “associated energy”— signifying the importance of the annotations in next decoder step Hₖ. We repeat this process for all annotations. Once, we have associated energies corresponding to all annotations, we do a softmax to obtain the global alignment weights ⍺ₖ ⱼ.

Step 2, mentioned before, can now be broken down as follows:

• Step 2.a: Calculate eₖ ⱼ where j = 0 to t, t = time steps in encoder model. The decoder hidden state will be the same for all j and will be Hₖ-₁.

• Step 2.b: Once we have all eₖⱼ, do a Softmax to get ⍺ₖ ⱼ.

Training/Loss Calculation

The alignment model directly computes a soft alignment — considers all inputs, which allows the gradient of the loss function — calculated for final outputs of the entire sequence to sequence model — to be back-propagated through. This gradient is used to train the alignment model as well as the whole translation model jointly.

Let ⍺ᵢ ⱼ be a probability that the target word Yᵢ is translated from a source word Xⱼ . Then, the i-th context vector Cᵢ is the expected annotation over all the annotations with probabilities ⍺ᵢ ⱼ . When loss at each time step is back-propagated, we calculate the gradient for all three inputs — previous hidden state, the previous output and the context vector. (If this is a little confusing for you, please read more about back-propagation here) All the gradients flowing back in a time step shall be added together before we calculate the gradients for its inputs.

The gradient at each time step for Cₖ is used as the loss for the feed forward neural network we use to predict global alignment weights.

Impact on Performance

• The model with attention mechanism was able to outperform the conventional encoder–decoder model significantly, regardless of the sentence length and that it is much more robust to the length of a source sentence.
• It was also able to correctly align each target word with the relevant words, or their annotations, in the source sentence as it generated a correct translation.
• It enabled further development in the field by paving the road for Transformers and SOTA models like Google’s BERT — which inspired RoBERTa by Facebook, AzureML-BERT by Microsoft and many more.

Conclusion

1. In our current approach with RNNs, the intermediary state act as a bottleneck for performance.
2. Attention can solve this problem by looking at each individual input state while predicting next output hidden state.
3. The mathematics for calculating attention.
4. Integration with RNNs based models.
5. Performance of RNN + attention models.

Follow Up Read:

• Transformers
• Keeping up with the BERTs

If you liked this article and want to explore more about Transformer and BERT (out now), make sure to check out my articles on the same. 😄✌️

References + Recommended Reads

• Original Paper.
• Intuitive Understanding Of Attention Mechanism In Deep Learning by Harshall Lamba.
• A Comprehensive Guide to Attention Mechanism in Deep Learning for Everyone by Analytics Vidhya.
• https://github.com/tensorflow/tensorflow/blob/master/tensorflow/contrib/eager/python/examples/nmt_with_attention/nmt_with_attention.ipynb (TensorFlow Implementation available on their official website as a tutorial)

Other articles by me that I think you would enjoy😄

• Yes, you should listen to Andrej Karpathy, and understand Back propagation
• Evaluation of an NLP model — latest benchmarks
• Machine Learning in Computational Fluid Dynamics
• Keeping Up With The BERTs — to understand how BERT leveraged attention and created a bidirectional model.

I‘m glad you made it till the end of this article. 🎉
I hope your reading experience was as enriching as the one I had writing this.💖

Do check out my other articles here. 🔍

If you want to reach out to me, my medium of choice would be Twitter. 📬

Understanding Attention In Deep Learning was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.