Luận Án Tiến Sĩ: Phương Pháp Thực Nghiệm Đánh Giá Độ Phức Tạp Của Các Bài Toán Khó

Luận án tiến sĩ nghiên cứu empirical approach to the complexity of hard problems, phát triển phương pháp mới, đánh giá hiệu quả ứng dụng trong lĩnh vực tại Việt Nam.

• Tác giả: Eugene Nudelman
• Người hướng dẫn: Yoav Shoham, Principal Adviser
• Trường học: Stanford University
• Chuyên ngành: Computer Science
• Đề tài: Empirical Approach to the Complexity of Hard Problems
• Loại tài liệu: dissertation
• Năm xuất bản: 2005
• Địa điểm: Stanford

Mục lục chi tiết

• Abstract
• Acknowledgements
• 1. CHƯƠNG 1: Introduction
• 1.1. Complexity
• 2. CHƯƠNG 2: Empirical Hardness: Models and Applications
• 2.1. Empirical Hardness Methodology
• 2.1.1. Step 1: Selecting an Algorithm
• 2.1.2. Step 2: Selecting an Instance Distribution
• 2.1.3. Step 3: Defining Problem Size
• 2.1.4. Step 4: Selecting Features
• 2.1.5. Step 5: Collecting Data
• 2.1.6. Step 6: Building Models
• 2.2. Analyzing Hardness Models
• 2.2.1. Evaluating the Importance of Variables
• 2.3. Applications of Empirical Hardness Models
• 2.3.1. The Boosting Metaphor
• 2.3.2. Building Algorithm Portfolios
• 2.3.3. Inducing Hard Distributions
• 2.4. Discussion and Related Work
• 2.4.1. Typical-Case Complexity
• 2.4.2. The Boosting Metaphor Revisited
• 3. CHƯƠNG 3: The Combinatorial Auctions WDP
• 3.1. The Winner Determination Problem
• 3.2. Combinatorial Auctions Test Suite
• 3.3. The Issue of Problem Size
• 3.4. Describing WDP Instances with Features
• 3.5. Empirical Hardness Models for the WDP
• 3.6. Analyzing the WDP Hardness Models
• 3.7. Applications of the WDP Hardness Models
• 3.7.1. Inducing Harder Distributions
• 4. CHƯƠNG 4: Understanding Random SAT
• 4.1. The Propositional Satisfiability Problem
• 4.2. Describing SAT Instances with Features
• 4.3. Empirical Hardness Models for SAT
• 4.3.1. Variable-Ratio Random Instances
• 4.3.2. Fixed-Ratio Random Instances
• 4.4. SATzilla: An Algorithm Portfolio for SAT
• 4.5. Conclusion and Research Directions
• 5. CHƯƠNG 5: Computational Game Theory
• 5.1. Game Theory Meets Computer Science
• 5.2. Notation and Background
• 5.3. Finding Nash Equilibria
• 6. CHƯƠNG 6: Evaluating Game-Theoretic Algorithms
• 6.1. The Need for a Testbed
• 6.2. Multiagent Learning in Repeated Games
• 6.3. GAMUT Implementation Notes
• 7. CHƯƠNG 7: Finding a Sample Nash Equilibrium
• 7.1. Searching Over Supports
• 7.2. Algorithm for Two-Player Games
• 7.3. Algorithm for N-Player Games
• 7.4. Results for Two-Player Games
• 7.5. Results for N-Player Games
• 7.6. On the Distribution of Support Sizes
• Bibliography
• List of Tables
• List of Figures

Tóm tắt

I. Phương pháp thực nghiệm

Phương pháp thực nghiệm được sử dụng để nghiên cứu các thuật toán như một hiện tượng tự nhiên. Cách tiếp cận này khác biệt so với phương pháp truyền thống, tập trung vào việc xây dựng các mô hình thống kê chính xác về thời gian chạy của thuật toán trên các bài toán cụ thể. Phương pháp thực nghiệm cho phép đánh giá toàn diện hơn về hiệu suất của thuật toán, thay vì chỉ dựa trên các khái niệm tổng hợp như độ phức tạp trường hợp xấu nhất hoặc trung bình.

1.1. Lựa chọn thuật toán

Bước đầu tiên trong phương pháp thực nghiệm là lựa chọn một thuật toán cụ thể để nghiên cứu. Việc này đòi hỏi sự hiểu biết sâu sắc về các đặc điểm của thuật toán và cách nó xử lý các bài toán khác nhau.

1.2. Lựa chọn phân phối bài toán

Tiếp theo, cần xác định phân phối các bài toán mà thuật toán sẽ được áp dụng. Điều này giúp đảm bảo rằng các mô hình thống kê được xây dựng phản ánh chính xác hiệu suất của thuật toán trong các tình huống thực tế.

II. Đánh giá độ phức tạp

Đánh giá độ phức tạp của các bài toán khó là một phần quan trọng trong nghiên cứu này. Các mô hình thống kê được xây dựng từ phương pháp thực nghiệm giúp phân tích các đặc điểm của bài toán ảnh hưởng đến độ phức tạp. Điều này không chỉ giúp hiểu rõ hơn về bản chất của các bài toán mà còn hỗ trợ trong việc tối ưu hóa thuật toán.

