Con đường tơ lụa, hay là hành trình từ perceptron, logistic regression đến neural network

Perceptron khi huấn luyện bằng gradient descent với hàm squared error thì chính là linear regression. Logistic regression chính là linear regression cộng với một hàm non-linearity, và logistic regression cũng là một neural network đơn giản nhất với chỉ 1 neuron. SVM nếu dùng hàm kernel là sigmoid function thì tương đương với một mạng neural 2 lớp.

Bài này sẽ chỉ ra con đường tơ lụa kết nối perceptron, linear regression và logistic regression. Một cách trực quan ta cũng dễ dàng thấy logistic regression tương đương với 1 neuron. Câu chuyện giữa SVM và mạng neural sẽ được trở lại trong bài khác.

Thực ra động lực để viết bài này là sau khi mình có cuộc nói chuyện vô tiền khoáng hậu khoảng 2, 3 tuần trước. Lúc đó đã nói về neural network, optimization và rất nhiều thứ khác, nhưng đến logistic regression thì lại ngọng. Trước giờ  chỉ đọc qua một vài lần nên trong phút chốc không thể nhớ lại đầy đủ và hệ thống được. Tuy nhiên qua đó cũng thấy trí nhớ ngắn hạn của mình ngày càng unreliable. Vì vậy mặc dù còn rất nhiều đề tài muốn đọc và viết, nhưng tạm thời ta sẽ dành thời gian để nhìn lại một chút lịch sử trong bài này.

1. Perceptron

Perceptron có lẽ là thuật toán máy học đơn giản nhất. Được giới thiệu vào những năm 60 của thế kỉ trước, perceptron từng được gắn với nhiều claim rất mạnh mẽ thời bấy giờ. Tuy nhiên năm 1969, Minsky viết quyển sách “Perceptrons” phân tích chi tiết mô hình này, và chỉ ra nhiều hạn chế của nó, khiến perceptron dần thoái trào. Ở đây có một bài viết khá thú vị về chủ đề này.

1.1. Định nghĩa

Trong ngữ cảnh bài toán phân lớp nhị phân (binary classification), thuật toán perceptron sử dụng hàm quyết định là tổng có trọng số giữa vector input \mathbf{x} và vector tham số \boldsymbol{\theta}:

\displaystyle h_\theta\left(\mathbf{x}\right)=\theta_0+\sum_{i=1}^n \theta_i x_i         (1)

Để phân lớp, thuật toán này sử dụng luật quyết định đơn giản sau:

\displaystyle \hat{y} \left(\mathbf{x}\right)=\begin{cases} 1 & \text{if } h_{\theta}\left(\mathbf{x}\right)\geq0\\ 0 & \text{otherwise} \end{cases}      (2)

Trong đó \mathbf{x} là vector input, \theta_0, \theta_i ... \theta_n là các tham số của mô hình, đặc biệt \theta_0 đôi khi gọi là bias. n là số lượng feature sử dụng trong bài toán.

Để ý rằng trong (2), nếu ta muốn dùng ngưỡng quyết định h_{\theta}\left(\mathbf{x}\right)\geq\gamma > 0 nào đó, thì cũng tương đương với việc dùng bias mới có giá trị là \theta_0 - \gamma, do đó ngưỡng luôn là 0 trong đa số các trường hợp.

Ngoài ra, để ý là ta có thể đơn giản hóa cách viết hàm h_\theta\left(\mathbf{x}\right) bằng cách đặt thêm phần tử x_0 = 1 vào vector input \mathbf{x}. Như vậy hàm này có thể viết lại là:

\displaystyle h_\theta \left(\mathbf{x}\right) = \theta_0 x_0 + \sum_{i=1}^n \theta_i x_i = \sum_{i=0}^n \theta_i x_i = \boldsymbol{\theta}^\top\mathbf{x}       (3)

1.2. Thuật toán học (Learning algorithm)

Thuật toán huấn luyện perceptron thực sự rất đơn giản:

  • Khởi tạo vector trọng số \boldsymbol{\theta}
  • foreach training sample \left(\mathbf{x}, y\right)
    • Tính giá trị predict \displaystyle \hat{y}\left(\mathbf{x}\right) theo (2)
    • Cập nhật vector trọng số {\displaystyle \boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\alpha\left(\hat{y}\left(\mathbf{x}\right)-y\right)\mathbf{x}}

