“Học máy” từ góc nhìn của lý thuyết tính toán (2)

Ngô Quang Hưng | 10 tháng 07, 2008 | Bản để in Bản để in

Trong bài trước ta đã định nghĩa cụ thể mô hình nhất quán. Có một vài điểm tinh tế cần nói rõ hơn.

Thứ nhất, tổng số concepts trong lớp concepts đã biết \mathcal C thường là rất lớn, có thể là hàm mũ của m, có thể vô hạn. Thứ hai, khi ta nói thuật toán ML cần “đưa ra” một giả thuyết h \in \mathcal C thì ta đã ngầm định một cách biểu diễn h nào đó. Nhớ rằng, mỗi concept là một hàm số từ \Omega vào \{0,1\}. Kích thước của \Omega rất lớn (như tổng số emails trong bài spam classification), không thể nào biểu diễn một concept bằng một lookup table được. Tổng số các concepts có thể có là 2^{|\Omega|}, do đó “chặn thông tin” (information theoretic bound) cho ta biết sẽ có rất nhiều concepts cần ít nhất \Theta(|\Omega|) bits để biểu diễn, không thể nhỏ hơn. (Đấy là trường hợp domain hữu hạn, nếu vô hạn thì còn tệ hơn nữa.)

Vì thế, yêu cầu “khái niệm đang học thuộc về một lớp các khái niệm cho trước” là cần thiết. Nói cách khác, lớp các khái niệm cho trước này phải “vừa vừa phải phải” thôi, phức tạp quá ai mà học cho được! Nhắc lại, ta ngầm định rằng khi nói “cho trước \mathcal C” ta cũng “cho” luôn cả một cách biểu diễn một khái niệm bất kỳ trong \mathcal C. Khái niệm cần học c có biểu diễn kích thước |c|.

Thứ hai, ta giả sử mỗi phần tử của \Omega có thể biểu diễn bằng \Theta(n) bits. Ví dụ, \Omega có thể là \mathbb R^n hoặc một vector gồm n từ khóa trong một email.

Thứ ba, khi yêu cầu thuật toán ML chạy trong thời gian đa thức, ta muốn nói là đa thức của các tham số m (tổng số examples trong training set), n (kích thước một phần tử trong domain), và |c| (kích thước của biểu diễn khái niệm đang học).

Đoạn trên có lẽ là khó hiểu khi đọc lần đầu. Tôi viết xong rồi cũng không hiểu thế nào là “cho trước”?. Ta hãy xét một vài ví dụ, sau đó bạn đọc quay lại đoạn ở trên chắc là sẽ thấy dễ hiểu hơn.

2.1 Lớp khái niệm Boolean Conjunctions có thể học được trong mô hình nhất quán

Giả sử Windows Vista của bạn cứ crash liên tục. Bạn có một log file ghi lại trạng thái của hệ thống mỗi lần bật máy. Trong log file này có các biến số như: “MS Word đang chạy”, “Firefox tắt”, “IE đang chạy”, vân vân. Trong log file chứa thông tin về m lần chạy, có lần bị crash, lần không. Có tổng cộng n biến số. Bạn muốn biết tổ hợp của các biến nào làm cho máy crash. Đó chính là bài toán sau đây trong mô hình nhất quán.

Lớp khái niệm (cho trước) \mathcal C là tập hợp tất cả các công thức Bool có dạng

\varphi = x_{i_1} \wedge \bar x_{i_2} \wedge \bar x_{i_3} \wedge \cdots \wedge x_{i_q}, \ \ 1\leq q \leq n

các công thức dạng này gọi là các Boolean conjunctions. Mỗi công thức là “AND” của một mớ các literals (tức là các biến và phủ định của chúng). Công thức ta cần học (hy vọng) sẽ xác định tổ hợp các trạng thái nào của hệ thống làm crash máy. (”MS Word” đang chạy và “Excel” không chạy và “BitTorrent” đang chạy, v.v.)

Training data sẽ có dạng kiểu như sau:


