Tìm Hiểu Thuật Toán BFGS và Ứng Dụng Trong Các Bài Toán Phân Loại

Khám phá thuật toán BFGS và ứng dụng của nó trong các bài toán phân loại, giúp tối ưu hóa hiệu suất và độ chính xác trong học máy.

• Tác giả: Mai Phương Đông
• Người hướng dẫn: TS. Ngô Thời Nhân
• Trường học: Đại Học Huế
• Chuyên ngành: Hệ Thống Thông Tin Kinh Tế
• Đề tài: Thuật Toán BFGS: Ứng Dụng Trong Phân Loại Dữ Liệu
• Loại tài liệu: Khóa Luận Tốt Nghiệp
• Năm xuất bản: 2018
• Địa điểm: Huế

Mục lục chi tiết

• LỜI CẢM ƠN
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC ĐỒ THỊ
• DANH MỤC CÁC HÌNH VẼ
• DANH MỤC CHỮ VIẾT TẮT VÀ KÝ HIỆU
• TÓM TẮT NỘI DUNG NGHIÊN CỨU
• 1. PHẦN I: ĐẶT VẤN ĐỀ
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu nghiên cứu
• 1.3. Đối tượng và phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 1.5. Nội dung nghiên cứu
• 2. PHẦN 2: NỘI DUNG VÀ KẾT QUẢ NGHIÊN CỨU
• 2. CHƯƠNG 1: THUẬT TOÁN BFGS
• 2.1. Thuật toán Newton
• 2.2. Thuật toán Newton cho hàm một biến
• 2.3. Thuật toán Newton cho nhiều biến
• 2.4. Hạn chế của thuật toán Newton
• 2.5. Thuật toán Quasi-Newton
• 2.6. Thuật toán Backtracking line search
• 2.7. Thuật toán BFGS
• 3. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT MACHINE LEARNING
• 3.1. Tổng quan về Machine learning
• 3.2. Khái niệm về Machine learning
• 3.3. Các phương pháp huấn luyện trong Machine learning
• 3.4. Simple Linear Regression (SLR)
• 3.5. Multiple Linear Regression (MLR - Hồi quy tuyến tính nhiều biến)
• 3.6. Bài toán phân loại
• 3.7. Phân loại nhiều lớp bằng thuật toán One-vs-all
• 4. CHƯƠNG 3: ÁP DỤNG BFGS VÀO BÀI TOÁN PHÂN LOẠI
• 4.1. Bài toán phân loại nhị phân
• 4.2. Bài toán phân loại sử dụng Regularized Logistic Regression
• 5. CHƯƠNG 4: ÁP DỤNG BFGS VÀO BÀI TOÁN NHẬN DIỆN CHỮ VIẾT TAY
• 5.1. Bài toán nhận diện chữ số
• 5.2. Nhận diện chữ viết bằng thuật toán BFGS
• 5.3. Áp dụng Regularized Logistic Regression
• 6. PHẦN 3: KẾT LUẬN
• 6.1. Kết quả đạt được
• 6.2. Hạn chế của đề tài
• 6.3. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC 1: Mã nguồn của thuật toán sử dụng trong khóa luận

Tóm tắt

I. Tổng quan về Thuật Toán BFGS và Phân Loại Dữ Liệu

Thuật toán BFGS (Broyden-Fletcher-Goldfarb-Shanno) là một trong những phương pháp tối ưu hóa nổi bật trong lĩnh vực học máy. Thuật toán này được sử dụng để tìm điểm cực tiểu của các hàm số phức tạp, đặc biệt trong các bài toán phân loại dữ liệu. Việc áp dụng BFGS giúp cải thiện hiệu suất của các mô hình học máy, từ đó nâng cao độ chính xác trong việc phân loại dữ liệu.

1.1. Khái niệm cơ bản về Thuật Toán BFGS

Thuật toán BFGS là một phương pháp tối ưu hóa không cần tính toán ma trận Hessian. Thay vào đó, nó sử dụng thông tin từ gradient để cập nhật ước lượng của ma trận Hessian, giúp giảm thiểu chi phí tính toán trong các bài toán lớn.

1.2. Tại sao BFGS quan trọng trong Phân Loại Dữ Liệu

BFGS giúp tối ưu hóa hàm chi phí trong các mô hình phân loại, từ đó cải thiện độ chính xác và tốc độ hội tụ của thuật toán. Điều này đặc biệt quan trọng trong các ứng dụng thực tiễn như nhận diện hình ảnh và phân loại văn bản.

II. Thách Thức Trong Việc Ứng Dụng Thuật Toán BFGS

Mặc dù BFGS mang lại nhiều lợi ích, nhưng việc áp dụng nó trong thực tế cũng gặp phải một số thách thức. Các vấn đề như độ phức tạp tính toán và yêu cầu về dữ liệu đầu vào có thể ảnh hưởng đến hiệu quả của thuật toán.

2.1. Độ phức tạp tính toán của BFGS

BFGS yêu cầu tính toán gradient và cập nhật ma trận Hessian, điều này có thể trở nên tốn kém khi số chiều của dữ liệu tăng lên. Việc này có thể làm chậm quá trình tối ưu hóa.

2.2. Yêu cầu về chất lượng dữ liệu

Để BFGS hoạt động hiệu quả, dữ liệu đầu vào cần phải được chuẩn hóa và có chất lượng cao. Dữ liệu không đồng nhất hoặc có nhiều nhiễu có thể dẫn đến kết quả không chính xác.

III. Phương Pháp Ứng Dụng Thuật Toán BFGS Trong Phân Loại Dữ Liệu