2.1. Xác định kích thước bài toán

Việc xác định kích thước bài toán là yếu tố quan trọng trong đánh giá độ phức tạp. Kích thước bài toán ảnh hưởng trực tiếp đến thời gian chạy và độ phức tạp của thuật toán.

2.2. Lựa chọn đặc trưng

Các đặc trưng của bài toán được lựa chọn để xây dựng mô hình thống kê. Những đặc trưng này giúp phân tích và dự đoán hiệu suất của thuật toán trên các bài toán cụ thể.

III. Bài toán khó

Nghiên cứu tập trung vào các bài toán khó như vấn đề xác định người thắng trong đấu giá tổ hợp và bài toán thỏa mãn công thức Boolean. Các mô hình thống kê được xây dựng từ phương pháp thực nghiệm giúp phân tích các đặc điểm của bài toán ảnh hưởng đến độ phức tạp. Điều này không chỉ giúp hiểu rõ hơn về bản chất của các bài toán mà còn hỗ trợ trong việc tối ưu hóa thuật toán.

3.1. Vấn đề xác định người thắng

Bài toán xác định người thắng trong đấu giá tổ hợp là một trong những bài toán khó được nghiên cứu. Các mô hình thống kê giúp phân tích các yếu tố ảnh hưởng đến độ phức tạp của bài toán này.

3.2. Bài toán thỏa mãn Boolean

Bài toán thỏa mãn công thức Boolean cũng là một bài toán khó được nghiên cứu. Các mô hình thống kê giúp dự đoán thời gian chạy của thuật toán trên các bài toán cụ thể.

IV. Lập chỉ mục ngữ nghĩa ngầm

Lập chỉ mục ngữ nghĩa ngầm (Latent Semantic Indexing - LSI) là một kỹ thuật quan trọng trong việc phân tích và tối ưu hóa nội dung. Kỹ thuật này giúp xác định các từ khóa liên quan và ngữ cảnh của chúng, từ đó cải thiện hiệu quả của các công cụ tìm kiếm. Lập chỉ mục ngữ nghĩa ngầm cũng được áp dụng trong việc phân tích các bài toán khó và đánh giá độ phức tạp của chúng.

4.1. Từ khóa LSI

Các từ khóa LSI được sử dụng để xác định các khái niệm liên quan trong nội dung. Việc sử dụng các từ khóa này giúp cải thiện độ chính xác của các công cụ tìm kiếm và hỗ trợ trong việc phân tích nội dung chuyên sâu.

4.2. Ngữ cảnh liên quan

Việc xác định ngữ cảnh liên quan là yếu tố quan trọng trong lập chỉ mục ngữ nghĩa ngầm. Ngữ cảnh liên quan giúp hiểu rõ hơn về mối quan hệ giữa các từ khóa và nội dung của bài toán.

V. Tối ưu hóa SEO

Tối ưu hóa SEO là một ứng dụng quan trọng của lập chỉ mục ngữ nghĩa ngầm. Việc sử dụng các từ khóa LSI và ngữ cảnh liên quan giúp cải thiện thứ hạng của nội dung trên các công cụ tìm kiếm. Tối ưu hóa SEO cũng hỗ trợ trong việc phân tích và đánh giá độ phức tạp của các bài toán khó.

5.1. Công cụ tìm kiếm

Các công cụ tìm kiếm sử dụng kỹ thuật lập chỉ mục ngữ nghĩa ngầm để cải thiện độ chính xác của kết quả tìm kiếm. Việc hiểu rõ cách các công cụ này hoạt động giúp tối ưu hóa nội dung hiệu quả hơn.

5.2. Nội dung chuyên sâu

Việc tạo ra nội dung chuyên sâu là yếu tố quan trọng trong tối ưu hóa SEO. Nội dung chuyên sâu giúp thu hút người đọc và cải thiện thứ hạng trên các công cụ tìm kiếm.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ của Eugene Nudelman, được bảo vệ tại Khoa Khoa học Máy tính, Đại học Stanford vào tháng 10 năm 2005 dưới sự hướng dẫn của Giáo sư Yoav Shoham cùng hội đồng gồm Giáo sư Andrew Ng và Giáo sư Bart Selman, tập trung vào việc nghiên cứu độ phức tạp tính toán thông qua phương pháp tiếp cận thực nghiệm.

