Reinforcement Learning
Reinforcement Learning (RL) หรือ การเรียนแบบเสริมกำลัง นั้นแต่ก่อนนี้เป็นหัวข้อท้ายๆ ที่ผมสอนในคลาส machine learning ถือซะว่าเป็นของแถม เพราะ application ของมันมักเป็นงานด้าน robot navigation หรือ การเล่นเกม ซึ่งไม่ใช่ application หลักดังนั้นคนก็ไม่ค่อยสนใจเท่าไร แต่มาช่วงนี้เห็นคนพูดถึงมากขึ้นเรื่อยๆ จนเข้าไปอยู่ใน hype cycle ของ Gartner ปีนี้เลย
ส่วนหนึ่งก็มาจาก DeepMind ที่นอกจาก AlphaGO แล้วก็ยังพัฒนางานด้านนี้ต่อเนื่อง นอกจากนี้ยังมีกลุ่ม OpenAI ที่ปล่อย OpenAI Gym ที่ช่วยให้เราสามารถลองพัฒนา reinforcement learning algorithm สำหรับงานเกมคลาสสิกอย่าง Pacman ได้ง่ายๆ ด้วย
ในบล็อกนี้ผมจะเล่าเรื่องเทคนิคพื้นฐานบางส่วนของ reinforcement learning ก่อนไว้วันหลังถ้าขยันค่อยดู OpenAI Gym
ตัวอย่างของงานที่ใช้ RL
งานแรกคงหนีไม่พ้น AlphaGO ซึ่งกระบวนการสอนของมันนั้นแบ่งเป็น 2 ส่วน ส่วนแรกทำการสอนแบบมีผู้สอน หรือ Supervised Learning (SL) โดยใช้ข้อมูล log ของการเล่นโกะระหว่างคนเล่น จากนั้นจึงใช้การเรียนแบบ RL โดยให้มันเล่นแข่งกับตัวเอง
อีกงานหนึ่งเร็วๆ นี้คือ Chatbot ของ Facebook ซึ่งกระบวนการสอนก็แบ่งเป็นสองส่วนเช่นกัน คือเริ่มจาก SL โดยใช้ข้อมูล log ที่ได้จากบทสนทนาของคน จากนั้นจึงใช้ RL ให้มันหัดต่อรองแข่งกับตัวเอง
บางคนอ่านตัวอย่างทั้งสองนี้แล้วอาจเข้าใจว่าประเด็นหลักของ RL คือการแข่งกับตัวเอง ซึ่งไม่ใช่ ประเด็นหลักจริงๆ คือการเรียนแบบมีผู้สอนนั้นทำให้ AI นั้นเรียนรู้ที่จะเลียนแบบพฤติกรรมของมนุษย์ เราสามารถเทียบได้กับการตอบสนองต่อสิ่งเร้า (reflex) โดยไม่ได้มีจุดหมายใดๆ เวลาคนบอกว่า AlphaGO นั้นมี intuition ก็ถือว่าจริงอยู่
การเรียนแบบเสริมกำลังนั้นทำให้ AI เรียนรู้เพิ่มว่า reflex แบบใดจะนำไปสู่เป้าหมายของเกมหรือการต่อรองได้ดีกว่า
โดยปกติแล้วการที่เป้าหมายนี้จะสำเร็จได้นั้นระบบต้องทำ การตัดสินใจต่อเนื่อง (sequential decision problem) ถ้าเป็นแต่ก่อนผมมองว่าอีกประเด็นสำคัญของ RL คือในการตัดสินใจแต่ละครั้งเราอาจไม่มี desired output สำหรับสอนก็ได้ แต่ตอนนี้ผมเปลี่ยนใจแล้ว เพราะต่อให้มี desired output ทุก step ถ้าเราสอนแค่นั้น AI ก็จะแค่เลียนแบบพฤติกรรมของเรา ซึ่งนับได้ว่าเป็นเพียงเป้าหมายรองเท่านั้น
RL นั้นใช้เพื่อให้ AI มันเรียนรู้ที่จะปรับตัวเองเพื่อให้บรรลุเป้าหมายหลัก
พื้นฐาน
ใน RL นั้นเราพิจารณา autonomous agent ที่สามารถเลือก action ได้โดยอาจเลือกแบบสุ่มก็ได้ หรือเลือกจากข้อมูลสภาพแวดล้อมของมันที่เรามักเรียกว่า state
เมื่อ agent นี้ทำ action ดังกล่าวแล้ว state ของสภาพแวดล้อมก็จะเปลี่ยนไป
เช่นให้ state เป็นตำแหน่งของ agent ในเขาวงกตและ action ก็คือการเลือกเดิน บน/ล่าง/ซ้าย/ขวา เป็นต้น
agent จะทำ action ไปเรื่อยๆ จนกว่าจะไปอยู่ใน state จบ เช่นออกจากเขาวงกต หรือเล่นเกมจบเป็นต้น ไม่ว่าจะชนะหรือแพ้ก็ตาม ในบางกรณีอย่าง agent ของเราเป็นหุ่นยนต์ดูดฝุ่น ก็อาจไม่มี state จบก็ได้ในกรณีนี้ agent ก็เดินไปเรื่อยๆ ไม่สิ้นสุด
กรณีง่ายสุดคือ state และ action นั้นมีจำนวนจำกัด ให้ a เป็น action และ s กับ s’ เป็น state 2 state ใดๆ เราพิจารณาค่าความน่าจะเป็น P(s’|s,a) นั่นคือความน่าจะเป็นที่ ถ้าเราทำ action a ใน state s แล้วจะไปจบที่ state s’
อันนี้อาจจะดูแปลกแต่ในความเป็นจริงแล้วมันมี factor ที่อยู่นอกเหนือจากการ model ของเราอยู่ ดังนั้นจึงเป็นไปได้ว่าการเลือก action อาจไม่ได้ผลที่ต้องการ เช่นสมมติว่าเราเปลี่ยนจากเขาวงกตเป็นเส้นทางในทะเล และ agent เราคือเรือใบ ตำแหน่งใหม่จากการเลือก action บน/ล่าง/ซ้าย/ขวา นั้นขึ้นกับสภาพลมในทะเลหรือกระแสน้ำอีกด้วย ดังนั้นถ้าเราเลือกเดินเรือไปทางซ้ายเราอาจไปจบที่ตำแหน่งซ้ายล่างก็ได้ เป็นต้น หรือในกรณีที่ agent เราเป็นหุ่นยนต์ที่การสั่งการการเคลื่อนที่นั้นทำผ่านการหมุนของล้อ การคำนวณระยะทางและมุมผ่านระบบ Odometry ก็อาจคลาดเคลื่อนได้ ดังนั้นตำแหน่งจบก็อาจไม่เป็นไปตามที่เราวางแผนไว้เป็นต้น
ให้ 𝜋(s) เป็น policy หรือแผน (แปลว่านโยบายดูแปร่งๆ ไป) ที่กำหนดว่าเมื่อเราอยู่ใน state s เราควรเลือก action ใด
ให้ R(s) เป็นคะแนน หรือ reward ที่ได้เมื่อ agent มาถึงตำแหน่ง s ซึ่งอาจเป็น 0 ก็ได้
จุดประสงค์ของ RL คือการสอน agent ให้เรียนรู้แผนที่เหมาะสม เพื่อให้ได้รับคะแนนรวมสูงสุดในการเดินสำรวจ state ทั้งหลาย
ในกรณีที่ปัญหาของเราไม่มี state สิ้นสุด agent ก็สามารถเดินไปได้เรื่อยๆ ซึ่งจะทำให้ผลรวมของคะแนนนั้นเป็นอนันต์ได้ เพื่อแก้ปัญหานี้เราพิจารณา discounting factor 𝛾 ที่มีค่าระหว่าง 0 ถึง 1 และคะแนนของการสำรวจที่เราสนใจก็ได้จากผลรวมคะแนนที่ใช้ 𝛾 เป็นค่าถ่วงน้ำหนัก
นั่นคือสมมติว่า agent เดินผ่าน state s1, s2, s3, … คะแนนที่เขาจะได้ก็คือ
เราเรียกค่านี้ว่า discounted reward แต่ขอเรียกสั้นๆ ว่าคะแนนรวมเหมือนเดิมละกัน
Value Iteration
เทคนิคมาตรฐานอันแรกคือการพิจารณา ประโยชน์ (utility) ของ state ต่างๆ ประโยชน์ของ state s หรือ V(s) คือผลรวมของคะแนนที่จะเกิดขึ้นถ้าเราเดินจาก s ต่อไปอนาคต
หากเรารู้ค่าประโยชน์ของ state ต่างๆ แล้ว เราก็สามารถเลือก action ได้โดยง่าย นั่นคือเราเลือก action ที่นำไปสู่ผลรวมของประโยชน์ในอนาคตสูงสุด (ผลรวมเพราะว่า action หนึ่งๆ อาจนำไปสู่ state ที่ต่างกันได้ ขึ้นกับความน่าจะเป็นในการเปลี่ยน state)
คำถามคือเราจะคำนวณ V ยังไงดี ในเมื่อมันขึ้นกับคะแนนรวมที่เราจะได้ในอนาคต?
คำตอบคือ ในเมื่อเรามี action จำกัด ดังนั้นคะแนนรวมสูงสุดในอนาคตก็ต้องมาจาก action หนึ่งในนี้นั่นเอง โดย action เหล่านี้ก็นำไปสู่ state ของระบบที่มีค่าประโยชน์กำกับอยู่ ดังนั้นเราสามารถจัดรูปการคำนวณใหม่ให้อยู่ในแบบเรียกตัวเองซ้ำ (recursive) ได้ วิธีคิดแบบนี้เรียกว่า dynamic programming แบบเดียวกับที่ใช้ในการคำนวณ edit distance หรือใน Viterbi algorithm
แนวความคิดข้างบนนี้แปลว่าเราสามารถคำนวณผลรวมของคะแนนที่ได้จากการเลือก action a ใน state s ได้จาก
ดังนั้นประโยชน์หรือคะแนนรวมของ state s นี้คำนวณจาก คะแนนปัจจุบัน R(s) บวกกับคะแนนสูงสุดที่ได้จาก action ที่เป็นไปได้ นั่นคือ
สมการข้างบนคือสิ่งที่เราอยากได้ จากสมการนี้เราก็สามารถสร้างอัลกอริทึมในการคำนวณ V(s) ได้ง่ายๆ คือ
เราเรียกเจ้าอัลกอริทึมนี้ว่า Value Iteration นั่นเอง
จากค่าประโยชน์ V(s) เราสามารถคำนวณแผนที่เหมาะสมได้นั่นคือ
ในกรณีง่ายๆ นี้ ตัวแปรของ agent ก็ประกอบด้วยตารางเก็บค่าประโยชน์เท่านั้นเอง
Q-learning
Value Iteration นั้นต้องการค่าความน่าจะเป็นในการเปลี่ยน state ถ้าในกรณีจริงอย่างเรือใบในทะเลที่ขึ้นกับสภาพลมและกระแสน้ำ ค่าความน่าจะเป็นนี้ก็อาจไม่มีให้เรา คำถามคือแล้วเราจะสอน agent อย่างไร?
คำตอบแรกคือ ลองเลือก action มั่วๆ ไปก่อนแล้วดูว่าเราไปจบที่ state ไหน แล้วนับจำนวนครั้งเพื่อประมาณค่าความน่าจะเป็นนี้ จากนั้นจึงใช้ value iteration ในการวางแผน แต่วิธีนี้ไม่สะดวกและหากสภาพแวดล้อมนั้นเปลี่ยนไป เราก็ต้องกลับมาประมาณค่าความน่าจะเป็นในการเปลี่ยน state นี้ใหม่
คำตอบที่ 2 คือ แทนที่เราจะพิจารณาแค่ประโยชน์ของ state ให้พิจารณาประโยชน์ของคู่ (state, action) แทน เราใช้ตัวแปร Q(s,a) เพื่อเก็บค่านี้
สมมติว่าเราเลือก action a ใน state s แล้วเราไปจบที่ state s’ ก็ให้ update ตาราง Q(s,a) โดย
อัลกอริทึม Q-learning นั้นทำงานโดยการสุ่มเลือก action a จาก state s จากนั้นก็ดูว่า state s’ ใหม่ของเราคืออะไร และทำการ update Q(s,a) และเริ่มสุ่ม action ใหม่คราวนี้จาก s’ ต่อไปเรื่อยๆ
เราสามารถนำการเรียนแบบ SL มาใช้กับ Q-learning ได้โดยสมมติว่าเรามีข้อมูล log เช่นของการเล่นโกะ เราก็จะรู้ว่าคนที่เล่นจริงๆ แล้วใน state s เขาเลือก action a อะไร และ state s’ ใหม่คืออะไร โดยไม่ต้องสุ่มเอง แต่การ update ตาราง Q(s,a) ก็ยังทำโดยสมการข้างบนนี้เช่นกัน
Deep Q-Networks
โดยปกติแล้วหากเราต้องการ implement Q(s,a) โดยใช้ตารางง่ายๆ เราต้องหาวิธีแปลงคู่ (state, action) นี้ให้อยู่ในรูปจำนวนเต็มเพื่อเป็น index ของตารางที่จะจัดเก็บ ถ้า state มี n ค่า และ action มี m ค่า การแปลงนี้ทำได้ง่ายมาก แต่ในกรณีที่ (state, action) นั้นมีปริมาณมาก หรือมีความซับซ้อนมาก การแปลงที่เหมาะสมอาจทำได้ไม่ง่ายนัก
หนึ่งในวิธีแก้ปัญหานี้คือการ implement ฟังก์ชัน Q(s,a) นี้โดยใช้ Neural Network (NN)
แนวความคิดหลักคือสมการ update ของ Q-learning นั้นแปลได้ว่าเมื่อการเรียนนั้นลู่เข้า (converge) แล้ว เราจะได้สมการต่อไปนี้
ให้เรามองฝั่งขวามือเป็นค่า desired output t(s,a) ที่เราต้องการสำหรับ input (s,a) และ train NN ให้หาวิธีแปลงค่า (s,a) ไปเป็น t(s,a)
การ implement NN แบบตรงไปตรงมาสำหรับงานนี้นั้นทำได้โดยสร้าง NN สำหรับแต่ละ action แยกกัน จากนั้นสำหรับ input (s,a) ก็ให้เลือก NN สำหรับ action a มาใช้แปลง s ไปเป็น t(s,a) เป็นต้น
อีกวิธีที่ใช้ในระบบของ DeepMind ที่เรียกว่า Deep Q-Network (DQN) คือสร้าง NN ที่ output node ตรงกับ action ต่างๆ จากนั้นสำหรับ input (s,a) ก็กำหนดให้ desired output ของ node a เป็น t(s,a) และของ node อื่นเป็น 0 (อันนี้เดาเอาอ่านข้ามๆ ไม่เจอใน paper)
ข้อดีของโครงสร้างนี้คือรองรับ action จำนวนมากๆ ได้ดีกว่าวิธีแรก นอกจากนี้การ share โครงสร้างสำหรับ action ต่างกัน น่าจะทำให้ NN สกัด representation ของข้อมูลที่ดีกว่าได้
DQN นี้ถูกเอาไปใช้ในการเล่นเกมของ Atari แบบอัตโนมัติ โครงสร้างที่ใช้ก็ประกอบด้วยชั้น Convolution, ReLU และ dense layer ตามปกติ ที่น่าสนใจคือ “state”
ในกรณีนี้ผู้พัฒนาเลือกที่จะใช้รูปจากหน้าจอเป็นข้อมูลนำเข้าของ NN เลย เราอาจจะมองรูปนี้เป็น “state” เองเลยก็ได้ หรือเราอาจมองว่า NN ที่ใช้นี้มีบางชั้นที่ทำหน้าที่สกัด “state representation” จากรูปนำเข้าก็ได้ ซึ่งทำให้เราทำงานได้ง่ายขึ้นเพราะไม่ต้องหาวิธี encode state เองจากรูปหน้าจอ
ส่งท้าย
บทความนี้ข้ามไปหลายหัวข้ออยู่ เช่น Policy Iteration, SARSA algorithm, TD-learning, … แต่ผู้อ่านคงพอเห็นภาพรวมของ Reinforcement Learning และความสัมพันธ์กับ Deep Learning ได้
วันนี้พอแค่นี้ก่อน ไว้มาต่อคราวหน้า
