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}, |
| Keywords: | |
| Projects |
Idiap |
| Authors | |
| Crossref by |
Mayo98a1 |
| Added by: | [UNK] |
| Total mark: | 0 |
|
Attachments
|
|
|
|
|
Notes
|
|
|
|
|
