การเคลื่อนลงตามความชัน คืออะไร

การเคลื่อนลงตามความชัน (Gradient Descent Algorithm) เป็นอัลกอริทึมที่ใช้หาค่าที่เหมาะสมที่สุดให้กับฟังก์ชั่นที่กำหนดขึ้นมา โดยอัลกอริทึมใช้การวนหาค่าที่ทำให้ค่าต่ำสุดจากการคำนวณจากความชันที่จุดที่เราอยู่แล้วพยายามเดินทางไปทางตรงข้ามกับความชันที่คำนวณขึ้นมา

ขั้นตอนการทำงาน

1.กำหนดฟังก์ชันที่ต้องการหาค่า ยกตัวอย่างเช่น ฟังก์ชันแคลคูลัส f(x) = x2 − 4x ซึ่งมีค่าความชัน (gradient) เท่ากับ f′(x) = 2x − 4

2.เราสามารถเริ่มที่จุดใดๆก็ได้บนพาราโบลา เช่นถ้าเราสุ่มค่าเริ่มต้นออกมาที่ x = 10 เราจะหาจุดต่ำสุดโดยดูจุดที่เราอยู่แล้วเลื่อนไปทางตรงข้าม ทำแบบเดียวกันหลายครั้ง x ก็จะลู่เข้าสู่จุดต่ำลงเรื่อยๆ และสิ้นสุดเมื่อถึงค่า xที่ slope มีค่าเท่าศูนย์

3.ให้ k (n_iter) คือ จำนวนครั้งที่เราวนหาค่า x อัลกอริทึมที่หาจุดต่ำสุดของ f(x) = x2 − 4x สามารถเขียนได้ดังนี้ xk + 1 = xk − α**f′(xk)

โดยค่า 𝛼 คือค่าการลู่เข้า ยิ่งมีค่ามากจะยิ่งลู่เข้าเร็ว แต่ถ้ามากเกินไป การอัพเดทครั้งถัดไปจะทำให้ค่า x มีค่ามากเกินไปจนลู่ออกไปถึงอนันต์ก็ได้

ความซับซ้อนในการทำงาน

ความซับซ้อนของอัลกอริทึมการเคลื่อนลงตามความชันมีค่าเท่ากับ Big(O ) = O(n)

Best case คือ จำนวนการวนรอบที่น้อยที่สุด
Worst case คือ จำนวนวนรอบที่มากที่สุด

ตัวอย่างการเขียนโปรแกรม

จากตัวอย่างข้างต้น เราสามารถเขียนโปรแกรมภาษา Python เพื่อหาค่า x ที่ทำให้ f(x) = x2 − 4x มีค่าต่ำที่สุดโดยใช้อัลกอริทึมการเคลื่อนลงตามความชันได้ดังนี้

 def gradient(x, n_iter, alpha):
    J = []
    def compute_cost(x):
        """
        ฟังก์ชันที่เราต้องการทำให้มีค่าต่ำที่สุด
        """
        J = x ** 2 - 4 * x
        return J
        
    def compute_grad(x):
        """
        ฟังก์ชันคำนวณหาความชันเมื่อได้รับค่า x
        """
        grad = 2 * x - 4
        return grad
    
    # n_iter เป็นจำนวนครั้งที่เราอัพเดทค่า x จนไปถึงจุดต่ำที่สุด
    for i in range(n_iter):
        x = x - alpha * compute_grad(x)
        J.append(compute_cost(x))       
    return x, J[-1]

นอกจากจะใช้วิธีการทั่วไปแล้ว เรายังสามารถใช้ไลบรารี่ Pytorch (เวอร์ชัน 0.4.1) ร่วมกับ autograd เพื่อคำนวณหาค่า x ที่ทำให้ f(x) = x2 − 4x มีค่าต่ำที่สุดได้เช่นกัน โดย autograd สามารถประมาณความชันได้โดยที่เราไม่ต้องคำนวณหาความชันของฟังก์ชันด้วยตัวเอง

import torch

x = 10 * torch.ones(1)
x.requires_grad_(True) # ตั้งค่าให้ x สามารถคำนวณหา gradient ได้
out = torch.sum(x * x - 4 * x) # cost function
print(x) # สมมติค่าเริ่มต้นที่ x = 10

# gradient descent
alpha = 0.02
for _ in range(1000):
    out.backward(retain_graph=True) # calculate gradient using
    x.data.sub_(alpha * x.grad.data) # x = x - alpha * f'(x)
    x.grad.data.zero_() # setting gradient back to zero again
print(x) # สุดท้ายแล้วจะได้ค่า x = 2 ที่ทำให้ฟังก์ชันมีค่าต่ำที่สุด