Các phương pháp tính toán: Từ toán học cổ điển đến trí tuệ nhân tạo

Mở đầu

Các phương pháp tính toán tạo thành nền tảng để giải quyết bài toán trong toán học ứng dụng, khoa học máy tính, kỹ thuật và trí tuệ nhân tạo (Artificial Intelligence). Mỗi phương pháp có một giả định riêng về dữ liệu, không gian nghiệm, mức độ chính xác cần đạt và chi phí tính toán có thể chấp nhận.

Phương pháp tất định (Deterministic) cung cấp nghiệm chính xác khi bài toán có cấu trúc rõ ràng. Phương pháp ngẫu nhiên (Stochastic) cho phép xử lý bài toán lớn hoặc khó mô hình hóa đầy đủ. Phương pháp xấp xỉ (Approximation) chấp nhận sai số có kiểm soát để đổi lấy khả năng tính toán thực tế. Nội suy và ngoại suy (Interpolation and Extrapolation) giúp suy luận từ dữ liệu hữu hạn. Tối ưu hóa (Optimization) đóng vai trò cơ chế tìm nghiệm. Học máy (Machine Learning) và AI kết hợp nhiều cơ chế trên trong một hệ thống học từ dữ liệu.

Mục tiêu của tài liệu không phải là liệt kê thuật toán rời rạc. Trọng tâm là làm rõ logic toán học phía sau từng nhóm phương pháp, điều kiện áp dụng, giới hạn kỹ thuật và lý do vì sao các phương pháp hiện đại, đặc biệt là AI, có thể hoạt động hiệu quả trên dữ liệu thực tế.

I. Phương pháp tất định (Deterministic)

Phần này trình bày nhóm thuật toán có hành vi hoàn toàn xác định. Đây là điểm xuất phát quan trọng vì nó cho thấy khi nào bài toán có thể được giải chính xác, khi nào chi phí tính toán bắt đầu vượt quá khả năng xử lý thực tế và vì sao các phương pháp khác phải xuất hiện.

Một thuật toán là tất định (Deterministic) khi cùng một đầu vào luôn tạo ra cùng một đầu ra theo cùng một chuỗi bước xử lý. Thuật toán không sử dụng yếu tố ngẫu nhiên trong quá trình tính toán.

Định nghĩa hình thức. Thuật toán \(\mathcal{A}\) là tất định nếu tồn tại hàm \(f: \mathcal{X} \to \mathcal{Y}\) sao cho:

với kết quả hoàn toàn xác định.

Ví dụ 1: Giải hệ phương trình tuyến tính (Gaussian Elimination)

Bài toán: tìm \(\mathbf{x}\in\mathbb{R}^n\) thoả \(A\mathbf{x}=\mathbf{b}\), với \(A\in\mathbb{R}^{n\times n}\) và \(\det(A)\ne 0\).

Phép khử Gauss có thể được mô tả thông qua LU Decomposition:

Trong đó \(L\) là ma trận tam giác dưới, \(U\) là ma trận tam giác trên. Nghiệm duy nhất và chính xác là:

Phân tích độ phức tạp: Phép khử Gauss tốn \(\mathcal{O}(n^3)\) phép toán. Với \(n=1000\), số phép tính xấp xỉ \(10^9\). Đây là cách tiếp cận tất định và chính xác tuyệt đối nếu điều kiện số cho phép.

Ví dụ 2: Thuật toán Dijkstra

Bài toán là tìm đường đi ngắn nhất từ nguồn \(s\) đến tất cả đỉnh trong đồ thị \(G=(V,E,w)\), với \(w\ge 0\).

Invariant của Dijkstra:

Khi đỉnh \(v\) được extract khỏi priority queue, \(d[v]\) là chính xác tuyệt đối. Chứng minh được thực hiện bằng quy nạp trên tập \(S\), tức tập các đỉnh đã xét.

Thách thức của Deterministic là curse of dimensionality. Không gian bài toán tăng theo hàm mũ:

Giải chính xác mọi bài toán tổ hợp \(n\) chiều là không khả thi. Ví dụ, Traveling Salesman Problem (TSP) với \(n\) thành phố có không gian tìm kiếm:

và thuộc lớp NP hard.

• Bài toán phù hợp: hệ phương trình tuyến tính, đường đi ngắn nhất, sắp xếp, tìm kiếm nhị phân, FFT, đồ thị DAG.
• Bài toán không phù hợp: bài toán NP hard, không gian trạng thái liên tục \(\mathbb{R}^n\) chiều cao, dữ liệu nhiễu, bài toán học từ dữ liệu.

II. Phương pháp ngẫu nhiên (Stochastic)

