คลาสแนวคิด

ในทฤษฎีการเรียนรู้เชิงคำนวณทางคณิตศาสตร์ แนวคิดบนโดเมน X คือฟังก์ชันบูลีนทั้งหมดบน X กลุ่มแนวคิดคือกลุ่มของแนวคิดต่างๆ กลุ่มแนวคิดเป็นหัวข้อหนึ่งของทฤษฎีการเรียนรู้เชิงคำนวณ

คำศัพท์เกี่ยวกับคลาสแนวคิดมักปรากฏในทฤษฎีแบบจำลองที่เกี่ยวข้องกับ การเรียนรู้ ที่ถูกต้องโดยประมาณ (PAC) ^{[ 1 ]}ในบริบทนี้ หากเราใช้เซตYเป็นเซตของป้ายกำกับ (ผลลัพธ์ของตัวจำแนก) และXเป็นเซตของตัวอย่าง แผนที่เช่น จากตัวอย่างไปยังป้ายกำกับของตัวจำแนก (โดยที่และโดยที่cเป็นเซตย่อยของX ) cจะถูกเรียกว่าเป็นแนวคิดคลาสแนวคิดจึงเป็นการรวบรวมแนวคิดดังกล่าว ${\displaystyle c:X\to Y}$${\displaystyle Y=\{0,1\}}$${\displaystyle C}$

เมื่อกำหนดคลาสของแนวคิดCแล้ว คลาสย่อยDจะสามารถเข้าถึงได้หากมีตัวอย่างs อยู่ ซึ่งDประกอบด้วยแนวคิดในCที่เป็นส่วนขยายของs อย่าง แน่นอน ^{[ 2 ]}ไม่ใช่ทุกคลาสย่อยจะสามารถเข้าถึงได้^{[ 2 ]}

ตัวอย่างคือฟังก์ชันบางส่วนจากไปยัง[ ^{2 ] การ}ระบุแนวคิดด้วยฟังก์ชันลักษณะเฉพาะที่แมปไปยังถือ เป็นกรณีพิเศษของตัวอย่าง^{[ 2 ]}${\displaystyle s}$${\displaystyle X}$${\displaystyle \{0,1\}}$${\displaystyle X}$${\displaystyle \{0,1\}}$

ตัวอย่างสองตัวอย่างจะสอดคล้องกันหากเห็นพ้องกันที่จุดตัดของโดเมน^{[ 2 ]}ตัวอย่างหนึ่งจะขยายตัวอย่างอีกตัวอย่างหนึ่งหากทั้งสองตัวอย่างสอดคล้องกันและโดเมนของตัวอย่างหนึ่งอยู่ในโดเมนของอีกตัวอย่าง หนึ่ง ^{[ 2 ]}${\displaystyle s'}$${\displaystyle s}$${\displaystyle s}$${\displaystyle s'}$

สมมติว่า. ดังนั้น: ${\displaystyle C=S^{+}(X)}$

• คลาสย่อยสามารถเข้าถึงได้ด้วยตัวอย่าง; ^{[ 2 ]}${\displaystyle \{\{x\}\}}$${\displaystyle s=\{(x,1)\}}$
• คลาสย่อยสามารถเข้าถึงได้ด้วยตัวอย่างที่แมปองค์ประกอบของไปยังศูนย์^{[ 2 ]}${\displaystyle S^{+}(Y)}$${\displaystyle Y\subseteq X}$${\displaystyle XY}$
• คลาสย่อยซึ่งประกอบด้วยเซตซิงเกิลตันไม่สามารถเข้าถึงได้^{[ 2 ]}${\displaystyle S(X)}$

ให้เป็นคลาสแนวคิดบางคลาส สำหรับแนวคิดใดๆเราเรียกแนวคิดนี้ว่า -ดีสำหรับจำนวนเต็มบวกถ้าสำหรับทุก อย่างน้อยของแนวคิดในเห็นด้วยกับบนการจำแนกประเภทของ[ ^{2 ] มิติ}ของลายนิ้วมือของคลาสแนวคิดทั้งหมดคือจำนวนเต็มบวกที่น้อยที่สุดซึ่งคลาสย่อยที่เข้าถึงได้ทุกคลาสจะมีแนวคิดที่เป็น-ดี สำหรับ คลาสย่อยนั้น ^{[ 2 ] ปริมาณนี้สามารถใช้เพื่อจำกัดจำนวนขั้นต่ำของการสอบถามความเท่าเทียมกันที่จำเป็นในการเรียน รู้}คลาสของแนวคิดตามอสมการ ต่อไปนี้ : [ ^{2 ]}${\displaystyle C}$${\displaystyle c\in C}$${\displaystyle 1/d}$${\displaystyle d}$${\displaystyle x\in X}$${\displaystyle 1/d}$${\displaystyle C}$${\displaystyle c}$${\displaystyle x}$${\displaystyle FD(C)}$${\displaystyle C}$${\displaystyle d}$${\displaystyle C'\subseteq C}$${\displaystyle 1/d}$${\textstyle FD(C)-1\leq \#EQ(C)\leq \lceil FD(C)\ln(|C|)\rceil }$