Trong đó \alpha là learning rate (quá đỗi) quen thuộc. Lưu ý rằng y\hat{y}\left(\mathbf{x}\right) chỉ có thể nhận giá trị 0 hay 1, do đó công thức cập nhật trọng số có thể phát biểu thành lời như sau:

  • Nếu y = \hat{y}\left(\mathbf{x}\right): giữ nguyên \boldsymbol{\theta}
  • Nếu y=1\hat{y}\left(\mathbf{x}\right)=0: \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \mathbf{x}
  • Nếu y=0\hat{y}\left(\mathbf{x}\right)=1: \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \mathbf{x}

Ta thấy thuật toán này là online, nghĩa là nó có thể làm việc trên từng training sample, và tập huấn luyện có thể vô hạn.

Tuy nhiên thuật toán này chỉ hoạt động được khi tập huấn luyện là linearly separable, nghĩa là tập positive và negative có thể phân tách bằng một hyperplane. Trong trường hợp tập huấn luyện không phải linearly separable, thuật toán này không thể tìm được trọng số có thể phân lớp đúng toàn bộ tập huấn luyện. Một ví dụ kinh điển cho trường hợp này là hàm XOR.

Ý tưởng chính của thuật toán perceptron là với mỗi training sample, ta dịch chuyển decision boundary một chút, sao cho nó tiến gần về decision boundary đúng, nếu như boundary đó tồn tại (nghĩa là nếu tập huấn luyện là linearly separable). Có thể chứng minh một cách không quá phức tạp rằng thuật toán sẽ hội tụ nếu tập huấn luyện là linearly separable, tuy nhiên ta sẽ trở lại trong dịp khác.

Với cùng ngữ cảnh như trên, nếu thay vì cố gắng tinh chỉnh decision boundary cho về càng gần boundary đúng càng tốt, ta cố gắng tinh chỉnh output của hệ thống \hat{y} càng gần với output trong tập huấn luyện y càng tốt, thì ta sẽ được thuật toán linear regression, như sẽ thấy trong phần tới.

2. Linear regression

Linear regression sử dụng hàm quyết định như (1), nhưng khi huấn luyện, mục tiêu của nó là làm cực tiểu hàm lỗi. Thông thuờng người ta dùng hàm squared error để đánh giá độ sai khác giữa giá trị predict \hat{y}\left(\mathbf{x}\right) và giá trị target y trong tập huấn luyện. Cụ thể hàm lỗi được viết như sau:

{\displaystyle J_{\theta}=\frac{1}{2m}\sum_{i=1}^{m}\left(h_{\theta}\left(\mathbf{x}^{(i)}\right)-y^{(i)}\right)^{2}=\frac{1}{2m}\sum_{i=1}^{m}\left(\boldsymbol{\theta}^{\top}\mathbf{x}^{(i)}-y^{(i)}\right)^{2}}      (4)

trong đó m là số lượng sample trong tập huấn luyện, \mathbf{x}^{(i)} kí hiệu training sample thứ i với target tương ứng y^{(i)}, và J_\theta kí hiệu hàm lỗi, hàm ý là với một tập huấn luyện cố định cho trước, giá trị của hàm lỗi này phụ thuộc vào tham số \boldsymbol{\theta}. Hằng số \frac{1}{2} là thủ thuật để đơn giản quá trình tính toán sau này.

Như vậy linear regression được đưa về bài toán tối ưu (không ràng buộc) như sau:

\displaystyle \min_{\boldsymbol{\theta}} J_\theta      (5)

Đến đây thì câu chuyện trở nên đơn giản. Linear regression sử dụng thuật toán gradient descent để giải bài toán tối ưu này, trong đó đạo hàm riêng của hàm lỗi theo tham số \boldsymbol{\theta}_j là:

\displaystyle \frac{\partial}{\partial \theta_j}J\left(\boldsymbol{\theta}\right) = \frac{1}{m}\sum_{i=1}^m\left(\mathbf{\theta}^\top\mathbf{x}^{(i)}-y^{(i)}\right)\mathbf{x}^{(i)}_j      (6)

và công thức cập nhật tham số là:

\theta_{j}\leftarrow\theta_{j}-\alpha\frac{\partial}{\partial\theta_{j}}J\left(\boldsymbol{\theta}\right)    (7)

Tất nhiên gradient descent không phải là cách duy nhất để giải bài toán này. Nếu viết lại công thức (3) dưới dạng ma trận, ta có:

\mathbf{y} = \mathbf{X}\boldsymbol{\theta}      (8)

