Re: GSoC/SoCiS: general maximum entropy algorithm

[Tomasz Ożański]

W dniu 27.03.2015 o 12:59, Olaf Till pisze:
> On Fri, Mar 27, 2015 at 02:09:15AM +0100, Tomasz Ożański wrote:
> > W dniu 26.03.2015 o 23:16, Juan Pablo Carbajal pisze:
> > > On Thu, Mar 26, 2015 at 4:24 PM, Jordi Gutiérrez Hermoso
> > > <address@hidden> wrote:
> > > > On Thu, 2015-03-26 at 13:44 +0100, Tomasz Ożański wrote:
> > > >
> > > > > What I would like to know is if you are interested in this sort of
> > > > > functionality in Octave?
> > > >
> > > > It certainly sounds useful, but I wonder if we have someone capable of
> > > > mentoring such a project. Perhaps Mike Miller? I don't know if he has
> > > > volunteered to mentor this year.
> > > >
> > > > - Jordi G. H.
> > > Olaf Till might be also suitable, since min max ent. is used a lot in
> > > optimization.
> >
> > I would be grateful if any of the proposed mentors would agree to
> > supervise my project.
>
> As for me, I'm not familiar with maximum entropy optimization and
> I'm not sure that I could get familiar enough with it in the required
> short time, so I don't think I could be a mentor.
I am aware that time for GSoC is short and it would be difficult to 
write a good proposal here. However, I am also eligible to participate 
in ESA Summer Of Code in Space for which there is still one month to go.
If the time is the matter here we can just aim for the other initiative 
(they don't give t-shirts though :) )

> Trying nevertheless to clarify something -- I can be completely wrong,
> but it seems to me that for maximizing entropy the nature of the model
> has to be considered, not only the deviations of observed values from
> values computed by the model function. If so, how is a _general_ ME
> algorithm possible? Even the reference you cite seems to give a
> "general" algorithm only for the still special case of image
> reconstruction. If I should be right in this, the proposed project
> would be no general optimization algorithm.
That's right, the article focuses on image reconstruction and they use a 
chi-squared criterium as an objective function which makes things a bit 
easier --  it guarantees the function is convex/concave.

The authors claim that the algorithm is also applicable to other image 
transformations so changing it to any other linear transformation 
(defined by a matrix or a function) shouldn't make much difference for 
the algorithm.

So yes, it is basically least-square fitting of data with entropy as a 
Tikhonov's regularizer and this would be one part of the project which I 
believe covers majority of the uses of MEM.

The other one will focus on a more general objective function.
The paper describes the procedures in means of derivatives (gradient and 
Hessian) and shows that there is a unique solution for any 
convex/concave objective function.

Probably this procedure has some limitations, but I believe it should 
give some reasonable results for some wide class of objective functions.
There would probably be needed some help from the user to provide the 
derivatives (or maybe the octave-ad package could be a help here), but I 
do not see any reason why it should not work, and implementing it is 
certainly possible.

Non-convex/non-concave functions are beyond of the scope of algorithm in 
the article, since the maximum-entropy solution might be no longer 
uniquely-defined, but who knows maybe for some problems there is only 
one or all the solutions are equally good for some reason.

So it's maybe not very general algorithm, but it's general in a sense 
that it is applicable in many areas and covers what is often considered 
as separate algorithms.

So this makes it just an another optimization algorithm, but maybe a one 
designed especially for constrained entropy maximization.

> Still I don't doubt that your project would be useful, without being
> able to thoroughly assess it. I hope someone can help you go on with
> it.
>
> > Everyone who is a potential mentor ought to be
> > a subscriber to this list and basically there aren't any other
> > places where I shall look for a supervisor for this project, right?
>
> I'd expect some users of Octave to have expert knowledge on this. The
> question is if they would undertake the effort and if they have write
> access to Octave or Octave Forge. Maybe there is some community
> mentoring or combined mentoring possible.
>
> You could possibly increase your chances by also asking at the help
> mailing list.
>
> Olaf
Thanks, I will ask there, but again we can just try to treat it as an 
optimization algorithm.

greetings,
--
Tomasz Ożański