AlphaGO

ช่วงนี้เรื่องที่ hot ที่สุดสำหรับคนทำ AI และ machine learning คงไม่พ้น AlphaGO เมื่อวานมีน้องส่งบทความของ AlphaGO ใน Nature มาให้อ่านเลยมาสรุปไว้หน่อย

อย่างแรกที่น่าสนใจคือการ represent state ของเกม

ในงาน AI มาตรฐาน (ตามหนังสือ) เรามักจะมองเกมต่างๆ ในกรอบการทำงานของ Markov decision process ที่ประกอบด้วยเซตของ state ของเกม, action ที่เราสามารถเลือกได้ในแต่ละ state และ “รางวัล” (reward) ที่อาจจะได้ในแต่ละ state หรือได้แค่ใน state จบเกม
ในกรณีที่จำนวน state ไม่มากนักและเรามีข้อมูลมากพอ เราสามารถคำนวณ “ค่า” (value) ของแต่ละ state ได้จากอัลกอริธึมมาตรฐานชื่อ value iteration และเก็บใส่ตารางไว้ จากนั้นเราสามารถกำหนด “นโยบาย” (policy) ในการเลือก action สำหรับแต่ละ state ได้ หรือเราสามารถปรับ policy นี้ได้โดยตรงจากอัลกอริธึมมาตรฐานอีกอันที่ชื่อ policy iteration

เกมโกะเล่นกันบนกระดาน 19x19 เส้น โดยแต่ละตำแหน่งบนตารางนี้เป็นได้ 3 แบบคือ ว่าง/ดำ/ขาว ดังนั้นถ้านับคร่าวๆ จำนวน state ของเกมทั้งหมดที่เป็นไปได้ก็คงเป็น 3 ยกกำลัง 361 (=19x19) ซึ่งเยอะมาก
แต่แทนที่ AlphaGO จะพยายาม encode ตำแหน่งการเล่นต่างๆ เพื่อเป็นดัชนีในการจัดเก็บค่า value และ policy ทีมที่พัฒนาเลือกที่จะส่งรูปของกระดานขนาด 19x19 เข้าไปประมวลผลโดยตรง โดยแบบจำลองที่ใช้ในการประมวลผลคือ “โครงข่ายประสาทเทียมแบบสังวัตนาการ” (convolutional neural network หรือ cnn) ที่นับเป็นโครงข่ายในกลุ่ม deep learning แบบหนึ่ง

Policy network

cnn อันแรกชื่อ policy network รับ input ที่เป็นตารางขนาด 19x19 และส่งออกตารางขนาด 19x19 ที่มีค่าความน่าจะเป็นในการเดินหมาก ณ ตำแหน่งต่างๆ network นี้ถูกสอนจากข้อมูลการเดินใน KGS GO serverให้ทำนายตาเดินถัดไปของผู้เล่น
โครงสร้างนี้ประกอบด้วยชั้น convolution จำนวน 13 ชั้น
ชั้นแรกจะเติมขอบ (padding) ให้ข้อมูลเป็นขนาด 23x23 และประมวลผลด้วย convolution kernel ขนาด 5x5 ซึ่งผลลัพธ์ที่ได้ก็คือตารางขนาด 19x19 นั่นเอง
ชั้นที่เหลือจะเติมขอบให้เป็นขนาด 21x21 และประมวลผลด้วย convolution kernel ขนาด 3x3 และส่งออกตารางขนาด 19x19 เช่นกัน
บทความบอกว่า AlphaGO version ที่แข่งนั้นใช้ kernel จำนวน 192 kernel ในแต่ละชั้น
โครงสร้างนี้เล็กกว่าพวกที่ใช้ในงาน image อย่าง GooLeNet หรือ residual network ของ Microsoft ที่เข้าร่วมงานแข่ง ImageNet ปลายปีก่อน
การสอนในขั้นตอนนี้น่าจะใช้การปรับ weight ตาม gradient ปกติของ neural network

