コンセプトクラス

数学における計算学習理論では、領域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 }$

参考文献

1. Chase, H., & Freitag, J. (2018). モデル理論と機械学習. arXiv プレプリント arXiv:1801.06566.
2. Angluin, D. (2004). 「クエリの再考」(PDF) .理論計算機科学. 313 (2): 188– 191. doi :10.1016/j.tcs.2003.11.004.