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

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

ความซับซ้อนของตัวอย่างมีสองรูปแบบ:

• รูปแบบที่อ่อนแอจะกำหนดการกระจายตัวของอินพุตและเอาต์พุตที่เฉพาะเจาะจง
• รูปแบบที่เข้มงวดจะพิจารณาความซับซ้อนของการสุ่มตัวอย่างในกรณีที่เลวร้ายที่สุดเหนือการแจกแจงอินพุต-เอาต์พุตทั้งหมด

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

อย่างไรก็ตาม หากเราสนใจเฉพาะฟังก์ชันเป้าหมายเฉพาะกลุ่ม (เช่น เฉพาะฟังก์ชันเชิงเส้น) ความซับซ้อนของตัวอย่างจะมีค่าจำกัด และขึ้นอยู่กับมิติ VCของกลุ่มฟังก์ชันเป้าหมายแบบเชิง เส้น ^{[ 1 ]}

ให้เป็นปริภูมิที่เราเรียกว่าปริภูมิอินพุต และเป็นปริภูมิที่เราเรียกว่าปริภูมิเอาต์พุต และให้แทนผลคูณตัวอย่างเช่น ในบริบทของการจำแนกแบบไบนารี โดยทั่วไปแล้ว จะ เป็น ปริภูมิเวกเตอร์มิติจำกัด และคือเซต${\displaystyle X}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle X\times Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \{-1,1\}}$

กำหนดปริภูมิสมมติฐานของฟังก์ชันอัลกอริทึมการเรียนรู้บนปริภูมิ สมมติฐานนี้ คือแผนที่ที่คำนวณได้จากปริภูมิ สมมติฐานไป ยังปริภูมิสมมติฐาน กล่าวอีกนัยหนึ่งคือ เป็นอัลกอริทึมที่รับอินพุตเป็นลำดับจำกัดของตัวอย่างการฝึกอบรม และส่งออกฟังก์ชันจากปริภูมิ สมมติฐานไป ยัง ปริภูมิสมมติฐาน อัลกอริทึมการเรียนรู้ทั่วไป ได้แก่การลดความเสี่ยงเชิงประจักษ์โดยไม่มีหรือมีตัวควบคุมแบบทิโคนอฟ ${\displaystyle {\mathcal {H}}}$${\displaystyle h\colon X\to Y}$${\displaystyle {\mathcal {H}}}$${\displaystyle Z}$${\displaystyle {\mathcal {H}}}$${\displaystyle X}$${\displaystyle Y}$

กำหนดฟังก์ชันความสูญเสียเช่น ฟังก์ชันความสูญเสียกำลังสองโดยที่. สำหรับการแจกแจงที่กำหนดบนความเสี่ยงที่คาดหวังของสมมติฐาน (ฟังก์ชัน) คือ ${\displaystyle {\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}}$${\displaystyle {\mathcal {L}}(y,y')=(yy')^{2}}$${\displaystyle h(x)=y'}$${\displaystyle \rho }$${\displaystyle X\times Y}$${\displaystyle h\in {\mathcal {H}}}$

${\displaystyle {\mathcal {E}}(h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}(h(x),y)\,d\rho (x,y)}$

ในการตั้งค่าของเรา เรามีโดยที่เป็นอัลกอริธึมการเรียนรู้ และเป็นลำดับของเวกเตอร์ซึ่งถูกสุ่มอย่างอิสระจากกำหนดชุด ความเสี่ยงที่เหมาะสมที่สุด สำหรับแต่ละขนาดตัวอย่างเป็นตัวแปรสุ่มและขึ้นอยู่กับตัวแปรสุ่มซึ่งถูกสุ่มจาก1 การแจกแจงอัลกอริธึมเรียกว่าสอดคล้องกันหากลู่เข้าสู่ ในเชิงความน่าจะเป็นกล่าวอีกนัยหนึ่ง สำหรับทุกจะมีจำนวนเต็มบวก อยู่เช่นนั้น สำหรับทุกขนาดตัวอย่างเราจะมี ${\displaystyle h={\mathcal {A}}(S_{n})}$${\displaystyle {\mathcal {A}}}$${\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}$${\displaystyle \rho }$$${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).}$$${\displaystyle h_{n}={\mathcal {A}}(S_{n})}$${\displaystyle n}$${\displaystyle h_{n}}$${\displaystyle S_{n}}$${\displaystyle \rho ^{n}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {E}}(h_{n})}$${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$${\displaystyle \epsilon ,\delta >0}$${\displaystyle N}$${\displaystyle n\geq N}$

$${\displaystyle \Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .}$$ความซับซ้อนของตัวอย่างของคือค่าต่ำสุดที่เงื่อนไขนี้เป็นจริง โดยเป็นฟังก์ชันของและเราเขียนความซับซ้อนของตัวอย่างเป็นเพื่อเน้นว่าค่านี้ขึ้นอยู่กับและถ้าไม่สอดคล้องกันเราจะกำหนดถ้ามีอัลกอริทึมสำหรับ ที่มีค่าจำกัด เราจะกล่าวว่าปริภูมิสมมติฐานนั้นสามารถเรียนรู้ได้ ${\displaystyle {\mathcal {A}}}$${\displaystyle N}$${\displaystyle \rho ,\epsilon }$${\displaystyle \delta }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle N}$${\displaystyle \rho ,\epsilon }$${\displaystyle \delta }$${\displaystyle {\mathcal {A}}}$${\displaystyle N(\rho ,\epsilon ,\delta )=\infty }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle {\mathcal {H}}}$

