# Integrating Interpolation and Extrapolation: A Hybrid Predictive Framework for Supervised Learning
## 2 Problem Statement and Model Setup
### Optimization Model M0  
In our predictive framework, a pivotal decision revolves around classifying a new observation as either an interior or an exterior point relative to the known dataset. This distinction is important for choosing which method to use for prediction. In this paper, the \(k\)NN model is used for predicting interior points by interpolation, and linear regression is used for predicting exterior points by extrapolation. Consequently, pinpointing this classification is of paramount importance. To this end, we introduce the optimization model M0. Model M0 harnesses a linear programming model to decisively categorize the new observation. Its core principle is to compute the shortest distance between the new observation and the known dataset's convex hull, which represents the smallest convex set encompassing all dataset points. A zero minimum distance suggests that the observation resides within the convex hull, designating it as an interior point. Conversely, a positive minimum distance indicates the observation's position outside the convex hull, categorizing it as an exterior point. Table 1 shows all of the notations needed in the optimization model. To ascertain the distance between a new observation \(x_{0}\) and the known dataset's convex hull, we formulate the optimization model, termed M0, as follows:  
\[\min_{\lambda(x_{0})}\left|\sum_{i=1}^{N}\lambda_{i}(x_{0})x_{i}-x_{0}\right| \tag{1}\]  
subject to  
\[\sum_{i=1}^{N}\lambda_{i}(x_{0})=1 \tag{2}\]  
\[\lambda_{i}(x_{0})\geq 0,\,\forall i\in\{1,\dots,N\}. \tag{3}\]  
Objective Function (1) aims to minimize the Manhattan distance between \(x_{0}\) and the convex hull defined by the known dataset. The optimal value of this objective function is termed the centrality coefficient, gauging the proximity of the new data point relative to the dataset. Constraint (2) ensures the sum of weights for all of the known data points equals one. Constraints (3) define the domains of the decision variables. Defining \(\lambda^{*}(x_{0})=\left[\lambda_{1}^{*}(x_{0}),\dots,\lambda_{N}^{*}(x_{0})\right]\) as the optimal solution obtained by solving the optimization model, we have  
\[d^{*}(x_{0})=\left|\sum_{i=1}^{N}\lambda_{i}^{*}(x_{0})x_{i}-x_{0}\right|,\] \begin{table}
\begin{tabular}{c l} \hline \hline
**Parameters** & \\ \hline \(S_{N}=\{(x_{i},y_{i}):i=1,\dots,N\}\) & A dataset with \(N\) known samples, \\ \(x_{i}\in X\subseteq\mathbb{R}^{p}\), \(y_{i}\in Y\subseteq\mathbb{R}\), where \(p\) is the & dimension of input feature vector \(x_{i}\). \\ \(x_{0}=\left(x_{0}^{1},\dots,x_{0}^{p}\right)\) & A new data point. \\ \hline
**Decision variables** & \\ \hline \(\lambda(x_{0})=\left[\lambda_{1}(x_{0}),\dots,\lambda_{N}(x_{0})\right]\) & The weighted vector for the new data point \(x_{0}\), \\ \(\lambda(x_{0})=\left[\lambda_{1}(x_{0}),\dots,\lambda_{N}(x_{0})\right]\) & where \(\lambda_{i}(x_{0})\) represents the weight of data \\  & point \((x_{i},y_{i})(i\in\{1,\dots,N\})\) in relation to the \\  & new data point. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations in the optimization model. which denotes the centrality coefficient of \(x_{0}\) and serves as the deciding factor for choosing between interpolation and extrapolation methods for \(x_{0}\). If \(d^{*}(x_{0})=0\), this represents that the new data point is an interior point with respect to the known dataset. If \(d^{*}(x_{0})>0\), this represents that the new data point is not an interior point to the given dataset; that is, the new data point has an exterior nature relative to the given dataset. Before applying our optimization model to classify the new observation as exterior or interior, we need to tackle two challenges. First, numerical features are naturally integrated into our optimization model without the need for additional processing. However, categorical features pose a unique challenge. These categorical data points do not have a clear numerical relationship, making it challenging to directly measure the categorical distance in our model.