Skip to content

BUG. LMNN loops when a bad update is calculated. #88

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
all2187 opened this issue Apr 25, 2018 · 2 comments
Closed

BUG. LMNN loops when a bad update is calculated. #88

all2187 opened this issue Apr 25, 2018 · 2 comments
Labels
Milestone

Comments

@all2187
Copy link

all2187 commented Apr 25, 2018

There seems to be a relatively large bug in the code for LMNN. In lines 157-164 we have:

# update step size
  if delta_obj > 0:
    # we're getting worse... roll back!
    learn_rate /= 2.0
    df = df_old
    a1 = a1_old
    a2 = a2_old
    objective = objective_old

But in an iteration the objective is calculated as (line 149-150):

objective = total_active * (1-reg)
      objective += G.flatten().dot(L.T.dot(L).flatten())

Where none of total_active, reg, G, or L depend on the learn_rate. Since that is the only thing changed when the above error occurs, the result of the iteration following the roll back will be the same as teh one that caused the roll back. Hence as soon as lines 157 to 164 are executed, the algorithm will just keep halving the learning rate and re calculating the same values until the max iteration is hit (as can be seen below):
image
The solution most likely is to either make the calculation of the new objective dependent on the learning rate, or revert L to its previous value also (as in the value it had when the previous iteration that did not cause a roll back started).

@fabienpesquerel
Copy link

fabienpesquerel commented Jun 23, 2018

This is a major issue ! I completely agree with all2187 on what he wrote above, thanks for reporting (although I do not understand why, even an unoptimized quick fix, nothing has been done to this day) .

I did something like below on my local version of this repository and it works just fine now. The thing is that it can get worst a every now and then but that is not an issue if the learn_rate parameters is set correctly at the beginning of the loop.

      if delta_obj > 0:
        # we're getting worse... roll back!
        learn_rate /= 2.0
        df = df_old
        a1 = a1_old
        a2 = a2_old
        objective = objective_old
        # the learning rate has been halfed      # ++++++
        L -= learn_rate * 2 * L.dot(G)           # ++++++
      else:
        # update L
        L -= learn_rate * 2 * L.dot(G)
        learn_rate *= 1.01

One solution to do a correct set up of the learn_rate parameter would be to compute the gradient at the initial point, compute the value of the objective function at the initial point and then loop the first step while the new objective value is greater than the initial one. This would avoid to compute to many bad values if we are initially close to the optimum relatively to the initial learn_rate parameter.

@wdevazelhes wdevazelhes added the bug label Jul 2, 2018
@wdevazelhes wdevazelhes added this to the v0.4.0 milestone Jul 2, 2018
wdevazelhes pushed a commit to wdevazelhes/metric-learn that referenced this issue Jul 2, 2018
Stores L and G in addition to what was stored before
@wdevazelhes
Copy link
Member

wdevazelhes commented Jul 2, 2018

I just proposed a quick fix in this PR: . It stores L and G in addition to what was already stored (df, a1 and a2), at the last "good" point (meaning the last time a point had a better objective than all the previous points), and gets back to this point if the update worsens the objective, as suggested by @all2187. I am not very familiar with LMNN so I may have missed something, but I guess it should fix the problem.

perimosocordiae pushed a commit that referenced this issue Aug 18, 2018
* FIX fixes #88
Stores L and G in addition to what was stored before

* TST: non regression test for this PR
- test that LMNN converges on a simple example where it should converge
- test that the objective function never has twice the same value

* MAINT: Invert the order of algorithm:
Try forward updates rather than doing rollback after wrong updates

* MAINT: update code according to comments #101 (review)

* FIX: update also test_convergence_simple_example

* FIX: remove \xc2 character

* FIX: use list to copy list for python2 compatibility

* MAINT: make code more readable with while break (see #101 (comment))

* FIX: remove non ascii character

* FIX: remove keyring.deb

* STY: remove unused imports
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

3 participants