การจำแนกประเภทเพื่อนบ้านที่ใกล้ที่สุดที่มีระยะขอบขนาดใหญ่ ( LMNN ) ^{[ 1 ]} เป็นอัลกอริธึมการเรียนรู้เครื่องจักร เชิงสถิติ สำหรับการเรียนรู้เมตริกโดยจะเรียนรู้เมตริกเทียมที่ออกแบบมาสำหรับ การจำแนกประเภท เพื่อนบ้านที่ใกล้ที่สุดkตัว อัลกอริธึมนี้อิงตามการเขียนโปรแกรมเชิงกึ่งกำหนดซึ่งเป็นคลาสย่อยของการเพิ่มประสิทธิภาพแบบนูน

เป้าหมายของการเรียนรู้แบบมีผู้กำกับดูแล (โดยเฉพาะอย่างยิ่งการจำแนกประเภท) คือการเรียนรู้กฎการตัดสินใจที่สามารถจัดหมวดหมู่ข้อมูลตัวอย่างลงในคลาสที่กำหนดไว้ล่วงหน้า กฎเพื่อนบ้านที่ใกล้ที่สุดk ตัว (k-nearest neighbor) สมมติว่า มีชุดข้อมูลฝึกฝน ที่มีป้ายกำกับ (กล่าวคือ ทราบคลาสแล้ว) โดยจะจำแนกข้อมูลตัวอย่างใหม่ด้วยคลาสที่ได้จากการลงคะแนนเสียงส่วนใหญ่ของข้อมูลฝึกฝน (ที่มีป้ายกำกับ) ที่ใกล้ที่สุด k ตัว ความใกล้ชิดจะวัดด้วยเมตริก ที่กำหนดไว้ล่วงหน้า อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดที่มีขอบเขตขนาดใหญ่ (Large margin nearest neighbors) เป็นอัลกอริทึมที่เรียนรู้เมตริก (เสมือน) ระดับโลกนี้ในลักษณะที่มีผู้กำกับดูแล เพื่อปรับปรุงความแม่นยำในการจำแนกประเภทของกฎเพื่อนบ้านที่ใกล้ที่สุด k ตัว

แนวคิดหลักเบื้องหลัง LMNN คือการเรียนรู้เมตริกเสมือน (pseudometric) ที่ทำให้ข้อมูลทุกตัวในชุดข้อมูลฝึกฝนถูกล้อมรอบด้วยข้อมูลอย่างน้อย k ตัวที่มีป้ายกำกับคลาสเดียวกัน หากทำได้เช่นนี้ ข้อผิดพลาดแบบ leave-one-out (กรณีพิเศษของการตรวจสอบแบบ cross validation ) จะลดลงเหลือน้อยที่สุด สมมติให้ข้อมูลฝึกฝนประกอบด้วยชุดข้อมูลโดยที่เซตของหมวดหมู่คลาสที่เป็นไปได้คือ ${\displaystyle D=\{({\vec {x}}_{1},y_{1}),\dots ,({\vec {x}}_{n},y_{n})\}\subset R^{d}\times C}$${\displaystyle C=\{1,\dots ,c\}}$

อัลกอริทึมเรียนรู้มาตรวัดเทียมประเภทหนึ่ง

${\displaystyle d({\vec {x}}_{i},{\vec {x}}_{j})=({\vec {x}}_{i}-{\vec {x}}_{j})^{\top }\mathbf {M} ({\vec {x}}_{i}-{\vec {x}}_{j})}$.

เพื่อให้นิยามของเมตริกสมบูรณ์ เมทริกซ์จะต้องเป็น เมทริกซ์กึ่งบวก กำหนด (positive semi-definite ) เมตริกแบบยุคลิดเป็นกรณีพิเศษ โดยที่ คือเมทริกซ์เอกลักษณ์การวางนัยทั่วไปนี้มักถูกเรียก (อย่างผิดๆ) ว่าเมตริกแบบมาฮาลาโนบิส ${\displaystyle d(\cdot ,\cdot )}$${\displaystyle \mathbf {M} }$${\displaystyle \mathbf {M} }$

ภาพที่ 1 แสดงให้เห็นถึงผลกระทบของเมตริกภายใต้ค่าต่างๆวงกลมสองวงแสดงถึงเซตของจุดที่มีระยะห่างเท่ากันจากจุดศูนย์กลางในกรณีของระบบพิกัดยุคลิด เซตนี้จะเป็นวงกลม ในขณะที่ภายใต้เมตริกที่ปรับปรุงแล้ว (มาฮาลาโนบิส) เซตนี้จะกลายเป็นทรงรี ${\displaystyle \mathbf {M} }$${\displaystyle {\vec {x}}_{i}}$

