Gradient cho hồi quy tuyến tính và graph embedding

Giới thiệu

Bài này học tìm đường thẳng khớp điểm và vẽ đồ thị. Dùng để hồi quy giá và xếp đỉnh cho đẹp mắt.

Kiến thức cần nhớ

Hồi quy bằng gradient

• Định nghĩa: tìm đường thẳng cho tổng lỗi bình phương nhỏ nhất.
• Bắt đầu đường bừa rồi nghiêng dịch theo hướng giảm lỗi.
• Ví dụ đời thường: như xoay thước cho gần hết đinh nhất.
• Phải chuẩn hóa để thung lũng tròn dễ đi hơn.
• Bài nhỏ có công thức đóng, bài lớn cần gradient.

Nhúng đồ thị

• Định nghĩa: mỗi đỉnh là 1 điểm cần tìm tọa độ đẹp.
• Cost đo giao cắt, cạnh lộn xộn, đỉnh dồn cục.
• Gradient mách mỗi đỉnh nên dịch hướng nào đẹp lên.
• Ví dụ đời thường: như gỡ rối dây tai nghe từng nút.
• Đếm giao cắt thật nhưng gãy khúc, lực hướng trơn hơn.

Vòng lặp cài đặt

• Khởi tạo đỉnh ngẫu nhiên hoặc theo vòng tròn.
• Tính cost, tính gradient, dịch toàn bộ 1 bước.
• Giảm bước dần, dừng khi dịch quá nhỏ.
• Ví dụ đời thường: như phơi ảnh lặp tới khi nét hẳn.
• Đồ thị lớn thì lấy mẫu cặp để chạy nổi.

Ví dụ

• Input: 1 đặc trưng lớn gấp 1000 lần kia -> Output: chuẩn hóa trước.
• Giải thích: thung lũng méo làm gradient lượn vòng mãi.

# Cập nhật đường hồi quy y = a*x + b
a = a - toc_do * dao_ham_a  # chỉnh độ dốc
b = b - toc_do * dao_ham_b  # chỉnh điểm cắt
print(a, b)

💻 Bài tập

Ngôn ngữ: Python 3 với NumPy và networkx (chỉ để tạo và vẽ đồ thị). Nộp vào day-112/.

Bài 1: Hồi quy tuyến tính bằng gradient descent

def fit_gd(X, y, lr=0.01, epochs=1000, batch_size=None, seed=0) -> tuple[np.ndarray, list[float]]:
    """batch_size=None: full batch; 1: SGD; k: mini-batch. Trả (w có bias, lịch sử MSE)."""

1. So hệ số với công thức đóng ngày 55 trên California Housing (đã chuẩn hóa). Sai số dưới 1e-3.
2. Chạy lại không chuẩn hóa. Ghi số epoch cần thiết hoặc hiện tượng phân kỳ.
3. So full batch, mini-batch 32, SGD: vẽ MSE theo số lần duyệt dữ liệu.

Bài 2: Vẽ đồ thị bằng lực (force-directed)

def layout(G, iters=500, lr=0.05, k=1.0, seed=0) -> dict[node, np.ndarray]:
    """Lực đẩy mọi cặp: k^2 / d. Lực hút mỗi cạnh: d^2 / k.
       Mỗi vòng dịch mọi đỉnh theo tổng lực, giảm lr dần. Dừng khi dịch tối đa < 1e-4."""

1. Chạy trên lưới 6x6, cây nhị phân 31 đỉnh, và Karate Club.
2. Vẽ kết quả. Đếm giao cắt bằng hàm ngày 79.
3. Vẽ tổng năng lượng theo vòng lặp: phải giảm.

Bài 3: Tăng tốc và so sánh (nâng cao)

1. Lực đẩy mọi cặp là $O(n^2)$. Cài xấp xỉ: chỉ tính lực đẩy với 50 đỉnh lấy mẫu ngẫu nhiên mỗi vòng, nhân hệ số bù. Chạy trên đồ thị 2000 đỉnh.
2. So thời gian và số giao cắt với bản đầy đủ và với networkx.spring_layout.
3. Khởi tạo vòng tròn và khởi tạo ngẫu nhiên. So kết quả cuối.

✅ Tiêu chí hoàn thành

• Hệ số GD khớp công thức đóng.
• Có số liệu cho thấy không chuẩn hóa thì chậm hoặc phân kỳ.
• Hình layout 3 đồ thị và hình năng lượng giảm dần.
• Bảng thời gian và giao cắt Bài 3.

❓ Câu hỏi ôn tập

• Hồi quy tối thiểu cái gì?
• Vì sao phải chuẩn hóa?
• Cost vẽ đồ thị đo gì?
• Khi nào dừng vòng lặp?

🌕 Bạn đã hoàn thành ngày 112. Làm hết bài tập phía trên rồi sang ngày tiếp theo.