Quantum Support Vector Machine


Share this article

วันนี้เราจะมาทำความรู้จักกับ Quantum Support Vector Machine (QSVM) กันครับ ซึ่ง QSVM คือการนำ SVM มาใช้กับ Quantum Computing โดย SVM นั้นเป็นโมเดล Machine Learning โมเดลหนึ่งสำหรับจำแนกประเภทของข้อมูลซึ่งถูกใช้กันอย่างแพร่หลาย ส่วน Quantum Computing นั้นจะช่วยในเรื่องการเร่งความเร็วในการคำนวณได้ตามทฤษฎี ต่างจากคอมพิวเตอร์แบบปกติ (Classical Computer) หากท่านใดไม่มีพื้นฐานทางด้าน Quantum Computing มาก่อน สามารถศึกษาได้จากบทความนี้ https://www.qute-th.com/2018/11/26/ควอนตัมคอมพิวเตอร์-101/  นอกจากนั้น ในบทความนี้จะมีการกล่าวถึง Qiskit ซึ่งเป็นหนึ่งใน open-source ที่ศึกษาและพัฒนาระบบต่าง ๆ เกี่ยวกับ quantum computing ตั้งแต่ระบบการจำลอง quantum simulation บน classical computer ไปจนถึง quantum program ใน quantum device บน IBM Quantum Experience https://quantum-computing.ibm.com/ ด้วย

Support Vector Machines

Support Vector Machine (SVM) คือ การทำ Machine Learning แบบ Supervised Learning (เรียนรู้แบบมีผู้สอน) โดยการหา Hyperplane ขั้นระหว่างข้อมูลแต่ละประเภท (Class) ซึ่ง Hyperplane ที่เหมาะสำหรับจำแนกประเภทของข้อมูลนั้นจะมาจากการหา Hyperplane ที่มีระยะขอบห่างจากตำแหน่งข้อมูลมากที่สุด

รูปที่ 1 ตัวอย่างการสร้าง hyperplane 1 มิติ (H1, H2, H3) บนข้อมูลที่มี 2 features (x1,x2) โดยข้อมูลมี 2 ประเภท (ขาว, ดำ)

รูปที่ 1 แสดงตัวอย่าง Hyperplane H1 ที่ไม่สามารถจำแนกประเภทของข้อมูลได้ ส่วน H2 นั้นสามารถแบ่งแยกประเภทข้อมูลได้ แต่มีระยะห่างจากตำแหน่งข้อมูลเพียงเล็กน้อย ในขณะที่ H3 นั้นเหมาะสมสำหรับการจำแนกข้อมูลชุดนี้ เนื่องจากเป็น Hyperplane ที่สร้างระยะห่างจากข้อมูลสองประเภทได้มากที่สุด

Kernel Trick

ในบางครั้งข้อมูลที่ปะปนกันนั้น ไม่สามารถใช้สมการเส้นตรงในการแบ่งประเภทได้ อย่างในรูปที่ 2 ทางด้านซ้าย ซึ่งเราสามารถทำให้ SVM  สามารถนำไปใช้งานได้หลากหลายมากขึ้นโดยการใช้ Kernel Trick ซึ่งเป็นเทคนิคที่ใช้ในการเพิ่มมิติให้กับข้อมูล เพื่อที่จะทำให้เราสามารถสร้าง Hyperplane มาแบ่งข้อมูลในมิติที่สูงขึ้นได้

รูปที่ 2 ซ้าย ตัวอย่างข้อมูลที่ไม่สามารถแยกได้โดยใช้ hyperplane ที่เป็นเส้นตรงขวา ตัวอย่างการใช้ kernel trick เพื่อเพิ่มมิติของข้อมูล

รูปที่ 2 ทางด้านขวา เป็นการนำข้อมูล 2 มิติ (x, y) จากรูปที่ 2 ทางด้านซ้าย มาแปลง โดยใช้ Kernel Function

ซึ่งผลลัพธ์ที่ได้จะเป็นข้อมูล 3 มิติ ที่สามารถสร้างระนาบ 2 มิติมาแบ่งข้อมูลออกจากกันได้อย่างชัดเจน

Quantum SVM Algorithm

