A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields

Mikito Nanashima
Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:660-686, 2020.

Abstract

We consider the problem of enumerating relevant features hidden in other irrelevant information for multi-labeled data, which is formalized as learning juntas. A $k$-junta function is a function which depends on only $k$ coordinates of the input. For relatively small $k$ w.r.t. the input size $n$, learning $k$-junta functions is one of fundamental problems both theoretically and practically in machine learning. For the last two decades, much effort has been made to design efficient learning algorithms for Boolean junta functions, and some novel techniques have been developed. In real-world, however, multi-labeled data seem to be obtained in much more often than binary-labeled one. Thus, it is a natural question whether these techniques can be applied to more general cases about the alphabet size. In this paper, we expand the Fourier detection techniques for the binary alphabet to any finite field $\mathbb{F}_q$, and give, roughly speaking, an $O(n^{0.8k})$-time learning algorithm for $k$-juntas over $\mathbb{F}_q$. Note that our algorithm is the first non-trivial (i.e., non-brute force) algorithm for such a class even in the case where $q=3$ and we give an affirmative answer to the question posed by Mossel et al. (2004).

Cite this Paper

BibTeX
@InProceedings{pmlr-v117-nanashima20a, title = {A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields}, author = {Nanashima, Mikito}, booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory}, pages = {660--686}, year = {2020}, editor = {Kontorovich, Aryeh and Neu, Gergely}, volume = {117}, series = {Proceedings of Machine Learning Research}, month = {08 Feb--11 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v117/nanashima20a/nanashima20a.pdf}, url = {https://proceedings.mlr.press/v117/nanashima20a.html}, abstract = {We consider the problem of enumerating relevant features hidden in other irrelevant information for multi-labeled data, which is formalized as learning juntas. A $k$-junta function is a function which depends on only $k$ coordinates of the input. For relatively small $k$ w.r.t. the input size $n$, learning $k$-junta functions is one of fundamental problems both theoretically and practically in machine learning. For the last two decades, much effort has been made to design efficient learning algorithms for Boolean junta functions, and some novel techniques have been developed. In real-world, however, multi-labeled data seem to be obtained in much more often than binary-labeled one. Thus, it is a natural question whether these techniques can be applied to more general cases about the alphabet size. In this paper, we expand the Fourier detection techniques for the binary alphabet to any finite field $\mathbb{F}_q$, and give, roughly speaking, an $O(n^{0.8k})$-time learning algorithm for $k$-juntas over $\mathbb{F}_q$. Note that our algorithm is the first non-trivial (i.e., non-brute force) algorithm for such a class even in the case where $q=3$ and we give an affirmative answer to the question posed by Mossel et al. (2004).} }
Endnote
%0 Conference Paper %T A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields %A Mikito Nanashima %B Proceedings of the 31st International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Aryeh Kontorovich %E Gergely Neu %F pmlr-v117-nanashima20a %I PMLR %P 660--686 %U https://proceedings.mlr.press/v117/nanashima20a.html %V 117 %X We consider the problem of enumerating relevant features hidden in other irrelevant information for multi-labeled data, which is formalized as learning juntas. A $k$-junta function is a function which depends on only $k$ coordinates of the input. For relatively small $k$ w.r.t. the input size $n$, learning $k$-junta functions is one of fundamental problems both theoretically and practically in machine learning. For the last two decades, much effort has been made to design efficient learning algorithms for Boolean junta functions, and some novel techniques have been developed. In real-world, however, multi-labeled data seem to be obtained in much more often than binary-labeled one. Thus, it is a natural question whether these techniques can be applied to more general cases about the alphabet size. In this paper, we expand the Fourier detection techniques for the binary alphabet to any finite field $\mathbb{F}_q$, and give, roughly speaking, an $O(n^{0.8k})$-time learning algorithm for $k$-juntas over $\mathbb{F}_q$. Note that our algorithm is the first non-trivial (i.e., non-brute force) algorithm for such a class even in the case where $q=3$ and we give an affirmative answer to the question posed by Mossel et al. (2004).
APA
Nanashima, M.. (2020). A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields. Proceedings of the 31st International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 117:660-686 Available from https://proceedings.mlr.press/v117/nanashima20a.html.

Related Material