ลงเขา: Gradient Descent และสองขั้นตอนที่ทุกคนมักข้าม

ทบทวนใหม่เพื่อให้บทนี้ยืนได้ด้วยตัวเอง: ชิ้นส่วนทั้งแปดจากสายพานลำเลียงใน บทที่ 1 แต่ถามคำถามคนละแบบ ไม่ใช่ รับหรือปฏิเสธ — เรื่องนั้นจะกลับมาทีหลัง — แต่เป็น ทำนายน้ำหนักของชิ้นส่วนจากความกว้างของมัน

import numpy as np

WIDTH  = np.array([18.0, 19.5, 20.2, 21.0, 24.0, 25.5, 23.0, 26.0])
WEIGHT = np.array([47.0, 52.0, 49.0, 55.0, 61.0, 66.0, 70.0, 58.0])

x = WIDTH  - WIDTH.mean()      # 22.15 mm
y = WEIGHT - WEIGHT.mean()     # 57.25 g

ค่าการวัดถูก centered ไว้แล้ว เหมือนในบทที่ 1 และด้วยเหตุผลที่จะกลับมาให้ผลตอบแทนก่อนจบบทนี้ โมเดลคือเส้นตรง $\hat{y} = a x + b$ และ loss คือ mean squared error ที่บทก่อนหน้าอนุมานไว้:

พารามิเตอร์สองตัว ทำไมไม่ลองค่าจำนวนมากไปเลย? ลองทำจริง ๆ กัน — grid จาก $a = 0$ ถึง $5$ และ $b = -5$ ถึง $5$ โดยก้าวทีละ $0.01$:

grid 501 x 1001 = 501,501 evaluations in 3.67 s
  best found: a = 2.1000, b = -0.0000, L = 24.592450

ประเมินครึ่งล้านครั้งเพื่อปักหมุดตัวเลขสองตัวให้ได้สองตำแหน่งทศนิยม — และวินาทีนั้นเป็นเวลา wall clock บนเครื่องหนึ่ง ดังนั้นรันใหม่อาจอยู่ที่สามถึงหกวินาที; จำนวนการประเมินและค่าต่ำสุดคือส่วนที่ทำซ้ำได้ Gradient descent ตอนท้ายบทนี้ได้สี่ตำแหน่งทศนิยมใน แปดก้าว และได้คำตอบ float64 เต็มในสามสิบหกก้าว

แต่ความเร็วไม่ใช่ข้อโต้แย้ง และนี่คือจุดที่ตัดสินทั้งคอร์ส Grid search ใช้ต้นทุน $k^P$ การประเมินสำหรับพารามิเตอร์ $P$ ตัว ที่แต่ละตัวมี $k$ ค่า ถ้ามีหนึ่งพันค่าต่อแกน:

แถวที่สามไม่ใช่จำนวนที่ใหญ่ แต่เป็นจำนวนที่ ไร้ความหมาย — มีอะตอมในเอกภพที่สังเกตได้ประมาณ $10^{80}$ อะตอม Search ไม่ได้แค่ช้าลงเมื่อโมเดลโตขึ้น แต่มันหยุดมีตัวตน ทุกอย่างต่อจากนี้มีอยู่เพราะตารางนั้น

ตรึง $b = 0$ ไว้ชั่วครู่ เพื่อให้เหลือพารามิเตอร์ตัวเดียวและเส้นโค้งเส้นเดียว ซึ่งเป็นภาพที่บทก่อนหน้าทิ้งไว้ให้คุณ หยิบจุดหนึ่งบนเส้นนั้น $a = 1$ แล้วถามว่า: ถ้าฉันขยับ $a$ เล็กน้อยเป็นจำนวน $h$ loss จะขยับเท่าไรต่อหนึ่งหน่วยของการขยับ?

อัตราส่วนนั้นคือ rise over run — ความชันของเส้นตรงที่ผ่านสองจุดบนเส้นโค้ง เมื่อ $h$ เล็กลง จุดสองจุดเลื่อนเข้าใกล้กัน และเส้นตรงกลายเป็นเส้นสัมผัส ความชันของมันคือ อนุพันธ์ $L'(a)$: อัตราที่ loss เปลี่ยนต่อหนึ่งหน่วยการเปลี่ยนของ $a$ มันไม่ใช่การประมาณอะไรบางอย่าง และไม่ใช่ปริมาณที่เล็กอย่างไม่มีที่สิ้นสุด แต่เป็นลิมิตของอัตราส่วนธรรมดา

ควรรันดู เพราะตัวเลขบอกบางอย่างที่นิยามไม่ได้บอก:

def loss1(a):
    return np.mean((a * x - y) ** 2)

for h in [1.0, 1e-2, 1e-4, 1e-6, 1e-8, 1e-10, 1e-12, 1e-14]:
    q = (loss1(1.0 + h) - loss1(1.0)) / h
    print(f"h = {h:<8.0e}   slope estimate = {q:.10f}   error = {abs(q + 16.385):.3e}")

