CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Archive for Tháng Bảy, 2009

« Những bài viết trước

Mô hình đồ thị (Graphical models) (1) – Giới thiệu

Đăng bởi tqlong on Tháng Bảy 15, 2009

Ta đã biết, để tiến hành việc “học” một khái niệm \displaystyle f^* (khái niệm gốc – true concept, ground truth), người ta thường chọn trong một lớp hàm \displaystyle \mathcal{F} ra một hàm \displaystyle \widehat{f} phù hợp nhất với dữ liệu vào (sinh ra từ khái niệm \displaystyle f^*) . Như vậy, lớp hàm \displaystyle \mathcal{F} có tính quyết định đối với việc ta có tìm được hàm \displaystyle f^* (hoặc một hàm gần với \displaystyle f^*) hay không. Nếu \displaystyle \mathcal{F} quá nhỏ (ví dụ: chiều VC nhỏ), rất có thể hàm \displaystyle \widehat{f} khác xa với hàm \displaystyle f^*. Ngược lại, nếu \displaystyle \mathcal{F} quá lớn (ví dụ: chiều VC lớn), rất có thể ta sẽ tìm được hàm \displaystyle \widehat{f} giống với hàm \displaystyle f^* trên toàn bộ tập mẫu học nhưng lại khác xa hàm \displaystyle f^* trên những mẫu chưa xuất hiện (hiện tượng học quá – overfitting). Một ví dụ điển hình chính là mạng nơron, một mô hình học máy rất mạnh (chính xác hơn là quá mạnh) nhưng lại rất khó huấn luyện để tránh hiện tượng học quá này.

Như vậy, một lớp hàm \displaystyle \mathcal{F} “vừa đủ” là rất cần thiết. Nhưng khái niệm “vừa đủ” rất mập mờ vì nó liên quan đến từng bài toán cụ thể mà ta cần giải quyết. Khi nhận ra những điểm yếu của mô hình học máy mạnh và tổng quát như mạng nơron, người ta cho rằng cần phải tận dụng được các kiến thức chuyên ngành (field knowledge) của từng bài toán cụ thể để tạo ra những lớp hàm đủ mạnh (nhưng không quá mạnh, quá tổng quát) để giải quyết riêng từng bài toán. Trong các mô hình như vậy, mô hình đồ thị (graphical model) hiện đang được nghiên cứu rất mạnh. Các đặc điểm của mô hình đồ thị là:

  • Khả năng mô tả bài toán một cách trực quan, mô tả được quan hệ giữa các bộ phận của bài toán.
  • Khả năng đưa kiến thức chuyên ngành một cách trực tiếp vào mô hình.
  • Với những mô hình đồ thị đơn giản (dạng cây, dạng chuỗi), ta có các thuật toán hiệu quả để huấn luyện (training) và truy xuất (query) mô hình. Lớp mô hình đồ thị này tuy đơn giản nhưng lại có ứng dụng rộng khắp (ví dụ: mạng  Markov ẩn (Hidden Markov Models – HMMs)).
  • Với những mô hình đồ thị phức tạp hơn, người ta chứng minh được việc huấn luyện và truy xuất chúng một cách chính xác là các bài toán NP khó. Như vậy, trên thực tế, không thể huấn luyện hoặc truy xuất các mô hình này một cách chính xác (trừ khi \displaystyle \mathrm{P}=\mathrm{NP}). Tuy vậy, ta vẫn có các thuật toán xấp xỉ rất hiệu quả.

Hiện nay, việc nghiên cứu các thuật toán xấp xỉ cho mô hình đồ thị cùng với việc xác định cấu trúc hợp lý của mô hình đồ thị cho từng bài toán cụ thể là một vấn đề nghiên cứu hết sức nóng hổi trong ngành Học máy và Trí tuệ nhân tạo.

