Abstract
In this paper, we aim at introducing a new machine learning model, namely reconciled polynomial machine, which can provide a unified representation of existing shallow and deep machine learning models. Reconciled polynomial machine predicts the output by computing the inner product of the feature kernel function and variable reconciling function. Analysis of several concrete models, including Linear Models, FM, MVM, Perceptron, MLP and Deep Neural Networks, will be provided in this paper, which can all be reduced to the reconciled polynomial machine representations. Detailed analysis of the learning error by these models will also be illustrated in this paper based on their reduced representations from the function approximation perspective.
Introduction
In modern machine learning, a conceptual divide often exists between "shallow" models—such as linear regression and factorization machines—and "deep" learning architectures. While deep neural networks (DNNs) consistently outperform shallow models on complex tasks, the underlying mathematical reason for this superiority is frequently obscured by the complexity of non-linear activations and multi-layered structures. This paper proposes the Reconciled Polynomial Machine (RPM), a theoretical framework that provides a unified mathematical language to describe how both shallow and deep models approximate target functions.
The Reconciled Polynomial Machine (RPM)
The core of the RPM framework is the realization that most predictive models can be expressed as a polynomial expansion of input features. The RPM is defined by two primary components:
- Feature Kernel Function ($\kappa$): This function projects input features into a high-dimensional space of "monomials" (e.g., $x_1, x_1x_2, x_1x_2x_3$).
- Variable Reconciling Function ($\psi$): This function maps the model's internal parameters (weights) to the coefficients of these monomials.
The model's output is then the inner product: $f(x; w) = \psi(w)^\top \kappa(x)$. By applying the Taylor Expansion Theorem, the authors demonstrate that any smooth mapping on binary features can be represented as a finite polynomial, allowing various architectures to be "reduced" to this RPM form.
Reducing Shallow Models
Shallow models are characterized by their limited ability to capture high-order feature interactions. The paper successfully maps these models into the RPM framework by identifying specific reconciling functions for each:
- Linear Models only capture first-order monomials (individual features).
- Factorization Machines (FM) extend this to second-order interactions (feature pairs).
- Perceptrons use a non-linear activation function to implicitly represent a sequence of polynomial terms, yet they remain limited in their representational capacity compared to multi-layer structures.
The Advantage of Depth
The transition from shallow to deep models is fundamentally a transition in how efficiently complex feature interactions are represented. While a single-layer Perceptron can approximate functions, it often fails on non-monotone tasks like the XOR problem.
The paper's most significant theoretical contribution is the proof of the Efficiency of Depth. To represent an $n$-order polynomial interaction:
- A shallow network (one hidden layer) requires an exponential number of neurons ($2^n$).
- A deep network can achieve the same representation with a linear number of neurons (approximately $n-1$).
This provides a rigorous mathematical justification for why deep architectures are more parameter-efficient than shallow ones: they can approximate the "high-order remainder" of a Taylor expansion with far fewer variables.
Generalization and Complexity
Using Hoeffding’s Inequality, the authors analyze the generalization error of these models. While DNNs have the capacity to achieve near-zero empirical loss due to their vast "feasible variable set," this same capacity necessitates more data or robust regularization to prevent overfitting. The RPM framework thus clarifies the trade-off between representation power and generalization.
Conclusion and Limitations
The Reconciled Polynomial Machine offers a powerful lens through which to view the machine learning landscape. However, the current theory primarily assumes binary features $\{0, 1\}$ for its most elegant proofs. Furthermore, the analysis focuses on representation power (what a model can do) rather than optimization (how easily it can be trained via gradient descent). Future work is needed to validate these theoretical bounds on modern, high-dimensional datasets.
Summary updated