Keilahaku: säilytä polku, jonka ahne valinta hylkäisi

Keilahaku (beam search) säilyttää useita hyvin pisteytettyjä osittaisia jonoja yhden tokenivalinnan sijaan. Kukin askel laajentaa säilytetyt polut ja karsii ehdokkaat takaisin keilan leveyteen.

Jonon pisteenä käytetään usein tokenien logaritmisten todennäköisyyksien summaa. Varsinainen toteutus käsittelee myös päättyvät jonot ja voi normalisoida pituuden mukaan.

Paikallisesti huonompi alku voi voittaa

Kiinteä kaksivaiheinen malli näyttää eron lataamatta painoja. Kaikki polut loppuvat kahden tokenin jälkeen, joten pituudet ovat samat.

from math import log

transitions = {
    (): {"A": 0.6, "B": 0.4},
    ("A",): {"x": 0.5, "y": 0.5},
    ("B",): {"x": 0.99, "y": 0.01},
}
def search(width):
    beam = [((), 0.)]
    for _ in range(2):
        candidates = [(path + (token,), score + log(probability))
                      for path, score in beam
                      for token, probability in transitions[path].items()]
        beam = sorted(candidates, key=lambda item: item[1], reverse=True)[:width]
    return beam[0]

greedy = search(1)
wider = search(2)

Leveys yksi valitsee ensin A:n ja päätyy todennäköisyyteen 0,30. Leveys kaksi säilyttää B:n ja löytää polun B–x todennäköisyydellä 0,396. Vaihtoehdon säilyttäminen välttää tämän ahneen valinnan virheen.

Rajallinen keila karsii silti polkuja eikä takaa globaalia optimia. Todennäköisin jono ei myöskään välttämättä ole kiinnostavin tai hyödyllisin teksti. Keilahaku etsii mallin pisteistä eikä korjaa sen tietoja.