Gradient-based Learning, hay là Optimization ứng dụng trong ML

Thuật toán huấn luyện của rất nhiều mô hình máy học được phát biểu hình thức dưới dạng một bài toán Optimization, chẳng hạn các mô hình như linear/logistic regression, ANN, SVM, k-means… Ý tưởng chung của các formulation dạng này là mỗi mô hình đều có một tập tham số \theta nào đó cần phải được xác định giá trị thông qua quá trình huấn luyện với dữ liệu.

Trước kia khi ngành ML chưa phát triển, dân thống kê đã gọi quá trình này là Parameter estimation, trong đó giá trị của các tham số được chọn sao cho chúng tối ưu một tiêu chuẩn nào đó do người xây dựng mô hình quyết định. Các tiêu chuẩn thường được dùng là phân phối xác suất likelihood, posterior hay là mean square error… tương ứng với các phương pháp  là MLE, MAP/EAPMMSE. Ta sẽ có bài riêng về các kĩ thuật này (hi vọng thế), nhưng nói chung chúng thể hiện “niềm tin” của người xây dựng mô hình về cách định nghĩa thế nào là mô hình tốt nhất, chứ không hề có chứng minh hình thức nào cả. Mặc dù vậy, ý tưởng cần được học hỏi ở đây là ta cần chọn ra một tiêu chuẩn nào đó, rồi chọn giá trị của tham số sao cho tối ưu tiêu chuẩn đó. Rõ ràng Optimization là ngành cung cấp cơ sở lí thuyết cho bài toán này một cách vững vàng nhất, do vậy áp dụng Optimization để học các mô hình thống kê trở thành tư tưởng hết sức tự nhiên.

Với các mô hình tham số (parametric model) thì cách làm như trên là rất tự nhiên. Mặc dù ML hiện nay còn nghiên cứu cả các mô hình phi tham số (nonparametric model) nhưng vì các mô hình tham số vẫn đóng vai trò hết sức quan trọng, nên tìm hiểu nguyên lí chung của các mô hình này là việc đáng làm. Bài này sẽ nói về các phương pháp ước lượng tham số sử dụng kĩ thuật tối ưu, mà ta gọi chung là gradient-based learning. Cụ thể bài này sẽ nói về gradient descent, stochastic gradient descentminibatch gradient descent cùng một số kĩ thuật regularization. Chi tiết về các thuật toán này có thể xem thêm trong bài giảng của Andrew Ng trong lớp Machine Learning của coursera.

Một cách tổng quát, thông thường ta muốn cực tiểu một hàm cost function C\left(\theta\right) ánh xạ vector tham số \theta thành một giá trị vô hướng. Hàm này được tính trên toàn tập huấn luyện. Trong Machine learning, cost function thường được biểu diễn thành trung bình cộng hoặc kì vọng của một hàm loss function nào đó áp dụng cho mỗi sample trong tập huấn luyện:

\displaystyle C\left(\theta\right) = \frac{1}{n}\sum_{i=1}^n L\left(f_\theta, z_i\right)

(gọi là training loss), hoặc

\displaystyle C\left(\theta\right)={\displaystyle \int L\left(f_{\theta},z\right)P\left(z\right)dz}

(gọi là generalization loss), trong đó \theta là vector tham số của mô hình, z_i là một sample trong tập huấn luyện và f_\theta là output của mô hình, ứng với tham số \theta. Ý tưởng là ta muốn tìm tham số \theta sao cho cực tiểu cost function này.

Chẳng hạn trong ngữ cảnh supervised learning thì z_i =\left(x_i,y_i\right) với x_i là sample đầu vào và y_i là nhãn tương ứng, còn f_\theta\left(x_i\right) là kết quả dự đoán y_i do mô hình đưa ra.

Cụ thể trong một bài toán phân lớp (classification), ta muốn xây dựng hàm dự đoán f:\;\mathbb{R}^{n}\rightarrow\left\{ 0,\dots,L-1\right\} với giả sử có L lớp trong bài toán đang xét. Một trong các hàm cost function có thể dùng là hàm zero-one loss:

\displaystyle C\left(\theta\right)\equiv l_{0,1}=\sum_{i=1}^{|D|}\mathbb{I}\left(f_{\theta}\left(x_{i}\right)\neq y_{i}\right)

trong đó D\equiv D_{train} là tập huấn luyện hoặc D\cap D_{train} = \varnothing để đảm bảo tính công bằng khi đánh giá thuật toán trên tập validation hoặc tập test, và \mathbb{I}\left(\textbf{A}\right) là hàm indicating function: \mathbb{I}\left(\textbf{A}\right)=1 nếu và chỉ nếu A đúng.

