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

Learn & Enjoy …

Archive for Tháng Bảy, 2008

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

Phân lớp bằng siêu phẳng (1) – Perceptron, tế bào thần kinh nhân tạo

Đăng bởi tqlong on Tháng Bảy 31, 2008

Có lẽ dạng hàm phân lớp đơn giản nhất là hàm tuyến tính (hoặc affine). Hàm phân lớp tuyến tính chỉ cho ranh giới phân lớp là một siêu phẳng. Mặc dù vậy, ứng dụng của dạng hàm phân lớp này vô cùng rộng rãi. Khoảng từ những năm 1990, các thuật toán phân lớp có độ chính xác, tốc độ học và bảo đảm toán học mạnh nhất chính là các thuật toán sử dụng hàm phân lớp tuyến tính. Ví dụ như: mạng các hàm cơ sở dạng bán kính (Radial Basis Functions network – RBF), máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines – SVM), v.v… đều là các hàm phân lớp tuyến tính. Trong bài này, ta xét một dạng hàm phân lớp đơn giản, gọi là Perceptron, một trong những tế bào thần kinh nhân tạo đầu tiên.

Hàm phân lớp tuyến tính: Ta biết rằng, hàm phân lớp tuyến tính có ranh giới phân lớp là 1 siêu phẳng, vì vậy nó chỉ phân tách được 2 lớp. Tất nhiên, ta có thể kết hợp nhiều hàm phân lớp lại để phân tách được nhiều lớp hơn. Nhưng trong ví dụ này, ta chỉ xét hàm tuyến tính phân tách \displaystyle \mathbb{R}^n  thành 2 nửa không gian (half-space).

Để cho tiện, ta gán \displaystyle \omega_1 = +1, \omega_2 = -1, luật phân lớp khi sử dụng hàm phân lớp tuyến tính là

\displaystyle f(x)=\theta( \langle w,x\rangle -b)

\displaystyle \theta(t) = \begin{cases}+1 & t\geq 0\\ -1 & t < 0\end{cases}

trong đó, \displaystyle f(x) là hàm phân lớp, \displaystyle \theta(t) là hàm ngưỡng (threshold function), \displaystyle \langle w,x\rangle là tích vô hướng của \displaystyle w,x, \displaystyle w là trọng số (weight) trên các tọa độ/đặc trưng của \displaystyle x, \displaystyle b là ngưỡng (threshold).

Phân lớp bằng siêu phẳng

Như vậy, nửa không gian \displaystyle R_+=\{x|\langle w,x\rangle \geq b\} được phân vào lớp \displaystyle \omega_1=+1, nửa không gian còn lại R_-=\displaystyle \{x|\langle w,x\rangle \geq b\} được phân vào lớp \displaystyle \omega_2=-1. Người ta còn thể hiện hàm phân lớp trên như sau

Perceptron

Perceptron

Với cách thể hiện này, người ta có ý đồ nối các Perceptron lại với nhau để tạo thành một mạng lưới gọi là Mạng nơron nhân tạo (Artificial Neural Networks) giống như hệ thần kinh gồm mạng lưới các tế bào thần kinh của con người. Bây giờ ta sẽ tìm hiểu làm thế nào để huấn luyện một Perceptron.

Bài toán huấn luyện Perceptron phát biểu như sau:

Cho một tập các mẫu học \displaystyle D=\{(x_i,y_i)\}_{i=1}^N với \displaystyle x_i\in \mathbb{R}^n, y_i=\pm 1, tìm giá trị của \displaystyle w,b sao cho

\displaystyle f(x_i) = \theta( \langle w,x_i\rangle -b) = y_i, \forall i=1,\ldots, N

Nếu tồn tại \displaystyle (w,b) như vậy, ta nói tập mẫu học \displaystyle D phân tách tuyến tính được (linear separable).

Do \displaystyle y_i=\pm 1, điều kiện trên tương đương với

\displaystyle y_i (\langle w,x_i\rangle -b) > 0, \forall i=1,\ldots, N

Nếu đặt \displaystyle \gamma = \min_i y_i (\langle w,x_i\rangle -b) thì

