Điểm yên ngựa trong tối ưu hóa: Khái niệm và tầm quan trọng

Ngay cả khi mọi đạo hàm riêng của hàm số bằng không, bạn vẫn không chắc đã ở gần một điểm cực tiểu.

Tối ưu hóa là quá trình tìm giá trị nhỏ nhất hoặc lớn nhất của một hàm, và mọi phương pháp bạn dùng đều tìm nơi mà gradient phẳng. Nhưng gradient phẳng không đảm bảo bạn đã tìm được lời giải tốt nhất. Đôi khi điều đó có nghĩa là hàm tăng theo một hướng và giảm theo hướng khác, ngay tại cùng một điểm.

Điểm đó được gọi là điểm yên ngựa: nó đi xuống theo một phía, đi lên theo phía kia, và phẳng xung quanh. Nhận diện điểm yên ngựa rất quan trọng vì thuật toán của bạn có thể mắc kẹt ở đó và nhầm lẫn gradient phẳng với một cực tiểu thực sự.

Trong bài viết này, tôi sẽ hướng dẫn bạn cách phát hiện điểm yên ngựa bằng toán học và vì sao nó thường khiến các thuật toán tối ưu hóa bối rối.

Điểm yên ngựa là gì?

Tại một điểm yên ngựa, gradient bằng không, giống như ở cực tiểu hay cực đại. Nhưng điểm yên ngựa không phải là cả hai loại đó.

Hàm cong lên theo một số hướng và cong xuống theo số hướng khác, ngay tại cùng điểm. Nếu bạn đi dọc theo một trục, giá trị tăng; đi dọc theo trục khác, giá trị giảm. Tên gọi xuất phát từ hình dáng của yên ngựa, cong lên ở phía trước và phía sau, cong xuống ở hai bên.

Dưới đây là một hàm hai biến đơn giản tôi sẽ dùng để minh họa:

Hàm hai biến

Tại gốc tọa độ, (0, 0), cả hai đạo hàm riêng đều bằng không, nên đó là một điểm tới hạn (còn gọi là điểm dừng). Di chuyển dọc trục x, f tăng do hạng x^2. Di chuyển dọc trục y, f giảm do hạng -y^2 .

Nếu bạn vẽ hàm này trong không gian 3D, bề mặt sẽ cong lên theo một hướng và cong xuống theo hướng khác, tạo nên hình dạng mà điểm yên ngựa được đặt tên theo đó.

Đồ thị bề mặt 3D của f(x, y) = x^2 - y^2

Biểu đồ đường đồng mức của cùng hàm cho thấy câu chuyện tương tự từ phía trên. Các đường đồng mức quanh gốc trông như các hyperbol, không phải các vòng kín như quanh cực tiểu hay cực đại.

Đồ thị đường đồng mức của f(x, y) = x^2 - y^2

Định nghĩa chính xác thay đổi đôi chút tùy lĩnh vực. Trong giải tích nhiều biến, điểm yên ngựa là điểm tới hạn không phải cực tiểu hay cực đại cục bộ. Trong tối ưu hóa và lý thuyết trò chơi, thuật ngữ có thể mang nghĩa khác, gắn với bài toán minimax hơn là độ cong. Tôi sẽ đề cập khác biệt này ở phần sau.

Điểm yên ngựa so với cực tiểu và cực đại

Trước khi đi vào cách nhận diện điểm yên ngựa bằng toán học, sẽ hữu ích nếu bạn thấy chúng so sánh thế nào với hai loại điểm tới hạn còn lại.

Cực tiểu cục bộ

Tại một cực tiểu cục bộ, hàm tăng theo mọi hướng lân cận. Hãy hình dung một chiếc bát - khi bạn bước rời đáy theo bất kỳ hướng nào, bạn đi lên. Hàm f(x, y) = x2 + y2 có hành vi như vậy.

Cực đại cục bộ

