AI Builder
Beam Search — tìm kiếm chùm tia
Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.Thuật toán giải mã giữ lại k ứng viên tốt nhất ở mỗi bước, cân bằng giữa chất lượng và chi phí tính toán.
Cây beam
Với một mô hình ngôn ngữ, mỗi bước sinh ra một phân phối trên toàn bộ từ vựng. Có ba cách giải mã chính: greedy, beam search và sampling. Mỗi cách tối ưu cho một mục tiêu khác nhau.
| Beam width k | Hành vi | Độ phức tạp |
|---|---|---|
| k = 1 | Greedy: chỉ giữ một đường | Nhanh nhất, chất lượng thấp nhất |
| k = 4 đến 10 | Giữ vài đường tốt nhất song song | Điểm cân bằng cho dịch máy, tóm tắt |
| k lớn | Gần như tìm kiếm vét cạn | Chậm, tối ưu hơn |
Length penalty α điều chỉnh việc ưu tiên câu dài hay ngắn: α bằng 0 thiên vị câu ngắn; α trong khoảng 0,6 đến 0,8 là điểm cân bằng cho dịch máy.
So sánh ba chiến lược
Cùng một prompt, ba chiến lược cho ra câu khác nhau:
| Chiến lược | Ví dụ đầu ra | Ưu điểm | Nhược điểm | Dùng cho |
|---|---|---|---|---|
| Greedy (k = 1) | “Tôi yêu em nhiều lắm.” | Cực nhanh, xác định, chi phí thấp | Hay bỏ lỡ câu tốt hơn do tham ăn từng bước | Bản nháp nhanh |
| Beam search (k = 5) | Câu có xác suất tích luỹ cao nhất trong các nhánh | Chất lượng cao, ổn định, tốt hơn greedy | Chậm hơn k lần; luôn cùng đầu ra, thiếu đa dạng | Dịch máy, tóm tắt, captioning, code completion |
| Sampling (top-p 0,9, T 0,8) | “Tôi yêu cà phê buổi sáng.” | Đa dạng, sáng tạo, mỗi lần một khác | Kém ổn định, đôi khi sai ngữ nghĩa | Chatbot, kể chuyện, brainstorm |
Beam search đôi khi tìm được xác suất tổng cao hơn greedy, còn sampling cho ra câu khác hoàn toàn.
Khoảnh khắc A-ha
Beam search giữ k con đường tốt nhất song song, không đặt cược vào một lựa chọn duy nhất. Giống đội thám hiểm chia nhóm: nhóm nào tìm được đường tốt nhất thì thắng.
Điều kỳ diệu: một ứng viên có xác suất thấp ở bước đầu (như “gia đình” chỉ 24%) vẫn có thể dẫn đến câu tốt nhất, nếu các token tiếp theo có xác suất điều kiện cao.
Thử thách nhanh
Lý thuyết và code
Beam search giữ k chuỗi ứng viên (beam) tốt nhất ở mỗi bước, mở rộng song song cho đến khi tất cả kết thúc bằng token kết thúc hoặc đạt độ dài tối đa. Đây là chiến lược giải mã xác định, khác với các phương pháp ngẫu nhiên như top-k, top-p hay chỉnh temperature. Cùng input, beam search luôn cho cùng output.
Top-p = 0,9 nghĩa là chỉ chọn từ trong nhóm 90% xác suất tích luỹ. Kết hợp với temperature T để điều chỉnh độ sáng tạo.
Ví dụ với Hugging Face
huggingface_generate_beam.py
from transformers import AutoModelForCausalLM, AutoTokenizer
model = AutoModelForCausalLM.from_pretrained("gpt2-medium")
tokenizer = AutoTokenizer.from_pretrained("gpt2-medium")
prompt = "Tôi yêu "
inputs = tokenizer(prompt, return_tensors="pt")
# 1. Greedy (num_beams = 1, không sample)
greedy = model.generate(
**inputs,
max_new_tokens=20,
num_beams=1,
do_sample=False,
)
print("Greedy:", tokenizer.decode(greedy[0], skip_special_tokens=True))
# 2. Beam search (num_beams = 5)
beam = model.generate(
**inputs,
max_new_tokens=20,
num_beams=5,
do_sample=False,
length_penalty=0.8, # 0.6–1.0 là phổ biến
early_stopping=True, # dừng khi đủ k beam đạt <eos>
no_repeat_ngram_size=3, # chặn lặp 3-gram (tránh mode collapse)
num_return_sequences=3, # trả về 3 beam tốt nhất
)
for i, seq in enumerate(beam):
print(f"Beam {i}:", tokenizer.decode(seq, skip_special_tokens=True))
# 3. Nucleus sampling (top_p = 0.9)
sample = model.generate(
**inputs,
max_new_tokens=20,
do_sample=True,
top_p=0.9,
top_k=50,
temperature=0.8,
num_return_sequences=3,
)
for i, seq in enumerate(sample):
print(f"Sample {i}:", tokenizer.decode(seq, skip_special_tokens=True))
# 4. Diverse beam search
diverse = model.generate(
**inputs,
max_new_tokens=20,
num_beams=6,
num_beam_groups=3, # chia k thành 3 nhóm
diversity_penalty=1.0, # hình phạt giữa các nhóm
num_return_sequences=3,
do_sample=False,
)
for i, seq in enumerate(diverse):
print(f"Diverse {i}:", tokenizer.decode(seq, skip_special_tokens=True))Beam search tự viết tay
beam_search_from_scratch.py
import torch
import torch.nn.functional as F
from typing import List, Tuple
def beam_search_decode(
model,
input_ids: torch.Tensor,
beam_width: int = 5,
max_length: int = 30,
length_penalty: float = 0.7,
eos_token_id: int = 2,
) -> List[Tuple[torch.Tensor, float]]:
"""
Beam search giải mã tự viết tay.
Trả về danh sách (sequence, score) đã sắp xếp.
"""
device = input_ids.device
# Mỗi beam: (sequence, cumulative_log_prob, is_done)
beams: List[Tuple[torch.Tensor, float, bool]] = [
(input_ids, 0.0, False)
]
for step in range(max_length):
candidates: List[Tuple[torch.Tensor, float, bool]] = []
for seq, score, done in beams:
# Beam đã gặp <eos> thì không mở rộng nữa.
if done:
candidates.append((seq, score, True))
continue
# Forward pass
with torch.no_grad():
logits = model(seq).logits[:, -1, :] # (1, V)
log_probs = F.log_softmax(logits, dim=-1).squeeze(0)
# Lấy top-k token
top_log_probs, top_indices = log_probs.topk(beam_width)
for lp, idx in zip(top_log_probs.tolist(), top_indices.tolist()):
new_seq = torch.cat(
[seq, torch.tensor([[idx]], device=device)],
dim=1,
)
new_score = score + lp
new_done = (idx == eos_token_id)
candidates.append((new_seq, new_score, new_done))
# Prune: lấy top beam_width theo score sau length penalty
def _rank(item):
seq, sc, _ = item
L = seq.size(1)
return sc / (L ** length_penalty)
candidates.sort(key=_rank, reverse=True)
beams = candidates[:beam_width]
# Nếu tất cả beam đã done thì dừng
if all(done for _, _, done in beams):
break
# Trả về (seq, score đã chia length penalty)
return [
(seq, sc / (seq.size(1) ** length_penalty))
for seq, sc, _ in beams
]Tóm tắt
- Beam search giữ k ứng viên tốt nhất song song (k là beam width hoặc num_beams).
- k = 1 là greedy (nhanh, kém). k từ 4 đến 10 là điểm cân bằng cho dịch máy và tóm tắt. k càng lớn càng chậm.
- Length penalty chia điểm cho |Y|^α để tránh thiên vị câu ngắn; α khoảng 0,6 đến 1,0 là phổ biến.
- Dịch máy, tóm tắt, captioning dùng beam search. Chatbot và kể chuyện dùng sampling (top-p và temperature).
- Beam search xác định (cùng input, cùng output); sampling tạo đa dạng.
- Diverse beam search giảm mode collapse; constrained beam search cho phép ép hoặc cấm cụm từ cụ thể.