\displaystyle y_i (\langle w,x_i\rangle -b) \geq \gamma > 0, \forall i=1,\ldots, N

Như vậy, ta có thể nói tập mẫu học \displaystyle D phân tách tuyến tính được nếu tồn tại \displaystyle (w,b) và \displaystyle \gamma>0 sao cho bất đẳng thức trên đúng với mọi \displaystyle i=1,\ldots, N.

Năm 1957, Rosenblatt đề xuất Perceptron và một thuật toán huấn luyện rất đơn giản. Đến năm 1962, Novikoff chứng minh rằng thuật toán huấn luyện này luôn dừng sau một số hữu hạn bước lặp nếu tập mẫu học phân tách tuyến tính được.

Thuật toán huấn luyện Perceptron: Thuật toán ở dạng trực tuyến (online), ta lần lượt cung cấp cho thuật toán các mẫu học trong \displaystyle D, có thể lặp lại nhiều lần. Mỗi lần có mẫu học mới, thuật toán sẽ chỉnh sửa \displaystyle (w,b) để cố gắng phân lớp được mẫu học này

Bước thứ \displaystyle t: Đầu vào là mẫu học \displaystyle (x_t, y_t)

  1. Nếu \displaystyle f(x_t) = y_t, không làm gì cả vì đã phân lớp đúng.
  2. Nếu \displaystyle f(x_t) \neq y_t (phân lớp sai), tức là

    \displaystyle y_i (\langle w,x_t\rangle - b) \leq 0

    thì cập nhật (update) lại \displaystyle (w,b) như sau

    \displaystyle w^{\mathrm{new}} = w^{\mathrm{old}} + y_t x_t
    \displaystyle b^{\mathrm{new}} = b^{\mathrm{old}} - y_t

  3. Chuyển sang bước thứ \displaystyle t+1.

Để ý là ở bước 2, khi phân lớp sai, giả sử \displaystyle y_t = +1, khi đó ta phải có

\displaystyle \langle w^{\mathrm{old}},x_t\rangle -b^{\mathrm{old}} \leq 0

Sau khi cập nhật, ta có

\displaystyle \langle w^{\mathrm{new}},x_i\rangle -b^{\mathrm{new}} = \langle w^{\mathrm{old}},x_i\rangle -b^{\mathrm{old}} + \langle x_t,x_t\rangle + 1 > \langle w^{\mathrm{old}},x_i\rangle -b^{\mathrm{old}}

Nghĩa là khả năng phân lớp đúng mẫu học \displaystyle (x_t,y_t) sẽ lớn hơn sau khi cập nhật các trọng số \displaystyle (w,b).

Định lý (tính dừng của thuật toán huấn luyện Perceptron): Nếu tập mẫu học \displaystyle D=\{(x_i,y_i)\}_{i=1}^N phân tách tuyến tính được thì thuật toán huấn luyện Perceptron cho ra các trọng số \displaystyle (w,b) phân tách tập mẫu học này sau một số hữu hạn lần cập nhật (bước 2).

Chứng minh: Để cho tiện, ta đặt

\displaystyle W = \left[\begin{array}{cc}w & b\end{array}\right]^T, z = \left[\begin{array}{cc}x & -1\end{array}\right]^T

như vậy \displaystyle \langle W,z\rangle = \langle w,x\rangle -b và cập nhật ở bước 2 tương đương với

\displaystyle W^{\mathrm{new}} = W^{\mathrm{old}} + y_t z_t

Do tập mẫu học \displaystyle D=\{z_i,y_i\}_{i=1}^N phân tách tuyến tính được, phải tồn tại \displaystyle W^* và \displaystyle \gamma>0 sao cho

\displaystyle y_i \langle W^*,z_i\rangle \geq \gamma,\forall i=1,\ldots,N

Giả sử thuật toán bắt đầu với trọng số \displaystyle W_1 = 0 và tại một thời điểm nào đó trong quá trình huấn luyện, thuật toán đã cập nhật trọng số \displaystyle W tất cả \displaystyle K lần, không mất tính tổng quát, giả sử

\displaystyle y_t\langle W_t,z_t\rangle\leq 0, t=1,\ldots,K (phân lớp sai)

