# Re: [R] missing values imputation

From: Ted Harding (Ted.Harding@nessie.mcc.ac.uk)
Date: Thu 13 May 2004 - 04:44:20 EST

```Message-id: <XFMail.040512194420.Ted.Harding@nessie.mcc.ac.uk>

```

On 12-May-04 A.J. Rossini wrote:
> (Ted Harding) <Ted.Harding@nessie.mcc.ac.uk> writes:
> [...]
>> Algorithm, this, or not????
> [...]
> Thanks, Ted :-) -- to extend it a bit, one can imagine the use of
> approximate solutions to the 2 steps (simulation methods to get
> expected values, similar range of approaches for the maximization) and
> get a general (but possibly not robust) computational solution for
> the parametric problem. Just plug in a formula for the likelihood and
> the sufficient statistics...

And thank you, Tony!

I confess to having deliberately been a bit provocative, since I see an
issue here on which I have a view (apparently shared by Tony).

For example:

Question: In your view, is the following "exchange sort" procedure
an algorithm? Or merely "a recipe for deriving an algorithm"?

A: Starting at the intended "low" end of the line compare each
i-th item X[i] with the (i+1)-th item X[i+1] for i=1,2,...
B: If you find an i such that X[i] > X[i+1],
exchange the positions of X[i] and X[i+1]
C: If you have reached the end of the line, stop.
Otherwise, go to (A).

Now, I think this is an algorithm. However, before reading on,

Well, you could use this to sort a line of people into order of
increasing height, without recourse to a measuring scale.

Just get X[i] and X[i+1] to stand up straight and look into each
others eyes. If X[i] has to look down into the eyes of X[i+1}, then
X[i] > X[i+1]; otherwise not.

The point is, illustrated naively by this example, that the above
description of "exchange sort" doesn't explain anything about ">".
So something has to be "plugged in" (in Tony's words) for ">", and
hence the algorithm, to have a meaning or an implementation. There
has to be a "sort key" with respect to which there is an implementation
of ">" in order to render the "algorithm" (my terminology ... ) concrete.
So yes, if being picky, the above description of "exchange sort" could be
called a "recipe for deriving an algorithm". But then a different
algorithm would result for (a) every different kind of thing which could
be sorted; (b) every different kind of interpretation of ">" (e.g. it
would not then be the same "algorithm" if you measured people's heights
with a scale). OK, now perhaps being "picky" in my turn ...

However, the general point is that an "algorithm", in my and no doubt
Tony's notion of it, usually needs a plugin or two or several in order
to be implemented for any particular case.

So for the EM algorithm.

It needs, specifically, a specification of the exponential-family
distribution, a means for computing a conditional expected value
with this distribution, and a solver for the complete-data maximum
likelihood equations. Once these are provided, the implementation
is complete.

Just as a coded computer routine can call a subroutine or co-routine,
so also one can envisage an algorithm calling a sub-algorithm.

Final question: What, for instance, is the status of the R function
"integrate"?

plugin <- function(x){x*(1-x)}
integrate(plugin,0,1)

uses (I quote):

For a finite interval, globally adaptive interval subdivision is
used in connection with extrapolation by the Epsilon algorithm.

If "plugin" has not been specified, does the code for "integrate"
represent an algorithm or not? Well, I rather think it does!

Best wishes to all,
Ted.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding@nessie.mcc.ac.uk>
Fax-to-email: +44 (0)870 167 1972
Date: 12-May-04 Time: 19:44:20
------------------------------ XFMail ------------------------------

______________________________________________
R-help@stat.math.ethz.ch mailing list
https://www.stat.math.ethz.ch/mailman/listinfo/r-help