Tại một cực đại cục bộ, hàm giảm theo mọi hướng lân cận. Đó là hình ảnh phản chiếu của cực tiểu, vòm thay vì bát. Hàm f(x, y) = -x2 - y2 giảm theo mọi hướng khi bạn rời gốc tọa độ.

Điểm yên ngựa

Tại một điểm yên ngựa, hàm tăng theo một số hướng và giảm theo số khác. Đó là điều khiến f(x, y) = x2 - y2, ví dụ ở phần trước, trở thành điểm yên ngựa thay vì cực tiểu hay cực đại: nó tăng theo trục x và giảm theo trục y, tại cùng một điểm.

Dưới đây là hình so sánh trực quan của cả ba:

Các đồ thị bề mặt 3D đặt cạnh nhau của cực tiểu cục bộ, cực đại cục bộ và điểm yên ngựa

Cách tìm điểm yên ngựa

Tìm điểm yên ngựa chủ yếu là lấy đạo hàm, tìm nơi chúng triệt tiêu, rồi xem hàm cong như thế nào quanh điểm đó.

Tôi sẽ dùng lại hàm ở trên:

Hàm tham chiếu

Quy trình gồm các bước sau.

1. Tính các đạo hàm riêng bậc nhất

Lấy đạo hàm của f theo x, coi y là hằng số, rồi làm tương tự theo y:

Tính các đạo hàm riêng bậc nhất

2. Cho chúng bằng không

Giải điểm mà cả hai đạo hàm riêng cùng triệt tiêu:

Cho các đạo hàm bằng không

Điều này cho x = 0 và y = 0, nên (0, 0) là điểm tới hạn. Đạo hàm bậc nhất sẽ không cho bạn biết đó là loại nào.

3. Tính các đạo hàm bậc hai

Bạn cần ba giá trị: đạo hàm của f_x theo x, đạo hàm của f_y theo y, và đạo hàm hỗn hợp:

Các đạo hàm bậc hai

4. Phân loại điểm tới hạn bằng độ cong 

f_xx = 2 dương, nên f cong lên dọc trục x. f_yy = -2 âm, nên f cong xuống dọc trục y. Một hướng cong lên, hướng kia cong xuống, ngay tại cùng điểm - đó là điểm yên ngựa.

Quy trình bốn bước này áp dụng cho bất kỳ hàm khả vi bậc hai nào.

Trong hai phần tiếp theo, tôi sẽ chính thức hóa bước 4 bằng các công cụ mở rộng vượt quá hai biến: ma trận Hessian và kiểm định đạo hàm bậc hai.

Cách ma trận Hessian nhận diện điểm yên ngựa

Ma trận Hessian gom tất cả các đạo hàm bậc hai ở phần trước vào một đối tượng, và đó là công cụ cho bạn biết một điểm tới hạn là cực tiểu, cực đại hay điểm yên ngựa.

Với hàm hai biến, Hessian trông như sau:

Hessian cho một hàm hai biến

Mỗi phần tử mô tả độ cong: f_xx và f_yy mô tả độ cong dọc các trục x và y, còn f_xy mô tả cách hai hướng đó tương tác. Nếu bạn thay các đạo hàm bậc hai từ phần trước, Hessian cho hàm ví dụ của chúng ta như sau:

Hessian cho hàm tham chiếu

Một ma trận tự thân không nói lên nhiều điều. Điều quan trọng là các trị riêng - những con số mô tả cách hàm cong theo một tập hướng cụ thể gọi là vectơ riêng.

• Trị riêng dương nghĩa là hàm cong lên theo hướng của vectơ riêng đó
• Trị riêng âm nghĩa là hàm cong xuống theo hướng đó
• Hỗn hợp trị riêng dương và âm nghĩa là hàm cong lên ở vài hướng và cong xuống ở hướng khác (một điểm yên ngựa)

