วิเคราะห์: แอปหาคู่ใช้ Stable Marriage + Graph Neural Network จริงหรือ?

วิเคราะห์: แอปหาคู่ใช้ Stable Marriage + Graph Neural Network จริงหรือ?

ในฐานะผู้ใช้งาน เราอาจมองว่าแอปหาคู่คือ “เกมแห่งการปัด” (Swiping Game) ที่ขึ้นอยู่กับโชคชะตาและรูปโปรไฟล์ แต่เบื้องหลังอินเทอร์เฟซที่เรียบง่ายนั้น คือสมรภูมิทางคณิตศาสตร์และ AI ที่ซับซ้อนมหาศาล

คำถามที่น่าสนใจคือ: บริษัทเทคโนโลยีเหล่านี้ นำ “อัลกอริทึม” สองตัวที่ดูเหมือนจะมาจากคนละยุคสมัย อย่าง Stable Marriage Problem (SMP) อัลกอริทึมคลาสสิกยุค 1960s และ Graph Neural Networks (GNNs) สุดยอด AI แห่งยุคปัจจุบัน มาผสมกันจริงหรือ?

คำตอบคือ “ใช่ครับ… แต่ไม่ใช่ในแบบที่คุณคิด”

มันไม่ใช่การเอาอัลกอริทึม 1 + 1 มาต่อกัน แต่ GNNs ได้เข้ามา “ปลดล็อก” และ “แก้ปัญหา” ที่ทำให้ SMP “ใช้การไม่ได้” ในโลกแห่งความเป็นจริง

🧠 1. ความฝันสุดคลาสสิก: Stable Marriage Problem (SMP)

SMP คืออัลกอริทึมที่สวยงาม สร้างโดย David Gale และ Lloyd Shapley (ซึ่ง Shapley ได้รับรางวัลโนเบลจากงานนี้)

• โจทย์: เรามีกลุ่ม “ผู้ชาย” $n$ คน และ “ผู้หญิง” $n$ คน (หรือนักเรียนกับโรงพยาบาล, ผู้สมัครงานกับบริษัท)
• เงื่อนไข: ทุกคนมี “รายการลำดับความชอบ” (Preference List) ของทุกคนในอีกฝั่ง
• เป้าหมาย: จับคู่ทุกคนให้ “มีเสถียรภาพ” (Stable)

“เสถียรภาพ” ในที่นี้ ไม่ได้แปลว่า “รักกัน” แต่หมายความว่า “ไม่มีการแอบนัด”

พูดทางคณิตศาสตร์คือ: จะต้องไม่มี “คู่ขวาง” (Blocking Pair)

“คู่ขวาง” (Blocking Pair) คือ ชาย A กับ หญิง B ที่ ไม่ได้ ถูกจับคู่กัน แต่…

1. ชาย A “ชอบ” หญิง B มากกว่าคู่ของตัวเอง
2. และ หญิง B ก็ “ชอบ” ชาย A มากกว่าคู่ของตัวเองด้วย

   ถ้ามีคู่นี้เกิดขึ้น ระบบจะ “ไม่เสถียร” เพราะ A กับ B มีแนวโน้มที่จะ “หนีตามกันไป”

ทำไมแอปหาคู่ถึง “ใช้ SMP ตรงๆ ไม่ได้”?

ปัญหาของโลกจริงมี 3 ข้อใหญ่:

1. ปัญหาด้านข้อมูล (The Preference List): SMP ตั้งสมมติฐานว่า “ทุกคนมีลำดับความชอบของทุกคน” ในโลกจริงที่มีผู้ใช้ 50 ล้านคน คุณจะไปเอา “Preference List” ที่คุณจัดอันดับคน 25 ล้านคนมาจากไหน? นี่คือจุดที่ SMP “ตาย” ในทางปฏิบัติ
2. ปัญหาด้านสเกล (The Scale): อัลกอริทึม Gale-Shapley ทำงานที่ความซับซ้อน $O(n^2)$ ซึ่ง “ดีมาก” สำหรับ $n=1000$ แต่ “เป็นไปไม่ได้” สำหรับ $n=25,000,000$
3. ปัญหาด้านธุรกิจ (The Business): เป้าหมายของ Gale-Shapley คือ “ความเสถียร” ครั้งเดียวจบ แต่เป้าหมายของแอปคือ “การมีส่วนร่วม” (Engagement)

🕸️ 2. เครื่องมือ AI ยุคใหม่: Graph Neural Networks (GNNs)

นี่คือจุดที่ AI เข้ามา GNN คือ Machine Learning ประเภทหนึ่งที่เกิดมาเพื่อ “ข้อมูลเครือข่าย” โดยเฉพาะ

