liveBook · Manning

Greedy algorithm

As explained in Deep Learning with Python, Third Edition

A decoding strategy that selects the most likely predicted token at each step without considering future alternatives.

At each generation step, greedy decoding chooses the token with the highest predicted probability. It is straightforward, but repeatedly choosing the most likely token can trap generation in high-probability loops. section 16.2.4

def greedy_search(preds):
    return ops.argmax(preds)

compiled_generate(prompt, greedy_search)

Use argmax to select the most likely token, then pass that strategy into the generation loop. section 16.2.4

Greedy decoding does not consider future alternatives. Random sampling and top-K sampling offer other ways to choose tokens from the model’s predictions. section 16.2.4 section 16.6

How Deep Learning with Python, Third Edition covers it

How deep it goes
Defines the strategy and demonstrates its implementation, while noting that it ignores future alternatives.
Examples
Uses an argmax function as the greedy strategy passed into a text-generation loop.
What you can do after
Apply it via Keras operations by selecting the highest-scoring token with argmax in a generation loop.
How it connects
Connects greedy decoding to language modeling, random sampling, and top-K sampling.

Also explained in

Compare how 12 books explain greedy algorithm →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Deep Learning with Python, Third Edition. The section links point to the parts of the book it draws on.