เครื่องสนับสนุนเวกเตอร์แบบมีโครงสร้าง (Structured Support Vector Machine: SVM) เป็นอัลกอริธึมการเรียนรู้ของเครื่อง ที่ขยายขอบเขตของตัวจำแนกประเภท SVM ( Support Vector Machine ) ในขณะที่ตัวจำแนกประเภท SVM รองรับการจำแนกแบบไบนารีการจำแนกแบบหลายคลาสและการถดถอย SVM แบบมีโครงสร้างช่วยให้สามารถฝึกฝนตัวจำแนกประเภทสำหรับป้ายกำกับเอาต์พุตที่มีโครงสร้างทั่วไป ได้

ยกตัวอย่างเช่น ตัวอย่างประโยคภาษาธรรมชาติ และป้ายกำกับผลลัพธ์คือแผนผังการวิเคราะห์ประโยค ที่มีคำอธิบาย ประกอบ การฝึกตัวจำแนกประเภทประกอบด้วยการแสดงคู่ตัวอย่างและป้ายกำกับผลลัพธ์ที่ถูกต้อง หลังจากฝึกแล้ว โมเดล SVM ที่มีโครงสร้างจะช่วยให้สามารถทำนายป้ายกำกับผลลัพธ์ที่สอดคล้องกันสำหรับตัวอย่างใหม่ได้ กล่าวคือ เมื่อได้รับประโยคภาษาธรรมชาติ ตัวจำแนกประเภทสามารถสร้างแผนผังการวิเคราะห์ประโยคที่มีความเป็นไปได้มากที่สุดได้

สำหรับชุดหนึ่ง${\displaystyle n}$ตัวอย่างการฝึกอบรม${\displaystyle ({\boldsymbol {x}}_{i},y_{i})\in {\mathcal {X}}\times {\mathcal {Y}}}$,${\displaystyle i=1,\dots ,n}$จากพื้นที่ตัวอย่าง${\displaystyle {\mathcal {X}}}$และพื้นที่สำหรับติดฉลาก${\displaystyle {\คณิตศาสตร์ {Y}}}$โดย SVM ที่มีโครงสร้างจะลดฟังก์ชันความเสี่ยงแบบปรับค่าต่อไปนี้ให้เหลือน้อยที่สุด

${\displaystyle {\underset {\boldsymbol {w}}{\min }}\quad \|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}{\underset {y\in {\mathcal {Y}}}{\max }}\left(0,\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle \right)}$

ฟังก์ชันนั้นเป็นฟังก์ชันนูนใน${\displaystyle {\boldสัญลักษณ์ {w}}}$เนื่องจากค่าสูงสุดของเซตของฟังก์ชันเชิงเส้นตรงเป็นฟังก์ชันนูน ฟังก์ชัน${\displaystyle \Delta$ :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}} เป็นการวัดระยะทางในปริภูมิป้ายกำกับ และเป็นฟังก์ชันใดๆ (ไม่จำเป็นต้องเป็นเมตริก ) ที่สอดคล้องกับเงื่อนไขต่อไปนี้${\displaystyle \เดลต้า (y,z)\geq 0}$และ${\displaystyle \Delta (y,y)=0\;\;\forall y,z\in {\mathcal {Y}}}$ฟังก์ชัน${\displaystyle \Psi$ :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}} คือฟังก์ชันคุณลักษณะ ซึ่งดึงเวกเตอร์คุณลักษณะบางอย่างจากตัวอย่างและป้ายกำกับที่กำหนด การออกแบบฟังก์ชันนี้ขึ้นอยู่กับแอปพลิเคชันเป็นอย่างมาก

เนื่องจากฟังก์ชันความเสี่ยงที่ปรับให้เป็นมาตรฐานข้างต้นไม่สามารถหาอนุพันธ์ได้ จึงมักจะเขียนใหม่ให้อยู่ในรูปของโปรแกรมกำลังสองโดยการเพิ่มตัวแปรส่วนเกินเข้าไป หนึ่งตัว${\displaystyle \xi _{i}}$สำหรับแต่ละตัวอย่าง แต่ละค่าแสดงถึงค่าสูงสุด สูตรพื้นฐานของ SVM ที่มีโครงสร้างมาตรฐานมีดังต่อไปนี้

${\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {w}},{\boldsymbol {\xi }}}{\min }}&\|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}\xi _{i}\\{\textrm {st}}&\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle +\xi _{i}\geq \Delta (y_{i},y),\qquad i=1,\dots ,n,\quad \forall y\in {\mathcal {Y}}\end{array}}}$