แอปหาคู่คือ “กราฟ” (Graph) ขนาดมหึมา:

• Nodes (โหนด): คือ “ตัวคุณ” และผู้ใช้คนอื่นๆ
• Edges (เส้นเชื่อม): คือ “การกระทำ” เช่น การปัดขวา, การปัดซ้าย, การส่งข้อความ, การดูโปรไฟล์ซ้ำๆ

GNN ไม่ได้มองคุณแค่ “โปรไฟล์ของคุณ” (อายุ, รูป, คำอวย) แต่มันมองคุณในฐานะ “ผลรวมของเครือข่าย”

GNN “คิด” ว่า: “ถ้าคุณปัดขวาให้คน A, B, C… และคน A, B, C ก็ปัดขวาให้คน X, Y, Z…

…ถ้าอย่างนั้น คุณ ก็น่าจะมีความชอบคล้ายกับ X, Y, Z”

หน้าที่ของ GNN คือการ “เรียนรู้” สิ่งที่เรียกว่า “User Embedding” (เวกเตอร์ตัวเลขที่ซับซ้อน) ซึ่งเป็น “รหัสลับ” ที่อธิบาย “รสนิยม” ที่แท้จริงของคุณ โดยอิงจากพฤติกรรมของคุณและพฤติกรรมของคนที่คุณชอบ (และคนที่ชอบคุณ)

❤️ 3. บทสรุป: GNNs “สร้าง” โลกให้ SMP “ทำงาน” ได้

นี่คือบทสรุปที่สำคัญที่สุด:

แอปหาคู่ไม่ได้ใช้ “SMP + GNN” แต่แอปใช้ “GNNs เพื่อสร้าง Preference List” แล้วนำไปป้อนให้ “ระบบจับคู่” (Matching System) ที่ได้รับแรงบันดาลใจจาก SMP

พูดง่ายๆ คือ:

1. GNNs แก้ปัญหาข้อที่ 1 (ปัญหาข้อมูล):

   คุณไม่ต้องนั่งจัดอันดับคน 25 ล้านคน แต่ GNN จะ “เรียนรู้” รสนิยมของคุณจาก “การปัด” ของคุณ แล้ว GNN จะ “คำนวณ” คะแนนความน่าจะเป็น (Probability Score) ให้คุณกับผู้ใช้คนอื่นๆ ที่คุณ “น่าจะ” ชอบ

   ผลลัพธ์: GNN สร้าง “Preference List” เสมือนจริง (Virtual Preference List) ที่มีขนาดสั้นๆ (เช่น 100 คนที่คุณน่าจะชอบที่สุด) ขึ้นมาให้คุณโดยอัตโนมัติ

2. ระบบจับคู่ แก้ปัญหาข้อที่ 2 (ปัญหาด้านสเกล):

   เมื่อ GNNs กรองคน 25 ล้านคน ให้เหลือ “กลุ่มเป้าหมาย” ที่น่าสนใจสำหรับคุณแค่ 100-1000 คนแล้ว…

   ณ จุดนี้ การรันอัลกอริทึมที่ซับซ้อน (อาจจะไม่ใช่ SMP เป๊ะๆ แต่เป็นระบบ Recommendation ที่คล้ายกัน) บนกลุ่มขนาดเล็ก ($n=1000$) ก็กลายเป็นเรื่องง่ายและรวดเร็ว

สรุปก็คือ:

• Graph Neural Network (GNN): คือ “เครื่องมือค้นหาและทำความเข้าใจ” ทำหน้าที่วิเคราะห์กราฟที่ซับซ้อน แล้วตะโกนบอกระบบว่า “เฮ้! User A กับ User B ดูมีเคมีเข้ากันมาก!”
• Stable Marriage Problem (SMP): คือ “ปรัชญา” หรือ “เป้าหมาย” ที่ระบบจับคู่พยายามทำ ระบบจะไม่อยากโชว์คู่ที่ “ไม่เสถียร” ให้คุณ (เช่น โชว์คนที่คุณปัดขวา แต่เขาไม่มีวันปัดขวาให้คุณกลับ) เพราะมันทำให้คุณ “รู้สึกแย่” และ “เลิกเล่น”

ดังนั้น จริงครับ แอปหาคู่ที่ฉลาดที่สุดกำลังใช้ GNNs เพื่อ “ทำนาย” ความชอบที่ซับซ้อน และใช้ปรัชญาของ SMP เพื่อ “จัดเรียง” คู่ที่น่าจะ “สมหวัง” (Mutually Interested) ที่สุดมาให้คุณเห็นก่อนนั่นเองครับ