Trong khoa học máy tính truyền thống, các bài toán và thuật toán thường được xem là các đối tượng hình thức trừu tượng, được phân tích thông qua các thước đo độ phức tạp tổng hợp như độ phức tạp trường hợp xấu nhất (worst-case complexity), trường hợp trung bình (average-case complexity) hoặc độ phức tạp làm mịn (smoothed complexity). Tuy nhiên, các chỉ số này chỉ dựa vào kích thước đầu vào và không phản ánh được hiệu năng thực tế trên từng trường hợp bài toán cụ thể (problem instance). Trong thực tế giải các bài toán NP-khó, thời gian chạy của cùng một thuật toán có thể biến thiên nhiều bậc độ lớn giữa các trường hợp có cùng kích thước. Các phương pháp phân tích lý thuyết thường trở nên bất khả thi đối với các thuật toán phức tạp hoặc các bài toán có không gian tham số đa chiều. Khoảng trống nghiên cứu được luận án giải quyết là thiếu một phương pháp luận thực nghiệm có hệ thống để mô hình hóa thống kê thời gian chạy của thuật toán trên từng cá thể, từ đó giải thích các yếu tố cấu trúc gây ra độ khó tính toán, xây dựng danh mục thuật toán (algorithm portfolios) và thiết lập môi trường kiểm thử thực nghiệm chuẩn xác.

Luận án đặt ra và giải quyết 5 mục tiêu nghiên cứu cụ thể:

1. Thiết lập quy trình chuẩn sử dụng kỹ thuật học máy để xây dựng các mô hình thống kê dự đoán chính xác thời gian chạy (empirical hardness models) của một thuật toán cho trước trên từng trường hợp bài toán.
2. Ứng dụng mô hình độ khó thực nghiệm để phân tích các đặc trưng cấu trúc ảnh hưởng đến độ khó tính toán trong hai miền bài toán NP-khó: bài toán xác định người chiến thắng trong đấu giá tổ hợp (Winner Determination Problem - WDP) và bài toán thỏa mãn công thức mệnh đề Boolean (SAT).
3. Hiện thực hóa hai ứng dụng của mô hình độ khó: xây dựng danh mục thuật toán tự động chọn thuật toán tối ưu theo từng trường hợp (như hệ thống SATzilla) và tạo ra các bộ phân phối dữ liệu thử nghiệm khó hơn thông qua kỹ thuật lấy mẫu loại bỏ (rejection sampling).
4. Phát triển bộ công cụ sinh dữ liệu thử nghiệm GAMUT cho lý thuyết trò chơi tính toán nhằm khắc phục sự thiếu hụt dữ liệu chuẩn trong việc đánh giá các thuật toán trò chơi.
5. Kiểm chứng giả thuyết: hầu hết các trò chơi có cấu trúc được quan tâm trong thực tế đều sở hữu cân bằng Nash chiến lược thuần (pure-strategy) hoặc cân bằng với không gian hỗ trợ (support size) rất nhỏ; từ đó thiết kế các thuật toán tìm kiếm cân bằng Nash hiệu quả.

Về đối tượng và phạm vi: Đối tượng nghiên cứu là độ phức tạp thực nghiệm (thời gian chạy thực tế) của các thuật toán giải bài toán tối ưu hóa tổ hợp (WDP), bài toán quyết định (SAT) và bài toán tìm cân bằng Nash trong trò chơi dạng chuẩn (normal-form games). Phạm vi dữ liệu thực nghiệm bao gồm bộ sinh dữ liệu CATS cho đấu giá tổ hợp, các phân phối Uniform Random 3-SAT (tỷ lệ mệnh đề trên biến thay đổi và cố định), dữ liệu cuộc thi SAT-2003, và bộ dữ liệu trò chơi GAMUT được tạo lập trên các cụm tính toán song song tại Đại học Cornell và Đại học Stanford trong giai đoạn 2000–2005.

---

Tổng quan tài liệu và vị trí của luận án

Luận án điểm lại các nền tảng lý thuyết và thực nghiệm then chốt trong lịch sử khoa học máy tính:

• Nền tảng độ phức tạp hình thức: Bắt nguồn từ các nghiên cứu của Church và Turing về mô hình tính toán hình thức, được củng cố bởi công trình của Cook (1971) và Levin (1973) về lý thuyết NP-đầy đủ. Luận án nhấn mạnh nhận định của Cook (1971) rằng việc chỉ dựa vào kích thước đầu vào để đo lường độ phức tạp là quá thô sơ và cần phải tính đến các biến số cấu trúc khác.
• Hiện tượng chuyển pha và độ khó điển hình: Các nghiên cứu thực nghiệm của Cheeseman, Kanefsky và Taylor (1991), Selman, Mitchell và Levesque (1996) đã phát hiện ra mối liên hệ chặt chẽ giữa tỷ lệ số mệnh đề trên số biến trong bài toán k-SAT ngẫu nhiên với xác suất có nghiệm và độ khó thực nghiệm.
• Bài toán lựa chọn thuật toán: Được định nghĩa chính thức bởi Rice (1976), chỉ ra sự cần thiết phải lựa chọn thuật toán phù hợp cho từng bài toán cụ thể thay vì chỉ dựa vào một thuật toán trung bình tốt nhất.
• Khung lý thuyết Boosting: Đề xuất bởi Schapire (1990) trong học máy, tạo cảm hứng cho nguyên lý kết hợp các thuật toán bổ trợ lẫn nhau và tập trung vào các miền bài toán khó.
• Kỹ thuật thống kê và học máy: Các nghiên cứu về hồi quy Least-Angle Regression (LAR) của Efron, Hastie, Johnstone và Tibshirani (2002); lựa chọn tập con đặc trưng của Kohavi và John (1997); thiết kế thí nghiệm thống kê của Mason, Gunst và Hess (2003), Chaloner và Verdinelli (1995); cùng kỹ thuật lấy mẫu loại bỏ của Doucet, de Freitas và Gordon (2001).

