Learning non-linear concepts based on random projection

我们将随机投影与线性分类器相结合，研究了学习非线性概念的新模式。特别是，我们证明了Boosting算法自然会导致我们的学习方案，其中该算法在给定的规则类中随机选择适当的规则，并作为最终假设产生这些规则的线性组合。另一方面，我们给出了恒定深度阈值电路复杂度的下界，为我们的学习模式提供了最自然的假设类。这些界限暗示了我们的Shema在理论上的局限性。

We investigate new schema for learning non-linear concepts by combining random projection with linear classifiers. In particular, we show that a boosting algorithm naturally results in our learning scheme, where the algorithm randomly chooses appropriate rules in a given rule class and produces as a final hypothesis a linear combination of them. On the other hand, we give lower bounds on the complexity of constant depth threshold circuits, which serve the most natural hypothesis class for our learning schema. The bounds imply theoretical limitations for our shema.