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

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

ขั้นตอนการทำงาน 
1.กำหนดฟังก์ชันที่ต้องการหาค่า ยกตัวอย่างเช่น ฟังก์ชันแคลคูลัส  ซึ่งมีค่าความชัน (gradient) เท่ากับ 

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

3.ให้  (n_iter) คือ จำนวนครั้งที่เราวนหาค่า  อัลกอริทึมที่หาจุดต่ำสุดของ  สามารถเขียนได้ดังนี้ 

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

ความซับซ้อนในการทำงาน 
ความซับซ้อนของอัลกอริทึมการเคลื่อนลงตามความชันมีค่าเท่ากับ Big(O ) = O(n) 
 Best case คือ จำนวนการวนรอบที่น้อยที่สุด
 Worst case คือ จำนวนวนรอบที่มากที่สุด

ตัวอย่างการเขียนโปรแกรม 
จากตัวอย่างข้างต้น เราสามารถเขียนโปรแกรมภาษา Python เพื่อหาค่า  ที่ทำให้   มีค่าต่ำที่สุดโดยใช้อัลกอริทึมการเคลื่อนลงตามความชันได้ดังนี้ 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 เพื่อคำนวณหาค่า  ที่ทำให้  มีค่าต่ำที่สุดได้เช่นกัน โดย 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 ที่ทำให้ฟังก์ชันมีค่าต่ำที่สุด

อ้างอิง 

วิธีการหาค่าเหมาะสมที่สุด