Để áp dụng BFGS vào bài toán phân loại dữ liệu, cần thực hiện một số bước cơ bản. Các bước này bao gồm việc xây dựng hàm chi phí, tính toán gradient và cập nhật tham số.

3.1. Xây dựng hàm chi phí cho bài toán phân loại

Hàm chi phí là yếu tố quyết định trong việc tối ưu hóa. Cần xây dựng hàm chi phí phù hợp với bài toán phân loại, đảm bảo tính lồi để dễ dàng tìm điểm cực tiểu.

3.2. Tính toán gradient và cập nhật tham số

Gradient được tính toán từ hàm chi phí, sau đó sử dụng BFGS để cập nhật tham số. Quá trình này lặp lại cho đến khi đạt được độ chính xác mong muốn.

IV. Ứng Dụng Thực Tiễn Của Thuật Toán BFGS Trong Phân Loại Dữ Liệu

Thuật toán BFGS đã được áp dụng thành công trong nhiều lĩnh vực khác nhau, từ nhận diện hình ảnh đến phân tích văn bản. Các ứng dụng này cho thấy khả năng của BFGS trong việc cải thiện hiệu suất của các mô hình học máy.

4.1. Nhận diện hình ảnh sử dụng BFGS

Trong nhận diện hình ảnh, BFGS giúp tối ưu hóa các mô hình phân loại, từ đó nâng cao độ chính xác trong việc nhận diện các đối tượng khác nhau.

4.2. Phân tích văn bản và phân loại email

BFGS cũng được sử dụng trong phân tích văn bản, giúp phân loại email thành spam và không spam, từ đó cải thiện trải nghiệm người dùng.

V. Kết Luận và Tương Lai Của Thuật Toán BFGS Trong Phân Loại Dữ Liệu

Thuật toán BFGS đã chứng minh được giá trị của mình trong việc tối ưu hóa các bài toán phân loại dữ liệu. Tương lai của BFGS hứa hẹn sẽ còn nhiều tiềm năng với sự phát triển của công nghệ học máy.

5.1. Tiềm năng phát triển của BFGS

Với sự phát triển không ngừng của công nghệ, BFGS có thể được cải tiến để xử lý các bài toán phức tạp hơn, mở ra nhiều cơ hội mới trong lĩnh vực học máy.

5.2. Hướng nghiên cứu tiếp theo

Nghiên cứu có thể tập trung vào việc tối ưu hóa thuật toán BFGS để cải thiện tốc độ và độ chính xác, cũng như áp dụng nó vào các lĩnh vực mới như y học và tài chính.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Lý do chọn đề tài và bối cảnh thực tiễn

Trong giai đoạn phát triển mạnh mẽ của công nghệ thông tin và khoa học dữ liệu, Machine Learning (ML - Học máy) cùng Trí tuệ nhân tạo (AI) và Dữ liệu lớn (Big Data) đã trở thành các lĩnh vực nghiên cứu trọng điểm, được ứng dụng sâu rộng trong nhiều ngành như y tế, tài chính - ngân hàng, xử lý ngôn ngữ tự nhiên và thị giác máy tính. Về bản chất toán học, quá trình huấn luyện hầu hết các mô hình học máy có giám sát (Supervised Learning) đều quy về bài toán tối ưu hóa: tìm tập tham số mô hình nhằm cực tiểu hóa hàm chi phí (Cost Function).

Các phương pháp tối ưu hóa truyền thống như Gradient Descent thường gặp hạn chế về tốc độ hội tụ và việc lựa chọn tốc độ học (learning rate), trong khi phương pháp Newton đòi hỏi chi phí tính toán và bộ nhớ rất lớn để nghịch đảo ma trận đạo hàm bậc hai (ma trận Hessian) khi số chiều dữ liệu tăng cao. Để khắc phục những điểm yếu này, các thuật toán xấp xỉ Quasi-Newton, tiêu biểu là thuật toán BFGS (Broyden–Fletcher–Goldfarb–Shanno), được phát triển nhằm cập nhật ma trận Hessian thông qua thông tin đạo hàm bậc nhất (gradient). Xuất phát từ bối cảnh học thuật và thực tiễn nêu trên, tác giả Mai Phương Đông đã thực hiện khóa luận tốt nghiệp ngành Tin học kinh tế tại Trường Đại học Kinh tế – Đại học Huế với đề tài: "Tìm hiểu về thuật toán BFGS và ứng dụng".

Mục tiêu và nhiệm vụ nghiên cứu

Khóa luận xác định các mục tiêu và nhiệm vụ nghiên cứu cụ thể bao gồm:

