§ 43. Логический анализ методов извлечения знаний

В данном параграфе проводится логический анализ методов Machine Learning и KDD&DM. Показывается, что если методы не основаны на теории измерений, то для них возникает проблема адекватности – доказательство инвариантности метода относительно допустимых преобразований шкал. В противном случае метод может давать различные результаты в зависимости от того в каких единицах измерения представлены данные. Вводится определение инвариантности метода относительно выбора числовых представлений для данных. Выделяется логическая составляющая данных. Показывается, как для любого метода Machine Learning и KDD&DM можно получить его логический аналог, для которого не возникает проблема инвариантности.

В результате проведенного анализа показывается, как для каждого Machine Learning и KDD&DM можно выделить:

- тип данных с которыми работает KDD&DM-метод в виде многосортной эмпирической системы;

- онтологию метода в виде множества отношений и операций, в которых записаны данные и представлены гипотезы метода;

- тип знаний метода как класс правил, которые проверяет метод.

Дадим определение инвариантности метода. Для этого представим числовые методы, как это показано на рис 8 :

- W = {w} – обучающая выборка;

- X(w) = (x₁, …, x_n) – набор значений из n признаков для каждого объекта обучения;

- Y(w) – целевое значение признака для каждого объекта обучения w;

KDD&DM метод M в результате обучения на обучающей выборке {X(w)}, wÎW, порождает решающее правило

J = M({X(w)}),

которое предсказывает целевые значения признака Y(w). Например, рассмотрим объект w с неизвестным значением Y(w), но известными значениями признаков X(w), тогда

J(X(w)) ~ Y(w),

где J(X(w)) является значением сгенерированным правилом J, и ~ приблизительное равенство. Решающее правило J может быть алгебраическим или логическим выражением, решающим деревом, нейронной сетью или гибридным алгоритмом.

Для признаков (x₁, …, x_n, Y) существуют эмпирические системы A₁, …, A_n, B, имеющие соответствующие группы преобразований g₁, …, g_n, g. Группа преобразований для всех признаков определяется как группа G = g₁ ´ … ´ g_n ´ g.

Рис 8.

Инвариантность KDD&DM-метода M относительно группы преобразований G определяется так, что для любого преобразования gÎG решающее правило обнаруживаемое методом М должно быть одним и тем же в том смысле, что принимаемые на объектах wÎW решения совпадают, т.е. решающие правила J = M({áX(w), Y(w)ñ}) и J_g = M({ágX(w), gY(w)ñ}), полученные методом М по преобразованной {ágX(w), gY(w)ñ} и не преобразованной {áX(w), Y(w)ñ} выборке должны давать одни и те же решения для любых объектов wÎW

J_g(g(X(w))) = g(J(X(w))),

J = M({áX(w), Y(w)ñ}), J_g = M({ágX(w), gY(w)ñ}).

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

Инвариантность метода тесно связана с интерпретируемостью его результатов. Если метод не инвариантен, то его результаты не могут быть полностью интерпретируемы. Интерпретируемость результатов означает их интерпретируемость в системе понятий предметной области.

Эмпирические системы A₁, …, A_n, B признаков, по определению, интерпретируемы в системе понятий предметной области. Методы KDD&DM очевидно инвариантны, если они используют в своей работе только интерпретируемую информацию эмпирических систем A₁, …, A_n, B и обнаруживают решающие правила J, являющиеся логическими выражениями в терминах эмпирических систем.

Покажем, как из любого метода KDD&DM можно извлечь инвариантный метод M : {X(w)} ® J. Проанализируем метод M с точки зрения ограничений KDD&DM-методов 1–3. Определим многосортную эмпирическую систему A(W) как произведение эмпирических систем A₁, …, A_n, B. Эмпирическая система A(W) содержит всю интерпретируемую информацию относительно обучающей выборки W. Обозначим через W ® A(W) преобразование выборки в многосортную эмпирическую систему A(W), извлекающую всю интерпретируемую информацию из данных в соответствии с теорией измерений. Преобразование

W ® {áX(w), Y(w)ñ}

заменим на преобразование

W ® A(W) ® {áX(w), Y(w)ñ}.

Метод

M : {áX(w), Y(w)ñ} ® J

преобразуем в метод

ML : A(W) ® J

таким образом, чтобы метод ML делал все то же самое, что и метод M, только вместо выборки W использовал соответствующую ей эмпирическую систему A(W) и все действия, которые осуществляет метод М переводил бы в действия над эмпирической системой. Точнее, если числовые представления признаков (x₁, …, x_n, Y) получены сильными гоморфизмами

φ_i : A_i ® , φ : B ® Reⁿ,

то комплексное преобразование

(φ₁, …, φ_n, φ) : A(W) ® {áX(w), Y(w)ñ}

переводит многосортную эмпирическую систему в числовое представление выборки. Отсюда получаем

J = M({áX(w), Y(w)ñ}) = М((φ₁, …, φ_n, φ)(A(W))) = ML(A(W)).

Извлечем из правила J некоторое правило JL, содержащее всю интерпретируемую правила J. Для этого преобразуем правило

J(X(w)) = J((φ₁, …, φ_n)A(w)) = JL(A(w)) ~ Y(w).

На основании метода ML и правила JL можно определить инвариантный метод

MLogic : A(W) ® JL

следующим образом:

MLogic(A(W)) = ML(A(W)) = J(X(w)) = JL(A(w)).

Метод MLogic очевидно инвариантен. Если мы рассмотрим все возможные выборки для метода М и получим все правила JL методом MLogic, то мы получим класс гипотез {JL} (тип знаний) метода M.

В результате проведенного анализа мы получили:

1) тип данных, с которыми работает KDD&DM-метод M в виде многосортной эмпирической системы A(W);

2) онтологию метода в виде множества отношений и операций, в которых записаны данные и представлены гипотезы;

3) тип знаний метода M как класс правил {JL}.

В отличие от конкретного KDD&DM-метода разработанная в рамках реляционного подхода система Discovery не имеет ограничений ни в типе данных, ни в онтологии, ни в классе обнаруживаемых знаний.