กล่าวอีกนัยหนึ่ง ความซับซ้อนของตัวอย่างกำหนดอัตราความสอดคล้องของอัลกอริทึม: เมื่อกำหนดความแม่นยำและความเชื่อ มั่นที่ต้องการ แล้ว จำเป็นต้องสุ่มตัวอย่างจุดข้อมูลเพื่อให้แน่ใจว่าความเสี่ยงของฟังก์ชันเอาต์พุตอยู่ในช่วงที่ดีที่สุดที่เป็นไปได้ โดยมีความน่าจะเป็นอย่างน้อย^{[ 2 ]}${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle \epsilon }$${\displaystyle \delta }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle \epsilon }$${\displaystyle 1-\delta }$

ในการเรียนรู้แบบประมาณที่ถูกต้อง (PAC) นั้นเราจะพิจารณาว่าความซับซ้อนของตัวอย่างเป็นพหุนามหรือไม่ กล่าวคือถูกจำกัดด้วยพหุนามในและ หรือไม่ ถ้าเป็นพหุนามสำหรับอัลกอริธึมการเรียนรู้บางอย่าง เราจะกล่าวว่าพื้นที่สมมติฐาน นั้นสามารถเรียนรู้แบบ PAC ได้นี่เป็นแนวคิดที่แข็งแกร่งกว่าการแค่เรียนรู้ได้ ${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle 1/\epsilon }$${\displaystyle 1/\delta }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle {\mathcal {H}}}$

อาจมีคำถามว่ามีอัลกอริธึมการเรียนรู้ใดบ้างที่ทำให้ความซับซ้อนของตัวอย่างมีค่าจำกัดในความหมายที่เข้มงวด กล่าวคือ มีขอบเขตจำกัดของจำนวนตัวอย่างที่จำเป็นเพื่อให้อัลกอริธึมสามารถเรียนรู้การกระจายใดๆ บนพื้นที่อินพุต-เอาต์พุตด้วยข้อผิดพลาดเป้าหมายที่กำหนดไว้ กล่าวอย่างเป็นทางการมากขึ้น อาจถามว่ามีอัลกอริธึมการเรียนรู้ใดบ้างที่ทำให้สำหรับ ทุกค่า มีจำนวนเต็มบวก อยู่ค่าหนึ่งที่ทำให้สำหรับทุกค่าเรามี ${\displaystyle {\mathcal {A}}}$${\displaystyle \epsilon ,\delta >0}$${\displaystyle N}$${\displaystyle n\geq N}$

