> > I think Sachin wants to provide something similar to the LossFunction but > for the convergence criterion. This would mean that the user can specify a > convergence calculator, for example to the optimization framework, which is > used from within a iterateWithTermination call >
@Till, yes. This is what I had in mind. I think this is a good idea and it would be a nice addition to the > optimization framework, to begin with. I think that with (data, > previousModel, currentModel) one can already model a lot of different > convergence criteria. @Sachin, do you want to take the lead? > Surely. I will create a WIP PR so we can decide on the exact interface. However, I don’t think that a convergence criterion makes sense for the > Predictor, because there are also algorithms which are non-iterative, e.g. > some linear regression implementations. However, those which are, can take > a convergence calculator as a parameter value. > Yes. This is why I was thinking of providing a convergence criteria as a parameter, using a {{set}} function call on the predictor at the time user creates a new one. For non-iterative algorithms, I cannot think of any possible convergence criteria as such that would be required. The solutions are almost always closed-form in such cases. I may be wrong in saying that though. Regards Sachin Goel -- Sachin Goel Computer Science, IIT Delhi m. +91-9871457685 On Tue, Jul 7, 2015 at 2:23 PM, Sachin Goel <sachingoel0...@gmail.com> wrote: > Am I correct to assume that by "user" you mean library developers here? >> Regular users who just use the API are unlikely to write their own >> convergence >> criterion function, yes? They would just set a value, for example the >> relative >> error change in gradient descent, perhaps after choosing the criterion >> from >> a few available options. >> > It could be a library developer who can just leave the burden of > specifying a convergence criteria on the user, or a user who doesn't want > to hack on the algorithm itself, instead whatever convergence criteria they > think is best. Hard-coding convergence criteria in the algorithm itself is > a bad idea, since there can be a lot more tests than just the relative > changes in error etc. For example, user might want to have a validation set > and use the validation results to determine the convergence. Of course, > while performing *early stopping *due to validation accuracy decrease, > there are several approaches which build on tracking the training, and > validation errors over the past few iterations in which case user needs to > have an explicit ability to write convergence modules. [I know this is part > of the evaluation framework, to add validation. This is just one example.] > > > Yes, we use this approach in the GradientDescent code, where we check for >> convergence using the relative loss between iterations. >> >> So assuming that this is aimed at developers and checking for convergence >> can be done quite efficiently using the above technique, what extra >> functionality >> would these proposed functions provide? >> >> I expect any kind of syntactic sugar aimed at developers will still have >> to >> use >> iterateWithTermination underneath. >> > > The idea is to have a ConvergenceUtils library which provides the most > widely used convergence modules, like relative changes in error etc. After > this, while defining the Predictor, we have a {{setConvergenceCriteria}} > function with a user-defined call. > The algorithm implementation is itself abstracted away from this in the > sense that all we're effectively doing is writing > originalSolution.filter(x => !converged) > This can further be abstracted further away with a pimp-my-class type > function in ml/package.scala. > This reduces the code developers need to write to determine convergence > criteria and places them away in a separate common convergenc criteria > module. This is exactly similar to the Scorer and several widely used Score > functions you're working on in the Evaluation Framework PR. > > > Regards > Sachin Goel > > On Mon, Jul 6, 2015 at 9:47 PM, Theodore Vasiloudis < > theodoros.vasilou...@gmail.com> wrote: > >> > >> > The point is to provide user with the solution before an iteration and >> > >> >> Am I correct to assume that by "user" you mean library developers here? >> Regular users who just use the API are unlikely to write their own >> convergence >> criterion function, yes? They would just set a value, for example the >> relative >> error change in gradient descent, perhaps after choosing the criterion >> from >> a few available options. >> >> We can very well employ the iterateWithTermination >> > semantics even under this by setting the second term in the return >> value to >> > originalSolution.filter(x => !converged) >> >> >> Yes, we use this approach in the GradientDescent code, where we check for >> convergence using the relative loss between iterations. >> >> So assuming that this is aimed at developers and checking for convergence >> can be done quite efficiently using the above technique, what extra >> functionality >> would these proposed functions provide? >> >> I expect any kind of syntactic sugar aimed at developers will still have >> to >> use >> iterateWithTermination underneath. >> >> On Mon, Jul 6, 2015 at 4:47 PM, Sachin Goel <sachingoel0...@gmail.com> >> wrote: >> >> > Sure. >> > Usually, the convergence criterion can be user defined. For example, >> for a >> > linear regression problem, user might want to run the training until the >> > relative change in squared error falls below a specific threshold, or >> the >> > weights fail to shift by a relative or absolute percentage. >> > Similarly, for example, in the kmeans problem, we again have several >> > different convergence criteria based on the change in wcss value, or the >> > relative change in centroids. >> > >> > The point is to provide user with the solution before an iteration and >> > solution after an iteration and let them decide whether it's time to >> just >> > be done with iterating. We can very well employ the >> iterateWithTermination >> > semantics even under this by setting the second term in the return >> value to >> > originalSolution.filter(x => !converged) >> > where converged is determined by the user defined convergence >> criteria. Of >> > course, we're free to use our own convergence criteria in case the user >> > doesn't specify any. >> > >> > This achieves the desired effect. >> > >> > This way user has more fine grained control over the training phase. >> > Of course, to aid the user in defining their own convergence criteria, >> we >> > can provide some generic functions in the Predictor itself, for >> example, to >> > calculate the current value of the objective function. After this, rest >> is >> > upto the imagination of the user. >> > >> > Thinking more about this, I'd actually like to drop the idea of >> providing >> > an iteration state to the user. That only makes it more complicated and >> > further requires user to know what exactly goes in the algorithm. >> Usually, >> > the before and after solutions should suffice. I got too hung up on my >> > decision tree implementation and wanted to incorporate the convergence >> > criteria used there too. >> > >> > Cheers! >> > Sachin >> > >> > [Written from a mobile device. Might contain some typos or grammatical >> > errors] >> > On Jul 6, 2015 1:31 PM, "Theodore Vasiloudis" < >> > theodoros.vasilou...@gmail.com> wrote: >> > >> > > Hello Sachin, >> > > >> > > could you share the motivation behind this? The iterateWithTermination >> > > function provides us with a means of checking for convergence during >> > > iterations, and checking for convergence depends highly on the >> algorithm >> > > being implemented. It could be the relative change in error, it could >> > > depend on the state (error+weights) history, or relative or absolute >> > change >> > > in the model etc. >> > > >> > > Could you provide an example where having this function makes >> development >> > > easier? My concern is that this is a hard problem to generalize >> properly, >> > > given the dependence on the specific algorithm, model, and data. >> > > >> > > Regards, >> > > Theodore >> > > >> > > On Wed, Jul 1, 2015 at 9:23 PM, Sachin Goel <sachingoel0...@gmail.com >> > >> > > wrote: >> > > >> > > > Hi all >> > > > I'm trying to work out a general convergence framework for Machine >> > > Learning >> > > > Algorithms which utilize iterations for optimization. For now, I can >> > > think >> > > > of three kinds of convergence functions which might be useful. >> > > > 1. converge(data, modelBeforeIteration, modelAfterIteration) >> > > > 2. converge(data, modelAfterIteration) >> > > > 3. converge(data, modelBeforeIteration, iterationState, >> > > > modelAfterIteration) >> > > > >> > > > where iterationState is some state computed while performing the >> > > iteration. >> > > > >> > > > Algorithm implementation would have to support all three of these, >> if >> > > > possible. While specifying the {{Predictor}}, user would implement >> the >> > > > Convergence class and override these methods with their own >> > > implementation. >> > > > >> > > > Any feedback and design suggestions are welcome. >> > > > >> > > > Regards >> > > > >> > > > Sachin Goel >> > > > >> > > >> > >> > >