งานวิจัยสุ่มๆ
วันนี้ได้รับเชิญให้ไปพูดให้เด็กมัธยมต้นฟังเรื่องอะไรก็ได้ที่เกี่ยวกับงานวิจัยที่ทำ เลยมานั่งนึกดูว่างานอะไรจะพอเอามาเล่าให้เด็กฟังได้ คิดไปคิดมาเลยนึกถึงงานที่ทำเมื่อ 2–3 ปีก่อนที่สนุกดี เลยมาบันทึกไว้หน่อยเผื่อมีคนสนใจ
โจทย์: วัดมุมด้วยไม้ฉาก
หากเราต้องการวัดมุมระหว่างเส้นสองเส้น ถ้าเรามีไม้โปรแทรกเตอร์เราก็สามารถวัดมันได้ง่ายๆ แต่สมมติว่าเราไม่มีไม้โปร แต่เรามีแค่ไม้ฉาก ที่วัดมุมได้แค่ 90 องศา เราจะวัดมุมที่ไม่ใช่มุมฉากได้หรือไม่?
ในตัวอย่างนี้มุมระหว่างเส้นทั้งสองคือ 84 องศา
ก่อนที่จะอ่านต่อลองคิดเล่นๆ ดูก่อนก็ได้ว่าต้องทำยังไง
อัลกอริธึม
วิธีง่ายๆ ในการวัดคือตีเส้นแบ่ง 8 เส้นตามรูปข้างล่างนี้
จากนั้นเราแยกพิจารณาเส้นทั้งสองเริ่มจากสีเขียวก่อน เราจะแยกเส้นแบ่งทั้ง 8 นี้ออกเป็นสองกลุ่ม กลุ่มแรกคือกลุ่มที่ทำมุมกับเส้นสีเขียวน้อยกว่าหรือเท่ากับ 90 องศา และกลุ่มที่สองคือกลุ่มที่ทำมุมมากกว่า 90 องศา การแบ่งกลุ่มนี้ทำได้ง่ายๆ โดยใช้ไม้ฉาก
หากให้เส้นแบ่งในกลุ่มแรกเป็นสีน้ำเงินและเส้นแบ่งในกลุ่มสองเป็นสีแดง เราจะได้รูปต่อไปนี้
หากเราทำอย่างเดียวกันกับเส้นสีแดงม่วง (magenta) เราจะได้อีกรูปคือ
จากนั้นให้นับจำนวนเส้นแบ่ง ในบรรดา 8 เส้นนี้ ที่ถูกจัดให้อยู่คนละกลุ่ม ในกรณีนี้มีอยู่ 4 เส้น ค่ามุมประมาณคือ 4/8 คูณ180 นั่นคือ 90 องศา
ค่าที่ได้นี้ยังต่างออกไปจากมุมจริง (84 องศา) อยู่ แต่เราสามารถทำซ้ำโดยใช้จำนวนเส้นแบ่งที่มากขึ้นได้ รูปข้างล่างนี้แสดงผลการแบ่งกลุ่มที่ได้จากการใช้เส้นแบ่งจำนวนมากขึ้นเป็น 16, 32, 64 และ 128 เส้น โดยฝั่งซ้ายเป็นผลจากการเทียบกับเส้นเขียวในรูปแรก และด้านขวาได้จากการเทียบกับเส้นแดงม่วง และค่ามุมที่ประมาณได้
จะเห็นว่ามุมที่ประมาณได้นั้นเข้าใกล้ผลเฉลยจริงมากขึ้นเรื่อยๆ เมื่อเราเพิ่มจำนวนเส้นแบ่งให้มากขึ้น
ตอนนี้บางคนอาจจะเถียงว่าในการสร้างเส้นแบ่งแบบนี้เราก็ต้องใช้ไม้โปรแทรกเตอร์อยู่ดี แต่จริงๆ แล้วเราก็สามารถประมาณค่ามุมได้จากเส้นแบ่งที่สร้างแบบสุ่ม ตัวอย่างผลจากการแบ่งกลุ่มของเส้นแบ่ง 64 เส้นที่ได้จากการสุ่มหลายครั้ง เป็นดังรูปข้างล่างนี้
ในตัวอย่างนี้ค่ามุมที่ประมาณได้ก็ต่างกันออกไปขึ้นกับการสุ่ม จากตัวอย่างนี้หากเราสุ่มเส้นแบ่ง 64 เส้นนี้มา 10 รอบ ค่าเฉลี่ยของมุมที่ประมาณได้จะอยู่ที่ 89.59 องศา โดยมีค่าเบี่ยงเบนมาตรฐานประมาณ 8 องศา ถึงแม้ว่ามุมที่ประมาณได้นั้นจะต่างจากมุมจริงอยู่บ้างแต่วิธีนี้สามารถนำไปใช้กับ ข้อมูลหลายมิติ ได้ด้วย
ทฤษฎีเล็กน้อย
เพื่อเข้าใจที่มาของอัลกอริธึมข้างบนให้ลองดูรูปข้างล่างนี้
ในรูปนี้เราต้องการวัดมุมระหว่างเส้นสีเขียวและม่วงแดง โดยมีเส้น a และ b ที่ตั้งฉากกันอยู่ จากรูปเราก็เห็นได้ง่ายๆ ว่ามุมระหว่าง a และเขียวนั้นน้อยกว่ามุมฉาก และมุมระหว่าง a และม่วงแดง นั้นมากกว่าฉาก ดังนั้นหากเราใช้ a เป็นเส้นเทียบผลที่ได้จากเขียวและม่วงแดงก็จะต่างกัน
ที่นี้เราสามารถสุ่มเส้นแบบ a ได้จำนวนเท่าไรล่ะ? คำตอบคือดูจาก b ตราบใดที่ b อยู่ระหว่างเขียวและม่วงแดงเส้น a ที่ตั้งฉากกับมันก็จะให้ผลเทียบที่ต่างกัน
ทั้งนี้หาก a ชี้ลงแทนที่จะชี้ขึ้นตามรูปผลเทียบที่ได้ก็ยังคงต่างกันอยู่
ถ้าคิดแบบง่ายๆ ก็คือเราสามารถสุ่ม a ได้ 2Ɵ วิธีจากจาก 360 มุม
เมื่อ Ɵ เป็นมุมระหว่างเขียวและม่วงแดงที่เราต้องการประมาณ
นั่นคือความน่าจะเป็นในการสุ่มเส้นเทียบที่ให้ผลต่างกันคือ Ɵ/180
นี่คือค่าทางทฤษฎีที่เราต้องการประมาณ
ในทางปฏิบัติเราสามารถนับจำนวนเส้นเทียบที่ให้ผลต่าง และเมื่อเรานำจำนวนนี้มาหารด้วยจำนวนเส้นเทียบทั้งหมดก็จะได้ค่าประมาณของความน่าจะเป็นที่เราต้องการนั่นเอง
ดังนั้นเมื่อเราเอาอัตราส่วนที่ได้นี้คูณกับ 180 ก็จะได้ค่าประมาณของมุม Ɵ ตามต้องการ
แนวความคิดนี้ไม่ได้จำกัดวิธีการสร้างเส้นเทียบดังนั้นเราจึงสามารถใช้การสุ่มแทนการแบ่งมุมแบบเป็นระบบได้
ข้อมูลหลายมิติและรหัสฐานสอง
ในงานด้านการรู้จำรูปแบบนั้นขั้นตอนแรกคือการสกัดลักษณะเด่นต่างๆ (features) จากข้อมูลนำเข้าไม่ว่าจะเป็น features ด้านภาพ, ด้านเสียง, หรือ features ที่ได้จาก CNN ซึ่งโดยปกติ features ที่สกัดได้นั้นจะถูกนำเสนอในรูปของ เวคเตอร์ในปริภูมิหลายมิติ (high-dimensional vector)
เราสามารถวัดความต่างของเวคเตอร์เหล่านี้ได้โดยใช้ ฟังก์ชันระยะห่างต่างๆ โดยหากเราสามารถวัดความต่างได้เราก็สามารถค้นคืนข้อมูลที่มีลักษณะคล้ายๆ กันได้ หรือสามารถประยุกต์ใช้ตัวจำแนกประเภทเช่น k-Nearest Neighbors (k-NN) ได้เป็นต้น
หนึ่งในระยะห่างที่เรามักใช้กันก็คือระยะห่างแบบยูคลิด (Euclidean distance) ซึ่งใน 2 มิติก็ตรงกับระยะห่างที่เราเรียนมาตั้งแต่มัธยมนั่นเอง ในกรณีที่เวคเตอร์ทั้งสองมี “ขนาด” ไม่ต่างกันนักระยะห่างแบบยูคลิดก็แปรผันตรงข้ามกับมุมระหว่างเวคเตอร์ทั้งสอง ดังนั้นถ้าเราสามารถคำนวณมุมระหว่างเวคเตอร์ได้ง่ายและเร็ว เราก็สามารถค้นคืนข้อมูลที่คล้ายกันได้เร็วขึ้นด้วย
หนึ่งในการประยุกต์ใช้แนวความคิดของการประมาณค่ามุมข้างบนนี้คือ ใช้ในการแปลงเวคเตอร์นำเข้าเป็นรหัสสุ่มฐานสอง
- สร้างเวคเตอร์สุ่มขึ้นมาจำนวนหนึ่ง
- ผูกเวคเตอร์สุ่มแต่ละตัวไว้กับ “บิต” หนึ่งๆ
- นำเวคเตอร์นำเข้าไปเทียบกับเวคเตอร์สุ่มแต่ละตัว โดยหากมุมระหว่างเวคเตอร์นำเข้าและเวคเตอร์สุ่มมีค่ามากกว่า 90 องศาก็ให้ค่าของบิตนี้เป็น 1 และหากค่ามุมนั้นน้อยกว่า 90 องศาก็ให้ค่าบิตนั้นเป็น 0
- หากเรามีเวคเตอร์สุ่ม m เวคเตอร์ ก็แปลว่าเราสามารถแปลงเวคเตอร์นำเข้าใดๆ เป็นรหัสฐานสองขนาด m บิตได้
สมมติให้ x และ y เป็นเวคเตอร์นำเข้าใดๆ โดยที่ c(x) และ c(y) เป็นรหัสสุ่มฐานสองของเวคเตอร์ทั้งสองแล้วมุม (แบบองศา) ระหว่าง x และ y นั้นประมาณได้จาก
โดยที่ Ham เป็นฟังก์ชันที่นับจำนวนบิตที่ต่างกันระหว่าง c(x) และ c(y) หรือก็คือ Hamming distance นั่นเอง
ควรทราบว่าเราสามารถแบ่งรหัสฐานสองนี้เป็นท่อนๆ ได้ เช่นท่อนละ 8 บิต ซึ่งเมื่อเรานำรหัส 8 บิตนี้มาแปลงเป็นจำนวนเต็มก็จะมีค่าที่ต่างกันได้ 256 ค่า นั่นแปลว่าเราสามารถคำนวณ Hamming distance นี้ล่วงหน้าได้โดยใส่ไว้ในตารางขนาด 256x256 ซึ่งก็ไม่ใหญ่มากนัก การคำนวณค่ามุมจากรหัสสุ่มฐานสองนั้นจึงใช้เพียงการนำค่าจากตาราง look-up table นี้มาบวกกัน
นอกจากนี้หากเราเก็บค่าขนาดของเวคเตอร์ต่างๆ ไว้ด้วยก็สามารถนำมาใช้รวมกันเพื่อประมาณค่าระยะห่างแบบยูคลิดได้ ซึ่งกระบวนการนี้ทำได้เร็วกว่าการคำนวณระยะห่างแบบยูคลิดแบบปกติมากกกก
นอกจากนี้รหัสฐานสองเช่นนี้ยังต้องการพื้นที่ในการเก็บที่น้อยกว่าอีกต่างหาก มันจึงเหมาะสำหรับการทำดัชนีข้อมูลเพื่อการค้นคืนอย่างเร็วภายหลัง
ตัวจำแนกแบบสุ่ม
หลังจากนั่งเล่นกับการเข้ารหัสแบบสุ่มข้างบนอยู่พักนึงก็เริ่มได้ idea ใหม่คือ ในเมื่อเราสามารถประมาณค่ามุมได้จากรหัสฐานสองที่ได้จากการฉายสุ่ม และตัวจำแนกประเภทแบบระนาบตรง หรือ linear classifier ซึ่งเป็นตัวจำแนกประเภทมาตรฐานอันหนึ่งก็ใช้ข้อมูลของมุมในการจำแนก บางทีเราน่าจะสามารถทำการจำแนกประเภทได้โดยตรงบนรหัสสุ่มฐานสองนี้โดยใช้แนวความคิดเดียวกับ linear classifier
ผลจากการวิเคราะห์เล็กๆ ได้ความว่าในกรณีของข้อมูล 2 คลาส เราสามารถสร้างรหัสต้นแบบ (template) ได้จากค่าฐานนิยม (mode) ของแต่ละบิตโดยตรง เมื่อได้รหัสต้นแบบแล้ว เราสามารถจำแนกประเภทข้อมูลนำเข้าใหม่ ที่อยู่ในรูปรหัสสุ่มฐานสอง ได้จากระยะห่าง Hamming ระหว่างรหัสต้นแบบนี้เอง
เราสามารถพิสูจน์ได้ว่าผลที่ได้จากการจำแนกด้วยรหัสสุ่มนี้จะใกล้เคียงกับผลที่ได้จากตัวจำแนกระนาบตรง ด้วยความน่าจะเป็นสูง น่าเสียดายที่การเพิ่มความยาวรหัสนั้นทำให้ generalization bound นั้นหลวมขึ้น ดังนั้นจึงอาจจะ overfit ได้ นอกจากนี้ผลการวิเคราะห์นั้นทำเฉพาะในกรณีที่ขอบเขตระหว่างทั้งสองคลาสนั้นเป็นเส้นตรงจริงเท่านั้นดังนั้นผลที่ได้จากตัวจำแนกสนุกๆ นี้จึงไม่ดีนัก อย่างไรก็ดีเราสามารถใช้กระบวนการ Boosting เพื่อเพิ่มประสิทธิภาพได้อยู่ แต่ผมไม่ค่อยชอบที่ Boosting ดูจะไม่เหมาะกับข้อมูลใหญ่ๆ ในขณะที่การฉายสุ่มนี้เหมาะกับมันมาก ตอนนี้เลยนึกไม่ออกว่าเอาไปทำอะไรต่อดี
เอกสารอ้างอิง
- Sanparith Marukatat, Ithipan Methasate: Fast nearest neighbor retrieval using randomized binary codes and approximate Euclidean distance. Pattern Recognition Letters 34(9):1101–1107 (2013)
- Sanparith Marukatat: Classification with Sign Random Projections. PRICAI 2014: 708–719
