โครงสร้างk -nearest neighbours ( SkNN ) ^{[ 1 ] [ 2 ] [ 3 ]}เป็น อัลกอริธึม การเรียนรู้ของเครื่องที่ขยายk -nearest neighbors ( k -NN) k -NN รองรับการจำแนกแบบไบนารีการจำแนกแบบหลายคลาสและการถดถอย^{[ 4 ​​]}ในขณะที่ SkNN อนุญาตให้ฝึกตัวจำแนกสำหรับเอาต์พุตที่มีโครงสร้างทั่วไป

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

SkNN รับลำดับขององค์ประกอบที่มีป้ายกำกับคลาส เป็นชุดข้อมูลฝึกฝนประเภทขององค์ประกอบไม่สำคัญ ข้อกำหนดเพียงอย่างเดียวคือต้องมีฟังก์ชันเมตริกที่กำหนดไว้ซึ่งให้ระยะห่างระหว่างองค์ประกอบแต่ละคู่ในชุดข้อมูล

SkNN มีพื้นฐานมาจากแนวคิดการสร้างกราฟโดยแต่ละโหนดแทนป้ายกำกับคลาส จะมีเส้นเชื่อมระหว่างโหนดคู่หนึ่งหากมีลำดับขององค์ประกอบสองตัวในชุดข้อมูลฝึกฝนที่มีคลาสที่สอดคล้องกัน ขั้นตอนแรกของการฝึกฝน SkNN คือการสร้างกราฟดังกล่าวจากลำดับการฝึกฝน มีโหนดพิเศษสองโหนดในกราฟที่สอดคล้องกับจุดเริ่มต้นและจุดสิ้นสุดของประโยค: หากลำดับเริ่มต้นด้วยคลาสCจะต้องสร้างเส้นเชื่อมระหว่างโหนดSTARTและโหนดC

เช่นเดียวกับ k -NN ทั่วไปส่วนที่สองของการฝึก SkNN ประกอบด้วยการจัดเก็บองค์ประกอบของลำดับการฝึกในลักษณะเฉพาะ แต่ละองค์ประกอบของลำดับการฝึกจะถูกจัดเก็บไว้ในโหนดที่เกี่ยวข้องกับคลาสขององค์ประกอบก่อนหน้าในลำดับนั้น โดยองค์ประกอบแรกสุดจะถูกจัดเก็บไว้ในโหนดSTART

การติดป้ายกำกับลำดับอินพุตโดย SkNN ประกอบด้วยการค้นหาลำดับการเปลี่ยนผ่านในกราฟ โดยเริ่มต้นจากโหนดSTARTการเปลี่ยนผ่านแต่ละครั้งสอดคล้องกับองค์ประกอบเดียวของลำดับอินพุต ดังนั้น ป้ายกำกับของแต่ละองค์ประกอบจึงถูกกำหนดให้เป็นป้ายกำกับโหนดเป้าหมายของการเปลี่ยนผ่าน ต้นทุนของเส้นทางถูกกำหนดให้เป็นผลรวมของการเปลี่ยนผ่านทั้งหมด โดยต้นทุนของการเปลี่ยนผ่านจากโหนดAไปยังโหนดBคือระยะทางจากองค์ประกอบลำดับอินพุตปัจจุบันไปยังองค์ประกอบที่ใกล้ที่สุดของคลาสBซึ่งเก็บไว้ในโหนดAการกำหนดเส้นทางที่เหมาะสมที่สุดอาจทำได้โดยใช้อัลกอริทึม Viterbi ที่ดัดแปลงแล้ว (โดยที่ผลรวมของระยะทางจะถูกทำให้มีค่าน้อยที่สุดซึ่งแตกต่างจากอัลกอริทึมดั้งเดิมที่ เพิ่มค่าผลคูณของความน่าจะเป็น ให้สูงสุด )

• ตัวอย่างการนำไปใช้