Publication

On the Complexity of Recognizing Regions Computable by Two-Layered Perceptrons

1998
Reports

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.

Official source

https://infoscience.epfl.ch/entities/publication/6462902c-509d-494e-b3b5-c45a8697bea3

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

1998
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/6462902c-509d-494e-b3b5-c45a8697bea3

About this result

Related concepts (32)

Multilayer perceptron

A multilayer perceptron (MLP) is a misnomer for a modern feedforward artificial neural network, consisting of fully connected neurons with a nonlinear kind of activation function, organized in at least three layers, notable for being able to distinguish data that is not linearly separable. It is a misnomer because the original perceptron used a Heaviside step function, instead of a nonlinear kind of activation function (used by modern networks).

Perceptrons (book)

Perceptrons: an introduction to computational geometry is a book written by Marvin Minsky and Seymour Papert and published in 1969. An edition with handwritten corrections and additions was released in the early 1970s. An expanded edition was further published in 1987, containing a chapter dedicated to counter the criticisms made of it in the 1980s. The main subject of the book is the perceptron, a type of artificial neural network developed in the late 1950s and early 1960s.

Perceptron

In machine learning, the perceptron (or McCulloch-Pitts neuron) is an algorithm for supervised learning of binary classifiers. A binary classifier is a function which can decide whether or not an input, represented by a vector of numbers, belongs to some specific class. It is a type of linear classifier, i.e. a classification algorithm that makes its predictions based on a linear predictor function combining a set of weights with the feature vector.

Related publications (32)

On the Complexity of Recognizing Regions Computable by Two-Layered Perceptrons

Chat with Graph Search

Acceleration of Solvers for Plasma Simulation in the Tokamak Boundary

Benchmarking of cancelable biometrics for deep templates

Faster Homomorphic Operations and Beyond: Expediting Homomorphic Computation via Boolean Circuit Optimization