A bug in “obs_memo” function

[BojieSheng]

Describe the bug We think there is a bug in “obs_memo” function in TreeParzen library. When two hyperparameters have the same distribution in the Space relating to “vals”, “obs_memo” function returns a wrong hyperparameter name as it only looks for a hyperparameter’s distribution relating to “vals” through a dictionary which has a pair of hyperparameter name and its “vals”’s distribution. Then the returned hyperparameter name is used to collect history trials’ values for TreeParzen posterior inference, a wrong name will cause a wrong output result.

For example, if hyperparameters “A” and “B” have the same distribution in Space relating to “vals”, when giving the distribution of “A” into “obs_memo” function, it returns the name of “B”, thus the TreeParzeen posterior inference for “A” will collect “B”’s history trials, which cause a wrong output result.

To Reproduce Please run the following simple example code which have a space with different hyperparameters. The two hyperparameters “bagging_fraction” and “feature_fraction” have the same distribution “HP.QuantUniform(label, 0.1, 1.0, 1.), round)”.  

import TreeParzen
 
@testset "TreeParzen -- obs_memo bug" begin
 
    space = [
        Dict{Symbol, Any}(
            :bagging_fraction=> TreeParzen.HP.QuantUniform(:bagging_fraction, 0.1, 1.0, 1.),
            :feature_fraction=> TreeParzen.HP.QuantUniform(:feature_fraction, 0.1, 1.0, 1.),
        )
    ]
    TreeParzen.Graph.checkspace(space)
 
    params = Dict{Symbol, TreeParzen.Types.AbstractDelayed}(
        item.label => item.obj
            for item in TreeParzen.Graph.dfs(space)
                if TreeParzen.Resolve.walkable(item)
    )
 
    item = TreeParzen.Delayed.QuantUniform(0.1, 1.0, 1.)
    fraction_results = []
    for i in 1:2
        nid = TreeParzen.Resolve.obs_memo(item, params)
        push!(fraction_results, nid)
    end
    @test all(y->y==:feature_fraction, fraction_results)
 
end

Actual behaviour TreeParzen only collects the history trials of “feature_fraction” for both two hyperparameters (“bagging_fraction” and “feature_fraction”) posterior inference as “obs_memo” function only returns “feature_fraction” for both hyperparameters, thus the posterior inference for “bagging_fraction” will have the wrong result.

Expected behaviour 
TreeParzen should collect the history trials for all the hyperparameters separately for posterior inference, therefore “obs_memo” function should return correct name for different hyperparameters.

Environment:

• OS: Mac OSX
• Version: M1
• Julia Version: 1.6.7
• TreeParzen.jl Version: v0.3.1

Additional example 
Another example below shows a space with different hyperparameters that the name of the two hyperparameters (“num_leaves” and “min_data_in_leaf”) are different and they have different distributions, but they have the same “vals”’s function of “HP.QuantUniform(label, 1., 4., (15/19)), round)”, thus they have the same issue as mentioned above.  

import TreeParzen
 
@testset "TreeParzen -- obs_memo bug" begin
 
    space = [
        Dict{Symbol, Any}(
            :num_leaves => TreeParzen.Delayed.UnaryOperator(2 ^ TreeParzen.HP.QuantUniform(:num_leaves, 1., 4., (15 / 19)), round),
            :min_data_in_leaf => TreeParzen.Delayed.UnaryOperator(10000 * (3 ^ TreeParzen.HP.QuantUniform(:min_data_in_leaf, 1., 4., (15/19))), round),
        )
    ]
 
    TreeParzen.Graph.checkspace(space)
 
    params = Dict{Symbol, TreeParzen.Types.AbstractDelayed}(
        item.label => item.obj
            for item in TreeParzen.Graph.dfs(space)
                if TreeParzen.Resolve.walkable(item)
    )
 
    item = TreeParzen.Delayed.QuantUniform(1.0, 4.0, 0.7894736842105263)
    leaf_results = []
    for i in 1:2
        nid = TreeParzen.Resolve.obs_memo(item, params)
        push!(leaf_results, nid)
    end
    @test all(y->y==:min_data_in_leaf, leaf_results)