Để bắt đầu, ta xem xét ví dụ sau: Xét một mô hình đơn giản của thời tiết bao gồm 2 trạng thái Mưa (rain) và Nắng (sunny) và giả sử thời tiết chỉ có thể ở 1 trong 2 trạng thái này. Đồng thời, chuyên gia về thời tiết cho ta biết, khả năng (xác suất) để ngày tiếp theo của một ngày nắng cũng nắng là \displaystyle 90\%, còn khả năng để ngày tiếp theo của một này mưa cũng mưa là \displaystyle 60\%. Ngoài ra, chuyên gia còn cho biết các xác suất này không phụ thuộc vào các ngày trước đó (tính chất Markov). Vậy ta có bảng xác suất

Mưa Nắng
Mưa 60% 40%
Nắng 10% 90%

Bảng trên thể hiện xác suất có điều kiện của thời tiết của ngày kế tiếp. Nếu ta đặt \displaystyle x_n là giá trị thời tiết của ngày thứ \displaystyle n thì bảng trên thể hiện phân bố xác suất có điều kiện \displaystyle p(x_{n+1}|x_n), tức là xác suất thời tiết ngày kế tiếp nếu biết thời tiết của ngày trước đó.  Đồng thời, do tính chất Markov, ta có

\displaystyle p(x_{n+1}|x_n,x_{n-1},\ldots, x_0)=p(x_{n+1}|x_n)

Ta có thể biểu diễn quan hệ này bằng đồ thị như sau:

Mô hình đồ thị của thời tiết

Đồ thị cho thấy, \displaystyle x_{n+1} chỉ phụ thuộc vào \displaystyle x_n (theo bảng xác suất \displaystyle p(x_{n+1}|x_n)) và không phụ thuộc vào \displaystyle x_{n-1},\ldots, x_0.

Mô hình này vẫn còn thiếu trạng thái ban đầu \displaystyle x_0. Ta có thể chọn xác suất \displaystyle p(x_0=\mathrm{rain})=p(x_0=\mathrm{sunny})=0.5 hoặc đơn giản hơn, ta cố định ngày đầu tiên \displaystyle x_0 luôn là ngày nắng (hoặc mưa) \displaystyle p(x_0=\mathrm{sunny})=1.

Như vậy, xác suất thời tiết \displaystyle x_0,\ldots,x_n của một chuỗi \displaystyle n+1 ngày là

\displaystyle p(x_0,x_1,\ldots, x_n) = p(x_0)p(x_1|x_0)p(x_2|x_1,x_0)\ldots p(x_n|x_{n-1},\ldots,x_0) (công thức xác suất điều kiện)

\displaystyle = p(x_0)p(x_1|x_0)p(x_2|x_1)\ldots p(x_n|x_{n-1}) (do tính chất Markov)

