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
      0 references
      0 references
      0 references
      10 October 1993
      0 references
      machine learning
      0 references
      learning with noise
      0 references
      Boolean formulas
      0 references
      identification algorithm
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references