О задаче выявления хунты для таблично заданных функций

П. Г. Емельянов

Институт систем информатики им. А. П. Ершова СО РАН, г. Новосибирск

Аннотация: $(n,k)$-хунта — это булева функция от $n$ переменных, которая зависит не более чем от $k$ этих переменных. Задача определения того, является ли данная булева функция $k$-хунтой, и нахождения этих $n-k$ несущественных переменных является широко распространенной в машинном обучении (сокращение несущественных признаков) и проектировании электронных схем (сокращение фиктивных переменных). Естественным обобщением данного понятия, широко встречающегося в данных и других областях, например в теории игр, является понятие переменной, оказывающей малое влияние на результаты вычисления функции. Отдельный интерес представляет вопрос: рассматриваются ли несущественные или маловлиятельные переменные по отдельности или ансамблем? Вычислительная эффективность решения данных задач чрезвычайно актуальна для приложений. В частности, это зависит от используемого представления булевой функции. В настоящей работе булевы функции задаются полными или частичными таблицами истинности (примерами наборов данных). Здесь представлены два полиномиальной временной сложности алгоритма для поиска хунт, а также обсуждается случай, когда можно, аппроксимируя заданную функцию, сделать маловлиятельные переменные несущественными.

Ключевые слова: машинное обучение, логический дизайн схем, теория голосования, таблично заданные функции, проблема хунты, иррелевантные свойства, несущественные переменные, маловлиятельные переменные, декартово произведение, SQL JOINs, декомпозиция таблиц.

УДК: 512.624.2, 519.714.7, 004.85

MSC: 13-04, 68Q32, 68T09, 68W30, 94D10

Поступила в редакцию: 11.05.2025
Исправленный вариант: 20.06.2025
Принята в печать: 27.06.2025

DOI: 10.21538/0134-4889-2025-31-3-fon-07

Реферативные базы данных:

•