ในขั้นตอนการทดสอบ จะใช้เพียงตัวอย่างเท่านั้น${\displaystyle {\boldsymbol {x}}\in {\mathcal {X}}}$เป็นที่ทราบกันดีอยู่แล้ว และมีฟังก์ชันการทำนายด้วย${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$แปลงค่าดังกล่าวเป็นป้ายกำกับที่คาดการณ์ไว้จากพื้นที่ป้ายกำกับ${\displaystyle {\คณิตศาสตร์ {Y}}}$สำหรับ SVM ที่มีโครงสร้าง เมื่อกำหนดเวกเตอร์แล้ว${\displaystyle {\boldสัญลักษณ์ {w}}}$ฟังก์ชันการทำนายที่ได้จากการฝึกฝนมีดังต่อไปนี้

${\displaystyle f({\boldสัญลักษณ์ {x}})={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\quad \langle {\boldสัญลักษณ์ {w}},\Psi ({\boldสัญลักษณ์ {x}},y)\rangle }$

ดังนั้น ค่าสูงสุดในพื้นที่ป้ายกำกับคือป้ายกำกับที่คาดการณ์ไว้ การหาค่าสูงสุดนี้เรียกว่าปัญหาการอนุมาน และคล้ายกับการทำนายค่าสูงสุดภายหลัง (MAP) ในแบบจำลองความน่าจะเป็น ขึ้นอยู่กับโครงสร้างของฟังก์ชัน${\displaystyle \Psi }$การหาค่าที่ทำให้ได้ผลลัพธ์สูงสุดอาจเป็นปัญหาที่ยาก

โปรแกรมกำลังสองข้างต้นเกี่ยวข้องกับ ข้อจำกัด อสมการเชิงเส้น จำนวนมาก ซึ่งอาจ เป็นอนันต์ โดยทั่วไปแล้ว จำนวนอสมการมีมากเกินกว่าที่จะหาค่าที่เหมาะสมที่สุดได้โดยตรง ดังนั้นจึงแก้ปัญหาโดยใช้การสร้างข้อจำกัดแบบหน่วงเวลา โดยใช้เพียงส่วนย่อยที่จำกัดและเล็กของข้อจำกัดเท่านั้น การหาค่าที่เหมาะสมที่สุดจากส่วนย่อยของข้อจำกัดจะขยายเซตที่เป็นไปได้และจะให้คำตอบที่เป็นขอบล่างของเป้าหมาย เพื่อทดสอบว่าคำตอบนั้นถูกต้องหรือไม่${\displaystyle {\boldสัญลักษณ์ {w}}}$หากละเมิดข้อจำกัดของชุดอสมการที่สมบูรณ์ จะต้องแก้ปัญหาการแยกส่วน เนื่องจากอสมการจะแยกย่อยไปตามตัวอย่าง สำหรับแต่ละตัวอย่าง${\displaystyle ({\boldsymbol {x}}_{i},y_{i})}$ปัญหาต่อไปนี้จำเป็นต้องได้รับการแก้ไข

${\displaystyle y_{n}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\xi _{i}\right)}$

เป้าหมายทางด้านขวามือที่ต้องการเพิ่มค่าให้สูงสุดนั้นประกอบด้วยค่าคงที่${\displaystyle -\langle {\boldสัญลักษณ์ {w}},\Psi ({\boldสัญลักษณ์ {x}__{i},y_{i})\rangle -\xi _{i}}$และเป็นเทอมที่ขึ้นอยู่กับตัวแปรที่ได้รับการปรับให้เหมาะสม กล่าวคือ${\displaystyle \Delta (y_{i},y)+\langle {\boldสัญลักษณ์ {w}},\Psi ({\boldสัญลักษณ์ {x}__{i},y)\rangle }$ถ้าค่าเป้าหมายด้านขวามือที่ได้นั้นมีค่าน้อยกว่าหรือเท่ากับศูนย์ แสดงว่าไม่มีข้อจำกัดใดถูกละเมิดสำหรับตัวอย่างนี้ แต่ถ้าค่าเป้าหมายด้านขวามือมีค่ามากกว่าศูนย์อย่างชัดเจน แสดงว่าได้ระบุข้อจำกัดที่ถูกละเมิดมากที่สุดสำหรับตัวอย่างนี้แล้ว ปัญหาจะถูกขยายใหญ่ขึ้นด้วยข้อจำกัดนี้และได้รับการแก้ไข กระบวนการนี้จะดำเนินต่อไปจนกว่าจะไม่สามารถระบุอสมการใดที่ถูกละเมิดได้อีก

หากตัดค่าคงที่ออกจากปัญหาข้างต้น เราจะได้ปัญหาต่อไปนี้ที่ต้องแก้ไข

${\displaystyle y_{i}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle \right)}$

ปัญหานี้ดูคล้ายกับปัญหาการอนุมานมาก ความแตกต่างเพียงอย่างเดียวคือการเพิ่มเทอมเข้าไป${\displaystyle \Delta (y_{i},y)}$โดยส่วนใหญ่แล้ว จะเลือกให้มีการแยกส่วนตามธรรมชาติในพื้นที่ป้ายกำกับ ในกรณีนั้น อิทธิพลของ${\displaystyle \Delta }$สามารถเข้ารหัสลงในปัญหาการอนุมานได้ และการหาข้อจำกัดที่ละเมิดมากที่สุดนั้นเทียบเท่ากับการแก้ปัญหาการอนุมาน