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

การเคลื่อนลงตามความชัน (gradient descent) เป็นขั้นตอนวิธีที่ใช้หาค่าที่เหมาะสมที่สุดให้กับฟังก์ชั่นที่กำหนดขึ้นมา โดยขั้นตอนวิธีนี้ใช้การวนหาค่าที่ทำให้ค่าต่ำสุดจากการคำนวณจากความชันที่จุดที่เราอยู่แล้วพยายามเดินทางไปทางตรงข้ามกับความชันที่คำนวณขึ้นมา 
 ขั้นตอนการทำงาน 
กำหนดฟังก์ชันที่ต้องการหาค่า ยกตัวอย่างเช่น ฟังก์ชันแคลคูลัส  ซึ่งมีค่าความชัน (gradient) เท่ากับ 
เราสามารถเริ่มที่จุดใด ๆ ก็ได้บนพาราโบลา เช่นถ้าเราสุ่มค่าเริ่มต้นออกมาที่  เราจะหาจุดต่ำสุดโดยดูจุดที่เราอยู่แล้วเลื่อนไปทางตรงข้าม ทำแบบเดียวกันหลายครั้ง x ก็จะลู่เข้าสู่จุดต่ำลงเรื่อย ๆ และสิ้นสุดเมื่อถึงค่า ที่ slope มีค่าเท่าศูนย์
ให้  (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 ที่ทำให้ฟังก์ชันมีค่าต่ำที่สุด

 อ้างอิง 
https://tupleblog.github.io/gradient-descent-part1/
https://lukkiddd.com/%E0%B9%80%E0%B8%94%E0%B8%B4%E0%B8%99%E0%B8%A5%E0%B8%87%E0%B9%80%E0%B8%82%E0%B8%B2%E0%B8%94%E0%B9%89%E0%B8%A7%E0%B8%A2-gradient-descent-algorithm-7db99092b981

หมวดหมู่:วิธีการหาค่าเหมาะที่สุด
หมวดหมู่:วิธีความชัน