Phần này xem xét các phương pháp đưa xác suất vào quá trình tính toán. Cách tiếp cận này phù hợp khi không thể duyệt hết không gian trạng thái, không thể tính tích phân trực tiếp hoặc cần lấy mẫu từ một phân phối phức tạp. Giá trị của stochastic nằm ở khả năng mở rộng, còn giới hạn chính nằm ở phương sai, thời gian hội tụ và độ tin cậy xác suất.

Phương pháp ngẫu nhiên (Stochastic) sử dụng yếu tố xác suất trong quá trình tính toán. Kết quả không còn được xác định tuyệt đối bởi đầu vào, nhưng phương pháp này phù hợp với các bài toán có không gian lớn, nhiều chiều hoặc khó mô hình hóa bằng thuật toán tất định.

Nền tảng toán học: Luật số lớn và CLT

Luật số lớn mạnh (Strong Law of Large Numbers, SLLN). Cho \(X_1,X_2,\ldots\) là các biến ngẫu nhiên iid với \(\mathbb{E}[|X_1|]<\infty\). Khi đó:

Định lý giới hạn trung tâm (Central Limit Theorem, CLT):

Sai số của ước lượng Monte Carlo tỉ lệ \(\sim \sigma/\sqrt{N}\). Điểm quan trọng là sai số này không phụ thuộc trực tiếp vào chiều \(d\).

Ví dụ 1: Monte Carlo Integration

Bài toán là tính:

với \(\Omega\subset\mathbb{R}^d\) phức tạp.

Monte Carlo Estimator:

Sai số chuẩn:

Phương pháp bậc thang (quadrature) tốn \(\mathcal{O}(N^d)\) điểm cho sai số \(\mathcal{O}(N^{-2/d})\). Monte Carlo có sai số \(\mathcal{O}(N^{-1/2})\) bất kể \(d\).

Ví dụ 2: MCMC (Markov Chain Monte Carlo)

Bài toán là lấy mẫu từ phân phối \(\pi(\mathbf{x})\propto p(\mathbf{x})\) khi \(p\) không tính chuẩn hoá được.

Metropolis Hastings:

Chuỗi Markov \(\{X_t\}\) hội tụ đến \(\pi\) nếu thoả detailed balance:

Ergodic Theorem:

Ví dụ 3: Simulated Annealing (Tối ưu ngẫu nhiên)

Xác suất chấp nhận trạng thái xấu hơn:

Khi \(T\to 0\), xác suất chấp nhận trạng thái xấu tiến về 0. Thuật toán hội tụ dần về nghiệm tốt. Chứng minh hội tụ đến tối ưu toàn cục yêu cầu lịch làm nguội loga:

Thách thức của stochastic gồm phương sai lớn, mixing time và tính phụ thuộc vào xác suất. Nếu \(\operatorname{Var}[f]\) lớn, cần \(N\) rất lớn để đạt độ chính xác. MCMC có thể hội tụ chậm nếu phân phối đa đỉnh (multimodal). Không có thuật toán tốt nhất cho mọi bài toán. Cách tiếp cận này đổi determinism lấy scalability, tức đúng với xác suất cao nhưng không chắc chắn tuyệt đối.

III. Phương pháp xấp xỉ (Approximation)

Phần này tập trung vào cách thay thế nghiệm chính xác bằng nghiệm đủ tốt có cơ sở toán học. Đây là hướng tiếp cận quan trọng đối với các bài toán tối ưu tổ hợp, bài toán NP hard và các phép tính số không thể biểu diễn chính xác trong thực tế. Điều cần quan tâm không chỉ là sai số, mà là sai số đó có được kiểm soát hay không.

Phương pháp xấp xỉ (Approximation) không đặt mục tiêu tìm nghiệm chính xác tuyệt đối trong mọi trường hợp. Mục tiêu chính là tìm nghiệm đủ tốt trong thời gian chấp nhận được, đồng thời có thể nêu rõ sai số hoặc tỉ số bảo đảm.

Approximation Algorithm: Lý thuyết

Approximation Ratio. Thuật toán \(\mathcal{A}\) là \(\alpha\)-approximation cho bài toán tối thiểu hoá nếu:

Ví dụ: Vertex Cover (2 approximation)

Gọi \(M\) là matching cực đại tìm được. Mọi cạnh trong \(M\) cần ít nhất một đỉnh cover. Thuật toán chọn cả hai đầu mút của mỗi cạnh trong \(M\):

Vì \(OPT\) cần ít nhất \(|M|\) đỉnh để cover \(|M|\) cạnh rời nhau.

Numerical Approximation: Taylor và Padé

Taylor Series và Error Bound:

Lagrange remainder:

Ví dụ, \(e^x\) xấp xỉ bậc 4 tại \(x=1\):

