ทฤษฎีบทของ Coverเป็นข้อความในทฤษฎีการเรียนรู้เชิงคำนวณ และเป็นหนึ่งในแรงจูงใจทางทฤษฎีหลักสำหรับการใช้ระเบียบ วิธีเคอร์เนลแบบไม่เชิงเส้นใน แอปพลิเคชัน การเรียนรู้ของเครื่อง ชื่อ นี้ตั้งตามชื่อของ Thomas M. Coverนักทฤษฎีสารสนเทศผู้กล่าวถึงทฤษฎีบทนี้ในปี 1965 โดยเรียกมันว่าทฤษฎีบทฟังก์ชันการนับ

ให้จำนวนของเซตที่แยกได้ด้วยเส้นตรงแบบเอกพันธุ์${\displaystyle N}$คะแนนใน${\displaystyle d}$มิติจะถูกกำหนดเป็นฟังก์ชันการนับ${\displaystyle C(N,d)}$จำนวนจุด${\displaystyle N}$และมิติ${\displaystyle d}$ทฤษฎีบทนี้กล่าวว่า${\displaystyle C(N,d)=2\sum _{k=0}^{d-1}{\binom {N-1}{k}}}$.

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

ฟังก์ชัน${\displaystyle C(N,d)}$ดำเนินไปตามระบอบที่แตกต่างกันสองแบบ ขึ้นอยู่กับความสัมพันธ์ระหว่าง${\displaystyle N}$และ${\displaystyle d}$.

• สำหรับ${\displaystyle N\leq d+1}$ฟังก์ชันนั้นเป็นฟังก์ชันเลขชี้กำลังใน${\displaystyle N}$โดยพื้นฐานแล้วหมายความว่า ชุดจุดที่มีป้ายกำกับ ใดๆที่อยู่ในตำแหน่งทั่วไปและมีจำนวนไม่เกินมิติ + 1 นั้นสามารถแยกได้ด้วยเส้นตรง ในศัพท์เฉพาะทางกล่าวกันว่า ตัวจำแนกเชิงเส้นจะทำลายชุดจุดใดๆ ก็ตามที่มี${\displaystyle N\leq d+1}$ปริมาณจำกัดนี้ยังเป็นที่รู้จักกันในชื่อมิติ Vapnik-Chervonenkisของตัวจำแนกเชิงเส้น อีกด้วย

• สำหรับ${\displaystyle N>d+1}$ฟังก์ชันการนับจะเริ่มเติบโตในอัตราที่น้อยกว่าแบบเลขชี้กำลัง ซึ่งหมายความว่า เมื่อกำหนดตัวอย่างที่มีขนาดคงที่แล้ว${\displaystyle N}$สำหรับมิติที่ใหญ่ขึ้น${\displaystyle d}$มีความเป็นไปได้มากขึ้นที่ชุดจุดที่มีป้ายกำกับแบบสุ่มจะสามารถแยกออกจากกันได้ด้วยเส้นตรง ในทางกลับกัน สำหรับมิติที่คงที่ จำนวนชุดจุดแบบสุ่มที่สามารถแยกออกจากกันได้ด้วยเส้นตรงจะน้อยลงสำหรับขนาดตัวอย่างที่ใหญ่ขึ้น หรือกล่าวอีกนัยหนึ่ง ความน่าจะเป็นที่จะพบตัวอย่างที่สามารถแยกออกจากกันได้ด้วยเส้นตรงจะลดลงตามขนาดตัวอย่างที่ใหญ่ขึ้น${\displaystyle N}$.

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

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

โดยการอุปมานด้วยความสัมพันธ์แบบเวียนเกิด$${\displaystyle C(N+1,d)=C(N,d)+C(N,d-1)}$$เพื่อแสดงให้เห็นว่า โดยที่ค่าคงที่${\displaystyle N}$เพิ่มขึ้น${\displaystyle d}$อาจเปลี่ยนชุดจุดจากที่ไม่สามารถแยกออกจากกันได้ให้กลายเป็นที่ที่สามารถแยกออกจากกันได้ โดยอาจใช้ การแมปแบบกำหนดได้ : สมมติว่ามี${\displaystyle N}$จุดต่างๆ ยกจุดเหล่านั้นขึ้นไปวางบนจุดยอดของซิมเพล็กซ์ใน${\displaystyle N-1}$พื้นที่จริงมิติ เนื่องจากทุกการแบ่งตัวอย่างออกเป็นสองชุดสามารถแยกได้ด้วยตัวคั่นเชิงเส้นคุณสมบัตินี้จึงเป็นไปตามนั้น

บทความปี 1965 ประกอบด้วยทฤษฎีบทหลายข้อ

ทฤษฎีบทที่ 6: ให้${\textstyle X\cup \{y\}=\left\{x_{1},x_{2},\cdots ,x_{N},y\right\}}$อยู่ใน${\textstyle \phi }$-ตำแหน่งทั่วไปใน${\textstyle d}$-พื้นที่ ที่ซึ่ง${\textstyle \phi =\left(\phi _{1},\phi _{2},\cdots ,\phi _{d}\right)}$. แล้ว${\textstyle y}$มีความคลุมเครือเกี่ยวกับเรื่องนี้${\textstyle C(N,d-1)}$ความแตกต่างสองประการของ${\textstyle X}$เมื่อเทียบกับชั้นเรียนทั้งหมด${\textstyle \phi }$-พื้นผิว

บทสรุป: ถ้าแต่ละข้อต่อไปนี้${\textstyle \phi }$- การแบ่งแยกแบบทวิภาคที่แยกออกจากกันได้ของ${\textstyle X}$หากมีความน่าจะเป็นเท่ากัน ความน่าจะเป็นก็จะเท่ากัน${\textstyle A(N,d)}$ที่${\textstyle y}$มีความคลุมเครือเกี่ยวกับความสุ่ม${\textstyle \phi }$-การแบ่งแยกแบบทวิภาคที่แยกออกจากกันได้ของ${\textstyle X}$เป็น${\displaystyle {\frac {C(N,d-1)}{C(N,d)}}}$.

ถ้า${\displaystyle N/d\to \beta }$จากนั้นที่ขีดจำกัดของ${\displaystyle N\to \infty }$ความน่าจะเป็นนี้จะลู่เข้าสู่${\displaystyle \lim _{N}A(N,d)={\begin{cases}1,&0\leq \beta \leq 2\\{\frac {1}{\beta -1}},&\beta \geq 2\end{cases}}}$.

สิ่งนี้สามารถตีความได้ว่าเป็นข้อจำกัดของความจุหน่วยความจำของหน่วยเพอร์เซปตรอนเดี่ยว${\displaystyle d}$คือจำนวนน้ำหนักอินพุตที่ป้อนเข้าสู่เพอร์เซปตรอน สูตรระบุว่าที่ขีดจำกัดของค่ามาก${\displaystyle d}$เพอร์เซปตรอนน่าจะสามารถจดจำได้มากถึง${\displaystyle 2d}$ป้ายกำกับแบบไบนารี แต่แทบจะแน่นอนว่าไม่สามารถจดจำอะไรได้มากกว่านั้น( MacKay 2003 , หน้า490) 

• เครื่องสนับสนุนเวกเตอร์
• วิธีการเคอร์เนล