Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions (Q3137706)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 428574
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions |
scientific article; zbMATH DE number 428574 |
Statements
Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions (English)
0 references
10 October 1993
0 references
machine learning
0 references
learning with noise
0 references
Boolean formulas
0 references
identification algorithm
0 references
0.8955797553062439
0 references
0.8955797553062439
0 references
0.8920121788978577
0 references
0.89133220911026
0 references
The identification problem consists of the following: a formula \(F\) is given as a ``black box'' in the sense that we are not allowed to see this formula, but we are allowed to input an arbitrary combination of input variables \(x_ 1,\dots,x_ n\), and to see the output truth value. If we impose no restrictions on \(F\), then no matter how many input sets we input, unless we inputted all \(2^ n\) sets, we will not be sure that we reconstructed \(F\) correctly. Therefore, usually an additional possibility is added: as soon as we have produced a reasonable hypothesis \(F_ 0\) for \(F\), we can ask whether this hypothesis is true (i.e., whether \(F_ 0\) and \(F\) are equivalent formulas). This ``guess-checking'' seems natural, but checking equivalence of propositional formulas is NP-hard and thus not always feasible. Therefore, it is important to find classes of formulas that can be identified without guess-checking. In the paper under review, the following class is considered: Boolean formulas in which each variable occurs only once (they are called read- once formulas). Examples of such formulas are log-depth ``majority'' formulas, i.e., formulas of logarithmic depth that are built from NOT and MAJ gates (a MAJ gate has three inputs, output is determined by the majority), and log-depth positive NAND formulas. In the proposed algorithms, the inputs \(x_ 1,\dots,x_ n\) are generated by \(n\) independent random number generators with \(P(x_ i)=p\), where \(p\) is chosen in such a way that the resulting probability of \(F\) being true is exactly \(p\). The resulting identification algorithm is polynomial-time, and works well even in the presence of noise. These results become even more interesting if we take into consideration the fact that a more general problem of distribution-free learning is known to be unsolvable in polynomial time. Namely, for every \(\varepsilon > 0\), if we generate inputs following some unknown distribution, then there is no polynomial-time method that would use this information and always come up with a guess \(F_ 0\) whose output coincides with \(F\) in \(>1-\varepsilon\) cases.
0 references