Re: GSoC/SoCiS: general maximum entropy algorithm

[Olaf Till]

On Fri, Mar 27, 2015 at 04:26:08PM +0100, Tomasz Ożański wrote:
> 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

I've undertaken some effort in studying the paper. In places, I've
difficulties to follow the derivations or ideas, to a degree that I
couldn't verify them. To mentor, I'd think it necessary to check the
plausibility of all the details of the algorithm before an application
for this project. But I see now that this would cost me too much time
and work. I'm sorry.

Some issues have occured to me. I report them here, for the case that
they should still be useful.

General:

- I'm not sure that your characterization of the algorithm is always
  correct. Chi-squared is not the objective function, and the
  algorithm is not least squares with entropy as a
  regularizer. Rather, entropy (of the image) is the objective
  function, and the normalized sum of squared deviations from observed
  values of a (linear) user function (applied to the image) is an
  equality constraint (formally an inequality constraint, but taken as
  equality since otherwise entropy would be too large anyway (?)).

- Having this as an extra algorithm is justified by its applicability
  to a large scale (a million parameters (pixels)).

- The value of the (in-)equality constraint (a still "plausible"
  normalized sum of squared deviations) depends on the standard error
  of the observations (due to the normalization). The paper does not
  mention how this standard error is provided. By the user?

Description of algorithm details in the paper:

- In equation (5), 'A' is just given, it does not follow from the
  derivation, not even considering (6) and (7). Maybe this is not so
  important.

- Possibly more important, but not sure if I've misunderstood it: Do
  they want to apply the metric 'g_ij = 1/f^i(i=j)' (18) for limiting
  the step by computing the step with the (later defined) quadratic
  model with suitably normalized subspace base-vectors and a suitable
  quadratic term? In that context: in the paragraph before (19), do
  they mean that 'f(Nabla Q)' is dQ/df, its components (subscript i)
  multiplied with the components 1/f_i ? This seems reasonable for the
  linear term in the quadratic model (23) (linear term produces a
  difference of S given by a sum (subindex i) of ((dS/df_i)^2/f_i) as
  possibly intended (?) considering (18)), however, its quadratic term
  produces a sum of ((dS/df_i)^2/(f_i)^2), while a metric (18) applied
  to steps would yield a sum of ((dS/df_i)^2/f_i) ... ?

Olaf

-- 
public key id EAFE0591, e.g. on x-hkp://pool.sks-keyservers.net

signature.asc
Description: Digital signature