\begin{array}{ccccc||c} x_1&x_2&x_3&x_4&x_5&c(\mathbf x)\\ \hline 1&1&0&0&1&1\\ 1&0&1&0&0&0\\ 0&1&0&0&1&1\\ 1&1&0&1&1&1\\ 0&1&1&1&1&0 \end{array}

Từ đó, thuật toán ML của ta sẽ phải đưa ra giả thuyết kiểu như h = x_2\wedge \bar x_3. Đây rõ ràng là một bài toán thiết kế một thuật toán mang tính tổ hợp, không phải thiết kế một thuật toán mang tính xác suất thống kê. Thuật toán tìm (hoặc trả lời là không tồn tại) giả thuyết nhất quán với training data cho bài này rất đơn giản: (bước 1) tìm tất cả các literals có giá trị bằng 1 trong tất cả các hàng mà c(\mathbf x)=1; giả thuyết của chúng ta sẽ là AND (hay conjunction) của tất cả các literals náy; (bước 2) nhìn vào các hàng có c(\mathbf x)=0 xem có hàng nào mâu thuẫn với giả thuyết không; nếu không thì thuật toán đưa giả thuyết này làm câu trả lời, nếu có mâu thuẫn thì trả lời là không tồn tại giả thuyết nào nhất quán với data. Trong ví dụ trên thì thuật toán này sẽ trả về giả thuyết h = x_2\wedge \bar x_3 \wedge x_5. Chú ý rằng đây không phải là giả thuyết duy nhất nhất quán với data, và cũng không phải là giả thuyết “ngắn gọn” nhất.

Bài tập: (i) chứng minh rằng thuật toán trên làm việc đúng ý ta muốn. (ii) giả thuyết nhất quán với data và chứa ít literals nhất trong ví dụ trên là giả thuyết nào? (iii) Nếu ta muốn tìm giả thuyết ngắn nhất và nhất quán với data thì bài toán này có lời giải hiệu quả trong thời gian đa thức không?

2.2 Lớp khái niệm k-Term DNF KHÔNG THỂ học được trong mô hình nhất quán, với mọi k ≥ 2

Lớp khái niệm này được định nghĩa như sau: nó bao gồm tất cả các Boolean formulae có dạng dưới đây, trong đó k là một số nguyên ≥ 2 cho trước:

\varphi = \underbrace{( \bullet \wedge \dots \wedge \bullet)}_{\text{term $1$}} \vee \underbrace{( \bullet \wedge \dots \wedge \bullet)}_{\text{term $2$}} \vee \dots \vee \underbrace{( \bullet \wedge \dots \wedge \bullet)}_{\text{term $k$}}

Các công thức Bool có dạng trên gọi là công thức ở dạng k-Term DNF

Để chứng minh rằng lớp khái niệm này không học được, ta sẽ chứng mình rằng bài toán xác định xem có tồn tại một một công thức Bool dạng k-Term DNF nhất quán với data hay không là bài toán NP-Hard. Tôi sẽ chỉ phác thảo đại ý chứng minh này ở đây với k=3 thôi. Ta sẽ chuyển giản (reduce) bài toán 3-coloring về bài toán đang xét. Xét một instance G=(V,E) của bài toán 3-coloring. Ta xây dựng một training data set như sau. Mỗi đỉnh v của đồ thị tương ứng với một biến Bool x_v. Bảng training data (giống bảng trong đề mục 2.1) sẽ có các hàng mà c(\mathbf x)=1 tạm gọi là hàng-1, và các hàng mà c(\mathbf x)=0 gọi là hàng-0 cho tiện. Sẽ có tổng cộng |V| hàng-1 và |E| hàng-0. Với mỗi đỉnh v của đồ thị, tạo một hàng-1 bằng cách gán x_v=0, x_{u}=1, \forall u\neq v. Với mỗi cạnh uv của đồ thị, tạo một hàng-0 bằng cách gán x_u=x_v=0, x_w=1, \forall w\neq u,v. Đồ thị G tô được bằng 3 màu nếu và chỉ nếu tồn tại một công thức k-Term DNF nhất quán với bảng training data vừa xây dựng.