1. Tìm hiểu các lý thuyết cơ bản về Machine Learning và các mô hình toán học trong Supervised Learning (Học có giám sát).
2. Nghiên cứu cơ sở lý thuyết, cơ chế vận hành và phương pháp cập nhật ma trận xấp xỉ Hessian của thuật toán Quasi-Newton nói chung và thuật toán BFGS nói riêng.
3. Tìm hiểu và ứng dụng thuật toán tìm kiếm đường đi Backtracking line search để xác định bước nhảy tối ưu trong mỗi vòng lặp.
4. Xây dựng chương trình tính toán và thực thi thuật toán trên môi trường ngôn ngữ lập trình GNU Octave / MATLAB.
5. Ứng dụng thuật toán BFGS để giải quyết các bài toán tối ưu hàm chi phí trong phân loại nhị phân, phân loại phi tuyến và bài toán nhận diện ký tự, chữ số viết tay.

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Thuật toán tối ưu hóa số BFGS; các bài toán hồi quy tuyến tính (Linear Regression) và phi tuyến; mô hình phân loại nhị phân (Binary Classification) sử dụng Logistic Regression; mô hình phân loại nhiều lớp (Multiclass Classification) thông qua chiến lược One-vs-all; kỹ thuật chuẩn hóa chống quá khớp (Regularization).
• Phạm vi nội dung và công nghệ: Các giải thuật tối ưu trong Supervised Learning; kỹ thuật lập trình ma trận hóa trên môi trường GNU Octave / MATLAB; kỹ thuật xử lý dữ liệu ảnh ma trận điểm phục vụ nhận dạng ký tự.
• Dữ liệu nghiên cứu:
  • Dữ liệu dự đoán tuyển sinh gồm 100 mẫu ($100 \times 3$) từ khóa học Machine Learning của Đại học Stanford.
  • Dữ liệu kiểm thử chất lượng vi mạch (chipset) gồm 118 mẫu ($118 \times 3$) từ Đại học Stanford.
  • Bộ dữ liệu chữ số viết tay chuẩn MNIST gồm 5.000 mẫu (500 mẫu cho mỗi chữ số từ 0 đến 9).
  • Bộ dữ liệu chữ cái viết tay A-Z Handwritten Alphabets từ Kaggle, trích xuất 13.000 mẫu phục vụ huấn luyện.
• Thời gian và địa điểm thực hiện: Nghiên cứu được tiến hành từ ngày 01/10/2018 đến ngày 30/12/2018 tại Khoa Hệ thống thông tin Kinh tế, Trường Đại học Kinh tế – Đại học Huế và quá trình thực tập tại Công ty MagRabbit Huế.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và mô hình toán học

Khóa luận xây dựng hệ thống cơ sở lý thuyết dựa trên hai trục chính: Giải tích tối ưu hóa số học và Lý thuyết học máy có giám sát.

1. Phương pháp Newton và giới hạn: Phương pháp Newton giải phương trình $f(x) = 0$ hoặc tìm cực trị của hàm nhiều biến thông qua khai triển Taylor bậc hai: $$f(x_k + \Delta x) \approx f(x_k) + \nabla f(x_k)^T \Delta x + \frac{1}{2} \Delta x^T B \Delta x$$ Điểm hạn chế là bắt buộc ma trận đạo hàm bậc hai (Hessian) phải xác định và chi phí tính nghịch đảo $O(n^3)$ rất tốn kém khi số chiều $n$ lớn.
2. Thuật toán Quasi-Newton và BFGS: Thay vì tính toán trực tiếp ma trận Hessian, phương pháp Quasi-Newton xây dựng ma trận xấp xỉ đối xứng xác định dương $B_k$ biến thiên qua từng bước lặp dựa trên phương trình Secant: $$B_{k+1} s_k = y_k$$ Trong đó $s_k = x_{k+1} - x_k$ và $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$. Công thức cập nhật hạng hai BFGS có dạng: $$B_{k+1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k}$$ Để tối ưu hóa tính toán, công thức Sherman-Morrison được áp dụng để tính trực tiếp nghịch đảo $B_{k+1}^{-1}$ mà không cần làm phép đảo ma trận.
3. Thuật toán Backtracking line search: Dùng để xác định bước nhảy $\alpha_k > 0$ theo hướng tìm kiếm $d_k = - B_k^{-1} \nabla f(x_k)$, thỏa mãn điều kiện suy giảm Armijo: $$f(x + \alpha d) \le f(x) + c \alpha m$$ với các tham số kiểm soát $c \in (0, 1)$ và hệ số thu nhỏ $\tau \in (0, 1)$.
4. Mô hình hồi quy và phân loại trong Machine Learning:
   • Hồi quy tuyến tính (Simple & Multiple Linear Regression): sử dụng hàm giả thuyết $h_\theta(x) = \theta^T x$ và hàm chi phí sai số bình phương trung bình $J(\theta)$ có tính lồi ngặt.
   • Hồi quy Logistic (Logistic Regression): kết hợp hàm tuyến tính với hàm kích hoạt Sigmoid $g(z) = \frac{1}{1 + e^{-z}}$, đưa đầu ra về khoảng xác suất $(0, 1)$. Hàm chi phí Cross-Entropy được biểu diễn: $$J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(h_\theta(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_\theta(x^{(i)})) \right]$$
   • Kỹ thuật Regularization: Bổ sung thành phần phạt $\frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2$ vào hàm chi phí để hạn chế hiện tượng quá khớp (overfitting) khi mở rộng số chiều đa thức phi tuyến.
   • Chiến lược One-vs-all: Huấn luyện $K$ bộ phân loại nhị phân độc lập cho bài toán phân loại $K$ lớp đối tượng, gán nhãn theo mô hình có xác suất dự đoán $h_\theta^{(k)}(x)$ lớn nhất.

Phương pháp nghiên cứu thực tế

• Phương pháp tối ưu hóa số học: Lập trình thực nghiệm giải thuật BFGS kết hợp Backtracking line search, tự động điều chỉnh tốc độ học qua từng vòng lặp để hội tụ về điểm cực tiểu toàn cục của hàm chi phí lồi.
• Phương pháp giải tích toán học: Chứng minh và kiểm chứng tính lồi ngặt của các hàm chi phí trong Linear Regression và Logistic Regression nhằm đảm bảo mọi cực tiểu địa phương tìm được bởi BFGS đều là nghiệm tối ưu toàn cục duy nhất.
• Phương pháp thực nghiệm và so sánh đối chuẩn: Cài đặt thuật toán trên GNU Octave/MATLAB, tiến hành đo lường hiệu năng và so sánh kết quả phân loại (độ chính xác, phương trình đường ranh giới quyết định) giữa thuật toán BFGS tự lập trình với hàm tối ưu tích hợp sẵn fminunc của Octave/MATLAB trên cùng một số lượng vòng lặp ($N = 200$).