Tuy nhiên một bất lợi lớn là hàm zero-one loss không khả vi nên không thể áp dụng các thuật toán tối ưu. Thay vào đó, ta sẽ cực đại hàm log-likelihood trên toàn tập huấn luyện:

\displaystyle \mathcal{L}\left(\theta,D\right)=\log\prod_{i=1}^{|D|}P\left(Y=y_{i}\vert x_{i},\theta\right)=\sum_{i=1}^{|D|}\log P\left(Y=y_{i}\vert x_{i},\theta\right)

Lưu ý là zero-one losslog-likelihood là 2 tiêu chuẩn khác nhau, cũng như ta có thể định nghĩa các tiêu chuẩn khác như xác suất posterior hoặc mean squared error… Thông thường zero-one loss và log-likelihood là correlated trên tập validation, tuy nhiên điều này không phải lúc nào cũng đúng.

Do ta đang muốn cực tiểu hóa một hàm cost function, nên ta sẽ cực tiểu hàm negative log-likelihood (NLL):

\displaystyle C\left(\theta\right)\equiv\textrm{NLL}\left(\theta,D\right)=-\sum_{i=1}^{|D|}\log P\left(Y=y_{i}\vert x_{i},\theta\right)

Tóm lại ý tưởng là tìm \theta để cực tiểu hóa cost function C\left(\theta\right). Mặc dù lí thuyết optimization về vấn đề này rất đầy đủ với nhiều phương pháp khác nhau, nhưng dân ML thường chỉ dùng các phương pháp được liệt kê dưới đây.

1. Gradient descent

Ta biết rằng để tìm cực trị của C\left(\theta\right), ta có thể giải phương trình sau:

\displaystyle \frac{\partial C\left(\theta\right)}{\partial \theta} = 0

để tìm giá trị của \theta tại điểm cực trị. Cách này chỉ làm được khi ta có thể tính toán chính xác đạo hàm bậc nhất của C\left(\theta\right). Thực tế bằng cách sử dụng hàm likelihood, lấy đạo hàm để có công thức tường minh của các tham số rồi sử dụng thuật toán Expectation Maximization, đây chính là cách làm tỏ ra thành công với các mô hình như k-means, GMM hay HMM, như đã thấy ở đây và đây.

Tuy nhiên việc lấy đạo hàm và giải phương trình trên không phải lúc nào cũng thực hiện được, do đó cần sử dụng các phương pháp tối ưu. Phương pháp mà cộng đồng Machine Learning hay sử dụng nhất là gradient descent (dân Optimization gọi là steepest descent), mặc dù còn rất nhiều phương pháp khác như đã từng chỉ ra ở đây.

Cách đơn giản nhất để hiểu gradient descent là từ vị trí hiện tại, ta đi theo chiều giảm của đạo hàm bậc nhất cho đến khi không thể giảm được nữa. Khi đó ta đã ở một điểm tối ưu cục bộ. Công thức cập nhật cho gradient descent là:

\displaystyle \theta_{k+1} = \theta_k - \alpha_k \frac{\partial}{\partial \theta}C\left(\theta_k\right)

trong đó \theta_k là tham số tại lần lặp thứ k và \alpha_k gọi là learning rate, có thể được cố định hoặc thay đổi thích nghi trong suốt quá trình huấn luyện.

Mã giả cho Gradient descent có thể viết như sau

% GRADIENT DESCENT

while True:
    loss = f(params)
    d_loss_wrt_params = ... % tính gradient
    params -= learning_rate * d_loss_wrt_params
    if <stopping condition is met>:
        return params

2. Stochastic gradient descent (SGD)

Nhận thấy C là trung bình cộng, và thông thường tập huấn luyện là i.i.d (independently and identically distributed) nên tại mỗi bước ta có thể cập nhật tham số với mỗi sample trong tập huấn luyện:

\displaystyle \theta_{k+1} = \theta_k - \alpha_k \frac{\partial}{\partial \theta}L\left(\theta_k, z\right)

với z là sample tiếp theo trong tập huấn luyện, hoặc trong các ngữ cảnh online khi dữ liệu huấn luyện được đưa đến từng mẫu một (có thể vô hạn), và ta không có trọn vẹn cả tập huấn luyện ngay từ đầu. Một cách để hiểu về SGD là hướng cập nhật cho tham số là một biến ngẫu nhiên mà kì vọng của nó là hướng cập nhật tính bởi Gradient descent. Mặc dù có thêm yếu tố ngẫu nhiên nhưng kết quả của SGD là tương tự với Gradient descent.