Vì Hessian của ví dụ là ma trận chéo, các trị riêng nằm ngay trên đường chéo: 2 và -2. Các vectơ riêng của chúng hướng dọc trục x và trục y, đúng như độ cong bạn đã tìm bằng tay ở phần trước. f cong lên theo x vì trị riêng dương, và cong xuống theo y vì trị riêng âm.

Đa số hàm sẽ không có Hessian chéo, nên các vectơ riêng sẽ không thẳng hàng gọn gàng với trục x và y, và bạn sẽ cần giải trực tiếp thay vì đọc từ ma trận. Nhưng một trị riêng dương và một trị riêng âm nghĩa là bạn đang đứng trên một điểm yên ngựa.

Kiểm định đạo hàm bậc hai cho điểm yên ngựa

Bạn không cần tính trị riêng bằng tay mỗi lần. Với hàm hai biến, có một lối tắt - kiểm định đạo hàm bậc hai - dựa trên định thức của Hessian.

Đây là định thức, dùng các đạo hàm bậc hai như trước:

Định thức

D là định thức của Hessian, và dấu của nó - kết hợp với dấu của f_xx - phân loại điểm tới hạn:

• D > 0 và f_xx > 0: Cực tiểu cục bộ

• D > 0 và f_xx < 0: Cực đại cục bộ

• D < 0: Điểm yên ngựa

• D = 0: Không kết luận được

Với ví dụ của chúng ta, f_xx = 2, f_yy = -2, và f_xy = 0:

Kiểm định đạo hàm bậc hai cho hàm tham chiếu

D âm, nên phép kiểm định khẳng định (0, 0) là một điểm yên ngựa.

Phép kiểm định này chính là quy tắc trị riêng ở phần trước, được viết lại dưới dạng bạn có thể tính mà không cần giải vectơ riêng. D là tích của hai trị riêng, còn f_xx + f_yy là tổng của chúng. Khi D âm, các trị riêng phải trái dấu, và đó là điểm yên ngựa. Khi D bằng không, ít nhất một trị riêng bằng không, nên độ cong theo hướng đó phẳng, và cả phép kiểm định lẫn trị riêng riêng lẻ đều không cho biết điều gì đang diễn ra.

Điểm yên ngựa trong tối ưu hóa

Mọi điều đến đây là về nhận diện điểm yên ngựa khi bạn đã có sẵn hàm. Nhưng trong tối ưu hóa, bạn đang tìm điểm tốt nhất mà không biết trước nó ở đâu, và các phương pháp dựa trên gradient dùng gradient bằng không để quyết định khi nào dừng.

Đó chính là nơi điểm yên ngựa gây rắc rối.

Một bộ tối ưu dựa trên gradient di chuyển theo hướng làm giảm hàm mục tiêu nhanh nhất, và tiếp tục cho đến khi gradient tiến gần về không. Nhưng gradient gần bằng không không nói cho thuật toán biết nó đã tìm thấy cực tiểu hay một điểm yên ngựa.

Các hướng có độ cong dương đẩy hàm đi lên, và thuật toán đã học rằng bước vào đó sẽ làm mọi thứ tệ hơn. Các hướng có độ cong âm vẫn tồn tại và là lối thoát - nhưng một thuật toán chỉ tin vào gradient có thể bỏ lỡ chúng, vì ngay tại điểm yên ngựa, gradient theo các hướng đó cũng gần bằng không.

Đây cũng là nơi tối ưu hóa chậm lại.

Độ lớn gradient có xu hướng thu nhỏ khi bạn tiến gần bất kỳ điểm dừng nào, nên một thuật toán tỷ lệ bước theo kích thước gradient sẽ bước rất nhỏ gần một điểm yên ngựa, bất kể nó có ở gần cực tiểu mà nó thực sự tìm kiếm hay không.