Approximation qua Fourier: Tín hiệu và Nén

Best \(k\)-term Approximation:

Theo Parseval theorem:

Với tín hiệu âm thanh hoặc hình ảnh, năng lượng tập trung ở tần số thấp dẫn đến việc JPEG và MP3 có thể loại bỏ các hệ số nhỏ mà lỗi tri giác vẫn thấp.

Thách thức của Approximation gồm inapproximability và bias variance. Một số bài toán NP hard có tỉ số xấp xỉ tốt nhất là \(\mathcal{O}(\log n)\), ví dụ Set Cover. Một số bài toán không thể xấp xỉ tốt hơn một tỉ lệ nhất định trừ phi \(P=NP\), theo định lý PCP. Xấp xỉ bậc thấp dẫn đến bias lớn, trong khi xấp xỉ bậc cao có thể dẫn đến không ổn định, điển hình là Runge phenomenon.

IV. Nội suy và ngoại suy (Interpolation and Extrapolation)

Phần này trình bày cách xây dựng hàm từ một tập quan sát hữu hạn. Interpolation phù hợp khi cần tái tạo giá trị trong miền dữ liệu đã biết. Extrapolation khó hơn vì phải dự đoán ngoài vùng quan sát. Do đó, phần này cần được đọc cùng với các khái niệm về sai số, ổn định số và mức độ không chắc chắn.

Cho tập điểm dữ liệu \(\{(x_i,y_i)\}_{i=0}^{n}\), tìm hàm \(p(x)\) sao cho \(p(x_i)=y_i\) với mọi \(i\) trong interpolation hoặc ước lượng \(f\) ngoài phạm vi dữ liệu trong extrapolation.

1. Nội suy Lagrange

Đa thức Lagrange bậc \(n\):

Sai số nội suy:

Hiện tượng Runge: với \(f(x)=1/(1+25x^2)\), điểm nút đều dẫn đến lỗi tăng mạnh ở biên khi \(n\to\infty\).

2. Spline Cubic: Giải pháp thực tế

Cubic Spline yêu cầu điều kiện \(C^2\) liên tục. Trên mỗi đoạn \([x_i,x_{i+1}]\), dùng đa thức bậc 3:

Điều kiện liên tục:

Các điều kiện này dẫn đến hệ tridiagonal \(4n\times 4n\) và có thể giải bằng Thomas algorithm trong \(\mathcal{O}(n)\). Đây là lý do spline được dùng trong thiết kế CAD, font chữ và đồ hoạ vector.

3. Kriging và Gaussian Process Interpolation

Gaussian Process là phiên bản stochastic của nội suy. Nó cung cấp cả giá trị dự đoán lẫn độ không chắc chắn.

GP Posterior:

Posterior sau khi quan sát \(\mathbf{y}=\mathbf{f}+\boldsymbol{\epsilon}\):

Tại điểm đã quan sát, \(\sigma_*=0\), nên nội suy chính xác. Ngoài vùng dữ liệu, \(\sigma_*\) tăng và biểu diễn được mức độ không chắc chắn.

Thách thức của Interpolation gồm Runge phenomenon, overfitting và khả năng mở rộng của GP. Đa thức bậc cao với nút đều không ổn định ở biên. Đi qua mọi điểm không đồng nghĩa với mô hình tốt khi dữ liệu có nhiễu. GP tốn \(\mathcal{O}(n^3)\) do phải nghịch đảo \(K_{XX}\), nên bị hạn chế khi \(n\gt10^4\).

V. Tối ưu hóa (Optimization)

Phần này trình bày Optimization như cơ chế trung tâm của tính toán hiện đại. Nhiều bài toán không chỉ yêu cầu tính một giá trị, mà yêu cầu tìm cấu hình tốt nhất theo một hàm mục tiêu. Trong Machine Learning, Optimization quyết định cách mô hình điều chỉnh tham số để giảm sai số trên dữ liệu huấn luyện.

Bài toán tổng quát:

Gradient Descent và biến thể

Cập nhật Gradient Descent:

Hội tụ với \(f\) là \(L\)-smooth và \(\mu\)-strongly convex:

Tốc độ hội tụ tuyến tính với \(\eta=1/L\). Condition number \(\kappa=L/\mu\) quyết định tốc độ.

SGD (Stochastic Gradient Descent)

SGD là thành phần quan trọng của deep learning:

Mỗi bước tốn \(\mathcal{O}(b)\) thay vì \(\mathcal{O}(n)\). Với \(b\ll n\), tốc độ mỗi bước cao hơn khoảng \(n/b\) lần.

Hội tụ SGD cho bài toán non convex với Lipschitz gradient:

Chọn \(\eta=\mathcal{O}(1/\sqrt{T})\):

Adam Optimizer: Adaptive Moments

Adam sử dụng adaptive learning rate có hiệu chỉnh bias:

Mỗi tham số có learning rate riêng, thích nghi theo lịch sử gradient. Các giá trị mặc định thường dùng là \(\beta_1=0.9\), \(\beta_2=0.999\), \(\epsilon=10^{-8}\).

VI. Học máy (Machine Learning) dưới góc nhìn toán học

Phần này đặt Machine Learning trong quan hệ trực tiếp với các phương pháp đã trình bày trước đó. Machine Learning không tách rời toán học cổ điển. Nó kết hợp Approximation để biểu diễn hàm, Optimization để tìm tham số, Stochastic để học trên dữ liệu lớn và Interpolation để tổng quát hóa từ mẫu quan sát.

Học máy (Machine Learning) là sự kết hợp có hệ thống của nhiều phương pháp tính toán. Neural network đóng vai trò như mô hình xấp xỉ, Gradient Descent cung cấp cơ chế tối ưu, SGD đưa yếu tố ngẫu nhiên vào huấn luyện, còn kernel methods và Gaussian Process liên hệ trực tiếp với nội suy.

1. Học có giám sát: Statistical Learning Theory

Risk và Empirical Risk:

Mục tiêu:

PAC Learning Bound theo VC Theory. Với xác suất \(\ge 1-\delta\), với mọi \(f\in\mathcal{H}\):

Ý nghĩa: Gap giữa train error và test error phụ thuộc vào \(VC(\mathcal{H})\), tức độ phức tạp mô hình, và \(n\), tức số mẫu. Training error thấp chưa đủ. Cần \(n\gg VC(\mathcal{H})\).

2. Neural Network: Universal Approximation

Universal Approximation Theorem (Cybenko 1989, Hornik 1991). Cho hàm kích hoạt \(\sigma\) liên tục, bị chặn và không đa thức. Với mọi \(f\in C([0,1]^d)\) và \(\varepsilon\gt0\), tồn tại mạng 1 lớp ẩn sao cho:

Nhưng tồn tại không nói \(N\) bao nhiêu và làm sao tìm \(\alpha_j\), \(\mathbf{w}_j\), \(b_j\). Deep network giải quyết điều này bằng representation power.

Deep Network:

Lợi thế của depth là mạng \(L\) lớp, mỗi lớp \(n\) units, có thể biểu diễn được hàm cần \(\mathcal{O}(n^L)\) units trong mạng 1 lớp. Các hàm như \(f(x)=\sin(2^nx)\) cần \(\Theta(2^n)\) neurons nếu dùng 1 lớp, nhưng chỉ cần \(\mathcal{O}(n)\) neurons nếu dùng \(n\) lớp bằng cách tổ hợp sin hai lần.

3. Backpropagation: Chuỗi đạo hàm (Chain Rule)

Backprop là Chain Rule được cài đặt hiệu quả:

Định nghĩa \(\delta^{(l)}=\partial\mathcal{L}/\partial z^{(l)}\), tức error signal tại lớp \(l\):

Tổng chi phí là \(\mathcal{O}(L\cdot n^2)\) per sample, tuyến tính theo số layers và không cần tính lại từ đầu. Đây là lý do deep learning khả thi.

4. Attention Mechanism: Transformer

Scaled Dot Product Attention:

Ý nghĩa toán học: \(QK^T/\sqrt{d_k}\) tính ma trận similarity \(\in\mathbb{R}^{n\times n}\). Sau softmax, mỗi token \(i\) nhận weighted sum của tất cả \(V\):

Chia \(\sqrt{d_k}\) giúp tránh dot product quá lớn làm softmax bão hoà, khiến gradient tiến về 0. Complexity là \(\mathcal{O}(n^2d)\), đây là tắc nghẽn chính của LLM.

VII. Heuristic và tri thức kinh nghiệm

Phần này trình bày heuristic như một cách đưa tri thức lĩnh vực vào quá trình tìm kiếm. Heuristic không luôn bảo đảm tối ưu toàn cục, nhưng giúp giảm đáng kể không gian cần khảo sát. Đây là lựa chọn thực tế khi bài toán quá lớn, quá nhiễu hoặc quá phức tạp để giải bằng phương pháp chính xác.

Heuristic là chiến lược tìm kiếm dựa trên tri thức lĩnh vực (domain knowledge). Mục tiêu là cắt giảm không gian tìm kiếm và thu được nghiệm tốt trong thời gian thực tế. Heuristic không phải một thuật toán đơn lẻ. Nó là một nhóm phương pháp nằm giữa Deterministic, Stochastic và Approximation.

