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

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

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

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

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

3.ให้ $k$ (n_iter) คือ จำนวนครั้งที่เราวนหาค่า $x$ ขั้นตอนวิธีที่หาจุดต่ำสุดของ $f(x)=x^{2}-4x$ สามารถเขียนได้ดังนี้ $x_{k+1}=x_{k}-\alpha f^{'}(x_{k})$

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

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

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

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

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

จากตัวอย่างข้างต้น เราสามารถเขียนโปรแกรมภาษา Python เพื่อหาค่า $x$ ที่ทำให้ $f(x)=x^{2}-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)=x^{2}-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 ที่ทำให้ฟังก์ชันมีค่าต่ำที่สุด