h = 1e+00      slope estimate = -8.9400000000    error = 7.445e+00
h = 1e-02      slope estimate = -16.3105500000   error = 7.445e-02
h = 1e-04      slope estimate = -16.3842555001   error = 7.445e-04
h = 1e-06      slope estimate = -16.3849925556   error = 7.444e-06
h = 1e-08      slope estimate = -16.3850003787   error = 3.787e-07
h = 1e-10      slope estimate = -16.3850444324   error = 4.443e-05
h = 1e-12      slope estimate = -16.3851154866   error = 1.155e-04
h = 1e-14      slope estimate = -17.0530256582   error = 6.680e-01

มีสองสิ่งเกิดขึ้นตรงนี้ และทั้งสองเป็นเสาหลักของเรื่อง

error ไม่ได้แค่แปรผันคร่าว ๆ กับ $h$ — แต่มันเท่ากับ $7.445\,h$ อย่างพอดี หาร $h$ ด้วยร้อย error ก็หารด้วยร้อย ทุกครั้งถึงสี่เลขนัยสำคัญ ค่าคงที่นั้นไม่ใช่ของตกแต่ง: มันคือครึ่งหนึ่งของอนุพันธ์ อันดับสอง ของ loss และเป็นการปรากฏครั้งแรกของแนวคิดที่จะมาในอีกสองส่วนข้างหน้า — ว่าเส้นโค้งใกล้จุดหนึ่งดูเหมือนเส้นตรงบวก correction ที่แปรผันกับ $h^2$

แล้ว pattern ก็พัง ต่ำกว่า $h = 10^{-8}$ ค่าประมาณกลับ แย่ลง และที่ $10^{-14}$ มันผิดตั้งแต่หลักที่สอง ไม่มีอะไรทางคณิตศาสตร์เกิดขึ้น; กล่อง floating-point จากบทก่อนหน้าต่างหากที่เกิดขึ้น $L(a+h)$ และ $L(a)$ ตรงกันในสิบหลักแรก การลบมันทำลายหลักเหล่านั้น แล้วการหารซากที่เหลือด้วยจำนวน tiny ก็ขยายสิ่งที่เหลืออยู่ มี $h$ ที่ดีที่สุด — ที่นี่ราว $10^{-8}$ ประมาณรากที่สองของ machine epsilon — และการทำให้เล็กลงไม่ใช่ระมัดระวังขึ้น แต่ระมัดระวังน้อยลง จำเรื่องนี้ไว้; ฟังก์ชันตอนท้ายบทนี้ต้องพึ่งมัน

ความชันที่แน่นอน จากแคลคูลัสแทนการวัด คือ $-16.385$ ดังนั้นเราหยุดวัดแล้วเริ่มอนุมานได้

นี่คือแนวคิดที่ส่วนที่เหลือของคอร์สสร้างอยู่บนนั้น กล่าวครั้งเดียวอย่างตรงไปตรงมา

การ ประกอบ ฟังก์ชันสองตัวคือการป้อนตัวหนึ่งเข้าไปในอีกตัวหนึ่ง: $(f \circ g)(x) = f(g(x))$ แค่นั้น

เครือข่าย deep network ไม่ได้ เหมือน การประกอบ แต่มัน คือ การประกอบ layer คือฟังก์ชัน; การวาง layer ซ้อนกันคือการประกอบมัน; “ความลึก” คือจำนวนฟังก์ชันใน chain เมื่อบทที่ 5 สร้างเครือข่าย มันกำลังสร้าง $f_4 \circ f_3 \circ f_2 \circ f_1$ และไม่มีอะไรมากกว่านั้น ซึ่งแปลว่ากฎแคลคูลัสที่สำคัญที่สุดข้อเดียวสำหรับจุดประสงค์ของเรา คือกฎที่หาอนุพันธ์ของการประกอบ:

อัตราจะคูณกัน ถ้า $g$ เปลี่ยนเร็วกว่า $x$ สามเท่า และ $f$ เปลี่ยนเร็วกว่า $g$ สองเท่า แล้ว $f$ จะเปลี่ยนเร็วกว่า $x$ หกเท่า นี่คือเนื้อหาทั้งหมด และเป็นเหตุผลว่าทำไมสัญญาณที่ส่งย้อนผ่านสิบ layer จึงถูกคูณด้วยตัวเลขสิบตัว — ซึ่งเป็นเหตุผลที่ บทที่ 6 ใช้หนึ่งส่วนพูดถึงสิ่งที่เกิดขึ้นเมื่อเลขเหล่านั้นทั้งหมดน้อยกว่าหนึ่งเล็กน้อย

ใช้มันกับ loss ของเรา เขียน residual เป็น $r_i = a x_i + b - y_i$ เพื่อให้ $L = \frac{1}{n}\sum r_i^2$ แต่ละ $r_i$ ขึ้นกับ $a$ ผ่านฟังก์ชันด้านใน $a x_i$ ซึ่งมีอนุพันธ์ $x_i$ ใช้ chain rule ทีละเทอม:

สัญลักษณ์โค้ง $\partial$ เหล่านั้นหมายถึง อนุพันธ์ย่อย: หาอนุพันธ์เทียบกับตัวแปรหนึ่ง และถือว่าตัวอื่นทั้งหมดเป็นค่าคงที่ ไม่มีอะไรใหม่เกิดขึ้น — มันคือลิมิตเดิม เพียงแต่ทำตามแกนหนึ่ง รวบรวมอนุพันธ์ย่อยเป็นเวกเตอร์ แล้วคุณได้ gradient:

ที่จุด $(a, b) = (1, 4)$ เวกเตอร์นั้นคือ $(-16.385,\ 8.0)$ ตัวเลขสองตัว คำถามคือมันหมายความว่าอะไร และนี่คือขั้นตอนแรกที่ทุกคนข้าม

gradient คือเวกเตอร์ของความชัน ตามแกน เท่านั้น นั่นคือทั้งหมดที่เราพิสูจน์ไปแล้ว มันไม่ชัดเจน — และไม่ควรชัดเจน — ว่าการเอามันมาประกอบเป็นเวกเตอร์จะให้สิ่งที่ชี้ไปทางใดทางหนึ่งโดยเฉพาะ

ดังนั้นนิยามสิ่งที่เราต้องการจริง ๆ เลือกเวกเตอร์หน่วย $\mathbf{u}$ ซึ่งเป็นทิศทางหนึ่ง directional derivative คืออัตราที่ loss เปลี่ยนเมื่อคุณเดินไปทางนั้น:

chain rule ทำให้สิ่งนี้คำนวณได้ การเดินตาม $\mathbf{u}$ เปลี่ยน $a$ ด้วยอัตรา $u_1$ และเปลี่ยน $b$ ด้วยอัตรา $u_2$ แล้วผลสนับสนุนเหล่านี้บวกกัน:

อัตราการเปลี่ยนใน ทุก ทิศทางคือ dot product ของ gradient กับทิศทางนั้น และตอนนี้คือ punchline ซึ่งเป็นเรขาคณิตเพียงบรรทัดเดียว เขียน dot product ด้วยมุม $\phi$ ระหว่างเวกเตอร์:

เพราะ $\mathbf{u}$ มีความยาว 1 สิ่งเดียวที่คุณควบคุมคือ $\cos\phi$ ซึ่งมากที่สุดที่ $\phi = 0$ และน้อยที่สุดเมื่อหมุนครึ่งรอบ $\phi = 180$ องศา ดังนั้น:

• ขึ้นชันที่สุด คือไปตาม $\nabla L$ เอง และความชันตรงนั้นคือ $\lVert \nabla L \rVert$ พอดี
• ลงชันที่สุด คือไปตาม $-\nabla L$ และความชันตรงนั้นคือ $-\lVert \nabla L \rVert$
• ตั้งฉากกับ gradient, loss ไม่เปลี่ยนเลย นั่นคือเหตุผลที่เส้นบน contour map ตัดกับ gradient เป็นมุมฉาก

นั่นคือเครื่องหมายลบ ไม่ใช่ขนบ ไม่ใช่การกลับเครื่องหมายที่ใครบางคนเลือก: ทิศทางที่ลดลงเร็วที่สุดคือ negative gradient เพราะ $\cos\phi$ มีค่าน้อยที่สุดเมื่อหมุนครึ่งรอบ และไม่มีเหตุผลอื่น

เพราะนี่เป็นข้อกล่าวอ้างเกี่ยวกับทุกทิศทาง จึงทดสอบกับทุกทิศทาง ลองสุ่ม 3,600 ทิศทาง หนึ่งทิศต่อหนึ่งในสิบองศา แล้ววัดแต่ละทิศด้วยการขยับเล็กน้อย:

theta = np.array([1.0, 4.0])
g = grad(theta)
print("gradient      ", g)
print("its length    ", np.linalg.norm(g))
print("its angle     ", np.degrees(np.arctan2(g[1], g[0])) % 360, "degrees")

best = max(
    ((loss(theta + 1e-6 * u) - loss(theta - 1e-6 * u)) / 2e-6, np.degrees(ang))
    for ang, u in (
        (a, np.array([np.cos(a), np.sin(a)])) for a in np.arange(3600) * 2 * np.pi / 3600
    )
)
print("steepest slope", best[0], "at", best[1], "degrees")

gradient       [-16.385   8.   ]
its length     18.23371122399386
its angle      153.97598928042032 degrees
steepest slope 18.233709624837502 at 154.0 degrees

การค้นหาที่ไม่รู้อะไรเกี่ยวกับ gradient เลย เหนือ 3,600 ทิศทาง พบการไต่ที่ชันที่สุดที่ 154.0 องศา — ซึ่งเป็นทิศของ gradient เอง ภายในความละเอียด 0.1 องศาของการค้นหา และความชันที่มันพบตรงนั้น 18.2337 คือความยาวของ gradient ถึงหกหลัก ทฤษฎีบทนี้ไม่ใช่เรื่องเล่าเกี่ยวกับความหมายของ gradient; มันเป็นข้อเท็จจริงที่วัดได้ และนั่นคือการวัด

ตอนนี้คือขั้นตอนที่สองที่ถูกข้าม เรารู้แล้วว่าทางไหนลง แต่ไม่ได้แปลว่าการเดินไปทางนั้นจะลด loss เพราะ “ลง” เป็นข้อความเกี่ยวกับการขยับเล็กอย่างอนันต์ ส่วนก้าวไม่ใช่อนันต์เล็ก

สะพานเชื่อมคือ linearisation ใกล้จุดหนึ่ง ฟังก์ชันที่ smooth คือเส้นสัมผัสของมันบวก correction:

นั่นคือ Taylor expansion อันดับหนึ่ง เทอม $O(\lVert\boldsymbol{\delta}\rVert^2)$ ที่ทิ้งไปคือ curvature — เทอมเดียวกับที่ทำให้ค่าประมาณในตารางความชันผิดไปพอดี $7.445\,h$ ใส่ก้าวที่เราตั้งใจจะเดิน $\boldsymbol{\delta} = -\eta \nabla L$ เข้าไป:

loss ลดลง $\eta \lVert \nabla L \rVert^2$ ทุกส่วนของสิ่งนั้นไม่เป็นลบ ดังนั้นคำสัญญานี้เป็นจริง — สำหรับ $\eta$ ที่เล็กพอ เพราะเทอมที่ละเลยโตแบบ $\eta^2$ และท้ายที่สุดจะกินมันหมด นั่นคือทฤษฎีทั้งหมด นี่คือคำสัญญาที่ถูกรักษาไว้ แล้วจากนั้นก็ถูกทำลาย:

eta = 0.2       promised    66.49364500   delivered   -16.01619240   ratio -0.240868
eta = 0.1       promised    33.24682250   delivered    12.61936315   ratio  0.379566
eta = 0.01      promised     3.32468225   delivered     3.11840766   ratio  0.937957
eta = 0.001     promised     0.33246822   delivered     0.33040548   ratio  0.993796
eta = 0.0001    promised     0.03324682   delivered     0.03322620   ratio  0.999380
eta = 1e-05     promised     0.00332468   delivered     0.00332448   ratio  0.999938

อ่านจากล่างขึ้นบน เมื่อ $\eta$ เล็กลง drop ที่ได้จริงลู่เข้าหา drop ที่สัญญาไว้ — ratio 0.99938 แล้ว 0.99994 — ซึ่งคือ Taylor theorem ที่ถูกต้อง อ่านจากบนลงล่าง และที่ $\eta = 0.2$ “drop” ที่ได้จริงคือ ติดลบสิบหก ก้าวนั้นเดินลงเขา แต่ loss กลับเพิ่มขึ้น

ดังนั้นกฎการอัปเดตคือ

และมันมาพร้อมเงื่อนไขที่ไม่มีใครบอก คือ $\eta$ ต้องเล็กพอ เล็กพอเมื่อเทียบกับ อะไร กันแน่ คือส่วนถัดไป

เริ่มจากหุบเขาที่ง่ายที่สุด $f(x) = x^2$ โดยที่ $f'(x) = 2x$ หนึ่งก้าวของ gradient descent คือ

ตำแหน่งถูกคูณด้วย $(1 - 2\eta)$ ในทุกก้าว นั่นคือ geometric sequence และ geometric sequence มีกฎเดียวอย่างแน่ชัด: มันหดเมื่อตัวคูณมีค่าสัมบูรณ์น้อยกว่า 1 และโตในกรณีอื่น ดังนั้น $\lvert 1 - 2\eta \rvert < 1$ ซึ่งคือ $0 < \eta < 1$

ขอบเขตอยู่ที่ $\eta = 1$ พอดี ไม่ใช่ “ประมาณ 1” ไม่ใช่ “1 มักใหญ่เกินไป” ที่ $\eta = 1$ ตัวคูณคือ $-1$ และจุดจะเด้งไปมาระหว่าง $x$ กับ $-x$ ตลอดกาล ไม่เข้าใกล้และไม่หนีออกไป ต่ำกว่านั้น converge; สูงกว่านั้น diverge ช่วงยังแยกอีกครั้งที่ $\eta = 0.5$ ซึ่งตัวคูณเปลี่ยนเครื่องหมาย: ต่ำกว่านั้นการเข้าใกล้เป็น monotone สูงกว่านั้นจุดจะ overshoot และสลับข้าง และที่ $0.5$ พอดี ตัวคูณเป็น 0 และก้าวเดียวก็ลงถึงค่าต่ำสุด

สี่ regime จากพีชคณิตสี่บรรทัด ลองข้ามขอบเขตด้วยตัวเอง:

และตอนนี้คือตัวที่น่าสนใจ:

ตอนนี้คือกฎทั่วไป ซึ่งหล่นออกมาจากข้อโต้แย้งเดียวกัน ตัวคูณ $1 - 2\eta$ แท้จริงแล้วคือ $1 - \eta f''$ และใกล้ minimum loss ที่มีหลายพารามิเตอร์มีตัวเลขแบบนี้หนึ่งตัวต่อทิศทาง — eigenvalues ของเมทริกซ์อนุพันธ์อันดับสอง ทุกทิศทางต้อง stable พร้อมกัน ดังนั้นเพดานจึงถูกกำหนดโดยค่าที่ใหญ่ที่สุด:

สำหรับ $f(x) = x^2$, $f'' = 2$, เพดาน 1 ซึ่งคือสิ่งที่เราเพิ่งอนุมาน สำหรับสายพานของเรา เมทริกซ์อนุพันธ์อันดับสองคือ $\frac{2}{n} A^{\top} A$ โดยมี $A$ เป็นเมทริกซ์ input สองคอลัมน์ และ eigenvalues คือ 2 และ 14.89 ดังนั้นเพดานคือ $2 / 14.89 = 0.13432$ นั่นคือการทำนายที่มีห้าเลขนัยสำคัญ ทดสอบมัน:

lr=0.1343    -> L =      24.5924
lr=0.13431   -> L =      24.5924
lr=0.13432   -> L =       4707.8       BLEW UP
lr=0.13433   -> L =  4.00452e+16       BLEW UP
lr=0.1344    -> L = 1.18229e+107       BLEW UP

ตรงกันห้าตำแหน่งทศนิยมระหว่าง linear algebra หนึ่งบรรทัดกับการวน for loop หนึ่งแสนครั้ง

และนี่คือจุดที่บทที่ 1 กลับมา ทุกอย่างข้างต้นใช้ค่าการวัดที่ centered รัน code เดียวกันบนมิลลิเมตรและกรัมดิบ แล้ว eigenvalues คือ 0.0298 และ 998.1 แทนที่จะเป็น 2 และ 14.89 เพดานยุบจาก 0.134 เป็น 0.002004 — แน่นอนพอ ๆ กัน converge ที่ lr=0.002003 และ blow up ที่ lr=0.002004

แย่กว่าเพดานคืออัตราส่วนระหว่าง eigenvalues condition number วัดว่าหุบเขาห่างจากความกลมแค่ไหน: ร่องยาวแคบบังคับให้ rate เล็กพอสำหรับผนังชัน แล้วพื้นร่องก็ต้องถูกเดินด้วยความคลานเดียวกัน ของเราเปลี่ยนจาก 7.44 เมื่อ centered เป็น 33,452 เมื่อ raw ด้วย rate ที่ดีที่สุดที่แต่ละเวอร์ชันรับได้:

ข้อมูลเดียวกัน code เดียวกัน คำตอบสุดท้ายเดียวกัน — และงานมากกว่าแปดพันเท่า เพราะไม่มีใครลบค่าเฉลี่ย ในบทที่ 1 การละเลยแบบเดียวกันทำให้ perceptron เสีย epoch มากขึ้นหกพันเท่า และการวินิจฉัยตอนนั้นเป็นเชิงเรขาคณิต: ข้อมูลลอยไกลจาก origin นี่คือเรขาคณิตเดียวกันในชุด optimization และเป็นเหตุผลว่าทำไม input normalisation ไม่ใช่คำแนะนำเรื่องความเรียบร้อย แต่เป็นเลขคณิต¹

ทั้งหมดข้างต้นไม่ต้องใช้ library นี่คือ optimiser ทั้งหมด

def loss(theta):
    a, b = theta
    return np.mean((a * x + b - y) ** 2)


def grad(theta):
    a, b = theta
    residual = a * x + b - y
    return np.array([np.mean(2 * residual * x), np.mean(2 * residual)])


def descend(theta, lr, steps):
    theta = np.array(theta, dtype=float)
    for _ in range(steps):
        theta = theta - lr * grad(theta)   
    return theta


theta = descend([0.0, 0.0], lr=0.05, steps=60)
print(theta, loss(theta))

[ 2.10040296e+00 -2.76445533e-15] 24.592448791134984

คำตอบ least-squares แบบ closed-form สำหรับแปดจุดนี้คือ $a = 2.100403$, $b = 0$ โดยมี loss $24.592449$ loop พบมันถึงแปดเลขนัยสำคัญโดยไม่รู้ว่ามี closed form อยู่ — ซึ่งสำคัญ เพราะตั้งแต่บทที่ 5 เป็นต้นไปจะไม่มีแบบนั้น

trajectory เพราะประเด็นคือการดูมัน:

   0 a=0.000000 b=0.000000 L=57.437500
   1 a=1.563750 b=0.000000 L=26.736582
   2 a=1.963288 b=-0.000000 L=24.732418
   5 a=2.098116 b=-0.000000 L=24.592488
  10 a=2.100400 b=-0.000000 L=24.592449
  60 a=2.100403 b=-0.000000 L=24.592449

ระยะส่วนใหญ่ถูกครอบคลุมในสองก้าวแรก เพราะ gradient ใหญ่ที่สุดเมื่อคุณอยู่ไกลจากก้นหุบเขาที่สุด และหดลงเมื่อคุณเข้าใกล้ Gradient descent ชะลอตัวลงเองใกล้ minimum นั่นเป็น feature และในบทที่ 6 ก็เป็นปัญหาด้วย

ข้อโต้แย้งจนถึงตอนนี้มีช่องโหว่ ก้าวหยุดเมื่อ $\nabla L = \mathbf{0}$ และเราเรียกสิ่งนั้นว่า “minimum” จุดที่ gradient เป็นศูนย์คือ critical point และการเป็น minimum เป็นเพียงหนึ่งในวิธีที่จะเป็นจุดแบบนั้น:

• local minimum: ขึ้นเขาในทุกทิศทาง แต่อาจไม่ใช่จุดต่ำสุดแบบนั้นในทุกที่;
• local maximum: ลงเขาในทุกทิศทาง;
• saddle point: ขึ้นเขาในบางทิศทางและลงเขาในบางทิศทาง พื้นผิว $f(x,y) = x^2 - y^2$ มี $\nabla f = (2x, -2y)$ ซึ่งเป็นศูนย์ที่ origin ที่ซึ่งฟังก์ชันเป็น minimum ตามแกน $x$ และเป็น maximum ตามแกน $y$ ในเวลาเดียวกัน

Gradient descent แยกสิ่งเหล่านี้ไม่ออก เพราะมันมองแค่ gradient เท่านั้น และ gradient เป็นศูนย์ในทั้งสามแบบ

เส้นตรงของเรามี critical point หนึ่งจุดและมันคือคำตอบ — squared-error loss บนโมเดล linear เป็น convex เป็นชามใบเดียว และ descent บนมันไม่สามารถพลาด global minimum ได้ คุณสมบัตินั้นไม่รอดเมื่อเจอกับคอร์สนี้ loss ของ neural network ไม่ convex และตั้งแต่บทที่ 5 เป็นต้นไป “minimum” ไม่ใช่สิ่งที่มีอยู่: มีหลายจุด ลึกไม่เท่ากัน และคุณได้จุดไหนขึ้นอยู่กับว่าคุณเริ่มตรงไหน นี่เป็นประโยคเดียวและจะอยู่แค่ประโยคเดียว เพราะทฤษฎีใหญ่มากและผลเชิงปฏิบัติน้อย

คุณเห็นผลลัพธ์ทั้งหมดได้บนเส้นโค้งเดียว ใช้ $f(x) = \tfrac{x^4}{4} - \tfrac{x^2}{2} + \tfrac{x}{10}$ ซึ่งมีหุบเขาสองแห่งที่ลึกไม่เท่ากัน:

   x =  -1.046681   f(x) =  -0.352386   minimum
   x =   0.101031   f(x) =   0.005026   maximum
   x =   0.945649   f(x) =  -0.152639   minimum

การตกลงในหุบเขาตื้นทำให้ loss แย่ลง 56.7% และอัลกอริทึมไม่มีทางรู้ เพราะจากภายในหุบเขา ทุกทิศทางคือขึ้นเขา ไม่มีการซ่อมสิ่งนี้ใน gradient descent และจะไม่มีมาให้ สิ่งที่มีในทางปฏิบัติคือข้อค้นพบว่ามันสำคัญน้อยกว่าที่ภาพนี้ชวนให้คิดมาก — ในมิติสูงมากของเครือข่ายจริง critical point ส่วนใหญ่กลายเป็น saddle มากกว่า trap,² และบทที่ 5 จะวัดว่าเครือข่ายเล็ก ๆ ติดจริงบ่อยแค่ไหน

มีสิ่งหนึ่งเกี่ยวกับ grad ข้างต้นที่ควรกวนใจคุณ: มันรวมทั้ง dataset สำหรับทุกก้าว ชิ้นส่วนแปดชิ้นไม่เป็นไร หนึ่งล้านคือการคำนวณ gradient หนึ่งล้านครั้งเพื่อขยับพารามิเตอร์ครั้งเดียว

ทางหนีคือ gradient เป็น ค่าเฉลี่ย และค่าเฉลี่ยประมาณได้จาก sample คำนวณมันบนหยิบมือแบบสุ่ม — minibatch — แล้วก้าวตามนั้น ค่าประมาณมี noise; แต่มันก็ unbiased และก้าว noisy ราคาถูกหลายร้อยก้าวชนะก้าว exact แพง ๆ หนึ่งก้าว บนชิ้นส่วนสังเคราะห์หนึ่งแสนชิ้น นับ per-example gradients แทนจำนวนก้าว:

ใช้เลขคณิตน้อยลงสองร้อยสิบเก้าเท่าเพื่อไปถึงที่เดียวกัน และสุดขั้ว — ทีละตัวอย่าง การประมาณแบบ stochastic ดั้งเดิมของ Robbins และ Monro³ — ไม่ใช่ ผู้ชนะ: มันแย่กว่า batch ขนาด 32 ห้าเท่า เพราะ 32 ตัวอย่างแทบไม่แพงกว่า 1 ตัวอย่างบน hardware ที่คูณเมทริกซ์ ขณะที่ noise ลดลงตามรากที่สองของ batch size trade-off นี้คือเหตุผลที่ training script ทุกตัวที่คุณจะได้อ่านมี batch_size อยู่ในนั้น

Momentum คือวิธีแก้ราคาถูกอีกอย่าง และมันเล็งตรงไปที่ร่อง ในหุบเขาที่ condition แย่ ก้าวจะ zig-zag ข้ามทิศทางแคบ ขณะคืบคลานไปตามทิศทางยาว Momentum เก็บ running average ของ gradients ที่ผ่านมา ดังนั้นองค์ประกอบที่แกว่งจะหักล้างกัน และองค์ประกอบที่สม่ำเสมอจะสะสม:⁴

เพิ่มสองบรรทัด บนสายพาน raw ที่ไม่ centered — condition number 33,452 กรณีเลวร้ายที่สุดที่เรามี — ที่ rate ที่ดีที่สุดที่ plain descent รับได้:

momentum beta=0.0   ->    79,513 steps to 1%
momentum beta=0.9   ->     1,609 steps to 1%
momentum beta=0.99  ->       461 steps to 1%

ดีขึ้น 172 เท่าจาก code สองบรรทัด บทที่ 6 จะเปลี่ยนสิ่งนี้เป็น Adam; กลไกอยู่ตรงนี้แล้ว

ทุก gradient ในบทนี้ถูกอนุมานด้วยมือ และจึงอาจผิดได้ วิธีแก้คือใช้ตารางความชันจากตอนต้น: วัดอนุพันธ์เชิงตัวเลขแล้วเปรียบเทียบ ใช้ central difference, $\frac{L(\theta+h) - L(\theta-h)}{2h}$ ซึ่งหักล้าง error term นำหน้า และแม่นยำกว่ามากสำหรับ $h$ เดียวกัน

def numeric_grad(f, theta, h=1e-5):
    theta = np.asarray(theta, dtype=float)
    out = np.zeros_like(theta)
    for i in range(theta.size):
        bump = np.zeros_like(theta)
        bump[i] = h
        out[i] = (f(theta + bump) - f(theta - bump)) / (2 * h)     
    return out


def gradcheck(f, df, theta, h=1e-5):
    analytic = np.asarray(df(theta), dtype=float)
    numeric = numeric_grad(f, theta, h)
    return np.max(np.abs(analytic - numeric) / np.maximum(1e-8, np.abs(analytic) + np.abs(numeric)))

รูปแบบ relative ของการเปรียบเทียบสำคัญ: absolute difference ขนาด $10^{-4}$ คือหายนะบน gradient ขนาด $10^{-3}$ และไม่สำคัญบน gradient ขนาด $10^{6}$

relative error: 1.8929136036763527e-11
with 2 dropped: 0.33333333331650744

บรรทัดแรกคือ gradient ที่อนุมานด้วยมือข้างต้น บรรทัดที่สองคือฟังก์ชันเดียวกันแต่ลืม factor 2 ใน component หนึ่ง — typo ตัวอักษรเดียว — และการตรวจจับก็จับได้ทันที อะไรที่ต่ำกว่าประมาณ $10^{-7}$ คือเห็นพ้องกัน; อะไรที่สูงกว่า $10^{-4}$ คือ bug เก็บฟังก์ชันนี้ไว้: บทที่ 5 ใช้มัน debug automatic differentiation engine และมันคือเหตุผลเดียวที่ gradient ผิด ๆ จะถูกหาเจอได้

ทุกอย่างในบทนี้ตั้งอยู่บนสมมติฐานหนึ่งที่ไม่เคยพูดออกมา: ว่าคุณสามารถเขียน $\partial L / \partial \theta$ ลงมาได้