โครงสร้างนี้สามารถทำนายตาเดินถัดไปของผู้เล่นได้แม่นยำถึง 55.7% ในขณะที่ทีมอื่นที่ทำงานบนข้อมูลชุดนี้ทำได้เพียง 44.4%
นอกจากนี้ AlphaGO ยังได้มีการเพิ่มข้อมูลนำเข้าอื่นนอกจากตำแหน่งของหมากตรงๆ อีก เช่นจำนวนลมหายใจที่เหลือบนตำแหน่งต่างๆ บทความบอกว่านำเข้าเป็นข้อมูล 19x19 จำนวน 8 แผ่น, จำนวน turn ตั้งแต่ที่เล่นในตำแหน่งต่างๆ 8 แผ่นเช่นกัน, ตำแหน่งที่จะไล่แบบขั้นบันไดได้และตำแหน่งหนีการไล่ตามขั้นบันได 2 แผ่น, ฯลฯ รวม 48 แผ่น ซึ่งข้อมูลเสริมเหล่านี้ทำให้ AlphaGO ทำนายได้แม่นขึ้นถึง 57%

policy network ที่ได้ในขั้นนี้ชื่อ SL policy network (SL สำหรับ supervised learning) ซึ่งจะถูกนำไปปรับต่อโดยคราวนี้จะใช้ข้อมูลที่ได้จากการเล่นกับตัวเอง ในขั้นนี้เรามีรางวัลให้กับการเล่นแค่ในตอนจบซึ่งเราต้องส่งข้อมูลนี้ย้อนกลับไปเพื่อใช้ในการปรับ weight สำหรับ state ต่างๆ ของเกมที่ถูกเล่น การสอนระบบในขั้นนี้ต้องไปหาดูเพิ่ม keyword คือ policy gradient reinforcement learning
คณะวิจัยเตือนว่าเพื่อไม่ให้ network ลู่เข้าหา policy ปัจจุบันเพียงอย่างเดียว ในการเล่นกับตัวเองนั้นเขาเลือกให้ network ปัจจุบันเล่นกับหนึ่งใน network เก่าๆ ที่เลือกมาจากการสุ่ม

network ที่ได้เรียกว่า RL policy network (RL สำหรับ reinforcement learning) สามารถใช้คำนวณ P(a|s_t) เมื่อ s_t เป็น state ของเกมปัจจุบัน และ a เป็นตำแหน่งเดินต่างๆ ที่เป็นไปได้ เราสามารถใช้ข้อมูลนี้เลือกการเดิน a_t จากการสุ่มตามความน่าจะเป็น P(a|s_t) นี้ บทความบอกว่า RL policy network +การสุ่ม นี้พอที่จะชนะ Pachi ที่เป็น open-source GO program ได้ถึง 85% ของจำนวนครั้งที่เล่นแล้ว อันนี้น่าประทับใจมาก ไม่รู้ว่ากว่าจะสอน network ได้ขนาดนี้ต้องปรับพวก learning rate หรือ parameter อื่นแค่ไหน

Value network

neural network อีกอันที่ใช้ใน AlphaGO ชื่อ value network ที่โครงสร้างคล้ายกับ policy network แต่มีข้อมูลเพิ่มอีก 1 แผ่น ที่ระบุว่า ณ ตอนนี้เป็นตาเล่นของดำหรือขาว และมีชั้นส่งออกอีกหนึ่งชั้นที่มีเพียงโหนดเดียว โครงสร้างนี้ถูกสอนให้ทำนายความน่าจะเป็นที่การเดินนี้จะนำไปสู่ชัยชนะ

การสอน value network นั้นอิงข้อมูลจากการเล่นกับตัวเองเช่นกัน โดยใช้ RL policy network เป็นหลัก แต่ทั้งนี้ข้อมูลการเล่นนี้ถูกนำมากองรวมกันก่อนจะทำการสุ่มขึ้นมาเพื่อปรับ network การสอนในขั้นนี้เดาว่าใช้การปรับ weight ตาม gradient ปกติของ neural network เช่นกัน

Fast rollout policy

นอกจาก neuralnet ทั้งสองแล้ว องค์ประกอบอีกอันที่ดูจะสำคัญคือ fast rollout policy แต่ดูไม่ค่อยมีข้อมูลมากนัก เท่าที่ดู feature ของมันเขียนแต่พวก “move matches …” เดาว่าอาจจะเป็น rule-based model ที่ให้ expert เขียน อาจจะเป็นส่วนนี้ที่เห็นแว๊บๆ ว่าคนทำให้สัมภาษณ์ว่ามีบางส่วนของ AlphaGO ที่ยัง hard code อยู่ บทความบอกว่าตัว rollout policy นี้ run อยู่ที่ระดับ micro-second เมื่อเทียบกับ policy network ที่อยู่ที่ระดับ milli-second (เร็วกว่า 1000 เท่า)

