Learning random monotone DNF (Q628302): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/j.dam.2010.08.022 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W3021060265 / rank | |||
Normal rank | |||
Revision as of 22:26, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Learning random monotone DNF |
scientific article |
Statements
Learning random monotone DNF (English)
0 references
10 March 2011
0 references
Learning polynomial-time disjunctive normal formulas from random samples is an open problem in learning theory, even with the uniform distribution. A special case is to learn monotone disjunctive normal formulas under the uniform distribution, which is the topic considered in this paper. By studying Fourier properties of monotone functions, the authors give a polynomial-time algorithm to solve an average-case version of this problem for learning monotone disjunctive normal formulas.
0 references
Fourier analysis
0 references
monotone Boolean function
0 references
computational learning theory
0 references