อัลกอริทึมนี้แยกแยะข้อมูลพิเศษออกเป็นสองประเภท ได้แก่เพื่อนบ้านเป้าหมายและผู้แอบอ้าง

ก่อนเริ่มการเรียนรู้ จะมีการเลือกเพื่อนบ้านเป้าหมาย โดยแต่ละอินสแตนซ์จะมีเพื่อนบ้านเป้าหมายที่แตกต่างกัน อย่างแน่นอน ซึ่งทั้งหมดจะมีป้ายกำกับคลาสเดียวกันเพื่อนบ้านเป้าหมายคือจุดข้อมูลที่ควรจะกลายเป็นเพื่อนบ้านที่ใกล้ที่สุดภายใต้เมตริกที่เรียนรู้เราจะใช้สัญลักษณ์ แทนเซตของเพื่อนบ้านเป้าหมายสำหรับจุดข้อมูลหนึ่ง ๆ${\displaystyle {\vec {x}}_{i}}$${\displaystyle k}$${\displaystyle D}$${\displaystyle y_{i}}$${\displaystyle {\vec {x}}_{i}}$${\displaystyle N_{i}}$

จุดข้อมูลปลอมคือจุดข้อมูลอื่นที่มีป้ายกำกับคลาสต่างกัน (เช่น) ซึ่งเป็นหนึ่งในจุดข้อมูลเพื่อนบ้านที่ใกล้ที่สุดของ จุดข้อมูลนั้น ในระหว่างการเรียนรู้ อัลกอริทึมจะพยายามลดจำนวนจุดข้อมูลปลอมสำหรับข้อมูลทุกจุดในชุดข้อมูลฝึกฝนให้เหลือน้อยที่สุด ${\displaystyle {\vec {x}}_{i}}$${\displaystyle {\vec {x}__{j}}$${\displaystyle y_{i}\neq y_{j}}$${\displaystyle {\vec {x}}_{i}}$

การหาเพื่อนบ้านที่ใกล้ที่สุดแบบมีขอบเขตขนาดใหญ่ (Large margin nearest neighbors) ปรับปรุงเมทริกซ์ด้วยความช่วยเหลือของการเขียนโปรแกรมเชิงกึ่งกำหนด (semidefinite programming ) วัตถุประสงค์มีสองประการคือ สำหรับทุกจุดข้อมูลเพื่อนบ้านเป้าหมายควรอยู่ใกล้และจุดปลอมควรอยู่ห่างไกลรูปที่ 1 แสดงผลของการปรับปรุงดังกล่าวในตัวอย่างประกอบ เมตริกที่เรียนรู้ทำให้เวกเตอร์อินพุตถูกล้อมรอบด้วยอินสแตนซ์การฝึกอบรมของคลาสเดียวกัน หากเป็นจุดทดสอบ ก็จะถูกจำแนกอย่างถูกต้องภายใต้กฎเพื่อนบ้านที่ใกล้ที่สุด ${\displaystyle \mathbf {M} }$${\displaystyle {\vec {x}}_{i}}$${\displaystyle {\vec {x}}_{i}}$${\displaystyle k=3}$

เป้าหมายการปรับปรุงประสิทธิภาพประการแรกบรรลุได้โดยการลดระยะห่างเฉลี่ยระหว่างอินสแตนซ์และเพื่อนบ้านเป้าหมายให้เหลือน้อยที่สุด

${\displaystyle \sum _{i,j\in N_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})}$.

