Gradient descent
Gradient descent
Thả một điểm lên đường cong mất mát rồi xem nó lăn xuống đáy.
Gần như mọi mô hình học máy đều được huấn luyện bằng đúng một ý tưởng: viết ra một con số đo độ sai, rồi đi từng bước nhỏ theo hướng làm con số đó giảm. Bài này mổ cái bước nhỏ ấy ra, trên trường hợp đơn giản nhất còn giữ được toàn bộ bài học, tức một biến và một đường cong.
Kéo điểm xuất phát dọc theo đường cong, chỉnh tốc độ học, rồi bấm chạy để xem nó lăn tới đáy hay vọt qua. Đường cong trong sim là f(x) = 0.5·(x - 2)², nên đạo hàm của nó là f'(x) = x - 2 và đáy nằm ở x = 2.
Ở trạng thái mở đầu, sim đang nói gì
Mặc định điểm xuất phát là x = -1, tốc độ học là 0.60, và hệ được phép đi tối đa 40 bước. Tại chỗ xuất phát, mất mát là 4.50 và gradient là -3.00.
Bấm chạy thì nó dừng sau đúng 9 bước, tức quỹ đạo có 10 điểm kể cả điểm đầu. Nhãn trạng thái ghi đã hội tụ, và ba ô số dưới hình đọc x = 2.00, f(x) = 0.00, f'(x) = -0.00.
Cả ba con số đó đều đã bị làm tròn về hai chữ số thập phân, và không con nào đúng bằng cái nó hiển thị. Giá trị x thật là 1.999213568, tức còn cách đáy 0.000786432. Mất mát thật là 3.092376453119592e-7, khác 0. Còn gradient thì giữ được dấu trừ sau khi làm tròn, và cái dấu trừ trong -0.00 chính là mẩu thông tin duy nhất cho bạn biết nó vẫn chưa tới đáy.
Gradient là gì, và vì sao đi ngược nó thì hàm giảm
Gradient tại một điểm là đạo hàm tại đó. Trong một chiều nó là một số, và số đó là độ dốc của tiếp tuyến. Dấu của nó trả lời một câu hỏi: đi sang phải thì hàm tăng hay giảm.
Ở x = -1 gradient bằng -3. Dấu âm nghĩa là đi sang phải thì hàm giảm, nên hướng đi xuống là ngược dấu gradient. Đó là toàn bộ lý do quy tắc cập nhật có dấu trừ:
x mới = x cũ - η · f'(x cũ)
Thay số vào với η = 0.6: -1 - 0.6·(-3) cho 0.7999999999999998, và mất mát ở đó là 0.72. Một bước đã cắt mất mát từ 4.50 xuống 0.72.
Bỏ dấu trừ đi thì chuyện ngược lại xảy ra ngay lập tức. -1 + 0.6·(-3) cho -2.8, và mất mát ở đó là 11.52, cao hơn cả 4.50 mà nó vừa đứng. Cùng một điểm, cùng một độ dài bước, chỉ khác một dấu, và một bên đi xuống còn một bên leo lên.
Mũi tên cam trong sim vẽ đúng cái hướng ngược gradient đó. Nhưng hãy đọc nó như một hướng, không phải một bước: độ dài mũi tên là cố định cho dễ nhìn, nên ở gần đáy đầu mũi tên còn vượt qua bên kia đáy và đậu ở chỗ cao hơn chỗ nó khởi hành. Điều đó xảy ra trên 1580 trong 14000 vị trí đã quét, cụ thể là dải từ x = 1.605 tới x = 2.395. Ví dụ ở x = 1.605, mũi tên chỉ đúng hướng nhưng đầu nó đậu ở 2.3956.
Mỗi bước cắt đi một phần cố định của khoảng cách còn lại
Đường cong này đủ đơn giản để giải hẳn ra. Đặt e = x - 2, tức khoảng cách có dấu tới đáy. Một bước cập nhật cho:
e mới = e cũ · (1 - η)
nên sau k bước thì e = e ban đầu · (1 - η)^k. Không có vòng lặp nào ở đây, chỉ một luỹ thừa.
Ở trạng thái mở đầu, η = 0.60 nên hệ số nhân là 0.4, và e ban đầu bằng -3. Dãy x vì thế là 2 - 3·0.4^k, và nó cho đúng những con số sim in ra: x sau 1 bước là 0.7999999999999998, sau 2 bước là 1.52, sau 5 bước là 1.96928, sau 9 bước là 1.999213568.
Đọc công thức đó ra thì thấy ngay một điều: mỗi bước cắt đi 60 phần trăm khoảng cách còn lại, nên khoảng cách nhỏ dần theo cấp số nhân và không bao giờ bằng 0. Trong cả 9 bước của trạng thái mở đầu, không bước nào đặt x đúng vào 2. Cái làm sim dừng không phải việc tới đáy, mà là một ngưỡng, và mục dưới nói về ngưỡng đó.
Tốc độ học: núm quan trọng nhất, và mốc phân kỳ là 2
Với dạng tổng quát f(x) = a·(x - m)², hệ số nhân mỗi bước là 1 - 2·a·η. Khoảng cách tới đáy co lại khi và chỉ khi |1 - 2·a·η| < 1, tức khi η < 1/a. Đường cong trong sim có a = 0.5, nên mốc là η = 2. Đó là đại số, không phải quan sát.
Đo trên sim thì đúng khớp, và ba mốc kề nhau cho ba kết cục khác nhau:
- Dưới mốc. Có
5499cấu hình gồm 141 vị trí xuất phát nhân 39 nấc tốc độ học nhỏ hơn2. Cho đủ chỗ thì cả 5499 đều hội tụ, không trừ cái nào. Chậm nhất là160bước, ở nấc0.05xuất phát từ mép tráix = -1.5. - Đúng mốc. Ở
η = 2hệ số nhân bằng đúng-1, nên khoảng cách tới đáy không co cũng không phình, chỉ đổi dấu. Quỹ đạo từx = -1chỉ ghé đúng hai chỗ,-1và5, và làm thế mãi mãi: chạy400bước vẫn vậy. Khoảng cách tới đáy bị đóng băng đúng như thế từ cả 141 vị trí xuất phát. Nhãn ghichưa hội tụ (dao động), và đó là câu đúng: nó không hội tụ, mà cũng không phân kỳ. - Trên mốc. Hệ số nhân có độ lớn hơn
1nên khoảng cách phình ra theo cấp số nhân. Trong423cấu hình cóηtừ2trở lên, chỉ3cái hội tụ, và cả ba là cùng một chuyện: xuất phát đúng tạix = 2, chỗ mà gradient đã bằng0nên tốc độ học không còn nghĩa gì.
Nhãn phân kỳ không phải là phép phân kỳ
Đây là chỗ dễ bị lừa nhất, và cũng là chỗ đặc tả ban đầu của bài này sai.
Sim chỉ ghi phân kỳ khi điểm đi quá 50 đơn vị khỏi đáy, và làm được việc đó trong 40 bước. Hai điều kiện, không phải một. Ở η = 2.05 khoảng cách thật sự phình ra, nhưng từ điểm mặc định nó cần 58 bước mới vượt 50, mà ngân sách chỉ có 40. Nên sau 40 bước nó mới ở x = -19.12, và nhãn ghi chưa hội tụ (dao động) chứ không ghi phân kỳ.
Quét cả 141 vị trí xuất phát thì ở η = 2.05 có 0 vị trí nào lấy được nhãn phân kỳ trong 40 bước. Nấc đầu tiên bật được nhãn đó từ điểm mặc định là η = 2.10, ở đó chỉ cần 30 bước. Mà ngay tại 2.10 cũng chỉ 96 trong 141 vị trí bật được nhãn: 45 vị trí còn lại nằm trong vòng 1.105 đơn vị quanh đáy, khởi động quá gần nên 40 lần phình vẫn chưa đủ xa.
Vậy có thước nào nhạy hơn không. Có, và nó nằm ngay trên hình: chữ phân kỳ kèm mũi tên ở mép khung, bật khi quỹ đạo rời khỏi vùng vẽ. Đo trên 5640 cấu hình có η nhỏ hơn hoặc bằng mốc thì cảnh báo đó chưa bao giờ bật lần nào, còn trong 282 cấu hình trên mốc thì nó bật 258 lần. Nói cách khác, rời khỏi khung thì chắc chắn là đã vượt mốc, nhưng vượt mốc thì chưa chắc rời khỏi khung kịp trong 40 bước.
Bài học chung: một nhãn trên giao diện là một phép đo có ngân sách, không phải một định lý. Muốn kết luận về phép tính thì phải biết ngân sách của phép đo là bao nhiêu.
Số bước không phải thước đo tốt
Nhìn số bước thì dễ tưởng tốc độ học càng lớn càng nhanh. Không phải. Đếm số bước cần thiết khi xuất phát từ x = -1 và cho đủ chỗ:
| Tốc độ học | Số bước để hội tụ |
|---|---|
0.05 | 157 |
0.60 | 9 |
1.00 | 1 |
1.40 | 9 |
1.95 | 157 |
Đường này có dạng chữ U với đáy ở η = 1, nơi hệ số nhân bằng đúng 0, nên một bước duy nhất đặt điểm thẳng vào đáy. Hai bên đáy thì tăng lên đối xứng: 0.60 và 1.40 cần đúng cùng 9 bước, 0.05 và 1.95 cần đúng cùng 157 bước.
Tính đối xứng đó gần như hoàn hảo nhưng không hoàn hảo, và chỗ nó vỡ đáng ghi lại. Quét 2679 cặp gồm 141 vị trí xuất phát nhân 19 cặp tốc độ học đối xứng, có đúng 1 cặp lệch: xuất phát từ x = 3, nấc 0.9 cần 3 bước còn nấc 1.1 cần 4. Lý do là dấu phẩy động, không phải quy luật: |1 - 0.9| tính ra trong máy nhỏ hơn một chút so với |1 - 1.1|, nên bên này lọt dưới ngưỡng sớm hơn một bước. Đại số nói cặp đó cần 4 bước cả hai bên.
Kể cả khi đối xứng, hai nấc cùng số bước vẫn không giống nhau chút nào. Trong ngân sách 40 bước, η = 0.05 dùng hết 40 bước rồi dừng ở x = 1.61 và nhãn ghi chưa tới đáy (còn chậm), vì nó bò từ một phía và chưa bao giờ băng qua đáy. Còn η = 1.95 cũng dùng hết 40 bước, nhưng nhãn ghi chưa hội tụ (dao động), vì nó băng qua đáy ở mỗi bước. Sim chia hai câu đó ra vì đây là hai kiểu thất bại khác nhau: một cái cần thêm thời gian, cái kia cần đổi tham số.
Và mỗi bước đều có giá thật. Trong huấn luyện thật, một bước nghĩa là một lượt truyền xuôi cộng một lượt truyền ngược trên một lô dữ liệu, tức thời gian máy và điện. Vì vậy thước đo có nghĩa không phải là số bước, mà là chi phí để đạt một mức sai số. Hai cấu hình cùng 157 bước có thể tốn khác nhau rất xa nếu kích thước lô khác nhau, và một cấu hình 9 bước trên lô lớn có thể đắt hơn 157 bước trên lô nhỏ.
Gradient bằng 0 không có nghĩa là đã tới đáy
Luật dừng của sim đọc duy nhất gradient: khi |f'(x)| nhỏ hơn 1e-3 thì nó báo đã hội tụ. Nó không xem f(x) bằng bao nhiêu, và cũng không biết đáy nằm ở đâu.
Hệ quả đo được ngay: kéo điểm xuất phát về x = 2.001. Ở đó |f'| bằng 0.001, vừa lọt dưới ngưỡng, nên sim dừng sau 0 bước và báo đã hội tụ, dù mất mát ở đó là 5e-7, khác 0, và vị trí không phải đáy. Nhích thêm một chút sang x = 2.0011 thì gradient vượt ngưỡng và nó chịu đi một bước. Quét cả 141 vị trí xuất phát ở tốc độ mặc định thì có 140 vị trí kết thúc với mất mát dương; chỗ duy nhất kết thúc ở 0 là chỗ vốn đã khởi động đúng tại đáy.
Trong không gian nhiều chiều, chuyện này nặng hơn nhiều, và tên của nó là điểm yên với cao nguyên. Điểm yên là chỗ gradient bằng 0 nhưng nó là cực tiểu theo một số hướng và cực đại theo các hướng khác, nên nó không phải đáy gì cả. Cao nguyên là vùng gradient rất nhỏ trên một quãng dài, nên bước đi cũng rất nhỏ và tưởng như đã dừng. Cả hai đều làm một luật dừng chỉ nhìn gradient tuyên bố thắng lợi ở chỗ không phải đáy.
Phải nói thẳng ở đây: sim này không thể cho bạn thấy điểm yên hay cao nguyên, vì một parabol không có cái nào cả. Trên toàn dải vẽ, gradient bằng đúng 0 tại đúng 1 trong 14001 vị trí đã quét, và đó chính là đáy. Cái sim cho thấy được là mảnh có thật của bài học: một ngưỡng trên gradient là một quy ước, và cái nó chứng nhận là "đã đủ phẳng", không phải "đã tới đáy". Thêm nữa, ngưỡng gradient ở đây tình cờ trùng với ngưỡng khoảng cách, vì f'' bằng 1 nên gradient bằng đúng khoảng cách tới đáy; trên một đường cong khác thì hai thứ đó khác nhau, và trùng hợp này không phải quy luật.
Cực tiểu địa phương, và vì sao sim này không chứng minh được nó
Câu chuyện quen thuộc về gradient descent nói rằng nó có thể mắc kẹt ở một cực tiểu địa phương, tức một cái hố không phải hố sâu nhất, và điểm khởi đầu quyết định bạn rơi vào hố nào. Câu đó đúng cho những mặt mất mát thật, và nó là lý do người ta khởi tạo lại nhiều lần rồi so kết quả.
Nhưng đường cong trong sim này lồi và chỉ có một cực tiểu, nên nó không thể minh hoạ chuyện đó, và tôi nói ra thay vì để bạn tưởng đã thấy. Số đo chứng minh điều đó:
- Ở tốc độ mặc định, cả
141vị trí xuất phát mà thao tác kéo chạm tới được đều hội tụ, và cả 141 đều kết thúc ở cùng một số hiển thị,2.00. - Vị trí xuất phát chỉ đổi được thời gian đi, và tệ nhất cũng chỉ
9bước, tức vẫn trong ngân sách 40. - Gradient tăng ngặt ở cả
14000bước quét, tức đường cong lồi ngặt, và nó cắt trục0đúng1lần.
Ba số đó cùng nói một câu: ở đây chỉ có một lòng chảo, nên không có hố nào khác để rơi vào.
Muốn thấy cực tiểu địa phương thật thì cần một hàm có hai đáy trở lên, và hàm nhỏ nhất làm được việc đó là một đa thức bậc bốn, ví dụ g(x) = x⁴ - 3x² + x. Đạo hàm của nó là g'(x) = 4x³ - 6x + 1, và nó có ba điểm dừng: hai đáy ở x = -1.3008 với g = -3.5139 và ở x = 1.1309 với g = -1.0702, cùng một đỉnh ở giữa tại x = 0.1699. Hai đáy sâu khác nhau, nên một cái là cực tiểu toàn cục còn cái kia chỉ là cực tiểu địa phương.
Chạy đúng quy tắc cập nhật của bài này trên hàm đó thì điểm khởi đầu quyết định số phận: xuất phát từ x = -0.5 thì nó lăn vào hố sâu, xuất phát từ x = 0.5 thì nó lăn vào hố cạn, cùng tốc độ học và cùng công thức. Đường phân chia hai lòng chảo chính là cái đỉnh ở 0.1699: nhích một phần trăm sang mỗi bên là đi về hai hố ngược nhau. Và điều đáng lo nhất: cả hai lần đều dừng với gradient nhỏ hơn 1e-6, nên nếu bạn chỉ đọc gradient thì không có cách nào biết mình đã dừng ở hố cạn. Đó mới là hình vẽ chứng minh được câu chuyện, và nó không phải hình bạn đang xem.
Gradient chỉ cho hướng, còn tốc độ học quyết định số phận. Mốc đổi chế độ suy được bằng đại số chứ không cần đo: với f(x) = a·(x - m)² thì hệ số co mỗi bước là 1 - 2·a·η, nên hội tụ khi η < 1/a, và ở sim này mốc là η = 2. Ba điều còn lại đừng lẫn: nhãn phân kỳ là một phép đo có ngân sách 40 bước chứ không phải định lý, nên nó chỉ bật từ η = 2.10; số bước có dạng chữ U với đáy ở η = 1 nên nhỏ hơn không có nghĩa là chậm hơn; và một ngưỡng trên gradient chứng nhận "đã đủ phẳng" chứ không chứng nhận "đã tới đáy".
- 1Đặt tốc độ học đúng bằng 2 rồi bấm chạy. Điều gì xảy ra?
- 2Đặt tốc độ học 0.05 rồi bấm chạy hết 40 bước. Kết luận nào đúng?
- 3Kéo điểm xuất phát tới x = 2.001. Sim báo đã hội tụ sau 0 bước. Vì sao?