---

Nội dung chính theo từng chương

Chương 1: Thuật toán BFGS

Chương này tập trung phân tích nguồn gốc toán học, cấu trúc giải thuật và cơ chế tối ưu của thuật toán BFGS trong không gian đa chiều. Tác giả trình bày chi tiết từ giải thuật Newton một biến, mở rộng sang hệ nhiều biến với ma trận đạo hàm Jacobi và ma trận Hessian. Sau khi chỉ ra hai nhược điểm cốt lõi của phương pháp Newton (phụ thuộc điểm khởi tạo và độ phức tạp tính toán ma trận Hessian bậc hai), chương phân tích giải pháp Quasi-Newton thông qua phương trình Secant và lớp cập nhật Broyden.

Nội dung trọng tâm của chương là việc triển khai thuật toán BFGS 5 bước kết hợp thuật toán Backtracking line search nhằm tự động xác định kích thước bước nhảy $\alpha_k$. Đồng thời, chương trình bày phương pháp ứng dụng bổ đề đảo ma trận Sherman-Morrison, giúp tính toán trực tiếp ma trận nghịch đảo Hessian xấp xỉ $B_{k+1}^{-1}$, qua đó tiết kiệm đáng kể thời gian xử lý và tài nguyên bộ nhớ máy tính.

Chương 2: Cơ sở lý thuyết Machine Learning

Chương 2 cung cấp bức tranh tổng quan về các phương pháp huấn luyện trong Machine Learning theo định nghĩa của Tom Mitchell, phân định rõ giữa học có giám sát (Supervised Learning) và học không giám sát (Unsupervised Learning). Tác giả đi sâu vào chi tiết toán học của hai bài toán nền tảng:

• Hồi quy tuyến tính đơn biến (SLR) và đa biến (MLR): Định nghĩa cấu trúc hàm giả thuyết Hypothesis Function $h_\theta(x) = \theta^T x$, xây dựng hàm chi phí bình phương sai số $J(\theta)$, biểu diễn dạng ma trận hóa $J(\theta) = \frac{1}{2m} (X\theta - y)^T (X\theta - y)$ và chứng minh tính lồi ngặt.
• Phân loại nhị phân (Binary Classification) với Logistic Regression: Phân tích lý do không thể dùng hàm chi phí bình phương (gây mất tính lồi khi qua hàm Sigmoid) và chuyển sang hàm chi phí Cross-Entropy. Tác giả thiết lập công thức tính Gradient $\nabla J(\theta) = \frac{1}{m} X^T (g(X\theta) - y)$ dưới dạng ma trận hóa.
• Phân loại đa lớp One-vs-all và kỹ thuật Regularization: Trình bày cơ chế chia bài toán $n$ lớp thành $n$ bài toán phân loại nhị phân và kỹ thuật bổ sung tham số điều chuẩn $\lambda$ vào hàm mất mát nhằm triệt tiêu phương sai cao (high variance/overfitting).

Chương 3: Áp dụng BFGS vào bài toán phân loại

Chương 3 trình bày các thực nghiệm cụ thể khi áp dụng thuật toán BFGS để tối ưu hóa hàm chi phí cho hai bài toán phân loại thực tế:

1. Bài toán phân loại nhị phân (Xét tuyển sinh viên): Sử dụng bộ dữ liệu 100 mẫu điểm thi. Mô hình phân loại tuyến tính sử dụng Logistic Regression tối ưu bằng BFGS và so sánh với hàm fminunc của Octave ở 200 vòng lặp. Kết quả ghi nhận véc-tơ tham số $\theta$ với hệ số chặn $\theta_0 = -25.168936$. Thuật toán BFGS tìm được đường phân cách phân định rõ ràng giữa hai miền đỗ/trượt, đạt độ chính xác 92%, vượt trội hơn mức 89% của fminunc.
2. Bài toán phân loại phi tuyến có Regularization (Kiểm định vi mạch bán dẫn - Chipset): Sử dụng 118 mẫu dữ liệu kiểm thử vi mạch không thể phân tách tuyến tính. Tác giả tiến hành mở rộng không gian đặc trưng bằng các đa thức bậc 6 dạng $x_1^{6-k} x_2^k$ ($k \in {1, \dots, 6}$). Mô hình Regularized Logistic Regression được kiểm thử với các giá trị tham số điều chuẩn $\lambda$ khác nhau ($\lambda = 0; 0.01; 0.03; 0.1; 0.3; 1$). Thực nghiệm chỉ ra tác động rõ rệt của $\lambda$: khi $\lambda = 0$, mô hình bị overfitting tạo ranh giới quá phức tạp; khi $\lambda$ tăng hợp lý ($\lambda = 1$), đường bao phân cách trở nên trơn tru và tổng quát hóa tốt hơn.

Bài toán thực nghiệm	Kích thước dữ liệu	Số vòng lặp	Độ chính xác fminunc	Độ chính xác BFGS
Tuyển sinh đại học (Tuyến tính)	$100 \times 3$	200	89%	92%
Kiểm định vi mạch (Phi tuyến)	$118 \times 3$	200	Khảo sát theo $\lambda$	Khảo sát theo $\lambda$

Chương 4: Áp dụng BFGS vào bài toán nhận diện chữ viết tay

Chương 4 mở rộng phạm vi ứng dụng của thuật toán BFGS sang bài toán thị giác máy tính nhận dạng ảnh ký tự:

• Nhận diện chữ số viết tay: Thực nghiệm trên tập dữ liệu chuẩn MNIST gồm 5.000 mẫu ảnh ma trận (500 mẫu/chữ số từ 0 đến 9). Tác giả kết hợp mô hình Regularized Logistic Regression với chiến lược phân lớp One-vs-all, sử dụng thuật toán BFGS để tối ưu 10 hàm chi phí tương ứng với 10 lớp chữ số.
• Nhận diện chữ cái viết tay: Thực nghiệm trên bộ dữ liệu A-Z Handwritten Alphabets (trích xuất 13.000 mẫu từ tập gốc hơn 3 triệu dòng của Kaggle). Mô hình mở rộng cấu trúc One-vs-all lên 26 lớp ký tự (A đến Z).
• Đồ án phân tích cấu trúc dữ liệu ảnh đầu vào, ma trận hóa các trọng số, tối ưu hóa các bước nhảy hội tụ bằng Backtracking line search và chứng minh tính khả thi của giải thuật BFGS trong việc giải quyết các bài toán phân loại đa lớp có số chiều tham số lớn.

---

Kết quả và đóng góp

Kết quả nghiên cứu chính

Khóa luận đã triển khai thành công mô hình toán học và mã nguồn thuật toán BFGS kết hợp Backtracking line search trên môi trường GNU Octave/MATLAB, đạt được các kết quả cụ thể sau:

1. Hiệu năng tối ưu phân loại nhị phân: Trên tập dữ liệu tuyển sinh 100 mẫu, thuật toán BFGS tự cài đặt đạt độ chính xác 92%, cao hơn 3% so với hàm chuẩn fminunc của Octave/MATLAB (đạt 89%) tại cùng mốc 200 vòng lặp.
2. Khả năng xử lý bài toán phi tuyến: Xây dựng thành công mô hình phân loại phi tuyến cho 118 mẫu chipset nhờ kỹ thuật mở rộng đa thức bậc 6 và chuẩn hóa Regularization. Đã phân tích thực nghiệm và vẽ trực quan hóa đường ranh giới quyết định (Decision Boundary) ở các mức $\lambda \in {0; 0.01; 0.03; 0.1; 0.3; 1}$, chứng minh cơ chế kiểm soát overfitting hiệu quả của mô hình khi kết hợp BFGS.
3. Ứng dụng nhận dạng ký tự đa lớp: Áp dụng thành công thuật toán BFGS cho bài toán nhận dạng 5.000 mẫu chữ số MNIST (10 lớp) và 13.000 mẫu chữ cái A-Z Kaggle (26 lớp) thông qua cơ chế One-vs-all, hoàn thiện quy trình huấn luyện đa lớp trên dữ liệu thực tế.

Đóng góp của đề tài

• Về mặt học thuật và phương pháp: Hệ thống hóa cơ sở toán học chặt chẽ của các thuật toán tối ưu Quasi-Newton; làm rõ mối liên hệ giữa điều kiện Secant, cập nhật hạng hai BFGS và công thức nghịch đảo Sherman-Morrison trong việc giải quyết bài toán cực tiểu hóa hàm chi phí lồi.
• Về mặt kỹ thuật và ứng dụng: Tự xây dựng trọn vẹn bộ mã nguồn thuật toán BFGS và Backtracking line search trên Octave mà không phụ thuộc hoàn toàn vào các hộp công cụ (toolbox) có sẵn. Cung cấp quy trình chi tiết về việc ma trận hóa dữ liệu và xử lý bài toán phân loại từ đơn biến, đa biến, phi tuyến đến phân loại đa lớp quy mô lớn.

---

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của đề tài

Dựa trên phạm vi và nội dung trình bày trong khóa luận, các hạn chế được ghi nhận bao gồm:

• Tốc độ thực thi và khả năng hội tụ của thuật toán BFGS vẫn phụ thuộc vào giá trị khởi tạo ban đầu và việc lựa chọn các tham số kiểm soát $c, \tau$ trong thuật toán Backtracking line search.
• Khi số lượng lớp phân loại và kích thước dữ liệu tăng cao (như tập chữ cái 26 lớp), thời gian huấn luyện tăng lên do phải chạy lặp $K$ lần mô hình One-vs-all độc lập.
• Nghiên cứu chỉ dừng lại ở các mô hình phân loại tuyến tính, phi tuyến bậc thấp và One-vs-all Logistic Regression; chưa mở rộng sang các kiến trúc mạng nơ-ron nhiều tầng (Multi-layer Neural Networks) hoặc Deep Learning.
• Toàn bộ thuật toán được cài đặt và đánh giá trên môi trường GNU Octave/MATLAB với các tập dữ liệu tĩnh, chưa xây dựng giao diện người dùng hoàn chỉnh hay triển khai thực tế trên hệ thống sản xuất.

Hướng nghiên cứu tiếp

• Tối ưu hóa hiệu năng tính toán của mã nguồn BFGS, nghiên cứu biến thể L-BFGS (Limited-memory BFGS) để tiết kiệm bộ nhớ khi xử lý các tập dữ liệu có số chiều tham số cực lớn.
• Tích hợp giải thuật BFGS vào quá trình lan truyền ngược (backpropagation) để huấn luyện các mạng nơ-ron nhân tạo sâu (Deep Neural Networks).
• Mở rộng phạm vi thử nghiệm trên toàn bộ cơ sở dữ liệu ảnh quy mô lớn và phát triển ứng dụng nhận dạng chữ viết tay trực tiếp thời gian thực.

---

Giá trị tham khảo

Tài liệu khóa luận có giá trị tham khảo chuyên môn đối với:

• Sinh viên các ngành Hệ thống thông tin, Tin học kinh tế, Khoa học máy tính, Toán tin: Nguồn tài liệu chi tiết để hiểu sâu bản chất giải tích của các thuật toán tối ưu hóa số học và kỹ thuật ma trận hóa khi lập trình học máy trên GNU Octave / MATLAB.
• Người nghiên cứu và lập trình viên Machine Learning: Tham khảo phương pháp tự lập trình các giải thuật tối ưu Quasi-Newton, cách giải quyết bài toán phi tuyến thông qua biến đổi đa thức đặc trưng, kỹ thuật điều chuẩn Regularization và cơ chế phân lớp One-vs-all.
• Phần đáng tham khảo nhất: Chương 1 (biến đổi toán học của BFGS và Sherman-Morrison), Chương 2 (dẫn xuất đạo hàm ma trận của Cross-Entropy Loss) và Phụ lục mã nguồn chi tiết các hàm BFGS, Backtracking line search.

---

Câu hỏi thường gặp

1. Tại sao thuật toán BFGS lại được ưu tiên sử dụng thay thế cho phương pháp Newton truyền thống trong tối ưu hóa hàm chi phí?

Phương pháp Newton đòi hỏi phải tính toán ma trận đạo hàm bậc hai (Hessian) và nghịch đảo ma trận này ở mỗi vòng lặp, dẫn tới chi phí tính toán $O(n^3)$ và tốn bộ nhớ rất lớn khi số chiều dữ liệu tăng. Thuật toán BFGS thuộc họ Quasi-Newton khắc phục điểm này bằng cách ước lượng xấp xỉ ma trận Hessian thông qua các véc-tơ gradient liên tiếp (dựa trên phương trình Secant và cập nhật hạng hai), đồng thời sử dụng công thức Sherman-Morrison để tính trực tiếp ma trận nghịch đảo mà không cần đảo ma trận thực sự.

2. Vai trò của thuật toán Backtracking line search trong cấu trúc của BFGS là gì?

Backtracking line search có nhiệm vụ xác định độ lớn bước di chuyển (bước nhảy $\alpha_k > 0$) dọc theo hướng tìm kiếm $d_k$ sao cho giá trị hàm chi phí giảm đủ lớn, thỏa mãn điều kiện Armijo ($f(x + \alpha d) \le f(x) + c \alpha m$). Thuật toán bắt đầu bằng một bước nhảy tương đối lớn và thu nhỏ dần theo hệ số $\tau \in (0, 1)$, giúp thuật toán BFGS tự động điều chỉnh tốc độ học (learning rate) tối ưu tại từng vòng lặp mà không cần người dùng chọn cố định bằng tay.

3. Trong bài toán thực nghiệm phân loại nhị phân dữ liệu tuyển sinh, thuật toán BFGS đạt kết quả ra sao so với hàm fminunc của Octave?

Trên tập dữ liệu tuyển sinh gồm 100 mẫu ($100 \times 3$) từ Đại học Stanford với 200 vòng lặp, thuật toán BFGS tự cài đặt đạt độ chính xác phân loại là 92%, cao hơn độ chính xác 89% của hàm tối ưu hóa tích hợp sẵn fminunc trong Octave/MATLAB.

4. Tác giả đã giải quyết bài toán phân loại phi tuyến trên tập dữ liệu kiểm thử vi mạch (chipset) bằng phương pháp nào?

Tác giả đã tạo thêm các đặc trưng phi tuyến từ hai đầu vào gốc $x_1, x_2$ bằng cách bổ sung các thành phần đa thức bậc 6 dạng $x_1^{6-k} x_2^k$ ($k \in {1, \dots, 6}$). Do số đặc trưng tăng lên làm tăng nguy cơ quá khớp (overfitting), tác giả đã kết hợp mô hình hồi quy Logistic với kỹ thuật chuẩn hóa Regularized Logistic Regression và thử nghiệm trên nhiều giá trị tham số $\lambda$ khác nhau nhằm tìm ra đường ranh giới quyết định tối ưu.

5. Khóa luận sử dụng các bộ dữ liệu nào cho bài toán nhận diện chữ số và chữ viết tay ở Chương 4?

Tác giả sử dụng hai bộ dữ liệu:

• Bộ dữ liệu chữ số viết tay MNIST với 5.000 mẫu được chia đều (500 mẫu cho mỗi chữ số từ 0 đến 9).
• Bộ dữ liệu chữ cái viết tay A-Z Handwritten Alphabets từ Kaggle, trong đó tác giả trích xuất 13.000 mẫu để phục vụ huấn luyện phân loại 26 lớp ký tự theo chiến lược One-vs-all.

---

Kết luận

Khóa luận tốt nghiệp của tác giả Mai Phương Đông đã hoàn thành việc nghiên cứu toàn diện về cơ sở lý thuyết và thuật toán tối ưu hóa số Quasi-Newton BFGS kết hợp kỹ thuật tìm kiếm đường đi Backtracking line search. Đề tài đã làm rõ phương pháp luận toán học trong việc giải quyết bài toán cực tiểu hóa hàm chi phí lồi của các mô hình học máy có giám sát (Linear Regression, Logistic Regression, Regularization và One-vs-all). Các kết quả thực nghiệm trên môi trường GNU Octave/MATLAB đối với bài toán tuyển sinh, kiểm thử vi mạch và nhận dạng chữ viết tay (MNIST, A-Z Kaggle) đã khẳng định tính chính xác, hiệu quả và giá trị ứng dụng thực tiễn của giải thuật BFGS trong phân loại dữ liệu.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: THUẬT TOÁN BFGS 1. Thuật toán Newton 1. Thuật toán Newton cho hàm một biến Phương pháp Newton [1], [2], [3] được đặt tên theo Isaac Newton và Joseph Paphson, là một phương pháp tìm nghiệm xấp xỉ gần đúng của một hàm số thực.1) Thuật toán Newton được thực thi như sau: Giả sử hàm f có đạo hàm liên tục. Bắt đầu bởi số thực x, với đạo hàm f ' và một số gần đúng x0 khá gần với nghiệm x * của phương trình f ( x )  0 , ta tìm được một điểm x1 gần với nghiệm x * hơn x0 xác định như sau: f ( x0 ) x1  x0  (1.