Vị trí của luận án: Luận án khắc phục hạn chế của cách tiếp cận phân tích tiệm cận truyền thống vốn không áp dụng được cho từng trường hợp cá thể. Đồng thời, luận án thay thế tư duy đánh giá "kẻ thắng cuộc chiếm tất cả" (winner-take-all) bằng việc phát triển danh mục thuật toán per-instance và khắc phục việc thiếu vắng các bộ dữ liệu kiểm thử chuẩn trong lý thuyết trò chơi tính toán.

---

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

Luận án xây dựng cơ sở lý thuyết dựa trên việc xem thuật toán và bài toán tính toán như các "hiện tượng tự nhiên" (natural phenomena) để thu thập dữ liệu và mô hình hóa thống kê. Độ phức tạp thực nghiệm (empirical complexity / empirical hardness) của trường hợp $I$ đối với thuật toán $A$ được định nghĩa là thời gian chạy thực tế của bản cài đặt thuật toán $A$ khi nhận đầu vào $I$.

Phương pháp nghiên cứu thực nghiệm định lượng bao gồm quy trình 6 bước có hệ thống:

Bước 1: Chọn thuật toán khảo sát (Xem như hộp đen)
Bước 2: Chọn phân phối các trường hợp bài toán (Bộ sinh nhân tạo hoặc dữ liệu thực tế)
Bước 3: Xác định kích thước bài toán (Cố định để tìm đặc trưng ẩn hoặc cho phép biến thiên)
Bước 4: Trích xuất tập đặc trưng cấu trúc (Tính toán trong thời gian đa thức bậc thấp)
Bước 5: Thu thập dữ liệu trên cụm máy tính song song (Quản lý thời gian chặn - captime)
Bước 6: Xây dựng mô hình hồi quy thống kê (Hồi quy tuyến tính, bậc hai, log, hàm mũ, logistic)

Thành phần phương pháp	Quy cách và kỹ thuật cụ thể trong luận án
Không gian giả thuyết hồi quy	Mô hình tuyến tính cơ sở $\sum w_i f_i$; mở rộng bậc hai bằng tích từng cặp đặc trưng $\sum w_{ij} f_i f_j$; biến đổi phi tuyến hàm mũ $h(y) = 10^y$ và logistic $h(y) = 1/(1 + e^{-y})$ cho dữ liệu bị giới hạn thời gian (capped runs).
Hàm mục tiêu và tối ưu hóa	Tối thiểu hóa sai số căn bậc hai trung bình (Root Mean Squared Error - RMSE); sử dụng ma trận nghịch đảo giải trong thời gian xấp xỉ bậc ba $O(n^3)$.
Kỹ thuật chọn tập con đặc trưng	Tìm kiếm vét cạn (với số biến nhỏ), Forward selection, Backward elimination, Sequential replacement, và Least-Angle Regression (LAR).
Đánh giá tầm quan trọng đặc trưng	Phương pháp Chi phí loại bỏ (Cost of omission) trên tập kiểm định chéo: $\text{score}(f_i)$, chuẩn hóa đặc trưng quan trọng nhất về thang điểm 100.
Tính toán đặc trưng thông minh	Phân cấp đặc trưng thành các tập $S_1, \dots, S_k$ theo độ phức tạp thời gian; chỉ tính toán tập tiếp theo nếu lợi ích giảm thời gian dự đoán vượt qua chi phí tính toán $c(S_j)$.
Thước đo danh mục thuật toán	Thời gian chạy trung bình (Average runtime), Tỷ lệ phần trăm tối ưu (Percent optimal), Tỷ lệ phần trăm dưới tối ưu trung bình (Average percent suboptimal).

Nguồn dữ liệu: Dữ liệu thực nghiệm được thu thập từ cụm máy tính "zippies" tại Đại học Cornell và cụm máy tính "Nashes" tại Đại học Stanford, sử dụng các phần mềm giải toán CPLEX (cho WDP), kcnfs, satz, oksolver (cho SAT), Lemke-Howson, Govindan-Wilson và Simplicial Subdivision (cho lý thuyết trò chơi).

---

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

Chương 1: Giới thiệu (Introduction)

Chương 1 phân tích sự hình thành của lý thuyết độ phức tạp tính toán từ các nghiên cứu nền tảng của Cook và Levin. Tác giả chỉ ra hạn chế của các thước đo độ phức tạp tổng hợp truyền thống (worst-case, average-case) khi xem thuật toán là thứ yếu so với bài toán. Luận án đề xuất góc nhìn bổ trợ: coi bài toán, phân phối dữ liệu và thuật toán là một bộ ba hiện tượng tự nhiên cần được nghiên cứu bằng phương pháp thực nghiệm để đo lường thời gian chạy trên từng trường hợp cụ thể. Cấu trúc luận án được chia làm hai phần chính: Phần I xem "Thuật toán là đối tượng nghiên cứu" (Chương 2, 3, 4) và Phần II xem "Thuật toán là công cụ khám phá cấu trúc bài toán" (Chương 5, 6, 7).

