Ricerca a fascio

Che cos'è la ricerca a fascio?

La ricerca a fascio è un algoritmo di ricerca euristica che espande il nodo più promettente in un insieme limitato per esplorare un grafo. Questa tecnica utilizza un algoritmo di ricerca in ampiezza per costruire una struttura dati ad albero e generare successori dello stato corrente di ciascun livello.

Le applicazioni software di elaborazione del linguaggio naturale (NLP) e i modelli di riconoscimento vocale utilizzano la ricerca a fascio come livello decisionale. L'obiettivo qui è scegliere il miglior output per variabili target come il prossimo carattere di output o la massima probabilità.

L'algoritmo di ricerca a fascio seleziona i token per una particolare posizione in una sequenza basandosi sulla probabilità condizionale. Regola la larghezza del fascio (β) per scegliere varie alternative di iperparametro n.

A differenza della ricerca golosa, la ricerca a fascio amplia la ricerca per esplorare possibili adattamenti per le parole in una sequenza. La ricerca a fascio prende il nome dal modo in cui l'algoritmo proietta un ampio fascio di ricerca. 

Tipi di ricerca a fascio

La ricerca a fascio ha diverse varianti, a seconda dell'algoritmo utilizzato, come la ricerca in profondità (DFS), la ricerca a discrepanza limitata e la ricerca basata sulla memoria.

1. Ricerca a fascio con pila è un algoritmo di ricerca che utilizza la pila a fascio come struttura dati per combinare la ricerca in profondità o il backtracking cronologico con la ricerca a fascio. Gli utenti possono anche collegarla con un algoritmo divide et impera — una tecnica che scompone ricorsivamente un problema in due o più sottoproblemi — per creare una ricerca a fascio con pila divide et impera.
2. Ricerca a fascio in profondità utilizza un algoritmo di ricerca in profondità per cercare strutture dati a grafo. Utilizza memoria aggiuntiva o una pila per tracciare i nodi esplorati lungo un ramo specifico e fare il backtracking del grafo. 
3. Ricerca a fascio locale traccia o mantiene fino a k stati generati casualmente o numeri di assegnazioni invece di uno. Sceglie i k migliori vicini degli individui correnti in ogni fase. L'algoritmo riporta il successo solo dopo aver trovato un'assegnazione soddisfacente. In caso di parità, sceglierà valori casuali.
4. Ricerca a fascio stocastica seleziona k degli individui casualmente invece dei migliori k individui. Questa variazione della ricerca a fascio utilizza la probabilità di essere scelti come funzione della funzione di valutazione. Migliore è la valutazione, maggiori sono le probabilità di essere scelti.
5. Ricerca a fascio con backtracking a discrepanza limitata (BULB) è un metodo di ricerca basato sulla memoria che risolve problemi di ricerca più grandi entro un tempo di esecuzione ragionevole. Le ricerche BULB lo fanno utilizzando larghezze di fascio maggiori e trovando percorsi più brevi senza perdere memoria.
6. Ricerca a fascio flessibile aumenta temporaneamente la larghezza del fascio per includere tutti i nodi figli con lo stesso valore euristico. 

Componenti della ricerca a fascio

La ricerca a fascio ha tre componenti:

1. Un problema che può essere un grafo o può contenere un insieme di nodi che rappresentano un obiettivo.
2. Regole euristiche si riferiscono alle linee guida specifiche del dominio del problema utilizzate per rimuovere nodi sfavorevoli dalla memoria e concentrarsi sul dominio del problema.
3. Memoria che memorizza il fascio ma ha una capacità disponibile limitata. Quando la memoria è piena, l'algoritmo elimina automaticamente il nodo più costoso per evitare di superare il limite di memoria. 

Vantaggi dell'uso della ricerca a fascio 

La ricerca a fascio tenta di trovare l'ottimale complesso in modo euristico. I vantaggi dell'uso della ricerca a fascio per risolvere problemi di ottimizzazione sono:

• Riduzione del calcolo: La ricerca a fascio utilizza un numero limitato di nodi o risorse alla volta. Di conseguenza, richiede meno calcolo e consumo di memoria rispetto ad altri metodi di ricerca. Sviluppare regole euristiche efficaci per la potatura è cruciale per realizzare questo vantaggio, che può essere difficile senza conoscenze del dominio.
• Miglioramento delle scelte subottimali: La ricerca golosa considera ogni posizione in isolamento. Al contrario, la ricerca a fascio considera più di un'opzione alla volta e migliora le scelte subottimali. 

Svantaggi dell'uso della ricerca a fascio 

Lo svantaggio principale dell'uso di una ricerca a fascio è che gli utenti potrebbero non raggiungere un obiettivo ottimale alla fine. La maggior parte degli algoritmi di ricerca a fascio termina in due scenari: o l'utente non ha ancora raggiunto un nodo obiettivo e non c'è più nessun nodo da esplorare, o ha raggiunto il nodo obiettivo richiesto. 

Inoltre, la ricerca a fascio può essere incompleta a causa della sua natura probabilistica. Nonostante questi svantaggi, gli algoritmi di ricerca a fascio hanno avuto successo nel riconoscimento vocale, nella visione, nella pianificazione e nel machine learning. 

Usi della ricerca a fascio

La ricerca a fascio ha molteplici usi nei sistemi di traduzione automatica, NLP e riconoscimento vocale. I grandi sistemi con memoria insufficiente per memorizzare l'intero albero di ricerca si rivolgono frequentemente alla ricerca a fascio per rimanere gestibili.

I sistemi di traduzione automatica neurale (NMT) utilizzano la ricerca a fascio per scegliere la migliore traduzione e processare ogni parte. Mantengono le migliori traduzioni con le giuste strutture di frase e scartano il resto. Il traduttore poi controlla le traduzioni e sceglie quella migliore che soddisfa gli obiettivi. Nel 1976, il sistema di riconoscimento vocale Harpy della Carnegie-Mellon University è stato il primo a utilizzare una ricerca a fascio. 

Ricerca a fascio vs. ricerca golosa vs. ricerca best-first

Una ricerca golosa segue l'euristica di risoluzione dei problemi per costruire una soluzione gradualmente, un passo alla volta. Il sistema dà priorità alla selezione del prossimo pezzo che fornisce vantaggi chiari e immediati. Gli algoritmi golosi funzionano meglio per problemi in cui è importante scegliere soluzioni localmente ottimali.

La ricerca a fascio ottimizza la ricerca best-first per ridurre i requisiti di memoria.

Sia le ricerche golose che quelle a fascio utilizzano modelli sequenza-a-sequenza per generare output di sequenza o token da una rete neurale. Tuttavia, la prima valuta ogni posizione indipendentemente, mentre la seconda considera più di una alla volta.

La ricerca best-first è una tecnica di ricerca su grafo che ordina e ordina soluzioni parziali basate su euristiche. Tuttavia, la ricerca a fascio considera un numero predeterminato di migliori soluzioni parziali come candidati. Ecco perché la ricerca a fascio è trattata come un algoritmo goloso. 

Vuoi interpretare i dati in modo comprensibile? Esplora il miglior software di generazione del linguaggio naturale (NLG) per elaborare set di dati.