logo Idiap Research Institute        
 [BibTeX] [Marc21]
On the Complexity of Recognizing Regions Computable by Two-Layered Perceptrons
Type of publication: Idiap-RR
Citation: Mayo98a
Number: Idiap-RR-03-1998
Year: 1998
Institution: IDIAP
Abstract: This work is concerned with the computational complexity of the recognition of $ÞPtwo$, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Some subclasses of $ÞPtwo$ of particular interest are also studied, such as the class of iterated differences of polyhedra, or the class of regions $V$ that can be classified by a two-layered perceptron with as only hidden units the ones associated to $(d-1)$-dimensional facets of $V$. In this paper, we show that the recognition problem for $ÞPtwo$ as well as most other subclasses considered here is \NPH\ in the most general case. We then identify special cases that admit polynomial time algorithms.
Userfields: ipdmembership={learning},
Projects Idiap
Authors Mayoraz, Eddy
Crossref by Mayo98a1
Added by: [UNK]
Total mark: 0
  • rr98-03.pdf
  • rr98-03.ps.gz