Định nghĩa hình thức. Hàm heuristic \(h:\mathcal{S}\to\mathbb{R}_+\) ước lượng chi phí từ trạng thái \(s\) đến đích. Thuật toán heuristic dùng \(h\) để ưu tiên thứ tự khám phá không gian trạng thái \(\mathcal{S}\) thay vì duyệt toàn bộ.

• Constructive Heuristic: Xây dựng nghiệm từ đầu, từng bước chọn lựa tham lam. Ví dụ gồm Greedy và Nearest Neighbor TSP.
• Informed Search: Tìm kiếm có hướng dẫn bởi \(h\). Ví dụ gồm A*, IDA*, RBFS. A* đảm bảo tối ưu nếu \(h\) admissible.
• Local Search: Cải thiện nghiệm hiện tại bằng di chuyển trong lân cận. Ví dụ gồm Hill Climbing, 2 opt và Tabu Search.
• Metaheuristic: Framework cấp cao điều phối local search hoặc population. Ví dụ gồm SA, GA, PSO, ACO và DE.

Nhóm 1: Constructive Heuristic (Deterministic)

Greedy Algorithm tổng quát. Tại mỗi bước, chọn lựa tốt nhất cục bộ theo hàm lựa chọn \(c:\mathcal{C}\to\mathbb{R}\):

Ví dụ Huffman Coding: Greedy chọn 2 node có tần suất thấp nhất để merge. Chứng minh tối ưu bằng exchange argument:

Nếu \(f_i\le f_j\) thì \(d_T(i)\ge d_T(j)\) trong cây tối ưu, dẫn đến Greedy đúng vì swap không cải thiện được.

Ví dụ Nearest Neighbor TSP: Bắt đầu từ thành phố bất kỳ, luôn đến thành phố gần nhất chưa thăm:

Thực nghiệm cho kết quả trong khoảng 10 đến 25% \(OPT\), chạy trong \(\mathcal{O}(n^2)\). Không có bound lý thuyết tốt. Worst case có thể tùy ý xấu hơn \(OPT\).

Nhóm 2: Informed Search: Thuật toán A*

A* là heuristic search hoàn chỉnh và tối ưu nếu heuristic thoả điều kiện admissible. Đây là cầu nối giữa deterministic, tức chính xác, và heuristic, tức nhanh.

Hàm đánh giá A*:

Trong đó \(g(n)\) là chi phí thực từ start đến \(n\), \(h(n)\) là ước lượng chi phí từ \(n\) đến goal, và \(h^*(n)\) là chi phí thực tế tối ưu.

Điều kiện Admissible và Consistent:

Admissible nghĩa là không được ước lượng quá cao, tức optimistic. Consistent là bất đẳng thức tam giác trên \(h\). Consistent suy ra Admissible. Nếu \(h\) consistent thì A* tối ưu và không mở node nào hai lần.

Chứng minh tối ưu của A* với admissible trong tree search. Giả sử A* trả về đường đi \(p\) với chi phí \(C\gt C^*\), trong đó \(C^*\) là \(OPT\). Gọi \(p^*\) là đường tối ưu và \(n\) là node trên \(p^*\) đang chờ trong Open. Tại thời điểm A* chọn goal node:

A* chọn node có \(f\) nhỏ nhất, nên A* phải chọn \(n\) trước goal. Điều này dẫn đến mâu thuẫn.

Complexity worst case là \(\mathcal{O}(b^d)\), với \(b\) là branching factor và \(d\) là depth. Chất lượng heuristic quyết định constant. Nếu \(h\equiv 0\) thì tương đương BFS. Nếu \(h=h^*\) thì complexity xấp xỉ \(\mathcal{O}(d)\).

Ví dụ Manhattan Distance cho 8 puzzle:

Heuristic này admissible vì mỗi tile cần ít nhất Manhattan distance bước để về đúng vị trí, và mỗi bước chỉ di chuyển một ô. Thực nghiệm cho thấy \(h_{\operatorname{Man}}\) mở ít hơn \(h\equiv0\) tới \(10^4\) lần trên các puzzle khó.

Nhóm 3: Local Search và Tabu Search

Hill Climbing: Steepest Ascent:

Trong đó \(\mathcal{N}(s)\) là tập lân cận của trạng thái \(s\). Vấn đề là thuật toán dễ mắc kẹt tại local optimum \(s_{loc}\) với \(f(s_{loc})\lt f(s^*)\).

Ví dụ TSP với 2 opt: \(\mathcal{N}(s)\) là tập tour thu được bằng đổi chỗ 2 cạnh. Mỗi bước cần kiểm tra \(\mathcal{O}(n^2)\) neighbors.

