Beam search

1. 1

   En afkodningsalgoritme, der ved hvert tidstrin bevarer de k mest sandsynlige delsekvenser (kaldet stråler) og udvider dem med alle mulige næste tokens, hvorefter de k bedste nye sekvenser vælges. Processen fortsætter, indtil en stopbetingelse er opfyldt (f.eks. slut-token eller maksimal længde).

   • I maskinoversættelse bruges beam search med en beam width på 4 til at generere en oversættelse, der er mere flydende end greedy decoding. — Jurafsky & Martin, Speech and Language Processing, 2023
   • Beam search kan kombineres med length-normalisering for at undgå bias mod korte sætninger.

Beam search bruges primært inden for naturlig sprogbehandling, f.eks. til maskinoversættelse, tekstgenerering og talegenkendelse, hvor modellen skal producere en sekvens af tokens. Algoritmen afbalancerer søgebredde (beam width) og kvalitet for at undgå at overse gode sekvenser, samtidig med at beregningsomkostninger holdes nede.

def beam_search_decoder(predict, start_token, end_token, beam_width=3, max_len=10):
    sequences = [[start_token, 0.0]]  # (sequence, log_prob)
    for _ in range(max_len):
        all_candidates = []
        for seq, score in sequences:
            if seq[-1] == end_token:
                all_candidates.append((seq, score))
                continue
            log_probs = predict(seq)
            for i, lp in enumerate(log_probs):
                candidate = (seq + [i], score + lp)
                all_candidates.append(candidate)
        sequences = sorted(all_candidates, key=lambda x: x[1], reverse=True)[:beam_width]
        if all(s[-1] == end_token for s, _ in sequences):
            break
    return max(sequences, key=lambda x: x[1])[0]

Simpel implementering af beam search til sekvensgenerering. Funktionen predict returnerer log-sandsynligheder for næste token.

Udtrykket 'beam search' kommer fra kunstig intelligens og refererer til idéen om at lade en 'stråle' (beam) af lovende sekvenser fortsætte gennem søgerummet, i modsætning til greedy search, der kun følger én vej.

• Jurafsky, D., & Martin, J. H. (2023). Speech and Language Processing
• Sutskever, I., Vinyals, O., & Le, Q. V. (2014). Sequence to Sequence Learning with Neural Networks