Online First 2025
УДК 512.624.2, 519.714.7, 004.85
MSC: 13-04, 68Q32, 68T09, 68W30, 94D10
DOI: 10.21538/0134-4889-2025-31-3-fon-07
(Full Text)
$(n,k)$-хунта — это булева функция от n переменных, которая зависит не более чем от $k$ этих переменных. Задача определения того, является ли данная булева функция $k$-хунтой, и нахождения этих $n - k$ несущественных переменных является широко распространенной в машинном обучении (сокращение несущественных признаков) и проектировании электронных схем (сокращение фиктивных переменных). Естественным обобщением данного понятия, широко встречающегося в данных и других областях, например в теории игр, является понятие переменной, оказывающей малое влияние на результаты вычисления функции. Отдельный интерес представляет вопрос: рассматриваются ли несущественные или маловлиятельные переменные по отдельности или ансамблем? Вычислительная эффективность решения данных задач чрезвычайно актуальна для приложений. В частности, это зависит от используемого представления булевой функции. В настоящей работе булевы функции задаются полными или частичными таблицами истинности (примерами наборов данных). Здесь представлены два полиномиальной временной сложности алгоритма для поиска хунт, а также обсуждается случай, когда можно, аппроксимируя заданную функцию, сделать маловлиятельные переменные несущественными.
Ключевые слова: машинное обучение, логический дизайн схем, теория голосования, таблично заданные функции, проблема хунты, иррелевантные свойства, несущественные переменные, маловлиятельные переменные, декартово произведение, SQL JOINs, декомпозиция таблиц.
Поступила 11.05.2025
После доработки 20.06.2025
Принята к публикации 27.06.2025
Опубликована онлайн 30.06.2025
Емельянов Павел Геннадьевич
канд. физ.-мат. наук
старший науч. сотрудник
Институт систем информатики им. А.П.Ершова СО РАН
г. Новосибирск
e-mail: emelyanov@iis.nsk.su
Ссылка на статью: П.Г. Емельянов. О задаче выявления хунты для таблично заданных функций // Тр. Ин-та математики и механики УрО РАН. 2025. https://doi.org/10.21538/0134-4889-2025-31-3-fon-07
P. G. Emelyanov. On junta problem for table–defined functions.
A $(n,k)$-junta is a Boolean function of n variables that depends on at most $k$ of these variables. The task of determining whether a given Boolean function is a $k$-junta and finding these $n - k$ unessential variables is common in machine learning (irrelevant feature reduction) and electronic circuit design (fictitious variable reduction). A natural extension of this idea, which is commonly found in these and other areas, for example, in game theory, is the notion of a variable with little influence on the results of a function’s calculation. Of particular interest is the issue of whether insignificant or low-impact variables are considered individually or as an ensemble. The computational efficiency of solving these problems is of significant relevance for practical applications. This depends, in particular, on the representation of the boolean function employed. In this paper Boolean functions are specified by complete or partial truth tables (sample datasets). This paper presents two poly-time algorithms for finding juntas, as well as discussing the case where we approximate a given function making low-impact variables entirely unessential.
Keywords: machine learning, logic design, voting theory, table-defined functions, junta problem, irrelevant features, inessential variables, low-impact variables, cartesian product, SQL JOINs, decomposition of tables.
Received May 11, 2025
Revised June 20, 2025
Accepted June 27, 2025
Published online June 30, 2025
Pavel Gennadievich Emelyanov, Cand. Sci. (Phys.-Math.), A.P. Ershov Institute of Informatics Systems of the Siberia Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: emelyanov@iis.nsk.su.
Cite this article as: P.G.Emelyanov. On junta problem for table-defined functions. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025. https://doi.org/10.21538/0134-4889-2025-31-3-fon-07
