# How can I tell if y is a function of x in a random sample?

I have some data and believe that a given metric is a function of another metric. I have the values of both metrics and many different sets of these values. Can I tell if one is a function of the other through some simple exercise like a regression? I'm not sure if the function is linear. I'm not a math expert so apologies if this is a trival question.

Edit: Here's my (Anton's) interpretation of the question. If I misunderstood, I hope gitkin corrects it.

Given a bunch of data points $\{(x_i,y_i)\}$ in the plane, I can find the line best fitting the data. Then I can compute the coefficient of determination $R^2$ to see how good the fit is. More generally, given a model $y=f(x)$ (where $f$ may not be linear), I can do various things to determine how well the model fits the data.

Is there some way to determine if there exists a model $y=f(x)$ fitting the data well? In other words, is there a way to measure your confidence that the $x$ values completely determine the $y$ values (in some reasonable way) in the system you've sampled? Intuitively, you should somehow vary over all possible functions $f$, measure how much the model $y=f(x)$ fails to explain the data, add some penalty depending on the complexity of $f$ relative to the size of the sample, and return the lowest value you get. Is there a precise, theoretically justified way to do this?

e.g. the penalty should be very high if $f$ is a polynomial of degree comparable to the number of data points.

-
poor use of terminology on my part. It's just a value. "property was quantitatively measured" is exactly what I meant. – gitkin Jan 17 '10 at 22:38
I think a version of this question, rephrased in the language of statistics, could be very good. As it is currently written, I suspect there will be votes to close, although I hope it is not, in that Douglas's answer below sufficiently interprets the question mathematically (although not deeply so). – Theo Johnson-Freyd Jan 17 '10 at 23:58
I disagree. This is not a real question. It is asking for a way to fit a curve to data points on a 2d-graph. Of course, you can construct a function that hits almost every point, but having a perfect or near-perfect fit curve doesn't help you prove anything. The whole point of modeling data like this is to see a clear trend and compute how effective your estimate is. If the function is too complicated, all that you get is a really strange looking interpolated graph. – Harry Gindi Jan 18 '10 at 4:15
I'm going to close this as "not a real question" because it's too ambiguous. We've resolved the confusion about "metric," but now I don't see what you mean by "function" or "the values of both metrics." If you have all the values, then x is a function of y if no value of y has two different values of x, but I suspect this isn't what you're looking for. Since you used the stats tag, you probably have samples. Are you asking if there's a dependence between the two? If you edit the question to ask a precise question, I'm happy to consider reopening it. – Anton Geraschenko Jan 18 '10 at 7:41
Although you can interpolate when there is no relation, nonmathematicians including physicists are likely to look at that mess and say, "That's not a function!" Perhaps they want the function to be $K$-Lipschitz for some $K$ which isn't too large, or $\alpha$-Holder continuous for some $\alpha$ which isn't too small. – Douglas Zare Jan 18 '10 at 12:07

If you are only interested in correlation between the two feature values, then there are a lot of ways to compute it (simple correlation, rank correlation, linear or nonlinear regression, etc.).

If you are interested in causality, a few places to look at are: Granger causality

and NIPS workshops on causality: 2008, 2009

-
I'm not sure why no one is upvoting this. To my limited knowledge, these look like very useful links. – David Speyer Jan 19 '10 at 13:22
I wish I understood that notion of causality well enough to say whether it fit the question. – Douglas Zare Feb 2 '10 at 6:27

Metric is a technical term in mathematics, but I'll ignore the usual technical meaning.

In practice, I would plot the points $(metric_1,metric_2)$. Decide whether you would call the graph a function, whether you can predict the value of one from the other.

A linear regression will only detect linear functions perfectly since the linear correlation will be +1 or -1. You can detect any increasing or decreasing function with a Spearman rank correlation coefficient, or just sort by one metric and see if that sorts the other.

This will not detect a relationship which is not monotone like $metric_1 = \sin(metric_2)$. If you have a good guess that something like this is the case, you might try testing the rank correlation of $metric_1$ and $\sin(metric_2)$.

-
I believe there is another technique which may be useful, which is to consider the topology of set of points within r of a data point as you increase r. It's too bad the question is closed. – Douglas Zare Jan 30 '10 at 10:47

I do have a little to add at a much lower level. The first step is to plot lots of points and see if you still believe one quantity is determined by the other. Next, rewrite the pairs as $(x_i, y_i)$ where you believe the $x$ value may determine the $y$ value (you might need to switch the order of every pair). One necessary condition is that there be no repeated $x_i.$

Finally and hardest, you really need to GUESS a functional relationship. As long as your function is determined by a (small) finite number of quantities the method of least squares can be applied. If you think you have a sine wave, you define the general curve by constants $A,B,C$ in the function $f(x) = A \sin (B x + C).$ Least squares says you minimize $\sum_{i} ( y_i - f(x_i) )^2,$ which is a process involving your data pairs and something called partial derivatives. You should get individual help with this process, it is commonly taught just for lines (regression). If the best curve matches the data points very well perhaps you have it.

Finally, the reason you are absolutely required to guess a function eventually is that, under the assumption that there is a dependence (no repeated $x_i$) there are infinitely many mathematical functions $g(x)$ that satisfy all $y_i = g(x_i)$ exactly, for example $g(x)$ can be a polynomial of high degree. What you really want is a function that will be deemed reasonable in your line of work.

-

Strictly a function is a mapping that assigns a unique value in a set B to every point in a set A. So the only way (in this strict sense) in which your second "metric" will not be a function of the first metric is if there are two datapoints for which the second metric gives different values but your first metric gives the same value.

However I suspect you have in mind the looser non-mathematical sense in which you can write the second "metric" (the quotation marks are because metric has a particular technical meaning in mathematics) as a closed-form function of the first metric plus some reasonably well-behaved error term. In this case a suitable linear regression may help you with your problem but only once you make some assumptions about the form of the functional relationship.

-
I also suspect this question will ultimately be closed as insufficiently mathematical/suitable for MathOverflow. – Tom Smith Jan 17 '10 at 22:35