SGD thông thường nhanh hơn Gradient descent vì ta cập nhật các tham số nhiều hơn hẳn. Điều này đặc biệt đúng khi ta có tập huấn luyện lớn hoặc không có toàn bộ tập huấn luyện ngay từ đầu. Thực tế trong ML, người ta chỉ dùng GD khi hàm cost function không thể viết dưới dạng trung bình như trên.

Dưới đây là mã giả cho SGD:

% STOCHASTIC GRADIENT DESCENT
for (x_i,y_i) in training_set:
                            % imagine an infinite generator
                            % that may repeat examples (if there is only a finite training set)
    loss = f(params, x_i, y_i)
    d_loss_wrt_params = ... % tính gradient
    params -= learning_rate * d_loss_wrt_params
    if <stopping condition is met>:
        return params

3. Minibatch gradient descent

Giữa 2 thái cực của gradient descent (dùng toàn bộ tập huấn luyện cho mỗi bước) và Stochastic gradient descent (chỉ dùng 1 sample cho mỗi bước), ta có dạng trung gian là minibatch gradient descent, trong đó ta sử dụng B sample cho mỗi bước cập nhật của \theta. Mã giả của phương pháp này có thể viết như sau:

for (x_batch,y_batch) in train_batches:
                            % imagine an infinite generator
                            % that may repeat examples
    loss = f(params, x_batch, y_batch)
    d_loss_wrt_params = ... % tính gradient
    params -= learning_rate * d_loss_wrt_params
    if <stopping condition is met>:
        return params

Minibatch có lợi thế hơn SGD ở chỗ nó giảm tính ngẫu nhiên của SGD và có thể giúp thuật toán hội tụ nhanh hơn vì thay vì tính B phép nhân vector và ma trận, ta chỉ cần tính một phép nhân ma trận với ma trận, trong đó ma trận thứ nhất có B hàng. Phép nhân này có thể được cài đặt rất hiệu quả trong MATLAB hay các thư viện tính toán khác như BLAS hay trên môi trường GPU.

Tuy nhiên nếu B lớn thì thuật toán sẽ tốn chi phí cho việc tính hướng giảm tại mỗi bước. Do đó B thực sự là tham số trade-off về mặt hiệu quả tính toán. Giá trị tối ưu cho B không chỉ phụ thuộc vào mô hình mà còn phụ thuộc vào dataset và kiến trúc máy tính (CPU hay GPU).

Lưu ý là nếu điều kiện dừng của thuật toán là số lần lặp (epochs), thì B trở nên vô cùng quan trọng vì nó quyết định số lần cập nhật của tham số. Huấn luyện mô hình với số epoch = 10 và B = 1 có thể cho kết quả hoàn toàn khác với epoch = 10 và B = 20. Do đó khi sử dụng minibatch gradient descent thì nên cẩn trọng khi thay đổi B, vì có thể ta sẽ phải tune toàn bộ các tham số khác với mỗi giá trị mới của B.

4. Momentum

Tương tự như minibatch GD nhưng ý tưởng của phương pháp momentum là tính toán mức độ thay đổi của tham số tại mỗi bước dựa vào bước trước đó. Như vậy tại mỗi bước tham số sẽ thay đổi một cách “thích nghi” dần dần với các lần lặp trước. Cụ thể

\Delta\theta_{k+1}=\varepsilon\Delta\theta_k + \left(1-\varepsilon\right)\frac{\partial}{\partial\theta}L\left(\theta_k,z\right)

với \varepsilon là hyper-parameter điều khiển mức độ ảnh hưởng của gradient vào mức giảm tại mỗi bước. Rõ ràng đây là một trick của dân CS chứ không phải là optimization chính quy.

5. Chiến lược chọn learning rate

