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

Learn & Enjoy …

Posts Tagged ‘concept’

« 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) (2) – Phá vỡ một tập hợp (shatter)

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

Một khái niệm quan trọng trong lý thuyết VC là khái niệm phá vỡ một tập hợp (shatter). Khái niệm này cho thấy khả năng thể hiện của một lớp khái niệm.

Định nghĩa: Cho không gian mẫu \displaystyle \mathbb{X}, tập \displaystyle S\subset \mathbb{X} và một lớp khái niệm \displaystyle \mathcal{C} trên \displaystyle \mathbb{X}. Đặt

\displaystyle \Pi_{\mathcal{C}}(S) = \{c\cap S:c\in \mathcal{C}\}

Có thể hiểu như sau: \displaystyle \Pi_{\mathcal{C}}(S) là tất cả các khả năng có thể có để một khái niệm \displaystyle c trong lớp khái niệm \displaystyle \mathcal{C} phân chia (phá vỡ) tập các mẫu \displaystyle S thành hai tập:

  • \displaystyle c\cap S thuộc \displaystyle c và
  • \displaystyle S\setminus (c\cap S) không thuộc \displaystyle c.

Rõ ràng \displaystyle \Pi_{\mathcal{C}}(S) \subset 2^S, tập các tập con của \displaystyle S.

Định nghĩa (phá vỡ – shatter): Ta nói lớp khái niệm \displaystyle \mathcal{C} phá vỡ tập \displaystyle S nếu \displaystyle \Pi_{\mathcal{C}}(S) = 2^S.

Nghĩa là các khái niệm trong lớp khái niệm \displaystyle \mathcal{C} hoàn toàn phá vỡ tập \displaystyle S (thành mọi tập con có thể có của \displaystyle S).

Định nghĩa (chiều VC – VC dimension): Chiều VC của lớp khái niệm \displaystyle \mathcal{C}, kí hiệu \displaystyle \mathrm{VCD}(\mathcal{C}) là lực lượng lớn nhất của một tập hợp \displaystyle S\subset \mathbb{X} bị phá vỡ bởi \displaystyle \mathcal{C}.

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

Như vậy, chiều VC cho biết khả năng thể hiện của một lớp khái niệm, kích cỡ lớn nhất của một tập hợp mẫu mà các khái niệm nằm trong lớp khái niệm này có thể phân chia.

Nếu \displaystyle \mathrm{VCD}(\mathcal{C})<\infty, ta nói lớp khái niệm \displaystyle \mathcal{C} có chiều VC hữu hạn. Ngược lại, ta viết \displaystyle \mathrm{VCD}(\mathcal{C})=\infty. Lưu ý rằng, \displaystyle \mathcal{C} có thể có chiều VC hữu hạn mặc dù bản thân \displaystyle \mathcal{C} vô hạn.

Để chứng minh \displaystyle \mathrm{VCD}(\mathcal{C}) = d, ta phải: (1) chỉ ra một tập \displaystyle S với \displaystyle |S|=d bị phá vỡ bởi \displaystyle \mathcal{C} và (2) chứng minh rằng mọi tập \displaystyle S' mà \displaystyle |S'|=d+1 không thể bị phá vỡ bởi \displaystyle \mathcal{C}.

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

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