Логическая закономерность

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск

Vokov (Обсуждение | вклад)
(Новая: '''Логическая закономерность''' (правило, rule) — в задачах классификации — легко интерп...)
К следующему изменению →

Версия 20:45, 18 мая 2008

Логическая закономерность (правило, rule) — в задачах классификации — легко интерпретируемое условие, выделяющее из обучающей выборки достаточно много объектов какого-то одного класса и практически не выделяющее объекты остальных классов. Логические закономерности являются элементарными «строительными блоками» для широкого класса логических алгоритмов классификации, называемых также алгоритмами индукции правил (rule induction).

Содержание

Определения и обозначения

Пусть X — пространство объектов, Y — множество имён классов, X^m = (x_i,y_i)_{i=1}^mобучающая выборка.

Пусть y\in Y — фиксированнный класс. Объекты этого класса будем называть положительными (positive examples); объекты остальных классов — отрицательными (negative examples).

Говорят, что предикат \phi: X\to\{0,1\} выделяет или покрывает (cover) объект x, если \phi(x)=1. Закономерностью называется предикат \phi(x), выделяющий много положительных объектов и мало отрицательных. К закономерностям предъявляется три основных требования: интерпретируемость, информативность и взаимодополняемость.

Интерпретируемость

Предикат \phi(x) должен описываться простой логической формулой, понятной экспертам в данной прикладной области. На практике логические закономерности часто ищут в виде конъюнкций небольшого числа элементарных высказываний. Именно в такой форме люди привыкли выражать свой житейский и профессиональный опыт.

Пример (из области медицины). Решается вопрос о целесообразности хирургической операции. Закономерность: «если возраст пациента выше 60 лет и ранее он перенёс инфаркт, то операцию не делать — риск отрицательного исхода велик и составляет 60%».

Пример (из области банковской деятельности). Решается вопрос о выдаче кредита. Закономерность: «если заёмщик указал в анкете свой домашний телефон, и его зарплата превышает $1000 в месяц, и сумма кредита не превышает $10000, то кредит можно выдать — риск невозврата мал и составляет 10%».

Наряду с конъюнкциями используются и другие формы интерпретируемых закономерностей: шары, гиперплоскости, ядра.

Информативность

Введём четыре величины:

P_y = \sum\nolimits_{i=1}^m [y_i=y] — число положительных объектов в выборке X^m;
N_y = \sum\nolimits_{i=1}^m [y_i\neq y] — число отрицательных объектов в выборке X^m;
p_y(\phi) = \sum\nolimits_{i=1}^m [\phi(x_i)=1] [y_i=y] — число положительных объектов, выделяемых правилом \phi;
n_y(\phi) = \sum\nolimits_{i=1}^m [\phi(x_i)=1] [y_i\neq y] — число отрицательных объектов, выделяемых правилом \phi;

Интуитивно предикат \phi(x) является информативным, если одновременно p_y(\phi)\to \max и n_y(\phi)\to \min. Формализовать это интуитивное требование не так просто. Можно показать на примерах, что «наивные» попытки определить информативность предиката на выборке как функцию I\bigl(p_y(\phi),n_y(\phi)\bigr) приводят к неадекватным результатам. Существует несколько различных формальных определений информативности, в том числе логическое, статистическое, энтропийное.

Взаимодополняемость

Набор закономерностей в совокупности должен образовывать алгоритм классификации a:\:X\to Y. Чаще всего логический классификатор представляет собой взвешенную сумму закономерностей:

a(x) = \arg\max_{y\in Y} \sum_{t=1}^T_y \alpha_{yt} \phi_{yt}(x),

где \alpha_{yt} — неотрицательные веса. В данной форме могут быть представлены также решающие списки и деревья.

Требование взаимодополняемости закономерностей означает, что для любого объекта выборки должна найтись закономерность \phi_{yt}, выделяющая данный объект. В противном случае алгоритм a(x) не сможет классифицировать объект, то есть произойдёт отказ от классификации.

Ссылки

Литература

Личные инструменты