Trong đó \mathbf{X}\in\mathbb{R}^{m\times n} là ma trận chứa m training cases trong tập huấn luyện, và \mathbf{y}\in\mathbb{R}^m là vector chứa giá trị target tương ứng. Khi đó (8) trở thành hệ phương trình tuyến tính over-determined (vì m luôn lớn hơn n trong đa số trường hợp), và ta có thể dùng phương pháp Least squares kinh điển trong đại số tuyến tính để tìm vector tham số \boldsymbol{\theta}, như đã trình bày ở đây. Tuy nhiên phương pháp này hạn chế khi m quá lớn so với n (giống như trong đa số các ứng dụng ML) vì phải tính ma trận nghịch đảo, do đó gradient descent vẫn là phương pháp được ưa chuộng hơn.

Như vậy ta đã thấy perceptron và linear regression thực chất sử dụng cùng một mô hình toán học, nhưng mục tiêu khác nhau nên thuật toán cũng khác nhau. Trong khi mục tiêu của perceptron là tinh chỉnh decision boundary, thì linear regression chỉ quan tâm đến làm sao để đạt ít lỗi nhất có thể trên tập huấn luyện.

Hạn chế lớn nhất của hai phương pháp này là hàm quyết định vẫn là tuyến tính theo các input. Logistic regression thêm vào mô hình này một non-linearity, như sẽ thấy trong phần tới.

3. Logistic regression

Trong logistic regression, hàm quyết định được định nghĩa như sau:

\displaystyle h_\theta\left(\mathbf{x}\right)=\sigma\left(\boldsymbol{\theta}^\top\mathbf{x}\right) = \frac{1}{1+\exp\left(-\boldsymbol{\theta}^\top\mathbf{x}\right)}      (9)

Trong đó \sigma\left(z\right)=\frac{1}{1+\exp\left(-z\right)} là hàm logistic (sigmoid), đây cũng là lí do phương pháp này gọi là logistic regression. Mặc dù vậy một số non-linearity khác cũng có thể được sử dụng, chẳng hạn \tanh\left(z\right). Trong ngữ cảnh logistic regression, chọn lựa non-linearity không có nhiều ý nghĩa lắm, nhưng với (deep) neural network, chọn lựa này có thể dẫn đến vài khác biệt đáng kể.

Đương nhiên ta cũng có thể dùng squared error để viết hàm lỗi tương tự như (4):

\displaystyle J_\theta = \frac{1}{m}\sum_{i=1}^m \frac{1}{2}\left[\sigma\left(\boldsymbol{\theta}^\top\mathbf{x}^{(i)}\right) - y^{(i)}\right]^2      (10)

Vấn đề là khi đó J_\theta không còn convex nữa, nên nếu dùng gradient descent ta không thể đảm bảo tìm được global optimum.

Tuy nhiên squared error không phải là cách duy nhất để ước lượng tham số. Bằng cách xem (9) dưới góc nhìn xác suất, ta có thể viết:

{\displaystyle p\left(y=1\vert\mathbf{x}\right)= \sigma\left(\boldsymbol{\theta}^\top\mathbf{x}\right)=\frac{1}{1+\exp\left(-\boldsymbol{\theta}^{\top}\mathbf{x}\right)}}      (11)

khi đó ta có thể dùng Maximum likelihood estimation (MLE) để ước lượng \boldsymbol{\theta}. (Thực ra cách viết này ẩn chứa một assumption khá chặt về phân bố của dữ liệu trong bài toán này, ta sẽ trở lại với vấn đề này trong bài sau)

Cụ thể, cho một training case \left(\mathbf{x}, y\right), ta có:

{\displaystyle p\left(\mathbf{x},y\vert\theta\right)=\begin{cases} \sigma\left(\mathbf{\theta}^{\top} \mathbf{x}\right) & \text{if }y=1\\ 1-\sigma\left(\mathbf{\theta}^{\top} \mathbf{x}\right) & \text{if }y=0\end{cases}}   (12)

y chỉ có thể bằng 0 hay 1 nên ta có định nghĩa như trên. Công thức này còn có thể viết gọn và đẹp hơn như sau:

{\displaystyle p\left(\mathbf{x},y\vert\theta\right)=\left[\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}\right)\right]^{y}\left[1-\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}\right)\right]^{1-y}}   (13)

và hàm negative log likelihood (NLL) của tập huấn luyện \mathcal{D} gồm m training case là:

\begin{aligned}J_{\theta}=-\log p\left(\mathcal{D}\vert\mathbf{\theta}\right) & =-\sum_{i=1}^{m}\log p\left(\mathbf{x}^{\left(i\right)},y^{\left(i\right)}\vert\mathbf{\theta}\right)\\ & =-\sum_{i=1}^{m}y^{\left(i\right)}\log\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}^{\left(i\right)}\right)+\left(1-y^{\left(i\right)}\right)\log\left(1-\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}^{\left(i\right)}\right)\right)\end{aligned}    (14)

Và mục tiêu bây giờ là tìm \boldsymbol{\theta} để cực tiểu hóa hàm NLL này. Một điều đặc biệt là đạo hàm của hàm này theo \theta_j có dạng khá đẹp:

\begin{aligned}\frac{\partial}{\partial\theta_{j}}J\left(\mathbf{\theta}\right) & =-\sum_{i=1}^{m}y^{\left(i\right)}\left(1-\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}^{\left(i\right)}\right)\right)\mathbf{x}_{j}^{\left(i\right)}-\left(1-y^{\left(i\right)}\right)\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}^{\left(i\right)}\right)\mathbf{x}_{j}^{\left(i\right)}\\ & =-\sum_{i=1}^{m}\left(y^{\left(i\right)}-\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}^{\left(i\right)}\right)\right)\mathbf{x}_{j}^{\left(i\right)}\\ & =\sum_{i=1}^{m}\left(\sigma\left(\mathbf{\theta}^{\top}\mathbf{x}^{\left(i\right)}\right)-y^{\left(i\right)}\right)\mathbf{x}_{j}^{\left(i\right)} \end{aligned}  (15)

Để ý rằng công thức đạo hàm này rất giống với trường hợp linear regression trong công thức (6), điểm khác biệt duy nhất là ta dùng hàm non-linear \sigma\left(\cdot\right) để “ép” tổng có trọng số \boldsymbol{\theta}^\top\mathbf{x}.

Và như vậy công thức cập nhật trọng số của logistic regression trở nên:

\theta_{j}\leftarrow\theta_{j}-\alpha\frac{\partial}{\partial\theta_{j}}J\left(\boldsymbol{\theta}\right)   (16)

với đạo hàm đã tính trong công thức (15).

Người ta thường xem logistic regression là một mô hình không đủ mạnh, vì nói chung nó chỉ hoạt động tốt khi decision boundary là tuyến tính. Tuy nhiên ta có thể làm cho mô hình này mạnh hơn và hoạt động tốt trong trường hợp non linear decision boundary bằng cách thêm vào các feature mới dựa trên feature hiện có. Chẳng hạn ta có thể định nghĩa hàm quyết định là:

h_\theta\left(\mathbf{x}\right)=\sigma\left(\mathbf{x}\right)=\sigma\left(\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_1^2+\theta_4x_2^2\right)

nghĩa là thêm vào các feature phi tuyến x_1^2x_2^2. Bằng cách này ta có thể fit mô hình trong các trường hợp decision boundary khá phức tạp. Thực tế (nghe nói) là logistic regression vẫn được dùng khá rộng rãi khi ta có rất nhiều feature. Khá dễ hiểu vì trong trường hợp đó, không gian của dữ liệu có số chiều lớn, và rất có thể tồn tại decision boundary tuyến tính trong không gian này (đây cũng chính là ý tưởng chủ đạo của the so-called kernel trick được dùng trong SVM).

4. Tổng kết

Bài này chỉ ra con đường tơ lụa kết nối từ perceptron đến logistic regression. Theo đó:

  • Cả 3 sử dụng cùng một mô hình để phân lớp
  • Perceptron sử dụng hàm quyết định tuyến tính và thuật toán học rất đơn giản (gần như là heuristic)
  • Linear regression là perceptron khi sử dụng hàm mục tiêu là squared error để tối ưu bằng gradient descent
  • Logistic regression = linear regression + non-linearity (thông thường là sigmoid). Tuy nhiên khi đó hàm mục tiêu là Negative Log Likelihood thì bài toán mới convex. Thực chất đây là MLE, thay vì SSE estimation.

Một điểm đáng lưu ý là sử dụng góc nhìn xác suất như trong (11), logistic regression hàm chứa một giả định khá chặt về phân bố của dữ liệu. Đây sẽ là chủ đề của bài kế tiếp.

Advertisements

2 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s