Bài tập: giả sử ta mở rộng lớp khái niệm k-Term DNF ra thành lớp khái niệm DNF chứa tất cả các công thức dạng DNF (không cần biết bao nhiêu term). Chứng minh rằng lớp khái niệm DNF có thể học được.

2.3 Lớp khái niệm k-CNF có thể học được trong mô hình nhất quán

Lớp khái niệm k-CNF bao gồm các công thức có dạng sau:

\varphi = \underbrace{( \bullet \vee \dots \vee \bullet)}_{\text{$\leq k$ literals}} \wedge \underbrace{( \bullet \vee \dots \vee \bullet)}_{\text{$\leq k$ literals}} \wedge \dots \wedge \underbrace{( \bullet \vee \dots \vee \bullet)}_{\text{$\leq k$ literals}}

Để học lớp khái niệm này, rât đơn giản: với mỗi một bộ ≤ k literals (l_1,\dots,l_q), q ≤ k, tạo một biến Bool mới y(l_1,\dots,l_q). Cứ tưởng tượng y(l_1,\dots,l_q) = l_1 \vee \dots \vee l_q và dùng thuật toán cho lớp khái niệm Boolean Conjunctions trong đề mục 2.1, conjunctions trên các biến y(l_1,\dots,l_q). Sau đó chuyển hypothesis trên các biến y ngược lại thành hypothesis trên các biến x.

Chú ý quan trọng: bất kỳ một công thức k-Term DNF nào cũng viết được dưới dạng một công thức k-CNF. Như vậy nếu thuật toán ML của ta được tự do output một hypothesis dạng k-CNF cho bài toán học lớp khái niệm k-Term DNF thì bài toán này lại có thể học được! Điểm này cho thấy cách biểu diễn khái niệm đóng vai trò cực kỳ quan trọng trong các thuật toán learning. Ta sẽ nói thêm về đề tài này sau.

2.5 Lớp khái niệm axis-parallel rectangles có thể học được trong mô hình nhất quán

Các hình chữ nhật song song với trục (axis-parallel rectangles) là các hình chữ nhật mà một cặp cạnh song song với trục x, cặp còn lại song song với trục y. Bây giờ, cho ta một mớ các điểm trong mặt phẳng làm training set như hình dưới đây thì việc tìm một hình chữ nhật nhất quán với data (hoặc chỉ ra là không tồn tại) rất là dễ dàng. Ví dụ này cho thấy cả domain lẫn lớp khái niệm đều có thể vô hạn.

Dĩ nhiên, ta có thể mở rộng bài toán lên không gian n-chiều và vẫn học được.

2.6 Lớp khái niệm separation hyperplanes có thể học được trong mô hình nhất quán

Cho hai nhóm điểm trên không gian \mathbb R^n, tìm một hyperplane sao cho mỗi nhóm nằm một bên hyperplane. Bài này có thể giải được bằng một LP-solver nào đó. Đây chẳng qua là một dạng của bổ đề Farkas.

2.7 Sơ kết

  • Ngoài các hạn chế như đã chỉ ra, mô hình nhất quán còn cho phép một lớp khái niệm con (k-term DNF) KHÔNG học được trong khi đó lớp khái niệm to hơn (DNF) thì lại học được.
  • Một mô hình đơn giản và nhiều hạn chế như vậy mà quyết định xem một lớp khái niệm có học được hay không đã không tầm thường. “Hùng mạnh” và “đơn giản” xem ra khó có thể cùng đạt tới được. Trong bài tới chúng ta sẽ xét một mô hình tốt hơn, gọi là mô hình có lẽ xấp xỉ đúng (Probably Approximately Correct — PAC). Đây là mô hình trung tâm của COLT, và có lẽ là một trong các ý tưởng sẽ mang lại cho Valiant giải Turing trong mộti vài năm tới.

Chủ đề: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê |

1 lời bình cho bài ““Học máy” từ góc nhìn của lý thuyết tính toán (2)”

  1. 1
    14 tháng 07, 2008, vào lúc 3:42 am Đặng Trí Dũng viết:

    Bài viết thật hay và khái quát, súc tích mà vẫn chuyển tải được nội dung. Gửi tiếp đi anh Hưng!!!

Ghi lời bình của bạn: