1
$\begingroup$

I am currently reading Boyd's book on convex optimization of maximum likelihood estimation problem http://web.stanford.edu/class/ee364a/lectures/stat.pdf

I have zero background in statistics so I am totally confused as to what the problem is trying to achieve.

The problem formulation is as such:

given $y_i = a_i^T x + v_i$ where $y_i$ is the observed data, $x_i$ is a set of parameter value you wish to estimate and $v_i$ is a uniformly distributed noise $U([-c,c]), c$ some positive number

The maximum likelihood estimation is:

$\max \quad l(x) = -m \log(2c), |a_i^Tx - y_i| \leq c, i = 1,...,m$

Can someone provide me with some idea as to:

  1. what a uniformly and identically distributed noise $v_i$ looks like?
  2. how to find $y_i, a_i$
  3. how to solve this particular problem
  4. how can we show that $x$ is the maximum likelihood estimate?

Is the situation the same if we had Gaussian distributed noise? Thanks!

$\endgroup$
2
$\begingroup$

Let me begin by just saying a few things. This is an unusual MLE problem to begin with but understandable if the focus is on constrained optimization, because it leads to the constraints you posted. With normally distributed noise things would be quite different and would lead to an unconstrained convex optimization (ordinary least squares). Many common MLE problems lead to unconstrained convex optimizations.

Now before addressing this particular problem let us talk about MLE. MLE includes two main steps. Come up with a probabilistic model for your data. You can think of this as an assumed way of how the data was generated. Then, find the parameters that maximize the probability that your data occurs.

$a$ was drawn. It was dotted with $x$. Then a random number was drawn from $[-c,c]$ and added to the results. (Uniform means that every value in the interval was equally likely). This is how $y$ was generated. So then what was the probability of getting that $y$, from that $a$ given the parameters $x, c$?

The only random variable here was the noise which is equal to $y-a\cdot x$. Since we're assuming it was drawn from a uniform distribution on $[-c,c]$, the probability (density) of that value is $1/2c$, if the value is in this interval, and 0 otherwise. The 0 leads to the constraint, because if the probability is zero this will not be the maximum likelihood estimate.

In MLE, we assume our data are independent so the probability of all of our data will be the products of our probabilities for each data point. Given our model with parameters $x, c$, this product will be $(1/2c)^m$ if $y_i-a_i \cdot x \in [-c,c]$ for all $i$, else 0. In the equation you're seeing he's just maximizing the log of this.

1) Sort of answered above. Just imagine all of the data fell perfectly on a line and it was nudged up or down by a value as big as $c$, with every intermediate value just as likely.

2) We're not trying to find these. We should be given them. We're trying to find $x,c$. Let's try to picture this. Because $m$ is fixed our function will be maximized when $c$ is as small as possible. For any $x$, there is some $c$ that satisfies the constraint. We want the $x$ with the smallest $c$. Picture the data being roughly linear and picture a line going through it. Now picture thickening that line to be a ribbon. We want the thinnest ribbon that covers our data, and obviously that will depend on the angle of the ribbon.

3) By maximizing that function. It will involve using the dual problem, but at that point it is an optimization problem instead of a statistics one.

4) same as (3)

Hope this was helpful. I suggest you look up uniform distribution, probability density function, and probabilistic model.

$\endgroup$
2
$\begingroup$

First I must express my annoyance at (yet again) seeing perfectly sensible statistical convention being replaced with counterintuitive notation - e.g. using $x$ for the unknown parameters and $a$ and $y$ for data (predictor and response), rather than $x$ and $y$ for predictor and response and - often - Greek letters for unknown quantities - parameters, noise). There's also oddness with the terminology there. Sometimes I think this contributes to the difficulties in understanding. I'd like to recast it into conventional form, but you probably have enough to worry about so I'll leave it. [the pdf you link to has far more egregious practices, including using $\bar{x}$ (which in statistical convention is a sample average) to represent a population mean. I feel you have little hope of untangling concepts with that sort of thing going on.

--

However, I didn't find anything related to your problem in the linked document -- what page is that discussed on?


So leaving those concerns aside, you have some setting where you're taking measurements.

There are your vector-valued predictors $a_i$ (independent variables, inputs), and your scalar response, $y_i$, (dependent variable, output) for $i=1,2,..., n$.

As a simple example, $a_i$ might be of length 2, consisting of a 1 ($a_{i,0}$) and say a voltage setting for the $i$th observation ($a_{i,1}$), while $y_i$ might be an output brightness. So in that case you have observations (data points) consisting of (voltage,brightness) -- i.e. $(a_{i,1},y_i)$. (Note that brightness doesn't actually behave uniformly in reality; few things really do; if I wanted to find something that came close to it, I'd be asking an engineer or a physicist for an example)

If you try to plot these points you'll see why $a$ would be conventionally $x$ in statistics (the units here are arbitrary):

enter image description here

Now in the formulation you quote, $x$ contains the unknown parameters, which in my setup there will correspond to intercept ($x_0$) and slope ($x_1$) of the "true" line, which we attempt to estimate:

enter image description here

As you see, at each given voltage, the noise is uniformly scattered above and below the "true" (but unknown) line.

Imagine we took one particular value of voltage (4) and measured not 3 values, as here, but 100 values. Then it might look like this:

enter image description here

as you see, the values are uniformly spread but random in the interval. If we had 10000 values, a histogram of them would look like this:

enter image description here

each bin is equally likely to be represented; the underlying probability density has a rectangular "box" shape of constant probability density in the interval. As you moved to different voltages, the endpoints of the uniform shift, but its spread (distance between the endpoints, say) in this model would remain constant, and the uniform density within the bounds would remain.

The phrasing "The maximum likelihood estimation is" is a little odd. The algebraic expression, contains constants that don't contribute to the problem being solved (e.g. maximizing $a+bf(t)$ is the same as maximizing $f(t)$). What you have there is a maximization problem whose solution is the maximum likelihood estimator for $x$. You don't ask about the original likelihood function itself (in this case a function of the unknown parameters in $x$), so I presume you're happy about where that thing being maximized comes from (i.e. it's derived from taking the likelihood function for $x$ ($\prod_i f(y_i-a_i^Tx)$, where $f$ here is $\frac{1}{2c}$ on $[-c,c]$)) and trying to find the argmax). Slightly simplified (taking logs and using some manipulation), that will give the expression you have (though it's not clear why the simplification wasn't taken just a little further).

That the solution to the above problem maximizes the likelihood follows directly from writing the likelihood and taking the argmax (i.e. writing the problem to be solved).

In this case, the problem itself can be solved numerically (i.e. the values $x_0$ and $x_1$ in the above example) using linear programming methods; it's readily converted into a standard form and solved using standard software (I presume you don't seek details about how linear programming works)

The situation is not the same with Gaussian noise. The data points would relatively be more dense close to the "true" line and less dense as you move away, rather than being uniformly dense then suddenly "cutting out" as you moved further away. We'd still write a likelihood function based on the model (which would still be a linear model), and we'd still take the argmax to get MLEs for the unknown parameters, $x$, but in that case it would reduce to a simple least squares problem for $x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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