Tìm thấy một điểm dừng không đồng nghĩa với việc hoàn thành tối ưu hóa. Bạn vẫn cần cách để biết một gradient gần bằng không thuộc về điểm yên ngựa chứ không phải cực tiểu, và cách tìm hướng tiếp tục cải thiện hàm mục tiêu khi bạn đã nhận diện được.

Điểm yên ngựa trong máy học

Hàm mất mát của mạng nơ-ron là hàm của mọi trọng số và độ lệch trong mạng, đôi khi có hàng triệu hoặc hàng tỷ chiều. Nó rất xa so với ví dụ đồ chơi hai biến.

Trong một phân tích về tối ưu hóa phi lồi trong không gian nhiều chiều, Dauphin và cộng sự lập luận rằng khi số chiều tăng, các điểm tới hạn có khả năng cao là điểm yên ngựa hơn là cực tiểu hay cực đại cục bộ. Mỗi chiều bổ sung thêm một hướng mà độ cong có thể đi theo cả hai chiều, và chỉ cần một hướng có độ cong âm để biến điểm tới hạn thành điểm yên ngựa thay vì cực tiểu.

Điều đó quan trọng trong huấn luyện vì hạ gradient chỉ nhìn thấy gradient tại vị trí hiện tại.

Gần điểm yên ngựa, gradient trở nên nhỏ theo mọi hướng - tín hiệu giống hệt khi bạn tiến gần một cực tiểu thực sự. Quá trình huấn luyện có thể chậm lại hoặc mắc kẹt trong một vùng không hề tối ưu, và không thể phân biệt chỉ từ đường cong mất mát xem bạn đang ở gần cực tiểu hay mắc kẹt ở điểm yên ngựa.

Đó là lý do điểm yên ngựa thường xuất hiện cùng với cực tiểu cục bộ khi bàn về huấn luyện mạng nơ-ron. Nhưng chúng không phải trở ngại duy nhất. Gradient tiêu biến, độ cong kém điều kiện và quy mô không gian tìm kiếm cũng khiến tối ưu hóa nhiều chiều trở nên khó.

Các thuật toán tối ưu hóa xử lý điểm yên ngựa như thế nào

Điều này không có nghĩa là huấn luyện dựa trên gradient bị bó tay gần điểm yên ngựa. Có vài kỹ thuật có thể giúp bạn vượt qua, mỗi kỹ thuật tiếp cận từ một góc khác nhau.

Hạ gradient ngẫu nhiên

Hạ gradient ngẫu nhiên tính gradient từ một tập con ngẫu nhiên của dữ liệu huấn luyện thay vì toàn bộ tập dữ liệu, và tập con này thay đổi ở mỗi bước.

Nhiễu mà điều này tạo ra khiến gradient ước lượng hiếm khi chính xác bằng không, ngay cả trong vùng mà gradient thực sự gần bằng không. Lượng nhiễu đó có thể đủ để đẩy bộ tối ưu rời khỏi điểm yên ngựa và vào hướng có độ cong âm, thay vì dừng lại đúng nơi gradient triệt tiêu.

Động lượng

Động lượng duy trì trung bình trượt của các gradient trong quá khứ và dùng nó, thay vì chỉ gradient hiện tại, để quyết định bước tiếp theo.

Quanh điểm yên ngựa, điều này quan trọng vì bộ tối ưu đi đến đó với quán tính sẵn có, được tích lũy từ các gradient trước đó. Quán tính đó có thể đưa nó xuyên qua vùng phẳng quanh điểm yên ngựa, thay vì chậm lại ngay khi gradient cục bộ tiến gần về không.

Phương pháp bậc hai

Các phương pháp bậc hai sử dụng trực tiếp thông tin về độ cong.

Bằng cách làm việc với Hessian hoặc xấp xỉ của nó, các phương pháp này có thể phân biệt giữa các hướng có độ cong dương và các hướng có độ cong âm tại một điểm tới hạn. Đó là sự khác biệt cốt lõi của điểm yên ngựa, vì vậy phương pháp bậc hai có thể nhận diện hướng đi xuống và bước theo nó, thay vì đối xử mọi gradient gần bằng không như nhau.