Nhận xét:

  1. Tính chất Markov (thể hiện qua đồ thị trên) cho phép ta rút gọn tính toán \displaystyle p(x_0,x_1,\ldots, x_n): Nếu trước đây ta cần một bảng xác suất gồm \displaystyle 2^{n+1} phần tử để thể hiện \displaystyle p(x_0,x_1,\ldots, x_n) thì nay ta chỉ cần \displaystyle n+1  bảng xác suất cỡ \displaystyle 2\times 2 và 1 phép tính như trên (ở đây, do các bảng đều giống nhau nên ta chỉ có 2 bảng \displaystyle p(x_0) và \displaystyle p(x_{n+1}|x_n)).
  2. Nếu nối đồ thị của \displaystyle x_0,x_1,\ldots, x_n lại với nhau ta sẽ có 1 đồ thị dạng dây (chain) như sauMô hình đồ thị thời tiết
    Rõ ràng, tính đơn giản của đồ thị cho phép tính toán \displaystyle p(x_0,x_1,\ldots, x_n) trở nên đơn giản.
  3. Ta còn có thể tính toán các giá trị xác suất có điều kiện khác, ví dụ

    \displaystyle p(x_n|x_0) = \frac{p(x_0,x_n)}{p(x_0)},

    đây là xác suất có điều kiện của ngày cuối cùng nếu biết trước ngày đầu tiên, trong đó
    \displaystyle p(x_0,x_n) = \sum_{x_1,\ldots,x_{n-1}}p(x_0,x_1,\ldots,x_n)=\sum_{x_1,\ldots,x_{n-1}}p(x_0)p(x_1|x_0)p(x_2|x_1)\ldots p(x_n|x_{n-1})
    \displaystyle = p(x_0) \sum_{x_1} p(x_1|x_0) \sum_{x_2}p(x_2|x_1)\ldots\sum_{x_{n-1}}p(x_{n-1}|x_{n-2})p(x_n|x_{n-1}) (do tính phân phối của phép cộng và phép nhân).

  4. Quá trình tính tổng trên như sau:
    • Với mọi giá trị của \displaystyle x_{n-2} tính
      \displaystyle \sum_{x_{n-1}}p(x_{n-1}|x_{n-2})p(x_n|x_{n-1})=\mu_{n-1}(x_{n-2}),
      đây là một hàm của \displaystyle x_{n-2}.
    • Với mọi giá trị của \displaystyle x_{n-3} tính tổng
      \displaystyle \sum_{x_{n-2}}p(x_{n-2}|x_{n-3})\sum_{x_{n-1}}p(x_{n-1}|x_{n-2})p(x_n|x_{n-1})
      \displaystyle =\sum_{x_{n-2}}p(x_{n-2}|x_{n-3})\mu_{n-1}(x_{n-2})=\mu_{n-2}(x_{n-3}).
    • Tiếp tục như vậy đến cuối cùng ta được \displaystyle p(x_0,x_n) = p(x_0)\mu_1(x_0).
  5. Hàm \displaystyle \mu_{k+1}(x_k) được gọi là thông điệp (message) chuyển từ nút \displaystyle x_{k+1} đến nút \displaystyle x_k trong mô hình đồ thị. Lưu ý, thông điệp này là một hàm của \displaystyle x_k. Đôi khi, người ta còn viết \displaystyle \mu_{k+1\rightarrow k}(x_k) cho rõ hơn.
  6. Nếu tính bằng thứ tự ngược lại, ta có:
    \displaystyle p(x_0,x_n) = \sum_{x_1,\ldots,x_{n-1}}p(x_n|x_{n-1}) \ldots p(x_2|x_1) p(x_1|x_0)p(x_0)
    \displaystyle = \sum_{x_{n-1}} p(x_n|x_{n-1}) \sum_{x_{n-2}}p(x_{n-1}|x_{n-2})\ldots\underbrace{\sum_{x_2}p(x_3|x_2)\underbrace{\sum_{x_1}p(x_2|x_1)\underbrace{p(x_1|x_0)p(x_0)}_{\mu_{0\rightarrow1}(x_1)}}_{\mu_{1\rightarrow 2}(x_2)}}_{\mu_{2\rightarrow 3}(x_3)}
    Nghĩa là có thể có nhiều thứ tự để tính giá trị của \displaystyle p(x_0,x_n). Ở đây, ta thấy độ phức tạp tính toán của hai cách tính này tương tự nhau. Ở các bài sau, ta sẽ thấy thứ tự tính toán ảnh hưởng lớn đến độ phức tạp.

Đăng trong Lý thuyết học máy, Mô hình đồ thị | Tagged: , , , , , , , , , , , , , , | Leave a Comment »

Chiều VC (VC dimension) (4) – Một số lớp hàm đơn giản

Đăng bởi tqlong on Tháng Bảy 9, 2009

Ta tìm hiểu chiều VC của một số lớp hàm đơn giản trong bài này. Theo định nghĩa, chiều VC của một lớp khái niệm là số phần tử lớn nhất của một tập có thể bị phá vỡ (shatter) bởi lớp khái niệm này.

\displaystyle \mathrm{VCD}(\mathcal{C}) = \max \{|S|: \Pi_{\mathcal{C}}(S)=2^S\}

