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

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

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

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

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

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

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

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

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

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

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

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

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

 1  def gradient(x, n_iter, alpha):
 2  	J = []
 3  	def compute_cost(x):
 4  	    """
 5  	    ฟังก์ชันที่เราต้องการทำให้มีค่าต่ำที่สุด
 6  	    """
 7  		J = x ** 2 - 4 * x
 8  		return J
 9  		
10  	def compute_grad(x):
11  	    """
12  	    ฟังก์ชันคำนวณหาความชันเมื่อได้รับค่า x
13  	    """
14  		grad = 2 * x - 4
15  		return grad
16  	
17  	# n_iter เป็นจำนวนครั้งที่เราอัพเดทค่า x จนไปถึงจุดต่ำที่สุด
18  	for i in range(n_iter):
19  		x = x - alpha * compute_grad(x)
20  		J.append(compute_cost(x))		
21  	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 ที่ทำให้ฟังก์ชันมีค่าต่ำที่สุด

อ้างอิง[แก้]

[1]

  1. 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