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

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

Версия от 20:45, 18 мая 2008; Vokov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Логическая закономерность (правило, 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)$ не сможет классифицировать объект, то есть произойдёт отказ от классификации.