Chương 2: Độ phức tạp thực nghiệm: Mô hình và ứng dụng (Empirical Hardness: Models and Applications)

Chương 2 trình bày chi tiết phương pháp luận 6 bước để xây dựng mô hình độ khó thực nghiệm. Chương phân tích các kỹ thuật hồi quy có giám sát (tuyến tính, bậc hai, hàm mũ, logistic) và phương pháp đánh giá tầm quan trọng của biến thông qua việc lựa chọn tập con đặc trưng và tính toán chi phí loại bỏ. Dựa trên ẩn dụ Boosting của Schapire, chương phát triển hai ứng dụng then chốt:

1. Xây dựng danh mục thuật toán (algorithm portfolios) kết hợp các thuật toán có thời gian chạy không tương quan, áp dụng cơ chế tính toán đặc trưng thông minh (smart feature computation).
2. Tạo lập phân phối kiểm thử khó (inducing hard distributions) bằng kỹ thuật lấy mẫu loại bỏ từ phân phối tích $D \cdot h_P$, sử dụng mô hình dự đoán độ khó trong không gian tham số $H_p$ để định hướng sinh dữ liệu.

Chương 3: Bài toán xác định người chiến thắng trong đấu giá tổ hợp (The Combinatorial Auctions WDP)

Chương 3 áp dụng phương pháp luận của Chương 2 vào bài toán xác định người chiến thắng trong đấu giá tổ hợp (WDP) - một bài toán tối ưu hóa NP-khó. Dữ liệu thử nghiệm được tạo từ bộ sinh CATS (Combinatorial Auctions Test Suite) với bộ giải chuẩn CPLEX.

Luận án trích xuất các nhóm đặc trưng đa thức từ đồ thị giá thầu (bid graph) và đồ thị giá thầu - hàng hóa (bid-good graph). Kết quả thực nghiệm cho thấy mô hình hồi quy bậc hai và mô hình hàm mũ dự đoán chính xác thời gian chạy của CPLEX (đạt hệ số xác định hiệu chỉnh $R^2$ cao). Phân tích chi phí loại bỏ chỉ ra các đặc trưng cấu trúc đồ thị chi phối mạnh nhất đến độ khó. Ứng dụng thực tế:

• Xây dựng danh mục thuật toán kết hợp CPLEX với các thuật toán chuyên biệt, đạt tốc độ giải nhanh hơn gấp 3 lần so với việc chỉ sử dụng riêng CPLEX.
• Tinh chỉnh các tham số phân phối của CATS để sinh ra các tập dữ liệu có độ khó tính toán cao hơn đáng kể so với phân phối mặc định.

Chương 4: Thấu hiểu bài toán SAT ngẫu nhiên (Understanding Random SAT)

Chương 4 kiểm chứng phương pháp luận trên bài toán thỏa mãn công thức mệnh đề Boolean (SAT). Khảo sát được thực hiện trên ba bộ giải SAT: kcnfs, oksolver và satz trên hai phân phối: Uniform Random 3-SAT có tỷ lệ số mệnh đề trên số biến biến thiên (variable-ratio) và tỷ lệ cố định tại điểm chuyển pha (fixed-ratio, $m/n \approx 4.26$).

Mô hình học máy tự động nhận diện và trích xuất các đặc trưng quan trọng nhất phản ánh độ khó mà không cần can thiệp thủ công, bao gồm hệ số phân cụm có trọng số trên đồ thị mệnh đề (clause graph clustering coefficient) và các đặc trưng tìm kiếm DPLL. Luận án xây dựng danh mục thuật toán SATzilla, tham gia cuộc thi SAT-2003 ở các hạng mục Random và Handmade, chứng minh hiệu quả vượt trội so với từng thuật toán thành phần đơn lẻ.

Chương 5: Lý thuyết trò chơi tính toán (Computational Game Theory)

Chương 5 chuyển sang Phần II của luận án, thiết lập cầu nối giữa lý thuyết trò chơi và khoa học máy tính. Chương giới thiệu các khái niệm hình thức về trò chơi dạng chuẩn (normal-form games), không gian chiến lược của người chơi, ma trận chi trả và định nghĩa cân bằng Nash (Nash Equilibrium - NE). Tác giả phân tích độ phức tạp tính toán của việc tìm kiếm một cân bằng Nash mẫu trong trò chơi 2 người và trò chơi $N$ người, chỉ ra tính chất phi tuyến và thách thức tổ hợp khi không gian chiến lược mở rộng.

Chương 6: Đánh giá các thuật toán trong lý thuyết trò chơi (Evaluating Game-Theoretic Algorithms)