\displaystyle W_{t+1} = W_t + y_t z_t, t=1,\ldots,K (cập nhật trọng số)

Suy ra

\displaystyle \|W_{t+1}\|^2 = \|W_t + y_t z_t\|^2 = \|W_t\|^2 + 2y_t\langle W_t,z_t\rangle + \|z_t\|^2 \leq \|W_t\|^2 + \|z_t\|^2

\displaystyle \Rightarrow \|W_{K+1}\|^2 \leq \sum_{i=1}^K \|z_i\|^2 \leq KR^2

trong đó \displaystyle R = \max_t \|z_t\|.

Mặt khác, do \displaystyle W_1 = 0 nên

\displaystyle W_{K+1} = \sum_{i=1}^K y_i z_i\displaystyle \Rightarrow \langle W^*,W_{K+1}\rangle = \sum_{i=1}^K y_i \langle W^*,z_i\rangle \geq K\gamma

Theo bất đẳng thức Swartz: \displaystyle \|x\|^2\|y\|^2\geq \langle x,y\rangle^2 , ta có

\displaystyle \|W^*\|^2\|W_{K+1}\|^2\geq \langle W^*,W_{K+1}\rangle ^2 \geq K^2\gamma^2\displaystyle \Rightarrow \|W_{K+1}\|^2 \geq \frac{K^2\gamma^2}{\|W^*\|^2}

Vậy

\displaystyle \frac{K^2\gamma^2}{\|W^*\|^2} \leq KR^2\displaystyle \Rightarrow K \leq \|W^*\|^2\left(\frac{R}{\gamma}\right)^2

Nghĩa là nếu tồn tại \displaystyle W^* phân cách tập mẫu học, số lần cập nhật \displaystyle K sẽ bị chặn trên.

Nhận xét:

  1. Để ý rằng \displaystyle h_i = \left|\frac{\langle W^*,z_i\rangle}{\|W^*\|}\right| chính là khoảng cách từ điểm \displaystyle z_i đến siêu phẳng phân cách \displaystyle \langle W^*,z\rangle = 0. Do đó

    \displaystyle \gamma = \min_i \{y_i\langle W^*,z_i\rangle\} = h\|W^*\|

    với \displaystyle h = \min_i h_i là khoảng cách nhỏ nhất từ các mẫu học đến siêu phẳng (còn gọi là lề của siêu phẳng – margin). Suy ra

    \displaystyle K \leq \left(\frac{R}{h}\right)^2

    Tức là nếu lề của siêu phẳng \displaystyle h càng lớn thì thuật toán hội tụ càng nhanh (số lần cập nhật càng ít). Hơn nữa, theo lý thuyết VC, \displaystyle h còn liên quan chặt chẽ đến ước lượng xác suất lỗi (generalization error), nếu \displaystyle h càng lớn thì ước lượng càng chính xác.

Lịch sử nghiên cứu mạng nơron nhân tạo:

Định lý trên do Novikoff chứng minh lần đầu tiên vào năm 1962, nó cho thấy có thể dùng một thuật toán cập nhật trọng số rất đơn giản để tìm ra hàm phân lớp tuyến tính nếu tập mẫu học có thể phân tách tuyến tính được. Kết quả này đã khởi nguồn cho phong trào nghiên cứu các phương pháp học máy có mô hình đơn giản tương tự trong những năm 60. Đến năm 1969, một quyển sách nhỏ tựa đề “Perceptrons” của hai nhà khoa học rất có ảnh hưởng lúc đó là Minsky và Papert (giáo sư này bị tai nạn xe máy ở trường Bách Khoa năm 2006) chỉ ra những bài toán phân lớp mà các mô hình học đơn giản này không thể phân lớp được. Hai ông cho rằng, dù các perceptron có được nối lại với nhau thành nhiều tầng, nhiều lớp cũng không thể vượt qua những hạn chế này. Kết quả là suốt thập kỉ 70, nghiên cứu về mạng nơron nhân tạo không được cấp tiền hỗ trợ nghiên cứu. Phải đến năm 1986, với thuật toán lan truyền ngược sai số (error back-propagation), nghiên cứu về mạng nơron mới nở rộ trở lại. Vào năm 1987, Minsky và Papert xuất bản cuốn sách “Perceptrons – Expanded edition” chỉ ra và chỉnh sửa lại những lỗi của lần xuất bản trước.

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 4 phản hồi »