Quá trình này cứ thế được lặp lại với: f ( xn ) xn 1  xn  (1.3) f '( xn ) cho đến khi dãy điểm hội tụ về nghiệm x *. Khả năng tốc độ hội tụ của phương pháp Newton phụ thuộc nhiều vào giá trị khởi tạo ban đầu x0. Giá trị x0 càng gần với nghiệm thực tế của phương trình (1.1) thì thuật toán Newton hội tụ càng nhanh. Trong trường hợp phương trình không có nghiệm, phương pháp này cũng không thể phát hiện ra.

Một điểm hạn chế nữa là do yêu cầu tính đạo hàm của hàm số, phương pháp này sẽ gặp khó khăn trong trường hợp việc tính toán đạo hàm phức tạp. Trong trường hợp này, người ta có thể xấp xỉ việc tính đạo hàm bằng các phương pháp số khác. 11 Khóa luận tốt nghiệp 1. Thuật toán Newton cho nhiều biến Bây giờ xét bài toán tìm nghiệm của hệ n phương trình sau:  f1 ( x1 , x2 , , xn )  0  f ( x , x , , x )  0 (1., xn ) là nghiệm của hệ phương trình * * * * (1.

Mở rộng từ thuật toán Newton cho hàm một biến, bắt đầu từ điểm x (1 ) ta lấy vi phân hành đạo hàm từng phần mỗi phương trình fi : n f f i f df i ( x (1) )  dx1    i dxn   j dxi .5) x1 xn i 1 xi Ta tiến hành tính xấp xỉ hiệu fi ( x )  fi ( x ) như sau: (2) (1) n  f  fi ( x(2) )  fi ( x(1) )    j   xi(2)  xi(1) , i {1,2,, n}.6) i 1  xi  Gọi x ( k ) là giá trị xấp xỉ của nghiệm x * ở lần lặp thứ k. Ta mong muốn fi (x (k 1) )  0 , do đó hệ n phương trình (1.6) có thể viết dưới dạng ma trận: J ( k ) x ( k )   R ( k ) , (1.9) 12 Khóa luận tốt nghiệp và  x ( k )  x ( k 1)  x ( k ) .10) Do đó nghiệm tại bước thứ k  1 là x( k 1)   x( k )  x( k ) .11) Tổng quát lại ta có thuật toán Newton cho hệ n phương trình như sau: (1) 1. Khởi tạo điểm ban đầu x. Tính ma trận Jacobi và vector thặng dư.