Monte Carlo tree search (MCTS)

MCTS นี้รู้สึกว่าจะเป็นเทรนใหม่สำหรับ AI เพื่อเกม ในเกมที่มีจำนวน state น้อยอย่าง O-X หรือ tic-tac-toe นั้นเราสามารถเขียน state ของเกมที่เกิดจากการเลือก action ต่างๆ ต่อจาก state ปัจจุบันในรูปของ tree ได้ โดยเมื่อเราพิจารณาจนถึง state จบของเกมแล้ว เราสามารถนำรางวัลที่ได้ (ชนะ=+1, แพ้=-1) ส่งย้อนกลับขึ้นไปจนถึง action ต่างๆ ได้ จากนั้นเราก็สามารถเลือก action ที่ให้ผลชนะมากที่สุดเป็นต้น

ใน AlphaGO นั้นไม่ได้มีการพูดถึงการเข้ารหัสของ state ที่ใช้ใน tree search นี้โดยตรง อาจเป็นภาพแบบก่อนหน้านี้หรือไม่ยังไม่แน่ใจ (เดาว่าไม่ใช่)
MCTS นั้นทำงานเป็น loop โดยในแต่ละ loop จะเริ่มจากการเดินจาก root node ซึ่งก็คือ state ปัจจุบันของกระดานลงไปยังโหนดลูกต่างๆ ตาม action โดยในตอนต้นนั้นเราจะเรียกใช้ SL policy network กับ state ปัจจุบัน ซึ่งผลลัพธ์ที่ได้จะถือเป็น prior ของการเลือก action ต่างๆ หลังจากการเลือกโหนดลูกต่างๆ ค่า prior นี้จะถูกปรับขึ้น/ลง เพื่อถ่วงสมดุลระหว่าง exploration/exploitation ของการเดินในรูปแบบต่างๆ (selection step) หาก action ที่เลือกนั้นนำไปสู่โหนดที่ยังไม่มี เราก็จะทำการเพิ่มโหนดลูกให้กับโหนดนั้น (expansion step) และสำหรับโหนดใหม่นี้เราจะให้คะแนนจากสองส่วน ส่วนแรกคือค่าความน่าจะเป็นที่จะชนะที่ได้จาก value network อีกส่วนหนึ่งคือผลลัพธ์จากการเล่นต่อจนจบโดยใช้ fast rollout policy (evaluation step) ค่าทั้งสองนี้จะถูกนำมารวมกันเพื่อส่งต่อกลับไปยังโหนดพ่อที่อยู่ใน path จนถึง root node
ขั้นตอนทั้งหมดนี้จะถูกทำซ้ำไปเรื่อยๆ จนกว่าจะหมดเวลาในการคิด
ขั้นตอนการเดินกับตัวเองนี้เองที่เป็นการทำ simulation พวก Monte Carlo method
คะแนนที่ถูกส่งกลับนี้อิงจำนวนครั้งที่จะชนะ นี่น่าจะเป็นส่วนที่ทีมที่ทำอธิบายว่า AlphaGO สนใจเปอร์เซ็นต์ที่จะชนะมากกว่าพื้นที่นั่นเอง

ส่งท้าย

ของที่น่าสนคือตอนฟังคนบรรยายพูดถึงการเล่นของ AlphaGO เขาเดาว่ามันคงใช้การเลือก pattern การเดินจากชุดข้อมูลที่มี ตอนแรกผมก็คิดว่าอาจจะมีแบบนี้ผสมด้วยเหมือนกัน แต่กลายเป็นว่ามันใช้การเล่นกับตัวเองในการตัดสินใจ (MCTS) แต่ทั้งนี้การเล่นด้วย MCTS ที่ใช้ rollout policy อย่างเดียวให้ผลที่ไม่ดีเท่าการสุ่มตาเดินจาก policy network หรือจาก value network ที่ไม่ต้อง search เลย (และน่าจะเร็วกว่ากันเยอะ) แต่การนำเอาทั้งสามส่วนมารวมกันยิ่งให้ผลการเล่นที่ดีขึ้นอีก

ตอนที่เขียนนี้ AlphaGO ชนะ Lee Sedol ไป 2 กระดานรวดแล้ว รอดูผลต่อไป