Các khái niệm trong Học máy (Machine Learning) (7) – Một số ví dụ

Đăng bởi tqlong on Tháng Bảy 30, 2008

Ước lượng tham số của phân phối chuẩn (normal distribution): Ở bài thứ 3, ta đã thấy một ví dụ sử dụng công thức Bayes để ước lượng xác suất của tham số. Trong ví dụ này, ta sẽ thử sử dụng nguyên tắc cực đại hóa khả năng (maximum likelihood estimation – MLE) để ước lượng tham số.

Ví dụ 1. Giả sử dữ liệu \displaystyle D=\{x_1,x_2,\ldots,x_N\} được lấy từ phân phối chuẩn \displaystyle \mathcal{N}(\mu,1). Hãy xác định \displaystyle \mu.

Giải: Giá trị của \displaystyle \mu phải cực đại hóa khả năng (likelihood) của dữ liệu

\displaystyle p(D|\mu) = \prod_{i=1}^N \left(\frac{1}{\sqrt{2\pi}}\exp \left\{-\frac{1}{2}(x_i-\mu)^2 \right\}\right)

Lấy logarit cơ số tự nhiên cả hai vế và loại bỏ đi hằng số, việc cực đại hóa \displaystyle p(D|\mu) tương đương với việc cực đại hóa hàm log-likelihood sau

\displaystyle L(\mu) = -\frac{1}{2}\sum_{i=1}^N (x_i-\mu)^2

Lấy đạo hàm \displaystyle L'(\mu) và đặt bằng \displaystyle {0} rồi giải ra ta được ước lượng MLE của \displaystyle \mu là

\displaystyle \widehat{\mu}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N x_i = \overline{x}

Ví dụ 2. Giả sử dữ liệu \displaystyle D=\{x_1,x_2,\ldots,x_N\} được lấy từ phân phối chuẩn \displaystyle \mathcal{N}(\mu,\sigma^2). Hãy xác định \displaystyle \mu, \sigma^2=v.

Giải: Tương tự như trên hàm log-likelihood là:

\displaystyle L(\mu,v) = -\frac{N}{2}\ln v - \frac{1}{2v} \sum_{i=1}^N (x_i-\mu)^2

Đầu tiên, cực đại hóa \displaystyle L(\mu,v) theo \displaystyle \mu, ta được

\displaystyle \widehat{\mu}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N x_i = \overline{x}

\displaystyle \overline{L}(v) = \max_\mu L(\mu,v) = L(\overline{x},v) = -\frac{N}{2}\ln v - \frac{1}{2v} \sum_{i=1}^N (x_i-\overline{x})^2

Tiếp tục cực đại hóa \displaystyle \overline{L}(v) theo \displaystyle v ta có