Giải phương trình (1.7) bằng các phương pháp trong đại số tuyến tính, 4. Cập nhật x mới theo (1. Lặp lại bước 2 đến bước 4 nếu kết quả còn chưa hội tụ. Hạn chế của thuật toán Newton Điểm khởi tạo phải rất gần với nghiệm thực.

Ý tưởng của Newton là dựa vào triển khai Taylor của hàm số f(x) tới đạo hàm thứ nhất 0  f ( x* )  f ( xt )  f '( xt )( xt  x* ) (1.12) để từ đó tính ra ngiệm xấp xỉ. Nhận xét rằng trong việc giải phương trình f ( x )  0 , chúng ta có đạo hàm ở mẫu số. Khi đạo hàm này gần với 0, ta sẽ được một đường thẳng song song với trục hoành. Ta sẽ hoặc không tìm được giao điểm, hoặc được một giao điểm ở vô cùng.

Đặc biệt khi nghiệm chính là điểm có đạo hàm bằng 0, thuật toán gần như sẽ không tìm được nghiệm. Khi áp dụng thuật tóa Newton cho bài toán tối ưu trong không gian nhiều chiều, chúng ta cần tính nghịch đảo của ma trận Hessian. Khi số chiều và số điển dữ liệu lớn, đạo hàm bậc hai của hàm f ( x ) là một ma trận rất lớn, ảnh hưởng tới cả bộ nhớ và tốc độ tính toán của hệ thống. Thuật toán Quasi-Newton Thuật toán quasi-Newton [4], [5], [6] là thuật toán dùng để tìm số nghiệm hoặc đi tìm cực trị của các hàm số, như là một thuật toán thay thế cho thuật toán Newton.

Thuật toán 13 Khóa luận tốt nghiệp quasi-Newton có thể được sử dụng nếu ma trận Jacobian hoặc Hessian không có sẵn hoặc quá khó khăn để tính toán được. Việc tìm tối thiểu hoặc tối đa của hàm có giá trị vô hướng không khác gì việc tìm kiếm các số 0 của gradient của hàm đó, các phương pháp quasi-Newton có thể dễ dàng tìm cực trị của hàm. Nói cách khác, nếu g là gradient của hàm số f , sau đó tìm kiếm các số 0 của hàm có giá trị véc tơ g tương ứng với việc tìm kiếm cực trị của hàm số f , ma trận Jacobi của g bây giờ thành Hessian của f. Sự khác biệt chính là ma trận Hessian là một ma trận đối xứng, không giống như Jacobi khi tìm kiếm các số 0.

Hầu hết trong các bài toán tối ưu hóa đều khác thác tính chất này. Thuật toán Quasi-Newton dựa trên thuật toán Newton để tìm điểm dừng của hàm, trong gradient là 0. Phương pháp của Newton giả định rằng các hàm có thể xấp xỉ cục bộ như một phương trình bậc hai quanh vùng tối ưu và sử dụng điểm thứ nhất và thứ hai đạo hàm để tìm điểm dừng. Ở các chiều cao hơn, thuật toán Newton sử dụng gradient và ma trận Hessian của các đạo hàm thứ hai của các hàm chức năng được giảm thiểu.

Trong các thuật toán Quasi-Newton, ma trận Hessian không cần phải tính toán. Thay vào đó, ma trận Hessian được cập nhật bằng cách phân tích các véc tơ gradient liên tiếp. Các thuật toán Quasi-Newton là một khái quát của thuật toán secant để tìm ra gốc của đạo hàm đầu tiên cho các hàm đa chiều. Trong nhiều chiều, phương trình secant được xác định dưới mức và các thuật toán quasi-Newton khác nhau về cách cập nhật, thông thường bằng cách thêm một lần cập nhật thứ hạng đơn giản vào ước tính hiện tại của ma trận Hessian.

Trong thuật toán Newton, người ta sử dụng xấp xỉ bậc hai để tìm mức tối thiểu của hàm số f ( x ). Triển khai Taylor của f ( x ) ta được: 1 f ( xk  x)  f ( xk )  f ( xk )T  xT Bx (1.13) 2 Ở đây  f là gradient và B là ma trận xỉ với ma trận Hessian. Gradient của xấp xỉ này là: 14 Khóa luận tốt nghiệp f (xk x) f (xk )  Bx (1.14) Và ta đặt gradient này về 0 (là mục tiêu của tối thiểu hóa) đặt lại giá trị cho bước lặp Newton: x  B1f (xk ) (1.15) Ma trận xấp xỉ ma trận Hessian được chọn để thỏa mãn f (xk x) f (xk )  Bx (1.17) được gọi là phương trình secant (là chuỗi khai triển Taylor của gradient). Trong nhiều chiều B không xác định.

Trong một chiều, ta áp dụng thuật toán Newton và cập nhật giá trị tương đương với phương trình secant. Thuật toán quasi-Newton có thể có nhiều giải pháp cho phương trình secant. Trong đó phương pháp đối xứng là phương pháp được sử dụng phổ biến nhất. Nếu ta đặt: sk  xk1  xk , yk f (xk1) f (xk ) (1.18) Vậy thì theo định lý của phép tích phân ta được:   f ( x  ts )dt s  y 1 0 2 k k k k (1.19) Ma trận nằm trong dấu ngoặc nhọn có thể hiểu là trung bình của ma trận Hessian trên đoạn  xk , xk  sk .

Kết quả này chứng minh rằng, khi ma trận được nhân với véc tơ sk thì thu được véc tơ là yk. Theo những quan sát này, ta có thể khiến Bk1 bắt chước hành vi của  f bằng cách thực thi điều kiện quasi-Newton. 2 Bk1sk  yk (1.20) Điều kiện này được thỏa mãn bằng cách thực hiện cập nhật xếp hạng thấp đơn giản cho Bk. Họ cập nhập được sử dụng phổ biến nhất là lớp cập nhật hạng hai của Broyden, có dạng: Bk sk ( Bk sk )T y k y kT Bk 1  Bk  T  T  k  skT Bk sk  vk vkT (1.21) sk Bk sk y k sk 15 Khóa luận tốt nghiệp Khi cho  0,1 và  y B s  vk   T k  T k k  (1.22)  yk sk sk Bk sk  1.

Thuật toán Backtracking line search Xét bài toán sau: Cho hàm số f ( x ) với x  R n và một vectơ đơn vị (hướng) dx ngược hướng với gradient  f ( x ). Hãy xác định kích thước  để cực tiểu hóa giá trị f (x . Backtracking line search [7], [8] là thuật toán được sử dụng để tìm ra nghiệm xấp xỉ của bài toán này. Nó liên quan đến việc bắt đầu với một ước lượng tương đối về độ lớn bước di chuyển dọc theo hướng tìm kiếm và lặp đi lặp lại việc thu nhỏ độ lớn bước di chuyển, cho đến khi giá trị của hàm số không còn giảm tiếp được nữa.

Vì hướng tìm kiếm dx là một vectơ đơn vị theo hướng ngược T hướng với gradient  f ( x ) nên m  0. Dựa trên một tham số điều kiện được chọn c  (0,1), chúng ta sẽ kiểm tra xem liệu có đúng khi chúng ta di chuyển từ vị trí hiện tại x đến vị trí mới là x .dx đạt mức giảm tương ứng ở hàm mục tiêu không. Điều kiện để được đáp ứng là: f (x dx )  f (x) cm  f (x)  f (x dx )  cm  0 (1.22) Điều kiện này khi được sử dụng một cách thích hợp đóng vai trò như là một phần của thuật toán, có để đảm bảo kích thước của các bước không quá lớn. Tuy nhiên điều kiện này không đủ khả năng để đảm bảo rằng, độ lớn của bước  là tối ưu, vì bất kỳ giá trị nào của  đủ nhỏ đều sẽ đáp ứng được điều kiện trên.

Do do, chúng ta sẽ tìm kiếm bắt đầu bằng một giá trị tương đối lớn và liên tục thu nhỏ nó bằng một nhân tố   (0,1) chừng nào điều kiện trên vẫn chưa được đáp ứng.