$${\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}$$โดย ที่ดังที่กล่าวมาข้างต้นทฤษฎีบทไม่มีอาหารกลางวันฟรีกล่าวว่า หากไม่มีข้อจำกัดเกี่ยวกับพื้นที่สมมติฐานกรณีนี้จะไม่เป็นเช่นนั้น กล่าวคือ จะมีการกระจาย "ไม่ดี" อยู่เสมอ ซึ่งความซับซ้อนของตัวอย่างมีขนาดใหญ่มากตามอำเภอใจ^{[ 1 ]}${\displaystyle h_{n}={\mathcal {A}}(S_{n})}$${\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}$${\displaystyle {\mathcal {H}}}$

ดังนั้น เพื่อที่จะกล่าวถึงอัตราการลู่เข้าของปริมาณดังกล่าว จำเป็นต้องทำอย่างใดอย่างหนึ่งดังต่อไปนี้ $${\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}$$

• จำกัดขอบเขตของพื้นที่การกระจายความน่าจะเป็นเช่น ผ่านวิธีการเชิงพารามิเตอร์ หรือ${\displaystyle \rho }$
• จำกัดขอบเขตของสมมติฐานเช่นเดียวกับในแนวทางที่ไม่ขึ้นกับการกระจายตัวของข้อมูล${\displaystyle {\mathcal {H}}}$

