О вычислительной эффективности извлечения знаний вероятностными алгоритмами

В статье доказана вычислительная эффективность вероятностного подхода к извлечению знаний с помощью бинарной операции сходства. В дополнении к ранее доказанному автором результату о достаточности полиномиального числа гипотез о причинах исследуемого целевого свойства, в настоящей работе дана полиномиальная верхняя оценка на среднее время работы алгоритма порождения одного кандидата в гипотезы. Доказанный результат касается семейства алгоритмов, основанных на спаривающих цепях Маркова. Чтобы получить хорошую оценку на длину траектории (до попадания в эргодическое состояние) такой цепи потребовалось обогатить обучающую выборку добавлением столбцов-отрицаний для существующих бинарных признаков.