**From:** Ted Harding (*Ted.Harding@nessie.mcc.ac.uk*)

**Date:** Thu 13 May 2004 - 04:44:20 EST

**Next message:**Gabor Grothendieck: "Re: [R] summary table newbie question"**Previous message:**Kel: "[R] Random Forest with highly imbalanced data"**In reply to:**A.J. Rossini: "Re: [R] missing values imputation"**Next in thread:**Liaw, Andy: "RE: [R] missing values imputation"

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,

please decide what you think yourself about this question.

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

PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

**Next message:**Gabor Grothendieck: "Re: [R] summary table newbie question"**Previous message:**Kel: "[R] Random Forest with highly imbalanced data"**In reply to:**A.J. Rossini: "Re: [R] missing values imputation"**Next in thread:**Liaw, Andy: "RE: [R] missing values imputation"

*
This archive was generated by hypermail 2.1.3
: Mon 31 May 2004 - 23:05:09 EST
*