Семинар ММИТ. Доклад Никиты Драгунова

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

Исследована актуальная задача поиска по базе транзакций максимальных частых и минимальных нечастых элементов декартового произведения частичных порядков P. Для её решения предложен эффективный в «типичном случае» алгоритм. Указанный алгоритм адаптирован для решения важной в дискретной математике задачи расшифровки двузначной монотонной функции, определённой на элементах множества P и принимающей значение 0 и 1 соответственно на частых и нечастых элементах этого множества.

Рассмотрен подход к задаче классификации по прецедентам, базирующийся на применении аппарата дискретной математики (логических методов анализа данных). Исследована возможность сокращения временных затрат на стадии обучения корректного логического классификатора. Предложены новые модели классификаторов, основанные на поиске в описаниях прецедентов часто встречающихся фрагментов специального вида, названных правильными элементарными классификаторами. Эффективность предлагаемых моделей классификаторов обоснована экспериментально и подтверждена теоретическими оценками сложности их обучения. А именно, получены асимптотические оценки типичного числа и оценки типичного ранга правильных элементарных классификаторов..