end

  TreeParzen only collects the history trials of “min_data_in_leaf” for both hyperparameters (“num_leaves” and “min_data_in_leaf”) posterior inference as “obs_memo” function only returns name of “min_data_in_leaf” for both hyperparameters, thus the posterior inference for “num_leaves” has the wrong result.

[FatemehTahavori]

@yaxxie could you please confirm that this is a bug so we can work on fixing it? we only want you to confirm it, not fix it ...

[yaxxie]

@BojieSheng thanks for taking the time to write this up, with a detailed case.

One thing I am uncertain about is whether or why this is a bug. To show the supposed buggy behaviour, there is use of the internal functions (and I've not looked super carefully but I'm not sure it is correct).

If I understand the claim correctly, it is that trial history is retrieved incorrectly when looking up from the history. But if it were true, then I would expect to see very weird behaviour at higher levels, from the ask/tell interface. So I decided to check this (with a modified space to make it clearer)

import TreeParzen

trialhist = TreeParzen.Trials.Trial[]
config = TreeParzen.Config(; random_trials=1, draws=1)

space = [
           Dict{Symbol, Any}(
               :bagging_fraction=> TreeParzen.HP.QuantUniform(:bagging_fraction, 0.1, 1.0, 0.1),
               :feature_fraction=> TreeParzen.HP.QuantUniform(:feature_fraction, 1.1, 2.0, 0.1),
           )
]

for i in 1:100

           trial1 = TreeParzen.ask(space, trialhist, config)
           TreeParzen.tell!(trialhist, trial1, rand())

end

if you then inspect the trialhist to see if any of the values went outside their bounds (which one would suppose would happen if we were retrieving the incorrect trials history for the parameter) we can see no evidence of this.

So, I would like to know under what circumstances you might be having an issue, at a higher level, in case there's some missing context, or if you came to this path while trying to find an explanation for an unusual behaviour.

I have no doubt there are bugs in this library, I'm just not sure without additional context that the specific thing described at is an issue. I will later on spend a bit more time looking at the examples given to see if either there is something I missed there or to explain why it is possibly an incorrect construction.

[BojieSheng]

@yaxxie Many thanks for your response. I am sorry for my vague explanation about the bug.   The bug is not about any values went outside their bounds and not about two hyperparameters with different distributions (as your example). If all the hyperparameters have unique distributions, there is no bug.   However when two hyperparameters have identical distribution (as my first example), it will cause the bug because when it runs the node() function for “:bagging_faction” item, obs_memo() function returns “:feature_fraction” as the “nid” (this is wrong as the “nid” should be “:bagging_faction”), thus the following Resolve.posterior() function will collect all the history trials’ values based on the “trial.vals[nid]” which collects all “:feature_fraction”’s values in history trials for the posterior inference, but it should collect all “:bagging_faction”’s values in history trials. Therefore the posterior inference output will be a wrong result for “:bagging_faction” as it is a result for “:feature_fraction”. Please check below screen copy about it in debug mode.  

Can you please let me know if this is not clear, how about we arrange a meeting on teams to discuss this? 

[yaxxie]

@BojieSheng thank you for clarifying, and for bringing this to our attention.

So to summarise, it seems that when we have at the same level of the lookup we have multiple distributions specified identically irrespective of the name, we retrieve only one of them.

This does correspond with some odd behavior observed before, so I can agree that this is likely to be a bug (and the source of the odd behavior).

@FatemehTahavori when resolving this it would be great to follow a couple of steps / principles:

1. A precise description of the conditions leading to the bug (in case what I wrote above is not actually sufficiently precise, because I fear it may actually be too narrow). More investigations are probably required.
2. Test cases reproducing the issue (ideally from a higher level if possible, at the ask/tell interface). In the case of a bug like this, I think its super important to write the cases before the fix. If when you make a PR you can push the tests which fail before the fix, all the better.

I've a few ideas and I'm happy to contribute towards the resolution of this issue.

[kainkad]

@BojieSheng can we close this issue given #90 was merged?

[BojieSheng]

@BojieSheng can we close this issue given #90 was merged?

yes, just closed now.