Cortical Computation via Iterative Constructions

Christos Papadimitriou, Samantha Petti, Santosh Vempala
29th Annual Conference on Learning Theory, PMLR 49:1357-1375, 2016.

Abstract

We study Boolean functions of an arbitrary number of input variables that can be realized by simple iterative constructions based on constant-size primitives. This restricted type of construction needs little global coordination or control and thus is a candidate for neurally feasible computation. Valiant’s construction of a majority function can be realized in this manner and, as we show, can be generalized to any uniform threshold function. We study the rate of convergence, finding that while linear convergence to the correct function can be achieved for any threshold using a fixed set of primitives, for quadratic convergence, the size of the primitives must grow as the threshold approaches 0 or 1. We also study finite realizations of this process and the learnability of the functions realized. We show that the constructions realized are accurate outside a small interval near the target threshold, where the size of the construction grows as the inverse square of the interval width. This phenomenon, that errors are higher closer to thresholds (and thresholds closer to the boundary are harder to represent), is a well-known cognitive finding.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-papadimitriou16, title = {Cortical Computation via Iterative Constructions}, author = {Papadimitriou, Christos and Petti, Samantha and Vempala, Santosh}, booktitle = {29th Annual Conference on Learning Theory}, pages = {1357--1375}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/papadimitriou16.pdf}, url = {https://proceedings.mlr.press/v49/papadimitriou16.html}, abstract = {We study Boolean functions of an arbitrary number of input variables that can be realized by simple iterative constructions based on constant-size primitives. This restricted type of construction needs little global coordination or control and thus is a candidate for neurally feasible computation. Valiant’s construction of a majority function can be realized in this manner and, as we show, can be generalized to any uniform threshold function. We study the rate of convergence, finding that while linear convergence to the correct function can be achieved for any threshold using a fixed set of primitives, for quadratic convergence, the size of the primitives must grow as the threshold approaches 0 or 1. We also study finite realizations of this process and the learnability of the functions realized. We show that the constructions realized are accurate outside a small interval near the target threshold, where the size of the construction grows as the inverse square of the interval width. This phenomenon, that errors are higher closer to thresholds (and thresholds closer to the boundary are harder to represent), is a well-known cognitive finding.} }
Endnote
%0 Conference Paper %T Cortical Computation via Iterative Constructions %A Christos Papadimitriou %A Samantha Petti %A Santosh Vempala %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-papadimitriou16 %I PMLR %P 1357--1375 %U https://proceedings.mlr.press/v49/papadimitriou16.html %V 49 %X We study Boolean functions of an arbitrary number of input variables that can be realized by simple iterative constructions based on constant-size primitives. This restricted type of construction needs little global coordination or control and thus is a candidate for neurally feasible computation. Valiant’s construction of a majority function can be realized in this manner and, as we show, can be generalized to any uniform threshold function. We study the rate of convergence, finding that while linear convergence to the correct function can be achieved for any threshold using a fixed set of primitives, for quadratic convergence, the size of the primitives must grow as the threshold approaches 0 or 1. We also study finite realizations of this process and the learnability of the functions realized. We show that the constructions realized are accurate outside a small interval near the target threshold, where the size of the construction grows as the inverse square of the interval width. This phenomenon, that errors are higher closer to thresholds (and thresholds closer to the boundary are harder to represent), is a well-known cognitive finding.
RIS
TY - CPAPER TI - Cortical Computation via Iterative Constructions AU - Christos Papadimitriou AU - Samantha Petti AU - Santosh Vempala BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-papadimitriou16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 1357 EP - 1375 L1 - http://proceedings.mlr.press/v49/papadimitriou16.pdf UR - https://proceedings.mlr.press/v49/papadimitriou16.html AB - We study Boolean functions of an arbitrary number of input variables that can be realized by simple iterative constructions based on constant-size primitives. This restricted type of construction needs little global coordination or control and thus is a candidate for neurally feasible computation. Valiant’s construction of a majority function can be realized in this manner and, as we show, can be generalized to any uniform threshold function. We study the rate of convergence, finding that while linear convergence to the correct function can be achieved for any threshold using a fixed set of primitives, for quadratic convergence, the size of the primitives must grow as the threshold approaches 0 or 1. We also study finite realizations of this process and the learnability of the functions realized. We show that the constructions realized are accurate outside a small interval near the target threshold, where the size of the construction grows as the inverse square of the interval width. This phenomenon, that errors are higher closer to thresholds (and thresholds closer to the boundary are harder to represent), is a well-known cognitive finding. ER -
APA
Papadimitriou, C., Petti, S. & Vempala, S.. (2016). Cortical Computation via Iterative Constructions. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:1357-1375 Available from https://proceedings.mlr.press/v49/papadimitriou16.html.

Related Material