HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Oztop, E. Search for Related Content PubMed PubMed Citation Articles by Oztop, E.

An Upper Bound on the Minimum Number of Monomials Required to Separate Dichotomies of {–1, 1}ⁿ

erhan{at}atr.jp JST-ICORP Computational Brain Project and ATR Computational Neuroscience Laboratory, 2-2-2 Hikari-dai Soraku-gun, Kyoto, 619-0288, Japan

It is known that any dichotomy of {–1, 1}ⁿ can be learned (separated) with a higher-order neuron (polynomial function) with 2ⁿ inputs (monomials). In general, less than 2ⁿ monomials are sufficient to solve a given dichotomy. In spite of the efforts to develop algorithms for finding solutions with fewer monomials, there have been relatively fewer studies investigating maximum density ((n)), the minimum number of monomials that would suffice to separate an arbitrary dichotomy of {–1, 1}ⁿ. This article derives a theoretical (upper) bound for this quantity, superseding previously known bounds. The main theorem here states that for any binary classification problem in {–1, 1}ⁿ (n > 1), one can always find a polynomial function solution with 2ⁿ – 2ⁿ/4 or fewer monomials. In particular, any dichotomy of {–1, 1}ⁿ can be learned by a higher-order neuron with a fan-in of 2ⁿ – 2ⁿ/4 or less. With this result, for the first time, a deterministic ratio bound independent of n is established as (n)/2ⁿ 0.75. The main theorem is constructive, so it provides a deterministic algorithm for achieving the theoretical result. The study presented provides the basic mathematical tools and forms the basis for further analyses that may have implications for neural computation mechanisms employed in the cerebral cortex.