เมื่อข้อมูลมีความซับซ้อนมากขึ้น และเราต้องใช้ Kernel Trick ทำให้ข้อมูลมีมิติสูงขึ้นเรื่อย ๆ นั้น ส่งผลต่อเวลาที่ใช้ในการคำนวณ และบางครั้งคอมพิวเตอร์ที่เราใช้กันอยู่ทั่วไปอาจจะพบเจอความลำบากในการคำนวณ Kernel ที่ซับซ้อนและใช้เวลานาน ในกรณีนี้ การใช้ Quantum Computer จะสามารถช่วยในการเร่งความเร็วในการ Train โมเดลได้ โดย Paper ที่ชื่อว่า Supervised Learning With Quantum Enhanced Feature Spaces (https://arxiv.org/abs/1804.11326) ได้กล่าวถึงการสร้าง Quantum Feature Maps ซึ่งคือการนำ Classical Data มาทำการ Encoding ให้อยู่ในรูปแบบ Quantum State แล้วสามารถสร้าง Kernel เพื่อ Train Quantum SVM ได้เช่นเดียวกันกับ Classical SVM

รูปที่ 3 การใช้ Bloch Sphere ในการนำเสนอ Feature Map ใน 1 Qubit

รูปที่ 3 ทางด้านซ้าย คือการใช้ Bloch Sphere ในการนำเสนอ Quantum Feature Map ใน 1 Qubit ที่แปลงจาก Classical Dataset ที่มีช่วงอยู่ระหว่าง 0 ถึง 2π และ รูปที่ 3 ทางด้านขวา นำเสนอ Label ของข้อมูล โดยเส้นตรงสีน้ำเงินและสีแดงระบุประเภทของข้อมูล และเส้นโค้งสีดำที่ตัดระหว่างข้อมูลทั้งสองประเภท คือ hyperplane ที่ใช้แบ่งประเภทของข้อมูล

แนวคิดของการทำ Quantum Features Map นั้นมีความเป็นไปได้ที่จะสามารถทำงานได้จริงโดยใช้ Quantum Computer ในอนาคตอันใกล้ เนื่องจาก Algorithm นี้สามารถทำงานได้ใน Quantum Circuit ที่มี Noise สูง และไม่จำเป็นต้องใช้ Quantum Circuit ที่มีความลึก และจำนวน Qubit สูง โดยทาง Qiskit ได้มีตัวอย่างของการ Simulate QSVM (https://qiskit.org/documentation/tutorials/machine_learning/01_qsvm_classification.html)  โดยใช้ Ad Hoc Dataset ที่ทาง Qiskit  สร้างขึ้นมา

รูปทางซ้ายสุด คือ ตัวอย่างของ Ad Hoc Dataset ตรงกลางคือ Kernel จากการใช้ Quantum Feature Map ของ Qiskit และ รูปขวาสุดคือ Kernel จาก Sklearn SVM ที่เป็น SVM ของ Classical

ผลลัพธ์ที่ได้จาก QSVM
ผลลัพธ์ที่ได้จาก Classical SVM

ตัวอย่างที่ Qiskit ยกมานั้นแสดงให้เห็นว่าบางครั้งจะมี Dataset ที่ Quantum ทำงานได้ดีกว่า โดยมี Success Rate 100% เทียบกับ 55% ของ Classical SVM

Least-Squares Support-Vector Machine

นอกจาก SVM จะใช้ประโยชน์จากการทำ Quantum Feature Maps ได้แล้วนั้น ยังมี SVM อีกประเภทหนึ่งที่สามารถใช้ Quantum Computer เร่งความเร็วในการ Train โมเดลได้โดยตรง ซึ่งก็คือ Least-Squares Support-Vector Machine (LS-SVM) โดย SVM แบบปกติคือการ Optimize หาพารามิเตอร์สำหรับ Maximize ระยะ Margin ระหว่าง Hyperplane กับข้อมูลของแต่ละประเภท ส่วน LS-SVM นั้นจะจัดปัญหาให้เป็น Linear Equation แทน โดยในส่วนของ LS-SVM นั้น สามารถศึกษาหาข้อมูลเพิ่มเติมรวมถึงที่มาของสมการได้จาก https://en.wikipedia.org/wiki/Least-squares_support-vector_machine โดย optimal solution ของ LS-SVM สามารถหาได้โดยการแก้สมการดังต่อไปนี้

โดย b และ α คือค่า Parameter ที่เราต้องการหา ส่วน K คือ Kernel ที่มาจาก Dataset และ Y คือ Label ซึ่งการแก้สมการหา Parameter ที่เราต้องการนั้น สามารถใช้การ Inverse Matrix จากสมการด้านบนได้เป็น

ในกรณีนี้มี Quantum Algorithm สำหรับการแก้สมการเชิงเส้นชื่อว่า HHL Algorithm ที่สามารถใช้แก้ปัญหาแบบเดียวกันได้โดยตรงคล้ายกับการทำ matrix inversion แต่จะใช้เวลาน้อยกว่าเมื่อเทียบกับวิธีการ Classical  โดยเวลาที่ใช้จะอยู่ที่ O(Log(N)) โดยที่ N คือจำนวนตัวแปรในระบบ เทียบกับ O(N ) สำหรับการแก้สมการเชิงเส้นแบบ Classical

Reference
[1] Quantum Support Vector Machines — A new era of AI

[2] Introduction into Quantum Support Vector Machines

[3] Wikipedia – Support-vector machine

[4] Everything You Wanted to Know about the Kernel Trick

[5] Wikipedia – Quantum computing

[6] Qiskit – Machine Learning Tutorials

[7] Supervised learning with quantum enhanced feature spaces

[8] Quantum support vector machine for big data classification

[9] Wikipedia – Least-squares support-vector machine


ลงทะเบียนรับข่าวสาร

ไม่พลาดทุกการอัพเดทจาก Big Data Experience Center

Big Data Experience Center (BX)

ชั้น 14 อาคาร Knowledge Exchange Center (KX)
110/1 ถนนกรุงธนบุรี, แขวงบางลำภูล่าง เขตคลองสาน กรุงเทพฯ 10600
อีเมล์: [email protected]
Tel: 097-941-9889

ABOUT

SERVICES