Chương 6 chỉ ra thực trạng thiếu vắng một bộ công cụ kiểm thử toàn diện trong cộng đồng lý thuyết trò chơi tính toán, nơi các thuật toán trước đây chủ yếu được thử nghiệm trên các trò chơi ngẫu nhiên thuần túy (uniformly random games). Tác giả giới thiệu GAMUT — bộ sinh dữ liệu trò chơi toàn diện bao gồm nhiều lớp trò chơi kinh điển và trò chơi có cấu trúc (như Covariance Games, Prisoner's Dilemma, Coordination Games, v.v.). Luận án tiến hành chuẩn đối sánh (benchmarking) các thuật toán tính cân bằng Nash hiện có (Lemke-Howson, Simplicial Subdivision, Govindan-Wilson) và các thuật toán học đa tác tử (multiagent learning) trong trò chơi lặp, chỉ ra sự biến thiên hiệu năng rất lớn giữa các lớp trò chơi khác nhau.

Chương 7: Tìm kiếm cân bằng Nash mẫu (Finding a Sample Nash Equilibrium)

Chương 7 đề xuất hai thuật toán tìm kiếm cân bằng Nash mẫu dựa trên phương pháp duyệt không gian hỗ trợ (searching over supports):

• Thuật toán 1 (Algorithm 1): Dành cho trò chơi 2 người (2-player games).
• Thuật toán 2 (Algorithm 2): Dành cho trò chơi $N$ người ($N$-player games).

Cả hai thuật toán đều áp dụng cơ chế thiên vị tìm kiếm (bias) vào các không gian hỗ trợ có kích thước nhỏ và cân bằng giữa các người chơi, kết hợp kỹ thuật quay lui (backtracking). Thử nghiệm trên các lớp trò chơi của GAMUT cho thấy:

• Trên trò chơi 2 người, 300 hành động: Thuật toán 1 vượt trội thuật toán Lemke-Howson về thời gian chạy trung vị vô điều kiện (unconditional median runtime) và tỷ lệ giải thành công.
• Trên trò chơi 6 người, 5 hành động: Thuật toán 2 vượt trội so với Simplicial Subdivision và Govindan-Wilson.
• Kết quả thực nghiệm xác nhận quy luật phân phối kích thước hỗ trợ: phần lớn các trò chơi có cấu trúc trong thực tế đều có cân bằng chiến lược thuần hoặc cân bằng hỗn hợp với kích thước hỗ trợ rất nhỏ.

---

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận

• Đưa ra quan điểm phương pháp luận mới: xem thuật toán và bài toán là các hiện tượng tự nhiên có thể mô hình hóa thông qua các phương pháp thực nghiệm thống kê định lượng, bổ khuyết cho cách tiếp cận phân tích tiệm cận truyền thống.
• Làm sáng tỏ các đặc trưng cấu trúc quyết định độ khó tính toán thực tế của bài toán WDP và SAT, vượt ra ngoài khái niệm kích thước bài toán đơn thuần.
• Chứng minh bằng thực nghiệm rằng không gian hỗ trợ của cân bằng Nash trong hầu hết các trò chơi có cấu trúc là rất nhỏ, giải thích lý do các thuật toán tìm kiếm cục bộ đơn giản có thể hoạt động hiệu quả trên các trò chơi quy mô lớn.

Đóng góp về mặt thực tiễn

• Đề xuất và chuẩn hóa quy trình 6 bước xây dựng mô hình độ khó thực nghiệm sử dụng các kỹ thuật hồi quy có giám sát kết hợp chọn lọc đặc trưng.
• Xây dựng danh mục thuật toán SATzilla cho bài toán SAT và danh mục thuật toán cho WDP, cải thiện tốc độ xử lý lên gấp 3 lần so với bộ giải CPLEX đơn lẻ.
• Phát triển và công bố công khai bộ sinh dữ liệu trò chơi GAMUT (http://gamut.stanford.edu), cung cấp bộ công cụ kiểm thử chuẩn cho cộng đồng nghiên cứu hệ đa tác tử và lý thuyết trò chơi.
• Đề xuất hai thuật toán tìm kiếm cân bằng Nash mẫu (Algorithm 1 và Algorithm 2) đạt hiệu năng thực nghiệm cao hơn các thuật toán tiêu chuẩn như Lemke-Howson, Govindan-Wilson và Simplicial Subdivision trên các tập dữ liệu có cấu trúc.

---

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

Dựa trên các nội dung được văn bản đề cập, luận án tồn tại một số giới hạn và mở ra các hướng phát triển:

• Giới hạn thuật toán: Phương pháp xây dựng mô hình độ khó thực nghiệm áp dụng trực tiếp cho các thuật toán tìm kiếm đầy đủ hoặc ngẫu nhiên có điều kiện dừng rõ ràng; chưa áp dụng trực tiếp cho các thuật toán không đầy đủ (incomplete algorithms / local search) do các thuật toán này thiếu điều kiện dừng tự nhiên khi không tìm thấy nghiệm trên bài toán tối ưu hoặc bài toán không thỏa mãn.
• Giới hạn mô hình: Mô hình học máy tạo ra mang tính đặc thù theo từng thuật toán (algorithm-specific) và phụ thuộc vào phân phối dữ liệu huấn luyện, không thể tự động tổng quát hóa sang các phân phối hoàn toàn khác nếu không được huấn luyện lại.
• Chi phí thu thập dữ liệu: Việc thu thập dữ liệu huấn luyện đòi hỏi tài nguyên tính toán lớn trên các cụm máy tính song song; kỹ thuật giới hạn thời gian chạy (capping runs) cần được xử lý cẩn trọng bằng các biến đổi phi tuyến (như logistic) để tránh làm sai lệch mô hình.
• Hướng nghiên cứu tiếp: Mở rộng phương pháp mô hình hóa sang các thuật toán không đầy đủ; nghiên cứu sâu hơn về các đặc trưng cấu trúc để làm tiền đề cho các chứng minh lý thuyết hình thức; và tích hợp thêm các bộ giải mới vào danh mục SATzilla.

---

Giá trị tham khảo

Luận án là tài liệu tham khảo hữu ích cho các nhóm đối tượng nghiên cứu chuyên ngành:

• Nghiên cứu sinh và nhà nghiên cứu Trí tuệ Nhân tạo / Tối ưu hóa Tổ hợp: Tham khảo phương pháp luận 6 bước tại Chương 2 để xây dựng mô hình dự đoán hiệu năng thuật toán, kỹ thuật lựa chọn đặc trưng bằng LAR và chi phí loại bỏ, cùng kiến trúc xây dựng danh mục thuật toán tối ưu.
• Giảng viên và chuyên gia Thiết kế Thuật toán: Sử dụng phương pháp lấy mẫu loại bỏ để sinh các bộ dữ liệu kiểm thử khó, hỗ trợ đánh giá khách quan các thuật toán mới thay vì phương pháp so sánh trung bình truyền thống.
• Cộng đồng Lý thuyết Trò chơi Tính toán và Hệ Đa tác tử: Ứng dụng bộ công cụ GAMUT (Chương 6) làm môi trường kiểm thử chuẩn và tham khảo thuật toán tìm kiếm cân bằng Nash theo không gian hỗ trợ (Chương 7) để giải quyết các trò chơi quy mô lớn trong thực tế.

---

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

1. Tại sao luận án lại coi thuật toán và bài toán là "hiện tượng tự nhiên" thay vì các đối tượng hình thức?

Trong phân tích truyền thống, thuật toán được xem là các đối tượng toán học hình thức và được đánh giá qua các chặn tiệm cận lý thuyết (như $O(n)$). Tuy nhiên, trên các bài toán NP-khó thực tế, thời gian chạy giữa các trường hợp có cùng kích thước biến thiên nhiều bậc độ lớn và rất khó giải thích bằng phân tích giải tích thuần túy. Luận án xem thuật toán, phân phối dữ liệu và không gian bài toán như một hệ thống tự nhiên phức tạp để áp dụng phương pháp nghiên cứu thực nghiệm: thu thập dữ liệu chạy thực tế, đo đạc các thuộc tính cấu trúc và khai phá dữ liệu để xây dựng các mô hình thống kê định lượng.

2. Mô hình độ khó thực nghiệm xử lý dữ liệu từ các trường hợp bị dừng sớm (capped runs) như thế nào?

Khi thu thập dữ liệu trên các trường hợp bài toán cực khó, việc chờ thuật toán chạy đến khi hoàn tất có thể mất nhiều ngày hoặc không khả thi. Luận án áp dụng kỹ thuật chặn thời gian chạy ở một ngưỡng tối đa (captime). Để mô hình hóa chính xác mà không làm sai lệch dự đoán, tác giả sử dụng hàm logistic $h(y) = 1/(1 + e^{-y})$ (với $y$ được ánh xạ về khoảng $(0,1)$) hoặc mô hình hàm mũ $h(y) = 10^y$, giúp giới hạn miền giá trị dự đoán và biến đổi các giá trị sai số tuyến tính phù hợp với phân phối thời gian thực tế.

3. Kỹ thuật "Tính toán đặc trưng thông minh" (Smart Feature Computation) trong danh mục thuật toán hoạt động ra sao?

Để tránh việc thời gian trích xuất đặc trưng lâu hơn thời gian chạy của chính thuật toán, luận án phân vùng các đặc trưng thành các tập $S_1, \dots, S_k$ sắp xếp theo độ phức tạp tính toán tăng dần. Danh mục thuật toán sẽ tính toán tập đặc trưng dễ nhất $S_1$ trước, sau đó sử dụng một mô hình ước lượng chi phí $c(S_j)$ và mô hình sai khác hiệu năng $D_j$ để đánh giá: nếu mức độ cải thiện dự kiến về thời gian chạy của thuật toán được chọn lớn hơn chi phí tính toán tập đặc trưng tiếp theo, hệ thống mới tiếp tục tính toán $S_{j+1}$; ngược lại sẽ ra quyết định chọn thuật toán ngay lập tức.

4. Bộ công cụ GAMUT giải quyết vấn đề gì trong lý thuyết trò chơi tính toán?

Trước khi có GAMUT, các thuật toán trong lý thuyết trò chơi chủ yếu được đánh giá trên các trò chơi ngẫu nhiên phân phối đều (uniformly random games), vốn không đại diện cho các tương tác chiến lược trong thực tế. GAMUT cung cấp một bộ sinh dữ liệu toàn diện bao gồm hàng loạt lớp trò chơi có cấu trúc kinh điển (như trò chơi hiệp đồng, song đề tù nhân, trò chơi ma trận hiệp phương sai), cho phép các nhà nghiên cứu kiểm thử thuật toán trên nhiều phân phối dữ liệu đa dạng và phản ánh đúng hiệu năng thực tế.

5. Thuật toán tìm kiếm cân bằng Nash trong Chương 7 dựa trên nguyên lý then chốt nào để vượt qua các thuật toán truyền thống?

Thuật toán 1 (cho trò chơi 2 người) và Thuật toán 2 (cho trò chơi $N$ người) khai thác phát hiện thực nghiệm rằng các trò chơi có cấu trúc trong thực tế hầu như luôn có cân bằng Nash với không gian hỗ trợ (tập các hành động có xác suất chọn dương) rất nhỏ và cân bằng giữa các người chơi. Thuật toán tổ chức tìm kiếm có định hướng (bias), ưu tiên duyệt qua các tập hỗ trợ từ nhỏ đến lớn kết hợp với thủ tục quay lui (backtracking) và kiểm tra tính khả thi bằng quy hoạch toán học, giúp tìm ra cân bằng nhanh hơn đáng kể so với thuật toán Lemke-Howson hay Govindan-Wilson.

---

Kết luận

Luận án của Eugene Nudelman đã thiết lập phương pháp luận mô hình hóa thống kê để phân tích độ phức tạp thực nghiệm của các bài toán NP-khó và thuật toán giải. Bằng việc kết hợp kỹ thuật hồi quy học máy, luận án giải thích thành công nguồn gốc độ khó cấu trúc trong bài toán đấu giá tổ hợp (WDP) và bài toán SAT, đồng thời hiện thực hóa các ứng dụng quan trọng như danh mục thuật toán SATzilla và phương pháp sinh dữ liệu thử nghiệm khó. Trong lĩnh vực lý thuyết trò chơi tính toán, tác giả đã đóng góp bộ công cụ kiểm thử GAMUT và chứng minh rằng các trò chơi có cấu trúc thực tế chủ yếu sở hữu cân bằng Nash với không gian hỗ trợ nhỏ, mở ra hướng tiếp cận tìm kiếm cân bằng hiệu quả trên quy mô lớn.

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

NOTE TO USERS This reproduction is the best copy available. ® UMI EMPIRICAL APPROACH TO THE COMPLEXITY OF HARD PROBLEMS A DISSERTATION SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Eugene Nudelman October 2005 UMI Number: 3197488 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3197488 Copyright 2006 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © Copyright by Eugene Nudelman 2006 All Rights Reserved il I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. V Yoav Shoham Principal Adviser I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. DL NY Andrew Ng Ũ I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.

3 %~= Bart Selman (Computer Science Department, Cornell University) Approved for the University Committee on Graduate Studies. ili To my parents and grandparents 1V Abstract Traditionally, computer scientists have considered computational problems and al- gorithms as artificial formal objects that can be studied theoretically. In this work we propose a different view of algorithms as natural phenomena that can be studied using empirical methods. In the first part, we propose a methodology for using ma- chine learning techniques to create accurate statistical models of running times of a given algorithm on particular problem instances.

Rather than focus on the traditional aggregate notions of hardness, such as worst-case or average-case complexity, these models provide a much more comprehensive picture of algorithms’ performance. We demonstrate that such models can indeed be constructed for two notoriously hard domains: winner determination problem for combinatorial auctions and satisfiability of Boolean formulae. In both cases the models can be analyzed to shed light on the characteristics of these problems that make them hard. We also demonstrate two con- crete applications of empirical hardness models.

First, these models can be used to construct efficient algorithm portfolios that select correct algorithm on a per-instance basis. Second, the models can be used to induce harder benchmarks. In the second part of this work we take a more traditional view of an algorithm as a tool for studying the underlying problem. We consider a very challenging problem of finding a sample Nash equilibrium (NE) of a normal-form game.

For this domain, we first present a novel benchmark suite that is more representative of the problem than traditionally-used random games. We also present a very simple search algorithm for finding NEs. The simplicity of that algorithm allows us to draw interesting conclusions about the underlying nature of the problem based on its empirical performance. In particular, we conclude that most structured games of interest have either pure- strategy equilibria or equilibria with very small supports.

Acknowledgements None of the work presented in this thesis would have been possible without many people who have continuously supported, guided, and influenced me in more ways than I can think of. Above all I am grateful to Yoav Shoham, my advisor. Yoav gave me something invaluable for a graduate student: an enormous amount of freedom to choose what I want to do and how do I want to do it.