Tabu Search dùng bộ nhớ ngắn hạn để giải quyết local optima bằng cách cấm quay lại trạng thái đã thăm gần đây. Cách này biến deterministic local search thành phương pháp có khả năng thoát local optima.

Tabu Search Framework:

Tabu List lưu \(\tau\) moves hoặc trạng thái gần nhất bị cấm.

Aspiration Criterion: Nếu move tabu nhưng cho nghiệm tốt hơn best so far, vẫn được chấp nhận:

Chọn \(\tau\) cần cân bằng. \(\tau\) nhỏ dễ cycle, còn \(\tau\) lớn có thể làm không gian khám phá bị thu hẹp quá mức. Thực nghiệm thường dùng \(\tau\in[\sqrt{n},n/5]\). Không có lý thuyết hội tụ mạnh. Đây là kinh nghiệm triển khai của Tabu.

Nhóm 4: Evolutionary Algorithms: Genetic Algorithm

Genetic Algorithm lấy cảm hứng từ tiến hoá Darwin. Thuật toán duy trì quần thể nghiệm, áp dụng selection, crossover và mutation để hội tụ về vùng tốt của không gian tìm kiếm.

GA Framework cho một thế hệ:

Fitness proportional selection, hay Roulette Wheel:

1 point crossover. Chọn điểm cắt \(k\sim\operatorname{Uniform}\{1,\ldots,\ell-1\}\):

Bit flip mutation. Mỗi bit lật độc lập với xác suất \(p_m\approx1/\ell\):

Schema Theorem (Holland 1975). Một schema \(H\) là template với ký tự \(\{0,1,*\}\). Định nghĩa \(o(H)\) là order, tức số bit cố định, và \(\delta(H)\) là defining length, tức khoảng cách giữa hai bit cố định ngoài cùng:

Schema ngắn, bậc thấp và fitness cao sẽ tăng số lượng trong quần thể. Đây là Building Block Hypothesis: GA kết hợp các khối cấu trúc tốt để tạo nghiệm tốt hơn.

Giới hạn toán học của GA là Schema Theorem chỉ là lower bound kỳ vọng, không đảm bảo hội tụ toàn cục trong thời gian đa thức. Không có thuật toán tốt nhất cho mọi bài toán. GA không tốt hơn random search trung bình trên mọi bài toán. GA hiệu quả khi bài toán có cấu trúc decomposable, tức fitness phụ thuộc vào các block con độc lập.

Nhóm 5: Swarm Intelligence: PSO và ACO

Particle Swarm Optimization (PSO) mô phỏng hành vi bầy đàn. Mỗi hạt di chuyển trong không gian liên tục, bị thu hút bởi vị trí tốt nhất của bản thân và của cả bầy.

PSO Velocity và Position Update:

Trong đó \(\omega\) là inertia weight, thường giảm từ 0.9 về 0.4. \(c_1,c_2\approx2.0\) là cognitive và social coefficients. \(r_1,r_2\sim\operatorname{Uniform}(0,1)\). \(\mathbf{p}_i\) là personal best và \(\mathbf{g}\) là global best.

Điều kiện hội tụ theo Clerc và Kennedy 2002. Hệ thống PSO ổn định khi:

Hoặc dùng constriction factor:

Ant Colony Optimization (ACO) mô phỏng kiến tìm đường. Pheromone trail tích luỹ trên những đường đi tốt, tạo cơ chế reinforcement learning dạng stigmergy.

ACO xác suất chọn cạnh và cập nhật pheromone. Xác suất kiến \(k\) đi từ \(i\) đến \(j\):

Trong đó \(\tau_{ij}\) là pheromone, \(\eta_{ij}=1/d_{ij}\) là visibility hoặc heuristic, \(\alpha\) và \(\beta\) là trọng số tương đối.

Cập nhật pheromone trong ACS (Ant Colony System):

Trong đó \(\rho\in(0,1)\) là evaporation rate và \(C^k\) là độ dài tour của kiến \(k\). Evaporation giúp tránh stagnation vì pheromone cũ được quên dần.

Phân tích toán học: ACO tương đương với Reinforcement Learning dạng tabular với reward tỉ lệ \(1/C^k\) và temporal discount. Hội tụ đến tối ưu toàn cục có thể chứng minh khi \(t\to\infty\), nhưng tốc độ hội tụ chậm hơn SA về mặt lý thuyết.

Nhóm 6: Hybrid Heuristics: GRASP và Memetic

GRASP (Greedy Randomized Adaptive Search Procedure) gồm hai pha trong mỗi iteration. Pha thứ nhất là construction phase với Restricted Candidate List (RCL):