แนวทางหลังนำไปสู่แนวคิดต่างๆ เช่นมิติ VCและความซับซ้อนของ Rademacherซึ่งควบคุมความซับซ้อนของพื้นที่พื้นที่สมมติฐานที่เล็กกว่าจะทำให้เกิดอคติมากขึ้นในกระบวนการอนุมาน ซึ่งหมายความว่าอาจมากกว่าความเสี่ยงที่ดีที่สุดที่เป็นไปได้ในพื้นที่ที่ใหญ่กว่า อย่างไรก็ตาม การจำกัดความซับซ้อนของพื้นที่สมมติฐานทำให้เป็นไปได้ที่อัลกอริทึมจะสร้างฟังก์ชันที่สอดคล้องกันอย่างสม่ำเสมอมากขึ้น การแลกเปลี่ยนนี้ทำให้เกิดแนวคิดของ การ ทำให้เป็นระเบียบ^{[ 2 ]}${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$

นี่คือทฤษฎีบทจากทฤษฎี VCที่ระบุว่าข้อความสามข้อต่อไปนี้มีความสมมูลกันสำหรับปริภูมิสมมติฐาน: ${\displaystyle {\mathcal {H}}}$

1. ${\displaystyle {\mathcal {H}}}$สามารถเรียนรู้ได้ด้วย PAC
2. มิติ VC ของมีค่าจำกัด${\displaystyle {\mathcal {H}}}$
3. ${\displaystyle {\mathcal {H}}}$เป็นชั้นเรียน Glivenko-Cantelliที่ เป็นเอกภาพ

วิธีนี้ช่วยพิสูจน์ได้ว่าพื้นที่สมมติฐานบางอย่างสามารถเรียนรู้ได้ด้วย PAC และโดยนัยแล้วสามารถเรียนรู้ได้

${\displaystyle X=\mathbb {R} ^{d},Y=\{-1,1\}}$และให้เป็นปริภูมิของฟังก์ชันเชิงเส้นบนนั่นคือ ฟังก์ชันในรูปแบบสำหรับบางค่านี่คือปัญหาการเรียนรู้การจำแนกเชิงเส้นที่มีการชดเชย ตอนนี้ จุดสี่จุดที่อยู่บนระนาบเดียวกันในรูปสี่เหลี่ยมจัตุรัสไม่สามารถถูกทำลายโดยฟังก์ชันเชิงเส้นใดๆ ได้ เนื่องจากไม่มีฟังก์ชันเชิงเส้นใดที่จะเป็นบวกบนจุดยอดสองจุดที่อยู่ตรงข้ามกันในแนวทแยงมุมและเป็นลบบนจุดยอดอีกสองจุดที่เหลือ ดังนั้น มิติ VC ของคือดังนั้นจึงมีค่าจำกัด จากลักษณะเฉพาะของคลาสที่เรียนรู้ได้ด้วย PAC ข้างต้น จึงสรุปได้ว่าสามารถเรียนรู้ได้ด้วย PAC และโดยนัยแล้ว สามารถเรียนรู้ได้เช่นกัน ${\displaystyle {\mathcal {H}}}$${\displaystyle X}$${\displaystyle x\mapsto \langle w,x\rangle +b}$${\displaystyle w\in \mathbb {R} ^{d},b\in \mathbb {R} }$${\displaystyle {\mathcal {H}}}$${\displaystyle d+1}$${\displaystyle {\mathcal {H}}}$

สมมติว่าเป็นคลาสของฟังก์ชันไบนารี (ฟังก์ชันไปยัง) จากนั้นสามารถเรียนรู้แบบ -PAC ได้ด้วยตัวอย่างขนาด: ^{[ 3 ]} โดยที่คือมิติ VCของ ยิ่งไปกว่านั้น อัลกอริทึมการเรียนรู้แบบ -PAC ใดๆ สำหรับ จะต้องมีความซับซ้อนของตัวอย่าง: ^{[ 4 ]} ดังนั้น ความซับซ้อนของตัวอย่างจึงเป็นฟังก์ชันเชิงเส้นของมิติ VCของพื้นที่สมมติฐาน ${\displaystyle {\mathcal {H}}}$${\displaystyle \{0,1\}}$${\displaystyle {\mathcal {H}}}$${\displaystyle (\epsilon ,\delta )}$$${\displaystyle N=O{\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}$$${\displaystyle VC({\mathcal {H}})}$${\displaystyle {\mathcal {H}}}$${\displaystyle (\epsilon ,\delta )}$${\displaystyle {\mathcal {H}}}$$${\displaystyle N=\Omega {\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}$$

สมมติว่าเป็นคลาสของฟังก์ชันค่าจริงที่มีช่วงในแล้วสามารถเรียนรู้แบบ -PAC ได้โดยมีตัวอย่างขนาด: ^{[ 5 ] [ 6 ]} โดยที่คือมิติเสมือนของ Pollard ของ${\displaystyle {\mathcal {H}}}$${\displaystyle [0,T]}$${\displaystyle {\mathcal {H}}}$${\displaystyle (\epsilon ,\delta )}$$${\displaystyle N=O{\bigg (}T^{2}{\frac {PD({\mathcal {H}})\ln {T \over \epsilon }+\ln {1 \over \delta }}{\epsilon ^{2}}}{\bigg )}}$$${\displaystyle PD({\mathcal {H}})}$${\displaystyle {\mathcal {H}}}$

นอกจากการตั้งค่าการเรียนรู้แบบมีผู้กำกับดูแลแล้ว ความซับซ้อนของตัวอย่างยังเกี่ยวข้องกับปัญหาการเรียนรู้แบบกึ่งมีผู้กำกับ ดูแล รวมถึง การเรียนรู้แบบแอคทีฟ [ ^{7 ] ซึ่ง}อัลกอริทึมสามารถขอป้ายกำกับสำหรับอินพุตที่เลือกไว้โดยเฉพาะเพื่อลดต้นทุนในการรับป้ายกำกับจำนวนมาก แนวคิดของความซับซ้อนของตัวอย่างยังปรากฏในการเรียนรู้แบบเสริมแรง [ ^{8 ] การเรียน รู้}แบบออนไลน์และอัลกอริทึมแบบไม่มีผู้กำกับดูแล เช่น สำหรับ การเรียน รู้พจนานุกรม^{[ 9 ]}

ความซับซ้อนของตัวอย่างที่สูงหมายความว่าต้องใช้การคำนวณจำนวนมากในการดำเนิน การ ค้นหาต้นไม้แบบมอนเตคาร์โล^{[ 10 ]}ซึ่งเทียบเท่ากับ การค้นหา แบบบรูทฟอร์ซที่ไม่มีแบบจำลองในพื้นที่สถานะ ในทางตรงกันข้าม อัลกอริทึมที่มีประสิทธิภาพสูงมีความซับซ้อนของตัวอย่างต่ำ^{[ 11 ]}เทคนิคที่เป็นไปได้สำหรับการลดความซับซ้อนของตัวอย่าง ได้แก่การเรียนรู้เมตริก^{[ 12 ]}และการเรียนรู้แบบเสริมแรงตามแบบจำลอง^{[ 13 ]}

• การเรียนรู้เชิงรุก (การเรียนรู้ของเครื่องจักร)