Nếu learning rate quá lớn, chẳng hạn lớn gấp đôi trị riêng lớn nhất của ma trận Hessian của C\left(\theta\right) thì các bước sẽ đi lên (ascent) thay vì đi xuống (descent). Ngược lại nếu learning rate quá nhỏ thì thuật toán sẽ hội tụ chậm. Lý thuyết optimization giải quyết vấn đề này bằng thuật toán line search, nhưng trong ML thì thường chọn \alpha^k theo các cách sau:

  • Hằng số \alpha_k = \alpha_0: đây là lựa chọn phổ biến nhất và phù hợp khi phân phối của C\left(\theta\right) không cố định. Đây là cách làm robust nhưng giá trị của C\left(\theta\right) có thể không giảm nữa sau một số lần lặp, trong khi nếu dùng learning rate nhỏ hơn thì có thể giảm tiếp (tiến gần hơn 1 chút đến điểm tối ưu).
  • Phụ thuộc vào số bước lặp k: \alpha_k = \alpha_0\frac{\tau}{\tau + k}. Chiến lược này đảm bảo đến được điểm tối ưu khi k\rightarrow \infty vì nó thỏa
    \displaystyle \sum_{k=1}^\infty \alpha_k = \infty và  \displaystyle \sum_{k=1}^\infty \alpha_k^2 < \infty
    và điều này đúng với mọi \tau nhưng \alpha_0 phải đủ nhỏ để tránh đi lên thay vì đi xuống.
    Tuy nhiên cần phải cân nhắc vì ta lại có thêm một hyper-parameter cần phải tune. Chọn giá trị không tốt cho \tau có thể làm chậm quá trình hội tụ của thuật toán.

6. Regularization

Đây là vấn đề của ML chứ không phải Optimization. Khi tối ưu C\left(\theta\right), ta không muốn “tối ưu quá”, vì như thế mô hình sẽ bị overfit vào dữ liệu huấn luyện và sẽ không đủ tổng quát để mô hình hóa cả dữ liệu mới. Regularization là cách để cân bằng hiện tượng này. Có nhiều cách để regularize mô hình ML, ta sẽ xem xét L1/L2 regularization và kĩ thuật Early-stopping.

6.1. L1/L2 regularization

Ta thêm vào sau C\left(\theta\right) một hàm của \theta để tránh hiện tượng overfitting. Cụ thể hàm regularized loss function sẽ có dạng:

\displaystyle E\left(\theta,D\right)=C\left(\theta\right)+\lambda R\left(\theta\right)

với R\left(\theta\right) là hàm regularization. Trong trường hợp L1/L2 regularization thì:

\displaystyle E\left(\theta,D\right)=C\left(\theta\right)+\lambda\left\Vert \theta\right\Vert _{p}^{p}

với

\displaystyle \left\Vert \theta\right\Vert _{p}=\left(\sum_{j=1}^{|\theta|}\left\vert \theta_{j}\right\vert ^{p}\right)^{\frac{1}{p}}

chuẩn L_p của vector \theta. p có thể bằng 1 hoặc 2, từ đó tạo nên cái tên L1/L2 regularization.

\lambda là hyper-parameter thể hiện mức độ trade-off giữa C\left(\theta\right)R\left(\theta\right). Một cách nôm na, ta có C\left(\theta\right) thể hiện mức độ fit của mô hình vào dữ liệu (nhất là khi sử dụng xác suất likelihood) còn R\left(\theta\right) thể hiện mức độ regularization mà ta muốn thực hiện. Tối ưu đồng thời cả 2 yếu tố này, ta hi vọng đạt được tình huống nào đó cân bằng cả 2. Mức độ trade-off giữa 2 bên được thể hiện bằng \lambda.

Trong huấn luyện ANN hay SVM, L1/L2 regularization giúp cân bằng các trọng số, tránh hiện tượng chênh lệch giá trị giữa các tham số và làm cho mô hình “đơn giản” hơn (decision boundary “đơn giản”/”mượt” hơn). Theo nguyên lí Occam, kết quả tối ưu sẽ giúp ta có kết quả đơn giản nhất có thể (theo tiêu chí đã chọn) mà vẫn fit được dữ liệu. Tất nhiên cần nhớ rằng decision boundary mượt không nhất thiết đồng nghĩa với khả năng tổng quát hóa tốt hơn.

6.2. Early stopping

Là một kĩ thuật regularization khác, trong đó sử dụng tập validation để theo dõi mức độ overfit của dữ liệu bằng một số heuristic nào đó.

Loại early stopping đơn giản nhất là nếu độ lỗi trên tập validation không giảm trong một số đủ lớn bước lặp, ta sẽ kết thúc thuật toán và trả về bộ tham số tốt nhất tìm được. Các chiến lược khác có thể xem ở đây.

7. Kết luận

Bài này tóm tắt về các chiến lược gradient descent thường dùng trong ML, sau đó nói tiếp về cách chọn learning rate và kĩ thuật regularization. Bài này có thể xem là cơ bản cho các bài tiếp theo (hi vọng) sẽ viết trong hè này về ML.

Advertisements

5 comments

  1. Hello anh Vũ,
    Cho xin hỏi anh một vấn đề (Nó không liên quan đến bài viết hiện tại của anh).
    Anh có thể giải thích dùng phương pháp Action Matrix để giải hệ phương trình tuyến tính không?
    Xin cảm ơn anh.

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