เป้าหมายที่สองบรรลุได้โดยการลงโทษระยะห่างของผู้แอบอ้างที่อยู่ห่างออกไปน้อยกว่าหนึ่งหน่วยจากเพื่อนบ้านเป้าหมาย(และด้วยเหตุนี้จึงผลักพวกเขาออกไปจากบริเวณใกล้เคียงของ เป้าหมาย ) ค่าที่ได้ที่จะต้องลดให้เหลือน้อยที่สุดสามารถระบุได้ดังนี้: ${\displaystyle {\vec {x}__{l}}$${\displaystyle {\vec {x}__{j}}$${\displaystyle {\vec {x}}_{i}}$

${\displaystyle \sum _{i,j\in N_{i},l,y_{l}\neq y_{i}}[d({\vec {x}}_{i},{\vec {x}}_{j})+1-d({\vec {x}}_{i},{\vec {x}}_{l})]_{+}}$

ด้วยฟังก์ชันการสูญเสียแบบบานพับ (hinge loss function ) ซึ่งช่วยให้มั่นใจได้ว่าความใกล้เคียงของผู้แอบอ้างจะไม่ถูกลงโทษเมื่ออยู่นอกขอบเขต ขอบเขตที่มีขนาดหนึ่งหน่วยพอดีจะกำหนดขนาดของเมทริกซ์การเลือกค่าอื่นใดจะส่งผลให้มีการปรับขนาดใหม่ด้วยปัจจัย${\textstyle [\cdot ]_{+}=\max(\cdot ,0)}$${\displaystyle M}$${\displaystyle c>0}$${\displaystyle M}$${\displaystyle 1/c}$

ปัญหาการหาค่าเหมาะสมที่สุดขั้นสุดท้ายจึงเป็นดังนี้:

${\displaystyle \min _{\mathbf {M} }\sum _{i,j\in N_{i}}d({\vec {x}__{i},{\vec {x}__{j})+\lambda \sum _{i,j,l}\xi _{ijl}}$

${\displaystyle \forall _{i,j\in N_{i},l,y_{l}\neq y_{i}}}$

${\displaystyle d({\vec {x}}_{i},{\vec {x}}_{j})+1-d({\vec {x}}_{i},{\vec {x}}_{l})\leq \xi _{ijl}}$

${\displaystyle \xi _{ijl}\geq 0}$

${\displaystyle \mathbf {M} \succeq 0}$

ไฮเปอร์พารามิเตอร์คือค่าคงที่บวกบางค่า (โดยทั่วไปกำหนดผ่านการตรวจสอบแบบไขว้) ในที่นี้ ตัวแปร(พร้อมกับข้อจำกัดสองประเภท) จะเข้ามาแทนที่เทอมในฟังก์ชันต้นทุน พวกมันมีบทบาทคล้ายกับตัวแปรส่วนเกินเพื่อดูดซับขอบเขตของการละเมิดข้อจำกัดของอิมโพสเตอร์ ข้อจำกัดสุดท้ายทำให้มั่นใจได้ว่าเมทริกซ์นั้นเป็นเมทริกซ์กึ่งบวกแน่นอน ปัญหาการหาค่าเหมาะสมที่สุดเป็นตัวอย่างหนึ่งของการเขียนโปรแกรมกึ่งแน่นอน (SDP) แม้ว่า SDP มักจะมีความซับซ้อนในการคำนวณสูง แต่ SDP ตัวอย่างนี้สามารถแก้ไขได้อย่างมีประสิทธิภาพมากเนื่องจากคุณสมบัติทางเรขาคณิตพื้นฐานของปัญหา โดยเฉพาะอย่างยิ่ง ข้อจำกัดของอิมโพสเตอร์ส่วนใหญ่เป็นไปตามเงื่อนไขโดยธรรมชาติและไม่จำเป็นต้องบังคับใช้ในระหว่างการทำงาน (เช่น ชุดตัวแปรนั้นเบาบาง) เทคนิคการแก้ปัญหาที่เหมาะสมเป็นพิเศษคือ วิธี การชุดการทำงานซึ่งจะเก็บชุดข้อจำกัดขนาดเล็กที่บังคับใช้อย่างจริงจังและตรวจสอบข้อจำกัดที่เหลือ (ซึ่งน่าจะเป็นไปตามเงื่อนไข) เป็นครั้งคราวเพื่อให้แน่ใจว่าถูกต้อง ${\textstyle \lambda >0}$${\displaystyle \xi _{ijl}}$${\displaystyle \mathbf {M} }$${\displaystyle \xi _{ijl}}$

LMNN ได้รับการขยายไปยังเมตริกท้องถิ่นหลายตัวในเอกสารปี 2008 ^{[ 2 ]} การขยายนี้ช่วยปรับปรุงข้อผิดพลาดในการจำแนกประเภทได้อย่างมาก แต่เกี่ยวข้องกับปัญหาการเพิ่มประสิทธิภาพที่มีราคาแพงกว่า ในสิ่งพิมพ์ปี 2009 ของพวกเขาในวารสาร Journal of Machine Learning Research ^{[ 3 ]} Weinberger และ Saul ได้พัฒนาตัวแก้ปัญหาที่มีประสิทธิภาพสำหรับโปรแกรมกึ่งกำหนด ซึ่งสามารถเรียนรู้เมตริกสำหรับชุดข้อมูลตัวเลขเขียนด้วยมือ MNIST ได้ภายในเวลาไม่กี่ชั่วโมง โดยเกี่ยวข้องกับข้อจำกัดแบบคู่หลายพันล้านรายการ การใช้งาน Matlab แบบโอเพนซอร์ส มีให้ใช้งานฟรีที่หน้าเว็บของผู้เขียน

Kumal และคณะ^{[ 4 ]}ได้ขยายอัลกอริทึมเพื่อรวมความไม่แปรผันในท้องถิ่นเข้ากับการแปลงพหุนาม หลายตัวแปร และปรับปรุงการควบคุม

• การใช้งาน Matlab
• บทช่วยสอนเกี่ยวกับการเรียนรู้เมตริกซ์ ในงาน ICML 2010