Điểm yên ngựa và các khái niệm liên quan

Một vài thuật ngữ thường bị nhầm với điểm yên ngựa đủ nhiều để đáng bàn riêng.

Điểm yên ngựa so với cực tiểu cục bộ

Cực tiểu cục bộ cong lên theo mọi hướng quanh nó, nên là độ cong dương nhất quán, toàn bộ xung quanh. Điểm yên ngựa chỉ cong lên theo một số hướng và cong xuống theo số khác. Chỉ cần bạn tìm thấy một hướng có độ cong âm, bạn không còn nhìn vào cực tiểu nữa.

Điểm yên ngựa so với cực đại cục bộ

Lập luận tương tự theo chiều ngược lại cho cực đại cục bộ. Độ cong âm theo mọi hướng quanh nó. Điểm yên ngựa thêm ít nhất một hướng có độ cong dương bên cạnh các hướng âm.

Điểm yên ngựa so với điểm uốn

Điểm uốn là khái niệm một chiều. Đó là nơi một đường cong chuyển từ lõm lên sang lõm xuống, hoặc ngược lại, theo một biến duy nhất.

Điểm yên ngựa cần ít nhất hai biến, vì toàn bộ khái niệm phụ thuộc vào việc so sánh độ cong theo các hướng khác nhau tại cùng một điểm. Một hàm một biến có thể có điểm uốn, nhưng không thể có điểm yên ngựa, vì không có hướng thứ hai để cong theo chiều ngược lại.

Điểm yên ngựa so với điểm dừng

Mọi điểm yên ngựa đều là điểm dừng, vì gradient bằng không ở đó. Nhưng chiều ngược lại không đúng. Điểm dừng chỉ là bất kỳ điểm nào gradient bằng không - có thể là cực tiểu cục bộ, cực đại cục bộ hoặc điểm yên ngựa. Bạn cần thông tin về độ cong từ Hessian hoặc kiểm định đạo hàm bậc hai để biết mình đang có loại nào.

Dưới đây là phần tổng quan trực quan hơn về cách chúng so sánh:

So sánh điểm yên ngựa với các khái niệm khác

Điểm yên ngựa trong tối ưu hóa minimax

Đến giờ, “điểm yên ngựa” đã được dùng để mô tả độ cong tại điểm tới hạn. Còn một nghĩa thứ hai, cổ hơn xuất phát từ lý thuyết trò chơi, và nó cũng xuất hiện trong máy học hiện đại.

Trong tối ưu hóa minimax, một người chơi tối thiểu hóa một hàm trong khi người kia tối đa hóa nó, và điểm yên ngựa là cặp giá trị mà không bên nào có thể cải thiện kết quả của mình chỉ bằng cách tự thay đổi nước đi.

Lý thuyết trò chơi dùng điều này để mô tả chiến lược cân bằng trong các trò chơi cạnh tranh. Tối ưu hóa đối kháng mượn cấu trúc tương tự cho các bài toán nơi một quá trình tìm trường hợp xấu nhất mà quá trình khác phải phòng thủ.

Mạng đối sinh (GAN) là ví dụ máy học tiêu biểu. Bộ sinh tối thiểu hóa mất mát bằng cách tạo dữ liệu giả thuyết phục, trong khi bộ phân biệt tối đa hóa khả năng phân biệt dữ liệu thật và giả. Huấn luyện GAN đồng nghĩa với việc tìm một điểm yên ngựa theo nghĩa minimax này, hay một trạng thái cân bằng nơi bộ sinh và bộ phân biệt đều đã tìm được phản hồi tốt nhất với bên kia.

Điểm yên ngựa minimax có liên quan đến điểm yên ngựa kiểu điểm tới hạn ở phần trước, nhưng hai khái niệm không thể thay thế cho nhau.

