Отправить статью по E-mail О вычислительной эффективности извлечения знаний вероятностными алгоритмами
- Авторы: Виноградов Д.В.1
-
Учреждения:
- Федеральный исследовательский центр «Информатика и управление» РАН
- Выпуск: № 4 (2023)
- Страницы: 29-37
- Раздел: Вычислительный интеллект
- URL: https://ogarev-online.ru/2071-8594/article/view/269741
- DOI: https://doi.org/10.14357/20718594230403
- EDN: https://elibrary.ru/NELPQW
- ID: 269741
Цитировать
Полный текст
Аннотация
В статье доказана вычислительная эффективность вероятностного подхода к извлечению знаний с помощью бинарной операции сходства. В дополнении к ранее доказанному автором результату о достаточности полиномиального числа гипотез о причинах исследуемого целевого свойства, в настоящей работе дана полиномиальная верхняя оценка на среднее время работы алгоритма порождения одного кандидата в гипотезы. Доказанный результат касается семейства алгоритмов, основанных на спаривающих цепях Маркова. Чтобы получить хорошую оценку на длину траектории (до попадания в эргодическое состояние) такой цепи потребовалось обогатить обучающую выборку добавлением столбцов-отрицаний для существующих бинарных признаков.
Ключевые слова
Об авторах
Дмитрий Вячеславович Виноградов
Федеральный исследовательский центр «Информатика и управление» РАН
Автор, ответственный за переписку.
Email: KRRGuest@yandex.ru
доктор физико-математических наук, ведущий научный сотрудник
Россия, МоскваСписок литературы
- ДСМ-метод автоматического порождения гипотез: Логические и эпистемологические основания //Ред.: Финн В.К., Аншаков О.М.). М.: URSS. 2009. 432 c.
- Милль Дж.Ст. Система логики силлогистической и индуктивной: Изложение принципов доказательства в связи с методами научного исследования. Пер. с англ. Изд. 5. М.: URSS. 2011. 832 c.
- Гусакова С.М., Финн В.К. Сходства и правдоподобный вывод // Известия АН СССР. Сер. «Техническая кибернетика». 1987. № 5. C. 42–63.
- Ganter, Bernhard and Wille, Rudolf. Formal Concept Analysis: Mathematical Foundations. Berlin: Springer–Verlag. 1999. 284 p.
- Виноградов Д.В. Вероятностное порождения гипотез в ДСМ-методе с помощью простейших цепей Маркова // Научная и техническая информация. Сер. 2. 2012. № 9. C. 20–27.
- Кузнецов С.О. Быстрый алгоритм построения всех пересечений объектов из нижней полурешетки // Научная и техническая информация. Сер. 2. 1993. № 1. C. 17–20.
- Виноградов Д.В. Алгебраическое машинное обучение: упор на эффективность // Автоматика и телемеханика. 2022. № 6. С. 5–23.
- Кемени Дж., Снелл Дж. Конечные цепи Маркова. Пер. с англ. М.: Наука. 1970. 272 c.
- Виноградов Д.В. ВКФ-метод интеллектуального анализа данных: обзор результатов и открытых проблем // Искусственный интеллект и принятие решений. 2017. № 2. C. 9–16.
- Виноградов Д.В. Цепи Маркова, формула полной вероятности и рекуррентные соотношения // Научная и техническая информация. Сер. 2. 2023. № 2. С. 35–39.
Дополнительные файлы