\displaystyle \overline{L'}(v) = -\frac{N}{2v}+\frac{1}{2v^2} \sum_{i=1}^N (x_i-\overline{x})^2 = 0

\displaystyle \widehat{v}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N (x_i-\overline{x})^2

Lưu ý:

  1. Qua 2 ví dụ trên, ta thấy \displaystyle \mu,\sigma^2 xác định qua nguyên tắc cực đại hóa khả năng chính là các đại lượng trung bình cộng của dữ liệu và trung bình bình phương sai số.
  2. Đối với dữ liệu nhiều chiều, \displaystyle \mathbb{R}^n\ni x\sim \mathcal{N}(\mu,\Sigma), với cách làm tương tự (có phức tạp hơn 1 chút), ta cũng có thể tính được

    \displaystyle \widehat{\mu}_{\mathrm{MLE}} = \overline{x}
    \displaystyle \widehat{\Sigma}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N (x_i-\overline{x})(x_i-\overline{x})^T

Ví dụ 3. Giả sử có hai lớp đối tượng \displaystyle \omega_1,\omega_2 , ta biết rằng

\displaystyle p(x|\omega_1) = \mathcal{N}(\mu_1,\sigma^2)

\displaystyle p(x|\omega_2) = \mathcal{N}(\mu_2,\sigma^2)

Nghĩa là phân bố của hai lớp đối tượng đều là phân phối chuẩn, có phương sai giống nhau. Đồng thời giả sử \displaystyle P(\omega_1)=P(\omega_2) = 0.5. Hãy xây dựng luật phân lớp tối ưu và ước lượng xác suất lỗi.

Giải: Do \displaystyle P(\omega_1)=P(\omega_2) = 0.5 nên luật phân lớp tối ưu là

\displaystyle x\in\omega_1\Leftrightarrow p(x|\omega_1) \geq p(x|\omega_2)

\displaystyle x\in\omega_1\Leftrightarrow \frac{1}{\sqrt{2\pi}\sigma}\exp \left\{-\frac{1}{2}\frac{(x_i-\mu_1)^2}{\sigma^2} \right\} \geq \frac{1}{\sqrt{2\pi}\sigma}\exp \left\{-\frac{1}{2}\frac{(x_i-\mu_2)^2}{\sigma^2} \right\}

Lấy logarith cơ số tự nhiên cả hai vế của bất đẳng thức rồi loại bỏ hằng số chung ta được

\displaystyle x\in\omega_1\Leftrightarrow (x-\mu_1)^2 \leq (x-\mu_2)^2

\displaystyle x\in\omega_1\Leftrightarrow |x-\mu_1| \leq |x-\mu_2|

Tức là nếu \displaystyle x ở gần \displaystyle \mu_1 hơn thì sẽ được phân vào lớp \displaystyle \omega_1 và ngược lại. Hoặc nếu \displaystyle \mu_1<\mu_2, ta có thể viết

\displaystyle x\in\omega_1\Leftrightarrow x\leq \frac{\mu_1+\mu_2}{2}

Để tính xác suất lỗi (generalization error), ta có

\displaystyle P\{\mathrm{error}\} = P\left\{X> \left.\frac{\mu_1+\mu_2}{2}\right|\omega_1\right\}P(\omega_1)+P\left\{\left.X\leq \frac{\mu_1+\mu_2}{2}\right|\omega_2\right\}P(\omega_2)

Do \displaystyle P(\omega_1)=P(\omega_2) = 0.5 và tính đối xứng của các phân bố ta có

\displaystyle P\{\mathrm{error}\} = P\left\{\left.X\leq \frac{\mu_1+\mu_2}{2}\right|\omega_2\right\}=\mathbf{\Phi}\left(\frac{\mu_1-\mu_2}{2\sigma}\right)

Trong đó \displaystyle \mathbf{\Phi}(x) là hàm phân bố xác suất (cummulative distribution function) của phân bố chuẩn \displaystyle \mathcal{N}(0,1).

Ví dụ 4. Xét trường hợp tổng quát hơn \displaystyle x\in \mathbb{R}^n và

\displaystyle p(x|\omega_1) = \mathcal{N}(\mu_1,\Sigma_1) = \frac{1}{(2\pi)^{n/2}|\Sigma_1|^{1/2}}\exp\left\{-\frac{1}{2}(x-\mu_1)^T\Sigma_1^{-1}(x-\mu_1)\right\}

\displaystyle p(x|\omega_2) = \mathcal{N}(\mu_2,\Sigma_2) = \frac{1}{(2\pi)^{n/2}|\Sigma_2|^{1/2}}\exp\left\{-\frac{1}{2}(x-\mu_2)^T\Sigma_2^{-1}(x-\mu_2)\right\}

Điều kiện để phân \displaystyle x vào lớp \displaystyle \omega_1 là

\displaystyle p(x|\omega_1)P(\omega_1)\geq p(x|\omega_2)P(\omega_2)

Lấy logarit cơ số tự nhiên cả 2 vế, ta có

\displaystyle \ln P(\omega_1)-\frac{1}{2}\ln |\Sigma_1|-\frac{1}{2} (x-\mu_1)^T\Sigma_1^{-1}(x-\mu_1)\displaystyle \geq \ln P(\omega_2)-\frac{1}{2}\ln |\Sigma_2|-\frac{1}{2} (x-\mu_2)^T\Sigma_2^{-1}(x-\mu_2)

Như vậy, ở trường hợp phân phối chuẩn tổng quát, đường phân ranh giới tối ưu giữa 2 lớp là một đường cong bậc 2. Nó có thể là đường thẳng, elipsoid, hyperbol hay parabol tùy thuộc vào \displaystyle \Sigma_1 và \displaystyle \Sigma_2. Ta xét một số trường hợp đơn giản:

  • \displaystyle \Sigma_1=\Sigma_2=\sigma^2 I_n: khi đó bất đẳng thức trên tương đương với

    \displaystyle \|x-\mu_1\|^2-2\sigma^2\ln P(\omega_1) \leq \|x-\mu_2\|^2-2\sigma^2\ln P(\omega_2)

    Nghĩa là quyết định phân lớp tương đương với việc so sánh khoảng cách Euclid (Euclidean distance) từ \displaystyle x đến kì vọng của 2 phân phối. Trường hợp này, đường ranh giới là một đường thẳng vuông góc với đường thẳng nối \displaystyle \mu_1 và \displaystyle \mu_2.

  • \displaystyle \Sigma_1=\Sigma_2=K^{-1}: khi đó bất đẳng thức tương đương với

    \displaystyle (x-\mu_1)^T K (x-\mu_1) -\ln P(\omega_1) \leq (x-\mu_2)^T K (x-\mu_2) -\ln P(\omega_2)

    Đại lượng \displaystyle \sqrt{(x-\mu_1)^T K (x-\mu_1)} gọi là khoảng cách Mahalanobis (Mahalanobis distance) tương ứng với ma trận \displaystyle K. Tiếp tục đơn giản bất đẳng thức trên ta có

    \displaystyle -2\mu_1^TKx +\mu_1^TK\mu_1 - \ln P(\omega_1) \leq -2\mu_2^TKx +\mu_2^TK\mu_2 - \ln P(\omega_2)
    \displaystyle 2(\mu_1-\mu_2)^TKx - \mu_1^TK\mu_1+\mu_2^TK\mu_2+ \ln P(\omega_1) - \ln P(\omega_2)\geq 0

    Nghĩa là đường phân ranh giới giữa 2 lớp là một siêu phẳng có véctơ pháp tuyến \displaystyle K(\mu_1-\mu_2).

Lưu ý:

  1. Do ma trận \displaystyle K=\Sigma_1^{-1} là ma trận xác định dương nên dễ thấy các tính chất sau

    \displaystyle d_K(x,y) = \sqrt{(x-y)^T K (x-y)}\geq 0,\forall x,y\in \mathbb{R}^n
    \displaystyle d_K(x,y) = 0 \Leftrightarrow x=y
    \displaystyle d_K(x,y) = d_K(y,x)
    \displaystyle d_K(x,y)+d_K(y,z) \geq d_K(x,z) (bất đẳng thức tam giác)

    Tức là khoảng cách Mahalanobis thỏa mãn các tính chất cần có của khoảng cách trong không gian metric.

  2. Với giả sử phân phối của 2 lớp là phân phối chuẩn với ma trận hiệp phương sai \displaystyle \Sigma giống nhau, theo ví dụ trên, đường phân giới tối ưu là một siêu phẳng. Vì vậy một số phương pháp phân lớp trực tiếp tìm một siêu phẳng để phân tách 2 lớp (linear discriminant analysis – LDA). Trong các bài sau, ta sẽ thấy đây là một phương pháp phân lớp rất mạnh (về độ chính xác/tốc độ học/tốc độ phân lớp), đặc biệt khi ta có thể biến đổi không gian đặc trưng lên không gian nhiều chiều hơn (tức là tạo một ánh xạ \displaystyle \phi:\mathbb{R}^n\rightarrow \mathbb{R}^D với \displaystyle D\gg n và tiến hành phân lớp bằng siêu phẳng trên \displaystyle \mathbb{R}^D). Đây cũng là ý tưởng cơ bản của các phương pháp sử dụng vectơ hỗ trợ (Support Vector Machines) do giáo sư Vapnik đề xuất (từ “hỗ trợ” ở đây có nghĩa là siêu phẳng được một số véctơ/điểm dữ liệu “đỡ” lấy).

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

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