Để chỉ ra chiều VC của một lớp khái niệm bằng \displaystyle d ta phải chứng minh:

  1. \displaystyle \mathrm{VCD}(\mathcal{C})\geq d: bằng cách chỉ ra một tập có số phần tử bằng \displaystyle d bị phá vỡ bởi \displaystyle \mathcal{C}.
  2. \displaystyle \mathrm{VCD}(\mathcal{C})< d+1: bằng cách chỉ ra với mọi tập có số phần tử  nhiều hơn \displaystyle d thì \displaystyle \mathcal{C} không thể phá vỡ được (thường khó hơn mệnh đề trên).

Trong một số trường hợp, ta chỉ xác định được mệnh đề 1 hoặc mệnh đề 2.

Ví dụ 1: Lớp các khoảng đóng trên trục số \displaystyle \mathbb{R}

Lớp khái niệm đoạn đóng

Xét lớp khái niệm \displaystyle \mathcal{C}=\{[a,b]:a\leq b\}. Đối với lớp khái niệm này, phá vỡ có nghĩa là gì ? Một tập hợp điểm \displaystyle \{x_1,\ldots, x_n\} bị phá vỡ bởi lớp các khoảng đóng nếu với mọi cách đánh dấu tập điểm này bằng các dấu \displaystyle +,-, ta đều có thể tìm được một khoảng đóng chỉ chứa các điểm được đánh dấu \displaystyle +.

Ta sẽ chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})=2. Thật vậy, đầu tiên dễ thấy rằng mọi tập 2 điểm \displaystyle \{x,y\} trên trục số đều có thể bị phá vỡ bởi \displaystyle \mathcal{C} (với cả 4 cách đánh dấu \displaystyle +,- cho \displaystyle x,y ta đều có thể vẽ một khoảng đóng chỉ chứa các điểm có dấu \displaystyle +).  Do đó \displaystyle \mathrm{VCD}(\mathcal{C})\geq 2.

Tuy nhiên, với mọi tập 3 điểm (phân biệt) \displaystyle x<y<z, nếu ta đánh dấu \displaystyle x,z thuộc lớp \displaystyle +1, còn \displaystyle ylà \displaystyle -1 thì không thể có khoảng đóng nào chứa \displaystyle x,z mà không chứa \displaystyle y. Do đó \displaystyle \mathcal{C} không thể phá vỡ tập 3 điểm bất kì (do không có khái niệm nào chứa \displaystyle x,z mà không chứa \displaystyle y). Vậy \displaystyle \mathrm{VCD}(\mathcal{C})< 3 hay \displaystyle \mathrm{VCD}(\mathcal{C})= 2.

Ví dụ 2: Lớp các hình chữ nhật có cạnh song song với 2 trục của mặt phẳng

Lớp khái niệm hình chữ nhật

Xét lớp khái niệm \displaystyle \mathcal{C}=\{[a,b]\times[c,d]\subset \mathbb{R}^2:a\leq b,c\leq d\}. Một tập bị phá vỡ bởi \displaystyle \mathcal{C} nghĩa là với mọi cách đánh dấu \displaystyle +,- các điểm của tập này ta đều có một hình chữ nhật chỉ chứa các điểm được đánh dấu \displaystyle +.

Ta sẽ chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})=4. Thật vậy, đầu tiên ta cần chỉ ra một tập có 4 điểm thuộc \displaystyle \mathbb{R}^2 bị phá vỡ bởi \displaystyle C. Xét tập 4 điểm gồm 4 đỉnh của một hình thoi có các trục song song với hai trục X, Y. Rõ ràng với mọi cách đánh dấu \displaystyle +,- ta đều có thể vẽ 1 hình chữ nhật chỉ chứa các dấu \displaystyle +. Suy ra \displaystyle \mathrm{VCD}(\mathcal{C})\geq 4.

Khả năng phá vỡ của lớp các hình chữ nhật