Thuật toán chọn ngẫu nhiên từ RCL thay vì greedy tuyệt đối. Pha thứ hai là local search phase để cải thiện nghiệm vừa xây được.

Khi \(\alpha=0\), GRASP trở thành Greedy deterministic. Khi \(\alpha=1\), GRASP trở thành random construction. Thực nghiệm thường cho thấy \(\alpha\in[0.2,0.5]\) hoạt động tốt.

Memetic Algorithm là GA kết hợp Local Search:

Sau mỗi crossover hoặc mutation, local search như 2 opt, 3 opt hoặc hill climbing được áp dụng lên từng cá thể trước khi đánh giá fitness. Đây là Lamarckian evolution: kinh nghiệm trong đời, tức local optima, được truyền cho thế hệ sau.

Memetic giảm số thế hệ cần thiết khoảng 10 đến 100 lần so với plain GA nhờ local refinement, đặc biệt trong TSP, VRP và scheduling.

Phân loại tổng hợp: Heuristic Taxonomy

Thách thức chung của Heuristic

Parameter tuning: SA cần lịch làm nguội. GA cần \(\mu\), \(p_c\), \(p_m\). PSO cần \(\omega\), \(c_1\), \(c_2\). Không có lý thuyết tổng quát chọn tham số tối ưu, nên thường cần meta optimization như grid search hoặc Bayesian optimization.

No convergence guarantee: Trừ SA với log schedule và A* với admissible \(h\), phần lớn metaheuristic không có bound hội tụ thực tế. Kết quả phụ thuộc vào random seed và budget, tức số iterations.

Problem specific tuning: ACO cho TSP khác ACO cho scheduling. Việc điều chỉnh \(\mathcal{N}(s)\), encoding và operators cho từng bài toán đòi hỏi domain expertise sâu. Đây là kinh nghiệm thiết kế của metaheuristic.

VIII. Vì sao AI có hiệu quả dưới góc nhìn toán học?

Phần này tổng hợp các lý do toán học giải thích hiệu quả của AI hiện đại. Trọng tâm không nằm ở việc xem AI như một cơ chế đặc biệt, mà ở cách dữ liệu thực tế có cấu trúc, cách mô hình tận dụng cấu trúc đó và cách Optimization tìm được nghiệm có khả năng tổng quát hóa.

Hiệu quả của AI không xuất phát từ một cơ chế đặc biệt duy nhất. Có ít nhất sáu lý do toán học cần được xem xét: cấu trúc thấp chiều của dữ liệu, inductive bias, regularization ngầm của SGD, overparameterization, transfer learning và sự tồn tại của sparse subnetworks.

Lý do 1: Phá vỡ Curse of Dimensionality một phần

Manifold Hypothesis. Dữ liệu thực tế \(\mathbf{x}\in\mathbb{R}^D\), ví dụ ảnh \(224\times224\times3\) dẫn đến \(D\approx150K\), thực sự nằm trên hoặc gần một manifold thấp chiều \(\mathcal{M}\subset\mathbb{R}^D\) với \(\dim(\mathcal{M})=d\ll D\).

Deep network học encoder \(f:\mathbb{R}^{D}\to\mathbb{R}^{d}\) và decoder \(g:\mathbb{R}^{d}\to\mathbb{R}^{D}\). Thay vì làm việc trong \(\mathbb{R}^{150K}\), mô hình thực sự chỉ cần làm việc trong \(\mathbb{R}^{d}\) với \(d\) thường khoảng 10 đến 100.

Lý do 2: Inductive Bias = Prior Knowledge

CNN có translational equivariance:

CNN không cần học riêng đối tượng ở góc trái và đối tượng ở góc phải vì cùng kernel được áp dụng ở mọi nơi. Điều này giảm số tham số từ:

xuống:

nhờ shared weights. Graph Network có \(f\) bất biến hoặc đồng biến với hoán vị node, nên phù hợp dữ liệu đồ thị phân tử và mạng xã hội.

Lý do 3: Implicit Regularization của SGD

SGD có xu hướng tìm nghiệm flat minima. Với loss landscape không lồi, có vô số global minima trong overparameterized networks. SGD ưu tiên nghiệm có Hessian nhỏ:

Sharpness nhỏ nghĩa là flat. Flat minima thường generalize tốt hơn vì nhiễu nhỏ \(\Delta\theta\) làm loss thay đổi ít hơn ở flat region. SGD với noise tự nhiên tỉ lệ \(\sigma^2/b\) có xu hướng drift đến flat minima.

Bayesian interpretation:

Lý do 4: Overparameterization và Double Descent

Bias Variance Decomposition tổng quát:

Lý thuyết cổ điển cho rằng thêm tham số dẫn đến variance tăng và lỗi tăng. Thực tế modern Machine Learning cho thấy Double Descent Phenomenon. Khi số tham số \(p\) vượt qua interpolation threshold \(p\gt n\), tức số mẫu, risk giảm trở lại:

Với \(p\to\infty\) và implicit regularisation, \(R\) có thể tiến về giá trị tốt hơn cả underparameterized regime.

Lý do 5: Transfer Learning và Feature Reuse

Pre training và fine tuning hiệu quả vì feature extractor đã được học trước. Gọi \(\phi:\mathbb{R}^{D}\to\mathbb{R}^{d}\) là feature extractor pre trained. Với task mới, chỉ cần học:

Thay vì:

là bài toán non convex có số chiều \(d\times D+d\times C\). Fine tuning với \(W\) tuyến tính dẫn đến bài toán lồi, trong đó mọi local minimum là global minimum.

Bất đẳng thức sample complexity:

Fine tuning tiết kiệm khoảng \(D/d_{task}\) lần dữ liệu, thường ở mức \(10^2\) đến \(10^4\) lần.

Lý do 6: Lottery Ticket và Sparse Subnetworks

Lottery Ticket Hypothesis (Frankle và Carlin 2019). Trong mạng dày \(f_{\theta}\), tức overparameterized, tồn tại subnetwork \(f_{\theta_s}\), sparse với \(|\theta_s|\ll|\theta|\), và mask \(m\) sao cho:

và khi huấn luyện riêng từ khởi tạo ban đầu:

subnetwork đạt kết quả tương đương. Ý nghĩa là overparameterization không dư thừa hoàn toàn. Nó tạo ra landscape thuận lợi để SGD tìm được subnetwork tốt. Pruning sau đó có thể giảm 80 đến 90% tham số mà chỉ mất dưới 1% accuracy.

Tổng hợp: So sánh định lượng

Không có thuật toán tốt nhất cho mọi bài toán. No Free Lunch Theorem (Wolpert 1996) phát biểu rằng không thuật toán nào tốt nhất trên mọi phân phối bài toán:

AI và Deep Learning hiệu quả vì thế giới thực không phải phân phối đều. Dữ liệu thực có cấu trúc phong phú, bao gồm manifold thấp chiều, tương quan cục bộ và tính đối xứng. Deep network khai thác chính xác cấu trúc đó thông qua inductive bias phù hợp. Nói cách khác, AI có hiệu quả vì dữ liệu thực tế có cấu trúc, không phải vì có một cơ chế toán học đặc biệt duy nhất.

Kết luận

Các phương pháp tính toán không tồn tại độc lập theo nghĩa tuyệt đối. Trong thực tế, một hệ thống có thể kết hợp Deterministic để xử lý các bước có cấu trúc rõ ràng, Stochastic để lấy mẫu hoặc tối ưu trong không gian lớn, Approximation để giảm chi phí, Interpolation để suy luận từ dữ liệu hữu hạn và Heuristic để đưa tri thức lĩnh vực vào quá trình tìm kiếm.

Điểm quan trọng là phải chọn phương pháp theo bản chất của bài toán. Nếu bài toán có nghiệm chính xác và chi phí tính toán chấp nhận được, Deterministic là lựa chọn tự nhiên. Nếu bài toán có không gian trạng thái lớn, dữ liệu nhiễu hoặc phân phối phức tạp, Stochastic và Heuristic thường phù hợp hơn. Nếu bài toán yêu cầu cân bằng giữa độ chính xác và hiệu năng, Approximation và Optimization giữ vai trò trung tâm.

Machine Learning và AI hiện đại có thể được hiểu như sự kết hợp có hệ thống của các nền tảng trên. Mô hình học máy biểu diễn hàm bằng Approximation, cập nhật tham số bằng Optimization, xử lý dữ liệu lớn bằng Stochastic và tận dụng cấu trúc dữ liệu thông qua inductive bias. Vì vậy, AI không thay thế các phương pháp tính toán cổ điển. AI mở rộng các phương pháp đó trong bối cảnh dữ liệu lớn, mô hình nhiều tham số và yêu cầu suy luận phức tạp.

Tài liều được tổng hợp tại: https://iahn.fpt.edu.vn/uploads/computational_methods_1_docx_math_equations_b5f62bab81.pdf 

Khi sử dụng tài liệu này, nên đọc mỗi phương pháp theo ba câu hỏi. Bài toán giả định điều gì. Phương pháp bảo đảm được điều gì. Giới hạn tính toán hoặc giới hạn mô hình nằm ở đâu. Ba câu hỏi này giúp người học tránh xem thuật toán như công thức rời rạc và hiểu đúng vai trò của từng phương pháp trong thiết kế hệ thống tính toán.