機械学習の初歩

機械学習にもいろいろな種類があるが、PBDに関係するのは主として次の二つ。

教示学習

教師は体系的な知識を与える。学習者はそれを必要に応じて変形して利用する。例えば、基本的な公式を習い、応用問題を解く。

例示学習（帰納学習）

教師は、学習すべき対象の具体例を示し、学習者はそれを帰納的に一般化する

例示学習

事例空間

個々の具体例の集合

概念

事例空間を、正の（あてはまる）部分集合と負の（あてはまらない）部分集合に分割する記述

正事例

学習すべき概念に当てはまる事例

負事例

学習すべき概念に当てはまらない事例

汎化

正事例（または概念）から、より一般的な概念を導くこと

例示学習とは、与えられたすべての正事例を含み、負事例を含まないような概念を見つけること。

例えば、記述方法として論理式を採用すると、事例空間はgroundな論理式の集合、概念空間は任意の論理式の集合になる。概念空間内の特殊/一般の関係は、logical consequence、subsumptionなどで定義することができる。

Subsumption と汎化

節$A,B$と代入$\theta$があり、$A\theta \subseteq B$が成り立つ時、$A$は$B$を包摂する(subsume)と言う。

概念空間をsubsumptionによって半順序集合にした場合、汎化の手続きは次のようになる。

1. 定数を変数で置き換える（代入の逆）
2. リテラルを削除する