コンセプトクラス

数学の計算学習理論では、領域X上の概念は、 X上の全ブール関数です。概念クラスは概念のクラスです。概念クラスは、計算学習理論の対象です。

概念クラスという用語は、おそらくほぼ正しい（PAC）学習に関連するモデル理論で頻繁に登場します。 ^[1]この設定では、集合Y を（分類器の出力）ラベルの集合として取り、X を例の集合とすると、例から分類器ラベルへのマップ（ここで、cはXのサブセット） 、c は概念であると言われます。概念クラスは、そのような概念のコレクションです。 ${\displaystyle c:X\to Y}$${\displaystyle Y=\{0,1\}}$ ${\displaystyle C}$

概念のクラスCが与えられたとき、サブクラスDが到達可能であるとは、サンプルsが存在し、 D がsの拡張であるCの概念を正確に含んでいる場合です。^[2]すべてのサブクラスが到達可能であるわけではありません。^{[2] [なぜ? ]}

サンプルは ^{[説明が必要]}からへの部分関数です。^[2]概念をその特性関数が にマッピングされることで、それはサンプルの特殊なケースになります。^[2]${\displaystyle s}$${\displaystyle X}$${\displaystyle \{0,1\}}$${\displaystyle X}$${\displaystyle \{0,1\}}$

2つのサンプルは、それらの定義域の共通部分で一致する場合、矛盾がないといえます。 ^[2] 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 X-Y}$
• シングルトン集合からなるサブクラスには到達できない。^{[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 }$