On Dec 21, 2007 8:53 AM, Rémi Coulom <[EMAIL PROTECTED]> wrote: > Hi, > > Minorization-maximization is a simple optimization method, and I agree > that it is likely that more efficient algorithms can be applied. > > Newton's method implies estimating the inverse of the Hessian matrix. > Really computing the inverse has a cost cubic in the size of the matrix, > so it is not practical with tens of thousands of parameters. > > Nevertheless, Newton's method can be applied to each parameter one by > one. If I understand correctly, this is what Jason proposed. One step of > Newton's method on just one parameter has a computational cost very > similar to MM, and is much more efficient (it should converge in just > one or two iterations).
You understand correctly. Mine was based off what I remembered of Newton's method from High School. We didn't mess with Hessian matrices! Hunter's paper [1] does compare MM with the matrix form of the Newton-Raphson method. It shows convergence in far fewer iterations (6 vs. 26 in an example with 82 parameters) Given that doing one parameter at a time may be less ideal, I don't know if my method would really inherit those properties or not. > Still, MM has the advantage that it can be applied in batch mode, thus > saving a lot of computation. What do you mean by batch mode? Are you implying something like what's at the top of page 387 in Hunter's paper? [1]. I initially it as that, but I don't really believe that any more. It looks like too much work to be useful. For each iteration of batch updates, do you pass over the data computing whatever you can and then pick a set of mutually exclusive items to update? How bad would it be to update everything, including those on the same team? In what I'm envisioning for my method, computations of 1/Ej would also be shared for each computations. I'd also keep a running sum of the selection probability and the square of the selection probability. Once at the end of the data, I'd apply my equation to compute the update of all parameters. [1] http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.aos/1079120141
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