สำหรับเส้นตรงที่มีสองพารามิเตอร์ นั่นคือพีชคณิตหนึ่งบรรทัด แต่มันหยุดเป็นแบบนั้นแทบจะทันที ลองถาม symbolic algebra system หาอนุพันธ์ของ loss ของเครือข่ายเทียบกับ weight ชั้นแรก หนึ่งตัว สำหรับตัวอย่าง หนึ่งตัว แล้วนับเลขคณิตในคำตอบ:

แถวที่สามคือเครือข่ายที่มี 57 พารามิเตอร์ — เครือข่ายเล็กจนในบทที่ 6 จะเป็นได้แค่เชิงอรรถ — และการเขียน gradient ของมันออกมาด้วยมือหมายถึงประมาณ 97,869 operations สำหรับ training example หนึ่งตัว ไม่มี notation ไหนช่วยชีวิตสิ่งนี้ได้ สิ่งที่ช่วยได้คือข้อสังเกตว่า chain rule เมื่อนำไปใช้กับ composition มีโครงสร้างมหาศาล ว่าปริมาณ intermediate เดิม ๆ ปรากฏซ้ำแล้วซ้ำเล่า และการคำนวณมันตามลำดับที่ถูกต้องจะให้อนุพันธ์ ทั้งหมด ในราคาประมาณเท่ากับ forward pass หนึ่งครั้ง นั่นคือบทที่ 5

แต่มีปัญหาเล็กกว่านั้นก่อน และมันรออยู่ทันที

ตอนนี้เรามีเครื่องจักรที่จะกลิ้งลงเขาบน loss ที่ differentiable ใด ๆ ชี้มันไปที่คำถามดั้งเดิมของสายพาน — รับหรือปฏิเสธ target ที่เป็น 1 หรือ 0 — ใส่ sigmoid บน output เพื่อให้ทำนายความน่าจะเป็น แล้ว minimize squared error มันจะรันได้ แต่มันแทบไม่ขยับเมื่อมันผิดที่สุด และ gradient บอกว่าทำไม:

โมเดลที่ผิดอย่าง มั่นใจและเลวร้ายสุดขีด — ทำนาย 0.0000454 ทั้งที่คำตอบคือ 1 — สร้าง gradient ของ squared-error เท่ากับ $9 \times 10^{-5}$ มันไม่รู้เลยว่าตัวเองกำลังมีปัญหา อีกคอลัมน์หนึ่ง จาก loss ที่เรายังไม่ได้อนุมาน รายงาน 1.0: ความเร่งด่วนสูงสุด ตรงที่มันสมควรเกิดพอดี

ซึ่งนำไปสู่คำถามที่บทถัดไปจะเปิดด้วย บทก่อนหน้าบอกว่า loss คือสมมติฐานเกี่ยวกับ noise และ squared error สมมติ Gaussian noise แล้วคำตอบแบบใช่หรือไม่ใช่มี noise model แบบไหน — และ loss แบบใดออกมาเมื่อคุณทำการอนุมานเดียวกันกับมัน?

วิธีนี้เก่ากว่าทั้งหมด: Cauchy อธิบายมันในบันทึกถึง Académie des Sciences ในปี 1847 ในฐานะวิธีแก้ระบบสมการด้วยการเดินลงเขาบนผลรวมของ squared residuals ของมัน สิ่งที่ควรอ่านคู่กับบทนี้ด้วย: An overview of gradient descent optimization algorithms ของ Sebastian Ruder (arXiv:1609.04747) ซึ่งครอบคลุม momentum ถึง Adam ในสิบสี่หน้าที่อ่านง่าย; บทที่ 3 ของ Numerical Optimization ของ Nocedal และ Wright (2nd ed., Springer, 2006) ซึ่ง theorem 3.3 ให้ convergence rate ของ steepest descent บน quadratic ในรูป condition number — มันคือทฤษฎีเบื้องหลังว่าทำไม conditioning จึงตัดสินจำนวนก้าว แม้มันจะพิจารณา line search แทนเพดาน fixed-step $2/\lambda_{\max}$ ที่วัดไว้ข้างต้น หรือ §5.8 และ §7.1 ของ Mathematics for Machine Learning โดย Deisenroth, Faisal และ Ong สำหรับพื้นที่เดียวกันแต่ใช้เครื่องมือน้อยกว่า; §6.1 ของ Understanding Deep Learning โดย Prince และ §4.3 ของ Deep Learning โดย Goodfellow, Bengio และ Courville; Dive into Deep Learning §12.1–12.3 ซึ่งมีการวิเคราะห์ minibatch พร้อมการวัดมากกว่าที่มีที่ว่างให้ใส่ที่นี่; และบทที่ 4 ของ Hands-On Machine Learning ของ Géron (3rd ed.) ซึ่งเป็นการอธิบาย learning rate ในฐานะสิ่งที่คุณ tune มากกว่าจะ derive ได้เชิงปฏิบัติที่สุด โน้ต MIT 6.390 วาง gradient descent ไว้ก่อน classification เหมือนคอร์สนี้ และด้วยเหตุผลเดียวกัน