Phiên bản điểm tới hạn mô tả độ cong tại một điểm của một hàm. Phiên bản minimax mô tả cân bằng giữa hai mục tiêu đối kháng. Cả hai dùng cùng một từ vì đều liên quan đến sự pha trộn “lên” và “xuống”, nhưng đánh đồng chúng sẽ không hữu ích nếu bạn cố áp dụng kiểm định dựa trên Hessian cho một trò chơi hai người.

Những lỗi thường gặp khi làm việc với điểm yên ngựa

Phần lớn sự nhầm lẫn về điểm yên ngựa xuất phát từ vài sai lầm lặp đi lặp lại. Dưới đây là điều bạn cần lưu ý.

Cho rằng gradient bằng không nghĩa là cực tiểu

Gradient bằng không chỉ cho bạn biết bạn đã tìm thấy một điểm tới hạn, không phải loại nào. Hãy kiểm tra độ cong trước khi cho rằng mình đã xong, vì một điểm yên ngựa cũng có gradient bằng không.

Phân loại điểm chỉ bằng đạo hàm bậc nhất

Đạo hàm bậc nhất tìm điểm tới hạn nhưng không thể phân loại chúng. Bạn cần đạo hàm bậc hai, thông qua Hessian hoặc kiểm định đạo hàm bậc hai, để phân biệt cực tiểu, cực đại và điểm yên ngựa.

Bỏ qua các hướng độ cong khác nhau

Một hàm có thể cong lên theo trục x nhưng vẫn là điểm yên ngựa tổng thể, nếu có hướng khác cong xuống. Hãy kiểm tra mọi hướng, hoặc dùng các trị riêng của Hessian, vốn bao quát tất cả cùng lúc.

Nhầm lẫn điểm yên ngựa với điểm uốn

Điểm uốn mô tả sự thay đổi độ cong theo một biến duy nhất. Điểm yên ngựa mô tả độ cong hỗn hợp qua nhiều biến tại cùng một điểm. Chúng liên quan ở ý niệm tổng quát, nhưng không áp dụng cho cùng một loại hàm, và phép toán đằng sau chúng không thể thay thế cho nhau.

Coi mọi cách dùng “điểm yên ngựa” là giống nhau

Điểm yên ngựa kiểu điểm tới hạn và điểm yên ngựa minimax chỉ chung tên gọi, không chung định nghĩa. Trước khi áp dụng kiểm định dựa trên Hessian hay lập luận về trị riêng, hãy kiểm tra xem nghĩa nào đang được dùng - lý thuyết trò chơi và tối ưu hóa đối kháng dùng phiên bản minimax, và nó không quy về kiểm tra độ cong của một hàm đơn.

Kết luận

Điểm yên ngựa cong lên theo một số hướng và cong xuống theo số khác, tại cùng tọa độ - đó là lý do nó không phải cực tiểu hay cực đại, dù gradient tiến về không ở đó giống như ở cả hai loại kia.

Gradient giúp tìm điểm tới hạn. Trị riêng của Hessian, hoặc kiểm định đạo hàm bậc hai, cho bạn biết đó là loại nào. Trong không gian nhiều chiều, khác biệt này rất quan trọng vì điểm yên ngựa nhiều hơn cực tiểu cục bộ, và các thuật toán huấn luyện như SGD và động lượng tồn tại một phần để vượt qua chúng.

Một điều cuối cần tách bạch là điểm yên ngựa minimax từ lý thuyết trò chơi và GANs cùng tên nhưng không cùng phép toán - hãy chắc rằng bạn biết mình đang nói đến loại nào.

Nếu bạn thấy ý tưởng về điểm yên ngựa thú vị, bạn sẽ thích Lộ trình Deep Learning bằng Python của chúng tôi. Bên cạnh lý thuyết, bạn sẽ dùng PyTorch để tạo mạng nơ-ron cho nhiều loại bài toán.