Hỏi về First - Second order method trong Optimization

optimization

#1

Em xin chào anh chị em trong diễn đàn. Em đang học về các thuật toán tối ưu dùng trong deep learning. Em có một số vấn đề thắc mắc về second order method như sau:

  1. Em thấy rằng trong thực hành thì người ta không dùng second order method do tốn thời gian tính ma trận Hessian nghịch đảo. Nhưng tại sao second order method lại giúp đạt đến local minimum với ít vòng lặp hơn khi so sánh với first order method?
  2. Có người nói rằng mọi phương pháp gradient descent đều có gắng xấp xỉ ma trận Hessian. Ý này có đúng không ạ? Và nếu đúng thì tại sao lại phải cố “bắt chước” second order method như vậy?
  3. Ma trận Hessian (của hàm loss) có condition number cao thì liên quan gì đến việc gradient descent sẽ hội tụ chậm và tại sao đường đồng mức (contour) lại có dạng dẹt? Em có đọc qua 1 số bài trên mạng nhưng vẫn cảm thấy rất khó hiểu (https://www.quora.com/What-does-it-mean-to-have-a-poorly-conditioned-Hessian-matrix), điều này có thể do một phần bởi kiến thức toán của em chưa đủ.

Mọi người trong diễn đàn có thể cho em biết các kiến thức toán cần thiết để em tra cứu thêm với ạ. Ngoài ra em rất cần những lời giải đáp hay theo 2 khía cạnh: một là trực quan, hai là chặt chẽ về toán (Ví dụ em xem trong slide course cs231n về second order method (http://cs231n.stanford.edu/slides/2018/cs231n_2018_lecture07.pdf) thì về trực quan em thấy họ nói rằng second order method là xấp xỉ quadratic, còn first order method là xấp xỉ linear với các hình vẽ, còn về mặt toán thì họ đưa ra khai triển taylor, nhưng em vẫn chưa hiểu rõ). Em tham khảo một số tài liệu nhưng chưa tìm được câu trả lời thuyết phục (có nhiều đoạn không nói chi tiết) khiến em không thoải mái mấy ngày nay. Mong các anh chị nào có thời gian có thể giải đáp giúp em với ạ. Em chân thành cảm ơn.


#2

Mình có một số thông tin thêm, hi vọng có thể giúp bạn giải quyết được một số vướng mắc:

  1. “Nhưng tại sao second order method lại giúp đạt đến local minimum với ít vòng lặp hơn khi so sánh với first order method”.

Về mặt trực quan, gradient là đạo hàm (riêng) của hàm, nó cho biết mức độ biên thiên của hàm số, còn ma trận Hesse là đạo hàm của đạo hàm, nó cho biết thông tin về mức độ biến thiên của gradient. Có nghĩa là nếu bạn dung các phương pháp bậc 2, thì bạn sẽ có nhiều thông tin hơn về độ cong của hàm, nên có thể hội tụ tốt hơn. Về mặt toán học, nếu bạn chỉ xét hàm bậc 2, ví dụ x^2 + bx +c, dung gradient bạn phải chạy nhiều vòng lặp mới đạt tới cực tiểu, trong khi dùng phương pháp bậc 2 thì chỉ cần one shot là tìm được cực tiểu luôn. Tất nhiên với các hàm phức tạp hơn, thì bạn không hi vọng one-shot, nhưng chuỗi xấp xỉ Taylor sẽ chính xác hơn nếu bạn dùng đến bậc hai, và về cơ bản second order method có thể hiểu là tối ưu hàm xấp xỉ Taylor bậc 2 sử dụng one shot cho mỗi xấp xỉ. Gradient thì chỉ coi như xấp xỉ one shot cho xấp xỉ taylor bậc 1, nghĩa là chỉ sử dụng gradien thì xấp xỉ thô hơn nhiều.

  1. Có người nói rằng mọi phương pháp gradient descent đều có gắng xấp xỉ ma trận Hessian. Ý này có đúng không ạ? Và nếu đúng thì tại sao lại phải cố “bắt chước” second order method như vậy?

Mình không biết là người nào nói thế, nhưng bản thân mình cho là không đúng (nếu mình sai thì xin để lại comment ở dưới, mình rất muốn biết lý do). Ví dụ phương pháp momentum mình không thấy nó bắt chước bậc 2 ở chỗ nào cả, mà đúng ra là nó tìm một cách xấp xử tốt hơn chỉ sử dụng gradient. Điều này có thể được giải thích thông qua Chebysev polynomial (xem thêm bài viết cực kỳ hay của Moritz hardt: http://blog.mrtz.org/2013/09/07/the-zen-of-gradient-descent.html). Như đã nói ở 1, phương pháp bậc hai cho bạn nhiều hơn thông tin của hàm, nhưng điểm yếu là chi phí tính toán lớn. Các phương pháp như quasi-newton hay một số biến thể, mục tiêu là tìm ra sự cân bằng giữa số vòng lặp cần thiết để hội tụ đến local minima và chi phí tính toan cho mỗi vòng lặp. Rất nhiều phương pháp “cố bắt chước” second order là vì các phương pháp này cố gắng tìm thông tin thêm về độ cong của hàm một cách rẻ nhất, để hội tụ nhanh hơn.

  1. Ma trận Hessian (của hàm loss) có condition number cao thì liên quan gì đến việc gradient descent sẽ hội tụ chậm và tại sao đường đồng mức (contour) lại có dạng dẹt? Em có đọc qua 1 số bài trên mạng nhưng vẫn cảm thấy rất khó hiểu (https://www.quora.com/What-does-it-mean-to-have-a-poorly-conditioned-Hessian-matrix 2), điều này có thể do một phần bởi kiến thức toán của em chưa đủ.

Hệ số điều hòa (condition number) của một ma trận là tỉ lệ giữa trị tuyệt đối của trị riêng có trị tuyệt đối lớn nhất và trị tuyệt đối của trị riêng có trị tuyệt đối nhỏ nhất. Để hiểu tại sao hệ số điều hòa lớn thì đường đòng mức có dạng dẹt, bạn phải hiểu trị riêng và vector riêng nó biểu diễn cái gì. Tiếc là bản dịch CHapter 2 trong sách deep learning của nhóm dlbookvn đã bị đóng, trong đó có giải thích rất rõ trị riêng nó biểu diễn cái gì. Nói nôm na, giả sử A là một ma trận 2\times 2 có hệ số điều hòa lớn. Như vậy, trị riêng ở một hướng của A sẽ lớn hơn rất nhiều trị riêng của A theo một hướng khác. Do đó, nếu bạn áp dụng phép biến đổi tuyến tính cho đường tròn đơn vị bằng cách nhân nó với A thì bạn sẽ thu được một elipse, một chiều rất dài còn một chiều rất ngắn, hay nói cách khác, nó bị dẹt. Đó là lý do tại sao đường đồng mức trông nó det.

Gradient hội tụ chậm vì theo một hướng, gradient thay đổi rất nhanh và theo hướng khác gradient thay đối rất chậm. Khi bạn cập nhật gradient, hướng thay đổi chậm sẽ triệt tiêu hiệu ứng của hướng thay đổi nhanh, do đó quá trình cập nhật bị chậm đi. Bạn có thể hỏi tại sao ta không cập nhật lời giải theo hướng nhanh của gradient và lờ đi hướng chậm? Đó chính là mục tiêu của phương pháp bậc 2, vì sử dụng ma trận Hesse bạn mới biết được hướng nào gradient biến dổi nhanh, hướng nào gradient biến đổi chậm.


#3

Dạ có thể cho em xin tên đầy đủ của cuốn sách deep leaning bản tiếng anh được nhắc ở trên không ạ. Em cảm ơn nhiều ạ.


#4

Sách Deep Learning mà nhóm dlbookvn đang dịch là quyển ở link này http://www.deeplearningbook.org/