Doctor of Physical and Mathematical Sciences, Leading Researcher
доктор физико-математических наук, ведущий научный сотрудник
The paper demonstrates computational efficiency of probabilistic approach to knowledge extraction through binary similarity operation. In addition to previously proved by the author the result on sufficiency of a polynomial number of hypotheses on causes of investigated target property, the paper contains a polynomial upper bound on mean working time of the algorithm to generate a single candidate for hypothesis. The proven result concerns a family of algorithms based on coupled Markov chains. To obtain a good estimate for the length of the trajectory (before entering the ergodic state) of such a chain, we needed to enrich the training sample by adding negative columns for existing binary features.
В статье доказана вычислительная эффективность вероятностного подхода к извлечению знаний с помощью бинарной операции сходства. В дополнении к ранее доказанному автором результату о достаточности полиномиального числа гипотез о причинах исследуемого целевого свойства, в настоящей работе дана полиномиальная верхняя оценка на среднее время работы алгоритма порождения одного кандидата в гипотезы. Доказанный результат касается семейства алгоритмов, основанных на спаривающих цепях Маркова. Чтобы получить хорошую оценку на длину траектории (до попадания в эргодическое состояние) такой цепи потребовалось обогатить обучающую выборку добавлением столбцов-отрицаний для существующих бинарных признаков.