7
$\begingroup$

From this thread I learned why the median is a nonlinear function. In the context in which I'm working I need to use a linear function.

Googling "approximate the median"+"linear" didn't reveal anything usable, but somehow it seems intuitive to me that some reasonable approximation should be possible with a linear function.

EDIT: I was asked in one of the comments to provide a fuller explanation of the context behind the question. The context is that I'm taking in a bunch of estimates from people about some quantity, and then generating an aggregated prediction them. One of the most obvious things to do is to linearly combine the estimates according to some predetermined weights.

The framework is provided by Davis-Stober et al (2014), who write:

Consider a set of N-many decision makers (DMs), where each DM makes a judgment about the unknown value of a criterion. [...] We take this criterion value to be a random variable, $Y$, with mean $\mu_{y}$ and variance $\sigma^{2}$. [...] A crowd prediction, denoted $C$, is defined as the random variable formed by linearly combining the DMs according to predetermined weights $w_{i}$, $C = \sum_{i=1}^{N} w_{i}X_{i}$, with the restriction that all $w_{i}$ are non-negative and, to ensure uniqueness, $\sum_{i=1}^{N} w_{i} = 1$. The weights $w_{i}$ are not random variables, but rather fixed choices of how to combine crowd member judgments. [...]

Let $\mu_{x}$ by the $N \times 1$ vector of the DM's mean predictions. Let $\Sigma_{xx}$ be the covariance matrix of the $X_{i}$, $i \in \{1, > 2, ..., N\}$ random variables. Let $\sigma_{xy}$ denote the $N \times > 1$ vector of covariances of $Y$ with each $X_{i}$, $i \in > \{1,2,...,N\}$. It is straightforward to show that $E[(C-Y)^2]$ is equal to the following

$E[(C-Y)^{2}]=(u{'}_{x}w - u_{y})^{2} + w{'}\Sigma_{xx}w - 2w{'}\sigma_{xy} + \sigma^{2}_{y}$,

where $w$ is the $N \times 1$ vector of weights, $w_{i}, i \in \{1,2, > ..., N\}$, defining $C$.

So I want to 'break down' $E[(C-Y)^{2}]$ in the way described in the aforementioned paper, but in the context in which I'm working it's more common to use the median instead of the mean. It's been asserted to me that I could get around this problem by using a linear aggregate to approximate the median.

Davis-Stober, C. P., Budescu, D. V., Dana, J., & Broomell, S. B. (2014). When is a crowd wise?. Decision, 1(2), 79. Chicago

$\endgroup$
9
  • $\begingroup$ Can you expand on your context? Essentially, for any data set there is some set of weights which make the weighted mean equal to the median. However the weights depend on the data (i.e. the median is nonlinear). In many contexts a sequence of linear problems can be solved, if that is suitable (e.g. Iteratively Reweighted Least Squares). $\endgroup$
    – GeoMatt22
    Aug 30, 2016 at 1:37
  • 2
    $\begingroup$ Linear function of what exactly? If it's the original observations, without regard to their size/order I think the unweighted mean is as good as you can do. If you can do it with regard to order (i.e. if you can apply it to the order statistics), then there is a linear function already. If you can do it with regard to size, there are various approaches. Is iteration allowed? (i.e. can I derive weights based on a sequence of weighted approximations?) $\endgroup$
    – Glen_b
    Aug 30, 2016 at 3:05
  • $\begingroup$ @GeoMatt22 Thanks for the tip. I've edited the OP to provide some additional context. $\endgroup$ Aug 30, 2016 at 4:06
  • 1
    $\begingroup$ It seems to me you could create a related vector of "crowd member judgments" by including various nonlinear functions of their original judgments. For instance, a set of judgments $(x_1,\ldots,x_n)$ could be augmented to $(x_1,\ldots,x_n;x_1^2,\ldots,x_n^2)$, which would be treated as a set of $2n$ "judgments". This would open up useful possibilities, especially if you also adopt some assumptions about the likely distribution of the judgments. Otherwise you're stuck with the conclusions given by @Glen_b. $\endgroup$
    – whuber
    Aug 30, 2016 at 13:51
  • $\begingroup$ When you say "median instead of mean" is this referring to $C$, $E[]$ or both? $\endgroup$
    – GeoMatt22
    Aug 30, 2016 at 14:23

2 Answers 2

2
$\begingroup$

We are looking to find $N$ constrained $w_i$ with $\sum_{i=1}^n w_i=1$ which minimize $$E\left[\left(\sum_{i=1}^N w_i X_i - \text{median}(X)\right)^{\!2\ }\right]$$ Equivalently, we are looking to find $N-1$ unconstrained $w_i$ which minimize $$E\left[\left(\sum_{i=1}^{N-1} w_i(X_i-X_N) + X_N - \text{median}(X)\right)^{\!2\ }\right]$$ Taking the derivative with respect to $w_j$ gives $$E\left[2\left(\sum_{i=1}^{N-1} w_i(X_i-X_N) + X_N - \text{median}(X)\right)(X_j-X_N)\right]=0$$ Or equivalently $$\sum_{i=1}^{N-1}E\Big[(X_i-X_N)(X_j-X_N)\Big]w_i= E\Big[(\text{median}(X)-X_N)(X_j-X_N)\Big]$$ We can put these equations in the matrix form $M w = C$ (where $M$ is square and $M$, $w$ and $C$ all have $N-1$ rows), and solve them as $w = M^{-1}C$.

If $X\sim N(\mu,\Sigma)$, then calculating $M$ is tedious, but each component has a formula in terms of $\mu$ and $\Sigma$. More numerical effort is required for calculating $M^{-1}$, and for calculating $C$: I think there are no closed formulas for the components of $C$ even in the simple case when $X$ is normal.

$\endgroup$
2
$\begingroup$

This is work towards an answer, too long for a comment:

One precise version of this question is: What vector of weights $w$ makes $w\cdot X$ the best estimate of the median of $X$, where $X$ is a normally distributed $n$-dimensional vector with mean $\mu$ and covariance matrix $\Sigma$?

This is different from asking for the vector $w$ for estimating the mean. E.g. suppose $X_1$, $X_2$, $X_3$ are independent and $N(10,1)$, $N(100,1)$ and $N(1000,1)$ respectively. Then the $w$ for estimating (and for exactly calculating) the mean of $X$ is $(\frac13, \frac13, \frac13)$. Meanwhile, the $w$ for estimating the median is close to or exactly $(0,1,0)$.

The original question is more general than the normal case, but the normal case seems challenging already.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.