On the Complexity of the Class of Regions Computable by a Two-Layered Perceptron
| Type of publication: | Idiap-RR |
| Citation: | Mayo96a |
| Number: | Idiap-RR-03-1996 |
| Year: | 1996 |
| Institution: | IDIAP |
| Abstract: | This work is concerned with the computational complexity of the recognition of $\mbox{LP}_2$, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Several subclasses of $\mbox{LP}_2$ of particular interest are also considered. We show that the recognition problems of $\mbox{LP}_2$ and of other classes considered here are intractable, even in some favorable circumstances. We then identify special cases having polynomial time algorithms. |
| Userfields: | ipdmembership={learning}, |
| Keywords: | |
| Projects |
Idiap |
| Authors | |
| Added by: | [UNK] |
| Total mark: | 0 |
|
Attachments
|
|
|
|
|
Notes
|
|
|
|
|
