Given a lot of training data, x and y, where y is the position of the maximum value of x. Can I train a regression model (e.g., logistic, linear) to approximate the POSITION of the maximum value of x?
For example, If x = [1 3 4 10 2 -1 -2], then y will be 4 (because the 4th position has a value of 10, which is the maximum value).
If we do max(x), then get 10. If we do maxpos(x), then get 4. <-- I want to use regression model to approximate the function maxpos.
Thanks!
Mode estimation is a big fat unknown in the statistical world. It is an unsupervised process, so regression would have to be framed carefully. Obviously, with discrete $X$ you can take your $Y$ to be counts and fit a loglinear model to those data. But your example, where $Y$ is magically taken to be $4$ which is the mode of the $X$ sample... that makes no sense.
The best nonparametric way that I'm aware of estimating the mode from a sample is using a density smoother with kernal Boxcar, Gaussian, or Epanechnikov. I think it's $n^{1/5}$ efficient, which is to say incredibly slow.
Otherwise, maximum likelihood is a fully parametric way. If you assume a certain density, like normal, gamma, double exponential, or even Cauchy, you need only maximize a likelihood for the parametric density, and calculate the mode based on your distributional assumptions.
One can use nonparametric methods with splines to fit a general non-linear trend, calculate the maximum from the fitted mean, and invert the maximum to obtain the $X$ value. For a small dataset, this doesn't make sense, but with hundreds of observations, continuously valued, it makes sense.
Example:
set.seed(1)
x <- seq(-3, 3, by=0.1)
f <- function(x) .3*x^3 - 4*log(abs(x))
curve(f, from=-3, to=3)
y <- rnorm(length(x), f(x), 2)
points(x, y)
l <- loess(y ~ x, subset = is.finite(y))
abline(v=x[which.max(predict(l))], col='red')
legend('bottomright', lty=1, col='red', 'Predicted max', bty='n', cex=0.5)
Disclaimer: I never thought of this problem previously. Just did now, and after ~30 minutes of thinking, my brain managed to spit an answer. Scrutinize please.
Depends on the process that generates those numbers. For some processes, it could be possible that (say) when the 2nd component has value between 1 and 2, then the component of the largest value is always the 7th. In those cases, it would be possible to find useful regression models up to some degree that is dependent on the process.
But on the other hand, if the process is totally random, then in my view we a regression can never do do anything better than this trivial function:
if input vector seen identically in the learning set:
return that vector
else:
return a random number from {1,2,...,d}
There are many problems that can be made that share this unfriendly property. For example, can a regression function figure out $a+b$ if given many values of $a$, $b$ and their answers? Your question is essentially similar: can we use regression to learn about an operator?
I cannot think of a way of solving those problems by regression without cheating (e.g. by adding fancy new components in the samples).
Let's say that here is your training samples: \begin{equation} \mathbf{X} = \begin{pmatrix} 1& 3 &4 &10& 2 &-1 &-2\\ 2& 66 &3 &3& 3 &3 &3\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 5& 4 &0 &0& 9 &7 &2\\ \end{pmatrix} \end{equation} with the following target variables that correspond to the training samples (which specify the position of the component/dimension that has the highest value): \begin{equation} \mathbf{Y} = \begin{pmatrix} 4\\ 2\\ \vdots\\ 6\\ \end{pmatrix} \end{equation}
So $x_i = (x_{i,1},x_{i,2}, \ldots, x_{i,d})$ is some training sample of yours (a $d$ dimensional vector). And since you have $n$ many samples, then if you stack those vectors atop each other you get an $n \times d$ matrix.
Let's say that, by analysing your learning samples and their target variables (which is only $n$ samples), you managed to obtain the following estimated PDFs:
Then you get the expected value of the position of the component of the largest value is by: \begin{equation} \sum_{y=1}^d y\frac{\hat f_{X,Y}(\mathbf{x},y)}{\hat f_{X}(\mathbf{x})} \end{equation}
The accuracy depends on how lucky we are in finding good estimations of the PDFs. The question is: how lucky can we be when we only have $n$ samples?
In my view, the answer is: it also depends on the process that generates those vectors. If we are lucky and the process is one that leaves a lot of correlation between the vector component values and the target variable, then this naive estimator could achieve 100% accuracy.
Let's go almost extreme:
I can't think if a proof now (sleep time here; or maybe I am wrong), but I strongly feel at the moment is that perfectly accurate estimations of PMFs of such random process can only exist when learning samples (i.e. those $n$ vectors) cover all possible sample vector values.
The smallest possible value for $n$ can be achieved only if learning samples are chosen at perfect randomness (uniform distribution) from the population. When this perfect random sampling happens, then smallest value for $n$ is $21^d$.
So if learning samples are perfectly uniform, then $n=21^d$ must be true in order to allow for finding perfect PMFs that can perfectly find the position of the component of the largest value.
In other words, while this is computationally feasible, it is far more computationally efficient to just a linked list of unique vectors instead! Which defeats the point using statistical methods to predict.
Let's go more extreme:
Then if sampling is perfectly random, $n$ must be a number that is uncountable infinite in order to perfectly predict the function.
This is even worse than the previous case: it's computationally infeasible.
