УДК 512.624.2, 519.714.7, 004.85
MSC: 13-04, 68Q32, 68T09, 68W30, 94D10
https://doi.org/10.21538/0134-4889-2025-31-3-fon-07
$(n,k)$-хунта 2 – это булева функция от n переменных, которая зависит не более чем от $k$ этих переменных. Задача определения того, является ли данная булева функция $k$-хунтой, и нахождения этих $n - k$ несущественных переменных является широко распространенной в машинном обучении (сокращение несущественных признаков) и проектировании электронных схем (сокращение фиктивных переменных). Естественным обобщением данного понятия, широко встречающегося в данных и других областях, например в теории игр, является понятие переменной, оказывающей малое влияние на результаты вычисления функции. Отдельный интерес представляет вопрос: рассматриваются ли несущественные или маловлиятельные переменные по отдельности или ансамблем? Вычислительная эффективность решения данных задач чрезвычайно актуальна для приложений. В частности, это зависит от используемого представления булевой функции. В настоящей работе булевы функции задаются полными или частичными таблицами истинности (примерами наборов данных). Здесь представлены два полиномиальной временной сложности алгоритма для поиска хунт, а также обсуждается случай, когда можно, аппроксимируя заданную функцию, сделать маловлиятельные переменные несущественными.
Ключевые слова: машинное обучение, логический дизайн схем, теория голосования, таблично заданные функции, проблема хунты, иррелевантные свойства, несущественные переменные, маловлиятельные переменные, декартово произведение, SQL JOINs, декомпозиция таблиц.
СПИСОК ЛИТЕРАТУРЫ
1. Rong M., Gong D., Gao X. Feature selection and its use in big data: challenges, methods, and trends // IEEE Access. 2019. Vol. 7. P. 197092–19725. https://doi.org/10.1109/ACCESS.2019.2894366
2. O’Donnell R. Analysis of Boolean functions. Cambridge: Cambridge Univ. Press, 2014. 417 p. ISBN: 9781139952507.
3. Mossel E. Probabilistic view of voting, paradoxes, and manipulation // Bull. Amer. Math. Soc. New Series. 2022. Vol. 59, no. 3. P. 297–330. https://doi.org/10.1090/bull/1751
4. Birnbaum Z.W. and Esary J.D. Modules of coherent binary systems // J. Soc. Indust. Appl. Math. 1965. Vol. 13, no. 2. P. 444–462. https://https://doi.org/10.1137/0113027
5. Borowik G., Łuba T., Zydek D. Features reduction using logic minimization techniques // Inter. J. Electron. Telecom. 2012. Vol. 58, no. 1. P. 71–76. https://doi.org/10.2478/v10177-012-0010-x
6. Amgoud L., Doder D. Compilation of logical arguments // Proc. Twenty-Eighth Inter. Joint Conf. Artificial Intelligence ( IJCAI-19). 2019. P. 1502–1508. https://doi.org/10.24963/ijcai.2019/208
7. Blum A. L., Langley P. Selection of relevant features and examples in machine learning // Artific. Intellig. 1997. Vol. 97, no. 1-2. P. 245–271. https://doi.org/10.1016/S0004-3702(97)00063-5
8. Boolean models and methods in mathematics, computer science, and engineering / eds. Y. Crama, P.L. Hammer. Cambridge: Cambridge Univ. Press, 2011. 687 p. (Ser. Encyclopedia Math. Appl.; vol. 134). ISBN: 9780521847520.
9. Tolo S., Andrews J. fault tree analysis including component dependencies // IEEE Transactions on Reliability. 2024. Vol. 73, no. 1. P. 413–421. https://doi.org/10.1109/TR.2023.3264943
10. Biswas A., Sarkar P. Influence of a set of variables on a Boolean function // SIAM J. Discr. Math. 2023. Vol. 37, no. 3. P. 2148–2171. https://doi.org/10.1137/22M1503531
11. Harder H., Jantsch S., Baier C., Dubslaff C. A unifying formal approach to importance values in Boolean functions // Proc. Thirty-Second Inter. Joint Conf. Artificial Intelligence (IJCAI-23). 2023. P. 2728–2737. https://doi.org/10.24963/ijcai.2023/304
12. Emelyanov P., Ponomaryov D. On tractability of disjoint AND-decomposition of Boolean formulas // Perspectives of system informatics (PSI 2014) / eds. A. Voronkov, I. Virbitskaite. Cham : Springer, 2015. P. 92–101. (Ser. Lecture Notes in Comp. Sci.) https://doi.org/10.1007/978-3-662-46823-4_8
13. Emelyanov P., Ponomaryov D. Cartesian decomposition in data analysis // Proc. Siberian Symp. Data Science and Engineering (SSDSE 2017). 2017. P. 55–60. https://doi.org/10.1109/SSDSE.2017.8071964
14. Emelyanov P. On two kinds of dataset decomposition // Proc. 18th Inter. Conf. Computational Science (ICCS 2018). Part II. / eds. Y. Shi et al. Cham : Springer, 2018. (Ser. Lecture Notes in Computer Science; vol. 10861). P. 171–183. https://doi.org/10.1007/978-3-319-93701-4_13
15. Emelyanov P., Ponomaryov D. The complexity of AND–decomposition of Boolean functions // Discrete Appl. Math. 2020. Vol. 280. P. 113–132. https://doi.org/10.1016/j.dam.2019.07.005
16. Knuth D.E. The art of computer programming. 12 ed. Boston, MA : Addison–Wesley, 2009. Vol. 4, Fascicle 1. 260 p. ISBN: 9780321580504.
17. Емельянов П.Г. Факторизация мультилинейных полиномов над GF(2) посредством редуцированного сортирующего полинома: v. 1.1, Python (2025). https://disk.yandex.ru/d/Urv4xOTCcPAqXQ (проверено 2025-11-05 ).
18. Aziz R.A., Chu G., Muise C., Stuckey P. #∃SAT: Projected Model Counting // Proc. 18th Inter. Conf. Theory and Applications of Satisfiability Testing (SAT 2015). Cham : Springer, 2015. P. 121–137. (Lecture Notes in Computer Science; vol. 11077). https://doi.org/10.1007/978-3-319-24318-4_10
19. Liu Zh., Chen X., Servedio R.A., Sheng Y., and Xie J. Distribution-free junta testing // ACM Transactions on Algorithms. 2019. Vol. 15, no. 1. Article 1, p. 1–23. https://doi.org/10.1145/3264434
Поступила 11.05.2025
После доработки 20.06.2025
Принята к публикации 27.06.2025
Опубликована онлайн 30.06.2025
Емельянов Павел Геннадьевич
канд. физ.-мат. наук
старший науч. сотрудник
Институт систем информатики им. А.П.Ершова СО РАН
г. Новосибирск
e-mail: emelyanov@iis.nsk.su
Ссылка на статью: П.Г. Емельянов. О задаче выявления хунты для таблично заданных функций // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 3. С. 105–120.
English
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, vol. 31, no. 3, pp.105–120.
[References -> on the "English" button bottom right]
