Индукция и дедукция. Алгоритм индуктивного обучения. Деревья решений

Виды машинного обучения:

«с учителем» (контролируемое обучение) – когда для каждого примера задается в явном виде значение признака его принадлежности некоторому классу ситуаций (классообразующего признака);

«без учителя» (неконтролируемое обучение) – когда по степени близости значений признаков классификации система сама выделяет классы ситуаций.

Дедукция – переход в процессе познания от общего знания о некотором классе предметов и явлений к знанию частному и единичному.

Индукция – это переход в процессе познания от частного знания к общему; от знания меньшей степени общности к знанию большей степени общности.

Обобщение примеров по принципу индукции сводится к выявлению подмножеств примеров, относящихся к одним и тем же классам, и определению для них значимых признаков.

Известным примером (рис.1 и рис.2) индуктивного обучения является подгонка функции от одной переменной к некоторым точкам из набора данных.

Примеры представляют собой пары (x, f(x)), где и x и f(x)– действительные числа. Выберем в качестве пространства гипотез – множество полиномов, имеющих степень не больше k, таких как5x2+2, x17-3x3. На рис.1 показаны значения, которые соответствуют некоторой прямой (полиному первой степени). Так как прямая согласуется со всеми данными, то она называется совместимой с гипотезой. На том же рис. 1 показан полином более высокой степени, который также совместим с этими данными. Это пример важной проблемы индуктивного обучения – выбору среди множества согласованных гипотез. Эта проблема может быть решена с использованием принципа “бритвы Оккама”, согласно которому предпочтение следует отдавать наиболее простой гипотезе, согласующейся с данными.

На рис. 2 показан второй набор данных, с которым нельзя точно совместить прямую линию. Для точного согласования с данным набором требуется полином четвертой степени с пятью параметрами. Возможно, что лучше согласовать этот набор данных с прямой линией, которая не будет точно совместимой, но позволит получать обоснованные предсказания. Принятие данного решения равносильно признанию недетерминированности искомой функции. При наличии недетерминированных функций неизбежно приходится искать компромисс между сложностью гипотезы и степенью ее согласованности с данными.

Возможность найти простую согласованную гипотезу зависит от выбранного пространства гипотез. На рис. 2 показано как тот же набор данных может быть точно согласован с простой функцией вида ax + b + csin(x). Задача обучения называется реализуемой, если Пространство гипотез содержит подходящую функцию, иначе она называется нереализуемой

Алгоритм индуктивного обучения:

• выбирается признак классификации из множества заданных;

• по значению выбранного признака множество примеров разбивается на подмножества;

• выполняется проверка, принадлежит ли каждое образовавшееся подмножество примеров одному подклассу. Если да, то процесс классификации заканчивается.

• Для подмножеств примеров с несовпадающим значением классообразующего признака процесс классификации продолжается, начиная с пункта 1. (Каждое подмножество примеров становится классифицирующим множеством).

Процесс классификации может быть представлен в виде дерева решений, в котором в промежуточных узлах находятся значения признаков последовательной классификации, а в конечных узлах – значения признака принадлежности определенному классу.

Пример построения дерева решений