Xét một tập 5 điểm (phân biệt) bất kì trên mặt phẳng. Như vậy tồn tại một điểm không phải là điểm trái nhất hoặc phải nhất hoặc cao nhất hoặc thấp nhất. Đánh dấu điểm này bằng dấu \displaystyle - còn 4 điểm còn lại bằng dấu \displaystyle + (như hình trên). Hình chữ nhật bao được 4 dấu  \displaystyle + bắt buộc phải chứa cả dấu \displaystyle -. Do đó tập 5 điểm không thể bị phá vỡ. Suy ra \displaystyle \mathrm{VCD}(\mathcal{C})< 5 hay \displaystyle \mathrm{VCD}(\mathcal{C})= 4.

Ví dụ 3: Lớp các nửa không gian (phân cách bằng siêu phẳng):

half-space-concept

Xét lớp khái niệm \displaystyle \mathcal{C}= \{ H_{w,b},\forall w\in \mathbb{R}^d,b\in \mathbb{R}\} là tập tất cả các nửa không gian

\displaystyle H_{w,b} = \{x\in \mathbb{R}^d: \langle w,x\rangle-b \geq 0\}

xác định bởi véctơ pháp tuyến (normal) \displaystyle w và ngưỡng (threshold) \displaystyle b. Đây là một lớp khái niệm rất quan trọng vì rất nhiều hàm phân lớp là hàm phân lớp tuyến tính (perceptron, SVM, RBF).

Ta sẽ chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})=d+1 với \displaystyle d là số chiều của không gian.

Để chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})\geq d+1 ta cần chỉ ra một tập có \displaystyle d+1 phần tử bị phá vỡ bởi \displaystyle \mathcal{C}. Xét tập điểm sau \displaystyle 0, e_1, \ldots, e_d với \displaystyle 0 là gốc tọa độ, \displaystyle e_1,\ldots, e_d là các véc tơ cơ sở trực chuẩn ta vẫn thường sử dụng \displaystyle e_i = (0,\ldots,0,1,0,\ldots,0). Bây giờ ta xét một cách đánh dấu bất kì các điểm này. Do tính đối xứng của nửa không gian, không mất tính tổng quát giả sử các điểm được đánh dấu \displaystyle + có điểm \displaystyle 0 và các véctơ được đánh dấu \displaystyle + là \displaystyle 0, e_1,\ldots, e_k với \displaystyle k\leq d. Nếu nửa không gian \displaystyle H_{w,b} chỉ chứa các điểm có dấu \displaystyle + thì

\displaystyle \langle w,0\rangle -b\geq 0 \Rightarrow b \leq 0

\displaystyle \langle w,e_i\rangle -b\geq 0,\forall i\leq k \Rightarrow w_i \geq b,\forall i\leq k

\displaystyle \langle w,e_i\rangle -b< 0,\forall i> k \Rightarrow w_i < b,\forall i> k

Có rất nhiều cách để chọn \displaystyle w,b như trên. Ví dụ \displaystyle b = -1, w_i = \begin{cases}0 & i\leq k\\ -2 & i>k\end{cases}. Vậy tập điểm trên bị phá vỡ bởi \displaystyle \mathcal{C}.

Để chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})<d+2, ta sử dụng định lý Radon. Theo đó, một tập điểm bất kì gồm \displaystyle d+2 điểm phân biệt có thể tách thành 2 tập con có bao lồi giao nhau. Đánh dấu một tập con bằng dấu \displaystyle + và tập còn lại bằng dấu \displaystyle -. Giả sử có một nửa không gian \displaystyle H nào đó chứa và chỉ chứa tất cả các điểm có dấu \displaystyle +. Suy ra \displaystyle H  chứa bao lồi các điểm này (do \displaystyle H là tập lồi), còn \displaystyle \mathbb{R}^d\setminus H chứa bao lồi của các điểm có dấu \displaystyle -. Suy ra bao lồi của hai tập điểm này không giao nhau, mâu thuẫn với định lý Radon.

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , | Leave a Comment »

« Những bài viết trước